rapidhash/v3/
rapid_stream_hasher.rs

1use crate::util::hints::{likely, unlikely};
2use crate::util::mix::{rapid_mix, rapid_mum};
3use crate::util::read::{read_u32, read_u64};
4use crate::v3::rapid_const::rapidhash_finish;
5use crate::v3::RapidSecrets;
6
7/// A bytewise-style incremental interface for rapidhash.
8///
9/// This interface guarantees incremental inputs are the same as a bulk hash of the same bytes.
10///
11/// See [`RapidStreamHasherInlineV3`] for more details, or view [`crate::v3::rapidhash_v3_file`] for a
12/// `Read`-based incremental interface.
13///
14/// This is a type alias for [`RapidStreamHasherInlineV3`] that sets:
15/// - `AVALANCHE`: `true`
16/// - `PROTECTED`: `false`
17pub type RapidStreamHasherV3<'a> = RapidStreamHasherInlineV3<'a, true, false>;
18
19/// A bytewise-style incremental interface for rapidhash.
20///
21/// This interface guarantees incremental inputs are the same as a bulk hash of the same bytes.
22///
23/// See [`crate::v3::rapidhash_v3_file`] for an alternative `Read`-based incremental interface.
24///
25/// ## Speed
26///
27/// `RapidStreamHasher` is slower than `rapidhash_v3` due to the extra overhead from the incremental
28/// interface. Where possible, we recommend using `rapidhash_v3` for bulk hashing.
29///
30/// This will copy bytes, except where written chunks are larger than 112 bytes. Larger chunks
31/// will perform better than smaller chunks by avoiding copying.
32///
33/// ## Portability
34///
35/// `RapidStreamHasher` does not implement `std::hash::Hasher` and is specially designed to produce
36/// stable hashes across platforms and compiler versions. Any changes to hash output in
37/// `RapidStreamHasher` will result in a major crate bump.
38///
39/// We're aiming to support the [portable-hash crate](https://github.com/hoxxep/portable-hash) in
40/// the future to enable `derive(PortableHash)` on user-defined types. Please leave a comment or
41/// upvote if this would be useful to you on a large project.
42///
43/// ## Example
44///
45/// ```rust
46/// use rapidhash::v3::{rapidhash_v3_seeded, RapidSecrets, RapidStreamHasherV3};
47///
48/// let secrets = RapidSecrets::seed(0);
49/// let data: &[u8] = [0, 1, 2, 3, 4, 5, 6, 7].as_slice();
50///
51/// // classic rapidhash v3
52/// let expected_hash = rapidhash_v3_seeded(data, &secrets);
53///
54/// // incremental rapidhash v3
55/// let mut hasher = RapidStreamHasherV3::new(&secrets);
56/// hasher.write(&data[0..3]);
57/// hasher.write(&data[3..6]);
58/// hasher.write(&data[6..]);
59/// let actual_hash = hasher.finish();
60///
61/// // equal hashes!
62/// assert_eq!(expected_hash, actual_hash);
63/// ```
64pub struct RapidStreamHasherInlineV3<'a, const AVALANCHE: bool, const PROTECTED: bool> {
65    seed: u64,
66    secrets: &'a [u64; 7],
67    state: RapidStreamChunkState<PROTECTED>,
68
69    /// We treat this as an array with two parts, `[CHUNK_PREV] + [CHUNK]` where
70    /// the `CHUNK_PREV` is the final 16 bytes of the preceding chunk, and
71    /// the `CHUNK` is the latest 112 byte block that we're appending `data` to
72    /// before processing once the block has been filled (or `finish()` is
73    /// called). Rapidhash in its longest form processes 112 byte blocks.
74    buffer: [u8; CHUNK_PREV + CHUNK_SIZE],
75}
76
77/// The size of a single rapidhash processing chunk.
78const CHUNK_SIZE: usize = 112;
79
80/// The minimum tail we must keep in the buffer for processing.
81const CHUNK_PREV: usize = 16;
82
83/// The intermediate hasher state for any full 112-byte chunks that have been written.
84///
85/// This is separated to allow mutably borrowing the state and buffer at the same time.
86struct RapidStreamChunkState<const PROTECTED: bool> {
87    seeds: [u64; 7],
88    /// `buffer_len` **excludes** the `CHUNK_PREV` bytes
89    buffer_len: usize,
90    /// Have we processed a full 112-byte chunk?
91    processed: bool,
92}
93
94impl<'a, const AVALANCHE: bool, const PROTECTED: bool> RapidStreamHasherInlineV3<'a, AVALANCHE, PROTECTED> {
95    /// Create a new `RapidStreamHasher` with seed and secrets.
96    #[inline(always)]
97    pub fn new(secrets: &'a RapidSecrets) -> Self {
98        Self {
99            seed: secrets.seed,
100            secrets: &secrets.secrets,
101            state: RapidStreamChunkState::new(secrets.seed),
102            buffer: [0; CHUNK_PREV + CHUNK_SIZE],
103        }
104    }
105
106    /// Write data to the stream hasher.
107    #[inline(always)]
108    pub fn write(&mut self, data: &[u8]) {
109        // if this data doesn't fit in the remaining buffer, slow-path to write the buffer chunk and
110        // any full chunks we can process from `data`.
111        if unlikely(CHUNK_SIZE < self.state.buffer_len + data.len()) {
112            self.write_inner(data);
113            return;
114        }
115
116        // fast inlined path for copying into the buffer
117        let start = CHUNK_PREV + self.state.buffer_len;
118        let end = start + data.len();
119        self.buffer[start..end].copy_from_slice(data);
120        self.state.buffer_len += data.len();
121    }
122
123    /// Write cold path that we keep separate so the copy logic is fast.
124    #[inline]
125    fn write_inner(&mut self, data: &[u8]) {
126        // set up arrays: chunk_prev as buffer[..16] and chunk_buffer as buffer[16..]
127        let (chunk_prev, chunk_curr) = self.buffer.split_at_mut(CHUNK_PREV);
128        let chunk_prev: &mut [u8; CHUNK_PREV] = chunk_prev.try_into().unwrap();
129        let chunk_buffer: &mut [u8; CHUNK_SIZE] = chunk_curr.try_into().unwrap();
130
131        // write buffer up to 112 bytes
132        let copy_bytes = CHUNK_SIZE - self.state.buffer_len;
133        let start = self.state.buffer_len;
134        chunk_buffer[start..].copy_from_slice(&data[..copy_bytes]);
135        debug_assert_eq!(CHUNK_SIZE, self.state.buffer_len + copy_bytes);
136
137        // write buffer chunk
138        self.state.chunk_write(self.secrets, chunk_buffer);
139
140        // write large data chunks without copying
141        // Keep back the last chunk when chunk-aligned: rapidhash v3 uses `pos + 112 < len`
142        // (not <=), so the final 112 bytes must go through the tail path in finish().
143        let remaining_data = &data[copy_bytes..];
144        let stop = (remaining_data.len().saturating_sub(1) / CHUNK_SIZE) * CHUNK_SIZE;
145        let mut chunk_last = None;
146        let mut pos = 0;
147        while pos < stop {
148            let chunk = remaining_data[pos..pos + CHUNK_SIZE].try_into().unwrap();
149            chunk_last = Some(chunk);
150            self.state.chunk_write(self.secrets, chunk);
151            pos += CHUNK_SIZE;
152        }
153        let unprocessed_data = &remaining_data[pos..];
154
155        // copy the final 16 data bytes from the previous chunk
156        if let Some(chunk) = chunk_last {
157            // if the last full chunk was from `data`
158            chunk_prev.copy_from_slice(&chunk[CHUNK_SIZE - CHUNK_PREV..]);
159        } else {
160            // otherwise the last chunk was from the buffer
161            let trailing_end = chunk_buffer.len() - CHUNK_PREV;
162            chunk_prev.copy_from_slice(&chunk_buffer[trailing_end..]);
163        }
164
165        // write remainder into the buffer
166        chunk_buffer[..unprocessed_data.len()].copy_from_slice(unprocessed_data);
167        self.state.buffer_len = unprocessed_data.len();
168    }
169
170    /// Finalize a hash from the hasher state.
171    #[inline(always)]
172    #[must_use]
173    pub fn finish(&self) -> u64 {
174        let mut seed = self.seed;
175        let mut a;
176        let mut b;
177        let remainder;
178
179        if likely(!self.state.processed && self.state.buffer_len <= 16) {
180            // short <= 16 pass only if we haven't processed a full chunk yet
181            let data =
182                &self.buffer[CHUNK_PREV..CHUNK_PREV + self.state.buffer_len];
183
184            if data.len() >= 4 {
185                seed ^= data.len() as u64;
186                if data.len() >= 8 {
187                    let plast = data.len() - 8;
188                    a = read_u64(data, 0);
189                    b = read_u64(data, plast);
190                } else {
191                    let plast = data.len() - 4;
192                    a = read_u32(data, 0) as u64;
193                    b = read_u32(data, plast) as u64;
194                }
195            } else if !data.is_empty() {
196                a = ((data[0] as u64) << 45) | data[data.len() - 1] as u64;
197                b = data[data.len() >> 1] as u64;
198            } else {
199                a = 0;
200                b = 0;
201            }
202
203            remainder = data.len() as u64;
204        } else {
205            if self.state.processed {
206                // merge independent lanes if we'd previously processed a full 112 byte chunk
207                seed =
208                    self.state.seeds[0]
209                        ^ self.state.seeds[1]
210                        ^ self.state.seeds[2]
211                        ^ self.state.seeds[3]
212                        ^ self.state.seeds[4]
213                        ^ self.state.seeds[5]
214                        ^ self.state.seeds[6];
215            }
216
217            // the >16 tail is the same whether we've processed a full chunk or not
218            let slice = &self.buffer[CHUNK_PREV..CHUNK_PREV + self.state.buffer_len];
219            if slice.len() > 16 {
220                seed = rapid_mix::<PROTECTED>(read_u64(slice, 0) ^ self.secrets[2], read_u64(slice, 8) ^ seed);
221                if slice.len() > 32 {
222                    seed = rapid_mix::<PROTECTED>(read_u64(slice, 16) ^ self.secrets[2], read_u64(slice, 24) ^ seed);
223                    if slice.len() > 48 {
224                        seed = rapid_mix::<PROTECTED>(read_u64(slice, 32) ^ self.secrets[1], read_u64(slice, 40) ^ seed);
225                        if slice.len() > 64 {
226                            seed = rapid_mix::<PROTECTED>(read_u64(slice, 48) ^ self.secrets[1], read_u64(slice, 56) ^ seed);
227                            if slice.len() > 80 {
228                                seed = rapid_mix::<PROTECTED>(read_u64(slice, 64) ^ self.secrets[2], read_u64(slice, 72) ^ seed);
229                                if slice.len() > 96 {
230                                    seed = rapid_mix::<PROTECTED>(read_u64(slice, 80) ^ self.secrets[1], read_u64(slice, 88) ^ seed);
231                                }
232                            }
233                        }
234                    }
235                }
236            }
237
238            // the final 16 bytes may read from the CHUNK_PREV part of the buffer
239            let data = &self.buffer[..CHUNK_PREV + self.state.buffer_len];
240            a = read_u64(data, data.len() - 16) ^ slice.len() as u64;
241            b = read_u64(data, data.len() - 8);
242
243            // passed to rapidhash_finish
244            remainder = self.state.buffer_len as u64;
245        }
246
247        a ^= self.secrets[1];
248        b ^= seed;
249
250        (a, b) = rapid_mum::<PROTECTED>(a, b);
251        if AVALANCHE {
252            rapidhash_finish::<PROTECTED>(a, b, remainder, self.secrets)
253        } else {
254            a ^ b
255        }
256    }
257
258    /// Reuse the buffer within this RapidStreamHasher.
259    #[inline(always)]
260    pub fn reset(&mut self) {
261        self.state.reset(self.seed);
262    }
263}
264
265impl<const PROTECTED: bool> RapidStreamChunkState<PROTECTED> {
266    #[inline(always)]
267    pub fn new(seed: u64) -> Self {
268        Self {
269            seeds: [seed; 7],
270            processed: false,
271            buffer_len: 0,
272        }
273    }
274
275    /// Write a 112-len chunk to the internal state.
276    #[inline(always)]
277    fn chunk_write(&mut self, secrets: &[u64; 7], chunk: &[u8; 112]) {
278        let slice = chunk.as_slice();
279        self.seeds[0] = rapid_mix::<PROTECTED>(read_u64(slice, 0) ^ secrets[0], read_u64(slice, 8) ^ self.seeds[0]);
280        self.seeds[1] = rapid_mix::<PROTECTED>(read_u64(slice, 16) ^ secrets[1], read_u64(slice, 24) ^ self.seeds[1]);
281        self.seeds[2] = rapid_mix::<PROTECTED>(read_u64(slice, 32) ^ secrets[2], read_u64(slice, 40) ^ self.seeds[2]);
282        self.seeds[3] = rapid_mix::<PROTECTED>(read_u64(slice, 48) ^ secrets[3], read_u64(slice, 56) ^ self.seeds[3]);
283        self.seeds[4] = rapid_mix::<PROTECTED>(read_u64(slice, 64) ^ secrets[4], read_u64(slice, 72) ^ self.seeds[4]);
284        self.seeds[5] = rapid_mix::<PROTECTED>(read_u64(slice, 80) ^ secrets[5], read_u64(slice, 88) ^ self.seeds[5]);
285        self.seeds[6] = rapid_mix::<PROTECTED>(read_u64(slice, 96) ^ secrets[6], read_u64(slice, 104) ^ self.seeds[6]);
286        self.processed = true;
287    }
288
289    /// Reuse the buffer within this RapidStreamHasher.
290    #[inline(always)]
291    pub fn reset(&mut self, seed: u64) {
292        self.seeds = [seed; 7];
293        self.processed = false;
294        self.buffer_len = 0;
295    }
296}
297
298#[cfg(test)]
299mod tests {
300    use crate::util::macros::compare_rapid_stream_hasher;
301    use crate::v3::{rapidhash_v3_inline, DEFAULT_RAPID_SECRETS};
302    use super::*;
303
304    compare_rapid_stream_hasher!(compare_stream_hasher_v3, rapidhash_v3_inline::<true, false, false>, RapidStreamHasherV3<'a>);
305    compare_rapid_stream_hasher!(compare_stream_hasher_v3_protected, rapidhash_v3_inline::<true, false, true>, RapidStreamHasherInlineV3::<'a, true, true>);
306    compare_rapid_stream_hasher!(compare_stream_hasher_v3_no_avalanche, rapidhash_v3_inline::<false, false, false>, RapidStreamHasherInlineV3::<'a, false, false>);
307
308    #[test]
309    fn test_rapid_stream_hasher() {
310        let secrets = DEFAULT_RAPID_SECRETS;
311        let data: &[u8] = &[0, 1, 2, 3, 4, 5, 6, 7];
312        let expected_hash = rapidhash_v3_inline::<true, false, false>(data, &secrets);
313
314        let mut hasher = RapidStreamHasherV3::new(&secrets);
315        hasher.write(data);
316        assert_eq!(expected_hash, hasher.finish());
317
318        hasher.reset();
319        hasher.write(&data[..1]);
320        hasher.write(&data[1..3]);
321        hasher.write(&data[3..6]);
322        hasher.write(&data[6..]);
323        assert_eq!(expected_hash, hasher.finish());
324    }
325
326    #[test]
327    fn test_chunk_writing() {
328        let secrets = DEFAULT_RAPID_SECRETS;
329        let mut hasher = RapidStreamHasherV3::new(&secrets);
330
331        let mut data = [0; 128];
332        for i in 0..data.len() {
333            data[i] = i as u8;
334        }
335
336        hasher.write(&data);
337        assert_eq!(&hasher.buffer[..32], &data[128-32..]);
338    }
339}
rapidhash/v3/rapid_stream_hasher.rs

rapidhash/v3/
rapid_stream_hasher.rs
