better patching for zip files

Adds a zip mode ("-z") to imgdiff to construct efficient patches for
zip files (including jars and apks).  We identify the regions within
the zip file containing deflated data, and when a corresponding file
can be found in the source zip, a patch is generated for the
uncompressed version of the data.

The GZIP chunk type is replaced with a DEFLATE chunk type that handles
a raw deflated data stream.  This new DEFLATE chunk can be used for
both gzipped pieces (as found within boot and recovery images) and zip
files (apks, etc.)  The gzip header and footer are handled by NORMAL
chunks on either side of the main DEFLATE chunks.  (Typically these
tiny NORMAL chunks will get merged with adjacent chunks, so the number
of output chunks is unaffected.)

Add a test script that tests the generate-apply cycle on all the zips
and images within a pair of full OTA packages.

8 files changed, 906 insertions, 203 deletions

diff --git a/tools/applypatch/Android.mk b/tools/applypatch/Android.mk
index fe317ff..9a6d2be 100644
--- a/tools/applypatch/Android.mk
+++ b/tools/applypatch/Android.mk
@@ -17,7 +17,7 @@ ifneq ($(TARGET_SIMULATOR),true)
 LOCAL_PATH := $(call my-dir)
 include $(CLEAR_VARS)
 
-LOCAL_SRC_FILES := applypatch.c bsdiff.c freecache.c imgpatch.c
+LOCAL_SRC_FILES := applypatch.c bsdiff.c freecache.c imgpatch.c utils.c
 LOCAL_MODULE := libapplypatch
 LOCAL_MODULE_TAGS := eng
 LOCAL_C_INCLUDES += external/bzip2 external/zlib bootable/recovery
@@ -39,7 +39,7 @@ include $(BUILD_EXECUTABLE)
 
 include $(CLEAR_VARS)
 
-LOCAL_SRC_FILES := imgdiff.c
+LOCAL_SRC_FILES := imgdiff.c utils.c
 LOCAL_MODULE := imgdiff
 LOCAL_FORCE_STATIC_EXECUTABLE := true
 LOCAL_MODULE_TAGS := eng
diff --git a/tools/applypatch/applypatch.c b/tools/applypatch/applypatch.c
index 185d3de..06089ea 100644
--- a/tools/applypatch/applypatch.c
+++ b/tools/applypatch/applypatch.c
@@ -765,7 +765,8 @@ int applypatch(int argc, char** argv) {
       return result;
     }
   } else if (header_bytes_read >= 8 &&
-             memcmp(header, "IMGDIFF1", 8) == 0) {
+             memcmp(header, "IMGDIFF", 7) == 0 &&
+             (header[7] == '1' || header[7] == '2')) {
     int result = ApplyImagePatch(source_to_use->data, source_to_use->size,
                                  patch_filename, output, &ctx);
     if (result != 0) {
@@ -773,7 +774,7 @@ int applypatch(int argc, char** argv) {
       return result;
     }
   } else {
-    fprintf(stderr, "Unknown patch file format");
+    fprintf(stderr, "Unknown patch file format\n");
     return 1;
   }
 
diff --git a/tools/applypatch/imgdiff.c b/tools/applypatch/imgdiff.c
index 6d610e6..51835b4 100644
--- a/tools/applypatch/imgdiff.c
+++ b/tools/applypatch/imgdiff.c
@@ -64,11 +64,15 @@
  *    "IMGDIFF1"                  (8)   [magic number and version]
  *    chunk count                 (4)
  *    for each chunk:
- *        chunk type              (4)   [CHUNK_NORMAL or CHUNK_GZIP]
- *        source start            (8)
- *        source len              (8)
- *        bsdiff patch offset     (8)   [from start of patch file]
- *        if chunk type == CHUNK_GZIP:
+ *        chunk type              (4)   [CHUNK_{NORMAL, GZIP, DEFLATE, RAW}]
+ *        if chunk type == CHUNK_NORMAL:
+ *           source start         (8)
+ *           source len           (8)
+ *           bsdiff patch offset  (8)   [from start of patch file]
+ *        if chunk type == CHUNK_GZIP:      (version 1 only)
+ *           source start         (8)
+ *           source len           (8)
+ *           bsdiff patch offset  (8)   [from start of patch file]
  *           source expanded len  (8)   [size of uncompressed source]
  *           target expected len  (8)   [size of uncompressed target]
  *           gzip level           (4)
@@ -79,6 +83,20 @@
  *           gzip header len      (4)
  *           gzip header          (gzip header len)
  *           gzip footer          (8)
+ *        if chunk type == CHUNK_DEFLATE:   (version 2 only)
+ *           source start         (8)
+ *           source len           (8)
+ *           bsdiff patch offset  (8)   [from start of patch file]
+ *           source expanded len  (8)   [size of uncompressed source]
+ *           target expected len  (8)   [size of uncompressed target]
+ *           gzip level           (4)
+ *                method          (4)
+ *                windowBits      (4)
+ *                memLevel        (4)
+ *                strategy        (4)
+ *        if chunk type == RAW:             (version 2 only)
+ *           target len           (4)
+ *           data                 (target len)
  *
  * All integers are little-endian.  "source start" and "source len"
  * specify the section of the input image that comprises this chunk,
@@ -104,29 +122,230 @@
 
 #include "zlib.h"
 #include "imgdiff.h"
+#include "utils.h"
 
 typedef struct {
-  int type;             // CHUNK_NORMAL or CHUNK_GZIP
+  int type;             // CHUNK_NORMAL, CHUNK_DEFLATE
   size_t start;         // offset of chunk in original image file
 
   size_t len;
-  unsigned char* data;  // data to be patched (ie, uncompressed, for
-                        // gzip chunks)
+  unsigned char* data;  // data to be patched (uncompressed, for deflate chunks)
+
+  size_t source_start;
+  size_t source_len;
 
-  // everything else is for CHUNK_GZIP chunks only:
+  // --- for CHUNK_DEFLATE chunks only: ---
 
-  size_t gzip_header_len;
-  unsigned char* gzip_header;
-  unsigned char* gzip_footer;
+  // original (compressed) deflate data
+  size_t deflate_len;
+  unsigned char* deflate_data;
 
-  // original (compressed) gzip data, including header and footer
-  size_t gzip_len;
-  unsigned char* gzip_data;
+  char* filename;       // used for zip entries
 
   // deflate encoder parameters
   int level, method, windowBits, memLevel, strategy;
+
+  size_t source_uncompressed_len;
 } ImageChunk;
 
+typedef struct {
+  int data_offset;
+  int deflate_len;
+  int uncomp_len;
+  char* filename;
+} ZipFileEntry;
+
+static int fileentry_compare(const void* a, const void* b) {
+  int ao = ((ZipFileEntry*)a)->data_offset;
+  int bo = ((ZipFileEntry*)b)->data_offset;
+  if (ao < bo) {
+    return -1;
+  } else if (ao > bo) {
+    return 1;
+  } else {
+    return 0;
+  }
+}
+
+unsigned char* ReadZip(const char* filename,
+                       int* num_chunks, ImageChunk** chunks,
+                       int include_pseudo_chunk) {
+  struct stat st;
+  if (stat(filename, &st) != 0) {
+    fprintf(stderr, "failed to stat \"%s\": %s\n", filename, strerror(errno));
+    return NULL;
+  }
+
+  unsigned char* img = malloc(st.st_size);
+  FILE* f = fopen(filename, "rb");
+  if (fread(img, 1, st.st_size, f) != st.st_size) {
+    fprintf(stderr, "failed to read \"%s\" %s\n", filename, strerror(errno));
+    fclose(f);
+    return NULL;
+  }
+  fclose(f);
+
+  // look for the end-of-central-directory record.
+
+  int i;
+  for (i = st.st_size-20; i >= 0 && i > st.st_size - 65600; --i) {
+    if (img[i] == 0x50 && img[i+1] == 0x4b &&
+        img[i+2] == 0x05 && img[i+3] == 0x06) {
+      break;
+    }
+  }
+  // double-check: this archive consists of a single "disk"
+  if (!(img[i+4] == 0 && img[i+5] == 0 && img[i+6] == 0 && img[i+7] == 0)) {
+    fprintf(stderr, "can't process multi-disk archive\n");
+    return NULL;
+  }
+
+  int cdcount = Read2(img+i+8);
+  int cdoffset = Read4(img+i+16);
+
+  ZipFileEntry* temp_entries = malloc(cdcount * sizeof(ZipFileEntry));
+  int entrycount = 0;
+
+  unsigned char* cd = img+cdoffset;
+  for (i = 0; i < cdcount; ++i) {
+    if (!(cd[0] == 0x50 && cd[1] == 0x4b && cd[2] == 0x01 && cd[3] == 0x02)) {
+      fprintf(stderr, "bad central directory entry %d\n", i);
+      return NULL;
+    }
+
+    int clen = Read4(cd+20);   // compressed len
+    int ulen = Read4(cd+24);   // uncompressed len
+    int nlen = Read2(cd+28);   // filename len
+    int xlen = Read2(cd+30);   // extra field len
+    int mlen = Read2(cd+32);   // file comment len
+    int hoffset = Read4(cd+42);   // local header offset
+
+    char* filename = malloc(nlen+1);
+    memcpy(filename, cd+46, nlen);
+    filename[nlen] = '\0';
+
+    int method = Read2(cd+10);
+
+    cd += 46 + nlen + xlen + mlen;
+
+    if (method != 8) {  // 8 == deflate
+      free(filename);
+      continue;
+    }
+
+    unsigned char* lh = img + hoffset;
+
+    if (!(lh[0] == 0x50 && lh[1] == 0x4b && lh[2] == 0x03 && lh[3] == 0x04)) {
+      fprintf(stderr, "bad local file header entry %d\n", i);
+      return NULL;
+    }
+
+    if (Read2(lh+26) != nlen || memcmp(lh+30, filename, nlen) != 0) {
+      fprintf(stderr, "central dir filename doesn't match local header\n");
+      return NULL;
+    }
+
+    xlen = Read2(lh+28);   // extra field len; might be different from CD entry?
+
+    temp_entries[entrycount].data_offset = hoffset+30+nlen+xlen;
+    temp_entries[entrycount].deflate_len = clen;
+    temp_entries[entrycount].uncomp_len = ulen;
+    temp_entries[entrycount].filename = filename;
+    ++entrycount;
+  }
+
+  qsort(temp_entries, entrycount, sizeof(ZipFileEntry), fileentry_compare);
+
+#if 0
+  printf("found %d deflated entries\n", entrycount);
+  for (i = 0; i < entrycount; ++i) {
+    printf("off %10d  len %10d unlen %10d   %p %s\n",
+           temp_entries[i].data_offset,
+           temp_entries[i].deflate_len,
+           temp_entries[i].uncomp_len,
+           temp_entries[i].filename,
+           temp_entries[i].filename);
+  }
+#endif
+
+  *num_chunks = 0;
+  *chunks = malloc((entrycount*2+2) * sizeof(ImageChunk));
+  ImageChunk* curr = *chunks;
+
+  if (include_pseudo_chunk) {
+    curr->type = CHUNK_NORMAL;
+    curr->start = 0;
+    curr->len = st.st_size;
+    curr->data = img;
+    curr->filename = NULL;
+    ++curr;
+    ++*num_chunks;
+  }
+
+  int pos = 0;
+  int nextentry = 0;
+
+  while (pos < st.st_size) {
+    if (nextentry < entrycount && pos == temp_entries[nextentry].data_offset) {
+      curr->type = CHUNK_DEFLATE;
+      curr->start = pos;
+      curr->deflate_len = temp_entries[nextentry].deflate_len;
+      curr->deflate_data = img + pos;
+      curr->filename = temp_entries[nextentry].filename;
+
+      curr->len = temp_entries[nextentry].uncomp_len;
+      curr->data = malloc(curr->len);
+
+      z_stream strm;
+      strm.zalloc = Z_NULL;
+      strm.zfree = Z_NULL;
+      strm.opaque = Z_NULL;
+      strm.avail_in = curr->deflate_len;
+      strm.next_in = curr->deflate_data;
+
+      // -15 means we are decoding a 'raw' deflate stream; zlib will
+      // not expect zlib headers.
+      int ret = inflateInit2(&strm, -15);
+
+      strm.avail_out = curr->len;
+      strm.next_out = curr->data;
+      ret = inflate(&strm, Z_NO_FLUSH);
+      if (ret != Z_STREAM_END) {
+        fprintf(stderr, "failed to inflate \"%s\"; %d\n", curr->filename, ret);
+        return NULL;
+      }
+
+      inflateEnd(&strm);
+
+      pos += curr->deflate_len;
+      ++nextentry;
+      ++*num_chunks;
+      ++curr;
+      continue;
+    }
+
+    // use a normal chunk to take all the data up to the start of the
+    // next deflate section.
+
+    curr->type = CHUNK_NORMAL;
+    curr->start = pos;
+    if (nextentry < entrycount) {
+      curr->len = temp_entries[nextentry].data_offset - pos;
+    } else {
+      curr->len = st.st_size - pos;
+    }
+    curr->data = img + pos;
+    curr->filename = NULL;
+    pos += curr->len;
+
+    ++*num_chunks;
+    ++curr;
+  }
+
+  free(temp_entries);
+  return img;
+}
+
 /*
  * Read the given file and break it up into chunks, putting the number
  * of chunks and their info in *num_chunks and **chunks,
@@ -166,38 +385,45 @@ unsigned char* ReadImage(const char* filename,
   while (pos < st.st_size) {
     unsigned char* p = img+pos;
 
-    // Reallocate the list for every chunk; we expect the number of
-    // chunks to be small (5 for typical boot and recovery images).
-    ++*num_chunks;
-    *chunks = realloc(*chunks, *num_chunks * sizeof(ImageChunk));
-    ImageChunk* curr = *chunks + (*num_chunks-1);
-    curr->start = pos;
-
     if (st.st_size - pos >= 4 &&
         p[0] == 0x1f && p[1] == 0x8b &&
         p[2] == 0x08 &&    // deflate compression
         p[3] == 0x00) {    // no header flags
       // 'pos' is the offset of the start of a gzip chunk.
 
-      curr->type = CHUNK_GZIP;
-      curr->gzip_header_len = GZIP_HEADER_LEN;
-      curr->gzip_header = p;
+      *num_chunks += 3;
+      *chunks = realloc(*chunks, *num_chunks * sizeof(ImageChunk));
+      ImageChunk* curr = *chunks + (*num_chunks-3);
+
+      // create a normal chunk for the header.
+      curr->start = pos;
+      curr->type = CHUNK_NORMAL;
+      curr->len = GZIP_HEADER_LEN;
+      curr->data = p;
+
+      pos += curr->len;
+      p += curr->len;
+      ++curr;
+
+      curr->type = CHUNK_DEFLATE;
+      curr->filename = NULL;
 
       // We must decompress this chunk in order to discover where it
       // ends, and so we can put the uncompressed data and its length
-      // into curr->data and curr->len;
+      // into curr->data and curr->len.
 
       size_t allocated = 32768;
       curr->len = 0;
       curr->data = malloc(allocated);
-      curr->gzip_data = p;
+      curr->start = pos;
+      curr->deflate_data = p;
 
       z_stream strm;
       strm.zalloc = Z_NULL;
       strm.zfree = Z_NULL;
       strm.opaque = Z_NULL;
-      strm.avail_in = st.st_size - (pos + curr->gzip_header_len);
-      strm.next_in = p + GZIP_HEADER_LEN;
+      strm.avail_in = st.st_size - pos;
+      strm.next_in = p;
 
       // -15 means we are decoding a 'raw' deflate stream; zlib will
       // not expect zlib headers.
@@ -214,27 +440,42 @@ unsigned char* ReadImage(const char* filename,
         }
       } while (ret != Z_STREAM_END);
 
-      curr->gzip_len = st.st_size - strm.avail_in - pos + GZIP_FOOTER_LEN;
-      pos = st.st_size - strm.avail_in;
+      curr->deflate_len = st.st_size - strm.avail_in - pos;
       inflateEnd(&strm);
+      pos += curr->deflate_len;
+      p += curr->deflate_len;
+      ++curr;
+
+      // create a normal chunk for the footer
 
-      // consume the gzip footer.
-      curr->gzip_footer = img+pos;
-      pos += GZIP_FOOTER_LEN;
-      p = img+pos;
+      curr->type = CHUNK_NORMAL;
+      curr->start = pos;
+      curr->len = GZIP_FOOTER_LEN;
+      curr->data = img+pos;
+
+      pos += curr->len;
+      p += curr->len;
+      ++curr;
 
       // The footer (that we just skipped over) contains the size of
       // the uncompressed data.  Double-check to make sure that it
       // matches the size of the data we got when we actually did
       // the decompression.
-      size_t footer_size = p[-4] + (p[-3] << 8) + (p[-2] << 16) + (p[-1] << 24);
-      if (footer_size != curr->len) {
+      size_t footer_size = Read4(p-4);
+      if (footer_size != curr[-2].len) {
         fprintf(stderr, "Error: footer size %d != decompressed size %d\n",
-                footer_size, curr->len);
+                footer_size, curr[-2].len);
         free(img);
         return NULL;
       }
     } else {
+      // Reallocate the list for every chunk; we expect the number of
+      // chunks to be small (5 for typical boot and recovery images).
+      ++*num_chunks;
+      *chunks = realloc(*chunks, *num_chunks * sizeof(ImageChunk));
+      ImageChunk* curr = *chunks + (*num_chunks-1);
+      curr->start = pos;
+
       // 'pos' is not the offset of the start of a gzip chunk, so scan
       // forward until we find a gzip header.
       curr->type = CHUNK_NORMAL;
@@ -264,7 +505,13 @@ unsigned char* ReadImage(const char* filename,
  * the chunk).  Return 0 on success.
  */
 int TryReconstruction(ImageChunk* chunk, unsigned char* out) {
-  size_t p = chunk->gzip_header_len;
+  size_t p = 0;
+
+#if 0
+  fprintf(stderr, "trying %d %d %d %d %d\n",
+          chunk->level, chunk->method, chunk->windowBits,
+          chunk->memLevel, chunk->strategy);
+#endif
 
   z_stream strm;
   strm.zalloc = Z_NULL;
@@ -281,7 +528,7 @@ int TryReconstruction(ImageChunk* chunk, unsigned char* out) {
     ret = deflate(&strm, Z_FINISH);
     size_t have = BUFFER_SIZE - strm.avail_out;
 
-    if (memcmp(out, chunk->gzip_data+p, have) != 0) {
+    if (memcmp(out, chunk->deflate_data+p, have) != 0) {
       // mismatch; data isn't the same.
       deflateEnd(&strm);
       return -1;
@@ -289,7 +536,7 @@ int TryReconstruction(ImageChunk* chunk, unsigned char* out) {
     p += have;
   } while (ret != Z_STREAM_END);
   deflateEnd(&strm);
-  if (p + GZIP_FOOTER_LEN != chunk->gzip_len) {
+  if (p != chunk->deflate_len) {
     // mismatch; ran out of data before we should have.
     return -1;
   }
@@ -302,9 +549,9 @@ int TryReconstruction(ImageChunk* chunk, unsigned char* out) {
  * strategy fields in the chunk to the encoding parameters needed to
  * produce the right output.  Returns 0 on success.
  */
-int ReconstructGzipChunk(ImageChunk* chunk) {
-  if (chunk->type != CHUNK_GZIP) {
-    fprintf(stderr, "attempt to reconstruct non-gzip chunk\n");
+int ReconstructDeflateChunk(ImageChunk* chunk) {
+  if (chunk->type != CHUNK_DEFLATE) {
+    fprintf(stderr, "attempt to reconstruct non-deflate chunk\n");
     return -1;
   }
 
@@ -329,27 +576,6 @@ int ReconstructGzipChunk(ImageChunk* chunk) {
   return -1;
 }
 
-/** Write a 4-byte value to f in little-endian order. */
-void Write4(int value, FILE* f) {
-  fputc(value & 0xff, f);
-  fputc((value >> 8) & 0xff, f);
-  fputc((value >> 16) & 0xff, f);
-  fputc((value >> 24) & 0xff, f);
-}
-
-/** Write an 8-byte value to f in little-endian order. */
-void Write8(long long value, FILE* f) {
-  fputc(value & 0xff, f);
-  fputc((value >> 8) & 0xff, f);
-  fputc((value >> 16) & 0xff, f);
-  fputc((value >> 24) & 0xff, f);
-  fputc((value >> 32) & 0xff, f);
-  fputc((value >> 40) & 0xff, f);
-  fputc((value >> 48) & 0xff, f);
-  fputc((value >> 56) & 0xff, f);
-}
-
-
 /*
  * Given source and target chunks, compute a bsdiff patch between them
  * by running bsdiff in a subprocess.  Return the patch data, placing
@@ -357,6 +583,14 @@ void Write8(long long value, FILE* f) {
  * program to be in the path.
  */
 unsigned char* MakePatch(ImageChunk* src, ImageChunk* tgt, size_t* size) {
+  if (tgt->type == CHUNK_NORMAL) {
+    if (tgt->len <= 160) {
+      tgt->type = CHUNK_RAW;
+      *size = tgt->len;
+      return tgt->data;
+    }
+  }
+
   char stemp[] = "/tmp/imgdiff-src-XXXXXX";
   char ttemp[] = "/tmp/imgdiff-tgt-XXXXXX";
   char ptemp[] = "/tmp/imgdiff-patch-XXXXXX";
@@ -405,6 +639,17 @@ unsigned char* MakePatch(ImageChunk* src, ImageChunk* tgt, size_t* size) {
   }
 
   unsigned char* data = malloc(st.st_size);
+
+  if (tgt->type == CHUNK_NORMAL && tgt->len <= st.st_size) {
+    unlink(stemp);
+    unlink(ttemp);
+    unlink(ptemp);
+
+    tgt->type = CHUNK_RAW;
+    *size = tgt->len;
+    return tgt->data;
+  }
+
   *size = st.st_size;
 
   f = fopen(ptemp, "rb");
@@ -422,6 +667,17 @@ unsigned char* MakePatch(ImageChunk* src, ImageChunk* tgt, size_t* size) {
   unlink(ttemp);
   unlink(ptemp);
 
+  tgt->source_start = src->start;
+  switch (tgt->type) {
+    case CHUNK_NORMAL:
+      tgt->source_len = src->len;
+      break;
+    case CHUNK_DEFLATE:
+      tgt->source_len = src->deflate_len;
+      tgt->source_uncompressed_len = src->len;
+      break;
+  }
+
   return data;
 }
 
@@ -432,11 +688,12 @@ unsigned char* MakePatch(ImageChunk* src, ImageChunk* tgt, size_t* size) {
  * where some gzip chunks are reconstructible but others aren't (by
  * treating the ones that aren't as normal chunks).
  */
-void ChangeGzipChunkToNormal(ImageChunk* ch) {
+void ChangeDeflateChunkToNormal(ImageChunk* ch) {
+  if (ch->type != CHUNK_DEFLATE) return;
   ch->type = CHUNK_NORMAL;
   free(ch->data);
-  ch->data = ch->gzip_data;
-  ch->len = ch->gzip_len;
+  ch->data = ch->deflate_data;
+  ch->len = ch->deflate_len;
 }
 
 /*
@@ -450,9 +707,9 @@ int AreChunksEqual(ImageChunk* a, ImageChunk* b) {
         case CHUNK_NORMAL:
             return a->len == b->len && memcmp(a->data, b->data, a->len) == 0;
 
-        case CHUNK_GZIP:
-            return a->gzip_len == b->gzip_len &&
-                memcmp(a->gzip_data, b->gzip_data, a->gzip_len) == 0;
+        case CHUNK_DEFLATE:
+            return a->deflate_len == b->deflate_len &&
+                memcmp(a->deflate_data, b->deflate_data, a->deflate_len) == 0;
 
         default:
             fprintf(stderr, "unknown chunk type %d\n", a->type);
@@ -462,7 +719,7 @@ int AreChunksEqual(ImageChunk* a, ImageChunk* b) {
 
 /*
  * Look for runs of adjacent normal chunks and compress them down into
- * a single chunk.  (Such runs can be produced when gzip chunks are
+ * a single chunk.  (Such runs can be produced when deflate chunks are
  * changed to normal chunks.)
  */
 void MergeAdjacentNormalChunks(ImageChunk* chunks, int* num_chunks) {
@@ -476,7 +733,7 @@ void MergeAdjacentNormalChunks(ImageChunk* chunks, int* num_chunks) {
       // that constitute a solid block of data (ie, each chunk begins
       // where the previous one ended).
       for (in_end = in_start+1;
-           in_end < num_chunks && chunks[in_end].type == CHUNK_NORMAL &&
+           in_end < *num_chunks && chunks[in_end].type == CHUNK_NORMAL &&
              (chunks[in_end].start ==
               chunks[in_end-1].start + chunks[in_end-1].len &&
               chunks[in_end].data ==
@@ -485,11 +742,16 @@ void MergeAdjacentNormalChunks(ImageChunk* chunks, int* num_chunks) {
     }
 
     if (in_end == in_start+1) {
+#if 0
+      printf("chunk %d is now %d\n", in_start, out);
+#endif
       if (out != in_start) {
         memcpy(chunks+out, chunks+in_start, sizeof(ImageChunk));
       }
     } else {
-      printf("collapse normal chunks %d - %d\n", in_start, in_end-1);
+#if 0
+      printf("collapse normal chunks %d-%d into %d\n", in_start, in_end-1, out);
+#endif
 
       // Merge chunks [in_start, in_end-1] into one chunk.  Since the
       // data member of each chunk is just a pointer into an in-memory
@@ -510,93 +772,159 @@ void MergeAdjacentNormalChunks(ImageChunk* chunks, int* num_chunks) {
   *num_chunks = out;
 }
 
+ImageChunk* FindChunkByName(const char* name,
+                            ImageChunk* chunks, int num_chunks) {
+  int i;
+  for (i = 0; i < num_chunks; ++i) {
+    if (chunks[i].type == CHUNK_DEFLATE && chunks[i].filename &&
+        strcmp(name, chunks[i].filename) == 0) {
+      return chunks+i;
+    }
+  }
+  return NULL;
+}
+
 int main(int argc, char** argv) {
-  if (argc != 4) {
-    fprintf(stderr, "usage: %s <src-img> <tgt-img> <patch-file>\n", argv[0]);
+  if (argc != 4 && argc != 5) {
+    usage:
+    fprintf(stderr, "usage: %s [-z] <src-img> <tgt-img> <patch-file>\n",
+            argv[0]);
     return 2;
   }
 
-  int num_src_chunks;
-  ImageChunk* src_chunks;
-  if (ReadImage(argv[1], &num_src_chunks, &src_chunks) == NULL) {
-    fprintf(stderr, "failed to break apart source image\n");
-    return 1;
+  int zip_mode = 0;
+
+  if (strcmp(argv[1], "-z") == 0) {
+    zip_mode = 1;
+    --argc;
+    ++argv;
   }
 
+
+  int num_src_chunks;
+  ImageChunk* src_chunks;
   int num_tgt_chunks;
   ImageChunk* tgt_chunks;
-  if (ReadImage(argv[2], &num_tgt_chunks, &tgt_chunks) == NULL) {
-    fprintf(stderr, "failed to break apart target image\n");
-    return 1;
-  }
+  int i;
 
-  // Verify that the source and target images have the same chunk
-  // structure (ie, the same sequence of gzip and normal chunks).
+  if (zip_mode) {
+    if (ReadZip(argv[1], &num_src_chunks, &src_chunks, 1) == NULL) {
+      fprintf(stderr, "failed to break apart source zip file\n");
+      return 1;
+    }
+    if (ReadZip(argv[2], &num_tgt_chunks, &tgt_chunks, 0) == NULL) {
+      fprintf(stderr, "failed to break apart target zip file\n");
+      return 1;
+    }
+  } else {
+    if (ReadImage(argv[1], &num_src_chunks, &src_chunks) == NULL) {
+      fprintf(stderr, "failed to break apart source image\n");
+      return 1;
+    }
+    if (ReadImage(argv[2], &num_tgt_chunks, &tgt_chunks) == NULL) {
+      fprintf(stderr, "failed to break apart target image\n");
+      return 1;
+    }
 
-  if (num_src_chunks != num_tgt_chunks) {
-    fprintf(stderr, "source and target don't have same number of chunks!\n");
-    return 1;
-  }
-  int i;
-  for (i = 0; i < num_src_chunks; ++i) {
-    if (src_chunks[i].type != tgt_chunks[i].type) {
-      fprintf(stderr, "source and target don't have same chunk "
-              "structure! (chunk %d)\n", i);
+    // Verify that the source and target images have the same chunk
+    // structure (ie, the same sequence of deflate and normal chunks).
+
+    if (num_src_chunks != num_tgt_chunks) {
+      fprintf(stderr, "source and target don't have same number of chunks!\n");
       return 1;
     }
+    for (i = 0; i < num_src_chunks; ++i) {
+      if (src_chunks[i].type != tgt_chunks[i].type) {
+        fprintf(stderr, "source and target don't have same chunk "
+                "structure! (chunk %d)\n", i);
+        return 1;
+      }
+    }
   }
 
   for (i = 0; i < num_tgt_chunks; ++i) {
-    if (tgt_chunks[i].type == CHUNK_GZIP) {
+    if (tgt_chunks[i].type == CHUNK_DEFLATE) {
       // Confirm that given the uncompressed chunk data in the target, we
       // can recompress it and get exactly the same bits as are in the
       // input target image.  If this fails, treat the chunk as a normal
-      // non-gzipped chunk.
-      if (ReconstructGzipChunk(tgt_chunks+i) < 0) {
-        printf("failed to reconstruct target gzip chunk %d; "
-               "treating as normal chunk\n", i);
-        ChangeGzipChunkToNormal(tgt_chunks+i);
-        ChangeGzipChunkToNormal(src_chunks+i);
+      // non-deflated chunk.
+      if (ReconstructDeflateChunk(tgt_chunks+i) < 0) {
+        printf("failed to reconstruct target deflate chunk %d [%s]; "
+               "treating as normal\n", i, tgt_chunks[i].filename);
+        ChangeDeflateChunkToNormal(tgt_chunks+i);
+        if (zip_mode) {
+          ImageChunk* src = FindChunkByName(tgt_chunks[i].filename, src_chunks, num_src_chunks);
+          if (src) {
+            ChangeDeflateChunkToNormal(src);
+          }
+        } else {
+          ChangeDeflateChunkToNormal(src_chunks+i);
+        }
         continue;
-      } else {
-        printf("reconstructed target gzip chunk %d\n", i);
       }
 
-      // If two gzip chunks are identical (eg, the kernel has not
+      // If two deflate chunks are identical (eg, the kernel has not
       // changed between two builds), treat them as normal chunks.
       // This makes applypatch much faster -- it can apply a trivial
       // patch to the compressed data, rather than uncompressing and
       // recompressing to apply the trivial patch to the uncompressed
       // data.
-      if (AreChunksEqual(tgt_chunks+i, src_chunks+i)) {
-        printf("source and target chunk %d are identical; "
-               "treating as normal chunk\n", i);
-        ChangeGzipChunkToNormal(tgt_chunks+i);
-        ChangeGzipChunkToNormal(src_chunks+i);
+      ImageChunk* src;
+      if (zip_mode) {
+        src = FindChunkByName(tgt_chunks[i].filename, src_chunks, num_src_chunks);
+      } else {
+        src = src_chunks+i;
+      }
+
+      if (src == NULL || AreChunksEqual(tgt_chunks+i, src)) {
+        ChangeDeflateChunkToNormal(tgt_chunks+i);
+        if (src) {
+          ChangeDeflateChunkToNormal(src);
+        }
       }
     }
   }
 
-  // If we changed any gzip chunks to normal chunks, we can simplify
-  // the patch by merging neighboring normal chunks.
-  MergeAdjacentNormalChunks(src_chunks, &num_src_chunks);
-  MergeAdjacentNormalChunks(tgt_chunks, &num_tgt_chunks);
-  if (num_src_chunks != num_tgt_chunks) {
-    // This shouldn't happen.
-    fprintf(stderr, "merging normal chunks went awry\n");
-    return 1;
+  // Merging neighboring normal chunks.
+  if (zip_mode) {
+    // For zips, we only need to do this to the target:  deflated
+    // chunks are matched via filename, and normal chunks are patched
+    // using the entire source file as the source.
+    MergeAdjacentNormalChunks(tgt_chunks, &num_tgt_chunks);
+  } else {
+    // For images, we need to maintain the parallel structure of the
+    // chunk lists, so do the merging in both the source and target
+    // lists.
+    MergeAdjacentNormalChunks(tgt_chunks, &num_tgt_chunks);
+    MergeAdjacentNormalChunks(src_chunks, &num_src_chunks);
+    if (num_src_chunks != num_tgt_chunks) {
+      // This shouldn't happen.
+      fprintf(stderr, "merging normal chunks went awry\n");
+      return 1;
+    }
   }
 
   // Compute bsdiff patches for each chunk's data (the uncompressed
-  // data, in the case of gzip chunks).
-
-  unsigned char** patch_data = malloc(num_src_chunks * sizeof(unsigned char*));
-  size_t* patch_size = malloc(num_src_chunks * sizeof(size_t));
-  for (i = 0; i < num_src_chunks; ++i) {
-    patch_data[i] = MakePatch(src_chunks+i, tgt_chunks+i, patch_size+i);
-    printf("patch %d is %d bytes (of %d)\n", i, patch_size[i],
-           tgt_chunks[i].type == CHUNK_NORMAL ? tgt_chunks[i].len : tgt_chunks[i].gzip_len);
+  // data, in the case of deflate chunks).
 
+  printf("Construct patches for %d chunks...\n", num_tgt_chunks);
+  unsigned char** patch_data = malloc(num_tgt_chunks * sizeof(unsigned char*));
+  size_t* patch_size = malloc(num_tgt_chunks * sizeof(size_t));
+  for (i = 0; i < num_tgt_chunks; ++i) {
+    if (zip_mode) {
+      ImageChunk* src;
+      if (tgt_chunks[i].type == CHUNK_DEFLATE &&
+          (src = FindChunkByName(tgt_chunks[i].filename, src_chunks,
+                                 num_src_chunks))) {
+        patch_data[i] = MakePatch(src, tgt_chunks+i, patch_size+i);
+      } else {
+        patch_data[i] = MakePatch(src_chunks, tgt_chunks+i, patch_size+i);
+      }
+    } else {
+      patch_data[i] = MakePatch(src_chunks+i, tgt_chunks+i, patch_size+i);
+    }
+    printf("patch %3d is %d bytes (of %d)\n",
+           i, patch_size[i], tgt_chunks[i].source_len);
   }
 
   // Figure out how big the imgdiff file header is going to be, so
@@ -604,10 +932,18 @@ int main(int argc, char** argv) {
   // within the file.
 
   size_t total_header_size = 12;
-  for (i = 0; i < num_src_chunks; ++i) {
-    total_header_size += 4 + 8*3;
-    if (src_chunks[i].type == CHUNK_GZIP) {
-      total_header_size += 8*2 + 4*6 + tgt_chunks[i].gzip_header_len + 8;
+  for (i = 0; i < num_tgt_chunks; ++i) {
+    total_header_size += 4;
+    switch (tgt_chunks[i].type) {
+      case CHUNK_NORMAL:
+        total_header_size += 8*3;
+        break;
+      case CHUNK_DEFLATE:
+        total_header_size += 8*5 + 4*5;
+        break;
+      case CHUNK_RAW:
+        total_header_size += 4 + patch_size[i];
+        break;
     }
   }
 
@@ -617,35 +953,53 @@ int main(int argc, char** argv) {
 
   // Write out the headers.
 
-  fwrite("IMGDIFF1", 1, 8, f);
-  Write4(num_src_chunks, f);
+  fwrite("IMGDIFF2", 1, 8, f);
+  Write4(num_tgt_chunks, f);
   for (i = 0; i < num_tgt_chunks; ++i) {
     Write4(tgt_chunks[i].type, f);
-    Write8(src_chunks[i].start, f);
-    Write8(src_chunks[i].type == CHUNK_NORMAL ? src_chunks[i].len :
-           (src_chunks[i].gzip_len + src_chunks[i].gzip_header_len + 8), f);
-    Write8(offset, f);
-
-    if (tgt_chunks[i].type == CHUNK_GZIP) {
-      Write8(src_chunks[i].len, f);
-      Write8(tgt_chunks[i].len, f);
-      Write4(tgt_chunks[i].level, f);
-      Write4(tgt_chunks[i].method, f);
-      Write4(tgt_chunks[i].windowBits, f);
-      Write4(tgt_chunks[i].memLevel, f);
-      Write4(tgt_chunks[i].strategy, f);
-      Write4(tgt_chunks[i].gzip_header_len, f);
-      fwrite(tgt_chunks[i].gzip_header, 1, tgt_chunks[i].gzip_header_len, f);
-      fwrite(tgt_chunks[i].gzip_footer, 1, GZIP_FOOTER_LEN, f);
-    }
 
-    offset += patch_size[i];
+    switch (tgt_chunks[i].type) {
+      case CHUNK_NORMAL:
+        printf("chunk %3d: normal   (%10d, %10d)  %10d\n", i,
+               tgt_chunks[i].start, tgt_chunks[i].len, patch_size[i]);
+        Write8(tgt_chunks[i].source_start, f);
+        Write8(tgt_chunks[i].source_len, f);
+        Write8(offset, f);
+        offset += patch_size[i];
+        break;
+
+      case CHUNK_DEFLATE:
+        printf("chunk %3d: deflate  (%10d, %10d)  %10d  %s\n", i,
+               tgt_chunks[i].start, tgt_chunks[i].deflate_len, patch_size[i],
+               tgt_chunks[i].filename);
+        Write8(tgt_chunks[i].source_start, f);
+        Write8(tgt_chunks[i].source_len, f);
+        Write8(offset, f);
+        Write8(tgt_chunks[i].source_uncompressed_len, f);
+        Write8(tgt_chunks[i].len, f);
+        Write4(tgt_chunks[i].level, f);
+        Write4(tgt_chunks[i].method, f);
+        Write4(tgt_chunks[i].windowBits, f);
+        Write4(tgt_chunks[i].memLevel, f);
+        Write4(tgt_chunks[i].strategy, f);
+        offset += patch_size[i];
+        break;
+
+      case CHUNK_RAW:
+        printf("chunk %3d: raw      (%10d, %10d)\n", i,
+               tgt_chunks[i].start, tgt_chunks[i].len);
+        Write4(patch_size[i], f);
+        fwrite(patch_data[i], 1, patch_size[i], f);
+        break;
+    }
   }
 
   // Append each chunk's bsdiff patch, in order.
 
   for (i = 0; i < num_tgt_chunks; ++i) {
-    fwrite(patch_data[i], 1, patch_size[i], f);
+    if (tgt_chunks[i].type != CHUNK_RAW) {
+      fwrite(patch_data[i], 1, patch_size[i], f);
+    }
   }
 
   fclose(f);
diff --git a/tools/applypatch/imgdiff.h b/tools/applypatch/imgdiff.h
index 7ec45c5..f2069b4 100644
--- a/tools/applypatch/imgdiff.h
+++ b/tools/applypatch/imgdiff.h
@@ -15,8 +15,10 @@
  */
 
 // Image patch chunk types
-#define CHUNK_NORMAL 0
-#define CHUNK_GZIP   1
+#define CHUNK_NORMAL   0
+#define CHUNK_GZIP     1   // version 1 only
+#define CHUNK_DEFLATE  2   // version 2 only
+#define CHUNK_RAW      3   // version 2 only
 
 // The gzip header size is actually variable, but we currently don't
 // support gzipped data with any of the optional fields, so for now it
diff --git a/tools/applypatch/imgdiff_test.sh b/tools/applypatch/imgdiff_test.sh
new file mode 100755
index 0000000..dcdb922
--- /dev/null
+++ b/tools/applypatch/imgdiff_test.sh
@@ -0,0 +1,118 @@
+#!/bin/bash
+#
+# A script for testing imgdiff/applypatch.  It takes two full OTA
+# packages as arguments.  It generates (on the host) patches for all
+# the zip/jar/apk files they have in common, as well as boot and
+# recovery images.  It then applies the patches on the device (or
+# emulator) and checks that the resulting file is correct.
+
+EMULATOR_PORT=5580
+
+# set to 0 to use a device instead
+USE_EMULATOR=0
+
+# where on the device to do all the patching.
+WORK_DIR=/data/local/tmp
+
+START_OTA_PACKAGE=$1
+END_OTA_PACKAGE=$2
+
+# ------------------------
+
+tmpdir=$(mktemp -d)
+
+if [ "$USE_EMULATOR" == 1 ]; then
+  emulator -wipe-data -noaudio -no-window -port $EMULATOR_PORT &
+  pid_emulator=$!
+  ADB="adb -s emulator-$EMULATOR_PORT "
+else
+  ADB="adb -d "
+fi
+
+echo "waiting to connect to device"
+$ADB wait-for-device
+
+# run a command on the device; exit with the exit status of the device
+# command.
+run_command() {
+  $ADB shell "$@" \; echo \$? | awk '{if (b) {print a}; a=$0; b=1} END {exit a}'
+}
+
+testname() {
+  echo
+  echo "$1"...
+  testname="$1"
+}
+
+fail() {
+  echo
+  echo FAIL: $testname
+  echo
+  [ "$open_pid" == "" ] || kill $open_pid
+  [ "$pid_emulator" == "" ] || kill $pid_emulator
+  exit 1
+}
+
+sha1() {
+  sha1sum $1 | awk '{print $1}'
+}
+
+size() {
+  stat -c %s $1 | tr -d '\n'
+}
+
+cleanup() {
+  # not necessary if we're about to kill the emulator, but nice for
+  # running on real devices or already-running emulators.
+  testname "removing test files"
+  run_command rm $WORK_DIR/applypatch
+  run_command rm $WORK_DIR/source
+  run_command rm $WORK_DIR/target
+  run_command rm $WORK_DIR/patch
+
+  [ "$pid_emulator" == "" ] || kill $pid_emulator
+
+  rm -rf $tmpdir
+}
+
+$ADB push $ANDROID_PRODUCT_OUT/system/bin/applypatch $WORK_DIR/applypatch
+
+patch_and_apply() {
+  local fn=$1
+  shift
+
+  unzip -p $START_OTA_PACKAGE $fn > $tmpdir/source
+  unzip -p $END_OTA_PACKAGE $fn > $tmpdir/target
+  imgdiff "$@" $tmpdir/source $tmpdir/target $tmpdir/patch
+  bsdiff $tmpdir/source $tmpdir/target $tmpdir/patch.bs
+  echo "patch for $fn is $(size $tmpdir/patch) [of $(size $tmpdir/target)] ($(size $tmpdir/patch.bs) with bsdiff)"
+  echo "$fn $(size $tmpdir/patch) of $(size $tmpdir/target) bsdiff $(size $tmpdir/patch.bs)" >> /tmp/stats.txt
+  $ADB push $tmpdir/source $WORK_DIR/source || fail "source push failed"
+  run_command rm /data/local/tmp/target
+  $ADB push $tmpdir/patch $WORK_DIR/patch || fail "patch push failed"
+  run_command /data/local/tmp/applypatch /data/local/tmp/source \
+    /data/local/tmp/target $(sha1 $tmpdir/target) $(size $tmpdir/target) \
+    $(sha1 $tmpdir/source):/data/local/tmp/patch \
+    || fail "applypatch of $fn failed"
+  $ADB pull /data/local/tmp/target $tmpdir/result
+  diff -q $tmpdir/target $tmpdir/result || fail "patch output not correct!"
+}
+
+# --------------- basic execution ----------------------
+
+for i in $((zipinfo -1 $START_OTA_PACKAGE; zipinfo -1 $END_OTA_PACKAGE) | \
+           sort | uniq -d | egrep -e '[.](apk|jar|zip)$'); do
+  patch_and_apply $i -z
+done
+patch_and_apply boot.img
+patch_and_apply system/recovery.img
+
+
+# --------------- cleanup ----------------------
+
+cleanup
+
+echo
+echo PASS
+echo
+
diff --git a/tools/applypatch/imgpatch.c b/tools/applypatch/imgpatch.c
index 2efe874..697cc68 100644
--- a/tools/applypatch/imgpatch.c
+++ b/tools/applypatch/imgpatch.c
@@ -27,24 +27,7 @@
 #include "mincrypt/sha.h"
 #include "applypatch.h"
 #include "imgdiff.h"
-
-int Read4(unsigned char* p) {
-  return (int)(((unsigned int)p[3] << 24) |
-               ((unsigned int)p[2] << 16) |
-               ((unsigned int)p[1] << 8) |
-               (unsigned int)p[0]);
-}
-
-long long Read8(unsigned char* p) {
-  return (long long)(((unsigned long long)p[7] << 56) |
-                     ((unsigned long long)p[6] << 48) |
-                     ((unsigned long long)p[5] << 40) |
-                     ((unsigned long long)p[4] << 32) |
-                     ((unsigned long long)p[3] << 24) |
-                     ((unsigned long long)p[2] << 16) |
-                     ((unsigned long long)p[1] << 8) |
-                     (unsigned long long)p[0]);
-}
+#include "utils.h"
 
 /*
  * Apply the patch given in 'patch_filename' to the source data given
@@ -67,7 +50,10 @@ int ApplyImagePatch(const unsigned char* old_data, ssize_t old_size,
     return -1;
   }
 
-  if (memcmp(header, "IMGDIFF1", 8) != 0) {
+  // IMGDIFF1 uses CHUNK_NORMAL and CHUNK_GZIP.
+  // IMGDIFF2 uses CHUNK_NORMAL, CHUNK_DEFLATE, and CHUNK_RAW.
+  if (memcmp(header, "IMGDIFF", 7) != 0 ||
+      (header[7] != '1' && header[7] != '2')) {
     fprintf(stderr, "corrupt patch file header (magic number)\n");
     return -1;
   }
@@ -76,48 +62,67 @@ int ApplyImagePatch(const unsigned char* old_data, ssize_t old_size,
 
   int i;
   for (i = 0; i < num_chunks; ++i) {
-    // each chunk's header record starts with 28 bytes (4 + 8*3).
-    unsigned char chunk[28];
-    if (fread(chunk, 1, 28, f) != 28) {
+    // each chunk's header record starts with 4 bytes.
+    unsigned char chunk[4];
+    if (fread(chunk, 1, 4, f) != 4) {
       fprintf(stderr, "failed to read chunk %d record\n", i);
       return -1;
     }
 
     int type = Read4(chunk);
-    size_t src_start = Read8(chunk+4);
-    size_t src_len = Read8(chunk+12);
-    size_t patch_offset = Read8(chunk+20);
 
     if (type == CHUNK_NORMAL) {
+      unsigned char normal_header[24];
+      if (fread(normal_header, 1, 24, f) != 24) {
+        fprintf(stderr, "failed to read chunk %d normal header data\n", i);
+        return -1;
+      }
+
+      size_t src_start = Read8(normal_header);
+      size_t src_len = Read8(normal_header+8);
+      size_t patch_offset = Read8(normal_header+16);
+
       fprintf(stderr, "CHUNK %d:  normal   patch offset %d\n", i, patch_offset);
 
       ApplyBSDiffPatch(old_data + src_start, src_len,
                        patch_filename, patch_offset,
                        output, ctx);
     } else if (type == CHUNK_GZIP) {
-      fprintf(stderr, "CHUNK %d:  gzip     patch offset %d\n", i, patch_offset);
+      // This branch is basically a duplicate of the CHUNK_DEFLATE
+      // branch, with a bit of extra processing for the gzip header
+      // and footer.  I've avoided factoring the common code out since
+      // this branch will just be deleted when we drop support for
+      // IMGDIFF1.
 
-      // gzip chunks have an additional 40 + gzip_header_len + 8 bytes
+      // gzip chunks have an additional 64 + gzip_header_len + 8 bytes
       // in their chunk header.
-      unsigned char* gzip = malloc(40);
-      if (fread(gzip, 1, 40, f) != 40) {
-        fprintf(stderr, "failed to read chunk %d initial gzip data\n", i);
+      unsigned char* gzip = malloc(64);
+      if (fread(gzip, 1, 64, f) != 64) {
+        fprintf(stderr, "failed to read chunk %d initial gzip header data\n",
+                i);
         return -1;
       }
-      size_t gzip_header_len = Read4(gzip+36);
-      gzip = realloc(gzip, 40 + gzip_header_len + 8);
-      if (fread(gzip+40, 1, gzip_header_len+8, f) != gzip_header_len+8) {
-        fprintf(stderr, "failed to read chunk %d remaining gzip data\n", i);
+      size_t gzip_header_len = Read4(gzip+60);
+      gzip = realloc(gzip, 64 + gzip_header_len + 8);
+      if (fread(gzip+64, 1, gzip_header_len+8, f) != gzip_header_len+8) {
+        fprintf(stderr, "failed to read chunk %d remaining gzip header data\n",
+                i);
         return -1;
       }
 
-      size_t expanded_len = Read8(gzip);
-      size_t target_len = Read8(gzip);
-      int gz_level = Read4(gzip+16);
-      int gz_method = Read4(gzip+20);
-      int gz_windowBits = Read4(gzip+24);
-      int gz_memLevel = Read4(gzip+28);
-      int gz_strategy = Read4(gzip+32);
+      size_t src_start = Read8(gzip);
+      size_t src_len = Read8(gzip+8);
+      size_t patch_offset = Read8(gzip+16);
+
+      size_t expanded_len = Read8(gzip+24);
+      size_t target_len = Read8(gzip+32);
+      int gz_level = Read4(gzip+40);
+      int gz_method = Read4(gzip+44);
+      int gz_windowBits = Read4(gzip+48);
+      int gz_memLevel = Read4(gzip+52);
+      int gz_strategy = Read4(gzip+56);
+
+      fprintf(stderr, "CHUNK %d:  gzip     patch offset %d\n", i, patch_offset);
 
       // Decompress the source data; the chunk header tells us exactly
       // how big we expect it to be when decompressed.
@@ -173,8 +178,8 @@ int ApplyImagePatch(const unsigned char* old_data, ssize_t old_size,
       // Now compress the target data and append it to the output.
 
       // start with the gzip header.
-      fwrite(gzip+40, 1, gzip_header_len, output);
-      SHA_update(ctx, gzip+40, gzip_header_len);
+      fwrite(gzip+64, 1, gzip_header_len, output);
+      SHA_update(ctx, gzip+64, gzip_header_len);
 
       // we're done with the expanded_source data buffer, so we'll
       // reuse that memory to receive the output of deflate.
@@ -212,12 +217,143 @@ int ApplyImagePatch(const unsigned char* old_data, ssize_t old_size,
       deflateEnd(&strm);
 
       // lastly, the gzip footer.
-      fwrite(gzip+40+gzip_header_len, 1, 8, output);
-      SHA_update(ctx, gzip+40+gzip_header_len, 8);
+      fwrite(gzip+64+gzip_header_len, 1, 8, output);
+      SHA_update(ctx, gzip+64+gzip_header_len, 8);
 
       free(temp_data);
       free(uncompressed_target_data);
       free(gzip);
+    } else if (type == CHUNK_RAW) {
+      unsigned char raw_header[4];
+      if (fread(raw_header, 1, 4, f) != 4) {
+        fprintf(stderr, "failed to read chunk %d raw header data\n", i);
+        return -1;
+      }
+
+      size_t data_len = Read4(raw_header);
+
+      fprintf(stderr, "CHUNK %d:  raw      data %d\n", i, data_len);
+
+      unsigned char* temp = malloc(data_len);
+      if (fread(temp, 1, data_len, f) != data_len) {
+          fprintf(stderr, "failed to read chunk %d raw data\n", i);
+          return -1;
+      }
+      SHA_update(ctx, temp, data_len);
+      if (fwrite(temp, 1, data_len, output) != data_len) {
+          fprintf(stderr, "failed to write chunk %d raw data\n", i);
+          return -1;
+      }
+    } else if (type == CHUNK_DEFLATE) {
+      // deflate chunks have an additional 60 bytes in their chunk header.
+      unsigned char deflate_header[60];
+      if (fread(deflate_header, 1, 60, f) != 60) {
+        fprintf(stderr, "failed to read chunk %d deflate header data\n", i);
+        return -1;
+      }
+
+      size_t src_start = Read8(deflate_header);
+      size_t src_len = Read8(deflate_header+8);
+      size_t patch_offset = Read8(deflate_header+16);
+      size_t expanded_len = Read8(deflate_header+24);
+      size_t target_len = Read8(deflate_header+32);
+      int level = Read4(deflate_header+40);
+      int method = Read4(deflate_header+44);
+      int windowBits = Read4(deflate_header+48);
+      int memLevel = Read4(deflate_header+52);
+      int strategy = Read4(deflate_header+56);
+
+      fprintf(stderr, "CHUNK %d:  deflate  patch offset %d\n", i, patch_offset);
+
+      // Decompress the source data; the chunk header tells us exactly
+      // how big we expect it to be when decompressed.
+
+      unsigned char* expanded_source = malloc(expanded_len);
+      if (expanded_source == NULL) {
+        fprintf(stderr, "failed to allocate %d bytes for expanded_source\n",
+                expanded_len);
+        return -1;
+      }
+
+      z_stream strm;
+      strm.zalloc = Z_NULL;
+      strm.zfree = Z_NULL;
+      strm.opaque = Z_NULL;
+      strm.avail_in = src_len;
+      strm.next_in = (unsigned char*)(old_data + src_start);
+      strm.avail_out = expanded_len;
+      strm.next_out = expanded_source;
+
+      int ret;
+      ret = inflateInit2(&strm, -15);
+      if (ret != Z_OK) {
+        fprintf(stderr, "failed to init source inflation: %d\n", ret);
+        return -1;
+      }
+
+      // Because we've provided enough room to accommodate the output
+      // data, we expect one call to inflate() to suffice.
+      ret = inflate(&strm, Z_SYNC_FLUSH);
+      if (ret != Z_STREAM_END) {
+        fprintf(stderr, "source inflation returned %d\n", ret);
+        return -1;
+      }
+      // We should have filled the output buffer exactly.
+      if (strm.avail_out != 0) {
+        fprintf(stderr, "source inflation short by %d bytes\n", strm.avail_out);
+        return -1;
+      }
+      inflateEnd(&strm);
+
+      // Next, apply the bsdiff patch (in memory) to the uncompressed
+      // data.
+      unsigned char* uncompressed_target_data;
+      ssize_t uncompressed_target_size;
+      if (ApplyBSDiffPatchMem(expanded_source, expanded_len,
+                              patch_filename, patch_offset,
+                              &uncompressed_target_data,
+                              &uncompressed_target_size) != 0) {
+        return -1;
+      }
+
+      // Now compress the target data and append it to the output.
+
+      // we're done with the expanded_source data buffer, so we'll
+      // reuse that memory to receive the output of deflate.
+      unsigned char* temp_data = expanded_source;
+      ssize_t temp_size = expanded_len;
+      if (temp_size < 32768) {
+        // ... unless the buffer is too small, in which case we'll
+        // allocate a fresh one.
+        free(temp_data);
+        temp_data = malloc(32768);
+        temp_size = 32768;
+      }
+
+      // now the deflate stream
+      strm.zalloc = Z_NULL;
+      strm.zfree = Z_NULL;
+      strm.opaque = Z_NULL;
+      strm.avail_in = uncompressed_target_size;
+      strm.next_in = uncompressed_target_data;
+      ret = deflateInit2(&strm, level, method, windowBits, memLevel, strategy);
+      do {
+        strm.avail_out = temp_size;
+        strm.next_out = temp_data;
+        ret = deflate(&strm, Z_FINISH);
+        size_t have = temp_size - strm.avail_out;
+
+        if (fwrite(temp_data, 1, have, output) != have) {
+          fprintf(stderr, "failed to write %d compressed bytes to output\n",
+                  have);
+          return -1;
+        }
+        SHA_update(ctx, temp_data, have);
+      } while (ret != Z_STREAM_END);
+      deflateEnd(&strm);
+
+      free(temp_data);
+      free(uncompressed_target_data);
     } else {
       fprintf(stderr, "patch chunk %d is unknown type %d\n", i, type);
       return -1;
diff --git a/tools/applypatch/utils.c b/tools/applypatch/utils.c
new file mode 100644
index 0000000..912229b
--- /dev/null
+++ b/tools/applypatch/utils.c
@@ -0,0 +1,62 @@
+/*
+ * Copyright (C) 2009 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <stdio.h>
+
+#include "utils.h"
+
+/** Write a 4-byte value to f in little-endian order. */
+void Write4(int value, FILE* f) {
+  fputc(value & 0xff, f);
+  fputc((value >> 8) & 0xff, f);
+  fputc((value >> 16) & 0xff, f);
+  fputc((value >> 24) & 0xff, f);
+}
+
+/** Write an 8-byte value to f in little-endian order. */
+void Write8(long long value, FILE* f) {
+  fputc(value & 0xff, f);
+  fputc((value >> 8) & 0xff, f);
+  fputc((value >> 16) & 0xff, f);
+  fputc((value >> 24) & 0xff, f);
+  fputc((value >> 32) & 0xff, f);
+  fputc((value >> 40) & 0xff, f);
+  fputc((value >> 48) & 0xff, f);
+  fputc((value >> 56) & 0xff, f);
+}
+
+int Read2(unsigned char* p) {
+  return (int)(((unsigned int)p[1] << 8) |
+               (unsigned int)p[0]);
+}
+
+int Read4(unsigned char* p) {
+  return (int)(((unsigned int)p[3] << 24) |
+               ((unsigned int)p[2] << 16) |
+               ((unsigned int)p[1] << 8) |
+               (unsigned int)p[0]);
+}
+
+long long Read8(unsigned char* p) {
+  return (long long)(((unsigned long long)p[7] << 56) |
+                     ((unsigned long long)p[6] << 48) |
+                     ((unsigned long long)p[5] << 40) |
+                     ((unsigned long long)p[4] << 32) |
+                     ((unsigned long long)p[3] << 24) |
+                     ((unsigned long long)p[2] << 16) |
+                     ((unsigned long long)p[1] << 8) |
+                     (unsigned long long)p[0]);
+}
diff --git a/tools/applypatch/utils.h b/tools/applypatch/utils.h
new file mode 100644
index 0000000..d6d6f1d
--- /dev/null
+++ b/tools/applypatch/utils.h
@@ -0,0 +1,30 @@
+/*
+ * Copyright (C) 2009 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef _BUILD_TOOLS_APPLYPATCH_UTILS_H
+#define _BUILD_TOOLS_APPLYPATCH_UTILS_H
+
+#include <stdio.h>
+
+// Read and write little-endian values of various sizes.
+
+void Write4(int value, FILE* f);
+void Write8(long long value, FILE* f);
+int Read2(unsigned char* p);
+int Read4(unsigned char* p);
+long long Read8(unsigned char* p);
+
+#endif //  _BUILD_TOOLS_APPLYPATCH_UTILS_H