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