It WAS a hash collision after all!

I don't know what I tested before lol but okay great!

1 files changed, 50 insertions, 30 deletions

diff --git a/src/hash.c b/src/hash.c
index 6a17e09..8940d70 100644
--- a/src/hash.c
+++ b/src/hash.c
@@ -1,42 +1,62 @@
 // murmur3 originally by Austin Appleby
+// Copyright (c) 2013, ksss
 // Copyright (c) 2023, Marvin Borner <dev@marvinborner.de>
 // SPDX-License-Identifier: MIT
 
 #include <stdint.h>
-#include <string.h>
 
 #include <hash.h>
 
-static inline uint32_t murmur_32_scramble(uint32_t k)
+hash_t hash(const void *key, int len, uint64_t seed)
 {
-	k *= 0xcc9e2d51;
-	k = (k << 15) | (k >> 17);
-	k *= 0x1b873593;
-	return k;
-}
+	const uint64_t m = 0xc6a4a7935bd1e995ULL;
+	const int r = 47;
+
+	uint64_t h = seed ^ (len * m);
+
+	const uint64_t *data = (const uint64_t *)key;
+	const uint64_t *end = data + (len / 8);
+
+	while (data != end) {
+		uint64_t k = *data++;
+
+		k *= m;
+		k ^= k >> r;
+		k *= m;
+
+		h ^= k;
+		h *= m;
+	}
+
+	const unsigned char *data2 = (const unsigned char *)data;
+
+	int b = len & 7;
+	if (b >= 7) {
+		h ^= ((uint64_t)data2[6]) << 48;
+	}
+	if (b >= 6) {
+		h ^= ((uint64_t)data2[5]) << 40;
+	}
+	if (b >= 5) {
+		h ^= ((uint64_t)data2[4]) << 32;
+	}
+	if (b >= 4) {
+		h ^= ((uint64_t)data2[3]) << 24;
+	}
+	if (b >= 3) {
+		h ^= ((uint64_t)data2[2]) << 16;
+	}
+	if (b >= 2) {
+		h ^= ((uint64_t)data2[1]) << 8;
+	}
+	if (b >= 1) {
+		h ^= ((uint64_t)data2[0]);
+		h *= m;
+	}
+
+	h ^= h >> r;
+	h *= m;
+	h ^= h >> r;
 
-hash_t hash(const uint8_t *key, size_t len, uint32_t seed)
-{
-	uint32_t h = seed;
-	uint32_t k;
-	for (size_t i = len >> 2; i; i--) {
-		memcpy(&k, key, sizeof(uint32_t));
-		key += sizeof(uint32_t);
-		h ^= murmur_32_scramble(k);
-		h = (h << 13) | (h >> 19);
-		h = h * 5 + 0xe6546b64;
-	}
-	k = 0;
-	for (size_t i = len & 3; i; i--) {
-		k <<= 8;
-		k |= key[i - 1];
-	}
-	h ^= murmur_32_scramble(k);
-	h ^= len;
-	h ^= h >> 16;
-	h *= 0x85ebca6b;
-	h ^= h >> 13;
-	h *= 0xc2b2ae35;
-	h ^= h >> 16;
 	return h;
 }