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..4fc972792a121daf85290e50148e471da9084d01
--- /dev/null
+++ b/components/rappor/bloom_filter.cc
@@ -0,0 +1,37 @@
+// Copyright 2014 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 "components/rappor/bloom_filter.h"
+
+#include "base/logging.h"
+
+// TODO(holte): we can't include "City.h" due to type def conflicts.

[Ilya Sherman, 2014/02/13 23:23:08]

nit: "type def" -> "typedef"

[Steven Holte, 2014/02/14 02:53:29]

Done.

+extern uint64 CityHash64WithSeed(const char *buf, size_t len, uint64 seed);
+
+namespace rappor {
+
+BloomFilter::BloomFilter(uint32_t bytes_size,
+                         uint32_t hash_function_count,
+                         uint32_t hash_seed_offset)
+    : bytes_(bytes_size),
+      hash_function_count_(hash_function_count),
+      hash_seed_offset_(hash_seed_offset) {
+  DCHECK_GT(bytes_size, 0u);
+}
+
+BloomFilter::~BloomFilter() {}
+
+void BloomFilter::AddString(const std::string& str) {
+  for (size_t i = 0; i < hash_function_count_; ++i) {
+    // Using CityHash here because we have support for it in Dremel.

[Ilya Sherman, 2014/02/13 23:23:08]

Dremel supports lots of hash functions.  Presumably you care about speed or
something like that as well?

[Steven Holte, 2014/02/14 02:53:29]

It's pretty flexible.  Murmur, MD5, or SHA would probably also work.

[Ilya Sherman, 2014/02/14 05:23:09]

Hmm, interesting.  I'd probably include that sentence in the documentation as
well, for extra clarity to anyone who might come along wondering if the newest,
hottest InstaHash function might be a good replacement here.

Just to appease my own curiosity, I've fired off an email to chromium-dev@
asking which hash function folks recommend.  No need to block on that thread to
resolve or anything, though :)

[Steven Holte, 2014/02/14 23:01:08]

Done.

+    uint32_t index =
+        CityHash64WithSeed(str.data(), str.size(), hash_seed_offset_ + i);
+    // Note that the "bytes" are uint8_t, so they are always 8-bits.
+    uint32_t byte_index = (index / 8) % bytes_.size();
+    uint32_t bit_index = index % 8;
+    bytes_[byte_index] |= 1 << bit_index;
+  }
+}
+
+}  // namespace rappor