LCOV - code coverage report
Current view: top level - journal - lookup3.c (source / functions) Hit Total Coverage
Test: systemd test coverage Lines: 62 266 23.3 %
Date: 2015-07-29 18:47:03 Functions: 1 5 20.0 %

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

Generated by: LCOV version 1.11