lookup3.c revision 1b4bb4fdac4dce4e658aa3743153d77c04d1a331
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poettering/* Slightly modified by Lennart Poettering, to avoid name clashes, and
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poettering * unexport a few functions. */
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poettering-------------------------------------------------------------------------------
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poetteringlookup3.c, by Bob Jenkins, May 2006, Public Domain.
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart PoetteringThese are functions for producing 32-bit hashes for hash table lookup.
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poetteringhashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poetteringare externally useful functions. Routines to test the hash are included
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poetteringif SELF_TEST is defined. You can use this free for any purpose. It's in
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poetteringthe public domain. It has no warranty.
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart PoetteringYou probably want to use hashlittle(). hashlittle() and hashbig()
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poetteringhash byte arrays. hashlittle() is faster than hashbig() on
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poetteringlittle-endian machines. Intel and AMD are little-endian machines.
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart PoetteringOn second thought, you probably want hashlittle2(), which is identical to
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poetteringhashlittle() except it returns two 32-bit hashes for the price of one.
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart PoetteringYou could implement hashbig2() if you wanted but I haven't bothered here.
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart PoetteringIf you want to find a hash of, say, exactly 7 integers, do
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poettering a = i1; b = i2; c = i3;
1ca208fb4f93e5869704af1812cbff7130a2fc03Zbigniew Jędrzejewski-Szmek a += i4; b += i5; c += i6;
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringthen use c as the hash value. If you have a variable length array of
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering4-byte integers to hash, use hashword(). If you have a byte array (like
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringa character string), use hashlittle(). If you have several byte arrays, or
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringa mix of things, see the comments above hashlittle().
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart PoetteringWhy is this so big? I read 12 bytes at a time into 3 4-byte integers,
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringthen mix those integers. This is fast (you can do a lot more thorough
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringmixing with 12*3 instructions on 3 integers than you can with 3 instructions
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringon 1 byte), but shoehorning those bytes into integers efficiently is messy.
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering-------------------------------------------------------------------------------
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering/* #define SELF_TEST 1 */
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering#include <stdio.h> /* defines printf for tests */
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering#include <time.h> /* defines time_t for timings in the test */
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering#include <stdint.h> /* defines uint32_t etc */
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering#include <sys/param.h> /* attempt to define endianness */
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering# include <endian.h> /* attempt to define endianness */
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering * My best guess at if you are big-endian or little-endian. This may
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering * need adjustment.
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering#if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering (defined(i386) || defined(__i386__) || defined(__i486__) || \
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering defined(__i586__) || defined(__i686__) || defined(vax) || defined(MIPSEL))
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering#elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering (defined(sparc) || defined(POWERPC) || defined(mc68000) || defined(sel))
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k))))
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering-------------------------------------------------------------------------------
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringmix -- mix 3 32-bit values reversibly.
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart PoetteringThis is reversible, so any information in (a,b,c) before mix() is
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringstill in (a,b,c) after mix().
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart PoetteringIf four pairs of (a,b,c) inputs are run through mix(), or through
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringmix() in reverse, there are at least 32 bits of the output that
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringare sometimes the same for one pair and different for another pair.
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart PoetteringThis was tested for:
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering* pairs that differed by one bit, by two bits, in any combination
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering of top bits of (a,b,c), or in any combination of bottom bits of
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering is commonly produced by subtraction) look like a single 1-bit
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering* the base values were pseudorandom, all zero but one bit set, or
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering all zero plus a counter that starts at zero.
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart PoetteringSome k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringsatisfy this are
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering 9 15 3 18 27 15
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart PoetteringWell, "9 15 3 18 27 15" didn't quite get 32 bits diffing
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringfor "differ" defined as + with a one-bit base and a two-bit delta. I
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringused http://burtleburtle.net/bob/hash/avalanche.html to choose
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringthe operations, constants, and arrangements of the variables.
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart PoetteringThis does not achieve avalanche. There are input bits of (a,b,c)
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringthat fail to affect some output bits of (a,b,c), especially of a. The
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringmost thoroughly mixed value is c, but it doesn't really even achieve
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringavalanche in c.
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart PoetteringThis allows some parallelism. Read-after-writes are good at doubling
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringthe number of bits affected, so the goal of mixing pulls in the opposite
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringdirection as the goal of parallelism. I did what I could. Rotates
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringseem to cost as much as shifts on every machine I could lay my hands
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringon, and rotates are much kinder to the top and bottom bits, so I used
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering-------------------------------------------------------------------------------
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering#define mix(a,b,c) \
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering-------------------------------------------------------------------------------
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringfinal -- final mixing of 3 32-bit values (a,b,c) into c
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart PoetteringPairs of (a,b,c) values differing in only a few bits will usually
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringproduce values of c that look totally different. This was tested for
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering* pairs that differed by one bit, by two bits, in any combination
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering of top bits of (a,b,c), or in any combination of bottom bits of
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering is commonly produced by subtraction) look like a single 1-bit
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering* the base values were pseudorandom, all zero but one bit set, or
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering all zero plus a counter that starts at zero.
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart PoetteringThese constants passed:
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering 14 11 25 16 4 14 24
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering 12 14 25 16 4 14 24
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringand these came close:
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering 4 8 15 26 3 22 24
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering 10 8 15 26 3 22 24
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering 11 8 15 26 3 22 24
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering-------------------------------------------------------------------------------
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering#define final(a,b,c) \
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering--------------------------------------------------------------------
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering This works on all machines. To be useful, it requires
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering -- that the key be an array of uint32_t's, and
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering -- that the length be the number of uint32_t's in the key
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering The function hashword() is identical to hashlittle() on little-endian
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering machines, and identical to hashbig() on big-endian machines,
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering except that the length has to be measured in uint32_ts rather than in
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering bytes. hashlittle() is more complicated than hashword() only because
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering hashlittle() has to dance around fitting the key bytes into registers.
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering--------------------------------------------------------------------
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringconst uint32_t *k, /* the key, an array of uint32_t values */
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringsize_t length, /* the length of the key, in uint32_ts */
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringuint32_t initval) /* the previous hash, or an arbitrary value */
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering /* Set up the internal state */
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval;
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering /*------------------------------------------------- handle most of the key */
be3f52f4ed02a9256b1577719677b32a17b525acLennart Poettering /*------------------------------------------- handle the last 3 uint32_t's */
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poettering switch(length) /* all the case statements fall through */
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poettering case 1 : a+=k[0];
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poettering case 0: /* case 0: nothing left to add */
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poettering /*------------------------------------------------------ report the result */
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poettering--------------------------------------------------------------------
1ca208fb4f93e5869704af1812cbff7130a2fc03Zbigniew Jędrzejewski-Szmekhashword2() -- same as hashword(), but take two seeds and return two
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poettering32-bit values. pc and pb must both be nonnull, and *pc and *pb must
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poetteringboth be initialized with seeds. If you pass in (*pb)==0, the output
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poettering(*pc) will be the same as the return value from hashword().
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poettering--------------------------------------------------------------------
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poetteringconst uint32_t *k, /* the key, an array of uint32_t values */
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poetteringsize_t length, /* the length of the key, in uint32_ts */
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringuint32_t *pc, /* IN: seed OUT: primary hash value */
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringuint32_t *pb) /* IN: more seed OUT: secondary hash value */
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering /* Set up the internal state */
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering a = b = c = 0xdeadbeef + ((uint32_t)(length<<2)) + *pc;
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering /*------------------------------------------------- handle most of the key */
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering /*------------------------------------------- handle the last 3 uint32_t's */
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poettering switch(length) /* all the case statements fall through */
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering case 1 : a+=k[0];
1ca208fb4f93e5869704af1812cbff7130a2fc03Zbigniew Jędrzejewski-Szmek case 0: /* case 0: nothing left to add */
be3f52f4ed02a9256b1577719677b32a17b525acLennart Poettering /*------------------------------------------------------ report the result */
be3f52f4ed02a9256b1577719677b32a17b525acLennart Poettering-------------------------------------------------------------------------------
be3f52f4ed02a9256b1577719677b32a17b525acLennart Poetteringhashlittle() -- hash a variable-length key into a 32-bit value
be3f52f4ed02a9256b1577719677b32a17b525acLennart Poettering k : the key (the unaligned variable-length array of bytes)
be3f52f4ed02a9256b1577719677b32a17b525acLennart Poettering length : the length of the key, counting by bytes
be3f52f4ed02a9256b1577719677b32a17b525acLennart Poettering initval : can be any 4-byte value
be3f52f4ed02a9256b1577719677b32a17b525acLennart PoetteringReturns a 32-bit value. Every bit of the key affects every bit of
be3f52f4ed02a9256b1577719677b32a17b525acLennart Poetteringthe return value. Two keys differing by one or two bits will have
be3f52f4ed02a9256b1577719677b32a17b525acLennart Poetteringtotally different hash values.
be3f52f4ed02a9256b1577719677b32a17b525acLennart PoetteringThe best hash table sizes are powers of 2. There is no need to do
be3f52f4ed02a9256b1577719677b32a17b525acLennart Poetteringmod a prime (mod is sooo slow!). If you need less than 32 bits,
be3f52f4ed02a9256b1577719677b32a17b525acLennart Poetteringuse a bitmask. For example, if you need only 10 bits, do
be3f52f4ed02a9256b1577719677b32a17b525acLennart Poettering h = (h & hashmask(10));
be3f52f4ed02a9256b1577719677b32a17b525acLennart PoetteringIn which case, the hash table should have hashsize(10) elements.
be3f52f4ed02a9256b1577719677b32a17b525acLennart PoetteringIf you are hashing n strings (uint8_t **)k, do it like this:
be3f52f4ed02a9256b1577719677b32a17b525acLennart Poettering for (i=0, h=0; i<n; ++i) h = hashlittle( k[i], len[i], h);
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart PoetteringBy Bob Jenkins, 2006. bob_jenkins@burtleburtle.net. You may use this
1ca208fb4f93e5869704af1812cbff7130a2fc03Zbigniew Jędrzejewski-Szmekcode any way you wish, private, educational, or commercial. It's free.
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart PoetteringUse for hash table lookup, or anything where one collision in 2^^32 is
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poetteringacceptable. Do NOT use for cryptographic purposes.
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering-------------------------------------------------------------------------------
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poetteringuint32_t jenkins_hashlittle( const void *key, size_t length, uint32_t initval)
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering /* Set up the internal state */
74df0fca09b3c31ed19e14ba80f996fdff772417Lennart Poettering a = b = c = 0xdeadbeef + ((uint32_t)length) + initval;
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) {
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poettering /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poettering /*----------------------------- handle the last (probably partial) block */
1ca208fb4f93e5869704af1812cbff7130a2fc03Zbigniew Jędrzejewski-Szmek * "k[2]&0xffffff" actually reads beyond the end of the string, but
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poettering * then masks off the part it's not allowed to read. Because the
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poettering * string is aligned, the masked-off tail is in the same word as the
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poettering * rest of the string. Every machine with memory protection I've seen
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poettering * does it on word boundaries, so is OK with this. But VALGRIND will
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poettering * still catch it and complain. The masking trick does make the hash
0f4ba83c397e807939a4eb0b2cbd04ad4ab548ccLennart Poettering * noticeably faster for short strings (like English words).
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poettering case 12: c+=k[2]; b+=k[1]; a+=k[0]; break;
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poettering case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break;
1ca208fb4f93e5869704af1812cbff7130a2fc03Zbigniew Jędrzejewski-Szmek case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break;
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poettering case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break;
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poettering case 7 : b+=k[1]&0xffffff; a+=k[0]; break;
1ca208fb4f93e5869704af1812cbff7130a2fc03Zbigniew Jędrzejewski-Szmek case 4 : a+=k[0]; break;
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poettering case 0 : return c; /* zero length strings require no mixing */
3731acf1acfb4a6eb68374a5b137f3b368f63381Lennart Poettering#else /* make valgrind happy */
switch(length)
mix(a,b,c);
switch(length)
mix(a,b,c);
final(a,b,c);
void jenkins_hashlittle2(
c += *pb;
mix(a,b,c);
#ifndef VALGRIND
switch(length)
switch(length)
mix(a,b,c);
switch(length)
mix(a,b,c);
final(a,b,c);
uint32_t a,b,c;
mix(a,b,c);
#ifndef VALGRIND
switch(length)
mix(a,b,c);
final(a,b,c);
#ifdef SELF_TEST
void driver1()
uint32_t i;
uint32_t h=0;
time_t a,z;
time(&a);
time(&z);
void driver2()
for (l=0; l<HASHSTATE; ++l)
e[l]=f[l]=g[l]=h[l]=x[l]=y[l]=~((uint32_t)0);
for (l=0; l<HASHSTATE; ++l)
if (e[l]|f[l]|g[l]|h[l]|x[l]|y[l]) finished=0;
if (finished) break;
if (k==MAXPAIR)
done:
if (z < MAXPAIR)
void driver3()
uint32_t h;
uint32_t i;
uint32_t j;
uint8_t *p;
hashlittle2(q, sizeof(q), &i, &j);
for (i=0; i<MAXLEN; ++i)
len = i;
*(b+i)=(uint8_t)~0;
void driver4()
buf[0] = ~0;
void driver5()
uint32_t b,c;
int main()