jenkins_hash.h

   1 #ifndef JENKINS_HASH_HH    //Taj
   2 #define JENKINS_HASH_HH
   3
   4 typedef  unsigned       int  ub4;   /* unsigned 4-byte quantities */ //Taj removed long
   5 typedef  unsigned       char ub1;   /* unsigned 1-byte quantities */
   6
   7
   8
   9
  10 #define hashsize(n) ((ub4)1<<(n))
  11 #define hashmask(n) (hashsize(n)-1)
  12
  13
  14
  15
  16 /* mix -- mix 3 32-bit values reversibly.
  17  * For every delta with one or two bits set, and the deltas of all three
  18  *   high bits or all three low bits, whether the original value of a,b,c
  19  *     is almost all zero or is uniformly distributed,
  20  *     * If mix() is run forward or backward, at least 32 bits in a,b,c
  21  *       have at least 1/4 probability of changing.
  22  *       * If mix() is run forward, every bit of c will change between 1/3 and
  23  *         2/3 of the time.  (Well, 22/100 and 78/100 for some 2-bit deltas.)
  24  *         mix() takes 36 machine instructions, but only 18 cycles on a superscalar
  25  *           machine (like a Pentium or a Sparc).  No faster mixer seems to work,
  26  *             that's the result of my brute-force search.  There were about 2^68
  27  *               hashes to choose from.  I only tested about a billion of those.
  28  *               */
  29 #define mix(a,b,c) \
  30 { \
  31   a -= b; a -= c; a ^= (c>>13); \
  32   b -= c; b -= a; b ^= (a<<8); \
  33   c -= a; c -= b; c ^= (b>>13); \
  34   a -= b; a -= c; a ^= (c>>12);  \
  35   b -= c; b -= a; b ^= (a<<16); \
  36   c -= a; c -= b; c ^= (b>>5); \
  37   a -= b; a -= c; a ^= (c>>3);  \
  38   b -= c; b -= a; b ^= (a<<10); \
  39   c -= a; c -= b; c ^= (b>>15); \
  40 }
  41
  42
  43
  44
  45 /* hash() -- hash a variable-length key into a 32-bit value
  46  *   k       : the key (the unaligned variable-length array of bytes)
  47  *     len     : the length of the key, counting by bytes
  48  *       initval : can be any 4-byte value
  49  *       Returns a 32-bit value.  Every bit of the key affects every bit of
  50  *       the return value.  Every 1-bit and 2-bit delta achieves avalanche.
  51  *       About 6*len+35 instructions.
  52  *       The best hash table sizes are powers of 2.  There is no need to do
  53  *       mod a prime (mod is sooo slow!).  If you need less than 32 bits,
  54  *       use a bitmask.  For example, if you need only 10 bits, do
  55  *         h = (h & hashmask(10));
  56  *         In which case, the hash table should have hashsize(10) elements.
  57  *         If you are hashing n strings (ub1 **)k, do it like this:
  58  *           for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);
  59  *           By Bob Jenkins, 1996.  bob_jenkins@compuserve.com.  You may use this
  60  *           code any way you wish, private, educational, or commercial.  It's free.
  61  *           See http://ourworld.compuserve.com/homepages/bob_jenkins/evahash.htm
  62  *           Use for hash table lookup, or anything where one collision in 2^^32 is
  63  *           acceptable.  Do NOT use for cryptographic purposes.
  64  *           */
  65
  66
  67
  68
  69 ub4 hash( ub1 *k, ub4 length, ub4 initval)
  70 //Tajregister ub1 *k;        /* the key */
  71 //register ub4  length;   /* the length of the key */
  72 //register ub4  initval;  /* the previous hash, or an arbitrary value */
  73 {
  74    register ub4 a,b,c,len;
  75
  76
  77
  78
  79    /* Set up the internal state */
  80    len = length;
  81    a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
  82    c = initval;         /* the previous hash value */
  83
  84
  85
  86
  87    /*---------------------------------------- handle most of the key */
  88    while (len >= 12)
  89    {
  90       a += (k[0] +((ub4)k[1]<<8) +((ub4)k[2]<<16) +((ub4)k[3]<<24));
  91       b += (k[4] +((ub4)k[5]<<8) +((ub4)k[6]<<16) +((ub4)k[7]<<24));
  92       c += (k[8] +((ub4)k[9]<<8) +((ub4)k[10]<<16)+((ub4)k[11]<<24));
  93       mix(a,b,c);
  94       k += 12; len -= 12;
  95    }
  96    /*------------------------------------- handle the last 11 bytes */
  97    c += length;
  98    switch(len)              /* all the case statements fall through */
  99    {
 100    case 11: c+=((ub4)k[10]<<24);
 101    case 10: c+=((ub4)k[9]<<16);
 102    case 9 : c+=((ub4)k[8]<<8);
 103       /* the first byte of c is reserved for the length */
 104    case 8 : b+=((ub4)k[7]<<24);
 105    case 7 : b+=((ub4)k[6]<<16);
 106    case 6 : b+=((ub4)k[5]<<8);
 107    case 5 : b+=k[4];
 108    case 4 : a+=((ub4)k[3]<<24);
 109    case 3 : a+=((ub4)k[2]<<16);
 110    case 2 : a+=((ub4)k[1]<<8);
 111    case 1 : a+=k[0];
 112      /* case 0: nothing left to add */
 113    }
 114    mix(a,b,c);
 115    /*-------------------------------------------- report the result */
 116    return c;
 117 }
 118
 119 #endif //JENKINS_HASH_HH