osom_lib_hashes/
fxhash.rs

1//! Holds the implementation of the `FxHash` algorithm.
2
3use core::hash::{BuildHasher, Hasher};
4
5use osom_lib_arrays::{
6    const_helpers::{fill_const, from_le_const_u64, subslice_mut_const},
7    fixed_array::ConstBuffer,
8};
9use osom_lib_reprc::macros::reprc;
10
11use crate::traits::HashFunction;
12
13const MULTIPLIER: u64 = 0x517cc1b727220a95;
14
15/// Implementation of the `FxHash` algorithm.
16///
17/// This is a fast, non-cryptographic hash function,
18/// suitable for use in hash tables.
19#[reprc]
20#[must_use]
21pub struct FxHash {
22    state: u64,
23    bufferer: ConstBuffer<8, u8>,
24}
25
26macro_rules! update_slice {
27    ($state:expr, $slice:expr) => {{
28        let word = unsafe { from_le_const_u64(($slice), 0) };
29        (($state).rotate_left(15) ^ word).wrapping_mul(MULTIPLIER)
30    }};
31}
32
33impl FxHash {
34    /// Creates a new [`FxHash`] instance with the default initial state.
35    #[inline(always)]
36    pub const fn new() -> Self {
37        Self {
38            state: 0,
39            bufferer: ConstBuffer::new(),
40        }
41    }
42
43    /// Creates a new [`FxHash`] instance with the given seed.
44    #[inline]
45    pub const fn with_seed(seed: u64) -> Self {
46        let mut hasher = Self::new();
47        hasher.update_const(&seed.to_le_bytes());
48        hasher
49    }
50
51    /// Updates the internal state with the given data.
52    pub const fn update_const(&mut self, data: &[u8]) {
53        let mut iterator = self.bufferer.buffer_const(data);
54        while let Some(block) = iterator.next() {
55            self.state = update_slice!(self.state, block);
56        }
57    }
58
59    /// Returns the final hash value.
60    ///
61    /// This function does not update the internal state, and thus
62    /// [`FxHash`] can still be used afterwards.
63    #[must_use]
64    pub const fn result_const(&self) -> u64 {
65        if self.bufferer.length().as_usize() == 0 {
66            return self.state;
67        }
68        let current_bufferer = self.bufferer.clone_const();
69        let mut current_array = current_bufferer.release_const();
70        let current_array_len = current_array.length().as_usize();
71        let raw_current_array = unsafe { current_array.as_raw_slice_mut_const() };
72        unsafe {
73            fill_const(subslice_mut_const(raw_current_array, current_array_len..8), 0);
74        }
75        update_slice!(self.state, raw_current_array)
76    }
77
78    /// Clones the [`FxHash`] instance.
79    #[inline(always)]
80    pub const fn clone_const(&self) -> Self {
81        Self {
82            state: self.state,
83            bufferer: self.bufferer.clone_const(),
84        }
85    }
86}
87
88impl Clone for FxHash {
89    #[inline(always)]
90    fn clone(&self) -> Self {
91        self.clone_const()
92    }
93}
94
95impl Default for FxHash {
96    #[inline(always)]
97    fn default() -> Self {
98        Self::new()
99    }
100}
101
102impl HashFunction for FxHash {
103    type Output = [u8; 8];
104
105    #[inline(always)]
106    fn update(&mut self, data: impl AsRef<[u8]>) {
107        self.update_const(data.as_ref());
108    }
109
110    #[inline(always)]
111    fn write_result(&self, output: &mut Self::Output) {
112        *output = self.result_const().to_le_bytes();
113    }
114}
115
116impl Hasher for FxHash {
117    #[inline(always)]
118    fn finish(&self) -> u64 {
119        self.result_const()
120    }
121
122    #[inline(always)]
123    fn write(&mut self, bytes: &[u8]) {
124        self.update_const(bytes);
125    }
126}
127
128/// Represents a builder for [`FxHash`].
129#[reprc]
130#[repr(transparent)]
131#[must_use]
132pub struct FxHashBuilder {
133    inner: FxHash,
134}
135
136impl Clone for FxHashBuilder {
137    fn clone(&self) -> Self {
138        Self {
139            inner: self.inner.clone_const(),
140        }
141    }
142}
143
144impl FxHashBuilder {
145    /// Creates a new [`FxHashBuilder`] instance with the default initial state.
146    #[inline(always)]
147    pub const fn new() -> Self {
148        Self { inner: FxHash::new() }
149    }
150
151    /// Updates the seed for the [`FxHash`] instance.
152    #[inline(always)]
153    pub const fn set_seed(mut self, seed: u64) -> Self {
154        self.inner = FxHash::with_seed(seed);
155        self
156    }
157
158    /// Creates a new [`FxHash`] instance from the builder.
159    #[inline(always)]
160    pub const fn create_hasher(&self) -> FxHash {
161        self.inner.clone_const()
162    }
163}
164
165impl BuildHasher for FxHashBuilder {
166    type Hasher = FxHash;
167
168    #[inline(always)]
169    fn build_hasher(&self) -> Self::Hasher {
170        self.create_hasher()
171    }
172}
173
174impl Default for FxHashBuilder {
175    #[inline(always)]
176    fn default() -> Self {
177        Self::new()
178    }
179}
osom_lib_hashes/fxhash.rs

osom_lib_hashes/
fxhash.rs
