endian: add constant versions.
[ccan] / ccan / hash / hash.c
1 /* CC0 (Public domain) - see LICENSE file for details */
2 /*
3 -------------------------------------------------------------------------------
4 lookup3.c, by Bob Jenkins, May 2006, Public Domain.
5
6 These are functions for producing 32-bit hashes for hash table lookup.
7 hash_word(), hashlittle(), hashlittle2(), hashbig(), mix(), and final() 
8 are externally useful functions.  Routines to test the hash are included 
9 if SELF_TEST is defined.  You can use this free for any purpose.  It's in
10 the public domain.  It has no warranty.
11
12 You probably want to use hashlittle().  hashlittle() and hashbig()
13 hash byte arrays.  hashlittle() is is faster than hashbig() on
14 little-endian machines.  Intel and AMD are little-endian machines.
15 On second thought, you probably want hashlittle2(), which is identical to
16 hashlittle() except it returns two 32-bit hashes for the price of one.  
17 You could implement hashbig2() if you wanted but I haven't bothered here.
18
19 If you want to find a hash of, say, exactly 7 integers, do
20   a = i1;  b = i2;  c = i3;
21   mix(a,b,c);
22   a += i4; b += i5; c += i6;
23   mix(a,b,c);
24   a += i7;
25   final(a,b,c);
26 then use c as the hash value.  If you have a variable length array of
27 4-byte integers to hash, use hash_word().  If you have a byte array (like
28 a character string), use hashlittle().  If you have several byte arrays, or
29 a mix of things, see the comments above hashlittle().  
30
31 Why is this so big?  I read 12 bytes at a time into 3 4-byte integers, 
32 then mix those integers.  This is fast (you can do a lot more thorough
33 mixing with 12*3 instructions on 3 integers than you can with 3 instructions
34 on 1 byte), but shoehorning those bytes into integers efficiently is messy.
35 -------------------------------------------------------------------------------
36 */
37 //#define SELF_TEST 1
38
39 #if 0
40 #include <stdio.h>      /* defines printf for tests */
41 #include <time.h>       /* defines time_t for timings in the test */
42 #include <stdint.h>     /* defines uint32_t etc */
43 #include <sys/param.h>  /* attempt to define endianness */
44
45 #ifdef linux
46 # include <endian.h>    /* attempt to define endianness */
47 #endif
48
49 /*
50  * My best guess at if you are big-endian or little-endian.  This may
51  * need adjustment.
52  */
53 #if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \
54      __BYTE_ORDER == __LITTLE_ENDIAN) || \
55     (defined(i386) || defined(__i386__) || defined(__i486__) || \
56      defined(__i586__) || defined(__i686__) || defined(__x86_64) || \
57      defined(vax) || defined(MIPSEL))
58 # define HASH_LITTLE_ENDIAN 1
59 # define HASH_BIG_ENDIAN 0
60 #elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \
61        __BYTE_ORDER == __BIG_ENDIAN) || \
62       (defined(sparc) || defined(POWERPC) || defined(mc68000) || defined(sel))
63 # define HASH_LITTLE_ENDIAN 0
64 # define HASH_BIG_ENDIAN 1
65 #else
66 # error Unknown endian
67 #endif
68 #endif /* old hash.c headers. */
69
70 #include "hash.h"
71
72 #if HAVE_LITTLE_ENDIAN
73 #define HASH_LITTLE_ENDIAN 1
74 #define HASH_BIG_ENDIAN 0
75 #elif HAVE_BIG_ENDIAN
76 #define HASH_LITTLE_ENDIAN 0
77 #define HASH_BIG_ENDIAN 1
78 #else
79 #error Unknown endian
80 #endif
81
82 #define hashsize(n) ((uint32_t)1<<(n))
83 #define hashmask(n) (hashsize(n)-1)
84 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
85
86 /*
87 -------------------------------------------------------------------------------
88 mix -- mix 3 32-bit values reversibly.
89
90 This is reversible, so any information in (a,b,c) before mix() is
91 still in (a,b,c) after mix().
92
93 If four pairs of (a,b,c) inputs are run through mix(), or through
94 mix() in reverse, there are at least 32 bits of the output that
95 are sometimes the same for one pair and different for another pair.
96 This was tested for:
97 * pairs that differed by one bit, by two bits, in any combination
98   of top bits of (a,b,c), or in any combination of bottom bits of
99   (a,b,c).
100 * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
101   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
102   is commonly produced by subtraction) look like a single 1-bit
103   difference.
104 * the base values were pseudorandom, all zero but one bit set, or 
105   all zero plus a counter that starts at zero.
106
107 Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
108 satisfy this are
109     4  6  8 16 19  4
110     9 15  3 18 27 15
111    14  9  3  7 17  3
112 Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
113 for "differ" defined as + with a one-bit base and a two-bit delta.  I
114 used http://burtleburtle.net/bob/hash/avalanche.html to choose 
115 the operations, constants, and arrangements of the variables.
116
117 This does not achieve avalanche.  There are input bits of (a,b,c)
118 that fail to affect some output bits of (a,b,c), especially of a.  The
119 most thoroughly mixed value is c, but it doesn't really even achieve
120 avalanche in c.
121
122 This allows some parallelism.  Read-after-writes are good at doubling
123 the number of bits affected, so the goal of mixing pulls in the opposite
124 direction as the goal of parallelism.  I did what I could.  Rotates
125 seem to cost as much as shifts on every machine I could lay my hands
126 on, and rotates are much kinder to the top and bottom bits, so I used
127 rotates.
128 -------------------------------------------------------------------------------
129 */
130 #define mix(a,b,c) \
131 { \
132   a -= c;  a ^= rot(c, 4);  c += b; \
133   b -= a;  b ^= rot(a, 6);  a += c; \
134   c -= b;  c ^= rot(b, 8);  b += a; \
135   a -= c;  a ^= rot(c,16);  c += b; \
136   b -= a;  b ^= rot(a,19);  a += c; \
137   c -= b;  c ^= rot(b, 4);  b += a; \
138 }
139
140 /*
141 -------------------------------------------------------------------------------
142 final -- final mixing of 3 32-bit values (a,b,c) into c
143
144 Pairs of (a,b,c) values differing in only a few bits will usually
145 produce values of c that look totally different.  This was tested for
146 * pairs that differed by one bit, by two bits, in any combination
147   of top bits of (a,b,c), or in any combination of bottom bits of
148   (a,b,c).
149 * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
150   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
151   is commonly produced by subtraction) look like a single 1-bit
152   difference.
153 * the base values were pseudorandom, all zero but one bit set, or 
154   all zero plus a counter that starts at zero.
155
156 These constants passed:
157  14 11 25 16 4 14 24
158  12 14 25 16 4 14 24
159 and these came close:
160   4  8 15 26 3 22 24
161  10  8 15 26 3 22 24
162  11  8 15 26 3 22 24
163 -------------------------------------------------------------------------------
164 */
165 #define final(a,b,c) \
166 { \
167   c ^= b; c -= rot(b,14); \
168   a ^= c; a -= rot(c,11); \
169   b ^= a; b -= rot(a,25); \
170   c ^= b; c -= rot(b,16); \
171   a ^= c; a -= rot(c,4);  \
172   b ^= a; b -= rot(a,14); \
173   c ^= b; c -= rot(b,24); \
174 }
175
176 /*
177 --------------------------------------------------------------------
178  This works on all machines.  To be useful, it requires
179  -- that the key be an array of uint32_t's, and
180  -- that the length be the number of uint32_t's in the key
181
182  The function hash_word() is identical to hashlittle() on little-endian
183  machines, and identical to hashbig() on big-endian machines,
184  except that the length has to be measured in uint32_ts rather than in
185  bytes.  hashlittle() is more complicated than hash_word() only because
186  hashlittle() has to dance around fitting the key bytes into registers.
187 --------------------------------------------------------------------
188 */
189 uint32_t hash_u32(
190 const uint32_t *k,                   /* the key, an array of uint32_t values */
191 size_t          length,               /* the length of the key, in uint32_ts */
192 uint32_t        initval)         /* the previous hash, or an arbitrary value */
193 {
194   uint32_t a,b,c;
195
196   /* Set up the internal state */
197   a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval;
198
199   /*------------------------------------------------- handle most of the key */
200   while (length > 3)
201   {
202     a += k[0];
203     b += k[1];
204     c += k[2];
205     mix(a,b,c);
206     length -= 3;
207     k += 3;
208   }
209
210   /*------------------------------------------- handle the last 3 uint32_t's */
211   switch(length)                     /* all the case statements fall through */
212   { 
213   case 3 : c+=k[2];
214   case 2 : b+=k[1];
215   case 1 : a+=k[0];
216     final(a,b,c);
217   case 0:     /* case 0: nothing left to add */
218     break;
219   }
220   /*------------------------------------------------------ report the result */
221   return c;
222 }
223
224 /*
225 -------------------------------------------------------------------------------
226 hashlittle() -- hash a variable-length key into a 32-bit value
227   k       : the key (the unaligned variable-length array of bytes)
228   length  : the length of the key, counting by bytes
229   val2    : IN: can be any 4-byte value OUT: second 32 bit hash.
230 Returns a 32-bit value.  Every bit of the key affects every bit of
231 the return value.  Two keys differing by one or two bits will have
232 totally different hash values.  Note that the return value is better
233 mixed than val2, so use that first.
234
235 The best hash table sizes are powers of 2.  There is no need to do
236 mod a prime (mod is sooo slow!).  If you need less than 32 bits,
237 use a bitmask.  For example, if you need only 10 bits, do
238   h = (h & hashmask(10));
239 In which case, the hash table should have hashsize(10) elements.
240
241 If you are hashing n strings (uint8_t **)k, do it like this:
242   for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
243
244 By Bob Jenkins, 2006.  bob_jenkins@burtleburtle.net.  You may use this
245 code any way you wish, private, educational, or commercial.  It's free.
246
247 Use for hash table lookup, or anything where one collision in 2^^32 is
248 acceptable.  Do NOT use for cryptographic purposes.
249 -------------------------------------------------------------------------------
250 */
251
252 static uint32_t hashlittle( const void *key, size_t length, uint32_t *val2 )
253 {
254   uint32_t a,b,c;                                          /* internal state */
255   union { const void *ptr; size_t i; } u;     /* needed for Mac Powerbook G4 */
256
257   /* Set up the internal state */
258   a = b = c = 0xdeadbeef + ((uint32_t)length) + *val2;
259
260   u.ptr = key;
261   if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
262     const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */
263     const uint8_t  *k8;
264
265     /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
266     while (length > 12)
267     {
268       a += k[0];
269       b += k[1];
270       c += k[2];
271       mix(a,b,c);
272       length -= 12;
273       k += 3;
274     }
275
276     /*----------------------------- handle the last (probably partial) block */
277     /* 
278      * "k[2]&0xffffff" actually reads beyond the end of the string, but
279      * then masks off the part it's not allowed to read.  Because the
280      * string is aligned, the masked-off tail is in the same word as the
281      * rest of the string.  Every machine with memory protection I've seen
282      * does it on word boundaries, so is OK with this.  But VALGRIND will
283      * still catch it and complain.  The masking trick does make the hash
284      * noticably faster for short strings (like English words).
285      *
286      * Not on my testing with gcc 4.5 on an intel i5 CPU, at least --RR.
287      */
288 #if 0
289     switch(length)
290     {
291     case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
292     case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
293     case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
294     case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
295     case 8 : b+=k[1]; a+=k[0]; break;
296     case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
297     case 6 : b+=k[1]&0xffff; a+=k[0]; break;
298     case 5 : b+=k[1]&0xff; a+=k[0]; break;
299     case 4 : a+=k[0]; break;
300     case 3 : a+=k[0]&0xffffff; break;
301     case 2 : a+=k[0]&0xffff; break;
302     case 1 : a+=k[0]&0xff; break;
303     case 0 : return c;              /* zero length strings require no mixing */
304     }
305
306 #else /* make valgrind happy */
307
308     k8 = (const uint8_t *)k;
309     switch(length)
310     {
311     case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
312     case 11: c+=((uint32_t)k8[10])<<16;  /* fall through */
313     case 10: c+=((uint32_t)k8[9])<<8;    /* fall through */
314     case 9 : c+=k8[8];                   /* fall through */
315     case 8 : b+=k[1]; a+=k[0]; break;
316     case 7 : b+=((uint32_t)k8[6])<<16;   /* fall through */
317     case 6 : b+=((uint32_t)k8[5])<<8;    /* fall through */
318     case 5 : b+=k8[4];                   /* fall through */
319     case 4 : a+=k[0]; break;
320     case 3 : a+=((uint32_t)k8[2])<<16;   /* fall through */
321     case 2 : a+=((uint32_t)k8[1])<<8;    /* fall through */
322     case 1 : a+=k8[0]; break;
323     case 0 : return c;
324     }
325
326 #endif /* !valgrind */
327
328   } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
329     const uint16_t *k = (const uint16_t *)key;         /* read 16-bit chunks */
330     const uint8_t  *k8;
331
332     /*--------------- all but last block: aligned reads and different mixing */
333     while (length > 12)
334     {
335       a += k[0] + (((uint32_t)k[1])<<16);
336       b += k[2] + (((uint32_t)k[3])<<16);
337       c += k[4] + (((uint32_t)k[5])<<16);
338       mix(a,b,c);
339       length -= 12;
340       k += 6;
341     }
342
343     /*----------------------------- handle the last (probably partial) block */
344     k8 = (const uint8_t *)k;
345     switch(length)
346     {
347     case 12: c+=k[4]+(((uint32_t)k[5])<<16);
348              b+=k[2]+(((uint32_t)k[3])<<16);
349              a+=k[0]+(((uint32_t)k[1])<<16);
350              break;
351     case 11: c+=((uint32_t)k8[10])<<16;     /* fall through */
352     case 10: c+=k[4];
353              b+=k[2]+(((uint32_t)k[3])<<16);
354              a+=k[0]+(((uint32_t)k[1])<<16);
355              break;
356     case 9 : c+=k8[8];                      /* fall through */
357     case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
358              a+=k[0]+(((uint32_t)k[1])<<16);
359              break;
360     case 7 : b+=((uint32_t)k8[6])<<16;      /* fall through */
361     case 6 : b+=k[2];
362              a+=k[0]+(((uint32_t)k[1])<<16);
363              break;
364     case 5 : b+=k8[4];                      /* fall through */
365     case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
366              break;
367     case 3 : a+=((uint32_t)k8[2])<<16;      /* fall through */
368     case 2 : a+=k[0];
369              break;
370     case 1 : a+=k8[0];
371              break;
372     case 0 : return c;                     /* zero length requires no mixing */
373     }
374
375   } else {                        /* need to read the key one byte at a time */
376     const uint8_t *k = (const uint8_t *)key;
377
378     /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
379     while (length > 12)
380     {
381       a += k[0];
382       a += ((uint32_t)k[1])<<8;
383       a += ((uint32_t)k[2])<<16;
384       a += ((uint32_t)k[3])<<24;
385       b += k[4];
386       b += ((uint32_t)k[5])<<8;
387       b += ((uint32_t)k[6])<<16;
388       b += ((uint32_t)k[7])<<24;
389       c += k[8];
390       c += ((uint32_t)k[9])<<8;
391       c += ((uint32_t)k[10])<<16;
392       c += ((uint32_t)k[11])<<24;
393       mix(a,b,c);
394       length -= 12;
395       k += 12;
396     }
397
398     /*-------------------------------- last block: affect all 32 bits of (c) */
399     switch(length)                   /* all the case statements fall through */
400     {
401     case 12: c+=((uint32_t)k[11])<<24;
402     case 11: c+=((uint32_t)k[10])<<16;
403     case 10: c+=((uint32_t)k[9])<<8;
404     case 9 : c+=k[8];
405     case 8 : b+=((uint32_t)k[7])<<24;
406     case 7 : b+=((uint32_t)k[6])<<16;
407     case 6 : b+=((uint32_t)k[5])<<8;
408     case 5 : b+=k[4];
409     case 4 : a+=((uint32_t)k[3])<<24;
410     case 3 : a+=((uint32_t)k[2])<<16;
411     case 2 : a+=((uint32_t)k[1])<<8;
412     case 1 : a+=k[0];
413              break;
414     case 0 : return c;
415     }
416   }
417
418   final(a,b,c);
419   *val2 = b;
420   return c;
421 }
422
423 /*
424  * hashbig():
425  * This is the same as hash_word() on big-endian machines.  It is different
426  * from hashlittle() on all machines.  hashbig() takes advantage of
427  * big-endian byte ordering. 
428  */
429 static uint32_t hashbig( const void *key, size_t length, uint32_t *val2)
430 {
431   uint32_t a,b,c;
432   union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */
433
434   /* Set up the internal state */
435   a = b = c = 0xdeadbeef + ((uint32_t)length) + *val2;
436
437   u.ptr = key;
438   if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) {
439     const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */
440     const uint8_t  *k8;
441
442     /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
443     while (length > 12)
444     {
445       a += k[0];
446       b += k[1];
447       c += k[2];
448       mix(a,b,c);
449       length -= 12;
450       k += 3;
451     }
452
453     /*----------------------------- handle the last (probably partial) block */
454     /* 
455      * "k[2]<<8" actually reads beyond the end of the string, but
456      * then shifts out the part it's not allowed to read.  Because the
457      * string is aligned, the illegal read is in the same word as the
458      * rest of the string.  Every machine with memory protection I've seen
459      * does it on word boundaries, so is OK with this.  But VALGRIND will
460      * still catch it and complain.  The masking trick does make the hash
461      * noticably faster for short strings (like English words).
462      *
463      * Not on my testing with gcc 4.5 on an intel i5 CPU, at least --RR.
464      */
465 #if 0
466     switch(length)
467     {
468     case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
469     case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break;
470     case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break;
471     case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break;
472     case 8 : b+=k[1]; a+=k[0]; break;
473     case 7 : b+=k[1]&0xffffff00; a+=k[0]; break;
474     case 6 : b+=k[1]&0xffff0000; a+=k[0]; break;
475     case 5 : b+=k[1]&0xff000000; a+=k[0]; break;
476     case 4 : a+=k[0]; break;
477     case 3 : a+=k[0]&0xffffff00; break;
478     case 2 : a+=k[0]&0xffff0000; break;
479     case 1 : a+=k[0]&0xff000000; break;
480     case 0 : return c;              /* zero length strings require no mixing */
481     }
482
483 #else  /* make valgrind happy */
484
485     k8 = (const uint8_t *)k;
486     switch(length)                   /* all the case statements fall through */
487     {
488     case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
489     case 11: c+=((uint32_t)k8[10])<<8;  /* fall through */
490     case 10: c+=((uint32_t)k8[9])<<16;  /* fall through */
491     case 9 : c+=((uint32_t)k8[8])<<24;  /* fall through */
492     case 8 : b+=k[1]; a+=k[0]; break;
493     case 7 : b+=((uint32_t)k8[6])<<8;   /* fall through */
494     case 6 : b+=((uint32_t)k8[5])<<16;  /* fall through */
495     case 5 : b+=((uint32_t)k8[4])<<24;  /* fall through */
496     case 4 : a+=k[0]; break;
497     case 3 : a+=((uint32_t)k8[2])<<8;   /* fall through */
498     case 2 : a+=((uint32_t)k8[1])<<16;  /* fall through */
499     case 1 : a+=((uint32_t)k8[0])<<24; break;
500     case 0 : return c;
501     }
502
503 #endif /* !VALGRIND */
504
505   } else {                        /* need to read the key one byte at a time */
506     const uint8_t *k = (const uint8_t *)key;
507
508     /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
509     while (length > 12)
510     {
511       a += ((uint32_t)k[0])<<24;
512       a += ((uint32_t)k[1])<<16;
513       a += ((uint32_t)k[2])<<8;
514       a += ((uint32_t)k[3]);
515       b += ((uint32_t)k[4])<<24;
516       b += ((uint32_t)k[5])<<16;
517       b += ((uint32_t)k[6])<<8;
518       b += ((uint32_t)k[7]);
519       c += ((uint32_t)k[8])<<24;
520       c += ((uint32_t)k[9])<<16;
521       c += ((uint32_t)k[10])<<8;
522       c += ((uint32_t)k[11]);
523       mix(a,b,c);
524       length -= 12;
525       k += 12;
526     }
527
528     /*-------------------------------- last block: affect all 32 bits of (c) */
529     switch(length)                   /* all the case statements fall through */
530     {
531     case 12: c+=k[11];
532     case 11: c+=((uint32_t)k[10])<<8;
533     case 10: c+=((uint32_t)k[9])<<16;
534     case 9 : c+=((uint32_t)k[8])<<24;
535     case 8 : b+=k[7];
536     case 7 : b+=((uint32_t)k[6])<<8;
537     case 6 : b+=((uint32_t)k[5])<<16;
538     case 5 : b+=((uint32_t)k[4])<<24;
539     case 4 : a+=k[3];
540     case 3 : a+=((uint32_t)k[2])<<8;
541     case 2 : a+=((uint32_t)k[1])<<16;
542     case 1 : a+=((uint32_t)k[0])<<24;
543              break;
544     case 0 : return c;
545     }
546   }
547
548   final(a,b,c);
549   *val2 = b;
550   return c;
551 }
552
553 /* I basically use hashlittle here, but use native endian within each
554  * element.  This delivers least-surprise: hash such as "int arr[] = {
555  * 1, 2 }; hash_stable(arr, 2, 0);" will be the same on big and little
556  * endian machines, even though a bytewise hash wouldn't be. */
557 uint64_t hash64_stable_64(const void *key, size_t n, uint64_t base)
558 {
559         const uint64_t *k = key;
560         uint32_t a,b,c;
561
562         /* Set up the internal state */
563         a = b = c = 0xdeadbeef + ((uint32_t)n*8) + (base >> 32) + base;
564
565         while (n > 3) {
566                 a += (uint32_t)k[0];
567                 b += (uint32_t)(k[0] >> 32);
568                 c += (uint32_t)k[1];
569                 mix(a,b,c);
570                 a += (uint32_t)(k[1] >> 32);
571                 b += (uint32_t)k[2];
572                 c += (uint32_t)(k[2] >> 32);
573                 mix(a,b,c);
574                 n -= 3;
575                 k += 3;
576         }
577         switch (n) {
578         case 2:
579                 a += (uint32_t)k[0];
580                 b += (uint32_t)(k[0] >> 32);
581                 c += (uint32_t)k[1];
582                 mix(a,b,c);
583                 a += (uint32_t)(k[1] >> 32);
584                 break;
585         case 1:
586                 a += (uint32_t)k[0];
587                 b += (uint32_t)(k[0] >> 32);
588                 break;
589         case 0:
590                 return c;
591         }
592         final(a,b,c);
593         return ((uint64_t)b << 32) | c;
594 }
595
596 uint64_t hash64_stable_32(const void *key, size_t n, uint64_t base)
597 {
598         const uint32_t *k = key;
599         uint32_t a,b,c;
600
601         /* Set up the internal state */
602         a = b = c = 0xdeadbeef + ((uint32_t)n*4) + (base >> 32) + base;
603
604         while (n > 3) {
605                 a += k[0];
606                 b += k[1];
607                 c += k[2];
608                 mix(a,b,c);
609
610                 n -= 3;
611                 k += 3;
612         }
613         switch (n) {
614         case 2:
615                 b += (uint32_t)k[1];
616         case 1:
617                 a += (uint32_t)k[0];
618                 break;
619         case 0:
620                 return c;
621         }
622         final(a,b,c);
623         return ((uint64_t)b << 32) | c;
624 }
625
626 uint64_t hash64_stable_16(const void *key, size_t n, uint64_t base)
627 {
628         const uint16_t *k = key;
629         uint32_t a,b,c;
630
631         /* Set up the internal state */
632         a = b = c = 0xdeadbeef + ((uint32_t)n*2) + (base >> 32) + base;
633
634         while (n > 6) {
635                 a += (uint32_t)k[0] + ((uint32_t)k[1] << 16);
636                 b += (uint32_t)k[2] + ((uint32_t)k[3] << 16);
637                 c += (uint32_t)k[4] + ((uint32_t)k[5] << 16);
638                 mix(a,b,c);
639
640                 n -= 6;
641                 k += 6;
642         }
643
644         switch (n) {
645         case 5:
646                 c += (uint32_t)k[4];
647         case 4:
648                 b += ((uint32_t)k[3] << 16);
649         case 3:
650                 b += (uint32_t)k[2];
651         case 2:
652                 a += ((uint32_t)k[1] << 16);
653         case 1:
654                 a += (uint32_t)k[0];
655                 break;
656         case 0:
657                 return c;
658         }
659         final(a,b,c);
660         return ((uint64_t)b << 32) | c;
661 }
662
663 uint64_t hash64_stable_8(const void *key, size_t n, uint64_t base)
664 {
665         uint32_t b32 = base + (base >> 32);
666         uint32_t lower = hashlittle(key, n, &b32);
667
668         return ((uint64_t)b32 << 32) | lower;   
669 }
670
671 uint32_t hash_any(const void *key, size_t length, uint32_t base)
672 {
673         if (HASH_BIG_ENDIAN)
674                 return hashbig(key, length, &base);
675         else
676                 return hashlittle(key, length, &base);
677 }
678
679 uint32_t hash_stable_64(const void *key, size_t n, uint32_t base)
680 {
681         return hash64_stable_64(key, n, base);
682 }
683
684 uint32_t hash_stable_32(const void *key, size_t n, uint32_t base)
685 {
686         return hash64_stable_32(key, n, base);
687 }
688
689 uint32_t hash_stable_16(const void *key, size_t n, uint32_t base)
690 {
691         return hash64_stable_16(key, n, base);
692 }
693
694 uint32_t hash_stable_8(const void *key, size_t n, uint32_t base)
695 {
696         return hashlittle(key, n, &base);
697 }
698
699 /* Jenkins' lookup8 is a 64 bit hash, but he says it's obsolete.  Use
700  * the plain one and recombine into 64 bits. */
701 uint64_t hash64_any(const void *key, size_t length, uint64_t base)
702 {
703         uint32_t b32 = base + (base >> 32);
704         uint32_t lower;
705
706         if (HASH_BIG_ENDIAN)
707                 lower = hashbig(key, length, &b32);
708         else
709                 lower = hashlittle(key, length, &b32);
710
711         return ((uint64_t)b32 << 32) | lower;
712 }
713
714 #ifdef SELF_TEST
715
716 /* used for timings */
717 void driver1()
718 {
719   uint8_t buf[256];
720   uint32_t i;
721   uint32_t h=0;
722   time_t a,z;
723
724   time(&a);
725   for (i=0; i<256; ++i) buf[i] = 'x';
726   for (i=0; i<1; ++i) 
727   {
728     h = hashlittle(&buf[0],1,h);
729   }
730   time(&z);
731   if (z-a > 0) printf("time %d %.8x\n", z-a, h);
732 }
733
734 /* check that every input bit changes every output bit half the time */
735 #define HASHSTATE 1
736 #define HASHLEN   1
737 #define MAXPAIR 60
738 #define MAXLEN  70
739 void driver2()
740 {
741   uint8_t qa[MAXLEN+1], qb[MAXLEN+2], *a = &qa[0], *b = &qb[1];
742   uint32_t c[HASHSTATE], d[HASHSTATE], i=0, j=0, k, l, m=0, z;
743   uint32_t e[HASHSTATE],f[HASHSTATE],g[HASHSTATE],h[HASHSTATE];
744   uint32_t x[HASHSTATE],y[HASHSTATE];
745   uint32_t hlen;
746
747   printf("No more than %d trials should ever be needed \n",MAXPAIR/2);
748   for (hlen=0; hlen < MAXLEN; ++hlen)
749   {
750     z=0;
751     for (i=0; i<hlen; ++i)  /*----------------------- for each input byte, */
752     {
753       for (j=0; j<8; ++j)   /*------------------------ for each input bit, */
754       {
755         for (m=1; m<8; ++m) /*------------ for several possible initvals, */
756         {
757           for (l=0; l<HASHSTATE; ++l)
758             e[l]=f[l]=g[l]=h[l]=x[l]=y[l]=~((uint32_t)0);
759
760           /*---- check that every output bit is affected by that input bit */
761           for (k=0; k<MAXPAIR; k+=2)
762           { 
763             uint32_t finished=1;
764             /* keys have one bit different */
765             for (l=0; l<hlen+1; ++l) {a[l] = b[l] = (uint8_t)0;}
766             /* have a and b be two keys differing in only one bit */
767             a[i] ^= (k<<j);
768             a[i] ^= (k>>(8-j));
769              c[0] = hashlittle(a, hlen, m);
770             b[i] ^= ((k+1)<<j);
771             b[i] ^= ((k+1)>>(8-j));
772              d[0] = hashlittle(b, hlen, m);
773             /* check every bit is 1, 0, set, and not set at least once */
774             for (l=0; l<HASHSTATE; ++l)
775             {
776               e[l] &= (c[l]^d[l]);
777               f[l] &= ~(c[l]^d[l]);
778               g[l] &= c[l];
779               h[l] &= ~c[l];
780               x[l] &= d[l];
781               y[l] &= ~d[l];
782               if (e[l]|f[l]|g[l]|h[l]|x[l]|y[l]) finished=0;
783             }
784             if (finished) break;
785           }
786           if (k>z) z=k;
787           if (k==MAXPAIR) 
788           {
789              printf("Some bit didn't change: ");
790              printf("%.8x %.8x %.8x %.8x %.8x %.8x  ",
791                     e[0],f[0],g[0],h[0],x[0],y[0]);
792              printf("i %d j %d m %d len %d\n", i, j, m, hlen);
793           }
794           if (z==MAXPAIR) goto done;
795         }
796       }
797     }
798    done:
799     if (z < MAXPAIR)
800     {
801       printf("Mix success  %2d bytes  %2d initvals  ",i,m);
802       printf("required  %d  trials\n", z/2);
803     }
804   }
805   printf("\n");
806 }
807
808 /* Check for reading beyond the end of the buffer and alignment problems */
809 void driver3()
810 {
811   uint8_t buf[MAXLEN+20], *b;
812   uint32_t len;
813   uint8_t q[] = "This is the time for all good men to come to the aid of their country...";
814   uint32_t h;
815   uint8_t qq[] = "xThis is the time for all good men to come to the aid of their country...";
816   uint32_t i;
817   uint8_t qqq[] = "xxThis is the time for all good men to come to the aid of their country...";
818   uint32_t j;
819   uint8_t qqqq[] = "xxxThis is the time for all good men to come to the aid of their country...";
820   uint32_t ref,x,y;
821   uint8_t *p;
822
823   printf("Endianness.  These lines should all be the same (for values filled in):\n");
824   printf("%.8x                            %.8x                            %.8x\n",
825          hash_word((const uint32_t *)q, (sizeof(q)-1)/4, 13),
826          hash_word((const uint32_t *)q, (sizeof(q)-5)/4, 13),
827          hash_word((const uint32_t *)q, (sizeof(q)-9)/4, 13));
828   p = q;
829   printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
830          hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
831          hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
832          hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
833          hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
834          hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
835          hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
836   p = &qq[1];
837   printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
838          hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
839          hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
840          hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
841          hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
842          hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
843          hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
844   p = &qqq[2];
845   printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
846          hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
847          hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
848          hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
849          hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
850          hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
851          hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
852   p = &qqqq[3];
853   printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
854          hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
855          hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
856          hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
857          hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
858          hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
859          hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
860   printf("\n");
861
862   /* check that hashlittle2 and hashlittle produce the same results */
863   i=47; j=0;
864   hashlittle2(q, sizeof(q), &i, &j);
865   if (hashlittle(q, sizeof(q), 47) != i)
866     printf("hashlittle2 and hashlittle mismatch\n");
867
868   /* check that hash_word2 and hash_word produce the same results */
869   len = 0xdeadbeef;
870   i=47, j=0;
871   hash_word2(&len, 1, &i, &j);
872   if (hash_word(&len, 1, 47) != i)
873     printf("hash_word2 and hash_word mismatch %x %x\n", 
874            i, hash_word(&len, 1, 47));
875
876   /* check hashlittle doesn't read before or after the ends of the string */
877   for (h=0, b=buf+1; h<8; ++h, ++b)
878   {
879     for (i=0; i<MAXLEN; ++i)
880     {
881       len = i;
882       for (j=0; j<i; ++j) *(b+j)=0;
883
884       /* these should all be equal */
885       ref = hashlittle(b, len, (uint32_t)1);
886       *(b+i)=(uint8_t)~0;
887       *(b-1)=(uint8_t)~0;
888       x = hashlittle(b, len, (uint32_t)1);
889       y = hashlittle(b, len, (uint32_t)1);
890       if ((ref != x) || (ref != y)) 
891       {
892         printf("alignment error: %.8x %.8x %.8x %d %d\n",ref,x,y,
893                h, i);
894       }
895     }
896   }
897 }
898
899 /* check for problems with nulls */
900  void driver4()
901 {
902   uint8_t buf[1];
903   uint32_t h,i,state[HASHSTATE];
904
905
906   buf[0] = ~0;
907   for (i=0; i<HASHSTATE; ++i) state[i] = 1;
908   printf("These should all be different\n");
909   for (i=0, h=0; i<8; ++i)
910   {
911     h = hashlittle(buf, 0, h);
912     printf("%2ld  0-byte strings, hash is  %.8x\n", i, h);
913   }
914 }
915
916
917 int main()
918 {
919   driver1();   /* test that the key is hashed: used for timings */
920   driver2();   /* test that whole key is hashed thoroughly */
921   driver3();   /* test that nothing but the key is hashed */
922   driver4();   /* test hashing multiple buffers (all buffers are null) */
923   return 1;
924 }
925
926 #endif  /* SELF_TEST */