diff --git a/payload_generator/ab_generator_unittest.cc b/payload_generator/ab_generator_unittest.cc
index 270657a..7a95284 100644
--- a/payload_generator/ab_generator_unittest.cc
+++ b/payload_generator/ab_generator_unittest.cc
@@ -30,10 +30,10 @@
 #include "update_engine/common/test_utils.h"
 #include "update_engine/common/utils.h"
 #include "update_engine/payload_generator/annotated_operation.h"
-#include "update_engine/payload_generator/bzip.h"
 #include "update_engine/payload_generator/delta_diff_generator.h"
 #include "update_engine/payload_generator/extent_ranges.h"
 #include "update_engine/payload_generator/extent_utils.h"
+#include "update_engine/payload_generator/xz.h"
 
 using std::string;
 using std::vector;
@@ -48,8 +48,8 @@
   return ext.start_block() == start_block && ext.num_blocks() == num_blocks;
 }
 
-// Tests splitting of a REPLACE/REPLACE_BZ operation.
-void TestSplitReplaceOrReplaceBzOperation(InstallOperation::Type orig_type,
+// Tests splitting of a REPLACE/REPLACE_XZ operation.
+void TestSplitReplaceOrReplaceXzOperation(InstallOperation::Type orig_type,
                                           bool compressible) {
   const size_t op_ex1_start_block = 2;
   const size_t op_ex1_num_blocks = 2;
@@ -71,7 +71,7 @@
   }
   ASSERT_EQ(part_size, part_data.size());
   test_utils::ScopedTempFile part_file(
-      "SplitReplaceOrReplaceBzTest_part.XXXXXX");
+      "SplitReplaceOrReplaceXzTest_part.XXXXXX");
   ASSERT_TRUE(test_utils::WriteFileVector(part_file.path(), part_data));
 
   // Create original operation and blob data.
@@ -97,7 +97,7 @@
   if (orig_type == InstallOperation::REPLACE) {
     op_blob = op_data;
   } else {
-    ASSERT_TRUE(BzipCompress(op_data, &op_blob));
+    ASSERT_TRUE(XzCompress(op_data, &op_blob));
   }
   op.set_data_offset(0);
   op.set_data_length(op_blob.size());
@@ -108,7 +108,7 @@
 
   // Create the data file.
   test_utils::ScopedTempFile data_file(
-      "SplitReplaceOrReplaceBzTest_data.XXXXXX");
+      "SplitReplaceOrReplaceXzTest_data.XXXXXX");
   EXPECT_TRUE(test_utils::WriteFileVector(data_file.path(), op_blob));
   int data_fd = open(data_file.path().c_str(), O_RDWR, 000);
   EXPECT_GE(data_fd, 0);
@@ -118,14 +118,14 @@
 
   // Split the operation.
   vector<AnnotatedOperation> result_ops;
-  PayloadVersion version(kChromeOSMajorPayloadVersion,
+  PayloadVersion version(kBrilloMajorPayloadVersion,
                          kSourceMinorPayloadVersion);
   ASSERT_TRUE(ABGenerator::SplitAReplaceOp(
       version, aop, part_file.path(), &result_ops, &blob_file));
 
   // Check the result.
   InstallOperation::Type expected_type =
-      compressible ? InstallOperation::REPLACE_BZ : InstallOperation::REPLACE;
+      compressible ? InstallOperation::REPLACE_XZ : InstallOperation::REPLACE;
 
   ASSERT_EQ(2U, result_ops.size());
 
@@ -143,7 +143,7 @@
       part_data.begin() + op_ex1_offset + op_ex1_size);
   brillo::Blob first_expected_blob;
   if (compressible) {
-    ASSERT_TRUE(BzipCompress(first_expected_data, &first_expected_blob));
+    ASSERT_TRUE(XzCompress(first_expected_data, &first_expected_blob));
   } else {
     first_expected_blob = first_expected_data;
   }
@@ -173,7 +173,7 @@
       part_data.begin() + op_ex2_offset + op_ex2_size);
   brillo::Blob second_expected_blob;
   if (compressible) {
-    ASSERT_TRUE(BzipCompress(second_expected_data, &second_expected_blob));
+    ASSERT_TRUE(XzCompress(second_expected_data, &second_expected_blob));
   } else {
     second_expected_blob = second_expected_data;
   }
@@ -199,8 +199,8 @@
   }
 }
 
-// Tests merging of REPLACE/REPLACE_BZ operations.
-void TestMergeReplaceOrReplaceBzOperations(InstallOperation::Type orig_type,
+// Tests merging of REPLACE/REPLACE_XZ operations.
+void TestMergeReplaceOrReplaceXzOperations(InstallOperation::Type orig_type,
                                            bool compressible) {
   const size_t first_op_num_blocks = 1;
   const size_t second_op_num_blocks = 2;
@@ -221,7 +221,7 @@
   }
   ASSERT_EQ(part_size, part_data.size());
   test_utils::ScopedTempFile part_file(
-      "MergeReplaceOrReplaceBzTest_part.XXXXXX");
+      "MergeReplaceOrReplaceXzTest_part.XXXXXX");
   ASSERT_TRUE(test_utils::WriteFileVector(part_file.path(), part_data));
 
   // Create original operations and blob data.
@@ -239,7 +239,7 @@
   if (orig_type == InstallOperation::REPLACE) {
     first_op_blob = first_op_data;
   } else {
-    ASSERT_TRUE(BzipCompress(first_op_data, &first_op_blob));
+    ASSERT_TRUE(XzCompress(first_op_data, &first_op_blob));
   }
   first_op.set_data_offset(0);
   first_op.set_data_length(first_op_blob.size());
@@ -259,7 +259,7 @@
   if (orig_type == InstallOperation::REPLACE) {
     second_op_blob = second_op_data;
   } else {
-    ASSERT_TRUE(BzipCompress(second_op_data, &second_op_blob));
+    ASSERT_TRUE(XzCompress(second_op_data, &second_op_blob));
   }
   second_op.set_data_offset(first_op_blob.size());
   second_op.set_data_length(second_op_blob.size());
@@ -272,7 +272,7 @@
 
   // Create the data file.
   test_utils::ScopedTempFile data_file(
-      "MergeReplaceOrReplaceBzTest_data.XXXXXX");
+      "MergeReplaceOrReplaceXzTest_data.XXXXXX");
   EXPECT_TRUE(test_utils::WriteFileVector(data_file.path(), blob_data));
   int data_fd = open(data_file.path().c_str(), O_RDWR, 000);
   EXPECT_GE(data_fd, 0);
@@ -281,14 +281,14 @@
   BlobFileWriter blob_file(data_fd, &data_file_size);
 
   // Merge the operations.
-  PayloadVersion version(kChromeOSMajorPayloadVersion,
+  PayloadVersion version(kBrilloMajorPayloadVersion,
                          kSourceMinorPayloadVersion);
   EXPECT_TRUE(ABGenerator::MergeOperations(
       &aops, version, 5, part_file.path(), &blob_file));
 
   // Check the result.
   InstallOperation::Type expected_op_type =
-      compressible ? InstallOperation::REPLACE_BZ : InstallOperation::REPLACE;
+      compressible ? InstallOperation::REPLACE_XZ : InstallOperation::REPLACE;
   EXPECT_EQ(1U, aops.size());
   InstallOperation new_op = aops[0].op;
   EXPECT_EQ(expected_op_type, new_op.type());
@@ -303,7 +303,7 @@
                              part_data.begin() + total_op_size);
   brillo::Blob expected_blob;
   if (compressible) {
-    ASSERT_TRUE(BzipCompress(expected_data, &expected_blob));
+    ASSERT_TRUE(XzCompress(expected_data, &expected_blob));
   } else {
     expected_blob = expected_data;
   }
@@ -384,19 +384,19 @@
 }
 
 TEST_F(ABGeneratorTest, SplitReplaceTest) {
-  TestSplitReplaceOrReplaceBzOperation(InstallOperation::REPLACE, false);
+  TestSplitReplaceOrReplaceXzOperation(InstallOperation::REPLACE, false);
 }
 
-TEST_F(ABGeneratorTest, SplitReplaceIntoReplaceBzTest) {
-  TestSplitReplaceOrReplaceBzOperation(InstallOperation::REPLACE, true);
+TEST_F(ABGeneratorTest, SplitReplaceIntoReplaceXzTest) {
+  TestSplitReplaceOrReplaceXzOperation(InstallOperation::REPLACE, true);
 }
 
-TEST_F(ABGeneratorTest, SplitReplaceBzTest) {
-  TestSplitReplaceOrReplaceBzOperation(InstallOperation::REPLACE_BZ, true);
+TEST_F(ABGeneratorTest, SplitReplaceXzTest) {
+  TestSplitReplaceOrReplaceXzOperation(InstallOperation::REPLACE_XZ, true);
 }
 
-TEST_F(ABGeneratorTest, SplitReplaceBzIntoReplaceTest) {
-  TestSplitReplaceOrReplaceBzOperation(InstallOperation::REPLACE_BZ, false);
+TEST_F(ABGeneratorTest, SplitReplaceXzIntoReplaceTest) {
+  TestSplitReplaceOrReplaceXzOperation(InstallOperation::REPLACE_XZ, false);
 }
 
 TEST_F(ABGeneratorTest, SortOperationsByDestinationTest) {
@@ -464,7 +464,7 @@
   aops.push_back(third_aop);
 
   BlobFileWriter blob_file(0, nullptr);
-  PayloadVersion version(kChromeOSMajorPayloadVersion,
+  PayloadVersion version(kBrilloMajorPayloadVersion,
                          kSourceMinorPayloadVersion);
   EXPECT_TRUE(ABGenerator::MergeOperations(&aops, version, 5, "", &blob_file));
 
@@ -484,19 +484,19 @@
 }
 
 TEST_F(ABGeneratorTest, MergeReplaceOperationsTest) {
-  TestMergeReplaceOrReplaceBzOperations(InstallOperation::REPLACE, false);
+  TestMergeReplaceOrReplaceXzOperations(InstallOperation::REPLACE, false);
 }
 
-TEST_F(ABGeneratorTest, MergeReplaceOperationsToReplaceBzTest) {
-  TestMergeReplaceOrReplaceBzOperations(InstallOperation::REPLACE, true);
+TEST_F(ABGeneratorTest, MergeReplaceOperationsToReplaceXzTest) {
+  TestMergeReplaceOrReplaceXzOperations(InstallOperation::REPLACE, true);
 }
 
-TEST_F(ABGeneratorTest, MergeReplaceBzOperationsTest) {
-  TestMergeReplaceOrReplaceBzOperations(InstallOperation::REPLACE_BZ, true);
+TEST_F(ABGeneratorTest, MergeReplaceXzOperationsTest) {
+  TestMergeReplaceOrReplaceXzOperations(InstallOperation::REPLACE_XZ, true);
 }
 
-TEST_F(ABGeneratorTest, MergeReplaceBzOperationsToReplaceTest) {
-  TestMergeReplaceOrReplaceBzOperations(InstallOperation::REPLACE_BZ, false);
+TEST_F(ABGeneratorTest, MergeReplaceXzOperationsToReplaceTest) {
+  TestMergeReplaceOrReplaceXzOperations(InstallOperation::REPLACE_XZ, false);
 }
 
 TEST_F(ABGeneratorTest, NoMergeOperationsTest) {
@@ -537,7 +537,7 @@
   aops.push_back(fourth_aop);
 
   BlobFileWriter blob_file(0, nullptr);
-  PayloadVersion version(kChromeOSMajorPayloadVersion,
+  PayloadVersion version(kBrilloMajorPayloadVersion,
                          kSourceMinorPayloadVersion);
   EXPECT_TRUE(ABGenerator::MergeOperations(&aops, version, 4, "", &blob_file));
 
diff --git a/payload_generator/cycle_breaker.cc b/payload_generator/cycle_breaker.cc
deleted file mode 100644
index d6eeed2..0000000
--- a/payload_generator/cycle_breaker.cc
+++ /dev/null
@@ -1,218 +0,0 @@
-//
-// Copyright (C) 2012 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//      http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#include "update_engine/payload_generator/cycle_breaker.h"
-
-#include <inttypes.h>
-
-#include <limits>
-#include <set>
-#include <string>
-#include <utility>
-
-#include <base/stl_util.h>
-#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"
-
-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++) {
-    InstallOperation::Type op_type = graph[i].aop.op.type();
-    if (op_type == InstallOperation::REPLACE ||
-        op_type == InstallOperation::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 (base::ContainsKey(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<vector<Vertex::Index>::size_type>(2));
-  Edge min_edge = make_pair(stack_[0], stack_[1]);
-  uint64_t min_edge_weight = std::numeric_limits<uint64_t>::max();
-  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 (vector<Vertex::Index>::const_iterator it = ++stack_.begin(),
-                                             e = stack_.end();
-       it != e;
-       ++it) {
-    Edge edge = make_pair(*(it - 1), *it);
-    if (base::ContainsKey(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 (Vertex::Index index : stack_) {
-        stack_str += std::to_string(index);
-        stack_str += " -> ";
-      }
-      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
deleted file mode 100644
index 01518fe..0000000
--- a/payload_generator/cycle_breaker.h
+++ /dev/null
@@ -1,71 +0,0 @@
-//
-// Copyright (C) 2010 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//      http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_CYCLE_BREAKER_H_
-#define 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  // UPDATE_ENGINE_PAYLOAD_GENERATOR_CYCLE_BREAKER_H_
diff --git a/payload_generator/cycle_breaker_unittest.cc b/payload_generator/cycle_breaker_unittest.cc
deleted file mode 100644
index fdcf49b..0000000
--- a/payload_generator/cycle_breaker_unittest.cc
+++ /dev/null
@@ -1,279 +0,0 @@
-//
-// Copyright (C) 2010 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//      http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#include "update_engine/payload_generator/cycle_breaker.h"
-
-#include <set>
-#include <string>
-#include <utility>
-#include <vector>
-
-#include <base/logging.h>
-#include <base/stl_util.h>
-#include <gtest/gtest.h>
-
-#include "update_engine/payload_generator/graph_types.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 (Vertex& vertex : *graph) {
-    vertex.aop.op.set_type(InstallOperation::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(base::ContainsKey(broken_edges, make_pair(n_a, n_e)) ||
-              base::ContainsKey(broken_edges, make_pair(n_e, n_b)) ||
-              base::ContainsKey(broken_edges, make_pair(n_b, n_a)));
-  EXPECT_TRUE(base::ContainsKey(broken_edges, make_pair(n_c, n_d)) ||
-              base::ContainsKey(broken_edges, make_pair(n_d, n_e)) ||
-              base::ContainsKey(broken_edges, make_pair(n_e, n_c)));
-  EXPECT_TRUE(base::ContainsKey(broken_edges, make_pair(n_g, n_h)) ||
-              base::ContainsKey(broken_edges, make_pair(n_h, n_g)));
-  EXPECT_EQ(3U, 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) {
-  size_t 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) {
-  size_t 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(base::ContainsKey(broken_edges, make_pair(n_b, n_a)));
-  EXPECT_TRUE(base::ContainsKey(broken_edges, make_pair(n_b, n_c)));
-  EXPECT_TRUE(base::ContainsKey(broken_edges, make_pair(n_d, n_e)));
-  EXPECT_TRUE(base::ContainsKey(broken_edges, make_pair(n_f, n_g)));
-  EXPECT_TRUE(base::ContainsKey(broken_edges, make_pair(n_h, n_i)));
-}
-
-TEST(CycleBreakerTest, UnblockGraphTest) {
-  size_t 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(base::ContainsKey(broken_edges, make_pair(n_a, n_b)));
-  EXPECT_TRUE(base::ContainsKey(broken_edges, make_pair(n_a, n_c)));
-}
-
-TEST(CycleBreakerTest, SkipOpsTest) {
-  size_t 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].aop.op.set_type(InstallOperation::REPLACE_BZ);
-  graph[n_c].aop.op.set_type(InstallOperation::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(2U, breaker.skipped_ops());
-}
-
-}  // namespace chromeos_update_engine
diff --git a/payload_generator/deflate_utils.cc b/payload_generator/deflate_utils.cc
index 01402dd..c874bfd 100644
--- a/payload_generator/deflate_utils.cc
+++ b/payload_generator/deflate_utils.cc
@@ -46,7 +46,7 @@
 // TODO(*): Optimize this so we don't have to read all extents into memory in
 // case it is large.
 bool CopyExtentsToFile(const string& in_path,
-                       const vector<Extent> extents,
+                       const vector<Extent>& extents,
                        const string& out_path,
                        size_t block_size) {
   brillo::Blob data(utils::BlocksInExtents(extents) * block_size);
@@ -284,8 +284,9 @@
       TEST_AND_RETURN_FALSE(
           CopyExtentsToFile(part.path, file.extents, path.value(), kBlockSize));
       // Test if it is actually a Squashfs file.
-      auto sqfs =
-          SquashfsFilesystem::CreateFromFile(path.value(), extract_deflates);
+      auto sqfs = SquashfsFilesystem::CreateFromFile(path.value(),
+                                                     extract_deflates,
+                                                     /*load_settings=*/false);
       if (sqfs) {
         // It is an squashfs file. Get its files to replace with itself.
         vector<FilesystemInterface::File> files;
@@ -306,7 +307,7 @@
       }
     }
 
-    if (is_regular_file && extract_deflates) {
+    if (is_regular_file && extract_deflates && !file.is_compressed) {
       // Search for deflates if the file is in zip or gzip format.
       // .zvoice files may eventually move out of rootfs. If that happens,
       // remove ".zvoice" (crbug.com/782918).
diff --git a/payload_generator/delta_diff_generator.cc b/payload_generator/delta_diff_generator.cc
index d484d32..595a41e 100644
--- a/payload_generator/delta_diff_generator.cc
+++ b/payload_generator/delta_diff_generator.cc
@@ -37,7 +37,6 @@
 #include "update_engine/payload_generator/blob_file_writer.h"
 #include "update_engine/payload_generator/delta_diff_utils.h"
 #include "update_engine/payload_generator/full_update_generator.h"
-#include "update_engine/payload_generator/inplace_generator.h"
 #include "update_engine/payload_generator/payload_file.h"
 
 using std::string;
@@ -93,13 +92,8 @@
       unique_ptr<OperationsGenerator> strategy;
       if (!old_part.path.empty()) {
         // Delta update.
-        if (config.version.minor == kInPlaceMinorPayloadVersion) {
-          LOG(INFO) << "Using generator InplaceGenerator().";
-          strategy.reset(new InplaceGenerator());
-        } else {
-          LOG(INFO) << "Using generator ABGenerator().";
-          strategy.reset(new ABGenerator());
-        }
+        LOG(INFO) << "Using generator ABGenerator().";
+        strategy.reset(new ABGenerator());
       } else {
         LOG(INFO) << "Using generator FullUpdateGenerator().";
         strategy.reset(new FullUpdateGenerator());
@@ -110,11 +104,6 @@
       TEST_AND_RETURN_FALSE(strategy->GenerateOperations(
           config, old_part, new_part, &blob_file, &aops));
 
-      // Filter the no-operations. OperationsGenerators should not output this
-      // kind of operations normally, but this is an extra step to fix that if
-      // happened.
-      diff_utils::FilterNoopOperations(&aops);
-
       TEST_AND_RETURN_FALSE(payload.AddPartition(old_part, new_part, aops));
     }
   }
diff --git a/payload_generator/delta_diff_utils.cc b/payload_generator/delta_diff_utils.cc
index 4ba6e24..22752e8 100644
--- a/payload_generator/delta_diff_utils.cc
+++ b/payload_generator/delta_diff_utils.cc
@@ -83,103 +83,6 @@
 
 const int kBrotliCompressionQuality = 11;
 
-// 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;
-  size_t removed_bytes = 0, nonfull_block_bytes;
-  bool do_remove = false;
-  while (src_idx < src_extents->size() && dst_idx < dst_extents->size()) {
-    do_remove = ((*src_extents)[src_idx].start_block() + src_offset ==
-                 (*dst_extents)[dst_idx].start_block() + dst_offset);
-
-    uint64_t src_num_blocks = (*src_extents)[src_idx].num_blocks();
-    uint64_t dst_num_blocks = (*dst_extents)[dst_idx].num_blocks();
-    uint64_t min_num_blocks =
-        std::min(src_num_blocks - src_offset, dst_num_blocks - dst_offset);
-    uint64_t prev_src_offset = src_offset;
-    uint64_t prev_dst_offset = dst_offset;
-    src_offset += min_num_blocks;
-    dst_offset += min_num_blocks;
-
-    bool new_src = ProcessExtentBlockRange(
-        src_extents, &src_idx, do_remove, prev_src_offset, src_offset);
-    bool new_dst = ProcessExtentBlockRange(
-        dst_extents, &dst_idx, do_remove, prev_dst_offset, dst_offset);
-    if (new_src) {
-      src_offset = 0;
-    }
-    if (new_dst) {
-      dst_offset = 0;
-    }
-
-    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;
-}
-
 // Storing a diff operation has more overhead over replace operation in the
 // manifest, we need to store an additional src_sha256_hash which is 32 bytes
 // and not compressible, and also src_extents which could use anywhere from a
@@ -318,13 +221,11 @@
     return;
   }
 
-  if (!version_.InplaceUpdate()) {
-    if (!ABGenerator::FragmentOperations(
-            version_, &file_aops_, new_part_, blob_file_)) {
-      LOG(ERROR) << "Failed to fragment operations for " << name_;
-      failed_ = true;
-      return;
-    }
+  if (!ABGenerator::FragmentOperations(
+          version_, &file_aops_, new_part_, blob_file_)) {
+    LOG(ERROR) << "Failed to fragment operations for " << name_;
+    failed_ = true;
+    return;
   }
 
   LOG(INFO) << "Encoded file " << name_ << " (" << new_extents_blocks_
@@ -349,12 +250,13 @@
   if (old_file_iter != old_files_map.end())
     return old_file_iter->second;
 
-  // No old file match for the new file name, use a similar file with the
-  // shortest levenshtein distance.
+  // No old file matches the new file name. Use a similar file with the
+  // shortest levenshtein distance instead.
   // This works great if the file has version number in it, but even for
   // a completely new file, using a similar file can still help.
-  int min_distance = new_file_name.size();
-  const FilesystemInterface::File* old_file;
+  int min_distance =
+      LevenshteinDistance(new_file_name, old_files_map.begin()->first);
+  const FilesystemInterface::File* old_file = &old_files_map.begin()->second;
   for (const auto& pair : old_files_map) {
     int distance = LevenshteinDistance(new_file_name, pair.first);
     if (distance < min_distance) {
@@ -447,12 +349,8 @@
     // from the same source blocks. At that time, this code can die. -adlr
     FilesystemInterface::File old_file =
         GetOldFile(old_files_map, new_file.name);
-    vector<Extent> old_file_extents;
-    if (version.InplaceUpdate())
-      old_file_extents =
-          FilterExtentRanges(old_file.extents, old_visited_blocks);
-    else
-      old_file_extents = FilterExtentRanges(old_file.extents, old_zero_blocks);
+    auto old_file_extents =
+        FilterExtentRanges(old_file.extents, old_zero_blocks);
     old_visited_blocks.AddExtents(old_file_extents);
 
     file_delta_processors.emplace_back(old_part.path,
@@ -541,21 +439,6 @@
                                            &old_block_ids,
                                            &new_block_ids));
 
-  // If the update is inplace, we map all the blocks that didn't move,
-  // regardless of the contents since they are already copied and no operation
-  // is required.
-  if (version.InplaceUpdate()) {
-    uint64_t num_blocks = std::min(old_num_blocks, new_num_blocks);
-    for (uint64_t block = 0; block < num_blocks; block++) {
-      if (old_block_ids[block] == new_block_ids[block] &&
-          !old_visited_blocks->ContainsBlock(block) &&
-          !new_visited_blocks->ContainsBlock(block)) {
-        old_visited_blocks->AddBlock(block);
-        new_visited_blocks->AddBlock(block);
-      }
-    }
-  }
-
   // A mapping from the block_id to the list of block numbers with that block id
   // in the old partition. This is used to lookup where in the old partition
   // is a block from the new partition.
@@ -602,10 +485,6 @@
     AppendBlockToExtents(&old_identical_blocks,
                          old_blocks_map_it->second.back());
     AppendBlockToExtents(&new_identical_blocks, block);
-    // We can't reuse source blocks in minor version 1 because the cycle
-    // breaking algorithm used in the in-place update doesn't support that.
-    if (version.InplaceUpdate())
-      old_blocks_map_it->second.pop_back();
   }
 
   if (chunk_blocks == -1)
@@ -657,9 +536,7 @@
       aops->emplace_back();
       AnnotatedOperation* aop = &aops->back();
       aop->name = "<identical-blocks>";
-      aop->op.set_type(version.OperationAllowed(InstallOperation::SOURCE_COPY)
-                           ? InstallOperation::SOURCE_COPY
-                           : InstallOperation::MOVE);
+      aop->op.set_type(InstallOperation::SOURCE_COPY);
 
       uint64_t chunk_num_blocks =
           std::min(static_cast<uint64_t>(extent.num_blocks()) - op_block_offset,
@@ -704,6 +581,11 @@
   InstallOperation operation;
 
   uint64_t total_blocks = utils::BlocksInExtents(new_extents);
+  if (chunk_blocks == 0) {
+    LOG(ERROR) << "Invalid number of chunk_blocks. Cannot be 0.";
+    return false;
+  }
+
   if (chunk_blocks == -1)
     chunk_blocks = total_blocks;
 
@@ -732,13 +614,8 @@
 
     // Check if the operation writes nothing.
     if (operation.dst_extents_size() == 0) {
-      if (operation.type() == InstallOperation::MOVE) {
-        LOG(INFO) << "Empty MOVE operation (" << name << "), skipping";
-        continue;
-      } else {
-        LOG(ERROR) << "Empty non-MOVE operation";
-        return false;
-      }
+      LOG(ERROR) << "Empty non-MOVE operation";
+      return false;
     }
 
     // Now, insert into the list of operations.
@@ -828,8 +705,7 @@
 
   // Disable bsdiff, and puffdiff when the data is too big.
   bool bsdiff_allowed =
-      version.OperationAllowed(InstallOperation::SOURCE_BSDIFF) ||
-      version.OperationAllowed(InstallOperation::BSDIFF);
+      version.OperationAllowed(InstallOperation::SOURCE_BSDIFF);
   if (bsdiff_allowed &&
       blocks_to_read * kBlockSize > kMaxBsdiffDestinationSize) {
     LOG(INFO) << "bsdiff blacklisted, data too big: "
@@ -878,9 +754,7 @@
                                              kBlockSize));
     if (old_data == new_data) {
       // No change in data.
-      operation.set_type(version.OperationAllowed(InstallOperation::SOURCE_COPY)
-                             ? InstallOperation::SOURCE_COPY
-                             : InstallOperation::MOVE);
+      operation.set_type(InstallOperation::SOURCE_COPY);
       data_blob = brillo::Blob();
     } else if (IsDiffOperationBetter(
                    operation, data_blob.size(), 0, src_extents.size())) {
@@ -892,7 +766,7 @@
         ScopedPathUnlinker unlinker(patch.value());
 
         std::unique_ptr<bsdiff::PatchWriterInterface> bsdiff_patch_writer;
-        InstallOperation::Type operation_type = InstallOperation::BSDIFF;
+        InstallOperation::Type operation_type = InstallOperation::SOURCE_BSDIFF;
         if (version.OperationAllowed(InstallOperation::BROTLI_BSDIFF)) {
           bsdiff_patch_writer =
               bsdiff::CreateBSDF2PatchWriter(patch.value(),
@@ -901,9 +775,6 @@
           operation_type = InstallOperation::BROTLI_BSDIFF;
         } else {
           bsdiff_patch_writer = bsdiff::CreateBsdiffPatchWriter(patch.value());
-          if (version.OperationAllowed(InstallOperation::SOURCE_BSDIFF)) {
-            operation_type = InstallOperation::SOURCE_BSDIFF;
-          }
         }
 
         brillo::Blob bsdiff_delta;
@@ -976,23 +847,14 @@
     }
   }
 
-  // Remove identical src/dst block ranges in MOVE operations.
-  if (operation.type() == InstallOperation::MOVE) {
-    auto removed_bytes =
-        RemoveIdenticalBlockRanges(&src_extents, &dst_extents, new_data.size());
-    operation.set_src_length(old_data.size() - removed_bytes);
-    operation.set_dst_length(new_data.size() - removed_bytes);
-  }
-
   // WARNING: We always set legacy |src_length| and |dst_length| fields for
   // BSDIFF. For SOURCE_BSDIFF we only set them for minor version 3 and
   // lower. This is needed because we used to use these two parameters in the
   // SOURCE_BSDIFF for minor version 3 and lower, but we do not need them
   // anymore in higher minor versions. This means if we stop adding these
   // parameters for those minor versions, the delta payloads will be invalid.
-  if (operation.type() == InstallOperation::BSDIFF ||
-      (operation.type() == InstallOperation::SOURCE_BSDIFF &&
-       version.minor <= kOpSrcHashMinorPayloadVersion)) {
+  if (operation.type() == InstallOperation::SOURCE_BSDIFF &&
+      version.minor <= kOpSrcHashMinorPayloadVersion) {
     operation.set_src_length(old_data.size());
     operation.set_dst_length(new_data.size());
   }
@@ -1021,22 +883,6 @@
           op_type == InstallOperation::DISCARD);
 }
 
-// Returns true if |op| is a no-op operation that doesn't do any useful work
-// (e.g., a move operation that copies blocks onto themselves).
-bool IsNoopOperation(const InstallOperation& op) {
-  return (op.type() == InstallOperation::MOVE &&
-          ExpandExtents(op.src_extents()) == ExpandExtents(op.dst_extents()));
-}
-
-void FilterNoopOperations(vector<AnnotatedOperation>* ops) {
-  ops->erase(std::remove_if(ops->begin(),
-                            ops->end(),
-                            [](const AnnotatedOperation& aop) {
-                              return IsNoopOperation(aop.op);
-                            }),
-             ops->end());
-}
-
 bool InitializePartitionInfo(const PartitionConfig& part, PartitionInfo* info) {
   info->set_size(part.size);
   HashCalculator hasher;
diff --git a/payload_generator/delta_diff_utils.h b/payload_generator/delta_diff_utils.h
index 2211b30..c75d16d 100644
--- a/payload_generator/delta_diff_utils.h
+++ b/payload_generator/delta_diff_utils.h
@@ -127,14 +127,6 @@
 // Returns true if an operation with type |op_type| has no |src_extents|.
 bool IsNoSourceOperation(InstallOperation::Type op_type);
 
-// Returns true if |op| is a no-op operation that doesn't do any useful work
-// (e.g., a move operation that copies blocks onto themselves).
-bool IsNoopOperation(const InstallOperation& op);
-
-// Filters all the operations that are no-op, maintaining the relative order
-// of the rest of the operations.
-void FilterNoopOperations(std::vector<AnnotatedOperation>* ops);
-
 bool InitializePartitionInfo(const PartitionConfig& partition,
                              PartitionInfo* info);
 
diff --git a/payload_generator/delta_diff_utils_unittest.cc b/payload_generator/delta_diff_utils_unittest.cc
index b2950e8..0857f9c 100644
--- a/payload_generator/delta_diff_utils_unittest.cc
+++ b/payload_generator/delta_diff_utils_unittest.cc
@@ -136,7 +136,7 @@
   bool RunDeltaMovedAndZeroBlocks(ssize_t chunk_blocks,
                                   uint32_t minor_version) {
     BlobFileWriter blob_file(blob_fd_, &blob_size_);
-    PayloadVersion version(kChromeOSMajorPayloadVersion, minor_version);
+    PayloadVersion version(kBrilloMajorPayloadVersion, minor_version);
     ExtentRanges old_zero_blocks;
     return diff_utils::DeltaMovedAndZeroBlocks(&aops_,
                                                old_part_.path,
@@ -194,164 +194,6 @@
   }
 }
 
-TEST_F(DeltaDiffUtilsTest, MoveSmallTest) {
-  brillo::Blob data_blob(block_size_);
-  test_utils::FillWithData(&data_blob);
-
-  // The old file is on a different block than the new one.
-  vector<Extent> old_extents = {ExtentForRange(11, 1)};
-  vector<Extent> new_extents = {ExtentForRange(1, 1)};
-
-  EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob));
-  EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob));
-
-  brillo::Blob data;
-  InstallOperation op;
-  EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
-      old_part_.path,
-      new_part_.path,
-      old_extents,
-      new_extents,
-      {},  // old_deflates
-      {},  // new_deflates
-      PayloadVersion(kChromeOSMajorPayloadVersion, kInPlaceMinorPayloadVersion),
-      &data,
-      &op));
-  EXPECT_TRUE(data.empty());
-
-  EXPECT_TRUE(op.has_type());
-  EXPECT_EQ(InstallOperation::MOVE, op.type());
-  EXPECT_FALSE(op.has_data_offset());
-  EXPECT_FALSE(op.has_data_length());
-  EXPECT_EQ(1, op.src_extents_size());
-  EXPECT_EQ(kBlockSize, op.src_length());
-  EXPECT_EQ(1, op.dst_extents_size());
-  EXPECT_EQ(kBlockSize, op.dst_length());
-  EXPECT_EQ(utils::BlocksInExtents(op.src_extents()),
-            utils::BlocksInExtents(op.dst_extents()));
-  EXPECT_EQ(1U, utils::BlocksInExtents(op.dst_extents()));
-}
-
-TEST_F(DeltaDiffUtilsTest, MoveWithSameBlock) {
-  // Setup the old/new files so that it has immobile chunks; we make sure to
-  // utilize all sub-cases of such chunks: blocks 21--22 induce a split (src)
-  // and complete removal (dst), whereas blocks 24--25 induce trimming of the
-  // tail (src) and head (dst) of extents. The final block (29) is used for
-  // ensuring we properly account for the number of bytes removed in cases where
-  // the last block is partly filled. The detailed configuration:
-  //
-  // Old:  [ 20     21 22     23     24 25 ] [ 28     29 ]
-  // New:  [ 18 ] [ 21 22 ] [ 20 ] [ 24 25     26 ] [ 29 ]
-  // Same:          ^^ ^^            ^^ ^^            ^^
-  vector<Extent> old_extents = {ExtentForRange(20, 6), ExtentForRange(28, 2)};
-  vector<Extent> new_extents = {ExtentForRange(18, 1),
-                                ExtentForRange(21, 2),
-                                ExtentForRange(20, 1),
-                                ExtentForRange(24, 3),
-                                ExtentForRange(29, 1)};
-
-  uint64_t num_blocks = utils::BlocksInExtents(old_extents);
-  EXPECT_EQ(num_blocks, utils::BlocksInExtents(new_extents));
-
-  // The size of the data should match the total number of blocks. Each block
-  // has a different content.
-  brillo::Blob file_data;
-  for (uint64_t i = 0; i < num_blocks; ++i) {
-    file_data.resize(file_data.size() + kBlockSize, 'a' + i);
-  }
-
-  EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, file_data));
-  EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, file_data));
-
-  brillo::Blob data;
-  InstallOperation op;
-  EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
-      old_part_.path,
-      new_part_.path,
-      old_extents,
-      new_extents,
-      {},  // old_deflates
-      {},  // new_deflates
-      PayloadVersion(kChromeOSMajorPayloadVersion, kInPlaceMinorPayloadVersion),
-      &data,
-      &op));
-
-  EXPECT_TRUE(data.empty());
-
-  EXPECT_TRUE(op.has_type());
-  EXPECT_EQ(InstallOperation::MOVE, op.type());
-  EXPECT_FALSE(op.has_data_offset());
-  EXPECT_FALSE(op.has_data_length());
-
-  // The expected old and new extents that actually moved. See comment above.
-  old_extents = {
-      ExtentForRange(20, 1), ExtentForRange(23, 1), ExtentForRange(28, 1)};
-  new_extents = {
-      ExtentForRange(18, 1), ExtentForRange(20, 1), ExtentForRange(26, 1)};
-  num_blocks = utils::BlocksInExtents(old_extents);
-
-  EXPECT_EQ(num_blocks * kBlockSize, op.src_length());
-  EXPECT_EQ(num_blocks * kBlockSize, op.dst_length());
-
-  EXPECT_EQ(old_extents.size(), static_cast<size_t>(op.src_extents_size()));
-  for (int i = 0; i < op.src_extents_size(); i++) {
-    EXPECT_EQ(old_extents[i].start_block(), op.src_extents(i).start_block())
-        << "i == " << i;
-    EXPECT_EQ(old_extents[i].num_blocks(), op.src_extents(i).num_blocks())
-        << "i == " << i;
-  }
-
-  EXPECT_EQ(new_extents.size(), static_cast<size_t>(op.dst_extents_size()));
-  for (int i = 0; i < op.dst_extents_size(); i++) {
-    EXPECT_EQ(new_extents[i].start_block(), op.dst_extents(i).start_block())
-        << "i == " << i;
-    EXPECT_EQ(new_extents[i].num_blocks(), op.dst_extents(i).num_blocks())
-        << "i == " << i;
-  }
-}
-
-TEST_F(DeltaDiffUtilsTest, BsdiffSmallTest) {
-  // Test a BSDIFF operation from block 1 to block 2.
-  brillo::Blob data_blob(kBlockSize);
-  test_utils::FillWithData(&data_blob);
-
-  // The old file is on a different block than the new one.
-  vector<Extent> old_extents = {ExtentForRange(1, 1)};
-  vector<Extent> new_extents = {ExtentForRange(2, 1)};
-
-  EXPECT_TRUE(WriteExtents(old_part_.path, old_extents, kBlockSize, data_blob));
-  // Modify one byte in the new file.
-  data_blob[0]++;
-  EXPECT_TRUE(WriteExtents(new_part_.path, new_extents, kBlockSize, data_blob));
-
-  brillo::Blob data;
-  InstallOperation op;
-  EXPECT_TRUE(diff_utils::ReadExtentsToDiff(
-      old_part_.path,
-      new_part_.path,
-      old_extents,
-      new_extents,
-      {},  // old_deflates
-      {},  // new_deflates
-      PayloadVersion(kChromeOSMajorPayloadVersion, kInPlaceMinorPayloadVersion),
-      &data,
-      &op));
-
-  EXPECT_FALSE(data.empty());
-
-  EXPECT_TRUE(op.has_type());
-  EXPECT_EQ(InstallOperation::BSDIFF, op.type());
-  EXPECT_FALSE(op.has_data_offset());
-  EXPECT_FALSE(op.has_data_length());
-  EXPECT_EQ(1, op.src_extents_size());
-  EXPECT_EQ(kBlockSize, op.src_length());
-  EXPECT_EQ(1, op.dst_extents_size());
-  EXPECT_EQ(kBlockSize, op.dst_length());
-  EXPECT_EQ(utils::BlocksInExtents(op.src_extents()),
-            utils::BlocksInExtents(op.dst_extents()));
-  EXPECT_EQ(1U, utils::BlocksInExtents(op.dst_extents()));
-}
-
 TEST_F(DeltaDiffUtilsTest, ReplaceSmallTest) {
   // The old file is on a different block than the new one.
   vector<Extent> old_extents = {ExtentForRange(1, 1)};
@@ -383,8 +225,7 @@
         new_extents,
         {},  // old_deflates
         {},  // new_deflates
-        PayloadVersion(kChromeOSMajorPayloadVersion,
-                       kInPlaceMinorPayloadVersion),
+        PayloadVersion(kBrilloMajorPayloadVersion, kSourceMinorPayloadVersion),
         &data,
         &op));
     EXPECT_FALSE(data.empty());
@@ -426,7 +267,7 @@
       new_extents,
       {},  // old_deflates
       {},  // new_deflates
-      PayloadVersion(kChromeOSMajorPayloadVersion, kSourceMinorPayloadVersion),
+      PayloadVersion(kBrilloMajorPayloadVersion, kSourceMinorPayloadVersion),
       &data,
       &op));
   EXPECT_TRUE(data.empty());
@@ -460,7 +301,7 @@
       new_extents,
       {},  // old_deflates
       {},  // new_deflates
-      PayloadVersion(kChromeOSMajorPayloadVersion, kSourceMinorPayloadVersion),
+      PayloadVersion(kBrilloMajorPayloadVersion, kSourceMinorPayloadVersion),
       &data,
       &op));
 
@@ -500,49 +341,6 @@
   EXPECT_EQ(InstallOperation::REPLACE_BZ, op.type());
 }
 
-TEST_F(DeltaDiffUtilsTest, IsNoopOperationTest) {
-  InstallOperation op;
-  op.set_type(InstallOperation::REPLACE_BZ);
-  EXPECT_FALSE(diff_utils::IsNoopOperation(op));
-  op.set_type(InstallOperation::MOVE);
-  EXPECT_TRUE(diff_utils::IsNoopOperation(op));
-  *(op.add_src_extents()) = ExtentForRange(3, 2);
-  *(op.add_dst_extents()) = ExtentForRange(3, 2);
-  EXPECT_TRUE(diff_utils::IsNoopOperation(op));
-  *(op.add_src_extents()) = ExtentForRange(7, 5);
-  *(op.add_dst_extents()) = ExtentForRange(7, 5);
-  EXPECT_TRUE(diff_utils::IsNoopOperation(op));
-  *(op.add_src_extents()) = ExtentForRange(20, 2);
-  *(op.add_dst_extents()) = ExtentForRange(20, 1);
-  *(op.add_dst_extents()) = ExtentForRange(21, 1);
-  EXPECT_TRUE(diff_utils::IsNoopOperation(op));
-  *(op.add_src_extents()) = ExtentForRange(24, 1);
-  *(op.add_dst_extents()) = ExtentForRange(25, 1);
-  EXPECT_FALSE(diff_utils::IsNoopOperation(op));
-}
-
-TEST_F(DeltaDiffUtilsTest, FilterNoopOperations) {
-  AnnotatedOperation aop1;
-  aop1.op.set_type(InstallOperation::REPLACE_BZ);
-  *(aop1.op.add_dst_extents()) = ExtentForRange(3, 2);
-  aop1.name = "aop1";
-
-  AnnotatedOperation aop2 = aop1;
-  aop2.name = "aop2";
-
-  AnnotatedOperation noop;
-  noop.op.set_type(InstallOperation::MOVE);
-  *(noop.op.add_src_extents()) = ExtentForRange(3, 2);
-  *(noop.op.add_dst_extents()) = ExtentForRange(3, 2);
-  noop.name = "noop";
-
-  vector<AnnotatedOperation> ops = {noop, aop1, noop, noop, aop2, noop};
-  diff_utils::FilterNoopOperations(&ops);
-  EXPECT_EQ(2u, ops.size());
-  EXPECT_EQ("aop1", ops[0].name);
-  EXPECT_EQ("aop2", ops[1].name);
-}
-
 // Test the simple case where all the blocks are different and no new blocks are
 // zeroed.
 TEST_F(DeltaDiffUtilsTest, NoZeroedOrUniqueBlocksDetected) {
@@ -550,7 +348,7 @@
   InitializePartitionWithUniqueBlocks(new_part_, block_size_, 42);
 
   EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1,  // chunk_blocks
-                                         kInPlaceMinorPayloadVersion));
+                                         kSourceMinorPayloadVersion));
 
   EXPECT_EQ(0U, old_visited_blocks_.blocks());
   EXPECT_EQ(0U, new_visited_blocks_.blocks());
@@ -558,29 +356,6 @@
   EXPECT_TRUE(aops_.empty());
 }
 
-// Test that when the partitions have identical blocks in the same positions no
-// MOVE operation is performed and all the blocks are handled.
-TEST_F(DeltaDiffUtilsTest, IdenticalPartitionsDontMove) {
-  InitializePartitionWithUniqueBlocks(old_part_, block_size_, 42);
-  InitializePartitionWithUniqueBlocks(new_part_, block_size_, 42);
-
-  // Mark some of the blocks as already visited.
-  vector<Extent> already_visited = {ExtentForRange(5, 10),
-                                    ExtentForRange(25, 10)};
-  old_visited_blocks_.AddExtents(already_visited);
-  new_visited_blocks_.AddExtents(already_visited);
-
-  // Most of the blocks rest in the same place, but there's no need for MOVE
-  // operations on those blocks.
-  EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(-1,  // chunk_blocks
-                                         kInPlaceMinorPayloadVersion));
-
-  EXPECT_EQ(kDefaultBlockCount, old_visited_blocks_.blocks());
-  EXPECT_EQ(kDefaultBlockCount, new_visited_blocks_.blocks());
-  EXPECT_EQ(0, blob_size_);
-  EXPECT_TRUE(aops_.empty());
-}
-
 // Test that when the partitions have identical blocks in the same positions
 // MOVE operation is performed and all the blocks are handled.
 TEST_F(DeltaDiffUtilsTest, IdenticalBlocksAreCopiedFromSource) {
@@ -701,16 +476,14 @@
   EXPECT_TRUE(WriteExtents(old_part_.path, old_zeros, block_size_, zeros_data));
 
   EXPECT_TRUE(RunDeltaMovedAndZeroBlocks(5,  // chunk_blocks
-                                         kInPlaceMinorPayloadVersion));
+                                         kSourceMinorPayloadVersion));
 
-  // Zeroed blocks from old_visited_blocks_ were copied over, so me actually
-  // use them regardless of the trivial MOVE operation not being emitted.
+  // Zeroed blocks from |old_visited_blocks_| were copied over.
   EXPECT_EQ(old_zeros,
             old_visited_blocks_.GetExtentsForBlockCount(
                 old_visited_blocks_.blocks()));
 
-  // All the new zeroed blocks should be used, part with REPLACE_BZ and part
-  // trivial MOVE operations (not included).
+  // All the new zeroed blocks should be used with REPLACE_BZ.
   EXPECT_EQ(new_zeros,
             new_visited_blocks_.GetExtentsForBlockCount(
                 new_visited_blocks_.blocks()));
@@ -721,7 +494,8 @@
       // This range should be split.
       ExtentForRange(30, 5),
       ExtentForRange(35, 5),
-      ExtentForRange(40, 3),
+      ExtentForRange(40, 5),
+      ExtentForRange(45, 5),
   };
 
   EXPECT_EQ(expected_op_extents.size(), aops_.size());
@@ -821,6 +595,8 @@
       "update_engine");
   EXPECT_EQ(diff_utils::GetOldFile(old_files_map, "bin/delta_generator").name,
             "delta_generator");
+  // Check file name with minimum size.
+  EXPECT_EQ(diff_utils::GetOldFile(old_files_map, "a").name, "filename");
 }
 
 }  // namespace chromeos_update_engine
diff --git a/payload_generator/extent_ranges.cc b/payload_generator/extent_ranges.cc
index 0e3f087..4600efe 100644
--- a/payload_generator/extent_ranges.cc
+++ b/payload_generator/extent_ranges.cc
@@ -27,7 +27,6 @@
 #include "update_engine/payload_consumer/payload_constants.h"
 #include "update_engine/payload_generator/extent_utils.h"
 
-using std::set;
 using std::vector;
 
 namespace chromeos_update_engine {
diff --git a/payload_generator/extent_ranges_unittest.cc b/payload_generator/extent_ranges_unittest.cc
index 2bcffed..326e936 100644
--- a/payload_generator/extent_ranges_unittest.cc
+++ b/payload_generator/extent_ranges_unittest.cc
@@ -18,6 +18,7 @@
 
 #include <vector>
 
+#include <base/stl_util.h>
 #include <gtest/gtest.h>
 
 #include "update_engine/common/test_utils.h"
@@ -53,7 +54,7 @@
 
 #define EXPECT_RANGE_EQ(ranges, var)                      \
   do {                                                    \
-    ExpectRangeEq(ranges, var, arraysize(var), __LINE__); \
+    ExpectRangeEq(ranges, var, base::size(var), __LINE__); \
   } while (0)
 
 void ExpectRangesOverlapOrTouch(uint64_t a_start,
diff --git a/payload_generator/filesystem_interface.h b/payload_generator/filesystem_interface.h
index d04295c..05d387f 100644
--- a/payload_generator/filesystem_interface.h
+++ b/payload_generator/filesystem_interface.h
@@ -62,6 +62,13 @@
     // indicating the starting block, and the number of consecutive blocks.
     std::vector<Extent> extents;
 
+    // If true, the file is already compressed on the disk, so we don't need to
+    // parse it again for deflates. For example, image .gz files inside a
+    // compressed SquashFS image. They might have already been compressed by the
+    // mksquashfs, so we can't really parse the file and look for deflate
+    // compressed parts anymore.
+    bool is_compressed = false;
+
     // All the deflate locations in the file. These locations are not relative
     // to the extents. They are relative to the file system itself.
     std::vector<puffin::BitExtent> deflates;
diff --git a/payload_generator/full_update_generator_unittest.cc b/payload_generator/full_update_generator_unittest.cc
index e398125..5f39e8b 100644
--- a/payload_generator/full_update_generator_unittest.cc
+++ b/payload_generator/full_update_generator_unittest.cc
@@ -90,7 +90,7 @@
     EXPECT_EQ(config_.hard_chunk_size / config_.block_size,
               aops[i].op.dst_extents(0).num_blocks());
     if (aops[i].op.type() != InstallOperation::REPLACE) {
-      EXPECT_EQ(InstallOperation::REPLACE_BZ, aops[i].op.type());
+      EXPECT_EQ(InstallOperation::REPLACE_XZ, aops[i].op.type());
     }
   }
 }
diff --git a/payload_generator/generate_delta_main.cc b/payload_generator/generate_delta_main.cc
index f035ff1..f7df211 100644
--- a/payload_generator/generate_delta_main.cc
+++ b/payload_generator/generate_delta_main.cc
@@ -38,6 +38,7 @@
 #include "update_engine/payload_consumer/payload_constants.h"
 #include "update_engine/payload_generator/delta_diff_generator.h"
 #include "update_engine/payload_generator/payload_generation_config.h"
+#include "update_engine/payload_generator/payload_properties.h"
 #include "update_engine/payload_generator/payload_signer.h"
 #include "update_engine/payload_generator/xz.h"
 #include "update_engine/update_metadata.pb.h"
@@ -53,6 +54,9 @@
 
 namespace {
 
+constexpr char kPayloadPropertiesFormatKeyValue[] = "key-value";
+constexpr char kPayloadPropertiesFormatJson[] = "json";
+
 void ParseSignatureSizes(const string& signature_sizes_flag,
                          vector<size_t>* signature_sizes) {
   signature_sizes->clear();
@@ -267,14 +271,24 @@
   return true;
 }
 
-int ExtractProperties(const string& payload_path, const string& props_file) {
-  brillo::KeyValueStore properties;
-  TEST_AND_RETURN_FALSE(
-      PayloadSigner::ExtractPayloadProperties(payload_path, &properties));
-  if (props_file == "-") {
-    printf("%s", properties.SaveToString().c_str());
+bool ExtractProperties(const string& payload_path,
+                       const string& props_file,
+                       const string& props_format) {
+  string properties;
+  PayloadProperties payload_props(payload_path);
+  if (props_format == kPayloadPropertiesFormatKeyValue) {
+    TEST_AND_RETURN_FALSE(payload_props.GetPropertiesAsKeyValue(&properties));
+  } else if (props_format == kPayloadPropertiesFormatJson) {
+    TEST_AND_RETURN_FALSE(payload_props.GetPropertiesAsJson(&properties));
   } else {
-    properties.Save(base::FilePath(props_file));
+    LOG(FATAL) << "Invalid option " << props_format
+               << " for --properties_format flag.";
+  }
+  if (props_file == "-") {
+    printf("%s", properties.c_str());
+  } else {
+    utils::WriteFile(
+        props_file.c_str(), properties.c_str(), properties.length());
     LOG(INFO) << "Generated properties file at " << props_file;
   }
   return true;
@@ -361,7 +375,11 @@
   DEFINE_string(properties_file,
                 "",
                 "If passed, dumps the payload properties of the payload passed "
-                "in --in_file and exits.");
+                "in --in_file and exits. Look at --properties_format.");
+  DEFINE_string(properties_format,
+                kPayloadPropertiesFormatKeyValue,
+                "Defines the format of the --properties_file. The acceptable "
+                "values are: key-value (default) and json");
   DEFINE_int64(max_timestamp,
                0,
                "The maximum timestamp of the OS allowed to apply this "
@@ -500,7 +518,10 @@
     return VerifySignedPayload(FLAGS_in_file, FLAGS_public_key);
   }
   if (!FLAGS_properties_file.empty()) {
-    return ExtractProperties(FLAGS_in_file, FLAGS_properties_file) ? 0 : 1;
+    return ExtractProperties(
+               FLAGS_in_file, FLAGS_properties_file, FLAGS_properties_format)
+               ? 0
+               : 1;
   }
 
   // A payload generation was requested. Convert the flags to a
@@ -521,16 +542,10 @@
   partition_names = base::SplitString(
       FLAGS_partition_names, ":", base::TRIM_WHITESPACE, base::SPLIT_WANT_ALL);
   CHECK(!partition_names.empty());
-  if (FLAGS_major_version == kChromeOSMajorPayloadVersion ||
-      FLAGS_new_partitions.empty()) {
-    LOG_IF(FATAL, partition_names.size() != 2)
-        << "To support more than 2 partitions, please use the "
-        << "--new_partitions flag and major version 2.";
-    LOG_IF(FATAL,
-           partition_names[0] != kPartitionNameRoot ||
-               partition_names[1] != kPartitionNameKernel)
-        << "To support non-default partition name, please use the "
-        << "--new_partitions flag and major version 2.";
+  if (FLAGS_major_version < kMinSupportedMajorPayloadVersion ||
+      FLAGS_major_version > kMaxSupportedMajorPayloadVersion) {
+    LOG(FATAL) << "Unsupported major version " << FLAGS_major_version;
+    return 1;
   }
 
   if (!FLAGS_new_partitions.empty()) {
@@ -591,8 +606,6 @@
   }
 
   if (!FLAGS_new_postinstall_config_file.empty()) {
-    LOG_IF(FATAL, FLAGS_major_version == kChromeOSMajorPayloadVersion)
-        << "Postinstall config is only allowed in major version 2 or newer.";
     brillo::KeyValueStore store;
     CHECK(store.Load(base::FilePath(FLAGS_new_postinstall_config_file)));
     CHECK(payload_config.target.LoadPostInstallConfig(store));
@@ -610,9 +623,6 @@
   CHECK(payload_config.target.LoadImageSize());
 
   if (!FLAGS_dynamic_partition_info_file.empty()) {
-    LOG_IF(FATAL, FLAGS_major_version == kChromeOSMajorPayloadVersion)
-        << "Dynamic partition info is only allowed in major version 2 or "
-           "newer.";
     brillo::KeyValueStore store;
     CHECK(store.Load(base::FilePath(FLAGS_dynamic_partition_info_file)));
     CHECK(payload_config.target.LoadDynamicPartitionMetadata(store));
@@ -656,25 +666,40 @@
     // Autodetect minor_version by looking at the update_engine.conf in the old
     // image.
     if (payload_config.is_delta) {
-      payload_config.version.minor = kInPlaceMinorPayloadVersion;
       brillo::KeyValueStore store;
       uint32_t minor_version;
+      bool minor_version_found = false;
       for (const PartitionConfig& part : payload_config.source.partitions) {
         if (part.fs_interface && part.fs_interface->LoadSettings(&store) &&
             utils::GetMinorVersion(store, &minor_version)) {
           payload_config.version.minor = minor_version;
+          minor_version_found = true;
+          LOG(INFO) << "Auto-detected minor_version="
+                    << payload_config.version.minor;
           break;
         }
       }
+      if (!minor_version_found) {
+        LOG(FATAL) << "Failed to detect the minor version.";
+        return 1;
+      }
     } else {
       payload_config.version.minor = kFullPayloadMinorVersion;
+      LOG(INFO) << "Using non-delta minor_version="
+                << payload_config.version.minor;
     }
-    LOG(INFO) << "Auto-detected minor_version=" << payload_config.version.minor;
   } else {
     payload_config.version.minor = FLAGS_minor_version;
     LOG(INFO) << "Using provided minor_version=" << FLAGS_minor_version;
   }
 
+  if (payload_config.version.minor != kFullPayloadMinorVersion &&
+      (payload_config.version.minor < kMinSupportedMinorPayloadVersion ||
+       payload_config.version.minor > kMaxSupportedMinorPayloadVersion)) {
+    LOG(FATAL) << "Unsupported minor version " << payload_config.version.minor;
+    return 1;
+  }
+
   payload_config.max_timestamp = FLAGS_max_timestamp;
 
   if (payload_config.version.minor >= kVerityMinorPayloadVersion)
diff --git a/payload_generator/graph_types.cc b/payload_generator/graph_types.cc
deleted file mode 100644
index c03766d..0000000
--- a/payload_generator/graph_types.cc
+++ /dev/null
@@ -1,23 +0,0 @@
-//
-// Copyright (C) 2015 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//      http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#include "update_engine/payload_generator/graph_types.h"
-
-namespace chromeos_update_engine {
-
-const Vertex::Index Vertex::kInvalidIndex = static_cast<Vertex::Index>(-1);
-
-}  // namespace chromeos_update_engine
diff --git a/payload_generator/graph_types.h b/payload_generator/graph_types.h
deleted file mode 100644
index f96b0f3..0000000
--- a/payload_generator/graph_types.h
+++ /dev/null
@@ -1,87 +0,0 @@
-//
-// Copyright (C) 2009 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//      http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_
-#define UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_
-
-#include <map>
-#include <set>
-#include <string>
-#include <utility>
-#include <vector>
-
-#include <base/macros.h>
-
-#include "update_engine/payload_generator/annotated_operation.h"
-#include "update_engine/payload_generator/extent_utils.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 {
-
-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) {}
-  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:
-  AnnotatedOperation aop;
-
-  typedef std::vector<Vertex>::size_type Index;
-  static const Vertex::Index kInvalidIndex;
-};
-
-typedef std::vector<Vertex> Graph;
-
-typedef std::pair<Vertex::Index, Vertex::Index> Edge;
-
-const uint64_t kTempBlockStart = 1ULL << 60;
-static_assert(kTempBlockStart != 0, "kTempBlockStart invalid");
-
-}  // namespace chromeos_update_engine
-
-#endif  // UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_
diff --git a/payload_generator/graph_utils.cc b/payload_generator/graph_utils.cc
deleted file mode 100644
index 7f5cf8f..0000000
--- a/payload_generator/graph_utils.cc
+++ /dev/null
@@ -1,142 +0,0 @@
-//
-// Copyright (C) 2009 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//      http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#include "update_engine/payload_generator/graph_utils.h"
-
-#include <string>
-#include <utility>
-#include <vector>
-
-#include <base/logging.h>
-#include <base/macros.h>
-
-#include "update_engine/payload_consumer/payload_constants.h"
-#include "update_engine/payload_generator/annotated_operation.h"
-#include "update_engine/payload_generator/extent_utils.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 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);
-  }
-}
-
-namespace {
-template <typename T>
-void DumpExtents(const T& field, int prepend_space_count) {
-  string header(prepend_space_count, ' ');
-  for (const auto& extent : field) {
-    LOG(INFO) << header << "(" << extent.start_block() << ", "
-              << extent.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) {
-    LOG(INFO) << i << (graph[i].valid ? "" : "-INV") << ": "
-              << graph[i].aop.name << ": "
-              << InstallOperationTypeName(graph[i].aop.op.type());
-    LOG(INFO) << "  src_extents:";
-    DumpExtents(graph[i].aop.op.src_extents(), 4);
-    LOG(INFO) << "  dst_extents:";
-    DumpExtents(graph[i].aop.op.dst_extents(), 4);
-    LOG(INFO) << "  out edges:";
-    DumpOutEdges(graph[i].out_edges);
-  }
-}
-
-}  // namespace graph_utils
-}  // namespace chromeos_update_engine
diff --git a/payload_generator/graph_utils.h b/payload_generator/graph_utils.h
deleted file mode 100644
index 7024215..0000000
--- a/payload_generator/graph_utils.h
+++ /dev/null
@@ -1,54 +0,0 @@
-//
-// Copyright (C) 2009 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//      http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_UTILS_H_
-#define UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_UTILS_H_
-
-#include <vector>
-
-#include <base/macros.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);
-
-void DumpGraph(const Graph& graph);
-
-}  // namespace graph_utils
-
-}  // namespace chromeos_update_engine
-
-#endif  // UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_UTILS_H_
diff --git a/payload_generator/graph_utils_unittest.cc b/payload_generator/graph_utils_unittest.cc
deleted file mode 100644
index 07e7664..0000000
--- a/payload_generator/graph_utils_unittest.cc
+++ /dev/null
@@ -1,94 +0,0 @@
-//
-// Copyright (C) 2009 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//      http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#include "update_engine/payload_generator/graph_utils.h"
-
-#include <utility>
-#include <vector>
-
-#include <gtest/gtest.h>
-
-#include "update_engine/payload_consumer/payload_constants.h"
-#include "update_engine/payload_generator/extent_ranges.h"
-#include "update_engine/payload_generator/extent_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(0U, extents.size());
-  AppendBlockToExtents(&extents, 0);
-  EXPECT_EQ(1U, extents.size());
-  AppendBlockToExtents(&extents, 1);
-  AppendBlockToExtents(&extents, 2);
-  EXPECT_EQ(1U, extents.size());
-  AppendBlockToExtents(&extents, 4);
-
-  EXPECT_EQ(2U, extents.size());
-  EXPECT_EQ(0U, extents[0].start_block());
-  EXPECT_EQ(3U, extents[0].num_blocks());
-  EXPECT_EQ(4U, extents[1].start_block());
-  EXPECT_EQ(1U, extents[1].num_blocks());
-
-  EXPECT_EQ(4U, graph_utils::EdgeWeight(graph, make_pair(0, 1)));
-}
-
-TEST(GraphUtilsTest, DepsTest) {
-  Graph graph(3);
-
-  graph_utils::AddReadBeforeDep(&graph[0], 1, 3);
-  EXPECT_EQ(1U, graph[0].out_edges.size());
-  {
-    Extent& extent = graph[0].out_edges[1].extents[0];
-    EXPECT_EQ(3U, extent.start_block());
-    EXPECT_EQ(1U, extent.num_blocks());
-  }
-  graph_utils::AddReadBeforeDep(&graph[0], 1, 4);
-  EXPECT_EQ(1U, graph[0].out_edges.size());
-  {
-    Extent& extent = graph[0].out_edges[1].extents[0];
-    EXPECT_EQ(3U, extent.start_block());
-    EXPECT_EQ(2U, extent.num_blocks());
-  }
-  graph_utils::AddReadBeforeDepExtents(
-      &graph[2], 1, vector<Extent>(1, ExtentForRange(5, 2)));
-  EXPECT_EQ(1U, graph[2].out_edges.size());
-  {
-    Extent& extent = graph[2].out_edges[1].extents[0];
-    EXPECT_EQ(5U, extent.start_block());
-    EXPECT_EQ(2U, 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(0U, graph[2].out_edges.size());
-
-  EXPECT_EQ(1U, graph[0].out_edges.size());
-  graph_utils::DropIncomingEdgesTo(&graph, 1);
-  EXPECT_EQ(0U, graph[0].out_edges.size());
-}
-
-}  // namespace chromeos_update_engine
diff --git a/payload_generator/inplace_generator.cc b/payload_generator/inplace_generator.cc
deleted file mode 100644
index d553cc4..0000000
--- a/payload_generator/inplace_generator.cc
+++ /dev/null
@@ -1,798 +0,0 @@
-//
-// Copyright (C) 2015 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//      http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#include "update_engine/payload_generator/inplace_generator.h"
-
-#include <algorithm>
-#include <map>
-#include <set>
-#include <string>
-#include <utility>
-#include <vector>
-
-#include <base/stl_util.h>
-
-#include "update_engine/common/utils.h"
-#include "update_engine/payload_consumer/payload_constants.h"
-#include "update_engine/payload_generator/cycle_breaker.h"
-#include "update_engine/payload_generator/delta_diff_generator.h"
-#include "update_engine/payload_generator/delta_diff_utils.h"
-#include "update_engine/payload_generator/extent_ranges.h"
-#include "update_engine/payload_generator/graph_types.h"
-#include "update_engine/payload_generator/graph_utils.h"
-#include "update_engine/payload_generator/topological_sort.h"
-#include "update_engine/update_metadata.pb.h"
-
-using std::make_pair;
-using std::map;
-using std::pair;
-using std::set;
-using std::string;
-using std::vector;
-
-namespace chromeos_update_engine {
-
-using Block = InplaceGenerator::Block;
-
-namespace {
-
-// The only PayloadVersion supported by this implementation.
-const PayloadVersion kInPlacePayloadVersion{kChromeOSMajorPayloadVersion,
-                                            kInPlaceMinorPayloadVersion};
-
-// 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:
-  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_{kTempBlockStart};
-};
-
-// 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 (uint64_t block : blocks) {
-    AppendBlockToExtents(&new_extents, block);
-  }
-  return new_extents;
-}
-
-// Helper class to compare two operations by start block of the first Extent in
-// their destination extents given the index of the operations in the graph.
-class IndexedInstallOperationsDstComparator {
- public:
-  explicit IndexedInstallOperationsDstComparator(Graph* graph)
-      : graph_(graph) {}
-
-  // Compares the operations in the vertex a and b of graph_.
-  bool operator()(size_t a, size_t b) const {
-    return diff_utils::CompareAopsByDestination((*graph_)[a].aop,
-                                                (*graph_)[b].aop);
-  }
-
- private:
-  const Graph* const graph_;
-};
-
-}  // namespace
-
-void InplaceGenerator::CheckGraph(const Graph& graph) {
-  for (const Vertex& v : graph) {
-    CHECK(v.aop.op.has_type());
-  }
-}
-
-void InplaceGenerator::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->aop.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];
-    }
-    ApplyMap(&read_blocks, conversion);
-    for (auto& edge_prop_pair : vertex->out_edges) {
-      vector<uint64_t> write_before_deps_expanded =
-          ExpandExtents(edge_prop_pair.second.write_extents);
-      ApplyMap(&write_before_deps_expanded, conversion);
-      edge_prop_pair.second.write_extents =
-          CompressExtents(write_before_deps_expanded);
-    }
-  }
-  // Convert read_blocks back to extents
-  vertex->aop.op.clear_src_extents();
-  vector<Extent> new_extents = CompressExtents(read_blocks);
-  StoreExtents(new_extents, vertex->aop.op.mutable_src_extents());
-}
-
-bool InplaceGenerator::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 (const Edge& edge : edges) {
-    cuts.resize(cuts.size() + 1);
-    vector<Extent> old_extents =
-        (*graph)[edge.first].out_edges[edge.second].extents;
-    // Choose some scratch space
-    scratch_blocks_used += graph_utils::EdgeWeight(*graph, edge);
-    cuts.back().tmp_extents =
-        scratch_allocator.Allocate(graph_utils::EdgeWeight(*graph, edge));
-    // create vertex to copy original->scratch
-    cuts.back().new_vertex = graph->size();
-    graph->emplace_back();
-    cuts.back().old_src = edge.first;
-    cuts.back().old_dst = edge.second;
-
-    EdgeProperties& cut_edge_properties =
-        (*graph)[edge.first].out_edges.find(edge.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)[edge.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().aop.op.set_type(InstallOperation::MOVE);
-    StoreExtents(cut_edge_properties.extents,
-                 graph->back().aop.op.mutable_src_extents());
-    StoreExtents(cuts.back().tmp_extents,
-                 graph->back().aop.op.mutable_dst_extents());
-    graph->back().aop.op.set_src_length(graph_utils::EdgeWeight(*graph, edge) *
-                                        kBlockSize);
-    graph->back().aop.op.set_dst_length(graph->back().aop.op.src_length());
-
-    // make the dest node read from the scratch space
-    SubstituteBlocks(&((*graph)[edge.second]),
-                     (*graph)[edge.first].out_edges[edge.second].extents,
-                     cuts.back().tmp_extents);
-
-    // delete the old edge
-    CHECK_EQ(static_cast<Graph::size_type>(1),
-             (*graph)[edge.first].out_edges.erase(edge.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)[edge.second].out_edges.insert(
-        make_pair(graph->size() - 1, write_before_edge_properties));
-  }
-  out_cuts->swap(cuts);
-  return true;
-}
-
-// 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 InplaceGenerator::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());
-    }
-    AppendBlockToExtents(&edge_it->second.extents, i);
-  }
-}
-
-namespace {
-
-class SortCutsByTopoOrderLess {
- public:
-  explicit SortCutsByTopoOrderLess(
-      const 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:
-  const vector<vector<Vertex::Index>::size_type>& table_;
-};
-
-}  // namespace
-
-void InplaceGenerator::GenerateReverseTopoOrderMap(
-    const 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 InplaceGenerator::SortCutsByTopoOrder(
-    const 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 InplaceGenerator::MoveAndSortFullOpsToBack(
-    Graph* graph, vector<Vertex::Index>* op_indexes) {
-  vector<Vertex::Index> ret;
-  vector<Vertex::Index> full_ops;
-  ret.reserve(op_indexes->size());
-  for (auto op_index : *op_indexes) {
-    InstallOperation::Type type = (*graph)[op_index].aop.op.type();
-    if (type == InstallOperation::REPLACE ||
-        type == InstallOperation::REPLACE_BZ) {
-      full_ops.push_back(op_index);
-    } else {
-      ret.push_back(op_index);
-    }
-  }
-  LOG(INFO) << "Stats: " << full_ops.size() << " full ops out of "
-            << (full_ops.size() + ret.size()) << " total ops.";
-  // Sort full ops according to their dst_extents.
-  sort(full_ops.begin(),
-       full_ops.end(),
-       IndexedInstallOperationsDstComparator(graph));
-  ret.insert(ret.end(), full_ops.begin(), full_ops.end());
-  op_indexes->swap(ret);
-}
-
-namespace {
-
-template <typename T>
-bool TempBlocksExistInExtents(const T& extents) {
-  for (const auto& extent : extents) {
-    uint64_t start = extent.start_block();
-    uint64_t num = extent.num_blocks();
-    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;
-}
-
-// Converts 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_part,
-    BlobFileWriter* blob_file,
-    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 (const CutEdgeVertexes& cut : cuts) {
-    TEST_AND_RETURN_FALSE(
-        InplaceGenerator::ConvertCutToFullOp(graph, cut, new_part, blob_file));
-    deleted_nodes.insert(cut.new_vertex);
-  }
-  deleted_nodes.insert(cuts[0].old_dst);
-
-  vector<Vertex::Index> new_op_indexes;
-  new_op_indexes.reserve(op_indexes->size());
-  for (Vertex::Index vertex_index : *op_indexes) {
-    if (base::ContainsKey(deleted_nodes, vertex_index))
-      continue;
-    new_op_indexes.push_back(vertex_index);
-  }
-  new_op_indexes.push_back(cuts[0].old_dst);
-  op_indexes->swap(new_op_indexes);
-  InplaceGenerator::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_part,
-    BlobFileWriter* blob_file,
-    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;
-  vector<uint64_t> cuts_blocks_needed(cuts.size());
-  for (vector<CutEdgeVertexes>::size_type i = 0; i < cuts.size(); ++i) {
-    uint64_t cut_blocks_needed = 0;
-    for (const Extent& extent : cuts[i].tmp_extents) {
-      cut_blocks_needed += extent.num_blocks();
-    }
-    blocks_needed += cut_blocks_needed;
-    cuts_blocks_needed[i] = 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].aop.op.dst_extents());
-    ranges.SubtractExtent(
-        ExtentForRange(kTempBlockStart, kSparseHole - kTempBlockStart));
-    ranges.SubtractRepeatedExtents((*graph)[test_node].aop.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);
-    }
-
-    // Prevent using the block 0 as scratch space due to crbug.com/480751.
-    if (ranges.ContainsBlock(0)) {
-      LOG(INFO) << "Removing block 0 from the selected scratch range in vertex "
-                << i;
-      ranges.SubtractBlock(0);
-    }
-
-    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_part, blob_file, 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 (const auto& index_range_pair : block_suppliers) {
-    graph_utils::AddReadBeforeDepExtents(
-        &(*graph)[index_range_pair.first],
-        old_dst,
-        index_range_pair.second.GetExtentsForBlockCount(
-            index_range_pair.second.blocks()));
-  }
-
-  // Replace temp blocks in each cut
-  for (vector<CutEdgeVertexes>::size_type i = 0; i < cuts.size(); ++i) {
-    const CutEdgeVertexes& cut = cuts[i];
-    vector<Extent> real_extents =
-        scratch_ranges.GetExtentsForBlockCount(cuts_blocks_needed[i]);
-    scratch_ranges.SubtractExtents(real_extents);
-
-    // Fix the old dest node w/ the real blocks
-    InplaceGenerator::SubstituteBlocks(
-        &(*graph)[old_dst], cut.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.
-    InstallOperation* op = &(*graph)[cut.new_vertex].aop.op;
-    op->clear_dst_extents();
-    StoreExtents(real_extents, op->mutable_dst_extents());
-  }
-  return true;
-}
-
-}  // namespace
-
-bool InplaceGenerator::AssignTempBlocks(
-    Graph* graph,
-    const string& new_part,
-    BlobFileWriter* blob_file,
-    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].aop.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_part,
-                                                        blob_file,
-                                                        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_part, blob_file, op_indexes, reverse_op_indexes, cuts_group));
-  return true;
-}
-
-bool InplaceGenerator::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 InstallOperation& op = it->aop.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 (const auto& edge_prop_pair : it->out_edges) {
-      if (TempBlocksExistInExtents(edge_prop_pair.second.extents) ||
-          TempBlocksExistInExtents(edge_prop_pair.second.write_extents)) {
-        LOG(INFO) << "bad out edge in node " << idx;
-        LOG(INFO) << "so yeah";
-        return false;
-      }
-    }
-  }
-  return true;
-}
-
-bool InplaceGenerator::ConvertCutToFullOp(Graph* graph,
-                                          const CutEdgeVertexes& cut,
-                                          const string& new_part,
-                                          BlobFileWriter* blob_file) {
-  // Drop all incoming edges, keep all outgoing edges
-
-  // Keep all outgoing edges
-  if ((*graph)[cut.old_dst].aop.op.type() != InstallOperation::REPLACE_BZ &&
-      (*graph)[cut.old_dst].aop.op.type() != InstallOperation::REPLACE) {
-    Vertex::EdgeMap out_edges = (*graph)[cut.old_dst].out_edges;
-    graph_utils::DropWriteBeforeDeps(&out_edges);
-
-    // Replace the operation with a REPLACE or REPLACE_BZ to generate the same
-    // |new_extents| list of blocks and update the graph.
-    vector<AnnotatedOperation> new_aop;
-    vector<Extent> new_extents;
-    ExtentsToVector((*graph)[cut.old_dst].aop.op.dst_extents(), &new_extents);
-    TEST_AND_RETURN_FALSE(diff_utils::DeltaReadFile(
-        &new_aop,
-        "",  // old_part
-        new_part,
-        vector<Extent>(),  // old_extents
-        new_extents,
-        {},  // old_deflates
-        {},  // new_deflates
-        (*graph)[cut.old_dst].aop.name,
-        -1,  // chunk_blocks, forces to have a single operation.
-        kInPlacePayloadVersion,
-        blob_file));
-    TEST_AND_RETURN_FALSE(new_aop.size() == 1);
-    TEST_AND_RETURN_FALSE(AddInstallOpToGraph(
-        graph, cut.old_dst, nullptr, new_aop.front().op, new_aop.front().name));
-
-    (*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 InplaceGenerator::ConvertGraphToDag(Graph* graph,
-                                         const string& new_part,
-                                         BlobFileWriter* blob_file,
-                                         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";
-  MoveAndSortFullOpsToBack(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_part, blob_file, 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 InplaceGenerator::CreateScratchNode(uint64_t start_block,
-                                         uint64_t num_blocks,
-                                         Vertex* vertex) {
-  vertex->aop.name = "<scratch>";
-  vertex->aop.op.set_type(InstallOperation::REPLACE_BZ);
-  vertex->aop.op.set_data_offset(0);
-  vertex->aop.op.set_data_length(0);
-  Extent* extent = vertex->aop.op.add_dst_extents();
-  extent->set_start_block(start_block);
-  extent->set_num_blocks(num_blocks);
-}
-
-bool InplaceGenerator::AddInstallOpToBlocksVector(
-    const 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 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 (const Extent& extent : extents) {
-      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].aop.name
-                     << ") and also " << vertex << "(" << graph[vertex].aop.name
-                     << ")";
-        }
-        (*blocks)[block].*access_type = vertex;
-      }
-    }
-  }
-  return true;
-}
-
-bool InplaceGenerator::AddInstallOpToGraph(Graph* graph,
-                                           Vertex::Index existing_vertex,
-                                           vector<Block>* blocks,
-                                           const InstallOperation& operation,
-                                           const string& op_name) {
-  Vertex::Index vertex = existing_vertex;
-  if (vertex == Vertex::kInvalidIndex) {
-    graph->emplace_back();
-    vertex = graph->size() - 1;
-  }
-  (*graph)[vertex].aop.op = operation;
-  CHECK((*graph)[vertex].aop.op.has_type());
-  (*graph)[vertex].aop.name = op_name;
-
-  if (blocks)
-    TEST_AND_RETURN_FALSE(InplaceGenerator::AddInstallOpToBlocksVector(
-        (*graph)[vertex].aop.op, *graph, vertex, blocks));
-  return true;
-}
-
-void InplaceGenerator::ApplyMap(vector<uint64_t>* collection,
-                                const map<uint64_t, uint64_t>& the_map) {
-  for (uint64_t& elem : *collection) {
-    const auto& map_it = the_map.find(elem);
-    if (map_it != the_map.end())
-      elem = map_it->second;
-  }
-}
-
-bool InplaceGenerator::ResolveReadAfterWriteDependencies(
-    const PartitionConfig& old_part,
-    const PartitionConfig& new_part,
-    uint64_t partition_size,
-    size_t block_size,
-    BlobFileWriter* blob_file,
-    vector<AnnotatedOperation>* aops) {
-  // Convert the operations to the graph.
-  Graph graph;
-  CheckGraph(graph);
-  vector<Block> blocks(std::max(old_part.size, new_part.size) / block_size);
-  for (const auto& aop : *aops) {
-    AddInstallOpToGraph(
-        &graph, Vertex::kInvalidIndex, &blocks, aop.op, aop.name);
-  }
-  CheckGraph(graph);
-
-  // Final scratch block (if there's space)
-  Vertex::Index scratch_vertex = Vertex::kInvalidIndex;
-  if (blocks.size() < (partition_size / block_size)) {
-    scratch_vertex = graph.size();
-    graph.emplace_back();
-    size_t scratch_blocks = (partition_size / block_size) - blocks.size();
-    LOG(INFO) << "Added " << scratch_blocks << " scratch space blocks.";
-    CreateScratchNode(blocks.size(), scratch_blocks, &graph.back());
-  }
-  CheckGraph(graph);
-
-  LOG(INFO) << "Creating edges...";
-  CreateEdges(&graph, blocks);
-  LOG(INFO) << "Done creating edges";
-  CheckGraph(graph);
-
-  vector<Vertex::Index> final_order;
-  TEST_AND_RETURN_FALSE(ConvertGraphToDag(
-      &graph, new_part.path, blob_file, &final_order, scratch_vertex));
-
-  // Copy operations over to the |aops| vector in the final_order generated by
-  // the topological sort.
-  aops->clear();
-  aops->reserve(final_order.size());
-  for (const Vertex::Index vertex_index : final_order) {
-    const Vertex& vertex = graph[vertex_index];
-    aops->push_back(vertex.aop);
-  }
-  return true;
-}
-
-bool InplaceGenerator::GenerateOperations(const PayloadGenerationConfig& config,
-                                          const PartitionConfig& old_part,
-                                          const PartitionConfig& new_part,
-                                          BlobFileWriter* blob_file,
-                                          vector<AnnotatedOperation>* aops) {
-  TEST_AND_RETURN_FALSE(old_part.name == new_part.name);
-  TEST_AND_RETURN_FALSE(config.version.major == kInPlacePayloadVersion.major);
-  TEST_AND_RETURN_FALSE(config.version.minor == kInPlacePayloadVersion.minor);
-
-  ssize_t hard_chunk_blocks =
-      (config.hard_chunk_size == -1
-           ? -1
-           : config.hard_chunk_size / config.block_size);
-  size_t soft_chunk_blocks = config.soft_chunk_size / config.block_size;
-  uint64_t partition_size = new_part.size;
-  if (new_part.name == kPartitionNameRoot)
-    partition_size = config.rootfs_partition_size;
-
-  LOG(INFO) << "Delta compressing " << new_part.name << " partition...";
-  TEST_AND_RETURN_FALSE(diff_utils::DeltaReadPartition(aops,
-                                                       old_part,
-                                                       new_part,
-                                                       hard_chunk_blocks,
-                                                       soft_chunk_blocks,
-                                                       config.version,
-                                                       blob_file));
-  LOG(INFO) << "Done reading " << new_part.name;
-
-  TEST_AND_RETURN_FALSE(ResolveReadAfterWriteDependencies(
-      old_part, new_part, partition_size, config.block_size, blob_file, aops));
-  LOG(INFO) << "Done reordering " << new_part.name;
-  return true;
-}
-
-};  // namespace chromeos_update_engine
diff --git a/payload_generator/inplace_generator.h b/payload_generator/inplace_generator.h
deleted file mode 100644
index e7298d2..0000000
--- a/payload_generator/inplace_generator.h
+++ /dev/null
@@ -1,240 +0,0 @@
-//
-// Copyright (C) 2015 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//      http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_INPLACE_GENERATOR_H_
-#define UPDATE_ENGINE_PAYLOAD_GENERATOR_INPLACE_GENERATOR_H_
-
-#include <map>
-#include <set>
-#include <string>
-#include <vector>
-
-#include "update_engine/payload_generator/blob_file_writer.h"
-#include "update_engine/payload_generator/delta_diff_generator.h"
-#include "update_engine/payload_generator/graph_types.h"
-#include "update_engine/payload_generator/operations_generator.h"
-
-// InplaceGenerator contains all functionality related to the inplace algorithm
-// for generating update payloads. These are the functions used when delta minor
-// version is 1.
-
-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 InplaceGenerator : public OperationsGenerator {
- 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;
-  };
-
-  InplaceGenerator() = default;
-
-  // Checks all the operations in the graph have a type assigned.
-  static void CheckGraph(const Graph& graph);
-
-  // 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);
-
-  // 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);
-
-  // 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(
-      const std::vector<Vertex::Index>& op_indexes,
-      std::vector<std::vector<Vertex::Index>::size_type>* reverse_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(const std::vector<Vertex::Index>& op_indexes,
-                                  std::vector<CutEdgeVertexes>* cuts);
-
-  // 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 MoveAndSortFullOpsToBack(Graph* graph,
-                                       std::vector<Vertex::Index>* op_indexes);
-
-  // 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);
-
-  // 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_part,
-      BlobFileWriter* blob_file,
-      std::vector<Vertex::Index>* op_indexes,
-      std::vector<std::vector<Vertex::Index>::size_type>* reverse_op_indexes,
-      const std::vector<CutEdgeVertexes>& cuts);
-
-  // 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_part,
-                                 BlobFileWriter* blob_file);
-
-  // 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_part,
-                                BlobFileWriter* blob_file,
-                                std::vector<Vertex::Index>* final_order,
-                                Vertex::Index scratch_vertex);
-
-  // 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);
-
-  // 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 InstallOperation& operation,
-                                         const Graph& graph,
-                                         Vertex::Index vertex,
-                                         std::vector<Block>* blocks);
-
-  // Add a vertex (if |existing_vertex| is kInvalidVertex) or update an
-  // |existing_vertex| with the passed |operation|.
-  // This method will also register the vertex as the reader or writer of the
-  // blocks involved in the operation updating the |blocks| vector. The
-  // |op_name| associated with the Vertex is used for logging purposes.
-  static bool AddInstallOpToGraph(Graph* graph,
-                                  Vertex::Index existing_vertex,
-                                  std::vector<Block>* blocks,
-                                  const InstallOperation& operation,
-                                  const std::string& op_name);
-
-  // Apply the transformation stored in |the_map| to the |collection| vector
-  // replacing the map keys found in |collection| with its associated value in
-  // |the_map|.
-  static void ApplyMap(std::vector<uint64_t>* collection,
-                       const std::map<uint64_t, uint64_t>& the_map);
-
-  // Resolve all read-after-write dependencies in the operation list |aops|. The
-  // operations in |aops| are such that they generate the desired |new_part| if
-  // applied reading always from the original image. This function reorders the
-  // operations and generates new operations when needed to make these
-  // operations produce the same |new_part| result when applied in-place.
-  // The new operations will create blobs in |data_file_fd| and update
-  // the file size pointed by |data_file_size| if needed.
-  // On success, stores the new operations in |aops| in the right order and
-  // returns true.
-  static bool ResolveReadAfterWriteDependencies(
-      const PartitionConfig& old_part,
-      const PartitionConfig& new_part,
-      uint64_t partition_size,
-      size_t block_size,
-      BlobFileWriter* blob_file,
-      std::vector<AnnotatedOperation>* aops);
-
-  // Generate the update payload operations for the given partition using
-  // only operations that read from the target and/or write to the target,
-  // hence, applying the payload "in-place" in the target partition. This method
-  // assumes that the contents of the source image are pre-copied to the target
-  // partition, up to the size of the source image. Use this method to generate
-  // a delta update with the minor version kInPlaceMinorPayloadVersion.
-  // The operations are stored in |aops|. All the offsets in the operations
-  // reference the data written to |blob_file|.
-  bool GenerateOperations(const PayloadGenerationConfig& config,
-                          const PartitionConfig& old_part,
-                          const PartitionConfig& new_part,
-                          BlobFileWriter* blob_file,
-                          std::vector<AnnotatedOperation>* aops) override;
-
- private:
-  DISALLOW_COPY_AND_ASSIGN(InplaceGenerator);
-};
-
-};  // namespace chromeos_update_engine
-
-#endif  // UPDATE_ENGINE_PAYLOAD_GENERATOR_INPLACE_GENERATOR_H_
diff --git a/payload_generator/inplace_generator_unittest.cc b/payload_generator/inplace_generator_unittest.cc
deleted file mode 100644
index 8028f36..0000000
--- a/payload_generator/inplace_generator_unittest.cc
+++ /dev/null
@@ -1,752 +0,0 @@
-//
-// Copyright (C) 2015 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//      http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#include "update_engine/payload_generator/inplace_generator.h"
-
-#include <map>
-#include <memory>
-#include <set>
-#include <sstream>
-#include <string>
-#include <utility>
-#include <vector>
-
-#include <base/format_macros.h>
-#include <base/logging.h>
-#include <base/strings/string_util.h>
-#include <base/strings/stringprintf.h>
-#include <gtest/gtest.h>
-
-#include "update_engine/common/test_utils.h"
-#include "update_engine/common/utils.h"
-#include "update_engine/payload_generator/cycle_breaker.h"
-#include "update_engine/payload_generator/delta_diff_generator.h"
-#include "update_engine/payload_generator/delta_diff_utils.h"
-#include "update_engine/payload_generator/extent_ranges.h"
-#include "update_engine/payload_generator/graph_types.h"
-#include "update_engine/payload_generator/graph_utils.h"
-
-using std::map;
-using std::set;
-using std::string;
-using std::stringstream;
-using std::vector;
-
-namespace chromeos_update_engine {
-
-using Block = InplaceGenerator::Block;
-
-namespace {
-
-void GenVertex(Vertex* out,
-               const vector<Extent>& src_extents,
-               const vector<Extent>& dst_extents,
-               const string& path,
-               InstallOperation::Type type) {
-  out->aop.op.set_type(type);
-  out->aop.name = path;
-  StoreExtents(src_extents, out->aop.op.mutable_src_extents());
-  StoreExtents(dst_extents, out->aop.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) {
-  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() << "}";
-}
-
-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(InstallOperation* op, uint64_t start, uint64_t length) {
-  Extent* extent = op->add_src_extents();
-  extent->set_start_block(start);
-  extent->set_num_blocks(length);
-}
-
-}  // namespace
-
-class InplaceGeneratorTest : public ::testing::Test {
- protected:
-  // Initialize |blob_path_|, |blob_file_size_| and |blob_file_fd_| variables
-  // with a new blob file. The file is closed and removed automatically when
-  // the test finishes.
-  void CreateBlobFile() {
-    // blob_fd_closer_ takes a pointer to blob_fd_. Make sure we destroy a
-    // previous instance before overriding blob_fd_.
-    blob_fd_closer_.reset();
-    EXPECT_TRUE(utils::MakeTempFile(
-        "InplaceGenerator_blob_file.XXXXXX", &blob_path_, &blob_fd_));
-    blob_path_unlinker_.reset(new ScopedPathUnlinker(blob_path_));
-    blob_fd_closer_.reset(new ScopedFdCloser(&blob_fd_));
-    blob_file_size_ = 0;
-    EXPECT_GE(blob_fd_, 0);
-    blob_file_.reset(new BlobFileWriter(blob_fd_, &blob_file_size_));
-  }
-
-  // Dump the list of operations |aops| in case of test failure.
-  void DumpAopsOnFailure(const vector<AnnotatedOperation>& aops) {
-    if (HasNonfatalFailure()) {
-      LOG(INFO) << "Result operation list:";
-      for (const auto& aop : aops) {
-        LOG(INFO) << aop;
-      }
-    }
-  }
-
-  // Blob file name, file descriptor and file size used to store operation
-  // blobs.
-  string blob_path_;
-  int blob_fd_{-1};
-  off_t blob_file_size_{0};
-  std::unique_ptr<BlobFileWriter> blob_file_;
-  std::unique_ptr<ScopedPathUnlinker> blob_path_unlinker_;
-  std::unique_ptr<ScopedFdCloser> blob_fd_closer_;
-};
-
-TEST_F(InplaceGeneratorTest, BlockDefaultValues) {
-  // Tests that a Block is initialized with the default values as a
-  // Vertex::kInvalidIndex. This is required by the delta generators.
-  Block block;
-  EXPECT_EQ(Vertex::kInvalidIndex, block.reader);
-  EXPECT_EQ(Vertex::kInvalidIndex, block.writer);
-}
-
-TEST_F(InplaceGeneratorTest, 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;
-  InstallOperation& op = vertex.aop.op;
-  OpAppendExtent(&op, 4, 3);
-  OpAppendExtent(&op, kSparseHole, 4);  // Sparse hole in file
-  OpAppendExtent(&op, 3, 1);
-  OpAppendExtent(&op, 7, 3);
-
-  InplaceGenerator::SubstituteBlocks(&vertex, remove_blocks, replace_blocks);
-
-  EXPECT_EQ(7, op.src_extents_size());
-  EXPECT_EQ(11U, op.src_extents(0).start_block());
-  EXPECT_EQ(1U, op.src_extents(0).num_blocks());
-  EXPECT_EQ(13U, op.src_extents(1).start_block());
-  EXPECT_EQ(1U, op.src_extents(1).num_blocks());
-  EXPECT_EQ(6U, op.src_extents(2).start_block());
-  EXPECT_EQ(1U, op.src_extents(2).num_blocks());
-  EXPECT_EQ(kSparseHole, op.src_extents(3).start_block());
-  EXPECT_EQ(4U, op.src_extents(3).num_blocks());
-  EXPECT_EQ(10U, op.src_extents(4).start_block());
-  EXPECT_EQ(1U, op.src_extents(4).num_blocks());
-  EXPECT_EQ(14U, op.src_extents(5).start_block());
-  EXPECT_EQ(1U, op.src_extents(5).num_blocks());
-  EXPECT_EQ(8U, op.src_extents(6).start_block());
-  EXPECT_EQ(2U, op.src_extents(6).num_blocks());
-}
-
-TEST_F(InplaceGeneratorTest, CutEdgesTest) {
-  Graph graph;
-  vector<Block> blocks(9);
-
-  // Create nodes in graph
-  {
-    graph.resize(graph.size() + 1);
-    graph.back().aop.op.set_type(InstallOperation::MOVE);
-    // Reads from blocks 3, 5, 7
-    vector<Extent> extents;
-    AppendBlockToExtents(&extents, 3);
-    AppendBlockToExtents(&extents, 5);
-    AppendBlockToExtents(&extents, 7);
-    StoreExtents(extents, graph.back().aop.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();
-    AppendBlockToExtents(&extents, 1);
-    AppendBlockToExtents(&extents, 2);
-    AppendBlockToExtents(&extents, 4);
-    StoreExtents(extents, graph.back().aop.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().aop.op.set_type(InstallOperation::MOVE);
-    // Reads from blocks 1, 2, 4
-    vector<Extent> extents;
-    AppendBlockToExtents(&extents, 1);
-    AppendBlockToExtents(&extents, 2);
-    AppendBlockToExtents(&extents, 4);
-    StoreExtents(extents, graph.back().aop.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();
-    AppendBlockToExtents(&extents, 3);
-    AppendBlockToExtents(&extents, 5);
-    AppendBlockToExtents(&extents, 6);
-    StoreExtents(extents, graph.back().aop.op.mutable_dst_extents());
-    blocks[3].writer = graph.size() - 1;
-    blocks[5].writer = graph.size() - 1;
-    blocks[6].writer = graph.size() - 1;
-  }
-
-  // Create edges
-  InplaceGenerator::CreateEdges(&graph, blocks);
-
-  // Find cycles
-  CycleBreaker cycle_breaker;
-  set<Edge> cut_edges;
-  cycle_breaker.BreakCycles(graph, &cut_edges);
-
-  EXPECT_EQ(1U, cut_edges.size());
-  EXPECT_TRUE(cut_edges.end() !=
-              cut_edges.find(std::pair<Vertex::Index, Vertex::Index>(1, 0)));
-
-  vector<CutEdgeVertexes> cuts;
-  EXPECT_TRUE(InplaceGenerator::CutEdges(&graph, cut_edges, &cuts));
-
-  EXPECT_EQ(3U, graph.size());
-
-  // Check new node in graph:
-  EXPECT_EQ(InstallOperation::MOVE, graph.back().aop.op.type());
-  EXPECT_EQ(2, graph.back().aop.op.src_extents_size());
-  EXPECT_EQ(1, graph.back().aop.op.dst_extents_size());
-  EXPECT_EQ(kTempBlockStart, graph.back().aop.op.dst_extents(0).start_block());
-  EXPECT_EQ(2U, graph.back().aop.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].aop.op.src_extents_size());
-  EXPECT_EQ(kTempBlockStart, graph[0].aop.op.src_extents(0).start_block());
-  EXPECT_EQ(2U, graph[0].aop.op.src_extents(0).num_blocks());
-  EXPECT_EQ(7U, graph[0].aop.op.src_extents(1).start_block());
-  EXPECT_EQ(1U, graph[0].aop.op.src_extents(1).num_blocks());
-
-  // And that the old dst extents haven't changed
-  EXPECT_EQ(2, graph[0].aop.op.dst_extents_size());
-  EXPECT_EQ(1U, graph[0].aop.op.dst_extents(0).start_block());
-  EXPECT_EQ(2U, graph[0].aop.op.dst_extents(0).num_blocks());
-  EXPECT_EQ(4U, graph[0].aop.op.dst_extents(1).start_block());
-  EXPECT_EQ(1U, graph[0].aop.op.dst_extents(1).num_blocks());
-
-  // Ensure it only depends on the next node and the new temp node
-  EXPECT_EQ(2U, 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].aop.op.src_extents_size());
-  EXPECT_EQ(1U, graph[1].aop.op.src_extents(0).start_block());
-  EXPECT_EQ(2U, graph[1].aop.op.src_extents(0).num_blocks());
-  EXPECT_EQ(4U, graph[1].aop.op.src_extents(1).start_block());
-  EXPECT_EQ(1U, graph[1].aop.op.src_extents(1).num_blocks());
-
-  EXPECT_EQ(2, graph[1].aop.op.dst_extents_size());
-  EXPECT_EQ(3U, graph[1].aop.op.dst_extents(0).start_block());
-  EXPECT_EQ(1U, graph[1].aop.op.dst_extents(0).num_blocks());
-  EXPECT_EQ(5U, graph[1].aop.op.dst_extents(1).start_block());
-  EXPECT_EQ(2U, graph[1].aop.op.dst_extents(1).num_blocks());
-
-  // Ensure it only depends on the next node
-  EXPECT_EQ(1U, graph[1].out_edges.size());
-  EXPECT_TRUE(graph[1].out_edges.end() != graph[1].out_edges.find(2));
-}
-
-TEST_F(InplaceGeneratorTest, AssignTempBlocksReuseTest) {
-  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), "", InstallOperation::MOVE);
-  GenVertex(&graph[1],
-            VectOfExt(tmp, 1),
-            VectOfExt(0, 1),
-            "",
-            InstallOperation::MOVE);
-  GenVertex(&graph[2],
-            VectOfExt(1, 1),
-            VectOfExt(tmp, 1),
-            "",
-            InstallOperation::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), "", InstallOperation::MOVE);
-  GenVertex(
-      &graph[4], VectOfExt(6, 1), VectOfExt(7, 1), "", InstallOperation::MOVE);
-  GenVertex(&graph[5],
-            VectOfExt(tmp, 3),
-            VectOfExt(4, 3),
-            kFilename,
-            InstallOperation::MOVE);
-  GenVertex(&graph[6],
-            VectOfExt(2, 2),
-            VectOfExt(tmp, 2),
-            "",
-            InstallOperation::MOVE);
-  GenVertex(&graph[7],
-            VectOfExt(7, 1),
-            VectOfExt(tmp + 2, 1),
-            "",
-            InstallOperation::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), "", InstallOperation::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;
-  InplaceGenerator::GenerateReverseTopoOrderMap(op_indexes,
-                                                &reverse_op_indexes);
-
-  CreateBlobFile();
-  EXPECT_TRUE(InplaceGenerator::AssignTempBlocks(&graph,
-                                                 "/dev/zero",
-                                                 blob_file_.get(),
-                                                 &op_indexes,
-                                                 &reverse_op_indexes,
-                                                 cuts));
-  EXPECT_FALSE(graph[6].valid);
-  EXPECT_FALSE(graph[7].valid);
-  EXPECT_EQ(1, graph[1].aop.op.src_extents_size());
-  EXPECT_EQ(2U, graph[1].aop.op.src_extents(0).start_block());
-  EXPECT_EQ(1U, graph[1].aop.op.src_extents(0).num_blocks());
-  EXPECT_EQ(InstallOperation::REPLACE_BZ, graph[5].aop.op.type());
-}
-
-TEST_F(InplaceGeneratorTest, MoveAndSortFullOpsToBackTest) {
-  Graph graph(4);
-  graph[0].aop.name = "A";
-  graph[0].aop.op.set_type(InstallOperation::REPLACE);
-  graph[1].aop.name = "B";
-  graph[1].aop.op.set_type(InstallOperation::BSDIFF);
-  graph[2].aop.name = "C";
-  graph[2].aop.op.set_type(InstallOperation::REPLACE_BZ);
-  graph[3].aop.name = "D";
-  graph[3].aop.op.set_type(InstallOperation::MOVE);
-
-  vector<Vertex::Index> vect(graph.size());
-
-  for (vector<Vertex::Index>::size_type i = 0; i < vect.size(); ++i) {
-    vect[i] = i;
-  }
-  InplaceGenerator::MoveAndSortFullOpsToBack(&graph, &vect);
-  EXPECT_EQ(vect.size(), graph.size());
-  EXPECT_EQ(graph[vect[0]].aop.name, "B");
-  EXPECT_EQ(graph[vect[1]].aop.name, "D");
-  EXPECT_EQ(graph[vect[2]].aop.name, "A");
-  EXPECT_EQ(graph[vect[3]].aop.name, "C");
-}
-
-TEST_F(InplaceGeneratorTest, AssignTempBlocksTest) {
-  Graph graph(9);
-  const vector<Extent> empt;  // empty
-  const string kFilename = "/foo";
-
-  // Some scratch space:
-  GenVertex(&graph[0], empt, VectOfExt(200, 1), "", InstallOperation::REPLACE);
-  GenVertex(&graph[1], empt, VectOfExt(210, 10), "", InstallOperation::REPLACE);
-  GenVertex(&graph[2], empt, VectOfExt(220, 1), "", InstallOperation::REPLACE);
-
-  // A cycle that requires 10 blocks to break:
-  GenVertex(&graph[3],
-            VectOfExt(10, 11),
-            VectOfExt(0, 9),
-            "",
-            InstallOperation::BSDIFF);
-  graph[3].out_edges[4] = EdgeWithReadDep(VectOfExt(0, 9));
-  GenVertex(&graph[4],
-            VectOfExt(0, 9),
-            VectOfExt(10, 11),
-            "",
-            InstallOperation::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),
-            "",
-            InstallOperation::BSDIFF);
-  graph[5].out_edges[6] = EdgeWithReadDep(VectOfExt(30, 10));
-  GenVertex(&graph[6],
-            VectOfExt(30, 10),
-            VectOfExt(40, 11),
-            "",
-            InstallOperation::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),
-            "",
-            InstallOperation::BSDIFF);
-  graph[7].out_edges[8] = EdgeWithReadDep(VectOfExt(60, 40));
-  GenVertex(&graph[8],
-            VectOfExt(60, 40),
-            VectOfExt(120, 50),
-            kFilename,
-            InstallOperation::BSDIFF);
-  graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
-
-  graph_utils::DumpGraph(graph);
-
-  vector<Vertex::Index> final_order;
-
-  CreateBlobFile();
-  EXPECT_TRUE(InplaceGenerator::ConvertGraphToDag(&graph,
-                                                  "/dev/zero",
-                                                  blob_file_.get(),
-                                                  &final_order,
-                                                  Vertex::kInvalidIndex));
-
-  Graph expected_graph(12);
-  GenVertex(&expected_graph[0],
-            empt,
-            VectOfExt(200, 1),
-            "",
-            InstallOperation::REPLACE);
-  GenVertex(&expected_graph[1],
-            empt,
-            VectOfExt(210, 10),
-            "",
-            InstallOperation::REPLACE);
-  GenVertex(&expected_graph[2],
-            empt,
-            VectOfExt(220, 1),
-            "",
-            InstallOperation::REPLACE);
-  GenVertex(&expected_graph[3],
-            VectOfExt(10, 11),
-            VectOfExt(0, 9),
-            "",
-            InstallOperation::BSDIFF);
-  expected_graph[3].out_edges[9] = EdgeWithReadDep(VectOfExt(0, 9));
-  GenVertex(&expected_graph[4],
-            VectOfExt(60, 9),
-            VectOfExt(10, 11),
-            "",
-            InstallOperation::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),
-            "",
-            InstallOperation::BSDIFF);
-  expected_graph[5].out_edges[10] = EdgeWithReadDep(VectOfExt(30, 10));
-
-  GenVertex(&expected_graph[6],
-            VectOfExt(60, 10),
-            VectOfExt(40, 11),
-            "",
-            InstallOperation::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),
-            "",
-            InstallOperation::BSDIFF);
-  expected_graph[7].out_edges[6] = EdgeWithReadDep(VectOfExt(60, 10));
-
-  GenVertex(&expected_graph[8],
-            empt,
-            VectOfExt(0, 50),
-            "/foo",
-            InstallOperation::REPLACE_BZ);
-  expected_graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
-
-  GenVertex(&expected_graph[9],
-            VectOfExt(0, 9),
-            VectOfExt(60, 9),
-            "",
-            InstallOperation::MOVE);
-
-  GenVertex(&expected_graph[10],
-            VectOfExt(30, 10),
-            VectOfExt(60, 10),
-            "",
-            InstallOperation::MOVE);
-  expected_graph[10].out_edges[4] = EdgeWithReadDep(VectOfExt(60, 9));
-
-  EXPECT_EQ(12U, 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_F(InplaceGeneratorTest, CreateScratchNodeTest) {
-  Vertex vertex;
-  InplaceGenerator::CreateScratchNode(12, 34, &vertex);
-  EXPECT_EQ(InstallOperation::REPLACE_BZ, vertex.aop.op.type());
-  EXPECT_EQ(0U, vertex.aop.op.data_offset());
-  EXPECT_EQ(0U, vertex.aop.op.data_length());
-  EXPECT_EQ(1, vertex.aop.op.dst_extents_size());
-  EXPECT_EQ(12U, vertex.aop.op.dst_extents(0).start_block());
-  EXPECT_EQ(34U, vertex.aop.op.dst_extents(0).num_blocks());
-}
-
-TEST_F(InplaceGeneratorTest, ApplyMapTest) {
-  vector<uint64_t> collection = {1, 2, 3, 4, 6};
-  vector<uint64_t> expected_values = {1, 2, 5, 4, 8};
-  map<uint64_t, uint64_t> value_map;
-  value_map[3] = 5;
-  value_map[6] = 8;
-  value_map[5] = 10;
-
-  InplaceGenerator::ApplyMap(&collection, value_map);
-  EXPECT_EQ(expected_values, collection);
-}
-
-// We can't produce MOVE operations with a source or destination in the block 0.
-// This test checks that the cycle breaker procedure doesn't produce such
-// operations.
-TEST_F(InplaceGeneratorTest, ResolveReadAfterWriteDependenciesAvoidMoveToZero) {
-  size_t block_size = 4096;
-  size_t num_blocks = 4;
-  vector<AnnotatedOperation> aops;
-
-  // Create a REPLACE_BZ for block 0, and a circular dependency among all other
-  // blocks. This situation would prefer to issue a MOVE to scratch space and
-  // the only available block is 0.
-  aops.emplace_back();
-  aops.back().name = base::StringPrintf("<bz-block-0>");
-  aops.back().op.set_type(InstallOperation::REPLACE_BZ);
-  StoreExtents({ExtentForRange(0, 1)}, aops.back().op.mutable_dst_extents());
-
-  for (size_t i = 1; i < num_blocks; i++) {
-    AnnotatedOperation aop;
-    aop.name = base::StringPrintf("<op-%" PRIuS ">", i);
-    aop.op.set_type(InstallOperation::BSDIFF);
-    StoreExtents({ExtentForRange(1 + i % (num_blocks - 1), 1)},
-                 aop.op.mutable_src_extents());
-    StoreExtents({ExtentForRange(i, 1)}, aop.op.mutable_dst_extents());
-    aops.push_back(aop);
-  }
-
-  PartitionConfig part("part");
-  part.path = "/dev/zero";
-  part.size = num_blocks * block_size;
-
-  CreateBlobFile();
-
-  // We ran two tests here. The first one without enough blocks for the scratch
-  // space, forcing it to create a new full operation and the second case with
-  // one extra block in the partition that can be used for the move operation.
-  for (const auto part_blocks : vector<uint64_t>{num_blocks, num_blocks + 1}) {
-    SCOPED_TRACE(
-        base::StringPrintf("Using partition_blocks=%" PRIu64, part_blocks));
-    vector<AnnotatedOperation> result_aops = aops;
-    EXPECT_TRUE(InplaceGenerator::ResolveReadAfterWriteDependencies(
-        part,
-        part,
-        part_blocks * block_size,
-        block_size,
-        blob_file_.get(),
-        &result_aops));
-
-    size_t full_ops = 0;
-    for (const auto& aop : result_aops) {
-      if (diff_utils::IsAReplaceOperation(aop.op.type()))
-        full_ops++;
-
-      if (aop.op.type() != InstallOperation::MOVE)
-        continue;
-      for (const Extent& extent : aop.op.src_extents()) {
-        EXPECT_NE(0U, extent.start_block())
-            << "On src extents for aop: " << aop;
-      }
-      for (const Extent& extent : aop.op.dst_extents()) {
-        EXPECT_NE(0U, extent.start_block())
-            << "On dst extents for aop: " << aop;
-      }
-    }
-
-    // If there's extra space in the partition, it should not use a new full
-    // operation for it.
-    EXPECT_EQ(part_blocks == num_blocks ? 2U : 1U, full_ops);
-
-    DumpAopsOnFailure(result_aops);
-  }
-}
-
-// Test that we can shrink a filesystem and break cycles.
-TEST_F(InplaceGeneratorTest, ResolveReadAfterWriteDependenciesShrinkData) {
-  size_t block_size = 4096;
-  size_t old_blocks = 10;
-  size_t new_blocks = 8;
-  vector<AnnotatedOperation> aops;
-
-  // Create a loop using the blocks 1-6 and one other operation writing to the
-  // block 7 from outside the new partition. The loop in the blocks 1-6 uses
-  // two-block operations, so it needs two blocks of scratch space. It can't use
-  // the block 0 as scratch space (see previous test) and it can't use the
-  // blocks 7 or 8 due the last move operation.
-
-  aops.emplace_back();
-  aops.back().name = base::StringPrintf("<bz-block-0>");
-  aops.back().op.set_type(InstallOperation::REPLACE_BZ);
-  StoreExtents({ExtentForRange(0, 1)}, aops.back().op.mutable_dst_extents());
-
-  const size_t num_ops = 3;
-  for (size_t i = 0; i < num_ops; i++) {
-    AnnotatedOperation aop;
-    aop.name = base::StringPrintf("<op-%" PRIuS ">", i);
-    aop.op.set_type(InstallOperation::BSDIFF);
-    StoreExtents({ExtentForRange(1 + 2 * i, 2)}, aop.op.mutable_src_extents());
-    StoreExtents({ExtentForRange(1 + 2 * ((i + 1) % num_ops), 2)},
-                 aop.op.mutable_dst_extents());
-    aops.push_back(aop);
-  }
-
-  {
-    AnnotatedOperation aop;
-    aop.name = "<op-shrink>";
-    aop.op.set_type(InstallOperation::BSDIFF);
-    StoreExtents({ExtentForRange(8, 1)}, aop.op.mutable_src_extents());
-    StoreExtents({ExtentForRange(7, 1)}, aop.op.mutable_dst_extents());
-    aops.push_back(aop);
-  }
-
-  PartitionConfig old_part("part");
-  old_part.path = "/dev/zero";
-  old_part.size = old_blocks * block_size;
-
-  PartitionConfig new_part("part");
-  new_part.path = "/dev/zero";
-  new_part.size = new_blocks * block_size;
-
-  CreateBlobFile();
-
-  EXPECT_TRUE(InplaceGenerator::ResolveReadAfterWriteDependencies(
-      old_part,
-      new_part,
-      (old_blocks + 2) * block_size,  // enough scratch space.
-      block_size,
-      blob_file_.get(),
-      &aops));
-
-  size_t full_ops = 0;
-  for (const auto& aop : aops) {
-    if (diff_utils::IsAReplaceOperation(aop.op.type()))
-      full_ops++;
-  }
-  // There should be only one REPLACE* operation, the one we added for block 0.
-  EXPECT_EQ(1U, full_ops);
-
-  // There should be only one MOVE operation, the one used to break the loop
-  // which should write to scratch space past the block 7 (the last block of the
-  // new partition) which is being written later.
-  size_t move_ops = 0;
-  for (const auto& aop : aops) {
-    if (aop.op.type() == InstallOperation::MOVE) {
-      move_ops++;
-      for (const Extent& extent : aop.op.dst_extents()) {
-        EXPECT_LE(7U, extent.start_block())
-            << "On dst extents for aop: " << aop;
-      }
-    }
-  }
-  EXPECT_EQ(1U, move_ops);
-
-  DumpAopsOnFailure(aops);
-}
-
-}  // namespace chromeos_update_engine
diff --git a/payload_generator/payload_file.cc b/payload_generator/payload_file.cc
index a111fd6..69325d7 100644
--- a/payload_generator/payload_file.cc
+++ b/payload_generator/payload_file.cc
@@ -74,11 +74,9 @@
   manifest_.set_block_size(config.block_size);
   manifest_.set_max_timestamp(config.max_timestamp);
 
-  if (major_version_ == kBrilloMajorPayloadVersion) {
-    if (config.target.dynamic_partition_metadata != nullptr)
-      *(manifest_.mutable_dynamic_partition_metadata()) =
-          *(config.target.dynamic_partition_metadata);
-  }
+  if (config.target.dynamic_partition_metadata != nullptr)
+    *(manifest_.mutable_dynamic_partition_metadata()) =
+        *(config.target.dynamic_partition_metadata);
 
   return true;
 }
@@ -86,13 +84,6 @@
 bool PayloadFile::AddPartition(const PartitionConfig& old_conf,
                                const PartitionConfig& new_conf,
                                const vector<AnnotatedOperation>& aops) {
-  // Check partitions order for Chrome OS
-  if (major_version_ == kChromeOSMajorPayloadVersion) {
-    const vector<const char*> part_order = {kPartitionNameRoot,
-                                            kPartitionNameKernel};
-    TEST_AND_RETURN_FALSE(part_vec_.size() < part_order.size());
-    TEST_AND_RETURN_FALSE(new_conf.name == part_order[part_vec_.size()]);
-  }
   Partition part;
   part.name = new_conf.name;
   part.aops = aops;
@@ -134,66 +125,45 @@
   }
 
   // Copy the operations and partition info from the part_vec_ to the manifest.
-  manifest_.clear_install_operations();
-  manifest_.clear_kernel_install_operations();
   manifest_.clear_partitions();
   for (const auto& part : part_vec_) {
-    if (major_version_ == kBrilloMajorPayloadVersion) {
-      PartitionUpdate* partition = manifest_.add_partitions();
-      partition->set_partition_name(part.name);
-      if (part.postinstall.run) {
-        partition->set_run_postinstall(true);
-        if (!part.postinstall.path.empty())
-          partition->set_postinstall_path(part.postinstall.path);
-        if (!part.postinstall.filesystem_type.empty())
-          partition->set_filesystem_type(part.postinstall.filesystem_type);
-        partition->set_postinstall_optional(part.postinstall.optional);
+    PartitionUpdate* partition = manifest_.add_partitions();
+    partition->set_partition_name(part.name);
+    if (part.postinstall.run) {
+      partition->set_run_postinstall(true);
+      if (!part.postinstall.path.empty())
+        partition->set_postinstall_path(part.postinstall.path);
+      if (!part.postinstall.filesystem_type.empty())
+        partition->set_filesystem_type(part.postinstall.filesystem_type);
+      partition->set_postinstall_optional(part.postinstall.optional);
+    }
+    if (!part.verity.IsEmpty()) {
+      if (part.verity.hash_tree_extent.num_blocks() != 0) {
+        *partition->mutable_hash_tree_data_extent() =
+            part.verity.hash_tree_data_extent;
+        *partition->mutable_hash_tree_extent() = part.verity.hash_tree_extent;
+        partition->set_hash_tree_algorithm(part.verity.hash_tree_algorithm);
+        if (!part.verity.hash_tree_salt.empty())
+          partition->set_hash_tree_salt(part.verity.hash_tree_salt.data(),
+                                        part.verity.hash_tree_salt.size());
       }
-      if (!part.verity.IsEmpty()) {
-        if (part.verity.hash_tree_extent.num_blocks() != 0) {
-          *partition->mutable_hash_tree_data_extent() =
-              part.verity.hash_tree_data_extent;
-          *partition->mutable_hash_tree_extent() = part.verity.hash_tree_extent;
-          partition->set_hash_tree_algorithm(part.verity.hash_tree_algorithm);
-          if (!part.verity.hash_tree_salt.empty())
-            partition->set_hash_tree_salt(part.verity.hash_tree_salt.data(),
-                                          part.verity.hash_tree_salt.size());
-        }
-        if (part.verity.fec_extent.num_blocks() != 0) {
-          *partition->mutable_fec_data_extent() = part.verity.fec_data_extent;
-          *partition->mutable_fec_extent() = part.verity.fec_extent;
-          partition->set_fec_roots(part.verity.fec_roots);
-        }
-      }
-      for (const AnnotatedOperation& aop : part.aops) {
-        *partition->add_operations() = aop.op;
-      }
-      if (part.old_info.has_size() || part.old_info.has_hash())
-        *(partition->mutable_old_partition_info()) = part.old_info;
-      if (part.new_info.has_size() || part.new_info.has_hash())
-        *(partition->mutable_new_partition_info()) = part.new_info;
-    } else {
-      // major_version_ == kChromeOSMajorPayloadVersion
-      if (part.name == kPartitionNameKernel) {
-        for (const AnnotatedOperation& aop : part.aops)
-          *manifest_.add_kernel_install_operations() = aop.op;
-        if (part.old_info.has_size() || part.old_info.has_hash())
-          *manifest_.mutable_old_kernel_info() = part.old_info;
-        if (part.new_info.has_size() || part.new_info.has_hash())
-          *manifest_.mutable_new_kernel_info() = part.new_info;
-      } else {
-        for (const AnnotatedOperation& aop : part.aops)
-          *manifest_.add_install_operations() = aop.op;
-        if (part.old_info.has_size() || part.old_info.has_hash())
-          *manifest_.mutable_old_rootfs_info() = part.old_info;
-        if (part.new_info.has_size() || part.new_info.has_hash())
-          *manifest_.mutable_new_rootfs_info() = part.new_info;
+      if (part.verity.fec_extent.num_blocks() != 0) {
+        *partition->mutable_fec_data_extent() = part.verity.fec_data_extent;
+        *partition->mutable_fec_extent() = part.verity.fec_extent;
+        partition->set_fec_roots(part.verity.fec_roots);
       }
     }
+    for (const AnnotatedOperation& aop : part.aops) {
+      *partition->add_operations() = aop.op;
+    }
+    if (part.old_info.has_size() || part.old_info.has_hash())
+      *(partition->mutable_old_partition_info()) = part.old_info;
+    if (part.new_info.has_size() || part.new_info.has_hash())
+      *(partition->mutable_new_partition_info()) = part.new_info;
   }
 
   // Signatures appear at the end of the blobs. Note the offset in the
-  // manifest_.
+  // |manifest_|.
   uint64_t signature_blob_length = 0;
   if (!private_key_path.empty()) {
     TEST_AND_RETURN_FALSE(PayloadSigner::SignatureBlobLength(
@@ -201,7 +171,6 @@
     PayloadSigner::AddSignatureToManifest(
         next_blob_offset,
         signature_blob_length,
-        major_version_ == kChromeOSMajorPayloadVersion,
         &manifest_);
   }
 
@@ -229,18 +198,14 @@
   TEST_AND_RETURN_FALSE(
       WriteUint64AsBigEndian(&writer, serialized_manifest.size()));
 
-  // Write metadata signature size.
-  uint32_t metadata_signature_size = 0;
-  if (major_version_ == kBrilloMajorPayloadVersion) {
-    // Metadata signature has the same size as payload signature, because they
-    // are both the same kind of signature for the same kind of hash.
-    uint32_t metadata_signature_size = htobe32(signature_blob_length);
-    TEST_AND_RETURN_FALSE_ERRNO(writer.Write(&metadata_signature_size,
-                                             sizeof(metadata_signature_size)));
-    metadata_size += sizeof(metadata_signature_size);
-    // Set correct size instead of big endian size.
-    metadata_signature_size = signature_blob_length;
-  }
+  // Metadata signature has the same size as payload signature, because they
+  // are both the same kind of signature for the same kind of hash.
+  uint32_t metadata_signature_size = htobe32(signature_blob_length);
+  TEST_AND_RETURN_FALSE_ERRNO(
+      writer.Write(&metadata_signature_size, sizeof(metadata_signature_size)));
+  metadata_size += sizeof(metadata_signature_size);
+  // Set correct size instead of big endian size.
+  metadata_signature_size = signature_blob_length;
 
   // Write protobuf
   LOG(INFO) << "Writing final delta file protobuf... "
@@ -249,8 +214,7 @@
       writer.Write(serialized_manifest.data(), serialized_manifest.size()));
 
   // Write metadata signature blob.
-  if (major_version_ == kBrilloMajorPayloadVersion &&
-      !private_key_path.empty()) {
+  if (!private_key_path.empty()) {
     brillo::Blob metadata_hash;
     TEST_AND_RETURN_FALSE(HashCalculator::RawHashOfFile(
         payload_file, metadata_size, &metadata_hash));
@@ -261,7 +225,7 @@
         writer.Write(metadata_signature.data(), metadata_signature.size()));
   }
 
-  // Append the data blobs
+  // 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);
diff --git a/payload_generator/payload_generation_config.cc b/payload_generator/payload_generation_config.cc
index 88cca30..b653a03 100644
--- a/payload_generator/payload_generation_config.cc
+++ b/payload_generator/payload_generation_config.cc
@@ -32,6 +32,7 @@
 #include "update_engine/payload_generator/ext2_filesystem.h"
 #include "update_engine/payload_generator/mapfile_filesystem.h"
 #include "update_engine/payload_generator/raw_filesystem.h"
+#include "update_engine/payload_generator/squashfs_filesystem.h"
 
 using std::string;
 
@@ -86,6 +87,14 @@
     return true;
   }
 
+  fs_interface = SquashfsFilesystem::CreateFromFile(path,
+                                                    /*extract_deflates=*/true,
+                                                    /*load_settings=*/true);
+  if (fs_interface) {
+    TEST_AND_RETURN_FALSE(fs_interface->GetBlockSize() == kBlockSize);
+    return true;
+  }
+
   // Fall back to a RAW filesystem.
   TEST_AND_RETURN_FALSE(size % kBlockSize == 0);
   fs_interface = RawFilesystem::Create(
@@ -219,10 +228,8 @@
 }
 
 bool PayloadVersion::Validate() const {
-  TEST_AND_RETURN_FALSE(major == kChromeOSMajorPayloadVersion ||
-                        major == kBrilloMajorPayloadVersion);
+  TEST_AND_RETURN_FALSE(major == kBrilloMajorPayloadVersion);
   TEST_AND_RETURN_FALSE(minor == kFullPayloadMinorVersion ||
-                        minor == kInPlaceMinorPayloadVersion ||
                         minor == kSourceMinorPayloadVersion ||
                         minor == kOpSrcHashMinorPayloadVersion ||
                         minor == kBrotliBsdiffMinorPayloadVersion ||
@@ -237,13 +244,10 @@
     case InstallOperation::REPLACE:
     case InstallOperation::REPLACE_BZ:
       // These operations were included in the original payload format.
-      return true;
-
     case InstallOperation::REPLACE_XZ:
-      // These operations are included in the major version used in Brillo, but
-      // can also be used with minor version 3 or newer.
-      return major == kBrilloMajorPayloadVersion ||
-             minor >= kOpSrcHashMinorPayloadVersion;
+      // These operations are included minor version 3 or newer and full
+      // payloads.
+      return true;
 
     case InstallOperation::ZERO:
     case InstallOperation::DISCARD:
@@ -252,14 +256,6 @@
       // them for delta payloads for now.
       return minor >= kBrotliBsdiffMinorPayloadVersion;
 
-    // Delta operations:
-    case InstallOperation::MOVE:
-    case InstallOperation::BSDIFF:
-      // MOVE and BSDIFF were replaced by SOURCE_COPY and SOURCE_BSDIFF and
-      // should not be used in newer delta versions, since the idempotent checks
-      // were removed.
-      return minor == kInPlaceMinorPayloadVersion;
-
     case InstallOperation::SOURCE_COPY:
     case InstallOperation::SOURCE_BSDIFF:
       return minor >= kSourceMinorPayloadVersion;
@@ -269,6 +265,10 @@
 
     case InstallOperation::PUFFDIFF:
       return minor >= kPuffdiffMinorPayloadVersion;
+
+    case InstallOperation::MOVE:
+    case InstallOperation::BSDIFF:
+      NOTREACHED();
   }
   return false;
 }
@@ -277,10 +277,6 @@
   return minor != kFullPayloadMinorVersion;
 }
 
-bool PayloadVersion::InplaceUpdate() const {
-  return minor == kInPlaceMinorPayloadVersion;
-}
-
 bool PayloadGenerationConfig::Validate() const {
   TEST_AND_RETURN_FALSE(version.Validate());
   TEST_AND_RETURN_FALSE(version.IsDelta() == is_delta);
@@ -307,11 +303,6 @@
   for (const PartitionConfig& part : target.partitions) {
     TEST_AND_RETURN_FALSE(part.ValidateExists());
     TEST_AND_RETURN_FALSE(part.size % block_size == 0);
-    if (version.minor == kInPlaceMinorPayloadVersion &&
-        part.name == kPartitionNameRoot)
-      TEST_AND_RETURN_FALSE(rootfs_partition_size >= part.size);
-    if (version.major == kChromeOSMajorPayloadVersion)
-      TEST_AND_RETURN_FALSE(part.postinstall.IsEmpty());
     if (version.minor < kVerityMinorPayloadVersion)
       TEST_AND_RETURN_FALSE(part.verity.IsEmpty());
   }
diff --git a/payload_generator/payload_generation_config.h b/payload_generator/payload_generation_config.h
index e90edde..af6f181 100644
--- a/payload_generator/payload_generation_config.h
+++ b/payload_generator/payload_generation_config.h
@@ -173,10 +173,6 @@
   // Whether this payload version is a delta payload.
   bool IsDelta() const;
 
-  // Tells whether the update is done in-place, that is, whether the operations
-  // read and write from the same partition.
-  bool InplaceUpdate() const;
-
   // The major version of the payload.
   uint64_t major;
 
diff --git a/payload_generator/payload_properties.cc b/payload_generator/payload_properties.cc
new file mode 100644
index 0000000..bc82eb7
--- /dev/null
+++ b/payload_generator/payload_properties.cc
@@ -0,0 +1,142 @@
+//
+// Copyright 2019 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+
+#include "update_engine/payload_generator/payload_properties.h"
+
+#include <algorithm>
+#include <string>
+#include <utility>
+#include <vector>
+
+#include <base/json/json_writer.h>
+#include <base/strings/string_util.h>
+#include <base/values.h>
+#include <brillo/data_encoding.h>
+
+#include "update_engine/common/constants.h"
+#include "update_engine/common/hash_calculator.h"
+#include "update_engine/common/utils.h"
+#include "update_engine/payload_consumer/payload_metadata.h"
+#include "update_engine/update_metadata.pb.h"
+
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+namespace {
+// These ones are needed by the GoldenEye.
+const char kPayloadPropertyJsonVersion[] = "version";
+const char kPayloadPropertyJsonPayloadHash[] = "sha256_hex";
+const char kPayloadPropertyJsonMetadataSize[] = "metadata_size";
+const char kPayloadPropertyJsonMetadataSignature[] = "metadata_signature";
+
+// These are needed by the Nebraska and devserver.
+const char kPayloadPropertyJsonPayloadSize[] = "size";
+const char kPayloadPropertyJsonIsDelta[] = "is_delta";
+const char kPayloadPropertyJsonTargetVersion[] = "target_version";
+const char kPayloadPropertyJsonSourceVersion[] = "source_version";
+}  // namespace
+
+PayloadProperties::PayloadProperties(const string& payload_path)
+    : payload_path_(payload_path) {}
+
+bool PayloadProperties::GetPropertiesAsJson(string* json_str) {
+  TEST_AND_RETURN_FALSE(LoadFromPayload());
+
+  base::DictionaryValue properties;
+  properties.SetInteger(kPayloadPropertyJsonVersion, version_);
+  properties.SetInteger(kPayloadPropertyJsonMetadataSize, metadata_size_);
+  properties.SetString(kPayloadPropertyJsonMetadataSignature,
+                       metadata_signatures_);
+  properties.SetInteger(kPayloadPropertyJsonPayloadSize, payload_size_);
+  properties.SetString(kPayloadPropertyJsonPayloadHash, payload_hash_);
+  properties.SetBoolean(kPayloadPropertyJsonIsDelta, is_delta_);
+  properties.SetString(kPayloadPropertyJsonTargetVersion, target_version_);
+  if (is_delta_) {
+    properties.SetString(kPayloadPropertyJsonSourceVersion, source_version_);
+  }
+
+  return base::JSONWriter::Write(properties, json_str);
+}
+
+bool PayloadProperties::GetPropertiesAsKeyValue(string* key_value_str) {
+  TEST_AND_RETURN_FALSE(LoadFromPayload());
+
+  brillo::KeyValueStore properties;
+  properties.SetString(kPayloadPropertyFileSize, std::to_string(payload_size_));
+  properties.SetString(kPayloadPropertyMetadataSize,
+                       std::to_string(metadata_size_));
+  properties.SetString(kPayloadPropertyFileHash, payload_hash_);
+  properties.SetString(kPayloadPropertyMetadataHash, metadata_hash_);
+
+  *key_value_str = properties.SaveToString();
+  return true;
+}
+
+bool PayloadProperties::LoadFromPayload() {
+  PayloadMetadata payload_metadata;
+  DeltaArchiveManifest manifest;
+  Signatures metadata_signatures;
+  TEST_AND_RETURN_FALSE(payload_metadata.ParsePayloadFile(
+      payload_path_, &manifest, &metadata_signatures));
+
+  metadata_size_ = payload_metadata.GetMetadataSize();
+  payload_size_ = utils::FileSize(payload_path_);
+
+  brillo::Blob metadata_hash;
+  TEST_AND_RETURN_FALSE(HashCalculator::RawHashOfFile(
+                            payload_path_, metadata_size_, &metadata_hash) ==
+                        static_cast<off_t>(metadata_size_));
+  metadata_hash_ = brillo::data_encoding::Base64Encode(metadata_hash);
+
+  brillo::Blob payload_hash;
+  TEST_AND_RETURN_FALSE(HashCalculator::RawHashOfFile(
+                            payload_path_, payload_size_, &payload_hash) ==
+                        static_cast<off_t>(payload_size_));
+  payload_hash_ = brillo::data_encoding::Base64Encode(payload_hash);
+
+  if (payload_metadata.GetMetadataSignatureSize() > 0) {
+    TEST_AND_RETURN_FALSE(metadata_signatures.signatures_size() > 0);
+    vector<string> base64_signatures;
+    for (const auto& sig : metadata_signatures.signatures()) {
+      base64_signatures.push_back(
+          brillo::data_encoding::Base64Encode(sig.data()));
+    }
+    metadata_signatures_ = base::JoinString(base64_signatures, ":");
+  }
+
+  is_delta_ = manifest.has_old_image_info() ||
+              std::any_of(manifest.partitions().begin(),
+                          manifest.partitions().end(),
+                          [](const PartitionUpdate& part) {
+                            return part.has_old_partition_info();
+                          });
+
+  if (manifest.has_new_image_info()) {
+    target_version_ = manifest.new_image_info().version();
+  } else {
+    target_version_ = "99999.0.0";
+  }
+
+  // No need to set the source version if it was not a delta payload.
+  if (is_delta_ && manifest.has_old_image_info()) {
+    source_version_ = manifest.old_image_info().version();
+  }
+  return true;
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/payload_properties.h b/payload_generator/payload_properties.h
new file mode 100644
index 0000000..3b34511
--- /dev/null
+++ b/payload_generator/payload_properties.h
@@ -0,0 +1,73 @@
+//
+// Copyright 2019 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+
+#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_PAYLOAD_PROPERTIES_H_
+#define UPDATE_ENGINE_PAYLOAD_GENERATOR_PAYLOAD_PROPERTIES_H_
+
+#include <string>
+
+#include <brillo/key_value_store.h>
+#include <brillo/secure_blob.h>
+
+namespace chromeos_update_engine {
+
+// A class for extracting information about a payload from the payload file
+// itself. Currently the metadata can be exported as a json file or a key/value
+// properties file. But more can be added if required.
+class PayloadProperties {
+ public:
+  explicit PayloadProperties(const std::string& payload_path);
+  ~PayloadProperties() = default;
+
+  // Get the properties in a json format. The json file will be used in
+  // autotests, cros flash, etc. Mainly in Chrome OS.
+  bool GetPropertiesAsJson(std::string* json_str);
+
+  // Get the properties of the payload as a key/value store. This is mainly used
+  // in Android.
+  bool GetPropertiesAsKeyValue(std::string* key_value_str);
+
+ private:
+  // Does the main job of reading the payload and extracting information from
+  // it.
+  bool LoadFromPayload();
+
+  // The path to the payload file.
+  std::string payload_path_;
+
+  // The version of the metadata json format. If the output json file changes
+  // format, this needs to be increased.
+  int version_{2};
+
+  size_t metadata_size_;
+  std::string metadata_hash_;
+  std::string metadata_signatures_;
+
+  size_t payload_size_;
+  std::string payload_hash_;
+
+  // Whether the payload is a delta (true) or full (false).
+  bool is_delta_;
+
+  std::string target_version_;
+  std::string source_version_;
+
+  DISALLOW_COPY_AND_ASSIGN(PayloadProperties);
+};
+
+}  // namespace chromeos_update_engine
+
+#endif  // UPDATE_ENGINE_PAYLOAD_GENERATOR_PAYLOAD_PROPERTIES_H_
diff --git a/payload_generator/payload_properties_unittest.cc b/payload_generator/payload_properties_unittest.cc
new file mode 100644
index 0000000..db3902c
--- /dev/null
+++ b/payload_generator/payload_properties_unittest.cc
@@ -0,0 +1,144 @@
+//
+// Copyright (C) 2019 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//      http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+
+#include "update_engine/payload_generator/payload_properties.h"
+
+#include <memory>
+#include <string>
+#include <vector>
+
+#include <base/files/file_util.h>
+#include <base/files/scoped_file.h>
+#include <base/files/scoped_temp_dir.h>
+#include <base/rand_util.h>
+#include <base/strings/stringprintf.h>
+#include <brillo/data_encoding.h>
+
+#include <gtest/gtest.h>
+
+#include "update_engine/common/hash_calculator.h"
+#include "update_engine/common/test_utils.h"
+#include "update_engine/common/utils.h"
+#include "update_engine/payload_consumer/install_plan.h"
+#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/delta_diff_utils.h"
+#include "update_engine/payload_generator/full_update_generator.h"
+#include "update_engine/payload_generator/operations_generator.h"
+#include "update_engine/payload_generator/payload_file.h"
+#include "update_engine/payload_generator/payload_generation_config.h"
+
+using chromeos_update_engine::test_utils::ScopedTempFile;
+using std::string;
+using std::unique_ptr;
+using std::vector;
+
+namespace chromeos_update_engine {
+
+// TODO(kimjae): current implementation is very specific to a static way of
+// producing a deterministic test. It would definitely be beneficial to
+// extend the |PayloadPropertiesTest::SetUp()| into a generic helper or
+// seperate class that can handle creation of different |PayloadFile|s.
+class PayloadPropertiesTest : public ::testing::Test {
+ protected:
+  void SetUp() override {
+    PayloadGenerationConfig config;
+    config.version.major = kBrilloMajorPayloadVersion;
+    config.version.minor = kSourceMinorPayloadVersion;
+    config.source.image_info.set_version("123.0.0");
+    config.target.image_info.set_version("456.7.8");
+    PayloadFile payload;
+    EXPECT_TRUE(payload.Init(config));
+
+    const string kTempFileTemplate = "temp_data.XXXXXX";
+    int data_file_fd;
+    string temp_file_path;
+    EXPECT_TRUE(
+        utils::MakeTempFile(kTempFileTemplate, &temp_file_path, &data_file_fd));
+    ScopedPathUnlinker temp_file_unlinker(temp_file_path);
+    EXPECT_LE(0, data_file_fd);
+
+    const auto SetupPartitionConfig =
+        [](PartitionConfig* config, const string& path, size_t size) {
+          config->path = path;
+          config->size = size;
+        };
+    const auto WriteZerosToFile = [](const char path[], size_t size) {
+      string zeros(size, '\0');
+      EXPECT_TRUE(utils::WriteFile(path, zeros.c_str(), zeros.size()));
+    };
+    ScopedTempFile old_part_file;
+    ScopedTempFile new_part_file;
+    PartitionConfig old_part(kPartitionNameRoot);
+    PartitionConfig new_part(kPartitionNameRoot);
+    SetupPartitionConfig(&old_part, old_part_file.path(), 0);
+    SetupPartitionConfig(&new_part, new_part_file.path(), 10000);
+    WriteZerosToFile(old_part_file.path().c_str(), old_part.size);
+    WriteZerosToFile(new_part_file.path().c_str(), new_part.size);
+
+    // Select payload generation strategy based on the config.
+    unique_ptr<OperationsGenerator> strategy(new FullUpdateGenerator());
+
+    vector<AnnotatedOperation> aops;
+    off_t data_file_size = 0;
+    BlobFileWriter blob_file_writer(data_file_fd, &data_file_size);
+    // Generate the operations using the strategy we selected above.
+    EXPECT_TRUE(strategy->GenerateOperations(
+        config, old_part, new_part, &blob_file_writer, &aops));
+
+    payload.AddPartition(old_part, new_part, aops);
+
+    uint64_t metadata_size;
+    EXPECT_TRUE(payload.WritePayload(
+        payload_file.path(), temp_file_path, "", &metadata_size));
+  }
+
+  ScopedTempFile payload_file;
+};
+
+// Validate the hash of file exists within the output.
+TEST_F(PayloadPropertiesTest, GetPropertiesAsJsonTestHash) {
+  constexpr char kJsonProperties[] =
+      "{"
+      R"("is_delta":true,)"
+      R"("metadata_signature":"",)"
+      R"("metadata_size":187,)"
+      R"("sha256_hex":"Rtrj9v3xXhrAi1741HAojtGxAQEOZ7mDyhzskIF4PJc=",)"
+      R"("size":233,)"
+      R"("source_version":"123.0.0",)"
+      R"("target_version":"456.7.8",)"
+      R"("version":2)"
+      "}";
+  string json;
+  EXPECT_TRUE(
+      PayloadProperties(payload_file.path()).GetPropertiesAsJson(&json));
+  EXPECT_EQ(kJsonProperties, json) << "JSON contents:\n" << json;
+}
+
+// Validate the hash of file and metadata are within the output.
+TEST_F(PayloadPropertiesTest, GetPropertiesAsKeyValueTestHash) {
+  constexpr char kKeyValueProperties[] =
+      "FILE_HASH=Rtrj9v3xXhrAi1741HAojtGxAQEOZ7mDyhzskIF4PJc=\n"
+      "FILE_SIZE=233\n"
+      "METADATA_HASH=kiXTexy/s2aPttf4+r8KRZWYZ6FYvwhU6rJGcnnI+U0=\n"
+      "METADATA_SIZE=187\n";
+  string key_value;
+  EXPECT_TRUE(PayloadProperties{payload_file.path()}.GetPropertiesAsKeyValue(
+      &key_value));
+  EXPECT_EQ(kKeyValueProperties, key_value) << "Key Value contents:\n"
+                                            << key_value;
+}
+
+}  // namespace chromeos_update_engine
diff --git a/payload_generator/payload_signer.cc b/payload_generator/payload_signer.cc
index 72780b1..7e5fd4e 100644
--- a/payload_generator/payload_signer.cc
+++ b/payload_generator/payload_signer.cc
@@ -104,22 +104,20 @@
   uint64_t metadata_size = payload_metadata.GetMetadataSize();
   uint32_t metadata_signature_size =
       payload_metadata.GetMetadataSignatureSize();
-  if (payload_metadata.GetMajorVersion() == kBrilloMajorPayloadVersion) {
-    // Write metadata signature size in header.
-    uint32_t metadata_signature_size_be = htobe32(metadata_signature.size());
-    memcpy(payload.data() + manifest_offset,
-           &metadata_signature_size_be,
-           sizeof(metadata_signature_size_be));
-    manifest_offset += sizeof(metadata_signature_size_be);
-    // Replace metadata signature.
-    payload.erase(payload.begin() + metadata_size,
-                  payload.begin() + metadata_size + metadata_signature_size);
-    payload.insert(payload.begin() + metadata_size,
-                   metadata_signature.begin(),
-                   metadata_signature.end());
-    metadata_signature_size = metadata_signature.size();
-    LOG(INFO) << "Metadata signature size: " << metadata_signature_size;
-  }
+  // Write metadata signature size in header.
+  uint32_t metadata_signature_size_be = htobe32(metadata_signature.size());
+  memcpy(payload.data() + manifest_offset,
+         &metadata_signature_size_be,
+         sizeof(metadata_signature_size_be));
+  manifest_offset += sizeof(metadata_signature_size_be);
+  // Replace metadata signature.
+  payload.erase(payload.begin() + metadata_size,
+                payload.begin() + metadata_size + metadata_signature_size);
+  payload.insert(payload.begin() + metadata_size,
+                 metadata_signature.begin(),
+                 metadata_signature.end());
+  metadata_signature_size = metadata_signature.size();
+  LOG(INFO) << "Metadata signature size: " << metadata_signature_size;
 
   DeltaArchiveManifest manifest;
   TEST_AND_RETURN_FALSE(payload_metadata.GetManifest(payload, &manifest));
@@ -143,7 +141,6 @@
     PayloadSigner::AddSignatureToManifest(
         payload.size() - metadata_size - metadata_signature_size,
         payload_signature.size(),
-        payload_metadata.GetMajorVersion() == kChromeOSMajorPayloadVersion,
         &manifest);
 
     // Updates the payload to include the new manifest.
@@ -241,25 +238,12 @@
 
 void PayloadSigner::AddSignatureToManifest(uint64_t signature_blob_offset,
                                            uint64_t signature_blob_length,
-                                           bool add_dummy_op,
                                            DeltaArchiveManifest* manifest) {
   LOG(INFO) << "Making room for signature in file";
   manifest->set_signatures_offset(signature_blob_offset);
   LOG(INFO) << "set? " << manifest->has_signatures_offset();
   manifest->set_signatures_offset(signature_blob_offset);
   manifest->set_signatures_size(signature_blob_length);
-  // Add a dummy op at the end to appease older clients
-  if (add_dummy_op) {
-    InstallOperation* dummy_op = manifest->add_kernel_install_operations();
-    dummy_op->set_type(InstallOperation::REPLACE);
-    dummy_op->set_data_offset(signature_blob_offset);
-    dummy_op->set_data_length(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(
-        utils::DivRoundUp(signature_blob_length, kBlockSize));
-  }
 }
 
 bool PayloadSigner::VerifySignedPayload(const string& payload_path,
@@ -512,35 +496,4 @@
   return true;
 }
 
-bool PayloadSigner::ExtractPayloadProperties(
-    const string& payload_path, brillo::KeyValueStore* properties) {
-  brillo::Blob payload;
-  TEST_AND_RETURN_FALSE(
-      utils::ReadFileChunk(payload_path, 0, kMaxPayloadHeaderSize, &payload));
-
-  PayloadMetadata payload_metadata;
-  TEST_AND_RETURN_FALSE(payload_metadata.ParsePayloadHeader(payload));
-  uint64_t metadata_size = payload_metadata.GetMetadataSize();
-
-  uint64_t file_size = utils::FileSize(payload_path);
-  properties->SetString(kPayloadPropertyFileSize, std::to_string(file_size));
-  properties->SetString(kPayloadPropertyMetadataSize,
-                        std::to_string(metadata_size));
-
-  brillo::Blob file_hash, metadata_hash;
-  TEST_AND_RETURN_FALSE(
-      HashCalculator::RawHashOfFile(payload_path, file_size, &file_hash) ==
-      static_cast<off_t>(file_size));
-
-  TEST_AND_RETURN_FALSE(HashCalculator::RawHashOfFile(
-                            payload_path, metadata_size, &metadata_hash) ==
-                        static_cast<off_t>(metadata_size));
-
-  properties->SetString(kPayloadPropertyFileHash,
-                        brillo::data_encoding::Base64Encode(file_hash));
-  properties->SetString(kPayloadPropertyMetadataHash,
-                        brillo::data_encoding::Base64Encode(metadata_hash));
-  return true;
-}
-
 }  // namespace chromeos_update_engine
diff --git a/payload_generator/payload_signer.h b/payload_generator/payload_signer.h
index bd1e32f..06e4823 100644
--- a/payload_generator/payload_signer.h
+++ b/payload_generator/payload_signer.h
@@ -39,12 +39,9 @@
   static bool VerifySignedPayload(const std::string& payload_path,
                                   const std::string& public_key_path);
 
-  // Adds specified signature offset/length to given |manifest|, also adds a
-  // dummy operation that points to a signature blob located at the specified
-  // offset/length if |add_dummy_op| is true.
+  // Adds specified signature offset/length to given |manifest|.
   static void AddSignatureToManifest(uint64_t signature_blob_offset,
                                      uint64_t signature_blob_length,
-                                     bool add_dummy_op,
                                      DeltaArchiveManifest* manifest);
 
   // Given a raw |hash| and a private key in |private_key_path| calculates the
diff --git a/payload_generator/payload_signer_unittest.cc b/payload_generator/payload_signer_unittest.cc
index bf7100b..fe62997 100644
--- a/payload_generator/payload_signer_unittest.cc
+++ b/payload_generator/payload_signer_unittest.cc
@@ -20,6 +20,7 @@
 #include <vector>
 
 #include <base/logging.h>
+#include <base/stl_util.h>
 #include <gtest/gtest.h>
 
 #include "update_engine/common/hash_calculator.h"
@@ -118,8 +119,8 @@
   EXPECT_EQ(1, signatures.signatures_size());
   const Signatures::Signature& sig = signatures.signatures(0);
   const string& sig_data = sig.data();
-  ASSERT_EQ(arraysize(kDataSignature), sig_data.size());
-  for (size_t i = 0; i < arraysize(kDataSignature); i++) {
+  ASSERT_EQ(base::size(kDataSignature), sig_data.size());
+  for (size_t i = 0; i < base::size(kDataSignature); i++) {
     EXPECT_EQ(kDataSignature[i], static_cast<uint8_t>(sig_data[i]));
   }
 }
diff --git a/payload_generator/squashfs_filesystem.cc b/payload_generator/squashfs_filesystem.cc
index 6c892f5..eb4fda3 100644
--- a/payload_generator/squashfs_filesystem.cc
+++ b/payload_generator/squashfs_filesystem.cc
@@ -23,6 +23,7 @@
 #include <utility>
 
 #include <base/files/file_util.h>
+#include <base/files/scoped_temp_dir.h>
 #include <base/logging.h>
 #include <base/strings/string_number_conversions.h>
 #include <base/strings/string_split.h>
@@ -36,6 +37,8 @@
 #include "update_engine/payload_generator/extent_utils.h"
 #include "update_engine/update_metadata.pb.h"
 
+using base::FilePath;
+using base::ScopedTempDir;
 using std::string;
 using std::unique_ptr;
 using std::vector;
@@ -49,6 +52,8 @@
 constexpr uint64_t kSquashfsCompressedBit = 1 << 24;
 constexpr uint32_t kSquashfsZlibCompression = 1;
 
+constexpr char kUpdateEngineConf[] = "etc/update_engine.conf";
+
 bool ReadSquashfsHeader(const brillo::Blob blob,
                         SquashfsFilesystem::SquashfsHeader* header) {
   if (blob.size() < kSquashfsSuperBlockSize) {
@@ -76,18 +81,59 @@
   // Run unsquashfs to get the system file map.
   // unsquashfs -m <map-file> <squashfs-file>
   vector<string> cmd = {"unsquashfs", "-m", map_file, sqfs_path};
-  string stdout;
+  string stdout, stderr;
   int exit_code;
-  if (!Subprocess::SynchronousExec(cmd, &exit_code, &stdout) ||
+  if (!Subprocess::SynchronousExec(cmd, &exit_code, &stdout, &stderr) ||
       exit_code != 0) {
-    LOG(ERROR) << "Failed to run unsquashfs -m. The stdout content was: "
-               << stdout;
+    LOG(ERROR) << "Failed to run `unsquashfs -m` with stdout content: "
+               << stdout << " and stderr content: " << stderr;
     return false;
   }
   TEST_AND_RETURN_FALSE(utils::ReadFile(map_file, map));
   return true;
 }
 
+bool GetUpdateEngineConfig(const std::string& sqfs_path, string* config) {
+  ScopedTempDir unsquash_dir;
+  if (!unsquash_dir.CreateUniqueTempDir()) {
+    PLOG(ERROR) << "Failed to create a temporary directory.";
+    return false;
+  }
+
+  // Run unsquashfs to extract update_engine.conf
+  // -f: To force overriding if the target directory exists.
+  // -d: The directory to unsquash the files.
+  vector<string> cmd = {"unsquashfs",
+                        "-f",
+                        "-d",
+                        unsquash_dir.GetPath().value(),
+                        sqfs_path,
+                        kUpdateEngineConf};
+  string stdout, stderr;
+  int exit_code;
+  if (!Subprocess::SynchronousExec(cmd, &exit_code, &stdout, &stderr) ||
+      exit_code != 0) {
+    PLOG(ERROR) << "Failed to unsquashfs etc/update_engine.conf with stdout: "
+                << stdout << " and stderr: " << stderr;
+    return false;
+  }
+
+  auto config_path = unsquash_dir.GetPath().Append(kUpdateEngineConf);
+  string config_content;
+  if (!utils::ReadFile(config_path.value(), &config_content)) {
+    PLOG(ERROR) << "Failed to read " << config_path.value();
+    return false;
+  }
+
+  if (config_content.empty()) {
+    LOG(ERROR) << "update_engine config file was empty!!";
+    return false;
+  }
+
+  *config = std::move(config_content);
+  return true;
+}
+
 }  // namespace
 
 bool SquashfsFilesystem::Init(const string& map,
@@ -120,6 +166,7 @@
     uint64_t start;
     TEST_AND_RETURN_FALSE(base::StringToUint64(splits[1], &start));
     uint64_t cur_offset = start;
+    bool is_compressed = false;
     for (size_t i = 2; i < splits.size(); ++i) {
       uint64_t blk_size;
       TEST_AND_RETURN_FALSE(base::StringToUint64(splits[i], &blk_size));
@@ -127,10 +174,11 @@
       auto new_blk_size = blk_size & ~kSquashfsCompressedBit;
       TEST_AND_RETURN_FALSE(new_blk_size <= header.block_size);
       if (new_blk_size > 0 && !(blk_size & kSquashfsCompressedBit)) {
-        // Compressed block
+        // It is a compressed block.
         if (is_zlib && extract_deflates) {
           zlib_blks.emplace_back(cur_offset, new_blk_size);
         }
+        is_compressed = true;
       }
       cur_offset += new_blk_size;
     }
@@ -140,6 +188,7 @@
       File file;
       file.name = splits[0].as_string();
       file.extents = {ExtentForBytes(kBlockSize, start, cur_offset - start)};
+      file.is_compressed = is_compressed;
       files_.emplace_back(file);
     }
   }
@@ -151,7 +200,8 @@
   // If there is any overlap between two consecutive extents, remove them. Here
   // we are assuming all files have exactly one extent. If this assumption
   // changes then this implementation needs to change too.
-  for (auto first = files_.begin(), second = first + 1;
+  for (auto first = files_.begin(),
+            second = first + (first == files_.end() ? 0 : 1);
        first != files_.end() && second != files_.end();
        second = first + 1) {
     auto first_begin = first->extents[0].start_block();
@@ -217,6 +267,14 @@
                 return a.offset < b.offset;
               });
 
+    // Sometimes a squashfs can have a two files that are hard linked. In this
+    // case both files will have the same starting offset in the image and hence
+    // the same zlib blocks. So we need to remove these duplicates to eliminate
+    // further potential probems. As a matter of fact the next statement will
+    // fail if there are duplicates (there will be overlap between two blocks).
+    auto last = std::unique(zlib_blks.begin(), zlib_blks.end());
+    zlib_blks.erase(last, zlib_blks.end());
+
     // Sanity check. Make sure zlib blocks are not overlapping.
     auto result = std::adjacent_find(
         zlib_blks.begin(),
@@ -239,12 +297,12 @@
 }
 
 unique_ptr<SquashfsFilesystem> SquashfsFilesystem::CreateFromFile(
-    const string& sqfs_path, bool extract_deflates) {
+    const string& sqfs_path, bool extract_deflates, bool load_settings) {
   if (sqfs_path.empty())
     return nullptr;
 
   brillo::StreamPtr sqfs_file =
-      brillo::FileStream::Open(base::FilePath(sqfs_path),
+      brillo::FileStream::Open(FilePath(sqfs_path),
                                brillo::Stream::AccessMode::READ,
                                brillo::FileStream::Disposition::OPEN_EXISTING,
                                nullptr);
@@ -278,6 +336,12 @@
     return nullptr;
   }
 
+  if (load_settings) {
+    if (!GetUpdateEngineConfig(sqfs_path, &sqfs->update_engine_config_)) {
+      return nullptr;
+    }
+  }
+
   return sqfs;
 }
 
@@ -311,9 +375,12 @@
 }
 
 bool SquashfsFilesystem::LoadSettings(brillo::KeyValueStore* store) const {
-  // Settings not supported in squashfs.
-  LOG(ERROR) << "squashfs doesn't support LoadSettings().";
-  return false;
+  if (!store->LoadFromString(update_engine_config_)) {
+    LOG(ERROR) << "Failed to load the settings with config: "
+               << update_engine_config_;
+    return false;
+  }
+  return true;
 }
 
 bool SquashfsFilesystem::IsSquashfsImage(const brillo::Blob& blob) {
diff --git a/payload_generator/squashfs_filesystem.h b/payload_generator/squashfs_filesystem.h
index b79f8c7..5045dfc 100644
--- a/payload_generator/squashfs_filesystem.h
+++ b/payload_generator/squashfs_filesystem.h
@@ -59,7 +59,7 @@
   // |extract_deflates| is true, it will process files to find location of all
   // deflate streams.
   static std::unique_ptr<SquashfsFilesystem> CreateFromFile(
-      const std::string& sqfs_path, bool extract_deflates);
+      const std::string& sqfs_path, bool extract_deflates, bool load_settings);
 
   // Creates the file system from a file map |filemap| which is a multi-line
   // string with each line with the following format:
@@ -113,6 +113,9 @@
   // All the files in the filesystem.
   std::vector<File> files_;
 
+  // The content of /etc/update_engine.conf.
+  std::string update_engine_config_;
+
   DISALLOW_COPY_AND_ASSIGN(SquashfsFilesystem);
 };
 
diff --git a/payload_generator/squashfs_filesystem_unittest.cc b/payload_generator/squashfs_filesystem_unittest.cc
index 29fcf1c..68ca9df 100644
--- a/payload_generator/squashfs_filesystem_unittest.cc
+++ b/payload_generator/squashfs_filesystem_unittest.cc
@@ -112,7 +112,7 @@
 #ifdef __CHROMEOS__
 TEST_F(SquashfsFilesystemTest, EmptyFilesystemTest) {
   unique_ptr<SquashfsFilesystem> fs = SquashfsFilesystem::CreateFromFile(
-      GetBuildArtifactsPath("gen/disk_sqfs_empty.img"), true);
+      GetBuildArtifactsPath("gen/disk_sqfs_empty.img"), true, false);
   CheckSquashfs(fs);
 
   // Even an empty squashfs filesystem is rounded up to 4K.
@@ -133,7 +133,7 @@
 
 TEST_F(SquashfsFilesystemTest, DefaultFilesystemTest) {
   unique_ptr<SquashfsFilesystem> fs = SquashfsFilesystem::CreateFromFile(
-      GetBuildArtifactsPath("gen/disk_sqfs_default.img"), true);
+      GetBuildArtifactsPath("gen/disk_sqfs_default.img"), true, false);
   CheckSquashfs(fs);
 
   vector<FilesystemInterface::File> files;
@@ -148,6 +148,18 @@
   EXPECT_EQ(files[0].name, file.name);
   EXPECT_EQ(files[0].extents, file.extents);
 }
+
+TEST_F(SquashfsFilesystemTest, UpdateEngineConfigTest) {
+  unique_ptr<SquashfsFilesystem> fs = SquashfsFilesystem::CreateFromFile(
+      GetBuildArtifactsPath("gen/disk_sqfs_unittest.img"), true, true);
+  CheckSquashfs(fs);
+
+  brillo::KeyValueStore kvs;
+  EXPECT_TRUE(fs->LoadSettings(&kvs));
+  string minor_version;
+  EXPECT_TRUE(kvs.GetString("PAYLOAD_MINOR_VERSION", &minor_version));
+  EXPECT_EQ(minor_version, "1234");
+}
 #endif  // __CHROMEOS__
 
 TEST_F(SquashfsFilesystemTest, SimpleFileMapTest) {
diff --git a/payload_generator/tarjan.cc b/payload_generator/tarjan.cc
deleted file mode 100644
index 2d4ca31..0000000
--- a/payload_generator/tarjan.cc
+++ /dev/null
@@ -1,83 +0,0 @@
-//
-// Copyright (C) 2010 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//      http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-#include "update_engine/payload_generator/tarjan.h"
-
-#include <algorithm>
-#include <vector>
-
-#include <base/logging.h>
-#include <base/stl_util.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 (base::ContainsValue(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 (base::ContainsValue(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
deleted file mode 100644
index 39ac4e4..0000000
--- a/payload_generator/tarjan.h
+++ /dev/null
@@ -1,53 +0,0 @@
-//
-// Copyright (C) 2010 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//      http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_TARJAN_H_
-#define UPDATE_ENGINE_PAYLOAD_GENERATOR_TARJAN_H_
-
-// This is an implementation 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  // UPDATE_ENGINE_PAYLOAD_GENERATOR_TARJAN_H_
diff --git a/payload_generator/tarjan_unittest.cc b/payload_generator/tarjan_unittest.cc
deleted file mode 100644
index b271227..0000000
--- a/payload_generator/tarjan_unittest.cc
+++ /dev/null
@@ -1,94 +0,0 @@
-//
-// Copyright (C) 2010 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//      http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#include "update_engine/payload_generator/tarjan.h"
-
-#include <string>
-#include <utility>
-
-#include <base/logging.h>
-#include <base/stl_util.h>
-#include <gtest/gtest.h>
-
-#include "update_engine/payload_generator/graph_types.h"
-
-using std::make_pair;
-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(5U, vertex_indexes.size());
-    EXPECT_TRUE(base::ContainsValue(vertex_indexes, n_a));
-    EXPECT_TRUE(base::ContainsValue(vertex_indexes, n_b));
-    EXPECT_TRUE(base::ContainsValue(vertex_indexes, n_c));
-    EXPECT_TRUE(base::ContainsValue(vertex_indexes, n_d));
-    EXPECT_TRUE(base::ContainsValue(vertex_indexes, n_e));
-  }
-
-  {
-    vector<Vertex::Index> vertex_indexes;
-    tarjan.Execute(n_f, &graph, &vertex_indexes);
-
-    EXPECT_EQ(1U, vertex_indexes.size());
-    EXPECT_TRUE(base::ContainsValue(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(2U, vertex_indexes.size());
-    EXPECT_TRUE(base::ContainsValue(vertex_indexes, n_g));
-    EXPECT_TRUE(base::ContainsValue(vertex_indexes, n_h));
-  }
-}
-
-}  // namespace chromeos_update_engine
diff --git a/payload_generator/topological_sort.cc b/payload_generator/topological_sort.cc
deleted file mode 100644
index 0abd708..0000000
--- a/payload_generator/topological_sort.cc
+++ /dev/null
@@ -1,57 +0,0 @@
-//
-// Copyright (C) 2010 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//      http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#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
deleted file mode 100644
index 461cbe1..0000000
--- a/payload_generator/topological_sort.h
+++ /dev/null
@@ -1,42 +0,0 @@
-//
-// Copyright (C) 2010 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//      http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_TOPOLOGICAL_SORT_H_
-#define 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  // UPDATE_ENGINE_PAYLOAD_GENERATOR_TOPOLOGICAL_SORT_H_
diff --git a/payload_generator/topological_sort_unittest.cc b/payload_generator/topological_sort_unittest.cc
deleted file mode 100644
index aa296d8..0000000
--- a/payload_generator/topological_sort_unittest.cc
+++ /dev/null
@@ -1,96 +0,0 @@
-//
-// Copyright (C) 2010 The Android Open Source Project
-//
-// Licensed under the Apache License, Version 2.0 (the "License");
-// you may not use this file except in compliance with the License.
-// You may obtain a copy of the License at
-//
-//      http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing, software
-// distributed under the License is distributed on an "AS IS" BASIS,
-// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
-// See the License for the specific language governing permissions and
-// limitations under the License.
-//
-
-#include "update_engine/payload_generator/topological_sort.h"
-
-#include <utility>
-#include <vector>
-
-#include <gtest/gtest.h>
-
-#include "update_engine/payload_generator/graph_types.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