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: https://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 | */ |
95 | uint32_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 | */ |
108 | uint64_t xxh64(const void *input, size_t length, uint64_t seed); |
109 | |
110 | /** |
111 | * xxhash() - calculate wordsize hash of the input with a given seed |
112 | * @input: The data to hash. |
113 | * @length: The length of the data to hash. |
114 | * @seed: The seed can be used to alter the result predictably. |
115 | * |
116 | * If the hash does not need to be comparable between machines with |
117 | * different word sizes, this function will call whichever of xxh32() |
118 | * or xxh64() is faster. |
119 | * |
120 | * Return: wordsize hash of the data. |
121 | */ |
122 | |
123 | static inline unsigned long xxhash(const void *input, size_t length, |
124 | uint64_t seed) |
125 | { |
126 | #if BITS_PER_LONG == 64 |
127 | return xxh64(input, length, seed); |
128 | #else |
129 | return xxh32(input, length, seed); |
130 | #endif |
131 | } |
132 | |
133 | /*-**************************** |
134 | * Streaming Hash Functions |
135 | *****************************/ |
136 | |
137 | /* |
138 | * These definitions are only meant to allow allocation of XXH state |
139 | * statically, on stack, or in a struct for example. |
140 | * Do not use members directly. |
141 | */ |
142 | |
143 | /** |
144 | * struct xxh32_state - private xxh32 state, do not use members directly |
145 | */ |
146 | struct xxh32_state { |
147 | uint32_t total_len_32; |
148 | uint32_t large_len; |
149 | uint32_t v1; |
150 | uint32_t v2; |
151 | uint32_t v3; |
152 | uint32_t v4; |
153 | uint32_t mem32[4]; |
154 | uint32_t memsize; |
155 | }; |
156 | |
157 | /** |
158 | * struct xxh32_state - private xxh64 state, do not use members directly |
159 | */ |
160 | struct xxh64_state { |
161 | uint64_t total_len; |
162 | uint64_t v1; |
163 | uint64_t v2; |
164 | uint64_t v3; |
165 | uint64_t v4; |
166 | uint64_t mem64[4]; |
167 | uint32_t memsize; |
168 | }; |
169 | |
170 | /** |
171 | * xxh32_reset() - reset the xxh32 state to start a new hashing operation |
172 | * |
173 | * @state: The xxh32 state to reset. |
174 | * @seed: Initialize the hash state with this seed. |
175 | * |
176 | * Call this function on any xxh32_state to prepare for a new hashing operation. |
177 | */ |
178 | void xxh32_reset(struct xxh32_state *state, uint32_t seed); |
179 | |
180 | /** |
181 | * xxh32_update() - hash the data given and update the xxh32 state |
182 | * |
183 | * @state: The xxh32 state to update. |
184 | * @input: The data to hash. |
185 | * @length: The length of the data to hash. |
186 | * |
187 | * After calling xxh32_reset() call xxh32_update() as many times as necessary. |
188 | * |
189 | * Return: Zero on success, otherwise an error code. |
190 | */ |
191 | int xxh32_update(struct xxh32_state *state, const void *input, size_t length); |
192 | |
193 | /** |
194 | * xxh32_digest() - produce the current xxh32 hash |
195 | * |
196 | * @state: Produce the current xxh32 hash of this state. |
197 | * |
198 | * A hash value can be produced at any time. It is still possible to continue |
199 | * inserting input into the hash state after a call to xxh32_digest(), and |
200 | * generate new hashes later on, by calling xxh32_digest() again. |
201 | * |
202 | * Return: The xxh32 hash stored in the state. |
203 | */ |
204 | uint32_t xxh32_digest(const struct xxh32_state *state); |
205 | |
206 | /** |
207 | * xxh64_reset() - reset the xxh64 state to start a new hashing operation |
208 | * |
209 | * @state: The xxh64 state to reset. |
210 | * @seed: Initialize the hash state with this seed. |
211 | */ |
212 | void xxh64_reset(struct xxh64_state *state, uint64_t seed); |
213 | |
214 | /** |
215 | * xxh64_update() - hash the data given and update the xxh64 state |
216 | * @state: The xxh64 state to update. |
217 | * @input: The data to hash. |
218 | * @length: The length of the data to hash. |
219 | * |
220 | * After calling xxh64_reset() call xxh64_update() as many times as necessary. |
221 | * |
222 | * Return: Zero on success, otherwise an error code. |
223 | */ |
224 | int xxh64_update(struct xxh64_state *state, const void *input, size_t length); |
225 | |
226 | /** |
227 | * xxh64_digest() - produce the current xxh64 hash |
228 | * |
229 | * @state: Produce the current xxh64 hash of this state. |
230 | * |
231 | * A hash value can be produced at any time. It is still possible to continue |
232 | * inserting input into the hash state after a call to xxh64_digest(), and |
233 | * generate new hashes later on, by calling xxh64_digest() again. |
234 | * |
235 | * Return: The xxh64 hash stored in the state. |
236 | */ |
237 | uint64_t xxh64_digest(const struct xxh64_state *state); |
238 | |
239 | /*-************************** |
240 | * Utils |
241 | ***************************/ |
242 | |
243 | /** |
244 | * xxh32_copy_state() - copy the source state into the destination state |
245 | * |
246 | * @src: The source xxh32 state. |
247 | * @dst: The destination xxh32 state. |
248 | */ |
249 | void xxh32_copy_state(struct xxh32_state *dst, const struct xxh32_state *src); |
250 | |
251 | /** |
252 | * xxh64_copy_state() - copy the source state into the destination state |
253 | * |
254 | * @src: The source xxh64 state. |
255 | * @dst: The destination xxh64 state. |
256 | */ |
257 | void xxh64_copy_state(struct xxh64_state *dst, const struct xxh64_state *src); |
258 | |
259 | #endif /* XXHASH_H */ |
260 | |