libbf  0.1
 All Classes Functions Typedefs Friends Pages
hash.cc
1 #include <bf/hash.h>
2 
3 #include <cassert>
4 
5 namespace bf {
6 
7 default_hash_function::default_hash_function(size_t seed)
8  : h3_(seed)
9 {
10 }
11 
12 size_t default_hash_function::operator()(object const& o) const
13 {
14  // FIXME: fall back to a generic universal hash function (e.g., HMAC/MD5) for
15  // too large objects.
16  if (o.size() > max_obj_size)
17  throw std::runtime_error("object too large");
18  return o.size() == 0 ? 0 : h3_(o.data(), o.size());
19 }
20 
21 default_hasher::default_hasher(std::vector<hash_function> fns)
22  : fns_(std::move(fns))
23 {
24 }
25 
26 std::vector<digest> default_hasher::operator()(object const& o) const
27 {
28  std::vector<digest> d(fns_.size());
29  for (size_t i = 0; i < fns_.size(); ++i)
30  d[i] = fns_[i](o);
31  return d;
32 }
33 
34 
35 double_hasher::double_hasher(size_t k, hash_function h1, hash_function h2)
36  : k_(k),
37  h1_(std::move(h1)),
38  h2_(std::move(h2))
39 {
40 }
41 
42 std::vector<digest> double_hasher::operator()(object const& o) const
43 {
44  auto d1 = h1_(o);
45  auto d2 = h2_(o);
46  std::vector<digest> d(k_);
47  for (size_t i = 0; i < d.size(); ++i)
48  d[i] = d1 + i * d2;
49  return d;
50 }
51 
52 hasher make_hasher(size_t k, size_t seed, bool double_hashing)
53 {
54  assert(k > 0);
55  std::minstd_rand0 prng(seed);
56  if (double_hashing)
57  {
58  auto h1 = default_hash_function(prng());
59  auto h2 = default_hash_function(prng());
60  return double_hasher(k, std::move(h1), std::move(h2));
61  }
62  else
63  {
64  std::vector<hash_function> fns(k);
65  for (size_t i = 0; i < k; ++i)
66  fns[i] = default_hash_function(prng());
67  return default_hasher(std::move(fns));
68  }
69 }
70 
71 } // namespace bf