tinybz2 0.1.2

Minimal-memory bz2 compressor/decompressor for embedded targets
Documentation
//! RLE1 — Initial run-length encoding.
//!
//! bz2's first compression stage replaces runs of 4 or more identical bytes
//! with exactly 4 copies followed by a repeat-count byte (0..255), encoding
//! runs of 4..259 identical bytes.
//!
//! Example: `AAAAAAA` (7 × 'A') → `AAAA\x03` (4 copies + count 3)
//!
//! This stage operates in-place on the block buffer and uses O(1) extra memory.

use crate::error::Error;

/// Encode RLE1 from `input` into `output`.
///
/// Returns the number of bytes written to `output`.
/// `output` must be large enough (worst case: same size as input for
/// data with no runs; for data with many runs the output is smaller).
pub fn encode(input: &[u8], output: &mut [u8]) -> Result<usize, Error> {
    let mut out_pos = 0;
    let mut i = 0;
    let len = input.len();

    while i < len {
        let ch = input[i];
        let mut run_len = 1usize;

        // Count consecutive identical bytes
        while i + run_len < len && input[i + run_len] == ch && run_len < 259 {
            run_len += 1;
        }

        if run_len >= 4 {
            // Emit 4 copies of the byte
            if out_pos + 5 > output.len() {
                return Err(Error::OutputOverflow);
            }
            output[out_pos] = ch;
            output[out_pos + 1] = ch;
            output[out_pos + 2] = ch;
            output[out_pos + 3] = ch;
            output[out_pos + 4] = (run_len - 4) as u8;
            out_pos += 5;
            i += run_len;
        } else {
            // Emit bytes literally
            for _ in 0..run_len {
                if out_pos >= output.len() {
                    return Err(Error::OutputOverflow);
                }
                output[out_pos] = ch;
                out_pos += 1;
            }
            i += run_len;
        }
    }

    Ok(out_pos)
}

/// Decode RLE1 from `input` into `output`.
///
/// Returns the number of bytes written to `output`.
pub fn decode(input: &[u8], output: &mut [u8], max_output: usize) -> Result<usize, Error> {
    let mut out_pos = 0;
    let mut i = 0;
    let len = input.len();

    while i < len {
        let ch = input[i];

        // Check if this starts a run (4 identical bytes)
        if i + 3 < len && input[i + 1] == ch && input[i + 2] == ch && input[i + 3] == ch {
            // Read repeat count
            if i + 4 >= len {
                return Err(Error::UnexpectedEof);
            }
            let repeat = input[i + 4] as usize;
            let total = 4 + repeat;

            if out_pos + total > max_output {
                return Err(Error::RleOverflow);
            }
            if out_pos + total > output.len() {
                return Err(Error::OutputOverflow);
            }

            for _ in 0..total {
                output[out_pos] = ch;
                out_pos += 1;
            }
            i += 5;
        } else {
            // Literal byte
            if out_pos >= max_output || out_pos >= output.len() {
                return Err(Error::RleOverflow);
            }
            output[out_pos] = ch;
            out_pos += 1;
            i += 1;
        }
    }

    Ok(out_pos)
}

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

    #[test]
    fn encode_no_runs() {
        let input = b"ABCDEF";
        let mut output = [0u8; 16];
        let n = encode(input, &mut output).unwrap();
        assert_eq!(&output[..n], b"ABCDEF");
    }

    #[test]
    fn encode_short_run() {
        // 3 identical bytes → literal (not a run)
        let input = b"AAA";
        let mut output = [0u8; 16];
        let n = encode(input, &mut output).unwrap();
        assert_eq!(&output[..n], b"AAA");
    }

    #[test]
    fn encode_exact_four() {
        let input = b"AAAA";
        let mut output = [0u8; 16];
        let n = encode(input, &mut output).unwrap();
        assert_eq!(n, 5);
        assert_eq!(&output[..5], &[b'A', b'A', b'A', b'A', 0]);
    }

    #[test]
    fn encode_longer_run() {
        // 7 × 'A' → AAAA\x03
        let input = [b'A'; 7];
        let mut output = [0u8; 16];
        let n = encode(&input, &mut output).unwrap();
        assert_eq!(n, 5);
        assert_eq!(&output[..5], &[b'A', b'A', b'A', b'A', 3]);
    }

    #[test]
    fn roundtrip() {
        let input = b"AAAAAABBCCCCCDDDDDDDD";
        let mut encoded = [0u8; 64];
        let enc_len = encode(input, &mut encoded).unwrap();

        let mut decoded = [0u8; 64];
        let dec_len = decode(&encoded[..enc_len], &mut decoded, 64).unwrap();
        assert_eq!(&decoded[..dec_len], &input[..]);
    }
}