murmurhash3.c revision 5a70b84cb66fb8c7a3fce0e3f2e4b61e0b2ea9d4
842ae4bd224140319ae7feec1872b93dfd491143fielding/* This file is based on the public domain MurmurHash3 from Austin Appleby:
842ae4bd224140319ae7feec1872b93dfd491143fielding * http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp
842ae4bd224140319ae7feec1872b93dfd491143fielding *
842ae4bd224140319ae7feec1872b93dfd491143fielding * We use only the 32 bit variant because the 2 produce different result while
842ae4bd224140319ae7feec1872b93dfd491143fielding * we need to produce the same result regardless of the architecture as
842ae4bd224140319ae7feec1872b93dfd491143fielding * clients can be both 64 or 32 bit at the same time.
cc003103e52ff9d5fe9bed567ef9438613ab4fbfrse */
ce9621257ef9e54c1bbe5ad8a5f445a1f211c2dcnd
cc003103e52ff9d5fe9bed567ef9438613ab4fbfrse#include <stdlib.h>
ce9621257ef9e54c1bbe5ad8a5f445a1f211c2dcnd#include <stdint.h>
ce9621257ef9e54c1bbe5ad8a5f445a1f211c2dcnd#include <endian.h>
ce9621257ef9e54c1bbe5ad8a5f445a1f211c2dcnd#include <string.h>
ce9621257ef9e54c1bbe5ad8a5f445a1f211c2dcnd
ce9621257ef9e54c1bbe5ad8a5f445a1f211c2dcndstatic uint32_t rotl(uint32_t x, int8_t r)
ce9621257ef9e54c1bbe5ad8a5f445a1f211c2dcnd{
ce9621257ef9e54c1bbe5ad8a5f445a1f211c2dcnd return (x << r) | (x >> (32 - r));
ce9621257ef9e54c1bbe5ad8a5f445a1f211c2dcnd}
ce9621257ef9e54c1bbe5ad8a5f445a1f211c2dcnd
ce9621257ef9e54c1bbe5ad8a5f445a1f211c2dcnd/* slower than original but is endian neutral and handles platforms that
ce9621257ef9e54c1bbe5ad8a5f445a1f211c2dcnd * do only aligned reads */
ce9621257ef9e54c1bbe5ad8a5f445a1f211c2dcnd__attribute__((always_inline))
ce9621257ef9e54c1bbe5ad8a5f445a1f211c2dcndstatic uint32_t getblock(const uint8_t *p, int i)
ce9621257ef9e54c1bbe5ad8a5f445a1f211c2dcnd{
ce9621257ef9e54c1bbe5ad8a5f445a1f211c2dcnd uint32_t r;
cc003103e52ff9d5fe9bed567ef9438613ab4fbfrse size_t size = sizeof(uint32_t);
6ace32dacb8313226eb9019275d0e4fa45a15148rse
70535d6421eb979ac79d8f49d31cd94d75dd8b2fjorton memcpy(&r, &p[i * size], size);
cc003103e52ff9d5fe9bed567ef9438613ab4fbfrse
a943533fd4d91d114af622731a405407990c4fb1rse return le32toh(r);
67139e2d50d1e11558d87f7042f61cb04bb0d1d2jim}
a943533fd4d91d114af622731a405407990c4fb1rse
cc003103e52ff9d5fe9bed567ef9438613ab4fbfrse/*
cc003103e52ff9d5fe9bed567ef9438613ab4fbfrse * Finalization mix - force all bits of a hash block to avalanche
cc003103e52ff9d5fe9bed567ef9438613ab4fbfrse */
cc003103e52ff9d5fe9bed567ef9438613ab4fbfrse
7933d4a963def02417113b6798d87a36395053b0rse__attribute__((always_inline))
7933d4a963def02417113b6798d87a36395053b0rsestatic uint32_t fmix(uint32_t h)
71c00f988beb28388702e14cb7fe06f08bd792bbdougm{
71c00f988beb28388702e14cb7fe06f08bd792bbdougm h ^= h >> 16;
71c00f988beb28388702e14cb7fe06f08bd792bbdougm h *= 0x85ebca6b;
7933d4a963def02417113b6798d87a36395053b0rse h ^= h >> 13;
71c00f988beb28388702e14cb7fe06f08bd792bbdougm h *= 0xc2b2ae35;
71c00f988beb28388702e14cb7fe06f08bd792bbdougm h ^= h >> 16;
71c00f988beb28388702e14cb7fe06f08bd792bbdougm
7933d4a963def02417113b6798d87a36395053b0rse return h;
71c00f988beb28388702e14cb7fe06f08bd792bbdougm}
71c00f988beb28388702e14cb7fe06f08bd792bbdougm
71c00f988beb28388702e14cb7fe06f08bd792bbdougm
7933d4a963def02417113b6798d87a36395053b0rseuint32_t murmurhash3(const char *key, int len, uint32_t seed)
7933d4a963def02417113b6798d87a36395053b0rse{
d1bb6e2664788e0437acc18e877562c9a796d7cerse const uint8_t *blocks;
cc003103e52ff9d5fe9bed567ef9438613ab4fbfrse const uint8_t *tail;
cc003103e52ff9d5fe9bed567ef9438613ab4fbfrse int nblocks;
cc003103e52ff9d5fe9bed567ef9438613ab4fbfrse uint32_t h1;
c95d39bd1b86b856ca72485516e7b2e61008fe96wrowe uint32_t k1;
7933d4a963def02417113b6798d87a36395053b0rse uint32_t c1;
7933d4a963def02417113b6798d87a36395053b0rse uint32_t c2;
71c00f988beb28388702e14cb7fe06f08bd792bbdougm int i;
71c00f988beb28388702e14cb7fe06f08bd792bbdougm
7933d4a963def02417113b6798d87a36395053b0rse blocks = (const uint8_t *)key;
7933d4a963def02417113b6798d87a36395053b0rse nblocks = len / 4;
42167da203d969a1402cf7ce09c14586c04af1dfjim h1 = seed;
53c239bee62c6d55b5ddfba5d99376d4c8de924ejwoolley c1 = 0xcc9e2d51;
7933d4a963def02417113b6798d87a36395053b0rse c2 = 0x1b873593;
7933d4a963def02417113b6798d87a36395053b0rse
7933d4a963def02417113b6798d87a36395053b0rse /* body */
cc003103e52ff9d5fe9bed567ef9438613ab4fbfrse
7933d4a963def02417113b6798d87a36395053b0rse for (i = 0; i < nblocks; i++) {
7933d4a963def02417113b6798d87a36395053b0rse
7933d4a963def02417113b6798d87a36395053b0rse k1 = getblock(blocks, i);
cc003103e52ff9d5fe9bed567ef9438613ab4fbfrse
cc003103e52ff9d5fe9bed567ef9438613ab4fbfrse k1 *= c1;
cc003103e52ff9d5fe9bed567ef9438613ab4fbfrse k1 = rotl(k1, 15);
cc003103e52ff9d5fe9bed567ef9438613ab4fbfrse k1 *= c2;
e726f34f8da08c01ee8bc90904b26196b69c8587wrowe
7933d4a963def02417113b6798d87a36395053b0rse h1 ^= k1;
7933d4a963def02417113b6798d87a36395053b0rse h1 = rotl(h1, 13);
7933d4a963def02417113b6798d87a36395053b0rse h1 = h1 * 5 + 0xe6546b64;
7933d4a963def02417113b6798d87a36395053b0rse }
7933d4a963def02417113b6798d87a36395053b0rse
7933d4a963def02417113b6798d87a36395053b0rse /* tail */
7933d4a963def02417113b6798d87a36395053b0rse
7933d4a963def02417113b6798d87a36395053b0rse tail = (const uint8_t *)key + nblocks * 4;
7933d4a963def02417113b6798d87a36395053b0rse
7933d4a963def02417113b6798d87a36395053b0rse k1 = 0;
7933d4a963def02417113b6798d87a36395053b0rse
7933d4a963def02417113b6798d87a36395053b0rse switch (len & 3) {
7933d4a963def02417113b6798d87a36395053b0rse case 3:
7933d4a963def02417113b6798d87a36395053b0rse k1 ^= tail[2] << 16;
176c2742db03fcb7b7d13e6408dd967d87e542e9ben case 2:
e0c3fda9f782aee1140d83fbce32672ac299f2a4ben k1 ^= tail[1] << 8;
3a8856c9ca9e996d3a1fae2c65943c35eed97481rpluem case 1:
7933d4a963def02417113b6798d87a36395053b0rse k1 ^= tail[0];
7933d4a963def02417113b6798d87a36395053b0rse k1 *= c1;
7933d4a963def02417113b6798d87a36395053b0rse k1 = rotl(k1, 15);
7933d4a963def02417113b6798d87a36395053b0rse k1 *= c2;
7933d4a963def02417113b6798d87a36395053b0rse h1 ^= k1;
7933d4a963def02417113b6798d87a36395053b0rse default:
e335319a08e12eb7daff9afa80e985dc53f652b8jorton break;
e335319a08e12eb7daff9afa80e985dc53f652b8jorton }
e335319a08e12eb7daff9afa80e985dc53f652b8jorton
e335319a08e12eb7daff9afa80e985dc53f652b8jorton /* finalization */
e335319a08e12eb7daff9afa80e985dc53f652b8jorton
e335319a08e12eb7daff9afa80e985dc53f652b8jorton h1 ^= len;
7933d4a963def02417113b6798d87a36395053b0rse h1 = fmix(h1);
7933d4a963def02417113b6798d87a36395053b0rse
7933d4a963def02417113b6798d87a36395053b0rse return h1;
7933d4a963def02417113b6798d87a36395053b0rse}
7933d4a963def02417113b6798d87a36395053b0rse
7933d4a963def02417113b6798d87a36395053b0rse
7933d4a963def02417113b6798d87a36395053b0rse