use alloc::vec::Vec;
use crate::utils::bitstream::{BitReader, BitWriter};
use crate::{Error, Result};
const MAX_SYMBOLS: usize = 256;
const MAX_BITS: u32 = 15;
#[derive(Clone, Debug)]
pub struct HuffEncoder {
codes: [u32; MAX_SYMBOLS],
lens: [u8; MAX_SYMBOLS],
max_bits: u32,
}
impl Default for HuffEncoder {
fn default() -> Self {
Self {
codes: [0; MAX_SYMBOLS],
lens: [0; MAX_SYMBOLS],
max_bits: 0,
}
}
}
#[derive(Clone, Debug)]
pub struct HuffDecoder {
table: Vec<(u8, u8)>,
max_bits: u32,
}
#[inline]
fn reverse_bits(mut code: u32, len: u32) -> u32 {
let mut r = 0u32;
for _ in 0..len {
r = (r << 1) | (code & 1);
code >>= 1;
}
r
}
pub fn build_encoder(freq: &[u32; MAX_SYMBOLS]) -> Option<HuffEncoder> {
let mut leaves: Vec<(u32, u16)> = Vec::new();
for (sym, &f) in freq.iter().enumerate() {
if f > 0 {
leaves.push((f, sym as u16));
}
}
if leaves.is_empty() {
return None;
}
if leaves.len() == 1 {
let mut enc = HuffEncoder::default();
let s = leaves[0].1 as usize;
enc.codes[s] = 0;
enc.lens[s] = 1;
enc.max_bits = 1;
return Some(enc);
}
#[derive(Clone, Copy)]
struct Node {
freq: u32,
left: i32,
right: i32,
}
let mut nodes: Vec<Node> = Vec::new();
let mut heap: Vec<usize> = Vec::new();
let less = |nodes: &[Node], a: usize, b: usize| -> bool {
nodes[a].freq < nodes[b].freq || (nodes[a].freq == nodes[b].freq && a < b)
};
let heap_push = |heap: &mut Vec<usize>, nodes: &[Node], idx: usize| {
heap.push(idx);
let mut i = heap.len() - 1;
while i > 0 {
let p = (i - 1) / 2;
if !less(nodes, heap[i], heap[p]) {
break;
}
heap.swap(p, i);
i = p;
}
};
let heap_pop = |heap: &mut Vec<usize>, nodes: &[Node]| -> Option<usize> {
if heap.is_empty() {
return None;
}
let res = heap[0];
let last = heap.pop().unwrap();
if !heap.is_empty() {
heap[0] = last;
let mut i = 0;
loop {
let l = 2 * i + 1;
let r = 2 * i + 2;
let mut s = i;
if l < heap.len() && less(nodes, heap[l], heap[s]) {
s = l;
}
if r < heap.len() && less(nodes, heap[r], heap[s]) {
s = r;
}
if s == i {
break;
}
heap.swap(i, s);
i = s;
}
}
Some(res)
};
for &(f, s) in &leaves {
let idx = nodes.len();
nodes.push(Node {
freq: f,
left: !(s as i32),
right: -1,
});
heap_push(&mut heap, &nodes, idx);
}
while heap.len() > 1 {
let a = heap_pop(&mut heap, &nodes).unwrap();
let b = heap_pop(&mut heap, &nodes).unwrap();
let idx = nodes.len();
nodes.push(Node {
freq: nodes[a].freq.saturating_add(nodes[b].freq),
left: a as i32,
right: b as i32,
});
heap_push(&mut heap, &nodes, idx);
}
let root = heap[0];
let mut lens = [0u8; MAX_SYMBOLS];
fn walk(nodes: &[Node], idx: usize, depth: u8, lens: &mut [u8; MAX_SYMBOLS]) {
let n = nodes[idx];
if n.left < 0 {
let sym = (!n.left) as usize;
lens[sym] = depth.max(1).min(MAX_BITS as u8);
return;
}
let d = depth.saturating_add(1).min(MAX_BITS as u8 + 1);
walk(nodes, n.left as usize, d, lens);
if n.right >= 0 {
walk(nodes, n.right as usize, d, lens);
}
}
walk(&nodes, root, 0, &mut lens);
if lens.contains(&(MAX_BITS as u8)) {
let mut kraft = 0u32;
for &l in &lens {
if l > 0 {
kraft += 1u32 << (MAX_BITS - l as u32);
}
}
if kraft > (1u32 << MAX_BITS) {
let nsym = leaves.len().next_power_of_two().trailing_zeros().max(1) as u8;
let nsym = nsym.min(MAX_BITS as u8);
lens = [0u8; MAX_SYMBOLS];
for &(_, s) in &leaves {
lens[s as usize] = nsym;
}
}
}
let mut enc = HuffEncoder {
codes: [0; MAX_SYMBOLS],
lens,
max_bits: 0,
};
assign_canonical_codes(&mut enc);
Some(enc)
}
fn assign_canonical_codes(enc: &mut HuffEncoder) {
let mut bl_count = [0u32; (MAX_BITS as usize) + 1];
let mut max_bits = 0u32;
for &l in &enc.lens {
if l > 0 {
bl_count[l as usize] += 1;
max_bits = max_bits.max(l as u32);
}
}
enc.max_bits = max_bits;
let mut next_code = [0u32; (MAX_BITS as usize) + 1];
let mut code = 0u32;
for bits in 1..=max_bits as usize {
code = (code + bl_count[bits - 1]) << 1;
next_code[bits] = code;
}
for sym in 0..MAX_SYMBOLS {
let len = enc.lens[sym] as u32;
if len > 0 {
let canonical = next_code[len as usize];
next_code[len as usize] += 1;
enc.codes[sym] = reverse_bits(canonical, len);
}
}
}
impl HuffEncoder {
#[inline]
pub fn encode(&self, w: &mut BitWriter, symbol: u8) {
let len = self.lens[symbol as usize] as u32;
debug_assert!(len > 0, "encoding unused symbol {symbol}");
w.write_bits(self.codes[symbol as usize], len);
}
pub fn write_table(&self, out: &mut Vec<u8>) {
out.extend_from_slice(&self.lens);
}
pub fn lengths(&self) -> &[u8; MAX_SYMBOLS] {
&self.lens
}
}
pub fn decoder_from_lengths(lens: &[u8; MAX_SYMBOLS]) -> Result<HuffDecoder> {
let mut max_bits = 0u32;
for &l in lens {
if l as u32 > MAX_BITS {
return Err(Error::Decompression(format!(
"huffman length {l} > {MAX_BITS}"
)));
}
if l > 0 {
max_bits = max_bits.max(l as u32);
}
}
if max_bits == 0 {
return Err(Error::Decompression("empty huffman table".into()));
}
let mut bl_count = [0u32; (MAX_BITS as usize) + 1];
for &l in lens {
if l > 0 {
bl_count[l as usize] += 1;
}
}
let mut next_code = [0u32; (MAX_BITS as usize) + 1];
let mut code = 0u32;
for bits in 1..=max_bits as usize {
code = (code + bl_count[bits - 1]) << 1;
next_code[bits] = code;
}
let size = 1usize << max_bits;
let mut table = vec![(0u8, 0u8); size];
for (sym, &len_u8) in lens.iter().enumerate().take(MAX_SYMBOLS) {
let len = len_u8 as u32;
if len == 0 {
continue;
}
let canonical = next_code[len as usize];
next_code[len as usize] += 1;
let rev = reverse_bits(canonical, len);
let free = max_bits - len;
let count = 1usize << free;
for i in 0..count {
let idx = (rev as usize) | (i << len as usize);
if table[idx].1 < len as u8 {
table[idx] = (sym as u8, len as u8);
}
}
}
Ok(HuffDecoder { table, max_bits })
}
impl HuffDecoder {
#[inline]
pub fn decode(&self, r: &mut BitReader<'_>) -> Result<u8> {
r.ensure_bits();
let peek = r
.peek_bits_padded(self.max_bits)
.ok_or_else(|| Error::Decompression("truncated huffman bitstream".into()))?;
let (sym, len) = self.table[peek as usize];
if len == 0 {
return Err(Error::Decompression("invalid huffman code".into()));
}
let _ = r
.read_bits(len as u32)
.ok_or_else(|| Error::Decompression("truncated huffman code bits".into()))?;
Ok(sym)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn huff_roundtrip() {
let mut freq = [0u32; 256];
for b in b"aaabbc" {
freq[*b as usize] += 1;
}
let enc = build_encoder(&freq).unwrap();
let mut w = BitWriter::new();
for &b in b"aaabbc" {
enc.encode(&mut w, b);
}
let bytes = w.finish();
let dec = decoder_from_lengths(enc.lengths()).unwrap();
let mut r = BitReader::new(&bytes);
let mut out = Vec::new();
for _ in 0..6 {
out.push(dec.decode(&mut r).unwrap());
}
assert_eq!(out, b"aaabbc");
}
#[test]
fn huff_large_alphabet() {
let mut freq = [0u32; 256];
for i in 0..36u8 {
let c = if i < 26 { b'A' + i } else { b'0' + (i - 26) };
freq[c as usize] = 200;
}
let enc = build_encoder(&freq).unwrap();
let mut data = Vec::new();
for _ in 0..200 {
data.extend_from_slice(b"ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789");
}
let mut w = BitWriter::new();
for &b in &data {
enc.encode(&mut w, b);
}
let bytes = w.finish();
let dec = decoder_from_lengths(enc.lengths()).unwrap();
let mut r = BitReader::new(&bytes);
let mut out = Vec::with_capacity(data.len());
for i in 0..data.len() {
match dec.decode(&mut r) {
Ok(s) => out.push(s),
Err(e) => panic!("at {i}: {e}"),
}
}
assert_eq!(out, data);
}
}