Add MurmurHash64A and MurmurHash64B to hv_func.h

Both of these hash functions are by Austin Appleby and are in the public domain.

The 64A variant is designed for 64 bit machines.

The 64B variant is designed for 32 bit machines.

Both use unaligned loads, so are unsuitable for platforms with strict alignment requirements.

Both have been converted to use Perls hash function calling conventions,
and to return a 32 bit hash instead of a 64 bit hash (low 32 bits)

1 files changed, 138 insertions, 0 deletions

diff --git a/hv_func.h b/hv_func.h
index 1923f3ec20..b3eea0071f 100644
--- a/hv_func.h
+++ b/hv_func.h
@@ -21,6 +21,8 @@
         || defined(PERL_HASH_FUNC_ONE_AT_A_TIME) \
         || defined(PERL_HASH_FUNC_ONE_AT_A_TIME_HARD) \
         || defined(PERL_HASH_FUNC_ONE_AT_A_TIME_OLD) \
+        || defined(PERL_HASH_FUNC_MURMUR_HASH_64A) \
+        || defined(PERL_HASH_FUNC_MURMUR_HASH_64B) \
     )
 #define PERL_HASH_FUNC_ONE_AT_A_TIME_HARD
 #endif
@@ -57,6 +59,14 @@
 #   define PERL_HASH_FUNC "ONE_AT_A_TIME_OLD"
 #   define PERL_HASH_SEED_BYTES 4
 #   define PERL_HASH_WITH_SEED(seed,hash,str,len) (hash)= S_perl_hash_old_one_at_a_time((seed),(U8*)(str),(len))
+#elif defined(PERL_HASH_FUNC_MURMUR_HASH_64A)
+#   define PERL_HASH_FUNC "MURMUR_HASH_64A"
+#   define PERL_HASH_SEED_BYTES 8
+#   define PERL_HASH_WITH_SEED(seed,hash,str,len) (hash)= S_perl_hash_murmur_hash_64a((seed),(U8*)(str),(len))
+#elif defined(PERL_HASH_FUNC_MURMUR_HASH_64B)
+#   define PERL_HASH_FUNC "MURMUR_HASH_64B"
+#   define PERL_HASH_SEED_BYTES 8
+#   define PERL_HASH_WITH_SEED(seed,hash,str,len) (hash)= S_perl_hash_murmur_hash_64b((seed),(U8*)(str),(len))
 #endif
 
 #ifndef PERL_HASH_WITH_SEED
@@ -554,6 +564,134 @@ S_perl_hash_old_one_at_a_time(const unsigned char * const seed, const unsigned c
     return (hash + (hash << 15));
 }
 
+#ifdef PERL_HASH_FUNC_MURMUR_HASH_64A
+/* This code is from Austin Appleby and is in the public domain.
+   Altered by Yves Orton to match Perl's hash interface, and to
+   return a 32 bit hash.
+
+   Note uses unaligned 64 bit loads - will NOT work on machines with
+   strict alginment requirements.
+
+   Also this code may not be suitable for big-endian machines.
+*/
+
+/* a 64 bit hash where we only use the low 32 bits */
+PERL_STATIC_INLINE U32
+S_perl_hash_murmur_hash_64a (const unsigned char * const seed, const unsigned char *str, const STRLEN len)
+{
+        const U64TYPE m = 0xc6a4a7935bd1e995;
+        const int r = 47;
+        U64TYPE h = *((U64TYPE*)seed) ^ len;
+        const U64TYPE * data = (const U64TYPE *)str;
+        const U64TYPE * end = data + (len/8);
+        const unsigned char * data2;
+
+        while(data != end)
+        {
+            U64TYPE k = *data++;
+
+            k *= m;
+            k ^= k >> r;
+            k *= m;
+
+            h ^= k;
+            h *= m;
+        }
+
+        data2 = (const unsigned char *)data;
+
+        switch(len & 7)
+        {
+            case 7: h ^= (U64TYPE)(data2[6]) << 48; /* fallthrough */
+            case 6: h ^= (U64TYPE)(data2[5]) << 40; /* fallthrough */
+            case 5: h ^= (U64TYPE)(data2[4]) << 32; /* fallthrough */
+            case 4: h ^= (U64TYPE)(data2[3]) << 24; /* fallthrough */
+            case 3: h ^= (U64TYPE)(data2[2]) << 16; /* fallthrough */
+            case 2: h ^= (U64TYPE)(data2[1]) << 8;  /* fallthrough */
+            case 1: h ^= (U64TYPE)(data2[0]);       /* fallthrough */
+                    h *= m;
+        };
+
+        h ^= h >> r;
+        h *= m;
+        h ^= h >> r;
+
+        /* was: return h; */
+        return h & 0xFFFFFFFF;
+}
+
+#endif
+
+#ifdef PERL_HASH_FUNC_MURMUR_HASH_64B
+/* This code is from Austin Appleby and is in the public domain.
+   Altered by Yves Orton to match Perl's hash interface and return
+   a 32 bit value
+
+   Note uses unaligned 32 bit loads - will NOT work on machines with
+   strict alginment requirements.
+
+   Also this code may not be suitable for big-endian machines.
+*/
+
+/* a 64-bit hash for 32-bit platforms where we only use the low 32 bits */
+PERL_STATIC_INLINE U32
+S_perl_hash_murmur_hash_64b (const unsigned char * const seed, const unsigned char *str, STRLEN len)
+{
+        const U32 m = 0x5bd1e995;
+        const int r = 24;
+
+        U32 h1 = ((U32 *)seed)[0] ^ len;
+        U32 h2 = ((U32 *)seed)[1];
+
+        const U32 * data = (const U32 *)str;
+
+        while(len >= 8)
+        {
+            U32 k1, k2;
+            k1 = *data++;
+            k1 *= m; k1 ^= k1 >> r; k1 *= m;
+            h1 *= m; h1 ^= k1;
+            len -= 4;
+
+            k2 = *data++;
+            k2 *= m; k2 ^= k2 >> r; k2 *= m;
+            h2 *= m; h2 ^= k2;
+            len -= 4;
+        }
+
+        if(len >= 4)
+        {
+            U32 k1 = *data++;
+            k1 *= m; k1 ^= k1 >> r; k1 *= m;
+            h1 *= m; h1 ^= k1;
+            len -= 4;
+        }
+
+        switch(len)
+        {
+            case 3: h2 ^= ((unsigned char*)data)[2] << 16;  /* fallthrough */
+            case 2: h2 ^= ((unsigned char*)data)[1] << 8;   /* fallthrough */
+            case 1: h2 ^= ((unsigned char*)data)[0];        /* fallthrough */
+                    h2 *= m;
+        };
+
+        h1 ^= h2 >> 18; h1 *= m;
+        h2 ^= h1 >> 22; h2 *= m;
+        /*
+        The following code has been removed as it is unused
+        when only the low 32 bits are used. -- Yves
+
+        h1 ^= h2 >> 17; h1 *= m;
+
+        U64TYPE h = h1;
+
+        h = (h << 32) | h2;
+        */
+
+        return h2;
+}
+#endif
+
 /* legacy - only mod_perl should be doing this.  */
 #ifdef PERL_HASH_INTERNAL_ACCESS
 #define PERL_HASH_INTERNAL(hash,str,len) PERL_HASH(hash,str,len)