use crate::{
entropy::mem::{highbit32, read_u64, write_u64},
error::{Error, Result},
};
use core::marker::PhantomData;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum BitDStreamStatus {
Unfinished = 0,
EndOfBuffer = 1,
Completed = 2,
Overflow = 3,
}
pub(crate) type BitContainer = u64;
pub(crate) const CONTAINER_BYTES: usize = core::mem::size_of::<BitContainer>();
pub(crate) const CONTAINER_BITS: u32 = BitContainer::BITS;
pub(crate) const STREAM_ACCUMULATOR_MIN: u32 = CONTAINER_BITS - 7;
const BIT_MASK: [BitContainer; 32] = [
0, 1, 3, 7, 0xF, 0x1F, 0x3F, 0x7F, 0xFF, 0x1FF, 0x3FF, 0x7FF, 0xFFF, 0x1FFF, 0x3FFF, 0x7FFF,
0xFFFF, 0x1FFFF, 0x3FFFF, 0x7FFFF, 0xFFFFF, 0x1FFFFF, 0x3FFFFF, 0x7FFFFF, 0xFFFFFF, 0x1FFFFFF,
0x3FFFFFF, 0x7FFFFFF, 0xFFFFFFF, 0x1FFFFFFF, 0x3FFFFFFF, 0x7FFFFFFF,
];
#[derive(Debug)]
pub(crate) struct BitCStream<'a> {
pub(crate) bit_container: BitContainer,
pub(crate) bit_pos: u32,
dst: &'a mut [u8],
byte_pos: usize,
end_pos: usize,
}
impl<'a> BitCStream<'a> {
#[inline(always)]
pub(crate) fn new(dst: &'a mut [u8]) -> Result<Self> {
if dst.len() <= CONTAINER_BYTES {
return Err(Error::DstSizeTooSmall);
}
let end_pos = dst.len() - CONTAINER_BYTES;
Ok(Self {
bit_container: 0,
bit_pos: 0,
dst,
byte_pos: 0,
end_pos,
})
}
#[inline(always)]
pub(crate) fn add_bits(&mut self, value: BitContainer, nb_bits: u32) {
debug_assert!(nb_bits < BIT_MASK.len() as u32);
debug_assert!(nb_bits + self.bit_pos < CONTAINER_BITS);
self.bit_container |= (value & BIT_MASK[nb_bits as usize]) << self.bit_pos;
self.bit_pos += nb_bits;
}
#[inline(always)]
pub(crate) fn add_bits_fast(&mut self, value: BitContainer, nb_bits: u32) {
debug_assert!(nb_bits + self.bit_pos < CONTAINER_BITS);
debug_assert!((value >> nb_bits) == 0);
self.bit_container |= value << self.bit_pos;
self.bit_pos += nb_bits;
}
#[inline(always)]
pub(crate) fn flush_bits_fast(&mut self) {
let nb_bytes = (self.bit_pos >> 3) as usize;
debug_assert!(self.byte_pos <= self.end_pos);
write_u64(self.dst, self.byte_pos, self.bit_container);
self.byte_pos += nb_bytes;
self.bit_pos &= 7;
self.bit_container >>= nb_bytes * 8;
}
#[inline(always)]
pub(crate) fn flush_bits(&mut self) {
let nb_bytes = (self.bit_pos >> 3) as usize;
debug_assert!(self.byte_pos <= self.end_pos);
write_u64(self.dst, self.byte_pos, self.bit_container);
self.byte_pos = (self.byte_pos + nb_bytes).min(self.end_pos);
self.bit_pos &= 7;
self.bit_container >>= nb_bytes * 8;
}
#[allow(unsafe_code)]
#[inline(always)]
pub(crate) unsafe fn flush_bits_unchecked(&mut self) {
let nb_bytes = (self.bit_pos >> 3) as usize;
debug_assert!(self.byte_pos <= self.end_pos);
let ptr = unsafe { self.dst.as_mut_ptr().add(self.byte_pos) };
unsafe { core::ptr::write_unaligned(ptr as *mut u64, self.bit_container.to_le()) };
self.byte_pos += nb_bytes;
self.bit_pos &= 7;
self.bit_container >>= nb_bytes * 8;
}
#[inline(always)]
pub(crate) fn close(mut self) -> usize {
self.add_bits_fast(1, 1);
self.flush_bits();
if self.byte_pos >= self.end_pos {
return 0;
}
self.byte_pos + usize::from(self.bit_pos > 0)
}
}
#[derive(Debug, Clone)]
pub(crate) struct BitDStream<'a> {
pub(crate) bit_container: BitContainer,
pub(crate) bits_consumed: u32,
ptr: *const u8,
start: *const u8,
#[cfg(debug_assertions)]
end: *const u8,
_phantom: PhantomData<&'a [u8]>,
}
#[allow(unsafe_code)]
unsafe impl Send for BitDStream<'_> {}
#[allow(unsafe_code)]
unsafe impl Sync for BitDStream<'_> {}
impl<'a> BitDStream<'a> {
#[allow(unsafe_code)]
#[inline(always)]
pub(crate) fn new(src: &'a [u8]) -> Result<Self> {
if src.is_empty() {
return Err(Error::SrcSizeWrong);
}
let base = src.as_ptr();
#[cfg(debug_assertions)]
let end = unsafe { base.add(src.len()) };
let last_byte = src[src.len() - 1];
if last_byte == 0 {
return Err(Error::Corruption("bitstream end marker is zero"));
}
let bits_consumed = 8 - highbit32(last_byte as u32);
if src.len() >= CONTAINER_BYTES {
let ptr = unsafe { base.add(src.len() - CONTAINER_BYTES) };
let bit_container = read_u64(src, src.len() - CONTAINER_BYTES);
Ok(Self {
bit_container,
bits_consumed,
ptr,
start: base,
#[cfg(debug_assertions)]
end,
_phantom: PhantomData,
})
} else {
let mut bit_container: BitContainer = 0;
for (index, byte) in src.iter().copied().enumerate() {
bit_container |= BitContainer::from(byte) << (index * 8);
}
Ok(Self {
bit_container,
bits_consumed: bits_consumed + ((CONTAINER_BYTES - src.len()) * 8) as u32,
ptr: base,
start: base,
#[cfg(debug_assertions)]
end,
_phantom: PhantomData,
})
}
}
#[inline(always)]
fn reg_mask(&self) -> u32 {
CONTAINER_BITS - 1
}
#[inline(always)]
pub(crate) fn look_bits(&self, nb_bits: u32) -> BitContainer {
let start = CONTAINER_BITS
.wrapping_sub(self.bits_consumed)
.wrapping_sub(nb_bits);
self.get_middle_bits(start, nb_bits)
}
#[inline(always)]
pub(crate) fn look_bits_fast(&self, nb_bits: u32) -> BitContainer {
debug_assert!(nb_bits >= 1);
let reg_mask = self.reg_mask();
(self.bit_container << (self.bits_consumed & reg_mask))
>> (((reg_mask + 1) - nb_bits) & reg_mask)
}
#[inline(always)]
fn get_middle_bits(&self, start: u32, nb_bits: u32) -> BitContainer {
let reg_mask = self.reg_mask();
debug_assert!(nb_bits < BIT_MASK.len() as u32);
(self.bit_container >> (start & reg_mask)) & BIT_MASK[nb_bits as usize]
}
#[inline(always)]
pub(crate) fn skip_bits(&mut self, nb_bits: u32) {
self.bits_consumed += nb_bits;
}
#[inline(always)]
pub(crate) fn can_read_fast(&self, nb_bits: u32) -> bool {
nb_bits != 0 && self.bits_consumed + nb_bits <= CONTAINER_BITS
}
#[inline(always)]
pub(crate) fn read_bits(&mut self, nb_bits: u32) -> BitContainer {
if nb_bits == 0 {
return 0;
}
if self.can_read_fast(nb_bits) {
return self.read_bits_fast(nb_bits);
}
let value = self.look_bits(nb_bits);
self.skip_bits(nb_bits);
value
}
#[inline(always)]
pub(crate) fn read_bits_fast(&mut self, nb_bits: u32) -> BitContainer {
let value = self.look_bits_fast(nb_bits);
self.skip_bits(nb_bits);
value
}
#[inline(always)]
pub(crate) fn read_bits_fast_zero_safe(&mut self, nb_bits: u32) -> BitContainer {
let reg_mask = self.reg_mask();
let raw = (self.bit_container << (self.bits_consumed & reg_mask))
>> (((reg_mask + 1) - nb_bits) & reg_mask);
let value = raw & ((1 as BitContainer) << nb_bits).wrapping_sub(1);
self.skip_bits(nb_bits);
value
}
#[inline(always)]
fn bytes_behind_ptr(&self) -> usize {
self.ptr.addr() - self.start.addr()
}
#[inline(always)]
fn debug_assert_load_in_bounds(&self) {
debug_assert!(self.ptr.addr() >= self.start.addr());
#[cfg(debug_assertions)]
debug_assert!(self.ptr.addr() + CONTAINER_BYTES <= self.end.addr());
}
#[allow(unsafe_code)]
#[inline(always)]
pub(crate) fn reload_fast(&mut self) -> BitDStreamStatus {
if self.bytes_behind_ptr() < CONTAINER_BYTES {
return BitDStreamStatus::Overflow;
}
let consumed_bytes = (self.bits_consumed >> 3) as usize;
unsafe {
self.ptr = self.ptr.sub(consumed_bytes);
self.bits_consumed &= 7;
self.debug_assert_load_in_bounds();
self.bit_container = core::ptr::read_unaligned(self.ptr as *const u64).to_le();
}
BitDStreamStatus::Unfinished
}
#[allow(unsafe_code)]
#[inline(always)]
pub(crate) fn reload(&mut self) -> BitDStreamStatus {
if self.bits_consumed > CONTAINER_BITS {
return reload_overflow();
}
if self.bytes_behind_ptr() >= CONTAINER_BYTES {
return self.reload_fast();
}
if self.ptr == self.start {
return reload_at_start(self.bits_consumed);
}
let mut nb_bytes = (self.bits_consumed >> 3) as usize;
let mut result = BitDStreamStatus::Unfinished;
let available = unsafe { self.ptr.offset_from(self.start) as usize };
if nb_bytes > available {
nb_bytes = available;
result = BitDStreamStatus::EndOfBuffer;
}
unsafe {
self.ptr = self.ptr.sub(nb_bytes);
self.bits_consumed -= (nb_bytes * 8) as u32;
self.debug_assert_load_in_bounds();
self.bit_container = core::ptr::read_unaligned(self.ptr as *const u64).to_le();
}
result
}
#[inline(always)]
pub(crate) fn end_of_stream(&self) -> bool {
core::ptr::eq(self.ptr, self.start) && self.bits_consumed == CONTAINER_BITS
}
}
#[cold]
#[inline(never)]
fn reload_overflow() -> BitDStreamStatus {
BitDStreamStatus::Overflow
}
#[cold]
#[inline(never)]
fn reload_at_start(bits_consumed: u32) -> BitDStreamStatus {
if bits_consumed < CONTAINER_BITS {
BitDStreamStatus::EndOfBuffer
} else {
BitDStreamStatus::Completed
}
}
#[cfg(test)]
mod tests {
use super::*;
fn encode(values: &[(BitContainer, u32)]) -> Vec<u8> {
let mut bytes = vec![0u8; 64];
let written = {
let mut stream = BitCStream::new(&mut bytes).unwrap();
for &(value, nb_bits) in values {
if stream.bit_pos + nb_bits >= STREAM_ACCUMULATOR_MIN {
stream.flush_bits();
}
stream.add_bits(value, nb_bits);
}
stream.close()
};
bytes.truncate(written);
bytes
}
#[test]
fn roundtrips_values_in_reverse_bitstream_order() {
let values = [
(0b10, 2),
(0b111, 3),
(0x12, 5),
(0x155, 9),
(0x1A, 5),
(0x1F, 5),
(0x2AA, 10),
(0x1234, 13),
];
let encoded = encode(&values);
let mut stream = BitDStream::new(&encoded).unwrap();
for &(expected, nb_bits) in values.iter().rev() {
assert_eq!(stream.read_bits(nb_bits), expected);
assert_ne!(stream.reload(), BitDStreamStatus::Overflow);
}
}
#[test]
fn rejects_zero_terminated_input() {
let err = BitDStream::new(&[0]).unwrap_err();
assert_eq!(err, Error::Corruption("bitstream end marker is zero"));
}
#[test]
fn fast_and_regular_reads_match() {
let values = [(0b10101, 5), (0b1111111, 7), (0b1011, 4), (0b1110, 4)];
let encoded = encode(&values);
let mut regular = BitDStream::new(&encoded).unwrap();
let mut fast = BitDStream::new(&encoded).unwrap();
for &(_, nb_bits) in values.iter().rev() {
assert_eq!(regular.read_bits(nb_bits), fast.read_bits_fast(nb_bits));
assert_eq!(regular.reload(), fast.reload());
}
}
#[test]
fn accumulates_a_full_sequences_worth_of_bits_without_a_flush() {
const WIDEST_SEQUENCE_BITS: u32 = 31 + 16 + 16;
const { assert!(WIDEST_SEQUENCE_BITS < CONTAINER_BITS) };
let values: [(BitContainer, u32); 3] = [(0x7FFF_FFFF, 31), (0xFFFF, 16), (0xABCD, 16)];
let mut bytes = vec![0u8; 64];
let written = {
let mut stream = BitCStream::new(&mut bytes).unwrap();
for &(value, nb_bits) in &values {
stream.add_bits(value, nb_bits);
}
assert_eq!(stream.bit_pos, WIDEST_SEQUENCE_BITS);
stream.flush_bits();
stream.close()
};
bytes.truncate(written);
let mut stream = BitDStream::new(&bytes).unwrap();
for &(expected, nb_bits) in values.iter().rev() {
assert_eq!(stream.read_bits(nb_bits), expected);
}
assert_ne!(stream.reload(), BitDStreamStatus::Overflow);
}
#[test]
fn reads_never_run_past_a_short_bitstream() {
for len in 1..=(CONTAINER_BYTES * 3) {
let mut bytes: Vec<u8> = (0..len).map(|i| (i as u8) | 1).collect();
bytes[len - 1] |= 0x80;
let mut stream = BitDStream::new(&bytes).unwrap();
loop {
let _ = stream.read_bits(5);
if stream.reload() != BitDStreamStatus::Unfinished {
break;
}
}
}
}
}