use alloc::vec::Vec;
use crate::Result;
use crate::utils::security::{MAX_MATCH_LEN, MAX_OFFSET, MIN_MATCH};
use crate::utils::simd;
const HASH_LOG_L1: u32 = 12;
const HASH_LOG_L2: u32 = 14;
#[inline]
fn hash4(v: u32, hash_log: 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), 12) & 0xFF;
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<()> {
compress_into_level(src, out, dict, 1)
}
pub fn compress_into_level(
src: &[u8],
out: &mut Vec<u8>,
dict: Option<&[u8]>,
level: 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 level = level.clamp(1, 2);
let hash_log = if level >= 2 { HASH_LOG_L2 } else { HASH_LOG_L1 };
let hash_size = 1usize << hash_log;
let accel: u32 = if level >= 2 { 4 } else { 6 };
let max_skip: usize = if level >= 2 { 32 } else { 64 };
let fill_step: usize = if level >= 2 { 1 } else { 2 };
let dict = dict.unwrap_or(&[]);
let dict = if dict.len() > MAX_OFFSET {
&dict[dict.len() - MAX_OFFSET..]
} else {
dict
};
let dlen = dict.len();
let cfg = TurboCfg {
hash_log,
hash_size,
accel,
max_skip,
fill_step,
};
if dlen == 0 {
return compress_body(src, 0, src, out, &cfg);
}
let mut combined = Vec::with_capacity(dlen + src.len());
combined.extend_from_slice(dict);
combined.extend_from_slice(src);
compress_body(&combined, dlen, src, out, &cfg)
}
struct TurboCfg {
hash_log: u32,
hash_size: usize,
accel: u32,
max_skip: usize,
fill_step: usize,
}
fn compress_body(
data: &[u8],
base: usize,
src_only: &[u8],
out: &mut Vec<u8>,
cfg: &TurboCfg,
) -> Result<()> {
let end = data.len();
let mut table = vec![0u32; cfg.hash_size];
if base >= MIN_MATCH {
let step = if base > 8192 { 4 } else { 1 };
let mut p = 0usize;
while p + 4 <= base {
table[hash4(read_u32(data, p), cfg.hash_log)] = (p as u32).wrapping_add(1);
p += step;
}
}
let mut literals = Vec::with_capacity(src_only.len() / 4 + 16);
let mut seqs: Vec<(u32, u32, u32)> = Vec::with_capacity(src_only.len() / 32 + 4);
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(data, ip);
let h = hash4(v, cfg.hash_log);
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(data, cpos) == v {
let max_ml = (end - ip).min(MAX_MATCH_LEN);
let ml = MIN_MATCH
+ simd::match_len(
&data[cpos + MIN_MATCH..],
&data[ip + MIN_MATCH..],
max_ml.saturating_sub(MIN_MATCH),
);
if ml >= MIN_MATCH && ip + ml <= end && !(ml == MIN_MATCH && off > 4096) {
let lit_len = (ip - anchor) as u32;
literals.extend_from_slice(&data[anchor..ip]);
seqs.push((lit_len, ml as u32, off as u32));
let mend = ip + ml;
let mut p = ip + cfg.fill_step;
while p < mend && p + 4 <= end {
table[hash4(read_u32(data, p), cfg.hash_log)] =
(p as u32).wrapping_add(1);
p += cfg.fill_step;
}
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) >> cfg.accel as usize)).min(cfg.max_skip)
} else {
1
};
ip += step;
}
}
if anchor < end {
literals.extend_from_slice(&data[anchor..end]);
seqs.push(((end - anchor) as u32, 0, 0));
} else if seqs.is_empty() {
literals.extend_from_slice(src_only);
seqs.push((src_only.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 turbo_level2_roundtrip() {
let src = b"level two denser hash table turbo path ".repeat(200);
let mut c = Vec::new();
compress_into_level(&src, &mut c, None, 2).unwrap();
let d = zex_native::decompress(&c, src.len()).unwrap();
assert_eq!(d, src.as_slice());
}
#[test]
fn turbo_dict_roundtrip() {
let dict = b"SHARED-PREFIX-AAAAAAAAAAAAAAAA";
let src = b"SHARED-PREFIX-AAAAAAAAAAAAAAAA and some tail data";
let mut c = Vec::new();
compress_into_level(src, &mut c, Some(dict), 2).unwrap();
let d = zex_native::decompress_with_history(&c, src.len(), Some(dict)).unwrap();
assert_eq!(d, src);
}
#[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());
}
}