summaryrefslogtreecommitdiff log msg author committer range
path: root/hash.h
blob: 66dd3d6916ea5b1386948c2d2a661d8bce59abf9 (plain)
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 #ifndef _LINUX_HASH_H #define _LINUX_HASH_H #include #include "arch/arch.h" /* Fast hashing routine for a long. (C) 2002 William Lee Irwin III, IBM */ /* * Knuth recommends primes in approximately golden ratio to the maximum * integer representable by a machine word for multiplicative hashing. * Chuck Lever verified the effectiveness of this technique: * http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf * * These primes are chosen to be bit-sparse, that is operations on * them can use shifts and additions instead of multiplications for * machines where multiplications are slow. */ #if BITS_PER_LONG == 32 /* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 */ #define GOLDEN_RATIO_PRIME 0x9e370001UL #elif BITS_PER_LONG == 64 /* 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */ #define GOLDEN_RATIO_PRIME 0x9e37fffffffc0001UL #else #error Define GOLDEN_RATIO_PRIME for your wordsize. #endif /* * The above primes are actively bad for hashing, since they are * too sparse. The 32-bit one is mostly ok, the 64-bit one causes * real problems. Besides, the "prime" part is pointless for the * multiplicative hash. * * Although a random odd number will do, it turns out that the golden * ratio phi = (sqrt(5)-1)/2, or its negative, has particularly nice * properties. * * These are the negative, (1 - phi) = (phi^2) = (3 - sqrt(5))/2. * (See Knuth vol 3, section 6.4, exercise 9.) */ #define GOLDEN_RATIO_32 0x61C88647 #define GOLDEN_RATIO_64 0x61C8864680B583EBull static inline unsigned long __hash_long(uint64_t val) { uint64_t hash = val; #if BITS_PER_LONG == 64 hash *= GOLDEN_RATIO_64; #else /* Sigh, gcc can't optimise this alone like it does for 32 bits. */ uint64_t n = hash; n <<= 18; hash -= n; n <<= 33; hash -= n; n <<= 3; hash += n; n <<= 3; hash -= n; n <<= 4; hash += n; n <<= 2; hash += n; #endif return hash; } static inline unsigned long hash_long(unsigned long val, unsigned int bits) { /* High bits are more random, so use them. */ return __hash_long(val) >> (BITS_PER_LONG - bits); } static inline uint64_t __hash_u64(uint64_t val) { return val * GOLDEN_RATIO_64; } static inline unsigned long hash_ptr(void *ptr, unsigned int bits) { return hash_long((uintptr_t)ptr, bits); } /* * Bob Jenkins jhash */ #define JHASH_INITVAL GOLDEN_RATIO_32 static inline uint32_t rol32(uint32_t word, uint32_t shift) { return (word << shift) | (word >> (32 - shift)); } /* __jhash_mix -- mix 3 32-bit values reversibly. */ #define __jhash_mix(a, b, c) \ { \ a -= c; a ^= rol32(c, 4); c += b; \ b -= a; b ^= rol32(a, 6); a += c; \ c -= b; c ^= rol32(b, 8); b += a; \ a -= c; a ^= rol32(c, 16); c += b; \ b -= a; b ^= rol32(a, 19); a += c; \ c -= b; c ^= rol32(b, 4); b += a; \ } /* __jhash_final - final mixing of 3 32-bit values (a,b,c) into c */ #define __jhash_final(a, b, c) \ { \ c ^= b; c -= rol32(b, 14); \ a ^= c; a -= rol32(c, 11); \ b ^= a; b -= rol32(a, 25); \ c ^= b; c -= rol32(b, 16); \ a ^= c; a -= rol32(c, 4); \ b ^= a; b -= rol32(a, 14); \ c ^= b; c -= rol32(b, 24); \ } static inline uint32_t jhash(const void *key, uint32_t length, uint32_t initval) { const uint8_t *k = key; uint32_t a, b, c; /* Set up the internal state */ a = b = c = JHASH_INITVAL + length + initval; /* All but the last block: affect some 32 bits of (a,b,c) */ while (length > 12) { a += *k; b += *(k + 4); c += *(k + 8); __jhash_mix(a, b, c); length -= 12; k += 12; } /* Last block: affect all 32 bits of (c) */ /* All the case statements fall through */ switch (length) { case 12: c += (uint32_t) k << 24; /* fall through */ case 11: c += (uint32_t) k << 16; /* fall through */ case 10: c += (uint32_t) k << 8; /* fall through */ case 9: c += k; /* fall through */ case 8: b += (uint32_t) k << 24; /* fall through */ case 7: b += (uint32_t) k << 16; /* fall through */ case 6: b += (uint32_t) k << 8; /* fall through */ case 5: b += k; /* fall through */ case 4: a += (uint32_t) k << 24; /* fall through */ case 3: a += (uint32_t) k << 16; /* fall through */ case 2: a += (uint32_t) k << 8; /* fall through */ case 1: a += k; __jhash_final(a, b, c); case 0: /* Nothing left to add */ break; } return c; } #endif /* _LINUX_HASH_H */