hash.h

   1 /* Fast hashing routine for a long.
   2    (C) 2002 William Lee Irwin III, IBM */
   3
   4 /*
   5  * Knuth recommends primes in approximately golden ratio to the maximum
   6  * integer representable by a machine word for multiplicative hashing.
   7  * Chuck Lever verified the effectiveness of this technique:
   8  * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
   9  *
  10  * These primes are chosen to be bit-sparse, that is operations on
  11  * them can use shifts and additions instead of multiplications for
  12  * machines where multiplications are slow.
  13  */
  14 #if BITS_PER_LONG == 32
  15 /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */
  16 #define GOLDEN_RATIO_PRIME 0x9e370001UL
  17 #elif BITS_PER_LONG == 64
  18 /*  2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */
  19 #define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL
  20 #else
  21 #error Define GOLDEN_RATIO_PRIME for your wordsize.
  22 #endif
  23
  24 static inline unsigned long hash_long(unsigned long val, unsigned int bits)
  25 {
  26         unsigned long hash = val;
  27
  28 #if BITS_PER_LONG == 64
  29         /*  Sigh, gcc can't optimise this alone like it does for 32 bits. */
  30         unsigned long n = hash;
  31         n <<= 18;
  32         hash -= n;
  33         n <<= 33;
  34         hash -= n;
  35         n <<= 3;
  36         hash += n;
  37         n <<= 3;
  38         hash -= n;
  39         n <<= 4;
  40         hash += n;
  41         n <<= 2;
  42         hash += n;
  43 #else
  44         /* On some cpus multiply is faster, on others gcc will do shifts */
  45         hash *= GOLDEN_RATIO_PRIME;
  46 #endif
  47
  48         /* High bits are more random, so use them. */
  49         return hash >> (BITS_PER_LONG - bits);
  50 }
  51
  52 static inline unsigned long hash_ptr(void *ptr, unsigned int bits)
  53 {
  54         return hash_long((unsigned long)ptr, bits);
  55 }
  56
  57 static inline unsigned long hash_str(char *name, int bits)
  58 {
  59         unsigned long hash = 0;
  60         unsigned long l = 0;
  61         int len = 0;
  62         unsigned char c;
  63         do {
  64                 if (!(c = *name++)) {
  65                         c = (char)len; len = -1;
  66                 }
  67                 l = (l << 8) | c;
  68                 len++;
  69                 if ((len & (BITS_PER_LONG/8-1))==0)
  70                         hash = hash_long(hash^l, BITS_PER_LONG);
  71         } while (len);
  72         return hash >> (BITS_PER_LONG - bits);
  73 }
  74
  75 static inline unsigned long hash_mem(char *buf, int length, int bits)
  76 {
  77         unsigned long hash = 0;
  78         unsigned long l = 0;
  79         int len = 0;
  80         unsigned char c;
  81         do {
  82                 if (len == length) {
  83                         c = (char)len; len = -1;
  84                 } else
  85                         c = *buf++;
  86                 l = (l << 8) | c;
  87                 len++;
  88                 if ((len & (BITS_PER_LONG/8-1))==0)
  89                         hash = hash_long(hash^l, BITS_PER_LONG);
  90         } while (len);
  91         return hash >> (BITS_PER_LONG - bits);
  92 }