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