use crate::deflate::bit_writer::BitWriter;
use crate::deflate::code_lengths::run_length_ops;
use crate::deflate::huffman::HuffmanCode;
use crate::webp::lossless::format::{CODE_LENGTH_CODES, CODE_LENGTH_ORDER};
const MAX_BITS: usize = 15;
const MAX_CODE_LENGTH_BITS: usize = 7;
#[derive(Clone, Debug)]
pub(super) enum PrefixCode {
Single(usize),
Huffman(HuffmanCode),
}
impl PrefixCode {
pub(super) fn for_histogram(histogram: &[u32]) -> Self {
let mut used = histogram
.iter()
.enumerate()
.filter(|&(_, &count)| count > 0);
match (used.next(), used.next()) {
(None, _) => Self::Single(0),
(Some((symbol, _)), None) => Self::Single(symbol),
_ => Self::Huffman(HuffmanCode::optimal(histogram, MAX_BITS)),
}
}
pub(super) fn write(&self, writer: &mut BitWriter<'_>, symbol: usize) {
if let Self::Huffman(code) = self {
writer.write_bits(
u32::from(code.codes[symbol]),
u32::from(code.lengths[symbol]),
);
}
}
pub(super) fn write_description(&self, writer: &mut BitWriter<'_>, alphabet: usize) {
match self {
Self::Single(symbol) if *symbol < 256 => write_simple(writer, &[*symbol]),
Self::Single(symbol) => {
let mut lengths = vec![0u8; alphabet];
lengths[*symbol] = 1;
write_lengths(writer, &lengths);
}
Self::Huffman(code) => {
let used: Vec<usize> = (0..alphabet).filter(|&s| code.lengths[s] > 0).collect();
if used.len() == 2 && used[1] < 256 {
write_simple(writer, &used);
} else {
write_lengths(writer, &code.lengths[..alphabet]);
}
}
}
}
}
fn write_simple(writer: &mut BitWriter<'_>, symbols: &[usize]) {
writer.write_bits(1, 1);
writer.write_bits(symbols.len() as u32 - 1, 1);
let first = symbols[0] as u32;
if first < 2 {
writer.write_bits(0, 1);
writer.write_bits(first, 1);
} else {
writer.write_bits(1, 1);
writer.write_bits(first, 8);
}
if let Some(&second) = symbols.get(1) {
writer.write_bits(second as u32, 8);
}
}
fn write_lengths(writer: &mut BitWriter<'_>, lengths: &[u8]) {
let ops = run_length_ops(lengths);
let mut frequencies = [0u32; CODE_LENGTH_CODES];
for op in &ops {
frequencies[usize::from(op.symbol)] += 1;
}
let code = HuffmanCode::optimal(&frequencies, MAX_CODE_LENGTH_BITS);
let stored = CODE_LENGTH_ORDER
.iter()
.rposition(|&symbol| code.lengths[symbol] != 0)
.map_or(4, |last| (last + 1).max(4));
writer.write_bits(0, 1);
writer.write_bits(stored as u32 - 4, 4);
for &symbol in &CODE_LENGTH_ORDER[..stored] {
writer.write_bits(u32::from(code.lengths[symbol]), 3);
}
writer.write_bits(0, 1);
for op in ops {
let symbol = usize::from(op.symbol);
writer.write_bits(
u32::from(code.codes[symbol]),
u32::from(code.lengths[symbol]),
);
writer.write_bits(u32::from(op.extra), op.extra_bits());
}
}