osom_lib_hashes/
fxhash.rs

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

osom_lib_hashes/
fxhash.rs
