use super::{Algorithm, Error};
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,
}
}
const LENGTH_OVERFLOWS: Error = malformed("a length extension overflows");
struct Decoder<'a> {
input: &'a [u8],
read: usize,
out: &'a mut [u8],
written: usize,
}
#[derive(Clone, Copy)]
enum Copied {
None,
Few,
Many,
}
impl Copied {
const fn after(count: usize) -> Self {
match count {
0 => Copied::None,
1..=3 => Copied::Few,
_ => Copied::Many,
}
}
}
enum Instruction {
Literals(usize),
Copy {
distance: usize,
length: usize,
literals: usize,
},
End,
}
impl Decoder<'_> {
fn run(mut self) -> Result<usize, Error> {
let mut copied = self.opening()?;
loop {
copied = match self.instruction(copied)? {
Instruction::Literals(count) => {
self.literals(count)?;
Copied::after(count)
}
Instruction::Copy {
distance,
length,
literals,
} => {
self.repeat(distance, length)?;
self.literals(literals)?;
Copied::after(literals)
}
Instruction::End if self.read == self.input.len() => return Ok(self.written),
Instruction::End => return Err(malformed("bytes follow the end of the stream")),
};
}
}
fn opening(&mut self) -> Result<Copied, Error> {
match self.input.first() {
Some(&first) if first >= 18 => {
self.read += 1;
let count = usize::from(first - 17);
self.literals(count)?;
Ok(Copied::after(count))
}
_ => Ok(Copied::None),
}
}
fn instruction(&mut self, copied: Copied) -> Result<Instruction, Error> {
let first = self.byte()?;
let bits = usize::from(first);
Ok(match first {
0..=15 if matches!(copied, Copied::None) => {
Instruction::Literals(self.length(bits, 4, 3)?)
}
0..=15 => {
let high = usize::from(self.byte()?);
let near = (high << 2) + ((bits >> 2) & 3);
let (distance, length) = if matches!(copied, Copied::Few) {
(near + 1, 2)
} else {
(near + 2049, 3)
};
Instruction::Copy {
distance,
length,
literals: bits & 3,
}
}
16..=31 => {
let length = self.length(bits, 3, 2)?;
let word = self.word()?;
let distance = 16384 + (((bits >> 3) & 1) << 14) + (word >> 2);
if distance == 16384 {
return Ok(Instruction::End);
}
Instruction::Copy {
distance,
length,
literals: word & 3,
}
}
32..=63 => {
let length = self.length(bits, 5, 2)?;
let word = self.word()?;
Instruction::Copy {
distance: (word >> 2) + 1,
length,
literals: word & 3,
}
}
64..=127 => Instruction::Copy {
distance: self.far(bits)?,
length: 3 + ((bits >> 5) & 1),
literals: bits & 3,
},
128..=255 => Instruction::Copy {
distance: self.far(bits)?,
length: 5 + ((bits >> 5) & 3),
literals: bits & 3,
},
})
}
fn far(&mut self, bits: usize) -> Result<usize, Error> {
let high = usize::from(self.byte()?);
Ok((high << 3) + ((bits >> 2) & 7) + 1)
}
fn length(&mut self, bits: usize, width: u32, base: usize) -> Result<usize, Error> {
let largest = (1usize << width) - 1;
let field = match bits & largest {
0 => largest
.checked_add(self.extension()?)
.ok_or(LENGTH_OVERFLOWS)?,
field => field,
};
field.checked_add(base).ok_or(LENGTH_OVERFLOWS)
}
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 word(&mut self) -> Result<usize, Error> {
let low = self.byte()?;
let high = self.byte()?;
Ok(usize::from(u16::from_le_bytes([low, high])))
}
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(LENGTH_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 repeat(&mut self, distance: usize, count: usize) -> Result<(), Error> {
if distance == 0 || distance > self.written {
return Err(malformed(
"a copy 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(),
});
}
super::copy_back(self.out, self.written, distance, count);
self.written += count;
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_copy_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 { .. })
));
}
const ABCD: [u8; 5] = [17 + 4, b'a', b'b', b'c', b'd'];
fn decoded(stream: &[u8], room: usize) -> Vec<u8> {
let mut out = vec![0u8; room];
let produced = decompress(stream, &mut out).expect("the stream decodes");
out.truncate(produced);
out
}
fn long_run(count: usize) -> Vec<u8> {
let mut extension = count - 3 - 15;
let mut stream = vec![0x00];
while extension > 255 {
stream.push(0);
extension -= 255;
}
stream.push(extension as u8);
stream.extend((0..count).map(|at| (at * 7 + 1) as u8));
stream
}
#[test]
fn every_row_of_the_table_reads_as_the_page_gives_it() {
let end = [0x11, 0x00, 0x00];
let stream = [&ABCD[..], &[0b1110_0000, 0], &end].concat();
assert_eq!(decoded(&stream, 64), b"abcddddddddd");
let stream = [&ABCD[..], &[0b0110_1110, 0, b'x', b'y', 0x00, 0], &end].concat();
assert_eq!(decoded(&stream, 64), b"abcdabcdxyyy");
let stream = [&ABCD[..], &[0x21, 3 << 2, 0], &end].concat();
assert_eq!(decoded(&stream, 64), b"abcdabc");
let stream = [&ABCD[..], &[0x20, 1, 0, 0], &end].concat();
let mut want = b"abcd".to_vec();
want.extend([b'd'; 34]);
assert_eq!(decoded(&stream, 64), want);
assert_eq!(decoded(&[18, b'a', 0x00, 0, 0x11, 0, 0], 8), b"aaa");
let run = long_run(2051);
let stream = [&run[..], &[0b0000_0100, 0], &end].concat();
let produced = decoded(&stream, 4096);
assert_eq!(produced.len(), 2054);
assert_eq!(produced[2051..], produced[1..4]);
for (instruction, back) in [(0x11u8, 16_385usize), (0x19, 32_769)] {
let run = long_run(back + 1);
let stream = [&run[..], &[instruction, 1 << 2, 0], &end].concat();
let produced = decoded(&stream, back + 4);
assert_eq!(produced[back + 1..], produced[1..4], "{instruction:#04x}");
}
}
#[test]
fn the_stream_ends_at_the_distance_the_page_gives() {
for ending in [
&[0x11u8, 0x00, 0x00][..],
&[0x11, 0x01, 0x00],
&[0x11, 0x03, 0x00],
&[0x12, 0x00, 0x00],
&[0x17, 0x02, 0x00],
&[0x10, 0x01, 0x00, 0x00],
] {
let stream = [&ABCD[..], ending].concat();
assert_eq!(decoded(&stream, 64), b"abcd", "{ending:02x?}");
}
let mut out = [0u8; 64];
for stream in [
[&ABCD[..], &[0x19, 0x00, 0x00]].concat(),
[&ABCD[..], &[0x11, 0x00, 0x00, 0x00]].concat(),
[&ABCD[..], &[0x11, 0x00, 0x00], &ABCD[..]].concat(),
] {
assert!(
matches!(decompress(&stream, &mut out), Err(Error::Malformed { .. })),
"{stream:02x?}"
);
}
for header in [
&[0x11u8, 0x01, 0x00, 0x00, 0x00][..],
&[0x11, 0x01, 0x04, 0x11, 0, 0],
] {
assert!(matches!(
decompress(header, &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);
}
}