From c953724a1a4bcaf03fc33a9f3bef8b864cb865d0 Mon Sep 17 00:00:00 2001 From: Michael Drake Date: Sat, 7 Mar 2015 21:50:04 +0000 Subject: Change arena hash from FNV-1 to 32-bit MurmurHash2. --- src/select/arena.c | 18 +------------ src/select/arena_hash.h | 67 +++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 68 insertions(+), 17 deletions(-) create mode 100644 src/select/arena_hash.h (limited to 'src/select') 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 #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 + */ + +#ifndef css_select_arena_hash_h_ +#define css_select_arena_hash_h_ + +#include + +/** + * 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 + -- cgit v1.2.3