components/rappor/bloom_filter.cc

   1 // Copyright 2014 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 "components/rappor/bloom_filter.h"
   6
   7 #include "base/logging.h"
   8
   9 // TODO(holte): we can't include "City.h" due to typedef conflicts.
  10 extern uint64 CityHash64WithSeed(const char *buf, size_t len, uint64 seed);
  11
  12 namespace rappor {
  13
  14 BloomFilter::BloomFilter(uint32_t bytes_size,
  15                          uint32_t hash_function_count,
  16                          uint32_t hash_seed_offset)
  17     : bytes_(bytes_size),
  18       hash_function_count_(hash_function_count),
  19       hash_seed_offset_(hash_seed_offset) {
  20   DCHECK_GT(bytes_size, 0u);
  21 }
  22
  23 BloomFilter::~BloomFilter() {}
  24
  25 void BloomFilter::AddString(const std::string& str) {
  26   for (size_t i = 0; i < hash_function_count_; ++i) {
  27     // Using CityHash here because we have support for it in Dremel.  Many hash
  28     // functions, such as MD5, SHA1, or Murmur, would probably also work.
  29     uint32_t index =
  30         CityHash64WithSeed(str.data(), str.size(), hash_seed_offset_ + i);
  31     // Note that the "bytes" are uint8_t, so they are always 8-bits.
  32     uint32_t byte_index = (index / 8) % bytes_.size();
  33     uint32_t bit_index = index % 8;
  34     bytes_[byte_index] |= 1 << bit_index;
  35   }
  36 }
  37
  38 }  // namespace rappor