initial commit

1 files changed, 105 insertions, 0 deletions

diff --git a/mmh3.c b/mmh3.c
new file mode 100644
index 0000000..dbbb09a
--- /dev/null
+++ b/mmh3.c
@@ -0,0 +1,105 @@
+/* mmh3.c
+ */
+#include <string.h>
+#include <stdint.h>
+
+#include "mmh3.h"
+
+
+static uint64_t
+load64_le(const uint8_t *p)
+{
+    return ((uint64_t)p[0])       |
+           ((uint64_t)p[1] << 8)  |
+           ((uint64_t)p[2] << 16) |
+           ((uint64_t)p[3] << 24) |
+           ((uint64_t)p[4] << 32) |
+           ((uint64_t)p[5] << 40) |
+           ((uint64_t)p[6] << 48) |
+           ((uint64_t)p[7] << 56);
+}
+
+/* mmh3_128() -- calculate 128 bit mmh3 hash.
+ *
+ * Args:
+ *     key
+ *     len
+ *     seed
+ *     out
+ *
+ * Returns:
+ *     Nothing. Output is written to 'out'.
+ */
+void mmh3_128(const void *key, const size_t len, const uint64_t seed, uint64_t *out) {
+    const uint64_t  c1 = 0x87c37b91114253d5;
+    const uint64_t  c2 = 0x4cf5ad432745937f;
+    const uint8_t   *data = (const uint8_t *)key;
+    const size_t    nblocks = len / 16;
+    uint64_t        h1 = seed;
+    uint64_t        h2 = seed;
+
+    // Process the data in 128-bit chunks
+    for (size_t i = 0; i < nblocks; i++) {
+        const uint8_t *block = data + i * 16;
+
+	uint64_t k1 = load64_le(block);
+	uint64_t k2 = load64_le(block + 8);
+
+        k1 *= c1; k1 = (k1 << 31) | (k1 >> 33); k1 *= c2; h1 ^= k1;
+        h1 = (h1 << 27) | (h1 >> 37); h1 += h2; h1 = h1 * 5 + 0x52dce729;
+
+        k2 *= c2; k2 = (k2 << 33) | (k2 >> 31); k2 *= c1; h2 ^= k2;
+        h2 = (h2 << 31) | (h2 >> 33); h2 += h1; h2 = h2 * 5 + 0x38495ab5;
+    }
+
+    // Process the remaining bytes
+    const uint8_t *tail = (const uint8_t *)(data + nblocks * 16);
+    uint64_t k1 = 0;
+    uint64_t k2 = 0;
+
+    switch (len & 15) {
+    case 15: k2 ^= ((uint64_t)tail[14]) << 48; /* fall through */
+    case 14: k2 ^= ((uint64_t)tail[13]) << 40;  /* fall through */
+    case 13: k2 ^= ((uint64_t)tail[12]) << 32;  /* fall through */
+    case 12: k2 ^= ((uint64_t)tail[11]) << 24;  /* fall through */
+    case 11: k2 ^= ((uint64_t)tail[10]) << 16; /* fall through */
+    case 10: k2 ^= ((uint64_t)tail[9]) << 8; /* fall through */
+    case  9: k2 ^= ((uint64_t)tail[8]) << 0; /* fall through */
+      k2 *= c2; k2 = (k2 << 33) | (k2 >> 31); k2 *= c1; h2 ^= k2;
+      /* fall through */
+    case  8: k1 ^= ((uint64_t)tail[7]) << 56; /* fall through */
+    case  7: k1 ^= ((uint64_t)tail[6]) << 48; /* fall through */
+    case  6: k1 ^= ((uint64_t)tail[5]) << 40; /* fall through */
+    case  5: k1 ^= ((uint64_t)tail[4]) << 32; /* fall through */
+    case  4: k1 ^= ((uint64_t)tail[3]) << 24; /* fall through */
+    case  3: k1 ^= ((uint64_t)tail[2]) << 16; /* fall through */
+    case  2: k1 ^= ((uint64_t)tail[1]) << 8; /* fall through */
+    case  1: k1 ^= ((uint64_t)tail[0]) << 0; /* fall through */
+      k1 *= c1; k1 = (k1 << 31) | (k1 >> 33); k1 *= c2; h1 ^= k1;
+    }
+
+    // Finalization
+    h1 ^= len;
+    h2 ^= len;
+
+    h1 += h2;
+    h2 += h1;
+
+    h1 ^= h1 >> 33;
+    h1 *= 0xff51afd7ed558ccd;
+    h1 ^= h1 >> 33;
+    h1 *= 0xc4ceb9fe1a85ec53;
+    h1 ^= h1 >> 33;
+
+    h2 ^= h2 >> 33;
+    h2 *= 0xff51afd7ed558ccd;
+    h2 ^= h2 >> 33;
+    h2 *= 0xc4ceb9fe1a85ec53;
+    h2 ^= h2 >> 33;
+
+    h1 += h2;
+    h2 += h1;
+
+    out[0] = h1;
+    out[1] = h2;
+}