Subject: [PATCH 2/5] st.c: seed st hash from random.c

From: Sokolov Yura aka funny_falcon <[email-masked]>
Date: Fri, 4 Nov 2016 12:48:03 +0300

Main Murmur weakness is permutation of a block without seed,
and simple interblock dependency.
We fix it in following way:
- add random seed to each block
- carefully choose rotates, so high bits of consecutive blocks are
  far from each other (were done in previous commit).
  High bits are not sensitive to seed, so we need to ensure they
  can't canceled each other.
- final block is mixed in stronger way.
- add random seed to finalization
---
 include/ruby/intern.h |  1 +
 include/ruby/st.h     |  3 ++-
 random.c              | 30 ++++++++++--------------------
 st.c                  | 29 +++++++++++++++++++++--------
 4 files changed, 34 insertions(+), 29 deletions(-)

diff --git a/include/ruby/intern.h b/include/ruby/intern.h
index efa8f40..057266c 100644
--- a/include/ruby/intern.h
+++ b/include/ruby/intern.h
@@ -763,6 +763,7 @@ st_index_t rb_hash_start(st_index_t);
 st_index_t rb_hash_uint32(st_index_t, uint32_t);
 st_index_t rb_hash_uint(st_index_t, st_index_t);
 st_index_t rb_hash_end(st_index_t);
+#define rb_hash_start(h) st_hash_start((h))
 #define rb_hash_uint32(h, i) st_hash_uint32((h), (i))
 #define rb_hash_uint(h, i) st_hash_uint((h), (i))
 #define rb_hash_end(h) st_hash_end(h)
diff --git a/include/ruby/st.h b/include/ruby/st.h
index 1843f0d..2e2d5a3 100644
--- a/include/ruby/st.h
+++ b/include/ruby/st.h
@@ -143,7 +143,8 @@ CONSTFUNC(st_index_t st_hash_uint32(st_index_t h, uint32_t i));
 CONSTFUNC(st_index_t st_hash_uint(st_index_t h, st_index_t i));
 CONSTFUNC(st_index_t st_hash_end(st_index_t h));
 CONSTFUNC(st_index_t st_hash_start(st_index_t h));
-#define st_hash_start(h) ((st_index_t)(h))
+void st_hash_seed(st_index_t seed[3]); /* init global seed */
+
 
 RUBY_SYMBOL_EXPORT_END
 
diff --git a/random.c b/random.c
index ee91c53..40031a3 100644
--- a/random.c
+++ b/random.c
@@ -1473,7 +1473,6 @@ random_s_rand(int argc, VALUE *argv, VALUE obj)
 #endif
 #include "siphash.c"
 
-static st_index_t hashseed;
 typedef uint8_t sipseed_keys_t[16];
 static union {
     sipseed_keys_t key;
@@ -1483,19 +1482,16 @@ static union {
 static void
 init_hashseed(struct MT *mt)
 {
-    hashseed = genrand_int32(mt);
-#if SIZEOF_ST_INDEX_T*CHAR_BIT > 4*8
-    hashseed <<= 32;
-    hashseed |= genrand_int32(mt);
-#endif
-#if SIZEOF_ST_INDEX_T*CHAR_BIT > 8*8
-    hashseed <<= 32;
-    hashseed |= genrand_int32(mt);
-#endif
-#if SIZEOF_ST_INDEX_T*CHAR_BIT > 12*8
-    hashseed <<= 32;
-    hashseed |= genrand_int32(mt);
-#endif
+    st_index_t hashseed[3];
+    int i,b;
+    for (i = 0; i < 3; i++) {
+	hashseed[i] = genrand_int32(mt);
+	for (b = ST_INDEX_BITS - 32; b > 0; b -= 32) {
+	    hashseed[i] <<= 32;
+	    hashseed[i] |= genrand_int32(mt);
+	}
+    }
+    st_hash_seed(hashseed);
 }
 
 static void
@@ -1508,12 +1504,6 @@ init_siphash(struct MT *mt)
 }
 
 st_index_t
-rb_hash_start(st_index_t h)
-{
-    return st_hash_start(hashseed + h);
-}
-
-st_index_t
 rb_memhash(const void *ptr, long len)
 {
     sip_uint64_t h = sip_hash24(sipseed.key, ptr, len);
diff --git a/st.c b/st.c
index 515e4f0..f343a12 100644
--- a/st.c
+++ b/st.c
@@ -1281,6 +1281,18 @@ st_reverse_foreach(st_table *table, int (*func)(ANYARGS), st_data_t arg)
 }
 #endif
 
+static st_index_t st_seed[3];
+static int st_need_seed = 1;
+void
+st_hash_seed(st_index_t seed[3])
+{
+    assert(st_need_seed);
+    st_seed[0] = seed[0];
+    st_seed[1] = seed[1];
+    st_seed[2] = seed[2];
+    st_need_seed = 0;
+}
+
 #define FNV1_32A_INIT 0x811c9dc5
 
 /*
@@ -1319,16 +1331,15 @@ murmur_step(st_index_t h, st_index_t k)
 #if ST_INDEX_BITS <= 32
 #define r1 (15)
 #define r2 (11)
-#define a 0xe6546b64;
 #else
 #define r1 (31)
 #define r2 (23)
-#define a BIG_CONSTANT(0xe6546b64,0x38495ab5);
 #endif
+    k ^= st_seed[1];
     k *= C1;
     k = ROTL(k, r1);
     h += k;
-    h = h*9 + a;
+    h = h*9 + st_seed[2];
     h = ROTL(h, r2);
     return h;
 }
@@ -1352,6 +1363,7 @@ murmur_finish(st_index_t h)
     const st_index_t c1 = BIG_CONSTANT(0xbf58476d,0x1ce4e5b9);
     const st_index_t c2 = BIG_CONSTANT(0x94d049bb,0x133111eb);
 #endif
+    h += st_seed[1];
 #if ST_INDEX_BITS > 64
     h ^= h >> 64;
     h *= c2;
@@ -1362,7 +1374,7 @@ murmur_finish(st_index_t h)
     h ^= h >> r2;
     h *= c2;
     h ^= h >> r3;
-    return h;
+    return h + st_seed[2];
 }
 #undef r1
 #undef r2
@@ -1374,6 +1386,7 @@ st_hash(const void *ptr, size_t len, st_index_t h)
     const char *data = ptr;
     st_index_t t = 0;
     size_t l = len;
+    assert(!st_need_seed);
 
 #define data_at(n) (st_index_t)((unsigned char)data[(n)])
 #define UNALIGNED_ADD_4 UNALIGNED_ADD(2); UNALIGNED_ADD(1); UNALIGNED_ADD(0)
@@ -1496,8 +1509,9 @@ st_hash(const void *ptr, size_t len, st_index_t h)
 #undef UNALIGNED_ADD
 #endif
       skip_tail:
+	t ^= h;
+	t *= C2;
 	h ^= t;
-	h *= C2;
     }
     h ^= l;
 
@@ -1530,18 +1544,17 @@ st_hash_end(st_index_t h)
     return h;
 }
 
-#undef st_hash_start
 st_index_t
 st_hash_start(st_index_t h)
 {
-    return h;
+    return h + st_seed[0];
 }
 
 static st_index_t
 strhash(st_data_t arg)
 {
     register const char *string = (const char *)arg;
-    return st_hash(string, strlen(string), FNV1_32A_INIT);
+    return st_hash(string, strlen(string), st_seed[0]);
 }
 
 int
-- 
2.7.4