hidane_core/export/
log.rs

1//! The LevelDB log format the export files are written in.
2//!
3//! A file is a sequence of 32 KiB blocks. Each record is stored as one or more fragments, each
4//! with a 7-byte header: the masked CRC-32C of the fragment's type and data (4 bytes, little
5//! endian), the data length (2 bytes, little endian) and the type: FULL (1), or FIRST (2),
6//! MIDDLE (3) and LAST (4) for a record split across blocks. A fragment never crosses a block
7//! boundary; a block's last 1 to 6 bytes, too few for a header, are zeros.
8
9use std::{
10    borrow::Cow,
11    fmt,
12    io::{self, Write},
13};
14
15const BLOCK: usize = 32 * 1024;
16const HEADER: usize = 7;
17
18const FULL: u8 = 1;
19const FIRST: u8 = 2;
20const MIDDLE: u8 = 3;
21const LAST: u8 = 4;
22
23/// CRC-32C (Castagnoli), as LevelDB checksums its records.
24pub fn crc32c(data: &[u8]) -> u32 {
25    crc32c_extend(0, data)
26}
27
28fn crc32c_extend(crc: u32, data: &[u8]) -> u32 {
29    const TABLE: [u32; 256] = {
30        let mut table = [0u32; 256];
31        let mut i = 0;
32        while i < 256 {
33            #[allow(clippy::cast_possible_truncation)]
34            let mut crc = i as u32;
35            let mut bit = 0;
36            while bit < 8 {
37                crc = if crc & 1 == 1 {
38                    (crc >> 1) ^ 0x82F6_3B78
39                } else {
40                    crc >> 1
41                };
42                bit += 1;
43            }
44            table[i] = crc;
45            i += 1;
46        }
47        table
48    };
49    let mut crc = !crc;
50    for &byte in data {
51        crc = TABLE[((crc ^ u32::from(byte)) & 0xff) as usize] ^ (crc >> 8);
52    }
53    !crc
54}
55
56/// LevelDB stores checksums masked, so that a checksum of data holding checksums stays useful.
57fn mask(crc: u32) -> u32 {
58    crc.rotate_right(15).wrapping_add(0xa282_ead8)
59}
60
61fn checksum(kind: u8, data: &[u8]) -> u32 {
62    mask(crc32c_extend(crc32c(&[kind]), data))
63}
64
65/// Writes records to `out`, splitting them across blocks as LevelDB does.
66pub struct Writer<W: Write> {
67    out: W,
68    /// Bytes already written in the current block.
69    offset: usize,
70    written: u64,
71}
72
73impl<W: Write> Writer<W> {
74    pub fn new(out: W) -> Self {
75        Self {
76            out,
77            offset: 0,
78            written: 0,
79        }
80    }
81
82    /// Bytes written so far.
83    pub fn len(&self) -> u64 {
84        self.written
85    }
86
87    pub fn is_empty(&self) -> bool {
88        self.written == 0
89    }
90
91    pub fn add_record(&mut self, mut data: &[u8]) -> io::Result<()> {
92        let mut first = true;
93        loop {
94            let left = BLOCK - self.offset;
95            if left < HEADER {
96                self.emit(&[0; HEADER][..left])?;
97                self.offset = 0;
98            }
99            let room = BLOCK - self.offset - HEADER;
100            let len = data.len().min(room);
101            let last = len == data.len();
102            let kind = match (first, last) {
103                (true, true) => FULL,
104                (true, false) => FIRST,
105                (false, false) => MIDDLE,
106                (false, true) => LAST,
107            };
108            let (fragment, rest) = data.split_at(len);
109            let mut header = [0u8; HEADER];
110            header[..4].copy_from_slice(&checksum(kind, fragment).to_le_bytes());
111            #[allow(clippy::cast_possible_truncation)]
112            header[4..6].copy_from_slice(&(len as u16).to_le_bytes());
113            header[6] = kind;
114            self.emit(&header)?;
115            self.emit(fragment)?;
116            self.offset += HEADER + len;
117            data = rest;
118            first = false;
119            if last {
120                return Ok(());
121            }
122        }
123    }
124
125    fn emit(&mut self, bytes: &[u8]) -> io::Result<()> {
126        self.out.write_all(bytes)?;
127        self.written += bytes.len() as u64;
128        Ok(())
129    }
130
131    pub fn into_inner(self) -> W {
132        self.out
133    }
134}
135
136/// Encodes `records` as a log in memory.
137pub fn write_all<'a>(records: impl IntoIterator<Item = &'a [u8]>) -> Vec<u8> {
138    let mut writer = Writer::new(Vec::new());
139    for record in records {
140        writer
141            .add_record(record)
142            .expect("writing to a Vec cannot fail");
143    }
144    writer.into_inner()
145}
146
147/// Why a log could not be read. The messages are the official emulator's.
148#[derive(Debug, Clone, Copy, PartialEq, Eq)]
149pub enum LogError {
150    /// A fragment's checksum does not match its data.
151    Checksum,
152    /// A truncated or misplaced fragment.
153    Invalid,
154}
155
156impl fmt::Display for LogError {
157    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
158        f.write_str(match self {
159            Self::Checksum => "Checksum doesn't validate.",
160            Self::Invalid => "Invalid record",
161        })
162    }
163}
164
165impl std::error::Error for LogError {}
166
167/// The records of a log, in order. Stops after the first error.
168pub fn records(data: &[u8]) -> Records<'_> {
169    Records { data, pos: 0 }
170}
171
172pub struct Records<'a> {
173    data: &'a [u8],
174    pos: usize,
175}
176
177impl<'a> Records<'a> {
178    /// The next fragment, or `None` at the end of the data.
179    fn fragment(&mut self) -> Result<Option<(u8, &'a [u8])>, LogError> {
180        loop {
181            let left_in_block = BLOCK - self.pos % BLOCK;
182            let rest = &self.data[self.pos..];
183            if rest.is_empty() {
184                return Ok(None);
185            }
186            if left_in_block < HEADER || rest.len() < HEADER {
187                // A block's zero trailer; anything else is a cut-off header.
188                let trailer = left_in_block.min(rest.len());
189                if rest[..trailer].iter().any(|&b| b != 0) {
190                    return Err(LogError::Invalid);
191                }
192                self.pos += trailer;
193                continue;
194            }
195            let crc = u32::from_le_bytes(rest[..4].try_into().expect("four bytes"));
196            let len = usize::from(u16::from_le_bytes([rest[4], rest[5]]));
197            let kind = rest[6];
198            if HEADER + len > left_in_block || HEADER + len > rest.len() {
199                return Err(LogError::Invalid);
200            }
201            let data = &rest[HEADER..HEADER + len];
202            if kind == 0 && len == 0 && crc == 0 {
203                // Zeros up to the end of the block (a preallocated file).
204                self.pos += left_in_block.min(rest.len());
205                continue;
206            }
207            if crc != checksum(kind, data) {
208                return Err(LogError::Checksum);
209            }
210            self.pos += HEADER + len;
211            return Ok(Some((kind, data)));
212        }
213    }
214
215    fn record(&mut self) -> Result<Option<Cow<'a, [u8]>>, LogError> {
216        let Some((kind, data)) = self.fragment()? else {
217            return Ok(None);
218        };
219        match kind {
220            FULL => Ok(Some(Cow::Borrowed(data))),
221            FIRST => {
222                let mut record = data.to_vec();
223                loop {
224                    match self.fragment()? {
225                        Some((MIDDLE, data)) => record.extend_from_slice(data),
226                        Some((LAST, data)) => {
227                            record.extend_from_slice(data);
228                            return Ok(Some(Cow::Owned(record)));
229                        }
230                        _ => return Err(LogError::Invalid),
231                    }
232                }
233            }
234            _ => Err(LogError::Invalid),
235        }
236    }
237}
238
239impl<'a> Iterator for Records<'a> {
240    type Item = Result<Cow<'a, [u8]>, LogError>;
241
242    fn next(&mut self) -> Option<Self::Item> {
243        match self.record() {
244            Ok(Some(record)) => Some(Ok(record)),
245            Ok(None) => None,
246            Err(err) => {
247                self.pos = self.data.len();
248                Some(Err(err))
249            }
250        }
251    }
252}
253
254#[cfg(test)]
255mod tests {
256    use super::*;
257
258    fn read(data: &[u8]) -> Result<Vec<Vec<u8>>, LogError> {
259        records(data).map(|r| r.map(Cow::into_owned)).collect()
260    }
261
262    #[test]
263    fn crc32c_matches_the_standard_check_value() {
264        assert_eq!(crc32c(b"123456789"), 0xe306_9283);
265    }
266
267    #[test]
268    fn the_leading_record_of_an_overall_metadata_file() {
269        // Byte for byte what the official emulator writes first.
270        assert_eq!(
271            write_all([&[0x33u8][..]]),
272            [0xb8, 0x6d, 0x44, 0x4e, 0x01, 0x00, 0x01, 0x33]
273        );
274        assert_eq!(write_all([&[][..]]), [0x05, 0x2b, 0x28, 0x43, 0, 0, 1]);
275    }
276
277    #[test]
278    fn records_split_across_blocks_round_trip() {
279        let big = vec![7u8; 2 * BLOCK + 100];
280        let mut writer = Writer::new(Vec::new());
281        writer.add_record(b"a").unwrap();
282        writer.add_record(&big).unwrap();
283        // Leaves 3 bytes in the block, too few for a header: they become a zero trailer.
284        let fill = vec![1u8; BLOCK - writer.offset - HEADER - 3];
285        writer.add_record(&fill).unwrap();
286        assert_eq!(BLOCK - writer.offset, 3);
287        writer.add_record(b"").unwrap();
288        writer.add_record(b"after the trailer").unwrap();
289        let log = writer.into_inner();
290        let records: Vec<&[u8]> = vec![b"a", &big, &fill, b"", b"after the trailer"];
291        assert_eq!(read(&log).unwrap(), records);
292        assert_eq!(log.len() % BLOCK, 2 * HEADER + "after the trailer".len());
293    }
294
295    #[test]
296    fn every_record_size_near_a_block_boundary_round_trips() {
297        for size in BLOCK - 20..BLOCK + 5 {
298            let records = [vec![1u8; size], vec![2u8; 9], vec![3u8; size]];
299            let log = write_all(records.iter().map(Vec::as_slice));
300            assert_eq!(read(&log).unwrap(), records, "size {size}");
301        }
302    }
303
304    #[test]
305    fn damage_is_reported() {
306        let log = write_all([&b"hello world"[..], b"second"]);
307        let mut flipped = log.clone();
308        flipped[9] ^= 0xff;
309        assert_eq!(read(&flipped), Err(LogError::Checksum));
310        assert_eq!(read(&log[..log.len() - 3]), Err(LogError::Invalid));
311        assert_eq!(read(&log[..3]), Err(LogError::Invalid));
312        // A FIRST fragment without the rest of its record.
313        let split = write_all([&vec![0u8; BLOCK][..]]);
314        assert_eq!(read(&split[..BLOCK]), Err(LogError::Invalid));
315    }
316}
hidane_core/export/log.rs

hidane_core/export/
log.rs
