diff --git a/SConstruct b/SConstruct
index 7730995..2a88e1a 100644
--- a/SConstruct
+++ b/SConstruct
@@ -206,28 +206,21 @@
                    clock.cc
                    connection_manager.cc
                    constants.cc
-                   cycle_breaker.cc
                    dbus_service.cc
-                   delta_diff_generator.cc
                    delta_performer.cc
                    download_action.cc
-                   extent_mapper.cc
                    extent_ranges.cc
                    extent_writer.cc
-                   filesystem_copier_action.cc
-                   filesystem_iterator.cc
                    file_descriptor.cc
                    file_writer.cc
-                   full_update_generator.cc
+                   filesystem_copier_action.cc
                    gpio_handler.cc
-                   graph_utils.cc
                    hardware.cc
                    http_common.cc
                    http_fetcher.cc
                    hwid_override.cc
                    install_plan.cc
                    libcurl_http_fetcher.cc
-                   metadata.cc
                    metrics.cc
                    multi_range_http_fetcher.cc
                    omaha_hash_calculator.cc
@@ -235,14 +228,24 @@
                    omaha_request_params.cc
                    omaha_response_handler_action.cc
                    p2p_manager.cc
+                   payload_constants.cc
+                   payload_generator/cycle_breaker.cc
+                   payload_generator/delta_diff_generator.cc
+                   payload_generator/extent_mapper.cc
+                   payload_generator/filesystem_iterator.cc
+                   payload_generator/full_update_generator.cc
+                   payload_generator/graph_utils.cc
+                   payload_generator/metadata.cc
+                   payload_generator/tarjan.cc
+                   payload_generator/topological_sort.cc
                    payload_signer.cc
                    payload_state.cc
                    policy_manager/boxed_value.cc
                    policy_manager/chromeos_policy.cc
                    policy_manager/evaluation_context.cc
                    policy_manager/event_loop.cc
-                   policy_manager/policy_manager.cc
                    policy_manager/policy.cc
+                   policy_manager/policy_manager.cc
                    policy_manager/real_config_provider.cc
                    policy_manager/real_device_policy_provider.cc
                    policy_manager/real_random_provider.cc
@@ -257,9 +260,7 @@
                    real_system_state.cc
                    simple_key_value_store.cc
                    subprocess.cc
-                   tarjan.cc
                    terminator.cc
-                   topological_sort.cc
                    update_attempter.cc
                    update_check_scheduler.cc
                    update_metadata.pb.cc
@@ -273,32 +274,34 @@
                             certificate_checker_unittest.cc
                             chrome_browser_proxy_resolver_unittest.cc
                             connection_manager_unittest.cc
-                            cycle_breaker_unittest.cc
-                            delta_diff_generator_unittest.cc
                             delta_performer_unittest.cc
                             download_action_unittest.cc
-                            extent_mapper_unittest.cc
                             extent_ranges_unittest.cc
                             extent_writer_unittest.cc
                             fake_prefs.cc
                             fake_system_state.cc
                             file_writer_unittest.cc
                             filesystem_copier_action_unittest.cc
-                            filesystem_iterator_unittest.cc
-                            full_update_generator_unittest.cc
                             gpio_handler_unittest.cc
                             gpio_mock_file_descriptor.cc
                             gpio_mock_udev_interface.cc
-                            graph_utils_unittest.cc
                             http_fetcher_unittest.cc
                             hwid_override_unittest.cc
-                            metadata_unittest.cc
                             mock_http_fetcher.cc
                             omaha_hash_calculator_unittest.cc
                             omaha_request_action_unittest.cc
                             omaha_request_params_unittest.cc
                             omaha_response_handler_action_unittest.cc
                             p2p_manager_unittest.cc
+                            payload_generator/cycle_breaker_unittest.cc
+                            payload_generator/delta_diff_generator_unittest.cc
+                            payload_generator/extent_mapper_unittest.cc
+                            payload_generator/filesystem_iterator_unittest.cc
+                            payload_generator/full_update_generator_unittest.cc
+                            payload_generator/graph_utils_unittest.cc
+                            payload_generator/metadata_unittest.cc
+                            payload_generator/tarjan_unittest.cc
+                            payload_generator/topological_sort_unittest.cc
                             payload_signer_unittest.cc
                             payload_state_unittest.cc
                             policy_manager/boxed_value_unittest.cc
@@ -321,10 +324,8 @@
                             prefs_unittest.cc
                             simple_key_value_store_unittest.cc
                             subprocess_unittest.cc
-                            tarjan_unittest.cc
                             terminator_unittest.cc
                             test_utils.cc
-                            topological_sort_unittest.cc
                             update_attempter_unittest.cc
                             update_check_scheduler_unittest.cc
                             utils_unittest.cc
@@ -333,7 +334,7 @@
 
 client_main = ['update_engine_client.cc']
 
-delta_generator_main = ['generate_delta_main.cc']
+delta_generator_main = ['payload_generator/generate_delta_main.cc']
 
 # Hack to generate header files first. They are generated as a side effect
 # of generating other files (usually their corresponding .c(c) files),
diff --git a/delta_performer.cc b/delta_performer.cc
index 89c319d..c0932df 100644
--- a/delta_performer.cc
+++ b/delta_performer.cc
@@ -13,19 +13,18 @@
 #include <vector>
 
 #include <base/file_util.h>
+#include <base/format_macros.h>
 #include <base/memory/scoped_ptr.h>
 #include <base/strings/string_util.h>
 #include <base/strings/stringprintf.h>
-#include <base/format_macros.h>
 #include <google/protobuf/repeated_field.h>
 
 #include "update_engine/bzip_extent_writer.h"
 #include "update_engine/constants.h"
-#include "update_engine/delta_diff_generator.h"
 #include "update_engine/extent_ranges.h"
 #include "update_engine/extent_writer.h"
-#include "update_engine/graph_types.h"
 #include "update_engine/hardware_interface.h"
+#include "update_engine/payload_constants.h"
 #include "update_engine/payload_signer.h"
 #include "update_engine/payload_state_interface.h"
 #include "update_engine/prefs_interface.h"
@@ -33,10 +32,10 @@
 #include "update_engine/terminator.h"
 #include "update_engine/update_attempter.h"
 
+using google::protobuf::RepeatedPtrField;
 using std::min;
 using std::string;
 using std::vector;
-using google::protobuf::RepeatedPtrField;
 
 namespace chromeos_update_engine {
 
diff --git a/delta_performer_unittest.cc b/delta_performer_unittest.cc
index 0a19aa2..21a6f8e 100644
--- a/delta_performer_unittest.cc
+++ b/delta_performer_unittest.cc
@@ -2,8 +2,8 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#include <sys/mount.h>
 #include <inttypes.h>
+#include <sys/mount.h>
 
 #include <algorithm>
 #include <string>
@@ -17,13 +17,12 @@
 #include <gtest/gtest.h>
 
 #include "update_engine/constants.h"
-#include "update_engine/delta_diff_generator.h"
 #include "update_engine/delta_performer.h"
 #include "update_engine/extent_ranges.h"
 #include "update_engine/fake_hardware.h"
 #include "update_engine/fake_system_state.h"
-#include "update_engine/full_update_generator.h"
-#include "update_engine/graph_types.h"
+#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/delta_diff_generator.h"
 #include "update_engine/payload_signer.h"
 #include "update_engine/prefs_mock.h"
 #include "update_engine/test_utils.h"
@@ -35,8 +34,8 @@
 using std::min;
 using std::string;
 using std::vector;
-using testing::_;
 using testing::Return;
+using testing::_;
 
 extern const char* kUnittestPrivateKeyPath;
 extern const char* kUnittestPublicKeyPath;
diff --git a/extent_ranges.cc b/extent_ranges.cc
index 5193d3d..1089de1 100644
--- a/extent_ranges.cc
+++ b/extent_ranges.cc
@@ -10,6 +10,8 @@
 
 #include <base/logging.h>
 
+#include "update_engine/payload_constants.h"
+
 using std::max;
 using std::min;
 using std::set;
diff --git a/extent_ranges.h b/extent_ranges.h
index c559849..2b5748f 100644
--- a/extent_ranges.h
+++ b/extent_ranges.h
@@ -11,8 +11,6 @@
 
 #include <base/basictypes.h>
 
-#include "update_engine/delta_diff_generator.h"
-#include "update_engine/graph_types.h"
 #include "update_engine/update_metadata.pb.h"
 
 // An ExtentRanges object represents an unordered collection of extents (and
diff --git a/extent_ranges_unittest.cc b/extent_ranges_unittest.cc
index 1b767f1..ba00d0d 100644
--- a/extent_ranges_unittest.cc
+++ b/extent_ranges_unittest.cc
@@ -7,6 +7,7 @@
 #include <gtest/gtest.h>
 
 #include "update_engine/extent_ranges.h"
+#include "update_engine/payload_constants.h"
 #include "update_engine/test_utils.h"
 
 using std::vector;
diff --git a/extent_writer.cc b/extent_writer.cc
index c28956b..0cdb797 100644
--- a/extent_writer.cc
+++ b/extent_writer.cc
@@ -3,10 +3,13 @@
 // found in the LICENSE file.
 
 #include "update_engine/extent_writer.h"
+
 #include <errno.h>
 #include <unistd.h>
+
 #include <algorithm>
-#include "update_engine/graph_types.h"
+
+#include "update_engine/payload_constants.h"
 #include "update_engine/utils.h"
 
 using std::min;
diff --git a/extent_writer_unittest.cc b/extent_writer_unittest.cc
index 55cbff6..fcd57dd 100644
--- a/extent_writer_unittest.cc
+++ b/extent_writer_unittest.cc
@@ -2,15 +2,19 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
+#include "update_engine/extent_writer.h"
+
 #include <sys/stat.h>
 #include <sys/types.h>
 #include <unistd.h>
+
 #include <algorithm>
 #include <string>
 #include <vector>
+
 #include <gtest/gtest.h>
-#include "update_engine/extent_writer.h"
-#include "update_engine/graph_types.h"
+
+#include "update_engine/payload_constants.h"
 #include "update_engine/test_utils.h"
 #include "update_engine/utils.h"
 
@@ -58,21 +62,21 @@
   extent.set_start_block(1);
   extent.set_num_blocks(1);
   extents.push_back(extent);
-  
+
   const string bytes = "1234";
 
   DirectExtentWriter direct_writer;
   EXPECT_TRUE(direct_writer.Init(fd(), extents, kBlockSize));
   EXPECT_TRUE(direct_writer.Write(bytes.data(), bytes.size()));
   EXPECT_TRUE(direct_writer.End());
-  
+
   struct stat stbuf;
   EXPECT_EQ(0, fstat(fd(), &stbuf));
   EXPECT_EQ(kBlockSize + bytes.size(), stbuf.st_size);
-  
+
   vector<char> result_file;
   EXPECT_TRUE(utils::ReadFile(path(), &result_file));
-  
+
   vector<char> expected_file(kBlockSize);
   expected_file.insert(expected_file.end(),
                        bytes.data(), bytes.data() + bytes.size());
@@ -117,13 +121,13 @@
   extent.set_start_block(2);
   extent.set_num_blocks(1);
   extents.push_back(extent);
-  
+
   vector<char> data(kBlockSize * 3);
   FillWithData(&data);
-  
+
   DirectExtentWriter direct_writer;
   EXPECT_TRUE(direct_writer.Init(fd(), extents, kBlockSize));
-  
+
   size_t bytes_written = 0;
   while (bytes_written < data.size()) {
     size_t bytes_to_write = min(data.size() - bytes_written, chunk_size);
@@ -134,14 +138,14 @@
     bytes_written += bytes_to_write;
   }
   EXPECT_TRUE(direct_writer.End());
-  
+
   struct stat stbuf;
   EXPECT_EQ(0, fstat(fd(), &stbuf));
   EXPECT_EQ(data.size(), stbuf.st_size);
-  
+
   vector<char> result_file;
   EXPECT_TRUE(utils::ReadFile(path(), &result_file));
-  
+
   vector<char> expected_file;
   expected_file.insert(expected_file.end(),
                        data.begin() + kBlockSize,
@@ -170,10 +174,10 @@
   extent.set_start_block(0);
   extent.set_num_blocks(1);
   extents.push_back(extent);
-  
+
   vector<char> data(kBlockSize * 2);
   FillWithData(&data);
-  
+
   DirectExtentWriter direct_writer;
   ZeroPadExtentWriter zero_pad_writer(&direct_writer);
 
@@ -185,14 +189,14 @@
   EXPECT_EQ(3, write(fd(), "xxx", 3));
   ASSERT_TRUE(zero_pad_writer.Write(&data[0], bytes_to_write));
   EXPECT_TRUE(zero_pad_writer.End());
-  
+
   struct stat stbuf;
   EXPECT_EQ(0, fstat(fd(), &stbuf));
   EXPECT_EQ(data.size(), stbuf.st_size);
-  
+
   vector<char> result_file;
   EXPECT_TRUE(utils::ReadFile(path(), &result_file));
-  
+
   vector<char> expected_file;
   expected_file.insert(expected_file.end(),
                        data.begin() + kBlockSize,
@@ -226,7 +230,7 @@
 
   DirectExtentWriter direct_writer;
   EXPECT_TRUE(direct_writer.Init(fd(), extents, kBlockSize));
-  
+
   size_t bytes_written = 0;
   while (bytes_written < (block_count * kBlockSize)) {
     size_t bytes_to_write = min(block_count * kBlockSize - bytes_written,
@@ -235,13 +239,13 @@
     bytes_written += bytes_to_write;
   }
   EXPECT_TRUE(direct_writer.End());
-  
+
   // check file size, then data inside
   ASSERT_EQ(2 * kBlockSize, utils::FileSize(path()));
-  
+
   vector<char> resultant_data;
   EXPECT_TRUE(utils::ReadFile(path(), &resultant_data));
-  
+
   // Create expected data
   vector<char> expected_data(on_disk_count * kBlockSize);
   vector<char> big(block_count * kBlockSize);
diff --git a/filesystem_copier_action.cc b/filesystem_copier_action.cc
index dbc3c29..d557eba 100644
--- a/filesystem_copier_action.cc
+++ b/filesystem_copier_action.cc
@@ -4,10 +4,10 @@
 
 #include "update_engine/filesystem_copier_action.h"
 
-#include <sys/stat.h>
-#include <sys/types.h>
 #include <errno.h>
 #include <fcntl.h>
+#include <sys/stat.h>
+#include <sys/types.h>
 
 #include <algorithm>
 #include <cstdlib>
@@ -20,7 +20,6 @@
 #include <gio/gunixoutputstream.h>
 #include <glib.h>
 
-#include "update_engine/filesystem_iterator.h"
 #include "update_engine/hardware_interface.h"
 #include "update_engine/subprocess.h"
 #include "update_engine/system_state.h"
diff --git a/filesystem_copier_action_unittest.cc b/filesystem_copier_action_unittest.cc
index 81c5bce..300708f 100644
--- a/filesystem_copier_action_unittest.cc
+++ b/filesystem_copier_action_unittest.cc
@@ -17,7 +17,6 @@
 
 #include "update_engine/fake_system_state.h"
 #include "update_engine/filesystem_copier_action.h"
-#include "update_engine/filesystem_iterator.h"
 #include "update_engine/mock_hardware.h"
 #include "update_engine/omaha_hash_calculator.h"
 #include "update_engine/test_utils.h"
diff --git a/payload_constants.cc b/payload_constants.cc
new file mode 100644
index 0000000..2fc31e3
--- /dev/null
+++ b/payload_constants.cc
@@ -0,0 +1,12 @@
+// Copyright 2014 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "update_engine/payload_constants.h"
+
+namespace chromeos_update_engine {
+
+const char kDeltaMagic[] = "CrAU";
+const char kBspatchPath[] = "bspatch";
+
+};  // namespace chromeos_update_engine
diff --git a/payload_constants.h b/payload_constants.h
new file mode 100644
index 0000000..4a4ec6f
--- /dev/null
+++ b/payload_constants.h
@@ -0,0 +1,21 @@
+// Copyright 2014 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_CONSTANTS_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_CONSTANTS_H_
+
+#include <base/basictypes.h>
+
+namespace chromeos_update_engine {
+
+extern const char kBspatchPath[];
+extern const char kDeltaMagic[];
+
+// A block number denoting a hole on a sparse file. Used on Extents to refer to
+// section of blocks not present on disk on a sparse file.
+const uint64_t kSparseHole = kuint64max;
+
+};  // namespace chromeos_update_engine
+
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_CONSTANTS_H_
diff --git a/cycle_breaker.cc b/payload_generator/cycle_breaker.cc
similarity index 96%
rename from cycle_breaker.cc
rename to payload_generator/cycle_breaker.cc
index 54fa51c..10ef6fb 100644
--- a/cycle_breaker.cc
+++ b/payload_generator/cycle_breaker.cc
@@ -2,14 +2,18 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#include "update_engine/cycle_breaker.h"
+#include "update_engine/payload_generator/cycle_breaker.h"
+
 #include <inttypes.h>
+
 #include <set>
 #include <utility>
+
 #include <base/strings/string_util.h>
 #include <base/strings/stringprintf.h>
-#include "update_engine/graph_utils.h"
-#include "update_engine/tarjan.h"
+
+#include "update_engine/payload_generator/graph_utils.h"
+#include "update_engine/payload_generator/tarjan.h"
 #include "update_engine/utils.h"
 
 using std::make_pair;
@@ -21,12 +25,12 @@
 // 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}".
@@ -36,7 +40,7 @@
 
   TarjanAlgorithm tarjan;
   skipped_ops_ = 0;
-    
+
   for (Graph::size_type i = 0; i < subgraph_.size(); i++) {
     DeltaArchiveManifest_InstallOperation_Type op_type = graph[i].op.type();
     if (op_type == DeltaArchiveManifest_InstallOperation_Type_REPLACE ||
@@ -68,7 +72,7 @@
         // add a subgraph_ edge
         if (utils::MapContainsKey(subgraph_[*it].out_edges, *jt))
           subgraph_[*it].subgraph_edges.insert(*jt);
-      }        
+      }
     }
 
     current_vertex_ = i;
@@ -78,7 +82,7 @@
     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());
diff --git a/cycle_breaker.h b/payload_generator/cycle_breaker.h
similarity index 86%
rename from cycle_breaker.h
rename to payload_generator/cycle_breaker.h
index 8bf2a3e..d0ae3fd 100644
--- a/cycle_breaker.h
+++ b/payload_generator/cycle_breaker.h
@@ -2,8 +2,8 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_CYCLE_BREAKER_H_
-#define CHROMEOS_PLATFORM_UPDATE_ENGINE_CYCLE_BREAKER_H_
+#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_CYCLE_BREAKER_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_CYCLE_BREAKER_H_
 
 // This is a modified implementation of Donald B. Johnson's algorithm for
 // finding all elementary cycles (a.k.a. circuits) in a directed graph.
@@ -22,7 +22,8 @@
 
 #include <set>
 #include <vector>
-#include "update_engine/graph_types.h"
+
+#include "update_engine/payload_generator/graph_types.h"
 
 namespace chromeos_update_engine {
 
@@ -31,7 +32,7 @@
   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:
@@ -47,7 +48,7 @@
   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_;
@@ -55,4 +56,4 @@
 
 }  // namespace chromeos_update_engine
 
-#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_CYCLE_BREAKER_H_
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_CYCLE_BREAKER_H_
diff --git a/cycle_breaker_unittest.cc b/payload_generator/cycle_breaker_unittest.cc
similarity index 97%
rename from cycle_breaker_unittest.cc
rename to payload_generator/cycle_breaker_unittest.cc
index 9922917..b2cd5d4 100644
--- a/cycle_breaker_unittest.cc
+++ b/payload_generator/cycle_breaker_unittest.cc
@@ -2,14 +2,17 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
+#include "update_engine/payload_generator/cycle_breaker.h"
+
 #include <set>
 #include <string>
 #include <utility>
 #include <vector>
+
+#include <base/logging.h>
 #include <gtest/gtest.h>
-#include "base/logging.h"
-#include "update_engine/cycle_breaker.h"
-#include "update_engine/graph_types.h"
+
+#include "update_engine/payload_generator/graph_types.h"
 #include "update_engine/utils.h"
 
 using std::make_pair;
@@ -59,10 +62,10 @@
   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
@@ -113,13 +116,13 @@
 // root, and that can massively speed up cycle cutting.
 TEST(CycleBreakerTest, AggressiveCutTest) {
   int counter = 0;
-  
+
   const int kNodesPerGroup = 4;
   const int kGroups = 33;
-  
+
   Graph graph(kGroups * kNodesPerGroup + 1);  // + 1 for the root node
   SetOpForNodes(&graph);
-  
+
   const Vertex::Index n_root = counter++;
 
   Vertex::Index last_hub = n_root;
@@ -129,7 +132,7 @@
       weight = 2;
     else if (i == (kGroups - 1))
       weight = 1;
-    
+
     const Vertex::Index next_hub = counter++;
 
     for (int j = 0; j < (kNodesPerGroup - 1); j++) {
@@ -139,18 +142,17 @@
     }
     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(),
@@ -198,7 +200,7 @@
   graph[n_i].out_edges.insert(EdgeWithWeight(n_j, 6));
 
   CycleBreaker breaker;
-  
+
   set<Edge> broken_edges;
   breaker.BreakCycles(graph, &broken_edges);
 
@@ -229,7 +231,7 @@
   graph[n_d].out_edges.insert(EdgeWithWeight(n_a, 2));
 
   CycleBreaker breaker;
-  
+
   set<Edge> broken_edges;
   breaker.BreakCycles(graph, &broken_edges);
 
@@ -254,10 +256,10 @@
   graph[n_c].out_edges.insert(EdgeWithWeight(n_b, 1));
 
   CycleBreaker breaker;
-  
+
   set<Edge> broken_edges;
   breaker.BreakCycles(graph, &broken_edges);
-  
+
   EXPECT_EQ(2, breaker.skipped_ops());
 }
 
diff --git a/delta_diff_generator.cc b/payload_generator/delta_diff_generator.cc
similarity index 98%
rename from delta_diff_generator.cc
rename to payload_generator/delta_diff_generator.cc
index 1ebf6bb..8fbbd0d 100644
--- a/delta_diff_generator.cc
+++ b/payload_generator/delta_diff_generator.cc
@@ -2,7 +2,7 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#include "update_engine/delta_diff_generator.h"
+#include "update_engine/payload_generator/delta_diff_generator.h"
 
 #include <errno.h>
 #include <fcntl.h>
@@ -17,8 +17,8 @@
 #include <utility>
 #include <vector>
 
-#include <base/files/file_path.h>
 #include <base/file_util.h>
+#include <base/files/file_path.h>
 #include <base/logging.h>
 #include <base/memory/scoped_ptr.h>
 #include <base/strings/string_number_conversions.h>
@@ -27,20 +27,21 @@
 #include <bzlib.h>
 
 #include "update_engine/bzip.h"
-#include "update_engine/cycle_breaker.h"
 #include "update_engine/delta_performer.h"
-#include "update_engine/extent_mapper.h"
 #include "update_engine/extent_ranges.h"
 #include "update_engine/file_writer.h"
-#include "update_engine/filesystem_iterator.h"
-#include "update_engine/full_update_generator.h"
-#include "update_engine/graph_types.h"
-#include "update_engine/graph_utils.h"
-#include "update_engine/metadata.h"
 #include "update_engine/omaha_hash_calculator.h"
+#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/cycle_breaker.h"
+#include "update_engine/payload_generator/extent_mapper.h"
+#include "update_engine/payload_generator/filesystem_iterator.h"
+#include "update_engine/payload_generator/full_update_generator.h"
+#include "update_engine/payload_generator/graph_types.h"
+#include "update_engine/payload_generator/graph_utils.h"
+#include "update_engine/payload_generator/metadata.h"
+#include "update_engine/payload_generator/topological_sort.h"
 #include "update_engine/payload_signer.h"
 #include "update_engine/subprocess.h"
-#include "update_engine/topological_sort.h"
 #include "update_engine/update_metadata.pb.h"
 #include "update_engine/utils.h"
 
@@ -53,6 +54,23 @@
 using std::string;
 using std::vector;
 
+namespace {
+
+const uint64_t kVersionNumber = 1;
+const uint64_t kFullUpdateChunkSize = 1024 * 1024;  // bytes
+
+const size_t kBlockSize = 4096;  // bytes
+const string kNonexistentPath = "";
+
+static const char* kInstallOperationTypes[] = {
+  "REPLACE",
+  "REPLACE_BZ",
+  "MOVE",
+  "BSDIFF"
+};
+
+}  // namespace
+
 namespace chromeos_update_engine {
 
 typedef DeltaDiffGenerator::Block Block;
@@ -61,8 +79,6 @@
 
 // bytes
 const size_t kRootFSPartitionSize = static_cast<size_t>(2) * 1024 * 1024 * 1024;
-const uint64_t kVersionNumber = 1;
-const uint64_t kFullUpdateChunkSize = 1024 * 1024;  // bytes
 
 // Needed for testing purposes, in case we can't use actual filesystem objects.
 // TODO(garnold)(chromium:331965) Replace this hack with a properly injected
@@ -72,16 +88,6 @@
     extent_mapper::ExtentsForFileChunkFibmap;
 
 namespace {
-const size_t kBlockSize = 4096;  // bytes
-const string kNonexistentPath = "";
-
-
-static const char* kInstallOperationTypes[] = {
-  "REPLACE",
-  "REPLACE_BZ",
-  "MOVE",
-  "BSDIFF"
-};
 
 // Stores all the extents of |path| into |extents|. Returns true on success.
 bool GatherExtents(const string& path,
@@ -1918,7 +1924,5 @@
 }
 
 const char* const kBsdiffPath = "bsdiff";
-const char* const kBspatchPath = "bspatch";
-const char* const kDeltaMagic = "CrAU";
 
 };  // namespace chromeos_update_engine
diff --git a/delta_diff_generator.h b/payload_generator/delta_diff_generator.h
similarity index 97%
rename from delta_diff_generator.h
rename to payload_generator/delta_diff_generator.h
index 2b620f0..596d9c0 100644
--- a/delta_diff_generator.h
+++ b/payload_generator/delta_diff_generator.h
@@ -2,13 +2,15 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_DELTA_DIFF_GENERATOR_H_
-#define CHROMEOS_PLATFORM_UPDATE_ENGINE_DELTA_DIFF_GENERATOR_H_
+#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_DELTA_DIFF_GENERATOR_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_DELTA_DIFF_GENERATOR_H_
 
 #include <string>
 #include <vector>
-#include "base/basictypes.h"
-#include "update_engine/graph_types.h"
+
+#include <base/basictypes.h>
+
+#include "update_engine/payload_generator/graph_types.h"
 #include "update_engine/update_metadata.pb.h"
 
 // There is one function in DeltaDiffGenerator of importance to users
@@ -267,10 +269,8 @@
 };
 
 extern const char* const kBsdiffPath;
-extern const char* const kBspatchPath;
-extern const char* const kDeltaMagic;
 extern const size_t kRootFSPartitionSize;
 
 };  // namespace chromeos_update_engine
 
-#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_DELTA_DIFF_GENERATOR_H_
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_DELTA_DIFF_GENERATOR_H_
diff --git a/delta_diff_generator_unittest.cc b/payload_generator/delta_diff_generator_unittest.cc
similarity index 98%
rename from delta_diff_generator_unittest.cc
rename to payload_generator/delta_diff_generator_unittest.cc
index c5c0fe6..05b173c 100644
--- a/delta_diff_generator_unittest.cc
+++ b/payload_generator/delta_diff_generator_unittest.cc
@@ -2,9 +2,9 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#include <sys/types.h>
-#include <sys/stat.h>
 #include <fcntl.h>
+#include <sys/stat.h>
+#include <sys/types.h>
 #include <unistd.h>
 
 #include <map>
@@ -18,16 +18,17 @@
 #include <base/strings/string_util.h>
 #include <gtest/gtest.h>
 
-#include "update_engine/cycle_breaker.h"
-#include "update_engine/delta_diff_generator.h"
 #include "update_engine/delta_performer.h"
-#include "update_engine/extent_mapper.h"
 #include "update_engine/extent_ranges.h"
-#include "update_engine/graph_types.h"
-#include "update_engine/graph_utils.h"
+#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/cycle_breaker.h"
+#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/extent_mapper.h"
+#include "update_engine/payload_generator/graph_types.h"
+#include "update_engine/payload_generator/graph_utils.h"
+#include "update_engine/payload_generator/topological_sort.h"
 #include "update_engine/subprocess.h"
 #include "update_engine/test_utils.h"
-#include "update_engine/topological_sort.h"
 #include "update_engine/utils.h"
 
 using std::make_pair;
diff --git a/extent_mapper.cc b/payload_generator/extent_mapper.cc
similarity index 91%
rename from extent_mapper.cc
rename to payload_generator/extent_mapper.cc
index 1cfd8bb..9e66619 100644
--- a/extent_mapper.cc
+++ b/payload_generator/extent_mapper.cc
@@ -2,22 +2,21 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#include "update_engine/extent_mapper.h"
-
-#include <sys/ioctl.h>
-#include <sys/types.h>
-#include <sys/stat.h>
+#include "update_engine/payload_generator/extent_mapper.h"
 
 #include <assert.h>
 #include <errno.h>
 #include <fcntl.h>
+#include <linux/fs.h>
 #include <stdio.h>
 #include <string.h>
+#include <sys/ioctl.h>
+#include <sys/stat.h>
+#include <sys/types.h>
 
-#include <linux/fs.h>
-
-#include "update_engine/graph_types.h"
-#include "update_engine/graph_utils.h"
+#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/graph_types.h"
+#include "update_engine/payload_generator/graph_utils.h"
 #include "update_engine/utils.h"
 
 using std::string;
diff --git a/extent_mapper.h b/payload_generator/extent_mapper.h
similarity index 86%
rename from extent_mapper.h
rename to payload_generator/extent_mapper.h
index 821fb3e..bc46e47 100644
--- a/extent_mapper.h
+++ b/payload_generator/extent_mapper.h
@@ -2,12 +2,14 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_EXTENT_MAPPER_H_
-#define CHROMEOS_PLATFORM_UPDATE_ENGINE_EXTENT_MAPPER_H_
+#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_MAPPER_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_MAPPER_H_
 
 #include <string>
 #include <vector>
-#include "base/basictypes.h"
+
+#include <base/basictypes.h>
+
 #include "update_engine/update_metadata.pb.h"
 
 namespace chromeos_update_engine {
@@ -41,4 +43,4 @@
 
 }  // namespace chromeos_update_engine
 
-#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_EXTENT_MAPPER_H_
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_MAPPER_H_
diff --git a/extent_mapper_unittest.cc b/payload_generator/extent_mapper_unittest.cc
similarity index 95%
rename from extent_mapper_unittest.cc
rename to payload_generator/extent_mapper_unittest.cc
index 3797b7a..3b23246 100644
--- a/extent_mapper_unittest.cc
+++ b/payload_generator/extent_mapper_unittest.cc
@@ -2,16 +2,20 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
+#include "update_engine/payload_generator/extent_mapper.h"
+
 #include <sys/stat.h>
 #include <sys/types.h>
 #include <unistd.h>
+
 #include <set>
 #include <string>
 #include <vector>
+
+#include <base/basictypes.h>
 #include <gtest/gtest.h>
-#include "base/basictypes.h"
-#include "update_engine/extent_mapper.h"
-#include "update_engine/graph_types.h"
+
+#include "update_engine/payload_constants.h"
 #include "update_engine/utils.h"
 
 using std::set;
@@ -86,11 +90,11 @@
   uint32_t block_size = 0;
   EXPECT_TRUE(extent_mapper::GetFilesystemBlockSize(buf, &block_size));
   EXPECT_GT(block_size, 0);
-  
+
   EXPECT_EQ(1, pwrite(fd, "x", 1, 0));
   EXPECT_EQ(1, pwrite(fd, "x", 1, 3 * block_size));
   close(fd);
-  
+
   vector<Extent> extents;
   EXPECT_TRUE(extent_mapper::ExtentsForFileFibmap(buf, &extents));
   unlink(buf);
diff --git a/filesystem_iterator.cc b/payload_generator/filesystem_iterator.cc
similarity index 96%
rename from filesystem_iterator.cc
rename to payload_generator/filesystem_iterator.cc
index af5f209..b7455fa 100644
--- a/filesystem_iterator.cc
+++ b/payload_generator/filesystem_iterator.cc
@@ -1,15 +1,19 @@
-// Copyright (c) 2009 The Chromium Authors. All rights reserved.
+// Copyright (c) 2009 The Chromium OS Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#include "update_engine/filesystem_iterator.h"
-#include <sys/types.h>
+#include "update_engine/payload_generator/filesystem_iterator.h"
+
 #include <dirent.h>
 #include <errno.h>
+#include <sys/types.h>
+
 #include <set>
 #include <string>
 #include <vector>
-#include "base/logging.h"
+
+#include <base/logging.h>
+
 #include "update_engine/utils.h"
 
 using std::set;
diff --git a/filesystem_iterator.h b/payload_generator/filesystem_iterator.h
similarity index 93%
rename from filesystem_iterator.h
rename to payload_generator/filesystem_iterator.h
index 67908ab..859965d 100644
--- a/filesystem_iterator.h
+++ b/payload_generator/filesystem_iterator.h
@@ -2,8 +2,8 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_FILESYSTEM_ITERATOR_H_
-#define CHROMEOS_PLATFORM_UPDATE_ENGINE_FILESYSTEM_ITERATOR_H_
+#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_FILESYSTEM_ITERATOR_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_FILESYSTEM_ITERATOR_H_
 
 // This class is used to walk a filesystem. It will iterate over every file
 // on the same device as the file passed in the ctor. Directories will be
@@ -24,12 +24,13 @@
 // 3. If you don't want that, you can just check Stat().st_dev and skip
 //    foreign filesystems manually.
 
+#include <dirent.h>
 #include <sys/stat.h>
 #include <sys/types.h>
-#include <dirent.h>
 #include <unistd.h>
-#include <string>
+
 #include <set>
+#include <string>
 #include <vector>
 
 namespace chromeos_update_engine {
@@ -123,4 +124,4 @@
 
 }  // namespace chromeos_update_engine
 
-#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_FILESYSTEM_ITERATOR_H_
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_FILESYSTEM_ITERATOR_H_
diff --git a/filesystem_iterator_unittest.cc b/payload_generator/filesystem_iterator_unittest.cc
similarity index 98%
rename from filesystem_iterator_unittest.cc
rename to payload_generator/filesystem_iterator_unittest.cc
index 83d699a..67ac177 100644
--- a/filesystem_iterator_unittest.cc
+++ b/payload_generator/filesystem_iterator_unittest.cc
@@ -2,16 +2,20 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
+#include "update_engine/payload_generator/filesystem_iterator.h"
+
 #include <sys/stat.h>
 #include <sys/types.h>
 #include <unistd.h>
+
 #include <set>
 #include <string>
 #include <vector>
-#include <gtest/gtest.h>
+
 #include <base/strings/string_util.h>
 #include <base/strings/stringprintf.h>
-#include "update_engine/filesystem_iterator.h"
+#include <gtest/gtest.h>
+
 #include "update_engine/test_utils.h"
 #include "update_engine/utils.h"
 
diff --git a/full_update_generator.cc b/payload_generator/full_update_generator.cc
similarity index 98%
rename from full_update_generator.cc
rename to payload_generator/full_update_generator.cc
index 3f32a1a..3a17594 100644
--- a/full_update_generator.cc
+++ b/payload_generator/full_update_generator.cc
@@ -2,10 +2,10 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#include "update_engine/full_update_generator.h"
+#include "update_engine/payload_generator/full_update_generator.h"
 
-#include <inttypes.h>
 #include <fcntl.h>
+#include <inttypes.h>
 
 #include <tr1/memory>
 
@@ -16,8 +16,8 @@
 #include "update_engine/utils.h"
 
 using std::deque;
-using std::min;
 using std::max;
+using std::min;
 using std::string;
 using std::tr1::shared_ptr;
 using std::vector;
diff --git a/full_update_generator.h b/payload_generator/full_update_generator.h
similarity index 79%
rename from full_update_generator.h
rename to payload_generator/full_update_generator.h
index 29e3919..4ca1aa4 100644
--- a/full_update_generator.h
+++ b/payload_generator/full_update_generator.h
@@ -2,12 +2,12 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_FULL_UPDATE_GENERATOR_H_
-#define CHROMEOS_PLATFORM_UPDATE_ENGINE_FULL_UPDATE_GENERATOR_H_
+#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_FULL_UPDATE_GENERATOR_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_FULL_UPDATE_GENERATOR_H_
 
 #include <glib.h>
 
-#include "update_engine/graph_types.h"
+#include "update_engine/payload_generator/graph_types.h"
 
 namespace chromeos_update_engine {
 
@@ -38,4 +38,4 @@
 
 }  // namespace chromeos_update_engine
 
-#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_FULL_UPDATE_GENERATOR_H_
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_FULL_UPDATE_GENERATOR_H_
diff --git a/full_update_generator_unittest.cc b/payload_generator/full_update_generator_unittest.cc
similarity index 97%
rename from full_update_generator_unittest.cc
rename to payload_generator/full_update_generator_unittest.cc
index c04773e..c3da115 100644
--- a/full_update_generator_unittest.cc
+++ b/payload_generator/full_update_generator_unittest.cc
@@ -7,7 +7,7 @@
 
 #include <gtest/gtest.h>
 
-#include "update_engine/full_update_generator.h"
+#include "update_engine/payload_generator/full_update_generator.h"
 #include "update_engine/test_utils.h"
 
 using std::string;
diff --git a/generate_delta_main.cc b/payload_generator/generate_delta_main.cc
similarity index 99%
rename from generate_delta_main.cc
rename to payload_generator/generate_delta_main.cc
index 71c4556..9dd6175 100644
--- a/generate_delta_main.cc
+++ b/payload_generator/generate_delta_main.cc
@@ -2,10 +2,10 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#include <sys/types.h>
-#include <sys/stat.h>
 #include <errno.h>
 #include <fcntl.h>
+#include <sys/stat.h>
+#include <sys/types.h>
 #include <unistd.h>
 
 #include <set>
@@ -19,8 +19,8 @@
 #include <gflags/gflags.h>
 #include <glib.h>
 
-#include "update_engine/delta_diff_generator.h"
 #include "update_engine/delta_performer.h"
+#include "update_engine/payload_generator/delta_diff_generator.h"
 #include "update_engine/payload_signer.h"
 #include "update_engine/prefs.h"
 #include "update_engine/subprocess.h"
diff --git a/graph_types.h b/payload_generator/graph_types.h
similarity index 89%
rename from graph_types.h
rename to payload_generator/graph_types.h
index e460b1a..c5531c2 100644
--- a/graph_types.h
+++ b/payload_generator/graph_types.h
@@ -2,15 +2,17 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_GRAPH_TYPES_H_
-#define CHROMEOS_PLATFORM_UPDATE_ENGINE_GRAPH_TYPES_H_
+#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_
 
 #include <map>
 #include <set>
 #include <string>
 #include <utility>
 #include <vector>
-#include "base/basictypes.h"
+
+#include <base/basictypes.h>
+
 #include "update_engine/update_metadata.pb.h"
 
 // A few classes that help in generating delta images use these types
@@ -73,10 +75,9 @@
 
 typedef std::pair<Vertex::Index, Vertex::Index> Edge;
 
-const uint64_t kSparseHole = kuint64max;
 const uint64_t kTempBlockStart = 1ULL << 60;
 COMPILE_ASSERT(kTempBlockStart != 0, kTempBlockStart_invalid);
 
 }  // namespace chromeos_update_engine
 
-#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_GRAPH_TYPES_H_
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_TYPES_H_
diff --git a/graph_utils.cc b/payload_generator/graph_utils.cc
similarity index 97%
rename from graph_utils.cc
rename to payload_generator/graph_utils.cc
index 3e3cc9e..8b6535d 100644
--- a/graph_utils.cc
+++ b/payload_generator/graph_utils.cc
@@ -2,7 +2,7 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#include "update_engine/graph_utils.h"
+#include "update_engine/payload_generator/graph_utils.h"
 
 #include <string>
 #include <utility>
@@ -11,6 +11,8 @@
 #include <base/basictypes.h>
 #include <base/logging.h>
 
+#include "update_engine/payload_constants.h"
+
 using std::make_pair;
 using std::pair;
 using std::string;
diff --git a/graph_utils.h b/payload_generator/graph_utils.h
similarity index 85%
rename from graph_utils.h
rename to payload_generator/graph_utils.h
index 30b9c0b..0489793 100644
--- a/graph_utils.h
+++ b/payload_generator/graph_utils.h
@@ -2,12 +2,14 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_GRAPH_UTILS_H_
-#define CHROMEOS_PLATFORM_UPDATE_ENGINE_GRAPH_UTILS_H_
+#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_UTILS_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_UTILS_H_
 
 #include <vector>
-#include "base/basictypes.h"
-#include "update_engine/graph_types.h"
+
+#include <base/basictypes.h>
+
+#include "update_engine/payload_generator/graph_types.h"
 #include "update_engine/update_metadata.pb.h"
 
 // A few utility functions for graphs
@@ -60,4 +62,4 @@
 
 }  // namespace chromeos_update_engine
 
-#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_GRAPH_UTILS_H_
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_GRAPH_UTILS_H_
diff --git a/graph_utils_unittest.cc b/payload_generator/graph_utils_unittest.cc
similarity index 97%
rename from graph_utils_unittest.cc
rename to payload_generator/graph_utils_unittest.cc
index 3bd9d16..0aed78d 100644
--- a/graph_utils_unittest.cc
+++ b/payload_generator/graph_utils_unittest.cc
@@ -7,8 +7,9 @@
 
 #include <gtest/gtest.h>
 
-#include "update_engine/graph_utils.h"
 #include "update_engine/extent_ranges.h"
+#include "update_engine/payload_constants.h"
+#include "update_engine/payload_generator/graph_utils.h"
 
 using std::make_pair;
 using std::vector;
diff --git a/metadata.cc b/payload_generator/metadata.cc
similarity index 98%
rename from metadata.cc
rename to payload_generator/metadata.cc
index 761ceb5..f0c9238 100644
--- a/metadata.cc
+++ b/payload_generator/metadata.cc
@@ -13,16 +13,16 @@
 #include <ext2fs/ext2fs.h>
 
 #include "update_engine/bzip.h"
-#include "update_engine/delta_diff_generator.h"
 #include "update_engine/extent_ranges.h"
-#include "update_engine/graph_utils.h"
-#include "update_engine/metadata.h"
+#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/graph_utils.h"
+#include "update_engine/payload_generator/metadata.h"
 #include "update_engine/utils.h"
 
+using base::StringPrintf;
 using std::min;
 using std::string;
 using std::vector;
-using base::StringPrintf;
 
 namespace chromeos_update_engine {
 
diff --git a/metadata.h b/payload_generator/metadata.h
similarity index 77%
rename from metadata.h
rename to payload_generator/metadata.h
index 45f5752..452e303 100644
--- a/metadata.h
+++ b/payload_generator/metadata.h
@@ -2,11 +2,11 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_METADATA_H_
-#define CHROMEOS_PLATFORM_UPDATE_ENGINE_METADATA_H_
+#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_METADATA_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_METADATA_H_
 
-#include "update_engine/delta_diff_generator.h"
-#include "update_engine/graph_types.h"
+#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/graph_types.h"
 
 namespace chromeos_update_engine {
 
@@ -34,4 +34,4 @@
 
 };  // namespace chromeos_update_engine
 
-#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_METADATA_H_
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_METADATA_H_
diff --git a/metadata_unittest.cc b/payload_generator/metadata_unittest.cc
similarity index 96%
rename from metadata_unittest.cc
rename to payload_generator/metadata_unittest.cc
index a1f3e48..39a2476 100644
--- a/metadata_unittest.cc
+++ b/payload_generator/metadata_unittest.cc
@@ -2,9 +2,9 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#include <sys/types.h>
-#include <sys/stat.h>
 #include <fcntl.h>
+#include <sys/stat.h>
+#include <sys/types.h>
 
 #include <string>
 #include <vector>
@@ -13,9 +13,9 @@
 #include <base/strings/stringprintf.h>
 #include <gtest/gtest.h>
 
-#include "update_engine/graph_types.h"
-#include "update_engine/delta_diff_generator.h"
-#include "update_engine/metadata.h"
+#include "update_engine/payload_generator/delta_diff_generator.h"
+#include "update_engine/payload_generator/graph_types.h"
+#include "update_engine/payload_generator/metadata.h"
 #include "update_engine/test_utils.h"
 #include "update_engine/utils.h"
 
diff --git a/tarjan.cc b/payload_generator/tarjan.cc
similarity index 95%
rename from tarjan.cc
rename to payload_generator/tarjan.cc
index 0e070ca..f3029c1 100644
--- a/tarjan.cc
+++ b/payload_generator/tarjan.cc
@@ -1,11 +1,13 @@
 // Copyright (c) 2010 The Chromium OS Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
+#include "update_engine/payload_generator/tarjan.h"
 
 #include <algorithm>
 #include <vector>
-#include "base/logging.h"
-#include "update_engine/tarjan.h"
+
+#include <base/logging.h>
+
 #include "update_engine/utils.h"
 
 using std::min;
@@ -58,7 +60,7 @@
       stack_.pop_back();
       component.push_back(other_vertex);
     } while (other_vertex != vertex && !stack_.empty());
-      
+
     if (utils::VectorContainsValue(component, required_vertex_)) {
       components_.resize(components_.size() + 1);
       component.swap(components_.back());
diff --git a/tarjan.h b/payload_generator/tarjan.h
similarity index 79%
rename from tarjan.h
rename to payload_generator/tarjan.h
index 53b0272..544cee3 100644
--- a/tarjan.h
+++ b/payload_generator/tarjan.h
@@ -2,8 +2,8 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_TARJAN_H_
-#define CHROMEOS_PLATFORM_UPDATE_ENGINE_TARJAN_H_
+#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_TARJAN_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_TARJAN_H_
 
 // This is an implemenation of Tarjan's algorithm which finds all
 // Strongly Connected Components in a graph.
@@ -13,7 +13,8 @@
 // component containing the vertex passed in.
 
 #include <vector>
-#include "update_engine/graph_types.h"
+
+#include "update_engine/payload_generator/graph_types.h"
 
 namespace chromeos_update_engine {
 
@@ -36,4 +37,4 @@
 
 }  // namespace chromeos_update_engine
 
-#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_TARJAN_H_
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_TARJAN_H_
diff --git a/tarjan_unittest.cc b/payload_generator/tarjan_unittest.cc
similarity index 94%
rename from tarjan_unittest.cc
rename to payload_generator/tarjan_unittest.cc
index a9f2c8b..a5fbac2 100644
--- a/tarjan_unittest.cc
+++ b/payload_generator/tarjan_unittest.cc
@@ -2,11 +2,14 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
+#include "update_engine/payload_generator/tarjan.h"
+
 #include <utility>
+
+#include <base/logging.h>
 #include <gtest/gtest.h>
-#include "base/logging.h"
-#include "update_engine/graph_types.h"
-#include "update_engine/tarjan.h"
+
+#include "update_engine/payload_generator/graph_types.h"
 #include "update_engine/utils.h"
 
 using std::make_pair;
@@ -31,7 +34,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()));
@@ -44,9 +47,9 @@
   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);
@@ -58,15 +61,15 @@
     EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_d));
     EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_e));
   }
-  
+
   {
     vector<Vertex::Index> vertex_indexes;
     tarjan.Execute(n_f, &graph, &vertex_indexes);
-    
+
     EXPECT_EQ(1, vertex_indexes.size());
     EXPECT_TRUE(utils::VectorContainsValue(vertex_indexes, n_f));
   }
-  
+
   for (Vertex::Index i = n_g; i <= n_h; i++) {
     vector<Vertex::Index> vertex_indexes;
     tarjan.Execute(i, &graph, &vertex_indexes);
diff --git a/topological_sort.cc b/payload_generator/topological_sort.cc
similarity index 92%
rename from topological_sort.cc
rename to payload_generator/topological_sort.cc
index 5af8cc4..3ee8c75 100644
--- a/topological_sort.cc
+++ b/payload_generator/topological_sort.cc
@@ -2,10 +2,12 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#include "update_engine/topological_sort.h"
+#include "update_engine/payload_generator/topological_sort.h"
+
 #include <set>
 #include <vector>
-#include "base/logging.h"
+
+#include <base/logging.h>
 
 using std::set;
 using std::vector;
diff --git a/topological_sort.h b/payload_generator/topological_sort.h
similarity index 70%
rename from topological_sort.h
rename to payload_generator/topological_sort.h
index 545d6d6..be130ce 100644
--- a/topological_sort.h
+++ b/payload_generator/topological_sort.h
@@ -2,12 +2,12 @@
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
-#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_TOPOLOGICAL_SORT_H_
-#define CHROMEOS_PLATFORM_UPDATE_ENGINE_TOPOLOGICAL_SORT_H_
-
+#ifndef CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_TOPOLOGICAL_SORT_H_
+#define CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_TOPOLOGICAL_SORT_H_
 
 #include <vector>
-#include "update_engine/graph_types.h"
+
+#include "update_engine/payload_generator/graph_types.h"
 
 namespace chromeos_update_engine {
 
@@ -27,4 +27,4 @@
 
 }  // namespace chromeos_update_engine
 
-#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_TOPOLOGICAL_SORT_H_
+#endif  // CHROMEOS_PLATFORM_UPDATE_ENGINE_PAYLOAD_GENERATOR_TOPOLOGICAL_SORT_H_
diff --git a/topological_sort_unittest.cc b/payload_generator/topological_sort_unittest.cc
similarity index 95%
rename from topological_sort_unittest.cc
rename to payload_generator/topological_sort_unittest.cc
index bddb0f0..696fd5b 100644
--- a/topological_sort_unittest.cc
+++ b/payload_generator/topological_sort_unittest.cc
@@ -4,9 +4,11 @@
 
 #include <utility>
 #include <vector>
+
 #include <gtest/gtest.h>
-#include "update_engine/graph_types.h"
-#include "update_engine/topological_sort.h"
+
+#include "update_engine/payload_generator/graph_types.h"
+#include "update_engine/payload_generator/topological_sort.h"
 
 using std::make_pair;
 using std::vector;
@@ -49,7 +51,7 @@
   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()));
diff --git a/payload_signer.cc b/payload_signer.cc
index e521314..1084109 100644
--- a/payload_signer.cc
+++ b/payload_signer.cc
@@ -9,9 +9,9 @@
 #include <base/strings/string_util.h>
 #include <openssl/pem.h>
 
-#include "update_engine/delta_diff_generator.h"
 #include "update_engine/delta_performer.h"
 #include "update_engine/omaha_hash_calculator.h"
+#include "update_engine/payload_generator/delta_diff_generator.h"
 #include "update_engine/subprocess.h"
 #include "update_engine/update_metadata.pb.h"
 #include "update_engine/utils.h"
diff --git a/test_utils.cc b/test_utils.cc
index 0005f03..723281a 100644
--- a/test_utils.cc
+++ b/test_utils.cc
@@ -4,28 +4,29 @@
 
 #include "update_engine/test_utils.h"
 
-#include <sys/stat.h>
-#include <sys/types.h>
 #include <errno.h>
 #include <stdio.h>
 #include <stdlib.h>
+#include <sys/stat.h>
+#include <sys/types.h>
 #include <unistd.h>
 
 #include <set>
 #include <string>
 #include <vector>
 
+#include <base/logging.h>
 #include <base/strings/string_util.h>
 #include <base/strings/stringprintf.h>
-#include "base/logging.h"
+
 #include "update_engine/file_writer.h"
-#include "update_engine/filesystem_iterator.h"
+#include "update_engine/payload_generator/filesystem_iterator.h"
 #include "update_engine/utils.h"
 
+using base::StringPrintf;
 using std::set;
 using std::string;
 using std::vector;
-using base::StringPrintf;
 
 namespace chromeos_update_engine {