aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTao Bao2017-10-13 16:54:12 -0500
committerTao Bao2017-10-16 13:28:18 -0500
commit45685820029fb191fe8509418df91a049227ea3a (patch)
tree4507a0c3c6de9d6106d3521e3aba46fb0b72c083
parentb4a8c6abd9a434c3494162b197cf4278179f4f68 (diff)
downloadplatform-bootable-recovery-45685820029fb191fe8509418df91a049227ea3a.tar.gz
platform-bootable-recovery-45685820029fb191fe8509418df91a049227ea3a.tar.xz
platform-bootable-recovery-45685820029fb191fe8509418df91a049227ea3a.zip
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
-rw-r--r--applypatch/Android.bp1
-rw-r--r--applypatch/imgdiff.cpp2
-rw-r--r--otautil/Android.bp1
-rw-r--r--otautil/include/otautil/rangeset.h166
-rw-r--r--otautil/rangeset.cpp200
-rw-r--r--tests/component/imgdiff_test.cpp1
6 files changed, 220 insertions, 151 deletions
diff --git a/applypatch/Android.bp b/applypatch/Android.bp
index db307df2..922f67ab 100644
--- a/applypatch/Android.bp
+++ b/applypatch/Android.bp
@@ -150,6 +150,7 @@ cc_binary_host {
150 150
151 static_libs: [ 151 static_libs: [
152 "libimgdiff", 152 "libimgdiff",
153 "libotautil",
153 "libbsdiff", 154 "libbsdiff",
154 "libdivsufsort", 155 "libdivsufsort",
155 "libdivsufsort64", 156 "libdivsufsort64",
diff --git a/applypatch/imgdiff.cpp b/applypatch/imgdiff.cpp
index 3a61a7d0..69ad75f3 100644
--- a/applypatch/imgdiff.cpp
+++ b/applypatch/imgdiff.cpp
@@ -160,6 +160,8 @@
160#include <android-base/logging.h> 160#include <android-base/logging.h>
161#include <android-base/memory.h> 161#include <android-base/memory.h>
162#include <android-base/parseint.h> 162#include <android-base/parseint.h>
163#include <android-base/stringprintf.h>
164#include <android-base/strings.h>
163#include <android-base/unique_fd.h> 165#include <android-base/unique_fd.h>
164#include <bsdiff.h> 166#include <bsdiff.h>
165#include <ziparchive/zip_archive.h> 167#include <ziparchive/zip_archive.h>
diff --git a/otautil/Android.bp b/otautil/Android.bp
index 659fefad..5efb12d6 100644
--- a/otautil/Android.bp
+++ b/otautil/Android.bp
@@ -21,6 +21,7 @@ cc_library_static {
21 "SysUtil.cpp", 21 "SysUtil.cpp",
22 "DirUtil.cpp", 22 "DirUtil.cpp",
23 "ThermalUtil.cpp", 23 "ThermalUtil.cpp",
24 "rangeset.cpp",
24 ], 25 ],
25 26
26 static_libs: [ 27 static_libs: [
diff --git a/otautil/include/otautil/rangeset.h b/otautil/include/otautil/rangeset.h
index f224a08b..c4234d18 100644
--- a/otautil/include/otautil/rangeset.h
+++ b/otautil/include/otautil/rangeset.h
@@ -22,103 +22,24 @@
22#include <utility> 22#include <utility>
23#include <vector> 23#include <vector>
24 24
25#include <android-base/logging.h>
26#include <android-base/parseint.h>
27#include <android-base/stringprintf.h>
28#include <android-base/strings.h>
29
30using Range = std::pair<size_t, size_t>; 25using Range = std::pair<size_t, size_t>;
31 26
32class RangeSet { 27class RangeSet {
33 public: 28 public:
34 RangeSet() : blocks_(0) {} 29 RangeSet() : blocks_(0) {}
35 30
36 explicit RangeSet(std::vector<Range>&& pairs) { 31 explicit RangeSet(std::vector<Range>&& pairs);
37 CHECK_NE(pairs.size(), static_cast<size_t>(0)) << "Invalid number of tokens";
38
39 // Sanity check the input.
40 size_t result = 0;
41 for (const auto& range : pairs) {
42 CHECK_LT(range.first, range.second)
43 << "Empty or negative range: " << range.first << ", " << range.second;
44 size_t sz = range.second - range.first;
45 CHECK_LE(result, SIZE_MAX - sz) << "RangeSet size overflow";
46 result += sz;
47 }
48
49 ranges_ = pairs;
50 blocks_ = result;
51 }
52
53 static RangeSet Parse(const std::string& range_text) {
54 std::vector<std::string> pieces = android::base::Split(range_text, ",");
55 CHECK_GE(pieces.size(), static_cast<size_t>(3)) << "Invalid range text: " << range_text;
56
57 size_t num;
58 CHECK(android::base::ParseUint(pieces[0], &num, static_cast<size_t>(INT_MAX)))
59 << "Failed to parse the number of tokens: " << range_text;
60
61 CHECK_NE(num, static_cast<size_t>(0)) << "Invalid number of tokens: " << range_text;
62 CHECK_EQ(num % 2, static_cast<size_t>(0)) << "Number of tokens must be even: " << range_text;
63 CHECK_EQ(num, pieces.size() - 1) << "Mismatching number of tokens: " << range_text;
64
65 std::vector<Range> pairs;
66 for (size_t i = 0; i < num; i += 2) {
67 size_t first;
68 CHECK(android::base::ParseUint(pieces[i + 1], &first, static_cast<size_t>(INT_MAX)));
69 size_t second;
70 CHECK(android::base::ParseUint(pieces[i + 2], &second, static_cast<size_t>(INT_MAX)));
71 32
72 pairs.emplace_back(first, second); 33 static RangeSet Parse(const std::string& range_text);
73 }
74 34
75 return RangeSet(std::move(pairs)); 35 std::string ToString() const;
76 }
77
78 std::string ToString() const {
79 if (ranges_.empty()) {
80 return "";
81 }
82 std::string result = std::to_string(ranges_.size() * 2);
83 for (const auto& r : ranges_) {
84 result += android::base::StringPrintf(",%zu,%zu", r.first, r.second);
85 }
86
87 return result;
88 }
89 36
90 // Get the block number for the i-th (starting from 0) block in the RangeSet. 37 // Get the block number for the i-th (starting from 0) block in the RangeSet.
91 size_t GetBlockNumber(size_t idx) const { 38 size_t GetBlockNumber(size_t idx) const;
92 CHECK_LT(idx, blocks_) << "Out of bound index " << idx << " (total blocks: " << blocks_ << ")";
93
94 for (const auto& range : ranges_) {
95 if (idx < range.second - range.first) {
96 return range.first + idx;
97 }
98 idx -= (range.second - range.first);
99 }
100
101 CHECK(false) << "Failed to find block number for index " << idx;
102 return 0; // Unreachable, but to make compiler happy.
103 }
104 39
105 // RangeSet has half-closed half-open bounds. For example, "3,5" contains blocks 3 and 4. So "3,5" 40 // RangeSet has half-closed half-open bounds. For example, "3,5" contains blocks 3 and 4. So "3,5"
106 // and "5,7" are not overlapped. 41 // and "5,7" are not overlapped.
107 bool Overlaps(const RangeSet& other) const { 42 bool Overlaps(const RangeSet& other) const;
108 for (const auto& range : ranges_) {
109 size_t start = range.first;
110 size_t end = range.second;
111 for (const auto& other_range : other.ranges_) {
112 size_t other_start = other_range.first;
113 size_t other_end = other_range.second;
114 // [start, end) vs [other_start, other_end)
115 if (!(other_start >= end || start >= other_end)) {
116 return true;
117 }
118 }
119 }
120 return false;
121 }
122 43
123 // size() gives the number of Range's in this RangeSet. 44 // size() gives the number of Range's in this RangeSet.
124 size_t size() const { 45 size_t size() const {
@@ -176,8 +97,6 @@ class RangeSet {
176 size_t blocks_; 97 size_t blocks_;
177}; 98};
178 99
179static constexpr size_t kBlockSize = 4096;
180
181// The class is a sorted version of a RangeSet; and it's useful in imgdiff to split the input 100// The class is a sorted version of a RangeSet; and it's useful in imgdiff to split the input
182// files when we're handling large zip files. Specifically, we can treat the input file as a 101// files when we're handling large zip files. Specifically, we can treat the input file as a
183// continuous RangeSet (i.e. RangeSet("0-99") for a 100 blocks file); and break it down into 102// 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 {
193 SortedRangeSet() {} 112 SortedRangeSet() {}
194 113
195 // Ranges in the the set should be mutually exclusive; and they're sorted by the start block. 114 // Ranges in the the set should be mutually exclusive; and they're sorted by the start block.
196 explicit SortedRangeSet(std::vector<Range>&& pairs) : RangeSet(std::move(pairs)) { 115 explicit SortedRangeSet(std::vector<Range>&& pairs);
197 std::sort(ranges_.begin(), ranges_.end());
198 }
199 116
200 void Insert(const Range& to_insert) { 117 void Insert(const Range& to_insert);
201 SortedRangeSet rs({ to_insert });
202 Insert(rs);
203 }
204 118
205 // Insert the input SortedRangeSet; keep the ranges sorted and merge the overlap ranges. 119 // Insert the input SortedRangeSet; keep the ranges sorted and merge the overlap ranges.
206 void Insert(const SortedRangeSet& rs) { 120 void Insert(const SortedRangeSet& rs);
207 if (rs.size() == 0) {
208 return;
209 }
210 // Merge and sort the two RangeSets.
211 std::vector<Range> temp = std::move(ranges_);
212 std::copy(rs.begin(), rs.end(), std::back_inserter(temp));
213 std::sort(temp.begin(), temp.end());
214
215 Clear();
216 // Trim overlaps and insert the result back to ranges_.
217 Range to_insert = temp.front();
218 for (auto it = temp.cbegin() + 1; it != temp.cend(); it++) {
219 if (it->first <= to_insert.second) {
220 to_insert.second = std::max(to_insert.second, it->second);
221 } else {
222 ranges_.push_back(to_insert);
223 blocks_ += (to_insert.second - to_insert.first);
224 to_insert = *it;
225 }
226 }
227 ranges_.push_back(to_insert);
228 blocks_ += (to_insert.second - to_insert.first);
229 }
230 121
231 void Clear() { 122 // Compute the block range the file occupies, and insert that range.
232 blocks_ = 0; 123 void Insert(size_t start, size_t len);
233 ranges_.clear(); 124
234 } 125 void Clear();
235 126
236 using RangeSet::Overlaps; 127 using RangeSet::Overlaps;
237 bool Overlaps(size_t start, size_t len) const {
238 RangeSet rs({ { start / kBlockSize, (start + len - 1) / kBlockSize + 1 } });
239 return Overlaps(rs);
240 }
241 128
242 // Compute the block range the file occupies, and insert that range. 129 bool Overlaps(size_t start, size_t len) const;
243 void Insert(size_t start, size_t len) {
244 Range to_insert{ start / kBlockSize, (start + len - 1) / kBlockSize + 1 };
245 Insert(to_insert);
246 }
247 130
248 // Given an offset of the file, checks if the corresponding block (by considering the file as 131 // Given an offset of the file, checks if the corresponding block (by considering the file as
249 // 0-based continuous block ranges) is covered by the SortedRangeSet. If so, returns the offset 132 // 0-based continuous block ranges) is covered by the SortedRangeSet. If so, returns the offset
@@ -255,24 +138,5 @@ class SortedRangeSet : public RangeSet {
255 // An offset of 65546 falls into the 16-th block in a file. Block 16 is contained as the 10-th 138 // An offset of 65546 falls into the 16-th block in a file. Block 16 is contained as the 10-th
256 // item in SortedRangeSet("1-9 15-19"). So its data can be found at offset 40970 (i.e. 4096 * 10 139 // item in SortedRangeSet("1-9 15-19"). So its data can be found at offset 40970 (i.e. 4096 * 10
257 // + 10) in a range represented by this SortedRangeSet. 140 // + 10) in a range represented by this SortedRangeSet.
258 size_t GetOffsetInRangeSet(size_t old_offset) const { 141 size_t GetOffsetInRangeSet(size_t old_offset) const;
259 size_t old_block_start = old_offset / kBlockSize; 142};
260 size_t new_block_start = 0;
261 for (const auto& range : ranges_) {
262 // Find the index of old_block_start.
263 if (old_block_start >= range.second) {
264 new_block_start += (range.second - range.first);
265 } else if (old_block_start >= range.first) {
266 new_block_start += (old_block_start - range.first);
267 return (new_block_start * kBlockSize + old_offset % kBlockSize);
268 } else {
269 CHECK(false) << "block_start " << old_block_start
270 << " is missing between two ranges: " << this->ToString();
271 return 0;
272 }
273 }
274 CHECK(false) << "block_start " << old_block_start
275 << " exceeds the limit of current RangeSet: " << this->ToString();
276 return 0;
277 }
278}; \ No newline at end of file
diff --git a/otautil/rangeset.cpp b/otautil/rangeset.cpp
new file mode 100644
index 00000000..a121a4ef
--- /dev/null
+++ b/otautil/rangeset.cpp
@@ -0,0 +1,200 @@
1/*
2 * Copyright (C) 2017 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#include "otautil/rangeset.h"
18
19#include <stddef.h>
20
21#include <string>
22#include <utility>
23#include <vector>
24
25#include <android-base/logging.h>
26#include <android-base/parseint.h>
27#include <android-base/stringprintf.h>
28#include <android-base/strings.h>
29
30RangeSet::RangeSet(std::vector<Range>&& pairs) {
31 CHECK_NE(pairs.size(), static_cast<size_t>(0)) << "Invalid number of tokens";
32
33 // Sanity check the input.
34 size_t result = 0;
35 for (const auto& range : pairs) {
36 CHECK_LT(range.first, range.second) << "Empty or negative range: " << range.first << ", "
37 << range.second;
38 size_t sz = range.second - range.first;
39 CHECK_LE(result, SIZE_MAX - sz) << "RangeSet size overflow";
40 result += sz;
41 }
42
43 ranges_ = pairs;
44 blocks_ = result;
45}
46
47RangeSet RangeSet::Parse(const std::string& range_text) {
48 std::vector<std::string> pieces = android::base::Split(range_text, ",");
49 CHECK_GE(pieces.size(), static_cast<size_t>(3)) << "Invalid range text: " << range_text;
50
51 size_t num;
52 CHECK(android::base::ParseUint(pieces[0], &num, static_cast<size_t>(INT_MAX)))
53 << "Failed to parse the number of tokens: " << range_text;
54
55 CHECK_NE(num, static_cast<size_t>(0)) << "Invalid number of tokens: " << range_text;
56 CHECK_EQ(num % 2, static_cast<size_t>(0)) << "Number of tokens must be even: " << range_text;
57 CHECK_EQ(num, pieces.size() - 1) << "Mismatching number of tokens: " << range_text;
58
59 std::vector<Range> pairs;
60 for (size_t i = 0; i < num; i += 2) {
61 size_t first;
62 CHECK(android::base::ParseUint(pieces[i + 1], &first, static_cast<size_t>(INT_MAX)));
63 size_t second;
64 CHECK(android::base::ParseUint(pieces[i + 2], &second, static_cast<size_t>(INT_MAX)));
65
66 pairs.emplace_back(first, second);
67 }
68
69 return RangeSet(std::move(pairs));
70}
71
72std::string RangeSet::ToString() const {
73 if (ranges_.empty()) {
74 return "";
75 }
76 std::string result = std::to_string(ranges_.size() * 2);
77 for (const auto& r : ranges_) {
78 result += android::base::StringPrintf(",%zu,%zu", r.first, r.second);
79 }
80
81 return result;
82}
83
84// Get the block number for the i-th (starting from 0) block in the RangeSet.
85size_t RangeSet::GetBlockNumber(size_t idx) const {
86 CHECK_LT(idx, blocks_) << "Out of bound index " << idx << " (total blocks: " << blocks_ << ")";
87
88 for (const auto& range : ranges_) {
89 if (idx < range.second - range.first) {
90 return range.first + idx;
91 }
92 idx -= (range.second - range.first);
93 }
94
95 CHECK(false) << "Failed to find block number for index " << idx;
96 return 0; // Unreachable, but to make compiler happy.
97}
98
99// RangeSet has half-closed half-open bounds. For example, "3,5" contains blocks 3 and 4. So "3,5"
100// and "5,7" are not overlapped.
101bool RangeSet::Overlaps(const RangeSet& other) const {
102 for (const auto& range : ranges_) {
103 size_t start = range.first;
104 size_t end = range.second;
105 for (const auto& other_range : other.ranges_) {
106 size_t other_start = other_range.first;
107 size_t other_end = other_range.second;
108 // [start, end) vs [other_start, other_end)
109 if (!(other_start >= end || start >= other_end)) {
110 return true;
111 }
112 }
113 }
114 return false;
115}
116
117static constexpr size_t kBlockSize = 4096;
118
119// Ranges in the the set should be mutually exclusive; and they're sorted by the start block.
120SortedRangeSet::SortedRangeSet(std::vector<Range>&& pairs) : RangeSet(std::move(pairs)) {
121 std::sort(ranges_.begin(), ranges_.end());
122}
123
124void SortedRangeSet::Insert(const Range& to_insert) {
125 SortedRangeSet rs({ to_insert });
126 Insert(rs);
127}
128
129// Insert the input SortedRangeSet; keep the ranges sorted and merge the overlap ranges.
130void SortedRangeSet::Insert(const SortedRangeSet& rs) {
131 if (rs.size() == 0) {
132 return;
133 }
134 // Merge and sort the two RangeSets.
135 std::vector<Range> temp = std::move(ranges_);
136 std::copy(rs.begin(), rs.end(), std::back_inserter(temp));
137 std::sort(temp.begin(), temp.end());
138
139 Clear();
140 // Trim overlaps and insert the result back to ranges_.
141 Range to_insert = temp.front();
142 for (auto it = temp.cbegin() + 1; it != temp.cend(); it++) {
143 if (it->first <= to_insert.second) {
144 to_insert.second = std::max(to_insert.second, it->second);
145 } else {
146 ranges_.push_back(to_insert);
147 blocks_ += (to_insert.second - to_insert.first);
148 to_insert = *it;
149 }
150 }
151 ranges_.push_back(to_insert);
152 blocks_ += (to_insert.second - to_insert.first);
153}
154
155// Compute the block range the file occupies, and insert that range.
156void SortedRangeSet::Insert(size_t start, size_t len) {
157 Range to_insert{ start / kBlockSize, (start + len - 1) / kBlockSize + 1 };
158 Insert(to_insert);
159}
160
161void SortedRangeSet::Clear() {
162 blocks_ = 0;
163 ranges_.clear();
164}
165
166bool SortedRangeSet::Overlaps(size_t start, size_t len) const {
167 RangeSet rs({ { start / kBlockSize, (start + len - 1) / kBlockSize + 1 } });
168 return Overlaps(rs);
169}
170
171// Given an offset of the file, checks if the corresponding block (by considering the file as
172// 0-based continuous block ranges) is covered by the SortedRangeSet. If so, returns the offset
173// within this SortedRangeSet.
174//
175// For example, the 4106-th byte of a file is from block 1, assuming a block size of 4096-byte.
176// The mapped offset within a SortedRangeSet("1-9 15-19") is 10.
177//
178// An offset of 65546 falls into the 16-th block in a file. Block 16 is contained as the 10-th
179// item in SortedRangeSet("1-9 15-19"). So its data can be found at offset 40970 (i.e. 4096 * 10
180// + 10) in a range represented by this SortedRangeSet.
181size_t SortedRangeSet::GetOffsetInRangeSet(size_t old_offset) const {
182 size_t old_block_start = old_offset / kBlockSize;
183 size_t new_block_start = 0;
184 for (const auto& range : ranges_) {
185 // Find the index of old_block_start.
186 if (old_block_start >= range.second) {
187 new_block_start += (range.second - range.first);
188 } else if (old_block_start >= range.first) {
189 new_block_start += (old_block_start - range.first);
190 return (new_block_start * kBlockSize + old_offset % kBlockSize);
191 } else {
192 CHECK(false) << "block_start " << old_block_start
193 << " is missing between two ranges: " << this->ToString();
194 return 0;
195 }
196 }
197 CHECK(false) << "block_start " << old_block_start
198 << " exceeds the limit of current RangeSet: " << this->ToString();
199 return 0;
200}
diff --git a/tests/component/imgdiff_test.cpp b/tests/component/imgdiff_test.cpp
index 161d58d4..bf591dae 100644
--- a/tests/component/imgdiff_test.cpp
+++ b/tests/component/imgdiff_test.cpp
@@ -24,6 +24,7 @@
24#include <android-base/file.h> 24#include <android-base/file.h>
25#include <android-base/memory.h> 25#include <android-base/memory.h>
26#include <android-base/stringprintf.h> 26#include <android-base/stringprintf.h>
27#include <android-base/strings.h>
27#include <android-base/test_utils.h> 28#include <android-base/test_utils.h>
28#include <applypatch/imgdiff.h> 29#include <applypatch/imgdiff.h>
29#include <applypatch/imgdiff_image.h> 30#include <applypatch/imgdiff_image.h>