1f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 2f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// MurmurHash3 was written by Austin Appleby, and is placed in the public 3f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// domain. The author hereby disclaims copyright to this source code. 4f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 5f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// Note - The x86 and x64 versions do _not_ produce the same results, as the 6f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// algorithms are optimized for their respective platforms. You can still 7f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// compile and run any of them on any platform, but your performance with the 8f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// non-native version will be less than optimal. 9f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 10f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#include "MurmurHash3.h" 11f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 12f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 13f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// Platform-specific functions and macros 14f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 15f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// Microsoft Visual Studio 16f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 17f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#if defined(_MSC_VER) 18f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 19f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#define FORCE_INLINE __forceinline 20f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 21f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#include <stdlib.h> 22f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 23f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#define ROTL32(x,y) _rotl(x,y) 24f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#define ROTL64(x,y) _rotl64(x,y) 25f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 26f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#define BIG_CONSTANT(x) (x) 27f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 28f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// Other compilers 29f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 30f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#else // defined(_MSC_VER) 31f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 326f63a4882e6b2cf87e8eec1a3ef8644e0d963283tanjent@gmail.com#define FORCE_INLINE inline __attribute__((always_inline)) 33f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 34f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.cominline uint32_t rotl32 ( uint32_t x, int8_t r ) 35f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 36f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com return (x << r) | (x >> (32 - r)); 37f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 38f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 39f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.cominline uint64_t rotl64 ( uint64_t x, int8_t r ) 40f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 41f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com return (x << r) | (x >> (64 - r)); 42f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 43f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 44f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#define ROTL32(x,y) rotl32(x,y) 45f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#define ROTL64(x,y) rotl64(x,y) 46f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 47f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#define BIG_CONSTANT(x) (x##LLU) 48f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 49f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#endif // !defined(_MSC_VER) 50f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 51f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 52f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// Block read - if your platform needs to do endian-swapping or can only 53f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// handle aligned reads, do the conversion here 54f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 555b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.comFORCE_INLINE uint32_t getblock32 ( const uint32_t * p, int i ) 56f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 57f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com return p[i]; 58f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 59f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 605b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.comFORCE_INLINE uint64_t getblock64 ( const uint64_t * p, int i ) 61f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 62f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com return p[i]; 63f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 64f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 65f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 66f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// Finalization mix - force all bits of a hash block to avalanche 67f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 685b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.comFORCE_INLINE uint32_t fmix32 ( uint32_t h ) 69f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 70f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h ^= h >> 16; 71f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h *= 0x85ebca6b; 72f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h ^= h >> 13; 73f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h *= 0xc2b2ae35; 74f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h ^= h >> 16; 75f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 76f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com return h; 77f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 78f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 79f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//---------- 80f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 815b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.comFORCE_INLINE uint64_t fmix64 ( uint64_t k ) 82f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 83f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k ^= k >> 33; 84f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k *= BIG_CONSTANT(0xff51afd7ed558ccd); 85f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k ^= k >> 33; 86f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53); 87f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k ^= k >> 33; 88f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 89f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com return k; 90f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 91f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 92f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 93f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 94f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comvoid MurmurHash3_x86_32 ( const void * key, int len, 95f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t seed, void * out ) 96f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 97f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const uint8_t * data = (const uint8_t*)key; 98f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int nblocks = len / 4; 99f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 100f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t h1 = seed; 101f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 102e813f9b95be7adad5a2e441f4484278c453e5261tanjent@gmail.com const uint32_t c1 = 0xcc9e2d51; 103e813f9b95be7adad5a2e441f4484278c453e5261tanjent@gmail.com const uint32_t c2 = 0x1b873593; 104f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 105f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com //---------- 106f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // body 107f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 108f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const uint32_t * blocks = (const uint32_t *)(data + nblocks*4); 109f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 110f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int i = -nblocks; i; i++) 111f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 1125b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com uint32_t k1 = getblock32(blocks,i); 113f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 114f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k1 *= c1; 115f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k1 = ROTL32(k1,15); 116f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k1 *= c2; 117f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 118f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h1 ^= k1; 119f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h1 = ROTL32(h1,13); 120f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h1 = h1*5+0xe6546b64; 121f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 122f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 123f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com //---------- 124f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // tail 125f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 126f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const uint8_t * tail = (const uint8_t*)(data + nblocks*4); 127f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 128f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t k1 = 0; 129f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 130f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com switch(len & 3) 131f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 132f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 3: k1 ^= tail[2] << 16; 133f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 2: k1 ^= tail[1] << 8; 134f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 1: k1 ^= tail[0]; 135f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1; 136f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com }; 137f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 138f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com //---------- 139f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // finalization 140f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 141f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h1 ^= len; 142f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 1435b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com h1 = fmix32(h1); 144f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 145f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com *(uint32_t*)out = h1; 146f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 147f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 148f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 149f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 150f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comvoid MurmurHash3_x86_128 ( const void * key, const int len, 151f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t seed, void * out ) 152f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 153f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const uint8_t * data = (const uint8_t*)key; 154f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int nblocks = len / 16; 155f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 156f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t h1 = seed; 157f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t h2 = seed; 158f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t h3 = seed; 159f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t h4 = seed; 160f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 161e813f9b95be7adad5a2e441f4484278c453e5261tanjent@gmail.com const uint32_t c1 = 0x239b961b; 162e813f9b95be7adad5a2e441f4484278c453e5261tanjent@gmail.com const uint32_t c2 = 0xab0e9789; 163e813f9b95be7adad5a2e441f4484278c453e5261tanjent@gmail.com const uint32_t c3 = 0x38b34ae5; 164e813f9b95be7adad5a2e441f4484278c453e5261tanjent@gmail.com const uint32_t c4 = 0xa1e38b93; 165f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 166f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com //---------- 167f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // body 168f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 169f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const uint32_t * blocks = (const uint32_t *)(data + nblocks*16); 170f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 171f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int i = -nblocks; i; i++) 172f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 1735b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com uint32_t k1 = getblock32(blocks,i*4+0); 1745b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com uint32_t k2 = getblock32(blocks,i*4+1); 1755b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com uint32_t k3 = getblock32(blocks,i*4+2); 1765b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com uint32_t k4 = getblock32(blocks,i*4+3); 177f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 178f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1; 179f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 180f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h1 = ROTL32(h1,19); h1 += h2; h1 = h1*5+0x561ccd1b; 181f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 182f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k2 *= c2; k2 = ROTL32(k2,16); k2 *= c3; h2 ^= k2; 183f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 184f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h2 = ROTL32(h2,17); h2 += h3; h2 = h2*5+0x0bcaa747; 185f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 186f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k3 *= c3; k3 = ROTL32(k3,17); k3 *= c4; h3 ^= k3; 187f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 188f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h3 = ROTL32(h3,15); h3 += h4; h3 = h3*5+0x96cd1c35; 189f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 190f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k4 *= c4; k4 = ROTL32(k4,18); k4 *= c1; h4 ^= k4; 191f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 192f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h4 = ROTL32(h4,13); h4 += h1; h4 = h4*5+0x32ac3b17; 193f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 194f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 195f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com //---------- 196f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // tail 197f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 198f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const uint8_t * tail = (const uint8_t*)(data + nblocks*16); 199f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 200f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t k1 = 0; 201f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t k2 = 0; 202f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t k3 = 0; 203f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t k4 = 0; 204f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 205f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com switch(len & 15) 206f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 207f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 15: k4 ^= tail[14] << 16; 208f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 14: k4 ^= tail[13] << 8; 209f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 13: k4 ^= tail[12] << 0; 210f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k4 *= c4; k4 = ROTL32(k4,18); k4 *= c1; h4 ^= k4; 211f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 212f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 12: k3 ^= tail[11] << 24; 213f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 11: k3 ^= tail[10] << 16; 214f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 10: k3 ^= tail[ 9] << 8; 215f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 9: k3 ^= tail[ 8] << 0; 216f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k3 *= c3; k3 = ROTL32(k3,17); k3 *= c4; h3 ^= k3; 217f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 218f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 8: k2 ^= tail[ 7] << 24; 219f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 7: k2 ^= tail[ 6] << 16; 220f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 6: k2 ^= tail[ 5] << 8; 221f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 5: k2 ^= tail[ 4] << 0; 222f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k2 *= c2; k2 = ROTL32(k2,16); k2 *= c3; h2 ^= k2; 223f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 224f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 4: k1 ^= tail[ 3] << 24; 225f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 3: k1 ^= tail[ 2] << 16; 226f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 2: k1 ^= tail[ 1] << 8; 227f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 1: k1 ^= tail[ 0] << 0; 228f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1; 229f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com }; 230f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 231f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com //---------- 232f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // finalization 233f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 234f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h1 ^= len; h2 ^= len; h3 ^= len; h4 ^= len; 235f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 236f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h1 += h2; h1 += h3; h1 += h4; 237f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h2 += h1; h3 += h1; h4 += h1; 238f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 2395b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com h1 = fmix32(h1); 2405b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com h2 = fmix32(h2); 2415b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com h3 = fmix32(h3); 2425b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com h4 = fmix32(h4); 243f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 244f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h1 += h2; h1 += h3; h1 += h4; 245f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h2 += h1; h3 += h1; h4 += h1; 246f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 247f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com ((uint32_t*)out)[0] = h1; 248f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com ((uint32_t*)out)[1] = h2; 249f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com ((uint32_t*)out)[2] = h3; 250f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com ((uint32_t*)out)[3] = h4; 251f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 252f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 253f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 254f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 255f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comvoid MurmurHash3_x64_128 ( const void * key, const int len, 256f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const uint32_t seed, void * out ) 257f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 258f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const uint8_t * data = (const uint8_t*)key; 259f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int nblocks = len / 16; 260f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 261f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint64_t h1 = seed; 262f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint64_t h2 = seed; 263f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 264e813f9b95be7adad5a2e441f4484278c453e5261tanjent@gmail.com const uint64_t c1 = BIG_CONSTANT(0x87c37b91114253d5); 265e813f9b95be7adad5a2e441f4484278c453e5261tanjent@gmail.com const uint64_t c2 = BIG_CONSTANT(0x4cf5ad432745937f); 266f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 267f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com //---------- 268f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // body 269f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 270f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const uint64_t * blocks = (const uint64_t *)(data); 271f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 272f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com for(int i = 0; i < nblocks; i++) 273f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 2745b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com uint64_t k1 = getblock64(blocks,i*2+0); 2755b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com uint64_t k2 = getblock64(blocks,i*2+1); 276f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 277f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k1 *= c1; k1 = ROTL64(k1,31); k1 *= c2; h1 ^= k1; 278f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 279f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h1 = ROTL64(h1,27); h1 += h2; h1 = h1*5+0x52dce729; 280f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 281f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k2 *= c2; k2 = ROTL64(k2,33); k2 *= c1; h2 ^= k2; 282f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 283f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h2 = ROTL64(h2,31); h2 += h1; h2 = h2*5+0x38495ab5; 284f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 285f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 286f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com //---------- 287f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // tail 288f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 289f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const uint8_t * tail = (const uint8_t*)(data + nblocks*16); 290f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 291f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint64_t k1 = 0; 292f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint64_t k2 = 0; 293f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 294f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com switch(len & 15) 295f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 2965b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com case 15: k2 ^= ((uint64_t)tail[14]) << 48; 2975b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com case 14: k2 ^= ((uint64_t)tail[13]) << 40; 2985b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com case 13: k2 ^= ((uint64_t)tail[12]) << 32; 2995b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com case 12: k2 ^= ((uint64_t)tail[11]) << 24; 3005b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com case 11: k2 ^= ((uint64_t)tail[10]) << 16; 3015b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com case 10: k2 ^= ((uint64_t)tail[ 9]) << 8; 3025b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com case 9: k2 ^= ((uint64_t)tail[ 8]) << 0; 303f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k2 *= c2; k2 = ROTL64(k2,33); k2 *= c1; h2 ^= k2; 304f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 3055b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com case 8: k1 ^= ((uint64_t)tail[ 7]) << 56; 3065b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com case 7: k1 ^= ((uint64_t)tail[ 6]) << 48; 3075b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com case 6: k1 ^= ((uint64_t)tail[ 5]) << 40; 3085b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com case 5: k1 ^= ((uint64_t)tail[ 4]) << 32; 3095b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com case 4: k1 ^= ((uint64_t)tail[ 3]) << 24; 3105b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com case 3: k1 ^= ((uint64_t)tail[ 2]) << 16; 3115b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com case 2: k1 ^= ((uint64_t)tail[ 1]) << 8; 3125b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com case 1: k1 ^= ((uint64_t)tail[ 0]) << 0; 313f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k1 *= c1; k1 = ROTL64(k1,31); k1 *= c2; h1 ^= k1; 314f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com }; 315f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 316f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com //---------- 317f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // finalization 318f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 319f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h1 ^= len; h2 ^= len; 320f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 321f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h1 += h2; 322f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h2 += h1; 323f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 3245b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com h1 = fmix64(h1); 3255b8fd3c31a58b87b80605dca7a64fad6cb3f8a0faappleby@google.com h2 = fmix64(h2); 326f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 327f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h1 += h2; 328f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h2 += h1; 329f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 330f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com ((uint64_t*)out)[0] = h1; 331f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com ((uint64_t*)out)[1] = h2; 332f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 333f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 334f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 335f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 336