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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
|
#include "common.h"
namespace farmhashna {
#undef Fetch
#define Fetch Fetch64
#undef Rotate
#define Rotate Rotate64
#undef Bswap
#define Bswap Bswap64
STATIC_INLINE uint64_t ShiftMix(uint64_t val) {
return val ^ (val >> 47);
}
STATIC_INLINE uint64_t HashLen16(uint64_t u, uint64_t v) {
return Hash128to64(Uint128(u, v));
}
STATIC_INLINE uint64_t HashLen16(uint64_t u, uint64_t v, uint64_t mul) {
// Murmur-inspired hashing.
uint64_t a = (u ^ v) * mul;
a ^= (a >> 47);
uint64_t b = (v ^ a) * mul;
b ^= (b >> 47);
b *= mul;
return b;
}
STATIC_INLINE uint64_t HashLen0to16(const char *s, size_t len) {
if (len >= 8) {
uint64_t mul = k2 + len * 2;
uint64_t a = Fetch(s) + k2;
uint64_t b = Fetch(s + len - 8);
uint64_t c = Rotate(b, 37) * mul + a;
uint64_t d = (Rotate(a, 25) + b) * mul;
return HashLen16(c, d, mul);
}
if (len >= 4) {
uint64_t mul = k2 + len * 2;
uint64_t a = Fetch32(s);
return HashLen16(len + (a << 3), Fetch32(s + len - 4), mul);
}
if (len > 0) {
uint8_t a = s[0];
uint8_t b = s[len >> 1];
uint8_t c = s[len - 1];
uint32_t y = static_cast<uint32_t>(a) + (static_cast<uint32_t>(b) << 8);
uint32_t z = len + (static_cast<uint32_t>(c) << 2);
return ShiftMix(y * k2 ^ z * k0) * k2;
}
return k2;
}
// This probably works well for 16-byte strings as well, but it may be overkill
// in that case.
STATIC_INLINE uint64_t HashLen17to32(const char *s, size_t len) {
uint64_t mul = k2 + len * 2;
uint64_t a = Fetch(s) * k1;
uint64_t b = Fetch(s + 8);
uint64_t c = Fetch(s + len - 8) * mul;
uint64_t d = Fetch(s + len - 16) * k2;
return HashLen16(Rotate(a + b, 43) + Rotate(c, 30) + d,
a + Rotate(b + k2, 18) + c, mul);
}
// Return a 16-byte hash for 48 bytes. Quick and dirty.
// Callers do best to use "random-looking" values for a and b.
STATIC_INLINE pair<uint64_t, uint64_t> WeakHashLen32WithSeeds(
uint64_t w, uint64_t x, uint64_t y, uint64_t z, uint64_t a, uint64_t b) {
a += w;
b = Rotate(b + a + z, 21);
uint64_t c = a;
a += x;
a += y;
b += Rotate(a, 44);
return make_pair(a + z, b + c);
}
// Return a 16-byte hash for s[0] ... s[31], a, and b. Quick and dirty.
STATIC_INLINE pair<uint64_t, uint64_t> WeakHashLen32WithSeeds(
const char* s, uint64_t a, uint64_t b) {
return WeakHashLen32WithSeeds(Fetch(s),
Fetch(s + 8),
Fetch(s + 16),
Fetch(s + 24),
a,
b);
}
// Return an 8-byte hash for 33 to 64 bytes.
STATIC_INLINE uint64_t HashLen33to64(const char *s, size_t len) {
uint64_t mul = k2 + len * 2;
uint64_t a = Fetch(s) * k2;
uint64_t b = Fetch(s + 8);
uint64_t c = Fetch(s + len - 8) * mul;
uint64_t d = Fetch(s + len - 16) * k2;
uint64_t y = Rotate(a + b, 43) + Rotate(c, 30) + d;
uint64_t z = HashLen16(y, a + Rotate(b + k2, 18) + c, mul);
uint64_t e = Fetch(s + 16) * mul;
uint64_t f = Fetch(s + 24);
uint64_t g = (y + Fetch(s + len - 32)) * mul;
uint64_t h = (z + Fetch(s + len - 24)) * mul;
return HashLen16(Rotate(e + f, 43) + Rotate(g, 30) + h,
e + Rotate(f + a, 18) + g, mul);
}
uint64_t Hash64(const char *s, size_t len) {
const uint64_t seed = 81;
if (len <= 32) {
if (len <= 16) {
return HashLen0to16(s, len);
} else {
return HashLen17to32(s, len);
}
} else if (len <= 64) {
return HashLen33to64(s, len);
}
// For strings over 64 bytes we loop. Internal state consists of
// 56 bytes: v, w, x, y, and z.
uint64_t x = seed;
uint64_t y = seed * k1 + 113;
uint64_t z = ShiftMix(y * k2 + 113) * k2;
pair<uint64_t, uint64_t> v = make_pair(0, 0);
pair<uint64_t, uint64_t> w = make_pair(0, 0);
x = x * k2 + Fetch(s);
// Set end so that after the loop we have 1 to 64 bytes left to process.
const char* end = s + ((len - 1) / 64) * 64;
const char* last64 = end + ((len - 1) & 63) - 63;
assert(s + len - 64 == last64);
do {
x = Rotate(x + y + v.first + Fetch(s + 8), 37) * k1;
y = Rotate(y + v.second + Fetch(s + 48), 42) * k1;
x ^= w.second;
y += v.first + Fetch(s + 40);
z = Rotate(z + w.first, 33) * k1;
v = WeakHashLen32WithSeeds(s, v.second * k1, x + w.first);
w = WeakHashLen32WithSeeds(s + 32, z + w.second, y + Fetch(s + 16));
std::swap(z, x);
s += 64;
} while (s != end);
uint64_t mul = k1 + ((z & 0xff) << 1);
// Make s point to the last 64 bytes of input.
s = last64;
w.first += ((len - 1) & 63);
v.first += w.first;
w.first += v.first;
x = Rotate(x + y + v.first + Fetch(s + 8), 37) * mul;
y = Rotate(y + v.second + Fetch(s + 48), 42) * mul;
x ^= w.second * 9;
y += v.first * 9 + Fetch(s + 40);
z = Rotate(z + w.first, 33) * mul;
v = WeakHashLen32WithSeeds(s, v.second * mul, x + w.first);
w = WeakHashLen32WithSeeds(s + 32, z + w.second, y + Fetch(s + 16));
std::swap(z, x);
return HashLen16(HashLen16(v.first, w.first, mul) + ShiftMix(y) * k0 + z,
HashLen16(v.second, w.second, mul) + x,
mul);
}
uint64_t Hash64WithSeeds(const char *s, size_t len, uint64_t seed0, uint64_t seed1);
uint64_t Hash64WithSeed(const char *s, size_t len, uint64_t seed) {
return Hash64WithSeeds(s, len, k2, seed);
}
uint64_t Hash64WithSeeds(const char *s, size_t len, uint64_t seed0, uint64_t seed1) {
return HashLen16(Hash64(s, len) - seed0, seed1);
}
} // namespace farmhashna
|
