arc_mac/
stuffit_huffman.rs

1// SPDX-License-Identifier: LGPL-2.1-or-later
2// Derived from XADMaster, Copyright (c) 2017-present MacPaw Way Ltd.; see THIRD_PARTY_NOTICES.md.
3//! StuffIt compression **method 3** ("Huffman"): a plain byte-wise Huffman
4//! code whose tree is serialized at the head of the stream. Ported from
5//! XADMaster `XADStuffItHuffmanHandle.m`. Big-endian (MSB-first) bitstream.
6//!
7//! Rare (StuffIt 1.x era); no local sample to validate against, so this is a
8//! faithful port. The per-fork CRC-16/ARC check makes a wrong decode fail
9//! loudly rather than produce silent garbage.
10
11use anyhow::{bail, Result};
12
13use super::bitreader_be::BitReaderBE;
14
15enum Node {
16    Leaf(u8),
17    Branch(Box<Node>, Box<Node>),
18}
19
20/// Parse the serialized tree: a `1` bit introduces a leaf (next 8 bits = byte),
21/// a `0` bit introduces an internal node (zero-branch then one-branch).
22fn parse_tree(br: &mut BitReaderBE, depth: u32) -> Result<Node> {
23    if depth > 64 {
24        bail!("StuffIt Huffman: tree too deep");
25    }
26    if br.next_bit() == 1 {
27        Ok(Node::Leaf(br.next_bits(8) as u8))
28    } else {
29        let zero = parse_tree(br, depth + 1)?;
30        let one = parse_tree(br, depth + 1)?;
31        Ok(Node::Branch(Box::new(zero), Box::new(one)))
32    }
33}
34
35/// Decompress a StuffIt method-3 (Huffman) stream to `want` bytes.
36pub fn decompress(comp: &[u8], want: usize) -> Result<Vec<u8>> {
37    if want == 0 {
38        return Ok(Vec::new());
39    }
40    let mut br = BitReaderBE::new(comp);
41    let root = parse_tree(&mut br, 0)?;
42
43    let mut out = Vec::with_capacity(want);
44    while out.len() < want {
45        let mut node = &root;
46        loop {
47            match node {
48                Node::Leaf(b) => {
49                    out.push(*b);
50                    break;
51                }
52                Node::Branch(zero, one) => {
53                    // CSInputNextSymbolUsingCode walks branches[bit]: bit 0 -> left.
54                    node = if br.next_bit() == 0 { zero } else { one };
55                }
56            }
57        }
58    }
59    Ok(out)
60}
61
62#[cfg(test)]
63mod tests {
64    use super::*;
65
66    #[test]
67    fn huffman_simple_tree() {
68        // Build a stream by hand: tree for symbols 'A' (code 0) and 'B' (code 1).
69        // Tree serialization (MSB-first): 0 (branch) 1 'A'(8b) 1 'B'(8b)
70        // Then data: A B A A -> bits 0 1 0 0
71        let mut bits: Vec<bool> = Vec::new();
72        let put_byte = |bits: &mut Vec<bool>, v: u8| {
73            for i in (0..8).rev() {
74                bits.push((v >> i) & 1 == 1);
75            }
76        };
77        bits.push(false); // branch
78        bits.push(true); // leaf
79        put_byte(&mut bits, b'A');
80        bits.push(true); // leaf
81        put_byte(&mut bits, b'B');
82        // data: A(0) B(1) A(0) A(0)
83        bits.push(false);
84        bits.push(true);
85        bits.push(false);
86        bits.push(false);
87
88        // pack MSB-first into bytes
89        let mut bytes = Vec::new();
90        let mut acc = 0u8;
91        let mut n = 0;
92        for b in bits {
93            acc = (acc << 1) | (b as u8);
94            n += 1;
95            if n == 8 {
96                bytes.push(acc);
97                acc = 0;
98                n = 0;
99            }
100        }
101        if n > 0 {
102            bytes.push(acc << (8 - n));
103        }
104
105        let out = decompress(&bytes, 4).unwrap();
106        assert_eq!(&out, b"ABAA");
107    }
108}
arc_mac/stuffit_huffman.rs

arc_mac/
stuffit_huffman.rs
