1//! This crate provides foldhash, a fast, non-cryptographic, minimally
2//! DoS-resistant hashing algorithm designed for computational uses such as
3//! hashmaps, bloom filters, count sketching, etc.
4//!
5//! When should you **not** use foldhash:
6//!
7//! - You are afraid of people studying your long-running program's behavior
8//! to reverse engineer its internal random state and using this knowledge to
9//! create many colliding inputs for computational complexity attacks.
10//!
11//! - You expect foldhash to have a consistent output across versions or
12//! platforms, such as for persistent file formats or communication protocols.
13//!
14//! - You are relying on foldhash's properties for any kind of security.
15//! Foldhash is **not appropriate for any cryptographic purpose**.
16//!
17//! Foldhash has two variants, one optimized for speed which is ideal for data
18//! structures such as hash maps and bloom filters, and one optimized for
19//! statistical quality which is ideal for algorithms such as
20//! [HyperLogLog](https://en.wikipedia.org/wiki/HyperLogLog) and
21//! [MinHash](https://en.wikipedia.org/wiki/MinHash).
22//!
23//! Foldhash can be used in a `#![no_std]` environment by disabling its default
24//! `"std"` feature.
25//!
26//! # Usage
27//!
28//! The easiest way to use this crate with the standard library [`HashMap`] or
29//! [`HashSet`] is to import them from `foldhash` instead, along with the
30//! extension traits to make [`HashMap::new`] and [`HashMap::with_capacity`]
31//! work out-of-the-box:
32//!
33//! ```rust
34//! use foldhash::{HashMap, HashMapExt};
35//!
36//! let mut hm = HashMap::new();
37//! hm.insert(42, "hello");
38//! ```
39//!
40//! You can also avoid the convenience types and do it manually by initializing
41//! a [`RandomState`](fast::RandomState), for example if you are using a different hash map
42//! implementation like [`hashbrown`](https://docs.rs/hashbrown/):
43//!
44//! ```rust
45//! use hashbrown::HashMap;
46//! use foldhash::fast::RandomState;
47//!
48//! let mut hm = HashMap::with_hasher(RandomState::default());
49//! hm.insert("foo", "bar");
50//! ```
51//!
52//! The above methods are the recommended way to use foldhash, which will
53//! automatically generate a randomly generated hasher instance for you. If you
54//! absolutely must have determinism you can use [`FixedState`](fast::FixedState)
55//! instead, but note that this makes you trivially vulnerable to HashDoS
56//! attacks and might lead to quadratic runtime when moving data from one
57//! hashmap/set into another:
58//!
59//! ```rust
60//! use std::collections::HashSet;
61//! use foldhash::fast::FixedState;
62//!
63//! let mut hm = HashSet::with_hasher(FixedState::with_seed(42));
64//! hm.insert([1, 10, 100]);
65//! ```
66//!
67//! If you rely on statistical properties of the hash for the correctness of
68//! your algorithm, such as in [HyperLogLog](https://en.wikipedia.org/wiki/HyperLogLog),
69//! it is suggested to use the [`RandomState`](quality::RandomState)
70//! or [`FixedState`](quality::FixedState) from the [`quality`] module instead
71//! of the [`fast`] module. The latter is optimized purely for speed in hash
72//! tables and has known statistical imperfections.
73//!
74//! Finally, you can also directly use the [`RandomState`](quality::RandomState)
75//! or [`FixedState`](quality::FixedState) to manually hash items using the
76//! [`BuildHasher`](std::hash::BuildHasher) trait:
77//! ```rust
78//! use std::hash::BuildHasher;
79//! use foldhash::quality::RandomState;
80//!
81//! let random_state = RandomState::default();
82//! let hash = random_state.hash_one("hello world");
83//! ```
84//!
85//! ## Seeding
86//!
87//! Foldhash relies on a single 8-byte per-hasher seed which should be ideally
88//! be different from each instance to instance, and also a larger
89//! [`SharedSeed`] which may be shared by many different instances.
90//!
91//! To reduce overhead, this [`SharedSeed`] is typically initialized once and
92//! stored. To prevent each hashmap unnecessarily containing a reference to this
93//! value there are three kinds of [`BuildHasher`](core::hash::BuildHasher)s
94//! foldhash provides (both for [`fast`] and [`quality`]):
95//!
96//! 1. [`RandomState`](fast::RandomState), which always generates a
97//! random per-hasher seed and implicitly stores a reference to [`SharedSeed::global_random`].
98//! 2. [`FixedState`](fast::FixedState), which by default uses a fixed
99//! per-hasher seed and implicitly stores a reference to [`SharedSeed::global_fixed`].
100//! 3. [`SeedableRandomState`](fast::SeedableRandomState), which works like
101//! [`RandomState`](fast::RandomState) by default but can be seeded in any manner.
102//! This state must include an explicit reference to a [`SharedSeed`], and thus
103//! this struct is 16 bytes as opposed to just 8 bytes for the previous two.
104//!
105//! ## Features
106//!
107//! This crate has the following features:
108//! - `nightly`, this feature improves string hashing performance
109//! slightly using the nightly-only Rust feature
110//! [`hasher_prefixfree_extras`](https://github.com/rust-lang/rust/issues/96762),
111//! - `std`, this enabled-by-default feature offers convenient aliases for `std`
112//! containers, but can be turned off for `#![no_std]` crates.
113
114#![cfg_attr(all(not(test), not(feature = "std")), no_std)]
115#![cfg_attr(feature = "nightly", feature(hasher_prefixfree_extras))]
116#![warn(missing_docs)]
117
118pub mod fast;
119pub mod quality;
120mod seed;
121pub use seed::SharedSeed;
122
123#[cfg(feature = "std")]
124mod convenience;
125#[cfg(feature = "std")]
126pub use convenience::*;
127
128// Arbitrary constants with high entropy. Hexadecimal digits of pi were used.
129const ARBITRARY0: u64 = 0x243f6a8885a308d3;
130const ARBITRARY1: u64 = 0x13198a2e03707344;
131const ARBITRARY2: u64 = 0xa4093822299f31d0;
132const ARBITRARY3: u64 = 0x082efa98ec4e6c89;
133const ARBITRARY4: u64 = 0x452821e638d01377;
134const ARBITRARY5: u64 = 0xbe5466cf34e90c6c;
135const ARBITRARY6: u64 = 0xc0ac29b7c97c50dd;
136const ARBITRARY7: u64 = 0x3f84d5b5b5470917;
137const ARBITRARY8: u64 = 0x9216d5d98979fb1b;
138const ARBITRARY9: u64 = 0xd1310ba698dfb5ac;
139const ARBITRARY10: u64 = 0x2ffd72dbd01adfb7;
140const ARBITRARY11: u64 = 0xb8e1afed6a267e96;
141
142#[inline(always)]
143const fn folded_multiply(x: u64, y: u64) -> u64 {
144 // The following code path is only fast if 64-bit to 128-bit widening
145 // multiplication is supported by the architecture. Most 64-bit
146 // architectures except SPARC64 and Wasm64 support it. However, the target
147 // pointer width doesn't always indicate that we are dealing with a 64-bit
148 // architecture, as there are ABIs that reduce the pointer width, especially
149 // on AArch64 and x86-64. WebAssembly (regardless of pointer width) supports
150 // 64-bit to 128-bit widening multiplication with the `wide-arithmetic`
151 // proposal.
152 #[cfg(any(
153 all(
154 target_pointer_width = "64",
155 not(any(target_arch = "sparc64", target_arch = "wasm64")),
156 ),
157 target_arch = "aarch64",
158 target_arch = "x86_64",
159 all(target_family = "wasm", target_feature = "wide-arithmetic"),
160 ))]
161 {
162 // We compute the full u64 x u64 -> u128 product, this is a single mul
163 // instruction on x86-64, one mul plus one mulhi on ARM64.
164 let full = (x as u128).wrapping_mul(y as u128);
165 let lo = full as u64;
166 let hi = (full >> 64) as u64;
167
168 // The middle bits of the full product fluctuate the most with small
169 // changes in the input. This is the top bits of lo and the bottom bits
170 // of hi. We can thus make the entire output fluctuate with small
171 // changes to the input by XOR'ing these two halves.
172 lo ^ hi
173 }
174
175 #[cfg(not(any(
176 all(
177 target_pointer_width = "64",
178 not(any(target_arch = "sparc64", target_arch = "wasm64")),
179 ),
180 target_arch = "aarch64",
181 target_arch = "x86_64",
182 all(target_family = "wasm", target_feature = "wide-arithmetic"),
183 )))]
184 {
185 // u64 x u64 -> u128 product is quite expensive on 32-bit.
186 // We approximate it by expanding the multiplication and eliminating
187 // carries by replacing additions with XORs:
188 // (2^32 hx + lx)*(2^32 hy + ly) =
189 // 2^64 hx*hy + 2^32 (hx*ly + lx*hy) + lx*ly ~=
190 // 2^64 hx*hy ^ 2^32 (hx*ly ^ lx*hy) ^ lx*ly
191 // Which when folded becomes:
192 // (hx*hy ^ lx*ly) ^ (hx*ly ^ lx*hy).rotate_right(32)
193
194 let lx = x as u32;
195 let ly = y as u32;
196 let hx = (x >> 32) as u32;
197 let hy = (y >> 32) as u32;
198
199 let ll = (lx as u64).wrapping_mul(ly as u64);
200 let lh = (lx as u64).wrapping_mul(hy as u64);
201 let hl = (hx as u64).wrapping_mul(ly as u64);
202 let hh = (hx as u64).wrapping_mul(hy as u64);
203
204 (hh ^ ll) ^ (hl ^ lh).rotate_right(32)
205 }
206}
207
208#[inline(always)]
209const fn rotate_right(x: u64, r: u32) -> u64 {
210 #[cfg(any(
211 target_pointer_width = "64",
212 target_arch = "aarch64",
213 target_arch = "x86_64",
214 target_family = "wasm",
215 ))]
216 {
217 x.rotate_right(r)
218 }
219
220 #[cfg(not(any(
221 target_pointer_width = "64",
222 target_arch = "aarch64",
223 target_arch = "x86_64",
224 target_family = "wasm",
225 )))]
226 {
227 // On platforms without 64-bit arithmetic rotation can be slow, rotate
228 // each 32-bit half independently.
229 let lo = (x as u32).rotate_right(r);
230 let hi = ((x >> 32) as u32).rotate_right(r);
231 ((hi as u64) << 32) | lo as u64
232 }
233}
234
235#[cold]
236fn cold_path() {}
237
238/// Hashes strings <= 16 bytes, has unspecified behavior when bytes.len() > 16.
239#[inline(always)]
240fn hash_bytes_short(bytes: &[u8], accumulator: u64, seeds: &[u64; 6]) -> u64 {
241 let len = bytes.len();
242 let mut s0: u64 = accumulator;
243 let mut s1: u64 = seeds[1];
244 // XOR the input into s0, s1, then multiply and fold.
245 if len >= 8 {
246 s0 ^= u64::from_ne_bytes(bytes[0..8].try_into().unwrap());
247 s1 ^= u64::from_ne_bytes(bytes[len - 8..].try_into().unwrap());
248 } else if len >= 4 {
249 s0 ^= u32::from_ne_bytes(bytes[0..4].try_into().unwrap()) as u64;
250 s1 ^= u32::from_ne_bytes(bytes[len - 4..].try_into().unwrap()) as u64;
251 } else if len > 0 {
252 let lo: u64 = bytes[0];
253 let mid: u64 = bytes[len / 2];
254 let hi: u64 = bytes[len - 1];
255 s0 ^= lo as u64;
256 s1 ^= ((hi as u64) << 8) | mid as u64;
257 }
258 folded_multiply(x:s0, y:s1)
259}
260
261/// Load 8 bytes into a u64 word at the given offset.
262///
263/// # Safety
264/// You must ensure that offset + 8 <= bytes.len().
265#[inline(always)]
266unsafe fn load(bytes: &[u8], offset: usize) -> u64 {
267 // In most (but not all) cases this unsafe code is not necessary to avoid
268 // the bounds checks in the below code, but the register allocation became
269 // worse if I replaced those calls which could be replaced with safe code.
270 unsafe { bytes.as_ptr().add(offset).cast::<u64>().read_unaligned() }
271}
272
273/// Hashes strings > 16 bytes.
274///
275/// # Safety
276/// v.len() must be > 16 bytes.
277#[cold]
278#[inline(never)]
279unsafe fn hash_bytes_long(mut v: &[u8], accumulator: u64, seeds: &[u64; 6]) -> u64 {
280 let mut s0 = accumulator;
281 let mut s1 = s0.wrapping_add(seeds[1]);
282
283 if v.len() > 128 {
284 cold_path();
285 let mut s2 = s0.wrapping_add(seeds[2]);
286 let mut s3 = s0.wrapping_add(seeds[3]);
287
288 if v.len() > 256 {
289 cold_path();
290 let mut s4 = s0.wrapping_add(seeds[4]);
291 let mut s5 = s0.wrapping_add(seeds[5]);
292 loop {
293 unsafe {
294 // SAFETY: we checked the length is > 256, we index at most v[..96].
295 s0 = folded_multiply(load(v, 0) ^ s0, load(v, 48) ^ seeds[0]);
296 s1 = folded_multiply(load(v, 8) ^ s1, load(v, 56) ^ seeds[0]);
297 s2 = folded_multiply(load(v, 16) ^ s2, load(v, 64) ^ seeds[0]);
298 s3 = folded_multiply(load(v, 24) ^ s3, load(v, 72) ^ seeds[0]);
299 s4 = folded_multiply(load(v, 32) ^ s4, load(v, 80) ^ seeds[0]);
300 s5 = folded_multiply(load(v, 40) ^ s5, load(v, 88) ^ seeds[0]);
301 }
302 v = &v[96..];
303 if v.len() <= 256 {
304 break;
305 }
306 }
307 s0 ^= s4;
308 s1 ^= s5;
309 }
310
311 loop {
312 unsafe {
313 // SAFETY: we checked the length is > 128, we index at most v[..64].
314 s0 = folded_multiply(load(v, 0) ^ s0, load(v, 32) ^ seeds[0]);
315 s1 = folded_multiply(load(v, 8) ^ s1, load(v, 40) ^ seeds[0]);
316 s2 = folded_multiply(load(v, 16) ^ s2, load(v, 48) ^ seeds[0]);
317 s3 = folded_multiply(load(v, 24) ^ s3, load(v, 56) ^ seeds[0]);
318 }
319 v = &v[64..];
320 if v.len() <= 128 {
321 break;
322 }
323 }
324 s0 ^= s2;
325 s1 ^= s3;
326 }
327
328 let len = v.len();
329 unsafe {
330 // SAFETY: our precondition ensures our length is at least 16, and the
331 // above loops do not reduce the length under that. This protects our
332 // first iteration of this loop, the further iterations are protected
333 // directly by the checks on len.
334 s0 = folded_multiply(load(v, 0) ^ s0, load(v, len - 16) ^ seeds[0]);
335 s1 = folded_multiply(load(v, 8) ^ s1, load(v, len - 8) ^ seeds[0]);
336 if len >= 32 {
337 s0 = folded_multiply(load(v, 16) ^ s0, load(v, len - 32) ^ seeds[0]);
338 s1 = folded_multiply(load(v, 24) ^ s1, load(v, len - 24) ^ seeds[0]);
339 if len >= 64 {
340 s0 = folded_multiply(load(v, 32) ^ s0, load(v, len - 48) ^ seeds[0]);
341 s1 = folded_multiply(load(v, 40) ^ s1, load(v, len - 40) ^ seeds[0]);
342 if len >= 96 {
343 s0 = folded_multiply(load(v, 48) ^ s0, load(v, len - 64) ^ seeds[0]);
344 s1 = folded_multiply(load(v, 56) ^ s1, load(v, len - 56) ^ seeds[0]);
345 }
346 }
347 }
348 }
349 s0 ^ s1
350}
351