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