41 #include <sys/param.h>
51 #if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \
52 __BYTE_ORDER == __LITTLE_ENDIAN) || \
53 (defined(i386) || defined(__i386__) || defined(__i486__) || \
54 defined(__i586__) || defined(__i686__) || defined(vax) || defined(MIPSEL))
55 # define HASH_LITTLE_ENDIAN 1
56 # define HASH_BIG_ENDIAN 0
57 #elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \
58 __BYTE_ORDER == __BIG_ENDIAN) || \
59 (defined(sparc) || defined(POWERPC) || defined(mc68000) || defined(sel))
60 # define HASH_LITTLE_ENDIAN 0
61 # define HASH_BIG_ENDIAN 1
63 # define HASH_LITTLE_ENDIAN 0
64 # define HASH_BIG_ENDIAN 0
67 #define hashsize(n) ((uint32_t)1<<(n))
68 #define hashmask(n) (hashsize(n)-1)
69 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
117 a -= c; a ^= rot(c, 4); c += b; \
118 b -= a; b ^= rot(a, 6); a += c; \
119 c -= b; c ^= rot(b, 8); b += a; \
120 a -= c; a ^= rot(c,16); c += b; \
121 b -= a; b ^= rot(a,19); a += c; \
122 c -= b; c ^= rot(b, 4); b += a; \
150 #define final(a,b,c) \
152 c ^= b; c -= rot(b,14); \
153 a ^= c; a -= rot(c,11); \
154 b ^= a; b -= rot(a,25); \
155 c ^= b; c -= rot(b,16); \
156 a ^= c; a -= rot(c,4); \
157 b ^= a; b -= rot(a,14); \
158 c ^= b; c -= rot(b,24); \
182 a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval;
227 a = b = c = 0xdeadbeef + ((uint32_t)(length<<2)) + *pc;
283 uint32_t
hashlittle(
const void *key,
size_t length, uint32_t initval)
286 union {
const void *ptr;
size_t i; } u;
289 a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
293 const uint32_t *k = (
const uint32_t *)key;
320 case 12: c+=k[2]; b+=k[1]; a+=k[0];
break;
321 case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0];
break;
322 case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0];
break;
323 case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0];
break;
324 case 8 : b+=k[1]; a+=k[0];
break;
325 case 7 : b+=k[1]&0xffffff; a+=k[0];
break;
326 case 6 : b+=k[1]&0xffff; a+=k[0];
break;
327 case 5 : b+=k[1]&0xff; a+=k[0];
break;
328 case 4 : a+=k[0];
break;
329 case 3 : a+=k[0]&0xffffff;
break;
330 case 2 : a+=k[0]&0xffff;
break;
331 case 1 : a+=k[0]&0xff;
break;
337 const uint8_t *k8 = (
const uint8_t *)k;
341 case 12: c+=k[2]; b+=k[1]; a+=k[0];
break;
342 case 11: c+=((uint32_t)k8[10])<<16;
343 case 10: c+=((uint32_t)k8[9])<<8;
345 case 8 : b+=k[1]; a+=k[0];
break;
346 case 7 : b+=((uint32_t)k8[6])<<16;
347 case 6 : b+=((uint32_t)k8[5])<<8;
349 case 4 : a+=k[0];
break;
350 case 3 : a+=((uint32_t)k8[2])<<16;
351 case 2 : a+=((uint32_t)k8[1])<<8;
352 case 1 : a+=k8[0];
break;
359 const uint16_t *k = (
const uint16_t *)key;
365 a += k[0] + (((uint32_t)k[1])<<16);
366 b += k[2] + (((uint32_t)k[3])<<16);
367 c += k[4] + (((uint32_t)k[5])<<16);
374 k8 = (
const uint8_t *)k;
377 case 12: c+=k[4]+(((uint32_t)k[5])<<16);
378 b+=k[2]+(((uint32_t)k[3])<<16);
379 a+=k[0]+(((uint32_t)k[1])<<16);
381 case 11: c+=((uint32_t)k8[10])<<16;
383 b+=k[2]+(((uint32_t)k[3])<<16);
384 a+=k[0]+(((uint32_t)k[1])<<16);
387 case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
388 a+=k[0]+(((uint32_t)k[1])<<16);
390 case 7 : b+=((uint32_t)k8[6])<<16;
392 a+=k[0]+(((uint32_t)k[1])<<16);
395 case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
397 case 3 : a+=((uint32_t)k8[2])<<16;
406 const uint8_t *k = (
const uint8_t *)key;
412 a += ((uint32_t)k[1])<<8;
413 a += ((uint32_t)k[2])<<16;
414 a += ((uint32_t)k[3])<<24;
416 b += ((uint32_t)k[5])<<8;
417 b += ((uint32_t)k[6])<<16;
418 b += ((uint32_t)k[7])<<24;
420 c += ((uint32_t)k[9])<<8;
421 c += ((uint32_t)k[10])<<16;
422 c += ((uint32_t)k[11])<<24;
431 case 12: c+=((uint32_t)k[11])<<24;
432 case 11: c+=((uint32_t)k[10])<<16;
433 case 10: c+=((uint32_t)k[9])<<8;
435 case 8 : b+=((uint32_t)k[7])<<24;
436 case 7 : b+=((uint32_t)k[6])<<16;
437 case 6 : b+=((uint32_t)k[5])<<8;
439 case 4 : a+=((uint32_t)k[3])<<24;
440 case 3 : a+=((uint32_t)k[2])<<16;
441 case 2 : a+=((uint32_t)k[1])<<8;
487 union {
const void *ptr;
size_t i; } u;
490 a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
494 const uint32_t *k = (
const uint32_t *)key;
514 const uint8_t *k8 = (
const uint8_t *)k;
518 case 12: c+=k[2]; b+=k[1]; a+=k[0];
break;
519 case 11: c+=((uint32_t)k8[10])<<16;
520 case 10: c+=((uint32_t)k8[9])<<8;
522 case 8 : b+=k[1]; a+=k[0];
break;
523 case 7 : b+=((uint32_t)k8[6])<<16;
524 case 6 : b+=((uint32_t)k8[5])<<8;
526 case 4 : a+=k[0];
break;
527 case 3 : a+=((uint32_t)k8[2])<<16;
528 case 2 : a+=((uint32_t)k8[1])<<8;
529 case 1 : a+=k8[0];
break;
533 const uint16_t *k = (
const uint16_t *)key;
539 a += k[0] + (((uint32_t)k[1])<<16);
540 b += k[2] + (((uint32_t)k[3])<<16);
541 c += k[4] + (((uint32_t)k[5])<<16);
548 k8 = (
const uint8_t *)k;
551 case 12: c+=k[4]+(((uint32_t)k[5])<<16);
552 b+=k[2]+(((uint32_t)k[3])<<16);
553 a+=k[0]+(((uint32_t)k[1])<<16);
555 case 11: c+=((uint32_t)k8[10])<<16;
557 b+=k[2]+(((uint32_t)k[3])<<16);
558 a+=k[0]+(((uint32_t)k[1])<<16);
561 case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
562 a+=k[0]+(((uint32_t)k[1])<<16);
564 case 7 : b+=((uint32_t)k8[6])<<16;
566 a+=k[0]+(((uint32_t)k[1])<<16);
569 case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
571 case 3 : a+=((uint32_t)k8[2])<<16;
580 const uint8_t *k = (
const uint8_t *)key;
586 a += ((uint32_t)k[1])<<8;
587 a += ((uint32_t)k[2])<<16;
588 a += ((uint32_t)k[3])<<24;
590 b += ((uint32_t)k[5])<<8;
591 b += ((uint32_t)k[6])<<16;
592 b += ((uint32_t)k[7])<<24;
594 c += ((uint32_t)k[9])<<8;
595 c += ((uint32_t)k[10])<<16;
596 c += ((uint32_t)k[11])<<24;
605 case 12: c+=((uint32_t)k[11])<<24;
606 case 11: c+=((uint32_t)k[10])<<16;
607 case 10: c+=((uint32_t)k[9])<<8;
609 case 8 : b+=((uint32_t)k[7])<<24;
610 case 7 : b+=((uint32_t)k[6])<<16;
611 case 6 : b+=((uint32_t)k[5])<<8;
613 case 4 : a+=((uint32_t)k[3])<<24;
614 case 3 : a+=((uint32_t)k[2])<<16;
615 case 2 : a+=((uint32_t)k[1])<<8;
644 union {
const void *ptr;
size_t i; } u;
647 a = b = c = 0xdeadbeef + ((uint32_t)length) + *pc;
652 const uint32_t *k = (
const uint32_t *)key;
679 case 12: c+=k[2]; b+=k[1]; a+=k[0];
break;
680 case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0];
break;
681 case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0];
break;
682 case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0];
break;
683 case 8 : b+=k[1]; a+=k[0];
break;
684 case 7 : b+=k[1]&0xffffff; a+=k[0];
break;
685 case 6 : b+=k[1]&0xffff; a+=k[0];
break;
686 case 5 : b+=k[1]&0xff; a+=k[0];
break;
687 case 4 : a+=k[0];
break;
688 case 3 : a+=k[0]&0xffffff;
break;
689 case 2 : a+=k[0]&0xffff;
break;
690 case 1 : a+=k[0]&0xff;
break;
691 case 0 : *pc=c; *pb=b;
return;
696 const uint8_t *k8 = (
const uint8_t *)k;
699 case 12: c+=k[2]; b+=k[1]; a+=k[0];
break;
700 case 11: c+=((uint32_t)k8[10])<<16;
701 case 10: c+=((uint32_t)k8[9])<<8;
703 case 8 : b+=k[1]; a+=k[0];
break;
704 case 7 : b+=((uint32_t)k8[6])<<16;
705 case 6 : b+=((uint32_t)k8[5])<<8;
707 case 4 : a+=k[0];
break;
708 case 3 : a+=((uint32_t)k8[2])<<16;
709 case 2 : a+=((uint32_t)k8[1])<<8;
710 case 1 : a+=k8[0];
break;
711 case 0 : *pc=c; *pb=b;
return;
717 const uint16_t *k = (
const uint16_t *)key;
723 a += k[0] + (((uint32_t)k[1])<<16);
724 b += k[2] + (((uint32_t)k[3])<<16);
725 c += k[4] + (((uint32_t)k[5])<<16);
732 k8 = (
const uint8_t *)k;
735 case 12: c+=k[4]+(((uint32_t)k[5])<<16);
736 b+=k[2]+(((uint32_t)k[3])<<16);
737 a+=k[0]+(((uint32_t)k[1])<<16);
739 case 11: c+=((uint32_t)k8[10])<<16;
741 b+=k[2]+(((uint32_t)k[3])<<16);
742 a+=k[0]+(((uint32_t)k[1])<<16);
745 case 8 : b+=k[2]+(((uint32_t)k[3])<<16);
746 a+=k[0]+(((uint32_t)k[1])<<16);
748 case 7 : b+=((uint32_t)k8[6])<<16;
750 a+=k[0]+(((uint32_t)k[1])<<16);
753 case 4 : a+=k[0]+(((uint32_t)k[1])<<16);
755 case 3 : a+=((uint32_t)k8[2])<<16;
760 case 0 : *pc=c; *pb=b;
return;
764 const uint8_t *k = (
const uint8_t *)key;
770 a += ((uint32_t)k[1])<<8;
771 a += ((uint32_t)k[2])<<16;
772 a += ((uint32_t)k[3])<<24;
774 b += ((uint32_t)k[5])<<8;
775 b += ((uint32_t)k[6])<<16;
776 b += ((uint32_t)k[7])<<24;
778 c += ((uint32_t)k[9])<<8;
779 c += ((uint32_t)k[10])<<16;
780 c += ((uint32_t)k[11])<<24;
789 case 12: c+=((uint32_t)k[11])<<24;
790 case 11: c+=((uint32_t)k[10])<<16;
791 case 10: c+=((uint32_t)k[9])<<8;
793 case 8 : b+=((uint32_t)k[7])<<24;
794 case 7 : b+=((uint32_t)k[6])<<16;
795 case 6 : b+=((uint32_t)k[5])<<8;
797 case 4 : a+=((uint32_t)k[3])<<24;
798 case 3 : a+=((uint32_t)k[2])<<16;
799 case 2 : a+=((uint32_t)k[1])<<8;
802 case 0 : *pc=c; *pb=b;
return;
818 uint32_t
hashbig(
const void *key,
size_t length, uint32_t initval)
821 union {
const void *ptr;
size_t i; } u;
824 a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
828 const uint32_t *k = (
const uint32_t *)key;
855 case 12: c+=k[2]; b+=k[1]; a+=k[0];
break;
856 case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0];
break;
857 case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0];
break;
858 case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0];
break;
859 case 8 : b+=k[1]; a+=k[0];
break;
860 case 7 : b+=k[1]&0xffffff00; a+=k[0];
break;
861 case 6 : b+=k[1]&0xffff0000; a+=k[0];
break;
862 case 5 : b+=k[1]&0xff000000; a+=k[0];
break;
863 case 4 : a+=k[0];
break;
864 case 3 : a+=k[0]&0xffffff00;
break;
865 case 2 : a+=k[0]&0xffff0000;
break;
866 case 1 : a+=k[0]&0xff000000;
break;
872 const uint8_t *k8 = (
const uint8_t *)k;
875 case 12: c+=k[2]; b+=k[1]; a+=k[0];
break;
876 case 11: c+=((uint32_t)k8[10])<<8;
877 case 10: c+=((uint32_t)k8[9])<<16;
878 case 9 : c+=((uint32_t)k8[8])<<24;
879 case 8 : b+=k[1]; a+=k[0];
break;
880 case 7 : b+=((uint32_t)k8[6])<<8;
881 case 6 : b+=((uint32_t)k8[5])<<16;
882 case 5 : b+=((uint32_t)k8[4])<<24;
883 case 4 : a+=k[0];
break;
884 case 3 : a+=((uint32_t)k8[2])<<8;
885 case 2 : a+=((uint32_t)k8[1])<<16;
886 case 1 : a+=((uint32_t)k8[0])<<24;
break;
893 const uint8_t *k = (
const uint8_t *)key;
898 a += ((uint32_t)k[0])<<24;
899 a += ((uint32_t)k[1])<<16;
900 a += ((uint32_t)k[2])<<8;
901 a += ((uint32_t)k[3]);
902 b += ((uint32_t)k[4])<<24;
903 b += ((uint32_t)k[5])<<16;
904 b += ((uint32_t)k[6])<<8;
905 b += ((uint32_t)k[7]);
906 c += ((uint32_t)k[8])<<24;
907 c += ((uint32_t)k[9])<<16;
908 c += ((uint32_t)k[10])<<8;
909 c += ((uint32_t)k[11]);
919 case 11: c+=((uint32_t)k[10])<<8;
920 case 10: c+=((uint32_t)k[9])<<16;
921 case 9 : c+=((uint32_t)k[8])<<24;
923 case 7 : b+=((uint32_t)k[6])<<8;
924 case 6 : b+=((uint32_t)k[5])<<16;
925 case 5 : b+=((uint32_t)k[4])<<24;
927 case 3 : a+=((uint32_t)k[2])<<8;
928 case 2 : a+=((uint32_t)k[1])<<16;
929 case 1 : a+=((uint32_t)k[0])<<24;
951 for (i=0; i<256; ++i) buf[i] =
'x';
957 if (z-a > 0) printf(
"time %d %.8x\n", z-a, h);
967 uint8_t qa[MAXLEN+1], qb[MAXLEN+2], *a = &qa[0], *b = &qb[1];
968 uint32_t c[HASHSTATE], d[HASHSTATE], i=0, j=0, k, l,
m=0, z;
969 uint32_t e[HASHSTATE],f[HASHSTATE],g[HASHSTATE],h[HASHSTATE];
970 uint32_t x[HASHSTATE],y[HASHSTATE];
973 printf(
"No more than %d trials should ever be needed \n",MAXPAIR/2);
974 for (hlen=0; hlen < MAXLEN; ++hlen)
977 for (i=0; i<hlen; ++i)
983 for (l=0; l<HASHSTATE; ++l)
984 e[l]=f[l]=g[l]=h[l]=x[l]=y[l]=~((uint32_t)0);
987 for (k=0; k<MAXPAIR; k+=2)
991 for (l=0; l<hlen+1; ++l) {a[l] = b[l] = (uint8_t)0;}
997 b[i] ^= ((k+1)>>(8-j));
1000 for (l=0; l<HASHSTATE; ++l)
1002 e[l] &= (c[l]^d[l]);
1003 f[l] &= ~(c[l]^d[l]);
1008 if (e[l]|f[l]|g[l]|h[l]|x[l]|y[l]) finished=0;
1010 if (finished)
break;
1015 printf(
"Some bit didn't change: ");
1016 printf(
"%.8x %.8x %.8x %.8x %.8x %.8x ",
1017 e[0],f[0],g[0],h[0],x[0],y[0]);
1018 printf(
"i %d j %d m %d len %d\n", i, j,
m, hlen);
1020 if (z==MAXPAIR)
goto done;
1027 printf(
"Mix success %2d bytes %2d initvals ",i,
m);
1028 printf(
"required %d trials\n", z/2);
1037 uint8_t buf[MAXLEN+20], *b;
1039 uint8_t q[] =
"This is the time for all good men to come to the aid of their country...";
1041 uint8_t qq[] =
"xThis is the time for all good men to come to the aid of their country...";
1043 uint8_t qqq[] =
"xxThis is the time for all good men to come to the aid of their country...";
1045 uint8_t qqqq[] =
"xxxThis is the time for all good men to come to the aid of their country...";
1049 printf(
"Endianness. These lines should all be the same (for values filled in):\n");
1050 printf(
"%.8x %.8x %.8x\n",
1051 hashword((
const uint32_t *)q, (
sizeof(q)-1)/4, 13),
1052 hashword((
const uint32_t *)q, (
sizeof(q)-5)/4, 13),
1053 hashword((
const uint32_t *)q, (
sizeof(q)-9)/4, 13));
1055 printf(
"%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
1063 printf(
"%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
1071 printf(
"%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
1079 printf(
"%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
1092 printf(
"hashlittle2 and hashlittle mismatch\n");
1099 printf(
"hashword2 and hashword mismatch %x %x\n",
1103 for (h=0, b=buf+1; h<8; ++h, ++b)
1105 for (i=0; i<MAXLEN; ++i)
1108 for (j=0; j<i; ++j) *(b+j)=0;
1116 if ((ref != x) || (ref != y))
1118 printf(
"alignment error: %.8x %.8x %.8x %d %d\n",ref,x,y,
1129 uint32_t h,i,state[HASHSTATE];
1133 for (i=0; i<HASHSTATE; ++i) state[i] = 1;
1134 printf(
"These should all be different\n");
1135 for (i=0, h=0; i<8; ++i)
1138 printf(
"%2ld 0-byte strings, hash is %.8x\n", i, h);
1146 printf(
"hash is %.8lx %.8lx\n", c, b);
1148 printf(
"hash is %.8lx %.8lx\n", c, b);
1149 b=0xdeadbeef, c=0xdeadbeef,
hashlittle2(
"", 0, &c, &b);
1150 printf(
"hash is %.8lx %.8lx\n", c, b);
1151 b=0, c=0,
hashlittle2(
"Four score and seven years ago", 30, &c, &b);
1152 printf(
"hash is %.8lx %.8lx\n", c, b);
1153 b=1, c=0,
hashlittle2(
"Four score and seven years ago", 30, &c, &b);
1154 printf(
"hash is %.8lx %.8lx\n", c, b);
1155 b=0, c=1,
hashlittle2(
"Four score and seven years ago", 30, &c, &b);
1156 printf(
"hash is %.8lx %.8lx\n", c, b);
1157 c =
hashlittle(
"Four score and seven years ago", 30, 0);
1158 printf(
"hash is %.8lx\n", c);
1159 c =
hashlittle(
"Four score and seven years ago", 30, 1);
1160 printf(
"hash is %.8lx\n", c);