diff options
author | Michael Drake <tlsa@netsurf-browser.org> | 2015-03-07 21:50:04 +0000 |
---|---|---|
committer | Michael Drake <tlsa@netsurf-browser.org> | 2015-08-15 11:46:01 +0100 |
commit | c78be88ddd451c3badeacf8a5e76e86a6161b847 (patch) | |
tree | a4f9a6c471861a823721c2efdff254803fb2b420 | |
parent | 4834c6938e13d866fb152f8a39fb33a2314b71a6 (diff) | |
download | libcss-c78be88ddd451c3badeacf8a5e76e86a6161b847.tar.gz |
Change arena hash from FNV-1 to 32-bit MurmurHash2.
-rw-r--r-- | src/select/arena.c | 18 | ||||
-rw-r--r-- | src/select/arena_hash.h | 67 |
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 + |