aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorNick Terrell <terrelln@fb.com>2017-08-04 16:19:17 -0400
committerChris Mason <clm@fb.com>2017-08-15 12:02:07 -0400
commit5d2405227a9eaea48e8cc95756a06d407b11f141 (patch)
treee277dff5d00014f32ab1810eacdeaab97f53cf67
parentef954844c7ace62f773f4f23e28d2d915adc419f (diff)
lib: Add xxhash module
Adds xxhash kernel module with xxh32 and xxh64 hashes. xxhash is an extremely fast non-cryptographic hash algorithm for checksumming. The zstd compression and decompression modules added in the next patch require xxhash. I extracted it out from zstd since it is useful on its own. I copied the code from the upstream XXHash source repository and translated it into kernel style. I ran benchmarks and tests in the kernel and tests in userland. I benchmarked xxhash as a special character device. I ran in four modes, no-op, xxh32, xxh64, and crc32. The no-op mode simply copies the data to kernel space and ignores it. The xxh32, xxh64, and crc32 modes compute hashes on the copied data. I also ran it with four different buffer sizes. The benchmark file is located in the upstream zstd source repository under `contrib/linux-kernel/xxhash_test.c` [1]. I ran the benchmarks on a Ubuntu 14.04 VM with 2 cores and 4 GiB of RAM. The VM is running on a MacBook Pro with a 3.1 GHz Intel Core i7 processor, 16 GB of RAM, and a SSD. I benchmarked using the file `filesystem.squashfs` from `ubuntu-16.10-desktop-amd64.iso`, which is 1,536,217,088 B large. Run the following commands for the benchmark: modprobe xxhash_test mknod xxhash_test c 245 0 time cp filesystem.squashfs xxhash_test The time is reported by the time of the userland `cp`. The GB/s is computed with 1,536,217,008 B / time(buffer size, hash) which includes the time to copy from userland. The Normalized GB/s is computed with 1,536,217,088 B / (time(buffer size, hash) - time(buffer size, none)). | Buffer Size (B) | Hash | Time (s) | GB/s | Adjusted GB/s | |-----------------|-------|----------|------|---------------| | 1024 | none | 0.408 | 3.77 | - | | 1024 | xxh32 | 0.649 | 2.37 | 6.37 | | 1024 | xxh64 | 0.542 | 2.83 | 11.46 | | 1024 | crc32 | 1.290 | 1.19 | 1.74 | | 4096 | none | 0.380 | 4.04 | - | | 4096 | xxh32 | 0.645 | 2.38 | 5.79 | | 4096 | xxh64 | 0.500 | 3.07 | 12.80 | | 4096 | crc32 | 1.168 | 1.32 | 1.95 | | 8192 | none | 0.351 | 4.38 | - | | 8192 | xxh32 | 0.614 | 2.50 | 5.84 | | 8192 | xxh64 | 0.464 | 3.31 | 13.60 | | 8192 | crc32 | 1.163 | 1.32 | 1.89 | | 16384 | none | 0.346 | 4.43 | - | | 16384 | xxh32 | 0.590 | 2.60 | 6.30 | | 16384 | xxh64 | 0.466 | 3.30 | 12.80 | | 16384 | crc32 | 1.183 | 1.30 | 1.84 | Tested in userland using the test-suite in the zstd repo under `contrib/linux-kernel/test/XXHashUserlandTest.cpp` [2] by mocking the kernel functions. A line in each branch of every function in `xxhash.c` was commented out to ensure that the test-suite fails. Additionally tested while testing zstd and with SMHasher [3]. [1] https://phabricator.intern.facebook.com/P57526246 [2] https://github.com/facebook/zstd/blob/dev/contrib/linux-kernel/test/XXHashUserlandTest.cpp [3] https://github.com/aappleby/smhasher zstd source repository: https://github.com/facebook/zstd XXHash source repository: https://github.com/cyan4973/xxhash Signed-off-by: Nick Terrell <terrelln@fb.com> Signed-off-by: Chris Mason <clm@fb.com>
Diffstat
-rw-r--r--include/linux/xxhash.h236
-rw-r--r--lib/Kconfig3
-rw-r--r--lib/Makefile1
-rw-r--r--lib/xxhash.c500
4 files changed, 740 insertions, 0 deletions
diff --git a/include/linux/xxhash.h b/include/linux/xxhash.h
new file mode 100644
index 000000000000..9e1f42cb57e9
--- /dev/null
+++ b/include/linux/xxhash.h
@@ -0,0 +1,236 @@
1/*
2 * xxHash - Extremely Fast Hash algorithm
3 * Copyright (C) 2012-2016, Yann Collet.
4 *
5 * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are
9 * met:
10 *
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following disclaimer
15 * in the documentation and/or other materials provided with the
16 * distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 *
30 * This program is free software; you can redistribute it and/or modify it under
31 * the terms of the GNU General Public License version 2 as published by the
32 * Free Software Foundation. This program is dual-licensed; you may select
33 * either version 2 of the GNU General Public License ("GPL") or BSD license
34 * ("BSD").
35 *
36 * You can contact the author at:
37 * - xxHash homepage: http://cyan4973.github.io/xxHash/
38 * - xxHash source repository: https://github.com/Cyan4973/xxHash
39 */
40
41/*
42 * Notice extracted from xxHash homepage:
43 *
44 * xxHash is an extremely fast Hash algorithm, running at RAM speed limits.
45 * It also successfully passes all tests from the SMHasher suite.
46 *
47 * Comparison (single thread, Windows Seven 32 bits, using SMHasher on a Core 2
48 * Duo @3GHz)
49 *
50 * Name Speed Q.Score Author
51 * xxHash 5.4 GB/s 10
52 * CrapWow 3.2 GB/s 2 Andrew
53 * MumurHash 3a 2.7 GB/s 10 Austin Appleby
54 * SpookyHash 2.0 GB/s 10 Bob Jenkins
55 * SBox 1.4 GB/s 9 Bret Mulvey
56 * Lookup3 1.2 GB/s 9 Bob Jenkins
57 * SuperFastHash 1.2 GB/s 1 Paul Hsieh
58 * CityHash64 1.05 GB/s 10 Pike & Alakuijala
59 * FNV 0.55 GB/s 5 Fowler, Noll, Vo
60 * CRC32 0.43 GB/s 9
61 * MD5-32 0.33 GB/s 10 Ronald L. Rivest
62 * SHA1-32 0.28 GB/s 10
63 *
64 * Q.Score is a measure of quality of the hash function.
65 * It depends on successfully passing SMHasher test set.
66 * 10 is a perfect score.
67 *
68 * A 64-bits version, named xxh64 offers much better speed,
69 * but for 64-bits applications only.
70 * Name Speed on 64 bits Speed on 32 bits
71 * xxh64 13.8 GB/s 1.9 GB/s
72 * xxh32 6.8 GB/s 6.0 GB/s
73 */
74
75#ifndef XXHASH_H
76#define XXHASH_H
77
78#include <linux/types.h>
79
80/*-****************************
81 * Simple Hash Functions
82 *****************************/
83
84/**
85 * xxh32() - calculate the 32-bit hash of the input with a given seed.
86 *
87 * @input: The data to hash.
88 * @length: The length of the data to hash.
89 * @seed: The seed can be used to alter the result predictably.
90 *
91 * Speed on Core 2 Duo @ 3 GHz (single thread, SMHasher benchmark) : 5.4 GB/s
92 *
93 * Return: The 32-bit hash of the data.
94 */
95uint32_t xxh32(const void *input, size_t length, uint32_t seed);
96
97/**
98 * xxh64() - calculate the 64-bit hash of the input with a given seed.
99 *
100 * @input: The data to hash.
101 * @length: The length of the data to hash.
102 * @seed: The seed can be used to alter the result predictably.
103 *
104 * This function runs 2x faster on 64-bit systems, but slower on 32-bit systems.
105 *
106 * Return: The 64-bit hash of the data.
107 */
108uint64_t xxh64(const void *input, size_t length, uint64_t seed);
109
110/*-****************************
111 * Streaming Hash Functions
112 *****************************/
113
114/*
115 * These definitions are only meant to allow allocation of XXH state
116 * statically, on stack, or in a struct for example.
117 * Do not use members directly.
118 */
119
120/**
121 * struct xxh32_state - private xxh32 state, do not use members directly
122 */
123struct xxh32_state {
124 uint32_t total_len_32;
125 uint32_t large_len;
126 uint32_t v1;
127 uint32_t v2;
128 uint32_t v3;
129 uint32_t v4;
130 uint32_t mem32[4];
131 uint32_t memsize;
132};
133
134/**
135 * struct xxh32_state - private xxh64 state, do not use members directly
136 */
137struct xxh64_state {
138 uint64_t total_len;
139 uint64_t v1;
140 uint64_t v2;
141 uint64_t v3;
142 uint64_t v4;
143 uint64_t mem64[4];
144 uint32_t memsize;
145};
146
147/**
148 * xxh32_reset() - reset the xxh32 state to start a new hashing operation
149 *
150 * @state: The xxh32 state to reset.
151 * @seed: Initialize the hash state with this seed.
152 *
153 * Call this function on any xxh32_state to prepare for a new hashing operation.
154 */
155void xxh32_reset(struct xxh32_state *state, uint32_t seed);
156
157/**
158 * xxh32_update() - hash the data given and update the xxh32 state
159 *
160 * @state: The xxh32 state to update.
161 * @input: The data to hash.
162 * @length: The length of the data to hash.
163 *
164 * After calling xxh32_reset() call xxh32_update() as many times as necessary.
165 *
166 * Return: Zero on success, otherwise an error code.
167 */
168int xxh32_update(struct xxh32_state *state, const void *input, size_t length);
169
170/**
171 * xxh32_digest() - produce the current xxh32 hash
172 *
173 * @state: Produce the current xxh32 hash of this state.
174 *
175 * A hash value can be produced at any time. It is still possible to continue
176 * inserting input into the hash state after a call to xxh32_digest(), and
177 * generate new hashes later on, by calling xxh32_digest() again.
178 *
179 * Return: The xxh32 hash stored in the state.
180 */
181uint32_t xxh32_digest(const struct xxh32_state *state);
182
183/**
184 * xxh64_reset() - reset the xxh64 state to start a new hashing operation
185 *
186 * @state: The xxh64 state to reset.
187 * @seed: Initialize the hash state with this seed.
188 */
189void xxh64_reset(struct xxh64_state *state, uint64_t seed);
190
191/**
192 * xxh64_update() - hash the data given and update the xxh64 state
193 * @state: The xxh64 state to update.
194 * @input: The data to hash.
195 * @length: The length of the data to hash.
196 *
197 * After calling xxh64_reset() call xxh64_update() as many times as necessary.
198 *
199 * Return: Zero on success, otherwise an error code.
200 */
201int xxh64_update(struct xxh64_state *state, const void *input, size_t length);
202
203/**
204 * xxh64_digest() - produce the current xxh64 hash
205 *
206 * @state: Produce the current xxh64 hash of this state.
207 *
208 * A hash value can be produced at any time. It is still possible to continue
209 * inserting input into the hash state after a call to xxh64_digest(), and
210 * generate new hashes later on, by calling xxh64_digest() again.
211 *
212 * Return: The xxh64 hash stored in the state.
213 */
214uint64_t xxh64_digest(const struct xxh64_state *state);
215
216/*-**************************
217 * Utils
218 ***************************/
219
220/**
221 * xxh32_copy_state() - copy the source state into the destination state
222 *
223 * @src: The source xxh32 state.
224 * @dst: The destination xxh32 state.
225 */
226void xxh32_copy_state(struct xxh32_state *dst, const struct xxh32_state *src);
227
228/**
229 * xxh64_copy_state() - copy the source state into the destination state
230 *
231 * @src: The source xxh64 state.
232 * @dst: The destination xxh64 state.
233 */
234void xxh64_copy_state(struct xxh64_state *dst, const struct xxh64_state *src);
235
236#endif /* XXHASH_H */
diff --git a/lib/Kconfig b/lib/Kconfig
index 6762529ad9e4..5e7541f46081 100644
--- a/lib/Kconfig
+++ b/lib/Kconfig
@@ -192,6 +192,9 @@ config CRC8
192 when they need to do cyclic redundancy check according CRC8 192 when they need to do cyclic redundancy check according CRC8
193 algorithm. Module will be called crc8. 193 algorithm. Module will be called crc8.
194 194
195config XXHASH
196 tristate
197
195config AUDIT_GENERIC 198config AUDIT_GENERIC
196 bool 199 bool
197 depends on AUDIT && !AUDIT_ARCH 200 depends on AUDIT && !AUDIT_ARCH
diff --git a/lib/Makefile b/lib/Makefile
index 40c18372b301..d06b68ae55a3 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -102,6 +102,7 @@ obj-$(CONFIG_CRC4) += crc4.o
102obj-$(CONFIG_CRC7) += crc7.o 102obj-$(CONFIG_CRC7) += crc7.o
103obj-$(CONFIG_LIBCRC32C) += libcrc32c.o 103obj-$(CONFIG_LIBCRC32C) += libcrc32c.o
104obj-$(CONFIG_CRC8) += crc8.o 104obj-$(CONFIG_CRC8) += crc8.o
105obj-$(CONFIG_XXHASH) += xxhash.o
105obj-$(CONFIG_GENERIC_ALLOCATOR) += genalloc.o 106obj-$(CONFIG_GENERIC_ALLOCATOR) += genalloc.o
106 107
107obj-$(CONFIG_842_COMPRESS) += 842/ 108obj-$(CONFIG_842_COMPRESS) += 842/
diff --git a/lib/xxhash.c b/lib/xxhash.c
new file mode 100644
index 000000000000..aa61e2a3802f
--- /dev/null
+++ b/lib/xxhash.c
@@ -0,0 +1,500 @@
1/*
2 * xxHash - Extremely Fast Hash algorithm
3 * Copyright (C) 2012-2016, Yann Collet.
4 *
5 * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions are
9 * met:
10 *
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following disclaimer
15 * in the documentation and/or other materials provided with the
16 * distribution.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 *
30 * This program is free software; you can redistribute it and/or modify it under
31 * the terms of the GNU General Public License version 2 as published by the
32 * Free Software Foundation. This program is dual-licensed; you may select
33 * either version 2 of the GNU General Public License ("GPL") or BSD license
34 * ("BSD").
35 *
36 * You can contact the author at:
37 * - xxHash homepage: http://cyan4973.github.io/xxHash/
38 * - xxHash source repository: https://github.com/Cyan4973/xxHash
39 */
40
41#include <asm/unaligned.h>
42#include <linux/errno.h>
43#include <linux/compiler.h>
44#include <linux/kernel.h>
45#include <linux/module.h>
46#include <linux/string.h>
47#include <linux/xxhash.h>
48
49/*-*************************************
50 * Macros
51 **************************************/
52#define xxh_rotl32(x, r) ((x << r) | (x >> (32 - r)))
53#define xxh_rotl64(x, r) ((x << r) | (x >> (64 - r)))
54
55#ifdef __LITTLE_ENDIAN
56# define XXH_CPU_LITTLE_ENDIAN 1
57#else
58# define XXH_CPU_LITTLE_ENDIAN 0
59#endif
60
61/*-*************************************
62 * Constants
63 **************************************/
64static const uint32_t PRIME32_1 = 2654435761U;
65static const uint32_t PRIME32_2 = 2246822519U;
66static const uint32_t PRIME32_3 = 3266489917U;
67static const uint32_t PRIME32_4 = 668265263U;
68static const uint32_t PRIME32_5 = 374761393U;
69
70static const uint64_t PRIME64_1 = 11400714785074694791ULL;
71static const uint64_t PRIME64_2 = 14029467366897019727ULL;
72static const uint64_t PRIME64_3 = 1609587929392839161ULL;
73static const uint64_t PRIME64_4 = 9650029242287828579ULL;
74static const uint64_t PRIME64_5 = 2870177450012600261ULL;
75
76/*-**************************
77 * Utils
78 ***************************/
79void xxh32_copy_state(struct xxh32_state *dst, const struct xxh32_state *src)
80{
81 memcpy(dst, src, sizeof(*dst));
82}
83EXPORT_SYMBOL(xxh32_copy_state);
84
85void xxh64_copy_state(struct xxh64_state *dst, const struct xxh64_state *src)
86{
87 memcpy(dst, src, sizeof(*dst));
88}
89EXPORT_SYMBOL(xxh64_copy_state);
90
91/*-***************************
92 * Simple Hash Functions
93 ****************************/
94static uint32_t xxh32_round(uint32_t seed, const uint32_t input)
95{
96 seed += input * PRIME32_2;
97 seed = xxh_rotl32(seed, 13);
98 seed *= PRIME32_1;
99 return seed;
100}
101
102uint32_t xxh32(const void *input, const size_t len, const uint32_t seed)
103{
104 const uint8_t *p = (const uint8_t *)input;
105 const uint8_t *b_end = p + len;
106 uint32_t h32;
107
108 if (len >= 16) {
109 const uint8_t *const limit = b_end - 16;
110 uint32_t v1 = seed + PRIME32_1 + PRIME32_2;
111 uint32_t v2 = seed + PRIME32_2;
112 uint32_t v3 = seed + 0;
113 uint32_t v4 = seed - PRIME32_1;
114
115 do {
116 v1 = xxh32_round(v1, get_unaligned_le32(p));
117 p += 4;
118 v2 = xxh32_round(v2, get_unaligned_le32(p));
119 p += 4;
120 v3 = xxh32_round(v3, get_unaligned_le32(p));
121 p += 4;
122 v4 = xxh32_round(v4, get_unaligned_le32(p));
123 p += 4;
124 } while (p <= limit);
125
126 h32 = xxh_rotl32(v1, 1) + xxh_rotl32(v2, 7) +
127 xxh_rotl32(v3, 12) + xxh_rotl32(v4, 18);
128 } else {
129 h32 = seed + PRIME32_5;
130 }
131
132 h32 += (uint32_t)len;
133
134 while (p + 4 <= b_end) {
135 h32 += get_unaligned_le32(p) * PRIME32_3;
136 h32 = xxh_rotl32(h32, 17) * PRIME32_4;
137 p += 4;
138 }
139
140 while (p < b_end) {
141 h32 += (*p) * PRIME32_5;
142 h32 = xxh_rotl32(h32, 11) * PRIME32_1;
143 p++;
144 }
145
146 h32 ^= h32 >> 15;
147 h32 *= PRIME32_2;
148 h32 ^= h32 >> 13;
149 h32 *= PRIME32_3;
150 h32 ^= h32 >> 16;
151
152 return h32;
153}
154EXPORT_SYMBOL(xxh32);
155
156static uint64_t xxh64_round(uint64_t acc, const uint64_t input)
157{
158 acc += input * PRIME64_2;
159 acc = xxh_rotl64(acc, 31);
160 acc *= PRIME64_1;
161 return acc;
162}
163
164static uint64_t xxh64_merge_round(uint64_t acc, uint64_t val)
165{
166 val = xxh64_round(0, val);
167 acc ^= val;
168 acc = acc * PRIME64_1 + PRIME64_4;
169 return acc;
170}
171
172uint64_t xxh64(const void *input, const size_t len, const uint64_t seed)
173{
174 const uint8_t *p = (const uint8_t *)input;
175 const uint8_t *const b_end = p + len;
176 uint64_t h64;
177
178 if (len >= 32) {
179 const uint8_t *const limit = b_end - 32;
180 uint64_t v1 = seed + PRIME64_1 + PRIME64_2;
181 uint64_t v2 = seed + PRIME64_2;
182 uint64_t v3 = seed + 0;
183 uint64_t v4 = seed - PRIME64_1;
184
185 do {
186 v1 = xxh64_round(v1, get_unaligned_le64(p));
187 p += 8;
188 v2 = xxh64_round(v2, get_unaligned_le64(p));
189 p += 8;
190 v3 = xxh64_round(v3, get_unaligned_le64(p));
191 p += 8;
192 v4 = xxh64_round(v4, get_unaligned_le64(p));
193 p += 8;
194 } while (p <= limit);
195
196 h64 = xxh_rotl64(v1, 1) + xxh_rotl64(v2, 7) +
197 xxh_rotl64(v3, 12) + xxh_rotl64(v4, 18);
198 h64 = xxh64_merge_round(h64, v1);
199 h64 = xxh64_merge_round(h64, v2);
200 h64 = xxh64_merge_round(h64, v3);
201 h64 = xxh64_merge_round(h64, v4);
202
203 } else {
204 h64 = seed + PRIME64_5;
205 }
206
207 h64 += (uint64_t)len;
208
209 while (p + 8 <= b_end) {
210 const uint64_t k1 = xxh64_round(0, get_unaligned_le64(p));
211
212 h64 ^= k1;
213 h64 = xxh_rotl64(h64, 27) * PRIME64_1 + PRIME64_4;
214 p += 8;
215 }
216
217 if (p + 4 <= b_end) {
218 h64 ^= (uint64_t)(get_unaligned_le32(p)) * PRIME64_1;
219 h64 = xxh_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
220 p += 4;
221 }
222
223 while (p < b_end) {
224 h64 ^= (*p) * PRIME64_5;
225 h64 = xxh_rotl64(h64, 11) * PRIME64_1;
226 p++;
227 }
228
229 h64 ^= h64 >> 33;
230 h64 *= PRIME64_2;
231 h64 ^= h64 >> 29;
232 h64 *= PRIME64_3;
233 h64 ^= h64 >> 32;
234
235 return h64;
236}
237EXPORT_SYMBOL(xxh64);
238
239/*-**************************************************
240 * Advanced Hash Functions
241 ***************************************************/
242void xxh32_reset(struct xxh32_state *statePtr, const uint32_t seed)
243{
244 /* use a local state for memcpy() to avoid strict-aliasing warnings */
245 struct xxh32_state state;
246
247 memset(&state, 0, sizeof(state));
248 state.v1 = seed + PRIME32_1 + PRIME32_2;
249 state.v2 = seed + PRIME32_2;
250 state.v3 = seed + 0;
251 state.v4 = seed - PRIME32_1;
252 memcpy(statePtr, &state, sizeof(state));
253}
254EXPORT_SYMBOL(xxh32_reset);
255
256void xxh64_reset(struct xxh64_state *statePtr, const uint64_t seed)
257{
258 /* use a local state for memcpy() to avoid strict-aliasing warnings */
259 struct xxh64_state state;
260
261 memset(&state, 0, sizeof(state));
262 state.v1 = seed + PRIME64_1 + PRIME64_2;
263 state.v2 = seed + PRIME64_2;
264 state.v3 = seed + 0;
265 state.v4 = seed - PRIME64_1;
266 memcpy(statePtr, &state, sizeof(state));
267}
268EXPORT_SYMBOL(xxh64_reset);
269
270int xxh32_update(struct xxh32_state *state, const void *input, const size_t len)
271{
272 const uint8_t *p = (const uint8_t *)input;
273 const uint8_t *const b_end = p + len;
274
275 if (input == NULL)
276 return -EINVAL;
277
278 state->total_len_32 += (uint32_t)len;
279 state->large_len |= (len >= 16) | (state->total_len_32 >= 16);
280
281 if (state->memsize + len < 16) { /* fill in tmp buffer */
282 memcpy((uint8_t *)(state->mem32) + state->memsize, input, len);
283 state->memsize += (uint32_t)len;
284 return 0;
285 }
286
287 if (state->memsize) { /* some data left from previous update */
288 const uint32_t *p32 = state->mem32;
289
290 memcpy((uint8_t *)(state->mem32) + state->memsize, input,
291 16 - state->memsize);
292
293 state->v1 = xxh32_round(state->v1, get_unaligned_le32(p32));
294 p32++;
295 state->v2 = xxh32_round(state->v2, get_unaligned_le32(p32));
296 p32++;
297 state->v3 = xxh32_round(state->v3, get_unaligned_le32(p32));
298 p32++;
299 state->v4 = xxh32_round(state->v4, get_unaligned_le32(p32));
300 p32++;
301
302 p += 16-state->memsize;
303 state->memsize = 0;
304 }
305
306 if (p <= b_end - 16) {
307 const uint8_t *const limit = b_end - 16;
308 uint32_t v1 = state->v1;
309 uint32_t v2 = state->v2;
310 uint32_t v3 = state->v3;
311 uint32_t v4 = state->v4;
312
313 do {
314 v1 = xxh32_round(v1, get_unaligned_le32(p));
315 p += 4;
316 v2 = xxh32_round(v2, get_unaligned_le32(p));
317 p += 4;
318 v3 = xxh32_round(v3, get_unaligned_le32(p));
319 p += 4;
320 v4 = xxh32_round(v4, get_unaligned_le32(p));
321 p += 4;
322 } while (p <= limit);
323
324 state->v1 = v1;
325 state->v2 = v2;
326 state->v3 = v3;
327 state->v4 = v4;
328 }
329
330 if (p < b_end) {
331 memcpy(state->mem32, p, (size_t)(b_end-p));
332 state->memsize = (uint32_t)(b_end-p);
333 }
334
335 return 0;
336}
337EXPORT_SYMBOL(xxh32_update);
338
339uint32_t xxh32_digest(const struct xxh32_state *state)
340{
341 const uint8_t *p = (const uint8_t *)state->mem32;
342 const uint8_t *const b_end = (const uint8_t *)(state->mem32) +
343 state->memsize;
344 uint32_t h32;
345
346 if (state->large_len) {
347 h32 = xxh_rotl32(state->v1, 1) + xxh_rotl32(state->v2, 7) +
348 xxh_rotl32(state->v3, 12) + xxh_rotl32(state->v4, 18);
349 } else {
350 h32 = state->v3 /* == seed */ + PRIME32_5;
351 }
352
353 h32 += state->total_len_32;
354
355 while (p + 4 <= b_end) {
356 h32 += get_unaligned_le32(p) * PRIME32_3;
357 h32 = xxh_rotl32(h32, 17) * PRIME32_4;
358 p += 4;
359 }
360
361 while (p < b_end) {
362 h32 += (*p) * PRIME32_5;
363 h32 = xxh_rotl32(h32, 11) * PRIME32_1;
364 p++;
365 }
366
367 h32 ^= h32 >> 15;
368 h32 *= PRIME32_2;
369 h32 ^= h32 >> 13;
370 h32 *= PRIME32_3;
371 h32 ^= h32 >> 16;
372
373 return h32;
374}
375EXPORT_SYMBOL(xxh32_digest);
376
377int xxh64_update(struct xxh64_state *state, const void *input, const size_t len)
378{
379 const uint8_t *p = (const uint8_t *)input;
380 const uint8_t *const b_end = p + len;
381
382 if (input == NULL)
383 return -EINVAL;
384
385 state->total_len += len;
386
387 if (state->memsize + len < 32) { /* fill in tmp buffer */
388 memcpy(((uint8_t *)state->mem64) + state->memsize, input, len);
389 state->memsize += (uint32_t)len;
390 return 0;
391 }
392
393 if (state->memsize) { /* tmp buffer is full */
394 uint64_t *p64 = state->mem64;
395
396 memcpy(((uint8_t *)p64) + state->memsize, input,
397 32 - state->memsize);
398
399 state->v1 = xxh64_round(state->v1, get_unaligned_le64(p64));
400 p64++;
401 state->v2 = xxh64_round(state->v2, get_unaligned_le64(p64));
402 p64++;
403 state->v3 = xxh64_round(state->v3, get_unaligned_le64(p64));
404 p64++;
405 state->v4 = xxh64_round(state->v4, get_unaligned_le64(p64));
406
407 p += 32 - state->memsize;
408 state->memsize = 0;
409 }
410
411 if (p + 32 <= b_end) {
412 const uint8_t *const limit = b_end - 32;
413 uint64_t v1 = state->v1;
414 uint64_t v2 = state->v2;
415 uint64_t v3 = state->v3;
416 uint64_t v4 = state->v4;
417
418 do {
419 v1 = xxh64_round(v1, get_unaligned_le64(p));
420 p += 8;
421 v2 = xxh64_round(v2, get_unaligned_le64(p));
422 p += 8;
423 v3 = xxh64_round(v3, get_unaligned_le64(p));
424 p += 8;
425 v4 = xxh64_round(v4, get_unaligned_le64(p));
426 p += 8;
427 } while (p <= limit);
428
429 state->v1 = v1;
430 state->v2 = v2;
431 state->v3 = v3;
432 state->v4 = v4;
433 }
434
435 if (p < b_end) {
436 memcpy(state->mem64, p, (size_t)(b_end-p));
437 state->memsize = (uint32_t)(b_end - p);
438 }
439
440 return 0;
441}
442EXPORT_SYMBOL(xxh64_update);
443
444uint64_t xxh64_digest(const struct xxh64_state *state)
445{
446 const uint8_t *p = (const uint8_t *)state->mem64;
447 const uint8_t *const b_end = (const uint8_t *)state->mem64 +
448 state->memsize;
449 uint64_t h64;
450
451 if (state->total_len >= 32) {
452 const uint64_t v1 = state->v1;
453 const uint64_t v2 = state->v2;
454 const uint64_t v3 = state->v3;
455 const uint64_t v4 = state->v4;
456
457 h64 = xxh_rotl64(v1, 1) + xxh_rotl64(v2, 7) +
458 xxh_rotl64(v3, 12) + xxh_rotl64(v4, 18);
459 h64 = xxh64_merge_round(h64, v1);
460 h64 = xxh64_merge_round(h64, v2);
461 h64 = xxh64_merge_round(h64, v3);
462 h64 = xxh64_merge_round(h64, v4);
463 } else {
464 h64 = state->v3 + PRIME64_5;
465 }
466
467 h64 += (uint64_t)state->total_len;
468
469 while (p + 8 <= b_end) {
470 const uint64_t k1 = xxh64_round(0, get_unaligned_le64(p));
471
472 h64 ^= k1;
473 h64 = xxh_rotl64(h64, 27) * PRIME64_1 + PRIME64_4;
474 p += 8;
475 }
476
477 if (p + 4 <= b_end) {
478 h64 ^= (uint64_t)(get_unaligned_le32(p)) * PRIME64_1;
479 h64 = xxh_rotl64(h64, 23) * PRIME64_2 + PRIME64_3;
480 p += 4;
481 }
482
483 while (p < b_end) {
484 h64 ^= (*p) * PRIME64_5;
485 h64 = xxh_rotl64(h64, 11) * PRIME64_1;
486 p++;
487 }
488
489 h64 ^= h64 >> 33;
490 h64 *= PRIME64_2;
491 h64 ^= h64 >> 29;
492 h64 *= PRIME64_3;
493 h64 ^= h64 >> 32;
494
495 return h64;
496}
497EXPORT_SYMBOL(xxh64_digest);
498
499MODULE_LICENSE("Dual BSD/GPL");
500MODULE_DESCRIPTION("xxHash");
generated by cgit v1.2.2 (git 2.25.0) at 2025-08-18 13:09:16 -0400