use crate::format::block::BlockType;
use crate::utils::bitstream::{BitReader, BitWriter};
use crate::utils::entropy::{build_encoder, decoder_from_lengths};
use crate::{Error, Result};
const MIN_MATCH: usize = 3;
const MAX_OFFSET: usize = 1 << 23;
#[derive(Debug, Clone, Copy)]
struct Seq {
lit_len: u32,
match_len: u32,
offset: u32,
}
struct MatchFinder {
hash_log: u32,
chain_log: u32,
hash_table: Vec<u32>,
chain: Vec<u32>,
window: usize,
}
impl MatchFinder {
fn new(level: u8, src_len: usize) -> Self {
let (hash_log, chain_log) = match level {
1..=2 => (12, 0),
3..=4 => (14, 12),
5..=6 => (15, 13),
7..=9 => (16, 14),
10..=12 => (17, 15),
13..=16 => (18, 16),
_ => (18, 17), };
let hash_size = 1usize << hash_log;
let chain_size = if chain_log > 0 {
1usize << chain_log
} else {
0
};
Self {
hash_log,
chain_log,
hash_table: vec![0; hash_size],
chain: vec![0; chain_size],
window: MAX_OFFSET.min(src_len.max(1)),
}
}
#[inline]
fn hash3(&self, data: &[u8], pos: usize) -> usize {
let v = u32::from_le_bytes([data[pos], data[pos + 1], data[pos + 2], 0]);
((v.wrapping_mul(2654435761)) >> (32 - self.hash_log)) as usize
}
#[inline]
fn hash4(&self, data: &[u8], pos: usize) -> usize {
let v = u32::from_le_bytes(data[pos..pos + 4].try_into().unwrap());
((v.wrapping_mul(2654435761)) >> (32 - self.hash_log)) as usize
}
fn insert(&mut self, data: &[u8], pos: usize) {
if pos + 4 > data.len() {
return;
}
let h = self.hash4(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;
}
}
fn find_best(
&self,
data: &[u8],
pos: usize,
max_len: usize,
max_searches: usize,
) -> Option<(usize, usize)> {
if pos + MIN_MATCH > data.len() || max_len < MIN_MATCH {
return None;
}
let h = if pos + 4 <= data.len() {
self.hash4(data, pos)
} else {
self.hash3(data, pos)
};
let mut candidate = self.hash_table[h];
let mut best_len = MIN_MATCH - 1;
let mut best_off = 0usize;
let mut searches = 0usize;
let low = pos.saturating_sub(self.window);
while candidate != 0 && searches < max_searches {
searches += 1;
let cpos = (candidate as usize).wrapping_sub(1);
if cpos >= pos || cpos < low {
break;
}
let offset = pos - cpos;
if offset == 0 || offset > MAX_OFFSET {
break;
}
if pos + 4 <= data.len()
&& cpos + 4 <= data.len()
&& data[cpos..cpos + 4] != data[pos..pos + 4]
{
if self.chain_log > 0 {
let mask = (1u32 << self.chain_log) - 1;
candidate = self.chain[(cpos as u32 & mask) as usize];
} else {
break;
}
continue;
}
let mlen = common_len(&data[cpos..], &data[pos..], max_len);
if mlen > best_len {
best_len = mlen;
best_off = offset;
if mlen >= max_len {
break;
}
}
if self.chain_log > 0 {
let mask = (1u32 << self.chain_log) - 1;
candidate = self.chain[(cpos as u32 & mask) as usize];
} else {
break;
}
}
if best_len >= MIN_MATCH && best_off > 0 {
Some((best_off, best_len))
} else {
None
}
}
}
#[inline]
fn common_len(a: &[u8], b: &[u8], max: usize) -> usize {
let n = a.len().min(b.len()).min(max);
let mut i = 0;
while i + 8 <= n {
let x = u64::from_le_bytes(a[i..i + 8].try_into().unwrap());
let y = u64::from_le_bytes(b[i..i + 8].try_into().unwrap());
if x != y {
return i + ((x ^ y).trailing_zeros() as usize / 8);
}
i += 8;
}
while i < n && a[i] == b[i] {
i += 1;
}
i
}
fn max_searches_for_level(level: u8) -> usize {
match level {
1 => 1,
2 => 2,
3 => 4,
4 => 8,
5 => 16,
6 => 32,
7 => 64,
8 => 128,
9 => 256,
10..=12 => 512,
13..=16 => 1024,
_ => 2048,
}
}
fn generate_sequences(src: &[u8], level: u8) -> (Vec<u8>, Vec<Seq>) {
let n = src.len();
if n == 0 {
return (Vec::new(), Vec::new());
}
let mut mf = MatchFinder::new(level, n);
let searches = max_searches_for_level(level);
let lazy = level >= 3;
let mut literals = Vec::with_capacity(n / 2);
let mut seqs = Vec::new();
let mut pos = 0usize;
let mut lit_start = 0usize;
while pos + MIN_MATCH < n {
mf.insert(src, pos);
let remain = n - pos;
let found = mf.find_best(src, pos, remain, searches);
let (off, mlen) = match found {
Some(m) => m,
None => {
pos += 1;
continue;
}
};
let (off, mlen, match_at) = if lazy && pos + 1 + MIN_MATCH < n {
mf.insert(src, pos + 1);
if let Some((off2, mlen2)) = mf.find_best(src, pos + 1, n - (pos + 1), searches) {
if mlen2 > mlen + 1 {
pos += 1;
(off2, mlen2, pos)
} else {
(off, mlen, pos)
}
} else {
(off, mlen, pos)
}
} else {
(off, mlen, pos)
};
let lit_len = match_at - lit_start;
literals.extend_from_slice(&src[lit_start..match_at]);
seqs.push(Seq {
lit_len: lit_len as u32,
match_len: mlen as u32,
offset: off as u32,
});
let end = match_at + mlen;
let mut p = match_at + 1;
while p < end && p + 4 <= n {
mf.insert(src, p);
p += 1;
}
pos = end;
lit_start = end;
}
if lit_start < n {
literals.extend_from_slice(&src[lit_start..]);
seqs.push(Seq {
lit_len: (n - lit_start) as u32,
match_len: 0,
offset: 0,
});
}
(literals, seqs)
}
fn write_uvarint(out: &mut Vec<u8>, mut v: u32) {
while v >= 0x80 {
out.push((v as u8) | 0x80);
v >>= 7;
}
out.push(v as u8);
}
fn read_uvarint(src: &[u8], ip: &mut usize) -> Result<u32> {
let mut result = 0u32;
let mut shift = 0u32;
loop {
if *ip >= src.len() {
return Err(Error::Decompression("truncated uvarint".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("uvarint overflow".into()));
}
}
}
pub fn compress(src: &[u8], level: u8) -> Result<Vec<u8>> {
let mut out = Vec::with_capacity(src.len() / 2 + 64);
compress_into(src, &mut out, level)?;
Ok(out)
}
pub fn compress_into(src: &[u8], out: &mut Vec<u8>, level: u8) -> Result<()> {
let level = level.clamp(1, 22);
let (literals, seqs) = generate_sequences(src, level);
let mut freq = [0u32; 256];
for &b in &literals {
freq[b as usize] += 1;
}
let huff = if literals.len() >= 64 {
build_encoder(&freq).and_then(|enc| {
let mut bits = 0u64;
for (sym, &f) in freq.iter().enumerate() {
if f > 0 {
bits += u64::from(f) * u64::from(enc.lengths()[sym]);
}
}
let est = 256 + 4 + ((bits + 7) / 8) as usize;
if est < literals.len() {
Some(enc)
} else {
None
}
})
} else {
None
};
let mut flags = 0u8;
if huff.is_some() {
flags |= 1;
}
if !seqs.is_empty() {
flags |= 2;
}
out.push(flags);
out.extend_from_slice(&(literals.len() as u32).to_le_bytes());
out.extend_from_slice(&(seqs.len() as u32).to_le_bytes());
if let Some(ref enc) = huff {
enc.write_table(out);
let mut bw = BitWriter::with_capacity(literals.len());
for &b in &literals {
enc.encode(&mut bw, b);
}
let bits = bw.finish();
out.extend_from_slice(&(bits.len() as u32).to_le_bytes());
out.extend_from_slice(&bits);
} else {
out.extend_from_slice(&literals);
}
for s in &seqs {
write_uvarint(out, s.lit_len);
write_uvarint(out, s.match_len);
if s.match_len > 0 {
write_uvarint(out, s.offset);
}
}
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)?;
Ok(out)
}
pub fn decompress_into(src: &[u8], dst: &mut Vec<u8>, uncompressed_size: usize) -> Result<()> {
dst.clear();
dst.reserve(uncompressed_size);
if src.is_empty() {
if uncompressed_size == 0 {
return Ok(());
}
return Err(Error::Decompression("empty zstd-style block".into()));
}
let mut ip = 0usize;
let flags = src[ip];
ip += 1;
if ip + 8 > src.len() {
return Err(Error::Decompression("truncated zstd-style header".into()));
}
let lit_size = 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;
let use_huff = flags & 1 != 0;
let literals: Vec<u8> = if use_huff {
if ip + 256 > src.len() {
return Err(Error::Decompression("truncated huffman table".into()));
}
let mut lens = [0u8; 256];
lens.copy_from_slice(&src[ip..ip + 256]);
ip += 256;
if ip + 4 > src.len() {
return Err(Error::Decompression("truncated huffman size".into()));
}
let bits_len = u32::from_le_bytes(src[ip..ip + 4].try_into().unwrap()) as usize;
ip += 4;
if ip + bits_len > src.len() {
return Err(Error::Decompression("truncated huffman data".into()));
}
let dec = decoder_from_lengths(&lens)?;
let mut br = BitReader::new(&src[ip..ip + bits_len]);
ip += bits_len;
let mut lits = Vec::with_capacity(lit_size);
for _ in 0..lit_size {
lits.push(dec.decode(&mut br)?);
}
lits
} else {
if ip + lit_size > src.len() {
return Err(Error::Decompression("truncated raw literals".into()));
}
let l = src[ip..ip + lit_size].to_vec();
ip += lit_size;
l
};
let mut lit_pos = 0usize;
for _ in 0..seq_count {
let lit_len = read_uvarint(src, &mut ip)? as usize;
let match_len = read_uvarint(src, &mut ip)? as usize;
if lit_pos + lit_len > literals.len() {
return Err(Error::Decompression("literal overrun".into()));
}
if dst.len() + lit_len > uncompressed_size {
return Err(Error::Decompression("output overflow (lits)".into()));
}
dst.extend_from_slice(&literals[lit_pos..lit_pos + lit_len]);
lit_pos += lit_len;
if match_len == 0 {
continue;
}
let offset = read_uvarint(src, &mut ip)? as usize;
if offset == 0 || offset > dst.len() {
return Err(Error::Decompression(format!(
"bad offset {offset} (decoded {})",
dst.len()
)));
}
if dst.len() + match_len > uncompressed_size {
return Err(Error::Decompression("output overflow (match)".into()));
}
let start = dst.len() - offset;
for i in 0..match_len {
let b = dst[start + i];
dst.push(b);
}
}
if lit_pos < literals.len() {
let rest = &literals[lit_pos..];
if dst.len() + rest.len() > uncompressed_size {
return Err(Error::Decompression("output overflow (tail lits)".into()));
}
dst.extend_from_slice(rest);
}
if dst.len() != uncompressed_size {
return Err(Error::SizeMismatch {
expected: uncompressed_size as u64,
actual: dst.len() as u64,
});
}
Ok(())
}
pub struct ZstdCompressor;
impl crate::algorithms::BlockCompressor for ZstdCompressor {
fn compress_block(&self, src: &[u8], dst: &mut Vec<u8>, level: u8) -> Result<BlockType> {
dst.clear();
compress_into(src, dst, level)?;
Ok(BlockType::Zstd)
}
}
pub struct ZstdDecompressor;
impl crate::algorithms::BlockDecompressor for ZstdDecompressor {
fn decompress_block(
&self,
src: &[u8],
dst: &mut Vec<u8>,
uncompressed_size: usize,
) -> Result<()> {
decompress_into(src, dst, uncompressed_size)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn roundtrip_text() {
let src = b"The quick brown fox jumps over the lazy dog. The quick brown fox jumps.";
for level in [1u8, 3, 6, 9] {
let c = compress(src, level).unwrap();
let d = decompress(&c, src.len()).unwrap();
assert_eq!(d, src, "level {level}");
}
}
#[test]
fn roundtrip_zeros() {
let src = vec![0u8; 8192];
let c = compress(&src, 5).unwrap();
assert!(c.len() < src.len() / 4, "zeros should compress well: {}", c.len());
let d = decompress(&c, src.len()).unwrap();
assert_eq!(d, src);
}
#[test]
fn roundtrip_pattern() {
let mut src = Vec::new();
for _ in 0..200 {
src.extend_from_slice(b"ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789");
}
let c = compress(&src, 4).unwrap();
let d = decompress(&c, src.len()).unwrap();
assert_eq!(d, src);
}
}