gamut_webp/vp8l/
bit_io.rs

1//! VP8L bit I/O: an **LSB-first** bit stream (RFC 9649 §3.3).
2//!
3//! VP8L reads values least-significant-bit-first within each byte, which is the opposite order to
4//! [`gamut_bitstream::BitWriter`](https://docs.rs/gamut-bitstream)'s MSB-first `f(n)` fields. The
5//! reader ([`BitReader`], `ReadBits(n)`) and the matching writer ([`BitWriter`]) land here at
6//! milestone M0; if a second consumer (e.g. a future JPEG/JXL path) needs LSB-first bit I/O, this is
7//! a candidate to graduate into `gamut-bitstream`. Tracked in `../STATUS.md` section F.
8//!
9//! Per the spec, "the bytes are read in the natural order of the stream ... and bits of each byte
10//! are read in least-significant-bit-first order. When multiple bits are read at the same time, the
11//! integer is constructed from the original data in the original order." So `read_bits(2)` is
12//! equivalent to `read_bits(1) | (read_bits(1) << 1)`.
13
14use gamut_core::{Error, Result};
15
16/// The widest single field the format reads or writes at once (length/distance extra bits top out
17/// at 18, dimensions at 14); reads/writes beyond this are a caller bug.
18const MAX_BITS_PER_OP: u32 = 32;
19
20/// An LSB-first bit reader over a VP8L bitstream (RFC 9649 §3.3).
21///
22/// Bits are pulled a byte at a time into a small accumulator and handed out least-significant-bit
23/// first. Running past the end of the input is reported as [`Error::InvalidInput`] rather than
24/// panicking, so a truncated stream fails cleanly.
25#[derive(Debug, Clone)]
26pub struct BitReader<'a> {
27    /// The bytes backing the stream (the VP8L chunk payload, signature byte included).
28    data: &'a [u8],
29    /// Index of the next not-yet-buffered byte in `data`.
30    byte_pos: usize,
31    /// Buffered bits, right-aligned: the next bit to return is bit 0.
32    acc: u64,
33    /// Number of valid low bits currently in `acc` (always `< 8` between operations).
34    bits_in_acc: u32,
35}
36
37impl<'a> BitReader<'a> {
38    /// Creates a reader positioned at the start of `data`.
39    #[must_use]
40    pub fn new(data: &'a [u8]) -> Self {
41        Self {
42            data,
43            byte_pos: 0,
44            acc: 0,
45            bits_in_acc: 0,
46        }
47    }
48
49    /// Reads `n` bits (`0..=32`) LSB-first, returning them right-aligned in a `u32`.
50    ///
51    /// Reading 0 bits returns `Ok(0)` without consuming input (used by single-symbol prefix codes
52    /// that encode no bits).
53    ///
54    /// # Errors
55    ///
56    /// Returns [`Error::InvalidInput`] if fewer than `n` bits remain, or if `n > 32`.
57    pub fn read_bits(&mut self, n: u32) -> Result<u32> {
58        if n == 0 {
59            return Ok(0);
60        }
61        if n > MAX_BITS_PER_OP {
62            return Err(Error::InvalidInput("VP8L: bit read width out of range"));
63        }
64        while self.bits_in_acc < n {
65            let Some(&byte) = self.data.get(self.byte_pos) else {
66                return Err(Error::InvalidInput("VP8L: unexpected end of bitstream"));
67            };
68            self.acc |= u64::from(byte) << self.bits_in_acc;
69            self.bits_in_acc += 8;
70            self.byte_pos += 1;
71        }
72        let mask = (1u64 << n) - 1;
73        let value = (self.acc & mask) as u32;
74        self.acc >>= n;
75        self.bits_in_acc -= n;
76        Ok(value)
77    }
78
79    /// Reads a single bit (a convenience wrapper over [`read_bits`](Self::read_bits)).
80    ///
81    /// # Errors
82    ///
83    /// Returns [`Error::InvalidInput`] if no bits remain.
84    pub fn read_bit(&mut self) -> Result<u32> {
85        self.read_bits(1)
86    }
87
88    /// Total number of bits consumed so far.
89    #[must_use]
90    pub fn bits_consumed(&self) -> usize {
91        self.byte_pos * 8 - self.bits_in_acc as usize
92    }
93
94    /// Whether every bit of the input has been consumed (the trailing partial byte, if any, is
95    /// treated as zero padding and is not counted as remaining data).
96    #[must_use]
97    pub fn is_exhausted(&self) -> bool {
98        self.byte_pos >= self.data.len() && self.bits_in_acc == 0
99    }
100}
101
102/// An LSB-first bit writer (the encoder side of [`BitReader`]).
103///
104/// Bits accumulate low-to-high and are flushed a byte at a time; [`finish`](Self::finish)
105/// zero-pads the final partial byte. The writer is infallible (it grows a `Vec`).
106#[derive(Debug, Clone, Default)]
107pub struct BitWriter {
108    /// Completed bytes.
109    buf: Vec<u8>,
110    /// Pending bits, right-aligned.
111    acc: u64,
112    /// Number of valid low bits in `acc` (always `< 8` between operations).
113    bits_in_acc: u32,
114}
115
116impl BitWriter {
117    /// Creates an empty writer.
118    #[must_use]
119    pub fn new() -> Self {
120        Self::default()
121    }
122
123    /// Appends the low `n` bits (`0..=32`) of `value`, LSB-first. Bits of `value` above bit `n-1`
124    /// are ignored. `n > 32` or `n == 0` writes nothing.
125    pub fn write_bits(&mut self, value: u32, n: u32) {
126        if n == 0 || n > MAX_BITS_PER_OP {
127            return;
128        }
129        let mask = (1u64 << n) - 1;
130        self.acc |= (u64::from(value) & mask) << self.bits_in_acc;
131        self.bits_in_acc += n;
132        while self.bits_in_acc >= 8 {
133            self.buf.push((self.acc & 0xff) as u8);
134            self.acc >>= 8;
135            self.bits_in_acc -= 8;
136        }
137    }
138
139    /// Number of bits written so far (including any pending partial byte).
140    #[must_use]
141    pub fn bit_len(&self) -> usize {
142        self.buf.len() * 8 + self.bits_in_acc as usize
143    }
144
145    /// Flushes any partial trailing byte (zero-padding its high bits) and returns the bytes.
146    #[must_use]
147    pub fn finish(mut self) -> Vec<u8> {
148        if self.bits_in_acc > 0 {
149            self.buf.push((self.acc & 0xff) as u8);
150        }
151        self.buf
152    }
153}
154
155#[cfg(test)]
156mod tests {
157    use super::*;
158
159    #[test]
160    fn reads_lsb_first_within_a_byte() {
161        // 0b1011_0010 = 0xB2. LSB-first the bits are 0,1,0,0,1,1,0,1.
162        let mut r = BitReader::new(&[0xB2]);
163        assert_eq!(r.read_bits(1).unwrap(), 0);
164        assert_eq!(r.read_bits(1).unwrap(), 1);
165        assert_eq!(r.read_bits(2).unwrap(), 0b00); // next two bits: 0,0
166        assert_eq!(r.read_bits(4).unwrap(), 0b1011); // remaining: 1,1,0,1 -> 0b1011
167    }
168
169    #[test]
170    fn multi_bit_read_equals_single_bit_reads() {
171        // Spec equivalence: read_bits(2) == read_bits(1) | (read_bits(1) << 1).
172        let data = [0x9D, 0x01, 0x2A, 0xFF];
173        let mut a = BitReader::new(&data);
174        let mut b = BitReader::new(&data);
175        for _ in 0..10 {
176            let combined = a.read_bits(2).unwrap();
177            let lo = b.read_bits(1).unwrap();
178            let hi = b.read_bits(1).unwrap();
179            assert_eq!(combined, lo | (hi << 1));
180        }
181    }
182
183    #[test]
184    fn read_zero_bits_is_noop() {
185        let mut r = BitReader::new(&[0xFF]);
186        assert_eq!(r.read_bits(0).unwrap(), 0);
187        assert_eq!(r.bits_consumed(), 0);
188        assert_eq!(r.read_bits(8).unwrap(), 0xFF);
189    }
190
191    #[test]
192    fn crosses_byte_boundaries() {
193        // 0x2f signature byte then a 14-bit width-1 field, exactly as the VP8L header is laid out.
194        let mut w = BitWriter::new();
195        w.write_bits(0x2f, 8);
196        w.write_bits(16383, 14); // width - 1 (max)
197        w.write_bits(0, 14); // height - 1
198        let bytes = w.finish();
199        let mut r = BitReader::new(&bytes);
200        assert_eq!(r.read_bits(8).unwrap(), 0x2f);
201        assert_eq!(r.read_bits(14).unwrap(), 16383);
202        assert_eq!(r.read_bits(14).unwrap(), 0);
203    }
204
205    #[test]
206    fn out_of_data_is_invalid_input_not_panic() {
207        let mut r = BitReader::new(&[0xAB]);
208        assert_eq!(r.read_bits(8).unwrap(), 0xAB);
209        assert!(matches!(r.read_bits(1), Err(Error::InvalidInput(_))));
210        // Reading from empty input also fails cleanly.
211        let mut empty = BitReader::new(&[]);
212        assert!(matches!(empty.read_bits(1), Err(Error::InvalidInput(_))));
213    }
214
215    #[test]
216    fn oversized_read_is_rejected() {
217        let mut r = BitReader::new(&[0; 8]);
218        assert!(matches!(r.read_bits(33), Err(Error::InvalidInput(_))));
219    }
220
221    #[test]
222    fn writer_round_trips_varied_widths() {
223        let fields: &[(u32, u32)] = &[
224            (0, 1),
225            (1, 1),
226            (0b101, 3),
227            (0, 0),
228            (0x3FFF, 14),
229            (0xABCD, 16),
230            (0x00FF_FF00, 24),
231            (0xDEAD_BEEF, 32),
232            (7, 3),
233        ];
234        let mut w = BitWriter::new();
235        for &(v, n) in fields {
236            w.write_bits(v, n);
237        }
238        let total_bits: usize = fields.iter().map(|&(_, n)| n as usize).sum();
239        assert_eq!(w.bit_len(), total_bits);
240        let bytes = w.finish();
241        let mut r = BitReader::new(&bytes);
242        for &(v, n) in fields {
243            let masked = if n == 0 {
244                0
245            } else {
246                v & ((1u64 << n) - 1) as u32
247            };
248            assert_eq!(r.read_bits(n).unwrap(), masked, "field {v:#x}/{n}");
249        }
250    }
251
252    #[test]
253    fn partial_final_byte_is_zero_padded() {
254        let mut w = BitWriter::new();
255        w.write_bits(0b1, 1); // a single set bit, then 7 pad bits
256        let bytes = w.finish();
257        assert_eq!(bytes, vec![0b0000_0001]);
258    }
259
260    #[test]
261    fn consumed_and_exhausted_track_position() {
262        let mut r = BitReader::new(&[0xFF, 0x0F]);
263        assert!(!r.is_exhausted());
264        r.read_bits(12).unwrap();
265        assert_eq!(r.bits_consumed(), 12);
266        assert!(!r.is_exhausted());
267        r.read_bits(4).unwrap();
268        assert_eq!(r.bits_consumed(), 16);
269        assert!(r.is_exhausted());
270    }
271}
gamut_webp/vp8l/bit_io.rs

gamut_webp/vp8l/
bit_io.rs
