1 /* 2 ------------------------------------------------------------------------------- 3 lookup3.c, by Bob Jenkins, May 2006, Public Domain. 4 5 These are functions for producing 32-bit hashes for hash table lookup. 6 hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final() 7 are externally useful functions. Routines to test the hash are included 8 if SELF_TEST is defined. You can use this free for any purpose. It's in 9 the public domain. It has no warranty. 10 11 You probably want to use hashlittle(). hashlittle() and hashbig() 12 hash byte arrays. hashlittle() is is faster than hashbig() on 13 little-endian machines. Intel and AMD are little-endian machines. 14 On second thought, you probably want hashlittle2(), which is identical to 15 hashlittle() except it returns two 32-bit hashes for the price of one. 16 You could implement hashbig2() if you wanted but I haven't bothered here. 17 18 If 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); 25 then use c as the hash value. If you have a variable length array of 26 4-byte integers to hash, use hashword(). If you have a byte array (like 27 a character string), use hashlittle(). If you have several byte arrays, or 28 a mix of things, see the comments above hashlittle(). 29 30 Why is this so big? I read 12 bytes at a time into 3 4-byte integers, 31 then mix those integers. This is fast (you can do a lot more thorough 32 mixing with 12*3 instructions on 3 integers than you can with 3 instructions 33 on 1 byte), but shoehorning those bytes into integers efficiently is messy. 34 ------------------------------------------------------------------------------- 35 */ 36 #define SELF_TEST 1 37 #undef SELF_TEST 38 39 #include <stdio.h> /* defines printf for tests */ 40 #include <time.h> /* defines time_t for timings in the test */ 41 #include <stdint.h> /* defines uint32_t etc */ 42 #include <sys/param.h> /* attempt to define endianness */ 43 #ifdef linux 44 # include <endian.h> /* attempt to define endianness */ 45 #endif 46 47 /* 48 * My best guess at if you are big-endian or little-endian. This may 49 * need adjustment. 50 */ 51 #if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \ 52 __BYTE_ORDER == __LITTLE_ENDIAN) || \ 53 (defined(i386) || defined(__i386__) || defined(__i486__) || \ 54 defined(__i586__) || defined(__i686__) || defined(vax) || defined(MIPSEL)) 55 # define HASH_LITTLE_ENDIAN 1 56 # define HASH_BIG_ENDIAN 0 57 #elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \ 58 __BYTE_ORDER == __BIG_ENDIAN) || \ 59 (defined(sparc) || defined(POWERPC) || defined(mc68000) || defined(sel)) 60 # define HASH_LITTLE_ENDIAN 0 61 # define HASH_BIG_ENDIAN 1 62 #else 63 # define HASH_LITTLE_ENDIAN 0 64 # define HASH_BIG_ENDIAN 0 65 #endif 66 67 #define hashsize(n) ((uint32_t)1<<(n)) 68 #define hashmask(n) (hashsize(n)-1) 69 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) 70 71 /* 72 ------------------------------------------------------------------------------- 73 mix -- mix 3 32-bit values reversibly. 74 75 This is reversible, so any information in (a,b,c) before mix() is 76 still in (a,b,c) after mix(). 77 78 If four pairs of (a,b,c) inputs are run through mix(), or through 79 mix() in reverse, there are at least 32 bits of the output that 80 are sometimes the same for one pair and different for another pair. 81 This was tested for: 82 * pairs that differed by one bit, by two bits, in any combination 83 of top bits of (a,b,c), or in any combination of bottom bits of 84 (a,b,c). 85 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed 86 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as 87 is commonly produced by subtraction) look like a single 1-bit 88 difference. 89 * the base values were pseudorandom, all zero but one bit set, or 90 all zero plus a counter that starts at zero. 91 92 Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that 93 satisfy this are 94 4 6 8 16 19 4 95 9 15 3 18 27 15 96 14 9 3 7 17 3 97 Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing 98 for "differ" defined as + with a one-bit base and a two-bit delta. I 99 used http://burtleburtle.net/bob/hash/avalanche.html to choose 100 the operations, constants, and arrangements of the variables. 101 102 This does not achieve avalanche. There are input bits of (a,b,c) 103 that fail to affect some output bits of (a,b,c), especially of a. The 104 most thoroughly mixed value is c, but it doesn't really even achieve 105 avalanche in c. 106 107 This allows some parallelism. Read-after-writes are good at doubling 108 the number of bits affected, so the goal of mixing pulls in the opposite 109 direction as the goal of parallelism. I did what I could. Rotates 110 seem to cost as much as shifts on every machine I could lay my hands 111 on, and rotates are much kinder to the top and bottom bits, so I used 112 rotates. 113 ------------------------------------------------------------------------------- 114 */ 115 #define mix(a,b,c) \ 116 { \ 117 a -= c; a ^= rot(c, 4); c += b; \ 118 b -= a; b ^= rot(a, 6); a += c; \ 119 c -= b; c ^= rot(b, 8); b += a; \ 120 a -= c; a ^= rot(c,16); c += b; \ 121 b -= a; b ^= rot(a,19); a += c; \ 122 c -= b; c ^= rot(b, 4); b += a; \ 123 } 124 125 /* 126 ------------------------------------------------------------------------------- 127 final -- final mixing of 3 32-bit values (a,b,c) into c 128 129 Pairs of (a,b,c) values differing in only a few bits will usually 130 produce values of c that look totally different. This was tested for 131 * pairs that differed by one bit, by two bits, in any combination 132 of top bits of (a,b,c), or in any combination of bottom bits of 133 (a,b,c). 134 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed 135 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as 136 is commonly produced by subtraction) look like a single 1-bit 137 difference. 138 * the base values were pseudorandom, all zero but one bit set, or 139 all zero plus a counter that starts at zero. 140 141 These constants passed: 142 14 11 25 16 4 14 24 143 12 14 25 16 4 14 24 144 and these came close: 145 4 8 15 26 3 22 24 146 10 8 15 26 3 22 24 147 11 8 15 26 3 22 24 148 ------------------------------------------------------------------------------- 149 */ 150 #define final(a,b,c) \ 151 { \ 152 c ^= b; c -= rot(b,14); \ 153 a ^= c; a -= rot(c,11); \ 154 b ^= a; b -= rot(a,25); \ 155 c ^= b; c -= rot(b,16); \ 156 a ^= c; a -= rot(c,4); \ 157 b ^= a; b -= rot(a,14); \ 158 c ^= b; c -= rot(b,24); \ 159 } 160 161 /* 162 -------------------------------------------------------------------- 163 This works on all machines. To be useful, it requires 164 -- that the key be an array of uint32_t's, and 165 -- that the length be the number of uint32_t's in the key 166 167 The function hashword() is identical to hashlittle() on little-endian 168 machines, and identical to hashbig() on big-endian machines, 169 except that the length has to be measured in uint32_ts rather than in 170 bytes. hashlittle() is more complicated than hashword() only because 171 hashlittle() has to dance around fitting the key bytes into registers. 172 -------------------------------------------------------------------- 173 */ 174 uint32_t hashword( 175 const uint32_t *k, /* the key, an array of uint32_t values */ 176 size_t length, /* the length of the key, in uint32_ts */ 177 uint32_t initval) /* the previous hash, or an arbitrary value */ 178 { 179 uint32_t a,b,c; 180 181 /* Set up the internal state */ 182 a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval; 183 184 /*------------------------------------------------- handle most of the key */ 185 while (length > 3) 186 { 187 a += k[0]; 188 b += k[1]; 189 c += k[2]; 190 mix(a,b,c); 191 length -= 3; 192 k += 3; 193 } 194 195 /*------------------------------------------- handle the last 3 uint32_t's */ 196 switch(length) /* all the case statements fall through */ 197 { 198 case 3 : c+=k[2]; 199 case 2 : b+=k[1]; 200 case 1 : a+=k[0]; 201 final(a,b,c); 202 case 0: /* case 0: nothing left to add */ 203 break; 204 } 205 /*------------------------------------------------------ report the result */ 206 return c; 207 } 208 209 210 /* 211 -------------------------------------------------------------------- 212 hashword2() -- same as hashword(), but take two seeds and return two 213 32-bit values. pc and pb must both be nonnull, and *pc and *pb must 214 both be initialized with seeds. If you pass in (*pb)==0, the output 215 (*pc) will be the same as the return value from hashword(). 216 -------------------------------------------------------------------- 217 */ 218 void hashword2 ( 219 const uint32_t *k, /* the key, an array of uint32_t values */ 220 size_t length, /* the length of the key, in uint32_ts */ 221 uint32_t *pc, /* IN: seed OUT: primary hash value */ 222 uint32_t *pb) /* IN: more seed OUT: secondary hash value */ 223 { 224 uint32_t a,b,c; 225 226 /* Set up the internal state */ 227 a = b = c = 0xdeadbeef + ((uint32_t)(length<<2)) + *pc; 228 c += *pb; 229 230 /*------------------------------------------------- handle most of the key */ 231 while (length > 3) 232 { 233 a += k[0]; 234 b += k[1]; 235 c += k[2]; 236 mix(a,b,c); 237 length -= 3; 238 k += 3; 239 } 240 241 /*------------------------------------------- handle the last 3 uint32_t's */ 242 switch(length) /* all the case statements fall through */ 243 { 244 case 3 : c+=k[2]; 245 case 2 : b+=k[1]; 246 case 1 : a+=k[0]; 247 final(a,b,c); 248 case 0: /* case 0: nothing left to add */ 249 break; 250 } 251 /*------------------------------------------------------ report the result */ 252 *pc=c; *pb=b; 253 } 254 255 256 /* 257 ------------------------------------------------------------------------------- 258 hashlittle() -- hash a variable-length key into a 32-bit value 259 k : the key (the unaligned variable-length array of bytes) 260 length : the length of the key, counting by bytes 261 initval : can be any 4-byte value 262 Returns a 32-bit value. Every bit of the key affects every bit of 263 the return value. Two keys differing by one or two bits will have 264 totally different hash values. 265 266 The best hash table sizes are powers of 2. There is no need to do 267 mod a prime (mod is sooo slow!). If you need less than 32 bits, 268 use a bitmask. For example, if you need only 10 bits, do 269 h = (h & hashmask(10)); 270 In which case, the hash table should have hashsize(10) elements. 271 272 If you are hashing n strings (uint8_t **)k, do it like this: 273 for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h); 274 275 By Bob Jenkins, 2006. bob_jenkins (at) burtleburtle.net. You may use this 276 code any way you wish, private, educational, or commercial. It's free. 277 278 Use for hash table lookup, or anything where one collision in 2^^32 is 279 acceptable. Do NOT use for cryptographic purposes. 280 ------------------------------------------------------------------------------- 281 */ 282 283 uint32_t hashlittle( const void *key, size_t length, uint32_t initval) 284 { 285 uint32_t a,b,c; /* internal state */ 286 union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */ 287 288 /* Set up the internal state */ 289 a = b = c = 0xdeadbeef + ((uint32_t)length) + initval; 290 291 u.ptr = key; 292 if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) { 293 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ 294 const uint8_t *k8; 295 296 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ 297 while (length > 12) 298 { 299 a += k[0]; 300 b += k[1]; 301 c += k[2]; 302 mix(a,b,c); 303 length -= 12; 304 k += 3; 305 } 306 307 /*----------------------------- handle the last (probably partial) block */ 308 /* 309 * "k[2]&0xffffff" actually reads beyond the end of the string, but 310 * then masks off the part it's not allowed to read. Because the 311 * string is aligned, the masked-off tail is in the same word as the 312 * rest of the string. Every machine with memory protection I've seen 313 * does it on word boundaries, so is OK with this. But VALGRIND will 314 * still catch it and complain. The masking trick does make the hash 315 * noticably faster for short strings (like English words). 316 */ 317 #ifndef VALGRIND 318 319 switch(length) 320 { 321 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; 322 case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break; 323 case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break; 324 case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break; 325 case 8 : b+=k[1]; a+=k[0]; break; 326 case 7 : b+=k[1]&0xffffff; a+=k[0]; break; 327 case 6 : b+=k[1]&0xffff; a+=k[0]; break; 328 case 5 : b+=k[1]&0xff; a+=k[0]; break; 329 case 4 : a+=k[0]; break; 330 case 3 : a+=k[0]&0xffffff; break; 331 case 2 : a+=k[0]&0xffff; break; 332 case 1 : a+=k[0]&0xff; break; 333 case 0 : return c; /* zero length strings require no mixing */ 334 } 335 336 #else /* make valgrind happy */ 337 338 k8 = (const uint8_t *)k; 339 switch(length) 340 { 341 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; 342 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ 343 case 10: c+=((uint32_t)k8[9])<<8; /* fall through */ 344 case 9 : c+=k8[8]; /* fall through */ 345 case 8 : b+=k[1]; a+=k[0]; break; 346 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ 347 case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */ 348 case 5 : b+=k8[4]; /* fall through */ 349 case 4 : a+=k[0]; break; 350 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ 351 case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */ 352 case 1 : a+=k8[0]; break; 353 case 0 : return c; 354 } 355 356 #endif /* !valgrind */ 357 358 } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) { 359 const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */ 360 const uint8_t *k8; 361 362 /*--------------- all but last block: aligned reads and different mixing */ 363 while (length > 12) 364 { 365 a += k[0] + (((uint32_t)k[1])<<16); 366 b += k[2] + (((uint32_t)k[3])<<16); 367 c += k[4] + (((uint32_t)k[5])<<16); 368 mix(a,b,c); 369 length -= 12; 370 k += 6; 371 } 372 373 /*----------------------------- handle the last (probably partial) block */ 374 k8 = (const uint8_t *)k; 375 switch(length) 376 { 377 case 12: c+=k[4]+(((uint32_t)k[5])<<16); 378 b+=k[2]+(((uint32_t)k[3])<<16); 379 a+=k[0]+(((uint32_t)k[1])<<16); 380 break; 381 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ 382 case 10: c+=k[4]; 383 b+=k[2]+(((uint32_t)k[3])<<16); 384 a+=k[0]+(((uint32_t)k[1])<<16); 385 break; 386 case 9 : c+=k8[8]; /* fall through */ 387 case 8 : b+=k[2]+(((uint32_t)k[3])<<16); 388 a+=k[0]+(((uint32_t)k[1])<<16); 389 break; 390 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ 391 case 6 : b+=k[2]; 392 a+=k[0]+(((uint32_t)k[1])<<16); 393 break; 394 case 5 : b+=k8[4]; /* fall through */ 395 case 4 : a+=k[0]+(((uint32_t)k[1])<<16); 396 break; 397 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ 398 case 2 : a+=k[0]; 399 break; 400 case 1 : a+=k8[0]; 401 break; 402 case 0 : return c; /* zero length requires no mixing */ 403 } 404 405 } else { /* need to read the key one byte at a time */ 406 const uint8_t *k = (const uint8_t *)key; 407 408 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ 409 while (length > 12) 410 { 411 a += k[0]; 412 a += ((uint32_t)k[1])<<8; 413 a += ((uint32_t)k[2])<<16; 414 a += ((uint32_t)k[3])<<24; 415 b += k[4]; 416 b += ((uint32_t)k[5])<<8; 417 b += ((uint32_t)k[6])<<16; 418 b += ((uint32_t)k[7])<<24; 419 c += k[8]; 420 c += ((uint32_t)k[9])<<8; 421 c += ((uint32_t)k[10])<<16; 422 c += ((uint32_t)k[11])<<24; 423 mix(a,b,c); 424 length -= 12; 425 k += 12; 426 } 427 428 /*-------------------------------- last block: affect all 32 bits of (c) */ 429 switch(length) /* all the case statements fall through */ 430 { 431 case 12: c+=((uint32_t)k[11])<<24; 432 case 11: c+=((uint32_t)k[10])<<16; 433 case 10: c+=((uint32_t)k[9])<<8; 434 case 9 : c+=k[8]; 435 case 8 : b+=((uint32_t)k[7])<<24; 436 case 7 : b+=((uint32_t)k[6])<<16; 437 case 6 : b+=((uint32_t)k[5])<<8; 438 case 5 : b+=k[4]; 439 case 4 : a+=((uint32_t)k[3])<<24; 440 case 3 : a+=((uint32_t)k[2])<<16; 441 case 2 : a+=((uint32_t)k[1])<<8; 442 case 1 : a+=k[0]; 443 break; 444 case 0 : return c; 445 } 446 } 447 448 final(a,b,c); 449 return c; 450 } 451 452 453 /* 454 * hashlittle2: return 2 32-bit hash values 455 * 456 * This is identical to hashlittle(), except it returns two 32-bit hash 457 * values instead of just one. This is good enough for hash table 458 * lookup with 2^^64 buckets, or if you want a second hash if you're not 459 * happy with the first, or if you want a probably-unique 64-bit ID for 460 * the key. *pc is better mixed than *pb, so use *pc first. If you want 461 * a 64-bit value do something like "*pc + (((uint64_t)*pb)<<32)". 462 */ 463 void hashlittle2( 464 const void *key, /* the key to hash */ 465 size_t length, /* length of the key */ 466 uint32_t *pc, /* IN: primary initval, OUT: primary hash */ 467 uint32_t *pb) /* IN: secondary initval, OUT: secondary hash */ 468 { 469 uint32_t a,b,c; /* internal state */ 470 union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */ 471 472 /* Set up the internal state */ 473 a = b = c = 0xdeadbeef + ((uint32_t)length) + *pc; 474 c += *pb; 475 476 u.ptr = key; 477 if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) { 478 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ 479 const uint8_t *k8; 480 481 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ 482 while (length > 12) 483 { 484 a += k[0]; 485 b += k[1]; 486 c += k[2]; 487 mix(a,b,c); 488 length -= 12; 489 k += 3; 490 } 491 492 /*----------------------------- handle the last (probably partial) block */ 493 /* 494 * "k[2]&0xffffff" actually reads beyond the end of the string, but 495 * then masks off the part it's not allowed to read. Because the 496 * string is aligned, the masked-off tail is in the same word as the 497 * rest of the string. Every machine with memory protection I've seen 498 * does it on word boundaries, so is OK with this. But VALGRIND will 499 * still catch it and complain. The masking trick does make the hash 500 * noticably faster for short strings (like English words). 501 */ 502 #ifndef VALGRIND 503 504 switch(length) 505 { 506 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; 507 case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break; 508 case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break; 509 case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break; 510 case 8 : b+=k[1]; a+=k[0]; break; 511 case 7 : b+=k[1]&0xffffff; a+=k[0]; break; 512 case 6 : b+=k[1]&0xffff; a+=k[0]; break; 513 case 5 : b+=k[1]&0xff; a+=k[0]; break; 514 case 4 : a+=k[0]; break; 515 case 3 : a+=k[0]&0xffffff; break; 516 case 2 : a+=k[0]&0xffff; break; 517 case 1 : a+=k[0]&0xff; break; 518 case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */ 519 } 520 521 #else /* make valgrind happy */ 522 523 k8 = (const uint8_t *)k; 524 switch(length) 525 { 526 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; 527 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ 528 case 10: c+=((uint32_t)k8[9])<<8; /* fall through */ 529 case 9 : c+=k8[8]; /* fall through */ 530 case 8 : b+=k[1]; a+=k[0]; break; 531 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ 532 case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */ 533 case 5 : b+=k8[4]; /* fall through */ 534 case 4 : a+=k[0]; break; 535 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ 536 case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */ 537 case 1 : a+=k8[0]; break; 538 case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */ 539 } 540 541 #endif /* !valgrind */ 542 543 } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) { 544 const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */ 545 const uint8_t *k8; 546 547 /*--------------- all but last block: aligned reads and different mixing */ 548 while (length > 12) 549 { 550 a += k[0] + (((uint32_t)k[1])<<16); 551 b += k[2] + (((uint32_t)k[3])<<16); 552 c += k[4] + (((uint32_t)k[5])<<16); 553 mix(a,b,c); 554 length -= 12; 555 k += 6; 556 } 557 558 /*----------------------------- handle the last (probably partial) block */ 559 k8 = (const uint8_t *)k; 560 switch(length) 561 { 562 case 12: c+=k[4]+(((uint32_t)k[5])<<16); 563 b+=k[2]+(((uint32_t)k[3])<<16); 564 a+=k[0]+(((uint32_t)k[1])<<16); 565 break; 566 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ 567 case 10: c+=k[4]; 568 b+=k[2]+(((uint32_t)k[3])<<16); 569 a+=k[0]+(((uint32_t)k[1])<<16); 570 break; 571 case 9 : c+=k8[8]; /* fall through */ 572 case 8 : b+=k[2]+(((uint32_t)k[3])<<16); 573 a+=k[0]+(((uint32_t)k[1])<<16); 574 break; 575 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ 576 case 6 : b+=k[2]; 577 a+=k[0]+(((uint32_t)k[1])<<16); 578 break; 579 case 5 : b+=k8[4]; /* fall through */ 580 case 4 : a+=k[0]+(((uint32_t)k[1])<<16); 581 break; 582 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ 583 case 2 : a+=k[0]; 584 break; 585 case 1 : a+=k8[0]; 586 break; 587 case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */ 588 } 589 590 } else { /* need to read the key one byte at a time */ 591 const uint8_t *k = (const uint8_t *)key; 592 593 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ 594 while (length > 12) 595 { 596 a += k[0]; 597 a += ((uint32_t)k[1])<<8; 598 a += ((uint32_t)k[2])<<16; 599 a += ((uint32_t)k[3])<<24; 600 b += k[4]; 601 b += ((uint32_t)k[5])<<8; 602 b += ((uint32_t)k[6])<<16; 603 b += ((uint32_t)k[7])<<24; 604 c += k[8]; 605 c += ((uint32_t)k[9])<<8; 606 c += ((uint32_t)k[10])<<16; 607 c += ((uint32_t)k[11])<<24; 608 mix(a,b,c); 609 length -= 12; 610 k += 12; 611 } 612 613 /*-------------------------------- last block: affect all 32 bits of (c) */ 614 switch(length) /* all the case statements fall through */ 615 { 616 case 12: c+=((uint32_t)k[11])<<24; 617 case 11: c+=((uint32_t)k[10])<<16; 618 case 10: c+=((uint32_t)k[9])<<8; 619 case 9 : c+=k[8]; 620 case 8 : b+=((uint32_t)k[7])<<24; 621 case 7 : b+=((uint32_t)k[6])<<16; 622 case 6 : b+=((uint32_t)k[5])<<8; 623 case 5 : b+=k[4]; 624 case 4 : a+=((uint32_t)k[3])<<24; 625 case 3 : a+=((uint32_t)k[2])<<16; 626 case 2 : a+=((uint32_t)k[1])<<8; 627 case 1 : a+=k[0]; 628 break; 629 case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */ 630 } 631 } 632 633 final(a,b,c); 634 *pc=c; *pb=b; 635 } 636 637 638 639 /* 640 * hashbig(): 641 * This is the same as hashword() on big-endian machines. It is different 642 * from hashlittle() on all machines. hashbig() takes advantage of 643 * big-endian byte ordering. 644 */ 645 uint32_t hashbig( const void *key, size_t length, uint32_t initval) 646 { 647 uint32_t a,b,c; 648 union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */ 649 650 /* Set up the internal state */ 651 a = b = c = 0xdeadbeef + ((uint32_t)length) + initval; 652 653 u.ptr = key; 654 if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) { 655 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ 656 const uint8_t *k8; 657 658 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ 659 while (length > 12) 660 { 661 a += k[0]; 662 b += k[1]; 663 c += k[2]; 664 mix(a,b,c); 665 length -= 12; 666 k += 3; 667 } 668 669 /*----------------------------- handle the last (probably partial) block */ 670 /* 671 * "k[2]<<8" actually reads beyond the end of the string, but 672 * then shifts out the part it's not allowed to read. Because the 673 * string is aligned, the illegal read is in the same word as the 674 * rest of the string. Every machine with memory protection I've seen 675 * does it on word boundaries, so is OK with this. But VALGRIND will 676 * still catch it and complain. The masking trick does make the hash 677 * noticably faster for short strings (like English words). 678 */ 679 #ifndef VALGRIND 680 681 switch(length) 682 { 683 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; 684 case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break; 685 case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break; 686 case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break; 687 case 8 : b+=k[1]; a+=k[0]; break; 688 case 7 : b+=k[1]&0xffffff00; a+=k[0]; break; 689 case 6 : b+=k[1]&0xffff0000; a+=k[0]; break; 690 case 5 : b+=k[1]&0xff000000; a+=k[0]; break; 691 case 4 : a+=k[0]; break; 692 case 3 : a+=k[0]&0xffffff00; break; 693 case 2 : a+=k[0]&0xffff0000; break; 694 case 1 : a+=k[0]&0xff000000; break; 695 case 0 : return c; /* zero length strings require no mixing */ 696 } 697 698 #else /* make valgrind happy */ 699 700 k8 = (const uint8_t *)k; 701 switch(length) /* all the case statements fall through */ 702 { 703 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; 704 case 11: c+=((uint32_t)k8[10])<<8; /* fall through */ 705 case 10: c+=((uint32_t)k8[9])<<16; /* fall through */ 706 case 9 : c+=((uint32_t)k8[8])<<24; /* fall through */ 707 case 8 : b+=k[1]; a+=k[0]; break; 708 case 7 : b+=((uint32_t)k8[6])<<8; /* fall through */ 709 case 6 : b+=((uint32_t)k8[5])<<16; /* fall through */ 710 case 5 : b+=((uint32_t)k8[4])<<24; /* fall through */ 711 case 4 : a+=k[0]; break; 712 case 3 : a+=((uint32_t)k8[2])<<8; /* fall through */ 713 case 2 : a+=((uint32_t)k8[1])<<16; /* fall through */ 714 case 1 : a+=((uint32_t)k8[0])<<24; break; 715 case 0 : return c; 716 } 717 718 #endif /* !VALGRIND */ 719 720 } else { /* need to read the key one byte at a time */ 721 const uint8_t *k = (const uint8_t *)key; 722 723 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ 724 while (length > 12) 725 { 726 a += ((uint32_t)k[0])<<24; 727 a += ((uint32_t)k[1])<<16; 728 a += ((uint32_t)k[2])<<8; 729 a += ((uint32_t)k[3]); 730 b += ((uint32_t)k[4])<<24; 731 b += ((uint32_t)k[5])<<16; 732 b += ((uint32_t)k[6])<<8; 733 b += ((uint32_t)k[7]); 734 c += ((uint32_t)k[8])<<24; 735 c += ((uint32_t)k[9])<<16; 736 c += ((uint32_t)k[10])<<8; 737 c += ((uint32_t)k[11]); 738 mix(a,b,c); 739 length -= 12; 740 k += 12; 741 } 742 743 /*-------------------------------- last block: affect all 32 bits of (c) */ 744 switch(length) /* all the case statements fall through */ 745 { 746 case 12: c+=k[11]; 747 case 11: c+=((uint32_t)k[10])<<8; 748 case 10: c+=((uint32_t)k[9])<<16; 749 case 9 : c+=((uint32_t)k[8])<<24; 750 case 8 : b+=k[7]; 751 case 7 : b+=((uint32_t)k[6])<<8; 752 case 6 : b+=((uint32_t)k[5])<<16; 753 case 5 : b+=((uint32_t)k[4])<<24; 754 case 4 : a+=k[3]; 755 case 3 : a+=((uint32_t)k[2])<<8; 756 case 2 : a+=((uint32_t)k[1])<<16; 757 case 1 : a+=((uint32_t)k[0])<<24; 758 break; 759 case 0 : return c; 760 } 761 } 762 763 final(a,b,c); 764 return c; 765 } 766 767 768 #ifdef SELF_TEST 769 770 /* used for timings */ 771 void driver1() 772 { 773 uint8_t buf[256]; 774 uint32_t i; 775 uint32_t h=0; 776 time_t a,z; 777 778 time(&a); 779 for (i=0; i<256; ++i) buf[i] = 'x'; 780 for (i=0; i<1; ++i) 781 { 782 h = hashlittle(&buf[0],1,h); 783 } 784 time(&z); 785 if (z-a > 0) printf("time %d %.8x\n", z-a, h); 786 } 787 788 /* check that every input bit changes every output bit half the time */ 789 #define HASHSTATE 1 790 #define HASHLEN 1 791 #define MAXPAIR 60 792 #define MAXLEN 70 793 void driver2() 794 { 795 uint8_t qa[MAXLEN+1], qb[MAXLEN+2], *a = &qa[0], *b = &qb[1]; 796 uint32_t c[HASHSTATE], d[HASHSTATE], i=0, j=0, k, l, m=0, z; 797 uint32_t e[HASHSTATE],f[HASHSTATE],g[HASHSTATE],h[HASHSTATE]; 798 uint32_t x[HASHSTATE],y[HASHSTATE]; 799 uint32_t hlen; 800 801 printf("No more than %d trials should ever be needed \n",MAXPAIR/2); 802 for (hlen=0; hlen < MAXLEN; ++hlen) 803 { 804 z=0; 805 for (i=0; i<hlen; ++i) /*----------------------- for each input byte, */ 806 { 807 for (j=0; j<8; ++j) /*------------------------ for each input bit, */ 808 { 809 for (m=1; m<8; ++m) /*------------ for serveral possible initvals, */ 810 { 811 for (l=0; l<HASHSTATE; ++l) 812 e[l]=f[l]=g[l]=h[l]=x[l]=y[l]=~((uint32_t)0); 813 814 /*---- check that every output bit is affected by that input bit */ 815 for (k=0; k<MAXPAIR; k+=2) 816 { 817 uint32_t finished=1; 818 /* keys have one bit different */ 819 for (l=0; l<hlen+1; ++l) {a[l] = b[l] = (uint8_t)0;} 820 /* have a and b be two keys differing in only one bit */ 821 a[i] ^= (k<<j); 822 a[i] ^= (k>>(8-j)); 823 c[0] = hashlittle(a, hlen, m); 824 b[i] ^= ((k+1)<<j); 825 b[i] ^= ((k+1)>>(8-j)); 826 d[0] = hashlittle(b, hlen, m); 827 /* check every bit is 1, 0, set, and not set at least once */ 828 for (l=0; l<HASHSTATE; ++l) 829 { 830 e[l] &= (c[l]^d[l]); 831 f[l] &= ~(c[l]^d[l]); 832 g[l] &= c[l]; 833 h[l] &= ~c[l]; 834 x[l] &= d[l]; 835 y[l] &= ~d[l]; 836 if (e[l]|f[l]|g[l]|h[l]|x[l]|y[l]) finished=0; 837 } 838 if (finished) break; 839 } 840 if (k>z) z=k; 841 if (k==MAXPAIR) 842 { 843 printf("Some bit didn't change: "); 844 printf("%.8x %.8x %.8x %.8x %.8x %.8x ", 845 e[0],f[0],g[0],h[0],x[0],y[0]); 846 printf("i %d j %d m %d len %d\n", i, j, m, hlen); 847 } 848 if (z==MAXPAIR) goto done; 849 } 850 } 851 } 852 done: 853 if (z < MAXPAIR) 854 { 855 printf("Mix success %2d bytes %2d initvals ",i,m); 856 printf("required %d trials\n", z/2); 857 } 858 } 859 printf("\n"); 860 } 861 862 /* Check for reading beyond the end of the buffer and alignment problems */ 863 void driver3() 864 { 865 uint8_t buf[MAXLEN+20], *b; 866 uint32_t len; 867 uint8_t q[] = "This is the time for all good men to come to the aid of their country..."; 868 uint32_t h; 869 uint8_t qq[] = "xThis is the time for all good men to come to the aid of their country..."; 870 uint32_t i; 871 uint8_t qqq[] = "xxThis is the time for all good men to come to the aid of their country..."; 872 uint32_t j; 873 uint8_t qqqq[] = "xxxThis is the time for all good men to come to the aid of their country..."; 874 uint32_t ref,x,y; 875 uint8_t *p; 876 877 printf("Endianness. These lines should all be the same (for values filled in):\n"); 878 printf("%.8x %.8x %.8x\n", 879 hashword((const uint32_t *)q, (sizeof(q)-1)/4, 13), 880 hashword((const uint32_t *)q, (sizeof(q)-5)/4, 13), 881 hashword((const uint32_t *)q, (sizeof(q)-9)/4, 13)); 882 p = q; 883 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n", 884 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13), 885 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13), 886 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13), 887 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13), 888 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13), 889 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13)); 890 p = &qq[1]; 891 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n", 892 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13), 893 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13), 894 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13), 895 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13), 896 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13), 897 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13)); 898 p = &qqq[2]; 899 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n", 900 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13), 901 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13), 902 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13), 903 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13), 904 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13), 905 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13)); 906 p = &qqqq[3]; 907 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n", 908 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13), 909 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13), 910 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13), 911 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13), 912 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13), 913 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13)); 914 printf("\n"); 915 916 /* check that hashlittle2 and hashlittle produce the same results */ 917 i=47; j=0; 918 hashlittle2(q, sizeof(q), &i, &j); 919 if (hashlittle(q, sizeof(q), 47) != i) 920 printf("hashlittle2 and hashlittle mismatch\n"); 921 922 /* check that hashword2 and hashword produce the same results */ 923 len = 0xdeadbeef; 924 i=47, j=0; 925 hashword2(&len, 1, &i, &j); 926 if (hashword(&len, 1, 47) != i) 927 printf("hashword2 and hashword mismatch %x %x\n", 928 i, hashword(&len, 1, 47)); 929 930 /* check hashlittle doesn't read before or after the ends of the string */ 931 for (h=0, b=buf+1; h<8; ++h, ++b) 932 { 933 for (i=0; i<MAXLEN; ++i) 934 { 935 len = i; 936 for (j=0; j<i; ++j) *(b+j)=0; 937 938 /* these should all be equal */ 939 ref = hashlittle(b, len, (uint32_t)1); 940 *(b+i)=(uint8_t)~0; 941 *(b-1)=(uint8_t)~0; 942 x = hashlittle(b, len, (uint32_t)1); 943 y = hashlittle(b, len, (uint32_t)1); 944 if ((ref != x) || (ref != y)) 945 { 946 printf("alignment error: %.8x %.8x %.8x %d %d\n",ref,x,y, 947 h, i); 948 } 949 } 950 } 951 } 952 953 /* check for problems with nulls */ 954 void driver4() 955 { 956 uint8_t buf[1]; 957 uint32_t h,i,state[HASHSTATE]; 958 959 960 buf[0] = ~0; 961 for (i=0; i<HASHSTATE; ++i) state[i] = 1; 962 printf("These should all be different\n"); 963 for (i=0, h=0; i<8; ++i) 964 { 965 h = hashlittle(buf, 0, h); 966 printf("%2ld 0-byte strings, hash is %.8x\n", i, h); 967 } 968 } 969 970 void driver5() 971 { 972 uint32_t b,c; 973 b=0, c=0, hashlittle2("", 0, &c, &b); 974 printf("hash is %.8lx %.8lx\n", c, b); /* deadbeef deadbeef */ 975 b=0xdeadbeef, c=0, hashlittle2("", 0, &c, &b); 976 printf("hash is %.8lx %.8lx\n", c, b); /* bd5b7dde deadbeef */ 977 b=0xdeadbeef, c=0xdeadbeef, hashlittle2("", 0, &c, &b); 978 printf("hash is %.8lx %.8lx\n", c, b); /* 9c093ccd bd5b7dde */ 979 b=0, c=0, hashlittle2("Four score and seven years ago", 30, &c, &b); 980 printf("hash is %.8lx %.8lx\n", c, b); /* 17770551 ce7226e6 */ 981 b=1, c=0, hashlittle2("Four score and seven years ago", 30, &c, &b); 982 printf("hash is %.8lx %.8lx\n", c, b); /* e3607cae bd371de4 */ 983 b=0, c=1, hashlittle2("Four score and seven years ago", 30, &c, &b); 984 printf("hash is %.8lx %.8lx\n", c, b); /* cd628161 6cbea4b3 */ 985 c = hashlittle("Four score and seven years ago", 30, 0); 986 printf("hash is %.8lx\n", c); /* 17770551 */ 987 c = hashlittle("Four score and seven years ago", 30, 1); 988 printf("hash is %.8lx\n", c); /* cd628161 */ 989 } 990 991 992 int main() 993 { 994 driver1(); /* test that the key is hashed: used for timings */ 995 driver2(); /* test that whole key is hashed thoroughly */ 996 driver3(); /* test that nothing but the key is hashed */ 997 driver4(); /* test hashing multiple buffers (all buffers are null) */ 998 driver5(); /* test the hash against known vectors */ 999 return 1; 1000 } 1001 1002 #endif /* SELF_TEST */ 1003
