Commit | Line | Data |
---|---|---|
9f0e365d | 1 | #include "murmur3.h" |
db83b0ab | 2 | #include "../compiler/compiler.h" |
9f0e365d JA |
3 | |
4 | static inline uint32_t rotl32(uint32_t x, int8_t r) | |
5 | { | |
6 | return (x << r) | (x >> (32 - r)); | |
7 | } | |
8 | ||
9 | //----------------------------------------------------------------------------- | |
10 | // Finalization mix - force all bits of a hash block to avalanche | |
11 | ||
12 | static inline uint32_t fmix32(uint32_t h) | |
13 | { | |
14 | h ^= h >> 16; | |
15 | h *= 0x85ebca6b; | |
16 | h ^= h >> 13; | |
17 | h *= 0xc2b2ae35; | |
18 | h ^= h >> 16; | |
19 | ||
20 | return h; | |
21 | } | |
22 | ||
23 | static uint32_t murmur3_tail(const uint8_t *data, const int nblocks, | |
24 | uint32_t len, const uint32_t c1, | |
25 | const uint32_t c2, uint32_t h1) | |
26 | { | |
27 | const uint8_t *tail = (const uint8_t *)(data + nblocks * 4); | |
28 | ||
29 | uint32_t k1 = 0; | |
30 | switch (len & 3) { | |
31 | case 3: | |
32 | k1 ^= tail[2] << 16; | |
87933e32 | 33 | fio_fallthrough; |
9f0e365d JA |
34 | case 2: |
35 | k1 ^= tail[1] << 8; | |
87933e32 | 36 | fio_fallthrough; |
9f0e365d JA |
37 | case 1: |
38 | k1 ^= tail[0]; | |
39 | k1 *= c1; | |
40 | k1 = rotl32(k1, 15); | |
41 | k1 *= c2; | |
42 | h1 ^= k1; | |
43 | }; | |
44 | ||
45 | return fmix32(h1 ^ len); | |
46 | } | |
47 | ||
48 | uint32_t murmurhash3(const void *key, uint32_t len, uint32_t seed) | |
49 | { | |
50 | const uint8_t *data = (const uint8_t *)key; | |
51 | const int nblocks = len / 4; | |
52 | uint32_t h1 = seed; | |
53 | const uint32_t c1 = 0xcc9e2d51; | |
54 | const uint32_t c2 = 0x1b873593; | |
55 | const uint32_t *blocks = (const uint32_t *)(data + nblocks * 4); | |
56 | int i; | |
57 | ||
58 | for (i = -nblocks; i; i++) { | |
59 | uint32_t k1 = blocks[i]; | |
60 | ||
61 | k1 *= c1; | |
62 | k1 = rotl32(k1, 15); | |
63 | k1 *= c2; | |
64 | ||
65 | h1 ^= k1; | |
66 | h1 = rotl32(h1, 13); | |
67 | h1 = h1 * 5 + 0xe6546b64; | |
68 | } | |
69 | ||
70 | return murmur3_tail(data, nblocks, len, c1, c2, h1); | |
71 | } |