OLD | NEW |
---|---|
(Empty) | |
1 // Copyright (c) 2013 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 #include <string> | |
6 | |
7 #include "base/logging.h" | |
8 #include "components/rappor/bloom_filter.h" | |
9 #include "third_party/smhasher/src/MurmurHash3.h" | |
10 | |
11 namespace { | |
12 | |
13 // NOTE: These were just generated from /dev/urandom. May be unecessary | |
14 // for murmur hash, or may be better to select carefully to help the | |
15 // hash function distribute its inputs. | |
16 static const uint32_t hashSeedCount = 20; | |
Alexei Svitkine (slow)
2013/12/11 15:27:05
Nit: No need for static keyword for things in the
Steven Holte
2013/12/11 20:31:26
Done.
| |
17 static const uint32_t mockHashSeeds[hashSeedCount] = { | |
18 0xd123957d, 0x6752fc9b, 0xcb6a0102, 0x1a82ea95, 0x55cb27bd, | |
19 0x0d23a17e, 0xbfb2beac, 0xbabca478, 0x6d0b103c, 0x5e98bc37, | |
20 0xe73ccb9d, 0xe60c1150, 0xa5f070a8, 0x91cc68c2, 0x12c919ff, | |
21 0xfec1d371, 0x01b6bf4c, 0xbbe5cf2b, 0x6bd30801, 0x292956d3}; | |
22 | |
23 static inline uint32_t MurmurHash3String(const std::string& str, | |
24 uint32_t seed) { | |
25 uint32_t output = 0; | |
26 MurmurHash3_x86_32(str.data(), str.size(), seed, &output); | |
Alexei Svitkine (slow)
2013/12/11 15:27:05
Chrome isn't always x86_32. Is there a way to call
Steven Holte
2013/12/11 20:31:26
I believe it is just optimized for x86_32.
Accordi
| |
27 return output; | |
28 } | |
29 | |
30 } // namespace | |
31 | |
32 namespace rappor { | |
33 | |
34 BloomFilter::BloomFilter(uint32_t bytes_size, uint32_t hash_count) | |
35 : bytes_(bytes_size), hash_count_(hash_count) { | |
36 DCHECK(hash_count < hashSeedCount); | |
37 } | |
38 | |
39 void BloomFilter::Add(const std::string& str) { | |
40 for (size_t j = 0; j < hash_count_; ++j) { | |
41 uint32_t index = MurmurHash3String(str, mockHashSeeds[j]); | |
42 uint32_t byte_index = (index / 8) % bytes_.size(); | |
43 uint32_t bit_index = index % 8; | |
44 bytes_[byte_index] |= 1 << bit_index; | |
45 } | |
46 } | |
47 | |
48 void BloomFilter::Add(const std::vector<std::string>& strings) { | |
49 for (size_t i = 0, len = strings.size(); i < len; ++i) { | |
Alexei Svitkine (slow)
2013/12/11 15:27:05
Nit: No need for {}s when body is a single line.
Steven Holte
2013/12/11 20:31:26
Done.
| |
50 Add(strings[i]); | |
51 } | |
52 } | |
53 | |
54 const ByteVector& BloomFilter::bytes() const { return bytes_; } | |
55 | |
56 uint32_t BloomFilter::hash_count() const { return hash_count_; } | |
57 | |
58 } // namespace rappor | |
OLD | NEW |