use super::bit_reader::BitReader;
use super::format::{CODE_LENGTH_CODES, CODE_LENGTH_ORDER};
use crate::webp::DecodeError;
const ROOT_BITS: u32 = 8;
const MAX_LENGTH: u32 = 15;
const DEFAULT_LENGTH: u8 = 8;
#[derive(Clone, Copy, Debug, Default)]
pub(super) struct Entry {
length: u8,
value: u16,
}
#[derive(Clone, Debug)]
pub(super) enum PrefixCode {
Single(u16),
Table(Vec<Entry>),
}
impl PrefixCode {
pub(super) fn from_lengths(lengths: &[u8]) -> Result<Self, DecodeError> {
let mut counts = [0usize; MAX_LENGTH as usize + 1];
for &length in lengths {
counts[usize::from(length)] += 1;
}
let mut used = lengths
.iter()
.enumerate()
.filter(|&(_, &length)| length > 0);
match (used.next(), used.next()) {
(None, _) => return Err(DecodeError::InvalidPrefixCode),
(Some((symbol, _)), None) => return Ok(Self::Single(symbol as u16)),
_ => {}
}
let mut open: i64 = 1;
for &count in &counts[1..] {
open = 2 * open - count as i64;
if open < 0 {
return Err(DecodeError::InvalidPrefixCode);
}
}
if open != 0 {
return Err(DecodeError::InvalidPrefixCode);
}
Ok(Self::Table(build_table(lengths, &counts)))
}
pub(super) fn read_symbol(&self, reader: &mut BitReader<'_>) -> u16 {
let table = match self {
Self::Single(symbol) => return *symbol,
Self::Table(table) => table,
};
let bits = reader.peek(MAX_LENGTH);
let root = table[(bits & ((1 << ROOT_BITS) - 1)) as usize];
if u32::from(root.length) <= ROOT_BITS {
reader.consume(u32::from(root.length));
return root.value;
}
let sub_bits = u32::from(root.length) - ROOT_BITS;
let index =
usize::from(root.value) + ((bits >> ROOT_BITS) & ((1 << sub_bits) - 1)) as usize;
let entry = table[index];
reader.consume(ROOT_BITS + u32::from(entry.length));
entry.value
}
}
fn build_table(lengths: &[u8], counts: &[usize]) -> Vec<Entry> {
let mut next_code = [0u32; MAX_LENGTH as usize + 1];
let mut code = 0;
for length in 1..=MAX_LENGTH as usize {
code = (code
+ if length > 1 {
counts[length - 1] as u32
} else {
0
})
<< 1;
next_code[length] = code;
}
let codes: Vec<(u16, u32, u32)> = lengths
.iter()
.enumerate()
.filter(|&(_, &length)| length > 0)
.map(|(symbol, &length)| {
let length = u32::from(length);
let code = next_code[length as usize];
next_code[length as usize] += 1;
(symbol as u16, length, code.reverse_bits() >> (32 - length))
})
.collect();
let root_mask = (1 << ROOT_BITS) - 1;
let mut sub_bits = vec![0u32; 1 << ROOT_BITS];
for &(_, length, reversed) in &codes {
if length > ROOT_BITS {
let slot = &mut sub_bits[(reversed & root_mask) as usize];
*slot = (*slot).max(length - ROOT_BITS);
}
}
let mut table = vec![Entry::default(); 1 << ROOT_BITS];
for (root, &bits) in sub_bits.iter().enumerate() {
if bits > 0 {
table[root] = Entry {
length: (ROOT_BITS + bits) as u8,
value: table.len() as u16,
};
table.resize(table.len() + (1 << bits), Entry::default());
}
}
for (symbol, length, reversed) in codes {
if length <= ROOT_BITS {
let entry = Entry {
length: length as u8,
value: symbol,
};
for index in (reversed as usize..1 << ROOT_BITS).step_by(1 << length) {
table[index] = entry;
}
} else {
let link = table[(reversed & root_mask) as usize];
let start = usize::from(link.value);
let size = 1usize << (u32::from(link.length) - ROOT_BITS);
let entry = Entry {
length: (length - ROOT_BITS) as u8,
value: symbol,
};
let step = 1 << (length - ROOT_BITS);
for index in ((reversed >> ROOT_BITS) as usize..size).step_by(step) {
table[start + index] = entry;
}
}
}
table
}
pub(super) fn read_prefix_code(
reader: &mut BitReader<'_>,
alphabet_size: usize,
) -> Result<PrefixCode, DecodeError> {
let mut lengths = vec![0u8; alphabet_size];
if reader.flag() {
let two_symbols = reader.flag();
let first_bits = if reader.flag() { 8 } else { 1 };
let first = reader.read_usize(first_bits);
let second = two_symbols.then(|| reader.read_usize(8));
for symbol in std::iter::once(first).chain(second) {
if let Some(length) = lengths.get_mut(symbol) {
*length = 1;
}
}
} else {
let stored = reader.read_usize(4) + 4;
let mut code_length_lengths = [0u8; CODE_LENGTH_CODES];
for &symbol in &CODE_LENGTH_ORDER[..stored] {
code_length_lengths[symbol] = reader.read(3) as u8;
}
let code_length_code = PrefixCode::from_lengths(&code_length_lengths)?;
read_code_lengths(reader, &code_length_code, &mut lengths)?;
}
if reader.is_overrun() {
return Err(DecodeError::Truncated);
}
PrefixCode::from_lengths(&lengths)
}
fn read_code_lengths(
reader: &mut BitReader<'_>,
code: &PrefixCode,
lengths: &mut [u8],
) -> Result<(), DecodeError> {
let mut remaining = if reader.flag() {
let bits = 2 + 2 * reader.read(3);
let limit = 2 + reader.read_usize(bits);
if limit > lengths.len() {
return Err(DecodeError::InvalidPrefixCode);
}
limit
} else {
lengths.len()
};
let mut symbol = 0;
let mut previous = DEFAULT_LENGTH;
while symbol < lengths.len() && remaining > 0 {
remaining -= 1;
let length = code.read_symbol(reader) as u8;
if length < 16 {
lengths[symbol] = length;
symbol += 1;
if length != 0 {
previous = length;
}
continue;
}
let (extra_bits, offset, value) = match length {
16 => (2, 3, previous),
17 => (3, 3, 0),
_ => (7, 11, 0),
};
let repeat = reader.read_usize(extra_bits) + offset;
let run = lengths
.get_mut(symbol..symbol + repeat)
.ok_or(DecodeError::InvalidPrefixCode)?;
run.fill(value);
symbol += repeat;
}
Ok(())
}
#[cfg(test)]
mod tests {
use super::*;
fn pack(fields: &[(u32, u32)]) -> Vec<u8> {
let mut out = Vec::new();
let (mut buffer, mut count) = (0u64, 0);
for &(value, bits) in fields {
buffer |= u64::from(value) << count;
count += bits;
while count >= 8 {
out.push(buffer as u8);
buffer >>= 8;
count -= 8;
}
}
if count > 0 {
out.push(buffer as u8);
}
out
}
#[test]
fn canonical_codes_decode_their_symbols() {
let code = PrefixCode::from_lengths(&[1, 2, 3, 3]).unwrap();
let data = pack(&[(0b0, 1), (0b01, 2), (0b011, 3), (0b111, 3)]);
let mut reader = BitReader::new(&data);
let symbols: Vec<u16> = (0..4).map(|_| code.read_symbol(&mut reader)).collect();
assert_eq!(symbols, [0, 1, 2, 3]);
}
#[test]
fn long_codes_go_through_second_level_tables() {
let mut lengths: Vec<u8> = (1..=15).collect();
lengths.push(15);
let code = PrefixCode::from_lengths(&lengths).unwrap();
let data = pack(&[(0x7FFF, 15), (0x1FF, 10)]);
let mut reader = BitReader::new(&data);
assert_eq!(code.read_symbol(&mut reader), 15);
assert_eq!(code.read_symbol(&mut reader), 9);
assert!(!reader.is_overrun());
}
#[test]
fn degenerate_codes_are_rejected_but_single_symbols_take_no_bits() {
assert_eq!(
PrefixCode::from_lengths(&[0, 0]).unwrap_err(),
DecodeError::InvalidPrefixCode
);
assert!(PrefixCode::from_lengths(&[1, 2, 0]).is_err(), "incomplete");
assert!(
PrefixCode::from_lengths(&[1, 1, 1]).is_err(),
"over-subscribed"
);
let single = PrefixCode::from_lengths(&[0, 0, 7]).unwrap();
assert!(matches!(single, PrefixCode::Single(2)));
let mut reader = BitReader::new(&[]);
assert_eq!(single.read_symbol(&mut reader), 2);
assert!(!reader.is_overrun());
}
#[test]
fn simple_codes_ignore_symbols_past_the_alphabet() {
let data = pack(&[(1, 1), (1, 1), (1, 1), (3, 8), (200, 8)]);
let code = read_prefix_code(&mut BitReader::new(&data), 40).unwrap();
assert!(matches!(code, PrefixCode::Single(3)));
}
#[test]
fn code_lengths_repeat_and_stop_at_the_stored_limit() {
let mut code_length_lengths = [0; CODE_LENGTH_CODES];
code_length_lengths[1] = 1;
code_length_lengths[16] = 1;
let code = PrefixCode::from_lengths(&code_length_lengths).unwrap();
let data = pack(&[
(1, 1),
(0, 3),
(1, 2),
(0, 1),
(1, 1),
(3, 2),
(0, 1),
]);
let mut lengths = [0; 10];
read_code_lengths(&mut BitReader::new(&data), &code, &mut lengths).unwrap();
assert_eq!(lengths, [1, 1, 1, 1, 1, 1, 1, 1, 0, 0]);
}
}