1 /* SPDX-License-Identifier: BSD-3-Clause 2 * 3 * Based on lookup3.c, by Bob Jenkins, May 2006, Public Domain. 4 * http://www.burtleburtle.net/bob/c/lookup3.c 5 * 6 * These functions for producing 32-bit hashes for has table lookup. 7 * hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final() 8 * are externally useful functions. Routines to test the hash are included 9 * if SELF_TEST is defined. You can use this free for any purpose. It is in 10 * the public domain. It has no warranty. 11 */ 12 13 #ifndef _LOOKUP3_H_ 14 #define _LOOKUP3_H_ 15 16 #define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k)))) 17 18 /** ------------------------------------------------------------------------- 19 * This is reversible, so any information in (a,b,c) before mix() is 20 * still in (a,b,c) after mix(). 21 * 22 * If four pairs of (a,b,c) inputs are run through mix(), or through 23 * mix() in reverse, there are at least 32 bits of the output that 24 * are sometimes the same for one pair and different for another pair. 25 * This was tested for: 26 * pairs that differed by one bit, by two bits, in any combination 27 * of top bits of (a,b,c), or in any combination of bottom bits of 28 * (a,b,c). 29 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed 30 * the output delta to a Gray code (a^(a>>1)) so a string of 1's (as 31 * is commonly produced by subtraction) look like a single 1-bit 32 * difference. 33 * the base values were pseudorandom, all zero but one bit set, or 34 * all zero plus a counter that starts at zero. 35 * 36 * Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that 37 * satisfy this are 38 * 4 6 8 16 19 4 39 * 9 15 3 18 27 15 40 * 14 9 3 7 17 3 41 * Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing 42 * for "differ" defined as + with a one-bit base and a two-bit delta. I 43 * used http://burtleburtle.net/bob/hash/avalanche.html to choose 44 * the operations, constants, and arrangements of the variables. 45 * 46 * This does not achieve avalanche. There are input bits of (a,b,c) 47 * that fail to affect some output bits of (a,b,c), especially of a. The 48 * most thoroughly mixed value is c, but it doesn't really even achieve 49 * avalanche in c. 50 * 51 * This allows some parallelism. Read-after-writes are good at doubling 52 * the number of bits affected, so the goal of mixing pulls in the opposite 53 * direction as the goal of parallelism. I did what I could. Rotates 54 * seem to cost as much as shifts on every machine I could lay my hands 55 * on, and rotates are much kinder to the top and bottom bits, so I used 56 * rotates. 57 * -------------------------------------------------------------------------- 58 */ 59 #define mix(a, b, c) \ 60 { \ 61 (a) -= (c); (a) ^= rot((c), 4); (c) += b; \ 62 (b) -= (a); (b) ^= rot((a), 6); (a) += c; \ 63 (c) -= (b); (c) ^= rot((b), 8); (b) += a; \ 64 (a) -= (c); (a) ^= rot((c), 16); (c) += b; \ 65 (b) -= (a); (b) ^= rot((a), 19); (a) += c; \ 66 (c) -= (b); (c) ^= rot((b), 4); (b) += a; \ 67 } 68 69 /** -------------------------------------------------------------------------- 70 * final -- final mixing of 3 32-bit values (a,b,c) into c 71 * 72 * Pairs of (a,b,c) values differing in only a few bits will usually 73 * produce values of c that look totally different. This was tested for 74 * pairs that differed by one bit, by two bits, in any combination 75 * of top bits of (a,b,c), or in any combination of bottom bits of 76 * (a,b,c). 77 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed 78 * the output delta to a Gray code (a^(a>>1)) so a string of 1's (as 79 * is commonly produced by subtraction) look like a single 1-bit 80 * difference. 81 * the base values were pseudorandom, all zero but one bit set, or 82 * all zero plus a counter that starts at zero. 83 * 84 * These constants passed: 85 * 14 11 25 16 4 14 24 86 * 12 14 25 16 4 14 24 87 * and these came close: 88 * 4 8 15 26 3 22 24 89 * 10 8 15 26 3 22 24 90 * 11 8 15 26 3 22 24 91 * -------------------------------------------------------------------------- 92 */ 93 #define final(a, b, c) \ 94 { \ 95 (c) ^= (b); (c) -= rot((b), 14); \ 96 (a) ^= (c); (a) -= rot((c), 11); \ 97 (b) ^= (a); (b) -= rot((a), 25); \ 98 (c) ^= (b); (c) -= rot((b), 16); \ 99 (a) ^= (c); (a) -= rot((c), 4); \ 100 (b) ^= (a); (b) -= rot((a), 14); \ 101 (c) ^= (b); (c) -= rot((b), 24); \ 102 } 103 104 /** -------------------------------------------------------------------- 105 * This works on all machines. To be useful, it requires 106 * -- that the key be an array of uint32_t's, and 107 * -- that the length be the number of uint32_t's in the key 108 109 * The function hashword() is identical to hashlittle() on little-endian 110 * machines, and identical to hashbig() on big-endian machines, 111 * except that the length has to be measured in uint32_ts rather than in 112 * bytes. hashlittle() is more complicated than hashword() only because 113 * hashlittle() has to dance around fitting the key bytes into registers. 114 * 115 * Input Parameters: 116 * key: an array of uint32_t values 117 * length: the length of the key, in uint32_ts 118 * initval: the previous hash, or an arbitrary value 119 * -------------------------------------------------------------------- 120 */ 121 static inline uint32_t hashword(const uint32_t *k, 122 size_t length, 123 uint32_t initval) { 124 uint32_t a, b, c; 125 int index = 12; 126 127 /* Set up the internal state */ 128 a = 0xdeadbeef + (((uint32_t)length) << 2) + initval; 129 b = a; 130 c = a; 131 132 /*-------------------------------------------- handle most of the key */ 133 while (length > 3) { 134 a += k[index]; 135 b += k[index - 1]; 136 c += k[index - 2]; 137 mix(a, b, c); 138 length -= 3; 139 index -= 3; 140 } 141 142 /*-------------------------------------- handle the last 3 uint32_t's */ 143 switch (length) { /* all the case statements fall through */ 144 case 3: 145 c += k[index - 2]; 146 /* Falls through. */ 147 case 2: 148 b += k[index - 1]; 149 /* Falls through. */ 150 case 1: 151 a += k[index]; 152 final(a, b, c); 153 /* Falls through. */ 154 case 0: /* case 0: nothing left to add */ 155 break; 156 } 157 /*------------------------------------------------- report the result */ 158 return c; 159 } 160 161 #endif /* _LOOKUP3_H_ */ 162