OLD | NEW |
---|---|
1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "chrome/browser/safe_browsing/prefix_set.h" | 5 #include "chrome/browser/safe_browsing/prefix_set.h" |
6 | 6 |
7 #include <algorithm> | 7 #include <algorithm> |
8 #include <math.h> | 8 #include <math.h> |
9 | 9 |
10 #include "base/file_util.h" | 10 #include "base/file_util.h" |
(...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
47 index_.push_back(std::make_pair(prev_prefix, deltas_.size())); | 47 index_.push_back(std::make_pair(prev_prefix, deltas_.size())); |
48 | 48 |
49 for (size_t i = 1; i < sorted_prefixes.size(); ++i) { | 49 for (size_t i = 1; i < sorted_prefixes.size(); ++i) { |
50 // Skip duplicates. | 50 // Skip duplicates. |
51 if (sorted_prefixes[i] == prev_prefix) | 51 if (sorted_prefixes[i] == prev_prefix) |
52 continue; | 52 continue; |
53 | 53 |
54 // Calculate the delta. |unsigned| is mandatory, because the | 54 // Calculate the delta. |unsigned| is mandatory, because the |
55 // sorted_prefixes could be more than INT_MAX apart. | 55 // sorted_prefixes could be more than INT_MAX apart. |
56 DCHECK_GT(sorted_prefixes[i], prev_prefix); | 56 DCHECK_GT(sorted_prefixes[i], prev_prefix); |
57 unsigned delta = sorted_prefixes[i] - prev_prefix; | 57 const unsigned delta = sorted_prefixes[i] - prev_prefix; |
58 const uint16 delta16 = static_cast<uint16>(delta); | |
58 | 59 |
59 // New index ref if the delta is too wide, or if too many | 60 // New index ref if the delta doesn't fit, or if too many |
60 // consecutive deltas have been encoded. Note that | 61 // consecutive deltas have been encoded. |
61 // |kMaxDelta| cannot itself be encoded. | 62 if (delta != static_cast<unsigned>(delta16) || run_length >= kMaxRun) { |
lzheng
2011/03/18 00:37:34
I feel delta >= kMaxDelta is the same as delta !=
Scott Hess - ex-Googler
2011/03/18 02:04:59
Should be identical. It was one of the notions th
| |
62 if (delta >= kMaxDelta || run_length >= kMaxRun) { | |
63 index_.push_back(std::make_pair(sorted_prefixes[i], deltas_.size())); | 63 index_.push_back(std::make_pair(sorted_prefixes[i], deltas_.size())); |
64 run_length = 0; | 64 run_length = 0; |
65 } else { | 65 } else { |
66 // Continue the run of deltas. | 66 // Continue the run of deltas. |
67 deltas_.push_back(static_cast<uint16>(delta)); | 67 deltas_.push_back(delta16); |
68 DCHECK_EQ(static_cast<unsigned>(deltas_.back()), delta); | |
68 ++run_length; | 69 ++run_length; |
69 } | 70 } |
70 | 71 |
71 prev_prefix = sorted_prefixes[i]; | 72 prev_prefix = sorted_prefixes[i]; |
72 } | 73 } |
73 | 74 |
74 // Send up some memory-usage stats. Bits because fractional bytes | 75 // Send up some memory-usage stats. Bits because fractional bytes |
75 // are weird. | 76 // are weird. |
76 const size_t bits_used = index_.size() * sizeof(index_[0]) * CHAR_BIT + | 77 const size_t bits_used = index_.size() * sizeof(index_[0]) * CHAR_BIT + |
77 deltas_.size() * sizeof(deltas_[0]) * CHAR_BIT; | 78 deltas_.size() * sizeof(deltas_[0]) * CHAR_BIT; |
(...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
118 return true; | 119 return true; |
119 | 120 |
120 // Scan forward accumulating deltas while a match is possible. | 121 // Scan forward accumulating deltas while a match is possible. |
121 for (size_t di = iter->second; di < bound && current < prefix; ++di) { | 122 for (size_t di = iter->second; di < bound && current < prefix; ++di) { |
122 current += deltas_[di]; | 123 current += deltas_[di]; |
123 } | 124 } |
124 | 125 |
125 return current == prefix; | 126 return current == prefix; |
126 } | 127 } |
127 | 128 |
128 void PrefixSet::GetPrefixes(std::vector<SBPrefix>* prefixes) { | 129 void PrefixSet::GetPrefixes(std::vector<SBPrefix>* prefixes) const { |
129 for (size_t ii = 0; ii < index_.size(); ++ii) { | 130 for (size_t ii = 0; ii < index_.size(); ++ii) { |
130 // The deltas for this |index_| entry run to the next index entry, | 131 // The deltas for this |index_| entry run to the next index entry, |
131 // or the end of the deltas. | 132 // or the end of the deltas. |
132 const size_t deltas_end = | 133 const size_t deltas_end = |
133 (ii + 1 < index_.size()) ? index_[ii + 1].second : deltas_.size(); | 134 (ii + 1 < index_.size()) ? index_[ii + 1].second : deltas_.size(); |
134 | 135 |
135 SBPrefix current = index_[ii].first; | 136 SBPrefix current = index_[ii].first; |
136 prefixes->push_back(current); | 137 prefixes->push_back(current); |
137 for (size_t di = index_[ii].second; di < deltas_end; ++di) { | 138 for (size_t di = index_[ii].second; di < deltas_end; ++di) { |
138 current += deltas_[di]; | 139 current += deltas_[di]; |
(...skipping 119 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
258 if (written != 1) | 259 if (written != 1) |
259 return false; | 260 return false; |
260 | 261 |
261 // TODO(shess): Can this code check that the close was successful? | 262 // TODO(shess): Can this code check that the close was successful? |
262 file.reset(); | 263 file.reset(); |
263 | 264 |
264 return true; | 265 return true; |
265 } | 266 } |
266 | 267 |
267 } // namespace safe_browsing | 268 } // namespace safe_browsing |
OLD | NEW |