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..a832fefefa978e7feaa4e2136bd5ea0fe4aeb464
--- /dev/null
+++ b/components/rappor/bloom_filter.cc
@@ -0,0 +1,50 @@
+// 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 {
+
+// Distinct seeds are used to create unique hash functions for the bloom filter.
+const uint32_t kHashSeedCount = 4;

[Alexei Svitkine (slow), 2014/01/09 19:23:09]

You can probably get rid of kHashSeedCount and just use [] on the line below.
Then, you can use arraysize(kHashSeeds) in place of it.

[Steven Holte, 2014/01/09 22:03:01]

Done.

+const uint32_t kHashSeeds[kHashSeedCount] = {0xd123957d, 0x6752fc9b,
+                                             0xcb6a0102, 0x1a82ea95};
+
+uint32_t MurmurHash3String(const std::string& str, uint32_t seed) {
+  uint32_t output = 0;
+  // This function is optimized for x86_32, but should work on any platform.
+  MurmurHash3_x86_32(str.data(), str.size(), seed, &output);
+  return output;
+}
+
+}  // namespace
+
+namespace rappor {
+
+BloomFilter::BloomFilter(uint32_t bytes_size, uint32_t hash_count)
+    : bytes_(bytes_size), hash_count_(hash_count) {
+  DCHECK_LE(hash_count, kHashSeedCount);
+}
+
+BloomFilter::~BloomFilter() {}
+
+void BloomFilter::AddString(const std::string& str) {
+  for (size_t j = 0; j < hash_count_; ++j) {
+    uint32_t index = MurmurHash3String(str, kHashSeeds[j]);
+    uint32_t byte_index = (index / 8) % bytes_.size();
+    uint32_t bit_index = index % 8;
+    bytes_[byte_index] |= 1 << bit_index;
+  }
+}
+
+void BloomFilter::AddStrings(const std::vector<std::string>& strings) {
+  for (size_t i = 0, len = strings.size(); i < len; ++i)

[Alexei Svitkine (slow), 2014/01/09 19:23:09]

Nit: No need for |len|, just use |strings.size()| directly. (Compiler will
optimize it.)

[Steven Holte, 2014/01/09 22:03:01]

Done.

+    AddString(strings[i]);
+}
+
+}  // namespace rappor