use crate::utils::security::{MAX_MATCH_LEN, MAX_OFFSET, MIN_MATCH};
use crate::utils::simd;
use crate::Result;
const HASH_LOG: u32 = 12;
const HASH_SIZE: usize = 1 << HASH_LOG;
const ACCEL: u32 = 6;
#[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 fn looks_incompressible(src: &[u8]) -> bool {
if src.len() < 4096 {
return false;
}
let step = (src.len() / 256).max(16);
let mut table = [0u32; 256]; let mut hits = 0u32;
let mut samples = 0u32;
let mut pos = 0usize;
while pos + 4 <= src.len() && samples < 256 {
let h = (hash4(read_u32(src, pos)) & 0xFF) as usize;
let tag = read_u32(src, pos);
if table[h] == tag.wrapping_add(1) {
hits += 1;
} else {
table[h] = tag.wrapping_add(1);
}
samples += 1;
pos += step;
}
samples > 64 && hits * 20 < samples
}
pub fn compress(src: &[u8]) -> Result<Vec<u8>> {
let mut out = Vec::with_capacity(src.len() / 2 + 64);
compress_into(src, &mut out, None)?;
Ok(out)
}
pub fn compress_into(src: &[u8], out: &mut Vec<u8>, dict: Option<&[u8]>) -> Result<()> {
if src.is_empty() {
out.push(0);
out.extend_from_slice(&0u32.to_le_bytes());
out.extend_from_slice(&0u32.to_le_bytes());
return Ok(());
}
let dict = dict.unwrap_or(&[]);
let dict = if dict.len() > MAX_OFFSET {
&dict[dict.len() - MAX_OFFSET..]
} else {
dict
};
let dlen = dict.len();
let mut combined = Vec::with_capacity(dlen + src.len());
combined.extend_from_slice(dict);
combined.extend_from_slice(src);
let base = dlen;
let end = combined.len();
let mut table = [0u32; HASH_SIZE];
if dlen >= MIN_MATCH {
let step = if dlen > 8192 { 4 } else { 1 };
let mut p = 0usize;
while p + 4 <= dlen {
table[hash4(read_u32(&combined, p))] = (p as u32).wrapping_add(1);
p += step;
}
}
let mut literals = Vec::with_capacity(src.len() / 2);
let mut seqs: Vec<(u32, u32, u32)> = Vec::new();
let mut anchor = base;
let mut ip = base;
let limit = end.saturating_sub(MIN_MATCH + 1);
let mut miss = 0u32;
let window = (64 * 1024).min(MAX_OFFSET).min(end.max(1));
while ip < limit {
let v = read_u32(&combined, ip);
let h = hash4(v);
let cand = table[h];
table[h] = (ip as u32).wrapping_add(1);
let mut matched = false;
if cand != 0 {
let cpos = (cand as usize).wrapping_sub(1);
if cpos < ip {
let off = ip - cpos;
if off > 0 && off <= window && read_u32(&combined, cpos) == v {
let max_ml = (end - ip).min(MAX_MATCH_LEN);
let ml = MIN_MATCH
+ simd::match_len(
&combined[cpos + MIN_MATCH..],
&combined[ip + MIN_MATCH..],
max_ml.saturating_sub(MIN_MATCH),
);
if ml >= MIN_MATCH && ip + ml <= end {
let lit_len = (ip - anchor) as u32;
literals.extend_from_slice(&combined[anchor..ip]);
seqs.push((lit_len, ml as u32, off as u32));
let mut p = ip + 2;
let mend = ip + ml;
while p < mend && p + 4 <= end {
table[hash4(read_u32(&combined, p))] = (p as u32).wrapping_add(1);
p += 2;
}
ip = mend;
anchor = mend;
miss = 0;
matched = true;
}
}
}
}
if !matched {
miss = miss.saturating_add(1);
let step = if miss > 16 {
(1 + ((miss as usize - 16) >> ACCEL as usize)).min(64)
} else {
1
};
ip += step;
}
}
if anchor < end {
literals.extend_from_slice(&combined[anchor..end]);
seqs.push(((end - anchor) as u32, 0, 0));
} else if seqs.is_empty() {
literals.extend_from_slice(src);
seqs.push((src.len() as u32, 0, 0));
}
const FLAG_REP: u8 = 4;
let mut reps = [1u32, 4u32, 8u32];
out.push(FLAG_REP);
out.extend_from_slice(&(literals.len() as u32).to_le_bytes());
out.extend_from_slice(&(seqs.len() as u32).to_le_bytes());
out.extend_from_slice(&literals);
for &(ll, ml, off) in &seqs {
put_varint(out, ll);
put_varint(out, ml);
if ml > 0 {
let code = encode_off(off, &mut reps);
put_varint(out, code);
}
}
Ok(())
}
#[inline]
fn put_varint(out: &mut Vec<u8>, mut v: u32) {
while v >= 0x80 {
out.push((v as u8) | 0x80);
v >>= 7;
}
out.push(v as u8);
}
#[inline]
fn encode_off(offset: u32, reps: &mut [u32; 3]) -> u32 {
if offset == reps[0] {
return 0;
}
if offset == reps[1] {
reps[1] = reps[0];
reps[0] = offset;
return 1;
}
if offset == reps[2] {
reps[2] = reps[1];
reps[1] = reps[0];
reps[0] = offset;
return 2;
}
let code = offset.saturating_add(3);
reps[2] = reps[1];
reps[1] = reps[0];
reps[0] = offset;
code
}
pub fn should_use_turbo(level: u8) -> bool {
level <= 2
}
#[cfg(test)]
mod tests {
use super::*;
use crate::algorithms::zex_native;
#[test]
fn turbo_roundtrip() {
let src = b"turbo turbo turbo speed path test!!!! ".repeat(100);
let c = compress(&src).unwrap();
let d = zex_native::decompress(&c, src.len()).unwrap();
assert_eq!(d, src.as_slice());
}
#[test]
fn incompressible_heuristic_randomish() {
let mut src = Vec::with_capacity(8192);
let mut x = 0xDEAD_BEEFu32;
for _ in 0..8192 {
x = x.wrapping_mul(1664525).wrapping_add(1013904223);
src.push((x >> 24) as u8);
}
assert!(looks_incompressible(&src));
let zeros = vec![0u8; 8192];
assert!(!looks_incompressible(&zeros));
}
#[test]
fn turbo_empty() {
let c = compress(b"").unwrap();
let d = zex_native::decompress(&c, 0).unwrap();
assert!(d.is_empty());
}
}