use alloc::vec::Vec;
use crate::format::block::BlockType;
use crate::utils::bitstream::{BitReader, BitWriter};
use crate::utils::entropy::{build_encoder, decoder_from_lengths};
use crate::utils::fse::{
decode_ll, decode_ml, decode_off_log2, decode_u32_array_auto, encode_ll, encode_ml,
encode_off_log2, encode_u32_array_compact,
};
use crate::utils::security::{
MAX_MATCH_LEN, MAX_OFFSET, MIN_MATCH, check_block_sizes, check_match_with_history,
};
use crate::utils::simd::{self, copy_match_with_history};
use crate::{Error, Result};
#[derive(Clone, Copy, Debug)]
struct LevelParams {
level: u8,
hash_log: u32,
chain_log: u32,
searches: u32,
accel: u32,
window: usize,
entropy: bool,
lazy: bool,
dual_hash: bool,
min_match_accept: usize,
good_enough: usize,
}
fn params_for_level(level: u8) -> LevelParams {
let level = level.clamp(1, 22);
let mut p = match level {
1 => LevelParams {
level,
hash_log: 12,
chain_log: 0,
searches: 1,
accel: 6,
window: 64 * 1024,
entropy: false,
lazy: false,
dual_hash: false,
min_match_accept: MIN_MATCH,
good_enough: 32,
},
2 => LevelParams {
level,
hash_log: 13,
chain_log: 0,
searches: 1,
accel: 4,
window: 64 * 1024,
entropy: false,
lazy: false,
dual_hash: false,
min_match_accept: MIN_MATCH,
good_enough: 48,
},
3 | 4 => LevelParams {
level,
hash_log: 14,
chain_log: 12,
searches: 4,
accel: 3,
window: 128 * 1024,
entropy: false,
lazy: true,
dual_hash: false,
min_match_accept: MIN_MATCH,
good_enough: 64,
},
5 | 6 => LevelParams {
level,
hash_log: 15,
chain_log: 13,
searches: 12,
accel: 2,
window: 256 * 1024,
entropy: false,
lazy: true,
dual_hash: true,
min_match_accept: MIN_MATCH,
good_enough: 96,
},
7..=9 => LevelParams {
level,
hash_log: 16,
chain_log: 14,
searches: 32,
accel: 1,
window: 512 * 1024,
entropy: true,
lazy: true,
dual_hash: true,
min_match_accept: MIN_MATCH,
good_enough: 128,
},
10..=12 => LevelParams {
level,
hash_log: 17,
chain_log: 15,
searches: 64,
accel: 1,
window: 1024 * 1024,
entropy: true,
lazy: true,
dual_hash: true,
min_match_accept: MIN_MATCH,
good_enough: 192,
},
13..=16 => LevelParams {
level,
hash_log: 17,
chain_log: 16,
searches: 128,
accel: 1,
window: 2 * 1024 * 1024,
entropy: true,
lazy: true,
dual_hash: true,
min_match_accept: MIN_MATCH,
good_enough: 256,
},
_ => LevelParams {
level,
hash_log: 18,
chain_log: 17,
searches: 512,
accel: 1,
window: MAX_OFFSET,
entropy: true,
lazy: true,
dual_hash: true,
min_match_accept: MIN_MATCH,
good_enough: 512,
},
};
p.level = level;
p
}
struct MatchFinder {
hash_log: u32,
chain_log: u32,
hash_table: Vec<u32>,
hash5_table: Vec<u32>,
chain: Vec<u32>,
dual: bool,
window: usize,
}
impl MatchFinder {
fn new(p: &LevelParams, total_len: usize) -> Self {
let hash_size = 1usize << p.hash_log;
let chain_size = if p.chain_log > 0 {
1usize << p.chain_log
} else {
0
};
Self {
hash_log: p.hash_log,
chain_log: p.chain_log,
hash_table: vec![0; hash_size],
hash5_table: if p.dual_hash {
vec![0; hash_size]
} else {
Vec::new()
},
chain: vec![0; chain_size],
dual: p.dual_hash,
window: p.window.min(MAX_OFFSET).min(total_len.max(1)),
}
}
fn seed_history(&mut self, data: &[u8], end: usize) {
let end = end.min(data.len().saturating_sub(MIN_MATCH));
let step = if end > 64 * 1024 { 3 } else { 1 };
let mut pos = 0usize;
while pos < end {
self.insert(data, pos);
pos += step;
}
if end > 0 {
let last = end.saturating_sub(1);
if last % step != 0 {
self.insert(data, last);
}
}
}
#[inline]
fn hash4(&self, v: u32) -> usize {
(v.wrapping_mul(0x9E37_79B1) >> (32 - self.hash_log)) as usize
}
#[inline]
fn hash5(data: &[u8], pos: usize, hash_log: u32) -> usize {
let v = u32::from_le_bytes(data[pos..pos + 4].try_into().unwrap())
^ (u32::from(data[pos + 4]) << 24);
(v.wrapping_mul(0x85EB_CA77) >> (32 - hash_log)) as usize
}
#[inline]
fn insert(&mut self, data: &[u8], pos: usize) {
if pos + 4 > data.len() {
return;
}
let h = self.hash4(read_u32(data, pos));
let prev = self.hash_table[h];
self.hash_table[h] = (pos as u32).wrapping_add(1);
if self.chain_log > 0 {
let mask = (1u32 << self.chain_log) - 1;
self.chain[(pos as u32 & mask) as usize] = prev;
}
if self.dual && pos + 5 <= data.len() {
let h5 = Self::hash5(data, pos, self.hash_log);
self.hash5_table[h5] = (pos as u32).wrapping_add(1);
}
}
fn find(
&self,
data: &[u8],
pos: usize,
max_len: usize,
searches: u32,
good_enough: usize,
) -> Option<(usize, usize)> {
if pos + MIN_MATCH > data.len() || max_len < MIN_MATCH {
return None;
}
let v = read_u32(data, pos);
let h = self.hash4(v);
let mut best_len = MIN_MATCH - 1;
let mut best_off = 0usize;
let low = pos.saturating_sub(self.window);
let try_cand = |cand: u32, best_len: &mut usize, best_off: &mut usize| -> bool {
if cand == 0 {
return false;
}
let cpos = (cand as usize).wrapping_sub(1);
if cpos >= pos || cpos < low {
return false;
}
let off = pos - cpos;
if off == 0 || off > self.window {
return false;
}
if read_u32(data, cpos) != v {
return true; }
let ml = MIN_MATCH
+ simd::match_len(
&data[cpos + MIN_MATCH..],
&data[pos + MIN_MATCH..],
(max_len - MIN_MATCH).min(MAX_MATCH_LEN - MIN_MATCH),
);
if ml > *best_len {
*best_len = ml;
*best_off = off;
if ml >= good_enough {
return false; }
}
true
};
let mut cand = self.hash_table[h];
let mut probes = 0u32;
let chain_mask = if self.chain_log > 0 {
(1u32 << self.chain_log) - 1
} else {
0
};
while cand != 0 && probes < searches {
probes += 1;
if self.chain_log > 0 {
let cpos = (cand as usize).wrapping_sub(1);
let idx = (cpos as u32 & chain_mask) as usize;
simd::prefetch_read(self.chain.as_ptr().wrapping_add(idx).cast::<u8>());
}
if !try_cand(cand, &mut best_len, &mut best_off) {
break;
}
if best_len >= good_enough {
break;
}
if self.chain_log > 0 {
let cpos = (cand as usize).wrapping_sub(1);
cand = self.chain[(cpos as u32 & chain_mask) as usize];
} else {
break;
}
}
if self.dual && pos + 5 <= data.len() && best_len < good_enough {
let h5 = Self::hash5(data, pos, self.hash_log);
let c5 = self.hash5_table[h5];
let _ = try_cand(c5, &mut best_len, &mut best_off);
}
if best_len >= MIN_MATCH && best_off > 0 {
Some((best_off, best_len))
} else {
None
}
}
}
#[inline]
fn read_u32(data: &[u8], pos: usize) -> u32 {
u32::from_le_bytes(data[pos..pos + 4].try_into().unwrap())
}
#[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 get_varint(src: &[u8], ip: &mut usize) -> Result<u32> {
let mut result = 0u32;
let mut shift = 0u32;
loop {
if *ip >= src.len() {
return Err(Error::Decompression("zex: truncated varint".into()));
}
let b = src[*ip];
*ip += 1;
result |= u32::from(b & 0x7F) << shift;
if b & 0x80 == 0 {
return Ok(result);
}
shift += 7;
if shift > 28 {
return Err(Error::Decompression("zex: varint overflow".into()));
}
}
}
const FLAG_HUFF: u8 = 1;
const FLAG_OFF3: u8 = 2; const FLAG_REP: u8 = 4;
const FLAG_FSE: u8 = 8;
const FLAG_CODETAB: u8 = 0x10;
fn encode_offset_code(offset: u32, lit_len: 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);
let _ = lit_len;
reps[2] = reps[1];
reps[1] = reps[0];
reps[0] = offset;
code
}
fn decode_offset_code(code: u32, lit_len: u32, reps: &mut [u32; 3]) -> Result<u32> {
let offset = if code < 3 {
let idx = code as usize;
let mut off = reps[idx];
if lit_len == 0 && code == 0 {
}
if idx != 0 {
let selected = off;
for i in (1..=idx).rev() {
reps[i] = reps[i - 1];
}
reps[0] = selected;
off = selected;
}
if off == 0 {
return Err(Error::Decompression("rep offset is 0".into()));
}
off
} else {
let off = code - 3;
if off == 0 {
return Err(Error::Decompression("raw offset code maps to 0".into()));
}
reps[2] = reps[1];
reps[1] = reps[0];
reps[0] = off;
off
};
Ok(offset)
}
pub fn compress(src: &[u8], level: u8) -> Result<Vec<u8>> {
let mut out = Vec::with_capacity(src.len().saturating_add(64));
compress_into(src, &mut out, level, None)?;
Ok(out)
}
pub fn compress_with_history(src: &[u8], level: u8, dict: Option<&[u8]>) -> Result<Vec<u8>> {
let mut out = Vec::with_capacity(src.len().saturating_add(64));
compress_into(src, &mut out, level, dict)?;
Ok(out)
}
pub fn compress_into(src: &[u8], out: &mut Vec<u8>, level: 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 p = params_for_level(level);
let (literals, seqs) = if crate::algorithms::optimal::should_use(level) && dlen == 0 {
crate::algorithms::optimal::parse(src)
} else {
greedy_parse(src, dict, &p)
};
emit_payload(out, level, p.entropy, &literals, &seqs)
}
fn greedy_parse(src: &[u8], dict: &[u8], p: &LevelParams) -> (Vec<u8>, Vec<(u32, u32, u32)>) {
use crate::algorithms::ldm::{LDM_MIN_MATCH, LdmTable};
let dlen = dict.len();
let mut combined = Vec::with_capacity(dlen + src.len());
combined.extend_from_slice(dict);
combined.extend_from_slice(src);
let total = combined.len();
let base = dlen;
let end_src = total;
let mut mf = MatchFinder::new(p, total);
if dlen >= MIN_MATCH {
mf.seed_history(&combined, dlen);
}
let use_ldm = LdmTable::should_use(p.level, src.len());
let mut ldm = if use_ldm {
let mut t = LdmTable::new();
if dlen >= 8 {
t.seed(&combined, 0, dlen);
}
Some(t)
} else {
None
};
let mut literals = Vec::with_capacity(src.len() / 2 + 16);
let mut seqs: Vec<(u32, u32, u32)> = Vec::new();
let mut anchor = base;
let mut ip = base;
let limit = end_src.saturating_sub(MIN_MATCH + 1);
let mut miss = 0u32;
while ip < limit {
let remain = end_src - ip;
let found = mf.find(&combined, ip, remain, p.searches, p.good_enough);
mf.insert(&combined, ip);
if let Some(ref mut ldm_table) = ldm {
ldm_table.maybe_insert(&combined, ip);
}
let ldm_hit = if found
.as_ref()
.map(|&(_, m)| m >= p.min_match_accept)
.unwrap_or(false)
{
None
} else {
ldm.as_ref()
.and_then(|t| t.find(&combined, ip, remain))
.filter(|&(_, ml)| ml >= LDM_MIN_MATCH)
.map(|(o, m)| (o, m.min(remain)))
};
if let Some((ldm_off, ldm_ml)) = ldm_hit {
let at = ip;
debug_assert!(at >= base && anchor >= base);
let lit_len = (at - anchor) as u32;
literals.extend_from_slice(&combined[anchor..at]);
seqs.push((lit_len, ldm_ml as u32, ldm_off as u32));
let match_end = at + ldm_ml;
let mut pcur = at + 2;
while pcur < match_end && pcur + 4 <= end_src {
mf.insert(&combined, pcur);
if let Some(ref mut t) = ldm {
t.maybe_insert(&combined, pcur);
}
pcur += 4;
}
ip = match_end;
anchor = match_end;
miss = 0;
continue;
}
let (mut off, mut mlen, mut at) = match found {
Some((o, m)) if m >= p.min_match_accept => (o, m, ip),
_ => {
miss = miss.saturating_add(1);
let step = if ldm.is_some() {
1
} else if miss > 16 {
(1 + ((miss as usize - 16) >> p.accel.max(1) as usize)).min(32)
} else {
1
};
ip += step;
continue;
}
};
if p.lazy && at + 1 < limit {
let found2 = mf.find(
&combined,
at + 1,
end_src - (at + 1),
p.searches,
p.good_enough,
);
mf.insert(&combined, at + 1);
if let Some(ref mut ldm_table) = ldm {
ldm_table.maybe_insert(&combined, at + 1);
}
if let Some((o2, m2)) = found2 {
let take_lazy = m2 > mlen || (m2 == mlen + 1 && o2 < off);
if take_lazy {
at += 1;
off = o2;
mlen = m2;
}
}
}
if at + mlen > end_src {
mlen = end_src - at;
}
if mlen < MIN_MATCH {
ip = at + 1;
continue;
}
if mlen == MIN_MATCH && off > 4096 {
ip = at + 1;
continue;
}
debug_assert!(at >= base && anchor >= base);
let lit_len = (at - anchor) as u32;
literals.extend_from_slice(&combined[anchor..at]);
seqs.push((lit_len, mlen as u32, off as u32));
let match_end = at + mlen;
let insert_step = if p.accel >= 4 { 2 } else { 1 };
let mut pcur = at + insert_step;
while pcur < match_end && pcur + 4 <= end_src {
mf.insert(&combined, pcur);
if let Some(ref mut ldm_table) = ldm {
ldm_table.maybe_insert(&combined, pcur);
}
pcur += insert_step;
}
ip = match_end;
anchor = match_end;
miss = 0;
}
if anchor < end_src {
let lit_len = (end_src - anchor) as u32;
literals.extend_from_slice(&combined[anchor..end_src]);
seqs.push((lit_len, 0, 0));
} else if seqs.is_empty() {
literals.extend_from_slice(src);
seqs.push((src.len() as u32, 0, 0));
}
(literals, seqs)
}
#[inline]
fn varint_bytes(v: u32) -> usize {
match v {
0..=0x7F => 1,
0x80..=0x3FFF => 2,
0x4000..=0x001F_FFFF => 3,
0x0020_0000..=0x0FFF_FFFF => 4,
_ => 5,
}
}
fn seqs_varint_size(lls: &[u32], mls: &[u32], ofs: &[u32]) -> usize {
let mut n = 0usize;
for i in 0..lls.len() {
n += varint_bytes(lls[i]) + varint_bytes(mls[i]);
if mls[i] > 0 {
n += varint_bytes(ofs[i]);
}
}
n
}
fn emit_payload(
out: &mut Vec<u8>,
level: u8,
entropy: bool,
literals: &[u8],
seqs: &[(u32, u32, u32)],
) -> Result<()> {
let mut flags = FLAG_REP;
let mut reps = [1u32, 4u32, 8u32];
let mut lls = Vec::with_capacity(seqs.len());
let mut mls = Vec::with_capacity(seqs.len());
let mut ofs = Vec::with_capacity(seqs.len());
for &(lit_len, match_len, offset) in seqs {
lls.push(lit_len);
mls.push(match_len);
if match_len > 0 {
let code = encode_offset_code(offset, lit_len, &mut reps);
ofs.push(code);
} else {
ofs.push(0);
}
}
let raw_seq_est = seqs_varint_size(&lls, &mls, &ofs);
let huff_min = if level >= 15 {
48
} else if level >= 9 {
96
} else {
160
};
let mut freq = [0u32; 256];
let mut distinct = 0u32;
for &b in literals {
let c = &mut freq[b as usize];
if *c == 0 {
distinct += 1;
}
*c += 1;
}
let huff = if entropy && literals.len() >= huff_min && (2..=200).contains(&distinct) {
build_encoder(&freq).and_then(|enc| {
let mut bits = 0u64;
for (s, &f) in freq.iter().enumerate() {
if f > 0 {
bits += u64::from(f) * u64::from(enc.lengths()[s]);
}
}
let est = 4 + 256 + 4 + bits.div_ceil(8) as usize;
let margin = (literals.len() / 50).max(32);
if est + margin < literals.len() {
Some(enc)
} else {
None
}
})
} else {
None
};
let lit_payload: Vec<u8> = if let Some(ref enc) = huff {
flags |= FLAG_HUFF;
let mut buf = Vec::with_capacity(literals.len() + 8);
buf.extend_from_slice(&(literals.len() as u32).to_le_bytes());
enc.write_table(&mut buf);
let mut bw = BitWriter::with_capacity(literals.len());
for &b in literals {
enc.encode(&mut bw, b);
}
let bits = bw.finish();
buf.extend_from_slice(&(bits.len() as u32).to_le_bytes());
buf.extend_from_slice(&bits);
if buf.len() >= literals.len() {
flags &= !FLAG_HUFF;
literals.to_vec()
} else {
buf
}
} else {
literals.to_vec()
};
let min_seqs_ct = if level >= 10 { 6 } else { 10 };
let use_codetab = seqs.len() >= min_seqs_ct && level >= 5;
let mut seq_blob = Vec::new();
let mut used_codetab = false;
if use_codetab {
let mut ll_codes: Vec<u8> = Vec::with_capacity(seqs.len());
let mut ml_codes: Vec<u8> = Vec::with_capacity(seqs.len());
let mut off_codes: Vec<u8> = Vec::with_capacity(seqs.len());
let mut extra_bw = BitWriter::with_capacity(seqs.len() * 4);
let mut extra_bits_est = 0u64;
for i in 0..seqs.len() {
let (llc, lle, lleb) = encode_ll(lls[i]);
ll_codes.push(llc);
if lleb > 0 {
extra_bw.write_bits(lle, lleb as u32);
extra_bits_est += u64::from(lleb);
}
let (mlc, mle, mleb) = encode_ml(mls[i]);
ml_codes.push(mlc);
if mleb > 0 {
extra_bw.write_bits(mle, mleb as u32);
extra_bits_est += u64::from(mleb);
}
if mls[i] > 0 {
let (ofc, ofe, ofeb) = encode_off_log2(ofs[i]);
off_codes.push(ofc);
if ofeb > 0 {
extra_bw.write_bits(ofe, ofeb as u32);
extra_bits_est += u64::from(ofeb);
}
} else {
off_codes.push(0);
}
}
let extra_bytes = extra_bw.finish();
let _ = extra_bits_est;
let ll_u32: Vec<u32> = ll_codes.iter().map(|&c| c as u32).collect();
let ml_u32: Vec<u32> = ml_codes.iter().map(|&c| c as u32).collect();
let of_u32: Vec<u32> = off_codes.iter().map(|&c| c as u32).collect();
let e_ll = encode_u32_array_compact(&ll_u32)?;
let e_ml = encode_u32_array_compact(&ml_u32)?;
let e_of = encode_u32_array_compact(&of_u32)?;
let ct_size = e_ll.len() + e_ml.len() + e_of.len() + 4 + extra_bytes.len();
let margin = (raw_seq_est / 33).max(8);
if ct_size + margin < raw_seq_est {
flags |= FLAG_CODETAB | FLAG_FSE;
seq_blob.extend_from_slice(&e_ll);
seq_blob.extend_from_slice(&e_ml);
seq_blob.extend_from_slice(&e_of);
seq_blob.extend_from_slice(&(extra_bytes.len() as u32).to_le_bytes());
seq_blob.extend_from_slice(&extra_bytes);
used_codetab = true;
}
}
if !used_codetab {
let use_fse = seqs.len() >= 12 && level >= 3 && raw_seq_est >= 64;
if use_fse {
let e_ll = encode_u32_array_compact(&lls)?;
let e_ml = encode_u32_array_compact(&mls)?;
let e_of = encode_u32_array_compact(&ofs)?;
let fse_size = e_ll.len() + e_ml.len() + e_of.len();
let margin = (raw_seq_est / 25).max(16);
if fse_size + margin < raw_seq_est {
flags |= FLAG_FSE;
seq_blob.extend_from_slice(&e_ll);
seq_blob.extend_from_slice(&e_ml);
seq_blob.extend_from_slice(&e_of);
}
}
if flags & FLAG_FSE == 0 {
seq_blob.reserve(raw_seq_est);
for i in 0..seqs.len() {
put_varint(&mut seq_blob, lls[i]);
put_varint(&mut seq_blob, mls[i]);
if mls[i] > 0 {
put_varint(&mut seq_blob, ofs[i]);
}
}
}
}
out.push(flags);
out.extend_from_slice(&(lit_payload.len() as u32).to_le_bytes());
out.extend_from_slice(&(seqs.len() as u32).to_le_bytes());
out.extend_from_slice(&lit_payload);
out.extend_from_slice(&seq_blob);
Ok(())
}
pub fn decompress(src: &[u8], uncompressed_size: usize) -> Result<Vec<u8>> {
let mut out = Vec::with_capacity(uncompressed_size);
decompress_into(src, &mut out, uncompressed_size, None)?;
Ok(out)
}
pub fn decompress_with_history(
src: &[u8],
uncompressed_size: usize,
dict: Option<&[u8]>,
) -> Result<Vec<u8>> {
let mut out = Vec::with_capacity(uncompressed_size);
decompress_into(src, &mut out, uncompressed_size, dict)?;
Ok(out)
}
pub fn decompress_into(
src: &[u8],
dst: &mut Vec<u8>,
uncompressed_size: usize,
dict: Option<&[u8]>,
) -> Result<()> {
dst.clear();
dst.reserve(uncompressed_size);
let dict = dict.unwrap_or(&[]);
let dict = if dict.len() > MAX_OFFSET {
&dict[dict.len() - MAX_OFFSET..]
} else {
dict
};
if src.len() < 9 {
return Err(Error::Decompression("zex: block too short".into()));
}
let mut ip = 0usize;
let flags = src[ip];
ip += 1;
let lit_bytes = u32::from_le_bytes(src[ip..ip + 4].try_into().unwrap()) as usize;
ip += 4;
let seq_count = u32::from_le_bytes(src[ip..ip + 4].try_into().unwrap()) as usize;
ip += 4;
if ip.saturating_add(lit_bytes) > src.len() {
return Err(Error::Decompression(
"zex: truncated literals section".into(),
));
}
if seq_count > uncompressed_size.saturating_add(1) {
return Err(Error::Decompression("zex: seq_count absurd".into()));
}
check_block_sizes(src.len(), uncompressed_size)?;
let lit_section = &src[ip..ip + lit_bytes];
ip += lit_bytes;
let use_rep = flags & FLAG_REP != 0;
let use_fse = flags & FLAG_FSE != 0;
let use_codetab = flags & FLAG_CODETAB != 0;
let off3 = flags & FLAG_OFF3 != 0;
let literals: Vec<u8> = if flags & FLAG_HUFF != 0 {
if use_rep {
if lit_section.len() < 4 + 256 + 4 {
return Err(Error::Decompression("zex: truncated huffman(rep)".into()));
}
let expected_lits = u32::from_le_bytes(lit_section[0..4].try_into().unwrap()) as usize;
if expected_lits > uncompressed_size {
return Err(Error::Decompression(
"zex: lit_count exceeds uncompressed_size".into(),
));
}
let mut lens = [0u8; 256];
lens.copy_from_slice(&lit_section[4..260]);
let bits_len = u32::from_le_bytes(lit_section[260..264].try_into().unwrap()) as usize;
if 264 + bits_len > lit_section.len() {
return Err(Error::Decompression("zex: truncated huffman bits".into()));
}
let dec = decoder_from_lengths(&lens)?;
let mut br = BitReader::new(&lit_section[264..264 + bits_len]);
let mut lits = Vec::with_capacity(expected_lits);
for _ in 0..expected_lits {
lits.push(dec.decode(&mut br)?);
}
lits
} else {
if lit_section.len() < 260 {
return Err(Error::Decompression("zex: truncated huffman table".into()));
}
let mut lens = [0u8; 256];
lens.copy_from_slice(&lit_section[..256]);
let bits_len = u32::from_le_bytes(lit_section[256..260].try_into().unwrap()) as usize;
if 260 + bits_len > lit_section.len() {
return Err(Error::Decompression("zex: truncated huffman bits".into()));
}
let expected_lits = dry_run_lit_count(&src[ip..], seq_count, flags)?;
if expected_lits > uncompressed_size {
return Err(Error::Decompression(
"zex: lit_count exceeds uncompressed_size".into(),
));
}
let dec = decoder_from_lengths(&lens)?;
let mut br = BitReader::new(&lit_section[260..260 + bits_len]);
let mut lits = Vec::with_capacity(expected_lits);
for _ in 0..expected_lits {
lits.push(dec.decode(&mut br)?);
}
lits
}
} else {
lit_section.to_vec()
};
let (lls, mls, ofs): (Vec<u32>, Vec<u32>, Vec<u32>) = if use_codetab && use_fse {
let ll_codes = decode_u32_array_auto(src, &mut ip, seq_count)?;
let ml_codes = decode_u32_array_auto(src, &mut ip, seq_count)?;
let off_codes = decode_u32_array_auto(src, &mut ip, seq_count)?;
if ip + 4 > src.len() {
return Err(Error::Decompression(
"zex: codetab extra len truncated".into(),
));
}
let extra_len = u32::from_le_bytes(src[ip..ip + 4].try_into().unwrap()) as usize;
ip += 4;
if ip + extra_len > src.len() {
return Err(Error::Decompression(
"zex: codetab extra bits truncated".into(),
));
}
let mut ebr = BitReader::new(&src[ip..ip + extra_len]);
ip += extra_len;
let _ = ip;
let mut lls = Vec::with_capacity(seq_count);
let mut mls = Vec::with_capacity(seq_count);
let mut ofs = Vec::with_capacity(seq_count);
for i in 0..seq_count {
let llc = ll_codes[i] as u8;
let lleb = if (llc as usize) < crate::utils::fse::LL_CODE_TABLE.len() {
crate::utils::fse::LL_CODE_TABLE[llc as usize].1
} else {
return Err(Error::Decompression(format!("bad LL code {llc}")));
};
let ll_extra = if lleb > 0 {
ebr.read_bits(lleb as u32).ok_or_else(|| {
Error::Decompression("codetab: LL extra bits truncated".into())
})?
} else {
0
};
lls.push(decode_ll(llc, ll_extra)?);
let mlc = ml_codes[i] as u8;
if mlc > 53 {
return Err(Error::Decompression(format!("bad ML code {mlc}")));
}
let mleb = crate::utils::fse::ml_extra_bits(mlc);
let ml_extra = if mleb > 0 {
ebr.read_bits(mleb as u32).ok_or_else(|| {
Error::Decompression("codetab: ML extra bits truncated".into())
})?
} else {
0
};
mls.push(decode_ml(mlc, ml_extra)?);
if mls[i] > 0 {
let ofc = off_codes[i] as u8;
if ofc > 32 {
return Err(Error::Decompression(format!("bad OFF code {ofc}")));
}
let ofeb = if ofc > 0 { (ofc - 1) as u32 } else { 0 };
let of_extra = if ofeb > 0 {
ebr.read_bits(ofeb).ok_or_else(|| {
Error::Decompression("codetab: OFF extra bits truncated".into())
})?
} else {
0
};
ofs.push(decode_off_log2(ofc, of_extra)?);
} else {
ofs.push(0);
}
}
(lls, mls, ofs)
} else if use_fse {
let lls = decode_u32_array_auto(src, &mut ip, seq_count)?;
let mls = decode_u32_array_auto(src, &mut ip, seq_count)?;
let ofs = decode_u32_array_auto(src, &mut ip, seq_count)?;
(lls, mls, ofs)
} else if use_rep {
let mut lls = Vec::with_capacity(seq_count);
let mut mls = Vec::with_capacity(seq_count);
let mut ofs = Vec::with_capacity(seq_count);
for _ in 0..seq_count {
let ll = get_varint(src, &mut ip)?;
let ml = get_varint(src, &mut ip)?;
lls.push(ll);
mls.push(ml);
if ml > 0 {
ofs.push(get_varint(src, &mut ip)?);
} else {
ofs.push(0);
}
}
(lls, mls, ofs)
} else {
let mut lls = Vec::with_capacity(seq_count);
let mut mls = Vec::with_capacity(seq_count);
let mut ofs = Vec::with_capacity(seq_count);
for _ in 0..seq_count {
let ll = get_varint(src, &mut ip)?;
let ml = get_varint(src, &mut ip)?;
lls.push(ll);
mls.push(ml);
if ml > 0 {
let o = if off3 {
if ip + 3 > src.len() {
return Err(Error::Decompression("zex: truncated offset3".into()));
}
let o =
src[ip] as u32 | ((src[ip + 1] as u32) << 8) | ((src[ip + 2] as u32) << 16);
ip += 3;
o
} else {
if ip + 2 > src.len() {
return Err(Error::Decompression("zex: truncated offset2".into()));
}
let o = src[ip] as u32 | ((src[ip + 1] as u32) << 8);
ip += 2;
o
};
ofs.push(o);
} else {
ofs.push(0);
}
}
(lls, mls, ofs)
};
let mut lit_pos = 0usize;
let mut reps = [1u32, 4u32, 8u32];
for i in 0..seq_count {
let lit_len = lls[i] as usize;
let mlen = mls[i] as usize;
if lit_pos + lit_len > literals.len() {
return Err(Error::Decompression("zex: literal overrun".into()));
}
if dst.len().saturating_add(lit_len) > uncompressed_size {
return Err(Error::Decompression("zex: output overflow (lits)".into()));
}
dst.extend_from_slice(&literals[lit_pos..lit_pos + lit_len]);
lit_pos += lit_len;
if mlen == 0 {
continue;
}
if mlen > MAX_MATCH_LEN {
return Err(Error::Decompression("zex: match too long".into()));
}
let offset = if use_rep {
decode_offset_code(ofs[i], lls[i], &mut reps)? as usize
} else {
ofs[i] as usize
};
check_match_with_history(offset, mlen, dst.len(), dict.len())?;
if dst.len().saturating_add(mlen) > uncompressed_size {
return Err(Error::Decompression("zex: output overflow (match)".into()));
}
copy_match_with_history(dst, offset, mlen, dict);
}
if lit_pos != literals.len() {
return Err(Error::Decompression(format!(
"zex: unused literals {} of {}",
literals.len() - lit_pos,
literals.len()
)));
}
if dst.len() != uncompressed_size {
return Err(Error::SizeMismatch {
expected: uncompressed_size as u64,
actual: dst.len() as u64,
});
}
Ok(())
}
fn dry_run_lit_count(seq_src: &[u8], seq_count: usize, flags: u8) -> Result<usize> {
let mut ip = 0usize;
let mut total = 0usize;
let off3 = flags & FLAG_OFF3 != 0;
for _ in 0..seq_count {
let lit_len = get_varint(seq_src, &mut ip)? as usize;
let mlen = get_varint(seq_src, &mut ip)? as usize;
total = total.saturating_add(lit_len);
if mlen > 0 {
let step = if off3 { 3 } else { 2 };
if ip + step > seq_src.len() {
return Err(Error::Decompression("zex: dry-run truncated".into()));
}
ip += step;
}
}
Ok(total)
}
pub struct ZexNativeCompressor;
impl crate::algorithms::BlockCompressor for ZexNativeCompressor {
fn compress_block(&self, src: &[u8], dst: &mut Vec<u8>, level: u8) -> Result<BlockType> {
dst.clear();
compress_into(src, dst, level, None)?;
Ok(BlockType::Zex)
}
}
pub struct ZexNativeDecompressor;
impl crate::algorithms::BlockDecompressor for ZexNativeDecompressor {
fn decompress_block(
&self,
src: &[u8],
dst: &mut Vec<u8>,
uncompressed_size: usize,
) -> Result<()> {
decompress_into(src, dst, uncompressed_size, None)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn roundtrip_text() {
let src = b"ZEX native algorithm test. ".repeat(50);
for level in [1u8, 3, 6, 12, 19] {
let c = compress(&src, level).unwrap();
let d = decompress(&c, src.len()).unwrap();
assert_eq!(d, src.as_slice(), "level {level}");
}
}
#[test]
fn roundtrip_zeros() {
let src = vec![0u8; 8192];
let c = compress(&src, 3).unwrap();
assert!(c.len() < 200, "zeros should pack tiny, got {}", c.len());
assert_eq!(decompress(&c, src.len()).unwrap(), src);
}
#[test]
fn higher_level_not_worse_on_rep() {
let src = b"ABCDEFGHIJKLMNOP ".repeat(400);
let c3 = compress(&src, 3).unwrap();
let c12 = compress(&src, 12).unwrap();
assert!(
c12.len() <= c3.len() + 32,
"l12={} l3={}",
c12.len(),
c3.len()
);
assert_eq!(decompress(&c12, src.len()).unwrap(), src.as_slice());
}
#[test]
fn roundtrip_incompressible() {
let mut src = Vec::with_capacity(10_000);
let mut x = 0xC0FFEE_u32;
for _ in 0..10_000 {
x = x.wrapping_mul(1664525).wrapping_add(1013904223);
src.push((x >> 24) as u8);
}
let c = compress(&src, 1).unwrap();
assert_eq!(decompress(&c, src.len()).unwrap(), src);
}
#[test]
fn dictionary_history_helps() {
let dict = b"HTTP/1.1 200 OK\r\nContent-Type: application/json\r\n\r\n";
let msg = b"HTTP/1.1 200 OK\r\nContent-Type: application/json\r\n\r\n{\"ok\":true}";
let plain = compress(msg, 6).unwrap();
let with_dict = compress_with_history(msg, 6, Some(dict)).unwrap();
assert!(
with_dict.len() < plain.len(),
"dict should help: with={} plain={}",
with_dict.len(),
plain.len()
);
let d = decompress_with_history(&with_dict, msg.len(), Some(dict)).unwrap();
assert_eq!(d, msg);
let bad = decompress_with_history(&with_dict, msg.len(), None);
assert!(bad.is_err() || bad.unwrap() != msg);
}
#[test]
fn dictionary_roundtrip_only_in_dict() {
let dict = b"ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
let msg = b"ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789ABCDEF";
let c = compress_with_history(msg, 5, Some(dict)).unwrap();
let d = decompress_with_history(&c, msg.len(), Some(dict)).unwrap();
assert_eq!(d, msg);
}
#[test]
fn large_block_ldm_roundtrip() {
let pattern =
b"ZEX_NATIVE_LDM_BLOCK_PATTERN_0123456789ABCDEF_XXXXYYYYZZZZ!!!!_PAD_TO_64PLUS";
assert!(
pattern.len() >= 64,
"pattern len {} must be >= LDM_MIN_MATCH",
pattern.len()
);
let gap = 300_000usize;
let mut src = Vec::with_capacity(pattern.len() * 2 + gap);
src.extend_from_slice(pattern);
let mut x = 0xA5A5_A5A5u32;
for _ in 0..gap {
x = x.wrapping_mul(1664525).wrapping_add(1013904223);
src.push((x >> 24) as u8);
}
src.extend_from_slice(pattern);
let c = compress(&src, 6).unwrap();
assert!(
c.len() < src.len(),
"should shrink: {} vs {}",
c.len(),
src.len()
);
let d = decompress(&c, src.len()).unwrap();
assert_eq!(d, src);
}
#[test]
fn dict_rep_many_records_level6() {
let dict = b"HTTP/1.1 200 OK\r\nContent-Type: application/json\r\n\r\n";
let mut msg = Vec::new();
for i in 0..200 {
msg.extend_from_slice(
format!(
"HTTP/1.1 200 OK\r\nContent-Type: application/json\r\n\r\n{{\"id\":{i}}}\n"
)
.as_bytes(),
);
}
for level in [1u8, 2, 3, 4, 5, 6, 9, 12] {
let c = compress_with_history(&msg, level, Some(dict)).unwrap();
let d = decompress_with_history(&c, msg.len(), Some(dict)).unwrap();
assert_eq!(d, msg, "level {level}");
}
}
}