1238106Sdes/* 2249141Sdes February 2013(Wouter) patch defines for BSD endianness, from Brad Smith. 3238106Sdes January 2012(Wouter) added randomised initial value, fallout from 28c3. 4238106Sdes March 2007(Wouter) adapted from lookup3.c original, add config.h include. 5238106Sdes added #ifdef VALGRIND to remove 298,384,660 'unused variable k8' warnings. 6238106Sdes added include of lookup3.h to check definitions match declarations. 7238106Sdes removed include of stdint - config.h takes care of platform independence. 8238106Sdes url http://burtleburtle.net/bob/hash/index.html. 9238106Sdes*/ 10238106Sdes/* 11238106Sdes------------------------------------------------------------------------------- 12238106Sdeslookup3.c, by Bob Jenkins, May 2006, Public Domain. 13238106Sdes 14238106SdesThese are functions for producing 32-bit hashes for hash table lookup. 15238106Sdeshashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final() 16238106Sdesare externally useful functions. Routines to test the hash are included 17238106Sdesif SELF_TEST is defined. You can use this free for any purpose. It's in 18238106Sdesthe public domain. It has no warranty. 19238106Sdes 20238106SdesYou probably want to use hashlittle(). hashlittle() and hashbig() 21238106Sdeshash byte arrays. hashlittle() is is faster than hashbig() on 22238106Sdeslittle-endian machines. Intel and AMD are little-endian machines. 23238106SdesOn second thought, you probably want hashlittle2(), which is identical to 24238106Sdeshashlittle() except it returns two 32-bit hashes for the price of one. 25238106SdesYou could implement hashbig2() if you wanted but I haven't bothered here. 26238106Sdes 27238106SdesIf you want to find a hash of, say, exactly 7 integers, do 28238106Sdes a = i1; b = i2; c = i3; 29238106Sdes mix(a,b,c); 30238106Sdes a += i4; b += i5; c += i6; 31238106Sdes mix(a,b,c); 32238106Sdes a += i7; 33238106Sdes final(a,b,c); 34238106Sdesthen use c as the hash value. If you have a variable length array of 35238106Sdes4-byte integers to hash, use hashword(). If you have a byte array (like 36238106Sdesa character string), use hashlittle(). If you have several byte arrays, or 37238106Sdesa mix of things, see the comments above hashlittle(). 38238106Sdes 39238106SdesWhy is this so big? I read 12 bytes at a time into 3 4-byte integers, 40238106Sdesthen mix those integers. This is fast (you can do a lot more thorough 41238106Sdesmixing with 12*3 instructions on 3 integers than you can with 3 instructions 42238106Sdeson 1 byte), but shoehorning those bytes into integers efficiently is messy. 43238106Sdes------------------------------------------------------------------------------- 44238106Sdes*/ 45238106Sdes/*#define SELF_TEST 1*/ 46238106Sdes 47238106Sdes#include "config.h" 48238106Sdes#include "util/storage/lookup3.h" 49238106Sdes#include <stdio.h> /* defines printf for tests */ 50238106Sdes#include <time.h> /* defines time_t for timings in the test */ 51238106Sdes/*#include <stdint.h> defines uint32_t etc (from config.h) */ 52238106Sdes#include <sys/param.h> /* attempt to define endianness */ 53269257Sdes#ifdef HAVE_SYS_TYPES_H 54269257Sdes# include <sys/types.h> /* attempt to define endianness (solaris) */ 55269257Sdes#endif 56285206Sdes#if defined(linux) || defined(__OpenBSD__) 57285206Sdes# ifdef HAVE_ENDIAN_H 58285206Sdes# include <endian.h> /* attempt to define endianness */ 59285206Sdes# else 60285206Sdes# include <machine/endian.h> /* on older OpenBSD */ 61285206Sdes# endif 62238106Sdes#endif 63249141Sdes#if defined(__FreeBSD__) || defined(__NetBSD__) || defined(__DragonFly__) 64249141Sdes#include <sys/endian.h> /* attempt to define endianness */ 65249141Sdes#endif 66238106Sdes 67238106Sdes/* random initial value */ 68269257Sdesstatic uint32_t raninit = (uint32_t)0xdeadbeef; 69238106Sdes 70238106Sdesvoid 71238106Sdeshash_set_raninit(uint32_t v) 72238106Sdes{ 73238106Sdes raninit = v; 74238106Sdes} 75238106Sdes 76238106Sdes/* 77238106Sdes * My best guess at if you are big-endian or little-endian. This may 78238106Sdes * need adjustment. 79238106Sdes */ 80238106Sdes#if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \ 81238106Sdes __BYTE_ORDER == __LITTLE_ENDIAN) || \ 82238106Sdes (defined(i386) || defined(__i386__) || defined(__i486__) || \ 83269257Sdes defined(__i586__) || defined(__i686__) || defined(vax) || defined(MIPSEL) || defined(__x86)) 84238106Sdes# define HASH_LITTLE_ENDIAN 1 85238106Sdes# define HASH_BIG_ENDIAN 0 86238106Sdes#elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \ 87238106Sdes __BYTE_ORDER == __BIG_ENDIAN) || \ 88269257Sdes (defined(sparc) || defined(__sparc) || defined(__sparc__) || defined(POWERPC) || defined(mc68000) || defined(sel)) 89238106Sdes# define HASH_LITTLE_ENDIAN 0 90238106Sdes# define HASH_BIG_ENDIAN 1 91269257Sdes#elif defined(_MACHINE_ENDIAN_H_) 92269257Sdes/* test for machine_endian_h protects failure if some are empty strings */ 93269257Sdes# if defined(_BYTE_ORDER) && defined(_BIG_ENDIAN) && _BYTE_ORDER == _BIG_ENDIAN 94269257Sdes# define HASH_LITTLE_ENDIAN 0 95269257Sdes# define HASH_BIG_ENDIAN 1 96269257Sdes# endif 97269257Sdes# if defined(_BYTE_ORDER) && defined(_LITTLE_ENDIAN) && _BYTE_ORDER == _LITTLE_ENDIAN 98269257Sdes# define HASH_LITTLE_ENDIAN 1 99269257Sdes# define HASH_BIG_ENDIAN 0 100269257Sdes# endif /* _MACHINE_ENDIAN_H_ */ 101238106Sdes#else 102238106Sdes# define HASH_LITTLE_ENDIAN 0 103238106Sdes# define HASH_BIG_ENDIAN 0 104238106Sdes#endif 105238106Sdes 106238106Sdes#define hashsize(n) ((uint32_t)1<<(n)) 107238106Sdes#define hashmask(n) (hashsize(n)-1) 108238106Sdes#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) 109238106Sdes 110238106Sdes/* 111238106Sdes------------------------------------------------------------------------------- 112238106Sdesmix -- mix 3 32-bit values reversibly. 113238106Sdes 114238106SdesThis is reversible, so any information in (a,b,c) before mix() is 115238106Sdesstill in (a,b,c) after mix(). 116238106Sdes 117238106SdesIf four pairs of (a,b,c) inputs are run through mix(), or through 118238106Sdesmix() in reverse, there are at least 32 bits of the output that 119238106Sdesare sometimes the same for one pair and different for another pair. 120238106SdesThis was tested for: 121238106Sdes* pairs that differed by one bit, by two bits, in any combination 122238106Sdes of top bits of (a,b,c), or in any combination of bottom bits of 123238106Sdes (a,b,c). 124238106Sdes* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed 125238106Sdes the output delta to a Gray code (a^(a>>1)) so a string of 1's (as 126238106Sdes is commonly produced by subtraction) look like a single 1-bit 127238106Sdes difference. 128238106Sdes* the base values were pseudorandom, all zero but one bit set, or 129238106Sdes all zero plus a counter that starts at zero. 130238106Sdes 131238106SdesSome k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that 132238106Sdessatisfy this are 133238106Sdes 4 6 8 16 19 4 134238106Sdes 9 15 3 18 27 15 135238106Sdes 14 9 3 7 17 3 136238106SdesWell, "9 15 3 18 27 15" didn't quite get 32 bits diffing 137238106Sdesfor "differ" defined as + with a one-bit base and a two-bit delta. I 138238106Sdesused http://burtleburtle.net/bob/hash/avalanche.html to choose 139238106Sdesthe operations, constants, and arrangements of the variables. 140238106Sdes 141238106SdesThis does not achieve avalanche. There are input bits of (a,b,c) 142238106Sdesthat fail to affect some output bits of (a,b,c), especially of a. The 143238106Sdesmost thoroughly mixed value is c, but it doesn't really even achieve 144238106Sdesavalanche in c. 145238106Sdes 146238106SdesThis allows some parallelism. Read-after-writes are good at doubling 147238106Sdesthe number of bits affected, so the goal of mixing pulls in the opposite 148238106Sdesdirection as the goal of parallelism. I did what I could. Rotates 149238106Sdesseem to cost as much as shifts on every machine I could lay my hands 150238106Sdeson, and rotates are much kinder to the top and bottom bits, so I used 151238106Sdesrotates. 152238106Sdes------------------------------------------------------------------------------- 153238106Sdes*/ 154238106Sdes#define mix(a,b,c) \ 155238106Sdes{ \ 156238106Sdes a -= c; a ^= rot(c, 4); c += b; \ 157238106Sdes b -= a; b ^= rot(a, 6); a += c; \ 158238106Sdes c -= b; c ^= rot(b, 8); b += a; \ 159238106Sdes a -= c; a ^= rot(c,16); c += b; \ 160238106Sdes b -= a; b ^= rot(a,19); a += c; \ 161238106Sdes c -= b; c ^= rot(b, 4); b += a; \ 162238106Sdes} 163238106Sdes 164238106Sdes/* 165238106Sdes------------------------------------------------------------------------------- 166238106Sdesfinal -- final mixing of 3 32-bit values (a,b,c) into c 167238106Sdes 168238106SdesPairs of (a,b,c) values differing in only a few bits will usually 169238106Sdesproduce values of c that look totally different. This was tested for 170238106Sdes* pairs that differed by one bit, by two bits, in any combination 171238106Sdes of top bits of (a,b,c), or in any combination of bottom bits of 172238106Sdes (a,b,c). 173238106Sdes* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed 174238106Sdes the output delta to a Gray code (a^(a>>1)) so a string of 1's (as 175238106Sdes is commonly produced by subtraction) look like a single 1-bit 176238106Sdes difference. 177238106Sdes* the base values were pseudorandom, all zero but one bit set, or 178238106Sdes all zero plus a counter that starts at zero. 179238106Sdes 180238106SdesThese constants passed: 181238106Sdes 14 11 25 16 4 14 24 182238106Sdes 12 14 25 16 4 14 24 183238106Sdesand these came close: 184238106Sdes 4 8 15 26 3 22 24 185238106Sdes 10 8 15 26 3 22 24 186238106Sdes 11 8 15 26 3 22 24 187238106Sdes------------------------------------------------------------------------------- 188238106Sdes*/ 189238106Sdes#define final(a,b,c) \ 190238106Sdes{ \ 191238106Sdes c ^= b; c -= rot(b,14); \ 192238106Sdes a ^= c; a -= rot(c,11); \ 193238106Sdes b ^= a; b -= rot(a,25); \ 194238106Sdes c ^= b; c -= rot(b,16); \ 195238106Sdes a ^= c; a -= rot(c,4); \ 196238106Sdes b ^= a; b -= rot(a,14); \ 197238106Sdes c ^= b; c -= rot(b,24); \ 198238106Sdes} 199238106Sdes 200238106Sdes/* 201238106Sdes-------------------------------------------------------------------- 202238106Sdes This works on all machines. To be useful, it requires 203238106Sdes -- that the key be an array of uint32_t's, and 204238106Sdes -- that the length be the number of uint32_t's in the key 205238106Sdes 206238106Sdes The function hashword() is identical to hashlittle() on little-endian 207238106Sdes machines, and identical to hashbig() on big-endian machines, 208238106Sdes except that the length has to be measured in uint32_ts rather than in 209238106Sdes bytes. hashlittle() is more complicated than hashword() only because 210238106Sdes hashlittle() has to dance around fitting the key bytes into registers. 211238106Sdes-------------------------------------------------------------------- 212238106Sdes*/ 213238106Sdesuint32_t hashword( 214238106Sdesconst uint32_t *k, /* the key, an array of uint32_t values */ 215238106Sdessize_t length, /* the length of the key, in uint32_ts */ 216238106Sdesuint32_t initval) /* the previous hash, or an arbitrary value */ 217238106Sdes{ 218238106Sdes uint32_t a,b,c; 219238106Sdes 220238106Sdes /* Set up the internal state */ 221238106Sdes a = b = c = raninit + (((uint32_t)length)<<2) + initval; 222238106Sdes 223238106Sdes /*------------------------------------------------- handle most of the key */ 224238106Sdes while (length > 3) 225238106Sdes { 226238106Sdes a += k[0]; 227238106Sdes b += k[1]; 228238106Sdes c += k[2]; 229238106Sdes mix(a,b,c); 230238106Sdes length -= 3; 231238106Sdes k += 3; 232238106Sdes } 233238106Sdes 234238106Sdes /*------------------------------------------- handle the last 3 uint32_t's */ 235238106Sdes switch(length) /* all the case statements fall through */ 236238106Sdes { 237238106Sdes case 3 : c+=k[2]; 238238106Sdes case 2 : b+=k[1]; 239238106Sdes case 1 : a+=k[0]; 240238106Sdes final(a,b,c); 241238106Sdes case 0: /* case 0: nothing left to add */ 242238106Sdes break; 243238106Sdes } 244238106Sdes /*------------------------------------------------------ report the result */ 245238106Sdes return c; 246238106Sdes} 247238106Sdes 248238106Sdes 249238106Sdes#ifdef SELF_TEST 250238106Sdes 251238106Sdes/* 252238106Sdes-------------------------------------------------------------------- 253238106Sdeshashword2() -- same as hashword(), but take two seeds and return two 254238106Sdes32-bit values. pc and pb must both be nonnull, and *pc and *pb must 255238106Sdesboth be initialized with seeds. If you pass in (*pb)==0, the output 256238106Sdes(*pc) will be the same as the return value from hashword(). 257238106Sdes-------------------------------------------------------------------- 258238106Sdes*/ 259238106Sdesvoid hashword2 ( 260238106Sdesconst uint32_t *k, /* the key, an array of uint32_t values */ 261238106Sdessize_t length, /* the length of the key, in uint32_ts */ 262238106Sdesuint32_t *pc, /* IN: seed OUT: primary hash value */ 263238106Sdesuint32_t *pb) /* IN: more seed OUT: secondary hash value */ 264238106Sdes{ 265238106Sdes uint32_t a,b,c; 266238106Sdes 267238106Sdes /* Set up the internal state */ 268238106Sdes a = b = c = raninit + ((uint32_t)(length<<2)) + *pc; 269238106Sdes c += *pb; 270238106Sdes 271238106Sdes /*------------------------------------------------- handle most of the key */ 272238106Sdes while (length > 3) 273238106Sdes { 274238106Sdes a += k[0]; 275238106Sdes b += k[1]; 276238106Sdes c += k[2]; 277238106Sdes mix(a,b,c); 278238106Sdes length -= 3; 279238106Sdes k += 3; 280238106Sdes } 281238106Sdes 282238106Sdes /*------------------------------------------- handle the last 3 uint32_t's */ 283238106Sdes switch(length) /* all the case statements fall through */ 284238106Sdes { 285238106Sdes case 3 : c+=k[2]; 286238106Sdes case 2 : b+=k[1]; 287238106Sdes case 1 : a+=k[0]; 288238106Sdes final(a,b,c); 289238106Sdes case 0: /* case 0: nothing left to add */ 290238106Sdes break; 291238106Sdes } 292238106Sdes /*------------------------------------------------------ report the result */ 293238106Sdes *pc=c; *pb=b; 294238106Sdes} 295238106Sdes 296238106Sdes#endif /* SELF_TEST */ 297238106Sdes 298238106Sdes/* 299238106Sdes------------------------------------------------------------------------------- 300238106Sdeshashlittle() -- hash a variable-length key into a 32-bit value 301238106Sdes k : the key (the unaligned variable-length array of bytes) 302238106Sdes length : the length of the key, counting by bytes 303238106Sdes initval : can be any 4-byte value 304238106SdesReturns a 32-bit value. Every bit of the key affects every bit of 305238106Sdesthe return value. Two keys differing by one or two bits will have 306238106Sdestotally different hash values. 307238106Sdes 308238106SdesThe best hash table sizes are powers of 2. There is no need to do 309238106Sdesmod a prime (mod is sooo slow!). If you need less than 32 bits, 310238106Sdesuse a bitmask. For example, if you need only 10 bits, do 311238106Sdes h = (h & hashmask(10)); 312238106SdesIn which case, the hash table should have hashsize(10) elements. 313238106Sdes 314238106SdesIf you are hashing n strings (uint8_t **)k, do it like this: 315238106Sdes for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h); 316238106Sdes 317238106SdesBy Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this 318238106Sdescode any way you wish, private, educational, or commercial. It's free. 319238106Sdes 320238106SdesUse for hash table lookup, or anything where one collision in 2^^32 is 321238106Sdesacceptable. Do NOT use for cryptographic purposes. 322238106Sdes------------------------------------------------------------------------------- 323238106Sdes*/ 324238106Sdes 325238106Sdesuint32_t hashlittle( const void *key, size_t length, uint32_t initval) 326238106Sdes{ 327238106Sdes uint32_t a,b,c; /* internal state */ 328238106Sdes union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */ 329238106Sdes 330238106Sdes /* Set up the internal state */ 331238106Sdes a = b = c = raninit + ((uint32_t)length) + initval; 332238106Sdes 333238106Sdes u.ptr = key; 334238106Sdes if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) { 335238106Sdes const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ 336238106Sdes#ifdef VALGRIND 337238106Sdes const uint8_t *k8; 338238106Sdes#endif 339238106Sdes 340238106Sdes /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ 341238106Sdes while (length > 12) 342238106Sdes { 343238106Sdes a += k[0]; 344238106Sdes b += k[1]; 345238106Sdes c += k[2]; 346238106Sdes mix(a,b,c); 347238106Sdes length -= 12; 348238106Sdes k += 3; 349238106Sdes } 350238106Sdes 351238106Sdes /*----------------------------- handle the last (probably partial) block */ 352238106Sdes /* 353238106Sdes * "k[2]&0xffffff" actually reads beyond the end of the string, but 354238106Sdes * then masks off the part it's not allowed to read. Because the 355238106Sdes * string is aligned, the masked-off tail is in the same word as the 356238106Sdes * rest of the string. Every machine with memory protection I've seen 357238106Sdes * does it on word boundaries, so is OK with this. But VALGRIND will 358238106Sdes * still catch it and complain. The masking trick does make the hash 359294190Sdes * noticeably faster for short strings (like English words). 360238106Sdes */ 361238106Sdes#ifndef VALGRIND 362238106Sdes 363238106Sdes switch(length) 364238106Sdes { 365238106Sdes case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; 366238106Sdes case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break; 367238106Sdes case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break; 368238106Sdes case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break; 369238106Sdes case 8 : b+=k[1]; a+=k[0]; break; 370238106Sdes case 7 : b+=k[1]&0xffffff; a+=k[0]; break; 371238106Sdes case 6 : b+=k[1]&0xffff; a+=k[0]; break; 372238106Sdes case 5 : b+=k[1]&0xff; a+=k[0]; break; 373238106Sdes case 4 : a+=k[0]; break; 374238106Sdes case 3 : a+=k[0]&0xffffff; break; 375238106Sdes case 2 : a+=k[0]&0xffff; break; 376238106Sdes case 1 : a+=k[0]&0xff; break; 377238106Sdes case 0 : return c; /* zero length strings require no mixing */ 378238106Sdes } 379238106Sdes 380238106Sdes#else /* make valgrind happy */ 381238106Sdes 382238106Sdes k8 = (const uint8_t *)k; 383238106Sdes switch(length) 384238106Sdes { 385238106Sdes case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; 386238106Sdes case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ 387238106Sdes case 10: c+=((uint32_t)k8[9])<<8; /* fall through */ 388238106Sdes case 9 : c+=k8[8]; /* fall through */ 389238106Sdes case 8 : b+=k[1]; a+=k[0]; break; 390238106Sdes case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ 391238106Sdes case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */ 392238106Sdes case 5 : b+=k8[4]; /* fall through */ 393238106Sdes case 4 : a+=k[0]; break; 394238106Sdes case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ 395238106Sdes case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */ 396238106Sdes case 1 : a+=k8[0]; break; 397238106Sdes case 0 : return c; 398238106Sdes } 399238106Sdes 400238106Sdes#endif /* !valgrind */ 401238106Sdes 402238106Sdes } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) { 403238106Sdes const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */ 404238106Sdes const uint8_t *k8; 405238106Sdes 406238106Sdes /*--------------- all but last block: aligned reads and different mixing */ 407238106Sdes while (length > 12) 408238106Sdes { 409238106Sdes a += k[0] + (((uint32_t)k[1])<<16); 410238106Sdes b += k[2] + (((uint32_t)k[3])<<16); 411238106Sdes c += k[4] + (((uint32_t)k[5])<<16); 412238106Sdes mix(a,b,c); 413238106Sdes length -= 12; 414238106Sdes k += 6; 415238106Sdes } 416238106Sdes 417238106Sdes /*----------------------------- handle the last (probably partial) block */ 418238106Sdes k8 = (const uint8_t *)k; 419238106Sdes switch(length) 420238106Sdes { 421238106Sdes case 12: c+=k[4]+(((uint32_t)k[5])<<16); 422238106Sdes b+=k[2]+(((uint32_t)k[3])<<16); 423238106Sdes a+=k[0]+(((uint32_t)k[1])<<16); 424238106Sdes break; 425238106Sdes case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ 426238106Sdes case 10: c+=k[4]; 427238106Sdes b+=k[2]+(((uint32_t)k[3])<<16); 428238106Sdes a+=k[0]+(((uint32_t)k[1])<<16); 429238106Sdes break; 430238106Sdes case 9 : c+=k8[8]; /* fall through */ 431238106Sdes case 8 : b+=k[2]+(((uint32_t)k[3])<<16); 432238106Sdes a+=k[0]+(((uint32_t)k[1])<<16); 433238106Sdes break; 434238106Sdes case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ 435238106Sdes case 6 : b+=k[2]; 436238106Sdes a+=k[0]+(((uint32_t)k[1])<<16); 437238106Sdes break; 438238106Sdes case 5 : b+=k8[4]; /* fall through */ 439238106Sdes case 4 : a+=k[0]+(((uint32_t)k[1])<<16); 440238106Sdes break; 441238106Sdes case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ 442238106Sdes case 2 : a+=k[0]; 443238106Sdes break; 444238106Sdes case 1 : a+=k8[0]; 445238106Sdes break; 446238106Sdes case 0 : return c; /* zero length requires no mixing */ 447238106Sdes } 448238106Sdes 449238106Sdes } else { /* need to read the key one byte at a time */ 450238106Sdes const uint8_t *k = (const uint8_t *)key; 451238106Sdes 452238106Sdes /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ 453238106Sdes while (length > 12) 454238106Sdes { 455238106Sdes a += k[0]; 456238106Sdes a += ((uint32_t)k[1])<<8; 457238106Sdes a += ((uint32_t)k[2])<<16; 458238106Sdes a += ((uint32_t)k[3])<<24; 459238106Sdes b += k[4]; 460238106Sdes b += ((uint32_t)k[5])<<8; 461238106Sdes b += ((uint32_t)k[6])<<16; 462238106Sdes b += ((uint32_t)k[7])<<24; 463238106Sdes c += k[8]; 464238106Sdes c += ((uint32_t)k[9])<<8; 465238106Sdes c += ((uint32_t)k[10])<<16; 466238106Sdes c += ((uint32_t)k[11])<<24; 467238106Sdes mix(a,b,c); 468238106Sdes length -= 12; 469238106Sdes k += 12; 470238106Sdes } 471238106Sdes 472238106Sdes /*-------------------------------- last block: affect all 32 bits of (c) */ 473238106Sdes switch(length) /* all the case statements fall through */ 474238106Sdes { 475238106Sdes case 12: c+=((uint32_t)k[11])<<24; 476238106Sdes case 11: c+=((uint32_t)k[10])<<16; 477238106Sdes case 10: c+=((uint32_t)k[9])<<8; 478238106Sdes case 9 : c+=k[8]; 479238106Sdes case 8 : b+=((uint32_t)k[7])<<24; 480238106Sdes case 7 : b+=((uint32_t)k[6])<<16; 481238106Sdes case 6 : b+=((uint32_t)k[5])<<8; 482238106Sdes case 5 : b+=k[4]; 483238106Sdes case 4 : a+=((uint32_t)k[3])<<24; 484238106Sdes case 3 : a+=((uint32_t)k[2])<<16; 485238106Sdes case 2 : a+=((uint32_t)k[1])<<8; 486238106Sdes case 1 : a+=k[0]; 487238106Sdes break; 488238106Sdes case 0 : return c; 489238106Sdes } 490238106Sdes } 491238106Sdes 492238106Sdes final(a,b,c); 493238106Sdes return c; 494238106Sdes} 495238106Sdes 496238106Sdes#ifdef SELF_TEST 497238106Sdes 498238106Sdes/* 499238106Sdes * hashlittle2: return 2 32-bit hash values 500238106Sdes * 501238106Sdes * This is identical to hashlittle(), except it returns two 32-bit hash 502238106Sdes * values instead of just one. This is good enough for hash table 503238106Sdes * lookup with 2^^64 buckets, or if you want a second hash if you're not 504238106Sdes * happy with the first, or if you want a probably-unique 64-bit ID for 505238106Sdes * the key. *pc is better mixed than *pb, so use *pc first. If you want 506238106Sdes * a 64-bit value do something like "*pc + (((uint64_t)*pb)<<32)". 507238106Sdes */ 508238106Sdesvoid hashlittle2( 509238106Sdes const void *key, /* the key to hash */ 510238106Sdes size_t length, /* length of the key */ 511238106Sdes uint32_t *pc, /* IN: primary initval, OUT: primary hash */ 512238106Sdes uint32_t *pb) /* IN: secondary initval, OUT: secondary hash */ 513238106Sdes{ 514238106Sdes uint32_t a,b,c; /* internal state */ 515238106Sdes union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */ 516238106Sdes 517238106Sdes /* Set up the internal state */ 518238106Sdes a = b = c = raninit + ((uint32_t)length) + *pc; 519238106Sdes c += *pb; 520238106Sdes 521238106Sdes u.ptr = key; 522238106Sdes if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) { 523238106Sdes const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ 524238106Sdes#ifdef VALGRIND 525238106Sdes const uint8_t *k8; 526238106Sdes#endif 527238106Sdes 528238106Sdes /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ 529238106Sdes while (length > 12) 530238106Sdes { 531238106Sdes a += k[0]; 532238106Sdes b += k[1]; 533238106Sdes c += k[2]; 534238106Sdes mix(a,b,c); 535238106Sdes length -= 12; 536238106Sdes k += 3; 537238106Sdes } 538238106Sdes 539238106Sdes /*----------------------------- handle the last (probably partial) block */ 540238106Sdes /* 541238106Sdes * "k[2]&0xffffff" actually reads beyond the end of the string, but 542238106Sdes * then masks off the part it's not allowed to read. Because the 543238106Sdes * string is aligned, the masked-off tail is in the same word as the 544238106Sdes * rest of the string. Every machine with memory protection I've seen 545238106Sdes * does it on word boundaries, so is OK with this. But VALGRIND will 546238106Sdes * still catch it and complain. The masking trick does make the hash 547294190Sdes * noticeably faster for short strings (like English words). 548238106Sdes */ 549238106Sdes#ifndef VALGRIND 550238106Sdes 551238106Sdes switch(length) 552238106Sdes { 553238106Sdes case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; 554238106Sdes case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break; 555238106Sdes case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break; 556238106Sdes case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break; 557238106Sdes case 8 : b+=k[1]; a+=k[0]; break; 558238106Sdes case 7 : b+=k[1]&0xffffff; a+=k[0]; break; 559238106Sdes case 6 : b+=k[1]&0xffff; a+=k[0]; break; 560238106Sdes case 5 : b+=k[1]&0xff; a+=k[0]; break; 561238106Sdes case 4 : a+=k[0]; break; 562238106Sdes case 3 : a+=k[0]&0xffffff; break; 563238106Sdes case 2 : a+=k[0]&0xffff; break; 564238106Sdes case 1 : a+=k[0]&0xff; break; 565238106Sdes case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */ 566238106Sdes } 567238106Sdes 568238106Sdes#else /* make valgrind happy */ 569238106Sdes 570238106Sdes k8 = (const uint8_t *)k; 571238106Sdes switch(length) 572238106Sdes { 573238106Sdes case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; 574238106Sdes case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ 575238106Sdes case 10: c+=((uint32_t)k8[9])<<8; /* fall through */ 576238106Sdes case 9 : c+=k8[8]; /* fall through */ 577238106Sdes case 8 : b+=k[1]; a+=k[0]; break; 578238106Sdes case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ 579238106Sdes case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */ 580238106Sdes case 5 : b+=k8[4]; /* fall through */ 581238106Sdes case 4 : a+=k[0]; break; 582238106Sdes case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ 583238106Sdes case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */ 584238106Sdes case 1 : a+=k8[0]; break; 585238106Sdes case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */ 586238106Sdes } 587238106Sdes 588238106Sdes#endif /* !valgrind */ 589238106Sdes 590238106Sdes } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) { 591238106Sdes const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */ 592238106Sdes const uint8_t *k8; 593238106Sdes 594238106Sdes /*--------------- all but last block: aligned reads and different mixing */ 595238106Sdes while (length > 12) 596238106Sdes { 597238106Sdes a += k[0] + (((uint32_t)k[1])<<16); 598238106Sdes b += k[2] + (((uint32_t)k[3])<<16); 599238106Sdes c += k[4] + (((uint32_t)k[5])<<16); 600238106Sdes mix(a,b,c); 601238106Sdes length -= 12; 602238106Sdes k += 6; 603238106Sdes } 604238106Sdes 605238106Sdes /*----------------------------- handle the last (probably partial) block */ 606238106Sdes k8 = (const uint8_t *)k; 607238106Sdes switch(length) 608238106Sdes { 609238106Sdes case 12: c+=k[4]+(((uint32_t)k[5])<<16); 610238106Sdes b+=k[2]+(((uint32_t)k[3])<<16); 611238106Sdes a+=k[0]+(((uint32_t)k[1])<<16); 612238106Sdes break; 613238106Sdes case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ 614238106Sdes case 10: c+=k[4]; 615238106Sdes b+=k[2]+(((uint32_t)k[3])<<16); 616238106Sdes a+=k[0]+(((uint32_t)k[1])<<16); 617238106Sdes break; 618238106Sdes case 9 : c+=k8[8]; /* fall through */ 619238106Sdes case 8 : b+=k[2]+(((uint32_t)k[3])<<16); 620238106Sdes a+=k[0]+(((uint32_t)k[1])<<16); 621238106Sdes break; 622238106Sdes case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ 623238106Sdes case 6 : b+=k[2]; 624238106Sdes a+=k[0]+(((uint32_t)k[1])<<16); 625238106Sdes break; 626238106Sdes case 5 : b+=k8[4]; /* fall through */ 627238106Sdes case 4 : a+=k[0]+(((uint32_t)k[1])<<16); 628238106Sdes break; 629238106Sdes case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ 630238106Sdes case 2 : a+=k[0]; 631238106Sdes break; 632238106Sdes case 1 : a+=k8[0]; 633238106Sdes break; 634238106Sdes case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */ 635238106Sdes } 636238106Sdes 637238106Sdes } else { /* need to read the key one byte at a time */ 638238106Sdes const uint8_t *k = (const uint8_t *)key; 639238106Sdes 640238106Sdes /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ 641238106Sdes while (length > 12) 642238106Sdes { 643238106Sdes a += k[0]; 644238106Sdes a += ((uint32_t)k[1])<<8; 645238106Sdes a += ((uint32_t)k[2])<<16; 646238106Sdes a += ((uint32_t)k[3])<<24; 647238106Sdes b += k[4]; 648238106Sdes b += ((uint32_t)k[5])<<8; 649238106Sdes b += ((uint32_t)k[6])<<16; 650238106Sdes b += ((uint32_t)k[7])<<24; 651238106Sdes c += k[8]; 652238106Sdes c += ((uint32_t)k[9])<<8; 653238106Sdes c += ((uint32_t)k[10])<<16; 654238106Sdes c += ((uint32_t)k[11])<<24; 655238106Sdes mix(a,b,c); 656238106Sdes length -= 12; 657238106Sdes k += 12; 658238106Sdes } 659238106Sdes 660238106Sdes /*-------------------------------- last block: affect all 32 bits of (c) */ 661238106Sdes switch(length) /* all the case statements fall through */ 662238106Sdes { 663238106Sdes case 12: c+=((uint32_t)k[11])<<24; 664238106Sdes case 11: c+=((uint32_t)k[10])<<16; 665238106Sdes case 10: c+=((uint32_t)k[9])<<8; 666238106Sdes case 9 : c+=k[8]; 667238106Sdes case 8 : b+=((uint32_t)k[7])<<24; 668238106Sdes case 7 : b+=((uint32_t)k[6])<<16; 669238106Sdes case 6 : b+=((uint32_t)k[5])<<8; 670238106Sdes case 5 : b+=k[4]; 671238106Sdes case 4 : a+=((uint32_t)k[3])<<24; 672238106Sdes case 3 : a+=((uint32_t)k[2])<<16; 673238106Sdes case 2 : a+=((uint32_t)k[1])<<8; 674238106Sdes case 1 : a+=k[0]; 675238106Sdes break; 676238106Sdes case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */ 677238106Sdes } 678238106Sdes } 679238106Sdes 680238106Sdes final(a,b,c); 681238106Sdes *pc=c; *pb=b; 682238106Sdes} 683238106Sdes 684238106Sdes#endif /* SELF_TEST */ 685238106Sdes 686238106Sdes#if 0 /* currently not used */ 687238106Sdes 688238106Sdes/* 689238106Sdes * hashbig(): 690238106Sdes * This is the same as hashword() on big-endian machines. It is different 691238106Sdes * from hashlittle() on all machines. hashbig() takes advantage of 692238106Sdes * big-endian byte ordering. 693238106Sdes */ 694238106Sdesuint32_t hashbig( const void *key, size_t length, uint32_t initval) 695238106Sdes{ 696238106Sdes uint32_t a,b,c; 697238106Sdes union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */ 698238106Sdes 699238106Sdes /* Set up the internal state */ 700238106Sdes a = b = c = raninit + ((uint32_t)length) + initval; 701238106Sdes 702238106Sdes u.ptr = key; 703238106Sdes if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) { 704238106Sdes const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ 705238106Sdes#ifdef VALGRIND 706238106Sdes const uint8_t *k8; 707238106Sdes#endif 708238106Sdes 709238106Sdes /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ 710238106Sdes while (length > 12) 711238106Sdes { 712238106Sdes a += k[0]; 713238106Sdes b += k[1]; 714238106Sdes c += k[2]; 715238106Sdes mix(a,b,c); 716238106Sdes length -= 12; 717238106Sdes k += 3; 718238106Sdes } 719238106Sdes 720238106Sdes /*----------------------------- handle the last (probably partial) block */ 721238106Sdes /* 722238106Sdes * "k[2]<<8" actually reads beyond the end of the string, but 723238106Sdes * then shifts out the part it's not allowed to read. Because the 724238106Sdes * string is aligned, the illegal read is in the same word as the 725238106Sdes * rest of the string. Every machine with memory protection I've seen 726238106Sdes * does it on word boundaries, so is OK with this. But VALGRIND will 727238106Sdes * still catch it and complain. The masking trick does make the hash 728294190Sdes * noticeably faster for short strings (like English words). 729238106Sdes */ 730238106Sdes#ifndef VALGRIND 731238106Sdes 732238106Sdes switch(length) 733238106Sdes { 734238106Sdes case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; 735238106Sdes case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break; 736238106Sdes case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break; 737238106Sdes case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break; 738238106Sdes case 8 : b+=k[1]; a+=k[0]; break; 739238106Sdes case 7 : b+=k[1]&0xffffff00; a+=k[0]; break; 740238106Sdes case 6 : b+=k[1]&0xffff0000; a+=k[0]; break; 741238106Sdes case 5 : b+=k[1]&0xff000000; a+=k[0]; break; 742238106Sdes case 4 : a+=k[0]; break; 743238106Sdes case 3 : a+=k[0]&0xffffff00; break; 744238106Sdes case 2 : a+=k[0]&0xffff0000; break; 745238106Sdes case 1 : a+=k[0]&0xff000000; break; 746238106Sdes case 0 : return c; /* zero length strings require no mixing */ 747238106Sdes } 748238106Sdes 749238106Sdes#else /* make valgrind happy */ 750238106Sdes 751238106Sdes k8 = (const uint8_t *)k; 752238106Sdes switch(length) /* all the case statements fall through */ 753238106Sdes { 754238106Sdes case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; 755238106Sdes case 11: c+=((uint32_t)k8[10])<<8; /* fall through */ 756238106Sdes case 10: c+=((uint32_t)k8[9])<<16; /* fall through */ 757238106Sdes case 9 : c+=((uint32_t)k8[8])<<24; /* fall through */ 758238106Sdes case 8 : b+=k[1]; a+=k[0]; break; 759238106Sdes case 7 : b+=((uint32_t)k8[6])<<8; /* fall through */ 760238106Sdes case 6 : b+=((uint32_t)k8[5])<<16; /* fall through */ 761238106Sdes case 5 : b+=((uint32_t)k8[4])<<24; /* fall through */ 762238106Sdes case 4 : a+=k[0]; break; 763238106Sdes case 3 : a+=((uint32_t)k8[2])<<8; /* fall through */ 764238106Sdes case 2 : a+=((uint32_t)k8[1])<<16; /* fall through */ 765238106Sdes case 1 : a+=((uint32_t)k8[0])<<24; break; 766238106Sdes case 0 : return c; 767238106Sdes } 768238106Sdes 769238106Sdes#endif /* !VALGRIND */ 770238106Sdes 771238106Sdes } else { /* need to read the key one byte at a time */ 772238106Sdes const uint8_t *k = (const uint8_t *)key; 773238106Sdes 774238106Sdes /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ 775238106Sdes while (length > 12) 776238106Sdes { 777238106Sdes a += ((uint32_t)k[0])<<24; 778238106Sdes a += ((uint32_t)k[1])<<16; 779238106Sdes a += ((uint32_t)k[2])<<8; 780238106Sdes a += ((uint32_t)k[3]); 781238106Sdes b += ((uint32_t)k[4])<<24; 782238106Sdes b += ((uint32_t)k[5])<<16; 783238106Sdes b += ((uint32_t)k[6])<<8; 784238106Sdes b += ((uint32_t)k[7]); 785238106Sdes c += ((uint32_t)k[8])<<24; 786238106Sdes c += ((uint32_t)k[9])<<16; 787238106Sdes c += ((uint32_t)k[10])<<8; 788238106Sdes c += ((uint32_t)k[11]); 789238106Sdes mix(a,b,c); 790238106Sdes length -= 12; 791238106Sdes k += 12; 792238106Sdes } 793238106Sdes 794238106Sdes /*-------------------------------- last block: affect all 32 bits of (c) */ 795238106Sdes switch(length) /* all the case statements fall through */ 796238106Sdes { 797238106Sdes case 12: c+=k[11]; 798238106Sdes case 11: c+=((uint32_t)k[10])<<8; 799238106Sdes case 10: c+=((uint32_t)k[9])<<16; 800238106Sdes case 9 : c+=((uint32_t)k[8])<<24; 801238106Sdes case 8 : b+=k[7]; 802238106Sdes case 7 : b+=((uint32_t)k[6])<<8; 803238106Sdes case 6 : b+=((uint32_t)k[5])<<16; 804238106Sdes case 5 : b+=((uint32_t)k[4])<<24; 805238106Sdes case 4 : a+=k[3]; 806238106Sdes case 3 : a+=((uint32_t)k[2])<<8; 807238106Sdes case 2 : a+=((uint32_t)k[1])<<16; 808238106Sdes case 1 : a+=((uint32_t)k[0])<<24; 809238106Sdes break; 810238106Sdes case 0 : return c; 811238106Sdes } 812238106Sdes } 813238106Sdes 814238106Sdes final(a,b,c); 815238106Sdes return c; 816238106Sdes} 817238106Sdes 818238106Sdes#endif /* 0 == currently not used */ 819238106Sdes 820238106Sdes#ifdef SELF_TEST 821238106Sdes 822238106Sdes/* used for timings */ 823238106Sdesvoid driver1() 824238106Sdes{ 825238106Sdes uint8_t buf[256]; 826238106Sdes uint32_t i; 827238106Sdes uint32_t h=0; 828238106Sdes time_t a,z; 829238106Sdes 830238106Sdes time(&a); 831238106Sdes for (i=0; i<256; ++i) buf[i] = 'x'; 832238106Sdes for (i=0; i<1; ++i) 833238106Sdes { 834238106Sdes h = hashlittle(&buf[0],1,h); 835238106Sdes } 836238106Sdes time(&z); 837238106Sdes if (z-a > 0) printf("time %d %.8x\n", z-a, h); 838238106Sdes} 839238106Sdes 840238106Sdes/* check that every input bit changes every output bit half the time */ 841238106Sdes#define HASHSTATE 1 842238106Sdes#define HASHLEN 1 843238106Sdes#define MAXPAIR 60 844238106Sdes#define MAXLEN 70 845238106Sdesvoid driver2() 846238106Sdes{ 847238106Sdes uint8_t qa[MAXLEN+1], qb[MAXLEN+2], *a = &qa[0], *b = &qb[1]; 848238106Sdes uint32_t c[HASHSTATE], d[HASHSTATE], i=0, j=0, k, l, m=0, z; 849238106Sdes uint32_t e[HASHSTATE],f[HASHSTATE],g[HASHSTATE],h[HASHSTATE]; 850238106Sdes uint32_t x[HASHSTATE],y[HASHSTATE]; 851238106Sdes uint32_t hlen; 852238106Sdes 853238106Sdes printf("No more than %d trials should ever be needed \n",MAXPAIR/2); 854238106Sdes for (hlen=0; hlen < MAXLEN; ++hlen) 855238106Sdes { 856238106Sdes z=0; 857238106Sdes for (i=0; i<hlen; ++i) /*----------------------- for each input byte, */ 858238106Sdes { 859238106Sdes for (j=0; j<8; ++j) /*------------------------ for each input bit, */ 860238106Sdes { 861294190Sdes for (m=1; m<8; ++m) /*------------ for several possible initvals, */ 862238106Sdes { 863238106Sdes for (l=0; l<HASHSTATE; ++l) 864238106Sdes e[l]=f[l]=g[l]=h[l]=x[l]=y[l]=~((uint32_t)0); 865238106Sdes 866238106Sdes /*---- check that every output bit is affected by that input bit */ 867238106Sdes for (k=0; k<MAXPAIR; k+=2) 868238106Sdes { 869238106Sdes uint32_t finished=1; 870238106Sdes /* keys have one bit different */ 871238106Sdes for (l=0; l<hlen+1; ++l) {a[l] = b[l] = (uint8_t)0;} 872238106Sdes /* have a and b be two keys differing in only one bit */ 873238106Sdes a[i] ^= (k<<j); 874238106Sdes a[i] ^= (k>>(8-j)); 875238106Sdes c[0] = hashlittle(a, hlen, m); 876238106Sdes b[i] ^= ((k+1)<<j); 877238106Sdes b[i] ^= ((k+1)>>(8-j)); 878238106Sdes d[0] = hashlittle(b, hlen, m); 879238106Sdes /* check every bit is 1, 0, set, and not set at least once */ 880238106Sdes for (l=0; l<HASHSTATE; ++l) 881238106Sdes { 882238106Sdes e[l] &= (c[l]^d[l]); 883238106Sdes f[l] &= ~(c[l]^d[l]); 884238106Sdes g[l] &= c[l]; 885238106Sdes h[l] &= ~c[l]; 886238106Sdes x[l] &= d[l]; 887238106Sdes y[l] &= ~d[l]; 888238106Sdes if (e[l]|f[l]|g[l]|h[l]|x[l]|y[l]) finished=0; 889238106Sdes } 890238106Sdes if (finished) break; 891238106Sdes } 892238106Sdes if (k>z) z=k; 893238106Sdes if (k==MAXPAIR) 894238106Sdes { 895238106Sdes printf("Some bit didn't change: "); 896238106Sdes printf("%.8x %.8x %.8x %.8x %.8x %.8x ", 897238106Sdes e[0],f[0],g[0],h[0],x[0],y[0]); 898238106Sdes printf("i %d j %d m %d len %d\n", i, j, m, hlen); 899238106Sdes } 900238106Sdes if (z==MAXPAIR) goto done; 901238106Sdes } 902238106Sdes } 903238106Sdes } 904238106Sdes done: 905238106Sdes if (z < MAXPAIR) 906238106Sdes { 907238106Sdes printf("Mix success %2d bytes %2d initvals ",i,m); 908238106Sdes printf("required %d trials\n", z/2); 909238106Sdes } 910238106Sdes } 911238106Sdes printf("\n"); 912238106Sdes} 913238106Sdes 914238106Sdes/* Check for reading beyond the end of the buffer and alignment problems */ 915238106Sdesvoid driver3() 916238106Sdes{ 917238106Sdes uint8_t buf[MAXLEN+20], *b; 918238106Sdes uint32_t len; 919238106Sdes uint8_t q[] = "This is the time for all good men to come to the aid of their country..."; 920238106Sdes uint32_t h; 921238106Sdes uint8_t qq[] = "xThis is the time for all good men to come to the aid of their country..."; 922238106Sdes uint32_t i; 923238106Sdes uint8_t qqq[] = "xxThis is the time for all good men to come to the aid of their country..."; 924238106Sdes uint32_t j; 925238106Sdes uint8_t qqqq[] = "xxxThis is the time for all good men to come to the aid of their country..."; 926238106Sdes uint32_t ref,x,y; 927238106Sdes uint8_t *p; 928238106Sdes 929238106Sdes printf("Endianness. These lines should all be the same (for values filled in):\n"); 930238106Sdes printf("%.8x %.8x %.8x\n", 931238106Sdes hashword((const uint32_t *)q, (sizeof(q)-1)/4, 13), 932238106Sdes hashword((const uint32_t *)q, (sizeof(q)-5)/4, 13), 933238106Sdes hashword((const uint32_t *)q, (sizeof(q)-9)/4, 13)); 934238106Sdes p = q; 935238106Sdes printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n", 936238106Sdes hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13), 937238106Sdes hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13), 938238106Sdes hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13), 939238106Sdes hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13), 940238106Sdes hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13), 941238106Sdes hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13)); 942238106Sdes p = &qq[1]; 943238106Sdes printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n", 944238106Sdes hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13), 945238106Sdes hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13), 946238106Sdes hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13), 947238106Sdes hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13), 948238106Sdes hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13), 949238106Sdes hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13)); 950238106Sdes p = &qqq[2]; 951238106Sdes printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n", 952238106Sdes hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13), 953238106Sdes hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13), 954238106Sdes hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13), 955238106Sdes hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13), 956238106Sdes hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13), 957238106Sdes hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13)); 958238106Sdes p = &qqqq[3]; 959238106Sdes printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n", 960238106Sdes hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13), 961238106Sdes hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13), 962238106Sdes hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13), 963238106Sdes hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13), 964238106Sdes hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13), 965238106Sdes hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13)); 966238106Sdes printf("\n"); 967238106Sdes 968238106Sdes /* check that hashlittle2 and hashlittle produce the same results */ 969238106Sdes i=47; j=0; 970238106Sdes hashlittle2(q, sizeof(q), &i, &j); 971238106Sdes if (hashlittle(q, sizeof(q), 47) != i) 972238106Sdes printf("hashlittle2 and hashlittle mismatch\n"); 973238106Sdes 974238106Sdes /* check that hashword2 and hashword produce the same results */ 975238106Sdes len = raninit; 976238106Sdes i=47, j=0; 977238106Sdes hashword2(&len, 1, &i, &j); 978238106Sdes if (hashword(&len, 1, 47) != i) 979238106Sdes printf("hashword2 and hashword mismatch %x %x\n", 980238106Sdes i, hashword(&len, 1, 47)); 981238106Sdes 982238106Sdes /* check hashlittle doesn't read before or after the ends of the string */ 983238106Sdes for (h=0, b=buf+1; h<8; ++h, ++b) 984238106Sdes { 985238106Sdes for (i=0; i<MAXLEN; ++i) 986238106Sdes { 987238106Sdes len = i; 988238106Sdes for (j=0; j<i; ++j) *(b+j)=0; 989238106Sdes 990238106Sdes /* these should all be equal */ 991238106Sdes ref = hashlittle(b, len, (uint32_t)1); 992238106Sdes *(b+i)=(uint8_t)~0; 993238106Sdes *(b-1)=(uint8_t)~0; 994238106Sdes x = hashlittle(b, len, (uint32_t)1); 995238106Sdes y = hashlittle(b, len, (uint32_t)1); 996238106Sdes if ((ref != x) || (ref != y)) 997238106Sdes { 998238106Sdes printf("alignment error: %.8x %.8x %.8x %d %d\n",ref,x,y, 999238106Sdes h, i); 1000238106Sdes } 1001238106Sdes } 1002238106Sdes } 1003238106Sdes} 1004238106Sdes 1005238106Sdes/* check for problems with nulls */ 1006238106Sdes void driver4() 1007238106Sdes{ 1008238106Sdes uint8_t buf[1]; 1009238106Sdes uint32_t h,i,state[HASHSTATE]; 1010238106Sdes 1011238106Sdes 1012238106Sdes buf[0] = ~0; 1013238106Sdes for (i=0; i<HASHSTATE; ++i) state[i] = 1; 1014238106Sdes printf("These should all be different\n"); 1015238106Sdes for (i=0, h=0; i<8; ++i) 1016238106Sdes { 1017238106Sdes h = hashlittle(buf, 0, h); 1018238106Sdes printf("%2ld 0-byte strings, hash is %.8x\n", i, h); 1019238106Sdes } 1020238106Sdes} 1021238106Sdes 1022238106Sdes 1023238106Sdesint main() 1024238106Sdes{ 1025238106Sdes driver1(); /* test that the key is hashed: used for timings */ 1026238106Sdes driver2(); /* test that whole key is hashed thoroughly */ 1027238106Sdes driver3(); /* test that nothing but the key is hashed */ 1028238106Sdes driver4(); /* test hashing multiple buffers (all buffers are null) */ 1029238106Sdes return 1; 1030238106Sdes} 1031238106Sdes 1032238106Sdes#endif /* SELF_TEST */ 1033