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 <joestrin...@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
_______________________________________________
dev mailing list
dev@openvswitch.org
http://openvswitch.org/mailman/listinfo/dev
