use alloc::vec;
use alloc::vec::Vec;
use super::block;
use super::matcher::{HashChain, History, Match, Params};
use super::optimal::{self, Prices};
const MAGIC: u32 = 0xfd2f_b528;
const MAX_WINDOW_LOG: u32 = 23;
const MAX_PARSED: usize = u32::MAX as usize;
const PASSES: usize = 4;
const MIN_SEGMENT: usize = 1 << 20;
const SEGMENT_MEMORY: usize = 384 << 20;
pub(super) fn encode(input: &[u8]) -> Vec<u8> {
let len = input.len();
let mut out = Vec::with_capacity(len / 3 + 32);
out.extend_from_slice(&MAGIC.to_le_bytes());
let window = write_header(&mut out, len);
if len == 0 {
out.extend_from_slice(&[0x01, 0x00, 0x00]);
return out;
}
let params = Params::for_input(len, window);
let segments = segments(len, window, ¶ms);
for body in crate::parallel::map(&segments, |&(start, stop)| {
encode_segment(input, start, stop, window, ¶ms, stop == len)
}) {
out.extend_from_slice(&body);
}
out
}
fn segments(len: usize, window: usize, params: &Params) -> Vec<(usize, usize)> {
let per_segment = HashChain::footprint(len, window, params.hash_bits);
let affordable = (SEGMENT_MEMORY / per_segment.max(1)).max(1);
let wanted = (len / MIN_SEGMENT).clamp(1, affordable);
let blocks = len.div_ceil(block::MAX_BLOCK);
let per = blocks.div_ceil(wanted);
(0..blocks)
.step_by(per)
.map(|first| {
let start = first * block::MAX_BLOCK;
(start, (start + per * block::MAX_BLOCK).min(len))
})
.collect()
}
fn encode_segment(
input: &[u8],
start: usize,
stop: usize,
window: usize,
params: &Params,
tail: bool,
) -> Vec<u8> {
let len = input.len();
let mut out = Vec::with_capacity((stop - start) / 3 + 16);
let mut chain = HashChain::new(len, window, params.hash_bits);
chain.start_at(start.saturating_sub(window));
chain.fill_to(input, start);
let mut history = History::fresh();
let mut at = start;
while at < stop {
let end = (at + block::MAX_BLOCK).min(stop);
let parses = if len <= MAX_PARSED {
parse_block(
input,
at,
end,
&mut chain,
params,
window - 1,
history.offsets(),
)
} else {
vec![Vec::new()]
};
block::write_one(
&mut out,
input,
at,
end,
&parses,
&mut history,
tail && end == stop,
);
at = end;
}
out
}
fn parse_block(
input: &[u8],
start: usize,
end: usize,
chain: &mut HashChain,
params: &Params,
max_offset: usize,
repeats: [usize; 3],
) -> Vec<Vec<Match>> {
let candidates = optimal::collect(input, start, end, chain, params, max_offset);
let block = &input[start..end];
let mut prices = Prices::seed(block);
let mut parses = Vec::with_capacity(PASSES);
for pass in 0..PASSES {
let parse = optimal::parse(input, start, end, &candidates, repeats, &prices);
if pass + 1 < PASSES {
prices = Prices::fit(block, &parse, repeats);
}
parses.push(parse);
}
parses
}
fn write_header(out: &mut Vec<u8>, len: usize) -> usize {
if len < 256 {
out.push(0x20);
out.push(len as u8);
return len.max(1);
}
let log = ceil_log2(len).min(MAX_WINDOW_LOG);
let descriptor = if len <= 65791 {
0x40
} else if len <= u32::MAX as usize {
0x80
} else {
0xc0
};
out.push(descriptor);
out.push(((log - 10) << 3) as u8);
if len <= 65791 {
out.extend_from_slice(&((len - 256) as u16).to_le_bytes());
} else if len <= u32::MAX as usize {
out.extend_from_slice(&(len as u32).to_le_bytes());
} else {
out.extend_from_slice(&(len as u64).to_le_bytes());
}
1usize << log
}
fn ceil_log2(n: usize) -> u32 {
(usize::BITS - (n - 1).leading_zeros()).max(10)
}