1/*
2-------------------------------------------------------------------------------
3lookup3.c, by Bob Jenkins, May 2006, Public Domain.
4Original: http://burtleburtle.net/bob/c/lookup3.c
5Modified by Russ Rew for adaption in netCDF.
6- Make use of Paul Hsieh's pstdint.h, if stdint.h not available.
7- Declare unused functions static to keep global namespace clean.
8- Provide function hash_fast() that uses either hashlittle() or
9  hashbig(), depending on endianness.
10- Because portability is more important than speed for netCDF use,
11  we define VALGRIND to skip "#ifndef VALGRIND" code, so reads of
12  strings don't access extra bytes after end of string.  This may
13  slow it down enough to justify a simpler hash, but blame me, not
14  original author!
15
16These are functions for producing 32-bit hashes for hash table lookup.
17hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
18are externally useful functions.  Routines to test the hash are included
19if SELF_TEST is defined.  You can use this free for any purpose.  It's in
20the public domain.  It has no warranty.
21
22You probably want to use hashlittle().  hashlittle() and hashbig()
23hash byte arrays.  hashlittle() is is faster than hashbig() on
24little-endian machines.  Intel and AMD are little-endian machines.
25On second thought, you probably want hashlittle2(), which is identical to
26hashlittle() except it returns two 32-bit hashes for the price of one.
27You could implement hashbig2() if you wanted but I haven't bothered here.
28
29If you want to find a hash of, say, exactly 7 integers, do
30  a = i1;  b = i2;  c = i3;
31  mix(a,b,c);
32  a += i4; b += i5; c += i6;
33  mix(a,b,c);
34  a += i7;
35  final(a,b,c);
36then use c as the hash value.  If you have a variable length array of
374-byte integers to hash, use hashword().  If you have a byte array (like
38a character string), use hashlittle().  If you have several byte arrays, or
39a mix of things, see the comments above hashlittle().
40
41Why is this so big?  I read 12 bytes at a time into 3 4-byte integers,
42then mix those integers.  This is fast (you can do a lot more thorough
43mixing with 12*3 instructions on 3 integers than you can with 3 instructions
44on 1 byte), but shoehorning those bytes into integers efficiently is messy.
45-------------------------------------------------------------------------------
46*/
47/* #define SELF_TEST 1 */
48
49#include "config.h"
50#include <stdio.h>      /* defines printf for tests */
51#include <time.h>       /* defines time_t for timings in the test */
52#ifndef HAVE_STDINT_H
53#  include "pstdint.h" /* attempts to define uint32_t etc portably */
54#else
55#  include <stdint.h>
56#endif /* HAVE_STDINT_H */
57#ifdef HAVE_SYS_PARAM_H
58#include <sys/param.h>  /* attempt to define endianness */
59#endif /* HAVE_SYS_PARAM_H */
60#ifdef linux
61# include <endian.h>    /* attempt to define endianness */
62#endif
63
64#define VALGRIND   /* added by Russ Rew, for portability over speed */
65
66#ifndef WORDS_BIGENDIAN /* from config.h */
67#define HASH_LITTLE_ENDIAN 1
68#define HASH_BIG_ENDIAN 0
69#else
70#define HASH_LITTLE_ENDIAN 0
71#define HASH_BIG_ENDIAN 1
72#endif
73
74#define hashsize(n) ((uint32_t)1<<(n))
75#define hashmask(n) (hashsize(n)-1)
76#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
77
78/*
79-------------------------------------------------------------------------------
80mix -- mix 3 32-bit values reversibly.
81
82This is reversible, so any information in (a,b,c) before mix() is
83still in (a,b,c) after mix().
84
85If four pairs of (a,b,c) inputs are run through mix(), or through
86mix() in reverse, there are at least 32 bits of the output that
87are sometimes the same for one pair and different for another pair.
88This was tested for:
89* pairs that differed by one bit, by two bits, in any combination
90  of top bits of (a,b,c), or in any combination of bottom bits of
91  (a,b,c).
92* "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
93  the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
94  is commonly produced by subtraction) look like a single 1-bit
95  difference.
96* the base values were pseudorandom, all zero but one bit set, or
97  all zero plus a counter that starts at zero.
98
99Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
100satisfy this are
101    4  6  8 16 19  4
102    9 15  3 18 27 15
103   14  9  3  7 17  3
104Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
105for "differ" defined as + with a one-bit base and a two-bit delta.  I
106used http://burtleburtle.net/bob/hash/avalanche.html to choose
107the operations, constants, and arrangements of the variables.
108
109This does not achieve avalanche.  There are input bits of (a,b,c)
110that fail to affect some output bits of (a,b,c), especially of a.  The
111most thoroughly mixed value is c, but it doesn't really even achieve
112avalanche in c.
113
114This allows some parallelism.  Read-after-writes are good at doubling
115the number of bits affected, so the goal of mixing pulls in the opposite
116direction as the goal of parallelism.  I did what I could.  Rotates
117seem to cost as much as shifts on every machine I could lay my hands
118on, and rotates are much kinder to the top and bottom bits, so I used
119rotates.
120-------------------------------------------------------------------------------
121*/
122#define mix(a,b,c) \
123{ \
124  a -= c;  a ^= rot(c, 4);  c += b; \
125  b -= a;  b ^= rot(a, 6);  a += c; \
126  c -= b;  c ^= rot(b, 8);  b += a; \
127  a -= c;  a ^= rot(c,16);  c += b; \
128  b -= a;  b ^= rot(a,19);  a += c; \
129  c -= b;  c ^= rot(b, 4);  b += a; \
130}
131
132/*
133-------------------------------------------------------------------------------
134final -- final mixing of 3 32-bit values (a,b,c) into c
135
136Pairs of (a,b,c) values differing in only a few bits will usually
137produce values of c that look totally different.  This was tested for
138* pairs that differed by one bit, by two bits, in any combination
139  of top bits of (a,b,c), or in any combination of bottom bits of
140  (a,b,c).
141* "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
142  the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
143  is commonly produced by subtraction) look like a single 1-bit
144  difference.
145* the base values were pseudorandom, all zero but one bit set, or
146  all zero plus a counter that starts at zero.
147
148These constants passed:
149 14 11 25 16 4 14 24
150 12 14 25 16 4 14 24
151and these came close:
152  4  8 15 26 3 22 24
153 10  8 15 26 3 22 24
154 11  8 15 26 3 22 24
155-------------------------------------------------------------------------------
156*/
157#define final(a,b,c) \
158{ \
159  c ^= bc -= rot(b,14); \
160  a ^= ca -= rot(c,11); \
161  b ^= ab -= rot(a,25); \
162  c ^= bc -= rot(b,16); \
163  a ^= ca -= rot(c,4);  \
164  b ^= ab -= rot(a,14); \
165  c ^= bc -= rot(b,24); \
166}
167
168/*
169--------------------------------------------------------------------
170 This works on all machines.  To be useful, it requires
171 -- that the key be an array of uint32_t's, and
172 -- that the length be the number of uint32_t's in the key
173
174 The function hashword() is identical to hashlittle() on little-endian
175 machines, and identical to hashbig() on big-endian machines,
176 except that the length has to be measured in uint32_ts rather than in
177 bytes.  hashlittle() is more complicated than hashword() only because
178 hashlittle() has to dance around fitting the key bytes into registers.
179--------------------------------------------------------------------
180*/
181#ifdef SELF_TEST
182static
183uint32_t hashword(
184const uint32_t *k,                   /* the key, an array of uint32_t values */
185size_t          length,               /* the length of the key, in uint32_ts */
186uint32_t        initval)         /* the previous hash, or an arbitrary value */
187{
188  uint32_t a,b,c;
189
190  /* Set up the internal state */
191  a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval;
192
193  /*------------------------------------------------- handle most of the key */
194  while (length > 3)
195  {
196    a += k[0];
197    b += k[1];
198    c += k[2];
199    mix(a,b,c);
200    length -= 3;
201    k += 3;
202  }
203
204  /*------------------------------------------- handle the last 3 uint32_t's */
205  switch(length)                     /* all the case statements fall through */
206  {
207  case 3 : c+=k[2];
208  case 2 : b+=k[1];
209  case 1 : a+=k[0];
210    final(a,b,c);
211  case 0:     /* case 0: nothing left to add */
212    break;
213  }
214  /*------------------------------------------------------ report the result */
215  return c;
216}
217
218/*
219--------------------------------------------------------------------
220hashword2() -- same as hashword(), but take two seeds and return two
22132-bit values.  pc and pb must both be nonnull, and *pc and *pb must
222both be initialized with seeds.  If you pass in (*pb)==0, the output
223(*pc) will be the same as the return value from hashword().
224--------------------------------------------------------------------
225*/
226static
227void hashword2 (
228const uint32_t *k,                   /* the key, an array of uint32_t values */
229size_t          length,               /* the length of the key, in uint32_ts */
230uint32_t       *pc,                      /* IN: seed OUT: primary hash value */
231uint32_t       *pb)               /* IN: more seed OUT: secondary hash value */
232{
233  uint32_t a,b,c;
234
235  /* Set up the internal state */
236  a = b = c = 0xdeadbeef + ((uint32_t)(length<<2)) + *pc;
237  c += *pb;
238
239  /*------------------------------------------------- handle most of the key */
240  while (length > 3)
241  {
242    a += k[0];
243    b += k[1];
244    c += k[2];
245    mix(a,b,c);
246    length -= 3;
247    k += 3;
248  }
249
250  /*------------------------------------------- handle the last 3 uint32_t's */
251  switch(length)                     /* all the case statements fall through */
252  {
253  case 3 : c+=k[2];
254  case 2 : b+=k[1];
255  case 1 : a+=k[0];
256    final(a,b,c);
257  case 0:     /* case 0: nothing left to add */
258    break;
259  }
260  /*------------------------------------------------------ report the result */
261  *pc=c; *pb=b;
262}
263
264/*
265 * hashlittle2: return 2 32-bit hash values
266 *
267 * This is identical to hashlittle(), except it returns two 32-bit hash
268 * values instead of just one.  This is good enough for hash table
269 * lookup with 2^^64 buckets, or if you want a second hash if you're not
270 * happy with the first, or if you want a probably-unique 64-bit ID for
271 * the key.  *pc is better mixed than *pb, so use *pc first.  If you want
272 * a 64-bit value do something like "*pc + (((uint64_t)*pb)<<32)".
273 */
274static void
275hashlittle2(
276  const void *key,       /* the key to hash */
277  size_t      length,    /* length of the key */
278  uint32_t   *pc,        /* IN: primary initval, OUT: primary hash */
279  uint32_t   *pb)        /* IN: secondary initval, OUT: secondary hash */
280{
281  uint32_t a,b,c;                                          /* internal state */
282  union { const void *ptr; size_t i; } u;     /* needed for Mac Powerbook G4 */
283
284  /* Set up the internal state */
285  a = b = c = 0xdeadbeef + ((uint32_t)length) + *pc;
286  c += *pb;
287
288  u.ptr = key;
289  if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
290    const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */
291    const uint8_t  *k8;
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]&0xffffffb+=k[1]; a+=k[0]; break;
320    case 10: c+=k[2]&0xffffb+=k[1]; a+=k[0]; break;
321    case 9 : c+=k[2]&0xffb+=k[1]; a+=k[0]; break;
322    case 8 : b+=k[1]; a+=k[0]; break;
323    case 7 : b+=k[1]&0xffffffa+=k[0]; break;
324    case 6 : b+=k[1]&0xffffa+=k[0]; break;
325    case 5 : b+=k[1]&0xffa+=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 : *pc=c; *pb=b; return;  /* zero length strings require no mixing */
331    }
332
333#else /* make valgrind happy */
334
335    k8 = (const uint8_t *)k;
336    switch(length)
337    {
338    case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
339    case 11: c+=((uint32_t)k8[10])<<16;  /* fall through */
340    case 10: c+=((uint32_t)k8[9])<<8;    /* fall through */
341    case 9 : c+=k8[8];                   /* fall through */
342    case 8 : b+=k[1]; a+=k[0]; break;
343    case 7 : b+=((uint32_t)k8[6])<<16;   /* fall through */
344    case 6 : b+=((uint32_t)k8[5])<<8;    /* fall through */
345    case 5 : b+=k8[4];                   /* fall through */
346    case 4 : a+=k[0]; break;
347    case 3 : a+=((uint32_t)k8[2])<<16;   /* fall through */
348    case 2 : a+=((uint32_t)k8[1])<<8;    /* fall through */
349    case 1 : a+=k8[0]; break;
350    case 0 : *pc=c; *pb=b; return;  /* zero length strings require no mixing */
351    }
352
353#endif /* !valgrind */
354
355  } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
356    const uint16_t *k = (const uint16_t *)key;         /* read 16-bit chunks */
357    const uint8_t  *k8;
358
359    /*--------------- all but last block: aligned reads and different mixing */
360    while (length > 12)
361    {
362      a += k[0] + (((uint32_t)k[1])<<16);
363      b += k[2] + (((uint32_t)k[3])<<16);
364      c += k[4] + (((uint32_t)k[5])<<16);
365      mix(a,b,c);
366      length -= 12;
367      k += 6;
368    }
369
370    /*----------------------------- handle the last (probably partial) block */
371    k8 = (const uint8_t *)k;
372    switch(length)
373    {
374    case 12: c+=k[4]+(((uint32_t)k[5])<<16);
375             b+=k[2]+(((uint32_t)k[3])<<16);
376             a+=k[0]+(((uint32_t)k[1])<<16);
377             break;
378    case 11: c+=((uint32_t)k8[10])<<16;     /* fall through */
379    case 10: c+=k[4];
380             b+=k[2]+(((uint32_t)k[3])<<16);
381             a+=k[0]+(((uint32_t)k[1])<<16);
382             break;
383    case 9 : c+=k8[8];                      /* fall through */
384    case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
385             a+=k[0]+(((uint32_t)k[1])<<16);
386             break;
387    case 7 : b+=((uint32_t)k8[6])<<16;      /* fall through */
388    case 6 : b+=k[2];
389             a+=k[0]+(((uint32_t)k[1])<<16);
390             break;
391    case 5 : b+=k8[4];                      /* fall through */
392    case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
393             break;
394    case 3 : a+=((uint32_t)k8[2])<<16;      /* fall through */
395    case 2 : a+=k[0];
396             break;
397    case 1 : a+=k8[0];
398             break;
399    case 0 : *pc=c; *pb=b; return;  /* zero length strings require no mixing */
400    }
401
402  } else {                        /* need to read the key one byte at a time */
403    const uint8_t *k = (const uint8_t *)key;
404
405    /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
406    while (length > 12)
407    {
408      a += k[0];
409      a += ((uint32_t)k[1])<<8;
410      a += ((uint32_t)k[2])<<16;
411      a += ((uint32_t)k[3])<<24;
412      b += k[4];
413      b += ((uint32_t)k[5])<<8;
414      b += ((uint32_t)k[6])<<16;
415      b += ((uint32_t)k[7])<<24;
416      c += k[8];
417      c += ((uint32_t)k[9])<<8;
418      c += ((uint32_t)k[10])<<16;
419      c += ((uint32_t)k[11])<<24;
420      mix(a,b,c);
421      length -= 12;
422      k += 12;
423    }
424
425    /*-------------------------------- last block: affect all 32 bits of (c) */
426    switch(length)                   /* all the case statements fall through */
427    {
428    case 12: c+=((uint32_t)k[11])<<24;
429    case 11: c+=((uint32_t)k[10])<<16;
430    case 10: c+=((uint32_t)k[9])<<8;
431    case 9 : c+=k[8];
432    case 8 : b+=((uint32_t)k[7])<<24;
433    case 7 : b+=((uint32_t)k[6])<<16;
434    case 6 : b+=((uint32_t)k[5])<<8;
435    case 5 : b+=k[4];
436    case 4 : a+=((uint32_t)k[3])<<24;
437    case 3 : a+=((uint32_t)k[2])<<16;
438    case 2 : a+=((uint32_t)k[1])<<8;
439    case 1 : a+=k[0];
440             break;
441    case 0 : *pc=c; *pb=b; return;  /* zero length strings require no mixing */
442    }
443  }
444
445  final(a,b,c);
446  *pc=c; *pb=b;
447}
448#endif /*SELF_TEST*/
449
450
451#ifdef WORDS_BIGENDIAN
452/*
453 * hashbig():
454 * This is the same as hashword() on big-endian machines.  It is different
455 * from hashlittle() on all machines.  hashbig() takes advantage of
456 * big-endian byte ordering.
457 */
458static uint32_t
459hashbig( const void *key, size_t lengthuint32_t initval)
460{
461  uint32_t a,b,c;
462  union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */
463
464  /* Set up the internal state */
465  a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
466
467  u.ptr = key;
468  if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) {
469    const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */
470    const uint8_t  *k8;
471
472    /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
473    while (length > 12)
474    {
475      a += k[0];
476      b += k[1];
477      c += k[2];
478      mix(a,b,c);
479      length -= 12;
480      k += 3;
481    }
482
483    /*----------------------------- handle the last (probably partial) block */
484    /*
485     * "k[2]<<8" actually reads beyond the end of the string, but
486     * then shifts out the part it's not allowed to read.  Because the
487     * string is aligned, the illegal read is in the same word as the
488     * rest of the string.  Every machine with memory protection I've seen
489     * does it on word boundaries, so is OK with this.  But VALGRIND will
490     * still catch it and complain.  The masking trick does make the hash
491     * noticeably faster for short strings (like English words).
492     */
493#ifndef VALGRIND
494
495    switch(length)
496    {
497    case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
498    case 11: c+=k[2]&0xffffff00b+=k[1]; a+=k[0]; break;
499    case 10: c+=k[2]&0xffff0000b+=k[1]; a+=k[0]; break;
500    case 9 : c+=k[2]&0xff000000b+=k[1]; a+=k[0]; break;
501    case 8 : b+=k[1]; a+=k[0]; break;
502    case 7 : b+=k[1]&0xffffff00a+=k[0]; break;
503    case 6 : b+=k[1]&0xffff0000a+=k[0]; break;
504    case 5 : b+=k[1]&0xff000000a+=k[0]; break;
505    case 4 : a+=k[0]; break;
506    case 3 : a+=k[0]&0xffffff00; break;
507    case 2 : a+=k[0]&0xffff0000; break;
508    case 1 : a+=k[0]&0xff000000; break;
509    case 0 : return c;              /* zero length strings require no mixing */
510    }
511
512#else  /* make valgrind happy */
513
514    k8 = (const uint8_t *)k;
515    switch(length)                   /* all the case statements fall through */
516    {
517    case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
518    case 11: c+=((uint32_t)k8[10])<<8;  /* fall through */
519    case 10: c+=((uint32_t)k8[9])<<16;  /* fall through */
520    case 9 : c+=((uint32_t)k8[8])<<24;  /* fall through */
521    case 8 : b+=k[1]; a+=k[0]; break;
522    case 7 : b+=((uint32_t)k8[6])<<8;   /* fall through */
523    case 6 : b+=((uint32_t)k8[5])<<16;  /* fall through */
524    case 5 : b+=((uint32_t)k8[4])<<24;  /* fall through */
525    case 4 : a+=k[0]; break;
526    case 3 : a+=((uint32_t)k8[2])<<8;   /* fall through */
527    case 2 : a+=((uint32_t)k8[1])<<16;  /* fall through */
528    case 1 : a+=((uint32_t)k8[0])<<24; break;
529    case 0 : return c;
530    }
531
532#endif /* !VALGRIND */
533
534  } else {                        /* need to read the key one byte at a time */
535    const uint8_t *k = (const uint8_t *)key;
536
537    /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
538    while (length > 12)
539    {
540      a += ((uint32_t)k[0])<<24;
541      a += ((uint32_t)k[1])<<16;
542      a += ((uint32_t)k[2])<<8;
543      a += ((uint32_t)k[3]);
544      b += ((uint32_t)k[4])<<24;
545      b += ((uint32_t)k[5])<<16;
546      b += ((uint32_t)k[6])<<8;
547      b += ((uint32_t)k[7]);
548      c += ((uint32_t)k[8])<<24;
549      c += ((uint32_t)k[9])<<16;
550      c += ((uint32_t)k[10])<<8;
551      c += ((uint32_t)k[11]);
552      mix(a,b,c);
553      length -= 12;
554      k += 12;
555    }
556
557    /*-------------------------------- last block: affect all 32 bits of (c) */
558    switch(length)                   /* all the case statements fall through */
559    {
560    case 12: c+=k[11];
561    case 11: c+=((uint32_t)k[10])<<8;
562    case 10: c+=((uint32_t)k[9])<<16;
563    case 9 : c+=((uint32_t)k[8])<<24;
564    case 8 : b+=k[7];
565    case 7 : b+=((uint32_t)k[6])<<8;
566    case 6 : b+=((uint32_t)k[5])<<16;
567    case 5 : b+=((uint32_t)k[4])<<24;
568    case 4 : a+=k[3];
569    case 3 : a+=((uint32_t)k[2])<<8;
570    case 2 : a+=((uint32_t)k[1])<<16;
571    case 1 : a+=((uint32_t)k[0])<<24;
572             break;
573    case 0 : return c;
574    }
575  }
576
577  final(a,b,c);
578  return c;
579}
580#endif /*WORDS_BIGENDIAN*/
581
582/*
583-------------------------------------------------------------------------------
584hashlittle() -- hash a variable-length key into a 32-bit value
585  k       : the key (the unaligned variable-length array of bytes)
586  length  : the length of the key, counting by bytes
587  initval : can be any 4-byte value
588Returns a 32-bit value.  Every bit of the key affects every bit of
589the return value.  Two keys differing by one or two bits will have
590totally different hash values.
591
592The best hash table sizes are powers of 2.  There is no need to do
593mod a prime (mod is sooo slow!).  If you need less than 32 bits,
594use a bitmask.  For example, if you need only 10 bits, do
595  h = (h & hashmask(10));
596In which case, the hash table should have hashsize(10) elements.
597
598If you are hashing n strings (uint8_t **)k, do it like this:
599  for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
600
601By Bob Jenkins, 2006.  bob_jenkins@burtleburtle.net.  You may use this
602code any way you wish, private, educational, or commercial.  It's free.
603
604Use for hash table lookup, or anything where one collision in 2^^32 is
605acceptable.  Do NOT use for cryptographic purposes.
606-------------------------------------------------------------------------------
607*/
608
609static uint32_t
610hashlittle( const void *key, size_t lengthuint32_t initval)
611{
612  uint32_t a,b,c;                                          /* internal state */
613  union { const void *ptr; size_t i; } u;     /* needed for Mac Powerbook G4 */
614
615  /* Set up the internal state */
616  a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
617
618  u.ptr = key;
619  if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
620    const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */
621    const uint8_t  *k8;
622
623    /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
624    while (length > 12)
625    {
626      a += k[0];
627      b += k[1];
628      c += k[2];
629      mix(a,b,c);
630      length -= 12;
631      k += 3;
632    }
633
634    /*----------------------------- handle the last (probably partial) block */
635    /*
636     * "k[2]&0xffffff" actually reads beyond the end of the string, but
637     * then masks off the part it's not allowed to read.  Because the
638     * string is aligned, the masked-off tail is in the same word as the
639     * rest of the string.  Every machine with memory protection I've seen
640     * does it on word boundaries, so is OK with this.  But VALGRIND will
641     * still catch it and complain.  The masking trick does make the hash
642     * noticeably faster for short strings (like English words).
643     */
644#ifndef VALGRIND
645
646    switch(length)
647    {
648    case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
649    case 11: c+=k[2]&0xffffffb+=k[1]; a+=k[0]; break;
650    case 10: c+=k[2]&0xffffb+=k[1]; a+=k[0]; break;
651    case 9 : c+=k[2]&0xffb+=k[1]; a+=k[0]; break;
652    case 8 : b+=k[1]; a+=k[0]; break;
653    case 7 : b+=k[1]&0xffffffa+=k[0]; break;
654    case 6 : b+=k[1]&0xffffa+=k[0]; break;
655    case 5 : b+=k[1]&0xffa+=k[0]; break;
656    case 4 : a+=k[0]; break;
657    case 3 : a+=k[0]&0xffffff; break;
658    case 2 : a+=k[0]&0xffff; break;
659    case 1 : a+=k[0]&0xff; break;
660    case 0 : return c;              /* zero length strings require no mixing */
661    }
662
663#else /* make valgrind happy */
664
665    k8 = (const uint8_t *)k;
666    switch(length)
667    {
668    case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
669    case 11: c+=((uint32_t)k8[10])<<16;  /* fall through */
670    case 10: c+=((uint32_t)k8[9])<<8;    /* fall through */
671    case 9 : c+=k8[8];                   /* fall through */
672    case 8 : b+=k[1]; a+=k[0]; break;
673    case 7 : b+=((uint32_t)k8[6])<<16;   /* fall through */
674    case 6 : b+=((uint32_t)k8[5])<<8;    /* fall through */
675    case 5 : b+=k8[4];                   /* fall through */
676    case 4 : a+=k[0]; break;
677    case 3 : a+=((uint32_t)k8[2])<<16;   /* fall through */
678    case 2 : a+=((uint32_t)k8[1])<<8;    /* fall through */
679    case 1 : a+=k8[0]; break;
680    case 0 : return c;
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;     /* fall through */
709    case 10: c+=k[4];
710             b+=k[2]+(((uint32_t)k[3])<<16);
711             a+=k[0]+(((uint32_t)k[1])<<16);
712             break;
713    case 9 : c+=k8[8];                      /* fall through */
714    case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
715             a+=k[0]+(((uint32_t)k[1])<<16);
716             break;
717    case 7 : b+=((uint32_t)k8[6])<<16;      /* fall through */
718    case 6 : b+=k[2];
719             a+=k[0]+(((uint32_t)k[1])<<16);
720             break;
721    case 5 : b+=k8[4];                      /* fall through */
722    case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
723             break;
724    case 3 : a+=((uint32_t)k8[2])<<16;      /* fall through */
725    case 2 : a+=k[0];
726             break;
727    case 1 : a+=k8[0];
728             break;
729    case 0 : return c;                     /* zero length requires no mixing */
730    }
731
732  } else {                        /* need to read the key one byte at a time */
733    const uint8_t *k = (const uint8_t *)key;
734
735    /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
736    while (length > 12)
737    {
738      a += k[0];
739      a += ((uint32_t)k[1])<<8;
740      a += ((uint32_t)k[2])<<16;
741      a += ((uint32_t)k[3])<<24;
742      b += k[4];
743      b += ((uint32_t)k[5])<<8;
744      b += ((uint32_t)k[6])<<16;
745      b += ((uint32_t)k[7])<<24;
746      c += k[8];
747      c += ((uint32_t)k[9])<<8;
748      c += ((uint32_t)k[10])<<16;
749      c += ((uint32_t)k[11])<<24;
750      mix(a,b,c);
751      length -= 12;
752      k += 12;
753    }
754
755    /*-------------------------------- last block: affect all 32 bits of (c) */
756    switch(length)                   /* all the case statements fall through */
757    {
758    case 12: c+=((uint32_t)k[11])<<24;
759    case 11: c+=((uint32_t)k[10])<<16;
760    case 10: c+=((uint32_t)k[9])<<8;
761    case 9 : c+=k[8];
762    case 8 : b+=((uint32_t)k[7])<<24;
763    case 7 : b+=((uint32_t)k[6])<<16;
764    case 6 : b+=((uint32_t)k[5])<<8;
765    case 5 : b+=k[4];
766    case 4 : a+=((uint32_t)k[3])<<24;
767    case 3 : a+=((uint32_t)k[2])<<16;
768    case 2 : a+=((uint32_t)k[1])<<8;
769    case 1 : a+=k[0];
770             break;
771    case 0 : return c;
772    }
773  }
774
775  final(a,b,c);
776  return c;
777}
778
779
780/*
781 * hash_fast(key, length, initval)
782 * Wrapper that calls either hashlittle or hashbig, depending on endianness.
783 */
784uint32_t
785hash_fast( const void *key, size_t length) {
786#define NC_ARBITRARY_UINT (992099683U)
787#ifndef WORDS_BIGENDIAN
788    return hashlittle(keylengthNC_ARBITRARY_UINT);
789#else
790    return hashbig(keylengthNC_ARBITRARY_UINT);
791#endif
792}
793
794#ifdef SELF_TEST
795/* used for timings */
796void driver1()
797{
798  uint8_t buf[256];
799  uint32_t i;
800  uint32_t h=0;
801  time_t a,z;
802
803  time(&a);
804  for (i=0; i<256; ++ibuf[i] = 'x';
805  for (i=0; i<1; ++i)
806  {
807    h = hashlittle(&buf[0],1,h);
808  }
809  time(&z);
810  if (z-a > 0) printf("time %d %.8x\n", z-ah);
811}
812
813/* check that every input bit changes every output bit half the time */
814#define HASHSTATE 1
815#define HASHLEN   1
816#define MAXPAIR 60
817#define MAXLEN  70
818void driver2()
819{
820  uint8_t qa[MAXLEN+1], qb[MAXLEN+2], *a = &qa[0], *b = &qb[1];
821  uint32_t c[HASHSTATE], d[HASHSTATE], i=0, j=0, klm=0, z;
822  uint32_t e[HASHSTATE],f[HASHSTATE],g[HASHSTATE],h[HASHSTATE];
823  uint32_t x[HASHSTATE],y[HASHSTATE];
824  uint32_t hlen;
825
826  printf("No more than %d trials should ever be needed \n",MAXPAIR/2);
827  for (hlen=0; hlen < MAXLEN; ++hlen)
828  {
829    z=0;
830    for (i=0; i<hlen; ++i)  /*----------------------- for each input byte, */
831    {
832      for (j=0; j<8; ++j)   /*------------------------ for each input bit, */
833      {
834 for (m=1; m<8; ++m) /*------------ for serveral possible initvals, */
835 {
836   for (l=0; l<HASHSTATE; ++l)
837     e[l]=f[l]=g[l]=h[l]=x[l]=y[l]=~((uint32_t)0);
838
839         /*---- check that every output bit is affected by that input bit */
840   for (k=0; k<MAXPAIRk+=2)
841   {
842     uint32_t finished=1;
843     /* keys have one bit different */
844     for (l=0; l<hlen+1; ++l) {a[l] = b[l] = (uint8_t)0;}
845     /* have a and b be two keys differing in only one bit */
846     a[i] ^= (k<<j);
847     a[i] ^= (k>>(8-j));
848      c[0] = hashlittle(ahlenm);
849     b[i] ^= ((k+1)<<j);
850     b[i] ^= ((k+1)>>(8-j));
851      d[0] = hashlittle(bhlenm);
852     /* check every bit is 1, 0, set, and not set at least once */
853     for (l=0; l<HASHSTATE; ++l)
854     {
855       e[l] &= (c[l]^d[l]);
856       f[l] &= ~(c[l]^d[l]);
857       g[l] &= c[l];
858       h[l] &= ~c[l];
859       x[l] &= d[l];
860       y[l] &= ~d[l];
861       if (e[l]|f[l]|g[l]|h[l]|x[l]|y[l]) finished=0;
862     }
863     if (finished) break;
864   }
865   if (k>zz=k;
866   if (k==MAXPAIR)
867   {
868      printf("Some bit didn't change: ");
869      printf("%.8x %.8x %.8x %.8x %.8x %.8x  ",
870             e[0],f[0],g[0],h[0],x[0],y[0]);
871      printf("i %d j %d m %d len %d\n", ijmhlen);
872   }
873   if (z==MAXPAIR) goto done;
874 }
875      }
876    }
877   done:
878    if (z < MAXPAIR)
879    {
880      printf("Mix success  %2d bytes  %2d initvals  ",i,m);
881      printf("required  %d  trials\n", z/2);
882    }
883  }
884  printf("\n");
885}
886
887/* Check for reading beyond the end of the buffer and alignment problems */
888void driver3()
889{
890  uint8_t buf[MAXLEN+20], *b;
891  uint32_t len;
892  uint8_t q[] = "This is the time for all good men to come to the aid of their country...";
893  uint32_t h;
894  uint8_t qq[] = "xThis is the time for all good men to come to the aid of their country...";
895  uint32_t i;
896  uint8_t qqq[] = "xxThis is the time for all good men to come to the aid of their country...";
897  uint32_t j;
898  uint8_t qqqq[] = "xxxThis is the time for all good men to come to the aid of their country...";
899  uint32_t ref,x,y;
900  uint8_t *p;
901
902  printf("Endianness.  These lines should all be the same (for values filled in):\n");
903  printf("%.8x                            %.8x                            %.8x\n",
904         hashword((const uint32_t *)q, (sizeof(q)-1)/4, 13),
905         hashword((const uint32_t *)q, (sizeof(q)-5)/4, 13),
906         hashword((const uint32_t *)q, (sizeof(q)-9)/4, 13));
907  p = q;
908  printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
909         hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
910         hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
911         hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
912         hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
913         hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
914         hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
915  p = &qq[1];
916  printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
917         hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
918         hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
919         hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
920         hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
921         hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
922         hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
923  p = &qqq[2];
924  printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
925         hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
926         hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
927         hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
928         hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
929         hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
930         hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
931  p = &qqqq[3];
932  printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
933         hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
934         hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
935         hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
936         hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
937         hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
938         hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
939  printf("\n");
940
941  /* check that hashlittle2 and hashlittle produce the same results */
942  i=47; j=0;
943  hashlittle2(q, sizeof(q), &i, &j);
944  if (hashlittle(q, sizeof(q), 47) != i)
945    printf("hashlittle2 and hashlittle mismatch\n");
946
947  /* check that hashword2 and hashword produce the same results */
948  len = 0xdeadbeef;
949  i=47, j=0;
950  hashword2(&len, 1, &i, &j);
951  if (hashword(&len, 1, 47) != i)
952    printf("hashword2 and hashword mismatch %x %x\n",
953    ihashword(&len, 1, 47));
954
955  /* check hashlittle doesn't read before or after the ends of the string */
956  for (h=0, b=buf+1; h<8; ++h, ++b)
957  {
958    for (i=0; i<MAXLEN; ++i)
959    {
960      len = i;
961      for (j=0; j<i; ++j) *(b+j)=0;
962
963      /* these should all be equal */
964      ref = hashlittle(blen, (uint32_t)1);
965      *(b+i)=(uint8_t)~0;
966      *(b-1)=(uint8_t)~0;
967      x = hashlittle(blen, (uint32_t)1);
968      y = hashlittle(blen, (uint32_t)1);
969      if ((ref != x) || (ref != y))
970      {
971 printf("alignment error: %.8x %.8x %.8x %d %d\n",ref,x,y,
972               hi);
973      }
974    }
975  }
976}
977
978/* check for problems with nulls */
979 void driver4()
980{
981  uint8_t buf[1];
982  uint32_t h,i,state[HASHSTATE];
983
984
985  buf[0] = ~0;
986  for (i=0; i<HASHSTATE; ++istate[i] = 1;
987  printf("These should all be different\n");
988  for (i=0, h=0; i<8; ++i)
989  {
990    h = hashlittle(buf, 0, h);
991    printf("%2ld  0-byte strings, hash is  %.8x\n", ih);
992  }
993}
994
995void driver5()
996{
997  uint32_t b,c;
998  b=0, c=0, hashlittle2("", 0, &c, &b);
999  printf("hash is %.8lx %.8lx\n", cb);   /* deadbeef deadbeef */
1000  b=0xdeadbeefc=0, hashlittle2("", 0, &c, &b);
1001  printf("hash is %.8lx %.8lx\n", cb);   /* bd5b7dde deadbeef */
1002  b=0xdeadbeefc=0xdeadbeefhashlittle2("", 0, &c, &b);
1003  printf("hash is %.8lx %.8lx\n", cb);   /* 9c093ccd bd5b7dde */
1004  b=0, c=0, hashlittle2("Four score and seven years ago", 30, &c, &b);
1005  printf("hash is %.8lx %.8lx\n", cb);   /* 17770551 ce7226e6 */
1006  b=1, c=0, hashlittle2("Four score and seven years ago", 30, &c, &b);
1007  printf("hash is %.8lx %.8lx\n", cb);   /* e3607cae bd371de4 */
1008  b=0, c=1, hashlittle2("Four score and seven years ago", 30, &c, &b);
1009  printf("hash is %.8lx %.8lx\n", cb);   /* cd628161 6cbea4b3 */
1010  c = hashlittle("Four score and seven years ago", 30, 0);
1011  printf("hash is %.8lx\n", c);   /* 17770551 */
1012  c = hashlittle("Four score and seven years ago", 30, 1);
1013  printf("hash is %.8lx\n", c);   /* cd628161 */
1014}
1015
1016
1017int main()
1018{
1019  driver1();   /* test that the key is hashed: used for timings */
1020  driver2();   /* test that whole key is hashed thoroughly */
1021  driver3();   /* test that nothing but the key is hashed */
1022  driver4();   /* test hashing multiple buffers (all buffers are null) */
1023  driver5();   /* test the hash against known vectors */
1024  return 1;
1025}
1026
1027#endif  /* SELF_TEST */


HyperKWIC - Version 7.20DA executed at 11:37 on 27 Oct 2017 | Polyhedron Solutions - INTERNAL USE | COMMERCIAL (Any O/S) SN 4AKIed