DTS Application Library  0.2.3
Application library containing referenced objects and interfaces to common libraries
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Groups Pages
lookup3.c
Go to the documentation of this file.
1 
43 /*#define SELF_TEST 1*/
44 
45 #include <stdio.h> /* defines printf for tests */
46 #include <time.h> /* defines time_t for timings in the test */
47 #include <stdint.h> /* defines uint32_t etc */
48 #include <sys/param.h> /* attempt to define endianness */
49 #ifdef linux
50 # include <endian.h> /* attempt to define endianness */
51 #endif
52 
53 /*
54  * My best guess at if you are big-endian or little-endian. This may
55  * need adjustment.
56  */
57 #if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \
58  __BYTE_ORDER == __LITTLE_ENDIAN) || \
59  (defined(i386) || defined(__i386__) || defined(__i486__) || \
60  defined(__i586__) || defined(__i686__) || defined(vax) || defined(MIPSEL))
61 # define HASH_LITTLE_ENDIAN 1
62 # define HASH_BIG_ENDIAN 0
63 #elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \
64  __BYTE_ORDER == __BIG_ENDIAN) || \
65  (defined(sparc) || defined(POWERPC) || defined(mc68000) || defined(sel))
66 # define HASH_LITTLE_ENDIAN 0
67 # define HASH_BIG_ENDIAN 1
68 #else
69 # define HASH_LITTLE_ENDIAN 0
70 # define HASH_BIG_ENDIAN 0
71 #endif
72 
73 #define hashsize(n) ((uint32_t)1<<(n))
74 #define hashmask(n) (hashsize(n)-1)
75 #define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
76 
77 
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 
158 #define final(a,b,c) \
159 { \
160  c ^= b; c -= rot(b,14); \
161  a ^= c; a -= rot(c,11); \
162  b ^= a; b -= rot(a,25); \
163  c ^= b; c -= rot(b,16); \
164  a ^= c; a -= rot(c,4); \
165  b ^= a; b -= rot(a,14); \
166  c ^= b; c -= rot(b,24); \
167 }
168 
182 uint32_t hashword(
183  const uint32_t *k, /* the key, an array of uint32_t values */
184  size_t length, /* the length of the key, in uint32_ts */
185  uint32_t initval) { /* the previous hash, or an arbitrary value */
186  uint32_t a,b,c;
187 
188  /* Set up the internal state */
189  a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval;
190 
191  /*------------------------------------------------- handle most of the key */
192  while (length > 3) {
193  a += k[0];
194  b += k[1];
195  c += k[2];
196  mix(a,b,c);
197  length -= 3;
198  k += 3;
199  }
200 
201  /*------------------------------------------- handle the last 3 uint32_t's */
202  switch(length) { /* all the case statements fall through */
203  case 3 :
204  c+=k[2];
205  /* no break */
206  case 2 :
207  b+=k[1];
208  /* no break */
209  case 1 :
210  a+=k[0];
211  final(a,b,c);
212  /* no break */
213  case 0: /* case 0: nothing left to add */
214  break;
215  }
216  /*------------------------------------------------------ report the result */
217  return (c);
218 }
219 
220 
229 void hashword2 (
230  const uint32_t *k, /* the key, an array of uint32_t values */
231  size_t length, /* the length of the key, in uint32_ts */
232  uint32_t *pc, /* IN: seed OUT: primary hash value */
233  uint32_t *pb) { /* IN: more seed OUT: secondary hash value */
234  uint32_t a,b,c;
235 
236  /* Set up the internal state */
237  a = b = c = 0xdeadbeef + ((uint32_t)(length<<2)) + *pc;
238  c += *pb;
239 
240  /*------------------------------------------------- handle most of the key */
241  while (length > 3) {
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  case 3 :
253  c+=k[2];
254  /* no break */
255  case 2 :
256  b+=k[1];
257  /* no break */
258  case 1 :
259  a+=k[0];
260  final(a,b,c);
261  /* no break */
262  case 0: /* case 0: nothing left to add */
263  break;
264  }
265  /*------------------------------------------------------ report the result */
266  *pc=c;
267  *pb=b;
268 }
269 
270 
298 uint32_t hashlittle( const void *key, size_t length, uint32_t initval) {
299  uint32_t a,b,c; /* internal state */
300  union {
301  const void *ptr;
302  size_t i;
303  } u; /* needed for Mac Powerbook G4 */
304 
305  /* Set up the internal state */
306  a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
307 
308  u.ptr = key;
309  if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
310  const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
311 #ifdef VALGRIND
312  const uint8_t *k8;
313 #endif
314  /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
315  while (length > 12) {
316  a += k[0];
317  b += k[1];
318  c += k[2];
319  mix(a,b,c);
320  length -= 12;
321  k += 3;
322  }
323 
324  /*----------------------------- handle the last (probably partial) block */
325  /*
326  * "k[2]&0xffffff" actually reads beyond the end of the string, but
327  * then masks off the part it's not allowed to read. Because the
328  * string is aligned, the masked-off tail is in the same word as the
329  * rest of the string. Every machine with memory protection I've seen
330  * does it on word boundaries, so is OK with this. But VALGRIND will
331  * still catch it and complain. The masking trick does make the hash
332  * noticably faster for short strings (like English words).
333  */
334 #ifndef VALGRIND
335 
336  switch(length) {
337  case 12:
338  c+=k[2];
339  b+=k[1];
340  a+=k[0];
341  break;
342  case 11:
343  c+=k[2]&0xffffff;
344  b+=k[1];
345  a+=k[0];
346  break;
347  case 10:
348  c+=k[2]&0xffff;
349  b+=k[1];
350  a+=k[0];
351  break;
352  case 9 :
353  c+=k[2]&0xff;
354  b+=k[1];
355  a+=k[0];
356  break;
357  case 8 :
358  b+=k[1];
359  a+=k[0];
360  break;
361  case 7 :
362  b+=k[1]&0xffffff;
363  a+=k[0];
364  break;
365  case 6 :
366  b+=k[1]&0xffff;
367  a+=k[0];
368  break;
369  case 5 :
370  b+=k[1]&0xff;
371  a+=k[0];
372  break;
373  case 4 :
374  a+=k[0];
375  break;
376  case 3 :
377  a+=k[0]&0xffffff;
378  break;
379  case 2 :
380  a+=k[0]&0xffff;
381  break;
382  case 1 :
383  a+=k[0]&0xff;
384  break;
385  case 0 :
386  return (c); /* zero length strings require no mixing */
387  }
388 
389 #else /* make valgrind happy */
390 
391  k8 = (const uint8_t *)k;
392  switch(length) {
393  case 12:
394  c+=k[2];
395  b+=k[1];
396  a+=k[0];
397  break;
398  case 11:
399  c+=((uint32_t)k8[10])<<16; /* fall through */
400  case 10:
401  c+=((uint32_t)k8[9])<<8; /* fall through */
402  case 9 :
403  c+=k8[8]; /* fall through */
404  case 8 :
405  b+=k[1];
406  a+=k[0];
407  break;
408  case 7 :
409  b+=((uint32_t)k8[6])<<16; /* fall through */
410  case 6 :
411  b+=((uint32_t)k8[5])<<8; /* fall through */
412  case 5 :
413  b+=k8[4]; /* fall through */
414  case 4 :
415  a+=k[0];
416  break;
417  case 3 :
418  a+=((uint32_t)k8[2])<<16; /* fall through */
419  case 2 :
420  a+=((uint32_t)k8[1])<<8; /* fall through */
421  case 1 :
422  a+=k8[0];
423  break;
424  case 0 :
425  return c;
426  }
427 
428 #endif /* !valgrind */
429 
430  } else
431  if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
432  const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */
433  const uint8_t *k8;
434 
435  /*--------------- all but last block: aligned reads and different mixing */
436  while (length > 12) {
437  a += k[0] + (((uint32_t)k[1])<<16);
438  b += k[2] + (((uint32_t)k[3])<<16);
439  c += k[4] + (((uint32_t)k[5])<<16);
440  mix(a,b,c);
441  length -= 12;
442  k += 6;
443  }
444 
445  /*----------------------------- handle the last (probably partial) block */
446  k8 = (const uint8_t *)k;
447  switch(length) {
448  case 12:
449  c+=k[4]+(((uint32_t)k[5])<<16);
450  b+=k[2]+(((uint32_t)k[3])<<16);
451  a+=k[0]+(((uint32_t)k[1])<<16);
452  break;
453  case 11:
454  c+=((uint32_t)k8[10])<<16; /* fall through */
455  /* no break */
456  case 10:
457  c+=k[4];
458  b+=k[2]+(((uint32_t)k[3])<<16);
459  a+=k[0]+(((uint32_t)k[1])<<16);
460  break;
461  case 9 :
462  c+=k8[8]; /* fall through */
463  /* no break */
464  case 8 :
465  b+=k[2]+(((uint32_t)k[3])<<16);
466  a+=k[0]+(((uint32_t)k[1])<<16);
467  break;
468  case 7 :
469  b+=((uint32_t)k8[6])<<16; /* fall through */
470  /* no break */
471  case 6 :
472  b+=k[2];
473  a+=k[0]+(((uint32_t)k[1])<<16);
474  break;
475  case 5 :
476  b+=k8[4]; /* fall through */
477  /* no break */
478  case 4 :
479  a+=k[0]+(((uint32_t)k[1])<<16);
480  break;
481  case 3 :
482  a+=((uint32_t)k8[2])<<16; /* fall through */
483  /* no break */
484  case 2 :
485  a+=k[0];
486  break;
487  case 1 :
488  a+=k8[0];
489  break;
490  case 0 :
491  return (c); /* zero length requires no mixing */
492  }
493 
494  } else { /* need to read the key one byte at a time */
495  const uint8_t *k = (const uint8_t *)key;
496 
497  /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
498  while (length > 12) {
499  a += k[0];
500  a += ((uint32_t)k[1])<<8;
501  a += ((uint32_t)k[2])<<16;
502  a += ((uint32_t)k[3])<<24;
503  b += k[4];
504  b += ((uint32_t)k[5])<<8;
505  b += ((uint32_t)k[6])<<16;
506  b += ((uint32_t)k[7])<<24;
507  c += k[8];
508  c += ((uint32_t)k[9])<<8;
509  c += ((uint32_t)k[10])<<16;
510  c += ((uint32_t)k[11])<<24;
511  mix(a,b,c);
512  length -= 12;
513  k += 12;
514  }
515 
516  /*-------------------------------- last block: affect all 32 bits of (c) */
517  switch(length) { /* all the case statements fall through */
518  case 12:
519  c+=((uint32_t)k[11])<<24;
520  /* no break */
521  case 11:
522  c+=((uint32_t)k[10])<<16;
523  /* no break */
524  case 10:
525  c+=((uint32_t)k[9])<<8;
526  /* no break */
527  case 9 :
528  c+=k[8];
529  /* no break */
530  case 8 :
531  b+=((uint32_t)k[7])<<24;
532  /* no break */
533  case 7 :
534  b+=((uint32_t)k[6])<<16;
535  /* no break */
536  case 6 :
537  b+=((uint32_t)k[5])<<8;
538  /* no break */
539  case 5 :
540  b+=k[4];
541  /* no break */
542  case 4 :
543  a+=((uint32_t)k[3])<<24;
544  /* no break */
545  case 3 :
546  a+=((uint32_t)k[2])<<16;
547  /* no break */
548  case 2 :
549  a+=((uint32_t)k[1])<<8;
550  /* no break */
551  case 1 :
552  a+=k[0];
553  break;
554  case 0 :
555  return (c);
556  }
557  }
558 
559  final(a,b,c);
560  return (c);
561 }
562 
563 
574 void hashlittle2(
575  const void *key, /* the key to hash */
576  size_t length, /* length of the key */
577  uint32_t *pc, /* IN: primary initval, OUT: primary hash */
578  uint32_t *pb) { /* IN: secondary initval, OUT: secondary hash */
579  uint32_t a,b,c; /* internal state */
580  union {
581  const void *ptr;
582  size_t i;
583  } u; /* needed for Mac Powerbook G4 */
584 
585  /* Set up the internal state */
586  a = b = c = 0xdeadbeef + ((uint32_t)length) + *pc;
587  c += *pb;
588 
589  u.ptr = key;
590  if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
591  const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
592 #ifdef VALGRIND
593  const uint8_t *k8;
594 #endif
595 
596  /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
597  while (length > 12) {
598  a += k[0];
599  b += k[1];
600  c += k[2];
601  mix(a,b,c);
602  length -= 12;
603  k += 3;
604  }
605 
606  /*----------------------------- handle the last (probably partial) block */
607  /*
608  * "k[2]&0xffffff" actually reads beyond the end of the string, but
609  * then masks off the part it's not allowed to read. Because the
610  * string is aligned, the masked-off tail is in the same word as the
611  * rest of the string. Every machine with memory protection I've seen
612  * does it on word boundaries, so is OK with this. But VALGRIND will
613  * still catch it and complain. The masking trick does make the hash
614  * noticably faster for short strings (like English words).
615  */
616 #ifndef VALGRIND
617 
618  switch(length) {
619  case 12:
620  c+=k[2];
621  b+=k[1];
622  a+=k[0];
623  break;
624  case 11:
625  c+=k[2]&0xffffff;
626  b+=k[1];
627  a+=k[0];
628  break;
629  case 10:
630  c+=k[2]&0xffff;
631  b+=k[1];
632  a+=k[0];
633  break;
634  case 9 :
635  c+=k[2]&0xff;
636  b+=k[1];
637  a+=k[0];
638  break;
639  case 8 :
640  b+=k[1];
641  a+=k[0];
642  break;
643  case 7 :
644  b+=k[1]&0xffffff;
645  a+=k[0];
646  break;
647  case 6 :
648  b+=k[1]&0xffff;
649  a+=k[0];
650  break;
651  case 5 :
652  b+=k[1]&0xff;
653  a+=k[0];
654  break;
655  case 4 :
656  a+=k[0];
657  break;
658  case 3 :
659  a+=k[0]&0xffffff;
660  break;
661  case 2 :
662  a+=k[0]&0xffff;
663  break;
664  case 1 :
665  a+=k[0]&0xff;
666  break;
667  case 0 :
668  *pc=c;
669  *pb=b;
670  return; /* zero length strings require no mixing */
671  }
672 
673 #else /* make valgrind happy */
674 
675  k8 = (const uint8_t *)k;
676  switch(length) {
677  case 12:
678  c+=k[2];
679  b+=k[1];
680  a+=k[0];
681  break;
682  case 11:
683  c+=((uint32_t)k8[10])<<16; /* fall through */
684  case 10:
685  c+=((uint32_t)k8[9])<<8; /* fall through */
686  case 9 :
687  c+=k8[8]; /* fall through */
688  case 8 :
689  b+=k[1];
690  a+=k[0];
691  break;
692  case 7 :
693  b+=((uint32_t)k8[6])<<16; /* fall through */
694  case 6 :
695  b+=((uint32_t)k8[5])<<8; /* fall through */
696  case 5 :
697  b+=k8[4]; /* fall through */
698  case 4 :
699  a+=k[0];
700  break;
701  case 3 :
702  a+=((uint32_t)k8[2])<<16; /* fall through */
703  case 2 :
704  a+=((uint32_t)k8[1])<<8; /* fall through */
705  case 1 :
706  a+=k8[0];
707  break;
708  case 0 :
709  *pc=c;
710  *pb=b;
711  return; /* zero length strings require no mixing */
712  }
713 
714 #endif /* !valgrind */
715 
716  } else
717  if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) {
718  const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */
719  const uint8_t *k8;
720 
721  /*--------------- all but last block: aligned reads and different mixing */
722  while (length > 12) {
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);
726  mix(a,b,c);
727  length -= 12;
728  k += 6;
729  }
730 
731  /*----------------------------- handle the last (probably partial) block */
732  k8 = (const uint8_t *)k;
733  switch(length) {
734  case 12:
735  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);
738  break;
739  case 11:
740  c+=((uint32_t)k8[10])<<16; /* fall through */
741  /* no break */
742  case 10:
743  c+=k[4];
744  b+=k[2]+(((uint32_t)k[3])<<16);
745  a+=k[0]+(((uint32_t)k[1])<<16);
746  break;
747  case 9 :
748  c+=k8[8]; /* fall through */
749  /* no break */
750  case 8 :
751  b+=k[2]+(((uint32_t)k[3])<<16);
752  a+=k[0]+(((uint32_t)k[1])<<16);
753  break;
754  case 7 :
755  b+=((uint32_t)k8[6])<<16; /* fall through */
756  /* no break */
757  case 6 :
758  b+=k[2];
759  a+=k[0]+(((uint32_t)k[1])<<16);
760  break;
761  case 5 :
762  b+=k8[4]; /* fall through */
763  /* no break */
764  case 4 :
765  a+=k[0]+(((uint32_t)k[1])<<16);
766  break;
767  case 3 :
768  a+=((uint32_t)k8[2])<<16; /* fall through */
769  /* no break */
770  case 2 :
771  a+=k[0];
772  break;
773  case 1 :
774  a+=k8[0];
775  break;
776  case 0 :
777  *pc=c;
778  *pb=b;
779  return; /* zero length strings require no mixing */
780  }
781 
782  } else { /* need to read the key one byte at a time */
783  const uint8_t *k = (const uint8_t *)key;
784 
785  /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
786  while (length > 12) {
787  a += k[0];
788  a += ((uint32_t)k[1])<<8;
789  a += ((uint32_t)k[2])<<16;
790  a += ((uint32_t)k[3])<<24;
791  b += k[4];
792  b += ((uint32_t)k[5])<<8;
793  b += ((uint32_t)k[6])<<16;
794  b += ((uint32_t)k[7])<<24;
795  c += k[8];
796  c += ((uint32_t)k[9])<<8;
797  c += ((uint32_t)k[10])<<16;
798  c += ((uint32_t)k[11])<<24;
799  mix(a,b,c);
800  length -= 12;
801  k += 12;
802  }
803 
804  /*-------------------------------- last block: affect all 32 bits of (c) */
805  switch(length) { /* all the case statements fall through */
806  case 12:
807  c+=((uint32_t)k[11])<<24;
808  /* no break */
809  case 11:
810  c+=((uint32_t)k[10])<<16;
811  /* no break */
812  case 10:
813  c+=((uint32_t)k[9])<<8;
814  /* no break */
815  case 9 :
816  c+=k[8];
817  /* no break */
818  case 8 :
819  b+=((uint32_t)k[7])<<24;
820  /* no break */
821  case 7 :
822  b+=((uint32_t)k[6])<<16;
823  /* no break */
824  case 6 :
825  b+=((uint32_t)k[5])<<8;
826  /* no break */
827  case 5 :
828  b+=k[4];
829  /* no break */
830  case 4 :
831  a+=((uint32_t)k[3])<<24;
832  /* no break */
833  case 3 :
834  a+=((uint32_t)k[2])<<16;
835  /* no break */
836  case 2 :
837  a+=((uint32_t)k[1])<<8;
838  /* no break */
839  case 1 :
840  a+=k[0];
841  break;
842  case 0 :
843  *pc=c;
844  *pb=b;
845  return; /* zero length strings require no mixing */
846  }
847  }
848 
849  final(a,b,c);
850  *pc=c;
851  *pb=b;
852 }
853 
854 
855 
862 uint32_t hashbig( const void *key, size_t length, uint32_t initval) {
863  uint32_t a,b,c;
864  union {
865  const void *ptr;
866  size_t i;
867  } u; /* to cast key to (size_t) happily */
868 
869  /* Set up the internal state */
870  a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
871 
872  u.ptr = key;
873  if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) {
874  const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
875 #ifdef VALGRIND
876  const uint8_t *k8;
877 #endif
878  /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
879  while (length > 12) {
880  a += k[0];
881  b += k[1];
882  c += k[2];
883  mix(a,b,c);
884  length -= 12;
885  k += 3;
886  }
887 
888  /*----------------------------- handle the last (probably partial) block */
889  /*
890  * "k[2]<<8" actually reads beyond the end of the string, but
891  * then shifts out the part it's not allowed to read. Because the
892  * string is aligned, the illegal read is in the same word as the
893  * rest of the string. Every machine with memory protection I've seen
894  * does it on word boundaries, so is OK with this. But VALGRIND will
895  * still catch it and complain. The masking trick does make the hash
896  * noticably faster for short strings (like English words).
897  */
898 #ifndef VALGRIND
899 
900  switch(length) {
901  case 12:
902  c+=k[2];
903  b+=k[1];
904  a+=k[0];
905  break;
906  case 11:
907  c+=k[2]&0xffffff00;
908  b+=k[1];
909  a+=k[0];
910  break;
911  case 10:
912  c+=k[2]&0xffff0000;
913  b+=k[1];
914  a+=k[0];
915  break;
916  case 9 :
917  c+=k[2]&0xff000000;
918  b+=k[1];
919  a+=k[0];
920  break;
921  case 8 :
922  b+=k[1];
923  a+=k[0];
924  break;
925  case 7 :
926  b+=k[1]&0xffffff00;
927  a+=k[0];
928  break;
929  case 6 :
930  b+=k[1]&0xffff0000;
931  a+=k[0];
932  break;
933  case 5 :
934  b+=k[1]&0xff000000;
935  a+=k[0];
936  break;
937  case 4 :
938  a+=k[0];
939  break;
940  case 3 :
941  a+=k[0]&0xffffff00;
942  break;
943  case 2 :
944  a+=k[0]&0xffff0000;
945  break;
946  case 1 :
947  a+=k[0]&0xff000000;
948  break;
949  case 0 :
950  return (c); /* zero length strings require no mixing */
951  }
952 
953 #else /* make valgrind happy */
954 
955  k8 = (const uint8_t *)k;
956  switch(length) { /* all the case statements fall through */
957  case 12:
958  c+=k[2];
959  b+=k[1];
960  a+=k[0];
961  break;
962  case 11:
963  c+=((uint32_t)k8[10])<<8; /* fall through */
964  case 10:
965  c+=((uint32_t)k8[9])<<16; /* fall through */
966  case 9 :
967  c+=((uint32_t)k8[8])<<24; /* fall through */
968  case 8 :
969  b+=k[1];
970  a+=k[0];
971  break;
972  case 7 :
973  b+=((uint32_t)k8[6])<<8; /* fall through */
974  case 6 :
975  b+=((uint32_t)k8[5])<<16; /* fall through */
976  case 5 :
977  b+=((uint32_t)k8[4])<<24; /* fall through */
978  case 4 :
979  a+=k[0];
980  break;
981  case 3 :
982  a+=((uint32_t)k8[2])<<8; /* fall through */
983  case 2 :
984  a+=((uint32_t)k8[1])<<16; /* fall through */
985  case 1 :
986  a+=((uint32_t)k8[0])<<24;
987  break;
988  case 0 :
989  return c;
990  }
991 
992 #endif /* !VALGRIND */
993 
994  } else { /* need to read the key one byte at a time */
995  const uint8_t *k = (const uint8_t *)key;
996 
997  /*--------------- all but the last block: affect some 32 bits of (a,b,c) */
998  while (length > 12) {
999  a += ((uint32_t)k[0])<<24;
1000  a += ((uint32_t)k[1])<<16;
1001  a += ((uint32_t)k[2])<<8;
1002  a += ((uint32_t)k[3]);
1003  b += ((uint32_t)k[4])<<24;
1004  b += ((uint32_t)k[5])<<16;
1005  b += ((uint32_t)k[6])<<8;
1006  b += ((uint32_t)k[7]);
1007  c += ((uint32_t)k[8])<<24;
1008  c += ((uint32_t)k[9])<<16;
1009  c += ((uint32_t)k[10])<<8;
1010  c += ((uint32_t)k[11]);
1011  mix(a,b,c);
1012  length -= 12;
1013  k += 12;
1014  }
1015 
1016  /*-------------------------------- last block: affect all 32 bits of (c) */
1017  switch(length) { /* all the case statements fall through */
1018  case 12:
1019  c+=k[11];
1020  /* no break */
1021  case 11:
1022  c+=((uint32_t)k[10])<<8;
1023  /* no break */
1024  case 10:
1025  c+=((uint32_t)k[9])<<16;
1026  /* no break */
1027  case 9 :
1028  c+=((uint32_t)k[8])<<24;
1029  /* no break */
1030  case 8 :
1031  b+=k[7];
1032  /* no break */
1033  case 7 :
1034  b+=((uint32_t)k[6])<<8;
1035  /* no break */
1036  case 6 :
1037  b+=((uint32_t)k[5])<<16;
1038  /* no break */
1039  case 5 :
1040  b+=((uint32_t)k[4])<<24;
1041  /* no break */
1042  case 4 :
1043  a+=k[3];
1044  /* no break */
1045  case 3 :
1046  a+=((uint32_t)k[2])<<8;
1047  /* no break */
1048  case 2 :
1049  a+=((uint32_t)k[1])<<16;
1050  /* no break */
1051  case 1 :
1052  a+=((uint32_t)k[0])<<24;
1053  break;
1054  case 0 :
1055  return (c);
1056  }
1057  }
1058 
1059  final(a,b,c);
1060  return (c);
1061 }
1062 
1065 #ifdef SELF_TEST
1066 
1067 /* used for timings */
1068 static void driver1() {
1069  uint8_t buf[256];
1070  uint32_t i;
1071  uint32_t h=0;
1072  time_t a,z;
1073 
1074  time(&a);
1075  for (i=0; i<256; ++i) {
1076  buf[i] = 'x';
1077  }
1078  for (i=0; i<1; ++i) {
1079  h = hashlittle(&buf[0],1,h);
1080  }
1081  time(&z);
1082  if (z-a > 0) {
1083  printf("time %d %.8x\n", z-a, h);
1084  }
1085 }
1086 
1087 /* check that every input bit changes every output bit half the time */
1088 #define HASHSTATE 1
1089 #define HASHLEN 1
1090 #define MAXPAIR 60
1091 #define MAXLEN 70
1092 static void driver2() {
1093  uint8_t qa[MAXLEN+1], qb[MAXLEN+2], *a = &qa[0], *b = &qb[1];
1094  uint32_t c[HASHSTATE], d[HASHSTATE], i=0, j=0, k, l, m=0, z;
1095  uint32_t e[HASHSTATE],f[HASHSTATE],g[HASHSTATE],h[HASHSTATE];
1096  uint32_t x[HASHSTATE],y[HASHSTATE];
1097  uint32_t hlen;
1098 
1099  printf("No more than %d trials should ever be needed \n",MAXPAIR/2);
1100  for (hlen=0; hlen < MAXLEN; ++hlen) {
1101  z=0;
1102  for (i=0; i<hlen; ++i) { /*----------------------- for each input byte, */
1103  for (j=0; j<8; ++j) { /*------------------------ for each input bit, */
1104  for (m=1; m<8; ++m) { /*------------ for serveral possible initvals, */
1105  for (l=0; l<HASHSTATE; ++l) {
1106  e[l]=f[l]=g[l]=h[l]=x[l]=y[l]=~((uint32_t)0);
1107  }
1108 
1109  /*---- check that every output bit is affected by that input bit */
1110  for (k=0; k<MAXPAIR; k+=2) {
1111  uint32_t finished=1;
1112  /* keys have one bit different */
1113  for (l=0; l<hlen+1; ++l) {
1114  a[l] = b[l] = (uint8_t)0;
1115  }
1116  /* have a and b be two keys differing in only one bit */
1117  a[i] ^= (k<<j);
1118  a[i] ^= (k>>(8-j));
1119  c[0] = hashlittle(a, hlen, m);
1120  b[i] ^= ((k+1)<<j);
1121  b[i] ^= ((k+1)>>(8-j));
1122  d[0] = hashlittle(b, hlen, m);
1123  /* check every bit is 1, 0, set, and not set at least once */
1124  for (l=0; l<HASHSTATE; ++l) {
1125  e[l] &= (c[l]^d[l]);
1126  f[l] &= ~(c[l]^d[l]);
1127  g[l] &= c[l];
1128  h[l] &= ~c[l];
1129  x[l] &= d[l];
1130  y[l] &= ~d[l];
1131  if (e[l]|f[l]|g[l]|h[l]|x[l]|y[l]) {
1132  finished=0;
1133  }
1134  }
1135  if (finished) {
1136  break;
1137  }
1138  }
1139  if (k>z) {
1140  z=k;
1141  }
1142  if (k==MAXPAIR) {
1143  printf("Some bit didn't change: ");
1144  printf("%.8x %.8x %.8x %.8x %.8x %.8x ",
1145  e[0],f[0],g[0],h[0],x[0],y[0]);
1146  printf("i %d j %d m %d len %d\n", i, j, m, hlen);
1147  }
1148  if (z==MAXPAIR) {
1149  goto done;
1150  }
1151  }
1152  }
1153  }
1154 done:
1155  if (z < MAXPAIR) {
1156  printf("Mix success %2d bytes %2d initvals ",i,m);
1157  printf("required %d trials\n", z/2);
1158  }
1159  }
1160  printf("\n");
1161 }
1162 
1163 /* Check for reading beyond the end of the buffer and alignment problems */
1164 static void driver3() {
1165  uint8_t buf[MAXLEN+20], *b;
1166  uint32_t len;
1167  uint8_t q[] = "This is the time for all good men to come to the aid of their country...";
1168  uint32_t h;
1169  uint8_t qq[] = "xThis is the time for all good men to come to the aid of their country...";
1170  uint32_t i;
1171  uint8_t qqq[] = "xxThis is the time for all good men to come to the aid of their country...";
1172  uint32_t j;
1173  uint8_t qqqq[] = "xxxThis is the time for all good men to come to the aid of their country...";
1174  uint32_t ref,x,y;
1175  uint8_t *p;
1176 
1177  printf("Endianness. These lines should all be the same (for values filled in):\n");
1178  printf("%.8x %.8x %.8x\n",
1179  hashword((const uint32_t *)q, (sizeof(q)-1)/4, 13),
1180  hashword((const uint32_t *)q, (sizeof(q)-5)/4, 13),
1181  hashword((const uint32_t *)q, (sizeof(q)-9)/4, 13));
1182  p = q;
1183  printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
1184  hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
1185  hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
1186  hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
1187  hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
1188  hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
1189  hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
1190  p = &qq[1];
1191  printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
1192  hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
1193  hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
1194  hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
1195  hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
1196  hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
1197  hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
1198  p = &qqq[2];
1199  printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
1200  hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
1201  hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
1202  hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
1203  hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
1204  hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
1205  hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
1206  p = &qqqq[3];
1207  printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n",
1208  hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13),
1209  hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13),
1210  hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13),
1211  hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13),
1212  hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13),
1213  hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13));
1214  printf("\n");
1215 
1216  /* check that hashlittle2 and hashlittle produce the same results */
1217  i=47;
1218  j=0;
1219  hashlittle2(q, sizeof(q), &i, &j);
1220  if (hashlittle(q, sizeof(q), 47) != i) {
1221  printf("hashlittle2 and hashlittle mismatch\n");
1222  }
1223 
1224  /* check that hashword2 and hashword produce the same results */
1225  len = 0xdeadbeef;
1226  i=47, j=0;
1227  hashword2(&len, 1, &i, &j);
1228  if (hashword(&len, 1, 47) != i)
1229  printf("hashword2 and hashword mismatch %x %x\n",
1230  i, hashword(&len, 1, 47));
1231 
1232  /* check hashlittle doesn't read before or after the ends of the string */
1233  for (h=0, b=buf+1; h<8; ++h, ++b) {
1234  for (i=0; i<MAXLEN; ++i) {
1235  len = i;
1236  for (j=0; j<i; ++j) {
1237  *(b+j)=0;
1238  }
1239 
1240  /* these should all be equal */
1241  ref = hashlittle(b, len, (uint32_t)1);
1242  *(b+i)=(uint8_t)~0;
1243  *(b-1)=(uint8_t)~0;
1244  x = hashlittle(b, len, (uint32_t)1);
1245  y = hashlittle(b, len, (uint32_t)1);
1246  if ((ref != x) || (ref != y)) {
1247  printf("alignment error: %.8x %.8x %.8x %d %d\n",ref,x,y,
1248  h, i);
1249  }
1250  }
1251  }
1252 }
1253 
1254 /* check for problems with nulls */
1255 static void driver4() {
1256  uint8_t buf[1];
1257  uint32_t h,i,state[HASHSTATE];
1258 
1259 
1260  buf[0] = ~0;
1261  for (i=0; i<HASHSTATE; ++i) {
1262  state[i] = 1;
1263  }
1264  printf("These should all be different\n");
1265  for (i=0, h=0; i<8; ++i) {
1266  h = hashlittle(buf, 0, h);
1267  printf("%2ld 0-byte strings, hash is %.8x\n", i, h);
1268  }
1269 }
1270 
1271 static void driver5() {
1272  uint32_t b,c;
1273  b=0, c=0, hashlittle2("", 0, &c, &b);
1274  printf("hash is %.8lx %.8lx\n", c, b); /* deadbeef deadbeef */
1275  b=0xdeadbeef, c=0, hashlittle2("", 0, &c, &b);
1276  printf("hash is %.8lx %.8lx\n", c, b); /* bd5b7dde deadbeef */
1277  b=0xdeadbeef, c=0xdeadbeef, hashlittle2("", 0, &c, &b);
1278  printf("hash is %.8lx %.8lx\n", c, b); /* 9c093ccd bd5b7dde */
1279  b=0, c=0, hashlittle2("Four score and seven years ago", 30, &c, &b);
1280  printf("hash is %.8lx %.8lx\n", c, b); /* 17770551 ce7226e6 */
1281  b=1, c=0, hashlittle2("Four score and seven years ago", 30, &c, &b);
1282  printf("hash is %.8lx %.8lx\n", c, b); /* e3607cae bd371de4 */
1283  b=0, c=1, hashlittle2("Four score and seven years ago", 30, &c, &b);
1284  printf("hash is %.8lx %.8lx\n", c, b); /* cd628161 6cbea4b3 */
1285  c = hashlittle("Four score and seven years ago", 30, 0);
1286  printf("hash is %.8lx\n", c); /* 17770551 */
1287  c = hashlittle("Four score and seven years ago", 30, 1);
1288  printf("hash is %.8lx\n", c); /* cd628161 */
1289 }
1290 
1291 
1292 static int main() {
1293  driver1(); /* test that the key is hashed: used for timings */
1294  driver2(); /* test that whole key is hashed thoroughly */
1295  driver3(); /* test that nothing but the key is hashed */
1296  driver4(); /* test hashing multiple buffers (all buffers are null) */
1297  driver5(); /* test the hash against known vectors */
1298  return 1;
1299 }
1300 
1301 #endif /* SELF_TEST */
HASH_LITTLE_ENDIAN
#define HASH_LITTLE_ENDIAN
Definition: lookup3.c:69
hashlittle
uint32_t hashlittle(const void *key, size_t length, uint32_t initval)
hash a variable-length key into a 32-bit value (Little Endian)
Definition: lookup3.c:298
hashword2
void hashword2(const uint32_t *k, size_t length, uint32_t *pc, uint32_t *pb)
same as hashword(), but take two seeds and return two 32-bit values
Definition: lookup3.c:229
hashbig
uint32_t hashbig(const void *key, size_t length, uint32_t initval)
This is the same as hashword() on big-endian machines.
Definition: lookup3.c:862
hashlittle2
void hashlittle2(const void *key, size_t length, uint32_t *pc, uint32_t *pb)
return 2 32-bit hash values.
Definition: lookup3.c:574
hashword
uint32_t hashword(const uint32_t *k, size_t length, uint32_t initval)
hash a variable-length key into a 32-bit value (Big Endian)
Definition: lookup3.c:182
HASH_BIG_ENDIAN
#define HASH_BIG_ENDIAN
Definition: lookup3.c:70
mix
#define mix(a, b, c)
mix 3 32-bit values reversibly
Definition: lookup3.c:122