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