use super::{Algorithm, Error};
const M2_MAX_OFFSET: usize = 0x0800;
const M4_DISTANCE_BIAS: usize = 0x4000;
const MIN_STREAM: usize = 3;
const END_MARKER_LENGTH: usize = 3;
pub(crate) fn decompress(input: &[u8], out: &mut [u8]) -> Result<usize, Error> {
Decoder {
input,
read: 0,
out,
written: 0,
}
.run()
}
const fn malformed(fault: &'static str) -> Error {
Error::Malformed {
algorithm: Algorithm::Lzo,
fault,
}
}
struct Decoder<'a> {
input: &'a [u8],
read: usize,
out: &'a mut [u8],
written: usize,
}
const STATE_AFTER_LITERAL_RUN: usize = 4;
impl Decoder<'_> {
fn run(mut self) -> Result<usize, Error> {
if self.input.len() < MIN_STREAM {
return Err(malformed("a stream is at least an end marker"));
}
let mut state = 0usize;
if self.input[0] > 17 {
let count = self.byte()? as usize - 17;
if count < STATE_AFTER_LITERAL_RUN {
state = count;
self.literals(count)?;
} else {
self.literals(count)?;
state = STATE_AFTER_LITERAL_RUN;
}
}
loop {
let instruction = self.byte()? as usize;
let (distance, length, next) = if instruction < 16 {
match state {
0 => {
let count = if instruction == 0 {
15 + self.extension()?
} else {
instruction
} + 3;
self.literals(count)?;
state = STATE_AFTER_LITERAL_RUN;
continue;
}
STATE_AFTER_LITERAL_RUN => {
let next = instruction & 3;
let far = self.byte()? as usize;
let distance = 1 + M2_MAX_OFFSET + (instruction >> 2) + (far << 2);
(distance, 3, next)
}
_ => {
let next = instruction & 3;
let far = self.byte()? as usize;
let distance = 1 + (instruction >> 2) + (far << 2);
(distance, 2, next)
}
}
} else if instruction >= 64 {
let far = self.byte()? as usize;
(
1 + ((instruction >> 2) & 7) + (far << 3),
(instruction >> 5) + 1,
instruction & 3,
)
} else if instruction >= 32 {
let mut length = (instruction & 31) + 2;
if length == 2 {
length += 31 + self.extension()?;
}
let pair = self.pair()?;
(1 + (pair >> 2), length, pair & 3)
} else {
let mut length = (instruction & 7) + 2;
if length == 2 {
length += 7 + self.extension()?;
}
let pair = self.pair()?;
let distance = ((instruction & 8) << 11) + (pair >> 2);
if distance == 0 {
if length != END_MARKER_LENGTH {
return Err(malformed("the end marker carries a length that is not its"));
}
if self.read != self.input.len() {
return Err(malformed("bytes follow the end of the stream"));
}
return Ok(self.written);
}
(distance + M4_DISTANCE_BIAS, length, pair & 3)
};
self.copy_match(distance, length)?;
state = next;
self.literals(next)?;
}
}
fn byte(&mut self) -> Result<u8, Error> {
let byte = *self
.input
.get(self.read)
.ok_or(malformed("an instruction reads past the end of the stream"))?;
self.read += 1;
Ok(byte)
}
fn pair(&mut self) -> Result<usize, Error> {
let low = self.byte()? as usize;
let high = self.byte()? as usize;
Ok(low | (high << 8))
}
fn extension(&mut self) -> Result<usize, Error> {
let mut total = 0usize;
loop {
let byte = self.byte()?;
let step = if byte == 0 { 255 } else { byte as usize };
total = total
.checked_add(step)
.ok_or(malformed("a length extension overflows"))?;
if byte != 0 {
return Ok(total);
}
}
}
fn literals(&mut self, count: usize) -> Result<(), Error> {
let from = self
.read
.checked_add(count)
.and_then(|end| self.input.get(self.read..end))
.ok_or(malformed("a literal run reads past the end of the stream"))?;
let overrun = Error::Overrun {
algorithm: Algorithm::Lzo,
expected: self.out.len(),
};
let into = self
.written
.checked_add(count)
.and_then(|end| self.out.get_mut(self.written..end))
.ok_or(overrun)?;
into.copy_from_slice(from);
self.read += count;
self.written += count;
Ok(())
}
fn copy_match(&mut self, distance: usize, count: usize) -> Result<(), Error> {
if distance > self.written {
return Err(malformed(
"a match names bytes before the start of the output",
));
}
if count > self.out.len() - self.written {
return Err(Error::Overrun {
algorithm: Algorithm::Lzo,
expected: self.out.len(),
});
}
for from in (self.written - distance..).take(count) {
self.out[self.written] = self.out[from];
self.written += 1;
}
Ok(())
}
}
#[cfg(test)]
mod tests {
use super::*;
const END: &[u8] = &[0x11, 0x00, 0x00];
fn foreign(data: &[u8]) -> Vec<u8> {
lzokay::compress::compress(data).expect("a second implementation compresses it")
}
fn round_trip(data: &[u8]) {
let stream = foreign(data);
let mut out = vec![0u8; data.len()];
let produced = decompress(&stream, &mut out)
.unwrap_or_else(|e| panic!("{} bytes did not decode: {e}", data.len()));
assert_eq!(produced, data.len(), "short by {}", data.len() - produced);
assert_eq!(out, data);
}
#[test]
fn an_empty_run_is_the_end_marker_and_nothing_else() {
let mut out = [0u8; 8];
assert_eq!(decompress(END, &mut out), Ok(0));
assert!(matches!(
decompress(&END[..2], &mut out),
Err(Error::Malformed { .. })
));
assert!(matches!(
decompress(&[0x11, 0x11, 0x00, 0x00], &mut out),
Err(Error::Malformed { .. })
));
assert_eq!(foreign(b""), [0x11, 0x11, 0x00, 0x00]);
}
#[test]
fn runs_a_second_implementation_produced_decode_to_what_went_in() {
round_trip(b"f");
round_trip(b"ferrosys");
round_trip(&b"ferrosys".repeat(4096));
round_trip(&vec![0x5au8; 70_000]);
for gap in [1000usize, 5000, 40_000] {
let block = b"a-block-worth-matching-against-later";
let filler: Vec<u8> = (0..gap).map(|at| (at * 181 + 3) as u8).collect();
let mut data = Vec::new();
data.extend_from_slice(block);
data.extend_from_slice(&filler);
data.extend_from_slice(block);
round_trip(&data);
}
for len in [1usize, 2, 3, 4, 17, 18, 19, 33, 34, 255, 256, 257, 512] {
let data: Vec<u8> = (0..len).map(|at| (at * 7 + 13) as u8).collect();
round_trip(&data);
round_trip(&vec![0xa5u8; len]);
}
}
#[test]
fn a_run_of_every_length_up_to_a_kibibyte_survives_the_round_trip() {
for len in 1..1024usize {
round_trip(&vec![0xc3u8; len]);
let data: Vec<u8> = (0..len).map(|at| (at * 31 + 7) as u8).collect();
round_trip(&data);
}
}
#[test]
fn a_stream_that_expands_past_the_room_it_was_given_is_refused() {
let data = b"ferrosys".repeat(64);
let stream = foreign(&data);
let mut out = vec![0u8; data.len() - 1];
assert!(matches!(
decompress(&stream, &mut out),
Err(Error::Overrun { .. })
));
}
#[test]
fn a_match_that_reaches_before_the_start_of_the_output_is_refused() {
let stream = [0x21, 0x04, 0x00];
let mut out = [0u8; 16];
assert!(matches!(
decompress(&stream, &mut out),
Err(Error::Malformed { .. })
));
}
#[test]
fn a_length_extension_that_never_ends_is_bounded_by_the_input() {
let mut stream = vec![0u8; 4096];
stream[0] = 0;
let mut out = [0u8; 64];
assert!(matches!(
decompress(&stream, &mut out),
Err(Error::Malformed { .. })
));
}
#[test]
fn arbitrary_bytes_never_panic_and_never_write_past_the_room_they_were_given() {
crate::compress::sweep_arbitrary_bytes(1, decompress);
}
}