diff --git a/payload_generator/ab_generator.cc b/payload_generator/ab_generator.cc
new file mode 100644
index 0000000..7a9c748
--- /dev/null
+++ b/payload_generator/ab_generator.cc
@@ -0,0 +1,373 @@
+// Copyright 2015 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.
+
+#include "update_engine/payload_generator/ab_generator.h"
+
+#include <algorithm>
+
+#include <base/strings/stringprintf.h>
+
+#include "update_engine/bzip.h"
+#include "update_engine/delta_performer.h"
+#include "update_engine/payload_generator/annotated_operation.h"
+#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/delta_diff_utils.h"
+#include "update_engine/payload_generator/ext2_filesystem.h"
+#include "update_engine/utils.h"
+
+using std::string;
+using std::unique_ptr;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+
+// Compare two AnnotatedOperations by the start block of the first Extent in
+// their destination extents.
+bool CompareAopsByDestination(AnnotatedOperation first_aop,
+                              AnnotatedOperation second_aop) {
+  // We want empty operations to be at the end of the payload.
+  if (!first_aop.op.dst_extents().size() || !second_aop.op.dst_extents().size())
+    return ((!first_aop.op.dst_extents().size()) <
+            (!second_aop.op.dst_extents().size()));
+  uint32_t first_dst_start = first_aop.op.dst_extents(0).start_block();
+  uint32_t second_dst_start = second_aop.op.dst_extents(0).start_block();
+  return first_dst_start < second_dst_start;
+}
+
+}  // namespace
+
+bool ABGenerator::GenerateOperations(
+    const PayloadGenerationConfig& config,
+    int data_file_fd,
+    off_t* data_file_size,
+    vector<AnnotatedOperation>* rootfs_ops,
+    vector<AnnotatedOperation>* kernel_ops) {
+  unique_ptr<Ext2Filesystem> old_fs = Ext2Filesystem::CreateFromFile(
+      config.source.rootfs.path);
+  unique_ptr<Ext2Filesystem> new_fs = Ext2Filesystem::CreateFromFile(
+      config.target.rootfs.path);
+
+  off_t chunk_blocks = (config.chunk_size == -1 ? -1 :
+                        config.chunk_size / config.block_size);
+
+  rootfs_ops->clear();
+  TEST_AND_RETURN_FALSE(diff_utils::DeltaReadFilesystem(
+      rootfs_ops,
+      config.source.rootfs.path,
+      config.target.rootfs.path,
+      old_fs.get(),
+      new_fs.get(),
+      chunk_blocks,
+      data_file_fd,
+      data_file_size,
+      false,  // skip_block_0
+      true));  // src_ops_allowed
+  LOG(INFO) << "done reading normal files";
+
+  // Read kernel partition
+  TEST_AND_RETURN_FALSE(diff_utils::DeltaCompressKernelPartition(
+      config.source.kernel.path,
+      config.target.kernel.path,
+      config.source.kernel.size,
+      config.target.kernel.size,
+      config.block_size,
+      kernel_ops,
+      data_file_fd,
+      data_file_size,
+      true));  // src_ops_allowed
+  LOG(INFO) << "done reading kernel";
+
+  TEST_AND_RETURN_FALSE(FragmentOperations(rootfs_ops,
+                                           config.target.rootfs.path,
+                                           data_file_fd,
+                                           data_file_size));
+  TEST_AND_RETURN_FALSE(FragmentOperations(kernel_ops,
+                                           config.target.kernel.path,
+                                           data_file_fd,
+                                           data_file_size));
+  SortOperationsByDestination(rootfs_ops);
+  SortOperationsByDestination(kernel_ops);
+  // TODO(alliewood): Change merge operations to use config.chunk_size once
+  // specifying chunk_size on the command line works. crbug/485397.
+  TEST_AND_RETURN_FALSE(MergeOperations(rootfs_ops,
+                                        kDefaultChunkSize,
+                                        config.target.rootfs.path,
+                                        data_file_fd,
+                                        data_file_size));
+  TEST_AND_RETURN_FALSE(MergeOperations(kernel_ops,
+                                        kDefaultChunkSize,
+                                        config.target.kernel.path,
+                                        data_file_fd,
+                                        data_file_size));
+  return true;
+}
+
+void ABGenerator::SortOperationsByDestination(
+    vector<AnnotatedOperation>* aops) {
+  sort(aops->begin(), aops->end(), CompareAopsByDestination);
+}
+
+bool ABGenerator::FragmentOperations(
+    vector<AnnotatedOperation>* aops,
+    const string& target_part_path,
+    int data_fd,
+    off_t* data_file_size) {
+  vector<AnnotatedOperation> fragmented_aops;
+  for (const AnnotatedOperation& aop : *aops) {
+    if (aop.op.type() ==
+        DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY) {
+      TEST_AND_RETURN_FALSE(SplitSourceCopy(aop, &fragmented_aops));
+    } else if ((aop.op.type() ==
+                DeltaArchiveManifest_InstallOperation_Type_REPLACE) ||
+               (aop.op.type() ==
+                DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ)) {
+      TEST_AND_RETURN_FALSE(SplitReplaceOrReplaceBz(aop, &fragmented_aops,
+                                                    target_part_path, data_fd,
+                                                    data_file_size));
+    } else {
+      fragmented_aops.push_back(aop);
+    }
+  }
+  *aops = fragmented_aops;
+  return true;
+}
+
+bool ABGenerator::SplitSourceCopy(
+    const AnnotatedOperation& original_aop,
+    vector<AnnotatedOperation>* result_aops) {
+  DeltaArchiveManifest_InstallOperation original_op = original_aop.op;
+  TEST_AND_RETURN_FALSE(original_op.type() ==
+                        DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
+  // Keeps track of the index of curr_src_ext.
+  int curr_src_ext_index = 0;
+  Extent curr_src_ext = original_op.src_extents(curr_src_ext_index);
+  for (int i = 0; i < original_op.dst_extents_size(); i++) {
+    Extent dst_ext = original_op.dst_extents(i);
+    // The new operation which will have only one dst extent.
+    DeltaArchiveManifest_InstallOperation new_op;
+    uint64_t blocks_left = dst_ext.num_blocks();
+    while (blocks_left > 0) {
+      if (curr_src_ext.num_blocks() <= blocks_left) {
+        // If the curr_src_ext is smaller than dst_ext, add it.
+        blocks_left -= curr_src_ext.num_blocks();
+        *(new_op.add_src_extents()) = curr_src_ext;
+        if (curr_src_ext_index + 1 < original_op.src_extents().size()) {
+          curr_src_ext = original_op.src_extents(++curr_src_ext_index);
+        } else {
+          break;
+        }
+      } else {
+        // Split src_exts that are bigger than the dst_ext we're dealing with.
+        Extent first_ext;
+        first_ext.set_num_blocks(blocks_left);
+        first_ext.set_start_block(curr_src_ext.start_block());
+        *(new_op.add_src_extents()) = first_ext;
+        // Keep the second half of the split op.
+        curr_src_ext.set_num_blocks(curr_src_ext.num_blocks() - blocks_left);
+        curr_src_ext.set_start_block(curr_src_ext.start_block() + blocks_left);
+        blocks_left -= first_ext.num_blocks();
+      }
+    }
+    // Fix up our new operation and add it to the results.
+    new_op.set_type(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
+    *(new_op.add_dst_extents()) = dst_ext;
+    new_op.set_src_length(dst_ext.num_blocks() * kBlockSize);
+    new_op.set_dst_length(dst_ext.num_blocks() * kBlockSize);
+
+    AnnotatedOperation new_aop;
+    new_aop.op = new_op;
+    new_aop.name = base::StringPrintf("%s:%d", original_aop.name.c_str(), i);
+    result_aops->push_back(new_aop);
+  }
+  if (curr_src_ext_index != original_op.src_extents().size() - 1) {
+    LOG(FATAL) << "Incorrectly split SOURCE_COPY operation. Did not use all "
+               << "source extents.";
+  }
+  return true;
+}
+
+bool ABGenerator::SplitReplaceOrReplaceBz(
+    const AnnotatedOperation& original_aop,
+    vector<AnnotatedOperation>* result_aops,
+    const string& target_part_path,
+    int data_fd,
+    off_t* data_file_size) {
+  DeltaArchiveManifest_InstallOperation original_op = original_aop.op;
+  const bool is_replace =
+      original_op.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE;
+  TEST_AND_RETURN_FALSE(
+      is_replace ||
+      (original_op.type() ==
+       DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ));
+
+  uint32_t data_offset = original_op.data_offset();
+  for (int i = 0; i < original_op.dst_extents_size(); i++) {
+    Extent dst_ext = original_op.dst_extents(i);
+    // Make a new operation with only one dst extent.
+    DeltaArchiveManifest_InstallOperation new_op;
+    *(new_op.add_dst_extents()) = dst_ext;
+    uint32_t data_size = dst_ext.num_blocks() * kBlockSize;
+    new_op.set_dst_length(data_size);
+    // If this is a REPLACE, attempt to reuse portions of the existing blob.
+    if (is_replace) {
+      new_op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+      new_op.set_data_length(data_size);
+      new_op.set_data_offset(data_offset);
+      data_offset += data_size;
+    }
+
+    AnnotatedOperation new_aop;
+    new_aop.op = new_op;
+    new_aop.name = base::StringPrintf("%s:%d", original_aop.name.c_str(), i);
+    TEST_AND_RETURN_FALSE(AddDataAndSetType(&new_aop, target_part_path, data_fd,
+                                            data_file_size));
+
+    result_aops->push_back(new_aop);
+  }
+  return true;
+}
+
+bool ABGenerator::MergeOperations(vector<AnnotatedOperation>* aops,
+                                  off_t chunk_size,
+                                  const string& target_part_path,
+                                  int data_fd,
+                                  off_t* data_file_size) {
+  vector<AnnotatedOperation> new_aops;
+  for (const AnnotatedOperation& curr_aop : *aops) {
+    if (new_aops.empty()) {
+      new_aops.push_back(curr_aop);
+      continue;
+    }
+    AnnotatedOperation& last_aop = new_aops.back();
+
+    if (last_aop.op.dst_extents_size() <= 0 ||
+        curr_aop.op.dst_extents_size() <= 0) {
+      new_aops.push_back(curr_aop);
+      continue;
+    }
+    uint32_t last_dst_idx = last_aop.op.dst_extents_size() - 1;
+    uint32_t last_end_block =
+        last_aop.op.dst_extents(last_dst_idx).start_block() +
+        last_aop.op.dst_extents(last_dst_idx).num_blocks();
+    uint32_t curr_start_block = curr_aop.op.dst_extents(0).start_block();
+    uint32_t combined_block_count =
+        last_aop.op.dst_extents(last_dst_idx).num_blocks() +
+        curr_aop.op.dst_extents(0).num_blocks();
+    bool good_op_type =
+        curr_aop.op.type() ==
+            DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY ||
+        curr_aop.op.type() ==
+            DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
+        curr_aop.op.type() ==
+            DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ;
+    if (good_op_type &&
+        last_aop.op.type() == curr_aop.op.type() &&
+        last_end_block == curr_start_block &&
+        static_cast<off_t>(combined_block_count * kBlockSize) <= chunk_size) {
+      // If the operations have the same type (which is a type that we can
+      // merge), are contiguous, are fragmented to have one destination extent,
+      // and their combined block count would be less than chunk size, merge
+      // them.
+      last_aop.name = base::StringPrintf("%s,%s",
+                                         last_aop.name.c_str(),
+                                         curr_aop.name.c_str());
+
+      ExtendExtents(last_aop.op.mutable_src_extents(),
+                    curr_aop.op.src_extents());
+      if (curr_aop.op.src_length() > 0)
+        last_aop.op.set_src_length(last_aop.op.src_length() +
+                                   curr_aop.op.src_length());
+      ExtendExtents(last_aop.op.mutable_dst_extents(),
+                    curr_aop.op.dst_extents());
+      if (curr_aop.op.dst_length() > 0)
+        last_aop.op.set_dst_length(last_aop.op.dst_length() +
+                                   curr_aop.op.dst_length());
+      // Set the data length to zero so we know to add the blob later.
+      if (curr_aop.op.type() ==
+          DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
+          curr_aop.op.type() ==
+          DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) {
+        last_aop.op.set_data_length(0);
+      }
+    } else {
+      // Otherwise just include the extent as is.
+      new_aops.push_back(curr_aop);
+    }
+  }
+
+  // Set the blobs for REPLACE/REPLACE_BZ operations that have been merged.
+  for (AnnotatedOperation& curr_aop : new_aops) {
+    if (curr_aop.op.data_length() == 0 &&
+        (curr_aop.op.type() ==
+            DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
+         curr_aop.op.type() ==
+            DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ)) {
+      TEST_AND_RETURN_FALSE(AddDataAndSetType(&curr_aop, target_part_path,
+                                              data_fd, data_file_size));
+    }
+  }
+
+  *aops = new_aops;
+  return true;
+}
+
+bool ABGenerator::AddDataAndSetType(AnnotatedOperation* aop,
+                                    const string& target_part_path,
+                                    int data_fd,
+                                    off_t* data_file_size) {
+  TEST_AND_RETURN_FALSE(
+      aop->op.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
+      aop->op.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+
+  chromeos::Blob data(aop->op.dst_length());
+  vector<Extent> dst_extents;
+  ExtentsToVector(aop->op.dst_extents(), &dst_extents);
+  TEST_AND_RETURN_FALSE(utils::ReadExtents(target_part_path,
+                                           dst_extents,
+                                           &data,
+                                           data.size(),
+                                           kBlockSize));
+
+  chromeos::Blob data_bz;
+  TEST_AND_RETURN_FALSE(BzipCompress(data, &data_bz));
+  CHECK(!data_bz.empty());
+
+  chromeos::Blob* data_p = nullptr;
+  DeltaArchiveManifest_InstallOperation_Type new_op_type;
+  if (data_bz.size() < data.size()) {
+    new_op_type = DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ;
+    data_p = &data_bz;
+  } else {
+    new_op_type = DeltaArchiveManifest_InstallOperation_Type_REPLACE;
+    data_p = &data;
+  }
+
+  // If the operation already points to a data blob, check whether it's
+  // identical to the new one, in which case don't add it.
+  if (aop->op.type() == new_op_type &&
+      aop->op.data_length() == data_p->size()) {
+    chromeos::Blob current_data(data_p->size());
+    ssize_t bytes_read;
+    TEST_AND_RETURN_FALSE(utils::PReadAll(data_fd,
+                                          current_data.data(),
+                                          aop->op.data_length(),
+                                          aop->op.data_offset(),
+                                          &bytes_read));
+    TEST_AND_RETURN_FALSE(bytes_read ==
+                          static_cast<ssize_t>(aop->op.data_length()));
+    if (current_data == *data_p)
+      data_p = nullptr;
+  }
+
+  if (data_p) {
+    aop->op.set_type(new_op_type);
+    aop->SetOperationBlob(data_p, data_fd, data_file_size);
+  }
+
+  return true;
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/ab_generator.h b/payload_generator/ab_generator.h
new file mode 100644
index 0000000..d027f22
--- /dev/null
+++ b/payload_generator/ab_generator.h
@@ -0,0 +1,120 @@
+// Copyright 2015 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.
+
+#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_AB_GENERATOR_H_
+#define UPDATE_ENGINE_PAYLOAD_GENERATOR_AB_GENERATOR_H_
+
+#include <string>
+#include <vector>
+
+#include <base/macros.h>
+#include <chromeos/secure_blob.h>
+
+#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/extent_utils.h"
+#include "update_engine/payload_generator/filesystem_interface.h"
+#include "update_engine/payload_generator/operations_generator.h"
+#include "update_engine/payload_generator/payload_generation_config.h"
+#include "update_engine/update_metadata.pb.h"
+
+namespace chromeos_update_engine {
+
+// The ABGenerator is an operations generator that generates payloads using the
+// A-to-B operations SOURCE_COPY and SOURCE_BSDIFF introduced in the payload
+// minor version 2 format.
+class ABGenerator : public OperationsGenerator {
+ public:
+  ABGenerator() = default;
+
+  // Generate the update payload operations for the kernel and rootfs using
+  // SOURCE_* operations, used for generating deltas for the minor version
+  // kSourceMinorPayloadVersion. This function will generate operations in the
+  // rootfs that will read blocks from the source partition in random order and
+  // write the new image on the target partition, also possibly in random order.
+  // The rootfs operations are stored in |rootfs_ops| and should be executed in
+  // that order. The kernel operations are stored in |kernel_ops|. All
+  // the offsets in the operations reference the data written to |data_file_fd|.
+  // The total amount of data written to that file is stored in
+  // |data_file_size|.
+  bool GenerateOperations(
+      const PayloadGenerationConfig& config,
+      int data_file_fd,
+      off_t* data_file_size,
+      std::vector<AnnotatedOperation>* rootfs_ops,
+      std::vector<AnnotatedOperation>* kernel_ops) override;
+
+  // Split the operations in the vector of AnnotatedOperations |aops|
+  // such that for every operation there is only one dst extent and updates
+  // |aops| with the new list of operations. All kinds of operations are
+  // fragmented except BSDIFF and SOURCE_BSDIFF operations.
+  // The |target_rootfs_part| is the filename of the new image, where the
+  // destination extents refer to. The blobs of the operations in |aops| should
+  // reference the file |data_fd| whose initial size is |*data_file_size|. The
+  // file contents and the value pointed by |data_file_size| are updated if
+  // needed.
+  static bool FragmentOperations(std::vector<AnnotatedOperation>* aops,
+                                 const std::string& target_rootfs_part,
+                                 int data_fd,
+                                 off_t* data_file_size);
+
+  // Takes a vector of AnnotatedOperations |aops| and sorts them by the first
+  // start block in their destination extents. Sets |aops| to a vector of the
+  // sorted operations.
+  static void SortOperationsByDestination(
+      std::vector<AnnotatedOperation>* aops);
+
+  // Takes an SOURCE_COPY install operation, |aop|, and adds one operation for
+  // each dst extent in |aop| to |ops|. The new operations added to |ops| will
+  // have only one dst extent. The src extents are split so the number of blocks
+  // in the src and dst extents are equal.
+  // E.g. we have a SOURCE_COPY operation:
+  //   src extents: [(1, 3), (5, 1), (7, 1)], dst extents: [(2, 2), (6, 3)]
+  // Then we will get 2 new operations:
+  //   1. src extents: [(1, 2)], dst extents: [(2, 2)]
+  //   2. src extents: [(3, 1),(5, 1),(7, 1)], dst extents: [(6, 3)]
+  static bool SplitSourceCopy(const AnnotatedOperation& original_aop,
+                              std::vector<AnnotatedOperation>* result_aops);
+
+  // Takes a REPLACE/REPLACE_BZ operation |aop|, and adds one operation for each
+  // dst extent in |aop| to |ops|. The new operations added to |ops| will have
+  // only one dst extent each, and may be either a REPLACE or REPLACE_BZ
+  // depending on whether compression is advantageous.
+  static bool SplitReplaceOrReplaceBz(
+      const AnnotatedOperation& original_aop,
+      std::vector<AnnotatedOperation>* result_aops,
+      const std::string& target_part,
+      int data_fd,
+      off_t* data_file_size);
+
+  // Takes a sorted (by first destination extent) vector of operations |aops|
+  // and merges SOURCE_COPY, REPLACE, and REPLACE_BZ operations in that vector.
+  // It will merge two operations if:
+  //   - They are of the same type.
+  //   - They are contiguous.
+  //   - Their combined blocks do not exceed |chunk_size|.
+  static bool MergeOperations(std::vector<AnnotatedOperation>* aops,
+                              off_t chunk_size,
+                              const std::string& target_part,
+                              int data_fd,
+                              off_t* data_file_size);
+
+ private:
+  // Adds the data payload for a REPLACE/REPLACE_BZ operation |aop| by reading
+  // its output extents from |target_part_path| and appending a corresponding
+  // data blob to |data_fd|. The blob will be compressed if this is smaller than
+  // the uncompressed form, and the operation type will be set accordingly.
+  // |*data_file_size| will be updated as well. If the operation happens to have
+  // the right type and already points to a data blob, we check whether its
+  // content is identical to the new one, in which case nothing is written.
+  static bool AddDataAndSetType(AnnotatedOperation* aop,
+                                const std::string& target_part_path,
+                                int data_fd,
+                                off_t* data_file_size);
+
+  DISALLOW_COPY_AND_ASSIGN(ABGenerator);
+};
+
+}  // namespace chromeos_update_engine
+
+#endif  // UPDATE_ENGINE_PAYLOAD_GENERATOR_AB_GENERATOR_H_
diff --git a/payload_generator/ab_generator_unittest.cc b/payload_generator/ab_generator_unittest.cc
new file mode 100644
index 0000000..9241701
--- /dev/null
+++ b/payload_generator/ab_generator_unittest.cc
@@ -0,0 +1,558 @@
+// Copyright 2015 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.
+
+#include "update_engine/payload_generator/ab_generator.h"
+
+#include <fcntl.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+
+#include <string>
+#include <vector>
+
+#include <gtest/gtest.h>
+
+#include "update_engine/bzip.h"
+#include "update_engine/payload_generator/annotated_operation.h"
+#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/extent_ranges.h"
+#include "update_engine/payload_generator/extent_utils.h"
+#include "update_engine/test_utils.h"
+#include "update_engine/utils.h"
+
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+
+bool ExtentEquals(Extent ext, uint64_t start_block, uint64_t num_blocks) {
+  return ext.start_block() == start_block && ext.num_blocks() == num_blocks;
+}
+
+// Tests splitting of a REPLACE/REPLACE_BZ operation.
+void TestSplitReplaceOrReplaceBzOperation(
+    DeltaArchiveManifest_InstallOperation_Type orig_type,
+    bool compressible) {
+  const size_t op_ex1_start_block = 2;
+  const size_t op_ex1_num_blocks = 2;
+  const size_t op_ex2_start_block = 6;
+  const size_t op_ex2_num_blocks = 1;
+  const size_t part_num_blocks = 7;
+
+  // Create the target partition data.
+  string part_path;
+  EXPECT_TRUE(utils::MakeTempFile(
+      "SplitReplaceOrReplaceBzTest_part.XXXXXX", &part_path, nullptr));
+  ScopedPathUnlinker part_path_unlinker(part_path);
+  const size_t part_size = part_num_blocks * kBlockSize;
+  chromeos::Blob part_data;
+  if (compressible) {
+    part_data.resize(part_size);
+    test_utils::FillWithData(&part_data);
+  } else {
+    std::mt19937 gen(12345);
+    std::uniform_int_distribution<uint8_t> dis(0, 255);
+    for (uint32_t i = 0; i < part_size; i++)
+      part_data.push_back(dis(gen));
+  }
+  ASSERT_EQ(part_size, part_data.size());
+  ASSERT_TRUE(utils::WriteFile(part_path.c_str(), part_data.data(), part_size));
+
+  // Create original operation and blob data.
+  const size_t op_ex1_offset = op_ex1_start_block * kBlockSize;
+  const size_t op_ex1_size = op_ex1_num_blocks * kBlockSize;
+  const size_t op_ex2_offset = op_ex2_start_block * kBlockSize;
+  const size_t op_ex2_size = op_ex2_num_blocks * kBlockSize;
+  DeltaArchiveManifest_InstallOperation op;
+  op.set_type(orig_type);
+  *(op.add_dst_extents()) = ExtentForRange(op_ex1_start_block,
+                                           op_ex1_num_blocks);
+  *(op.add_dst_extents()) = ExtentForRange(op_ex2_start_block,
+                                           op_ex2_num_blocks);
+  op.set_dst_length(op_ex1_num_blocks + op_ex2_num_blocks);
+
+  chromeos::Blob op_data;
+  op_data.insert(op_data.end(),
+                 part_data.begin() + op_ex1_offset,
+                 part_data.begin() + op_ex1_offset + op_ex1_size);
+  op_data.insert(op_data.end(),
+                 part_data.begin() + op_ex2_offset,
+                 part_data.begin() + op_ex2_offset + op_ex2_size);
+  chromeos::Blob op_blob;
+  if (orig_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE) {
+    op_blob = op_data;
+  } else {
+    ASSERT_TRUE(BzipCompress(op_data, &op_blob));
+  }
+  op.set_data_offset(0);
+  op.set_data_length(op_blob.size());
+
+  AnnotatedOperation aop;
+  aop.op = op;
+  aop.name = "SplitTestOp";
+
+  // Create the data file.
+  string data_path;
+  EXPECT_TRUE(utils::MakeTempFile(
+      "SplitReplaceOrReplaceBzTest_data.XXXXXX", &data_path, nullptr));
+  ScopedPathUnlinker data_path_unlinker(data_path);
+  int data_fd = open(data_path.c_str(), O_RDWR, 000);
+  EXPECT_GE(data_fd, 0);
+  ScopedFdCloser data_fd_closer(&data_fd);
+  EXPECT_TRUE(utils::WriteFile(data_path.c_str(), op_blob.data(),
+                               op_blob.size()));
+  off_t data_file_size = op_blob.size();
+
+  // Split the operation.
+  vector<AnnotatedOperation> result_ops;
+  ASSERT_TRUE(ABGenerator::SplitReplaceOrReplaceBz(
+          aop, &result_ops, part_path, data_fd, &data_file_size));
+
+  // Check the result.
+  DeltaArchiveManifest_InstallOperation_Type expected_type =
+      compressible ?
+      DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ :
+      DeltaArchiveManifest_InstallOperation_Type_REPLACE;
+
+  ASSERT_EQ(2, result_ops.size());
+
+  EXPECT_EQ("SplitTestOp:0", result_ops[0].name);
+  DeltaArchiveManifest_InstallOperation first_op = result_ops[0].op;
+  EXPECT_EQ(expected_type, first_op.type());
+  EXPECT_EQ(op_ex1_size, first_op.dst_length());
+  EXPECT_EQ(1, first_op.dst_extents().size());
+  EXPECT_TRUE(ExtentEquals(first_op.dst_extents(0), op_ex1_start_block,
+                           op_ex1_num_blocks));
+  // Obtain the expected blob.
+  chromeos::Blob first_expected_data(
+      part_data.begin() + op_ex1_offset,
+      part_data.begin() + op_ex1_offset + op_ex1_size);
+  chromeos::Blob first_expected_blob;
+  if (compressible) {
+    ASSERT_TRUE(BzipCompress(first_expected_data, &first_expected_blob));
+  } else {
+    first_expected_blob = first_expected_data;
+  }
+  EXPECT_EQ(first_expected_blob.size(), first_op.data_length());
+  // Check that the actual blob matches what's expected.
+  chromeos::Blob first_data_blob(first_op.data_length());
+  ssize_t bytes_read;
+  ASSERT_TRUE(utils::PReadAll(data_fd,
+                              first_data_blob.data(),
+                              first_op.data_length(),
+                              first_op.data_offset(),
+                              &bytes_read));
+  ASSERT_EQ(bytes_read, first_op.data_length());
+  EXPECT_EQ(first_expected_blob, first_data_blob);
+
+  EXPECT_EQ("SplitTestOp:1", result_ops[1].name);
+  DeltaArchiveManifest_InstallOperation second_op = result_ops[1].op;
+  EXPECT_EQ(expected_type, second_op.type());
+  EXPECT_EQ(op_ex2_size, second_op.dst_length());
+  EXPECT_EQ(1, second_op.dst_extents().size());
+  EXPECT_TRUE(ExtentEquals(second_op.dst_extents(0), op_ex2_start_block,
+                           op_ex2_num_blocks));
+  // Obtain the expected blob.
+  chromeos::Blob second_expected_data(
+      part_data.begin() + op_ex2_offset,
+      part_data.begin() + op_ex2_offset + op_ex2_size);
+  chromeos::Blob second_expected_blob;
+  if (compressible) {
+    ASSERT_TRUE(BzipCompress(second_expected_data, &second_expected_blob));
+  } else {
+    second_expected_blob = second_expected_data;
+  }
+  EXPECT_EQ(second_expected_blob.size(), second_op.data_length());
+  // Check that the actual blob matches what's expected.
+  chromeos::Blob second_data_blob(second_op.data_length());
+  ASSERT_TRUE(utils::PReadAll(data_fd,
+                              second_data_blob.data(),
+                              second_op.data_length(),
+                              second_op.data_offset(),
+                              &bytes_read));
+  ASSERT_EQ(bytes_read, second_op.data_length());
+  EXPECT_EQ(second_expected_blob, second_data_blob);
+
+  // Check relative layout of data blobs.
+  EXPECT_EQ(first_op.data_offset() + first_op.data_length(),
+            second_op.data_offset());
+  EXPECT_EQ(second_op.data_offset() + second_op.data_length(), data_file_size);
+  // If we split a REPLACE into multiple ones, ensure reuse of preexisting blob.
+  if (!compressible &&
+      orig_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE) {
+    EXPECT_EQ(0, first_op.data_offset());
+  }
+}
+
+// Tests merging of REPLACE/REPLACE_BZ operations.
+void TestMergeReplaceOrReplaceBzOperations(
+    DeltaArchiveManifest_InstallOperation_Type orig_type,
+    bool compressible) {
+  const size_t first_op_num_blocks = 1;
+  const size_t second_op_num_blocks = 2;
+  const size_t total_op_num_blocks = first_op_num_blocks + second_op_num_blocks;
+  const size_t part_num_blocks = total_op_num_blocks + 2;
+
+  // Create the target partition data.
+  string part_path;
+  EXPECT_TRUE(utils::MakeTempFile(
+      "MergeReplaceOrReplaceBzTest_part.XXXXXX", &part_path, nullptr));
+  ScopedPathUnlinker part_path_unlinker(part_path);
+  const size_t part_size = part_num_blocks * kBlockSize;
+  chromeos::Blob part_data;
+  if (compressible) {
+    part_data.resize(part_size);
+    test_utils::FillWithData(&part_data);
+  } else {
+    std::mt19937 gen(12345);
+    std::uniform_int_distribution<uint8_t> dis(0, 255);
+    for (uint32_t i = 0; i < part_size; i++)
+      part_data.push_back(dis(gen));
+  }
+  ASSERT_EQ(part_size, part_data.size());
+  ASSERT_TRUE(utils::WriteFile(part_path.c_str(), part_data.data(), part_size));
+
+  // Create original operations and blob data.
+  vector<AnnotatedOperation> aops;
+  chromeos::Blob blob_data;
+  const size_t total_op_size = total_op_num_blocks * kBlockSize;
+
+  DeltaArchiveManifest_InstallOperation first_op;
+  first_op.set_type(orig_type);
+  const size_t first_op_size = first_op_num_blocks * kBlockSize;
+  first_op.set_dst_length(first_op_size);
+  *(first_op.add_dst_extents()) = ExtentForRange(0, first_op_num_blocks);
+  chromeos::Blob first_op_data(part_data.begin(),
+                               part_data.begin() + first_op_size);
+  chromeos::Blob first_op_blob;
+  if (orig_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE) {
+    first_op_blob = first_op_data;
+  } else {
+    ASSERT_TRUE(BzipCompress(first_op_data, &first_op_blob));
+  }
+  first_op.set_data_offset(0);
+  first_op.set_data_length(first_op_blob.size());
+  blob_data.insert(blob_data.end(), first_op_blob.begin(), first_op_blob.end());
+  AnnotatedOperation first_aop;
+  first_aop.op = first_op;
+  first_aop.name = "first";
+  aops.push_back(first_aop);
+
+  DeltaArchiveManifest_InstallOperation second_op;
+  second_op.set_type(orig_type);
+  const size_t second_op_size = second_op_num_blocks * kBlockSize;
+  second_op.set_dst_length(second_op_size);
+  *(second_op.add_dst_extents()) = ExtentForRange(first_op_num_blocks,
+                                                  second_op_num_blocks);
+  chromeos::Blob second_op_data(part_data.begin() + first_op_size,
+                                part_data.begin() + total_op_size);
+  chromeos::Blob second_op_blob;
+  if (orig_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE) {
+    second_op_blob = second_op_data;
+  } else {
+    ASSERT_TRUE(BzipCompress(second_op_data, &second_op_blob));
+  }
+  second_op.set_data_offset(first_op_blob.size());
+  second_op.set_data_length(second_op_blob.size());
+  blob_data.insert(blob_data.end(), second_op_blob.begin(),
+                   second_op_blob.end());
+  AnnotatedOperation second_aop;
+  second_aop.op = second_op;
+  second_aop.name = "second";
+  aops.push_back(second_aop);
+
+  // Create the data file.
+  string data_path;
+  EXPECT_TRUE(utils::MakeTempFile(
+      "MergeReplaceOrReplaceBzTest_data.XXXXXX", &data_path, nullptr));
+  ScopedPathUnlinker data_path_unlinker(data_path);
+  int data_fd = open(data_path.c_str(), O_RDWR, 000);
+  EXPECT_GE(data_fd, 0);
+  ScopedFdCloser data_fd_closer(&data_fd);
+  EXPECT_TRUE(utils::WriteFile(data_path.c_str(), blob_data.data(),
+                               blob_data.size()));
+  off_t data_file_size = blob_data.size();
+
+  // Merge the operations.
+  EXPECT_TRUE(ABGenerator::MergeOperations(
+      &aops, 5 * kBlockSize, part_path, data_fd, &data_file_size));
+
+  // Check the result.
+  DeltaArchiveManifest_InstallOperation_Type expected_op_type =
+      compressible ?
+      DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ :
+      DeltaArchiveManifest_InstallOperation_Type_REPLACE;
+  EXPECT_EQ(1, aops.size());
+  DeltaArchiveManifest_InstallOperation new_op = aops[0].op;
+  EXPECT_EQ(expected_op_type, new_op.type());
+  EXPECT_FALSE(new_op.has_src_length());
+  EXPECT_EQ(total_op_num_blocks * kBlockSize, new_op.dst_length());
+  EXPECT_EQ(1, new_op.dst_extents().size());
+  EXPECT_TRUE(ExtentEquals(new_op.dst_extents(0), 0, total_op_num_blocks));
+  EXPECT_EQ("first,second", aops[0].name);
+
+  // Check to see if the blob pointed to in the new extent has what we expect.
+  chromeos::Blob expected_data(part_data.begin(),
+                               part_data.begin() + total_op_size);
+  chromeos::Blob expected_blob;
+  if (compressible) {
+    ASSERT_TRUE(BzipCompress(expected_data, &expected_blob));
+  } else {
+    expected_blob = expected_data;
+  }
+  ASSERT_EQ(expected_blob.size(), new_op.data_length());
+  ASSERT_EQ(blob_data.size() + expected_blob.size(), data_file_size);
+  chromeos::Blob new_op_blob(new_op.data_length());
+  ssize_t bytes_read;
+  ASSERT_TRUE(utils::PReadAll(data_fd,
+                              new_op_blob.data(),
+                              new_op.data_length(),
+                              new_op.data_offset(),
+                              &bytes_read));
+  ASSERT_EQ(new_op.data_length(), bytes_read);
+  EXPECT_EQ(expected_blob, new_op_blob);
+}
+
+}  // namespace
+
+class ABGeneratorTest : public ::testing::Test {};
+
+TEST_F(ABGeneratorTest, SplitSourceCopyTest) {
+  DeltaArchiveManifest_InstallOperation op;
+  op.set_type(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
+  *(op.add_src_extents()) = ExtentForRange(2, 3);
+  *(op.add_src_extents()) = ExtentForRange(6, 1);
+  *(op.add_src_extents()) = ExtentForRange(8, 4);
+  *(op.add_dst_extents()) = ExtentForRange(10, 2);
+  *(op.add_dst_extents()) = ExtentForRange(14, 3);
+  *(op.add_dst_extents()) = ExtentForRange(18, 3);
+
+  AnnotatedOperation aop;
+  aop.op = op;
+  aop.name = "SplitSourceCopyTestOp";
+  vector<AnnotatedOperation> result_ops;
+  EXPECT_TRUE(ABGenerator::SplitSourceCopy(aop, &result_ops));
+  EXPECT_EQ(result_ops.size(), 3);
+
+  EXPECT_EQ("SplitSourceCopyTestOp:0", result_ops[0].name);
+  DeltaArchiveManifest_InstallOperation first_op = result_ops[0].op;
+  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY,
+            first_op.type());
+  EXPECT_EQ(kBlockSize * 2, first_op.src_length());
+  EXPECT_EQ(1, first_op.src_extents().size());
+  EXPECT_EQ(2, first_op.src_extents(0).start_block());
+  EXPECT_EQ(2, first_op.src_extents(0).num_blocks());
+  EXPECT_EQ(kBlockSize * 2, first_op.dst_length());
+  EXPECT_EQ(1, first_op.dst_extents().size());
+  EXPECT_EQ(10, first_op.dst_extents(0).start_block());
+  EXPECT_EQ(2, first_op.dst_extents(0).num_blocks());
+
+  EXPECT_EQ("SplitSourceCopyTestOp:1", result_ops[1].name);
+  DeltaArchiveManifest_InstallOperation second_op = result_ops[1].op;
+  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY,
+            second_op.type());
+  EXPECT_EQ(kBlockSize * 3, second_op.src_length());
+  EXPECT_EQ(3, second_op.src_extents().size());
+  EXPECT_EQ(4, second_op.src_extents(0).start_block());
+  EXPECT_EQ(1, second_op.src_extents(0).num_blocks());
+  EXPECT_EQ(6, second_op.src_extents(1).start_block());
+  EXPECT_EQ(1, second_op.src_extents(1).num_blocks());
+  EXPECT_EQ(8, second_op.src_extents(2).start_block());
+  EXPECT_EQ(1, second_op.src_extents(2).num_blocks());
+  EXPECT_EQ(kBlockSize * 3, second_op.dst_length());
+  EXPECT_EQ(1, second_op.dst_extents().size());
+  EXPECT_EQ(14, second_op.dst_extents(0).start_block());
+  EXPECT_EQ(3, second_op.dst_extents(0).num_blocks());
+
+  EXPECT_EQ("SplitSourceCopyTestOp:2", result_ops[2].name);
+  DeltaArchiveManifest_InstallOperation third_op = result_ops[2].op;
+  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY,
+            third_op.type());
+  EXPECT_EQ(kBlockSize * 3, third_op.src_length());
+  EXPECT_EQ(1, third_op.src_extents().size());
+  EXPECT_EQ(9, third_op.src_extents(0).start_block());
+  EXPECT_EQ(3, third_op.src_extents(0).num_blocks());
+  EXPECT_EQ(kBlockSize * 3, third_op.dst_length());
+  EXPECT_EQ(1, third_op.dst_extents().size());
+  EXPECT_EQ(18, third_op.dst_extents(0).start_block());
+  EXPECT_EQ(3, third_op.dst_extents(0).num_blocks());
+}
+
+TEST_F(ABGeneratorTest, SplitReplaceTest) {
+  TestSplitReplaceOrReplaceBzOperation(
+      DeltaArchiveManifest_InstallOperation_Type_REPLACE, false);
+}
+
+TEST_F(ABGeneratorTest, SplitReplaceIntoReplaceBzTest) {
+  TestSplitReplaceOrReplaceBzOperation(
+      DeltaArchiveManifest_InstallOperation_Type_REPLACE, true);
+}
+
+TEST_F(ABGeneratorTest, SplitReplaceBzTest) {
+  TestSplitReplaceOrReplaceBzOperation(
+      DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ, true);
+}
+
+TEST_F(ABGeneratorTest, SplitReplaceBzIntoReplaceTest) {
+  TestSplitReplaceOrReplaceBzOperation(
+      DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ, false);
+}
+
+TEST_F(ABGeneratorTest, SortOperationsByDestinationTest) {
+  vector<AnnotatedOperation> aops;
+  // One operation with multiple destination extents.
+  DeltaArchiveManifest_InstallOperation first_op;
+  *(first_op.add_dst_extents()) = ExtentForRange(6, 1);
+  *(first_op.add_dst_extents()) = ExtentForRange(10, 2);
+  AnnotatedOperation first_aop;
+  first_aop.op = first_op;
+  first_aop.name = "first";
+  aops.push_back(first_aop);
+
+  // One with no destination extent. Should end up at the end of the vector.
+  DeltaArchiveManifest_InstallOperation second_op;
+  AnnotatedOperation second_aop;
+  second_aop.op = second_op;
+  second_aop.name = "second";
+  aops.push_back(second_aop);
+
+  // One with one destination extent.
+  DeltaArchiveManifest_InstallOperation third_op;
+  *(third_op.add_dst_extents()) = ExtentForRange(3, 2);
+  AnnotatedOperation third_aop;
+  third_aop.op = third_op;
+  third_aop.name = "third";
+  aops.push_back(third_aop);
+
+  ABGenerator::SortOperationsByDestination(&aops);
+  EXPECT_EQ(aops.size(), 3);
+  EXPECT_EQ(third_aop.name, aops[0].name);
+  EXPECT_EQ(first_aop.name, aops[1].name);
+  EXPECT_EQ(second_aop.name, aops[2].name);
+}
+
+TEST_F(ABGeneratorTest, MergeSourceCopyOperationsTest) {
+  vector<AnnotatedOperation> aops;
+  DeltaArchiveManifest_InstallOperation first_op;
+  first_op.set_type(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
+  first_op.set_src_length(kBlockSize);
+  first_op.set_dst_length(kBlockSize);
+  *(first_op.add_src_extents()) = ExtentForRange(1, 1);
+  *(first_op.add_dst_extents()) = ExtentForRange(6, 1);
+  AnnotatedOperation first_aop;
+  first_aop.op = first_op;
+  first_aop.name = "1";
+  aops.push_back(first_aop);
+
+  DeltaArchiveManifest_InstallOperation second_op;
+  second_op.set_type(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
+  second_op.set_src_length(3 * kBlockSize);
+  second_op.set_dst_length(3 * kBlockSize);
+  *(second_op.add_src_extents()) = ExtentForRange(2, 2);
+  *(second_op.add_src_extents()) = ExtentForRange(8, 2);
+  *(second_op.add_dst_extents()) = ExtentForRange(7, 3);
+  *(second_op.add_dst_extents()) = ExtentForRange(11, 1);
+  AnnotatedOperation second_aop;
+  second_aop.op = second_op;
+  second_aop.name = "2";
+  aops.push_back(second_aop);
+
+  DeltaArchiveManifest_InstallOperation third_op;
+  third_op.set_type(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
+  third_op.set_src_length(kBlockSize);
+  third_op.set_dst_length(kBlockSize);
+  *(third_op.add_src_extents()) = ExtentForRange(11, 1);
+  *(third_op.add_dst_extents()) = ExtentForRange(12, 1);
+  AnnotatedOperation third_aop;
+  third_aop.op = third_op;
+  third_aop.name = "3";
+  aops.push_back(third_aop);
+
+  EXPECT_TRUE(ABGenerator::MergeOperations(&aops, 5 * kBlockSize,
+                                           "", 0, nullptr));
+
+  EXPECT_EQ(aops.size(), 1);
+  DeltaArchiveManifest_InstallOperation first_result_op = aops[0].op;
+  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY,
+            first_result_op.type());
+  EXPECT_EQ(kBlockSize * 5, first_result_op.src_length());
+  EXPECT_EQ(3, first_result_op.src_extents().size());
+  EXPECT_TRUE(ExtentEquals(first_result_op.src_extents(0), 1, 3));
+  EXPECT_TRUE(ExtentEquals(first_result_op.src_extents(1), 8, 2));
+  EXPECT_TRUE(ExtentEquals(first_result_op.src_extents(2), 11, 1));
+  EXPECT_EQ(kBlockSize * 5, first_result_op.dst_length());
+  EXPECT_EQ(2, first_result_op.dst_extents().size());
+  EXPECT_TRUE(ExtentEquals(first_result_op.dst_extents(0), 6, 4));
+  EXPECT_TRUE(ExtentEquals(first_result_op.dst_extents(1), 11, 2));
+  EXPECT_EQ(aops[0].name, "1,2,3");
+}
+
+TEST_F(ABGeneratorTest, MergeReplaceOperationsTest) {
+  TestMergeReplaceOrReplaceBzOperations(
+      DeltaArchiveManifest_InstallOperation_Type_REPLACE, false);
+}
+
+TEST_F(ABGeneratorTest, MergeReplaceOperationsToReplaceBzTest) {
+  TestMergeReplaceOrReplaceBzOperations(
+      DeltaArchiveManifest_InstallOperation_Type_REPLACE, true);
+}
+
+TEST_F(ABGeneratorTest, MergeReplaceBzOperationsTest) {
+  TestMergeReplaceOrReplaceBzOperations(
+      DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ, true);
+}
+
+TEST_F(ABGeneratorTest, MergeReplaceBzOperationsToReplaceTest) {
+  TestMergeReplaceOrReplaceBzOperations(
+      DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ, false);
+}
+
+TEST_F(ABGeneratorTest, NoMergeOperationsTest) {
+  // Test to make sure we don't merge operations that shouldn't be merged.
+  vector<AnnotatedOperation> aops;
+  DeltaArchiveManifest_InstallOperation first_op;
+  first_op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+  *(first_op.add_dst_extents()) = ExtentForRange(0, 1);
+  first_op.set_data_length(kBlockSize);
+  AnnotatedOperation first_aop;
+  first_aop.op = first_op;
+  aops.push_back(first_aop);
+
+  // Should merge with first, except op types don't match...
+  DeltaArchiveManifest_InstallOperation second_op;
+  second_op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+  *(second_op.add_dst_extents()) = ExtentForRange(1, 2);
+  second_op.set_data_length(2 * kBlockSize);
+  AnnotatedOperation second_aop;
+  second_aop.op = second_op;
+  aops.push_back(second_aop);
+
+  // Should merge with second, except it would exceed chunk size...
+  DeltaArchiveManifest_InstallOperation third_op;
+  third_op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+  *(third_op.add_dst_extents()) = ExtentForRange(3, 3);
+  third_op.set_data_length(3 * kBlockSize);
+  AnnotatedOperation third_aop;
+  third_aop.op = third_op;
+  aops.push_back(third_aop);
+
+  // Should merge with third, except they aren't contiguous...
+  DeltaArchiveManifest_InstallOperation fourth_op;
+  fourth_op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+  *(fourth_op.add_dst_extents()) = ExtentForRange(7, 2);
+  fourth_op.set_data_length(2 * kBlockSize);
+  AnnotatedOperation fourth_aop;
+  fourth_aop.op = fourth_op;
+  aops.push_back(fourth_aop);
+
+  EXPECT_TRUE(ABGenerator::MergeOperations(
+      &aops, 4 * kBlockSize, "", 0, nullptr));
+
+  // No operations were merged, the number of ops is the same.
+  EXPECT_EQ(aops.size(), 4);
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/delta_diff_generator.cc b/payload_generator/delta_diff_generator.cc
index 61ac4ad..bedfbbb 100644
--- a/payload_generator/delta_diff_generator.cc
+++ b/payload_generator/delta_diff_generator.cc
@@ -11,830 +11,31 @@
 #include <sys/types.h>
 
 #include <algorithm>
-#include <map>
 #include <memory>
 #include <string>
 #include <utility>
 #include <vector>
 
-#include <base/files/file_path.h>
-#include <base/files/file_util.h>
 #include <base/logging.h>
-#include <base/strings/stringprintf.h>
-#include <base/strings/string_util.h>
-#include <bzlib.h>
-#include <chromeos/secure_blob.h>
 
-#include "update_engine/bzip.h"
 #include "update_engine/delta_performer.h"
-#include "update_engine/file_writer.h"
-#include "update_engine/omaha_hash_calculator.h"
 #include "update_engine/payload_constants.h"
-#include "update_engine/payload_generator/ext2_filesystem.h"
-#include "update_engine/payload_generator/extent_ranges.h"
+#include "update_engine/payload_generator/ab_generator.h"
+#include "update_engine/payload_generator/delta_diff_utils.h"
 #include "update_engine/payload_generator/full_update_generator.h"
 #include "update_engine/payload_generator/inplace_generator.h"
-#include "update_engine/payload_generator/payload_signer.h"
-#include "update_engine/payload_generator/raw_filesystem.h"
-#include "update_engine/payload_verifier.h"
-#include "update_engine/subprocess.h"
-#include "update_engine/update_metadata.pb.h"
+#include "update_engine/payload_generator/payload_file.h"
 #include "update_engine/utils.h"
 
-using std::map;
-using std::set;
-using std::sort;
 using std::string;
 using std::unique_ptr;
 using std::vector;
 
-namespace {
-
-const uint64_t kMajorVersionNumber = 1;
-
-// The maximum destination size allowed for bsdiff. In general, bsdiff should
-// work for arbitrary big files, but the payload generation and payload
-// application requires a significant amount of RAM. We put a hard-limit of
-// 200 MiB that should not affect any released board, but will limit the
-// Chrome binary in ASan builders.
-const uint64_t kMaxBsdiffDestinationSize = 200 * 1024 * 1024;  // bytes
-
-static const char* kInstallOperationTypes[] = {
-  "REPLACE",
-  "REPLACE_BZ",
-  "MOVE",
-  "BSDIFF",
-  "SOURCE_COPY",
-  "SOURCE_BSDIFF"
-};
-
-}  // namespace
-
 namespace chromeos_update_engine {
 
-typedef map<const DeltaArchiveManifest_InstallOperation*,
-            string> OperationNameMap;
-
 // bytes
 const size_t kRootFSPartitionSize = static_cast<size_t>(2) * 1024 * 1024 * 1024;
 const size_t kBlockSize = 4096;  // bytes
-const char* const kEmptyPath = "";
-const char* const kBsdiffPath = "bsdiff";
-
-namespace {
-
-// Writes the uint64_t passed in in host-endian to the file as big-endian.
-// Returns true on success.
-bool WriteUint64AsBigEndian(FileWriter* writer, const uint64_t value) {
-  uint64_t value_be = htobe64(value);
-  TEST_AND_RETURN_FALSE(writer->Write(&value_be, sizeof(value_be)));
-  return true;
-}
-
-// Adds each operation from |rootfs_ops| and |kernel_ops| to |out_manifest| in
-// the order they come in those vectors. reports the operations names
-void InstallOperationsToManifest(
-    const vector<AnnotatedOperation>& rootfs_ops,
-    const vector<AnnotatedOperation>& kernel_ops,
-    DeltaArchiveManifest* out_manifest,
-    OperationNameMap* out_op_name_map) {
-  for (const AnnotatedOperation& aop : rootfs_ops) {
-    if (DeltaDiffGenerator::IsNoopOperation(aop.op))
-      continue;
-    DeltaArchiveManifest_InstallOperation* new_op =
-        out_manifest->add_install_operations();
-    (*out_op_name_map)[new_op] = aop.name;
-    *new_op = aop.op;
-  }
-  for (const AnnotatedOperation& aop : kernel_ops) {
-    if (DeltaDiffGenerator::IsNoopOperation(aop.op))
-      continue;
-    DeltaArchiveManifest_InstallOperation* new_op =
-        out_manifest->add_kernel_install_operations();
-    (*out_op_name_map)[new_op] = aop.name;
-    *new_op = aop.op;
-  }
-}
-
-struct DeltaObject {
-  DeltaObject(const string& in_name, const int in_type, const off_t in_size)
-      : name(in_name),
-        type(in_type),
-        size(in_size) {}
-  bool operator <(const DeltaObject& object) const {
-    return (size != object.size) ? (size < object.size) : (name < object.name);
-  }
-  string name;
-  int type;
-  off_t size;
-};
-
-void ReportPayloadUsage(const DeltaArchiveManifest& manifest,
-                        const int64_t manifest_metadata_size,
-                        const OperationNameMap& op_name_map) {
-  vector<DeltaObject> objects;
-  off_t total_size = 0;
-
-  // Rootfs install operations.
-  for (int i = 0; i < manifest.install_operations_size(); ++i) {
-    const DeltaArchiveManifest_InstallOperation& op =
-        manifest.install_operations(i);
-    objects.push_back(DeltaObject(op_name_map.find(&op)->second,
-                                  op.type(),
-                                  op.data_length()));
-    total_size += op.data_length();
-  }
-
-  // Kernel install operations.
-  for (int i = 0; i < manifest.kernel_install_operations_size(); ++i) {
-    const DeltaArchiveManifest_InstallOperation& op =
-        manifest.kernel_install_operations(i);
-    objects.push_back(DeltaObject(base::StringPrintf("<kernel-operation-%d>",
-                                                     i),
-                                  op.type(),
-                                  op.data_length()));
-    total_size += op.data_length();
-  }
-
-  objects.push_back(DeltaObject("<manifest-metadata>",
-                                -1,
-                                manifest_metadata_size));
-  total_size += manifest_metadata_size;
-
-  sort(objects.begin(), objects.end());
-
-  static const char kFormatString[] = "%6.2f%% %10jd %-10s %s\n";
-  for (const DeltaObject& object : objects) {
-    fprintf(stderr, kFormatString,
-            object.size * 100.0 / total_size,
-            static_cast<intmax_t>(object.size),
-            object.type >= 0 ? kInstallOperationTypes[object.type] : "-",
-            object.name.c_str());
-  }
-  fprintf(stderr, kFormatString,
-          100.0, static_cast<intmax_t>(total_size), "", "<total>");
-}
-
-// Process a range of blocks from |range_start| to |range_end| in the extent at
-// position |*idx_p| of |extents|. If |do_remove| is true, this range will be
-// removed, which may cause the extent to be trimmed, split or removed entirely.
-// The value of |*idx_p| is updated to point to the next extent to be processed.
-// Returns true iff the next extent to process is a new or updated one.
-bool ProcessExtentBlockRange(vector<Extent>* extents, size_t* idx_p,
-                             const bool do_remove, uint64_t range_start,
-                             uint64_t range_end) {
-  size_t idx = *idx_p;
-  uint64_t start_block = (*extents)[idx].start_block();
-  uint64_t num_blocks = (*extents)[idx].num_blocks();
-  uint64_t range_size = range_end - range_start;
-
-  if (do_remove) {
-    if (range_size == num_blocks) {
-      // Remove the entire extent.
-      extents->erase(extents->begin() + idx);
-    } else if (range_end == num_blocks) {
-      // Trim the end of the extent.
-      (*extents)[idx].set_num_blocks(num_blocks - range_size);
-      idx++;
-    } else if (range_start == 0) {
-      // Trim the head of the extent.
-      (*extents)[idx].set_start_block(start_block + range_size);
-      (*extents)[idx].set_num_blocks(num_blocks - range_size);
-    } else {
-      // Trim the middle, splitting the remainder into two parts.
-      (*extents)[idx].set_num_blocks(range_start);
-      Extent e;
-      e.set_start_block(start_block + range_end);
-      e.set_num_blocks(num_blocks - range_end);
-      idx++;
-      extents->insert(extents->begin() + idx, e);
-    }
-  } else if (range_end == num_blocks) {
-    // Done with this extent.
-    idx++;
-  } else {
-    return false;
-  }
-
-  *idx_p = idx;
-  return true;
-}
-
-// Remove identical corresponding block ranges in |src_extents| and
-// |dst_extents|. Used for preventing moving of blocks onto themselves during
-// MOVE operations. The value of |total_bytes| indicates the actual length of
-// content; this may be slightly less than the total size of blocks, in which
-// case the last block is only partly occupied with data. Returns the total
-// number of bytes removed.
-size_t RemoveIdenticalBlockRanges(vector<Extent>* src_extents,
-                                  vector<Extent>* dst_extents,
-                                  const size_t total_bytes) {
-  size_t src_idx = 0;
-  size_t dst_idx = 0;
-  uint64_t src_offset = 0, dst_offset = 0;
-  bool new_src = true, new_dst = true;
-  size_t removed_bytes = 0, nonfull_block_bytes;
-  bool do_remove = false;
-  while (src_idx < src_extents->size() && dst_idx < dst_extents->size()) {
-    if (new_src) {
-      src_offset = 0;
-      new_src = false;
-    }
-    if (new_dst) {
-      dst_offset = 0;
-      new_dst = false;
-    }
-
-    do_remove = ((*src_extents)[src_idx].start_block() + src_offset ==
-                 (*dst_extents)[dst_idx].start_block() + dst_offset);
-
-    uint64_t src_num_blocks = (*src_extents)[src_idx].num_blocks();
-    uint64_t dst_num_blocks = (*dst_extents)[dst_idx].num_blocks();
-    uint64_t min_num_blocks = std::min(src_num_blocks - src_offset,
-                                       dst_num_blocks - dst_offset);
-    uint64_t prev_src_offset = src_offset;
-    uint64_t prev_dst_offset = dst_offset;
-    src_offset += min_num_blocks;
-    dst_offset += min_num_blocks;
-
-    new_src = ProcessExtentBlockRange(src_extents, &src_idx, do_remove,
-                                      prev_src_offset, src_offset);
-    new_dst = ProcessExtentBlockRange(dst_extents, &dst_idx, do_remove,
-                                      prev_dst_offset, dst_offset);
-    if (do_remove)
-      removed_bytes += min_num_blocks * kBlockSize;
-  }
-
-  // If we removed the last block and this block is only partly used by file
-  // content, deduct the unused portion from the total removed byte count.
-  if (do_remove && (nonfull_block_bytes = total_bytes % kBlockSize))
-    removed_bytes -= kBlockSize - nonfull_block_bytes;
-
-  return removed_bytes;
-}
-
-// Compare two AnnotatedOperations by the start block of the first Extent in
-// their destination extents.
-bool CompareAopsByDestination(AnnotatedOperation first_aop,
-                              AnnotatedOperation second_aop) {
-  // We want empty operations to be at the end of the payload.
-  if (!first_aop.op.dst_extents().size() || !second_aop.op.dst_extents().size())
-    return ((!first_aop.op.dst_extents().size()) <
-            (!second_aop.op.dst_extents().size()));
-  uint32_t first_dst_start = first_aop.op.dst_extents(0).start_block();
-  uint32_t second_dst_start = second_aop.op.dst_extents(0).start_block();
-  return first_dst_start < second_dst_start;
-}
-
-}  // namespace
-
-bool DeltaDiffGenerator::DeltaReadFilesystem(
-    vector<AnnotatedOperation>* aops,
-    const string& old_part,
-    const string& new_part,
-    FilesystemInterface* old_fs,
-    FilesystemInterface* new_fs,
-    off_t chunk_blocks,
-    int data_fd,
-    off_t* data_file_size,
-    bool skip_block_0,
-    bool src_ops_allowed) {
-  ExtentRanges old_visited_blocks;
-  ExtentRanges new_visited_blocks;
-
-  // We can't produce a MOVE operation with a 0 block as neither source nor
-  // destination, so we avoid generating an operation for the block 0 here, and
-  // we will add an operation for it in the InplaceGenerator. Excluding both
-  // old and new blocks ensures that identical images would still produce empty
-  // deltas.
-  if (skip_block_0) {
-    old_visited_blocks.AddBlock(0);
-    new_visited_blocks.AddBlock(0);
-  }
-
-  map<string, vector<Extent>> old_files_map;
-  if (old_fs) {
-    vector<FilesystemInterface::File> old_files;
-    old_fs->GetFiles(&old_files);
-    for (const FilesystemInterface::File& file : old_files)
-      old_files_map[file.name] = file.extents;
-  }
-
-  vector<FilesystemInterface::File> new_files;
-  new_fs->GetFiles(&new_files);
-
-  // The processing is very straightforward here, we generate operations for
-  // every file (and pseudo-file such as the metadata) in the new filesystem
-  // based on the file with the same name in the old filesystem, if any.
-  // Files with overlapping data blocks (like hardlinks or filesystems with tail
-  // packing or compression where the blocks store more than one file) are only
-  // generated once in the new image, but are also used only once from the old
-  // image due to some simplifications (see below).
-  for (const FilesystemInterface::File& new_file : new_files) {
-    // Ignore the files in the new filesystem without blocks. Symlinks with
-    // data blocks (for example, symlinks bigger than 60 bytes in ext2) are
-    // handled as normal files. We also ignore blocks that were already
-    // processed by a previous file.
-    vector<Extent> new_file_extents = FilterExtentRanges(
-        new_file.extents, new_visited_blocks);
-    new_visited_blocks.AddExtents(new_file_extents);
-
-    if (new_file_extents.empty())
-      continue;
-
-    LOG(INFO) << "Encoding file " << new_file.name << " ("
-              << BlocksInExtents(new_file_extents) << " blocks)";
-
-    // We can't visit each dst image inode more than once, as that would
-    // duplicate work. Here, we avoid visiting each source image inode
-    // more than once. Technically, we could have multiple operations
-    // that read the same blocks from the source image for diffing, but
-    // we choose not to avoid complexity. Eventually we will move away
-    // from using a graph/cycle detection/etc to generate diffs, and at that
-    // time, it will be easy (non-complex) to have many operations read
-    // from the same source blocks. At that time, this code can die. -adlr
-    vector<Extent> old_file_extents = FilterExtentRanges(
-        old_files_map[new_file.name], old_visited_blocks);
-    old_visited_blocks.AddExtents(old_file_extents);
-
-    TEST_AND_RETURN_FALSE(DeltaReadFile(
-        aops,
-        old_part,
-        new_part,
-        old_file_extents,
-        new_file_extents,
-        new_file.name,  // operation name
-        chunk_blocks,
-        data_fd,
-        data_file_size,
-        src_ops_allowed));
-  }
-  // Process all the blocks not included in any file. We provided all the unused
-  // blocks in the old partition as available data.
-  vector<Extent> new_unvisited = { ExtentForRange(0, new_fs->GetBlockCount()) };
-  new_unvisited = FilterExtentRanges(new_unvisited, new_visited_blocks);
-  if (new_unvisited.empty())
-    return true;
-
-  vector<Extent> old_unvisited;
-  if (old_fs) {
-    old_unvisited.push_back(ExtentForRange(0, old_fs->GetBlockCount()));
-    old_unvisited = FilterExtentRanges(old_unvisited, old_visited_blocks);
-  }
-
-  LOG(INFO) << "Scanning " << BlocksInExtents(new_unvisited)
-            << " unwritten blocks";
-  TEST_AND_RETURN_FALSE(DeltaReadFile(
-      aops,
-      old_part,
-      new_part,
-      old_unvisited,
-      new_unvisited,
-      "<non-file-data>",  // operation name
-      chunk_blocks,
-      data_fd,
-      data_file_size,
-      src_ops_allowed));
-
-  return true;
-}
-
-bool DeltaDiffGenerator::DeltaReadFile(
-    vector<AnnotatedOperation>* aops,
-    const string& old_part,
-    const string& new_part,
-    const vector<Extent>& old_extents,
-    const vector<Extent>& new_extents,
-    const string& name,
-    off_t chunk_blocks,
-    int data_fd,
-    off_t* data_file_size,
-    bool src_ops_allowed) {
-  chromeos::Blob data;
-  DeltaArchiveManifest_InstallOperation operation;
-
-  uint64_t total_blocks = BlocksInExtents(new_extents);
-  if (chunk_blocks == -1)
-    chunk_blocks = total_blocks;
-
-  // If bsdiff breaks again, blacklist the problem file by using:
-  //   bsdiff_allowed = (name != "/foo/bar")
-  //
-  // TODO(dgarrett): chromium-os:15274 connect this test to the command line.
-  bool bsdiff_allowed = true;
-  if (static_cast<uint64_t>(chunk_blocks) * kBlockSize >
-      kMaxBsdiffDestinationSize) {
-    bsdiff_allowed = false;
-  }
-
-  if (!bsdiff_allowed) {
-    LOG(INFO) << "bsdiff blacklisting: " << name;
-  }
-
-  for (uint64_t block_offset = 0; block_offset < total_blocks;
-      block_offset += chunk_blocks) {
-    // Split the old/new file in the same chunks. Note that this could drop
-    // some information from the old file used for the new chunk. If the old
-    // file is smaller (or even empty when there's no old file) the chunk will
-    // also be empty.
-    vector<Extent> old_extents_chunk = ExtentsSublist(
-        old_extents, block_offset, chunk_blocks);
-    vector<Extent> new_extents_chunk = ExtentsSublist(
-        new_extents, block_offset, chunk_blocks);
-    NormalizeExtents(&old_extents_chunk);
-    NormalizeExtents(&new_extents_chunk);
-
-    TEST_AND_RETURN_FALSE(ReadExtentsToDiff(old_part,
-                                            new_part,
-                                            old_extents_chunk,
-                                            new_extents_chunk,
-                                            bsdiff_allowed,
-                                            &data,
-                                            &operation,
-                                            src_ops_allowed));
-
-    // Check if the operation writes nothing.
-    if (operation.dst_extents_size() == 0) {
-      if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE) {
-        LOG(INFO) << "Empty MOVE operation ("
-                  << name << "), skipping";
-        continue;
-      } else {
-        LOG(ERROR) << "Empty non-MOVE operation";
-        return false;
-      }
-    }
-
-    // Write the data
-    if (operation.type() != DeltaArchiveManifest_InstallOperation_Type_MOVE &&
-        operation.type() !=
-            DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY) {
-      operation.set_data_offset(*data_file_size);
-      operation.set_data_length(data.size());
-    }
-
-    TEST_AND_RETURN_FALSE(utils::WriteAll(data_fd, data.data(), data.size()));
-    *data_file_size += data.size();
-
-    // Now, insert into the list of operations.
-    AnnotatedOperation aop;
-    aop.name = name;
-    if (static_cast<uint64_t>(chunk_blocks) < total_blocks) {
-      aop.name = base::StringPrintf("%s:%" PRIu64,
-                                    name.c_str(), block_offset / chunk_blocks);
-    }
-    aop.op = operation;
-    aops->emplace_back(aop);
-  }
-  return true;
-}
-
-bool DeltaDiffGenerator::ReadExtentsToDiff(
-    const string& old_part,
-    const string& new_part,
-    const vector<Extent>& old_extents,
-    const vector<Extent>& new_extents,
-    bool bsdiff_allowed,
-    chromeos::Blob* out_data,
-    DeltaArchiveManifest_InstallOperation* out_op,
-    bool src_ops_allowed) {
-  DeltaArchiveManifest_InstallOperation operation;
-  // Data blob that will be written to delta file.
-  const chromeos::Blob* data_blob = nullptr;
-
-  // We read blocks from old_extents and write blocks to new_extents.
-  uint64_t blocks_to_read = BlocksInExtents(old_extents);
-  uint64_t blocks_to_write = BlocksInExtents(new_extents);
-
-  // Make copies of the extents so we can modify them.
-  vector<Extent> src_extents = old_extents;
-  vector<Extent> dst_extents = new_extents;
-
-  // Read in bytes from new data.
-  chromeos::Blob new_data;
-  TEST_AND_RETURN_FALSE(utils::ReadExtents(new_part,
-                                           new_extents,
-                                           &new_data,
-                                           kBlockSize * blocks_to_write,
-                                           kBlockSize));
-  TEST_AND_RETURN_FALSE(!new_data.empty());
-
-
-  // Using a REPLACE is always an option.
-  operation.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
-  data_blob = &new_data;
-
-  // Try compressing it with bzip2.
-  chromeos::Blob new_data_bz;
-  TEST_AND_RETURN_FALSE(BzipCompress(new_data, &new_data_bz));
-  CHECK(!new_data_bz.empty());
-  if (new_data_bz.size() < data_blob->size()) {
-    // A REPLACE_BZ is better.
-    operation.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
-    data_blob = &new_data_bz;
-  }
-
-  chromeos::Blob old_data;
-  chromeos::Blob empty_blob;
-  chromeos::Blob bsdiff_delta;
-  if (blocks_to_read > 0) {
-    // Read old data.
-    TEST_AND_RETURN_FALSE(
-        utils::ReadExtents(old_part, src_extents, &old_data,
-                           kBlockSize * blocks_to_read, kBlockSize));
-    if (old_data == new_data) {
-      // No change in data.
-      if (src_ops_allowed) {
-        operation.set_type(
-            DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
-      } else {
-        operation.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
-      }
-      data_blob = &empty_blob;
-    } else if (bsdiff_allowed) {
-      // If the source file is considered bsdiff safe (no bsdiff bugs
-      // triggered), see if BSDIFF encoding is smaller.
-      base::FilePath old_chunk;
-      TEST_AND_RETURN_FALSE(base::CreateTemporaryFile(&old_chunk));
-      ScopedPathUnlinker old_unlinker(old_chunk.value());
-      TEST_AND_RETURN_FALSE(
-          utils::WriteFile(old_chunk.value().c_str(),
-                           old_data.data(), old_data.size()));
-      base::FilePath new_chunk;
-      TEST_AND_RETURN_FALSE(base::CreateTemporaryFile(&new_chunk));
-      ScopedPathUnlinker new_unlinker(new_chunk.value());
-      TEST_AND_RETURN_FALSE(
-          utils::WriteFile(new_chunk.value().c_str(),
-                           new_data.data(), new_data.size()));
-
-      TEST_AND_RETURN_FALSE(
-          BsdiffFiles(old_chunk.value(), new_chunk.value(), &bsdiff_delta));
-      CHECK_GT(bsdiff_delta.size(), static_cast<chromeos::Blob::size_type>(0));
-      if (bsdiff_delta.size() < data_blob->size()) {
-        if (src_ops_allowed) {
-          operation.set_type(
-              DeltaArchiveManifest_InstallOperation_Type_SOURCE_BSDIFF);
-        } else {
-          operation.set_type(DeltaArchiveManifest_InstallOperation_Type_BSDIFF);
-        }
-        data_blob = &bsdiff_delta;
-      }
-    }
-  }
-
-  size_t removed_bytes = 0;
-  // Remove identical src/dst block ranges in MOVE operations.
-  if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE) {
-    removed_bytes = RemoveIdenticalBlockRanges(
-        &src_extents, &dst_extents, new_data.size());
-  }
-  // Set legacy src_length and dst_length fields.
-  operation.set_src_length(old_data.size() - removed_bytes);
-  operation.set_dst_length(new_data.size() - removed_bytes);
-
-  // Embed extents in the operation.
-  StoreExtents(src_extents, operation.mutable_src_extents());
-  StoreExtents(dst_extents, operation.mutable_dst_extents());
-
-  // Replace operations should not have source extents.
-  if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
-      operation.type() ==
-          DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) {
-    operation.clear_src_extents();
-    operation.clear_src_length();
-  }
-
-  *out_data = std::move(*data_blob);
-  *out_op = operation;
-
-  return true;
-}
-
-bool DeltaDiffGenerator::DeltaCompressKernelPartition(
-    const string& old_kernel_part,
-    const string& new_kernel_part,
-    uint64_t old_kernel_size,
-    uint64_t new_kernel_size,
-    uint64_t block_size,
-    vector<AnnotatedOperation>* aops,
-    int blobs_fd,
-    off_t* blobs_length,
-    bool src_ops_allowed) {
-  LOG(INFO) << "Delta compressing kernel partition...";
-  LOG_IF(INFO, old_kernel_part.empty()) << "Generating full kernel update...";
-
-  unique_ptr<RawFilesystem> old_kernel_fs;
-  if (!old_kernel_part.empty())
-    old_kernel_fs = RawFilesystem::Create("<kernel-delta-operation>",
-                                          block_size,
-                                          old_kernel_size / block_size);
-  unique_ptr<RawFilesystem> new_kernel_fs = RawFilesystem::Create(
-      "<kernel-delta-operation>",
-      block_size,
-      new_kernel_size / block_size);
-
-  TEST_AND_RETURN_FALSE(DeltaReadFilesystem(aops,
-                                            old_kernel_part,
-                                            new_kernel_part,
-                                            old_kernel_fs.get(),
-                                            new_kernel_fs.get(),
-                                            -1,  // chunk_blocks
-                                            blobs_fd,
-                                            blobs_length,
-                                            false,  // skip_block_0
-                                            src_ops_allowed));
-
-  LOG(INFO) << "Done delta compressing kernel partition.";
-  return true;
-}
-
-bool DeltaDiffGenerator::InitializePartitionInfo(const PartitionConfig& part,
-                                                 PartitionInfo* info) {
-  info->set_size(part.size);
-  OmahaHashCalculator hasher;
-  TEST_AND_RETURN_FALSE(hasher.UpdateFile(part.path, part.size) ==
-                        static_cast<off_t>(part.size));
-  TEST_AND_RETURN_FALSE(hasher.Finalize());
-  const chromeos::Blob& hash = hasher.raw_hash();
-  info->set_hash(hash.data(), hash.size());
-  LOG(INFO) << part.path << ": size=" << part.size << " hash=" << hasher.hash();
-  return true;
-}
-
-bool InitializePartitionInfos(const PayloadGenerationConfig& config,
-                              DeltaArchiveManifest* manifest) {
-  if (!config.source.kernel.path.empty()) {
-    TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo(
-        config.source.kernel,
-        manifest->mutable_old_kernel_info()));
-  }
-  TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo(
-      config.target.kernel,
-      manifest->mutable_new_kernel_info()));
-  if (!config.source.rootfs.path.empty()) {
-    TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo(
-        config.source.rootfs,
-        manifest->mutable_old_rootfs_info()));
-  }
-  TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo(
-      config.target.rootfs,
-      manifest->mutable_new_rootfs_info()));
-  return true;
-}
-
-// Stores all Extents in 'extents' into 'out'.
-void DeltaDiffGenerator::StoreExtents(
-    const vector<Extent>& extents,
-    google::protobuf::RepeatedPtrField<Extent>* out) {
-  for (const Extent& extent : extents) {
-    Extent* new_extent = out->Add();
-    *new_extent = extent;
-  }
-}
-
-// Stores all extents in |extents| into |out_vector|.
-void DeltaDiffGenerator::ExtentsToVector(
-    const google::protobuf::RepeatedPtrField<Extent>& extents,
-    vector<Extent>* out_vector) {
-  out_vector->clear();
-  for (int i = 0; i < extents.size(); i++) {
-    out_vector->push_back(extents.Get(i));
-  }
-}
-
-// Returns true if |op| is a no-op operation that doesn't do any useful work
-// (e.g., a move operation that copies blocks onto themselves).
-bool DeltaDiffGenerator::IsNoopOperation(
-    const DeltaArchiveManifest_InstallOperation& op) {
-  return (op.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE &&
-          ExpandExtents(op.src_extents()) == ExpandExtents(op.dst_extents()));
-}
-
-void DeltaDiffGenerator::FilterNoopOperations(vector<AnnotatedOperation>* ops) {
-  ops->erase(
-      std::remove_if(
-          ops->begin(), ops->end(),
-          [](const AnnotatedOperation& aop){return IsNoopOperation(aop.op);}),
-      ops->end());
-}
-
-bool DeltaDiffGenerator::ReorderDataBlobs(
-    DeltaArchiveManifest* manifest,
-    const string& data_blobs_path,
-    const string& new_data_blobs_path) {
-  int in_fd = open(data_blobs_path.c_str(), O_RDONLY, 0);
-  TEST_AND_RETURN_FALSE_ERRNO(in_fd >= 0);
-  ScopedFdCloser in_fd_closer(&in_fd);
-
-  DirectFileWriter writer;
-  TEST_AND_RETURN_FALSE(
-      writer.Open(new_data_blobs_path.c_str(),
-                  O_WRONLY | O_TRUNC | O_CREAT,
-                  0644) == 0);
-  ScopedFileWriterCloser writer_closer(&writer);
-  uint64_t out_file_size = 0;
-
-  for (int i = 0; i < (manifest->install_operations_size() +
-                       manifest->kernel_install_operations_size()); i++) {
-    DeltaArchiveManifest_InstallOperation* op = nullptr;
-    if (i < manifest->install_operations_size()) {
-      op = manifest->mutable_install_operations(i);
-    } else {
-      op = manifest->mutable_kernel_install_operations(
-          i - manifest->install_operations_size());
-    }
-    if (!op->has_data_offset())
-      continue;
-    CHECK(op->has_data_length());
-    chromeos::Blob buf(op->data_length());
-    ssize_t rc = pread(in_fd, buf.data(), buf.size(), op->data_offset());
-    TEST_AND_RETURN_FALSE(rc == static_cast<ssize_t>(buf.size()));
-
-    // Add the hash of the data blobs for this operation
-    TEST_AND_RETURN_FALSE(AddOperationHash(op, buf));
-
-    op->set_data_offset(out_file_size);
-    TEST_AND_RETURN_FALSE(writer.Write(buf.data(), buf.size()));
-    out_file_size += buf.size();
-  }
-  return true;
-}
-
-bool DeltaDiffGenerator::AddOperationHash(
-    DeltaArchiveManifest_InstallOperation* op,
-    const chromeos::Blob& buf) {
-  OmahaHashCalculator hasher;
-  TEST_AND_RETURN_FALSE(hasher.Update(buf.data(), buf.size()));
-  TEST_AND_RETURN_FALSE(hasher.Finalize());
-  const chromeos::Blob& hash = hasher.raw_hash();
-  op->set_data_sha256_hash(hash.data(), hash.size());
-  return true;
-}
-
-bool DeltaDiffGenerator::GenerateOperations(
-    const PayloadGenerationConfig& config,
-    int data_file_fd,
-    off_t* data_file_size,
-    vector<AnnotatedOperation>* rootfs_ops,
-    vector<AnnotatedOperation>* kernel_ops) {
-  unique_ptr<Ext2Filesystem> old_fs = Ext2Filesystem::CreateFromFile(
-      config.source.rootfs.path);
-  unique_ptr<Ext2Filesystem> new_fs = Ext2Filesystem::CreateFromFile(
-      config.target.rootfs.path);
-
-  off_t chunk_blocks = config.chunk_size == -1 ? -1 : (
-      config.chunk_size / config.block_size);
-
-  rootfs_ops->clear();
-  TEST_AND_RETURN_FALSE(DeltaReadFilesystem(rootfs_ops,
-                                            config.source.rootfs.path,
-                                            config.target.rootfs.path,
-                                            old_fs.get(),
-                                            new_fs.get(),
-                                            chunk_blocks,
-                                            data_file_fd,
-                                            data_file_size,
-                                            false,  // skip_block_0
-                                            true));  // src_ops_allowed
-  LOG(INFO) << "done reading normal files";
-
-  // Read kernel partition
-  TEST_AND_RETURN_FALSE(
-      DeltaCompressKernelPartition(config.source.kernel.path,
-                                   config.target.kernel.path,
-                                   config.source.kernel.size,
-                                   config.target.kernel.size,
-                                   config.block_size,
-                                   kernel_ops,
-                                   data_file_fd,
-                                   data_file_size,
-                                   true));  // src_ops_allowed
-  LOG(INFO) << "done reading kernel";
-
-  TEST_AND_RETURN_FALSE(FragmentOperations(rootfs_ops,
-                                           config.target.rootfs.path,
-                                           data_file_fd,
-                                           data_file_size));
-  TEST_AND_RETURN_FALSE(FragmentOperations(kernel_ops,
-                                           config.target.kernel.path,
-                                           data_file_fd,
-                                           data_file_size));
-  SortOperationsByDestination(rootfs_ops);
-  SortOperationsByDestination(kernel_ops);
-  // TODO(alliewood): Change merge operations to use config.chunk_size once
-  // specifying chunk_size on the command line works. crbug/485397.
-  TEST_AND_RETURN_FALSE(MergeOperations(rootfs_ops,
-                                        kDefaultChunkSize,
-                                        config.target.rootfs.path,
-                                        data_file_fd,
-                                        data_file_size));
-  TEST_AND_RETURN_FALSE(MergeOperations(kernel_ops,
-                                        kDefaultChunkSize,
-                                        config.target.kernel.path,
-                                        data_file_fd,
-                                        data_file_size));
-  return true;
-}
 
 bool GenerateUpdatePayloadFile(
     const PayloadGenerationConfig& config,
@@ -859,14 +60,13 @@
 
   const string kTempFileTemplate("CrAU_temp_data.XXXXXX");
   string temp_file_path;
-  unique_ptr<ScopedPathUnlinker> temp_file_unlinker;
   off_t data_file_size = 0;
 
   LOG(INFO) << "Reading files...";
 
-  // Create empty protobuf Manifest object
-  DeltaArchiveManifest manifest;
-  manifest.set_minor_version(config.minor_version);
+  // Create empty payload file object.
+  PayloadFile payload;
+  TEST_AND_RETURN_FALSE(payload.Init(config));
 
   vector<AnnotatedOperation> rootfs_ops;
   vector<AnnotatedOperation> kernel_ops;
@@ -877,17 +77,16 @@
     // We don't efficiently support deltas on squashfs. For now, we will
     // produce full operations in that case.
     if (utils::IsSquashfsFilesystem(config.target.rootfs.path)) {
-      LOG(INFO) << "Using generator FullUpdateGenerator::Run for squashfs "
-                   "deltas";
+      LOG(INFO) << "Using generator FullUpdateGenerator() for squashfs deltas";
       strategy.reset(new FullUpdateGenerator());
     } else if (utils::IsExtFilesystem(config.target.rootfs.path)) {
       // Delta update (with possibly a full kernel update).
       if (config.minor_version == kInPlaceMinorPayloadVersion) {
-        LOG(INFO) << "Using generator InplaceGenerator::GenerateInplaceDelta";
+        LOG(INFO) << "Using generator InplaceGenerator()";
         strategy.reset(new InplaceGenerator());
       } else if (config.minor_version == kSourceMinorPayloadVersion) {
-        LOG(INFO) << "Using generator DeltaDiffGenerator::GenerateSourceDelta";
-        strategy.reset(new DeltaDiffGenerator());
+        LOG(INFO) << "Using generator ABGenerator()";
+        strategy.reset(new ABGenerator());
       } else {
         LOG(ERROR) << "Unsupported minor version given for delta payload: "
                    << config.minor_version;
@@ -904,14 +103,16 @@
     strategy.reset(new FullUpdateGenerator());
   }
 
-  {
-    int data_file_fd;
-    TEST_AND_RETURN_FALSE(
-        utils::MakeTempFile(kTempFileTemplate, &temp_file_path, &data_file_fd));
-    temp_file_unlinker.reset(new ScopedPathUnlinker(temp_file_path));
-    TEST_AND_RETURN_FALSE(data_file_fd >= 0);
-    ScopedFdCloser data_file_fd_closer(&data_file_fd);
 
+  int data_file_fd;
+  TEST_AND_RETURN_FALSE(
+      utils::MakeTempFile(kTempFileTemplate, &temp_file_path, &data_file_fd));
+  unique_ptr<ScopedPathUnlinker> temp_file_unlinker(
+      new ScopedPathUnlinker(temp_file_path));
+  TEST_AND_RETURN_FALSE(data_file_fd >= 0);
+
+  {
+    ScopedFdCloser data_file_fd_closer(&data_file_fd);
     // Generate the operations using the strategy we selected above.
     TEST_AND_RETURN_FALSE(strategy->GenerateOperations(config,
                                                        data_file_fd,
@@ -920,458 +121,22 @@
                                                        &kernel_ops));
   }
 
-  if (!config.source.ImageInfoIsEmpty())
-    *(manifest.mutable_old_image_info()) = config.source.image_info;
-
-  if (!config.target.ImageInfoIsEmpty())
-    *(manifest.mutable_new_image_info()) = config.target.image_info;
-
   // Filter the no-operations. OperationsGenerators should not output this kind
   // of operations normally, but this is an extra step to fix that if
   // happened.
-  DeltaDiffGenerator::FilterNoopOperations(&rootfs_ops);
-  DeltaDiffGenerator::FilterNoopOperations(&kernel_ops);
+  diff_utils::FilterNoopOperations(&rootfs_ops);
+  diff_utils::FilterNoopOperations(&kernel_ops);
 
-  OperationNameMap op_name_map;
-  InstallOperationsToManifest(rootfs_ops, kernel_ops, &manifest, &op_name_map);
-  manifest.set_block_size(config.block_size);
-
-  // Reorder the data blobs with the newly ordered manifest.
-  string ordered_blobs_path;
-  TEST_AND_RETURN_FALSE(utils::MakeTempFile(
-      "CrAU_temp_data.ordered.XXXXXX",
-      &ordered_blobs_path,
-      nullptr));
-  ScopedPathUnlinker ordered_blobs_unlinker(ordered_blobs_path);
-  TEST_AND_RETURN_FALSE(
-      DeltaDiffGenerator::ReorderDataBlobs(&manifest,
-                                           temp_file_path,
-                                           ordered_blobs_path));
+  // Write payload file to disk.
+  payload.AddPartitionOperations(PartitionName::kRootfs, rootfs_ops);
+  payload.AddPartitionOperations(PartitionName::kKernel, kernel_ops);
+  payload.WritePayload(output_path, temp_file_path, private_key_path,
+                       metadata_size);
   temp_file_unlinker.reset();
 
-  // Check that install op blobs are in order.
-  uint64_t next_blob_offset = 0;
-  {
-    for (int i = 0; i < (manifest.install_operations_size() +
-                         manifest.kernel_install_operations_size()); i++) {
-      DeltaArchiveManifest_InstallOperation* op =
-          i < manifest.install_operations_size() ?
-          manifest.mutable_install_operations(i) :
-          manifest.mutable_kernel_install_operations(
-              i - manifest.install_operations_size());
-      if (op->has_data_offset()) {
-        if (op->data_offset() != next_blob_offset) {
-          LOG(FATAL) << "bad blob offset! " << op->data_offset() << " != "
-                     << next_blob_offset;
-        }
-        next_blob_offset += op->data_length();
-      }
-    }
-  }
-
-  // Signatures appear at the end of the blobs. Note the offset in the
-  // manifest
-  if (!private_key_path.empty()) {
-    uint64_t signature_blob_length = 0;
-    TEST_AND_RETURN_FALSE(
-        PayloadSigner::SignatureBlobLength(vector<string>(1, private_key_path),
-                                           &signature_blob_length));
-    DeltaDiffGenerator::AddSignatureOp(
-        next_blob_offset, signature_blob_length, &manifest);
-  }
-
-  TEST_AND_RETURN_FALSE(InitializePartitionInfos(config, &manifest));
-
-  // Serialize protobuf
-  string serialized_manifest;
-
-  TEST_AND_RETURN_FALSE(manifest.AppendToString(&serialized_manifest));
-
-  LOG(INFO) << "Writing final delta file header...";
-  DirectFileWriter writer;
-  TEST_AND_RETURN_FALSE_ERRNO(writer.Open(output_path.c_str(),
-                                          O_WRONLY | O_CREAT | O_TRUNC,
-                                          0644) == 0);
-  ScopedFileWriterCloser writer_closer(&writer);
-
-  // Write header
-  TEST_AND_RETURN_FALSE(writer.Write(kDeltaMagic, strlen(kDeltaMagic)));
-
-  // Write major version number
-  TEST_AND_RETURN_FALSE(WriteUint64AsBigEndian(&writer, kMajorVersionNumber));
-
-  // Write protobuf length
-  TEST_AND_RETURN_FALSE(WriteUint64AsBigEndian(&writer,
-                                               serialized_manifest.size()));
-
-  // Write protobuf
-  LOG(INFO) << "Writing final delta file protobuf... "
-            << serialized_manifest.size();
-  TEST_AND_RETURN_FALSE(writer.Write(serialized_manifest.data(),
-                                     serialized_manifest.size()));
-
-  // Append the data blobs
-  LOG(INFO) << "Writing final delta file data blobs...";
-  int blobs_fd = open(ordered_blobs_path.c_str(), O_RDONLY, 0);
-  ScopedFdCloser blobs_fd_closer(&blobs_fd);
-  TEST_AND_RETURN_FALSE(blobs_fd >= 0);
-  for (;;) {
-    vector<char> buf(config.block_size);
-    ssize_t rc = read(blobs_fd, buf.data(), buf.size());
-    if (0 == rc) {
-      // EOF
-      break;
-    }
-    TEST_AND_RETURN_FALSE_ERRNO(rc > 0);
-    TEST_AND_RETURN_FALSE(writer.Write(buf.data(), rc));
-  }
-
-  // Write signature blob.
-  if (!private_key_path.empty()) {
-    LOG(INFO) << "Signing the update...";
-    chromeos::Blob signature_blob;
-    TEST_AND_RETURN_FALSE(PayloadSigner::SignPayload(
-        output_path,
-        vector<string>(1, private_key_path),
-        &signature_blob));
-    TEST_AND_RETURN_FALSE(writer.Write(signature_blob.data(),
-                                       signature_blob.size()));
-  }
-
-  *metadata_size =
-      strlen(kDeltaMagic) + 2 * sizeof(uint64_t) + serialized_manifest.size();
-  ReportPayloadUsage(manifest, *metadata_size, op_name_map);
-
   LOG(INFO) << "All done. Successfully created delta file with "
             << "metadata size = " << *metadata_size;
   return true;
 }
 
-// Runs the bsdiff tool on two files and returns the resulting delta in
-// 'out'. Returns true on success.
-bool DeltaDiffGenerator::BsdiffFiles(const string& old_file,
-                                     const string& new_file,
-                                     chromeos::Blob* out) {
-  const string kPatchFile = "delta.patchXXXXXX";
-  string patch_file_path;
-
-  TEST_AND_RETURN_FALSE(
-      utils::MakeTempFile(kPatchFile, &patch_file_path, nullptr));
-
-  vector<string> cmd;
-  cmd.push_back(kBsdiffPath);
-  cmd.push_back(old_file);
-  cmd.push_back(new_file);
-  cmd.push_back(patch_file_path);
-
-  int rc = 1;
-  chromeos::Blob patch_file;
-  TEST_AND_RETURN_FALSE(Subprocess::SynchronousExec(cmd, &rc, nullptr));
-  TEST_AND_RETURN_FALSE(rc == 0);
-  TEST_AND_RETURN_FALSE(utils::ReadFile(patch_file_path, out));
-  unlink(patch_file_path.c_str());
-  return true;
-}
-
-void DeltaDiffGenerator::AddSignatureOp(uint64_t signature_blob_offset,
-                                        uint64_t signature_blob_length,
-                                        DeltaArchiveManifest* manifest) {
-  LOG(INFO) << "Making room for signature in file";
-  manifest->set_signatures_offset(signature_blob_offset);
-  LOG(INFO) << "set? " << manifest->has_signatures_offset();
-  // Add a dummy op at the end to appease older clients
-  DeltaArchiveManifest_InstallOperation* dummy_op =
-      manifest->add_kernel_install_operations();
-  dummy_op->set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
-  dummy_op->set_data_offset(signature_blob_offset);
-  manifest->set_signatures_offset(signature_blob_offset);
-  dummy_op->set_data_length(signature_blob_length);
-  manifest->set_signatures_size(signature_blob_length);
-  Extent* dummy_extent = dummy_op->add_dst_extents();
-  // Tell the dummy op to write this data to a big sparse hole
-  dummy_extent->set_start_block(kSparseHole);
-  dummy_extent->set_num_blocks((signature_blob_length + kBlockSize - 1) /
-                               kBlockSize);
-}
-
-bool DeltaDiffGenerator::FragmentOperations(
-    vector<AnnotatedOperation>* aops,
-    const string& target_part_path,
-    int data_fd,
-    off_t* data_file_size) {
-  vector<AnnotatedOperation> fragmented_aops;
-  for (const AnnotatedOperation& aop : *aops) {
-    if (aop.op.type() ==
-        DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY) {
-      TEST_AND_RETURN_FALSE(SplitSourceCopy(aop, &fragmented_aops));
-    } else if ((aop.op.type() ==
-                DeltaArchiveManifest_InstallOperation_Type_REPLACE) ||
-               (aop.op.type() ==
-                DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ)) {
-      TEST_AND_RETURN_FALSE(SplitReplaceOrReplaceBz(aop, &fragmented_aops,
-                                                    target_part_path, data_fd,
-                                                    data_file_size));
-    } else {
-      fragmented_aops.push_back(aop);
-    }
-  }
-  *aops = fragmented_aops;
-  return true;
-}
-
-void DeltaDiffGenerator::SortOperationsByDestination(
-    vector<AnnotatedOperation>* aops) {
-  sort(aops->begin(), aops->end(), CompareAopsByDestination);
-}
-
-bool DeltaDiffGenerator::SplitSourceCopy(
-    const AnnotatedOperation& original_aop,
-    vector<AnnotatedOperation>* result_aops) {
-  DeltaArchiveManifest_InstallOperation original_op = original_aop.op;
-  TEST_AND_RETURN_FALSE(original_op.type() ==
-                        DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
-  // Keeps track of the index of curr_src_ext.
-  int curr_src_ext_index = 0;
-  Extent curr_src_ext = original_op.src_extents(curr_src_ext_index);
-  for (int i = 0; i < original_op.dst_extents_size(); i++) {
-    Extent dst_ext = original_op.dst_extents(i);
-    // The new operation which will have only one dst extent.
-    DeltaArchiveManifest_InstallOperation new_op;
-    uint64_t blocks_left = dst_ext.num_blocks();
-    while (blocks_left > 0) {
-      if (curr_src_ext.num_blocks() <= blocks_left) {
-        // If the curr_src_ext is smaller than dst_ext, add it.
-        blocks_left -= curr_src_ext.num_blocks();
-        *(new_op.add_src_extents()) = curr_src_ext;
-        if (curr_src_ext_index + 1 < original_op.src_extents().size()) {
-          curr_src_ext = original_op.src_extents(++curr_src_ext_index);
-        } else {
-          break;
-        }
-      } else {
-        // Split src_exts that are bigger than the dst_ext we're dealing with.
-        Extent first_ext;
-        first_ext.set_num_blocks(blocks_left);
-        first_ext.set_start_block(curr_src_ext.start_block());
-        *(new_op.add_src_extents()) = first_ext;
-        // Keep the second half of the split op.
-        curr_src_ext.set_num_blocks(curr_src_ext.num_blocks() - blocks_left);
-        curr_src_ext.set_start_block(curr_src_ext.start_block() + blocks_left);
-        blocks_left -= first_ext.num_blocks();
-      }
-    }
-    // Fix up our new operation and add it to the results.
-    new_op.set_type(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
-    *(new_op.add_dst_extents()) = dst_ext;
-    new_op.set_src_length(dst_ext.num_blocks() * kBlockSize);
-    new_op.set_dst_length(dst_ext.num_blocks() * kBlockSize);
-
-    AnnotatedOperation new_aop;
-    new_aop.op = new_op;
-    new_aop.name = base::StringPrintf("%s:%d", original_aop.name.c_str(), i);
-    result_aops->push_back(new_aop);
-  }
-  if (curr_src_ext_index != original_op.src_extents().size() - 1) {
-    LOG(FATAL) << "Incorrectly split SOURCE_COPY operation. Did not use all "
-               << "source extents.";
-  }
-  return true;
-}
-
-bool DeltaDiffGenerator::SplitReplaceOrReplaceBz(
-    const AnnotatedOperation& original_aop,
-    vector<AnnotatedOperation>* result_aops,
-    const string& target_part_path,
-    int data_fd,
-    off_t* data_file_size) {
-  DeltaArchiveManifest_InstallOperation original_op = original_aop.op;
-  const bool is_replace =
-      original_op.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE;
-  TEST_AND_RETURN_FALSE(
-      is_replace ||
-      (original_op.type() ==
-       DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ));
-
-  uint32_t data_offset = original_op.data_offset();
-  for (int i = 0; i < original_op.dst_extents_size(); i++) {
-    Extent dst_ext = original_op.dst_extents(i);
-    // Make a new operation with only one dst extent.
-    DeltaArchiveManifest_InstallOperation new_op;
-    *(new_op.add_dst_extents()) = dst_ext;
-    uint32_t data_size = dst_ext.num_blocks() * kBlockSize;
-    new_op.set_dst_length(data_size);
-    // If this is a REPLACE, attempt to reuse portions of the existing blob.
-    if (is_replace) {
-      new_op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
-      new_op.set_data_length(data_size);
-      new_op.set_data_offset(data_offset);
-      data_offset += data_size;
-    }
-
-    AnnotatedOperation new_aop;
-    new_aop.op = new_op;
-    new_aop.name = base::StringPrintf("%s:%d", original_aop.name.c_str(), i);
-    TEST_AND_RETURN_FALSE(AddDataAndSetType(&new_aop, target_part_path, data_fd,
-                                            data_file_size));
-
-    result_aops->push_back(new_aop);
-  }
-  return true;
-}
-
-bool DeltaDiffGenerator::MergeOperations(vector<AnnotatedOperation>* aops,
-                                         off_t chunk_size,
-                                         const string& target_part_path,
-                                         int data_fd,
-                                         off_t* data_file_size) {
-  vector<AnnotatedOperation> new_aops;
-  for (const AnnotatedOperation& curr_aop : *aops) {
-    if (new_aops.empty()) {
-      new_aops.push_back(curr_aop);
-      continue;
-    }
-    AnnotatedOperation& last_aop = new_aops.back();
-
-    if (last_aop.op.dst_extents_size() <= 0 ||
-        curr_aop.op.dst_extents_size() <= 0) {
-      new_aops.push_back(curr_aop);
-      continue;
-    }
-    uint32_t last_dst_idx = last_aop.op.dst_extents_size() - 1;
-    uint32_t last_end_block =
-        last_aop.op.dst_extents(last_dst_idx).start_block() +
-        last_aop.op.dst_extents(last_dst_idx).num_blocks();
-    uint32_t curr_start_block = curr_aop.op.dst_extents(0).start_block();
-    uint32_t combined_block_count =
-        last_aop.op.dst_extents(last_dst_idx).num_blocks() +
-        curr_aop.op.dst_extents(0).num_blocks();
-    bool good_op_type =
-        curr_aop.op.type() ==
-            DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY ||
-        curr_aop.op.type() ==
-            DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
-        curr_aop.op.type() ==
-            DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ;
-    if (good_op_type &&
-        last_aop.op.type() == curr_aop.op.type() &&
-        last_end_block == curr_start_block &&
-        static_cast<off_t>(combined_block_count * kBlockSize) <= chunk_size) {
-      // If the operations have the same type (which is a type that we can
-      // merge), are contiguous, are fragmented to have one destination extent,
-      // and their combined block count would be less than chunk size, merge
-      // them.
-      last_aop.name = base::StringPrintf("%s,%s",
-                                         last_aop.name.c_str(),
-                                         curr_aop.name.c_str());
-
-      ExtendExtents(last_aop.op.mutable_src_extents(),
-                    curr_aop.op.src_extents());
-      if (curr_aop.op.src_length() > 0)
-        last_aop.op.set_src_length(last_aop.op.src_length() +
-                                   curr_aop.op.src_length());
-      ExtendExtents(last_aop.op.mutable_dst_extents(),
-                    curr_aop.op.dst_extents());
-      if (curr_aop.op.dst_length() > 0)
-        last_aop.op.set_dst_length(last_aop.op.dst_length() +
-                                   curr_aop.op.dst_length());
-      // Set the data length to zero so we know to add the blob later.
-      if (curr_aop.op.type() ==
-          DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
-          curr_aop.op.type() ==
-          DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) {
-        last_aop.op.set_data_length(0);
-      }
-    } else {
-      // Otherwise just include the extent as is.
-      new_aops.push_back(curr_aop);
-    }
-  }
-
-  // Set the blobs for REPLACE/REPLACE_BZ operations that have been merged.
-  for (AnnotatedOperation& curr_aop : new_aops) {
-    if (curr_aop.op.data_length() == 0 &&
-        (curr_aop.op.type() ==
-            DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
-         curr_aop.op.type() ==
-            DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ)) {
-      TEST_AND_RETURN_FALSE(AddDataAndSetType(&curr_aop, target_part_path,
-                                              data_fd, data_file_size));
-    }
-  }
-
-  *aops = new_aops;
-  return true;
-}
-
-void DeltaDiffGenerator::ExtendExtents(
-    google::protobuf::RepeatedPtrField<Extent>* extents,
-    const google::protobuf::RepeatedPtrField<Extent>& extents_to_add) {
-  vector<Extent> extents_vector;
-  vector<Extent> extents_to_add_vector;
-  ExtentsToVector(*extents, &extents_vector);
-  ExtentsToVector(extents_to_add, &extents_to_add_vector);
-  extents_vector.insert(extents_vector.end(),
-                        extents_to_add_vector.begin(),
-                        extents_to_add_vector.end());
-  NormalizeExtents(&extents_vector);
-  extents->Clear();
-  StoreExtents(extents_vector, extents);
-}
-
-bool DeltaDiffGenerator::AddDataAndSetType(AnnotatedOperation* aop,
-                                           const string& target_part_path,
-                                           int data_fd,
-                                           off_t* data_file_size) {
-  TEST_AND_RETURN_FALSE(
-      aop->op.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
-      aop->op.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
-
-  chromeos::Blob data(aop->op.dst_length());
-  vector<Extent> dst_extents;
-  ExtentsToVector(aop->op.dst_extents(), &dst_extents);
-  TEST_AND_RETURN_FALSE(utils::ReadExtents(target_part_path,
-                                           dst_extents,
-                                           &data,
-                                           data.size(),
-                                           kBlockSize));
-
-  chromeos::Blob data_bz;
-  TEST_AND_RETURN_FALSE(BzipCompress(data, &data_bz));
-  CHECK(!data_bz.empty());
-
-  chromeos::Blob* data_p = nullptr;
-  DeltaArchiveManifest_InstallOperation_Type new_op_type;
-  if (data_bz.size() < data.size()) {
-    new_op_type = DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ;
-    data_p = &data_bz;
-  } else {
-    new_op_type = DeltaArchiveManifest_InstallOperation_Type_REPLACE;
-    data_p = &data;
-  }
-
-  // If the operation already points to a data blob, check whether it's
-  // identical to the new one, in which case don't add it.
-  if (aop->op.type() == new_op_type &&
-      aop->op.data_length() == data_p->size()) {
-    chromeos::Blob current_data(data_p->size());
-    ssize_t bytes_read;
-    TEST_AND_RETURN_FALSE(utils::PReadAll(data_fd,
-                                          current_data.data(),
-                                          aop->op.data_length(),
-                                          aop->op.data_offset(),
-                                          &bytes_read));
-    TEST_AND_RETURN_FALSE(bytes_read ==
-                          static_cast<ssize_t>(aop->op.data_length()));
-    if (current_data == *data_p)
-      data_p = nullptr;
-  }
-
-  if (data_p) {
-    aop->op.set_type(new_op_type);
-    aop->SetOperationBlob(data_p, data_fd, data_file_size);
-  }
-
-  return true;
-}
-
 };  // namespace chromeos_update_engine
diff --git a/payload_generator/delta_diff_generator.h b/payload_generator/delta_diff_generator.h
index b3b5cee..8ba1dc0 100644
--- a/payload_generator/delta_diff_generator.h
+++ b/payload_generator/delta_diff_generator.h
@@ -5,19 +5,9 @@
 #ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_DELTA_DIFF_GENERATOR_H_
 #define UPDATE_ENGINE_PAYLOAD_GENERATOR_DELTA_DIFF_GENERATOR_H_
 
-#include <set>
 #include <string>
-#include <vector>
 
-#include <base/macros.h>
-#include <chromeos/secure_blob.h>
-
-#include "update_engine/payload_constants.h"
-#include "update_engine/payload_generator/extent_utils.h"
-#include "update_engine/payload_generator/filesystem_interface.h"
-#include "update_engine/payload_generator/operations_generator.h"
 #include "update_engine/payload_generator/payload_generation_config.h"
-#include "update_engine/update_metadata.pb.h"
 
 // There is one function in DeltaDiffGenerator of importance to users
 // of the class: GenerateDeltaUpdateFile(). Before calling it,
@@ -28,250 +18,9 @@
 
 namespace chromeos_update_engine {
 
-extern const char* const kEmptyPath;
 extern const size_t kBlockSize;
 extern const size_t kRootFSPartitionSize;
 
-class DeltaDiffGenerator : public OperationsGenerator {
- public:
-  DeltaDiffGenerator() = default;
-
-  // These functions are public so that the unit tests can access them:
-
-  // Generate the update payload operations for the kernel and rootfs using
-  // SOURCE_* operations, used to generate deltas for the minor version
-  // kSourceMinorPayloadVersion. This function will generate operations in the
-  // rootfs that will read blocks from the source partition in random order and
-  // write the new image on the target partition, also possibly in random order.
-  // The rootfs operations are stored in |rootfs_ops| and should be executed in
-  // that order. The kernel operations are stored in |kernel_ops|. All
-  // the offsets in the operations reference the data written to |data_file_fd|.
-  // The total amount of data written to that file is stored in
-  // |data_file_size|.
-  bool GenerateOperations(
-      const PayloadGenerationConfig& config,
-      int data_file_fd,
-      off_t* data_file_size,
-      std::vector<AnnotatedOperation>* rootfs_ops,
-      std::vector<AnnotatedOperation>* kernel_ops) override;
-
-  // Create operations in |aops| to produce all the files reported by |new_fs|,
-  // including all the blocks not reported by any file.
-  // It uses the files reported by |old_fs| and the data in |old_part| to
-  // determine the best way to compress the new files (REPLACE, REPLACE_BZ,
-  // COPY, BSDIFF) and writes any necessary data to the end of data_fd updating
-  // data_file_size accordingly.
-  static bool DeltaReadFilesystem(std::vector<AnnotatedOperation>* aops,
-                                  const std::string& old_part,
-                                  const std::string& new_part,
-                                  FilesystemInterface* old_fs,
-                                  FilesystemInterface* new_fs,
-                                  off_t chunk_blocks,
-                                  int data_fd,
-                                  off_t* data_file_size,
-                                  bool skip_block_0,
-                                  bool src_ops_allowed);
-
-  // For a given file |name| append operations to |aops| to produce it in the
-  // |new_part|. The file will be split in chunks of |chunk_blocks| blocks each
-  // or treated as a single chunk if |chunk_blocks| is -1. The file data is
-  // stored in |new_part| in the blocks described by |new_extents| and, if it
-  // exists, the old version exists in |old_part| in the blocks described by
-  // |old_extents|. The operations added to |aops| reference the data blob
-  // in the file |data_fd|, which has length *data_file_size. *data_file_size is
-  // updated appropriately. Returns true on success.
-  static bool DeltaReadFile(std::vector<AnnotatedOperation>* aops,
-                            const std::string& old_part,
-                            const std::string& new_part,
-                            const std::vector<Extent>& old_extents,
-                            const std::vector<Extent>& new_extents,
-                            const std::string& name,
-                            off_t chunk_blocks,
-                            int data_fd,
-                            off_t* data_file_size,
-                            bool src_ops_allowed);
-
-  // Reads the blocks |old_extents| from |old_part| (if it exists) and the
-  // |new_extents| from |new_part| and determines the smallest way to encode
-  // this |new_extents| for the diff. It stores necessary data in |out_data| and
-  // fills in |out_op|. If there's no change in old and new files, it creates a
-  // MOVE operation. If there is a change, the smallest of REPLACE, REPLACE_BZ,
-  // or BSDIFF wins. |new_extents| must not be empty.
-  // If |src_ops_allowed| is true, it will emit SOURCE_COPY and SOURCE_BSDIFF
-  // operations instead of MOVE and BSDIFF, respectively.
-  // Returns true on success.
-  static bool ReadExtentsToDiff(const std::string& old_part,
-                                const std::string& new_part,
-                                const std::vector<Extent>& old_extents,
-                                const std::vector<Extent>& new_extents,
-                                bool bsdiff_allowed,
-                                chromeos::Blob* out_data,
-                                DeltaArchiveManifest_InstallOperation* out_op,
-                                bool src_ops_allowed);
-
-  // 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. The size of the old and
-  // new kernel is passed in |old_kernel_size| and |new_kernel_size|. The
-  // operations used to generate the new kernel are stored in the |aops|
-  // vector, and the blob associated to those operations is written at the end
-  // of the |blobs_fd| file, adding to the value pointed by |blobs_length| the
-  // bytes written to |blobs_fd|.
-  static bool DeltaCompressKernelPartition(
-      const std::string& old_kernel_part,
-      const std::string& new_kernel_part,
-      uint64_t old_kernel_size,
-      uint64_t new_kernel_size,
-      uint64_t block_size,
-      std::vector<AnnotatedOperation>* aops,
-      int blobs_fd,
-      off_t* blobs_length,
-      bool src_ops_allowed);
-
-  // Stores all Extents in 'extents' into 'out'.
-  static void StoreExtents(const std::vector<Extent>& extents,
-                           google::protobuf::RepeatedPtrField<Extent>* out);
-
-  // Stores all extents in |extents| into |out_vector|.
-  static void ExtentsToVector(
-    const google::protobuf::RepeatedPtrField<Extent>& extents,
-    std::vector<Extent>* out_vector);
-
-  // Install operations in the manifest may reference data blobs, which
-  // are in data_blobs_path. This function creates a new data blobs file
-  // with the data blobs in the same order as the referencing install
-  // operations in the manifest. E.g. if manifest[0] has a data blob
-  // "X" at offset 1, manifest[1] has a data blob "Y" at offset 0,
-  // and data_blobs_path's file contains "YX", new_data_blobs_path
-  // will set to be a file that contains "XY".
-  static bool ReorderDataBlobs(DeltaArchiveManifest* manifest,
-                               const std::string& data_blobs_path,
-                               const std::string& new_data_blobs_path);
-
-  // Computes a SHA256 hash of the given buf and sets the hash value in the
-  // operation so that update_engine could verify. This hash should be set
-  // for all operations that have a non-zero data blob. One exception is the
-  // dummy operation for signature blob because the contents of the signature
-  // blob will not be available at payload creation time. So, update_engine will
-  // gracefully ignore the dummy signature operation.
-  static bool AddOperationHash(DeltaArchiveManifest_InstallOperation* op,
-                               const chromeos::Blob& buf);
-
-
-  // Returns true if |op| is a no-op operation that doesn't do any useful work
-  // (e.g., a move operation that copies blocks onto themselves).
-  static bool IsNoopOperation(const DeltaArchiveManifest_InstallOperation& op);
-
-  // Filters all the operations that are no-op, maintaining the relative order
-  // of the rest of the operations.
-  static void FilterNoopOperations(std::vector<AnnotatedOperation>* ops);
-
-  static bool InitializePartitionInfo(const PartitionConfig& partition,
-                                      PartitionInfo* info);
-
-  // Runs the bsdiff tool on two files and returns the resulting delta in
-  // |out|. Returns true on success.
-  static bool BsdiffFiles(const std::string& old_file,
-                          const std::string& new_file,
-                          chromeos::Blob* out);
-
-  // Adds to |manifest| a dummy operation that points to a signature blob
-  // located at the specified offset/length.
-  static void AddSignatureOp(uint64_t signature_blob_offset,
-                             uint64_t signature_blob_length,
-                             DeltaArchiveManifest* manifest);
-
-  // Takes a collection (vector or RepeatedPtrField) of Extent and
-  // returns a vector of the blocks referenced, in order.
-  template<typename T>
-  static std::vector<uint64_t> ExpandExtents(const T& extents) {
-    std::vector<uint64_t> ret;
-    for (size_t i = 0, e = static_cast<size_t>(extents.size()); i != e; ++i) {
-      const Extent extent = GetElement(extents, i);
-      if (extent.start_block() == kSparseHole) {
-        ret.resize(ret.size() + extent.num_blocks(), kSparseHole);
-      } else {
-        for (uint64_t block = extent.start_block();
-             block < (extent.start_block() + extent.num_blocks()); block++) {
-          ret.push_back(block);
-        }
-      }
-    }
-    return ret;
-  }
-
-  // Takes a vector of AnnotatedOperations |aops| and fragments those operations
-  // such that there is only one dst extent per operation. Sets |aops| to a
-  // vector of the new fragmented operations.
-  static bool FragmentOperations(std::vector<AnnotatedOperation>* aops,
-                                 const std::string& target_rootfs_part,
-                                 int data_fd,
-                                 off_t* data_file_size);
-
-  // Takes a vector of AnnotatedOperations |aops| and sorts them by the first
-  // start block in their destination extents. Sets |aops| to a vector of the
-  // sorted operations.
-  static void SortOperationsByDestination(
-      std::vector<AnnotatedOperation>* aops);
-
-  // Takes an SOURCE_COPY install operation, |aop|, and adds one operation for
-  // each dst extent in |aop| to |ops|. The new operations added to |ops| will
-  // have only one dst extent. The src extents are split so the number of blocks
-  // in the src and dst extents are equal.
-  // E.g. we have a SOURCE_COPY operation:
-  //   src extents: [(1, 3), (5, 1), (7, 1)], dst extents: [(2, 2), (6, 3)]
-  // Then we will get 2 new operations:
-  //   1. src extents: [(1, 2)], dst extents: [(2, 2)]
-  //   2. src extents: [(3, 1),(5, 1),(7, 1)], dst extents: [(6, 3)]
-  static bool SplitSourceCopy(const AnnotatedOperation& original_aop,
-                              std::vector<AnnotatedOperation>* result_aops);
-
-  // Takes a REPLACE/REPLACE_BZ operation |aop|, and adds one operation for each
-  // dst extent in |aop| to |ops|. The new operations added to |ops| will have
-  // only one dst extent each, and may be either a REPLACE or REPLACE_BZ
-  // depending on whether compression is advantageous.
-  static bool SplitReplaceOrReplaceBz(
-      const AnnotatedOperation& original_aop,
-      std::vector<AnnotatedOperation>* result_aops,
-      const std::string& target_part,
-      int data_fd,
-      off_t* data_file_size);
-
-  // Takes a sorted (by first destination extent) vector of operations |aops|
-  // and merges SOURCE_COPY, REPLACE, and REPLACE_BZ operations in that vector.
-  // It will merge two operations if:
-  //   - They are of the same type.
-  //   - They are contiguous.
-  //   - Their combined blocks do not exceed |chunk_size|.
-  static bool MergeOperations(std::vector<AnnotatedOperation>* aops,
-                              off_t chunk_size,
-                              const std::string& target_part,
-                              int data_fd,
-                              off_t* data_file_size);
-
-  // Takes a pointer to extents |extents| and extents |extents_to_add|, and
-  // merges them by adding |extents_to_add| to |extents| and normalizing.
-  static void ExtendExtents(
-    google::protobuf::RepeatedPtrField<Extent>* extents,
-    const google::protobuf::RepeatedPtrField<Extent>& extents_to_add);
-
- private:
-  // Adds the data payload for a REPLACE/REPLACE_BZ operation |aop| by reading
-  // its output extents from |target_part_path| and appending a corresponding
-  // data blob to |data_fd|. The blob will be compressed if this is smaller than
-  // the uncompressed form, and the operation type will be set accordingly.
-  // |*data_file_size| will be updated as well. If the operation happens to have
-  // the right type and already points to a data blob, we check whether its
-  // content is identical to the new one, in which case nothing is written.
-  static bool AddDataAndSetType(AnnotatedOperation* aop,
-                                const std::string& target_part_path,
-                                int data_fd,
-                                off_t* data_file_size);
-
-  DISALLOW_COPY_AND_ASSIGN(DeltaDiffGenerator);
-};
-
-// This is the only function that external users of this module should call.
 // The |config| describes the payload generation request, describing both
 // old and new images for delta payloads and only the new image for full
 // payloads.
diff --git a/payload_generator/delta_diff_generator_unittest.cc b/payload_generator/delta_diff_generator_unittest.cc
deleted file mode 100644
index 187da7a..0000000
--- a/payload_generator/delta_diff_generator_unittest.cc
+++ /dev/null
@@ -1,1076 +0,0 @@
-// Copyright (c) 2012 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.
-
-#include "update_engine/payload_generator/delta_diff_generator.h"
-
-#include <fcntl.h>
-#include <sys/stat.h>
-#include <sys/types.h>
-#include <unistd.h>
-
-#include <algorithm>
-#include <cstdio>
-#include <map>
-#include <set>
-#include <sstream>
-#include <string>
-#include <utility>
-#include <vector>
-
-#include <base/files/scoped_file.h>
-#include <base/logging.h>
-#include <base/strings/string_util.h>
-#include <bzlib.h>
-#include <chromeos/secure_blob.h>
-#include <gtest/gtest.h>
-
-#include "update_engine/bzip.h"
-#include "update_engine/delta_performer.h"
-#include "update_engine/payload_constants.h"
-#include "update_engine/payload_generator/extent_ranges.h"
-#include "update_engine/payload_generator/extent_utils.h"
-#include "update_engine/payload_generator/fake_filesystem.h"
-#include "update_engine/payload_generator/graph_types.h"
-#include "update_engine/subprocess.h"
-#include "update_engine/test_utils.h"
-#include "update_engine/utils.h"
-
-using std::set;
-using std::string;
-using std::unique_ptr;
-using std::vector;
-
-namespace chromeos_update_engine {
-
-namespace {
-
-// Writes the |data| in the blocks specified by |extents| on the partition
-// |part_path|. The |data| size could be smaller than the size of the blocks
-// passed.
-bool WriteExtents(const string& part_path,
-                  const vector<Extent>& extents,
-                  off_t block_size,
-                  const chromeos::Blob& data) {
-  uint64_t offset = 0;
-  base::ScopedFILE fp(fopen(part_path.c_str(), "r+"));
-  TEST_AND_RETURN_FALSE(fp.get());
-
-  for (const Extent& extent : extents) {
-    if (offset >= data.size())
-      break;
-    TEST_AND_RETURN_FALSE(
-        fseek(fp.get(), extent.start_block() * block_size, SEEK_SET) == 0);
-    uint64_t to_write = std::min(extent.num_blocks() * block_size,
-                                 data.size() - offset);
-    TEST_AND_RETURN_FALSE(
-        fwrite(data.data() + offset, 1, to_write, fp.get()) == to_write);
-    offset += extent.num_blocks() * block_size;
-  }
-  return true;
-}
-
-bool ExtentEquals(Extent ext, uint64_t start_block, uint64_t num_blocks) {
-  return ext.start_block() == start_block && ext.num_blocks() == num_blocks;
-}
-
-// Tests splitting of a REPLACE/REPLACE_BZ operation.
-void TestSplitReplaceOrReplaceBzOperation(
-    DeltaArchiveManifest_InstallOperation_Type orig_type,
-    bool compressible) {
-  const size_t op_ex1_start_block = 2;
-  const size_t op_ex1_num_blocks = 2;
-  const size_t op_ex2_start_block = 6;
-  const size_t op_ex2_num_blocks = 1;
-  const size_t part_num_blocks = 7;
-
-  // Create the target partition data.
-  string part_path;
-  EXPECT_TRUE(utils::MakeTempFile(
-      "SplitReplaceOrReplaceBzTest_part.XXXXXX", &part_path, nullptr));
-  ScopedPathUnlinker part_path_unlinker(part_path);
-  const size_t part_size = part_num_blocks * kBlockSize;
-  chromeos::Blob part_data;
-  if (compressible) {
-    part_data.resize(part_size);
-    test_utils::FillWithData(&part_data);
-  } else {
-    std::mt19937 gen(12345);
-    std::uniform_int_distribution<uint8_t> dis(0, 255);
-    for (uint32_t i = 0; i < part_size; i++)
-      part_data.push_back(dis(gen));
-  }
-  ASSERT_EQ(part_size, part_data.size());
-  ASSERT_TRUE(utils::WriteFile(part_path.c_str(), part_data.data(), part_size));
-
-  // Create original operation and blob data.
-  const size_t op_ex1_offset = op_ex1_start_block * kBlockSize;
-  const size_t op_ex1_size = op_ex1_num_blocks * kBlockSize;
-  const size_t op_ex2_offset = op_ex2_start_block * kBlockSize;
-  const size_t op_ex2_size = op_ex2_num_blocks * kBlockSize;
-  DeltaArchiveManifest_InstallOperation op;
-  op.set_type(orig_type);
-  *(op.add_dst_extents()) = ExtentForRange(op_ex1_start_block,
-                                           op_ex1_num_blocks);
-  *(op.add_dst_extents()) = ExtentForRange(op_ex2_start_block,
-                                           op_ex2_num_blocks);
-  op.set_dst_length(op_ex1_num_blocks + op_ex2_num_blocks);
-
-  chromeos::Blob op_data;
-  op_data.insert(op_data.end(),
-                 part_data.begin() + op_ex1_offset,
-                 part_data.begin() + op_ex1_offset + op_ex1_size);
-  op_data.insert(op_data.end(),
-                 part_data.begin() + op_ex2_offset,
-                 part_data.begin() + op_ex2_offset + op_ex2_size);
-  chromeos::Blob op_blob;
-  if (orig_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE) {
-    op_blob = op_data;
-  } else {
-    ASSERT_TRUE(BzipCompress(op_data, &op_blob));
-  }
-  op.set_data_offset(0);
-  op.set_data_length(op_blob.size());
-
-  AnnotatedOperation aop;
-  aop.op = op;
-  aop.name = "SplitTestOp";
-
-  // Create the data file.
-  string data_path;
-  EXPECT_TRUE(utils::MakeTempFile(
-      "SplitReplaceOrReplaceBzTest_data.XXXXXX", &data_path, nullptr));
-  ScopedPathUnlinker data_path_unlinker(data_path);
-  int data_fd = open(data_path.c_str(), O_RDWR, 000);
-  EXPECT_GE(data_fd, 0);
-  ScopedFdCloser data_fd_closer(&data_fd);
-  EXPECT_TRUE(utils::WriteFile(data_path.c_str(), op_blob.data(),
-                               op_blob.size()));
-  off_t data_file_size = op_blob.size();
-
-  // Split the operation.
-  vector<AnnotatedOperation> result_ops;
-  ASSERT_TRUE(DeltaDiffGenerator::SplitReplaceOrReplaceBz(
-          aop, &result_ops, part_path, data_fd, &data_file_size));
-
-  // Check the result.
-  DeltaArchiveManifest_InstallOperation_Type expected_type =
-      compressible ?
-      DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ :
-      DeltaArchiveManifest_InstallOperation_Type_REPLACE;
-
-  ASSERT_EQ(2, result_ops.size());
-
-  EXPECT_EQ("SplitTestOp:0", result_ops[0].name);
-  DeltaArchiveManifest_InstallOperation first_op = result_ops[0].op;
-  EXPECT_EQ(expected_type, first_op.type());
-  EXPECT_EQ(op_ex1_size, first_op.dst_length());
-  EXPECT_EQ(1, first_op.dst_extents().size());
-  EXPECT_TRUE(ExtentEquals(first_op.dst_extents(0), op_ex1_start_block,
-                           op_ex1_num_blocks));
-  // Obtain the expected blob.
-  chromeos::Blob first_expected_data(
-      part_data.begin() + op_ex1_offset,
-      part_data.begin() + op_ex1_offset + op_ex1_size);
-  chromeos::Blob first_expected_blob;
-  if (compressible) {
-    ASSERT_TRUE(BzipCompress(first_expected_data, &first_expected_blob));
-  } else {
-    first_expected_blob = first_expected_data;
-  }
-  EXPECT_EQ(first_expected_blob.size(), first_op.data_length());
-  // Check that the actual blob matches what's expected.
-  chromeos::Blob first_data_blob(first_op.data_length());
-  ssize_t bytes_read;
-  ASSERT_TRUE(utils::PReadAll(data_fd,
-                              first_data_blob.data(),
-                              first_op.data_length(),
-                              first_op.data_offset(),
-                              &bytes_read));
-  ASSERT_EQ(bytes_read, first_op.data_length());
-  EXPECT_EQ(first_expected_blob, first_data_blob);
-
-  EXPECT_EQ("SplitTestOp:1", result_ops[1].name);
-  DeltaArchiveManifest_InstallOperation second_op = result_ops[1].op;
-  EXPECT_EQ(expected_type, second_op.type());
-  EXPECT_EQ(op_ex2_size, second_op.dst_length());
-  EXPECT_EQ(1, second_op.dst_extents().size());
-  EXPECT_TRUE(ExtentEquals(second_op.dst_extents(0), op_ex2_start_block,
-                           op_ex2_num_blocks));
-  // Obtain the expected blob.
-  chromeos::Blob second_expected_data(
-      part_data.begin() + op_ex2_offset,
-      part_data.begin() + op_ex2_offset + op_ex2_size);
-  chromeos::Blob second_expected_blob;
-  if (compressible) {
-    ASSERT_TRUE(BzipCompress(second_expected_data, &second_expected_blob));
-  } else {
-    second_expected_blob = second_expected_data;
-  }
-  EXPECT_EQ(second_expected_blob.size(), second_op.data_length());
-  // Check that the actual blob matches what's expected.
-  chromeos::Blob second_data_blob(second_op.data_length());
-  ASSERT_TRUE(utils::PReadAll(data_fd,
-                              second_data_blob.data(),
-                              second_op.data_length(),
-                              second_op.data_offset(),
-                              &bytes_read));
-  ASSERT_EQ(bytes_read, second_op.data_length());
-  EXPECT_EQ(second_expected_blob, second_data_blob);
-
-  // Check relative layout of data blobs.
-  EXPECT_EQ(first_op.data_offset() + first_op.data_length(),
-            second_op.data_offset());
-  EXPECT_EQ(second_op.data_offset() + second_op.data_length(), data_file_size);
-  // If we split a REPLACE into multiple ones, ensure reuse of preexisting blob.
-  if (!compressible &&
-      orig_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE) {
-    EXPECT_EQ(0, first_op.data_offset());
-  }
-}
-
-// Tests merging of REPLACE/REPLACE_BZ operations.
-void TestMergeReplaceOrReplaceBzOperations(
-    DeltaArchiveManifest_InstallOperation_Type orig_type,
-    bool compressible) {
-  const size_t first_op_num_blocks = 1;
-  const size_t second_op_num_blocks = 2;
-  const size_t total_op_num_blocks = first_op_num_blocks + second_op_num_blocks;
-  const size_t part_num_blocks = total_op_num_blocks + 2;
-
-  // Create the target partition data.
-  string part_path;
-  EXPECT_TRUE(utils::MakeTempFile(
-      "MergeReplaceOrReplaceBzTest_part.XXXXXX", &part_path, nullptr));
-  ScopedPathUnlinker part_path_unlinker(part_path);
-  const size_t part_size = part_num_blocks * kBlockSize;
-  chromeos::Blob part_data;
-  if (compressible) {
-    part_data.resize(part_size);
-    test_utils::FillWithData(&part_data);
-  } else {
-    std::mt19937 gen(12345);
-    std::uniform_int_distribution<uint8_t> dis(0, 255);
-    for (uint32_t i = 0; i < part_size; i++)
-      part_data.push_back(dis(gen));
-  }
-  ASSERT_EQ(part_size, part_data.size());
-  ASSERT_TRUE(utils::WriteFile(part_path.c_str(), part_data.data(), part_size));
-
-  // Create original operations and blob data.
-  vector<AnnotatedOperation> aops;
-  chromeos::Blob blob_data;
-  const size_t total_op_size = total_op_num_blocks * kBlockSize;
-
-  DeltaArchiveManifest_InstallOperation first_op;
-  first_op.set_type(orig_type);
-  const size_t first_op_size = first_op_num_blocks * kBlockSize;
-  first_op.set_dst_length(first_op_size);
-  *(first_op.add_dst_extents()) = ExtentForRange(0, first_op_num_blocks);
-  chromeos::Blob first_op_data(part_data.begin(),
-                               part_data.begin() + first_op_size);
-  chromeos::Blob first_op_blob;
-  if (orig_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE) {
-    first_op_blob = first_op_data;
-  } else {
-    ASSERT_TRUE(BzipCompress(first_op_data, &first_op_blob));
-  }
-  first_op.set_data_offset(0);
-  first_op.set_data_length(first_op_blob.size());
-  blob_data.insert(blob_data.end(), first_op_blob.begin(), first_op_blob.end());
-  AnnotatedOperation first_aop;
-  first_aop.op = first_op;
-  first_aop.name = "first";
-  aops.push_back(first_aop);
-
-  DeltaArchiveManifest_InstallOperation second_op;
-  second_op.set_type(orig_type);
-  const size_t second_op_size = second_op_num_blocks * kBlockSize;
-  second_op.set_dst_length(second_op_size);
-  *(second_op.add_dst_extents()) = ExtentForRange(first_op_num_blocks,
-                                                  second_op_num_blocks);
-  chromeos::Blob second_op_data(part_data.begin() + first_op_size,
-                                part_data.begin() + total_op_size);
-  chromeos::Blob second_op_blob;
-  if (orig_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE) {
-    second_op_blob = second_op_data;
-  } else {
-    ASSERT_TRUE(BzipCompress(second_op_data, &second_op_blob));
-  }
-  second_op.set_data_offset(first_op_blob.size());
-  second_op.set_data_length(second_op_blob.size());
-  blob_data.insert(blob_data.end(), second_op_blob.begin(),
-                   second_op_blob.end());
-  AnnotatedOperation second_aop;
-  second_aop.op = second_op;
-  second_aop.name = "second";
-  aops.push_back(second_aop);
-
-  // Create the data file.
-  string data_path;
-  EXPECT_TRUE(utils::MakeTempFile(
-      "MergeReplaceOrReplaceBzTest_data.XXXXXX", &data_path, nullptr));
-  ScopedPathUnlinker data_path_unlinker(data_path);
-  int data_fd = open(data_path.c_str(), O_RDWR, 000);
-  EXPECT_GE(data_fd, 0);
-  ScopedFdCloser data_fd_closer(&data_fd);
-  EXPECT_TRUE(utils::WriteFile(data_path.c_str(), blob_data.data(),
-                               blob_data.size()));
-  off_t data_file_size = blob_data.size();
-
-  // Merge the operations.
-  EXPECT_TRUE(DeltaDiffGenerator::MergeOperations(
-      &aops, 5 * kBlockSize, part_path, data_fd, &data_file_size));
-
-  // Check the result.
-  DeltaArchiveManifest_InstallOperation_Type expected_op_type =
-      compressible ?
-      DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ :
-      DeltaArchiveManifest_InstallOperation_Type_REPLACE;
-  EXPECT_EQ(1, aops.size());
-  DeltaArchiveManifest_InstallOperation new_op = aops[0].op;
-  EXPECT_EQ(expected_op_type, new_op.type());
-  EXPECT_FALSE(new_op.has_src_length());
-  EXPECT_EQ(total_op_num_blocks * kBlockSize, new_op.dst_length());
-  EXPECT_EQ(1, new_op.dst_extents().size());
-  EXPECT_TRUE(ExtentEquals(new_op.dst_extents(0), 0, total_op_num_blocks));
-  EXPECT_EQ("first,second", aops[0].name);
-
-  // Check to see if the blob pointed to in the new extent has what we expect.
-  chromeos::Blob expected_data(part_data.begin(),
-                               part_data.begin() + total_op_size);
-  chromeos::Blob expected_blob;
-  if (compressible) {
-    ASSERT_TRUE(BzipCompress(expected_data, &expected_blob));
-  } else {
-    expected_blob = expected_data;
-  }
-  ASSERT_EQ(expected_blob.size(), new_op.data_length());
-  ASSERT_EQ(blob_data.size() + expected_blob.size(), data_file_size);
-  chromeos::Blob new_op_blob(new_op.data_length());
-  ssize_t bytes_read;
-  ASSERT_TRUE(utils::PReadAll(data_fd,
-                              new_op_blob.data(),
-                              new_op.data_length(),
-                              new_op.data_offset(),
-                              &bytes_read));
-  ASSERT_EQ(new_op.data_length(), bytes_read);
-  EXPECT_EQ(expected_blob, new_op_blob);
-}
-
-}  // namespace
-
-class DeltaDiffGeneratorTest : public ::testing::Test {
- protected:
-  const uint64_t kFilesystemSize = kBlockSize * 1024;
-
-  void SetUp() override {
-    old_part_path_ = "DeltaDiffGeneratorTest-old_part_path-XXXXXX";
-    CreateFilesystem(&old_fs_, &old_part_path_, kFilesystemSize);
-
-    new_part_path_ = "DeltaDiffGeneratorTest-new_part_path-XXXXXX";
-    CreateFilesystem(&old_fs_, &new_part_path_, kFilesystemSize);
-  }
-
-  void TearDown() override {
-    unlink(old_part_path_.c_str());
-    unlink(new_part_path_.c_str());
-  }
-
-  // Create a fake filesystem of the given size and initialize the partition
-  // holding it.
-  void CreateFilesystem(unique_ptr<FakeFilesystem>* fs, string* filename,
-                        uint64_t size) {
-    string pattern = *filename;
-    ASSERT_TRUE(utils::MakeTempFile(pattern.c_str(), filename, nullptr));
-    ASSERT_EQ(0, truncate(filename->c_str(), size));
-    fs->reset(new FakeFilesystem(kBlockSize, size / kBlockSize));
-  }
-
-  // Paths to old and new temporary filesystems used in the tests.
-  string old_part_path_;
-  string new_part_path_;
-
-  // FilesystemInterface fake implementations used to mock out the file/block
-  // distribution.
-  unique_ptr<FakeFilesystem> old_fs_;
-  unique_ptr<FakeFilesystem> new_fs_;
-};
-
-TEST_F(DeltaDiffGeneratorTest, MoveSmallTest) {
-  chromeos::Blob data_blob(kBlockSize);
-  test_utils::FillWithData(&data_blob);
-
-  // The old file is on a different block than the new one.
-  vector<Extent> old_extents = { ExtentForRange(11, 1) };
-  vector<Extent> new_extents = { ExtentForRange(1, 1) };
-
-  EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, data_blob));
-  EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
-
-  chromeos::Blob data;
-  DeltaArchiveManifest_InstallOperation op;
-  EXPECT_TRUE(DeltaDiffGenerator::ReadExtentsToDiff(
-      old_part_path_,
-      new_part_path_,
-      old_extents,
-      new_extents,
-      true,  // bsdiff_allowed
-      &data,
-      &op,
-      false));  // src_ops_allowed
-  EXPECT_TRUE(data.empty());
-
-  EXPECT_TRUE(op.has_type());
-  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE, op.type());
-  EXPECT_FALSE(op.has_data_offset());
-  EXPECT_FALSE(op.has_data_length());
-  EXPECT_EQ(1, op.src_extents_size());
-  EXPECT_EQ(kBlockSize, op.src_length());
-  EXPECT_EQ(1, op.dst_extents_size());
-  EXPECT_EQ(kBlockSize, op.dst_length());
-  EXPECT_EQ(BlocksInExtents(op.src_extents()),
-            BlocksInExtents(op.dst_extents()));
-  EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
-}
-
-TEST_F(DeltaDiffGeneratorTest, MoveWithSameBlock) {
-  // Setup the old/new files so that it has immobile chunks; we make sure to
-  // utilize all sub-cases of such chunks: blocks 21--22 induce a split (src)
-  // and complete removal (dst), whereas blocks 24--25 induce trimming of the
-  // tail (src) and head (dst) of extents. The final block (29) is used for
-  // ensuring we properly account for the number of bytes removed in cases where
-  // the last block is partly filled. The detailed configuration:
-  //
-  // Old:  [ 20     21 22     23     24 25 ] [ 28     29 ]
-  // New:  [ 18 ] [ 21 22 ] [ 20 ] [ 24 25     26 ] [ 29 ]
-  // Same:          ^^ ^^            ^^ ^^            ^^
-  vector<Extent> old_extents = {
-      ExtentForRange(20, 6),
-      ExtentForRange(28, 2) };
-  vector<Extent> new_extents = {
-      ExtentForRange(18, 1),
-      ExtentForRange(21, 2),
-      ExtentForRange(20, 1),
-      ExtentForRange(24, 3),
-      ExtentForRange(29, 1) };
-
-  uint64_t num_blocks = BlocksInExtents(old_extents);
-  EXPECT_EQ(num_blocks, BlocksInExtents(new_extents));
-
-  // The size of the data should match the total number of blocks. Each block
-  // has a different content.
-  chromeos::Blob file_data;
-  for (uint64_t i = 0; i < num_blocks; ++i) {
-    file_data.resize(file_data.size() + kBlockSize, 'a' + i);
-  }
-
-  EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, file_data));
-  EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, file_data));
-
-  chromeos::Blob data;
-  DeltaArchiveManifest_InstallOperation op;
-  EXPECT_TRUE(DeltaDiffGenerator::ReadExtentsToDiff(
-      old_part_path_,
-      new_part_path_,
-      old_extents,
-      new_extents,
-      true,  // bsdiff_allowed
-      &data,
-      &op,
-      false));  // src_ops_allowed
-
-  EXPECT_TRUE(data.empty());
-
-  EXPECT_TRUE(op.has_type());
-  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE, op.type());
-  EXPECT_FALSE(op.has_data_offset());
-  EXPECT_FALSE(op.has_data_length());
-
-  // The expected old and new extents that actually moved. See comment above.
-  old_extents = {
-      ExtentForRange(20, 1),
-      ExtentForRange(23, 1),
-      ExtentForRange(28, 1) };
-  new_extents = {
-      ExtentForRange(18, 1),
-      ExtentForRange(20, 1),
-      ExtentForRange(26, 1) };
-  num_blocks = BlocksInExtents(old_extents);
-
-  EXPECT_EQ(num_blocks * kBlockSize, op.src_length());
-  EXPECT_EQ(num_blocks * kBlockSize, op.dst_length());
-
-  EXPECT_EQ(old_extents.size(), op.src_extents_size());
-  for (int i = 0; i < op.src_extents_size(); i++) {
-    EXPECT_EQ(old_extents[i].start_block(), op.src_extents(i).start_block())
-        << "i == " << i;
-    EXPECT_EQ(old_extents[i].num_blocks(), op.src_extents(i).num_blocks())
-        << "i == " << i;
-  }
-
-  EXPECT_EQ(new_extents.size(), op.dst_extents_size());
-  for (int i = 0; i < op.dst_extents_size(); i++) {
-    EXPECT_EQ(new_extents[i].start_block(), op.dst_extents(i).start_block())
-        << "i == " << i;
-    EXPECT_EQ(new_extents[i].num_blocks(), op.dst_extents(i).num_blocks())
-        << "i == " << i;
-  }
-}
-
-TEST_F(DeltaDiffGeneratorTest, BsdiffSmallTest) {
-  // Test a BSDIFF operation from block 1 to block 2.
-  chromeos::Blob data_blob(kBlockSize);
-  test_utils::FillWithData(&data_blob);
-
-  // The old file is on a different block than the new one.
-  vector<Extent> old_extents = { ExtentForRange(1, 1) };
-  vector<Extent> new_extents = { ExtentForRange(2, 1) };
-
-  EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, data_blob));
-  // Modify one byte in the new file.
-  data_blob[0]++;
-  EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
-
-  chromeos::Blob data;
-  DeltaArchiveManifest_InstallOperation op;
-  EXPECT_TRUE(DeltaDiffGenerator::ReadExtentsToDiff(
-      old_part_path_,
-      new_part_path_,
-      old_extents,
-      new_extents,
-      true,  // bsdiff_allowed
-      &data,
-      &op,
-      false));  // src_ops_allowed
-
-  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(kBlockSize, op.src_length());
-  EXPECT_EQ(1, op.dst_extents_size());
-  EXPECT_EQ(kBlockSize, op.dst_length());
-  EXPECT_EQ(BlocksInExtents(op.src_extents()),
-            BlocksInExtents(op.dst_extents()));
-  EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
-}
-
-TEST_F(DeltaDiffGeneratorTest, BsdiffNotAllowedTest) {
-  // Same setup as the previous test, but this time BSDIFF operations are not
-  // allowed.
-  chromeos::Blob data_blob(kBlockSize);
-  test_utils::FillWithData(&data_blob);
-
-  // The old file is on a different block than the new one.
-  vector<Extent> old_extents = { ExtentForRange(1, 1) };
-  vector<Extent> new_extents = { ExtentForRange(2, 1) };
-
-  EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, data_blob));
-  // Modify one byte in the new file.
-  data_blob[0]++;
-  EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
-
-  chromeos::Blob data;
-  DeltaArchiveManifest_InstallOperation op;
-  EXPECT_TRUE(DeltaDiffGenerator::ReadExtentsToDiff(
-      old_part_path_,
-      new_part_path_,
-      old_extents,
-      new_extents,
-      false,  // bsdiff_allowed
-      &data,
-      &op,
-      false));  // src_ops_allowed
-
-  EXPECT_FALSE(data.empty());
-
-  // The point of this test is that we don't use BSDIFF the way the above
-  // did. The rest of the details are to be caught in other tests.
-  EXPECT_TRUE(op.has_type());
-  EXPECT_NE(DeltaArchiveManifest_InstallOperation_Type_BSDIFF, op.type());
-}
-
-TEST_F(DeltaDiffGeneratorTest, BsdiffNotAllowedMoveTest) {
-  chromeos::Blob data_blob(kBlockSize);
-  test_utils::FillWithData(&data_blob);
-
-  // The old file is on a different block than the new one.
-  vector<Extent> old_extents = { ExtentForRange(1, 1) };
-  vector<Extent> new_extents = { ExtentForRange(2, 1) };
-
-  EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, data_blob));
-  EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
-
-  chromeos::Blob data;
-  DeltaArchiveManifest_InstallOperation op;
-  EXPECT_TRUE(DeltaDiffGenerator::ReadExtentsToDiff(
-      old_part_path_,
-      new_part_path_,
-      old_extents,
-      new_extents,
-      false,  // bsdiff_allowed
-      &data,
-      &op,
-      false));  // src_ops_allowed
-
-  EXPECT_TRUE(data.empty());
-
-  // The point of this test is that we can still use a MOVE for a file
-  // that is blacklisted.
-  EXPECT_TRUE(op.has_type());
-  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE, op.type());
-}
-
-TEST_F(DeltaDiffGeneratorTest, ReplaceSmallTest) {
-  // The old file is on a different block than the new one.
-  vector<Extent> old_extents = { ExtentForRange(1, 1) };
-  vector<Extent> new_extents = { ExtentForRange(2, 1) };
-
-  // Make a blob that's just 1's that will compress well.
-  chromeos::Blob ones(kBlockSize, 1);
-
-  // Make a blob with random data that won't compress well.
-  chromeos::Blob random_data;
-  std::mt19937 gen(12345);
-  std::uniform_int_distribution<uint8_t> dis(0, 255);
-  for (uint32_t i = 0; i < kBlockSize; i++) {
-    random_data.push_back(dis(gen));
-  }
-
-  for (int i = 0; i < 2; i++) {
-    chromeos::Blob data_to_test = i == 0 ? random_data : ones;
-    // The old_extents will be initialized with 0.
-    EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize,
-                             data_to_test));
-
-    chromeos::Blob data;
-    DeltaArchiveManifest_InstallOperation op;
-    EXPECT_TRUE(DeltaDiffGenerator::ReadExtentsToDiff(
-        old_part_path_,
-        new_part_path_,
-        old_extents,
-        new_extents,
-        true,  // bsdiff_allowed
-        &data,
-        &op,
-        false));  // src_ops_allowed
-    EXPECT_FALSE(data.empty());
-
-    EXPECT_TRUE(op.has_type());
-    const DeltaArchiveManifest_InstallOperation_Type expected_type =
-        (i == 0 ? DeltaArchiveManifest_InstallOperation_Type_REPLACE :
-         DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
-    EXPECT_EQ(expected_type, op.type());
-    EXPECT_FALSE(op.has_data_offset());
-    EXPECT_FALSE(op.has_data_length());
-    EXPECT_EQ(0, op.src_extents_size());
-    EXPECT_FALSE(op.has_src_length());
-    EXPECT_EQ(1, op.dst_extents_size());
-    EXPECT_EQ(data_to_test.size(), op.dst_length());
-    EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
-  }
-}
-
-TEST_F(DeltaDiffGeneratorTest, SourceCopyTest) {
-  // Makes sure SOURCE_COPY operations are emitted whenever src_ops_allowed
-  // is true. It is the same setup as MoveSmallTest, which checks that
-  // the operation is well-formed.
-  chromeos::Blob data_blob(kBlockSize);
-  test_utils::FillWithData(&data_blob);
-
-  // The old file is on a different block than the new one.
-  vector<Extent> old_extents = { ExtentForRange(11, 1) };
-  vector<Extent> new_extents = { ExtentForRange(1, 1) };
-
-  EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, data_blob));
-  EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
-
-  chromeos::Blob data;
-  DeltaArchiveManifest_InstallOperation op;
-  EXPECT_TRUE(DeltaDiffGenerator::ReadExtentsToDiff(
-      old_part_path_,
-      new_part_path_,
-      old_extents,
-      new_extents,
-      true,  // bsdiff_allowed
-      &data,
-      &op,
-      true));  // src_ops_allowed
-  EXPECT_TRUE(data.empty());
-
-  EXPECT_TRUE(op.has_type());
-  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY, op.type());
-}
-
-TEST_F(DeltaDiffGeneratorTest, SourceBsdiffTest) {
-  // Makes sure SOURCE_BSDIFF operations are emitted whenever src_ops_allowed
-  // is true. It is the same setup as BsdiffSmallTest, which checks
-  // that the operation is well-formed.
-  chromeos::Blob data_blob(kBlockSize);
-  test_utils::FillWithData(&data_blob);
-
-  // The old file is on a different block than the new one.
-  vector<Extent> old_extents = { ExtentForRange(1, 1) };
-  vector<Extent> new_extents = { ExtentForRange(2, 1) };
-
-  EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, data_blob));
-  // Modify one byte in the new file.
-  data_blob[0]++;
-  EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
-
-  chromeos::Blob data;
-  DeltaArchiveManifest_InstallOperation op;
-  EXPECT_TRUE(DeltaDiffGenerator::ReadExtentsToDiff(
-      old_part_path_,
-      new_part_path_,
-      old_extents,
-      new_extents,
-      true,  // bsdiff_allowed
-      &data,
-      &op,
-      true));  // src_ops_allowed
-
-  EXPECT_FALSE(data.empty());
-  EXPECT_TRUE(op.has_type());
-  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_BSDIFF,
-            op.type());
-}
-
-TEST_F(DeltaDiffGeneratorTest, ReorderBlobsTest) {
-  string orig_blobs;
-  EXPECT_TRUE(utils::MakeTempFile("ReorderBlobsTest.orig.XXXXXX", &orig_blobs,
-                                  nullptr));
-  ScopedPathUnlinker orig_blobs_unlinker(orig_blobs);
-
-  string orig_data = "abcd";
-  EXPECT_TRUE(
-      utils::WriteFile(orig_blobs.c_str(), orig_data.data(), orig_data.size()));
-
-  string new_blobs;
-  EXPECT_TRUE(
-      utils::MakeTempFile("ReorderBlobsTest.new.XXXXXX", &new_blobs, nullptr));
-  ScopedPathUnlinker new_blobs_unlinker(new_blobs);
-
-  DeltaArchiveManifest manifest;
-  DeltaArchiveManifest_InstallOperation* op =
-      manifest.add_install_operations();
-  op->set_data_offset(1);
-  op->set_data_length(3);
-  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::ReadFile(new_blobs, &new_data));
-  EXPECT_EQ("bcda", new_data);
-  EXPECT_EQ(2, manifest.install_operations_size());
-  EXPECT_EQ(0, manifest.install_operations(0).data_offset());
-  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());
-}
-
-TEST_F(DeltaDiffGeneratorTest, IsNoopOperationTest) {
-  DeltaArchiveManifest_InstallOperation op;
-  op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
-  EXPECT_FALSE(DeltaDiffGenerator::IsNoopOperation(op));
-  op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
-  EXPECT_TRUE(DeltaDiffGenerator::IsNoopOperation(op));
-  *(op.add_src_extents()) = ExtentForRange(3, 2);
-  *(op.add_dst_extents()) = ExtentForRange(3, 2);
-  EXPECT_TRUE(DeltaDiffGenerator::IsNoopOperation(op));
-  *(op.add_src_extents()) = ExtentForRange(7, 5);
-  *(op.add_dst_extents()) = ExtentForRange(7, 5);
-  EXPECT_TRUE(DeltaDiffGenerator::IsNoopOperation(op));
-  *(op.add_src_extents()) = ExtentForRange(20, 2);
-  *(op.add_dst_extents()) = ExtentForRange(20, 1);
-  *(op.add_dst_extents()) = ExtentForRange(21, 1);
-  EXPECT_TRUE(DeltaDiffGenerator::IsNoopOperation(op));
-  *(op.add_src_extents()) = ExtentForRange(24, 1);
-  *(op.add_dst_extents()) = ExtentForRange(25, 1);
-  EXPECT_FALSE(DeltaDiffGenerator::IsNoopOperation(op));
-}
-
-TEST_F(DeltaDiffGeneratorTest, FilterNoopOperations) {
-  AnnotatedOperation aop1;
-  aop1.op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
-  *(aop1.op.add_dst_extents()) = ExtentForRange(3, 2);
-  aop1.name = "aop1";
-
-  AnnotatedOperation aop2 = aop1;
-  aop2.name = "aop2";
-
-  AnnotatedOperation noop;
-  noop.op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
-  *(noop.op.add_src_extents()) = ExtentForRange(3, 2);
-  *(noop.op.add_dst_extents()) = ExtentForRange(3, 2);
-  noop.name = "noop";
-
-  vector<AnnotatedOperation> ops = {noop, aop1, noop, noop, aop2, noop};
-  DeltaDiffGenerator::FilterNoopOperations(&ops);
-  EXPECT_EQ(2u, ops.size());
-  EXPECT_EQ("aop1", ops[0].name);
-  EXPECT_EQ("aop2", ops[1].name);
-}
-
-TEST_F(DeltaDiffGeneratorTest, SplitSourceCopyTest) {
-  DeltaArchiveManifest_InstallOperation op;
-  op.set_type(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
-  *(op.add_src_extents()) = ExtentForRange(2, 3);
-  *(op.add_src_extents()) = ExtentForRange(6, 1);
-  *(op.add_src_extents()) = ExtentForRange(8, 4);
-  *(op.add_dst_extents()) = ExtentForRange(10, 2);
-  *(op.add_dst_extents()) = ExtentForRange(14, 3);
-  *(op.add_dst_extents()) = ExtentForRange(18, 3);
-
-  AnnotatedOperation aop;
-  aop.op = op;
-  aop.name = "SplitSourceCopyTestOp";
-  vector<AnnotatedOperation> result_ops;
-  EXPECT_TRUE(DeltaDiffGenerator::SplitSourceCopy(aop, &result_ops));
-  EXPECT_EQ(result_ops.size(), 3);
-
-  EXPECT_EQ("SplitSourceCopyTestOp:0", result_ops[0].name);
-  DeltaArchiveManifest_InstallOperation first_op = result_ops[0].op;
-  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY,
-            first_op.type());
-  EXPECT_EQ(kBlockSize * 2, first_op.src_length());
-  EXPECT_EQ(1, first_op.src_extents().size());
-  EXPECT_EQ(2, first_op.src_extents(0).start_block());
-  EXPECT_EQ(2, first_op.src_extents(0).num_blocks());
-  EXPECT_EQ(kBlockSize * 2, first_op.dst_length());
-  EXPECT_EQ(1, first_op.dst_extents().size());
-  EXPECT_EQ(10, first_op.dst_extents(0).start_block());
-  EXPECT_EQ(2, first_op.dst_extents(0).num_blocks());
-
-  EXPECT_EQ("SplitSourceCopyTestOp:1", result_ops[1].name);
-  DeltaArchiveManifest_InstallOperation second_op = result_ops[1].op;
-  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY,
-            second_op.type());
-  EXPECT_EQ(kBlockSize * 3, second_op.src_length());
-  EXPECT_EQ(3, second_op.src_extents().size());
-  EXPECT_EQ(4, second_op.src_extents(0).start_block());
-  EXPECT_EQ(1, second_op.src_extents(0).num_blocks());
-  EXPECT_EQ(6, second_op.src_extents(1).start_block());
-  EXPECT_EQ(1, second_op.src_extents(1).num_blocks());
-  EXPECT_EQ(8, second_op.src_extents(2).start_block());
-  EXPECT_EQ(1, second_op.src_extents(2).num_blocks());
-  EXPECT_EQ(kBlockSize * 3, second_op.dst_length());
-  EXPECT_EQ(1, second_op.dst_extents().size());
-  EXPECT_EQ(14, second_op.dst_extents(0).start_block());
-  EXPECT_EQ(3, second_op.dst_extents(0).num_blocks());
-
-  EXPECT_EQ("SplitSourceCopyTestOp:2", result_ops[2].name);
-  DeltaArchiveManifest_InstallOperation third_op = result_ops[2].op;
-  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY,
-            third_op.type());
-  EXPECT_EQ(kBlockSize * 3, third_op.src_length());
-  EXPECT_EQ(1, third_op.src_extents().size());
-  EXPECT_EQ(9, third_op.src_extents(0).start_block());
-  EXPECT_EQ(3, third_op.src_extents(0).num_blocks());
-  EXPECT_EQ(kBlockSize * 3, third_op.dst_length());
-  EXPECT_EQ(1, third_op.dst_extents().size());
-  EXPECT_EQ(18, third_op.dst_extents(0).start_block());
-  EXPECT_EQ(3, third_op.dst_extents(0).num_blocks());
-}
-
-TEST_F(DeltaDiffGeneratorTest, SplitReplaceTest) {
-  TestSplitReplaceOrReplaceBzOperation(
-      DeltaArchiveManifest_InstallOperation_Type_REPLACE, false);
-}
-
-TEST_F(DeltaDiffGeneratorTest, SplitReplaceIntoReplaceBzTest) {
-  TestSplitReplaceOrReplaceBzOperation(
-      DeltaArchiveManifest_InstallOperation_Type_REPLACE, true);
-}
-
-TEST_F(DeltaDiffGeneratorTest, SplitReplaceBzTest) {
-  TestSplitReplaceOrReplaceBzOperation(
-      DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ, true);
-}
-
-TEST_F(DeltaDiffGeneratorTest, SplitReplaceBzIntoReplaceTest) {
-  TestSplitReplaceOrReplaceBzOperation(
-      DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ, false);
-}
-
-TEST_F(DeltaDiffGeneratorTest, SortOperationsByDestinationTest) {
-  vector<AnnotatedOperation> aops;
-  // One operation with multiple destination extents.
-  DeltaArchiveManifest_InstallOperation first_op;
-  *(first_op.add_dst_extents()) = ExtentForRange(6, 1);
-  *(first_op.add_dst_extents()) = ExtentForRange(10, 2);
-  AnnotatedOperation first_aop;
-  first_aop.op = first_op;
-  first_aop.name = "first";
-  aops.push_back(first_aop);
-
-  // One with no destination extent. Should end up at the end of the vector.
-  DeltaArchiveManifest_InstallOperation second_op;
-  AnnotatedOperation second_aop;
-  second_aop.op = second_op;
-  second_aop.name = "second";
-  aops.push_back(second_aop);
-
-  // One with one destination extent.
-  DeltaArchiveManifest_InstallOperation third_op;
-  *(third_op.add_dst_extents()) = ExtentForRange(3, 2);
-  AnnotatedOperation third_aop;
-  third_aop.op = third_op;
-  third_aop.name = "third";
-  aops.push_back(third_aop);
-
-  DeltaDiffGenerator::SortOperationsByDestination(&aops);
-  EXPECT_EQ(aops.size(), 3);
-  EXPECT_EQ(third_aop.name, aops[0].name);
-  EXPECT_EQ(first_aop.name, aops[1].name);
-  EXPECT_EQ(second_aop.name, aops[2].name);
-}
-
-TEST_F(DeltaDiffGeneratorTest, MergeSourceCopyOperationsTest) {
-  vector<AnnotatedOperation> aops;
-  DeltaArchiveManifest_InstallOperation first_op;
-  first_op.set_type(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
-  first_op.set_src_length(kBlockSize);
-  first_op.set_dst_length(kBlockSize);
-  *(first_op.add_src_extents()) = ExtentForRange(1, 1);
-  *(first_op.add_dst_extents()) = ExtentForRange(6, 1);
-  AnnotatedOperation first_aop;
-  first_aop.op = first_op;
-  first_aop.name = "1";
-  aops.push_back(first_aop);
-
-  DeltaArchiveManifest_InstallOperation second_op;
-  second_op.set_type(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
-  second_op.set_src_length(3 * kBlockSize);
-  second_op.set_dst_length(3 * kBlockSize);
-  *(second_op.add_src_extents()) = ExtentForRange(2, 2);
-  *(second_op.add_src_extents()) = ExtentForRange(8, 2);
-  *(second_op.add_dst_extents()) = ExtentForRange(7, 3);
-  *(second_op.add_dst_extents()) = ExtentForRange(11, 1);
-  AnnotatedOperation second_aop;
-  second_aop.op = second_op;
-  second_aop.name = "2";
-  aops.push_back(second_aop);
-
-  DeltaArchiveManifest_InstallOperation third_op;
-  third_op.set_type(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
-  third_op.set_src_length(kBlockSize);
-  third_op.set_dst_length(kBlockSize);
-  *(third_op.add_src_extents()) = ExtentForRange(11, 1);
-  *(third_op.add_dst_extents()) = ExtentForRange(12, 1);
-  AnnotatedOperation third_aop;
-  third_aop.op = third_op;
-  third_aop.name = "3";
-  aops.push_back(third_aop);
-
-  EXPECT_TRUE(DeltaDiffGenerator::MergeOperations(
-      &aops, 5 * kBlockSize, "", 0, nullptr));
-
-  EXPECT_EQ(aops.size(), 1);
-  DeltaArchiveManifest_InstallOperation first_result_op = aops[0].op;
-  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY,
-            first_result_op.type());
-  EXPECT_EQ(kBlockSize * 5, first_result_op.src_length());
-  EXPECT_EQ(3, first_result_op.src_extents().size());
-  EXPECT_TRUE(ExtentEquals(first_result_op.src_extents(0), 1, 3));
-  EXPECT_TRUE(ExtentEquals(first_result_op.src_extents(1), 8, 2));
-  EXPECT_TRUE(ExtentEquals(first_result_op.src_extents(2), 11, 1));
-  EXPECT_EQ(kBlockSize * 5, first_result_op.dst_length());
-  EXPECT_EQ(2, first_result_op.dst_extents().size());
-  EXPECT_TRUE(ExtentEquals(first_result_op.dst_extents(0), 6, 4));
-  EXPECT_TRUE(ExtentEquals(first_result_op.dst_extents(1), 11, 2));
-  EXPECT_EQ(aops[0].name, "1,2,3");
-}
-
-TEST_F(DeltaDiffGeneratorTest, MergeReplaceOperationsTest) {
-  TestMergeReplaceOrReplaceBzOperations(
-      DeltaArchiveManifest_InstallOperation_Type_REPLACE, false);
-}
-
-TEST_F(DeltaDiffGeneratorTest, MergeReplaceOperationsToReplaceBzTest) {
-  TestMergeReplaceOrReplaceBzOperations(
-      DeltaArchiveManifest_InstallOperation_Type_REPLACE, true);
-}
-
-TEST_F(DeltaDiffGeneratorTest, MergeReplaceBzOperationsTest) {
-  TestMergeReplaceOrReplaceBzOperations(
-      DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ, true);
-}
-
-TEST_F(DeltaDiffGeneratorTest, MergeReplaceBzOperationsToReplaceTest) {
-  TestMergeReplaceOrReplaceBzOperations(
-      DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ, false);
-}
-
-TEST_F(DeltaDiffGeneratorTest, NoMergeOperationsTest) {
-  // Test to make sure we don't merge operations that shouldn't be merged.
-  vector<AnnotatedOperation> aops;
-  DeltaArchiveManifest_InstallOperation first_op;
-  first_op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
-  *(first_op.add_dst_extents()) = ExtentForRange(0, 1);
-  first_op.set_data_length(kBlockSize);
-  AnnotatedOperation first_aop;
-  first_aop.op = first_op;
-  aops.push_back(first_aop);
-
-  // Should merge with first, except op types don't match...
-  DeltaArchiveManifest_InstallOperation second_op;
-  second_op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
-  *(second_op.add_dst_extents()) = ExtentForRange(1, 2);
-  second_op.set_data_length(2 * kBlockSize);
-  AnnotatedOperation second_aop;
-  second_aop.op = second_op;
-  aops.push_back(second_aop);
-
-  // Should merge with second, except it would exceed chunk size...
-  DeltaArchiveManifest_InstallOperation third_op;
-  third_op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
-  *(third_op.add_dst_extents()) = ExtentForRange(3, 3);
-  third_op.set_data_length(3 * kBlockSize);
-  AnnotatedOperation third_aop;
-  third_aop.op = third_op;
-  aops.push_back(third_aop);
-
-  // Should merge with third, except they aren't contiguous...
-  DeltaArchiveManifest_InstallOperation fourth_op;
-  fourth_op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
-  *(fourth_op.add_dst_extents()) = ExtentForRange(7, 2);
-  fourth_op.set_data_length(2 * kBlockSize);
-  AnnotatedOperation fourth_aop;
-  fourth_aop.op = fourth_op;
-  aops.push_back(fourth_aop);
-
-  EXPECT_TRUE(DeltaDiffGenerator::MergeOperations(&aops, 4 * kBlockSize,
-                                                  "", 0, nullptr));
-
-  // No operations were merged, the number of ops is the same.
-  EXPECT_EQ(aops.size(), 4);
-}
-
-TEST_F(DeltaDiffGeneratorTest, ExtendExtentsTest) {
-  DeltaArchiveManifest_InstallOperation first_op;
-  *(first_op.add_src_extents()) = ExtentForRange(1, 1);
-  *(first_op.add_src_extents()) = ExtentForRange(3, 1);
-
-  DeltaArchiveManifest_InstallOperation second_op;
-  *(second_op.add_src_extents()) = ExtentForRange(4, 2);
-  *(second_op.add_src_extents()) = ExtentForRange(8, 2);
-
-  DeltaDiffGenerator::ExtendExtents(first_op.mutable_src_extents(),
-                                    second_op.src_extents());
-  EXPECT_EQ(first_op.src_extents_size(), 3);
-  EXPECT_TRUE(ExtentEquals(first_op.src_extents(0), 1, 1));
-  EXPECT_TRUE(ExtentEquals(first_op.src_extents(1), 3, 3));
-  EXPECT_TRUE(ExtentEquals(first_op.src_extents(2), 8, 2));
-}
-
-}  // namespace chromeos_update_engine
diff --git a/payload_generator/delta_diff_utils.cc b/payload_generator/delta_diff_utils.cc
new file mode 100644
index 0000000..d53c5e0
--- /dev/null
+++ b/payload_generator/delta_diff_utils.cc
@@ -0,0 +1,556 @@
+// Copyright 2015 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.
+
+#include "update_engine/payload_generator/delta_diff_utils.h"
+
+#include <algorithm>
+#include <map>
+
+#include <base/files/file_util.h>
+#include <base/format_macros.h>
+#include <base/strings/stringprintf.h>
+
+#include "update_engine/bzip.h"
+#include "update_engine/omaha_hash_calculator.h"
+#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/extent_ranges.h"
+#include "update_engine/payload_generator/extent_utils.h"
+#include "update_engine/payload_generator/raw_filesystem.h"
+#include "update_engine/subprocess.h"
+#include "update_engine/utils.h"
+
+using std::map;
+using std::string;
+using std::unique_ptr;
+using std::vector;
+
+namespace chromeos_update_engine {
+namespace {
+
+const char* const kBsdiffPath = "bsdiff";
+
+// The maximum destination size allowed for bsdiff. In general, bsdiff should
+// work for arbitrary big files, but the payload generation and payload
+// application requires a significant amount of RAM. We put a hard-limit of
+// 200 MiB that should not affect any released board, but will limit the
+// Chrome binary in ASan builders.
+const uint64_t kMaxBsdiffDestinationSize = 200 * 1024 * 1024;  // bytes
+
+// Process a range of blocks from |range_start| to |range_end| in the extent at
+// position |*idx_p| of |extents|. If |do_remove| is true, this range will be
+// removed, which may cause the extent to be trimmed, split or removed entirely.
+// The value of |*idx_p| is updated to point to the next extent to be processed.
+// Returns true iff the next extent to process is a new or updated one.
+bool ProcessExtentBlockRange(vector<Extent>* extents, size_t* idx_p,
+                             const bool do_remove, uint64_t range_start,
+                             uint64_t range_end) {
+  size_t idx = *idx_p;
+  uint64_t start_block = (*extents)[idx].start_block();
+  uint64_t num_blocks = (*extents)[idx].num_blocks();
+  uint64_t range_size = range_end - range_start;
+
+  if (do_remove) {
+    if (range_size == num_blocks) {
+      // Remove the entire extent.
+      extents->erase(extents->begin() + idx);
+    } else if (range_end == num_blocks) {
+      // Trim the end of the extent.
+      (*extents)[idx].set_num_blocks(num_blocks - range_size);
+      idx++;
+    } else if (range_start == 0) {
+      // Trim the head of the extent.
+      (*extents)[idx].set_start_block(start_block + range_size);
+      (*extents)[idx].set_num_blocks(num_blocks - range_size);
+    } else {
+      // Trim the middle, splitting the remainder into two parts.
+      (*extents)[idx].set_num_blocks(range_start);
+      Extent e;
+      e.set_start_block(start_block + range_end);
+      e.set_num_blocks(num_blocks - range_end);
+      idx++;
+      extents->insert(extents->begin() + idx, e);
+    }
+  } else if (range_end == num_blocks) {
+    // Done with this extent.
+    idx++;
+  } else {
+    return false;
+  }
+
+  *idx_p = idx;
+  return true;
+}
+
+// Remove identical corresponding block ranges in |src_extents| and
+// |dst_extents|. Used for preventing moving of blocks onto themselves during
+// MOVE operations. The value of |total_bytes| indicates the actual length of
+// content; this may be slightly less than the total size of blocks, in which
+// case the last block is only partly occupied with data. Returns the total
+// number of bytes removed.
+size_t RemoveIdenticalBlockRanges(vector<Extent>* src_extents,
+                                  vector<Extent>* dst_extents,
+                                  const size_t total_bytes) {
+  size_t src_idx = 0;
+  size_t dst_idx = 0;
+  uint64_t src_offset = 0, dst_offset = 0;
+  bool new_src = true, new_dst = true;
+  size_t removed_bytes = 0, nonfull_block_bytes;
+  bool do_remove = false;
+  while (src_idx < src_extents->size() && dst_idx < dst_extents->size()) {
+    if (new_src) {
+      src_offset = 0;
+      new_src = false;
+    }
+    if (new_dst) {
+      dst_offset = 0;
+      new_dst = false;
+    }
+
+    do_remove = ((*src_extents)[src_idx].start_block() + src_offset ==
+                 (*dst_extents)[dst_idx].start_block() + dst_offset);
+
+    uint64_t src_num_blocks = (*src_extents)[src_idx].num_blocks();
+    uint64_t dst_num_blocks = (*dst_extents)[dst_idx].num_blocks();
+    uint64_t min_num_blocks = std::min(src_num_blocks - src_offset,
+                                       dst_num_blocks - dst_offset);
+    uint64_t prev_src_offset = src_offset;
+    uint64_t prev_dst_offset = dst_offset;
+    src_offset += min_num_blocks;
+    dst_offset += min_num_blocks;
+
+    new_src = ProcessExtentBlockRange(src_extents, &src_idx, do_remove,
+                                      prev_src_offset, src_offset);
+    new_dst = ProcessExtentBlockRange(dst_extents, &dst_idx, do_remove,
+                                      prev_dst_offset, dst_offset);
+    if (do_remove)
+      removed_bytes += min_num_blocks * kBlockSize;
+  }
+
+  // If we removed the last block and this block is only partly used by file
+  // content, deduct the unused portion from the total removed byte count.
+  if (do_remove && (nonfull_block_bytes = total_bytes % kBlockSize))
+    removed_bytes -= kBlockSize - nonfull_block_bytes;
+
+  return removed_bytes;
+}
+
+}  // namespace
+
+namespace diff_utils {
+
+bool DeltaReadFilesystem(
+    vector<AnnotatedOperation>* aops,
+    const string& old_part,
+    const string& new_part,
+    FilesystemInterface* old_fs,
+    FilesystemInterface* new_fs,
+    off_t chunk_blocks,
+    int data_fd,
+    off_t* data_file_size,
+    bool skip_block_0,
+    bool src_ops_allowed) {
+  ExtentRanges old_visited_blocks;
+  ExtentRanges new_visited_blocks;
+
+  // We can't produce a MOVE operation with a 0 block as neither source nor
+  // destination, so we avoid generating an operation for the block 0 here, and
+  // we will add an operation for it in the InplaceGenerator. Excluding both
+  // old and new blocks ensures that identical images would still produce empty
+  // deltas.
+  if (skip_block_0) {
+    old_visited_blocks.AddBlock(0);
+    new_visited_blocks.AddBlock(0);
+  }
+
+  map<string, vector<Extent>> old_files_map;
+  if (old_fs) {
+    vector<FilesystemInterface::File> old_files;
+    old_fs->GetFiles(&old_files);
+    for (const FilesystemInterface::File& file : old_files)
+      old_files_map[file.name] = file.extents;
+  }
+
+  vector<FilesystemInterface::File> new_files;
+  new_fs->GetFiles(&new_files);
+
+  // The processing is very straightforward here, we generate operations for
+  // every file (and pseudo-file such as the metadata) in the new filesystem
+  // based on the file with the same name in the old filesystem, if any.
+  // Files with overlapping data blocks (like hardlinks or filesystems with tail
+  // packing or compression where the blocks store more than one file) are only
+  // generated once in the new image, but are also used only once from the old
+  // image due to some simplifications (see below).
+  for (const FilesystemInterface::File& new_file : new_files) {
+    // Ignore the files in the new filesystem without blocks. Symlinks with
+    // data blocks (for example, symlinks bigger than 60 bytes in ext2) are
+    // handled as normal files. We also ignore blocks that were already
+    // processed by a previous file.
+    vector<Extent> new_file_extents = FilterExtentRanges(
+        new_file.extents, new_visited_blocks);
+    new_visited_blocks.AddExtents(new_file_extents);
+
+    if (new_file_extents.empty())
+      continue;
+
+    LOG(INFO) << "Encoding file " << new_file.name << " ("
+              << BlocksInExtents(new_file_extents) << " blocks)";
+
+    // We can't visit each dst image inode more than once, as that would
+    // duplicate work. Here, we avoid visiting each source image inode
+    // more than once. Technically, we could have multiple operations
+    // that read the same blocks from the source image for diffing, but
+    // we choose not to avoid complexity. Eventually we will move away
+    // from using a graph/cycle detection/etc to generate diffs, and at that
+    // time, it will be easy (non-complex) to have many operations read
+    // from the same source blocks. At that time, this code can die. -adlr
+    vector<Extent> old_file_extents = FilterExtentRanges(
+        old_files_map[new_file.name], old_visited_blocks);
+    old_visited_blocks.AddExtents(old_file_extents);
+
+    TEST_AND_RETURN_FALSE(DeltaReadFile(
+        aops,
+        old_part,
+        new_part,
+        old_file_extents,
+        new_file_extents,
+        new_file.name,  // operation name
+        chunk_blocks,
+        data_fd,
+        data_file_size,
+        src_ops_allowed));
+  }
+  // Process all the blocks not included in any file. We provided all the unused
+  // blocks in the old partition as available data.
+  vector<Extent> new_unvisited = { ExtentForRange(0, new_fs->GetBlockCount()) };
+  new_unvisited = FilterExtentRanges(new_unvisited, new_visited_blocks);
+  if (new_unvisited.empty())
+    return true;
+
+  vector<Extent> old_unvisited;
+  if (old_fs) {
+    old_unvisited.push_back(ExtentForRange(0, old_fs->GetBlockCount()));
+    old_unvisited = FilterExtentRanges(old_unvisited, old_visited_blocks);
+  }
+
+  LOG(INFO) << "Scanning " << BlocksInExtents(new_unvisited)
+            << " unwritten blocks";
+  TEST_AND_RETURN_FALSE(DeltaReadFile(
+      aops,
+      old_part,
+      new_part,
+      old_unvisited,
+      new_unvisited,
+      "<non-file-data>",  // operation name
+      chunk_blocks,
+      data_fd,
+      data_file_size,
+      src_ops_allowed));
+
+  return true;
+}
+
+bool DeltaReadFile(
+    vector<AnnotatedOperation>* aops,
+    const string& old_part,
+    const string& new_part,
+    const vector<Extent>& old_extents,
+    const vector<Extent>& new_extents,
+    const string& name,
+    off_t chunk_blocks,
+    int data_fd,
+    off_t* data_file_size,
+    bool src_ops_allowed) {
+  chromeos::Blob data;
+  DeltaArchiveManifest_InstallOperation operation;
+
+  uint64_t total_blocks = BlocksInExtents(new_extents);
+  if (chunk_blocks == -1)
+    chunk_blocks = total_blocks;
+
+  // If bsdiff breaks again, blacklist the problem file by using:
+  //   bsdiff_allowed = (name != "/foo/bar")
+  //
+  // TODO(dgarrett): chromium-os:15274 connect this test to the command line.
+  bool bsdiff_allowed = true;
+  if (static_cast<uint64_t>(chunk_blocks) * kBlockSize >
+      kMaxBsdiffDestinationSize) {
+    bsdiff_allowed = false;
+  }
+
+  if (!bsdiff_allowed) {
+    LOG(INFO) << "bsdiff blacklisting: " << name;
+  }
+
+  for (uint64_t block_offset = 0; block_offset < total_blocks;
+      block_offset += chunk_blocks) {
+    // Split the old/new file in the same chunks. Note that this could drop
+    // some information from the old file used for the new chunk. If the old
+    // file is smaller (or even empty when there's no old file) the chunk will
+    // also be empty.
+    vector<Extent> old_extents_chunk = ExtentsSublist(
+        old_extents, block_offset, chunk_blocks);
+    vector<Extent> new_extents_chunk = ExtentsSublist(
+        new_extents, block_offset, chunk_blocks);
+    NormalizeExtents(&old_extents_chunk);
+    NormalizeExtents(&new_extents_chunk);
+
+    TEST_AND_RETURN_FALSE(ReadExtentsToDiff(old_part,
+                                            new_part,
+                                            old_extents_chunk,
+                                            new_extents_chunk,
+                                            bsdiff_allowed,
+                                            &data,
+                                            &operation,
+                                            src_ops_allowed));
+
+    // Check if the operation writes nothing.
+    if (operation.dst_extents_size() == 0) {
+      if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE) {
+        LOG(INFO) << "Empty MOVE operation ("
+                  << name << "), skipping";
+        continue;
+      } else {
+        LOG(ERROR) << "Empty non-MOVE operation";
+        return false;
+      }
+    }
+
+    // Write the data
+    if (operation.type() != DeltaArchiveManifest_InstallOperation_Type_MOVE &&
+        operation.type() !=
+            DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY) {
+      operation.set_data_offset(*data_file_size);
+      operation.set_data_length(data.size());
+    }
+
+    TEST_AND_RETURN_FALSE(utils::WriteAll(data_fd, data.data(), data.size()));
+    *data_file_size += data.size();
+
+    // Now, insert into the list of operations.
+    AnnotatedOperation aop;
+    aop.name = name;
+    if (static_cast<uint64_t>(chunk_blocks) < total_blocks) {
+      aop.name = base::StringPrintf("%s:%" PRIu64,
+                                    name.c_str(), block_offset / chunk_blocks);
+    }
+    aop.op = operation;
+    aops->emplace_back(aop);
+  }
+  return true;
+}
+
+bool ReadExtentsToDiff(const string& old_part,
+                       const string& new_part,
+                       const vector<Extent>& old_extents,
+                       const vector<Extent>& new_extents,
+                       bool bsdiff_allowed,
+                       chromeos::Blob* out_data,
+                       DeltaArchiveManifest_InstallOperation* out_op,
+                       bool src_ops_allowed) {
+  DeltaArchiveManifest_InstallOperation operation;
+  // Data blob that will be written to delta file.
+  const chromeos::Blob* data_blob = nullptr;
+
+  // We read blocks from old_extents and write blocks to new_extents.
+  uint64_t blocks_to_read = BlocksInExtents(old_extents);
+  uint64_t blocks_to_write = BlocksInExtents(new_extents);
+
+  // Make copies of the extents so we can modify them.
+  vector<Extent> src_extents = old_extents;
+  vector<Extent> dst_extents = new_extents;
+
+  // Read in bytes from new data.
+  chromeos::Blob new_data;
+  TEST_AND_RETURN_FALSE(utils::ReadExtents(new_part,
+                                           new_extents,
+                                           &new_data,
+                                           kBlockSize * blocks_to_write,
+                                           kBlockSize));
+  TEST_AND_RETURN_FALSE(!new_data.empty());
+
+
+  // Using a REPLACE is always an option.
+  operation.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+  data_blob = &new_data;
+
+  // Try compressing it with bzip2.
+  chromeos::Blob new_data_bz;
+  TEST_AND_RETURN_FALSE(BzipCompress(new_data, &new_data_bz));
+  CHECK(!new_data_bz.empty());
+  if (new_data_bz.size() < data_blob->size()) {
+    // A REPLACE_BZ is better.
+    operation.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+    data_blob = &new_data_bz;
+  }
+
+  chromeos::Blob old_data;
+  chromeos::Blob empty_blob;
+  chromeos::Blob bsdiff_delta;
+  if (blocks_to_read > 0) {
+    // Read old data.
+    TEST_AND_RETURN_FALSE(
+        utils::ReadExtents(old_part, src_extents, &old_data,
+                           kBlockSize * blocks_to_read, kBlockSize));
+    if (old_data == new_data) {
+      // No change in data.
+      if (src_ops_allowed) {
+        operation.set_type(
+            DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY);
+      } else {
+        operation.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+      }
+      data_blob = &empty_blob;
+    } else if (bsdiff_allowed) {
+      // If the source file is considered bsdiff safe (no bsdiff bugs
+      // triggered), see if BSDIFF encoding is smaller.
+      base::FilePath old_chunk;
+      TEST_AND_RETURN_FALSE(base::CreateTemporaryFile(&old_chunk));
+      ScopedPathUnlinker old_unlinker(old_chunk.value());
+      TEST_AND_RETURN_FALSE(
+          utils::WriteFile(old_chunk.value().c_str(),
+                           old_data.data(), old_data.size()));
+      base::FilePath new_chunk;
+      TEST_AND_RETURN_FALSE(base::CreateTemporaryFile(&new_chunk));
+      ScopedPathUnlinker new_unlinker(new_chunk.value());
+      TEST_AND_RETURN_FALSE(
+          utils::WriteFile(new_chunk.value().c_str(),
+                           new_data.data(), new_data.size()));
+
+      TEST_AND_RETURN_FALSE(
+          BsdiffFiles(old_chunk.value(), new_chunk.value(), &bsdiff_delta));
+      CHECK_GT(bsdiff_delta.size(), static_cast<chromeos::Blob::size_type>(0));
+      if (bsdiff_delta.size() < data_blob->size()) {
+        if (src_ops_allowed) {
+          operation.set_type(
+              DeltaArchiveManifest_InstallOperation_Type_SOURCE_BSDIFF);
+        } else {
+          operation.set_type(DeltaArchiveManifest_InstallOperation_Type_BSDIFF);
+        }
+        data_blob = &bsdiff_delta;
+      }
+    }
+  }
+
+  size_t removed_bytes = 0;
+  // Remove identical src/dst block ranges in MOVE operations.
+  if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE) {
+    removed_bytes = RemoveIdenticalBlockRanges(
+        &src_extents, &dst_extents, new_data.size());
+  }
+  // Set legacy src_length and dst_length fields.
+  operation.set_src_length(old_data.size() - removed_bytes);
+  operation.set_dst_length(new_data.size() - removed_bytes);
+
+  // Embed extents in the operation.
+  StoreExtents(src_extents, operation.mutable_src_extents());
+  StoreExtents(dst_extents, operation.mutable_dst_extents());
+
+  // Replace operations should not have source extents.
+  if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
+      operation.type() ==
+          DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) {
+    operation.clear_src_extents();
+    operation.clear_src_length();
+  }
+
+  *out_data = std::move(*data_blob);
+  *out_op = operation;
+
+  return true;
+}
+
+bool DeltaCompressKernelPartition(
+    const string& old_kernel_part,
+    const string& new_kernel_part,
+    uint64_t old_kernel_size,
+    uint64_t new_kernel_size,
+    uint64_t block_size,
+    vector<AnnotatedOperation>* aops,
+    int blobs_fd,
+    off_t* blobs_length,
+    bool src_ops_allowed) {
+  LOG(INFO) << "Delta compressing kernel partition...";
+  LOG_IF(INFO, old_kernel_part.empty()) << "Generating full kernel update...";
+
+  unique_ptr<RawFilesystem> old_kernel_fs;
+  if (!old_kernel_part.empty())
+    old_kernel_fs = RawFilesystem::Create("<kernel-delta-operation>",
+                                          block_size,
+                                          old_kernel_size / block_size);
+  unique_ptr<RawFilesystem> new_kernel_fs = RawFilesystem::Create(
+      "<kernel-delta-operation>",
+      block_size,
+      new_kernel_size / block_size);
+
+  TEST_AND_RETURN_FALSE(DeltaReadFilesystem(aops,
+                                            old_kernel_part,
+                                            new_kernel_part,
+                                            old_kernel_fs.get(),
+                                            new_kernel_fs.get(),
+                                            -1,  // chunk_blocks
+                                            blobs_fd,
+                                            blobs_length,
+                                            false,  // skip_block_0
+                                            src_ops_allowed));
+
+  LOG(INFO) << "Done delta compressing kernel partition.";
+  return true;
+}
+
+// Runs the bsdiff tool on two files and returns the resulting delta in
+// 'out'. Returns true on success.
+bool BsdiffFiles(const string& old_file,
+                 const string& new_file,
+                 chromeos::Blob* out) {
+  const string kPatchFile = "delta.patchXXXXXX";
+  string patch_file_path;
+
+  TEST_AND_RETURN_FALSE(
+      utils::MakeTempFile(kPatchFile, &patch_file_path, nullptr));
+
+  vector<string> cmd;
+  cmd.push_back(kBsdiffPath);
+  cmd.push_back(old_file);
+  cmd.push_back(new_file);
+  cmd.push_back(patch_file_path);
+
+  int rc = 1;
+  chromeos::Blob patch_file;
+  TEST_AND_RETURN_FALSE(Subprocess::SynchronousExec(cmd, &rc, nullptr));
+  TEST_AND_RETURN_FALSE(rc == 0);
+  TEST_AND_RETURN_FALSE(utils::ReadFile(patch_file_path, out));
+  unlink(patch_file_path.c_str());
+  return true;
+}
+
+// Returns true if |op| is a no-op operation that doesn't do any useful work
+// (e.g., a move operation that copies blocks onto themselves).
+bool IsNoopOperation(const DeltaArchiveManifest_InstallOperation& op) {
+  return (op.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE &&
+          ExpandExtents(op.src_extents()) == ExpandExtents(op.dst_extents()));
+}
+
+void FilterNoopOperations(vector<AnnotatedOperation>* ops) {
+  ops->erase(
+      std::remove_if(
+          ops->begin(), ops->end(),
+          [](const AnnotatedOperation& aop){return IsNoopOperation(aop.op);}),
+      ops->end());
+}
+
+bool InitializePartitionInfo(const PartitionConfig& part, PartitionInfo* info) {
+  info->set_size(part.size);
+  OmahaHashCalculator hasher;
+  TEST_AND_RETURN_FALSE(hasher.UpdateFile(part.path, part.size) ==
+                        static_cast<off_t>(part.size));
+  TEST_AND_RETURN_FALSE(hasher.Finalize());
+  const chromeos::Blob& hash = hasher.raw_hash();
+  info->set_hash(hash.data(), hash.size());
+  LOG(INFO) << part.path << ": size=" << part.size << " hash=" << hasher.hash();
+  return true;
+}
+
+}  // namespace diff_utils
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/delta_diff_utils.h b/payload_generator/delta_diff_utils.h
new file mode 100644
index 0000000..aa18f16
--- /dev/null
+++ b/payload_generator/delta_diff_utils.h
@@ -0,0 +1,116 @@
+// Copyright 2015 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.
+
+#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_DELTA_DIFF_UTILS_H_
+#define UPDATE_ENGINE_PAYLOAD_GENERATOR_DELTA_DIFF_UTILS_H_
+
+#include <string>
+#include <vector>
+
+#include <chromeos/secure_blob.h>
+
+#include "update_engine/payload_generator/annotated_operation.h"
+#include "update_engine/payload_generator/filesystem_interface.h"
+#include "update_engine/payload_generator/payload_generation_config.h"
+#include "update_engine/update_metadata.pb.h"
+
+namespace chromeos_update_engine {
+
+namespace diff_utils {
+
+// Create operations in |aops| to produce all the files reported by |new_fs|,
+// including all the blocks not reported by any file.
+// It uses the files reported by |old_fs| and the data in |old_part| to
+// determine the best way to compress the new files (REPLACE, REPLACE_BZ,
+// COPY, BSDIFF) and writes any necessary data to the end of data_fd updating
+// data_file_size accordingly.
+bool DeltaReadFilesystem(std::vector<AnnotatedOperation>* aops,
+                         const std::string& old_part,
+                         const std::string& new_part,
+                         FilesystemInterface* old_fs,
+                         FilesystemInterface* new_fs,
+                         off_t chunk_blocks,
+                         int data_fd,
+                         off_t* data_file_size,
+                         bool skip_block_0,
+                         bool src_ops_allowed);
+
+// For a given file |name| append operations to |aops| to produce it in the
+// |new_part|. The file will be split in chunks of |chunk_blocks| blocks each
+// or treated as a single chunk if |chunk_blocks| is -1. The file data is
+// stored in |new_part| in the blocks described by |new_extents| and, if it
+// exists, the old version exists in |old_part| in the blocks described by
+// |old_extents|. The operations added to |aops| reference the data blob
+// in the file |data_fd|, which has length *data_file_size. *data_file_size is
+// updated appropriately. Returns true on success.
+bool DeltaReadFile(std::vector<AnnotatedOperation>* aops,
+                   const std::string& old_part,
+                   const std::string& new_part,
+                   const std::vector<Extent>& old_extents,
+                   const std::vector<Extent>& new_extents,
+                   const std::string& name,
+                   off_t chunk_blocks,
+                   int data_fd,
+                   off_t* data_file_size,
+                   bool src_ops_allowed);
+
+// Reads the blocks |old_extents| from |old_part| (if it exists) and the
+// |new_extents| from |new_part| and determines the smallest way to encode
+// this |new_extents| for the diff. It stores necessary data in |out_data| and
+// fills in |out_op|. If there's no change in old and new files, it creates a
+// MOVE operation. If there is a change, the smallest of REPLACE, REPLACE_BZ,
+// or BSDIFF wins. |new_extents| must not be empty.
+// If |src_ops_allowed| is true, it will emit SOURCE_COPY and SOURCE_BSDIFF
+// operations instead of MOVE and BSDIFF, respectively.
+// Returns true on success.
+bool ReadExtentsToDiff(const std::string& old_part,
+                       const std::string& new_part,
+                       const std::vector<Extent>& old_extents,
+                       const std::vector<Extent>& new_extents,
+                       bool bsdiff_allowed,
+                       chromeos::Blob* out_data,
+                       DeltaArchiveManifest_InstallOperation* out_op,
+                       bool src_ops_allowed);
+
+// 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. The size of the old and
+// new kernel is passed in |old_kernel_size| and |new_kernel_size|. The
+// operations used to generate the new kernel are stored in the |aops|
+// vector, and the blob associated to those operations is written at the end
+// of the |blobs_fd| file, adding to the value pointed by |blobs_length| the
+// bytes written to |blobs_fd|.
+bool DeltaCompressKernelPartition(
+    const std::string& old_kernel_part,
+    const std::string& new_kernel_part,
+    uint64_t old_kernel_size,
+    uint64_t new_kernel_size,
+    uint64_t block_size,
+    std::vector<AnnotatedOperation>* aops,
+    int blobs_fd,
+    off_t* blobs_length,
+    bool src_ops_allowed);
+
+// Runs the bsdiff tool on two files and returns the resulting delta in
+// |out|. Returns true on success.
+bool BsdiffFiles(const std::string& old_file,
+                 const std::string& new_file,
+                 chromeos::Blob* out);
+
+// Returns true if |op| is a no-op operation that doesn't do any useful work
+// (e.g., a move operation that copies blocks onto themselves).
+bool IsNoopOperation(const DeltaArchiveManifest_InstallOperation& op);
+
+// Filters all the operations that are no-op, maintaining the relative order
+// of the rest of the operations.
+void FilterNoopOperations(std::vector<AnnotatedOperation>* ops);
+
+bool InitializePartitionInfo(const PartitionConfig& partition,
+                             PartitionInfo* info);
+
+}  // namespace diff_utils
+
+}  // namespace chromeos_update_engine
+
+#endif  // UPDATE_ENGINE_PAYLOAD_GENERATOR_DELTA_DIFF_UTILS_H_
diff --git a/payload_generator/delta_diff_utils_unittest.cc b/payload_generator/delta_diff_utils_unittest.cc
new file mode 100644
index 0000000..2157aa1
--- /dev/null
+++ b/payload_generator/delta_diff_utils_unittest.cc
@@ -0,0 +1,479 @@
+// Copyright 2015 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.
+
+#include "update_engine/payload_generator/delta_diff_utils.h"
+
+#include <algorithm>
+#include <string>
+#include <vector>
+
+#include <base/files/scoped_file.h>
+#include <gtest/gtest.h>
+
+#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/extent_ranges.h"
+#include "update_engine/payload_generator/extent_utils.h"
+#include "update_engine/payload_generator/fake_filesystem.h"
+#include "update_engine/test_utils.h"
+#include "update_engine/utils.h"
+
+using std::string;
+using std::unique_ptr;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+
+// Writes the |data| in the blocks specified by |extents| on the partition
+// |part_path|. The |data| size could be smaller than the size of the blocks
+// passed.
+bool WriteExtents(const string& part_path,
+                  const vector<Extent>& extents,
+                  off_t block_size,
+                  const chromeos::Blob& data) {
+  uint64_t offset = 0;
+  base::ScopedFILE fp(fopen(part_path.c_str(), "r+"));
+  TEST_AND_RETURN_FALSE(fp.get());
+
+  for (const Extent& extent : extents) {
+    if (offset >= data.size())
+      break;
+    TEST_AND_RETURN_FALSE(
+        fseek(fp.get(), extent.start_block() * block_size, SEEK_SET) == 0);
+    uint64_t to_write = std::min(extent.num_blocks() * block_size,
+                                 data.size() - offset);
+    TEST_AND_RETURN_FALSE(
+        fwrite(data.data() + offset, 1, to_write, fp.get()) == to_write);
+    offset += extent.num_blocks() * block_size;
+  }
+  return true;
+}
+
+}  // namespace
+
+class DeltaDiffUtilsTest : public ::testing::Test {
+ protected:
+  const uint64_t kFilesystemSize = kBlockSize * 1024;
+
+  void SetUp() override {
+    old_part_path_ = "DeltaDiffUtilsTest-old_part_path-XXXXXX";
+    CreateFilesystem(&old_fs_, &old_part_path_, kFilesystemSize);
+
+    new_part_path_ = "DeltaDiffUtilsTest-new_part_path-XXXXXX";
+    CreateFilesystem(&old_fs_, &new_part_path_, kFilesystemSize);
+  }
+
+  void TearDown() override {
+    unlink(old_part_path_.c_str());
+    unlink(new_part_path_.c_str());
+  }
+
+  // Create a fake filesystem of the given size and initialize the partition
+  // holding it.
+  void CreateFilesystem(unique_ptr<FakeFilesystem>* fs, string* filename,
+                        uint64_t size) {
+    string pattern = *filename;
+    ASSERT_TRUE(utils::MakeTempFile(pattern.c_str(), filename, nullptr));
+    ASSERT_EQ(0, truncate(filename->c_str(), size));
+    fs->reset(new FakeFilesystem(kBlockSize, size / kBlockSize));
+  }
+
+  // Paths to old and new temporary filesystems used in the tests.
+  string old_part_path_;
+  string new_part_path_;
+
+  // FilesystemInterface fake implementations used to mock out the file/block
+  // distribution.
+  unique_ptr<FakeFilesystem> old_fs_;
+  unique_ptr<FakeFilesystem> new_fs_;
+};
+
+TEST_F(DeltaDiffUtilsTest, MoveSmallTest) {
+  chromeos::Blob data_blob(kBlockSize);
+  test_utils::FillWithData(&data_blob);
+
+  // The old file is on a different block than the new one.
+  vector<Extent> old_extents = { ExtentForRange(11, 1) };
+  vector<Extent> new_extents = { ExtentForRange(1, 1) };
+
+  EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, data_blob));
+  EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
+
+  chromeos::Blob data;
+  DeltaArchiveManifest_InstallOperation op;
+  EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
+      old_part_path_,
+      new_part_path_,
+      old_extents,
+      new_extents,
+      true,  // bsdiff_allowed
+      &data,
+      &op,
+      false));  // src_ops_allowed
+  EXPECT_TRUE(data.empty());
+
+  EXPECT_TRUE(op.has_type());
+  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE, op.type());
+  EXPECT_FALSE(op.has_data_offset());
+  EXPECT_FALSE(op.has_data_length());
+  EXPECT_EQ(1, op.src_extents_size());
+  EXPECT_EQ(kBlockSize, op.src_length());
+  EXPECT_EQ(1, op.dst_extents_size());
+  EXPECT_EQ(kBlockSize, op.dst_length());
+  EXPECT_EQ(BlocksInExtents(op.src_extents()),
+            BlocksInExtents(op.dst_extents()));
+  EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
+}
+
+TEST_F(DeltaDiffUtilsTest, MoveWithSameBlock) {
+  // Setup the old/new files so that it has immobile chunks; we make sure to
+  // utilize all sub-cases of such chunks: blocks 21--22 induce a split (src)
+  // and complete removal (dst), whereas blocks 24--25 induce trimming of the
+  // tail (src) and head (dst) of extents. The final block (29) is used for
+  // ensuring we properly account for the number of bytes removed in cases where
+  // the last block is partly filled. The detailed configuration:
+  //
+  // Old:  [ 20     21 22     23     24 25 ] [ 28     29 ]
+  // New:  [ 18 ] [ 21 22 ] [ 20 ] [ 24 25     26 ] [ 29 ]
+  // Same:          ^^ ^^            ^^ ^^            ^^
+  vector<Extent> old_extents = {
+      ExtentForRange(20, 6),
+      ExtentForRange(28, 2) };
+  vector<Extent> new_extents = {
+      ExtentForRange(18, 1),
+      ExtentForRange(21, 2),
+      ExtentForRange(20, 1),
+      ExtentForRange(24, 3),
+      ExtentForRange(29, 1) };
+
+  uint64_t num_blocks = BlocksInExtents(old_extents);
+  EXPECT_EQ(num_blocks, BlocksInExtents(new_extents));
+
+  // The size of the data should match the total number of blocks. Each block
+  // has a different content.
+  chromeos::Blob file_data;
+  for (uint64_t i = 0; i < num_blocks; ++i) {
+    file_data.resize(file_data.size() + kBlockSize, 'a' + i);
+  }
+
+  EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, file_data));
+  EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, file_data));
+
+  chromeos::Blob data;
+  DeltaArchiveManifest_InstallOperation op;
+  EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
+      old_part_path_,
+      new_part_path_,
+      old_extents,
+      new_extents,
+      true,  // bsdiff_allowed
+      &data,
+      &op,
+      false));  // src_ops_allowed
+
+  EXPECT_TRUE(data.empty());
+
+  EXPECT_TRUE(op.has_type());
+  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE, op.type());
+  EXPECT_FALSE(op.has_data_offset());
+  EXPECT_FALSE(op.has_data_length());
+
+  // The expected old and new extents that actually moved. See comment above.
+  old_extents = {
+      ExtentForRange(20, 1),
+      ExtentForRange(23, 1),
+      ExtentForRange(28, 1) };
+  new_extents = {
+      ExtentForRange(18, 1),
+      ExtentForRange(20, 1),
+      ExtentForRange(26, 1) };
+  num_blocks = BlocksInExtents(old_extents);
+
+  EXPECT_EQ(num_blocks * kBlockSize, op.src_length());
+  EXPECT_EQ(num_blocks * kBlockSize, op.dst_length());
+
+  EXPECT_EQ(old_extents.size(), op.src_extents_size());
+  for (int i = 0; i < op.src_extents_size(); i++) {
+    EXPECT_EQ(old_extents[i].start_block(), op.src_extents(i).start_block())
+        << "i == " << i;
+    EXPECT_EQ(old_extents[i].num_blocks(), op.src_extents(i).num_blocks())
+        << "i == " << i;
+  }
+
+  EXPECT_EQ(new_extents.size(), op.dst_extents_size());
+  for (int i = 0; i < op.dst_extents_size(); i++) {
+    EXPECT_EQ(new_extents[i].start_block(), op.dst_extents(i).start_block())
+        << "i == " << i;
+    EXPECT_EQ(new_extents[i].num_blocks(), op.dst_extents(i).num_blocks())
+        << "i == " << i;
+  }
+}
+
+TEST_F(DeltaDiffUtilsTest, BsdiffSmallTest) {
+  // Test a BSDIFF operation from block 1 to block 2.
+  chromeos::Blob data_blob(kBlockSize);
+  test_utils::FillWithData(&data_blob);
+
+  // The old file is on a different block than the new one.
+  vector<Extent> old_extents = { ExtentForRange(1, 1) };
+  vector<Extent> new_extents = { ExtentForRange(2, 1) };
+
+  EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, data_blob));
+  // Modify one byte in the new file.
+  data_blob[0]++;
+  EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
+
+  chromeos::Blob data;
+  DeltaArchiveManifest_InstallOperation op;
+  EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
+      old_part_path_,
+      new_part_path_,
+      old_extents,
+      new_extents,
+      true,  // bsdiff_allowed
+      &data,
+      &op,
+      false));  // src_ops_allowed
+
+  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(kBlockSize, op.src_length());
+  EXPECT_EQ(1, op.dst_extents_size());
+  EXPECT_EQ(kBlockSize, op.dst_length());
+  EXPECT_EQ(BlocksInExtents(op.src_extents()),
+            BlocksInExtents(op.dst_extents()));
+  EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
+}
+
+TEST_F(DeltaDiffUtilsTest, BsdiffNotAllowedTest) {
+  // Same setup as the previous test, but this time BSDIFF operations are not
+  // allowed.
+  chromeos::Blob data_blob(kBlockSize);
+  test_utils::FillWithData(&data_blob);
+
+  // The old file is on a different block than the new one.
+  vector<Extent> old_extents = { ExtentForRange(1, 1) };
+  vector<Extent> new_extents = { ExtentForRange(2, 1) };
+
+  EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, data_blob));
+  // Modify one byte in the new file.
+  data_blob[0]++;
+  EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
+
+  chromeos::Blob data;
+  DeltaArchiveManifest_InstallOperation op;
+  EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
+      old_part_path_,
+      new_part_path_,
+      old_extents,
+      new_extents,
+      false,  // bsdiff_allowed
+      &data,
+      &op,
+      false));  // src_ops_allowed
+
+  EXPECT_FALSE(data.empty());
+
+  // The point of this test is that we don't use BSDIFF the way the above
+  // did. The rest of the details are to be caught in other tests.
+  EXPECT_TRUE(op.has_type());
+  EXPECT_NE(DeltaArchiveManifest_InstallOperation_Type_BSDIFF, op.type());
+}
+
+TEST_F(DeltaDiffUtilsTest, BsdiffNotAllowedMoveTest) {
+  chromeos::Blob data_blob(kBlockSize);
+  test_utils::FillWithData(&data_blob);
+
+  // The old file is on a different block than the new one.
+  vector<Extent> old_extents = { ExtentForRange(1, 1) };
+  vector<Extent> new_extents = { ExtentForRange(2, 1) };
+
+  EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, data_blob));
+  EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
+
+  chromeos::Blob data;
+  DeltaArchiveManifest_InstallOperation op;
+  EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
+      old_part_path_,
+      new_part_path_,
+      old_extents,
+      new_extents,
+      false,  // bsdiff_allowed
+      &data,
+      &op,
+      false));  // src_ops_allowed
+
+  EXPECT_TRUE(data.empty());
+
+  // The point of this test is that we can still use a MOVE for a file
+  // that is blacklisted.
+  EXPECT_TRUE(op.has_type());
+  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE, op.type());
+}
+
+TEST_F(DeltaDiffUtilsTest, ReplaceSmallTest) {
+  // The old file is on a different block than the new one.
+  vector<Extent> old_extents = { ExtentForRange(1, 1) };
+  vector<Extent> new_extents = { ExtentForRange(2, 1) };
+
+  // Make a blob that's just 1's that will compress well.
+  chromeos::Blob ones(kBlockSize, 1);
+
+  // Make a blob with random data that won't compress well.
+  chromeos::Blob random_data;
+  std::mt19937 gen(12345);
+  std::uniform_int_distribution<uint8_t> dis(0, 255);
+  for (uint32_t i = 0; i < kBlockSize; i++) {
+    random_data.push_back(dis(gen));
+  }
+
+  for (int i = 0; i < 2; i++) {
+    chromeos::Blob data_to_test = i == 0 ? random_data : ones;
+    // The old_extents will be initialized with 0.
+    EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize,
+                             data_to_test));
+
+    chromeos::Blob data;
+    DeltaArchiveManifest_InstallOperation op;
+    EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
+        old_part_path_,
+        new_part_path_,
+        old_extents,
+        new_extents,
+        true,  // bsdiff_allowed
+        &data,
+        &op,
+        false));  // src_ops_allowed
+    EXPECT_FALSE(data.empty());
+
+    EXPECT_TRUE(op.has_type());
+    const DeltaArchiveManifest_InstallOperation_Type expected_type =
+        (i == 0 ? DeltaArchiveManifest_InstallOperation_Type_REPLACE :
+         DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+    EXPECT_EQ(expected_type, op.type());
+    EXPECT_FALSE(op.has_data_offset());
+    EXPECT_FALSE(op.has_data_length());
+    EXPECT_EQ(0, op.src_extents_size());
+    EXPECT_FALSE(op.has_src_length());
+    EXPECT_EQ(1, op.dst_extents_size());
+    EXPECT_EQ(data_to_test.size(), op.dst_length());
+    EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
+  }
+}
+
+TEST_F(DeltaDiffUtilsTest, SourceCopyTest) {
+  // Makes sure SOURCE_COPY operations are emitted whenever src_ops_allowed
+  // is true. It is the same setup as MoveSmallTest, which checks that
+  // the operation is well-formed.
+  chromeos::Blob data_blob(kBlockSize);
+  test_utils::FillWithData(&data_blob);
+
+  // The old file is on a different block than the new one.
+  vector<Extent> old_extents = { ExtentForRange(11, 1) };
+  vector<Extent> new_extents = { ExtentForRange(1, 1) };
+
+  EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, data_blob));
+  EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
+
+  chromeos::Blob data;
+  DeltaArchiveManifest_InstallOperation op;
+  EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
+      old_part_path_,
+      new_part_path_,
+      old_extents,
+      new_extents,
+      true,  // bsdiff_allowed
+      &data,
+      &op,
+      true));  // src_ops_allowed
+  EXPECT_TRUE(data.empty());
+
+  EXPECT_TRUE(op.has_type());
+  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY, op.type());
+}
+
+TEST_F(DeltaDiffUtilsTest, SourceBsdiffTest) {
+  // Makes sure SOURCE_BSDIFF operations are emitted whenever src_ops_allowed
+  // is true. It is the same setup as BsdiffSmallTest, which checks
+  // that the operation is well-formed.
+  chromeos::Blob data_blob(kBlockSize);
+  test_utils::FillWithData(&data_blob);
+
+  // The old file is on a different block than the new one.
+  vector<Extent> old_extents = { ExtentForRange(1, 1) };
+  vector<Extent> new_extents = { ExtentForRange(2, 1) };
+
+  EXPECT_TRUE(WriteExtents(old_part_path_, old_extents, kBlockSize, data_blob));
+  // Modify one byte in the new file.
+  data_blob[0]++;
+  EXPECT_TRUE(WriteExtents(new_part_path_, new_extents, kBlockSize, data_blob));
+
+  chromeos::Blob data;
+  DeltaArchiveManifest_InstallOperation op;
+  EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
+      old_part_path_,
+      new_part_path_,
+      old_extents,
+      new_extents,
+      true,  // bsdiff_allowed
+      &data,
+      &op,
+      true));  // src_ops_allowed
+
+  EXPECT_FALSE(data.empty());
+  EXPECT_TRUE(op.has_type());
+  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_BSDIFF,
+            op.type());
+}
+
+TEST_F(DeltaDiffUtilsTest, IsNoopOperationTest) {
+  DeltaArchiveManifest_InstallOperation op;
+  op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+  EXPECT_FALSE(diff_utils::IsNoopOperation(op));
+  op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+  EXPECT_TRUE(diff_utils::IsNoopOperation(op));
+  *(op.add_src_extents()) = ExtentForRange(3, 2);
+  *(op.add_dst_extents()) = ExtentForRange(3, 2);
+  EXPECT_TRUE(diff_utils::IsNoopOperation(op));
+  *(op.add_src_extents()) = ExtentForRange(7, 5);
+  *(op.add_dst_extents()) = ExtentForRange(7, 5);
+  EXPECT_TRUE(diff_utils::IsNoopOperation(op));
+  *(op.add_src_extents()) = ExtentForRange(20, 2);
+  *(op.add_dst_extents()) = ExtentForRange(20, 1);
+  *(op.add_dst_extents()) = ExtentForRange(21, 1);
+  EXPECT_TRUE(diff_utils::IsNoopOperation(op));
+  *(op.add_src_extents()) = ExtentForRange(24, 1);
+  *(op.add_dst_extents()) = ExtentForRange(25, 1);
+  EXPECT_FALSE(diff_utils::IsNoopOperation(op));
+}
+
+TEST_F(DeltaDiffUtilsTest, FilterNoopOperations) {
+  AnnotatedOperation aop1;
+  aop1.op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+  *(aop1.op.add_dst_extents()) = ExtentForRange(3, 2);
+  aop1.name = "aop1";
+
+  AnnotatedOperation aop2 = aop1;
+  aop2.name = "aop2";
+
+  AnnotatedOperation noop;
+  noop.op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+  *(noop.op.add_src_extents()) = ExtentForRange(3, 2);
+  *(noop.op.add_dst_extents()) = ExtentForRange(3, 2);
+  noop.name = "noop";
+
+  vector<AnnotatedOperation> ops = {noop, aop1, noop, noop, aop2, noop};
+  diff_utils::FilterNoopOperations(&ops);
+  EXPECT_EQ(2u, ops.size());
+  EXPECT_EQ("aop1", ops[0].name);
+  EXPECT_EQ("aop2", ops[1].name);
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/extent_utils.cc b/payload_generator/extent_utils.cc
index 71aae1d..caacb38 100644
--- a/payload_generator/extent_utils.cc
+++ b/payload_generator/extent_utils.cc
@@ -41,12 +41,46 @@
 Extent GetElement(const vector<Extent>& collection, size_t index) {
   return collection[index];
 }
+
 Extent GetElement(
     const google::protobuf::RepeatedPtrField<Extent>& collection,
     size_t index) {
   return collection.Get(index);
 }
 
+void ExtendExtents(
+    google::protobuf::RepeatedPtrField<Extent>* extents,
+    const google::protobuf::RepeatedPtrField<Extent>& extents_to_add) {
+  vector<Extent> extents_vector;
+  vector<Extent> extents_to_add_vector;
+  ExtentsToVector(*extents, &extents_vector);
+  ExtentsToVector(extents_to_add, &extents_to_add_vector);
+  extents_vector.insert(extents_vector.end(),
+                        extents_to_add_vector.begin(),
+                        extents_to_add_vector.end());
+  NormalizeExtents(&extents_vector);
+  extents->Clear();
+  StoreExtents(extents_vector, extents);
+}
+
+// Stores all Extents in 'extents' into 'out'.
+void StoreExtents(const vector<Extent>& extents,
+                  google::protobuf::RepeatedPtrField<Extent>* out) {
+  for (const Extent& extent : extents) {
+    Extent* new_extent = out->Add();
+    *new_extent = extent;
+  }
+}
+
+// Stores all extents in |extents| into |out_vector|.
+void ExtentsToVector(const google::protobuf::RepeatedPtrField<Extent>& extents,
+                     vector<Extent>* out_vector) {
+  out_vector->clear();
+  for (int i = 0; i < extents.size(); i++) {
+    out_vector->push_back(extents.Get(i));
+  }
+}
+
 void NormalizeExtents(vector<Extent>* extents) {
   vector<Extent> new_extents;
   for (const Extent& curr_ext : *extents) {
diff --git a/payload_generator/extent_utils.h b/payload_generator/extent_utils.h
index e9ab9eb..eeeed40 100644
--- a/payload_generator/extent_utils.h
+++ b/payload_generator/extent_utils.h
@@ -7,6 +7,7 @@
 
 #include <vector>
 
+#include "update_engine/payload_constants.h"
 #include "update_engine/update_metadata.pb.h"
 
 // Utility functions for manipulating Extents and lists of blocks.
@@ -25,6 +26,8 @@
     const google::protobuf::RepeatedPtrField<Extent>& collection,
     size_t index);
 
+// Return the total number of blocks in a collection (vector or
+// RepeatedPtrField) of Extents.
 template<typename T>
 uint64_t BlocksInExtents(const T& collection) {
   uint64_t ret = 0;
@@ -34,6 +37,39 @@
   return ret;
 }
 
+// Takes a collection (vector or RepeatedPtrField) of Extent and
+// returns a vector of the blocks referenced, in order.
+template<typename T>
+std::vector<uint64_t> ExpandExtents(const T& extents) {
+  std::vector<uint64_t> ret;
+  for (size_t i = 0, e = static_cast<size_t>(extents.size()); i != e; ++i) {
+    const Extent extent = GetElement(extents, i);
+    if (extent.start_block() == kSparseHole) {
+      ret.resize(ret.size() + extent.num_blocks(), kSparseHole);
+    } else {
+      for (uint64_t block = extent.start_block();
+           block < (extent.start_block() + extent.num_blocks()); block++) {
+        ret.push_back(block);
+      }
+    }
+  }
+  return ret;
+}
+
+// Stores all Extents in 'extents' into 'out'.
+void StoreExtents(const std::vector<Extent>& extents,
+                  google::protobuf::RepeatedPtrField<Extent>* out);
+
+// Stores all extents in |extents| into |out_vector|.
+void ExtentsToVector(const google::protobuf::RepeatedPtrField<Extent>& extents,
+                     std::vector<Extent>* out_vector);
+
+// Takes a pointer to extents |extents| and extents |extents_to_add|, and
+// merges them by adding |extents_to_add| to |extents| and normalizing.
+void ExtendExtents(
+  google::protobuf::RepeatedPtrField<Extent>* extents,
+  const google::protobuf::RepeatedPtrField<Extent>& extents_to_add);
+
 // Takes a vector of extents and normalizes those extents. Expects the extents
 // to be sorted by start block. E.g. if |extents| is [(1, 2), (3, 5), (10, 2)]
 // then |extents| will be changed to [(1, 7), (10, 2)].
diff --git a/payload_generator/extent_utils_unittest.cc b/payload_generator/extent_utils_unittest.cc
index b9f9ef2..188164d 100644
--- a/payload_generator/extent_utils_unittest.cc
+++ b/payload_generator/extent_utils_unittest.cc
@@ -62,6 +62,24 @@
   }
 }
 
+TEST(ExtentUtilsTest, ExtendExtentsTest) {
+  DeltaArchiveManifest_InstallOperation first_op;
+  *(first_op.add_src_extents()) = ExtentForRange(1, 1);
+  *(first_op.add_src_extents()) = ExtentForRange(3, 1);
+
+  DeltaArchiveManifest_InstallOperation second_op;
+  *(second_op.add_src_extents()) = ExtentForRange(4, 2);
+  *(second_op.add_src_extents()) = ExtentForRange(8, 2);
+
+  ExtendExtents(first_op.mutable_src_extents(), second_op.src_extents());
+  vector<Extent> first_op_vec;
+  ExtentsToVector(first_op.src_extents(), &first_op_vec);
+  EXPECT_EQ((vector<Extent>{
+      ExtentForRange(1, 1),
+      ExtentForRange(3, 3),
+      ExtentForRange(8, 2)}), first_op_vec);
+}
+
 TEST(ExtentUtilsTest, NormalizeExtentsSimpleList) {
   // Make sure it works when there's just one extent.
   vector<Extent> extents;
diff --git a/payload_generator/generate_delta_main.cc b/payload_generator/generate_delta_main.cc
index 7f7b2b8..662c1f4 100644
--- a/payload_generator/generate_delta_main.cc
+++ b/payload_generator/generate_delta_main.cc
@@ -20,6 +20,7 @@
 
 #include "update_engine/delta_performer.h"
 #include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/delta_diff_utils.h"
 #include "update_engine/payload_generator/payload_generation_config.h"
 #include "update_engine/payload_generator/payload_signer.h"
 #include "update_engine/payload_verifier.h"
@@ -190,10 +191,8 @@
   old_image.kernel.path = old_kernel;
   old_image.rootfs.path = old_rootfs;
   CHECK(old_image.LoadImageSize());
-  CHECK(DeltaDiffGenerator::InitializePartitionInfo(old_image.kernel,
-                                                    &kern_info));
-  CHECK(DeltaDiffGenerator::InitializePartitionInfo(old_image.rootfs,
-                                                    &root_info));
+  CHECK(diff_utils::InitializePartitionInfo(old_image.kernel, &kern_info));
+  CHECK(diff_utils::InitializePartitionInfo(old_image.rootfs, &root_info));
   install_plan.kernel_hash.assign(kern_info.hash().begin(),
                                   kern_info.hash().end());
   install_plan.rootfs_hash.assign(root_info.hash().begin(),
diff --git a/payload_generator/inplace_generator.cc b/payload_generator/inplace_generator.cc
index 9494d73..2ada2f3 100644
--- a/payload_generator/inplace_generator.cc
+++ b/payload_generator/inplace_generator.cc
@@ -14,6 +14,7 @@
 #include "update_engine/payload_constants.h"
 #include "update_engine/payload_generator/cycle_breaker.h"
 #include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/delta_diff_utils.h"
 #include "update_engine/payload_generator/ext2_filesystem.h"
 #include "update_engine/payload_generator/extent_ranges.h"
 #include "update_engine/payload_generator/graph_types.h"
@@ -74,25 +75,22 @@
     const vector<Extent>& replace_extents) {
   // First, expand out the blocks that op reads from
   vector<uint64_t> read_blocks =
-      DeltaDiffGenerator::ExpandExtents(vertex->op.src_extents());
+      ExpandExtents(vertex->op.src_extents());
   {
     // Expand remove_extents and replace_extents
-    vector<uint64_t> remove_extents_expanded =
-        DeltaDiffGenerator::ExpandExtents(remove_extents);
-    vector<uint64_t> replace_extents_expanded =
-        DeltaDiffGenerator::ExpandExtents(replace_extents);
+    vector<uint64_t> remove_extents_expanded = ExpandExtents(remove_extents);
+    vector<uint64_t> replace_extents_expanded = ExpandExtents(replace_extents);
     CHECK_EQ(remove_extents_expanded.size(), replace_extents_expanded.size());
     map<uint64_t, uint64_t> conversion;
     for (vector<uint64_t>::size_type i = 0;
          i < replace_extents_expanded.size(); i++) {
       conversion[remove_extents_expanded[i]] = replace_extents_expanded[i];
     }
-    utils::ApplyMap(&read_blocks, conversion);
+    ApplyMap(&read_blocks, conversion);
     for (auto& edge_prop_pair : vertex->out_edges) {
-      vector<uint64_t> write_before_deps_expanded =
-          DeltaDiffGenerator::ExpandExtents(
-              edge_prop_pair.second.write_extents);
-      utils::ApplyMap(&write_before_deps_expanded, conversion);
+      vector<uint64_t> write_before_deps_expanded = ExpandExtents(
+          edge_prop_pair.second.write_extents);
+      ApplyMap(&write_before_deps_expanded, conversion);
       edge_prop_pair.second.write_extents =
           CompressExtents(write_before_deps_expanded);
     }
@@ -100,8 +98,7 @@
   // Convert read_blocks back to extents
   vertex->op.clear_src_extents();
   vector<Extent> new_extents = CompressExtents(read_blocks);
-  DeltaDiffGenerator::StoreExtents(new_extents,
-                                   vertex->op.mutable_src_extents());
+  StoreExtents(new_extents, vertex->op.mutable_src_extents());
 }
 
 bool InplaceGenerator::CutEdges(Graph* graph,
@@ -141,11 +138,10 @@
 
     // Set src/dst extents and other proto variables for copy operation
     graph->back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
-    DeltaDiffGenerator::StoreExtents(
-        cut_edge_properties.extents,
-        graph->back().op.mutable_src_extents());
-    DeltaDiffGenerator::StoreExtents(cuts.back().tmp_extents,
-                                     graph->back().op.mutable_dst_extents());
+    StoreExtents(cut_edge_properties.extents,
+                 graph->back().op.mutable_src_extents());
+    StoreExtents(cuts.back().tmp_extents,
+                 graph->back().op.mutable_dst_extents());
     graph->back().op.set_src_length(
         graph_utils::EdgeWeight(*graph, edge) * kBlockSize);
     graph->back().op.set_dst_length(graph->back().op.src_length());
@@ -430,7 +426,7 @@
     // blocks.
     DeltaArchiveManifest_InstallOperation *op = &(*graph)[cut.new_vertex].op;
     op->clear_dst_extents();
-    DeltaDiffGenerator::StoreExtents(real_extents, op->mutable_dst_extents());
+    StoreExtents(real_extents, op->mutable_dst_extents());
   }
   return true;
 }
@@ -534,11 +530,11 @@
     // |new_extents| list of blocks and update the graph.
     vector<AnnotatedOperation> new_aop;
     vector<Extent> new_extents;
-    DeltaDiffGenerator::ExtentsToVector((*graph)[cut.old_dst].op.dst_extents(),
-                                        &new_extents);
-    TEST_AND_RETURN_FALSE(DeltaDiffGenerator::DeltaReadFile(
+    ExtentsToVector((*graph)[cut.old_dst].op.dst_extents(),
+                    &new_extents);
+    TEST_AND_RETURN_FALSE(diff_utils::DeltaReadFile(
         &new_aop,
-        kEmptyPath,  // old_part
+        "",  // old_part
         new_part,
         vector<Extent>(),  // old_extents
         new_extents,
@@ -701,6 +697,15 @@
   return true;
 }
 
+void InplaceGenerator::ApplyMap(vector<uint64_t>* collection,
+                                const map<uint64_t, uint64_t>& the_map) {
+  for (uint64_t& elem : *collection) {
+    const auto& map_it = the_map.find(elem);
+    if (map_it != the_map.end())
+      elem = map_it->second;
+  }
+}
+
 bool InplaceGenerator::GenerateOperations(
     const PayloadGenerationConfig& config,
     int data_file_fd,
@@ -718,16 +723,16 @@
   // Temporary list of operations used to construct the dependency graph.
   vector<AnnotatedOperation> aops;
   TEST_AND_RETURN_FALSE(
-      DeltaDiffGenerator::DeltaReadFilesystem(&aops,
-                                              config.source.rootfs.path,
-                                              config.target.rootfs.path,
-                                              old_fs.get(),
-                                              new_fs.get(),
-                                              chunk_blocks,
-                                              data_file_fd,
-                                              data_file_size,
-                                              true,  // skip_block_0
-                                              false));  // src_ops_allowed
+      diff_utils::DeltaReadFilesystem(&aops,
+                                      config.source.rootfs.path,
+                                      config.target.rootfs.path,
+                                      old_fs.get(),
+                                      new_fs.get(),
+                                      chunk_blocks,
+                                      data_file_fd,
+                                      data_file_size,
+                                      true,  // skip_block_0
+                                      false));  // src_ops_allowed
   // Convert the rootfs operations to the graph.
   Graph graph;
   CheckGraph(graph);
@@ -751,17 +756,16 @@
   }
 
   // Read kernel partition
-  TEST_AND_RETURN_FALSE(
-      DeltaDiffGenerator::DeltaCompressKernelPartition(
-          config.source.kernel.path,
-          config.target.kernel.path,
-          config.source.kernel.size,
-          config.target.kernel.size,
-          config.block_size,
-          kernel_ops,
-          data_file_fd,
-          data_file_size,
-          false));  // src_ops_allowed
+  TEST_AND_RETURN_FALSE(diff_utils::DeltaCompressKernelPartition(
+      config.source.kernel.path,
+      config.target.kernel.path,
+      config.source.kernel.size,
+      config.target.kernel.size,
+      config.block_size,
+      kernel_ops,
+      data_file_fd,
+      data_file_size,
+      false));  // src_ops_allowed
   LOG(INFO) << "done reading kernel";
   CheckGraph(graph);
 
@@ -790,7 +794,7 @@
   }
 
   // Re-add the operation for the block 0.
-  TEST_AND_RETURN_FALSE(DeltaDiffGenerator::DeltaReadFile(
+  TEST_AND_RETURN_FALSE(diff_utils::DeltaReadFile(
       rootfs_ops,
       config.source.rootfs.path,
       config.target.rootfs.path,
diff --git a/payload_generator/inplace_generator.h b/payload_generator/inplace_generator.h
index 90c1fd4..158e364 100644
--- a/payload_generator/inplace_generator.h
+++ b/payload_generator/inplace_generator.h
@@ -5,6 +5,7 @@
 #ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_INPLACE_GENERATOR_H_
 #define UPDATE_ENGINE_PAYLOAD_GENERATOR_INPLACE_GENERATOR_H_
 
+#include <map>
 #include <set>
 #include <string>
 #include <vector>
@@ -187,6 +188,12 @@
       const DeltaArchiveManifest_InstallOperation operation,
       const std::string& op_name);
 
+  // Apply the transformation stored in |the_map| to the |collection| vector
+  // replacing the map keys found in |collection| with its associated value in
+  // |the_map|.
+  static void ApplyMap(std::vector<uint64_t>* collection,
+                       const std::map<uint64_t, uint64_t>& the_map);
+
   // Generate the update payload operations for the kernel and rootfs using
   // only operations that read from the target and/or write to the target,
   // hence, applying the payload "in-place" in the target partition. This method
diff --git a/payload_generator/inplace_generator_unittest.cc b/payload_generator/inplace_generator_unittest.cc
index b988787..5de0df9 100644
--- a/payload_generator/inplace_generator_unittest.cc
+++ b/payload_generator/inplace_generator_unittest.cc
@@ -4,6 +4,7 @@
 
 #include "update_engine/payload_generator/inplace_generator.h"
 
+#include <map>
 #include <set>
 #include <sstream>
 #include <string>
@@ -22,6 +23,7 @@
 #include "update_engine/test_utils.h"
 #include "update_engine/utils.h"
 
+using std::map;
 using std::set;
 using std::string;
 using std::stringstream;
@@ -45,8 +47,8 @@
                DeltaArchiveManifest_InstallOperation_Type type) {
   out->op.set_type(type);
   out->file_name = path;
-  DeltaDiffGenerator::StoreExtents(src_extents, out->op.mutable_src_extents());
-  DeltaDiffGenerator::StoreExtents(dst_extents, out->op.mutable_dst_extents());
+  StoreExtents(src_extents, out->op.mutable_src_extents());
+  StoreExtents(dst_extents, out->op.mutable_dst_extents());
 }
 
 vector<Extent> VectOfExt(uint64_t start_block, uint64_t num_blocks) {
@@ -148,7 +150,7 @@
     AppendBlockToExtents(&extents, 3);
     AppendBlockToExtents(&extents, 5);
     AppendBlockToExtents(&extents, 7);
-    DeltaDiffGenerator::StoreExtents(extents,
+    StoreExtents(extents,
                                      graph.back().op.mutable_src_extents());
     blocks[3].reader = graph.size() - 1;
     blocks[5].reader = graph.size() - 1;
@@ -159,7 +161,7 @@
     AppendBlockToExtents(&extents, 1);
     AppendBlockToExtents(&extents, 2);
     AppendBlockToExtents(&extents, 4);
-    DeltaDiffGenerator::StoreExtents(extents,
+    StoreExtents(extents,
                                      graph.back().op.mutable_dst_extents());
     blocks[1].writer = graph.size() - 1;
     blocks[2].writer = graph.size() - 1;
@@ -173,7 +175,7 @@
     AppendBlockToExtents(&extents, 1);
     AppendBlockToExtents(&extents, 2);
     AppendBlockToExtents(&extents, 4);
-    DeltaDiffGenerator::StoreExtents(extents,
+    StoreExtents(extents,
                                      graph.back().op.mutable_src_extents());
     blocks[1].reader = graph.size() - 1;
     blocks[2].reader = graph.size() - 1;
@@ -184,7 +186,7 @@
     AppendBlockToExtents(&extents, 3);
     AppendBlockToExtents(&extents, 5);
     AppendBlockToExtents(&extents, 6);
-    DeltaDiffGenerator::StoreExtents(extents,
+    StoreExtents(extents,
                                      graph.back().op.mutable_dst_extents());
     blocks[3].writer = graph.size() - 1;
     blocks[5].writer = graph.size() - 1;
@@ -501,4 +503,16 @@
   EXPECT_EQ(34, vertex.op.dst_extents(0).num_blocks());
 }
 
+TEST_F(InplaceGeneratorTest, ApplyMapTest) {
+  vector<uint64_t> collection = {1, 2, 3, 4, 6};
+  vector<uint64_t> expected_values = {1, 2, 5, 4, 8};
+  map<uint64_t, uint64_t> value_map;
+  value_map[3] = 5;
+  value_map[6] = 8;
+  value_map[5] = 10;
+
+  InplaceGenerator::ApplyMap(&collection, value_map);
+  EXPECT_EQ(expected_values, collection);
+}
+
 }  // namespace chromeos_update_engine
diff --git a/payload_generator/payload_file.cc b/payload_generator/payload_file.cc
new file mode 100644
index 0000000..fe453a2
--- /dev/null
+++ b/payload_generator/payload_file.cc
@@ -0,0 +1,319 @@
+// Copyright 2015 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.
+
+#include "update_engine/payload_generator/payload_file.h"
+
+#include <algorithm>
+
+#include "update_engine/file_writer.h"
+#include "update_engine/omaha_hash_calculator.h"
+#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/annotated_operation.h"
+#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/delta_diff_utils.h"
+#include "update_engine/payload_generator/payload_signer.h"
+
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+
+const uint64_t kMajorVersionNumber = 1;
+
+static const char* kInstallOperationTypes[] = {
+  "REPLACE",
+  "REPLACE_BZ",
+  "MOVE",
+  "BSDIFF",
+  "SOURCE_COPY",
+  "SOURCE_BSDIFF"
+};
+
+struct DeltaObject {
+  DeltaObject(const string& in_name, const int in_type, const off_t in_size)
+      : name(in_name),
+        type(in_type),
+        size(in_size) {}
+  bool operator <(const DeltaObject& object) const {
+    return (size != object.size) ? (size < object.size) : (name < object.name);
+  }
+  string name;
+  int type;
+  off_t size;
+};
+
+// Writes the uint64_t passed in in host-endian to the file as big-endian.
+// Returns true on success.
+bool WriteUint64AsBigEndian(FileWriter* writer, const uint64_t value) {
+  uint64_t value_be = htobe64(value);
+  TEST_AND_RETURN_FALSE(writer->Write(&value_be, sizeof(value_be)));
+  return true;
+}
+
+}  // namespace
+
+const vector<PartitionName> PayloadFile::partition_disk_order_ = {
+  PartitionName::kRootfs,
+  PartitionName::kKernel,
+};
+
+bool PayloadFile::Init(const PayloadGenerationConfig& config) {
+  manifest_.set_minor_version(config.minor_version);
+
+  if (!config.source.ImageInfoIsEmpty())
+    *(manifest_.mutable_old_image_info()) = config.source.image_info;
+
+  if (!config.target.ImageInfoIsEmpty())
+    *(manifest_.mutable_new_image_info()) = config.target.image_info;
+
+  manifest_.set_block_size(config.block_size);
+
+  // Initialize the PartitionInfo objects if present.
+  if (!config.source.kernel.path.empty()) {
+    TEST_AND_RETURN_FALSE(diff_utils::InitializePartitionInfo(
+        config.source.kernel,
+        manifest_.mutable_old_kernel_info()));
+  }
+  TEST_AND_RETURN_FALSE(diff_utils::InitializePartitionInfo(
+      config.target.kernel,
+      manifest_.mutable_new_kernel_info()));
+  if (!config.source.rootfs.path.empty()) {
+    TEST_AND_RETURN_FALSE(diff_utils::InitializePartitionInfo(
+        config.source.rootfs,
+        manifest_.mutable_old_rootfs_info()));
+  }
+  TEST_AND_RETURN_FALSE(diff_utils::InitializePartitionInfo(
+      config.target.rootfs,
+      manifest_.mutable_new_rootfs_info()));
+  return true;
+}
+
+void PayloadFile::AddPartitionOperations(
+    PartitionName name,
+    const vector<AnnotatedOperation>& aops) {
+  aops_map_[name].insert(aops_map_[name].end(), aops.begin(), aops.end());
+}
+
+bool PayloadFile::WritePayload(const string& payload_file,
+                               const string& data_blobs_path,
+                               const string& private_key_path,
+                               uint64_t* medatata_size_out) {
+  // Reorder the data blobs with the manifest_.
+  string ordered_blobs_path;
+  TEST_AND_RETURN_FALSE(utils::MakeTempFile(
+      "CrAU_temp_data.ordered.XXXXXX",
+      &ordered_blobs_path,
+      nullptr));
+  ScopedPathUnlinker ordered_blobs_unlinker(ordered_blobs_path);
+  TEST_AND_RETURN_FALSE(ReorderDataBlobs(data_blobs_path, ordered_blobs_path));
+
+  // Copy the operations from the aops_map_ to the manifest.
+  manifest_.clear_install_operations();
+  manifest_.clear_kernel_install_operations();
+  for (PartitionName name : partition_disk_order_) {
+    for (const AnnotatedOperation& aop : aops_map_[name]) {
+      if (name == PartitionName::kKernel) {
+        *manifest_.add_kernel_install_operations() = aop.op;
+      } else {
+        *manifest_.add_install_operations() = aop.op;
+      }
+    }
+  }
+
+  // Check that install op blobs are in order.
+  uint64_t next_blob_offset = 0;
+  {
+    for (int i = 0; i < (manifest_.install_operations_size() +
+                         manifest_.kernel_install_operations_size()); i++) {
+      DeltaArchiveManifest_InstallOperation* op =
+          i < manifest_.install_operations_size() ?
+          manifest_.mutable_install_operations(i) :
+          manifest_.mutable_kernel_install_operations(
+              i - manifest_.install_operations_size());
+      if (op->has_data_offset()) {
+        if (op->data_offset() != next_blob_offset) {
+          LOG(FATAL) << "bad blob offset! " << op->data_offset() << " != "
+                     << next_blob_offset;
+        }
+        next_blob_offset += op->data_length();
+      }
+    }
+  }
+
+  // Signatures appear at the end of the blobs. Note the offset in the
+  // manifest_.
+  if (!private_key_path.empty()) {
+    uint64_t signature_blob_length = 0;
+    TEST_AND_RETURN_FALSE(
+        PayloadSigner::SignatureBlobLength(vector<string>(1, private_key_path),
+                                           &signature_blob_length));
+    AddSignatureOp(next_blob_offset, signature_blob_length, &manifest_);
+  }
+
+    // Serialize protobuf
+  string serialized_manifest;
+  TEST_AND_RETURN_FALSE(manifest_.AppendToString(&serialized_manifest));
+
+  LOG(INFO) << "Writing final delta file header...";
+  DirectFileWriter writer;
+  TEST_AND_RETURN_FALSE_ERRNO(writer.Open(payload_file.c_str(),
+                                          O_WRONLY | O_CREAT | O_TRUNC,
+                                          0644) == 0);
+  ScopedFileWriterCloser writer_closer(&writer);
+
+  // Write header
+  TEST_AND_RETURN_FALSE(writer.Write(kDeltaMagic, strlen(kDeltaMagic)));
+
+  // Write major version number
+  TEST_AND_RETURN_FALSE(WriteUint64AsBigEndian(&writer, kMajorVersionNumber));
+
+  // Write protobuf length
+  TEST_AND_RETURN_FALSE(WriteUint64AsBigEndian(&writer,
+                                               serialized_manifest.size()));
+
+  // Write protobuf
+  LOG(INFO) << "Writing final delta file protobuf... "
+            << serialized_manifest.size();
+  TEST_AND_RETURN_FALSE(writer.Write(serialized_manifest.data(),
+                                     serialized_manifest.size()));
+
+  // Append the data blobs
+  LOG(INFO) << "Writing final delta file data blobs...";
+  int blobs_fd = open(ordered_blobs_path.c_str(), O_RDONLY, 0);
+  ScopedFdCloser blobs_fd_closer(&blobs_fd);
+  TEST_AND_RETURN_FALSE(blobs_fd >= 0);
+  for (;;) {
+    vector<char> buf(1024 * 1024);
+    ssize_t rc = read(blobs_fd, buf.data(), buf.size());
+    if (0 == rc) {
+      // EOF
+      break;
+    }
+    TEST_AND_RETURN_FALSE_ERRNO(rc > 0);
+    TEST_AND_RETURN_FALSE(writer.Write(buf.data(), rc));
+  }
+
+  // Write signature blob.
+  if (!private_key_path.empty()) {
+    LOG(INFO) << "Signing the update...";
+    chromeos::Blob signature_blob;
+    TEST_AND_RETURN_FALSE(PayloadSigner::SignPayload(
+        payload_file,
+        vector<string>(1, private_key_path),
+        &signature_blob));
+    TEST_AND_RETURN_FALSE(writer.Write(signature_blob.data(),
+                                       signature_blob.size()));
+  }
+
+  *medatata_size_out =
+      strlen(kDeltaMagic) + 2 * sizeof(uint64_t) + serialized_manifest.size();
+  ReportPayloadUsage(*medatata_size_out);
+  return true;
+}
+
+bool PayloadFile::ReorderDataBlobs(
+    const string& data_blobs_path,
+    const string& new_data_blobs_path) {
+  int in_fd = open(data_blobs_path.c_str(), O_RDONLY, 0);
+  TEST_AND_RETURN_FALSE_ERRNO(in_fd >= 0);
+  ScopedFdCloser in_fd_closer(&in_fd);
+
+  DirectFileWriter writer;
+  TEST_AND_RETURN_FALSE(
+      writer.Open(new_data_blobs_path.c_str(),
+                  O_WRONLY | O_TRUNC | O_CREAT,
+                  0644) == 0);
+  ScopedFileWriterCloser writer_closer(&writer);
+  uint64_t out_file_size = 0;
+
+  for (PartitionName name : partition_disk_order_) {
+    for (AnnotatedOperation& aop : aops_map_[name]) {
+      if (!aop.op.has_data_offset())
+        continue;
+      CHECK(aop.op.has_data_length());
+      chromeos::Blob buf(aop.op.data_length());
+      ssize_t rc = pread(in_fd, buf.data(), buf.size(), aop.op.data_offset());
+      TEST_AND_RETURN_FALSE(rc == static_cast<ssize_t>(buf.size()));
+
+      // Add the hash of the data blobs for this operation
+      TEST_AND_RETURN_FALSE(AddOperationHash(&aop.op, buf));
+
+      aop.op.set_data_offset(out_file_size);
+      TEST_AND_RETURN_FALSE(writer.Write(buf.data(), buf.size()));
+      out_file_size += buf.size();
+    }
+  }
+  return true;
+}
+
+bool PayloadFile::AddOperationHash(
+    DeltaArchiveManifest_InstallOperation* op,
+    const chromeos::Blob& buf) {
+  OmahaHashCalculator hasher;
+  TEST_AND_RETURN_FALSE(hasher.Update(buf.data(), buf.size()));
+  TEST_AND_RETURN_FALSE(hasher.Finalize());
+  const chromeos::Blob& hash = hasher.raw_hash();
+  op->set_data_sha256_hash(hash.data(), hash.size());
+  return true;
+}
+
+void PayloadFile::ReportPayloadUsage(uint64_t metadata_size) const {
+  vector<DeltaObject> objects;
+  off_t total_size = 0;
+
+  for (PartitionName name : partition_disk_order_) {
+    const auto& partition_aops = aops_map_.find(name);
+    if (partition_aops == aops_map_.end())
+      continue;
+    for (const AnnotatedOperation& aop : partition_aops->second) {
+      objects.push_back(DeltaObject(aop.name,
+                                    aop.op.type(),
+                                    aop.op.data_length()));
+      total_size += aop.op.data_length();
+    }
+  }
+
+  objects.push_back(DeltaObject("<manifest-metadata>",
+                                -1,
+                                metadata_size));
+  total_size += metadata_size;
+
+  std::sort(objects.begin(), objects.end());
+
+  static const char kFormatString[] = "%6.2f%% %10jd %-10s %s\n";
+  for (const DeltaObject& object : objects) {
+    fprintf(stderr, kFormatString,
+            object.size * 100.0 / total_size,
+            static_cast<intmax_t>(object.size),
+            object.type >= 0 ? kInstallOperationTypes[object.type] : "-",
+            object.name.c_str());
+  }
+  fprintf(stderr, kFormatString,
+          100.0, static_cast<intmax_t>(total_size), "", "<total>");
+}
+
+void AddSignatureOp(uint64_t signature_blob_offset,
+                    uint64_t signature_blob_length,
+                    DeltaArchiveManifest* manifest) {
+  LOG(INFO) << "Making room for signature in file";
+  manifest->set_signatures_offset(signature_blob_offset);
+  LOG(INFO) << "set? " << manifest->has_signatures_offset();
+  // Add a dummy op at the end to appease older clients
+  DeltaArchiveManifest_InstallOperation* dummy_op =
+      manifest->add_kernel_install_operations();
+  dummy_op->set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+  dummy_op->set_data_offset(signature_blob_offset);
+  manifest->set_signatures_offset(signature_blob_offset);
+  dummy_op->set_data_length(signature_blob_length);
+  manifest->set_signatures_size(signature_blob_length);
+  Extent* dummy_extent = dummy_op->add_dst_extents();
+  // Tell the dummy op to write this data to a big sparse hole
+  dummy_extent->set_start_block(kSparseHole);
+  dummy_extent->set_num_blocks((signature_blob_length + kBlockSize - 1) /
+                               kBlockSize);
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/payload_file.h b/payload_generator/payload_file.h
new file mode 100644
index 0000000..150b0b0
--- /dev/null
+++ b/payload_generator/payload_file.h
@@ -0,0 +1,86 @@
+// Copyright 2015 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.
+
+#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_PAYLOAD_FILE_H_
+#define UPDATE_ENGINE_PAYLOAD_GENERATOR_PAYLOAD_FILE_H_
+
+#include <map>
+#include <string>
+#include <vector>
+
+#include <chromeos/secure_blob.h>
+#include <gtest/gtest_prod.h>  // for FRIEND_TEST
+
+#include "update_engine/payload_generator/annotated_operation.h"
+#include "update_engine/payload_generator/payload_generation_config.h"
+#include "update_engine/update_metadata.pb.h"
+
+namespace chromeos_update_engine {
+
+// Class to handle the creation of a payload file. This class is the only one
+// dealing with writing the payload and its format, but has no logic about what
+// should be on it.
+class PayloadFile {
+ public:
+  // Initialize the payload file with the payload generation config. It computes
+  // required hashes of the requested partitions.
+  bool Init(const PayloadGenerationConfig& config);
+
+  // Sets the list of operations to the payload manifest. The operations
+  // reference a blob stored in the file provided to WritePayload().
+  void AddPartitionOperations(PartitionName name,
+                              const std::vector<AnnotatedOperation>& aops);
+
+  // Write the payload to the |payload_file| file. The operations reference
+  // blobs in the |data_blobs_path| file and the blobs will be reordered in the
+  // payload file to match the order of the operations. The size of the metadata
+  // section of the payload is stored in |metadata_size_out|.
+  bool WritePayload(const std::string& payload_file,
+                    const std::string& data_blobs_path,
+                    const std::string& private_key_path,
+                    uint64_t* medatata_size_out);
+
+ private:
+  FRIEND_TEST(PayloadFileTest, ReorderBlobsTest);
+
+  // Computes a SHA256 hash of the given buf and sets the hash value in the
+  // operation so that update_engine could verify. This hash should be set
+  // for all operations that have a non-zero data blob. One exception is the
+  // dummy operation for signature blob because the contents of the signature
+  // blob will not be available at payload creation time. So, update_engine will
+  // gracefully ignore the dummy signature operation.
+  static bool AddOperationHash(DeltaArchiveManifest_InstallOperation* op,
+                               const chromeos::Blob& buf);
+
+  // Install operations in the manifest may reference data blobs, which
+  // are in data_blobs_path. This function creates a new data blobs file
+  // with the data blobs in the same order as the referencing install
+  // operations in the manifest. E.g. if manifest[0] has a data blob
+  // "X" at offset 1, manifest[1] has a data blob "Y" at offset 0,
+  // and data_blobs_path's file contains "YX", new_data_blobs_path
+  // will set to be a file that contains "XY".
+  bool ReorderDataBlobs(const std::string& data_blobs_path,
+                        const std::string& new_data_blobs_path);
+
+  // Print in stderr the Payload usage report.
+  void ReportPayloadUsage(uint64_t metadata_size) const;
+
+  // The list of partitions in the order their blobs should appear in the
+  // payload file.
+  static const std::vector<PartitionName> partition_disk_order_;
+
+  DeltaArchiveManifest manifest_;
+
+  std::map<PartitionName, std::vector<AnnotatedOperation>> aops_map_;
+};
+
+// Adds a dummy operation that points to a signature blob located at the
+// specified offset/length.
+void AddSignatureOp(uint64_t signature_blob_offset,
+                    uint64_t signature_blob_length,
+                    DeltaArchiveManifest* manifest);
+
+}  // namespace chromeos_update_engine
+
+#endif  // UPDATE_ENGINE_PAYLOAD_GENERATOR_PAYLOAD_FILE_H_
diff --git a/payload_generator/payload_file_unittest.cc b/payload_generator/payload_file_unittest.cc
new file mode 100644
index 0000000..1d9661f
--- /dev/null
+++ b/payload_generator/payload_file_unittest.cc
@@ -0,0 +1,84 @@
+// Copyright 2015 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.
+
+#include "update_engine/payload_generator/payload_file.h"
+
+#include <string>
+#include <utility>
+#include <vector>
+
+#include <gtest/gtest.h>
+
+#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/extent_ranges.h"
+#include "update_engine/test_utils.h"
+
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+class PayloadFileTest : public ::testing::Test {
+ protected:
+  PayloadFile payload_;
+};
+
+TEST_F(PayloadFileTest, ReorderBlobsTest) {
+  string orig_blobs;
+  EXPECT_TRUE(utils::MakeTempFile("ReorderBlobsTest.orig.XXXXXX", &orig_blobs,
+                                  nullptr));
+  ScopedPathUnlinker orig_blobs_unlinker(orig_blobs);
+
+  // The operations have three blob and one gap (the whitespace):
+  // Rootfs operation 1: [8, 3] bcd
+  // Rootfs operation 2: [7, 1] a
+  // Kernel operation 1: [0, 6] kernel
+  string orig_data = "kernel abcd";
+  EXPECT_TRUE(
+      utils::WriteFile(orig_blobs.c_str(), orig_data.data(), orig_data.size()));
+
+  string new_blobs;
+  EXPECT_TRUE(
+      utils::MakeTempFile("ReorderBlobsTest.new.XXXXXX", &new_blobs, nullptr));
+  ScopedPathUnlinker new_blobs_unlinker(new_blobs);
+
+  vector<AnnotatedOperation> aops;
+  AnnotatedOperation aop;
+  aop.op.set_data_offset(8);
+  aop.op.set_data_length(3);
+  aops.push_back(aop);
+
+  aop.op.set_data_offset(7);
+  aop.op.set_data_length(1);
+  aops.push_back(aop);
+  payload_.AddPartitionOperations(PartitionName::kRootfs, aops);
+
+  aop.op.set_data_offset(0);
+  aop.op.set_data_length(6);
+  aops = {aop};
+  payload_.AddPartitionOperations(PartitionName::kKernel, aops);
+
+  EXPECT_TRUE(payload_.ReorderDataBlobs(orig_blobs, new_blobs));
+
+  const vector<AnnotatedOperation>& rootfs_aops =
+      payload_.aops_map_[PartitionName::kRootfs];
+  const vector<AnnotatedOperation>& kernel_aops =
+      payload_.aops_map_[PartitionName::kKernel];
+  string new_data;
+  EXPECT_TRUE(utils::ReadFile(new_blobs, &new_data));
+  // Kernel blobs should appear at the end.
+  EXPECT_EQ("bcdakernel", new_data);
+
+  EXPECT_EQ(2, rootfs_aops.size());
+  EXPECT_EQ(0, rootfs_aops[0].op.data_offset());
+  EXPECT_EQ(3, rootfs_aops[0].op.data_length());
+  EXPECT_EQ(3, rootfs_aops[1].op.data_offset());
+  EXPECT_EQ(1, rootfs_aops[1].op.data_length());
+
+  EXPECT_EQ(1, kernel_aops.size());
+  EXPECT_EQ(4, kernel_aops[0].op.data_offset());
+  EXPECT_EQ(6, kernel_aops[0].op.data_length());
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/payload_generation_config.h b/payload_generator/payload_generation_config.h
index af9afb5..0f002e1 100644
--- a/payload_generator/payload_generation_config.h
+++ b/payload_generator/payload_generation_config.h
@@ -14,7 +14,15 @@
 
 namespace chromeos_update_engine {
 
+// The list different kind of partitions supported by the updater.
+enum class PartitionName {
+  kKernel,
+  kRootfs,
+};
+
 struct PartitionConfig {
+  explicit PartitionConfig(PartitionName name) : name(name) {}
+
   // Returns whether the PartitionConfig is not an empty image and all the
   // fields are set correctly to a valid image file.
   bool ValidateExists() const;
@@ -30,6 +38,8 @@
   // the source image, and the size of that data it should generate for the
   // target image.
   uint64_t size = 0;
+
+  PartitionName name;
 };
 
 // The ImageConfig struct describes a pair of binaries kernel and rootfs and the
@@ -60,8 +70,8 @@
   ImageInfo image_info;
 
   // The updated partitions.
-  PartitionConfig rootfs;
-  PartitionConfig kernel;
+  PartitionConfig rootfs = PartitionConfig{PartitionName::kRootfs};
+  PartitionConfig kernel = PartitionConfig{PartitionName::kKernel};
 };
 
 // The PayloadGenerationConfig struct encapsulates all the configuration to
diff --git a/payload_generator/payload_signer.cc b/payload_generator/payload_signer.cc
index eec8d7a..8c3bc28 100644
--- a/payload_generator/payload_signer.cc
+++ b/payload_generator/payload_signer.cc
@@ -11,7 +11,7 @@
 #include <openssl/pem.h>
 
 #include "update_engine/omaha_hash_calculator.h"
-#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/payload_file.h"
 #include "update_engine/payload_verifier.h"
 #include "update_engine/subprocess.h"
 #include "update_engine/update_metadata.pb.h"
@@ -90,9 +90,9 @@
     LOG(INFO) << "Matching signature sizes already present.";
   } else {
     // Updates the manifest to include the signature operation.
-    DeltaDiffGenerator::AddSignatureOp(payload.size() - metadata_size,
-                                       signature_blob_size,
-                                       &manifest);
+    AddSignatureOp(payload.size() - metadata_size,
+                   signature_blob_size,
+                   &manifest);
 
     // Updates the payload to include the new manifest.
     string serialized_manifest;