From 45685820029fb191fe8509418df91a049227ea3a Mon Sep 17 00:00:00 2001 From: Tao Bao Date: Fri, 13 Oct 2017 14:54:12 -0700 Subject: otautil: Move RangeSet implementation into rangeset.cpp. Since it has grown much larger, users of the header shouldn't compile and carry their full copies. Also add missing header includes in imgdiff.cpp and imgdiff_test.cpp. Test: mmma bootable/recovery Test: recovery_unit_test; recovery_component_test; recovery_host_test Change-Id: I88ca54171765e5606ab0d61580fbc1ada578fd7d --- applypatch/Android.bp | 1 + applypatch/imgdiff.cpp | 2 + otautil/Android.bp | 1 + otautil/include/otautil/rangeset.h | 166 +++--------------------------- otautil/rangeset.cpp | 200 +++++++++++++++++++++++++++++++++++++ tests/component/imgdiff_test.cpp | 1 + 6 files changed, 220 insertions(+), 151 deletions(-) create mode 100644 otautil/rangeset.cpp diff --git a/applypatch/Android.bp b/applypatch/Android.bp index db307df28..922f67abf 100644 --- a/applypatch/Android.bp +++ b/applypatch/Android.bp @@ -150,6 +150,7 @@ cc_binary_host { static_libs: [ "libimgdiff", + "libotautil", "libbsdiff", "libdivsufsort", "libdivsufsort64", diff --git a/applypatch/imgdiff.cpp b/applypatch/imgdiff.cpp index 3a61a7d0d..69ad75f37 100644 --- a/applypatch/imgdiff.cpp +++ b/applypatch/imgdiff.cpp @@ -160,6 +160,8 @@ #include #include #include +#include +#include #include #include #include diff --git a/otautil/Android.bp b/otautil/Android.bp index 659fefada..5efb12d60 100644 --- a/otautil/Android.bp +++ b/otautil/Android.bp @@ -21,6 +21,7 @@ cc_library_static { "SysUtil.cpp", "DirUtil.cpp", "ThermalUtil.cpp", + "rangeset.cpp", ], static_libs: [ diff --git a/otautil/include/otautil/rangeset.h b/otautil/include/otautil/rangeset.h index f224a08be..c4234d181 100644 --- a/otautil/include/otautil/rangeset.h +++ b/otautil/include/otautil/rangeset.h @@ -22,103 +22,24 @@ #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))); + explicit RangeSet(std::vector&& pairs); - pairs.emplace_back(first, second); - } + static RangeSet Parse(const std::string& range_text); - 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; - } + std::string ToString() const; // 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. - } + size_t GetBlockNumber(size_t idx) const; // 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; - } + bool Overlaps(const RangeSet& other) const; // size() gives the number of Range's in this RangeSet. size_t size() const { @@ -176,8 +97,6 @@ class RangeSet { 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 @@ -193,57 +112,21 @@ class SortedRangeSet : public RangeSet { 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()); - } + explicit SortedRangeSet(std::vector&& pairs); - void Insert(const Range& to_insert) { - SortedRangeSet rs({ to_insert }); - Insert(rs); - } + void Insert(const Range& to_insert); // 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 Insert(const SortedRangeSet& rs); - void Clear() { - blocks_ = 0; - ranges_.clear(); - } + // Compute the block range the file occupies, and insert that range. + void Insert(size_t start, size_t len); + + void 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); - } + bool Overlaps(size_t start, size_t len) const; // 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 @@ -255,24 +138,5 @@ class SortedRangeSet : public RangeSet { // 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 + size_t GetOffsetInRangeSet(size_t old_offset) const; +}; diff --git a/otautil/rangeset.cpp b/otautil/rangeset.cpp new file mode 100644 index 000000000..a121a4efc --- /dev/null +++ b/otautil/rangeset.cpp @@ -0,0 +1,200 @@ +/* + * 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. + */ + +#include "otautil/rangeset.h" + +#include + +#include +#include +#include + +#include +#include +#include +#include + +RangeSet::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; +} + +RangeSet 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 RangeSet::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 RangeSet::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 RangeSet::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; +} + +static constexpr size_t kBlockSize = 4096; + +// Ranges in the the set should be mutually exclusive; and they're sorted by the start block. +SortedRangeSet::SortedRangeSet(std::vector&& pairs) : RangeSet(std::move(pairs)) { + std::sort(ranges_.begin(), ranges_.end()); +} + +void SortedRangeSet::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 SortedRangeSet::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); +} + +// Compute the block range the file occupies, and insert that range. +void SortedRangeSet::Insert(size_t start, size_t len) { + Range to_insert{ start / kBlockSize, (start + len - 1) / kBlockSize + 1 }; + Insert(to_insert); +} + +void SortedRangeSet::Clear() { + blocks_ = 0; + ranges_.clear(); +} + +bool SortedRangeSet::Overlaps(size_t start, size_t len) const { + RangeSet rs({ { start / kBlockSize, (start + len - 1) / kBlockSize + 1 } }); + return Overlaps(rs); +} + +// 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 SortedRangeSet::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; +} diff --git a/tests/component/imgdiff_test.cpp b/tests/component/imgdiff_test.cpp index 161d58d45..bf591dae4 100644 --- a/tests/component/imgdiff_test.cpp +++ b/tests/component/imgdiff_test.cpp @@ -24,6 +24,7 @@ #include #include #include +#include #include #include #include -- cgit v1.2.3