tinybz2 0.1.0

Minimal-memory bz2 compressor/decompressor for embedded targets
Documentation
//! bz2 decompressor — reads a bz2 bitstream and reconstructs the original data.
//!
//! Pipeline: bitstream → Huffman decode → RLE2 decode → inverse MTF → inverse BWT → RLE1 decode
//!
//! Memory usage for block size 1: ~112 KB total
//!   - BWT block buffer: 100 KB
//!   - T-vector or scratch: reused from symbol buffer
//!   - Huffman tables: ~10 KB
//!   - Frequency/cumulative tables: ~2 KB

use crate::bitio::BitReader;
use crate::bwt;
use crate::constants::*;
use crate::crc::{self, Crc32};
use crate::error::Error;
use crate::huffman::{self, HuffTables};
use crate::mtf;
use crate::rle1;
use crate::rle2;

/// Status returned by decompression operations.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum DecompressStatus {
    /// Decompression completed successfully.
    Ok,
    /// Need more input data.
    NeedInput,
    /// Output buffer full, call again with more space.
    OutputFull,
}

/// bz2 decompressor.
pub struct Decompressor {
    _placeholder: (),
}

impl Decompressor {
    pub fn new() -> Self {
        Self { _placeholder: () }
    }

    /// One-shot decompression of a complete bz2 stream.
    ///
    /// `input`: the complete bz2 compressed data.
    /// `output`: buffer to receive the decompressed data.
    ///
    /// Returns the number of bytes written to `output`.
    pub fn decompress_block(&mut self, input: &[u8], output: &mut [u8]) -> Result<usize, Error> {
        let mut reader = BitReader::new(input);
        let mut out_pos = 0;

        // ── Read stream header ─────────────────────────────────────────
        let magic0 = reader.read_u8()?;
        let magic1 = reader.read_u8()?;
        if magic0 != STREAM_MAGIC[0] || magic1 != STREAM_MAGIC[1] {
            return Err(Error::BadMagic);
        }

        let version = reader.read_u8()?;
        if version != STREAM_VERSION {
            return Err(Error::BadMagic);
        }

        let block_size_char = reader.read_u8()?;
        if block_size_char < BLOCK_SIZE_CHAR_BASE + 1 || block_size_char > BLOCK_SIZE_CHAR_BASE + 9
        {
            return Err(Error::BadBlockSize);
        }
        let block_size_100k = (block_size_char - BLOCK_SIZE_CHAR_BASE) as usize;
        let _max_block_size = block_size_100k * BLOCK_SIZE_UNIT;

        // ── Read blocks ────────────────────────────────────────────────
        let mut stream_crc_computed = 0u32;

        loop {
            // Read 48-bit magic (block or end-of-stream)
            let magic_hi = reader.read_bits(24)?;
            let magic_lo = reader.read_bits(24)?;
            let magic = ((magic_hi as u64) << 24) | (magic_lo as u64);

            if magic == EOS_MAGIC {
                // End of stream — read and verify stream CRC
                let stream_crc_stored = reader.read_u32()?;
                if stream_crc_stored != stream_crc_computed {
                    return Err(Error::StreamCrcMismatch);
                }
                break;
            }

            if magic != BLOCK_MAGIC {
                return Err(Error::BadBlockHeader);
            }

            // Read block CRC and randomized flag
            let block_crc_stored = reader.read_u32()?;
            let _randomized = reader.read_bool()?;

            // Read BWT primary index (24 bits)
            let primary_index = reader.read_bits(24)?;

            // ── Read in-use bitmap ─────────────────────────────────────
            let mut in_use = [false; ALPHABET_SIZE];
            let group_mask = reader.read_u16()?;

            for g in 0..16u16 {
                if group_mask & (1 << (15 - g)) != 0 {
                    let sym_mask = reader.read_u16()?;
                    for i in 0..16u16 {
                        if sym_mask & (1 << (15 - i)) != 0 {
                            in_use[(g * 16 + i) as usize] = true;
                        }
                    }
                }
            }

            let n_in_use = in_use.iter().filter(|&&b| b).count();
            if n_in_use == 0 {
                return Err(Error::BadBlockHeader);
            }

            let n_symbols = n_in_use + 2; // RUNA, RUNB, shifted values, EOB

            // ── Read Huffman tables ────────────────────────────────────
            let n_groups = reader.read_bits(3)? as usize;
            if n_groups < 1 || n_groups > MAX_GROUPS {
                return Err(Error::BadHuffmanTable);
            }

            let n_selectors = reader.read_bits(15)? as usize;
            if n_selectors == 0 {
                return Err(Error::BadSelector);
            }

            // Read selectors
            // For block size 1, max selectors ≈ 2500. We use stack alloc.
            const MAX_SEL: usize = 18_002;
            let mut selectors = [0u8; MAX_SEL];
            if n_selectors > MAX_SEL {
                return Err(Error::BadSelector);
            }
            huffman::read_selectors(&mut reader, n_selectors, n_groups, &mut selectors)?;

            // Read Huffman code length tables
            let mut huff_tables = HuffTables::new();
            huffman::read_tables(&mut reader, n_groups, n_symbols, &mut huff_tables)?;

            // ── Decode Huffman symbols ──────────────────────────────────
            // Max symbols per block: roughly block_size + overhead.
            // For block size 1: ~125_000. For stack alloc we limit to 32 KB.
            const MAX_SYM_BUF: usize = 33_000;
            let mut symbols = [0u16; MAX_SYM_BUF];

            let sym_count = huffman::decode_symbols(
                &mut reader,
                &huff_tables,
                &selectors,
                n_selectors,
                &mut symbols,
                MAX_SYM_BUF,
            )?;

            // ── Stage 4 (reverse): RLE2 decode ─────────────────────────
            const MAX_MTF_BUF: usize = 33_000;
            let mut mtf_data = [0u8; MAX_MTF_BUF];
            let mtf_len = rle2::decode(&symbols[..sym_count], &mut mtf_data, n_in_use);

            // ── Stage 3 (reverse): inverse MTF ─────────────────────────
            let mut bwt_data = [0u8; MAX_MTF_BUF];
            mtf::decode(&mtf_data[..mtf_len], &mut bwt_data, &in_use);

            // ── Stage 2 (reverse): inverse BWT ─────────────────────────
            let mut rle1_data = [0u8; MAX_MTF_BUF];

            if mtf_len <= 4096 {
                // Small block: use inverse_small (no T-vector, O(n²))
                bwt::inverse_small(
                    &bwt_data[..mtf_len],
                    primary_index,
                    &mut rle1_data,
                )?;
            } else {
                // Larger block: use T-vector inverse
                let mut t_vec = [0u32; MAX_MTF_BUF];
                bwt::inverse(
                    &bwt_data[..mtf_len],
                    primary_index,
                    &mut rle1_data,
                    &mut t_vec,
                )?;
            }

            // ── Stage 1 (reverse): RLE1 decode ─────────────────────────
            let space_left = output.len() - out_pos;
            let decoded_len = rle1::decode(
                &rle1_data[..mtf_len],
                &mut output[out_pos..],
                space_left,
            )?;

            // ── Verify block CRC ───────────────────────────────────────
            let mut crc = Crc32::new();
            crc.update(&output[out_pos..out_pos + decoded_len]);
            let block_crc_computed = crc.finish();

            if block_crc_computed != block_crc_stored {
                return Err(Error::BlockCrcMismatch);
            }

            stream_crc_computed = crc::combine_crcs(stream_crc_computed, block_crc_computed);
            out_pos += decoded_len;
        }

        Ok(out_pos)
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn decompress_detects_bad_magic() {
        let bad_input = b"XX not bz2 data";
        let mut output = [0u8; 256];
        let mut decomp = Decompressor::new();
        assert_eq!(
            decomp.decompress_block(bad_input, &mut output),
            Err(Error::BadMagic)
        );
    }
}