const PROB_TOP: u32 = 1 << 15;
const PROB_SHIFT: u32 = 6;
const MIN_PROB: u32 = 4;
pub(crate) trait SymbolSink {
fn symbol<const N: usize>(&mut self, cdf: &mut [u16; N], symbol: usize);
fn bool_with(&mut self, bit: bool, p0: u16);
fn literal(&mut self, value: u32, bits: u32) {
for i in (0..bits).rev() {
self.bool_with((value >> i) & 1 == 1, 1 << 14);
}
}
}
fn interval<const N: usize>(cdf: &[u16; N], symbol: usize) -> (u32, u32) {
let below = if symbol == 0 {
0
} else {
u32::from(cdf[symbol - 1])
};
let upto = if symbol + 1 == N {
PROB_TOP
} else {
u32::from(cdf[symbol])
};
(PROB_TOP - below, PROB_TOP - upto)
}
pub(crate) fn adapt<const N: usize>(cdf: &mut [u16; N], symbol: usize) {
let count = cdf[N - 1];
let rate = 3 + u32::from(count > 15) + u32::from(count > 31) + N.ilog2().min(2);
for (i, p) in cdf[..N - 1].iter_mut().enumerate() {
if i >= symbol {
*p += (32768 - *p) >> rate;
} else {
*p -= *p >> rate;
}
}
cdf[N - 1] += u16::from(count < 32);
}
#[derive(Debug)]
pub(crate) struct SymbolEncoder {
precarry: Vec<u16>,
low: u64,
range: u32,
count: i32,
}
impl SymbolEncoder {
pub(crate) fn new() -> Self {
Self {
precarry: Vec::new(),
low: 0,
range: 0x8000,
count: -9,
}
}
fn encode(&mut self, (fl, fh): (u32, u32), symbol: usize, symbols: usize) {
let n = (symbols - 1) as u32;
let s = symbol as u32;
let r = self.range;
let scaled = |f: u32| ((r >> 8) * (f >> PROB_SHIFT)) >> (7 - PROB_SHIFT);
let v = scaled(fh) + MIN_PROB * (n - s);
let (low, range) = if symbol > 0 {
let u = scaled(fl) + MIN_PROB * (n + 1 - s);
(self.low + u64::from(r - u), u - v)
} else {
(self.low, r - v)
};
self.normalize(low, range);
}
fn normalize(&mut self, mut low: u64, range: u32) {
let d = 15 - range.ilog2() as i32;
let mut c = self.count;
let mut s = c + d;
if s >= 0 {
c += 16;
let mut mask = (1u64 << c) - 1;
if s >= 8 {
self.precarry.push((low >> c) as u16);
low &= mask;
c -= 8;
mask >>= 8;
}
self.precarry.push((low >> c) as u16);
s = c + d - 24;
low &= mask;
}
self.low = low << d;
self.range = range << d;
self.count = s;
}
pub(crate) fn finish(mut self) -> Vec<u8> {
let mut c = self.count;
let mut s = c + 10;
let mask = 0x3FFF;
let mut e = ((self.low + mask) & !mask) | (mask + 1);
if s > 0 {
let mut n = (1u64 << (c + 16)) - 1;
while s > 0 {
self.precarry.push((e >> (c + 16)) as u16);
e &= n;
s -= 8;
c -= 8;
n >>= 8;
}
}
let mut out = vec![0; self.precarry.len()];
let mut carry = 0u32;
for (byte, &entry) in out.iter_mut().zip(&self.precarry).rev() {
carry += u32::from(entry);
*byte = carry as u8;
carry >>= 8;
}
out
}
}
impl SymbolSink for SymbolEncoder {
fn symbol<const N: usize>(&mut self, cdf: &mut [u16; N], symbol: usize) {
self.encode(interval(cdf, symbol), symbol, N);
adapt(cdf, symbol);
}
fn bool_with(&mut self, bit: bool, p0: u16) {
let cdf = [p0, 0];
let symbol = usize::from(bit);
self.encode(interval(&cdf, symbol), symbol, 2);
}
}
#[derive(Debug, Default)]
pub(crate) struct RateEstimate {
pub(crate) bits: f64,
}
impl RateEstimate {
fn add(&mut self, (fl, fh): (u32, u32)) {
let width = (fl - fh).max(1);
self.bits += (f64::from(PROB_TOP) / f64::from(width)).log2();
}
}
impl SymbolSink for RateEstimate {
fn symbol<const N: usize>(&mut self, cdf: &mut [u16; N], symbol: usize) {
self.add(interval(cdf, symbol));
}
fn bool_with(&mut self, bit: bool, p0: u16) {
self.add(interval(&[p0, 0], usize::from(bit)));
}
fn literal(&mut self, _value: u32, bits: u32) {
self.bits += f64::from(bits);
}
}
#[cfg(test)]
mod tests {
use super::*;
struct SpecDecoder<'a> {
data: &'a [u8],
bit_pos: usize,
value: u32,
range: u32,
max_bits: i64,
}
impl<'a> SpecDecoder<'a> {
fn new(data: &'a [u8]) -> Self {
let mut decoder = Self {
data,
bit_pos: 0,
value: 0,
range: 1 << 15,
max_bits: 8 * data.len() as i64 - 15,
};
let num_bits = (data.len() * 8).min(15);
let buf = decoder.read_bits(num_bits);
let padded = buf << (15 - num_bits);
decoder.value = ((1 << 15) - 1) ^ padded;
decoder
}
fn read_bits(&mut self, n: usize) -> u32 {
let mut x = 0;
for _ in 0..n {
let byte = self.data.get(self.bit_pos / 8).copied().unwrap_or(0);
x = (x << 1) | u32::from((byte >> (7 - self.bit_pos % 8)) & 1);
self.bit_pos += 1;
}
x
}
fn symbol<const N: usize>(&mut self, cdf: &mut [u16; N], adapt_cdf: bool) -> usize {
let full = |i: usize| if i + 1 == N { 32768 } else { u32::from(cdf[i]) };
let mut symbol = 0;
let mut prev = self.range;
let cur = loop {
let f = (1 << 15) - full(symbol);
let cur = (((self.range >> 8) * (f >> PROB_SHIFT)) >> (7 - PROB_SHIFT))
+ MIN_PROB * (N - symbol - 1) as u32;
if self.value >= cur {
break cur;
}
prev = cur;
symbol += 1;
};
self.range = prev - cur;
self.value -= cur;
let bits = 15 - self.range.ilog2() as usize;
self.range <<= bits;
let num_bits = bits.min(self.max_bits.max(0) as usize);
let new_data = self.read_bits(num_bits);
let padded = new_data << (bits - num_bits);
self.value = padded ^ (((self.value + 1) << bits) - 1);
self.max_bits -= bits as i64;
if adapt_cdf {
adapt(cdf, symbol);
}
symbol
}
fn trailing_ok(&self) -> bool {
let padding_end = self.bit_pos + self.max_bits.max(0) as usize;
let trailing = self.bit_pos - (self.max_bits + 15).min(15) as usize;
let bit = |pos: usize| (self.data[pos / 8] >> (7 - pos % 8)) & 1;
padding_end == self.data.len() * 8
&& bit(trailing) == 1
&& (trailing + 1..padding_end).all(|pos| bit(pos) == 0)
}
}
fn next(state: &mut u64) -> u64 {
*state = state.wrapping_add(0x9E37_79B9_7F4A_7C15);
let mut z = *state;
z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
z ^ (z >> 31)
}
#[test]
fn adaptation_follows_the_specification() {
let mut cdf = [8192, 16384, 24576, 0];
adapt(&mut cdf, 1);
assert_eq!(cdf, [8192 - 256, 16384 + 512, 24576 + 256, 1]);
let mut cdf = [16384, 32];
adapt(&mut cdf, 0);
assert_eq!(cdf, [16384 + 256, 32]);
}
#[test]
fn a_single_equiprobable_bit() {
let mut encoder = SymbolEncoder::new();
encoder.bool_with(false, 1 << 14);
assert_eq!(encoder.finish(), [0b0010_0000]);
let mut encoder = SymbolEncoder::new();
encoder.bool_with(true, 1 << 14);
assert_eq!(encoder.finish(), [0b1100_0000]);
assert_eq!(SymbolEncoder::new().finish(), [0b1000_0000]);
}
#[test]
fn the_specification_decoder_reads_what_is_written() {
let mut state = 7;
for length in [0, 1, 2, 5, 40, 1000] {
let mut cdfs = ([4000, 9000, 20000, 31000, 0], [16384, 0], [100, 32000, 0]);
let mut encoder = SymbolEncoder::new();
let mut symbols = Vec::new();
for _ in 0..length {
let roll = next(&mut state);
let kind = roll % 4;
let symbol = (roll >> 8) as usize;
let value = match kind {
0 => {
let s = symbol % 5;
encoder.symbol(&mut cdfs.0, s);
s
}
1 => {
let s = symbol % 2;
encoder.symbol(&mut cdfs.1, s);
s
}
2 => {
let s = symbol % 3;
encoder.symbol(&mut cdfs.2, s);
s
}
_ => {
let v = symbol % 64;
encoder.literal(v as u32, 6);
v
}
};
symbols.push((kind, value));
}
let data = encoder.finish();
let mut cdfs = ([4000, 9000, 20000, 31000, 0], [16384, 0], [100, 32000, 0]);
let mut decoder = SpecDecoder::new(&data);
for &(kind, value) in &symbols {
let decoded = match kind {
0 => decoder.symbol(&mut cdfs.0, true),
1 => decoder.symbol(&mut cdfs.1, true),
2 => decoder.symbol(&mut cdfs.2, true),
_ => (0..6).fold(0, |x, _| 2 * x + decoder.symbol(&mut [16384, 0], false)),
};
assert_eq!(decoded, value, "length {length}");
}
if !data.is_empty() {
assert!(decoder.trailing_ok(), "length {length}");
}
}
}
#[test]
fn rates_follow_probabilities() {
let mut estimate = RateEstimate::default();
estimate.bool_with(false, 1 << 14);
assert!((estimate.bits - 1.0).abs() < 1e-9);
let mut cdf = [8192, 0];
estimate.symbol(&mut cdf, 1);
assert!((estimate.bits - (1.0 + (4.0f64 / 3.0).log2())).abs() < 0.01);
assert_eq!(cdf, [8192, 0]);
estimate.literal(5, 3);
assert!((estimate.bits - 4.415).abs() < 0.01);
}
}