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/logging.h" | 10 #include "base/logging.h" |
11 #include "base/metrics/histogram.h" | 11 #include "base/metrics/histogram.h" |
12 | 12 |
13 namespace { | 13 namespace { |
14 | 14 |
15 // For |std::upper_bound()| to find a prefix w/in a vector of pairs. | 15 // For |std::upper_bound()| to find a prefix w/in a vector of pairs. |
16 bool PrefixLess(const std::pair<SBPrefix,size_t>& a, | 16 bool PrefixLess(const std::pair<SBPrefix,size_t>& a, |
17 const std::pair<SBPrefix,size_t>& b) { | 17 const std::pair<SBPrefix,size_t>& b) { |
18 return a.first < b.first; | 18 return a.first < b.first; |
19 } | 19 } |
20 | 20 |
21 } // namespace | 21 } // namespace |
22 | 22 |
23 namespace safe_browsing { | 23 namespace safe_browsing { |
24 | 24 |
25 PrefixSet::PrefixSet(const std::vector<SBPrefix>& prefixes) { | 25 PrefixSet::PrefixSet(const std::vector<SBPrefix>& sorted_prefixes) { |
26 if (prefixes.size()) { | 26 if (sorted_prefixes.size()) { |
27 std::vector<SBPrefix> sorted(prefixes.begin(), prefixes.end()); | |
28 std::sort(sorted.begin(), sorted.end()); | |
29 | |
30 // Lead with the first prefix. | 27 // Lead with the first prefix. |
31 SBPrefix prev_prefix = sorted[0]; | 28 SBPrefix prev_prefix = sorted_prefixes[0]; |
32 size_t run_length = 0; | 29 size_t run_length = 0; |
33 index_.push_back(std::make_pair(prev_prefix, deltas_.size())); | 30 index_.push_back(std::make_pair(prev_prefix, deltas_.size())); |
34 | 31 |
35 for (size_t i = 1; i < sorted.size(); ++i) { | 32 for (size_t i = 1; i < sorted_prefixes.size(); ++i) { |
36 // Don't encode zero deltas. | 33 // Skip duplicates. |
37 if (sorted[i] == prev_prefix) | 34 if (sorted_prefixes[i] == prev_prefix) |
38 continue; | 35 continue; |
39 | 36 |
40 // Calculate the delta. |unsigned| is mandatory, because the | 37 // Calculate the delta. |unsigned| is mandatory, because the |
41 // prefixes could be more than INT_MAX apart. | 38 // sorted_prefixes could be more than INT_MAX apart. |
42 unsigned delta = sorted[i] - prev_prefix; | 39 DCHECK_GT(sorted_prefixes[i], prev_prefix); |
| 40 unsigned delta = sorted_prefixes[i] - prev_prefix; |
43 | 41 |
44 // New index ref if the delta is too wide, or if too many | 42 // New index ref if the delta is too wide, or if too many |
45 // consecutive deltas have been encoded. Note that | 43 // consecutive deltas have been encoded. Note that |
46 // |kMaxDelta| cannot itself be encoded. | 44 // |kMaxDelta| cannot itself be encoded. |
47 if (delta >= kMaxDelta || run_length >= kMaxRun) { | 45 if (delta >= kMaxDelta || run_length >= kMaxRun) { |
48 index_.push_back(std::make_pair(sorted[i], deltas_.size())); | 46 index_.push_back(std::make_pair(sorted_prefixes[i], deltas_.size())); |
49 run_length = 0; | 47 run_length = 0; |
50 } else { | 48 } else { |
51 // Continue the run of deltas. | 49 // Continue the run of deltas. |
52 deltas_.push_back(static_cast<uint16>(delta)); | 50 deltas_.push_back(static_cast<uint16>(delta)); |
53 ++run_length; | 51 ++run_length; |
54 } | 52 } |
55 | 53 |
56 prev_prefix = sorted[i]; | 54 prev_prefix = sorted_prefixes[i]; |
57 } | 55 } |
58 | 56 |
59 // Send up some memory-usage stats. Bits because fractional bytes | 57 // Send up some memory-usage stats. Bits because fractional bytes |
60 // are weird. | 58 // are weird. |
61 const size_t bits_used = index_.size() * sizeof(index_[0]) * CHAR_BIT + | 59 const size_t bits_used = index_.size() * sizeof(index_[0]) * CHAR_BIT + |
62 deltas_.size() * sizeof(deltas_[0]) * CHAR_BIT; | 60 deltas_.size() * sizeof(deltas_[0]) * CHAR_BIT; |
63 const size_t unique_prefixes = index_.size() + deltas_.size(); | 61 const size_t unique_prefixes = index_.size() + deltas_.size(); |
64 static const size_t kMaxBitsPerPrefix = sizeof(SBPrefix) * CHAR_BIT; | 62 static const size_t kMaxBitsPerPrefix = sizeof(SBPrefix) * CHAR_BIT; |
65 UMA_HISTOGRAM_ENUMERATION("SB2.PrefixSetBitsPerPrefix", | 63 UMA_HISTOGRAM_ENUMERATION("SB2.PrefixSetBitsPerPrefix", |
66 bits_used / unique_prefixes, | 64 bits_used / unique_prefixes, |
(...skipping 29 matching lines...) Expand all Loading... |
96 return true; | 94 return true; |
97 | 95 |
98 // Scan forward accumulating deltas while a match is possible. | 96 // Scan forward accumulating deltas while a match is possible. |
99 for (size_t di = iter->second; di < bound && current < prefix; ++di) { | 97 for (size_t di = iter->second; di < bound && current < prefix; ++di) { |
100 current += deltas_[di]; | 98 current += deltas_[di]; |
101 } | 99 } |
102 | 100 |
103 return current == prefix; | 101 return current == prefix; |
104 } | 102 } |
105 | 103 |
| 104 void PrefixSet::GetPrefixes(std::vector<SBPrefix>* prefixes) { |
| 105 for (size_t ii = 0; ii < index_.size(); ++ii) { |
| 106 // The deltas for this |index_| entry run to the next index entry, |
| 107 // or the end of the deltas. |
| 108 const size_t deltas_end = |
| 109 (ii + 1 < index_.size()) ? index_[ii + 1].second : deltas_.size(); |
| 110 |
| 111 SBPrefix current = index_[ii].first; |
| 112 prefixes->push_back(current); |
| 113 for (size_t di = index_[ii].second; di < deltas_end; ++di) { |
| 114 current += deltas_[di]; |
| 115 prefixes->push_back(current); |
| 116 } |
| 117 } |
| 118 } |
| 119 |
106 } // namespace safe_browsing | 120 } // namespace safe_browsing |
OLD | NEW |