blob: 41d73ab985881ac015d8e4b2f7c3c6d8c10fef9c [file] [log] [blame]
Doug Zongker512536a2010-02-17 16:11:44 -08001/*
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 Zongkera3ccba62012-08-20 15:28:02 -0700114 *
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 Zongker512536a2010-02-17 16:11:44 -0800122 */
123
Tao Bao97555da2016-12-15 10:15:06 -0800124#include "applypatch/imgdiff.h"
125
Doug Zongker512536a2010-02-17 16:11:44 -0800126#include <errno.h>
Tao Baod37ce8f2016-12-17 17:10:04 -0800127#include <fcntl.h>
Doug Zongker512536a2010-02-17 16:11:44 -0800128#include <stdio.h>
129#include <stdlib.h>
130#include <string.h>
131#include <sys/stat.h>
Doug Zongker512536a2010-02-17 16:11:44 -0800132#include <sys/types.h>
Tao Bao97555da2016-12-15 10:15:06 -0800133#include <unistd.h>
Doug Zongker512536a2010-02-17 16:11:44 -0800134
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800135#include <algorithm>
136#include <string>
137#include <vector>
138
Tao Baod37ce8f2016-12-17 17:10:04 -0800139#include <android-base/file.h>
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800140#include <android-base/logging.h>
141#include <android-base/memory.h>
Tao Baod37ce8f2016-12-17 17:10:04 -0800142#include <android-base/unique_fd.h>
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800143#include <ziparchive/zip_archive.h>
Tao Baod37ce8f2016-12-17 17:10:04 -0800144
Sen Jiang2fffcb12016-05-03 15:49:10 -0700145#include <bsdiff.h>
Tao Bao97555da2016-12-15 10:15:06 -0800146#include <zlib.h>
Sen Jiang2fffcb12016-05-03 15:49:10 -0700147
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800148using android::base::get_unaligned;
Doug Zongker512536a2010-02-17 16:11:44 -0800149
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800150static constexpr auto BUFFER_SIZE = 0x8000;
Doug Zongker512536a2010-02-17 16:11:44 -0800151
Tianjie Xu12b90552017-03-07 14:44:14 -0800152// 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.
154static 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).
160static inline bool Write4(int fd, int32_t value) {
161 return android::base::WriteFully(fd, &value, sizeof(int32_t));
162}
163
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800164class 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),
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800176 compress_level_(6),
177 source_start_(0),
178 source_len_(0),
Tianjie Xu12b90552017-03-07 14:44:14 -0800179 source_uncompressed_len_(0) {
180 CHECK(file_content != nullptr) << "input file container can't be nullptr";
181 }
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800182
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;
Tianjie Xu12b90552017-03-07 14:44:14 -0800213 // 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);
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800215
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:
Tianjie Xu12b90552017-03-07 14:44:14 -0800237 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
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800240 size_t raw_data_len_;
Doug Zongker512536a2010-02-17 16:11:44 -0800241
Doug Zongker512536a2010-02-17 16:11:44 -0800242 // --- for CHUNK_DEFLATE chunks only: ---
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800243 std::vector<uint8_t> uncompressed_data_;
244 std::string entry_name_; // used for zip entries
Doug Zongker512536a2010-02-17 16:11:44 -0800245
246 // deflate encoder parameters
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800247 int compress_level_;
Doug Zongker512536a2010-02-17 16:11:44 -0800248
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800249 size_t source_start_;
250 size_t source_len_;
251 size_t source_uncompressed_len_;
Doug Zongker512536a2010-02-17 16:11:44 -0800252
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800253 const uint8_t* GetRawData() const;
254 bool TryReconstruction(int level);
255};
Doug Zongker512536a2010-02-17 16:11:44 -0800256
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800257const 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
262const uint8_t * ImageChunk::DataForPatch() const {
263 if (type_ == CHUNK_DEFLATE) {
264 return uncompressed_data_.data();
265 }
266 return GetRawData();
267}
268
269size_t ImageChunk::DataLengthForPatch() const {
270 if (type_ == CHUNK_DEFLATE) {
271 return uncompressed_data_.size();
272 }
273 return raw_data_len_;
274}
275
276bool 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
284void 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();
Tao Baoa0c40112016-06-01 13:15:44 -0700291 }
Doug Zongker512536a2010-02-17 16:11:44 -0800292}
293
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800294void ImageChunk::SetEntryName(std::string entryname) {
Tianjie Xu12b90552017-03-07 14:44:14 -0800295 entry_name_ = std::move(entryname);
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800296}
297
298void ImageChunk::SetUncompressedData(std::vector<uint8_t> data) {
Tianjie Xu12b90552017-03-07 14:44:14 -0800299 uncompressed_data_ = std::move(data);
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800300}
301
302bool 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
Tianjie Xu12b90552017-03-07 14:44:14 -0800310// Convert CHUNK_NORMAL & CHUNK_DEFLATE to CHUNK_RAW if the target size is
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800311// smaller. Also take the header size into account during size comparison.
312bool 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
322void ImageChunk::ChangeDeflateChunkToNormal() {
323 if (type_ != CHUNK_DEFLATE) return;
324 type_ = CHUNK_NORMAL;
Tianjie Xu12b90552017-03-07 14:44:14 -0800325 entry_name_.clear();
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800326 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
Tianjie Xu12b90552017-03-07 14:44:14 -0800333// CHUNK_RAW 4 bytes + patch_size
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800334size_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:
Tianjie Xu12b90552017-03-07 14:44:14 -0800343 CHECK(false) << "unexpected chunk type: " << type_; // Should not reach here.
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800344 return 0;
345 }
346}
347
Tianjie Xu12b90552017-03-07 14:44:14 -0800348size_t ImageChunk::WriteHeaderToFd(int fd, const std::vector<uint8_t>& patch, size_t offset) {
349 Write4(fd, type_);
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800350 switch (type_) {
351 case CHUNK_NORMAL:
352 printf("normal (%10zu, %10zu) %10zu\n", start_, raw_data_len_, patch.size());
Tianjie Xu12b90552017-03-07 14:44:14 -0800353 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));
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800356 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());
Tianjie Xu12b90552017-03-07 14:44:14 -0800360 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);
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800370 return offset + patch.size();
371 case CHUNK_RAW:
372 printf("raw (%10zu, %10zu)\n", start_, raw_data_len_);
Tianjie Xu12b90552017-03-07 14:44:14 -0800373 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 }
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800377 return offset;
378 default:
Tianjie Xu12b90552017-03-07 14:44:14 -0800379 CHECK(false) << "unexpected chunk type: " << type_;
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800380 return offset;
381 }
382}
383
384bool 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
391void ImageChunk::MergeAdjacentNormal(const ImageChunk& other) {
392 CHECK(IsAdjacentNormal(other));
393 raw_data_len_ = raw_data_len_ + other.raw_data_len_;
394}
395
396bool ImageChunk::ReconstructDeflateChunk() {
397 if (type_ != CHUNK_DEFLATE) {
398 printf("attempt to reconstruct non-deflate chunk\n");
399 return false;
Doug Zongker512536a2010-02-17 16:11:44 -0800400 }
401
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800402 // 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;
Doug Zongker512536a2010-02-17 16:11:44 -0800408 }
409 }
Doug Zongker512536a2010-02-17 16:11:44 -0800410
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800411 return false;
Doug Zongker512536a2010-02-17 16:11:44 -0800412}
413
414/*
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800415 * 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).
Doug Zongker512536a2010-02-17 16:11:44 -0800419 */
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800420bool 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
467static 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
494static bool ReadZip(const char* filename, std::vector<ImageChunk>* chunks,
495 std::vector<uint8_t>* zip_file, bool include_pseudo_chunk) {
Tianjie Xu12b90552017-03-07 14:44:14 -0800496 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 }
Doug Zongker512536a2010-02-17 16:11:44 -0800503 struct stat st;
Tianjie Xu12b90552017-03-07 14:44:14 -0800504 if (fstat(fd, &st) != 0) {
Doug Zongker512536a2010-02-17 16:11:44 -0800505 printf("failed to stat \"%s\": %s\n", filename, strerror(errno));
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800506 return false;
Doug Zongker512536a2010-02-17 16:11:44 -0800507 }
508
Tao Baoba9a42a2015-06-23 23:23:33 -0700509 size_t sz = static_cast<size_t>(st.st_size);
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800510 zip_file->resize(sz);
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800511 if (!android::base::ReadFully(fd, zip_file->data(), sz)) {
Doug Zongker512536a2010-02-17 16:11:44 -0800512 printf("failed to read \"%s\" %s\n", filename, strerror(errno));
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800513 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.
611static bool ReadImage(const char* filename, std::vector<ImageChunk>* chunks,
612 std::vector<uint8_t>* img) {
Tianjie Xu12b90552017-03-07 14:44:14 -0800613 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 }
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800620 struct stat st;
Tianjie Xu12b90552017-03-07 14:44:14 -0800621 if (fstat(fd, &st) != 0) {
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800622 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);
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800628 if (!android::base::ReadFully(fd, img->data(), sz)) {
629 printf("failed to read \"%s\" %s\n", filename, strerror(errno));
630 return false;
Doug Zongker512536a2010-02-17 16:11:44 -0800631 }
Doug Zongker512536a2010-02-17 16:11:44 -0800632
633 size_t pos = 0;
634
Tao Baoba9a42a2015-06-23 23:23:33 -0700635 while (pos < sz) {
Tianjie Xu12b90552017-03-07 14:44:14 -0800636 // 0x00 no header flags, 0x08 deflate compression, 0x1f8b gzip magic number
637 if (sz - pos >= 4 && get_unaligned<uint32_t>(img->data() + pos) == 0x00088b1f) {
Doug Zongker512536a2010-02-17 16:11:44 -0800638 // 'pos' is the offset of the start of a gzip chunk.
Johan Redestigc68bd342015-04-14 21:20:06 +0200639 size_t chunk_offset = pos;
Doug Zongker512536a2010-02-17 16:11:44 -0800640
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800641 // 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 }
Doug Zongker512536a2010-02-17 16:11:44 -0800646
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800647 // 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;
Doug Zongker512536a2010-02-17 16:11:44 -0800651
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800652 // 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.
Doug Zongker512536a2010-02-17 16:11:44 -0800654
655 z_stream strm;
656 strm.zalloc = Z_NULL;
657 strm.zfree = Z_NULL;
658 strm.opaque = Z_NULL;
Tao Baoba9a42a2015-06-23 23:23:33 -0700659 strm.avail_in = sz - pos;
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800660 strm.next_in = img->data() + pos;
Doug Zongker512536a2010-02-17 16:11:44 -0800661
662 // -15 means we are decoding a 'raw' deflate stream; zlib will
663 // not expect zlib headers.
664 int ret = inflateInit2(&strm, -15);
Rahul Chaudhrya793c582016-11-29 17:10:14 -0800665 if (ret < 0) {
666 printf("failed to initialize inflate: %d\n", ret);
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800667 return false;
Rahul Chaudhrya793c582016-11-29 17:10:14 -0800668 }
Doug Zongker512536a2010-02-17 16:11:44 -0800669
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800670 size_t allocated = BUFFER_SIZE;
671 std::vector<uint8_t> uncompressed_data(allocated);
672 size_t uncompressed_len = 0, raw_data_len = 0;
Doug Zongker512536a2010-02-17 16:11:44 -0800673 do {
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800674 strm.avail_out = allocated - uncompressed_len;
675 strm.next_out = uncompressed_data.data() + uncompressed_len;
Doug Zongker512536a2010-02-17 16:11:44 -0800676 ret = inflate(&strm, Z_NO_FLUSH);
Johan Redestigc68bd342015-04-14 21:20:06 +0200677 if (ret < 0) {
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800678 printf("Warning: inflate failed [%s] at offset [%zu], treating as a normal chunk\n",
David Riley0779fc92015-12-10 10:18:25 -0800679 strm.msg, chunk_offset);
Sen Jiangfa4f1b72016-02-11 16:14:23 -0800680 break;
Johan Redestigc68bd342015-04-14 21:20:06 +0200681 }
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800682 uncompressed_len = allocated - strm.avail_out;
Doug Zongker512536a2010-02-17 16:11:44 -0800683 if (strm.avail_out == 0) {
684 allocated *= 2;
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800685 uncompressed_data.resize(allocated);
Doug Zongker512536a2010-02-17 16:11:44 -0800686 }
687 } while (ret != Z_STREAM_END);
688
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800689 raw_data_len = sz - strm.avail_in - pos;
Doug Zongker512536a2010-02-17 16:11:44 -0800690 inflateEnd(&strm);
Sen Jiangfa4f1b72016-02-11 16:14:23 -0800691
692 if (ret < 0) {
Sen Jiangfa4f1b72016-02-11 16:14:23 -0800693 continue;
694 }
695
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800696 ImageChunk body(CHUNK_DEFLATE, pos, img, raw_data_len);
697 uncompressed_data.resize(uncompressed_len);
698 body.SetUncompressedData(std::move(uncompressed_data));
699 chunks->push_back(body);
700
701 pos += raw_data_len;
Doug Zongker512536a2010-02-17 16:11:44 -0800702
703 // create a normal chunk for the footer
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800704 chunks->emplace_back(CHUNK_NORMAL, pos, img, GZIP_FOOTER_LEN);
Doug Zongker512536a2010-02-17 16:11:44 -0800705
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800706 pos += GZIP_FOOTER_LEN;
Doug Zongker512536a2010-02-17 16:11:44 -0800707
708 // The footer (that we just skipped over) contains the size of
709 // the uncompressed data. Double-check to make sure that it
710 // matches the size of the data we got when we actually did
711 // the decompression.
Tianjie Xu12b90552017-03-07 14:44:14 -0800712 size_t footer_size = get_unaligned<uint32_t>(img->data() + pos - 4);
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800713 if (footer_size != body.DataLengthForPatch()) {
714 printf("Error: footer size %zu != decompressed size %zu\n", footer_size,
715 body.GetRawDataLength());
716 return false;
Doug Zongker512536a2010-02-17 16:11:44 -0800717 }
718 } else {
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800719 // Use a normal chunk to take all the contents until the next gzip chunk (or EOF); we expect
720 // the number of chunks to be small (5 for typical boot and recovery images).
Doug Zongker512536a2010-02-17 16:11:44 -0800721
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800722 // Scan forward until we find a gzip header.
723 size_t data_len = 0;
724 while (data_len + pos < sz) {
Tianjie Xu12b90552017-03-07 14:44:14 -0800725 if (data_len + pos + 4 <= sz &&
726 get_unaligned<uint32_t>(img->data() + pos + data_len) == 0x00088b1f) {
Doug Zongker512536a2010-02-17 16:11:44 -0800727 break;
728 }
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800729 data_len++;
Doug Zongker512536a2010-02-17 16:11:44 -0800730 }
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800731 chunks->emplace_back(CHUNK_NORMAL, pos, img, data_len);
732
733 pos += data_len;
Doug Zongker512536a2010-02-17 16:11:44 -0800734 }
735 }
736
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800737 return true;
Doug Zongker512536a2010-02-17 16:11:44 -0800738}
739
740/*
Sen Jiang930edb62017-01-18 17:26:42 -0800741 * Given source and target chunks, compute a bsdiff patch between them.
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800742 * Store the result in the patch_data.
Sen Jiang930edb62017-01-18 17:26:42 -0800743 * |bsdiff_cache| can be used to cache the suffix array if the same |src| chunk
744 * is used repeatedly, pass nullptr if not needed.
Doug Zongker512536a2010-02-17 16:11:44 -0800745 */
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800746static bool MakePatch(const ImageChunk* src, ImageChunk* tgt, std::vector<uint8_t>* patch_data,
747 saidx_t** bsdiff_cache) {
748 if (tgt->ChangeChunkToRaw(0)) {
749 size_t patch_size = tgt->DataLengthForPatch();
750 patch_data->resize(patch_size);
751 std::copy(tgt->DataForPatch(), tgt->DataForPatch() + patch_size, patch_data->begin());
752 return true;
Doug Zongker512536a2010-02-17 16:11:44 -0800753 }
754
Tao Bao97555da2016-12-15 10:15:06 -0800755#if defined(__ANDROID__)
756 char ptemp[] = "/data/local/tmp/imgdiff-patch-XXXXXX";
757#else
Doug Zongker512536a2010-02-17 16:11:44 -0800758 char ptemp[] = "/tmp/imgdiff-patch-XXXXXX";
Tao Bao97555da2016-12-15 10:15:06 -0800759#endif
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800760
Jeremy Compostellaa91c66d2015-09-08 19:15:09 +0200761 int fd = mkstemp(ptemp);
Jeremy Compostellaa91c66d2015-09-08 19:15:09 +0200762 if (fd == -1) {
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800763 printf("MakePatch failed to create a temporary file: %s\n", strerror(errno));
764 return false;
Jeremy Compostellaa91c66d2015-09-08 19:15:09 +0200765 }
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800766 close(fd);
Doug Zongker512536a2010-02-17 16:11:44 -0800767
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800768 int r = bsdiff::bsdiff(src->DataForPatch(), src->DataLengthForPatch(), tgt->DataForPatch(),
769 tgt->DataLengthForPatch(), ptemp, bsdiff_cache);
Doug Zongker512536a2010-02-17 16:11:44 -0800770 if (r != 0) {
771 printf("bsdiff() failed: %d\n", r);
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800772 return false;
Doug Zongker512536a2010-02-17 16:11:44 -0800773 }
774
Tianjie Xu12b90552017-03-07 14:44:14 -0800775 android::base::unique_fd patch_fd(open(ptemp, O_RDONLY));
776 if (patch_fd == -1) {
777 printf("failed to open %s: %s\n", ptemp, strerror(errno));
778 return false;
779 }
Doug Zongker512536a2010-02-17 16:11:44 -0800780 struct stat st;
Tianjie Xu12b90552017-03-07 14:44:14 -0800781 if (fstat(patch_fd, &st) != 0) {
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800782 printf("failed to stat patch file %s: %s\n", ptemp, strerror(errno));
783 return false;
Doug Zongker512536a2010-02-17 16:11:44 -0800784 }
785
Tao Baoba9a42a2015-06-23 23:23:33 -0700786 size_t sz = static_cast<size_t>(st.st_size);
Tianjie Xu12b90552017-03-07 14:44:14 -0800787 // Change the chunk type to raw if the patch takes less space that way.
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800788 if (tgt->ChangeChunkToRaw(sz)) {
Doug Zongker512536a2010-02-17 16:11:44 -0800789 unlink(ptemp);
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800790 size_t patch_size = tgt->DataLengthForPatch();
791 patch_data->resize(patch_size);
792 std::copy(tgt->DataForPatch(), tgt->DataForPatch() + patch_size, patch_data->begin());
793 return true;
Doug Zongker512536a2010-02-17 16:11:44 -0800794 }
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800795 patch_data->resize(sz);
796 if (!android::base::ReadFully(patch_fd, patch_data->data(), sz)) {
797 printf("failed to read \"%s\" %s\n", ptemp, strerror(errno));
798 return false;
Doug Zongker512536a2010-02-17 16:11:44 -0800799 }
Doug Zongker512536a2010-02-17 16:11:44 -0800800
801 unlink(ptemp);
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800802 tgt->SetSourceInfo(*src);
Doug Zongker512536a2010-02-17 16:11:44 -0800803
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800804 return true;
Doug Zongker512536a2010-02-17 16:11:44 -0800805}
806
807/*
808 * Look for runs of adjacent normal chunks and compress them down into
809 * a single chunk. (Such runs can be produced when deflate chunks are
810 * changed to normal chunks.)
811 */
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800812static void MergeAdjacentNormalChunks(std::vector<ImageChunk>* chunks) {
813 size_t merged_last = 0, cur = 0;
814 while (cur < chunks->size()) {
815 // Look for normal chunks adjacent to the current one. If such chunk exists, extend the
816 // length of the current normal chunk.
817 size_t to_check = cur + 1;
818 while (to_check < chunks->size() && chunks->at(cur).IsAdjacentNormal(chunks->at(to_check))) {
819 chunks->at(cur).MergeAdjacentNormal(chunks->at(to_check));
820 to_check++;
Doug Zongker512536a2010-02-17 16:11:44 -0800821 }
822
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800823 if (merged_last != cur) {
824 chunks->at(merged_last) = std::move(chunks->at(cur));
Doug Zongker512536a2010-02-17 16:11:44 -0800825 }
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800826 merged_last++;
827 cur = to_check;
Doug Zongker512536a2010-02-17 16:11:44 -0800828 }
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800829 if (merged_last < chunks->size()) {
830 chunks->erase(chunks->begin() + merged_last, chunks->end());
831 }
Doug Zongker512536a2010-02-17 16:11:44 -0800832}
833
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800834static ImageChunk* FindChunkByName(const std::string& name, std::vector<ImageChunk>& chunks) {
835 for (size_t i = 0; i < chunks.size(); ++i) {
836 if (chunks[i].GetType() == CHUNK_DEFLATE && chunks[i].GetEntryName() == name) {
837 return &chunks[i];
Doug Zongker512536a2010-02-17 16:11:44 -0800838 }
839 }
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800840 return nullptr;
Doug Zongker512536a2010-02-17 16:11:44 -0800841}
842
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800843static void DumpChunks(const std::vector<ImageChunk>& chunks) {
844 for (size_t i = 0; i < chunks.size(); ++i) {
845 printf("chunk %zu: ", i);
846 chunks[i].Dump();
847 }
Doug Zongker512536a2010-02-17 16:11:44 -0800848}
849
Tao Bao97555da2016-12-15 10:15:06 -0800850int imgdiff(int argc, const char** argv) {
851 bool zip_mode = false;
Doug Zongker512536a2010-02-17 16:11:44 -0800852
Doug Zongkera3ccba62012-08-20 15:28:02 -0700853 if (argc >= 2 && strcmp(argv[1], "-z") == 0) {
Tao Bao97555da2016-12-15 10:15:06 -0800854 zip_mode = true;
Doug Zongker512536a2010-02-17 16:11:44 -0800855 --argc;
856 ++argv;
857 }
858
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800859 std::vector<uint8_t> bonus_data;
Doug Zongkera3ccba62012-08-20 15:28:02 -0700860 if (argc >= 3 && strcmp(argv[1], "-b") == 0) {
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800861 android::base::unique_fd fd(open(argv[2], O_RDONLY));
862 if (fd == -1) {
Doug Zongkera3ccba62012-08-20 15:28:02 -0700863 printf("failed to open bonus file %s: %s\n", argv[2], strerror(errno));
864 return 1;
865 }
Tianjie Xu12b90552017-03-07 14:44:14 -0800866 struct stat st;
867 if (fstat(fd, &st) != 0) {
868 printf("failed to stat bonus file %s: %s\n", argv[2], strerror(errno));
869 return 1;
870 }
871
872 size_t bonus_size = st.st_size;
873 bonus_data.resize(bonus_size);
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800874 if (!android::base::ReadFully(fd, bonus_data.data(), bonus_size)) {
Doug Zongkera3ccba62012-08-20 15:28:02 -0700875 printf("failed to read bonus file %s: %s\n", argv[2], strerror(errno));
876 return 1;
877 }
Doug Zongkera3ccba62012-08-20 15:28:02 -0700878
879 argc -= 2;
880 argv += 2;
881 }
882
883 if (argc != 4) {
Doug Zongkera3ccba62012-08-20 15:28:02 -0700884 printf("usage: %s [-z] [-b <bonus-file>] <src-img> <tgt-img> <patch-file>\n",
885 argv[0]);
886 return 2;
887 }
Doug Zongker512536a2010-02-17 16:11:44 -0800888
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800889 std::vector<ImageChunk> src_chunks;
890 std::vector<ImageChunk> tgt_chunks;
891 std::vector<uint8_t> src_file;
892 std::vector<uint8_t> tgt_file;
Doug Zongker512536a2010-02-17 16:11:44 -0800893
894 if (zip_mode) {
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800895 if (!ReadZip(argv[1], &src_chunks, &src_file, true)) {
Doug Zongker512536a2010-02-17 16:11:44 -0800896 printf("failed to break apart source zip file\n");
897 return 1;
898 }
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800899 if (!ReadZip(argv[2], &tgt_chunks, &tgt_file, false)) {
Doug Zongker512536a2010-02-17 16:11:44 -0800900 printf("failed to break apart target zip file\n");
901 return 1;
902 }
903 } else {
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800904 if (!ReadImage(argv[1], &src_chunks, &src_file)) {
Doug Zongker512536a2010-02-17 16:11:44 -0800905 printf("failed to break apart source image\n");
906 return 1;
907 }
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800908 if (!ReadImage(argv[2], &tgt_chunks, &tgt_file)) {
Doug Zongker512536a2010-02-17 16:11:44 -0800909 printf("failed to break apart target image\n");
910 return 1;
911 }
912
913 // Verify that the source and target images have the same chunk
914 // structure (ie, the same sequence of deflate and normal chunks).
915
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800916 // Merge the gzip header and footer in with any adjacent normal chunks.
917 MergeAdjacentNormalChunks(&tgt_chunks);
918 MergeAdjacentNormalChunks(&src_chunks);
Doug Zongker512536a2010-02-17 16:11:44 -0800919
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800920 if (src_chunks.size() != tgt_chunks.size()) {
Doug Zongker512536a2010-02-17 16:11:44 -0800921 printf("source and target don't have same number of chunks!\n");
922 printf("source chunks:\n");
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800923 DumpChunks(src_chunks);
Doug Zongker512536a2010-02-17 16:11:44 -0800924 printf("target chunks:\n");
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800925 DumpChunks(tgt_chunks);
Doug Zongker512536a2010-02-17 16:11:44 -0800926 return 1;
927 }
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800928 for (size_t i = 0; i < src_chunks.size(); ++i) {
929 if (src_chunks[i].GetType() != tgt_chunks[i].GetType()) {
930 printf("source and target don't have same chunk structure! (chunk %zu)\n", i);
Doug Zongker512536a2010-02-17 16:11:44 -0800931 printf("source chunks:\n");
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800932 DumpChunks(src_chunks);
Doug Zongker512536a2010-02-17 16:11:44 -0800933 printf("target chunks:\n");
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800934 DumpChunks(tgt_chunks);
Doug Zongker512536a2010-02-17 16:11:44 -0800935 return 1;
936 }
937 }
938 }
939
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800940 for (size_t i = 0; i < tgt_chunks.size(); ++i) {
941 if (tgt_chunks[i].GetType() == CHUNK_DEFLATE) {
Doug Zongker512536a2010-02-17 16:11:44 -0800942 // Confirm that given the uncompressed chunk data in the target, we
943 // can recompress it and get exactly the same bits as are in the
944 // input target image. If this fails, treat the chunk as a normal
945 // non-deflated chunk.
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800946 if (!tgt_chunks[i].ReconstructDeflateChunk()) {
947 printf("failed to reconstruct target deflate chunk %zu [%s]; treating as normal\n", i,
948 tgt_chunks[i].GetEntryName().c_str());
949 tgt_chunks[i].ChangeDeflateChunkToNormal();
Doug Zongker512536a2010-02-17 16:11:44 -0800950 if (zip_mode) {
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800951 ImageChunk* src = FindChunkByName(tgt_chunks[i].GetEntryName(), src_chunks);
952 if (src != nullptr) {
953 src->ChangeDeflateChunkToNormal();
Doug Zongker512536a2010-02-17 16:11:44 -0800954 }
955 } else {
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800956 src_chunks[i].ChangeDeflateChunkToNormal();
Doug Zongker512536a2010-02-17 16:11:44 -0800957 }
958 continue;
959 }
960
961 // If two deflate chunks are identical (eg, the kernel has not
962 // changed between two builds), treat them as normal chunks.
963 // This makes applypatch much faster -- it can apply a trivial
964 // patch to the compressed data, rather than uncompressing and
965 // recompressing to apply the trivial patch to the uncompressed
966 // data.
967 ImageChunk* src;
968 if (zip_mode) {
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800969 src = FindChunkByName(tgt_chunks[i].GetEntryName(), src_chunks);
Doug Zongker512536a2010-02-17 16:11:44 -0800970 } else {
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800971 src = &src_chunks[i];
Doug Zongker512536a2010-02-17 16:11:44 -0800972 }
973
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800974 if (src == nullptr) {
975 tgt_chunks[i].ChangeDeflateChunkToNormal();
976 } else if (tgt_chunks[i] == *src) {
977 tgt_chunks[i].ChangeDeflateChunkToNormal();
978 src->ChangeDeflateChunkToNormal();
Doug Zongker512536a2010-02-17 16:11:44 -0800979 }
980 }
981 }
982
983 // Merging neighboring normal chunks.
984 if (zip_mode) {
985 // For zips, we only need to do this to the target: deflated
986 // chunks are matched via filename, and normal chunks are patched
987 // using the entire source file as the source.
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800988 MergeAdjacentNormalChunks(&tgt_chunks);
989
Doug Zongker512536a2010-02-17 16:11:44 -0800990 } else {
991 // For images, we need to maintain the parallel structure of the
992 // chunk lists, so do the merging in both the source and target
993 // lists.
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800994 MergeAdjacentNormalChunks(&tgt_chunks);
995 MergeAdjacentNormalChunks(&src_chunks);
996 if (src_chunks.size() != tgt_chunks.size()) {
Doug Zongker512536a2010-02-17 16:11:44 -0800997 // This shouldn't happen.
998 printf("merging normal chunks went awry\n");
999 return 1;
1000 }
1001 }
1002
1003 // Compute bsdiff patches for each chunk's data (the uncompressed
1004 // data, in the case of deflate chunks).
1005
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001006 DumpChunks(src_chunks);
Doug Zongkera3ccba62012-08-20 15:28:02 -07001007
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001008 printf("Construct patches for %zu chunks...\n", tgt_chunks.size());
1009 std::vector<std::vector<uint8_t>> patch_data(tgt_chunks.size());
Sen Jiang930edb62017-01-18 17:26:42 -08001010 saidx_t* bsdiff_cache = nullptr;
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001011 for (size_t i = 0; i < tgt_chunks.size(); ++i) {
Doug Zongker512536a2010-02-17 16:11:44 -08001012 if (zip_mode) {
1013 ImageChunk* src;
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001014 if (tgt_chunks[i].GetType() == CHUNK_DEFLATE &&
1015 (src = FindChunkByName(tgt_chunks[i].GetEntryName(), src_chunks))) {
Tianjie Xu12b90552017-03-07 14:44:14 -08001016 if (!MakePatch(src, &tgt_chunks[i], &patch_data[i], nullptr)) {
1017 printf("Failed to generate patch for target chunk %zu: ", i);
1018 return 1;
1019 }
Doug Zongker512536a2010-02-17 16:11:44 -08001020 } else {
Tianjie Xu12b90552017-03-07 14:44:14 -08001021 if (!MakePatch(&src_chunks[0], &tgt_chunks[i], &patch_data[i], &bsdiff_cache)) {
1022 printf("Failed to generate patch for target chunk %zu: ", i);
1023 return 1;
1024 }
Doug Zongker512536a2010-02-17 16:11:44 -08001025 }
1026 } else {
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001027 if (i == 1 && !bonus_data.empty()) {
1028 printf(" using %zu bytes of bonus data for chunk %zu\n", bonus_data.size(), i);
1029 src_chunks[i].SetBonusData(bonus_data);
Sen Jiang930edb62017-01-18 17:26:42 -08001030 }
Doug Zongkera3ccba62012-08-20 15:28:02 -07001031
Tianjie Xu12b90552017-03-07 14:44:14 -08001032 if (!MakePatch(&src_chunks[i], &tgt_chunks[i], &patch_data[i], nullptr)) {
1033 printf("Failed to generate patch for target chunk %zu: ", i);
1034 return 1;
1035 }
Doug Zongker512536a2010-02-17 16:11:44 -08001036 }
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001037 printf("patch %3zu is %zu bytes (of %zu)\n", i, patch_data[i].size(),
1038 src_chunks[i].GetRawDataLength());
Doug Zongker512536a2010-02-17 16:11:44 -08001039 }
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001040
1041 if (bsdiff_cache != nullptr) {
1042 free(bsdiff_cache);
1043 }
Doug Zongker512536a2010-02-17 16:11:44 -08001044
1045 // Figure out how big the imgdiff file header is going to be, so
1046 // that we can correctly compute the offset of each bsdiff patch
1047 // within the file.
1048
1049 size_t total_header_size = 12;
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001050 for (size_t i = 0; i < tgt_chunks.size(); ++i) {
1051 total_header_size += tgt_chunks[i].GetHeaderSize(patch_data[i].size());
Doug Zongker512536a2010-02-17 16:11:44 -08001052 }
1053
1054 size_t offset = total_header_size;
1055
Tianjie Xu12b90552017-03-07 14:44:14 -08001056 android::base::unique_fd patch_fd(open(argv[3], O_CREAT | O_WRONLY | O_TRUNC, S_IRUSR | S_IWUSR));
1057 if (patch_fd == -1) {
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001058 printf("failed to open \"%s\": %s\n", argv[3], strerror(errno));
Tianjie Xu12b90552017-03-07 14:44:14 -08001059 return 1;
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001060 }
Doug Zongker512536a2010-02-17 16:11:44 -08001061
1062 // Write out the headers.
Tianjie Xu12b90552017-03-07 14:44:14 -08001063 if (!android::base::WriteStringToFd("IMGDIFF2", patch_fd)) {
1064 printf("failed to write \"IMGDIFF2\" to \"%s\": %s\n", argv[3], strerror(errno));
1065 return 1;
1066 }
1067 Write4(patch_fd, static_cast<int32_t>(tgt_chunks.size()));
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001068 for (size_t i = 0; i < tgt_chunks.size(); ++i) {
1069 printf("chunk %zu: ", i);
Tianjie Xu12b90552017-03-07 14:44:14 -08001070 offset = tgt_chunks[i].WriteHeaderToFd(patch_fd, patch_data[i], offset);
Doug Zongker512536a2010-02-17 16:11:44 -08001071 }
1072
1073 // Append each chunk's bsdiff patch, in order.
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001074 for (size_t i = 0; i < tgt_chunks.size(); ++i) {
1075 if (tgt_chunks[i].GetType() != CHUNK_RAW) {
Tianjie Xu12b90552017-03-07 14:44:14 -08001076 if (!android::base::WriteFully(patch_fd, patch_data[i].data(), patch_data[i].size())) {
1077 CHECK(false) << "failed to write " << patch_data[i].size() << " bytes patch for chunk "
1078 << i;
1079 }
Doug Zongker512536a2010-02-17 16:11:44 -08001080 }
1081 }
1082
Doug Zongker512536a2010-02-17 16:11:44 -08001083 return 0;
1084}