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
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
|
#include "common.h"
namespace {
#include "farmhashxo.cc"
}
namespace farmhashte {
#if !can_use_sse41 || !x86_64
uint64_t Hash64(const char *s, size_t len) {
FARMHASH_DIE_IF_MISCONFIGURED;
return s == NULL ? 0 : len;
}
uint64_t Hash64WithSeed(const char *s, size_t len, uint64_t seed) {
FARMHASH_DIE_IF_MISCONFIGURED;
return seed + Hash64(s, len);
}
uint64_t Hash64WithSeeds(const char *s, size_t len,
uint64_t seed0, uint64_t seed1) {
FARMHASH_DIE_IF_MISCONFIGURED;
return seed0 + seed1 + Hash64(s, len);
}
#else
#undef Fetch
#define Fetch Fetch64
#undef Rotate
#define Rotate Rotate64
#undef Bswap
#define Bswap Bswap64
// Helpers for data-parallel operations (1x 128 bits or 2x 64 or 4x 32).
STATIC_INLINE __m128i Add(__m128i x, __m128i y) { return _mm_add_epi64(x, y); }
STATIC_INLINE __m128i Xor(__m128i x, __m128i y) { return _mm_xor_si128(x, y); }
STATIC_INLINE __m128i Mul(__m128i x, __m128i y) { return _mm_mullo_epi32(x, y); }
STATIC_INLINE __m128i Shuf(__m128i x, __m128i y) { return _mm_shuffle_epi8(y, x); }
// Requires n >= 256. Requires SSE4.1. Should be slightly faster if the
// compiler uses AVX instructions (e.g., use the -mavx flag with GCC).
STATIC_INLINE uint64_t Hash64Long(const char* s, size_t n,
uint64_t seed0, uint64_t seed1) {
const __m128i kShuf =
_mm_set_epi8(4, 11, 10, 5, 8, 15, 6, 9, 12, 2, 14, 13, 0, 7, 3, 1);
const __m128i kMult =
_mm_set_epi8(0xbd, 0xd6, 0x33, 0x39, 0x45, 0x54, 0xfa, 0x03,
0x34, 0x3e, 0x33, 0xed, 0xcc, 0x9e, 0x2d, 0x51);
uint64_t seed2 = (seed0 + 113) * (seed1 + 9);
uint64_t seed3 = (Rotate(seed0, 23) + 27) * (Rotate(seed1, 30) + 111);
__m128i d0 = _mm_cvtsi64_si128(seed0);
__m128i d1 = _mm_cvtsi64_si128(seed1);
__m128i d2 = Shuf(kShuf, d0);
__m128i d3 = Shuf(kShuf, d1);
__m128i d4 = Xor(d0, d1);
__m128i d5 = Xor(d1, d2);
__m128i d6 = Xor(d2, d4);
__m128i d7 = _mm_set1_epi32(seed2 >> 32);
__m128i d8 = Mul(kMult, d2);
__m128i d9 = _mm_set1_epi32(seed3 >> 32);
__m128i d10 = _mm_set1_epi32(seed3);
__m128i d11 = Add(d2, _mm_set1_epi32(seed2));
const char* end = s + (n & ~static_cast<size_t>(255));
do {
__m128i z;
z = Fetch128(s);
d0 = Add(d0, z);
d1 = Shuf(kShuf, d1);
d2 = Xor(d2, d0);
d4 = Xor(d4, z);
d4 = Xor(d4, d1);
std::swap(d0, d6);
z = Fetch128(s + 16);
d5 = Add(d5, z);
d6 = Shuf(kShuf, d6);
d8 = Shuf(kShuf, d8);
d7 = Xor(d7, d5);
d0 = Xor(d0, z);
d0 = Xor(d0, d6);
std::swap(d5, d11);
z = Fetch128(s + 32);
d1 = Add(d1, z);
d2 = Shuf(kShuf, d2);
d4 = Shuf(kShuf, d4);
d5 = Xor(d5, z);
d5 = Xor(d5, d2);
std::swap(d10, d4);
z = Fetch128(s + 48);
d6 = Add(d6, z);
d7 = Shuf(kShuf, d7);
d0 = Shuf(kShuf, d0);
d8 = Xor(d8, d6);
d1 = Xor(d1, z);
d1 = Add(d1, d7);
z = Fetch128(s + 64);
d2 = Add(d2, z);
d5 = Shuf(kShuf, d5);
d4 = Add(d4, d2);
d6 = Xor(d6, z);
d6 = Xor(d6, d11);
std::swap(d8, d2);
z = Fetch128(s + 80);
d7 = Xor(d7, z);
d8 = Shuf(kShuf, d8);
d1 = Shuf(kShuf, d1);
d0 = Add(d0, d7);
d2 = Add(d2, z);
d2 = Add(d2, d8);
std::swap(d1, d7);
z = Fetch128(s + 96);
d4 = Shuf(kShuf, d4);
d6 = Shuf(kShuf, d6);
d8 = Mul(kMult, d8);
d5 = Xor(d5, d11);
d7 = Xor(d7, z);
d7 = Add(d7, d4);
std::swap(d6, d0);
z = Fetch128(s + 112);
d8 = Add(d8, z);
d0 = Shuf(kShuf, d0);
d2 = Shuf(kShuf, d2);
d1 = Xor(d1, d8);
d10 = Xor(d10, z);
d10 = Xor(d10, d0);
std::swap(d11, d5);
z = Fetch128(s + 128);
d4 = Add(d4, z);
d5 = Shuf(kShuf, d5);
d7 = Shuf(kShuf, d7);
d6 = Add(d6, d4);
d8 = Xor(d8, z);
d8 = Xor(d8, d5);
std::swap(d4, d10);
z = Fetch128(s + 144);
d0 = Add(d0, z);
d1 = Shuf(kShuf, d1);
d2 = Add(d2, d0);
d4 = Xor(d4, z);
d4 = Xor(d4, d1);
z = Fetch128(s + 160);
d5 = Add(d5, z);
d6 = Shuf(kShuf, d6);
d8 = Shuf(kShuf, d8);
d7 = Xor(d7, d5);
d0 = Xor(d0, z);
d0 = Xor(d0, d6);
std::swap(d2, d8);
z = Fetch128(s + 176);
d1 = Add(d1, z);
d2 = Shuf(kShuf, d2);
d4 = Shuf(kShuf, d4);
d5 = Mul(kMult, d5);
d5 = Xor(d5, z);
d5 = Xor(d5, d2);
std::swap(d7, d1);
z = Fetch128(s + 192);
d6 = Add(d6, z);
d7 = Shuf(kShuf, d7);
d0 = Shuf(kShuf, d0);
d8 = Add(d8, d6);
d1 = Xor(d1, z);
d1 = Xor(d1, d7);
std::swap(d0, d6);
z = Fetch128(s + 208);
d2 = Add(d2, z);
d5 = Shuf(kShuf, d5);
d4 = Xor(d4, d2);
d6 = Xor(d6, z);
d6 = Xor(d6, d9);
std::swap(d5, d11);
z = Fetch128(s + 224);
d7 = Add(d7, z);
d8 = Shuf(kShuf, d8);
d1 = Shuf(kShuf, d1);
d0 = Xor(d0, d7);
d2 = Xor(d2, z);
d2 = Xor(d2, d8);
std::swap(d10, d4);
z = Fetch128(s + 240);
d3 = Add(d3, z);
d4 = Shuf(kShuf, d4);
d6 = Shuf(kShuf, d6);
d7 = Mul(kMult, d7);
d5 = Add(d5, d3);
d7 = Xor(d7, z);
d7 = Xor(d7, d4);
std::swap(d3, d9);
s += 256;
} while (s != end);
d6 = Add(Mul(kMult, d6), _mm_cvtsi64_si128(n));
if (n % 256 != 0) {
d7 = Add(_mm_shuffle_epi32(d8, (0 << 6) + (3 << 4) + (2 << 2) + (1 << 0)), d7);
d8 = Add(Mul(kMult, d8), _mm_cvtsi64_si128(farmhashxo::Hash64(s, n % 256)));
}
__m128i t[8];
d0 = Mul(kMult, Shuf(kShuf, Mul(kMult, d0)));
d3 = Mul(kMult, Shuf(kShuf, Mul(kMult, d3)));
d9 = Mul(kMult, Shuf(kShuf, Mul(kMult, d9)));
d1 = Mul(kMult, Shuf(kShuf, Mul(kMult, d1)));
d0 = Add(d11, d0);
d3 = Xor(d7, d3);
d9 = Add(d8, d9);
d1 = Add(d10, d1);
d4 = Add(d3, d4);
d5 = Add(d9, d5);
d6 = Xor(d1, d6);
d2 = Add(d0, d2);
t[0] = d0;
t[1] = d3;
t[2] = d9;
t[3] = d1;
t[4] = d4;
t[5] = d5;
t[6] = d6;
t[7] = d2;
return farmhashxo::Hash64(reinterpret_cast<const char*>(t), sizeof(t));
}
uint64_t Hash64(const char *s, size_t len) {
// Empirically, farmhashxo seems faster until length 512.
return len >= 512 ? Hash64Long(s, len, k2, k1) : farmhashxo::Hash64(s, len);
}
uint64_t Hash64WithSeed(const char *s, size_t len, uint64_t seed) {
return len >= 512 ? Hash64Long(s, len, k1, seed) :
farmhashxo::Hash64WithSeed(s, len, seed);
}
uint64_t Hash64WithSeeds(const char *s, size_t len, uint64_t seed0, uint64_t seed1) {
return len >= 512 ? Hash64Long(s, len, seed0, seed1) :
farmhashxo::Hash64WithSeeds(s, len, seed0, seed1);
}
#endif
} // namespace farmhashte
|
