aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-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>