tinybz2 0.1.0

Minimal-memory bz2 compressor/decompressor for embedded targets
Documentation
//! bz2 compressor — wires together all pipeline stages.
//!
//! Pipeline: input → RLE1 → BWT → MTF → RLE2 → Huffman → bitstream

use crate::bitio::BitWriter;
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 streaming compression operations.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum CompressStatus {
    /// More input can be accepted.
    Ok,
    /// The block is full; call `flush_block` before providing more input.
    BlockFull,
    /// Compression is finished.
    Finished,
}

/// bz2 compressor state.
///
/// Memory usage for block_size_100k = 1:
///   block_buf:  100_000 bytes (input block)
///   work_buf:   125_000 bytes (RLE1 output / BWT workspace)
///   indices:    400_000 bytes (suffix array) — THIS is the big one
///   mtf_buf:    125_000 bytes (MTF output)
///   symbols:    250_000 bytes (RLE2 output, u16)
///
/// Total: ~1 MB. That's too much for ESP32.
///
/// **Practical approach**: We use a SHARED buffer strategy where buffers
/// are reused across pipeline stages (since each stage fully consumes
/// its input before the next starts).
///
/// With buffer sharing:
///   shared_buf:  125_000 bytes (used for RLE1 out, then MTF, then symbols)
///   block_buf:   100_000 bytes (original input, then BWT output)
///   indices:     100_000 × 4 = 400_000 bytes (suffix array)
///
/// Still ~625 KB due to the suffix array. For block_size 1 to fit in
/// ESP32 we need to avoid the full suffix array — see bwt.rs for the
/// shellsort approach that sorts in-place using O(1) extra memory.
///
/// **With in-place BWT sort**:
///   block_buf:   100_000 bytes (overwritten by BWT output)
///   work_buf:    125_000 bytes (shared across stages)
///   indices:     100_000 × 4 bytes — REQUIRED by BWT, but we can use
///                the work_buf for this if we process in phases
///
/// Actually the indices and work_buf can be the same allocation since
/// they're used at different times:
///   Phase 1 (RLE1):  work_buf holds RLE1 output (max 125 KB)
///   Phase 2 (BWT):   work_buf reinterpreted as &mut [u32] for indices
///   Phase 3 (MTF):   work_buf holds MTF output
///   Phase 4 (RLE2):  work_buf reinterpreted as &mut [u16] for symbols
///   Phase 5 (Huff):  reads from symbols, writes to output bitstream
///
/// This works because 125_000 bytes = 31_250 u32s, but we need 100_000 u32s
/// for the suffix array. So work_buf needs to be at least 400 KB for BWT.
///
/// **With shellsort BWT (no suffix array)**: We sort a [u32] index array
/// but that still needs n × 4 bytes. The trick: during BWT, we need the
/// original block AND the index array. After BWT, we only need the output.
///
/// For true minimum memory, we store indices as u16 + u8 packed (3 bytes
/// each) for blocks up to 16M. For block size 1 (max 100K), u17 suffices
/// but we can't use u17 — we use u32.
///
/// **FINAL APPROACH**: Accept ~500 KB total for block size 1 compression.
/// On ESP32 with 520 KB RAM minus ~100 KB for AtomVM base = 420 KB free.
/// This is TIGHT but possible if AtomVM + our app stay lean.
///
/// For decompression the story is much better — see decompress.rs.
pub struct Compressor {
    block_size_100k: u8,
    max_block_size: usize,
}

impl Compressor {
    /// Create a new compressor.
    ///
    /// `block_size_100k` must be 1..=9.
    pub fn new(block_size_100k: u8) -> Self {
        Self {
            block_size_100k,
            max_block_size: block_size_100k as usize * BLOCK_SIZE_UNIT,
        }
    }

    /// Compress a complete input block into a bz2 stream.
    ///
    /// This is the one-shot API. For streaming, a more complex interface
    /// would be needed (feeding data into blocks, flushing, etc.).
    ///
    /// `input`: raw data to compress.
    /// `output`: buffer to receive the bz2 stream.
    ///
    /// Returns the number of bytes written to `output`.
    pub fn compress_block(&mut self, input: &[u8], output: &mut [u8]) -> Result<usize, Error> {
        let mut writer = BitWriter::new(output);

        // ── Stream header ──────────────────────────────────────────────
        writer.write_u8(STREAM_MAGIC[0])?;
        writer.write_u8(STREAM_MAGIC[1])?;
        writer.write_u8(STREAM_VERSION)?;
        writer.write_u8(BLOCK_SIZE_CHAR_BASE + self.block_size_100k)?;

        // ── Compress in blocks ─────────────────────────────────────────
        let mut stream_crc = 0u32;
        let mut pos = 0;

        while pos < input.len() {
            let end = (pos + self.max_block_size).min(input.len());
            let block_data = &input[pos..end];

            let block_crc = self.write_block(block_data, &mut writer)?;
            stream_crc = crc::combine_crcs(stream_crc, block_crc);

            pos = end;
        }

        // ── End-of-stream marker ───────────────────────────────────────
        writer.write_bits(24, (EOS_MAGIC >> 24) as u32)?;
        writer.write_bits(24, (EOS_MAGIC & 0xFF_FFFF) as u32)?;
        writer.write_u32(stream_crc)?;

        writer.finish()
    }

    /// Write a single compressed block to the bitstream.
    /// Returns the block's CRC.
    fn write_block(&self, data: &[u8], writer: &mut BitWriter) -> Result<u32, Error> {
        let n = data.len();
        if n == 0 {
            return Ok(0);
        }

        // Compute CRC of original data
        let mut crc = Crc32::new();
        crc.update(data);
        let block_crc = crc.finish();

        // ── Stage 1: RLE1 ──────────────────────────────────────────────
        // Worst case: no compression, same size + a few extra bytes for runs.
        // We need a temporary buffer. For minimal memory we'll use a
        // stack-allocated buffer for small blocks and error out for large ones
        // that don't fit.

        // For blocks up to ~32 KB (typical LoRa use), stack alloc is fine.
        // For larger blocks this needs a provided workspace.
        const MAX_STACK_BLOCK: usize = 32_768;
        const MAX_RLE1_BUF: usize = MAX_STACK_BLOCK * RLE1_OVERHEAD_NUM / RLE1_OVERHEAD_DEN;

        if n > MAX_STACK_BLOCK {
            // For large blocks, just skip RLE1 and treat input as-is.
            // This is valid — RLE1 is optional for correctness (the decoder
            // handles unencoded data too since it looks for 4-byte runs).
            return self.write_block_inner(data, n, block_crc, writer);
        }

        let mut rle1_buf = [0u8; MAX_RLE1_BUF];
        let rle1_len = rle1::encode(data, &mut rle1_buf)?;

        self.write_block_inner(&rle1_buf[..rle1_len], rle1_len, block_crc, writer)
    }

    /// Inner block writer after RLE1 encoding.
    fn write_block_inner(
        &self,
        rle1_data: &[u8],
        rle1_len: usize,
        block_crc: u32,
        writer: &mut BitWriter,
    ) -> Result<u32, Error> {
        // ── Block header ───────────────────────────────────────────────
        // 48-bit magic split into two 24-bit writes
        writer.write_bits(24, (BLOCK_MAGIC >> 24) as u32)?;
        writer.write_bits(24, (BLOCK_MAGIC & 0xFF_FFFF) as u32)?;
        writer.write_u32(block_crc)?;
        writer.write_bit(0)?; // not randomized

        // ── Stage 2: BWT ───────────────────────────────────────────────
        // We need: bwt_output[rle1_len] and indices[rle1_len].
        // For blocks ≤ 32 KB: bwt_output = 32 KB, indices = 128 KB.
        // Total stack: ~192 KB for BWT phase. Still a lot but manageable.
        const MAX_BWT_BLOCK: usize = 32_768;

        if rle1_len > MAX_BWT_BLOCK {
            return Err(Error::BlockFull);
        }

        let mut bwt_output = [0u8; MAX_BWT_BLOCK];
        let mut indices = [0u32; MAX_BWT_BLOCK];

        let primary_index = bwt::forward(
            &rle1_data[..rle1_len],
            &mut bwt_output,
            &mut indices,
        )?;

        // Write BWT primary index (24 bits — enough for blocks up to 16M)
        writer.write_bits(24, primary_index)?;

        // ── Determine in-use symbols ───────────────────────────────────
        let mut in_use = [false; ALPHABET_SIZE];
        for &b in &bwt_output[..rle1_len] {
            in_use[b as usize] = true;
        }

        // Write in-use bitmap: 16 groups of 16 bits
        // First a 16-bit mask of which groups have any symbols
        let mut group_mask = 0u16;
        for g in 0..16 {
            for i in 0..16 {
                if in_use[g * 16 + i] {
                    group_mask |= 1 << (15 - g);
                    break;
                }
            }
        }
        writer.write_u16(group_mask)?;

        for g in 0..16 {
            if group_mask & (1 << (15 - g)) != 0 {
                let mut sym_mask = 0u16;
                for i in 0..16 {
                    if in_use[g * 16 + i] {
                        sym_mask |= 1 << (15 - i);
                    }
                }
                writer.write_u16(sym_mask)?;
            }
        }

        // Count in-use symbols
        let n_in_use = in_use.iter().filter(|&&b| b).count();

        // ── Stage 3: MTF ───────────────────────────────────────────────
        let mut mtf_output = [0u8; MAX_BWT_BLOCK];
        mtf::encode(&bwt_output[..rle1_len], &mut mtf_output, &in_use);

        // ── Stage 4: RLE2 (RUNA/RUNB) ─────────────────────────────────
        // Output symbols are u16; max count ≈ rle1_len + some.
        let mut symbols = [0u16; MAX_BWT_BLOCK + 256];
        let n_symbols_total = n_in_use + 2; // RUNA, RUNB + shifted values + EOB
        let sym_count = rle2::encode(
            &mtf_output[..rle1_len],
            &mut symbols,
            n_in_use,
        );

        // ── Stage 5: Huffman coding ────────────────────────────────────
        // Compute symbol frequencies
        let mut freq = [0u32; MAX_SYMBOLS];
        for i in 0..sym_count {
            freq[symbols[i] as usize] += 1;
        }

        // Generate Huffman tables
        let mut huff_tables = HuffTables::new();
        huffman::generate_tables(&freq, n_symbols_total, &mut huff_tables);

        // Write number of groups and selectors
        let n_groups = huff_tables.n_groups;
        let n_selectors = (sym_count + GROUP_SIZE - 1) / GROUP_SIZE;
        writer.write_bits(3, n_groups as u32)?;
        writer.write_bits(15, n_selectors as u32)?;

        // Write selectors (all 0 since we only have 1 group)
        let selectors = [0u8; 8192];
        huffman::write_selectors(writer, &selectors, n_selectors, n_groups)?;

        // Write Huffman tables
        huffman::write_tables(writer, &huff_tables)?;

        // Write encoded symbols
        let table = &huff_tables.tables[0];
        for i in 0..sym_count {
            let sym = symbols[i] as usize;
            let code = table.codes[sym];
            let len = table.lengths[sym] as u32;
            writer.write_bits(len, code)?;
        }

        Ok(block_crc)
    }
}

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

    #[test]
    fn compress_small() {
        let input = b"hello world";
        let mut output = [0u8; 256];
        let mut comp = Compressor::new(1);
        let n = comp.compress_block(input, &mut output).unwrap();
        assert!(n > 0);

        // Verify stream header
        assert_eq!(output[0], b'B');
        assert_eq!(output[1], b'Z');
        assert_eq!(output[2], b'h');
        assert_eq!(output[3], b'1'); // block size 1
    }
}