Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 1 | /* |
| 2 | * Copyright (C) 2009 The Android Open Source Project |
| 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
| 17 | /* |
| 18 | * This program constructs binary patches for images -- such as boot.img |
| 19 | * and recovery.img -- that consist primarily of large chunks of gzipped |
| 20 | * data interspersed with uncompressed data. Doing a naive bsdiff of |
| 21 | * these files is not useful because small changes in the data lead to |
| 22 | * large changes in the compressed bitstream; bsdiff patches of gzipped |
| 23 | * data are typically as large as the data itself. |
| 24 | * |
| 25 | * To patch these usefully, we break the source and target images up into |
| 26 | * chunks of two types: "normal" and "gzip". Normal chunks are simply |
| 27 | * patched using a plain bsdiff. Gzip chunks are first expanded, then a |
| 28 | * bsdiff is applied to the uncompressed data, then the patched data is |
| 29 | * gzipped using the same encoder parameters. Patched chunks are |
| 30 | * concatenated together to create the output file; the output image |
| 31 | * should be *exactly* the same series of bytes as the target image used |
| 32 | * originally to generate the patch. |
| 33 | * |
| 34 | * To work well with this tool, the gzipped sections of the target |
| 35 | * image must have been generated using the same deflate encoder that |
| 36 | * is available in applypatch, namely, the one in the zlib library. |
| 37 | * In practice this means that images should be compressed using the |
| 38 | * "minigzip" tool included in the zlib distribution, not the GNU gzip |
| 39 | * program. |
| 40 | * |
| 41 | * An "imgdiff" patch consists of a header describing the chunk structure |
| 42 | * of the file and any encoding parameters needed for the gzipped |
| 43 | * chunks, followed by N bsdiff patches, one per chunk. |
| 44 | * |
| 45 | * For a diff to be generated, the source and target images must have the |
| 46 | * same "chunk" structure: that is, the same number of gzipped and normal |
| 47 | * chunks in the same order. Android boot and recovery images currently |
| 48 | * consist of five chunks: a small normal header, a gzipped kernel, a |
| 49 | * small normal section, a gzipped ramdisk, and finally a small normal |
| 50 | * footer. |
| 51 | * |
| 52 | * Caveats: we locate gzipped sections within the source and target |
| 53 | * images by searching for the byte sequence 1f8b0800: 1f8b is the gzip |
| 54 | * magic number; 08 specifies the "deflate" encoding [the only encoding |
| 55 | * supported by the gzip standard]; and 00 is the flags byte. We do not |
| 56 | * currently support any extra header fields (which would be indicated by |
| 57 | * a nonzero flags byte). We also don't handle the case when that byte |
| 58 | * sequence appears spuriously in the file. (Note that it would have to |
| 59 | * occur spuriously within a normal chunk to be a problem.) |
| 60 | * |
| 61 | * |
| 62 | * The imgdiff patch header looks like this: |
| 63 | * |
| 64 | * "IMGDIFF1" (8) [magic number and version] |
| 65 | * chunk count (4) |
| 66 | * for each chunk: |
| 67 | * chunk type (4) [CHUNK_{NORMAL, GZIP, DEFLATE, RAW}] |
| 68 | * if chunk type == CHUNK_NORMAL: |
| 69 | * source start (8) |
| 70 | * source len (8) |
| 71 | * bsdiff patch offset (8) [from start of patch file] |
| 72 | * if chunk type == CHUNK_GZIP: (version 1 only) |
| 73 | * source start (8) |
| 74 | * source len (8) |
| 75 | * bsdiff patch offset (8) [from start of patch file] |
| 76 | * source expanded len (8) [size of uncompressed source] |
| 77 | * target expected len (8) [size of uncompressed target] |
| 78 | * gzip level (4) |
| 79 | * method (4) |
| 80 | * windowBits (4) |
| 81 | * memLevel (4) |
| 82 | * strategy (4) |
| 83 | * gzip header len (4) |
| 84 | * gzip header (gzip header len) |
| 85 | * gzip footer (8) |
| 86 | * if chunk type == CHUNK_DEFLATE: (version 2 only) |
| 87 | * source start (8) |
| 88 | * source len (8) |
| 89 | * bsdiff patch offset (8) [from start of patch file] |
| 90 | * source expanded len (8) [size of uncompressed source] |
| 91 | * target expected len (8) [size of uncompressed target] |
| 92 | * gzip level (4) |
| 93 | * method (4) |
| 94 | * windowBits (4) |
| 95 | * memLevel (4) |
| 96 | * strategy (4) |
| 97 | * if chunk type == RAW: (version 2 only) |
| 98 | * target len (4) |
| 99 | * data (target len) |
| 100 | * |
| 101 | * All integers are little-endian. "source start" and "source len" |
| 102 | * specify the section of the input image that comprises this chunk, |
| 103 | * including the gzip header and footer for gzip chunks. "source |
| 104 | * expanded len" is the size of the uncompressed source data. "target |
| 105 | * expected len" is the size of the uncompressed data after applying |
| 106 | * the bsdiff patch. The next five parameters specify the zlib |
| 107 | * parameters to be used when compressing the patched data, and the |
| 108 | * next three specify the header and footer to be wrapped around the |
| 109 | * compressed data to create the output chunk (so that header contents |
| 110 | * like the timestamp are recreated exactly). |
| 111 | * |
| 112 | * After the header there are 'chunk count' bsdiff patches; the offset |
| 113 | * of each from the beginning of the file is specified in the header. |
Doug Zongker | a3ccba6 | 2012-08-20 15:28:02 -0700 | [diff] [blame] | 114 | * |
| 115 | * This tool can take an optional file of "bonus data". This is an |
| 116 | * extra file of data that is appended to chunk #1 after it is |
| 117 | * compressed (it must be a CHUNK_DEFLATE chunk). The same file must |
| 118 | * be available (and passed to applypatch with -b) when applying the |
| 119 | * patch. This is used to reduce the size of recovery-from-boot |
| 120 | * patches by combining the boot image with recovery ramdisk |
| 121 | * information that is stored on the system partition. |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 122 | */ |
| 123 | |
| 124 | #include <errno.h> |
Tao Bao | ba9a42a | 2015-06-23 23:23:33 -0700 | [diff] [blame] | 125 | #include <inttypes.h> |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 126 | #include <stdio.h> |
| 127 | #include <stdlib.h> |
| 128 | #include <string.h> |
| 129 | #include <sys/stat.h> |
| 130 | #include <unistd.h> |
| 131 | #include <sys/types.h> |
| 132 | |
Sen Jiang | 2fffcb1 | 2016-05-03 15:49:10 -0700 | [diff] [blame] | 133 | #include <bsdiff.h> |
| 134 | |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 135 | #include "zlib.h" |
| 136 | #include "imgdiff.h" |
| 137 | #include "utils.h" |
| 138 | |
| 139 | typedef struct { |
| 140 | int type; // CHUNK_NORMAL, CHUNK_DEFLATE |
| 141 | size_t start; // offset of chunk in original image file |
| 142 | |
| 143 | size_t len; |
| 144 | unsigned char* data; // data to be patched (uncompressed, for deflate chunks) |
| 145 | |
| 146 | size_t source_start; |
| 147 | size_t source_len; |
| 148 | |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 149 | // --- for CHUNK_DEFLATE chunks only: --- |
| 150 | |
| 151 | // original (compressed) deflate data |
| 152 | size_t deflate_len; |
| 153 | unsigned char* deflate_data; |
| 154 | |
| 155 | char* filename; // used for zip entries |
| 156 | |
| 157 | // deflate encoder parameters |
| 158 | int level, method, windowBits, memLevel, strategy; |
| 159 | |
| 160 | size_t source_uncompressed_len; |
| 161 | } ImageChunk; |
| 162 | |
| 163 | typedef struct { |
| 164 | int data_offset; |
| 165 | int deflate_len; |
| 166 | int uncomp_len; |
| 167 | char* filename; |
| 168 | } ZipFileEntry; |
| 169 | |
Tao Bao | 65f98cb | 2016-06-01 21:40:20 +0000 | [diff] [blame] | 170 | static int fileentry_compare(const void* a, const void* b) { |
| 171 | int ao = ((ZipFileEntry*)a)->data_offset; |
| 172 | int bo = ((ZipFileEntry*)b)->data_offset; |
| 173 | if (ao < bo) { |
| 174 | return -1; |
| 175 | } else if (ao > bo) { |
| 176 | return 1; |
| 177 | } else { |
| 178 | return 0; |
| 179 | } |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 180 | } |
| 181 | |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 182 | unsigned char* ReadZip(const char* filename, |
| 183 | int* num_chunks, ImageChunk** chunks, |
| 184 | int include_pseudo_chunk) { |
| 185 | struct stat st; |
| 186 | if (stat(filename, &st) != 0) { |
| 187 | printf("failed to stat \"%s\": %s\n", filename, strerror(errno)); |
| 188 | return NULL; |
| 189 | } |
| 190 | |
Tao Bao | ba9a42a | 2015-06-23 23:23:33 -0700 | [diff] [blame] | 191 | size_t sz = static_cast<size_t>(st.st_size); |
Rahul Chaudhry | 4f7faac | 2016-11-08 16:06:13 -0800 | [diff] [blame^] | 192 | unsigned char* img = static_cast<unsigned char*>(malloc(sz)); |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 193 | FILE* f = fopen(filename, "rb"); |
Tao Bao | 65f98cb | 2016-06-01 21:40:20 +0000 | [diff] [blame] | 194 | if (fread(img, 1, sz, f) != sz) { |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 195 | printf("failed to read \"%s\" %s\n", filename, strerror(errno)); |
| 196 | fclose(f); |
| 197 | return NULL; |
| 198 | } |
| 199 | fclose(f); |
| 200 | |
| 201 | // look for the end-of-central-directory record. |
| 202 | |
| 203 | int i; |
| 204 | for (i = st.st_size-20; i >= 0 && i > st.st_size - 65600; --i) { |
| 205 | if (img[i] == 0x50 && img[i+1] == 0x4b && |
| 206 | img[i+2] == 0x05 && img[i+3] == 0x06) { |
| 207 | break; |
| 208 | } |
| 209 | } |
| 210 | // double-check: this archive consists of a single "disk" |
| 211 | if (!(img[i+4] == 0 && img[i+5] == 0 && img[i+6] == 0 && img[i+7] == 0)) { |
| 212 | printf("can't process multi-disk archive\n"); |
| 213 | return NULL; |
| 214 | } |
| 215 | |
Tao Bao | 65f98cb | 2016-06-01 21:40:20 +0000 | [diff] [blame] | 216 | int cdcount = Read2(img+i+8); |
| 217 | int cdoffset = Read4(img+i+16); |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 218 | |
Rahul Chaudhry | 4f7faac | 2016-11-08 16:06:13 -0800 | [diff] [blame^] | 219 | ZipFileEntry* temp_entries = static_cast<ZipFileEntry*>(malloc( |
Tao Bao | 65f98cb | 2016-06-01 21:40:20 +0000 | [diff] [blame] | 220 | cdcount * sizeof(ZipFileEntry))); |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 221 | int entrycount = 0; |
| 222 | |
Tao Bao | 65f98cb | 2016-06-01 21:40:20 +0000 | [diff] [blame] | 223 | unsigned char* cd = img+cdoffset; |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 224 | for (i = 0; i < cdcount; ++i) { |
| 225 | if (!(cd[0] == 0x50 && cd[1] == 0x4b && cd[2] == 0x01 && cd[3] == 0x02)) { |
| 226 | printf("bad central directory entry %d\n", i); |
| 227 | return NULL; |
| 228 | } |
| 229 | |
| 230 | int clen = Read4(cd+20); // compressed len |
| 231 | int ulen = Read4(cd+24); // uncompressed len |
| 232 | int nlen = Read2(cd+28); // filename len |
| 233 | int xlen = Read2(cd+30); // extra field len |
| 234 | int mlen = Read2(cd+32); // file comment len |
| 235 | int hoffset = Read4(cd+42); // local header offset |
| 236 | |
Rahul Chaudhry | 4f7faac | 2016-11-08 16:06:13 -0800 | [diff] [blame^] | 237 | char* filename = static_cast<char*>(malloc(nlen+1)); |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 238 | memcpy(filename, cd+46, nlen); |
| 239 | filename[nlen] = '\0'; |
| 240 | |
| 241 | int method = Read2(cd+10); |
| 242 | |
| 243 | cd += 46 + nlen + xlen + mlen; |
| 244 | |
| 245 | if (method != 8) { // 8 == deflate |
| 246 | free(filename); |
| 247 | continue; |
| 248 | } |
| 249 | |
Tao Bao | 65f98cb | 2016-06-01 21:40:20 +0000 | [diff] [blame] | 250 | unsigned char* lh = img + hoffset; |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 251 | |
| 252 | if (!(lh[0] == 0x50 && lh[1] == 0x4b && lh[2] == 0x03 && lh[3] == 0x04)) { |
| 253 | printf("bad local file header entry %d\n", i); |
| 254 | return NULL; |
| 255 | } |
| 256 | |
| 257 | if (Read2(lh+26) != nlen || memcmp(lh+30, filename, nlen) != 0) { |
| 258 | printf("central dir filename doesn't match local header\n"); |
| 259 | return NULL; |
| 260 | } |
| 261 | |
| 262 | xlen = Read2(lh+28); // extra field len; might be different from CD entry? |
| 263 | |
| 264 | temp_entries[entrycount].data_offset = hoffset+30+nlen+xlen; |
| 265 | temp_entries[entrycount].deflate_len = clen; |
| 266 | temp_entries[entrycount].uncomp_len = ulen; |
| 267 | temp_entries[entrycount].filename = filename; |
| 268 | ++entrycount; |
| 269 | } |
| 270 | |
Tao Bao | 65f98cb | 2016-06-01 21:40:20 +0000 | [diff] [blame] | 271 | qsort(temp_entries, entrycount, sizeof(ZipFileEntry), fileentry_compare); |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 272 | |
| 273 | #if 0 |
| 274 | printf("found %d deflated entries\n", entrycount); |
| 275 | for (i = 0; i < entrycount; ++i) { |
| 276 | printf("off %10d len %10d unlen %10d %p %s\n", |
| 277 | temp_entries[i].data_offset, |
| 278 | temp_entries[i].deflate_len, |
| 279 | temp_entries[i].uncomp_len, |
| 280 | temp_entries[i].filename, |
| 281 | temp_entries[i].filename); |
| 282 | } |
| 283 | #endif |
| 284 | |
| 285 | *num_chunks = 0; |
Rahul Chaudhry | 4f7faac | 2016-11-08 16:06:13 -0800 | [diff] [blame^] | 286 | *chunks = static_cast<ImageChunk*>(malloc((entrycount*2+2) * sizeof(ImageChunk))); |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 287 | ImageChunk* curr = *chunks; |
| 288 | |
| 289 | if (include_pseudo_chunk) { |
| 290 | curr->type = CHUNK_NORMAL; |
| 291 | curr->start = 0; |
| 292 | curr->len = st.st_size; |
Tao Bao | 65f98cb | 2016-06-01 21:40:20 +0000 | [diff] [blame] | 293 | curr->data = img; |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 294 | curr->filename = NULL; |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 295 | ++curr; |
| 296 | ++*num_chunks; |
| 297 | } |
| 298 | |
| 299 | int pos = 0; |
| 300 | int nextentry = 0; |
| 301 | |
| 302 | while (pos < st.st_size) { |
| 303 | if (nextentry < entrycount && pos == temp_entries[nextentry].data_offset) { |
| 304 | curr->type = CHUNK_DEFLATE; |
| 305 | curr->start = pos; |
| 306 | curr->deflate_len = temp_entries[nextentry].deflate_len; |
Tao Bao | 65f98cb | 2016-06-01 21:40:20 +0000 | [diff] [blame] | 307 | curr->deflate_data = img + pos; |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 308 | curr->filename = temp_entries[nextentry].filename; |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 309 | |
| 310 | curr->len = temp_entries[nextentry].uncomp_len; |
Rahul Chaudhry | 4f7faac | 2016-11-08 16:06:13 -0800 | [diff] [blame^] | 311 | curr->data = static_cast<unsigned char*>(malloc(curr->len)); |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 312 | |
| 313 | z_stream strm; |
| 314 | strm.zalloc = Z_NULL; |
| 315 | strm.zfree = Z_NULL; |
| 316 | strm.opaque = Z_NULL; |
| 317 | strm.avail_in = curr->deflate_len; |
| 318 | strm.next_in = curr->deflate_data; |
| 319 | |
| 320 | // -15 means we are decoding a 'raw' deflate stream; zlib will |
| 321 | // not expect zlib headers. |
| 322 | int ret = inflateInit2(&strm, -15); |
| 323 | |
| 324 | strm.avail_out = curr->len; |
| 325 | strm.next_out = curr->data; |
| 326 | ret = inflate(&strm, Z_NO_FLUSH); |
| 327 | if (ret != Z_STREAM_END) { |
| 328 | printf("failed to inflate \"%s\"; %d\n", curr->filename, ret); |
| 329 | return NULL; |
| 330 | } |
| 331 | |
| 332 | inflateEnd(&strm); |
| 333 | |
| 334 | pos += curr->deflate_len; |
| 335 | ++nextentry; |
| 336 | ++*num_chunks; |
| 337 | ++curr; |
| 338 | continue; |
| 339 | } |
| 340 | |
| 341 | // use a normal chunk to take all the data up to the start of the |
| 342 | // next deflate section. |
| 343 | |
| 344 | curr->type = CHUNK_NORMAL; |
| 345 | curr->start = pos; |
| 346 | if (nextentry < entrycount) { |
| 347 | curr->len = temp_entries[nextentry].data_offset - pos; |
| 348 | } else { |
| 349 | curr->len = st.st_size - pos; |
| 350 | } |
Tao Bao | 65f98cb | 2016-06-01 21:40:20 +0000 | [diff] [blame] | 351 | curr->data = img + pos; |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 352 | curr->filename = NULL; |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 353 | pos += curr->len; |
| 354 | |
| 355 | ++*num_chunks; |
| 356 | ++curr; |
| 357 | } |
| 358 | |
Tao Bao | 65f98cb | 2016-06-01 21:40:20 +0000 | [diff] [blame] | 359 | free(temp_entries); |
| 360 | return img; |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 361 | } |
| 362 | |
| 363 | /* |
| 364 | * Read the given file and break it up into chunks, putting the number |
| 365 | * of chunks and their info in *num_chunks and **chunks, |
| 366 | * respectively. Returns a malloc'd block of memory containing the |
| 367 | * contents of the file; various pointers in the output chunk array |
| 368 | * will point into this block of memory. The caller should free the |
| 369 | * return value when done with all the chunks. Returns NULL on |
| 370 | * failure. |
| 371 | */ |
| 372 | unsigned char* ReadImage(const char* filename, |
| 373 | int* num_chunks, ImageChunk** chunks) { |
| 374 | struct stat st; |
| 375 | if (stat(filename, &st) != 0) { |
| 376 | printf("failed to stat \"%s\": %s\n", filename, strerror(errno)); |
| 377 | return NULL; |
| 378 | } |
| 379 | |
Tao Bao | ba9a42a | 2015-06-23 23:23:33 -0700 | [diff] [blame] | 380 | size_t sz = static_cast<size_t>(st.st_size); |
Rahul Chaudhry | 4f7faac | 2016-11-08 16:06:13 -0800 | [diff] [blame^] | 381 | unsigned char* img = static_cast<unsigned char*>(malloc(sz + 4)); |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 382 | FILE* f = fopen(filename, "rb"); |
Tao Bao | 65f98cb | 2016-06-01 21:40:20 +0000 | [diff] [blame] | 383 | if (fread(img, 1, sz, f) != sz) { |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 384 | printf("failed to read \"%s\" %s\n", filename, strerror(errno)); |
| 385 | fclose(f); |
| 386 | return NULL; |
| 387 | } |
| 388 | fclose(f); |
| 389 | |
| 390 | // append 4 zero bytes to the data so we can always search for the |
| 391 | // four-byte string 1f8b0800 starting at any point in the actual |
| 392 | // file data, without special-casing the end of the data. |
Tao Bao | 65f98cb | 2016-06-01 21:40:20 +0000 | [diff] [blame] | 393 | memset(img+sz, 0, 4); |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 394 | |
| 395 | size_t pos = 0; |
| 396 | |
| 397 | *num_chunks = 0; |
| 398 | *chunks = NULL; |
| 399 | |
Tao Bao | ba9a42a | 2015-06-23 23:23:33 -0700 | [diff] [blame] | 400 | while (pos < sz) { |
Tao Bao | 65f98cb | 2016-06-01 21:40:20 +0000 | [diff] [blame] | 401 | unsigned char* p = img+pos; |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 402 | |
Tao Bao | ba9a42a | 2015-06-23 23:23:33 -0700 | [diff] [blame] | 403 | if (sz - pos >= 4 && |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 404 | p[0] == 0x1f && p[1] == 0x8b && |
| 405 | p[2] == 0x08 && // deflate compression |
| 406 | p[3] == 0x00) { // no header flags |
| 407 | // 'pos' is the offset of the start of a gzip chunk. |
Johan Redestig | c68bd34 | 2015-04-14 21:20:06 +0200 | [diff] [blame] | 408 | size_t chunk_offset = pos; |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 409 | |
| 410 | *num_chunks += 3; |
Rahul Chaudhry | 4f7faac | 2016-11-08 16:06:13 -0800 | [diff] [blame^] | 411 | *chunks = static_cast<ImageChunk*>(realloc(*chunks, |
Tao Bao | ba9a42a | 2015-06-23 23:23:33 -0700 | [diff] [blame] | 412 | *num_chunks * sizeof(ImageChunk))); |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 413 | ImageChunk* curr = *chunks + (*num_chunks-3); |
| 414 | |
| 415 | // create a normal chunk for the header. |
| 416 | curr->start = pos; |
| 417 | curr->type = CHUNK_NORMAL; |
| 418 | curr->len = GZIP_HEADER_LEN; |
| 419 | curr->data = p; |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 420 | |
| 421 | pos += curr->len; |
| 422 | p += curr->len; |
| 423 | ++curr; |
| 424 | |
| 425 | curr->type = CHUNK_DEFLATE; |
| 426 | curr->filename = NULL; |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 427 | |
| 428 | // We must decompress this chunk in order to discover where it |
| 429 | // ends, and so we can put the uncompressed data and its length |
| 430 | // into curr->data and curr->len. |
| 431 | |
| 432 | size_t allocated = 32768; |
| 433 | curr->len = 0; |
Rahul Chaudhry | 4f7faac | 2016-11-08 16:06:13 -0800 | [diff] [blame^] | 434 | curr->data = static_cast<unsigned char*>(malloc(allocated)); |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 435 | curr->start = pos; |
| 436 | curr->deflate_data = p; |
| 437 | |
| 438 | z_stream strm; |
| 439 | strm.zalloc = Z_NULL; |
| 440 | strm.zfree = Z_NULL; |
| 441 | strm.opaque = Z_NULL; |
Tao Bao | ba9a42a | 2015-06-23 23:23:33 -0700 | [diff] [blame] | 442 | strm.avail_in = sz - pos; |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 443 | strm.next_in = p; |
| 444 | |
| 445 | // -15 means we are decoding a 'raw' deflate stream; zlib will |
| 446 | // not expect zlib headers. |
| 447 | int ret = inflateInit2(&strm, -15); |
| 448 | |
| 449 | do { |
| 450 | strm.avail_out = allocated - curr->len; |
| 451 | strm.next_out = curr->data + curr->len; |
| 452 | ret = inflate(&strm, Z_NO_FLUSH); |
Johan Redestig | c68bd34 | 2015-04-14 21:20:06 +0200 | [diff] [blame] | 453 | if (ret < 0) { |
Sen Jiang | fa4f1b7 | 2016-02-11 16:14:23 -0800 | [diff] [blame] | 454 | printf("Warning: inflate failed [%s] at offset [%zu]," |
| 455 | " treating as a normal chunk\n", |
David Riley | 0779fc9 | 2015-12-10 10:18:25 -0800 | [diff] [blame] | 456 | strm.msg, chunk_offset); |
Sen Jiang | fa4f1b7 | 2016-02-11 16:14:23 -0800 | [diff] [blame] | 457 | break; |
Johan Redestig | c68bd34 | 2015-04-14 21:20:06 +0200 | [diff] [blame] | 458 | } |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 459 | curr->len = allocated - strm.avail_out; |
| 460 | if (strm.avail_out == 0) { |
| 461 | allocated *= 2; |
Rahul Chaudhry | 4f7faac | 2016-11-08 16:06:13 -0800 | [diff] [blame^] | 462 | curr->data = static_cast<unsigned char*>(realloc(curr->data, allocated)); |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 463 | } |
| 464 | } while (ret != Z_STREAM_END); |
| 465 | |
Tao Bao | ba9a42a | 2015-06-23 23:23:33 -0700 | [diff] [blame] | 466 | curr->deflate_len = sz - strm.avail_in - pos; |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 467 | inflateEnd(&strm); |
Sen Jiang | fa4f1b7 | 2016-02-11 16:14:23 -0800 | [diff] [blame] | 468 | |
| 469 | if (ret < 0) { |
| 470 | free(curr->data); |
| 471 | *num_chunks -= 2; |
| 472 | continue; |
| 473 | } |
| 474 | |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 475 | pos += curr->deflate_len; |
| 476 | p += curr->deflate_len; |
| 477 | ++curr; |
| 478 | |
| 479 | // create a normal chunk for the footer |
| 480 | |
| 481 | curr->type = CHUNK_NORMAL; |
| 482 | curr->start = pos; |
| 483 | curr->len = GZIP_FOOTER_LEN; |
Tao Bao | 65f98cb | 2016-06-01 21:40:20 +0000 | [diff] [blame] | 484 | curr->data = img+pos; |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 485 | |
| 486 | pos += curr->len; |
| 487 | p += curr->len; |
| 488 | ++curr; |
| 489 | |
| 490 | // The footer (that we just skipped over) contains the size of |
| 491 | // the uncompressed data. Double-check to make sure that it |
| 492 | // matches the size of the data we got when we actually did |
| 493 | // the decompression. |
| 494 | size_t footer_size = Read4(p-4); |
| 495 | if (footer_size != curr[-2].len) { |
Tao Bao | ba9a42a | 2015-06-23 23:23:33 -0700 | [diff] [blame] | 496 | printf("Error: footer size %zu != decompressed size %zu\n", |
| 497 | footer_size, curr[-2].len); |
Tao Bao | 65f98cb | 2016-06-01 21:40:20 +0000 | [diff] [blame] | 498 | free(img); |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 499 | return NULL; |
| 500 | } |
| 501 | } else { |
| 502 | // Reallocate the list for every chunk; we expect the number of |
| 503 | // chunks to be small (5 for typical boot and recovery images). |
| 504 | ++*num_chunks; |
Rahul Chaudhry | 4f7faac | 2016-11-08 16:06:13 -0800 | [diff] [blame^] | 505 | *chunks = static_cast<ImageChunk*>(realloc(*chunks, *num_chunks * sizeof(ImageChunk))); |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 506 | ImageChunk* curr = *chunks + (*num_chunks-1); |
| 507 | curr->start = pos; |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 508 | |
| 509 | // 'pos' is not the offset of the start of a gzip chunk, so scan |
| 510 | // forward until we find a gzip header. |
| 511 | curr->type = CHUNK_NORMAL; |
| 512 | curr->data = p; |
| 513 | |
Tao Bao | ba9a42a | 2015-06-23 23:23:33 -0700 | [diff] [blame] | 514 | for (curr->len = 0; curr->len < (sz - pos); ++curr->len) { |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 515 | if (p[curr->len] == 0x1f && |
| 516 | p[curr->len+1] == 0x8b && |
| 517 | p[curr->len+2] == 0x08 && |
| 518 | p[curr->len+3] == 0x00) { |
| 519 | break; |
| 520 | } |
| 521 | } |
| 522 | pos += curr->len; |
| 523 | } |
| 524 | } |
| 525 | |
Tao Bao | 65f98cb | 2016-06-01 21:40:20 +0000 | [diff] [blame] | 526 | return img; |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 527 | } |
| 528 | |
| 529 | #define BUFFER_SIZE 32768 |
| 530 | |
| 531 | /* |
| 532 | * Takes the uncompressed data stored in the chunk, compresses it |
| 533 | * using the zlib parameters stored in the chunk, and checks that it |
| 534 | * matches exactly the compressed data we started with (also stored in |
| 535 | * the chunk). Return 0 on success. |
| 536 | */ |
| 537 | int TryReconstruction(ImageChunk* chunk, unsigned char* out) { |
| 538 | size_t p = 0; |
| 539 | |
| 540 | #if 0 |
| 541 | printf("trying %d %d %d %d %d\n", |
| 542 | chunk->level, chunk->method, chunk->windowBits, |
| 543 | chunk->memLevel, chunk->strategy); |
| 544 | #endif |
| 545 | |
| 546 | z_stream strm; |
| 547 | strm.zalloc = Z_NULL; |
| 548 | strm.zfree = Z_NULL; |
| 549 | strm.opaque = Z_NULL; |
| 550 | strm.avail_in = chunk->len; |
| 551 | strm.next_in = chunk->data; |
| 552 | int ret; |
| 553 | ret = deflateInit2(&strm, chunk->level, chunk->method, chunk->windowBits, |
| 554 | chunk->memLevel, chunk->strategy); |
| 555 | do { |
| 556 | strm.avail_out = BUFFER_SIZE; |
| 557 | strm.next_out = out; |
| 558 | ret = deflate(&strm, Z_FINISH); |
| 559 | size_t have = BUFFER_SIZE - strm.avail_out; |
| 560 | |
| 561 | if (memcmp(out, chunk->deflate_data+p, have) != 0) { |
| 562 | // mismatch; data isn't the same. |
| 563 | deflateEnd(&strm); |
| 564 | return -1; |
| 565 | } |
| 566 | p += have; |
| 567 | } while (ret != Z_STREAM_END); |
| 568 | deflateEnd(&strm); |
| 569 | if (p != chunk->deflate_len) { |
| 570 | // mismatch; ran out of data before we should have. |
| 571 | return -1; |
| 572 | } |
| 573 | return 0; |
| 574 | } |
| 575 | |
| 576 | /* |
| 577 | * Verify that we can reproduce exactly the same compressed data that |
| 578 | * we started with. Sets the level, method, windowBits, memLevel, and |
| 579 | * strategy fields in the chunk to the encoding parameters needed to |
| 580 | * produce the right output. Returns 0 on success. |
| 581 | */ |
| 582 | int ReconstructDeflateChunk(ImageChunk* chunk) { |
| 583 | if (chunk->type != CHUNK_DEFLATE) { |
| 584 | printf("attempt to reconstruct non-deflate chunk\n"); |
| 585 | return -1; |
| 586 | } |
| 587 | |
Rahul Chaudhry | 4f7faac | 2016-11-08 16:06:13 -0800 | [diff] [blame^] | 588 | unsigned char* out = static_cast<unsigned char*>(malloc(BUFFER_SIZE)); |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 589 | |
| 590 | // We only check two combinations of encoder parameters: level 6 |
| 591 | // (the default) and level 9 (the maximum). |
| 592 | for (chunk->level = 6; chunk->level <= 9; chunk->level += 3) { |
| 593 | chunk->windowBits = -15; // 32kb window; negative to indicate a raw stream. |
| 594 | chunk->memLevel = 8; // the default value. |
| 595 | chunk->method = Z_DEFLATED; |
| 596 | chunk->strategy = Z_DEFAULT_STRATEGY; |
| 597 | |
| 598 | if (TryReconstruction(chunk, out) == 0) { |
| 599 | free(out); |
| 600 | return 0; |
| 601 | } |
| 602 | } |
| 603 | |
| 604 | free(out); |
| 605 | return -1; |
| 606 | } |
| 607 | |
| 608 | /* |
| 609 | * Given source and target chunks, compute a bsdiff patch between them |
| 610 | * by running bsdiff in a subprocess. Return the patch data, placing |
| 611 | * its length in *size. Return NULL on failure. We expect the bsdiff |
| 612 | * program to be in the path. |
| 613 | */ |
| 614 | unsigned char* MakePatch(ImageChunk* src, ImageChunk* tgt, size_t* size) { |
| 615 | if (tgt->type == CHUNK_NORMAL) { |
| 616 | if (tgt->len <= 160) { |
| 617 | tgt->type = CHUNK_RAW; |
| 618 | *size = tgt->len; |
| 619 | return tgt->data; |
| 620 | } |
| 621 | } |
| 622 | |
| 623 | char ptemp[] = "/tmp/imgdiff-patch-XXXXXX"; |
Jeremy Compostella | a91c66d | 2015-09-08 19:15:09 +0200 | [diff] [blame] | 624 | int fd = mkstemp(ptemp); |
| 625 | |
| 626 | if (fd == -1) { |
| 627 | printf("MakePatch failed to create a temporary file: %s\n", |
| 628 | strerror(errno)); |
| 629 | return NULL; |
| 630 | } |
| 631 | close(fd); // temporary file is created and we don't need its file |
| 632 | // descriptor |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 633 | |
Sen Jiang | 2fffcb1 | 2016-05-03 15:49:10 -0700 | [diff] [blame] | 634 | int r = bsdiff::bsdiff(src->data, src->len, tgt->data, tgt->len, ptemp); |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 635 | if (r != 0) { |
| 636 | printf("bsdiff() failed: %d\n", r); |
| 637 | return NULL; |
| 638 | } |
| 639 | |
| 640 | struct stat st; |
| 641 | if (stat(ptemp, &st) != 0) { |
| 642 | printf("failed to stat patch file %s: %s\n", |
| 643 | ptemp, strerror(errno)); |
| 644 | return NULL; |
| 645 | } |
| 646 | |
Tao Bao | ba9a42a | 2015-06-23 23:23:33 -0700 | [diff] [blame] | 647 | size_t sz = static_cast<size_t>(st.st_size); |
Tao Bao | 65f98cb | 2016-06-01 21:40:20 +0000 | [diff] [blame] | 648 | // TODO: Memory leak on error return. |
Rahul Chaudhry | 4f7faac | 2016-11-08 16:06:13 -0800 | [diff] [blame^] | 649 | unsigned char* data = static_cast<unsigned char*>(malloc(sz)); |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 650 | |
Tao Bao | ba9a42a | 2015-06-23 23:23:33 -0700 | [diff] [blame] | 651 | if (tgt->type == CHUNK_NORMAL && tgt->len <= sz) { |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 652 | unlink(ptemp); |
| 653 | |
| 654 | tgt->type = CHUNK_RAW; |
| 655 | *size = tgt->len; |
| 656 | return tgt->data; |
| 657 | } |
| 658 | |
Tao Bao | ba9a42a | 2015-06-23 23:23:33 -0700 | [diff] [blame] | 659 | *size = sz; |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 660 | |
| 661 | FILE* f = fopen(ptemp, "rb"); |
| 662 | if (f == NULL) { |
| 663 | printf("failed to open patch %s: %s\n", ptemp, strerror(errno)); |
| 664 | return NULL; |
| 665 | } |
Tao Bao | 65f98cb | 2016-06-01 21:40:20 +0000 | [diff] [blame] | 666 | if (fread(data, 1, sz, f) != sz) { |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 667 | printf("failed to read patch %s: %s\n", ptemp, strerror(errno)); |
| 668 | return NULL; |
| 669 | } |
| 670 | fclose(f); |
| 671 | |
| 672 | unlink(ptemp); |
| 673 | |
| 674 | tgt->source_start = src->start; |
| 675 | switch (tgt->type) { |
| 676 | case CHUNK_NORMAL: |
| 677 | tgt->source_len = src->len; |
| 678 | break; |
| 679 | case CHUNK_DEFLATE: |
| 680 | tgt->source_len = src->deflate_len; |
| 681 | tgt->source_uncompressed_len = src->len; |
| 682 | break; |
| 683 | } |
| 684 | |
Tao Bao | 65f98cb | 2016-06-01 21:40:20 +0000 | [diff] [blame] | 685 | return data; |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 686 | } |
| 687 | |
| 688 | /* |
| 689 | * Cause a gzip chunk to be treated as a normal chunk (ie, as a blob |
| 690 | * of uninterpreted data). The resulting patch will likely be about |
| 691 | * as big as the target file, but it lets us handle the case of images |
| 692 | * where some gzip chunks are reconstructible but others aren't (by |
| 693 | * treating the ones that aren't as normal chunks). |
| 694 | */ |
| 695 | void ChangeDeflateChunkToNormal(ImageChunk* ch) { |
| 696 | if (ch->type != CHUNK_DEFLATE) return; |
| 697 | ch->type = CHUNK_NORMAL; |
| 698 | free(ch->data); |
| 699 | ch->data = ch->deflate_data; |
| 700 | ch->len = ch->deflate_len; |
| 701 | } |
| 702 | |
| 703 | /* |
| 704 | * Return true if the data in the chunk is identical (including the |
| 705 | * compressed representation, for gzip chunks). |
| 706 | */ |
| 707 | int AreChunksEqual(ImageChunk* a, ImageChunk* b) { |
| 708 | if (a->type != b->type) return 0; |
| 709 | |
| 710 | switch (a->type) { |
| 711 | case CHUNK_NORMAL: |
| 712 | return a->len == b->len && memcmp(a->data, b->data, a->len) == 0; |
| 713 | |
| 714 | case CHUNK_DEFLATE: |
| 715 | return a->deflate_len == b->deflate_len && |
| 716 | memcmp(a->deflate_data, b->deflate_data, a->deflate_len) == 0; |
| 717 | |
| 718 | default: |
| 719 | printf("unknown chunk type %d\n", a->type); |
| 720 | return 0; |
| 721 | } |
| 722 | } |
| 723 | |
| 724 | /* |
| 725 | * Look for runs of adjacent normal chunks and compress them down into |
| 726 | * a single chunk. (Such runs can be produced when deflate chunks are |
| 727 | * changed to normal chunks.) |
| 728 | */ |
| 729 | void MergeAdjacentNormalChunks(ImageChunk* chunks, int* num_chunks) { |
| 730 | int out = 0; |
| 731 | int in_start = 0, in_end; |
| 732 | while (in_start < *num_chunks) { |
| 733 | if (chunks[in_start].type != CHUNK_NORMAL) { |
| 734 | in_end = in_start+1; |
| 735 | } else { |
| 736 | // in_start is a normal chunk. Look for a run of normal chunks |
| 737 | // that constitute a solid block of data (ie, each chunk begins |
| 738 | // where the previous one ended). |
| 739 | for (in_end = in_start+1; |
| 740 | in_end < *num_chunks && chunks[in_end].type == CHUNK_NORMAL && |
| 741 | (chunks[in_end].start == |
| 742 | chunks[in_end-1].start + chunks[in_end-1].len && |
| 743 | chunks[in_end].data == |
| 744 | chunks[in_end-1].data + chunks[in_end-1].len); |
| 745 | ++in_end); |
| 746 | } |
| 747 | |
| 748 | if (in_end == in_start+1) { |
| 749 | #if 0 |
| 750 | printf("chunk %d is now %d\n", in_start, out); |
| 751 | #endif |
| 752 | if (out != in_start) { |
| 753 | memcpy(chunks+out, chunks+in_start, sizeof(ImageChunk)); |
| 754 | } |
| 755 | } else { |
| 756 | #if 0 |
| 757 | printf("collapse normal chunks %d-%d into %d\n", in_start, in_end-1, out); |
| 758 | #endif |
| 759 | |
| 760 | // Merge chunks [in_start, in_end-1] into one chunk. Since the |
| 761 | // data member of each chunk is just a pointer into an in-memory |
| 762 | // copy of the file, this can be done without recopying (the |
| 763 | // output chunk has the first chunk's start location and data |
| 764 | // pointer, and length equal to the sum of the input chunk |
| 765 | // lengths). |
| 766 | chunks[out].type = CHUNK_NORMAL; |
| 767 | chunks[out].start = chunks[in_start].start; |
| 768 | chunks[out].data = chunks[in_start].data; |
| 769 | chunks[out].len = chunks[in_end-1].len + |
| 770 | (chunks[in_end-1].start - chunks[in_start].start); |
| 771 | } |
| 772 | |
| 773 | ++out; |
| 774 | in_start = in_end; |
| 775 | } |
| 776 | *num_chunks = out; |
| 777 | } |
| 778 | |
| 779 | ImageChunk* FindChunkByName(const char* name, |
| 780 | ImageChunk* chunks, int num_chunks) { |
| 781 | int i; |
| 782 | for (i = 0; i < num_chunks; ++i) { |
| 783 | if (chunks[i].type == CHUNK_DEFLATE && chunks[i].filename && |
| 784 | strcmp(name, chunks[i].filename) == 0) { |
| 785 | return chunks+i; |
| 786 | } |
| 787 | } |
| 788 | return NULL; |
| 789 | } |
| 790 | |
| 791 | void DumpChunks(ImageChunk* chunks, int num_chunks) { |
Tao Bao | ba9a42a | 2015-06-23 23:23:33 -0700 | [diff] [blame] | 792 | for (int i = 0; i < num_chunks; ++i) { |
| 793 | printf("chunk %d: type %d start %zu len %zu\n", |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 794 | i, chunks[i].type, chunks[i].start, chunks[i].len); |
| 795 | } |
| 796 | } |
| 797 | |
| 798 | int main(int argc, char** argv) { |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 799 | int zip_mode = 0; |
| 800 | |
Doug Zongker | a3ccba6 | 2012-08-20 15:28:02 -0700 | [diff] [blame] | 801 | if (argc >= 2 && strcmp(argv[1], "-z") == 0) { |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 802 | zip_mode = 1; |
| 803 | --argc; |
| 804 | ++argv; |
| 805 | } |
| 806 | |
Doug Zongker | a3ccba6 | 2012-08-20 15:28:02 -0700 | [diff] [blame] | 807 | size_t bonus_size = 0; |
Tao Bao | 65f98cb | 2016-06-01 21:40:20 +0000 | [diff] [blame] | 808 | unsigned char* bonus_data = NULL; |
Doug Zongker | a3ccba6 | 2012-08-20 15:28:02 -0700 | [diff] [blame] | 809 | if (argc >= 3 && strcmp(argv[1], "-b") == 0) { |
| 810 | struct stat st; |
| 811 | if (stat(argv[2], &st) != 0) { |
| 812 | printf("failed to stat bonus file %s: %s\n", argv[2], strerror(errno)); |
| 813 | return 1; |
| 814 | } |
| 815 | bonus_size = st.st_size; |
Rahul Chaudhry | 4f7faac | 2016-11-08 16:06:13 -0800 | [diff] [blame^] | 816 | bonus_data = static_cast<unsigned char*>(malloc(bonus_size)); |
Doug Zongker | a3ccba6 | 2012-08-20 15:28:02 -0700 | [diff] [blame] | 817 | FILE* f = fopen(argv[2], "rb"); |
| 818 | if (f == NULL) { |
| 819 | printf("failed to open bonus file %s: %s\n", argv[2], strerror(errno)); |
| 820 | return 1; |
| 821 | } |
Tao Bao | 65f98cb | 2016-06-01 21:40:20 +0000 | [diff] [blame] | 822 | if (fread(bonus_data, 1, bonus_size, f) != bonus_size) { |
Doug Zongker | a3ccba6 | 2012-08-20 15:28:02 -0700 | [diff] [blame] | 823 | printf("failed to read bonus file %s: %s\n", argv[2], strerror(errno)); |
| 824 | return 1; |
| 825 | } |
| 826 | fclose(f); |
| 827 | |
| 828 | argc -= 2; |
| 829 | argv += 2; |
| 830 | } |
| 831 | |
| 832 | if (argc != 4) { |
Doug Zongker | a3ccba6 | 2012-08-20 15:28:02 -0700 | [diff] [blame] | 833 | printf("usage: %s [-z] [-b <bonus-file>] <src-img> <tgt-img> <patch-file>\n", |
| 834 | argv[0]); |
| 835 | return 2; |
| 836 | } |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 837 | |
| 838 | int num_src_chunks; |
| 839 | ImageChunk* src_chunks; |
| 840 | int num_tgt_chunks; |
| 841 | ImageChunk* tgt_chunks; |
| 842 | int i; |
| 843 | |
| 844 | if (zip_mode) { |
| 845 | if (ReadZip(argv[1], &num_src_chunks, &src_chunks, 1) == NULL) { |
| 846 | printf("failed to break apart source zip file\n"); |
| 847 | return 1; |
| 848 | } |
| 849 | if (ReadZip(argv[2], &num_tgt_chunks, &tgt_chunks, 0) == NULL) { |
| 850 | printf("failed to break apart target zip file\n"); |
| 851 | return 1; |
| 852 | } |
| 853 | } else { |
| 854 | if (ReadImage(argv[1], &num_src_chunks, &src_chunks) == NULL) { |
| 855 | printf("failed to break apart source image\n"); |
| 856 | return 1; |
| 857 | } |
| 858 | if (ReadImage(argv[2], &num_tgt_chunks, &tgt_chunks) == NULL) { |
| 859 | printf("failed to break apart target image\n"); |
| 860 | return 1; |
| 861 | } |
| 862 | |
| 863 | // Verify that the source and target images have the same chunk |
| 864 | // structure (ie, the same sequence of deflate and normal chunks). |
| 865 | |
| 866 | if (!zip_mode) { |
| 867 | // Merge the gzip header and footer in with any adjacent |
| 868 | // normal chunks. |
| 869 | MergeAdjacentNormalChunks(tgt_chunks, &num_tgt_chunks); |
| 870 | MergeAdjacentNormalChunks(src_chunks, &num_src_chunks); |
| 871 | } |
| 872 | |
| 873 | if (num_src_chunks != num_tgt_chunks) { |
| 874 | printf("source and target don't have same number of chunks!\n"); |
| 875 | printf("source chunks:\n"); |
| 876 | DumpChunks(src_chunks, num_src_chunks); |
| 877 | printf("target chunks:\n"); |
| 878 | DumpChunks(tgt_chunks, num_tgt_chunks); |
| 879 | return 1; |
| 880 | } |
| 881 | for (i = 0; i < num_src_chunks; ++i) { |
| 882 | if (src_chunks[i].type != tgt_chunks[i].type) { |
| 883 | printf("source and target don't have same chunk " |
| 884 | "structure! (chunk %d)\n", i); |
| 885 | printf("source chunks:\n"); |
| 886 | DumpChunks(src_chunks, num_src_chunks); |
| 887 | printf("target chunks:\n"); |
| 888 | DumpChunks(tgt_chunks, num_tgt_chunks); |
| 889 | return 1; |
| 890 | } |
| 891 | } |
| 892 | } |
| 893 | |
| 894 | for (i = 0; i < num_tgt_chunks; ++i) { |
| 895 | if (tgt_chunks[i].type == CHUNK_DEFLATE) { |
| 896 | // Confirm that given the uncompressed chunk data in the target, we |
| 897 | // can recompress it and get exactly the same bits as are in the |
| 898 | // input target image. If this fails, treat the chunk as a normal |
| 899 | // non-deflated chunk. |
| 900 | if (ReconstructDeflateChunk(tgt_chunks+i) < 0) { |
| 901 | printf("failed to reconstruct target deflate chunk %d [%s]; " |
| 902 | "treating as normal\n", i, tgt_chunks[i].filename); |
| 903 | ChangeDeflateChunkToNormal(tgt_chunks+i); |
| 904 | if (zip_mode) { |
| 905 | ImageChunk* src = FindChunkByName(tgt_chunks[i].filename, src_chunks, num_src_chunks); |
| 906 | if (src) { |
| 907 | ChangeDeflateChunkToNormal(src); |
| 908 | } |
| 909 | } else { |
| 910 | ChangeDeflateChunkToNormal(src_chunks+i); |
| 911 | } |
| 912 | continue; |
| 913 | } |
| 914 | |
| 915 | // If two deflate chunks are identical (eg, the kernel has not |
| 916 | // changed between two builds), treat them as normal chunks. |
| 917 | // This makes applypatch much faster -- it can apply a trivial |
| 918 | // patch to the compressed data, rather than uncompressing and |
| 919 | // recompressing to apply the trivial patch to the uncompressed |
| 920 | // data. |
| 921 | ImageChunk* src; |
| 922 | if (zip_mode) { |
| 923 | src = FindChunkByName(tgt_chunks[i].filename, src_chunks, num_src_chunks); |
| 924 | } else { |
| 925 | src = src_chunks+i; |
| 926 | } |
| 927 | |
| 928 | if (src == NULL || AreChunksEqual(tgt_chunks+i, src)) { |
| 929 | ChangeDeflateChunkToNormal(tgt_chunks+i); |
| 930 | if (src) { |
| 931 | ChangeDeflateChunkToNormal(src); |
| 932 | } |
| 933 | } |
| 934 | } |
| 935 | } |
| 936 | |
| 937 | // Merging neighboring normal chunks. |
| 938 | if (zip_mode) { |
| 939 | // For zips, we only need to do this to the target: deflated |
| 940 | // chunks are matched via filename, and normal chunks are patched |
| 941 | // using the entire source file as the source. |
| 942 | MergeAdjacentNormalChunks(tgt_chunks, &num_tgt_chunks); |
| 943 | } else { |
| 944 | // For images, we need to maintain the parallel structure of the |
| 945 | // chunk lists, so do the merging in both the source and target |
| 946 | // lists. |
| 947 | MergeAdjacentNormalChunks(tgt_chunks, &num_tgt_chunks); |
| 948 | MergeAdjacentNormalChunks(src_chunks, &num_src_chunks); |
| 949 | if (num_src_chunks != num_tgt_chunks) { |
| 950 | // This shouldn't happen. |
| 951 | printf("merging normal chunks went awry\n"); |
| 952 | return 1; |
| 953 | } |
| 954 | } |
| 955 | |
| 956 | // Compute bsdiff patches for each chunk's data (the uncompressed |
| 957 | // data, in the case of deflate chunks). |
| 958 | |
Doug Zongker | a3ccba6 | 2012-08-20 15:28:02 -0700 | [diff] [blame] | 959 | DumpChunks(src_chunks, num_src_chunks); |
| 960 | |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 961 | printf("Construct patches for %d chunks...\n", num_tgt_chunks); |
Rahul Chaudhry | 4f7faac | 2016-11-08 16:06:13 -0800 | [diff] [blame^] | 962 | unsigned char** patch_data = static_cast<unsigned char**>(malloc( |
Tao Bao | ba9a42a | 2015-06-23 23:23:33 -0700 | [diff] [blame] | 963 | num_tgt_chunks * sizeof(unsigned char*))); |
Rahul Chaudhry | 4f7faac | 2016-11-08 16:06:13 -0800 | [diff] [blame^] | 964 | size_t* patch_size = static_cast<size_t*>(malloc(num_tgt_chunks * sizeof(size_t))); |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 965 | for (i = 0; i < num_tgt_chunks; ++i) { |
| 966 | if (zip_mode) { |
| 967 | ImageChunk* src; |
| 968 | if (tgt_chunks[i].type == CHUNK_DEFLATE && |
| 969 | (src = FindChunkByName(tgt_chunks[i].filename, src_chunks, |
| 970 | num_src_chunks))) { |
| 971 | patch_data[i] = MakePatch(src, tgt_chunks+i, patch_size+i); |
| 972 | } else { |
| 973 | patch_data[i] = MakePatch(src_chunks, tgt_chunks+i, patch_size+i); |
| 974 | } |
| 975 | } else { |
Tao Bao | 65f98cb | 2016-06-01 21:40:20 +0000 | [diff] [blame] | 976 | if (i == 1 && bonus_data) { |
Tao Bao | ba9a42a | 2015-06-23 23:23:33 -0700 | [diff] [blame] | 977 | printf(" using %zu bytes of bonus data for chunk %d\n", bonus_size, i); |
Rahul Chaudhry | 4f7faac | 2016-11-08 16:06:13 -0800 | [diff] [blame^] | 978 | src_chunks[i].data = static_cast<unsigned char*>(realloc(src_chunks[i].data, |
Tao Bao | ba9a42a | 2015-06-23 23:23:33 -0700 | [diff] [blame] | 979 | src_chunks[i].len + bonus_size)); |
Tao Bao | 65f98cb | 2016-06-01 21:40:20 +0000 | [diff] [blame] | 980 | memcpy(src_chunks[i].data+src_chunks[i].len, bonus_data, bonus_size); |
Doug Zongker | a3ccba6 | 2012-08-20 15:28:02 -0700 | [diff] [blame] | 981 | src_chunks[i].len += bonus_size; |
| 982 | } |
| 983 | |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 984 | patch_data[i] = MakePatch(src_chunks+i, tgt_chunks+i, patch_size+i); |
| 985 | } |
Tao Bao | ba9a42a | 2015-06-23 23:23:33 -0700 | [diff] [blame] | 986 | printf("patch %3d is %zu bytes (of %zu)\n", |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 987 | i, patch_size[i], tgt_chunks[i].source_len); |
| 988 | } |
| 989 | |
| 990 | // Figure out how big the imgdiff file header is going to be, so |
| 991 | // that we can correctly compute the offset of each bsdiff patch |
| 992 | // within the file. |
| 993 | |
| 994 | size_t total_header_size = 12; |
| 995 | for (i = 0; i < num_tgt_chunks; ++i) { |
| 996 | total_header_size += 4; |
| 997 | switch (tgt_chunks[i].type) { |
| 998 | case CHUNK_NORMAL: |
| 999 | total_header_size += 8*3; |
| 1000 | break; |
| 1001 | case CHUNK_DEFLATE: |
| 1002 | total_header_size += 8*5 + 4*5; |
| 1003 | break; |
| 1004 | case CHUNK_RAW: |
| 1005 | total_header_size += 4 + patch_size[i]; |
| 1006 | break; |
| 1007 | } |
| 1008 | } |
| 1009 | |
| 1010 | size_t offset = total_header_size; |
| 1011 | |
| 1012 | FILE* f = fopen(argv[3], "wb"); |
| 1013 | |
| 1014 | // Write out the headers. |
| 1015 | |
| 1016 | fwrite("IMGDIFF2", 1, 8, f); |
| 1017 | Write4(num_tgt_chunks, f); |
| 1018 | for (i = 0; i < num_tgt_chunks; ++i) { |
| 1019 | Write4(tgt_chunks[i].type, f); |
| 1020 | |
| 1021 | switch (tgt_chunks[i].type) { |
| 1022 | case CHUNK_NORMAL: |
Tao Bao | ba9a42a | 2015-06-23 23:23:33 -0700 | [diff] [blame] | 1023 | printf("chunk %3d: normal (%10zu, %10zu) %10zu\n", i, |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 1024 | tgt_chunks[i].start, tgt_chunks[i].len, patch_size[i]); |
| 1025 | Write8(tgt_chunks[i].source_start, f); |
| 1026 | Write8(tgt_chunks[i].source_len, f); |
| 1027 | Write8(offset, f); |
| 1028 | offset += patch_size[i]; |
| 1029 | break; |
| 1030 | |
| 1031 | case CHUNK_DEFLATE: |
Tao Bao | ba9a42a | 2015-06-23 23:23:33 -0700 | [diff] [blame] | 1032 | printf("chunk %3d: deflate (%10zu, %10zu) %10zu %s\n", i, |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 1033 | tgt_chunks[i].start, tgt_chunks[i].deflate_len, patch_size[i], |
| 1034 | tgt_chunks[i].filename); |
| 1035 | Write8(tgt_chunks[i].source_start, f); |
| 1036 | Write8(tgt_chunks[i].source_len, f); |
| 1037 | Write8(offset, f); |
| 1038 | Write8(tgt_chunks[i].source_uncompressed_len, f); |
| 1039 | Write8(tgt_chunks[i].len, f); |
| 1040 | Write4(tgt_chunks[i].level, f); |
| 1041 | Write4(tgt_chunks[i].method, f); |
| 1042 | Write4(tgt_chunks[i].windowBits, f); |
| 1043 | Write4(tgt_chunks[i].memLevel, f); |
| 1044 | Write4(tgt_chunks[i].strategy, f); |
| 1045 | offset += patch_size[i]; |
| 1046 | break; |
| 1047 | |
| 1048 | case CHUNK_RAW: |
Tao Bao | ba9a42a | 2015-06-23 23:23:33 -0700 | [diff] [blame] | 1049 | printf("chunk %3d: raw (%10zu, %10zu)\n", i, |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 1050 | tgt_chunks[i].start, tgt_chunks[i].len); |
| 1051 | Write4(patch_size[i], f); |
| 1052 | fwrite(patch_data[i], 1, patch_size[i], f); |
| 1053 | break; |
| 1054 | } |
| 1055 | } |
| 1056 | |
| 1057 | // Append each chunk's bsdiff patch, in order. |
| 1058 | |
| 1059 | for (i = 0; i < num_tgt_chunks; ++i) { |
| 1060 | if (tgt_chunks[i].type != CHUNK_RAW) { |
| 1061 | fwrite(patch_data[i], 1, patch_size[i], f); |
| 1062 | } |
| 1063 | } |
| 1064 | |
| 1065 | fclose(f); |
Doug Zongker | 512536a | 2010-02-17 16:11:44 -0800 | [diff] [blame] | 1066 | |
| 1067 | return 0; |
| 1068 | } |