Change arena hash from FNV-1 to 32-bit MurmurHash2.

2 files changed, 68 insertions, 17 deletions

diff --git a/src/select/arena.c b/src/select/arena.c
index 8f5a319..1b0ea57 100644
--- a/src/select/arena.c
+++ b/src/select/arena.c
@@ -9,6 +9,7 @@
 #include <string.h>
 
 #include "select/arena.h"
+#include "select/arena_hash.h"
 #include "select/computed.h"
 
 #define TU_SIZE 3037
@@ -18,23 +19,6 @@ struct css_computed_uncommon *table_u[TU_SIZE];
 struct css_computed_style *table_s[TS_SIZE];
 
 
-/**
- * FNV-1 hash
- */
-static inline uint32_t css__arena_hash(const uint8_t *data, size_t len)
-{
-	lwc_hash h = 0x811c9dc5;
-
-	while (len > 0) {
-		h *= 0x01000193;
-		h ^= *data++;
-                len--;
-	}
-
-	return h;
-}
-
-
 static inline uint32_t css__arena_hash_uncommon(struct css_computed_uncommon *u)
 {
 	return css__arena_hash((const uint8_t *) &u->i, sizeof(u->i));
diff --git a/src/select/arena_hash.h b/src/select/arena_hash.h
new file mode 100644
index 0000000..58abcd4
--- /dev/null
+++ b/src/select/arena_hash.h
@@ -0,0 +1,67 @@
+/*
+ * This file is part of LibCSS
+ * Licensed under the MIT License,
+ *                http://www.opensource.org/licenses/mit-license.php
+ *
+ * Copyright 2015 Michael Drake <tlsa@netsurf-browser.org>
+ */
+
+#ifndef css_select_arena_hash_h_
+#define css_select_arena_hash_h_
+
+#include <stdint.h>
+
+/**
+ * Currently 32-bit MurmurHash2.
+ *
+ * Created by Austin Appleby, and placed in the public domain.
+ *   https://sites.google.com/site/murmurhash/
+ *
+ * Refactored and adapted a little for libcss.
+ */
+static inline uint32_t css__arena_hash(const uint8_t *data, size_t len)
+{
+	/* Hashing constants */
+	const uint32_t m = 0x5bd1e995;
+	const int r = 24;
+
+	/* Start with length */
+	uint32_t h = len;
+
+	/* Hash four bytes at a time */
+	while (len >= 4) {
+		/* If we could ensure 4-byte alignment of the input, this
+		 * could be faster. */
+		uint32_t k =
+				(((uint32_t) data[0])      ) |
+				(((uint32_t) data[1]) <<  8) |
+				(((uint32_t) data[2]) << 16) |
+				(((uint32_t) data[3]) << 24);
+
+		k *= m;
+		k ^= k >> r;
+		k *= m;
+		h *= m;
+		h ^= k;
+		data += 4;
+		len -= 4;
+	}
+
+	/* Hash any left over bytes */
+	switch (len) {
+	case 3: h ^= data[2] << 16;
+	case 2: h ^= data[1] << 8;
+	case 1: h ^= data[0];
+		h *= m;
+	}
+
+	/* Finalise */
+	h ^= h >> 13;
+	h *= m;
+	h ^= h >> 15;
+
+	return h;
+}
+
+#endif
+