]>
git.ipfire.org Git - thirdparty/systemd.git/blob - src/shared/MurmurHash3.c
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 "MurmurHash3.h"
12 //-----------------------------------------------------------------------------
13 // Platform-specific functions and macros
15 // Microsoft Visual Studio
19 #define FORCE_INLINE __forceinline
23 #define ROTL32(x,y) _rotl(x,y)
24 #define ROTL64(x,y) _rotl64(x,y)
26 #define BIG_CONSTANT(x) (x)
30 #else // defined(_MSC_VER)
32 #define FORCE_INLINE __attribute__((always_inline))
34 static inline uint32_t rotl32 ( uint32_t x
, int8_t r
)
36 return (x
<< r
) | (x
>> (32 - r
));
39 static inline uint64_t rotl64 ( uint64_t x
, int8_t r
)
41 return (x
<< r
) | (x
>> (64 - r
));
44 #define ROTL32(x,y) rotl32(x,y)
45 #define ROTL64(x,y) rotl64(x,y)
47 #define BIG_CONSTANT(x) (x##LLU)
49 #endif // !defined(_MSC_VER)
51 //-----------------------------------------------------------------------------
52 // Block read - if your platform needs to do endian-swapping or can only
53 // handle aligned reads, do the conversion here
55 static FORCE_INLINE
uint32_t getblock32 ( const uint32_t * p
, int i
)
60 static FORCE_INLINE
uint64_t getblock64 ( const uint64_t * p
, int i
)
65 //-----------------------------------------------------------------------------
66 // Finalization mix - force all bits of a hash block to avalanche
68 static FORCE_INLINE
uint32_t fmix32 ( uint32_t h
)
81 static FORCE_INLINE
uint64_t fmix64 ( uint64_t k
)
84 k
*= BIG_CONSTANT(0xff51afd7ed558ccd);
86 k
*= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
92 //-----------------------------------------------------------------------------
94 void MurmurHash3_x86_32 ( const void * key
, size_t len
,
95 uint32_t seed
, void * out
)
97 const uint8_t * data
= (const uint8_t*)key
;
98 const int nblocks
= len
/ 4;
102 const uint32_t c1
= 0xcc9e2d51;
103 const uint32_t c2
= 0x1b873593;
105 const uint8_t * tail
;
111 const uint32_t * blocks
= (const uint32_t *)(data
+ nblocks
*4);
113 for(int i
= -nblocks
; i
; i
++)
115 k1
= getblock32(blocks
,i
);
123 h1
= h1
*5+0xe6546b64;
129 tail
= (const uint8_t*)(data
+ nblocks
*4);
135 case 3: k1
^= tail
[2] << 16;
136 case 2: k1
^= tail
[1] << 8;
137 case 1: k1
^= tail
[0];
138 k1
*= c1
; k1
= ROTL32(k1
,15); k1
*= c2
; h1
^= k1
;
148 *(uint32_t*)out
= h1
;
151 //-----------------------------------------------------------------------------
153 void MurmurHash3_x86_128 ( const void * key
, const size_t len
,
154 uint32_t seed
, void * out
)
156 const uint8_t * data
= (const uint8_t*)key
;
157 const int nblocks
= len
/ 16;
164 const uint32_t c1
= 0x239b961b;
165 const uint32_t c2
= 0xab0e9789;
166 const uint32_t c3
= 0x38b34ae5;
167 const uint32_t c4
= 0xa1e38b93;
169 const uint8_t * tail
;
179 const uint32_t * blocks
= (const uint32_t *)(data
+ nblocks
*16);
181 for(int i
= -nblocks
; i
; i
++)
183 k1
= getblock32(blocks
,i
*4+0);
184 k2
= getblock32(blocks
,i
*4+1);
185 k3
= getblock32(blocks
,i
*4+2);
186 k4
= getblock32(blocks
,i
*4+3);
188 k1
*= c1
; k1
= ROTL32(k1
,15); k1
*= c2
; h1
^= k1
;
190 h1
= ROTL32(h1
,19); h1
+= h2
; h1
= h1
*5+0x561ccd1b;
192 k2
*= c2
; k2
= ROTL32(k2
,16); k2
*= c3
; h2
^= k2
;
194 h2
= ROTL32(h2
,17); h2
+= h3
; h2
= h2
*5+0x0bcaa747;
196 k3
*= c3
; k3
= ROTL32(k3
,17); k3
*= c4
; h3
^= k3
;
198 h3
= ROTL32(h3
,15); h3
+= h4
; h3
= h3
*5+0x96cd1c35;
200 k4
*= c4
; k4
= ROTL32(k4
,18); k4
*= c1
; h4
^= k4
;
202 h4
= ROTL32(h4
,13); h4
+= h1
; h4
= h4
*5+0x32ac3b17;
208 tail
= (const uint8_t*)(data
+ nblocks
*16);
217 case 15: k4
^= tail
[14] << 16;
218 case 14: k4
^= tail
[13] << 8;
219 case 13: k4
^= tail
[12] << 0;
220 k4
*= c4
; k4
= ROTL32(k4
,18); k4
*= c1
; h4
^= k4
;
222 case 12: k3
^= tail
[11] << 24;
223 case 11: k3
^= tail
[10] << 16;
224 case 10: k3
^= tail
[ 9] << 8;
225 case 9: k3
^= tail
[ 8] << 0;
226 k3
*= c3
; k3
= ROTL32(k3
,17); k3
*= c4
; h3
^= k3
;
228 case 8: k2
^= tail
[ 7] << 24;
229 case 7: k2
^= tail
[ 6] << 16;
230 case 6: k2
^= tail
[ 5] << 8;
231 case 5: k2
^= tail
[ 4] << 0;
232 k2
*= c2
; k2
= ROTL32(k2
,16); k2
*= c3
; h2
^= k2
;
234 case 4: k1
^= tail
[ 3] << 24;
235 case 3: k1
^= tail
[ 2] << 16;
236 case 2: k1
^= tail
[ 1] << 8;
237 case 1: k1
^= tail
[ 0] << 0;
238 k1
*= c1
; k1
= ROTL32(k1
,15); k1
*= c2
; h1
^= k1
;
244 h1
^= len
; h2
^= len
; h3
^= len
; h4
^= len
;
246 h1
+= h2
; h1
+= h3
; h1
+= h4
;
247 h2
+= h1
; h3
+= h1
; h4
+= h1
;
254 h1
+= h2
; h1
+= h3
; h1
+= h4
;
255 h2
+= h1
; h3
+= h1
; h4
+= h1
;
257 ((uint32_t*)out
)[0] = h1
;
258 ((uint32_t*)out
)[1] = h2
;
259 ((uint32_t*)out
)[2] = h3
;
260 ((uint32_t*)out
)[3] = h4
;
263 //-----------------------------------------------------------------------------
265 void MurmurHash3_x64_128 ( const void * key
, const size_t len
,
266 const uint32_t seed
, void * out
)
268 const uint8_t * data
= (const uint8_t*)key
;
269 const int nblocks
= len
/ 16;
274 const uint64_t c1
= BIG_CONSTANT(0x87c37b91114253d5);
275 const uint64_t c2
= BIG_CONSTANT(0x4cf5ad432745937f);
285 const uint64_t * blocks
= (const uint64_t *)(data
);
287 for(int i
= 0; i
< nblocks
; i
++)
289 k1
= getblock64(blocks
,i
*2+0);
290 k2
= getblock64(blocks
,i
*2+1);
292 k1
*= c1
; k1
= ROTL64(k1
,31); k1
*= c2
; h1
^= k1
;
294 h1
= ROTL64(h1
,27); h1
+= h2
; h1
= h1
*5+0x52dce729;
296 k2
*= c2
; k2
= ROTL64(k2
,33); k2
*= c1
; h2
^= k2
;
298 h2
= ROTL64(h2
,31); h2
+= h1
; h2
= h2
*5+0x38495ab5;
304 tail
= (const uint8_t*)(data
+ nblocks
*16);
311 case 15: k2
^= (uint64_t)(tail
[14]) << 48;
312 case 14: k2
^= (uint64_t)(tail
[13]) << 40;
313 case 13: k2
^= (uint64_t)(tail
[12]) << 32;
314 case 12: k2
^= (uint64_t)(tail
[11]) << 24;
315 case 11: k2
^= (uint64_t)(tail
[10]) << 16;
316 case 10: k2
^= (uint64_t)(tail
[ 9]) << 8;
317 case 9: k2
^= (uint64_t)(tail
[ 8]) << 0;
318 k2
*= c2
; k2
= ROTL64(k2
,33); k2
*= c1
; h2
^= k2
;
320 case 8: k1
^= (uint64_t)(tail
[ 7]) << 56;
321 case 7: k1
^= (uint64_t)(tail
[ 6]) << 48;
322 case 6: k1
^= (uint64_t)(tail
[ 5]) << 40;
323 case 5: k1
^= (uint64_t)(tail
[ 4]) << 32;
324 case 4: k1
^= (uint64_t)(tail
[ 3]) << 24;
325 case 3: k1
^= (uint64_t)(tail
[ 2]) << 16;
326 case 2: k1
^= (uint64_t)(tail
[ 1]) << 8;
327 case 1: k1
^= (uint64_t)(tail
[ 0]) << 0;
328 k1
*= c1
; k1
= ROTL64(k1
,31); k1
*= c2
; h1
^= k1
;
334 h1
^= len
; h2
^= len
;
345 ((uint64_t*)out
)[0] = h1
;
346 ((uint64_t*)out
)[1] = h2
;
349 //-----------------------------------------------------------------------------