From 142afe327024262a0eaa0731bcf31def91c146e0 Mon Sep 17 00:00:00 2001 From: Rusty Russell Date: Thu, 26 Aug 2010 13:59:20 +0930 Subject: [PATCH] hash: 64-bit hash functions should take 64-bit base. --- ccan/hash/hash.c | 30 ++++++----- ccan/hash/hash.h | 137 +++++++++++++++++++++++------------------------ 2 files changed, 84 insertions(+), 83 deletions(-) diff --git a/ccan/hash/hash.c b/ccan/hash/hash.c index cb446540..9b3f58b2 100644 --- a/ccan/hash/hash.c +++ b/ccan/hash/hash.c @@ -543,13 +543,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 +582,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 +612,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 +648,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 +687,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 diff --git a/ccan/hash/hash.h b/ccan/hash/hash.h index 1c531cf9..1f8ccbf0 100644 --- a/ccan/hash/hash.h +++ b/ccan/hash/hash.h @@ -112,18 +112,6 @@ */ uint32_t hash_u32(const uint32_t *key, size_t num, uint32_t 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, uint32_t base); -uint64_t hash64_stable_64(const void *key, size_t n, uint32_t base); -uint64_t hash64_stable_32(const void *key, size_t n, uint32_t base); -uint64_t hash64_stable_16(const void *key, size_t n, uint32_t base); -uint64_t hash64_stable_8(const void *key, size_t n, uint32_t base); - /** * hash_string - very fast hash of an ascii string * @str: the nul-terminated string @@ -149,67 +137,11 @@ static inline uint32_t hash_string(const char *string) return ret; } -/** - * 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 "hash/hash.h" - * - * // 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); - * - * r->chain = region_hash[h]; - * region_hash[h] = r->chain; - * } - * - * static void find_region(const void *start) - * { - * struct region *r; - * - * for (r = region_hash[hash_pointer(start)]; 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); -} - /** * 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 base number to roll into the hash (usually 0) + * @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. @@ -306,4 +238,71 @@ static inline uint32_t hash_pointer(const void *p, uint32_t base) (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 "hash/hash.h" + * + * // 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); + * + * r->chain = region_hash[h]; + * region_hash[h] = r->chain; + * } + * + * static void find_region(const void *start) + * { + * struct region *r; + * + * for (r = region_hash[hash_pointer(start)]; 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 */ -- 2.39.2