/rust/registry/src/index.crates.io-1949cf8c6b5b557f/foldhash-0.2.0/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_short, 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<'a> {
    accumulator: u64,
    sponge: u128,
    sponge_len: u8,
    seeds: &'a [u64; 6],
}

impl<'a> FoldHasher<'a> {
    /// Initializes this [`FoldHasher`] with the given per-hasher seed and
    /// [`SharedSeed`].
    #[inline]
    pub const fn with_seed(per_hasher_seed: u64, shared_seed: &'a SharedSeed) -> FoldHasher<'a> {
        FoldHasher {
            accumulator: per_hasher_seed,
            sponge: 0,
            sponge_len: 0,
            seeds: &shared_seed.seeds,
        }
    }

    #[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.seeds[0]);
            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<'a> Hasher for FoldHasher<'a> {
    #[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();
        self.accumulator = rotate_right(self.accumulator, len as u32);
        if len <= 16 {
            self.accumulator = hash_bytes_short(bytes, self.accumulator, self.seeds);
        } else {
            unsafe {
                // SAFETY: we checked that the length is > 16 bytes.
                self.accumulator = hash_bytes_long(bytes, self.accumulator, self.seeds);
            }
        }
    }

    #[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.seeds[0]);
    }

    #[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);
    }

    #[cfg(feature = "nightly")]
    #[inline(always)]
    fn write_str(&mut self, s: &str) {
        // Our write function already handles length differences.
        self.write(s.as_bytes())
    }

    #[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.seeds[0])
        } else {
            self.accumulator
        }
    }
}

/// A [`BuildHasher`] for [`fast::FoldHasher`](FoldHasher) that is randomly initialized.
#[derive(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<'static>;

    #[inline(always)]
    fn build_hasher(&self) -> FoldHasher<'static> {
        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(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<'static>;

    #[inline(always)]
    fn build_hasher(&self) -> FoldHasher<'static> {
        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(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<'static>;

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

Coverage Report

Created: 2025-11-16 07:04

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