1 /*
2 -------------------------------------------------------------------------------
3 lookup3.c, by Bob Jenkins, May 2006, Public Domain.
4
5 These are functions for producing 32-bit hashes for hash table lookup.
6 hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
7 are externally useful functions. Routines to test the hash are included
8 if SELF_TEST is defined. You can use this free for any purpose. It's in
9 the public domain. It has no warranty.
10
11 You probably want to use hashlittle(). hashlittle() and hashbig()
12 hash byte arrays. hashlittle() is is faster than hashbig() on
13 little-endian machines. Intel and AMD are little-endian machines.
14 On second thought, you probably want hashlittle2(), which is identical to
15 hashlittle() except it returns two 32-bit hashes for the price of one.
16 You could implement hashbig2() if you wanted but I haven't bothered here.
17
18 If you want to find a hash of, say, exactly 7 integers, do
19 a = i1; b = i2; c = i3;
20 mix(a,b,c);
21 a += i4; b += i5; c += i6;
22 mix(a,b,c);
23 a += i7;
24 final(a,b,c);
25 then use c as the hash value. If you have a variable length array of
26 4-byte integers to hash, use hashword(). If you have a byte array (like
27 a character string), use hashlittle(). If you have several byte arrays, or
28 a mix of things, see the comments above hashlittle().
29
30 Why is this so big? I read 12 bytes at a time into 3 4-byte integers,
31 then mix those integers. This is fast (you can do a lot more thorough
32 mixing with 12*3 instructions on 3 integers than you can with 3 instructions
33 on 1 byte), but shoehorning those bytes into integers efficiently is messy.
34 -------------------------------------------------------------------------------
35 */
36
37 #include <stdio.h> /* defines printf for tests */
38 #include <time.h> /* defines time_t for timings in the test */
39 #include <stdint.h> /* defines uint32_t etc */
40 #include <sys/param.h> /* attempt to define endianness */
41 #ifdef linux
42 # include <endian.h> /* attempt to define endianness */
43 #endif
44
45 /*
46 * My best guess at if you are big-endian or little-endian. This may
47 * need adjustment.
48 */
49 #if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \
50 __BYTE_ORDER == __LITTLE_ENDIAN) || \
51 (defined(i386) || defined(__i386__) || defined(__i486__) || \
52 defined(__i586__) || defined(__i686__) || defined(vax) || defined(MIPSEL))
53 # define HASH_LITTLE_ENDIAN 1
54 # define HASH_BIG_ENDIAN 0
55 #elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \
56 __BYTE_ORDER == __BIG_ENDIAN) || \
57 (defined(sparc) || defined(POWERPC) || defined(mc68000) || defined(sel))
58 # define HASH_LITTLE_ENDIAN 0
59 # define HASH_BIG_ENDIAN 1
60 #else
61 # define HASH_LITTLE_ENDIAN 0
62 # define HASH_BIG_ENDIAN 0
63 #endif
64
65 #pragma GCC diagnostic ignored "-Wswitch-default"
66 #pragma GCC diagnostic ignored "-Wunused-variable"
67
68 #define hashsize(n) ((uint32_t)1<<(n))
69 #define hashmask(n) (hashsize(n)-1)
70 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
71
72 /*
73 -------------------------------------------------------------------------------
74 mix -- mix 3 32-bit values reversibly.
75
76 This is reversible, so any information in (a,b,c) before mix() is
77 still in (a,b,c) after mix().
78
79 If four pairs of (a,b,c) inputs are run through mix(), or through
80 mix() in reverse, there are at least 32 bits of the output that
81 are sometimes the same for one pair and different for another pair.
82 This was tested for:
83 * pairs that differed by one bit, by two bits, in any combination
84 of top bits of (a,b,c), or in any combination of bottom bits of
85 (a,b,c).
86 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
87 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
88 is commonly produced by subtraction) look like a single 1-bit
89 difference.
90 * the base values were pseudorandom, all zero but one bit set, or
91 all zero plus a counter that starts at zero.
92
93 Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
94 satisfy this are
95 4 6 8 16 19 4
96 9 15 3 18 27 15
97 14 9 3 7 17 3
98 Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
99 for "differ" defined as + with a one-bit base and a two-bit delta. I
100 used http://burtleburtle.net/bob/hash/avalanche.html to choose
101 the operations, constants, and arrangements of the variables.
102
103 This does not achieve avalanche. There are input bits of (a,b,c)
104 that fail to affect some output bits of (a,b,c), especially of a. The
105 most thoroughly mixed value is c, but it doesn't really even achieve
106 avalanche in c.
107
108 This allows some parallelism. Read-after-writes are good at doubling
109 the number of bits affected, so the goal of mixing pulls in the opposite
110 direction as the goal of parallelism. I did what I could. Rotates
111 seem to cost as much as shifts on every machine I could lay my hands
112 on, and rotates are much kinder to the top and bottom bits, so I used
113 rotates.
114 -------------------------------------------------------------------------------
115 */
116 #define mix(a,b,c) \
117 { \
118 a -= c; a ^= rot(c, 4); c += b; \
119 b -= a; b ^= rot(a, 6); a += c; \
120 c -= b; c ^= rot(b, 8); b += a; \
121 a -= c; a ^= rot(c,16); c += b; \
122 b -= a; b ^= rot(a,19); a += c; \
123 c -= b; c ^= rot(b, 4); b += a; \
124 }
125
126 /*
127 -------------------------------------------------------------------------------
128 final -- final mixing of 3 32-bit values (a,b,c) into c
129
130 Pairs of (a,b,c) values differing in only a few bits will usually
131 produce values of c that look totally different. This was tested for
132 * pairs that differed by one bit, by two bits, in any combination
133 of top bits of (a,b,c), or in any combination of bottom bits of
134 (a,b,c).
135 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
136 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
137 is commonly produced by subtraction) look like a single 1-bit
138 difference.
139 * the base values were pseudorandom, all zero but one bit set, or
140 all zero plus a counter that starts at zero.
141
142 These constants passed:
143 14 11 25 16 4 14 24
144 12 14 25 16 4 14 24
145 and these came close:
146 4 8 15 26 3 22 24
147 10 8 15 26 3 22 24
148 11 8 15 26 3 22 24
149 -------------------------------------------------------------------------------
150 */
151 #define final(a,b,c) \
152 { \
153 c ^= b; c -= rot(b,14); \
154 a ^= c; a -= rot(c,11); \
155 b ^= a; b -= rot(a,25); \
156 c ^= b; c -= rot(b,16); \
157 a ^= c; a -= rot(c,4); \
158 b ^= a; b -= rot(a,14); \
159 c ^= b; c -= rot(b,24); \
160 }
161
162 /*
163 --------------------------------------------------------------------
164 This works on all machines. To be useful, it requires
165 -- that the key be an array of uint32_t's, and
166 -- that the length be the number of uint32_t's in the key
167
168 The function hashword() is identical to hashlittle() on little-endian
169 machines, and identical to hashbig() on big-endian machines,
170 except that the length has to be measured in uint32_ts rather than in
171 bytes. hashlittle() is more complicated than hashword() only because
172 hashlittle() has to dance around fitting the key bytes into registers.
173 --------------------------------------------------------------------
174 */
hashword(const uint32_t * k,size_t length,uint32_t initval)175 uint32_t hashword(
176 const uint32_t *k, /* the key, an array of uint32_t values */
177 size_t length, /* the length of the key, in uint32_ts */
178 uint32_t initval) /* the previous hash, or an arbitrary value */
179 {
180 uint32_t a,b,c;
181
182 /* Set up the internal state */
183 a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval;
184
185 /*------------------------------------------------- handle most of the key */
186 while (length > 3)
187 {
188 a += k[0];
189 b += k[1];
190 c += k[2];
191 mix(a,b,c);
192 length -= 3;
193 k += 3;
194 }
195
196 /*------------------------------------------- handle the last 3 uint32_t's */
197 switch(length) /* all the case statements fall through */
198 {
199 case 3 : c+=k[2];
200 case 2 : b+=k[1];
201 case 1 : a+=k[0];
202 final(a,b,c);
203 case 0: /* case 0: nothing left to add */
204 break;
205 }
206 /*------------------------------------------------------ report the result */
207 return c;
208 }
209
210
211 /*
212 --------------------------------------------------------------------
213 hashword2() -- same as hashword(), but take two seeds and return two
214 32-bit values. pc and pb must both be nonnull, and *pc and *pb must
215 both be initialized with seeds. If you pass in (*pb)==0, the output
216 (*pc) will be the same as the return value from hashword().
217 --------------------------------------------------------------------
218 */
hashword2(const uint32_t * k,size_t length,uint32_t * pc,uint32_t * pb)219 void hashword2 (
220 const uint32_t *k, /* the key, an array of uint32_t values */
221 size_t length, /* the length of the key, in uint32_ts */
222 uint32_t *pc, /* IN: seed OUT: primary hash value */
223 uint32_t *pb) /* IN: more seed OUT: secondary hash value */
224 {
225 uint32_t a,b,c;
226
227 /* Set up the internal state */
228 a = b = c = 0xdeadbeef + ((uint32_t)(length<<2)) + *pc;
229 c += *pb;
230
231 /*------------------------------------------------- handle most of the key */
232 while (length > 3)
233 {
234 a += k[0];
235 b += k[1];
236 c += k[2];
237 mix(a,b,c);
238 length -= 3;
239 k += 3;
240 }
241
242 /*------------------------------------------- handle the last 3 uint32_t's */
243 switch(length) /* all the case statements fall through */
244 {
245 case 3 : c+=k[2];
246 case 2 : b+=k[1];
247 case 1 : a+=k[0];
248 final(a,b,c);
249 case 0: /* case 0: nothing left to add */
250 break;
251 }
252 /*------------------------------------------------------ report the result */
253 *pc=c; *pb=b;
254 }
255
256
257 /*
258 -------------------------------------------------------------------------------
259 hashlittle() -- hash a variable-length key into a 32-bit value
260 k : the key (the unaligned variable-length array of bytes)
261 length : the length of the key, counting by bytes
262 initval : can be any 4-byte value
263 Returns a 32-bit value. Every bit of the key affects every bit of
264 the return value. Two keys differing by one or two bits will have
265 totally different hash values.
266
267 The best hash table sizes are powers of 2. There is no need to do
268 mod a prime (mod is sooo slow!). If you need less than 32 bits,
269 use a bitmask. For example, if you need only 10 bits, do
270 h = (h & hashmask(10));
271 In which case, the hash table should have hashsize(10) elements.
272
273 If you are hashing n strings (uint8_t **)k, do it like this:
274 for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
275
276 By Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this
277 code any way you wish, private, educational, or commercial. It's free.
278
279 Use for hash table lookup, or anything where one collision in 2^^32 is
280 acceptable. Do NOT use for cryptographic purposes.
281 -------------------------------------------------------------------------------
282 */
283
hashlittle(const void * key,size_t length,uint32_t initval)284 uint32_t hashlittle( const void *key, size_t length, uint32_t initval)
285 {
286 uint32_t a,b,c; /* internal state */
287 union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */
288
289 /* Set up the internal state */
290 a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
291
292 u.ptr = key;
293 if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
294 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
295 const uint8_t *k8;
296
297 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
298 while (length > 12)
299 {
300 a += k[0];
301 b += k[1];
302 c += k[2];
303 mix(a,b,c);
304 length -= 12;
305 k += 3;
306 }
307
308 /*----------------------------- handle the last (probably partial) block */
309 /*
310 * "k[2]&0xffffff" actually reads beyond the end of the string, but
311 * then masks off the part it's not allowed to read. Because the
312 * string is aligned, the masked-off tail is in the same word as the
313 * rest of the string. Every machine with memory protection I've seen
314 * does it on word boundaries, so is OK with this. But VALGRIND will
315 * still catch it and complain. The masking trick does make the hash
316 * noticably faster for short strings (like English words).
317 */
318 #ifndef VALGRIND
319
320 switch(length)
321 {
322 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
323 case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
324 case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
325 case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
326 case 8 : b+=k[1]; a+=k[0]; break;
327 case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
328 case 6 : b+=k[1]&0xffff; a+=k[0]; break;
329 case 5 : b+=k[1]&0xff; a+=k[0]; break;
330 case 4 : a+=k[0]; break;
331 case 3 : a+=k[0]&0xffffff; break;
332 case 2 : a+=k[0]&0xffff; break;
333 case 1 : a+=k[0]&0xff; break;
334 case 0 : return c; /* zero length strings require no mixing */
335 }
336
337 #else /* make valgrind happy */
338
339 k8 = (const uint8_t *)k;
340 switch(length)
341 {
342 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
343 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
344 case 10: c+=((uint32_t)k8[9])<<8; /* fall through */
345 case 9 : c+=k8[8]; /* fall through */
346 case 8 : b+=k[1]; a+=k[0]; break;
347 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
348 case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */
349 case 5 : b+=k8[4]; /* fall through */
350 case 4 : a+=k[0]; break;
351 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
352 case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */
353 case 1 : a+=k8[0]; break;
354 case 0 : return c;
355 }
356
357 #endif /* !valgrind */
358
359 } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
360 const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */
361 const uint8_t *k8;
362
363 /*--------------- all but last block: aligned reads and different mixing */
364 while (length > 12)
365 {
366 a += k[0] + (((uint32_t)k[1])<<16);
367 b += k[2] + (((uint32_t)k[3])<<16);
368 c += k[4] + (((uint32_t)k[5])<<16);
369 mix(a,b,c);
370 length -= 12;
371 k += 6;
372 }
373
374 /*----------------------------- handle the last (probably partial) block */
375 k8 = (const uint8_t *)k;
376 switch(length)
377 {
378 case 12: c+=k[4]+(((uint32_t)k[5])<<16);
379 b+=k[2]+(((uint32_t)k[3])<<16);
380 a+=k[0]+(((uint32_t)k[1])<<16);
381 break;
382 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
383 case 10: c+=k[4];
384 b+=k[2]+(((uint32_t)k[3])<<16);
385 a+=k[0]+(((uint32_t)k[1])<<16);
386 break;
387 case 9 : c+=k8[8]; /* fall through */
388 case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
389 a+=k[0]+(((uint32_t)k[1])<<16);
390 break;
391 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
392 case 6 : b+=k[2];
393 a+=k[0]+(((uint32_t)k[1])<<16);
394 break;
395 case 5 : b+=k8[4]; /* fall through */
396 case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
397 break;
398 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
399 case 2 : a+=k[0];
400 break;
401 case 1 : a+=k8[0];
402 break;
403 case 0 : return c; /* zero length requires no mixing */
404 }
405
406 } else { /* need to read the key one byte at a time */
407 const uint8_t *k = (const uint8_t *)key;
408
409 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
410 while (length > 12)
411 {
412 a += k[0];
413 a += ((uint32_t)k[1])<<8;
414 a += ((uint32_t)k[2])<<16;
415 a += ((uint32_t)k[3])<<24;
416 b += k[4];
417 b += ((uint32_t)k[5])<<8;
418 b += ((uint32_t)k[6])<<16;
419 b += ((uint32_t)k[7])<<24;
420 c += k[8];
421 c += ((uint32_t)k[9])<<8;
422 c += ((uint32_t)k[10])<<16;
423 c += ((uint32_t)k[11])<<24;
424 mix(a,b,c);
425 length -= 12;
426 k += 12;
427 }
428
429 /*-------------------------------- last block: affect all 32 bits of (c) */
430 switch(length) /* all the case statements fall through */
431 {
432 case 12: c+=((uint32_t)k[11])<<24;
433 case 11: c+=((uint32_t)k[10])<<16;
434 case 10: c+=((uint32_t)k[9])<<8;
435 case 9 : c+=k[8];
436 case 8 : b+=((uint32_t)k[7])<<24;
437 case 7 : b+=((uint32_t)k[6])<<16;
438 case 6 : b+=((uint32_t)k[5])<<8;
439 case 5 : b+=k[4];
440 case 4 : a+=((uint32_t)k[3])<<24;
441 case 3 : a+=((uint32_t)k[2])<<16;
442 case 2 : a+=((uint32_t)k[1])<<8;
443 case 1 : a+=k[0];
444 break;
445 case 0 : return c;
446 }
447 }
448
449 final(a,b,c);
450 return c;
451 }
452
453
454 /*
455 * hashlittle2: return 2 32-bit hash values
456 *
457 * This is identical to hashlittle(), except it returns two 32-bit hash
458 * values instead of just one. This is good enough for hash table
459 * lookup with 2^^64 buckets, or if you want a second hash if you're not
460 * happy with the first, or if you want a probably-unique 64-bit ID for
461 * the key. *pc is better mixed than *pb, so use *pc first. If you want
462 * a 64-bit value do something like "*pc + (((uint64_t)*pb)<<32)".
463 */
hashlittle2(const void * key,size_t length,uint32_t * pc,uint32_t * pb)464 void hashlittle2(
465 const void *key, /* the key to hash */
466 size_t length, /* length of the key */
467 uint32_t *pc, /* IN: primary initval, OUT: primary hash */
468 uint32_t *pb) /* IN: secondary initval, OUT: secondary hash */
469 {
470 uint32_t a,b,c; /* internal state */
471 union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */
472
473 /* Set up the internal state */
474 a = b = c = 0xdeadbeef + ((uint32_t)length) + *pc;
475 c += *pb;
476
477 u.ptr = key;
478 if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
479 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
480 const uint8_t *k8;
481
482 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
483 while (length > 12)
484 {
485 a += k[0];
486 b += k[1];
487 c += k[2];
488 mix(a,b,c);
489 length -= 12;
490 k += 3;
491 }
492
493 /*----------------------------- handle the last (probably partial) block */
494 /*
495 * "k[2]&0xffffff" actually reads beyond the end of the string, but
496 * then masks off the part it's not allowed to read. Because the
497 * string is aligned, the masked-off tail is in the same word as the
498 * rest of the string. Every machine with memory protection I've seen
499 * does it on word boundaries, so is OK with this. But VALGRIND will
500 * still catch it and complain. The masking trick does make the hash
501 * noticably faster for short strings (like English words).
502 */
503 #ifndef VALGRIND
504
505 switch(length)
506 {
507 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
508 case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
509 case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
510 case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
511 case 8 : b+=k[1]; a+=k[0]; break;
512 case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
513 case 6 : b+=k[1]&0xffff; a+=k[0]; break;
514 case 5 : b+=k[1]&0xff; a+=k[0]; break;
515 case 4 : a+=k[0]; break;
516 case 3 : a+=k[0]&0xffffff; break;
517 case 2 : a+=k[0]&0xffff; break;
518 case 1 : a+=k[0]&0xff; break;
519 case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */
520 }
521
522 #else /* make valgrind happy */
523
524 k8 = (const uint8_t *)k;
525 switch(length)
526 {
527 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
528 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
529 case 10: c+=((uint32_t)k8[9])<<8; /* fall through */
530 case 9 : c+=k8[8]; /* fall through */
531 case 8 : b+=k[1]; a+=k[0]; break;
532 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
533 case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */
534 case 5 : b+=k8[4]; /* fall through */
535 case 4 : a+=k[0]; break;
536 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
537 case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */
538 case 1 : a+=k8[0]; break;
539 case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */
540 }
541
542 #endif /* !valgrind */
543
544 } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
545 const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */
546 const uint8_t *k8;
547
548 /*--------------- all but last block: aligned reads and different mixing */
549 while (length > 12)
550 {
551 a += k[0] + (((uint32_t)k[1])<<16);
552 b += k[2] + (((uint32_t)k[3])<<16);
553 c += k[4] + (((uint32_t)k[5])<<16);
554 mix(a,b,c);
555 length -= 12;
556 k += 6;
557 }
558
559 /*----------------------------- handle the last (probably partial) block */
560 k8 = (const uint8_t *)k;
561 switch(length)
562 {
563 case 12: c+=k[4]+(((uint32_t)k[5])<<16);
564 b+=k[2]+(((uint32_t)k[3])<<16);
565 a+=k[0]+(((uint32_t)k[1])<<16);
566 break;
567 case 11: c+=((uint32_t)k8[10])<<16; /* fall through */
568 case 10: c+=k[4];
569 b+=k[2]+(((uint32_t)k[3])<<16);
570 a+=k[0]+(((uint32_t)k[1])<<16);
571 break;
572 case 9 : c+=k8[8]; /* fall through */
573 case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
574 a+=k[0]+(((uint32_t)k[1])<<16);
575 break;
576 case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */
577 case 6 : b+=k[2];
578 a+=k[0]+(((uint32_t)k[1])<<16);
579 break;
580 case 5 : b+=k8[4]; /* fall through */
581 case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
582 break;
583 case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */
584 case 2 : a+=k[0];
585 break;
586 case 1 : a+=k8[0];
587 break;
588 case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */
589 }
590
591 } else { /* need to read the key one byte at a time */
592 const uint8_t *k = (const uint8_t *)key;
593
594 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
595 while (length > 12)
596 {
597 a += k[0];
598 a += ((uint32_t)k[1])<<8;
599 a += ((uint32_t)k[2])<<16;
600 a += ((uint32_t)k[3])<<24;
601 b += k[4];
602 b += ((uint32_t)k[5])<<8;
603 b += ((uint32_t)k[6])<<16;
604 b += ((uint32_t)k[7])<<24;
605 c += k[8];
606 c += ((uint32_t)k[9])<<8;
607 c += ((uint32_t)k[10])<<16;
608 c += ((uint32_t)k[11])<<24;
609 mix(a,b,c);
610 length -= 12;
611 k += 12;
612 }
613
614 /*-------------------------------- last block: affect all 32 bits of (c) */
615 switch(length) /* all the case statements fall through */
616 {
617 case 12: c+=((uint32_t)k[11])<<24;
618 case 11: c+=((uint32_t)k[10])<<16;
619 case 10: c+=((uint32_t)k[9])<<8;
620 case 9 : c+=k[8];
621 case 8 : b+=((uint32_t)k[7])<<24;
622 case 7 : b+=((uint32_t)k[6])<<16;
623 case 6 : b+=((uint32_t)k[5])<<8;
624 case 5 : b+=k[4];
625 case 4 : a+=((uint32_t)k[3])<<24;
626 case 3 : a+=((uint32_t)k[2])<<16;
627 case 2 : a+=((uint32_t)k[1])<<8;
628 case 1 : a+=k[0];
629 break;
630 case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */
631 }
632 }
633
634 final(a,b,c);
635 *pc=c; *pb=b;
636 }
637
638
639
640 /*
641 * hashbig():
642 * This is the same as hashword() on big-endian machines. It is different
643 * from hashlittle() on all machines. hashbig() takes advantage of
644 * big-endian byte ordering.
645 */
hashbig(const void * key,size_t length,uint32_t initval)646 uint32_t hashbig( const void *key, size_t length, uint32_t initval)
647 {
648 uint32_t a,b,c;
649 union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */
650
651 /* Set up the internal state */
652 a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
653
654 u.ptr = key;
655 if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) {
656 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
657 const uint8_t *k8;
658
659 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
660 while (length > 12)
661 {
662 a += k[0];
663 b += k[1];
664 c += k[2];
665 mix(a,b,c);
666 length -= 12;
667 k += 3;
668 }
669
670 /*----------------------------- handle the last (probably partial) block */
671 /*
672 * "k[2]<<8" actually reads beyond the end of the string, but
673 * then shifts out the part it's not allowed to read. Because the
674 * string is aligned, the illegal read is in the same word as the
675 * rest of the string. Every machine with memory protection I've seen
676 * does it on word boundaries, so is OK with this. But VALGRIND will
677 * still catch it and complain. The masking trick does make the hash
678 * noticably faster for short strings (like English words).
679 */
680 #ifndef VALGRIND
681
682 switch(length)
683 {
684 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
685 case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break;
686 case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break;
687 case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break;
688 case 8 : b+=k[1]; a+=k[0]; break;
689 case 7 : b+=k[1]&0xffffff00; a+=k[0]; break;
690 case 6 : b+=k[1]&0xffff0000; a+=k[0]; break;
691 case 5 : b+=k[1]&0xff000000; a+=k[0]; break;
692 case 4 : a+=k[0]; break;
693 case 3 : a+=k[0]&0xffffff00; break;
694 case 2 : a+=k[0]&0xffff0000; break;
695 case 1 : a+=k[0]&0xff000000; break;
696 case 0 : return c; /* zero length strings require no mixing */
697 }
698
699 #else /* make valgrind happy */
700
701 k8 = (const uint8_t *)k;
702 switch(length) /* all the case statements fall through */
703 {
704 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
705 case 11: c+=((uint32_t)k8[10])<<8; /* fall through */
706 case 10: c+=((uint32_t)k8[9])<<16; /* fall through */
707 case 9 : c+=((uint32_t)k8[8])<<24; /* fall through */
708 case 8 : b+=k[1]; a+=k[0]; break;
709 case 7 : b+=((uint32_t)k8[6])<<8; /* fall through */
710 case 6 : b+=((uint32_t)k8[5])<<16; /* fall through */
711 case 5 : b+=((uint32_t)k8[4])<<24; /* fall through */
712 case 4 : a+=k[0]; break;
713 case 3 : a+=((uint32_t)k8[2])<<8; /* fall through */
714 case 2 : a+=((uint32_t)k8[1])<<16; /* fall through */
715 case 1 : a+=((uint32_t)k8[0])<<24; break;
716 case 0 : return c;
717 }
718
719 #endif /* !VALGRIND */
720
721 } else { /* need to read the key one byte at a time */
722 const uint8_t *k = (const uint8_t *)key;
723
724 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
725 while (length > 12)
726 {
727 a += ((uint32_t)k[0])<<24;
728 a += ((uint32_t)k[1])<<16;
729 a += ((uint32_t)k[2])<<8;
730 a += ((uint32_t)k[3]);
731 b += ((uint32_t)k[4])<<24;
732 b += ((uint32_t)k[5])<<16;
733 b += ((uint32_t)k[6])<<8;
734 b += ((uint32_t)k[7]);
735 c += ((uint32_t)k[8])<<24;
736 c += ((uint32_t)k[9])<<16;
737 c += ((uint32_t)k[10])<<8;
738 c += ((uint32_t)k[11]);
739 mix(a,b,c);
740 length -= 12;
741 k += 12;
742 }
743
744 /*-------------------------------- last block: affect all 32 bits of (c) */
745 switch(length) /* all the case statements fall through */
746 {
747 case 12: c+=k[11];
748 case 11: c+=((uint32_t)k[10])<<8;
749 case 10: c+=((uint32_t)k[9])<<16;
750 case 9 : c+=((uint32_t)k[8])<<24;
751 case 8 : b+=k[7];
752 case 7 : b+=((uint32_t)k[6])<<8;
753 case 6 : b+=((uint32_t)k[5])<<16;
754 case 5 : b+=((uint32_t)k[4])<<24;
755 case 4 : a+=k[3];
756 case 3 : a+=((uint32_t)k[2])<<8;
757 case 2 : a+=((uint32_t)k[1])<<16;
758 case 1 : a+=((uint32_t)k[0])<<24;
759 break;
760 case 0 : return c;
761 }
762 }
763
764 final(a,b,c);
765 return c;
766 }
767
768
769