1 /*
2 May 2019(Wouter) patch to enable the valgrind clean implementation all the
3 time. This enables better security audit and checks, which is better
4 than the speedup. Git issue #30. Renamed the define ARRAY_CLEAN_ACCESS.
5 February 2013(Wouter) patch defines for BSD endianness, from Brad Smith.
6 January 2012(Wouter) added randomised initial value, fallout from 28c3.
7 March 2007(Wouter) adapted from lookup3.c original, add config.h include.
8 added #ifdef VALGRIND to remove 298,384,660 'unused variable k8' warnings.
9 added include of lookup3.h to check definitions match declarations.
10 removed include of stdint - config.h takes care of platform independence.
11 added fallthrough comments for new gcc warning suppression.
12 url http://burtleburtle.net/bob/hash/index.html.
13 */
14 /*
15 -------------------------------------------------------------------------------
16 lookup3.c, by Bob Jenkins, May 2006, Public Domain.
17
18 These are functions for producing 32-bit hashes for hash table lookup.
19 hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
20 are externally useful functions. Routines to test the hash are included
21 if SELF_TEST is defined. You can use this free for any purpose. It's in
22 the public domain. It has no warranty.
23
24 You probably want to use hashlittle(). hashlittle() and hashbig()
25 hash byte arrays. hashlittle() is is faster than hashbig() on
26 little-endian machines. Intel and AMD are little-endian machines.
27 On second thought, you probably want hashlittle2(), which is identical to
28 hashlittle() except it returns two 32-bit hashes for the price of one.
29 You could implement hashbig2() if you wanted but I haven't bothered here.
30
31 If you want to find a hash of, say, exactly 7 integers, do
32 a = i1; b = i2; c = i3;
33 mix(a,b,c);
34 a += i4; b += i5; c += i6;
35 mix(a,b,c);
36 a += i7;
37 final(a,b,c);
38 then use c as the hash value. If you have a variable length array of
39 4-byte integers to hash, use hashword(). If you have a byte array (like
40 a character string), use hashlittle(). If you have several byte arrays, or
41 a mix of things, see the comments above hashlittle().
42
43 Why is this so big? I read 12 bytes at a time into 3 4-byte integers,
44 then mix those integers. This is fast (you can do a lot more thorough
45 mixing with 12*3 instructions on 3 integers than you can with 3 instructions
46 on 1 byte), but shoehorning those bytes into integers efficiently is messy.
47 -------------------------------------------------------------------------------
48 */
49 /*#define SELF_TEST 1*/
50 #define ARRAY_CLEAN_ACCESS 1
51
52 #include "config.h"
53 #include "util/storage/lookup3.h"
54 #include <stdio.h> /* defines printf for tests */
55 #include <time.h> /* defines time_t for timings in the test */
56
57 /*
58 * If our build system provides endianness info, signalled by
59 * HAVE_TARGET_ENDIANNESS and the presence or absence of TARGET_IS_BIG_ENDIAN,
60 * use that. Otherwise try to work out the endianness.
61 */
62 #if defined(HAVE_TARGET_ENDIANNESS)
63 # if defined(TARGET_IS_BIG_ENDIAN)
64 # define HASH_LITTLE_ENDIAN 0
65 # define HASH_BIG_ENDIAN 1
66 # else
67 # define HASH_LITTLE_ENDIAN 1
68 # define HASH_BIG_ENDIAN 0
69 # endif
70 #else
71 # include <sys/param.h> /* attempt to define endianness */
72 # ifdef HAVE_SYS_TYPES_H
73 # include <sys/types.h> /* attempt to define endianness (solaris) */
74 # endif
75 # if defined(linux) || defined(__OpenBSD__)
76 # ifdef HAVE_ENDIAN_H
77 # include <endian.h> /* attempt to define endianness */
78 # else
79 # include <machine/endian.h> /* on older OpenBSD */
80 # endif
81 # endif
82 # if defined(__FreeBSD__) || defined(__NetBSD__) || defined(__DragonFly__)
83 # include <sys/endian.h> /* attempt to define endianness */
84 # endif
85 /*
86 * My best guess at if you are big-endian or little-endian. This may
87 * need adjustment.
88 */
89 # if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \
90 __BYTE_ORDER == __LITTLE_ENDIAN) || \
91 (defined(i386) || defined(__i386__) || defined(__i486__) || \
92 defined(__i586__) || defined(__i686__) || defined(vax) || defined(MIPSEL) || defined(__x86) || defined(__loongarch__))
93 # define HASH_LITTLE_ENDIAN 1
94 # define HASH_BIG_ENDIAN 0
95 # elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \
96 __BYTE_ORDER == __BIG_ENDIAN) || \
97 (defined(sparc) || defined(__sparc) || defined(__sparc__) || defined(POWERPC) || defined(mc68000) || defined(sel))
98 # define HASH_LITTLE_ENDIAN 0
99 # define HASH_BIG_ENDIAN 1
100 # elif defined(_MACHINE_ENDIAN_H_)
101 /* test for machine_endian_h protects failure if some are empty strings */
102 # if defined(_BYTE_ORDER) && defined(_BIG_ENDIAN) && _BYTE_ORDER == _BIG_ENDIAN
103 # define HASH_LITTLE_ENDIAN 0
104 # define HASH_BIG_ENDIAN 1
105 # endif
106 # if defined(_BYTE_ORDER) && defined(_LITTLE_ENDIAN) && _BYTE_ORDER == _LITTLE_ENDIAN
107 # define HASH_LITTLE_ENDIAN 1
108 # define HASH_BIG_ENDIAN 0
109 # endif /* _MACHINE_ENDIAN_H_ */
110 # else
111 # define HASH_LITTLE_ENDIAN 0
112 # define HASH_BIG_ENDIAN 0
113 # endif
114 #endif /* defined(HAVE_TARGET_ENDIANNESS) */
115
116 #define hashsize(n) ((uint32_t)1<<(n))
117 #define hashmask(n) (hashsize(n)-1)
118 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
119
120 /* random initial value */
121 static uint32_t raninit = (uint32_t)0xdeadbeef;
122
123 void
hash_set_raninit(uint32_t v)124 hash_set_raninit(uint32_t v)
125 {
126 raninit = v;
127 }
128
129 /*
130 -------------------------------------------------------------------------------
131 mix -- mix 3 32-bit values reversibly.
132
133 This is reversible, so any information in (a,b,c) before mix() is
134 still in (a,b,c) after mix().
135
136 If four pairs of (a,b,c) inputs are run through mix(), or through
137 mix() in reverse, there are at least 32 bits of the output that
138 are sometimes the same for one pair and different for another pair.
139 This was tested for:
140 * pairs that differed by one bit, by two bits, in any combination
141 of top bits of (a,b,c), or in any combination of bottom bits of
142 (a,b,c).
143 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
144 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
145 is commonly produced by subtraction) look like a single 1-bit
146 difference.
147 * the base values were pseudorandom, all zero but one bit set, or
148 all zero plus a counter that starts at zero.
149
150 Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
151 satisfy this are
152 4 6 8 16 19 4
153 9 15 3 18 27 15
154 14 9 3 7 17 3
155 Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
156 for "differ" defined as + with a one-bit base and a two-bit delta. I
157 used http://burtleburtle.net/bob/hash/avalanche.html to choose
158 the operations, constants, and arrangements of the variables.
159
160 This does not achieve avalanche. There are input bits of (a,b,c)
161 that fail to affect some output bits of (a,b,c), especially of a. The
162 most thoroughly mixed value is c, but it doesn't really even achieve
163 avalanche in c.
164
165 This allows some parallelism. Read-after-writes are good at doubling
166 the number of bits affected, so the goal of mixing pulls in the opposite
167 direction as the goal of parallelism. I did what I could. Rotates
168 seem to cost as much as shifts on every machine I could lay my hands
169 on, and rotates are much kinder to the top and bottom bits, so I used
170 rotates.
171 -------------------------------------------------------------------------------
172 */
173 #define mix(a,b,c) \
174 { \
175 a -= c; a ^= rot(c, 4); c += b; \
176 b -= a; b ^= rot(a, 6); a += c; \
177 c -= b; c ^= rot(b, 8); b += a; \
178 a -= c; a ^= rot(c,16); c += b; \
179 b -= a; b ^= rot(a,19); a += c; \
180 c -= b; c ^= rot(b, 4); b += a; \
181 }
182
183 /*
184 -------------------------------------------------------------------------------
185 final -- final mixing of 3 32-bit values (a,b,c) into c
186
187 Pairs of (a,b,c) values differing in only a few bits will usually
188 produce values of c that look totally different. This was tested for
189 * pairs that differed by one bit, by two bits, in any combination
190 of top bits of (a,b,c), or in any combination of bottom bits of
191 (a,b,c).
192 * "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
193 the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
194 is commonly produced by subtraction) look like a single 1-bit
195 difference.
196 * the base values were pseudorandom, all zero but one bit set, or
197 all zero plus a counter that starts at zero.
198
199 These constants passed:
200 14 11 25 16 4 14 24
201 12 14 25 16 4 14 24
202 and these came close:
203 4 8 15 26 3 22 24
204 10 8 15 26 3 22 24
205 11 8 15 26 3 22 24
206 -------------------------------------------------------------------------------
207 */
208 #define final(a,b,c) \
209 { \
210 c ^= b; c -= rot(b,14); \
211 a ^= c; a -= rot(c,11); \
212 b ^= a; b -= rot(a,25); \
213 c ^= b; c -= rot(b,16); \
214 a ^= c; a -= rot(c,4); \
215 b ^= a; b -= rot(a,14); \
216 c ^= b; c -= rot(b,24); \
217 }
218
219 /*
220 --------------------------------------------------------------------
221 This works on all machines. To be useful, it requires
222 -- that the key be an array of uint32_t's, and
223 -- that the length be the number of uint32_t's in the key
224
225 The function hashword() is identical to hashlittle() on little-endian
226 machines, and identical to hashbig() on big-endian machines,
227 except that the length has to be measured in uint32_ts rather than in
228 bytes. hashlittle() is more complicated than hashword() only because
229 hashlittle() has to dance around fitting the key bytes into registers.
230 --------------------------------------------------------------------
231 */
hashword(const uint32_t * k,size_t length,uint32_t initval)232 uint32_t hashword(
233 const uint32_t *k, /* the key, an array of uint32_t values */
234 size_t length, /* the length of the key, in uint32_ts */
235 uint32_t initval) /* the previous hash, or an arbitrary value */
236 {
237 uint32_t a,b,c;
238
239 /* Set up the internal state */
240 a = b = c = raninit + (((uint32_t)length)<<2) + initval;
241
242 /*------------------------------------------------- handle most of the key */
243 while (length > 3)
244 {
245 a += k[0];
246 b += k[1];
247 c += k[2];
248 mix(a,b,c);
249 length -= 3;
250 k += 3;
251 }
252
253 /*------------------------------------------- handle the last 3 uint32_t's */
254 switch(length) /* all the case statements fall through */
255 {
256 case 3 : c+=k[2];
257 ATTR_FALLTHROUGH
258 /* fallthrough */
259 case 2 : b+=k[1];
260 ATTR_FALLTHROUGH
261 /* fallthrough */
262 case 1 : a+=k[0];
263 final(a,b,c);
264 ATTR_FALLTHROUGH
265 /* fallthrough */
266 case 0: /* case 0: nothing left to add */
267 break;
268 }
269 /*------------------------------------------------------ report the result */
270 return c;
271 }
272
273
274 #ifdef SELF_TEST
275
276 /*
277 --------------------------------------------------------------------
278 hashword2() -- same as hashword(), but take two seeds and return two
279 32-bit values. pc and pb must both be nonnull, and *pc and *pb must
280 both be initialized with seeds. If you pass in (*pb)==0, the output
281 (*pc) will be the same as the return value from hashword().
282 --------------------------------------------------------------------
283 */
hashword2(const uint32_t * k,size_t length,uint32_t * pc,uint32_t * pb)284 void hashword2 (
285 const uint32_t *k, /* the key, an array of uint32_t values */
286 size_t length, /* the length of the key, in uint32_ts */
287 uint32_t *pc, /* IN: seed OUT: primary hash value */
288 uint32_t *pb) /* IN: more seed OUT: secondary hash value */
289 {
290 uint32_t a,b,c;
291
292 /* Set up the internal state */
293 a = b = c = raninit + ((uint32_t)(length<<2)) + *pc;
294 c += *pb;
295
296 /*------------------------------------------------- handle most of the key */
297 while (length > 3)
298 {
299 a += k[0];
300 b += k[1];
301 c += k[2];
302 mix(a,b,c);
303 length -= 3;
304 k += 3;
305 }
306
307 /*------------------------------------------- handle the last 3 uint32_t's */
308 switch(length) /* all the case statements fall through */
309 {
310 case 3 : c+=k[2];
311 ATTR_FALLTHROUGH
312 /* fallthrough */
313 case 2 : b+=k[1];
314 ATTR_FALLTHROUGH
315 /* fallthrough */
316 case 1 : a+=k[0];
317 final(a,b,c);
318 ATTR_FALLTHROUGH
319 /* fallthrough */
320 case 0: /* case 0: nothing left to add */
321 break;
322 }
323 /*------------------------------------------------------ report the result */
324 *pc=c; *pb=b;
325 }
326
327 #endif /* SELF_TEST */
328
329 /*
330 -------------------------------------------------------------------------------
331 hashlittle() -- hash a variable-length key into a 32-bit value
332 k : the key (the unaligned variable-length array of bytes)
333 length : the length of the key, counting by bytes
334 initval : can be any 4-byte value
335 Returns a 32-bit value. Every bit of the key affects every bit of
336 the return value. Two keys differing by one or two bits will have
337 totally different hash values.
338
339 The best hash table sizes are powers of 2. There is no need to do
340 mod a prime (mod is sooo slow!). If you need less than 32 bits,
341 use a bitmask. For example, if you need only 10 bits, do
342 h = (h & hashmask(10));
343 In which case, the hash table should have hashsize(10) elements.
344
345 If you are hashing n strings (uint8_t **)k, do it like this:
346 for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
347
348 By Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this
349 code any way you wish, private, educational, or commercial. It's free.
350
351 Use for hash table lookup, or anything where one collision in 2^^32 is
352 acceptable. Do NOT use for cryptographic purposes.
353 -------------------------------------------------------------------------------
354 */
355
hashlittle(const void * key,size_t length,uint32_t initval)356 uint32_t hashlittle( const void *key, size_t length, uint32_t initval)
357 {
358 uint32_t a,b,c; /* internal state */
359 union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */
360
361 /* Set up the internal state */
362 a = b = c = raninit + ((uint32_t)length) + initval;
363
364 u.ptr = key;
365 if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
366 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
367 #ifdef ARRAY_CLEAN_ACCESS
368 const uint8_t *k8;
369 #endif
370
371 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
372 while (length > 12)
373 {
374 a += k[0];
375 b += k[1];
376 c += k[2];
377 mix(a,b,c);
378 length -= 12;
379 k += 3;
380 }
381
382 /*----------------------------- handle the last (probably partial) block */
383 /*
384 * "k[2]&0xffffff" actually reads beyond the end of the string, but
385 * then masks off the part it's not allowed to read. Because the
386 * string is aligned, the masked-off tail is in the same word as the
387 * rest of the string. Every machine with memory protection I've seen
388 * does it on word boundaries, so is OK with this. But VALGRIND will
389 * still catch it and complain. The masking trick does make the hash
390 * noticeably faster for short strings (like English words).
391 */
392 #ifndef ARRAY_CLEAN_ACCESS
393
394 switch(length)
395 {
396 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
397 case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
398 case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
399 case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
400 case 8 : b+=k[1]; a+=k[0]; break;
401 case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
402 case 6 : b+=k[1]&0xffff; a+=k[0]; break;
403 case 5 : b+=k[1]&0xff; a+=k[0]; break;
404 case 4 : a+=k[0]; break;
405 case 3 : a+=k[0]&0xffffff; break;
406 case 2 : a+=k[0]&0xffff; break;
407 case 1 : a+=k[0]&0xff; break;
408 case 0 : return c; /* zero length strings require no mixing */
409 }
410
411 #else /* make valgrind happy */
412
413 k8 = (const uint8_t *)k;
414 switch(length)
415 {
416 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
417 case 11: c+=((uint32_t)k8[10])<<16;
418 ATTR_FALLTHROUGH
419 /* fallthrough */
420 case 10: c+=((uint32_t)k8[9])<<8;
421 ATTR_FALLTHROUGH
422 /* fallthrough */
423 case 9 : c+=k8[8];
424 ATTR_FALLTHROUGH
425 /* fallthrough */
426 case 8 : b+=k[1]; a+=k[0]; break;
427 case 7 : b+=((uint32_t)k8[6])<<16;
428 ATTR_FALLTHROUGH
429 /* fallthrough */
430 case 6 : b+=((uint32_t)k8[5])<<8;
431 ATTR_FALLTHROUGH
432 /* fallthrough */
433 case 5 : b+=k8[4];
434 ATTR_FALLTHROUGH
435 /* fallthrough */
436 case 4 : a+=k[0]; break;
437 case 3 : a+=((uint32_t)k8[2])<<16;
438 ATTR_FALLTHROUGH
439 /* fallthrough */
440 case 2 : a+=((uint32_t)k8[1])<<8;
441 ATTR_FALLTHROUGH
442 /* fallthrough */
443 case 1 : a+=k8[0]; break;
444 case 0 : return c;
445 }
446
447 #endif /* !valgrind */
448
449 } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
450 const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */
451 const uint8_t *k8;
452
453 /*--------------- all but last block: aligned reads and different mixing */
454 while (length > 12)
455 {
456 a += k[0] + (((uint32_t)k[1])<<16);
457 b += k[2] + (((uint32_t)k[3])<<16);
458 c += k[4] + (((uint32_t)k[5])<<16);
459 mix(a,b,c);
460 length -= 12;
461 k += 6;
462 }
463
464 /*----------------------------- handle the last (probably partial) block */
465 k8 = (const uint8_t *)k;
466 switch(length)
467 {
468 case 12: c+=k[4]+(((uint32_t)k[5])<<16);
469 b+=k[2]+(((uint32_t)k[3])<<16);
470 a+=k[0]+(((uint32_t)k[1])<<16);
471 break;
472 case 11: c+=((uint32_t)k8[10])<<16;
473 ATTR_FALLTHROUGH
474 /* fallthrough */
475 case 10: c+=k[4];
476 b+=k[2]+(((uint32_t)k[3])<<16);
477 a+=k[0]+(((uint32_t)k[1])<<16);
478 break;
479 case 9 : c+=k8[8];
480 ATTR_FALLTHROUGH
481 /* fallthrough */
482 case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
483 a+=k[0]+(((uint32_t)k[1])<<16);
484 break;
485 case 7 : b+=((uint32_t)k8[6])<<16;
486 ATTR_FALLTHROUGH
487 /* fallthrough */
488 case 6 : b+=k[2];
489 a+=k[0]+(((uint32_t)k[1])<<16);
490 break;
491 case 5 : b+=k8[4];
492 ATTR_FALLTHROUGH
493 /* fallthrough */
494 case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
495 break;
496 case 3 : a+=((uint32_t)k8[2])<<16;
497 ATTR_FALLTHROUGH
498 /* fallthrough */
499 case 2 : a+=k[0];
500 break;
501 case 1 : a+=k8[0];
502 break;
503 case 0 : return c; /* zero length requires no mixing */
504 }
505
506 } else { /* need to read the key one byte at a time */
507 const uint8_t *k = (const uint8_t *)key;
508
509 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
510 while (length > 12)
511 {
512 a += k[0];
513 a += ((uint32_t)k[1])<<8;
514 a += ((uint32_t)k[2])<<16;
515 a += ((uint32_t)k[3])<<24;
516 b += k[4];
517 b += ((uint32_t)k[5])<<8;
518 b += ((uint32_t)k[6])<<16;
519 b += ((uint32_t)k[7])<<24;
520 c += k[8];
521 c += ((uint32_t)k[9])<<8;
522 c += ((uint32_t)k[10])<<16;
523 c += ((uint32_t)k[11])<<24;
524 mix(a,b,c);
525 length -= 12;
526 k += 12;
527 }
528
529 /*-------------------------------- last block: affect all 32 bits of (c) */
530 switch(length) /* all the case statements fall through */
531 {
532 case 12: c+=((uint32_t)k[11])<<24;
533 ATTR_FALLTHROUGH
534 /* fallthrough */
535 case 11: c+=((uint32_t)k[10])<<16;
536 ATTR_FALLTHROUGH
537 /* fallthrough */
538 case 10: c+=((uint32_t)k[9])<<8;
539 ATTR_FALLTHROUGH
540 /* fallthrough */
541 case 9 : c+=k[8];
542 ATTR_FALLTHROUGH
543 /* fallthrough */
544 case 8 : b+=((uint32_t)k[7])<<24;
545 ATTR_FALLTHROUGH
546 /* fallthrough */
547 case 7 : b+=((uint32_t)k[6])<<16;
548 ATTR_FALLTHROUGH
549 /* fallthrough */
550 case 6 : b+=((uint32_t)k[5])<<8;
551 ATTR_FALLTHROUGH
552 /* fallthrough */
553 case 5 : b+=k[4];
554 ATTR_FALLTHROUGH
555 /* fallthrough */
556 case 4 : a+=((uint32_t)k[3])<<24;
557 ATTR_FALLTHROUGH
558 /* fallthrough */
559 case 3 : a+=((uint32_t)k[2])<<16;
560 ATTR_FALLTHROUGH
561 /* fallthrough */
562 case 2 : a+=((uint32_t)k[1])<<8;
563 ATTR_FALLTHROUGH
564 /* fallthrough */
565 case 1 : a+=k[0];
566 break;
567 case 0 : return c;
568 }
569 }
570
571 final(a,b,c);
572 return c;
573 }
574
575 #ifdef SELF_TEST
576
577 /*
578 * hashlittle2: return 2 32-bit hash values
579 *
580 * This is identical to hashlittle(), except it returns two 32-bit hash
581 * values instead of just one. This is good enough for hash table
582 * lookup with 2^^64 buckets, or if you want a second hash if you're not
583 * happy with the first, or if you want a probably-unique 64-bit ID for
584 * the key. *pc is better mixed than *pb, so use *pc first. If you want
585 * a 64-bit value do something like "*pc + (((uint64_t)*pb)<<32)".
586 */
hashlittle2(const void * key,size_t length,uint32_t * pc,uint32_t * pb)587 void hashlittle2(
588 const void *key, /* the key to hash */
589 size_t length, /* length of the key */
590 uint32_t *pc, /* IN: primary initval, OUT: primary hash */
591 uint32_t *pb) /* IN: secondary initval, OUT: secondary hash */
592 {
593 uint32_t a,b,c; /* internal state */
594 union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */
595
596 /* Set up the internal state */
597 a = b = c = raninit + ((uint32_t)length) + *pc;
598 c += *pb;
599
600 u.ptr = key;
601 if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
602 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
603 #ifdef VALGRIND
604 const uint8_t *k8;
605 #endif
606
607 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
608 while (length > 12)
609 {
610 a += k[0];
611 b += k[1];
612 c += k[2];
613 mix(a,b,c);
614 length -= 12;
615 k += 3;
616 }
617
618 /*----------------------------- handle the last (probably partial) block */
619 /*
620 * "k[2]&0xffffff" actually reads beyond the end of the string, but
621 * then masks off the part it's not allowed to read. Because the
622 * string is aligned, the masked-off tail is in the same word as the
623 * rest of the string. Every machine with memory protection I've seen
624 * does it on word boundaries, so is OK with this. But VALGRIND will
625 * still catch it and complain. The masking trick does make the hash
626 * noticeably faster for short strings (like English words).
627 */
628 #ifndef VALGRIND
629
630 switch(length)
631 {
632 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
633 case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
634 case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
635 case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
636 case 8 : b+=k[1]; a+=k[0]; break;
637 case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
638 case 6 : b+=k[1]&0xffff; a+=k[0]; break;
639 case 5 : b+=k[1]&0xff; a+=k[0]; break;
640 case 4 : a+=k[0]; break;
641 case 3 : a+=k[0]&0xffffff; break;
642 case 2 : a+=k[0]&0xffff; break;
643 case 1 : a+=k[0]&0xff; break;
644 case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */
645 }
646
647 #else /* make valgrind happy */
648
649 k8 = (const uint8_t *)k;
650 switch(length)
651 {
652 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
653 case 11: c+=((uint32_t)k8[10])<<16;
654 ATTR_FALLTHROUGH
655 /* fallthrough */
656 case 10: c+=((uint32_t)k8[9])<<8;
657 ATTR_FALLTHROUGH
658 /* fallthrough */
659 case 9 : c+=k8[8];
660 ATTR_FALLTHROUGH
661 /* fallthrough */
662 case 8 : b+=k[1]; a+=k[0]; break;
663 case 7 : b+=((uint32_t)k8[6])<<16;
664 ATTR_FALLTHROUGH
665 /* fallthrough */
666 case 6 : b+=((uint32_t)k8[5])<<8;
667 ATTR_FALLTHROUGH
668 /* fallthrough */
669 case 5 : b+=k8[4];
670 ATTR_FALLTHROUGH
671 /* fallthrough */
672 case 4 : a+=k[0]; break;
673 case 3 : a+=((uint32_t)k8[2])<<16;
674 ATTR_FALLTHROUGH
675 /* fallthrough */
676 case 2 : a+=((uint32_t)k8[1])<<8;
677 ATTR_FALLTHROUGH
678 /* fallthrough */
679 case 1 : a+=k8[0]; break;
680 case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */
681 }
682
683 #endif /* !valgrind */
684
685 } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
686 const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */
687 const uint8_t *k8;
688
689 /*--------------- all but last block: aligned reads and different mixing */
690 while (length > 12)
691 {
692 a += k[0] + (((uint32_t)k[1])<<16);
693 b += k[2] + (((uint32_t)k[3])<<16);
694 c += k[4] + (((uint32_t)k[5])<<16);
695 mix(a,b,c);
696 length -= 12;
697 k += 6;
698 }
699
700 /*----------------------------- handle the last (probably partial) block */
701 k8 = (const uint8_t *)k;
702 switch(length)
703 {
704 case 12: c+=k[4]+(((uint32_t)k[5])<<16);
705 b+=k[2]+(((uint32_t)k[3])<<16);
706 a+=k[0]+(((uint32_t)k[1])<<16);
707 break;
708 case 11: c+=((uint32_t)k8[10])<<16;
709 ATTR_FALLTHROUGH
710 /* fallthrough */
711 case 10: c+=k[4];
712 b+=k[2]+(((uint32_t)k[3])<<16);
713 a+=k[0]+(((uint32_t)k[1])<<16);
714 break;
715 case 9 : c+=k8[8];
716 ATTR_FALLTHROUGH
717 /* fallthrough */
718 case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
719 a+=k[0]+(((uint32_t)k[1])<<16);
720 break;
721 case 7 : b+=((uint32_t)k8[6])<<16;
722 ATTR_FALLTHROUGH
723 /* fallthrough */
724 case 6 : b+=k[2];
725 a+=k[0]+(((uint32_t)k[1])<<16);
726 break;
727 case 5 : b+=k8[4];
728 ATTR_FALLTHROUGH
729 /* fallthrough */
730 case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
731 break;
732 case 3 : a+=((uint32_t)k8[2])<<16;
733 ATTR_FALLTHROUGH
734 /* fallthrough */
735 case 2 : a+=k[0];
736 break;
737 case 1 : a+=k8[0];
738 break;
739 case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */
740 }
741
742 } else { /* need to read the key one byte at a time */
743 const uint8_t *k = (const uint8_t *)key;
744
745 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
746 while (length > 12)
747 {
748 a += k[0];
749 a += ((uint32_t)k[1])<<8;
750 a += ((uint32_t)k[2])<<16;
751 a += ((uint32_t)k[3])<<24;
752 b += k[4];
753 b += ((uint32_t)k[5])<<8;
754 b += ((uint32_t)k[6])<<16;
755 b += ((uint32_t)k[7])<<24;
756 c += k[8];
757 c += ((uint32_t)k[9])<<8;
758 c += ((uint32_t)k[10])<<16;
759 c += ((uint32_t)k[11])<<24;
760 mix(a,b,c);
761 length -= 12;
762 k += 12;
763 }
764
765 /*-------------------------------- last block: affect all 32 bits of (c) */
766 switch(length) /* all the case statements fall through */
767 {
768 case 12: c+=((uint32_t)k[11])<<24;
769 ATTR_FALLTHROUGH
770 /* fallthrough */
771 case 11: c+=((uint32_t)k[10])<<16;
772 ATTR_FALLTHROUGH
773 /* fallthrough */
774 case 10: c+=((uint32_t)k[9])<<8;
775 ATTR_FALLTHROUGH
776 /* fallthrough */
777 case 9 : c+=k[8];
778 ATTR_FALLTHROUGH
779 /* fallthrough */
780 case 8 : b+=((uint32_t)k[7])<<24;
781 ATTR_FALLTHROUGH
782 /* fallthrough */
783 case 7 : b+=((uint32_t)k[6])<<16;
784 ATTR_FALLTHROUGH
785 /* fallthrough */
786 case 6 : b+=((uint32_t)k[5])<<8;
787 ATTR_FALLTHROUGH
788 /* fallthrough */
789 case 5 : b+=k[4];
790 ATTR_FALLTHROUGH
791 /* fallthrough */
792 case 4 : a+=((uint32_t)k[3])<<24;
793 ATTR_FALLTHROUGH
794 /* fallthrough */
795 case 3 : a+=((uint32_t)k[2])<<16;
796 ATTR_FALLTHROUGH
797 /* fallthrough */
798 case 2 : a+=((uint32_t)k[1])<<8;
799 ATTR_FALLTHROUGH
800 /* fallthrough */
801 case 1 : a+=k[0];
802 break;
803 case 0 : *pc=c; *pb=b; return; /* zero length strings require no mixing */
804 }
805 }
806
807 final(a,b,c);
808 *pc=c; *pb=b;
809 }
810
811 #endif /* SELF_TEST */
812
813 #if 0 /* currently not used */
814
815 /*
816 * hashbig():
817 * This is the same as hashword() on big-endian machines. It is different
818 * from hashlittle() on all machines. hashbig() takes advantage of
819 * big-endian byte ordering.
820 */
821 uint32_t hashbig( const void *key, size_t length, uint32_t initval)
822 {
823 uint32_t a,b,c;
824 union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */
825
826 /* Set up the internal state */
827 a = b = c = raninit + ((uint32_t)length) + initval;
828
829 u.ptr = key;
830 if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) {
831 const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
832 #ifdef VALGRIND
833 const uint8_t *k8;
834 #endif
835
836 /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
837 while (length > 12)
838 {
839 a += k[0];
840 b += k[1];
841 c += k[2];
842 mix(a,b,c);
843 length -= 12;
844 k += 3;
845 }
846
847 /*----------------------------- handle the last (probably partial) block */
848 /*
849 * "k[2]<<8" actually reads beyond the end of the string, but
850 * then shifts out the part it's not allowed to read. Because the
851 * string is aligned, the illegal read is in the same word as the
852 * rest of the string. Every machine with memory protection I've seen
853 * does it on word boundaries, so is OK with this. But VALGRIND will
854 * still catch it and complain. The masking trick does make the hash
855 * noticeably faster for short strings (like English words).
856 */
857 #ifndef VALGRIND
858
859 switch(length)
860 {
861 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
862 case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break;
863 case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break;
864 case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break;
865 case 8 : b+=k[1]; a+=k[0]; break;
866 case 7 : b+=k[1]&0xffffff00; a+=k[0]; break;
867 case 6 : b+=k[1]&0xffff0000; a+=k[0]; break;
868 case 5 : b+=k[1]&0xff000000; a+=k[0]; break;
869 case 4 : a+=k[0]; break;
870 case 3 : a+=k[0]&0xffffff00; break;
871 case 2 : a+=k[0]&0xffff0000; break;
872 case 1 : a+=k[0]&0xff000000; break;
873 case 0 : return c; /* zero length strings require no mixing */
874 }
875
876 #else /* make valgrind happy */
877
878 k8 = (const uint8_t *)k;
879 switch(length) /* all the case statements fall through */
880 {
881 case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
882 case 11: c+=((uint32_t)k8[10])<<8;
883 ATTR_FALLTHROUGH
884 /* fallthrough */
885 case 10: c+=((uint32_t)k8[9])<<16;
886 ATTR_FALLTHROUGH
887 /* fallthrough */
888 case 9 : c+=((uint32_t)k8[8])<<24;
889 ATTR_FALLTHROUGH
890 /* fallthrough */
891 case 8 : b+=k[1]; a+=k[0]; break;
892 case 7 : b+=((uint32_t)k8[6])<<8;
893 ATTR_FALLTHROUGH
894 /* fallthrough */
895 case 6 : b+=((uint32_t)k8[5])<<16;
896 ATTR_FALLTHROUGH
897 /* fallthrough */
898 case 5 : b+=((uint32_t)k8[4])<<24;
899 ATTR_FALLTHROUGH
900 /* fallthrough */
901 case 4 : a+=k[0]; break;
902 case 3 : a+=((uint32_t)k8[2])<<8;
903 ATTR_FALLTHROUGH
904 /* fallthrough */
905 case 2 : a+=((uint32_t)k8[1])<<16;
906 ATTR_FALLTHROUGH
907 /* fallthrough */
908 case 1 : a+=((uint32_t)k8[0])<<24; break;
909 case 0 : return c;
910 }
911
912 #endif /* !VALGRIND */
913
914 } else { /* need to read the key one byte at a time */
915 const uint8_t *k = (const uint8_t *)key;
916
917 /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
918 while (length > 12)
919 {
920 a += ((uint32_t)k[0])<<24;
921 a += ((uint32_t)k[1])<<16;
922 a += ((uint32_t)k[2])<<8;
923 a += ((uint32_t)k[3]);
924 b += ((uint32_t)k[4])<<24;
925 b += ((uint32_t)k[5])<<16;
926 b += ((uint32_t)k[6])<<8;
927 b += ((uint32_t)k[7]);
928 c += ((uint32_t)k[8])<<24;
929 c += ((uint32_t)k[9])<<16;
930 c += ((uint32_t)k[10])<<8;
931 c += ((uint32_t)k[11]);
932 mix(a,b,c);
933 length -= 12;
934 k += 12;
935 }
936
937 /*-------------------------------- last block: affect all 32 bits of (c) */
938 switch(length) /* all the case statements fall through */
939 {
940 case 12: c+=k[11];
941 ATTR_FALLTHROUGH
942 /* fallthrough */
943 case 11: c+=((uint32_t)k[10])<<8;
944 ATTR_FALLTHROUGH
945 /* fallthrough */
946 case 10: c+=((uint32_t)k[9])<<16;
947 ATTR_FALLTHROUGH
948 /* fallthrough */
949 case 9 : c+=((uint32_t)k[8])<<24;
950 ATTR_FALLTHROUGH
951 /* fallthrough */
952 case 8 : b+=k[7];
953 ATTR_FALLTHROUGH
954 /* fallthrough */
955 case 7 : b+=((uint32_t)k[6])<<8;
956 ATTR_FALLTHROUGH
957 /* fallthrough */
958 case 6 : b+=((uint32_t)k[5])<<16;
959 ATTR_FALLTHROUGH
960 /* fallthrough */
961 case 5 : b+=((uint32_t)k[4])<<24;
962 ATTR_FALLTHROUGH
963 /* fallthrough */
964 case 4 : a+=k[3];
965 ATTR_FALLTHROUGH
966 /* fallthrough */
967 case 3 : a+=((uint32_t)k[2])<<8;
968 ATTR_FALLTHROUGH
969 /* fallthrough */
970 case 2 : a+=((uint32_t)k[1])<<16;
971 ATTR_FALLTHROUGH
972 /* fallthrough */
973 case 1 : a+=((uint32_t)k[0])<<24;
974 break;
975 case 0 : return c;
976 }
977 }
978
979 final(a,b,c);
980 return c;
981 }
982
983 #endif /* 0 == currently not used */
984
985 #ifdef SELF_TEST
986
987 /* used for timings */
driver1(void)988 void driver1(void)
989 {
990 uint8_t buf[256];
991 uint32_t i;
992 uint32_t h=0;
993 time_t a,z;
994
995 time(&a);
996 for (i=0; i<256; ++i) buf[i] = 'x';
997 for (i=0; i<1; ++i)
998 {
999 h = hashlittle(&buf[0],1,h);
1000 }
1001 time(&z);
1002 if (z-a > 0) printf("time %d %.8x\n", z-a, h);
1003 }
1004
1005 /* check that every input bit changes every output bit half the time */
1006 #define HASHSTATE 1
1007 #define HASHLEN 1
1008 #define MAXPAIR 60
1009 #define MAXLEN 70
driver2(void)1010 void driver2(void)
1011 {
1012 uint8_t qa[MAXLEN+1], qb[MAXLEN+2], *a = &qa[0], *b = &qb[1];
1013 uint32_t c[HASHSTATE], d[HASHSTATE], i=0, j=0, k, l, m=0, z;
1014 uint32_t e[HASHSTATE],f[HASHSTATE],g[HASHSTATE],h[HASHSTATE];
1015 uint32_t x[HASHSTATE],y[HASHSTATE];
1016 uint32_t hlen;
1017
1018 printf("No more than %d trials should ever be needed \n",MAXPAIR/2);
1019 for (hlen=0; hlen < MAXLEN; ++hlen)
1020 {
1021 z=0;
1022 for (i=0; i<hlen; ++i) /*----------------------- for each input byte, */
1023 {
1024 for (j=0; j<8; ++j) /*------------------------ for each input bit, */
1025 {
1026 for (m=1; m<8; ++m) /*------------ for several possible initvals, */
1027 {
1028 for (l=0; l<HASHSTATE; ++l)
1029 e[l]=f[l]=g[l]=h[l]=x[l]=y[l]=~((uint32_t)0);
1030
1031 /*---- check that every output bit is affected by that input bit */
1032 for (k=0; k<MAXPAIR; k+=2)
1033 {
1034 uint32_t finished=1;
1035 /* keys have one bit different */
1036 for (l=0; l<hlen+1; ++l) {a[l] = b[l] = (uint8_t)0;}
1037 /* have a and b be two keys differing in only one bit */
1038 a[i] ^= (k<<j);
1039 a[i] ^= (k>>(8-j));
1040 c[0] = hashlittle(a, hlen, m);
1041 b[i] ^= ((k+1)<<j);
1042 b[i] ^= ((k+1)>>(8-j));
1043 d[0] = hashlittle(b, hlen, m);
1044 /* check every bit is 1, 0, set, and not set at least once */
1045 for (l=0; l<HASHSTATE; ++l)
1046 {
1047 e[l] &= (c[l]^d[l]);
1048 f[l] &= ~(c[l]^d[l]);
1049 g[l] &= c[l];
1050 h[l] &= ~c[l];
1051 x[l] &= d[l];
1052 y[l] &= ~d[l];
1053 if (e[l]|f[l]|g[l]|h[l]|x[l]|y[l]) finished=0;
1054 }
1055 if (finished) break;
1056 }
1057 if (k>z) z=k;
1058 if (k==MAXPAIR)
1059 {
1060 printf("Some bit didn't change: ");
1061 printf("%.8x %.8x %.8x %.8x %.8x %.8x ",
1062 e[0],f[0],g[0],h[0],x[0],y[0]);
1063 printf("i %d j %d m %d len %d\n", i, j, m, hlen);
1064 }
1065 if (z==MAXPAIR) goto done;
1066 }
1067 }
1068 }
1069 done:
1070 if (z < MAXPAIR)
1071 {
1072 printf("Mix success %2d bytes %2d initvals ",i,m);
1073 printf("required %d trials\n", z/2);
1074 }
1075 }
1076 printf("\n");
1077 }
1078
1079 /* Check for reading beyond the end of the buffer and alignment problems */
driver3(void)1080 void driver3(void)
1081 {
1082 uint8_t buf[MAXLEN+20], *b;
1083 uint32_t len;
1084 uint8_t q[] = "This is the time for all good men to come to the aid of their country...";
1085 uint32_t h;
1086 uint8_t qq[] = "xThis is the time for all good men to come to the aid of their country...";
1087 uint32_t i;
1088 uint8_t qqq[] = "xxThis is the time for all good men to come to the aid of their country...";
1089 uint32_t j;
1090 uint8_t qqqq[] = "xxxThis is the time for all good men to come to the aid of their country...";
1091 uint32_t ref,x,y;
1092 uint8_t *p;
1093
1094 printf("Endianness. These lines should all be the same (for values filled in):\n");
1095 printf("%.8x %.8x %.8x\n",
1096 hashword((const uint32_t *)q, (sizeof(q)-1)/4, 13),
1097 hashword((const uint32_t *)q, (sizeof(q)-5)/4, 13),
1098 hashword((const uint32_t *)q, (sizeof(q)-9)/4, 13));
1099 p = q;
1100 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
1101 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
1102 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
1103 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
1104 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
1105 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
1106 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
1107 p = &qq[1];
1108 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
1109 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
1110 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
1111 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
1112 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
1113 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
1114 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
1115 p = &qqq[2];
1116 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
1117 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
1118 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
1119 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
1120 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
1121 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
1122 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
1123 p = &qqqq[3];
1124 printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
1125 hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
1126 hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
1127 hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
1128 hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
1129 hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
1130 hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
1131 printf("\n");
1132
1133 /* check that hashlittle2 and hashlittle produce the same results */
1134 i=47; j=0;
1135 hashlittle2(q, sizeof(q), &i, &j);
1136 if (hashlittle(q, sizeof(q), 47) != i)
1137 printf("hashlittle2 and hashlittle mismatch\n");
1138
1139 /* check that hashword2 and hashword produce the same results */
1140 len = raninit;
1141 i=47, j=0;
1142 hashword2(&len, 1, &i, &j);
1143 if (hashword(&len, 1, 47) != i)
1144 printf("hashword2 and hashword mismatch %x %x\n",
1145 i, hashword(&len, 1, 47));
1146
1147 /* check hashlittle doesn't read before or after the ends of the string */
1148 for (h=0, b=buf+1; h<8; ++h, ++b)
1149 {
1150 for (i=0; i<MAXLEN; ++i)
1151 {
1152 len = i;
1153 for (j=0; j<i; ++j) *(b+j)=0;
1154
1155 /* these should all be equal */
1156 ref = hashlittle(b, len, (uint32_t)1);
1157 *(b+i)=(uint8_t)~0;
1158 *(b-1)=(uint8_t)~0;
1159 x = hashlittle(b, len, (uint32_t)1);
1160 y = hashlittle(b, len, (uint32_t)1);
1161 if ((ref != x) || (ref != y))
1162 {
1163 printf("alignment error: %.8x %.8x %.8x %d %d\n",ref,x,y,
1164 h, i);
1165 }
1166 }
1167 }
1168 }
1169
1170 /* check for problems with nulls */
driver4(void)1171 void driver4(void)
1172 {
1173 uint8_t buf[1];
1174 uint32_t h,i,state[HASHSTATE];
1175
1176
1177 buf[0] = ~0;
1178 for (i=0; i<HASHSTATE; ++i) state[i] = 1;
1179 printf("These should all be different\n");
1180 for (i=0, h=0; i<8; ++i)
1181 {
1182 h = hashlittle(buf, 0, h);
1183 printf("%2ld 0-byte strings, hash is %.8x\n", i, h);
1184 }
1185 }
1186
1187
main(void)1188 int main(void)
1189 {
1190 driver1(); /* test that the key is hashed: used for timings */
1191 driver2(); /* test that whole key is hashed thoroughly */
1192 driver3(); /* test that nothing but the key is hashed */
1193 driver4(); /* test hashing multiple buffers (all buffers are null) */
1194 return 1;
1195 }
1196
1197 #endif /* SELF_TEST */
1198