chess/formats/cbv/
huffman.rs

1use super::*;
2
3/// Huffman tree
4#[derive(Default)]
5pub struct Tree {
6    pub left: Option<Box<Tree>>,
7    pub right: Option<Box<Tree>>,
8    pub value: Option<u8>,
9}
10
11impl From<u8> for Tree {
12    fn from(value: u8) -> Self {
13        Self { left: None, right: None, value: Some(value) }
14    }
15}
16
17impl Tree {
18    /// Descend into the tree in the specified direction (right or left).
19    /// When a leaf is reached, push the value to result and reset the visitor.
20    // fn visit<'a>(mut current: &mut &'a Tree, root: &'a Tree, result: &mut Vec<u8>, right: bool) {
21    fn visit<'a>(
22        &'a self,
23        current: &mut &'a Tree,
24        result: &mut Vec<u8>,
25        right: bool,
26    ) -> Option<()> {
27        let direction = if right { current.right.as_ref()? } else { current.left.as_ref()? };
28        if let Some(byte) = direction.value {
29            result.push(byte);
30            *current = self;
31        } else {
32            *current = direction;
33        }
34        Some(())
35    }
36
37    #[must_use]
38    // None denotes failure
39    pub fn unpack(&self, bits: Bits<'_>, decompressed: usize) -> Option<Vec<u8>> {
40        let mut current = self;
41        let mut result = Vec::new();
42
43        for direction in bits {
44            if result.len() == decompressed {
45                break;
46            }
47
48            self.visit(&mut current, &mut result, direction)?;
49        }
50
51        Some(result)
52    }
53
54    pub fn get_mut_or_insert(&mut self, right: bool) -> &mut Self {
55        if right { self.right.get_or_insert_default() } else { self.left.get_or_insert_default() }
56    }
57
58    pub fn load(values: [(usize, u16); 256]) -> Self {
59        let mut tree = Tree::default();
60        for (i, (len, bits)) in values.into_iter().enumerate() {
61            if len > 0 {
62                let mut node = &mut tree;
63                let bits = (bits << (16 - len)).to_be_bytes();
64
65                for direction in Bits::from(bits.as_slice()).take(len) {
66                    node = node.get_mut_or_insert(direction);
67                }
68
69                node.value = Some(i as u8);
70            }
71        }
72        tree
73    }
74}
chess/formats/cbv/huffman.rs

chess/formats/cbv/
huffman.rs
