tinybz2 0.1.0

Minimal-memory bz2 compressor/decompressor for embedded targets
Documentation
//! bz2 format constants.
//!
//! Reference: <https://en.wikipedia.org/wiki/Bzip2#File_format>
//! and the libbzip2 source (bzlib_private.h).

// ── Stream header ──────────────────────────────────────────────────────────

/// Stream magic: "BZ" (0x42, 0x5A)
pub const STREAM_MAGIC: [u8; 2] = [0x42, 0x5A];

/// Stream version: "h" for Huffman coding (0x68)
pub const STREAM_VERSION: u8 = 0x68;

/// Block size stored as ASCII '1'..'9' (0x31..0x39)
pub const BLOCK_SIZE_CHAR_BASE: u8 = 0x30;

// ── Block header ───────────────────────────────────────────────────────────

/// Block magic: 0x31_41_59_26_53_59 ("1AY&SY" — first digits of pi)
pub const BLOCK_MAGIC: u64 = 0x31_4159_2653_59;
pub const BLOCK_MAGIC_BITS: u32 = 48;

/// End-of-stream magic: 0x17_72_45_38_50_90 (sqrt(pi))
pub const EOS_MAGIC: u64 = 0x17_7245_3850_90;
pub const EOS_MAGIC_BITS: u32 = 48;

// ── Block parameters ───────────────────────────────────────────────────────

/// Base block size unit (100 000 bytes).
pub const BLOCK_SIZE_UNIT: usize = 100_000;

/// Maximum block size (block_size_100k = 9 → 900 000 bytes).
pub const MAX_BLOCK_SIZE: usize = 9 * BLOCK_SIZE_UNIT;

/// After RLE1, the block can grow by at most 1.25× (255 → 259 bytes worst case).
/// We budget 25% overhead on the raw block size.
pub const RLE1_OVERHEAD_NUM: usize = 5;
pub const RLE1_OVERHEAD_DEN: usize = 4;

// ── Alphabet ───────────────────────────────────────────────────────────────

/// Byte alphabet size.
pub const ALPHABET_SIZE: usize = 256;

/// Extra symbols added by the MTF/RLE2 stage.
/// RUNA = 0, RUNB = 1, then the MTF values shifted up by 1, plus EOB.
/// Total in-use symbols = n_in_use + 2 (RUNA, RUNB, plus EOB).
/// Maximum possible: 256 + 2 = 258.
pub const MAX_SYMBOLS: usize = 258;

/// Maximum number of Huffman tables (groups).
pub const MAX_GROUPS: usize = 6;

/// Minimum number of Huffman tables.
pub const MIN_GROUPS: usize = 2;

/// Number of symbols per Huffman group selector.
pub const GROUP_SIZE: usize = 50;

/// Maximum number of selectors (for a 900 KB block at worst: ~18 002).
/// We compute it as ceil(max_mtf_symbols / GROUP_SIZE) where max_mtf_symbols
/// is bounded by block_size * RLE1_OVERHEAD (each byte can expand to at most
/// a few MTF symbols).
pub const MAX_SELECTORS: usize = 18_002;

// For block size 1, max selectors ≈ ceil(125_000 / 50) = 2500.
// We'll dynamically cap based on actual block size.

/// Maximum Huffman code length in bits.
pub const MAX_CODE_LEN: u32 = 20;

/// Minimum Huffman code length in bits.
pub const MIN_CODE_LEN: u32 = 1;

// ── Run-length encoding ────────────────────────────────────────────────────

/// RLE1 (initial): runs of 4+ identical bytes encoded as (byte×4)(count-4).
pub const RLE1_TRIGGER: usize = 4;

/// Maximum additional run length byte value.
pub const RLE1_MAX_RUN: usize = 255;

// ── CRC ────────────────────────────────────────────────────────────────────

/// CRC-32 polynomial used by bz2 (same as standard CRC-32/ISO-HDLC but
/// with big-endian bit ordering — bz2 uses a reflected table with 0x04C11DB7).
pub const CRC32_POLY: u32 = 0x04C1_1DB7;