diff --git a/payload_generator/cycle_breaker.cc b/payload_generator/cycle_breaker.cc
new file mode 100644
index 0000000..10ef6fb
--- /dev/null
+++ b/payload_generator/cycle_breaker.cc
@@ -0,0 +1,199 @@
+// 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/cycle_breaker.h"
+
+#include <inttypes.h>
+
+#include <set>
+#include <utility>
+
+#include <base/strings/string_util.h>
+#include <base/strings/stringprintf.h>
+
+#include "update_engine/payload_generator/graph_utils.h"
+#include "update_engine/payload_generator/tarjan.h"
+#include "update_engine/utils.h"
+
+using std::make_pair;
+using std::set;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+// This is the outer function from the original paper.
+void CycleBreaker::BreakCycles(const Graph& graph, set<Edge>* out_cut_edges) {
+  cut_edges_.clear();
+
+  // Make a copy, which we will modify by removing edges. Thus, in each
+  // iteration subgraph_ is the current subgraph or the original with
+  // vertices we desire. This variable was "A_K" in the original paper.
+  subgraph_ = graph;
+
+  // The paper calls for the "adjacency structure (i.e., graph) of
+  // strong (-ly connected) component K with least vertex in subgraph
+  // induced by {s, s + 1, ..., n}".
+  // We arbitrarily order each vertex by its index in the graph. Thus,
+  // each iteration, we are looking at the subgraph {s, s + 1, ..., n}
+  // and looking for the strongly connected component with vertex s.
+
+  TarjanAlgorithm tarjan;
+  skipped_ops_ = 0;
+
+  for (Graph::size_type i = 0; i < subgraph_.size(); i++) {
+    DeltaArchiveManifest_InstallOperation_Type op_type = graph[i].op.type();
+    if (op_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
+        op_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) {
+      skipped_ops_++;
+      continue;
+    }
+
+    if (i > 0) {
+      // Erase node (i - 1) from subgraph_. First, erase what it points to
+      subgraph_[i - 1].out_edges.clear();
+      // Now, erase any pointers to node (i - 1)
+      for (Graph::size_type j = i; j < subgraph_.size(); j++) {
+        subgraph_[j].out_edges.erase(i - 1);
+      }
+    }
+
+    // Calculate SCC (strongly connected component) with vertex i.
+    vector<Vertex::Index> component_indexes;
+    tarjan.Execute(i, &subgraph_, &component_indexes);
+
+    // Set subgraph edges for the components in the SCC.
+    for (vector<Vertex::Index>::iterator it = component_indexes.begin();
+         it != component_indexes.end(); ++it) {
+      subgraph_[*it].subgraph_edges.clear();
+      for (vector<Vertex::Index>::iterator jt = component_indexes.begin();
+           jt != component_indexes.end(); ++jt) {
+        // If there's a link from *it -> *jt in the graph,
+        // add a subgraph_ edge
+        if (utils::MapContainsKey(subgraph_[*it].out_edges, *jt))
+          subgraph_[*it].subgraph_edges.insert(*jt);
+      }
+    }
+
+    current_vertex_ = i;
+    blocked_.clear();
+    blocked_.resize(subgraph_.size());
+    blocked_graph_.clear();
+    blocked_graph_.resize(subgraph_.size());
+    Circuit(current_vertex_, 0);
+  }
+
+  out_cut_edges->swap(cut_edges_);
+  LOG(INFO) << "Cycle breaker skipped " << skipped_ops_ << " ops.";
+  DCHECK(stack_.empty());
+}
+
+static const size_t kMaxEdgesToConsider = 2;
+
+void CycleBreaker::HandleCircuit() {
+  stack_.push_back(current_vertex_);
+  CHECK_GE(stack_.size(),
+           static_cast<std::vector<Vertex::Index>::size_type>(2));
+  Edge min_edge = make_pair(stack_[0], stack_[1]);
+  uint64_t min_edge_weight = kuint64max;
+  size_t edges_considered = 0;
+  for (vector<Vertex::Index>::const_iterator it = stack_.begin();
+       it != (stack_.end() - 1); ++it) {
+    Edge edge = make_pair(*it, *(it + 1));
+    if (cut_edges_.find(edge) != cut_edges_.end()) {
+      stack_.pop_back();
+      return;
+    }
+    uint64_t edge_weight = graph_utils::EdgeWeight(subgraph_, edge);
+    if (edge_weight < min_edge_weight) {
+      min_edge_weight = edge_weight;
+      min_edge = edge;
+    }
+    edges_considered++;
+    if (edges_considered == kMaxEdgesToConsider)
+      break;
+  }
+  cut_edges_.insert(min_edge);
+  stack_.pop_back();
+}
+
+void CycleBreaker::Unblock(Vertex::Index u) {
+  blocked_[u] = false;
+
+  for (Vertex::EdgeMap::iterator it = blocked_graph_[u].out_edges.begin();
+       it != blocked_graph_[u].out_edges.end(); ) {
+    Vertex::Index w = it->first;
+    blocked_graph_[u].out_edges.erase(it++);
+    if (blocked_[w])
+      Unblock(w);
+  }
+}
+
+bool CycleBreaker::StackContainsCutEdge() const {
+  for (std::vector<Vertex::Index>::const_iterator it = ++stack_.begin(),
+           e = stack_.end(); it != e; ++it) {
+    Edge edge = make_pair(*(it - 1), *it);
+    if (utils::SetContainsKey(cut_edges_, edge)) {
+      return true;
+    }
+  }
+  return false;
+}
+
+bool CycleBreaker::Circuit(Vertex::Index vertex, Vertex::Index depth) {
+  // "vertex" was "v" in the original paper.
+  bool found = false;  // Was "f" in the original paper.
+  stack_.push_back(vertex);
+  blocked_[vertex] = true;
+  {
+    static int counter = 0;
+    counter++;
+    if (counter == 10000) {
+      counter = 0;
+      std::string stack_str;
+      for (vector<Vertex::Index>::const_iterator it = stack_.begin();
+           it != stack_.end(); ++it) {
+        stack_str += base::StringPrintf("%lu -> ",
+                                        static_cast<long unsigned int>(*it));
+      }
+      LOG(INFO) << "stack: " << stack_str;
+    }
+  }
+
+  for (Vertex::SubgraphEdgeMap::iterator w =
+           subgraph_[vertex].subgraph_edges.begin();
+       w != subgraph_[vertex].subgraph_edges.end(); ++w) {
+    if (*w == current_vertex_) {
+      // The original paper called for printing stack_ followed by
+      // current_vertex_ here, which is a cycle. Instead, we call
+      // HandleCircuit() to break it.
+      HandleCircuit();
+      found = true;
+    } else if (!blocked_[*w]) {
+      if (Circuit(*w, depth + 1)) {
+        found = true;
+        if ((depth > kMaxEdgesToConsider) || StackContainsCutEdge())
+          break;
+      }
+    }
+  }
+
+  if (found) {
+    Unblock(vertex);
+  } else {
+    for (Vertex::SubgraphEdgeMap::iterator w =
+             subgraph_[vertex].subgraph_edges.begin();
+         w != subgraph_[vertex].subgraph_edges.end(); ++w) {
+      if (blocked_graph_[*w].out_edges.find(vertex) ==
+          blocked_graph_[*w].out_edges.end()) {
+        blocked_graph_[*w].out_edges.insert(make_pair(vertex,
+                                                      EdgeProperties()));
+      }
+    }
+  }
+  CHECK_EQ(vertex, stack_.back());
+  stack_.pop_back();
+  return found;
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/cycle_breaker.h b/payload_generator/cycle_breaker.h
new file mode 100644
index 0000000..d0ae3fd
--- /dev/null
+++ b/payload_generator/cycle_breaker.h
@@ -0,0 +1,59 @@
+// 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 CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_CYCLE_BREAKER_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_CYCLE_BREAKER_H_
+
+// This is a modified implementation of Donald B. Johnson's algorithm for
+// finding all elementary cycles (a.k.a. circuits) in a directed graph.
+// See the paper "Finding All the Elementary Circuits of a Directed Graph"
+// at http://dutta.csc.ncsu.edu/csc791_spring07/wrap/circuits_johnson.pdf
+// for reference.
+
+// Note: this version of the algorithm not only finds cycles, but breaks them.
+// It uses a simple greedy algorithm for cutting: when a cycle is discovered,
+// the edge with the least weight is cut. Longer term we may wish to do
+// something more intelligent, since the goal is (ideally) to minimize the
+// sum of the weights of all cut cycles. In practice, it's intractable
+// to consider all cycles before cutting any; there are simply too many.
+// In a sample graph representative of a typical workload, I found over
+// 5 * 10^15 cycles.
+
+#include <set>
+#include <vector>
+
+#include "update_engine/payload_generator/graph_types.h"
+
+namespace chromeos_update_engine {
+
+class CycleBreaker {
+ public:
+  CycleBreaker() : skipped_ops_(0) {}
+  // out_cut_edges is replaced with the cut edges.
+  void BreakCycles(const Graph& graph, std::set<Edge>* out_cut_edges);
+
+  size_t skipped_ops() const { return skipped_ops_; }
+
+ private:
+  void HandleCircuit();
+  void Unblock(Vertex::Index u);
+  bool Circuit(Vertex::Index vertex, Vertex::Index depth);
+  bool StackContainsCutEdge() const;
+
+  std::vector<bool> blocked_;  // "blocked" in the paper
+  Vertex::Index current_vertex_;  // "s" in the paper
+  std::vector<Vertex::Index> stack_;  // the stack variable in the paper
+  Graph subgraph_;  // "A_K" in the paper
+  Graph blocked_graph_;  // "B" in the paper
+
+  std::set<Edge> cut_edges_;
+
+  // Number of operations skipped b/c we know they don't have any
+  // incoming edges.
+  size_t skipped_ops_;
+};
+
+}  // namespace chromeos_update_engine
+
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_CYCLE_BREAKER_H_
diff --git a/payload_generator/cycle_breaker_unittest.cc b/payload_generator/cycle_breaker_unittest.cc
new file mode 100644
index 0000000..b2cd5d4
--- /dev/null
+++ b/payload_generator/cycle_breaker_unittest.cc
@@ -0,0 +1,266 @@
+// 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/cycle_breaker.h"
+
+#include <set>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include <base/logging.h>
+#include <gtest/gtest.h>
+
+#include "update_engine/payload_generator/graph_types.h"
+#include "update_engine/utils.h"
+
+using std::make_pair;
+using std::pair;
+using std::set;
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+void SetOpForNodes(Graph* graph) {
+  for (Graph::iterator it = graph->begin(), e = graph->end(); it != e; ++it) {
+    it->op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+  }
+}
+}  // namespace {}
+
+class CycleBreakerTest : public ::testing::Test {};
+
+TEST(CycleBreakerTest, SimpleTest) {
+  int counter = 0;
+  const Vertex::Index n_a = counter++;
+  const Vertex::Index n_b = counter++;
+  const Vertex::Index n_c = counter++;
+  const Vertex::Index n_d = counter++;
+  const Vertex::Index n_e = counter++;
+  const Vertex::Index n_f = counter++;
+  const Vertex::Index n_g = counter++;
+  const Vertex::Index n_h = counter++;
+  const Graph::size_type kNodeCount = counter++;
+
+  Graph graph(kNodeCount);
+  SetOpForNodes(&graph);
+
+  graph[n_a].out_edges.insert(make_pair(n_e, EdgeProperties()));
+  graph[n_a].out_edges.insert(make_pair(n_f, EdgeProperties()));
+  graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties()));
+  graph[n_c].out_edges.insert(make_pair(n_d, EdgeProperties()));
+  graph[n_d].out_edges.insert(make_pair(n_e, EdgeProperties()));
+  graph[n_d].out_edges.insert(make_pair(n_f, EdgeProperties()));
+  graph[n_e].out_edges.insert(make_pair(n_b, EdgeProperties()));
+  graph[n_e].out_edges.insert(make_pair(n_c, EdgeProperties()));
+  graph[n_e].out_edges.insert(make_pair(n_f, EdgeProperties()));
+  graph[n_f].out_edges.insert(make_pair(n_g, EdgeProperties()));
+  graph[n_g].out_edges.insert(make_pair(n_h, EdgeProperties()));
+  graph[n_h].out_edges.insert(make_pair(n_g, EdgeProperties()));
+
+  CycleBreaker breaker;
+
+  set<Edge> broken_edges;
+  breaker.BreakCycles(graph, &broken_edges);
+
+  // The following cycles must be cut:
+  // A->E->B
+  // C->D->E
+  // G->H
+
+  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_a, n_e)) ||
+              utils::SetContainsKey(broken_edges, make_pair(n_e, n_b)) ||
+              utils::SetContainsKey(broken_edges, make_pair(n_b, n_a)));
+  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_c, n_d)) ||
+              utils::SetContainsKey(broken_edges, make_pair(n_d, n_e)) ||
+              utils::SetContainsKey(broken_edges, make_pair(n_e, n_c)));
+  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_g, n_h)) ||
+              utils::SetContainsKey(broken_edges, make_pair(n_h, n_g)));
+  EXPECT_EQ(3, broken_edges.size());
+}
+
+namespace {
+pair<Vertex::Index, EdgeProperties> EdgeWithWeight(Vertex::Index dest,
+uint64_t weight) {
+  EdgeProperties props;
+  props.extents.resize(1);
+  props.extents[0].set_num_blocks(weight);
+  return make_pair(dest, props);
+}
+}  // namespace {}
+
+
+// This creates a bunch of cycles like this:
+//
+//               root <------.
+//    (t)->     / | \        |
+//             V  V  V       |
+//             N  N  N       |
+//              \ | /        |
+//               VVV         |
+//                N          |
+//              / | \        |
+//             V  V  V       |
+//             N  N  N       |
+//               ...         |
+//     (s)->    \ | /        |
+//               VVV         |
+//                N          |
+//                 \_________/
+//
+// such that the original cutting algo would cut edges (s). We changed
+// the algorithm to cut cycles (t) instead, since they are closer to the
+// root, and that can massively speed up cycle cutting.
+TEST(CycleBreakerTest, AggressiveCutTest) {
+  int counter = 0;
+
+  const int kNodesPerGroup = 4;
+  const int kGroups = 33;
+
+  Graph graph(kGroups * kNodesPerGroup + 1);  // + 1 for the root node
+  SetOpForNodes(&graph);
+
+  const Vertex::Index n_root = counter++;
+
+  Vertex::Index last_hub = n_root;
+  for (int i = 0; i < kGroups; i++) {
+    uint64_t weight = 5;
+    if (i == 0)
+      weight = 2;
+    else if (i == (kGroups - 1))
+      weight = 1;
+
+    const Vertex::Index next_hub = counter++;
+
+    for (int j = 0; j < (kNodesPerGroup - 1); j++) {
+      const Vertex::Index node = counter++;
+      graph[last_hub].out_edges.insert(EdgeWithWeight(node, weight));
+      graph[node].out_edges.insert(EdgeWithWeight(next_hub, weight));
+    }
+    last_hub = next_hub;
+  }
+
+  graph[last_hub].out_edges.insert(EdgeWithWeight(n_root, 5));
+
+  EXPECT_EQ(counter, graph.size());
+
+  CycleBreaker breaker;
+
+  set<Edge> broken_edges;
+  LOG(INFO) << "If this hangs for more than 1 second, the test has failed.";
+  breaker.BreakCycles(graph, &broken_edges);
+
+  set<Edge> expected_cuts;
+
+  for (Vertex::EdgeMap::const_iterator it = graph[n_root].out_edges.begin(),
+       e = graph[n_root].out_edges.end(); it != e; ++it) {
+    expected_cuts.insert(make_pair(n_root, it->first));
+  }
+
+  EXPECT_TRUE(broken_edges == expected_cuts);
+}
+
+TEST(CycleBreakerTest, WeightTest) {
+  int counter = 0;
+  const Vertex::Index n_a = counter++;
+  const Vertex::Index n_b = counter++;
+  const Vertex::Index n_c = counter++;
+  const Vertex::Index n_d = counter++;
+  const Vertex::Index n_e = counter++;
+  const Vertex::Index n_f = counter++;
+  const Vertex::Index n_g = counter++;
+  const Vertex::Index n_h = counter++;
+  const Vertex::Index n_i = counter++;
+  const Vertex::Index n_j = counter++;
+  const Graph::size_type kNodeCount = counter++;
+
+  Graph graph(kNodeCount);
+  SetOpForNodes(&graph);
+
+  graph[n_a].out_edges.insert(EdgeWithWeight(n_b, 4));
+  graph[n_a].out_edges.insert(EdgeWithWeight(n_f, 3));
+  graph[n_a].out_edges.insert(EdgeWithWeight(n_h, 2));
+  graph[n_b].out_edges.insert(EdgeWithWeight(n_a, 3));
+  graph[n_b].out_edges.insert(EdgeWithWeight(n_c, 4));
+  graph[n_c].out_edges.insert(EdgeWithWeight(n_b, 5));
+  graph[n_c].out_edges.insert(EdgeWithWeight(n_d, 3));
+  graph[n_d].out_edges.insert(EdgeWithWeight(n_a, 6));
+  graph[n_d].out_edges.insert(EdgeWithWeight(n_e, 3));
+  graph[n_e].out_edges.insert(EdgeWithWeight(n_d, 4));
+  graph[n_e].out_edges.insert(EdgeWithWeight(n_g, 5));
+  graph[n_f].out_edges.insert(EdgeWithWeight(n_g, 2));
+  graph[n_g].out_edges.insert(EdgeWithWeight(n_f, 3));
+  graph[n_g].out_edges.insert(EdgeWithWeight(n_d, 5));
+  graph[n_h].out_edges.insert(EdgeWithWeight(n_i, 8));
+  graph[n_i].out_edges.insert(EdgeWithWeight(n_e, 4));
+  graph[n_i].out_edges.insert(EdgeWithWeight(n_h, 9));
+  graph[n_i].out_edges.insert(EdgeWithWeight(n_j, 6));
+
+  CycleBreaker breaker;
+
+  set<Edge> broken_edges;
+  breaker.BreakCycles(graph, &broken_edges);
+
+  // These are required to be broken:
+  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_b, n_a)));
+  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_b, n_c)));
+  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_d, n_e)));
+  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_f, n_g)));
+  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_h, n_i)));
+}
+
+TEST(CycleBreakerTest, UnblockGraphTest) {
+  int counter = 0;
+  const Vertex::Index n_a = counter++;
+  const Vertex::Index n_b = counter++;
+  const Vertex::Index n_c = counter++;
+  const Vertex::Index n_d = counter++;
+  const Graph::size_type kNodeCount = counter++;
+
+  Graph graph(kNodeCount);
+  SetOpForNodes(&graph);
+
+  graph[n_a].out_edges.insert(EdgeWithWeight(n_b, 1));
+  graph[n_a].out_edges.insert(EdgeWithWeight(n_c, 1));
+  graph[n_b].out_edges.insert(EdgeWithWeight(n_c, 2));
+  graph[n_c].out_edges.insert(EdgeWithWeight(n_b, 2));
+  graph[n_b].out_edges.insert(EdgeWithWeight(n_d, 2));
+  graph[n_d].out_edges.insert(EdgeWithWeight(n_a, 2));
+
+  CycleBreaker breaker;
+
+  set<Edge> broken_edges;
+  breaker.BreakCycles(graph, &broken_edges);
+
+  // These are required to be broken:
+  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_a, n_b)));
+  EXPECT_TRUE(utils::SetContainsKey(broken_edges, make_pair(n_a, n_c)));
+}
+
+TEST(CycleBreakerTest, SkipOpsTest) {
+  int counter = 0;
+  const Vertex::Index n_a = counter++;
+  const Vertex::Index n_b = counter++;
+  const Vertex::Index n_c = counter++;
+  const Graph::size_type kNodeCount = counter++;
+
+  Graph graph(kNodeCount);
+  SetOpForNodes(&graph);
+  graph[n_a].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+  graph[n_c].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+
+  graph[n_a].out_edges.insert(EdgeWithWeight(n_b, 1));
+  graph[n_c].out_edges.insert(EdgeWithWeight(n_b, 1));
+
+  CycleBreaker breaker;
+
+  set<Edge> broken_edges;
+  breaker.BreakCycles(graph, &broken_edges);
+
+  EXPECT_EQ(2, breaker.skipped_ops());
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/delta_diff_generator.cc b/payload_generator/delta_diff_generator.cc
new file mode 100644
index 0000000..8fbbd0d
--- /dev/null
+++ b/payload_generator/delta_diff_generator.cc
@@ -0,0 +1,1928 @@
+// 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 <errno.h>
+#include <fcntl.h>
+#include <inttypes.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+
+#include <algorithm>
+#include <map>
+#include <set>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include <base/file_util.h>
+#include <base/files/file_path.h>
+#include <base/logging.h>
+#include <base/memory/scoped_ptr.h>
+#include <base/strings/string_number_conversions.h>
+#include <base/strings/string_util.h>
+#include <base/strings/stringprintf.h>
+#include <bzlib.h>
+
+#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/cycle_breaker.h"
+#include "update_engine/payload_generator/extent_mapper.h"
+#include "update_engine/payload_generator/filesystem_iterator.h"
+#include "update_engine/payload_generator/full_update_generator.h"
+#include "update_engine/payload_generator/graph_types.h"
+#include "update_engine/payload_generator/graph_utils.h"
+#include "update_engine/payload_generator/metadata.h"
+#include "update_engine/payload_generator/topological_sort.h"
+#include "update_engine/payload_signer.h"
+#include "update_engine/subprocess.h"
+#include "update_engine/update_metadata.pb.h"
+#include "update_engine/utils.h"
+
+using std::make_pair;
+using std::map;
+using std::max;
+using std::min;
+using std::pair;
+using std::set;
+using std::string;
+using std::vector;
+
+namespace {
+
+const uint64_t kVersionNumber = 1;
+const uint64_t kFullUpdateChunkSize = 1024 * 1024;  // bytes
+
+const size_t kBlockSize = 4096;  // bytes
+const string kNonexistentPath = "";
+
+static const char* kInstallOperationTypes[] = {
+  "REPLACE",
+  "REPLACE_BZ",
+  "MOVE",
+  "BSDIFF"
+};
+
+}  // namespace
+
+namespace chromeos_update_engine {
+
+typedef DeltaDiffGenerator::Block Block;
+typedef map<const DeltaArchiveManifest_InstallOperation*,
+            string> OperationNameMap;
+
+// bytes
+const size_t kRootFSPartitionSize = static_cast<size_t>(2) * 1024 * 1024 * 1024;
+
+// Needed for testing purposes, in case we can't use actual filesystem objects.
+// TODO(garnold)(chromium:331965) Replace this hack with a properly injected
+// parameter in form of a mockable abstract class.
+bool (*get_extents_with_chunk_func)(const std::string&, off_t, off_t,
+                                    std::vector<Extent>*) =
+    extent_mapper::ExtentsForFileChunkFibmap;
+
+namespace {
+
+// Stores all the extents of |path| into |extents|. Returns true on success.
+bool GatherExtents(const string& path,
+                   off_t chunk_offset,
+                   off_t chunk_size,
+                   vector<Extent>* extents) {
+  extents->clear();
+  TEST_AND_RETURN_FALSE(
+      get_extents_with_chunk_func(
+          path, chunk_offset, chunk_size, extents));
+  return true;
+}
+
+// For a given regular file which must exist at new_root + path, and
+// may exist at old_root + path, creates a new InstallOperation and
+// adds it to the graph. Also, populates the |blocks| array as
+// necessary, if |blocks| is non-NULL.  Also, writes the data
+// necessary to send the file down to the client into data_fd, which
+// has length *data_file_size. *data_file_size is updated
+// appropriately. If |existing_vertex| is no kInvalidIndex, use that
+// rather than allocating a new vertex. Returns true on success.
+bool DeltaReadFile(Graph* graph,
+                   Vertex::Index existing_vertex,
+                   vector<Block>* blocks,
+                   const string& old_root,
+                   const string& new_root,
+                   const string& path,  // within new_root
+                   off_t chunk_offset,
+                   off_t chunk_size,
+                   int data_fd,
+                   off_t* data_file_size) {
+  vector<char> data;
+  DeltaArchiveManifest_InstallOperation operation;
+
+  string old_path = (old_root == kNonexistentPath) ? kNonexistentPath :
+      old_root + path;
+
+  // If bsdiff breaks again, blacklist the problem file by using:
+  //   bsdiff_allowed = (path != "/foo/bar")
+  //
+  // TODO(dgarrett): chromium-os:15274 connect this test to the command line.
+  bool bsdiff_allowed = true;
+
+  if (!bsdiff_allowed)
+    LOG(INFO) << "bsdiff blacklisting: " << path;
+
+  TEST_AND_RETURN_FALSE(DeltaDiffGenerator::ReadFileToDiff(old_path,
+                                                           new_root + path,
+                                                           chunk_offset,
+                                                           chunk_size,
+                                                           bsdiff_allowed,
+                                                           &data,
+                                                           &operation,
+                                                           true));
+
+  // Check if the operation writes nothing.
+  if (operation.dst_extents_size() == 0) {
+    if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE) {
+      LOG(INFO) << "Empty MOVE operation (" << new_root + path << "), skipping";
+      return true;
+    } else {
+      LOG(ERROR) << "Empty non-MOVE operation";
+      return false;
+    }
+  }
+
+  // Write the data
+  if (operation.type() != DeltaArchiveManifest_InstallOperation_Type_MOVE) {
+    operation.set_data_offset(*data_file_size);
+    operation.set_data_length(data.size());
+  }
+
+  TEST_AND_RETURN_FALSE(utils::WriteAll(data_fd, &data[0], data.size()));
+  *data_file_size += data.size();
+
+  // Now, insert into graph and blocks vector
+  Vertex::Index vertex = existing_vertex;
+  if (vertex == Vertex::kInvalidIndex) {
+    graph->resize(graph->size() + 1);
+    vertex = graph->size() - 1;
+  }
+  (*graph)[vertex].op = operation;
+  CHECK((*graph)[vertex].op.has_type());
+  (*graph)[vertex].file_name = path;
+  (*graph)[vertex].chunk_offset = chunk_offset;
+  (*graph)[vertex].chunk_size = chunk_size;
+
+  if (blocks)
+    TEST_AND_RETURN_FALSE(DeltaDiffGenerator::AddInstallOpToBlocksVector(
+        (*graph)[vertex].op,
+        *graph,
+        vertex,
+        blocks));
+  return true;
+}
+
+// For each regular file within new_root, creates a node in the graph,
+// determines the best way to compress it (REPLACE, REPLACE_BZ, COPY, BSDIFF),
+// and writes any necessary data to the end of data_fd.
+bool DeltaReadFiles(Graph* graph,
+                    vector<Block>* blocks,
+                    const string& old_root,
+                    const string& new_root,
+                    off_t chunk_size,
+                    int data_fd,
+                    off_t* data_file_size) {
+  set<ino_t> visited_inodes;
+  set<ino_t> visited_src_inodes;
+  for (FilesystemIterator fs_iter(new_root,
+                                  utils::SetWithValue<string>("/lost+found"));
+       !fs_iter.IsEnd(); fs_iter.Increment()) {
+    // We never diff symlinks (here, we check that dst file is not a symlink).
+    if (!S_ISREG(fs_iter.GetStat().st_mode))
+      continue;
+
+    // Make sure we visit each inode only once.
+    if (utils::SetContainsKey(visited_inodes, fs_iter.GetStat().st_ino))
+      continue;
+    visited_inodes.insert(fs_iter.GetStat().st_ino);
+    off_t dst_size = fs_iter.GetStat().st_size;
+    if (dst_size == 0)
+      continue;
+
+    LOG(INFO) << "Encoding file " << fs_iter.GetPartialPath();
+
+    // 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 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
+    bool should_diff_from_source = false;
+    string src_path = old_root + fs_iter.GetPartialPath();
+    struct stat src_stbuf;
+    // We never diff symlinks (here, we check that src file is not a symlink).
+    if (0 == lstat(src_path.c_str(), &src_stbuf) &&
+        S_ISREG(src_stbuf.st_mode)) {
+      should_diff_from_source = !utils::SetContainsKey(visited_src_inodes,
+                                                       src_stbuf.st_ino);
+      visited_src_inodes.insert(src_stbuf.st_ino);
+    }
+
+    off_t size = chunk_size == -1 ? dst_size : chunk_size;
+    off_t step = size;
+    for (off_t offset = 0; offset < dst_size; offset += step) {
+      if (offset + size >= dst_size) {
+        size = -1;  // Read through the end of the file.
+      }
+      TEST_AND_RETURN_FALSE(DeltaReadFile(graph,
+                                          Vertex::kInvalidIndex,
+                                          blocks,
+                                          (should_diff_from_source ?
+                                           old_root :
+                                           kNonexistentPath),
+                                          new_root,
+                                          fs_iter.GetPartialPath(),
+                                          offset,
+                                          size,
+                                          data_fd,
+                                          data_file_size));
+    }
+  }
+  return true;
+}
+
+// This class allocates non-existent temp blocks, starting from
+// kTempBlockStart. Other code is responsible for converting these
+// temp blocks into real blocks, as the client can't read or write to
+// these blocks.
+class DummyExtentAllocator {
+ public:
+  explicit DummyExtentAllocator()
+      : next_block_(kTempBlockStart) {}
+  vector<Extent> Allocate(const uint64_t block_count) {
+    vector<Extent> ret(1);
+    ret[0].set_start_block(next_block_);
+    ret[0].set_num_blocks(block_count);
+    next_block_ += block_count;
+    return ret;
+  }
+ private:
+  uint64_t next_block_;
+};
+
+// Reads blocks from image_path that are not yet marked as being written
+// in the blocks array. These blocks that remain are non-file-data blocks.
+// In the future we might consider intelligent diffing between this data
+// and data in the previous image, but for now we just bzip2 compress it
+// and include it in the update.
+// Creates a new node in the graph to write these blocks and writes the
+// appropriate blob to blobs_fd. Reads and updates blobs_length;
+bool ReadUnwrittenBlocks(const vector<Block>& blocks,
+                         int blobs_fd,
+                         off_t* blobs_length,
+                         const string& image_path,
+                         Vertex* vertex) {
+  vertex->file_name = "<rootfs-non-file-data>";
+
+  DeltaArchiveManifest_InstallOperation* out_op = &vertex->op;
+  int image_fd = open(image_path.c_str(), O_RDONLY, 000);
+  TEST_AND_RETURN_FALSE_ERRNO(image_fd >= 0);
+  ScopedFdCloser image_fd_closer(&image_fd);
+
+  string temp_file_path;
+  TEST_AND_RETURN_FALSE(utils::MakeTempFile("CrAU_temp_data.XXXXXX",
+                                            &temp_file_path,
+                                            NULL));
+
+  FILE* file = fopen(temp_file_path.c_str(), "w");
+  TEST_AND_RETURN_FALSE(file);
+  int err = BZ_OK;
+
+  BZFILE* bz_file = BZ2_bzWriteOpen(&err,
+                                    file,
+                                    9,  // max compression
+                                    0,  // verbosity
+                                    0);  // default work factor
+  TEST_AND_RETURN_FALSE(err == BZ_OK);
+
+  vector<Extent> extents;
+  vector<Block>::size_type block_count = 0;
+
+  LOG(INFO) << "Appending left over blocks to extents";
+  for (vector<Block>::size_type i = 0; i < blocks.size(); i++) {
+    if (blocks[i].writer != Vertex::kInvalidIndex)
+      continue;
+    if (blocks[i].reader != Vertex::kInvalidIndex) {
+      graph_utils::AddReadBeforeDep(vertex, blocks[i].reader, i);
+    }
+    graph_utils::AppendBlockToExtents(&extents, i);
+    block_count++;
+  }
+
+  // Code will handle 'buf' at any size that's a multiple of kBlockSize,
+  // so we arbitrarily set it to 1024 * kBlockSize.
+  vector<char> buf(1024 * kBlockSize);
+
+  LOG(INFO) << "Reading left over blocks";
+  vector<Block>::size_type blocks_copied_count = 0;
+
+  // For each extent in extents, write the data into BZ2_bzWrite which
+  // sends it to an output file.
+  // We use the temporary buffer 'buf' to hold the data, which may be
+  // smaller than the extent, so in that case we have to loop to get
+  // the extent's data (that's the inner while loop).
+  for (vector<Extent>::const_iterator it = extents.begin();
+       it != extents.end(); ++it) {
+    vector<Block>::size_type blocks_read = 0;
+    float printed_progress = -1;
+    while (blocks_read < it->num_blocks()) {
+      const int copy_block_cnt =
+          min(buf.size() / kBlockSize,
+              static_cast<vector<char>::size_type>(
+                  it->num_blocks() - blocks_read));
+      ssize_t rc = pread(image_fd,
+                         &buf[0],
+                         copy_block_cnt * kBlockSize,
+                         (it->start_block() + blocks_read) * kBlockSize);
+      TEST_AND_RETURN_FALSE_ERRNO(rc >= 0);
+      TEST_AND_RETURN_FALSE(static_cast<size_t>(rc) ==
+                            copy_block_cnt * kBlockSize);
+      BZ2_bzWrite(&err, bz_file, &buf[0], copy_block_cnt * kBlockSize);
+      TEST_AND_RETURN_FALSE(err == BZ_OK);
+      blocks_read += copy_block_cnt;
+      blocks_copied_count += copy_block_cnt;
+      float current_progress =
+          static_cast<float>(blocks_copied_count) / block_count;
+      if (printed_progress + 0.1 < current_progress ||
+          blocks_copied_count == block_count) {
+        LOG(INFO) << "progress: " << current_progress;
+        printed_progress = current_progress;
+      }
+    }
+  }
+  BZ2_bzWriteClose(&err, bz_file, 0, NULL, NULL);
+  TEST_AND_RETURN_FALSE(err == BZ_OK);
+  bz_file = NULL;
+  TEST_AND_RETURN_FALSE_ERRNO(0 == fclose(file));
+  file = NULL;
+
+  vector<char> compressed_data;
+  LOG(INFO) << "Reading compressed data off disk";
+  TEST_AND_RETURN_FALSE(utils::ReadFile(temp_file_path, &compressed_data));
+  TEST_AND_RETURN_FALSE(unlink(temp_file_path.c_str()) == 0);
+
+  // Add node to graph to write these blocks
+  out_op->set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+  out_op->set_data_offset(*blobs_length);
+  out_op->set_data_length(compressed_data.size());
+  LOG(INFO) << "Rootfs non-data blocks compressed take up "
+            << compressed_data.size();
+  *blobs_length += compressed_data.size();
+  out_op->set_dst_length(kBlockSize * block_count);
+  DeltaDiffGenerator::StoreExtents(extents, out_op->mutable_dst_extents());
+
+  TEST_AND_RETURN_FALSE(utils::WriteAll(blobs_fd,
+                                        &compressed_data[0],
+                                        compressed_data.size()));
+  LOG(INFO) << "done with extra blocks";
+  return true;
+}
+
+// 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 |graph| to |out_manifest| in the order specified by
+// |order| while building |out_op_name_map| with operation to name
+// mappings. Adds all |kernel_ops| to |out_manifest|. Filters out no-op
+// operations.
+void InstallOperationsToManifest(
+    const Graph& graph,
+    const vector<Vertex::Index>& order,
+    const vector<DeltaArchiveManifest_InstallOperation>& kernel_ops,
+    DeltaArchiveManifest* out_manifest,
+    OperationNameMap* out_op_name_map) {
+  for (vector<Vertex::Index>::const_iterator it = order.begin();
+       it != order.end(); ++it) {
+    const Vertex& vertex = graph[*it];
+    const DeltaArchiveManifest_InstallOperation& add_op = vertex.op;
+    if (DeltaDiffGenerator::IsNoopOperation(add_op)) {
+      continue;
+    }
+    DeltaArchiveManifest_InstallOperation* op =
+        out_manifest->add_install_operations();
+    *op = add_op;
+    string name = vertex.file_name;
+    if (vertex.chunk_offset || vertex.chunk_size != -1) {
+      string offset = base::Int64ToString(vertex.chunk_offset);
+      if (vertex.chunk_size != -1) {
+        name += " [" + offset + ", " +
+            base::Int64ToString(vertex.chunk_offset + vertex.chunk_size - 1) +
+            "]";
+      } else {
+        name += " [" + offset + ", end]";
+      }
+    }
+    (*out_op_name_map)[op] = name;
+  }
+  for (vector<DeltaArchiveManifest_InstallOperation>::const_iterator it =
+           kernel_ops.begin(); it != kernel_ops.end(); ++it) {
+    const DeltaArchiveManifest_InstallOperation& add_op = *it;
+    if (DeltaDiffGenerator::IsNoopOperation(add_op)) {
+      continue;
+    }
+    DeltaArchiveManifest_InstallOperation* op =
+        out_manifest->add_kernel_install_operations();
+    *op = add_op;
+  }
+}
+
+void CheckGraph(const Graph& graph) {
+  for (Graph::const_iterator it = graph.begin(); it != graph.end(); ++it) {
+    CHECK(it->op.has_type());
+  }
+}
+
+// Delta compresses a kernel partition |new_kernel_part| with knowledge of the
+// old kernel partition |old_kernel_part|. If |old_kernel_part| is an empty
+// string, generates a full update of the partition.
+bool DeltaCompressKernelPartition(
+    const string& old_kernel_part,
+    const string& new_kernel_part,
+    vector<DeltaArchiveManifest_InstallOperation>* ops,
+    int blobs_fd,
+    off_t* blobs_length) {
+  LOG(INFO) << "Delta compressing kernel partition...";
+  LOG_IF(INFO, old_kernel_part.empty()) << "Generating full kernel update...";
+
+  DeltaArchiveManifest_InstallOperation op;
+  vector<char> data;
+  TEST_AND_RETURN_FALSE(
+      DeltaDiffGenerator::ReadFileToDiff(old_kernel_part,
+                                         new_kernel_part,
+                                         0,  // chunk_offset
+                                         -1,  // chunk_size
+                                         true, // bsdiff_allowed
+                                         &data,
+                                         &op,
+                                         false));
+
+  // Check if the operation writes nothing.
+  if (op.dst_extents_size() == 0) {
+    if (op.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE) {
+      LOG(INFO) << "Empty MOVE operation, nothing to do.";
+      return true;
+    } else {
+      LOG(ERROR) << "Empty non-MOVE operation";
+      return false;
+    }
+  }
+
+  // Write the data.
+  if (op.type() != DeltaArchiveManifest_InstallOperation_Type_MOVE) {
+    op.set_data_offset(*blobs_length);
+    op.set_data_length(data.size());
+  }
+
+  // Add the new install operation.
+  ops->clear();
+  ops->push_back(op);
+
+  TEST_AND_RETURN_FALSE(utils::WriteAll(blobs_fd, &data[0], data.size()));
+  *blobs_length += data.size();
+
+  LOG(INFO) << "Done delta compressing kernel partition: "
+            << kInstallOperationTypes[op.type()];
+  return true;
+}
+
+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;
+
+  std::sort(objects.begin(), objects.end());
+
+  static const char kFormatString[] = "%6.2f%% %10jd %-10s %s\n";
+  for (vector<DeltaObject>::const_iterator it = objects.begin();
+       it != objects.end(); ++it) {
+    const DeltaObject& object = *it;
+    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 = 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 {}
+
+bool DeltaDiffGenerator::ReadFileToDiff(
+    const string& old_filename,
+    const string& new_filename,
+    off_t chunk_offset,
+    off_t chunk_size,
+    bool bsdiff_allowed,
+    vector<char>* out_data,
+    DeltaArchiveManifest_InstallOperation* out_op,
+    bool gather_extents) {
+  // Read new data in
+  vector<char> new_data;
+  TEST_AND_RETURN_FALSE(
+      utils::ReadFileChunk(new_filename, chunk_offset, chunk_size, &new_data));
+
+  TEST_AND_RETURN_FALSE(!new_data.empty());
+  TEST_AND_RETURN_FALSE(chunk_size == -1 ||
+                        static_cast<off_t>(new_data.size()) <= chunk_size);
+
+  vector<char> new_data_bz;
+  TEST_AND_RETURN_FALSE(BzipCompress(new_data, &new_data_bz));
+  CHECK(!new_data_bz.empty());
+
+  vector<char> data;  // Data blob that will be written to delta file.
+
+  DeltaArchiveManifest_InstallOperation operation;
+  size_t current_best_size = 0;
+  if (new_data.size() <= new_data_bz.size()) {
+    operation.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+    current_best_size = new_data.size();
+    data = new_data;
+  } else {
+    operation.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+    current_best_size = new_data_bz.size();
+    data = new_data_bz;
+  }
+
+  // Do we have an original file to consider?
+  struct stat old_stbuf;
+  bool original = !old_filename.empty();
+  if (original && 0 != stat(old_filename.c_str(), &old_stbuf)) {
+    // If stat-ing the old file fails, it should be because it doesn't exist.
+    TEST_AND_RETURN_FALSE(errno == ENOTDIR || errno == ENOENT);
+    original = false;
+  }
+
+  vector<char> old_data;
+  if (original) {
+    // Read old data
+    TEST_AND_RETURN_FALSE(
+        utils::ReadFileChunk(
+            old_filename, chunk_offset, chunk_size, &old_data));
+    if (old_data == new_data) {
+      // No change in data.
+      operation.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+      current_best_size = 0;
+      data.clear();
+    } else if (!old_data.empty() && 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[0], 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[0], new_data.size()));
+
+      vector<char> bsdiff_delta;
+      TEST_AND_RETURN_FALSE(
+          BsdiffFiles(old_chunk.value(), new_chunk.value(), &bsdiff_delta));
+      CHECK_GT(bsdiff_delta.size(), static_cast<vector<char>::size_type>(0));
+      if (bsdiff_delta.size() < current_best_size) {
+        operation.set_type(DeltaArchiveManifest_InstallOperation_Type_BSDIFF);
+        current_best_size = bsdiff_delta.size();
+        data = bsdiff_delta;
+      }
+    }
+  }
+
+  // Set parameters of the operations
+  CHECK_EQ(data.size(), current_best_size);
+
+  vector<Extent> src_extents, dst_extents;
+  if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE ||
+      operation.type() == DeltaArchiveManifest_InstallOperation_Type_BSDIFF) {
+    if (gather_extents) {
+      TEST_AND_RETURN_FALSE(
+          GatherExtents(old_filename,
+                        chunk_offset,
+                        chunk_size,
+                        &src_extents));
+    } else {
+      Extent* src_extent = operation.add_src_extents();
+      src_extent->set_start_block(0);
+      src_extent->set_num_blocks(
+          (old_stbuf.st_size + kBlockSize - 1) / kBlockSize);
+    }
+    operation.set_src_length(old_data.size());
+  }
+
+  if (gather_extents) {
+    TEST_AND_RETURN_FALSE(
+        GatherExtents(new_filename,
+                      chunk_offset,
+                      chunk_size,
+                      &dst_extents));
+  } else {
+    Extent* dst_extent = operation.add_dst_extents();
+    dst_extent->set_start_block(0);
+    dst_extent->set_num_blocks((new_data.size() + kBlockSize - 1) / kBlockSize);
+  }
+  operation.set_dst_length(new_data.size());
+
+  if (gather_extents) {
+    // Remove identical src/dst block ranges in MOVE operations.
+    if (operation.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE) {
+      size_t removed_bytes = RemoveIdenticalBlockRanges(
+          &src_extents, &dst_extents, new_data.size());
+
+      // Adjust the file length field accordingly.
+      if (removed_bytes) {
+        operation.set_src_length(old_data.size() - removed_bytes);
+        operation.set_dst_length(new_data.size() - removed_bytes);
+      }
+    }
+
+    // Embed extents in the operation.
+    DeltaDiffGenerator::StoreExtents(src_extents,
+                                     operation.mutable_src_extents());
+    DeltaDiffGenerator::StoreExtents(dst_extents,
+                                     operation.mutable_dst_extents());
+  }
+
+  out_data->swap(data);
+  *out_op = operation;
+
+  return true;
+}
+
+bool DeltaDiffGenerator::InitializePartitionInfo(bool is_kernel,
+                                                 const string& partition,
+                                                 PartitionInfo* info) {
+  int64_t size = 0;
+  if (is_kernel) {
+    size = utils::FileSize(partition);
+  } else {
+    int block_count = 0, block_size = 0;
+    TEST_AND_RETURN_FALSE(utils::GetFilesystemSize(partition,
+                                                   &block_count,
+                                                   &block_size));
+    size = static_cast<int64_t>(block_count) * block_size;
+  }
+  TEST_AND_RETURN_FALSE(size > 0);
+  info->set_size(size);
+  OmahaHashCalculator hasher;
+  TEST_AND_RETURN_FALSE(hasher.UpdateFile(partition, size) == size);
+  TEST_AND_RETURN_FALSE(hasher.Finalize());
+  const vector<char>& hash = hasher.raw_hash();
+  info->set_hash(hash.data(), hash.size());
+  LOG(INFO) << partition << ": size=" << size << " hash=" << hasher.hash();
+  return true;
+}
+
+bool InitializePartitionInfos(const string& old_kernel,
+                              const string& new_kernel,
+                              const string& old_rootfs,
+                              const string& new_rootfs,
+                              DeltaArchiveManifest* manifest) {
+  if (!old_kernel.empty()) {
+    TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo(
+        true,
+        old_kernel,
+        manifest->mutable_old_kernel_info()));
+  }
+  TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo(
+      true,
+      new_kernel,
+      manifest->mutable_new_kernel_info()));
+  if (!old_rootfs.empty()) {
+    TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo(
+        false,
+        old_rootfs,
+        manifest->mutable_old_rootfs_info()));
+  }
+  TEST_AND_RETURN_FALSE(DeltaDiffGenerator::InitializePartitionInfo(
+      false,
+      new_rootfs,
+      manifest->mutable_new_rootfs_info()));
+  return true;
+}
+
+namespace {
+
+// Takes a collection (vector or RepeatedPtrField) of Extent and
+// returns a vector of the blocks referenced, in order.
+template<typename T>
+vector<uint64_t> ExpandExtents(const T& extents) {
+  vector<uint64_t> ret;
+  for (size_t i = 0, e = static_cast<size_t>(extents.size()); i != e; ++i) {
+    const Extent extent = graph_utils::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 blocks and returns an equivalent vector of Extent
+// objects.
+vector<Extent> CompressExtents(const vector<uint64_t>& blocks) {
+  vector<Extent> new_extents;
+  for (vector<uint64_t>::const_iterator it = blocks.begin(), e = blocks.end();
+       it != e; ++it) {
+    graph_utils::AppendBlockToExtents(&new_extents, *it);
+  }
+  return new_extents;
+}
+
+}  // namespace {}
+
+void DeltaDiffGenerator::SubstituteBlocks(
+    Vertex* vertex,
+    const vector<Extent>& remove_extents,
+    const vector<Extent>& replace_extents) {
+  // First, expand out the blocks that op reads from
+  vector<uint64_t> read_blocks = ExpandExtents(vertex->op.src_extents());
+  {
+    // Expand remove_extents and 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);
+    for (Vertex::EdgeMap::iterator it = vertex->out_edges.begin(),
+             e = vertex->out_edges.end(); it != e; ++it) {
+      vector<uint64_t> write_before_deps_expanded =
+          ExpandExtents(it->second.write_extents);
+      utils::ApplyMap(&write_before_deps_expanded, conversion);
+      it->second.write_extents = CompressExtents(write_before_deps_expanded);
+    }
+  }
+  // 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());
+}
+
+bool DeltaDiffGenerator::CutEdges(Graph* graph,
+                                  const set<Edge>& edges,
+                                  vector<CutEdgeVertexes>* out_cuts) {
+  DummyExtentAllocator scratch_allocator;
+  vector<CutEdgeVertexes> cuts;
+  cuts.reserve(edges.size());
+
+  uint64_t scratch_blocks_used = 0;
+  for (set<Edge>::const_iterator it = edges.begin();
+       it != edges.end(); ++it) {
+    cuts.resize(cuts.size() + 1);
+    vector<Extent> old_extents =
+        (*graph)[it->first].out_edges[it->second].extents;
+    // Choose some scratch space
+    scratch_blocks_used += graph_utils::EdgeWeight(*graph, *it);
+    cuts.back().tmp_extents =
+        scratch_allocator.Allocate(graph_utils::EdgeWeight(*graph, *it));
+    // create vertex to copy original->scratch
+    cuts.back().new_vertex = graph->size();
+    graph->resize(graph->size() + 1);
+    cuts.back().old_src = it->first;
+    cuts.back().old_dst = it->second;
+
+    EdgeProperties& cut_edge_properties =
+        (*graph)[it->first].out_edges.find(it->second)->second;
+
+    // This should never happen, as we should only be cutting edges between
+    // real file nodes, and write-before relationships are created from
+    // a real file node to a temp copy node:
+    CHECK(cut_edge_properties.write_extents.empty())
+        << "Can't cut edge that has write-before relationship.";
+
+    // make node depend on the copy operation
+    (*graph)[it->first].out_edges.insert(make_pair(graph->size() - 1,
+                                                   cut_edge_properties));
+
+    // 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());
+    graph->back().op.set_src_length(
+        graph_utils::EdgeWeight(*graph, *it) * kBlockSize);
+    graph->back().op.set_dst_length(graph->back().op.src_length());
+
+    // make the dest node read from the scratch space
+    DeltaDiffGenerator::SubstituteBlocks(
+        &((*graph)[it->second]),
+        (*graph)[it->first].out_edges[it->second].extents,
+        cuts.back().tmp_extents);
+
+    // delete the old edge
+    CHECK_EQ(static_cast<Graph::size_type>(1),
+             (*graph)[it->first].out_edges.erase(it->second));
+
+    // Add an edge from dst to copy operation
+    EdgeProperties write_before_edge_properties;
+    write_before_edge_properties.write_extents = cuts.back().tmp_extents;
+    (*graph)[it->second].out_edges.insert(
+        make_pair(graph->size() - 1, write_before_edge_properties));
+  }
+  out_cuts->swap(cuts);
+  return true;
+}
+
+// Stores all Extents in 'extents' into 'out'.
+void DeltaDiffGenerator::StoreExtents(
+    const vector<Extent>& extents,
+    google::protobuf::RepeatedPtrField<Extent>* out) {
+  for (vector<Extent>::const_iterator it = extents.begin();
+       it != extents.end(); ++it) {
+    Extent* new_extent = out->Add();
+    *new_extent = *it;
+  }
+}
+
+// Creates all the edges for the graph. Writers of a block point to
+// readers of the same block. This is because for an edge A->B, B
+// must complete before A executes.
+void DeltaDiffGenerator::CreateEdges(Graph* graph,
+                                     const vector<Block>& blocks) {
+  for (vector<Block>::size_type i = 0; i < blocks.size(); i++) {
+    // Blocks with both a reader and writer get an edge
+    if (blocks[i].reader == Vertex::kInvalidIndex ||
+        blocks[i].writer == Vertex::kInvalidIndex)
+      continue;
+    // Don't have a node depend on itself
+    if (blocks[i].reader == blocks[i].writer)
+      continue;
+    // See if there's already an edge we can add onto
+    Vertex::EdgeMap::iterator edge_it =
+        (*graph)[blocks[i].writer].out_edges.find(blocks[i].reader);
+    if (edge_it == (*graph)[blocks[i].writer].out_edges.end()) {
+      // No existing edge. Create one
+      (*graph)[blocks[i].writer].out_edges.insert(
+          make_pair(blocks[i].reader, EdgeProperties()));
+      edge_it = (*graph)[blocks[i].writer].out_edges.find(blocks[i].reader);
+      CHECK(edge_it != (*graph)[blocks[i].writer].out_edges.end());
+    }
+    graph_utils::AppendBlockToExtents(&edge_it->second.extents, i);
+  }
+}
+
+namespace {
+
+class SortCutsByTopoOrderLess {
+ public:
+  SortCutsByTopoOrderLess(vector<vector<Vertex::Index>::size_type>& table)
+      : table_(table) {}
+  bool operator()(const CutEdgeVertexes& a, const CutEdgeVertexes& b) {
+    return table_[a.old_dst] < table_[b.old_dst];
+  }
+ private:
+  vector<vector<Vertex::Index>::size_type>& table_;
+};
+
+}  // namespace {}
+
+void DeltaDiffGenerator::GenerateReverseTopoOrderMap(
+    vector<Vertex::Index>& op_indexes,
+    vector<vector<Vertex::Index>::size_type>* reverse_op_indexes) {
+  vector<vector<Vertex::Index>::size_type> table(op_indexes.size());
+  for (vector<Vertex::Index>::size_type i = 0, e = op_indexes.size();
+       i != e; ++i) {
+    Vertex::Index node = op_indexes[i];
+    if (table.size() < (node + 1)) {
+      table.resize(node + 1);
+    }
+    table[node] = i;
+  }
+  reverse_op_indexes->swap(table);
+}
+
+void DeltaDiffGenerator::SortCutsByTopoOrder(vector<Vertex::Index>& op_indexes,
+                                             vector<CutEdgeVertexes>* cuts) {
+  // first, make a reverse lookup table.
+  vector<vector<Vertex::Index>::size_type> table;
+  GenerateReverseTopoOrderMap(op_indexes, &table);
+  SortCutsByTopoOrderLess less(table);
+  sort(cuts->begin(), cuts->end(), less);
+}
+
+void DeltaDiffGenerator::MoveFullOpsToBack(Graph* graph,
+                                           vector<Vertex::Index>* op_indexes) {
+  vector<Vertex::Index> ret;
+  vector<Vertex::Index> full_ops;
+  ret.reserve(op_indexes->size());
+  for (vector<Vertex::Index>::size_type i = 0, e = op_indexes->size(); i != e;
+       ++i) {
+    DeltaArchiveManifest_InstallOperation_Type type =
+        (*graph)[(*op_indexes)[i]].op.type();
+    if (type == DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
+        type == DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ) {
+      full_ops.push_back((*op_indexes)[i]);
+    } else {
+      ret.push_back((*op_indexes)[i]);
+    }
+  }
+  LOG(INFO) << "Stats: " << full_ops.size() << " full ops out of "
+            << (full_ops.size() + ret.size()) << " total ops.";
+  ret.insert(ret.end(), full_ops.begin(), full_ops.end());
+  op_indexes->swap(ret);
+}
+
+namespace {
+
+template<typename T>
+bool TempBlocksExistInExtents(const T& extents) {
+  for (int i = 0, e = extents.size(); i < e; ++i) {
+    Extent extent = graph_utils::GetElement(extents, i);
+    uint64_t start = extent.start_block();
+    uint64_t num = extent.num_blocks();
+    if (start == kSparseHole)
+      continue;
+    if (start >= kTempBlockStart ||
+        (start + num) >= kTempBlockStart) {
+      LOG(ERROR) << "temp block!";
+      LOG(ERROR) << "start: " << start << ", num: " << num;
+      LOG(ERROR) << "kTempBlockStart: " << kTempBlockStart;
+      LOG(ERROR) << "returning true";
+      return true;
+    }
+    // check for wrap-around, which would be a bug:
+    CHECK(start <= (start + num));
+  }
+  return false;
+}
+
+// Convertes the cuts, which must all have the same |old_dst| member,
+// to full. It does this by converting the |old_dst| to REPLACE or
+// REPLACE_BZ, dropping all incoming edges to |old_dst|, and marking
+// all temp nodes invalid.
+bool ConvertCutsToFull(
+    Graph* graph,
+    const string& new_root,
+    int data_fd,
+    off_t* data_file_size,
+    vector<Vertex::Index>* op_indexes,
+    vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
+    const vector<CutEdgeVertexes>& cuts) {
+  CHECK(!cuts.empty());
+  set<Vertex::Index> deleted_nodes;
+  for (vector<CutEdgeVertexes>::const_iterator it = cuts.begin(),
+           e = cuts.end(); it != e; ++it) {
+    TEST_AND_RETURN_FALSE(DeltaDiffGenerator::ConvertCutToFullOp(
+        graph,
+        *it,
+        new_root,
+        data_fd,
+        data_file_size));
+    deleted_nodes.insert(it->new_vertex);
+  }
+  deleted_nodes.insert(cuts[0].old_dst);
+
+  vector<Vertex::Index> new_op_indexes;
+  new_op_indexes.reserve(op_indexes->size());
+  for (vector<Vertex::Index>::iterator it = op_indexes->begin(),
+           e = op_indexes->end(); it != e; ++it) {
+    if (utils::SetContainsKey(deleted_nodes, *it))
+      continue;
+    new_op_indexes.push_back(*it);
+  }
+  new_op_indexes.push_back(cuts[0].old_dst);
+  op_indexes->swap(new_op_indexes);
+  DeltaDiffGenerator::GenerateReverseTopoOrderMap(*op_indexes,
+                                                  reverse_op_indexes);
+  return true;
+}
+
+// Tries to assign temp blocks for a collection of cuts, all of which share
+// the same old_dst member. If temp blocks can't be found, old_dst will be
+// converted to a REPLACE or REPLACE_BZ operation. Returns true on success,
+// which can happen even if blocks are converted to full. Returns false
+// on exceptional error cases.
+bool AssignBlockForAdjoiningCuts(
+    Graph* graph,
+    const string& new_root,
+    int data_fd,
+    off_t* data_file_size,
+    vector<Vertex::Index>* op_indexes,
+    vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
+    const vector<CutEdgeVertexes>& cuts) {
+  CHECK(!cuts.empty());
+  const Vertex::Index old_dst = cuts[0].old_dst;
+  // Calculate # of blocks needed
+  uint64_t blocks_needed = 0;
+  map<const CutEdgeVertexes*, uint64_t> cuts_blocks_needed;
+  for (vector<CutEdgeVertexes>::const_iterator it = cuts.begin(),
+           e = cuts.end(); it != e; ++it) {
+    uint64_t cut_blocks_needed = 0;
+    for (vector<Extent>::const_iterator jt = it->tmp_extents.begin(),
+             je = it->tmp_extents.end(); jt != je; ++jt) {
+      cut_blocks_needed += jt->num_blocks();
+    }
+    blocks_needed += cut_blocks_needed;
+    cuts_blocks_needed[&*it] = cut_blocks_needed;
+  }
+
+  // Find enough blocks
+  ExtentRanges scratch_ranges;
+  // Each block that's supplying temp blocks and the corresponding blocks:
+  typedef vector<pair<Vertex::Index, ExtentRanges> > SupplierVector;
+  SupplierVector block_suppliers;
+  uint64_t scratch_blocks_found = 0;
+  for (vector<Vertex::Index>::size_type i = (*reverse_op_indexes)[old_dst] + 1,
+           e = op_indexes->size(); i < e; ++i) {
+    Vertex::Index test_node = (*op_indexes)[i];
+    if (!(*graph)[test_node].valid)
+      continue;
+    // See if this node has sufficient blocks
+    ExtentRanges ranges;
+    ranges.AddRepeatedExtents((*graph)[test_node].op.dst_extents());
+    ranges.SubtractExtent(ExtentForRange(
+        kTempBlockStart, kSparseHole - kTempBlockStart));
+    ranges.SubtractRepeatedExtents((*graph)[test_node].op.src_extents());
+    // For now, for simplicity, subtract out all blocks in read-before
+    // dependencies.
+    for (Vertex::EdgeMap::const_iterator edge_i =
+             (*graph)[test_node].out_edges.begin(),
+             edge_e = (*graph)[test_node].out_edges.end();
+         edge_i != edge_e; ++edge_i) {
+      ranges.SubtractExtents(edge_i->second.extents);
+    }
+    if (ranges.blocks() == 0)
+      continue;
+
+    if (ranges.blocks() + scratch_blocks_found > blocks_needed) {
+      // trim down ranges
+      vector<Extent> new_ranges = ranges.GetExtentsForBlockCount(
+          blocks_needed - scratch_blocks_found);
+      ranges = ExtentRanges();
+      ranges.AddExtents(new_ranges);
+    }
+    scratch_ranges.AddRanges(ranges);
+    block_suppliers.push_back(make_pair(test_node, ranges));
+    scratch_blocks_found += ranges.blocks();
+    if (scratch_ranges.blocks() >= blocks_needed)
+      break;
+  }
+  if (scratch_ranges.blocks() < blocks_needed) {
+    LOG(INFO) << "Unable to find sufficient scratch";
+    TEST_AND_RETURN_FALSE(ConvertCutsToFull(graph,
+                                            new_root,
+                                            data_fd,
+                                            data_file_size,
+                                            op_indexes,
+                                            reverse_op_indexes,
+                                            cuts));
+    return true;
+  }
+  // Use the scratch we found
+  TEST_AND_RETURN_FALSE(scratch_ranges.blocks() == scratch_blocks_found);
+
+  // Make all the suppliers depend on this node
+  for (SupplierVector::iterator it = block_suppliers.begin(),
+           e = block_suppliers.end(); it != e; ++it) {
+    graph_utils::AddReadBeforeDepExtents(
+        &(*graph)[it->first],
+        old_dst,
+        it->second.GetExtentsForBlockCount(it->second.blocks()));
+  }
+
+  // Replace temp blocks in each cut
+  for (vector<CutEdgeVertexes>::const_iterator it = cuts.begin(),
+           e = cuts.end(); it != e; ++it) {
+    vector<Extent> real_extents =
+        scratch_ranges.GetExtentsForBlockCount(cuts_blocks_needed[&*it]);
+    scratch_ranges.SubtractExtents(real_extents);
+
+    // Fix the old dest node w/ the real blocks
+    DeltaDiffGenerator::SubstituteBlocks(&(*graph)[old_dst],
+                                         it->tmp_extents,
+                                         real_extents);
+
+    // Fix the new node w/ the real blocks. Since the new node is just a
+    // copy operation, we can replace all the dest extents w/ the real
+    // blocks.
+    DeltaArchiveManifest_InstallOperation *op =
+        &(*graph)[it->new_vertex].op;
+    op->clear_dst_extents();
+    DeltaDiffGenerator::StoreExtents(real_extents, op->mutable_dst_extents());
+  }
+  return true;
+}
+
+}  // namespace {}
+
+// 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()));
+}
+
+bool DeltaDiffGenerator::AssignTempBlocks(
+    Graph* graph,
+    const string& new_root,
+    int data_fd,
+    off_t* data_file_size,
+    vector<Vertex::Index>* op_indexes,
+    vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
+    const vector<CutEdgeVertexes>& cuts) {
+  CHECK(!cuts.empty());
+
+  // group of cuts w/ the same old_dst:
+  vector<CutEdgeVertexes> cuts_group;
+
+  for (vector<CutEdgeVertexes>::size_type i = cuts.size() - 1, e = 0;
+       true ; --i) {
+    LOG(INFO) << "Fixing temp blocks in cut " << i
+              << ": old dst: " << cuts[i].old_dst << " new vertex: "
+              << cuts[i].new_vertex << " path: "
+              << (*graph)[cuts[i].old_dst].file_name;
+
+    if (cuts_group.empty() || (cuts_group[0].old_dst == cuts[i].old_dst)) {
+      cuts_group.push_back(cuts[i]);
+    } else {
+      CHECK(!cuts_group.empty());
+      TEST_AND_RETURN_FALSE(AssignBlockForAdjoiningCuts(graph,
+                                                        new_root,
+                                                        data_fd,
+                                                        data_file_size,
+                                                        op_indexes,
+                                                        reverse_op_indexes,
+                                                        cuts_group));
+      cuts_group.clear();
+      cuts_group.push_back(cuts[i]);
+    }
+
+    if (i == e) {
+      // break out of for() loop
+      break;
+    }
+  }
+  CHECK(!cuts_group.empty());
+  TEST_AND_RETURN_FALSE(AssignBlockForAdjoiningCuts(graph,
+                                                    new_root,
+                                                    data_fd,
+                                                    data_file_size,
+                                                    op_indexes,
+                                                    reverse_op_indexes,
+                                                    cuts_group));
+  return true;
+}
+
+bool DeltaDiffGenerator::NoTempBlocksRemain(const Graph& graph) {
+  size_t idx = 0;
+  for (Graph::const_iterator it = graph.begin(), e = graph.end(); it != e;
+       ++it, ++idx) {
+    if (!it->valid)
+      continue;
+    const DeltaArchiveManifest_InstallOperation& op = it->op;
+    if (TempBlocksExistInExtents(op.dst_extents()) ||
+        TempBlocksExistInExtents(op.src_extents())) {
+      LOG(INFO) << "bad extents in node " << idx;
+      LOG(INFO) << "so yeah";
+      return false;
+    }
+
+    // Check out-edges:
+    for (Vertex::EdgeMap::const_iterator jt = it->out_edges.begin(),
+             je = it->out_edges.end(); jt != je; ++jt) {
+      if (TempBlocksExistInExtents(jt->second.extents) ||
+          TempBlocksExistInExtents(jt->second.write_extents)) {
+        LOG(INFO) << "bad out edge in node " << idx;
+        LOG(INFO) << "so yeah";
+        return false;
+      }
+    }
+  }
+  return true;
+}
+
+bool DeltaDiffGenerator::ReorderDataBlobs(
+    DeltaArchiveManifest* manifest,
+    const std::string& data_blobs_path,
+    const std::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 = NULL;
+    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());
+    vector<char> buf(op->data_length());
+    ssize_t rc = pread(in_fd, &buf[0], 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[0], buf.size()));
+    out_file_size += buf.size();
+  }
+  return true;
+}
+
+bool DeltaDiffGenerator::AddOperationHash(
+    DeltaArchiveManifest_InstallOperation* op,
+    const vector<char>& buf) {
+  OmahaHashCalculator hasher;
+
+  TEST_AND_RETURN_FALSE(hasher.Update(&buf[0], buf.size()));
+  TEST_AND_RETURN_FALSE(hasher.Finalize());
+
+  const vector<char>& hash = hasher.raw_hash();
+  op->set_data_sha256_hash(hash.data(), hash.size());
+  return true;
+}
+
+bool DeltaDiffGenerator::ConvertCutToFullOp(Graph* graph,
+                                            const CutEdgeVertexes& cut,
+                                            const string& new_root,
+                                            int data_fd,
+                                            off_t* data_file_size) {
+  // Drop all incoming edges, keep all outgoing edges
+
+  // Keep all outgoing edges
+  if ((*graph)[cut.old_dst].op.type() !=
+      DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ &&
+      (*graph)[cut.old_dst].op.type() !=
+      DeltaArchiveManifest_InstallOperation_Type_REPLACE) {
+    Vertex::EdgeMap out_edges = (*graph)[cut.old_dst].out_edges;
+    graph_utils::DropWriteBeforeDeps(&out_edges);
+
+    TEST_AND_RETURN_FALSE(DeltaReadFile(graph,
+                                        cut.old_dst,
+                                        NULL,
+                                        kNonexistentPath,
+                                        new_root,
+                                        (*graph)[cut.old_dst].file_name,
+                                        (*graph)[cut.old_dst].chunk_offset,
+                                        (*graph)[cut.old_dst].chunk_size,
+                                        data_fd,
+                                        data_file_size));
+
+    (*graph)[cut.old_dst].out_edges = out_edges;
+
+    // Right now we don't have doubly-linked edges, so we have to scan
+    // the whole graph.
+    graph_utils::DropIncomingEdgesTo(graph, cut.old_dst);
+  }
+
+  // Delete temp node
+  (*graph)[cut.old_src].out_edges.erase(cut.new_vertex);
+  CHECK((*graph)[cut.old_dst].out_edges.find(cut.new_vertex) ==
+        (*graph)[cut.old_dst].out_edges.end());
+  (*graph)[cut.new_vertex].valid = false;
+  LOG(INFO) << "marked node invalid: " << cut.new_vertex;
+  return true;
+}
+
+bool DeltaDiffGenerator::ConvertGraphToDag(Graph* graph,
+                                           const string& new_root,
+                                           int fd,
+                                           off_t* data_file_size,
+                                           vector<Vertex::Index>* final_order,
+                                           Vertex::Index scratch_vertex) {
+  CycleBreaker cycle_breaker;
+  LOG(INFO) << "Finding cycles...";
+  set<Edge> cut_edges;
+  cycle_breaker.BreakCycles(*graph, &cut_edges);
+  LOG(INFO) << "done finding cycles";
+  CheckGraph(*graph);
+
+  // Calculate number of scratch blocks needed
+
+  LOG(INFO) << "Cutting cycles...";
+  vector<CutEdgeVertexes> cuts;
+  TEST_AND_RETURN_FALSE(CutEdges(graph, cut_edges, &cuts));
+  LOG(INFO) << "done cutting cycles";
+  LOG(INFO) << "There are " << cuts.size() << " cuts.";
+  CheckGraph(*graph);
+
+  LOG(INFO) << "Creating initial topological order...";
+  TopologicalSort(*graph, final_order);
+  LOG(INFO) << "done with initial topo order";
+  CheckGraph(*graph);
+
+  LOG(INFO) << "Moving full ops to the back";
+  MoveFullOpsToBack(graph, final_order);
+  LOG(INFO) << "done moving full ops to back";
+
+  vector<vector<Vertex::Index>::size_type> inverse_final_order;
+  GenerateReverseTopoOrderMap(*final_order, &inverse_final_order);
+
+  SortCutsByTopoOrder(*final_order, &cuts);
+
+  if (!cuts.empty())
+    TEST_AND_RETURN_FALSE(AssignTempBlocks(graph,
+                                           new_root,
+                                           fd,
+                                           data_file_size,
+                                           final_order,
+                                           &inverse_final_order,
+                                           cuts));
+  LOG(INFO) << "Making sure all temp blocks have been allocated";
+
+  // Remove the scratch node, if any
+  if (scratch_vertex != Vertex::kInvalidIndex) {
+    final_order->erase(final_order->begin() +
+                       inverse_final_order[scratch_vertex]);
+    (*graph)[scratch_vertex].valid = false;
+    GenerateReverseTopoOrderMap(*final_order, &inverse_final_order);
+  }
+
+  graph_utils::DumpGraph(*graph);
+  CHECK(NoTempBlocksRemain(*graph));
+  LOG(INFO) << "done making sure all temp blocks are allocated";
+  return true;
+}
+
+void DeltaDiffGenerator::CreateScratchNode(uint64_t start_block,
+                                           uint64_t num_blocks,
+                                           Vertex* vertex) {
+  vertex->file_name = "<scratch>";
+  vertex->op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+  vertex->op.set_data_offset(0);
+  vertex->op.set_data_length(0);
+  Extent* extent = vertex->op.add_dst_extents();
+  extent->set_start_block(start_block);
+  extent->set_num_blocks(num_blocks);
+}
+
+bool DeltaDiffGenerator::GenerateDeltaUpdateFile(
+    const string& old_root,
+    const string& old_image,
+    const string& new_root,
+    const string& new_image,
+    const string& old_kernel_part,
+    const string& new_kernel_part,
+    const string& output_path,
+    const string& private_key_path,
+    off_t chunk_size,
+    size_t rootfs_partition_size,
+    const ImageInfo* old_image_info,
+    const ImageInfo* new_image_info,
+    uint64_t* metadata_size) {
+  TEST_AND_RETURN_FALSE(chunk_size == -1 || chunk_size % kBlockSize == 0);
+  int old_image_block_count = 0, old_image_block_size = 0;
+  int new_image_block_count = 0, new_image_block_size = 0;
+  TEST_AND_RETURN_FALSE(utils::GetFilesystemSize(new_image,
+                                                 &new_image_block_count,
+                                                 &new_image_block_size));
+  if (!old_image.empty()) {
+    TEST_AND_RETURN_FALSE(utils::GetFilesystemSize(old_image,
+                                                   &old_image_block_count,
+                                                   &old_image_block_size));
+    TEST_AND_RETURN_FALSE(old_image_block_size == new_image_block_size);
+    LOG_IF(WARNING, old_image_block_count != new_image_block_count)
+        << "Old and new images have different block counts.";
+
+    // If new_image_info is present, old_image_info must be present.
+    TEST_AND_RETURN_FALSE((bool)old_image_info == (bool)new_image_info);
+  } else {
+    // old_image_info must not be present for a full update.
+    TEST_AND_RETURN_FALSE(!old_image_info);
+  }
+
+  // Sanity checks for the partition size.
+  TEST_AND_RETURN_FALSE(rootfs_partition_size % kBlockSize == 0);
+  size_t fs_size = static_cast<size_t>(new_image_block_size) *
+                   new_image_block_count;
+  LOG(INFO) << "Rootfs partition size: " << rootfs_partition_size;
+  LOG(INFO) << "Actual filesystem size: " << fs_size;
+  TEST_AND_RETURN_FALSE(rootfs_partition_size >= fs_size);
+
+  // Sanity check kernel partition arg
+  TEST_AND_RETURN_FALSE(utils::FileSize(new_kernel_part) >= 0);
+
+  vector<Block> blocks(max(old_image_block_count, new_image_block_count));
+  LOG(INFO) << "Invalid block index: " << Vertex::kInvalidIndex;
+  LOG(INFO) << "Block count: " << blocks.size();
+  for (vector<Block>::size_type i = 0; i < blocks.size(); i++) {
+    CHECK(blocks[i].reader == Vertex::kInvalidIndex);
+    CHECK(blocks[i].writer == Vertex::kInvalidIndex);
+  }
+  Graph graph;
+  CheckGraph(graph);
+
+  const string kTempFileTemplate("CrAU_temp_data.XXXXXX");
+  string temp_file_path;
+  scoped_ptr<ScopedPathUnlinker> temp_file_unlinker;
+  off_t data_file_size = 0;
+
+  LOG(INFO) << "Reading files...";
+
+  // Create empty protobuf Manifest object
+  DeltaArchiveManifest manifest;
+
+  vector<DeltaArchiveManifest_InstallOperation> kernel_ops;
+
+  vector<Vertex::Index> final_order;
+  Vertex::Index scratch_vertex = Vertex::kInvalidIndex;
+  {
+    int fd;
+    TEST_AND_RETURN_FALSE(
+        utils::MakeTempFile(kTempFileTemplate, &temp_file_path, &fd));
+    temp_file_unlinker.reset(new ScopedPathUnlinker(temp_file_path));
+    TEST_AND_RETURN_FALSE(fd >= 0);
+    ScopedFdCloser fd_closer(&fd);
+    if (!old_image.empty()) {
+      // Delta update
+
+      TEST_AND_RETURN_FALSE(DeltaReadFiles(&graph,
+                                           &blocks,
+                                           old_root,
+                                           new_root,
+                                           chunk_size,
+                                           fd,
+                                           &data_file_size));
+      LOG(INFO) << "done reading normal files";
+      CheckGraph(graph);
+
+      LOG(INFO) << "Starting metadata processing";
+      TEST_AND_RETURN_FALSE(Metadata::DeltaReadMetadata(&graph,
+                                                        &blocks,
+                                                        old_image,
+                                                        new_image,
+                                                        fd,
+                                                        &data_file_size));
+      LOG(INFO) << "Done metadata processing";
+      CheckGraph(graph);
+
+      graph.resize(graph.size() + 1);
+      TEST_AND_RETURN_FALSE(ReadUnwrittenBlocks(blocks,
+                                                fd,
+                                                &data_file_size,
+                                                new_image,
+                                                &graph.back()));
+
+      // Final scratch block (if there's space)
+      if (blocks.size() < (rootfs_partition_size / kBlockSize)) {
+        scratch_vertex = graph.size();
+        graph.resize(graph.size() + 1);
+        CreateScratchNode(blocks.size(),
+                          (rootfs_partition_size / kBlockSize) - blocks.size(),
+                          &graph.back());
+      }
+
+      // Read kernel partition
+      TEST_AND_RETURN_FALSE(DeltaCompressKernelPartition(old_kernel_part,
+                                                         new_kernel_part,
+                                                         &kernel_ops,
+                                                         fd,
+                                                         &data_file_size));
+
+      LOG(INFO) << "done reading kernel";
+      CheckGraph(graph);
+
+      LOG(INFO) << "Creating edges...";
+      CreateEdges(&graph, blocks);
+      LOG(INFO) << "Done creating edges";
+      CheckGraph(graph);
+
+      TEST_AND_RETURN_FALSE(ConvertGraphToDag(&graph,
+                                              new_root,
+                                              fd,
+                                              &data_file_size,
+                                              &final_order,
+                                              scratch_vertex));
+
+      // Set the minor version for this payload.
+      LOG(INFO) << "Adding Delta Minor Version.";
+      manifest.set_minor_version(DeltaPerformer::kSupportedMinorPayloadVersion);
+    } else {
+      // Full update
+      off_t new_image_size =
+          static_cast<off_t>(new_image_block_count) * new_image_block_size;
+      TEST_AND_RETURN_FALSE(FullUpdateGenerator::Run(&graph,
+                                                     new_kernel_part,
+                                                     new_image,
+                                                     new_image_size,
+                                                     fd,
+                                                     &data_file_size,
+                                                     kFullUpdateChunkSize,
+                                                     kBlockSize,
+                                                     &kernel_ops,
+                                                     &final_order));
+
+      // Set the minor version for this payload.
+      LOG(INFO) << "Adding Full Minor Version.";
+      manifest.set_minor_version(DeltaPerformer::kFullPayloadMinorVersion);
+    }
+  }
+
+  if (old_image_info)
+    *(manifest.mutable_old_image_info()) = *old_image_info;
+
+  if (new_image_info)
+    *(manifest.mutable_new_image_info()) = *new_image_info;
+
+  OperationNameMap op_name_map;
+  CheckGraph(graph);
+  InstallOperationsToManifest(graph,
+                              final_order,
+                              kernel_ops,
+                              &manifest,
+                              &op_name_map);
+  CheckGraph(graph);
+  manifest.set_block_size(kBlockSize);
+
+  // 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,
+      NULL));
+  ScopedPathUnlinker ordered_blobs_unlinker(ordered_blobs_path);
+  TEST_AND_RETURN_FALSE(ReorderDataBlobs(&manifest,
+                                         temp_file_path,
+                                         ordered_blobs_path));
+  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));
+    AddSignatureOp(next_blob_offset, signature_blob_length, &manifest);
+  }
+
+  TEST_AND_RETURN_FALSE(InitializePartitionInfos(old_kernel_part,
+                                                 new_kernel_part,
+                                                 old_image,
+                                                 new_image,
+                                                 &manifest));
+
+  // Serialize protobuf
+  string serialized_manifest;
+
+  CheckGraph(graph);
+  TEST_AND_RETURN_FALSE(manifest.AppendToString(&serialized_manifest));
+  CheckGraph(graph);
+
+  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 version number
+  TEST_AND_RETURN_FALSE(WriteUint64AsBigEndian(&writer, kVersionNumber));
+
+  // 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 (;;) {
+    char buf[kBlockSize];
+    ssize_t rc = read(blobs_fd, buf, sizeof(buf));
+    if (0 == rc) {
+      // EOF
+      break;
+    }
+    TEST_AND_RETURN_FALSE_ERRNO(rc > 0);
+    TEST_AND_RETURN_FALSE(writer.Write(buf, rc));
+  }
+
+  // Write signature blob.
+  if (!private_key_path.empty()) {
+    LOG(INFO) << "Signing the update...";
+    vector<char> 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[0],
+                                       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,
+                                     vector<char>* out) {
+  const string kPatchFile = "delta.patchXXXXXX";
+  string patch_file_path;
+
+  TEST_AND_RETURN_FALSE(
+      utils::MakeTempFile(kPatchFile, &patch_file_path, NULL));
+
+  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;
+  vector<char> patch_file;
+  TEST_AND_RETURN_FALSE(Subprocess::SynchronousExec(cmd, &rc, NULL));
+  TEST_AND_RETURN_FALSE(rc == 0);
+  TEST_AND_RETURN_FALSE(utils::ReadFile(patch_file_path, out));
+  unlink(patch_file_path.c_str());
+  return true;
+}
+
+// The |blocks| vector contains a reader and writer for each block on the
+// filesystem that's being in-place updated. We populate the reader/writer
+// fields of |blocks| by calling this function.
+// For each block in |operation| that is read or written, find that block
+// in |blocks| and set the reader/writer field to the vertex passed.
+// |graph| is not strictly necessary, but useful for printing out
+// error messages.
+bool DeltaDiffGenerator::AddInstallOpToBlocksVector(
+    const DeltaArchiveManifest_InstallOperation& operation,
+    const Graph& graph,
+    Vertex::Index vertex,
+    vector<Block>* blocks) {
+  // See if this is already present.
+  TEST_AND_RETURN_FALSE(operation.dst_extents_size() > 0);
+
+  enum BlockField { READER = 0, WRITER, BLOCK_FIELD_COUNT };
+  for (int field = READER; field < BLOCK_FIELD_COUNT; field++) {
+    const int extents_size =
+        (field == READER) ? operation.src_extents_size() :
+        operation.dst_extents_size();
+    const char* past_participle = (field == READER) ? "read" : "written";
+    const google::protobuf::RepeatedPtrField<Extent>& extents =
+        (field == READER) ? operation.src_extents() : operation.dst_extents();
+    Vertex::Index Block::*access_type =
+        (field == READER) ? &Block::reader : &Block::writer;
+
+    for (int i = 0; i < extents_size; i++) {
+      const Extent& extent = extents.Get(i);
+      if (extent.start_block() == kSparseHole) {
+        // Hole in sparse file. skip
+        continue;
+      }
+      for (uint64_t block = extent.start_block();
+           block < (extent.start_block() + extent.num_blocks()); block++) {
+        if ((*blocks)[block].*access_type != Vertex::kInvalidIndex) {
+          LOG(FATAL) << "Block " << block << " is already "
+                     << past_participle << " by "
+                     << (*blocks)[block].*access_type << "("
+                     << graph[(*blocks)[block].*access_type].file_name
+                     << ") and also " << vertex << "("
+                     << graph[vertex].file_name << ")";
+        }
+        (*blocks)[block].*access_type = vertex;
+      }
+    }
+  }
+  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);
+}
+
+const char* const kBsdiffPath = "bsdiff";
+
+};  // namespace chromeos_update_engine
diff --git a/payload_generator/delta_diff_generator.h b/payload_generator/delta_diff_generator.h
new file mode 100644
index 0000000..596d9c0
--- /dev/null
+++ b/payload_generator/delta_diff_generator.h
@@ -0,0 +1,276 @@
+// 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.
+
+#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_DELTA_DIFF_GENERATOR_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_DELTA_DIFF_GENERATOR_H_
+
+#include <string>
+#include <vector>
+
+#include <base/basictypes.h>
+
+#include "update_engine/payload_generator/graph_types.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,
+// the old and new images must be mounted. Call GenerateDeltaUpdateFile()
+// with both the mount-points of the images in addition to the paths of
+// the images (both old and new). A delta from old to new will be
+// generated and stored in output_path.
+
+namespace chromeos_update_engine {
+
+// This struct stores all relevant info for an edge that is cut between
+// nodes old_src -> old_dst by creating new vertex new_vertex. The new
+// relationship is:
+// old_src -(read before)-> new_vertex <-(write before)- old_dst
+// new_vertex is a MOVE operation that moves some existing blocks into
+// temp space. The temp extents are, by necessity, stored in new_vertex
+// (as dst extents) and old_dst (as src extents), but they are also broken
+// out into tmp_extents, as the nodes themselves may contain many more
+// extents.
+struct CutEdgeVertexes {
+  Vertex::Index new_vertex;
+  Vertex::Index old_src;
+  Vertex::Index old_dst;
+  std::vector<Extent> tmp_extents;
+};
+
+class DeltaDiffGenerator {
+ public:
+  // Represents a disk block on the install partition.
+  struct Block {
+    // During install, each block on the install partition will be written
+    // and some may be read (in all likelihood, many will be read).
+    // The reading and writing will be performed by InstallOperations,
+    // each of which has a corresponding vertex in a graph.
+    // A Block object tells which vertex will read or write this block
+    // at install time.
+    // Generally, there will be a vector of Block objects whose length
+    // is the number of blocks on the install partition.
+    Block() : reader(Vertex::kInvalidIndex), writer(Vertex::kInvalidIndex) {}
+    Vertex::Index reader;
+    Vertex::Index writer;
+  };
+
+  // This is the only function that external users of the class should call.
+  // old_image and new_image are paths to two image files. They should be
+  // mounted read-only at paths old_root and new_root respectively.
+  // {old,new}_kernel_part are paths to the old and new kernel partition
+  // images, respectively.
+  // private_key_path points to a private key used to sign the update.
+  // Pass empty string to not sign the update.
+  // output_path is the filename where the delta update should be written.
+  // If |chunk_size| is not -1, the delta payload is generated based on
+  // |chunk_size| chunks rather than whole files.
+  // This method computes scratch space based on |rootfs_partition_size|.
+  // Returns true on success. Also writes the size of the metadata into
+  // |metadata_size|.
+  static bool GenerateDeltaUpdateFile(const std::string& old_root,
+                                      const std::string& old_image,
+                                      const std::string& new_root,
+                                      const std::string& new_image,
+                                      const std::string& old_kernel_part,
+                                      const std::string& new_kernel_part,
+                                      const std::string& output_path,
+                                      const std::string& private_key_path,
+                                      off_t chunk_size,
+                                      size_t rootfs_partition_size,
+                                      const ImageInfo* old_image_info,
+                                      const ImageInfo* new_image_info,
+                                      uint64_t* metadata_size);
+
+  // These functions are public so that the unit tests can access them:
+
+  // Takes a graph, which is not a DAG, which represents the files just
+  // read from disk, and converts it into a DAG by breaking all cycles
+  // and finding temp space to resolve broken edges.
+  // The final order of the nodes is given in |final_order|
+  // Some files may need to be reread from disk, thus |fd| and
+  // |data_file_size| are be passed.
+  // If |scratch_vertex| is not kInvalidIndex, removes it from
+  // |final_order| before returning.
+  // Returns true on success.
+  static bool ConvertGraphToDag(Graph* graph,
+                                const std::string& new_root,
+                                int fd,
+                                off_t* data_file_size,
+                                std::vector<Vertex::Index>* final_order,
+                                Vertex::Index scratch_vertex);
+
+  // Reads old_filename (if it exists) and a new_filename and determines
+  // the smallest way to encode this file 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, or the old file doesn't exist,
+  // the smallest of REPLACE, REPLACE_BZ, or BSDIFF wins.
+  // new_filename must contain at least one byte.
+  // |new_filename| is read starting at |chunk_offset|.
+  // If |chunk_size| is not -1, only up to |chunk_size| bytes are diffed.
+  // Returns true on success.
+  static bool ReadFileToDiff(const std::string& old_filename,
+                             const std::string& new_filename,
+                             off_t chunk_offset,
+                             off_t chunk_size,
+                             bool bsdiff_allowed,
+                             std::vector<char>* out_data,
+                             DeltaArchiveManifest_InstallOperation* out_op,
+                             bool gather_extents);
+
+  // Creates a dummy REPLACE_BZ node in the given |vertex|. This can be used
+  // to provide scratch space. The node writes |num_blocks| blocks starting at
+  // |start_block|The node should be marked invalid before writing all nodes to
+  // the output file.
+  static void CreateScratchNode(uint64_t start_block,
+                                uint64_t num_blocks,
+                                Vertex* vertex);
+
+  // Modifies blocks read by 'op' so that any blocks referred to by
+  // 'remove_extents' are replaced with blocks from 'replace_extents'.
+  // 'remove_extents' and 'replace_extents' must be the same number of blocks.
+  // Blocks will be substituted in the order listed in the vectors.
+  // E.g. if 'op' reads blocks 1, 2, 3, 4, 5, 6, 7, 8, remove_extents
+  // contains blocks 6, 2, 3, 5, and replace blocks contains
+  // 12, 13, 14, 15, then op will be changed to read from:
+  // 1, 13, 14, 4, 15, 12, 7, 8
+  static void SubstituteBlocks(Vertex* vertex,
+                               const std::vector<Extent>& remove_extents,
+                               const std::vector<Extent>& replace_extents);
+
+  // Cuts 'edges' from 'graph' according to the AU algorithm. This means
+  // for each edge A->B, remove the dependency that B occur before A.
+  // Do this by creating a new operation X that copies from the blocks
+  // specified by the edge's properties to temp space T. Modify B to read
+  // from T rather than the blocks in the edge. Modify A to depend on X,
+  // but not on B. Free space is found by looking in 'blocks'.
+  // Returns true on success.
+  static bool CutEdges(Graph* graph,
+                       const std::set<Edge>& edges,
+                       std::vector<CutEdgeVertexes>* out_cuts);
+
+  // Stores all Extents in 'extents' into 'out'.
+  static void StoreExtents(const std::vector<Extent>& extents,
+                           google::protobuf::RepeatedPtrField<Extent>* out);
+
+  // Creates all the edges for the graph. Writers of a block point to
+  // readers of the same block. This is because for an edge A->B, B
+  // must complete before A executes.
+  static void CreateEdges(Graph* graph, const std::vector<Block>& blocks);
+
+  // Given a topologically sorted graph |op_indexes| and |graph|, alters
+  // |op_indexes| to move all the full operations to the end of the vector.
+  // Full operations should not be depended on, so this is safe.
+  static void MoveFullOpsToBack(Graph* graph,
+                                std::vector<Vertex::Index>* op_indexes);
+
+  // Sorts the vector |cuts| by its |cuts[].old_dest| member. Order is
+  // determined by the order of elements in op_indexes.
+  static void SortCutsByTopoOrder(std::vector<Vertex::Index>& op_indexes,
+                                  std::vector<CutEdgeVertexes>* cuts);
+
+  // Returns true iff there are no extents in the graph that refer to temp
+  // blocks. Temp blocks are in the range [kTempBlockStart, kSparseHole).
+  static bool NoTempBlocksRemain(const Graph& graph);
+
+  // 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 std::vector<char>& buf);
+
+  // Handles allocation of temp blocks to a cut edge by converting the
+  // dest node to a full op. This removes the need for temp blocks, but
+  // comes at the cost of a worse compression ratio.
+  // For example, say we have A->B->A. It would first be cut to form:
+  // A->B->N<-A, where N copies blocks to temp space. If there are no
+  // temp blocks, this function can be called to convert it to the form:
+  // A->B. Now, A is a full operation.
+  static bool ConvertCutToFullOp(Graph* graph,
+                                 const CutEdgeVertexes& cut,
+                                 const std::string& new_root,
+                                 int data_fd,
+                                 off_t* data_file_size);
+
+  // Takes |op_indexes|, which is effectively a mapping from order in
+  // which the op is performed -> graph vertex index, and produces the
+  // reverse: a mapping from graph vertex index -> op_indexes index.
+  static void GenerateReverseTopoOrderMap(
+      std::vector<Vertex::Index>& op_indexes,
+      std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes);
+
+  // Takes a |graph|, which has edges that must be cut, as listed in
+  // |cuts|.  Cuts the edges. Maintains a list in which the operations
+  // will be performed (in |op_indexes|) and the reverse (in
+  // |reverse_op_indexes|).  Cutting edges requires scratch space, and
+  // if insufficient scratch is found, the file is reread and will be
+  // send down (either as REPLACE or REPLACE_BZ).  Returns true on
+  // success.
+  static bool AssignTempBlocks(
+      Graph* graph,
+      const std::string& new_root,
+      int data_fd,
+      off_t* data_file_size,
+      std::vector<Vertex::Index>* op_indexes,
+      std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes,
+      const std::vector<CutEdgeVertexes>& cuts);
+
+  // 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);
+
+  static bool InitializePartitionInfo(bool is_kernel,
+                                      const std::string& 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,
+                          std::vector<char>* out);
+
+  // The |blocks| vector contains a reader and writer for each block on the
+  // filesystem that's being in-place updated. We populate the reader/writer
+  // fields of |blocks| by calling this function.
+  // For each block in |operation| that is read or written, find that block
+  // in |blocks| and set the reader/writer field to the vertex passed.
+  // |graph| is not strictly necessary, but useful for printing out
+  // error messages.
+  static bool AddInstallOpToBlocksVector(
+      const DeltaArchiveManifest_InstallOperation& operation,
+      const Graph& graph,
+      Vertex::Index vertex,
+      std::vector<DeltaDiffGenerator::Block>* blocks);
+
+  // 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);
+
+ private:
+ // This should never be constructed
+  DISALLOW_IMPLICIT_CONSTRUCTORS(DeltaDiffGenerator);
+};
+
+extern const char* const kBsdiffPath;
+extern const size_t kRootFSPartitionSize;
+
+};  // namespace chromeos_update_engine
+
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_DELTA_DIFF_GENERATOR_H_
diff --git a/payload_generator/delta_diff_generator_unittest.cc b/payload_generator/delta_diff_generator_unittest.cc
new file mode 100644
index 0000000..05b173c
--- /dev/null
+++ b/payload_generator/delta_diff_generator_unittest.cc
@@ -0,0 +1,1130 @@
+// 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 <fcntl.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+#include <map>
+#include <set>
+#include <sstream>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include <base/logging.h>
+#include <base/strings/string_util.h>
+#include <gtest/gtest.h>
+
+#include "update_engine/delta_performer.h"
+#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/extent_mapper.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"
+#include "update_engine/subprocess.h"
+#include "update_engine/test_utils.h"
+#include "update_engine/utils.h"
+
+using std::make_pair;
+using std::set;
+using std::string;
+using std::stringstream;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+typedef DeltaDiffGenerator::Block Block;
+
+typedef bool (*GetExtentsWithChunk)(const std::string&, off_t, off_t,
+                                    std::vector<Extent>*);
+extern GetExtentsWithChunk get_extents_with_chunk_func;
+
+namespace {
+int64_t BlocksInExtents(
+    const google::protobuf::RepeatedPtrField<Extent>& extents) {
+  int64_t ret = 0;
+  for (int i = 0; i < extents.size(); i++) {
+    ret += extents.Get(i).num_blocks();
+  }
+  return ret;
+}
+}  // namespace {}
+
+class DeltaDiffGeneratorTest : public ::testing::Test {
+ protected:
+  const string& old_path() { return old_path_; }
+  const string& new_path() { return new_path_; }
+
+  virtual void SetUp() {
+    ASSERT_TRUE(utils::MakeTempFile("DeltaDiffGeneratorTest-old_path-XXXXXX",
+                                    &old_path_, NULL));
+    ASSERT_TRUE(utils::MakeTempFile("DeltaDiffGeneratorTest-new_path-XXXXXX",
+                                    &new_path_, NULL));
+  }
+
+  virtual void TearDown() {
+    unlink(old_path().c_str());
+    unlink(new_path().c_str());
+  }
+
+ private:
+  string old_path_;
+  string new_path_;
+};
+
+TEST_F(DeltaDiffGeneratorTest, RunAsRootMoveSmallTest) {
+  EXPECT_TRUE(utils::WriteFile(old_path().c_str(),
+                               reinterpret_cast<const char*>(kRandomString),
+                               sizeof(kRandomString)));
+  EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
+                               reinterpret_cast<const char*>(kRandomString),
+                               sizeof(kRandomString)));
+  vector<char> data;
+  DeltaArchiveManifest_InstallOperation op;
+  EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
+                                                 new_path(),
+                                                 0,  // chunk_offset
+                                                 -1,  // chunk_size
+                                                 true, // bsdiff_allowed
+                                                 &data,
+                                                 &op,
+                                                 true));
+  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(sizeof(kRandomString), op.src_length());
+  EXPECT_EQ(1, op.dst_extents_size());
+  EXPECT_EQ(sizeof(kRandomString), op.dst_length());
+  EXPECT_EQ(BlocksInExtents(op.src_extents()),
+            BlocksInExtents(op.dst_extents()));
+  EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
+}
+
+std::map<string, vector<Extent>*> fake_file_extents;
+
+bool FakeGetExtents(const string& path, off_t chunk_offset, off_t chunk_size,
+                    vector<Extent>* out) {
+  if (fake_file_extents.count(path) == 1) {
+    *out = *fake_file_extents[path];
+    return true;
+  } else {
+    return false;
+  }
+}
+
+uint64_t AddExtent(uint64_t start_block, uint64_t num_blocks,
+                   vector<Extent>* extents) {
+  Extent e;
+  e.set_start_block(start_block);
+  e.set_num_blocks(num_blocks);
+  extents->push_back(e);
+  return num_blocks;
+}
+
+TEST_F(DeltaDiffGeneratorTest, RunAsRootMoveWithSameBlock) {
+  // Mock out the extent gathering function.
+  GetExtentsWithChunk orig_get_extents_with_chunk_func =
+      get_extents_with_chunk_func;
+  get_extents_with_chunk_func = FakeGetExtents;
+
+  // 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;
+  uint64_t num_extents = 0;
+  num_extents += AddExtent(20, 6, &old_extents);
+  num_extents += AddExtent(28, 2, &old_extents);
+  fake_file_extents[old_path()] = &old_extents;
+  vector<Extent> new_extents;
+  AddExtent(18, 1, &new_extents);
+  AddExtent(21, 2, &new_extents);
+  AddExtent(20, 1, &new_extents);
+  AddExtent(24, 3, &new_extents);
+  AddExtent(29, 1, &new_extents);
+  fake_file_extents[new_path()] = &new_extents;
+
+  // The size of the data should match the total number of blocks; the last
+  // block is only partly filled.
+  size_t file_len = 7 * 4096 + 3333;
+  const string random_string(reinterpret_cast<const char*>(kRandomString),
+                             sizeof(kRandomString));
+  string random_data;
+  while (random_data.size() < file_len)
+    random_data += random_string;
+  if (random_data.size() > file_len)
+    random_data.erase(file_len);
+  EXPECT_TRUE(utils::WriteFile(old_path().c_str(),
+                               random_data.c_str(), file_len));
+  EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
+                               random_data.c_str(), file_len));
+
+  vector<char> data;
+  DeltaArchiveManifest_InstallOperation op;
+  EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
+                                                 new_path(),
+                                                 0,  // chunk_offset
+                                                 -1,  // chunk_size
+                                                 true, // bsdiff_allowed
+                                                 &data,
+                                                 &op,
+                                                 true));
+
+  // Adjust the old/new extents to remove duplicates.
+  old_extents[0].set_num_blocks(1);
+  Extent e;
+  e.set_start_block(23);
+  e.set_num_blocks(1);
+  old_extents.insert(old_extents.begin() + 1, e);
+  old_extents[2].set_num_blocks(1);
+  new_extents.erase(new_extents.begin() + 1);
+  new_extents[2].set_start_block(26);
+  new_extents[2].set_num_blocks(1);
+  new_extents.erase(new_extents.begin() + 3);
+  num_extents -= 5;
+  file_len -= 4 * 4096 + 3333;
+
+  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(file_len, op.src_length());
+  EXPECT_EQ(num_extents, BlocksInExtents(op.src_extents()));
+  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(file_len, op.dst_length());
+  EXPECT_EQ(num_extents, BlocksInExtents(op.dst_extents()));
+  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;
+  }
+
+  // Clean up fake extents and restore the module's extent gathering logic.
+  fake_file_extents.clear();
+  get_extents_with_chunk_func = orig_get_extents_with_chunk_func;
+}
+
+TEST_F(DeltaDiffGeneratorTest, RunAsRootBsdiffSmallTest) {
+  EXPECT_TRUE(utils::WriteFile(old_path().c_str(),
+                               reinterpret_cast<const char*>(kRandomString),
+                               sizeof(kRandomString) - 1));
+  EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
+                               reinterpret_cast<const char*>(kRandomString),
+                               sizeof(kRandomString)));
+  vector<char> data;
+  DeltaArchiveManifest_InstallOperation op;
+  EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
+                                                 new_path(),
+                                                 0,  // chunk_offset
+                                                 -1,  // chunk_size
+                                                 true, // bsdiff_allowed
+                                                 &data,
+                                                 &op,
+                                                 true));
+  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(sizeof(kRandomString) - 1, op.src_length());
+  EXPECT_EQ(1, op.dst_extents_size());
+  EXPECT_EQ(sizeof(kRandomString), op.dst_length());
+  EXPECT_EQ(BlocksInExtents(op.src_extents()),
+            BlocksInExtents(op.dst_extents()));
+  EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
+}
+
+TEST_F(DeltaDiffGeneratorTest, RunAsRootBsdiffNotAllowedTest) {
+  EXPECT_TRUE(utils::WriteFile(old_path().c_str(),
+                               reinterpret_cast<const char*>(kRandomString),
+                               sizeof(kRandomString) - 1));
+  EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
+                               reinterpret_cast<const char*>(kRandomString),
+                               sizeof(kRandomString)));
+  vector<char> data;
+  DeltaArchiveManifest_InstallOperation op;
+
+  EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
+                                                 new_path(),
+                                                 0,  // chunk_offset
+                                                 -1,  // chunk_size
+                                                 false, // bsdiff_allowed
+                                                 &data,
+                                                 &op,
+                                                 true));
+  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, RunAsRootBsdiffNotAllowedMoveTest) {
+  EXPECT_TRUE(utils::WriteFile(old_path().c_str(),
+                               reinterpret_cast<const char*>(kRandomString),
+                               sizeof(kRandomString)));
+  EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
+                               reinterpret_cast<const char*>(kRandomString),
+                               sizeof(kRandomString)));
+  vector<char> data;
+  DeltaArchiveManifest_InstallOperation op;
+
+  EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
+                                                 new_path(),
+                                                 0,  // chunk_offset
+                                                 -1,  // chunk_size
+                                                 false, // bsdiff_allowed
+                                                 &data,
+                                                 &op,
+                                                 true));
+  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, RunAsRootReplaceSmallTest) {
+  vector<char> new_data;
+  for (int i = 0; i < 2; i++) {
+    new_data.insert(new_data.end(),
+                    kRandomString,
+                    kRandomString + sizeof(kRandomString));
+    EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
+                                 &new_data[0],
+                                 new_data.size()));
+    vector<char> data;
+    DeltaArchiveManifest_InstallOperation op;
+    EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
+                                                   new_path(),
+                                                   0,  // chunk_offset
+                                                   -1,  // chunk_size
+                                                   true, // bsdiff_allowed
+                                                   &data,
+                                                   &op,
+                                                   true));
+    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(new_data.size(), op.dst_length());
+    EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
+  }
+}
+
+TEST_F(DeltaDiffGeneratorTest, RunAsRootBsdiffNoGatherExtentsSmallTest) {
+  EXPECT_TRUE(utils::WriteFile(old_path().c_str(),
+                               reinterpret_cast<const char*>(kRandomString),
+                               sizeof(kRandomString) - 1));
+  EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
+                               reinterpret_cast<const char*>(kRandomString),
+                               sizeof(kRandomString)));
+  vector<char> data;
+  DeltaArchiveManifest_InstallOperation op;
+  EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
+                                                 new_path(),
+                                                 0,  // chunk_offset
+                                                 -1,  // chunk_size
+                                                 true, // bsdiff_allowed
+                                                 &data,
+                                                 &op,
+                                                 false));
+  EXPECT_FALSE(data.empty());
+
+  EXPECT_TRUE(op.has_type());
+  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_BSDIFF, op.type());
+  EXPECT_FALSE(op.has_data_offset());
+  EXPECT_FALSE(op.has_data_length());
+  EXPECT_EQ(1, op.src_extents_size());
+  EXPECT_EQ(0, op.src_extents().Get(0).start_block());
+  EXPECT_EQ(1, op.src_extents().Get(0).num_blocks());
+  EXPECT_EQ(sizeof(kRandomString) - 1, op.src_length());
+  EXPECT_EQ(1, op.dst_extents_size());
+  EXPECT_EQ(0, op.dst_extents().Get(0).start_block());
+  EXPECT_EQ(1, op.dst_extents().Get(0).num_blocks());
+  EXPECT_EQ(sizeof(kRandomString), op.dst_length());
+}
+
+namespace {
+void AppendExtent(vector<Extent>* vect, uint64_t start, uint64_t length) {
+  vect->resize(vect->size() + 1);
+  vect->back().set_start_block(start);
+  vect->back().set_num_blocks(length);
+}
+void OpAppendExtent(DeltaArchiveManifest_InstallOperation* op,
+                    uint64_t start,
+                    uint64_t length) {
+  Extent* extent = op->add_src_extents();
+  extent->set_start_block(start);
+  extent->set_num_blocks(length);
+}
+}
+
+TEST_F(DeltaDiffGeneratorTest, SubstituteBlocksTest) {
+  vector<Extent> remove_blocks;
+  AppendExtent(&remove_blocks, 3, 3);
+  AppendExtent(&remove_blocks, 7, 1);
+  vector<Extent> replace_blocks;
+  AppendExtent(&replace_blocks, 10, 2);
+  AppendExtent(&replace_blocks, 13, 2);
+  Vertex vertex;
+  DeltaArchiveManifest_InstallOperation& op = vertex.op;
+  OpAppendExtent(&op, 4, 3);
+  OpAppendExtent(&op, kSparseHole, 4);  // Sparse hole in file
+  OpAppendExtent(&op, 3, 1);
+  OpAppendExtent(&op, 7, 3);
+
+  DeltaDiffGenerator::SubstituteBlocks(&vertex, remove_blocks, replace_blocks);
+
+  EXPECT_EQ(7, op.src_extents_size());
+  EXPECT_EQ(11, op.src_extents(0).start_block());
+  EXPECT_EQ(1, op.src_extents(0).num_blocks());
+  EXPECT_EQ(13, op.src_extents(1).start_block());
+  EXPECT_EQ(1, op.src_extents(1).num_blocks());
+  EXPECT_EQ(6, op.src_extents(2).start_block());
+  EXPECT_EQ(1, op.src_extents(2).num_blocks());
+  EXPECT_EQ(kSparseHole, op.src_extents(3).start_block());
+  EXPECT_EQ(4, op.src_extents(3).num_blocks());
+  EXPECT_EQ(10, op.src_extents(4).start_block());
+  EXPECT_EQ(1, op.src_extents(4).num_blocks());
+  EXPECT_EQ(14, op.src_extents(5).start_block());
+  EXPECT_EQ(1, op.src_extents(5).num_blocks());
+  EXPECT_EQ(8, op.src_extents(6).start_block());
+  EXPECT_EQ(2, op.src_extents(6).num_blocks());
+}
+
+TEST_F(DeltaDiffGeneratorTest, CutEdgesTest) {
+  Graph graph;
+  vector<Block> blocks(9);
+
+  // Create nodes in graph
+  {
+    graph.resize(graph.size() + 1);
+    graph.back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+    // Reads from blocks 3, 5, 7
+    vector<Extent> extents;
+    graph_utils::AppendBlockToExtents(&extents, 3);
+    graph_utils::AppendBlockToExtents(&extents, 5);
+    graph_utils::AppendBlockToExtents(&extents, 7);
+    DeltaDiffGenerator::StoreExtents(extents,
+                                     graph.back().op.mutable_src_extents());
+    blocks[3].reader = graph.size() - 1;
+    blocks[5].reader = graph.size() - 1;
+    blocks[7].reader = graph.size() - 1;
+
+    // Writes to blocks 1, 2, 4
+    extents.clear();
+    graph_utils::AppendBlockToExtents(&extents, 1);
+    graph_utils::AppendBlockToExtents(&extents, 2);
+    graph_utils::AppendBlockToExtents(&extents, 4);
+    DeltaDiffGenerator::StoreExtents(extents,
+                                     graph.back().op.mutable_dst_extents());
+    blocks[1].writer = graph.size() - 1;
+    blocks[2].writer = graph.size() - 1;
+    blocks[4].writer = graph.size() - 1;
+  }
+  {
+    graph.resize(graph.size() + 1);
+    graph.back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+    // Reads from blocks 1, 2, 4
+    vector<Extent> extents;
+    graph_utils::AppendBlockToExtents(&extents, 1);
+    graph_utils::AppendBlockToExtents(&extents, 2);
+    graph_utils::AppendBlockToExtents(&extents, 4);
+    DeltaDiffGenerator::StoreExtents(extents,
+                                     graph.back().op.mutable_src_extents());
+    blocks[1].reader = graph.size() - 1;
+    blocks[2].reader = graph.size() - 1;
+    blocks[4].reader = graph.size() - 1;
+
+    // Writes to blocks 3, 5, 6
+    extents.clear();
+    graph_utils::AppendBlockToExtents(&extents, 3);
+    graph_utils::AppendBlockToExtents(&extents, 5);
+    graph_utils::AppendBlockToExtents(&extents, 6);
+    DeltaDiffGenerator::StoreExtents(extents,
+                                     graph.back().op.mutable_dst_extents());
+    blocks[3].writer = graph.size() - 1;
+    blocks[5].writer = graph.size() - 1;
+    blocks[6].writer = graph.size() - 1;
+  }
+
+  // Create edges
+  DeltaDiffGenerator::CreateEdges(&graph, blocks);
+
+  // Find cycles
+  CycleBreaker cycle_breaker;
+  set<Edge> cut_edges;
+  cycle_breaker.BreakCycles(graph, &cut_edges);
+
+  EXPECT_EQ(1, cut_edges.size());
+  EXPECT_TRUE(cut_edges.end() != cut_edges.find(make_pair<Vertex::Index>(1,
+                                                                         0)));
+
+  vector<CutEdgeVertexes> cuts;
+  EXPECT_TRUE(DeltaDiffGenerator::CutEdges(&graph, cut_edges, &cuts));
+
+  EXPECT_EQ(3, graph.size());
+
+  // Check new node in graph:
+  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE,
+            graph.back().op.type());
+  EXPECT_EQ(2, graph.back().op.src_extents_size());
+  EXPECT_EQ(1, graph.back().op.dst_extents_size());
+  EXPECT_EQ(kTempBlockStart, graph.back().op.dst_extents(0).start_block());
+  EXPECT_EQ(2, graph.back().op.dst_extents(0).num_blocks());
+  EXPECT_TRUE(graph.back().out_edges.empty());
+
+  // Check that old node reads from new blocks
+  EXPECT_EQ(2, graph[0].op.src_extents_size());
+  EXPECT_EQ(kTempBlockStart, graph[0].op.src_extents(0).start_block());
+  EXPECT_EQ(2, graph[0].op.src_extents(0).num_blocks());
+  EXPECT_EQ(7, graph[0].op.src_extents(1).start_block());
+  EXPECT_EQ(1, graph[0].op.src_extents(1).num_blocks());
+
+  // And that the old dst extents haven't changed
+  EXPECT_EQ(2, graph[0].op.dst_extents_size());
+  EXPECT_EQ(1, graph[0].op.dst_extents(0).start_block());
+  EXPECT_EQ(2, graph[0].op.dst_extents(0).num_blocks());
+  EXPECT_EQ(4, graph[0].op.dst_extents(1).start_block());
+  EXPECT_EQ(1, graph[0].op.dst_extents(1).num_blocks());
+
+  // Ensure it only depends on the next node and the new temp node
+  EXPECT_EQ(2, graph[0].out_edges.size());
+  EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(1));
+  EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(graph.size() -
+                                                                  1));
+
+  // Check second node has unchanged extents
+  EXPECT_EQ(2, graph[1].op.src_extents_size());
+  EXPECT_EQ(1, graph[1].op.src_extents(0).start_block());
+  EXPECT_EQ(2, graph[1].op.src_extents(0).num_blocks());
+  EXPECT_EQ(4, graph[1].op.src_extents(1).start_block());
+  EXPECT_EQ(1, graph[1].op.src_extents(1).num_blocks());
+
+  EXPECT_EQ(2, graph[1].op.dst_extents_size());
+  EXPECT_EQ(3, graph[1].op.dst_extents(0).start_block());
+  EXPECT_EQ(1, graph[1].op.dst_extents(0).num_blocks());
+  EXPECT_EQ(5, graph[1].op.dst_extents(1).start_block());
+  EXPECT_EQ(2, graph[1].op.dst_extents(1).num_blocks());
+
+  // Ensure it only depends on the next node
+  EXPECT_EQ(1, graph[1].out_edges.size());
+  EXPECT_TRUE(graph[1].out_edges.end() != graph[1].out_edges.find(2));
+}
+
+TEST_F(DeltaDiffGeneratorTest, ReorderBlobsTest) {
+  string orig_blobs;
+  EXPECT_TRUE(
+      utils::MakeTempFile("ReorderBlobsTest.orig.XXXXXX", &orig_blobs, NULL));
+
+  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, NULL));
+
+  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());
+
+  unlink(orig_blobs.c_str());
+  unlink(new_blobs.c_str());
+}
+
+TEST_F(DeltaDiffGeneratorTest, MoveFullOpsToBackTest) {
+  Graph graph(4);
+  graph[0].file_name = "A";
+  graph[0].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+  graph[1].file_name = "B";
+  graph[1].op.set_type(DeltaArchiveManifest_InstallOperation_Type_BSDIFF);
+  graph[2].file_name = "C";
+  graph[2].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+  graph[3].file_name = "D";
+  graph[3].op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+
+  vector<Vertex::Index> vect(graph.size());
+
+  for (vector<Vertex::Index>::size_type i = 0; i < vect.size(); ++i) {
+    vect[i] = i;
+  }
+  DeltaDiffGenerator::MoveFullOpsToBack(&graph, &vect);
+  EXPECT_EQ(vect.size(), graph.size());
+  EXPECT_EQ(graph[vect[0]].file_name, "B");
+  EXPECT_EQ(graph[vect[1]].file_name, "D");
+  EXPECT_EQ(graph[vect[2]].file_name, "A");
+  EXPECT_EQ(graph[vect[3]].file_name, "C");
+}
+
+namespace {
+
+#define OP_BSDIFF DeltaArchiveManifest_InstallOperation_Type_BSDIFF
+#define OP_MOVE DeltaArchiveManifest_InstallOperation_Type_MOVE
+#define OP_REPLACE DeltaArchiveManifest_InstallOperation_Type_REPLACE
+#define OP_REPLACE_BZ DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ
+
+void GenVertex(Vertex* out,
+               const vector<Extent>& src_extents,
+               const vector<Extent>& dst_extents,
+               const string& path,
+               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());
+}
+
+vector<Extent> VectOfExt(uint64_t start_block, uint64_t num_blocks) {
+  return vector<Extent>(1, ExtentForRange(start_block, num_blocks));
+}
+
+EdgeProperties EdgeWithReadDep(const vector<Extent>& extents) {
+  EdgeProperties ret;
+  ret.extents = extents;
+  return ret;
+}
+
+EdgeProperties EdgeWithWriteDep(const vector<Extent>& extents) {
+  EdgeProperties ret;
+  ret.write_extents = extents;
+  return ret;
+}
+
+template<typename T>
+void DumpVect(const vector<T>& vect) {
+  std::stringstream ss(stringstream::out);
+  for (typename vector<T>::const_iterator it = vect.begin(), e = vect.end();
+       it != e; ++it) {
+    ss << *it << ", ";
+  }
+  LOG(INFO) << "{" << ss.str() << "}";
+}
+
+}  // namespace {}
+
+TEST_F(DeltaDiffGeneratorTest, RunAsRootAssignTempBlocksTest) {
+  Graph graph(9);
+  const vector<Extent> empt;  // empty
+  const string kFilename = "/foo";
+
+  // Some scratch space:
+  GenVertex(&graph[0], empt, VectOfExt(200, 1), "", OP_REPLACE);
+  GenVertex(&graph[1], empt, VectOfExt(210, 10), "", OP_REPLACE);
+  GenVertex(&graph[2], empt, VectOfExt(220, 1), "", OP_REPLACE);
+
+  // A cycle that requires 10 blocks to break:
+  GenVertex(&graph[3], VectOfExt(10, 11), VectOfExt(0, 9), "", OP_BSDIFF);
+  graph[3].out_edges[4] = EdgeWithReadDep(VectOfExt(0, 9));
+  GenVertex(&graph[4], VectOfExt(0, 9), VectOfExt(10, 11), "", OP_BSDIFF);
+  graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11));
+
+  // A cycle that requires 9 blocks to break:
+  GenVertex(&graph[5], VectOfExt(40, 11), VectOfExt(30, 10), "", OP_BSDIFF);
+  graph[5].out_edges[6] = EdgeWithReadDep(VectOfExt(30, 10));
+  GenVertex(&graph[6], VectOfExt(30, 10), VectOfExt(40, 11), "", OP_BSDIFF);
+  graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11));
+
+  // A cycle that requires 40 blocks to break (which is too many):
+  GenVertex(&graph[7],
+            VectOfExt(120, 50),
+            VectOfExt(60, 40),
+            "",
+            OP_BSDIFF);
+  graph[7].out_edges[8] = EdgeWithReadDep(VectOfExt(60, 40));
+  GenVertex(&graph[8],
+            VectOfExt(60, 40),
+            VectOfExt(120, 50),
+            kFilename,
+            OP_BSDIFF);
+  graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
+
+  graph_utils::DumpGraph(graph);
+
+  vector<Vertex::Index> final_order;
+
+
+  // Prepare the filesystem with the minimum required for this to work
+  string temp_dir;
+  EXPECT_TRUE(utils::MakeTempDirectory("AssignTempBlocksTest.XXXXXX",
+                                       &temp_dir));
+  ScopedDirRemover temp_dir_remover(temp_dir);
+
+  const size_t kBlockSize = 4096;
+  vector<char> temp_data(kBlockSize * 50);
+  FillWithData(&temp_data);
+  EXPECT_TRUE(WriteFileVector(temp_dir + kFilename, temp_data));
+  ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
+
+  int fd;
+  EXPECT_TRUE(utils::MakeTempFile("AssignTempBlocksTestData.XXXXXX",
+                                  NULL,
+                                  &fd));
+  ScopedFdCloser fd_closer(&fd);
+  off_t data_file_size = 0;
+
+
+  EXPECT_TRUE(DeltaDiffGenerator::ConvertGraphToDag(&graph,
+                                                    temp_dir,
+                                                    fd,
+                                                    &data_file_size,
+                                                    &final_order,
+                                                    Vertex::kInvalidIndex));
+
+
+  Graph expected_graph(12);
+  GenVertex(&expected_graph[0], empt, VectOfExt(200, 1), "", OP_REPLACE);
+  GenVertex(&expected_graph[1], empt, VectOfExt(210, 10), "", OP_REPLACE);
+  GenVertex(&expected_graph[2], empt, VectOfExt(220, 1), "", OP_REPLACE);
+  GenVertex(&expected_graph[3],
+            VectOfExt(10, 11),
+            VectOfExt(0, 9),
+            "",
+            OP_BSDIFF);
+  expected_graph[3].out_edges[9] = EdgeWithReadDep(VectOfExt(0, 9));
+  GenVertex(&expected_graph[4],
+            VectOfExt(60, 9),
+            VectOfExt(10, 11),
+            "",
+            OP_BSDIFF);
+  expected_graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11));
+  expected_graph[4].out_edges[9] = EdgeWithWriteDep(VectOfExt(60, 9));
+  GenVertex(&expected_graph[5],
+            VectOfExt(40, 11),
+            VectOfExt(30, 10),
+            "",
+            OP_BSDIFF);
+  expected_graph[5].out_edges[10] = EdgeWithReadDep(VectOfExt(30, 10));
+
+  GenVertex(&expected_graph[6],
+            VectOfExt(60, 10),
+            VectOfExt(40, 11),
+            "",
+            OP_BSDIFF);
+  expected_graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11));
+  expected_graph[6].out_edges[10] = EdgeWithWriteDep(VectOfExt(60, 10));
+
+  GenVertex(&expected_graph[7],
+            VectOfExt(120, 50),
+            VectOfExt(60, 40),
+            "",
+            OP_BSDIFF);
+  expected_graph[7].out_edges[6] = EdgeWithReadDep(VectOfExt(60, 10));
+
+  GenVertex(&expected_graph[8], empt, VectOfExt(0, 50), "/foo", OP_REPLACE_BZ);
+  expected_graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
+
+  GenVertex(&expected_graph[9],
+            VectOfExt(0, 9),
+            VectOfExt(60, 9),
+            "",
+            OP_MOVE);
+
+  GenVertex(&expected_graph[10],
+            VectOfExt(30, 10),
+            VectOfExt(60, 10),
+            "",
+            OP_MOVE);
+  expected_graph[10].out_edges[4] = EdgeWithReadDep(VectOfExt(60, 9));
+
+  EXPECT_EQ(12, graph.size());
+  EXPECT_FALSE(graph.back().valid);
+  for (Graph::size_type i = 0; i < graph.size() - 1; i++) {
+    EXPECT_TRUE(graph[i].out_edges == expected_graph[i].out_edges);
+    if (i == 8) {
+      // special case
+    } else {
+      // EXPECT_TRUE(graph[i] == expected_graph[i]) << "i = " << i;
+    }
+  }
+}
+
+// Test that sparse holes are not used as scratch. More specifically, test that
+// if all full operations write to sparse holes and there's no extra scratch
+// space, delta operations that need scratch are converted to full. See
+// crbug.com/238440.
+TEST_F(DeltaDiffGeneratorTest, RunAsRootNoSparseAsTempTest) {
+  Graph graph(3);
+  const vector<Extent> kEmpty;
+  const string kFilename = "/foo";
+
+  // Make sure this sparse hole is not used as scratch.
+  GenVertex(&graph[0], kEmpty, VectOfExt(kSparseHole, 1), "", OP_REPLACE);
+
+  // Create a single-block cycle.
+  GenVertex(&graph[1], VectOfExt(0, 1), VectOfExt(1, 1), "", OP_BSDIFF);
+  graph[1].out_edges[2] = EdgeWithReadDep(VectOfExt(1, 1));
+  GenVertex(&graph[2], VectOfExt(1, 1), VectOfExt(0, 1), kFilename, OP_BSDIFF);
+  graph[2].out_edges[1] = EdgeWithReadDep(VectOfExt(0, 1));
+
+  graph_utils::DumpGraph(graph);
+
+  vector<Vertex::Index> final_order;
+
+  // Prepare the filesystem with the minimum required for this to work.
+  string temp_dir;
+  EXPECT_TRUE(utils::MakeTempDirectory("NoSparseAsTempTest.XXXXXX",
+                                       &temp_dir));
+  ScopedDirRemover temp_dir_remover(temp_dir);
+
+  const size_t kBlockSize = 4096;
+  vector<char> temp_data(kBlockSize);
+  FillWithData(&temp_data);
+  EXPECT_TRUE(WriteFileVector(temp_dir + kFilename, temp_data));
+  ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
+
+  int fd = -1;
+  EXPECT_TRUE(utils::MakeTempFile("NoSparseAsTempTestData.XXXXXX",
+                                  NULL,
+                                  &fd));
+  ScopedFdCloser fd_closer(&fd);
+  off_t data_file_size = 0;
+
+  EXPECT_TRUE(DeltaDiffGenerator::ConvertGraphToDag(&graph,
+                                                    temp_dir,
+                                                    fd,
+                                                    &data_file_size,
+                                                    &final_order,
+                                                    Vertex::kInvalidIndex));
+
+  ASSERT_EQ(4, graph.size());
+
+  // The second BSDIFF operation must have been converted to a full operation
+  // (due to insufficient scratch space).
+  EXPECT_TRUE(graph[2].op.type() == OP_REPLACE ||
+              graph[2].op.type() == OP_REPLACE_BZ);
+
+  // The temporary node created for breaking the cycle must have been marked as
+  // invalid.
+  EXPECT_FALSE(graph[3].valid);
+}
+
+// Test that sparse holes are not used as scratch. More specifically, test that
+// if scratch space comes only from full operations writing to real blocks as
+// well as sparse holes, only the real blocks are utilized. See
+// crbug.com/238440.
+TEST_F(DeltaDiffGeneratorTest, NoSparseAsTempTest) {
+  Graph graph;
+  vector<Block> blocks(4);
+
+  // Create nodes in |graph|.
+  {
+    graph.resize(graph.size() + 1);
+    graph.back().op.set_type(
+        DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+
+    // Write to a sparse hole -- basically a no-op to ensure sparse holes are
+    // not used as scratch.
+    vector<Extent> extents;
+    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+    DeltaDiffGenerator::StoreExtents(extents,
+                                     graph.back().op.mutable_dst_extents());
+  }
+  {
+    graph.resize(graph.size() + 1);
+    graph.back().op.set_type(OP_REPLACE);
+
+    // Scratch space: write to block 0 with sparse holes around.
+    vector<Extent> extents;
+    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+    graph_utils::AppendBlockToExtents(&extents, 0);
+    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+    DeltaDiffGenerator::StoreExtents(extents,
+                                     graph.back().op.mutable_dst_extents());
+    blocks[0].writer = graph.size() - 1;
+  }
+  {
+    graph.resize(graph.size() + 1);
+    graph.back().op.set_type(OP_REPLACE);
+
+    // Write to a sparse hole.
+    vector<Extent> extents;
+    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+    DeltaDiffGenerator::StoreExtents(extents,
+                                     graph.back().op.mutable_dst_extents());
+  }
+  // Create a two-node cycle between (2, sparse, sparse) and (1, sparse, 3).
+  {
+    graph.resize(graph.size() + 1);
+    graph.back().op.set_type(OP_MOVE);
+    // Read from (2, sparse, sparse).
+    vector<Extent> extents;
+    graph_utils::AppendBlockToExtents(&extents, 2);
+    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+    DeltaDiffGenerator::StoreExtents(extents,
+                                     graph.back().op.mutable_src_extents());
+    blocks[2].reader = graph.size() - 1;
+
+    // Write to (1, sparse, 3).
+    extents.clear();
+    graph_utils::AppendBlockToExtents(&extents, 1);
+    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+    graph_utils::AppendBlockToExtents(&extents, 3);
+    DeltaDiffGenerator::StoreExtents(extents,
+                                     graph.back().op.mutable_dst_extents());
+    blocks[1].writer = graph.size() - 1;
+    blocks[3].writer = graph.size() - 1;
+  }
+  {
+    graph.resize(graph.size() + 1);
+    graph.back().op.set_type(OP_MOVE);
+    // Read from (1, sparse, 3).
+    vector<Extent> extents;
+    graph_utils::AppendBlockToExtents(&extents, 1);
+    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+    graph_utils::AppendBlockToExtents(&extents, 3);
+    DeltaDiffGenerator::StoreExtents(extents,
+                                     graph.back().op.mutable_src_extents());
+    blocks[1].reader = graph.size() - 1;
+    blocks[3].reader = graph.size() - 1;
+
+    // Write to (2, sparse, sparse).
+    extents.clear();
+    graph_utils::AppendBlockToExtents(&extents, 2);
+    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+    graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+    DeltaDiffGenerator::StoreExtents(extents,
+                                     graph.back().op.mutable_dst_extents());
+    blocks[2].writer = graph.size() - 1;
+  }
+
+  graph_utils::DumpGraph(graph);
+
+  // Create edges
+  DeltaDiffGenerator::CreateEdges(&graph, blocks);
+
+  graph_utils::DumpGraph(graph);
+
+  vector<Vertex::Index> final_order;
+  off_t data_file_size = 0;
+  EXPECT_TRUE(DeltaDiffGenerator::ConvertGraphToDag(&graph,
+                                                    "/non/existent/dir",
+                                                    -1,
+                                                    &data_file_size,
+                                                    &final_order,
+                                                    Vertex::kInvalidIndex));
+
+  // Check for a single temporary node writing to scratch.
+  ASSERT_EQ(6, graph.size());
+  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE,
+            graph[5].op.type());
+  EXPECT_EQ(1, graph[5].op.src_extents_size());
+  ASSERT_EQ(1, graph[5].op.dst_extents_size());
+  EXPECT_EQ(0, graph[5].op.dst_extents(0).start_block());
+  EXPECT_EQ(1, graph[5].op.dst_extents(0).num_blocks());
+
+  // Make sure the cycle nodes still read from and write to sparse holes.
+  for (int i = 3; i < 5; i++) {
+    ASSERT_GE(graph[i].op.src_extents_size(), 2);
+    EXPECT_EQ(kSparseHole, graph[i].op.src_extents(1).start_block());
+    ASSERT_GE(graph[i].op.dst_extents_size(), 2);
+    EXPECT_EQ(kSparseHole, graph[i].op.dst_extents(1).start_block());
+  }
+}
+
+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(kSparseHole, 2);
+  *(op.add_src_extents()) = ExtentForRange(kSparseHole, 1);
+  *(op.add_dst_extents()) = ExtentForRange(kSparseHole, 3);
+  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, RunAsRootAssignTempBlocksReuseTest) {
+  // AssignTempBlocks(Graph* graph,
+  // const string& new_root,
+  // int data_fd,
+  // off_t* data_file_size,
+  // vector<Vertex::Index>* op_indexes,
+  // vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
+  // const vector<CutEdgeVertexes>& cuts
+  Graph graph(9);
+
+  const vector<Extent> empt;
+  uint64_t tmp = kTempBlockStart;
+  const string kFilename = "/foo";
+
+  vector<CutEdgeVertexes> cuts;
+  cuts.resize(3);
+
+  // Simple broken loop:
+  GenVertex(&graph[0], VectOfExt(0, 1), VectOfExt(1, 1), "", OP_MOVE);
+  GenVertex(&graph[1], VectOfExt(tmp, 1), VectOfExt(0, 1), "", OP_MOVE);
+  GenVertex(&graph[2], VectOfExt(1, 1), VectOfExt(tmp, 1), "", OP_MOVE);
+  // Corresponding edges:
+  graph[0].out_edges[2] = EdgeWithReadDep(VectOfExt(1, 1));
+  graph[1].out_edges[2] = EdgeWithWriteDep(VectOfExt(tmp, 1));
+  graph[1].out_edges[0] = EdgeWithReadDep(VectOfExt(0, 1));
+  // Store the cut:
+  cuts[0].old_dst = 1;
+  cuts[0].old_src = 0;
+  cuts[0].new_vertex = 2;
+  cuts[0].tmp_extents = VectOfExt(tmp, 1);
+  tmp++;
+
+  // Slightly more complex pair of loops:
+  GenVertex(&graph[3], VectOfExt(4, 2), VectOfExt(2, 2), "", OP_MOVE);
+  GenVertex(&graph[4], VectOfExt(6, 1), VectOfExt(7, 1), "", OP_MOVE);
+  GenVertex(&graph[5], VectOfExt(tmp, 3), VectOfExt(4, 3), kFilename, OP_MOVE);
+  GenVertex(&graph[6], VectOfExt(2, 2), VectOfExt(tmp, 2), "", OP_MOVE);
+  GenVertex(&graph[7], VectOfExt(7, 1), VectOfExt(tmp + 2, 1), "", OP_MOVE);
+  // Corresponding edges:
+  graph[3].out_edges[6] = EdgeWithReadDep(VectOfExt(2, 2));
+  graph[4].out_edges[7] = EdgeWithReadDep(VectOfExt(7, 1));
+  graph[5].out_edges[6] = EdgeWithWriteDep(VectOfExt(tmp, 2));
+  graph[5].out_edges[7] = EdgeWithWriteDep(VectOfExt(tmp + 2, 1));
+  graph[5].out_edges[3] = EdgeWithReadDep(VectOfExt(4, 2));
+  graph[5].out_edges[4] = EdgeWithReadDep(VectOfExt(6, 1));
+  // Store the cuts:
+  cuts[1].old_dst = 5;
+  cuts[1].old_src = 3;
+  cuts[1].new_vertex = 6;
+  cuts[1].tmp_extents = VectOfExt(tmp, 2);
+  cuts[2].old_dst = 5;
+  cuts[2].old_src = 4;
+  cuts[2].new_vertex = 7;
+  cuts[2].tmp_extents = VectOfExt(tmp + 2, 1);
+
+  // Supplier of temp block:
+  GenVertex(&graph[8], empt, VectOfExt(8, 1), "", OP_REPLACE);
+
+  // Specify the final order:
+  vector<Vertex::Index> op_indexes;
+  op_indexes.push_back(2);
+  op_indexes.push_back(0);
+  op_indexes.push_back(1);
+  op_indexes.push_back(6);
+  op_indexes.push_back(3);
+  op_indexes.push_back(7);
+  op_indexes.push_back(4);
+  op_indexes.push_back(5);
+  op_indexes.push_back(8);
+
+  vector<vector<Vertex::Index>::size_type> reverse_op_indexes;
+  DeltaDiffGenerator::GenerateReverseTopoOrderMap(op_indexes,
+                                                  &reverse_op_indexes);
+
+  // Prepare the filesystem with the minimum required for this to work
+  string temp_dir;
+  EXPECT_TRUE(utils::MakeTempDirectory("AssignTempBlocksReuseTest.XXXXXX",
+                                       &temp_dir));
+  ScopedDirRemover temp_dir_remover(temp_dir);
+
+  const size_t kBlockSize = 4096;
+  vector<char> temp_data(kBlockSize * 3);
+  FillWithData(&temp_data);
+  EXPECT_TRUE(WriteFileVector(temp_dir + kFilename, temp_data));
+  ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
+
+  int fd;
+  EXPECT_TRUE(utils::MakeTempFile("AssignTempBlocksReuseTest.XXXXXX",
+                                  NULL,
+                                  &fd));
+  ScopedFdCloser fd_closer(&fd);
+  off_t data_file_size = 0;
+
+  EXPECT_TRUE(DeltaDiffGenerator::AssignTempBlocks(&graph,
+                                                   temp_dir,
+                                                   fd,
+                                                   &data_file_size,
+                                                   &op_indexes,
+                                                   &reverse_op_indexes,
+                                                   cuts));
+  EXPECT_FALSE(graph[6].valid);
+  EXPECT_FALSE(graph[7].valid);
+  EXPECT_EQ(1, graph[1].op.src_extents_size());
+  EXPECT_EQ(2, graph[1].op.src_extents(0).start_block());
+  EXPECT_EQ(1, graph[1].op.src_extents(0).num_blocks());
+  EXPECT_EQ(OP_REPLACE_BZ, graph[5].op.type());
+}
+
+TEST_F(DeltaDiffGeneratorTest, CreateScratchNodeTest) {
+  Vertex vertex;
+  DeltaDiffGenerator::CreateScratchNode(12, 34, &vertex);
+  EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ,
+            vertex.op.type());
+  EXPECT_EQ(0, vertex.op.data_offset());
+  EXPECT_EQ(0, vertex.op.data_length());
+  EXPECT_EQ(1, vertex.op.dst_extents_size());
+  EXPECT_EQ(12, vertex.op.dst_extents(0).start_block());
+  EXPECT_EQ(34, vertex.op.dst_extents(0).num_blocks());
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/extent_mapper.cc b/payload_generator/extent_mapper.cc
new file mode 100644
index 0000000..9e66619
--- /dev/null
+++ b/payload_generator/extent_mapper.cc
@@ -0,0 +1,93 @@
+// 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_mapper.h"
+
+#include <assert.h>
+#include <errno.h>
+#include <fcntl.h>
+#include <linux/fs.h>
+#include <stdio.h>
+#include <string.h>
+#include <sys/ioctl.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+
+#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/graph_types.h"
+#include "update_engine/payload_generator/graph_utils.h"
+#include "update_engine/utils.h"
+
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace extent_mapper {
+
+namespace {
+const int kBlockSize = 4096;
+}
+
+bool ExtentsForFileChunkFibmap(const std::string& path,
+                               off_t chunk_offset,
+                               off_t chunk_size,
+                               std::vector<Extent>* out) {
+  CHECK(out);
+  CHECK_EQ(0, chunk_offset % kBlockSize);
+  CHECK(chunk_size == -1 || chunk_size >= 0);
+  struct stat stbuf;
+  int rc = stat(path.c_str(), &stbuf);
+  TEST_AND_RETURN_FALSE_ERRNO(rc == 0);
+  TEST_AND_RETURN_FALSE(S_ISREG(stbuf.st_mode));
+
+  int fd = open(path.c_str(), O_RDONLY, 0);
+  TEST_AND_RETURN_FALSE_ERRNO(fd >= 0);
+  ScopedFdCloser fd_closer(&fd);
+
+  // Get file size in blocks
+  rc = fstat(fd, &stbuf);
+  if (rc < 0) {
+    perror("fstat");
+    return false;
+  }
+  CHECK_LE(chunk_offset, stbuf.st_size);
+  off_t size = stbuf.st_size - chunk_offset;
+  if (chunk_size != -1) {
+    size = std::min(size, chunk_size);
+  }
+  const int block_count = (size + kBlockSize - 1) / kBlockSize;
+  const int start_block = chunk_offset / kBlockSize;
+  Extent current;
+  current.set_start_block(0);
+  current.set_num_blocks(0);
+
+  for (int i = start_block; i < start_block + block_count; i++) {
+    unsigned int block32 = i;
+    rc = ioctl(fd, FIBMAP, &block32);
+    TEST_AND_RETURN_FALSE_ERRNO(rc == 0);
+
+    const uint64_t block = (block32 == 0 ? kSparseHole : block32);
+
+    graph_utils::AppendBlockToExtents(out, block);
+  }
+  return true;
+}
+
+bool ExtentsForFileFibmap(const std::string& path, std::vector<Extent>* out) {
+  return ExtentsForFileChunkFibmap(path, 0, -1, out);
+}
+
+bool GetFilesystemBlockSize(const std::string& path, uint32_t* out_blocksize) {
+  int fd = open(path.c_str(), O_RDONLY, 0);
+  TEST_AND_RETURN_FALSE_ERRNO(fd >= 0);
+  ScopedFdCloser fd_closer(&fd);
+  int rc = ioctl(fd, FIGETBSZ, out_blocksize);
+  TEST_AND_RETURN_FALSE_ERRNO(rc != -1);
+  return true;
+}
+
+}  // namespace extent_mapper
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/extent_mapper.h b/payload_generator/extent_mapper.h
new file mode 100644
index 0000000..bc46e47
--- /dev/null
+++ b/payload_generator/extent_mapper.h
@@ -0,0 +1,46 @@
+// 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 CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_MAPPER_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_MAPPER_H_
+
+#include <string>
+#include <vector>
+
+#include <base/basictypes.h>
+
+#include "update_engine/update_metadata.pb.h"
+
+namespace chromeos_update_engine {
+
+namespace extent_mapper {
+
+// Uses the FIBMAP ioctl to get all blocks used by a file and return them
+// as extents. Blocks are relative to the start of the filesystem. If
+// there is a sparse "hole" in the file, the blocks for that will be
+// represented by an extent whose start block is kSpareseHole.
+// The resulting extents are stored in 'out'. Keep in mind that while
+// the blocksize of a filesystem is often 4096 bytes, that is not always
+// the case, so one should consult GetFilesystemBlockSize(), too.
+// Returns true on success.
+//
+// ExtentsForFileChunkFibmap gets the blocks starting from
+// |chunk_offset|. |chunk_offset| must be a multiple of the block size. If
+// |chunk_size| is not -1, only blocks covering up to |chunk_size| bytes are
+// returned.
+bool ExtentsForFileFibmap(const std::string& path, std::vector<Extent>* out);
+bool ExtentsForFileChunkFibmap(const std::string& path,
+                               off_t chunk_offset,
+                               off_t chunk_size,
+                               std::vector<Extent>* out);
+
+// Puts the blocksize of the filesystem, as used by the FIBMAP ioctl, into
+// out_blocksize by using the FIGETBSZ ioctl. Returns true on success.
+bool GetFilesystemBlockSize(const std::string& path, uint32_t* out_blocksize);
+
+}  // namespace extent_mapper
+
+}  // namespace chromeos_update_engine
+
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_MAPPER_H_
diff --git a/payload_generator/extent_mapper_unittest.cc b/payload_generator/extent_mapper_unittest.cc
new file mode 100644
index 0000000..3b23246
--- /dev/null
+++ b/payload_generator/extent_mapper_unittest.cc
@@ -0,0 +1,111 @@
+// 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_mapper.h"
+
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+#include <set>
+#include <string>
+#include <vector>
+
+#include <base/basictypes.h>
+#include <gtest/gtest.h>
+
+#include "update_engine/payload_constants.h"
+#include "update_engine/utils.h"
+
+using std::set;
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+class ExtentMapperTest : public ::testing::Test {};
+
+TEST(ExtentMapperTest, RunAsRootSimpleTest) {
+  // It's hard to have a concrete test for extent mapping without including
+  // a specific filesystem image.
+  // In lieu of this, we do a weak test: make sure the extents of the unittest
+  // executable are consistent and they match with the size of the file.
+  const string kFilename = "/proc/self/exe";
+
+  uint32_t block_size = 0;
+  EXPECT_TRUE(extent_mapper::GetFilesystemBlockSize(kFilename, &block_size));
+  EXPECT_GT(block_size, 0);
+
+  vector<Extent> extents;
+
+  ASSERT_TRUE(extent_mapper::ExtentsForFileFibmap(kFilename, &extents));
+
+  EXPECT_FALSE(extents.empty());
+  set<uint64_t> blocks;
+
+  for (vector<Extent>::const_iterator it = extents.begin();
+       it != extents.end(); ++it) {
+    for (uint64_t block = it->start_block();
+         block < it->start_block() + it->num_blocks();
+         block++) {
+      EXPECT_FALSE(utils::SetContainsKey(blocks, block));
+      blocks.insert(block);
+    }
+  }
+
+  struct stat stbuf;
+  EXPECT_EQ(0, stat(kFilename.c_str(), &stbuf));
+  EXPECT_EQ(blocks.size(), (stbuf.st_size + block_size - 1)/block_size);
+
+  // Map a 2-block chunk at offset |block_size|.
+  vector<Extent> chunk_extents;
+  ASSERT_TRUE(
+      extent_mapper::ExtentsForFileChunkFibmap(kFilename,
+                                               block_size,
+                                               block_size + 1,
+                                               &chunk_extents));
+  EXPECT_FALSE(chunk_extents.empty());
+  int chunk_blocks = 0;
+  for (vector<Extent>::const_iterator it = chunk_extents.begin();
+       it != chunk_extents.end(); ++it) {
+    chunk_blocks += it->num_blocks();
+  }
+  EXPECT_EQ(2, chunk_blocks);
+}
+
+TEST(ExtentMapperTest, RunAsRootSparseFileTest) {
+  // Create sparse file with one real block, then two sparse ones, then a real
+  // block at the end.
+  const char tmp_name_template[] =
+      "/tmp/ExtentMapperTest.RunAsRootSparseFileTest.XXXXXX";
+  char buf[sizeof(tmp_name_template)];
+  strncpy(buf, tmp_name_template, sizeof(buf));
+  COMPILE_ASSERT(sizeof(buf) > 8, buf_size_incorrect);
+  ASSERT_EQ('\0', buf[sizeof(buf) - 1]);
+
+  int fd = mkstemp(buf);
+  ASSERT_GE(fd, 0);
+
+  uint32_t block_size = 0;
+  EXPECT_TRUE(extent_mapper::GetFilesystemBlockSize(buf, &block_size));
+  EXPECT_GT(block_size, 0);
+
+  EXPECT_EQ(1, pwrite(fd, "x", 1, 0));
+  EXPECT_EQ(1, pwrite(fd, "x", 1, 3 * block_size));
+  close(fd);
+
+  vector<Extent> extents;
+  EXPECT_TRUE(extent_mapper::ExtentsForFileFibmap(buf, &extents));
+  unlink(buf);
+  EXPECT_EQ(3, extents.size());
+  EXPECT_EQ(1, extents[0].num_blocks());
+  EXPECT_EQ(2, extents[1].num_blocks());
+  EXPECT_EQ(1, extents[2].num_blocks());
+  EXPECT_NE(kSparseHole, extents[0].start_block());
+  EXPECT_EQ(kSparseHole, extents[1].start_block());
+  EXPECT_NE(kSparseHole, extents[2].start_block());
+  EXPECT_NE(extents[2].start_block(), extents[0].start_block());
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/filesystem_iterator.cc b/payload_generator/filesystem_iterator.cc
new file mode 100644
index 0000000..b7455fa
--- /dev/null
+++ b/payload_generator/filesystem_iterator.cc
@@ -0,0 +1,151 @@
+// Copyright (c) 2009 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/filesystem_iterator.h"
+
+#include <dirent.h>
+#include <errno.h>
+#include <sys/types.h>
+
+#include <set>
+#include <string>
+#include <vector>
+
+#include <base/logging.h>
+
+#include "update_engine/utils.h"
+
+using std::set;
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+// We use a macro here for two reasons:
+// 1. We want to be able to return from the caller's function.
+// 2. We can use the #macro_arg ism to get a string of the calling statement,
+//    which we can log.
+
+#define RETURN_ERROR_IF_FALSE(_statement)                               \
+  do {                                                                  \
+    bool _result = (_statement);                                        \
+    if (!_result) {                                                     \
+      string _message = utils::ErrnoNumberAsString(errno);              \
+      LOG(INFO) << #_statement << " failed: " << _message << ". Aborting"; \
+      is_end_ = true;                                                   \
+      is_err_ = true;                                                   \
+      return;                                                           \
+    }                                                                   \
+  } while (0)
+
+FilesystemIterator::FilesystemIterator(
+    const std::string& path,
+    const std::set<std::string>& excl_prefixes)
+    : excl_prefixes_(excl_prefixes),
+      is_end_(false),
+      is_err_(false) {
+  root_path_ = utils::NormalizePath(path, true);
+  RETURN_ERROR_IF_FALSE(lstat(root_path_.c_str(), &stbuf_) == 0);
+  root_dev_ = stbuf_.st_dev;
+}
+
+FilesystemIterator::~FilesystemIterator() {
+  for (vector<DIR*>::iterator it = dirs_.begin(); it != dirs_.end(); ++it) {
+    LOG_IF(ERROR, closedir(*it) != 0) << "closedir failed";
+  }
+}
+
+// Returns full path for current file
+std::string FilesystemIterator::GetFullPath() const {
+  return root_path_ + GetPartialPath();
+}
+
+std::string FilesystemIterator::GetPartialPath() const {
+  std::string ret;
+  for (vector<string>::const_iterator it = names_.begin();
+       it != names_.end(); ++it) {
+    ret += "/";
+    ret += *it;
+  }
+  return ret;
+}
+
+// Increments to the next file
+void FilesystemIterator::Increment() {
+  // If we're currently on a dir, descend into children, but only if
+  // we're on the same device as the root device
+
+  bool entering_dir = false;  // true if we're entering into a new dir
+  if (S_ISDIR(stbuf_.st_mode) && (stbuf_.st_dev == root_dev_)) {
+    DIR* dir = opendir(GetFullPath().c_str());
+    if ((!dir) && ((errno == ENOTDIR) || (errno == ENOENT))) {
+      // opendir failed b/c either it's not a dir or it doesn't exist.
+      // that's fine. let's just skip over this.
+      LOG(ERROR) << "Can't descend into " << GetFullPath();
+    } else {
+      RETURN_ERROR_IF_FALSE(dir);
+      entering_dir = true;
+      dirs_.push_back(dir);
+    }
+  }
+
+  if (!entering_dir && names_.empty()) {
+    // root disappeared while we tried to descend into it
+    is_end_ = true;
+    return;
+  }
+
+  if (!entering_dir)
+    names_.pop_back();
+
+  IncrementInternal();
+  for (set<string>::const_iterator it = excl_prefixes_.begin();
+       it != excl_prefixes_.end(); ++it) {
+    if (utils::StringHasPrefix(GetPartialPath(), *it)) {
+      Increment();
+      break;
+    }
+  }
+  return;
+}
+
+// Assumes that we need to find the next child of dirs_.back(), or if
+// there are none more, go up the chain
+void FilesystemIterator::IncrementInternal() {
+  CHECK_EQ(dirs_.size(), names_.size() + 1);
+  for (;;) {
+    struct dirent dir_entry;
+    struct dirent* dir_entry_pointer;
+    int r;
+    RETURN_ERROR_IF_FALSE(
+        (r = readdir_r(dirs_.back(), &dir_entry, &dir_entry_pointer)) == 0);
+    if (dir_entry_pointer) {
+      // Found an entry
+      names_.push_back(dir_entry_pointer->d_name);
+      // Validate
+      RETURN_ERROR_IF_FALSE(lstat(GetFullPath().c_str(), &stbuf_) == 0);
+      if (strcmp(dir_entry_pointer->d_name, ".") &&
+          strcmp(dir_entry_pointer->d_name, "..")) {
+        // Done
+        return;
+      }
+      // Child didn't work out. Try again
+      names_.pop_back();
+    } else {
+      // No more children in this dir. Pop it and try again
+      RETURN_ERROR_IF_FALSE(closedir(dirs_.back()) == 0);
+      dirs_.pop_back();
+      if (dirs_.empty()) {
+        CHECK(names_.empty());
+        // Done with the entire iteration
+        is_end_ = true;
+        return;
+      }
+      CHECK(!names_.empty());
+      names_.pop_back();
+    }
+  }
+}
+
+}  //   namespace chromeos_update_engine
diff --git a/payload_generator/filesystem_iterator.h b/payload_generator/filesystem_iterator.h
new file mode 100644
index 0000000..859965d
--- /dev/null
+++ b/payload_generator/filesystem_iterator.h
@@ -0,0 +1,127 @@
+// Copyright (c) 2009 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 CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_FILESYSTEM_ITERATOR_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_FILESYSTEM_ITERATOR_H_
+
+// This class is used to walk a filesystem. It will iterate over every file
+// on the same device as the file passed in the ctor. Directories will be
+// visited before their children. Children will be visited in no particular
+// order.
+
+// The iterator is a forward iterator. It's not random access nor can it be
+// decremented.
+
+// Note: If the iterator comes across a mount point where another filesystem
+// is mounted, that mount point will be present, but none of its children
+// will be. Technically the mount point is on the other filesystem (and
+// the Stat() call will verify that), but we return it anyway since:
+// 1. Such a folder must exist in the first filesystem if it got used
+//    as a mount point.
+// 2. You probably want to copy if it you're using the iterator to do a
+//    filesystem copy
+// 3. If you don't want that, you can just check Stat().st_dev and skip
+//    foreign filesystems manually.
+
+#include <dirent.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+#include <set>
+#include <string>
+#include <vector>
+
+namespace chromeos_update_engine {
+
+class FilesystemIterator {
+ public:
+  FilesystemIterator(const std::string& path,
+                     const std::set<std::string>& excl_prefixes);
+
+  ~FilesystemIterator();
+
+  // Returns stat struct for the current file.
+  struct stat GetStat() const {
+    return stbuf_;
+  }
+
+  // Returns full path for current file.
+  std::string GetFullPath() const;
+
+  // Returns the path that's part of the iterator. For example, if
+  // the object were constructed by passing in "/foo/bar" and Path()
+  // returns "/foo/bar/baz/bat.txt", IterPath would return
+  // "/baz/bat.txt". When this object is on root (ie, the very first
+  // path), IterPath will return "", otherwise the first character of
+  // IterPath will be "/".
+  std::string GetPartialPath() const;
+
+  // Returns name for current file.
+  std::string GetBasename() const {
+    return names_.back();
+  }
+
+  // Increments to the next file.
+  void Increment();
+
+  // If we're at the end. If at the end, do not call Stat(), Path(), etc.,
+  // since this iterator currently isn't pointing to any file at all.
+  bool IsEnd() const {
+    return is_end_;
+  }
+
+  // Returns true if the iterator is in an error state.
+  bool IsErr() const {
+    return is_err_;
+  }
+ private:
+  // Helper for Increment.
+  void IncrementInternal();
+
+  // Returns true if path exists and it's a directory.
+  bool DirectoryExists(const std::string& path);
+
+  // In general (i.e., not midway through a call to Increment()), there is a
+  // relationship between dirs_ and names_: dirs[i] == names_[i - 1].
+  // For example, say we are asked to iterate "/usr/local" and we're currently
+  // at /usr/local/share/dict/words. dirs_ contains DIR* variables for the
+  // dirs at: {"/usr/local", ".../share", ".../dict"} and names_ contains:
+  // {"share", "dict", "words"}. root_path_ contains "/usr/local".
+  // root_dev_ would be the dev for root_path_
+  // (and /usr/local/share/dict/words). stbuf_ would be the stbuf for
+  // /usr/local/share/dict/words.
+
+  // All opened directories. If this is empty, we're currently on the root,
+  // but not descended into the root.
+  // This will always contain the current directory and all it's ancestors
+  // in root-to-leaf order. For more details, see comment above.
+  std::vector<DIR*> dirs_;
+
+  // The list of all filenames for the current path that we've descended into.
+  std::vector<std::string> names_;
+
+  // The device of the root path we've been asked to iterate.
+  dev_t root_dev_;
+
+  // The root path we've been asked to iteratate.
+  std::string root_path_;
+
+  // Exclude items w/ this prefix.
+  std::set<std::string> excl_prefixes_;
+
+  // The struct stat of the current file we're at.
+  struct stat stbuf_;
+
+  // Generally false; set to true when we reach the end of files to iterate
+  // or error occurs.
+  bool is_end_;
+
+  // Generally false; set to true if an error occurrs.
+  bool is_err_;
+};
+
+}  // namespace chromeos_update_engine
+
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_FILESYSTEM_ITERATOR_H_
diff --git a/payload_generator/filesystem_iterator_unittest.cc b/payload_generator/filesystem_iterator_unittest.cc
new file mode 100644
index 0000000..67ac177
--- /dev/null
+++ b/payload_generator/filesystem_iterator_unittest.cc
@@ -0,0 +1,146 @@
+// 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/filesystem_iterator.h"
+
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+#include <set>
+#include <string>
+#include <vector>
+
+#include <base/strings/string_util.h>
+#include <base/strings/stringprintf.h>
+#include <gtest/gtest.h>
+
+#include "update_engine/test_utils.h"
+#include "update_engine/utils.h"
+
+using std::set;
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+class FilesystemIteratorTest : public ::testing::Test {
+ protected:
+  virtual void SetUp() {
+    ASSERT_TRUE(utils::MakeTempDirectory("FilesystemIteratorTest-XXXXXX",
+                                         &test_dir_));
+    LOG(INFO) << "SetUp() mkdir " << test_dir_;
+  }
+
+  virtual void TearDown() {
+    LOG(INFO) << "TearDown() rmdir " << test_dir_;
+    EXPECT_EQ(0, System(base::StringPrintf("rm -rf %s", TestDir())));
+  }
+
+  const char* TestDir() {
+    return test_dir_.c_str();
+  }
+
+ private:
+  string test_dir_;
+};
+
+TEST_F(FilesystemIteratorTest, RunAsRootSuccessTest) {
+  ASSERT_EQ(0, getuid());
+
+  // Create uniquely named main/sub images.
+  string main_image;
+  ASSERT_TRUE(utils::MakeTempFile("FilesystemIteratorTest.image1-XXXXXX",
+                                  &main_image, NULL));
+  ScopedPathUnlinker main_image_unlinker(main_image);
+
+  string sub_image;
+  ASSERT_TRUE(utils::MakeTempFile("FilesystemIteratorTest.image2-XXXXXX",
+                                  &sub_image, NULL));
+  ScopedPathUnlinker sub_image_unlinker(sub_image);
+
+  // Create uniqely named main/sub mount points.
+  string main_image_mount_point;
+  ASSERT_TRUE(utils::MakeTempDirectory(
+          "FilesystemIteratorTest.mount-XXXXXX",
+          &main_image_mount_point));
+  ScopedPathUnlinker main_image_mount_point_unlinker(main_image_mount_point);
+  const string sub_image_mount_point = main_image_mount_point + "/some_dir/mnt";
+
+  vector<string> expected_paths_vector;
+  CreateExtImageAtPath(main_image, &expected_paths_vector);
+  CreateExtImageAtPath(sub_image, NULL);
+  ASSERT_EQ(0, System(string("mount -o loop ") + main_image + " " +
+                      main_image_mount_point));
+  ASSERT_EQ(0, System(string("mount -o loop ") + sub_image + " " +
+                      sub_image_mount_point));
+  for (vector<string>::iterator it = expected_paths_vector.begin();
+       it != expected_paths_vector.end(); ++it)
+    *it = main_image_mount_point + *it;
+  set<string> expected_paths(expected_paths_vector.begin(),
+                             expected_paths_vector.end());
+  VerifyAllPaths(main_image_mount_point, expected_paths);
+
+  EXPECT_TRUE(utils::UnmountFilesystem(sub_image_mount_point));
+  EXPECT_TRUE(utils::UnmountFilesystem(main_image_mount_point));
+}
+
+TEST_F(FilesystemIteratorTest, NegativeTest) {
+  {
+    FilesystemIterator iter("/non/existent/path", set<string>());
+    EXPECT_TRUE(iter.IsEnd());
+    EXPECT_TRUE(iter.IsErr());
+  }
+
+  {
+    FilesystemIterator iter(TestDir(), set<string>());
+    EXPECT_FALSE(iter.IsEnd());
+    EXPECT_FALSE(iter.IsErr());
+    // Here I'm deleting the exact directory that iterator is point at,
+    // then incrementing (which normally would descend into that directory).
+    EXPECT_EQ(0, rmdir(TestDir()));
+    iter.Increment();
+    EXPECT_TRUE(iter.IsEnd());
+    EXPECT_FALSE(iter.IsErr());
+  }
+}
+
+TEST_F(FilesystemIteratorTest, DeleteWhileTraverseTest) {
+  const string dir_name = TestDir();
+  ASSERT_EQ(0, chmod(dir_name.c_str(), 0755));
+  const string sub_dir_name(dir_name + "/a");
+  ASSERT_EQ(0, mkdir(sub_dir_name.c_str(), 0755));
+  const string sub_sub_dir_name(sub_dir_name + "/b");
+  ASSERT_EQ(0, mkdir(sub_sub_dir_name.c_str(), 0755));
+  ASSERT_EQ(0, mkdir((dir_name + "/b").c_str(), 0755));
+  ASSERT_EQ(0, mkdir((dir_name + "/c").c_str(), 0755));
+
+  string expected_paths_arr[] = {
+    "",
+    "/a",
+    "/b",
+    "/c"
+  };
+  set<string> expected_paths(expected_paths_arr,
+                             expected_paths_arr +
+                             arraysize(expected_paths_arr));
+
+  FilesystemIterator iter(dir_name, set<string>());
+  while (!iter.IsEnd()) {
+    string path = iter.GetPartialPath();
+    EXPECT_TRUE(expected_paths.find(path) != expected_paths.end());
+    if (expected_paths.find(path) != expected_paths.end()) {
+      expected_paths.erase(path);
+    }
+    if (path == "/a") {
+      EXPECT_EQ(0, rmdir(sub_sub_dir_name.c_str()));
+      EXPECT_EQ(0, rmdir(sub_dir_name.c_str()));
+    }
+    iter.Increment();
+  }
+  EXPECT_FALSE(iter.IsErr());
+  EXPECT_TRUE(expected_paths.empty());
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/full_update_generator.cc b/payload_generator/full_update_generator.cc
new file mode 100644
index 0000000..3a17594
--- /dev/null
+++ b/payload_generator/full_update_generator.cc
@@ -0,0 +1,203 @@
+// 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/full_update_generator.h"
+
+#include <fcntl.h>
+#include <inttypes.h>
+
+#include <tr1/memory>
+
+#include <base/strings/string_util.h>
+#include <base/strings/stringprintf.h>
+
+#include "update_engine/bzip.h"
+#include "update_engine/utils.h"
+
+using std::deque;
+using std::max;
+using std::min;
+using std::string;
+using std::tr1::shared_ptr;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+
+// This class encapsulates a full update chunk processing thread. The processor
+// reads a chunk of data from the input file descriptor and compresses it. The
+// processor needs to be started through Start() then waited on through Wait().
+class ChunkProcessor {
+ public:
+  // Read a chunk of |size| bytes from |fd| starting at offset |offset|.
+  ChunkProcessor(int fd, off_t offset, size_t size)
+      : thread_(NULL),
+        fd_(fd),
+        offset_(offset),
+        buffer_in_(size) {}
+  ~ChunkProcessor() { Wait(); }
+
+  off_t offset() const { return offset_; }
+  const vector<char>& buffer_in() const { return buffer_in_; }
+  const vector<char>& buffer_compressed() const { return buffer_compressed_; }
+
+  // Starts the processor. Returns true on success, false on failure.
+  bool Start();
+
+  // Waits for the processor to complete. Returns true on success, false on
+  // failure.
+  bool Wait();
+
+  bool ShouldCompress() const {
+    return buffer_compressed_.size() < buffer_in_.size();
+  }
+
+ private:
+  // Reads the input data into |buffer_in_| and compresses it into
+  // |buffer_compressed_|. Returns true on success, false otherwise.
+  bool ReadAndCompress();
+  static gpointer ReadAndCompressThread(gpointer data);
+
+  GThread* thread_;
+  int fd_;
+  off_t offset_;
+  vector<char> buffer_in_;
+  vector<char> buffer_compressed_;
+
+  DISALLOW_COPY_AND_ASSIGN(ChunkProcessor);
+};
+
+bool ChunkProcessor::Start() {
+  // g_thread_create is deprecated since glib 2.32. Use
+  // g_thread_new instead.
+  thread_ = g_thread_try_new("chunk_proc", ReadAndCompressThread, this, NULL);
+  TEST_AND_RETURN_FALSE(thread_ != NULL);
+  return true;
+}
+
+bool ChunkProcessor::Wait() {
+  if (!thread_) {
+    return false;
+  }
+  gpointer result = g_thread_join(thread_);
+  thread_ = NULL;
+  TEST_AND_RETURN_FALSE(result == this);
+  return true;
+}
+
+gpointer ChunkProcessor::ReadAndCompressThread(gpointer data) {
+  return
+      reinterpret_cast<ChunkProcessor*>(data)->ReadAndCompress() ? data : NULL;
+}
+
+bool ChunkProcessor::ReadAndCompress() {
+  ssize_t bytes_read = -1;
+  TEST_AND_RETURN_FALSE(utils::PReadAll(fd_,
+                                        buffer_in_.data(),
+                                        buffer_in_.size(),
+                                        offset_,
+                                        &bytes_read));
+  TEST_AND_RETURN_FALSE(bytes_read == static_cast<ssize_t>(buffer_in_.size()));
+  TEST_AND_RETURN_FALSE(BzipCompress(buffer_in_, &buffer_compressed_));
+  return true;
+}
+
+}  // namespace
+
+bool FullUpdateGenerator::Run(
+    Graph* graph,
+    const std::string& new_kernel_part,
+    const std::string& new_image,
+    off_t image_size,
+    int fd,
+    off_t* data_file_size,
+    off_t chunk_size,
+    off_t block_size,
+    vector<DeltaArchiveManifest_InstallOperation>* kernel_ops,
+    std::vector<Vertex::Index>* final_order) {
+  TEST_AND_RETURN_FALSE(chunk_size > 0);
+  TEST_AND_RETURN_FALSE((chunk_size % block_size) == 0);
+
+  size_t max_threads = max(sysconf(_SC_NPROCESSORS_ONLN), 4L);
+  LOG(INFO) << "Max threads: " << max_threads;
+
+  // Get the sizes early in the function, so we can fail fast if the user
+  // passed us bad paths.
+  TEST_AND_RETURN_FALSE(image_size >= 0 &&
+                        image_size <= utils::FileSize(new_image));
+  const off_t kernel_size = utils::FileSize(new_kernel_part);
+  TEST_AND_RETURN_FALSE(kernel_size >= 0);
+
+  off_t part_sizes[] = { image_size, kernel_size };
+  string paths[] = { new_image, new_kernel_part };
+
+  for (int partition = 0; partition < 2; ++partition) {
+    const string& path = paths[partition];
+    LOG(INFO) << "compressing " << path;
+    int in_fd = open(path.c_str(), O_RDONLY, 0);
+    TEST_AND_RETURN_FALSE(in_fd >= 0);
+    ScopedFdCloser in_fd_closer(&in_fd);
+    deque<shared_ptr<ChunkProcessor> > threads;
+    int last_progress_update = INT_MIN;
+    off_t bytes_left = part_sizes[partition], counter = 0, offset = 0;
+    while (bytes_left > 0 || !threads.empty()) {
+      // Check and start new chunk processors if possible.
+      while (threads.size() < max_threads && bytes_left > 0) {
+        shared_ptr<ChunkProcessor> processor(
+            new ChunkProcessor(in_fd, offset, min(bytes_left, chunk_size)));
+        threads.push_back(processor);
+        TEST_AND_RETURN_FALSE(processor->Start());
+        bytes_left -= chunk_size;
+        offset += chunk_size;
+      }
+
+      // Need to wait for a chunk processor to complete and process its ouput
+      // before spawning new processors.
+      shared_ptr<ChunkProcessor> processor = threads.front();
+      threads.pop_front();
+      TEST_AND_RETURN_FALSE(processor->Wait());
+
+      DeltaArchiveManifest_InstallOperation* op = NULL;
+      if (partition == 0) {
+        graph->resize(graph->size() + 1);
+        graph->back().file_name =
+            base::StringPrintf("<rootfs-operation-%" PRIi64 ">", counter++);
+        op = &graph->back().op;
+        final_order->push_back(graph->size() - 1);
+      } else {
+        kernel_ops->resize(kernel_ops->size() + 1);
+        op = &kernel_ops->back();
+      }
+
+      const bool compress = processor->ShouldCompress();
+      const vector<char>& use_buf =
+          compress ? processor->buffer_compressed() : processor->buffer_in();
+      op->set_type(compress ?
+                   DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ :
+                   DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+      op->set_data_offset(*data_file_size);
+      TEST_AND_RETURN_FALSE(utils::WriteAll(fd, &use_buf[0], use_buf.size()));
+      *data_file_size += use_buf.size();
+      op->set_data_length(use_buf.size());
+      Extent* dst_extent = op->add_dst_extents();
+      dst_extent->set_start_block(processor->offset() / block_size);
+      dst_extent->set_num_blocks(chunk_size / block_size);
+
+      int progress = static_cast<int>(
+          (processor->offset() + processor->buffer_in().size()) * 100.0 /
+          part_sizes[partition]);
+      if (last_progress_update < progress &&
+          (last_progress_update + 10 <= progress || progress == 100)) {
+        LOG(INFO) << progress << "% complete (output size: "
+                  << *data_file_size << ")";
+        last_progress_update = progress;
+      }
+    }
+  }
+
+  return true;
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/full_update_generator.h b/payload_generator/full_update_generator.h
new file mode 100644
index 0000000..4ca1aa4
--- /dev/null
+++ b/payload_generator/full_update_generator.h
@@ -0,0 +1,41 @@
+// 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 CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_FULL_UPDATE_GENERATOR_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_FULL_UPDATE_GENERATOR_H_
+
+#include <glib.h>
+
+#include "update_engine/payload_generator/graph_types.h"
+
+namespace chromeos_update_engine {
+
+class FullUpdateGenerator {
+ public:
+  // Given a new rootfs and kernel (|new_image|, |new_kernel_part|), reads them
+  // sequentially, creating a full update of chunk_size chunks. Populates
+  // |graph|, |kernel_ops|, and |final_order|, with data about the update
+  // operations, and writes relevant data to |fd|, updating |data_file_size| as
+  // it does. Only the first |image_size| bytes are read from |new_image|
+  // assuming that this is the actual file system.
+  static bool Run(
+      Graph* graph,
+      const std::string& new_kernel_part,
+      const std::string& new_image,
+      off_t image_size,
+      int fd,
+      off_t* data_file_size,
+      off_t chunk_size,
+      off_t block_size,
+      std::vector<DeltaArchiveManifest_InstallOperation>* kernel_ops,
+      std::vector<Vertex::Index>* final_order);
+
+ private:
+  // This should never be constructed.
+  DISALLOW_IMPLICIT_CONSTRUCTORS(FullUpdateGenerator);
+};
+
+}  // namespace chromeos_update_engine
+
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_FULL_UPDATE_GENERATOR_H_
diff --git a/payload_generator/full_update_generator_unittest.cc b/payload_generator/full_update_generator_unittest.cc
new file mode 100644
index 0000000..c3da115
--- /dev/null
+++ b/payload_generator/full_update_generator_unittest.cc
@@ -0,0 +1,91 @@
+// 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 <string>
+#include <vector>
+
+#include <gtest/gtest.h>
+
+#include "update_engine/payload_generator/full_update_generator.h"
+#include "update_engine/test_utils.h"
+
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+  const size_t kBlockSize = 4096;
+}  // namespace {}
+
+
+class FullUpdateGeneratorTest : public ::testing::Test { };
+
+
+TEST(FullUpdateGeneratorTest, RunTest) {
+  vector<char> new_root(20 * 1024 * 1024);
+  vector<char> new_kern(16 * 1024 * 1024);
+  const off_t kChunkSize = 128 * 1024;
+  FillWithData(&new_root);
+  FillWithData(&new_kern);
+  // Assume hashes take 2 MiB beyond the rootfs.
+  off_t new_rootfs_size = new_root.size() - 2 * 1024 * 1024;
+
+  string new_root_path;
+  EXPECT_TRUE(utils::MakeTempFile("NewFullUpdateTest_R.XXXXXX",
+                                  &new_root_path,
+                                  NULL));
+  ScopedPathUnlinker new_root_path_unlinker(new_root_path);
+  EXPECT_TRUE(WriteFileVector(new_root_path, new_root));
+
+  string new_kern_path;
+  EXPECT_TRUE(utils::MakeTempFile("NewFullUpdateTest_K.XXXXXX",
+                                  &new_kern_path,
+                                  NULL));
+  ScopedPathUnlinker new_kern_path_unlinker(new_kern_path);
+  EXPECT_TRUE(WriteFileVector(new_kern_path, new_kern));
+
+  string out_blobs_path;
+  int out_blobs_fd;
+  EXPECT_TRUE(utils::MakeTempFile("NewFullUpdateTest_D.XXXXXX",
+                                  &out_blobs_path,
+                                  &out_blobs_fd));
+  ScopedPathUnlinker out_blobs_path_unlinker(out_blobs_path);
+  ScopedFdCloser out_blobs_fd_closer(&out_blobs_fd);
+
+  off_t out_blobs_length = 0;
+
+  Graph graph;
+  vector<DeltaArchiveManifest_InstallOperation> kernel_ops;
+  vector<Vertex::Index> final_order;
+
+  EXPECT_TRUE(FullUpdateGenerator::Run(&graph,
+                                       new_kern_path,
+                                       new_root_path,
+                                       new_rootfs_size,
+                                       out_blobs_fd,
+                                       &out_blobs_length,
+                                       kChunkSize,
+                                       kBlockSize,
+                                       &kernel_ops,
+                                       &final_order));
+  EXPECT_EQ(new_rootfs_size / kChunkSize, graph.size());
+  EXPECT_EQ(new_rootfs_size / kChunkSize, final_order.size());
+  EXPECT_EQ(new_kern.size() / kChunkSize, kernel_ops.size());
+  for (off_t i = 0; i < (new_rootfs_size / kChunkSize); ++i) {
+    EXPECT_EQ(i, final_order[i]);
+    EXPECT_EQ(1, graph[i].op.dst_extents_size());
+    EXPECT_EQ(i * kChunkSize / kBlockSize,
+              graph[i].op.dst_extents(0).start_block()) << "i = " << i;
+    EXPECT_EQ(kChunkSize / kBlockSize,
+              graph[i].op.dst_extents(0).num_blocks());
+    if (graph[i].op.type() !=
+        DeltaArchiveManifest_InstallOperation_Type_REPLACE) {
+      EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ,
+                graph[i].op.type());
+    }
+  }
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/generate_delta_main.cc b/payload_generator/generate_delta_main.cc
new file mode 100644
index 0000000..9dd6175
--- /dev/null
+++ b/payload_generator/generate_delta_main.cc
@@ -0,0 +1,397 @@
+// 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 <errno.h>
+#include <fcntl.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include <unistd.h>
+
+#include <set>
+#include <string>
+#include <vector>
+
+#include <base/command_line.h>
+#include <base/logging.h>
+#include <base/strings/string_number_conversions.h>
+#include <base/strings/string_split.h>
+#include <gflags/gflags.h>
+#include <glib.h>
+
+#include "update_engine/delta_performer.h"
+#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_signer.h"
+#include "update_engine/prefs.h"
+#include "update_engine/subprocess.h"
+#include "update_engine/terminator.h"
+#include "update_engine/update_metadata.pb.h"
+#include "update_engine/utils.h"
+
+DEFINE_string(old_dir, "",
+              "Directory where the old rootfs is loop mounted read-only");
+DEFINE_string(new_dir, "",
+              "Directory where the new rootfs is loop mounted read-only");
+DEFINE_string(old_image, "", "Path to the old rootfs");
+DEFINE_string(new_image, "", "Path to the new rootfs");
+DEFINE_string(old_kernel, "", "Path to the old kernel partition image");
+DEFINE_string(new_kernel, "", "Path to the new kernel partition image");
+DEFINE_string(in_file, "",
+              "Path to input delta payload file used to hash/sign payloads "
+              "and apply delta over old_image (for debugging)");
+DEFINE_string(out_file, "", "Path to output delta payload file");
+DEFINE_string(out_hash_file, "", "Path to output hash file");
+DEFINE_string(out_metadata_hash_file, "", "Path to output metadata hash file");
+DEFINE_string(private_key, "", "Path to private key in .pem format");
+DEFINE_string(public_key, "", "Path to public key in .pem format");
+DEFINE_int32(public_key_version,
+             chromeos_update_engine::kSignatureMessageCurrentVersion,
+             "Key-check version # of client");
+DEFINE_string(prefs_dir, "/tmp/update_engine_prefs",
+              "Preferences directory, used with apply_delta");
+DEFINE_string(signature_size, "",
+              "Raw signature size used for hash calculation. "
+              "You may pass in multiple sizes by colon separating them. E.g. "
+              "2048:2048:4096 will assume 3 signatures, the first two with "
+              "2048 size and the last 4096.");
+DEFINE_string(signature_file, "",
+              "Raw signature file to sign payload with. To pass multiple "
+              "signatures, use a single argument with a colon between paths, "
+              "e.g. /path/to/sig:/path/to/next:/path/to/last_sig . Each "
+              "signature will be assigned a client version, starting from "
+              "kSignatureOriginalVersion.");
+DEFINE_int32(chunk_size, -1, "Payload chunk size (-1 -- no limit/default)");
+DEFINE_int64(rootfs_partition_size,
+             chromeos_update_engine::kRootFSPartitionSize,
+             "RootFS partition size for the image once installed");
+
+DEFINE_string(old_channel, "",
+              "The channel for the old image. 'dev-channel', 'npo-channel', "
+              "etc. Ignored, except during delta generation.");
+DEFINE_string(old_board, "",
+              "The board for the old image. 'x86-mario', 'lumpy', "
+              "etc. Ignored, except during delta generation.");
+DEFINE_string(old_version, "",
+              "The build version of the old image. 1.2.3, etc.");
+DEFINE_string(old_key, "",
+              "The key used to sign the old image. 'premp', 'mp', 'mp-v3',"
+              " etc");
+DEFINE_string(old_build_channel, "",
+              "The channel for the build of the old image. 'dev-channel', "
+              "etc, but will never contain special channels such as "
+              "'npo-channel'. Ignored, except during delta generation.");
+DEFINE_string(old_build_version, "",
+              "The version of the build containing the old image.");
+
+DEFINE_string(new_channel, "",
+              "The channel for the new image. 'dev-channel', 'npo-channel', "
+              "etc. Ignored, except during delta generation.");
+DEFINE_string(new_board, "",
+              "The board for the new image. 'x86-mario', 'lumpy', "
+              "etc. Ignored, except during delta generation.");
+DEFINE_string(new_version, "",
+              "The build version of the new image. 1.2.3, etc.");
+DEFINE_string(new_key, "",
+              "The key used to sign the new image. 'premp', 'mp', 'mp-v3',"
+              " etc");
+DEFINE_string(new_build_channel, "",
+              "The channel for the build of the new image. 'dev-channel', "
+              "etc, but will never contain special channels such as "
+              "'npo-channel'. Ignored, except during delta generation.");
+DEFINE_string(new_build_version, "",
+              "The version of the build containing the new image.");
+
+// This file contains a simple program that takes an old path, a new path,
+// and an output file as arguments and the path to an output file and
+// generates a delta that can be sent to Chrome OS clients.
+
+using std::set;
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+
+bool IsDir(const char* path) {
+  struct stat stbuf;
+  TEST_AND_RETURN_FALSE_ERRNO(lstat(path, &stbuf) == 0);
+  return S_ISDIR(stbuf.st_mode);
+}
+
+void ParseSignatureSizes(const string& signature_sizes_flag,
+                         vector<int>* signature_sizes) {
+  signature_sizes->clear();
+  vector<string> split_strings;
+
+  base::SplitString(signature_sizes_flag, ':', &split_strings);
+  for (vector<string>::iterator i = split_strings.begin();
+       i < split_strings.end();
+       i++) {
+    int size = 0;
+    bool parsing_successful = base::StringToInt(*i, &size);
+    LOG_IF(FATAL, !parsing_successful)
+        << "Invalid signature size: " << *i;
+
+    LOG_IF(FATAL, size != (2048 / 8)) <<
+        "Only signature sizes of 256 bytes are supported.";
+
+    signature_sizes->push_back(size);
+  }
+}
+
+
+bool ParseImageInfo(const string& channel,
+                    const string& board,
+                    const string& version,
+                    const string& key,
+                    const string& build_channel,
+                    const string& build_version,
+                    ImageInfo* image_info) {
+
+  // All of these arguments should be present or missing.
+  bool empty = channel.empty();
+
+  CHECK_EQ(channel.empty(), empty);
+  CHECK_EQ(board.empty(), empty);
+  CHECK_EQ(version.empty(), empty);
+  CHECK_EQ(key.empty(), empty);
+
+  if (empty)
+    return false;
+
+  image_info->set_channel(channel);
+  image_info->set_board(board);
+  image_info->set_version(version);
+  image_info->set_key(key);
+
+  image_info->set_build_channel(
+      build_channel.empty() ? channel : build_channel);
+
+  image_info->set_build_version(
+      build_version.empty() ? version : build_version);
+
+  return true;
+}
+
+void CalculatePayloadHashForSigning(const vector<int> &sizes,
+                                    const string& out_hash_file) {
+  LOG(INFO) << "Calculating payload hash for signing.";
+  LOG_IF(FATAL, FLAGS_in_file.empty())
+      << "Must pass --in_file to calculate hash for signing.";
+  LOG_IF(FATAL, out_hash_file.empty())
+      << "Must pass --out_hash_file to calculate hash for signing.";
+
+  vector<char> hash;
+  bool result = PayloadSigner::HashPayloadForSigning(FLAGS_in_file, sizes,
+                                                     &hash);
+  CHECK(result);
+
+  result = utils::WriteFile(out_hash_file.c_str(), hash.data(), hash.size());
+  CHECK(result);
+  LOG(INFO) << "Done calculating payload hash for signing.";
+}
+
+
+void CalculateMetadataHashForSigning(const vector<int> &sizes,
+                                     const string& out_metadata_hash_file) {
+  LOG(INFO) << "Calculating metadata hash for signing.";
+  LOG_IF(FATAL, FLAGS_in_file.empty())
+      << "Must pass --in_file to calculate metadata hash for signing.";
+  LOG_IF(FATAL, out_metadata_hash_file.empty())
+      << "Must pass --out_metadata_hash_file to calculate metadata hash.";
+
+  vector<char> hash;
+  bool result = PayloadSigner::HashMetadataForSigning(FLAGS_in_file, sizes,
+                                                      &hash);
+  CHECK(result);
+
+  result = utils::WriteFile(out_metadata_hash_file.c_str(), hash.data(),
+                            hash.size());
+  CHECK(result);
+
+  LOG(INFO) << "Done calculating metadata hash for signing.";
+}
+
+void SignPayload() {
+  LOG(INFO) << "Signing payload.";
+  LOG_IF(FATAL, FLAGS_in_file.empty())
+      << "Must pass --in_file to sign payload.";
+  LOG_IF(FATAL, FLAGS_out_file.empty())
+      << "Must pass --out_file to sign payload.";
+  LOG_IF(FATAL, FLAGS_signature_file.empty())
+      << "Must pass --signature_file to sign payload.";
+  vector<vector<char> > signatures;
+  vector<string> signature_files;
+  base::SplitString(FLAGS_signature_file, ':', &signature_files);
+  for (vector<string>::iterator it = signature_files.begin(),
+           e = signature_files.end(); it != e; ++it) {
+    vector<char> signature;
+    CHECK(utils::ReadFile(*it, &signature));
+    signatures.push_back(signature);
+  }
+  uint64_t final_metadata_size;
+  CHECK(PayloadSigner::AddSignatureToPayload(
+      FLAGS_in_file, signatures, FLAGS_out_file, &final_metadata_size));
+  LOG(INFO) << "Done signing payload. Final metadata size = "
+            << final_metadata_size;
+}
+
+void VerifySignedPayload() {
+  LOG(INFO) << "Verifying signed payload.";
+  LOG_IF(FATAL, FLAGS_in_file.empty())
+      << "Must pass --in_file to verify signed payload.";
+  LOG_IF(FATAL, FLAGS_public_key.empty())
+      << "Must pass --public_key to verify signed payload.";
+  CHECK(PayloadSigner::VerifySignedPayload(FLAGS_in_file, FLAGS_public_key,
+                                           FLAGS_public_key_version));
+  LOG(INFO) << "Done verifying signed payload.";
+}
+
+void ApplyDelta() {
+  LOG(INFO) << "Applying delta.";
+  LOG_IF(FATAL, FLAGS_old_image.empty())
+      << "Must pass --old_image to apply delta.";
+  Prefs prefs;
+  InstallPlan install_plan;
+  LOG(INFO) << "Setting up preferences under: " << FLAGS_prefs_dir;
+  LOG_IF(ERROR, !prefs.Init(base::FilePath(FLAGS_prefs_dir)))
+      << "Failed to initialize preferences.";
+  // Get original checksums
+  LOG(INFO) << "Calculating original checksums";
+  PartitionInfo kern_info, root_info;
+  CHECK(DeltaDiffGenerator::InitializePartitionInfo(true,  // is_kernel
+                                                    FLAGS_old_kernel,
+                                                    &kern_info));
+  CHECK(DeltaDiffGenerator::InitializePartitionInfo(false,  // is_kernel
+                                                    FLAGS_old_image,
+                                                    &root_info));
+  install_plan.kernel_hash.assign(kern_info.hash().begin(),
+                                  kern_info.hash().end());
+  install_plan.rootfs_hash.assign(root_info.hash().begin(),
+                                  root_info.hash().end());
+  DeltaPerformer performer(&prefs, NULL, &install_plan);
+  CHECK_EQ(performer.Open(FLAGS_old_image.c_str(), 0, 0), 0);
+  CHECK(performer.OpenKernel(FLAGS_old_kernel.c_str()));
+  vector<char> buf(1024 * 1024);
+  int fd = open(FLAGS_in_file.c_str(), O_RDONLY, 0);
+  CHECK_GE(fd, 0);
+  ScopedFdCloser fd_closer(&fd);
+  for (off_t offset = 0;; offset += buf.size()) {
+    ssize_t bytes_read;
+    CHECK(utils::PReadAll(fd, &buf[0], buf.size(), offset, &bytes_read));
+    if (bytes_read == 0)
+      break;
+    CHECK_EQ(performer.Write(&buf[0], bytes_read), bytes_read);
+  }
+  CHECK_EQ(performer.Close(), 0);
+  DeltaPerformer::ResetUpdateProgress(&prefs, false);
+  LOG(INFO) << "Done applying delta.";
+}
+
+int Main(int argc, char** argv) {
+  google::ParseCommandLineFlags(&argc, &argv, true);
+  CommandLine::Init(argc, argv);
+  Terminator::Init();
+  Subprocess::Init();
+
+  logging::LoggingSettings log_settings;
+  log_settings.log_file     = "delta_generator.log";
+  log_settings.logging_dest = logging::LOG_TO_SYSTEM_DEBUG_LOG;
+  log_settings.lock_log     = logging::DONT_LOCK_LOG_FILE;
+  log_settings.delete_old   = logging::APPEND_TO_OLD_LOG_FILE;
+  log_settings.dcheck_state =
+    logging::DISABLE_DCHECK_FOR_NON_OFFICIAL_RELEASE_BUILDS;
+
+  logging::InitLogging(log_settings);
+
+  vector<int> signature_sizes;
+  ParseSignatureSizes(FLAGS_signature_size, &signature_sizes);
+
+  if (!FLAGS_out_hash_file.empty() || !FLAGS_out_metadata_hash_file.empty()) {
+    if (!FLAGS_out_hash_file.empty()) {
+      CalculatePayloadHashForSigning(signature_sizes, FLAGS_out_hash_file);
+    }
+    if (!FLAGS_out_metadata_hash_file.empty()) {
+      CalculateMetadataHashForSigning(signature_sizes,
+                                      FLAGS_out_metadata_hash_file);
+    }
+    return 0;
+  }
+  if (!FLAGS_signature_file.empty()) {
+    SignPayload();
+    return 0;
+  }
+  if (!FLAGS_public_key.empty()) {
+    VerifySignedPayload();
+    return 0;
+  }
+  if (!FLAGS_in_file.empty()) {
+    ApplyDelta();
+    return 0;
+  }
+  CHECK(!FLAGS_new_image.empty());
+  CHECK(!FLAGS_out_file.empty());
+  CHECK(!FLAGS_new_kernel.empty());
+
+  bool is_delta = !FLAGS_old_image.empty();
+
+  ImageInfo old_image_info;
+  ImageInfo new_image_info;
+
+  // Ignore failures. These are optional arguments.
+  ParseImageInfo(FLAGS_new_channel,
+                 FLAGS_new_board,
+                 FLAGS_new_version,
+                 FLAGS_new_key,
+                 FLAGS_new_build_channel,
+                 FLAGS_new_build_version,
+                 &new_image_info);
+
+  // Ignore failures. These are optional arguments.
+  ParseImageInfo(FLAGS_old_channel,
+                 FLAGS_old_board,
+                 FLAGS_old_version,
+                 FLAGS_old_key,
+                 FLAGS_old_build_channel,
+                 FLAGS_old_build_version,
+                 &old_image_info);
+
+  if (is_delta) {
+    LOG(INFO) << "Generating delta update";
+    CHECK(!FLAGS_old_dir.empty());
+    CHECK(!FLAGS_new_dir.empty());
+    if ((!IsDir(FLAGS_old_dir.c_str())) || (!IsDir(FLAGS_new_dir.c_str()))) {
+      LOG(FATAL) << "old_dir or new_dir not directory";
+    }
+  } else {
+    LOG(INFO) << "Generating full update";
+  }
+
+  uint64_t metadata_size;
+  if (!DeltaDiffGenerator::GenerateDeltaUpdateFile(
+      FLAGS_old_dir,
+      FLAGS_old_image,
+      FLAGS_new_dir,
+      FLAGS_new_image,
+      FLAGS_old_kernel,
+      FLAGS_new_kernel,
+      FLAGS_out_file,
+      FLAGS_private_key,
+      FLAGS_chunk_size,
+      FLAGS_rootfs_partition_size,
+      is_delta ? &old_image_info : NULL,
+      &new_image_info,
+      &metadata_size)) {
+    return 1;
+  }
+  return 0;
+}
+
+}  // namespace {}
+
+}  // namespace chromeos_update_engine
+
+int main(int argc, char** argv) {
+  return chromeos_update_engine::Main(argc, argv);
+}
diff --git a/payload_generator/graph_types.h b/payload_generator/graph_types.h
new file mode 100644
index 0000000..c5531c2
--- /dev/null
+++ b/payload_generator/graph_types.h
@@ -0,0 +1,83 @@
+// Copyright (c) 2009 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 CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_
+
+#include <map>
+#include <set>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include <base/basictypes.h>
+
+#include "update_engine/update_metadata.pb.h"
+
+// A few classes that help in generating delta images use these types
+// for the graph work.
+
+namespace chromeos_update_engine {
+
+bool operator==(const Extent& a, const Extent& b);
+
+struct EdgeProperties {
+  // Read-before extents. I.e., blocks in |extents| must be read by the
+  // node pointed to before the pointing node runs (presumably b/c it
+  // overwrites these blocks).
+  std::vector<Extent> extents;
+
+  // Write before extents. I.e., blocks in |write_extents| must be written
+  // by the node pointed to before the pointing node runs (presumably
+  // b/c it reads the data written by the other node).
+  std::vector<Extent> write_extents;
+
+  bool operator==(const EdgeProperties& that) const {
+    return extents == that.extents && write_extents == that.write_extents;
+  }
+};
+
+struct Vertex {
+  Vertex() :
+      valid(true),
+      index(-1),
+      lowlink(-1),
+      chunk_offset(0),
+      chunk_size(-1) {}
+  bool valid;
+
+  typedef std::map<std::vector<Vertex>::size_type, EdgeProperties> EdgeMap;
+  EdgeMap out_edges;
+
+  // We sometimes wish to consider a subgraph of a graph. A subgraph would have
+  // a subset of the vertices from the graph and a subset of the edges.
+  // When considering this vertex within a subgraph, subgraph_edges stores
+  // the out-edges.
+  typedef std::set<std::vector<Vertex>::size_type> SubgraphEdgeMap;
+  SubgraphEdgeMap subgraph_edges;
+
+  // For Tarjan's algorithm:
+  std::vector<Vertex>::size_type index;
+  std::vector<Vertex>::size_type lowlink;
+
+  // Other Vertex properties:
+  DeltaArchiveManifest_InstallOperation op;
+  std::string file_name;
+  off_t chunk_offset;
+  off_t chunk_size;
+
+  typedef std::vector<Vertex>::size_type Index;
+  static const Vertex::Index kInvalidIndex = -1;
+};
+
+typedef std::vector<Vertex> Graph;
+
+typedef std::pair<Vertex::Index, Vertex::Index> Edge;
+
+const uint64_t kTempBlockStart = 1ULL << 60;
+COMPILE_ASSERT(kTempBlockStart != 0, kTempBlockStart_invalid);
+
+}  // namespace chromeos_update_engine
+
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_
diff --git a/payload_generator/graph_utils.cc b/payload_generator/graph_utils.cc
new file mode 100644
index 0000000..8b6535d
--- /dev/null
+++ b/payload_generator/graph_utils.cc
@@ -0,0 +1,176 @@
+// Copyright (c) 2009 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/graph_utils.h"
+
+#include <string>
+#include <utility>
+#include <vector>
+
+#include <base/basictypes.h>
+#include <base/logging.h>
+
+#include "update_engine/payload_constants.h"
+
+using std::make_pair;
+using std::pair;
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace graph_utils {
+
+uint64_t EdgeWeight(const Graph& graph, const Edge& edge) {
+  uint64_t weight = 0;
+  const vector<Extent>& extents =
+      graph[edge.first].out_edges.find(edge.second)->second.extents;
+  for (vector<Extent>::const_iterator it = extents.begin();
+       it != extents.end(); ++it) {
+    if (it->start_block() != kSparseHole)
+      weight += it->num_blocks();
+  }
+  return weight;
+}
+
+void AppendBlockToExtents(vector<Extent>* extents, uint64_t block) {
+  // First try to extend the last extent in |extents|, if any.
+  if (!extents->empty()) {
+    Extent& extent = extents->back();
+    uint64_t next_block = extent.start_block() == kSparseHole ?
+        kSparseHole : extent.start_block() + extent.num_blocks();
+    if (next_block == block) {
+      extent.set_num_blocks(extent.num_blocks() + 1);
+      return;
+    }
+  }
+  // If unable to extend the last extent, append a new single-block extent.
+  Extent new_extent;
+  new_extent.set_start_block(block);
+  new_extent.set_num_blocks(1);
+  extents->push_back(new_extent);
+}
+
+void AddReadBeforeDep(Vertex* src,
+                      Vertex::Index dst,
+                      uint64_t block) {
+  Vertex::EdgeMap::iterator edge_it = src->out_edges.find(dst);
+  if (edge_it == src->out_edges.end()) {
+    // Must create new edge
+    pair<Vertex::EdgeMap::iterator, bool> result =
+        src->out_edges.insert(make_pair(dst, EdgeProperties()));
+    CHECK(result.second);
+    edge_it = result.first;
+  }
+  AppendBlockToExtents(&edge_it->second.extents, block);
+}
+
+void AddReadBeforeDepExtents(Vertex* src,
+                             Vertex::Index dst,
+                             const vector<Extent>& extents) {
+  // TODO(adlr): Be more efficient than adding each block individually.
+  for (vector<Extent>::const_iterator it = extents.begin(), e = extents.end();
+       it != e; ++it) {
+    const Extent& extent = *it;
+    for (uint64_t block = extent.start_block(),
+             block_end = extent.start_block() + extent.num_blocks();
+         block != block_end; ++block) {
+      AddReadBeforeDep(src, dst, block);
+    }
+  }
+}
+
+void DropWriteBeforeDeps(Vertex::EdgeMap* edge_map) {
+  // Specially crafted for-loop for the map-iterate-delete dance.
+  for (Vertex::EdgeMap::iterator it = edge_map->begin();
+       it != edge_map->end(); ) {
+    if (!it->second.write_extents.empty())
+      it->second.write_extents.clear();
+    if (it->second.extents.empty()) {
+      // Erase *it, as it contains no blocks
+      edge_map->erase(it++);
+    } else {
+      ++it;
+    }
+  }
+}
+
+// For each node N in graph, drop all edges N->|index|.
+void DropIncomingEdgesTo(Graph* graph, Vertex::Index index) {
+  // This would be much more efficient if we had doubly-linked
+  // edges in the graph.
+  for (Graph::iterator it = graph->begin(), e = graph->end(); it != e; ++it) {
+    it->out_edges.erase(index);
+  }
+}
+
+Extent GetElement(const std::vector<Extent>& collection, size_t index) {
+  return collection[index];
+}
+Extent GetElement(
+    const google::protobuf::RepeatedPtrField<Extent>& collection,
+    size_t index) {
+  return collection.Get(index);
+}
+
+namespace {
+template<typename T>
+void DumpExtents(const T& field, int prepend_space_count) {
+  string header(prepend_space_count, ' ');
+  for (int i = 0, e = field.size(); i != e; ++i) {
+    LOG(INFO) << header << "(" << GetElement(field, i).start_block() << ", "
+              << GetElement(field, i).num_blocks() << ")";
+  }
+}
+
+void DumpOutEdges(const Vertex::EdgeMap& out_edges) {
+  for (Vertex::EdgeMap::const_iterator it = out_edges.begin(),
+           e = out_edges.end(); it != e; ++it) {
+    LOG(INFO) << "    " << it->first << " read-before:";
+    DumpExtents(it->second.extents, 6);
+    LOG(INFO) << "      write-before:";
+    DumpExtents(it->second.write_extents, 6);
+  }
+}
+}  // namespace {}
+
+void DumpGraph(const Graph& graph) {
+  LOG(INFO) << "Graph length: " << graph.size();
+  for (Graph::size_type i = 0, e = graph.size(); i != e; ++i) {
+    string type_str = "UNK";
+    switch(graph[i].op.type()) {
+      case DeltaArchiveManifest_InstallOperation_Type_BSDIFF:
+        type_str = "BSDIFF";
+        break;
+      case DeltaArchiveManifest_InstallOperation_Type_MOVE:
+        type_str = "MOVE";
+        break;
+      case DeltaArchiveManifest_InstallOperation_Type_REPLACE:
+        type_str = "REPLACE";
+        break;
+      case DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ:
+        type_str = "REPLACE_BZ";
+        break;
+    }
+    LOG(INFO) << i
+              << (graph[i].valid ? "" : "-INV")
+              << ": " << graph[i].file_name
+              << " " << graph[i].chunk_size << "@" << graph[i].chunk_offset
+              << ": " << type_str;
+    LOG(INFO) << "  src_extents:";
+    DumpExtents(graph[i].op.src_extents(), 4);
+    LOG(INFO) << "  dst_extents:";
+    DumpExtents(graph[i].op.dst_extents(), 4);
+    LOG(INFO) << "  out edges:";
+    DumpOutEdges(graph[i].out_edges);
+  }
+}
+
+}  // namespace graph_utils
+
+bool operator==(const Extent& a, const Extent& b) {
+  return a.start_block() == b.start_block() && a.num_blocks() == b.num_blocks();
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/graph_utils.h b/payload_generator/graph_utils.h
new file mode 100644
index 0000000..0489793
--- /dev/null
+++ b/payload_generator/graph_utils.h
@@ -0,0 +1,65 @@
+// Copyright (c) 2009 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 CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_UTILS_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_UTILS_H_
+
+#include <vector>
+
+#include <base/basictypes.h>
+
+#include "update_engine/payload_generator/graph_types.h"
+#include "update_engine/update_metadata.pb.h"
+
+// A few utility functions for graphs
+
+namespace chromeos_update_engine {
+
+namespace graph_utils {
+
+// Returns the number of blocks represented by all extents in the edge.
+uint64_t EdgeWeight(const Graph& graph, const Edge& edge);
+
+// These add a read-before dependency from graph[src] -> graph[dst]. If the dep
+// already exists, the block/s is/are added to the existing edge.
+void AddReadBeforeDep(Vertex* src,
+                      Vertex::Index dst,
+                      uint64_t block);
+void AddReadBeforeDepExtents(Vertex* src,
+                             Vertex::Index dst,
+                             const std::vector<Extent>& extents);
+
+void DropWriteBeforeDeps(Vertex::EdgeMap* edge_map);
+
+// For each node N in graph, drop all edges N->|index|.
+void DropIncomingEdgesTo(Graph* graph, Vertex::Index index);
+
+// block must either be the next block in the last extent or a block
+// in the next extent. This function will not handle inserting block
+// into an arbitrary place in the extents.
+void AppendBlockToExtents(std::vector<Extent>* extents, uint64_t block);
+
+// Get/SetElement are intentionally overloaded so that templated functions
+// can accept either type of collection of Extents.
+Extent GetElement(const std::vector<Extent>& collection, size_t index);
+Extent GetElement(
+    const google::protobuf::RepeatedPtrField<Extent>& collection,
+    size_t index);
+
+template<typename T>
+uint64_t BlocksInExtents(const T& collection) {
+  uint64_t ret = 0;
+  for (size_t i = 0; i < static_cast<size_t>(collection.size()); ++i) {
+    ret += GetElement(collection, i).num_blocks();
+  }
+  return ret;
+}
+
+void DumpGraph(const Graph& graph);
+
+}  // namespace graph_utils
+
+}  // namespace chromeos_update_engine
+
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_UTILS_H_
diff --git a/payload_generator/graph_utils_unittest.cc b/payload_generator/graph_utils_unittest.cc
new file mode 100644
index 0000000..0aed78d
--- /dev/null
+++ b/payload_generator/graph_utils_unittest.cc
@@ -0,0 +1,123 @@
+// Copyright (c) 2009 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 <utility>
+#include <vector>
+
+#include <gtest/gtest.h>
+
+#include "update_engine/extent_ranges.h"
+#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/graph_utils.h"
+
+using std::make_pair;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+class GraphUtilsTest : public ::testing::Test {};
+
+TEST(GraphUtilsTest, SimpleTest) {
+  Graph graph(2);
+
+  graph[0].out_edges.insert(make_pair(1, EdgeProperties()));
+
+  vector<Extent>& extents = graph[0].out_edges[1].extents;
+
+  EXPECT_EQ(0, extents.size());
+  graph_utils::AppendBlockToExtents(&extents, 0);
+  EXPECT_EQ(1, extents.size());
+  graph_utils::AppendBlockToExtents(&extents, 1);
+  graph_utils::AppendBlockToExtents(&extents, 2);
+  EXPECT_EQ(1, extents.size());
+  graph_utils::AppendBlockToExtents(&extents, 4);
+
+  EXPECT_EQ(2, extents.size());
+  EXPECT_EQ(0, extents[0].start_block());
+  EXPECT_EQ(3, extents[0].num_blocks());
+  EXPECT_EQ(4, extents[1].start_block());
+  EXPECT_EQ(1, extents[1].num_blocks());
+
+  EXPECT_EQ(4, graph_utils::EdgeWeight(graph, make_pair(0, 1)));
+}
+
+TEST(GraphUtilsTest, AppendSparseToExtentsTest) {
+  vector<Extent> extents;
+
+  EXPECT_EQ(0, extents.size());
+  graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+  EXPECT_EQ(1, extents.size());
+  graph_utils::AppendBlockToExtents(&extents, 0);
+  EXPECT_EQ(2, extents.size());
+  graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+  graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+
+  ASSERT_EQ(3, extents.size());
+  EXPECT_EQ(kSparseHole, extents[0].start_block());
+  EXPECT_EQ(1, extents[0].num_blocks());
+  EXPECT_EQ(0, extents[1].start_block());
+  EXPECT_EQ(1, extents[1].num_blocks());
+  EXPECT_EQ(kSparseHole, extents[2].start_block());
+  EXPECT_EQ(2, extents[2].num_blocks());
+}
+
+TEST(GraphUtilsTest, BlocksInExtentsTest) {
+  {
+    vector<Extent> extents;
+    EXPECT_EQ(0, graph_utils::BlocksInExtents(extents));
+    extents.push_back(ExtentForRange(0, 1));
+    EXPECT_EQ(1, graph_utils::BlocksInExtents(extents));
+    extents.push_back(ExtentForRange(23, 55));
+    EXPECT_EQ(56, graph_utils::BlocksInExtents(extents));
+    extents.push_back(ExtentForRange(1, 2));
+    EXPECT_EQ(58, graph_utils::BlocksInExtents(extents));
+  }
+  {
+    google::protobuf::RepeatedPtrField<Extent> extents;
+    EXPECT_EQ(0, graph_utils::BlocksInExtents(extents));
+    *extents.Add() = ExtentForRange(0, 1);
+    EXPECT_EQ(1, graph_utils::BlocksInExtents(extents));
+    *extents.Add() = ExtentForRange(23, 55);
+    EXPECT_EQ(56, graph_utils::BlocksInExtents(extents));
+    *extents.Add() = ExtentForRange(1, 2);
+    EXPECT_EQ(58, graph_utils::BlocksInExtents(extents));
+  }
+}
+
+TEST(GraphUtilsTest, DepsTest) {
+  Graph graph(3);
+
+  graph_utils::AddReadBeforeDep(&graph[0], 1, 3);
+  EXPECT_EQ(1, graph[0].out_edges.size());
+  {
+    Extent& extent = graph[0].out_edges[1].extents[0];
+    EXPECT_EQ(3, extent.start_block());
+    EXPECT_EQ(1, extent.num_blocks());
+  }
+  graph_utils::AddReadBeforeDep(&graph[0], 1, 4);
+  EXPECT_EQ(1, graph[0].out_edges.size());
+  {
+    Extent& extent = graph[0].out_edges[1].extents[0];
+    EXPECT_EQ(3, extent.start_block());
+    EXPECT_EQ(2, extent.num_blocks());
+  }
+  graph_utils::AddReadBeforeDepExtents(&graph[2], 1,
+    vector<Extent>(1, ExtentForRange(5, 2)));
+  EXPECT_EQ(1, graph[2].out_edges.size());
+  {
+    Extent& extent = graph[2].out_edges[1].extents[0];
+    EXPECT_EQ(5, extent.start_block());
+    EXPECT_EQ(2, extent.num_blocks());
+  }
+  // Change most recent edge from read-before to write-before
+  graph[2].out_edges[1].write_extents.swap(graph[2].out_edges[1].extents);
+  graph_utils::DropWriteBeforeDeps(&graph[2].out_edges);
+  EXPECT_EQ(0, graph[2].out_edges.size());
+
+  EXPECT_EQ(1, graph[0].out_edges.size());
+  graph_utils::DropIncomingEdgesTo(&graph, 1);
+  EXPECT_EQ(0, graph[0].out_edges.size());
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/metadata.cc b/payload_generator/metadata.cc
new file mode 100644
index 0000000..f0c9238
--- /dev/null
+++ b/payload_generator/metadata.cc
@@ -0,0 +1,486 @@
+// 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 <algorithm>
+#include <string>
+#include <vector>
+
+#include <base/strings/string_util.h>
+#include <base/strings/stringprintf.h>
+#include <et/com_err.h>
+#include <ext2fs/ext2_io.h>
+#include <ext2fs/ext2fs.h>
+
+#include "update_engine/bzip.h"
+#include "update_engine/extent_ranges.h"
+#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/graph_utils.h"
+#include "update_engine/payload_generator/metadata.h"
+#include "update_engine/utils.h"
+
+using base::StringPrintf;
+using std::min;
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+const size_t kBlockSize = 4096;
+
+typedef DeltaDiffGenerator::Block Block;
+
+// Read data from the specified extents.
+bool ReadExtentsData(const ext2_filsys fs,
+                     const vector<Extent>& extents,
+                     vector<char>* data) {
+  // Resize the data buffer to hold all data in the extents
+  size_t num_data_blocks = 0;
+  for (vector<Extent>::const_iterator it = extents.begin();
+       it != extents.end(); it++) {
+    num_data_blocks += it->num_blocks();
+  }
+
+  data->resize(num_data_blocks * kBlockSize);
+
+  // Read in the data blocks
+  const size_t kMaxReadBlocks = 256;
+  vector<Block>::size_type blocks_copied_count = 0;
+  for (vector<Extent>::const_iterator it = extents.begin();
+       it != extents.end(); it++) {
+    vector<Block>::size_type blocks_read = 0;
+    while (blocks_read < it->num_blocks()) {
+      const int copy_block_cnt =
+          min(kMaxReadBlocks,
+              static_cast<size_t>(
+                  it->num_blocks() - blocks_read));
+      TEST_AND_RETURN_FALSE_ERRCODE(
+          io_channel_read_blk(fs->io,
+                              it->start_block() + blocks_read,
+                              copy_block_cnt,
+                              &(*data)[blocks_copied_count * kBlockSize]));
+      blocks_read += copy_block_cnt;
+      blocks_copied_count += copy_block_cnt;
+    }
+  }
+
+  return true;
+}
+
+// Compute the bsdiff between two metadata blobs.
+bool ComputeMetadataBsdiff(const vector<char>& old_metadata,
+                           const vector<char>& new_metadata,
+                           vector<char>* bsdiff_delta) {
+  const string kTempFileTemplate("CrAU_temp_data.XXXXXX");
+
+  // Write the metadata buffers to temporary files
+  int old_fd;
+  string temp_old_file_path;
+  TEST_AND_RETURN_FALSE(
+      utils::MakeTempFile(kTempFileTemplate, &temp_old_file_path, &old_fd));
+  TEST_AND_RETURN_FALSE(old_fd >= 0);
+  ScopedPathUnlinker temp_old_file_path_unlinker(temp_old_file_path);
+  ScopedFdCloser old_fd_closer(&old_fd);
+  TEST_AND_RETURN_FALSE(utils::WriteAll(old_fd,
+                                        &old_metadata[0],
+                                        old_metadata.size()));
+
+  int new_fd;
+  string temp_new_file_path;
+  TEST_AND_RETURN_FALSE(
+      utils::MakeTempFile(kTempFileTemplate, &temp_new_file_path, &new_fd));
+  TEST_AND_RETURN_FALSE(new_fd >= 0);
+  ScopedPathUnlinker temp_new_file_path_unlinker(temp_new_file_path);
+  ScopedFdCloser new_fd_closer(&new_fd);
+  TEST_AND_RETURN_FALSE(utils::WriteAll(new_fd,
+                                        &new_metadata[0],
+                                        new_metadata.size()));
+
+  // Perform bsdiff on these files
+  TEST_AND_RETURN_FALSE(
+      DeltaDiffGenerator::BsdiffFiles(temp_old_file_path,
+                                      temp_new_file_path,
+                                      bsdiff_delta));
+
+  return true;
+}
+
+// Add the specified metadata extents to the graph and blocks vector.
+bool AddMetadataExtents(Graph* graph,
+                        vector<Block>* blocks,
+                        const ext2_filsys fs_old,
+                        const ext2_filsys fs_new,
+                        const string& metadata_name,
+                        const vector<Extent>& extents,
+                        int data_fd,
+                        off_t* data_file_size) {
+  vector<char> data;  // Data blob that will be written to delta file.
+  DeltaArchiveManifest_InstallOperation op;
+
+  {
+    // Read in the metadata blocks from the old and new image.
+    vector<char> old_data;
+    TEST_AND_RETURN_FALSE(ReadExtentsData(fs_old, extents, &old_data));
+
+    vector<char> new_data;
+    TEST_AND_RETURN_FALSE(ReadExtentsData(fs_new, extents, &new_data));
+
+    // Determine the best way to compress this.
+    vector<char> new_data_bz;
+    TEST_AND_RETURN_FALSE(BzipCompress(new_data, &new_data_bz));
+    CHECK(!new_data_bz.empty());
+
+    size_t current_best_size = 0;
+    if (new_data.size() <= new_data_bz.size()) {
+      op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+      current_best_size = new_data.size();
+      data = new_data;
+    } else {
+      op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
+      current_best_size = new_data_bz.size();
+      data = new_data_bz;
+    }
+
+    if (old_data == new_data) {
+      // No change in data.
+      op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
+      current_best_size = 0;
+      data.clear();
+    } else {
+      // Try bsdiff of old to new data
+      vector<char> bsdiff_delta;
+      TEST_AND_RETURN_FALSE(ComputeMetadataBsdiff(old_data,
+                                                  new_data,
+                                                  &bsdiff_delta));
+      CHECK_GT(bsdiff_delta.size(), static_cast<vector<char>::size_type>(0));
+
+      if (bsdiff_delta.size() < current_best_size) {
+        op.set_type(DeltaArchiveManifest_InstallOperation_Type_BSDIFF);
+        current_best_size = bsdiff_delta.size();
+        data = bsdiff_delta;
+      }
+    }
+
+    CHECK_EQ(data.size(), current_best_size);
+
+    // Set the source and dest extents to be the same since the filesystem
+    // structures are identical
+    if (op.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE ||
+        op.type() == DeltaArchiveManifest_InstallOperation_Type_BSDIFF) {
+      DeltaDiffGenerator::StoreExtents(extents, op.mutable_src_extents());
+      op.set_src_length(old_data.size());
+    }
+
+    DeltaDiffGenerator::StoreExtents(extents, op.mutable_dst_extents());
+    op.set_dst_length(new_data.size());
+  }
+
+  // Write data to output file
+  if (op.type() != DeltaArchiveManifest_InstallOperation_Type_MOVE) {
+    op.set_data_offset(*data_file_size);
+    op.set_data_length(data.size());
+  }
+
+  TEST_AND_RETURN_FALSE(utils::WriteAll(data_fd, &data[0], data.size()));
+  *data_file_size += data.size();
+
+  // Now, insert into graph and blocks vector
+  graph->resize(graph->size() + 1);
+  Vertex::Index vertex = graph->size() - 1;
+  (*graph)[vertex].op = op;
+  CHECK((*graph)[vertex].op.has_type());
+  (*graph)[vertex].file_name = metadata_name;
+
+  TEST_AND_RETURN_FALSE(DeltaDiffGenerator::AddInstallOpToBlocksVector(
+      (*graph)[vertex].op,
+      *graph,
+      vertex,
+      blocks));
+
+  return true;
+}
+
+// Reads the file system metadata extents.
+bool ReadFilesystemMetadata(Graph* graph,
+                            vector<Block>* blocks,
+                            const ext2_filsys fs_old,
+                            const ext2_filsys fs_new,
+                            int data_fd,
+                            off_t* data_file_size) {
+  LOG(INFO) << "Processing <rootfs-metadata>";
+
+  // Read all the extents that belong to the main file system metadata.
+  // The metadata blocks are at the start of each block group and goes
+  // until the end of the inode table.
+  for (dgrp_t bg = 0; bg < fs_old->group_desc_count; bg++) {
+    struct ext2_group_desc* group_desc = ext2fs_group_desc(fs_old,
+                                                           fs_old->group_desc,
+                                                           bg);
+    __u32 num_metadata_blocks = (group_desc->bg_inode_table +
+                                 fs_old->inode_blocks_per_group) -
+                                 (bg * fs_old->super->s_blocks_per_group);
+    __u32 bg_start_block = bg * fs_old->super->s_blocks_per_group;
+
+    // Due to bsdiff slowness, we're going to break each block group down
+    // into metadata chunks and feed them to bsdiff.
+    __u32 num_chunks = 10;
+    __u32 blocks_per_chunk = num_metadata_blocks / num_chunks;
+    __u32 curr_block = bg_start_block;
+    for (__u32 chunk = 0; chunk < num_chunks; chunk++) {
+      Extent extent;
+      if (chunk < num_chunks - 1) {
+        extent = ExtentForRange(curr_block, blocks_per_chunk);
+      } else {
+        extent = ExtentForRange(curr_block,
+                                bg_start_block + num_metadata_blocks -
+                                curr_block);
+      }
+
+      vector<Extent> extents;
+      extents.push_back(extent);
+
+      string metadata_name = StringPrintf("<rootfs-bg-%d-%d-metadata>",
+                                          bg, chunk);
+
+      LOG(INFO) << "Processing " << metadata_name;
+
+      TEST_AND_RETURN_FALSE(AddMetadataExtents(graph,
+                                               blocks,
+                                               fs_old,
+                                               fs_new,
+                                               metadata_name,
+                                               extents,
+                                               data_fd,
+                                               data_file_size));
+
+      curr_block += blocks_per_chunk;
+    }
+  }
+
+  return true;
+}
+
+// Processes all blocks belonging to an inode
+int ProcessInodeAllBlocks(ext2_filsys fs,
+                          blk_t* blocknr,
+                          e2_blkcnt_t blockcnt,
+                          blk_t ref_blk,
+                          int ref_offset,
+                          void* priv) {
+  vector<Extent>* extents = static_cast<vector<Extent>*>(priv);
+  graph_utils::AppendBlockToExtents(extents, *blocknr);
+  return 0;
+}
+
+// Processes only indirect, double indirect or triple indirect metadata
+// blocks belonging to an inode
+int ProcessInodeMetadataBlocks(ext2_filsys fs,
+                               blk_t* blocknr,
+                               e2_blkcnt_t blockcnt,
+                               blk_t ref_blk,
+                               int ref_offset,
+                               void* priv) {
+  vector<Extent>* extents = static_cast<vector<Extent>*>(priv);
+  if (blockcnt < 0) {
+    graph_utils::AppendBlockToExtents(extents, *blocknr);
+  }
+  return 0;
+}
+
+// Read inode metadata blocks.
+bool ReadInodeMetadata(Graph* graph,
+                       vector<Block>* blocks,
+                       const ext2_filsys fs_old,
+                       const ext2_filsys fs_new,
+                       int data_fd,
+                       off_t* data_file_size) {
+  TEST_AND_RETURN_FALSE_ERRCODE(ext2fs_read_inode_bitmap(fs_old));
+  TEST_AND_RETURN_FALSE_ERRCODE(ext2fs_read_inode_bitmap(fs_new));
+
+  ext2_inode_scan iscan;
+  TEST_AND_RETURN_FALSE_ERRCODE(ext2fs_open_inode_scan(fs_old, 0, &iscan));
+
+  ext2_ino_t ino;
+  ext2_inode old_inode;
+  while (true) {
+    // Get the next inode on both file systems
+    errcode_t error = ext2fs_get_next_inode(iscan, &ino, &old_inode);
+
+    // If we get an error enumerating the inodes, we'll just log the error
+    // and exit from our loop which will eventually return a success code
+    // back to the caller. The inode blocks that we cannot account for will
+    // be handled by DeltaDiffGenerator::ReadUnwrittenBlocks().
+    if (error) {
+      LOG(ERROR) << "Failed to retrieve next inode (" << error << ")";
+      break;
+    }
+
+    if (ino == 0) {
+      break;
+    }
+
+    if (ino == EXT2_RESIZE_INO) {
+      continue;
+    }
+
+    ext2_inode new_inode;
+    error = ext2fs_read_inode(fs_new, ino, &new_inode);
+    if (error) {
+      LOG(ERROR) << "Failed to retrieve new inode (" << error << ")";
+      continue;
+    }
+
+    // Skip inodes that are not in use
+    if (!ext2fs_test_inode_bitmap(fs_old->inode_map, ino)  ||
+        !ext2fs_test_inode_bitmap(fs_new->inode_map, ino)) {
+      continue;
+    }
+
+    // Skip inodes that have no data blocks
+    if (old_inode.i_blocks == 0 || new_inode.i_blocks == 0) {
+      continue;
+    }
+
+    // Skip inodes that are not the same type
+    bool is_old_dir = (ext2fs_check_directory(fs_old, ino) == 0);
+    bool is_new_dir = (ext2fs_check_directory(fs_new, ino) == 0);
+    if (is_old_dir != is_new_dir) {
+      continue;
+    }
+
+    // Process the inodes metadata blocks
+    // For normal files, metadata blocks are indirect, double indirect
+    // and triple indirect blocks (no data blocks). For directories and
+    // the journal, all blocks are considered metadata blocks.
+    LOG(INFO) << "Processing inode " << ino << " metadata";
+
+    bool all_blocks = ((ino == EXT2_JOURNAL_INO) || is_old_dir || is_new_dir);
+
+    vector<Extent> old_extents;
+    error = ext2fs_block_iterate2(fs_old, ino, 0, NULL,
+                                  all_blocks ? ProcessInodeAllBlocks :
+                                               ProcessInodeMetadataBlocks,
+                                  &old_extents);
+    if (error) {
+      LOG(ERROR) << "Failed to enumerate old inode " << ino
+                << " blocks (" << error << ")";
+      continue;
+    }
+
+    vector<Extent> new_extents;
+    error = ext2fs_block_iterate2(fs_new, ino, 0, NULL,
+                                  all_blocks ? ProcessInodeAllBlocks :
+                                               ProcessInodeMetadataBlocks,
+                                  &new_extents);
+    if (error) {
+      LOG(ERROR) << "Failed to enumerate new inode " << ino
+                << " blocks (" << error << ")";
+      continue;
+    }
+
+    // Skip inode if there are no metadata blocks
+    if (old_extents.size() == 0 || new_extents.size() == 0) {
+      continue;
+    }
+
+    // Make sure the two inodes have the same metadata blocks
+    if (old_extents.size() != new_extents.size()) {
+      continue;
+    }
+
+    bool same_metadata_extents = true;
+    vector<Extent>::iterator it_old;
+    vector<Extent>::iterator it_new;
+    for (it_old = old_extents.begin(),
+         it_new = new_extents.begin();
+         it_old != old_extents.end() && it_new != new_extents.end();
+         it_old++, it_new++) {
+      if (it_old->start_block() != it_new->start_block() ||
+          it_old->num_blocks() != it_new->num_blocks()) {
+            same_metadata_extents = false;
+            break;
+      }
+    }
+
+    if (!same_metadata_extents) {
+      continue;
+    }
+
+    // We have identical inode metadata blocks, we can now add them to
+    // our graph and blocks vector
+    string metadata_name = StringPrintf("<rootfs-inode-%d-metadata>", ino);
+    TEST_AND_RETURN_FALSE(AddMetadataExtents(graph,
+                                             blocks,
+                                             fs_old,
+                                             fs_new,
+                                             metadata_name,
+                                             old_extents,
+                                             data_fd,
+                                             data_file_size));
+  }
+
+  ext2fs_close_inode_scan(iscan);
+
+  return true;
+}
+
+}  // namespace {}
+
+// Reads metadata from old image and new image and determines
+// the smallest way to encode the metadata for the diff.
+// If there's no change in the metadata, it creates a MOVE
+// operation. If there is a change, the smallest of REPLACE, REPLACE_BZ,
+// or BSDIFF wins. It writes the diff to data_fd and updates data_file_size
+// accordingly. It also adds the required operation to the graph and adds the
+// metadata extents to blocks.
+// Returns true on success.
+bool Metadata::DeltaReadMetadata(Graph* graph,
+                                 vector<Block>* blocks,
+                                 const string& old_image,
+                                 const string& new_image,
+                                 int data_fd,
+                                 off_t* data_file_size) {
+  // Open the two file systems.
+  ext2_filsys fs_old;
+  TEST_AND_RETURN_FALSE_ERRCODE(ext2fs_open(old_image.c_str(), 0, 0, 0,
+                                            unix_io_manager, &fs_old));
+  ScopedExt2fsCloser fs_old_closer(fs_old);
+
+  ext2_filsys fs_new;
+  TEST_AND_RETURN_FALSE_ERRCODE(ext2fs_open(new_image.c_str(), 0, 0, 0,
+                                            unix_io_manager, &fs_new));
+  ScopedExt2fsCloser fs_new_closer(fs_new);
+
+  // Make sure these two file systems are the same.
+  // If they are not the same, the metadata blocks will be packaged up in its
+  // entirety by ReadUnwrittenBlocks().
+  if (fs_old->blocksize != fs_new->blocksize ||
+      fs_old->fragsize != fs_new->fragsize ||
+      fs_old->group_desc_count != fs_new->group_desc_count ||
+      fs_old->inode_blocks_per_group != fs_new->inode_blocks_per_group ||
+      fs_old->super->s_inodes_count != fs_new->super->s_inodes_count ||
+      fs_old->super->s_blocks_count != fs_new->super->s_blocks_count) {
+    return true;
+  }
+
+  // Process the main file system metadata (superblock, inode tables, etc)
+  TEST_AND_RETURN_FALSE(ReadFilesystemMetadata(graph,
+                                               blocks,
+                                               fs_old,
+                                               fs_new,
+                                               data_fd,
+                                               data_file_size));
+
+  // Process each inode metadata blocks.
+  TEST_AND_RETURN_FALSE(ReadInodeMetadata(graph,
+                                          blocks,
+                                          fs_old,
+                                          fs_new,
+                                          data_fd,
+                                          data_file_size));
+
+  return true;
+}
+
+};  // namespace chromeos_update_engine
diff --git a/payload_generator/metadata.h b/payload_generator/metadata.h
new file mode 100644
index 0000000..452e303
--- /dev/null
+++ b/payload_generator/metadata.h
@@ -0,0 +1,37 @@
+// 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 CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_METADATA_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_METADATA_H_
+
+#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/graph_types.h"
+
+namespace chromeos_update_engine {
+
+class Metadata {
+ public:
+  // Reads metadata from old image and new image and determines
+  // the smallest way to encode the metadata for the diff.
+  // If there's no change in the metadata, it creates a MOVE
+  // operation. If there is a change, the smallest of REPLACE, REPLACE_BZ,
+  // or BSDIFF wins. It writes the diff to data_fd and updates data_file_size
+  // accordingly. It also adds the required operation to the graph and adds the
+  // metadata extents to blocks.
+  // Returns true on success.
+  static bool DeltaReadMetadata(Graph* graph,
+                                std::vector<DeltaDiffGenerator::Block>* blocks,
+                                const std::string& old_image,
+                                const std::string& new_image,
+                                int data_fd,
+                                off_t* data_file_size);
+
+ private:
+  // This should never be constructed.
+  DISALLOW_IMPLICIT_CONSTRUCTORS(Metadata);
+};
+
+};  // namespace chromeos_update_engine
+
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_METADATA_H_
diff --git a/payload_generator/metadata_unittest.cc b/payload_generator/metadata_unittest.cc
new file mode 100644
index 0000000..39a2476
--- /dev/null
+++ b/payload_generator/metadata_unittest.cc
@@ -0,0 +1,171 @@
+// 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 <fcntl.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+
+#include <string>
+#include <vector>
+
+#include <base/strings/string_util.h>
+#include <base/strings/stringprintf.h>
+#include <gtest/gtest.h>
+
+#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/graph_types.h"
+#include "update_engine/payload_generator/metadata.h"
+#include "update_engine/test_utils.h"
+#include "update_engine/utils.h"
+
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+typedef DeltaDiffGenerator::Block Block;
+
+class MetadataTest : public ::testing::Test {
+};
+
+TEST_F(MetadataTest, RunAsRootReadMetadataDissimilarFileSystems) {
+  string a_img, b_img;
+  EXPECT_TRUE(utils::MakeTempFile("a_img.XXXXXX", &a_img, NULL));
+  ScopedPathUnlinker a_img_unlinker(a_img);
+  EXPECT_TRUE(utils::MakeTempFile("b_img.XXXXXX", &b_img, NULL));
+  ScopedPathUnlinker b_img_unlinker(b_img);
+
+  CreateEmptyExtImageAtPath(a_img, 10485759, 4096);
+  CreateEmptyExtImageAtPath(b_img, 11534336, 4096);
+
+  Graph graph;
+  vector<Block> blocks;
+  EXPECT_TRUE(Metadata::DeltaReadMetadata(&graph,
+                                          &blocks,
+                                          a_img,
+                                          b_img,
+                                          0,
+                                          NULL));
+  EXPECT_EQ(graph.size(), 0);
+
+  CreateEmptyExtImageAtPath(a_img, 10485759, 4096);
+  CreateEmptyExtImageAtPath(b_img, 10485759, 8192);
+
+  graph.clear();
+  blocks.clear();
+  EXPECT_TRUE(Metadata::DeltaReadMetadata(&graph,
+                                          &blocks,
+                                          a_img,
+                                          b_img,
+                                          0,
+                                          NULL));
+  EXPECT_EQ(graph.size(), 0);
+}
+
+TEST_F(MetadataTest, RunAsRootReadMetadata) {
+  string a_img, b_img, data_file;
+  EXPECT_TRUE(utils::MakeTempFile("a_img.XXXXXX", &a_img, NULL));
+  ScopedPathUnlinker a_img_unlinker(a_img);
+  EXPECT_TRUE(utils::MakeTempFile("b_img.XXXXXX", &b_img, NULL));
+  ScopedPathUnlinker b_img_unlinker(b_img);
+  EXPECT_TRUE(utils::MakeTempFile("data_file.XXXXXX", &data_file, NULL));
+  ScopedPathUnlinker data_file_unlinker(data_file);
+
+  const size_t image_size = (256 * 1024 * 1024);  // Enough for 2 block groups
+  const int block_size = 4096;
+  CreateEmptyExtImageAtPath(a_img, image_size, block_size);
+
+  // Create a file large enough to create an indirect block
+  {
+    string a_img_mnt;
+    ScopedLoopMounter a_img_mount(a_img, &a_img_mnt, 0);
+    System(base::StringPrintf("dd if=/dev/zero of=%s/test_file bs=%d count=%d",
+                              a_img_mnt.c_str(), block_size,
+                              EXT2_NDIR_BLOCKS + 1));
+  }
+
+  System(base::StringPrintf("cp %s %s", a_img.c_str(), b_img.c_str()));
+
+  int fd = open(data_file.c_str(), O_RDWR | O_CREAT, S_IRWXU);
+  EXPECT_NE(fd, -1);
+  ScopedFdCloser fd_closer(&fd);
+
+  Graph graph;
+  vector<Block> blocks(image_size / block_size);
+  off_t data_file_size;
+  EXPECT_TRUE(Metadata::DeltaReadMetadata(&graph,
+                                          &blocks,
+                                          a_img,
+                                          b_img,
+                                          fd,
+                                          &data_file_size));
+
+  // There are 12 metadata that we look for:
+  //   - Block group 0 metadata (superblock, group descriptor, bitmaps, etc)
+  //       - Chunk 0, 1, 2, 3
+  //   - Block group 1 metadata
+  //       - Chunk 0, 1, 2, 3
+  //   - Root directory (inode 2)
+  //   - Journal (inode 8)
+  //   - lost+found directory (inode 11)
+  //   - test_file indirect block (inode 12)
+  struct {
+    string metadata_name;
+    off_t start_block; // Set to -1 to skip start block verification
+    off_t num_blocks; // Set to -1 to skip num blocks verification
+  } exp_results[] =
+      {{"<rootfs-bg-0-0-metadata>", 0, 104},
+       {"<rootfs-bg-0-1-metadata>", 104, 104},
+       {"<rootfs-bg-0-2-metadata>", 208, 104},
+       {"<rootfs-bg-0-3-metadata>", 312, 104},
+       {"<rootfs-bg-0-4-metadata>", 416, 104},
+       {"<rootfs-bg-0-5-metadata>", 520, 104},
+       {"<rootfs-bg-0-6-metadata>", 624, 104},
+       {"<rootfs-bg-0-7-metadata>", 728, 104},
+       {"<rootfs-bg-0-8-metadata>", 832, 104},
+       {"<rootfs-bg-0-9-metadata>", 936, 107},
+       {"<rootfs-bg-1-0-metadata>", 32768, 104},
+       {"<rootfs-bg-1-1-metadata>", 32872, 104},
+       {"<rootfs-bg-1-2-metadata>", 32976, 104},
+       {"<rootfs-bg-1-3-metadata>", 33080, 104},
+       {"<rootfs-bg-1-4-metadata>", 33184, 104},
+       {"<rootfs-bg-1-5-metadata>", 33288, 104},
+       {"<rootfs-bg-1-6-metadata>", 33392, 104},
+       {"<rootfs-bg-1-7-metadata>", 33496, 104},
+       {"<rootfs-bg-1-8-metadata>", 33600, 104},
+       {"<rootfs-bg-1-9-metadata>", 33704, 107},
+       {"<rootfs-inode-2-metadata>", -1, 1},
+       {"<rootfs-inode-8-metadata>", -1, 4101},
+       {"<rootfs-inode-11-metadata>", -1, 4},
+       {"<rootfs-inode-12-metadata>", -1, 1}};
+
+  int num_exp_results = sizeof(exp_results) / sizeof(exp_results[0]);
+  EXPECT_EQ(graph.size(), num_exp_results);
+
+  for (int i = 0; i < num_exp_results; i++) {
+    Vertex& vertex = graph[i];
+    DeltaArchiveManifest_InstallOperation& op = vertex.op;
+
+    EXPECT_STRCASEEQ(vertex.file_name.c_str(),
+                     exp_results[i].metadata_name.c_str());
+
+    EXPECT_EQ(op.src_extents().size(), op.dst_extents().size());
+    for (int e = 0; e < op.src_extents().size(); e++) {
+      EXPECT_EQ(op.src_extents(e).start_block(),
+                op.dst_extents(e).start_block());
+      EXPECT_EQ(op.src_extents(e).num_blocks(),
+                op.dst_extents(e).num_blocks());
+    }
+
+    if (exp_results[i].start_block != -1) {
+      EXPECT_EQ(op.src_extents(0).start_block(), exp_results[i].start_block);
+    }
+
+    if (exp_results[i].num_blocks != -1) {
+      EXPECT_EQ(op.src_extents(0).num_blocks(), exp_results[i].num_blocks);
+    }
+  }
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/tarjan.cc b/payload_generator/tarjan.cc
new file mode 100644
index 0000000..f3029c1
--- /dev/null
+++ b/payload_generator/tarjan.cc
@@ -0,0 +1,71 @@
+// 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/tarjan.h"
+
+#include <algorithm>
+#include <vector>
+
+#include <base/logging.h>
+
+#include "update_engine/utils.h"
+
+using std::min;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+const vector<Vertex>::size_type kInvalidIndex = -1;
+}
+
+void TarjanAlgorithm::Execute(Vertex::Index vertex,
+                              Graph* graph,
+                              vector<Vertex::Index>* out) {
+  stack_.clear();
+  components_.clear();
+  index_ = 0;
+  for (Graph::iterator it = graph->begin(); it != graph->end(); ++it)
+    it->index = it->lowlink = kInvalidIndex;
+  required_vertex_ = vertex;
+
+  Tarjan(vertex, graph);
+  if (!components_.empty())
+    out->swap(components_[0]);
+}
+
+void TarjanAlgorithm::Tarjan(Vertex::Index vertex, Graph* graph) {
+  CHECK_EQ((*graph)[vertex].index, kInvalidIndex);
+  (*graph)[vertex].index = index_;
+  (*graph)[vertex].lowlink = index_;
+  index_++;
+  stack_.push_back(vertex);
+  for (Vertex::EdgeMap::iterator it = (*graph)[vertex].out_edges.begin();
+       it != (*graph)[vertex].out_edges.end(); ++it) {
+    Vertex::Index vertex_next = it->first;
+    if ((*graph)[vertex_next].index == kInvalidIndex) {
+      Tarjan(vertex_next, graph);
+      (*graph)[vertex].lowlink = min((*graph)[vertex].lowlink,
+                                     (*graph)[vertex_next].lowlink);
+    } else if (utils::VectorContainsValue(stack_, vertex_next)) {
+      (*graph)[vertex].lowlink = min((*graph)[vertex].lowlink,
+                                     (*graph)[vertex_next].index);
+    }
+  }
+  if ((*graph)[vertex].lowlink == (*graph)[vertex].index) {
+    vector<Vertex::Index> component;
+    Vertex::Index other_vertex;
+    do {
+      other_vertex = stack_.back();
+      stack_.pop_back();
+      component.push_back(other_vertex);
+    } while (other_vertex != vertex && !stack_.empty());
+
+    if (utils::VectorContainsValue(component, required_vertex_)) {
+      components_.resize(components_.size() + 1);
+      component.swap(components_.back());
+    }
+  }
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/tarjan.h b/payload_generator/tarjan.h
new file mode 100644
index 0000000..544cee3
--- /dev/null
+++ b/payload_generator/tarjan.h
@@ -0,0 +1,40 @@
+// 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 CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_TARJAN_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_TARJAN_H_
+
+// This is an implemenation of Tarjan's algorithm which finds all
+// Strongly Connected Components in a graph.
+
+// Note: a true Tarjan algorithm would find all strongly connected components
+// in the graph. This implementation will only find the strongly connected
+// component containing the vertex passed in.
+
+#include <vector>
+
+#include "update_engine/payload_generator/graph_types.h"
+
+namespace chromeos_update_engine {
+
+class TarjanAlgorithm {
+ public:
+  TarjanAlgorithm() : index_(0), required_vertex_(0) {}
+
+  // 'out' is set to the result if there is one, otherwise it's untouched.
+  void Execute(Vertex::Index vertex,
+               Graph* graph,
+               std::vector<Vertex::Index>* out);
+ private:
+  void Tarjan(Vertex::Index vertex, Graph* graph);
+
+  Vertex::Index index_;
+  Vertex::Index required_vertex_;
+  std::vector<Vertex::Index> stack_;
+  std::vector<std::vector<Vertex::Index> > components_;
+};
+
+}  // namespace chromeos_update_engine
+
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_TARJAN_H_
diff --git a/payload_generator/tarjan_unittest.cc b/payload_generator/tarjan_unittest.cc
new file mode 100644
index 0000000..a5fbac2
--- /dev/null
+++ b/payload_generator/tarjan_unittest.cc
@@ -0,0 +1,83 @@
+// 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/tarjan.h"
+
+#include <utility>
+
+#include <base/logging.h>
+#include <gtest/gtest.h>
+
+#include "update_engine/payload_generator/graph_types.h"
+#include "update_engine/utils.h"
+
+using std::make_pair;
+using std::pair;
+using std::set;
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+class TarjanAlgorithmTest : public ::testing::Test {};
+
+TEST(TarjanAlgorithmTest, SimpleTest) {
+  const Vertex::Index n_a = 0;
+  const Vertex::Index n_b = 1;
+  const Vertex::Index n_c = 2;
+  const Vertex::Index n_d = 3;
+  const Vertex::Index n_e = 4;
+  const Vertex::Index n_f = 5;
+  const Vertex::Index n_g = 6;
+  const Vertex::Index n_h = 7;
+  const Graph::size_type kNodeCount = 8;
+
+  Graph graph(kNodeCount);
+
+  graph[n_a].out_edges.insert(make_pair(n_e, EdgeProperties()));
+  graph[n_a].out_edges.insert(make_pair(n_f, EdgeProperties()));
+  graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties()));
+  graph[n_c].out_edges.insert(make_pair(n_d, EdgeProperties()));
+  graph[n_d].out_edges.insert(make_pair(n_e, EdgeProperties()));
+  graph[n_d].out_edges.insert(make_pair(n_f, EdgeProperties()));
+  graph[n_e].out_edges.insert(make_pair(n_b, EdgeProperties()));
+  graph[n_e].out_edges.insert(make_pair(n_c, EdgeProperties()));
+  graph[n_e].out_edges.insert(make_pair(n_f, EdgeProperties()));
+  graph[n_f].out_edges.insert(make_pair(n_g, EdgeProperties()));
+  graph[n_g].out_edges.insert(make_pair(n_h, EdgeProperties()));
+  graph[n_h].out_edges.insert(make_pair(n_g, EdgeProperties()));
+
+  TarjanAlgorithm tarjan;
+
+  for (Vertex::Index i = n_a; i <= n_e; i++) {
+    vector<Vertex::Index> vertex_indexes;
+    tarjan.Execute(i, &graph, &vertex_indexes);
+
+    EXPECT_EQ(5, vertex_indexes.size());
+    EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_a));
+    EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_b));
+    EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_c));
+    EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_d));
+    EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_e));
+  }
+
+  {
+    vector<Vertex::Index> vertex_indexes;
+    tarjan.Execute(n_f, &graph, &vertex_indexes);
+
+    EXPECT_EQ(1, vertex_indexes.size());
+    EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_f));
+  }
+
+  for (Vertex::Index i = n_g; i <= n_h; i++) {
+    vector<Vertex::Index> vertex_indexes;
+    tarjan.Execute(i, &graph, &vertex_indexes);
+
+    EXPECT_EQ(2, vertex_indexes.size());
+    EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_g));
+    EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_h));
+  }
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/topological_sort.cc b/payload_generator/topological_sort.cc
new file mode 100644
index 0000000..3ee8c75
--- /dev/null
+++ b/payload_generator/topological_sort.cc
@@ -0,0 +1,44 @@
+// 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/topological_sort.h"
+
+#include <set>
+#include <vector>
+
+#include <base/logging.h>
+
+using std::set;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+void TopologicalSortVisit(const Graph& graph,
+                          set<Vertex::Index>* visited_nodes,
+                          vector<Vertex::Index>* nodes,
+                          Vertex::Index node) {
+  if (visited_nodes->find(node) != visited_nodes->end())
+    return;
+
+  visited_nodes->insert(node);
+  // Visit all children.
+  for (Vertex::EdgeMap::const_iterator it = graph[node].out_edges.begin();
+       it != graph[node].out_edges.end(); ++it) {
+    TopologicalSortVisit(graph, visited_nodes, nodes, it->first);
+  }
+  // Visit this node.
+  nodes->push_back(node);
+}
+}  // namespace {}
+
+void TopologicalSort(const Graph& graph, vector<Vertex::Index>* out) {
+  set<Vertex::Index> visited_nodes;
+
+  for (Vertex::Index i = 0; i < graph.size(); i++) {
+    TopologicalSortVisit(graph, &visited_nodes, out, i);
+  }
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/topological_sort.h b/payload_generator/topological_sort.h
new file mode 100644
index 0000000..be130ce
--- /dev/null
+++ b/payload_generator/topological_sort.h
@@ -0,0 +1,30 @@
+// 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 CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_TOPOLOGICAL_SORT_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_TOPOLOGICAL_SORT_H_
+
+#include <vector>
+
+#include "update_engine/payload_generator/graph_types.h"
+
+namespace chromeos_update_engine {
+
+// Performs a topological sort on the directed graph 'graph' and stores
+// the nodes, in order visited, in 'out'.
+// For example, this graph:
+// A ---> C ----.
+//  \           v
+//   `--> B --> D
+// Might result in this in 'out':
+// out[0] = D
+// out[1] = B
+// out[2] = C
+// out[3] = A
+// Note: results are undefined if there is a cycle in the graph.
+void TopologicalSort(const Graph& graph, std::vector<Vertex::Index>* out);
+
+}  // namespace chromeos_update_engine
+
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_TOPOLOGICAL_SORT_H_
diff --git a/payload_generator/topological_sort_unittest.cc b/payload_generator/topological_sort_unittest.cc
new file mode 100644
index 0000000..696fd5b
--- /dev/null
+++ b/payload_generator/topological_sort_unittest.cc
@@ -0,0 +1,82 @@
+// 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 <utility>
+#include <vector>
+
+#include <gtest/gtest.h>
+
+#include "update_engine/payload_generator/graph_types.h"
+#include "update_engine/payload_generator/topological_sort.h"
+
+using std::make_pair;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+class TopologicalSortTest : public ::testing::Test {};
+
+namespace {
+// Returns true if the value is found in vect. If found, the index is stored
+// in out_index if out_index is not null.
+template<typename T>
+bool IndexOf(const vector<T>& vect,
+             const T& value,
+             typename vector<T>::size_type* out_index) {
+  for (typename vector<T>::size_type i = 0; i < vect.size(); i++) {
+    if (vect[i] == value) {
+      if (out_index) {
+        *out_index = i;
+      }
+      return true;
+    }
+  }
+  return false;
+}
+}  // namespace {}
+
+TEST(TopologicalSortTest, SimpleTest) {
+  int counter = 0;
+  const Vertex::Index n_a = counter++;
+  const Vertex::Index n_b = counter++;
+  const Vertex::Index n_c = counter++;
+  const Vertex::Index n_d = counter++;
+  const Vertex::Index n_e = counter++;
+  const Vertex::Index n_f = counter++;
+  const Vertex::Index n_g = counter++;
+  const Vertex::Index n_h = counter++;
+  const Vertex::Index n_i = counter++;
+  const Vertex::Index n_j = counter++;
+  const Graph::size_type kNodeCount = counter++;
+
+  Graph graph(kNodeCount);
+
+  graph[n_i].out_edges.insert(make_pair(n_j, EdgeProperties()));
+  graph[n_i].out_edges.insert(make_pair(n_c, EdgeProperties()));
+  graph[n_i].out_edges.insert(make_pair(n_e, EdgeProperties()));
+  graph[n_i].out_edges.insert(make_pair(n_h, EdgeProperties()));
+  graph[n_c].out_edges.insert(make_pair(n_b, EdgeProperties()));
+  graph[n_b].out_edges.insert(make_pair(n_a, EdgeProperties()));
+  graph[n_e].out_edges.insert(make_pair(n_d, EdgeProperties()));
+  graph[n_e].out_edges.insert(make_pair(n_g, EdgeProperties()));
+  graph[n_g].out_edges.insert(make_pair(n_d, EdgeProperties()));
+  graph[n_g].out_edges.insert(make_pair(n_f, EdgeProperties()));
+  graph[n_d].out_edges.insert(make_pair(n_a, EdgeProperties()));
+
+  vector<Vertex::Index> sorted;
+  TopologicalSort(graph, &sorted);
+
+  for (Vertex::Index i = 0; i < graph.size(); i++) {
+    vector<Vertex::Index>::size_type src_index = 0;
+    EXPECT_TRUE(IndexOf(sorted, i, &src_index));
+    for (Vertex::EdgeMap::const_iterator it = graph[i].out_edges.begin();
+         it != graph[i].out_edges.end(); ++it) {
+      vector<Vertex::Index>::size_type dst_index = 0;
+      EXPECT_TRUE(IndexOf(sorted, it->first, &dst_index));
+      EXPECT_LT(dst_index, src_index);
+    }
+  }
+}
+
+}  // namespace chromeos_update_engine