jevsnes.git / packages / replay / src / keyframe.rs
keyframe.rsannotatedkeyframe.rssource120 lines · 4.8 KB · raw

Compressing one console snapshot (console::Console::snapshot_fixed, 1.3 MB) against a reference, usually the previous keyframe of its tier (crate::keyframes): XOR the two, then zstd the result.

XOR turns every byte the snapshot did not change into zero, so the input to zstd is mostly zero runs with scattered pockets of change, which is what zstd compresses best. A keyframe with no reference is XORed against nothing (the bytes themselves), and zstd alone then finds the state's own redundancy: long zero regions, repeated tiles.

The XOR is only as good as the alignment. It pairs byte i with byte i, so a snapshot whose fields moved relative to its reference deltas badly. That is why keyframes are snapshot_fixed: varint snapshots came in 70 lengths across 83 keyframes, and 2 s deltas averaged 866 KB of 1.31 MB (apps/replay-probe, 2026-09-22). zstd limits that damage too, where the hand-rolled run-length coder this replaced could not.

The zstd is ruzstd (pure Rust), whose encoder implements only its fastest level. third-party/rust/Cargo.toml says why that crate.

21use std::io::{self, Read};

23use ruzstd::decoding::StreamingDecoder;
24use ruzstd::encoding::{CompressionLevel, compress_to_vec};

data XORed against reference byte for byte, where reference is shorter than data (or absent) its missing bytes count as zero.

28fn xor(reference: Option<&[u8]>, data: &[u8]) -> Vec<u8> {
29    let reference = reference.unwrap_or(&[]);
30    data.iter().enumerate().map(|(i, &b)| b ^ reference.get(i).copied().unwrap_or(0)).collect()
31}

data compressed against reference. [decompress] needs the exact same reference and data.len() back.

35pub fn compress(reference: Option<&[u8]>, data: &[u8]) -> Vec<u8> {
36    compress_to_vec(xor(reference, data).as_slice(), CompressionLevel::Fastest)
37}

The inverse of [compress]. len is the original snapshot's length; a stream that decodes to anything else is corrupt and is refused rather than handed on as a machine.

42pub fn decompress(reference: Option<&[u8]>, compressed: &[u8], len: usize) -> io::Result<Vec<u8>> {
43    let mut source = compressed;
44    let mut decoder = StreamingDecoder::new(&mut source).map_err(|e| io::Error::new(io::ErrorKind::InvalidData, e.to_string()))?;
45    let mut xored = Vec::with_capacity(len);
46    decoder.read_to_end(&mut xored)?;
47    if xored.len() != len {
48        return Err(io::Error::new(
49            io::ErrorKind::InvalidData,
50            format!("keyframe decodes to {} bytes, expected {len}", xored.len()),
51        ));
52    }
53    Ok(xor(reference, &xored))
54}

56#[cfg(test)]
57mod tests {
58    use super::*;
59
60    fn roundtrip(reference: Option<&[u8]>, data: &[u8]) {
61        let compressed = compress(reference, data);
62        let back = decompress(reference, &compressed, data.len()).unwrap();
63        assert_eq!(back, data, "roundtrip with reference of len {:?}", reference.map(<[u8]>::len));
64    }
65
66    #[test]
67    fn empty_data_round_trips() {
68        roundtrip(None, &[]);
69        roundtrip(Some(&[1, 2, 3]), &[]);
70    }
71
72    #[test]
73    fn identical_to_reference_compresses_to_almost_nothing() {
74        let data: Vec<u8> = (0..100_000u32).map(|i| (i * 31 % 251) as u8).collect();
75        let compressed = compress(Some(&data), &data);
76        assert!(compressed.len() < 200, "all-zero XOR should be tiny, got {}", compressed.len());
77        assert_eq!(decompress(Some(&data), &compressed, data.len()).unwrap(), data);
78    }
79
80    #[test]
81    fn no_reference_still_round_trips() {
82        let data: Vec<u8> = (0..2000).map(|i| (i * 37 % 251) as u8).collect();
83        roundtrip(None, &data);
84    }
85
86    #[test]
87    fn a_reference_of_a_different_length_still_round_trips() {
88        let reference = vec![5u8; 40];
89        let data: Vec<u8> = (0..300).map(|i| (i % 17) as u8).collect();
90        roundtrip(Some(&reference), &data);
91        roundtrip(Some(&data), &reference);
92    }
93
94    #[test]
95    fn scattered_changes_compress_well() {
96        // The shape of a live console against its keyframe 2 s earlier:
97        // mostly unchanged, with isolated changed bytes.
98        let n = 100_000;
99        let reference: Vec<u8> = (0..n).map(|i| (i * 7 % 251) as u8).collect();
100        let mut data = reference.clone();
101        for i in (0..data.len()).step_by(40) {
102            data[i] ^= 1;
103        }
104        roundtrip(Some(&reference), &data);
105        let compressed = compress(Some(&reference), &data);
106        assert!(compressed.len() < n / 10, "compressed {} vs raw {n}", compressed.len());
107    }
108
109    #[test]
110    fn a_wrong_length_is_refused() {
111        let data = vec![3u8; 500];
112        let compressed = compress(None, &data);
113        assert!(decompress(None, &compressed, 499).is_err());
114    }
115
116    #[test]
117    fn garbage_is_refused_not_decoded() {
118        assert!(decompress(None, &[1, 2, 3, 4, 5, 6, 7, 8], 8).is_err());
119    }
120}