From 57dd96199570beb29ea8b0f3934c594cd42e3043 Mon Sep 17 00:00:00 2001 From: Tianjie Xu Date: Thu, 17 Aug 2017 17:50:56 -0700 Subject: Move Image/ImageChunk/PatchChunk declaration into header files 1. Move the declaration of the Image classes to the header file to make testing easier. 2. Also move rangeset.h to bootable/recovery to allow access in imgdiff. Test: recovery component test Change-Id: I68a863e60a3f2e7ae46ee48f48eb15391f5f4330 --- applypatch/Android.mk | 9 +- applypatch/imgdiff.cpp | 335 +++++--------------------- applypatch/include/applypatch/imgdiff_image.h | 247 +++++++++++++++++++ rangeset.h | 278 +++++++++++++++++++++ tests/unit/rangeset_test.cpp | 2 +- updater/blockimg.cpp | 2 +- updater/include/updater/rangeset.h | 278 --------------------- 7 files changed, 599 insertions(+), 552 deletions(-) create mode 100644 applypatch/include/applypatch/imgdiff_image.h create mode 100644 rangeset.h delete mode 100644 updater/include/updater/rangeset.h diff --git a/applypatch/Android.mk b/applypatch/Android.mk index 7aed0a95a..e38207c22 100644 --- a/applypatch/Android.mk +++ b/applypatch/Android.mk @@ -151,7 +151,8 @@ LOCAL_CFLAGS := \ LOCAL_STATIC_LIBRARIES := \ $(libimgdiff_static_libraries) LOCAL_C_INCLUDES := \ - $(LOCAL_PATH)/include + $(LOCAL_PATH)/include \ + bootable/recovery LOCAL_EXPORT_C_INCLUDE_DIRS := $(LOCAL_PATH)/include include $(BUILD_STATIC_LIBRARY) @@ -166,7 +167,8 @@ LOCAL_CFLAGS := \ LOCAL_STATIC_LIBRARIES := \ $(libimgdiff_static_libraries) LOCAL_C_INCLUDES := \ - $(LOCAL_PATH)/include + $(LOCAL_PATH)/include \ + bootable/recovery LOCAL_EXPORT_C_INCLUDE_DIRS := $(LOCAL_PATH)/include include $(BUILD_HOST_STATIC_LIBRARY) @@ -180,4 +182,7 @@ LOCAL_STATIC_LIBRARIES := \ libimgdiff \ $(libimgdiff_static_libraries) \ libbz +LOCAL_C_INCLUDES := \ + $(LOCAL_PATH)/include \ + bootable/recovery include $(BUILD_HOST_EXECUTABLE) diff --git a/applypatch/imgdiff.cpp b/applypatch/imgdiff.cpp index a81e385a3..59b600713 100644 --- a/applypatch/imgdiff.cpp +++ b/applypatch/imgdiff.cpp @@ -140,11 +140,12 @@ #include #include #include -#include - #include +#include #include +#include "applypatch/imgdiff_image.h" + using android::base::get_unaligned; static constexpr auto BUFFER_SIZE = 0x8000; @@ -161,99 +162,16 @@ static inline bool Write4(int fd, int32_t value) { return android::base::WriteFully(fd, &value, sizeof(int32_t)); } -class ImageChunk { - public: - static constexpr auto WINDOWBITS = -15; // 32kb window; negative to indicate a raw stream. - static constexpr auto MEMLEVEL = 8; // the default value. - static constexpr auto METHOD = Z_DEFLATED; - static constexpr auto STRATEGY = Z_DEFAULT_STRATEGY; - - ImageChunk(int type, size_t start, const std::vector* file_content, size_t raw_data_len, - std::string entry_name = {}) - : type_(type), - start_(start), - input_file_ptr_(file_content), - raw_data_len_(raw_data_len), - compress_level_(6), - entry_name_(std::move(entry_name)) { - CHECK(file_content != nullptr) << "input file container can't be nullptr"; - } - - int GetType() const { - return type_; - } - size_t GetRawDataLength() const { - return raw_data_len_; - } - const std::string& GetEntryName() const { - return entry_name_; - } - size_t GetStartOffset() const { - return start_; - } - int GetCompressLevel() const { - return compress_level_; - } - - // CHUNK_DEFLATE will return the uncompressed data for diff, while other types will simply return - // the raw data. - const uint8_t * DataForPatch() const; - size_t DataLengthForPatch() const; - - void Dump() const { - printf("type: %d, start: %zu, len: %zu, name: %s\n", type_, start_, DataLengthForPatch(), - entry_name_.c_str()); - } - - void SetUncompressedData(std::vector data); - bool SetBonusData(const std::vector& bonus_data); - - bool operator==(const ImageChunk& other) const; - bool operator!=(const ImageChunk& other) const { - return !(*this == other); - } - - /* - * Cause a gzip chunk to be treated as a normal chunk (ie, as a blob of uninterpreted data). - * The resulting patch will likely be about as big as the target file, but it lets us handle - * the case of images where some gzip chunks are reconstructible but others aren't (by treating - * the ones that aren't as normal chunks). - */ - void ChangeDeflateChunkToNormal(); - - /* - * Verify that we can reproduce exactly the same compressed data that we started with. Sets the - * level, method, windowBits, memLevel, and strategy fields in the chunk to the encoding - * parameters needed to produce the right output. - */ - bool ReconstructDeflateChunk(); - bool IsAdjacentNormal(const ImageChunk& other) const; - void MergeAdjacentNormal(const ImageChunk& other); - - /* - * Compute a bsdiff patch between |src| and |tgt|; Store the result in the patch_data. - * |bsdiff_cache| can be used to cache the suffix array if the same |src| chunk is used - * repeatedly, pass nullptr if not needed. - */ - static bool MakePatch(const ImageChunk& tgt, const ImageChunk& src, - std::vector* patch_data, saidx_t** bsdiff_cache); - - private: - const uint8_t* GetRawData() const; - bool TryReconstruction(int level); - - int type_; // CHUNK_NORMAL, CHUNK_DEFLATE, CHUNK_RAW - size_t start_; // offset of chunk in the original input file - const std::vector* input_file_ptr_; // ptr to the full content of original input file - size_t raw_data_len_; - - // deflate encoder parameters - int compress_level_; - - // --- for CHUNK_DEFLATE chunks only: --- - std::vector uncompressed_data_; - std::string entry_name_; // used for zip entries -}; +ImageChunk::ImageChunk(int type, size_t start, const std::vector* file_content, + size_t raw_data_len, std::string entry_name) + : type_(type), + start_(start), + input_file_ptr_(file_content), + raw_data_len_(raw_data_len), + compress_level_(6), + entry_name_(std::move(entry_name)) { + CHECK(file_content != nullptr) << "input file container can't be nullptr"; +} const uint8_t* ImageChunk::GetRawData() const { CHECK_LE(start_ + raw_data_len_, input_file_ptr_->size()); @@ -424,57 +342,28 @@ bool ImageChunk::TryReconstruction(int level) { return true; } -// PatchChunk stores the patch data between a source chunk and a target chunk. It also keeps track -// of the metadata of src&tgt chunks (e.g. offset, raw data length, uncompressed data length). -class PatchChunk { - public: - PatchChunk(const ImageChunk& tgt, const ImageChunk& src, std::vector data) - : type_(tgt.GetType()), - source_start_(src.GetStartOffset()), - source_len_(src.GetRawDataLength()), - source_uncompressed_len_(src.DataLengthForPatch()), - target_start_(tgt.GetStartOffset()), - target_len_(tgt.GetRawDataLength()), - target_uncompressed_len_(tgt.DataLengthForPatch()), - target_compress_level_(tgt.GetCompressLevel()), - data_(std::move(data)) {} - - // Construct a CHUNK_RAW patch from the target data directly. - explicit PatchChunk(const ImageChunk& tgt) - : type_(CHUNK_RAW), - source_start_(0), - source_len_(0), - source_uncompressed_len_(0), - target_start_(tgt.GetStartOffset()), - target_len_(tgt.GetRawDataLength()), - target_uncompressed_len_(tgt.DataLengthForPatch()), - target_compress_level_(tgt.GetCompressLevel()), - data_(tgt.DataForPatch(), tgt.DataForPatch() + tgt.DataLengthForPatch()) {} - - // Return true if raw data size is smaller than the patch size. - static bool RawDataIsSmaller(const ImageChunk& tgt, size_t patch_size); - - static bool WritePatchDataToFd(const std::vector& patch_chunks, int patch_fd); - - private: - size_t GetHeaderSize() const; - size_t WriteHeaderToFd(int fd, size_t offset) const; - - // The patch chunk type is the same as the target chunk type. The only exception is we change - // the |type_| to CHUNK_RAW if target length is smaller than the patch size. - int type_; - - size_t source_start_; - size_t source_len_; - size_t source_uncompressed_len_; - - size_t target_start_; // offset of the target chunk within the target file - size_t target_len_; - size_t target_uncompressed_len_; - size_t target_compress_level_; // the deflate compression level of the target chunk. - - std::vector data_; // storage for the patch data -}; +PatchChunk::PatchChunk(const ImageChunk& tgt, const ImageChunk& src, std::vector data) + : type_(tgt.GetType()), + source_start_(src.GetStartOffset()), + source_len_(src.GetRawDataLength()), + source_uncompressed_len_(src.DataLengthForPatch()), + target_start_(tgt.GetStartOffset()), + target_len_(tgt.GetRawDataLength()), + target_uncompressed_len_(tgt.DataLengthForPatch()), + target_compress_level_(tgt.GetCompressLevel()), + data_(std::move(data)) {} + +// Construct a CHUNK_RAW patch from the target data directly. +PatchChunk::PatchChunk(const ImageChunk& tgt) + : type_(CHUNK_RAW), + source_start_(0), + source_len_(0), + source_uncompressed_len_(0), + target_start_(tgt.GetStartOffset()), + target_len_(tgt.GetRawDataLength()), + target_uncompressed_len_(tgt.DataLengthForPatch()), + target_compress_level_(tgt.GetCompressLevel()), + data_(tgt.DataForPatch(), tgt.DataForPatch() + tgt.DataLengthForPatch()) {} // Return true if raw data is smaller than the patch size. bool PatchChunk::RawDataIsSmaller(const ImageChunk& tgt, size_t patch_size) { @@ -574,59 +463,15 @@ bool PatchChunk::WritePatchDataToFd(const std::vector& patch_chunks, return true; } -// Interface for zip_mode and image_mode images. We initialize the image from an input file and -// split the file content into a list of image chunks. -class Image { - public: - explicit Image(bool is_source) : is_source_(is_source) {} - - virtual ~Image() {} - - // Create a list of image chunks from input file. - virtual bool Initialize(const std::string& filename) = 0; - - // Look for runs of adjacent normal chunks and compress them down into a single chunk. (Such - // runs can be produced when deflate chunks are changed to normal chunks.) - void MergeAdjacentNormalChunks(); - - // In zip mode, find the matching deflate source chunk by entry name. Search for normal chunks - // also if |find_normal| is true. - ImageChunk* FindChunkByName(const std::string& name, bool find_normal = false); - - const ImageChunk* FindChunkByName(const std::string& name, bool find_normal = false) const; - - void DumpChunks() const; - - // Non const iterators to access the stored ImageChunks. - std::vector::iterator begin() { - return chunks_.begin(); - } - - std::vector::iterator end() { - return chunks_.end(); - } - - ImageChunk& operator[](size_t i) { - CHECK_LT(i, chunks_.size()); - return chunks_[i]; - } - - const ImageChunk& operator[](size_t i) const { - CHECK_LT(i, chunks_.size()); - return chunks_[i]; - } - - size_t NumOfChunks() const { - return chunks_.size(); - } - - protected: - bool ReadFile(const std::string& filename, std::vector* file_content); +ImageChunk& Image::operator[](size_t i) { + CHECK_LT(i, chunks_.size()); + return chunks_[i]; +} - bool is_source_; // True if it's for source chunks. - std::vector chunks_; // Internal storage of ImageChunk. - std::vector file_content_; // Store the whole input file in memory. -}; +const ImageChunk& Image::operator[](size_t i) const { + CHECK_LT(i, chunks_.size()); + return chunks_[i]; +} void Image::MergeAdjacentNormalChunks() { size_t merged_last = 0, cur = 0; @@ -650,23 +495,6 @@ void Image::MergeAdjacentNormalChunks() { } } -const ImageChunk* Image::FindChunkByName(const std::string& name, bool find_normal) const { - if (name.empty()) { - return nullptr; - } - for (auto& chunk : chunks_) { - if ((chunk.GetType() == CHUNK_DEFLATE || find_normal) && chunk.GetEntryName() == name) { - return &chunk; - } - } - return nullptr; -} - -ImageChunk* Image::FindChunkByName(const std::string& name, bool find_normal) { - return const_cast( - static_cast(this)->FindChunkByName(name, find_normal)); -} - void Image::DumpChunks() const { std::string type = is_source_ ? "source" : "target"; printf("Dumping chunks for %s\n", type.c_str()); @@ -701,39 +529,6 @@ bool Image::ReadFile(const std::string& filename, std::vector* file_con return true; } -class ZipModeImage : public Image { - public: - explicit ZipModeImage(bool is_source) : Image(is_source) {} - - bool Initialize(const std::string& filename) override; - - const ImageChunk& PseudoSource() const { - CHECK(is_source_); - CHECK(pseudo_source_ != nullptr); - return *pseudo_source_; - } - - // Verify that we can reconstruct the deflate chunks; also change the type to CHUNK_NORMAL if - // src and tgt are identical. - static bool CheckAndProcessChunks(ZipModeImage* tgt_image, ZipModeImage* src_image); - - // Compute the patch between tgt & src images, and write the data into |patch_name|. - static bool GeneratePatches(const ZipModeImage& tgt_image, const ZipModeImage& src_image, - const std::string& patch_name); - - private: - // Initialize image chunks based on the zip entries. - bool InitializeChunks(const std::string& filename, ZipArchiveHandle handle); - // Add the a zip entry to the list. - bool AddZipEntryToChunks(ZipArchiveHandle handle, const std::string& entry_name, ZipEntry* entry); - // Return the real size of the zip file. (omit the trailing zeros that used for alignment) - bool GetZipFileSize(size_t* input_file_size); - - // The pesudo source chunk for bsdiff if there's no match for the given target chunk. It's in - // fact the whole source file. - std::unique_ptr pseudo_source_; -}; - bool ZipModeImage::Initialize(const std::string& filename) { if (!ReadFile(filename, &file_content_)) { return false; @@ -754,9 +549,6 @@ bool ZipModeImage::Initialize(const std::string& filename) { return false; } - if (is_source_) { - pseudo_source_ = std::make_unique(CHUNK_NORMAL, 0, &file_content_, zipfile_size); - } if (!InitializeChunks(filename, handle)) { CloseArchive(handle); return false; @@ -895,6 +687,28 @@ bool ZipModeImage::GetZipFileSize(size_t* input_file_size) { return false; } +ImageChunk ZipModeImage::PseudoSource() const { + CHECK(is_source_); + return ImageChunk(CHUNK_NORMAL, 0, &file_content_, file_content_.size()); +} + +const ImageChunk* ZipModeImage::FindChunkByName(const std::string& name, bool find_normal) const { + if (name.empty()) { + return nullptr; + } + for (auto& chunk : chunks_) { + if ((chunk.GetType() == CHUNK_DEFLATE || find_normal) && chunk.GetEntryName() == name) { + return &chunk; + } + } + return nullptr; +} + +ImageChunk* ZipModeImage::FindChunkByName(const std::string& name, bool find_normal) { + return const_cast( + static_cast(this)->FindChunkByName(name, find_normal)); +} + bool ZipModeImage::CheckAndProcessChunks(ZipModeImage* tgt_image, ZipModeImage* src_image) { for (auto& tgt_chunk : *tgt_image) { if (tgt_chunk.GetType() != CHUNK_DEFLATE) { @@ -981,25 +795,6 @@ bool ZipModeImage::GeneratePatches(const ZipModeImage& tgt_image, const ZipModeI return PatchChunk::WritePatchDataToFd(patch_chunks, patch_fd); } -class ImageModeImage : public Image { - public: - explicit ImageModeImage(bool is_source) : Image(is_source) {} - - // Initialize the image chunks list by searching the magic numbers in an image file. - bool Initialize(const std::string& filename) override; - - bool SetBonusData(const std::vector& bonus_data); - - // In Image Mode, verify that the source and target images have the same chunk structure (ie, the - // same sequence of deflate and normal chunks). - static bool CheckAndProcessChunks(ImageModeImage* tgt_image, ImageModeImage* src_image); - - // In image mode, generate patches against the given source chunks and bonus_data; write the - // result to |patch_name|. - static bool GeneratePatches(const ImageModeImage& tgt_image, const ImageModeImage& src_image, - const std::string& patch_name); -}; - bool ImageModeImage::Initialize(const std::string& filename) { if (!ReadFile(filename, &file_content_)) { return false; diff --git a/applypatch/include/applypatch/imgdiff_image.h b/applypatch/include/applypatch/imgdiff_image.h new file mode 100644 index 000000000..221dd5ab5 --- /dev/null +++ b/applypatch/include/applypatch/imgdiff_image.h @@ -0,0 +1,247 @@ +/* + * Copyright (C) 2017 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef _APPLYPATCH_IMGDIFF_IMAGE_H +#define _APPLYPATCH_IMGDIFF_IMAGE_H + +#include +#include +#include + +#include +#include + +#include +#include +#include + +#include "imgdiff.h" +#include "rangeset.h" + +class ImageChunk { + public: + static constexpr auto WINDOWBITS = -15; // 32kb window; negative to indicate a raw stream. + static constexpr auto MEMLEVEL = 8; // the default value. + static constexpr auto METHOD = Z_DEFLATED; + static constexpr auto STRATEGY = Z_DEFAULT_STRATEGY; + + ImageChunk(int type, size_t start, const std::vector* file_content, size_t raw_data_len, + std::string entry_name = {}); + + int GetType() const { + return type_; + } + size_t GetRawDataLength() const { + return raw_data_len_; + } + const std::string& GetEntryName() const { + return entry_name_; + } + size_t GetStartOffset() const { + return start_; + } + int GetCompressLevel() const { + return compress_level_; + } + + // CHUNK_DEFLATE will return the uncompressed data for diff, while other types will simply return + // the raw data. + const uint8_t* DataForPatch() const; + size_t DataLengthForPatch() const; + + void Dump() const { + printf("type: %d, start: %zu, len: %zu, name: %s\n", type_, start_, DataLengthForPatch(), + entry_name_.c_str()); + } + + void SetUncompressedData(std::vector data); + bool SetBonusData(const std::vector& bonus_data); + + bool operator==(const ImageChunk& other) const; + bool operator!=(const ImageChunk& other) const { + return !(*this == other); + } + + /* + * Cause a gzip chunk to be treated as a normal chunk (ie, as a blob of uninterpreted data). + * The resulting patch will likely be about as big as the target file, but it lets us handle + * the case of images where some gzip chunks are reconstructible but others aren't (by treating + * the ones that aren't as normal chunks). + */ + void ChangeDeflateChunkToNormal(); + + /* + * Verify that we can reproduce exactly the same compressed data that we started with. Sets the + * level, method, windowBits, memLevel, and strategy fields in the chunk to the encoding + * parameters needed to produce the right output. + */ + bool ReconstructDeflateChunk(); + bool IsAdjacentNormal(const ImageChunk& other) const; + void MergeAdjacentNormal(const ImageChunk& other); + + /* + * Compute a bsdiff patch between |src| and |tgt|; Store the result in the patch_data. + * |bsdiff_cache| can be used to cache the suffix array if the same |src| chunk is used + * repeatedly, pass nullptr if not needed. + */ + static bool MakePatch(const ImageChunk& tgt, const ImageChunk& src, + std::vector* patch_data, saidx_t** bsdiff_cache); + + private: + const uint8_t* GetRawData() const; + bool TryReconstruction(int level); + + int type_; // CHUNK_NORMAL, CHUNK_DEFLATE, CHUNK_RAW + size_t start_; // offset of chunk in the original input file + const std::vector* input_file_ptr_; // ptr to the full content of original input file + size_t raw_data_len_; + + // deflate encoder parameters + int compress_level_; + + // --- for CHUNK_DEFLATE chunks only: --- + std::vector uncompressed_data_; + std::string entry_name_; // used for zip entries +}; + +// PatchChunk stores the patch data between a source chunk and a target chunk. It also keeps track +// of the metadata of src&tgt chunks (e.g. offset, raw data length, uncompressed data length). +class PatchChunk { + public: + PatchChunk(const ImageChunk& tgt, const ImageChunk& src, std::vector data); + + // Construct a CHUNK_RAW patch from the target data directly. + explicit PatchChunk(const ImageChunk& tgt); + + // Return true if raw data size is smaller than the patch size. + static bool RawDataIsSmaller(const ImageChunk& tgt, size_t patch_size); + + static bool WritePatchDataToFd(const std::vector& patch_chunks, int patch_fd); + + private: + size_t GetHeaderSize() const; + size_t WriteHeaderToFd(int fd, size_t offset) const; + + // The patch chunk type is the same as the target chunk type. The only exception is we change + // the |type_| to CHUNK_RAW if target length is smaller than the patch size. + int type_; + + size_t source_start_; + size_t source_len_; + size_t source_uncompressed_len_; + + size_t target_start_; // offset of the target chunk within the target file + size_t target_len_; + size_t target_uncompressed_len_; + size_t target_compress_level_; // the deflate compression level of the target chunk. + + std::vector data_; // storage for the patch data +}; + +// Interface for zip_mode and image_mode images. We initialize the image from an input file and +// split the file content into a list of image chunks. +class Image { + public: + explicit Image(bool is_source) : is_source_(is_source) {} + + virtual ~Image() {} + + // Create a list of image chunks from input file. + virtual bool Initialize(const std::string& filename) = 0; + + // Look for runs of adjacent normal chunks and compress them down into a single chunk. (Such + // runs can be produced when deflate chunks are changed to normal chunks.) + void MergeAdjacentNormalChunks(); + + void DumpChunks() const; + + // Non const iterators to access the stored ImageChunks. + std::vector::iterator begin() { + return chunks_.begin(); + } + + std::vector::iterator end() { + return chunks_.end(); + } + + ImageChunk& operator[](size_t i); + const ImageChunk& operator[](size_t i) const; + + size_t NumOfChunks() const { + return chunks_.size(); + } + + protected: + bool ReadFile(const std::string& filename, std::vector* file_content); + + bool is_source_; // True if it's for source chunks. + std::vector chunks_; // Internal storage of ImageChunk. + std::vector file_content_; // Store the whole input file in memory. +}; + +class ZipModeImage : public Image { + public: + explicit ZipModeImage(bool is_source) : Image(is_source) {} + + bool Initialize(const std::string& filename) override; + + // The pesudo source chunk for bsdiff if there's no match for the given target chunk. It's in + // fact the whole source file. + ImageChunk PseudoSource() const; + + // Find the matching deflate source chunk by entry name. Search for normal chunks also if + // |find_normal| is true. + ImageChunk* FindChunkByName(const std::string& name, bool find_normal = false); + + const ImageChunk* FindChunkByName(const std::string& name, bool find_normal = false) const; + + // Verify that we can reconstruct the deflate chunks; also change the type to CHUNK_NORMAL if + // src and tgt are identical. + static bool CheckAndProcessChunks(ZipModeImage* tgt_image, ZipModeImage* src_image); + + // Compute the patch between tgt & src images, and write the data into |patch_name|. + static bool GeneratePatches(const ZipModeImage& tgt_image, const ZipModeImage& src_image, + const std::string& patch_name); + + private: + // Initialize image chunks based on the zip entries. + bool InitializeChunks(const std::string& filename, ZipArchiveHandle handle); + // Add the a zip entry to the list. + bool AddZipEntryToChunks(ZipArchiveHandle handle, const std::string& entry_name, ZipEntry* entry); + // Return the real size of the zip file. (omit the trailing zeros that used for alignment) + bool GetZipFileSize(size_t* input_file_size); +}; + +class ImageModeImage : public Image { + public: + explicit ImageModeImage(bool is_source) : Image(is_source) {} + + // Initialize the image chunks list by searching the magic numbers in an image file. + bool Initialize(const std::string& filename) override; + + bool SetBonusData(const std::vector& bonus_data); + + // In Image Mode, verify that the source and target images have the same chunk structure (ie, the + // same sequence of deflate and normal chunks). + static bool CheckAndProcessChunks(ImageModeImage* tgt_image, ImageModeImage* src_image); + + // In image mode, generate patches against the given source chunks and bonus_data; write the + // result to |patch_name|. + static bool GeneratePatches(const ImageModeImage& tgt_image, const ImageModeImage& src_image, + const std::string& patch_name); +}; + +#endif // _APPLYPATCH_IMGDIFF_IMAGE_H diff --git a/rangeset.h b/rangeset.h new file mode 100644 index 000000000..f224a08be --- /dev/null +++ b/rangeset.h @@ -0,0 +1,278 @@ +/* + * Copyright (C) 2017 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#pragma once + +#include + +#include +#include +#include + +#include +#include +#include +#include + +using Range = std::pair; + +class RangeSet { + public: + RangeSet() : blocks_(0) {} + + explicit RangeSet(std::vector&& pairs) { + CHECK_NE(pairs.size(), static_cast(0)) << "Invalid number of tokens"; + + // Sanity check the input. + size_t result = 0; + for (const auto& range : pairs) { + CHECK_LT(range.first, range.second) + << "Empty or negative range: " << range.first << ", " << range.second; + size_t sz = range.second - range.first; + CHECK_LE(result, SIZE_MAX - sz) << "RangeSet size overflow"; + result += sz; + } + + ranges_ = pairs; + blocks_ = result; + } + + static RangeSet Parse(const std::string& range_text) { + std::vector pieces = android::base::Split(range_text, ","); + CHECK_GE(pieces.size(), static_cast(3)) << "Invalid range text: " << range_text; + + size_t num; + CHECK(android::base::ParseUint(pieces[0], &num, static_cast(INT_MAX))) + << "Failed to parse the number of tokens: " << range_text; + + CHECK_NE(num, static_cast(0)) << "Invalid number of tokens: " << range_text; + CHECK_EQ(num % 2, static_cast(0)) << "Number of tokens must be even: " << range_text; + CHECK_EQ(num, pieces.size() - 1) << "Mismatching number of tokens: " << range_text; + + std::vector pairs; + for (size_t i = 0; i < num; i += 2) { + size_t first; + CHECK(android::base::ParseUint(pieces[i + 1], &first, static_cast(INT_MAX))); + size_t second; + CHECK(android::base::ParseUint(pieces[i + 2], &second, static_cast(INT_MAX))); + + pairs.emplace_back(first, second); + } + + return RangeSet(std::move(pairs)); + } + + std::string ToString() const { + if (ranges_.empty()) { + return ""; + } + std::string result = std::to_string(ranges_.size() * 2); + for (const auto& r : ranges_) { + result += android::base::StringPrintf(",%zu,%zu", r.first, r.second); + } + + return result; + } + + // Get the block number for the i-th (starting from 0) block in the RangeSet. + size_t GetBlockNumber(size_t idx) const { + CHECK_LT(idx, blocks_) << "Out of bound index " << idx << " (total blocks: " << blocks_ << ")"; + + for (const auto& range : ranges_) { + if (idx < range.second - range.first) { + return range.first + idx; + } + idx -= (range.second - range.first); + } + + CHECK(false) << "Failed to find block number for index " << idx; + return 0; // Unreachable, but to make compiler happy. + } + + // RangeSet has half-closed half-open bounds. For example, "3,5" contains blocks 3 and 4. So "3,5" + // and "5,7" are not overlapped. + bool Overlaps(const RangeSet& other) const { + for (const auto& range : ranges_) { + size_t start = range.first; + size_t end = range.second; + for (const auto& other_range : other.ranges_) { + size_t other_start = other_range.first; + size_t other_end = other_range.second; + // [start, end) vs [other_start, other_end) + if (!(other_start >= end || start >= other_end)) { + return true; + } + } + } + return false; + } + + // size() gives the number of Range's in this RangeSet. + size_t size() const { + return ranges_.size(); + } + + // blocks() gives the number of all blocks in this RangeSet. + size_t blocks() const { + return blocks_; + } + + // We provide const iterators only. + std::vector::const_iterator cbegin() const { + return ranges_.cbegin(); + } + + std::vector::const_iterator cend() const { + return ranges_.cend(); + } + + // Need to provide begin()/end() since range-based loop expects begin()/end(). + std::vector::const_iterator begin() const { + return ranges_.cbegin(); + } + + std::vector::const_iterator end() const { + return ranges_.cend(); + } + + // Reverse const iterators for MoveRange(). + std::vector::const_reverse_iterator crbegin() const { + return ranges_.crbegin(); + } + + std::vector::const_reverse_iterator crend() const { + return ranges_.crend(); + } + + const Range& operator[](size_t i) const { + return ranges_[i]; + } + + bool operator==(const RangeSet& other) const { + // The orders of Range's matter. "4,1,5,8,10" != "4,8,10,1,5". + return (ranges_ == other.ranges_); + } + + bool operator!=(const RangeSet& other) const { + return ranges_ != other.ranges_; + } + + protected: + // Actual limit for each value and the total number are both INT_MAX. + std::vector ranges_; + size_t blocks_; +}; + +static constexpr size_t kBlockSize = 4096; + +// The class is a sorted version of a RangeSet; and it's useful in imgdiff to split the input +// files when we're handling large zip files. Specifically, we can treat the input file as a +// continuous RangeSet (i.e. RangeSet("0-99") for a 100 blocks file); and break it down into +// several smaller chunks based on the zip entries. + +// For example, [source: 0-99] can be split into +// [split_src1: 10-29]; [split_src2: 40-49, 60-69]; [split_src3: 70-89] +// Here "10-29" simply means block 10th to block 29th with respect to the original input file. +// Also, note that the split sources should be mutual exclusive, but they don't need to cover +// every block in the original source. +class SortedRangeSet : public RangeSet { + public: + SortedRangeSet() {} + + // Ranges in the the set should be mutually exclusive; and they're sorted by the start block. + explicit SortedRangeSet(std::vector&& pairs) : RangeSet(std::move(pairs)) { + std::sort(ranges_.begin(), ranges_.end()); + } + + void Insert(const Range& to_insert) { + SortedRangeSet rs({ to_insert }); + Insert(rs); + } + + // Insert the input SortedRangeSet; keep the ranges sorted and merge the overlap ranges. + void Insert(const SortedRangeSet& rs) { + if (rs.size() == 0) { + return; + } + // Merge and sort the two RangeSets. + std::vector temp = std::move(ranges_); + std::copy(rs.begin(), rs.end(), std::back_inserter(temp)); + std::sort(temp.begin(), temp.end()); + + Clear(); + // Trim overlaps and insert the result back to ranges_. + Range to_insert = temp.front(); + for (auto it = temp.cbegin() + 1; it != temp.cend(); it++) { + if (it->first <= to_insert.second) { + to_insert.second = std::max(to_insert.second, it->second); + } else { + ranges_.push_back(to_insert); + blocks_ += (to_insert.second - to_insert.first); + to_insert = *it; + } + } + ranges_.push_back(to_insert); + blocks_ += (to_insert.second - to_insert.first); + } + + void Clear() { + blocks_ = 0; + ranges_.clear(); + } + + using RangeSet::Overlaps; + bool Overlaps(size_t start, size_t len) const { + RangeSet rs({ { start / kBlockSize, (start + len - 1) / kBlockSize + 1 } }); + return Overlaps(rs); + } + + // Compute the block range the file occupies, and insert that range. + void Insert(size_t start, size_t len) { + Range to_insert{ start / kBlockSize, (start + len - 1) / kBlockSize + 1 }; + Insert(to_insert); + } + + // Given an offset of the file, checks if the corresponding block (by considering the file as + // 0-based continuous block ranges) is covered by the SortedRangeSet. If so, returns the offset + // within this SortedRangeSet. + // + // For example, the 4106-th byte of a file is from block 1, assuming a block size of 4096-byte. + // The mapped offset within a SortedRangeSet("1-9 15-19") is 10. + // + // An offset of 65546 falls into the 16-th block in a file. Block 16 is contained as the 10-th + // item in SortedRangeSet("1-9 15-19"). So its data can be found at offset 40970 (i.e. 4096 * 10 + // + 10) in a range represented by this SortedRangeSet. + size_t GetOffsetInRangeSet(size_t old_offset) const { + size_t old_block_start = old_offset / kBlockSize; + size_t new_block_start = 0; + for (const auto& range : ranges_) { + // Find the index of old_block_start. + if (old_block_start >= range.second) { + new_block_start += (range.second - range.first); + } else if (old_block_start >= range.first) { + new_block_start += (old_block_start - range.first); + return (new_block_start * kBlockSize + old_offset % kBlockSize); + } else { + CHECK(false) << "block_start " << old_block_start + << " is missing between two ranges: " << this->ToString(); + return 0; + } + } + CHECK(false) << "block_start " << old_block_start + << " exceeds the limit of current RangeSet: " << this->ToString(); + return 0; + } +}; \ No newline at end of file diff --git a/tests/unit/rangeset_test.cpp b/tests/unit/rangeset_test.cpp index 3993cb9ea..15bcec855 100644 --- a/tests/unit/rangeset_test.cpp +++ b/tests/unit/rangeset_test.cpp @@ -21,7 +21,7 @@ #include -#include "updater/rangeset.h" +#include "rangeset.h" TEST(RangeSetTest, Parse_smoke) { RangeSet rs = RangeSet::Parse("2,1,10"); diff --git a/updater/blockimg.cpp b/updater/blockimg.cpp index a0b9ad233..fe21dd0eb 100644 --- a/updater/blockimg.cpp +++ b/updater/blockimg.cpp @@ -53,8 +53,8 @@ #include "error_code.h" #include "ota_io.h" #include "print_sha1.h" +#include "rangeset.h" #include "updater/install.h" -#include "updater/rangeset.h" #include "updater/updater.h" // Set this to 0 to interpret 'erase' transfers to mean do a diff --git a/updater/include/updater/rangeset.h b/updater/include/updater/rangeset.h deleted file mode 100644 index b67c98724..000000000 --- a/updater/include/updater/rangeset.h +++ /dev/null @@ -1,278 +0,0 @@ -/* - * Copyright (C) 2017 The Android Open Source Project - * - * Licensed under the Apache License, Version 2.0 (the "License"); - * you may not use this file except in compliance with the License. - * You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -#pragma once - -#include - -#include -#include -#include - -#include -#include -#include -#include - -using Range = std::pair; - -class RangeSet { - public: - RangeSet() : blocks_(0) {} - - explicit RangeSet(std::vector&& pairs) { - CHECK_NE(pairs.size(), static_cast(0)) << "Invalid number of tokens"; - - // Sanity check the input. - size_t result = 0; - for (const auto& range : pairs) { - CHECK_LT(range.first, range.second) - << "Empty or negative range: " << range.first << ", " << range.second; - size_t sz = range.second - range.first; - CHECK_LE(result, SIZE_MAX - sz) << "RangeSet size overflow"; - result += sz; - } - - ranges_ = pairs; - blocks_ = result; - } - - static RangeSet Parse(const std::string& range_text) { - std::vector pieces = android::base::Split(range_text, ","); - CHECK_GE(pieces.size(), static_cast(3)) << "Invalid range text: " << range_text; - - size_t num; - CHECK(android::base::ParseUint(pieces[0], &num, static_cast(INT_MAX))) - << "Failed to parse the number of tokens: " << range_text; - - CHECK_NE(num, static_cast(0)) << "Invalid number of tokens: " << range_text; - CHECK_EQ(num % 2, static_cast(0)) << "Number of tokens must be even: " << range_text; - CHECK_EQ(num, pieces.size() - 1) << "Mismatching number of tokens: " << range_text; - - std::vector pairs; - for (size_t i = 0; i < num; i += 2) { - size_t first; - CHECK(android::base::ParseUint(pieces[i + 1], &first, static_cast(INT_MAX))); - size_t second; - CHECK(android::base::ParseUint(pieces[i + 2], &second, static_cast(INT_MAX))); - - pairs.emplace_back(first, second); - } - - return RangeSet(std::move(pairs)); - } - - std::string ToString() const { - if (ranges_.empty()) { - return ""; - } - std::string result = std::to_string(ranges_.size() * 2); - for (const auto& r : ranges_) { - result += android::base::StringPrintf(",%zu,%zu", r.first, r.second); - } - - return result; - } - - // Get the block number for the i-th (starting from 0) block in the RangeSet. - size_t GetBlockNumber(size_t idx) const { - CHECK_LT(idx, blocks_) << "Out of bound index " << idx << " (total blocks: " << blocks_ << ")"; - - for (const auto& range : ranges_) { - if (idx < range.second - range.first) { - return range.first + idx; - } - idx -= (range.second - range.first); - } - - CHECK(false) << "Failed to find block number for index " << idx; - return 0; // Unreachable, but to make compiler happy. - } - - // RangeSet has half-closed half-open bounds. For example, "3,5" contains blocks 3 and 4. So "3,5" - // and "5,7" are not overlapped. - bool Overlaps(const RangeSet& other) const { - for (const auto& range : ranges_) { - size_t start = range.first; - size_t end = range.second; - for (const auto& other_range : other.ranges_) { - size_t other_start = other_range.first; - size_t other_end = other_range.second; - // [start, end) vs [other_start, other_end) - if (!(other_start >= end || start >= other_end)) { - return true; - } - } - } - return false; - } - - // size() gives the number of Range's in this RangeSet. - size_t size() const { - return ranges_.size(); - } - - // blocks() gives the number of all blocks in this RangeSet. - size_t blocks() const { - return blocks_; - } - - // We provide const iterators only. - std::vector::const_iterator cbegin() const { - return ranges_.cbegin(); - } - - std::vector::const_iterator cend() const { - return ranges_.cend(); - } - - // Need to provide begin()/end() since range-based loop expects begin()/end(). - std::vector::const_iterator begin() const { - return ranges_.cbegin(); - } - - std::vector::const_iterator end() const { - return ranges_.cend(); - } - - // Reverse const iterators for MoveRange(). - std::vector::const_reverse_iterator crbegin() const { - return ranges_.crbegin(); - } - - std::vector::const_reverse_iterator crend() const { - return ranges_.crend(); - } - - const Range& operator[](size_t i) const { - return ranges_[i]; - } - - bool operator==(const RangeSet& other) const { - // The orders of Range's matter. "4,1,5,8,10" != "4,8,10,1,5". - return (ranges_ == other.ranges_); - } - - bool operator!=(const RangeSet& other) const { - return ranges_ != other.ranges_; - } - - protected: - // Actual limit for each value and the total number are both INT_MAX. - std::vector ranges_; - size_t blocks_; -}; - -static constexpr size_t kBlockSize = 4096; - -// The class is a sorted version of a RangeSet; and it's useful in imgdiff to split the input -// files when we're handling large zip files. Specifically, we can treat the input file as a -// continuous RangeSet (i.e. RangeSet("0-99") for a 100 blocks file); and break it down into -// several smaller chunks based on the zip entries. - -// For example, [source: 0-99] can be split into -// [split_src1: 10-29]; [split_src2: 40-49, 60-69]; [split_src3: 70-89] -// Here "10-29" simply means block 10th to block 29th with respect to the original input file. -// Also, note that the split sources should be mutual exclusive, but they don't need to cover -// every block in the original source. -class SortedRangeSet : public RangeSet { - public: - SortedRangeSet() {} - - // Ranges in the the set should be mutually exclusive; and they're sorted by the start block. - explicit SortedRangeSet(std::vector&& pairs) : RangeSet(std::move(pairs)) { - std::sort(ranges_.begin(), ranges_.end()); - } - - void Insert(const Range& to_insert) { - SortedRangeSet rs({ to_insert }); - Insert(rs); - } - - // Insert the input SortedRangeSet; keep the ranges sorted and merge the overlap ranges. - void Insert(const SortedRangeSet& rs) { - if (rs.size() == 0) { - return; - } - // Merge and sort the two RangeSets. - std::vector temp = std::move(ranges_); - std::copy(rs.begin(), rs.end(), std::back_inserter(temp)); - std::sort(temp.begin(), temp.end()); - - Clear(); - // Trim overlaps and insert the result back to ranges_. - Range to_insert = temp.front(); - for (auto it = temp.cbegin() + 1; it != temp.cend(); it++) { - if (it->first <= to_insert.second) { - to_insert.second = std::max(to_insert.second, it->second); - } else { - ranges_.push_back(to_insert); - blocks_ += (to_insert.second - to_insert.first); - to_insert = *it; - } - } - ranges_.push_back(to_insert); - blocks_ += (to_insert.second - to_insert.first); - } - - void Clear() { - blocks_ = 0; - ranges_.clear(); - } - - using RangeSet::Overlaps; - bool Overlaps(size_t start, size_t len) const { - RangeSet rs({ { start / kBlockSize, (start + len - 1) / kBlockSize + 1 } }); - return Overlaps(rs); - } - - // Compute the block range the file occupies, and insert that range. - void Insert(size_t start, size_t len) { - Range to_insert{ start / kBlockSize, (start + len - 1) / kBlockSize + 1 }; - Insert(to_insert); - } - - // Given an offset of the file, checks if the corresponding block (by considering the file as - // 0-based continuous block ranges) is covered by the SortedRangeSet. If so, returns the offset - // within this SortedRangeSet. - // - // For example, the 4106-th byte of a file is from block 1, assuming a block size of 4096-byte. - // The mapped offset within a SortedRangeSet("1-9 15-19") is 10. - // - // An offset of 65546 falls into the 16-th block in a file. Block 16 is contained as the 10-th - // item in SortedRangeSet("1-9 15-19"). So its data can be found at offset 40970 (i.e. 4096 * 10 - // + 10) in a range represented by this SortedRangeSet. - size_t GetOffsetInRangeSet(size_t old_offset) const { - size_t old_block_start = old_offset / kBlockSize; - size_t new_block_start = 0; - for (const auto& range : ranges_) { - // Find the index of old_block_start. - if (old_block_start >= range.second) { - new_block_start += (range.second - range.first); - } else if (old_block_start >= range.first) { - new_block_start += (old_block_start - range.first); - return (new_block_start * kBlockSize + old_offset % kBlockSize); - } else { - CHECK(false) <<"block_start " << old_block_start << " is missing between two ranges: " - << this->ToString(); - return 0; - } - } - CHECK(false) <<"block_start " << old_block_start << " exceeds the limit of current RangeSet: " - << this->ToString(); - return 0; - } -}; \ No newline at end of file -- cgit v1.2.3