1/* 2------------------------------------------------------------------------------- 3lookup3.c, by Bob Jenkins, May 2006, Public Domain. 4 5These are functions for producing 32-bit hashes for hash table lookup. 6hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final() 7are externally useful functions. Routines to test the hash are included 8if SELF_TEST is defined. You can use this free for any purpose. It's in 9the public domain. It has no warranty. 10 11You probably want to use hashlittle(). hashlittle() and hashbig() 12hash byte arrays. hashlittle() is is faster than hashbig() on 13little-endian machines. Intel and AMD are little-endian machines. 14On second thought, you probably want hashlittle2(), which is identical to 15hashlittle() except it returns two 32-bit hashes for the price of one. 16You could implement hashbig2() if you wanted but I haven't bothered here. 17 18If you want to find a hash of, say, exactly 7 integers, do 19 a = i1; b = i2; c = i3; 20 mix(a,b,c); 21 a += i4; b += i5; c += i6; 22 mix(a,b,c); 23 a += i7; 24 final(a,b,c); 25then use c as the hash value. If you have a variable length array of 264-byte integers to hash, use hashword(). If you have a byte array (like 27a character string), use hashlittle(). If you have several byte arrays, or 28a mix of things, see the comments above hashlittle(). 29 30Why is this so big? I read 12 bytes at a time into 3 4-byte integers, 31then mix those integers. This is fast (you can do a lot more thorough 32mixing with 12*3 instructions on 3 integers than you can with 3 instructions 33on 1 byte), but shoehorning those bytes into integers efficiently is messy. 34------------------------------------------------------------------------------- 35*/ 36 37#include <stdlib.h> 38 39#ifdef HAVE_CONFIG_H 40#include <jansson_private_config.h> 41#endif 42 43#ifdef HAVE_STDINT_H 44#include <stdint.h> /* defines uint32_t etc */ 45#endif 46 47#ifdef HAVE_SYS_PARAM_H 48#include <sys/param.h> /* attempt to define endianness */ 49#endif 50 51#ifdef HAVE_ENDIAN_H 52# include <endian.h> /* attempt to define endianness */ 53#endif 54 55/* 56 * My best guess at if you are big-endian or little-endian. This may 57 * need adjustment. 58 */ 59#if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \ 60 __BYTE_ORDER == __LITTLE_ENDIAN) || \ 61 (defined(i386) || defined(__i386__) || defined(__i486__) || \ 62 defined(__i586__) || defined(__i686__) || defined(vax) || defined(MIPSEL)) 63# define HASH_LITTLE_ENDIAN 1 64# define HASH_BIG_ENDIAN 0 65#elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \ 66 __BYTE_ORDER == __BIG_ENDIAN) || \ 67 (defined(sparc) || defined(POWERPC) || defined(mc68000) || defined(sel)) 68# define HASH_LITTLE_ENDIAN 0 69# define HASH_BIG_ENDIAN 1 70#else 71# define HASH_LITTLE_ENDIAN 0 72# define HASH_BIG_ENDIAN 0 73#endif 74 75#define hashsize(n) ((uint32_t)1<<(n)) 76#define hashmask(n) (hashsize(n)-1) 77#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) 78 79/* 80------------------------------------------------------------------------------- 81mix -- mix 3 32-bit values reversibly. 82 83This is reversible, so any information in (a,b,c) before mix() is 84still in (a,b,c) after mix(). 85 86If four pairs of (a,b,c) inputs are run through mix(), or through 87mix() in reverse, there are at least 32 bits of the output that 88are sometimes the same for one pair and different for another pair. 89This was tested for: 90* pairs that differed by one bit, by two bits, in any combination 91 of top bits of (a,b,c), or in any combination of bottom bits of 92 (a,b,c). 93* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed 94 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as 95 is commonly produced by subtraction) look like a single 1-bit 96 difference. 97* the base values were pseudorandom, all zero but one bit set, or 98 all zero plus a counter that starts at zero. 99 100Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that 101satisfy this are 102 4 6 8 16 19 4 103 9 15 3 18 27 15 104 14 9 3 7 17 3 105Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing 106for "differ" defined as + with a one-bit base and a two-bit delta. I 107used http://burtleburtle.net/bob/hash/avalanche.html to choose 108the operations, constants, and arrangements of the variables. 109 110This does not achieve avalanche. There are input bits of (a,b,c) 111that fail to affect some output bits of (a,b,c), especially of a. The 112most thoroughly mixed value is c, but it doesn't really even achieve 113avalanche in c. 114 115This allows some parallelism. Read-after-writes are good at doubling 116the number of bits affected, so the goal of mixing pulls in the opposite 117direction as the goal of parallelism. I did what I could. Rotates 118seem to cost as much as shifts on every machine I could lay my hands 119on, and rotates are much kinder to the top and bottom bits, so I used 120rotates. 121------------------------------------------------------------------------------- 122*/ 123#define mix(a,b,c) \ 124{ \ 125 a -= c; a ^= rot(c, 4); c += b; \ 126 b -= a; b ^= rot(a, 6); a += c; \ 127 c -= b; c ^= rot(b, 8); b += a; \ 128 a -= c; a ^= rot(c,16); c += b; \ 129 b -= a; b ^= rot(a,19); a += c; \ 130 c -= b; c ^= rot(b, 4); b += a; \ 131} 132 133/* 134------------------------------------------------------------------------------- 135final -- final mixing of 3 32-bit values (a,b,c) into c 136 137Pairs of (a,b,c) values differing in only a few bits will usually 138produce values of c that look totally different. This was tested for 139* pairs that differed by one bit, by two bits, in any combination 140 of top bits of (a,b,c), or in any combination of bottom bits of 141 (a,b,c). 142* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed 143 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as 144 is commonly produced by subtraction) look like a single 1-bit 145 difference. 146* the base values were pseudorandom, all zero but one bit set, or 147 all zero plus a counter that starts at zero. 148 149These constants passed: 150 14 11 25 16 4 14 24 151 12 14 25 16 4 14 24 152and these came close: 153 4 8 15 26 3 22 24 154 10 8 15 26 3 22 24 155 11 8 15 26 3 22 24 156------------------------------------------------------------------------------- 157*/ 158#define final(a,b,c) \ 159{ \ 160 c ^= b; c -= rot(b,14); \ 161 a ^= c; a -= rot(c,11); \ 162 b ^= a; b -= rot(a,25); \ 163 c ^= b; c -= rot(b,16); \ 164 a ^= c; a -= rot(c,4); \ 165 b ^= a; b -= rot(a,14); \ 166 c ^= b; c -= rot(b,24); \ 167} 168 169/* 170------------------------------------------------------------------------------- 171hashlittle() -- hash a variable-length key into a 32-bit value 172 k : the key (the unaligned variable-length array of bytes) 173 length : the length of the key, counting by bytes 174 initval : can be any 4-byte value 175Returns a 32-bit value. Every bit of the key affects every bit of 176the return value. Two keys differing by one or two bits will have 177totally different hash values. 178 179The best hash table sizes are powers of 2. There is no need to do 180mod a prime (mod is sooo slow!). If you need less than 32 bits, 181use a bitmask. For example, if you need only 10 bits, do 182 h = (h & hashmask(10)); 183In which case, the hash table should have hashsize(10) elements. 184 185If you are hashing n strings (uint8_t **)k, do it like this: 186 for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h); 187 188By Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this 189code any way you wish, private, educational, or commercial. It's free. 190 191Use for hash table lookup, or anything where one collision in 2^^32 is 192acceptable. Do NOT use for cryptographic purposes. 193------------------------------------------------------------------------------- 194*/ 195 196static uint32_t hashlittle(const void *key, size_t length, uint32_t initval) 197{ 198 uint32_t a,b,c; /* internal state */ 199 union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */ 200 201 /* Set up the internal state */ 202 a = b = c = 0xdeadbeef + ((uint32_t)length) + initval; 203 204 u.ptr = key; 205 if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) { 206 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ 207 208/* Detect Valgrind or AddressSanitizer */ 209#ifdef VALGRIND 210# define NO_MASKING_TRICK 1 211#else 212# if defined(__has_feature) /* Clang */ 213# if __has_feature(address_sanitizer) /* is ASAN enabled? */ 214# define NO_MASKING_TRICK 1 215# endif 216# else 217# if defined(__SANITIZE_ADDRESS__) /* GCC 4.8.x, is ASAN enabled? */ 218# define NO_MASKING_TRICK 1 219# endif 220# endif 221#endif 222 223#ifdef NO_MASKING_TRICK 224 const uint8_t *k8; 225#endif 226 227 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ 228 while (length > 12) 229 { 230 a += k[0]; 231 b += k[1]; 232 c += k[2]; 233 mix(a,b,c); 234 length -= 12; 235 k += 3; 236 } 237 238 /*----------------------------- handle the last (probably partial) block */ 239 /* 240 * "k[2]&0xffffff" actually reads beyond the end of the string, but 241 * then masks off the part it's not allowed to read. Because the 242 * string is aligned, the masked-off tail is in the same word as the 243 * rest of the string. Every machine with memory protection I've seen 244 * does it on word boundaries, so is OK with this. But VALGRIND will 245 * still catch it and complain. The masking trick does make the hash 246 * noticably faster for short strings (like English words). 247 */ 248#ifndef NO_MASKING_TRICK 249 250 switch(length) 251 { 252 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; 253 case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break; 254 case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break; 255 case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break; 256 case 8 : b+=k[1]; a+=k[0]; break; 257 case 7 : b+=k[1]&0xffffff; a+=k[0]; break; 258 case 6 : b+=k[1]&0xffff; a+=k[0]; break; 259 case 5 : b+=k[1]&0xff; a+=k[0]; break; 260 case 4 : a+=k[0]; break; 261 case 3 : a+=k[0]&0xffffff; break; 262 case 2 : a+=k[0]&0xffff; break; 263 case 1 : a+=k[0]&0xff; break; 264 case 0 : return c; /* zero length strings require no mixing */ 265 } 266 267#else /* make valgrind happy */ 268 269 k8 = (const uint8_t *)k; 270 switch(length) 271 { 272 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; 273 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ 274 case 10: c+=((uint32_t)k8[9])<<8; /* fall through */ 275 case 9 : c+=k8[8]; /* fall through */ 276 case 8 : b+=k[1]; a+=k[0]; break; 277 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ 278 case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */ 279 case 5 : b+=k8[4]; /* fall through */ 280 case 4 : a+=k[0]; break; 281 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ 282 case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */ 283 case 1 : a+=k8[0]; break; 284 case 0 : return c; 285 } 286 287#endif /* !valgrind */ 288 289 } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) { 290 const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */ 291 const uint8_t *k8; 292 293 /*--------------- all but last block: aligned reads and different mixing */ 294 while (length > 12) 295 { 296 a += k[0] + (((uint32_t)k[1])<<16); 297 b += k[2] + (((uint32_t)k[3])<<16); 298 c += k[4] + (((uint32_t)k[5])<<16); 299 mix(a,b,c); 300 length -= 12; 301 k += 6; 302 } 303 304 /*----------------------------- handle the last (probably partial) block */ 305 k8 = (const uint8_t *)k; 306 switch(length) 307 { 308 case 12: c+=k[4]+(((uint32_t)k[5])<<16); 309 b+=k[2]+(((uint32_t)k[3])<<16); 310 a+=k[0]+(((uint32_t)k[1])<<16); 311 break; 312 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ 313 case 10: c+=k[4]; 314 b+=k[2]+(((uint32_t)k[3])<<16); 315 a+=k[0]+(((uint32_t)k[1])<<16); 316 break; 317 case 9 : c+=k8[8]; /* fall through */ 318 case 8 : b+=k[2]+(((uint32_t)k[3])<<16); 319 a+=k[0]+(((uint32_t)k[1])<<16); 320 break; 321 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ 322 case 6 : b+=k[2]; 323 a+=k[0]+(((uint32_t)k[1])<<16); 324 break; 325 case 5 : b+=k8[4]; /* fall through */ 326 case 4 : a+=k[0]+(((uint32_t)k[1])<<16); 327 break; 328 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ 329 case 2 : a+=k[0]; 330 break; 331 case 1 : a+=k8[0]; 332 break; 333 case 0 : return c; /* zero length requires no mixing */ 334 } 335 336 } else { /* need to read the key one byte at a time */ 337 const uint8_t *k = (const uint8_t *)key; 338 339 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ 340 while (length > 12) 341 { 342 a += k[0]; 343 a += ((uint32_t)k[1])<<8; 344 a += ((uint32_t)k[2])<<16; 345 a += ((uint32_t)k[3])<<24; 346 b += k[4]; 347 b += ((uint32_t)k[5])<<8; 348 b += ((uint32_t)k[6])<<16; 349 b += ((uint32_t)k[7])<<24; 350 c += k[8]; 351 c += ((uint32_t)k[9])<<8; 352 c += ((uint32_t)k[10])<<16; 353 c += ((uint32_t)k[11])<<24; 354 mix(a,b,c); 355 length -= 12; 356 k += 12; 357 } 358 359 /*-------------------------------- last block: affect all 32 bits of (c) */ 360 switch(length) /* all the case statements fall through */ 361 { 362 case 12: c+=((uint32_t)k[11])<<24; 363 case 11: c+=((uint32_t)k[10])<<16; 364 case 10: c+=((uint32_t)k[9])<<8; 365 case 9 : c+=k[8]; 366 case 8 : b+=((uint32_t)k[7])<<24; 367 case 7 : b+=((uint32_t)k[6])<<16; 368 case 6 : b+=((uint32_t)k[5])<<8; 369 case 5 : b+=k[4]; 370 case 4 : a+=((uint32_t)k[3])<<24; 371 case 3 : a+=((uint32_t)k[2])<<16; 372 case 2 : a+=((uint32_t)k[1])<<8; 373 case 1 : a+=k[0]; 374 break; 375 case 0 : return c; 376 } 377 } 378 379 final(a,b,c); 380 return c; 381} 382