1use crate::ParseError;
6
7#[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 fn decode(bytes: &[u8], at_bit: usize) -> Result<(Self, usize), ParseError>;
27
28 fn encode<B: crate::Buffer>(
34 &self,
35 out: &mut BitWriter<'_, B, MSB>,
36 ) -> Result<(), crate::Overflow>;
37}
38
39const 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#[derive(Debug, Clone)]
47pub struct BitReader<'a, const MSB: bool> {
48 bytes: &'a [u8],
49 at: u64,
51}
52
53impl<'a, const MSB: bool> BitReader<'a, MSB> {
54 #[must_use]
58 pub const fn new(bytes: &'a [u8]) -> Self {
59 Self { bytes, at: 0 }
60 }
61
62 #[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 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 pub fn bit(&mut self) -> Result<bool, ParseError> {
108 Ok(self.read(1)? != 0)
109 }
110
111 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 #[must_use]
132 pub const fn position(&self) -> usize {
133 self.at as usize
134 }
135
136 #[must_use]
138 pub const fn bytes_consumed(&self) -> usize {
139 self.at.div_ceil(8) as usize
140 }
141}
142
143#[derive(Debug)]
147pub struct BitWriter<'a, B, const MSB: bool> {
148 out: &'a mut B,
149 base: usize,
151 used: u32,
153}
154
155impl<'a, B: crate::Buffer, const MSB: bool> BitWriter<'a, B, MSB> {
156 #[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 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 pub fn bit(&mut self, set: bool) -> Result<(), crate::Overflow> {
212 self.write(u64::from(set), 1)
213 }
214
215 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 #[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 fn sample(bits: u32) -> u64 {
265 let v = 0x9E37_79B9_7F4A_7C15u64;
266 if bits == 64 { v } else { v & mask64(bits) }
267 }
268
269 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 #[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 }
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}