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. 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. 122 */ 123 124 #include "applypatch/imgdiff.h" 125 126 #include <errno.h> 127 #include <fcntl.h> 128 #include <stdio.h> 129 #include <stdlib.h> 130 #include <string.h> 131 #include <sys/stat.h> 132 #include <sys/types.h> 133 #include <unistd.h> 134 135 #include <algorithm> 136 #include <string> 137 #include <vector> 138 139 #include <android-base/file.h> 140 #include <android-base/logging.h> 141 #include <android-base/memory.h> 142 #include <android-base/unique_fd.h> 143 #include <ziparchive/zip_archive.h> 144 145 #include <bsdiff.h> 146 #include <zlib.h> 147 148 using android::base::get_unaligned; 149 150 static constexpr auto BUFFER_SIZE = 0x8000; 151 152 // If we use this function to write the offset and length (type size_t), their values should not 153 // exceed 2^63; because the signed bit will be casted away. 154 static inline bool Write8(int fd, int64_t value) { 155 return android::base::WriteFully(fd, &value, sizeof(int64_t)); 156 } 157 158 // Similarly, the value should not exceed 2^31 if we are casting from size_t (e.g. target chunk 159 // size). 160 static inline bool Write4(int fd, int32_t value) { 161 return android::base::WriteFully(fd, &value, sizeof(int32_t)); 162 } 163 164 class ImageChunk { 165 public: 166 static constexpr auto WINDOWBITS = -15; // 32kb window; negative to indicate a raw stream. 167 static constexpr auto MEMLEVEL = 8; // the default value. 168 static constexpr auto METHOD = Z_DEFLATED; 169 static constexpr auto STRATEGY = Z_DEFAULT_STRATEGY; 170 171 ImageChunk(int type, size_t start, const std::vector<uint8_t>* file_content, size_t raw_data_len) 172 : type_(type), 173 start_(start), 174 input_file_ptr_(file_content), 175 raw_data_len_(raw_data_len), 176 compress_level_(6), 177 source_start_(0), 178 source_len_(0), 179 source_uncompressed_len_(0) { 180 CHECK(file_content != nullptr) << "input file container can't be nullptr"; 181 } 182 183 int GetType() const { 184 return type_; 185 } 186 size_t GetRawDataLength() const { 187 return raw_data_len_; 188 } 189 const std::string& GetEntryName() const { 190 return entry_name_; 191 } 192 193 // CHUNK_DEFLATE will return the uncompressed data for diff, while other types will simply return 194 // the raw data. 195 const uint8_t * DataForPatch() const; 196 size_t DataLengthForPatch() const; 197 198 void Dump() const { 199 printf("type %d start %zu len %zu\n", type_, start_, DataLengthForPatch()); 200 } 201 202 void SetSourceInfo(const ImageChunk& other); 203 void SetEntryName(std::string entryname); 204 void SetUncompressedData(std::vector<uint8_t> data); 205 bool SetBonusData(const std::vector<uint8_t>& bonus_data); 206 207 bool operator==(const ImageChunk& other) const; 208 bool operator!=(const ImageChunk& other) const { 209 return !(*this == other); 210 } 211 212 size_t GetHeaderSize(size_t patch_size) const; 213 // Return the offset of the next patch into the patch data. 214 size_t WriteHeaderToFd(int fd, const std::vector<uint8_t>& patch, size_t offset); 215 216 /* 217 * Cause a gzip chunk to be treated as a normal chunk (ie, as a blob 218 * of uninterpreted data). The resulting patch will likely be about 219 * as big as the target file, but it lets us handle the case of images 220 * where some gzip chunks are reconstructible but others aren't (by 221 * treating the ones that aren't as normal chunks). 222 */ 223 void ChangeDeflateChunkToNormal(); 224 bool ChangeChunkToRaw(size_t patch_size); 225 226 /* 227 * Verify that we can reproduce exactly the same compressed data that 228 * we started with. Sets the level, method, windowBits, memLevel, and 229 * strategy fields in the chunk to the encoding parameters needed to 230 * produce the right output. 231 */ 232 bool ReconstructDeflateChunk(); 233 bool IsAdjacentNormal(const ImageChunk& other) const; 234 void MergeAdjacentNormal(const ImageChunk& other); 235 236 private: 237 int type_; // CHUNK_NORMAL, CHUNK_DEFLATE, CHUNK_RAW 238 size_t start_; // offset of chunk in the original input file 239 const std::vector<uint8_t>* input_file_ptr_; // ptr to the full content of original input file 240 size_t raw_data_len_; 241 242 // --- for CHUNK_DEFLATE chunks only: --- 243 std::vector<uint8_t> uncompressed_data_; 244 std::string entry_name_; // used for zip entries 245 246 // deflate encoder parameters 247 int compress_level_; 248 249 size_t source_start_; 250 size_t source_len_; 251 size_t source_uncompressed_len_; 252 253 const uint8_t* GetRawData() const; 254 bool TryReconstruction(int level); 255 }; 256 257 const uint8_t* ImageChunk::GetRawData() const { 258 CHECK_LE(start_ + raw_data_len_, input_file_ptr_->size()); 259 return input_file_ptr_->data() + start_; 260 } 261 262 const uint8_t * ImageChunk::DataForPatch() const { 263 if (type_ == CHUNK_DEFLATE) { 264 return uncompressed_data_.data(); 265 } 266 return GetRawData(); 267 } 268 269 size_t ImageChunk::DataLengthForPatch() const { 270 if (type_ == CHUNK_DEFLATE) { 271 return uncompressed_data_.size(); 272 } 273 return raw_data_len_; 274 } 275 276 bool ImageChunk::operator==(const ImageChunk& other) const { 277 if (type_ != other.type_) { 278 return false; 279 } 280 return (raw_data_len_ == other.raw_data_len_ && 281 memcmp(GetRawData(), other.GetRawData(), raw_data_len_) == 0); 282 } 283 284 void ImageChunk::SetSourceInfo(const ImageChunk& src) { 285 source_start_ = src.start_; 286 if (type_ == CHUNK_NORMAL) { 287 source_len_ = src.raw_data_len_; 288 } else if (type_ == CHUNK_DEFLATE) { 289 source_len_ = src.raw_data_len_; 290 source_uncompressed_len_ = src.uncompressed_data_.size(); 291 } 292 } 293 294 void ImageChunk::SetEntryName(std::string entryname) { 295 entry_name_ = std::move(entryname); 296 } 297 298 void ImageChunk::SetUncompressedData(std::vector<uint8_t> data) { 299 uncompressed_data_ = std::move(data); 300 } 301 302 bool ImageChunk::SetBonusData(const std::vector<uint8_t>& bonus_data) { 303 if (type_ != CHUNK_DEFLATE) { 304 return false; 305 } 306 uncompressed_data_.insert(uncompressed_data_.end(), bonus_data.begin(), bonus_data.end()); 307 return true; 308 } 309 310 // Convert CHUNK_NORMAL & CHUNK_DEFLATE to CHUNK_RAW if the target size is 311 // smaller. Also take the header size into account during size comparison. 312 bool ImageChunk::ChangeChunkToRaw(size_t patch_size) { 313 if (type_ == CHUNK_RAW) { 314 return true; 315 } else if (type_ == CHUNK_NORMAL && (raw_data_len_ <= 160 || raw_data_len_ < patch_size)) { 316 type_ = CHUNK_RAW; 317 return true; 318 } 319 return false; 320 } 321 322 void ImageChunk::ChangeDeflateChunkToNormal() { 323 if (type_ != CHUNK_DEFLATE) return; 324 type_ = CHUNK_NORMAL; 325 entry_name_.clear(); 326 uncompressed_data_.clear(); 327 } 328 329 // Header size: 330 // header_type 4 bytes 331 // CHUNK_NORMAL 8*3 = 24 bytes 332 // CHUNK_DEFLATE 8*5 + 4*5 = 60 bytes 333 // CHUNK_RAW 4 bytes + patch_size 334 size_t ImageChunk::GetHeaderSize(size_t patch_size) const { 335 switch (type_) { 336 case CHUNK_NORMAL: 337 return 4 + 8 * 3; 338 case CHUNK_DEFLATE: 339 return 4 + 8 * 5 + 4 * 5; 340 case CHUNK_RAW: 341 return 4 + 4 + patch_size; 342 default: 343 CHECK(false) << "unexpected chunk type: " << type_; // Should not reach here. 344 return 0; 345 } 346 } 347 348 size_t ImageChunk::WriteHeaderToFd(int fd, const std::vector<uint8_t>& patch, size_t offset) { 349 Write4(fd, type_); 350 switch (type_) { 351 case CHUNK_NORMAL: 352 printf("normal (%10zu, %10zu) %10zu\n", start_, raw_data_len_, patch.size()); 353 Write8(fd, static_cast<int64_t>(source_start_)); 354 Write8(fd, static_cast<int64_t>(source_len_)); 355 Write8(fd, static_cast<int64_t>(offset)); 356 return offset + patch.size(); 357 case CHUNK_DEFLATE: 358 printf("deflate (%10zu, %10zu) %10zu %s\n", start_, raw_data_len_, patch.size(), 359 entry_name_.c_str()); 360 Write8(fd, static_cast<int64_t>(source_start_)); 361 Write8(fd, static_cast<int64_t>(source_len_)); 362 Write8(fd, static_cast<int64_t>(offset)); 363 Write8(fd, static_cast<int64_t>(source_uncompressed_len_)); 364 Write8(fd, static_cast<int64_t>(uncompressed_data_.size())); 365 Write4(fd, compress_level_); 366 Write4(fd, METHOD); 367 Write4(fd, WINDOWBITS); 368 Write4(fd, MEMLEVEL); 369 Write4(fd, STRATEGY); 370 return offset + patch.size(); 371 case CHUNK_RAW: 372 printf("raw (%10zu, %10zu)\n", start_, raw_data_len_); 373 Write4(fd, static_cast<int32_t>(patch.size())); 374 if (!android::base::WriteFully(fd, patch.data(), patch.size())) { 375 CHECK(false) << "failed to write " << patch.size() <<" bytes patch"; 376 } 377 return offset; 378 default: 379 CHECK(false) << "unexpected chunk type: " << type_; 380 return offset; 381 } 382 } 383 384 bool ImageChunk::IsAdjacentNormal(const ImageChunk& other) const { 385 if (type_ != CHUNK_NORMAL || other.type_ != CHUNK_NORMAL) { 386 return false; 387 } 388 return (other.start_ == start_ + raw_data_len_); 389 } 390 391 void ImageChunk::MergeAdjacentNormal(const ImageChunk& other) { 392 CHECK(IsAdjacentNormal(other)); 393 raw_data_len_ = raw_data_len_ + other.raw_data_len_; 394 } 395 396 bool ImageChunk::ReconstructDeflateChunk() { 397 if (type_ != CHUNK_DEFLATE) { 398 printf("attempt to reconstruct non-deflate chunk\n"); 399 return false; 400 } 401 402 // We only check two combinations of encoder parameters: level 6 403 // (the default) and level 9 (the maximum). 404 for (int level = 6; level <= 9; level += 3) { 405 if (TryReconstruction(level)) { 406 compress_level_ = level; 407 return true; 408 } 409 } 410 411 return false; 412 } 413 414 /* 415 * Takes the uncompressed data stored in the chunk, compresses it 416 * using the zlib parameters stored in the chunk, and checks that it 417 * matches exactly the compressed data we started with (also stored in 418 * the chunk). 419 */ 420 bool ImageChunk::TryReconstruction(int level) { 421 z_stream strm; 422 strm.zalloc = Z_NULL; 423 strm.zfree = Z_NULL; 424 strm.opaque = Z_NULL; 425 strm.avail_in = uncompressed_data_.size(); 426 strm.next_in = uncompressed_data_.data(); 427 int ret = deflateInit2(&strm, level, METHOD, WINDOWBITS, MEMLEVEL, STRATEGY); 428 if (ret < 0) { 429 printf("failed to initialize deflate: %d\n", ret); 430 return false; 431 } 432 433 std::vector<uint8_t> buffer(BUFFER_SIZE); 434 size_t offset = 0; 435 do { 436 strm.avail_out = buffer.size(); 437 strm.next_out = buffer.data(); 438 ret = deflate(&strm, Z_FINISH); 439 if (ret < 0) { 440 printf("failed to deflate: %d\n", ret); 441 return false; 442 } 443 444 size_t compressed_size = buffer.size() - strm.avail_out; 445 if (memcmp(buffer.data(), input_file_ptr_->data() + start_ + offset, compressed_size) != 0) { 446 // mismatch; data isn't the same. 447 deflateEnd(&strm); 448 return false; 449 } 450 offset += compressed_size; 451 } while (ret != Z_STREAM_END); 452 deflateEnd(&strm); 453 454 if (offset != raw_data_len_) { 455 // mismatch; ran out of data before we should have. 456 return false; 457 } 458 return true; 459 } 460 461 // EOCD record 462 // offset 0: signature 0x06054b50, 4 bytes 463 // offset 4: number of this disk, 2 bytes 464 // ... 465 // offset 20: comment length, 2 bytes 466 // offset 22: comment, n bytes 467 static bool GetZipFileSize(const std::vector<uint8_t>& zip_file, size_t* input_file_size) { 468 if (zip_file.size() < 22) { 469 printf("file is too small to be a zip file\n"); 470 return false; 471 } 472 473 // Look for End of central directory record of the zip file, and calculate the actual 474 // zip_file size. 475 for (int i = zip_file.size() - 22; i >= 0; i--) { 476 if (zip_file[i] == 0x50) { 477 if (get_unaligned<uint32_t>(&zip_file[i]) == 0x06054b50) { 478 // double-check: this archive consists of a single "disk". 479 CHECK_EQ(get_unaligned<uint16_t>(&zip_file[i + 4]), 0); 480 481 uint16_t comment_length = get_unaligned<uint16_t>(&zip_file[i + 20]); 482 size_t file_size = i + 22 + comment_length; 483 CHECK_LE(file_size, zip_file.size()); 484 *input_file_size = file_size; 485 return true; 486 } 487 } 488 } 489 490 // EOCD not found, this file is likely not a valid zip file. 491 return false; 492 } 493 494 static bool ReadZip(const char* filename, std::vector<ImageChunk>* chunks, 495 std::vector<uint8_t>* zip_file, bool include_pseudo_chunk) { 496 CHECK(chunks != nullptr && zip_file != nullptr); 497 498 android::base::unique_fd fd(open(filename, O_RDONLY)); 499 if (fd == -1) { 500 printf("failed to open \"%s\" %s\n", filename, strerror(errno)); 501 return false; 502 } 503 struct stat st; 504 if (fstat(fd, &st) != 0) { 505 printf("failed to stat \"%s\": %s\n", filename, strerror(errno)); 506 return false; 507 } 508 509 size_t sz = static_cast<size_t>(st.st_size); 510 zip_file->resize(sz); 511 if (!android::base::ReadFully(fd, zip_file->data(), sz)) { 512 printf("failed to read \"%s\" %s\n", filename, strerror(errno)); 513 return false; 514 } 515 fd.reset(); 516 517 // Trim the trailing zeros before we pass the file to ziparchive handler. 518 size_t zipfile_size; 519 if (!GetZipFileSize(*zip_file, &zipfile_size)) { 520 printf("failed to parse the actual size of %s\n", filename); 521 return false; 522 } 523 ZipArchiveHandle handle; 524 int err = OpenArchiveFromMemory(zip_file->data(), zipfile_size, filename, &handle); 525 if (err != 0) { 526 printf("failed to open zip file %s: %s\n", filename, ErrorCodeString(err)); 527 CloseArchive(handle); 528 return false; 529 } 530 531 // Create a list of deflated zip entries, sorted by offset. 532 std::vector<std::pair<std::string, ZipEntry>> temp_entries; 533 void* cookie; 534 int ret = StartIteration(handle, &cookie, nullptr, nullptr); 535 if (ret != 0) { 536 printf("failed to iterate over entries in %s: %s\n", filename, ErrorCodeString(ret)); 537 CloseArchive(handle); 538 return false; 539 } 540 541 ZipString name; 542 ZipEntry entry; 543 while ((ret = Next(cookie, &entry, &name)) == 0) { 544 if (entry.method == kCompressDeflated) { 545 std::string entryname(name.name, name.name + name.name_length); 546 temp_entries.push_back(std::make_pair(entryname, entry)); 547 } 548 } 549 550 if (ret != -1) { 551 printf("Error while iterating over zip entries: %s\n", ErrorCodeString(ret)); 552 CloseArchive(handle); 553 return false; 554 } 555 std::sort(temp_entries.begin(), temp_entries.end(), 556 [](auto& entry1, auto& entry2) { 557 return entry1.second.offset < entry2.second.offset; 558 }); 559 560 EndIteration(cookie); 561 562 if (include_pseudo_chunk) { 563 chunks->emplace_back(CHUNK_NORMAL, 0, zip_file, zip_file->size()); 564 } 565 566 size_t pos = 0; 567 size_t nextentry = 0; 568 while (pos < zip_file->size()) { 569 if (nextentry < temp_entries.size() && 570 static_cast<off64_t>(pos) == temp_entries[nextentry].second.offset) { 571 // compose the next deflate chunk. 572 std::string entryname = temp_entries[nextentry].first; 573 size_t uncompressed_len = temp_entries[nextentry].second.uncompressed_length; 574 std::vector<uint8_t> uncompressed_data(uncompressed_len); 575 if ((ret = ExtractToMemory(handle, &temp_entries[nextentry].second, uncompressed_data.data(), 576 uncompressed_len)) != 0) { 577 printf("failed to extract %s with size %zu: %s\n", entryname.c_str(), uncompressed_len, 578 ErrorCodeString(ret)); 579 CloseArchive(handle); 580 return false; 581 } 582 583 size_t compressed_len = temp_entries[nextentry].second.compressed_length; 584 ImageChunk curr(CHUNK_DEFLATE, pos, zip_file, compressed_len); 585 curr.SetEntryName(std::move(entryname)); 586 curr.SetUncompressedData(std::move(uncompressed_data)); 587 chunks->push_back(curr); 588 589 pos += compressed_len; 590 ++nextentry; 591 continue; 592 } 593 594 // Use a normal chunk to take all the data up to the start of the next deflate section. 595 size_t raw_data_len; 596 if (nextentry < temp_entries.size()) { 597 raw_data_len = temp_entries[nextentry].second.offset - pos; 598 } else { 599 raw_data_len = zip_file->size() - pos; 600 } 601 chunks->emplace_back(CHUNK_NORMAL, pos, zip_file, raw_data_len); 602 603 pos += raw_data_len; 604 } 605 606 CloseArchive(handle); 607 return true; 608 } 609 610 // Read the given file and break it up into chunks, and putting the data in to a vector. 611 static bool ReadImage(const char* filename, std::vector<ImageChunk>* chunks, 612 std::vector<uint8_t>* img) { 613 CHECK(chunks != nullptr && img != nullptr); 614 615 android::base::unique_fd fd(open(filename, O_RDONLY)); 616 if (fd == -1) { 617 printf("failed to open \"%s\" %s\n", filename, strerror(errno)); 618 return false; 619 } 620 struct stat st; 621 if (fstat(fd, &st) != 0) { 622 printf("failed to stat \"%s\": %s\n", filename, strerror(errno)); 623 return false; 624 } 625 626 size_t sz = static_cast<size_t>(st.st_size); 627 img->resize(sz); 628 if (!android::base::ReadFully(fd, img->data(), sz)) { 629 printf("failed to read \"%s\" %s\n", filename, strerror(errno)); 630 return false; 631 } 632 633 size_t pos = 0; 634 635 while (pos < sz) { 636 // 0x00 no header flags, 0x08 deflate compression, 0x1f8b gzip magic number 637 if (sz - pos >= 4 && get_unaligned<uint32_t>(img->data() + pos) == 0x00088b1f) { 638 // 'pos' is the offset of the start of a gzip chunk. 639 size_t chunk_offset = pos; 640 641 // The remaining data is too small to be a gzip chunk; treat them as a normal chunk. 642 if (sz - pos < GZIP_HEADER_LEN + GZIP_FOOTER_LEN) { 643 chunks->emplace_back(CHUNK_NORMAL, pos, img, sz - pos); 644 break; 645 } 646 647 // We need three chunks for the deflated image in total, one normal chunk for the header, 648 // one deflated chunk for the body, and another normal chunk for the footer. 649 chunks->emplace_back(CHUNK_NORMAL, pos, img, GZIP_HEADER_LEN); 650 pos += GZIP_HEADER_LEN; 651 652 // We must decompress this chunk in order to discover where it ends, and so we can update 653 // the uncompressed_data of the image body and its length. 654 655 z_stream strm; 656 strm.zalloc = Z_NULL; 657 strm.zfree = Z_NULL; 658 strm.opaque = Z_NULL; 659 strm.avail_in = sz - pos; 660 strm.next_in = img->data() + pos; 661 662 // -15 means we are decoding a 'raw' deflate stream; zlib will 663 // not expect zlib headers. 664 int ret = inflateInit2(&strm, -15); 665 if (ret < 0) { 666 printf("failed to initialize inflate: %d\n", ret); 667 return false; 668 } 669 670 size_t allocated = BUFFER_SIZE; 671 std::vector<uint8_t> uncompressed_data(allocated); 672 size_t uncompressed_len = 0, raw_data_len = 0; 673 do { 674 strm.avail_out = allocated - uncompressed_len; 675 strm.next_out = uncompressed_data.data() + uncompressed_len; 676 ret = inflate(&strm, Z_NO_FLUSH); 677 if (ret < 0) { 678 printf("Warning: inflate failed [%s] at offset [%zu], treating as a normal chunk\n", 679 strm.msg, chunk_offset); 680 break; 681 } 682 uncompressed_len = allocated - strm.avail_out; 683 if (strm.avail_out == 0) { 684 allocated *= 2; 685 uncompressed_data.resize(allocated); 686 } 687 } while (ret != Z_STREAM_END); 688 689 raw_data_len = sz - strm.avail_in - pos; 690 inflateEnd(&strm); 691 692 if (ret < 0) { 693 continue; 694 } 695 696 // The footer contains the size of the uncompressed data. Double-check to make sure that it 697 // matches the size of the data we got when we actually did the decompression. 698 size_t footer_index = pos + raw_data_len + GZIP_FOOTER_LEN - 4; 699 if (sz - footer_index < 4) { 700 printf("Warning: invalid footer position; treating as a nomal chunk\n"); 701 continue; 702 } 703 size_t footer_size = get_unaligned<uint32_t>(img->data() + footer_index); 704 if (footer_size != uncompressed_len) { 705 printf("Warning: footer size %zu != decompressed size %zu; treating as a nomal chunk\n", 706 footer_size, uncompressed_len); 707 continue; 708 } 709 710 ImageChunk body(CHUNK_DEFLATE, pos, img, raw_data_len); 711 uncompressed_data.resize(uncompressed_len); 712 body.SetUncompressedData(std::move(uncompressed_data)); 713 chunks->push_back(body); 714 715 pos += raw_data_len; 716 717 // create a normal chunk for the footer 718 chunks->emplace_back(CHUNK_NORMAL, pos, img, GZIP_FOOTER_LEN); 719 720 pos += GZIP_FOOTER_LEN; 721 } else { 722 // Use a normal chunk to take all the contents until the next gzip chunk (or EOF); we expect 723 // the number of chunks to be small (5 for typical boot and recovery images). 724 725 // Scan forward until we find a gzip header. 726 size_t data_len = 0; 727 while (data_len + pos < sz) { 728 if (data_len + pos + 4 <= sz && 729 get_unaligned<uint32_t>(img->data() + pos + data_len) == 0x00088b1f) { 730 break; 731 } 732 data_len++; 733 } 734 chunks->emplace_back(CHUNK_NORMAL, pos, img, data_len); 735 736 pos += data_len; 737 } 738 } 739 740 return true; 741 } 742 743 /* 744 * Given source and target chunks, compute a bsdiff patch between them. 745 * Store the result in the patch_data. 746 * |bsdiff_cache| can be used to cache the suffix array if the same |src| chunk 747 * is used repeatedly, pass nullptr if not needed. 748 */ 749 static bool MakePatch(const ImageChunk* src, ImageChunk* tgt, std::vector<uint8_t>* patch_data, 750 saidx_t** bsdiff_cache) { 751 if (tgt->ChangeChunkToRaw(0)) { 752 size_t patch_size = tgt->DataLengthForPatch(); 753 patch_data->resize(patch_size); 754 std::copy(tgt->DataForPatch(), tgt->DataForPatch() + patch_size, patch_data->begin()); 755 return true; 756 } 757 758 #if defined(__ANDROID__) 759 char ptemp[] = "/data/local/tmp/imgdiff-patch-XXXXXX"; 760 #else 761 char ptemp[] = "/tmp/imgdiff-patch-XXXXXX"; 762 #endif 763 764 int fd = mkstemp(ptemp); 765 if (fd == -1) { 766 printf("MakePatch failed to create a temporary file: %s\n", strerror(errno)); 767 return false; 768 } 769 close(fd); 770 771 int r = bsdiff::bsdiff(src->DataForPatch(), src->DataLengthForPatch(), tgt->DataForPatch(), 772 tgt->DataLengthForPatch(), ptemp, bsdiff_cache); 773 if (r != 0) { 774 printf("bsdiff() failed: %d\n", r); 775 return false; 776 } 777 778 android::base::unique_fd patch_fd(open(ptemp, O_RDONLY)); 779 if (patch_fd == -1) { 780 printf("failed to open %s: %s\n", ptemp, strerror(errno)); 781 return false; 782 } 783 struct stat st; 784 if (fstat(patch_fd, &st) != 0) { 785 printf("failed to stat patch file %s: %s\n", ptemp, strerror(errno)); 786 return false; 787 } 788 789 size_t sz = static_cast<size_t>(st.st_size); 790 // Change the chunk type to raw if the patch takes less space that way. 791 if (tgt->ChangeChunkToRaw(sz)) { 792 unlink(ptemp); 793 size_t patch_size = tgt->DataLengthForPatch(); 794 patch_data->resize(patch_size); 795 std::copy(tgt->DataForPatch(), tgt->DataForPatch() + patch_size, patch_data->begin()); 796 return true; 797 } 798 patch_data->resize(sz); 799 if (!android::base::ReadFully(patch_fd, patch_data->data(), sz)) { 800 printf("failed to read \"%s\" %s\n", ptemp, strerror(errno)); 801 return false; 802 } 803 804 unlink(ptemp); 805 tgt->SetSourceInfo(*src); 806 807 return true; 808 } 809 810 /* 811 * Look for runs of adjacent normal chunks and compress them down into 812 * a single chunk. (Such runs can be produced when deflate chunks are 813 * changed to normal chunks.) 814 */ 815 static void MergeAdjacentNormalChunks(std::vector<ImageChunk>* chunks) { 816 size_t merged_last = 0, cur = 0; 817 while (cur < chunks->size()) { 818 // Look for normal chunks adjacent to the current one. If such chunk exists, extend the 819 // length of the current normal chunk. 820 size_t to_check = cur + 1; 821 while (to_check < chunks->size() && chunks->at(cur).IsAdjacentNormal(chunks->at(to_check))) { 822 chunks->at(cur).MergeAdjacentNormal(chunks->at(to_check)); 823 to_check++; 824 } 825 826 if (merged_last != cur) { 827 chunks->at(merged_last) = std::move(chunks->at(cur)); 828 } 829 merged_last++; 830 cur = to_check; 831 } 832 if (merged_last < chunks->size()) { 833 chunks->erase(chunks->begin() + merged_last, chunks->end()); 834 } 835 } 836 837 static ImageChunk* FindChunkByName(const std::string& name, std::vector<ImageChunk>& chunks) { 838 for (size_t i = 0; i < chunks.size(); ++i) { 839 if (chunks[i].GetType() == CHUNK_DEFLATE && chunks[i].GetEntryName() == name) { 840 return &chunks[i]; 841 } 842 } 843 return nullptr; 844 } 845 846 static void DumpChunks(const std::vector<ImageChunk>& chunks) { 847 for (size_t i = 0; i < chunks.size(); ++i) { 848 printf("chunk %zu: ", i); 849 chunks[i].Dump(); 850 } 851 } 852 853 int imgdiff(int argc, const char** argv) { 854 bool zip_mode = false; 855 856 if (argc >= 2 && strcmp(argv[1], "-z") == 0) { 857 zip_mode = true; 858 --argc; 859 ++argv; 860 } 861 862 std::vector<uint8_t> bonus_data; 863 if (argc >= 3 && strcmp(argv[1], "-b") == 0) { 864 android::base::unique_fd fd(open(argv[2], O_RDONLY)); 865 if (fd == -1) { 866 printf("failed to open bonus file %s: %s\n", argv[2], strerror(errno)); 867 return 1; 868 } 869 struct stat st; 870 if (fstat(fd, &st) != 0) { 871 printf("failed to stat bonus file %s: %s\n", argv[2], strerror(errno)); 872 return 1; 873 } 874 875 size_t bonus_size = st.st_size; 876 bonus_data.resize(bonus_size); 877 if (!android::base::ReadFully(fd, bonus_data.data(), bonus_size)) { 878 printf("failed to read bonus file %s: %s\n", argv[2], strerror(errno)); 879 return 1; 880 } 881 882 argc -= 2; 883 argv += 2; 884 } 885 886 if (argc != 4) { 887 printf("usage: %s [-z] [-b <bonus-file>] <src-img> <tgt-img> <patch-file>\n", 888 argv[0]); 889 return 2; 890 } 891 892 std::vector<ImageChunk> src_chunks; 893 std::vector<ImageChunk> tgt_chunks; 894 std::vector<uint8_t> src_file; 895 std::vector<uint8_t> tgt_file; 896 897 if (zip_mode) { 898 if (!ReadZip(argv[1], &src_chunks, &src_file, true)) { 899 printf("failed to break apart source zip file\n"); 900 return 1; 901 } 902 if (!ReadZip(argv[2], &tgt_chunks, &tgt_file, false)) { 903 printf("failed to break apart target zip file\n"); 904 return 1; 905 } 906 } else { 907 if (!ReadImage(argv[1], &src_chunks, &src_file)) { 908 printf("failed to break apart source image\n"); 909 return 1; 910 } 911 if (!ReadImage(argv[2], &tgt_chunks, &tgt_file)) { 912 printf("failed to break apart target image\n"); 913 return 1; 914 } 915 916 // Verify that the source and target images have the same chunk 917 // structure (ie, the same sequence of deflate and normal chunks). 918 919 // Merge the gzip header and footer in with any adjacent normal chunks. 920 MergeAdjacentNormalChunks(&tgt_chunks); 921 MergeAdjacentNormalChunks(&src_chunks); 922 923 if (src_chunks.size() != tgt_chunks.size()) { 924 printf("source and target don't have same number of chunks!\n"); 925 printf("source chunks:\n"); 926 DumpChunks(src_chunks); 927 printf("target chunks:\n"); 928 DumpChunks(tgt_chunks); 929 return 1; 930 } 931 for (size_t i = 0; i < src_chunks.size(); ++i) { 932 if (src_chunks[i].GetType() != tgt_chunks[i].GetType()) { 933 printf("source and target don't have same chunk structure! (chunk %zu)\n", i); 934 printf("source chunks:\n"); 935 DumpChunks(src_chunks); 936 printf("target chunks:\n"); 937 DumpChunks(tgt_chunks); 938 return 1; 939 } 940 } 941 } 942 943 for (size_t i = 0; i < tgt_chunks.size(); ++i) { 944 if (tgt_chunks[i].GetType() == CHUNK_DEFLATE) { 945 // Confirm that given the uncompressed chunk data in the target, we 946 // can recompress it and get exactly the same bits as are in the 947 // input target image. If this fails, treat the chunk as a normal 948 // non-deflated chunk. 949 if (!tgt_chunks[i].ReconstructDeflateChunk()) { 950 printf("failed to reconstruct target deflate chunk %zu [%s]; treating as normal\n", i, 951 tgt_chunks[i].GetEntryName().c_str()); 952 tgt_chunks[i].ChangeDeflateChunkToNormal(); 953 if (zip_mode) { 954 ImageChunk* src = FindChunkByName(tgt_chunks[i].GetEntryName(), src_chunks); 955 if (src != nullptr) { 956 src->ChangeDeflateChunkToNormal(); 957 } 958 } else { 959 src_chunks[i].ChangeDeflateChunkToNormal(); 960 } 961 continue; 962 } 963 964 // If two deflate chunks are identical (eg, the kernel has not 965 // changed between two builds), treat them as normal chunks. 966 // This makes applypatch much faster -- it can apply a trivial 967 // patch to the compressed data, rather than uncompressing and 968 // recompressing to apply the trivial patch to the uncompressed 969 // data. 970 ImageChunk* src; 971 if (zip_mode) { 972 src = FindChunkByName(tgt_chunks[i].GetEntryName(), src_chunks); 973 } else { 974 src = &src_chunks[i]; 975 } 976 977 if (src == nullptr) { 978 tgt_chunks[i].ChangeDeflateChunkToNormal(); 979 } else if (tgt_chunks[i] == *src) { 980 tgt_chunks[i].ChangeDeflateChunkToNormal(); 981 src->ChangeDeflateChunkToNormal(); 982 } 983 } 984 } 985 986 // Merging neighboring normal chunks. 987 if (zip_mode) { 988 // For zips, we only need to do this to the target: deflated 989 // chunks are matched via filename, and normal chunks are patched 990 // using the entire source file as the source. 991 MergeAdjacentNormalChunks(&tgt_chunks); 992 993 } else { 994 // For images, we need to maintain the parallel structure of the 995 // chunk lists, so do the merging in both the source and target 996 // lists. 997 MergeAdjacentNormalChunks(&tgt_chunks); 998 MergeAdjacentNormalChunks(&src_chunks); 999 if (src_chunks.size() != tgt_chunks.size()) { 1000 // This shouldn't happen. 1001 printf("merging normal chunks went awry\n"); 1002 return 1; 1003 } 1004 } 1005 1006 // Compute bsdiff patches for each chunk's data (the uncompressed 1007 // data, in the case of deflate chunks). 1008 1009 DumpChunks(src_chunks); 1010 1011 printf("Construct patches for %zu chunks...\n", tgt_chunks.size()); 1012 std::vector<std::vector<uint8_t>> patch_data(tgt_chunks.size()); 1013 saidx_t* bsdiff_cache = nullptr; 1014 for (size_t i = 0; i < tgt_chunks.size(); ++i) { 1015 if (zip_mode) { 1016 ImageChunk* src; 1017 if (tgt_chunks[i].GetType() == CHUNK_DEFLATE && 1018 (src = FindChunkByName(tgt_chunks[i].GetEntryName(), src_chunks))) { 1019 if (!MakePatch(src, &tgt_chunks[i], &patch_data[i], nullptr)) { 1020 printf("Failed to generate patch for target chunk %zu: ", i); 1021 return 1; 1022 } 1023 } else { 1024 if (!MakePatch(&src_chunks[0], &tgt_chunks[i], &patch_data[i], &bsdiff_cache)) { 1025 printf("Failed to generate patch for target chunk %zu: ", i); 1026 return 1; 1027 } 1028 } 1029 } else { 1030 if (i == 1 && !bonus_data.empty()) { 1031 printf(" using %zu bytes of bonus data for chunk %zu\n", bonus_data.size(), i); 1032 src_chunks[i].SetBonusData(bonus_data); 1033 } 1034 1035 if (!MakePatch(&src_chunks[i], &tgt_chunks[i], &patch_data[i], nullptr)) { 1036 printf("Failed to generate patch for target chunk %zu: ", i); 1037 return 1; 1038 } 1039 } 1040 printf("patch %3zu is %zu bytes (of %zu)\n", i, patch_data[i].size(), 1041 src_chunks[i].GetRawDataLength()); 1042 } 1043 1044 if (bsdiff_cache != nullptr) { 1045 free(bsdiff_cache); 1046 } 1047 1048 // Figure out how big the imgdiff file header is going to be, so 1049 // that we can correctly compute the offset of each bsdiff patch 1050 // within the file. 1051 1052 size_t total_header_size = 12; 1053 for (size_t i = 0; i < tgt_chunks.size(); ++i) { 1054 total_header_size += tgt_chunks[i].GetHeaderSize(patch_data[i].size()); 1055 } 1056 1057 size_t offset = total_header_size; 1058 1059 android::base::unique_fd patch_fd(open(argv[3], O_CREAT | O_WRONLY | O_TRUNC, S_IRUSR | S_IWUSR)); 1060 if (patch_fd == -1) { 1061 printf("failed to open \"%s\": %s\n", argv[3], strerror(errno)); 1062 return 1; 1063 } 1064 1065 // Write out the headers. 1066 if (!android::base::WriteStringToFd("IMGDIFF2", patch_fd)) { 1067 printf("failed to write \"IMGDIFF2\" to \"%s\": %s\n", argv[3], strerror(errno)); 1068 return 1; 1069 } 1070 Write4(patch_fd, static_cast<int32_t>(tgt_chunks.size())); 1071 for (size_t i = 0; i < tgt_chunks.size(); ++i) { 1072 printf("chunk %zu: ", i); 1073 offset = tgt_chunks[i].WriteHeaderToFd(patch_fd, patch_data[i], offset); 1074 } 1075 1076 // Append each chunk's bsdiff patch, in order. 1077 for (size_t i = 0; i < tgt_chunks.size(); ++i) { 1078 if (tgt_chunks[i].GetType() != CHUNK_RAW) { 1079 if (!android::base::WriteFully(patch_fd, patch_data[i].data(), patch_data[i].size())) { 1080 CHECK(false) << "failed to write " << patch_data[i].size() << " bytes patch for chunk " 1081 << i; 1082 } 1083 } 1084 } 1085 1086 return 0; 1087 } 1088