diff --git a/payload_generator/block_mapping.cc b/payload_generator/block_mapping.cc
new file mode 100644
index 0000000..734f44f
--- /dev/null
+++ b/payload_generator/block_mapping.cc
@@ -0,0 +1,149 @@
+// 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/block_mapping.h"
+
+#include <fcntl.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+
+#include <functional>
+#include <string>
+#include <vector>
+
+#include "update_engine/utils.h"
+
+using std::string;
+using std::vector;
+
+namespace {
+
+size_t HashValue(const chromeos::Blob& blob) {
+  std::hash<string> hash_fn;
+  return hash_fn(string(blob.begin(), blob.end()));
+}
+
+}  // namespace
+
+namespace chromeos_update_engine {
+
+BlockMapping::BlockId BlockMapping::AddBlock(const chromeos::Blob& block_data) {
+  return AddBlock(-1, 0, block_data);
+}
+
+BlockMapping::BlockId BlockMapping::AddDiskBlock(int fd, off_t byte_offset) {
+  chromeos::Blob blob(block_size_);
+  ssize_t bytes_read = 0;
+  if (!utils::PReadAll(fd, blob.data(), block_size_, byte_offset, &bytes_read))
+    return -1;
+  if (static_cast<size_t>(bytes_read) != block_size_)
+    return -1;
+  return AddBlock(fd, byte_offset, blob);
+}
+
+bool BlockMapping::AddManyDiskBlocks(int fd,
+                                     off_t initial_byte_offset,
+                                     size_t num_blocks,
+                                     std::vector<BlockId>* block_ids) {
+  bool ret = true;
+  block_ids->resize(num_blocks);
+  for (size_t block = 0; block < num_blocks; block++) {
+    (*block_ids)[block] = AddDiskBlock(
+        fd, initial_byte_offset + block * block_size_);
+    ret = ret && (*block_ids)[block] != -1;
+  }
+  return ret;
+}
+
+BlockMapping::BlockId BlockMapping::AddBlock(int fd,
+                                             off_t byte_offset,
+                                             const chromeos::Blob& block_data) {
+  if (block_data.size() != block_size_)
+    return -1;
+  size_t h = HashValue(block_data);
+
+  // We either reuse a UniqueBlock or create a new one. If we need a new
+  // UniqueBlock it could also be part of a new or existing bucket (if there is
+  // a hash collision).
+  vector<UniqueBlock> *bucket = nullptr;
+
+  auto mapping_it = mapping_.find(h);
+  if (mapping_it == mapping_.end()) {
+    bucket = &mapping_[h];
+  } else {
+    for (UniqueBlock& existing_block : mapping_it->second) {
+      bool equals = false;
+      if (!existing_block.CompareData(block_data, &equals))
+        return -1;
+      if (equals)
+        return existing_block.block_id;
+    }
+    bucket = &mapping_it->second;
+  }
+
+  // No existing block was found at this point, so we create and fill in a new
+  // one.
+  bucket->emplace_back();
+  UniqueBlock *new_ublock = &bucket->back();
+
+  new_ublock->times_read = 1;
+  new_ublock->fd = fd;
+  new_ublock->byte_offset = byte_offset;
+  new_ublock->block_id = used_block_ids++;
+  // We need to cache blocks that are not referencing any disk location.
+  if (fd == -1)
+    new_ublock->block_data = block_data;
+
+  return new_ublock->block_id;
+}
+
+bool BlockMapping::UniqueBlock::CompareData(const chromeos::Blob& other_block,
+                                            bool* equals) {
+  if (!block_data.empty()) {
+    *equals = block_data == other_block;
+    return true;
+  }
+  const size_t block_size = other_block.size();
+  chromeos::Blob blob(block_size);
+  ssize_t bytes_read = 0;
+  if (!utils::PReadAll(fd, blob.data(), block_size, byte_offset, &bytes_read))
+    return false;
+  if (static_cast<size_t>(bytes_read) != block_size)
+    return false;
+  *equals = blob == other_block;
+
+  // We increase the number of times we had to read this block from disk and
+  // we cache this block based on that. This caching method is optimized for
+  // the common use case of having two partitions that share blocks between them
+  // but have few repeated blocks inside each partition, such as the block
+  // with all zeros or duplicated files.
+  times_read++;
+  if (times_read > 3)
+    block_data = std::move(blob);
+  return true;
+}
+
+bool MapPartitionBlocks(const string& old_part,
+                        const string& new_part,
+                        size_t old_size,
+                        size_t new_size,
+                        size_t block_size,
+                        vector<BlockMapping::BlockId>* old_block_ids,
+                        vector<BlockMapping::BlockId>* new_block_ids) {
+  BlockMapping mapping(block_size);
+  if (mapping.AddBlock(chromeos::Blob(block_size, '\0')) != 0)
+    return false;
+  int old_fd = HANDLE_EINTR(open(old_part.c_str(), O_RDONLY));
+  int new_fd = HANDLE_EINTR(open(new_part.c_str(), O_RDONLY));
+  ScopedFdCloser old_fd_closer(&old_fd);
+  ScopedFdCloser new_fd_closer(&new_fd);
+
+  TEST_AND_RETURN_FALSE(mapping.AddManyDiskBlocks(
+      old_fd, 0, old_size / block_size, old_block_ids));
+  TEST_AND_RETURN_FALSE(mapping.AddManyDiskBlocks(
+      new_fd, 0, new_size / block_size, new_block_ids));
+  return true;
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/block_mapping.h b/payload_generator/block_mapping.h
new file mode 100644
index 0000000..2cfca56
--- /dev/null
+++ b/payload_generator/block_mapping.h
@@ -0,0 +1,100 @@
+// 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_BLOCK_MAPPING_H_
+#define UPDATE_ENGINE_PAYLOAD_GENERATOR_BLOCK_MAPPING_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/payload_generation_config.h"
+
+namespace chromeos_update_engine {
+
+// BlockMapping allows to map data blocks (chromeos::Blobs of block_size size)
+// into unique integer values called "block ids". This mapping differs from a
+// hash function in that two blocks with the same data will have the same id but
+// also two blocks with the same id will have the same data. This is only valid
+// in the context of the same BlockMapping instance.
+class BlockMapping {
+ public:
+  using BlockId = int64_t;
+
+  explicit BlockMapping(size_t block_size) : block_size_(block_size) {}
+
+  // Add a single data block to the mapping. Returns its unique block id.
+  // In case of error returns -1.
+  BlockId AddBlock(const chromeos::Blob& block_data);
+
+  // Add a block from disk reading it from the file descriptor |fd| from the
+  // offset in bytes |byte_offset|. The data block may or may not be cached, so
+  // the file descriptor must be available until the BlockMapping is destroyed.
+  // Returns the unique block id of the added block or -1 in case of error.
+  BlockId AddDiskBlock(int fd, off_t byte_offset);
+
+  // This is a helper method to add |num_blocks| contiguous blocks reading them
+  // from the file descriptor |fd| starting at offset |initial_byte_offset|.
+  // Returns whether it succeeded to add all the disk blocks and stores in
+  // |block_ids| the block id for each one of the added blocks.
+  bool AddManyDiskBlocks(int fd, off_t initial_byte_offset, size_t num_blocks,
+                         std::vector<BlockId>* block_ids);
+
+ private:
+  FRIEND_TEST(BlockMappingTest, BlocksAreNotKeptInMemory);
+
+  // Add a single block passed in |block_data|. If |fd| is not -1, the block
+  // can be discarded to save RAM and retrieved later from |fd| at the position
+  // |byte_offset|.
+  BlockId AddBlock(int fd, off_t byte_offset, const chromeos::Blob& block_data);
+
+  size_t block_size_;
+
+  BlockId used_block_ids{0};
+
+  // The UniqueBlock represents the data of a block associated to a unique
+  // block id.
+  struct UniqueBlock {
+    chromeos::Blob block_data;
+
+    // The block id assigned to this unique block.
+    BlockId block_id;
+
+    // The location on this unique block on disk (if not cached in block_data).
+    int fd{-1};
+    off_t byte_offset{0};
+
+    // Number of times we have seen this data block. Used for caching.
+    uint32_t times_read{0};
+
+    // Compares the UniqueBlock data with the other_block data and stores if
+    // they are equal in |equals|. Returns whether there was an error reading
+    // the block from disk while comparing it.
+    bool CompareData(const chromeos::Blob& other_block, bool* equals);
+  };
+
+  // A mapping from hash values to possible block ids.
+  std::map<size_t, std::vector<UniqueBlock>> mapping_;
+};
+
+// Maps the blocks of the old and new partitions |old_part| and |new_part| whose
+// size in bytes are |old_size| and |new_size| into block ids where two blocks
+// with the same data will have the same block id and vice versa, regardless of
+// the partition they are on.
+// The block ids number 0 corresponds to the block with all zeros, but any
+// other block id number is assigned randomly.
+bool MapPartitionBlocks(const std::string& old_part,
+                        const std::string& new_part,
+                        size_t old_size,
+                        size_t new_size,
+                        size_t block_size,
+                        std::vector<BlockMapping::BlockId>* old_block_ids,
+                        std::vector<BlockMapping::BlockId>* new_block_ids);
+
+}  // namespace chromeos_update_engine
+
+#endif  // UPDATE_ENGINE_PAYLOAD_GENERATOR_BLOCK_MAPPING_H_
diff --git a/payload_generator/block_mapping_unittest.cc b/payload_generator/block_mapping_unittest.cc
new file mode 100644
index 0000000..699ac60
--- /dev/null
+++ b/payload_generator/block_mapping_unittest.cc
@@ -0,0 +1,122 @@
+// 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/block_mapping.h"
+
+#include <fcntl.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+
+#include <string>
+#include <vector>
+
+#include <gtest/gtest.h>
+
+#include "update_engine/test_utils.h"
+#include "update_engine/utils.h"
+
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+
+}  // namespace
+
+class BlockMappingTest : public ::testing::Test {
+ protected:
+  void SetUp() override {
+    EXPECT_TRUE(utils::MakeTempFile("BlockMappingTest_old.XXXXXX",
+                                    &old_part_path_,
+                                    nullptr));
+    EXPECT_TRUE(utils::MakeTempFile("BlockMappingTest_new.XXXXXX",
+                                    &new_part_path_,
+                                    nullptr));
+
+    old_part_unlinker_.reset(new ScopedPathUnlinker(old_part_path_));
+    new_part_unlinker_.reset(new ScopedPathUnlinker(new_part_path_));
+  }
+
+  // Old new partition files used in testing.
+  string old_part_path_;
+  string new_part_path_;
+  std::unique_ptr<ScopedPathUnlinker> old_part_unlinker_;
+  std::unique_ptr<ScopedPathUnlinker> new_part_unlinker_;
+
+  size_t block_size_{1024};
+  BlockMapping bm_{block_size_};  // BlockMapping under test.
+};
+
+TEST_F(BlockMappingTest, FirstAddedBlockIsZero) {
+  chromeos::Blob blob(block_size_);
+  // The BlockMapping just assigns the block ids in order, so it doesn't matter
+  // what are the contents of the first block.
+  blob[0] = 42;
+  EXPECT_EQ(0, bm_.AddBlock(blob));
+  blob[0] = 5;
+  EXPECT_EQ(1, bm_.AddBlock(blob));
+}
+
+TEST_F(BlockMappingTest, BlocksAreNotKeptInMemory) {
+  test_utils::WriteFileString(old_part_path_, string(block_size_, 'a'));
+  int old_fd = HANDLE_EINTR(open(old_part_path_.c_str(), O_RDONLY));
+  ScopedFdCloser old_fd_closer(&old_fd);
+
+  EXPECT_EQ(0, bm_.AddDiskBlock(old_fd, 0));
+
+  // Check that the block_data is not stored on memory if we just used the block
+  // once.
+  for (const auto& it : bm_.mapping_) {
+    for (const BlockMapping::UniqueBlock& ublock : it.second) {
+      EXPECT_TRUE(ublock.block_data.empty());
+    }
+  }
+
+  chromeos::Blob block(block_size_, 'a');
+  for (int i = 0; i < 5; ++i) {
+    // Re-add the same block 5 times.
+    EXPECT_EQ(0, bm_.AddBlock(block));
+  }
+
+  for (const auto& it : bm_.mapping_) {
+    for (const BlockMapping::UniqueBlock& ublock : it.second) {
+      EXPECT_FALSE(ublock.block_data.empty());
+      // The block was loaded from disk only 4 times, and after that the counter
+      // is not updated anymore.
+      EXPECT_EQ(4, ublock.times_read);
+    }
+  }
+}
+
+TEST_F(BlockMappingTest, MapPartitionBlocks) {
+  // A string with 10 blocks where all the blocks are different.
+  string old_contents(10 * block_size_, '\0');
+  for (size_t i = 0; i < old_contents.size(); ++i)
+    old_contents[i] = 4 + i / block_size_;
+  test_utils::WriteFileString(old_part_path_, old_contents);
+
+  // A string including the block with all zeros and overlapping some of the
+  // other blocks in old_contents.
+  string new_contents(6 * block_size_, '\0');
+  for (size_t i = 0; i < new_contents.size(); ++i)
+    new_contents[i] = i / block_size_;
+  test_utils::WriteFileString(new_part_path_, new_contents);
+
+  vector<BlockMapping::BlockId> old_ids, new_ids;
+  EXPECT_TRUE(MapPartitionBlocks(old_part_path_,
+                                 new_part_path_,
+                                 old_contents.size(),
+                                 new_contents.size(),
+                                 block_size_,
+                                 &old_ids,
+                                 &new_ids));
+
+  EXPECT_EQ((vector<BlockMapping::BlockId>{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}),
+            old_ids);
+  EXPECT_EQ((vector<BlockMapping::BlockId>{0, 11, 12, 13, 1, 2}),
+            new_ids);
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/delta_diff_utils.cc b/payload_generator/delta_diff_utils.cc
index 6c15919..2d56b68 100644
--- a/payload_generator/delta_diff_utils.cc
+++ b/payload_generator/delta_diff_utils.cc
@@ -13,6 +13,7 @@
 
 #include "update_engine/bzip.h"
 #include "update_engine/omaha_hash_calculator.h"
+#include "update_engine/payload_generator/block_mapping.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"
@@ -21,7 +22,6 @@
 
 using std::map;
 using std::string;
-using std::unique_ptr;
 using std::vector;
 
 namespace chromeos_update_engine {
@@ -160,6 +160,19 @@
     new_visited_blocks.AddBlock(0);
   }
 
+  TEST_AND_RETURN_FALSE(DeltaMovedAndZeroBlocks(
+      aops,
+      old_part.path,
+      new_part.path,
+      old_part.fs_interface ? old_part.fs_interface->GetBlockCount() : 0,
+      new_part.fs_interface->GetBlockCount(),
+      chunk_blocks,
+      src_ops_allowed,
+      data_fd,
+      data_file_size,
+      &old_visited_blocks,
+      &new_visited_blocks));
+
   map<string, vector<Extent>> old_files_map;
   if (old_part.fs_interface) {
     vector<FilesystemInterface::File> old_files;
@@ -249,6 +262,152 @@
   return true;
 }
 
+bool DeltaMovedAndZeroBlocks(
+    vector<AnnotatedOperation>* aops,
+    const string& old_part,
+    const string& new_part,
+    size_t old_num_blocks,
+    size_t new_num_blocks,
+    off_t chunk_blocks,
+    bool src_ops_allowed,
+    int data_fd,
+    off_t* data_file_size,
+    ExtentRanges* old_visited_blocks,
+    ExtentRanges* new_visited_blocks) {
+  vector<BlockMapping::BlockId> old_block_ids;
+  vector<BlockMapping::BlockId> new_block_ids;
+  TEST_AND_RETURN_FALSE(MapPartitionBlocks(old_part,
+                                           new_part,
+                                           old_num_blocks * kBlockSize,
+                                           new_num_blocks * kBlockSize,
+                                           kBlockSize,
+                                           &old_block_ids,
+                                           &new_block_ids));
+
+  // For minor-version=1, we map all the blocks that didn't move, regardless of
+  // the contents since they are already copied and no operation is required.
+  if (!src_ops_allowed) {
+    uint64_t num_blocks = std::min(old_num_blocks, new_num_blocks);
+    for (uint64_t block = 0; block < num_blocks; block++) {
+      if (old_block_ids[block] == new_block_ids[block] &&
+          !old_visited_blocks->ContainsBlock(block) &&
+          !new_visited_blocks->ContainsBlock(block)) {
+        old_visited_blocks->AddBlock(block);
+        new_visited_blocks->AddBlock(block);
+      }
+    }
+  }
+
+  // A mapping from the block_id to the list of block numbers with that block id
+  // in the old partition. This is used to lookup where in the old partition
+  // is a block from the new partition.
+  map<BlockMapping::BlockId, vector<uint64_t>> old_blocks_map;
+
+  for (uint64_t block = old_num_blocks; block-- > 0; ) {
+    if (old_block_ids[block] != 0 && !old_visited_blocks->ContainsBlock(block))
+      old_blocks_map[old_block_ids[block]].push_back(block);
+  }
+
+  // The collection of blocks in the new partition with just zeros. This is a
+  // common case for free-space that's also problematic for bsdiff, so we want
+  // to optimize it using REPLACE_BZ operations. The blob for a REPLACE_BZ of
+  // just zeros is so small that it doesn't make sense to spend the I/O reading
+  // zeros from the old partition.
+  vector<Extent> new_zeros;
+
+  vector<Extent> old_identical_blocks;
+  vector<Extent> new_identical_blocks;
+
+  for (uint64_t block = 0; block < new_num_blocks; block++) {
+    // Only produce operations for blocks that were not yet visited.
+    if (new_visited_blocks->ContainsBlock(block))
+      continue;
+    if (new_block_ids[block] == 0) {
+      AppendBlockToExtents(&new_zeros, block);
+      continue;
+    }
+
+    auto old_blocks_map_it = old_blocks_map.find(new_block_ids[block]);
+    // Check if the block exists in the old partition at all.
+    if (old_blocks_map_it == old_blocks_map.end() ||
+        old_blocks_map_it->second.empty())
+      continue;
+
+    AppendBlockToExtents(&old_identical_blocks,
+                         old_blocks_map_it->second.back());
+    AppendBlockToExtents(&new_identical_blocks, block);
+    // We can't reuse source blocks in minor version 1 because the cycle
+    // breaking algorithm doesn't support that.
+    if (!src_ops_allowed)
+      old_blocks_map_it->second.pop_back();
+  }
+
+  // Produce operations for the zero blocks split per output extent.
+  size_t num_ops = aops->size();
+  new_visited_blocks->AddExtents(new_zeros);
+  for (Extent extent : new_zeros) {
+    TEST_AND_RETURN_FALSE(DeltaReadFile(
+        aops,
+        "",
+        new_part,
+        vector<Extent>(),  // old_extents
+        vector<Extent>{extent},  // new_extents
+        "<zeros>",
+        chunk_blocks,
+        data_fd,
+        data_file_size,
+        src_ops_allowed));
+  }
+  LOG(INFO) << "Produced " << (aops->size() - num_ops) << " operations for "
+            << BlocksInExtents(new_zeros) << " zeroed blocks";
+
+  // Produce MOVE/SOURCE_COPY operations for the moved blocks.
+  num_ops = aops->size();
+  if (chunk_blocks == -1)
+    chunk_blocks = new_num_blocks;
+  uint64_t used_blocks = 0;
+  old_visited_blocks->AddExtents(old_identical_blocks);
+  new_visited_blocks->AddExtents(new_identical_blocks);
+  for (Extent extent : new_identical_blocks) {
+    // We split the operation at the extent boundary or when bigger than
+    // chunk_blocks.
+    for (uint64_t op_block_offset = 0; op_block_offset < extent.num_blocks();
+         op_block_offset += chunk_blocks) {
+      aops->emplace_back();
+      AnnotatedOperation* aop = &aops->back();
+      aop->name = "<identical-blocks>";
+      aop->op.set_type(src_ops_allowed ?
+                       DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY :
+                       DeltaArchiveManifest_InstallOperation_Type_MOVE);
+
+      uint64_t chunk_num_blocks =
+        std::min(extent.num_blocks() - op_block_offset,
+                 static_cast<uint64_t>(chunk_blocks));
+
+      // The current operation represents the move/copy operation for the
+      // sublist starting at |used_blocks| of length |chunk_num_blocks| where
+      // the src and dst are from |old_identical_blocks| and
+      // |new_identical_blocks| respectively.
+      StoreExtents(
+          ExtentsSublist(old_identical_blocks, used_blocks, chunk_num_blocks),
+          aop->op.mutable_src_extents());
+
+      Extent* op_dst_extent = aop->op.add_dst_extents();
+      op_dst_extent->set_start_block(extent.start_block() + op_block_offset);
+      op_dst_extent->set_num_blocks(chunk_num_blocks);
+      CHECK(
+          vector<Extent>{*op_dst_extent} ==  // NOLINT(whitespace/braces)
+          ExtentsSublist(new_identical_blocks, used_blocks, chunk_num_blocks));
+
+      used_blocks += chunk_num_blocks;
+    }
+  }
+  LOG(INFO) << "Produced " << (aops->size() - num_ops) << " operations for "
+            << used_blocks << " identical blocks moved";
+
+  return true;
+}
+
 bool DeltaReadFile(
     vector<AnnotatedOperation>* aops,
     const string& old_part,
diff --git a/payload_generator/delta_diff_utils.h b/payload_generator/delta_diff_utils.h
index 0be8666..d85249d 100644
--- a/payload_generator/delta_diff_utils.h
+++ b/payload_generator/delta_diff_utils.h
@@ -11,6 +11,7 @@
 #include <chromeos/secure_blob.h>
 
 #include "update_engine/payload_generator/annotated_operation.h"
+#include "update_engine/payload_generator/extent_ranges.h"
 #include "update_engine/payload_generator/payload_generation_config.h"
 #include "update_engine/update_metadata.pb.h"
 
@@ -33,6 +34,29 @@
                         bool skip_block_0,
                         bool src_ops_allowed);
 
+// Create operations in |aops| for identical blocks that moved around in the old
+// and new partition and also handle zeroed blocks. The old and new partition
+// are stored in the |old_part| and |new_part| files and have |old_num_blocks|
+// and |new_num_blocks| respectively. The maximum operation size is
+// |chunk_blocks| blocks, or unlimited if |chunk_blocks| is -1. The blobs of the
+// produced operations are stored in the |data_fd| file whose size is updated
+// in the value pointed by |data_file_size|.
+// The collections |old_visited_blocks| and |new_visited_blocks| state what
+// blocks already have operations reading or writing them and only operations
+// for unvisited blocks are produced by this function updating both collections
+// with the used blocks.
+bool DeltaMovedAndZeroBlocks(std::vector<AnnotatedOperation>* aops,
+                             const std::string& old_part,
+                             const std::string& new_part,
+                             size_t old_num_blocks,
+                             size_t new_num_blocks,
+                             off_t chunk_blocks,
+                             bool src_ops_allowed,
+                             int data_fd,
+                             off_t* data_file_size,
+                             ExtentRanges* old_visited_blocks,
+                             ExtentRanges* new_visited_blocks);
+
 // 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
diff --git a/payload_generator/delta_diff_utils_unittest.cc b/payload_generator/delta_diff_utils_unittest.cc
index 2157aa1..3b1d44d 100644
--- a/payload_generator/delta_diff_utils_unittest.cc
+++ b/payload_generator/delta_diff_utils_unittest.cc
@@ -9,6 +9,8 @@
 #include <vector>
 
 #include <base/files/scoped_file.h>
+#include <base/format_macros.h>
+#include <base/strings/stringprintf.h>
 #include <gtest/gtest.h>
 
 #include "update_engine/payload_generator/delta_diff_generator.h"
@@ -19,7 +21,6 @@
 #include "update_engine/utils.h"
 
 using std::string;
-using std::unique_ptr;
 using std::vector;
 
 namespace chromeos_update_engine {
@@ -51,61 +52,117 @@
   return true;
 }
 
+// Create a fake filesystem of the given |size| and initialize the partition
+// holding it in the PartitionConfig |part|.
+void CreatePartition(PartitionConfig* part, const string& pattern,
+                     uint64_t block_size, off_t size) {
+  int fd = -1;
+  ASSERT_TRUE(utils::MakeTempFile(pattern.c_str(), &part->path, &fd));
+  ASSERT_EQ(0, ftruncate(fd, size));
+  ASSERT_EQ(0, close(fd));
+  part->fs_interface.reset(new FakeFilesystem(block_size, size / block_size));
+  part->size = size;
+}
+
+// Writes to the |partition| path blocks such they are all different and they
+// include the tag passed in |tag|, making them also different to any other
+// block on a partition initialized with this function with a different tag.
+// The |block_size| should be a divisor of the partition size.
+// Returns whether the function succeeded writing the partition.
+bool InitializePartitionWithUniqueBlocks(const PartitionConfig& part,
+                                         uint64_t block_size,
+                                         uint64_t tag) {
+  TEST_AND_RETURN_FALSE(part.size % block_size == 0);
+  size_t num_blocks = part.size / block_size;
+  chromeos::Blob file_data(part.size);
+  for (size_t i = 0; i < num_blocks; ++i) {
+    string prefix = base::StringPrintf(
+        "block tag 0x%.16" PRIx64 ", block number %16" PRIuS " ", tag, i);
+    chromeos::Blob block_data(prefix.begin(), prefix.end());
+    TEST_AND_RETURN_FALSE(prefix.size() <= block_size);
+    block_data.resize(block_size, 'X');
+    std::copy(block_data.begin(), block_data.end(),
+              file_data.begin() + i * block_size);
+  }
+  return test_utils::WriteFileVector(part.path, file_data);
+}
+
 }  // namespace
 
 class DeltaDiffUtilsTest : public ::testing::Test {
  protected:
-  const uint64_t kFilesystemSize = kBlockSize * 1024;
+  const uint64_t kDefaultBlockCount = 128;
 
   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);
+    CreatePartition(&old_part_, "DeltaDiffUtilsTest-old_part-XXXXXX",
+                    block_size_, block_size_ * kDefaultBlockCount);
+    CreatePartition(&new_part_, "DeltaDiffUtilsTest-old_part-XXXXXX",
+                    block_size_, block_size_ * kDefaultBlockCount);
+    ASSERT_TRUE(utils::MakeTempFile("DeltaDiffUtilsTest-blob-XXXXXX",
+                                    &blob_path_,
+                                    &blob_fd_));
   }
 
   void TearDown() override {
-    unlink(old_part_path_.c_str());
-    unlink(new_part_path_.c_str());
+    unlink(old_part_.path.c_str());
+    unlink(new_part_.path.c_str());
+    if (blob_fd_ != -1)
+      close(blob_fd_);
+    unlink(blob_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));
+  // Helper function to call DeltaMovedAndZeroBlocks() using this class' data
+  // members. This simply avoid repeating all the arguments that never change.
+  bool RunDeltaMovedAndZeroBlocks(off_t chunk_blocks,
+                                  bool src_ops_allowed) {
+    return diff_utils::DeltaMovedAndZeroBlocks(
+        &aops_,
+        old_part_.path,
+        new_part_.path,
+        old_part_.size / block_size_,
+        new_part_.size / block_size_,
+        chunk_blocks,
+        src_ops_allowed,
+        blob_fd_,
+        &blob_size_,
+        &old_visited_blocks_,
+        &new_visited_blocks_);
   }
 
-  // Paths to old and new temporary filesystems used in the tests.
-  string old_part_path_;
-  string new_part_path_;
+  // Old and new temporary partitions used in the tests. These are initialized
+  // with
+  PartitionConfig old_part_{PartitionName::kRootfs};
+  PartitionConfig new_part_{PartitionName::kRootfs};
 
-  // FilesystemInterface fake implementations used to mock out the file/block
-  // distribution.
-  unique_ptr<FakeFilesystem> old_fs_;
-  unique_ptr<FakeFilesystem> new_fs_;
+  // The file holding the output blob from the various diff utils functions.
+  string blob_path_;
+  int blob_fd_{-1};
+  off_t blob_size_{0};
+
+  size_t block_size_{kBlockSize};
+
+  // Default input/output arguments used when calling DeltaMovedAndZeroBlocks().
+  vector<AnnotatedOperation> aops_;
+  ExtentRanges old_visited_blocks_;
+  ExtentRanges new_visited_blocks_;
 };
 
 TEST_F(DeltaDiffUtilsTest, MoveSmallTest) {
-  chromeos::Blob data_blob(kBlockSize);
+  chromeos::Blob data_blob(block_size_);
   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));
+  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_part_.path,
+      new_part_.path,
       old_extents,
       new_extents,
       true,  // bsdiff_allowed
@@ -158,14 +215,14 @@
     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));
+  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_part_.path,
+      new_part_.path,
       old_extents,
       new_extents,
       true,  // bsdiff_allowed
@@ -220,16 +277,16 @@
   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(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));
+  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_part_.path,
+      new_part_.path,
       old_extents,
       new_extents,
       true,  // bsdiff_allowed
@@ -262,16 +319,16 @@
   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(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));
+  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_part_.path,
+      new_part_.path,
       old_extents,
       new_extents,
       false,  // bsdiff_allowed
@@ -295,14 +352,14 @@
   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));
+  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_part_.path,
+      new_part_.path,
       old_extents,
       new_extents,
       false,  // bsdiff_allowed
@@ -337,14 +394,14 @@
   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,
+    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_part_.path,
+        new_part_.path,
         old_extents,
         new_extents,
         true,  // bsdiff_allowed
@@ -379,14 +436,14 @@
   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));
+  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_part_.path,
+      new_part_.path,
       old_extents,
       new_extents,
       true,  // bsdiff_allowed
@@ -410,16 +467,16 @@
   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(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));
+  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_part_.path,
+      new_part_.path,
       old_extents,
       new_extents,
       true,  // bsdiff_allowed
@@ -476,4 +533,237 @@
   EXPECT_EQ("aop2", ops[1].name);
 }
 
+// Test the simple case where all the blocks are different and no new blocks are
+// zeroed.
+TEST_F(DeltaDiffUtilsTest, NoZeroedOrUniqueBlocksDetected) {
+  InitializePartitionWithUniqueBlocks(old_part_, block_size_, 5);
+  InitializePartitionWithUniqueBlocks(new_part_, block_size_, 42);
+
+  EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1,  // chunk_blocks
+                                         false));  // src_ops_allowed
+
+  EXPECT_EQ(0, old_visited_blocks_.blocks());
+  EXPECT_EQ(0, new_visited_blocks_.blocks());
+  EXPECT_EQ(0, blob_size_);
+  EXPECT_TRUE(aops_.empty());
+}
+
+// Test that when the partitions have identical blocks in the same positions no
+// MOVE operation is performed and all the blocks are handled.
+TEST_F(DeltaDiffUtilsTest, IdenticalPartitionsDontMove) {
+  InitializePartitionWithUniqueBlocks(old_part_, block_size_, 42);
+  InitializePartitionWithUniqueBlocks(new_part_, block_size_, 42);
+
+  // Mark some of the blocks as already visited.
+  vector<Extent> already_visited = {ExtentForRange(5, 10),
+                                    ExtentForRange(25, 10)};
+  old_visited_blocks_.AddExtents(already_visited);
+  new_visited_blocks_.AddExtents(already_visited);
+
+  // Most of the blocks rest in the same place, but there's no need for MOVE
+  // operations on those blocks.
+  EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1,  // chunk_blocks
+                                         false));  // src_ops_allowed
+
+  EXPECT_EQ(kDefaultBlockCount, old_visited_blocks_.blocks());
+  EXPECT_EQ(kDefaultBlockCount, new_visited_blocks_.blocks());
+  EXPECT_EQ(0, blob_size_);
+  EXPECT_TRUE(aops_.empty());
+}
+
+// Test that when the partitions have identical blocks in the same positions
+// MOVE operation is performed and all the blocks are handled.
+TEST_F(DeltaDiffUtilsTest, IdenticalBlocksAreCopiedFromSource) {
+  // We use a smaller partition for this test.
+  old_part_.size = kBlockSize * 50;
+  new_part_.size = kBlockSize * 50;
+
+  InitializePartitionWithUniqueBlocks(old_part_, block_size_, 42);
+  InitializePartitionWithUniqueBlocks(new_part_, block_size_, 42);
+
+  // Mark some of the blocks as already visited.
+  vector<Extent> already_visited = {ExtentForRange(5, 5),
+                                    ExtentForRange(25, 7)};
+  old_visited_blocks_.AddExtents(already_visited);
+  new_visited_blocks_.AddExtents(already_visited);
+
+  // Override some of the old blocks with different data.
+  vector<Extent> different_blocks = {ExtentForRange(40, 5)};
+  EXPECT_TRUE(WriteExtents(old_part_.path, different_blocks, kBlockSize,
+                           chromeos::Blob(5 * kBlockSize, 'a')));
+
+  EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(10,  // chunk_blocks
+                                         true));  // src_ops_allowed
+
+  ExtentRanges expected_ranges;
+  expected_ranges.AddExtent(ExtentForRange(0, 50));
+  expected_ranges.SubtractExtents(different_blocks);
+
+  EXPECT_EQ(expected_ranges.extent_set(), old_visited_blocks_.extent_set());
+  EXPECT_EQ(expected_ranges.extent_set(), new_visited_blocks_.extent_set());
+  EXPECT_EQ(0, blob_size_);
+
+  // We expect all the blocks that we didn't override with |different_blocks|
+  // and that we didn't mark as visited in |already_visited| to match and have a
+  // SOURCE_COPY operation chunked at 10 blocks.
+  vector<Extent> expected_op_extents = {
+      ExtentForRange(0, 5),
+      ExtentForRange(10, 10),
+      ExtentForRange(20, 5),
+      ExtentForRange(32, 8),
+      ExtentForRange(45, 5),
+  };
+
+  EXPECT_EQ(expected_op_extents.size(), aops_.size());
+  for (size_t i = 0; i < aops_.size() && i < expected_op_extents.size(); ++i) {
+    SCOPED_TRACE(base::StringPrintf("Failed on operation number %" PRIuS, i));
+    const AnnotatedOperation& aop = aops_[i];
+    EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY,
+              aop.op.type());
+    EXPECT_EQ(1, aop.op.src_extents_size());
+    EXPECT_EQ(expected_op_extents[i], aop.op.src_extents(0));
+    EXPECT_EQ(1, aop.op.dst_extents_size());
+    EXPECT_EQ(expected_op_extents[i], aop.op.dst_extents(0));
+  }
+}
+
+TEST_F(DeltaDiffUtilsTest, IdenticalBlocksAreCopiedInOder) {
+  // We use a smaller partition for this test.
+  old_part_.size = block_size_ * 50;
+  new_part_.size = block_size_ * 50;
+
+  // Create two identical partitions with 5 copies of the same unique "file".
+  chromeos::Blob file_data(block_size_ * 10, 'a');
+  for (size_t offset = 0; offset < file_data.size(); offset += block_size_)
+    file_data[offset] = 'a' + offset / block_size_;
+
+  chromeos::Blob partition_data(old_part_.size);
+  for (size_t offset = 0; offset < partition_data.size();
+       offset += file_data.size()) {
+    std::copy(file_data.begin(), file_data.end(),
+              partition_data.begin() + offset);
+  }
+  EXPECT_TRUE(test_utils::WriteFileVector(old_part_.path, partition_data));
+  EXPECT_TRUE(test_utils::WriteFileVector(new_part_.path, partition_data));
+
+  EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1,  // chunk_blocks
+                                         true));  // src_ops_allowed
+
+  // There should be only one SOURCE_COPY, for the whole partition and the
+  // source extents should cover only the first copy of the source file since
+  // we prefer to re-read files (maybe cached) instead of continue reading the
+  // rest of the partition.
+  EXPECT_EQ(1, aops_.size());
+  const AnnotatedOperation& aop = aops_[0];
+  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY,
+            aop.op.type());
+  EXPECT_EQ(5, aop.op.src_extents_size());
+  for (int i = 0; i < aop.op.src_extents_size(); ++i) {
+    EXPECT_EQ(ExtentForRange(0, 10), aop.op.src_extents(i));
+  }
+
+  EXPECT_EQ(1, aop.op.dst_extents_size());
+  EXPECT_EQ(ExtentForRange(0, 50), aop.op.dst_extents(0));
+
+  EXPECT_EQ(0, blob_size_);
+}
+
+// Test that all blocks with zeros are handled separately using REPLACE_BZ
+// operations unless they are not moved.
+TEST_F(DeltaDiffUtilsTest, ZeroBlocksUseReplaceBz) {
+  InitializePartitionWithUniqueBlocks(old_part_, block_size_, 42);
+  InitializePartitionWithUniqueBlocks(new_part_, block_size_, 5);
+
+  // We set four ranges of blocks with zeros: a single block, a range that fits
+  // in the chunk size, a range that doesn't and finally a range of zeros that
+  // was also zeros in the old image.
+  vector<Extent> new_zeros = {
+      ExtentForRange(10, 1),
+      ExtentForRange(20, 4),
+      // The last range is split since the old image has zeros in part of it.
+      ExtentForRange(30, 20),
+  };
+  chromeos::Blob zeros_data(BlocksInExtents(new_zeros) * block_size_, '\0');
+  EXPECT_TRUE(WriteExtents(new_part_.path, new_zeros, block_size_, zeros_data));
+
+  vector<Extent> old_zeros = vector<Extent>{ExtentForRange(43, 7)};
+  EXPECT_TRUE(WriteExtents(old_part_.path, old_zeros, block_size_, zeros_data));
+
+  EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(5,  // chunk_blocks
+                                         false));  // src_ops_allowed
+
+  // Zeroed blocks from old_visited_blocks_ were copied over, so me actually
+  // use them regardless of the trivial MOVE operation not being emitted.
+  EXPECT_EQ(old_zeros,
+            old_visited_blocks_.GetExtentsForBlockCount(
+                old_visited_blocks_.blocks()));
+
+  // All the new zeroed blocks should be used, part with REPLACE_BZ and part
+  // trivial MOVE operations (not included).
+  EXPECT_EQ(new_zeros,
+            new_visited_blocks_.GetExtentsForBlockCount(
+                new_visited_blocks_.blocks()));
+
+  vector<Extent> expected_op_extents = {
+      ExtentForRange(10, 1),
+      ExtentForRange(20, 4),
+      // This range should be split.
+      ExtentForRange(30, 5),
+      ExtentForRange(35, 5),
+      ExtentForRange(40, 3),
+  };
+
+  EXPECT_EQ(expected_op_extents.size(), aops_.size());
+  for (size_t i = 0; i < aops_.size() && i < expected_op_extents.size(); ++i) {
+    SCOPED_TRACE(base::StringPrintf("Failed on operation number %" PRIuS, i));
+    const AnnotatedOperation& aop = aops_[i];
+    EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ,
+              aop.op.type());
+    EXPECT_EQ(0, aop.op.src_extents_size());
+    EXPECT_EQ(1, aop.op.dst_extents_size());
+    EXPECT_EQ(expected_op_extents[i], aop.op.dst_extents(0));
+  }
+  EXPECT_NE(0, blob_size_);
+}
+
+TEST_F(DeltaDiffUtilsTest, ShuffledBlocksAreTracked) {
+  vector<uint64_t> permutation = {0, 1, 5, 6, 7, 2, 3, 4, 9, 10, 11, 12, 8};
+  vector<Extent> perm_extents;
+  for (uint64_t x : permutation)
+    AppendBlockToExtents(&perm_extents, x);
+
+  // We use a smaller partition for this test.
+  old_part_.size = block_size_ * permutation.size();
+  new_part_.size = block_size_ * permutation.size();
+  InitializePartitionWithUniqueBlocks(new_part_, block_size_, 123);
+
+  // We initialize the old_part_ with the blocks from new_part but in the
+  // |permutation| order. Block i in the old_part_ will contain the same data
+  // as block permutation[i] in the new_part_.
+  chromeos::Blob new_contents;
+  EXPECT_TRUE(utils::ReadFile(new_part_.path, &new_contents));
+  EXPECT_TRUE(WriteExtents(old_part_.path, perm_extents, block_size_,
+                           new_contents));
+
+  EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1,  // chunk_blocks
+                                         true));  // src_ops_allowed
+
+  EXPECT_EQ(permutation.size(), old_visited_blocks_.blocks());
+  EXPECT_EQ(permutation.size(), new_visited_blocks_.blocks());
+
+  // There should be only one SOURCE_COPY, with a complicate list of extents.
+  EXPECT_EQ(1, aops_.size());
+  const AnnotatedOperation& aop = aops_[0];
+  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_SOURCE_COPY,
+            aop.op.type());
+  vector<Extent> aop_src_extents;
+  ExtentsToVector(aop.op.src_extents(), &aop_src_extents);
+  EXPECT_EQ(perm_extents, aop_src_extents);
+
+  EXPECT_EQ(1, aop.op.dst_extents_size());
+  EXPECT_EQ(ExtentForRange(0, permutation.size()), aop.op.dst_extents(0));
+
+  EXPECT_EQ(0, blob_size_);
+}
+
 }  // namespace chromeos_update_engine
diff --git a/payload_generator/extent_ranges.cc b/payload_generator/extent_ranges.cc
index d86bcfc..9151efe 100644
--- a/payload_generator/extent_ranges.cc
+++ b/payload_generator/extent_ranges.cc
@@ -180,6 +180,23 @@
   }
 }
 
+bool ExtentRanges::ContainsBlock(uint64_t block) const {
+  auto lower = extent_set_.lower_bound(ExtentForRange(block, 1));
+  // The block could be on the extent before the one in |lower|.
+  if (lower != extent_set_.begin())
+    lower--;
+  // Any extent starting at block+1 or later is not interesting, so this is the
+  // upper limit.
+  auto upper = extent_set_.lower_bound(ExtentForRange(block + 1, 0));
+  for (auto iter = lower; iter != upper; ++iter) {
+    if (iter->start_block() <= block &&
+        block < iter->start_block() + iter->num_blocks()) {
+      return true;
+    }
+  }
+  return false;
+}
+
 void ExtentRanges::Dump() const {
   LOG(INFO) << "ExtentRanges Dump. blocks: " << blocks_;
   for (ExtentSet::const_iterator it = extent_set_.begin(),
@@ -223,7 +240,7 @@
   return out;
 }
 
-vector<Extent> FilterExtentRanges(const std::vector<Extent>& extents,
+vector<Extent> FilterExtentRanges(const vector<Extent>& extents,
                                   const ExtentRanges& ranges) {
   vector<Extent> result;
   const ExtentRanges::ExtentSet& extent_set = ranges.extent_set();
diff --git a/payload_generator/extent_ranges.h b/payload_generator/extent_ranges.h
index fc15149..f14bb61 100644
--- a/payload_generator/extent_ranges.h
+++ b/payload_generator/extent_ranges.h
@@ -48,6 +48,9 @@
   void AddRanges(const ExtentRanges& ranges);
   void SubtractRanges(const ExtentRanges& ranges);
 
+  // Returns whether the block |block| is in this ExtentRange.
+  bool ContainsBlock(uint64_t block) const;
+
   static bool ExtentsOverlapOrTouch(const Extent& a, const Extent& b);
   static bool ExtentsOverlap(const Extent& a, const Extent& b);
 
diff --git a/payload_generator/extent_ranges_unittest.cc b/payload_generator/extent_ranges_unittest.cc
index b7036a5..2cda195 100644
--- a/payload_generator/extent_ranges_unittest.cc
+++ b/payload_generator/extent_ranges_unittest.cc
@@ -256,6 +256,25 @@
   }
 }
 
+TEST(ExtentRangesTest, ContainsBlockTest) {
+  ExtentRanges ranges;
+  EXPECT_FALSE(ranges.ContainsBlock(123));
+
+  ranges.AddExtent(ExtentForRange(10, 10));
+  ranges.AddExtent(ExtentForRange(100, 1));
+
+  EXPECT_FALSE(ranges.ContainsBlock(9));
+  EXPECT_TRUE(ranges.ContainsBlock(10));
+  EXPECT_TRUE(ranges.ContainsBlock(15));
+  EXPECT_TRUE(ranges.ContainsBlock(19));
+  EXPECT_FALSE(ranges.ContainsBlock(20));
+
+  // Test for an extent with just the block we are requesting.
+  EXPECT_FALSE(ranges.ContainsBlock(99));
+  EXPECT_TRUE(ranges.ContainsBlock(100));
+  EXPECT_FALSE(ranges.ContainsBlock(101));
+}
+
 TEST(ExtentRangesTest, FilterExtentRangesEmptyRanges) {
   ExtentRanges ranges;
   EXPECT_EQ(vector<Extent>(),
diff --git a/update_engine.gyp b/update_engine.gyp
index aaccad3..89e0b7b 100644
--- a/update_engine.gyp
+++ b/update_engine.gyp
@@ -267,6 +267,7 @@
       'sources': [
         'payload_generator/ab_generator.cc',
         'payload_generator/annotated_operation.cc',
+        'payload_generator/block_mapping.cc',
         'payload_generator/cycle_breaker.cc',
         'payload_generator/delta_diff_generator.cc',
         'payload_generator/delta_diff_utils.cc',
@@ -384,6 +385,7 @@
             'omaha_response_handler_action_unittest.cc',
             'p2p_manager_unittest.cc',
             'payload_generator/ab_generator_unittest.cc',
+            'payload_generator/block_mapping_unittest.cc',
             'payload_generator/cycle_breaker_unittest.cc',
             'payload_generator/delta_diff_utils_unittest.cc',
             'payload_generator/ext2_filesystem_unittest.cc',