use crate::format::block::BlockType;
use crate::{Error, Result};
const MIN_MATCH: usize = 4;
const LAST_LITERALS: usize = 5;
const MATCH_SAFEGUARD: usize = 12;
const HASH_LOG: usize = 12; const HASH_SIZE: usize = 1 << HASH_LOG;
const MAX_DISTANCE: usize = 65535;
#[inline]
fn hash4(data: &[u8], pos: usize) -> usize {
let v = u32::from_le_bytes(data[pos..pos + 4].try_into().unwrap());
((v.wrapping_mul(2654435761)) >> (32 - HASH_LOG)) as usize
}
#[inline]
fn common_prefix_len(a: &[u8], b: &[u8]) -> usize {
let n = a.len().min(b.len());
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 write_var_len(out: &mut Vec<u8>, mut len: usize) {
while len >= 255 {
out.push(255);
len -= 255;
}
out.push(len as u8);
}
pub fn compress(src: &[u8], _level: u8) -> Result<Vec<u8>> {
let mut out = Vec::with_capacity(src.len() + src.len() / 255 + 16);
compress_into(src, &mut out, _level)?;
Ok(out)
}
pub fn compress_into(src: &[u8], out: &mut Vec<u8>, _level: u8) -> Result<()> {
let n = src.len();
if n == 0 {
out.push(0);
return Ok(());
}
if n < MATCH_SAFEGUARD {
emit_last_literals(out, src);
return Ok(());
}
let mut hash_table = [0u32; HASH_SIZE];
let mut anchor = 0usize;
let iend = n;
let mflimit = iend.saturating_sub(MATCH_SAFEGUARD);
let match_limit = iend - LAST_LITERALS;
let mut ip = 1usize;
while ip <= mflimit {
let h = hash4(src, ip);
let ref_pos = hash_table[h] as usize;
hash_table[h] = ip as u32;
let distance = ip.wrapping_sub(ref_pos);
if ref_pos == 0
|| distance == 0
|| distance > MAX_DISTANCE
|| ref_pos >= ip
|| ip + MIN_MATCH > match_limit
|| src[ref_pos..ref_pos + MIN_MATCH] != src[ip..ip + MIN_MATCH]
{
ip += 1;
continue;
}
let mut match_len = MIN_MATCH
+ common_prefix_len(
&src[ref_pos + MIN_MATCH..match_limit],
&src[ip + MIN_MATCH..match_limit],
);
let mut match_pos = ref_pos;
let mut lit_start = ip;
while lit_start > anchor && match_pos > 0 && src[lit_start - 1] == src[match_pos - 1] {
lit_start -= 1;
match_pos -= 1;
match_len += 1;
}
let lit_len = lit_start - anchor;
let offset = (lit_start - match_pos) as u16;
let mut token = 0u8;
let token_lit = if lit_len >= 15 { 15 } else { lit_len };
let ml_stored = match_len - MIN_MATCH;
let token_ml = if ml_stored >= 15 { 15 } else { ml_stored };
token |= (token_lit as u8) << 4;
token |= token_ml as u8;
out.push(token);
if lit_len >= 15 {
write_var_len(out, lit_len - 15);
}
out.extend_from_slice(&src[anchor..lit_start]);
out.push((offset & 0xFF) as u8);
out.push((offset >> 8) as u8);
if ml_stored >= 15 {
write_var_len(out, ml_stored - 15);
}
ip = lit_start + match_len;
anchor = ip;
let fill_end = ip.min(mflimit + 1);
let mut p = lit_start + 1;
while p < fill_end {
hash_table[hash4(src, p)] = p as u32;
p += 1;
}
}
emit_last_literals(out, &src[anchor..]);
Ok(())
}
fn emit_last_literals(out: &mut Vec<u8>, lits: &[u8]) {
let lit_len = lits.len();
let token_lit = if lit_len >= 15 { 15 } else { lit_len };
out.push((token_lit as u8) << 4); if lit_len >= 15 {
write_var_len(out, lit_len - 15);
}
out.extend_from_slice(lits);
}
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);
let mut ip = 0usize;
let src_end = src.len();
while ip < src_end {
let token = src[ip];
ip += 1;
let mut lit_len = (token >> 4) as usize;
if lit_len == 15 {
loop {
if ip >= src_end {
return Err(Error::Decompression("lz4: truncated lit length".into()));
}
let b = src[ip];
ip += 1;
lit_len += b as usize;
if b != 255 {
break;
}
}
}
if lit_len > 0 {
if ip + lit_len > src_end {
return Err(Error::Decompression("lz4: truncated literals".into()));
}
if dst.len() + lit_len > uncompressed_size {
return Err(Error::Decompression("lz4: output overflow (literals)".into()));
}
dst.extend_from_slice(&src[ip..ip + lit_len]);
ip += lit_len;
}
if ip >= src_end {
break;
}
if ip + 2 > src_end {
return Err(Error::Decompression("lz4: truncated offset".into()));
}
let offset = u16::from_le_bytes([src[ip], src[ip + 1]]) as usize;
ip += 2;
if offset == 0 {
return Err(Error::Decompression("lz4: invalid offset 0".into()));
}
if offset > dst.len() {
return Err(Error::Decompression(format!(
"lz4: offset {offset} > decoded {}",
dst.len()
)));
}
let mut match_len = (token & 0x0F) as usize + MIN_MATCH;
if (token & 0x0F) == 15 {
loop {
if ip >= src_end {
return Err(Error::Decompression("lz4: truncated match length".into()));
}
let b = src[ip];
ip += 1;
match_len += b as usize;
if b != 255 {
break;
}
}
}
if dst.len() + match_len > uncompressed_size {
return Err(Error::Decompression("lz4: output overflow (match)".into()));
}
let match_start = dst.len() - offset;
for i in 0..match_len {
let b = dst[match_start + i];
dst.push(b);
}
}
if dst.len() != uncompressed_size {
return Err(Error::SizeMismatch {
expected: uncompressed_size as u64,
actual: dst.len() as u64,
});
}
Ok(())
}
pub struct Lz4Compressor;
impl crate::algorithms::BlockCompressor for Lz4Compressor {
fn compress_block(&self, src: &[u8], dst: &mut Vec<u8>, level: u8) -> Result<BlockType> {
dst.clear();
compress_into(src, dst, level)?;
Ok(BlockType::Lz4)
}
}
pub struct Lz4Decompressor;
impl crate::algorithms::BlockDecompressor for Lz4Decompressor {
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"Hello Hello Hello Hello LZ4 pure Rust block format test!!!!";
let c = compress(src, 1).unwrap();
let d = decompress(&c, src.len()).unwrap();
assert_eq!(d, src);
}
#[test]
fn roundtrip_zeros() {
let src = vec![0u8; 4096];
let c = compress(&src, 1).unwrap();
assert!(c.len() < src.len());
let d = decompress(&c, src.len()).unwrap();
assert_eq!(d, src);
}
#[test]
fn roundtrip_randomish() {
let mut src = Vec::new();
for i in 0..5000u32 {
src.extend_from_slice(&(i.wrapping_mul(2654435761)).to_le_bytes());
}
let c = compress(&src, 1).unwrap();
let d = decompress(&c, src.len()).unwrap();
assert_eq!(d, src);
}
#[test]
fn empty() {
let c = compress(b"", 1).unwrap();
let d = decompress(&c, 0).unwrap();
assert!(d.is_empty());
}
}