145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* Modified for use with yasm by Peter Johnson. */ 245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#include "util.h" 345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* 545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org-------------------------------------------------------------------- 645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orglookupa.c, by Bob Jenkins, December 1996. Same as lookup2.c 745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgUse this code however you wish. Public Domain. No warranty. 845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgSource is http://burtleburtle.net/bob/c/lookupa.c 945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org-------------------------------------------------------------------- 1045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org*/ 1145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#include "phash.h" 1245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 1345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define ub4 unsigned long 1445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 1545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define hashsize(n) ((ub4)1<<(n)) 1645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define hashmask(n) (hashsize(n)-1) 1745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 1845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* 1945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org-------------------------------------------------------------------- 2045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgmix -- mix 3 32-bit values reversibly. 2145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgFor every delta with one or two bit set, and the deltas of all three 2245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org high bits or all three low bits, whether the original value of a,b,c 2345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org is almost all zero or is uniformly distributed, 2445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org* If mix() is run forward or backward, at least 32 bits in a,b,c 2545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org have at least 1/4 probability of changing. 2645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org* If mix() is run forward, every bit of c will change between 1/3 and 2745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 2/3 of the time. (Well, 22/100 and 78/100 for some 2-bit deltas.) 2845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgmix() was built out of 36 single-cycle latency instructions in a 2945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org structure that could supported 2x parallelism, like so: 3045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org a -= b; 3145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org a -= c; x = (c>>13); 3245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org b -= c; a ^= x; 3345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org b -= a; x = (a<<8); 3445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org c -= a; b ^= x; 3545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org c -= b; x = (b>>13); 3645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org ... 3745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org Unfortunately, superscalar Pentiums and Sparcs can't take advantage 3845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org of that parallelism. They've also turned some of those single-cycle 3945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org latency instructions into multi-cycle latency instructions. Still, 4045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org this is the fastest good hash I could find. There were about 2^^68 4145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org to choose from. I only looked at a billion or so. 4245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org-------------------------------------------------------------------- 4345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org*/ 4445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define mix(a,b,c) \ 4545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org{ \ 4645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org a -= b; a -= c; a ^= (c>>13); \ 4745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org a &= 0xffffffff; \ 4845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org b -= c; b -= a; b ^= (a<<8); \ 4945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org b &= 0xffffffff; \ 5045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org c -= a; c -= b; c ^= (b>>13); \ 5145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org c &= 0xffffffff; \ 5245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org a -= b; a -= c; a ^= (c>>12); \ 5345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org a &= 0xffffffff; \ 5445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org b -= c; b -= a; b ^= (a<<16); \ 5545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org b &= 0xffffffff; \ 5645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org c -= a; c -= b; c ^= (b>>5); \ 5745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org c &= 0xffffffff; \ 5845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org a -= b; a -= c; a ^= (c>>3); \ 5945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org a &= 0xffffffff; \ 6045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org b -= c; b -= a; b ^= (a<<10); \ 6145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org b &= 0xffffffff; \ 6245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org c -= a; c -= b; c ^= (b>>15); \ 6345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org c &= 0xffffffff; \ 6445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 6545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 6645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* 6745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org-------------------------------------------------------------------- 6845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orglookup() -- hash a variable-length key into a 32-bit value 6945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org k : the key (the unaligned variable-length array of bytes) 7045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org len : the length of the key, counting by bytes 7145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org level : can be any 4-byte value 7245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgReturns a 32-bit value. Every bit of the key affects every bit of 7345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgthe return value. Every 1-bit and 2-bit delta achieves avalanche. 7445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgAbout 6len+35 instructions. 7545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 7645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgThe best hash table sizes are powers of 2. There is no need to do 7745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgmod a prime (mod is sooo slow!). If you need less than 32 bits, 7845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orguse a bitmask. For example, if you need only 10 bits, do 7945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org h = (h & hashmask(10)); 8045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgIn which case, the hash table should have hashsize(10) elements. 8145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 8245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgIf you are hashing n strings (ub1 **)k, do it like this: 8345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org for (i=0, h=0; i<n; ++i) h = lookup( k[i], len[i], h); 8445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 8545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgBy Bob Jenkins, 1996. bob_jenkins@burtleburtle.net. You may use this 8645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgcode any way you wish, private, educational, or commercial. 8745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 8845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgSee http://burtleburtle.net/bob/hash/evahash.html 8945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgUse for hash table lookup, or anything where one collision in 2^32 is 9045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgacceptable. Do NOT use for cryptographic purposes. 9145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org-------------------------------------------------------------------- 9245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org*/ 9345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 9445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgunsigned long 9545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgphash_lookup( 9645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org register const char *sk, /* the key */ 9745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org register size_t length, /* the length of the key */ 9845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org register unsigned long level) /* the previous hash, or an arbitrary value */ 9945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org{ 10045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org register unsigned long a,b,c; 10145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org register size_t len; 10245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org register const unsigned char *k = (const unsigned char *)sk; 10345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 10445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /* Set up the internal state */ 10545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org len = length; 10645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */ 10745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org c = level; /* the previous hash value */ 10845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 10945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /*---------------------------------------- handle most of the key */ 11045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org while (len >= 12) 11145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org { 11245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org a += (k[0] +((ub4)k[1]<<8) +((ub4)k[2]<<16) +((ub4)k[3]<<24)); 11345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org a &= 0xffffffff; 11445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org b += (k[4] +((ub4)k[5]<<8) +((ub4)k[6]<<16) +((ub4)k[7]<<24)); 11545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org b &= 0xffffffff; 11645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org c += (k[8] +((ub4)k[9]<<8) +((ub4)k[10]<<16)+((ub4)k[11]<<24)); 11745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org c &= 0xffffffff; 11845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org mix(a,b,c); 11945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org k += 12; len -= 12; 12045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 12145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 12245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /*------------------------------------- handle the last 11 bytes */ 12345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org c += (ub4)length; 12445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org switch(len) /* all the case statements fall through */ 12545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org { 12645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 11: c+=((ub4)k[10]<<24); 12745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 10: c+=((ub4)k[9]<<16); 12845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 9 : c+=((ub4)k[8]<<8); 12945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org c &= 0xffffffff; 13045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /* the first byte of c is reserved for the length */ 13145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 8 : b+=((ub4)k[7]<<24); 13245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 7 : b+=((ub4)k[6]<<16); 13345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 6 : b+=((ub4)k[5]<<8); 13445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 5 : b+=k[4]; 13545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org b &= 0xffffffff; 13645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 4 : a+=((ub4)k[3]<<24); 13745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 3 : a+=((ub4)k[2]<<16); 13845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 2 : a+=((ub4)k[1]<<8); 13945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 1 : a+=k[0]; 14045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org a &= 0xffffffff; 14145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /* case 0: nothing left to add */ 14245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 14345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org mix(a,b,c); 14445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /*-------------------------------------------- report the result */ 14545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org return c; 14645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 14745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 14845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 14945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* 15045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org-------------------------------------------------------------------- 15145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgmixc -- mixc 8 4-bit values as quickly and thoroughly as possible. 15245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgRepeating mix() three times achieves avalanche. 15345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgRepeating mix() four times eliminates all funnels and all 15445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org characteristics stronger than 2^{-11}. 15545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org-------------------------------------------------------------------- 15645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org*/ 15745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org#define mixc(a,b,c,d,e,f,g,h) \ 15845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org{ \ 15945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org a^=b<<11; d+=a; b+=c; \ 16045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org b^=c>>2; e+=b; c+=d; \ 16145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org c^=d<<8; f+=c; d+=e; \ 16245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org d^=e>>16; g+=d; e+=f; \ 16345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org e^=f<<10; h+=e; f+=g; \ 16445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org f^=g>>4; a+=f; g+=h; \ 16545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org g^=h<<8; b+=g; h+=a; \ 16645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org h^=a>>9; c+=h; a+=b; \ 16745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 16845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 16945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org/* 17045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org-------------------------------------------------------------------- 17145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgchecksum() -- hash a variable-length key into a 256-bit value 17245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org k : the key (the unaligned variable-length array of bytes) 17345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org len : the length of the key, counting by bytes 17445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org state : an array of CHECKSTATE 4-byte values (256 bits) 17545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgThe state is the checksum. Every bit of the key affects every bit of 17645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgthe state. There are no funnels. About 112+6.875len instructions. 17745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 17845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgIf you are hashing n strings (ub1 **)k, do it like this: 17945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org for (i=0; i<8; ++i) state[i] = 0x9e3779b9; 18045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org for (i=0, h=0; i<n; ++i) checksum( k[i], len[i], state); 18145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 18245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org(c) Bob Jenkins, 1996. bob_jenkins@burtleburtle.net. You may use this 18345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgcode any way you wish, private, educational, or commercial, as long 18445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgas this whole comment accompanies it. 18545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 18645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgSee http://burtleburtle.net/bob/hash/evahash.html 18745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgUse to detect changes between revisions of documents, assuming nobody 18845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgis trying to cause collisions. Do NOT use for cryptography. 18945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org-------------------------------------------------------------------- 19045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org*/ 19145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgvoid 19245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.orgphash_checksum( 19345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org register const char *sk, 19445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org register size_t len, 19545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org register unsigned long *state) 19645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org{ 19745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org register unsigned long a,b,c,d,e,f,g,h; 19845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org register size_t length; 19945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org register const unsigned char *k = (const unsigned char *)sk; 20045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 20145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /* Use the length and level; add in the golden ratio. */ 20245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org length = len; 20345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org a=state[0]; b=state[1]; c=state[2]; d=state[3]; 20445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org e=state[4]; f=state[5]; g=state[6]; h=state[7]; 20545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 20645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /*---------------------------------------- handle most of the key */ 20745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org while (len >= 32) 20845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org { 20945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org a += (k[0] +(k[1]<<8) +(k[2]<<16) +(k[3]<<24)); 21045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org b += (k[4] +(k[5]<<8) +(k[6]<<16) +(k[7]<<24)); 21145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org c += (k[8] +(k[9]<<8) +(k[10]<<16)+(k[11]<<24)); 21245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org d += (k[12]+(k[13]<<8)+(k[14]<<16)+(k[15]<<24)); 21345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org e += (k[16]+(k[17]<<8)+(k[18]<<16)+(k[19]<<24)); 21445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org f += (k[20]+(k[21]<<8)+(k[22]<<16)+(k[23]<<24)); 21545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org g += (k[24]+(k[25]<<8)+(k[26]<<16)+(k[27]<<24)); 21645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org h += (k[28]+(k[29]<<8)+(k[30]<<16)+(k[31]<<24)); 21745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org mixc(a,b,c,d,e,f,g,h); 21845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org mixc(a,b,c,d,e,f,g,h); 21945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org mixc(a,b,c,d,e,f,g,h); 22045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org mixc(a,b,c,d,e,f,g,h); 22145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org k += 32; len -= 32; 22245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 22345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 22445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /*------------------------------------- handle the last 31 bytes */ 22545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org h += (ub4)length; 22645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org switch(len) 22745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org { 22845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 31: h+=(k[30]<<24); 22945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 30: h+=(k[29]<<16); 23045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 29: h+=(k[28]<<8); 23145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 28: g+=(k[27]<<24); 23245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 27: g+=(k[26]<<16); 23345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 26: g+=(k[25]<<8); 23445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 25: g+=k[24]; 23545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 24: f+=(k[23]<<24); 23645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 23: f+=(k[22]<<16); 23745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 22: f+=(k[21]<<8); 23845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 21: f+=k[20]; 23945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 20: e+=(k[19]<<24); 24045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 19: e+=(k[18]<<16); 24145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 18: e+=(k[17]<<8); 24245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 17: e+=k[16]; 24345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 16: d+=(k[15]<<24); 24445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 15: d+=(k[14]<<16); 24545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 14: d+=(k[13]<<8); 24645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 13: d+=k[12]; 24745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 12: c+=(k[11]<<24); 24845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 11: c+=(k[10]<<16); 24945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 10: c+=(k[9]<<8); 25045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 9 : c+=k[8]; 25145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 8 : b+=(k[7]<<24); 25245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 7 : b+=(k[6]<<16); 25345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 6 : b+=(k[5]<<8); 25445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 5 : b+=k[4]; 25545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 4 : a+=(k[3]<<24); 25645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 3 : a+=(k[2]<<16); 25745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 2 : a+=(k[1]<<8); 25845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org case 1 : a+=k[0]; 25945afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org } 26045afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org mixc(a,b,c,d,e,f,g,h); 26145afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org mixc(a,b,c,d,e,f,g,h); 26245afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org mixc(a,b,c,d,e,f,g,h); 26345afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org mixc(a,b,c,d,e,f,g,h); 26445afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org 26545afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org /*-------------------------------------------- report the result */ 26645afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org state[0]=a; state[1]=b; state[2]=c; state[3]=d; 26745afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org state[4]=e; state[5]=f; state[6]=g; state[7]=h; 26845afe016bed87b9c6946184709058b39ede3f77ajwong@chromium.org} 269