1#include "murmur3.h" 2 3static inline uint32_t rotl32(uint32_t x, int8_t r) 4{ 5 return (x << r) | (x >> (32 - r)); 6} 7 8//----------------------------------------------------------------------------- 9// Finalization mix - force all bits of a hash block to avalanche 10 11static inline uint32_t fmix32(uint32_t h) 12{ 13 h ^= h >> 16; 14 h *= 0x85ebca6b; 15 h ^= h >> 13; 16 h *= 0xc2b2ae35; 17 h ^= h >> 16; 18 19 return h; 20} 21 22static uint32_t murmur3_tail(const uint8_t *data, const int nblocks, 23 uint32_t len, const uint32_t c1, 24 const uint32_t c2, uint32_t h1) 25{ 26 const uint8_t *tail = (const uint8_t *)(data + nblocks * 4); 27 28 uint32_t k1 = 0; 29 switch (len & 3) { 30 case 3: 31 k1 ^= tail[2] << 16; 32 case 2: 33 k1 ^= tail[1] << 8; 34 case 1: 35 k1 ^= tail[0]; 36 k1 *= c1; 37 k1 = rotl32(k1, 15); 38 k1 *= c2; 39 h1 ^= k1; 40 }; 41 42 return fmix32(h1 ^ len); 43} 44 45uint32_t murmurhash3(const void *key, uint32_t len, uint32_t seed) 46{ 47 const uint8_t *data = (const uint8_t *)key; 48 const int nblocks = len / 4; 49 uint32_t h1 = seed; 50 const uint32_t c1 = 0xcc9e2d51; 51 const uint32_t c2 = 0x1b873593; 52 const uint32_t *blocks = (const uint32_t *)(data + nblocks * 4); 53 int i; 54 55 for (i = -nblocks; i; i++) { 56 uint32_t k1 = blocks[i]; 57 58 k1 *= c1; 59 k1 = rotl32(k1, 15); 60 k1 *= c2; 61 62 h1 ^= k1; 63 h1 = rotl32(h1, 13); 64 h1 = h1 * 5 + 0xe6546b64; 65 } 66 67 return murmur3_tail(data, nblocks, len, c1, c2, h1); 68} 69