use super::error::{HuffmanTable, InflateError};
use super::tables::{
CODE_LENGTH_SYMBOLS, DIST_BASE, DIST_EXTRA, END_OF_BLOCK, FIXED_LITLEN_SYMBOLS, LENGTH_BASE,
LENGTH_EXTRA, MAX_CODE_BITS,
};
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum Symbol {
Literal(u8),
EndOfBlock,
Base { base: u16, extra: u8 },
Subtable { offset: u16, bits: u8 },
Invalid,
}
#[derive(Clone, Copy, Debug)]
pub(crate) struct Entry {
pub(crate) symbol: Symbol,
pub(crate) length: u8,
}
const INVALID: Entry = Entry {
symbol: Symbol::Invalid,
length: 0,
};
#[derive(Debug)]
pub(crate) struct DecodeTable {
table: HuffmanTable,
primary_bits: u32,
entries: Vec<Entry>,
}
impl DecodeTable {
pub(crate) fn new(table: HuffmanTable) -> Self {
let primary_bits = match table {
HuffmanTable::LiteralLength => 10,
HuffmanTable::Distance => 8,
HuffmanTable::CodeLength => 7,
};
Self {
table,
primary_bits,
entries: vec![INVALID; 1 << primary_bits],
}
}
pub(crate) fn build(&mut self, lengths: &[u8]) -> Result<(), InflateError> {
debug_assert!(lengths.len() <= FIXED_LITLEN_SYMBOLS);
let mut counts = [0u16; MAX_CODE_BITS + 1];
for &length in lengths {
counts[usize::from(length)] += 1;
}
counts[0] = 0;
self.validate(&counts)?;
let mut next_code = [0u32; MAX_CODE_BITS + 1];
let mut code = 0;
for (length, next) in next_code.iter_mut().enumerate().skip(1) {
code = (code + u32::from(counts[length - 1])) << 1;
*next = code;
}
let mut reversed = [0u32; FIXED_LITLEN_SYMBOLS];
for (slot, &length) in reversed.iter_mut().zip(lengths) {
if length > 0 {
let length = usize::from(length);
*slot = next_code[length].reverse_bits() >> (32 - length);
next_code[length] += 1;
}
}
self.entries.clear();
self.entries.resize(1 << self.primary_bits, INVALID);
let subtables = self.allocate_subtables(lengths, &reversed);
for (symbol, (&length, &code)) in lengths.iter().zip(&reversed).enumerate() {
if length > 0 {
let entry = Entry {
symbol: self.symbol(symbol),
length,
};
self.place(entry, code as usize, &subtables);
}
}
Ok(())
}
pub(crate) fn lookup(&self, bits: u64) -> Entry {
let primary_mask = (1 << self.primary_bits) - 1;
let entry = self.entries[(bits & primary_mask) as usize];
match entry.symbol {
Symbol::Subtable { offset, bits: sub } => {
let sub_index = (bits >> self.primary_bits) & ((1 << sub) - 1);
self.entries[usize::from(offset) + sub_index as usize]
}
_ => entry,
}
}
fn validate(&self, counts: &[u16; MAX_CODE_BITS + 1]) -> Result<(), InflateError> {
let mut unused: i32 = 1;
for &count in &counts[1..] {
unused = 2 * unused - i32::from(count);
if unused < 0 {
return Err(InflateError::OversubscribedCode(self.table));
}
}
let longest = counts.iter().rposition(|&count| count > 0).unwrap_or(0);
let incomplete = unused > 0 && longest > 0;
if incomplete && (longest != 1 || self.table == HuffmanTable::CodeLength) {
return Err(InflateError::IncompleteCode(self.table));
}
Ok(())
}
fn allocate_subtables(&mut self, lengths: &[u8], reversed: &[u32]) -> Vec<(u16, u8)> {
let primary_size = 1 << self.primary_bits;
let primary_mask = primary_size - 1;
let mut subtables = vec![(0u16, 0u8); primary_size];
for (&length, &code) in lengths.iter().zip(reversed) {
if u32::from(length) > self.primary_bits {
let bits = &mut subtables[code as usize & primary_mask].1;
*bits = (*bits).max(length - self.primary_bits as u8);
}
}
for (prefix, (offset, bits)) in subtables.iter_mut().enumerate() {
if *bits > 0 {
*offset = self.entries.len() as u16;
self.entries[prefix] = Entry {
symbol: Symbol::Subtable {
offset: *offset,
bits: *bits,
},
length: self.primary_bits as u8,
};
self.entries
.resize(self.entries.len() + (1 << *bits), INVALID);
}
}
subtables
}
fn place(&mut self, entry: Entry, code: usize, subtables: &[(u16, u8)]) {
let length = usize::from(entry.length);
let primary_bits = self.primary_bits as usize;
let (slots, step) = if length <= primary_bits {
(&mut self.entries[code..1 << primary_bits], 1 << length)
} else {
let (offset, bits) = subtables[code & ((1 << primary_bits) - 1)];
let offset = usize::from(offset);
let first = offset + (code >> primary_bits);
(
&mut self.entries[first..offset + (1 << bits)],
1 << (length - primary_bits),
)
};
for slot in slots.iter_mut().step_by(step) {
*slot = entry;
}
}
fn symbol(&self, symbol: usize) -> Symbol {
match self.table {
HuffmanTable::CodeLength => {
debug_assert!(symbol < CODE_LENGTH_SYMBOLS);
Symbol::Literal(symbol as u8)
}
HuffmanTable::LiteralLength => match symbol {
0..=255 => Symbol::Literal(symbol as u8),
END_OF_BLOCK => Symbol::EndOfBlock,
_ => match (
LENGTH_BASE.get(symbol - 257),
LENGTH_EXTRA.get(symbol - 257),
) {
(Some(&base), Some(&extra)) => Symbol::Base { base, extra },
_ => Symbol::Invalid,
},
},
HuffmanTable::Distance => match (DIST_BASE.get(symbol), DIST_EXTRA.get(symbol)) {
(Some(&base), Some(&extra)) => Symbol::Base { base, extra },
_ => Symbol::Invalid,
},
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::deflate::huffman::HuffmanCode;
#[test]
fn long_codes_resolve_through_subtables() {
let mut lengths: Vec<u8> = (1..=15).collect();
lengths.push(15);
let mut table = DecodeTable::new(HuffmanTable::LiteralLength);
table.build(&lengths).unwrap();
let code = HuffmanCode::from_lengths(lengths.clone());
for (symbol, (&length, &bits)) in lengths.iter().zip(&code.codes).enumerate() {
let entry = table.lookup(u64::from(bits) | 0xABCD << length);
assert_eq!(
entry.symbol,
Symbol::Literal(symbol as u8),
"symbol {symbol}"
);
assert_eq!(entry.length, length);
}
}
#[test]
fn symbols_map_to_lengths_distances_and_reserved_codes() {
let mut table = DecodeTable::new(HuffmanTable::LiteralLength);
table
.build(&crate::deflate::tables::fixed_litlen_lengths())
.unwrap();
let code =
HuffmanCode::from_lengths(crate::deflate::tables::fixed_litlen_lengths().to_vec());
let lookup = |symbol: usize| table.lookup(u64::from(code.codes[symbol])).symbol;
assert_eq!(lookup(65), Symbol::Literal(65));
assert_eq!(lookup(256), Symbol::EndOfBlock);
assert_eq!(lookup(265), Symbol::Base { base: 11, extra: 1 });
assert_eq!(
lookup(285),
Symbol::Base {
base: 258,
extra: 0
}
);
assert_eq!(lookup(287), Symbol::Invalid);
}
#[test]
fn validation_follows_zlib() {
let mut dist = DecodeTable::new(HuffmanTable::Distance);
assert_eq!(dist.build(&[0, 0]), Ok(()), "no distance codes at all");
assert_eq!(dist.build(&[1]), Ok(()), "a single one-bit code");
assert_eq!(dist.lookup(1).symbol, Symbol::Invalid);
assert_eq!(
dist.build(&[2, 2, 2]),
Err(InflateError::IncompleteCode(HuffmanTable::Distance))
);
assert_eq!(
dist.build(&[1, 1, 1]),
Err(InflateError::OversubscribedCode(HuffmanTable::Distance))
);
let mut code_lengths = DecodeTable::new(HuffmanTable::CodeLength);
assert_eq!(
code_lengths.build(&[1]),
Err(InflateError::IncompleteCode(HuffmanTable::CodeLength))
);
}
}