Add zucchini support in puffin am: 24d989fe3c

Original change: https://android-review.googlesource.com/c/platform/external/puffin/+/1777027

Change-Id: I915113e3659056e0e23a4960d993eeb6afb71c0d

7 files changed, 316 insertions, 88 deletions

diff --git a/Android.bp b/Android.bp
index f49c69b..decde42 100644
--- a/Android.bp
+++ b/Android.bp
@@ -61,6 +61,9 @@ cc_library_static {
     static_libs: [
         "libbspatch",
     ],
+    whole_static_libs: [
+        "libzucchini",
+    ],
     proto: {
         type: "lite",
         export_proto_headers: true,
@@ -78,6 +81,7 @@ cc_library_static {
     ],
     static_libs: [
         "libbsdiff",
+        "libzucchini",
         "libpuffpatch",
     ],
 }
@@ -95,6 +99,7 @@ cc_binary {
     static_libs: [
         "libbsdiff",
         "libbspatch",
+        "libzucchini",
         "libdivsufsort",
         "libdivsufsort64",
         "libpuffdiff",
@@ -110,6 +115,7 @@ cc_test {
     srcs: [
         "src/bit_io_unittest.cc",
         "src/extent_stream.cc",
+        "src/integration_test.cc",
         "src/patching_unittest.cc",
         "src/puff_io_unittest.cc",
         "src/puffin_unittest.cc",
@@ -124,6 +130,7 @@ cc_test {
     static_libs: [
         "libbsdiff",
         "libbspatch",
+        "libzucchini",
         "libdivsufsort",
         "libdivsufsort64",
         "libpuffdiff",
diff --git a/src/include/puffin/puffdiff.h b/src/include/puffin/puffdiff.h
index c8883bf..ad8a106 100644
--- a/src/include/puffin/puffdiff.h
+++ b/src/include/puffin/puffdiff.h
@@ -15,14 +15,22 @@
 
 namespace puffin {
 
+enum class PatchAlgorithm {
+  kBsdiff = 0,
+  kZucchini = 1,
+};
+
 // Performs a diff operation between input deflate streams and creates a patch
 // that is used in the client to recreate the |dst| from |src|.
 // |src|          IN   Source deflate stream.
 // |dst|          IN   Destination deflate stream.
 // |src_deflates| IN   Deflate locations in |src|.
 // |dst_deflates| IN   Deflate locations in |dst|.
-// |compressors|  IN   Compressors to use in the underlying bsdiff, e.g. bz2,
+// |compressors|  IN   Compressors to use in the underlying bsdiff, e.g.
+// bz2,
 //                     brotli.
+// |patchAlgorithm|    IN   The patchAlgorithm used to create patches between
+//                     uncompressed bytes, e.g. bsdiff, zucchini.
 // |tmp_filepath| IN   A path to a temporary file. The caller has the
 //                     responsibility of unlinking the file after the call to
 //                     |PuffDiff| finishes.
@@ -32,6 +40,16 @@ bool PuffDiff(UniqueStreamPtr src,
               const std::vector<BitExtent>& src_deflates,
               const std::vector<BitExtent>& dst_deflates,
               const std::vector<bsdiff::CompressorType>& compressors,
+              PatchAlgorithm patchAlgorithm,
+              const std::string& tmp_filepath,
+              Buffer* patch);
+
+// This function uses bsdiff as the patch algorithm.
+bool PuffDiff(UniqueStreamPtr src,
+              UniqueStreamPtr dst,
+              const std::vector<BitExtent>& src_deflates,
+              const std::vector<BitExtent>& dst_deflates,
+              const std::vector<bsdiff::CompressorType>& compressors,
               const std::string& tmp_filepath,
               Buffer* patch);
 
diff --git a/src/integration_test.cc b/src/integration_test.cc
new file mode 100644
index 0000000..d7cc59c
--- /dev/null
+++ b/src/integration_test.cc
@@ -0,0 +1,88 @@
+// Copyright 2021 The Chromium OS Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <string>
+#include <vector>
+
+#include "gtest/gtest.h"
+
+#include "puffin/src/include/puffin/puffdiff.h"
+#include "puffin/src/include/puffin/puffpatch.h"
+#include "puffin/src/include/puffin/utils.h"
+#include "puffin/src/memory_stream.h"
+#include "puffin/src/puffin_stream.h"
+#include "puffin/src/unittest_common.h"
+
+namespace puffin {
+
+namespace {
+// xxd -i <name>.zip
+const Buffer kTestZipA = {
+    0x50, 0x4b, 0x03, 0x04, 0x0a, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0e, 0x79,
+    0x0d, 0x53, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x01, 0x00, 0x1c, 0x00, 0x31, 0x55, 0x54, 0x09, 0x00, 0x03,
+    0x5c, 0xed, 0x16, 0x61, 0x5c, 0xed, 0x16, 0x61, 0x75, 0x78, 0x0b, 0x00,
+    0x01, 0x04, 0x8f, 0x66, 0x05, 0x00, 0x04, 0x53, 0x5f, 0x01, 0x00, 0x50,
+    0x4b, 0x01, 0x02, 0x1e, 0x03, 0x0a, 0x00, 0x00, 0x00, 0x00, 0x00, 0x0e,
+    0x79, 0x0d, 0x53, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x01, 0x00, 0x18, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0xa4, 0x81, 0x00, 0x00, 0x00, 0x00, 0x31, 0x55, 0x54,
+    0x05, 0x00, 0x03, 0x5c, 0xed, 0x16, 0x61, 0x75, 0x78, 0x0b, 0x00, 0x01,
+    0x04, 0x8f, 0x66, 0x05, 0x00, 0x04, 0x53, 0x5f, 0x01, 0x00, 0x50, 0x4b,
+    0x05, 0x06, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00, 0x01, 0x00, 0x47, 0x00,
+    0x00, 0x00, 0x3b, 0x00, 0x00, 0x00, 0x00, 0x00};
+
+const Buffer kTestZipB = {
+    0x50, 0x4b, 0x03, 0x04, 0x0a, 0x00, 0x00, 0x00, 0x00, 0x00, 0x26, 0x79,
+    0x0d, 0x53, 0x4e, 0x81, 0x88, 0x47, 0x04, 0x00, 0x00, 0x00, 0x04, 0x00,
+    0x00, 0x00, 0x01, 0x00, 0x1c, 0x00, 0x32, 0x55, 0x54, 0x09, 0x00, 0x03,
+    0x88, 0xed, 0x16, 0x61, 0x88, 0xed, 0x16, 0x61, 0x75, 0x78, 0x0b, 0x00,
+    0x01, 0x04, 0x8f, 0x66, 0x05, 0x00, 0x04, 0x53, 0x5f, 0x01, 0x00, 0x61,
+    0x62, 0x63, 0x0a, 0x50, 0x4b, 0x01, 0x02, 0x1e, 0x03, 0x0a, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x26, 0x79, 0x0d, 0x53, 0x4e, 0x81, 0x88, 0x47, 0x04,
+    0x00, 0x00, 0x00, 0x04, 0x00, 0x00, 0x00, 0x01, 0x00, 0x18, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0xa4, 0x81, 0x00, 0x00, 0x00,
+    0x00, 0x32, 0x55, 0x54, 0x05, 0x00, 0x03, 0x88, 0xed, 0x16, 0x61, 0x75,
+    0x78, 0x0b, 0x00, 0x01, 0x04, 0x8f, 0x66, 0x05, 0x00, 0x04, 0x53, 0x5f,
+    0x01, 0x00, 0x50, 0x4b, 0x05, 0x06, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00,
+    0x01, 0x00, 0x47, 0x00, 0x00, 0x00, 0x3f, 0x00, 0x00, 0x00, 0x00, 0x00};
+
+}  // namespace
+
+class PuffinIntegrationTest : public testing::TestWithParam<PatchAlgorithm> {
+ protected:
+  PatchAlgorithm getPatchType() { return GetParam(); }
+};
+
+TEST_P(PuffinIntegrationTest, PuffinDiffPatchTest) {
+  std::vector<BitExtent> src_deflates;
+  ASSERT_TRUE(LocateDeflatesInZipArchive(kTestZipA, &src_deflates));
+
+  std::vector<BitExtent> dst_deflates;
+  ASSERT_TRUE(LocateDeflatesInZipArchive(kTestZipB, &dst_deflates));
+
+  std::string tmp_file;
+  ASSERT_TRUE(MakeTempFile(&tmp_file, nullptr));
+  Buffer patch;
+  ASSERT_TRUE(PuffDiff(MemoryStream::CreateForRead(kTestZipA),
+                       MemoryStream::CreateForRead(kTestZipB), src_deflates,
+                       dst_deflates, {bsdiff::CompressorType::kBrotli},
+                       getPatchType(), tmp_file, &patch));
+
+  Buffer patched;
+  auto src_stream = MemoryStream::CreateForRead(kTestZipA);
+  auto dst_stream = MemoryStream::CreateForWrite(&patched);
+  ASSERT_TRUE(PuffPatch(MemoryStream::CreateForRead(kTestZipA),
+                        MemoryStream::CreateForWrite(&patched), patch.data(),
+                        patch.size()));
+
+  ASSERT_EQ(kTestZipB, patched);
+}
+
+INSTANTIATE_TEST_CASE_P(TestWithPatchType,
+                        PuffinIntegrationTest,
+                        testing::Values(PatchAlgorithm::kBsdiff,
+                                        PatchAlgorithm::kZucchini));
+
+}  // namespace puffin
\ No newline at end of file
diff --git a/src/main.cc b/src/main.cc
index 20f0948..5a5cc9b 100644
--- a/src/main.cc
+++ b/src/main.cc
@@ -154,44 +154,46 @@ bool LocateDeflatesBasedOnFileType(const UniqueStreamPtr& stream,
 
 }  // namespace
 
-#define SETUP_FLAGS                                                        \
-  DEFINE_string(src_file, "", "Source file");                              \
-  DEFINE_string(dst_file, "", "Target file");                              \
-  DEFINE_string(patch_file, "", "patch file");                             \
-  DEFINE_string(                                                           \
-      src_deflates_byte, "",                                               \
-      "Source deflate byte locations in the format offset:length,...");    \
-  DEFINE_string(                                                           \
-      dst_deflates_byte, "",                                               \
-      "Target deflate byte locations in the format offset:length,...");    \
-  DEFINE_string(                                                           \
-      src_deflates_bit, "",                                                \
-      "Source deflate bit locations in the format offset:length,...");     \
-  DEFINE_string(                                                           \
-      dst_deflates_bit, "",                                                \
-      "Target deflatebit locations in the format offset:length,...");      \
-  DEFINE_string(src_puffs, "",                                             \
-                "Source puff locations in the format offset:length,...");  \
-  DEFINE_string(dst_puffs, "",                                             \
-                "Target puff locations in the format offset:length,...");  \
-  DEFINE_string(src_extents, "",                                           \
-                "Source extents in the format of offset:length,...");      \
-  DEFINE_string(dst_extents, "",                                           \
-                "Target extents in the format of offset:length,...");      \
-  DEFINE_string(operation, "",                                             \
-                "Type of the operation: puff, huff, puffdiff, puffpatch, " \
-                "puffhuff");                                               \
-  DEFINE_string(src_file_type, "",                                         \
-                "Type of the input source file: deflate, gzip, "           \
-                "zlib or zip");                                            \
-  DEFINE_string(dst_file_type, "",                                         \
-                "Same as src_file_type but for the target file");          \
-  DEFINE_bool(verbose, false,                                              \
-              "Logs all the given parameters including internally "        \
-              "generated ones");                                           \
-  DEFINE_uint64(cache_size, kDefaultPuffCacheSize,                         \
-                "Maximum size to cache the puff stream. Used in puffpatch");
-
+#define SETUP_FLAGS                                                          \
+  DEFINE_string(src_file, "", "Source file");                                \
+  DEFINE_string(dst_file, "", "Target file");                                \
+  DEFINE_string(patch_file, "", "patch file");                               \
+  DEFINE_string(                                                             \
+      src_deflates_byte, "",                                                 \
+      "Source deflate byte locations in the format offset:length,...");      \
+  DEFINE_string(                                                             \
+      dst_deflates_byte, "",                                                 \
+      "Target deflate byte locations in the format offset:length,...");      \
+  DEFINE_string(                                                             \
+      src_deflates_bit, "",                                                  \
+      "Source deflate bit locations in the format offset:length,...");       \
+  DEFINE_string(                                                             \
+      dst_deflates_bit, "",                                                  \
+      "Target deflatebit locations in the format offset:length,...");        \
+  DEFINE_string(src_puffs, "",                                               \
+                "Source puff locations in the format offset:length,...");    \
+  DEFINE_string(dst_puffs, "",                                               \
+                "Target puff locations in the format offset:length,...");    \
+  DEFINE_string(src_extents, "",                                             \
+                "Source extents in the format of offset:length,...");        \
+  DEFINE_string(dst_extents, "",                                             \
+                "Target extents in the format of offset:length,...");        \
+  DEFINE_string(operation, "",                                               \
+                "Type of the operation: puff, huff, puffdiff, puffpatch, "   \
+                "puffhuff");                                                 \
+  DEFINE_string(src_file_type, "",                                           \
+                "Type of the input source file: deflate, gzip, "             \
+                "zlib or zip");                                              \
+  DEFINE_string(dst_file_type, "",                                           \
+                "Same as src_file_type but for the target file");            \
+  DEFINE_bool(verbose, false,                                                \
+              "Logs all the given parameters including internally "          \
+              "generated ones");                                             \
+  DEFINE_uint64(cache_size, kDefaultPuffCacheSize,                           \
+                "Maximum size to cache the puff stream. Used in puffpatch"); \
+  DEFINE_int32(patch_algorithm, 0,                                           \
+               "Type of raw diff algorithm to use. The current supported "   \
+               "ones are 0: bsdiff, 1: zucchini.");
 #ifndef USE_BRILLO
 SETUP_FLAGS;
 #endif
@@ -343,12 +345,18 @@ bool Main(int argc, char** argv) {
                                                  &dst_deflates_bit));
     }
 
+    if (FLAGS_patch_algorithm != 0 && FLAGS_patch_algorithm != 1) {
+      LOG(ERROR)
+          << "The supported patch algorithms are 0: bsdiff, 1: zucchini.";
+      return false;
+    }
     // TODO(xunchang) add flags to select the bsdiff compressors.
     Buffer puffdiff_delta;
     TEST_AND_RETURN_FALSE(puffin::PuffDiff(
         std::move(src_stream), std::move(dst_stream), src_deflates_bit,
         dst_deflates_bit,
         {bsdiff::CompressorType::kBZ2, bsdiff::CompressorType::kBrotli},
+        static_cast<puffin::PatchAlgorithm>(FLAGS_patch_algorithm),
         "/tmp/patch.tmp", &puffdiff_delta));
     if (FLAGS_verbose) {
       LOG(INFO) << "patch_size: " << puffdiff_delta.size();
diff --git a/src/puffdiff.cc b/src/puffdiff.cc
index 15d0fa6..6d9bc27 100644
--- a/src/puffdiff.cc
+++ b/src/puffdiff.cc
@@ -13,6 +13,9 @@
 
 #include "bsdiff/bsdiff.h"
 #include "bsdiff/patch_writer_factory.h"
+#include "zucchini/buffer_view.h"
+#include "zucchini/patch_writer.h"
+#include "zucchini/zucchini.h"
 
 #include "puffin/src/file_stream.h"
 #include "puffin/src/include/puffin/common.h"
@@ -47,15 +50,16 @@ void CopyVectorToRpf(
 
 // Structure of a puffin patch
 // +-------+------------------+-------------+--------------+
-// |P|U|F|1| PatchHeader Size | PatchHeader | bsdiff_patch |
+// |P|U|F|1| PatchHeader Size | PatchHeader | raw patch |
 // +-------+------------------+-------------+--------------+
-bool CreatePatch(const Buffer& bsdiff_patch,
+bool CreatePatch(const Buffer& raw_patch,
                  const vector<BitExtent>& src_deflates,
                  const vector<BitExtent>& dst_deflates,
                  const vector<ByteExtent>& src_puffs,
                  const vector<ByteExtent>& dst_puffs,
                  uint64_t src_puff_size,
                  uint64_t dst_puff_size,
+                 PatchAlgorithm patchAlgorithm,
                  Buffer* patch) {
   metadata::PatchHeader header;
   header.set_version(1);
@@ -67,6 +71,7 @@ bool CreatePatch(const Buffer& bsdiff_patch,
 
   header.mutable_src()->set_puff_length(src_puff_size);
   header.mutable_dst()->set_puff_length(dst_puff_size);
+  header.set_type(static_cast<metadata::PatchHeader_PatchType>(patchAlgorithm));
 
   const size_t header_size_long = header.ByteSizeLong();
   TEST_AND_RETURN_FALSE(header_size_long <= UINT32_MAX);
@@ -74,7 +79,7 @@ bool CreatePatch(const Buffer& bsdiff_patch,
 
   uint64_t offset = 0;
   patch->resize(kMagicLength + sizeof(header_size) + header_size +
-                bsdiff_patch.size());
+                raw_patch.size());
 
   memcpy(patch->data() + offset, kMagic, kMagicLength);
   offset += kMagicLength;
@@ -88,9 +93,9 @@ bool CreatePatch(const Buffer& bsdiff_patch,
       header.SerializeToArray(patch->data() + offset, header_size));
   offset += header_size;
 
-  memcpy(patch->data() + offset, bsdiff_patch.data(), bsdiff_patch.size());
+  memcpy(patch->data() + offset, raw_patch.data(), raw_patch.size());
 
-  if (bsdiff_patch.size() > patch->size()) {
+  if (raw_patch.size() > patch->size()) {
     LOG(ERROR) << "Puffin patch is invalid";
   }
   return true;
@@ -103,6 +108,7 @@ bool PuffDiff(UniqueStreamPtr src,
               const vector<BitExtent>& src_deflates,
               const vector<BitExtent>& dst_deflates,
               const vector<bsdiff::CompressorType>& compressors,
+              PatchAlgorithm patchAlgorithm,
               const string& tmp_filepath,
               Buffer* patch) {
   auto puffer = std::make_shared<Puffer>();
@@ -130,29 +136,63 @@ bool PuffDiff(UniqueStreamPtr src,
   TEST_AND_RETURN_FALSE(puff_deflate_stream(std::move(dst), dst_deflates,
                                             &dst_puff_buffer, &dst_puffs));
 
-  auto bsdiff_patch_writer = bsdiff::CreateBSDF2PatchWriter(
-      tmp_filepath, compressors, kBrotliCompressionQuality);
-
-  TEST_AND_RETURN_FALSE(
-      0 == bsdiff::bsdiff(src_puff_buffer.data(), src_puff_buffer.size(),
-                          dst_puff_buffer.data(), dst_puff_buffer.size(),
-                          bsdiff_patch_writer.get(), nullptr));
-
-  auto bsdiff_patch = FileStream::Open(tmp_filepath, true, false);
-  TEST_AND_RETURN_FALSE(bsdiff_patch);
-  uint64_t patch_size;
-  TEST_AND_RETURN_FALSE(bsdiff_patch->GetSize(&patch_size));
-  Buffer bsdiff_patch_buf(patch_size);
-  TEST_AND_RETURN_FALSE(
-      bsdiff_patch->Read(bsdiff_patch_buf.data(), bsdiff_patch_buf.size()));
-  TEST_AND_RETURN_FALSE(bsdiff_patch->Close());
+  if (patchAlgorithm == PatchAlgorithm::kBsdiff) {
+    auto bsdiff_patch_writer = bsdiff::CreateBSDF2PatchWriter(
+        tmp_filepath, compressors, kBrotliCompressionQuality);
+
+    TEST_AND_RETURN_FALSE(
+        0 == bsdiff::bsdiff(src_puff_buffer.data(), src_puff_buffer.size(),
+                            dst_puff_buffer.data(), dst_puff_buffer.size(),
+                            bsdiff_patch_writer.get(), nullptr));
+
+    auto bsdiff_patch = FileStream::Open(tmp_filepath, true, false);
+    TEST_AND_RETURN_FALSE(bsdiff_patch);
+    uint64_t patch_size;
+    TEST_AND_RETURN_FALSE(bsdiff_patch->GetSize(&patch_size));
+    Buffer bsdiff_patch_buf(patch_size);
+    TEST_AND_RETURN_FALSE(
+        bsdiff_patch->Read(bsdiff_patch_buf.data(), bsdiff_patch_buf.size()));
+    TEST_AND_RETURN_FALSE(bsdiff_patch->Close());
+
+    TEST_AND_RETURN_FALSE(CreatePatch(
+        bsdiff_patch_buf, src_deflates, dst_deflates, src_puffs, dst_puffs,
+        src_puff_buffer.size(), dst_puff_buffer.size(), patchAlgorithm, patch));
+  } else if (patchAlgorithm == PatchAlgorithm::kZucchini) {
+    zucchini::ConstBufferView src_bytes(src_puff_buffer.data(),
+                                        src_puff_buffer.size());
+    zucchini::ConstBufferView dst_bytes(dst_puff_buffer.data(),
+                                        dst_puff_buffer.size());
+
+    zucchini::EnsemblePatchWriter patch_writer(src_bytes, dst_bytes);
+    auto status = zucchini::GenerateBuffer(src_bytes, dst_bytes, &patch_writer);
+    CHECK_EQ(zucchini::status::kStatusSuccess, status);
+
+    Buffer zucchini_patch_buf(patch_writer.SerializedSize());
+    patch_writer.SerializeInto(
+        {zucchini_patch_buf.data(), zucchini_patch_buf.size()});
+
+    TEST_AND_RETURN_FALSE(CreatePatch(
+        zucchini_patch_buf, src_deflates, dst_deflates, src_puffs, dst_puffs,
+        src_puff_buffer.size(), dst_puff_buffer.size(), patchAlgorithm, patch));
+  } else {
+    LOG(ERROR) << "unsupported type " << static_cast<int>(patchAlgorithm);
+    return false;
+  }
 
-  TEST_AND_RETURN_FALSE(CreatePatch(
-      bsdiff_patch_buf, src_deflates, dst_deflates, src_puffs, dst_puffs,
-      src_puff_buffer.size(), dst_puff_buffer.size(), patch));
   return true;
 }
 
+bool PuffDiff(UniqueStreamPtr src,
+              UniqueStreamPtr dst,
+              const std::vector<BitExtent>& src_deflates,
+              const std::vector<BitExtent>& dst_deflates,
+              const std::vector<bsdiff::CompressorType>& compressors,
+              const std::string& tmp_filepath,
+              Buffer* patch) {
+  return PuffDiff(std::move(src), std::move(dst), src_deflates, dst_deflates,
+                  compressors, PatchAlgorithm::kBsdiff, tmp_filepath, patch);
+}
+
 bool PuffDiff(const Buffer& src,
               const Buffer& dst,
               const vector<BitExtent>& src_deflates,
@@ -162,7 +202,7 @@ bool PuffDiff(const Buffer& src,
               Buffer* patch) {
   return PuffDiff(MemoryStream::CreateForRead(src),
                   MemoryStream::CreateForRead(dst), src_deflates, dst_deflates,
-                  compressors, tmp_filepath, patch);
+                  compressors, PatchAlgorithm::kBsdiff, tmp_filepath, patch);
 }
 
 bool PuffDiff(const Buffer& src,
diff --git a/src/puffin.proto b/src/puffin.proto
index 7651bc0..7ed5bc7 100644
--- a/src/puffin.proto
+++ b/src/puffin.proto
@@ -19,8 +19,15 @@ message StreamInfo {
 }
 
 message PatchHeader {
+  enum PatchType {
+    BSDIFF = 0;
+    ZUCCHINI = 1;
+  }
+
   int32 version = 1;
   StreamInfo src = 2;
   StreamInfo dst = 3;
   // The bsdiff patch is installed right after this protobuf.
+
+  PatchType type = 4;
 }
\ No newline at end of file
diff --git a/src/puffpatch.cc b/src/puffpatch.cc
index 0b4ffcb..09bfb98 100644
--- a/src/puffpatch.cc
+++ b/src/puffpatch.cc
@@ -14,6 +14,8 @@
 
 #include "bsdiff/bspatch.h"
 #include "bsdiff/file_interface.h"
+#include "zucchini/patch_reader.h"
+#include "zucchini/zucchini.h"
 
 #include "puffin/src/include/puffin/common.h"
 #include "puffin/src/include/puffin/huffer.h"
@@ -92,8 +94,6 @@ class BsdiffStream : public bsdiff::FileInterface {
   DISALLOW_COPY_AND_ASSIGN(BsdiffStream);
 };
 
-}  // namespace
-
 bool DecodePatch(const uint8_t* patch,
                  size_t patch_length,
                  size_t* bsdiff_patch_offset,
@@ -103,7 +103,8 @@ bool DecodePatch(const uint8_t* patch,
                  vector<ByteExtent>* src_puffs,
                  vector<ByteExtent>* dst_puffs,
                  uint64_t* src_puff_size,
-                 uint64_t* dst_puff_size) {
+                 uint64_t* dst_puff_size,
+                 metadata::PatchHeader_PatchType* patch_type) {
   size_t offset = 0;
   uint32_t header_size;
   TEST_AND_RETURN_FALSE(patch_length >= (kMagicLength + sizeof(header_size)));
@@ -135,43 +136,102 @@ bool DecodePatch(const uint8_t* patch,
 
   *bsdiff_patch_offset = offset;
   *bsdiff_patch_size = patch_length - offset;
+
+  *patch_type = header.type();
+  return true;
+}
+
+bool ApplyZucchiniPatch(UniqueStreamPtr src_stream,
+                        size_t src_size,
+                        const uint8_t* patch_start,
+                        size_t patch_size,
+                        UniqueStreamPtr dst_stream) {
+  // Read the source data
+  Buffer puffed_src(src_size);
+  Buffer buffer(1024 * 1024);
+  uint64_t bytes_wrote = 0;
+  while (bytes_wrote < src_size) {
+    auto write_size =
+        std::min(static_cast<uint64_t>(buffer.size()), src_size - bytes_wrote);
+    TEST_AND_RETURN_FALSE(src_stream->Read(buffer.data(), write_size));
+    std::copy(buffer.data(), buffer.data() + write_size,
+              puffed_src.data() + bytes_wrote);
+    bytes_wrote += write_size;
+  }
+  // Read the patch
+  auto patch_reader =
+      zucchini::EnsemblePatchReader::Create({patch_start, patch_size});
+  if (!patch_reader.has_value()) {
+    LOG(ERROR) << "Failed to parse the zucchini patch.";
+    return false;
+  }
+
+  // TODO(197361113) Stream the patched result once zucchini supports it. So we
+  // can save some memory when applying patch on device.
+  Buffer patched_data(patch_reader->header().new_size);
+  auto status = zucchini::ApplyBuffer(
+      {puffed_src.data(), puffed_src.size()}, *patch_reader,
+      {patched_data.data(), patched_data.size()});
+  if (status != zucchini::status::kStatusSuccess) {
+    LOG(ERROR) << "Failed to parse the zucchini patch: " << status;
+    return false;
+  }
+
+  TEST_AND_RETURN_FALSE(
+      dst_stream->Write(patched_data.data(), patched_data.size()));
   return true;
 }
 
+}  // namespace
+
 bool PuffPatch(UniqueStreamPtr src,
                UniqueStreamPtr dst,
                const uint8_t* patch,
                size_t patch_length,
                size_t max_cache_size) {
-  size_t bsdiff_patch_offset;  // bsdiff offset in |patch|.
-  size_t bsdiff_patch_size = 0;
+  size_t patch_offset;  // raw patch offset in puffin |patch|.
+  size_t raw_patch_size = 0;
   vector<BitExtent> src_deflates, dst_deflates;
   vector<ByteExtent> src_puffs, dst_puffs;
   uint64_t src_puff_size, dst_puff_size;
 
-  // Decode the patch and get the bsdiff_patch.
-  TEST_AND_RETURN_FALSE(DecodePatch(patch, patch_length, &bsdiff_patch_offset,
-                                    &bsdiff_patch_size, &src_deflates,
-                                    &dst_deflates, &src_puffs, &dst_puffs,
-                                    &src_puff_size, &dst_puff_size));
+  metadata::PatchHeader_PatchType patch_type;
+
+  // Decode the patch and get the raw patch (e.g. bsdiff, zucchini).
+  TEST_AND_RETURN_FALSE(
+      DecodePatch(patch, patch_length, &patch_offset, &raw_patch_size,
+                  &src_deflates, &dst_deflates, &src_puffs, &dst_puffs,
+                  &src_puff_size, &dst_puff_size, &patch_type));
   auto puffer = std::make_shared<Puffer>();
   auto huffer = std::make_shared<Huffer>();
 
-  // For reading from source.
-  auto reader = BsdiffStream::Create(
+  auto src_stream =
       PuffinStream::CreateForPuff(std::move(src), puffer, src_puff_size,
-                                  src_deflates, src_puffs, max_cache_size));
-  TEST_AND_RETURN_FALSE(reader);
-
-  // For writing into destination.
-  auto writer = BsdiffStream::Create(PuffinStream::CreateForHuff(
-      std::move(dst), huffer, dst_puff_size, dst_deflates, dst_puffs));
-  TEST_AND_RETURN_FALSE(writer);
-
-  // Running bspatch itself.
-  TEST_AND_RETURN_FALSE(0 == bspatch(reader, writer,
-                                     &patch[bsdiff_patch_offset],
-                                     bsdiff_patch_size));
+                                  src_deflates, src_puffs, max_cache_size);
+  TEST_AND_RETURN_FALSE(src_stream);
+  auto dst_stream = PuffinStream::CreateForHuff(
+      std::move(dst), huffer, dst_puff_size, dst_deflates, dst_puffs);
+  TEST_AND_RETURN_FALSE(dst_stream);
+
+  if (patch_type == metadata::PatchHeader_PatchType_BSDIFF) {
+    // For reading from source.
+    auto reader = BsdiffStream::Create(std::move(src_stream));
+    TEST_AND_RETURN_FALSE(reader);
+    // For writing into destination.
+    auto writer = BsdiffStream::Create(std::move(dst_stream));
+    TEST_AND_RETURN_FALSE(writer);
+
+    // Running bspatch itself.
+    TEST_AND_RETURN_FALSE(
+        0 == bspatch(reader, writer, &patch[patch_offset], raw_patch_size));
+  } else if (patch_type == metadata::PatchHeader_PatchType_ZUCCHINI) {
+    TEST_AND_RETURN_FALSE(ApplyZucchiniPatch(
+        std::move(src_stream), src_puff_size, patch + patch_offset,
+        raw_patch_size, std::move(dst_stream)));
+  } else {
+    LOG(ERROR) << "Unsupported patch type " << patch_type;
+    return false;
+  }
   return true;
 }