hash: 64-bit hash functions should take 64-bit base.

diff --git a/ccan/hash/hash.c b/ccan/hash/hash.c
index cb4465405e2eff8022a014e0690583e6d16d9ac0..9b3f58b2b20a649785b7f053c4c7828413610148 100644 (file)
--- 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 1c531cf9edccd1f86c4298b19402246e261bfc22..1f8ccbf06212e3b3b7b98ce32ee07659c717a8df 100644 (file)
--- 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 */