1 files changed, 99 insertions, 0 deletions
diff --git a/ext/tdb/murmur3.c b/ext/tdb/murmur3.c
new file mode 100644
index 0000000..cdc7f73
--- /dev/null
+++ b/ext/tdb/murmur3.c
@@ -0,0 +1,99 @@
+#include "rbtdb.h"
+/*
+ * https://sites.google.com/site/murmurhash/
+ *
+ * MurmurHash3 was written by Austin Appleby, and is placed in the public
+ * domain. The author hereby disclaims copyright to this source code.
+ *
+ * Eric Wong trivially ported this to C for Ruby tdb (32-bit version only)
+ */
+
+#include <stdint.h>
+#define        FORCE_INLINE __attribute__((always_inline))
+
+static inline uint32_t rotl32(uint32_t x, int8_t r)
+{
+        return (x << r) | (x >> (32 - r));
+}
+
+#define        ROTL32(x,y)        rotl32(x,y)
+
+#define BIG_CONSTANT(x) (x##LLU)
+
+/* ----------------------------------------------------------------------------
+ * Block read - if your platform needs to do endian-swapping or can only
+ * handle aligned reads, do the conversion here
+ */
+
+static FORCE_INLINE uint32_t getblock(const uint32_t * p, int i)
+{
+        return p[i];
+}
+
+/* ----------------------------------------------------------------------------
+ * Finalization mix - force all bits of a hash block to avalanche
+ */
+
+static FORCE_INLINE uint32_t fmix(uint32_t h)
+{
+        h ^= h >> 16;
+        h *= 0x85ebca6b;
+        h ^= h >> 13;
+        h *= 0xc2b2ae35;
+        h ^= h >> 16;
+
+        return h;
+}
+
+unsigned int rbtdb_murmur3a(TDB_DATA * key)
+{
+        const uint8_t *data = key->dptr;
+        int len = (int)key->dsize;
+        const int nblocks = len / 4;
+        static const uint32_t seed;
+        uint32_t h1 = seed;
+        int i;
+
+        static const uint32_t c1 = 0xcc9e2d51;
+        static const uint32_t c2 = 0x1b873593;
+
+        /* body */
+        const uint32_t *blocks = (const uint32_t *)(data + nblocks * 4);
+
+        for (i = -nblocks; i; i++) {
+                uint32_t k1 = getblock(blocks, i);
+
+                k1 *= c1;
+                k1 = ROTL32(k1, 15);
+                k1 *= c2;
+
+                h1 ^= k1;
+                h1 = ROTL32(h1, 13);
+                h1 = h1 * 5 + 0xe6546b64;
+        }
+
+        /* tail */
+        {
+                const uint8_t *tail = (const uint8_t *)(data + nblocks * 4);
+                uint32_t 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 = ROTL32(k1, 15);
+                        k1 *= c2;
+                        h1 ^= k1;
+                };
+        }
+
+        /* finalization */
+
+        h1 ^= len;
+
+        return fmix(h1);
+}