diff --git a/Android.mk b/Android.mk
index fcde4f5..08798aa 100644
--- a/Android.mk
+++ b/Android.mk
@@ -611,8 +611,9 @@
 # for any client code.
 ue_libpayload_generator_exported_static_libraries := \
     libbsdiff \
-    libpayload_consumer \
     liblzma \
+    libpayload_consumer \
+    libpuffdiff \
     update_metadata-protos \
     $(ue_libpayload_consumer_exported_static_libraries) \
     $(ue_update_metadata_protos_exported_static_libraries)
@@ -661,8 +662,9 @@
 LOCAL_C_INCLUDES := $(ue_common_c_includes)
 LOCAL_STATIC_LIBRARIES := \
     libbsdiff \
-    libpayload_consumer \
     liblzma \
+    libpayload_consumer \
+    libpuffdiff \
     update_metadata-protos \
     $(ue_common_static_libraries) \
     $(ue_libpayload_consumer_exported_static_libraries) \
diff --git a/payload_generator/deflate_utils.cc b/payload_generator/deflate_utils.cc
index 9dd3fa4..7a5d9a4 100644
--- a/payload_generator/deflate_utils.cc
+++ b/payload_generator/deflate_utils.cc
@@ -33,6 +33,8 @@
 
 using std::string;
 using std::vector;
+using puffin::BitExtent;
+using puffin::ByteExtent;
 
 namespace chromeos_update_engine {
 namespace deflate_utils {
@@ -81,6 +83,9 @@
   for (auto& in_file : *files) {  // We need to modify so no constant.
     TEST_AND_RETURN_FALSE(
         ShiftExtentsOverExtents(file.extents, &in_file.extents));
+    TEST_AND_RETURN_FALSE(
+        ShiftBitExtentsOverExtents(file.extents, &in_file.deflates));
+
     in_file.name = file.name + "/" + in_file.name;
     num_blocks += BlocksInExtents(in_file.extents);
   }
@@ -90,8 +95,20 @@
   return true;
 }
 
+bool IsBitExtentInExtent(const Extent& extent, const BitExtent& bit_extent) {
+  return (bit_extent.offset / 8) >= (extent.start_block() * kBlockSize) &&
+         ((bit_extent.offset + bit_extent.length + 7) / 8) <=
+             ((extent.start_block() + extent.num_blocks()) * kBlockSize);
+}
+
 }  // namespace
 
+ByteExtent ExpandToByteExtent(const BitExtent& extent) {
+  uint64_t offset = extent.offset / 8;
+  uint64_t length = ((extent.offset + extent.length + 7) / 8) - offset;
+  return {offset, length};
+}
+
 bool ShiftExtentsOverExtents(const vector<Extent>& base_extents,
                              vector<Extent>* over_extents) {
   if (BlocksInExtents(base_extents) < BlocksInExtents(*over_extents)) {
@@ -133,8 +150,104 @@
   return true;
 }
 
+bool ShiftBitExtentsOverExtents(const vector<Extent>& base_extents,
+                                vector<BitExtent>* over_extents) {
+  if (over_extents->empty()) {
+    return true;
+  }
+
+  // This check is needed to make sure the number of bytes in |over_extents|
+  // does not exceed |base_extents|.
+  auto last_extent = ExpandToByteExtent(over_extents->back());
+  TEST_AND_RETURN_FALSE(last_extent.offset + last_extent.length <=
+                        BlocksInExtents(base_extents) * kBlockSize);
+
+  for (auto o_ext = over_extents->begin(); o_ext != over_extents->end();) {
+    size_t gap_blocks = base_extents[0].start_block();
+    size_t last_end_block = base_extents[0].start_block();
+    bool o_ext_processed = false;
+    for (auto b_ext : base_extents) {  // We need to modify |b_ext|, so we copy.
+      gap_blocks += b_ext.start_block() - last_end_block;
+      last_end_block = b_ext.start_block() + b_ext.num_blocks();
+      b_ext.set_start_block(b_ext.start_block() - gap_blocks);
+      auto byte_o_ext = ExpandToByteExtent(*o_ext);
+      if (byte_o_ext.offset >= b_ext.start_block() * kBlockSize &&
+          byte_o_ext.offset <
+              (b_ext.start_block() + b_ext.num_blocks()) * kBlockSize) {
+        if ((byte_o_ext.offset + byte_o_ext.length) <=
+            (b_ext.start_block() + b_ext.num_blocks()) * kBlockSize) {
+          // |o_ext| is inside |b_ext|, increase its start block.
+          o_ext->offset += gap_blocks * kBlockSize * 8;
+          ++o_ext;
+        } else {
+          // |o_ext| spills over this |b_ext|, remove it.
+          o_ext = over_extents->erase(o_ext);
+        }
+        o_ext_processed = true;
+        break;  // We processed o_ext, so break the loop;
+      }
+    }
+    TEST_AND_RETURN_FALSE(o_ext_processed);
+  }
+  return true;
+}
+
+vector<BitExtent> FindDeflates(const vector<Extent>& extents,
+                               const vector<BitExtent>& in_deflates) {
+  vector<BitExtent> result;
+  // TODO(ahassani): Replace this with binary_search style search.
+  for (const auto& deflate : in_deflates) {
+    for (const auto& extent : extents) {
+      if (IsBitExtentInExtent(extent, deflate)) {
+        result.push_back(deflate);
+        break;
+      }
+    }
+  }
+  return result;
+}
+
+bool CompactDeflates(const vector<Extent>& extents,
+                     const vector<BitExtent>& in_deflates,
+                     vector<BitExtent>* out_deflates) {
+  size_t bytes_passed = 0;
+  out_deflates->reserve(in_deflates.size());
+  for (const auto& extent : extents) {
+    size_t gap_bytes = extent.start_block() * kBlockSize - bytes_passed;
+    for (const auto& deflate : in_deflates) {
+      if (IsBitExtentInExtent(extent, deflate)) {
+        out_deflates->emplace_back(deflate.offset - (gap_bytes * 8),
+                                   deflate.length);
+      }
+    }
+    bytes_passed += extent.num_blocks() * kBlockSize;
+  }
+
+  // All given |in_deflates| items should've been inside one of the extents in
+  // |extents|.
+  TEST_AND_RETURN_FALSE(in_deflates.size() == out_deflates->size());
+
+  // Make sure all outgoing deflates are ordered and non-overlapping.
+  auto result = std::adjacent_find(out_deflates->begin(),
+                                   out_deflates->end(),
+                                   [](const BitExtent& a, const BitExtent& b) {
+                                     return (a.offset + a.length) > b.offset;
+                                   });
+  TEST_AND_RETURN_FALSE(result == out_deflates->end());
+  return true;
+}
+
+bool FindAndCompactDeflates(const vector<Extent>& extents,
+                            const vector<BitExtent>& in_deflates,
+                            vector<BitExtent>* out_deflates) {
+  auto found_deflates = FindDeflates(extents, in_deflates);
+  TEST_AND_RETURN_FALSE(CompactDeflates(extents, found_deflates, out_deflates));
+  return true;
+}
+
 bool PreprocessParitionFiles(const PartitionConfig& part,
-                             vector<FilesystemInterface::File>* result_files) {
+                             vector<FilesystemInterface::File>* result_files,
+                             bool extract_deflates) {
   // Get the file system files.
   vector<FilesystemInterface::File> tmp_files;
   part.fs_interface->GetFiles(&tmp_files);
@@ -149,15 +262,18 @@
       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());
+      auto sqfs =
+          SquashfsFilesystem::CreateFromFile(path.value(), extract_deflates);
       if (sqfs) {
         // It is an squashfs file. Get its files to replace with itself.
         vector<FilesystemInterface::File> files;
         sqfs->GetFiles(&files);
 
-        // Replace squashfs file with its files only if |files| has at
-        // least two files.
-        if (files.size() > 1) {
+        // Replace squashfs file with its files only if |files| has at least two
+        // files or if it has some deflates (since it is better to replace it to
+        // take advantage of the deflates.)
+        if (files.size() > 1 ||
+            (files.size() == 1 && !files[0].deflates.empty())) {
           TEST_AND_RETURN_FALSE(RealignSplittedFiles(file, &files));
           result_files->insert(result_files->end(), files.begin(), files.end());
           continue;
@@ -170,7 +286,6 @@
     // TODO(ahassani): Process other types of files like apk, zip, etc.
     result_files->push_back(file);
   }
-
   return true;
 }
 
diff --git a/payload_generator/deflate_utils.h b/payload_generator/deflate_utils.h
index 31082c3..798ce25 100644
--- a/payload_generator/deflate_utils.h
+++ b/payload_generator/deflate_utils.h
@@ -17,6 +17,7 @@
 #ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_DEFLATE_UTILS_H_
 #define UPDATE_ENGINE_PAYLOAD_GENERATOR_DEFLATE_UTILS_H_
 
+#include <puffin/puffdiff.h>
 #include <vector>
 
 #include "update_engine/payload_generator/filesystem_interface.h"
@@ -25,8 +26,15 @@
 namespace chromeos_update_engine {
 namespace deflate_utils {
 
+// Gets the files from the partition and processes all its files. Processing
+// includes:
+//  - splitting large Squashfs containers into its smaller files.
+bool PreprocessParitionFiles(const PartitionConfig& part,
+                             std::vector<FilesystemInterface::File>* result,
+                             bool extract_deflates);
+
 // Spreads all extents in |over_extents| over |base_extents|. Here we assume the
-// extents are non-overlapping.
+// |over_extents| are non-overlapping and sorted by their offset.
 //
 // |base_extents|:
 // |               -----------------------        ------         --------------
@@ -38,11 +46,51 @@
 bool ShiftExtentsOverExtents(const std::vector<Extent>& base_extents,
                              std::vector<Extent>* over_extents);
 
-// Gets the files from the partition and processes all its files. Processing
-// includes:
-//  - splitting large Squashfs containers into its smaller files.
-bool PreprocessParitionFiles(const PartitionConfig& part,
-                             std::vector<FilesystemInterface::File>* result);
+// Spreads all extents in |over_extents| over |base_extents|. Here we assume the
+// |over_extents| are non-overlapping and sorted by their offset. An item in
+// |over_extents| is removed if it is spread in two or more extents in
+// |base_extents|.
+//
+// |base_extents|:
+// |               -----------------------        ------         --------------
+// |over_extents|:
+// |  ==========  ====    ==========  ======
+// |over_extents| is transforms to:
+// |                 ==========  ====                                 ======
+//
+bool ShiftBitExtentsOverExtents(const std::vector<Extent>& base_extents,
+                                std::vector<puffin::BitExtent>* over_extents);
+
+// Finds all deflate locations in |deflates| that are inside an Extent in
+// |extents|. This function should not change the order of deflates.
+std::vector<puffin::BitExtent> FindDeflates(
+    const std::vector<Extent>& extents,
+    const std::vector<puffin::BitExtent>& deflates);
+
+// Creates a new list of deflate locations (|out_deflates|) from |in_deflates|
+// by assuming all extents in the |extents| have been put together
+// linearly. This function assumes that all deflate locations given in
+// |in_deflates| are located somewhere in the |extents|. |out_deflates| should
+// be empty on call.
+//
+// |extents|:
+// |               -----------------------        ------         --------------
+// |in_deflates|:
+// |                   ========  ====              ====           ======
+// |out_deflates|:
+// |    ========  ====      ====  ======
+//
+bool CompactDeflates(const std::vector<Extent>& extents,
+                     const std::vector<puffin::BitExtent>& in_deflates,
+                     std::vector<puffin::BitExtent>* out_deflates);
+
+// Combines |FindDeflates| and |CompcatDeflates| for ease of use.
+bool FindAndCompactDeflates(const std::vector<Extent>& extents,
+                            const std::vector<puffin::BitExtent>& in_deflates,
+                            std::vector<puffin::BitExtent>* out_deflates);
+
+// Expands a BitExtents to a ByteExtent.
+puffin::ByteExtent ExpandToByteExtent(const puffin::BitExtent& extent);
 
 }  // namespace deflate_utils
 }  // namespace chromeos_update_engine
diff --git a/payload_generator/deflate_utils_unittest.cc b/payload_generator/deflate_utils_unittest.cc
index 8774ef0..cb9476a 100644
--- a/payload_generator/deflate_utils_unittest.cc
+++ b/payload_generator/deflate_utils_unittest.cc
@@ -30,15 +30,27 @@
 #include "update_engine/payload_generator/extent_utils.h"
 
 using std::vector;
+using puffin::BitExtent;
+using puffin::ByteExtent;
 
 namespace chromeos_update_engine {
 namespace deflate_utils {
 
+// This creates a sudo-random BitExtents from ByteExtents for simpler testing.
+vector<BitExtent> ByteToBitExtent(const vector<ByteExtent>& byte_extents) {
+  vector<BitExtent> bit_extents;
+  for (auto& byte_extent : byte_extents) {
+    bit_extents.emplace_back(byte_extent.offset * 8 + (byte_extent.offset & 7),
+                             byte_extent.length * 8 - (byte_extent.length & 7));
+  }
+  return bit_extents;
+}
+
 TEST(DeflateUtilsTest, ExtentsShiftTest) {
   vector<Extent> base_extents = {ExtentForRange(10, 10),
-                                 ExtentForRange(30, 10),
-                                 ExtentForRange(50, 10),
                                  ExtentForRange(70, 10),
+                                 ExtentForRange(50, 10),
+                                 ExtentForRange(30, 10),
                                  ExtentForRange(90, 10)};
   vector<Extent> over_extents = {ExtentForRange(2, 2),
                                  ExtentForRange(5, 2),
@@ -49,10 +61,10 @@
   vector<Extent> out_over_extents = {ExtentForRange(12, 2),
                                      ExtentForRange(15, 2),
                                      ExtentForRange(17, 3),
-                                     ExtentForRange(33, 7),
+                                     ExtentForRange(73, 7),
                                      ExtentForRange(50, 3),
                                      ExtentForRange(55, 5),
-                                     ExtentForRange(70, 10),
+                                     ExtentForRange(30, 10),
                                      ExtentForRange(90, 5),
                                      ExtentForRange(97, 3)};
   EXPECT_TRUE(ShiftExtentsOverExtents(base_extents, &over_extents));
@@ -64,5 +76,115 @@
   EXPECT_FALSE(ShiftExtentsOverExtents(base_extents, &over_extents));
 }
 
+TEST(DeflateUtilsTest, ShiftBitExtentsOverExtentsTest) {
+  vector<Extent> base_extents = {ExtentForRange(3, 1),
+                                 ExtentForRange(1, 1),
+                                 ExtentForRange(5, 1),
+                                 ExtentForRange(7, 1),
+                                 ExtentForRange(9, 1)};
+  vector<BitExtent> over_extents =
+      ByteToBitExtent({{0, 0}, {100, 2000}, {4096, 0}, {5000, 5000}});
+  vector<BitExtent> out_over_extents =
+      ByteToBitExtent({{12288, 0}, {12388, 2000}, {4096, 0}});
+  ASSERT_TRUE(ShiftBitExtentsOverExtents(base_extents, &over_extents));
+  EXPECT_EQ(over_extents, out_over_extents);
+}
+
+TEST(DeflateUtilsTest, ShiftBitExtentsOverExtentsBoundaryTest) {
+  vector<Extent> base_extents = {ExtentForRange(1, 1)};
+  vector<BitExtent> over_extents = ByteToBitExtent({{2, 4096}});
+  vector<BitExtent> out_over_extents = {};
+  EXPECT_FALSE(ShiftBitExtentsOverExtents(base_extents, &over_extents));
+
+  base_extents = {ExtentForRange(1, 1)};
+  over_extents = {};
+  out_over_extents = {};
+  EXPECT_TRUE(ShiftBitExtentsOverExtents(base_extents, &over_extents));
+  EXPECT_EQ(over_extents, out_over_extents);
+
+  base_extents = {};
+  over_extents = {};
+  out_over_extents = {};
+  EXPECT_TRUE(ShiftBitExtentsOverExtents(base_extents, &over_extents));
+  EXPECT_EQ(over_extents, out_over_extents);
+
+  base_extents = {};
+  over_extents = ByteToBitExtent({{0, 1}});
+  out_over_extents = ByteToBitExtent({{0, 1}});
+  EXPECT_FALSE(ShiftBitExtentsOverExtents(base_extents, &over_extents));
+  EXPECT_EQ(over_extents, out_over_extents);
+
+  base_extents = {ExtentForRange(1, 2)};
+  over_extents = ByteToBitExtent({{0, 3 * 4096}, {4 * 4096, 4096}});
+  out_over_extents = ByteToBitExtent({{0, 3 * 4096}, {4 * 4096, 4096}});
+  EXPECT_FALSE(ShiftBitExtentsOverExtents(base_extents, &over_extents));
+  EXPECT_EQ(over_extents, out_over_extents);
+}
+
+TEST(DeflateUtilsTest, FindDeflatesTest) {
+  vector<Extent> extents = {
+      ExtentForRange(1, 1), ExtentForRange(3, 1), ExtentForRange(5, 1)};
+  vector<BitExtent> in_deflates = ByteToBitExtent({{0, 0},
+                                                   {10, 400},
+                                                   {4096, 0},
+                                                   {3000, 2000},
+                                                   {4096, 100},
+                                                   {4097, 100},
+                                                   {8100, 92},
+                                                   {8100, 93},
+                                                   {8100, 6000},
+                                                   {25000, 1}});
+  vector<BitExtent> expected_out_deflates =
+      ByteToBitExtent({{4096, 0}, {4096, 100}, {4097, 100}, {8100, 92}});
+  vector<BitExtent> out_deflates;
+  out_deflates = FindDeflates(extents, in_deflates);
+  EXPECT_EQ(out_deflates, expected_out_deflates);
+}
+
+TEST(DeflateUtilsTest, FindDeflatesBoundaryTest) {
+  vector<Extent> extents = {};
+  vector<BitExtent> in_deflates = ByteToBitExtent({{0, 0}, {8100, 93}});
+  vector<BitExtent> expected_out_deflates = {};
+  vector<BitExtent> out_deflates;
+  out_deflates = FindDeflates(extents, in_deflates);
+  EXPECT_EQ(out_deflates, expected_out_deflates);
+
+  extents = {};
+  in_deflates = {};
+  out_deflates = FindDeflates(extents, in_deflates);
+  EXPECT_EQ(out_deflates, expected_out_deflates);
+}
+
+TEST(DeflateUtilsTest, CompactTest) {
+  vector<Extent> extents = {
+      ExtentForRange(1, 1), ExtentForRange(5, 1), ExtentForRange(3, 1)};
+  vector<BitExtent> in_deflates =
+      ByteToBitExtent({{4096, 0}, {12288, 4096}, {4096, 100}, {20480, 100}});
+  vector<BitExtent> expected_out_deflates =
+      ByteToBitExtent({{0, 0}, {0, 100}, {4096, 100}, {8192, 4096}});
+  vector<BitExtent> out_deflates;
+  ASSERT_TRUE(CompactDeflates(extents, in_deflates, &out_deflates));
+  EXPECT_EQ(out_deflates, expected_out_deflates);
+}
+
+TEST(DeflateUtilsTest, CompactBoundaryTest) {
+  vector<Extent> extents = {};
+  vector<BitExtent> in_deflates = ByteToBitExtent({{4096, 0}});
+  vector<BitExtent> expected_out_deflates = {};
+  vector<BitExtent> out_deflates;
+  EXPECT_FALSE(CompactDeflates(extents, in_deflates, &out_deflates));
+  EXPECT_EQ(out_deflates, expected_out_deflates);
+
+  extents = {};
+  in_deflates = {};
+  ASSERT_TRUE(CompactDeflates(extents, in_deflates, &out_deflates));
+  EXPECT_EQ(out_deflates, expected_out_deflates);
+
+  extents = {ExtentForRange(1, 1)};
+  in_deflates = {};
+  ASSERT_TRUE(CompactDeflates(extents, in_deflates, &out_deflates));
+  EXPECT_EQ(out_deflates, expected_out_deflates);
+}
+
 }  // namespace deflate_utils
 }  // namespace chromeos_update_engine
diff --git a/payload_generator/delta_diff_utils.cc b/payload_generator/delta_diff_utils.cc
index 39438dd..b2b6b51 100644
--- a/payload_generator/delta_diff_utils.cc
+++ b/payload_generator/delta_diff_utils.cc
@@ -18,7 +18,7 @@
 
 #include <endian.h>
 #if defined(__clang__)
-// TODO: Remove these pragmas when b/35721782 is fixed.
+// TODO(*): Remove these pragmas when b/35721782 is fixed.
 #pragma clang diagnostic push
 #pragma clang diagnostic ignored "-Wmacro-redefined"
 #endif
@@ -30,9 +30,12 @@
 
 #include <algorithm>
 #include <map>
+#include <memory>
+#include <utility>
 
 #include <base/files/file_util.h>
 #include <base/format_macros.h>
+#include <base/strings/string_util.h>
 #include <base/strings/stringprintf.h>
 #include <base/threading/simple_thread.h>
 #include <bsdiff/bsdiff.h>
@@ -46,6 +49,7 @@
 #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/squashfs_filesystem.h"
 #include "update_engine/payload_generator/xz.h"
 
 using std::map;
@@ -64,8 +68,8 @@
 
 // The maximum destination size allowed for puffdiff. In general, puffdiff
 // should work for arbitrary big files, but the payload application is quite
-// memory intensive, so we limit these operations to 50 MiB.
-const uint64_t kMaxPuffdiffDestinationSize = 50 * 1024 * 1024;  // bytes
+// memory intensive, so we limit these operations to 150 MiB.
+const uint64_t kMaxPuffdiffDestinationSize = 150 * 1024 * 1024;  // bytes
 
 // 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
@@ -176,6 +180,8 @@
                      const PayloadVersion& version,
                      const vector<Extent>& old_extents,
                      const vector<Extent>& new_extents,
+                     const vector<puffin::BitExtent>& old_deflates,
+                     const vector<puffin::BitExtent>& new_deflates,
                      const string& name,
                      ssize_t chunk_blocks,
                      BlobFileWriter* blob_file)
@@ -184,6 +190,8 @@
         version_(version),
         old_extents_(old_extents),
         new_extents_(new_extents),
+        old_deflates_(old_deflates),
+        new_deflates_(new_deflates),
         name_(name),
         chunk_blocks_(chunk_blocks),
         blob_file_(blob_file) {}
@@ -208,6 +216,8 @@
   // The block ranges of the old/new file within the src/tgt image
   const vector<Extent> old_extents_;
   const vector<Extent> new_extents_;
+  const vector<puffin::BitExtent> old_deflates_;
+  const vector<puffin::BitExtent> new_deflates_;
   const string name_;
   // Block limit of one aop.
   ssize_t chunk_blocks_;
@@ -230,6 +240,8 @@
                      new_part_,
                      old_extents_,
                      new_extents_,
+                     old_deflates_,
+                     new_deflates_,
                      name_,
                      chunk_blocks_,
                      version_,
@@ -266,19 +278,20 @@
       &old_visited_blocks,
       &new_visited_blocks));
 
-  map<string, vector<Extent>> old_files_map;
+  bool puffdiff_allowed = version.OperationAllowed(InstallOperation::PUFFDIFF);
+  map<string, FilesystemInterface::File> old_files_map;
   if (old_part.fs_interface) {
     vector<FilesystemInterface::File> old_files;
-    TEST_AND_RETURN_FALSE(
-        deflate_utils::PreprocessParitionFiles(old_part, &old_files));
+    TEST_AND_RETURN_FALSE(deflate_utils::PreprocessParitionFiles(
+        old_part, &old_files, puffdiff_allowed));
     for (const FilesystemInterface::File& file : old_files)
-      old_files_map[file.name] = file.extents;
+      old_files_map[file.name] = file;
   }
 
   TEST_AND_RETURN_FALSE(new_part.fs_interface);
   vector<FilesystemInterface::File> new_files;
-  TEST_AND_RETURN_FALSE(
-      deflate_utils::PreprocessParitionFiles(new_part, &new_files));
+  TEST_AND_RETURN_FALSE(deflate_utils::PreprocessParitionFiles(
+      new_part, &new_files, puffdiff_allowed));
 
   vector<FileDeltaProcessor> file_delta_processors;
 
@@ -309,8 +322,9 @@
     // from using a graph/cycle detection/etc to generate diffs, and at that
     // time, it will be easy (non-complex) to have many operations read
     // from the same source blocks. At that time, this code can die. -adlr
-    vector<Extent> old_file_extents = FilterExtentRanges(
-        old_files_map[new_file.name], old_visited_blocks);
+    auto old_file = old_files_map[new_file.name];
+    vector<Extent> old_file_extents =
+        FilterExtentRanges(old_file.extents, old_visited_blocks);
     old_visited_blocks.AddExtents(old_file_extents);
 
     file_delta_processors.emplace_back(old_part.path,
@@ -318,6 +332,8 @@
                                        version,
                                        std::move(old_file_extents),
                                        std::move(new_file_extents),
+                                       old_file.deflates,
+                                       new_file.deflates,
                                        new_file.name,  // operation name
                                        hard_chunk_blocks,
                                        blob_file);
@@ -361,6 +377,8 @@
                                       new_part.path,
                                       old_unvisited,
                                       new_unvisited,
+                                      {},                 // old_deflates,
+                                      {},                 // new_deflates
                                       "<non-file-data>",  // operation name
                                       soft_chunk_blocks,
                                       version,
@@ -465,6 +483,8 @@
                                         new_part,
                                         vector<Extent>(),        // old_extents
                                         vector<Extent>{extent},  // new_extents
+                                        {},                      // old_deflates
+                                        {},                      // new_deflates
                                         "<zeros>",
                                         chunk_blocks,
                                         version,
@@ -525,6 +545,8 @@
                    const string& new_part,
                    const vector<Extent>& old_extents,
                    const vector<Extent>& new_extents,
+                   const vector<puffin::BitExtent>& old_deflates,
+                   const vector<puffin::BitExtent>& new_deflates,
                    const string& name,
                    ssize_t chunk_blocks,
                    const PayloadVersion& version,
@@ -553,6 +575,8 @@
                                             new_part,
                                             old_extents_chunk,
                                             new_extents_chunk,
+                                            old_deflates,
+                                            new_deflates,
                                             version,
                                             &data,
                                             &operation));
@@ -643,6 +667,8 @@
                        const string& new_part,
                        const vector<Extent>& old_extents,
                        const vector<Extent>& new_extents,
+                       const vector<puffin::BitExtent>& old_deflates,
+                       const vector<puffin::BitExtent>& new_deflates,
                        const PayloadVersion& version,
                        brillo::Blob* out_data,
                        InstallOperation* out_op) {
@@ -731,8 +757,58 @@
         }
       }
       if (puffdiff_allowed) {
-        LOG(ERROR) << "puffdiff is not supported yet!";
-        return false;
+        // Find all deflate positions inside the given extents and then put all
+        // deflates together because we have already read all the extents into
+        // one buffer.
+        vector<puffin::BitExtent> src_deflates;
+        TEST_AND_RETURN_FALSE(deflate_utils::FindAndCompactDeflates(
+            src_extents, old_deflates, &src_deflates));
+
+        vector<puffin::BitExtent> dst_deflates;
+        TEST_AND_RETURN_FALSE(deflate_utils::FindAndCompactDeflates(
+            dst_extents, new_deflates, &dst_deflates));
+
+        // Remove equal deflates. TODO(*): We can do a N*N check using
+        // hashing. It will not reduce the payload size, but it will speeds up
+        // the puffing on the client device.
+        auto src = src_deflates.begin();
+        auto dst = dst_deflates.begin();
+        for (; src != src_deflates.end() && dst != dst_deflates.end();) {
+          auto src_in_bytes = deflate_utils::ExpandToByteExtent(*src);
+          auto dst_in_bytes = deflate_utils::ExpandToByteExtent(*dst);
+          if (src_in_bytes.length == dst_in_bytes.length &&
+              !memcmp(old_data.data() + src_in_bytes.offset,
+                      new_data.data() + dst_in_bytes.offset,
+                      src_in_bytes.length)) {
+            src = src_deflates.erase(src);
+            dst = dst_deflates.erase(dst);
+          } else {
+            src++;
+            dst++;
+          }
+        }
+
+        // Only Puffdiff if both files have at least one deflate left.
+        if (!src_deflates.empty() && !dst_deflates.empty()) {
+          brillo::Blob puffdiff_delta;
+          string temp_file_path;
+          TEST_AND_RETURN_FALSE(utils::MakeTempFile(
+              "puffdiff-delta.XXXXXX", &temp_file_path, nullptr));
+          ScopedPathUnlinker temp_file_unlinker(temp_file_path);
+
+          // Perform PuffDiff operation.
+          TEST_AND_RETURN_FALSE(puffin::PuffDiff(old_data,
+                                                 new_data,
+                                                 src_deflates,
+                                                 dst_deflates,
+                                                 temp_file_path,
+                                                 &puffdiff_delta));
+          TEST_AND_RETURN_FALSE(puffdiff_delta.size() > 0);
+          if (puffdiff_delta.size() < data_blob.size()) {
+            operation.set_type(InstallOperation::PUFFDIFF);
+            data_blob = std::move(puffdiff_delta);
+          }
+        }
       }
     }
   }
diff --git a/payload_generator/delta_diff_utils.h b/payload_generator/delta_diff_utils.h
index d21468f..dea8535 100644
--- a/payload_generator/delta_diff_utils.h
+++ b/payload_generator/delta_diff_utils.h
@@ -21,6 +21,7 @@
 #include <vector>
 
 #include <brillo/secure_blob.h>
+#include <puffin/puffdiff.h>
 
 #include "update_engine/payload_generator/annotated_operation.h"
 #include "update_engine/payload_generator/extent_ranges.h"
@@ -76,12 +77,15 @@
 // stored in |new_part| in the blocks described by |new_extents| and, if it
 // exists, the old version exists in |old_part| in the blocks described by
 // |old_extents|. The operations added to |aops| reference the data blob
-// in the |blob_file|. Returns true on success.
+// in the |blob_file|. |old_deflates| and |new_deflates| are all deflate
+// locations in |old_part| and |new_part|. Returns true on success.
 bool DeltaReadFile(std::vector<AnnotatedOperation>* aops,
                    const std::string& old_part,
                    const std::string& new_part,
                    const std::vector<Extent>& old_extents,
                    const std::vector<Extent>& new_extents,
+                   const std::vector<puffin::BitExtent>& old_deflates,
+                   const std::vector<puffin::BitExtent>& new_deflates,
                    const std::string& name,
                    ssize_t chunk_blocks,
                    const PayloadVersion& version,
@@ -94,11 +98,14 @@
 // MOVE or SOURCE_COPY operation. If there is a change, the smallest of the
 // operations allowed in the given |version| (REPLACE, REPLACE_BZ, BSDIFF,
 // SOURCE_BSDIFF, or PUFFDIFF) wins.
-// |new_extents| must not be empty. Returns true on success.
+// |new_extents| must not be empty. |old_deflates| and |new_deflates| are all
+// the deflate locations in |old_part| and |new_part|. Returns true on success.
 bool ReadExtentsToDiff(const std::string& old_part,
                        const std::string& new_part,
                        const std::vector<Extent>& old_extents,
                        const std::vector<Extent>& new_extents,
+                       const std::vector<puffin::BitExtent>& old_deflates,
+                       const std::vector<puffin::BitExtent>& new_deflates,
                        const PayloadVersion& version,
                        brillo::Blob* out_data,
                        InstallOperation* out_op);
diff --git a/payload_generator/delta_diff_utils_unittest.cc b/payload_generator/delta_diff_utils_unittest.cc
index 34e33ad..46e68c5 100644
--- a/payload_generator/delta_diff_utils_unittest.cc
+++ b/payload_generator/delta_diff_utils_unittest.cc
@@ -179,6 +179,8 @@
       new_part_.path,
       old_extents,
       new_extents,
+      {},  // old_deflates
+      {},  // new_deflates
       PayloadVersion(kChromeOSMajorPayloadVersion, kInPlaceMinorPayloadVersion),
       &data,
       &op));
@@ -238,6 +240,8 @@
       new_part_.path,
       old_extents,
       new_extents,
+      {},  // old_deflates
+      {},  // new_deflates
       PayloadVersion(kChromeOSMajorPayloadVersion, kInPlaceMinorPayloadVersion),
       &data,
       &op));
@@ -301,6 +305,8 @@
       new_part_.path,
       old_extents,
       new_extents,
+      {},  // old_deflates
+      {},  // new_deflates
       PayloadVersion(kChromeOSMajorPayloadVersion, kInPlaceMinorPayloadVersion),
       &data,
       &op));
@@ -349,6 +355,8 @@
         new_part_.path,
         old_extents,
         new_extents,
+        {},  // old_deflates
+        {},  // new_deflates
         PayloadVersion(kChromeOSMajorPayloadVersion,
                        kInPlaceMinorPayloadVersion),
         &data,
@@ -390,6 +398,8 @@
       new_part_.path,
       old_extents,
       new_extents,
+      {},  // old_deflates
+      {},  // new_deflates
       PayloadVersion(kChromeOSMajorPayloadVersion, kSourceMinorPayloadVersion),
       &data,
       &op));
@@ -422,6 +432,8 @@
       new_part_.path,
       old_extents,
       new_extents,
+      {},  // old_deflates
+      {},  // new_deflates
       PayloadVersion(kChromeOSMajorPayloadVersion, kSourceMinorPayloadVersion),
       &data,
       &op));
diff --git a/payload_generator/filesystem_interface.h b/payload_generator/filesystem_interface.h
index 866c46b..b1506e4 100644
--- a/payload_generator/filesystem_interface.h
+++ b/payload_generator/filesystem_interface.h
@@ -33,6 +33,7 @@
 
 #include <base/macros.h>
 #include <brillo/key_value_store.h>
+#include <puffin/utils.h>
 
 #include "update_engine/update_metadata.pb.h"
 
@@ -62,6 +63,10 @@
     // between 0 and GetBlockCount() - 1. The blocks are encoded in extents,
     // indicating the starting block, and the number of consecutive blocks.
     std::vector<Extent> extents;
+
+    // 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;
   };
 
   virtual ~FilesystemInterface() = default;
diff --git a/payload_generator/inplace_generator.cc b/payload_generator/inplace_generator.cc
index bc140e8..cf02c91 100644
--- a/payload_generator/inplace_generator.cc
+++ b/payload_generator/inplace_generator.cc
@@ -573,6 +573,8 @@
         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,
diff --git a/payload_generator/squashfs_filesystem.cc b/payload_generator/squashfs_filesystem.cc
index 54a2c1a..c98ad12 100644
--- a/payload_generator/squashfs_filesystem.cc
+++ b/payload_generator/squashfs_filesystem.cc
@@ -20,6 +20,7 @@
 
 #include <algorithm>
 #include <string>
+#include <utility>
 
 #include <base/files/file_util.h>
 #include <base/logging.h>
@@ -29,6 +30,7 @@
 
 #include "update_engine/common/subprocess.h"
 #include "update_engine/common/utils.h"
+#include "update_engine/payload_generator/deflate_utils.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"
@@ -53,6 +55,7 @@
 // The size of the squashfs super block.
 constexpr size_t kSquashfsSuperBlockSize = 96;
 constexpr uint64_t kSquashfsCompressedBit = 1 << 24;
+constexpr uint32_t kSquashfsZlibCompression = 1;
 
 bool ReadSquashfsHeader(const brillo::Blob blob,
                         SquashfsFilesystem::SquashfsHeader* header) {
@@ -96,9 +99,18 @@
 }  // namespace
 
 bool SquashfsFilesystem::Init(const string& map,
+                              const string& sqfs_path,
                               size_t size,
-                              const SquashfsHeader& header) {
+                              const SquashfsHeader& header,
+                              bool extract_deflates) {
   size_ = size;
+
+  bool is_zlib = header.compression_type == kSquashfsZlibCompression;
+  if (!is_zlib) {
+    LOG(WARNING) << "Filesystem is not Gzipped. Not filling deflates!";
+  }
+  vector<puffin::ByteExtent> zlib_blks;
+
   // Reading files map. For the format of the file map look at the comments for
   // |CreateFromFileMap()|.
   auto lines = base::SplitStringPiece(map,
@@ -122,6 +134,12 @@
       // TODO(ahassani): For puffin push it into a proper list if uncompressed.
       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
+        if (is_zlib && extract_deflates) {
+          zlib_blks.emplace_back(cur_offset, new_blk_size);
+        }
+      }
       cur_offset += new_blk_size;
     }
 
@@ -192,11 +210,45 @@
   std::sort(files_.begin(), files_.end(), [](const File& a, const File& b) {
     return a.extents[0].start_block() < b.extents[0].start_block();
   });
+
+  if (is_zlib && extract_deflates) {
+    // If it is infact gzipped, then the sqfs_path should be valid to read its
+    // content.
+    TEST_AND_RETURN_FALSE(!sqfs_path.empty());
+    if (zlib_blks.empty()) {
+      return true;
+    }
+
+    // Sort zlib blocks.
+    std::sort(zlib_blks.begin(),
+              zlib_blks.end(),
+              [](const puffin::ByteExtent& a, const puffin::ByteExtent& b) {
+                return a.offset < b.offset;
+              });
+
+    // Sanity check. Make sure zlib blocks are not overlapping.
+    auto result = std::adjacent_find(
+        zlib_blks.begin(),
+        zlib_blks.end(),
+        [](const puffin::ByteExtent& a, const puffin::ByteExtent& b) {
+          return (a.offset + a.length) > b.offset;
+        });
+    TEST_AND_RETURN_FALSE(result == zlib_blks.end());
+
+    vector<puffin::BitExtent> deflates;
+    TEST_AND_RETURN_FALSE(
+        puffin::LocateDeflatesInZlibBlocks(sqfs_path, zlib_blks, &deflates));
+
+    // Add deflates for each file.
+    for (auto& file : files_) {
+      file.deflates = deflate_utils::FindDeflates(file.extents, deflates);
+    }
+  }
   return true;
 }
 
 unique_ptr<SquashfsFilesystem> SquashfsFilesystem::CreateFromFile(
-    const string& sqfs_path) {
+    const string& sqfs_path, bool extract_deflates) {
   if (sqfs_path.empty())
     return nullptr;
 
@@ -229,11 +281,12 @@
   }
 
   unique_ptr<SquashfsFilesystem> sqfs(new SquashfsFilesystem());
-  if (!sqfs->Init(filemap, sqfs_file->GetSize(), header)) {
+  if (!sqfs->Init(
+          filemap, sqfs_path, sqfs_file->GetSize(), header, extract_deflates)) {
     LOG(ERROR) << "Failed to initialized the Squashfs file system";
     return nullptr;
   }
-  // TODO(ahassani): Add a function that initializes the puffin related extents.
+
   return sqfs;
 }
 
@@ -245,7 +298,7 @@
   }
 
   unique_ptr<SquashfsFilesystem> sqfs(new SquashfsFilesystem());
-  if (!sqfs->Init(filemap, size, header)) {
+  if (!sqfs->Init(filemap, "", size, header, false)) {
     LOG(ERROR) << "Failed to initialize the Squashfs file system using filemap";
     return nullptr;
   }
@@ -276,5 +329,4 @@
   SquashfsHeader header;
   return ReadSquashfsHeader(blob, &header) && CheckHeader(header);
 }
-
 }  // namespace chromeos_update_engine
diff --git a/payload_generator/squashfs_filesystem.h b/payload_generator/squashfs_filesystem.h
index aceebb8..b79f8c7 100644
--- a/payload_generator/squashfs_filesystem.h
+++ b/payload_generator/squashfs_filesystem.h
@@ -55,9 +55,11 @@
 
   ~SquashfsFilesystem() override = default;
 
-  // Creates the file system from the Squashfs file itself.
+  // Creates the file system from the Squashfs file itself. If
+  // |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);
+      const std::string& sqfs_path, bool extract_deflates);
 
   // Creates the file system from a file map |filemap| which is a multi-line
   // string with each line with the following format:
@@ -99,7 +101,11 @@
   SquashfsFilesystem() = default;
 
   // Initialize and populates the files in the file system.
-  bool Init(const std::string& map, size_t size, const SquashfsHeader& header);
+  bool Init(const std::string& map,
+            const std::string& sqfs_path,
+            size_t size,
+            const SquashfsHeader& header,
+            bool extract_deflates);
 
   // The size of the image in bytes.
   size_t size_;
diff --git a/payload_generator/squashfs_filesystem_unittest.cc b/payload_generator/squashfs_filesystem_unittest.cc
index 77f4ec9..13b4dd3 100644
--- a/payload_generator/squashfs_filesystem_unittest.cc
+++ b/payload_generator/squashfs_filesystem_unittest.cc
@@ -110,7 +110,7 @@
 
 TEST_F(SquashfsFilesystemTest, EmptyFilesystemTest) {
   unique_ptr<SquashfsFilesystem> fs = SquashfsFilesystem::CreateFromFile(
-      GetBuildArtifactsPath("gen/disk_sqfs_empty.img"));
+      GetBuildArtifactsPath("gen/disk_sqfs_empty.img"), true);
   CheckSquashfs(fs);
 
   // Even an empty squashfs filesystem is rounded up to 4K.
@@ -131,7 +131,7 @@
 
 TEST_F(SquashfsFilesystemTest, DefaultFilesystemTest) {
   unique_ptr<SquashfsFilesystem> fs = SquashfsFilesystem::CreateFromFile(
-      GetBuildArtifactsPath("gen/disk_sqfs_default.img"));
+      GetBuildArtifactsPath("gen/disk_sqfs_default.img"), true);
   CheckSquashfs(fs);
 
   vector<FilesystemInterface::File> files;
diff --git a/update_engine.gyp b/update_engine.gyp
index 6f0a140..9f68810 100644
--- a/update_engine.gyp
+++ b/update_engine.gyp
@@ -353,6 +353,7 @@
       'variables': {
         'exported_deps': [
           'ext2fs',
+          'libpuffdiff',
         ],
         'deps': ['<@(exported_deps)'],
       },