2   May 2019(Wouter) patch to enable the valgrind clean implementation all the
8      added #ifdef VALGRIND to remove 298,384,660 'unused variable k8' warnings.
10      removed include of stdint - config.h takes care of platform independence.
15 -------------------------------------------------------------------------------
18 These are functions for producing 32-bit hashes for hash table lookup.
26 little-endian machines.  Intel and AMD are little-endian machines.
28 hashlittle() except it returns two 32-bit hashes for the price of one.  
39 4-byte integers to hash, use hashword().  If you have a byte array (like
43 Why is this so big?  I read 12 bytes at a time into 3 4-byte integers, 
47 -------------------------------------------------------------------------------
60  * use that. Otherwise try to work out the endianness.
86    * My best guess at if you are big-endian or little-endian.  This may
117 #define hashmask(n) (hashsize(n)-1)
118 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
130 -------------------------------------------------------------------------------
131 mix -- mix 3 32-bit values reversibly.
143 * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
145   is commonly produced by subtraction) look like a single 1-bit
150 Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
156 for "differ" defined as + with a one-bit base and a two-bit delta.  I
165 This allows some parallelism.  Read-after-writes are good at doubling
171 -------------------------------------------------------------------------------
175   a -= c;  a ^= rot(c, 4);  c += b; \
176   b -= a;  b ^= rot(a, 6);  a += c; \
177   c -= b;  c ^= rot(b, 8);  b += a; \
178   a -= c;  a ^= rot(c,16);  c += b; \
179   b -= a;  b ^= rot(a,19);  a += c; \
180   c -= b;  c ^= rot(b, 4);  b += a; \
184 -------------------------------------------------------------------------------
185 final -- final mixing of 3 32-bit values (a,b,c) into c
192 * "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
194   is commonly produced by subtraction) look like a single 1-bit
206 -------------------------------------------------------------------------------
210   c ^= b; c -= rot(b,14); \
211   a ^= c; a -= rot(c,11); \
212   b ^= a; b -= rot(a,25); \
213   c ^= b; c -= rot(b,16); \
214   a ^= c; a -= rot(c,4);  \
215   b ^= a; b -= rot(a,14); \
216   c ^= b; c -= rot(b,24); \
220 --------------------------------------------------------------------
222  -- that the key be an array of uint32_t's, and
223  -- that the length be the number of uint32_t's in the key
225  The function hashword() is identical to hashlittle() on little-endian
226  machines, and identical to hashbig() on big-endian machines,
230 --------------------------------------------------------------------
242   /*------------------------------------------------- handle most of the key */  in hashword()
249     length -= 3;  in hashword()
253   /*------------------------------------------- handle the last 3 uint32_t's */  in hashword()
269   /*------------------------------------------------------ report the result */  in hashword()
277 --------------------------------------------------------------------
278 hashword2() -- same as hashword(), but take two seeds and return two
279 32-bit values.  pc and pb must both be nonnull, and *pc and *pb must
282 --------------------------------------------------------------------
287 uint32_t       *pc,                      /* IN: seed OUT: primary hash value */  in hashword2()
288 uint32_t       *pb)               /* IN: more seed OUT: secondary hash value */  in hashword2()
296   /*------------------------------------------------- handle most of the key */  in hashword2()
303     length -= 3;  in hashword2()
307   /*------------------------------------------- handle the last 3 uint32_t's */  in hashword2()
323   /*------------------------------------------------------ report the result */  in hashword2()
330 -------------------------------------------------------------------------------
331 hashlittle() -- hash a variable-length key into a 32-bit value
332   k       : the key (the unaligned variable-length array of bytes)
334   initval : can be any 4-byte value
335 Returns a 32-bit value.  Every bit of the key affects every bit of
353 -------------------------------------------------------------------------------
366     const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */  in hashlittle()
371     /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */  in hashlittle()
378       length -= 12;  in hashlittle()
382     /*----------------------------- handle the last (probably partial) block */  in hashlittle()
386      * string is aligned, the masked-off tail is in the same word as the  in hashlittle()
388      * does it on word boundaries, so is OK with this.  But VALGRIND will  in hashlittle()
411 #else /* make valgrind happy */  in hashlittle()
447 #endif /* !valgrind */  in hashlittle()
450     const uint16_t *k = (const uint16_t *)key;         /* read 16-bit chunks */  in hashlittle()
453     /*--------------- all but last block: aligned reads and different mixing */  in hashlittle()
460       length -= 12;  in hashlittle()
464     /*----------------------------- handle the last (probably partial) block */  in hashlittle()
509     /*--------------- all but the last block: affect some 32 bits of (a,b,c) */  in hashlittle()
525       length -= 12;  in hashlittle()
529     /*-------------------------------- last block: affect all 32 bits of (c) */  in hashlittle()
578  * hashlittle2: return 2 32-bit hash values
580  * This is identical to hashlittle(), except it returns two 32-bit hash
583  * happy with the first, or if you want a probably-unique 64-bit ID for
585  * a 64-bit value do something like "*pc + (((uint64_t)*pb)<<32)".
590   uint32_t   *pc,        /* IN: primary initval, OUT: primary hash */  in hashlittle2()
591   uint32_t   *pb)        /* IN: secondary initval, OUT: secondary hash */  in hashlittle2()
602     const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */  in hashlittle2()
603 #ifdef VALGRIND  in hashlittle2()
607     /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */  in hashlittle2()
614       length -= 12;  in hashlittle2()
618     /*----------------------------- handle the last (probably partial) block */  in hashlittle2()
622      * string is aligned, the masked-off tail is in the same word as the  in hashlittle2()
624      * does it on word boundaries, so is OK with this.  But VALGRIND will  in hashlittle2()
628 #ifndef VALGRIND  in hashlittle2()
647 #else /* make valgrind happy */  in hashlittle2()
683 #endif /* !valgrind */  in hashlittle2()
686     const uint16_t *k = (const uint16_t *)key;         /* read 16-bit chunks */  in hashlittle2()
689     /*--------------- all but last block: aligned reads and different mixing */  in hashlittle2()
696       length -= 12;  in hashlittle2()
700     /*----------------------------- handle the last (probably partial) block */  in hashlittle2()
745     /*--------------- all but the last block: affect some 32 bits of (a,b,c) */  in hashlittle2()
761       length -= 12;  in hashlittle2()
765     /*-------------------------------- last block: affect all 32 bits of (c) */  in hashlittle2()
817  * This is the same as hashword() on big-endian machines.  It is different
819  * big-endian byte ordering. 
831     const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */
832 #ifdef VALGRIND
836     /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
843       length -= 12;
847     /*----------------------------- handle the last (probably partial) block */
850      * then shifts out the part it's not allowed to read.  Because the
853      * does it on word boundaries, so is OK with this.  But VALGRIND will
857 #ifndef VALGRIND
876 #else  /* make valgrind happy */
912 #endif /* !VALGRIND */
917     /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
933       length -= 12;
937     /*-------------------------------- last block: affect all 32 bits of (c) */
1002   if (z-a > 0) printf("time %d %.8x\n", z-a, h);  in driver1()
1022     for (i=0; i<hlen; ++i)  /*----------------------- for each input byte, */  in driver2()
1024       for (j=0; j<8; ++j)   /*------------------------ for each input bit, */  in driver2()
1026 	for (m=1; m<8; ++m) /*------------ for several possible initvals, */  in driver2()
1031       	  /*---- check that every output bit is affected by that input bit */  in driver2()
1039 	    a[i] ^= (k>>(8-j));  in driver2()
1042 	    b[i] ^= ((k+1)>>(8-j));  in driver2()
1096          hashword((const uint32_t *)q, (sizeof(q)-1)/4, 13),  in driver3()
1097          hashword((const uint32_t *)q, (sizeof(q)-5)/4, 13),  in driver3()
1098          hashword((const uint32_t *)q, (sizeof(q)-9)/4, 13));  in driver3()
1101          hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),  in driver3()
1102          hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),  in driver3()
1103          hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),  in driver3()
1104          hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),  in driver3()
1105          hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),  in driver3()
1106          hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));  in driver3()
1109          hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),  in driver3()
1110          hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),  in driver3()
1111          hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),  in driver3()
1112          hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),  in driver3()
1113          hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),  in driver3()
1114          hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));  in driver3()
1117          hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),  in driver3()
1118          hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),  in driver3()
1119          hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),  in driver3()
1120          hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),  in driver3()
1121          hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),  in driver3()
1122          hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));  in driver3()
1125          hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),  in driver3()
1126          hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),  in driver3()
1127          hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),  in driver3()
1128          hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),  in driver3()
1129          hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),  in driver3()
1130          hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));  in driver3()
1158       *(b-1)=(uint8_t)~0;  in driver3()
1183     printf("%2ld  0-byte strings, hash is  %.8x\n", i, h);  in driver4()