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_hash.h | 67 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 67 insertions(+) create mode 100644 src/select/arena_hash.h (limited to 'src/select/arena_hash.h') 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