use alloc::vec::Vec;
use super::huffman;
use super::matcher::{History, Match};
use super::sequences::{self, Coded};
pub(super) const MAX_BLOCK: usize = 128 * 1024;
const RAW: u8 = 0;
const RLE: u8 = 1;
const COMPRESSED: u8 = 2;
const RAW_LITERALS: u8 = 0;
const RLE_LITERALS: u8 = 1;
const COMPRESSED_LITERALS: u8 = 2;
pub(super) fn write_one(
out: &mut Vec<u8>,
input: &[u8],
start: usize,
end: usize,
parses: &[Vec<Match>],
history: &mut History,
last: bool,
) {
let raw = &input[start..end];
if !raw.is_empty() && raw.iter().all(|&b| b == raw[0]) {
write_header(out, raw.len(), RLE, last);
out.push(raw[0]);
return;
}
let mut best: Option<(Vec<u8>, History)> = None;
for parse in parses {
let mut trial = *history;
let body = compressed_body(input, start, end, parse, &mut trial);
if best
.as_ref()
.is_none_or(|(kept, _)| body.len() < kept.len())
{
best = Some((body, trial));
}
}
match best {
Some((body, trial)) if body.len() < raw.len() => {
write_header(out, body.len(), COMPRESSED, last);
out.extend_from_slice(&body);
*history = trial;
}
_ => {
write_header(out, raw.len(), RAW, last);
out.extend_from_slice(raw);
}
}
}
fn write_header(out: &mut Vec<u8>, size: usize, kind: u8, last: bool) {
let word = (size as u32) << 3 | u32::from(kind) << 1 | u32::from(last);
out.extend_from_slice(&word.to_le_bytes()[..3]);
}
fn compressed_body(
input: &[u8],
start: usize,
end: usize,
parse: &[Match],
history: &mut History,
) -> Vec<u8> {
let mut literals = Vec::new();
let mut coded = Vec::with_capacity(parse.len());
let mut at = start;
for seq in parse {
literals.extend_from_slice(&input[at..at + seq.literal_len]);
at += seq.literal_len + seq.match_len;
let offset = history.encode(seq.offset, seq.literal_len);
coded.push(Coded::new(
seq.literal_len as u32,
seq.match_len as u32,
offset,
));
}
literals.extend_from_slice(&input[at..end]);
let mut body = Vec::with_capacity(literals.len() + coded.len() * 4 + 8);
write_literals(&mut body, &literals);
sequences::write_section(&mut body, &coded);
body
}
fn write_literals(out: &mut Vec<u8>, literals: &[u8]) {
if !literals.is_empty() && literals.iter().all(|&b| b == literals[0]) {
write_literals_header(out, RLE_LITERALS, literals.len(), None);
out.push(literals[0]);
return;
}
if let Some(content) = huffman::compress(literals) {
let coded = header_len(literals.len(), Some(content.len())) + content.len();
if coded < header_len(literals.len(), None) + literals.len() {
write_literals_header(
out,
COMPRESSED_LITERALS,
literals.len(),
Some(content.len()),
);
out.extend_from_slice(&content);
return;
}
}
write_literals_header(out, RAW_LITERALS, literals.len(), None);
out.extend_from_slice(literals);
}
fn header_shape(regenerated: usize, compressed: Option<usize>) -> (u8, u32, u32, usize) {
match compressed {
None if regenerated < 32 => (0, 1, 5, 1),
None if regenerated < 4096 => (1, 2, 12, 2),
None => (3, 2, 20, 3),
Some(size) if regenerated < 1024 && size < 1024 => (1, 2, 10, 3),
Some(size) if regenerated < 16384 && size < 16384 => (2, 2, 14, 4),
_ => (3, 2, 18, 5),
}
}
fn header_len(regenerated: usize, compressed: Option<usize>) -> usize {
header_shape(regenerated, compressed).3
}
fn write_literals_header(
out: &mut Vec<u8>,
kind: u8,
regenerated: usize,
compressed: Option<usize>,
) {
let (format, format_bits, size_bits, bytes) = header_shape(regenerated, compressed);
let mut word =
u64::from(kind) | u64::from(format) << 2 | (regenerated as u64) << (2 + format_bits);
if let Some(size) = compressed {
word |= (size as u64) << (2 + format_bits + size_bits);
}
out.extend_from_slice(&word.to_le_bytes()[..bytes]);
}