1 // SPDX-License-Identifier: (GPL-2.0 or BSD-2-Clause)
2 /*
3 * xxHash - Extremely Fast Hash algorithm
4 * Copyright (C) 2012-2016, Yann Collet.
5 *
6 * You can contact the author at:
7 * - xxHash homepage: http://cyan4973.github.io/xxHash/
8 * - xxHash source repository: https://github.com/Cyan4973/xxHash
9 */
10
11 #include <asm/unaligned.h>
12 #include <linux/errno.h>
13 #include <linux/compiler.h>
14 #include <linux/kernel.h>
15 #include <linux/compat.h>
16 #include <linux/string.h>
17 #include <linux/xxhash.h>
18
19 /*-*************************************
20 * Macros
21 **************************************/
22 #define xxh_rotl32(x, r) ((x << r) | (x >> (32 - r)))
23 #define xxh_rotl64(x, r) ((x << r) | (x >> (64 - r)))
24
25 #ifdef __LITTLE_ENDIAN
26 # define XXH_CPU_LITTLE_ENDIAN 1
27 #else
28 # define XXH_CPU_LITTLE_ENDIAN 0
29 #endif
30
31 /*-*************************************
32 * Constants
33 **************************************/
34 static const uint32_t PRIME32_1 = 2654435761U;
35 static const uint32_t PRIME32_2 = 2246822519U;
36 static const uint32_t PRIME32_3 = 3266489917U;
37 static const uint32_t PRIME32_4 = 668265263U;
38 static const uint32_t PRIME32_5 = 374761393U;
39
40 static const uint64_t PRIME64_1 = 11400714785074694791ULL;
41 static const uint64_t PRIME64_2 = 14029467366897019727ULL;
42 static const uint64_t PRIME64_3 = 1609587929392839161ULL;
43 static const uint64_t PRIME64_4 = 9650029242287828579ULL;
44 static const uint64_t PRIME64_5 = 2870177450012600261ULL;
45
46 /*-**************************
47 * Utils
48 ***************************/
xxh32_copy_state(struct xxh32_state * dst,const struct xxh32_state * src)49 void xxh32_copy_state(struct xxh32_state *dst, const struct xxh32_state *src)
50 {
51 memcpy(dst, src, sizeof(*dst));
52 }
53 EXPORT_SYMBOL(xxh32_copy_state);
54
xxh64_copy_state(struct xxh64_state * dst,const struct xxh64_state * src)55 void xxh64_copy_state(struct xxh64_state *dst, const struct xxh64_state *src)
56 {
57 memcpy(dst, src, sizeof(*dst));
58 }
59 EXPORT_SYMBOL(xxh64_copy_state);
60
61 /*-***************************
62 * Simple Hash Functions
63 ****************************/
xxh32_round(uint32_t seed,const uint32_t input)64 static uint32_t xxh32_round(uint32_t seed, const uint32_t input)
65 {
66 seed += input * PRIME32_2;
67 seed = xxh_rotl32(seed, 13);
68 seed *= PRIME32_1;
69 return seed;
70 }
71
xxh32(const void * input,const size_t len,const uint32_t seed)72 uint32_t xxh32(const void *input, const size_t len, const uint32_t seed)
73 {
74 const uint8_t *p = (const uint8_t *)input;
75 const uint8_t *b_end = p + len;
76 uint32_t h32;
77
78 if (len >= 16) {
79 const uint8_t *const limit = b_end - 16;
80 uint32_t v1 = seed + PRIME32_1 + PRIME32_2;
81 uint32_t v2 = seed + PRIME32_2;
82 uint32_t v3 = seed + 0;
83 uint32_t v4 = seed - PRIME32_1;
84
85 do {
86 v1 = xxh32_round(v1, get_unaligned_le32(p));
87 p += 4;
88 v2 = xxh32_round(v2, get_unaligned_le32(p));
89 p += 4;
90 v3 = xxh32_round(v3, get_unaligned_le32(p));
91 p += 4;
92 v4 = xxh32_round(v4, get_unaligned_le32(p));
93 p += 4;
94 } while (p <= limit);
95
96 h32 = xxh_rotl32(v1, 1) + xxh_rotl32(v2, 7) +
97 xxh_rotl32(v3, 12) + xxh_rotl32(v4, 18);
98 } else {
99 h32 = seed + PRIME32_5;
100 }
101
102 h32 += (uint32_t)len;
103
104 while (p + 4 <= b_end) {
105 h32 += get_unaligned_le32(p) * PRIME32_3;
106 h32 = xxh_rotl32(h32, 17) * PRIME32_4;
107 p += 4;
108 }
109
110 while (p < b_end) {
111 h32 += (*p) * PRIME32_5;
112 h32 = xxh_rotl32(h32, 11) * PRIME32_1;
113 p++;
114 }
115
116 h32 ^= h32 >> 15;
117 h32 *= PRIME32_2;
118 h32 ^= h32 >> 13;
119 h32 *= PRIME32_3;
120 h32 ^= h32 >> 16;
121
122 return h32;
123 }
124 EXPORT_SYMBOL(xxh32);
125
xxh64_round(uint64_t acc,const uint64_t input)126 static uint64_t xxh64_round(uint64_t acc, const uint64_t input)
127 {
128 acc += input * PRIME64_2;
129 acc = xxh_rotl64(acc, 31);
130 acc *= PRIME64_1;
131 return acc;
132 }
133
xxh64_merge_round(uint64_t acc,uint64_t val)134 static uint64_t xxh64_merge_round(uint64_t acc, uint64_t val)
135 {
136 val = xxh64_round(0, val);
137 acc ^= val;
138 acc = acc * PRIME64_1 + PRIME64_4;
139 return acc;
140 }
141
xxh64(const void * input,const size_t len,const uint64_t seed)142 uint64_t xxh64(const void *input, const size_t len, const uint64_t seed)
143 {
144 const uint8_t *p = (const uint8_t *)input;
145 const uint8_t *const b_end = p + len;
146 uint64_t h64;
147
148 if (len >= 32) {
149 const uint8_t *const limit = b_end - 32;
150 uint64_t v1 = seed + PRIME64_1 + PRIME64_2;
151 uint64_t v2 = seed + PRIME64_2;
152 uint64_t v3 = seed + 0;
153 uint64_t v4 = seed - PRIME64_1;
154
155 do {
156 v1 = xxh64_round(v1, get_unaligned_le64(p));
157 p += 8;
158 v2 = xxh64_round(v2, get_unaligned_le64(p));
159 p += 8;
160 v3 = xxh64_round(v3, get_unaligned_le64(p));
161 p += 8;
162 v4 = xxh64_round(v4, get_unaligned_le64(p));
163 p += 8;
164 } while (p <= limit);
165
166 h64 = xxh_rotl64(v1, 1) + xxh_rotl64(v2, 7) +
167 xxh_rotl64(v3, 12) + xxh_rotl64(v4, 18);
168 h64 = xxh64_merge_round(h64, v1);
169 h64 = xxh64_merge_round(h64, v2);
170 h64 = xxh64_merge_round(h64, v3);
171 h64 = xxh64_merge_round(h64, v4);
172
173 } else {
174 h64 = seed + PRIME64_5;
175 }
176
177 h64 += (uint64_t)len;
178
179 while (p + 8 <= b_end) {
180 const uint64_t k1 = xxh64_round(0, get_unaligned_le64(p));
181
182 h64 ^= k1;
183 h64 = xxh_rotl64(h64, 27) * PRIME64_1 + PRIME64_4;
184 p += 8;
185 }
186
187 if (p + 4 <= b_end) {
188 h64 ^= (uint64_t)(get_unaligned_le32(p)) * PRIME64_1;
189 h64 = xxh_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
190 p += 4;
191 }
192
193 while (p < b_end) {
194 h64 ^= (*p) * PRIME64_5;
195 h64 = xxh_rotl64(h64, 11) * PRIME64_1;
196 p++;
197 }
198
199 h64 ^= h64 >> 33;
200 h64 *= PRIME64_2;
201 h64 ^= h64 >> 29;
202 h64 *= PRIME64_3;
203 h64 ^= h64 >> 32;
204
205 return h64;
206 }
207 EXPORT_SYMBOL(xxh64);
208
209 /*-**************************************************
210 * Advanced Hash Functions
211 ***************************************************/
xxh32_reset(struct xxh32_state * statePtr,const uint32_t seed)212 void xxh32_reset(struct xxh32_state *statePtr, const uint32_t seed)
213 {
214 /* use a local state for memcpy() to avoid strict-aliasing warnings */
215 struct xxh32_state state;
216
217 memset(&state, 0, sizeof(state));
218 state.v1 = seed + PRIME32_1 + PRIME32_2;
219 state.v2 = seed + PRIME32_2;
220 state.v3 = seed + 0;
221 state.v4 = seed - PRIME32_1;
222 memcpy(statePtr, &state, sizeof(state));
223 }
224 EXPORT_SYMBOL(xxh32_reset);
225
xxh64_reset(struct xxh64_state * statePtr,const uint64_t seed)226 void xxh64_reset(struct xxh64_state *statePtr, const uint64_t seed)
227 {
228 /* use a local state for memcpy() to avoid strict-aliasing warnings */
229 struct xxh64_state state;
230
231 memset(&state, 0, sizeof(state));
232 state.v1 = seed + PRIME64_1 + PRIME64_2;
233 state.v2 = seed + PRIME64_2;
234 state.v3 = seed + 0;
235 state.v4 = seed - PRIME64_1;
236 memcpy(statePtr, &state, sizeof(state));
237 }
238 EXPORT_SYMBOL(xxh64_reset);
239
xxh32_update(struct xxh32_state * state,const void * input,const size_t len)240 int xxh32_update(struct xxh32_state *state, const void *input, const size_t len)
241 {
242 const uint8_t *p = (const uint8_t *)input;
243 const uint8_t *const b_end = p + len;
244
245 if (input == NULL)
246 return -EINVAL;
247
248 state->total_len_32 += (uint32_t)len;
249 state->large_len |= (len >= 16) | (state->total_len_32 >= 16);
250
251 if (state->memsize + len < 16) { /* fill in tmp buffer */
252 memcpy((uint8_t *)(state->mem32) + state->memsize, input, len);
253 state->memsize += (uint32_t)len;
254 return 0;
255 }
256
257 if (state->memsize) { /* some data left from previous update */
258 const uint32_t *p32 = state->mem32;
259
260 memcpy((uint8_t *)(state->mem32) + state->memsize, input,
261 16 - state->memsize);
262
263 state->v1 = xxh32_round(state->v1, get_unaligned_le32(p32));
264 p32++;
265 state->v2 = xxh32_round(state->v2, get_unaligned_le32(p32));
266 p32++;
267 state->v3 = xxh32_round(state->v3, get_unaligned_le32(p32));
268 p32++;
269 state->v4 = xxh32_round(state->v4, get_unaligned_le32(p32));
270 p32++;
271
272 p += 16-state->memsize;
273 state->memsize = 0;
274 }
275
276 if (p <= b_end - 16) {
277 const uint8_t *const limit = b_end - 16;
278 uint32_t v1 = state->v1;
279 uint32_t v2 = state->v2;
280 uint32_t v3 = state->v3;
281 uint32_t v4 = state->v4;
282
283 do {
284 v1 = xxh32_round(v1, get_unaligned_le32(p));
285 p += 4;
286 v2 = xxh32_round(v2, get_unaligned_le32(p));
287 p += 4;
288 v3 = xxh32_round(v3, get_unaligned_le32(p));
289 p += 4;
290 v4 = xxh32_round(v4, get_unaligned_le32(p));
291 p += 4;
292 } while (p <= limit);
293
294 state->v1 = v1;
295 state->v2 = v2;
296 state->v3 = v3;
297 state->v4 = v4;
298 }
299
300 if (p < b_end) {
301 memcpy(state->mem32, p, (size_t)(b_end-p));
302 state->memsize = (uint32_t)(b_end-p);
303 }
304
305 return 0;
306 }
307 EXPORT_SYMBOL(xxh32_update);
308
xxh32_digest(const struct xxh32_state * state)309 uint32_t xxh32_digest(const struct xxh32_state *state)
310 {
311 const uint8_t *p = (const uint8_t *)state->mem32;
312 const uint8_t *const b_end = (const uint8_t *)(state->mem32) +
313 state->memsize;
314 uint32_t h32;
315
316 if (state->large_len) {
317 h32 = xxh_rotl32(state->v1, 1) + xxh_rotl32(state->v2, 7) +
318 xxh_rotl32(state->v3, 12) + xxh_rotl32(state->v4, 18);
319 } else {
320 h32 = state->v3 /* == seed */ + PRIME32_5;
321 }
322
323 h32 += state->total_len_32;
324
325 while (p + 4 <= b_end) {
326 h32 += get_unaligned_le32(p) * PRIME32_3;
327 h32 = xxh_rotl32(h32, 17) * PRIME32_4;
328 p += 4;
329 }
330
331 while (p < b_end) {
332 h32 += (*p) * PRIME32_5;
333 h32 = xxh_rotl32(h32, 11) * PRIME32_1;
334 p++;
335 }
336
337 h32 ^= h32 >> 15;
338 h32 *= PRIME32_2;
339 h32 ^= h32 >> 13;
340 h32 *= PRIME32_3;
341 h32 ^= h32 >> 16;
342
343 return h32;
344 }
345 EXPORT_SYMBOL(xxh32_digest);
346
xxh64_update(struct xxh64_state * state,const void * input,const size_t len)347 int xxh64_update(struct xxh64_state *state, const void *input, const size_t len)
348 {
349 const uint8_t *p = (const uint8_t *)input;
350 const uint8_t *const b_end = p + len;
351
352 if (input == NULL)
353 return -EINVAL;
354
355 state->total_len += len;
356
357 if (state->memsize + len < 32) { /* fill in tmp buffer */
358 memcpy(((uint8_t *)state->mem64) + state->memsize, input, len);
359 state->memsize += (uint32_t)len;
360 return 0;
361 }
362
363 if (state->memsize) { /* tmp buffer is full */
364 uint64_t *p64 = state->mem64;
365
366 memcpy(((uint8_t *)p64) + state->memsize, input,
367 32 - state->memsize);
368
369 state->v1 = xxh64_round(state->v1, get_unaligned_le64(p64));
370 p64++;
371 state->v2 = xxh64_round(state->v2, get_unaligned_le64(p64));
372 p64++;
373 state->v3 = xxh64_round(state->v3, get_unaligned_le64(p64));
374 p64++;
375 state->v4 = xxh64_round(state->v4, get_unaligned_le64(p64));
376
377 p += 32 - state->memsize;
378 state->memsize = 0;
379 }
380
381 if (p + 32 <= b_end) {
382 const uint8_t *const limit = b_end - 32;
383 uint64_t v1 = state->v1;
384 uint64_t v2 = state->v2;
385 uint64_t v3 = state->v3;
386 uint64_t v4 = state->v4;
387
388 do {
389 v1 = xxh64_round(v1, get_unaligned_le64(p));
390 p += 8;
391 v2 = xxh64_round(v2, get_unaligned_le64(p));
392 p += 8;
393 v3 = xxh64_round(v3, get_unaligned_le64(p));
394 p += 8;
395 v4 = xxh64_round(v4, get_unaligned_le64(p));
396 p += 8;
397 } while (p <= limit);
398
399 state->v1 = v1;
400 state->v2 = v2;
401 state->v3 = v3;
402 state->v4 = v4;
403 }
404
405 if (p < b_end) {
406 memcpy(state->mem64, p, (size_t)(b_end-p));
407 state->memsize = (uint32_t)(b_end - p);
408 }
409
410 return 0;
411 }
412 EXPORT_SYMBOL(xxh64_update);
413
xxh64_digest(const struct xxh64_state * state)414 uint64_t xxh64_digest(const struct xxh64_state *state)
415 {
416 const uint8_t *p = (const uint8_t *)state->mem64;
417 const uint8_t *const b_end = (const uint8_t *)state->mem64 +
418 state->memsize;
419 uint64_t h64;
420
421 if (state->total_len >= 32) {
422 const uint64_t v1 = state->v1;
423 const uint64_t v2 = state->v2;
424 const uint64_t v3 = state->v3;
425 const uint64_t v4 = state->v4;
426
427 h64 = xxh_rotl64(v1, 1) + xxh_rotl64(v2, 7) +
428 xxh_rotl64(v3, 12) + xxh_rotl64(v4, 18);
429 h64 = xxh64_merge_round(h64, v1);
430 h64 = xxh64_merge_round(h64, v2);
431 h64 = xxh64_merge_round(h64, v3);
432 h64 = xxh64_merge_round(h64, v4);
433 } else {
434 h64 = state->v3 + PRIME64_5;
435 }
436
437 h64 += (uint64_t)state->total_len;
438
439 while (p + 8 <= b_end) {
440 const uint64_t k1 = xxh64_round(0, get_unaligned_le64(p));
441
442 h64 ^= k1;
443 h64 = xxh_rotl64(h64, 27) * PRIME64_1 + PRIME64_4;
444 p += 8;
445 }
446
447 if (p + 4 <= b_end) {
448 h64 ^= (uint64_t)(get_unaligned_le32(p)) * PRIME64_1;
449 h64 = xxh_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
450 p += 4;
451 }
452
453 while (p < b_end) {
454 h64 ^= (*p) * PRIME64_5;
455 h64 = xxh_rotl64(h64, 11) * PRIME64_1;
456 p++;
457 }
458
459 h64 ^= h64 >> 33;
460 h64 *= PRIME64_2;
461 h64 ^= h64 >> 29;
462 h64 *= PRIME64_3;
463 h64 ^= h64 >> 32;
464
465 return h64;
466 }
467 EXPORT_SYMBOL(xxh64_digest);
468