osom_lib_hashes/
siphash.rs

1//! Holds the implementation of the `SipHash` algorithm.
2
3#![allow(clippy::assign_op_pattern, clippy::cast_possible_truncation, clippy::doc_markdown)]
4
5use core::hash::{BuildHasher, Hasher};
6
7use osom_lib_arrays::{
8    const_helpers::{fill_const, from_le_const_u64, subslice_mut_const},
9    fixed_array::ConstBuffer,
10};
11use osom_lib_reprc::macros::reprc;
12
13use crate::traits::HashFunction;
14
15/// Implementation of the `SipHash` algorithm.
16///
17/// This algorithm is resistant to various hash attacks when C >= 2 and D >= 4.
18///
19/// # Notes
20///
21/// The `HashFunction` implementation returns values in little-endian order,
22/// and thus is cross-platform (with slightly better performance on little-endian platforms).
23///
24/// This algorithm is an implementation of the "SipHash: a fast short-input PRF" paper
25/// by Jean-Philippe Aumasson and Daniel J. Bernstein.
26#[reprc]
27#[must_use]
28pub struct GeneralSipHash<const C: u32, const D: u32> {
29    /// Current state of the hash function.
30    state: [u64; 4],
31
32    bufferer: ConstBuffer<8, u8>,
33
34    /// How many bytes have been hashed so far, mod 256. This value is used
35    /// at the final step of the algorithm.
36    last_byte: u8,
37}
38
39unsafe impl<const C: u32, const D: u32> Send for GeneralSipHash<C, D> {}
40unsafe impl<const C: u32, const D: u32> Sync for GeneralSipHash<C, D> {}
41
42impl<const C: u32, const D: u32> GeneralSipHash<C, D> {
43    /// Creates a new [`GeneralSipHash`] instance from a given array key.
44    #[inline]
45    pub const fn for_array_key(key: &[u8; 2 * size_of::<u64>()]) -> Self {
46        unsafe {
47            let k0 = from_le_const_u64(key, 0);
48            let k1 = from_le_const_u64(key, size_of::<u64>());
49            Self::for_keys(k0, k1)
50        }
51    }
52
53    /// Creates a new [`GeneralSipHash`] instance from a given slice.
54    ///
55    /// # Panics
56    ///
57    /// If the key is not exactly 16 bytes long, this function will panic.
58    #[inline]
59    pub const fn for_slice_key(key: &[u8]) -> Self {
60        assert!(
61            key.len() == 2 * size_of::<u64>(),
62            "The key must be exactly 16 bytes long."
63        );
64        unsafe {
65            let k0 = from_le_const_u64(key, 0);
66            let k1 = from_le_const_u64(key, size_of::<u64>());
67            Self::for_keys(k0, k1)
68        }
69    }
70
71    /// Creates a new [`GeneralSipHash`] instance from a key pair.
72    #[inline]
73    pub const fn for_keys(key0: u64, key1: u64) -> Self {
74        Self {
75            state: [
76                key0 ^ 0x736f6d6570736575,
77                key1 ^ 0x646f72616e646f6d,
78                key0 ^ 0x6c7967656e657261,
79                key1 ^ 0x7465646279746573,
80            ],
81            bufferer: ConstBuffer::new(),
82            last_byte: 0,
83        }
84    }
85
86    const fn update_with_full_block(state: &mut [u64; 4], data: &[u8]) {
87        debug_assert!(data.len() >= 8, "The block must be at least 8 bytes long.");
88        let value = unsafe { from_le_const_u64(data, 0) };
89        state[3] = state[3] ^ value;
90        sip_rounds::<C>(state);
91        state[0] = state[0] ^ value;
92    }
93
94    /// Updates the underlying state with the given block.
95    ///
96    /// # Panics
97    ///
98    /// If the length of the block exceeds `u32::MAX`.
99    pub const fn update_const(&mut self, data: &[u8]) {
100        let len = data.len();
101
102        assert!(
103            len <= u32::MAX as usize,
104            "The max size of a chunk for SipHash is u32::MAX."
105        );
106
107        // This is a safety cast, in case `usize` is 32-bit.
108        // We need 64-bit in case u32 overflows. While unlikely,
109        // better safe than sorry.
110        let len = len as u64;
111
112        self.last_byte = self.last_byte.wrapping_add(len as u8);
113
114        let mut iterator = self.bufferer.buffer_const(data);
115        while let Some(block) = iterator.next() {
116            Self::update_with_full_block(&mut self.state, block);
117        }
118    }
119
120    /// Calculates the final hash value.
121    ///
122    /// This function does not update the internal state, and thus
123    /// [`SipHash`] can still be used afterwards.
124    #[must_use]
125    pub const fn result_const(&self) -> u64 {
126        // Update the final block
127        let mut state = self.state;
128        let current_bufferer = self.bufferer.clone_const();
129        let mut current_array = current_bufferer.release_const();
130        let current_array_len = current_array.length().as_usize();
131        let raw_current_array = unsafe { current_array.as_raw_slice_mut_const() };
132
133        unsafe {
134            fill_const(subslice_mut_const(raw_current_array, current_array_len..7), 0);
135            raw_current_array[7] = self.last_byte;
136        }
137
138        Self::update_with_full_block(&mut state, raw_current_array);
139
140        // Finalization
141        state[2] = state[2] ^ 0xff;
142        sip_rounds::<D>(&mut state);
143        state[0] ^ state[1] ^ state[2] ^ state[3]
144    }
145}
146
147impl<const C: u32, const D: u32> HashFunction for GeneralSipHash<C, D> {
148    type Output = [u8; 8];
149
150    #[inline(always)]
151    fn update(&mut self, data: impl AsRef<[u8]>) {
152        self.update_const(data.as_ref());
153    }
154
155    #[inline(always)]
156    fn write_result(&self, output: &mut Self::Output) {
157        *output = self.result_const().to_le_bytes();
158    }
159}
160
161const fn sip_rounds<const ROUNDS: u32>(state: &mut [u64; 4]) {
162    let mut index = 0;
163    while index < ROUNDS {
164        state[0] = state[0].wrapping_add(state[1]);
165        state[1] = state[1].rotate_left(13);
166        state[1] = state[1] ^ state[0];
167        state[0] = state[0].rotate_left(32);
168        state[2] = state[2].wrapping_add(state[3]);
169        state[3] = state[3].rotate_left(16);
170        state[3] = state[3] ^ state[2];
171        state[0] = state[0].wrapping_add(state[3]);
172        state[3] = state[3].rotate_left(21);
173        state[3] = state[3] ^ state[0];
174        state[2] = state[2].wrapping_add(state[1]);
175        state[1] = state[1].rotate_left(17);
176        state[1] = state[1] ^ state[2];
177        state[2] = state[2].rotate_left(32);
178        index += 1;
179    }
180}
181
182impl<const C: u32, const D: u32> Hasher for GeneralSipHash<C, D> {
183    #[inline(always)]
184    fn finish(&self) -> u64 {
185        self.result_const()
186    }
187
188    #[inline(always)]
189    fn write(&mut self, bytes: &[u8]) {
190        self.update_const(bytes);
191    }
192}
193
194/// Represents a builder for [`GeneralSipHash`].
195#[reprc]
196#[must_use]
197pub struct GeneralSipHashBuilder<const C: u32, const D: u32> {
198    key0: u64,
199    key1: u64,
200}
201
202impl<const C: u32, const D: u32> GeneralSipHashBuilder<C, D> {
203    /// Creates a new [`GeneralSipHashBuilder`] instance with custom keys.
204    #[inline(always)]
205    pub const fn with_keys(key0: u64, key1: u64) -> Self {
206        Self { key0, key1 }
207    }
208
209    /// Creates a new [`GeneralSipHashBuilder`] instance from a given array key.
210    #[inline]
211    pub const fn with_array_key(key: &[u8; 2 * size_of::<u64>()]) -> Self {
212        unsafe {
213            let k0 = from_le_const_u64(key, 0);
214            let k1 = from_le_const_u64(key, size_of::<u64>());
215            Self::with_keys(k0, k1)
216        }
217    }
218
219    /// Creates a new [`GeneralSipHashBuilder`] instance from a given slice.
220    ///
221    /// # Panics
222    ///
223    /// If the key is not exactly 16 bytes long, this function will panic.
224    #[inline]
225    pub const fn with_slice_key(key: &[u8]) -> Self {
226        assert!(
227            key.len() == 2 * size_of::<u64>(),
228            "The key must be exactly 16 bytes long."
229        );
230
231        unsafe {
232            let k0 = from_le_const_u64(key, 0);
233            let k1 = from_le_const_u64(key, size_of::<u64>());
234            Self::with_keys(k0, k1)
235        }
236    }
237
238    /// Creates a new [`GeneralSipHash`] instance from the builder.
239    #[inline(always)]
240    pub const fn create_hasher(&self) -> GeneralSipHash<C, D> {
241        GeneralSipHash::for_keys(self.key0, self.key1)
242    }
243}
244
245impl<const C: u32, const D: u32> BuildHasher for GeneralSipHashBuilder<C, D> {
246    type Hasher = GeneralSipHash<C, D>;
247
248    #[inline(always)]
249    fn build_hasher(&self) -> Self::Hasher {
250        self.create_hasher()
251    }
252}
253
254impl<const C: u32, const D: u32> Clone for GeneralSipHashBuilder<C, D> {
255    #[inline(always)]
256    fn clone(&self) -> Self {
257        Self {
258            key0: self.key0,
259            key1: self.key1,
260        }
261    }
262}
263
264/// The alias for [`GeneralSipHash<2, 4>`], which is an optimal choice of constants.
265pub type SipHash = GeneralSipHash<2, 4>;
266
267/// The alias for [`GeneralSipHashBuilder<2, 4>`], which is an optimal choice of constants.
268pub type SipHashBuilder = GeneralSipHashBuilder<2, 4>;
osom_lib_hashes/siphash.rs

osom_lib_hashes/
siphash.rs
