#[cfg(feature = "alloc")]
use alloc::vec;
#[cfg(feature = "alloc")]
use alloc::vec::Vec;
use super::primitives;
use crate::bitstream::reader_reverse::ReverseBitReader;
use crate::error::DecompressError;
use crate::huffman::{
DECODE_TABLE_SIZE, HuffmanDecodeEntry, MAX_TABLE_LOG, PAIR_TABLE_LOG, PAIR_TABLE_SIZE,
};
pub fn decode_single_stream(
table: &[HuffmanDecodeEntry],
table_log: u8,
data: &[u8],
output_size: usize,
) -> Result<Vec<u8>, DecompressError> {
validate_decode_table(table, table_log)?;
let mut reader = ReverseBitReader::new(data).map_err(|_| DecompressError::BadHuffmanStream)?;
let mut output = Vec::with_capacity(output_size);
let tl = table_log as usize;
while output.len() + 4 <= output_size && reader.bits_remaining() >= tl + tl + tl + tl {
for _ in 0..4 {
let bits = reader.peek_bits(table_log);
let entry = primitives::huf_table_lookup(table, bits as usize);
output.push(entry.symbol);
reader.consume_bits(entry.num_bits);
}
}
while output.len() < output_size {
reader.refill();
let remaining = reader.bits_remaining();
if remaining == 0 {
return Err(DecompressError::BadHuffmanStream);
}
let bits = if remaining >= tl {
reader.peek_bits(table_log)
} else {
reader.peek_bits(remaining as u8) << (tl - remaining)
};
let entry = primitives::huf_table_lookup(table, bits as usize);
if entry.num_bits as usize > remaining {
return Err(DecompressError::BadHuffmanStream);
}
output.push(entry.symbol);
reader.bits_consumed += entry.num_bits as u32;
}
if reader.bits_remaining() != 0 {
return Err(DecompressError::BadHuffmanStream);
}
Ok(output)
}
pub fn decode_single_stream_into(
table: &[HuffmanDecodeEntry],
table_log: u8,
data: &[u8],
output: &mut [u8],
) -> Result<(), DecompressError> {
validate_decode_table(table, table_log)?;
let mut reader = ReverseBitReader::new(data).map_err(|_| DecompressError::BadHuffmanStream)?;
decode_stream_tail(table, table_log, &mut reader, output)
}
pub fn decode_single_stream_vec(
table: &[HuffmanDecodeEntry],
table_log: u8,
data: &[u8],
output_size: usize,
output: &mut Vec<u8>,
) -> Result<(), DecompressError> {
validate_decode_table(table, table_log)?;
prepare_output(output, output_size);
let result = decode_single_stream_into(table, table_log, data, output);
if result.is_err() {
output.clear();
}
result
}
pub fn decode_4_streams(
table: &[HuffmanDecodeEntry],
table_log: u8,
data: &[u8],
output_size: usize,
) -> Result<Vec<u8>, DecompressError> {
validate_decode_table(table, table_log)?;
let mut output = vec![0u8; output_size];
decode_4_streams_core_safe(table, table_log, None, data, output_size, &mut output)?;
Ok(output)
}
pub fn decode_4_streams_into(
table: &[HuffmanDecodeEntry],
table_log: u8,
data: &[u8],
output_size: usize,
output: &mut Vec<u8>,
) -> Result<(), DecompressError> {
decode_4_streams_with(table, table_log, None, data, output_size, output)
}
pub fn decode_4_streams_pairs_into(
table: &[HuffmanDecodeEntry],
table_log: u8,
pairs: &[u32],
data: &[u8],
output_size: usize,
output: &mut Vec<u8>,
) -> Result<(), DecompressError> {
let pairs: &[u32; PAIR_TABLE_SIZE] = pairs
.first_chunk()
.ok_or(DecompressError::BadHuffmanStream)?;
decode_4_streams_with(table, table_log, Some(pairs), data, output_size, output)
}
const ALGO_TIME: [[(u32, u32); 2]; 16] = [
[(0, 0), (1, 1)],
[(0, 0), (1, 1)],
[(150, 216), (381, 119)],
[(170, 205), (514, 112)],
[(177, 199), (539, 110)],
[(197, 194), (644, 107)],
[(221, 192), (735, 107)],
[(256, 189), (881, 106)],
[(359, 188), (1167, 109)],
[(582, 187), (1570, 114)],
[(688, 187), (1712, 122)],
[(825, 186), (1965, 136)],
[(976, 185), (2131, 150)],
[(1180, 186), (2070, 175)],
[(1377, 185), (1731, 202)],
[(1412, 185), (1695, 202)],
];
const PAIR_MIN_LITERALS: usize = 24 * 1024;
pub fn prefers_pairs(literals: usize, compressed: usize) -> bool {
if literals < PAIR_MIN_LITERALS || compressed * 8 > literals * 5 {
return false;
}
let bucket = if compressed >= literals {
15
} else {
compressed * 16 / literals
};
let blocks = (literals >> 8) as u32;
let [single, pair] = ALGO_TIME[bucket];
let single = single.0 + single.1 * blocks;
let pair = pair.0 + pair.1 * blocks;
pair + (pair >> 5) < single
}
#[inline(always)]
const fn pair_row(symbols: u32, nb_bits: u32, count: u32) -> u32 {
symbols | (nb_bits << 16) | (count << 24)
}
pub fn build_pair_table(
table: &[HuffmanDecodeEntry],
table_log: u8,
pairs: &mut Vec<u32>,
) -> Result<(), DecompressError> {
validate_decode_table(table, table_log)?;
let table: &[HuffmanDecodeEntry; DECODE_TABLE_SIZE] = table
.first_chunk()
.ok_or(DecompressError::BadHuffmanStream)?;
pairs.resize(PAIR_TABLE_SIZE, 0);
let down = u32::from(PAIR_TABLE_LOG - table_log);
let mask = PAIR_TABLE_SIZE - 1;
for (index, row) in pairs[..PAIR_TABLE_SIZE].iter_mut().enumerate() {
let first = table[(index >> down) & (DECODE_TABLE_SIZE - 1)];
let first_bits = u32::from(first.num_bits) & 15;
let second = table[((index << first_bits) & mask) >> down];
let second_bits = u32::from(second.num_bits);
*row = if first_bits + second_bits <= u32::from(PAIR_TABLE_LOG) {
pair_row(
u32::from(first.symbol) | (u32::from(second.symbol) << 8),
first_bits + second_bits,
2,
)
} else {
pair_row(u32::from(first.symbol), first_bits, 1)
};
}
Ok(())
}
fn decode_4_streams_with(
table: &[HuffmanDecodeEntry],
table_log: u8,
pairs: Option<&[u32; PAIR_TABLE_SIZE]>,
data: &[u8],
output_size: usize,
output: &mut Vec<u8>,
) -> Result<(), DecompressError> {
validate_decode_table(table, table_log)?;
prepare_output(output, output_size);
let result = decode_4_streams_core_safe(table, table_log, pairs, data, output_size, output);
if result.is_err() {
output.clear();
}
result
}
fn validate_decode_table(
table: &[HuffmanDecodeEntry],
table_log: u8,
) -> Result<(), DecompressError> {
if table_log == 0 || table_log > MAX_TABLE_LOG {
return Err(DecompressError::BadHuffmanStream);
}
if table.len() < (1usize << table_log) {
return Err(DecompressError::BadHuffmanStream);
}
Ok(())
}
fn decode_4_streams_core_safe(
table: &[HuffmanDecodeEntry],
table_log: u8,
pairs: Option<&[u32; PAIR_TABLE_SIZE]>,
data: &[u8],
output_size: usize,
output: &mut [u8],
) -> Result<(), DecompressError> {
super::decode_4stream::decode_4_streams_core(table, table_log, pairs, data, output_size, output)
}
#[inline(always)]
fn prepare_output(output: &mut Vec<u8>, output_size: usize) {
output.resize(output_size, 0);
}
pub(super) fn decode_stream_tail(
table: &[HuffmanDecodeEntry],
table_log: u8,
reader: &mut ReverseBitReader,
output: &mut [u8],
) -> Result<(), DecompressError> {
let output_size = output.len();
let tl = table_log as usize;
let mut pos = 0;
let tl5 = (tl + tl + tl + tl + tl) as u32;
while pos + 5 <= output_size {
reader.refill();
if reader.bits_remaining() < tl5 as usize
|| 64u32.saturating_sub(reader.bits_consumed) < tl5
{
break;
}
for _ in 0..5 {
let bits =
((reader.container << reader.bits_consumed) >> (64 - table_log as u32)) as usize;
let entry = primitives::huf_table_lookup(table, bits);
primitives::huf_output_write(output, pos, entry.symbol);
pos += 1;
reader.bits_consumed += entry.num_bits as u32;
}
}
reader.refill();
let container = reader.container;
let mut consumed = reader.bits_consumed;
while pos < output_size {
if consumed >= 64 {
return Err(DecompressError::BadHuffmanStream);
}
let bits = ((container << consumed) >> (64 - table_log as u32)) as usize;
let entry = primitives::huf_table_lookup(table, bits);
primitives::huf_output_write(output, pos, entry.symbol);
pos += 1;
consumed += entry.num_bits as u32;
}
reader.bits_consumed = consumed;
if reader.ptr != 0 || consumed != 64 {
return Err(DecompressError::BadHuffmanStream);
}
Ok(())
}
#[cfg(test)]
mod tests {
use super::*;
use crate::bitstream::writer::BitWriter;
#[test]
fn huffman_decode_rejects_zero_table_log_before_fast_tail_lookup() {
let table = [HuffmanDecodeEntry {
symbol: 0,
num_bits: 1,
}];
let data = [0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x80];
let mut output = [0u8; 5];
assert_eq!(
decode_single_stream_into(&table, 0, &data, &mut output),
Err(DecompressError::BadHuffmanStream)
);
}
#[test]
fn huffman_4stream_rejects_zero_table_log_before_tail_lookup() {
let table = [HuffmanDecodeEntry {
symbol: 0,
num_bits: 1,
}];
let stream = [0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x80];
let mut data = Vec::new();
data.extend_from_slice(&8u16.to_le_bytes());
data.extend_from_slice(&8u16.to_le_bytes());
data.extend_from_slice(&8u16.to_le_bytes());
data.extend_from_slice(&stream);
data.extend_from_slice(&stream);
data.extend_from_slice(&stream);
data.extend_from_slice(&stream);
let mut output = Vec::new();
assert_eq!(
decode_4_streams_into(&table, 0, &data, 24, &mut output),
Err(DecompressError::BadHuffmanStream)
);
}
fn xorshift(seed: u64) -> impl FnMut() -> u64 {
let mut seed = seed;
move || {
seed ^= seed << 13;
seed ^= seed >> 7;
seed ^= seed << 17;
seed
}
}
type RandomCode = (Vec<HuffmanDecodeEntry>, u8, Vec<u8>, Vec<(u32, u8)>);
fn random_code(rand: &mut impl FnMut() -> u64) -> RandomCode {
use crate::huffman::weights::build_huffman_decode_table;
let leaves = 2 + (rand() as usize) % 60;
let mut depths = vec![1u8, 1];
while depths.len() < leaves {
let i = (rand() as usize) % depths.len();
if depths[i] < 11 {
depths[i] += 1;
depths.push(depths[i]);
}
}
let table_log = *depths.iter().max().unwrap();
let last_symbol = leaves - 1 + (rand() as usize) % (256 - leaves + 1);
let mut symbols: Vec<usize> = (0..last_symbol).collect();
for i in (1..symbols.len()).rev() {
symbols.swap(i, (rand() as usize) % (i + 1));
}
symbols.truncate(leaves - 1);
symbols.push(last_symbol);
let mut weights = vec![0u8; last_symbol];
for (&symbol, &depth) in symbols[..leaves - 1].iter().zip(&depths) {
weights[symbol] = table_log + 1 - depth;
}
let (table, log) = build_huffman_decode_table(&weights).unwrap();
assert_eq!(log, table_log);
let mut codes = vec![(0u32, 0u8); 256];
for (i, e) in table[..1 << table_log].iter().enumerate() {
codes[e.symbol as usize] = ((i >> (table_log - e.num_bits)) as u32, e.num_bits);
}
let symbols = symbols.iter().map(|&s| s as u8).collect();
(table, log, symbols, codes)
}
fn encode_stream(message: &[u8], codes: &[(u32, u8)]) -> Vec<u8> {
let mut writer = BitWriter::new();
for &symbol in message.iter().rev() {
let (code, bits) = codes[symbol as usize];
writer.write_bits(code, bits);
}
writer.close_reverse_stream();
writer.into_bytes()
}
#[test]
fn stream_tail_matches_reference() {
let mut rand = xorshift(0x9e6c_63d0_676a_9a99);
let (mut ok, mut err) = (0, 0);
for _ in 0..2000 {
let (table, log, symbols, codes) = random_code(&mut rand);
let message: Vec<u8> = (0..=(rand() as usize) % 300)
.map(|_| symbols[(rand() as usize) % symbols.len()])
.collect();
let stream = encode_stream(&message, &codes);
let mut variants = vec![stream.clone()];
let mut flipped = stream.clone();
let bit = (rand() as usize) % (flipped.len() * 8);
flipped[bit / 8] ^= 1 << (bit % 8);
variants.push(flipped);
variants.push(stream[..(rand() as usize) % stream.len()].to_vec());
let mut longer = stream.clone();
longer.push(1 + rand() as u8 % 255);
variants.push(longer);
for (v, data) in variants.iter().enumerate() {
let expected = decode_single_stream(&table, log, data, message.len());
let mut out = vec![0u8; message.len()];
let result = decode_single_stream_into(&table, log, data, &mut out);
match (expected, result) {
(Ok(expected), Ok(())) => {
assert_eq!(out, expected);
if v == 0 {
assert_eq!(out, message);
}
ok += 1;
}
(Err(e), Err(result_e)) => {
assert_eq!(result_e, e);
err += 1;
}
(expected, result) => panic!("{expected:?} vs {result:?}"),
}
}
}
assert!(ok > 2000 && err > 2000, "ok {ok}, err {err}");
}
#[test]
fn four_streams_match_single_stream_decode() {
let mut rand = xorshift(0x2f69_3a8e_1bd5_c047);
let (mut ok, mut err) = (0, 0);
for _ in 0..1500 {
let (table, log, symbols, codes) = random_code(&mut rand);
let size = 16 + (rand() as usize) % 2000;
let message: Vec<u8> = (0..size)
.map(|_| symbols[(rand() as usize) % symbols.len()])
.collect();
let seg = size.div_ceil(4);
let parts = [
&message[..seg],
&message[seg..2 * seg],
&message[2 * seg..3 * seg],
&message[3 * seg..],
];
let streams: Vec<Vec<u8>> = parts.iter().map(|m| encode_stream(m, &codes)).collect();
let mut variants = Vec::new();
for corrupt in 0..3 {
let mut streams = streams.clone();
let k = (rand() as usize) % 4;
match corrupt {
1 => {
let bit = (rand() as usize) % (streams[k].len() * 8);
streams[k][bit / 8] ^= 1 << (bit % 8);
}
2 => {
let len = streams[k].len();
streams[k].truncate(1 + (rand() as usize) % len);
if streams[k].last() == Some(&0) {
streams[k].pop();
streams[k].push(1);
}
}
_ => {}
}
if streams[..3].iter().any(|s| s.len() > usize::from(u16::MAX)) {
continue;
}
let mut data = Vec::new();
for stream in &streams[..3] {
data.extend_from_slice(&(stream.len() as u16).to_le_bytes());
}
for stream in &streams {
data.extend_from_slice(stream);
}
variants.push((corrupt, data, streams));
}
for (corrupt, data, streams) in variants {
let expected: Result<Vec<u8>, DecompressError> = streams
.iter()
.zip(parts)
.map(|(s, part)| decode_single_stream(&table, log, s, part.len()))
.collect::<Result<Vec<_>, _>>()
.map(|p| p.concat());
let mut out = Vec::new();
let result = decode_4_streams_into(&table, log, &data, size, &mut out);
let mut pairs = Vec::new();
build_pair_table(&table, log, &mut pairs).unwrap();
let mut out_pairs = Vec::new();
let result_pairs =
decode_4_streams_pairs_into(&table, log, &pairs, &data, size, &mut out_pairs);
assert_eq!(result.is_ok(), result_pairs.is_ok(), "corrupt {corrupt}");
if result.is_ok() {
assert_eq!(out_pairs, out, "corrupt {corrupt}");
}
match (expected, result) {
(Ok(expected), Ok(())) => {
assert_eq!(out, expected);
if corrupt == 0 {
assert_eq!(out, message);
}
ok += 1;
}
(Err(_), Err(_)) => err += 1,
(expected, result) => panic!("{expected:?} vs {result:?} (corrupt {corrupt})"),
}
}
}
assert!(ok > 1500 && err > 500, "ok {ok}, err {err}");
}
#[test]
fn the_timing_model_prefers_pairs_for_well_compressed_large_sections() {
assert!(prefers_pairs(100_000, 30_000));
assert!(!prefers_pairs(100, 99));
assert!(!prefers_pairs(1_000, 2_000));
assert!(!prefers_pairs(8_000, 2_400));
}
#[test]
fn decode_single_stream_rejects_short_huffman_table() {
let table = [HuffmanDecodeEntry {
symbol: 0,
num_bits: 1,
}];
let mut data = BitWriter::new();
data.write_bits(1, 1);
data.close_reverse_stream();
assert_eq!(
decode_single_stream(&table, 1, &data.into_bytes(), 1),
Err(DecompressError::BadHuffmanStream)
);
}
}