libbf  0.1
 All Classes Functions Typedefs Friends Pages
h3.h
1 #ifndef BF_H3_H
2 #define BF_H3_H
3 
4 #include <limits>
5 #include <random>
6 
7 namespace bf {
8 
10 template <typename T, int N>
11 class h3
12 {
13  static size_t const bits_per_byte =
14  std::numeric_limits<unsigned char>::digits;
15 
16 public:
17  constexpr static size_t byte_range =
18  std::numeric_limits<unsigned char>::max() + 1;
19 
20  h3(T seed = 0)
21  {
22  T bits[N * bits_per_byte];
23  std::minstd_rand0 prng(seed);
24  for (size_t bit = 0; bit < N * bits_per_byte; ++bit)
25  {
26  bits[bit] = 0;
27  for (size_t i = 0; i < sizeof(T)/2; i++)
28  bits[bit] = (bits[bit] << 16) | (prng() & 0xFFFF);
29  }
30 
31  for (size_t byte = 0; byte < N; ++byte)
32  for (size_t val = 0; val < byte_range; ++val)
33  {
34  bytes_[byte][val] = 0;
35  for (size_t bit = 0; bit < bits_per_byte; ++bit)
36  if (val & (1 << bit))
37  bytes_[byte][val] ^= bits[byte * bits_per_byte + bit];
38  }
39  }
40 
41  T operator()(void const* data, size_t size, size_t offset = 0) const
42  {
43  auto *p = static_cast<unsigned char const*>(data);
44  T result = 0;
45  // Duff's Device.
46  register auto n = (size + 7) / 8;
47  switch (size % 8)
48  {
49  case 0: do { result ^= bytes_[offset++][*p++];
50  case 7: result ^= bytes_[offset++][*p++];
51  case 6: result ^= bytes_[offset++][*p++];
52  case 5: result ^= bytes_[offset++][*p++];
53  case 4: result ^= bytes_[offset++][*p++];
54  case 3: result ^= bytes_[offset++][*p++];
55  case 2: result ^= bytes_[offset++][*p++];
56  case 1: result ^= bytes_[offset++][*p++];
57  } while ( --n > 0 );
58  }
59  return result;
60  }
61 
62 private:
63  T bytes_[N][byte_range];
64 };
65 
66 } // namespace bf
67 
68 #endif