1/* Modified for use with yasm by Peter Johnson. */
2#include "util.h"
3
4/*
5--------------------------------------------------------------------
6lookupa.c, by Bob Jenkins, December 1996.  Same as lookup2.c
7Use this code however you wish.  Public Domain.  No warranty.
8Source is http://burtleburtle.net/bob/c/lookupa.c
9--------------------------------------------------------------------
10*/
11#include "phash.h"
12
13#define ub4 unsigned long
14
15#define hashsize(n) ((ub4)1<<(n))
16#define hashmask(n) (hashsize(n)-1)
17
18/*
19--------------------------------------------------------------------
20mix -- mix 3 32-bit values reversibly.
21For every delta with one or two bit set, and the deltas of all three
22  high bits or all three low bits, whether the original value of a,b,c
23  is almost all zero or is uniformly distributed,
24* If mix() is run forward or backward, at least 32 bits in a,b,c
25  have at least 1/4 probability of changing.
26* If mix() is run forward, every bit of c will change between 1/3 and
27  2/3 of the time.  (Well, 22/100 and 78/100 for some 2-bit deltas.)
28mix() was built out of 36 single-cycle latency instructions in a
29  structure that could supported 2x parallelism, like so:
30      a -= b;
31      a -= c; x = (c>>13);
32      b -= c; a ^= x;
33      b -= a; x = (a<<8);
34      c -= a; b ^= x;
35      c -= b; x = (b>>13);
36      ...
37  Unfortunately, superscalar Pentiums and Sparcs can't take advantage
38  of that parallelism.  They've also turned some of those single-cycle
39  latency instructions into multi-cycle latency instructions.  Still,
40  this is the fastest good hash I could find.  There were about 2^^68
41  to choose from.  I only looked at a billion or so.
42--------------------------------------------------------------------
43*/
44#define mix(a,b,c) \
45{ \
46    a -= b; a -= c; a ^= (c>>13); \
47    a &= 0xffffffff; \
48    b -= c; b -= a; b ^= (a<<8); \
49    b &= 0xffffffff; \
50    c -= a; c -= b; c ^= (b>>13); \
51    c &= 0xffffffff; \
52    a -= b; a -= c; a ^= (c>>12);  \
53    a &= 0xffffffff; \
54    b -= c; b -= a; b ^= (a<<16); \
55    b &= 0xffffffff; \
56    c -= a; c -= b; c ^= (b>>5); \
57    c &= 0xffffffff; \
58    a -= b; a -= c; a ^= (c>>3);  \
59    a &= 0xffffffff; \
60    b -= c; b -= a; b ^= (a<<10); \
61    b &= 0xffffffff; \
62    c -= a; c -= b; c ^= (b>>15); \
63    c &= 0xffffffff; \
64}
65
66/*
67--------------------------------------------------------------------
68lookup() -- hash a variable-length key into a 32-bit value
69  k     : the key (the unaligned variable-length array of bytes)
70  len   : the length of the key, counting by bytes
71  level : can be any 4-byte value
72Returns a 32-bit value.  Every bit of the key affects every bit of
73the return value.  Every 1-bit and 2-bit delta achieves avalanche.
74About 6len+35 instructions.
75
76The best hash table sizes are powers of 2.  There is no need to do
77mod a prime (mod is sooo slow!).  If you need less than 32 bits,
78use a bitmask.  For example, if you need only 10 bits, do
79  h = (h & hashmask(10));
80In which case, the hash table should have hashsize(10) elements.
81
82If you are hashing n strings (ub1 **)k, do it like this:
83  for (i=0, h=0; i<n; ++i) h = lookup( k[i], len[i], h);
84
85By Bob Jenkins, 1996.  bob_jenkins@burtleburtle.net.  You may use this
86code any way you wish, private, educational, or commercial.
87
88See http://burtleburtle.net/bob/hash/evahash.html
89Use for hash table lookup, or anything where one collision in 2^32 is
90acceptable.  Do NOT use for cryptographic purposes.
91--------------------------------------------------------------------
92*/
93
94unsigned long
95phash_lookup(
96    register const char *sk, /* the key */
97    register size_t length,   /* the length of the key */
98    register unsigned long level) /* the previous hash, or an arbitrary value */
99{
100    register unsigned long a,b,c;
101    register size_t len;
102    register const unsigned char *k = (const unsigned char *)sk;
103
104    /* Set up the internal state */
105    len = length;
106    a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
107    c = level;           /* the previous hash value */
108
109    /*---------------------------------------- handle most of the key */
110    while (len >= 12)
111    {
112        a += (k[0] +((ub4)k[1]<<8) +((ub4)k[2]<<16) +((ub4)k[3]<<24));
113        a &= 0xffffffff;
114        b += (k[4] +((ub4)k[5]<<8) +((ub4)k[6]<<16) +((ub4)k[7]<<24));
115        b &= 0xffffffff;
116        c += (k[8] +((ub4)k[9]<<8) +((ub4)k[10]<<16)+((ub4)k[11]<<24));
117        c &= 0xffffffff;
118        mix(a,b,c);
119        k += 12; len -= 12;
120    }
121
122    /*------------------------------------- handle the last 11 bytes */
123    c += (ub4)length;
124    switch(len)              /* all the case statements fall through */
125    {
126        case 11: c+=((ub4)k[10]<<24);
127        case 10: c+=((ub4)k[9]<<16);
128        case 9 : c+=((ub4)k[8]<<8);
129                 c &= 0xffffffff;
130            /* the first byte of c is reserved for the length */
131        case 8 : b+=((ub4)k[7]<<24);
132        case 7 : b+=((ub4)k[6]<<16);
133        case 6 : b+=((ub4)k[5]<<8);
134        case 5 : b+=k[4];
135                 b &= 0xffffffff;
136        case 4 : a+=((ub4)k[3]<<24);
137        case 3 : a+=((ub4)k[2]<<16);
138        case 2 : a+=((ub4)k[1]<<8);
139        case 1 : a+=k[0];
140                 a &= 0xffffffff;
141        /* case 0: nothing left to add */
142    }
143    mix(a,b,c);
144    /*-------------------------------------------- report the result */
145    return c;
146}
147
148
149/*
150--------------------------------------------------------------------
151mixc -- mixc 8 4-bit values as quickly and thoroughly as possible.
152Repeating mix() three times achieves avalanche.
153Repeating mix() four times eliminates all funnels and all
154  characteristics stronger than 2^{-11}.
155--------------------------------------------------------------------
156*/
157#define mixc(a,b,c,d,e,f,g,h) \
158{ \
159    a^=b<<11; d+=a; b+=c; \
160    b^=c>>2;  e+=b; c+=d; \
161    c^=d<<8;  f+=c; d+=e; \
162    d^=e>>16; g+=d; e+=f; \
163    e^=f<<10; h+=e; f+=g; \
164    f^=g>>4;  a+=f; g+=h; \
165    g^=h<<8;  b+=g; h+=a; \
166    h^=a>>9;  c+=h; a+=b; \
167}
168
169/*
170--------------------------------------------------------------------
171checksum() -- hash a variable-length key into a 256-bit value
172  k     : the key (the unaligned variable-length array of bytes)
173  len   : the length of the key, counting by bytes
174  state : an array of CHECKSTATE 4-byte values (256 bits)
175The state is the checksum.  Every bit of the key affects every bit of
176the state.  There are no funnels.  About 112+6.875len instructions.
177
178If you are hashing n strings (ub1 **)k, do it like this:
179  for (i=0; i<8; ++i) state[i] = 0x9e3779b9;
180  for (i=0, h=0; i<n; ++i) checksum( k[i], len[i], state);
181
182(c) Bob Jenkins, 1996.  bob_jenkins@burtleburtle.net.  You may use this
183code any way you wish, private, educational, or commercial, as long
184as this whole comment accompanies it.
185
186See http://burtleburtle.net/bob/hash/evahash.html
187Use to detect changes between revisions of documents, assuming nobody
188is trying to cause collisions.  Do NOT use for cryptography.
189--------------------------------------------------------------------
190*/
191void
192phash_checksum(
193    register const char *sk,
194    register size_t len,
195    register unsigned long *state)
196{
197    register unsigned long a,b,c,d,e,f,g,h;
198    register size_t length;
199    register const unsigned char *k = (const unsigned char *)sk;
200
201    /* Use the length and level; add in the golden ratio. */
202    length = len;
203    a=state[0]; b=state[1]; c=state[2]; d=state[3];
204    e=state[4]; f=state[5]; g=state[6]; h=state[7];
205
206    /*---------------------------------------- handle most of the key */
207    while (len >= 32)
208    {
209        a += (k[0] +(k[1]<<8) +(k[2]<<16) +(k[3]<<24));
210        b += (k[4] +(k[5]<<8) +(k[6]<<16) +(k[7]<<24));
211        c += (k[8] +(k[9]<<8) +(k[10]<<16)+(k[11]<<24));
212        d += (k[12]+(k[13]<<8)+(k[14]<<16)+(k[15]<<24));
213        e += (k[16]+(k[17]<<8)+(k[18]<<16)+(k[19]<<24));
214        f += (k[20]+(k[21]<<8)+(k[22]<<16)+(k[23]<<24));
215        g += (k[24]+(k[25]<<8)+(k[26]<<16)+(k[27]<<24));
216        h += (k[28]+(k[29]<<8)+(k[30]<<16)+(k[31]<<24));
217        mixc(a,b,c,d,e,f,g,h);
218        mixc(a,b,c,d,e,f,g,h);
219        mixc(a,b,c,d,e,f,g,h);
220        mixc(a,b,c,d,e,f,g,h);
221        k += 32; len -= 32;
222    }
223
224    /*------------------------------------- handle the last 31 bytes */
225    h += (ub4)length;
226    switch(len)
227    {
228        case 31: h+=(k[30]<<24);
229        case 30: h+=(k[29]<<16);
230        case 29: h+=(k[28]<<8);
231        case 28: g+=(k[27]<<24);
232        case 27: g+=(k[26]<<16);
233        case 26: g+=(k[25]<<8);
234        case 25: g+=k[24];
235        case 24: f+=(k[23]<<24);
236        case 23: f+=(k[22]<<16);
237        case 22: f+=(k[21]<<8);
238        case 21: f+=k[20];
239        case 20: e+=(k[19]<<24);
240        case 19: e+=(k[18]<<16);
241        case 18: e+=(k[17]<<8);
242        case 17: e+=k[16];
243        case 16: d+=(k[15]<<24);
244        case 15: d+=(k[14]<<16);
245        case 14: d+=(k[13]<<8);
246        case 13: d+=k[12];
247        case 12: c+=(k[11]<<24);
248        case 11: c+=(k[10]<<16);
249        case 10: c+=(k[9]<<8);
250        case 9 : c+=k[8];
251        case 8 : b+=(k[7]<<24);
252        case 7 : b+=(k[6]<<16);
253        case 6 : b+=(k[5]<<8);
254        case 5 : b+=k[4];
255        case 4 : a+=(k[3]<<24);
256        case 3 : a+=(k[2]<<16);
257        case 2 : a+=(k[1]<<8);
258        case 1 : a+=k[0];
259    }
260    mixc(a,b,c,d,e,f,g,h);
261    mixc(a,b,c,d,e,f,g,h);
262    mixc(a,b,c,d,e,f,g,h);
263    mixc(a,b,c,d,e,f,g,h);
264
265    /*-------------------------------------------- report the result */
266    state[0]=a; state[1]=b; state[2]=c; state[3]=d;
267    state[4]=e; state[5]=f; state[6]=g; state[7]=h;
268}
269