use crate::constants::{MAX_SYMBOLS, MAX_GROUPS, MAX_CODE_LEN, MIN_CODE_LEN, GROUP_SIZE};
use crate::error::Error;
use crate::bitio::{BitReader, BitWriter};
#[derive(Clone)]
pub struct HuffTable {
pub lengths: [u8; MAX_SYMBOLS],
pub n_symbols: usize,
pub codes: [u32; MAX_SYMBOLS],
}
impl HuffTable {
pub const fn new() -> Self {
Self {
lengths: [0; MAX_SYMBOLS],
n_symbols: 0,
codes: [0; MAX_SYMBOLS],
}
}
pub fn build_codes(&mut self) -> Result<(), Error> {
let mut min_len = MAX_CODE_LEN;
let mut max_len = 0u32;
for i in 0..self.n_symbols {
let l = self.lengths[i] as u32;
if l > 0 {
if l < min_len {
min_len = l;
}
if l > max_len {
max_len = l;
}
}
}
if max_len > MAX_CODE_LEN {
return Err(Error::BadHuffmanTable);
}
let mut bl_count = [0u32; (MAX_CODE_LEN + 1) as usize];
for i in 0..self.n_symbols {
bl_count[self.lengths[i] as usize] += 1;
}
bl_count[0] = 0;
let mut next_code = [0u32; (MAX_CODE_LEN + 1) as usize];
let mut code = 0u32;
for bits in 1..=max_len {
code = (code + bl_count[(bits - 1) as usize]) << 1;
next_code[bits as usize] = code;
}
for i in 0..self.n_symbols {
let l = self.lengths[i] as u32;
if l > 0 {
self.codes[i] = next_code[l as usize];
next_code[l as usize] += 1;
}
}
Ok(())
}
}
pub struct HuffTables {
pub tables: [HuffTable; MAX_GROUPS],
pub n_groups: usize,
pub n_symbols: usize,
}
impl HuffTables {
pub fn new() -> Self {
Self {
tables: [
HuffTable::new(),
HuffTable::new(),
HuffTable::new(),
HuffTable::new(),
HuffTable::new(),
HuffTable::new(),
],
n_groups: 0,
n_symbols: 0,
}
}
}
pub fn generate_tables(
freq: &[u32],
n_symbols: usize,
tables: &mut HuffTables,
) {
tables.n_symbols = n_symbols;
tables.n_groups = 1;
let mut sorted: [(u32, u16); MAX_SYMBOLS] = [(0, 0); MAX_SYMBOLS];
for i in 0..n_symbols {
sorted[i] = (freq[i], i as u16);
}
for i in 1..n_symbols {
let key = sorted[i];
let mut j = i;
while j > 0 && sorted[j - 1].0 < key.0 {
sorted[j] = sorted[j - 1];
j -= 1;
}
sorted[j] = key;
}
let table = &mut tables.tables[0];
table.n_symbols = n_symbols;
if n_symbols <= 2 {
for i in 0..n_symbols {
table.lengths[sorted[i].1 as usize] = 1;
}
} else {
let total_freq: u64 = freq[..n_symbols].iter().map(|&f| f as u64).sum();
if total_freq == 0 {
let bits = log2_ceil(n_symbols as u32).max(1);
for i in 0..n_symbols {
table.lengths[i] = bits as u8;
}
} else {
for i in 0..n_symbols {
let f = freq[i] as u64;
if f == 0 {
table.lengths[i] = MAX_CODE_LEN as u8;
} else {
let ideal = if total_freq <= f {
1
} else {
let ratio = ((total_freq + f - 1) / f) as u32;
log2_ceil(ratio).max(1)
};
let clamped = ideal.clamp(MIN_CODE_LEN, MAX_CODE_LEN);
table.lengths[i] = clamped as u8;
}
}
}
}
let kraft_limit = 1u32 << MAX_CODE_LEN;
loop {
let mut kraft_sum = 0u32;
for i in 0..n_symbols {
let l = table.lengths[i] as u32;
if l > 0 && l <= MAX_CODE_LEN {
kraft_sum = kraft_sum.saturating_add(1u32 << (MAX_CODE_LEN - l));
}
}
if kraft_sum <= kraft_limit {
break;
}
let mut min_len = MAX_CODE_LEN as u8;
let mut min_idx = 0;
for i in 0..n_symbols {
if table.lengths[i] > 0 && table.lengths[i] < min_len {
min_len = table.lengths[i];
min_idx = i;
}
}
table.lengths[min_idx] += 1;
}
let _ = table.build_codes();
}
fn log2_ceil(n: u32) -> u32 {
if n <= 1 {
return 0;
}
32 - (n - 1).leading_zeros()
}
pub fn write_tables(writer: &mut BitWriter, tables: &HuffTables) -> Result<(), Error> {
let n_groups = tables.n_groups;
let n_symbols = tables.n_symbols;
for g in 0..n_groups {
let table = &tables.tables[g];
let mut current_len = table.lengths[0] as i32;
writer.write_bits(5, current_len as u32)?;
for i in 0..n_symbols {
let target_len = table.lengths[i] as i32;
while current_len < target_len {
writer.write_bits(2, 0b10)?; current_len += 1;
}
while current_len > target_len {
writer.write_bits(2, 0b11)?; current_len -= 1;
}
writer.write_bit(0)?; }
}
Ok(())
}
pub fn write_selectors(
writer: &mut BitWriter,
selectors: &[u8],
n_selectors: usize,
n_groups: usize,
) -> Result<(), Error> {
let mut mtf_list = [0u8; MAX_GROUPS];
for i in 0..n_groups {
mtf_list[i] = i as u8;
}
for i in 0..n_selectors {
let sel = selectors[i];
let mut pos = 0;
while pos < n_groups && mtf_list[pos] != sel {
pos += 1;
}
if pos > 0 {
let ch = mtf_list[pos];
let mut j = pos;
while j > 0 {
mtf_list[j] = mtf_list[j - 1];
j -= 1;
}
mtf_list[0] = ch;
}
for _ in 0..pos {
writer.write_bit(1)?;
}
writer.write_bit(0)?;
}
Ok(())
}
pub fn read_tables(
reader: &mut BitReader,
n_groups: usize,
n_symbols: usize,
tables: &mut HuffTables,
) -> Result<(), Error> {
tables.n_groups = n_groups;
tables.n_symbols = n_symbols;
for g in 0..n_groups {
let table = &mut tables.tables[g];
table.n_symbols = n_symbols;
let mut current_len = reader.read_bits(5)? as i32;
for i in 0..n_symbols {
loop {
if current_len < MIN_CODE_LEN as i32 || current_len > MAX_CODE_LEN as i32 {
return Err(Error::BadHuffmanTable);
}
let bit = reader.read_bit()?;
if bit == 0 {
break; }
let bit2 = reader.read_bit()?;
if bit2 == 0 {
current_len += 1; } else {
current_len -= 1; }
}
table.lengths[i] = current_len as u8;
}
table.build_codes()?;
}
Ok(())
}
pub fn read_selectors(
reader: &mut BitReader,
n_selectors: usize,
n_groups: usize,
selectors: &mut [u8],
) -> Result<(), Error> {
let mut mtf_list = [0u8; MAX_GROUPS];
for i in 0..n_groups {
mtf_list[i] = i as u8;
}
for i in 0..n_selectors {
let mut pos = 0usize;
while reader.read_bool()? {
pos += 1;
if pos >= n_groups {
return Err(Error::BadSelector);
}
}
let sel = mtf_list[pos];
if pos > 0 {
let mut j = pos;
while j > 0 {
mtf_list[j] = mtf_list[j - 1];
j -= 1;
}
mtf_list[0] = sel;
}
selectors[i] = sel;
}
Ok(())
}
pub fn decode_symbols(
reader: &mut BitReader,
tables: &HuffTables,
selectors: &[u8],
n_selectors: usize,
symbols: &mut [u16],
max_symbols: usize,
) -> Result<usize, Error> {
let eob = tables.n_symbols as u16 - 1;
let mut out_pos = 0;
let mut group_idx = 0;
let mut sym_in_group = 0;
loop {
if group_idx >= n_selectors {
return Err(Error::BadSelector);
}
let table_idx = selectors[group_idx] as usize;
if table_idx >= tables.n_groups {
return Err(Error::BadSelector);
}
let table = &tables.tables[table_idx];
let sym = decode_one_symbol(reader, table)?;
if sym == eob {
break;
}
if out_pos >= max_symbols {
return Err(Error::RleOverflow);
}
symbols[out_pos] = sym;
out_pos += 1;
sym_in_group += 1;
if sym_in_group >= GROUP_SIZE {
sym_in_group = 0;
group_idx += 1;
}
}
Ok(out_pos)
}
fn decode_one_symbol(reader: &mut BitReader, table: &HuffTable) -> Result<u16, Error> {
let mut code = 0u32;
let mut first_code = [0u32; (MAX_CODE_LEN + 1) as usize];
let mut first_symbol = [0u16; (MAX_CODE_LEN + 1) as usize];
let mut counts = [0u32; (MAX_CODE_LEN + 1) as usize];
for i in 0..table.n_symbols {
let l = table.lengths[i] as usize;
counts[l] += 1;
}
let mut sorted_symbols = [0u16; MAX_SYMBOLS];
let mut pos = 0;
for l in (MIN_CODE_LEN as usize)..=(MAX_CODE_LEN as usize) {
first_code[l] = code;
first_symbol[l] = pos as u16;
for sym in 0..table.n_symbols {
if table.lengths[sym] as usize == l {
sorted_symbols[pos] = sym as u16;
pos += 1;
}
}
code = (code + counts[l]) << 1;
}
let mut value = 0u32;
for l in (MIN_CODE_LEN as usize)..=(MAX_CODE_LEN as usize) {
value = (value << 1) | reader.read_bit()? as u32;
if counts[l] > 0 && value >= first_code[l] && value < first_code[l] + counts[l] {
let offset = (value - first_code[l]) as usize;
return Ok(sorted_symbols[first_symbol[l] as usize + offset]);
}
}
Err(Error::BadHuffmanTable)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn log2_ceil_values() {
assert_eq!(log2_ceil(1), 0);
assert_eq!(log2_ceil(2), 1);
assert_eq!(log2_ceil(3), 2);
assert_eq!(log2_ceil(4), 2);
assert_eq!(log2_ceil(5), 3);
assert_eq!(log2_ceil(256), 8);
}
#[test]
fn build_simple_codes() {
let mut table = HuffTable::new();
table.n_symbols = 4;
table.lengths[0] = 1;
table.lengths[1] = 2;
table.lengths[2] = 3;
table.lengths[3] = 3;
table.build_codes().unwrap();
assert_eq!(table.codes[0], 0b0);
assert_eq!(table.codes[1], 0b10);
assert_eq!(table.codes[2], 0b110);
assert_eq!(table.codes[3], 0b111);
}
}