diff --git a/payload_generator/delta_diff_generator.cc b/payload_generator/delta_diff_generator.cc
index 34b9737..8676086 100644
--- a/payload_generator/delta_diff_generator.cc
+++ b/payload_generator/delta_diff_generator.cc
@@ -27,11 +27,11 @@
 
 #include "update_engine/bzip.h"
 #include "update_engine/delta_performer.h"
-#include "update_engine/extent_ranges.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/full_update_generator.h"
 #include "update_engine/payload_generator/inplace_generator.h"
 #include "update_engine/payload_generator/payload_signer.h"
@@ -161,7 +161,7 @@
                                 manifest_metadata_size));
   total_size += manifest_metadata_size;
 
-  std::sort(objects.begin(), objects.end());
+  sort(objects.begin(), objects.end());
 
   static const char kFormatString[] = "%6.2f%% %10jd %-10s %s\n";
   for (const DeltaObject& object : objects) {
diff --git a/payload_generator/delta_diff_generator_unittest.cc b/payload_generator/delta_diff_generator_unittest.cc
index c198916..baf308f 100644
--- a/payload_generator/delta_diff_generator_unittest.cc
+++ b/payload_generator/delta_diff_generator_unittest.cc
@@ -27,8 +27,8 @@
 
 #include "update_engine/bzip.h"
 #include "update_engine/delta_performer.h"
-#include "update_engine/extent_ranges.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"
@@ -36,7 +36,6 @@
 #include "update_engine/test_utils.h"
 #include "update_engine/utils.h"
 
-using chromeos_update_engine::test_utils::kRandomString;
 using std::set;
 using std::string;
 using std::unique_ptr;
diff --git a/payload_generator/ext2_filesystem.cc b/payload_generator/ext2_filesystem.cc
index d3e0930..0467b80 100644
--- a/payload_generator/ext2_filesystem.cc
+++ b/payload_generator/ext2_filesystem.cc
@@ -14,7 +14,7 @@
 #include <base/logging.h>
 #include <base/strings/stringprintf.h>
 
-#include "update_engine/extent_ranges.h"
+#include "update_engine/payload_generator/extent_ranges.h"
 #include "update_engine/payload_generator/extent_utils.h"
 #include "update_engine/update_metadata.pb.h"
 #include "update_engine/utils.h"
diff --git a/payload_generator/extent_ranges.cc b/payload_generator/extent_ranges.cc
new file mode 100644
index 0000000..d86bcfc
--- /dev/null
+++ b/payload_generator/extent_ranges.cc
@@ -0,0 +1,277 @@
+// Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "update_engine/payload_generator/extent_ranges.h"
+
+#include <algorithm>
+#include <set>
+#include <utility>
+#include <vector>
+
+#include <base/logging.h>
+
+#include "update_engine/payload_constants.h"
+
+using std::set;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+bool ExtentRanges::ExtentsOverlapOrTouch(const Extent& a, const Extent& b) {
+  if (a.start_block() == b.start_block())
+    return true;
+  if (a.start_block() == kSparseHole || b.start_block() == kSparseHole)
+    return false;
+  if (a.start_block() < b.start_block()) {
+    return a.start_block() + a.num_blocks() >= b.start_block();
+  } else {
+    return b.start_block() + b.num_blocks() >= a.start_block();
+  }
+}
+
+bool ExtentRanges::ExtentsOverlap(const Extent& a, const Extent& b) {
+  if (a.start_block() == b.start_block())
+    return true;
+  if (a.start_block() == kSparseHole || b.start_block() == kSparseHole)
+    return false;
+  if (a.start_block() < b.start_block()) {
+    return a.start_block() + a.num_blocks() > b.start_block();
+  } else {
+    return b.start_block() + b.num_blocks() > a.start_block();
+  }
+}
+
+void ExtentRanges::AddBlock(uint64_t block) {
+  AddExtent(ExtentForRange(block, 1));
+}
+
+void ExtentRanges::SubtractBlock(uint64_t block) {
+  SubtractExtent(ExtentForRange(block, 1));
+}
+
+namespace {
+
+Extent UnionOverlappingExtents(const Extent& first, const Extent& second) {
+  CHECK_NE(kSparseHole, first.start_block());
+  CHECK_NE(kSparseHole, second.start_block());
+  uint64_t start = std::min(first.start_block(), second.start_block());
+  uint64_t end = std::max(first.start_block() + first.num_blocks(),
+                          second.start_block() + second.num_blocks());
+  return ExtentForRange(start, end - start);
+}
+
+}  // namespace
+
+void ExtentRanges::AddExtent(Extent extent) {
+  if (extent.start_block() == kSparseHole || extent.num_blocks() == 0)
+    return;
+
+  ExtentSet::iterator begin_del = extent_set_.end();
+  ExtentSet::iterator end_del = extent_set_.end();
+  uint64_t del_blocks = 0;
+  for (ExtentSet::iterator it = extent_set_.begin(), e = extent_set_.end();
+       it != e; ++it) {
+    if (ExtentsOverlapOrTouch(*it, extent)) {
+      end_del = it;
+      ++end_del;
+      del_blocks += it->num_blocks();
+      if (begin_del == extent_set_.end())
+        begin_del = it;
+
+      extent = UnionOverlappingExtents(extent, *it);
+    }
+  }
+  extent_set_.erase(begin_del, end_del);
+  extent_set_.insert(extent);
+  blocks_ -= del_blocks;
+  blocks_ += extent.num_blocks();
+}
+
+namespace {
+// Returns base - subtractee (set subtraction).
+ExtentRanges::ExtentSet SubtractOverlappingExtents(const Extent& base,
+                                                   const Extent& subtractee) {
+  ExtentRanges::ExtentSet ret;
+  if (subtractee.start_block() > base.start_block()) {
+    ret.insert(ExtentForRange(base.start_block(),
+                              subtractee.start_block() - base.start_block()));
+  }
+  uint64_t base_end = base.start_block() + base.num_blocks();
+  uint64_t subtractee_end = subtractee.start_block() + subtractee.num_blocks();
+  if (base_end > subtractee_end) {
+    ret.insert(ExtentForRange(subtractee_end, base_end - subtractee_end));
+  }
+  return ret;
+}
+}  // namespace
+
+void ExtentRanges::SubtractExtent(const Extent& extent) {
+  if (extent.start_block() == kSparseHole || extent.num_blocks() == 0)
+    return;
+
+  ExtentSet::iterator begin_del = extent_set_.end();
+  ExtentSet::iterator end_del = extent_set_.end();
+  uint64_t del_blocks = 0;
+  ExtentSet new_extents;
+  for (ExtentSet::iterator it = extent_set_.begin(), e = extent_set_.end();
+       it != e; ++it) {
+    if (!ExtentsOverlap(*it, extent))
+      continue;
+
+    if (begin_del == extent_set_.end())
+      begin_del = it;
+    end_del = it;
+    ++end_del;
+
+    del_blocks += it->num_blocks();
+
+    ExtentSet subtraction = SubtractOverlappingExtents(*it, extent);
+    for (ExtentSet::iterator jt = subtraction.begin(), je = subtraction.end();
+         jt != je; ++jt) {
+      new_extents.insert(*jt);
+      del_blocks -= jt->num_blocks();
+    }
+  }
+  extent_set_.erase(begin_del, end_del);
+  extent_set_.insert(new_extents.begin(), new_extents.end());
+  blocks_ -= del_blocks;
+}
+
+void ExtentRanges::AddRanges(const ExtentRanges& ranges) {
+  for (ExtentSet::const_iterator it = ranges.extent_set_.begin(),
+           e = ranges.extent_set_.end(); it != e; ++it) {
+    AddExtent(*it);
+  }
+}
+
+void ExtentRanges::SubtractRanges(const ExtentRanges& ranges) {
+  for (ExtentSet::const_iterator it = ranges.extent_set_.begin(),
+           e = ranges.extent_set_.end(); it != e; ++it) {
+    SubtractExtent(*it);
+  }
+}
+
+void ExtentRanges::AddExtents(const vector<Extent>& extents) {
+  for (vector<Extent>::const_iterator it = extents.begin(), e = extents.end();
+       it != e; ++it) {
+    AddExtent(*it);
+  }
+}
+
+void ExtentRanges::SubtractExtents(const vector<Extent>& extents) {
+  for (vector<Extent>::const_iterator it = extents.begin(), e = extents.end();
+       it != e; ++it) {
+    SubtractExtent(*it);
+  }
+}
+
+void ExtentRanges::AddRepeatedExtents(
+    const ::google::protobuf::RepeatedPtrField<Extent> &exts) {
+  for (int i = 0, e = exts.size(); i != e; ++i) {
+    AddExtent(exts.Get(i));
+  }
+}
+
+void ExtentRanges::SubtractRepeatedExtents(
+    const ::google::protobuf::RepeatedPtrField<Extent> &exts) {
+  for (int i = 0, e = exts.size(); i != e; ++i) {
+    SubtractExtent(exts.Get(i));
+  }
+}
+
+void ExtentRanges::Dump() const {
+  LOG(INFO) << "ExtentRanges Dump. blocks: " << blocks_;
+  for (ExtentSet::const_iterator it = extent_set_.begin(),
+           e = extent_set_.end();
+       it != e; ++it) {
+    LOG(INFO) << "{" << it->start_block() << ", " << it->num_blocks() << "}";
+  }
+}
+
+Extent ExtentForRange(uint64_t start_block, uint64_t num_blocks) {
+  Extent ret;
+  ret.set_start_block(start_block);
+  ret.set_num_blocks(num_blocks);
+  return ret;
+}
+
+vector<Extent> ExtentRanges::GetExtentsForBlockCount(
+    uint64_t count) const {
+  vector<Extent> out;
+  if (count == 0)
+    return out;
+  uint64_t out_blocks = 0;
+  CHECK(count <= blocks_);
+  for (ExtentSet::const_iterator it = extent_set_.begin(),
+           e = extent_set_.end();
+       it != e; ++it) {
+    const uint64_t blocks_needed = count - out_blocks;
+    const Extent& extent = *it;
+    out.push_back(extent);
+    out_blocks += extent.num_blocks();
+    if (extent.num_blocks() < blocks_needed)
+      continue;
+    if (extent.num_blocks() == blocks_needed)
+      break;
+    // If we get here, we just added the last extent needed, but it's too big
+    out_blocks -= extent.num_blocks();
+    out_blocks += blocks_needed;
+    out.back().set_num_blocks(blocks_needed);
+    break;
+  }
+  return out;
+}
+
+vector<Extent> FilterExtentRanges(const std::vector<Extent>& extents,
+                                  const ExtentRanges& ranges) {
+  vector<Extent> result;
+  const ExtentRanges::ExtentSet& extent_set = ranges.extent_set();
+  for (Extent extent : extents) {
+    // The extents are sorted by the start_block. We want to iterate all the
+    // Extents in the ExtentSet possibly overlapping the current |extent|. This
+    // is achieved by looking from the extent whose start_block is *lower* than
+    // the extent.start_block() up to the greatest extent whose start_block is
+    // lower than extent.start_block() + extent.num_blocks().
+    auto lower = extent_set.lower_bound(extent);
+    // We need to decrement the lower_bound to look at the extent that could
+    // overlap the beginning of the current |extent|.
+    if (lower != extent_set.begin())
+      lower--;
+    auto upper = extent_set.lower_bound(
+        ExtentForRange(extent.start_block() + extent.num_blocks(), 0));
+    for (auto iter = lower; iter != upper; ++iter) {
+      if (!ExtentRanges::ExtentsOverlap(extent, *iter))
+        continue;
+      if (iter->start_block() <= extent.start_block()) {
+        // We need to cut blocks from the beginning of the |extent|.
+        uint64_t cut_blocks = iter->start_block() + iter->num_blocks() -
+            extent.start_block();
+        if (cut_blocks >= extent.num_blocks()) {
+          extent.set_num_blocks(0);
+          break;
+        }
+        extent = ExtentForRange(extent.start_block() + cut_blocks,
+                                extent.num_blocks() - cut_blocks);
+      } else {
+        // We need to cut blocks on the middle of the extent, possible up to the
+        // end of it.
+        result.push_back(
+            ExtentForRange(extent.start_block(),
+                           iter->start_block() - extent.start_block()));
+        uint64_t new_start = iter->start_block() + iter->num_blocks();
+        uint64_t old_end = extent.start_block() + extent.num_blocks();
+        if (new_start >= old_end) {
+          extent.set_num_blocks(0);
+          break;
+        }
+        extent = ExtentForRange(new_start, old_end - new_start);
+      }
+    }
+    if (extent.num_blocks() > 0)
+      result.push_back(extent);
+  }
+  return result;
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/extent_ranges.h b/payload_generator/extent_ranges.h
new file mode 100644
index 0000000..fc15149
--- /dev/null
+++ b/payload_generator/extent_ranges.h
@@ -0,0 +1,79 @@
+// Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_RANGES_H_
+#define UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_RANGES_H_
+
+#include <map>
+#include <set>
+#include <vector>
+
+#include <base/macros.h>
+
+#include "update_engine/update_metadata.pb.h"
+
+// An ExtentRanges object represents an unordered collection of extents (and
+// therefore blocks). Such an object may be modified by adding or subtracting
+// blocks (think: set addition or set subtraction). Note that ExtentRanges
+// ignores sparse hole extents mostly to avoid confusion between extending a
+// sparse hole range vs. set addition but also to ensure that the delta
+// generator doesn't use sparse holes as scratch space.
+
+namespace chromeos_update_engine {
+
+struct ExtentLess {
+  bool operator()(const Extent& x, const Extent& y) const {
+    return x.start_block() < y.start_block();
+  }
+};
+
+Extent ExtentForRange(uint64_t start_block, uint64_t num_blocks);
+
+class ExtentRanges {
+ public:
+  typedef std::set<Extent, ExtentLess> ExtentSet;
+
+  ExtentRanges() : blocks_(0) {}
+  void AddBlock(uint64_t block);
+  void SubtractBlock(uint64_t block);
+  void AddExtent(Extent extent);
+  void SubtractExtent(const Extent& extent);
+  void AddExtents(const std::vector<Extent>& extents);
+  void SubtractExtents(const std::vector<Extent>& extents);
+  void AddRepeatedExtents(
+      const ::google::protobuf::RepeatedPtrField<Extent> &exts);
+  void SubtractRepeatedExtents(
+      const ::google::protobuf::RepeatedPtrField<Extent> &exts);
+  void AddRanges(const ExtentRanges& ranges);
+  void SubtractRanges(const ExtentRanges& ranges);
+
+  static bool ExtentsOverlapOrTouch(const Extent& a, const Extent& b);
+  static bool ExtentsOverlap(const Extent& a, const Extent& b);
+
+  // Dumps contents to the log file. Useful for debugging.
+  void Dump() const;
+
+  uint64_t blocks() const { return blocks_; }
+  const ExtentSet& extent_set() const { return extent_set_; }
+
+  // Returns an ordered vector of extents for |count| blocks,
+  // using extents in extent_set_. The returned extents are not
+  // removed from extent_set_. |count| must be less than or equal to
+  // the number of blocks in this extent set.
+  std::vector<Extent> GetExtentsForBlockCount(uint64_t count) const;
+
+ private:
+  ExtentSet extent_set_;
+  uint64_t blocks_;
+};
+
+// Filters out from the passed list of extents |extents| all the blocks in the
+// ExtentRanges set. Note that the order of the blocks in |extents| is preserved
+// omitting blocks present in the ExtentRanges |ranges|.
+std::vector<Extent> FilterExtentRanges(const std::vector<Extent>& extents,
+                                       const ExtentRanges& ranges);
+
+}  // namespace chromeos_update_engine
+
+#endif  // UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_RANGES_H_
diff --git a/payload_generator/extent_ranges_unittest.cc b/payload_generator/extent_ranges_unittest.cc
new file mode 100644
index 0000000..b7036a5
--- /dev/null
+++ b/payload_generator/extent_ranges_unittest.cc
@@ -0,0 +1,314 @@
+// Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "update_engine/payload_generator/extent_ranges.h"
+
+#include <vector>
+
+#include <gtest/gtest.h>
+
+#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/extent_utils.h"
+#include "update_engine/test_utils.h"
+
+using std::vector;
+
+namespace chromeos_update_engine {
+
+class ExtentRangesTest : public ::testing::Test {};
+
+namespace {
+void ExpectRangeEq(const ExtentRanges& ranges,
+                   const uint64_t* expected,
+                   size_t sz,
+                   int line) {
+  uint64_t blocks = 0;
+  for (size_t i = 1; i < sz; i += 2) {
+    blocks += expected[i];
+  }
+  EXPECT_EQ(blocks, ranges.blocks()) << "line: " << line;
+
+  const ExtentRanges::ExtentSet& result = ranges.extent_set();
+  ExtentRanges::ExtentSet::const_iterator it = result.begin();
+  for (size_t i = 0; i < sz; i += 2) {
+    EXPECT_FALSE(it == result.end()) << "line: " << line;
+    EXPECT_EQ(expected[i], it->start_block()) << "line: " << line;
+    EXPECT_EQ(expected[i + 1], it->num_blocks()) << "line: " << line;
+    ++it;
+  }
+}
+
+#define EXPECT_RANGE_EQ(ranges, var)                            \
+  do {                                                          \
+    ExpectRangeEq(ranges, var, arraysize(var), __LINE__);       \
+  } while (0)
+
+void ExpectRangesOverlapOrTouch(uint64_t a_start, uint64_t a_num,
+                                uint64_t b_start, uint64_t b_num) {
+  EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(a_start,
+                                                                 a_num),
+                                                  ExtentForRange(b_start,
+                                                                 b_num)));
+  EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(b_start,
+                                                                 b_num),
+                                                  ExtentForRange(a_start,
+                                                                 a_num)));
+}
+
+void ExpectFalseRangesOverlapOrTouch(uint64_t a_start, uint64_t a_num,
+                                     uint64_t b_start, uint64_t b_num) {
+  EXPECT_FALSE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(a_start,
+                                                                  a_num),
+                                                   ExtentForRange(b_start,
+                                                                  b_num)));
+  EXPECT_FALSE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(b_start,
+                                                                  b_num),
+                                                   ExtentForRange(a_start,
+                                                                  a_num)));
+  EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start,
+                                                           a_num),
+                                            ExtentForRange(b_start,
+                                                           b_num)));
+  EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start,
+                                                           b_num),
+                                            ExtentForRange(a_start,
+                                                           a_num)));
+}
+
+void ExpectRangesOverlap(uint64_t a_start, uint64_t a_num,
+                         uint64_t b_start, uint64_t b_num) {
+  EXPECT_TRUE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start,
+                                                          a_num),
+                                           ExtentForRange(b_start,
+                                                          b_num)));
+  EXPECT_TRUE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start,
+                                                          b_num),
+                                           ExtentForRange(a_start,
+                                                          a_num)));
+  EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(a_start,
+                                                                 a_num),
+                                                  ExtentForRange(b_start,
+                                                                 b_num)));
+  EXPECT_TRUE(ExtentRanges::ExtentsOverlapOrTouch(ExtentForRange(b_start,
+                                                                 b_num),
+                                                  ExtentForRange(a_start,
+                                                                 a_num)));
+}
+
+void ExpectFalseRangesOverlap(uint64_t a_start, uint64_t a_num,
+                              uint64_t b_start, uint64_t b_num) {
+  EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(a_start,
+                                                           a_num),
+                                            ExtentForRange(b_start,
+                                                           b_num)));
+  EXPECT_FALSE(ExtentRanges::ExtentsOverlap(ExtentForRange(b_start,
+                                                           b_num),
+                                            ExtentForRange(a_start,
+                                                           a_num)));
+}
+
+}  // namespace
+
+TEST(ExtentRangesTest, ExtentsOverlapTest) {
+  ExpectRangesOverlapOrTouch(10, 20, 30, 10);
+  ExpectRangesOverlap(10, 20, 25, 10);
+  ExpectFalseRangesOverlapOrTouch(10, 20, 35, 10);
+  ExpectFalseRangesOverlap(10, 20, 30, 10);
+  ExpectRangesOverlap(12, 4, 12, 3);
+
+  ExpectRangesOverlapOrTouch(kSparseHole, 2, kSparseHole, 3);
+  ExpectRangesOverlap(kSparseHole, 2, kSparseHole, 3);
+  ExpectFalseRangesOverlapOrTouch(kSparseHole, 2, 10, 3);
+  ExpectFalseRangesOverlapOrTouch(10, 2, kSparseHole, 3);
+  ExpectFalseRangesOverlap(kSparseHole, 2, 10, 3);
+  ExpectFalseRangesOverlap(10, 2, kSparseHole, 3);
+}
+
+TEST(ExtentRangesTest, SimpleTest) {
+  ExtentRanges ranges;
+  {
+    static const uint64_t expected[] = {};
+    // Can't use arraysize() on 0-length arrays:
+    ExpectRangeEq(ranges, expected, 0, __LINE__);
+  }
+  ranges.SubtractBlock(2);
+  {
+    static const uint64_t expected[] = {};
+    // Can't use arraysize() on 0-length arrays:
+    ExpectRangeEq(ranges, expected, 0, __LINE__);
+  }
+
+  ranges.AddBlock(0);
+  ranges.Dump();
+  ranges.AddBlock(1);
+  ranges.AddBlock(3);
+
+  {
+    static const uint64_t expected[] = {0, 2, 3, 1};
+    EXPECT_RANGE_EQ(ranges, expected);
+  }
+  ranges.AddBlock(2);
+  {
+    static const uint64_t expected[] = {0, 4};
+    EXPECT_RANGE_EQ(ranges, expected);
+    ranges.AddBlock(kSparseHole);
+    EXPECT_RANGE_EQ(ranges, expected);
+    ranges.SubtractBlock(kSparseHole);
+    EXPECT_RANGE_EQ(ranges, expected);
+  }
+  ranges.SubtractBlock(2);
+  {
+    static const uint64_t expected[] = {0, 2, 3, 1};
+    EXPECT_RANGE_EQ(ranges, expected);
+  }
+
+  for (uint64_t i = 100; i < 1000; i += 100) {
+    ranges.AddExtent(ExtentForRange(i, 50));
+  }
+  {
+    static const uint64_t expected[] = {
+      0, 2, 3, 1, 100, 50, 200, 50, 300, 50, 400, 50,
+      500, 50, 600, 50, 700, 50, 800, 50, 900, 50
+    };
+    EXPECT_RANGE_EQ(ranges, expected);
+  }
+
+  ranges.SubtractExtent(ExtentForRange(210, 410 - 210));
+  {
+    static const uint64_t expected[] = {
+      0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
+      600, 50, 700, 50, 800, 50, 900, 50
+    };
+    EXPECT_RANGE_EQ(ranges, expected);
+  }
+  ranges.AddExtent(ExtentForRange(100000, 0));
+  {
+    static const uint64_t expected[] = {
+      0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
+      600, 50, 700, 50, 800, 50, 900, 50
+    };
+    EXPECT_RANGE_EQ(ranges, expected);
+  }
+  ranges.SubtractExtent(ExtentForRange(3, 0));
+  {
+    static const uint64_t expected[] = {
+      0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
+      600, 50, 700, 50, 800, 50, 900, 50
+    };
+    EXPECT_RANGE_EQ(ranges, expected);
+  }
+}
+
+TEST(ExtentRangesTest, MultipleRanges) {
+  ExtentRanges ranges_a, ranges_b;
+  ranges_a.AddBlock(0);
+  ranges_b.AddBlock(4);
+  ranges_b.AddBlock(3);
+  {
+    uint64_t expected[] = {3, 2};
+    EXPECT_RANGE_EQ(ranges_b, expected);
+  }
+  ranges_a.AddRanges(ranges_b);
+  {
+    uint64_t expected[] = {0, 1, 3, 2};
+    EXPECT_RANGE_EQ(ranges_a, expected);
+  }
+  ranges_a.SubtractRanges(ranges_b);
+  {
+    uint64_t expected[] = {0, 1};
+    EXPECT_RANGE_EQ(ranges_a, expected);
+  }
+  {
+    uint64_t expected[] = {3, 2};
+    EXPECT_RANGE_EQ(ranges_b, expected);
+  }
+}
+
+TEST(ExtentRangesTest, GetExtentsForBlockCountTest) {
+  ExtentRanges ranges;
+  ranges.AddExtents(vector<Extent>(1, ExtentForRange(10, 30)));
+  {
+    vector<Extent> zero_extents = ranges.GetExtentsForBlockCount(0);
+    EXPECT_TRUE(zero_extents.empty());
+  }
+  ::google::protobuf::RepeatedPtrField<Extent> rep_field;
+  *rep_field.Add() = ExtentForRange(30, 40);
+  ranges.AddRepeatedExtents(rep_field);
+  ranges.SubtractExtents(vector<Extent>(1, ExtentForRange(20, 10)));
+  *rep_field.Mutable(0) = ExtentForRange(50, 10);
+  ranges.SubtractRepeatedExtents(rep_field);
+  EXPECT_EQ(40, ranges.blocks());
+
+  for (int i = 0; i < 2; i++) {
+    vector<Extent> expected(2);
+    expected[0] = ExtentForRange(10, 10);
+    expected[1] = ExtentForRange(30, i == 0 ? 10 : 20);
+    vector<Extent> actual =
+        ranges.GetExtentsForBlockCount(10 + expected[1].num_blocks());
+    EXPECT_EQ(expected.size(), actual.size());
+    for (vector<Extent>::size_type j = 0, e = expected.size(); j != e; ++j) {
+      EXPECT_EQ(expected[j].start_block(), actual[j].start_block())
+          << "j = " << j;
+      EXPECT_EQ(expected[j].num_blocks(), actual[j].num_blocks())
+          << "j = " << j;
+    }
+  }
+}
+
+TEST(ExtentRangesTest, FilterExtentRangesEmptyRanges) {
+  ExtentRanges ranges;
+  EXPECT_EQ(vector<Extent>(),
+            FilterExtentRanges(vector<Extent>(), ranges));
+  EXPECT_EQ(
+      vector<Extent>{ ExtentForRange(50, 10) },
+      FilterExtentRanges(vector<Extent>{ ExtentForRange(50, 10) }, ranges));
+  // Check that the empty Extents are ignored.
+  EXPECT_EQ(
+      (vector<Extent>{ ExtentForRange(10, 10), ExtentForRange(20, 10) }),
+      FilterExtentRanges(vector<Extent>{
+           ExtentForRange(10, 10),
+           ExtentForRange(3, 0),
+           ExtentForRange(20, 10) }, ranges));
+}
+
+TEST(ExtentRangesTest, FilterExtentRangesMultipleRanges) {
+  // Two overlaping extents, with three ranges to remove.
+  vector<Extent> extents {
+      ExtentForRange(10, 100),
+      ExtentForRange(30, 100) };
+  ExtentRanges ranges;
+  // This overlaps the beginning of the second extent.
+  ranges.AddExtent(ExtentForRange(28, 3));
+  ranges.AddExtent(ExtentForRange(50, 10));
+  ranges.AddExtent(ExtentForRange(70, 10));
+  // This overlaps the end of the second extent.
+  ranges.AddExtent(ExtentForRange(108, 6));
+  EXPECT_EQ(
+      (vector<Extent>{
+           // For the first extent:
+           ExtentForRange(10, 18),
+           ExtentForRange(31, 19),
+           ExtentForRange(60, 10),
+           ExtentForRange(80, 28),
+           // For the second extent:
+           ExtentForRange(31, 19),
+           ExtentForRange(60, 10),
+           ExtentForRange(80, 28),
+           ExtentForRange(114, 16)}),
+      FilterExtentRanges(extents, ranges));
+}
+
+TEST(ExtentRangesTest, FilterExtentRangesOvelapping) {
+  ExtentRanges ranges;
+  ranges.AddExtent(ExtentForRange(10, 3));
+  ranges.AddExtent(ExtentForRange(20, 5));
+  // Requested extent overlaps with one of the ranges.
+  EXPECT_EQ(vector<Extent>(),
+            FilterExtentRanges(vector<Extent>{
+                                   ExtentForRange(10, 1),
+                                   ExtentForRange(22, 1) },
+                               ranges));
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/extent_utils.cc b/payload_generator/extent_utils.cc
index 6896678..71aae1d 100644
--- a/payload_generator/extent_utils.cc
+++ b/payload_generator/extent_utils.cc
@@ -11,9 +11,9 @@
 #include <base/logging.h>
 #include <base/macros.h>
 
-#include "update_engine/extent_ranges.h"
 #include "update_engine/payload_constants.h"
 #include "update_engine/payload_generator/annotated_operation.h"
+#include "update_engine/payload_generator/extent_ranges.h"
 
 using std::string;
 using std::vector;
diff --git a/payload_generator/extent_utils_unittest.cc b/payload_generator/extent_utils_unittest.cc
index 6e685e0..b9f9ef2 100644
--- a/payload_generator/extent_utils_unittest.cc
+++ b/payload_generator/extent_utils_unittest.cc
@@ -9,8 +9,8 @@
 
 #include <gtest/gtest.h>
 
-#include "update_engine/extent_ranges.h"
 #include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/extent_ranges.h"
 #include "update_engine/test_utils.h"
 
 using std::vector;
diff --git a/payload_generator/graph_utils_unittest.cc b/payload_generator/graph_utils_unittest.cc
index 3253f71..bd6c979 100644
--- a/payload_generator/graph_utils_unittest.cc
+++ b/payload_generator/graph_utils_unittest.cc
@@ -9,8 +9,8 @@
 
 #include <gtest/gtest.h>
 
-#include "update_engine/extent_ranges.h"
 #include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/extent_ranges.h"
 #include "update_engine/payload_generator/extent_utils.h"
 
 using std::make_pair;
diff --git a/payload_generator/inplace_generator.cc b/payload_generator/inplace_generator.cc
index fd19d14..64c8226 100644
--- a/payload_generator/inplace_generator.cc
+++ b/payload_generator/inplace_generator.cc
@@ -11,11 +11,11 @@
 #include <utility>
 #include <vector>
 
-#include "update_engine/extent_ranges.h"
 #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/ext2_filesystem.h"
+#include "update_engine/payload_generator/extent_ranges.h"
 #include "update_engine/payload_generator/graph_types.h"
 #include "update_engine/payload_generator/graph_utils.h"
 #include "update_engine/payload_generator/topological_sort.h"
diff --git a/payload_generator/inplace_generator_unittest.cc b/payload_generator/inplace_generator_unittest.cc
index 5c563c5..b988787 100644
--- a/payload_generator/inplace_generator_unittest.cc
+++ b/payload_generator/inplace_generator_unittest.cc
@@ -14,9 +14,9 @@
 #include <base/strings/string_util.h>
 #include <gtest/gtest.h>
 
-#include "update_engine/extent_ranges.h"
 #include "update_engine/payload_generator/cycle_breaker.h"
 #include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/extent_ranges.h"
 #include "update_engine/payload_generator/graph_types.h"
 #include "update_engine/payload_generator/graph_utils.h"
 #include "update_engine/test_utils.h"
diff --git a/payload_generator/raw_filesystem.cc b/payload_generator/raw_filesystem.cc
index ee4423e..f24096e 100644
--- a/payload_generator/raw_filesystem.cc
+++ b/payload_generator/raw_filesystem.cc
@@ -4,7 +4,7 @@
 
 #include "update_engine/payload_generator/raw_filesystem.h"
 
-#include "update_engine/extent_ranges.h"
+#include "update_engine/payload_generator/extent_ranges.h"
 #include "update_engine/update_metadata.pb.h"
 #include "update_engine/utils.h"