use std::fmt;
use crate::error::{Error, Result};
use super::MAX_SIZE;
use super::reader::{read_bytes, read_u32, read_u32_be, read_u64, slice};
const LZFSE_MAGIC_PREFIX: &[u8] = b"bvx";
const LZFSE_END_OF_STREAM: &[u8] = b"bvx$";
const LZFSE_UNCOMPRESSED_BLOCK: &[u8] = b"bvx-";
const LZVN_BLOCK: &[u8] = b"bvxn";
const LZFSE_V1_BLOCK: &[u8] = b"bvx1";
const LZFSE_V2_BLOCK: &[u8] = b"bvx2";
const UNCOMPRESSED_BLOCK_HEADER_SIZE: usize = 8;
const LZVN_BLOCK_HEADER_SIZE: usize = 12;
const LZFSE_V1_BLOCK_HEADER_SIZE: usize = 772;
const LZFSE_V2_BLOCK_HEADER_SIZES: std::ops::RangeInclusive<usize> = 32..=752;
const COMPLZSS_MAGIC: &[u8] = b"complzss";
const COMPLZSS_HEADER_SIZE: usize = 0x180;
const COMPLZSS_CHECKSUM_OFFSET: usize = 8;
const COMPLZSS_DECODED_SIZE_OFFSET: usize = 12;
const COMPLZSS_ENCODED_SIZE_OFFSET: usize = 16;
const LZSS_WINDOW_SIZE: usize = 4096;
const LZSS_MIN_MATCH: usize = 3;
const LZSS_MAX_MATCH: usize = 18;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Compression {
Lzfse,
Complzss,
}
impl Compression {
pub(super) fn detect(data: &[u8]) -> Option<Self> {
if data.starts_with(COMPLZSS_MAGIC) {
Some(Self::Complzss)
} else if data.starts_with(LZFSE_MAGIC_PREFIX) {
Some(Self::Lzfse)
} else {
None
}
}
pub(super) fn decompress(self, data: &[u8]) -> Result<Vec<u8>> {
match self {
Self::Lzfse => decompress_lzfse(data),
Self::Complzss => decompress_complzss(data),
}
}
}
impl fmt::Display for Compression {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str(match self {
Self::Lzfse => "LZFSE",
Self::Complzss => "complzss",
})
}
}
fn decompress_lzfse(data: &[u8]) -> Result<Vec<u8>> {
let size = lzfse_decoded_size(data)?;
let mut output = vec![0; size + 1];
let decoded = lzfse::decode_buffer(data, &mut output)
.map_err(|error| Error::parse(0, format!("invalid LZFSE stream: {error:?}")))?;
if decoded != size {
return Err(Error::parse(
0,
"LZFSE decoded size disagrees with block headers",
));
}
output.truncate(decoded);
Ok(output)
}
fn lzfse_decoded_size(data: &[u8]) -> Result<usize> {
let mut position = 0;
let mut total = 0usize;
loop {
let magic = slice(data, position, 4)?;
if magic == LZFSE_END_OF_STREAM {
if position + 4 != data.len() || total == 0 {
return Err(Error::parse(
position,
"empty LZFSE stream or trailing bytes",
));
}
return Ok(total);
}
let decoded = read_u32(data, position + 4)? as usize;
let block_size = lzfse_block_size(data, position, magic, decoded)?;
total = total
.checked_add(decoded)
.filter(|&total| total <= MAX_SIZE)
.ok_or_else(|| Error::parse(position, "LZFSE output exceeds 1 GiB"))?;
slice(data, position, block_size)?;
position += block_size;
}
}
fn lzfse_block_size(data: &[u8], position: usize, magic: &[u8], decoded: usize) -> Result<usize> {
let (header, payload) = match magic {
LZFSE_UNCOMPRESSED_BLOCK => (UNCOMPRESSED_BLOCK_HEADER_SIZE, decoded),
LZVN_BLOCK => (
LZVN_BLOCK_HEADER_SIZE,
read_u32(data, position + 8)? as usize,
),
LZFSE_V1_BLOCK => (
LZFSE_V1_BLOCK_HEADER_SIZE,
read_u32(data, position + 8)? as usize,
),
LZFSE_V2_BLOCK => {
slice(data, position, *LZFSE_V2_BLOCK_HEADER_SIZES.start())?;
let header = read_u32(data, position + 24)? as usize;
if !LZFSE_V2_BLOCK_HEADER_SIZES.contains(&header) {
return Err(Error::parse(position, "invalid LZFSE v2 header size"));
}
let literals = (read_u64(data, position + 8)? >> 20) & 0xf_ffff;
let lmds = (read_u64(data, position + 16)? >> 40) & 0xf_ffff;
(header, (literals + lmds) as usize)
}
_ => return Err(Error::parse(position, "unknown LZFSE block magic")),
};
header
.checked_add(payload)
.ok_or_else(|| Error::parse(position, "LZFSE block size overflow"))
}
fn decompress_complzss(data: &[u8]) -> Result<Vec<u8>> {
slice(data, 0, COMPLZSS_HEADER_SIZE)?;
let decoded_size = read_u32_be(data, COMPLZSS_DECODED_SIZE_OFFSET)? as usize;
if decoded_size > MAX_SIZE {
return Err(Error::parse(
COMPLZSS_DECODED_SIZE_OFFSET,
"complzss output exceeds 1 GiB",
));
}
let encoded_size = read_u32_be(data, COMPLZSS_ENCODED_SIZE_OFFSET)? as usize;
let encoded = slice(data, COMPLZSS_HEADER_SIZE, encoded_size)?;
let output = LzssDecoder::new(encoded, decoded_size).decode()?;
if adler32(&output) != read_u32_be(data, COMPLZSS_CHECKSUM_OFFSET)? {
return Err(Error::parse(
COMPLZSS_CHECKSUM_OFFSET,
"complzss Adler-32 mismatch",
));
}
Ok(output)
}
struct LzssDecoder<'a> {
input: &'a [u8],
position: usize,
output: Vec<u8>,
expected: usize,
window: [u8; LZSS_WINDOW_SIZE],
cursor: usize,
}
impl<'a> LzssDecoder<'a> {
fn new(input: &'a [u8], expected: usize) -> Self {
let capacity = expected.min(input.len().saturating_mul(9));
Self {
input,
position: 0,
output: Vec::with_capacity(capacity),
expected,
window: [b' '; LZSS_WINDOW_SIZE],
cursor: LZSS_WINDOW_SIZE - LZSS_MAX_MATCH,
}
}
fn decode(mut self) -> Result<Vec<u8>> {
while self.output.len() < self.expected {
let flags = self.next_byte()?;
for bit in 0..8 {
if self.output.len() == self.expected {
break;
}
if flags & (1 << bit) != 0 {
let literal = self.next_byte()?;
self.emit(literal);
} else {
self.copy_back_reference()?;
}
}
}
if self.position != self.input.len() {
return Err(Error::parse(
self.position,
"trailing complzss compressed bytes",
));
}
Ok(self.output)
}
fn next_byte(&mut self) -> Result<u8> {
let [byte] = read_bytes(self.input, self.position)?;
self.position += 1;
Ok(byte)
}
fn copy_back_reference(&mut self) -> Result<()> {
let [low, high] = read_bytes(self.input, self.position)?;
self.position += 2;
let start = usize::from(low) | (usize::from(high & 0xf0) << 4);
let len = usize::from(high & 0x0f) + LZSS_MIN_MATCH;
if self.output.len() + len > self.expected {
return Err(Error::parse(
self.position,
"complzss match exceeds declared output",
));
}
for index in 0..len {
self.emit(self.window[(start + index) % LZSS_WINDOW_SIZE]);
}
Ok(())
}
fn emit(&mut self, byte: u8) {
self.output.push(byte);
self.window[self.cursor] = byte;
self.cursor = (self.cursor + 1) % LZSS_WINDOW_SIZE;
}
}
fn adler32(data: &[u8]) -> u32 {
const MODULUS: u32 = 65_521;
const BLOCK: usize = 5_552;
let (mut a, mut b) = (1u32, 0u32);
for block in data.chunks(BLOCK) {
for &byte in block {
a += u32::from(byte);
b += a;
}
a %= MODULUS;
b %= MODULUS;
}
(b << 16) | a
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn adler32_matches_reference_values() {
assert_eq!(adler32(b""), 1);
assert_eq!(adler32(b"Wikipedia"), 0x11e6_0398);
let long = vec![0xff; 3 * 5_552 + 17];
let (mut a, mut b) = (1u32, 0u32);
for &byte in &long {
a = (a + u32::from(byte)) % 65_521;
b = (b + a) % 65_521;
}
assert_eq!(adler32(&long), (b << 16) | a);
}
#[test]
fn detects_compression_by_magic() {
assert_eq!(
Compression::detect(b"complzss..."),
Some(Compression::Complzss)
);
assert_eq!(Compression::detect(b"bvx2...."), Some(Compression::Lzfse));
assert_eq!(Compression::detect(&[0xcf, 0xfa, 0xed, 0xfe]), None);
}
}