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