blob: dbbb09a6b0df6a9c728d30ee53ca49cf79196f05 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
/* mmh3.c
*/
#include <string.h>
#include <stdint.h>
#include "mmh3.h"
static uint64_t
load64_le(const uint8_t *p)
{
return ((uint64_t)p[0]) |
((uint64_t)p[1] << 8) |
((uint64_t)p[2] << 16) |
((uint64_t)p[3] << 24) |
((uint64_t)p[4] << 32) |
((uint64_t)p[5] << 40) |
((uint64_t)p[6] << 48) |
((uint64_t)p[7] << 56);
}
/* mmh3_128() -- calculate 128 bit mmh3 hash.
*
* Args:
* key
* len
* seed
* out
*
* Returns:
* Nothing. Output is written to 'out'.
*/
void mmh3_128(const void *key, const size_t len, const uint64_t seed, uint64_t *out) {
const uint64_t c1 = 0x87c37b91114253d5;
const uint64_t c2 = 0x4cf5ad432745937f;
const uint8_t *data = (const uint8_t *)key;
const size_t nblocks = len / 16;
uint64_t h1 = seed;
uint64_t h2 = seed;
// Process the data in 128-bit chunks
for (size_t i = 0; i < nblocks; i++) {
const uint8_t *block = data + i * 16;
uint64_t k1 = load64_le(block);
uint64_t k2 = load64_le(block + 8);
k1 *= c1; k1 = (k1 << 31) | (k1 >> 33); k1 *= c2; h1 ^= k1;
h1 = (h1 << 27) | (h1 >> 37); h1 += h2; h1 = h1 * 5 + 0x52dce729;
k2 *= c2; k2 = (k2 << 33) | (k2 >> 31); k2 *= c1; h2 ^= k2;
h2 = (h2 << 31) | (h2 >> 33); h2 += h1; h2 = h2 * 5 + 0x38495ab5;
}
// Process the remaining bytes
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; /* fall through */
k2 *= c2; k2 = (k2 << 33) | (k2 >> 31); 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; /* fall through */
k1 *= c1; k1 = (k1 << 31) | (k1 >> 33); k1 *= c2; h1 ^= k1;
}
// Finalization
h1 ^= len;
h2 ^= len;
h1 += h2;
h2 += h1;
h1 ^= h1 >> 33;
h1 *= 0xff51afd7ed558ccd;
h1 ^= h1 >> 33;
h1 *= 0xc4ceb9fe1a85ec53;
h1 ^= h1 >> 33;
h2 ^= h2 >> 33;
h2 *= 0xff51afd7ed558ccd;
h2 ^= h2 >> 33;
h2 *= 0xc4ceb9fe1a85ec53;
h2 ^= h2 >> 33;
h1 += h2;
h2 += h1;
out[0] = h1;
out[1] = h2;
}
|
