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
42 #define getblock(p, i) (p[i])
44 //-----------------------------------------------------------------------------
45 // Finalization mix - force all bits of a hash block to avalanche
47 static FORCE_INLINE
uint32_t fmix32 ( uint32_t h
)
60 static FORCE_INLINE
uint64_t fmix64 ( uint64_t k
)
63 k
*= BIG_CONSTANT(0xff51afd7ed558ccd);
65 k
*= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
71 //-----------------------------------------------------------------------------
73 void MurmurHash3_x86_32 ( const void * key
, int len
,
74 uint32_t seed
, void * out
)
76 const uint8_t * data
= (const uint8_t*)key
;
77 const int nblocks
= len
/ 4;
82 uint32_t c1
= 0xcc9e2d51;
83 uint32_t c2
= 0x1b873593;
88 const uint32_t * blocks
= (const uint32_t *)(data
+ nblocks
*4);
90 for(i
= -nblocks
; i
; i
++)
92 uint32_t k1
= getblock(blocks
,i
);
100 h1
= h1
*5+0xe6546b64;
106 const uint8_t * tail
= (const uint8_t*)(data
+ nblocks
*4);
112 case 3: k1
^= tail
[2] << 16;
113 case 2: k1
^= tail
[1] << 8;
114 case 1: k1
^= tail
[0];
115 k1
*= c1
; k1
= ROTL32(k1
,15); k1
*= c2
; h1
^= k1
;
125 *(uint32_t*)out
= h1
;
128 //-----------------------------------------------------------------------------
130 void MurmurHash3_x86_128 ( const void * key
, const int len
,
131 uint32_t seed
, void * out
)
133 const uint8_t * data
= (const uint8_t*)key
;
134 const int nblocks
= len
/ 16;
142 uint32_t c1
= 0x239b961b;
143 uint32_t c2
= 0xab0e9789;
144 uint32_t c3
= 0x38b34ae5;
145 uint32_t c4
= 0xa1e38b93;
150 const uint32_t * blocks
= (const uint32_t *)(data
+ nblocks
*16);
152 for(i
= -nblocks
; i
; i
++)
154 uint32_t k1
= getblock(blocks
,i
*4+0);
155 uint32_t k2
= getblock(blocks
,i
*4+1);
156 uint32_t k3
= getblock(blocks
,i
*4+2);
157 uint32_t k4
= getblock(blocks
,i
*4+3);
159 k1
*= c1
; k1
= ROTL32(k1
,15); k1
*= c2
; h1
^= k1
;
161 h1
= ROTL32(h1
,19); h1
+= h2
; h1
= h1
*5+0x561ccd1b;
163 k2
*= c2
; k2
= ROTL32(k2
,16); k2
*= c3
; h2
^= k2
;
165 h2
= ROTL32(h2
,17); h2
+= h3
; h2
= h2
*5+0x0bcaa747;
167 k3
*= c3
; k3
= ROTL32(k3
,17); k3
*= c4
; h3
^= k3
;
169 h3
= ROTL32(h3
,15); h3
+= h4
; h3
= h3
*5+0x96cd1c35;
171 k4
*= c4
; k4
= ROTL32(k4
,18); k4
*= c1
; h4
^= k4
;
173 h4
= ROTL32(h4
,13); h4
+= h1
; h4
= h4
*5+0x32ac3b17;
179 const uint8_t * tail
= (const uint8_t*)(data
+ nblocks
*16);
188 case 15: k4
^= tail
[14] << 16;
189 case 14: k4
^= tail
[13] << 8;
190 case 13: k4
^= tail
[12] << 0;
191 k4
*= c4
; k4
= ROTL32(k4
,18); k4
*= c1
; h4
^= k4
;
193 case 12: k3
^= tail
[11] << 24;
194 case 11: k3
^= tail
[10] << 16;
195 case 10: k3
^= tail
[ 9] << 8;
196 case 9: k3
^= tail
[ 8] << 0;
197 k3
*= c3
; k3
= ROTL32(k3
,17); k3
*= c4
; h3
^= k3
;
199 case 8: k2
^= tail
[ 7] << 24;
200 case 7: k2
^= tail
[ 6] << 16;
201 case 6: k2
^= tail
[ 5] << 8;
202 case 5: k2
^= tail
[ 4] << 0;
203 k2
*= c2
; k2
= ROTL32(k2
,16); k2
*= c3
; h2
^= k2
;
205 case 4: k1
^= tail
[ 3] << 24;
206 case 3: k1
^= tail
[ 2] << 16;
207 case 2: k1
^= tail
[ 1] << 8;
208 case 1: k1
^= tail
[ 0] << 0;
209 k1
*= c1
; k1
= ROTL32(k1
,15); k1
*= c2
; h1
^= k1
;
215 h1
^= len
; h2
^= len
; h3
^= len
; h4
^= len
;
217 h1
+= h2
; h1
+= h3
; h1
+= h4
;
218 h2
+= h1
; h3
+= h1
; h4
+= h1
;
225 h1
+= h2
; h1
+= h3
; h1
+= h4
;
226 h2
+= h1
; h3
+= h1
; h4
+= h1
;
228 ((uint32_t*)out
)[0] = h1
;
229 ((uint32_t*)out
)[1] = h2
;
230 ((uint32_t*)out
)[2] = h3
;
231 ((uint32_t*)out
)[3] = h4
;
234 //-----------------------------------------------------------------------------
236 void MurmurHash3_x64_128 ( const void * key
, const int len
,
237 const uint32_t seed
, void * out
)
239 const uint8_t * data
= (const uint8_t*)key
;
240 const int nblocks
= len
/ 16;
246 uint64_t c1
= BIG_CONSTANT(0x87c37b91114253d5);
247 uint64_t c2
= BIG_CONSTANT(0x4cf5ad432745937f);
252 const uint64_t * blocks
= (const uint64_t *)(data
);
254 for(i
= 0; i
< nblocks
; i
++)
256 uint64_t k1
= getblock(blocks
,i
*2+0);
257 uint64_t k2
= getblock(blocks
,i
*2+1);
259 k1
*= c1
; k1
= ROTL64(k1
,31); k1
*= c2
; h1
^= k1
;
261 h1
= ROTL64(h1
,27); h1
+= h2
; h1
= h1
*5+0x52dce729;
263 k2
*= c2
; k2
= ROTL64(k2
,33); k2
*= c1
; h2
^= k2
;
265 h2
= ROTL64(h2
,31); h2
+= h1
; h2
= h2
*5+0x38495ab5;
271 const uint8_t * tail
= (const uint8_t*)(data
+ nblocks
*16);
278 case 15: k2
^= (uint64_t)(tail
[14]) << 48;
279 case 14: k2
^= (uint64_t)(tail
[13]) << 40;
280 case 13: k2
^= (uint64_t)(tail
[12]) << 32;
281 case 12: k2
^= (uint64_t)(tail
[11]) << 24;
282 case 11: k2
^= (uint64_t)(tail
[10]) << 16;
283 case 10: k2
^= (uint64_t)(tail
[ 9]) << 8;
284 case 9: k2
^= (uint64_t)(tail
[ 8]) << 0;
285 k2
*= c2
; k2
= ROTL64(k2
,33); k2
*= c1
; h2
^= k2
;
287 case 8: k1
^= (uint64_t)(tail
[ 7]) << 56;
288 case 7: k1
^= (uint64_t)(tail
[ 6]) << 48;
289 case 6: k1
^= (uint64_t)(tail
[ 5]) << 40;
290 case 5: k1
^= (uint64_t)(tail
[ 4]) << 32;
291 case 4: k1
^= (uint64_t)(tail
[ 3]) << 24;
292 case 3: k1
^= (uint64_t)(tail
[ 2]) << 16;
293 case 2: k1
^= (uint64_t)(tail
[ 1]) << 8;
294 case 1: k1
^= (uint64_t)(tail
[ 0]) << 0;
295 k1
*= c1
; k1
= ROTL64(k1
,31); k1
*= c2
; h1
^= k1
;
301 h1
^= len
; h2
^= len
;
312 ((uint64_t*)out
)[0] = h1
;
313 ((uint64_t*)out
)[1] = h2
;
316 //-----------------------------------------------------------------------------