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