use alloc::vec;
use alloc::vec::Vec;
use super::bitstream::BitWriter;
use super::weights;
const MAX_BITS: u32 = 11;
const MAX_DIRECT_WEIGHTS: usize = 128;
const MIN_LITERALS: usize = 256;
pub(super) fn compress(literals: &[u8]) -> Option<Vec<u8>> {
if literals.len() < MIN_LITERALS {
return None;
}
let mut counts = [0u32; 256];
for &byte in literals {
counts[byte as usize] += 1;
}
let last = counts.iter().rposition(|&c| c > 0)?;
if counts.iter().filter(|&&c| c > 0).count() < 2 {
return None;
}
let lengths = code_lengths(&counts);
let codes = assign_codes(&lengths);
let max_bits = u32::from(*lengths.iter().max()?);
let series: Vec<u8> = lengths[..last]
.iter()
.map(|&len| weight(len, max_bits))
.collect();
let mut out = Vec::with_capacity(literals.len() / 2 + last / 2 + 8);
write_tree(&mut out, &series)?;
let quarter = literals.len().div_ceil(4);
let jump_table = out.len();
out.extend_from_slice(&[0u8; 6]);
let mut sizes = [0usize; 3];
for (i, part) in literals.chunks(quarter).enumerate() {
let before = out.len();
write_stream(&mut out, part, &lengths, &codes);
if i < 3 {
sizes[i] = out.len() - before;
}
}
for (i, size) in sizes.iter().enumerate() {
out[jump_table + i * 2..jump_table + i * 2 + 2]
.copy_from_slice(&(u16::try_from(*size).ok()?).to_le_bytes());
}
Some(out)
}
fn code_lengths(counts: &[u32; 256]) -> [u8; 256] {
let mut freqs = *counts;
loop {
let lengths = huffman(&freqs);
if lengths.iter().all(|&len| u32::from(len) <= MAX_BITS) {
return lengths;
}
for freq in &mut freqs {
*freq = (*freq).div_ceil(2);
}
}
}
fn huffman(freqs: &[u32; 256]) -> [u8; 256] {
let mut leaves: Vec<(u64, usize)> = (0..256)
.filter(|&s| freqs[s] > 0)
.map(|s| (u64::from(freqs[s]), s))
.collect();
leaves.sort_unstable();
let leaf_count = leaves.len();
let mut lengths = [0u8; 256];
if leaf_count < 2 {
if let Some(&(_, symbol)) = leaves.first() {
lengths[symbol] = 1;
}
return lengths;
}
let mut internal_freq: Vec<u64> = Vec::with_capacity(leaf_count - 1);
let mut children: Vec<(usize, usize)> = Vec::with_capacity(leaf_count - 1);
let mut next_leaf = 0usize;
let mut next_internal = 0usize;
let mut picked = [(0u64, 0usize); 2];
while (leaf_count - next_leaf) + (internal_freq.len() - next_internal) > 1 {
for slot in &mut picked {
let leaf = leaves.get(next_leaf).map(|&(freq, _)| freq);
let internal = internal_freq.get(next_internal).copied();
let take_internal = match (leaf, internal) {
(Some(l), Some(i)) => i < l,
(None, Some(_)) => true,
_ => false,
};
*slot = if take_internal {
next_internal += 1;
(internal.unwrap_or_default(), leaf_count + next_internal - 1)
} else {
next_leaf += 1;
(leaf.unwrap_or_default(), next_leaf - 1)
};
}
internal_freq.push(picked[0].0 + picked[1].0);
children.push((picked[0].1, picked[1].1));
}
let mut depth = vec![0u32; leaf_count + children.len()];
for (index, &(left, right)) in children.iter().enumerate().rev() {
let parent = depth[leaf_count + index] + 1;
depth[left] = parent;
depth[right] = parent;
}
for (index, &(_, symbol)) in leaves.iter().enumerate() {
lengths[symbol] = depth[index] as u8;
}
lengths
}
fn assign_codes(lengths: &[u8; 256]) -> [u16; 256] {
let mut codes = [0u16; 256];
let mut code = 0u32;
for bits in (1..=MAX_BITS as u8).rev() {
for (symbol, &len) in lengths.iter().enumerate() {
if len == bits {
codes[symbol] = code as u16;
code += 1;
}
}
code >>= 1;
}
codes
}
fn write_tree(out: &mut Vec<u8>, series: &[u8]) -> Option<()> {
let direct = (series.len() <= MAX_DIRECT_WEIGHTS).then(|| 1 + series.len().div_ceil(2));
let coded = weights::compress(series);
match (direct, coded) {
(Some(size), Some(body)) if size <= body.len() + 1 => write_direct(out, series),
(_, Some(body)) => {
out.push(body.len() as u8);
out.extend_from_slice(&body);
}
(Some(_), None) => write_direct(out, series),
(None, None) => return None,
}
Some(())
}
fn write_direct(out: &mut Vec<u8>, series: &[u8]) {
out.push((127 + series.len()) as u8);
for pair in series.chunks(2) {
out.push(pair[0] << 4 | pair.get(1).copied().unwrap_or(0));
}
}
fn weight(len: u8, max_bits: u32) -> u8 {
if len == 0 {
0
} else {
(max_bits + 1) as u8 - len
}
}
fn write_stream(out: &mut Vec<u8>, part: &[u8], lengths: &[u8; 256], codes: &[u16; 256]) {
let mut bw = BitWriter::new();
for &byte in part.iter().rev() {
bw.push(
u32::from(codes[byte as usize]),
u32::from(lengths[byte as usize]),
);
}
out.extend_from_slice(&bw.finish());
}