1 // Copyright (c) 2010 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 //
5 // Implementation of ChunkRange class.
6
7 #include <algorithm>
8
9 #include "chrome/browser/safe_browsing/chunk_range.h"
10
11 #include "base/logging.h"
12 #include "base/strings/string_number_conversions.h"
13 #include "base/strings/string_split.h"
14 #include "base/strings/string_util.h"
15
ChunkRange(int start)16 ChunkRange::ChunkRange(int start) : start_(start), stop_(start) {
17 }
18
ChunkRange(int start,int stop)19 ChunkRange::ChunkRange(int start, int stop) : start_(start), stop_(stop) {
20 }
21
ChunkRange(const ChunkRange & rhs)22 ChunkRange::ChunkRange(const ChunkRange& rhs)
23 : start_(rhs.start()), stop_(rhs.stop()) {
24 }
25
26 // Helper functions -----------------------------------------------------------
27
ChunksToRangeString(const std::vector<int> & chunks,std::string * result)28 void ChunksToRangeString(const std::vector<int>& chunks, std::string* result) {
29 // The following code requires the range to be sorted.
30 std::vector<int> sorted_chunks(chunks);
31 std::sort(sorted_chunks.begin(), sorted_chunks.end());
32
33 DCHECK(result);
34 result->clear();
35 std::vector<int>::const_iterator iter = sorted_chunks.begin();
36 while (iter != sorted_chunks.end()) {
37 const int range_begin = *iter;
38 int range_end = *iter;
39
40 // Extend the range forward across duplicates and increments.
41 for (; iter != sorted_chunks.end() && *iter <= range_end + 1; ++iter) {
42 range_end = *iter;
43 }
44
45 if (!result->empty())
46 result->append(",");
47 result->append(base::IntToString(range_begin));
48 if (range_end > range_begin) {
49 result->append("-");
50 result->append(base::IntToString(range_end));
51 }
52 }
53 }
54
RangesToChunks(const std::vector<ChunkRange> & ranges,std::vector<int> * chunks)55 void RangesToChunks(const std::vector<ChunkRange>& ranges,
56 std::vector<int>* chunks) {
57 DCHECK(chunks);
58 for (size_t i = 0; i < ranges.size(); ++i) {
59 const ChunkRange& range = ranges[i];
60 for (int chunk = range.start(); chunk <= range.stop(); ++chunk) {
61 chunks->push_back(chunk);
62 }
63 }
64 }
65
StringToRanges(const std::string & input,std::vector<ChunkRange> * ranges)66 bool StringToRanges(const std::string& input,
67 std::vector<ChunkRange>* ranges) {
68 DCHECK(ranges);
69
70 // Crack the string into chunk parts, then crack each part looking for a
71 // range.
72 std::vector<std::string> chunk_parts;
73 base::SplitString(input, ',', &chunk_parts);
74
75 for (size_t i = 0; i < chunk_parts.size(); ++i) {
76 std::vector<std::string> chunk_ranges;
77 base::SplitString(chunk_parts[i], '-', &chunk_ranges);
78 int start = atoi(chunk_ranges[0].c_str());
79 int stop = start;
80 if (chunk_ranges.size() == 2)
81 stop = atoi(chunk_ranges[1].c_str());
82 if (start == 0 || stop == 0) {
83 // atoi error, since chunk numbers are guaranteed to never be 0.
84 ranges->clear();
85 return false;
86 }
87 ranges->push_back(ChunkRange(start, stop));
88 }
89
90 return true;
91 }
92
93 // Binary search over a series of ChunkRanges.
IsChunkInRange(int chunk_number,const std::vector<ChunkRange> & ranges)94 bool IsChunkInRange(int chunk_number, const std::vector<ChunkRange>& ranges) {
95 if (ranges.empty())
96 return false;
97
98 int low = 0;
99 int high = ranges.size() - 1;
100
101 while (low <= high) {
102 // http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
103 int mid = ((unsigned int)low + (unsigned int)high) >> 1;
104 const ChunkRange& chunk = ranges[mid];
105 if ((chunk.stop() >= chunk_number) && (chunk.start() <= chunk_number))
106 return true; // chunk_number is in range.
107
108 // Adjust our mid point.
109 if (chunk.stop() < chunk_number)
110 low = mid + 1;
111 else
112 high = mid - 1;
113 }
114
115 return false;
116 }
117