From 754c677b0bbf3ea6c7d2a73c93848f1b0d68c91e Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Mon, 20 Jun 2011 16:54:15 +0930 Subject: lib: import ccan modules for tdb2 Imported from git://git.ozlabs.org/~ccan/ccan init-1161-g661d41f Signed-off-by: Rusty Russell --- lib/ccan/hash/_info | 31 ++ lib/ccan/hash/hash.c | 925 +++++++++++++++++++++++++++++++++++ lib/ccan/hash/hash.h | 312 ++++++++++++ lib/ccan/hash/test/api-hash_stable.c | 300 ++++++++++++ lib/ccan/hash/test/run.c | 149 ++++++ 5 files changed, 1717 insertions(+) create mode 100644 lib/ccan/hash/_info create mode 100644 lib/ccan/hash/hash.c create mode 100644 lib/ccan/hash/hash.h create mode 100644 lib/ccan/hash/test/api-hash_stable.c create mode 100644 lib/ccan/hash/test/run.c (limited to 'lib/ccan/hash') diff --git a/lib/ccan/hash/_info b/lib/ccan/hash/_info new file mode 100644 index 0000000000..5aeb912136 --- /dev/null +++ b/lib/ccan/hash/_info @@ -0,0 +1,31 @@ +#include +#include + +/** + * hash - routines for hashing bytes + * + * When creating a hash table it's important to have a hash function + * which mixes well and is fast. This package supplies such functions. + * + * The hash functions come in two flavors: the normal ones and the + * stable ones. The normal ones can vary from machine-to-machine and + * may change if we find better or faster hash algorithms in future. + * The stable ones will always give the same results on any computer, + * and on any version of this package. + * + * License: Public Domain + * Maintainer: Rusty Russell + * Author: Bob Jenkins + */ +int main(int argc, char *argv[]) +{ + if (argc != 2) + return 1; + + if (strcmp(argv[1], "depends") == 0) { + printf("ccan/build_assert\n"); + return 0; + } + + return 1; +} diff --git a/lib/ccan/hash/hash.c b/lib/ccan/hash/hash.c new file mode 100644 index 0000000000..0fd6109513 --- /dev/null +++ b/lib/ccan/hash/hash.c @@ -0,0 +1,925 @@ +/* +------------------------------------------------------------------------------- +lookup3.c, by Bob Jenkins, May 2006, Public Domain. + +These are functions for producing 32-bit hashes for hash table lookup. +hash_word(), 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. + +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. +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 + a = i1; b = i2; c = i3; + mix(a,b,c); + a += i4; b += i5; c += i6; + mix(a,b,c); + a += i7; + 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 hash_word(). 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(). + +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. +------------------------------------------------------------------------------- +*/ +//#define SELF_TEST 1 + +#if 0 +#include /* defines printf for tests */ +#include /* defines time_t for timings in the test */ +#include /* defines uint32_t etc */ +#include /* attempt to define endianness */ + +#ifdef linux +# include /* attempt to define endianness */ +#endif + +/* + * My best guess at if you are big-endian or little-endian. This may + * need adjustment. + */ +#if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \ + __BYTE_ORDER == __LITTLE_ENDIAN) || \ + (defined(i386) || defined(__i386__) || defined(__i486__) || \ + defined(__i586__) || defined(__i686__) || defined(__x86_64) || \ + defined(vax) || defined(MIPSEL)) +# define HASH_LITTLE_ENDIAN 1 +# define HASH_BIG_ENDIAN 0 +#elif (defined(__BYTE_ORDER) && defined(__BIG_ENDIAN) && \ + __BYTE_ORDER == __BIG_ENDIAN) || \ + (defined(sparc) || defined(POWERPC) || defined(mc68000) || defined(sel)) +# define HASH_LITTLE_ENDIAN 0 +# define HASH_BIG_ENDIAN 1 +#else +# error Unknown endian +#endif +#endif /* old hash.c headers. */ + +#include "hash.h" + +#if HAVE_LITTLE_ENDIAN +#define HASH_LITTLE_ENDIAN 1 +#define HASH_BIG_ENDIAN 0 +#elif HAVE_BIG_ENDIAN +#define HASH_LITTLE_ENDIAN 0 +#define HASH_BIG_ENDIAN 1 +#else +#error Unknown endian +#endif + +#define hashsize(n) ((uint32_t)1<<(n)) +#define hashmask(n) (hashsize(n)-1) +#define rot(x,k) (((x)<<(k)) | ((x)>>(32-(k)))) + +/* +------------------------------------------------------------------------------- +mix -- mix 3 32-bit values reversibly. + +This is reversible, so any information in (a,b,c) before mix() is +still in (a,b,c) after mix(). + +If four pairs of (a,b,c) inputs are run through mix(), or through +mix() in reverse, there are at least 32 bits of the output that +are sometimes the same for one pair and different for another pair. +This was tested for: +* pairs that differed by one bit, by two bits, in any combination + of top bits of (a,b,c), or in any combination of bottom bits of + (a,b,c). +* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed + 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 + all zero plus a counter that starts at zero. + +Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that +satisfy this are + 4 6 8 16 19 4 + 9 15 3 18 27 15 + 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 +the operations, constants, and arrangements of the variables. + +This does not achieve avalanche. There are input bits of (a,b,c) +that fail to affect some output bits of (a,b,c), especially of a. The +most thoroughly mixed value is c, but it doesn't really even achieve +avalanche in c. + +This allows some parallelism. Read-after-writes are good at doubling +the number of bits affected, so the goal of mixing pulls in the opposite +direction as the goal of parallelism. I did what I could. Rotates +seem to cost as much as shifts on every machine I could lay my hands +on, and rotates are much kinder to the top and bottom bits, so I used +rotates. +------------------------------------------------------------------------------- +*/ +#define mix(a,b,c) \ +{ \ + a -= c; a ^= rot(c, 4); c += b; \ + b -= a; b ^= rot(a, 6); a += c; \ + c -= b; c ^= rot(b, 8); b += a; \ + a -= c; a ^= rot(c,16); c += b; \ + b -= a; b ^= rot(a,19); a += c; \ + c -= b; c ^= rot(b, 4); b += a; \ +} + +/* +------------------------------------------------------------------------------- +final -- final mixing of 3 32-bit values (a,b,c) into c + +Pairs of (a,b,c) values differing in only a few bits will usually +produce values of c that look totally different. This was tested for +* pairs that differed by one bit, by two bits, in any combination + of top bits of (a,b,c), or in any combination of bottom bits of + (a,b,c). +* "differ" is defined as +, -, ^, or ~^. For + and -, I transformed + 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 + all zero plus a counter that starts at zero. + +These constants passed: + 14 11 25 16 4 14 24 + 12 14 25 16 4 14 24 +and these came close: + 4 8 15 26 3 22 24 + 10 8 15 26 3 22 24 + 11 8 15 26 3 22 24 +------------------------------------------------------------------------------- +*/ +#define final(a,b,c) \ +{ \ + c ^= b; c -= rot(b,14); \ + a ^= c; a -= rot(c,11); \ + b ^= a; b -= rot(a,25); \ + c ^= b; c -= rot(b,16); \ + a ^= c; a -= rot(c,4); \ + b ^= a; b -= rot(a,14); \ + c ^= b; c -= rot(b,24); \ +} + +/* +-------------------------------------------------------------------- + This works on all machines. To be useful, it requires + -- that the key be an array of uint32_t's, and + -- that the length be the number of uint32_t's in the key + + The function hash_word() is identical to hashlittle() on little-endian + machines, and identical to hashbig() on big-endian machines, + except that the length has to be measured in uint32_ts rather than in + bytes. hashlittle() is more complicated than hash_word() only because + hashlittle() has to dance around fitting the key bytes into registers. +-------------------------------------------------------------------- +*/ +uint32_t hash_u32( +const uint32_t *k, /* the key, an array of uint32_t values */ +size_t length, /* the length of the key, in uint32_ts */ +uint32_t initval) /* the previous hash, or an arbitrary value */ +{ + uint32_t a,b,c; + + /* Set up the internal state */ + a = b = c = 0xdeadbeef + (((uint32_t)length)<<2) + initval; + + /*------------------------------------------------- handle most of the key */ + while (length > 3) + { + a += k[0]; + b += k[1]; + c += k[2]; + mix(a,b,c); + length -= 3; + k += 3; + } + + /*------------------------------------------- handle the last 3 uint32_t's */ + switch(length) /* all the case statements fall through */ + { + case 3 : c+=k[2]; + case 2 : b+=k[1]; + case 1 : a+=k[0]; + final(a,b,c); + case 0: /* case 0: nothing left to add */ + break; + } + /*------------------------------------------------------ report the result */ + return c; +} + +/* +------------------------------------------------------------------------------- +hashlittle() -- hash a variable-length key into a 32-bit value + k : the key (the unaligned variable-length array of bytes) + length : the length of the key, counting by bytes + val2 : IN: can be any 4-byte value OUT: second 32 bit hash. +Returns a 32-bit value. Every bit of the key affects every bit of +the return value. Two keys differing by one or two bits will have +totally different hash values. Note that the return value is better +mixed than val2, so use that first. + +The best hash table sizes are powers of 2. There is no need to do +mod a prime (mod is sooo slow!). If you need less than 32 bits, +use a bitmask. For example, if you need only 10 bits, do + h = (h & hashmask(10)); +In which case, the hash table should have hashsize(10) elements. + +If you are hashing n strings (uint8_t **)k, do it like this: + for (i=0, h=0; i 12) + { + a += k[0]; + b += k[1]; + c += k[2]; + mix(a,b,c); + length -= 12; + k += 3; + } + + /*----------------------------- handle the last (probably partial) block */ + /* + * "k[2]&0xffffff" actually reads beyond the end of the string, but + * then masks off the part it's not allowed to read. Because the + * string is aligned, the masked-off tail is in the same word as the + * rest of the string. Every machine with memory protection I've seen + * does it on word boundaries, so is OK with this. But VALGRIND will + * still catch it and complain. The masking trick does make the hash + * noticably faster for short strings (like English words). + * + * Not on my testing with gcc 4.5 on an intel i5 CPU, at least --RR. + */ +#if 0 + switch(length) + { + case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; + case 11: c+=k[2]&0xffffff; b+=k[1]; a+=k[0]; break; + case 10: c+=k[2]&0xffff; b+=k[1]; a+=k[0]; break; + case 9 : c+=k[2]&0xff; b+=k[1]; a+=k[0]; break; + case 8 : b+=k[1]; a+=k[0]; break; + case 7 : b+=k[1]&0xffffff; a+=k[0]; break; + case 6 : b+=k[1]&0xffff; a+=k[0]; break; + case 5 : b+=k[1]&0xff; a+=k[0]; break; + case 4 : a+=k[0]; break; + case 3 : a+=k[0]&0xffffff; break; + case 2 : a+=k[0]&0xffff; break; + case 1 : a+=k[0]&0xff; break; + case 0 : return c; /* zero length strings require no mixing */ + } + +#else /* make valgrind happy */ + + k8 = (const uint8_t *)k; + switch(length) + { + case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; + case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ + case 10: c+=((uint32_t)k8[9])<<8; /* fall through */ + case 9 : c+=k8[8]; /* fall through */ + case 8 : b+=k[1]; a+=k[0]; break; + case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ + case 6 : b+=((uint32_t)k8[5])<<8; /* fall through */ + case 5 : b+=k8[4]; /* fall through */ + case 4 : a+=k[0]; break; + case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ + case 2 : a+=((uint32_t)k8[1])<<8; /* fall through */ + case 1 : a+=k8[0]; break; + case 0 : return c; + } + +#endif /* !valgrind */ + + } else if (HASH_LITTLE_ENDIAN && ((u.i & 0x1) == 0)) { + const uint16_t *k = (const uint16_t *)key; /* read 16-bit chunks */ + const uint8_t *k8; + + /*--------------- all but last block: aligned reads and different mixing */ + while (length > 12) + { + a += k[0] + (((uint32_t)k[1])<<16); + b += k[2] + (((uint32_t)k[3])<<16); + c += k[4] + (((uint32_t)k[5])<<16); + mix(a,b,c); + length -= 12; + k += 6; + } + + /*----------------------------- handle the last (probably partial) block */ + k8 = (const uint8_t *)k; + switch(length) + { + case 12: c+=k[4]+(((uint32_t)k[5])<<16); + b+=k[2]+(((uint32_t)k[3])<<16); + a+=k[0]+(((uint32_t)k[1])<<16); + break; + case 11: c+=((uint32_t)k8[10])<<16; /* fall through */ + case 10: c+=k[4]; + b+=k[2]+(((uint32_t)k[3])<<16); + a+=k[0]+(((uint32_t)k[1])<<16); + break; + case 9 : c+=k8[8]; /* fall through */ + case 8 : b+=k[2]+(((uint32_t)k[3])<<16); + a+=k[0]+(((uint32_t)k[1])<<16); + break; + case 7 : b+=((uint32_t)k8[6])<<16; /* fall through */ + case 6 : b+=k[2]; + a+=k[0]+(((uint32_t)k[1])<<16); + break; + case 5 : b+=k8[4]; /* fall through */ + case 4 : a+=k[0]+(((uint32_t)k[1])<<16); + break; + case 3 : a+=((uint32_t)k8[2])<<16; /* fall through */ + case 2 : a+=k[0]; + break; + case 1 : a+=k8[0]; + break; + case 0 : return c; /* zero length requires no mixing */ + } + + } else { /* need to read the key one byte at a time */ + const uint8_t *k = (const uint8_t *)key; + + /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ + while (length > 12) + { + a += k[0]; + a += ((uint32_t)k[1])<<8; + a += ((uint32_t)k[2])<<16; + a += ((uint32_t)k[3])<<24; + b += k[4]; + b += ((uint32_t)k[5])<<8; + b += ((uint32_t)k[6])<<16; + b += ((uint32_t)k[7])<<24; + c += k[8]; + c += ((uint32_t)k[9])<<8; + c += ((uint32_t)k[10])<<16; + c += ((uint32_t)k[11])<<24; + mix(a,b,c); + length -= 12; + k += 12; + } + + /*-------------------------------- last block: affect all 32 bits of (c) */ + switch(length) /* all the case statements fall through */ + { + case 12: c+=((uint32_t)k[11])<<24; + case 11: c+=((uint32_t)k[10])<<16; + case 10: c+=((uint32_t)k[9])<<8; + case 9 : c+=k[8]; + case 8 : b+=((uint32_t)k[7])<<24; + case 7 : b+=((uint32_t)k[6])<<16; + case 6 : b+=((uint32_t)k[5])<<8; + case 5 : b+=k[4]; + case 4 : a+=((uint32_t)k[3])<<24; + case 3 : a+=((uint32_t)k[2])<<16; + case 2 : a+=((uint32_t)k[1])<<8; + case 1 : a+=k[0]; + break; + case 0 : return c; + } + } + + final(a,b,c); + *val2 = b; + return c; +} + +/* + * hashbig(): + * This is the same as hash_word() on big-endian machines. It is different + * from hashlittle() on all machines. hashbig() takes advantage of + * big-endian byte ordering. + */ +static uint32_t hashbig( const void *key, size_t length, uint32_t *val2) +{ + uint32_t a,b,c; + union { const void *ptr; size_t i; } u; /* to cast key to (size_t) happily */ + + /* Set up the internal state */ + a = b = c = 0xdeadbeef + ((uint32_t)length) + *val2; + + u.ptr = key; + if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) { + const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ + const uint8_t *k8; + + /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ + while (length > 12) + { + a += k[0]; + b += k[1]; + c += k[2]; + mix(a,b,c); + length -= 12; + k += 3; + } + + /*----------------------------- handle the last (probably partial) block */ + /* + * "k[2]<<8" actually reads beyond the end of the string, but + * then shifts out the part it's not allowed to read. Because the + * string is aligned, the illegal read is in the same word as the + * rest of the string. Every machine with memory protection I've seen + * does it on word boundaries, so is OK with this. But VALGRIND will + * still catch it and complain. The masking trick does make the hash + * noticably faster for short strings (like English words). + * + * Not on my testing with gcc 4.5 on an intel i5 CPU, at least --RR. + */ +#if 0 + switch(length) + { + case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; + case 11: c+=k[2]&0xffffff00; b+=k[1]; a+=k[0]; break; + case 10: c+=k[2]&0xffff0000; b+=k[1]; a+=k[0]; break; + case 9 : c+=k[2]&0xff000000; b+=k[1]; a+=k[0]; break; + case 8 : b+=k[1]; a+=k[0]; break; + case 7 : b+=k[1]&0xffffff00; a+=k[0]; break; + case 6 : b+=k[1]&0xffff0000; a+=k[0]; break; + case 5 : b+=k[1]&0xff000000; a+=k[0]; break; + case 4 : a+=k[0]; break; + case 3 : a+=k[0]&0xffffff00; break; + case 2 : a+=k[0]&0xffff0000; break; + case 1 : a+=k[0]&0xff000000; break; + case 0 : return c; /* zero length strings require no mixing */ + } + +#else /* make valgrind happy */ + + k8 = (const uint8_t *)k; + switch(length) /* all the case statements fall through */ + { + case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; + case 11: c+=((uint32_t)k8[10])<<8; /* fall through */ + case 10: c+=((uint32_t)k8[9])<<16; /* fall through */ + case 9 : c+=((uint32_t)k8[8])<<24; /* fall through */ + case 8 : b+=k[1]; a+=k[0]; break; + case 7 : b+=((uint32_t)k8[6])<<8; /* fall through */ + case 6 : b+=((uint32_t)k8[5])<<16; /* fall through */ + case 5 : b+=((uint32_t)k8[4])<<24; /* fall through */ + case 4 : a+=k[0]; break; + case 3 : a+=((uint32_t)k8[2])<<8; /* fall through */ + case 2 : a+=((uint32_t)k8[1])<<16; /* fall through */ + case 1 : a+=((uint32_t)k8[0])<<24; break; + case 0 : return c; + } + +#endif /* !VALGRIND */ + + } else { /* need to read the key one byte at a time */ + const uint8_t *k = (const uint8_t *)key; + + /*--------------- all but the last block: affect some 32 bits of (a,b,c) */ + while (length > 12) + { + a += ((uint32_t)k[0])<<24; + a += ((uint32_t)k[1])<<16; + a += ((uint32_t)k[2])<<8; + a += ((uint32_t)k[3]); + b += ((uint32_t)k[4])<<24; + b += ((uint32_t)k[5])<<16; + b += ((uint32_t)k[6])<<8; + b += ((uint32_t)k[7]); + c += ((uint32_t)k[8])<<24; + c += ((uint32_t)k[9])<<16; + c += ((uint32_t)k[10])<<8; + c += ((uint32_t)k[11]); + mix(a,b,c); + length -= 12; + k += 12; + } + + /*-------------------------------- last block: affect all 32 bits of (c) */ + switch(length) /* all the case statements fall through */ + { + case 12: c+=k[11]; + case 11: c+=((uint32_t)k[10])<<8; + case 10: c+=((uint32_t)k[9])<<16; + case 9 : c+=((uint32_t)k[8])<<24; + case 8 : b+=k[7]; + case 7 : b+=((uint32_t)k[6])<<8; + case 6 : b+=((uint32_t)k[5])<<16; + case 5 : b+=((uint32_t)k[4])<<24; + case 4 : a+=k[3]; + case 3 : a+=((uint32_t)k[2])<<8; + case 2 : a+=((uint32_t)k[1])<<16; + case 1 : a+=((uint32_t)k[0])<<24; + break; + case 0 : return c; + } + } + + final(a,b,c); + *val2 = b; + return c; +} + +/* I basically use hashlittle here, but use native endian within each + * element. This delivers least-surprise: hash such as "int arr[] = { + * 1, 2 }; hash_stable(arr, 2, 0);" will be the same on big and little + * endian machines, even though a bytewise hash wouldn't be. */ +uint64_t hash64_stable_64(const void *key, size_t n, uint64_t base) +{ + const uint64_t *k = key; + uint32_t a,b,c; + + /* Set up the internal state */ + a = b = c = 0xdeadbeef + ((uint32_t)n*8) + (base >> 32) + base; + + while (n > 3) { + a += (uint32_t)k[0]; + b += (uint32_t)(k[0] >> 32); + c += (uint32_t)k[1]; + mix(a,b,c); + a += (uint32_t)(k[1] >> 32); + b += (uint32_t)k[2]; + c += (uint32_t)(k[2] >> 32); + mix(a,b,c); + n -= 3; + k += 3; + } + switch (n) { + case 2: + a += (uint32_t)k[0]; + b += (uint32_t)(k[0] >> 32); + c += (uint32_t)k[1]; + mix(a,b,c); + a += (uint32_t)(k[1] >> 32); + break; + case 1: + a += (uint32_t)k[0]; + b += (uint32_t)(k[0] >> 32); + break; + case 0: + return c; + } + final(a,b,c); + return ((uint64_t)b << 32) | c; +} + +uint64_t hash64_stable_32(const void *key, size_t n, uint64_t base) +{ + const uint32_t *k = key; + uint32_t a,b,c; + + /* Set up the internal state */ + a = b = c = 0xdeadbeef + ((uint32_t)n*4) + (base >> 32) + base; + + while (n > 3) { + a += k[0]; + b += k[1]; + c += k[2]; + mix(a,b,c); + + n -= 3; + k += 3; + } + switch (n) { + case 2: + b += (uint32_t)k[1]; + case 1: + a += (uint32_t)k[0]; + break; + case 0: + return c; + } + final(a,b,c); + return ((uint64_t)b << 32) | c; +} + +uint64_t hash64_stable_16(const void *key, size_t n, uint64_t base) +{ + const uint16_t *k = key; + uint32_t a,b,c; + + /* Set up the internal state */ + a = b = c = 0xdeadbeef + ((uint32_t)n*2) + (base >> 32) + base; + + while (n > 6) { + a += (uint32_t)k[0] + ((uint32_t)k[1] << 16); + b += (uint32_t)k[2] + ((uint32_t)k[3] << 16); + c += (uint32_t)k[4] + ((uint32_t)k[5] << 16); + mix(a,b,c); + + n -= 6; + k += 6; + } + + switch (n) { + case 5: + c += (uint32_t)k[4]; + case 4: + b += ((uint32_t)k[3] << 16); + case 3: + b += (uint32_t)k[2]; + case 2: + a += ((uint32_t)k[1] << 16); + case 1: + a += (uint32_t)k[0]; + break; + case 0: + return c; + } + final(a,b,c); + return ((uint64_t)b << 32) | c; +} + +uint64_t hash64_stable_8(const void *key, size_t n, uint64_t base) +{ + uint32_t b32 = base + (base >> 32); + uint32_t lower = hashlittle(key, n, &b32); + + return ((uint64_t)b32 << 32) | lower; +} + +uint32_t hash_any(const void *key, size_t length, uint32_t base) +{ + if (HASH_BIG_ENDIAN) + return hashbig(key, length, &base); + else + return hashlittle(key, length, &base); +} + +uint32_t hash_stable_64(const void *key, size_t n, uint32_t base) +{ + return hash64_stable_64(key, n, base); +} + +uint32_t hash_stable_32(const void *key, size_t n, uint32_t base) +{ + return hash64_stable_32(key, n, base); +} + +uint32_t hash_stable_16(const void *key, size_t n, uint32_t base) +{ + return hash64_stable_16(key, n, base); +} + +uint32_t hash_stable_8(const void *key, size_t n, uint32_t base) +{ + return hashlittle(key, n, &base); +} + +/* Jenkins' lookup8 is a 64 bit hash, but he says it's obsolete. Use + * the plain one and recombine into 64 bits. */ +uint64_t hash64_any(const void *key, size_t length, uint64_t base) +{ + uint32_t b32 = base + (base >> 32); + uint32_t lower; + + if (HASH_BIG_ENDIAN) + lower = hashbig(key, length, &b32); + else + lower = hashlittle(key, length, &b32); + + return ((uint64_t)b32 << 32) | lower; +} + +#ifdef SELF_TEST + +/* used for timings */ +void driver1() +{ + uint8_t buf[256]; + uint32_t i; + uint32_t h=0; + time_t a,z; + + time(&a); + for (i=0; i<256; ++i) buf[i] = 'x'; + for (i=0; i<1; ++i) + { + h = hashlittle(&buf[0],1,h); + } + time(&z); + if (z-a > 0) printf("time %d %.8x\n", z-a, h); +} + +/* check that every input bit changes every output bit half the time */ +#define HASHSTATE 1 +#define HASHLEN 1 +#define MAXPAIR 60 +#define MAXLEN 70 +void driver2() +{ + uint8_t qa[MAXLEN+1], qb[MAXLEN+2], *a = &qa[0], *b = &qb[1]; + uint32_t c[HASHSTATE], d[HASHSTATE], i=0, j=0, k, l, m=0, z; + uint32_t e[HASHSTATE],f[HASHSTATE],g[HASHSTATE],h[HASHSTATE]; + uint32_t x[HASHSTATE],y[HASHSTATE]; + uint32_t hlen; + + printf("No more than %d trials should ever be needed \n",MAXPAIR/2); + for (hlen=0; hlen < MAXLEN; ++hlen) + { + z=0; + for (i=0; i>(8-j)); + c[0] = hashlittle(a, hlen, m); + b[i] ^= ((k+1)<>(8-j)); + d[0] = hashlittle(b, hlen, m); + /* check every bit is 1, 0, set, and not set at least once */ + for (l=0; lz) z=k; + if (k==MAXPAIR) + { + printf("Some bit didn't change: "); + printf("%.8x %.8x %.8x %.8x %.8x %.8x ", + e[0],f[0],g[0],h[0],x[0],y[0]); + printf("i %d j %d m %d len %d\n", i, j, m, hlen); + } + if (z==MAXPAIR) goto done; + } + } + } + done: + if (z < MAXPAIR) + { + printf("Mix success %2d bytes %2d initvals ",i,m); + printf("required %d trials\n", z/2); + } + } + printf("\n"); +} + +/* Check for reading beyond the end of the buffer and alignment problems */ +void driver3() +{ + uint8_t buf[MAXLEN+20], *b; + uint32_t len; + uint8_t q[] = "This is the time for all good men to come to the aid of their country..."; + uint32_t h; + uint8_t qq[] = "xThis is the time for all good men to come to the aid of their country..."; + uint32_t i; + uint8_t qqq[] = "xxThis is the time for all good men to come to the aid of their country..."; + uint32_t j; + uint8_t qqqq[] = "xxxThis is the time for all good men to come to the aid of their country..."; + uint32_t ref,x,y; + uint8_t *p; + + printf("Endianness. These lines should all be the same (for values filled in):\n"); + printf("%.8x %.8x %.8x\n", + hash_word((const uint32_t *)q, (sizeof(q)-1)/4, 13), + hash_word((const uint32_t *)q, (sizeof(q)-5)/4, 13), + hash_word((const uint32_t *)q, (sizeof(q)-9)/4, 13)); + p = q; + printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n", + hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13), + hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13), + hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13), + hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13), + hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13), + hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13)); + p = &qq[1]; + printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n", + hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13), + hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13), + hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13), + hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13), + hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13), + hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13)); + p = &qqq[2]; + printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n", + hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13), + hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13), + hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13), + hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13), + hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13), + hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13)); + p = &qqqq[3]; + printf("%.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x %.8x\n", + hashlittle(p, sizeof(q)-1, 13), hashlittle(p, sizeof(q)-2, 13), + hashlittle(p, sizeof(q)-3, 13), hashlittle(p, sizeof(q)-4, 13), + hashlittle(p, sizeof(q)-5, 13), hashlittle(p, sizeof(q)-6, 13), + hashlittle(p, sizeof(q)-7, 13), hashlittle(p, sizeof(q)-8, 13), + hashlittle(p, sizeof(q)-9, 13), hashlittle(p, sizeof(q)-10, 13), + hashlittle(p, sizeof(q)-11, 13), hashlittle(p, sizeof(q)-12, 13)); + printf("\n"); + + /* check that hashlittle2 and hashlittle produce the same results */ + i=47; j=0; + hashlittle2(q, sizeof(q), &i, &j); + if (hashlittle(q, sizeof(q), 47) != i) + printf("hashlittle2 and hashlittle mismatch\n"); + + /* check that hash_word2 and hash_word produce the same results */ + len = 0xdeadbeef; + i=47, j=0; + hash_word2(&len, 1, &i, &j); + if (hash_word(&len, 1, 47) != i) + printf("hash_word2 and hash_word mismatch %x %x\n", + i, hash_word(&len, 1, 47)); + + /* check hashlittle doesn't read before or after the ends of the string */ + for (h=0, b=buf+1; h<8; ++h, ++b) + { + for (i=0; i +#include +#include + +/* Stolen mostly from: lookup3.c, by Bob Jenkins, May 2006, Public Domain. + * + * http://burtleburtle.net/bob/c/lookup3.c + */ + +/** + * hash - fast hash of an array for internal use + * @p: the array or pointer to first element + * @num: the number of elements to hash + * @base: the base number to roll into the hash (usually 0) + * + * The memory region pointed to by p is combined with the base to form + * a 32-bit hash. + * + * This hash will have different results on different machines, so is + * only useful for internal hashes (ie. not hashes sent across the + * network or saved to disk). + * + * It may also change with future versions: it could even detect at runtime + * what the fastest hash to use is. + * + * See also: hash64, hash_stable. + * + * Example: + * #include + * #include + * #include + * #include + * + * // Simple demonstration: idential strings will have the same hash, but + * // two different strings will probably not. + * int main(int argc, char *argv[]) + * { + * uint32_t hash1, hash2; + * + * if (argc != 3) + * err(1, "Usage: %s ", argv[0]); + * + * hash1 = hash(argv[1], strlen(argv[1]), 0); + * hash2 = hash(argv[2], strlen(argv[2]), 0); + * printf("Hash is %s\n", hash1 == hash2 ? "same" : "different"); + * return 0; + * } + */ +#define hash(p, num, base) hash_any((p), (num)*sizeof(*(p)), (base)) + +/** + * hash_stable - hash of an array for external use + * @p: the array or pointer to first element + * @num: the number of elements to hash + * @base: the base number to roll into the hash (usually 0) + * + * The array of simple integer types pointed to by p is combined with + * the base to form a 32-bit hash. + * + * This hash will have the same results on different machines, so can + * be used for external hashes (ie. hashes sent across the network or + * saved to disk). The results will not change in future versions of + * this module. + * + * Note that it is only legal to hand an array of simple integer types + * to this hash (ie. char, uint16_t, int64_t, etc). In these cases, + * the same values will have the same hash result, even though the + * memory representations of integers depend on the machine + * endianness. + * + * See also: + * hash64_stable + * + * Example: + * #include + * #include + * #include + * #include + * + * int main(int argc, char *argv[]) + * { + * if (argc != 2) + * err(1, "Usage: %s ", argv[0]); + * + * printf("Hash stable result is %u\n", + * hash_stable(argv[1], strlen(argv[1]), 0)); + * return 0; + * } + */ +#define hash_stable(p, num, base) \ + (BUILD_ASSERT_OR_ZERO(sizeof(*(p)) == 8 || sizeof(*(p)) == 4 \ + || sizeof(*(p)) == 2 || sizeof(*(p)) == 1) + \ + sizeof(*(p)) == 8 ? hash_stable_64((p), (num), (base)) \ + : sizeof(*(p)) == 4 ? hash_stable_32((p), (num), (base)) \ + : sizeof(*(p)) == 2 ? hash_stable_16((p), (num), (base)) \ + : hash_stable_8((p), (num), (base))) + +/** + * hash_u32 - fast hash an array of 32-bit values for internal use + * @key: the array of uint32_t + * @num: the number of elements to hash + * @base: the base number to roll into the hash (usually 0) + * + * The array of uint32_t pointed to by @key is combined with the base + * to form a 32-bit hash. This is 2-3 times faster than hash() on small + * arrays, but the advantage vanishes over large hashes. + * + * This hash will have different results on different machines, so is + * only useful for internal hashes (ie. not hashes sent across the + * network or saved to disk). + */ +uint32_t hash_u32(const uint32_t *key, size_t num, uint32_t base); + +/** + * hash_string - very fast hash of an ascii string + * @str: the nul-terminated string + * + * The string is hashed, using a hash function optimized for ASCII and + * similar strings. It's weaker than the other hash functions. + * + * This hash may have different results on different machines, so is + * only useful for internal hashes (ie. not hashes sent across the + * network or saved to disk). The results will be different from the + * other hash functions in this module, too. + */ +static inline uint32_t hash_string(const char *string) +{ + /* This is Karl Nelson 's X31 hash. + * It's a little faster than the (much better) lookup3 hash(): 56ns vs + * 84ns on my 2GHz Intel Core Duo 2 laptop for a 10 char string. */ + uint32_t ret; + + for (ret = 0; *string; string++) + ret = (ret << 5) - ret + *string; + + return ret; +} + +/** + * hash64 - fast 64-bit hash of an array for internal use + * @p: the array or pointer to first element + * @num: the number of elements to hash + * @base: the 64-bit base number to roll into the hash (usually 0) + * + * The memory region pointed to by p is combined with the base to form + * a 64-bit hash. + * + * This hash will have different results on different machines, so is + * only useful for internal hashes (ie. not hashes sent across the + * network or saved to disk). + * + * It may also change with future versions: it could even detect at runtime + * what the fastest hash to use is. + * + * See also: hash. + * + * Example: + * #include + * #include + * #include + * #include + * + * // Simple demonstration: idential strings will have the same hash, but + * // two different strings will probably not. + * int main(int argc, char *argv[]) + * { + * uint64_t hash1, hash2; + * + * if (argc != 3) + * err(1, "Usage: %s ", argv[0]); + * + * hash1 = hash64(argv[1], strlen(argv[1]), 0); + * hash2 = hash64(argv[2], strlen(argv[2]), 0); + * printf("Hash is %s\n", hash1 == hash2 ? "same" : "different"); + * return 0; + * } + */ +#define hash64(p, num, base) hash64_any((p), (num)*sizeof(*(p)), (base)) + +/** + * hash64_stable - 64 bit hash of an array for external use + * @p: the array or pointer to first element + * @num: the number of elements to hash + * @base: the base number to roll into the hash (usually 0) + * + * The array of simple integer types pointed to by p is combined with + * the base to form a 64-bit hash. + * + * This hash will have the same results on different machines, so can + * be used for external hashes (ie. hashes sent across the network or + * saved to disk). The results will not change in future versions of + * this module. + * + * Note that it is only legal to hand an array of simple integer types + * to this hash (ie. char, uint16_t, int64_t, etc). In these cases, + * the same values will have the same hash result, even though the + * memory representations of integers depend on the machine + * endianness. + * + * See also: + * hash_stable + * + * Example: + * #include + * #include + * #include + * #include + * + * int main(int argc, char *argv[]) + * { + * if (argc != 2) + * err(1, "Usage: %s ", argv[0]); + * + * printf("Hash stable result is %llu\n", + * (long long)hash64_stable(argv[1], strlen(argv[1]), 0)); + * return 0; + * } + */ +#define hash64_stable(p, num, base) \ + (BUILD_ASSERT_OR_ZERO(sizeof(*(p)) == 8 || sizeof(*(p)) == 4 \ + || sizeof(*(p)) == 2 || sizeof(*(p)) == 1) + \ + sizeof(*(p)) == 8 ? hash64_stable_64((p), (num), (base)) \ + : sizeof(*(p)) == 4 ? hash64_stable_32((p), (num), (base)) \ + : sizeof(*(p)) == 2 ? hash64_stable_16((p), (num), (base)) \ + : hash64_stable_8((p), (num), (base))) + + +/** + * hashl - fast 32/64-bit hash of an array for internal use + * @p: the array or pointer to first element + * @num: the number of elements to hash + * @base: the base number to roll into the hash (usually 0) + * + * This is either hash() or hash64(), on 32/64 bit long machines. + */ +#define hashl(p, num, base) \ + (BUILD_ASSERT_OR_ZERO(sizeof(long) == sizeof(uint32_t) \ + || sizeof(long) == sizeof(uint64_t)) + \ + (sizeof(long) == sizeof(uint64_t) \ + ? hash64((p), (num), (base)) : hash((p), (num), (base)))) + +/* Our underlying operations. */ +uint32_t hash_any(const void *key, size_t length, uint32_t base); +uint32_t hash_stable_64(const void *key, size_t n, uint32_t base); +uint32_t hash_stable_32(const void *key, size_t n, uint32_t base); +uint32_t hash_stable_16(const void *key, size_t n, uint32_t base); +uint32_t hash_stable_8(const void *key, size_t n, uint32_t base); +uint64_t hash64_any(const void *key, size_t length, uint64_t base); +uint64_t hash64_stable_64(const void *key, size_t n, uint64_t base); +uint64_t hash64_stable_32(const void *key, size_t n, uint64_t base); +uint64_t hash64_stable_16(const void *key, size_t n, uint64_t base); +uint64_t hash64_stable_8(const void *key, size_t n, uint64_t base); + +/** + * hash_pointer - hash a pointer for internal use + * @p: the pointer value to hash + * @base: the base number to roll into the hash (usually 0) + * + * The pointer p (not what p points to!) is combined with the base to form + * a 32-bit hash. + * + * This hash will have different results on different machines, so is + * only useful for internal hashes (ie. not hashes sent across the + * network or saved to disk). + * + * Example: + * #include + * + * // Code to keep track of memory regions. + * struct region { + * struct region *chain; + * void *start; + * unsigned int size; + * }; + * // We keep a simple hash table. + * static struct region *region_hash[128]; + * + * static void add_region(struct region *r) + * { + * unsigned int h = hash_pointer(r->start, 0); + * + * r->chain = region_hash[h]; + * region_hash[h] = r->chain; + * } + * + * static struct region *find_region(const void *start) + * { + * struct region *r; + * + * for (r = region_hash[hash_pointer(start, 0)]; r; r = r->chain) + * if (r->start == start) + * return r; + * return NULL; + * } + */ +static inline uint32_t hash_pointer(const void *p, uint32_t base) +{ + if (sizeof(p) % sizeof(uint32_t) == 0) { + /* This convoluted union is the right way of aliasing. */ + union { + uint32_t u32[sizeof(p) / sizeof(uint32_t)]; + const void *p; + } u; + u.p = p; + return hash_u32(u.u32, sizeof(p) / sizeof(uint32_t), base); + } else + return hash(&p, 1, base); +} +#endif /* HASH_H */ diff --git a/lib/ccan/hash/test/api-hash_stable.c b/lib/ccan/hash/test/api-hash_stable.c new file mode 100644 index 0000000000..bb58d16b18 --- /dev/null +++ b/lib/ccan/hash/test/api-hash_stable.c @@ -0,0 +1,300 @@ +#include +#include +#include +#include + +#define ARRAY_WORDS 5 + +int main(int argc, char *argv[]) +{ + unsigned int i; + uint8_t u8array[ARRAY_WORDS]; + uint16_t u16array[ARRAY_WORDS]; + uint32_t u32array[ARRAY_WORDS]; + uint64_t u64array[ARRAY_WORDS]; + + /* Initialize arrays. */ + for (i = 0; i < ARRAY_WORDS; i++) { + u8array[i] = i; + u16array[i] = i; + u32array[i] = i; + u64array[i] = i; + } + + plan_tests(264); + + /* hash_stable is API-guaranteed. */ + ok1(hash_stable(u8array, ARRAY_WORDS, 0) == 0x1d4833cc); + ok1(hash_stable(u8array, ARRAY_WORDS, 1) == 0x37125e2 ); + ok1(hash_stable(u8array, ARRAY_WORDS, 2) == 0x330a007a); + ok1(hash_stable(u8array, ARRAY_WORDS, 4) == 0x7b0df29b); + ok1(hash_stable(u8array, ARRAY_WORDS, 8) == 0xe7e5d741); + ok1(hash_stable(u8array, ARRAY_WORDS, 16) == 0xaae57471); + ok1(hash_stable(u8array, ARRAY_WORDS, 32) == 0xc55399e5); + ok1(hash_stable(u8array, ARRAY_WORDS, 64) == 0x67f21f7 ); + ok1(hash_stable(u8array, ARRAY_WORDS, 128) == 0x1d795b71); + ok1(hash_stable(u8array, ARRAY_WORDS, 256) == 0xeb961671); + ok1(hash_stable(u8array, ARRAY_WORDS, 512) == 0xc2597247); + ok1(hash_stable(u8array, ARRAY_WORDS, 1024) == 0x3f5c4d75); + ok1(hash_stable(u8array, ARRAY_WORDS, 2048) == 0xe65cf4f9); + ok1(hash_stable(u8array, ARRAY_WORDS, 4096) == 0xf2cd06cb); + ok1(hash_stable(u8array, ARRAY_WORDS, 8192) == 0x443041e1); + ok1(hash_stable(u8array, ARRAY_WORDS, 16384) == 0xdfc618f5); + ok1(hash_stable(u8array, ARRAY_WORDS, 32768) == 0x5e3d5b97); + ok1(hash_stable(u8array, ARRAY_WORDS, 65536) == 0xd5f64730); + ok1(hash_stable(u8array, ARRAY_WORDS, 131072) == 0x372bbecc); + ok1(hash_stable(u8array, ARRAY_WORDS, 262144) == 0x7c194c8d); + ok1(hash_stable(u8array, ARRAY_WORDS, 524288) == 0x16cbb416); + ok1(hash_stable(u8array, ARRAY_WORDS, 1048576) == 0x53e99222); + ok1(hash_stable(u8array, ARRAY_WORDS, 2097152) == 0x6394554a); + ok1(hash_stable(u8array, ARRAY_WORDS, 4194304) == 0xd83a506d); + ok1(hash_stable(u8array, ARRAY_WORDS, 8388608) == 0x7619d9a4); + ok1(hash_stable(u8array, ARRAY_WORDS, 16777216) == 0xfe98e5f6); + ok1(hash_stable(u8array, ARRAY_WORDS, 33554432) == 0x6c262927); + ok1(hash_stable(u8array, ARRAY_WORDS, 67108864) == 0x3f0106fd); + ok1(hash_stable(u8array, ARRAY_WORDS, 134217728) == 0xc91e3a28); + ok1(hash_stable(u8array, ARRAY_WORDS, 268435456) == 0x14229579); + ok1(hash_stable(u8array, ARRAY_WORDS, 536870912) == 0x9dbefa76); + ok1(hash_stable(u8array, ARRAY_WORDS, 1073741824) == 0xb05c0c78); + ok1(hash_stable(u8array, ARRAY_WORDS, 2147483648U) == 0x88f24d81); + + ok1(hash_stable(u16array, ARRAY_WORDS, 0) == 0xecb5f507); + ok1(hash_stable(u16array, ARRAY_WORDS, 1) == 0xadd666e6); + ok1(hash_stable(u16array, ARRAY_WORDS, 2) == 0xea0f214c); + ok1(hash_stable(u16array, ARRAY_WORDS, 4) == 0xae4051ba); + ok1(hash_stable(u16array, ARRAY_WORDS, 8) == 0x6ed28026); + ok1(hash_stable(u16array, ARRAY_WORDS, 16) == 0xa3917a19); + ok1(hash_stable(u16array, ARRAY_WORDS, 32) == 0xf370f32b); + ok1(hash_stable(u16array, ARRAY_WORDS, 64) == 0x807af460); + ok1(hash_stable(u16array, ARRAY_WORDS, 128) == 0xb4c8cd83); + ok1(hash_stable(u16array, ARRAY_WORDS, 256) == 0xa10cb5b0); + ok1(hash_stable(u16array, ARRAY_WORDS, 512) == 0x8b7d7387); + ok1(hash_stable(u16array, ARRAY_WORDS, 1024) == 0x9e49d1c ); + ok1(hash_stable(u16array, ARRAY_WORDS, 2048) == 0x288830d1); + ok1(hash_stable(u16array, ARRAY_WORDS, 4096) == 0xbe078a43); + ok1(hash_stable(u16array, ARRAY_WORDS, 8192) == 0xa16d5d88); + ok1(hash_stable(u16array, ARRAY_WORDS, 16384) == 0x46839fcd); + ok1(hash_stable(u16array, ARRAY_WORDS, 32768) == 0x9db9bd4f); + ok1(hash_stable(u16array, ARRAY_WORDS, 65536) == 0xedff58f8); + ok1(hash_stable(u16array, ARRAY_WORDS, 131072) == 0x95ecef18); + ok1(hash_stable(u16array, ARRAY_WORDS, 262144) == 0x23c31b7d); + ok1(hash_stable(u16array, ARRAY_WORDS, 524288) == 0x1d85c7d0); + ok1(hash_stable(u16array, ARRAY_WORDS, 1048576) == 0x25218842); + ok1(hash_stable(u16array, ARRAY_WORDS, 2097152) == 0x711d985c); + ok1(hash_stable(u16array, ARRAY_WORDS, 4194304) == 0x85470eca); + ok1(hash_stable(u16array, ARRAY_WORDS, 8388608) == 0x99ed4ceb); + ok1(hash_stable(u16array, ARRAY_WORDS, 16777216) == 0x67b3710c); + ok1(hash_stable(u16array, ARRAY_WORDS, 33554432) == 0x77f1ab35); + ok1(hash_stable(u16array, ARRAY_WORDS, 67108864) == 0x81f688aa); + ok1(hash_stable(u16array, ARRAY_WORDS, 134217728) == 0x27b56ca5); + ok1(hash_stable(u16array, ARRAY_WORDS, 268435456) == 0xf21ba203); + ok1(hash_stable(u16array, ARRAY_WORDS, 536870912) == 0xd48d1d1 ); + ok1(hash_stable(u16array, ARRAY_WORDS, 1073741824) == 0xa542b62d); + ok1(hash_stable(u16array, ARRAY_WORDS, 2147483648U) == 0xa04c7058); + + ok1(hash_stable(u32array, ARRAY_WORDS, 0) == 0x13305f8c); + ok1(hash_stable(u32array, ARRAY_WORDS, 1) == 0x171abf74); + ok1(hash_stable(u32array, ARRAY_WORDS, 2) == 0x7646fcc7); + ok1(hash_stable(u32array, ARRAY_WORDS, 4) == 0xa758ed5); + ok1(hash_stable(u32array, ARRAY_WORDS, 8) == 0x2dedc2e4); + ok1(hash_stable(u32array, ARRAY_WORDS, 16) == 0x28e2076b); + ok1(hash_stable(u32array, ARRAY_WORDS, 32) == 0xb73091c5); + ok1(hash_stable(u32array, ARRAY_WORDS, 64) == 0x87daf5db); + ok1(hash_stable(u32array, ARRAY_WORDS, 128) == 0xa16dfe20); + ok1(hash_stable(u32array, ARRAY_WORDS, 256) == 0x300c63c3); + ok1(hash_stable(u32array, ARRAY_WORDS, 512) == 0x255c91fc); + ok1(hash_stable(u32array, ARRAY_WORDS, 1024) == 0x6357b26); + ok1(hash_stable(u32array, ARRAY_WORDS, 2048) == 0x4bc5f339); + ok1(hash_stable(u32array, ARRAY_WORDS, 4096) == 0x1301617c); + ok1(hash_stable(u32array, ARRAY_WORDS, 8192) == 0x506792c9); + ok1(hash_stable(u32array, ARRAY_WORDS, 16384) == 0xcd596705); + ok1(hash_stable(u32array, ARRAY_WORDS, 32768) == 0xa8713cac); + ok1(hash_stable(u32array, ARRAY_WORDS, 65536) == 0x94d9794); + ok1(hash_stable(u32array, ARRAY_WORDS, 131072) == 0xac753e8); + ok1(hash_stable(u32array, ARRAY_WORDS, 262144) == 0xcd8bdd20); + ok1(hash_stable(u32array, ARRAY_WORDS, 524288) == 0xd44faf80); + ok1(hash_stable(u32array, ARRAY_WORDS, 1048576) == 0x2547ccbe); + ok1(hash_stable(u32array, ARRAY_WORDS, 2097152) == 0xbab06dbc); + ok1(hash_stable(u32array, ARRAY_WORDS, 4194304) == 0xaac0e882); + ok1(hash_stable(u32array, ARRAY_WORDS, 8388608) == 0x443f48d0); + ok1(hash_stable(u32array, ARRAY_WORDS, 16777216) == 0xdff49fcc); + ok1(hash_stable(u32array, ARRAY_WORDS, 33554432) == 0x9ce0fd65); + ok1(hash_stable(u32array, ARRAY_WORDS, 67108864) == 0x9ddb1def); + ok1(hash_stable(u32array, ARRAY_WORDS, 134217728) == 0x86096f25); + ok1(hash_stable(u32array, ARRAY_WORDS, 268435456) == 0xe713b7b5); + ok1(hash_stable(u32array, ARRAY_WORDS, 536870912) == 0x5baeffc5); + ok1(hash_stable(u32array, ARRAY_WORDS, 1073741824) == 0xde874f52); + ok1(hash_stable(u32array, ARRAY_WORDS, 2147483648U) == 0xeca13b4e); + + ok1(hash_stable(u64array, ARRAY_WORDS, 0) == 0x12ef6302); + ok1(hash_stable(u64array, ARRAY_WORDS, 1) == 0xe9aeb406); + ok1(hash_stable(u64array, ARRAY_WORDS, 2) == 0xc4218ceb); + ok1(hash_stable(u64array, ARRAY_WORDS, 4) == 0xb3d11412); + ok1(hash_stable(u64array, ARRAY_WORDS, 8) == 0xdafbd654); + ok1(hash_stable(u64array, ARRAY_WORDS, 16) == 0x9c336cba); + ok1(hash_stable(u64array, ARRAY_WORDS, 32) == 0x65059721); + ok1(hash_stable(u64array, ARRAY_WORDS, 64) == 0x95b5bbe6); + ok1(hash_stable(u64array, ARRAY_WORDS, 128) == 0xe7596b84); + ok1(hash_stable(u64array, ARRAY_WORDS, 256) == 0x503622a2); + ok1(hash_stable(u64array, ARRAY_WORDS, 512) == 0xecdcc5ca); + ok1(hash_stable(u64array, ARRAY_WORDS, 1024) == 0xc40d0513); + ok1(hash_stable(u64array, ARRAY_WORDS, 2048) == 0xaab25e4d); + ok1(hash_stable(u64array, ARRAY_WORDS, 4096) == 0xcc353fb9); + ok1(hash_stable(u64array, ARRAY_WORDS, 8192) == 0x18e2319f); + ok1(hash_stable(u64array, ARRAY_WORDS, 16384) == 0xfddaae8d); + ok1(hash_stable(u64array, ARRAY_WORDS, 32768) == 0xef7976f2); + ok1(hash_stable(u64array, ARRAY_WORDS, 65536) == 0x86359fc9); + ok1(hash_stable(u64array, ARRAY_WORDS, 131072) == 0x8b5af385); + ok1(hash_stable(u64array, ARRAY_WORDS, 262144) == 0x80d4ee31); + ok1(hash_stable(u64array, ARRAY_WORDS, 524288) == 0x42f5f85b); + ok1(hash_stable(u64array, ARRAY_WORDS, 1048576) == 0x9a6920e1); + ok1(hash_stable(u64array, ARRAY_WORDS, 2097152) == 0x7b7c9850); + ok1(hash_stable(u64array, ARRAY_WORDS, 4194304) == 0x69573e09); + ok1(hash_stable(u64array, ARRAY_WORDS, 8388608) == 0xc942bc0e); + ok1(hash_stable(u64array, ARRAY_WORDS, 16777216) == 0x7a89f0f1); + ok1(hash_stable(u64array, ARRAY_WORDS, 33554432) == 0x2dd641ca); + ok1(hash_stable(u64array, ARRAY_WORDS, 67108864) == 0x89bbd391); + ok1(hash_stable(u64array, ARRAY_WORDS, 134217728) == 0xbcf88e31); + ok1(hash_stable(u64array, ARRAY_WORDS, 268435456) == 0xfa7a3460); + ok1(hash_stable(u64array, ARRAY_WORDS, 536870912) == 0x49a37be0); + ok1(hash_stable(u64array, ARRAY_WORDS, 1073741824) == 0x1b346394); + ok1(hash_stable(u64array, ARRAY_WORDS, 2147483648U) == 0x6c3a1592); + + ok1(hash64_stable(u8array, ARRAY_WORDS, 0) == 16887282882572727244ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 1) == 12032777473133454818ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 2) == 18183407363221487738ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 4) == 17860764172704150171ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 8) == 18076051600675559233ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 16) == 9909361918431556721ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 32) == 12937969888744675813ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 64) == 5245669057381736951ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 128) == 4376874646406519665ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 256) == 14219974419871569521ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 512) == 2263415354134458951ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 1024) == 4953859694526221685ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 2048) == 3432228642067641593ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 4096) == 1219647244417697483ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 8192) == 7629939424585859553ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 16384) == 10041660531376789749ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 32768) == 13859885793922603927ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 65536) == 15069060338344675120ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 131072) == 818163430835601100ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 262144) == 14914314323019517069ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 524288) == 17518437749769352214ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 1048576) == 14920048004901212706ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 2097152) == 8758567366332536138ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 4194304) == 6226655736088907885ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 8388608) == 13716650013685832100ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 16777216) == 305325651636315638ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 33554432) == 16784147606583781671ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 67108864) == 16509467555140798205ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 134217728) == 8717281234694060584ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 268435456) == 8098476701725660537ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 536870912) == 16345871539461094006ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 1073741824) == 3755557000429964408ULL); + ok1(hash64_stable(u8array, ARRAY_WORDS, 2147483648U) == 15017348801959710081ULL); + + ok1(hash64_stable(u16array, ARRAY_WORDS, 0) == 1038028831307724039ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 1) == 10155473272642627302ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 2) == 5714751190106841420ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 4) == 3923885607767527866ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 8) == 3931017318293995558ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 16) == 1469696588339313177ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 32) == 11522218526952715051ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 64) == 6953517591561958496ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 128) == 7406689491740052867ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 256) == 10101844489704093104ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 512) == 12511348870707245959ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 1024) == 1614019938016861468ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 2048) == 5294796182374592721ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 4096) == 16089570706643716675ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 8192) == 1689302638424579464ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 16384) == 1446340172370386893ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 32768) == 16535503506744393039ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 65536) == 3496794142527150328ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 131072) == 6568245367474548504ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 262144) == 9487676460765485949ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 524288) == 4519762130966530000ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 1048576) == 15623412069215340610ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 2097152) == 544013388676438108ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 4194304) == 5594904760290840266ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 8388608) == 18098755780041592043ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 16777216) == 6389168672387330316ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 33554432) == 896986127732419381ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 67108864) == 13232626471143901354ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 134217728) == 53378562890493093ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 268435456) == 10072361400297824771ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 536870912) == 14511948118285144529ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 1073741824) == 6981033484844447277ULL); + ok1(hash64_stable(u16array, ARRAY_WORDS, 2147483648U) == 5619339091684126808ULL); + + ok1(hash64_stable(u32array, ARRAY_WORDS, 0) == 3037571077312110476ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 1) == 14732398743825071988ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 2) == 14949132158206672071ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 4) == 1291370080511561429ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 8) == 10792665964172133092ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 16) == 14250138032054339435ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 32) == 17136741522078732741ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 64) == 3260193403318236635ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 128) == 10526616652205653536ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 256) == 9019690373358576579ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 512) == 6997491436599677436ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 1024) == 18302783371416533798ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 2048) == 10149320644446516025ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 4096) == 7073759949410623868ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 8192) == 17442399482223760073ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 16384) == 2983906194216281861ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 32768) == 4975845419129060524ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 65536) == 594019910205413268ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 131072) == 11903010186073691112ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 262144) == 7339636527154847008ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 524288) == 15243305400579108736ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 1048576) == 16737926245392043198ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 2097152) == 15725083267699862972ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 4194304) == 12527834265678833794ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 8388608) == 13908436455987824848ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 16777216) == 9672773345173872588ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 33554432) == 2305314279896710501ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 67108864) == 1866733780381408751ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 134217728) == 11906263969465724709ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 268435456) == 5501594918093830069ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 536870912) == 15823785789276225477ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 1073741824) == 17353000723889475410ULL); + ok1(hash64_stable(u32array, ARRAY_WORDS, 2147483648U) == 7494736910655503182ULL); + + ok1(hash64_stable(u64array, ARRAY_WORDS, 0) == 9765419389786481410ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 1) == 11182806172127114246ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 2) == 2559155171395472619ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 4) == 3311692033324815378ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 8) == 1297175419505333844ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 16) == 617896928653569210ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 32) == 1517398559958603553ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 64) == 4504821917445110758ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 128) == 1971743331114904452ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 256) == 6177667912354374306ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 512) == 15570521289777792458ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 1024) == 9204559632415917331ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 2048) == 9008982669760028237ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 4096) == 14803537660281700281ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 8192) == 2873966517448487327ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 16384) == 5859277625928363661ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 32768) == 15520461285618185970ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 65536) == 16746489793331175369ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 131072) == 514952025484227461ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 262144) == 10867212269810675249ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 524288) == 9822204377278314587ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 1048576) == 3295088921987850465ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 2097152) == 7559197431498053712ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 4194304) == 1667267269116771849ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 8388608) == 2916804068951374862ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 16777216) == 14422558383125688561ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 33554432) == 10083112683694342602ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 67108864) == 7222777647078298513ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 134217728) == 18424513674048212529ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 268435456) == 14913668581101810784ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 536870912) == 14377721174297902048ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 1073741824) == 6031715005667500948ULL); + ok1(hash64_stable(u64array, ARRAY_WORDS, 2147483648U) == 4827100319722378642ULL); + + return exit_status(); +} diff --git a/lib/ccan/hash/test/run.c b/lib/ccan/hash/test/run.c new file mode 100644 index 0000000000..dad8e86b9e --- /dev/null +++ b/lib/ccan/hash/test/run.c @@ -0,0 +1,149 @@ +#include +#include +#include +#include +#include + +#define ARRAY_WORDS 5 + +int main(int argc, char *argv[]) +{ + unsigned int i, j, k; + uint32_t array[ARRAY_WORDS], val; + char array2[sizeof(array) + sizeof(uint32_t)]; + uint32_t results[256]; + + /* Initialize array. */ + for (i = 0; i < ARRAY_WORDS; i++) + array[i] = i; + + plan_tests(39); + /* Hash should be the same, indep of memory alignment. */ + val = hash(array, ARRAY_WORDS, 0); + for (i = 0; i < sizeof(uint32_t); i++) { + memcpy(array2 + i, array, sizeof(array)); + ok(hash(array2 + i, ARRAY_WORDS, 0) != val, + "hash matched at offset %i", i); + } + + /* Hash of random values should have random distribution: + * check one byte at a time. */ + for (i = 0; i < sizeof(uint32_t); i++) { + unsigned int lowest = -1U, highest = 0; + + memset(results, 0, sizeof(results)); + + for (j = 0; j < 256000; j++) { + for (k = 0; k < ARRAY_WORDS; k++) + array[k] = random(); + results[(hash(array, ARRAY_WORDS, 0) >> i*8)&0xFF]++; + } + + for (j = 0; j < 256; j++) { + if (results[j] < lowest) + lowest = results[j]; + if (results[j] > highest) + highest = results[j]; + } + /* Expect within 20% */ + ok(lowest > 800, "Byte %i lowest %i", i, lowest); + ok(highest < 1200, "Byte %i highest %i", i, highest); + diag("Byte %i, range %u-%u", i, lowest, highest); + } + + /* Hash of random values should have random distribution: + * check one byte at a time. */ + for (i = 0; i < sizeof(uint64_t); i++) { + unsigned int lowest = -1U, highest = 0; + + memset(results, 0, sizeof(results)); + + for (j = 0; j < 256000; j++) { + for (k = 0; k < ARRAY_WORDS; k++) + array[k] = random(); + results[(hash64(array, sizeof(array)/sizeof(uint64_t), + 0) >> i*8)&0xFF]++; + } + + for (j = 0; j < 256; j++) { + if (results[j] < lowest) + lowest = results[j]; + if (results[j] > highest) + highest = results[j]; + } + /* Expect within 20% */ + ok(lowest > 800, "Byte %i lowest %i", i, lowest); + ok(highest < 1200, "Byte %i highest %i", i, highest); + diag("Byte %i, range %u-%u", i, lowest, highest); + } + + /* Hash of pointer values should also have random distribution. */ + for (i = 0; i < sizeof(uint32_t); i++) { + unsigned int lowest = -1U, highest = 0; + char *p = malloc(256000); + + memset(results, 0, sizeof(results)); + + for (j = 0; j < 256000; j++) + results[(hash_pointer(p + j, 0) >> i*8)&0xFF]++; + free(p); + + for (j = 0; j < 256; j++) { + if (results[j] < lowest) + lowest = results[j]; + if (results[j] > highest) + highest = results[j]; + } + /* Expect within 20% */ + ok(lowest > 800, "hash_pointer byte %i lowest %i", i, lowest); + ok(highest < 1200, "hash_pointer byte %i highest %i", + i, highest); + diag("hash_pointer byte %i, range %u-%u", i, lowest, highest); + } + + if (sizeof(long) == sizeof(uint32_t)) + ok1(hashl(array, ARRAY_WORDS, 0) + == hash(array, ARRAY_WORDS, 0)); + else + ok1(hashl(array, ARRAY_WORDS, 0) + == hash64(array, ARRAY_WORDS, 0)); + + /* String hash: weak, so only test bottom byte */ + for (i = 0; i < 1; i++) { + unsigned int num = 0, cursor, lowest = -1U, highest = 0; + char p[5]; + + memset(results, 0, sizeof(results)); + + memset(p, 'A', sizeof(p)); + p[sizeof(p)-1] = '\0'; + + for (;;) { + for (cursor = 0; cursor < sizeof(p)-1; cursor++) { + p[cursor]++; + if (p[cursor] <= 'z') + break; + p[cursor] = 'A'; + } + if (cursor == sizeof(p)-1) + break; + + results[(hash_string(p) >> i*8)&0xFF]++; + num++; + } + + for (j = 0; j < 256; j++) { + if (results[j] < lowest) + lowest = results[j]; + if (results[j] > highest) + highest = results[j]; + } + /* Expect within 20% */ + ok(lowest > 35000, "hash_pointer byte %i lowest %i", i, lowest); + ok(highest < 53000, "hash_pointer byte %i highest %i", + i, highest); + diag("hash_pointer byte %i, range %u-%u", i, lowest, highest); + } + + return exit_status(); +} -- cgit