53 namespace Murmur3Implementation {
91 inline uint32_t
rotl32 ( uint32_t
x, int8_t r )
93 return (x << r) | (x >> (32 - r));
103 inline uint64_t
rotl64 ( uint64_t
x, int8_t r )
105 return (x << r) | (x >> (64 - r));
109 #define BIG_CONSTANT(x) (x##LLU)
122 inline uint32_t
getblock (
const uint32_t * p,
int i )
127 inline uint64_t
getblock (
const uint64_t * p,
int i )
139 inline uint32_t
fmix ( uint32_t h )
152 inline uint64_t
fmix ( uint64_t h )
175 uint32_t seed,
void * out );
184 uint32_t seed,
void * out );
189 uint32_t seed,
void * out )
197 uint32_t seed,
void * out )
199 const uint8_t *
data = (
const uint8_t*)key;
200 const int nblocks = len / 4;
204 uint32_t c1 = 0xcc9e2d51;
205 uint32_t c2 = 0x1b873593;
210 const uint32_t * blocks = (
const uint32_t *)(data + nblocks*4);
212 for(
int i = -nblocks; i; i++)
222 h1 = h1*5+0xe6546b64;
228 const uint8_t * tail = (
const uint8_t*)(data + nblocks*4);
234 case 3: k1 ^= tail[2] << 16;
235 case 2: k1 ^= tail[1] << 8;
236 case 1: k1 ^= tail[0];
237 k1 *= c1; k1 =
rotl32(k1,15); k1 *= c2; h1 ^= k1;
240 *(uint32_t *)out = h1;
245 uint32_t seed,
void * out )
256 *(uint32_t *)out = h1;
271 uint32_t * seeds,
void * out );
280 uint32_t * seeds,
void * out );
292 uint32_t seed,
void * out )
296 seeds[0] = seeds[1] = seeds[2] = seeds[3] = seed;
302 uint32_t * seeds,
void * out )
304 const uint8_t *
data = (
const uint8_t*)key;
305 const int nblocks = len / 16;
307 uint32_t h1 = seeds[0];
308 uint32_t h2 = seeds[1];
309 uint32_t h3 = seeds[2];
310 uint32_t h4 = seeds[3];
312 uint32_t c1 = 0x239b961b;
313 uint32_t c2 = 0xab0e9789;
314 uint32_t c3 = 0x38b34ae5;
315 uint32_t c4 = 0xa1e38b93;
320 const uint32_t * blocks = (
const uint32_t *)(data + nblocks*16);
322 for(
int i = -nblocks; i; i++)
324 uint32_t k1 =
getblock(blocks,i*4+0);
325 uint32_t k2 =
getblock(blocks,i*4+1);
326 uint32_t k3 =
getblock(blocks,i*4+2);
327 uint32_t k4 =
getblock(blocks,i*4+3);
329 k1 *= c1; k1 =
rotl32(k1,15); k1 *= c2; h1 ^= k1;
331 h1 =
rotl32(h1,19); h1 += h2; h1 = h1*5+0x561ccd1b;
333 k2 *= c2; k2 =
rotl32(k2,16); k2 *= c3; h2 ^= k2;
335 h2 =
rotl32(h2,17); h2 += h3; h2 = h2*5+0x0bcaa747;
337 k3 *= c3; k3 =
rotl32(k3,17); k3 *= c4; h3 ^= k3;
339 h3 =
rotl32(h3,15); h3 += h4; h3 = h3*5+0x96cd1c35;
341 k4 *= c4; k4 =
rotl32(k4,18); k4 *= c1; h4 ^= k4;
343 h4 =
rotl32(h4,13); h4 += h1; h4 = h4*5+0x32ac3b17;
349 const uint8_t * tail = (
const uint8_t*)(data + nblocks*16);
358 case 15: k4 ^= tail[14] << 16;
359 case 14: k4 ^= tail[13] << 8;
360 case 13: k4 ^= tail[12] << 0;
361 k4 *= c4; k4 =
rotl32(k4,18); k4 *= c1; h4 ^= k4;
363 case 12: k3 ^= tail[11] << 24;
364 case 11: k3 ^= tail[10] << 16;
365 case 10: k3 ^= tail[ 9] << 8;
366 case 9: k3 ^= tail[ 8] << 0;
367 k3 *= c3; k3 =
rotl32(k3,17); k3 *= c4; h3 ^= k3;
369 case 8: k2 ^= tail[ 7] << 24;
370 case 7: k2 ^= tail[ 6] << 16;
371 case 6: k2 ^= tail[ 5] << 8;
372 case 5: k2 ^= tail[ 4] << 0;
373 k2 *= c2; k2 =
rotl32(k2,16); k2 *= c3; h2 ^= k2;
375 case 4: k1 ^= tail[ 3] << 24;
376 case 3: k1 ^= tail[ 2] << 16;
377 case 2: k1 ^= tail[ 1] << 8;
378 case 1: k1 ^= tail[ 0] << 0;
379 k1 *= c1; k1 =
rotl32(k1,15); k1 *= c2; h1 ^= k1;
382 ((uint32_t *)out)[0] = h1;
383 ((uint32_t *)out)[1] = h2;
384 ((uint32_t *)out)[2] = h3;
385 ((uint32_t *)out)[3] = h4;
390 uint32_t * seeds,
void * out )
395 uint32_t h1 = seeds[0];
396 uint32_t h2 = seeds[1];
397 uint32_t h3 = seeds[2];
398 uint32_t h4 = seeds[3];
400 h1 ^= len; h2 ^= len; h3 ^= len; h4 ^= len;
402 h1 += h2; h1 += h3; h1 += h4;
403 h2 += h1; h3 += h1; h4 += h1;
410 h1 += h2; h1 += h3; h1 += h4;
411 h2 += h1; h3 += h1; h4 += h1;
413 ((uint32_t *)out)[0] = h1;
414 ((uint32_t *)out)[1] = h2;
415 ((uint32_t *)out)[2] = h3;
416 ((uint32_t *)out)[3] = h4;
422 const uint32_t seed,
void * out )
424 const uint8_t *
data = (
const uint8_t*)key;
425 const int nblocks = len / 16;
436 const uint64_t * blocks = (
const uint64_t *)(data);
438 for(
int i = 0; i < nblocks; i++)
440 uint64_t k1 =
getblock(blocks,i*2+0);
441 uint64_t k2 =
getblock(blocks,i*2+1);
443 k1 *= c1; k1 =
rotl64(k1,31); k1 *= c2; h1 ^= k1;
445 h1 =
rotl64(h1,27); h1 += h2; h1 = h1*5+0x52dce729;
447 k2 *= c2; k2 =
rotl64(k2,33); k2 *= c1; h2 ^= k2;
449 h2 =
rotl64(h2,31); h2 += h1; h2 = h2*5+0x38495ab5;
455 const uint8_t * tail = (
const uint8_t*)(data + nblocks*16);
462 case 15: k2 ^= uint64_t(tail[14]) << 48;
463 case 14: k2 ^= uint64_t(tail[13]) << 40;
464 case 13: k2 ^= uint64_t(tail[12]) << 32;
465 case 12: k2 ^= uint64_t(tail[11]) << 24;
466 case 11: k2 ^= uint64_t(tail[10]) << 16;
467 case 10: k2 ^= uint64_t(tail[ 9]) << 8;
468 case 9: k2 ^= uint64_t(tail[ 8]) << 0;
469 k2 *= c2; k2 =
rotl64(k2,33); k2 *= c1; h2 ^= k2;
471 case 8: k1 ^= uint64_t(tail[ 7]) << 56;
472 case 7: k1 ^= uint64_t(tail[ 6]) << 48;
473 case 6: k1 ^= uint64_t(tail[ 5]) << 40;
474 case 5: k1 ^= uint64_t(tail[ 4]) << 32;
475 case 4: k1 ^= uint64_t(tail[ 3]) << 24;
476 case 3: k1 ^= uint64_t(tail[ 2]) << 16;
477 case 2: k1 ^= uint64_t(tail[ 1]) << 8;
478 case 1: k1 ^= uint64_t(tail[ 0]) << 0;
479 k1 *= c1; k1 =
rotl64(k1,31); k1 *= c2; h1 ^= k1;
485 h1 ^= len; h2 ^= len;
496 ((uint32_t *)out)[0] = h1;
497 ((uint32_t *)out)[1] = h2;
522 using namespace Murmur3Implementation;
535 using namespace Murmur3Implementation;
555 (uint32_t *)(
void *)
m_hash64, hash);
556 uint64_t result = hash[1];
557 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_x86_32(const void *key, int len, uint32_t seed, void *out)
Initial and incremental hash.
void MurmurHash3_x86_32_incr(const void *key, int len, uint32_t seed, void *out)
Initial and incremental hash.
virtual void clear(void)
Restore initial state.
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
uint32_t getblock(const uint32_t *p, int i)
Block read.
void MurmurHash3_x64_128(const void *key, const int len, const uint32_t seed, void *out)
Initial and incremental hash.
void MurmurHash3_x86_128_fin(const int len, uint32_t *seeds, void *out)
Finalize a hash.
void MurmurHash3_x86_128_incr(const void *key, const int len, uint32_t *seeds, void *out)
Initial and incremental hash.
uint32_t rotl32(uint32_t x, int8_t r)
Barrel shift (rotate) left on 32 bits.
void MurmurHash3_x86_128(const void *key, const int len, uint32_t seed, void *out)
Initial and incremental hash.
uint64_t rotl64(uint64_t x, int8_t r)
Barrel shift (rotate) left on 64 bits.
void MurmurHash3_x86_32_fin(int len, uint32_t seed, void *out)
Finalize a hash.
uint32_t fmix(uint32_t h)
Finalization mix - force all bits of a hash block to avalanche.
Murmur3()
Constructor, clears internal state.
uint64_t m_size64
murmur3 produces 128-bit hash and state; we use just the first 64-bits.
uint64_t GetHash64(const char *buffer, const size_t size)
Compute 64-bit hash of a byte buffer.
ns3::Hash::Function::Murmur3 declaration.
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.
#define BIG_CONSTANT(x)
Unsigned long long constants.
uint32_t GetHash32(const char *buffer, const size_t size)
Compute 32-bit hash of a byte buffer.