pub struct BoolEncoder {
out: Vec<u8>,
range: u32,
bottom: u32,
bit_count: i32,
}
impl Default for BoolEncoder {
fn default() -> Self {
Self::new()
}
}
impl BoolEncoder {
pub fn new() -> Self {
let mut e = Self {
out: Vec::new(),
range: 255,
bottom: 0,
bit_count: 24,
};
e.put_bit(false); e
}
fn carry(&mut self) {
let mut i = self.out.len();
while i > 0 {
i -= 1;
if self.out[i] == 0xff {
self.out[i] = 0;
} else {
self.out[i] += 1;
return;
}
}
self.out.insert(0, 1);
}
#[inline]
fn shift(&mut self) {
if self.bottom & 0x8000_0000 != 0 {
self.carry();
}
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;
}
}
pub fn put_bool(&mut self, prob: u8, bit: bool) {
let split = 1 + (((self.range - 1) * prob as u32) >> 8);
if bit {
self.bottom += split;
self.range -= split;
} else {
self.range = split;
}
while self.range < 128 {
self.range <<= 1;
self.shift();
}
}
pub fn put_bit(&mut self, bit: bool) {
self.put_bool(128, bit);
}
pub fn put_literal(&mut self, value: u32, n: u32) {
for i in (0..n).rev() {
self.put_bit((value >> i) & 1 != 0);
}
}
pub fn finish(mut self) -> Vec<u8> {
for _ in 0..32 {
self.put_bit(false);
}
self.out
}
pub fn len(&self) -> usize {
self.out.len()
}
pub fn is_empty(&self) -> bool {
self.out.is_empty()
}
}
#[cfg(test)]
mod tests {
use super::*;
struct BoolDecoder<'a> {
input: &'a [u8],
pos: usize,
range: u32,
value: u32,
bit_count: i32,
}
impl<'a> BoolDecoder<'a> {
fn new(input: &'a [u8]) -> Self {
let b0 = input.first().copied().unwrap_or(0) as u32;
let b1 = input.get(1).copied().unwrap_or(0) as u32;
let mut d = Self {
input,
pos: 2,
range: 255,
value: (b0 << 8) | b1,
bit_count: 0,
};
assert!(!d.get_bool(128), "bool coder marker bit must be 0");
d
}
fn get_bool(&mut self, prob: u8) -> bool {
let split = 1 + (((self.range - 1) * prob as u32) >> 8);
let big_split = split << 8;
let ret = if self.value >= big_split {
self.range -= split;
self.value -= big_split;
true
} else {
self.range = split;
false
};
while self.range < 128 {
self.value <<= 1;
self.range <<= 1;
self.bit_count += 1;
if self.bit_count == 8 {
self.bit_count = 0;
let byte = self.input.get(self.pos).copied().unwrap_or(0) as u32;
self.pos += 1;
self.value |= byte;
}
}
ret
}
fn get_literal(&mut self, n: u32) -> u32 {
let mut v = 0;
for _ in 0..n {
v = (v << 1) | self.get_bool(128) as u32;
}
v
}
}
struct Rng(u32);
impl Rng {
fn next(&mut self) -> u32 {
let mut x = self.0;
x ^= x << 13;
x ^= x >> 17;
x ^= x << 5;
self.0 = x;
x
}
}
#[test]
fn roundtrip_simple() {
let script: &[(u8, bool)] = &[
(128, true),
(128, false),
(10, true),
(250, false),
(200, true),
(5, false),
];
let mut enc = BoolEncoder::new();
for &(p, b) in script {
enc.put_bool(p, b);
}
let bytes = enc.finish();
let mut dec = BoolDecoder::new(&bytes);
for &(p, b) in script {
assert_eq!(dec.get_bool(p), b);
}
}
#[test]
fn roundtrip_randomized() {
for trial in 0..300u32 {
let mut rng = Rng(0x9E37_79B9 ^ trial.wrapping_mul(2654435761));
let len = 20 + (rng.next() % 500) as usize;
let ops: Vec<(u8, bool)> = (0..len)
.map(|_| {
let p = match rng.next() % 4 {
0 => 1,
1 => 255,
_ => (rng.next() % 256) as u8,
};
(p.max(1), rng.next() & 1 != 0)
})
.collect();
let mut enc = BoolEncoder::new();
for &(p, b) in &ops {
enc.put_bool(p, b);
}
let bytes = enc.finish();
let mut dec = BoolDecoder::new(&bytes);
for (i, &(p, b)) in ops.iter().enumerate() {
assert_eq!(dec.get_bool(p), b, "trial {trial} bin {i} (prob {p})");
}
}
}
#[test]
fn roundtrip_literals() {
let mut rng = Rng(0x1234_5678);
let vals: Vec<(u32, u32)> = (0..200)
.map(|_| {
let n = 1 + rng.next() % 16;
(rng.next() & ((1 << n) - 1), n)
})
.collect();
let mut enc = BoolEncoder::new();
for &(v, n) in &vals {
enc.put_literal(v, n);
}
let bytes = enc.finish();
let mut dec = BoolDecoder::new(&bytes);
for &(v, n) in &vals {
assert_eq!(dec.get_literal(n), v, "literal {v} ({n} bits)");
}
}
#[test]
fn roundtrip_all_ones_carry_stress() {
let mut enc = BoolEncoder::new();
let ops: Vec<(u8, bool)> = (0..2000).map(|i| (1u8, i % 7 != 0)).collect();
for &(p, b) in &ops {
enc.put_bool(p, b);
}
let bytes = enc.finish();
let mut dec = BoolDecoder::new(&bytes);
for &(p, b) in &ops {
assert_eq!(dec.get_bool(p), b);
}
}
}