use crate::error::{Error, Result};
const COORD_INTEGER_BITS: usize = 14;
const COORD_FRACTIONAL_BITS: usize = 5;
const COORD_DENOMINATOR: f32 = (1 << COORD_FRACTIONAL_BITS) as f32;
const COORD_RESOLUTION: f32 = 1.0 / COORD_DENOMINATOR;
const NORMAL_FRACTIONAL_BITS: usize = 11;
const NORMAL_DENOMINATOR: f32 = ((1 << NORMAL_FRACTIONAL_BITS) - 1) as f32;
const NORMAL_RESOLUTION: f32 = 1.0 / NORMAL_DENOMINATOR;
pub struct BitReader<'a> {
data: &'a [u8],
position: usize,
total_bits: usize,
}
impl<'a> BitReader<'a> {
#[inline]
pub fn new(data: &'a [u8]) -> Self {
Self {
data,
position: 0,
total_bits: data.len() * 8,
}
}
#[inline]
pub fn bits_remaining(&self) -> usize {
self.total_bits.saturating_sub(self.position)
}
#[inline]
pub fn position(&self) -> usize {
self.position
}
#[inline]
pub fn data(&self) -> &'a [u8] {
self.data
}
#[inline]
pub fn read_bits(&mut self, n: usize) -> Result<u64> {
if n == 0 {
return Ok(0);
}
if n > 64 || self.position + n > self.total_bits {
return Err(Error::Overflow {
needed: n,
available: self.bits_remaining(),
});
}
let value = self.peek_bits_unchecked(n);
self.position += n;
Ok(value)
}
#[inline]
pub fn peek_bits(&self, n: usize) -> Result<u64> {
if n == 0 {
return Ok(0);
}
if n > 64 || self.position + n > self.total_bits {
return Err(Error::Overflow {
needed: n,
available: self.bits_remaining(),
});
}
Ok(self.peek_bits_unchecked(n))
}
#[inline(always)]
fn peek_bits_unchecked(&self, n: usize) -> u64 {
let byte_pos = self.position / 8;
let bit_offset = self.position % 8;
let remaining_bytes = self.data.len() - byte_pos;
let word = if remaining_bytes >= 8 {
u64::from_le_bytes(
self.data[byte_pos..byte_pos + 8]
.try_into()
.expect("slice has exactly eight bytes"),
)
} else {
self.data[byte_pos..]
.iter()
.enumerate()
.fold(0u64, |word, (i, &byte)| word | (byte as u64) << (i * 8))
};
let low = word >> bit_offset;
if bit_offset + n <= 64 {
return low & mask(n);
}
let taken = 64 - bit_offset;
let hi = self.data.get(byte_pos + 8).copied().unwrap_or(0) as u64 & mask(n - taken);
(low | (hi << taken)) & mask(n)
}
#[inline]
pub fn read_bool(&mut self) -> Result<bool> {
if self.position >= self.total_bits {
return Err(Error::Overflow {
needed: 1,
available: 0,
});
}
let value = self.data[self.position / 8] & (1 << (self.position % 8)) != 0;
self.position += 1;
Ok(value)
}
#[inline]
pub fn read_u8(&mut self) -> Result<u8> {
if self.bits_remaining() < 8 {
return Err(Error::Overflow {
needed: 8,
available: self.bits_remaining(),
});
}
let byte_pos = self.position / 8;
let bit_offset = self.position % 8;
let value = if bit_offset == 0 {
self.data[byte_pos]
} else {
let window = self.data[byte_pos] as u16 | (self.data[byte_pos + 1] as u16) << 8;
(window >> bit_offset) as u8
};
self.position += 8;
Ok(value)
}
#[inline]
pub fn read_u16(&mut self) -> Result<u16> {
Ok(self.read_bits(16)? as u16)
}
#[inline]
pub fn read_u32(&mut self) -> Result<u32> {
Ok(self.read_bits(32)? as u32)
}
#[inline]
pub fn read_u64(&mut self) -> Result<u64> {
self.read_bits(64)
}
#[inline]
pub fn read_f32(&mut self) -> Result<f32> {
Ok(f32::from_bits(self.read_bits(32)? as u32))
}
pub fn read_bytes(&mut self, buf: &mut [u8]) -> Result<()> {
if buf.len() > self.bits_remaining() / 8 {
return Err(Error::Overflow {
needed: buf.len().saturating_mul(8),
available: self.bits_remaining(),
});
}
if buf.is_empty() {
return Ok(());
}
let byte_pos = self.position / 8;
let shift = self.position % 8;
if shift == 0 {
buf.copy_from_slice(&self.data[byte_pos..byte_pos + buf.len()]);
} else {
let input = &self.data[byte_pos..byte_pos + buf.len() + 1];
for ((output, low), high) in buf.iter_mut().zip(input).zip(&input[1..]) {
*output = (low >> shift) | (high << (8 - shift));
}
}
self.position += buf.len() * 8;
Ok(())
}
pub fn read_bits_to_bytes(&mut self, buf: &mut [u8], bits: usize) -> Result<()> {
let needed = bits.div_ceil(8);
if needed > buf.len() {
return Err(Error::Overflow {
needed,
available: buf.len(),
});
}
let full_bytes = bits / 8;
let remaining_bits = bits % 8;
if remaining_bits == 0 {
return self.read_bytes(&mut buf[..full_bytes]);
}
if full_bytes > 0 {
self.read_bytes(&mut buf[..full_bytes])?;
}
buf[full_bytes] = self.read_bits(remaining_bits)? as u8;
Ok(())
}
#[inline]
pub fn read_uvarint32(&mut self) -> Result<u32> {
let mut result: u32 = 0;
for i in 0..5 {
let byte = self.read_u8()? as u32;
result |= (byte & 0x7F) << (7 * i);
if byte & 0x80 == 0 {
return Ok(result);
}
}
Ok(result)
}
pub fn read_uvarint64(&mut self) -> Result<u64> {
let mut result: u64 = 0;
for i in 0..10 {
let byte = self.read_u8()? as u64;
result |= (byte & 0x7F) << (7 * i);
if byte & 0x80 == 0 {
return Ok(result);
}
}
Ok(result)
}
pub fn read_varint32(&mut self) -> Result<i32> {
let n = self.read_uvarint32()?;
Ok(((n >> 1) as i32) ^ -((n & 1) as i32))
}
pub fn read_varint64(&mut self) -> Result<i64> {
let n = self.read_uvarint64()?;
Ok(((n >> 1) as i64) ^ -((n & 1) as i64))
}
#[inline]
pub fn read_ubitvar(&mut self) -> Result<u32> {
let ret = self.read_bits(6)? as u32;
match ret & (16 | 32) {
16 => Ok((ret & 15) | (self.read_bits(4)? as u32) << 4),
32 => Ok((ret & 15) | (self.read_bits(8)? as u32) << 4),
48 => Ok((ret & 15) | (self.read_bits(28)? as u32) << 4),
_ => Ok(ret),
}
}
#[inline]
pub fn read_ubitvarfp(&mut self) -> Result<u32> {
if self.bits_remaining() >= 35 {
let word = self.peek_bits_unchecked(35);
let selector = (word as u32).trailing_zeros().min(4) as usize;
let prefix_bits = (selector + 1).min(4);
let payload_bits = [2, 4, 10, 17, 31][selector];
self.position += prefix_bits + payload_bits;
return Ok(((word >> prefix_bits) & mask(payload_bits)) as u32);
}
if self.read_bool()? {
return Ok(self.read_bits(2)? as u32);
}
if self.read_bool()? {
return Ok(self.read_bits(4)? as u32);
}
if self.read_bool()? {
return Ok(self.read_bits(10)? as u32);
}
if self.read_bool()? {
return Ok(self.read_bits(17)? as u32);
}
Ok(self.read_bits(31)? as u32)
}
pub fn read_bitcoord(&mut self) -> Result<f32> {
let has_int = self.read_bool()?;
let has_frac = self.read_bool()?;
if !has_int && !has_frac {
return Ok(0.0);
}
let negative = self.read_bool()?;
let mut value = 0.0f32;
if has_int {
value += self.read_bits(COORD_INTEGER_BITS)? as f32 + 1.0;
}
if has_frac {
value += self.read_bits(COORD_FRACTIONAL_BITS)? as f32 * COORD_RESOLUTION;
}
if negative {
value = -value;
}
Ok(value)
}
pub fn read_bitnormal(&mut self) -> Result<f32> {
let negative = self.read_bool()?;
let frac = self.read_bits(NORMAL_FRACTIONAL_BITS)? as f32;
let mut value = frac * NORMAL_RESOLUTION;
if negative {
value = -value;
}
Ok(value)
}
pub fn read_bitvec3coord(&mut self) -> Result<[f32; 3]> {
let has_x = self.read_bool()?;
let has_y = self.read_bool()?;
let has_z = self.read_bool()?;
let x = if has_x { self.read_bitcoord()? } else { 0.0 };
let y = if has_y { self.read_bitcoord()? } else { 0.0 };
let z = if has_z { self.read_bitcoord()? } else { 0.0 };
Ok([x, y, z])
}
pub fn read_bitvec3normal(&mut self) -> Result<[f32; 3]> {
let has_x = self.read_bool()?;
let has_y = self.read_bool()?;
let x = if has_x { self.read_bitnormal()? } else { 0.0 };
let y = if has_y { self.read_bitnormal()? } else { 0.0 };
let z_sign = self.read_bool()?;
let z_sq = 1.0 - x * x - y * y;
let z = if z_sq > 0.0 { z_sq.sqrt() } else { 0.0 };
let z = if z_sign { -z } else { z };
Ok([x, y, z])
}
pub fn read_bitangle(&mut self, n: usize) -> Result<f32> {
let raw = self.read_bits(n)? as f32;
let shift = (1u64 << n) as f32;
Ok(raw * 360.0 / shift)
}
pub fn read_string(&mut self) -> Result<String> {
let mut bytes = Vec::new();
loop {
let byte = self.read_u8()?;
if byte == 0 {
break;
}
bytes.push(byte);
}
Ok(String::from_utf8_lossy(&bytes).into_owned())
}
pub fn read_string_into(&mut self, buf: &mut [u8]) -> Result<usize> {
let mut i = 0;
loop {
let b = self.read_u8()?;
if b == 0 {
break;
}
if i < buf.len() {
buf[i] = b;
i += 1;
}
}
Ok(i)
}
pub fn read_string_raw_limited(
&mut self,
buf: &mut Vec<u8>,
max_bytes: usize,
) -> Result<usize> {
let start = buf.len();
loop {
let b = self.read_u8()?;
if b == 0 {
break;
}
let written = buf.len() - start;
if written == max_bytes {
return Err(Error::LimitExceeded {
resource: "decoded field string",
limit: max_bytes,
actual: written.saturating_add(1),
});
}
buf.push(b);
}
Ok(buf.len() - start)
}
pub fn read_string_raw(&mut self, buf: &mut Vec<u8>) -> Result<usize> {
let start = buf.len();
loop {
let b = self.read_u8()?;
if b == 0 {
break;
}
buf.push(b);
}
Ok(buf.len() - start)
}
pub fn skip_bits(&mut self, n: usize) -> Result<()> {
if n > self.bits_remaining() {
return Err(Error::Overflow {
needed: n,
available: self.bits_remaining(),
});
}
self.position += n;
Ok(())
}
pub fn skip_varint(&mut self) -> Result<()> {
for _ in 0..10 {
let byte = self.read_u8()?;
if byte & 0x80 == 0 {
return Ok(());
}
}
Ok(())
}
pub fn skip_bitcoord(&mut self) -> Result<()> {
let has_int = self.read_bool()?;
let has_frac = self.read_bool()?;
if !has_int && !has_frac {
return Ok(());
}
self.skip_bits(1)?;
if has_int {
self.skip_bits(COORD_INTEGER_BITS)?;
}
if has_frac {
self.skip_bits(COORD_FRACTIONAL_BITS)?;
}
Ok(())
}
pub fn skip_bitnormal(&mut self) -> Result<()> {
self.skip_bits(1 + NORMAL_FRACTIONAL_BITS)
}
pub fn skip_bitvec3coord(&mut self) -> Result<()> {
let has_x = self.read_bool()?;
let has_y = self.read_bool()?;
let has_z = self.read_bool()?;
if has_x {
self.skip_bitcoord()?;
}
if has_y {
self.skip_bitcoord()?;
}
if has_z {
self.skip_bitcoord()?;
}
Ok(())
}
pub fn skip_bitvec3normal(&mut self) -> Result<()> {
let has_x = self.read_bool()?;
let has_y = self.read_bool()?;
if has_x {
self.skip_bitnormal()?;
}
if has_y {
self.skip_bitnormal()?;
}
self.skip_bits(1)?;
Ok(())
}
#[inline]
pub fn skip_string_limited(&mut self, max_bytes: usize) -> Result<()> {
if self.read_u8()? == 0 {
return Ok(());
}
if self.bits_remaining() / 8 < max_bytes {
return self.skip_string();
}
self.skip_string_bounded(max_bytes)
}
#[cold]
fn skip_string_bounded(&mut self, max_bytes: usize) -> Result<()> {
if max_bytes == 0 {
return Err(Error::LimitExceeded {
resource: "decoded field string",
limit: 0,
actual: 1,
});
}
let mut length = 1_usize;
loop {
if self.read_u8()? == 0 {
return Ok(());
}
if length == max_bytes {
return Err(Error::LimitExceeded {
resource: "decoded field string",
limit: max_bytes,
actual: length.saturating_add(1),
});
}
length += 1;
}
}
pub fn skip_string(&mut self) -> Result<()> {
loop {
let b = self.read_u8()?;
if b == 0 {
return Ok(());
}
}
}
}
#[inline(always)]
fn mask(n: usize) -> u64 {
if n >= 64 { u64::MAX } else { (1u64 << n) - 1 }
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn limited_string_skip_matches_read_errors_and_cursor() {
for alignment in 0..8 {
for length in 0..20 {
for terminated in [false, true] {
let mut bits = crate::test_utils::BitWriter::default();
bits.push_bits(0, alignment);
bits.push_bytes(&vec![b'x'; length]);
if terminated {
bits.push_bits(0, 8);
}
let data = bits.finish();
for limit in [0, 1, 3, 8, 20, usize::MAX] {
let mut read = BitReader::new(&data);
let mut skip = BitReader::new(&data);
read.skip_bits(alignment).unwrap();
skip.skip_bits(alignment).unwrap();
let expected = read
.read_string_raw_limited(&mut Vec::new(), limit)
.map(|_| ())
.map_err(|e| e.to_string());
let actual = skip.skip_string_limited(limit).map_err(|e| e.to_string());
assert_eq!((actual, skip.position()), (expected, read.position()));
}
}
}
}
}
#[test]
fn oversized_skip_preserves_cursor() {
let mut reader = BitReader::new(&[0xff]);
reader.skip_bits(1).unwrap();
assert!(matches!(
reader.skip_bits(usize::MAX),
Err(Error::Overflow { .. })
));
assert_eq!(reader.position(), 1);
assert_eq!(reader.read_bits(7).unwrap(), 127);
}
#[test]
fn bit_copy_rejects_short_output_before_consuming_input() {
for bits in [9, 16, usize::MAX] {
let mut reader = BitReader::new(&[0xff; 4]);
let mut output = [0x55];
assert!(matches!(
reader.read_bits_to_bytes(&mut output, bits),
Err(Error::Overflow { .. })
));
assert_eq!(reader.position(), 0);
assert_eq!(output, [0x55]);
}
}
#[test]
fn test_read_u8_unaligned() {
let data = [0b1011_0100, 0b1100_1010, 0b0110_0001];
for offset in 1..8 {
let mut br = BitReader::new(&data);
br.skip_bits(offset).unwrap();
let got = br.read_u8().unwrap();
let window = u32::from_le_bytes([data[0], data[1], data[2], 0]);
assert_eq!(got, ((window >> offset) & 0xff) as u8);
}
}
#[test]
fn test_read_bool_overflow() {
let data = [0xff];
let mut br = BitReader::new(&data);
for _ in 0..8 {
assert!(br.read_bool().unwrap());
}
assert!(br.read_bool().is_err());
}
#[test]
fn test_read_bits_wide_unaligned() {
let data: Vec<u8> = (0..16).collect();
let full = u128::from_le_bytes(data[..16].try_into().unwrap());
for offset in 0..8usize {
for n in 57..=64usize {
let mut br = BitReader::new(&data);
if offset > 0 {
br.read_bits(offset).unwrap();
}
let got = br.read_bits(n).unwrap();
let want = ((full >> offset) & ((1u128 << n) - 1)) as u64;
assert_eq!(got, want, "read_bits({n}) at offset {offset}");
}
}
}
#[test]
fn test_read_bits_basic() {
let data = [0b10110100, 0b11001010];
let mut br = BitReader::new(&data);
assert_eq!(br.read_bits(1).unwrap(), 0);
assert_eq!(br.read_bits(1).unwrap(), 0);
assert_eq!(br.read_bits(1).unwrap(), 1);
assert_eq!(br.read_bits(1).unwrap(), 0);
assert_eq!(br.read_bits(1).unwrap(), 1);
assert_eq!(br.read_bits(1).unwrap(), 1);
assert_eq!(br.read_bits(1).unwrap(), 0);
assert_eq!(br.read_bits(1).unwrap(), 1);
}
#[test]
fn test_read_byte() {
let data = [0xAB, 0xCD];
let mut br = BitReader::new(&data);
assert_eq!(br.read_u8().unwrap(), 0xAB);
assert_eq!(br.read_u8().unwrap(), 0xCD);
}
#[test]
fn test_read_across_boundary() {
let data = [0xFF, 0x00, 0xFF];
let mut br = BitReader::new(&data);
br.read_bits(4).unwrap();
let val = br.read_bits(8).unwrap();
assert_eq!(val, 0x0F);
}
#[test]
fn test_read_bool() {
let data = [0b10000001];
let mut br = BitReader::new(&data);
assert!(br.read_bool().unwrap());
assert!(!br.read_bool().unwrap());
}
#[test]
fn test_overflow() {
let data = [0xFF];
let mut br = BitReader::new(&data);
br.read_bits(8).unwrap();
assert!(br.read_bits(1).is_err());
}
#[test]
fn test_uvarint32() {
let data = [0xAC, 0x02];
let mut br = BitReader::new(&data);
assert_eq!(br.read_uvarint32().unwrap(), 300);
}
#[test]
fn test_varint32_negative() {
let data = [0x01];
let mut br = BitReader::new(&data);
assert_eq!(br.read_varint32().unwrap(), -1);
}
#[test]
fn test_varint32_positive() {
let data = [0x02];
let mut br = BitReader::new(&data);
assert_eq!(br.read_varint32().unwrap(), 1);
}
#[test]
fn test_read_f32() {
let val: f32 = 1.5;
let data = val.to_bits().to_le_bytes();
let mut br = BitReader::new(&data);
let read_val = br.read_f32().unwrap();
assert!((read_val - val).abs() < f32::EPSILON);
}
#[test]
fn test_bits_remaining() {
let data = [0xFF, 0xFF];
let mut br = BitReader::new(&data);
assert_eq!(br.bits_remaining(), 16);
br.read_bits(5).unwrap();
assert_eq!(br.bits_remaining(), 11);
}
#[test]
fn test_skip_bits() {
let data = [0b11110000, 0b10101010];
let mut br = BitReader::new(&data);
br.skip_bits(4).unwrap();
assert_eq!(br.read_bits(4).unwrap(), 0b1111);
}
#[test]
fn test_ubitvar() {
let data = [0b00000101];
let mut br = BitReader::new(&data);
assert_eq!(br.read_ubitvar().unwrap(), 5);
}
#[test]
fn test_bitangle() {
let data = [0x00, 0x00, 0x00, 0x00];
let mut br = BitReader::new(&data);
assert!((br.read_bitangle(16).unwrap() - 0.0).abs() < f32::EPSILON);
}
}
#[cfg(test)]
mod field_path_varint_tests {
use super::*;
fn read_reference(reader: &mut BitReader) -> Result<u32> {
for width in [2, 4, 10, 17] {
if reader.read_bool()? {
return Ok(reader.read_bits(width)? as u32);
}
}
Ok(reader.read_bits(31)? as u32)
}
#[test]
fn every_width_alignment_and_truncation_matches_the_reference() {
use crate::test_utils::BitWriter;
for (selector, width) in [2, 4, 10, 17, 31].into_iter().enumerate() {
for value in [0, 1, (1u64 << width) - 1] {
for offset in 0..8 {
let mut writer = BitWriter::default();
writer.push_bits(0, offset);
for _ in 0..selector.min(4) {
writer.push_bool(false);
}
if selector < 4 {
writer.push_bool(true);
}
writer.push_bits(value, width);
writer.push_bits(0xabcdef12, 32);
let bytes = writer.finish();
for end in 0..=bytes.len() {
if end * 8 < offset {
continue;
}
let mut actual = BitReader::new(&bytes[..end]);
let mut reference = BitReader::new(&bytes[..end]);
actual.skip_bits(offset).unwrap();
reference.skip_bits(offset).unwrap();
assert_eq!(
format!("{:?}", actual.read_ubitvarfp()),
format!("{:?}", read_reference(&mut reference))
);
assert_eq!(actual.position(), reference.position());
if end == bytes.len() {
assert_eq!(actual.read_bits(32).unwrap(), 0xabcdef12);
}
}
}
}
}
}
proptest::proptest! {
#[test]
fn combined_field_path_varints_preserve_values_errors_and_cursors(
bytes in proptest::collection::vec(proptest::prelude::any::<u8>(), 1..128),
offset in 0usize..8,
) {
let mut actual = BitReader::new(&bytes);
let mut reference = BitReader::new(&bytes);
actual.skip_bits(offset).unwrap();
reference.skip_bits(offset).unwrap();
loop {
let actual_result = actual.read_ubitvarfp();
let reference_result = read_reference(&mut reference);
proptest::prop_assert_eq!(format!("{actual_result:?}"), format!("{reference_result:?}"));
proptest::prop_assert_eq!(actual.position(), reference.position());
if actual_result.is_err() { break; }
}
}
}
}