Final final final Murmur3, all variants. I am tired of working on it. :)

Unified, simplified, optimized implementation that works well on all platforms and is easy to extend to larger/smaller hash sizes and streaming implementations if needed.

git-svn-id: http://smhasher.googlecode.com/svn/trunk@107 77a7d1d3-4c08-bdc2-d393-d5859734b01a

3 files changed, 113 insertions, 157 deletions

diff --git a/MurmurHash3.cpp b/MurmurHash3.cpp
index 33eb2e8..52c4043 100644
--- a/MurmurHash3.cpp
+++ b/MurmurHash3.cpp
@@ -1,3 +1,7 @@
+//-----------------------------------------------------------------------------

+// MurmurHash3 was written by Austin Appleby, and is placed in the public

+// domain. The author hereby disclaims copyright to this source code.

+

 #include "MurmurHash3.h"

 

 // Note - The x86 and x64 versions do _not_ produce the same results, as the

@@ -15,35 +19,97 @@ FORCE_INLINE uint32_t getblock ( const uint32_t * p, int i )
   return p[i];

 }

 

+FORCE_INLINE uint64_t getblock ( const uint64_t * p, int i )

+{

+  return p[i];

+}

+

+//-----------------------------------------------------------------------------

+// Block mix - mix the key block, combine with hash block, mix the hash block,

+// repeat.

+

+FORCE_INLINE void bmix ( uint32_t & h1, uint32_t & k1, 

+                         uint32_t & c1, uint32_t & c2 )

+{

+  k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;

+

+  h1 = ROTL32(h1,13); h1 = h1*5+0xe6546b64;

+}

+

 //----------

 

-FORCE_INLINE void bmix32 ( uint32_t & h1, uint32_t & k1, 

-                           uint32_t & c1, uint32_t & c2 )

+FORCE_INLINE void bmix ( uint64_t & h1, uint64_t & h2, 

+                         uint64_t & k1, uint64_t & k2, 

+                         uint64_t & c1, uint64_t & c2 )

 {

-  k1 *= c1; 

-  k1 = ROTL32(k1,16); 

-  k1 *= c2;

+  k1 *= c1; k1  = ROTL64(k1,31); k1 *= c2; h1 ^= k1;

 

-  h1 ^= k1;

-  h1 = h1*3+0x52dce729;

-  h1 = ROTL32(h1,15);

+  h1 = ROTL64(h1,27); h1 += h2; h1 = h1*5+0x52dce729;

+

+  k2 *= c2; k2  = ROTL64(k2,33); k2 *= c1; h2 ^= k2;

+

+  h2 = ROTL64(h2,31); h2 += h1; h2 = h2*5+0x38495ab5;

+}

+

+//----------

+

+FORCE_INLINE void bmix ( uint32_t & h1, uint32_t & h2,

+                         uint32_t & h3, uint32_t & h4, 

+                         uint32_t & k1, uint32_t & k2, 

+                         uint32_t & k3, uint32_t & k4,

+                         uint32_t & c1, uint32_t & c2, 

+                         uint32_t & c3, uint32_t & c4 )

+{

+  k1 *= c1; k1  = ROTL32(k1,15); k1 *= c2; h1 ^= k1;

+  k2 *= c2; k2  = ROTL32(k2,16); k2 *= c3; h2 ^= k2;

+  k3 *= c3; k3  = ROTL32(k3,17); k3 *= c4; h3 ^= k3;

+  k4 *= c4; k4  = ROTL32(k4,18); k4 *= c1; h4 ^= k4;

+

+  h1 = ROTL32(h1,19); h1 += h2; h1 = h1*5+0x561ccd1b;

+  h2 = ROTL32(h2,17); h2 += h3; h2 = h2*5+0x0bcaa747;

+  h3 = ROTL32(h3,15); h3 += h4; h3 = h3*5+0x96cd1c35;

+  h4 = ROTL32(h4,13); h4 += h1; h4 = h4*5+0x32ac3b17;

+}

+

+//-----------------------------------------------------------------------------

+// Finalization mix - force all bits of a hash block to avalanche

+

+FORCE_INLINE uint32_t fmix ( uint32_t h )

+{

+  h ^= h >> 16;

+  h *= 0x85ebca6b;

+  h ^= h >> 13;

+  h *= 0xc2b2ae35;

+  h ^= h >> 16;

 

-  c1 = c1*3+0x7b7d159c;

-  c2 = c2*3+0x6bce6396;

+  return h;

 }

 

 //----------

 

+FORCE_INLINE uint64_t fmix ( uint64_t k )

+{

+  k ^= k >> 33;

+  k *= BIG_CONSTANT(0xff51afd7ed558ccd);

+  k ^= k >> 33;

+  k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);

+  k ^= k >> 33;

+

+  return k;

+}

+

+//-----------------------------------------------------------------------------

+

 void MurmurHash3_x86_32 ( const void * key, int len,

                           uint32_t seed, void * out )

 {

   const uint8_t * data = (const uint8_t*)key;

   const int nblocks = len / 4;

 

-  uint32_t h1 = 0x971e137b ^ seed;

+  uint32_t h1 = seed;

 

-  uint32_t c1 = 0x95543787;

-  uint32_t c2 = 0x2ad7eb25;

+  uint32_t c1 = 0xcc9e2d51;

+  uint32_t c2 = 0x1b873593;

 

   //----------

   // body

@@ -54,7 +120,7 @@ void MurmurHash3_x86_32 ( const void * key, int len,
   {

     uint32_t k1 = getblock(blocks,i);

 

-    bmix32(h1,k1,c1,c2);

+    bmix(h1,k1,c1,c2);

   }

 

   //----------

@@ -69,7 +135,7 @@ void MurmurHash3_x86_32 ( const void * key, int len,
   case 3: k1 ^= tail[2] << 16;

   case 2: k1 ^= tail[1] << 8;

   case 1: k1 ^= tail[0];

-      bmix32(h1,k1,c1,c2);

+          k1 *= c1; k1 = ROTL32(k1,16); k1 *= c2; h1 ^= k1;

   };

 

   //----------

@@ -77,82 +143,12 @@ void MurmurHash3_x86_32 ( const void * key, int len,
 

   h1 ^= len;

 

-  h1 *= 0x85ebca6b;

-  h1 ^= h1 >> 13;

-  h1 *= 0xc2b2ae35;

-  h1 ^= h1 >> 16;

-

-  h1 ^= seed;

+  h1 = fmix(h1);

 

   *(uint32_t*)out = h1;

 } 

 

 //-----------------------------------------------------------------------------

-// x86 platforms don't have enough registers to do the c1/c2 mixing step

-// without spilling data onto the stack, so we use inline constants for this

-// block mix.

-

-FORCE_INLINE void bmix32 ( uint32_t & h1, uint32_t & h2,

-                           uint32_t & h3, uint32_t & h4, 

-                           uint32_t & k1, uint32_t & k2, 

-                           uint32_t & k3, uint32_t & k4 )

-{

-  k1 *= 0x239b961b; 

-  k1  = ROTL32(k1,15); 

-  k1 *= 0xab0e9789;

-

-  h1 ^= k1;

-  h1 = h1*3+0x561ccd1b;

-  h1 = ROTL32(h1,19);

-

-  k2 *= 0x38b34ae5; 

-  k2  = ROTL32(k2,16);

-  k2 *= 0xa1e38b93;

-

-  h2 ^= k2;

-  h2 = h2*3+0x0bcaa747;

-  h2 = ROTL32(h2,17);

-

-  k3 *= 0x4b2f1cc5; 

-  k3  = ROTL32(k3,17); 

-  k3 *= 0x8cd62ad3;

-

-  h3 ^= k3;

-  h3 = h3*3+0x96cd1c35;

-  h3 = ROTL32(h3,15);

-

-  k4 *= 0x561ad8f1; 

-  k4  = ROTL32(k4,18);

-  k4 *= 0xaac75299;

-

-  h4 ^= k4;

-  h4 = h4*3+0x32ac3b17;

-  h4 = ROTL32(h4,13);

-

-  h1 += h2;

-  h1 += h3;

-  h1 += h4;

-

-  h2 += h1;

-  h3 += h1;

-  h4 += h1;

-}

-

-//----------

-// Finalization mix - force all bits of a hash block to avalanche

-

-// avalanches all bits to within 0.25% bias

-

-FORCE_INLINE uint32_t fmix32 ( uint32_t h )

-{

-  h ^= h >> 16;

-  h *= 0x85ebca6b;

-  h ^= h >> 13;

-  h *= 0xc2b2ae35;

-  h ^= h >> 16;

-

-  return h;

-}

 

 void MurmurHash3_x86_128 ( const void * key, const int len,

                            uint32_t seed, void * out )

@@ -160,10 +156,15 @@ void MurmurHash3_x86_128 ( const void * key, const int len,
   const uint8_t * data = (const uint8_t*)key;

   const int nblocks = len / 16;

 

-  uint32_t h1 = 0x8de1c3ac ^ seed;

-  uint32_t h2 = 0xbab98226 ^ seed;

-  uint32_t h3 = 0xfcba5b2d ^ seed;

-  uint32_t h4 = 0x32452e3e ^ seed;

+  uint32_t h1 = seed;

+  uint32_t h2 = seed;

+  uint32_t h3 = seed;

+  uint32_t h4 = seed;

+

+  uint32_t c1 = 0x239b961b; 

+  uint32_t c2 = 0xab0e9789;

+  uint32_t c3 = 0x38b34ae5; 

+  uint32_t c4 = 0xa1e38b93;

 

   //----------

   // body

@@ -177,7 +178,7 @@ void MurmurHash3_x86_128 ( const void * key, const int len,
     uint32_t k3 = getblock(blocks,i*4+2);

     uint32_t k4 = getblock(blocks,i*4+3);

 

-    bmix32(h1,h2,h3,h4, k1,k2,k3,k4);

+    bmix(h1,h2,h3,h4, k1,k2,k3,k4, c1, c2, c3, c4);

   }

 

   //----------

@@ -195,22 +196,25 @@ void MurmurHash3_x86_128 ( const void * key, const int len,
   case 15: k4 ^= tail[14] << 16;

   case 14: k4 ^= tail[13] << 8;

   case 13: k4 ^= tail[12] << 0;

+           k4 *= c4; k4  = ROTL32(k4,18); k4 *= c1; h4 ^= k4;

 

   case 12: k3 ^= tail[11] << 24;

   case 11: k3 ^= tail[10] << 16;

   case 10: k3 ^= tail[ 9] << 8;

   case  9: k3 ^= tail[ 8] << 0;

+           k3 *= c3; k3  = ROTL32(k3,17); k3 *= c4; h3 ^= k3;

 

   case  8: k2 ^= tail[ 7] << 24;

   case  7: k2 ^= tail[ 6] << 16;

   case  6: k2 ^= tail[ 5] << 8;

   case  5: k2 ^= tail[ 4] << 0;

+           k2 *= c2; k2  = ROTL32(k2,16); k2 *= c3; h2 ^= k2;

 

   case  4: k1 ^= tail[ 3] << 24;

   case  3: k1 ^= tail[ 2] << 16;

   case  2: k1 ^= tail[ 1] << 8;

   case  1: k1 ^= tail[ 0] << 0;

-           bmix32(h1,h2,h3,h4, k1,k2,k3,k4);

+           k1 *= c1; k1  = ROTL32(k1,15); k1 *= c2; h1 ^= k1;

   };

 

   //----------

@@ -221,10 +225,10 @@ void MurmurHash3_x86_128 ( const void * key, const int len,
   h1 += h2; h1 += h3; h1 += h4;

   h2 += h1; h3 += h1; h4 += h1;

 

-  h1 = fmix32(h1);

-  h2 = fmix32(h2);

-  h3 = fmix32(h3);

-  h4 = fmix32(h4);

+  h1 = fmix(h1);

+  h2 = fmix(h2);

+  h3 = fmix(h3);

+  h4 = fmix(h4);

 

   h1 += h2; h1 += h3; h1 += h4;

   h2 += h1; h3 += h1; h4 += h1;

@@ -236,55 +240,6 @@ void MurmurHash3_x86_128 ( const void * key, const int len,
 }

 

 //-----------------------------------------------------------------------------

-// Block read - if your platform needs to do endian-swapping or can only

-// handle aligned reads, do the conversion here

-

-FORCE_INLINE uint64_t getblock ( const uint64_t * p, int i )

-{

-  return p[i];

-}

-

-//----------

-// Block mix - combine the key bits with the hash bits and scramble everything

-

-FORCE_INLINE void bmix64 ( uint64_t & h1, uint64_t & h2, 

-                           uint64_t & k1, uint64_t & k2, 

-                           uint64_t & c1, uint64_t & c2 )

-{

-  k1 *= c1; 

-  k1  = ROTL64(k1,29); 

-  k1 *= c2;

-

-  h1 ^= k1;

-  h1 = ROTL64(h1,27);

-  h1 += h2;

-  h1 = h1*3+0x52dce729;

-

-  k2 *= c2; 

-  k2  = ROTL64(k2,33);

-  k2 *= c1;

-

-  h2 ^= k2;

-  h2 = ROTL64(h2,31);

-  h2 += h1;

-  h2 = h2*3+0x38495ab5;

-}

-

-//----------

-// Finalization mix - avalanches all bits to within 0.05% bias

-

-FORCE_INLINE uint64_t fmix64 ( uint64_t k )

-{

-  k ^= k >> 33;

-  k *= BIG_CONSTANT(0xff51afd7ed558ccd);

-  k ^= k >> 33;

-  k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);

-  k ^= k >> 33;

-

-  return k;

-}

-

-//----------

 

 void MurmurHash3_x64_128 ( const void * key, const int len,

                            const uint32_t seed, void * out )

@@ -292,8 +247,8 @@ void MurmurHash3_x64_128 ( const void * key, const int len,
   const uint8_t * data = (const uint8_t*)key;

   const int nblocks = len / 16;

 

-  uint64_t h1 = BIG_CONSTANT(0x9368e53c2f6af274) ^ seed;

-  uint64_t h2 = BIG_CONSTANT(0x586dcd208f7cd3fd) ^ seed;

+  uint64_t h1 = seed;

+  uint64_t h2 = seed;

 

   uint64_t c1 = BIG_CONSTANT(0x87c37b91114253d5);

   uint64_t c2 = BIG_CONSTANT(0x4cf5ad432745937f);

@@ -308,7 +263,7 @@ void MurmurHash3_x64_128 ( const void * key, const int len,
     uint64_t k1 = getblock(blocks,i*2+0);

     uint64_t k2 = getblock(blocks,i*2+1);

 

-    bmix64(h1,h2,k1,k2,c1,c2);

+    bmix(h1,h2,k1,k2,c1,c2);

   }

 

   //----------

@@ -328,6 +283,7 @@ void MurmurHash3_x64_128 ( const void * key, const int len,
   case 11: k2 ^= uint64_t(tail[10]) << 16;

   case 10: k2 ^= uint64_t(tail[ 9]) << 8;

   case  9: k2 ^= uint64_t(tail[ 8]) << 0;

+           k2 *= c2; k2  = ROTL64(k2,33); k2 *= c1; h2 ^= k2;

 

   case  8: k1 ^= uint64_t(tail[ 7]) << 56;

   case  7: k1 ^= uint64_t(tail[ 6]) << 48;

@@ -337,7 +293,7 @@ void MurmurHash3_x64_128 ( const void * key, const int len,
   case  3: k1 ^= uint64_t(tail[ 2]) << 16;

   case  2: k1 ^= uint64_t(tail[ 1]) << 8;

   case  1: k1 ^= uint64_t(tail[ 0]) << 0;

-           bmix64(h1,h2,k1,k2,c1,c2);

+           k1 *= c1; k1  = ROTL64(k1,29); k1 *= c2; h1 ^= k1;

   };

 

   //----------

@@ -348,8 +304,8 @@ void MurmurHash3_x64_128 ( const void * key, const int len,
   h1 += h2;

   h2 += h1;

 

-  h1 = fmix64(h1);

-  h2 = fmix64(h2);

+  h1 = fmix(h1);

+  h2 = fmix(h2);

 

   h1 += h2;

   h2 += h1;

diff --git a/SpeedTest.cpp b/SpeedTest.cpp
index a450c53..d0bba8b 100644
--- a/SpeedTest.cpp
+++ b/SpeedTest.cpp
@@ -58,7 +58,7 @@ void BulkSpeedTest ( pfHash hash, uint32_t seed )
 

 void TinySpeedTest ( pfHash hash, int hashsize, int keysize, uint32_t seed, bool verbose, double & outCycles )

 {

-  const int trials = 100000;

+  const int trials = 300000;

 

   if(verbose) printf("Small key speed test - %4d-byte keys - ",keysize);

   

diff --git a/main.cpp b/main.cpp
index 5f8921f..4574015 100644
--- a/main.cpp
+++ b/main.cpp
@@ -66,9 +66,9 @@ HashInfo g_hashes[] =
 

   // MurmurHash3

 

-  { MurmurHash3_x86_32,   32, 0xCB75A3F6, "Murmur3A",    "MurmurHash3 for x86, 32-bit" },

-  { MurmurHash3_x86_128, 128, 0x917EC4EF, "Murmur3C",    "MurmurHash3 for x86, 128-bit" },

-  { MurmurHash3_x64_128, 128, 0x9E20536F, "Murmur3F",    "MurmurHash3 for x64, 128-bit" },

+  { MurmurHash3_x86_32,   32, 0x3252D141, "Murmur3A",    "MurmurHash3 for x86, 32-bit" },

+  { MurmurHash3_x86_128, 128, 0x13C7ED69, "Murmur3C",    "MurmurHash3 for x86, 128-bit" },

+  { MurmurHash3_x64_128, 128, 0x33949085, "Murmur3F",    "MurmurHash3 for x64, 128-bit" },

 

 };

 

@@ -119,7 +119,7 @@ void test ( hashfunc<hashtype> hash, HashInfo * info )
   const int hashbits = sizeof(hashtype) * 8;

 

   printf("-------------------------------------------------------------------------------\n");

-  printf("--- Testing %s\n\n",info->name);

+  printf("--- Testing %s (%s)\n\n",info->name,info->desc);

 

   //-----------------------------------------------------------------------------

   // Sanity tests

@@ -538,7 +538,7 @@ void testHash ( const char * name )
 

 int main ( int argc, char ** argv )

 {

-  const char * hashToTest = "murmur3f";

+  const char * hashToTest = "murmur3a";

 

   if(argc < 2)

   {