Skip to main content

layline_core/
bits.rs

1//! Bit cursors for reading and writing bit fields.
2//!
3//! `MSB = true` fills each byte from the top bit down. A field is at most 64 bits wide.
4
5use crate::ParseError;
6
7/// A value whose width in bits is read from the wire.
8///
9/// The bit-level [`VarCodec`](crate::VarCodec). A `#[var]` field in a `#[message(bits)]` uses one.
10#[diagnostic::on_unimplemented(
11    message = "`{Self}` is not a `BitCodec` for this message's bit order",
12    label = "wrong bit order, or not a `BitCodec` at all",
13    note = "a coding that reads the top of each byte first implements `BitCodec<true>`, \
14            and one that reads the bottom first implements `BitCodec<false>`. \
15            Change the message's `order`, or use a coding for this order"
16)]
17pub trait BitCodec<const MSB: bool>: Sized {
18    /// Decode from bit `at_bit` of `bytes`. Returns the value and the bits consumed.
19    ///
20    /// A successful decode must consume at least one bit.
21    ///
22    /// # Errors
23    ///
24    /// [`ParseError::Short`] if the bytes end inside the value, [`ParseError::Malformed`] if the
25    /// value is too wide for `Self`.
26    fn decode(bytes: &[u8], at_bit: usize) -> Result<(Self, usize), ParseError>;
27
28    /// Write this value to the bit cursor.
29    ///
30    /// # Errors
31    ///
32    /// [`Overflow`](crate::Overflow) if the buffer has no room.
33    fn encode<B: crate::Buffer>(
34        &self,
35        out: &mut BitWriter<'_, B, MSB>,
36    ) -> Result<(), crate::Overflow>;
37}
38
39/// The low `n` bits set, for `n <= 8`. Avoids `mask64`'s branch in the inner loop.
40const fn chunk_mask(n: u32) -> u64 {
41    debug_assert!(n <= 8, "a chunk is at most one byte wide");
42    (1u64 << n) - 1
43}
44
45/// A bit cursor that reads from a byte slice.
46#[derive(Debug, Clone)]
47pub struct BitReader<'a, const MSB: bool> {
48    bytes: &'a [u8],
49    /// Bits read so far.
50    at: u64,
51}
52
53impl<'a, const MSB: bool> BitReader<'a, MSB> {
54    /// A cursor at the first bit of `bytes`.
55    ///
56    /// `MSB` is `true` to read the top of each byte first.
57    #[must_use]
58    pub const fn new(bytes: &'a [u8]) -> Self {
59        Self { bytes, at: 0 }
60    }
61
62    /// A cursor at bit `at_bit` of `bytes`. A position past the end reads as [`Short`](ParseError::Short).
63    #[must_use]
64    pub const fn at(bytes: &'a [u8], at_bit: usize) -> Self {
65        Self { bytes, at: at_bit as u64 }
66    }
67
68    /// Read the next `bits` bits as an integer.
69    ///
70    /// # Errors
71    ///
72    /// [`ParseError::Short`] if the slice ends inside the field. `at` is the field's first byte.
73    pub fn read(&mut self, bits: u32) -> Result<u64, ParseError> {
74        debug_assert!(bits <= 64, "a bit field is at most 64 bits wide");
75        let end = self.at.saturating_add(u64::from(bits));
76        let need = usize::try_from(end.div_ceil(8)).unwrap_or(usize::MAX);
77        if need > self.bytes.len() {
78            return Err(ParseError::Short {
79                need_bytes: need,
80                got_bytes: self.bytes.len(),
81                at: (self.at / 8) as usize,
82            });
83        }
84        let mut value = 0u64;
85        let mut left = bits;
86        while left > 0 {
87            let byte = u64::from(self.bytes[(self.at / 8) as usize]);
88            let used = (self.at % 8) as u32;
89            let free = 8 - used;
90            let take = if left < free { left } else { free };
91            if MSB {
92                value = (value << take) | ((byte >> (free - take)) & chunk_mask(take));
93            } else {
94                value |= ((byte >> used) & chunk_mask(take)) << (bits - left);
95            }
96            self.at += u64::from(take);
97            left -= take;
98        }
99        Ok(value)
100    }
101
102    /// Read the next bit.
103    ///
104    /// # Errors
105    ///
106    /// [`ParseError::Short`] if the slice ends first.
107    pub fn bit(&mut self) -> Result<bool, ParseError> {
108        Ok(self.read(1)? != 0)
109    }
110
111    /// Skip `bits` bits.
112    ///
113    /// # Errors
114    ///
115    /// [`ParseError::Short`] if the slice ends inside them. `at` is the first skipped byte.
116    pub fn skip(&mut self, bits: usize) -> Result<(), ParseError> {
117        let end = self.at.saturating_add(bits as u64);
118        let need = usize::try_from(end.div_ceil(8)).unwrap_or(usize::MAX);
119        if need > self.bytes.len() {
120            return Err(ParseError::Short {
121                need_bytes: need,
122                got_bytes: self.bytes.len(),
123                at: (self.at / 8) as usize,
124            });
125        }
126        self.at = end;
127        Ok(())
128    }
129
130    /// Bits read so far.
131    #[must_use]
132    pub const fn position(&self) -> usize {
133        self.at as usize
134    }
135
136    /// Bytes touched so far, counting a partly read byte.
137    #[must_use]
138    pub const fn bytes_consumed(&self) -> usize {
139        self.at.div_ceil(8) as usize
140    }
141}
142
143/// A bit cursor that appends to a [`Buffer`](crate::Buffer).
144///
145/// Unused bits in the last byte are zero.
146#[derive(Debug)]
147pub struct BitWriter<'a, B, const MSB: bool> {
148    out: &'a mut B,
149    /// The buffer's length in bytes when the cursor was created.
150    base: usize,
151    /// Bits used in the last byte, `0..8`.
152    used: u32,
153}
154
155impl<'a, B: crate::Buffer, const MSB: bool> BitWriter<'a, B, MSB> {
156    /// A cursor at the end of `out`.
157    ///
158    /// `MSB` is `true` to fill the top of each byte first.
159    #[must_use]
160    pub fn new(out: &'a mut B) -> Self {
161        let base = out.len();
162        Self { out, base, used: 0 }
163    }
164
165    /// Append the low `bits` bits of `value`.
166    ///
167    /// # Errors
168    ///
169    /// [`Overflow`](crate::Overflow) if a new byte does not fit. The cursor and buffer are unchanged.
170    pub fn write(&mut self, value: u64, bits: u32) -> Result<(), crate::Overflow> {
171        let (len, used) = (self.out.len(), self.used);
172        let result = self.append(value, bits);
173        if result.is_err() {
174            self.out.rewind(len);
175            self.used = used;
176            if let (1.., Some(last)) = (used, self.out.written_mut().last_mut()) {
177                *last &= if MSB { 0xFF << (8 - used) } else { (1 << used) - 1 };
178            }
179        }
180        result
181    }
182
183    fn append(&mut self, value: u64, bits: u32) -> Result<(), crate::Overflow> {
184        debug_assert!(bits <= 64, "a bit field is at most 64 bits wide");
185        let mut left = bits;
186        while left > 0 {
187            if self.used == 0 {
188                self.out.push(&[0])?;
189            }
190            let free = 8 - self.used;
191            let take = if left < free { left } else { free };
192            let chunk = if MSB {
193                (((value >> (left - take)) & chunk_mask(take)) as u8) << (free - take)
194            } else {
195                (((value >> (bits - left)) & chunk_mask(take)) as u8) << self.used
196            };
197            let last =
198                self.out.written_mut().last_mut().expect("a byte was pushed for the free bits");
199            *last |= chunk;
200            self.used = (self.used + take) % 8;
201            left -= take;
202        }
203        Ok(())
204    }
205
206    /// Append one bit.
207    ///
208    /// # Errors
209    ///
210    /// As [`write`](Self::write).
211    pub fn bit(&mut self, set: bool) -> Result<(), crate::Overflow> {
212        self.write(u64::from(set), 1)
213    }
214
215    /// Overwrite `bits` bits at `at_bit`. Those bits must already be written.
216    pub fn patch(&mut self, at_bit: usize, bits: u32, value: u64) {
217        debug_assert!(bits <= 64, "a bit field is at most 64 bits wide");
218        debug_assert!(
219            at_bit + bits as usize <= self.position(),
220            "a patch lies inside the bits already written"
221        );
222        let base = self.base;
223        let bytes = self.out.written_mut();
224        let mut at = at_bit as u64;
225        let mut left = bits;
226        while left > 0 {
227            let used = (at % 8) as u32;
228            let free = 8 - used;
229            let take = if left < free { left } else { free };
230            let (chunk, hole) = if MSB {
231                let shift = free - take;
232                (
233                    (((value >> (left - take)) & chunk_mask(take)) as u8) << shift,
234                    (chunk_mask(take) as u8) << shift,
235                )
236            } else {
237                (
238                    (((value >> (bits - left)) & chunk_mask(take)) as u8) << used,
239                    (chunk_mask(take) as u8) << used,
240                )
241            };
242            let byte = &mut bytes[base + (at / 8) as usize];
243            *byte = (*byte & !hole) | chunk;
244            at += u64::from(take);
245            left -= take;
246        }
247    }
248
249    /// Bits written so far.
250    #[must_use]
251    pub fn position(&self) -> usize {
252        (self.out.len() - self.base) * 8 - if self.used == 0 { 0 } else { 8 - self.used as usize }
253    }
254}
255
256#[cfg(all(test, feature = "alloc"))]
257mod tests {
258    use super::*;
259    use crate::Buffer;
260    use crate::mask::mask64;
261    use alloc::vec::Vec;
262
263    /// A mixed bit pattern, cut to `bits`.
264    fn sample(bits: u32) -> u64 {
265        let v = 0x9E37_79B9_7F4A_7C15u64;
266        if bits == 64 { v } else { v & mask64(bits) }
267    }
268
269    /// The bytes written for a sequence of `(value, bits)` fields.
270    fn written<const MSB: bool>(runs: &[(u64, u32)]) -> Vec<u8> {
271        let mut out = Vec::new();
272        let mut w = BitWriter::<_, MSB>::new(&mut out);
273        for (value, bits) in runs {
274            w.write(*value, *bits).unwrap();
275        }
276        out
277    }
278
279    #[test]
280    fn every_width_at_every_offset_round_trips_in_both_orders() {
281        fn each<const MSB: bool>() {
282            for offset in 0..=7u32 {
283                for bits in 1..=64u32 {
284                    let value = sample(bits);
285                    let bytes = written::<MSB>(&[(mask64(offset), offset), (value, bits)]);
286                    assert_eq!(
287                        bytes.len(),
288                        ((offset + bits) as usize).div_ceil(8),
289                        "msb={MSB} offset={offset} bits={bits}"
290                    );
291
292                    let mut r = BitReader::<MSB>::new(&bytes);
293                    if offset > 0 {
294                        assert_eq!(r.read(offset).unwrap(), mask64(offset));
295                    }
296                    assert_eq!(
297                        r.read(bits).unwrap(),
298                        value,
299                        "msb={MSB} offset={offset} bits={bits}"
300                    );
301                    assert_eq!(r.bytes_consumed(), bytes.len());
302                }
303            }
304        }
305        each::<false>();
306        each::<true>();
307    }
308
309    #[test]
310    fn a_nibble_pair_lands_at_the_end_of_the_byte_the_order_names() {
311        assert_eq!(written::<true>(&[(0xA, 4), (0x5, 4)]), [0xA5]);
312        assert_eq!(written::<false>(&[(0xA, 4), (0x5, 4)]), [0x5A]);
313    }
314
315    #[test]
316    fn a_field_across_a_byte_boundary_keeps_its_order() {
317        assert_eq!(written::<true>(&[(0b101, 3), (0b1_1000_0110, 9)]), [0b1011_1000, 0b0110_0000]);
318
319        let mut r = BitReader::<true>::new(&[0b1011_1000, 0b0110_0000]);
320        assert_eq!(r.read(3).unwrap(), 0b101);
321        assert_eq!(r.read(9).unwrap(), 0b1_1000_0110);
322    }
323
324    #[test]
325    fn the_pad_is_zero_and_the_reader_ignores_it() {
326        let bytes = written::<true>(&[(0b1011_0011_0011, 13)]);
327        assert_eq!(bytes.len(), 2);
328        assert_eq!(bytes[1] & 0b111, 0, "the last three bits are the pad");
329
330        let mut r = BitReader::<true>::new(&bytes);
331        assert_eq!(r.read(13).unwrap(), 0b1011_0011_0011);
332        assert_eq!(r.bytes_consumed(), 2);
333    }
334
335    #[test]
336    fn a_bit_at_a_time_is_the_same_wire_as_a_field() {
337        fn each<const MSB: bool>() {
338            let mut out = Vec::new();
339            let mut w = BitWriter::<_, MSB>::new(&mut out);
340            for i in 0..12 {
341                w.bit(i % 3 == 0).unwrap();
342            }
343            let mut r = BitReader::<MSB>::new(&out);
344            for i in 0..12 {
345                assert_eq!(r.bit().unwrap(), i % 3 == 0, "msb={MSB} bit={i}");
346            }
347        }
348        each::<false>();
349        each::<true>();
350    }
351
352    /// A test coding: three bits of width, then that many bits of value.
353    #[derive(Debug, Clone, Copy, PartialEq, Eq)]
354    struct Widthed<const MSB: bool>(u64, u32);
355
356    impl<const MSB: bool> BitCodec<MSB> for Widthed<MSB> {
357        fn decode(bytes: &[u8], at_bit: usize) -> Result<(Self, usize), ParseError> {
358            let mut r = BitReader::<MSB>::at(bytes, at_bit);
359            let width = r.read(3)? as u32;
360            let value = if width == 0 { 0 } else { r.read(width)? };
361            Ok((Self(value, width), r.position() - at_bit))
362        }
363
364        fn encode<B: Buffer>(
365            &self,
366            out: &mut BitWriter<'_, B, MSB>,
367        ) -> Result<(), crate::Overflow> {
368            out.write(u64::from(self.1), 3)?;
369            out.write(self.0, self.1)
370        }
371    }
372
373    #[test]
374    fn a_bit_codec_round_trips_at_every_start_offset_in_both_orders() {
375        fn each<const MSB: bool>() {
376            for offset in 0..=7u32 {
377                for width in 0..=7u32 {
378                    let value = Widthed::<MSB>(sample(width), width);
379                    let mut out = Vec::new();
380                    let mut w = BitWriter::<_, MSB>::new(&mut out);
381                    w.write(mask64(offset), offset).unwrap();
382                    let at = w.position();
383                    value.encode(&mut w).unwrap();
384                    let used = w.position() - at;
385                    assert_eq!(used, 3 + width as usize, "offset={offset} width={width}");
386                    w.write(0, 7).unwrap();
387                    assert_eq!(
388                        Widthed::<MSB>::decode(&out, at),
389                        Ok((value, used)),
390                        "offset={offset} width={width}"
391                    );
392                }
393            }
394        }
395        each::<true>();
396        each::<false>();
397    }
398
399    #[test]
400    fn a_coding_reads_one_end_of_the_byte_and_says_so_in_its_type() {
401        fn msb_only<T: BitCodec<true>>() {}
402        fn lsb_only<T: BitCodec<false>>() {}
403        msb_only::<Widthed<true>>();
404        lsb_only::<Widthed<false>>();
405        #[cfg(feature = "num")]
406        msb_only::<crate::num::ExpGolomb>();
407        // `lsb_only::<ExpGolomb>()` does not compile: the coding reads the top of each byte.
408    }
409
410    #[test]
411    fn a_patch_rewrites_its_own_bits_and_leaves_the_bits_either_side_of_it() {
412        fn each<const MSB: bool>() {
413            let mut out = Vec::new();
414            let mut w = BitWriter::<_, MSB>::new(&mut out);
415            w.write(mask64(5), 5).unwrap();
416            let at = w.position();
417            w.write(0, 6).unwrap();
418            w.write(mask64(9), 9).unwrap();
419            assert_eq!(w.position(), 20);
420            w.patch(at, 6, 0b10_1101);
421
422            let mut r = BitReader::<MSB>::new(&out);
423            assert_eq!(r.read(5).unwrap(), mask64(5));
424            assert_eq!(r.read(6).unwrap(), 0b10_1101);
425            assert_eq!(r.read(9).unwrap(), mask64(9));
426        }
427        each::<false>();
428        each::<true>();
429    }
430
431    #[test]
432    fn a_patch_clears_the_bits_the_new_value_does_not_set() {
433        fn each<const MSB: bool>() {
434            let mut out = Vec::new();
435            let mut w = BitWriter::<_, MSB>::new(&mut out);
436            w.write(u64::MAX, 12).unwrap();
437            w.patch(2, 8, 0);
438            let mut r = BitReader::<MSB>::new(&out);
439            assert_eq!(r.read(2).unwrap(), 0b11);
440            assert_eq!(r.read(8).unwrap(), 0);
441            assert_eq!(r.read(2).unwrap(), 0b11);
442        }
443        each::<false>();
444        each::<true>();
445    }
446
447    #[test]
448    fn a_cursor_over_a_buffer_with_bytes_in_it_writes_and_patches_past_them() {
449        let mut out = alloc::vec![0xAAu8, 0xBB];
450        let mut w = BitWriter::<_, true>::new(&mut out);
451        w.write(0b1111, 4).unwrap();
452        w.write(0, 4).unwrap();
453        w.patch(4, 4, 0b0101);
454        assert_eq!(out, [0xAA, 0xBB, 0xF5]);
455    }
456
457    #[test]
458    fn a_cursor_over_a_full_fixed_buffer_refuses_the_write() {
459        let mut room = [0u8; 1];
460        let mut out = crate::Fixed::new(&mut room);
461        let mut w = BitWriter::<_, true>::new(&mut out);
462        assert_eq!(w.write(0, 8), Ok(()));
463        assert_eq!(w.write(0, 1), Err(crate::Overflow));
464    }
465
466    #[test]
467    fn a_refused_write_leaves_the_cursor_and_the_bytes_as_they_were() {
468        fn each<const MSB: bool>(before: u8) {
469            let mut room = [0u8; 2];
470            let mut out = crate::Fixed::new(&mut room);
471            let mut w = BitWriter::<_, MSB>::new(&mut out);
472            w.write(0b101, 3).unwrap();
473            assert_eq!(w.write(u64::MAX, 20), Err(crate::Overflow));
474            assert_eq!(w.position(), 3, "msb={MSB}");
475            w.write(0, 5).unwrap();
476            assert_eq!(out.written(), [before], "msb={MSB}");
477        }
478        each::<true>(0b1010_0000);
479        each::<false>(0b0000_0101);
480    }
481
482    #[test]
483    fn a_hostile_position_reads_short_instead_of_overflowing() {
484        let mut r = BitReader::<true>::at(&[0, 0], usize::MAX);
485        assert!(matches!(r.read(8), Err(ParseError::Short { .. })));
486        let mut r = BitReader::<true>::new(&[0, 0]);
487        r.read(1).unwrap();
488        assert!(matches!(r.skip(usize::MAX), Err(ParseError::Short { .. })));
489    }
490
491    #[test]
492    fn a_cursor_reports_the_bits_it_has_read_and_steps_over_the_bits_it_skips() {
493        let bytes = [0b1010_1010u8, 0b0101_0101];
494        let mut r = BitReader::<true>::new(&bytes);
495        assert_eq!(r.position(), 0);
496        r.skip(5).unwrap();
497        assert_eq!(r.position(), 5);
498        assert_eq!(r.read(3).unwrap(), 0b010);
499        assert_eq!(r.bytes_consumed(), 1);
500        assert_eq!(
501            r.skip(9).unwrap_err(),
502            ParseError::Short { need_bytes: 3, got_bytes: 2, at: 1 }
503        );
504    }
505
506    #[test]
507    fn a_read_past_the_end_reports_the_byte_it_began_in() {
508        let bytes = [0xFFu8, 0x0F];
509        let mut r = BitReader::<true>::new(&bytes);
510        assert_eq!(r.read(12).unwrap(), 0xFF0);
511        assert_eq!(
512            r.read(8).unwrap_err(),
513            ParseError::Short { need_bytes: 3, got_bytes: 2, at: 1 }
514        );
515    }
516
517    #[test]
518    fn a_value_above_its_width_is_cut_to_it() {
519        assert_eq!(written::<true>(&[(u64::MAX, 5), (0, 3)]), [0b1111_1000]);
520        assert_eq!(written::<false>(&[(u64::MAX, 5), (0, 3)]), [0b0001_1111]);
521    }
522}