bloom_filter.cc 2.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778
  1. // Copyright 2019 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. #include "components/optimization_guide/core/bloom_filter.h"
  5. #include <stddef.h>
  6. #include <stdint.h>
  7. #include "base/check_op.h"
  8. #include "third_party/smhasher/src/MurmurHash3.h"
  9. namespace optimization_guide {
  10. namespace {
  11. uint64_t MurmurHash3(const std::string& str, uint32_t seed) {
  12. // Uses MurmurHash3 in coordination with server as it is a fast hashing
  13. // function with compatible public client and private server implementations.
  14. // DO NOT CHANGE this hashing function without coordination and migration
  15. // plan with the server providing the OptimizationGuide proto.
  16. uint64_t output[2];
  17. MurmurHash3_x64_128(str.data(), str.size(), seed, &output);
  18. // Drop the last 64 bits.
  19. return output[0];
  20. }
  21. } // namespace
  22. BloomFilter::BloomFilter(uint32_t num_hash_functions, uint32_t num_bits)
  23. : num_hash_functions_(num_hash_functions),
  24. num_bits_(num_bits),
  25. bytes_(((num_bits + 7) / 8), 0) {
  26. // May be created on one thread but used on another. The first call to
  27. // CalledOnValidSequence() will re-bind it.
  28. DETACH_FROM_SEQUENCE(sequence_checker_);
  29. }
  30. BloomFilter::BloomFilter(uint32_t num_hash_functions,
  31. uint32_t num_bits,
  32. std::string filter_data)
  33. : num_hash_functions_(num_hash_functions),
  34. num_bits_(num_bits),
  35. bytes_(filter_data.size()) {
  36. // May be created on one thread but used on another. The first call to
  37. // CalledOnValidSequence() will re-bind it.
  38. DETACH_FROM_SEQUENCE(sequence_checker_);
  39. CHECK_GE(filter_data.size() * 8, num_bits);
  40. memcpy(&bytes_[0], filter_data.data(), filter_data.size());
  41. }
  42. BloomFilter::~BloomFilter() = default;
  43. bool BloomFilter::Contains(const std::string& str) const {
  44. DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
  45. for (size_t i = 0; i < num_hash_functions_; ++i) {
  46. uint64_t n = MurmurHash3(str, i) % num_bits_;
  47. uint32_t byte_index = (n / 8);
  48. uint32_t bit_index = n % 8;
  49. if ((bytes_[byte_index] & (1 << bit_index)) == 0)
  50. return false;
  51. }
  52. return true;
  53. }
  54. void BloomFilter::Add(const std::string& str) {
  55. DCHECK_CALLED_ON_VALID_SEQUENCE(sequence_checker_);
  56. for (size_t i = 0; i < num_hash_functions_; ++i) {
  57. uint64_t n = MurmurHash3(str, i) % num_bits_;
  58. uint32_t byte_index = (n / 8);
  59. uint32_t bit_index = n % 8;
  60. bytes_[byte_index] |= 1 << bit_index;
  61. }
  62. }
  63. } // namespace optimization_guide