45 namespace Murmur3Implementation {
69 inline uint32_t
rotl32 ( uint32_t
x, int8_t r )
71 return (x << r) | (x >> (32 - r));
74 inline uint64_t
rotl64 ( uint64_t
x, int8_t r )
76 return (x << r) | (x >> (64 - r));
79 #define BIG_CONSTANT(x) (x##LLU)
85 inline uint32_t
getblock (
const uint32_t * p,
int i )
90 inline uint64_t
getblock (
const uint64_t * p,
int i )
98 inline uint32_t
fmix ( uint32_t h )
111 inline uint64_t
fmix ( uint64_t k )
126 uint32_t seed,
void * out );
128 uint32_t seed,
void * out );
132 uint32_t seed,
void * out )
140 uint32_t seed,
void * out )
142 const uint8_t *
data = (
const uint8_t*)key;
143 const int nblocks = len / 4;
147 uint32_t c1 = 0xcc9e2d51;
148 uint32_t c2 = 0x1b873593;
153 const uint32_t * blocks = (
const uint32_t *)(data + nblocks*4);
155 for(
int i = -nblocks; i; i++)
165 h1 = h1*5+0xe6546b64;
171 const uint8_t * tail = (
const uint8_t*)(data + nblocks*4);
177 case 3: k1 ^= tail[2] << 16;
178 case 2: k1 ^= tail[1] << 8;
179 case 1: k1 ^= tail[0];
180 k1 *= c1; k1 =
rotl32(k1,15); k1 *= c2; h1 ^= k1;
183 *(uint32_t *)out = h1;
188 uint32_t seed,
void * out )
199 *(uint32_t *)out = h1;
206 uint32_t * seeds,
void * out );
208 uint32_t * seeds,
void * out );
212 uint32_t seed,
void * out )
216 seeds[0] = seeds[1] = seeds[2] = seeds[3] = seed;
222 uint32_t * seeds,
void * out )
224 const uint8_t *
data = (
const uint8_t*)key;
225 const int nblocks = len / 16;
227 uint32_t h1 = seeds[0];
228 uint32_t h2 = seeds[1];
229 uint32_t h3 = seeds[2];
230 uint32_t h4 = seeds[3];
232 uint32_t c1 = 0x239b961b;
233 uint32_t c2 = 0xab0e9789;
234 uint32_t c3 = 0x38b34ae5;
235 uint32_t c4 = 0xa1e38b93;
240 const uint32_t * blocks = (
const uint32_t *)(data + nblocks*16);
242 for(
int i = -nblocks; i; i++)
244 uint32_t k1 =
getblock(blocks,i*4+0);
245 uint32_t k2 =
getblock(blocks,i*4+1);
246 uint32_t k3 =
getblock(blocks,i*4+2);
247 uint32_t k4 =
getblock(blocks,i*4+3);
249 k1 *= c1; k1 =
rotl32(k1,15); k1 *= c2; h1 ^= k1;
251 h1 =
rotl32(h1,19); h1 += h2; h1 = h1*5+0x561ccd1b;
253 k2 *= c2; k2 =
rotl32(k2,16); k2 *= c3; h2 ^= k2;
255 h2 =
rotl32(h2,17); h2 += h3; h2 = h2*5+0x0bcaa747;
257 k3 *= c3; k3 =
rotl32(k3,17); k3 *= c4; h3 ^= k3;
259 h3 =
rotl32(h3,15); h3 += h4; h3 = h3*5+0x96cd1c35;
261 k4 *= c4; k4 =
rotl32(k4,18); k4 *= c1; h4 ^= k4;
263 h4 =
rotl32(h4,13); h4 += h1; h4 = h4*5+0x32ac3b17;
269 const uint8_t * tail = (
const uint8_t*)(data + nblocks*16);
278 case 15: k4 ^= tail[14] << 16;
279 case 14: k4 ^= tail[13] << 8;
280 case 13: k4 ^= tail[12] << 0;
281 k4 *= c4; k4 =
rotl32(k4,18); k4 *= c1; h4 ^= k4;
283 case 12: k3 ^= tail[11] << 24;
284 case 11: k3 ^= tail[10] << 16;
285 case 10: k3 ^= tail[ 9] << 8;
286 case 9: k3 ^= tail[ 8] << 0;
287 k3 *= c3; k3 =
rotl32(k3,17); k3 *= c4; h3 ^= k3;
289 case 8: k2 ^= tail[ 7] << 24;
290 case 7: k2 ^= tail[ 6] << 16;
291 case 6: k2 ^= tail[ 5] << 8;
292 case 5: k2 ^= tail[ 4] << 0;
293 k2 *= c2; k2 =
rotl32(k2,16); k2 *= c3; h2 ^= k2;
295 case 4: k1 ^= tail[ 3] << 24;
296 case 3: k1 ^= tail[ 2] << 16;
297 case 2: k1 ^= tail[ 1] << 8;
298 case 1: k1 ^= tail[ 0] << 0;
299 k1 *= c1; k1 =
rotl32(k1,15); k1 *= c2; h1 ^= k1;
302 ((uint32_t *)out)[0] = h1;
303 ((uint32_t *)out)[1] = h2;
304 ((uint32_t *)out)[2] = h3;
305 ((uint32_t *)out)[3] = h4;
310 uint32_t * seeds,
void * out )
315 uint32_t h1 = seeds[0];
316 uint32_t h2 = seeds[1];
317 uint32_t h3 = seeds[2];
318 uint32_t h4 = seeds[3];
320 h1 ^= len; h2 ^= len; h3 ^= len; h4 ^= len;
322 h1 += h2; h1 += h3; h1 += h4;
323 h2 += h1; h3 += h1; h4 += h1;
330 h1 += h2; h1 += h3; h1 += h4;
331 h2 += h1; h3 += h1; h4 += h1;
333 ((uint32_t *)out)[0] = h1;
334 ((uint32_t *)out)[1] = h2;
335 ((uint32_t *)out)[2] = h3;
336 ((uint32_t *)out)[3] = h4;
342 const uint32_t seed,
void * out )
344 const uint8_t *
data = (
const uint8_t*)key;
345 const int nblocks = len / 16;
356 const uint64_t * blocks = (
const uint64_t *)(data);
358 for(
int i = 0; i < nblocks; i++)
360 uint64_t k1 =
getblock(blocks,i*2+0);
361 uint64_t k2 =
getblock(blocks,i*2+1);
363 k1 *= c1; k1 =
rotl64(k1,31); k1 *= c2; h1 ^= k1;
365 h1 =
rotl64(h1,27); h1 += h2; h1 = h1*5+0x52dce729;
367 k2 *= c2; k2 =
rotl64(k2,33); k2 *= c1; h2 ^= k2;
369 h2 =
rotl64(h2,31); h2 += h1; h2 = h2*5+0x38495ab5;
375 const uint8_t * tail = (
const uint8_t*)(data + nblocks*16);
382 case 15: k2 ^= uint64_t(tail[14]) << 48;
383 case 14: k2 ^= uint64_t(tail[13]) << 40;
384 case 13: k2 ^= uint64_t(tail[12]) << 32;
385 case 12: k2 ^= uint64_t(tail[11]) << 24;
386 case 11: k2 ^= uint64_t(tail[10]) << 16;
387 case 10: k2 ^= uint64_t(tail[ 9]) << 8;
388 case 9: k2 ^= uint64_t(tail[ 8]) << 0;
389 k2 *= c2; k2 =
rotl64(k2,33); k2 *= c1; h2 ^= k2;
391 case 8: k1 ^= uint64_t(tail[ 7]) << 56;
392 case 7: k1 ^= uint64_t(tail[ 6]) << 48;
393 case 6: k1 ^= uint64_t(tail[ 5]) << 40;
394 case 5: k1 ^= uint64_t(tail[ 4]) << 32;
395 case 4: k1 ^= uint64_t(tail[ 3]) << 24;
396 case 3: k1 ^= uint64_t(tail[ 2]) << 16;
397 case 2: k1 ^= uint64_t(tail[ 1]) << 8;
398 case 1: k1 ^= uint64_t(tail[ 0]) << 0;
399 k1 *= c1; k1 =
rotl64(k1,31); k1 *= c2; h1 ^= k1;
405 h1 ^= len; h2 ^= len;
416 ((uint32_t *)out)[0] = h1;
417 ((uint32_t *)out)[1] = h2;
440 using namespace Murmur3Implementation;
453 using namespace Murmur3Implementation;
473 (uint32_t *)(
void *)
m_hash64, hash);
474 uint64_t result = hash[1];
475 result = (result << 32) | hash[0];
uint32_t m_size32
Cache last hash value, and total bytes hashed (needed to finalize), for incremental hashing...
void MurmurHash3_x64_128(const void *key, const int len, const uint32_t seed, void *out)
virtual void clear(void)
Restore initial state.
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
uint64_t rotl64(uint64_t x, int8_t r)
void MurmurHash3_x86_32(const void *key, int len, uint32_t seed, void *out)
uint32_t fmix(uint32_t h)
uint32_t rotl32(uint32_t x, int8_t r)
void MurmurHash3_x86_32_incr(const void *key, int len, uint32_t seed, void *out)
void MurmurHash3_x86_128(const void *key, const int len, uint32_t seed, void *out)
Murmur3()
Constructor, clears internal state.
uint32_t getblock(const uint32_t *p, int i)
uint64_t m_size64
Cache last hash value, and total bytes hashed (needed to finalize), for incremental hashing...
uint64_t GetHash64(const char *buffer, const size_t size)
Compute 64-bit hash of a byte buffer.
void MurmurHash3_x86_32_fin(int len, uint32_t seed, void *out)
void MurmurHash3_x86_128_fin(const int len, uint32_t *seeds, void *out)
void MurmurHash3_x86_128_incr(const void *key, const int len, uint32_t *seeds, void *out)
uint32_t m_hash32
Cache last hash value, and total bytes hashed (needed to finalize), for incremental hashing...
uint64_t m_hash64[2]
murmur3 produces 128-bit hash and state; we use just the first 64-bits.
uint32_t GetHash32(const char *buffer, const size_t size)
Compute 32-bit hash of a byte buffer.