use pltrs_core::alloc::{self, OutOfMemory};
use super::Output;
use super::codes::{
BL_CODES, Builder, Code, D_CODES, DISTANCE_TREE, END_BLOCK, HEAP_SIZE, L_CODES, LENGTH_TREE,
LITERAL_TREE, LITERALS, Node, STATIC_DTREE, STATIC_LTREE, on_heap,
};
use crate::deflate::tables::{
CODE_LENGTH_ORDER, DIST_BASE, DIST_EXTRA, LENGTH_BASE, LENGTH_EXTRA, dist_index, length_index,
};
const REP_3_6: usize = 16;
const REPZ_3_10: usize = 17;
const REPZ_11_138: usize = 18;
const STORED_BLOCK: u64 = 0;
const STATIC_TREES: u64 = 1;
const DYN_TREES: u64 = 2;
#[derive(Debug)]
pub(super) struct Symbols {
dist: Vec<u16>,
lit: Vec<u8>,
len: usize,
end: usize,
}
impl Symbols {
pub(super) fn capacity(&self) -> usize {
self.end + 1
}
pub(super) fn cleared(mut self) -> Self {
self.len = 0;
self
}
pub(super) fn new(capacity: usize) -> Result<Self, OutOfMemory> {
let mut dist = alloc::try_with_capacity(capacity)?;
dist.resize(capacity, 0);
let mut lit = alloc::try_with_capacity(capacity)?;
lit.resize(capacity, 0);
Ok(Self {
dist,
lit,
len: 0,
end: capacity - 1,
})
}
}
#[derive(Clone, Copy, Debug)]
enum Run {
Each { len: u16, count: u32 },
Repeat { len: u16, count: u32, first: bool },
Zeros { count: u32 },
}
fn runs(tree: &[Node], max_code: usize, mut visit: impl FnMut(Run)) {
let mut prevlen = None;
let mut nextlen = tree[0].len;
let mut count = 0;
let (mut max_count, mut min_count) = if nextlen == 0 { (138, 3) } else { (7, 4) };
for n in 0..=max_code {
let curlen = nextlen;
nextlen = if n == max_code {
u16::MAX
} else {
tree[n + 1].len
};
count += 1;
if count < max_count && curlen == nextlen {
continue;
}
visit(if count < min_count {
Run::Each { len: curlen, count }
} else if curlen != 0 {
Run::Repeat {
len: curlen,
count,
first: prevlen != Some(curlen),
}
} else {
Run::Zeros { count }
});
count = 0;
prevlen = Some(curlen);
(max_count, min_count) = if nextlen == 0 {
(138, 3)
} else if curlen == nextlen {
(6, 3)
} else {
(7, 4)
};
}
}
#[derive(Debug)]
pub(super) struct Trees {
ltree: Box<[Node; HEAP_SIZE]>,
dtree: Box<[Node; 2 * D_CODES + 1]>,
bltree: Box<[Node; 2 * BL_CODES + 1]>,
lcodes: Box<[Code; L_CODES]>,
dcodes: Box<[Code; D_CODES]>,
blcodes: Box<[Code; BL_CODES]>,
builder: Builder,
}
impl Trees {
pub(super) fn new() -> Self {
let mut trees = Self {
ltree: on_heap(Node::default()),
dtree: on_heap(Node::default()),
bltree: on_heap(Node::default()),
lcodes: on_heap(Code::default()),
dcodes: on_heap(Code::default()),
blcodes: on_heap(Code::default()),
builder: Builder::new(),
};
trees.init_block();
trees
}
pub(super) fn cleared(mut self) -> Self {
self.ltree.fill(Node::default());
self.dtree.fill(Node::default());
self.bltree.fill(Node::default());
self.lcodes.fill(Code::default());
self.dcodes.fill(Code::default());
self.blcodes.fill(Code::default());
self.builder.clear();
self.init_block();
self
}
fn init_block(&mut self) {
for node in &mut self.ltree[..L_CODES] {
node.freq = 0;
}
for node in &mut self.dtree[..D_CODES] {
node.freq = 0;
}
for node in &mut self.bltree[..BL_CODES] {
node.freq = 0;
}
self.ltree[END_BLOCK].freq = 1;
self.builder.opt_len = 0;
self.builder.static_len = 0;
}
#[inline]
pub(super) fn tally_lit(&mut self, syms: &mut Symbols, byte: u8) -> bool {
syms.dist[syms.len] = 0;
syms.lit[syms.len] = byte;
syms.len += 1;
self.ltree[usize::from(byte)].freq += 1;
syms.len == syms.end
}
#[inline]
pub(super) fn tally_dist(&mut self, syms: &mut Symbols, dist: u32, len: u32) -> bool {
syms.dist[syms.len] = dist as u16;
syms.lit[syms.len] = len as u8;
syms.len += 1;
self.ltree[length_index(len as usize + 3) + LITERALS + 1].freq += 1;
self.dtree[dist_index(dist as usize)].freq += 1;
syms.len == syms.end
}
pub(super) fn flush_block(
&mut self,
syms: &mut Symbols,
out: &mut Output<'_>,
stored: Option<&[u8]>,
last: bool,
fixed_only: bool,
) {
let mut dynamic = None;
let (mut opt_lenb, static_lenb) = if syms.len == 0 {
(0, 0)
} else {
let l_max_code =
self.builder
.build_tree(&mut self.ltree[..], &mut self.lcodes[..], &LITERAL_TREE);
let d_max_code =
self.builder
.build_tree(&mut self.dtree[..], &mut self.dcodes[..], &DISTANCE_TREE);
let max_blindex = self.build_bl_tree(l_max_code, d_max_code);
dynamic = Some((l_max_code, d_max_code, max_blindex));
(
self.builder.opt_len.wrapping_add(3 + 7) >> 3,
self.builder.static_len.wrapping_add(3 + 7) >> 3,
)
};
if static_lenb <= opt_lenb || fixed_only {
opt_lenb = static_lenb;
}
match (stored, dynamic) {
(Some(bytes), _) if bytes.len() as u64 + 4 <= opt_lenb => {
stored_block(out, bytes, last);
}
(_, Some((l_max_code, d_max_code, max_blindex))) if static_lenb != opt_lenb => {
send_block_header(out, DYN_TREES, last);
self.send_all_trees(out, l_max_code + 1, d_max_code + 1, max_blindex + 1);
compress_block(syms, out, &self.lcodes[..], &self.dcodes[..]);
}
_ => {
send_block_header(out, STATIC_TREES, last);
compress_block(syms, out, &STATIC_LTREE, &STATIC_DTREE);
}
}
self.init_block();
syms.len = 0;
if last {
out.align();
}
}
fn build_bl_tree(&mut self, l_max_code: usize, d_max_code: usize) -> usize {
scan_tree(&mut self.bltree[..], &self.ltree[..], l_max_code);
scan_tree(&mut self.bltree[..], &self.dtree[..], d_max_code);
self.builder
.build_tree(&mut self.bltree[..], &mut self.blcodes[..], &LENGTH_TREE);
let max_blindex = (3..BL_CODES)
.rev()
.find(|&index| self.bltree[CODE_LENGTH_ORDER[index]].len != 0)
.expect("a non-zero length is sent as itself");
self.builder.opt_len = self
.builder
.opt_len
.wrapping_add(3 * (max_blindex as u64 + 1) + 5 + 5 + 4);
max_blindex
}
fn send_all_trees(&self, out: &mut Output<'_>, lcodes: usize, dcodes: usize, blcodes: usize) {
out.send_bits((lcodes - 257) as u64, 5);
out.send_bits((dcodes - 1) as u64, 5);
out.send_bits((blcodes - 4) as u64, 4);
for &symbol in &CODE_LENGTH_ORDER[..blcodes] {
out.send_bits(u64::from(self.bltree[symbol].len), 3);
}
self.send_tree(out, &self.ltree[..], lcodes - 1);
self.send_tree(out, &self.dtree[..], dcodes - 1);
}
fn send_tree(&self, out: &mut Output<'_>, tree: &[Node], max_code: usize) {
let send = |out: &mut Output<'_>, symbol: usize| {
let code = self.blcodes[symbol];
out.send_bits(u64::from(code.code), u32::from(code.len));
};
runs(tree, max_code, |run| match run {
Run::Each { len, count } => {
for _ in 0..count {
send(out, usize::from(len));
}
}
Run::Repeat { len, count, first } => {
let mut count = count;
if first {
send(out, usize::from(len));
count -= 1;
}
send(out, REP_3_6);
out.send_bits(u64::from(count - 3), 2);
}
Run::Zeros { count } if count <= 10 => {
send(out, REPZ_3_10);
out.send_bits(u64::from(count - 3), 3);
}
Run::Zeros { count } => {
send(out, REPZ_11_138);
out.send_bits(u64::from(count - 11), 7);
}
});
}
}
fn scan_tree(bltree: &mut [Node], tree: &[Node], max_code: usize) {
runs(tree, max_code, |run| match run {
Run::Each { len, count } => bltree[usize::from(len)].freq += count,
Run::Repeat { len, first, .. } => {
if first {
bltree[usize::from(len)].freq += 1;
}
bltree[REP_3_6].freq += 1;
}
Run::Zeros { count } if count <= 10 => bltree[REPZ_3_10].freq += 1,
Run::Zeros { .. } => bltree[REPZ_11_138].freq += 1,
});
}
#[inline]
pub(super) fn send_block_header(out: &mut Output<'_>, kind: u64, last: bool) {
out.send_bits(kind << 1 | u64::from(last), 3);
}
pub(super) fn send_fixed_header(out: &mut Output<'_>, last: bool) {
send_block_header(out, STATIC_TREES, last);
}
pub(super) fn send_stored_header(out: &mut Output<'_>, len: u16, last: bool) {
send_block_header(out, STORED_BLOCK, last);
out.align();
out.put_bytes(&len.to_le_bytes());
out.put_bytes(&(!len).to_le_bytes());
}
fn stored_block(out: &mut Output<'_>, bytes: &[u8], last: bool) {
send_stored_header(out, bytes.len() as u16, last);
out.put_bytes(bytes);
}
#[inline]
pub(super) fn send_fixed_literal(out: &mut Output<'_>, byte: u8) {
let code = STATIC_LTREE[usize::from(byte)];
out.send_bits(u64::from(code.code), u32::from(code.len));
}
#[inline]
pub(super) fn send_fixed_match(out: &mut Output<'_>, len: u32, dist: u32) {
send_match(out, &STATIC_LTREE, &STATIC_DTREE, len, dist);
}
pub(super) fn send_fixed_end(out: &mut Output<'_>) {
let code = STATIC_LTREE[END_BLOCK];
out.send_bits(u64::from(code.code), u32::from(code.len));
}
#[inline]
fn send_match(out: &mut Output<'_>, lcodes: &[Code], dcodes: &[Code], len: u32, dist: u32) {
let length = len as usize + 3;
let index = length_index(length);
let code = lcodes[LITERALS + 1 + index];
let mut bits = u64::from(code.code);
let mut count = u32::from(code.len);
bits |= ((length - usize::from(LENGTH_BASE[index])) as u64) << count;
count += u32::from(LENGTH_EXTRA[index]);
let index = dist_index(dist as usize);
let code = dcodes[index];
bits |= u64::from(code.code) << count;
count += u32::from(code.len);
bits |= u64::from(dist - u32::from(DIST_BASE[index])) << count;
count += u32::from(DIST_EXTRA[index]);
out.send_bits(bits, count);
}
fn compress_block(syms: &Symbols, out: &mut Output<'_>, lcodes: &[Code], dcodes: &[Code]) {
for (&dist, &lit) in syms.dist[..syms.len].iter().zip(&syms.lit[..syms.len]) {
if dist == 0 {
let code = lcodes[usize::from(lit)];
out.send_bits(u64::from(code.code), u32::from(code.len));
} else {
send_match(out, lcodes, dcodes, u32::from(lit), u32::from(dist));
}
}
let code = lcodes[END_BLOCK];
out.send_bits(u64::from(code.code), u32::from(code.len));
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn runs_group_lengths_as_zlib_does() {
let lengths = [0, 0, 0, 0, 5, 5, 5, 5, 5, 5, 5, 5, 3, 0, 0];
let mut tree = [Node::default(); 16];
for (node, &len) in tree.iter_mut().zip(&lengths) {
node.len = len;
}
let mut seen = Vec::new();
runs(&tree, lengths.len() - 1, |run| {
seen.push(format!("{run:?}"));
});
assert_eq!(
seen,
[
"Zeros { count: 4 }",
"Repeat { len: 5, count: 7, first: true }",
"Each { len: 5, count: 1 }",
"Each { len: 3, count: 1 }",
"Each { len: 0, count: 2 }",
]
);
}
}