repame_sim/
hash.rs

1//! The hash a determinism check folds: FNV-1a 64.
2//!
3//! FNV-1a 64 is what the games' hand-rolled session digests already used, so
4//! the engine and a game agree on a digest and nothing new is pulled in for it.
5//! It is a change detector, not a cryptographic hash: state nobody folds does
6//! not move it, and a crafted collision is possible. Use it to find *where* two
7//! runs differ, not to prove they cannot.
8//!
9//! Determinism rule: every value is folded as its bytes, little-endian, one byte
10//! at a time, in the order the caller wrote it. `usize`/`isize` fold as
11//! `u64`/`i64`, so a 32-bit wasm build folds the same bytes as a 64-bit desktop
12//! build for the same value, and a float folds its `to_bits`, so the digest is
13//! bit-exact rather than approximate (`0.0` and `-0.0` differ, NaN payloads
14//! included). Strings are length-prefixed, so two short strings cannot fold
15//! like one long one. Unlike `std`'s `DefaultHasher`, nothing here is seeded
16//! per process: a digest computed in one run means the same thing in the next.
17
18use std::hash::Hasher;
19
20/// FNV-1a 64 offset basis: the digest of no bytes at all.
21const OFFSET: u64 = 0xCBF2_9CE4_8422_2325;
22
23/// FNV-1a 64 prime.
24const PRIME: u64 = 0x0000_0100_0000_01B3;
25
26/// FNV-1a 64 over `bytes`.
27///
28/// `const`, so a name can fold to a number at compile time; [`Hash64`] folds the
29/// same bytes when it is written to.
30pub const fn fnv1a64(bytes: &[u8]) -> u64 {
31    let mut state = OFFSET;
32    let mut index = 0;
33    while index < bytes.len() {
34        state ^= bytes[index] as u64;
35        state = state.wrapping_mul(PRIME);
36        index += 1;
37    }
38    state
39}
40
41/// A streaming FNV-1a 64 digest: write values in a fixed order, read
42/// [`digest`](Self::digest).
43///
44/// It is also a [`Hasher`], so a type whose `Hash` implementation is yours can be
45/// folded through `Hash::hash`. The two paths agree on every primitive: this type
46/// overrides every integer writer, so `u32` folds as four little-endian bytes
47/// either way. They differ on `str`, which the harness's own [`str`](Self::str)
48/// length-prefixes while `Hash`'s stable default writes the bytes and a `0xff`;
49/// both are pinned, pick one and stay with it.
50#[derive(Clone, Copy, Debug, PartialEq, Eq)]
51pub struct Hash64 {
52    state: u64,
53}
54
55impl Hash64 {
56    /// A digest of nothing: the FNV-1a offset basis.
57    pub const fn new() -> Self {
58        Self { state: OFFSET }
59    }
60
61    /// What has been written so far.
62    ///
63    /// Writing more changes it, so read it where the stream ends.
64    pub const fn digest(&self) -> u64 {
65        self.state
66    }
67
68    /// Raw bytes, as given: no length prefix, no padding.
69    pub fn bytes(&mut self, bytes: &[u8]) {
70        for byte in bytes {
71            self.state ^= *byte as u64;
72            self.state = self.state.wrapping_mul(PRIME);
73        }
74    }
75
76    /// A string as its length then its UTF-8 bytes.
77    pub fn str(&mut self, value: &str) {
78        self.u64(value.len() as u64);
79        self.bytes(value.as_bytes());
80    }
81
82    /// One byte.
83    pub fn u8(&mut self, value: u8) {
84        self.bytes(&[value]);
85    }
86
87    /// A 16-bit value, little-endian.
88    pub fn u16(&mut self, value: u16) {
89        self.bytes(&value.to_le_bytes());
90    }
91
92    /// A 32-bit value, little-endian.
93    pub fn u32(&mut self, value: u32) {
94        self.bytes(&value.to_le_bytes());
95    }
96
97    /// A 64-bit value, little-endian.
98    pub fn u64(&mut self, value: u64) {
99        self.bytes(&value.to_le_bytes());
100    }
101
102    /// A 128-bit value, little-endian.
103    pub fn u128(&mut self, value: u128) {
104        self.bytes(&value.to_le_bytes());
105    }
106
107    /// A signed value as its two's-complement bits.
108    pub fn i8(&mut self, value: i8) {
109        self.u8(value as u8);
110    }
111
112    /// A signed value as its two's-complement bits.
113    pub fn i16(&mut self, value: i16) {
114        self.u16(value as u16);
115    }
116
117    /// A signed value as its two's-complement bits.
118    pub fn i32(&mut self, value: i32) {
119        self.u32(value as u32);
120    }
121
122    /// A signed value as its two's-complement bits.
123    pub fn i64(&mut self, value: i64) {
124        self.u64(value as u64);
125    }
126
127    /// A length or index, folded as `u64` so the width is not target-dependent.
128    pub fn usize(&mut self, value: usize) {
129        self.u64(value as u64);
130    }
131
132    /// A length or index, folded as `i64` so the width is not target-dependent.
133    pub fn isize(&mut self, value: isize) {
134        self.i64(value as i64);
135    }
136
137    /// A float by its bits, so the fold is exact.
138    pub fn f32(&mut self, value: f32) {
139        self.u32(value.to_bits());
140    }
141
142    /// A float by its bits, so the fold is exact.
143    pub fn f64(&mut self, value: f64) {
144        self.u64(value.to_bits());
145    }
146
147    /// A bool as one byte, `0` or `1`.
148    pub fn bool(&mut self, value: bool) {
149        self.u8(value as u8);
150    }
151}
152
153impl Default for Hash64 {
154    fn default() -> Self {
155        Self::new()
156    }
157}
158
159impl Hasher for Hash64 {
160    fn finish(&self) -> u64 {
161        self.digest()
162    }
163
164    fn write(&mut self, bytes: &[u8]) {
165        self.bytes(bytes);
166    }
167
168    fn write_u8(&mut self, value: u8) {
169        self.u8(value);
170    }
171
172    fn write_u16(&mut self, value: u16) {
173        self.u16(value);
174    }
175
176    fn write_u32(&mut self, value: u32) {
177        self.u32(value);
178    }
179
180    fn write_u64(&mut self, value: u64) {
181        self.u64(value);
182    }
183
184    fn write_u128(&mut self, value: u128) {
185        self.u128(value);
186    }
187
188    fn write_usize(&mut self, value: usize) {
189        self.usize(value);
190    }
191
192    fn write_i8(&mut self, value: i8) {
193        self.i8(value);
194    }
195
196    fn write_i16(&mut self, value: i16) {
197        self.i16(value);
198    }
199
200    fn write_i32(&mut self, value: i32) {
201        self.i32(value);
202    }
203
204    fn write_i64(&mut self, value: i64) {
205        self.i64(value);
206    }
207
208    fn write_i128(&mut self, value: i128) {
209        self.u128(value as u128);
210    }
211
212    fn write_isize(&mut self, value: isize) {
213        self.isize(value);
214    }
215}
216
217#[cfg(test)]
218mod tests {
219    use super::*;
220
221    #[test]
222    fn the_published_fnv1a_vectors_hold() {
223        // The FNV reference vectors, and the empty digest that is the basis.
224        assert_eq!(fnv1a64(b""), 0xCBF2_9CE4_8422_2325);
225        assert_eq!(fnv1a64(b"a"), 0xAF63_DC4C_8601_EC8C);
226        assert_eq!(fnv1a64(b"foobar"), 0x8594_4171_F739_67E8);
227        // The one the engine itself depends on: `WorldSeed::named("loot")`.
228        assert_eq!(fnv1a64(b"loot"), 0xCDEC_E8AD_70D5_84B7);
229    }
230
231    #[test]
232    fn streaming_agrees_with_the_one_shot_hash() {
233        for bytes in [b"".as_slice(), b"a", b"loot", b"repame-sim"] {
234            let mut hash = Hash64::new();
235            hash.bytes(bytes);
236            assert_eq!(hash.digest(), fnv1a64(bytes), "{bytes:?}");
237        }
238    }
239
240    #[test]
241    fn a_written_integer_equals_its_little_endian_bytes() {
242        let mut by_value = Hash64::new();
243        by_value.u32(0x0403_0201);
244        by_value.u8(0x05);
245        let mut by_bytes = Hash64::new();
246        by_bytes.bytes(&[0x01, 0x02, 0x03, 0x04, 0x05]);
247        assert_eq!(by_value.digest(), by_bytes.digest());
248
249        let mut wide = Hash64::new();
250        wide.u64(u64::MAX);
251        let mut wide_bytes = Hash64::new();
252        wide_bytes.bytes(&[0xFF; 8]);
253        assert_eq!(wide.digest(), wide_bytes.digest());
254    }
255
256    #[test]
257    fn lengths_prefix_and_signs_keep_their_bits() {
258        // "ab" must not fold like "a" followed by "b" with no separator.
259        let mut joined = Hash64::new();
260        joined.str("ab");
261        let mut split = Hash64::new();
262        split.str("a");
263        split.str("b");
264        assert_ne!(joined.digest(), split.digest());
265
266        let mut signed = Hash64::new();
267        signed.i32(-1);
268        let mut unsigned = Hash64::new();
269        unsigned.u32(u32::MAX);
270        assert_eq!(signed.digest(), unsigned.digest());
271
272        let mut plus_zero = Hash64::new();
273        plus_zero.f32(0.0);
274        let mut minus_zero = Hash64::new();
275        minus_zero.f32(-0.0);
276        assert_ne!(plus_zero.digest(), minus_zero.digest(), "bits, not values");
277    }
278
279    #[test]
280    fn the_hasher_path_matches_the_write_methods() {
281        use std::hash::Hash;
282
283        let mut through_hash = Hash64::new();
284        7u32.hash(&mut through_hash);
285        true.hash(&mut through_hash);
286        (-3i64).hash(&mut through_hash);
287
288        let mut through_writes = Hash64::new();
289        through_writes.u32(7);
290        through_writes.bool(true);
291        through_writes.i64(-3);
292        assert_eq!(through_hash.digest(), through_writes.digest());
293    }
294
295    #[test]
296    fn a_digest_is_the_same_in_the_next_run() {
297        // No per-process seed: two hashers folded the same way agree, and a
298        // std `DefaultHasher` comparison is deliberately absent here.
299        let mut first = Hash64::new();
300        first.str("repame-sim");
301        let mut second = Hash64::new();
302        second.str("repame-sim");
303        assert_eq!(first.digest(), second.digest());
304        assert_eq!(first, second);
305        assert_eq!(Hash64::default().digest(), fnv1a64(b""));
306    }
307}
repame_sim/hash.rs

repame_sim/
hash.rs
