const MAX_WIDTH: u8 = 12;
const TABLE_CODES: u16 = 1 << MAX_WIDTH;
pub(super) fn compress(indices: &[u8], min_code_size: u8) -> Vec<u8> {
let clear = 1_u16 << min_code_size;
let end = clear + 1;
let mut out = BitWriter::default();
let mut table = Table::new();
let mut width = min_code_size + 1;
let mut next = end + 1;
out.write(clear, width);
let mut rest = indices.iter();
let Some(&first) = rest.next() else {
out.write(end, width);
return out.finish();
};
let mut prefix = u16::from(first);
for &index in rest {
let key = u32::from(prefix) << 8 | u32::from(index);
if let Some(code) = table.get(key) {
prefix = code;
continue;
}
out.write(prefix, width);
if next == TABLE_CODES {
out.write(clear, width);
table.clear();
width = min_code_size + 1;
next = end + 1;
} else {
table.insert(key, next);
if next == 1 << width && width < MAX_WIDTH {
width += 1;
}
next += 1;
}
prefix = u16::from(index);
}
out.write(prefix, width);
out.write(end, width);
out.finish()
}
#[derive(Default)]
struct BitWriter {
bytes: Vec<u8>,
pending: u32,
bits: u8,
}
impl BitWriter {
fn write(&mut self, code: u16, width: u8) {
self.pending |= u32::from(code) << self.bits;
self.bits += width;
while self.bits >= 8 {
self.bytes.push(self.pending.to_le_bytes()[0]);
self.pending >>= 8;
self.bits -= 8;
}
}
fn finish(mut self) -> Vec<u8> {
if self.bits > 0 {
self.bytes.push(self.pending.to_le_bytes()[0]);
}
self.bytes
}
}
struct Table {
keys: Vec<u32>,
codes: Vec<u16>,
}
impl Table {
const SLOTS: usize = 2 * TABLE_CODES as usize;
const EMPTY: u32 = u32::MAX;
fn new() -> Self {
Self {
keys: vec![Self::EMPTY; Self::SLOTS],
codes: vec![0; Self::SLOTS],
}
}
fn clear(&mut self) {
self.keys.fill(Self::EMPTY);
}
fn slot(&self, key: u32) -> usize {
let hash = key.wrapping_mul(0x9E37_79B9) >> 19;
let mut slot = hash as usize;
while self.keys[slot] != key && self.keys[slot] != Self::EMPTY {
slot = (slot + 1) % Self::SLOTS;
}
slot
}
fn get(&self, key: u32) -> Option<u16> {
let slot = self.slot(key);
(self.keys[slot] == key).then(|| self.codes[slot])
}
fn insert(&mut self, key: u32, code: u16) {
let slot = self.slot(key);
self.keys[slot] = key;
self.codes[slot] = code;
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(super) enum LzwError {
InvalidCodeSize,
InvalidCode,
Truncated,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(super) enum Finish {
Complete,
EndCode,
}
pub(super) fn decompress(
bytes: impl IntoIterator<Item = u8>,
min_code_size: u8,
mut sink: impl FnMut(u8) -> bool,
) -> Result<Finish, LzwError> {
if min_code_size > MAX_WIDTH {
return Err(LzwError::InvalidCodeSize);
}
let clear = 1_u16 << min_code_size;
let end = clear + 1;
let mut bytes = bytes.into_iter();
let (mut buffer, mut buffered) = (0_u32, 0_u8);
let mut links = vec![0_u16; usize::from(TABLE_CODES)];
let mut suffixes = vec![0_u8; usize::from(TABLE_CODES)];
let mut string: Vec<u8> = Vec::with_capacity(usize::from(TABLE_CODES));
let mut width = min_code_size + 1;
let mut next = end + 1;
let mut previous: Option<(u16, u8)> = None;
loop {
while buffered < width {
let byte = bytes.next().ok_or(LzwError::Truncated)?;
buffer |= u32::from(byte) << buffered;
buffered += 8;
}
let code = u16::try_from(buffer & ((1 << width) - 1)).expect("at most 13 bits");
buffer >>= width;
buffered -= width;
if code == clear {
if previous.is_some() {
width = min_code_size + 1;
next = end + 1;
previous = None;
}
continue;
}
if code == end {
return Ok(Finish::EndCode);
}
string.clear();
let first = match previous {
None if code > clear => return Err(LzwError::InvalidCode),
None => code as u8,
Some((last_code, last_first)) => {
if code > next {
return Err(LzwError::InvalidCode);
}
let mut walk = code;
if code == next {
string.push(last_first);
walk = last_code;
}
while walk >= clear {
if string.len() >= usize::from(TABLE_CODES) || walk >= TABLE_CODES {
return Err(LzwError::InvalidCode);
}
string.push(suffixes[usize::from(walk)]);
walk = links[usize::from(walk)];
}
let first = walk as u8;
if next < TABLE_CODES {
suffixes[usize::from(next)] = first;
links[usize::from(next)] = last_code;
if next == (1 << width) - 1 && width < MAX_WIDTH {
width += 1;
}
next += 1;
}
first
}
};
previous = Some((code, first));
if sink(first) {
return Ok(Finish::Complete);
}
for &index in string.iter().rev() {
if sink(index) {
return Ok(Finish::Complete);
}
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::test_util::Rng;
fn unpack(packed: &[u8], min_code_size: u8) -> Result<(Vec<u8>, Finish), LzwError> {
let mut indices = Vec::new();
let finish = decompress(packed.iter().copied(), min_code_size, |index| {
indices.push(index);
false
})?;
Ok((indices, finish))
}
fn round_trip(indices: &[u8], min_code_size: u8) {
let packed = compress(indices, min_code_size);
assert_eq!(
unpack(&packed, min_code_size),
Ok((indices.to_vec(), Finish::EndCode)),
"{} indices at {min_code_size} bits",
indices.len()
);
}
#[test]
fn empty_and_tiny_inputs() {
round_trip(&[], 2);
round_trip(&[3], 2);
round_trip(&[0, 0, 0, 0, 0, 0, 0], 2);
assert_eq!(compress(&[], 2), [0b0010_1100], "clear (4), end (5)");
}
#[test]
fn runs_fill_and_restart_the_table() {
round_trip(&vec![7; 200_000], 8);
let mut rng = Rng::new(7);
for bits in 2..=8 {
let alphabet = 1 << bits;
let noise: Vec<u8> = (0..60_000)
.map(|_| u8::try_from(rng.below(alphabet)).unwrap())
.collect();
round_trip(&noise, bits);
}
}
#[test]
fn repetitive_images_compress_well() {
let stripes: Vec<u8> = (0..100_000).map(|i| u8::from(i % 640 < 320)).collect();
assert!(compress(&stripes, 2).len() < stripes.len() / 20);
round_trip(&stripes, 2);
}
#[test]
fn a_complete_image_stops_decoding() {
let packed = compress(&[1, 2, 3, 1, 2, 3], 2);
let mut seen = Vec::new();
let finish = decompress(packed.iter().copied(), 2, |index| {
seen.push(index);
seen.len() == 4
});
assert_eq!(finish, Ok(Finish::Complete));
assert_eq!(seen, [1, 2, 3, 1]);
}
#[test]
fn malformed_streams_are_errors() {
assert_eq!(unpack(&[], 2), Err(LzwError::Truncated));
assert_eq!(unpack(&[0xFF], 13), Err(LzwError::InvalidCodeSize));
assert_eq!(
unpack(&[0b1100_1100, 0b0000_0001], 2),
Err(LzwError::InvalidCode)
);
assert_eq!(unpack(&[0b0000_0110], 2), Err(LzwError::InvalidCode));
let mut rng = Rng::new(3);
for _ in 0..2000 {
let len = rng.below(64);
let noise = rng.bytes(len);
let bits = u8::try_from(rng.below(13)).unwrap();
let mut count = 0_usize;
let _ = decompress(noise.iter().copied(), bits, |_| {
count += 1;
count > 100_000
});
}
}
}