12bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill//----------------------------------------------------------------------------- 22bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill// MurmurHash3 was written by Austin Appleby, and is placed in the public 32bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill// domain. The author hereby disclaims copyright to this source code. 42bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 52bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill// Note - The x86 and x64 versions do _not_ produce the same results, as the 62bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill// algorithms are optimized for their respective platforms. You can still 72bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill// compile and run any of them on any platform, but your performance with the 82bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill// non-native version will be less than optimal. 92bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 102bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill#include "MurmurHash3.h" 112bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 122bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill//----------------------------------------------------------------------------- 132bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill// Platform-specific functions and macros 142bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 152bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill// Microsoft Visual Studio 162bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 172bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill#if defined(_MSC_VER) 182bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 192bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill#define FORCE_INLINE __forceinline 202bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 212bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill#include <stdlib.h> 222bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 232bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill#define ROTL32(x,y) _rotl(x,y) 242bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill#define ROTL64(x,y) _rotl64(x,y) 252bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 262bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill#define BIG_CONSTANT(x) (x) 272bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 282bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill// Other compilers 292bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 302bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill#else // defined(_MSC_VER) 312bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 322bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill#define FORCE_INLINE __attribute__((always_inline)) 332bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 342bcc909963640803dafb5f5c8f296c1a467e814bJamie Madillinline uint32_t rotl32 ( uint32_t x, int8_t r ) 352bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill{ 362bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill return (x << r) | (x >> (32 - r)); 372bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill} 382bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 392bcc909963640803dafb5f5c8f296c1a467e814bJamie Madillinline uint64_t rotl64 ( uint64_t x, int8_t r ) 402bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill{ 412bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill return (x << r) | (x >> (64 - r)); 422bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill} 432bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 442bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill#define ROTL32(x,y) rotl32(x,y) 452bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill#define ROTL64(x,y) rotl64(x,y) 462bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 472bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill#define BIG_CONSTANT(x) (x##LLU) 482bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 492bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill#endif // !defined(_MSC_VER) 502bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 512bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill//----------------------------------------------------------------------------- 522bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill// Block read - if your platform needs to do endian-swapping or can only 532bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill// handle aligned reads, do the conversion here 542bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 552bcc909963640803dafb5f5c8f296c1a467e814bJamie MadillFORCE_INLINE uint32_t getblock ( const uint32_t * p, int i ) 562bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill{ 572bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill return p[i]; 582bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill} 592bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 602bcc909963640803dafb5f5c8f296c1a467e814bJamie MadillFORCE_INLINE uint64_t getblock ( const uint64_t * p, int i ) 612bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill{ 622bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill return p[i]; 632bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill} 642bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 652bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill//----------------------------------------------------------------------------- 662bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill// Finalization mix - force all bits of a hash block to avalanche 672bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 682bcc909963640803dafb5f5c8f296c1a467e814bJamie MadillFORCE_INLINE uint32_t fmix ( uint32_t h ) 692bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill{ 702bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h ^= h >> 16; 712bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h *= 0x85ebca6b; 722bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h ^= h >> 13; 732bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h *= 0xc2b2ae35; 742bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h ^= h >> 16; 752bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 762bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill return h; 772bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill} 782bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 792bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill//---------- 802bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 812bcc909963640803dafb5f5c8f296c1a467e814bJamie MadillFORCE_INLINE uint64_t fmix ( uint64_t k ) 822bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill{ 832bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill k ^= k >> 33; 842bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill k *= BIG_CONSTANT(0xff51afd7ed558ccd); 852bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill k ^= k >> 33; 862bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53); 872bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill k ^= k >> 33; 882bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 892bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill return k; 902bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill} 912bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 922bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill//----------------------------------------------------------------------------- 932bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 942bcc909963640803dafb5f5c8f296c1a467e814bJamie Madillvoid MurmurHash3_x86_32 ( const void * key, int len, 952bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill uint32_t seed, void * out ) 962bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill{ 972bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill const uint8_t * data = (const uint8_t*)key; 982bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill const int nblocks = len / 4; 992bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1002bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill uint32_t h1 = seed; 1012bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1022bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill const uint32_t c1 = 0xcc9e2d51; 1032bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill const uint32_t c2 = 0x1b873593; 1042bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1052bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill //---------- 1062bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill // body 1072bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1082bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill const uint32_t * blocks = (const uint32_t *)(data + nblocks*4); 1092bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1102bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill for(int i = -nblocks; i; i++) 1112bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill { 1122bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill uint32_t k1 = getblock(blocks,i); 1132bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1142bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill k1 *= c1; 1152bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill k1 = ROTL32(k1,15); 1162bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill k1 *= c2; 1172bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1182bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h1 ^= k1; 1192bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h1 = ROTL32(h1,13); 1202bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h1 = h1*5+0xe6546b64; 1212bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill } 1222bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1232bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill //---------- 1242bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill // tail 1252bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1262bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill const uint8_t * tail = (const uint8_t*)(data + nblocks*4); 1272bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1282bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill uint32_t k1 = 0; 1292bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1302bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill switch(len & 3) 1312bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill { 1322bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 3: k1 ^= tail[2] << 16; 1332bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 2: k1 ^= tail[1] << 8; 1342bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 1: k1 ^= tail[0]; 1352bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1; 1362bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill }; 1372bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1382bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill //---------- 1392bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill // finalization 1402bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1412bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h1 ^= len; 1422bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1432bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h1 = fmix(h1); 1442bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1452bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill *(uint32_t*)out = h1; 1462bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill} 1472bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1482bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill//----------------------------------------------------------------------------- 1492bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1502bcc909963640803dafb5f5c8f296c1a467e814bJamie Madillvoid MurmurHash3_x86_128 ( const void * key, const int len, 1512bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill uint32_t seed, void * out ) 1522bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill{ 1532bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill const uint8_t * data = (const uint8_t*)key; 1542bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill const int nblocks = len / 16; 1552bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1562bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill uint32_t h1 = seed; 1572bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill uint32_t h2 = seed; 1582bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill uint32_t h3 = seed; 1592bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill uint32_t h4 = seed; 1602bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1612bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill const uint32_t c1 = 0x239b961b; 1622bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill const uint32_t c2 = 0xab0e9789; 1632bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill const uint32_t c3 = 0x38b34ae5; 1642bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill const uint32_t c4 = 0xa1e38b93; 1652bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1662bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill //---------- 1672bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill // body 1682bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1692bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill const uint32_t * blocks = (const uint32_t *)(data + nblocks*16); 1702bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1712bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill for(int i = -nblocks; i; i++) 1722bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill { 1732bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill uint32_t k1 = getblock(blocks,i*4+0); 1742bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill uint32_t k2 = getblock(blocks,i*4+1); 1752bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill uint32_t k3 = getblock(blocks,i*4+2); 1762bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill uint32_t k4 = getblock(blocks,i*4+3); 1772bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1782bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1; 1792bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1802bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h1 = ROTL32(h1,19); h1 += h2; h1 = h1*5+0x561ccd1b; 1812bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1822bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill k2 *= c2; k2 = ROTL32(k2,16); k2 *= c3; h2 ^= k2; 1832bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1842bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h2 = ROTL32(h2,17); h2 += h3; h2 = h2*5+0x0bcaa747; 1852bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1862bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill k3 *= c3; k3 = ROTL32(k3,17); k3 *= c4; h3 ^= k3; 1872bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1882bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h3 = ROTL32(h3,15); h3 += h4; h3 = h3*5+0x96cd1c35; 1892bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1902bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill k4 *= c4; k4 = ROTL32(k4,18); k4 *= c1; h4 ^= k4; 1912bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1922bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h4 = ROTL32(h4,13); h4 += h1; h4 = h4*5+0x32ac3b17; 1932bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill } 1942bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1952bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill //---------- 1962bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill // tail 1972bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 1982bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill const uint8_t * tail = (const uint8_t*)(data + nblocks*16); 1992bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 2002bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill uint32_t k1 = 0; 2012bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill uint32_t k2 = 0; 2022bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill uint32_t k3 = 0; 2032bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill uint32_t k4 = 0; 2042bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 2052bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill switch(len & 15) 2062bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill { 2072bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 15: k4 ^= tail[14] << 16; 2082bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 14: k4 ^= tail[13] << 8; 2092bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 13: k4 ^= tail[12] << 0; 2102bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill k4 *= c4; k4 = ROTL32(k4,18); k4 *= c1; h4 ^= k4; 2112bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 2122bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 12: k3 ^= tail[11] << 24; 2132bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 11: k3 ^= tail[10] << 16; 2142bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 10: k3 ^= tail[ 9] << 8; 2152bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 9: k3 ^= tail[ 8] << 0; 2162bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill k3 *= c3; k3 = ROTL32(k3,17); k3 *= c4; h3 ^= k3; 2172bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 2182bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 8: k2 ^= tail[ 7] << 24; 2192bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 7: k2 ^= tail[ 6] << 16; 2202bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 6: k2 ^= tail[ 5] << 8; 2212bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 5: k2 ^= tail[ 4] << 0; 2222bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill k2 *= c2; k2 = ROTL32(k2,16); k2 *= c3; h2 ^= k2; 2232bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 2242bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 4: k1 ^= tail[ 3] << 24; 2252bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 3: k1 ^= tail[ 2] << 16; 2262bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 2: k1 ^= tail[ 1] << 8; 2272bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 1: k1 ^= tail[ 0] << 0; 2282bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1; 2292bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill }; 2302bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 2312bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill //---------- 2322bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill // finalization 2332bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 2342bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h1 ^= len; h2 ^= len; h3 ^= len; h4 ^= len; 2352bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 2362bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h1 += h2; h1 += h3; h1 += h4; 2372bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h2 += h1; h3 += h1; h4 += h1; 2382bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 2392bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h1 = fmix(h1); 2402bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h2 = fmix(h2); 2412bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h3 = fmix(h3); 2422bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h4 = fmix(h4); 2432bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 2442bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h1 += h2; h1 += h3; h1 += h4; 2452bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h2 += h1; h3 += h1; h4 += h1; 2462bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 2472bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill ((uint32_t*)out)[0] = h1; 2482bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill ((uint32_t*)out)[1] = h2; 2492bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill ((uint32_t*)out)[2] = h3; 2502bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill ((uint32_t*)out)[3] = h4; 2512bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill} 2522bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 2532bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill//----------------------------------------------------------------------------- 2542bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 2552bcc909963640803dafb5f5c8f296c1a467e814bJamie Madillvoid MurmurHash3_x64_128 ( const void * key, const int len, 2562bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill const uint32_t seed, void * out ) 2572bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill{ 2582bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill const uint8_t * data = (const uint8_t*)key; 2592bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill const int nblocks = len / 16; 2602bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 2612bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill uint64_t h1 = seed; 2622bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill uint64_t h2 = seed; 2632bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 2642bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill const uint64_t c1 = BIG_CONSTANT(0x87c37b91114253d5); 2652bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill const uint64_t c2 = BIG_CONSTANT(0x4cf5ad432745937f); 2662bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 2672bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill //---------- 2682bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill // body 2692bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 2702bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill const uint64_t * blocks = (const uint64_t *)(data); 2712bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 2722bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill for(int i = 0; i < nblocks; i++) 2732bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill { 2742bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill uint64_t k1 = getblock(blocks,i*2+0); 2752bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill uint64_t k2 = getblock(blocks,i*2+1); 2762bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 2772bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill k1 *= c1; k1 = ROTL64(k1,31); k1 *= c2; h1 ^= k1; 2782bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 2792bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h1 = ROTL64(h1,27); h1 += h2; h1 = h1*5+0x52dce729; 2802bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 2812bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill k2 *= c2; k2 = ROTL64(k2,33); k2 *= c1; h2 ^= k2; 2822bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 2832bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h2 = ROTL64(h2,31); h2 += h1; h2 = h2*5+0x38495ab5; 2842bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill } 2852bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 2862bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill //---------- 2872bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill // tail 2882bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 2892bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill const uint8_t * tail = (const uint8_t*)(data + nblocks*16); 2902bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 2912bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill uint64_t k1 = 0; 2922bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill uint64_t k2 = 0; 2932bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 2942bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill switch(len & 15) 2952bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill { 2962bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 15: k2 ^= uint64_t(tail[14]) << 48; 2972bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 14: k2 ^= uint64_t(tail[13]) << 40; 2982bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 13: k2 ^= uint64_t(tail[12]) << 32; 2992bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 12: k2 ^= uint64_t(tail[11]) << 24; 3002bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 11: k2 ^= uint64_t(tail[10]) << 16; 3012bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 10: k2 ^= uint64_t(tail[ 9]) << 8; 3022bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 9: k2 ^= uint64_t(tail[ 8]) << 0; 3032bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill k2 *= c2; k2 = ROTL64(k2,33); k2 *= c1; h2 ^= k2; 3042bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 3052bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 8: k1 ^= uint64_t(tail[ 7]) << 56; 3062bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 7: k1 ^= uint64_t(tail[ 6]) << 48; 3072bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 6: k1 ^= uint64_t(tail[ 5]) << 40; 3082bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 5: k1 ^= uint64_t(tail[ 4]) << 32; 3092bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 4: k1 ^= uint64_t(tail[ 3]) << 24; 3102bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 3: k1 ^= uint64_t(tail[ 2]) << 16; 3112bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 2: k1 ^= uint64_t(tail[ 1]) << 8; 3122bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill case 1: k1 ^= uint64_t(tail[ 0]) << 0; 3132bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill k1 *= c1; k1 = ROTL64(k1,31); k1 *= c2; h1 ^= k1; 3142bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill }; 3152bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 3162bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill //---------- 3172bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill // finalization 3182bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 3192bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h1 ^= len; h2 ^= len; 3202bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 3212bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h1 += h2; 3222bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h2 += h1; 3232bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 3242bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h1 = fmix(h1); 3252bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h2 = fmix(h2); 3262bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 3272bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h1 += h2; 3282bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill h2 += h1; 3292bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 3302bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill ((uint64_t*)out)[0] = h1; 3312bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill ((uint64_t*)out)[1] = h2; 3322bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill} 3332bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill 3342bcc909963640803dafb5f5c8f296c1a467e814bJamie Madill//----------------------------------------------------------------------------- 335