X-Git-Url: http://git.ozlabs.org/?p=ccan;a=blobdiff_plain;f=ccan%2Fhash%2Fhash.c;h=59c4d24b3b989013a6ef7004f99e62151dc6ebfc;hp=cb4465405e2eff8022a014e0690583e6d16d9ac0;hb=926996e88c32445c874ff9c4f47f159db6b45995;hpb=7449ae0ff0ef5c96b7a76010986e00ebb28b2a65 diff --git a/ccan/hash/hash.c b/ccan/hash/hash.c index cb446540..59c4d24b 100644 --- a/ccan/hash/hash.c +++ b/ccan/hash/hash.c @@ -40,9 +40,7 @@ on 1 byte), but shoehorning those bytes into integers efficiently is messy. #include /* defines time_t for timings in the test */ #include /* defines uint32_t etc */ #include /* attempt to define endianness */ -#endif -#include "hash.h" #ifdef linux # include /* attempt to define endianness */ #endif @@ -54,7 +52,8 @@ on 1 byte), but shoehorning those bytes into integers efficiently is messy. #if (defined(__BYTE_ORDER) && defined(__LITTLE_ENDIAN) && \ __BYTE_ORDER == __LITTLE_ENDIAN) || \ (defined(i386) || defined(__i386__) || defined(__i486__) || \ - defined(__i586__) || defined(__i686__) || defined(vax) || defined(MIPSEL)) + 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) && \ @@ -65,6 +64,19 @@ on 1 byte), but shoehorning those bytes into integers efficiently is messy. #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) @@ -247,9 +259,7 @@ static uint32_t hashlittle( const void *key, size_t length, uint32_t *val2 ) u.ptr = key; if (HASH_LITTLE_ENDIAN && ((u.i & 0x3) == 0)) { const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ -#ifdef VALGRIND const uint8_t *k8; -#endif /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ while (length > 12) @@ -271,9 +281,10 @@ static uint32_t hashlittle( const void *key, size_t length, uint32_t *val2 ) * 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. */ -#ifndef VALGRIND - +#if 0 switch(length) { case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; @@ -425,9 +436,7 @@ static uint32_t hashbig( const void *key, size_t length, uint32_t *val2) u.ptr = key; if (HASH_BIG_ENDIAN && ((u.i & 0x3) == 0)) { const uint32_t *k = (const uint32_t *)key; /* read 32-bit chunks */ -#ifdef VALGRIND const uint8_t *k8; -#endif /*------ all but last block: aligned reads and affect 32 bits of (a,b,c) */ while (length > 12) @@ -449,9 +458,10 @@ static uint32_t hashbig( const void *key, size_t length, uint32_t *val2) * 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. */ -#ifndef VALGRIND - +#if 0 switch(length) { case 12: c+=k[2]; b+=k[1]; a+=k[0]; break; @@ -543,13 +553,13 @@ static uint32_t hashbig( const void *key, size_t length, uint32_t *val2) * 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, uint32_t base) +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; + a = b = c = 0xdeadbeef + ((uint32_t)n*8) + (base >> 32) + base; while (n > 3) { a += (uint32_t)k[0]; @@ -582,13 +592,13 @@ uint64_t hash64_stable_64(const void *key, size_t n, uint32_t base) return ((uint64_t)b << 32) | c; } -uint64_t hash64_stable_32(const void *key, size_t n, uint32_t base) +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; + a = b = c = 0xdeadbeef + ((uint32_t)n*4) + (base >> 32) + base; while (n > 3) { a += k[0]; @@ -612,13 +622,13 @@ uint64_t hash64_stable_32(const void *key, size_t n, uint32_t base) return ((uint64_t)b << 32) | c; } -uint64_t hash64_stable_16(const void *key, size_t n, uint32_t base) +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; + a = b = c = 0xdeadbeef + ((uint32_t)n*2) + (base >> 32) + base; while (n > 6) { a += (uint32_t)k[0] + ((uint32_t)k[1] << 16); @@ -648,12 +658,13 @@ uint64_t hash64_stable_16(const void *key, size_t n, uint32_t base) final(a,b,c); return ((uint64_t)b << 32) | c; } - -uint64_t hash64_stable_8(const void *key, size_t n, uint32_t base) + +uint64_t hash64_stable_8(const void *key, size_t n, uint64_t base) { - uint32_t lower = hashlittle(key, n, &base); + uint32_t b32 = base + (base >> 32); + uint32_t lower = hashlittle(key, n, &b32); - return ((uint64_t)base << 32) | lower; + return ((uint64_t)b32 << 32) | lower; } uint32_t hash_any(const void *key, size_t length, uint32_t base) @@ -686,16 +697,17 @@ uint32_t hash_stable_8(const void *key, size_t n, uint32_t 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, uint32_t base) +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, &base); + lower = hashbig(key, length, &b32); else - lower = hashlittle(key, length, &base); + lower = hashlittle(key, length, &b32); - return ((uint64_t)base << 32) | lower; + return ((uint64_t)b32 << 32) | lower; } #ifdef SELF_TEST @@ -739,7 +751,7 @@ void driver2() { for (j=0; j<8; ++j) /*------------------------ for each input bit, */ { - for (m=1; m<8; ++m) /*------------ for serveral possible initvals, */ + for (m=1; m<8; ++m) /*------------ for several possible initvals, */ { for (l=0; l