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 <limits.h> 20 #include <stddef.h> 21 22 #include <algorithm> 23 #include <string> 24 #include <utility> 25 #include <vector> 26 27 #include <android-base/logging.h> 28 #include <android-base/parseint.h> 29 #include <android-base/stringprintf.h> 30 #include <android-base/strings.h> 31 32 RangeSet::RangeSet(std::vector<Range>&& pairs) { 33 blocks_ = 0; 34 if (pairs.empty()) { 35 LOG(ERROR) << "Invalid number of tokens"; 36 return; 37 } 38 39 for (const auto& range : pairs) { 40 if (!PushBack(range)) { 41 Clear(); 42 return; 43 } 44 } 45 } 46 47 RangeSet RangeSet::Parse(const std::string& range_text) { 48 std::vector<std::string> pieces = android::base::Split(range_text, ","); 49 if (pieces.size() < 3) { 50 LOG(ERROR) << "Invalid range text: " << range_text; 51 return {}; 52 } 53 54 size_t num; 55 if (!android::base::ParseUint(pieces[0], &num, static_cast<size_t>(INT_MAX))) { 56 LOG(ERROR) << "Failed to parse the number of tokens: " << range_text; 57 return {}; 58 } 59 if (num == 0) { 60 LOG(ERROR) << "Invalid number of tokens: " << range_text; 61 return {}; 62 } 63 if (num % 2 != 0) { 64 LOG(ERROR) << "Number of tokens must be even: " << range_text; 65 return {}; 66 } 67 if (num != pieces.size() - 1) { 68 LOG(ERROR) << "Mismatching number of tokens: " << range_text; 69 return {}; 70 } 71 72 std::vector<Range> pairs; 73 for (size_t i = 0; i < num; i += 2) { 74 size_t first; 75 size_t second; 76 if (!android::base::ParseUint(pieces[i + 1], &first, static_cast<size_t>(INT_MAX)) || 77 !android::base::ParseUint(pieces[i + 2], &second, static_cast<size_t>(INT_MAX))) { 78 return {}; 79 } 80 pairs.emplace_back(first, second); 81 } 82 return RangeSet(std::move(pairs)); 83 } 84 85 bool RangeSet::PushBack(Range range) { 86 if (range.first >= range.second) { 87 LOG(ERROR) << "Empty or negative range: " << range.first << ", " << range.second; 88 return false; 89 } 90 size_t sz = range.second - range.first; 91 if (blocks_ >= SIZE_MAX - sz) { 92 LOG(ERROR) << "RangeSet size overflow"; 93 return false; 94 } 95 96 ranges_.push_back(std::move(range)); 97 blocks_ += sz; 98 return true; 99 } 100 101 void RangeSet::Clear() { 102 ranges_.clear(); 103 blocks_ = 0; 104 } 105 106 std::vector<RangeSet> RangeSet::Split(size_t groups) const { 107 if (ranges_.empty() || groups == 0) return {}; 108 109 if (blocks_ < groups) { 110 groups = blocks_; 111 } 112 113 // Evenly distribute blocks, with the first few groups possibly containing one more. 114 size_t mean = blocks_ / groups; 115 std::vector<size_t> blocks_per_group(groups, mean); 116 std::fill_n(blocks_per_group.begin(), blocks_ % groups, mean + 1); 117 118 std::vector<RangeSet> result; 119 120 // Forward iterate Ranges and fill up each group with the desired number of blocks. 121 auto it = ranges_.cbegin(); 122 Range range = *it; 123 for (const auto& blocks : blocks_per_group) { 124 RangeSet buffer; 125 size_t needed = blocks; 126 while (needed > 0) { 127 size_t range_blocks = range.second - range.first; 128 if (range_blocks > needed) { 129 // Split the current range and don't advance the iterator. 130 buffer.PushBack({ range.first, range.first + needed }); 131 range.first = range.first + needed; 132 break; 133 } 134 buffer.PushBack(range); 135 it++; 136 if (it != ranges_.cend()) { 137 range = *it; 138 } 139 needed -= range_blocks; 140 } 141 result.push_back(std::move(buffer)); 142 } 143 return result; 144 } 145 146 std::string RangeSet::ToString() const { 147 if (ranges_.empty()) { 148 return ""; 149 } 150 std::string result = std::to_string(ranges_.size() * 2); 151 for (const auto& [begin, end] : ranges_) { 152 result += android::base::StringPrintf(",%zu,%zu", begin, end); 153 } 154 155 return result; 156 } 157 158 // Get the block number for the i-th (starting from 0) block in the RangeSet. 159 size_t RangeSet::GetBlockNumber(size_t idx) const { 160 CHECK_LT(idx, blocks_) << "Out of bound index " << idx << " (total blocks: " << blocks_ << ")"; 161 162 for (const auto& [begin, end] : ranges_) { 163 if (idx < end - begin) { 164 return begin + idx; 165 } 166 idx -= (end - begin); 167 } 168 169 CHECK(false) << "Failed to find block number for index " << idx; 170 return 0; // Unreachable, but to make compiler happy. 171 } 172 173 // RangeSet has half-closed half-open bounds. For example, "3,5" contains blocks 3 and 4. So "3,5" 174 // and "5,7" are not overlapped. 175 bool RangeSet::Overlaps(const RangeSet& other) const { 176 for (const auto& [begin, end] : ranges_) { 177 for (const auto& [other_begin, other_end] : other.ranges_) { 178 // [begin, end) vs [other_begin, other_end) 179 if (!(other_begin >= end || begin >= other_end)) { 180 return true; 181 } 182 } 183 } 184 return false; 185 } 186 187 // Ranges in the the set should be mutually exclusive; and they're sorted by the start block. 188 SortedRangeSet::SortedRangeSet(std::vector<Range>&& pairs) : RangeSet(std::move(pairs)) { 189 std::sort(ranges_.begin(), ranges_.end()); 190 } 191 192 void SortedRangeSet::Insert(const Range& to_insert) { 193 SortedRangeSet rs({ to_insert }); 194 Insert(rs); 195 } 196 197 // Insert the input SortedRangeSet; keep the ranges sorted and merge the overlap ranges. 198 void SortedRangeSet::Insert(const SortedRangeSet& rs) { 199 if (rs.size() == 0) { 200 return; 201 } 202 // Merge and sort the two RangeSets. 203 std::vector<Range> temp = std::move(ranges_); 204 std::copy(rs.begin(), rs.end(), std::back_inserter(temp)); 205 std::sort(temp.begin(), temp.end()); 206 207 Clear(); 208 // Trim overlaps and insert the result back to ranges_. 209 Range to_insert = temp.front(); 210 for (auto it = temp.cbegin() + 1; it != temp.cend(); it++) { 211 if (it->first <= to_insert.second) { 212 to_insert.second = std::max(to_insert.second, it->second); 213 } else { 214 ranges_.push_back(to_insert); 215 blocks_ += (to_insert.second - to_insert.first); 216 to_insert = *it; 217 } 218 } 219 ranges_.push_back(to_insert); 220 blocks_ += (to_insert.second - to_insert.first); 221 } 222 223 // Compute the block range the file occupies, and insert that range. 224 void SortedRangeSet::Insert(size_t start, size_t len) { 225 Range to_insert{ start / kBlockSize, (start + len - 1) / kBlockSize + 1 }; 226 Insert(to_insert); 227 } 228 229 bool SortedRangeSet::Overlaps(size_t start, size_t len) const { 230 RangeSet rs({ { start / kBlockSize, (start + len - 1) / kBlockSize + 1 } }); 231 return Overlaps(rs); 232 } 233 234 // Given an offset of the file, checks if the corresponding block (by considering the file as 235 // 0-based continuous block ranges) is covered by the SortedRangeSet. If so, returns the offset 236 // within this SortedRangeSet. 237 // 238 // For example, the 4106-th byte of a file is from block 1, assuming a block size of 4096-byte. 239 // The mapped offset within a SortedRangeSet("1-9 15-19") is 10. 240 // 241 // An offset of 65546 falls into the 16-th block in a file. Block 16 is contained as the 10-th 242 // item in SortedRangeSet("1-9 15-19"). So its data can be found at offset 40970 (i.e. 4096 * 10 243 // + 10) in a range represented by this SortedRangeSet. 244 size_t SortedRangeSet::GetOffsetInRangeSet(size_t old_offset) const { 245 size_t old_block_start = old_offset / kBlockSize; 246 size_t new_block_start = 0; 247 for (const auto& [start, end] : ranges_) { 248 // Find the index of old_block_start. 249 if (old_block_start >= end) { 250 new_block_start += (end - start); 251 } else if (old_block_start >= start) { 252 new_block_start += (old_block_start - start); 253 return (new_block_start * kBlockSize + old_offset % kBlockSize); 254 } else { 255 CHECK(false) << "block_start " << old_block_start 256 << " is missing between two ranges: " << ToString(); 257 return 0; 258 } 259 } 260 CHECK(false) << "block_start " << old_block_start 261 << " exceeds the limit of current RangeSet: " << ToString(); 262 return 0; 263 } 264
