ahash/
random_state.rs

1#[cfg(all(feature = "runtime-rng", not(all(feature = "compile-time-rng", test))))]
2use crate::convert::Convert;
3#[cfg(feature = "specialize")]
4use crate::BuildHasherExt;
5
6#[cfg(any(
7    all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)),
8    all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd")
9))]
10pub use crate::aes_hash::*;
11
12#[cfg(not(any(
13    all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)),
14    all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd")
15)))]
16pub use crate::fallback_hash::*;
17
18#[cfg(all(feature = "compile-time-rng", any(not(feature = "runtime-rng"), test)))]
19use const_random::const_random;
20use core::any::{Any, TypeId};
21use core::fmt;
22use core::hash::BuildHasher;
23#[cfg(feature = "specialize")]
24use core::hash::Hash;
25use core::hash::Hasher;
26
27#[cfg(not(feature = "std"))]
28extern crate alloc;
29#[cfg(feature = "std")]
30extern crate std as alloc;
31
32#[cfg(feature = "atomic-polyfill")]
33use atomic_polyfill as atomic;
34#[cfg(not(feature = "atomic-polyfill"))]
35use core::sync::atomic;
36
37use alloc::boxed::Box;
38use atomic::{AtomicUsize, Ordering};
39#[cfg(not(all(target_arch = "arm", target_os = "none")))]
40use once_cell::race::OnceBox;
41
42#[cfg(any(
43    all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)),
44    all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd")
45))]
46use crate::aes_hash::*;
47#[cfg(not(any(
48    all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "aes", not(miri)),
49    all(any(target_arch = "arm", target_arch = "aarch64"), target_feature = "crypto", not(miri), feature = "stdsimd")
50)))]
51use crate::fallback_hash::*;
52
53#[cfg(not(all(target_arch = "arm", target_os = "none")))]
54static RAND_SOURCE: OnceBox<Box<dyn RandomSource + Send + Sync>> = OnceBox::new();
55
56/// A supplier of Randomness used for different hashers.
57/// See [RandomState.set_random_source].
58pub trait RandomSource {
59
60    fn get_fixed_seeds(&self) -> &'static [[u64; 4]; 2];
61
62    fn gen_hasher_seed(&self) -> usize;
63
64}
65
66pub(crate) const PI: [u64; 4] = [
67    0x243f_6a88_85a3_08d3,
68    0x1319_8a2e_0370_7344,
69    0xa409_3822_299f_31d0,
70    0x082e_fa98_ec4e_6c89,
71];
72
73pub(crate) const PI2: [u64; 4] = [
74    0x4528_21e6_38d0_1377,
75    0xbe54_66cf_34e9_0c6c,
76    0xc0ac_29b7_c97c_50dd,
77    0x3f84_d5b5_b547_0917,
78];
79
80struct DefaultRandomSource {
81    counter: AtomicUsize,
82}
83
84impl DefaultRandomSource {
85    fn new() -> DefaultRandomSource {
86        DefaultRandomSource {
87            counter: AtomicUsize::new(&PI as *const _ as usize),
88        }
89    }
90
91    const fn default() -> DefaultRandomSource {
92        DefaultRandomSource {
93            counter: AtomicUsize::new(PI[3] as usize),
94        }
95    }
96}
97
98impl RandomSource for DefaultRandomSource {
99
100    #[cfg(all(feature = "runtime-rng", not(all(feature = "compile-time-rng", test))))]
101    fn get_fixed_seeds(&self) -> &'static [[u64; 4]; 2] {
102        static SEEDS: OnceBox<[[u64; 4]; 2]> = OnceBox::new();
103
104        SEEDS.get_or_init(|| {
105            let mut result: [u8; 64] = [0; 64];
106            getrandom::getrandom(&mut result).expect("getrandom::getrandom() failed.");
107            Box::new(result.convert())
108        })
109    }
110
111    #[cfg(all(feature = "compile-time-rng", any(not(feature = "runtime-rng"), test)))]
112    fn get_fixed_seeds(&self) -> &'static [[u64; 4]; 2] {
113        const RAND: [[u64; 4]; 2] = [
114            [
115                const_random!(u64),
116                const_random!(u64),
117                const_random!(u64),
118                const_random!(u64),
119            ], [
120                const_random!(u64),
121                const_random!(u64),
122                const_random!(u64),
123                const_random!(u64),
124            ]
125        ];
126        &RAND
127    }
128
129    #[cfg(all(not(feature = "runtime-rng"), not(feature = "compile-time-rng")))]
130    fn get_fixed_seeds(&self) -> &'static [[u64; 4]; 2] {
131        &[PI, PI2]
132    }
133
134    #[cfg(not(all(target_arch = "arm", target_os = "none")))]
135    fn gen_hasher_seed(&self) -> usize {
136        let stack = self as *const _ as usize;
137        self.counter.fetch_add(stack, Ordering::Relaxed)
138    }
139
140    #[cfg(all(target_arch = "arm", target_os = "none"))]
141    fn gen_hasher_seed(&self) -> usize {
142        let stack = self as *const _ as usize;
143        let previous = self.counter.load(Ordering::Relaxed);
144        let new = previous.wrapping_add(stack);
145        self.counter.store(new, Ordering::Relaxed);
146        new
147    }
148}
149
150/// Provides a [Hasher] factory. This is typically used (e.g. by [HashMap]) to create
151/// [AHasher]s in order to hash the keys of the map. See `build_hasher` below.
152///
153/// [build_hasher]: ahash::
154/// [Hasher]: std::hash::Hasher
155/// [BuildHasher]: std::hash::BuildHasher
156/// [HashMap]: std::collections::HashMap
157#[derive(Clone)]
158pub struct RandomState {
159    pub(crate) k0: u64,
160    pub(crate) k1: u64,
161    pub(crate) k2: u64,
162    pub(crate) k3: u64,
163}
164
165impl fmt::Debug for RandomState {
166    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
167        f.pad("RandomState { .. }")
168    }
169}
170
171impl RandomState {
172
173    /// Provides an optional way to manually supply a source of randomness for Hasher keys.
174    ///
175    /// The provided [RandomSource] will be used to be used as a source of randomness by [RandomState] to generate new states.
176    /// If this method is not invoked the standard source of randomness is used as described in the Readme.
177    ///
178    /// The source of randomness can only be set once, and must be set before the first RandomState is created.
179    /// If the source has already been specified `Err` is returned with a `bool` indicating if the set failed because
180    /// method was previously invoked (true) or if the default source is already being used (false).
181    #[cfg(not(all(target_arch = "arm", target_os = "none")))]
182    pub fn set_random_source(source: impl RandomSource + Send + Sync + 'static) -> Result<(), bool> {
183        RAND_SOURCE.set(Box::new(Box::new(source))).map_err(|s| s.as_ref().type_id() != TypeId::of::<&DefaultRandomSource>())
184    }
185
186    #[inline]
187    #[cfg(not(all(target_arch = "arm", target_os = "none")))]
188    fn get_src() -> &'static dyn RandomSource {
189        RAND_SOURCE.get_or_init(|| Box::new(Box::new(DefaultRandomSource::new()))).as_ref()
190    }
191
192    #[inline]
193    #[cfg(all(target_arch = "arm", target_os = "none"))]
194    fn get_src() -> &'static dyn RandomSource {
195        static RAND_SOURCE: DefaultRandomSource = DefaultRandomSource::default();
196        &RAND_SOURCE
197    }
198
199    /// Use randomly generated keys
200    #[inline]
201    pub fn new() -> RandomState {
202        let src = Self::get_src();
203        let fixed = src.get_fixed_seeds();
204        Self::from_keys(&fixed[0], &fixed[1], src.gen_hasher_seed())
205    }
206
207    /// Allows for supplying seeds, but each time it is called the resulting state will be different.
208    /// This is done using a static counter, so it can safely be used with a fixed keys.
209    #[inline]
210    pub fn generate_with(k0: u64, k1: u64, k2: u64, k3: u64) -> RandomState {
211        let src = Self::get_src();
212        let fixed = src.get_fixed_seeds();
213        RandomState::from_keys(&fixed[0], &[k0, k1, k2, k3], src.gen_hasher_seed())
214    }
215
216    fn from_keys(a: &[u64; 4], b: &[u64; 4], c: usize) -> RandomState {
217        let &[k0, k1, k2, k3] = a;
218        let mut hasher = AHasher::from_random_state(&RandomState { k0, k1, k2, k3 });
219        hasher.write_usize(c);
220        let mix = |k: u64| {
221            let mut h = hasher.clone();
222            h.write_u64(k);
223            h.finish()
224        };
225        RandomState {
226            k0: mix(b[0]),
227            k1: mix(b[1]),
228            k2: mix(b[2]),
229            k3: mix(b[3]),
230        }
231    }
232
233    /// Internal. Used by Default.
234    #[inline]
235    pub(crate) fn with_fixed_keys() -> RandomState {
236        let [k0, k1, k2, k3] = Self::get_src().get_fixed_seeds()[0];
237        RandomState { k0, k1, k2, k3 }
238    }
239
240    /// Allows for explicitly setting a seed to used.
241    ///
242    /// Note: This method does not require the provided seed to be strong.
243    #[inline]
244    pub fn with_seed(key: usize) -> RandomState {
245        let fixed = Self::get_src().get_fixed_seeds();
246        RandomState::from_keys(&fixed[0], &fixed[1], key)
247    }
248
249    /// Allows for explicitly setting the seeds to used.
250    ///
251    /// Note: This method is robust against 0s being passed for one or more of the parameters
252    /// or the same value being passed for more than one parameter.
253    #[inline]
254    pub const fn with_seeds(k0: u64, k1: u64, k2: u64, k3: u64) -> RandomState {
255        RandomState { k0: k0 ^ PI2[0], k1: k1 ^ PI2[1], k2: k2 ^ PI2[2], k3: k3 ^ PI2[3] }
256    }
257}
258
259impl Default for RandomState {
260    #[inline]
261    fn default() -> Self {
262        Self::new()
263    }
264}
265
266impl BuildHasher for RandomState {
267    type Hasher = AHasher;
268
269    /// Constructs a new [AHasher] with keys based on this [RandomState] object.
270    /// This means that two different [RandomState]s will will generate
271    /// [AHasher]s that will return different hashcodes, but [Hasher]s created from the same [BuildHasher]
272    /// will generate the same hashes for the same input data.
273    ///
274    /// # Examples
275    ///
276    /// ```
277    /// use ahash::{AHasher, RandomState};
278    /// use std::hash::{Hasher, BuildHasher};
279    ///
280    /// let build_hasher = RandomState::new();
281    /// let mut hasher_1 = build_hasher.build_hasher();
282    /// let mut hasher_2 = build_hasher.build_hasher();
283    ///
284    /// hasher_1.write_u32(1234);
285    /// hasher_2.write_u32(1234);
286    ///
287    /// assert_eq!(hasher_1.finish(), hasher_2.finish());
288    ///
289    /// let other_build_hasher = RandomState::new();
290    /// let mut different_hasher = other_build_hasher.build_hasher();
291    /// different_hasher.write_u32(1234);
292    /// assert_ne!(different_hasher.finish(), hasher_1.finish());
293    /// ```
294    /// [Hasher]: std::hash::Hasher
295    /// [BuildHasher]: std::hash::BuildHasher
296    /// [HashMap]: std::collections::HashMap
297    #[inline]
298    fn build_hasher(&self) -> AHasher {
299        AHasher::from_random_state(self)
300    }
301}
302
303#[cfg(feature = "specialize")]
304impl BuildHasherExt for RandomState {
305    #[inline]
306    fn hash_as_u64<T: Hash + ?Sized>(&self, value: &T) -> u64 {
307        let mut hasher = AHasherU64 {
308            buffer: self.k0,
309            pad: self.k1,
310        };
311        value.hash(&mut hasher);
312        hasher.finish()
313    }
314
315    #[inline]
316    fn hash_as_fixed_length<T: Hash + ?Sized>(&self, value: &T) -> u64 {
317        let mut hasher = AHasherFixed(self.build_hasher());
318        value.hash(&mut hasher);
319        hasher.finish()
320    }
321
322    #[inline]
323    fn hash_as_str<T: Hash + ?Sized>(&self, value: &T) -> u64 {
324        let mut hasher = AHasherStr(self.build_hasher());
325        value.hash(&mut hasher);
326        hasher.finish()
327    }
328}
329
330#[cfg(test)]
331mod test {
332    use super::*;
333
334    #[test]
335    fn test_unique() {
336        let a = RandomState::new();
337        let b = RandomState::new();
338        assert_ne!(a.build_hasher().finish(), b.build_hasher().finish());
339    }
340
341    #[cfg(all(feature = "runtime-rng", not(all(feature = "compile-time-rng", test))))]
342    #[test]
343    fn test_not_pi() {
344        assert_ne!(PI, RandomState::get_src().get_fixed_seeds()[0]);
345    }
346
347    #[cfg(all(feature = "compile-time-rng", any(not(feature = "runtime-rng"), test)))]
348    #[test]
349    fn test_not_pi_const() {
350        assert_ne!(PI, RandomState::get_src().get_fixed_seeds()[0]);
351    }
352
353    #[cfg(all(not(feature = "runtime-rng"), not(feature = "compile-time-rng")))]
354    #[test]
355    fn test_pi() {
356        assert_eq!(PI, RandomState::get_src().get_fixed_seeds()[0]);
357    }
358
359    #[test]
360    fn test_with_seeds_const() {
361        const _CONST_RANDOM_STATE: RandomState = RandomState::with_seeds(17, 19, 21, 23);
362    }
363}