#[derive(Debug)]
pub(super) struct BoolDecoder<'a> {
data: &'a [u8],
pos: usize,
value: u64,
bits: i32,
range: u32,
eof: bool,
}
impl<'a> BoolDecoder<'a> {
pub(super) fn new(data: &'a [u8]) -> Self {
let mut decoder = Self {
data,
pos: 0,
value: 0,
bits: -8,
range: 255 - 1,
eof: false,
};
decoder.load();
decoder
}
fn load(&mut self) {
if let Some(&byte) = self.data.get(self.pos) {
self.pos += 1;
self.bits += 8;
self.value = (self.value << 8) | u64::from(byte);
} else if !self.eof {
self.value <<= 8;
self.bits += 8;
self.eof = true;
} else {
self.bits = 0;
}
}
pub(super) fn is_eof(&self) -> bool {
self.eof
}
pub(super) fn bit(&mut self, probability: u8) -> bool {
let mut range = self.range;
if self.bits < 0 {
self.load();
}
let pos = self.bits as u32;
let split = (range * u32::from(probability)) >> 8;
let value = (self.value >> pos) as u32;
let bit = value > split;
if bit {
range -= split;
self.value -= u64::from(split + 1) << pos;
} else {
range = split + 1;
}
let shift = 7 ^ range.ilog2();
range <<= shift;
self.bits -= shift as i32;
self.range = range - 1;
bit
}
pub(super) fn signed(&mut self, v: i32) -> i32 {
if self.bits < 0 {
self.load();
}
let pos = self.bits as u32;
let split = self.range >> 1;
let value = (self.value >> pos) as u32;
let mask = (split.wrapping_sub(value) as i32) >> 31;
self.bits -= 1;
self.range = self.range.wrapping_add(mask as u32) | 1;
self.value -= u64::from((split + 1) & mask as u32) << pos;
(v ^ mask) - mask
}
pub(super) fn literal(&mut self, bits: u32) -> u32 {
(0..bits).fold(0, |value, _| (value << 1) | u32::from(self.bit(0x80)))
}
pub(super) fn flag(&mut self) -> bool {
self.bit(0x80)
}
pub(super) fn signed_literal(&mut self, bits: u32) -> i32 {
let magnitude = self.literal(bits) as i32;
if self.flag() { -magnitude } else { magnitude }
}
pub(super) fn optional_signed(&mut self, bits: u32) -> i32 {
if self.flag() {
self.signed_literal(bits)
} else {
0
}
}
}
#[cfg(test)]
mod tests {
use super::*;
struct Encoder {
out: Vec<u8>,
range: u32,
bottom: u32,
bit_count: i32,
}
impl Encoder {
fn new() -> Self {
Self {
out: Vec::new(),
range: 255,
bottom: 0,
bit_count: 24,
}
}
fn add_one_to_output(&mut self) {
for byte in self.out.iter_mut().rev() {
if *byte == 255 {
*byte = 0;
} else {
*byte += 1;
break;
}
}
}
fn put(&mut self, probability: u8, bit: bool) {
let split = 1 + (((self.range - 1) * u32::from(probability)) >> 8);
if bit {
self.bottom = self.bottom.wrapping_add(split);
self.range -= split;
} else {
self.range = split;
}
while self.range < 128 {
self.range <<= 1;
if self.bottom & (1 << 31) != 0 {
self.add_one_to_output();
}
self.bottom <<= 1;
self.bit_count -= 1;
if self.bit_count == 0 {
self.out.push((self.bottom >> 24) as u8);
self.bottom &= (1 << 24) - 1;
self.bit_count = 8;
}
}
}
fn finish(mut self) -> Vec<u8> {
for _ in 0..32 {
self.put(128, false);
}
self.out
}
}
#[test]
fn decodes_what_the_reference_encoder_wrote() {
let mut encoder = Encoder::new();
let bits: Vec<(u8, bool)> = (0..500u32)
.map(|i| (((i * 37) % 254 + 1) as u8, (i * 7919) % 3 == 0))
.collect();
for &(probability, bit) in &bits {
encoder.put(probability, bit);
}
for value in [5u32, 0, 127] {
for shift in (0..7).rev() {
encoder.put(128, (value >> shift) & 1 == 1);
}
}
let data = encoder.finish();
let mut decoder = BoolDecoder::new(&data);
for &(probability, bit) in &bits {
assert_eq!(decoder.bit(probability), bit);
}
assert_eq!(decoder.literal(7), 5);
assert_eq!(decoder.literal(7), 0);
assert_eq!(decoder.signed(9), -9, "the first bit of 127 is set");
assert!(!decoder.is_eof());
}
#[test]
fn running_out_of_data_is_noticed() {
let mut decoder = BoolDecoder::new(&[0x00]);
assert!(!decoder.is_eof());
for _ in 0..16 {
decoder.bit(128);
}
assert!(decoder.is_eof());
}
}