RAPPOR implementation

components/rappor/bloom_filter.cc

Index: components/rappor/bloom_filter.cc
diff --git a/components/rappor/bloom_filter.cc b/components/rappor/bloom_filter.cc
new file mode 100644
index 0000000000000000000000000000000000000000..d913e2c642ea0710df1016dd11bd0cf593d49c40
--- /dev/null
+++ b/components/rappor/bloom_filter.cc
@@ -0,0 +1,58 @@
+// Copyright (c) 2013 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <string>
+
+#include "base/logging.h"
+#include "components/rappor/bloom_filter.h"
+#include "third_party/smhasher/src/MurmurHash3.h"
+
+namespace {
+
+// NOTE: These were just generated from /dev/urandom.  May be unecessary
+//       for murmur hash, or may be better to select carefully to help the
+//       hash function distribute its inputs.
+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 anon namespace. For these
constants and the function below.

[Steven Holte, 2013/12/11 20:31:26]

Done.

+static const uint32_t mockHashSeeds[hashSeedCount] = {
+    0xd123957d, 0x6752fc9b, 0xcb6a0102, 0x1a82ea95, 0x55cb27bd,
+    0x0d23a17e, 0xbfb2beac, 0xbabca478, 0x6d0b103c, 0x5e98bc37,
+    0xe73ccb9d, 0xe60c1150, 0xa5f070a8, 0x91cc68c2, 0x12c919ff,
+    0xfec1d371, 0x01b6bf4c, 0xbbe5cf2b, 0x6bd30801, 0x292956d3};
+
+static inline uint32_t MurmurHash3String(const std::string& str,
+                                         uint32_t seed) {
+  uint32_t output = 0;
+  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 a non-arch specific version
of this?

[Steven Holte, 2013/12/11 20:31:26]

I believe it is just optimized for x86_32.
According to the comment in third_party/smhasher/src/MurmurHash3.cpp:
// You can still
// compile and run any of them on any platform, but your performance with the
// non-native version will be less than optimal.

safe_browsing uses the same hash function:
chrome/renderer/safe_browsing/murmurhash3_util.cc

+  return output;
+}
+
+}  // namespace
+
+namespace rappor {
+
+BloomFilter::BloomFilter(uint32_t bytes_size, uint32_t hash_count)
+    : bytes_(bytes_size), hash_count_(hash_count) {
+  DCHECK(hash_count < hashSeedCount);
+}
+
+void BloomFilter::Add(const std::string& str) {
+  for (size_t j = 0; j < hash_count_; ++j) {
+    uint32_t index = MurmurHash3String(str, mockHashSeeds[j]);
+    uint32_t byte_index = (index / 8) % bytes_.size();
+    uint32_t bit_index = index % 8;
+    bytes_[byte_index] |= 1 << bit_index;
+  }
+}
+
+void BloomFilter::Add(const std::vector<std::string>& strings) {
+  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.

+    Add(strings[i]);
+  }
+}
+
+const ByteVector& BloomFilter::bytes() const { return bytes_; }
+
+uint32_t BloomFilter::hash_count() const { return hash_count_; }
+
+}  // namespace rappor