murmurhash3.c revision 5a70b84cb66fb8c7a3fce0e3f2e4b61e0b2ea9d4
0N/A/* This file is based on the public domain MurmurHash3 from Austin Appleby:
4019N/A * http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp
0N/A *
0N/A * We use only the 32 bit variant because the 2 produce different result while
0N/A * we need to produce the same result regardless of the architecture as
0N/A * clients can be both 64 or 32 bit at the same time.
0N/A */
0N/A
0N/A#include <stdlib.h>
0N/A#include <stdint.h>
0N/A#include <endian.h>
0N/A#include <string.h>
0N/A
0N/Astatic uint32_t rotl(uint32_t x, int8_t r)
0N/A{
0N/A return (x << r) | (x >> (32 - r));
0N/A}
0N/A
2362N/A/* slower than original but is endian neutral and handles platforms that
2362N/A * do only aligned reads */
2362N/A__attribute__((always_inline))
0N/Astatic uint32_t getblock(const uint8_t *p, int i)
0N/A{
0N/A uint32_t r;
0N/A size_t size = sizeof(uint32_t);
4019N/A
4019N/A memcpy(&r, &p[i * size], size);
0N/A
0N/A return le32toh(r);
0N/A}
0N/A
0N/A/*
4019N/A * Finalization mix - force all bits of a hash block to avalanche
4019N/A */
4019N/A
4019N/A__attribute__((always_inline))
0N/Astatic uint32_t fmix(uint32_t h)
4019N/A{
0N/A h ^= h >> 16;
0N/A h *= 0x85ebca6b;
0N/A h ^= h >> 13;
0N/A h *= 0xc2b2ae35;
0N/A h ^= h >> 16;
0N/A
0N/A return h;
0N/A}
0N/A
0N/A
0N/Auint32_t murmurhash3(const char *key, int len, uint32_t seed)
0N/A{
4019N/A const uint8_t *blocks;
4019N/A const uint8_t *tail;
4019N/A int nblocks;
4019N/A uint32_t h1;
4019N/A uint32_t k1;
4019N/A uint32_t c1;
4019N/A uint32_t c2;
4019N/A int i;
4019N/A
4019N/A blocks = (const uint8_t *)key;
4019N/A nblocks = len / 4;
4019N/A h1 = seed;
4019N/A c1 = 0xcc9e2d51;
4019N/A c2 = 0x1b873593;
4019N/A
4019N/A /* body */
4019N/A
4019N/A for (i = 0; i < nblocks; i++) {
4019N/A
4019N/A k1 = getblock(blocks, i);
4019N/A
4019N/A k1 *= c1;
4019N/A k1 = rotl(k1, 15);
4019N/A k1 *= c2;
4019N/A
4019N/A h1 ^= k1;
4019N/A h1 = rotl(h1, 13);
4019N/A h1 = h1 * 5 + 0xe6546b64;
4019N/A }
4019N/A
4019N/A /* tail */
4019N/A
4019N/A tail = (const uint8_t *)key + nblocks * 4;
4019N/A
4019N/A k1 = 0;
4019N/A
4019N/A switch (len & 3) {
4019N/A case 3:
4019N/A k1 ^= tail[2] << 16;
4019N/A case 2:
4019N/A k1 ^= tail[1] << 8;
4019N/A case 1:
4019N/A k1 ^= tail[0];
4019N/A k1 *= c1;
4019N/A k1 = rotl(k1, 15);
4019N/A k1 *= c2;
4019N/A h1 ^= k1;
4019N/A default:
4019N/A break;
4019N/A }
4019N/A
4019N/A /* finalization */
4019N/A
4019N/A h1 ^= len;
4019N/A h1 = fmix(h1);
4019N/A
4019N/A return h1;
4019N/A}
4019N/A
4019N/A
4019N/A