diff options
Diffstat (limited to 'src/util')
-rw-r--r-- | src/util/murmurhash3.c | 110 | ||||
-rw-r--r-- | src/util/murmurhash3.h | 10 |
2 files changed, 120 insertions, 0 deletions
diff --git a/src/util/murmurhash3.c b/src/util/murmurhash3.c new file mode 100644 index 00000000..c14cd7ce --- /dev/null +++ b/src/util/murmurhash3.c @@ -0,0 +1,110 @@ +/* This file is based on the public domain MurmurHash3 from Austin Appleby: + * http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp + * + * We use only the 32 bit variant because the 2 produce different result while + * we need to produce the same result regardless of the architecture as + * clients can be both 64 or 32 bit at the same time. + */ + +#include <stdlib.h> +#include <stdint.h> +#include <endian.h> +#include <string.h> + +static uint32_t rotl(uint32_t x, int8_t r) +{ + return (x << r) | (x >> (32 - r)); +} + +/* slower than original but is endian neutral and handles platforms that + * do only aligned reads */ +__attribute__((always_inline)) +static uint32_t getblock(const uint8_t *p, int i) +{ + uint32_t r; + size_t size = sizeof(uint32_t); + + memcpy(&r, &p[i * size], size); + + return le32toh(r); +} + +/* + * Finalization mix - force all bits of a hash block to avalanche + */ + +__attribute__((always_inline)) +static uint32_t fmix(uint32_t h) +{ + h ^= h >> 16; + h *= 0x85ebca6b; + h ^= h >> 13; + h *= 0xc2b2ae35; + h ^= h >> 16; + + return h; +} + + +uint32_t murmurhash3(const char *key, int len, uint32_t seed) +{ + const uint8_t *blocks; + const uint8_t *tail; + int nblocks; + uint32_t h1; + uint32_t k1; + uint32_t c1; + uint32_t c2; + int i; + + blocks = (const uint8_t *)key; + nblocks = len / 4; + h1 = seed; + c1 = 0xcc9e2d51; + c2 = 0x1b873593; + + /* body */ + + for (i = 0; i < nblocks; i++) { + + k1 = getblock(blocks, i); + + k1 *= c1; + k1 = rotl(k1, 15); + k1 *= c2; + + h1 ^= k1; + h1 = rotl(h1, 13); + h1 = h1 * 5 + 0xe6546b64; + } + + /* tail */ + + tail = (const uint8_t *)key + nblocks * 4; + + k1 = 0; + + switch (len & 3) { + case 3: + k1 ^= tail[2] << 16; + case 2: + k1 ^= tail[1] << 8; + case 1: + k1 ^= tail[0]; + k1 *= c1; + k1 = rotl(k1, 15); + k1 *= c2; + h1 ^= k1; + default: + break; + } + + /* finalization */ + + h1 ^= len; + h1 = fmix(h1); + + return h1; +} + + diff --git a/src/util/murmurhash3.h b/src/util/murmurhash3.h new file mode 100644 index 00000000..9174554b --- /dev/null +++ b/src/util/murmurhash3.h @@ -0,0 +1,10 @@ +/* This file is based on the public domain MurmurHash3 from Austin Appleby: + * http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp + * + * We use only the 32 bit variant because the 2 produce different result while + * we need to produce the same result regardless of the architecture as + * clients can be both 64 or 32 bit at the same time. + */ + +uint32_t murmurhash3(const char *key, int len, uint32_t seed); + |