wmv_decoder/
vlc_tree.rs

1//! Bit-by-bit Huffman/VLC decoder (upstream get_vlc2 equivalent strategy).
2//!
3//! We intentionally use a tree (bit traversal) instead of a flat lookup table,
4//! because MSMPEG4/WMV2 DC tables contain code lengths up to 24 bits.
5
6use crate::bitreader::BitReader;
7
8#[derive(Clone, Copy, Default)]
9struct Node {
10    left: Option<usize>,
11    right: Option<usize>,
12    sym: Option<i32>,
13}
14
15/// MSB-first VLC tree.
16#[derive(Clone)]
17pub struct VlcTree {
18    nodes: Vec<Node>,
19}
20
21impl VlcTree {
22    pub fn new() -> Self {
23        VlcTree { nodes: vec![Node::default()] }
24    }
25
26    pub fn insert(&mut self, code: u32, len: u8, sym: i32) {
27        let mut cur = 0usize;
28        for bitpos in (0..len).rev() {
29            let bit_is_one = ((code >> bitpos) & 1) != 0;
30
31            // Avoid holding a mutable reference into `self.nodes` across a `push()`.
32            // (A push may reallocate and would invalidate such a reference.)
33            let next = if !bit_is_one { self.nodes[cur].left } else { self.nodes[cur].right };
34            cur = match next {
35                Some(i) => i,
36                None => {
37                    let i = self.nodes.len();
38                    self.nodes.push(Node::default());
39                    if !bit_is_one {
40                        self.nodes[cur].left = Some(i);
41                    } else {
42                        self.nodes[cur].right = Some(i);
43                    }
44                    i
45                }
46            };
47        }
48        self.nodes[cur].sym = Some(sym);
49    }
50
51    /// Decode a symbol. Returns None on EOF or invalid code path.
52    pub fn decode(&self, br: &mut BitReader<'_>) -> Option<i32> {
53        let mut cur = 0usize;
54        loop {
55            if let Some(sym) = self.nodes[cur].sym {
56                return Some(sym);
57            }
58            let bit = br.read_bit()?;
59            cur = if !bit {
60                self.nodes[cur].left?
61            } else {
62                self.nodes[cur].right?
63            };
64        }
65    }
66}
wmv_decoder/vlc_tree.rs

wmv_decoder/
vlc_tree.rs
