tinybz2 0.1.1

Minimal-memory bz2 compressor/decompressor for embedded targets
Documentation
//! Bit-level I/O for reading and writing bz2 bitstreams.
//!
//! bz2 is a bit-oriented format — Huffman codes and many header fields
//! are not byte-aligned. These types provide efficient bit-at-a-time
//! and multi-bit access over byte slices, with no allocation.

use crate::error::Error;

// ── Bit Reader ─────────────────────────────────────────────────────────────

/// Reads bits from a byte slice, MSB-first (big-endian bit order),
/// which is what bz2 uses.
pub struct BitReader<'a> {
    data: &'a [u8],
    /// Byte position in `data`.
    byte_pos: usize,
    /// Bits remaining in the current accumulator (0..=64).
    bits_left: u32,
    /// Accumulator holding pre-fetched bits, left-aligned.
    accum: u64,
}

impl<'a> BitReader<'a> {
    /// Create a new reader over the given byte slice.
    pub fn new(data: &'a [u8]) -> Self {
        let mut reader = Self {
            data,
            byte_pos: 0,
            bits_left: 0,
            accum: 0,
        };
        reader.refill();
        reader
    }

    /// Refill the accumulator from the byte stream.
    #[inline]
    fn refill(&mut self) {
        while self.bits_left <= 56 && self.byte_pos < self.data.len() {
            self.accum |= (self.data[self.byte_pos] as u64) << (56 - self.bits_left);
            self.byte_pos += 1;
            self.bits_left += 8;
        }
    }

    /// Read up to 32 bits. Bits are returned right-aligned.
    #[inline]
    pub fn read_bits(&mut self, n: u32) -> Result<u32, Error> {
        debug_assert!(n <= 32);
        if n == 0 {
            return Ok(0);
        }
        if self.bits_left < n {
            self.refill();
            if self.bits_left < n {
                return Err(Error::UnexpectedEof);
            }
        }
        let val = (self.accum >> (64 - n)) as u32;
        self.accum <<= n;
        self.bits_left -= n;
        Ok(val)
    }

    /// Read a single bit (0 or 1).
    #[inline]
    pub fn read_bit(&mut self) -> Result<u8, Error> {
        Ok(self.read_bits(1)? as u8)
    }

    /// Read a boolean (1 = true, 0 = false).
    #[inline]
    pub fn read_bool(&mut self) -> Result<bool, Error> {
        Ok(self.read_bits(1)? != 0)
    }

    /// Read an unsigned 8-bit value.
    #[inline]
    pub fn read_u8(&mut self) -> Result<u8, Error> {
        Ok(self.read_bits(8)? as u8)
    }

    /// Read an unsigned 16-bit value.
    #[inline]
    pub fn read_u16(&mut self) -> Result<u16, Error> {
        Ok(self.read_bits(16)? as u16)
    }

    /// Read an unsigned 32-bit value.
    #[inline]
    pub fn read_u32(&mut self) -> Result<u32, Error> {
        self.read_bits(32)
    }

    /// Total bits consumed so far.
    pub fn bits_consumed(&self) -> usize {
        self.byte_pos * 8 - self.bits_left as usize
    }

    /// Check if we've reached the end of input.
    pub fn is_empty(&self) -> bool {
        self.bits_left == 0 && self.byte_pos >= self.data.len()
    }
}

// ── Bit Writer ─────────────────────────────────────────────────────────────

/// Writes bits to a byte slice, MSB-first.
pub struct BitWriter<'a> {
    data: &'a mut [u8],
    /// Next byte position to write.
    byte_pos: usize,
    /// Accumulator for partial byte, left-aligned.
    accum: u8,
    /// Number of bits accumulated in `accum` (0..8).
    bits_used: u32,
}

impl<'a> BitWriter<'a> {
    /// Create a new writer over the given output buffer.
    pub fn new(data: &'a mut [u8]) -> Self {
        Self {
            data,
            byte_pos: 0,
            accum: 0,
            bits_used: 0,
        }
    }

    /// Flush the accumulator to the byte stream.
    #[inline]
    fn flush_byte(&mut self) -> Result<(), Error> {
        if self.byte_pos >= self.data.len() {
            return Err(Error::OutputOverflow);
        }
        self.data[self.byte_pos] = self.accum;
        self.byte_pos += 1;
        self.accum = 0;
        self.bits_used = 0;
        Ok(())
    }

    /// Write up to 32 bits. Bits are taken from the low `n` bits of `val`.
    pub fn write_bits(&mut self, n: u32, val: u32) -> Result<(), Error> {
        debug_assert!(n <= 32);
        if n == 0 {
            return Ok(());
        }

        let mut remaining = n;
        let mut value = val;

        while remaining > 0 {
            let space = 8 - self.bits_used;
            let chunk = if remaining < space { remaining } else { space };

            // Extract the top `chunk` bits from `value` (shifted to be the
            // most-significant `remaining` bits).
            let shift = remaining - chunk;
            let bits = ((value >> shift) & ((1 << chunk) - 1)) as u8;
            value &= (1u32 << shift).wrapping_sub(1); // mask off consumed bits

            self.accum |= bits << (space - chunk);
            self.bits_used += chunk;
            remaining -= chunk;

            if self.bits_used == 8 {
                self.flush_byte()?;
            }
        }
        Ok(())
    }

    /// Write a single bit.
    #[inline]
    pub fn write_bit(&mut self, bit: u8) -> Result<(), Error> {
        self.write_bits(1, bit as u32)
    }

    /// Write a boolean as a single bit.
    #[inline]
    pub fn write_bool(&mut self, val: bool) -> Result<(), Error> {
        self.write_bits(1, val as u32)
    }

    /// Write an unsigned 8-bit value.
    #[inline]
    pub fn write_u8(&mut self, val: u8) -> Result<(), Error> {
        self.write_bits(8, val as u32)
    }

    /// Write an unsigned 16-bit value.
    #[inline]
    pub fn write_u16(&mut self, val: u16) -> Result<(), Error> {
        self.write_bits(16, val as u32)
    }

    /// Write an unsigned 32-bit value.
    #[inline]
    pub fn write_u32(&mut self, val: u32) -> Result<(), Error> {
        self.write_bits(32, val)
    }

    /// Finalize: flush any remaining partial byte (zero-padded).
    /// Returns total bytes written.
    pub fn finish(mut self) -> Result<usize, Error> {
        if self.bits_used > 0 {
            self.flush_byte()?;
        }
        Ok(self.byte_pos)
    }

    /// Total bytes written so far (not including partial byte).
    pub fn bytes_written(&self) -> usize {
        self.byte_pos
    }

    /// Total bits written so far.
    pub fn bits_written(&self) -> usize {
        self.byte_pos * 8 + self.bits_used as usize
    }
}

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

    #[test]
    fn roundtrip_bits() {
        let mut buf = [0u8; 16];
        {
            let mut w = BitWriter::new(&mut buf);
            w.write_bits(3, 0b101).unwrap();
            w.write_bits(5, 0b01100).unwrap();
            w.write_bits(8, 0xFF).unwrap();
            w.write_bits(1, 1).unwrap();
            w.finish().unwrap();
        }
        let mut r = BitReader::new(&buf);
        assert_eq!(r.read_bits(3).unwrap(), 0b101);
        assert_eq!(r.read_bits(5).unwrap(), 0b01100);
        assert_eq!(r.read_bits(8).unwrap(), 0xFF);
        assert_eq!(r.read_bits(1).unwrap(), 1);
    }

    #[test]
    fn roundtrip_32bit() {
        let mut buf = [0u8; 8];
        {
            let mut w = BitWriter::new(&mut buf);
            w.write_u32(0xDEADBEEF).unwrap();
            w.finish().unwrap();
        }
        let mut r = BitReader::new(&buf);
        assert_eq!(r.read_u32().unwrap(), 0xDEADBEEF);
    }
}