lib: Add MurmurHash3 hash_mix64 for hash tables

Adds a (non-cryptographic) MurmurHash3 fmix64 finalizer for hashing an
integer key to a table index, replacing the MD5-based bucket hashing
in the pft.

Signed-off-by: Dimitri Staessens <dimitri@ouroboros.rocks>
Signed-off-by: Sander Vrijders <sander@ouroboros.rocks>

3 files changed, 53 insertions, 0 deletions

diff --git a/include/ouroboros/hash.h b/include/ouroboros/hash.h
index 17ab98ac..c6609ffc 100644
--- a/include/ouroboros/hash.h
+++ b/include/ouroboros/hash.h
@@ -89,4 +89,7 @@ void     str_hash(enum hash_algo algo,
                   void *         dst,
                   const char *   str);
 
+/* Non-cryptographic finalizer for hashing an integer key to a table index. */
+uint64_t hash_mix64(uint64_t key);
+
 #endif /* OUROBOROS_LIB_HASH_H */
diff --git a/src/lib/hash.c b/src/lib/hash.c
index 9b26a552..903474df 100644
--- a/src/lib/hash.c
+++ b/src/lib/hash.c
@@ -74,8 +74,10 @@ uint16_t hash_len(enum hash_algo algo)
 {
         if (algo == HASH_CRC8)
                 return CRC8_HASH_LEN;
+
         if (algo == HASH_CRC16)
                 return CRC16_HASH_LEN;
+
         if (algo == HASH_CRC64)
                 return CRC64_HASH_LEN;
 #ifdef HAVE_LIBGCRYPT
@@ -164,3 +166,14 @@ void str_hash(enum hash_algo algo,
 {
         return mem_hash(algo, dst, (const uint8_t *) str, strlen(str));
 }
+
+uint64_t hash_mix64(uint64_t key)
+{
+        key ^= key >> 33;
+        key *= 0xff51afd7ed558ccdULL;
+        key ^= key >> 33;
+        key *= 0xc4ceb9fe1a85ec53ULL;
+        key ^= key >> 33;
+
+        return key;
+}
diff --git a/src/lib/tests/hash_test.c b/src/lib/tests/hash_test.c
index 451d3c25..a2ba62cc 100644
--- a/src/lib/tests/hash_test.c
+++ b/src/lib/tests/hash_test.c
@@ -39,6 +39,11 @@ struct vec_entry {
         char * out;
 };
 
+struct mix_entry {
+        uint64_t in;
+        uint64_t out;
+};
+
 static int test_crc8(void)
 {
         int ret = 0;
@@ -288,6 +293,36 @@ static int test_sha3(void)
         return ret;
 }
 
+static int test_mix64(void)
+{
+        int ret = 0;
+
+        struct mix_entry vec [] = {
+                { 0x0000000000000000ULL, 0x0000000000000000ULL },
+                { 0x123456789abcdefeULL, 0xb1943cfea4f78f08ULL }
+        };
+
+        size_t n = sizeof(vec) / sizeof(vec[0]);
+        size_t i;
+
+        TEST_START();
+
+        for (i = 0; i < n; i++) {
+                uint64_t res = hash_mix64(vec[i].in);
+
+                if (res != vec[i].out) {
+                        printf("Mix failed %016llx != %016llx.\n",
+                               (unsigned long long) res,
+                               (unsigned long long) vec[i].out);
+                        ret |= -1;
+                }
+        }
+
+        TEST_END(ret);
+
+        return ret;
+}
+
 int hash_test(int     argc,
               char ** argv)
 {
@@ -308,5 +343,7 @@ int hash_test(int     argc,
 
         ret |= test_sha3();
 
+        ret |= test_mix64();
+
         return ret;
 }