46 on 1 byte), but shoehorning those bytes into integers efficiently is messy.
49 /*#define SELF_TEST 1*/
50 #define ARRAY_CLEAN_ACCESS 1
65 #  define HASH_BIG_ENDIAN 1
67 #  define HASH_LITTLE_ENDIAN 1
93 #  define HASH_LITTLE_ENDIAN 1
99 #  define HASH_BIG_ENDIAN 1
104 #   define HASH_BIG_ENDIAN 1
107 #   define HASH_LITTLE_ENDIAN 1
116 #define hashsize(n) ((uint32_t)1<<(n))
117 #define hashmask(n) (hashsize(n)-1)
118 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))  argument
144   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
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
193   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
194   is commonly produced by subtraction) look like a single 1-bit
233 const uint32_t *k,                   /* the key, an array of uint32_t values */  in hashword()  argument
245     a += k[0];  in hashword()
246     b += k[1];  in hashword()
247     c += k[2];  in hashword()
250     k += 3;  in hashword()
256   case 3 : c+=k[2];  in hashword()
259   case 2 : b+=k[1];  in hashword()
262   case 1 : a+=k[0];  in hashword()
285 const uint32_t *k,                   /* the key, an array of uint32_t values */  in hashword2()  argument
299     a += k[0];  in hashword2()
300     b += k[1];  in hashword2()
301     c += k[2];  in hashword2()
304     k += 3;  in hashword2()
310   case 3 : c+=k[2];  in hashword2()
313   case 2 : b+=k[1];  in hashword2()
316   case 1 : a+=k[0];  in hashword2()
332   k       : the key (the unaligned variable-length array of bytes)
345 If you are hashing n strings (uint8_t **)k, do it like this:
346   for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
366     const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */  in hashlittle()  local
374       a += k[0];  in hashlittle()
375       b += k[1];  in hashlittle()
376       c += k[2];  in hashlittle()
379       k += 3;  in hashlittle()
384      * "k[2]&0xffffff" actually reads beyond the end of the string, but  in hashlittle()
396     case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;  in hashlittle()
397     case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;  in hashlittle()
398     case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;  in hashlittle()
399     case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;  in hashlittle()
400     case 8 : b+=k[1]; a+=k[0]; break;  in hashlittle()
401     case 7 : b+=k[1]&0xffffff; a+=k[0]; break;  in hashlittle()
402     case 6 : b+=k[1]&0xffff; a+=k[0]; break;  in hashlittle()
403     case 5 : b+=k[1]&0xff; a+=k[0]; break;  in hashlittle()
404     case 4 : a+=k[0]; break;  in hashlittle()
405     case 3 : a+=k[0]&0xffffff; break;  in hashlittle()
406     case 2 : a+=k[0]&0xffff; break;  in hashlittle()
407     case 1 : a+=k[0]&0xff; break;  in hashlittle()
413     k8 = (const uint8_t *)k;  in hashlittle()
416     case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;  in hashlittle()
426     case 8 : b+=k[1]; a+=k[0]; break;  in hashlittle()
436     case 4 : a+=k[0]; break;  in hashlittle()
440     case 2 : a+=((uint32_t)k8[1])<<8;  in hashlittle()
443     case 1 : a+=k8[0]; break;  in hashlittle()
450     const uint16_t *k = (const uint16_t *)key;         /* read 16-bit chunks */  in hashlittle()  local
456       a += k[0] + (((uint32_t)k[1])<<16);  in hashlittle()
457       b += k[2] + (((uint32_t)k[3])<<16);  in hashlittle()
458       c += k[4] + (((uint32_t)k[5])<<16);  in hashlittle()
461       k += 6;  in hashlittle()
465     k8 = (const uint8_t *)k;  in hashlittle()
468     case 12: c+=k[4]+(((uint32_t)k[5])<<16);  in hashlittle()
469              b+=k[2]+(((uint32_t)k[3])<<16);  in hashlittle()
470              a+=k[0]+(((uint32_t)k[1])<<16);  in hashlittle()
475     case 10: c+=k[4];  in hashlittle()
476              b+=k[2]+(((uint32_t)k[3])<<16);  in hashlittle()
477              a+=k[0]+(((uint32_t)k[1])<<16);  in hashlittle()
482     case 8 : b+=k[2]+(((uint32_t)k[3])<<16);  in hashlittle()
483              a+=k[0]+(((uint32_t)k[1])<<16);  in hashlittle()
488     case 6 : b+=k[2];  in hashlittle()
489              a+=k[0]+(((uint32_t)k[1])<<16);  in hashlittle()
494     case 4 : a+=k[0]+(((uint32_t)k[1])<<16);  in hashlittle()
499     case 2 : a+=k[0];  in hashlittle()
501     case 1 : a+=k8[0];  in hashlittle()
507     const uint8_t *k = (const uint8_t *)key;  in hashlittle()  local
512       a += k[0];  in hashlittle()
513       a += ((uint32_t)k[1])<<8;  in hashlittle()
514       a += ((uint32_t)k[2])<<16;  in hashlittle()
515       a += ((uint32_t)k[3])<<24;  in hashlittle()
516       b += k[4];  in hashlittle()
517       b += ((uint32_t)k[5])<<8;  in hashlittle()
518       b += ((uint32_t)k[6])<<16;  in hashlittle()
519       b += ((uint32_t)k[7])<<24;  in hashlittle()
520       c += k[8];  in hashlittle()
521       c += ((uint32_t)k[9])<<8;  in hashlittle()
522       c += ((uint32_t)k[10])<<16;  in hashlittle()
523       c += ((uint32_t)k[11])<<24;  in hashlittle()
526       k += 12;  in hashlittle()
532     case 12: c+=((uint32_t)k[11])<<24;  in hashlittle()
535     case 11: c+=((uint32_t)k[10])<<16;  in hashlittle()
538     case 10: c+=((uint32_t)k[9])<<8;  in hashlittle()
541     case 9 : c+=k[8];  in hashlittle()
544     case 8 : b+=((uint32_t)k[7])<<24;  in hashlittle()
547     case 7 : b+=((uint32_t)k[6])<<16;  in hashlittle()
550     case 6 : b+=((uint32_t)k[5])<<8;  in hashlittle()
553     case 5 : b+=k[4];  in hashlittle()
556     case 4 : a+=((uint32_t)k[3])<<24;  in hashlittle()
559     case 3 : a+=((uint32_t)k[2])<<16;  in hashlittle()
562     case 2 : a+=((uint32_t)k[1])<<8;  in hashlittle()
565     case 1 : a+=k[0];  in hashlittle()
602     const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */  in hashlittle2()  local
610       a += k[0];  in hashlittle2()
611       b += k[1];  in hashlittle2()
612       c += k[2];  in hashlittle2()
615       k += 3;  in hashlittle2()
620      * "k[2]&0xffffff" actually reads beyond the end of the string, but  in hashlittle2()
632     case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;  in hashlittle2()
633     case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;  in hashlittle2()
634     case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;  in hashlittle2()
635     case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;  in hashlittle2()
636     case 8 : b+=k[1]; a+=k[0]; break;  in hashlittle2()
637     case 7 : b+=k[1]&0xffffff; a+=k[0]; break;  in hashlittle2()
638     case 6 : b+=k[1]&0xffff; a+=k[0]; break;  in hashlittle2()
639     case 5 : b+=k[1]&0xff; a+=k[0]; break;  in hashlittle2()
640     case 4 : a+=k[0]; break;  in hashlittle2()
641     case 3 : a+=k[0]&0xffffff; break;  in hashlittle2()
642     case 2 : a+=k[0]&0xffff; break;  in hashlittle2()
643     case 1 : a+=k[0]&0xff; break;  in hashlittle2()
649     k8 = (const uint8_t *)k;  in hashlittle2()
652     case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;  in hashlittle2()
662     case 8 : b+=k[1]; a+=k[0]; break;  in hashlittle2()
672     case 4 : a+=k[0]; break;  in hashlittle2()
676     case 2 : a+=((uint32_t)k8[1])<<8;  in hashlittle2()
679     case 1 : a+=k8[0]; break;  in hashlittle2()
686     const uint16_t *k = (const uint16_t *)key;         /* read 16-bit chunks */  in hashlittle2()  local
692       a += k[0] + (((uint32_t)k[1])<<16);  in hashlittle2()
693       b += k[2] + (((uint32_t)k[3])<<16);  in hashlittle2()
694       c += k[4] + (((uint32_t)k[5])<<16);  in hashlittle2()
697       k += 6;  in hashlittle2()
701     k8 = (const uint8_t *)k;  in hashlittle2()
704     case 12: c+=k[4]+(((uint32_t)k[5])<<16);  in hashlittle2()
705              b+=k[2]+(((uint32_t)k[3])<<16);  in hashlittle2()
706              a+=k[0]+(((uint32_t)k[1])<<16);  in hashlittle2()
711     case 10: c+=k[4];  in hashlittle2()
712              b+=k[2]+(((uint32_t)k[3])<<16);  in hashlittle2()
713              a+=k[0]+(((uint32_t)k[1])<<16);  in hashlittle2()
718     case 8 : b+=k[2]+(((uint32_t)k[3])<<16);  in hashlittle2()
719              a+=k[0]+(((uint32_t)k[1])<<16);  in hashlittle2()
724     case 6 : b+=k[2];  in hashlittle2()
725              a+=k[0]+(((uint32_t)k[1])<<16);  in hashlittle2()
730     case 4 : a+=k[0]+(((uint32_t)k[1])<<16);  in hashlittle2()
735     case 2 : a+=k[0];  in hashlittle2()
737     case 1 : a+=k8[0];  in hashlittle2()
743     const uint8_t *k = (const uint8_t *)key;  in hashlittle2()  local
748       a += k[0];  in hashlittle2()
749       a += ((uint32_t)k[1])<<8;  in hashlittle2()
750       a += ((uint32_t)k[2])<<16;  in hashlittle2()
751       a += ((uint32_t)k[3])<<24;  in hashlittle2()
752       b += k[4];  in hashlittle2()
753       b += ((uint32_t)k[5])<<8;  in hashlittle2()
754       b += ((uint32_t)k[6])<<16;  in hashlittle2()
755       b += ((uint32_t)k[7])<<24;  in hashlittle2()
756       c += k[8];  in hashlittle2()
757       c += ((uint32_t)k[9])<<8;  in hashlittle2()
758       c += ((uint32_t)k[10])<<16;  in hashlittle2()
759       c += ((uint32_t)k[11])<<24;  in hashlittle2()
762       k += 12;  in hashlittle2()
768     case 12: c+=((uint32_t)k[11])<<24;  in hashlittle2()
771     case 11: c+=((uint32_t)k[10])<<16;  in hashlittle2()
774     case 10: c+=((uint32_t)k[9])<<8;  in hashlittle2()
777     case 9 : c+=k[8];  in hashlittle2()
780     case 8 : b+=((uint32_t)k[7])<<24;  in hashlittle2()
783     case 7 : b+=((uint32_t)k[6])<<16;  in hashlittle2()
786     case 6 : b+=((uint32_t)k[5])<<8;  in hashlittle2()
789     case 5 : b+=k[4];  in hashlittle2()
792     case 4 : a+=((uint32_t)k[3])<<24;  in hashlittle2()
795     case 3 : a+=((uint32_t)k[2])<<16;  in hashlittle2()
798     case 2 : a+=((uint32_t)k[1])<<8;  in hashlittle2()
801     case 1 : a+=k[0];  in hashlittle2()
831     const uint32_t *k = (const uint32_t *)key;         /* read 32-bit chunks */
839       a += k[0];
840       b += k[1];
841       c += k[2];
844       k += 3;
849      * "k[2]<<8" actually reads beyond the end of the string, but
861     case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
862     case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break;
863     case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break;
864     case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break;
865     case 8 : b+=k[1]; a+=k[0]; break;
866     case 7 : b+=k[1]&0xffffff00; a+=k[0]; break;
867     case 6 : b+=k[1]&0xffff0000; a+=k[0]; break;
868     case 5 : b+=k[1]&0xff000000; a+=k[0]; break;
869     case 4 : a+=k[0]; break;
870     case 3 : a+=k[0]&0xffffff00; break;
871     case 2 : a+=k[0]&0xffff0000; break;
872     case 1 : a+=k[0]&0xff000000; break;
878     k8 = (const uint8_t *)k;
881     case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
891     case 8 : b+=k[1]; a+=k[0]; break;
901     case 4 : a+=k[0]; break;
905     case 2 : a+=((uint32_t)k8[1])<<16;
908     case 1 : a+=((uint32_t)k8[0])<<24; break;
915     const uint8_t *k = (const uint8_t *)key;
920       a += ((uint32_t)k[0])<<24;
921       a += ((uint32_t)k[1])<<16;
922       a += ((uint32_t)k[2])<<8;
923       a += ((uint32_t)k[3]);
924       b += ((uint32_t)k[4])<<24;
925       b += ((uint32_t)k[5])<<16;
926       b += ((uint32_t)k[6])<<8;
927       b += ((uint32_t)k[7]);
928       c += ((uint32_t)k[8])<<24;
929       c += ((uint32_t)k[9])<<16;
930       c += ((uint32_t)k[10])<<8;
931       c += ((uint32_t)k[11]);
934       k += 12;
940     case 12: c+=k[11];
943     case 11: c+=((uint32_t)k[10])<<8;
946     case 10: c+=((uint32_t)k[9])<<16;
949     case 9 : c+=((uint32_t)k[8])<<24;
952     case 8 : b+=k[7];
955     case 7 : b+=((uint32_t)k[6])<<8;
958     case 6 : b+=((uint32_t)k[5])<<16;
961     case 5 : b+=((uint32_t)k[4])<<24;
964     case 4 : a+=k[3];
967     case 3 : a+=((uint32_t)k[2])<<8;
970     case 2 : a+=((uint32_t)k[1])<<16;
973     case 1 : a+=((uint32_t)k[0])<<24;
997   for (i=0; i<1; ++i)   in driver1()
999     h = hashlittle(&buf[0],1,h);  in driver1()
1006 #define HASHSTATE 1
1007 #define HASHLEN   1
1012   uint8_t qa[MAXLEN+1], qb[MAXLEN+2], *a = &qa[0], *b = &qb[1];  in driver2()
1013   uint32_t c[HASHSTATE], d[HASHSTATE], i=0, j=0, k, l, m=0, z;  in driver2()  local
1026 	for (m=1; m<8; ++m) /*------------ for several possible initvals, */  in driver2()
1032 	  for (k=0; k<MAXPAIR; k+=2)  in driver2()
1034 	    uint32_t finished=1;  in driver2()
1036 	    for (l=0; l<hlen+1; ++l) {a[l] = b[l] = (uint8_t)0;}  in driver2()
1038 	    a[i] ^= (k<<j);  in driver2()
1039 	    a[i] ^= (k>>(8-j));  in driver2()
1041 	    b[i] ^= ((k+1)<<j);  in driver2()
1042 	    b[i] ^= ((k+1)>>(8-j));  in driver2()
1044 	    /* check every bit is 1, 0, set, and not set at least once */  in driver2()
1057 	  if (k>z) z=k;  in driver2()
1058 	  if (k==MAXPAIR)   in driver2()
1096          hashword((const uint32_t *)q, (sizeof(q)-1)/4, 13),  in driver3()
1101          hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),  in driver3()
1107   p = &qq[1];  in driver3()
1109          hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),  in driver3()
1117          hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),  in driver3()
1125          hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),  in driver3()
1142   hashword2(&len, 1, &i, &j);  in driver3()
1143   if (hashword(&len, 1, 47) != i)  in driver3()
1145 	   i, hashword(&len, 1, 47));  in driver3()
1148   for (h=0, b=buf+1; h<8; ++h, ++b)  in driver3()
1156       ref = hashlittle(b, len, (uint32_t)1);  in driver3()
1158       *(b-1)=(uint8_t)~0;  in driver3()
1159       x = hashlittle(b, len, (uint32_t)1);  in driver3()
1160       y = hashlittle(b, len, (uint32_t)1);  in driver3()
1173   uint8_t buf[1];  in driver4()
1178   for (i=0; i<HASHSTATE; ++i) state[i] = 1;  in driver4()
1194   return 1;  in main()