From 930edb666122d04ffb6a1ff1648181d5b08dda84 Mon Sep 17 00:00:00 2001
From: Sen Jiang <senj@google.com>
Date: Wed, 18 Jan 2017 17:26:42 -0800
Subject: imgdiff: cache bsdiff suffix array in zip mode.

In zip mode, if a chunk is not deflate or its filename can't be found
in source chunks, the entire source file is used as old data for bsdiff,
To avoid repeatedly construct the suffix array used by bsdiff, we cache
the suffix array of the entire source file.

Bug: 34281147
Test: =time -v imgdiff -z Chrome-ORF74B.apk Chrome-ORF76B.apk Chrome.imgdiff
Change-Id: Ifd957ccecf7226fcb44dbf28c58969a06ef74f4b
---
 applypatch/Android.mk  |  6 +++---
 applypatch/imgdiff.cpp | 30 +++++++++++++++++-------------
 2 files changed, 20 insertions(+), 16 deletions(-)

diff --git a/applypatch/Android.mk b/applypatch/Android.mk
index ec3c6ee38..85b5c9fcd 100644
--- a/applypatch/Android.mk
+++ b/applypatch/Android.mk
@@ -124,6 +124,8 @@ libimgdiff_cflags := \
 
 libimgdiff_static_libraries := \
     libbsdiff \
+    libdivsufsort \
+    libdivsufsort64 \
     libbase \
     libz
 
@@ -166,7 +168,5 @@ LOCAL_CFLAGS := -Werror
 LOCAL_STATIC_LIBRARIES := \
     libimgdiff \
     $(libimgdiff_static_libraries) \
-    libbz \
-    libdivsufsort \
-    libdivsufsort64
+    libbz
 include $(BUILD_HOST_EXECUTABLE)
diff --git a/applypatch/imgdiff.cpp b/applypatch/imgdiff.cpp
index 62de726a4..395150614 100644
--- a/applypatch/imgdiff.cpp
+++ b/applypatch/imgdiff.cpp
@@ -615,12 +615,12 @@ int ReconstructDeflateChunk(ImageChunk* chunk) {
 }
 
 /*
- * Given source and target chunks, compute a bsdiff patch between them
- * by running bsdiff in a subprocess.  Return the patch data, placing
- * its length in *size.  Return NULL on failure.  We expect the bsdiff
- * program to be in the path.
+ * Given source and target chunks, compute a bsdiff patch between them.
+ * Return the patch data, placing its length in *size. Return NULL on failure.
+ * |bsdiff_cache| can be used to cache the suffix array if the same |src| chunk
+ * is used repeatedly, pass nullptr if not needed.
  */
-unsigned char* MakePatch(ImageChunk* src, ImageChunk* tgt, size_t* size) {
+unsigned char* MakePatch(ImageChunk* src, ImageChunk* tgt, size_t* size, saidx_t** bsdiff_cache) {
   if (tgt->type == CHUNK_NORMAL) {
     if (tgt->len <= 160) {
       tgt->type = CHUNK_RAW;
@@ -644,7 +644,7 @@ unsigned char* MakePatch(ImageChunk* src, ImageChunk* tgt, size_t* size) {
   close(fd); // temporary file is created and we don't need its file
              // descriptor
 
-  int r = bsdiff::bsdiff(src->data, src->len, tgt->data, tgt->len, ptemp);
+  int r = bsdiff::bsdiff(src->data, src->len, tgt->data, tgt->len, ptemp, bsdiff_cache);
   if (r != 0) {
     printf("bsdiff() failed: %d\n", r);
     return NULL;
@@ -970,28 +970,31 @@ int imgdiff(int argc, const char** argv) {
   unsigned char** patch_data = static_cast<unsigned char**>(malloc(
       num_tgt_chunks * sizeof(unsigned char*)));
   size_t* patch_size = static_cast<size_t*>(malloc(num_tgt_chunks * sizeof(size_t)));
+  saidx_t* bsdiff_cache = nullptr;
   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);
+        patch_data[i] = MakePatch(src, tgt_chunks + i, patch_size + i, nullptr);
       } else {
-        patch_data[i] = MakePatch(src_chunks, tgt_chunks+i, patch_size+i);
+        patch_data[i] = MakePatch(src_chunks, tgt_chunks + i, patch_size + i, &bsdiff_cache);
       }
     } else {
       if (i == 1 && bonus_data) {
         printf("  using %zu bytes of bonus data for chunk %d\n", bonus_size, i);
-        src_chunks[i].data = static_cast<unsigned char*>(realloc(src_chunks[i].data,
-            src_chunks[i].len + bonus_size));
-        memcpy(src_chunks[i].data+src_chunks[i].len, bonus_data, bonus_size);
+        src_chunks[i].data =
+            static_cast<unsigned char*>(realloc(src_chunks[i].data, src_chunks[i].len + bonus_size));
+        memcpy(src_chunks[i].data + src_chunks[i].len, bonus_data, bonus_size);
         src_chunks[i].len += bonus_size;
-     }
+      }
 
-      patch_data[i] = MakePatch(src_chunks+i, tgt_chunks+i, patch_size+i);
+      patch_data[i] = MakePatch(src_chunks + i, tgt_chunks + i, patch_size + i, nullptr);
     }
     printf("patch %3d is %zu bytes (of %zu)\n", i, patch_size[i], tgt_chunks[i].source_len);
   }
+  free(bsdiff_cache);
+  free(src_chunks);
 
   // Figure out how big the imgdiff file header is going to be, so
   // that we can correctly compute the offset of each bsdiff patch
@@ -1068,6 +1071,7 @@ int imgdiff(int argc, const char** argv) {
     }
   }
 
+  free(tgt_chunks);
   free(patch_data);
   free(patch_size);
 
-- 
cgit v1.2.3