[ovs-dev] [RFC 09/14] hash: Add 128-bit murmurhash.

Joe Stringer joestringer at nicira.com
Thu Aug 21 05:42:04 UTC 2014


Add the 128-bit murmurhash by Austin Appleby, for 32-bit systems from:
http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp

Signed-off-by: Joe Stringer <joestringer at nicira.com>
---
There is also a version for 64-bit systems which I haven't tried yet,
mostly because this version provides the same code for x32/x64. I can
look at adding the alternative if we think it's worth doing.
---
 include/openvswitch/types.h |    5 ++
 lib/hash.c                  |  194 ++++++++++++++++++++++++++++++++++++++++++-
 lib/hash.h                  |    4 +-
 3 files changed, 201 insertions(+), 2 deletions(-)

diff --git a/include/openvswitch/types.h b/include/openvswitch/types.h
index 54541a4..3fb1243 100644
--- a/include/openvswitch/types.h
+++ b/include/openvswitch/types.h
@@ -81,6 +81,11 @@ typedef struct {
 #endif
 } ovs_32aligned_u64;
 
+/* XXX: endianness? */
+typedef struct {
+    uint32_t h[4];
+} ovs_u128;
+
 /* A 64-bit value, in network byte order, that is only aligned on a 32-bit
  * boundary. */
 typedef struct {
diff --git a/lib/hash.c b/lib/hash.c
index 71cd74c..26a031e 100644
--- a/lib/hash.c
+++ b/lib/hash.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2008, 2009, 2010, 2012, 2013 Nicira, Inc.
+ * Copyright (c) 2008, 2009, 2010, 2012, 2013, 2014 Nicira, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -50,6 +50,198 @@ hash_bytes(const void *p_, size_t n, uint32_t basis)
     return hash_finish(hash, orig_n);
 }
 
+static void mhash128_add(ovs_u128 *hashp, const uint32_t *data)
+{
+    const uint32_t c1 = 0x239b961b;
+    const uint32_t c2 = 0xab0e9789;
+    const uint32_t c3 = 0x38b34ae5;
+    const uint32_t c4 = 0xa1e38b93;
+    uint32_t k1 = data[0];
+    uint32_t k2 = data[1];
+    uint32_t k3 = data[2];
+    uint32_t k4 = data[3];
+
+    ovs_u128 hash = *hashp;
+
+    k1 *= c1;
+    k1  = hash_rot(k1,15);
+    k1 *= c2;
+    hash.h[0] ^= k1;
+
+    hash.h[0] = hash_rot(hash.h[0],19);
+    hash.h[0] += hash.h[1];
+    hash.h[0] = hash.h[0]*5+0x561ccd1b;
+
+    k2 *= c2;
+    k2  = hash_rot(k2,16);
+    k2 *= c3;
+    hash.h[1] ^= k2;
+
+    hash.h[1] = hash_rot(hash.h[1],17);
+    hash.h[1] += hash.h[2];
+    hash.h[1] = hash.h[1]*5+0x0bcaa747;
+
+    k3 *= c3;
+    k3  = hash_rot(k3,17);
+    k3 *= c4;
+    hash.h[2] ^= k3;
+
+    hash.h[2] = hash_rot(hash.h[2],15);
+    hash.h[2] += hash.h[3];
+    hash.h[2] = hash.h[2]*5+0x96cd1c35;
+
+    k4 *= c4;
+    k4  = hash_rot(k4,18);
+    k4 *= c1;
+    hash.h[3] ^= k4;
+
+    hash.h[3] = hash_rot(hash.h[3],13);
+    hash.h[3] += hash.h[0];
+    hash.h[3] = hash.h[3]*5+0x32ac3b17;
+
+    *hashp = hash;
+}
+
+static void mhash128_add_tail(ovs_u128 *hashp, const uint8_t *data, size_t len)
+{
+    const uint32_t c1 = 0x239b961b;
+    const uint32_t c2 = 0xab0e9789;
+    const uint32_t c3 = 0x38b34ae5;
+    const uint32_t c4 = 0xa1e38b93;
+    uint32_t k1 = 0;
+    uint32_t k2 = 0;
+    uint32_t k3 = 0;
+    uint32_t k4 = 0;
+    ovs_u128 hash = *hashp;
+
+    switch(len & 15) {
+    case 15:
+        k4 ^= data[14] << 16;
+    case 14:
+        k4 ^= data[13] << 8;
+    case 13:
+        k4 ^= data[12] << 0;
+        k4 *= c4;
+        k4  = hash_rot(k4,18);
+        k4 *= c1; hash.h[3] ^= k4;
+
+    case 12:
+        k3 ^= data[11] << 24;
+    case 11:
+        k3 ^= data[10] << 16;
+    case 10:
+        k3 ^= data[ 9] << 8;
+    case  9:
+        k3 ^= data[ 8] << 0;
+        k3 *= c3;
+        k3  = hash_rot(k3,17);
+        k3 *= c4;
+        hash.h[2] ^= k3;
+
+    case  8:
+        k2 ^= data[ 7] << 24;
+    case  7:
+        k2 ^= data[ 6] << 16;
+    case  6:
+        k2 ^= data[ 5] << 8;
+    case  5:
+        k2 ^= data[ 4] << 0;
+        k2 *= c2;
+        k2  = hash_rot(k2,16);
+        k2 *= c3;
+        hash.h[1] ^= k2;
+
+    case  4:
+        k1 ^= data[ 3] << 24;
+    case  3:
+        k1 ^= data[ 2] << 16;
+    case  2:
+        k1 ^= data[ 1] << 8;
+    case  1:
+        k1 ^= data[ 0] << 0;
+        k1 *= c1;
+        k1  = hash_rot(k1,15);
+        k1 *= c2;
+        hash.h[0] ^= k1;
+    };
+
+    *hashp = hash;
+}
+
+static void
+fmix32(ovs_u128 *in, ovs_u128 *out)
+{
+    int i, h;
+
+    for (i = 0; i < 4; i++) {
+        h = in->h[i];
+
+        h ^= h >> 16;
+        h *= 0x85ebca6b;
+        h ^= h >> 13;
+        h *= 0xc2b2ae35;
+        h ^= h >> 16;
+
+        out->h[i] = h;
+    }
+}
+
+static void
+mhash128_finish(ovs_u128 *hashp, size_t len)
+{
+    ovs_u128 hash = *hashp;
+
+    hash.h[0] ^= len;
+    hash.h[1] ^= len;
+    hash.h[2] ^= len;
+    hash.h[3] ^= len;
+
+    hash.h[0] += hash.h[1];
+    hash.h[0] += hash.h[2];
+    hash.h[0] += hash.h[3];
+    hash.h[1] += hash.h[0];
+    hash.h[2] += hash.h[0];
+    hash.h[3] += hash.h[0];
+
+    fmix32(&hash, &hash);
+
+    hash.h[0] += hash.h[1];
+    hash.h[0] += hash.h[2];
+    hash.h[0] += hash.h[3];
+    hash.h[1] += hash.h[0];
+    hash.h[2] += hash.h[0];
+    hash.h[3] += hash.h[0];
+
+    *hashp = hash;
+}
+
+/* Calculates the 128-bit hash of the 'len' bytes at 'p_', starting from
+ * 'basis' and places it into 'out'. */
+void
+hash_words128(const void *p_, size_t len, uint32_t basis, ovs_u128 *out)
+{
+    const uint32_t *p = p_;
+    const int nblocks = len / 16;
+    const uint32_t *blocks = (const uint32_t *)(p + nblocks*4);
+    const uint8_t *tail = (const uint8_t*)(p + nblocks*4);
+
+    ovs_u128 hash = {
+        .h[0] = basis,
+        .h[1] = basis,
+        .h[2] = basis,
+        .h[3] = basis,
+    };
+
+    for(int i = -nblocks; i; i++) {
+        mhash128_add(&hash, &blocks[i*4]);
+    }
+
+    mhash128_add_tail(&hash, tail, len);
+    mhash128_finish(&hash, len);
+
+    *out = hash;
+}
+
 uint32_t
 hash_double(double x, uint32_t basis)
 {
diff --git a/lib/hash.h b/lib/hash.h
index f8bbada..102f35a 100644
--- a/lib/hash.h
+++ b/lib/hash.h
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2008, 2009, 2010, 2012, 2013 Nicira, Inc.
+ * Copyright (c) 2008, 2009, 2010, 2012, 2013, 2014 Nicira, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -82,6 +82,8 @@ static inline uint32_t mhash_finish(uint32_t hash, uint32_t n_bytes)
     return hash;
 }
 
+void hash_words128(const void *p_, size_t n, uint32_t basis, ovs_u128 *out);
+
 #if !(defined(__SSE4_2__) && defined(__x86_64__))
 /* Mhash-based implemantation. */
 
-- 
1.7.10.4




More information about the dev mailing list