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..f9b59110aa0de0a58cf94646aa3e2bda0e6c7a2e
--- /dev/null
+++ b/components/rappor/bloom_filter.cc
@@ -0,0 +1,48 @@
+// 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>

[Ilya Sherman, 2014/01/10 11:00:32]

nit: Already included in the header file.

[Steven Holte, 2014/01/14 00:47:54]

Done.

+
+#include "base/logging.h"
+#include "components/rappor/bloom_filter.h"

[Ilya Sherman, 2014/01/10 11:00:32]

nit: This should be the *first* include in the implementation file, even before
system headers.

[Steven Holte, 2014/01/14 00:47:54]

Done.

[Steven Holte, 2014/01/14 00:47:54]

Done.

+#include "third_party/smhasher/src/MurmurHash3.h"
+
+namespace {
+
+// Distinct seeds are used to create unique hash functions for the bloom filter.

[Ilya Sherman, 2014/01/10 11:00:32]

Might be worth mentioning how these specific seeds were generated, and why there
are only four of them.

[Steven Holte, 2014/01/15 04:53:44]

Expanded the description.

+const uint32_t kHashSeeds[] = {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, arraysize(kHashSeeds));

[Ilya Sherman, 2014/01/10 11:00:32]

Please add an assertion that bytes_size > 0 (and probably > 1)

[Steven Holte, 2014/01/14 00:47:54]

Done.

+}
+
+BloomFilter::~BloomFilter() {}
+
+void BloomFilter::AddString(const std::string& str) {
+  for (size_t j = 0; j < hash_count_; ++j) {

[Ilya Sherman, 2014/01/10 11:00:32]

nit: Why use |j| rather than |i| here?

[Steven Holte, 2014/01/14 00:47:54]

Done.

+    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; i < strings.size(); ++i)

[Ilya Sherman, 2014/01/10 11:00:32]

nit: Please include curly braces to enclose all loop bodies, even when they are
just a single line.

[Alexei Svitkine (slow), 2014/01/10 12:51:02]

Hmm, I advised the opposite. What's the reasoning behind this advise? I thought
Chromium preferred no {}'s for single line bodies, regardless of loop or if or
whatever.

[Ilya Sherman, 2014/01/10 22:34:48]

Sorry, I should have marked this as an optional nit, since it's personal style
preference rather than something dictated by the style guide.  That said, in the
parts of the Chromium codebase that I've worked on, the prevailing style has
been to omit curly braces only for single-line if stmts.

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