loam_time/
replay.rs

1use std::fmt;
2
3use thiserror::Error;
4
5// FNV-1a 64 (Fowler/Noll/Vo 1991, <http://www.isthe.com/chongo/tech/comp/fnv/>).
6const FNV_OFFSET_BASIS: u64 = 0xcbf2_9ce4_8422_2325;
7const FNV_PRIME: u64 = 0x0000_0100_0000_01b3;
8
9/// FNV-1a over unframed little-endian words; callers own the sampled state schema.
10#[derive(Clone, Copy, Debug, PartialEq, Eq)]
11pub struct StateHash(u64);
12
13impl Default for StateHash {
14    fn default() -> Self {
15        Self::new()
16    }
17}
18
19impl StateHash {
20    pub fn new() -> Self {
21        Self(FNV_OFFSET_BASIS)
22    }
23
24    fn write_bytes(&mut self, bytes: &[u8]) {
25        for &byte in bytes {
26            self.0 ^= byte as u64;
27            self.0 = self.0.wrapping_mul(FNV_PRIME);
28        }
29    }
30
31    pub fn write_u32(&mut self, word: u32) {
32        self.write_bytes(&word.to_le_bytes());
33    }
34
35    pub fn write_u32s(&mut self, words: &[u32]) {
36        for &word in words {
37            self.write_u32(word);
38        }
39    }
40
41    pub fn write_u64(&mut self, value: u64) {
42        self.write_bytes(&value.to_le_bytes());
43    }
44
45    /// Preserves signed zero and NaN payload bits.
46    pub fn write_f32(&mut self, value: f32) {
47        self.write_u32(value.to_bits());
48    }
49
50    pub fn finish(&self) -> u64 {
51        self.0
52    }
53}
54
55pub const TAPE_MAGIC: [u8; 8] = *b"LOAMTAPE";
56
57/// Version of the tape container, independent of the game's input and state schemas.
58pub const TAPE_FORMAT_VERSION: u32 = 1;
59
60// Tape v1 header: magic, version, hz, seed, words_per_tick, ticks, checkpoint count.
61const HEADER_LEN: usize = 8 + 4 + 4 + 8 + 4 + 8 + 4;
62const CHECKPOINT_LEN: usize = 16;
63
64/// A state hash observed after `tick` completed.
65#[derive(Clone, Copy, Debug, PartialEq, Eq)]
66pub struct Checkpoint {
67    pub tick: u64,
68    pub state_hash: u64,
69}
70
71#[derive(Debug, Error, PartialEq, Eq)]
72pub enum TapeError {
73    #[error("not a loam tape: leading bytes are {found:02x?}")]
74    BadMagic { found: [u8; 8] },
75    #[error("tape format version {found}, this build reads {TAPE_FORMAT_VERSION}")]
76    UnsupportedVersion { found: u32 },
77    #[error("tape declares {expected} bytes, got {found}")]
78    LengthMismatch { expected: u64, found: usize },
79    #[error("checkpoint ticks are not strictly ascending at index {index}")]
80    CheckpointOrder { index: usize },
81}
82
83/// `words_per_tick` may be zero.
84#[derive(Clone, Debug, PartialEq, Eq)]
85pub struct Tape {
86    tick_hz: u32,
87    seed: u64,
88    words_per_tick: u32,
89    ticks: u64,
90    inputs: Vec<u32>,
91    checkpoints: Vec<Checkpoint>,
92}
93
94impl Tape {
95    pub fn new(tick_hz: u32, seed: u64, words_per_tick: u32) -> Self {
96        Self {
97            tick_hz,
98            seed,
99            words_per_tick,
100            ticks: 0,
101            inputs: Vec::new(),
102            checkpoints: Vec::new(),
103        }
104    }
105
106    pub fn tick_hz(&self) -> u32 {
107        self.tick_hz
108    }
109
110    pub fn seed(&self) -> u64 {
111        self.seed
112    }
113
114    pub fn words_per_tick(&self) -> u32 {
115        self.words_per_tick
116    }
117
118    pub fn ticks(&self) -> u64 {
119        self.ticks
120    }
121
122    /// Panics if `input.len()` is not `words_per_tick`.
123    pub fn push_tick(&mut self, input: &[u32]) {
124        assert_eq!(
125            input.len(),
126            self.words_per_tick as usize,
127            "tape frame is {} words",
128            self.words_per_tick,
129        );
130        self.inputs.extend_from_slice(input);
131        self.ticks += 1;
132    }
133
134    pub fn input(&self, tick: u64) -> Option<&[u32]> {
135        if tick >= self.ticks {
136            return None;
137        }
138        let width = self.words_per_tick as usize;
139        let start = tick as usize * width;
140        Some(&self.inputs[start..start + width])
141    }
142
143    /// Panics unless `tick` is past the last checkpoint.
144    pub fn checkpoint(&mut self, tick: u64, state_hash: u64) {
145        if let Some(last) = self.checkpoints.last() {
146            assert!(
147                tick > last.tick,
148                "checkpoint ticks must ascend: {tick} after {}",
149                last.tick,
150            );
151        }
152        self.checkpoints.push(Checkpoint { tick, state_hash });
153    }
154
155    pub fn checkpoints(&self) -> &[Checkpoint] {
156        &self.checkpoints
157    }
158
159    pub fn encode(&self) -> Vec<u8> {
160        let mut bytes = Vec::with_capacity(
161            HEADER_LEN + self.inputs.len() * 4 + self.checkpoints.len() * CHECKPOINT_LEN,
162        );
163        bytes.extend_from_slice(&TAPE_MAGIC);
164        bytes.extend_from_slice(&TAPE_FORMAT_VERSION.to_le_bytes());
165        bytes.extend_from_slice(&self.tick_hz.to_le_bytes());
166        bytes.extend_from_slice(&self.seed.to_le_bytes());
167        bytes.extend_from_slice(&self.words_per_tick.to_le_bytes());
168        bytes.extend_from_slice(&self.ticks.to_le_bytes());
169        bytes.extend_from_slice(&(self.checkpoints.len() as u32).to_le_bytes());
170        for &word in &self.inputs {
171            bytes.extend_from_slice(&word.to_le_bytes());
172        }
173        for checkpoint in &self.checkpoints {
174            bytes.extend_from_slice(&checkpoint.tick.to_le_bytes());
175            bytes.extend_from_slice(&checkpoint.state_hash.to_le_bytes());
176        }
177        bytes
178    }
179
180    pub fn decode(bytes: &[u8]) -> Result<Self, TapeError> {
181        let mut reader = Reader::new(bytes);
182        let magic = reader.take::<8>().ok_or(TapeError::LengthMismatch {
183            expected: HEADER_LEN as u64,
184            found: bytes.len(),
185        })?;
186        if magic != TAPE_MAGIC {
187            return Err(TapeError::BadMagic { found: magic });
188        }
189        let version = reader.u32().ok_or(TapeError::LengthMismatch {
190            expected: HEADER_LEN as u64,
191            found: bytes.len(),
192        })?;
193        if version != TAPE_FORMAT_VERSION {
194            return Err(TapeError::UnsupportedVersion { found: version });
195        }
196        let (tick_hz, seed, words_per_tick, ticks, checkpoint_count) =
197            reader.header_tail().ok_or(TapeError::LengthMismatch {
198                expected: HEADER_LEN as u64,
199                found: bytes.len(),
200            })?;
201
202        let input_bytes = u64::from(words_per_tick)
203            .saturating_mul(ticks)
204            .saturating_mul(4);
205        let expected = (HEADER_LEN as u64)
206            .saturating_add(input_bytes)
207            .saturating_add(u64::from(checkpoint_count) * CHECKPOINT_LEN as u64);
208        if expected != bytes.len() as u64 {
209            return Err(TapeError::LengthMismatch {
210                expected,
211                found: bytes.len(),
212            });
213        }
214
215        let word_count = (input_bytes / 4) as usize;
216        let mut inputs = Vec::with_capacity(word_count);
217        for _ in 0..word_count {
218            inputs.push(reader.u32().ok_or(TapeError::LengthMismatch {
219                expected,
220                found: bytes.len(),
221            })?);
222        }
223        let mut checkpoints = Vec::with_capacity(checkpoint_count as usize);
224        for index in 0..checkpoint_count as usize {
225            let tick = reader.u64().ok_or(TapeError::LengthMismatch {
226                expected,
227                found: bytes.len(),
228            })?;
229            let state_hash = reader.u64().ok_or(TapeError::LengthMismatch {
230                expected,
231                found: bytes.len(),
232            })?;
233            if let Some(last) = checkpoints.last() {
234                let Checkpoint { tick: prev, .. } = *last;
235                if tick <= prev {
236                    return Err(TapeError::CheckpointOrder { index });
237                }
238            }
239            checkpoints.push(Checkpoint { tick, state_hash });
240        }
241
242        Ok(Self {
243            tick_hz,
244            seed,
245            words_per_tick,
246            ticks,
247            inputs,
248            checkpoints,
249        })
250    }
251}
252
253impl fmt::Display for Tape {
254    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
255        write!(
256            f,
257            "tape v{TAPE_FORMAT_VERSION}: {} ticks at {}Hz, seed {:#018x}, \
258             {} input words/tick, {} checkpoints",
259            self.ticks,
260            self.tick_hz,
261            self.seed,
262            self.words_per_tick,
263            self.checkpoints.len(),
264        )
265    }
266}
267
268struct Reader<'a> {
269    bytes: &'a [u8],
270}
271
272impl<'a> Reader<'a> {
273    fn new(bytes: &'a [u8]) -> Self {
274        Self { bytes }
275    }
276
277    fn take<const N: usize>(&mut self) -> Option<[u8; N]> {
278        let (value, remaining) = self.bytes.split_first_chunk::<N>()?;
279        self.bytes = remaining;
280        Some(*value)
281    }
282
283    fn u32(&mut self) -> Option<u32> {
284        self.take::<4>().map(u32::from_le_bytes)
285    }
286
287    fn u64(&mut self) -> Option<u64> {
288        self.take::<8>().map(u64::from_le_bytes)
289    }
290
291    fn header_tail(&mut self) -> Option<(u32, u64, u32, u64, u32)> {
292        Some((
293            self.u32()?,
294            self.u64()?,
295            self.u32()?,
296            self.u64()?,
297            self.u32()?,
298        ))
299    }
300}
301
302#[cfg(test)]
303mod tests {
304    use super::*;
305
306    fn recorded() -> Tape {
307        let mut tape = Tape::new(60, 0x1234_5678_9abc_def0, 3);
308        for tick in 0..8u64 {
309            let t = tick as u32;
310            tape.push_tick(&[t, t.wrapping_mul(7), (1.5f32 * t as f32).to_bits()]);
311        }
312        tape.checkpoint(3, 0xdead_beef_0000_0001);
313        tape.checkpoint(7, 0xdead_beef_0000_0002);
314        tape
315    }
316
317    #[test]
318    fn hash_detects_word_order_and_bit_changes() {
319        let mut ab = StateHash::new();
320        ab.write_u32(1);
321        ab.write_u32(2);
322        let mut ba = StateHash::new();
323        ba.write_u32(2);
324        ba.write_u32(1);
325        assert_ne!(ab.finish(), ba.finish(), "swapped operands must be visible");
326
327        let mut low = StateHash::new();
328        low.write_u32s(&[7, 7, 7, 7]);
329        let mut flipped = StateHash::new();
330        flipped.write_u32s(&[7, 7, 7 ^ 1, 7]);
331        assert_ne!(low.finish(), flipped.finish());
332    }
333
334    #[test]
335    fn hash_uses_little_endian_words() {
336        let mut split = StateHash::new();
337        split.write_u32(0);
338        split.write_u32(1);
339        let mut whole = StateHash::new();
340        whole.write_u64(1 << 32);
341        assert_eq!(split.finish(), whole.finish());
342    }
343
344    #[test]
345    fn hash_preserves_signed_zero_and_nan_payloads() {
346        for (a, b) in [(0x0000_0000, 0x8000_0000), (0x7fc0_0001, 0x7fc0_0002)] {
347            let mut first = StateHash::new();
348            first.write_f32(f32::from_bits(a));
349            let mut second = StateHash::new();
350            second.write_f32(f32::from_bits(b));
351            assert_ne!(first.finish(), second.finish());
352        }
353    }
354
355    #[test]
356    fn encoded_tape_preserves_fields() {
357        let tape = recorded();
358        let decoded = Tape::decode(&tape.encode()).expect("own encoding decodes");
359        assert_eq!(decoded, tape);
360    }
361
362    #[test]
363    fn input_ends_at_tick_count() {
364        let tape = recorded();
365        assert_eq!(tape.ticks(), 8);
366        assert_eq!(tape.input(0), Some(&[0u32, 0, 0.0f32.to_bits()][..]));
367        assert_eq!(tape.input(5).map(|w| w[1]), Some(35));
368        assert_eq!(tape.input(8), None, "one past the last tick has no input");
369    }
370
371    #[test]
372    fn zero_width_tape_preserves_ticks() {
373        let mut tape = Tape::new(120, 7, 0);
374        for _ in 0..4 {
375            tape.push_tick(&[]);
376        }
377        tape.checkpoint(3, 0xabc);
378        let decoded = Tape::decode(&tape.encode()).expect("width-zero tape decodes");
379        assert_eq!(decoded.ticks(), 4);
380        assert_eq!(decoded.input(0), Some(&[][..]));
381        assert_eq!(decoded.checkpoints(), tape.checkpoints());
382    }
383
384    #[test]
385    fn future_container_version_is_rejected() {
386        let mut bytes = recorded().encode();
387        let bumped = TAPE_FORMAT_VERSION + 1;
388        bytes[8..12].copy_from_slice(&bumped.to_le_bytes());
389        assert_eq!(
390            Tape::decode(&bytes),
391            Err(TapeError::UnsupportedVersion { found: bumped }),
392        );
393    }
394
395    #[test]
396    fn bad_magic_and_empty_tapes_are_rejected() {
397        let mut bytes = recorded().encode();
398        bytes[0] = b'X';
399        let mut found = TAPE_MAGIC;
400        found[0] = b'X';
401        assert_eq!(Tape::decode(&bytes), Err(TapeError::BadMagic { found }));
402        assert!(matches!(
403            Tape::decode(&[]),
404            Err(TapeError::LengthMismatch { .. }),
405        ));
406    }
407
408    #[test]
409    fn truncated_and_padded_payloads_are_rejected() {
410        let full = recorded().encode();
411        let expected = full.len() as u64;
412        assert_eq!(
413            Tape::decode(&full[..full.len() - 1]),
414            Err(TapeError::LengthMismatch {
415                expected,
416                found: full.len() - 1,
417            }),
418        );
419
420        let mut padded = full.clone();
421        padded.push(0);
422        assert_eq!(
423            Tape::decode(&padded),
424            Err(TapeError::LengthMismatch {
425                expected,
426                found: padded.len(),
427            }),
428            "trailing bytes mean the writer and the reader disagree",
429        );
430    }
431
432    #[test]
433    fn oversized_input_width_is_rejected() {
434        let mut bytes = recorded().encode();
435        bytes[24..28].copy_from_slice(&u32::MAX.to_le_bytes());
436        assert!(matches!(
437            Tape::decode(&bytes),
438            Err(TapeError::LengthMismatch { .. }),
439        ));
440    }
441
442    #[test]
443    fn overflowing_tick_count_is_rejected() {
444        let mut bytes = recorded().encode();
445        bytes[28..36].copy_from_slice(&u64::MAX.to_le_bytes());
446        assert!(matches!(
447            Tape::decode(&bytes),
448            Err(TapeError::LengthMismatch { .. }),
449        ));
450    }
451
452    #[test]
453    fn decoded_checkpoints_must_ascend() {
454        let mut tape = recorded();
455        tape.checkpoints[1].tick = 3;
456        assert_eq!(
457            Tape::decode(&tape.encode()),
458            Err(TapeError::CheckpointOrder { index: 1 }),
459        );
460    }
461
462    #[test]
463    #[should_panic(expected = "tape frame is 3 words")]
464    fn short_input_cannot_shift_tick_boundaries() {
465        let mut tape = Tape::new(60, 0, 3);
466        tape.push_tick(&[1, 2]);
467    }
468
469    #[test]
470    #[should_panic(expected = "checkpoint ticks must ascend")]
471    fn writer_rejects_duplicate_checkpoint_ticks() {
472        let mut tape = Tape::new(60, 0, 0);
473        tape.checkpoint(5, 1);
474        tape.checkpoint(5, 2);
475    }
476}
loam_time/replay.rs

loam_time/
replay.rs
