Branch data Line data Source code
1 : : /* -*- Mode:C++; c-basic-offset:8; tab-width:8; indent-tabs-mode:t -*- */
2 : : // $Id: TwoWise.h 2809 2006-04-23 20:26:07Z vern $
3 : : //
4 : : // Implementation of 2-wise independent hash functions. Contributed
5 : : // by Yin Zhang.
6 : : //
7 : :
8 : : #ifndef twowise_h
9 : : #define twowise_h
10 : :
11 : : #include "util.h"
12 : :
13 : : typedef union {
14 : : uint64 as_int64;
15 : : uint32 as_int32s[2];
16 : : uint32 as_int16s[4];
17 : : } int64views;
18 : :
19 : : #ifdef WORDS_BIGENDIAN
20 : : #define TOP32BITS(h) h.as_int32s[0]
21 : : #else
22 : : #define TOP32BITS(h) h.as_int32s[1]
23 : : #endif
24 : :
25 : : typedef union {
26 : : uint32 as_int32;
27 : : uint16 as_int16s[2];
28 : : uint16 as_int8s[4];
29 : : } int32views;
30 : :
31 : : class TwoWise {
32 : : public:
33 : : TwoWise(int dim = 0);
34 : : ~TwoWise();
35 : :
36 : 0 : uint32 Hash(uint32 k) const
37 : : {
38 : : int64views h;
39 : 0 : h.as_int64 = a0*k + b0;
40 : 0 : return TOP32BITS(h);
41 : : }
42 : :
43 : 0 : uint32 Hash(uint32 k0, uint32 k1) const
44 : : {
45 : : int64views h;
46 : 0 : h.as_int64 = (a0*k0+b0) ^ (a1*k1+b1);
47 : 0 : return TOP32BITS(h);
48 : : }
49 : :
50 : : uint32 Hash(const uint32* k) const
51 : : {
52 : : int64views h;
53 : : h.as_int64 = (a0*k[0]+b0);
54 : :
55 : : for ( int i = 1; i < dim; ++i )
56 : : h.as_int64 ^= (a[i]*k[i] + b[i]);
57 : :
58 : : return TOP32BITS(h);
59 : : }
60 : :
61 : : uint32 Hash(int size, const uint8* data) const
62 : : {
63 : : if ( size == 0 )
64 : : return 0;
65 : :
66 : : // Copy data to c to resolve any potential alignment problem.
67 : : int num_words = (size + 3) >> 2;
68 : : c[num_words - 1] = 0; // pad with 0
69 : : memcpy(c, data, size);
70 : :
71 : : int64views h;
72 : : h.as_int64 = (a0*c[0]+b0);
73 : :
74 : : for ( int i = 1; i < num_words; ++i )
75 : : h.as_int64 ^= (a[i]*c[i] + b[i]);
76 : :
77 : : return TOP32BITS(h);
78 : : }
79 : :
80 : : void TestSpeed(uint32 N = 1000000);
81 : :
82 : : private:
83 : :
84 : : // Coefficients in Dietzfelbinger scheme.
85 : : uint64 a0, b0, a1, b1; // for 1-d and 2-d case
86 : : uint64 *a, *b; // for N-d case
87 : : uint32 *c;
88 : :
89 : : int dim;
90 : : };
91 : :
92 : : #endif // twowise_h
|