1 //-----------------------------------------------------------------------------
2 //MurmurHash3 was written by Austin Appleby, and is placed in the public
3 //domain. The author hereby disclaims copyright to this source code.
5 // Note - The x86 and x64 versions do _not_ produce the same results, as the
6 // algorithms are optimized for their respective platforms. You can still
7 // compile and run any of them on any platform, but your performance with the
8 // non-native version will be less than optimal.
10 #include "libhashkit/hashkitcon.h"
12 #include "libhashkit/murmur3.h"
14 //-----------------------------------------------------------------------------
15 // Platform-specific functions and macros
18 #define FORCE_INLINE __attribute__((always_inline)) inline
20 #define FORCE_INLINE inline
23 static FORCE_INLINE
uint32_t rotl32 ( uint32_t x
, int8_t r
)
25 return (x
<< r
) | (x
>> (32 - r
));
28 static FORCE_INLINE
uint64_t rotl64 ( uint64_t x
, int8_t r
)
30 return (x
<< r
) | (x
>> (64 - r
));
33 #define ROTL32(x,y) rotl32(x,y)
34 #define ROTL64(x,y) rotl64(x,y)
36 #define BIG_CONSTANT(x) (x##LLU)
38 //-----------------------------------------------------------------------------
39 // Block read - if your platform needs to do endian-swapping or can only
40 // handle aligned reads, do the conversion here
44 static inline T
getblock(const T
*blocks
, int i
) {
46 memcpy(&b
, ((const uint8_t *) blocks
) + i
* sizeof(T
), sizeof(T
));
50 //-----------------------------------------------------------------------------
51 // Finalization mix - force all bits of a hash block to avalanche
53 static FORCE_INLINE
uint32_t fmix32 ( uint32_t h
)
66 static FORCE_INLINE
uint64_t fmix64 ( uint64_t k
)
69 k
*= BIG_CONSTANT(0xff51afd7ed558ccd);
71 k
*= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
77 //-----------------------------------------------------------------------------
79 void MurmurHash3_x86_32 ( const void * key
, int len
,
80 uint32_t seed
, void * out
)
82 const uint8_t * data
= (const uint8_t*)key
;
83 const int nblocks
= len
/ 4;
88 uint32_t c1
= 0xcc9e2d51;
89 uint32_t c2
= 0x1b873593;
94 const uint32_t * blocks
= (const uint32_t *)(data
+ nblocks
*4);
96 for(i
= -nblocks
; i
; i
++)
98 uint32_t k1
= getblock(blocks
,i
);
106 h1
= h1
*5+0xe6546b64;
112 const uint8_t * tail
= (const uint8_t*)(data
+ nblocks
*4);
118 case 3: k1
^= tail
[2] << 16;
120 case 2: k1
^= tail
[1] << 8;
122 case 1: k1
^= tail
[0];
123 k1
*= c1
; k1
= ROTL32(k1
,15); k1
*= c2
; h1
^= k1
;
133 *(uint32_t*)out
= h1
;
136 //-----------------------------------------------------------------------------
138 void MurmurHash3_x86_128 ( const void * key
, const int len
,
139 uint32_t seed
, void * out
)
141 const uint8_t * data
= (const uint8_t*)key
;
142 const int nblocks
= len
/ 16;
150 uint32_t c1
= 0x239b961b;
151 uint32_t c2
= 0xab0e9789;
152 uint32_t c3
= 0x38b34ae5;
153 uint32_t c4
= 0xa1e38b93;
158 const uint32_t * blocks
= (const uint32_t *)(data
+ nblocks
*16);
160 for(i
= -nblocks
; i
; i
++)
162 uint32_t k1
= getblock(blocks
,i
*4+0);
163 uint32_t k2
= getblock(blocks
,i
*4+1);
164 uint32_t k3
= getblock(blocks
,i
*4+2);
165 uint32_t k4
= getblock(blocks
,i
*4+3);
167 k1
*= c1
; k1
= ROTL32(k1
,15); k1
*= c2
; h1
^= k1
;
169 h1
= ROTL32(h1
,19); h1
+= h2
; h1
= h1
*5+0x561ccd1b;
171 k2
*= c2
; k2
= ROTL32(k2
,16); k2
*= c3
; h2
^= k2
;
173 h2
= ROTL32(h2
,17); h2
+= h3
; h2
= h2
*5+0x0bcaa747;
175 k3
*= c3
; k3
= ROTL32(k3
,17); k3
*= c4
; h3
^= k3
;
177 h3
= ROTL32(h3
,15); h3
+= h4
; h3
= h3
*5+0x96cd1c35;
179 k4
*= c4
; k4
= ROTL32(k4
,18); k4
*= c1
; h4
^= k4
;
181 h4
= ROTL32(h4
,13); h4
+= h1
; h4
= h4
*5+0x32ac3b17;
187 const uint8_t * tail
= (const uint8_t*)(data
+ nblocks
*16);
196 case 15: k4
^= tail
[14] << 16;
198 case 14: k4
^= tail
[13] << 8;
200 case 13: k4
^= tail
[12] << 0;
201 k4
*= c4
; k4
= ROTL32(k4
,18); k4
*= c1
; h4
^= k4
;
203 case 12: k3
^= tail
[11] << 24;
205 case 11: k3
^= tail
[10] << 16;
207 case 10: k3
^= tail
[ 9] << 8;
209 case 9: k3
^= tail
[ 8] << 0;
210 k3
*= c3
; k3
= ROTL32(k3
,17); k3
*= c4
; h3
^= k3
;
212 case 8: k2
^= tail
[ 7] << 24;
214 case 7: k2
^= tail
[ 6] << 16;
216 case 6: k2
^= tail
[ 5] << 8;
218 case 5: k2
^= tail
[ 4] << 0;
219 k2
*= c2
; k2
= ROTL32(k2
,16); k2
*= c3
; h2
^= k2
;
221 case 4: k1
^= tail
[ 3] << 24;
223 case 3: k1
^= tail
[ 2] << 16;
225 case 2: k1
^= tail
[ 1] << 8;
227 case 1: k1
^= tail
[ 0] << 0;
228 k1
*= c1
; k1
= ROTL32(k1
,15); k1
*= c2
; h1
^= k1
;
234 h1
^= len
; h2
^= len
; h3
^= len
; h4
^= len
;
236 h1
+= h2
; h1
+= h3
; h1
+= h4
;
237 h2
+= h1
; h3
+= h1
; h4
+= h1
;
244 h1
+= h2
; h1
+= h3
; h1
+= h4
;
245 h2
+= h1
; h3
+= h1
; h4
+= h1
;
247 ((uint32_t*)out
)[0] = h1
;
248 ((uint32_t*)out
)[1] = h2
;
249 ((uint32_t*)out
)[2] = h3
;
250 ((uint32_t*)out
)[3] = h4
;
253 //-----------------------------------------------------------------------------
255 void MurmurHash3_x64_128 ( const void * key
, const int len
,
256 const uint32_t seed
, void * out
)
258 const uint8_t * data
= (const uint8_t*)key
;
259 const int nblocks
= len
/ 16;
265 uint64_t c1
= BIG_CONSTANT(0x87c37b91114253d5);
266 uint64_t c2
= BIG_CONSTANT(0x4cf5ad432745937f);
271 const uint64_t * blocks
= (const uint64_t *)(data
);
273 for(i
= 0; i
< nblocks
; i
++)
275 uint64_t k1
= getblock(blocks
,i
*2+0);
276 uint64_t k2
= getblock(blocks
,i
*2+1);
278 k1
*= c1
; k1
= ROTL64(k1
,31); k1
*= c2
; h1
^= k1
;
280 h1
= ROTL64(h1
,27); h1
+= h2
; h1
= h1
*5+0x52dce729;
282 k2
*= c2
; k2
= ROTL64(k2
,33); k2
*= c1
; h2
^= k2
;
284 h2
= ROTL64(h2
,31); h2
+= h1
; h2
= h2
*5+0x38495ab5;
290 const uint8_t * tail
= (const uint8_t*)(data
+ nblocks
*16);
297 case 15: k2
^= (uint64_t)(tail
[14]) << 48;
299 case 14: k2
^= (uint64_t)(tail
[13]) << 40;
301 case 13: k2
^= (uint64_t)(tail
[12]) << 32;
303 case 12: k2
^= (uint64_t)(tail
[11]) << 24;
305 case 11: k2
^= (uint64_t)(tail
[10]) << 16;
307 case 10: k2
^= (uint64_t)(tail
[ 9]) << 8;
309 case 9: k2
^= (uint64_t)(tail
[ 8]) << 0;
310 k2
*= c2
; k2
= ROTL64(k2
,33); k2
*= c1
; h2
^= k2
;
312 case 8: k1
^= (uint64_t)(tail
[ 7]) << 56;
314 case 7: k1
^= (uint64_t)(tail
[ 6]) << 48;
316 case 6: k1
^= (uint64_t)(tail
[ 5]) << 40;
318 case 5: k1
^= (uint64_t)(tail
[ 4]) << 32;
320 case 4: k1
^= (uint64_t)(tail
[ 3]) << 24;
322 case 3: k1
^= (uint64_t)(tail
[ 2]) << 16;
324 case 2: k1
^= (uint64_t)(tail
[ 1]) << 8;
326 case 1: k1
^= (uint64_t)(tail
[ 0]) << 0;
327 k1
*= c1
; k1
= ROTL64(k1
,31); k1
*= c2
; h1
^= k1
;
333 h1
^= len
; h2
^= len
;
344 ((uint64_t*)out
)[0] = h1
;
345 ((uint64_t*)out
)[1] = h2
;
348 //-----------------------------------------------------------------------------