blob: 3a61a7d0debd5ce3d39c495eebf540194c868cf0 [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/*
Tianjie Xu82582b42017-08-31 18:05:19 -070018 * This program constructs binary patches for images -- such as boot.img and recovery.img -- that
19 * consist primarily of large chunks of gzipped data interspersed with uncompressed data. Doing a
20 * naive bsdiff of these files is not useful because small changes in the data lead to large
21 * changes in the compressed bitstream; bsdiff patches of gzipped data are typically as large as
22 * the data itself.
Doug Zongker512536a2010-02-17 16:11:44 -080023 *
Tianjie Xu82582b42017-08-31 18:05:19 -070024 * To patch these usefully, we break the source and target images up into chunks of two types:
25 * "normal" and "gzip". Normal chunks are simply patched using a plain bsdiff. Gzip chunks are
26 * first expanded, then a bsdiff is applied to the uncompressed data, then the patched data is
27 * gzipped using the same encoder parameters. Patched chunks are concatenated together to create
28 * the output file; the output image should be *exactly* the same series of bytes as the target
29 * image used originally to generate the patch.
Doug Zongker512536a2010-02-17 16:11:44 -080030 *
Tianjie Xu82582b42017-08-31 18:05:19 -070031 * To work well with this tool, the gzipped sections of the target image must have been generated
32 * using the same deflate encoder that is available in applypatch, namely, the one in the zlib
33 * library. In practice this means that images should be compressed using the "minigzip" tool
34 * included in the zlib distribution, not the GNU gzip program.
Doug Zongker512536a2010-02-17 16:11:44 -080035 *
Tianjie Xu82582b42017-08-31 18:05:19 -070036 * An "imgdiff" patch consists of a header describing the chunk structure of the file and any
37 * encoding parameters needed for the gzipped chunks, followed by N bsdiff patches, one per chunk.
Doug Zongker512536a2010-02-17 16:11:44 -080038 *
Tianjie Xu82582b42017-08-31 18:05:19 -070039 * For a diff to be generated, the source and target must be in well-formed zip archive format;
40 * or they are image files with the same "chunk" structure: that is, the same number of gzipped and
41 * normal chunks in the same order. Android boot and recovery images currently consist of five
42 * chunks: a small normal header, a gzipped kernel, a small normal section, a gzipped ramdisk, and
43 * finally a small normal footer.
Doug Zongker512536a2010-02-17 16:11:44 -080044 *
Tianjie Xu82582b42017-08-31 18:05:19 -070045 * Caveats: we locate gzipped sections within the source and target images by searching for the
46 * byte sequence 1f8b0800: 1f8b is the gzip magic number; 08 specifies the "deflate" encoding
47 * [the only encoding supported by the gzip standard]; and 00 is the flags byte. We do not
48 * currently support any extra header fields (which would be indicated by a nonzero flags byte).
49 * We also don't handle the case when that byte sequence appears spuriously in the file. (Note
50 * that it would have to occur spuriously within a normal chunk to be a problem.)
Doug Zongker512536a2010-02-17 16:11:44 -080051 *
52 *
53 * The imgdiff patch header looks like this:
54 *
Tianjie Xu82582b42017-08-31 18:05:19 -070055 * "IMGDIFF2" (8) [magic number and version]
Doug Zongker512536a2010-02-17 16:11:44 -080056 * chunk count (4)
57 * for each chunk:
58 * chunk type (4) [CHUNK_{NORMAL, GZIP, DEFLATE, RAW}]
59 * if chunk type == CHUNK_NORMAL:
60 * source start (8)
61 * source len (8)
62 * bsdiff patch offset (8) [from start of patch file]
63 * if chunk type == CHUNK_GZIP: (version 1 only)
64 * source start (8)
65 * source len (8)
66 * bsdiff patch offset (8) [from start of patch file]
67 * source expanded len (8) [size of uncompressed source]
68 * target expected len (8) [size of uncompressed target]
69 * gzip level (4)
70 * method (4)
71 * windowBits (4)
72 * memLevel (4)
73 * strategy (4)
74 * gzip header len (4)
75 * gzip header (gzip header len)
76 * gzip footer (8)
77 * if chunk type == CHUNK_DEFLATE: (version 2 only)
78 * source start (8)
79 * source len (8)
80 * bsdiff patch offset (8) [from start of patch file]
81 * source expanded len (8) [size of uncompressed source]
82 * target expected len (8) [size of uncompressed target]
83 * gzip level (4)
84 * method (4)
85 * windowBits (4)
86 * memLevel (4)
87 * strategy (4)
88 * if chunk type == RAW: (version 2 only)
89 * target len (4)
90 * data (target len)
91 *
Tianjie Xu82582b42017-08-31 18:05:19 -070092 * All integers are little-endian. "source start" and "source len" specify the section of the
93 * input image that comprises this chunk, including the gzip header and footer for gzip chunks.
94 * "source expanded len" is the size of the uncompressed source data. "target expected len" is the
95 * size of the uncompressed data after applying the bsdiff patch. The next five parameters
96 * specify the zlib parameters to be used when compressing the patched data, and the next three
97 * specify the header and footer to be wrapped around the compressed data to create the output
98 * chunk (so that header contents like the timestamp are recreated exactly).
Doug Zongker512536a2010-02-17 16:11:44 -080099 *
Tianjie Xu82582b42017-08-31 18:05:19 -0700100 * After the header there are 'chunk count' bsdiff patches; the offset of each from the beginning
101 * of the file is specified in the header.
Doug Zongkera3ccba62012-08-20 15:28:02 -0700102 *
Tianjie Xu82582b42017-08-31 18:05:19 -0700103 * This tool can take an optional file of "bonus data". This is an extra file of data that is
104 * appended to chunk #1 after it is compressed (it must be a CHUNK_DEFLATE chunk). The same file
105 * must be available (and passed to applypatch with -b) when applying the patch. This is used to
106 * reduce the size of recovery-from-boot patches by combining the boot image with recovery ramdisk
Doug Zongkera3ccba62012-08-20 15:28:02 -0700107 * information that is stored on the system partition.
Tianjie Xu82582b42017-08-31 18:05:19 -0700108 *
109 * When generating the patch between two zip files, this tool has an option "--block-limit" to
110 * split the large source/target files into several pair of pieces, with each piece has at most
111 * *limit* blocks. When this option is used, we also need to output the split info into the file
112 * path specified by "--split-info".
113 *
114 * Format of split info file:
115 * 2 [version of imgdiff]
116 * n [count of split pieces]
117 * <patch_size>, <tgt_size>, <src_range> [size and ranges for split piece#1]
118 * ...
119 * <patch_size>, <tgt_size>, <src_range> [size and ranges for split piece#n]
120 *
121 * To split a pair of large zip files, we walk through the chunks in target zip and search by its
122 * entry_name in the source zip. If the entry_name is non-empty and a matching entry in source
123 * is found, we'll add the source entry to the current split source image; otherwise we'll skip
124 * this chunk and later do bsdiff between all the skipped trunks and the whole split source image.
125 * We move on to the next pair of pieces if the size of the split source image reaches the block
126 * limit.
127 *
128 * After the split, the target pieces are continuous and block aligned, while the source pieces
129 * are mutually exclusive. Some of the source blocks may not be used if there's no matching
130 * entry_name in the target; as a result, they won't be included in any of these split source
131 * images. Then we will generate patches accordingly between each split image pairs; in particular,
132 * the unmatched trunks in the split target will diff against the entire split source image.
133 *
134 * For example:
135 * Input: [src_image, tgt_image]
136 * Split: [src-0, tgt-0; src-1, tgt-1, src-2, tgt-2]
137 * Diff: [ patch-0; patch-1; patch-2]
138 *
139 * Patch: [(src-0, patch-0) = tgt-0; (src-1, patch-1) = tgt-1; (src-2, patch-2) = tgt-2]
140 * Concatenate: [tgt-0 + tgt-1 + tgt-2 = tgt_image]
Doug Zongker512536a2010-02-17 16:11:44 -0800141 */
142
Tao Bao97555da2016-12-15 10:15:06 -0800143#include "applypatch/imgdiff.h"
144
Doug Zongker512536a2010-02-17 16:11:44 -0800145#include <errno.h>
Tao Baod37ce8f2016-12-17 17:10:04 -0800146#include <fcntl.h>
Tianjie Xu2903cdd2017-08-18 18:15:47 -0700147#include <getopt.h>
Doug Zongker512536a2010-02-17 16:11:44 -0800148#include <stdio.h>
149#include <stdlib.h>
150#include <string.h>
151#include <sys/stat.h>
Doug Zongker512536a2010-02-17 16:11:44 -0800152#include <sys/types.h>
Tao Bao97555da2016-12-15 10:15:06 -0800153#include <unistd.h>
Doug Zongker512536a2010-02-17 16:11:44 -0800154
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800155#include <algorithm>
156#include <string>
157#include <vector>
158
Tao Baod37ce8f2016-12-17 17:10:04 -0800159#include <android-base/file.h>
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800160#include <android-base/logging.h>
161#include <android-base/memory.h>
Tianjie Xu2903cdd2017-08-18 18:15:47 -0700162#include <android-base/parseint.h>
Tao Baod37ce8f2016-12-17 17:10:04 -0800163#include <android-base/unique_fd.h>
Sen Jiang2fffcb12016-05-03 15:49:10 -0700164#include <bsdiff.h>
Tianjie Xu57dd9612017-08-17 17:50:56 -0700165#include <ziparchive/zip_archive.h>
Tao Bao97555da2016-12-15 10:15:06 -0800166#include <zlib.h>
Sen Jiang2fffcb12016-05-03 15:49:10 -0700167
Tianjie Xu57dd9612017-08-17 17:50:56 -0700168#include "applypatch/imgdiff_image.h"
Tao Bao09e468f2017-09-29 14:39:33 -0700169#include "otautil/rangeset.h"
Tianjie Xu57dd9612017-08-17 17:50:56 -0700170
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800171using android::base::get_unaligned;
Doug Zongker512536a2010-02-17 16:11:44 -0800172
Tianjie Xu82582b42017-08-31 18:05:19 -0700173static constexpr size_t VERSION = 2;
174
175// We assume the header "IMGDIFF#" is 8 bytes.
176static_assert(VERSION <= 9, "VERSION occupies more than one byte.");
177
Tianjie Xu2903cdd2017-08-18 18:15:47 -0700178static constexpr size_t BLOCK_SIZE = 4096;
179static constexpr size_t BUFFER_SIZE = 0x8000;
Doug Zongker512536a2010-02-17 16:11:44 -0800180
Tianjie Xu12b90552017-03-07 14:44:14 -0800181// If we use this function to write the offset and length (type size_t), their values should not
182// exceed 2^63; because the signed bit will be casted away.
183static inline bool Write8(int fd, int64_t value) {
184 return android::base::WriteFully(fd, &value, sizeof(int64_t));
185}
186
187// Similarly, the value should not exceed 2^31 if we are casting from size_t (e.g. target chunk
188// size).
189static inline bool Write4(int fd, int32_t value) {
190 return android::base::WriteFully(fd, &value, sizeof(int32_t));
191}
192
Tianjie Xu2903cdd2017-08-18 18:15:47 -0700193// Trim the head or tail to align with the block size. Return false if the chunk has nothing left
194// after alignment.
195static bool AlignHead(size_t* start, size_t* length) {
196 size_t residual = (*start % BLOCK_SIZE == 0) ? 0 : BLOCK_SIZE - *start % BLOCK_SIZE;
197
198 if (*length <= residual) {
199 *length = 0;
200 return false;
201 }
202
203 // Trim the data in the beginning.
204 *start += residual;
205 *length -= residual;
206 return true;
207}
208
209static bool AlignTail(size_t* start, size_t* length) {
210 size_t residual = (*start + *length) % BLOCK_SIZE;
211 if (*length <= residual) {
212 *length = 0;
213 return false;
214 }
215
216 // Trim the data in the end.
217 *length -= residual;
218 return true;
219}
220
221// Remove the used blocks from the source chunk to make sure the source ranges are mutually
222// exclusive after split. Return false if we fail to get the non-overlapped ranges. In such
223// a case, we'll skip the entire source chunk.
224static bool RemoveUsedBlocks(size_t* start, size_t* length, const SortedRangeSet& used_ranges) {
225 if (!used_ranges.Overlaps(*start, *length)) {
226 return true;
227 }
228
229 // TODO find the largest non-overlap chunk.
230 printf("Removing block %s from %zu - %zu\n", used_ranges.ToString().c_str(), *start,
231 *start + *length - 1);
232
233 // If there's no duplicate entry name, we should only overlap in the head or tail block. Try to
234 // trim both blocks. Skip this source chunk in case it still overlaps with the used ranges.
235 if (AlignHead(start, length) && !used_ranges.Overlaps(*start, *length)) {
236 return true;
237 }
238 if (AlignTail(start, length) && !used_ranges.Overlaps(*start, *length)) {
239 return true;
240 }
241
242 printf("Failed to remove the overlapped block ranges; skip the source\n");
243 return false;
244}
245
246static const struct option OPTIONS[] = {
247 { "zip-mode", no_argument, nullptr, 'z' },
248 { "bonus-file", required_argument, nullptr, 'b' },
249 { "block-limit", required_argument, nullptr, 0 },
250 { "debug-dir", required_argument, nullptr, 0 },
Tianjie Xu82582b42017-08-31 18:05:19 -0700251 { "split-info", required_argument, nullptr, 0 },
Tianjie Xu2903cdd2017-08-18 18:15:47 -0700252 { nullptr, 0, nullptr, 0 },
253};
254
Tianjie Xu57dd9612017-08-17 17:50:56 -0700255ImageChunk::ImageChunk(int type, size_t start, const std::vector<uint8_t>* file_content,
256 size_t raw_data_len, std::string entry_name)
257 : type_(type),
258 start_(start),
259 input_file_ptr_(file_content),
260 raw_data_len_(raw_data_len),
261 compress_level_(6),
262 entry_name_(std::move(entry_name)) {
263 CHECK(file_content != nullptr) << "input file container can't be nullptr";
264}
Doug Zongker512536a2010-02-17 16:11:44 -0800265
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800266const uint8_t* ImageChunk::GetRawData() const {
267 CHECK_LE(start_ + raw_data_len_, input_file_ptr_->size());
268 return input_file_ptr_->data() + start_;
269}
270
271const uint8_t * ImageChunk::DataForPatch() const {
272 if (type_ == CHUNK_DEFLATE) {
273 return uncompressed_data_.data();
274 }
275 return GetRawData();
276}
277
278size_t ImageChunk::DataLengthForPatch() const {
279 if (type_ == CHUNK_DEFLATE) {
280 return uncompressed_data_.size();
281 }
282 return raw_data_len_;
283}
284
285bool ImageChunk::operator==(const ImageChunk& other) const {
286 if (type_ != other.type_) {
287 return false;
288 }
289 return (raw_data_len_ == other.raw_data_len_ &&
290 memcmp(GetRawData(), other.GetRawData(), raw_data_len_) == 0);
291}
292
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800293void ImageChunk::SetUncompressedData(std::vector<uint8_t> data) {
Tianjie Xu12b90552017-03-07 14:44:14 -0800294 uncompressed_data_ = std::move(data);
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800295}
296
297bool ImageChunk::SetBonusData(const std::vector<uint8_t>& bonus_data) {
298 if (type_ != CHUNK_DEFLATE) {
299 return false;
300 }
301 uncompressed_data_.insert(uncompressed_data_.end(), bonus_data.begin(), bonus_data.end());
302 return true;
303}
304
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800305void ImageChunk::ChangeDeflateChunkToNormal() {
306 if (type_ != CHUNK_DEFLATE) return;
307 type_ = CHUNK_NORMAL;
Tianjie Xu6b03ba72017-07-19 14:16:30 -0700308 // No need to clear the entry name.
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800309 uncompressed_data_.clear();
310}
311
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800312bool ImageChunk::IsAdjacentNormal(const ImageChunk& other) const {
313 if (type_ != CHUNK_NORMAL || other.type_ != CHUNK_NORMAL) {
314 return false;
315 }
316 return (other.start_ == start_ + raw_data_len_);
317}
318
319void ImageChunk::MergeAdjacentNormal(const ImageChunk& other) {
320 CHECK(IsAdjacentNormal(other));
321 raw_data_len_ = raw_data_len_ + other.raw_data_len_;
322}
323
Tianjie Xud82a2ed2017-08-08 17:35:01 -0700324bool ImageChunk::MakePatch(const ImageChunk& tgt, const ImageChunk& src,
325 std::vector<uint8_t>* patch_data, saidx_t** bsdiff_cache) {
Tianjie Xu6b03ba72017-07-19 14:16:30 -0700326#if defined(__ANDROID__)
327 char ptemp[] = "/data/local/tmp/imgdiff-patch-XXXXXX";
328#else
329 char ptemp[] = "/tmp/imgdiff-patch-XXXXXX";
330#endif
331
332 int fd = mkstemp(ptemp);
333 if (fd == -1) {
334 printf("MakePatch failed to create a temporary file: %s\n", strerror(errno));
335 return false;
336 }
337 close(fd);
338
Tianjie Xud82a2ed2017-08-08 17:35:01 -0700339 int r = bsdiff::bsdiff(src.DataForPatch(), src.DataLengthForPatch(), tgt.DataForPatch(),
340 tgt.DataLengthForPatch(), ptemp, bsdiff_cache);
Tianjie Xu6b03ba72017-07-19 14:16:30 -0700341 if (r != 0) {
342 printf("bsdiff() failed: %d\n", r);
343 return false;
344 }
345
346 android::base::unique_fd patch_fd(open(ptemp, O_RDONLY));
347 if (patch_fd == -1) {
348 printf("failed to open %s: %s\n", ptemp, strerror(errno));
349 return false;
350 }
351 struct stat st;
352 if (fstat(patch_fd, &st) != 0) {
353 printf("failed to stat patch file %s: %s\n", ptemp, strerror(errno));
354 return false;
355 }
356
357 size_t sz = static_cast<size_t>(st.st_size);
Tianjie Xud82a2ed2017-08-08 17:35:01 -0700358
Tianjie Xu6b03ba72017-07-19 14:16:30 -0700359 patch_data->resize(sz);
360 if (!android::base::ReadFully(patch_fd, patch_data->data(), sz)) {
361 printf("failed to read \"%s\" %s\n", ptemp, strerror(errno));
362 unlink(ptemp);
363 return false;
364 }
365
366 unlink(ptemp);
Tianjie Xu6b03ba72017-07-19 14:16:30 -0700367
368 return true;
369}
370
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800371bool ImageChunk::ReconstructDeflateChunk() {
372 if (type_ != CHUNK_DEFLATE) {
373 printf("attempt to reconstruct non-deflate chunk\n");
374 return false;
Doug Zongker512536a2010-02-17 16:11:44 -0800375 }
376
Tianjie Xud82a2ed2017-08-08 17:35:01 -0700377 // We only check two combinations of encoder parameters: level 6 (the default) and level 9
378 // (the maximum).
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800379 for (int level = 6; level <= 9; level += 3) {
380 if (TryReconstruction(level)) {
381 compress_level_ = level;
382 return true;
Doug Zongker512536a2010-02-17 16:11:44 -0800383 }
384 }
Doug Zongker512536a2010-02-17 16:11:44 -0800385
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800386 return false;
Doug Zongker512536a2010-02-17 16:11:44 -0800387}
388
389/*
Tianjie Xud82a2ed2017-08-08 17:35:01 -0700390 * Takes the uncompressed data stored in the chunk, compresses it using the zlib parameters stored
391 * in the chunk, and checks that it matches exactly the compressed data we started with (also
392 * stored in the chunk).
Doug Zongker512536a2010-02-17 16:11:44 -0800393 */
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800394bool ImageChunk::TryReconstruction(int level) {
395 z_stream strm;
396 strm.zalloc = Z_NULL;
397 strm.zfree = Z_NULL;
398 strm.opaque = Z_NULL;
399 strm.avail_in = uncompressed_data_.size();
400 strm.next_in = uncompressed_data_.data();
401 int ret = deflateInit2(&strm, level, METHOD, WINDOWBITS, MEMLEVEL, STRATEGY);
402 if (ret < 0) {
403 printf("failed to initialize deflate: %d\n", ret);
404 return false;
405 }
406
407 std::vector<uint8_t> buffer(BUFFER_SIZE);
408 size_t offset = 0;
409 do {
410 strm.avail_out = buffer.size();
411 strm.next_out = buffer.data();
412 ret = deflate(&strm, Z_FINISH);
413 if (ret < 0) {
414 printf("failed to deflate: %d\n", ret);
415 return false;
416 }
417
418 size_t compressed_size = buffer.size() - strm.avail_out;
419 if (memcmp(buffer.data(), input_file_ptr_->data() + start_ + offset, compressed_size) != 0) {
420 // mismatch; data isn't the same.
421 deflateEnd(&strm);
422 return false;
423 }
424 offset += compressed_size;
425 } while (ret != Z_STREAM_END);
426 deflateEnd(&strm);
427
428 if (offset != raw_data_len_) {
429 // mismatch; ran out of data before we should have.
430 return false;
431 }
432 return true;
433}
434
Tianjie Xu57dd9612017-08-17 17:50:56 -0700435PatchChunk::PatchChunk(const ImageChunk& tgt, const ImageChunk& src, std::vector<uint8_t> data)
436 : type_(tgt.GetType()),
437 source_start_(src.GetStartOffset()),
438 source_len_(src.GetRawDataLength()),
439 source_uncompressed_len_(src.DataLengthForPatch()),
440 target_start_(tgt.GetStartOffset()),
441 target_len_(tgt.GetRawDataLength()),
442 target_uncompressed_len_(tgt.DataLengthForPatch()),
443 target_compress_level_(tgt.GetCompressLevel()),
444 data_(std::move(data)) {}
Tianjie Xud82a2ed2017-08-08 17:35:01 -0700445
Tianjie Xu57dd9612017-08-17 17:50:56 -0700446// Construct a CHUNK_RAW patch from the target data directly.
447PatchChunk::PatchChunk(const ImageChunk& tgt)
448 : type_(CHUNK_RAW),
449 source_start_(0),
450 source_len_(0),
451 source_uncompressed_len_(0),
452 target_start_(tgt.GetStartOffset()),
453 target_len_(tgt.GetRawDataLength()),
454 target_uncompressed_len_(tgt.DataLengthForPatch()),
455 target_compress_level_(tgt.GetCompressLevel()),
456 data_(tgt.DataForPatch(), tgt.DataForPatch() + tgt.DataLengthForPatch()) {}
Tianjie Xud82a2ed2017-08-08 17:35:01 -0700457
458// Return true if raw data is smaller than the patch size.
459bool PatchChunk::RawDataIsSmaller(const ImageChunk& tgt, size_t patch_size) {
460 size_t target_len = tgt.GetRawDataLength();
461 return (tgt.GetType() == CHUNK_NORMAL && (target_len <= 160 || target_len < patch_size));
462}
463
Tianjie Xu2903cdd2017-08-18 18:15:47 -0700464void PatchChunk::UpdateSourceOffset(const SortedRangeSet& src_range) {
465 if (type_ == CHUNK_DEFLATE) {
466 source_start_ = src_range.GetOffsetInRangeSet(source_start_);
467 }
468}
469
Tianjie Xud82a2ed2017-08-08 17:35:01 -0700470// Header size:
471// header_type 4 bytes
472// CHUNK_NORMAL 8*3 = 24 bytes
473// CHUNK_DEFLATE 8*5 + 4*5 = 60 bytes
474// CHUNK_RAW 4 bytes + patch_size
475size_t PatchChunk::GetHeaderSize() const {
476 switch (type_) {
477 case CHUNK_NORMAL:
478 return 4 + 8 * 3;
479 case CHUNK_DEFLATE:
480 return 4 + 8 * 5 + 4 * 5;
481 case CHUNK_RAW:
482 return 4 + 4 + data_.size();
483 default:
484 CHECK(false) << "unexpected chunk type: " << type_; // Should not reach here.
485 return 0;
486 }
487}
488
489// Return the offset of the next patch into the patch data.
490size_t PatchChunk::WriteHeaderToFd(int fd, size_t offset) const {
491 Write4(fd, type_);
492 switch (type_) {
493 case CHUNK_NORMAL:
494 printf("normal (%10zu, %10zu) %10zu\n", target_start_, target_len_, data_.size());
495 Write8(fd, static_cast<int64_t>(source_start_));
496 Write8(fd, static_cast<int64_t>(source_len_));
497 Write8(fd, static_cast<int64_t>(offset));
498 return offset + data_.size();
499 case CHUNK_DEFLATE:
500 printf("deflate (%10zu, %10zu) %10zu\n", target_start_, target_len_, data_.size());
501 Write8(fd, static_cast<int64_t>(source_start_));
502 Write8(fd, static_cast<int64_t>(source_len_));
503 Write8(fd, static_cast<int64_t>(offset));
504 Write8(fd, static_cast<int64_t>(source_uncompressed_len_));
505 Write8(fd, static_cast<int64_t>(target_uncompressed_len_));
506 Write4(fd, target_compress_level_);
507 Write4(fd, ImageChunk::METHOD);
508 Write4(fd, ImageChunk::WINDOWBITS);
509 Write4(fd, ImageChunk::MEMLEVEL);
510 Write4(fd, ImageChunk::STRATEGY);
511 return offset + data_.size();
512 case CHUNK_RAW:
513 printf("raw (%10zu, %10zu)\n", target_start_, target_len_);
514 Write4(fd, static_cast<int32_t>(data_.size()));
515 if (!android::base::WriteFully(fd, data_.data(), data_.size())) {
516 CHECK(false) << "failed to write " << data_.size() << " bytes patch";
517 }
518 return offset;
519 default:
520 CHECK(false) << "unexpected chunk type: " << type_;
521 return offset;
522 }
523}
524
Tianjie Xu82582b42017-08-31 18:05:19 -0700525size_t PatchChunk::PatchSize() const {
526 if (type_ == CHUNK_RAW) {
527 return GetHeaderSize();
528 }
529 return GetHeaderSize() + data_.size();
530}
531
Tianjie Xud82a2ed2017-08-08 17:35:01 -0700532// Write the contents of |patch_chunks| to |patch_fd|.
533bool PatchChunk::WritePatchDataToFd(const std::vector<PatchChunk>& patch_chunks, int patch_fd) {
534 // Figure out how big the imgdiff file header is going to be, so that we can correctly compute
535 // the offset of each bsdiff patch within the file.
536 size_t total_header_size = 12;
537 for (const auto& patch : patch_chunks) {
538 total_header_size += patch.GetHeaderSize();
539 }
540
541 size_t offset = total_header_size;
542
543 // Write out the headers.
Tianjie Xu82582b42017-08-31 18:05:19 -0700544 if (!android::base::WriteStringToFd("IMGDIFF" + std::to_string(VERSION), patch_fd)) {
545 printf("failed to write \"IMGDIFF%zu\": %s\n", VERSION, strerror(errno));
Tianjie Xud82a2ed2017-08-08 17:35:01 -0700546 return false;
547 }
548
549 Write4(patch_fd, static_cast<int32_t>(patch_chunks.size()));
550 for (size_t i = 0; i < patch_chunks.size(); ++i) {
551 printf("chunk %zu: ", i);
552 offset = patch_chunks[i].WriteHeaderToFd(patch_fd, offset);
553 }
554
555 // Append each chunk's bsdiff patch, in order.
556 for (const auto& patch : patch_chunks) {
557 if (patch.type_ == CHUNK_RAW) {
558 continue;
559 }
560 if (!android::base::WriteFully(patch_fd, patch.data_.data(), patch.data_.size())) {
561 printf("failed to write %zu bytes patch to patch_fd\n", patch.data_.size());
562 return false;
563 }
564 }
565
566 return true;
567}
568
Tianjie Xu57dd9612017-08-17 17:50:56 -0700569ImageChunk& Image::operator[](size_t i) {
570 CHECK_LT(i, chunks_.size());
571 return chunks_[i];
572}
Tianjie Xu6b03ba72017-07-19 14:16:30 -0700573
Tianjie Xu57dd9612017-08-17 17:50:56 -0700574const ImageChunk& Image::operator[](size_t i) const {
575 CHECK_LT(i, chunks_.size());
576 return chunks_[i];
577}
Tianjie Xu6b03ba72017-07-19 14:16:30 -0700578
579void Image::MergeAdjacentNormalChunks() {
580 size_t merged_last = 0, cur = 0;
581 while (cur < chunks_.size()) {
582 // Look for normal chunks adjacent to the current one. If such chunk exists, extend the
583 // length of the current normal chunk.
584 size_t to_check = cur + 1;
585 while (to_check < chunks_.size() && chunks_[cur].IsAdjacentNormal(chunks_[to_check])) {
586 chunks_[cur].MergeAdjacentNormal(chunks_[to_check]);
587 to_check++;
588 }
589
590 if (merged_last != cur) {
591 chunks_[merged_last] = std::move(chunks_[cur]);
592 }
593 merged_last++;
594 cur = to_check;
595 }
596 if (merged_last < chunks_.size()) {
597 chunks_.erase(chunks_.begin() + merged_last, chunks_.end());
598 }
599}
600
Tianjie Xu6b03ba72017-07-19 14:16:30 -0700601void Image::DumpChunks() const {
602 std::string type = is_source_ ? "source" : "target";
603 printf("Dumping chunks for %s\n", type.c_str());
604 for (size_t i = 0; i < chunks_.size(); ++i) {
605 printf("chunk %zu: ", i);
606 chunks_[i].Dump();
607 }
608}
609
610bool Image::ReadFile(const std::string& filename, std::vector<uint8_t>* file_content) {
611 CHECK(file_content != nullptr);
612
613 android::base::unique_fd fd(open(filename.c_str(), O_RDONLY));
614 if (fd == -1) {
615 printf("failed to open \"%s\" %s\n", filename.c_str(), strerror(errno));
616 return false;
617 }
618 struct stat st;
619 if (fstat(fd, &st) != 0) {
620 printf("failed to stat \"%s\": %s\n", filename.c_str(), strerror(errno));
621 return false;
622 }
623
624 size_t sz = static_cast<size_t>(st.st_size);
625 file_content->resize(sz);
626 if (!android::base::ReadFully(fd, file_content->data(), sz)) {
627 printf("failed to read \"%s\" %s\n", filename.c_str(), strerror(errno));
628 return false;
629 }
630 fd.reset();
631
632 return true;
633}
634
Tianjie Xu6b03ba72017-07-19 14:16:30 -0700635bool ZipModeImage::Initialize(const std::string& filename) {
636 if (!ReadFile(filename, &file_content_)) {
637 return false;
638 }
639
640 // Omit the trailing zeros before we pass the file to ziparchive handler.
641 size_t zipfile_size;
642 if (!GetZipFileSize(&zipfile_size)) {
643 printf("failed to parse the actual size of %s\n", filename.c_str());
644 return false;
645 }
646 ZipArchiveHandle handle;
647 int err = OpenArchiveFromMemory(const_cast<uint8_t*>(file_content_.data()), zipfile_size,
648 filename.c_str(), &handle);
649 if (err != 0) {
650 printf("failed to open zip file %s: %s\n", filename.c_str(), ErrorCodeString(err));
651 CloseArchive(handle);
652 return false;
653 }
654
Tianjie Xu6b03ba72017-07-19 14:16:30 -0700655 if (!InitializeChunks(filename, handle)) {
656 CloseArchive(handle);
657 return false;
658 }
659
660 CloseArchive(handle);
661 return true;
662}
663
664// Iterate the zip entries and compose the image chunks accordingly.
665bool ZipModeImage::InitializeChunks(const std::string& filename, ZipArchiveHandle handle) {
666 void* cookie;
667 int ret = StartIteration(handle, &cookie, nullptr, nullptr);
668 if (ret != 0) {
669 printf("failed to iterate over entries in %s: %s\n", filename.c_str(), ErrorCodeString(ret));
670 return false;
671 }
672
673 // Create a list of deflated zip entries, sorted by offset.
674 std::vector<std::pair<std::string, ZipEntry>> temp_entries;
675 ZipString name;
676 ZipEntry entry;
677 while ((ret = Next(cookie, &entry, &name)) == 0) {
Tianjie Xu2903cdd2017-08-18 18:15:47 -0700678 if (entry.method == kCompressDeflated || limit_ > 0) {
Tianjie Xu6b03ba72017-07-19 14:16:30 -0700679 std::string entry_name(name.name, name.name + name.name_length);
680 temp_entries.emplace_back(entry_name, entry);
681 }
682 }
683
684 if (ret != -1) {
685 printf("Error while iterating over zip entries: %s\n", ErrorCodeString(ret));
686 return false;
687 }
688 std::sort(temp_entries.begin(), temp_entries.end(),
689 [](auto& entry1, auto& entry2) { return entry1.second.offset < entry2.second.offset; });
690
691 EndIteration(cookie);
692
693 // For source chunks, we don't need to compose chunks for the metadata.
694 if (is_source_) {
695 for (auto& entry : temp_entries) {
696 if (!AddZipEntryToChunks(handle, entry.first, &entry.second)) {
697 printf("Failed to add %s to source chunks\n", entry.first.c_str());
698 return false;
699 }
700 }
Tianjie Xu2903cdd2017-08-18 18:15:47 -0700701
702 // Add the end of zip file (mainly central directory) as a normal chunk.
703 size_t entries_end = 0;
704 if (!temp_entries.empty()) {
705 entries_end = static_cast<size_t>(temp_entries.back().second.offset +
706 temp_entries.back().second.compressed_length);
707 }
708 CHECK_LT(entries_end, file_content_.size());
709 chunks_.emplace_back(CHUNK_NORMAL, entries_end, &file_content_,
710 file_content_.size() - entries_end);
711
Tianjie Xu6b03ba72017-07-19 14:16:30 -0700712 return true;
713 }
714
715 // For target chunks, add the deflate entries as CHUNK_DEFLATE and the contents between two
716 // deflate entries as CHUNK_NORMAL.
717 size_t pos = 0;
718 size_t nextentry = 0;
719 while (pos < file_content_.size()) {
720 if (nextentry < temp_entries.size() &&
721 static_cast<off64_t>(pos) == temp_entries[nextentry].second.offset) {
722 // Add the next zip entry.
723 std::string entry_name = temp_entries[nextentry].first;
724 if (!AddZipEntryToChunks(handle, entry_name, &temp_entries[nextentry].second)) {
725 printf("Failed to add %s to target chunks\n", entry_name.c_str());
726 return false;
727 }
728
729 pos += temp_entries[nextentry].second.compressed_length;
730 ++nextentry;
731 continue;
732 }
733
734 // Use a normal chunk to take all the data up to the start of the next entry.
735 size_t raw_data_len;
736 if (nextentry < temp_entries.size()) {
737 raw_data_len = temp_entries[nextentry].second.offset - pos;
738 } else {
739 raw_data_len = file_content_.size() - pos;
740 }
741 chunks_.emplace_back(CHUNK_NORMAL, pos, &file_content_, raw_data_len);
742
743 pos += raw_data_len;
744 }
745
746 return true;
747}
748
749bool ZipModeImage::AddZipEntryToChunks(ZipArchiveHandle handle, const std::string& entry_name,
750 ZipEntry* entry) {
751 size_t compressed_len = entry->compressed_length;
Tianjie Xu2903cdd2017-08-18 18:15:47 -0700752 if (compressed_len == 0) return true;
753
754 // Split the entry into several normal chunks if it's too large.
755 if (limit_ > 0 && compressed_len > limit_) {
756 int count = 0;
757 while (compressed_len > 0) {
758 size_t length = std::min(limit_, compressed_len);
759 std::string name = entry_name + "-" + std::to_string(count);
760 chunks_.emplace_back(CHUNK_NORMAL, entry->offset + limit_ * count, &file_content_, length,
761 name);
762
763 count++;
764 compressed_len -= length;
765 }
766 } else if (entry->method == kCompressDeflated) {
Tianjie Xu6b03ba72017-07-19 14:16:30 -0700767 size_t uncompressed_len = entry->uncompressed_length;
768 std::vector<uint8_t> uncompressed_data(uncompressed_len);
769 int ret = ExtractToMemory(handle, entry, uncompressed_data.data(), uncompressed_len);
770 if (ret != 0) {
771 printf("failed to extract %s with size %zu: %s\n", entry_name.c_str(), uncompressed_len,
772 ErrorCodeString(ret));
773 return false;
774 }
Tianjie Xud82a2ed2017-08-08 17:35:01 -0700775 ImageChunk curr(CHUNK_DEFLATE, entry->offset, &file_content_, compressed_len, entry_name);
Tianjie Xu6b03ba72017-07-19 14:16:30 -0700776 curr.SetUncompressedData(std::move(uncompressed_data));
Tianjie Xud82a2ed2017-08-08 17:35:01 -0700777 chunks_.push_back(std::move(curr));
Tianjie Xu6b03ba72017-07-19 14:16:30 -0700778 } else {
Tianjie Xud82a2ed2017-08-08 17:35:01 -0700779 chunks_.emplace_back(CHUNK_NORMAL, entry->offset, &file_content_, compressed_len, entry_name);
Tianjie Xu6b03ba72017-07-19 14:16:30 -0700780 }
781
782 return true;
783}
784
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800785// EOCD record
786// offset 0: signature 0x06054b50, 4 bytes
787// offset 4: number of this disk, 2 bytes
788// ...
789// offset 20: comment length, 2 bytes
790// offset 22: comment, n bytes
Tianjie Xu6b03ba72017-07-19 14:16:30 -0700791bool ZipModeImage::GetZipFileSize(size_t* input_file_size) {
792 if (file_content_.size() < 22) {
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800793 printf("file is too small to be a zip file\n");
794 return false;
795 }
796
797 // Look for End of central directory record of the zip file, and calculate the actual
798 // zip_file size.
Tianjie Xu6b03ba72017-07-19 14:16:30 -0700799 for (int i = file_content_.size() - 22; i >= 0; i--) {
800 if (file_content_[i] == 0x50) {
801 if (get_unaligned<uint32_t>(&file_content_[i]) == 0x06054b50) {
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800802 // double-check: this archive consists of a single "disk".
Tianjie Xu6b03ba72017-07-19 14:16:30 -0700803 CHECK_EQ(get_unaligned<uint16_t>(&file_content_[i + 4]), 0);
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800804
Tianjie Xu6b03ba72017-07-19 14:16:30 -0700805 uint16_t comment_length = get_unaligned<uint16_t>(&file_content_[i + 20]);
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800806 size_t file_size = i + 22 + comment_length;
Tianjie Xu6b03ba72017-07-19 14:16:30 -0700807 CHECK_LE(file_size, file_content_.size());
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800808 *input_file_size = file_size;
809 return true;
810 }
811 }
812 }
813
814 // EOCD not found, this file is likely not a valid zip file.
815 return false;
816}
817
Tianjie Xu57dd9612017-08-17 17:50:56 -0700818ImageChunk ZipModeImage::PseudoSource() const {
819 CHECK(is_source_);
820 return ImageChunk(CHUNK_NORMAL, 0, &file_content_, file_content_.size());
821}
822
823const ImageChunk* ZipModeImage::FindChunkByName(const std::string& name, bool find_normal) const {
824 if (name.empty()) {
825 return nullptr;
826 }
827 for (auto& chunk : chunks_) {
Tianjie Xu2903cdd2017-08-18 18:15:47 -0700828 if (chunk.GetType() != CHUNK_DEFLATE && !find_normal) {
829 continue;
830 }
831
832 if (chunk.GetEntryName() == name) {
Tianjie Xu57dd9612017-08-17 17:50:56 -0700833 return &chunk;
834 }
Tianjie Xu2903cdd2017-08-18 18:15:47 -0700835
836 // Edge case when target chunk is split due to size limit but source chunk isn't.
837 if (name == (chunk.GetEntryName() + "-0") || chunk.GetEntryName() == (name + "-0")) {
838 return &chunk;
839 }
840
841 // TODO handle the .so files with incremental version number.
842 // (e.g. lib/arm64-v8a/libcronet.59.0.3050.4.so)
Tianjie Xu57dd9612017-08-17 17:50:56 -0700843 }
Tianjie Xu2903cdd2017-08-18 18:15:47 -0700844
Tianjie Xu57dd9612017-08-17 17:50:56 -0700845 return nullptr;
846}
847
848ImageChunk* ZipModeImage::FindChunkByName(const std::string& name, bool find_normal) {
849 return const_cast<ImageChunk*>(
850 static_cast<const ZipModeImage*>(this)->FindChunkByName(name, find_normal));
851}
852
Tianjie Xu6b03ba72017-07-19 14:16:30 -0700853bool ZipModeImage::CheckAndProcessChunks(ZipModeImage* tgt_image, ZipModeImage* src_image) {
854 for (auto& tgt_chunk : *tgt_image) {
855 if (tgt_chunk.GetType() != CHUNK_DEFLATE) {
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800856 continue;
857 }
858
Tianjie Xu6b03ba72017-07-19 14:16:30 -0700859 ImageChunk* src_chunk = src_image->FindChunkByName(tgt_chunk.GetEntryName());
860 if (src_chunk == nullptr) {
861 tgt_chunk.ChangeDeflateChunkToNormal();
862 } else if (tgt_chunk == *src_chunk) {
863 // If two deflate chunks are identical (eg, the kernel has not changed between two builds),
864 // treat them as normal chunks. This makes applypatch much faster -- it can apply a trivial
865 // patch to the compressed data, rather than uncompressing and recompressing to apply the
866 // trivial patch to the uncompressed data.
867 tgt_chunk.ChangeDeflateChunkToNormal();
868 src_chunk->ChangeDeflateChunkToNormal();
869 } else if (!tgt_chunk.ReconstructDeflateChunk()) {
870 // We cannot recompress the data and get exactly the same bits as are in the input target
871 // image. Treat the chunk as a normal non-deflated chunk.
872 printf("failed to reconstruct target deflate chunk [%s]; treating as normal\n",
873 tgt_chunk.GetEntryName().c_str());
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800874
Tianjie Xu6b03ba72017-07-19 14:16:30 -0700875 tgt_chunk.ChangeDeflateChunkToNormal();
876 src_chunk->ChangeDeflateChunkToNormal();
877 }
Tianjie Xu1ea84d62017-02-22 18:23:58 -0800878 }
879
Tianjie Xu6b03ba72017-07-19 14:16:30 -0700880 // For zips, we only need merge normal chunks for the target: deflated chunks are matched via
881 // filename, and normal chunks are patched using the entire source file as the source.
Tianjie Xu2903cdd2017-08-18 18:15:47 -0700882 if (tgt_image->limit_ == 0) {
883 tgt_image->MergeAdjacentNormalChunks();
884 tgt_image->DumpChunks();
885 }
Tianjie Xu12b90552017-03-07 14:44:14 -0800886
Tianjie Xud82a2ed2017-08-08 17:35:01 -0700887 return true;
888}
889
Tianjie Xu2903cdd2017-08-18 18:15:47 -0700890// For each target chunk, look for the corresponding source chunk by the zip_entry name. If
891// found, add the range of this chunk in the original source file to the block aligned source
892// ranges. Construct the split src & tgt image once the size of source range reaches limit.
893bool ZipModeImage::SplitZipModeImageWithLimit(const ZipModeImage& tgt_image,
894 const ZipModeImage& src_image,
895 std::vector<ZipModeImage>* split_tgt_images,
896 std::vector<ZipModeImage>* split_src_images,
897 std::vector<SortedRangeSet>* split_src_ranges) {
898 CHECK_EQ(tgt_image.limit_, src_image.limit_);
899 size_t limit = tgt_image.limit_;
900
901 src_image.DumpChunks();
902 printf("Splitting %zu tgt chunks...\n", tgt_image.NumOfChunks());
903
904 SortedRangeSet used_src_ranges; // ranges used for previous split source images.
905
906 // Reserve the central directory in advance for the last split image.
907 const auto& central_directory = src_image.cend() - 1;
908 CHECK_EQ(CHUNK_NORMAL, central_directory->GetType());
909 used_src_ranges.Insert(central_directory->GetStartOffset(),
910 central_directory->DataLengthForPatch());
911
912 SortedRangeSet src_ranges;
913 std::vector<ImageChunk> split_src_chunks;
914 std::vector<ImageChunk> split_tgt_chunks;
915 for (auto tgt = tgt_image.cbegin(); tgt != tgt_image.cend(); tgt++) {
916 const ImageChunk* src = src_image.FindChunkByName(tgt->GetEntryName(), true);
917 if (src == nullptr) {
918 split_tgt_chunks.emplace_back(CHUNK_NORMAL, tgt->GetStartOffset(), &tgt_image.file_content_,
919 tgt->GetRawDataLength());
920 continue;
921 }
922
923 size_t src_offset = src->GetStartOffset();
924 size_t src_length = src->GetRawDataLength();
925
926 CHECK(src_length > 0);
927 CHECK_LE(src_length, limit);
928
929 // Make sure this source range hasn't been used before so that the src_range pieces don't
930 // overlap with each other.
931 if (!RemoveUsedBlocks(&src_offset, &src_length, used_src_ranges)) {
932 split_tgt_chunks.emplace_back(CHUNK_NORMAL, tgt->GetStartOffset(), &tgt_image.file_content_,
933 tgt->GetRawDataLength());
934 } else if (src_ranges.blocks() * BLOCK_SIZE + src_length <= limit) {
935 src_ranges.Insert(src_offset, src_length);
936
937 // Add the deflate source chunk if it hasn't been aligned.
938 if (src->GetType() == CHUNK_DEFLATE && src_length == src->GetRawDataLength()) {
939 split_src_chunks.push_back(*src);
940 split_tgt_chunks.push_back(*tgt);
941 } else {
942 // TODO split smarter to avoid alignment of large deflate chunks
943 split_tgt_chunks.emplace_back(CHUNK_NORMAL, tgt->GetStartOffset(), &tgt_image.file_content_,
944 tgt->GetRawDataLength());
945 }
946 } else {
947 ZipModeImage::AddSplitImageFromChunkList(tgt_image, src_image, src_ranges, split_tgt_chunks,
948 split_src_chunks, split_tgt_images,
949 split_src_images);
950
951 split_tgt_chunks.clear();
952 split_src_chunks.clear();
953 used_src_ranges.Insert(src_ranges);
954 split_src_ranges->push_back(std::move(src_ranges));
955 src_ranges.Clear();
956
957 // We don't have enough space for the current chunk; start a new split image and handle
958 // this chunk there.
959 tgt--;
960 }
961 }
962
963 // TODO Trim it in case the CD exceeds limit too much.
964 src_ranges.Insert(central_directory->GetStartOffset(), central_directory->DataLengthForPatch());
965 ZipModeImage::AddSplitImageFromChunkList(tgt_image, src_image, src_ranges, split_tgt_chunks,
966 split_src_chunks, split_tgt_images, split_src_images);
967 split_src_ranges->push_back(std::move(src_ranges));
968
969 ValidateSplitImages(*split_tgt_images, *split_src_images, *split_src_ranges,
970 tgt_image.file_content_.size());
971
972 return true;
973}
974
975void ZipModeImage::AddSplitImageFromChunkList(const ZipModeImage& tgt_image,
976 const ZipModeImage& src_image,
977 const SortedRangeSet& split_src_ranges,
978 const std::vector<ImageChunk>& split_tgt_chunks,
979 const std::vector<ImageChunk>& split_src_chunks,
980 std::vector<ZipModeImage>* split_tgt_images,
981 std::vector<ZipModeImage>* split_src_images) {
982 CHECK(!split_tgt_chunks.empty());
983 // Target chunks should occupy at least one block.
984 // TODO put a warning and change the type to raw if it happens in extremely rare cases.
985 size_t tgt_size = split_tgt_chunks.back().GetStartOffset() +
986 split_tgt_chunks.back().DataLengthForPatch() -
987 split_tgt_chunks.front().GetStartOffset();
988 CHECK_GE(tgt_size, BLOCK_SIZE);
989
990 std::vector<ImageChunk> aligned_tgt_chunks;
991
992 // Align the target chunks in the beginning with BLOCK_SIZE.
993 size_t i = 0;
994 while (i < split_tgt_chunks.size()) {
995 size_t tgt_start = split_tgt_chunks[i].GetStartOffset();
996 size_t tgt_length = split_tgt_chunks[i].GetRawDataLength();
997
998 // Current ImageChunk is long enough to align.
999 if (AlignHead(&tgt_start, &tgt_length)) {
1000 aligned_tgt_chunks.emplace_back(CHUNK_NORMAL, tgt_start, &tgt_image.file_content_,
1001 tgt_length);
1002 break;
1003 }
1004
1005 i++;
1006 }
1007 CHECK_LT(i, split_tgt_chunks.size());
1008 aligned_tgt_chunks.insert(aligned_tgt_chunks.end(), split_tgt_chunks.begin() + i + 1,
1009 split_tgt_chunks.end());
1010 CHECK(!aligned_tgt_chunks.empty());
1011
1012 // Add a normal chunk to align the contents in the end.
1013 size_t end_offset =
1014 aligned_tgt_chunks.back().GetStartOffset() + aligned_tgt_chunks.back().GetRawDataLength();
1015 if (end_offset % BLOCK_SIZE != 0 && end_offset < tgt_image.file_content_.size()) {
1016 aligned_tgt_chunks.emplace_back(CHUNK_NORMAL, end_offset, &tgt_image.file_content_,
1017 BLOCK_SIZE - (end_offset % BLOCK_SIZE));
1018 }
1019
1020 ZipModeImage split_tgt_image(false);
1021 split_tgt_image.Initialize(std::move(aligned_tgt_chunks), {});
1022 split_tgt_image.MergeAdjacentNormalChunks();
1023
1024 // Construct the dummy source file based on the src_ranges.
1025 std::vector<uint8_t> src_content;
1026 for (const auto& r : split_src_ranges) {
1027 size_t end = std::min(src_image.file_content_.size(), r.second * BLOCK_SIZE);
1028 src_content.insert(src_content.end(), src_image.file_content_.begin() + r.first * BLOCK_SIZE,
1029 src_image.file_content_.begin() + end);
1030 }
1031
1032 // We should not have an empty src in our design; otherwise we will encounter an error in
1033 // bsdiff since src_content.data() == nullptr.
1034 CHECK(!src_content.empty());
1035
1036 ZipModeImage split_src_image(true);
1037 split_src_image.Initialize(split_src_chunks, std::move(src_content));
1038
1039 split_tgt_images->push_back(std::move(split_tgt_image));
1040 split_src_images->push_back(std::move(split_src_image));
1041}
1042
1043void ZipModeImage::ValidateSplitImages(const std::vector<ZipModeImage>& split_tgt_images,
1044 const std::vector<ZipModeImage>& split_src_images,
1045 std::vector<SortedRangeSet>& split_src_ranges,
1046 size_t total_tgt_size) {
1047 CHECK_EQ(split_tgt_images.size(), split_src_images.size());
1048
1049 printf("Validating %zu images\n", split_tgt_images.size());
1050
1051 // Verify that the target image pieces is continuous and can add up to the total size.
1052 size_t last_offset = 0;
1053 for (const auto& tgt_image : split_tgt_images) {
1054 CHECK(!tgt_image.chunks_.empty());
1055
1056 CHECK_EQ(last_offset, tgt_image.chunks_.front().GetStartOffset());
1057 CHECK(last_offset % BLOCK_SIZE == 0);
1058
1059 // Check the target chunks within the split image are continuous.
1060 for (const auto& chunk : tgt_image.chunks_) {
1061 CHECK_EQ(last_offset, chunk.GetStartOffset());
1062 last_offset += chunk.GetRawDataLength();
1063 }
1064 }
1065 CHECK_EQ(total_tgt_size, last_offset);
1066
1067 // Verify that the source ranges are mutually exclusive.
1068 CHECK_EQ(split_src_images.size(), split_src_ranges.size());
1069 SortedRangeSet used_src_ranges;
1070 for (size_t i = 0; i < split_src_ranges.size(); i++) {
1071 CHECK(!used_src_ranges.Overlaps(split_src_ranges[i]))
1072 << "src range " << split_src_ranges[i].ToString() << " overlaps "
1073 << used_src_ranges.ToString();
1074 used_src_ranges.Insert(split_src_ranges[i]);
1075 }
1076}
1077
1078bool ZipModeImage::GeneratePatchesInternal(const ZipModeImage& tgt_image,
1079 const ZipModeImage& src_image,
1080 std::vector<PatchChunk>* patch_chunks) {
Tianjie Xud82a2ed2017-08-08 17:35:01 -07001081 printf("Construct patches for %zu chunks...\n", tgt_image.NumOfChunks());
Tianjie Xu2903cdd2017-08-18 18:15:47 -07001082 patch_chunks->clear();
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001083
1084 saidx_t* bsdiff_cache = nullptr;
Tianjie Xud82a2ed2017-08-08 17:35:01 -07001085 for (size_t i = 0; i < tgt_image.NumOfChunks(); i++) {
1086 const auto& tgt_chunk = tgt_image[i];
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001087
Tianjie Xud82a2ed2017-08-08 17:35:01 -07001088 if (PatchChunk::RawDataIsSmaller(tgt_chunk, 0)) {
Tianjie Xu2903cdd2017-08-18 18:15:47 -07001089 patch_chunks->emplace_back(tgt_chunk);
Tianjie Xud82a2ed2017-08-08 17:35:01 -07001090 continue;
1091 }
1092
1093 const ImageChunk* src_chunk = (tgt_chunk.GetType() != CHUNK_DEFLATE)
1094 ? nullptr
1095 : src_image.FindChunkByName(tgt_chunk.GetEntryName());
1096
1097 const auto& src_ref = (src_chunk == nullptr) ? src_image.PseudoSource() : *src_chunk;
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001098 saidx_t** bsdiff_cache_ptr = (src_chunk == nullptr) ? &bsdiff_cache : nullptr;
1099
Tianjie Xud82a2ed2017-08-08 17:35:01 -07001100 std::vector<uint8_t> patch_data;
1101 if (!ImageChunk::MakePatch(tgt_chunk, src_ref, &patch_data, bsdiff_cache_ptr)) {
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001102 printf("Failed to generate patch, name: %s\n", tgt_chunk.GetEntryName().c_str());
1103 return false;
1104 }
1105
Tianjie Xud82a2ed2017-08-08 17:35:01 -07001106 printf("patch %3zu is %zu bytes (of %zu)\n", i, patch_data.size(),
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001107 tgt_chunk.GetRawDataLength());
Tianjie Xud82a2ed2017-08-08 17:35:01 -07001108
1109 if (PatchChunk::RawDataIsSmaller(tgt_chunk, patch_data.size())) {
Tianjie Xu2903cdd2017-08-18 18:15:47 -07001110 patch_chunks->emplace_back(tgt_chunk);
Tianjie Xud82a2ed2017-08-08 17:35:01 -07001111 } else {
Tianjie Xu2903cdd2017-08-18 18:15:47 -07001112 patch_chunks->emplace_back(tgt_chunk, src_ref, std::move(patch_data));
Tianjie Xud82a2ed2017-08-08 17:35:01 -07001113 }
Tianjie Xu12b90552017-03-07 14:44:14 -08001114 }
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001115 free(bsdiff_cache);
1116
Tianjie Xu2903cdd2017-08-18 18:15:47 -07001117 CHECK_EQ(patch_chunks->size(), tgt_image.NumOfChunks());
1118 return true;
1119}
1120
1121bool ZipModeImage::GeneratePatches(const ZipModeImage& tgt_image, const ZipModeImage& src_image,
1122 const std::string& patch_name) {
1123 std::vector<PatchChunk> patch_chunks;
1124
1125 ZipModeImage::GeneratePatchesInternal(tgt_image, src_image, &patch_chunks);
1126
Tianjie Xud82a2ed2017-08-08 17:35:01 -07001127 CHECK_EQ(tgt_image.NumOfChunks(), patch_chunks.size());
1128
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001129 android::base::unique_fd patch_fd(
1130 open(patch_name.c_str(), O_CREAT | O_WRONLY | O_TRUNC, S_IRUSR | S_IWUSR));
1131 if (patch_fd == -1) {
1132 printf("failed to open \"%s\": %s\n", patch_name.c_str(), strerror(errno));
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001133 return false;
1134 }
1135
Tianjie Xud82a2ed2017-08-08 17:35:01 -07001136 return PatchChunk::WritePatchDataToFd(patch_chunks, patch_fd);
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001137}
1138
Tianjie Xu2903cdd2017-08-18 18:15:47 -07001139bool ZipModeImage::GeneratePatches(const std::vector<ZipModeImage>& split_tgt_images,
1140 const std::vector<ZipModeImage>& split_src_images,
1141 const std::vector<SortedRangeSet>& split_src_ranges,
Tianjie Xu82582b42017-08-31 18:05:19 -07001142 const std::string& patch_name,
1143 const std::string& split_info_file,
1144 const std::string& debug_dir) {
Tianjie Xu2903cdd2017-08-18 18:15:47 -07001145 printf("Construct patches for %zu split images...\n", split_tgt_images.size());
1146
1147 android::base::unique_fd patch_fd(
1148 open(patch_name.c_str(), O_CREAT | O_WRONLY | O_TRUNC, S_IRUSR | S_IWUSR));
1149 if (patch_fd == -1) {
1150 printf("failed to open \"%s\": %s\n", patch_name.c_str(), strerror(errno));
1151 return false;
1152 }
1153
Tianjie Xu82582b42017-08-31 18:05:19 -07001154 std::vector<std::string> split_info_list;
Tianjie Xu2903cdd2017-08-18 18:15:47 -07001155 for (size_t i = 0; i < split_tgt_images.size(); i++) {
1156 std::vector<PatchChunk> patch_chunks;
1157 if (!ZipModeImage::GeneratePatchesInternal(split_tgt_images[i], split_src_images[i],
1158 &patch_chunks)) {
1159 printf("failed to generate split patch\n");
1160 return false;
1161 }
1162
Tianjie Xu82582b42017-08-31 18:05:19 -07001163 size_t total_patch_size = 12;
Tianjie Xu2903cdd2017-08-18 18:15:47 -07001164 for (auto& p : patch_chunks) {
1165 p.UpdateSourceOffset(split_src_ranges[i]);
Tianjie Xu82582b42017-08-31 18:05:19 -07001166 total_patch_size += p.PatchSize();
Tianjie Xu2903cdd2017-08-18 18:15:47 -07001167 }
1168
1169 if (!PatchChunk::WritePatchDataToFd(patch_chunks, patch_fd)) {
1170 return false;
1171 }
1172
Tianjie Xu82582b42017-08-31 18:05:19 -07001173 size_t split_tgt_size = split_tgt_images[i].chunks_.back().GetStartOffset() +
1174 split_tgt_images[i].chunks_.back().GetRawDataLength() -
1175 split_tgt_images[i].chunks_.front().GetStartOffset();
1176 std::string split_info = android::base::StringPrintf(
1177 "%zu %zu %s", total_patch_size, split_tgt_size, split_src_ranges[i].ToString().c_str());
1178 split_info_list.push_back(split_info);
1179
Tianjie Xu2903cdd2017-08-18 18:15:47 -07001180 // Write the split source & patch into the debug directory.
1181 if (!debug_dir.empty()) {
1182 std::string src_name = android::base::StringPrintf("%s/src-%zu", debug_dir.c_str(), i);
1183 android::base::unique_fd fd(
1184 open(src_name.c_str(), O_CREAT | O_WRONLY | O_TRUNC, S_IRUSR | S_IWUSR));
1185
1186 if (fd == -1) {
1187 printf("Failed to open %s\n", src_name.c_str());
1188 return false;
1189 }
1190 if (!android::base::WriteFully(fd, split_src_images[i].PseudoSource().DataForPatch(),
1191 split_src_images[i].PseudoSource().DataLengthForPatch())) {
1192 printf("Failed to write split source data into %s\n", src_name.c_str());
1193 return false;
1194 }
1195
1196 std::string patch_name = android::base::StringPrintf("%s/patch-%zu", debug_dir.c_str(), i);
1197 fd.reset(open(patch_name.c_str(), O_CREAT | O_WRONLY | O_TRUNC, S_IRUSR | S_IWUSR));
1198
1199 if (fd == -1) {
1200 printf("Failed to open %s\n", patch_name.c_str());
1201 return false;
1202 }
1203 if (!PatchChunk::WritePatchDataToFd(patch_chunks, fd)) {
1204 return false;
1205 }
1206 }
1207 }
Tianjie Xu82582b42017-08-31 18:05:19 -07001208
1209 // Store the split in the following format:
1210 // Line 0: imgdiff version#
1211 // Line 1: number of pieces
1212 // Line 2: patch_size_1 tgt_size_1 src_range_1
1213 // ...
1214 // Line n+1: patch_size_n tgt_size_n src_range_n
1215 std::string split_info_string = android::base::StringPrintf(
1216 "%zu\n%zu\n", VERSION, split_info_list.size()) + android::base::Join(split_info_list, '\n');
1217 if (!android::base::WriteStringToFile(split_info_string, split_info_file)) {
1218 printf("failed to write split info to \"%s\": %s\n", split_info_file.c_str(),
1219 strerror(errno));
1220 return false;
1221 }
1222
Tianjie Xu2903cdd2017-08-18 18:15:47 -07001223 return true;
1224}
1225
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001226bool ImageModeImage::Initialize(const std::string& filename) {
1227 if (!ReadFile(filename, &file_content_)) {
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001228 return false;
Doug Zongker512536a2010-02-17 16:11:44 -08001229 }
Doug Zongker512536a2010-02-17 16:11:44 -08001230
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001231 size_t sz = file_content_.size();
Doug Zongker512536a2010-02-17 16:11:44 -08001232 size_t pos = 0;
Tao Baoba9a42a2015-06-23 23:23:33 -07001233 while (pos < sz) {
Tianjie Xu12b90552017-03-07 14:44:14 -08001234 // 0x00 no header flags, 0x08 deflate compression, 0x1f8b gzip magic number
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001235 if (sz - pos >= 4 && get_unaligned<uint32_t>(file_content_.data() + pos) == 0x00088b1f) {
Doug Zongker512536a2010-02-17 16:11:44 -08001236 // 'pos' is the offset of the start of a gzip chunk.
Johan Redestigc68bd342015-04-14 21:20:06 +02001237 size_t chunk_offset = pos;
Doug Zongker512536a2010-02-17 16:11:44 -08001238
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001239 // The remaining data is too small to be a gzip chunk; treat them as a normal chunk.
1240 if (sz - pos < GZIP_HEADER_LEN + GZIP_FOOTER_LEN) {
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001241 chunks_.emplace_back(CHUNK_NORMAL, pos, &file_content_, sz - pos);
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001242 break;
1243 }
Doug Zongker512536a2010-02-17 16:11:44 -08001244
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001245 // We need three chunks for the deflated image in total, one normal chunk for the header,
1246 // one deflated chunk for the body, and another normal chunk for the footer.
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001247 chunks_.emplace_back(CHUNK_NORMAL, pos, &file_content_, GZIP_HEADER_LEN);
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001248 pos += GZIP_HEADER_LEN;
Doug Zongker512536a2010-02-17 16:11:44 -08001249
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001250 // We must decompress this chunk in order to discover where it ends, and so we can update
1251 // the uncompressed_data of the image body and its length.
Doug Zongker512536a2010-02-17 16:11:44 -08001252
1253 z_stream strm;
1254 strm.zalloc = Z_NULL;
1255 strm.zfree = Z_NULL;
1256 strm.opaque = Z_NULL;
Tao Baoba9a42a2015-06-23 23:23:33 -07001257 strm.avail_in = sz - pos;
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001258 strm.next_in = file_content_.data() + pos;
Doug Zongker512536a2010-02-17 16:11:44 -08001259
1260 // -15 means we are decoding a 'raw' deflate stream; zlib will
1261 // not expect zlib headers.
1262 int ret = inflateInit2(&strm, -15);
Rahul Chaudhrya793c582016-11-29 17:10:14 -08001263 if (ret < 0) {
1264 printf("failed to initialize inflate: %d\n", ret);
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001265 return false;
Rahul Chaudhrya793c582016-11-29 17:10:14 -08001266 }
Doug Zongker512536a2010-02-17 16:11:44 -08001267
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001268 size_t allocated = BUFFER_SIZE;
1269 std::vector<uint8_t> uncompressed_data(allocated);
1270 size_t uncompressed_len = 0, raw_data_len = 0;
Doug Zongker512536a2010-02-17 16:11:44 -08001271 do {
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001272 strm.avail_out = allocated - uncompressed_len;
1273 strm.next_out = uncompressed_data.data() + uncompressed_len;
Doug Zongker512536a2010-02-17 16:11:44 -08001274 ret = inflate(&strm, Z_NO_FLUSH);
Johan Redestigc68bd342015-04-14 21:20:06 +02001275 if (ret < 0) {
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001276 printf("Warning: inflate failed [%s] at offset [%zu], treating as a normal chunk\n",
David Riley0779fc92015-12-10 10:18:25 -08001277 strm.msg, chunk_offset);
Sen Jiangfa4f1b72016-02-11 16:14:23 -08001278 break;
Johan Redestigc68bd342015-04-14 21:20:06 +02001279 }
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001280 uncompressed_len = allocated - strm.avail_out;
Doug Zongker512536a2010-02-17 16:11:44 -08001281 if (strm.avail_out == 0) {
1282 allocated *= 2;
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001283 uncompressed_data.resize(allocated);
Doug Zongker512536a2010-02-17 16:11:44 -08001284 }
1285 } while (ret != Z_STREAM_END);
1286
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001287 raw_data_len = sz - strm.avail_in - pos;
Doug Zongker512536a2010-02-17 16:11:44 -08001288 inflateEnd(&strm);
Sen Jiangfa4f1b72016-02-11 16:14:23 -08001289
1290 if (ret < 0) {
Sen Jiangfa4f1b72016-02-11 16:14:23 -08001291 continue;
1292 }
1293
Tianjie Xu14ebc1e2017-07-05 12:04:07 -07001294 // The footer contains the size of the uncompressed data. Double-check to make sure that it
1295 // matches the size of the data we got when we actually did the decompression.
1296 size_t footer_index = pos + raw_data_len + GZIP_FOOTER_LEN - 4;
1297 if (sz - footer_index < 4) {
1298 printf("Warning: invalid footer position; treating as a nomal chunk\n");
1299 continue;
1300 }
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001301 size_t footer_size = get_unaligned<uint32_t>(file_content_.data() + footer_index);
Tianjie Xu14ebc1e2017-07-05 12:04:07 -07001302 if (footer_size != uncompressed_len) {
1303 printf("Warning: footer size %zu != decompressed size %zu; treating as a nomal chunk\n",
1304 footer_size, uncompressed_len);
1305 continue;
1306 }
1307
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001308 ImageChunk body(CHUNK_DEFLATE, pos, &file_content_, raw_data_len);
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001309 uncompressed_data.resize(uncompressed_len);
1310 body.SetUncompressedData(std::move(uncompressed_data));
Tianjie Xud82a2ed2017-08-08 17:35:01 -07001311 chunks_.push_back(std::move(body));
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001312
1313 pos += raw_data_len;
Doug Zongker512536a2010-02-17 16:11:44 -08001314
1315 // create a normal chunk for the footer
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001316 chunks_.emplace_back(CHUNK_NORMAL, pos, &file_content_, GZIP_FOOTER_LEN);
Doug Zongker512536a2010-02-17 16:11:44 -08001317
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001318 pos += GZIP_FOOTER_LEN;
Doug Zongker512536a2010-02-17 16:11:44 -08001319 } else {
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001320 // Use a normal chunk to take all the contents until the next gzip chunk (or EOF); we expect
1321 // the number of chunks to be small (5 for typical boot and recovery images).
Doug Zongker512536a2010-02-17 16:11:44 -08001322
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001323 // Scan forward until we find a gzip header.
1324 size_t data_len = 0;
1325 while (data_len + pos < sz) {
Tianjie Xu12b90552017-03-07 14:44:14 -08001326 if (data_len + pos + 4 <= sz &&
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001327 get_unaligned<uint32_t>(file_content_.data() + pos + data_len) == 0x00088b1f) {
Doug Zongker512536a2010-02-17 16:11:44 -08001328 break;
1329 }
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001330 data_len++;
Doug Zongker512536a2010-02-17 16:11:44 -08001331 }
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001332 chunks_.emplace_back(CHUNK_NORMAL, pos, &file_content_, data_len);
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001333
1334 pos += data_len;
Doug Zongker512536a2010-02-17 16:11:44 -08001335 }
1336 }
1337
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001338 return true;
Doug Zongker512536a2010-02-17 16:11:44 -08001339}
1340
Tianjie Xud82a2ed2017-08-08 17:35:01 -07001341bool ImageModeImage::SetBonusData(const std::vector<uint8_t>& bonus_data) {
1342 CHECK(is_source_);
1343 if (chunks_.size() < 2 || !chunks_[1].SetBonusData(bonus_data)) {
1344 printf("Failed to set bonus data\n");
1345 DumpChunks();
1346 return false;
1347 }
1348
1349 printf(" using %zu bytes of bonus data\n", bonus_data.size());
1350 return true;
1351}
1352
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001353// In Image Mode, verify that the source and target images have the same chunk structure (ie, the
1354// same sequence of deflate and normal chunks).
1355bool ImageModeImage::CheckAndProcessChunks(ImageModeImage* tgt_image, ImageModeImage* src_image) {
1356 // In image mode, merge the gzip header and footer in with any adjacent normal chunks.
1357 tgt_image->MergeAdjacentNormalChunks();
1358 src_image->MergeAdjacentNormalChunks();
Doug Zongker512536a2010-02-17 16:11:44 -08001359
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001360 if (tgt_image->NumOfChunks() != src_image->NumOfChunks()) {
1361 printf("source and target don't have same number of chunks!\n");
1362 tgt_image->DumpChunks();
1363 src_image->DumpChunks();
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001364 return false;
Jeremy Compostellaa91c66d2015-09-08 19:15:09 +02001365 }
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001366 for (size_t i = 0; i < tgt_image->NumOfChunks(); ++i) {
Tianjie Xud82a2ed2017-08-08 17:35:01 -07001367 if ((*tgt_image)[i].GetType() != (*src_image)[i].GetType()) {
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001368 printf("source and target don't have same chunk structure! (chunk %zu)\n", i);
1369 tgt_image->DumpChunks();
1370 src_image->DumpChunks();
1371 return false;
1372 }
Doug Zongker512536a2010-02-17 16:11:44 -08001373 }
1374
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001375 for (size_t i = 0; i < tgt_image->NumOfChunks(); ++i) {
Tianjie Xud82a2ed2017-08-08 17:35:01 -07001376 auto& tgt_chunk = (*tgt_image)[i];
1377 auto& src_chunk = (*src_image)[i];
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001378 if (tgt_chunk.GetType() != CHUNK_DEFLATE) {
1379 continue;
1380 }
1381
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001382 // If two deflate chunks are identical treat them as normal chunks.
1383 if (tgt_chunk == src_chunk) {
1384 tgt_chunk.ChangeDeflateChunkToNormal();
1385 src_chunk.ChangeDeflateChunkToNormal();
Tianjie Xud82a2ed2017-08-08 17:35:01 -07001386 } else if (!tgt_chunk.ReconstructDeflateChunk()) {
1387 // We cannot recompress the data and get exactly the same bits as are in the input target
1388 // image, fall back to normal
1389 printf("failed to reconstruct target deflate chunk %zu [%s]; treating as normal\n", i,
1390 tgt_chunk.GetEntryName().c_str());
1391 tgt_chunk.ChangeDeflateChunkToNormal();
1392 src_chunk.ChangeDeflateChunkToNormal();
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001393 }
Doug Zongker512536a2010-02-17 16:11:44 -08001394 }
1395
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001396 // For images, we need to maintain the parallel structure of the chunk lists, so do the merging
1397 // in both the source and target lists.
1398 tgt_image->MergeAdjacentNormalChunks();
1399 src_image->MergeAdjacentNormalChunks();
1400 if (tgt_image->NumOfChunks() != src_image->NumOfChunks()) {
1401 // This shouldn't happen.
1402 printf("merging normal chunks went awry\n");
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001403 return false;
Doug Zongker512536a2010-02-17 16:11:44 -08001404 }
Doug Zongker512536a2010-02-17 16:11:44 -08001405
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001406 return true;
Doug Zongker512536a2010-02-17 16:11:44 -08001407}
1408
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001409// In image mode, generate patches against the given source chunks and bonus_data; write the
1410// result to |patch_name|.
Tianjie Xud82a2ed2017-08-08 17:35:01 -07001411bool ImageModeImage::GeneratePatches(const ImageModeImage& tgt_image,
1412 const ImageModeImage& src_image,
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001413 const std::string& patch_name) {
Tianjie Xud82a2ed2017-08-08 17:35:01 -07001414 printf("Construct patches for %zu chunks...\n", tgt_image.NumOfChunks());
1415 std::vector<PatchChunk> patch_chunks;
1416 patch_chunks.reserve(tgt_image.NumOfChunks());
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001417
Tianjie Xud82a2ed2017-08-08 17:35:01 -07001418 for (size_t i = 0; i < tgt_image.NumOfChunks(); i++) {
1419 const auto& tgt_chunk = tgt_image[i];
1420 const auto& src_chunk = src_image[i];
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001421
Tianjie Xud82a2ed2017-08-08 17:35:01 -07001422 if (PatchChunk::RawDataIsSmaller(tgt_chunk, 0)) {
1423 patch_chunks.emplace_back(tgt_chunk);
1424 continue;
Doug Zongker512536a2010-02-17 16:11:44 -08001425 }
1426
Tianjie Xud82a2ed2017-08-08 17:35:01 -07001427 std::vector<uint8_t> patch_data;
1428 if (!ImageChunk::MakePatch(tgt_chunk, src_chunk, &patch_data, nullptr)) {
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001429 printf("Failed to generate patch for target chunk %zu: ", i);
1430 return false;
Doug Zongker512536a2010-02-17 16:11:44 -08001431 }
Tianjie Xud82a2ed2017-08-08 17:35:01 -07001432 printf("patch %3zu is %zu bytes (of %zu)\n", i, patch_data.size(),
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001433 tgt_chunk.GetRawDataLength());
Tianjie Xud82a2ed2017-08-08 17:35:01 -07001434
1435 if (PatchChunk::RawDataIsSmaller(tgt_chunk, patch_data.size())) {
1436 patch_chunks.emplace_back(tgt_chunk);
1437 } else {
1438 patch_chunks.emplace_back(tgt_chunk, src_chunk, std::move(patch_data));
1439 }
Doug Zongker512536a2010-02-17 16:11:44 -08001440 }
Doug Zongker512536a2010-02-17 16:11:44 -08001441
Tianjie Xud82a2ed2017-08-08 17:35:01 -07001442 CHECK_EQ(tgt_image.NumOfChunks(), patch_chunks.size());
1443
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001444 android::base::unique_fd patch_fd(
1445 open(patch_name.c_str(), O_CREAT | O_WRONLY | O_TRUNC, S_IRUSR | S_IWUSR));
1446 if (patch_fd == -1) {
1447 printf("failed to open \"%s\": %s\n", patch_name.c_str(), strerror(errno));
1448 return false;
Doug Zongker512536a2010-02-17 16:11:44 -08001449 }
Doug Zongker512536a2010-02-17 16:11:44 -08001450
Tianjie Xud82a2ed2017-08-08 17:35:01 -07001451 return PatchChunk::WritePatchDataToFd(patch_chunks, patch_fd);
Doug Zongker512536a2010-02-17 16:11:44 -08001452}
1453
Tao Bao97555da2016-12-15 10:15:06 -08001454int imgdiff(int argc, const char** argv) {
1455 bool zip_mode = false;
Tianjie Xu1ea84d62017-02-22 18:23:58 -08001456 std::vector<uint8_t> bonus_data;
Tianjie Xu2903cdd2017-08-18 18:15:47 -07001457 size_t blocks_limit = 0;
Tianjie Xu82582b42017-08-31 18:05:19 -07001458 std::string split_info_file;
Tianjie Xu2903cdd2017-08-18 18:15:47 -07001459 std::string debug_dir;
Tianjie Xu12b90552017-03-07 14:44:14 -08001460
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001461 int opt;
Tianjie Xu2903cdd2017-08-18 18:15:47 -07001462 int option_index;
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001463 optind = 1; // Reset the getopt state so that we can call it multiple times for test.
Doug Zongkera3ccba62012-08-20 15:28:02 -07001464
Tianjie Xu2903cdd2017-08-18 18:15:47 -07001465 while ((opt = getopt_long(argc, const_cast<char**>(argv), "zb:", OPTIONS, &option_index)) != -1) {
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001466 switch (opt) {
1467 case 'z':
1468 zip_mode = true;
1469 break;
1470 case 'b': {
1471 android::base::unique_fd fd(open(optarg, O_RDONLY));
1472 if (fd == -1) {
1473 printf("failed to open bonus file %s: %s\n", optarg, strerror(errno));
1474 return 1;
1475 }
1476 struct stat st;
1477 if (fstat(fd, &st) != 0) {
1478 printf("failed to stat bonus file %s: %s\n", optarg, strerror(errno));
1479 return 1;
1480 }
1481
1482 size_t bonus_size = st.st_size;
1483 bonus_data.resize(bonus_size);
1484 if (!android::base::ReadFully(fd, bonus_data.data(), bonus_size)) {
1485 printf("failed to read bonus file %s: %s\n", optarg, strerror(errno));
1486 return 1;
1487 }
1488 break;
1489 }
Tianjie Xu2903cdd2017-08-18 18:15:47 -07001490 case 0: {
1491 std::string name = OPTIONS[option_index].name;
1492 if (name == "block-limit" && !android::base::ParseUint(optarg, &blocks_limit)) {
1493 printf("failed to parse size blocks_limit: %s\n", optarg);
1494 return 1;
Tianjie Xu82582b42017-08-31 18:05:19 -07001495 } else if (name == "split-info") {
1496 split_info_file = optarg;
Tianjie Xu2903cdd2017-08-18 18:15:47 -07001497 } else if (name == "debug-dir") {
1498 debug_dir = optarg;
1499 }
1500 break;
1501 }
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001502 default:
1503 printf("unexpected opt: %s\n", optarg);
1504 return 2;
1505 }
Doug Zongkera3ccba62012-08-20 15:28:02 -07001506 }
1507
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001508 if (argc - optind != 3) {
Tianjie Xu2903cdd2017-08-18 18:15:47 -07001509 printf("usage: %s [options] <src-img> <tgt-img> <patch-file>\n", argv[0]);
1510 printf(
1511 " -z <zip-mode>, Generate patches in zip mode, src and tgt should be zip files.\n"
1512 " -b <bonus-file>, Bonus file in addition to src, image mode only.\n"
1513 " --block-limit, For large zips, split the src and tgt based on the block limit;\n"
1514 " and generate patches between each pair of pieces. Concatenate these\n"
1515 " patches together and output them into <patch-file>.\n"
Tianjie Xu82582b42017-08-31 18:05:19 -07001516 " --split-info, Output the split information (patch_size, tgt_size, src_ranges);\n"
1517 " zip mode with block-limit only.\n"
Tianjie Xu2903cdd2017-08-18 18:15:47 -07001518 " --debug_dir, Debug directory to put the split srcs and patches, zip mode only.\n");
Doug Zongkera3ccba62012-08-20 15:28:02 -07001519 return 2;
1520 }
Doug Zongker512536a2010-02-17 16:11:44 -08001521
Doug Zongker512536a2010-02-17 16:11:44 -08001522 if (zip_mode) {
Tianjie Xu2903cdd2017-08-18 18:15:47 -07001523 ZipModeImage src_image(true, blocks_limit * BLOCK_SIZE);
1524 ZipModeImage tgt_image(false, blocks_limit * BLOCK_SIZE);
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001525
1526 if (!src_image.Initialize(argv[optind])) {
Doug Zongker512536a2010-02-17 16:11:44 -08001527 return 1;
1528 }
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001529 if (!tgt_image.Initialize(argv[optind + 1])) {
1530 return 1;
1531 }
1532
1533 if (!ZipModeImage::CheckAndProcessChunks(&tgt_image, &src_image)) {
1534 return 1;
1535 }
Tianjie Xu2903cdd2017-08-18 18:15:47 -07001536
1537 // TODO save and output the split information so that caller can create split transfer lists
1538 // accordingly.
1539
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001540 // Compute bsdiff patches for each chunk's data (the uncompressed data, in the case of
1541 // deflate chunks).
Tianjie Xu2903cdd2017-08-18 18:15:47 -07001542 if (blocks_limit > 0) {
Tianjie Xu82582b42017-08-31 18:05:19 -07001543 if (split_info_file.empty()) {
1544 printf("split-info path cannot be empty when generating patches with a block-limit.\n");
1545 return 1;
1546 }
1547
Tianjie Xu2903cdd2017-08-18 18:15:47 -07001548 std::vector<ZipModeImage> split_tgt_images;
1549 std::vector<ZipModeImage> split_src_images;
1550 std::vector<SortedRangeSet> split_src_ranges;
1551 ZipModeImage::SplitZipModeImageWithLimit(tgt_image, src_image, &split_tgt_images,
1552 &split_src_images, &split_src_ranges);
1553
1554 if (!ZipModeImage::GeneratePatches(split_tgt_images, split_src_images, split_src_ranges,
Tianjie Xu82582b42017-08-31 18:05:19 -07001555 argv[optind + 2], split_info_file, debug_dir)) {
Tianjie Xu2903cdd2017-08-18 18:15:47 -07001556 return 1;
1557 }
1558
1559 } else if (!ZipModeImage::GeneratePatches(tgt_image, src_image, argv[optind + 2])) {
Doug Zongker512536a2010-02-17 16:11:44 -08001560 return 1;
1561 }
1562 } else {
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001563 ImageModeImage src_image(true);
1564 ImageModeImage tgt_image(false);
1565
1566 if (!src_image.Initialize(argv[optind])) {
Doug Zongker512536a2010-02-17 16:11:44 -08001567 return 1;
1568 }
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001569 if (!tgt_image.Initialize(argv[optind + 1])) {
Doug Zongker512536a2010-02-17 16:11:44 -08001570 return 1;
1571 }
1572
Tianjie Xu6b03ba72017-07-19 14:16:30 -07001573 if (!ImageModeImage::CheckAndProcessChunks(&tgt_image, &src_image)) {
Doug Zongker512536a2010-02-17 16:11:44 -08001574 return 1;
1575 }
Tianjie Xud82a2ed2017-08-08 17:35:01 -07001576
1577 if (!bonus_data.empty() && !src_image.SetBonusData(bonus_data)) {
1578 return 1;
1579 }
1580
1581 if (!ImageModeImage::GeneratePatches(tgt_image, src_image, argv[optind + 2])) {
Doug Zongker512536a2010-02-17 16:11:44 -08001582 return 1;
1583 }
1584 }
1585
Doug Zongker512536a2010-02-17 16:11:44 -08001586 return 0;
1587}