const CLEAR: u16 = 256;
const END: u16 = 257;
const FIRST: u16 = 258;
const ENTRIES: usize = 4095 + 1024;
const MAX_BITS: u32 = 12;
struct Table {
prefix: Vec<u16>,
last: Vec<u8>,
first: Vec<u8>,
length: Vec<u16>,
}
impl Table {
fn new() -> Self {
let mut table = Self {
prefix: vec![0; ENTRIES],
last: vec![0; ENTRIES],
first: vec![0; ENTRIES],
length: vec![0; ENTRIES],
};
for (code, byte) in (0..256).zip(0..=255) {
table.last[code] = byte;
table.first[code] = byte;
table.length[code] = 1;
}
table
}
fn write(&self, code: usize, room: usize, out: &mut Vec<u8>) {
let length = usize::from(self.length[code]);
let start = out.len();
out.resize(start + length.min(room), 0);
let mut entry = code;
for at in (0..length).rev() {
if at < room {
out[start + at] = self.last[entry];
}
entry = usize::from(self.prefix[entry]);
}
}
}
struct Codes<'a> {
data: &'a [u8],
pos: usize,
buffer: u32,
buffered: u32,
msb_first: bool,
}
impl Codes<'_> {
fn next(&mut self, bits: u32) -> Option<u16> {
while self.buffered < bits {
let byte = u32::from(*self.data.get(self.pos)?);
self.pos += 1;
if self.msb_first {
self.buffer = self.buffer << 8 | byte;
} else {
self.buffer |= byte << self.buffered;
}
self.buffered += 8;
}
self.buffered -= bits;
let mask = (1 << bits) - 1;
let code = if self.msb_first {
(self.buffer >> self.buffered) & mask
} else {
let code = self.buffer & mask;
self.buffer >>= bits;
code
};
Some(u16::try_from(code).expect("at most 12 bits"))
}
}
pub(super) fn decompress(data: &[u8], expected: usize) -> Option<Vec<u8>> {
let old_style = data.len() >= 2 && data[0] == 0 && data[1] & 1 == 1;
let mut codes = Codes {
data,
pos: 0,
buffer: 0,
buffered: 0,
msb_first: !old_style,
};
let early = u16::from(!old_style);
let mut table = Table::new();
let mut out = Vec::with_capacity(expected);
let mut bits = 9;
let mut next: Option<u16> = None;
let mut previous = 0_u16;
while out.len() < expected {
let code = codes.next(bits)?;
match code {
END => return None,
CLEAR => {
let mut code = CLEAR;
while code == CLEAR {
code = codes.next(9)?;
}
if code >= END {
return None;
}
table.length[usize::from(FIRST)..].fill(0);
bits = 9;
next = Some(FIRST);
out.push(u8::try_from(code).expect("below 256"));
previous = code;
}
_ => {
let free = next?;
if code > free || table.length[usize::from(code)] == 0 && code != free {
return None;
}
let entry = usize::from(free);
let old = usize::from(previous);
table.prefix[entry] = previous;
table.first[entry] = table.first[old];
table.length[entry] = table.length[old] + 1;
table.last[entry] = if code == free {
table.first[old]
} else {
table.first[usize::from(code)]
};
let grown = free + 1;
next = (usize::from(grown) < ENTRIES).then_some(grown);
if grown > (1 << bits) - 1 - early && bits < MAX_BITS {
bits += 1;
}
previous = code;
table.write(usize::from(code), expected - out.len(), &mut out);
}
}
}
Some(out)
}
#[cfg(test)]
mod tests {
use super::*;
fn pack(codes: &[(u16, u32)]) -> Vec<u8> {
let (mut out, mut buffer, mut bits) = (Vec::new(), 0_u64, 0);
for &(code, width) in codes {
buffer = buffer << width | u64::from(code);
bits += width;
while bits >= 8 {
bits -= 8;
out.push((buffer >> bits) as u8);
}
}
if bits > 0 {
out.push((buffer << (8 - bits)) as u8);
}
out
}
#[test]
fn strings_build_up() {
let data = pack(&[(256, 9), (65, 9), (66, 9), (258, 9), (260, 9), (257, 9)]);
assert_eq!(decompress(&data, 7).as_deref(), Some(&b"ABABABA"[..]));
assert_eq!(
decompress(&data, 4).as_deref(),
Some(&b"ABAB"[..]),
"cut short"
);
assert_eq!(decompress(&data, 8), None, "ends early");
}
#[test]
fn corrupt_streams_are_rejected() {
assert_eq!(
decompress(&pack(&[(65, 9)]), 1),
None,
"no clear code first"
);
assert_eq!(decompress(&pack(&[(256, 9), (300, 9)]), 1), None);
assert_eq!(decompress(&pack(&[(256, 9), (65, 9), (300, 9)]), 3), None);
assert_eq!(decompress(&[], 1), None);
let mut rng = crate::test_util::Rng::new(5);
for _ in 0..2000 {
let len = rng.below(80);
let mut noise = rng.bytes(len);
if let Some(first) = noise.first_mut() {
*first = 0x80;
}
let _ = decompress(&noise, rng.below(5000));
}
}
}