Subject: [PATCH 5/9] random.c: use sip_hash13 as faster but still safe alternative to sip_hash24

From: Sokolov Yura aka funny_falcon <[email-masked]>
Date: Sat, 9 Jul 2016 16:35:17 +0300

SipHash13 is secure enough to be used in hash-tables,
and SipHash's author confirms that.
Rust already considered switch to SipHash13:
  https://github.com/rust-lang/rust/issues/29754#issue-116174313
Jean-Philippe Aumasson confirmation:
  https://github.com/rust-lang/rust/issues/29754#issuecomment-156073946
Merged pull request:
  https://github.com/rust-lang/rust/pull/33940
---
 random.c  |   2 +-
 siphash.c | 120 ++++++++++++++++++++++++++++++++++++++++++++++----------------
 siphash.h |   1 +
 3 files changed, 92 insertions(+), 31 deletions(-)

diff --git a/random.c b/random.c
index f584bb2..011bf07 100644
--- a/random.c
+++ b/random.c
@@ -1521,7 +1521,7 @@ init_siphash(sipseed_keys_t key, uint32_t* cnt)
 st_index_t
 rb_memhash(const void *ptr, long len)
 {
-    sip_uint64_t h = sip_hash24(sipseed.key, ptr, len);
+    sip_uint64_t h = sip_hash13(sipseed.key, ptr, len);
 #ifdef HAVE_UINT64_T
     return (st_index_t)h;
 #else
diff --git a/siphash.c b/siphash.c
index 0df96f8..8cc850e 100644
--- a/siphash.c
+++ b/siphash.c
@@ -394,37 +394,10 @@ do {					\
     XOR64_TO((v0), (m));		\
 } while (0)
 
-uint64_t
-sip_hash24(const uint8_t key[16], const uint8_t *data, size_t len)
+static inline uint64_t
+sip_read_last(const uint8_t *end, size_t len)
 {
-    uint64_t k0, k1;
-    uint64_t v0, v1, v2, v3;
-    uint64_t m, last;
-    const uint8_t *end = data + len - (len % sizeof(uint64_t));
-
-    k0 = U8TO64_LE(key);
-    k1 = U8TO64_LE(key + sizeof(uint64_t));
-
-    v0 = k0; XOR64_TO(v0, sip_init_state[0]);
-    v1 = k1; XOR64_TO(v1, sip_init_state[1]);
-    v2 = k0; XOR64_TO(v2, sip_init_state[2]);
-    v3 = k1; XOR64_TO(v3, sip_init_state[3]);
-
-#if BYTE_ORDER == LITTLE_ENDIAN && UNALIGNED_WORD_ACCESS
-    {
-        uint64_t *data64 = (uint64_t *)data;
-        while (data64 != (uint64_t *) end) {
-	    m = *data64++;
-	    SIP_2_ROUND(m, v0, v1, v2, v3);
-        }
-    }
-#else
-    for (; data != end; data += sizeof(uint64_t)) {
-	m = U8TO64_LE(data);
-	SIP_2_ROUND(m, v0, v1, v2, v3);
-    }
-#endif
-
+    uint64_t last;
 #ifdef HAVE_UINT64_T
     last = (uint64_t)len << 56;
 #define OR_BYTE(n) (last |= ((uint64_t) end[n]) << ((n) * 8))
@@ -467,7 +440,41 @@ sip_hash24(const uint8_t key[16], const uint8_t *data, size_t len)
 	case 0:
 	    break;
     }
+    return last;
+}
+
+uint64_t
+sip_hash24(const uint8_t key[16], const uint8_t *data, size_t len)
+{
+    uint64_t k0, k1;
+    uint64_t v0, v1, v2, v3;
+    uint64_t m, last;
+    const uint8_t *end = data + len - (len % sizeof(uint64_t));
+
+    k0 = U8TO64_LE(key);
+    k1 = U8TO64_LE(key + sizeof(uint64_t));
+
+    v0 = k0; XOR64_TO(v0, sip_init_state[0]);
+    v1 = k1; XOR64_TO(v1, sip_init_state[1]);
+    v2 = k0; XOR64_TO(v2, sip_init_state[2]);
+    v3 = k1; XOR64_TO(v3, sip_init_state[3]);
+
+#if BYTE_ORDER == LITTLE_ENDIAN && UNALIGNED_WORD_ACCESS
+    {
+        uint64_t *data64 = (uint64_t *)data;
+        while (data64 != (uint64_t *) end) {
+	    m = *data64++;
+	    SIP_2_ROUND(m, v0, v1, v2, v3);
+        }
+    }
+#else
+    for (; data != end; data += sizeof(uint64_t)) {
+	m = U8TO64_LE(data);
+	SIP_2_ROUND(m, v0, v1, v2, v3);
+    }
+#endif
 
+    last = sip_read_last(end, len);
     SIP_2_ROUND(last, v0, v1, v2, v3);
 
     XOR64_INT(v2, 0xff);
@@ -482,3 +489,56 @@ sip_hash24(const uint8_t key[16], const uint8_t *data, size_t len)
     XOR64_TO(v0, v3);
     return v0;
 }
+
+#define SIP_1_ROUND(m, v0, v1, v2, v3)	\
+do {					\
+    XOR64_TO((v3), (m));		\
+    SIP_COMPRESS(v0, v1, v2, v3);	\
+    XOR64_TO((v0), (m));		\
+} while (0)
+
+uint64_t
+sip_hash13(const uint8_t key[16], const uint8_t *data, size_t len)
+{
+    uint64_t k0, k1;
+    uint64_t v0, v1, v2, v3;
+    uint64_t m, last;
+    const uint8_t *end = data + len - (len % sizeof(uint64_t));
+
+    k0 = U8TO64_LE(key);
+    k1 = U8TO64_LE(key + sizeof(uint64_t));
+
+    v0 = k0; XOR64_TO(v0, sip_init_state[0]);
+    v1 = k1; XOR64_TO(v1, sip_init_state[1]);
+    v2 = k0; XOR64_TO(v2, sip_init_state[2]);
+    v3 = k1; XOR64_TO(v3, sip_init_state[3]);
+
+#if BYTE_ORDER == LITTLE_ENDIAN && UNALIGNED_WORD_ACCESS
+    {
+        uint64_t *data64 = (uint64_t *)data;
+        while (data64 != (uint64_t *) end) {
+	    m = *data64++;
+	    SIP_1_ROUND(m, v0, v1, v2, v3);
+        }
+    }
+#else
+    for (; data != end; data += sizeof(uint64_t)) {
+	m = U8TO64_LE(data);
+	SIP_1_ROUND(m, v0, v1, v2, v3);
+    }
+#endif
+
+    last = sip_read_last(end, len);
+    SIP_1_ROUND(last, v0, v1, v2, v3);
+
+    XOR64_INT(v2, 0xff);
+
+    SIP_COMPRESS(v0, v1, v2, v3);
+    SIP_COMPRESS(v0, v1, v2, v3);
+    SIP_COMPRESS(v0, v1, v2, v3);
+
+    XOR64_TO(v0, v1);
+    XOR64_TO(v0, v2);
+    XOR64_TO(v0, v3);
+    return v0;
+}
diff --git a/siphash.h b/siphash.h
index 3f39884..3a477cf 100644
--- a/siphash.h
+++ b/siphash.h
@@ -44,5 +44,6 @@ void sip_hash_free(sip_hash *h);
 void sip_hash_dump(sip_hash *h);
 
 uint64_t sip_hash24(const uint8_t key[16], const uint8_t *data, size_t len);
+uint64_t sip_hash13(const uint8_t key[16], const uint8_t *data, size_t len);
 
 #endif
-- 
2.7.4