summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMichael Drake <tlsa@netsurf-browser.org>2015-03-07 21:50:04 (GMT)
committer Michael Drake <tlsa@netsurf-browser.org>2016-11-19 14:30:07 (GMT)
commitc953724a1a4bcaf03fc33a9f3bef8b864cb865d0 (patch)
tree347f02171e8ba78dd5a55d7a70c954afd307d9b9
parentfac1ad8641848a3d747b6c495cf443ccc29c077e (diff)
downloadlibcss-c953724a1a4bcaf03fc33a9f3bef8b864cb865d0.tar.gz
libcss-c953724a1a4bcaf03fc33a9f3bef8b864cb865d0.tar.bz2
Change arena hash from FNV-1 to 32-bit MurmurHash2.
-rw-r--r--src/select/arena.c18
-rw-r--r--src/select/arena_hash.h67
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
--- a/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
+