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.

1 files changed, 181 insertions, 45 deletions

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;