1266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand/* 2266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand------------------------------------------------------------------------------- 3266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandlookup3.c, by Bob Jenkins, May 2006, Public Domain. 4266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 5266dde27811b78f466702295ba0173b8d8be5adaRom LemarchandThese are functions for producing 32-bit hashes for hash table lookup. 6266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandhashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final() 7266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandare externally useful functions. Routines to test the hash are included 8266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandif SELF_TEST is defined. You can use this free for any purpose. It's in 9266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandthe public domain. It has no warranty. 10266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 11266dde27811b78f466702295ba0173b8d8be5adaRom LemarchandYou probably want to use hashlittle(). hashlittle() and hashbig() 12266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandhash byte arrays. hashlittle() is is faster than hashbig() on 13266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandlittle-endian machines. Intel and AMD are little-endian machines. 14266dde27811b78f466702295ba0173b8d8be5adaRom LemarchandOn second thought, you probably want hashlittle2(), which is identical to 15266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandhashlittle() except it returns two 32-bit hashes for the price of one. 16266dde27811b78f466702295ba0173b8d8be5adaRom LemarchandYou could implement hashbig2() if you wanted but I haven't bothered here. 17266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 18266dde27811b78f466702295ba0173b8d8be5adaRom LemarchandIf you want to find a hash of, say, exactly 7 integers, do 19266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a = i1; b = i2; c = i3; 20266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand mix(a,b,c); 21266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a += i4; b += i5; c += i6; 22266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand mix(a,b,c); 23266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a += i7; 24266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand final(a,b,c); 25266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandthen use c as the hash value. If you have a variable length array of 26266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand4-byte integers to hash, use hashword(). If you have a byte array (like 27266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchanda character string), use hashlittle(). If you have several byte arrays, or 28266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchanda mix of things, see the comments above hashlittle(). 29266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 30266dde27811b78f466702295ba0173b8d8be5adaRom LemarchandWhy is this so big? I read 12 bytes at a time into 3 4-byte integers, 31266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandthen mix those integers. This is fast (you can do a lot more thorough 32266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandmixing with 12*3 instructions on 3 integers than you can with 3 instructions 33266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandon 1 byte), but shoehorning those bytes into integers efficiently is messy. 34266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand------------------------------------------------------------------------------- 35266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand*/ 36266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#define SELF_TEST 1 37266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#undef SELF_TEST 38266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 39266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#include <stdio.h> /* defines printf for tests */ 40266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#include <time.h> /* defines time_t for timings in the test */ 41266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#include <stdint.h> /* defines uint32_t etc */ 42266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#include <sys/param.h> /* attempt to define endianness */ 43266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#ifdef linux 44266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand# include <endian.h> /* attempt to define endianness */ 45266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#endif 46266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 47266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand/* 48266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * My best guess at if you are big-endian or little-endian. This may 49266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * need adjustment. 50266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand */ 51266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \ 52266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand __BYTE_ORDER == __LITTLE_ENDIAN) || \ 53266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand (defined(i386) || defined(__i386__) || defined(__i486__) || \ 54266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand defined(__i586__) || defined(__i686__) || defined(vax) || defined(MIPSEL)) 55266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand# define HASH_LITTLE_ENDIAN 1 56266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand# define HASH_BIG_ENDIAN 0 57266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \ 58266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand __BYTE_ORDER == __BIG_ENDIAN) || \ 59266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand (defined(sparc) || defined(POWERPC) || defined(mc68000) || defined(sel)) 60266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand# define HASH_LITTLE_ENDIAN 0 61266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand# define HASH_BIG_ENDIAN 1 62266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#else 63266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand# define HASH_LITTLE_ENDIAN 0 64266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand# define HASH_BIG_ENDIAN 0 65266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#endif 66266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 67266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#define hashsize(n) ((uint32_t)1<<(n)) 68266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#define hashmask(n) (hashsize(n)-1) 69266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) 70266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 71266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand/* 72266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand------------------------------------------------------------------------------- 73266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandmix -- mix 3 32-bit values reversibly. 74266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 75266dde27811b78f466702295ba0173b8d8be5adaRom LemarchandThis is reversible, so any information in (a,b,c) before mix() is 76266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandstill in (a,b,c) after mix(). 77266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 78266dde27811b78f466702295ba0173b8d8be5adaRom LemarchandIf four pairs of (a,b,c) inputs are run through mix(), or through 79266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandmix() in reverse, there are at least 32 bits of the output that 80266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandare sometimes the same for one pair and different for another pair. 81266dde27811b78f466702295ba0173b8d8be5adaRom LemarchandThis was tested for: 82266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand* pairs that differed by one bit, by two bits, in any combination 83266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand of top bits of (a,b,c), or in any combination of bottom bits of 84266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand (a,b,c). 85266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed 86266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand the output delta to a Gray code (a^(a>>1)) so a string of 1's (as 87266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand is commonly produced by subtraction) look like a single 1-bit 88266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand difference. 89266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand* the base values were pseudorandom, all zero but one bit set, or 90266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand all zero plus a counter that starts at zero. 91266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 92266dde27811b78f466702295ba0173b8d8be5adaRom LemarchandSome k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that 93266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandsatisfy this are 94266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 4 6 8 16 19 4 95266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 9 15 3 18 27 15 96266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 14 9 3 7 17 3 97266dde27811b78f466702295ba0173b8d8be5adaRom LemarchandWell, "9 15 3 18 27 15" didn't quite get 32 bits diffing 98266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandfor "differ" defined as + with a one-bit base and a two-bit delta. I 99266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandused http://burtleburtle.net/bob/hash/avalanche.html to choose 100266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandthe operations, constants, and arrangements of the variables. 101266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 102266dde27811b78f466702295ba0173b8d8be5adaRom LemarchandThis does not achieve avalanche. There are input bits of (a,b,c) 103266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandthat fail to affect some output bits of (a,b,c), especially of a. The 104266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandmost thoroughly mixed value is c, but it doesn't really even achieve 105266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandavalanche in c. 106266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 107266dde27811b78f466702295ba0173b8d8be5adaRom LemarchandThis allows some parallelism. Read-after-writes are good at doubling 108266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandthe number of bits affected, so the goal of mixing pulls in the opposite 109266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchanddirection as the goal of parallelism. I did what I could. Rotates 110266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandseem to cost as much as shifts on every machine I could lay my hands 111266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandon, and rotates are much kinder to the top and bottom bits, so I used 112266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandrotates. 113266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand------------------------------------------------------------------------------- 114266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand*/ 115266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#define mix(a,b,c) \ 116266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand{ \ 117266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a -= c; a ^= rot(c, 4); c += b; \ 118266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b -= a; b ^= rot(a, 6); a += c; \ 119266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c -= b; c ^= rot(b, 8); b += a; \ 120266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a -= c; a ^= rot(c,16); c += b; \ 121266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b -= a; b ^= rot(a,19); a += c; \ 122266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c -= b; c ^= rot(b, 4); b += a; \ 123266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand} 124266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 125266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand/* 126266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand------------------------------------------------------------------------------- 127266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandfinal -- final mixing of 3 32-bit values (a,b,c) into c 128266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 129266dde27811b78f466702295ba0173b8d8be5adaRom LemarchandPairs of (a,b,c) values differing in only a few bits will usually 130266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandproduce values of c that look totally different. This was tested for 131266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand* pairs that differed by one bit, by two bits, in any combination 132266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand of top bits of (a,b,c), or in any combination of bottom bits of 133266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand (a,b,c). 134266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed 135266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand the output delta to a Gray code (a^(a>>1)) so a string of 1's (as 136266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand is commonly produced by subtraction) look like a single 1-bit 137266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand difference. 138266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand* the base values were pseudorandom, all zero but one bit set, or 139266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand all zero plus a counter that starts at zero. 140266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 141266dde27811b78f466702295ba0173b8d8be5adaRom LemarchandThese constants passed: 142266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 14 11 25 16 4 14 24 143266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 12 14 25 16 4 14 24 144266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandand these came close: 145266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 4 8 15 26 3 22 24 146266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 10 8 15 26 3 22 24 147266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 11 8 15 26 3 22 24 148266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand------------------------------------------------------------------------------- 149266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand*/ 150266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#define final(a,b,c) \ 151266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand{ \ 152266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c ^= b; c -= rot(b,14); \ 153266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a ^= c; a -= rot(c,11); \ 154266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b ^= a; b -= rot(a,25); \ 155266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c ^= b; c -= rot(b,16); \ 156266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a ^= c; a -= rot(c,4); \ 157266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b ^= a; b -= rot(a,14); \ 158266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c ^= b; c -= rot(b,24); \ 159266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand} 160266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 161266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand/* 162266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand-------------------------------------------------------------------- 163266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand This works on all machines. To be useful, it requires 164266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand -- that the key be an array of uint32_t's, and 165266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand -- that the length be the number of uint32_t's in the key 166266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 167266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand The function hashword() is identical to hashlittle() on little-endian 168266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand machines, and identical to hashbig() on big-endian machines, 169266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand except that the length has to be measured in uint32_ts rather than in 170266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand bytes. hashlittle() is more complicated than hashword() only because 171266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashlittle() has to dance around fitting the key bytes into registers. 172266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand-------------------------------------------------------------------- 173266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand*/ 174266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchanduint32_t hashword( 175266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandconst uint32_t *k, /* the key, an array of uint32_t values */ 176266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandsize_t length, /* the length of the key, in uint32_ts */ 177266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchanduint32_t initval) /* the previous hash, or an arbitrary value */ 178266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand{ 179266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint32_t a,b,c; 180266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 181266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /* Set up the internal state */ 182266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval; 183266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 184266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /*------------------------------------------------- handle most of the key */ 185266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand while (length > 3) 186266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 187266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a += k[0]; 188266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b += k[1]; 189266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c += k[2]; 190266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand mix(a,b,c); 191266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand length -= 3; 192266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand k += 3; 193266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 194266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 195266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /*------------------------------------------- handle the last 3 uint32_t's */ 196266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand switch(length) /* all the case statements fall through */ 197266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 198266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 3 : c+=k[2]; 199266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 2 : b+=k[1]; 200266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 1 : a+=k[0]; 201266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand final(a,b,c); 202266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 0: /* case 0: nothing left to add */ 203266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand break; 204266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 205266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /*------------------------------------------------------ report the result */ 206266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand return c; 207266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand} 208266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 209266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 210266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand/* 211266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand-------------------------------------------------------------------- 212266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandhashword2() -- same as hashword(), but take two seeds and return two 213266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand32-bit values. pc and pb must both be nonnull, and *pc and *pb must 214266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandboth be initialized with seeds. If you pass in (*pb)==0, the output 215266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand(*pc) will be the same as the return value from hashword(). 216266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand-------------------------------------------------------------------- 217266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand*/ 218266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandvoid hashword2 ( 219266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandconst uint32_t *k, /* the key, an array of uint32_t values */ 220266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandsize_t length, /* the length of the key, in uint32_ts */ 221266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchanduint32_t *pc, /* IN: seed OUT: primary hash value */ 222266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchanduint32_t *pb) /* IN: more seed OUT: secondary hash value */ 223266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand{ 224266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint32_t a,b,c; 225266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 226266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /* Set up the internal state */ 227266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a = b = c = 0xdeadbeef + ((uint32_t)(length<<2)) + *pc; 228266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c += *pb; 229266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 230266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /*------------------------------------------------- handle most of the key */ 231266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand while (length > 3) 232266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 233266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a += k[0]; 234266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b += k[1]; 235266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c += k[2]; 236266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand mix(a,b,c); 237266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand length -= 3; 238266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand k += 3; 239266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 240266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 241266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /*------------------------------------------- handle the last 3 uint32_t's */ 242266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand switch(length) /* all the case statements fall through */ 243266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 244266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 3 : c+=k[2]; 245266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 2 : b+=k[1]; 246266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 1 : a+=k[0]; 247266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand final(a,b,c); 248266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 0: /* case 0: nothing left to add */ 249266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand break; 250266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 251266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /*------------------------------------------------------ report the result */ 252266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand *pc=c; *pb=b; 253266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand} 254266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 255266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 256266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand/* 257266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand------------------------------------------------------------------------------- 258266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandhashlittle() -- hash a variable-length key into a 32-bit value 259266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand k : the key (the unaligned variable-length array of bytes) 260266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand length : the length of the key, counting by bytes 261266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand initval : can be any 4-byte value 262266dde27811b78f466702295ba0173b8d8be5adaRom LemarchandReturns a 32-bit value. Every bit of the key affects every bit of 263266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandthe return value. Two keys differing by one or two bits will have 264266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandtotally different hash values. 265266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 266266dde27811b78f466702295ba0173b8d8be5adaRom LemarchandThe best hash table sizes are powers of 2. There is no need to do 267266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandmod a prime (mod is sooo slow!). If you need less than 32 bits, 268266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchanduse a bitmask. For example, if you need only 10 bits, do 269266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand h = (h & hashmask(10)); 270266dde27811b78f466702295ba0173b8d8be5adaRom LemarchandIn which case, the hash table should have hashsize(10) elements. 271266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 272266dde27811b78f466702295ba0173b8d8be5adaRom LemarchandIf you are hashing n strings (uint8_t **)k, do it like this: 273266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h); 274266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 275266dde27811b78f466702295ba0173b8d8be5adaRom LemarchandBy Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this 276266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandcode any way you wish, private, educational, or commercial. It's free. 277266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 278266dde27811b78f466702295ba0173b8d8be5adaRom LemarchandUse for hash table lookup, or anything where one collision in 2^^32 is 279266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandacceptable. Do NOT use for cryptographic purposes. 280266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand------------------------------------------------------------------------------- 281266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand*/ 282266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 283266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchanduint32_t hashlittle( const void *key, size_t length, uint32_t initval) 284266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand{ 285266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint32_t a,b,c; /* internal state */ 286266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */ 287266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 288266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /* Set up the internal state */ 289266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a = b = c = 0xdeadbeef + ((uint32_t)length) + initval; 290266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 291266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand u.ptr = key; 292266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) { 293266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ 294266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand const uint8_t *k8; 295266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 296266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ 297266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand while (length > 12) 298266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 299266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a += k[0]; 300266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b += k[1]; 301266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c += k[2]; 302266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand mix(a,b,c); 303266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand length -= 12; 304266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand k += 3; 305266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 306266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 307266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /*----------------------------- handle the last (probably partial) block */ 308266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /* 309266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * "k[2]&0xffffff" actually reads beyond the end of the string, but 310266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * then masks off the part it's not allowed to read. Because the 311266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * string is aligned, the masked-off tail is in the same word as the 312266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * rest of the string. Every machine with memory protection I've seen 313266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * does it on word boundaries, so is OK with this. But VALGRIND will 314266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * still catch it and complain. The masking trick does make the hash 315266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * noticably faster for short strings (like English words). 316266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand */ 317266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#ifndef VALGRIND 318266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 319266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand switch(length) 320266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 321266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; 322266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break; 323266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break; 324266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break; 325266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 8 : b+=k[1]; a+=k[0]; break; 326266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 7 : b+=k[1]&0xffffff; a+=k[0]; break; 327266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 6 : b+=k[1]&0xffff; a+=k[0]; break; 328266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 5 : b+=k[1]&0xff; a+=k[0]; break; 329266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 4 : a+=k[0]; break; 330266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 3 : a+=k[0]&0xffffff; break; 331266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 2 : a+=k[0]&0xffff; break; 332266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 1 : a+=k[0]&0xff; break; 333266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 0 : return c; /* zero length strings require no mixing */ 334266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 335266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 336266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#else /* make valgrind happy */ 337266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 338266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand k8 = (const uint8_t *)k; 339266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand switch(length) 340266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 341266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; 342266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ 343266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 10: c+=((uint32_t)k8[9])<<8; /* fall through */ 344266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 9 : c+=k8[8]; /* fall through */ 345266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 8 : b+=k[1]; a+=k[0]; break; 346266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ 347266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */ 348266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 5 : b+=k8[4]; /* fall through */ 349266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 4 : a+=k[0]; break; 350266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ 351266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */ 352266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 1 : a+=k8[0]; break; 353266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 0 : return c; 354266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 355266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 356266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#endif /* !valgrind */ 357266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 358266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) { 359266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */ 360266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand const uint8_t *k8; 361266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 362266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /*--------------- all but last block: aligned reads and different mixing */ 363266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand while (length > 12) 364266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 365266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a += k[0] + (((uint32_t)k[1])<<16); 366266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b += k[2] + (((uint32_t)k[3])<<16); 367266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c += k[4] + (((uint32_t)k[5])<<16); 368266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand mix(a,b,c); 369266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand length -= 12; 370266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand k += 6; 371266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 372266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 373266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /*----------------------------- handle the last (probably partial) block */ 374266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand k8 = (const uint8_t *)k; 375266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand switch(length) 376266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 377266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 12: c+=k[4]+(((uint32_t)k[5])<<16); 378266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b+=k[2]+(((uint32_t)k[3])<<16); 379266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a+=k[0]+(((uint32_t)k[1])<<16); 380266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand break; 381266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ 382266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 10: c+=k[4]; 383266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b+=k[2]+(((uint32_t)k[3])<<16); 384266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a+=k[0]+(((uint32_t)k[1])<<16); 385266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand break; 386266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 9 : c+=k8[8]; /* fall through */ 387266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 8 : b+=k[2]+(((uint32_t)k[3])<<16); 388266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a+=k[0]+(((uint32_t)k[1])<<16); 389266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand break; 390266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ 391266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 6 : b+=k[2]; 392266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a+=k[0]+(((uint32_t)k[1])<<16); 393266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand break; 394266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 5 : b+=k8[4]; /* fall through */ 395266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 4 : a+=k[0]+(((uint32_t)k[1])<<16); 396266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand break; 397266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ 398266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 2 : a+=k[0]; 399266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand break; 400266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 1 : a+=k8[0]; 401266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand break; 402266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 0 : return c; /* zero length requires no mixing */ 403266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 404266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 405266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } else { /* need to read the key one byte at a time */ 406266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand const uint8_t *k = (const uint8_t *)key; 407266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 408266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ 409266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand while (length > 12) 410266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 411266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a += k[0]; 412266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a += ((uint32_t)k[1])<<8; 413266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a += ((uint32_t)k[2])<<16; 414266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a += ((uint32_t)k[3])<<24; 415266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b += k[4]; 416266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b += ((uint32_t)k[5])<<8; 417266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b += ((uint32_t)k[6])<<16; 418266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b += ((uint32_t)k[7])<<24; 419266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c += k[8]; 420266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c += ((uint32_t)k[9])<<8; 421266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c += ((uint32_t)k[10])<<16; 422266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c += ((uint32_t)k[11])<<24; 423266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand mix(a,b,c); 424266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand length -= 12; 425266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand k += 12; 426266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 427266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 428266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /*-------------------------------- last block: affect all 32 bits of (c) */ 429266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand switch(length) /* all the case statements fall through */ 430266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 431266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 12: c+=((uint32_t)k[11])<<24; 432266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 11: c+=((uint32_t)k[10])<<16; 433266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 10: c+=((uint32_t)k[9])<<8; 434266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 9 : c+=k[8]; 435266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 8 : b+=((uint32_t)k[7])<<24; 436266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 7 : b+=((uint32_t)k[6])<<16; 437266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 6 : b+=((uint32_t)k[5])<<8; 438266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 5 : b+=k[4]; 439266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 4 : a+=((uint32_t)k[3])<<24; 440266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 3 : a+=((uint32_t)k[2])<<16; 441266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 2 : a+=((uint32_t)k[1])<<8; 442266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 1 : a+=k[0]; 443266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand break; 444266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 0 : return c; 445266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 446266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 447266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 448266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand final(a,b,c); 449266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand return c; 450266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand} 451266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 452266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 453266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand/* 454266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * hashlittle2: return 2 32-bit hash values 455266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * 456266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * This is identical to hashlittle(), except it returns two 32-bit hash 457266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * values instead of just one. This is good enough for hash table 458266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * lookup with 2^^64 buckets, or if you want a second hash if you're not 459266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * happy with the first, or if you want a probably-unique 64-bit ID for 460266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * the key. *pc is better mixed than *pb, so use *pc first. If you want 461266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * a 64-bit value do something like "*pc + (((uint64_t)*pb)<<32)". 462266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand */ 463266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandvoid hashlittle2( 464266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand const void *key, /* the key to hash */ 465266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand size_t length, /* length of the key */ 466266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint32_t *pc, /* IN: primary initval, OUT: primary hash */ 467266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint32_t *pb) /* IN: secondary initval, OUT: secondary hash */ 468266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand{ 469266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint32_t a,b,c; /* internal state */ 470266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */ 471266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 472266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /* Set up the internal state */ 473266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a = b = c = 0xdeadbeef + ((uint32_t)length) + *pc; 474266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c += *pb; 475266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 476266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand u.ptr = key; 477266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) { 478266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ 479266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand const uint8_t *k8; 480266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 481266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ 482266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand while (length > 12) 483266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 484266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a += k[0]; 485266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b += k[1]; 486266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c += k[2]; 487266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand mix(a,b,c); 488266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand length -= 12; 489266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand k += 3; 490266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 491266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 492266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /*----------------------------- handle the last (probably partial) block */ 493266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /* 494266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * "k[2]&0xffffff" actually reads beyond the end of the string, but 495266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * then masks off the part it's not allowed to read. Because the 496266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * string is aligned, the masked-off tail is in the same word as the 497266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * rest of the string. Every machine with memory protection I've seen 498266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * does it on word boundaries, so is OK with this. But VALGRIND will 499266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * still catch it and complain. The masking trick does make the hash 500266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * noticably faster for short strings (like English words). 501266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand */ 502266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#ifndef VALGRIND 503266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 504266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand switch(length) 505266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 506266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; 507266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break; 508266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break; 509266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break; 510266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 8 : b+=k[1]; a+=k[0]; break; 511266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 7 : b+=k[1]&0xffffff; a+=k[0]; break; 512266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 6 : b+=k[1]&0xffff; a+=k[0]; break; 513266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 5 : b+=k[1]&0xff; a+=k[0]; break; 514266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 4 : a+=k[0]; break; 515266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 3 : a+=k[0]&0xffffff; break; 516266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 2 : a+=k[0]&0xffff; break; 517266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 1 : a+=k[0]&0xff; break; 518266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */ 519266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 520266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 521266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#else /* make valgrind happy */ 522266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 523266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand k8 = (const uint8_t *)k; 524266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand switch(length) 525266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 526266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; 527266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ 528266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 10: c+=((uint32_t)k8[9])<<8; /* fall through */ 529266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 9 : c+=k8[8]; /* fall through */ 530266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 8 : b+=k[1]; a+=k[0]; break; 531266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ 532266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */ 533266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 5 : b+=k8[4]; /* fall through */ 534266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 4 : a+=k[0]; break; 535266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ 536266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */ 537266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 1 : a+=k8[0]; break; 538266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */ 539266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 540266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 541266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#endif /* !valgrind */ 542266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 543266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) { 544266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */ 545266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand const uint8_t *k8; 546266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 547266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /*--------------- all but last block: aligned reads and different mixing */ 548266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand while (length > 12) 549266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 550266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a += k[0] + (((uint32_t)k[1])<<16); 551266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b += k[2] + (((uint32_t)k[3])<<16); 552266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c += k[4] + (((uint32_t)k[5])<<16); 553266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand mix(a,b,c); 554266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand length -= 12; 555266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand k += 6; 556266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 557266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 558266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /*----------------------------- handle the last (probably partial) block */ 559266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand k8 = (const uint8_t *)k; 560266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand switch(length) 561266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 562266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 12: c+=k[4]+(((uint32_t)k[5])<<16); 563266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b+=k[2]+(((uint32_t)k[3])<<16); 564266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a+=k[0]+(((uint32_t)k[1])<<16); 565266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand break; 566266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ 567266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 10: c+=k[4]; 568266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b+=k[2]+(((uint32_t)k[3])<<16); 569266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a+=k[0]+(((uint32_t)k[1])<<16); 570266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand break; 571266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 9 : c+=k8[8]; /* fall through */ 572266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 8 : b+=k[2]+(((uint32_t)k[3])<<16); 573266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a+=k[0]+(((uint32_t)k[1])<<16); 574266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand break; 575266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ 576266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 6 : b+=k[2]; 577266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a+=k[0]+(((uint32_t)k[1])<<16); 578266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand break; 579266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 5 : b+=k8[4]; /* fall through */ 580266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 4 : a+=k[0]+(((uint32_t)k[1])<<16); 581266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand break; 582266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ 583266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 2 : a+=k[0]; 584266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand break; 585266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 1 : a+=k8[0]; 586266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand break; 587266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */ 588266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 589266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 590266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } else { /* need to read the key one byte at a time */ 591266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand const uint8_t *k = (const uint8_t *)key; 592266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 593266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ 594266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand while (length > 12) 595266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 596266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a += k[0]; 597266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a += ((uint32_t)k[1])<<8; 598266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a += ((uint32_t)k[2])<<16; 599266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a += ((uint32_t)k[3])<<24; 600266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b += k[4]; 601266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b += ((uint32_t)k[5])<<8; 602266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b += ((uint32_t)k[6])<<16; 603266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b += ((uint32_t)k[7])<<24; 604266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c += k[8]; 605266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c += ((uint32_t)k[9])<<8; 606266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c += ((uint32_t)k[10])<<16; 607266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c += ((uint32_t)k[11])<<24; 608266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand mix(a,b,c); 609266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand length -= 12; 610266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand k += 12; 611266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 612266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 613266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /*-------------------------------- last block: affect all 32 bits of (c) */ 614266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand switch(length) /* all the case statements fall through */ 615266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 616266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 12: c+=((uint32_t)k[11])<<24; 617266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 11: c+=((uint32_t)k[10])<<16; 618266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 10: c+=((uint32_t)k[9])<<8; 619266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 9 : c+=k[8]; 620266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 8 : b+=((uint32_t)k[7])<<24; 621266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 7 : b+=((uint32_t)k[6])<<16; 622266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 6 : b+=((uint32_t)k[5])<<8; 623266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 5 : b+=k[4]; 624266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 4 : a+=((uint32_t)k[3])<<24; 625266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 3 : a+=((uint32_t)k[2])<<16; 626266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 2 : a+=((uint32_t)k[1])<<8; 627266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 1 : a+=k[0]; 628266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand break; 629266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */ 630266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 631266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 632266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 633266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand final(a,b,c); 634266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand *pc=c; *pb=b; 635266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand} 636266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 637266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 638266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 639266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand/* 640266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * hashbig(): 641266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * This is the same as hashword() on big-endian machines. It is different 642266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * from hashlittle() on all machines. hashbig() takes advantage of 643266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * big-endian byte ordering. 644266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand */ 645266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchanduint32_t hashbig( const void *key, size_t length, uint32_t initval) 646266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand{ 647266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint32_t a,b,c; 648266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */ 649266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 650266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /* Set up the internal state */ 651266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a = b = c = 0xdeadbeef + ((uint32_t)length) + initval; 652266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 653266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand u.ptr = key; 654266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) { 655266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ 656266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand const uint8_t *k8; 657266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 658266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ 659266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand while (length > 12) 660266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 661266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a += k[0]; 662266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b += k[1]; 663266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c += k[2]; 664266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand mix(a,b,c); 665266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand length -= 12; 666266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand k += 3; 667266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 668266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 669266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /*----------------------------- handle the last (probably partial) block */ 670266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /* 671266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * "k[2]<<8" actually reads beyond the end of the string, but 672266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * then shifts out the part it's not allowed to read. Because the 673266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * string is aligned, the illegal read is in the same word as the 674266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * rest of the string. Every machine with memory protection I've seen 675266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * does it on word boundaries, so is OK with this. But VALGRIND will 676266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * still catch it and complain. The masking trick does make the hash 677266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand * noticably faster for short strings (like English words). 678266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand */ 679266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#ifndef VALGRIND 680266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 681266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand switch(length) 682266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 683266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; 684266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break; 685266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break; 686266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break; 687266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 8 : b+=k[1]; a+=k[0]; break; 688266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 7 : b+=k[1]&0xffffff00; a+=k[0]; break; 689266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 6 : b+=k[1]&0xffff0000; a+=k[0]; break; 690266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 5 : b+=k[1]&0xff000000; a+=k[0]; break; 691266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 4 : a+=k[0]; break; 692266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 3 : a+=k[0]&0xffffff00; break; 693266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 2 : a+=k[0]&0xffff0000; break; 694266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 1 : a+=k[0]&0xff000000; break; 695266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 0 : return c; /* zero length strings require no mixing */ 696266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 697266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 698266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#else /* make valgrind happy */ 699266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 700266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand k8 = (const uint8_t *)k; 701266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand switch(length) /* all the case statements fall through */ 702266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 703266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; 704266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 11: c+=((uint32_t)k8[10])<<8; /* fall through */ 705266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 10: c+=((uint32_t)k8[9])<<16; /* fall through */ 706266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 9 : c+=((uint32_t)k8[8])<<24; /* fall through */ 707266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 8 : b+=k[1]; a+=k[0]; break; 708266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 7 : b+=((uint32_t)k8[6])<<8; /* fall through */ 709266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 6 : b+=((uint32_t)k8[5])<<16; /* fall through */ 710266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 5 : b+=((uint32_t)k8[4])<<24; /* fall through */ 711266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 4 : a+=k[0]; break; 712266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 3 : a+=((uint32_t)k8[2])<<8; /* fall through */ 713266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 2 : a+=((uint32_t)k8[1])<<16; /* fall through */ 714266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 1 : a+=((uint32_t)k8[0])<<24; break; 715266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 0 : return c; 716266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 717266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 718266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#endif /* !VALGRIND */ 719266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 720266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } else { /* need to read the key one byte at a time */ 721266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand const uint8_t *k = (const uint8_t *)key; 722266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 723266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ 724266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand while (length > 12) 725266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 726266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a += ((uint32_t)k[0])<<24; 727266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a += ((uint32_t)k[1])<<16; 728266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a += ((uint32_t)k[2])<<8; 729266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a += ((uint32_t)k[3]); 730266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b += ((uint32_t)k[4])<<24; 731266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b += ((uint32_t)k[5])<<16; 732266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b += ((uint32_t)k[6])<<8; 733266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b += ((uint32_t)k[7]); 734266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c += ((uint32_t)k[8])<<24; 735266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c += ((uint32_t)k[9])<<16; 736266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c += ((uint32_t)k[10])<<8; 737266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c += ((uint32_t)k[11]); 738266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand mix(a,b,c); 739266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand length -= 12; 740266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand k += 12; 741266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 742266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 743266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /*-------------------------------- last block: affect all 32 bits of (c) */ 744266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand switch(length) /* all the case statements fall through */ 745266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 746266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 12: c+=k[11]; 747266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 11: c+=((uint32_t)k[10])<<8; 748266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 10: c+=((uint32_t)k[9])<<16; 749266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 9 : c+=((uint32_t)k[8])<<24; 750266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 8 : b+=k[7]; 751266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 7 : b+=((uint32_t)k[6])<<8; 752266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 6 : b+=((uint32_t)k[5])<<16; 753266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 5 : b+=((uint32_t)k[4])<<24; 754266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 4 : a+=k[3]; 755266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 3 : a+=((uint32_t)k[2])<<8; 756266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 2 : a+=((uint32_t)k[1])<<16; 757266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 1 : a+=((uint32_t)k[0])<<24; 758266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand break; 759266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand case 0 : return c; 760266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 761266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 762266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 763266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand final(a,b,c); 764266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand return c; 765266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand} 766266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 767266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 768266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#ifdef SELF_TEST 769266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 770266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand/* used for timings */ 771266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandvoid driver1() 772266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand{ 773266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint8_t buf[256]; 774266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint32_t i; 775266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint32_t h=0; 776266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand time_t a,z; 777266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 778266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand time(&a); 779266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand for (i=0; i<256; ++i) buf[i] = 'x'; 780266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand for (i=0; i<1; ++i) 781266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 782266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand h = hashlittle(&buf[0],1,h); 783266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 784266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand time(&z); 785266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand if (z-a > 0) printf("time %d %.8x\n", z-a, h); 786266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand} 787266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 788266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand/* check that every input bit changes every output bit half the time */ 789266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#define HASHSTATE 1 790266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#define HASHLEN 1 791266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#define MAXPAIR 60 792266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#define MAXLEN 70 793266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandvoid driver2() 794266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand{ 795266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint8_t qa[MAXLEN+1], qb[MAXLEN+2], *a = &qa[0], *b = &qb[1]; 796266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint32_t c[HASHSTATE], d[HASHSTATE], i=0, j=0, k, l, m=0, z; 797266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint32_t e[HASHSTATE],f[HASHSTATE],g[HASHSTATE],h[HASHSTATE]; 798266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint32_t x[HASHSTATE],y[HASHSTATE]; 799266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint32_t hlen; 800266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 801266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("No more than %d trials should ever be needed \n",MAXPAIR/2); 802266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand for (hlen=0; hlen < MAXLEN; ++hlen) 803266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 804266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand z=0; 805266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand for (i=0; i<hlen; ++i) /*----------------------- for each input byte, */ 806266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 807266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand for (j=0; j<8; ++j) /*------------------------ for each input bit, */ 808266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 809266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand for (m=1; m<8; ++m) /*------------ for serveral possible initvals, */ 810266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 811266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand for (l=0; l<HASHSTATE; ++l) 812266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand e[l]=f[l]=g[l]=h[l]=x[l]=y[l]=~((uint32_t)0); 813266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 814266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /*---- check that every output bit is affected by that input bit */ 815266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand for (k=0; k<MAXPAIR; k+=2) 816266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 817266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint32_t finished=1; 818266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /* keys have one bit different */ 819266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand for (l=0; l<hlen+1; ++l) {a[l] = b[l] = (uint8_t)0;} 820266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /* have a and b be two keys differing in only one bit */ 821266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a[i] ^= (k<<j); 822266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand a[i] ^= (k>>(8-j)); 823266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c[0] = hashlittle(a, hlen, m); 824266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b[i] ^= ((k+1)<<j); 825266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b[i] ^= ((k+1)>>(8-j)); 826266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand d[0] = hashlittle(b, hlen, m); 827266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /* check every bit is 1, 0, set, and not set at least once */ 828266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand for (l=0; l<HASHSTATE; ++l) 829266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 830266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand e[l] &= (c[l]^d[l]); 831266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand f[l] &= ~(c[l]^d[l]); 832266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand g[l] &= c[l]; 833266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand h[l] &= ~c[l]; 834266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand x[l] &= d[l]; 835266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand y[l] &= ~d[l]; 836266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand if (e[l]|f[l]|g[l]|h[l]|x[l]|y[l]) finished=0; 837266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 838266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand if (finished) break; 839266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 840266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand if (k>z) z=k; 841266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand if (k==MAXPAIR) 842266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 843266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("Some bit didn't change: "); 844266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("%.8x %.8x %.8x %.8x %.8x %.8x ", 845266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand e[0],f[0],g[0],h[0],x[0],y[0]); 846266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("i %d j %d m %d len %d\n", i, j, m, hlen); 847266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 848266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand if (z==MAXPAIR) goto done; 849266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 850266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 851266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 852266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand done: 853266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand if (z < MAXPAIR) 854266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 855266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("Mix success %2d bytes %2d initvals ",i,m); 856266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("required %d trials\n", z/2); 857266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 858266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 859266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("\n"); 860266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand} 861266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 862266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand/* Check for reading beyond the end of the buffer and alignment problems */ 863266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandvoid driver3() 864266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand{ 865266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint8_t buf[MAXLEN+20], *b; 866266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint32_t len; 867266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint8_t q[] = "This is the time for all good men to come to the aid of their country..."; 868266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint32_t h; 869266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint8_t qq[] = "xThis is the time for all good men to come to the aid of their country..."; 870266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint32_t i; 871266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint8_t qqq[] = "xxThis is the time for all good men to come to the aid of their country..."; 872266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint32_t j; 873266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint8_t qqqq[] = "xxxThis is the time for all good men to come to the aid of their country..."; 874266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint32_t ref,x,y; 875266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint8_t *p; 876266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 877266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("Endianness. These lines should all be the same (for values filled in):\n"); 878266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("%.8x %.8x %.8x\n", 879266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashword((const uint32_t *)q, (sizeof(q)-1)/4, 13), 880266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashword((const uint32_t *)q, (sizeof(q)-5)/4, 13), 881266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashword((const uint32_t *)q, (sizeof(q)-9)/4, 13)); 882266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand p = q; 883266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n", 884266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13), 885266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13), 886266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13), 887266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13), 888266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13), 889266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13)); 890266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand p = &qq[1]; 891266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n", 892266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13), 893266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13), 894266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13), 895266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13), 896266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13), 897266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13)); 898266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand p = &qqq[2]; 899266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n", 900266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13), 901266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13), 902266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13), 903266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13), 904266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13), 905266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13)); 906266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand p = &qqqq[3]; 907266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n", 908266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13), 909266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13), 910266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13), 911266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13), 912266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13), 913266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13)); 914266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("\n"); 915266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 916266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /* check that hashlittle2 and hashlittle produce the same results */ 917266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand i=47; j=0; 918266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashlittle2(q, sizeof(q), &i, &j); 919266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand if (hashlittle(q, sizeof(q), 47) != i) 920266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("hashlittle2 and hashlittle mismatch\n"); 921266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 922266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /* check that hashword2 and hashword produce the same results */ 923266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand len = 0xdeadbeef; 924266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand i=47, j=0; 925266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand hashword2(&len, 1, &i, &j); 926266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand if (hashword(&len, 1, 47) != i) 927266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("hashword2 and hashword mismatch %x %x\n", 928266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand i, hashword(&len, 1, 47)); 929266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 930266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /* check hashlittle doesn't read before or after the ends of the string */ 931266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand for (h=0, b=buf+1; h<8; ++h, ++b) 932266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 933266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand for (i=0; i<MAXLEN; ++i) 934266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 935266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand len = i; 936266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand for (j=0; j<i; ++j) *(b+j)=0; 937266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 938266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand /* these should all be equal */ 939266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand ref = hashlittle(b, len, (uint32_t)1); 940266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand *(b+i)=(uint8_t)~0; 941266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand *(b-1)=(uint8_t)~0; 942266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand x = hashlittle(b, len, (uint32_t)1); 943266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand y = hashlittle(b, len, (uint32_t)1); 944266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand if ((ref != x) || (ref != y)) 945266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 946266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("alignment error: %.8x %.8x %.8x %d %d\n",ref,x,y, 947266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand h, i); 948266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 949266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 950266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 951266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand} 952266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 953266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand/* check for problems with nulls */ 954266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand void driver4() 955266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand{ 956266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint8_t buf[1]; 957266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint32_t h,i,state[HASHSTATE]; 958266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 959266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 960266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand buf[0] = ~0; 961266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand for (i=0; i<HASHSTATE; ++i) state[i] = 1; 962266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("These should all be different\n"); 963266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand for (i=0, h=0; i<8; ++i) 964266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand { 965266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand h = hashlittle(buf, 0, h); 966266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("%2ld 0-byte strings, hash is %.8x\n", i, h); 967266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand } 968266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand} 969266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 970266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandvoid driver5() 971266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand{ 972266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand uint32_t b,c; 973266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b=0, c=0, hashlittle2("", 0, &c, &b); 974266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("hash is %.8lx %.8lx\n", c, b); /* deadbeef deadbeef */ 975266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b=0xdeadbeef, c=0, hashlittle2("", 0, &c, &b); 976266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("hash is %.8lx %.8lx\n", c, b); /* bd5b7dde deadbeef */ 977266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b=0xdeadbeef, c=0xdeadbeef, hashlittle2("", 0, &c, &b); 978266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("hash is %.8lx %.8lx\n", c, b); /* 9c093ccd bd5b7dde */ 979266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b=0, c=0, hashlittle2("Four score and seven years ago", 30, &c, &b); 980266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("hash is %.8lx %.8lx\n", c, b); /* 17770551 ce7226e6 */ 981266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b=1, c=0, hashlittle2("Four score and seven years ago", 30, &c, &b); 982266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("hash is %.8lx %.8lx\n", c, b); /* e3607cae bd371de4 */ 983266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand b=0, c=1, hashlittle2("Four score and seven years ago", 30, &c, &b); 984266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("hash is %.8lx %.8lx\n", c, b); /* cd628161 6cbea4b3 */ 985266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c = hashlittle("Four score and seven years ago", 30, 0); 986266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("hash is %.8lx\n", c); /* 17770551 */ 987266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand c = hashlittle("Four score and seven years ago", 30, 1); 988266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand printf("hash is %.8lx\n", c); /* cd628161 */ 989266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand} 990266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 991266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 992266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchandint main() 993266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand{ 994266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand driver1(); /* test that the key is hashed: used for timings */ 995266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand driver2(); /* test that whole key is hashed thoroughly */ 996266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand driver3(); /* test that nothing but the key is hashed */ 997266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand driver4(); /* test hashing multiple buffers (all buffers are null) */ 998266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand driver5(); /* test the hash against known vectors */ 999266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand return 1; 1000266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand} 1001266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand 1002266dde27811b78f466702295ba0173b8d8be5adaRom Lemarchand#endif /* SELF_TEST */ 1003