1/*
2Copyright (c) 2012, Broadcom Europe Ltd
3All rights reserved.
4
5Redistribution and use in source and binary forms, with or without
6modification, are permitted provided that the following conditions are met:
7 * Redistributions of source code must retain the above copyright
8 notice, this list of conditions and the following disclaimer.
9 * Redistributions in binary form must reproduce the above copyright
10 notice, this list of conditions and the following disclaimer in the
11 documentation and/or other materials provided with the distribution.
12 * Neither the name of the copyright holder nor the
13 names of its contributors may be used to endorse or promote products
14 derived from this software without specific prior written permission.
15
16THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
17ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY
20DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26*/
27
28/*
29-------------------------------------------------------------------------------
30These are functions for producing 32-bit hashes for hash table lookup.
31khrn_hashword(), khrn_hashlittle(), hashlittle2(), hashbig(), mix(), and final()
32are externally useful functions. Routines to test the hash are included
33if SELF_TEST is defined. You can use this free for any purpose. It's in
34the public domain. It has no warranty.
35
36You probably want to use khrn_hashlittle(). khrn_hashlittle() and hashbig()
37hash byte arrays. khrn_hashlittle() is is faster than hashbig() on
38little-endian machines. Intel and AMD are little-endian machines.
39On second thought, you probably want hashlittle2(), which is identical to
40khrn_hashlittle() except it returns two 32-bit hashes for the price of one.
41You could implement hashbig2() if you wanted but I haven't bothered here.
42
43If you want to find a hash of, say, exactly 7 integers, do
44 a = i1; b = i2; c = i3;
45 mix(a,b,c);
46 a += i4; b += i5; c += i6;
47 mix(a,b,c);
48 a += i7;
49 final(a,b,c);
50then use c as the hash value. If you have a variable length array of
514-byte integers to hash, use khrn_hashword(). If you have a byte array (like
52a character string), use khrn_hashlittle(). If you have several byte arrays, or
53a mix of things, see the comments above khrn_hashlittle().
54
55Why is this so big? I read 12 bytes at a time into 3 4-byte integers,
56then mix those integers. This is fast (you can do a lot more thorough
57mixing with 12*3 instructions on 3 integers than you can with 3 instructions
58on 1 byte), but shoehorning those bytes into integers efficiently is messy.
59-------------------------------------------------------------------------------
60*/
61
62#include "interface/khronos/common/khrn_int_common.h"
63
64#include "interface/khronos/common/khrn_int_hash.h" // get definitions of rot, mix and final
65
66# define HASH_LITTLE_ENDIAN 1
67# define HASH_BIG_ENDIAN 0
68
69#ifndef __arm__ // Use the version in khrn_int_hash_asm.s instead
70/*
71--------------------------------------------------------------------
72 This works on all machines. To be useful, it requires
73 -- that the key be an array of uint32_t's, and
74 -- that the length be the number of uint32_t's in the key
75
76 The function khrn_hashword() is identical to khrn_hashlittle() on little-endian
77 machines, and identical to hashbig() on big-endian machines,
78 except that the length has to be measured in uint32_ts rather than in
79 bytes. khrn_hashlittle() is more complicated than khrn_hashword() only because
80 khrn_hashlittle() has to dance around fitting the key bytes into registers.
81--------------------------------------------------------------------
82*/
83uint32_t khrn_hashword(
84const uint32_t *k, /* the key, an array of uint32_t values */
85int length, /* the length of the key, in uint32_ts */
86uint32_t initval) /* the previous hash, or an arbitrary value */
87{
88 uint32_t a,b,c;
89 /* Set up the internal state */
90 a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval;
91 /*------------------------------------------------- handle most of the key */
92 while (length > 3)
93 {
94 a += k[0];
95 b += k[1];
96 c += k[2];
97 mix(a,b,c);
98 length -= 3;
99 k += 3;
100 }
101
102 /*------------------------------------------- handle the last 3 uint32_t's */
103 switch(length) /* all the case statements fall through */
104 {
105 case 3 : c+=k[2];
106 case 2 : b+=k[1];
107 case 1 : a+=k[0];
108 final(a,b,c);
109 case 0: /* case 0: nothing left to add */
110 break;
111 }
112 /*------------------------------------------------------ report the result */
113 return c;
114}
115
116#endif
117
118/*
119-------------------------------------------------------------------------------
120khrn_hashlittle() -- hash a variable-length key into a 32-bit value
121 k : the key (the unaligned variable-length array of bytes)
122 length : the length of the key, counting by bytes
123 initval : can be any 4-byte value
124Returns a 32-bit value. Every bit of the key affects every bit of
125the return value. Two keys differing by one or two bits will have
126totally different hash values.
127
128The best hash table sizes are powers of 2. There is no need to do
129mod a prime (mod is sooo slow!). If you need less than 32 bits,
130use a bitmask. For example, if you need only 10 bits, do
131 h = (h & hashmask(10));
132In which case, the hash table should have hashsize(10) elements.
133
134If you are hashing n strings (uint8_t **)k, do it like this:
135 for (i=0, h=0; i<n; ++i) h = khrn_hashlittle( k[i], len[i], h);
136
137By Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this
138code any way you wish, private, educational, or commercial. It's free.
139
140Use for hash table lookup, or anything where one collision in 2^^32 is
141acceptable. Do NOT use for cryptographic purposes.
142-------------------------------------------------------------------------------
143*/
144uint32_t khrn_hashlittle( const void *key, int length, uint32_t initval)
145{
146 uint32_t a,b,c; /* internal state */
147 union { const void *ptr; int i; } u; /* needed for Mac Powerbook G4 */
148
149 /* Set up the internal state */
150 a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
151
152 u.ptr = key;
153 if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
154 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
155
156 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
157 while (length > 12)
158 {
159 a += k[0];
160 b += k[1];
161 c += k[2];
162 mix(a,b,c);
163 length -= 12;
164 k += 3;
165 }
166
167 /*----------------------------- handle the last (probably partial) block */
168 /*
169 * "k[2]&0xffffff" actually reads beyond the end of the string, but
170 * then masks off the part it's not allowed to read. Because the
171 * string is aligned, the masked-off tail is in the same word as the
172 * rest of the string. Every machine with memory protection I've seen
173 * does it on word boundaries, so is OK with this. But VALGRIND will
174 * still catch it and complain. The masking trick does make the hash
175 * noticeably faster for short strings (like English words).
176 */
177#ifndef VALGRIND
178
179 switch(length)
180 {
181 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
182 case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
183 case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
184 case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
185 case 8 : b+=k[1]; a+=k[0]; break;
186 case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
187 case 6 : b+=k[1]&0xffff; a+=k[0]; break;
188 case 5 : b+=k[1]&0xff; a+=k[0]; break;
189 case 4 : a+=k[0]; break;
190 case 3 : a+=k[0]&0xffffff; break;
191 case 2 : a+=k[0]&0xffff; break;
192 case 1 : a+=k[0]&0xff; break;
193 case 0 : return c; /* zero length strings require no mixing */
194 }
195
196#else /* make valgrind happy */
197
198 k8 = (const uint8_t *)k;
199 switch(length)
200 {
201 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
202 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
203 case 10: c+=((uint32_t)k8[9])<<8; /* fall through */
204 case 9 : c+=k8[8]; /* fall through */
205 case 8 : b+=k[1]; a+=k[0]; break;
206 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
207 case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */
208 case 5 : b+=k8[4]; /* fall through */
209 case 4 : a+=k[0]; break;
210 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
211 case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */
212 case 1 : a+=k8[0]; break;
213 case 0 : return c;
214 }
215
216#endif /* !valgrind */
217
218 } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
219 const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */
220 const uint8_t *k8;
221
222 /*--------------- all but last block: aligned reads and different mixing */
223 while (length > 12)
224 {
225 a += k[0] + (((uint32_t)k[1])<<16);
226 b += k[2] + (((uint32_t)k[3])<<16);
227 c += k[4] + (((uint32_t)k[5])<<16);
228 mix(a,b,c);
229 length -= 12;
230 k += 6;
231 }
232
233 /*----------------------------- handle the last (probably partial) block */
234 k8 = (const uint8_t *)k;
235 switch(length)
236 {
237 case 12: c+=k[4]+(((uint32_t)k[5])<<16);
238 b+=k[2]+(((uint32_t)k[3])<<16);
239 a+=k[0]+(((uint32_t)k[1])<<16);
240 break;
241 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
242 case 10: c+=k[4];
243 b+=k[2]+(((uint32_t)k[3])<<16);
244 a+=k[0]+(((uint32_t)k[1])<<16);
245 break;
246 case 9 : c+=k8[8]; /* fall through */
247 case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
248 a+=k[0]+(((uint32_t)k[1])<<16);
249 break;
250 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
251 case 6 : b+=k[2];
252 a+=k[0]+(((uint32_t)k[1])<<16);
253 break;
254 case 5 : b+=k8[4]; /* fall through */
255 case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
256 break;
257 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
258 case 2 : a+=k[0];
259 break;
260 case 1 : a+=k8[0];
261 break;
262 case 0 : return c; /* zero length requires no mixing */
263 }
264
265 } else { /* need to read the key one byte at a time */
266 const uint8_t *k = (const uint8_t *)key;
267
268 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
269 while (length > 12)
270 {
271 a += k[0];
272 a += ((uint32_t)k[1])<<8;
273 a += ((uint32_t)k[2])<<16;
274 a += ((uint32_t)k[3])<<24;
275 b += k[4];
276 b += ((uint32_t)k[5])<<8;
277 b += ((uint32_t)k[6])<<16;
278 b += ((uint32_t)k[7])<<24;
279 c += k[8];
280 c += ((uint32_t)k[9])<<8;
281 c += ((uint32_t)k[10])<<16;
282 c += ((uint32_t)k[11])<<24;
283 mix(a,b,c);
284 length -= 12;
285 k += 12;
286 }
287
288 /*-------------------------------- last block: affect all 32 bits of (c) */
289 switch(length) /* all the case statements fall through */
290 { /* Comments to pacify Coverity */
291 case 12: c+=((uint32_t)k[11])<<24; /* fall through */
292 case 11: c+=((uint32_t)k[10])<<16; /* fall through */
293 case 10: c+=((uint32_t)k[9])<<8; /* fall through */
294 case 9 : c+=k[8]; /* fall through */
295 case 8 : b+=((uint32_t)k[7])<<24; /* fall through */
296 case 7 : b+=((uint32_t)k[6])<<16; /* fall through */
297 case 6 : b+=((uint32_t)k[5])<<8; /* fall through */
298 case 5 : b+=k[4]; /* fall through */
299 case 4 : a+=((uint32_t)k[3])<<24; /* fall through */
300 case 3 : a+=((uint32_t)k[2])<<16; /* fall through */
301 case 2 : a+=((uint32_t)k[1])<<8; /* fall through */
302 case 1 : a+=k[0];
303 break;
304 case 0 : return c;
305 }
306 }
307
308 final(a,b,c);
309 return c;
310}
311