/rust/registry/src/index.crates.io-1949cf8c6b5b557f/foldhash-0.1.5/src/fast.rs

Source
//! The foldhash implementation optimized for speed.

use core::hash::{BuildHasher, Hasher};

use crate::seed::{gen_per_hasher_seed, GlobalSeed, SharedSeed};
use crate::{folded_multiply, hash_bytes_long, hash_bytes_medium, rotate_right, ARBITRARY3};

/// A [`Hasher`] instance implementing foldhash, optimized for speed.
///
/// While you can create one directly with [`FoldHasher::with_seed`], you
/// most likely want to use [`RandomState`], [`SeedableRandomState`] or
/// [`FixedState`] to create [`FoldHasher`]s.
#[derive(Clone)]
pub struct FoldHasher {
    accumulator: u64,
    sponge: u128,
    sponge_len: u8,
    fold_seed: u64,
    expand_seed: u64,
    expand_seed2: u64,
    expand_seed3: u64,
}

impl FoldHasher {
    /// Initializes this [`FoldHasher`] with the given per-hasher seed and
    /// [`SharedSeed`].
    #[inline]
    pub fn with_seed(per_hasher_seed: u64, shared_seed: &SharedSeed) -> FoldHasher {
        FoldHasher {
            accumulator: per_hasher_seed,
            sponge: 0,
            sponge_len: 0,
            fold_seed: shared_seed.seeds[0],
            expand_seed: shared_seed.seeds[1],
            expand_seed2: shared_seed.seeds[2],
            expand_seed3: shared_seed.seeds[3],
        }
    }

    #[inline(always)]
    fn write_num<T: Into<u128>>(&mut self, x: T) {
        let bits: usize = 8 * core::mem::size_of::<T>();
        if self.sponge_len as usize + bits > 128 {
            let lo = self.sponge as u64;
            let hi = (self.sponge >> 64) as u64;
            self.accumulator = folded_multiply(lo ^ self.accumulator, hi ^ self.fold_seed);
            self.sponge = x.into();
            self.sponge_len = bits as u8;
        } else {
            self.sponge |= x.into() << self.sponge_len;
            self.sponge_len += bits as u8;
        }
    }
}

impl Hasher for FoldHasher {
    #[inline(always)]
    fn write(&mut self, bytes: &[u8]) {
        // We perform overlapping reads in the byte hash which could lead to
        // trivial length-extension attacks. These should be defeated by
        // adding a length-dependent rotation on our unpredictable seed
        // which costs only a single cycle (or none if executed with
        // instruction-level parallelism).
        let len = bytes.len();
        let base_seed = rotate_right(self.accumulator, len as u32);
        if len <= 16 {
            let mut s0 = base_seed;
            let mut s1 = self.expand_seed;
            // XOR the input into s0, s1, then multiply and fold.
            if len >= 8 {
                s0 ^= u64::from_ne_bytes(bytes[0..8].try_into().unwrap());
                s1 ^= u64::from_ne_bytes(bytes[len - 8..].try_into().unwrap());
            } else if len >= 4 {
                s0 ^= u32::from_ne_bytes(bytes[0..4].try_into().unwrap()) as u64;
                s1 ^= u32::from_ne_bytes(bytes[len - 4..].try_into().unwrap()) as u64;
            } else if len > 0 {
                let lo = bytes[0];
                let mid = bytes[len / 2];
                let hi = bytes[len - 1];
                s0 ^= lo as u64;
                s1 ^= ((hi as u64) << 8) | mid as u64;
            }
            self.accumulator = folded_multiply(s0, s1);
        } else if len < 256 {
            self.accumulator = hash_bytes_medium(
                bytes,
                base_seed,
                base_seed.wrapping_add(self.expand_seed),
                self.fold_seed,
            );
        } else {
            self.accumulator = hash_bytes_long(
                bytes,
                base_seed,
                base_seed.wrapping_add(self.expand_seed),
                base_seed.wrapping_add(self.expand_seed2),
                base_seed.wrapping_add(self.expand_seed3),
                self.fold_seed,
            );
        }
    }

    #[inline(always)]
    fn write_u8(&mut self, i: u8) {
        self.write_num(i);
    }

    #[inline(always)]
    fn write_u16(&mut self, i: u16) {
        self.write_num(i);
    }

    #[inline(always)]
    fn write_u32(&mut self, i: u32) {
        self.write_num(i);
    }

    #[inline(always)]
    fn write_u64(&mut self, i: u64) {
        self.write_num(i);
    }

    #[inline(always)]
    fn write_u128(&mut self, i: u128) {
        let lo = i as u64;
        let hi = (i >> 64) as u64;
        self.accumulator = folded_multiply(lo ^ self.accumulator, hi ^ self.fold_seed);
    }

    #[inline(always)]
    fn write_usize(&mut self, i: usize) {
        // u128 doesn't implement From<usize>.
        #[cfg(target_pointer_width = "32")]
        self.write_num(i as u32);
        #[cfg(target_pointer_width = "64")]
        self.write_num(i as u64);
    }

    #[inline(always)]
    fn finish(&self) -> u64 {
        if self.sponge_len > 0 {
            let lo = self.sponge as u64;
            let hi = (self.sponge >> 64) as u64;
            folded_multiply(lo ^ self.accumulator, hi ^ self.fold_seed)
        } else {
            self.accumulator
        }
    }
}

/// A [`BuildHasher`] for [`fast::FoldHasher`](FoldHasher) that is randomly initialized.
#[derive(Copy, Clone, Debug)]
pub struct RandomState {
    per_hasher_seed: u64,
    global_seed: GlobalSeed,
}

impl Default for RandomState {
    #[inline(always)]
    fn default() -> Self {
        Self {
            per_hasher_seed: gen_per_hasher_seed(),
            global_seed: GlobalSeed::new(),
        }
    }
}

impl BuildHasher for RandomState {
    type Hasher = FoldHasher;

    #[inline(always)]
    fn build_hasher(&self) -> FoldHasher {
        FoldHasher::with_seed(self.per_hasher_seed, self.global_seed.get())
    }
}

/// A [`BuildHasher`] for [`fast::FoldHasher`](FoldHasher) that is randomly
/// initialized by default, but can also be initialized with a specific seed.
///
/// This can be useful for e.g. testing, but the downside is that this type
/// has a size of 16 bytes rather than the 8 bytes [`RandomState`] is.
#[derive(Copy, Clone, Debug)]
pub struct SeedableRandomState {
    per_hasher_seed: u64,
    shared_seed: &'static SharedSeed,
}

impl Default for SeedableRandomState {
    #[inline(always)]
    fn default() -> Self {
        Self::random()
    }
}

impl SeedableRandomState {
    /// Generates a random [`SeedableRandomState`], similar to [`RandomState`].
    #[inline(always)]
    pub fn random() -> Self {
        Self {
            per_hasher_seed: gen_per_hasher_seed(),
            shared_seed: SharedSeed::global_random(),
        }
    }

    /// Generates a fixed [`SeedableRandomState`], similar to [`FixedState`].
    #[inline(always)]
    pub fn fixed() -> Self {
        Self {
            per_hasher_seed: ARBITRARY3,
            shared_seed: SharedSeed::global_fixed(),
        }
    }

    /// Generates a [`SeedableRandomState`] with the given per-hasher seed
    /// and [`SharedSeed`].
    #[inline(always)]
    pub fn with_seed(per_hasher_seed: u64, shared_seed: &'static SharedSeed) -> Self {
        // XOR with ARBITRARY3 such that with_seed(0) matches default.
        Self {
            per_hasher_seed: per_hasher_seed ^ ARBITRARY3,
            shared_seed,
        }
    }
}

impl BuildHasher for SeedableRandomState {
    type Hasher = FoldHasher;

    #[inline(always)]
    fn build_hasher(&self) -> FoldHasher {
        FoldHasher::with_seed(self.per_hasher_seed, self.shared_seed)
    }
}

/// A [`BuildHasher`] for [`fast::FoldHasher`](FoldHasher) that always has the same fixed seed.
///
/// Not recommended unless you absolutely need determinism.
#[derive(Copy, Clone, Debug)]
pub struct FixedState {
    per_hasher_seed: u64,
}

impl FixedState {
    /// Creates a [`FixedState`] with the given per-hasher-seed.
    #[inline(always)]
    pub const fn with_seed(per_hasher_seed: u64) -> Self {
        // XOR with ARBITRARY3 such that with_seed(0) matches default.
        Self {
            per_hasher_seed: per_hasher_seed ^ ARBITRARY3,
        }
    }
}

impl Default for FixedState {
    #[inline(always)]
    fn default() -> Self {
        Self {
            per_hasher_seed: ARBITRARY3,
        }
    }
}

impl BuildHasher for FixedState {
    type Hasher = FoldHasher;

    #[inline(always)]
    fn build_hasher(&self) -> FoldHasher {
        FoldHasher::with_seed(self.per_hasher_seed, SharedSeed::global_fixed())
    }
}

Coverage Report

Created: 2025-12-11 06:38

Line	Count	Source
1		//! The foldhash implementation optimized for speed.
2
3		use core::hash::{BuildHasher, Hasher};
4
5		use crate::seed::{gen_per_hasher_seed, GlobalSeed, SharedSeed};
6		use crate::{folded_multiply, hash_bytes_long, hash_bytes_medium, rotate_right, ARBITRARY3};
7
8		/// A [`Hasher`] instance implementing foldhash, optimized for speed.
9		///
10		/// While you can create one directly with [`FoldHasher::with_seed`], you
11		/// most likely want to use [`RandomState`], [`SeedableRandomState`] or
12		/// [`FixedState`] to create [`FoldHasher`]s.
13		#[derive(Clone)]
14		pub struct FoldHasher {
15		accumulator: u64,
16		sponge: u128,
17		sponge_len: u8,
18		fold_seed: u64,
19		expand_seed: u64,
20		expand_seed2: u64,
21		expand_seed3: u64,
22		}
23
24		impl FoldHasher {
25		/// Initializes this [`FoldHasher`] with the given per-hasher seed and
26		/// [`SharedSeed`].
27		#[inline]
28	0	pub fn with_seed(per_hasher_seed: u64, shared_seed: &SharedSeed) -> FoldHasher {
29	0	FoldHasher {
30	0	accumulator: per_hasher_seed,
31	0	sponge: 0,
32	0	sponge_len: 0,
33	0	fold_seed: shared_seed.seeds[0],
34	0	expand_seed: shared_seed.seeds[1],
35	0	expand_seed2: shared_seed.seeds[2],
36	0	expand_seed3: shared_seed.seeds[3],
37	0	}
38	0	} Unexecuted instantiation: <foldhash::fast::FoldHasher>::with_seed Unexecuted instantiation: <foldhash::fast::FoldHasher>::with_seed
39
40		#[inline(always)]
41	0	fn write_num<T: Into<u128>>(&mut self, x: T) {
42	0	let bits: usize = 8 * core::mem::size_of::<T>();
43	0	if self.sponge_len as usize + bits > 128 {
44	0	let lo = self.sponge as u64;
45	0	let hi = (self.sponge >> 64) as u64;
46	0	self.accumulator = folded_multiply(lo ^ self.accumulator, hi ^ self.fold_seed);
47	0	self.sponge = x.into();
48	0	self.sponge_len = bits as u8;
49	0	} else {
50	0	self.sponge \|= x.into() << self.sponge_len;
51	0	self.sponge_len += bits as u8;
52	0	}
53	0	} Unexecuted instantiation: <foldhash::fast::FoldHasher>::write_num::<u32> Unexecuted instantiation: <foldhash::fast::FoldHasher>::write_num::<_>
54		}
55
56		impl Hasher for FoldHasher {
57		#[inline(always)]
58	0	fn write(&mut self, bytes: &[u8]) {
59		// We perform overlapping reads in the byte hash which could lead to
60		// trivial length-extension attacks. These should be defeated by
61		// adding a length-dependent rotation on our unpredictable seed
62		// which costs only a single cycle (or none if executed with
63		// instruction-level parallelism).
64	0	let len = bytes.len();
65	0	let base_seed = rotate_right(self.accumulator, len as u32);
66	0	if len <= 16 {
67	0	let mut s0 = base_seed;
68	0	let mut s1 = self.expand_seed;
69		// XOR the input into s0, s1, then multiply and fold.
70	0	if len >= 8 {
71	0	s0 ^= u64::from_ne_bytes(bytes[0..8].try_into().unwrap());
72	0	s1 ^= u64::from_ne_bytes(bytes[len - 8..].try_into().unwrap());
73	0	} else if len >= 4 {
74	0	s0 ^= u32::from_ne_bytes(bytes[0..4].try_into().unwrap()) as u64;
75	0	s1 ^= u32::from_ne_bytes(bytes[len - 4..].try_into().unwrap()) as u64;
76	0	} else if len > 0 {
77	0	let lo = bytes[0];
78	0	let mid = bytes[len / 2];
79	0	let hi = bytes[len - 1];
80	0	s0 ^= lo as u64;
81	0	s1 ^= ((hi as u64) << 8) \| mid as u64;
82	0	}
83	0	self.accumulator = folded_multiply(s0, s1);
84	0	} else if len < 256 {
85	0	self.accumulator = hash_bytes_medium(
86	0	bytes,
87	0	base_seed,
88	0	base_seed.wrapping_add(self.expand_seed),
89	0	self.fold_seed,
90	0	);
91	0	} else {
92	0	self.accumulator = hash_bytes_long(
93	0	bytes,
94	0	base_seed,
95	0	base_seed.wrapping_add(self.expand_seed),
96	0	base_seed.wrapping_add(self.expand_seed2),
97	0	base_seed.wrapping_add(self.expand_seed3),
98	0	self.fold_seed,
99	0	);
100	0	}
101	0	}
102
103		#[inline(always)]
104	0	fn write_u8(&mut self, i: u8) {
105	0	self.write_num(i);
106	0	}
107
108		#[inline(always)]
109	0	fn write_u16(&mut self, i: u16) {
110	0	self.write_num(i);
111	0	}
112
113		#[inline(always)]
114	0	fn write_u32(&mut self, i: u32) {
115	0	self.write_num(i);
116	0	}
117
118		#[inline(always)]
119	0	fn write_u64(&mut self, i: u64) {
120	0	self.write_num(i);
121	0	}
122
123		#[inline(always)]
124	0	fn write_u128(&mut self, i: u128) {
125	0	let lo = i as u64;
126	0	let hi = (i >> 64) as u64;
127	0	self.accumulator = folded_multiply(lo ^ self.accumulator, hi ^ self.fold_seed);
128	0	}
129
130		#[inline(always)]
131	0	fn write_usize(&mut self, i: usize) {
132		// u128 doesn't implement From<usize>.
133		#[cfg(target_pointer_width = "32")]
134		self.write_num(i as u32);
135		#[cfg(target_pointer_width = "64")]
136	0	self.write_num(i as u64);
137	0	}
138
139		#[inline(always)]
140	0	fn finish(&self) -> u64 {
141	0	if self.sponge_len > 0 {
142	0	let lo = self.sponge as u64;
143	0	let hi = (self.sponge >> 64) as u64;
144	0	folded_multiply(lo ^ self.accumulator, hi ^ self.fold_seed)
145		} else {
146	0	self.accumulator
147		}
148	0	}
149		}
150
151		/// A [`BuildHasher`] for [`fast::FoldHasher`](FoldHasher) that is randomly initialized.
152		#[derive(Copy, Clone, Debug)]
153		pub struct RandomState {
154		per_hasher_seed: u64,
155		global_seed: GlobalSeed,
156		}
157
158		impl Default for RandomState {
159		#[inline(always)]
160	0	fn default() -> Self {
161	0	Self {
162	0	per_hasher_seed: gen_per_hasher_seed(),
163	0	global_seed: GlobalSeed::new(),
164	0	}
165	0	}
166		}
167
168		impl BuildHasher for RandomState {
169		type Hasher = FoldHasher;
170
171		#[inline(always)]
172	0	fn build_hasher(&self) -> FoldHasher {
173	0	FoldHasher::with_seed(self.per_hasher_seed, self.global_seed.get())
174	0	}
175		}
176
177		/// A [`BuildHasher`] for [`fast::FoldHasher`](FoldHasher) that is randomly
178		/// initialized by default, but can also be initialized with a specific seed.
179		///
180		/// This can be useful for e.g. testing, but the downside is that this type
181		/// has a size of 16 bytes rather than the 8 bytes [`RandomState`] is.
182		#[derive(Copy, Clone, Debug)]
183		pub struct SeedableRandomState {
184		per_hasher_seed: u64,
185		shared_seed: &'static SharedSeed,
186		}
187
188		impl Default for SeedableRandomState {
189		#[inline(always)]
190	0	fn default() -> Self {
191	0	Self::random()
192	0	}
193		}
194
195		impl SeedableRandomState {
196		/// Generates a random [`SeedableRandomState`], similar to [`RandomState`].
197		#[inline(always)]
198	0	pub fn random() -> Self {
199	0	Self {
200	0	per_hasher_seed: gen_per_hasher_seed(),
201	0	shared_seed: SharedSeed::global_random(),
202	0	}
203	0	}
204
205		/// Generates a fixed [`SeedableRandomState`], similar to [`FixedState`].
206		#[inline(always)]
207	0	pub fn fixed() -> Self {
208	0	Self {
209	0	per_hasher_seed: ARBITRARY3,
210	0	shared_seed: SharedSeed::global_fixed(),
211	0	}
212	0	}
213
214		/// Generates a [`SeedableRandomState`] with the given per-hasher seed
215		/// and [`SharedSeed`].
216		#[inline(always)]
217	0	pub fn with_seed(per_hasher_seed: u64, shared_seed: &'static SharedSeed) -> Self {
218		// XOR with ARBITRARY3 such that with_seed(0) matches default.
219	0	Self {
220	0	per_hasher_seed: per_hasher_seed ^ ARBITRARY3,
221	0	shared_seed,
222	0	}
223	0	}
224		}
225
226		impl BuildHasher for SeedableRandomState {
227		type Hasher = FoldHasher;
228
229		#[inline(always)]
230	0	fn build_hasher(&self) -> FoldHasher {
231	0	FoldHasher::with_seed(self.per_hasher_seed, self.shared_seed)
232	0	}
233		}
234
235		/// A [`BuildHasher`] for [`fast::FoldHasher`](FoldHasher) that always has the same fixed seed.
236		///
237		/// Not recommended unless you absolutely need determinism.
238		#[derive(Copy, Clone, Debug)]
239		pub struct FixedState {
240		per_hasher_seed: u64,
241		}
242
243		impl FixedState {
244		/// Creates a [`FixedState`] with the given per-hasher-seed.
245		#[inline(always)]
246	0	pub const fn with_seed(per_hasher_seed: u64) -> Self {
247		// XOR with ARBITRARY3 such that with_seed(0) matches default.
248	0	Self {
249	0	per_hasher_seed: per_hasher_seed ^ ARBITRARY3,
250	0	}
251	0	}
252		}
253
254		impl Default for FixedState {
255		#[inline(always)]
256	0	fn default() -> Self {
257	0	Self {
258	0	per_hasher_seed: ARBITRARY3,
259	0	}
260	0	}
261		}
262
263		impl BuildHasher for FixedState {
264		type Hasher = FoldHasher;
265
266		#[inline(always)]
267	0	fn build_hasher(&self) -> FoldHasher {
268	0	FoldHasher::with_seed(self.per_hasher_seed, SharedSeed::global_fixed())
269	0	}
270		}