#![forbid(unsafe_code)]
#[cfg(feature = "alloc")]
use alloc::vec::Vec;
use crate::huffman::{MAX_BITS, MAX_SYMBOL_VALUE};
#[derive(Clone)]
pub struct HuffmanEncodeTable {
num_bits: [u8; MAX_SYMBOL_VALUE + 1],
celt: [u64; MAX_SYMBOL_VALUE + 1],
description: Description,
table_log: u8,
}
#[cfg(feature = "alloc")]
impl HuffmanEncodeTable {
pub fn from_data(data: &[u8]) -> Option<Self> {
if data.is_empty() {
return None;
}
Self::from_histogram(&byte_histogram(data))
}
pub fn from_histogram(freqs: &[u32; MAX_SYMBOL_VALUE + 1]) -> Option<Self> {
let max_sym = freqs.iter().rposition(|&f| f > 0)?;
let mut syms = [0u8; MAX_SYMBOL_VALUE + 1];
let mut counts = [0u32; MAX_SYMBOL_VALUE + 1];
let mut n = 0usize;
for (s, &f) in freqs[..=max_sym].iter().enumerate() {
syms[n & MAX_SYMBOL_VALUE] = s as u8;
counts[n & MAX_SYMBOL_VALUE] = f;
n += usize::from(f > 0);
}
if n < 2 {
return None;
}
let syms = &syms[..n];
let counts = &mut counts[..n];
loop {
let (num_bits, table_log) = code_lengths(counts, syms);
let mut weights = [0u8; MAX_SYMBOL_VALUE + 1];
for &s in syms {
weights[s as usize] = table_log + 1 - num_bits[s as usize];
}
let mut hist = [0u32; WEIGHT_HIST_LEN];
for &s in &syms[..n - 1] {
hist[usize::from(weights[s as usize]) % WEIGHT_HIST_LEN] += 1;
}
hist[0] = (max_sym + 1 - n) as u32;
if let Some(description) = describe_weights(&weights[..max_sym], &hist) {
return Some(Self {
celt: code_entries(&weights, &num_bits, syms, table_log),
description,
num_bits,
table_log,
});
}
if counts.iter().all(|&c| c <= 1) {
return None;
}
for c in counts.iter_mut() {
*c = c.div_ceil(2);
}
}
}
pub fn from_decode_table(
decode_table: &[super::HuffmanDecodeEntry],
table_log: u8,
) -> Option<Self> {
let table_size = 1usize << table_log;
if decode_table.len() < table_size {
return None;
}
let mut num_bits_per_sym = [0u8; MAX_SYMBOL_VALUE + 1];
let mut max_sym = 0u8;
let mut seen = [false; MAX_SYMBOL_VALUE + 1];
for entry in &decode_table[..table_size] {
let s = entry.symbol;
if !seen[s as usize] {
num_bits_per_sym[s as usize] = entry.num_bits;
seen[s as usize] = true;
if s > max_sym {
max_sym = s;
}
}
}
let mut syms = [0u8; MAX_SYMBOL_VALUE + 1];
let mut n = 0usize;
let mut weights = [0u8; MAX_SYMBOL_VALUE + 1];
let mut num_bits = [0u8; MAX_SYMBOL_VALUE + 1];
for s in 0..=max_sym {
if seen[s as usize] {
syms[n] = s;
n += 1;
num_bits[s as usize] = num_bits_per_sym[s as usize];
weights[s as usize] = table_log + 1 - num_bits_per_sym[s as usize];
}
}
if n < 2 {
return None;
}
let explicit = &weights[..max_sym as usize];
let description =
describe_weights(explicit, &weight_histogram(explicit)).unwrap_or_default();
Some(Self {
celt: code_entries(&weights, &num_bits, &syms[..n], table_log),
description,
num_bits,
table_log,
})
}
pub fn table_log(&self) -> u8 {
self.table_log
}
pub fn estimate_bits(&self, freqs: &[u32; MAX_SYMBOL_VALUE + 1]) -> Option<u64> {
let mut bits = 0u64;
let mut missing = false;
for (&f, &n) in freqs.iter().zip(&self.num_bits) {
missing |= f > 0 && n == 0;
bits += u64::from(f) * u64::from(n);
}
(!missing).then_some(bits)
}
pub fn can_encode(&self, data: &[u8]) -> bool {
for &b in data {
if self.num_bits[b as usize] == 0 {
return false;
}
}
true
}
pub fn serialize_weights(&self) -> Vec<u8> {
self.weights_description().to_vec()
}
#[cfg(test)]
fn explicit_weights(&self) -> Vec<u8> {
let last = self.num_bits.iter().rposition(|&n| n > 0).unwrap_or(0);
self.num_bits[..last]
.iter()
.map(|&n| if n == 0 { 0 } else { self.table_log + 1 - n })
.collect()
}
pub fn weights_description(&self) -> &[u8] {
debug_assert_ne!(self.description.len, 0);
&self.description.bytes[..usize::from(self.description.len)]
}
pub fn encode_single_stream(&self, data: &[u8]) -> Vec<u8> {
let mut buf = Vec::new();
let len = self.encode_single_stream_into(data, &mut buf);
buf.truncate(len);
buf
}
pub fn encode_single_stream_into(&self, data: &[u8], out: &mut Vec<u8>) -> usize {
let need = stream_bound(data.len());
if out.len() < need {
out.resize(need, 0);
}
self.encode_stream(data, out)
}
pub fn encode_4_streams(&self, data: &[u8]) -> Vec<u8> {
let mut out = Vec::new();
let len = self.encode_4_streams_into(data, &mut out);
out.truncate(len);
out
}
pub fn encode_4_streams_into(&self, data: &[u8], out: &mut Vec<u8>) -> usize {
let seg = data.len().div_ceil(4);
let need = 6 + 4 * stream_bound(seg);
if out.len() < need {
out.resize(need, 0);
}
let mut pos = 6;
for k in 0..4 {
let stream = &data[(seg * k).min(data.len())..(seg * (k + 1)).min(data.len())];
let len = self.encode_stream(stream, &mut out[pos..]);
if k < 3 {
out[2 * k..2 * k + 2].copy_from_slice(&(len as u16).to_le_bytes());
}
pos += len;
}
pos
}
fn encode_stream(&self, data: &[u8], out: &mut [u8]) -> usize {
match self.table_log {
0..=7 => self.encode_stream_n::<8>(data, out),
8 => self.encode_stream_n::<7>(data, out),
9 => self.encode_stream_n::<6>(data, out),
_ => self.encode_stream_n::<5>(data, out),
}
}
fn encode_stream_n<const N: usize>(&self, data: &[u8], out: &mut [u8]) -> usize {
debug_assert!(7 + N * usize::from(self.table_log) <= 64);
debug_assert!(out.len() >= stream_bound(data.len()));
let celt = &self.celt;
let mut bits: u64 = 0;
let mut used: u64 = 0;
let mut pos = 0;
macro_rules! put {
($bits:ident, $used:ident, $sym:expr, $mask:expr) => {
let e = celt[usize::from($sym)];
$bits = ($bits >> (e & 63)) | (e & $mask);
$used = $used.wrapping_add(e);
};
}
macro_rules! group {
($bits:ident, $used:ident, $syms:expr) => {
for i in 0..N - 1 {
put!($bits, $used, $syms[N - 1 - i], !0);
}
put!($bits, $used, $syms[0], !15);
};
}
macro_rules! flush {
() => {
let nb = (used & 0xFF) as u32;
let word = bits.wrapping_shr(64 - nb);
out[pos..pos + 8].copy_from_slice(&word.to_le_bytes());
pos += (nb >> 3) as usize;
used &= 7;
};
}
let chunks = data.rchunks_exact(2 * N);
let head = chunks.remainder();
for c in chunks {
let (lo, hi) = c.split_at(N);
group!(bits, used, hi);
flush!();
let mut bits2: u64 = 0;
let mut used2: u64 = 0;
group!(bits2, used2, lo);
bits = (bits >> (used2 & 63)) | bits2;
used = used.wrapping_add(used2);
flush!();
}
for group in head.rchunks(N) {
for &b in group.iter().rev() {
put!(bits, used, b, !15);
}
flush!();
}
bits = (bits >> 1) | (1 << 63);
used += 1;
flush!();
pos + usize::from(used != 0)
}
pub fn compressed_size_single(&self, data: &[u8]) -> usize {
let total_bits: usize = data
.iter()
.map(|&b| self.num_bits[b as usize] as usize)
.sum();
(total_bits + 8) / 8
}
}
fn code_lengths(counts: &[u32], syms: &[u8]) -> ([u8; MAX_SYMBOL_VALUE + 1], u8) {
let n = syms.len();
debug_assert!((2..=MAX_SYMBOL_VALUE + 1).contains(&n));
let mut freq = [0u32; MAX_SYMBOL_VALUE + 1];
freq[..n].copy_from_slice(counts);
let max = freq[..n].iter().copied().max().unwrap_or(0);
let scale = (u32::BITS - max.leading_zeros()).saturating_sub(23);
if scale > 0 {
for f in &mut freq[..n] {
*f = (*f >> scale).max(1);
}
}
let mut keys = [0u32; MAX_SYMBOL_VALUE + 1];
let mut depths = [0u8; MAX_SYMBOL_VALUE + 1];
huffman_depths(&freq[..n], syms, &mut keys, &mut depths);
let mut bits = [0u8; MAX_SYMBOL_VALUE + 1];
let mut sorted = [0u32; MAX_SYMBOL_VALUE + 1];
for p in 0..n {
bits[p] = depths[n - 1 - p];
sorted[p] = keys[n - 1 - p] >> 8;
}
let max_bits = set_max_height(&mut bits[..n], &sorted[..n], MAX_BITS);
let mut num_bits = [0u8; MAX_SYMBOL_VALUE + 1];
for p in 0..n {
num_bits[(keys[n - 1 - p] & 0xFF) as usize] = bits[p];
}
(num_bits, max_bits)
}
fn set_max_height(bits: &mut [u8], counts: &[u32], target: u8) -> u8 {
let last = bits.len() - 1;
let largest = bits[last];
if largest <= target {
return largest;
}
let base_cost = 1i32 << (largest - target);
let mut total_cost = 0i32;
let mut n = last;
while bits[n] > target {
total_cost += base_cost - (1 << (largest - bits[n]));
bits[n] = target;
n -= 1;
}
while bits[n] == target {
n -= 1;
}
total_cost >>= largest - target;
const NONE: usize = usize::MAX;
let mut rank_last = [NONE; 16];
let mut current = target;
for pos in (0..=n).rev() {
if bits[pos] < current {
current = bits[pos];
rank_last[usize::from(target - current) & 15] = pos;
}
}
while total_cost > 0 {
let mut k = (31 - total_cost.leading_zeros()) as usize + 1;
while k > 1 {
let high = rank_last[k & 15];
let low = rank_last[(k - 1) & 15];
if high == NONE {
k -= 1;
continue;
}
if low == NONE || counts[high] <= 2 * counts[low] {
break;
}
k -= 1;
}
while k <= usize::from(MAX_BITS) && rank_last[k & 15] == NONE {
k += 1;
}
let pos = rank_last[k & 15];
total_cost -= 1 << (k - 1);
bits[pos] += 1;
if rank_last[(k - 1) & 15] == NONE {
rank_last[(k - 1) & 15] = pos;
}
rank_last[k & 15] = if pos == 0 || bits[pos - 1] != target - k as u8 {
NONE
} else {
pos - 1
};
}
while total_cost < 0 {
if rank_last[1] == NONE {
while bits[n] == target {
n -= 1;
}
bits[n + 1] -= 1;
rank_last[1] = n + 1;
} else {
bits[rank_last[1] + 1] -= 1;
rank_last[1] += 1;
}
total_cost += 1;
}
target
}
fn huffman_depths(
freq: &[u32],
syms: &[u8],
keys: &mut [u32; MAX_SYMBOL_VALUE + 1],
depths: &mut [u8; MAX_SYMBOL_VALUE + 1],
) {
const SYMS: usize = MAX_SYMBOL_VALUE + 1;
let n = syms.len();
debug_assert!((2..=SYMS).contains(&n));
const TOP: usize = 255;
let max = freq.iter().copied().max().unwrap_or(0) as usize;
let top = max.min(TOP);
let mut starts = [0u16; TOP + 1];
for &f in freq {
starts[(f as usize).min(top) & TOP] += 1;
}
let mut at = 0u16;
for start in &mut starts[..=top] {
let count = *start;
*start = at;
at += count;
}
for (&f, &s) in freq.iter().zip(syms) {
let bucket = &mut starts[(f as usize).min(top) & TOP];
keys[usize::from(*bucket) & MAX_SYMBOL_VALUE] = (f << 8) | u32::from(s);
*bucket += 1;
}
let keys = &mut keys[..n];
if max > TOP {
let frequent = usize::from(starts[TOP - 1]);
keys[frequent..].sort_unstable();
}
let mut leaves = [u32::MAX; 2 * SYMS];
for (l, &k) in leaves.iter_mut().zip(keys.iter()) {
*l = k >> 8;
}
let mut sums = [u32::MAX; SYMS];
let mut parent = [0u8; 2 * SYMS];
let (mut leaf, mut internal) = (0usize, 0usize);
for j in 0..n - 1 {
let mut pick = || {
let (l, i) = (leaves[leaf & (2 * SYMS - 1)], sums[internal & (SYMS - 1)]);
let take_leaf = l <= i;
let id = if take_leaf { leaf } else { SYMS + internal };
leaf += usize::from(take_leaf);
internal += usize::from(!take_leaf);
(id, if take_leaf { l } else { i })
};
let (a, fa) = pick();
let (b, fb) = pick();
sums[j] = fa + fb;
parent[a & (2 * SYMS - 1)] = j as u8;
parent[b & (2 * SYMS - 1)] = j as u8;
}
let mut depth = [0u8; SYMS];
for j in (0..n - 2).rev() {
depth[j] = depth[usize::from(parent[SYMS + j])] + 1;
}
for (d, &p) in depths[..n].iter_mut().zip(&parent) {
*d = depth[usize::from(p)] + 1;
}
}
#[derive(Clone, Copy)]
struct Description {
bytes: [u8; 128],
len: u8,
}
impl Default for Description {
fn default() -> Self {
Self {
bytes: [0; 128],
len: 0,
}
}
}
fn describe_weights(explicit: &[u8], hist: &[u32; WEIGHT_HIST_LEN]) -> Option<Description> {
let num_symbols = explicit.len();
let direct_len = 1 + num_symbols.div_ceil(2);
let mut d = Description::default();
if let Some(len) = compress_weights(explicit, hist, &mut d.bytes[1..])
&& (num_symbols > 128 || 1 + len < direct_len)
{
d.bytes[0] = len as u8;
d.len = 1 + len as u8;
return Some(d);
}
if num_symbols > 128 {
return None;
}
d.bytes[0] = (num_symbols + 127) as u8;
for (b, pair) in d.bytes[1..].iter_mut().zip(explicit.chunks(2)) {
*b = (pair[0] << 4) | pair.get(1).copied().unwrap_or(0);
}
d.len = direct_len as u8;
Some(d)
}
fn compress_weights(
weights: &[u8],
hist: &[u32; WEIGHT_HIST_LEN],
out: &mut [u8],
) -> Option<usize> {
use crate::fse::encode::{SymbolTransform, build_encode_table};
use crate::fse::table_builder::{normalize_counts_into, write_fse_table_description};
const LOG: u8 = 5;
const STATES: usize = 1 << LOG;
let n = weights.len();
if n < 2 {
return None;
}
debug_assert_eq!(hist, &weight_histogram(weights));
let max_w = hist.iter().rposition(|&c| c > 0)?;
if hist[..=max_w].iter().filter(|&&c| c > 0).count() < 2 {
return None;
}
let syms = max_w + 1;
let mut dist = [0i16; WEIGHT_HIST_LEN];
normalize_counts_into(&hist[..syms], LOG, &mut dist[..syms]);
let mut tt = [SymbolTransform {
delta_nb_bits: 0,
delta_find_state: 0,
}; WEIGHT_HIST_LEN];
let mut states = [0u16; STATES];
let mut spread = [0u16; STATES];
let mut cumul = [0u32; WEIGHT_HIST_LEN + 1];
build_encode_table(
&dist[..syms],
LOG,
&mut tt[..syms],
&mut states,
&mut spread,
&mut cumul[..=syms],
);
let mut w = WeightBits {
buf: [0; 128],
len: 0,
acc: 0,
used: 0,
};
write_fse_table_description(&dist[..syms], LOG, |v, nb| w.put(v, u32::from(nb)));
w.put(0, (8 - w.used % 8) % 8);
macro_rules! encode {
($state:ident, $sym:expr) => {{
let t = tt[usize::from($sym) % WEIGHT_HIST_LEN];
let nb = $state.wrapping_add(t.delta_nb_bits) >> 16;
w.put($state & ((1u32 << nb) - 1), nb);
$state =
u32::from(states[((($state >> nb) as i32 + t.delta_find_state) as usize) % STATES]);
}};
}
let init = |sym: u8| {
let t = tt[usize::from(sym) % WEIGHT_HIST_LEN];
let nb = t.delta_nb_bits.wrapping_add(1 << 16) >> 16;
let value = (nb << 16).wrapping_sub(t.delta_nb_bits);
u32::from(states[((value >> nb) as i32 + t.delta_find_state) as usize % STATES])
};
let mut i = n;
let (mut s1, mut s2);
if n % 2 == 1 {
s1 = init(weights[n - 1]);
s2 = init(weights[n - 2]);
i -= 3;
encode!(s1, weights[i]);
} else {
s2 = init(weights[n - 1]);
s1 = init(weights[n - 2]);
i -= 2;
}
while i > 0 {
encode!(s2, weights[i - 1]);
encode!(s1, weights[i - 2]);
i -= 2;
}
let mask = (1u32 << LOG) - 1;
w.put(s2 & mask, u32::from(LOG));
w.put(s1 & mask, u32::from(LOG));
w.put(1, 1);
let len = w.finish();
if len >= 128 {
return None;
}
out[..len].copy_from_slice(&w.buf[..len]);
Some(len)
}
struct WeightBits {
buf: [u8; 128],
len: usize,
acc: u64,
used: u32,
}
impl WeightBits {
fn put(&mut self, value: u32, nb: u32) {
self.acc |= u64::from(value) << self.used;
self.used += nb;
if self.used >= 32 {
if let Some(dst) = self.buf.get_mut(self.len..self.len + 4) {
dst.copy_from_slice(&(self.acc as u32).to_le_bytes());
}
self.len += 4;
self.acc >>= 32;
self.used -= 32;
}
}
fn finish(&mut self) -> usize {
let tail = self.used.div_ceil(8) as usize;
for k in 0..tail {
if let Some(b) = self.buf.get_mut(self.len + k) {
*b = (self.acc >> (8 * k)) as u8;
}
}
self.len + tail
}
}
const WEIGHT_HIST_LEN: usize = MAX_BITS as usize + 2;
fn weight_histogram(weights: &[u8]) -> [u32; WEIGHT_HIST_LEN] {
let mut hist = [0u32; WEIGHT_HIST_LEN];
for &w in weights {
hist[usize::from(w) % WEIGHT_HIST_LEN] += 1;
}
hist
}
pub fn byte_histogram(data: &[u8]) -> [u32; MAX_SYMBOL_VALUE + 1] {
let mut t = [[0u32; MAX_SYMBOL_VALUE + 1]; 4];
let (chunks, tail) = data.as_chunks::<8>();
for c in chunks {
let w = u64::from_le_bytes(*c);
t[0][(w & 0xFF) as usize] += 1;
t[1][((w >> 8) & 0xFF) as usize] += 1;
t[2][((w >> 16) & 0xFF) as usize] += 1;
t[3][((w >> 24) & 0xFF) as usize] += 1;
t[0][((w >> 32) & 0xFF) as usize] += 1;
t[1][((w >> 40) & 0xFF) as usize] += 1;
t[2][((w >> 48) & 0xFF) as usize] += 1;
t[3][(w >> 56) as usize] += 1;
}
for &b in tail {
t[0][b as usize] += 1;
}
core::array::from_fn(|i| t[0][i] + t[1][i] + t[2][i] + t[3][i])
}
const fn stream_bound(n: usize) -> usize {
n + n / 2 + 16
}
fn code_entries(
weights: &[u8; MAX_SYMBOL_VALUE + 1],
num_bits: &[u8; MAX_SYMBOL_VALUE + 1],
syms: &[u8],
table_log: u8,
) -> [u64; MAX_SYMBOL_VALUE + 1] {
let mut rank_count = [0u32; 16];
for &s in syms {
rank_count[usize::from(weights[s as usize]) & 15] += 1;
}
let mut rank_start = [0u32; 16];
let mut cumul = 0u32;
for w in 1..=usize::from(table_log) + 1 {
rank_start[w & 15] = cumul;
cumul += rank_count[w & 15] << (w - 1);
}
let mut celt = [0u64; MAX_SYMBOL_VALUE + 1];
for &s in syms {
let w = usize::from(weights[s as usize]);
let start = rank_start[w & 15];
rank_start[w & 15] += 1u32 << (w - 1);
let nb = u32::from(num_bits[s as usize]);
celt[s as usize] = (u64::from(start >> (w - 1)) << (64 - nb)) | u64::from(nb);
}
celt
}
#[cfg(test)]
mod tests {
use super::*;
fn fibonacci_symbols() -> Vec<u8> {
let mut data = Vec::new();
let (mut a, mut b) = (1usize, 1usize);
for sym in 0..20u8 {
data.extend(core::iter::repeat_n(sym, a));
(a, b) = (b, a + b);
}
data
}
#[test]
fn compressed_weights_roundtrip_through_parser() {
let mut data = Vec::new();
for s in 0..200u32 {
data.extend(core::iter::repeat_n(s as u8, 1 + (s * 7 % 23) as usize));
}
let table = HuffmanEncodeTable::from_data(&data).expect("table");
let desc = table.serialize_weights();
assert!(desc[0] < 128, "expected compressed header");
let (parsed, used) = crate::huffman::weights::parse_huffman_weights(&desc).expect("parse");
assert_eq!(used, desc.len());
assert_eq!(&parsed[..], &table.explicit_weights()[..]);
}
#[test]
fn compressed_weights_with_rare_weight_roundtrip() {
let mut data = Vec::new();
for s in 0..180u32 {
data.extend(core::iter::repeat_n(s as u8, 40 + (s % 3) as usize));
}
data.extend(core::iter::repeat_n(200u8, 5000));
data.push(201);
let table = HuffmanEncodeTable::from_data(&data).expect("table");
let desc = table.serialize_weights();
assert!(desc[0] < 128, "expected compressed header");
let (parsed, _) = crate::huffman::weights::parse_huffman_weights(&desc).expect("parse");
assert_eq!(&parsed[..], &table.explicit_weights()[..]);
}
#[test]
fn uniform_bytes_terminate_without_a_table() {
let data: Vec<u8> = (0..8192u32).map(|i| i as u8).collect();
assert!(HuffmanEncodeTable::from_data(&data).is_none());
}
#[test]
fn from_data_limits_code_length() {
let table = HuffmanEncodeTable::from_data(&fibonacci_symbols())
.expect("a deep tree must be length-limited, not rejected");
let tl = table.table_log;
assert!(tl <= MAX_BITS);
assert!(table.num_bits.iter().all(|&n| n <= tl));
let kraft: u32 = table.num_bits[..20].iter().map(|&n| 1u32 << (tl - n)).sum();
assert_eq!(kraft, 1 << tl);
}
#[test]
fn from_decode_table_roundtrip() {
let data = b"hello world hello world hello world!";
let original = HuffmanEncodeTable::from_data(data).unwrap();
let weights_raw = original.serialize_weights();
let (parsed_weights, _) =
crate::huffman::weights::parse_huffman_weights(&weights_raw).unwrap();
let (decode_table, decode_log) =
crate::huffman::weights::build_huffman_decode_table(&parsed_weights).unwrap();
let rebuilt = HuffmanEncodeTable::from_decode_table(&decode_table, decode_log).unwrap();
assert_eq!(original.table_log, rebuilt.table_log);
assert_eq!(original.explicit_weights(), rebuilt.explicit_weights());
assert_eq!(original.num_bits, rebuilt.num_bits);
assert_eq!(original.celt, rebuilt.celt);
let encoded = rebuilt.encode_single_stream(data);
let decoded = crate::huffman::decode::decode_single_stream(
&decode_table,
decode_log,
&encoded,
data.len(),
)
.unwrap();
assert_eq!(decoded, data);
}
#[test]
fn from_decode_table_skewed() {
let mut data = vec![0u8; 900];
data.extend(vec![1u8; 80]);
data.extend(vec![2u8; 15]);
data.extend(vec![3u8; 5]);
let original = HuffmanEncodeTable::from_data(&data).unwrap();
let weights_raw = original.serialize_weights();
let (parsed_weights, _) =
crate::huffman::weights::parse_huffman_weights(&weights_raw).unwrap();
let (decode_table, decode_log) =
crate::huffman::weights::build_huffman_decode_table(&parsed_weights).unwrap();
let rebuilt = HuffmanEncodeTable::from_decode_table(&decode_table, decode_log).unwrap();
assert_eq!(original.celt, rebuilt.celt);
assert_eq!(original.num_bits, rebuilt.num_bits);
let encoded = rebuilt.encode_single_stream(&data);
let decoded = crate::huffman::decode::decode_single_stream(
&decode_table,
decode_log,
&encoded,
data.len(),
)
.unwrap();
assert_eq!(decoded, data);
}
#[test]
fn roundtrip_simple() {
let data = b"hello world hello world hello world!";
let table = HuffmanEncodeTable::from_data(data).unwrap();
let weights_raw = table.serialize_weights();
let encoded = table.encode_single_stream(data);
let (parsed_weights, _) =
crate::huffman::weights::parse_huffman_weights(&weights_raw).unwrap();
let (decode_table, decode_log) =
crate::huffman::weights::build_huffman_decode_table(&parsed_weights).unwrap();
let decoded = crate::huffman::decode::decode_single_stream(
&decode_table,
decode_log,
&encoded,
data.len(),
)
.unwrap();
assert_eq!(decoded, data);
}
#[test]
fn roundtrip_4_streams() {
let data: Vec<u8> = b"ABCDEFGH".iter().cycle().take(1024).copied().collect();
let table = HuffmanEncodeTable::from_data(&data).unwrap();
let weights_raw = table.serialize_weights();
let encoded = table.encode_4_streams(&data);
let (parsed_weights, _) =
crate::huffman::weights::parse_huffman_weights(&weights_raw).unwrap();
let (decode_table, decode_log) =
crate::huffman::weights::build_huffman_decode_table(&parsed_weights).unwrap();
let decoded = crate::huffman::decode::decode_4_streams(
&decode_table,
decode_log,
&encoded,
data.len(),
)
.unwrap();
assert_eq!(decoded, data);
}
#[test]
fn roundtrip_all_bytes() {
let data: Vec<u8> = (0u8..=127).cycle().take(4096).collect();
let table = HuffmanEncodeTable::from_data(&data).unwrap();
let weights_raw = table.serialize_weights();
let encoded = table.encode_single_stream(&data);
let (parsed_weights, _) =
crate::huffman::weights::parse_huffman_weights(&weights_raw).unwrap();
let (decode_table, decode_log) =
crate::huffman::weights::build_huffman_decode_table(&parsed_weights).unwrap();
let decoded = crate::huffman::decode::decode_single_stream(
&decode_table,
decode_log,
&encoded,
data.len(),
)
.unwrap();
assert_eq!(decoded, data);
}
#[test]
fn skewed_distribution() {
let mut data = vec![0u8; 900];
data.extend(vec![1u8; 80]);
data.extend(vec![2u8; 15]);
data.extend(vec![3u8; 5]);
let table = HuffmanEncodeTable::from_data(&data).unwrap();
assert!(table.num_bits[0] < table.num_bits[3]);
let weights_raw = table.serialize_weights();
let encoded = table.encode_single_stream(&data);
let (parsed_weights, _) =
crate::huffman::weights::parse_huffman_weights(&weights_raw).unwrap();
let (decode_table, decode_log) =
crate::huffman::weights::build_huffman_decode_table(&parsed_weights).unwrap();
let decoded = crate::huffman::decode::decode_single_stream(
&decode_table,
decode_log,
&encoded,
data.len(),
)
.unwrap();
assert_eq!(decoded, data);
}
#[test]
fn two_symbols() {
let mut data = vec![0u8; 500];
data.extend(vec![1u8; 500]);
let table = HuffmanEncodeTable::from_data(&data).unwrap();
assert_eq!(table.num_bits[0], 1);
assert_eq!(table.num_bits[1], 1);
let encoded = table.encode_single_stream(&data);
let weights_raw = table.serialize_weights();
let (parsed_weights, _) =
crate::huffman::weights::parse_huffman_weights(&weights_raw).unwrap();
let (decode_table, decode_log) =
crate::huffman::weights::build_huffman_decode_table(&parsed_weights).unwrap();
let decoded = crate::huffman::decode::decode_single_stream(
&decode_table,
decode_log,
&encoded,
data.len(),
)
.unwrap();
assert_eq!(decoded, data);
}
}