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