simpler block mix for murmur3c

add mix-constant-generator code
tweak constants for 3c and 3f

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

2 files changed, 157 insertions, 45 deletions

diff --git a/MurmurHash3.cpp b/MurmurHash3.cpp
index 28aa6a0..8334435 100644
--- a/MurmurHash3.cpp
+++ b/MurmurHash3.cpp
@@ -88,54 +88,54 @@ void MurmurHash3_x86_32 ( const void * key, int len,
 } 

 

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

-// This mix is large enough that VC++ refuses to inline it unless we use

-// __forceinline. It's also not all that fast due to register spillage.

+// 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, 

-                           uint32_t & c1, uint32_t & c2 )

+                           uint32_t & k3, uint32_t & k4 )

 {

-  k1 *= c1; 

-  k1  = ROTL32(k1,11); 

-  k1 *= c2;

+  k1 *= 0x239b961b; 

+  k1  = ROTL32(k1,15); 

+  k1 *= 0xab0e9789;

+

   h1 ^= k1;

-  h1 += h2;

-  h1 += h3;

-  h1 += h4;

+  h1 = h1*3+0x561ccd1b;

+  h1 = ROTL32(h1,19);

 

-  h1 = ROTL32(h1,17);

+  k2 *= 0x38b34ae5; 

+  k2  = ROTL32(k2,16);

+  k2 *= 0xa1e38b93;

 

-  k2 *= c2; 

-  k2  = ROTL32(k2,11);

-  k2 *= c1;

   h2 ^= k2;

-  h2 += h1;

+  h2 = h2*3+0x0bcaa747;

+  h2 = ROTL32(h2,17);

 

-  h1 = h1*3+0x52dce729;

-  h2 = h2*3+0x38495ab5;

+  k3 *= 0x4b2f1cc5; 

+  k3  = ROTL32(k3,17); 

+  k3 *= 0x8cd62ad3;

 

-  c1 = c1*5+0x7b7d159c;

-  c2 = c2*5+0x6bce6396;

-

-  k3 *= c1; 

-  k3  = ROTL32(k3,11); 

-  k3 *= c2;

   h3 ^= k3;

-  h3 += h1;

+  h3 = h3*3+0x96cd1c35;

+  h3 = ROTL32(h3,15);

+

+  k4 *= 0x561ad8f1; 

+  k4  = ROTL32(k4,18);

+  k4 *= 0xaac75299;

 

-  k4 *= c2; 

-  k4  = ROTL32(k4,11);

-  k4 *= c1;

   h4 ^= k4;

-  h4 += h1;

+  h4 = h4*3+0x32ac3b17;

+  h4 = ROTL32(h4,13);

 

-  h3 = h3*3+0x52dce729;

-  h4 = h4*3+0x38495ab5;

+  h1 += h2;

+  h1 += h3;

+  h1 += h4;

 

-  c1 = c1*5+0x7b7d159c;

-  c2 = c2*5+0x6bce6396;

+  h2 += h1;

+  h3 += h1;

+  h4 += h1;

 }

 

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

@@ -165,22 +165,19 @@ void MurmurHash3_x86_128 ( const void * key, const int len,
   uint32_t h3 = 0xfcba5b2d ^ seed;

   uint32_t h4 = 0x32452e3e ^ seed;

 

-  uint32_t c1 = 0x95543787;

-  uint32_t c2 = 0x2ad7eb25;

-

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

   // body

 

-  const uint32_t * blocks = (const uint32_t *)(data);

+  const uint32_t * blocks = (const uint32_t *)(data + nblocks*16);

 

-  for(int i = 0; i < nblocks; i++)

+  for(int i = -nblocks; i; i++)

   {

     uint32_t k1 = getblock(blocks,i*4+0);

     uint32_t k2 = getblock(blocks,i*4+1);

     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, c1,c2);

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

   }

 

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

@@ -213,7 +210,7 @@ void MurmurHash3_x86_128 ( const void * key, const int len,
   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, c1,c2);

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

   };

 

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

@@ -255,26 +252,26 @@ FORCE_INLINE void bmix64 ( uint64_t & h1, uint64_t & h2,
                            uint64_t & c1, uint64_t & c2 )

 {

   k1 *= c1; 

-  k1  = ROTL64(k1,23); 

+  k1  = ROTL64(k1,29); 

   k1 *= c2;

 

   k2 *= c2; 

-  k2  = ROTL64(k2,23);

+  k2  = ROTL64(k2,33);

   k2 *= c1;

 

-  h1 = ROTL64(h1,17);

+  h1 = ROTL64(h1,27);

   h1 += h2;

   h1 ^= k1;

 

-  h2 = ROTL64(h2,41);

+  h2 = ROTL64(h2,31);

   h2 += h1;

   h2 ^= k2;

 

   h1 = h1*3+0x52dce729;

   h2 = h2*3+0x38495ab5;

 

-  c1 = c1*5+0x7b7d159c;

-  c2 = c2*5+0x6bce6396;

+  c1 = c1*3+0x7b7d159c;

+  c2 = c2*3+0x6bce6396;

 }

 

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

diff --git a/Types.cpp b/Types.cpp
index 91b617c..34f5e88 100644
--- a/Types.cpp
+++ b/Types.cpp
@@ -1,5 +1,7 @@
 #include "Types.h"

 

+#include "Random.h"

+

 uint32_t MurmurOAAT ( const void * blob, int len, uint32_t seed );

 

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

@@ -25,3 +27,116 @@ void MixVCode ( const void * blob, int len )
 }

 

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

+

+bool isprime ( uint32_t x )

+{

+  uint32_t p[] = 

+  {

+    2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,

+    103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,

+    199,211,223,227,229,233,239,241,251

+  };

+

+  for(int i=0; i < sizeof(p)/sizeof(uint32_t); i++)

+  { 

+    if((x % p[i]) == 0)

+    {

+      return false;

+    }

+  } 

+

+  for(int i = 257; i < 65536; i += 2) 

+  { 

+    if((x % i) == 0)

+    {

+      return false;

+    }

+  }

+

+  return true;

+}

+

+void GenerateMixingConstants ( void )

+{

+  Rand r(8350147);

+

+  int count = 0;

+

+  int trials = 0;

+  int bitfail = 0;

+  int popfail = 0;

+  int matchfail = 0;

+  int primefail = 0;

+

+  //for(uint32_t x = 1; x; x++)

+  while(count < 100)

+  {

+    //if(x % 100000000 == 0) printf(".");

+

+    trials++;

+    uint32_t b = r.rand_u32();

+    //uint32_t b = x;

+

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

+    // must have between 14 and 18 set bits

+

+    if(popcount(b) < 16) { b = 0; popfail++; }

+    if(popcount(b) > 16) { b = 0; popfail++; }

+

+    if(b == 0) continue;

+

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

+    // must have 3-5 bits set per 8-bit window

+

+    for(int i = 0; i < 32; i++)

+    {

+      uint32_t c = ROTL32(b,i) & 0xFF;

+

+      if(popcount(c) < 3) { b = 0; bitfail++; break; }

+      if(popcount(c) > 5) { b = 0; bitfail++; break; }

+    }

+

+    if(b == 0) continue;

+

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

+    // all 8-bit windows must be different

+

+    uint8_t match[256];

+

+    memset(match,0,256);

+

+    for(int i = 0; i < 32; i++)

+    {

+      uint32_t c = ROTL32(b,i) & 0xFF;

+      

+      if(match[c]) { b = 0; matchfail++; break; }

+

+      match[c] = 1;

+    }

+

+    if(b == 0) continue;

+

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

+    // must be prime

+

+    if(!isprime(b))

+    {

+      b = 0;

+      primefail++;

+    }

+

+    if(b == 0) continue;

+

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

+

+    if(b)

+    {

+      printf("0x%08x : 0x%08x\n",b,~b);

+      count++;

+    }

+  }

+

+  printf("%d %d %d %d %d %d\n",trials,popfail,bitfail,matchfail,primefail,count);

+}

+

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