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