use alloc::vec::Vec;
use crate::utils::security::{MAX_MATCH_LEN, MAX_OFFSET, MIN_MATCH};
use crate::utils::simd;
const HASH_LOG: u32 = 17;
const HASH_SIZE: usize = 1 << HASH_LOG;
const CHAIN_LOG: u32 = 15;
const SEARCHES: usize = 64;
#[inline]
fn lit_cost(n: u32) -> u32 {
n.saturating_mul(8).saturating_add(2)
}
#[inline]
fn match_cost(ml: u32, offset: u32) -> u32 {
let ml_bits = if ml < 16 {
4
} else if ml < 256 {
12
} else {
20
};
let off_bits = if offset < 128 {
8
} else if offset < 16384 {
16
} else {
24
};
8 + ml_bits + off_bits
}
#[inline]
fn hash4(v: u32) -> usize {
(v.wrapping_mul(0x9E37_79B1) >> (32 - HASH_LOG)) as usize
}
#[inline]
fn read_u32(data: &[u8], pos: usize) -> u32 {
u32::from_le_bytes(data[pos..pos + 4].try_into().unwrap())
}
pub type OptSeq = (u32, u32, u32);
pub fn parse(src: &[u8]) -> (Vec<u8>, Vec<OptSeq>) {
let n = src.len();
if n == 0 {
return (Vec::new(), Vec::new());
}
if n < MIN_MATCH + 1 {
return (src.to_vec(), vec![(n as u32, 0, 0)]);
}
let mut hash = vec![0u32; HASH_SIZE];
let mut chain = vec![0u32; 1 << CHAIN_LOG];
let chain_mask = (1u32 << CHAIN_LOG) - 1;
let window = MAX_OFFSET.min(n);
let mut cost = vec![u32::MAX / 4; n + 1];
let mut prev = vec![0usize; n + 1];
let mut arr_ml = vec![0u32; n + 1];
let mut arr_off = vec![0u32; n + 1];
cost[0] = 0;
for i in 0..n {
if cost[i] >= u32::MAX / 8 {
if i + 4 <= n {
let h = hash4(read_u32(src, i));
let old = hash[h];
hash[h] = (i as u32).wrapping_add(1);
chain[(i as u32 & chain_mask) as usize] = old;
}
continue;
}
let cl = cost[i].saturating_add(lit_cost(1));
if cl < cost[i + 1] {
cost[i + 1] = cl;
prev[i + 1] = i;
arr_ml[i + 1] = 0;
arr_off[i + 1] = 0;
}
if i + MIN_MATCH <= n {
let v = read_u32(src, i);
let h = hash4(v);
let mut cand = hash[h];
let mut probes = 0usize;
while cand != 0 && probes < SEARCHES {
probes += 1;
let cpos = (cand as usize).wrapping_sub(1);
if cpos >= i {
break;
}
let off = i - cpos;
if off == 0 || off > window {
break;
}
simd::prefetch_read(
chain
.as_ptr()
.wrapping_add((cpos as u32 & chain_mask) as usize)
.cast::<u8>(),
);
if read_u32(src, cpos) == v {
let max_ml = (n - i).min(MAX_MATCH_LEN);
let ml = MIN_MATCH
+ simd::match_len(
&src[cpos + MIN_MATCH..],
&src[i + MIN_MATCH..],
max_ml.saturating_sub(MIN_MATCH),
);
if ml >= MIN_MATCH {
let j = i + ml;
let cm = cost[i].saturating_add(match_cost(ml as u32, off as u32));
if cm < cost[j] {
cost[j] = cm;
prev[j] = i;
arr_ml[j] = ml as u32;
arr_off[j] = off as u32;
}
}
}
cand = chain[(cpos as u32 & chain_mask) as usize];
}
let old = hash[h];
hash[h] = (i as u32).wrapping_add(1);
chain[(i as u32 & chain_mask) as usize] = old;
} else if i + 4 <= n {
let h = hash4(read_u32(src, i));
let old = hash[h];
hash[h] = (i as u32).wrapping_add(1);
chain[(i as u32 & chain_mask) as usize] = old;
}
}
let mut nodes = Vec::new();
let mut i = n;
while i > 0 {
let p = prev[i];
nodes.push((p, i, arr_ml[i], arr_off[i]));
i = p;
}
nodes.reverse();
let mut literals = Vec::new();
let mut seqs: Vec<OptSeq> = Vec::new();
let mut pending_lits = 0u32;
for &(start, end, ml, off) in &nodes {
if ml == 0 {
pending_lits += (end - start) as u32;
literals.extend_from_slice(&src[start..end]);
} else {
seqs.push((pending_lits, ml, off));
pending_lits = 0;
debug_assert_eq!(end - start, ml as usize);
}
}
if pending_lits > 0 || seqs.is_empty() {
seqs.push((pending_lits, 0, 0));
}
(literals, seqs)
}
pub fn should_use(level: u8) -> bool {
level >= 15
}
pub fn execute(lits: &[u8], seqs: &[OptSeq]) -> Vec<u8> {
let mut out = Vec::new();
let mut li = 0usize;
for &(ll, ml, off) in seqs {
out.extend_from_slice(&lits[li..li + ll as usize]);
li += ll as usize;
if ml > 0 {
let start = out.len() - off as usize;
for k in 0..ml as usize {
let b = out[start + k];
out.push(b);
}
}
}
out
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn opt_rebuilds_source() {
let src = b"OPTIMAL PARSE TEST DATA OPTIMAL PARSE ".repeat(100);
let (lits, seqs) = parse(&src);
let sum_ll: usize = seqs.iter().map(|s| s.0 as usize).sum();
assert_eq!(sum_ll, lits.len());
assert_eq!(execute(&lits, &seqs), src.as_slice());
}
#[test]
fn opt_beats_all_literals_on_rep() {
let src = b"ABCDEFGH".repeat(200);
let (lits, seqs) = parse(&src);
let has_match = seqs.iter().any(|s| s.1 >= MIN_MATCH as u32);
assert!(has_match, "expected matches on repetitive data");
assert!(lits.len() < src.len());
assert_eq!(execute(&lits, &seqs), src.as_slice());
}
}