summaryrefslogtreecommitdiff
path: root/src/util
diff options
context:
space:
mode:
authorSimo Sorce <simo@redhat.com>2011-12-27 19:56:43 -0500
committerSimo Sorce <simo@redhat.com>2012-01-09 15:00:32 -0500
commit5a70b84cb66fb8c7a3fce0e3f2e4b61e0b2ea9d4 (patch)
treed60aab13a1253480b797c0615c25487759ff0490 /src/util
parenta096f75242bb612b7a1ae126c8e960934dc85fd4 (diff)
downloadsssd-5a70b84cb66fb8c7a3fce0e3f2e4b61e0b2ea9d4.tar.gz
sssd-5a70b84cb66fb8c7a3fce0e3f2e4b61e0b2ea9d4.tar.bz2
sssd-5a70b84cb66fb8c7a3fce0e3f2e4b61e0b2ea9d4.zip
util: add murmurhash3 hash function
Diffstat (limited to 'src/util')
-rw-r--r--src/util/murmurhash3.c110
-rw-r--r--src/util/murmurhash3.h10
2 files changed, 120 insertions, 0 deletions
diff --git a/src/util/murmurhash3.c b/src/util/murmurhash3.c
new file mode 100644
index 00000000..c14cd7ce
--- /dev/null
+++ b/src/util/murmurhash3.c
@@ -0,0 +1,110 @@
+/* This file is based on the public domain MurmurHash3 from Austin Appleby:
+ * http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp
+ *
+ * We use only the 32 bit variant because the 2 produce different result while
+ * we need to produce the same result regardless of the architecture as
+ * clients can be both 64 or 32 bit at the same time.
+ */
+
+#include <stdlib.h>
+#include <stdint.h>
+#include <endian.h>
+#include <string.h>
+
+static uint32_t rotl(uint32_t x, int8_t r)
+{
+ return (x << r) | (x >> (32 - r));
+}
+
+/* slower than original but is endian neutral and handles platforms that
+ * do only aligned reads */
+__attribute__((always_inline))
+static uint32_t getblock(const uint8_t *p, int i)
+{
+ uint32_t r;
+ size_t size = sizeof(uint32_t);
+
+ memcpy(&r, &p[i * size], size);
+
+ return le32toh(r);
+}
+
+/*
+ * Finalization mix - force all bits of a hash block to avalanche
+ */
+
+__attribute__((always_inline))
+static uint32_t fmix(uint32_t h)
+{
+ h ^= h >> 16;
+ h *= 0x85ebca6b;
+ h ^= h >> 13;
+ h *= 0xc2b2ae35;
+ h ^= h >> 16;
+
+ return h;
+}
+
+
+uint32_t murmurhash3(const char *key, int len, uint32_t seed)
+{
+ const uint8_t *blocks;
+ const uint8_t *tail;
+ int nblocks;
+ uint32_t h1;
+ uint32_t k1;
+ uint32_t c1;
+ uint32_t c2;
+ int i;
+
+ blocks = (const uint8_t *)key;
+ nblocks = len / 4;
+ h1 = seed;
+ c1 = 0xcc9e2d51;
+ c2 = 0x1b873593;
+
+ /* body */
+
+ for (i = 0; i < nblocks; i++) {
+
+ k1 = getblock(blocks, i);
+
+ k1 *= c1;
+ k1 = rotl(k1, 15);
+ k1 *= c2;
+
+ h1 ^= k1;
+ h1 = rotl(h1, 13);
+ h1 = h1 * 5 + 0xe6546b64;
+ }
+
+ /* tail */
+
+ tail = (const uint8_t *)key + nblocks * 4;
+
+ k1 = 0;
+
+ switch (len & 3) {
+ case 3:
+ k1 ^= tail[2] << 16;
+ case 2:
+ k1 ^= tail[1] << 8;
+ case 1:
+ k1 ^= tail[0];
+ k1 *= c1;
+ k1 = rotl(k1, 15);
+ k1 *= c2;
+ h1 ^= k1;
+ default:
+ break;
+ }
+
+ /* finalization */
+
+ h1 ^= len;
+ h1 = fmix(h1);
+
+ return h1;
+}
+
+
diff --git a/src/util/murmurhash3.h b/src/util/murmurhash3.h
new file mode 100644
index 00000000..9174554b
--- /dev/null
+++ b/src/util/murmurhash3.h
@@ -0,0 +1,10 @@
+/* This file is based on the public domain MurmurHash3 from Austin Appleby:
+ * http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp
+ *
+ * We use only the 32 bit variant because the 2 produce different result while
+ * we need to produce the same result regardless of the architecture as
+ * clients can be both 64 or 32 bit at the same time.
+ */
+
+uint32_t murmurhash3(const char *key, int len, uint32_t seed);
+