hash: switch to CC0 license.
[ccan] / ccan / hash / hash.c
index cb4465405e2eff8022a014e0690583e6d16d9ac0..5ccc695505e76929cffccc7a4f5dbbde44e7f72d 100644 (file)
@@ -1,3 +1,4 @@
+/* CC0 (Public domain) - see LICENSE file for details */
 /*
 -------------------------------------------------------------------------------
 lookup3.c, by Bob Jenkins, May 2006, Public Domain.
@@ -40,9 +41,7 @@ on 1 byte), but shoehorning those bytes into integers efficiently is messy.
 #include <time.h>       /* defines time_t for timings in the test */
 #include <stdint.h>     /* defines uint32_t etc */
 #include <sys/param.h>  /* attempt to define endianness */
-#endif
 
-#include "hash.h"
 #ifdef linux
 # include <endian.h>    /* attempt to define endianness */
 #endif
@@ -54,7 +53,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 +65,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 +260,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 +282,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 +437,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 +459,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 +554,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 +593,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 +623,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 +659,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 +698,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 +752,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<HASHSTATE; ++l)
            e[l]=f[l]=g[l]=h[l]=x[l]=y[l]=~((uint32_t)0);