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