diff --git a/payload_consumer/payload_constants.cc b/payload_consumer/payload_constants.cc
index e47b4f8..3d78e0a 100644
--- a/payload_consumer/payload_constants.cc
+++ b/payload_consumer/payload_constants.cc
@@ -25,6 +25,7 @@
 const uint32_t kInPlaceMinorPayloadVersion = 1;
 const uint32_t kSourceMinorPayloadVersion = 2;
 const uint32_t kOpSrcHashMinorPayloadVersion = 3;
+const uint32_t kImgdiffMinorPayloadVersion = 4;
 
 const char kLegacyPartitionNameKernel[] = "boot";
 const char kLegacyPartitionNameRoot[] = "system";
diff --git a/payload_consumer/payload_constants.h b/payload_consumer/payload_constants.h
index c3cd363..76d740f 100644
--- a/payload_consumer/payload_constants.h
+++ b/payload_consumer/payload_constants.h
@@ -43,6 +43,9 @@
 // The minor version that allows per-operation source hash.
 extern const uint32_t kOpSrcHashMinorPayloadVersion;
 
+// The minor version that allows IMGDIFF operation.
+extern const uint32_t kImgdiffMinorPayloadVersion;
+
 
 // The kernel and rootfs partition names used by the BootControlInterface when
 // handling update payloads with a major version 1. The names of the updated
diff --git a/payload_generator/ab_generator.cc b/payload_generator/ab_generator.cc
index 7caf897..740659b 100644
--- a/payload_generator/ab_generator.cc
+++ b/payload_generator/ab_generator.cc
@@ -53,6 +53,7 @@
       hard_chunk_blocks,
       soft_chunk_blocks,
       blob_file,
+      config.imgdiff_allowed,
       true));  // src_ops_allowed
   LOG(INFO) << "done reading " << new_part.name;
 
@@ -74,7 +75,7 @@
                                         new_part.path,
                                         blob_file));
 
-  if (config.minor_version == kOpSrcHashMinorPayloadVersion)
+  if (config.minor_version >= kOpSrcHashMinorPayloadVersion)
     TEST_AND_RETURN_FALSE(AddSourceHash(aops, old_part.path));
 
   return true;
diff --git a/payload_generator/delta_diff_generator.cc b/payload_generator/delta_diff_generator.cc
index ffe0fe9..6143334 100644
--- a/payload_generator/delta_diff_generator.cc
+++ b/payload_generator/delta_diff_generator.cc
@@ -105,7 +105,8 @@
           LOG(INFO) << "Using generator InplaceGenerator().";
           strategy.reset(new InplaceGenerator());
         } else if (config.minor_version == kSourceMinorPayloadVersion ||
-                   config.minor_version == kOpSrcHashMinorPayloadVersion) {
+                   config.minor_version == kOpSrcHashMinorPayloadVersion ||
+                   config.minor_version == kImgdiffMinorPayloadVersion) {
           LOG(INFO) << "Using generator ABGenerator().";
           strategy.reset(new ABGenerator());
         } else {
diff --git a/payload_generator/delta_diff_utils.cc b/payload_generator/delta_diff_utils.cc
index ba1aac4..88567b2 100644
--- a/payload_generator/delta_diff_utils.cc
+++ b/payload_generator/delta_diff_utils.cc
@@ -40,6 +40,7 @@
 namespace {
 
 const char* const kBsdiffPath = "bsdiff";
+const char* const kImgdiffPath = "imgdiff";
 
 // The maximum destination size allowed for bsdiff. In general, bsdiff should
 // work for arbitrary big files, but the payload generation and payload
@@ -146,6 +147,15 @@
   return removed_bytes;
 }
 
+// Returns true if the given blob |data| contains gzip header magic.
+bool ContainsGZip(const brillo::Blob& data) {
+  const uint8_t kGZipMagic[] = {0x1f, 0x8b, 0x08, 0x00};
+  return std::search(data.begin(),
+                     data.end(),
+                     std::begin(kGZipMagic),
+                     std::end(kGZipMagic)) != data.end();
+}
+
 }  // namespace
 
 namespace diff_utils {
@@ -157,6 +167,7 @@
     ssize_t hard_chunk_blocks,
     size_t soft_chunk_blocks,
     BlobFileWriter* blob_file,
+    bool imgdiff_allowed,
     bool src_ops_allowed) {
   ExtentRanges old_visited_blocks;
   ExtentRanges new_visited_blocks;
@@ -228,6 +239,7 @@
         new_file.name,  // operation name
         hard_chunk_blocks,
         blob_file,
+        imgdiff_allowed,
         src_ops_allowed));
   }
   // Process all the blocks not included in any file. We provided all the unused
@@ -259,6 +271,7 @@
       "<non-file-data>",  // operation name
       soft_chunk_blocks,
       blob_file,
+      imgdiff_allowed,
       src_ops_allowed));
 
   return true;
@@ -356,6 +369,7 @@
         "<zeros>",
         chunk_blocks,
         blob_file,
+        false,  // imgdiff_allowed
         src_ops_allowed));
   }
   LOG(INFO) << "Produced " << (aops->size() - num_ops) << " operations for "
@@ -416,6 +430,7 @@
     const string& name,
     ssize_t chunk_blocks,
     BlobFileWriter* blob_file,
+    bool imgdiff_allowed,
     bool src_ops_allowed) {
   brillo::Blob data;
   InstallOperation operation;
@@ -432,6 +447,7 @@
   if (static_cast<uint64_t>(chunk_blocks) * kBlockSize >
       kMaxBsdiffDestinationSize) {
     bsdiff_allowed = false;
+    imgdiff_allowed = false;
   }
 
   if (!bsdiff_allowed) {
@@ -456,6 +472,7 @@
                                             old_extents_chunk,
                                             new_extents_chunk,
                                             bsdiff_allowed,
+                                            imgdiff_allowed,
                                             &data,
                                             &operation,
                                             src_ops_allowed));
@@ -498,6 +515,7 @@
                        const vector<Extent>& old_extents,
                        const vector<Extent>& new_extents,
                        bool bsdiff_allowed,
+                       bool imgdiff_allowed,
                        brillo::Blob* out_data,
                        InstallOperation* out_op,
                        bool src_ops_allowed) {
@@ -540,6 +558,7 @@
   brillo::Blob old_data;
   brillo::Blob empty_blob;
   brillo::Blob bsdiff_delta;
+  brillo::Blob imgdiff_delta;
   if (blocks_to_read > 0) {
     // Read old data.
     TEST_AND_RETURN_FALSE(
@@ -553,32 +572,51 @@
         operation.set_type(InstallOperation::MOVE);
       }
       data_blob = &empty_blob;
-    } else if (bsdiff_allowed) {
+    } else if (bsdiff_allowed || imgdiff_allowed) {
       // If the source file is considered bsdiff safe (no bsdiff bugs
       // triggered), see if BSDIFF encoding is smaller.
       base::FilePath old_chunk;
       TEST_AND_RETURN_FALSE(base::CreateTemporaryFile(&old_chunk));
       ScopedPathUnlinker old_unlinker(old_chunk.value());
-      TEST_AND_RETURN_FALSE(
-          utils::WriteFile(old_chunk.value().c_str(),
-                           old_data.data(), old_data.size()));
+      TEST_AND_RETURN_FALSE(utils::WriteFile(
+          old_chunk.value().c_str(), old_data.data(), old_data.size()));
       base::FilePath new_chunk;
       TEST_AND_RETURN_FALSE(base::CreateTemporaryFile(&new_chunk));
       ScopedPathUnlinker new_unlinker(new_chunk.value());
-      TEST_AND_RETURN_FALSE(
-          utils::WriteFile(new_chunk.value().c_str(),
-                           new_data.data(), new_data.size()));
+      TEST_AND_RETURN_FALSE(utils::WriteFile(
+          new_chunk.value().c_str(), new_data.data(), new_data.size()));
 
-      TEST_AND_RETURN_FALSE(
-          BsdiffFiles(old_chunk.value(), new_chunk.value(), &bsdiff_delta));
-      CHECK_GT(bsdiff_delta.size(), static_cast<brillo::Blob::size_type>(0));
-      if (bsdiff_delta.size() < data_blob->size()) {
-        if (src_ops_allowed) {
-          operation.set_type(InstallOperation::SOURCE_BSDIFF);
-        } else {
-          operation.set_type(InstallOperation::BSDIFF);
+      if (bsdiff_allowed) {
+        TEST_AND_RETURN_FALSE(DiffFiles(
+            kBsdiffPath, old_chunk.value(), new_chunk.value(), &bsdiff_delta));
+        CHECK_GT(bsdiff_delta.size(), static_cast<brillo::Blob::size_type>(0));
+        if (bsdiff_delta.size() < data_blob->size()) {
+          if (src_ops_allowed) {
+            operation.set_type(InstallOperation::SOURCE_BSDIFF);
+          } else {
+            operation.set_type(InstallOperation::BSDIFF);
+          }
+          data_blob = &bsdiff_delta;
         }
-        data_blob = &bsdiff_delta;
+      }
+      if (imgdiff_allowed && ContainsGZip(old_data) && ContainsGZip(new_data)) {
+        // Imgdiff might fail in some cases, only use the result if it succeed,
+        // otherwise print the extents to analyze.
+        if (DiffFiles(kImgdiffPath,
+                      old_chunk.value(),
+                      new_chunk.value(),
+                      &imgdiff_delta) &&
+            imgdiff_delta.size() > 0) {
+          if (imgdiff_delta.size() < data_blob->size()) {
+            operation.set_type(InstallOperation::IMGDIFF);
+            data_blob = &imgdiff_delta;
+          }
+        } else {
+          LOG(ERROR) << "Imgdiff failed with source extents: "
+                     << ExtentsToString(src_extents)
+                     << ", destination extents: "
+                     << ExtentsToString(dst_extents);
+        }
       }
     }
   }
@@ -610,11 +648,12 @@
   return true;
 }
 
-// Runs the bsdiff tool on two files and returns the resulting delta in
-// 'out'. Returns true on success.
-bool BsdiffFiles(const string& old_file,
-                 const string& new_file,
-                 brillo::Blob* out) {
+// Runs the bsdiff or imgdiff tool in |diff_path| on two files and returns the
+// resulting delta in |out|. Returns true on success.
+bool DiffFiles(const string& diff_path,
+               const string& old_file,
+               const string& new_file,
+               brillo::Blob* out) {
   const string kPatchFile = "delta.patchXXXXXX";
   string patch_file_path;
 
@@ -622,15 +661,19 @@
       utils::MakeTempFile(kPatchFile, &patch_file_path, nullptr));
 
   vector<string> cmd;
-  cmd.push_back(kBsdiffPath);
+  cmd.push_back(diff_path);
   cmd.push_back(old_file);
   cmd.push_back(new_file);
   cmd.push_back(patch_file_path);
 
   int rc = 1;
   brillo::Blob patch_file;
-  TEST_AND_RETURN_FALSE(Subprocess::SynchronousExec(cmd, &rc, nullptr));
-  TEST_AND_RETURN_FALSE(rc == 0);
+  string stdout;
+  TEST_AND_RETURN_FALSE(Subprocess::SynchronousExec(cmd, &rc, &stdout));
+  if (rc != 0) {
+    LOG(ERROR) << diff_path << " returned " << rc << std::endl << stdout;
+    return false;
+  }
   TEST_AND_RETURN_FALSE(utils::ReadFile(patch_file_path, out));
   unlink(patch_file_path.c_str());
   return true;
diff --git a/payload_generator/delta_diff_utils.h b/payload_generator/delta_diff_utils.h
index 5ba9bc7..8a02358 100644
--- a/payload_generator/delta_diff_utils.h
+++ b/payload_generator/delta_diff_utils.h
@@ -36,18 +36,18 @@
 // It uses the files reported by the filesystem in |old_part| and the data
 // blocks in that partition (if available) to determine the best way to compress
 // the new files (REPLACE, REPLACE_BZ, COPY, BSDIFF) and writes any necessary
-// data to the end of |data_fd| updating |data_file_size| accordingly.
-// |hard_chunk_blocks| and |soft_chunk_blocks| are the hard and soft chunk
-// limits in number of blocks respectively. The soft chunk limit is used to
-// split MOVE and SOURCE_COPY operations and REPLACE_BZ of zeroed blocks, while
-// the hard limit is used to split a file when generating other operations. A
-// value of -1 in |hard_chunk_blocks| means whole files.
+// data to |blob_file|. |hard_chunk_blocks| and |soft_chunk_blocks| are the hard
+// and soft chunk limits in number of blocks respectively. The soft chunk limit
+// is used to split MOVE and SOURCE_COPY operations and REPLACE_BZ of zeroed
+// blocks, while the hard limit is used to split a file when generating other
+// operations. A value of -1 in |hard_chunk_blocks| means whole files.
 bool DeltaReadPartition(std::vector<AnnotatedOperation>* aops,
                         const PartitionConfig& old_part,
                         const PartitionConfig& new_part,
                         ssize_t hard_chunk_blocks,
                         size_t soft_chunk_blocks,
                         BlobFileWriter* blob_file,
+                        bool imgdiff_allowed,
                         bool src_ops_allowed);
 
 // Create operations in |aops| for identical blocks that moved around in the old
@@ -55,8 +55,7 @@
 // are stored in the |old_part| and |new_part| files and have |old_num_blocks|
 // and |new_num_blocks| respectively. The maximum operation size is
 // |chunk_blocks| blocks, or unlimited if |chunk_blocks| is -1. The blobs of the
-// produced operations are stored in the |data_fd| file whose size is updated
-// in the value pointed by |data_file_size|.
+// produced operations are stored in the |blob_file|.
 // The collections |old_visited_blocks| and |new_visited_blocks| state what
 // blocks already have operations reading or writing them and only operations
 // for unvisited blocks are produced by this function updating both collections
@@ -78,8 +77,7 @@
 // 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 file |data_fd|, which has length *data_file_size. *data_file_size is
-// updated appropriately. Returns true on success.
+// in the |blob_file|. Returns true on success.
 bool DeltaReadFile(std::vector<AnnotatedOperation>* aops,
                    const std::string& old_part,
                    const std::string& new_part,
@@ -88,6 +86,7 @@
                    const std::string& name,
                    ssize_t chunk_blocks,
                    BlobFileWriter* blob_file,
+                   bool imgdiff_allowed,
                    bool src_ops_allowed);
 
 // Reads the blocks |old_extents| from |old_part| (if it exists) and the
@@ -95,7 +94,8 @@
 // this |new_extents| for the diff. It stores necessary data in |out_data| and
 // fills in |out_op|. If there's no change in old and new files, it creates a
 // MOVE operation. If there is a change, the smallest of REPLACE, REPLACE_BZ,
-// or BSDIFF wins. |new_extents| must not be empty.
+// BSDIFF (if |bsdiff_allowed|) or IMGDIFF (if |imgdiff_allowed|) wins.
+// |new_extents| must not be empty.
 // If |src_ops_allowed| is true, it will emit SOURCE_COPY and SOURCE_BSDIFF
 // operations instead of MOVE and BSDIFF, respectively.
 // Returns true on success.
@@ -104,15 +104,17 @@
                        const std::vector<Extent>& old_extents,
                        const std::vector<Extent>& new_extents,
                        bool bsdiff_allowed,
+                       bool imgdiff_allowed,
                        brillo::Blob* out_data,
                        InstallOperation* out_op,
                        bool src_ops_allowed);
 
-// Runs the bsdiff tool on two files and returns the resulting delta in
-// |out|. Returns true on success.
-bool BsdiffFiles(const std::string& old_file,
-                 const std::string& new_file,
-                 brillo::Blob* out);
+// Runs the bsdiff or imgdiff tool in |diff_path| on two files and returns the
+// resulting delta in |out|. Returns true on success.
+bool DiffFiles(const std::string& diff_path,
+               const std::string& old_file,
+               const std::string& new_file,
+               brillo::Blob* out);
 
 // Returns true if |op| is a no-op operation that doesn't do any useful work
 // (e.g., a move operation that copies blocks onto themselves).
diff --git a/payload_generator/delta_diff_utils_unittest.cc b/payload_generator/delta_diff_utils_unittest.cc
index 72349d8..7aadfdf 100644
--- a/payload_generator/delta_diff_utils_unittest.cc
+++ b/payload_generator/delta_diff_utils_unittest.cc
@@ -179,6 +179,7 @@
       old_extents,
       new_extents,
       true,  // bsdiff_allowed
+      true,  // imgdiff_allowed
       &data,
       &op,
       false));  // src_ops_allowed
@@ -239,6 +240,7 @@
       old_extents,
       new_extents,
       true,  // bsdiff_allowed
+      true,  // imgdiff_allowed
       &data,
       &op,
       false));  // src_ops_allowed
@@ -303,6 +305,7 @@
       old_extents,
       new_extents,
       true,  // bsdiff_allowed
+      true,  // imgdiff_allowed
       &data,
       &op,
       false));  // src_ops_allowed
@@ -345,6 +348,7 @@
       old_extents,
       new_extents,
       false,  // bsdiff_allowed
+      false,  // imgdiff_allowed
       &data,
       &op,
       false));  // src_ops_allowed
@@ -376,6 +380,7 @@
       old_extents,
       new_extents,
       false,  // bsdiff_allowed
+      false,  // imgdiff_allowed
       &data,
       &op,
       false));  // src_ops_allowed
@@ -418,6 +423,7 @@
         old_extents,
         new_extents,
         true,  // bsdiff_allowed
+        true,  // imgdiff_allowed
         &data,
         &op,
         false));  // src_ops_allowed
@@ -459,6 +465,7 @@
       old_extents,
       new_extents,
       true,  // bsdiff_allowed
+      true,  // imgdiff_allowed
       &data,
       &op,
       true));  // src_ops_allowed
@@ -492,6 +499,7 @@
       old_extents,
       new_extents,
       true,  // bsdiff_allowed
+      true,  // imgdiff_allowed
       &data,
       &op,
       true));  // src_ops_allowed
diff --git a/payload_generator/extent_utils.cc b/payload_generator/extent_utils.cc
index 1093445..72e4b7c 100644
--- a/payload_generator/extent_utils.cc
+++ b/payload_generator/extent_utils.cc
@@ -16,12 +16,15 @@
 
 #include "update_engine/payload_generator/extent_utils.h"
 
+#include <inttypes.h>
+
 #include <string>
 #include <utility>
 #include <vector>
 
 #include <base/logging.h>
 #include <base/macros.h>
+#include <base/strings/stringprintf.h>
 
 #include "update_engine/payload_consumer/payload_constants.h"
 #include "update_engine/payload_generator/annotated_operation.h"
@@ -93,6 +96,14 @@
   }
 }
 
+string ExtentsToString(const vector<Extent>& extents) {
+  string ext_str;
+  for (const Extent& e : extents)
+    ext_str += base::StringPrintf(
+        "[%" PRIu64 ", %" PRIu64 "] ", e.start_block(), e.num_blocks());
+  return ext_str;
+}
+
 void NormalizeExtents(vector<Extent>* extents) {
   vector<Extent> new_extents;
   for (const Extent& curr_ext : *extents) {
diff --git a/payload_generator/extent_utils.h b/payload_generator/extent_utils.h
index 91729d5..3e45264 100644
--- a/payload_generator/extent_utils.h
+++ b/payload_generator/extent_utils.h
@@ -17,6 +17,7 @@
 #ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_UTILS_H_
 #define UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_UTILS_H_
 
+#include <string>
 #include <vector>
 
 #include "update_engine/payload_consumer/payload_constants.h"
@@ -76,6 +77,9 @@
 void ExtentsToVector(const google::protobuf::RepeatedPtrField<Extent>& extents,
                      std::vector<Extent>* out_vector);
 
+// Returns a string representing all extents in |extents|.
+std::string ExtentsToString(const std::vector<Extent>& extents);
+
 // Takes a pointer to extents |extents| and extents |extents_to_add|, and
 // merges them by adding |extents_to_add| to |extents| and normalizing.
 void ExtendExtents(
diff --git a/payload_generator/generate_delta_main.cc b/payload_generator/generate_delta_main.cc
index d4b3641..70df2a0 100644
--- a/payload_generator/generate_delta_main.cc
+++ b/payload_generator/generate_delta_main.cc
@@ -535,6 +535,11 @@
     LOG(INFO) << "Using provided minor_version=" << FLAGS_minor_version;
   }
 
+  if (payload_config.minor_version >= kImgdiffMinorPayloadVersion) {
+    // TODO(senj): Check if the zlib version in source and target are the same.
+    payload_config.imgdiff_allowed = true;
+  }
+
   if (payload_config.is_delta) {
     LOG(INFO) << "Generating delta update";
   } else {
diff --git a/payload_generator/inplace_generator.cc b/payload_generator/inplace_generator.cc
index 2111748..dcc8e01 100644
--- a/payload_generator/inplace_generator.cc
+++ b/payload_generator/inplace_generator.cc
@@ -572,6 +572,7 @@
         (*graph)[cut.old_dst].aop.name,
         -1,  // chunk_blocks, forces to have a single operation.
         blob_file,
+        false,
         false));  // src_ops_allowed
     TEST_AND_RETURN_FALSE(new_aop.size() == 1);
     TEST_AND_RETURN_FALSE(AddInstallOpToGraph(
@@ -807,6 +808,7 @@
                                    hard_chunk_blocks,
                                    soft_chunk_blocks,
                                    blob_file,
+                                   false,    // imgdiff_allowed
                                    false));  // src_ops_allowed
   LOG(INFO) << "Done reading " << new_part.name;
 
diff --git a/payload_generator/payload_generation_config.cc b/payload_generator/payload_generation_config.cc
index 813e33c..f93a95a 100644
--- a/payload_generator/payload_generation_config.cc
+++ b/payload_generator/payload_generation_config.cc
@@ -126,7 +126,11 @@
     // Check for the supported minor_version values.
     TEST_AND_RETURN_FALSE(minor_version == kInPlaceMinorPayloadVersion ||
                           minor_version == kSourceMinorPayloadVersion ||
-                          minor_version == kOpSrcHashMinorPayloadVersion);
+                          minor_version == kOpSrcHashMinorPayloadVersion ||
+                          minor_version == kImgdiffMinorPayloadVersion);
+
+    if (imgdiff_allowed)
+      TEST_AND_RETURN_FALSE(minor_version >= kImgdiffMinorPayloadVersion);
 
     // If new_image_info is present, old_image_info must be present.
     TEST_AND_RETURN_FALSE(source.ImageInfoIsEmpty() ==
diff --git a/payload_generator/payload_generation_config.h b/payload_generator/payload_generation_config.h
index 21bb89b..92ebbe5 100644
--- a/payload_generator/payload_generation_config.h
+++ b/payload_generator/payload_generation_config.h
@@ -125,6 +125,9 @@
   // Wheter the requested payload is a delta payload.
   bool is_delta = false;
 
+  // Wheter the IMGDIFF operation is allowed.
+  bool imgdiff_allowed = false;
+
   // The major_version of the requested payload.
   uint64_t major_version;