X-Git-Url: https://git.m6w6.name/?a=blobdiff_plain;f=src%2Flibhashkit%2Fmurmur3.cc;h=19ad0ec3a33abec89fe662896a3340acc73ca28f;hb=0d7a3e0e040ddf840d656b61f41419c252debcde;hp=0eda93199b0b71796bd6237e1f183f0fc0c090d3;hpb=04ef6e10123e867ca7e7b4b09f45e0e1a84aaf40;p=awesomized%2Flibmemcached diff --git a/src/libhashkit/murmur3.cc b/src/libhashkit/murmur3.cc index 0eda9319..19ad0ec3 100644 --- a/src/libhashkit/murmur3.cc +++ b/src/libhashkit/murmur3.cc @@ -1,11 +1,17 @@ -//----------------------------------------------------------------------------- -//MurmurHash3 was written by Austin Appleby, and is placed in the public -//domain. The author hereby disclaims copyright to this source code. - -// Note - The x86 and x64 versions do _not_ produce the same results, as the -// algorithms are optimized for their respective platforms. You can still -// compile and run any of them on any platform, but your performance with the -// non-native version will be less than optimal. +/* + +--------------------------------------------------------------------+ + | libmemcached-awesome - C/C++ Client Library for memcached | + +--------------------------------------------------------------------+ + | Redistribution and use in source and binary forms, with or without | + | modification, are permitted under the terms of the BSD license. | + | You should have received a copy of the license in a bundled file | + | named LICENSE; in case you did not receive a copy you can review | + | the terms online at: https://opensource.org/licenses/BSD-3-Clause | + +--------------------------------------------------------------------+ + | Copyright (c) 2006-2014 Brian Aker https://datadifferential.com/ | + | Copyright (c) 2020-2021 Michael Wallner https://awesome.co/ | + +--------------------------------------------------------------------+ +*/ #include "libhashkit/hashkitcon.h" @@ -15,25 +21,16 @@ // Platform-specific functions and macros #ifdef __GNUC__ -#define FORCE_INLINE __attribute__((always_inline)) inline +# define FORCE_INLINE __attribute__((always_inline)) inline #else -#define FORCE_INLINE inline +# define FORCE_INLINE inline #endif -static FORCE_INLINE uint32_t rotl32 ( uint32_t x, int8_t r ) -{ +static FORCE_INLINE uint32_t rotl32(uint32_t x, int8_t r) { return (x << r) | (x >> (32 - r)); } -static FORCE_INLINE uint64_t rotl64 ( uint64_t x, int8_t r ) -{ - return (x << r) | (x >> (64 - r)); -} - -#define ROTL32(x,y) rotl32(x,y) -#define ROTL64(x,y) rotl64(x,y) - -#define BIG_CONSTANT(x) (x##LLU) +#define ROTL32(x, y) rotl32(x, y) //----------------------------------------------------------------------------- // Block read - if your platform needs to do endian-swapping or can only @@ -41,35 +38,17 @@ static FORCE_INLINE uint64_t rotl64 ( uint64_t x, int8_t r ) #include #include -template +template static inline T getblock(const T *blocks, int i) { T b; -#if WORDS_BIGENDIAN - const uint8_t *data = ((const uint8_t *) blocks) + i * sizeof(T); -# define sl(s) (((T)data[s - 1]) << (8 * (sizeof(T) - s))) - b = 0; - switch (sizeof(T)) { - case 8: b |= sl(8); /* fall through */ - case 7: b |= sl(7); /* fall through */ - case 6: b |= sl(6); /* fall through */ - case 5: b |= sl(5); /* fall through */ - case 4: b |= sl(4); /* fall through */ - case 3: b |= sl(3); /* fall through */ - case 2: b |= sl(2); /* fall through */ - case 1: b |= sl(1); break; - default: assert(0); - } -#else memcpy(&b, ((const uint8_t *) blocks) + i * sizeof(T), sizeof(T)); -#endif return b; } //----------------------------------------------------------------------------- // Finalization mix - force all bits of a hash block to avalanche -static FORCE_INLINE uint32_t fmix32 ( uint32_t h ) -{ +static FORCE_INLINE uint32_t fmix32(uint32_t h) { h ^= h >> 16; h *= 0x85ebca6b; h ^= h >> 13; @@ -79,25 +58,10 @@ static FORCE_INLINE uint32_t fmix32 ( uint32_t h ) return h; } -//---------- - -static FORCE_INLINE uint64_t fmix64 ( uint64_t k ) -{ - k ^= k >> 33; - k *= BIG_CONSTANT(0xff51afd7ed558ccd); - k ^= k >> 33; - k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53); - k ^= k >> 33; - - return k; -} - //----------------------------------------------------------------------------- -void MurmurHash3_x86_32 ( const void * key, int len, - uint32_t seed, void * out ) -{ - const uint8_t * data = (const uint8_t*)key; +void MurmurHash3_x86_32(const void *key, int len, uint32_t seed, void *out) { + const uint8_t *data = (const uint8_t *) key; const int nblocks = len / 4; int i; @@ -109,267 +73,45 @@ void MurmurHash3_x86_32 ( const void * key, int len, //---------- // body - const uint32_t * blocks = (const uint32_t *)(data + nblocks*4); + const uint32_t *blocks = (const uint32_t *) (data + nblocks * 4); - for(i = -nblocks; i; i++) - { - uint32_t k1 = getblock(blocks,i); + for (i = -nblocks; i; i++) { + uint32_t k1 = getblock(blocks, i); +#if WORDS_BIGENDIAN + k1 = BYTESWAP_32(k1); +#endif k1 *= c1; - k1 = ROTL32(k1,15); + k1 = ROTL32(k1, 15); k1 *= c2; h1 ^= k1; - h1 = ROTL32(h1,13); - h1 = h1*5+0xe6546b64; + h1 = ROTL32(h1, 13); + h1 = h1 * 5 + 0xe6546b64; } //---------- // tail - const uint8_t * tail = (const uint8_t*)(data + nblocks*4); + const uint8_t *tail = (const uint8_t *) (data + nblocks * 4); uint32_t k1 = 0; - - switch(len & 3) - { + memcpy(&k1, tail, len & 3); #if WORDS_BIGENDIAN - case 3: k1 ^= tail[2] << 8; - /* fall through */ - case 2: k1 ^= tail[1] << 16; - /* fall through */ - case 1: k1 ^= tail[0] << 24; -#else - case 3: k1 ^= tail[2] << 16; - /* fall through */ - case 2: k1 ^= tail[1] << 8; - /* fall through */ - case 1: k1 ^= tail[0]; + k1 = BYTESWAP_32(k1); #endif - k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1; - }; - - //---------- - // finalization - - h1 ^= len; - - h1 = fmix32(h1); - - *(uint32_t*)out = h1; -} - -//----------------------------------------------------------------------------- - -void MurmurHash3_x86_128 ( const void * key, const int len, - uint32_t seed, void * out ) -{ - const uint8_t * data = (const uint8_t*)key; - const int nblocks = len / 16; - int i; - - uint32_t h1 = seed; - uint32_t h2 = seed; - uint32_t h3 = seed; - uint32_t h4 = seed; - - uint32_t c1 = 0x239b961b; - uint32_t c2 = 0xab0e9789; - uint32_t c3 = 0x38b34ae5; - uint32_t c4 = 0xa1e38b93; - - //---------- - // body - - const uint32_t * blocks = (const uint32_t *)(data + nblocks*16); - - for(i = -nblocks; i; i++) - { - uint32_t k1 = getblock(blocks,i*4+0); - uint32_t k2 = getblock(blocks,i*4+1); - uint32_t k3 = getblock(blocks,i*4+2); - uint32_t k4 = getblock(blocks,i*4+3); - - k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1; - - h1 = ROTL32(h1,19); h1 += h2; h1 = h1*5+0x561ccd1b; - - k2 *= c2; k2 = ROTL32(k2,16); k2 *= c3; h2 ^= k2; - - h2 = ROTL32(h2,17); h2 += h3; h2 = h2*5+0x0bcaa747; - - k3 *= c3; k3 = ROTL32(k3,17); k3 *= c4; h3 ^= k3; - - h3 = ROTL32(h3,15); h3 += h4; h3 = h3*5+0x96cd1c35; - - k4 *= c4; k4 = ROTL32(k4,18); k4 *= c1; h4 ^= k4; - h4 = ROTL32(h4,13); h4 += h1; h4 = h4*5+0x32ac3b17; - } - - //---------- - // tail - - const uint8_t * tail = (const uint8_t*)(data + nblocks*16); - - uint32_t k1 = 0; - uint32_t k2 = 0; - uint32_t k3 = 0; - uint32_t k4 = 0; - - switch(len & 15) - { - case 15: k4 ^= tail[14] << 16; - /* fall through */ - case 14: k4 ^= tail[13] << 8; - /* fall through */ - case 13: k4 ^= tail[12] << 0; - k4 *= c4; k4 = ROTL32(k4,18); k4 *= c1; h4 ^= k4; - /* fall through */ - case 12: k3 ^= tail[11] << 24; - /* fall through */ - case 11: k3 ^= tail[10] << 16; - /* fall through */ - case 10: k3 ^= tail[ 9] << 8; - /* fall through */ - case 9: k3 ^= tail[ 8] << 0; - k3 *= c3; k3 = ROTL32(k3,17); k3 *= c4; h3 ^= k3; - /* fall through */ - case 8: k2 ^= tail[ 7] << 24; - /* fall through */ - case 7: k2 ^= tail[ 6] << 16; - /* fall through */ - case 6: k2 ^= tail[ 5] << 8; - /* fall through */ - case 5: k2 ^= tail[ 4] << 0; - k2 *= c2; k2 = ROTL32(k2,16); k2 *= c3; h2 ^= k2; - /* fall through */ - case 4: k1 ^= tail[ 3] << 24; - /* fall through */ - case 3: k1 ^= tail[ 2] << 16; - /* fall through */ - case 2: k1 ^= tail[ 1] << 8; - /* fall through */ - case 1: k1 ^= tail[ 0] << 0; - k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1; - }; + k1 *= c1; + k1 = ROTL32(k1, 15); + k1 *= c2; + h1 ^= k1; //---------- // finalization - h1 ^= len; h2 ^= len; h3 ^= len; h4 ^= len; - - h1 += h2; h1 += h3; h1 += h4; - h2 += h1; h3 += h1; h4 += h1; + h1 ^= len; h1 = fmix32(h1); - h2 = fmix32(h2); - h3 = fmix32(h3); - h4 = fmix32(h4); - - h1 += h2; h1 += h3; h1 += h4; - h2 += h1; h3 += h1; h4 += h1; - ((uint32_t*)out)[0] = h1; - ((uint32_t*)out)[1] = h2; - ((uint32_t*)out)[2] = h3; - ((uint32_t*)out)[3] = h4; + *(uint32_t *) out = h1; } - -//----------------------------------------------------------------------------- - -void MurmurHash3_x64_128 ( const void * key, const int len, - const uint32_t seed, void * out ) -{ - const uint8_t * data = (const uint8_t*)key; - const int nblocks = len / 16; - int i; - - uint64_t h1 = seed; - uint64_t h2 = seed; - - uint64_t c1 = BIG_CONSTANT(0x87c37b91114253d5); - uint64_t c2 = BIG_CONSTANT(0x4cf5ad432745937f); - - //---------- - // body - - const uint64_t * blocks = (const uint64_t *)(data); - - for(i = 0; i < nblocks; i++) - { - uint64_t k1 = getblock(blocks,i*2+0); - uint64_t k2 = getblock(blocks,i*2+1); - - k1 *= c1; k1 = ROTL64(k1,31); k1 *= c2; h1 ^= k1; - - h1 = ROTL64(h1,27); h1 += h2; h1 = h1*5+0x52dce729; - - k2 *= c2; k2 = ROTL64(k2,33); k2 *= c1; h2 ^= k2; - - h2 = ROTL64(h2,31); h2 += h1; h2 = h2*5+0x38495ab5; - } - - //---------- - // tail - - const uint8_t * tail = (const uint8_t*)(data + nblocks*16); - - uint64_t k1 = 0; - uint64_t k2 = 0; - - switch(len & 15) - { - case 15: k2 ^= (uint64_t)(tail[14]) << 48; - /* fall through */ - case 14: k2 ^= (uint64_t)(tail[13]) << 40; - /* fall through */ - case 13: k2 ^= (uint64_t)(tail[12]) << 32; - /* fall through */ - case 12: k2 ^= (uint64_t)(tail[11]) << 24; - /* fall through */ - case 11: k2 ^= (uint64_t)(tail[10]) << 16; - /* fall through */ - case 10: k2 ^= (uint64_t)(tail[ 9]) << 8; - /* fall through */ - case 9: k2 ^= (uint64_t)(tail[ 8]) << 0; - k2 *= c2; k2 = ROTL64(k2,33); k2 *= c1; h2 ^= k2; - /* fall through */ - case 8: k1 ^= (uint64_t)(tail[ 7]) << 56; - /* fall through */ - case 7: k1 ^= (uint64_t)(tail[ 6]) << 48; - /* fall through */ - case 6: k1 ^= (uint64_t)(tail[ 5]) << 40; - /* fall through */ - case 5: k1 ^= (uint64_t)(tail[ 4]) << 32; - /* fall through */ - case 4: k1 ^= (uint64_t)(tail[ 3]) << 24; - /* fall through */ - case 3: k1 ^= (uint64_t)(tail[ 2]) << 16; - /* fall through */ - case 2: k1 ^= (uint64_t)(tail[ 1]) << 8; - /* fall through */ - case 1: k1 ^= (uint64_t)(tail[ 0]) << 0; - k1 *= c1; k1 = ROTL64(k1,31); k1 *= c2; h1 ^= k1; - }; - - //---------- - // finalization - - h1 ^= len; h2 ^= len; - - h1 += h2; - h2 += h1; - - h1 = fmix64(h1); - h2 = fmix64(h2); - - h1 += h2; - h2 += h1; - - ((uint64_t*)out)[0] = h1; - ((uint64_t*)out)[1] = h2; -} - -//----------------------------------------------------------------------------- -