**diff options**

Diffstat (limited to 'apps/plugins/lib/jhash.c')

-rw-r--r-- | apps/plugins/lib/jhash.c | 32 |

1 files changed, 18 insertions, 14 deletions

diff --git a/apps/plugins/lib/jhash.c b/apps/plugins/lib/jhash.c index 780d220408..40fb861d71 100644 --- a/apps/plugins/lib/jhash.c +++ b/apps/plugins/lib/jhash.c @@ -23,8 +23,8 @@ lookup3.c, by Bob Jenkins, May 2006, Public Domain. These are functions for producing 32-bit hashes for hash table lookup. -hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final() -are externally useful functions. Routines to test the hash are included +hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final() +are externally useful functions. Routines to test the hash are included if SELF_TEST is defined. You can use this free for any purpose. It's in the public domain. It has no warranty. @@ -32,7 +32,7 @@ You probably want to use hashlittle(). hashlittle() and hashbig() hash byte arrays. hashlittle() is is faster than hashbig() on little-endian machines. Intel and AMD are little-endian machines. On second thought, you probably want hashlittle2(), which is identical to -hashlittle() except it returns two 32-bit hashes for the price of one. +hashlittle() except it returns two 32-bit hashes for the price of one. You could implement hashbig2() if you wanted but I haven't bothered here. If you want to find a hash of, say, exactly 7 integers, do @@ -45,9 +45,9 @@ final(a,b,c); then use c as the hash value. If you have a variable length array of 4-byte integers to hash, use hashword(). If you have a byte array (like a character string), use hashlittle(). If you have several byte arrays, or -a mix of things, see the comments above hashlittle(). +a mix of things, see the comments above hashlittle(). -Why is this so big? I read 12 bytes at a time into 3 4-byte integers, +Why is this so big? I read 12 bytes at a time into 3 4-byte integers, then mix those integers. This is fast (you can do a lot more thorough mixing with 12*3 instructions on 3 integers than you can with 3 instructions on 1 byte), but shoehorning those bytes into integers efficiently is messy. @@ -92,7 +92,7 @@ This was tested for: the output delta to a Gray code (a^(a>>1)) so a string of 1's (as is commonly produced by subtraction) look like a single 1-bit difference. -* the base values were pseudorandom, all zero but one bit set, or +* the base values were pseudorandom, all zero but one bit set, or all zero plus a counter that starts at zero. Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that @@ -102,7 +102,7 @@ satisfy this are 14 9 3 7 17 3 Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing for "differ" defined as + with a one-bit base and a two-bit delta. I -used http://burtleburtle.net/bob/hash/avalanche.html to choose +used http://burtleburtle.net/bob/hash/avalanche.html to choose the operations, constants, and arrangements of the variables. This does not achieve avalanche. There are input bits of (a,b,c) @@ -139,7 +139,7 @@ produce values of c that look totally different. This was tested for the output delta to a Gray code (a^(a>>1)) so a string of 1's (as is commonly produced by subtraction) look like a single 1-bit difference. -* the base values were pseudorandom, all zero but one bit set, or +* the base values were pseudorandom, all zero but one bit set, or all zero plus a counter that starts at zero. These constants passed: @@ -187,7 +187,7 @@ uint32_t hashw(const uint32_t *k, size_t length, uint32_t initval) /* handle the last 3 uint32_t's */ switch(length) /* all the case statements fall through */ - { + { case 3: c+=k[2]; case 2: @@ -206,7 +206,7 @@ uint32_t hashw(const uint32_t *k, size_t length, uint32_t initval) /* hashw2() -- same as hashw(), but take two seeds and return two 32-bit values. pc and pb must both be nonnull, and *pc and *pb must -both be initialized with seeds. If you pass in (*pb)==0, the output +both be initialized with seeds. If you pass in (*pb)==0, the output (*pc) will be the same as the return value from hashword(). k: pointer to the key, an array of uint32_t length: number of elements in the key @@ -234,7 +234,7 @@ void hashw2 (const uint32_t *k, size_t length, uint32_t *pc, uint32_t *pb) /* handle the last 3 uint32_t's */ switch(length) /* all the case statements fall through */ - { + { case 3: c+=k[2]; case 2: @@ -279,13 +279,15 @@ acceptable. Do NOT use for cryptographic purposes. uint32_t hashs( const void *key, size_t length, uint32_t initval) { uint32_t a,b,c; /* internal state */ +#if HASH_LITTLE_ENDIAN union { const void *ptr; size_t i; } u;/* needed for Mac Powerbook G4 */ +#endif /* Set up the internal state */ a = b = c = 0xdeadbeef + ((uint32_t)length) + initval; - u.ptr = key; #if HASH_LITTLE_ENDIAN + u.ptr = key; if ((u.i & 0x3) == 0) { const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ @@ -351,7 +353,7 @@ uint32_t hashs( const void *key, size_t length, uint32_t initval) case 1: a += k[0] & 0xff; break; - case 0: + case 0: return c; /* zero length strings require no mixing */ } @@ -494,14 +496,16 @@ hashs2: return 2 32-bit hash values void hashs2(const void *key, size_t length, uint32_t *pc, uint32_t *pb) { uint32_t a, b, c; /* internal state */ +#if HASH_LITTLE_ENDIAN union { const void *ptr; size_t i; } u; /* needed for Mac Powerbook G4 */ +#endif /* Set up the internal state */ a = b = c = 0xdeadbeef + ((uint32_t)length) + *pc; c += *pb; - u.ptr = key; #if HASH_LITTLE_ENDIAN + u.ptr = key; if (((u.i & 0x3) == 0)) { const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ |