tinybz2 0.1.1

Minimal-memory bz2 compressor/decompressor for embedded targets
Documentation
//! Move-to-Front Transform.
//!
//! After BWT, the data contains many repeated characters and characters
//! that tend to recur in nearby positions. MTF exploits this by
//! maintaining a list of recently-seen characters and encoding each
//! character as its position in that list. Recently seen characters get
//! small indices, which compresses well.
//!
//! Memory: 256 bytes for the lookup table. O(1) extra.

use crate::constants::ALPHABET_SIZE;

/// Move-to-Front encoder/decoder state.
///
/// This is just a 256-byte array representing the current character ordering.
pub struct Mtf {
    /// The MTF list: `list[i]` is the character currently at position `i`.
    list: [u8; ALPHABET_SIZE],
}

impl Mtf {
    /// Create a new MTF state with the identity permutation (0, 1, 2, ..., 255).
    pub fn new() -> Self {
        let mut list = [0u8; ALPHABET_SIZE];
        for i in 0..ALPHABET_SIZE {
            list[i] = i as u8;
        }
        Self { list }
    }

    /// Create a new MTF state using only the in-use symbols.
    ///
    /// `in_use` is a 256-element boolean array; only symbols where
    /// `in_use[i] == true` are placed in the initial list (in order).
    /// This matches bz2's behavior where unused symbols are excluded.
    ///
    /// Returns (Mtf, n_in_use) where n_in_use is the number of active symbols.
    pub fn new_with_in_use(in_use: &[bool; ALPHABET_SIZE]) -> (Self, usize) {
        let mut list = [0u8; ALPHABET_SIZE];
        let mut n = 0;
        for i in 0..ALPHABET_SIZE {
            if in_use[i] {
                list[n] = i as u8;
                n += 1;
            }
        }
        (Self { list }, n)
    }

    /// Encode one byte: find its position in the list, move it to front,
    /// return the position (0..255).
    #[inline]
    pub fn encode(&mut self, byte: u8) -> u8 {
        // Find position of `byte` in the list
        let mut pos = 0;
        while pos < ALPHABET_SIZE && self.list[pos] != byte {
            pos += 1;
        }

        // Move to front: shift everything right by 1 from position 0 to pos-1
        if pos > 0 {
            let ch = self.list[pos];
            // Shift right
            let mut i = pos;
            while i > 0 {
                self.list[i] = self.list[i - 1];
                i -= 1;
            }
            self.list[0] = ch;
        }

        pos as u8
    }

    /// Decode one MTF index: look up the character at position `index`,
    /// move it to front, return the character.
    #[inline]
    pub fn decode(&mut self, index: u8) -> u8 {
        let pos = index as usize;
        let ch = self.list[pos];

        // Move to front
        if pos > 0 {
            let mut i = pos;
            while i > 0 {
                self.list[i] = self.list[i - 1];
                i -= 1;
            }
            self.list[0] = ch;
        }

        ch
    }
}

/// Encode a block of BWT output through MTF.
///
/// `input` is the BWT output. `output` receives MTF indices.
/// `in_use` marks which byte values actually appear in the input.
///
/// Returns the number of distinct symbols used (n_in_use).
pub fn encode(input: &[u8], output: &mut [u8], in_use: &[bool; ALPHABET_SIZE]) -> usize {
    let (mut mtf, n_in_use) = Mtf::new_with_in_use(in_use);

    for i in 0..input.len() {
        output[i] = mtf.encode(input[i]);
    }

    n_in_use
}

/// Decode MTF indices back to byte values.
///
/// `input` contains MTF indices, `output` receives the decoded bytes.
pub fn decode(input: &[u8], output: &mut [u8], in_use: &[bool; ALPHABET_SIZE]) {
    let (mut mtf, _) = Mtf::new_with_in_use(in_use);

    for i in 0..input.len() {
        output[i] = mtf.decode(input[i]);
    }
}

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

    #[test]
    fn encode_decode_roundtrip() {
        let input = b"bananaaa";
        let mut in_use = [false; ALPHABET_SIZE];
        for &b in input.iter() {
            in_use[b as usize] = true;
        }

        let mut encoded = [0u8; 16];
        encode(input, &mut encoded, &in_use);

        let mut decoded = [0u8; 16];
        decode(&encoded[..input.len()], &mut decoded, &in_use);

        assert_eq!(&decoded[..input.len()], &input[..]);
    }

    #[test]
    fn repeated_chars_get_zeros() {
        // After MTF, repeated characters should produce runs of zeros.
        let input = [b'A'; 8];
        let mut in_use = [false; ALPHABET_SIZE];
        in_use[b'A' as usize] = true;

        let mut encoded = [0u8; 8];
        encode(&input, &mut encoded, &in_use);

        // First 'A' gets its initial position, all subsequent get 0.
        assert_eq!(encoded[0], 0); // 'A' is the only char, at position 0
        for i in 1..8 {
            assert_eq!(encoded[i], 0);
        }
    }
}