tinybz2 0.1.0

Minimal-memory bz2 compressor/decompressor for embedded targets
Documentation
//! RLE2 — Zero run-length encoding (RUNA/RUNB).
//!
//! After MTF, the output contains many zeros (from repeated characters).
//! bz2 encodes runs of zeros using a bijective base-2 numbering with
//! two symbols: RUNA (value 1) and RUNB (value 2).
//!
//! A run of N zeros is encoded as a sequence of RUNA/RUNB symbols where
//! the run length is computed as:
//!   length = Σ (symbol_value × 2^position)
//! where symbol_value is 1 for RUNA, 2 for RUNB, and position counts
//! from 0 (rightmost/first emitted symbol).
//!
//! This is a bijective numeration: every positive integer has a unique
//! representation, and zero-length runs simply emit no symbols.
//!
//! The MTF values 1..n_in_use are shifted up by 1 in the output symbol
//! space, so that RUNA=0, RUNB=1, and MTF value k maps to symbol k+1.
//! The end-of-block (EOB) symbol is n_in_use + 1.

/// Symbol index for RUNA.
pub const RUNA: u16 = 0;

/// Symbol index for RUNB.
pub const RUNB: u16 = 1;

/// Encode MTF output into RLE2 symbols.
///
/// `mtf_data[..len]` contains MTF indices (0..n_in_use-1).
/// `symbols[..capacity]` receives the output symbol stream.
/// `n_in_use` is the number of distinct characters.
///
/// Returns the number of symbols written (including the trailing EOB).
///
/// Symbol values:
///   0 = RUNA
///   1 = RUNB
///   2..n_in_use+1 = MTF values 1..n_in_use (value 0 is absorbed by RUNA/RUNB)
///   n_in_use+1 = EOB
pub fn encode(mtf_data: &[u8], symbols: &mut [u16], n_in_use: usize) -> usize {
    let eob = (n_in_use + 1) as u16;
    let mut out_pos = 0;
    let mut i = 0;

    while i < mtf_data.len() {
        if mtf_data[i] == 0 {
            // Count the run of zeros
            let mut run_len = 0u32;
            while i < mtf_data.len() && mtf_data[i] == 0 {
                run_len += 1;
                i += 1;
            }

            // Encode run_len using bijective base-2 (RUNA/RUNB)
            encode_run(run_len, symbols, &mut out_pos);
        } else {
            // Non-zero MTF value: shift up by 1
            symbols[out_pos] = mtf_data[i] as u16 + 1;
            out_pos += 1;
            i += 1;
        }
    }

    // Append EOB symbol
    symbols[out_pos] = eob;
    out_pos += 1;

    out_pos
}

/// Encode a zero-run of length `run_len` as RUNA/RUNB symbols.
fn encode_run(mut run_len: u32, symbols: &mut [u16], pos: &mut usize) {
    // Bijective base-2: represent run_len as sum of (1 or 2) × 2^k
    // Starting from the least significant "digit".
    while run_len > 0 {
        run_len -= 1; // Convert to 0-based for the bijective encoding
        if run_len & 1 == 0 {
            symbols[*pos] = RUNA;
        } else {
            symbols[*pos] = RUNB;
        }
        *pos += 1;
        run_len >>= 1;
    }
}

/// Decode RLE2 symbols back to MTF indices.
///
/// `symbols[..len]` is the symbol stream (including EOB as last symbol).
/// `mtf_data[..capacity]` receives decoded MTF indices.
/// `n_in_use` is the number of distinct characters (EOB = n_in_use + 1).
///
/// Returns the number of MTF values written.
pub fn decode(symbols: &[u16], mtf_data: &mut [u8], n_in_use: usize) -> usize {
    let eob = (n_in_use + 1) as u16;
    let mut out_pos = 0;
    let mut i = 0;

    while i < symbols.len() {
        let sym = symbols[i];

        if sym == eob {
            break;
        }

        if sym == RUNA || sym == RUNB {
            // Decode a zero-run
            let mut run_len = 0u32;
            let mut power = 1u32;

            while i < symbols.len() && (symbols[i] == RUNA || symbols[i] == RUNB) {
                if symbols[i] == RUNA {
                    run_len += power;
                } else {
                    run_len += 2 * power;
                }
                power <<= 1;
                i += 1;
            }

            // Emit `run_len` zeros
            for _ in 0..run_len {
                mtf_data[out_pos] = 0;
                out_pos += 1;
            }
        } else {
            // Regular MTF value: shift back down by 1
            mtf_data[out_pos] = (sym - 1) as u8;
            out_pos += 1;
            i += 1;
        }
    }

    out_pos
}

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

    #[test]
    fn encode_no_zeros() {
        // MTF values [1, 2, 3], n_in_use=4
        let mtf = [1u8, 2, 3];
        let mut symbols = [0u16; 16];
        let n = encode(&mtf, &mut symbols, 4);
        // Symbols: 2, 3, 4, EOB(5)
        assert_eq!(n, 4);
        assert_eq!(symbols[0], 2);
        assert_eq!(symbols[1], 3);
        assert_eq!(symbols[2], 4);
        assert_eq!(symbols[3], 5); // EOB
    }

    #[test]
    fn encode_zeros() {
        // 3 zeros then a 1, n_in_use=4
        let mtf = [0u8, 0, 0, 1];
        let mut symbols = [0u16; 16];
        let n = encode(&mtf, &mut symbols, 4);

        // 3 zeros → bijective base-2 of 3:
        //   3-1=2, bit 0=0 → RUNA, 2>>1=1
        //   1-1=0, bit 0=0 → RUNA, 0>>1=0 → done
        // So RUNA, RUNA... wait, let me recalculate:
        //   run_len=3: 3-1=2, 2&1=0 → RUNA, 2>>1=1
        //              1-1=0, 0&1=0 → RUNA, 0>>1=0 → done
        // Hmm, that gives run_len 1+2=3. ✓
        // Then mtf value 1 → symbol 2, then EOB(5)

        // Decode to verify
        let mut decoded = [0u8; 16];
        let dn = decode(&symbols[..n], &mut decoded, 4);
        assert_eq!(dn, 4);
        assert_eq!(&decoded[..4], &[0, 0, 0, 1]);
    }

    #[test]
    fn roundtrip_mixed() {
        let mtf = [0u8, 0, 0, 0, 0, 1, 0, 0, 2, 0];
        let n_in_use = 4;
        let mut symbols = [0u16; 64];
        let sym_len = encode(&mtf, &mut symbols, n_in_use);

        let mut decoded = [0u8; 64];
        let dec_len = decode(&symbols[..sym_len], &mut decoded, n_in_use);
        assert_eq!(dec_len, mtf.len());
        assert_eq!(&decoded[..dec_len], &mtf[..]);
    }

    #[test]
    fn single_zero() {
        let mtf = [0u8];
        let mut symbols = [0u16; 16];
        let sym_len = encode(&mtf, &mut symbols, 2);

        let mut decoded = [0u8; 16];
        let dec_len = decode(&symbols[..sym_len], &mut decoded, 2);
        assert_eq!(dec_len, 1);
        assert_eq!(decoded[0], 0);
    }
}