chess/formats/chessbase/
archive.rs

1//! Chessbase archive file format
2
3// https://github.com/antoyo/uncbv
4// https://github.com/antoyo/uncbv/issues/3
5// https://github.com/antoyo/uncbv/issues/3
6
7// Note: It's called cbV for archiVe (or also version
8
9use std::{
10    io::{self, Read, Seek, SeekFrom, Write},
11    path::Path,
12};
13
14use crate::formats::{Bits, ByteInput as Input, prelude::*};
15
16use super::{cstr, huffman::Tree};
17
18/// ChessBase archive filename suffix.
19pub const SUFFIX: &str = "cbv";
20
21pub type Range = core::range::Range<usize>;
22
23crate::finite_set!(
24    /// A recognized ChessBase archive member.
25    Kind,
26    /// Archive members by kind.
27    Members {
28        Games as games,
29        Index as index,
30        Players as players,
31        Tournaments as tournaments,
32        Annotations as annotations,
33        Annotators as annotators,
34        Sources as sources,
35        Teams as teams,
36    }
37);
38
39/////////////
40// Parsing //
41/////////////
42
43/// Archive directory framing.
44#[derive(Clone, Copy, Debug, Eq, PartialEq)]
45pub struct Info {
46    pub members: usize,
47    pub metadata_len: usize,
48}
49
50/// ChessBase archive header.
51#[derive(Debug)]
52pub struct Header {
53    pub len: usize,
54    pub members: Vec<Member>,
55}
56
57impl Info {
58    pub const LEN: usize = 8;
59
60    pub fn header_len(self) -> usize {
61        self.members * self.metadata_len + Self::LEN
62    }
63}
64
65/// A file contained in a ChessBase archive.
66#[derive(Clone, Debug)]
67pub struct Member {
68    /// Member filename.
69    ///
70    /// This can contain embedded Windows-style backslash paths,
71    /// e.g. `D85 Gruenfeld Defence-163.html\42289499p0.jpg`.
72    pub name: String,
73    /// Unpacked member length.
74    pub len: usize,
75    /// Packed location within the archive.
76    pub packed: Range,
77}
78
79/// Packed and unpacked locations of an archive compression block.
80#[derive(Clone, Copy, Debug, Eq, PartialEq)]
81pub struct Block {
82    pub packed: Range,
83    pub unpacked: Range,
84}
85
86/// Random access to members packed in a ChessBase archive.
87pub struct Access<I> {
88    input: I,
89    members: Members<Option<State>>,
90    packed: Vec<u8>,
91}
92
93/// An unpacked view of one member in a ChessBase archive.
94pub struct Reader<'a, I> {
95    input: &'a mut I,
96    state: &'a mut State,
97    packed: &'a mut Vec<u8>,
98    position: usize,
99}
100
101struct State {
102    member: Member,
103    blocks: Vec<Block>,
104    cached: Option<(usize, Vec<u8>)>,
105}
106
107#[derive(Debug, thiserror::Error)]
108pub enum Error {
109    #[error("invalid ChessBase archive")]
110    Data,
111    #[error(transparent)]
112    Io(#[from] io::Error),
113}
114
115impl From<FrameError<ContextMode>> for Error {
116    fn from(error: FrameError<ContextMode>) -> Self {
117        match error {
118            FrameError::Error(_) => Self::Data,
119            FrameError::Io(error) => Self::Io(error),
120        }
121    }
122}
123
124pub type Result<T, E = Error> = core::result::Result<T, E>;
125
126impl Framed for Info {
127    const LEN: usize = Info::LEN;
128
129    fn total(&self) -> usize {
130        self.header_len()
131    }
132}
133
134pub fn read_header(input: &mut impl Read) -> Result<Header> {
135    Ok(framed(input, &mut Vec::new(), info, members)?)
136}
137
138// 8 byte header
139// - 2B magic number tag
140// - 2B number of members
141// - 1B length of each metadata record
142// - 3B unknown
143//
144// Metadata for each member (all same length e.g. 173 bytes)
145// - offset   0: C-string filename (Windows1252 encoding?)
146// - offset 132..136: 4B packed size
147// - offset 136..140: 4B unpacked size
148// - offset 140: unknown
149// - offsets 141 and 145: possibly last-modified date and time
150/// Parse the header out of a Chessbase archive
151pub fn header(input: &mut Input<'_>) -> ModalResult<Header> {
152    let info = info.parse_next(input)?;
153    members(info).parse_next(input)
154}
155
156fn members(info: Info) -> impl FnMut(&mut Input<'_>) -> ModalResult<Header> {
157    move |input| {
158        let len = info.header_len();
159        let mut offset = len;
160        let mut members = Vec::with_capacity(info.members);
161        // The archive stores relative member layout; retain absolute offsets for access.
162        for _ in 0..info.members {
163            let member = member(offset, info.metadata_len).parse_next(input)?;
164            offset = member.packed.end;
165            members.push(member);
166        }
167        Ok(Header { len, members })
168    }
169}
170
171pub fn info(input: &mut Input<'_>) -> ModalResult<Info> {
172    let (members, metadata_len) =
173        delimited(magic_tag, (le_u16, u8), take(3u8)).parse_next(input)?;
174    Ok(Info { members: members as usize, metadata_len: metadata_len as usize })
175}
176
177fn member(offset: usize, metadata_len: usize) -> impl FnMut(&mut Input<'_>) -> ModalResult<Member> {
178    move |input: &mut Input<'_>| {
179        let metadata = take(metadata_len).and_then(metadata).parse_next(input)?;
180        let end = offset.checked_add(metadata.packed).ok_or_else(backtrack)?;
181        Ok(Member { name: metadata.name, len: metadata.len, packed: Range::from(offset..end) })
182    }
183}
184
185struct Metadata {
186    name: String,
187    len: usize,
188    packed: usize,
189}
190
191fn metadata(input: &mut Input<'_>) -> ModalResult<Metadata> {
192    terminated(
193        seq! {Metadata {
194            name: take(132usize).map(cstr),
195            packed: le_i32.map(as_usize),
196            len: le_i32.map(as_usize),
197        }},
198        take(1usize),
199    )
200    .parse_next(input)
201}
202
203///////////////
204// Uncompression //
205///////////////
206
207pub fn unpack_to(member: &Member, input: &mut impl Read, output: &mut impl Write) -> Result<()> {
208    let mut input = input.take((member.packed.end - member.packed.start) as u64);
209    let mut packed = Vec::new();
210    let mut len = 0usize;
211    while input.limit() != 0 {
212        let block = framed(&mut input, &mut packed, block_info, unpack_block)?;
213        len = len.checked_add(block.len()).ok_or(Error::Data)?;
214        output.write_all(&block)?;
215    }
216    if len != member.len {
217        return Err(Error::Data);
218    }
219    Ok(())
220}
221
222#[derive(Clone, Copy, Debug)]
223struct BlockInfo {
224    len: usize,
225}
226
227impl Framed for BlockInfo {
228    const LEN: usize = 4;
229
230    fn total(&self) -> usize {
231        Self::LEN + self.len
232    }
233}
234
235/// Encodings applied to a block of a packed member.
236#[derive(Clone, Copy, Debug)]
237pub struct Compression {
238    /// Huffman-tree encoding
239    pub huffman: bool,
240    /// Mix of run-time length encoding and backward references
241    pub rle: bool,
242}
243
244fn block_info(input: &mut Input<'_>) -> ModalResult<BlockInfo> {
245    terminated(le_u16, take(2u8))
246        .verify(|len| *len > 0)
247        .map(|len| BlockInfo { len: usize::from(len) })
248        .parse_next(input)
249}
250
251fn unpack_block(info: BlockInfo) -> impl FnMut(&mut Input<'_>) -> ModalResult<Vec<u8>> {
252    move |input| {
253        let compression = compression.parse_next(input)?;
254        let mut block = take(info.len - 1).parse_next(input)?;
255
256        let block = if compression.huffman {
257            unpack_huffman(&mut block).expect("correct Huffman")
258        } else {
259            block.to_vec()
260        };
261
262        if compression.rle {
263            unpack_rle_backref(&mut block.as_slice()).map_err(ErrMode::Backtrack)
264        } else {
265            Ok(block)
266        }
267    }
268}
269
270fn compression(input: &mut Input<'_>) -> ModalResult<Compression> {
271    u8.verify_map(|compression| {
272        (compression < 4)
273            .then_some(Compression { rle: compression & 1 != 0, huffman: compression & 2 != 0 })
274    })
275    .parse_next(input)
276}
277
278// https://reverseengineering.stackexchange.com/questions/8593/unknown-decompression-algorithm/8601
279pub fn unpack_huffman(input: &mut Input<'_>) -> winnow::Result<Vec<u8>> {
280    use core::array::from_fn;
281
282    // 1. unpacked length
283    let len = be_u16(input)? as usize;
284
285    // 2. Huffman tree
286    let mut bits = Bits::from(*input);
287    let values: [(usize, u16); 256] = from_fn(|_| huffman_node(&mut bits).unwrap());
288
289    // 3. Decode block with tree
290    let tree = Tree::load(values);
291    let unpacked = tree.unpack(bits, len).unwrap();
292
293    assert_eq!(len, unpacked.len());
294    Ok(unpacked)
295}
296
297fn huffman_node(bits: &mut Bits) -> Option<(usize, u16)> {
298    let len = bits.unsigned(4)?;
299    let bits = bits.unsigned(len)? as u16;
300    Some((len, bits))
301}
302
303// This has run-length encoding and backward references
304pub fn unpack_rle_backref(input: &mut Input<'_>) -> winnow::Result<Vec<u8>> {
305    use winnow::binary::{le_u16, u8};
306
307    let mut result = vec![];
308    while !input.is_empty() {
309        let indicator = le_u16(input)?.to_be_bytes();
310        let indicator = Bits::from(indicator.as_slice());
311
312        for encoded in indicator {
313            if input.is_empty() {
314                return Ok(result);
315            }
316
317            if !encoded {
318                result.push(u8(input)?);
319                continue;
320            }
321
322            let (high, low) = u8(input).map(nibbles)?;
323
324            match high {
325                // run-length encoding, 3..=18
326                0 => {
327                    result.append(&mut vec![u8(input)?; 3 + low]);
328                }
329                // run-length encoding, 19..=4114
330                1 => {
331                    let size = 19 + low + ((u8(input)? as usize) << 4);
332                    result.append(&mut vec![u8(input)?; size]);
333                }
334                // backward reference
335                _ => {
336                    // 3..=4098
337                    let start = result.len() - (3 + low + ((u8(input)? as usize) << 4));
338                    let end = start
339                        + if high > 2 {
340                            // 3..=15
341                            high as usize
342                        } else {
343                            // 16..=271
344                            16 + u8(input)? as usize
345                        };
346                    result.extend_from_within(start..end);
347                }
348            }
349        }
350    }
351
352    Ok(result)
353}
354
355fn nibbles(x: u8) -> (u8, usize) {
356    (x >> 4, x as usize & 0xF)
357}
358
359////////////////////////////
360// Implementation details //
361////////////////////////////
362
363fn magic_tag(input: &mut Input<'_>) -> ModalResult<[u8; 2]> {
364    const MAGIC_NUMBER: [u8; 2] = [0x08, 0x00];
365    MAGIC_NUMBER.as_slice().map(|_| MAGIC_NUMBER).parse_next(input)
366}
367
368fn as_usize(x: i32) -> usize {
369    x as usize
370}
371
372impl<I> Access<I> {
373    pub fn new(input: I, members: &[Member]) -> Result<Self> {
374        let mut states: Members<Option<State>> = Members::empty();
375        for member in members {
376            let Some(kind) = Kind::from_name(&member.name) else {
377                continue;
378            };
379            if states[kind].is_some() {
380                return Err(Error::Data);
381            }
382            states[kind] = Some(State { member: member.clone(), blocks: Vec::new(), cached: None });
383        }
384        Ok(Self { input, members: states, packed: Vec::new() })
385    }
386
387    pub fn reader(&mut self, kind: Kind) -> Option<Reader<'_, I>> {
388        let state = self.members[kind].as_mut()?;
389        Some(Reader { input: &mut self.input, state, packed: &mut self.packed, position: 0 })
390    }
391}
392
393impl Kind {
394    fn from_name(name: &str) -> Option<Self> {
395        Self::from_suffix(Path::new(name).extension()?.to_str()?)
396    }
397
398    fn from_suffix(suffix: &str) -> Option<Self> {
399        use Kind::*;
400
401        Some(match suffix.to_ascii_lowercase().as_str() {
402            "cbg" => Games,
403            "cbh" => Index,
404            "cbp" => Players,
405            "cbt" => Tournaments,
406            "cba" => Annotations,
407            "cbc" => Annotators,
408            "cbs" => Sources,
409            "cbe" => Teams,
410            _ => return None,
411        })
412    }
413}
414
415impl<I: Read + Seek> Reader<'_, I> {
416    fn locate(&mut self, position: usize) -> Result<(usize, Block)> {
417        if let Some((i, block)) = self
418            .state
419            .blocks
420            .iter()
421            .enumerate()
422            .find(|(_, block)| block.unpacked.contains(&position))
423        {
424            return Ok((i, *block));
425        }
426
427        loop {
428            let (packed_offset, unpacked_offset, index) =
429                if let Some(block) = self.state.blocks.last() {
430                    (block.packed.end, block.unpacked.end, self.state.blocks.len())
431                } else {
432                    (0, 0, 0)
433                };
434
435            if packed_offset >= self.state.member.packed.end - self.state.member.packed.start {
436                return Err(Error::Data);
437            }
438
439            let (block, unpacked) = self.discover(packed_offset, unpacked_offset)?;
440            self.state.blocks.push(block);
441            self.state.cached = Some((index, unpacked));
442            if block.unpacked.contains(&position) {
443                return Ok((index, block));
444            }
445        }
446    }
447
448    fn discover(
449        &mut self,
450        packed_offset: usize,
451        unpacked_offset: usize,
452    ) -> Result<(Block, Vec<u8>)> {
453        let absolute =
454            self.state.member.packed.start.checked_add(packed_offset).ok_or(Error::Data)?;
455        self.input.seek(SeekFrom::Start(absolute as u64))?;
456        let remaining = (self.state.member.packed.end - self.state.member.packed.start)
457            .checked_sub(packed_offset)
458            .ok_or(Error::Data)?;
459        let mut input = self.input.by_ref().take(remaining as u64);
460        let data = framed(&mut input, self.packed, block_info, unpack_block)?;
461        let packed = Range {
462            start: packed_offset,
463            end: packed_offset.checked_add(self.packed.len()).ok_or(Error::Data)?,
464        };
465        let unpacked = Range {
466            start: unpacked_offset,
467            end: unpacked_offset.checked_add(data.len()).ok_or(Error::Data)?,
468        };
469
470        Ok((Block { packed, unpacked }, data))
471    }
472
473    fn load(&mut self, index: usize, block: Block) -> Result<()> {
474        if self.state.cached.as_ref().map(|(cached, _)| *cached) == Some(index) {
475            return Ok(());
476        }
477
478        let (loaded, unpacked) = self.discover(block.packed.start, block.unpacked.start)?;
479        if loaded != block {
480            return Err(Error::Data);
481        }
482        self.state.cached = Some((index, unpacked));
483        Ok(())
484    }
485}
486
487impl<I: Read + Seek> Read for Reader<'_, I> {
488    fn read(&mut self, mut output: &mut [u8]) -> io::Result<usize> {
489        let start_len = output.len();
490        while !output.is_empty() && self.position < self.state.member.len {
491            let (index, block) = self.locate(self.position)?;
492            self.load(index, block)?;
493            let offset = self.position - block.unpacked.start;
494            let available = block.unpacked.end - self.position;
495            let len = available.min(output.len());
496            let unpacked = &self.state.cached.as_ref().ok_or_else(invalid_data)?.1;
497            output[..len].copy_from_slice(&unpacked[offset..offset + len]);
498            self.position += len;
499            output = &mut output[len..];
500        }
501        Ok(start_len - output.len())
502    }
503}
504
505impl<I> Seek for Reader<'_, I> {
506    fn seek(&mut self, position: SeekFrom) -> io::Result<u64> {
507        use SeekFrom::*;
508
509        let base = match position {
510            Start(position) => {
511                self.position = usize::try_from(position).map_err(|_| invalid_input())?;
512                return Ok(position);
513            }
514            Current(_) => self.position,
515            End(_) => self.state.member.len,
516        };
517        let offset = match position {
518            Current(offset) | End(offset) => offset,
519            Start(_) => unreachable!(),
520        };
521        let position = (base as i128).checked_add(i128::from(offset)).ok_or_else(invalid_input)?;
522        self.position = usize::try_from(position).map_err(|_| invalid_input())?;
523        Ok(self.position as u64)
524    }
525}
526
527impl From<Error> for io::Error {
528    fn from(error: Error) -> io::Error {
529        match error {
530            Error::Data => io::Error::new(io::ErrorKind::InvalidData, error),
531            Error::Io(error) => error,
532        }
533    }
534}
535
536fn invalid_input() -> io::Error {
537    io::Error::new(io::ErrorKind::InvalidInput, "invalid ChessBase archive seek")
538}
539
540fn invalid_data() -> io::Error {
541    io::Error::new(io::ErrorKind::InvalidData, Error::Data)
542}
543
544#[cfg(test)]
545mod tests {
546    use hex_literal::hex;
547
548    use crate::formats::twic;
549
550    use super::*;
551
552    #[test]
553    fn unpack_to_rle() {
554        const INPUT: [u8; 38] = hex!(
555            "22004d39013740010400d20296494806000001ff410104040005ff1e62000008
556             6b1800004665"
557        );
558        const PREFIX: [u8; 40] = hex!(
559            "0100000000000000d202964948060000ffffffff010000000400000000000000
560             ffffffffffffffff"
561        );
562        const SUFFIX: [u8; 8] = hex!("6b18000001000000");
563
564        let member = Member {
565            name: "twic1616.cbl".to_string(),
566            len: 1649,
567            packed: Range::from(0..INPUT.len()),
568        };
569        let mut input = INPUT.as_slice();
570        let mut output = Vec::new();
571        super::unpack_to(&member, &mut input, &mut output).unwrap();
572
573        let mut expected = vec![0; member.len];
574        expected[..PREFIX.len()].copy_from_slice(&PREFIX);
575        expected[member.len - SUFFIX.len()..].copy_from_slice(&SUFFIX);
576        assert_eq!(output, expected);
577    }
578
579    #[test]
580    fn unpack_to_huffman_rle() {
581        const INPUT: [u8; 295] = hex!(
582            "23014bce03013d2190085a756ebe120f0000000428429001b0084684984a3a10
583             8a10a210aa007000000002138000000002130000000002134211c00000000000
584             21600000000000000000000002170000000021740000000000000000216c0000
585             0000000000000002164000000000000000000000000000000000212c00000000
586             000000000000000000000211000000213c0000214c0000000000215000000000
587             000000fab475e0b28027202e2e8a6ad685b554d4558504f4c41243612cc64149
588             18444a4825ea2bcfe5ef12f7897bc4bde25ef12f7897bc4bde3f97bc4bde25ef
589             12f7897bc4bde25ef12f78fe5ef12f7897bc4bde25ef12f7897bc4bde3f97bc4
590             bde25ef12f7897bc4bde25ef12f78fe5ef12f7897bc4bde25ef12f7897bc4bde
591             05497bc4beaf00"
592        );
593
594        let member = Member {
595            name: "twic1616.cbtt".to_string(),
596            len: 17_852,
597            packed: Range::from(0..INPUT.len()),
598        };
599        let mut input = INPUT.as_slice();
600        let mut output = Vec::new();
601        super::unpack_to(&member, &mut input, &mut output).unwrap();
602
603        assert_eq!(output.len(), member.len);
604        assert_eq!(crc32(&output), 0xb007_79cb);
605    }
606
607    fn crc32(input: &[u8]) -> u32 {
608        let mut crc = u32::MAX;
609        for byte in input {
610            crc ^= u32::from(*byte);
611            for _ in 0..8 {
612                crc = (crc >> 1) ^ (0xedb8_8320 & 0u32.wrapping_sub(crc & 1));
613            }
614        }
615        !crc
616    }
617
618    #[test]
619    #[ignore = "exhaustive test against the external TWIC fixture"]
620    fn twic_unpack_to() {
621        let data = twic::data(1616, "cbv");
622        let mut input = data.as_slice();
623        let header = read_header(&mut input).unwrap();
624        for member in &header.members {
625            let mut output = Vec::new();
626            super::unpack_to(member, &mut input, &mut output).unwrap();
627        }
628        println!("{header:?}");
629    }
630}
chess/formats/chessbase/archive.rs

chess/formats/chessbase/
archive.rs
