jenkins_hash.c revision 240086
11541Srgrimes/* 21541Srgrimes * Taken from http://burtleburtle.net/bob/c/lookup3.c 31541Srgrimes * $FreeBSD: head/sys/libkern/jenkins_hash.c 240086 2012-09-04 12:07:33Z glebius $ 41541Srgrimes */ 51541Srgrimes 61541Srgrimes#include <sys/hash.h> 71541Srgrimes#include <machine/endian.h> 81541Srgrimes 91541Srgrimes/* 101541Srgrimes------------------------------------------------------------------------------- 111541Srgrimeslookup3.c, by Bob Jenkins, May 2006, Public Domain. 121541Srgrimes 131541SrgrimesThese are functions for producing 32-bit hashes for hash table lookup. 141541Srgrimeshashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final() 151541Srgrimesare externally useful functions. Routines to test the hash are included 161541Srgrimesif SELF_TEST is defined. You can use this free for any purpose. It's in 171541Srgrimesthe public domain. It has no warranty. 181541Srgrimes 191541SrgrimesYou probably want to use hashlittle(). hashlittle() and hashbig() 201541Srgrimeshash byte arrays. hashlittle() is is faster than hashbig() on 211541Srgrimeslittle-endian machines. Intel and AMD are little-endian machines. 221541SrgrimesOn second thought, you probably want hashlittle2(), which is identical to 231541Srgrimeshashlittle() except it returns two 32-bit hashes for the price of one. 241541SrgrimesYou could implement hashbig2() if you wanted but I haven't bothered here. 251541Srgrimes 261541SrgrimesIf you want to find a hash of, say, exactly 7 integers, do 271541Srgrimes a = i1; b = i2; c = i3; 281541Srgrimes mix(a,b,c); 291541Srgrimes a += i4; b += i5; c += i6; 301541Srgrimes mix(a,b,c); 311541Srgrimes a += i7; 321541Srgrimes final(a,b,c); 331541Srgrimesthen use c as the hash value. If you have a variable length array of 343055Sdg4-byte integers to hash, use hashword(). If you have a byte array (like 351541Srgrimesa character string), use hashlittle(). If you have several byte arrays, or 361541Srgrimesa mix of things, see the comments above hashlittle(). 371541Srgrimes 381549SrgrimesWhy is this so big? I read 12 bytes at a time into 3 4-byte integers, 391541Srgrimesthen mix those integers. This is fast (you can do a lot more thorough 401541Srgrimesmixing with 12*3 instructions on 3 integers than you can with 3 instructions 411541Srgrimeson 1 byte), but shoehorning those bytes into integers efficiently is messy. 421541Srgrimes------------------------------------------------------------------------------- 431541Srgrimes*/ 441541Srgrimes 451541Srgrimes#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) 461541Srgrimes 471541Srgrimes/* 481541Srgrimes------------------------------------------------------------------------------- 491541Srgrimesmix -- mix 3 32-bit values reversibly. 503055Sdg 511541SrgrimesThis is reversible, so any information in (a,b,c) before mix() is 521541Srgrimesstill in (a,b,c) after mix(). 531541Srgrimes 543055SdgIf four pairs of (a,b,c) inputs are run through mix(), or through 551541Srgrimesmix() in reverse, there are at least 32 bits of the output that 561541Srgrimesare sometimes the same for one pair and different for another pair. 571541SrgrimesThis was tested for: 581541Srgrimes* pairs that differed by one bit, by two bits, in any combination 591541Srgrimes of top bits of (a,b,c), or in any combination of bottom bits of 601541Srgrimes (a,b,c). 611541Srgrimes* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed 621541Srgrimes the output delta to a Gray code (a^(a>>1)) so a string of 1's (as 631541Srgrimes is commonly produced by subtraction) look like a single 1-bit 641541Srgrimes difference. 651541Srgrimes* the base values were pseudorandom, all zero but one bit set, or 661541Srgrimes all zero plus a counter that starts at zero. 671541Srgrimes 681541SrgrimesSome k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that 691541Srgrimessatisfy this are 701541Srgrimes 4 6 8 16 19 4 711541Srgrimes 9 15 3 18 27 15 721541Srgrimes 14 9 3 7 17 3 731541SrgrimesWell, "9 15 3 18 27 15" didn't quite get 32 bits diffing 741541Srgrimesfor "differ" defined as + with a one-bit base and a two-bit delta. I 751541Srgrimesused http://burtleburtle.net/bob/hash/avalanche.html to choose 761541Srgrimesthe operations, constants, and arrangements of the variables. 771541Srgrimes 781541SrgrimesThis does not achieve avalanche. There are input bits of (a,b,c) 791541Srgrimesthat fail to affect some output bits of (a,b,c), especially of a. The 801541Srgrimesmost thoroughly mixed value is c, but it doesn't really even achieve 811541Srgrimesavalanche in c. 821541Srgrimes 831541SrgrimesThis allows some parallelism. Read-after-writes are good at doubling 841541Srgrimesthe number of bits affected, so the goal of mixing pulls in the opposite 851541Srgrimesdirection as the goal of parallelism. I did what I could. Rotates 861541Srgrimesseem to cost as much as shifts on every machine I could lay my hands 871541Srgrimeson, and rotates are much kinder to the top and bottom bits, so I used 881541Srgrimesrotates. 891541Srgrimes------------------------------------------------------------------------------- 901541Srgrimes*/ 911541Srgrimes#define mix(a,b,c) \ 921541Srgrimes{ \ 931541Srgrimes a -= c; a ^= rot(c, 4); c += b; \ 941541Srgrimes b -= a; b ^= rot(a, 6); a += c; \ 951541Srgrimes c -= b; c ^= rot(b, 8); b += a; \ 961541Srgrimes a -= c; a ^= rot(c,16); c += b; \ 971541Srgrimes b -= a; b ^= rot(a,19); a += c; \ 981541Srgrimes c -= b; c ^= rot(b, 4); b += a; \ 991541Srgrimes} 1001541Srgrimes 1011541Srgrimes/* 1021541Srgrimes------------------------------------------------------------------------------- 1031541Srgrimesfinal -- final mixing of 3 32-bit values (a,b,c) into c 1041541Srgrimes 1051541SrgrimesPairs of (a,b,c) values differing in only a few bits will usually 1061541Srgrimesproduce values of c that look totally different. This was tested for 1071541Srgrimes* pairs that differed by one bit, by two bits, in any combination 1081541Srgrimes of top bits of (a,b,c), or in any combination of bottom bits of 1091541Srgrimes (a,b,c). 1101549Srgrimes* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed 1111541Srgrimes the output delta to a Gray code (a^(a>>1)) so a string of 1's (as 1121541Srgrimes is commonly produced by subtraction) look like a single 1-bit 1131541Srgrimes difference. 1141541Srgrimes* the base values were pseudorandom, all zero but one bit set, or 1151541Srgrimes all zero plus a counter that starts at zero. 1161541Srgrimes 1171541SrgrimesThese constants passed: 1181541Srgrimes 14 11 25 16 4 14 24 1191541Srgrimes 12 14 25 16 4 14 24 1201541Srgrimesand these came close: 1211541Srgrimes 4 8 15 26 3 22 24 1221541Srgrimes 10 8 15 26 3 22 24 1231541Srgrimes 11 8 15 26 3 22 24 1241541Srgrimes------------------------------------------------------------------------------- 1251541Srgrimes*/ 1261541Srgrimes#define final(a,b,c) \ 1271541Srgrimes{ \ 1281541Srgrimes c ^= b; c -= rot(b,14); \ 1291541Srgrimes a ^= c; a -= rot(c,11); \ 1301541Srgrimes b ^= a; b -= rot(a,25); \ 1311541Srgrimes c ^= b; c -= rot(b,16); \ 1321541Srgrimes a ^= c; a -= rot(c,4); \ 1331541Srgrimes b ^= a; b -= rot(a,14); \ 1341541Srgrimes c ^= b; c -= rot(b,24); \ 1351541Srgrimes} 1361541Srgrimes 1371541Srgrimes/* 1381541Srgrimes-------------------------------------------------------------------- 1391541Srgrimes This works on all machines. To be useful, it requires 1401541Srgrimes -- that the key be an array of uint32_t's, and 1411541Srgrimes -- that the length be the number of uint32_t's in the key 1421541Srgrimes 1431541Srgrimes The function hashword() is identical to hashlittle() on little-endian 1441541Srgrimes machines, and identical to hashbig() on big-endian machines, 1451541Srgrimes except that the length has to be measured in uint32_ts rather than in 1461541Srgrimes bytes. hashlittle() is more complicated than hashword() only because 1471541Srgrimes hashlittle() has to dance around fitting the key bytes into registers. 1481541Srgrimes-------------------------------------------------------------------- 1491541Srgrimes*/ 1501541Srgrimesuint32_t jenkins_hash32( 1511541Srgrimesconst uint32_t *k, /* the key, an array of uint32_t values */ 1521541Srgrimessize_t length, /* the length of the key, in uint32_ts */ 1531541Srgrimesuint32_t initval) /* the previous hash, or an arbitrary value */ 1541541Srgrimes{ 1551541Srgrimes uint32_t a,b,c; 1561541Srgrimes 1571541Srgrimes /* Set up the internal state */ 1581541Srgrimes a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval; 1591541Srgrimes 1601541Srgrimes /*------------------------------------------------- handle most of the key */ 1611541Srgrimes while (length > 3) 1621541Srgrimes { 1631541Srgrimes a += k[0]; 1641541Srgrimes b += k[1]; 1651541Srgrimes c += k[2]; 1661541Srgrimes mix(a,b,c); 1671541Srgrimes length -= 3; 1681541Srgrimes k += 3; 1691541Srgrimes } 1701541Srgrimes 1711541Srgrimes /*------------------------------------------- handle the last 3 uint32_t's */ 1721541Srgrimes switch(length) /* all the case statements fall through */ 1731541Srgrimes { 1741541Srgrimes case 3 : c+=k[2]; 1751541Srgrimes case 2 : b+=k[1]; 1761541Srgrimes case 1 : a+=k[0]; 1771541Srgrimes final(a,b,c); 1781541Srgrimes case 0: /* case 0: nothing left to add */ 1791541Srgrimes break; 1801541Srgrimes } 1811541Srgrimes /*------------------------------------------------------ report the result */ 1821541Srgrimes return c; 1831541Srgrimes} 1841541Srgrimes 1851541Srgrimes#if BYTE_ORDER == LITTLE_ENDIAN 1861541Srgrimes/* 1871541Srgrimes------------------------------------------------------------------------------- 1881541Srgrimeshashlittle() -- hash a variable-length key into a 32-bit value 1891541Srgrimes k : the key (the unaligned variable-length array of bytes) 1901541Srgrimes length : the length of the key, counting by bytes 1911541Srgrimes initval : can be any 4-byte value 1921541SrgrimesReturns a 32-bit value. Every bit of the key affects every bit of 1931541Srgrimesthe return value. Two keys differing by one or two bits will have 1941541Srgrimestotally different hash values. 1951541Srgrimes 1961541SrgrimesThe best hash table sizes are powers of 2. There is no need to do 1971541Srgrimesmod a prime (mod is sooo slow!). If you need less than 32 bits, 1981541Srgrimesuse a bitmask. For example, if you need only 10 bits, do 1991541Srgrimes h = (h & hashmask(10)); 2001541SrgrimesIn which case, the hash table should have hashsize(10) elements. 2011541Srgrimes 2021541SrgrimesIf you are hashing n strings (uint8_t **)k, do it like this: 2031541Srgrimes for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h); 2041541Srgrimes 2051541SrgrimesBy Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this 2061541Srgrimescode any way you wish, private, educational, or commercial. It's free. 2071541Srgrimes 2081541SrgrimesUse for hash table lookup, or anything where one collision in 2^^32 is 2091541Srgrimesacceptable. Do NOT use for cryptographic purposes. 2101541Srgrimes------------------------------------------------------------------------------- 2111541Srgrimes*/ 2121541Srgrimes 2131541Srgrimesuint32_t jenkins_hash( const void *key, size_t length, uint32_t initval) 2141541Srgrimes{ 2151541Srgrimes uint32_t a,b,c; /* internal state */ 2161541Srgrimes union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */ 2171541Srgrimes 2181541Srgrimes /* Set up the internal state */ 2191541Srgrimes a = b = c = 0xdeadbeef + ((uint32_t)length) + initval; 2201541Srgrimes 2211541Srgrimes u.ptr = key; 2221541Srgrimes if ((u.i & 0x3) == 0) { 2231541Srgrimes const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ 2241541Srgrimes 2251541Srgrimes /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ 2261541Srgrimes while (length > 12) 2271541Srgrimes { 2281541Srgrimes a += k[0]; 2291541Srgrimes b += k[1]; 2301541Srgrimes c += k[2]; 2311541Srgrimes mix(a,b,c); 2321541Srgrimes length -= 12; 2331541Srgrimes k += 3; 2341541Srgrimes } 2351541Srgrimes 2361541Srgrimes /*----------------------------- handle the last (probably partial) block */ 2371541Srgrimes /* 2381541Srgrimes * "k[2]&0xffffff" actually reads beyond the end of the string, but 2391541Srgrimes * then masks off the part it's not allowed to read. Because the 2401541Srgrimes * string is aligned, the masked-off tail is in the same word as the 2411541Srgrimes * rest of the string. Every machine with memory protection I've seen 2421541Srgrimes * does it on word boundaries, so is OK with this. But VALGRIND will 2431541Srgrimes * still catch it and complain. The masking trick does make the hash 2441541Srgrimes * noticably faster for short strings (like English words). 2451541Srgrimes */ 2461541Srgrimes 2471541Srgrimes switch(length) 2481541Srgrimes { 2491541Srgrimes case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; 2501541Srgrimes case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break; 2511541Srgrimes case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break; 2521541Srgrimes case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break; 2531541Srgrimes case 8 : b+=k[1]; a+=k[0]; break; 2541541Srgrimes case 7 : b+=k[1]&0xffffff; a+=k[0]; break; 2551541Srgrimes case 6 : b+=k[1]&0xffff; a+=k[0]; break; 2561541Srgrimes case 5 : b+=k[1]&0xff; a+=k[0]; break; 2571541Srgrimes case 4 : a+=k[0]; break; 2581541Srgrimes case 3 : a+=k[0]&0xffffff; break; 2591541Srgrimes case 2 : a+=k[0]&0xffff; break; 2601541Srgrimes case 1 : a+=k[0]&0xff; break; 2611541Srgrimes case 0 : return c; /* zero length strings require no mixing */ 2621541Srgrimes } 2631541Srgrimes 2641541Srgrimes } else if ((u.i & 0x1) == 0) { 2651541Srgrimes const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */ 2661541Srgrimes const uint8_t *k8; 2671541Srgrimes 2681541Srgrimes /*--------------- all but last block: aligned reads and different mixing */ 2691541Srgrimes while (length > 12) 2701541Srgrimes { 2711541Srgrimes a += k[0] + (((uint32_t)k[1])<<16); 2721541Srgrimes b += k[2] + (((uint32_t)k[3])<<16); 2731541Srgrimes c += k[4] + (((uint32_t)k[5])<<16); 2741541Srgrimes mix(a,b,c); 2751541Srgrimes length -= 12; 2761541Srgrimes k += 6; 2771541Srgrimes } 2781541Srgrimes 2791541Srgrimes /*----------------------------- handle the last (probably partial) block */ 2801541Srgrimes k8 = (const uint8_t *)k; 2811541Srgrimes switch(length) 2821541Srgrimes { 2831541Srgrimes case 12: c+=k[4]+(((uint32_t)k[5])<<16); 2841541Srgrimes b+=k[2]+(((uint32_t)k[3])<<16); 2851541Srgrimes a+=k[0]+(((uint32_t)k[1])<<16); 2861541Srgrimes break; 2871541Srgrimes case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ 2881541Srgrimes case 10: c+=k[4]; 2891541Srgrimes b+=k[2]+(((uint32_t)k[3])<<16); 2901541Srgrimes a+=k[0]+(((uint32_t)k[1])<<16); 2911541Srgrimes break; 2921541Srgrimes case 9 : c+=k8[8]; /* fall through */ 2931541Srgrimes case 8 : b+=k[2]+(((uint32_t)k[3])<<16); 2941541Srgrimes a+=k[0]+(((uint32_t)k[1])<<16); 2951541Srgrimes break; 2961541Srgrimes case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ 2971541Srgrimes case 6 : b+=k[2]; 2981541Srgrimes a+=k[0]+(((uint32_t)k[1])<<16); 2991541Srgrimes break; 3001541Srgrimes case 5 : b+=k8[4]; /* fall through */ 3011541Srgrimes case 4 : a+=k[0]+(((uint32_t)k[1])<<16); 3021541Srgrimes break; 3031541Srgrimes case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ 3041541Srgrimes case 2 : a+=k[0]; 3051541Srgrimes break; 3061541Srgrimes case 1 : a+=k8[0]; 3071541Srgrimes break; 3081541Srgrimes case 0 : return c; /* zero length requires no mixing */ 3091541Srgrimes } 3101541Srgrimes 3111541Srgrimes } else { /* need to read the key one byte at a time */ 3121541Srgrimes const uint8_t *k = (const uint8_t *)key; 3131541Srgrimes 3141541Srgrimes /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ 3151541Srgrimes while (length > 12) 3161541Srgrimes { 3171541Srgrimes a += k[0]; 3181541Srgrimes a += ((uint32_t)k[1])<<8; 3191541Srgrimes a += ((uint32_t)k[2])<<16; 3201541Srgrimes a += ((uint32_t)k[3])<<24; 3211541Srgrimes b += k[4]; 3221541Srgrimes b += ((uint32_t)k[5])<<8; 3231541Srgrimes b += ((uint32_t)k[6])<<16; 3241541Srgrimes b += ((uint32_t)k[7])<<24; 3251541Srgrimes c += k[8]; 3261541Srgrimes c += ((uint32_t)k[9])<<8; 3271541Srgrimes c += ((uint32_t)k[10])<<16; 3281541Srgrimes c += ((uint32_t)k[11])<<24; 3291541Srgrimes mix(a,b,c); 3301541Srgrimes length -= 12; 3311541Srgrimes k += 12; 3321541Srgrimes } 3331541Srgrimes 3341541Srgrimes /*-------------------------------- last block: affect all 32 bits of (c) */ 3351541Srgrimes switch(length) /* all the case statements fall through */ 3361541Srgrimes { 3371541Srgrimes case 12: c+=((uint32_t)k[11])<<24; 3381541Srgrimes case 11: c+=((uint32_t)k[10])<<16; 3391541Srgrimes case 10: c+=((uint32_t)k[9])<<8; 3401541Srgrimes case 9 : c+=k[8]; 3411541Srgrimes case 8 : b+=((uint32_t)k[7])<<24; 3421541Srgrimes case 7 : b+=((uint32_t)k[6])<<16; 3431541Srgrimes case 6 : b+=((uint32_t)k[5])<<8; 3441541Srgrimes case 5 : b+=k[4]; 3451541Srgrimes case 4 : a+=((uint32_t)k[3])<<24; 3461541Srgrimes case 3 : a+=((uint32_t)k[2])<<16; 3471541Srgrimes case 2 : a+=((uint32_t)k[1])<<8; 3481541Srgrimes case 1 : a+=k[0]; 3491541Srgrimes break; 3501541Srgrimes case 0 : return c; 3511541Srgrimes } 3521541Srgrimes } 3531541Srgrimes 3541541Srgrimes final(a,b,c); 3551541Srgrimes return c; 3561541Srgrimes} 3571541Srgrimes 3581541Srgrimes#else /* !(BYTE_ORDER == LITTLE_ENDIAN) */ 3591541Srgrimes 3601541Srgrimes/* 3611541Srgrimes * hashbig(): 3621541Srgrimes * This is the same as hashword() on big-endian machines. It is different 3631541Srgrimes * from hashlittle() on all machines. hashbig() takes advantage of 3641541Srgrimes * big-endian byte ordering. 3651541Srgrimes */ 3661541Srgrimesuint32_t jenkins_hash( const void *key, size_t length, uint32_t initval) 3671541Srgrimes{ 3681541Srgrimes uint32_t a,b,c; 3691541Srgrimes union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */ 3701541Srgrimes 3711541Srgrimes /* Set up the internal state */ 3721541Srgrimes a = b = c = 0xdeadbeef + ((uint32_t)length) + initval; 3731541Srgrimes 3741541Srgrimes u.ptr = key; 3751541Srgrimes if ((u.i & 0x3) == 0) { 3761541Srgrimes const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ 3771541Srgrimes 3781541Srgrimes /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ 3791541Srgrimes while (length > 12) 3801541Srgrimes { 3811541Srgrimes a += k[0]; 3821541Srgrimes b += k[1]; 3831541Srgrimes c += k[2]; 3841541Srgrimes mix(a,b,c); 3851541Srgrimes length -= 12; 3861541Srgrimes k += 3; 3871541Srgrimes } 3881541Srgrimes 3891541Srgrimes /*----------------------------- handle the last (probably partial) block */ 3901541Srgrimes /* 3911541Srgrimes * "k[2]<<8" actually reads beyond the end of the string, but 3921541Srgrimes * then shifts out the part it's not allowed to read. Because the 3931541Srgrimes * string is aligned, the illegal read is in the same word as the 3941541Srgrimes * rest of the string. Every machine with memory protection I've seen 3951541Srgrimes * does it on word boundaries, so is OK with this. But VALGRIND will 3961541Srgrimes * still catch it and complain. The masking trick does make the hash 3971541Srgrimes * noticably faster for short strings (like English words). 3981541Srgrimes */ 3991541Srgrimes 4001541Srgrimes switch(length) 4011541Srgrimes { 4021541Srgrimes case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; 4031541Srgrimes case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break; 4041541Srgrimes case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break; 4051541Srgrimes case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break; 4061541Srgrimes case 8 : b+=k[1]; a+=k[0]; break; 4071541Srgrimes case 7 : b+=k[1]&0xffffff00; a+=k[0]; break; 4081541Srgrimes case 6 : b+=k[1]&0xffff0000; a+=k[0]; break; 4091541Srgrimes case 5 : b+=k[1]&0xff000000; a+=k[0]; break; 4101541Srgrimes case 4 : a+=k[0]; break; 4111541Srgrimes case 3 : a+=k[0]&0xffffff00; break; 4121541Srgrimes case 2 : a+=k[0]&0xffff0000; break; 4131541Srgrimes case 1 : a+=k[0]&0xff000000; break; 4141541Srgrimes case 0 : return c; /* zero length strings require no mixing */ 4151541Srgrimes } 4161541Srgrimes 4171541Srgrimes } else { /* need to read the key one byte at a time */ 4181541Srgrimes const uint8_t *k = (const uint8_t *)key; 4191541Srgrimes 4201541Srgrimes /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ 4211541Srgrimes while (length > 12) 4221541Srgrimes { 4231541Srgrimes a += ((uint32_t)k[0])<<24; 4241541Srgrimes a += ((uint32_t)k[1])<<16; 4251541Srgrimes a += ((uint32_t)k[2])<<8; 4261541Srgrimes a += ((uint32_t)k[3]); 4271541Srgrimes b += ((uint32_t)k[4])<<24; 4281541Srgrimes b += ((uint32_t)k[5])<<16; 4291541Srgrimes b += ((uint32_t)k[6])<<8; 4301541Srgrimes b += ((uint32_t)k[7]); 4311541Srgrimes c += ((uint32_t)k[8])<<24; 4321541Srgrimes c += ((uint32_t)k[9])<<16; 4331541Srgrimes c += ((uint32_t)k[10])<<8; 4341541Srgrimes c += ((uint32_t)k[11]); 4351541Srgrimes mix(a,b,c); 4361541Srgrimes length -= 12; 4371541Srgrimes k += 12; 4381541Srgrimes } 4391541Srgrimes 4401541Srgrimes /*-------------------------------- last block: affect all 32 bits of (c) */ 4411541Srgrimes switch(length) /* all the case statements fall through */ 4421541Srgrimes { 4431541Srgrimes case 12: c+=k[11]; 4441541Srgrimes case 11: c+=((uint32_t)k[10])<<8; 4451541Srgrimes case 10: c+=((uint32_t)k[9])<<16; 4461541Srgrimes case 9 : c+=((uint32_t)k[8])<<24; 4471541Srgrimes case 8 : b+=k[7]; 4481541Srgrimes case 7 : b+=((uint32_t)k[6])<<8; 4491541Srgrimes case 6 : b+=((uint32_t)k[5])<<16; 4501541Srgrimes case 5 : b+=((uint32_t)k[4])<<24; 4511541Srgrimes case 4 : a+=k[3]; 4521541Srgrimes case 3 : a+=((uint32_t)k[2])<<8; 4531541Srgrimes case 2 : a+=((uint32_t)k[1])<<16; 4541541Srgrimes case 1 : a+=((uint32_t)k[0])<<24; 4551541Srgrimes break; 4561541Srgrimes case 0 : return c; 4571541Srgrimes } 4581541Srgrimes } 4591541Srgrimes 4601541Srgrimes final(a,b,c); 4611541Srgrimes return c; 4621541Srgrimes} 4631541Srgrimes#endif 4641541Srgrimes