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