shuyi_core/
hash.rs

1//! A hash of a game's state, the same on every platform and every run: what
2//! a replay compares step by step to find where two runs part, and what
3//! two machines playing one game can exchange to find a desync.
4//!
5//! [`state_hash`] feeds any [`Serialize`] value to a 64-bit FNV-1a hash in
6//! a fixed form of this file's own: every value is a tag byte and its
7//! bytes, integers little-endian at a fixed width, strings and byte
8//! strings with their length, sequences, maps and structs closed by an end
9//! byte, variants by their index. So the form never depends on a
10//! dependency's version or on the platform, and two different values of
11//! one type never have the same form. Field and type names are left out:
12//! renaming a field keeps a state's hash; reordering fields changes it.
13//!
14//! A state hashes the same each run only if it serializes the same: its
15//! maps must be ordered (`BTreeMap`), never a hash map whose order changes
16//! from run to run.
17
18use alloc::string::{String, ToString};
19use core::fmt;
20
21use serde::Serialize;
22use serde::ser::{self, Serializer};
23
24/// The 64-bit FNV-1a offset basis.
25const FNV_OFFSET: u64 = 0xcbf2_9ce4_8422_2325;
26
27/// The 64-bit FNV-1a prime.
28const FNV_PRIME: u64 = 0x0000_0100_0000_01b3;
29
30/// The hash of a state ([`state_hash`]).
31#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
32pub struct StateHash(pub u64);
33
34impl fmt::Display for StateHash {
35    /// Sixteen lowercase hex digits.
36    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
37        write!(f, "{:016x}", self.0)
38    }
39}
40
41/// Why a state could not be hashed: its own `Serialize` refused, with this
42/// message.
43#[derive(Debug, Clone, PartialEq, Eq)]
44pub struct HashError(pub String);
45
46impl fmt::Display for HashError {
47    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
48        write!(f, "the state could not be hashed: {}", self.0)
49    }
50}
51
52impl ser::StdError for HashError {}
53
54impl ser::Error for HashError {
55    fn custom<T: fmt::Display>(msg: T) -> Self {
56        Self(msg.to_string())
57    }
58}
59
60/// The hash of `value` ([module docs](self)).
61pub fn state_hash<T: Serialize + ?Sized>(value: &T) -> Result<StateHash, HashError> {
62    let mut hasher = Hasher(FNV_OFFSET);
63    value.serialize(&mut hasher)?;
64    Ok(StateHash(hasher.0))
65}
66
67/// The tag bytes of the form, one per kind of value.
68mod tag {
69    pub const FALSE: u8 = 0x00;
70    pub const TRUE: u8 = 0x01;
71    pub const SIGNED: u8 = 0x02;
72    pub const UNSIGNED: u8 = 0x03;
73    pub const SIGNED_WIDE: u8 = 0x04;
74    pub const UNSIGNED_WIDE: u8 = 0x05;
75    pub const F32: u8 = 0x06;
76    pub const F64: u8 = 0x07;
77    pub const CHAR: u8 = 0x08;
78    pub const STR: u8 = 0x09;
79    pub const BYTES: u8 = 0x0a;
80    pub const NONE: u8 = 0x0b;
81    pub const SOME: u8 = 0x0c;
82    pub const UNIT: u8 = 0x0d;
83    pub const VARIANT: u8 = 0x0e;
84    pub const SEQ: u8 = 0x0f;
85    pub const MAP: u8 = 0x10;
86    pub const STRUCT: u8 = 0x11;
87    pub const END: u8 = 0x12;
88}
89
90/// The running FNV-1a hash, fed by serializing a value into it.
91struct Hasher(u64);
92
93impl Hasher {
94    fn bytes(&mut self, bytes: &[u8]) {
95        for &byte in bytes {
96            self.0 = (self.0 ^ u64::from(byte)).wrapping_mul(FNV_PRIME);
97        }
98    }
99
100    fn tag(&mut self, tag: u8) {
101        self.bytes(&[tag]);
102    }
103
104    /// A length or an index: as a `u64`, so it is the same on 32 and 64
105    /// bits.
106    fn count(&mut self, n: usize) {
107        self.bytes(&u64::try_from(n).unwrap_or(u64::MAX).to_le_bytes());
108    }
109
110    fn variant(&mut self, index: u32) {
111        self.tag(tag::VARIANT);
112        self.bytes(&index.to_le_bytes());
113    }
114}
115
116impl Serializer for &mut Hasher {
117    type Ok = ();
118    type Error = HashError;
119    type SerializeSeq = Self;
120    type SerializeTuple = Self;
121    type SerializeTupleStruct = Self;
122    type SerializeTupleVariant = Self;
123    type SerializeMap = Self;
124    type SerializeStruct = Self;
125    type SerializeStructVariant = Self;
126
127    fn serialize_bool(self, v: bool) -> Result<(), HashError> {
128        self.tag(if v { tag::TRUE } else { tag::FALSE });
129        Ok(())
130    }
131
132    fn serialize_i8(self, v: i8) -> Result<(), HashError> {
133        self.serialize_i64(i64::from(v))
134    }
135
136    fn serialize_i16(self, v: i16) -> Result<(), HashError> {
137        self.serialize_i64(i64::from(v))
138    }
139
140    fn serialize_i32(self, v: i32) -> Result<(), HashError> {
141        self.serialize_i64(i64::from(v))
142    }
143
144    fn serialize_i64(self, v: i64) -> Result<(), HashError> {
145        self.tag(tag::SIGNED);
146        self.bytes(&v.to_le_bytes());
147        Ok(())
148    }
149
150    fn serialize_i128(self, v: i128) -> Result<(), HashError> {
151        self.tag(tag::SIGNED_WIDE);
152        self.bytes(&v.to_le_bytes());
153        Ok(())
154    }
155
156    fn serialize_u8(self, v: u8) -> Result<(), HashError> {
157        self.serialize_u64(u64::from(v))
158    }
159
160    fn serialize_u16(self, v: u16) -> Result<(), HashError> {
161        self.serialize_u64(u64::from(v))
162    }
163
164    fn serialize_u32(self, v: u32) -> Result<(), HashError> {
165        self.serialize_u64(u64::from(v))
166    }
167
168    fn serialize_u64(self, v: u64) -> Result<(), HashError> {
169        self.tag(tag::UNSIGNED);
170        self.bytes(&v.to_le_bytes());
171        Ok(())
172    }
173
174    fn serialize_u128(self, v: u128) -> Result<(), HashError> {
175        self.tag(tag::UNSIGNED_WIDE);
176        self.bytes(&v.to_le_bytes());
177        Ok(())
178    }
179
180    /// By its bits: a state should hold no floats (ADR-0002), but one that
181    /// does still hashes the same for the same bits.
182    fn serialize_f32(self, v: f32) -> Result<(), HashError> {
183        self.tag(tag::F32);
184        self.bytes(&v.to_bits().to_le_bytes());
185        Ok(())
186    }
187
188    fn serialize_f64(self, v: f64) -> Result<(), HashError> {
189        self.tag(tag::F64);
190        self.bytes(&v.to_bits().to_le_bytes());
191        Ok(())
192    }
193
194    fn serialize_char(self, v: char) -> Result<(), HashError> {
195        self.tag(tag::CHAR);
196        self.bytes(&u32::from(v).to_le_bytes());
197        Ok(())
198    }
199
200    fn serialize_str(self, v: &str) -> Result<(), HashError> {
201        self.tag(tag::STR);
202        self.count(v.len());
203        self.bytes(v.as_bytes());
204        Ok(())
205    }
206
207    fn serialize_bytes(self, v: &[u8]) -> Result<(), HashError> {
208        self.tag(tag::BYTES);
209        self.count(v.len());
210        self.bytes(v);
211        Ok(())
212    }
213
214    fn serialize_none(self) -> Result<(), HashError> {
215        self.tag(tag::NONE);
216        Ok(())
217    }
218
219    fn serialize_some<T: Serialize + ?Sized>(self, value: &T) -> Result<(), HashError> {
220        self.tag(tag::SOME);
221        value.serialize(self)
222    }
223
224    fn serialize_unit(self) -> Result<(), HashError> {
225        self.tag(tag::UNIT);
226        Ok(())
227    }
228
229    fn serialize_unit_struct(self, _name: &'static str) -> Result<(), HashError> {
230        self.serialize_unit()
231    }
232
233    fn serialize_unit_variant(
234        self,
235        _name: &'static str,
236        index: u32,
237        _variant: &'static str,
238    ) -> Result<(), HashError> {
239        self.variant(index);
240        Ok(())
241    }
242
243    fn serialize_newtype_struct<T: Serialize + ?Sized>(
244        self,
245        _name: &'static str,
246        value: &T,
247    ) -> Result<(), HashError> {
248        value.serialize(self)
249    }
250
251    fn serialize_newtype_variant<T: Serialize + ?Sized>(
252        self,
253        _name: &'static str,
254        index: u32,
255        _variant: &'static str,
256        value: &T,
257    ) -> Result<(), HashError> {
258        self.variant(index);
259        value.serialize(self)
260    }
261
262    fn serialize_seq(self, _len: Option<usize>) -> Result<Self, HashError> {
263        self.tag(tag::SEQ);
264        Ok(self)
265    }
266
267    fn serialize_tuple(self, len: usize) -> Result<Self, HashError> {
268        self.serialize_seq(Some(len))
269    }
270
271    fn serialize_tuple_struct(self, _name: &'static str, len: usize) -> Result<Self, HashError> {
272        self.serialize_seq(Some(len))
273    }
274
275    fn serialize_tuple_variant(
276        self,
277        _name: &'static str,
278        index: u32,
279        _variant: &'static str,
280        len: usize,
281    ) -> Result<Self, HashError> {
282        self.variant(index);
283        self.serialize_seq(Some(len))
284    }
285
286    fn serialize_map(self, _len: Option<usize>) -> Result<Self, HashError> {
287        self.tag(tag::MAP);
288        Ok(self)
289    }
290
291    fn serialize_struct(self, _name: &'static str, _len: usize) -> Result<Self, HashError> {
292        self.tag(tag::STRUCT);
293        Ok(self)
294    }
295
296    fn serialize_struct_variant(
297        self,
298        _name: &'static str,
299        index: u32,
300        _variant: &'static str,
301        _len: usize,
302    ) -> Result<Self, HashError> {
303        self.variant(index);
304        self.tag(tag::STRUCT);
305        Ok(self)
306    }
307
308    fn collect_str<T: fmt::Display + ?Sized>(self, value: &T) -> Result<(), HashError> {
309        self.serialize_str(&value.to_string())
310    }
311
312    fn is_human_readable(&self) -> bool {
313        false
314    }
315}
316
317impl ser::SerializeSeq for &mut Hasher {
318    type Ok = ();
319    type Error = HashError;
320
321    fn serialize_element<T: Serialize + ?Sized>(&mut self, value: &T) -> Result<(), HashError> {
322        value.serialize(&mut **self)
323    }
324
325    fn end(self) -> Result<(), HashError> {
326        self.tag(tag::END);
327        Ok(())
328    }
329}
330
331impl ser::SerializeTuple for &mut Hasher {
332    type Ok = ();
333    type Error = HashError;
334
335    fn serialize_element<T: Serialize + ?Sized>(&mut self, value: &T) -> Result<(), HashError> {
336        value.serialize(&mut **self)
337    }
338
339    fn end(self) -> Result<(), HashError> {
340        self.tag(tag::END);
341        Ok(())
342    }
343}
344
345impl ser::SerializeTupleStruct for &mut Hasher {
346    type Ok = ();
347    type Error = HashError;
348
349    fn serialize_field<T: Serialize + ?Sized>(&mut self, value: &T) -> Result<(), HashError> {
350        value.serialize(&mut **self)
351    }
352
353    fn end(self) -> Result<(), HashError> {
354        self.tag(tag::END);
355        Ok(())
356    }
357}
358
359impl ser::SerializeTupleVariant for &mut Hasher {
360    type Ok = ();
361    type Error = HashError;
362
363    fn serialize_field<T: Serialize + ?Sized>(&mut self, value: &T) -> Result<(), HashError> {
364        value.serialize(&mut **self)
365    }
366
367    fn end(self) -> Result<(), HashError> {
368        self.tag(tag::END);
369        Ok(())
370    }
371}
372
373impl ser::SerializeMap for &mut Hasher {
374    type Ok = ();
375    type Error = HashError;
376
377    fn serialize_key<T: Serialize + ?Sized>(&mut self, key: &T) -> Result<(), HashError> {
378        key.serialize(&mut **self)
379    }
380
381    fn serialize_value<T: Serialize + ?Sized>(&mut self, value: &T) -> Result<(), HashError> {
382        value.serialize(&mut **self)
383    }
384
385    fn end(self) -> Result<(), HashError> {
386        self.tag(tag::END);
387        Ok(())
388    }
389}
390
391impl ser::SerializeStruct for &mut Hasher {
392    type Ok = ();
393    type Error = HashError;
394
395    fn serialize_field<T: Serialize + ?Sized>(
396        &mut self,
397        _key: &'static str,
398        value: &T,
399    ) -> Result<(), HashError> {
400        value.serialize(&mut **self)
401    }
402
403    fn end(self) -> Result<(), HashError> {
404        self.tag(tag::END);
405        Ok(())
406    }
407}
408
409impl ser::SerializeStructVariant for &mut Hasher {
410    type Ok = ();
411    type Error = HashError;
412
413    fn serialize_field<T: Serialize + ?Sized>(
414        &mut self,
415        _key: &'static str,
416        value: &T,
417    ) -> Result<(), HashError> {
418        value.serialize(&mut **self)
419    }
420
421    fn end(self) -> Result<(), HashError> {
422        self.tag(tag::END);
423        Ok(())
424    }
425}
426
427#[cfg(test)]
428mod tests;
shuyi_core/hash.rs

shuyi_core/
hash.rs
