]>
git.ipfire.org Git - thirdparty/u-boot.git/blob - lib/xxhash.c
1 // SPDX-License-Identifier: (GPL-2.0 or BSD-2-Clause)
3 * xxHash - Extremely Fast Hash algorithm
4 * Copyright (C) 2012-2016, Yann Collet.
6 * You can contact the author at:
7 * - xxHash homepage: http://cyan4973.github.io/xxHash/
8 * - xxHash source repository: https://github.com/Cyan4973/xxHash
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>
19 /*-*************************************
21 **************************************/
22 #define xxh_rotl32(x, r) ((x << r) | (x >> (32 - r)))
23 #define xxh_rotl64(x, r) ((x << r) | (x >> (64 - r)))
25 #ifdef __LITTLE_ENDIAN
26 # define XXH_CPU_LITTLE_ENDIAN 1
28 # define XXH_CPU_LITTLE_ENDIAN 0
31 /*-*************************************
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;
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;
46 /*-**************************
48 ***************************/
49 void xxh32_copy_state(struct xxh32_state
*dst
, const struct xxh32_state
*src
)
51 memcpy(dst
, src
, sizeof(*dst
));
53 EXPORT_SYMBOL(xxh32_copy_state
);
55 void xxh64_copy_state(struct xxh64_state
*dst
, const struct xxh64_state
*src
)
57 memcpy(dst
, src
, sizeof(*dst
));
59 EXPORT_SYMBOL(xxh64_copy_state
);
61 /*-***************************
62 * Simple Hash Functions
63 ****************************/
64 static uint32_t xxh32_round(uint32_t seed
, const uint32_t input
)
66 seed
+= input
* PRIME32_2
;
67 seed
= xxh_rotl32(seed
, 13);
72 uint32_t xxh32(const void *input
, const size_t len
, const uint32_t seed
)
74 const uint8_t *p
= (const uint8_t *)input
;
75 const uint8_t *b_end
= p
+ len
;
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
;
86 v1
= xxh32_round(v1
, get_unaligned_le32(p
));
88 v2
= xxh32_round(v2
, get_unaligned_le32(p
));
90 v3
= xxh32_round(v3
, get_unaligned_le32(p
));
92 v4
= xxh32_round(v4
, get_unaligned_le32(p
));
96 h32
= xxh_rotl32(v1
, 1) + xxh_rotl32(v2
, 7) +
97 xxh_rotl32(v3
, 12) + xxh_rotl32(v4
, 18);
99 h32
= seed
+ PRIME32_5
;
102 h32
+= (uint32_t)len
;
104 while (p
+ 4 <= b_end
) {
105 h32
+= get_unaligned_le32(p
) * PRIME32_3
;
106 h32
= xxh_rotl32(h32
, 17) * PRIME32_4
;
111 h32
+= (*p
) * PRIME32_5
;
112 h32
= xxh_rotl32(h32
, 11) * PRIME32_1
;
124 EXPORT_SYMBOL(xxh32
);
126 static uint64_t xxh64_round(uint64_t acc
, const uint64_t input
)
128 acc
+= input
* PRIME64_2
;
129 acc
= xxh_rotl64(acc
, 31);
134 static uint64_t xxh64_merge_round(uint64_t acc
, uint64_t val
)
136 val
= xxh64_round(0, val
);
138 acc
= acc
* PRIME64_1
+ PRIME64_4
;
142 uint64_t xxh64(const void *input
, const size_t len
, const uint64_t seed
)
144 const uint8_t *p
= (const uint8_t *)input
;
145 const uint8_t *const b_end
= p
+ len
;
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
;
156 v1
= xxh64_round(v1
, get_unaligned_le64(p
));
158 v2
= xxh64_round(v2
, get_unaligned_le64(p
));
160 v3
= xxh64_round(v3
, get_unaligned_le64(p
));
162 v4
= xxh64_round(v4
, get_unaligned_le64(p
));
164 } while (p
<= limit
);
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
);
174 h64
= seed
+ PRIME64_5
;
177 h64
+= (uint64_t)len
;
179 while (p
+ 8 <= b_end
) {
180 const uint64_t k1
= xxh64_round(0, get_unaligned_le64(p
));
183 h64
= xxh_rotl64(h64
, 27) * PRIME64_1
+ PRIME64_4
;
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
;
194 h64
^= (*p
) * PRIME64_5
;
195 h64
= xxh_rotl64(h64
, 11) * PRIME64_1
;
207 EXPORT_SYMBOL(xxh64
);
209 /*-**************************************************
210 * Advanced Hash Functions
211 ***************************************************/
212 void xxh32_reset(struct xxh32_state
*statePtr
, const uint32_t seed
)
214 /* use a local state for memcpy() to avoid strict-aliasing warnings */
215 struct xxh32_state state
;
217 memset(&state
, 0, sizeof(state
));
218 state
.v1
= seed
+ PRIME32_1
+ PRIME32_2
;
219 state
.v2
= seed
+ PRIME32_2
;
221 state
.v4
= seed
- PRIME32_1
;
222 memcpy(statePtr
, &state
, sizeof(state
));
224 EXPORT_SYMBOL(xxh32_reset
);
226 void xxh64_reset(struct xxh64_state
*statePtr
, const uint64_t seed
)
228 /* use a local state for memcpy() to avoid strict-aliasing warnings */
229 struct xxh64_state state
;
231 memset(&state
, 0, sizeof(state
));
232 state
.v1
= seed
+ PRIME64_1
+ PRIME64_2
;
233 state
.v2
= seed
+ PRIME64_2
;
235 state
.v4
= seed
- PRIME64_1
;
236 memcpy(statePtr
, &state
, sizeof(state
));
238 EXPORT_SYMBOL(xxh64_reset
);
240 int xxh32_update(struct xxh32_state
*state
, const void *input
, const size_t len
)
242 const uint8_t *p
= (const uint8_t *)input
;
243 const uint8_t *const b_end
= p
+ len
;
248 state
->total_len_32
+= (uint32_t)len
;
249 state
->large_len
|= (len
>= 16) | (state
->total_len_32
>= 16);
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
;
257 if (state
->memsize
) { /* some data left from previous update */
258 const uint32_t *p32
= state
->mem32
;
260 memcpy((uint8_t *)(state
->mem32
) + state
->memsize
, input
,
261 16 - state
->memsize
);
263 state
->v1
= xxh32_round(state
->v1
, get_unaligned_le32(p32
));
265 state
->v2
= xxh32_round(state
->v2
, get_unaligned_le32(p32
));
267 state
->v3
= xxh32_round(state
->v3
, get_unaligned_le32(p32
));
269 state
->v4
= xxh32_round(state
->v4
, get_unaligned_le32(p32
));
272 p
+= 16-state
->memsize
;
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
;
284 v1
= xxh32_round(v1
, get_unaligned_le32(p
));
286 v2
= xxh32_round(v2
, get_unaligned_le32(p
));
288 v3
= xxh32_round(v3
, get_unaligned_le32(p
));
290 v4
= xxh32_round(v4
, get_unaligned_le32(p
));
292 } while (p
<= limit
);
301 memcpy(state
->mem32
, p
, (size_t)(b_end
-p
));
302 state
->memsize
= (uint32_t)(b_end
-p
);
307 EXPORT_SYMBOL(xxh32_update
);
309 uint32_t xxh32_digest(const struct xxh32_state
*state
)
311 const uint8_t *p
= (const uint8_t *)state
->mem32
;
312 const uint8_t *const b_end
= (const uint8_t *)(state
->mem32
) +
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);
320 h32
= state
->v3
/* == seed */ + PRIME32_5
;
323 h32
+= state
->total_len_32
;
325 while (p
+ 4 <= b_end
) {
326 h32
+= get_unaligned_le32(p
) * PRIME32_3
;
327 h32
= xxh_rotl32(h32
, 17) * PRIME32_4
;
332 h32
+= (*p
) * PRIME32_5
;
333 h32
= xxh_rotl32(h32
, 11) * PRIME32_1
;
345 EXPORT_SYMBOL(xxh32_digest
);
347 int xxh64_update(struct xxh64_state
*state
, const void *input
, const size_t len
)
349 const uint8_t *p
= (const uint8_t *)input
;
350 const uint8_t *const b_end
= p
+ len
;
355 state
->total_len
+= len
;
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
;
363 if (state
->memsize
) { /* tmp buffer is full */
364 uint64_t *p64
= state
->mem64
;
366 memcpy(((uint8_t *)p64
) + state
->memsize
, input
,
367 32 - state
->memsize
);
369 state
->v1
= xxh64_round(state
->v1
, get_unaligned_le64(p64
));
371 state
->v2
= xxh64_round(state
->v2
, get_unaligned_le64(p64
));
373 state
->v3
= xxh64_round(state
->v3
, get_unaligned_le64(p64
));
375 state
->v4
= xxh64_round(state
->v4
, get_unaligned_le64(p64
));
377 p
+= 32 - state
->memsize
;
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
;
389 v1
= xxh64_round(v1
, get_unaligned_le64(p
));
391 v2
= xxh64_round(v2
, get_unaligned_le64(p
));
393 v3
= xxh64_round(v3
, get_unaligned_le64(p
));
395 v4
= xxh64_round(v4
, get_unaligned_le64(p
));
397 } while (p
<= limit
);
406 memcpy(state
->mem64
, p
, (size_t)(b_end
-p
));
407 state
->memsize
= (uint32_t)(b_end
- p
);
412 EXPORT_SYMBOL(xxh64_update
);
414 uint64_t xxh64_digest(const struct xxh64_state
*state
)
416 const uint8_t *p
= (const uint8_t *)state
->mem64
;
417 const uint8_t *const b_end
= (const uint8_t *)state
->mem64
+
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
;
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
);
434 h64
= state
->v3
+ PRIME64_5
;
437 h64
+= (uint64_t)state
->total_len
;
439 while (p
+ 8 <= b_end
) {
440 const uint64_t k1
= xxh64_round(0, get_unaligned_le64(p
));
443 h64
= xxh_rotl64(h64
, 27) * PRIME64_1
+ PRIME64_4
;
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
;
454 h64
^= (*p
) * PRIME64_5
;
455 h64
= xxh_rotl64(h64
, 11) * PRIME64_1
;
467 EXPORT_SYMBOL(xxh64_digest
);