diff --git a/delta_diff_generator.cc b/delta_diff_generator.cc
index f024481..3dcd2cb 100644
--- a/delta_diff_generator.cc
+++ b/delta_diff_generator.cc
@@ -54,6 +54,13 @@
 const uint64_t kVersionNumber = 1;
 const uint64_t kFullUpdateChunkSize = 128 * 1024;  // bytes
 
+static const char* kInstallOperationTypes[] = {
+  "REPLACE",
+  "REPLACE_BZ",
+  "MOVE",
+  "BSDIFF"
+};
+
 // Stores all Extents for a file into 'out'. Returns true on success.
 bool GatherExtents(const string& path,
                    google::protobuf::RepeatedPtrField<Extent>* out) {
@@ -163,7 +170,8 @@
   TEST_AND_RETURN_FALSE(DeltaDiffGenerator::ReadFileToDiff(old_root + path,
                                                            new_root + path,
                                                            &data,
-                                                           &operation));
+                                                           &operation,
+                                                           true));
 
   // Write the data
   if (operation.type() != DeltaArchiveManifest_InstallOperation_Type_MOVE) {
@@ -395,51 +403,40 @@
   }
 }
 
-// Delta compresses a kernel partition new_kernel_part with knowledge of
-// the old kernel partition old_kernel_part.
+// Delta compresses a kernel partition |new_kernel_part| with knowledge of the
+// old kernel partition |old_kernel_part|. If |old_kernel_part| is an empty
+// string, generates a full update of the partition.
 bool DeltaCompressKernelPartition(
     const string& old_kernel_part,
     const string& new_kernel_part,
     vector<DeltaArchiveManifest_InstallOperation>* ops,
     int blobs_fd,
     off_t* blobs_length) {
-  // For now, just bsdiff the kernel partition as a whole.
-  // TODO(adlr): Use knowledge of how the kernel partition is laid out
-  // to more efficiently compress it.
-
   LOG(INFO) << "Delta compressing kernel partition...";
+  LOG_IF(INFO, old_kernel_part.empty()) << "Generating full kernel update...";
 
   // Add a new install operation
   ops->resize(1);
   DeltaArchiveManifest_InstallOperation* op = &(*ops)[0];
-  op->set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
-  op->set_data_offset(*blobs_length);
 
-  // Do the actual compression
   vector<char> data;
-  TEST_AND_RETURN_FALSE(utils::ReadFile(new_kernel_part, &data));
-  TEST_AND_RETURN_FALSE(!data.empty());
+  TEST_AND_RETURN_FALSE(DeltaDiffGenerator::ReadFileToDiff(old_kernel_part,
+                                                           new_kernel_part,
+                                                           &data,
+                                                           op,
+                                                           false));
 
-  vector<char> data_bz;
-  TEST_AND_RETURN_FALSE(BzipCompress(data, &data_bz));
-  CHECK(!data_bz.empty());
+  // Write the data
+  if (op->type() != DeltaArchiveManifest_InstallOperation_Type_MOVE) {
+    op->set_data_offset(*blobs_length);
+    op->set_data_length(data.size());
+  }
 
-  TEST_AND_RETURN_FALSE(utils::WriteAll(blobs_fd, &data_bz[0], data_bz.size()));
-  *blobs_length += data_bz.size();
+  TEST_AND_RETURN_FALSE(utils::WriteAll(blobs_fd, &data[0], data.size()));
+  *blobs_length += data.size();
 
-  off_t new_part_size = utils::FileSize(new_kernel_part);
-  TEST_AND_RETURN_FALSE(new_part_size >= 0);
-
-  op->set_data_length(data_bz.size());
-
-  op->set_dst_length(new_part_size);
-
-  // There's a single dest extent
-  Extent* dst_extent = op->add_dst_extents();
-  dst_extent->set_start_block(0);
-  dst_extent->set_num_blocks((new_part_size + kBlockSize - 1) / kBlockSize);
-
-  LOG(INFO) << "Done compressing kernel partition.";
+  LOG(INFO) << "Done delta compressing kernel partition: "
+            << kInstallOperationTypes[op->type()];
   return true;
 }
 
@@ -456,13 +453,6 @@
   off_t size;
 };
 
-static const char* kInstallOperationTypes[] = {
-  "REPLACE",
-  "REPLACE_BZ",
-  "MOVE",
-  "BSDIFF"
-};
-
 void ReportPayloadUsage(const Graph& graph,
                         const DeltaArchiveManifest& manifest,
                         const int64_t manifest_metadata_size) {
@@ -517,7 +507,8 @@
     const string& old_filename,
     const string& new_filename,
     vector<char>* out_data,
-    DeltaArchiveManifest_InstallOperation* out_op) {
+    DeltaArchiveManifest_InstallOperation* out_op,
+    bool gather_extents) {
   // Read new data in
   vector<char> new_data;
   TEST_AND_RETURN_FALSE(utils::ReadFile(new_filename, &new_data));
@@ -544,10 +535,13 @@
 
   // Do we have an original file to consider?
   struct stat old_stbuf;
-  if (0 != stat(old_filename.c_str(), &old_stbuf)) {
+  bool no_original = old_filename.empty();
+  if (!no_original && 0 != stat(old_filename.c_str(), &old_stbuf)) {
     // If stat-ing the old file fails, it should be because it doesn't exist.
     TEST_AND_RETURN_FALSE(errno == ENOTDIR || errno == ENOENT);
-  } else {
+    no_original = true;
+  }
+  if (!no_original) {
     // Read old data
     vector<char> old_data;
     TEST_AND_RETURN_FALSE(utils::ReadFile(old_filename, &old_data));
@@ -576,13 +570,26 @@
 
   if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE ||
       operation.type() == DeltaArchiveManifest_InstallOperation_Type_BSDIFF) {
-    TEST_AND_RETURN_FALSE(
-        GatherExtents(old_filename, operation.mutable_src_extents()));
+    if (gather_extents) {
+      TEST_AND_RETURN_FALSE(
+          GatherExtents(old_filename, operation.mutable_src_extents()));
+    } else {
+      Extent* src_extent = operation.add_src_extents();
+      src_extent->set_start_block(0);
+      src_extent->set_num_blocks(
+          (old_stbuf.st_size + kBlockSize - 1) / kBlockSize);
+    }
     operation.set_src_length(old_stbuf.st_size);
   }
 
-  TEST_AND_RETURN_FALSE(
-      GatherExtents(new_filename, operation.mutable_dst_extents()));
+  if (gather_extents) {
+    TEST_AND_RETURN_FALSE(
+        GatherExtents(new_filename, operation.mutable_dst_extents()));
+  } else {
+    Extent* dst_extent = operation.add_dst_extents();
+    dst_extent->set_start_block(0);
+    dst_extent->set_num_blocks((new_data.size() + kBlockSize - 1) / kBlockSize);
+  }
   operation.set_dst_length(new_data.size());
 
   out_data->swap(data);
@@ -1273,8 +1280,6 @@
     TEST_AND_RETURN_FALSE(old_image_block_size == new_image_block_size);
     LOG_IF(WARNING, old_image_block_count != new_image_block_count)
         << "Old and new images have different block counts.";
-    // Sanity check kernel partition arg
-    TEST_AND_RETURN_FALSE(utils::FileSize(old_kernel_part) >= 0);
   }
   // Sanity check kernel partition arg
   TEST_AND_RETURN_FALSE(utils::FileSize(new_kernel_part) >= 0);
diff --git a/delta_diff_generator.h b/delta_diff_generator.h
index d3eee3e..de3be0d 100644
--- a/delta_diff_generator.h
+++ b/delta_diff_generator.h
@@ -97,7 +97,8 @@
   static bool ReadFileToDiff(const std::string& old_filename,
                              const std::string& new_filename,
                              std::vector<char>* out_data,
-                             DeltaArchiveManifest_InstallOperation* out_op);
+                             DeltaArchiveManifest_InstallOperation* out_op,
+                             bool gather_extents);
 
   // Modifies blocks read by 'op' so that any blocks referred to by
   // 'remove_extents' are replaced with blocks from 'replace_extents'.
diff --git a/delta_diff_generator_unittest.cc b/delta_diff_generator_unittest.cc
index 0d7b0fe..d897a0a 100644
--- a/delta_diff_generator_unittest.cc
+++ b/delta_diff_generator_unittest.cc
@@ -1,4 +1,4 @@
-// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
@@ -67,7 +67,8 @@
   EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
                                                  new_path(),
                                                  &data,
-                                                 &op));
+                                                 &op,
+                                                 true));
   EXPECT_TRUE(data.empty());
 
   EXPECT_TRUE(op.has_type());
@@ -95,7 +96,8 @@
   EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
                                                  new_path(),
                                                  &data,
-                                                 &op));
+                                                 &op,
+                                                 true));
   EXPECT_FALSE(data.empty());
 
   EXPECT_TRUE(op.has_type());
@@ -125,7 +127,8 @@
     EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
                                                    new_path(),
                                                    &data,
-                                                   &op));
+                                                   &op,
+                                                   true));
     EXPECT_FALSE(data.empty());
 
     EXPECT_TRUE(op.has_type());
@@ -143,6 +146,36 @@
   }
 }
 
+TEST_F(DeltaDiffGeneratorTest, RunAsRootBsdiffNoGatherExtentsSmallTest) {
+  EXPECT_TRUE(utils::WriteFile(old_path().c_str(),
+                               reinterpret_cast<const char*>(kRandomString),
+                               sizeof(kRandomString) - 1));
+  EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
+                               reinterpret_cast<const char*>(kRandomString),
+                               sizeof(kRandomString)));
+  vector<char> data;
+  DeltaArchiveManifest_InstallOperation op;
+  EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
+                                                 new_path(),
+                                                 &data,
+                                                 &op,
+                                                 false));
+  EXPECT_FALSE(data.empty());
+
+  EXPECT_TRUE(op.has_type());
+  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_BSDIFF, op.type());
+  EXPECT_FALSE(op.has_data_offset());
+  EXPECT_FALSE(op.has_data_length());
+  EXPECT_EQ(1, op.src_extents_size());
+  EXPECT_EQ(0, op.src_extents().Get(0).start_block());
+  EXPECT_EQ(1, op.src_extents().Get(0).num_blocks());
+  EXPECT_EQ(sizeof(kRandomString) - 1, op.src_length());
+  EXPECT_EQ(1, op.dst_extents_size());
+  EXPECT_EQ(0, op.dst_extents().Get(0).start_block());
+  EXPECT_EQ(1, op.dst_extents().Get(0).num_blocks());
+  EXPECT_EQ(sizeof(kRandomString), op.dst_length());
+}
+
 namespace {
 void AppendExtent(vector<Extent>* vect, uint64_t start, uint64_t length) {
   vect->resize(vect->size() + 1);
@@ -171,9 +204,9 @@
   OpAppendExtent(&op, kSparseHole, 4);  // Sparse hole in file
   OpAppendExtent(&op, 3, 1);
   OpAppendExtent(&op, 7, 3);
-  
+
   DeltaDiffGenerator::SubstituteBlocks(&vertex, remove_blocks, replace_blocks);
-  
+
   EXPECT_EQ(7, op.src_extents_size());
   EXPECT_EQ(11, op.src_extents(0).start_block());
   EXPECT_EQ(1, op.src_extents(0).num_blocks());
@@ -194,7 +227,7 @@
 TEST_F(DeltaDiffGeneratorTest, CutEdgesTest) {
   Graph graph;
   vector<Block> blocks(9);
-  
+
   // Create nodes in graph
   {
     graph.resize(graph.size() + 1);
@@ -209,7 +242,7 @@
     blocks[3].reader = graph.size() - 1;
     blocks[5].reader = graph.size() - 1;
     blocks[7].reader = graph.size() - 1;
-    
+
     // Writes to blocks 1, 2, 4
     extents.clear();
     graph_utils::AppendBlockToExtents(&extents, 1);
@@ -234,7 +267,7 @@
     blocks[1].reader = graph.size() - 1;
     blocks[2].reader = graph.size() - 1;
     blocks[4].reader = graph.size() - 1;
-    
+
     // Writes to blocks 3, 5, 6
     extents.clear();
     graph_utils::AppendBlockToExtents(&extents, 3);
@@ -246,10 +279,10 @@
     blocks[5].writer = graph.size() - 1;
     blocks[6].writer = graph.size() - 1;
   }
-  
+
   // Create edges
   DeltaDiffGenerator::CreateEdges(&graph, blocks);
-  
+
   // Find cycles
   CycleBreaker cycle_breaker;
   set<Edge> cut_edges;
@@ -261,9 +294,9 @@
 
   vector<CutEdgeVertexes> cuts;
   EXPECT_TRUE(DeltaDiffGenerator::CutEdges(&graph, cut_edges, &cuts));
-  
+
   EXPECT_EQ(3, graph.size());
-  
+
   // Check new node in graph:
   EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE,
             graph.back().op.type());
@@ -272,7 +305,7 @@
   EXPECT_EQ(kTempBlockStart, graph.back().op.dst_extents(0).start_block());
   EXPECT_EQ(2, graph.back().op.dst_extents(0).num_blocks());
   EXPECT_TRUE(graph.back().out_edges.empty());
-  
+
   // Check that old node reads from new blocks
   EXPECT_EQ(2, graph[0].op.src_extents_size());
   EXPECT_EQ(kTempBlockStart, graph[0].op.src_extents(0).start_block());
@@ -305,7 +338,7 @@
   EXPECT_EQ(1, graph[1].op.dst_extents(0).num_blocks());
   EXPECT_EQ(5, graph[1].op.dst_extents(1).start_block());
   EXPECT_EQ(2, graph[1].op.dst_extents(1).num_blocks());
-  
+
   // Ensure it only depends on the next node
   EXPECT_EQ(1, graph[1].out_edges.size());
   EXPECT_TRUE(graph[1].out_edges.end() != graph[1].out_edges.find(2));
@@ -323,7 +356,7 @@
   string new_blobs;
   EXPECT_TRUE(
       utils::MakeTempFile("ReorderBlobsTest.new.XXXXXX", &new_blobs, NULL));
-  
+
   DeltaArchiveManifest manifest;
   DeltaArchiveManifest_InstallOperation* op =
       manifest.add_install_operations();
@@ -332,11 +365,11 @@
   op = manifest.add_install_operations();
   op->set_data_offset(0);
   op->set_data_length(1);
-  
+
   EXPECT_TRUE(DeltaDiffGenerator::ReorderDataBlobs(&manifest,
                                                    orig_blobs,
                                                    new_blobs));
-                                                   
+
   string new_data;
   EXPECT_TRUE(utils::ReadFileToString(new_blobs, &new_data));
   EXPECT_EQ("bcda", new_data);
@@ -345,7 +378,7 @@
   EXPECT_EQ(3, manifest.install_operations(0).data_length());
   EXPECT_EQ(3, manifest.install_operations(1).data_offset());
   EXPECT_EQ(1, manifest.install_operations(1).data_length());
-  
+
   unlink(orig_blobs.c_str());
   unlink(new_blobs.c_str());
 }
@@ -424,7 +457,7 @@
   Graph graph(9);
   const vector<Extent> empt;  // empty
   const string kFilename = "/foo";
-  
+
   // Some scratch space:
   GenVertex(&graph[0], empt, VectOfExt(200, 1), "", OP_REPLACE);
   GenVertex(&graph[1], empt, VectOfExt(210, 10), "", OP_REPLACE);
@@ -455,9 +488,9 @@
             kFilename,
             OP_BSDIFF);
   graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
-  
+
   graph_utils::DumpGraph(graph);
-  
+
   vector<Vertex::Index> final_order;
 
 
@@ -466,13 +499,13 @@
   EXPECT_TRUE(utils::MakeTempDirectory("/tmp/AssignTempBlocksTest.XXXXXX",
                                        &temp_dir));
   ScopedDirRemover temp_dir_remover(temp_dir);
-  
+
   const size_t kBlockSize = 4096;
   vector<char> temp_data(kBlockSize * 50);
   FillWithData(&temp_data);
   EXPECT_TRUE(WriteFileVector(temp_dir + kFilename, temp_data));
   ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
-  
+
   int fd;
   EXPECT_TRUE(utils::MakeTempFile("/tmp/AssignTempBlocksTestData.XXXXXX",
                                   NULL,
@@ -487,7 +520,7 @@
                                                     &data_file_size,
                                                     &final_order));
 
-  
+
   Graph expected_graph(12);
   GenVertex(&expected_graph[0], empt, VectOfExt(200, 1), "", OP_REPLACE);
   GenVertex(&expected_graph[1], empt, VectOfExt(210, 10), "", OP_REPLACE);
@@ -519,7 +552,7 @@
             OP_BSDIFF);
   expected_graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11));
   expected_graph[6].out_edges[10] = EdgeWithWriteDep(VectOfExt(60, 10));
-  
+
   GenVertex(&expected_graph[7],
             VectOfExt(120, 50),
             VectOfExt(60, 40),
@@ -542,7 +575,7 @@
             "",
             OP_MOVE);
   expected_graph[10].out_edges[4] = EdgeWithReadDep(VectOfExt(60, 9));
-  
+
   EXPECT_EQ(12, graph.size());
   EXPECT_FALSE(graph.back().valid);
   for (Graph::size_type i = 0; i < graph.size() - 1; i++) {
diff --git a/delta_performer_unittest.cc b/delta_performer_unittest.cc
index 4f6661e..5a48441 100755
--- a/delta_performer_unittest.cc
+++ b/delta_performer_unittest.cc
@@ -111,9 +111,8 @@
   TEST_AND_RETURN_FALSE_ERRNO(return_code == 0);
   return true;
 }
-}
 
-TEST(DeltaPerformerTest, RunAsRootSmallImageTest) {
+void DoSmallImageTest(bool full_kernel) {
   string a_img, b_img;
   EXPECT_TRUE(utils::MakeTempFile("/tmp/a_img.XXXXXX", &a_img, NULL));
   ScopedPathUnlinker a_img_unlinker(a_img);
@@ -213,14 +212,15 @@
     ScopedLoopMounter b_mounter(b_img, &b_mnt, MS_RDONLY);
 
     EXPECT_TRUE(
-        DeltaDiffGenerator::GenerateDeltaUpdateFile(a_mnt,
-                                                    a_img,
-                                                    b_mnt,
-                                                    b_img,
-                                                    old_kernel,
-                                                    new_kernel,
-                                                    delta_path,
-                                                    kUnittestPrivateKeyPath));
+        DeltaDiffGenerator::GenerateDeltaUpdateFile(
+            a_mnt,
+            a_img,
+            b_mnt,
+            b_img,
+            full_kernel ? "" : old_kernel,
+            new_kernel,
+            delta_path,
+            kUnittestPrivateKeyPath));
   }
 
   // Read delta into memory.
@@ -321,6 +321,15 @@
       delta.size()));
   EXPECT_TRUE(performer.VerifyAppliedUpdate(a_img, old_kernel));
 }
+}
+
+TEST(DeltaPerformerTest, RunAsRootSmallImageTest) {
+  DoSmallImageTest(false);
+}
+
+TEST(DeltaPerformerTest, RunAsRootFullKernelSmallImageTest) {
+  DoSmallImageTest(true);
+}
 
 TEST(DeltaPerformerTest, NewFullUpdateTest) {
   vector<char> new_root(20 * 1024 * 1024);
diff --git a/generate_delta_main.cc b/generate_delta_main.cc
index a113e15..efeeb3b 100644
--- a/generate_delta_main.cc
+++ b/generate_delta_main.cc
@@ -102,7 +102,6 @@
     LOG(INFO) << "Generating full update";
   } else {
     LOG(INFO) << "Generating delta update";
-    CHECK(!FLAGS_old_kernel.empty());
     CHECK(!FLAGS_old_dir.empty());
     CHECK(!FLAGS_new_dir.empty());
     if ((!IsDir(FLAGS_old_dir.c_str())) || (!IsDir(FLAGS_new_dir.c_str()))) {