use core::cmp;
use crate::{
entropy::{
bitstream::{BitCStream, BitDStream, BitDStreamStatus, CONTAINER_BITS, CONTAINER_BYTES},
fse,
hist::{HIST_WKSP_SIZE_U32, count_simple, count_wksp},
mem::highbit32,
},
error::{Error, Result},
};
pub(crate) const BLOCKSIZE_MAX: usize = 128 * 1024;
pub(crate) const TABLELOG_MAX: usize = 12;
const DECODER_FAST_TABLELOG: usize = 11;
const TABLELOG_DEFAULT: usize = 11;
const SYMBOLVALUE_MAX: usize = 255;
const STARTNODE: usize = SYMBOLVALUE_MAX + 1;
const CTABLE_WORKSPACE_SIZE_U32: usize = (2 * SYMBOLVALUE_MAX) + 2;
const BLOCKBOUND_MIN: usize = 6 + 1 + 1 + 1 + 8;
const MAX_FSE_TABLELOG_FOR_HUFF_HEADER: usize = 6;
#[derive(Clone, Copy, Default)]
struct CElt {
val: u16,
nb_bits: u8,
}
#[derive(Clone, Copy, Default)]
struct NodeElt {
count: u32,
parent: u16,
byte: u8,
nb_bits: u8,
}
#[derive(Clone, Copy, Default)]
struct RankPos {
base: u32,
current: u32,
}
const RANK_POSITION_TABLE_SIZE: usize = 192;
const RANK_POSITION_LOG_BUCKETS_BEGIN: u32 = 158;
const RANK_POSITION_DISTINCT_COUNT_CUTOFF: u32 = RANK_POSITION_LOG_BUCKETS_BEGIN + 7;
#[derive(Clone, Copy)]
struct BuildCTableWorkspace {
nodes: [NodeElt; CTABLE_WORKSPACE_SIZE_U32],
rank_position: [RankPos; RANK_POSITION_TABLE_SIZE],
}
impl Default for BuildCTableWorkspace {
fn default() -> Self {
Self {
nodes: [NodeElt::default(); CTABLE_WORKSPACE_SIZE_U32],
rank_position: [RankPos::default(); RANK_POSITION_TABLE_SIZE],
}
}
}
#[derive(Clone)]
struct WeightCompressionWorkspace {
count: [u32; TABLELOG_MAX + 1],
norm: [i16; TABLELOG_MAX + 1],
ctable: fse::CTable,
}
impl Default for WeightCompressionWorkspace {
fn default() -> Self {
Self {
count: [0; TABLELOG_MAX + 1],
norm: [0; TABLELOG_MAX + 1],
ctable: fse::CTable::default(),
}
}
}
#[derive(Clone)]
pub(crate) struct CompressWorkspace {
count: [u32; SYMBOLVALUE_MAX + 1],
ctable: [CElt; SYMBOLVALUE_MAX + 1],
build: BuildCTableWorkspace,
weights: WeightCompressionWorkspace,
hist: [u32; HIST_WKSP_SIZE_U32],
}
impl Default for CompressWorkspace {
fn default() -> Self {
Self {
count: [0; SYMBOLVALUE_MAX + 1],
ctable: [CElt::default(); SYMBOLVALUE_MAX + 1],
build: BuildCTableWorkspace::default(),
weights: WeightCompressionWorkspace::default(),
hist: [0; HIST_WKSP_SIZE_U32],
}
}
}
impl CompressWorkspace {
pub(crate) fn build_literal_ctable(
&mut self,
count: &[u32; SYMBOLVALUE_MAX + 1],
max_symbol_value: u32,
max_nb_bits: u32,
) -> Result<u32> {
build_ctable(
&mut self.ctable,
count,
max_symbol_value,
max_nb_bits,
&mut self.build,
)
}
pub(crate) fn write_literal_ctable(
&mut self,
dst: &mut [u8],
max_symbol_value: u32,
huff_log: u32,
) -> Result<usize> {
write_ctable(
dst,
&self.ctable,
max_symbol_value,
huff_log,
&mut self.weights,
)
}
}
#[derive(Clone, Copy, Default)]
struct DEltX1 {
byte: u8,
nb_bits: u8,
}
#[derive(Clone, Copy)]
pub(crate) struct CTableX1 {
table_log: u8,
entries: [CElt; SYMBOLVALUE_MAX + 1],
}
impl Default for CTableX1 {
fn default() -> Self {
Self {
table_log: 0,
entries: [CElt::default(); SYMBOLVALUE_MAX + 1],
}
}
}
impl CTableX1 {
#[inline(always)]
pub(crate) fn symbol_nb_bits(&self, symbol: u8) -> u8 {
self.entries[symbol as usize].nb_bits
}
}
const DTABLE_X1_SIZE: usize = 1 << TABLELOG_MAX;
#[derive(Clone, Copy)]
pub(crate) struct DTableX1 {
table_log: u8,
entries: [DEltX1; DTABLE_X1_SIZE],
}
impl Default for DTableX1 {
fn default() -> Self {
Self {
table_log: 0,
entries: [DEltX1::default(); DTABLE_X1_SIZE],
}
}
}
#[inline(always)]
fn read_segment_length(src: &[u8], offset: usize) -> usize {
u16::from_le_bytes([src[offset], src[offset + 1]]) as usize
}
fn read_stats(
huff_weight: &mut [u8; SYMBOLVALUE_MAX + 1],
rank_stats: &mut [u32; TABLELOG_MAX + 1],
nb_symbols: &mut u32,
table_log: &mut u32,
src: &[u8],
) -> Result<usize> {
if src.is_empty() {
return Err(Error::SrcSizeWrong);
}
let mut i_size = src[0] as usize;
let o_size;
if i_size >= 128 {
o_size = i_size - 127;
i_size = o_size.div_ceil(2);
if i_size + 1 > src.len() || o_size >= huff_weight.len() {
return Err(Error::SrcSizeWrong);
}
for index in (0..o_size).step_by(2) {
huff_weight[index] = src[1 + (index / 2)] >> 4;
huff_weight[index + 1] = src[1 + (index / 2)] & 15;
}
} else {
if i_size + 1 > src.len() {
return Err(Error::SrcSizeWrong);
}
let hw_len = huff_weight.len() - 1;
o_size = fse::decompress(
&mut huff_weight[..hw_len],
&src[1..=i_size],
TABLELOG_MAX as u32,
MAX_FSE_TABLELOG_FOR_HUFF_HEADER,
)?;
}
rank_stats.fill(0);
let mut weight_total = 0u32;
for &weight in &huff_weight[..o_size] {
if weight as usize >= TABLELOG_MAX {
return Err(Error::Corruption("invalid Huff0 weight"));
}
rank_stats[weight as usize] += 1;
weight_total += (1u32 << weight) >> 1;
}
if weight_total == 0 {
return Err(Error::Corruption("empty Huff0 weight table"));
}
let log = highbit32(weight_total) + 1;
if log as usize > TABLELOG_MAX {
return Err(Error::Corruption("Huff0 table log too large"));
}
*table_log = log;
let total = 1u32 << log;
let rest = total - weight_total;
let verif = 1u32 << highbit32(rest);
let last_weight = highbit32(rest) + 1;
if verif != rest {
return Err(Error::Corruption("non power-of-two Huff0 weight remainder"));
}
huff_weight[o_size] = last_weight as u8;
rank_stats[last_weight as usize] += 1;
if rank_stats[1] < 2 || (rank_stats[1] & 1) != 0 {
return Err(Error::Corruption("invalid Huff0 rank-1 weight count"));
}
*nb_symbols = o_size as u32 + 1;
Ok(i_size + 1)
}
pub(crate) fn read_dtable_x1(src: &[u8], dtable: &mut DTableX1) -> Result<usize> {
let mut rank_val = [0u32; TABLELOG_MAX + 1];
let mut huff_weight = [0u8; SYMBOLVALUE_MAX + 1];
let mut table_log = 0u32;
let mut nb_symbols = 0u32;
let i_size = read_stats(
&mut huff_weight,
&mut rank_val,
&mut nb_symbols,
&mut table_log,
src,
)?;
if (1usize << table_log) > dtable.entries.len() {
return Err(Error::Corruption(
"Huff0 table log exceeds decode table capacity",
));
}
dtable.table_log = table_log as u8;
let mut next_rank_start = 0u32;
for index in 1..=table_log as usize {
let current = next_rank_start;
next_rank_start += rank_val[index] << (index - 1);
rank_val[index] = current;
}
for index in 0..nb_symbols as usize {
let weight = huff_weight[index] as usize;
let length = (1usize << weight) >> 1;
let start = rank_val[weight] as usize;
let end = start + length;
let entry = DEltX1 {
byte: index as u8,
nb_bits: (table_log + 1 - weight as u32) as u8,
};
rank_val[weight] = end as u32;
for slot in &mut dtable.entries[start..end] {
*slot = entry;
}
}
Ok(i_size)
}
pub(crate) fn read_ctable_x1(src: &[u8], ctable: &mut CTableX1) -> Result<usize> {
Ok(read_ctable_x1_with_repeat_validity(src, ctable)?.0)
}
pub(crate) fn read_ctable_x1_with_repeat_validity(
src: &[u8],
ctable: &mut CTableX1,
) -> Result<(usize, bool)> {
let mut rank_val = [0u32; TABLELOG_MAX + 1];
let mut huff_weight = [0u8; SYMBOLVALUE_MAX + 1];
let mut table_log = 0u32;
let mut nb_symbols = 0u32;
let i_size = read_stats(
&mut huff_weight,
&mut rank_val,
&mut nb_symbols,
&mut table_log,
src,
)?;
ctable.table_log = table_log as u8;
build_ctable_from_weights(
&mut ctable.entries,
&huff_weight,
nb_symbols as usize,
table_log,
)?;
let repeat_valid = nb_symbols as usize == SYMBOLVALUE_MAX + 1
&& huff_weight[..nb_symbols as usize]
.iter()
.all(|&weight| weight != 0);
Ok((i_size, repeat_valid))
}
#[allow(unsafe_code)]
#[inline(always)]
fn decode_symbol_x1(bit_d: &mut BitDStream, table: &[DEltX1], table_log: u32) -> u8 {
let value = bit_d.look_bits_fast(table_log) as usize;
let entry = unsafe { *table.get_unchecked(value) };
bit_d.skip_bits(entry.nb_bits as u32);
entry.byte
}
#[allow(unsafe_code)]
fn decode_stream_x1(
dst: &mut [u8],
mut pos: usize,
bit_d: &mut BitDStream,
end: usize,
table: &[DEltX1],
table_log: u32,
) -> usize {
while bit_d.reload() == BitDStreamStatus::Unfinished && pos < end.saturating_sub(3) {
unsafe { *dst.get_unchecked_mut(pos) = decode_symbol_x1(bit_d, table, table_log) };
pos += 1;
unsafe { *dst.get_unchecked_mut(pos) = decode_symbol_x1(bit_d, table, table_log) };
pos += 1;
unsafe { *dst.get_unchecked_mut(pos) = decode_symbol_x1(bit_d, table, table_log) };
pos += 1;
unsafe { *dst.get_unchecked_mut(pos) = decode_symbol_x1(bit_d, table, table_log) };
pos += 1;
}
while pos < end {
unsafe { *dst.get_unchecked_mut(pos) = decode_symbol_x1(bit_d, table, table_log) };
pos += 1;
}
pos
}
fn decompress_1x1_using_dtable(dst: &mut [u8], src: &[u8], dtable: &DTableX1) -> Result<usize> {
let mut bit_d = BitDStream::new(src)?;
let table_log = dtable.table_log as u32;
let written = decode_stream_x1(dst, 0, &mut bit_d, dst.len(), &dtable.entries, table_log);
if written != dst.len() || !bit_d.end_of_stream() {
return Err(Error::Corruption("Huff0 stream did not terminate cleanly"));
}
Ok(written)
}
fn decompress_4x1_using_dtable(dst: &mut [u8], src: &[u8], dtable: &DTableX1) -> Result<usize> {
if src.len() < 10 {
return Err(Error::Corruption("truncated Huff0 4X stream"));
}
if dst.len() < 6 {
return Err(Error::Corruption("Huff0 4X output too small to split"));
}
let length1 = read_segment_length(src, 0);
let length2 = read_segment_length(src, 2);
let length3 = read_segment_length(src, 4);
let length4 = src.len().wrapping_sub(length1 + length2 + length3 + 6);
if length4 > src.len() {
return Err(Error::Corruption("invalid Huff0 4X segment lengths"));
}
let istart1 = 6;
let istart2 = istart1 + length1;
let istart3 = istart2 + length2;
let istart4 = istart3 + length3;
let segment_size = dst.len().div_ceil(4);
let mut bit_d1 = BitDStream::new(&src[istart1..istart2])?;
let mut bit_d2 = BitDStream::new(&src[istart2..istart3])?;
let mut bit_d3 = BitDStream::new(&src[istart3..istart4])?;
let mut bit_d4 = BitDStream::new(&src[istart4..])?;
let op_start2 = segment_size;
let op_start3 = op_start2 + segment_size;
let op_start4 = op_start3 + segment_size;
if op_start4 > dst.len() {
return Err(Error::Corruption("Huff0 4X segment starts past the output"));
}
let olimit = dst.len().saturating_sub(3);
let mut op1 = 0usize;
let mut op2 = op_start2;
let mut op3 = op_start3;
let mut op4 = op_start4;
let mut end_signal = true;
let table_log = dtable.table_log as u32;
#[allow(unsafe_code)]
while end_signal && op4 < olimit {
unsafe {
*dst.get_unchecked_mut(op1) = decode_symbol_x1(&mut bit_d1, &dtable.entries, table_log)
};
op1 += 1;
unsafe {
*dst.get_unchecked_mut(op2) = decode_symbol_x1(&mut bit_d2, &dtable.entries, table_log)
};
op2 += 1;
unsafe {
*dst.get_unchecked_mut(op3) = decode_symbol_x1(&mut bit_d3, &dtable.entries, table_log)
};
op3 += 1;
unsafe {
*dst.get_unchecked_mut(op4) = decode_symbol_x1(&mut bit_d4, &dtable.entries, table_log)
};
op4 += 1;
unsafe {
*dst.get_unchecked_mut(op1) = decode_symbol_x1(&mut bit_d1, &dtable.entries, table_log)
};
op1 += 1;
unsafe {
*dst.get_unchecked_mut(op2) = decode_symbol_x1(&mut bit_d2, &dtable.entries, table_log)
};
op2 += 1;
unsafe {
*dst.get_unchecked_mut(op3) = decode_symbol_x1(&mut bit_d3, &dtable.entries, table_log)
};
op3 += 1;
unsafe {
*dst.get_unchecked_mut(op4) = decode_symbol_x1(&mut bit_d4, &dtable.entries, table_log)
};
op4 += 1;
unsafe {
*dst.get_unchecked_mut(op1) = decode_symbol_x1(&mut bit_d1, &dtable.entries, table_log)
};
op1 += 1;
unsafe {
*dst.get_unchecked_mut(op2) = decode_symbol_x1(&mut bit_d2, &dtable.entries, table_log)
};
op2 += 1;
unsafe {
*dst.get_unchecked_mut(op3) = decode_symbol_x1(&mut bit_d3, &dtable.entries, table_log)
};
op3 += 1;
unsafe {
*dst.get_unchecked_mut(op4) = decode_symbol_x1(&mut bit_d4, &dtable.entries, table_log)
};
op4 += 1;
unsafe {
*dst.get_unchecked_mut(op1) = decode_symbol_x1(&mut bit_d1, &dtable.entries, table_log)
};
op1 += 1;
unsafe {
*dst.get_unchecked_mut(op2) = decode_symbol_x1(&mut bit_d2, &dtable.entries, table_log)
};
op2 += 1;
unsafe {
*dst.get_unchecked_mut(op3) = decode_symbol_x1(&mut bit_d3, &dtable.entries, table_log)
};
op3 += 1;
unsafe {
*dst.get_unchecked_mut(op4) = decode_symbol_x1(&mut bit_d4, &dtable.entries, table_log)
};
op4 += 1;
end_signal &= bit_d1.reload_fast() == BitDStreamStatus::Unfinished;
end_signal &= bit_d2.reload_fast() == BitDStreamStatus::Unfinished;
end_signal &= bit_d3.reload_fast() == BitDStreamStatus::Unfinished;
end_signal &= bit_d4.reload_fast() == BitDStreamStatus::Unfinished;
}
if op1 > op_start2 || op2 > op_start3 || op3 > op_start4 {
return Err(Error::Corruption("Huff0 segment overrun"));
}
op1 = decode_stream_x1(dst, op1, &mut bit_d1, op_start2, &dtable.entries, table_log);
op2 = decode_stream_x1(dst, op2, &mut bit_d2, op_start3, &dtable.entries, table_log);
op3 = decode_stream_x1(dst, op3, &mut bit_d3, op_start4, &dtable.entries, table_log);
op4 = decode_stream_x1(dst, op4, &mut bit_d4, dst.len(), &dtable.entries, table_log);
debug_assert_eq!(op1, op_start2);
debug_assert_eq!(op2, op_start3);
debug_assert_eq!(op3, op_start4);
debug_assert_eq!(op4, dst.len());
if !bit_d1.end_of_stream()
|| !bit_d2.end_of_stream()
|| !bit_d3.end_of_stream()
|| !bit_d4.end_of_stream()
{
return Err(Error::Corruption("Huff0 stream did not consume all bits"));
}
Ok(dst.len())
}
#[derive(Clone, Copy, Default)]
struct DEltX2 {
sequence: u16,
nb_bits: u8,
length: u8,
}
const DTABLE_X2_SIZE: usize = 1 << TABLELOG_MAX;
#[derive(Clone, Copy)]
pub(crate) struct DTableX2 {
table_log: u8,
entries: [DEltX2; DTABLE_X2_SIZE],
}
impl Default for DTableX2 {
fn default() -> Self {
Self {
table_log: 0,
entries: [DEltX2::default(); DTABLE_X2_SIZE],
}
}
}
#[inline]
fn build_delt_x2(symbol: u8, nb_bits: u32, base_symbol: u8, level: u8) -> DEltX2 {
debug_assert!(level == 1 || level == 2);
let sequence = if level == 1 {
symbol as u16
} else {
base_symbol as u16 | ((symbol as u16) << 8)
};
DEltX2 {
sequence,
nb_bits: nb_bits as u8,
length: level,
}
}
fn fill_dtable_x2_for_weight(
slots: &mut [DEltX2],
symbols: &[u8],
nb_bits: u32,
table_log: u32,
base_symbol: u8,
level: u8,
) -> Result<()> {
let shift = table_log.checked_sub(nb_bits).ok_or(Error::Corruption(
"Huff0 X2 symbol is deeper than its table",
))?;
let length = 1usize << shift;
let mut at = 0usize;
for &symbol in symbols {
let entry = build_delt_x2(symbol, nb_bits, base_symbol, level);
let end = at
.checked_add(length)
.ok_or(Error::Corruption("Huff0 X2 rank overflows the table"))?;
slots
.get_mut(at..end)
.ok_or(Error::Corruption("Huff0 X2 rank runs past the table"))?
.fill(entry);
at = end;
}
Ok(())
}
#[allow(clippy::too_many_arguments)]
fn fill_dtable_x2_level2(
sub_table: &mut [DEltX2],
table_log: u32,
consumed_bits: u32,
rank_val: &[u32; TABLELOG_MAX + 1],
min_weight: usize,
weight_end: usize,
sorted_symbols: &[u8],
rank_start: &[u32; TABLELOG_MAX + 2],
nb_bits_baseline: u32,
base_symbol: u8,
) -> Result<()> {
if min_weight > 1 {
let skip = *rank_val
.get(min_weight)
.ok_or(Error::Corruption("Huff0 X2 weight exceeds the table log"))?
as usize;
let entry = build_delt_x2(base_symbol, consumed_bits, 0, 1);
sub_table
.get_mut(..skip)
.ok_or(Error::Corruption("Huff0 X2 single-symbol run overflows"))?
.fill(entry);
}
for weight in min_weight..weight_end {
let begin = rank_start[weight] as usize;
let end = rank_start[weight + 1] as usize;
let nb_bits = nb_bits_baseline - weight as u32;
let at = rank_val[weight] as usize;
fill_dtable_x2_for_weight(
sub_table
.get_mut(at..)
.ok_or(Error::Corruption("Huff0 X2 rank starts past the table"))?,
sorted_symbols
.get(begin..end)
.ok_or(Error::Corruption("Huff0 X2 rank bounds are inconsistent"))?,
nb_bits + consumed_bits,
table_log,
base_symbol,
2,
)?;
}
Ok(())
}
#[allow(clippy::too_many_arguments)]
fn fill_dtable_x2(
entries: &mut [DEltX2],
table_log: u32,
sorted_symbols: &[u8],
rank_start: &[u32; TABLELOG_MAX + 2],
rank_val: &[[u32; TABLELOG_MAX + 1]; TABLELOG_MAX],
max_weight: usize,
nb_bits_baseline: u32,
) -> Result<()> {
let scale_log = nb_bits_baseline as i32 - table_log as i32;
let min_bits = nb_bits_baseline - max_weight as u32;
for weight in 1..=max_weight {
let begin = rank_start[weight] as usize;
let end = rank_start[weight + 1] as usize;
let nb_bits = nb_bits_baseline - weight as u32;
let symbols = sorted_symbols
.get(begin..end)
.ok_or(Error::Corruption("Huff0 X2 rank bounds are inconsistent"))?;
let at = rank_val[0][weight] as usize;
if table_log - nb_bits >= min_bits {
let length = 1usize << (table_log - nb_bits);
let min_weight = (nb_bits as i32 + scale_log).max(1) as usize;
let mut start = at;
for &symbol in symbols {
let sub_end = start
.checked_add(length)
.ok_or(Error::Corruption("Huff0 X2 rank overflows the table"))?;
fill_dtable_x2_level2(
entries
.get_mut(start..sub_end)
.ok_or(Error::Corruption("Huff0 X2 rank runs past the table"))?,
table_log,
nb_bits,
&rank_val[nb_bits as usize],
min_weight,
max_weight + 1,
sorted_symbols,
rank_start,
nb_bits_baseline,
symbol,
)?;
start = sub_end;
}
} else {
fill_dtable_x2_for_weight(
entries
.get_mut(at..)
.ok_or(Error::Corruption("Huff0 X2 rank starts past the table"))?,
symbols,
nb_bits,
table_log,
0,
1,
)?;
}
}
Ok(())
}
pub(crate) fn read_dtable_x2(src: &[u8], dtable: &mut DTableX2) -> Result<usize> {
let mut rank_stats = [0u32; TABLELOG_MAX + 1];
let mut huff_weight = [0u8; SYMBOLVALUE_MAX + 1];
let mut table_log = 0u32;
let mut nb_symbols = 0u32;
let i_size = read_stats(
&mut huff_weight,
&mut rank_stats,
&mut nb_symbols,
&mut table_log,
src,
)?;
if table_log as usize > TABLELOG_MAX {
return Err(Error::Corruption(
"Huff0 table log exceeds decode table capacity",
));
}
let target_log = if (table_log as usize) <= DECODER_FAST_TABLELOG {
DECODER_FAST_TABLELOG as u32
} else {
TABLELOG_MAX as u32
};
dtable.table_log = target_log as u8;
let mut max_weight = table_log as usize;
while rank_stats[max_weight] == 0 {
max_weight -= 1;
}
let mut rank_start = [0u32; TABLELOG_MAX + 2];
let mut next_start = 0u32;
for weight in 1..=max_weight {
rank_start[weight] = next_start;
next_start += rank_stats[weight];
}
rank_start[max_weight + 1] = next_start;
let mut sorted_symbols = [0u8; SYMBOLVALUE_MAX + 1];
let mut cursor = rank_start;
let mut absent_cursor = next_start;
for symbol in 0..nb_symbols as usize {
let weight = huff_weight[symbol] as usize;
let slot = if weight == 0 {
&mut absent_cursor
} else {
&mut cursor[weight]
};
sorted_symbols[*slot as usize] = symbol as u8;
*slot += 1;
}
let mut rank_val = [[0u32; TABLELOG_MAX + 1]; TABLELOG_MAX];
let rescale = target_log as i32 - table_log as i32 - 1;
let mut next_val = 0u32;
for weight in 1..=max_weight {
rank_val[0][weight] = next_val;
next_val += rank_stats[weight] << (weight as i32 + rescale) as u32;
}
if next_val as usize != 1usize << target_log {
return Err(Error::Corruption("Huff0 X2 ranks do not tile the table"));
}
let min_bits = table_log + 1 - max_weight as u32;
debug_assert!(min_bits <= target_log);
for consumed in min_bits..=(target_log - min_bits) {
for weight in 1..=max_weight {
rank_val[consumed as usize][weight] = rank_val[0][weight] >> consumed;
}
}
fill_dtable_x2(
&mut dtable.entries[..1usize << target_log],
target_log,
&sorted_symbols,
&rank_start,
&rank_val,
max_weight,
table_log + 1,
)?;
Ok(i_size)
}
#[allow(unsafe_code)]
#[inline(always)]
unsafe fn decode_symbol_x2(
dst: &mut [u8],
pos: usize,
bit_d: &mut BitDStream,
table: &[DEltX2],
table_log: u32,
) -> usize {
let value = bit_d.look_bits_fast(table_log) as usize;
debug_assert!(value < table.len());
let entry = unsafe { *table.get_unchecked(value) };
unsafe {
core::ptr::write_unaligned(
dst.as_mut_ptr().add(pos) as *mut u16,
entry.sequence.to_le(),
);
}
bit_d.skip_bits(entry.nb_bits as u32);
entry.length as usize
}
#[inline(always)]
fn decode_last_symbol_x2(
dst: &mut [u8],
pos: usize,
bit_d: &mut BitDStream,
table: &[DEltX2],
table_log: u32,
) -> usize {
let value = bit_d.look_bits_fast(table_log) as usize;
debug_assert!(value < table.len());
let entry = table[value & (table.len() - 1)];
dst[pos] = entry.sequence as u8;
if entry.length == 1 {
bit_d.skip_bits(entry.nb_bits as u32);
} else if bit_d.bits_consumed < CONTAINER_BITS {
bit_d.skip_bits(entry.nb_bits as u32);
if bit_d.bits_consumed > CONTAINER_BITS {
bit_d.bits_consumed = CONTAINER_BITS;
}
}
1
}
#[allow(unsafe_code)]
fn decode_stream_x2(
dst: &mut [u8],
mut pos: usize,
bit_d: &mut BitDStream,
end: usize,
table: &[DEltX2],
table_log: u32,
) -> usize {
assert!(pos <= end && end <= dst.len());
let width = CONTAINER_BYTES;
if end - pos >= width {
if table_log <= DECODER_FAST_TABLELOG as u32 {
while bit_d.reload() == BitDStreamStatus::Unfinished && pos + 10 <= end {
unsafe {
pos += decode_symbol_x2(dst, pos, bit_d, table, table_log);
pos += decode_symbol_x2(dst, pos, bit_d, table, table_log);
pos += decode_symbol_x2(dst, pos, bit_d, table, table_log);
pos += decode_symbol_x2(dst, pos, bit_d, table, table_log);
pos += decode_symbol_x2(dst, pos, bit_d, table, table_log);
}
}
} else {
while bit_d.reload() == BitDStreamStatus::Unfinished && pos + width <= end {
unsafe {
pos += decode_symbol_x2(dst, pos, bit_d, table, table_log);
pos += decode_symbol_x2(dst, pos, bit_d, table, table_log);
pos += decode_symbol_x2(dst, pos, bit_d, table, table_log);
pos += decode_symbol_x2(dst, pos, bit_d, table, table_log);
}
}
}
} else {
bit_d.reload();
}
if end - pos >= 2 {
while bit_d.reload() == BitDStreamStatus::Unfinished && pos + 2 <= end {
pos += unsafe { decode_symbol_x2(dst, pos, bit_d, table, table_log) };
}
while pos + 2 <= end {
pos += unsafe { decode_symbol_x2(dst, pos, bit_d, table, table_log) };
}
}
if pos < end {
pos += decode_last_symbol_x2(dst, pos, bit_d, table, table_log);
}
pos
}
fn decompress_1x2_using_dtable(dst: &mut [u8], src: &[u8], dtable: &DTableX2) -> Result<usize> {
let mut bit_d = BitDStream::new(src)?;
let table_log = dtable.table_log as u32;
let table = &dtable.entries[..1usize << table_log];
let written = decode_stream_x2(dst, 0, &mut bit_d, dst.len(), table, table_log);
if written != dst.len() || !bit_d.end_of_stream() {
return Err(Error::Corruption("Huff0 stream did not terminate cleanly"));
}
Ok(written)
}
fn decompress_4x2_using_dtable(dst: &mut [u8], src: &[u8], dtable: &DTableX2) -> Result<usize> {
if src.len() < 10 {
return Err(Error::Corruption("truncated Huff0 4X stream"));
}
if dst.len() < 6 {
return Err(Error::Corruption("Huff0 4X output too small to split"));
}
let length1 = read_segment_length(src, 0);
let length2 = read_segment_length(src, 2);
let length3 = read_segment_length(src, 4);
let length4 = src.len().wrapping_sub(length1 + length2 + length3 + 6);
if length4 > src.len() {
return Err(Error::Corruption("invalid Huff0 4X segment lengths"));
}
let istart1 = 6;
let istart2 = istart1 + length1;
let istart3 = istart2 + length2;
let istart4 = istart3 + length3;
let segment_size = dst.len().div_ceil(4);
let mut bit_d1 = BitDStream::new(&src[istart1..istart2])?;
let mut bit_d2 = BitDStream::new(&src[istart2..istart3])?;
let mut bit_d3 = BitDStream::new(&src[istart3..istart4])?;
let mut bit_d4 = BitDStream::new(&src[istart4..])?;
let op_start2 = segment_size;
let op_start3 = op_start2 + segment_size;
let op_start4 = op_start3 + segment_size;
if op_start4 > dst.len() {
return Err(Error::Corruption("Huff0 4X segment starts past the output"));
}
let mut op1 = 0usize;
let mut op2 = op_start2;
let mut op3 = op_start3;
let mut op4 = op_start4;
let mut end_signal = true;
let table_log = dtable.table_log as u32;
let table = &dtable.entries[..1usize << table_log];
let width = CONTAINER_BYTES;
#[allow(unsafe_code)]
while end_signal
&& op1 + width <= op_start2
&& op2 + width <= op_start3
&& op3 + width <= op_start4
&& op4 + width <= dst.len()
{
unsafe {
op1 += decode_symbol_x2(dst, op1, &mut bit_d1, table, table_log);
op2 += decode_symbol_x2(dst, op2, &mut bit_d2, table, table_log);
op3 += decode_symbol_x2(dst, op3, &mut bit_d3, table, table_log);
op4 += decode_symbol_x2(dst, op4, &mut bit_d4, table, table_log);
op1 += decode_symbol_x2(dst, op1, &mut bit_d1, table, table_log);
op2 += decode_symbol_x2(dst, op2, &mut bit_d2, table, table_log);
op3 += decode_symbol_x2(dst, op3, &mut bit_d3, table, table_log);
op4 += decode_symbol_x2(dst, op4, &mut bit_d4, table, table_log);
op1 += decode_symbol_x2(dst, op1, &mut bit_d1, table, table_log);
op2 += decode_symbol_x2(dst, op2, &mut bit_d2, table, table_log);
op3 += decode_symbol_x2(dst, op3, &mut bit_d3, table, table_log);
op4 += decode_symbol_x2(dst, op4, &mut bit_d4, table, table_log);
op1 += decode_symbol_x2(dst, op1, &mut bit_d1, table, table_log);
op2 += decode_symbol_x2(dst, op2, &mut bit_d2, table, table_log);
op3 += decode_symbol_x2(dst, op3, &mut bit_d3, table, table_log);
op4 += decode_symbol_x2(dst, op4, &mut bit_d4, table, table_log);
}
end_signal &= bit_d1.reload_fast() == BitDStreamStatus::Unfinished;
end_signal &= bit_d2.reload_fast() == BitDStreamStatus::Unfinished;
end_signal &= bit_d3.reload_fast() == BitDStreamStatus::Unfinished;
end_signal &= bit_d4.reload_fast() == BitDStreamStatus::Unfinished;
}
if op1 > op_start2 || op2 > op_start3 || op3 > op_start4 {
return Err(Error::Corruption("Huff0 segment overrun"));
}
op1 = decode_stream_x2(dst, op1, &mut bit_d1, op_start2, table, table_log);
op2 = decode_stream_x2(dst, op2, &mut bit_d2, op_start3, table, table_log);
op3 = decode_stream_x2(dst, op3, &mut bit_d3, op_start4, table, table_log);
op4 = decode_stream_x2(dst, op4, &mut bit_d4, dst.len(), table, table_log);
debug_assert_eq!(op1, op_start2);
debug_assert_eq!(op2, op_start3);
debug_assert_eq!(op3, op_start4);
debug_assert_eq!(op4, dst.len());
if !bit_d1.end_of_stream()
|| !bit_d2.end_of_stream()
|| !bit_d3.end_of_stream()
|| !bit_d4.end_of_stream()
{
return Err(Error::Corruption("Huff0 stream did not consume all bits"));
}
Ok(dst.len())
}
pub(crate) fn prefers_double_symbol_decoder(
regenerated_size: usize,
compressed_size: usize,
) -> bool {
const ALGO_TIME: [[(u64, u64); 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)],
];
if regenerated_size == 0 {
return false;
}
let quantized = if compressed_size >= regenerated_size {
15
} else {
compressed_size * 16 / regenerated_size
};
let per_256 = (regenerated_size >> 8) as u64;
let [(single_build, single_rate), (double_build, double_rate)] = ALGO_TIME[quantized];
let single = single_build + single_rate * per_256;
let double = double_build + double_rate * per_256;
double + (double >> 5) < single
}
#[derive(Clone, Copy)]
#[allow(clippy::large_enum_variant)]
pub(crate) enum HuffmanDTable {
Single(DTableX1),
Double(DTableX2),
}
impl HuffmanDTable {
pub(crate) fn single_slot(slot: &mut Option<Self>) -> &mut DTableX1 {
if !matches!(slot, Some(Self::Single(_))) {
*slot = Some(Self::Single(DTableX1::default()));
}
match slot {
Some(Self::Single(table)) => table,
_ => unreachable!("just installed"),
}
}
pub(crate) fn double_slot(slot: &mut Option<Self>) -> &mut DTableX2 {
if !matches!(slot, Some(Self::Double(_))) {
*slot = Some(Self::Double(DTableX2::default()));
}
match slot {
Some(Self::Double(table)) => table,
_ => unreachable!("just installed"),
}
}
}
pub(crate) fn decompress_1x_using_dtable(
dst: &mut [u8],
src: &[u8],
dtable: &HuffmanDTable,
) -> Result<usize> {
match dtable {
HuffmanDTable::Single(table) => decompress_1x1_using_dtable(dst, src, table),
HuffmanDTable::Double(table) => decompress_1x2_using_dtable(dst, src, table),
}
}
pub(crate) fn decompress_4x_using_dtable(
dst: &mut [u8],
src: &[u8],
dtable: &HuffmanDTable,
) -> Result<usize> {
match dtable {
HuffmanDTable::Single(table) => decompress_4x1_using_dtable(dst, src, table),
HuffmanDTable::Double(table) => decompress_4x2_using_dtable(dst, src, table),
}
}
pub(crate) fn decompress_into(dst: &mut [u8], src: &[u8]) -> Result<usize> {
if dst.is_empty() {
return Err(Error::DstSizeTooSmall);
}
if src.len() > dst.len() {
return Err(Error::Corruption("Huff0 input larger than output"));
}
if src.len() == dst.len() {
dst.copy_from_slice(src);
return Ok(dst.len());
}
if src.len() == 1 {
dst.fill(src[0]);
return Ok(dst.len());
}
let mut dtable = None;
let hsize = if prefers_double_symbol_decoder(dst.len(), src.len()) {
read_dtable_x2(src, HuffmanDTable::double_slot(&mut dtable))?
} else {
read_dtable_x1(src, HuffmanDTable::single_slot(&mut dtable))?
};
if hsize >= src.len() {
return Err(Error::SrcSizeWrong);
}
let dtable = dtable.expect("installed above");
decompress_4x_using_dtable(dst, &src[hsize..], &dtable)
}
pub(crate) fn compress_bound(size: usize) -> usize {
129 + size + (size >> 8) + 8
}
pub(crate) fn compress(src: &[u8]) -> Result<Option<Vec<u8>>> {
let mut dst = vec![0u8; compress_bound(src.len())];
let written = compress_into(&mut dst, src)?;
if written == 0 {
return Ok(None);
}
dst.truncate(written);
Ok(Some(dst))
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum StreamMode {
Single,
Four,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum TableDepth {
Estimated,
Searched,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) enum Compressibility {
Unknown,
Suspect,
}
const SUSPECT_INCOMPRESSIBLE_SAMPLE_SIZE: usize = 4096;
const SUSPECT_INCOMPRESSIBLE_SAMPLE_RATIO: usize = 10;
fn looks_incompressible_from_sample(src: &[u8], count: &mut [u32; SYMBOLVALUE_MAX + 1]) -> bool {
if src.len() < SUSPECT_INCOMPRESSIBLE_SAMPLE_SIZE * SUSPECT_INCOMPRESSIBLE_SAMPLE_RATIO {
return false;
}
let mut largest_total = 0u32;
for sample in [
&src[..SUSPECT_INCOMPRESSIBLE_SAMPLE_SIZE],
&src[src.len() - SUSPECT_INCOMPRESSIBLE_SAMPLE_SIZE..],
] {
let mut max_symbol_value = SYMBOLVALUE_MAX as u32;
largest_total += count_simple(count, &mut max_symbol_value, sample);
}
largest_total as usize <= ((2 * SUSPECT_INCOMPRESSIBLE_SAMPLE_SIZE) >> 7) + 4
}
#[inline(always)]
fn compress_using_ctable_mode(
dst: &mut [u8],
src: &[u8],
ctable: &[CElt; SYMBOLVALUE_MAX + 1],
table_log: u32,
stream_mode: StreamMode,
) -> usize {
match stream_mode {
StreamMode::Single => compress_1x_using_ctable(dst, src, ctable, table_log),
StreamMode::Four => compress_4x_using_ctable(dst, src, ctable, table_log),
}
}
pub(crate) fn compress_with_table(src: &[u8], ctable: &CTableX1) -> Result<Option<Vec<u8>>> {
compress_with_table_mode(src, ctable, StreamMode::Four)
}
pub(crate) fn compress_with_table_mode(
src: &[u8],
ctable: &CTableX1,
stream_mode: StreamMode,
) -> Result<Option<Vec<u8>>> {
if src.is_empty() || !table_supports_all_symbols(ctable, src) {
return Ok(None);
}
let mut dst = vec![0u8; src.len() + BLOCKBOUND_MIN];
let written = compress_using_ctable_mode(
&mut dst,
src,
&ctable.entries,
ctable.table_log as u32,
stream_mode,
);
if written == 0 || written >= src.len().saturating_sub(1) {
return Ok(None);
}
dst.truncate(written);
Ok(Some(dst))
}
pub(crate) fn compress_with_table_into(
dst: &mut [u8],
src: &[u8],
ctable: &CTableX1,
) -> Result<usize> {
compress_with_table_into_mode(dst, src, ctable, StreamMode::Four)
}
pub(crate) fn compress_with_table_into_mode(
dst: &mut [u8],
src: &[u8],
ctable: &CTableX1,
stream_mode: StreamMode,
) -> Result<usize> {
if src.is_empty() || !table_supports_all_symbols(ctable, src) {
return Ok(0);
}
if matches!(stream_mode, StreamMode::Four) && dst.len() < BLOCKBOUND_MIN {
return Ok(0);
}
let written = compress_using_ctable_mode(
dst,
src,
&ctable.entries,
ctable.table_log as u32,
stream_mode,
);
if written == 0 || written >= src.len().saturating_sub(1) {
return Ok(0);
}
Ok(written)
}
#[derive(Clone, Copy)]
pub(crate) struct PreferredTableCompression {
pub(crate) written: usize,
pub(crate) reused_table: bool,
pub(crate) table: CTableX1,
}
pub(crate) fn compress_prefer_existing_table_into(
dst: &mut [u8],
src: &[u8],
previous: Option<&CTableX1>,
) -> Result<Option<PreferredTableCompression>> {
let mut workspace = CompressWorkspace::default();
compress_prefer_existing_table_into_mode(
dst,
src,
previous,
StreamMode::Four,
TableDepth::Estimated,
Compressibility::Unknown,
&mut workspace,
)
}
pub(crate) fn compress_prefer_existing_table_into_mode(
dst: &mut [u8],
src: &[u8],
previous: Option<&CTableX1>,
stream_mode: StreamMode,
table_depth: TableDepth,
compressibility: Compressibility,
workspace: &mut CompressWorkspace,
) -> Result<Option<PreferredTableCompression>> {
if src.is_empty() || dst.is_empty() {
return Ok(None);
}
if src.len() > BLOCKSIZE_MAX {
return Err(Error::SrcSizeWrong);
}
if compressibility == Compressibility::Suspect
&& looks_incompressible_from_sample(src, &mut workspace.count)
{
return Ok(None);
}
let mut max_symbol_value = SYMBOLVALUE_MAX as u32;
let mut huff_log = TABLELOG_DEFAULT as u32;
let largest = count_wksp(
&mut workspace.count,
&mut max_symbol_value,
src,
&mut workspace.hist,
)?;
if largest as usize == src.len() || largest as usize <= (src.len() >> 7) + 4 {
return Ok(None);
}
huff_log = match table_depth {
TableDepth::Estimated => optimal_table_log(huff_log, src.len(), max_symbol_value),
TableDepth::Searched => {
optimal_table_log_search(huff_log, &workspace.count, max_symbol_value)
}
};
huff_log = build_ctable(
&mut workspace.ctable,
&workspace.count,
max_symbol_value,
huff_log,
&mut workspace.build,
)?;
workspace.ctable[(max_symbol_value as usize + 1)..].fill(CElt::default());
let new_table = CTableX1 {
table_log: huff_log as u8,
entries: workspace.ctable,
};
let header_size = match write_ctable(
dst,
&workspace.ctable,
max_symbol_value,
huff_log,
&mut workspace.weights,
) {
Ok(size) => Some(size),
Err(Error::Generic) => None,
Err(err) => return Err(err),
};
let previous = previous
.filter(|table| table_covers_counted_symbols(table, &workspace.count, max_symbol_value));
if let Some(previous) = previous {
let old_size =
estimate_compressed_size(&previous.entries, &workspace.count, max_symbol_value);
let new_size =
estimate_compressed_size(&workspace.ctable, &workspace.count, max_symbol_value);
let previous_looks_better = match header_size {
Some(header_size) => {
old_size <= header_size + new_size || header_size + 12 >= src.len()
}
None => true,
};
if previous_looks_better {
let written = compress_using_ctable_mode(
dst,
src,
&previous.entries,
previous.table_log as u32,
stream_mode,
);
if written != 0 && written < src.len().saturating_sub(1) {
return Ok(Some(PreferredTableCompression {
written,
reused_table: true,
table: *previous,
}));
}
}
}
let Some(header_size) = header_size else {
return Ok(None);
};
if header_size + 12 >= src.len() {
return Ok(None);
}
let compressed_size = compress_using_ctable_mode(
&mut dst[header_size..],
src,
&workspace.ctable,
huff_log,
stream_mode,
);
if compressed_size == 0 {
return Ok(None);
}
let total = header_size + compressed_size;
if total >= src.len().saturating_sub(1) {
return Ok(None);
}
Ok(Some(PreferredTableCompression {
written: total,
reused_table: false,
table: new_table,
}))
}
pub(crate) fn estimate_literal_section_bytes(src: &[u8]) -> Option<usize> {
if src.is_empty() {
return Some(0);
}
let mut workspace = CompressWorkspace::default();
let mut max_symbol_value = SYMBOLVALUE_MAX as u32;
let largest = count_wksp(
&mut workspace.count,
&mut max_symbol_value,
src,
&mut workspace.hist,
)
.ok()?;
if largest as usize == src.len() {
return Some(1);
}
if largest as usize <= (src.len() >> 7) + 4 {
return None;
}
let huff_log = optimal_table_log(TABLELOG_DEFAULT as u32, src.len(), max_symbol_value);
let huff_log = build_ctable(
&mut workspace.ctable,
&workspace.count,
max_symbol_value,
huff_log,
&mut workspace.build,
)
.ok()?;
let header_size = write_ctable(
&mut [0u8; 256],
&workspace.ctable,
max_symbol_value,
huff_log,
&mut workspace.weights,
)
.ok()?;
let data_size = estimate_compressed_size(&workspace.ctable, &workspace.count, max_symbol_value);
let jump_table = if src.len() >= 256 { 6 } else { 0 };
Some(header_size + data_size + jump_table)
}
pub(crate) fn estimate_literal_section_bytes_with_repeat(
src: &[u8],
previous: Option<&CTableX1>,
) -> Option<usize> {
if src.is_empty() {
return Some(0);
}
let mut workspace = CompressWorkspace::default();
let mut max_symbol_value = SYMBOLVALUE_MAX as u32;
let largest = count_wksp(
&mut workspace.count,
&mut max_symbol_value,
src,
&mut workspace.hist,
)
.ok()?;
if largest as usize == src.len() {
return Some(1);
}
if largest as usize <= (src.len() >> 7) + 4 {
return None;
}
let previous = previous.filter(|table| {
table.table_log > 0
&& validate_ctable_counts(&table.entries, &workspace.count, max_symbol_value)
});
let huff_log = optimal_table_log(TABLELOG_DEFAULT as u32, src.len(), max_symbol_value);
let huff_log = build_ctable(
&mut workspace.ctable,
&workspace.count,
max_symbol_value,
huff_log,
&mut workspace.build,
)
.ok()?;
let header_size = write_ctable(
&mut [0u8; 256],
&workspace.ctable,
max_symbol_value,
huff_log,
&mut workspace.weights,
)
.ok()?;
let new_data_size =
estimate_compressed_size(&workspace.ctable, &workspace.count, max_symbol_value);
let jump_table = if src.len() >= 256 { 6 } else { 0 };
if let Some(prev) = previous {
let old_data_size =
estimate_compressed_size(&prev.entries, &workspace.count, max_symbol_value);
if old_data_size < src.len()
&& (old_data_size <= header_size + new_data_size || header_size + 12 >= src.len())
{
return Some(old_data_size + jump_table);
}
}
Some(header_size + new_data_size + jump_table)
}
fn validate_ctable_counts(
ctable: &[CElt; SYMBOLVALUE_MAX + 1],
count: &[u32; SYMBOLVALUE_MAX + 1],
max_symbol_value: u32,
) -> bool {
for symbol in 0..=max_symbol_value as usize {
if count[symbol] > 0 && ctable[symbol].nb_bits == 0 {
return false;
}
}
true
}
pub(crate) fn compress_into(dst: &mut [u8], src: &[u8]) -> Result<usize> {
Ok(compress_prefer_existing_table_into(dst, src, None)?.map_or(0, |result| result.written))
}
#[inline(always)]
fn encode_symbol(bit_c: &mut BitCStream<'_>, symbol: u8, ctable: &[CElt; SYMBOLVALUE_MAX + 1]) {
let entry = ctable[symbol as usize];
bit_c.add_bits_fast(entry.val.into(), entry.nb_bits as u32);
}
#[inline(always)]
fn flush_bits_1(bit_c: &mut BitCStream<'_>) {
if CONTAINER_BITS < (TABLELOG_MAX * 2 + 7) as u32 {
bit_c.flush_bits();
}
}
#[inline(always)]
fn flush_bits_2(bit_c: &mut BitCStream<'_>) {
if CONTAINER_BITS < (TABLELOG_MAX * 4 + 7) as u32 {
bit_c.flush_bits();
}
}
fn compress_1x_using_ctable(
dst: &mut [u8],
src: &[u8],
ctable: &[CElt; SYMBOLVALUE_MAX + 1],
table_log: u32,
) -> usize {
let mut packed = [0u64; SYMBOLVALUE_MAX + 1];
for i in 0..=SYMBOLVALUE_MAX {
let nb = ctable[i].nb_bits as u32;
let val = ctable[i].val as u64;
if nb > 0 {
packed[i] = (val << (64 - nb)) | nb as u64;
}
}
compress_1x_packed(dst, src, &packed, table_log)
}
#[allow(unsafe_code)]
fn compress_1x_packed(
dst: &mut [u8],
src: &[u8],
packed: &[u64; SYMBOLVALUE_MAX + 1],
table_log: u32,
) -> usize {
if dst.len() <= 8 || src.is_empty() {
return 0;
}
let tight_bound = ((src.len() * table_log as usize) >> 3) + 8;
if dst.len() < tight_bound || table_log > 11 {
return compress_1x_loop::<4, false, false>(dst, src, packed);
}
match table_log {
11 => compress_1x_loop::<5, false, true>(dst, src, packed),
10 => compress_1x_loop::<5, true, true>(dst, src, packed),
9 => compress_1x_loop::<6, false, true>(dst, src, packed),
8 => compress_1x_loop::<7, false, true>(dst, src, packed),
7 => compress_1x_loop::<8, false, true>(dst, src, packed),
_ => compress_1x_loop::<9, true, true>(dst, src, packed),
}
}
#[allow(unsafe_code)]
#[inline(always)]
fn compress_1x_loop<const K_UNROLL: usize, const K_LAST_FAST: bool, const K_FAST_FLUSH: bool>(
dst: &mut [u8],
src: &[u8],
packed: &[u64; SYMBOLVALUE_MAX + 1],
) -> usize {
let packed_ptr = packed.as_ptr();
let src_ptr = src.as_ptr();
let dst_ptr = dst.as_mut_ptr();
let end_pos = dst.len() - 8;
let mut c: u64 = 0;
let mut bp: u64 = 0;
let mut byte_pos: usize = 0;
#[inline(always)]
unsafe fn add_fast(c: &mut u64, bp: &mut u64, pt: *const u64, sp: *const u8, pos: usize) {
let elt = unsafe { *pt.add(*sp.add(pos) as usize) };
*c = c.wrapping_shr(elt as u32);
*c |= elt;
*bp = bp.wrapping_add(elt);
}
#[inline(always)]
unsafe fn add_slow(c: &mut u64, bp: &mut u64, pt: *const u64, sp: *const u8, pos: usize) {
let elt = unsafe { *pt.add(*sp.add(pos) as usize) };
let nb = elt & 0xFF;
*c = c.wrapping_shr(nb as u32);
*c |= elt & 0xFFFF_FFFF_FFFF_FF00;
*bp = bp.wrapping_add(nb);
}
#[inline(always)]
unsafe fn add_last<const FAST: bool>(
c: &mut u64,
bp: &mut u64,
pt: *const u64,
sp: *const u8,
pos: usize,
) {
unsafe {
if FAST {
add_fast(c, bp, pt, sp, pos);
} else {
add_slow(c, bp, pt, sp, pos);
}
}
}
#[inline(always)]
unsafe fn flush<const FAST: bool>(
c: &u64,
bp: &mut u64,
dp: *mut u8,
byte_pos: &mut usize,
end: usize,
) {
let nb_bits = (*bp & 0xFF) as u32;
let nb_bytes = (nb_bits >> 3) as usize;
let out = *c >> ((64u32.wrapping_sub(nb_bits)) & 63);
unsafe { core::ptr::write_unaligned(dp.add(*byte_pos) as *mut u64, out.to_le()) };
if FAST {
*byte_pos += nb_bytes;
} else {
*byte_pos = (*byte_pos + nb_bytes).min(end);
}
*bp &= 7;
}
#[inline(always)]
fn merge_index1(c0: &mut u64, bp0: &mut u64, c1: u64, bp1: u64) {
debug_assert!((bp1 & 0xFF) < 64);
*c0 = c0.wrapping_shr((bp1 & 0xFF) as u32);
*c0 |= c1;
*bp0 = bp0.wrapping_add(bp1);
}
let mut n = src.len() as isize;
unsafe {
let rem = n % K_UNROLL as isize;
if rem > 0 {
for _i in 0..rem {
n -= 1;
add_slow(&mut c, &mut bp, packed_ptr, src_ptr, n as usize);
}
flush::<K_FAST_FLUSH>(&c, &mut bp, dst_ptr, &mut byte_pos, end_pos);
}
debug_assert!((n as usize).is_multiple_of(K_UNROLL));
if !(n as usize).is_multiple_of(2 * K_UNROLL) {
for u in 1..K_UNROLL {
add_fast(&mut c, &mut bp, packed_ptr, src_ptr, (n as usize) - u);
}
add_last::<K_LAST_FAST>(
&mut c,
&mut bp,
packed_ptr,
src_ptr,
(n as usize) - K_UNROLL,
);
flush::<K_FAST_FLUSH>(&c, &mut bp, dst_ptr, &mut byte_pos, end_pos);
n -= K_UNROLL as isize;
}
debug_assert!((n as usize).is_multiple_of(2 * K_UNROLL));
while n > 0 {
for u in 1..K_UNROLL {
add_fast(&mut c, &mut bp, packed_ptr, src_ptr, (n as usize) - u);
}
add_last::<K_LAST_FAST>(
&mut c,
&mut bp,
packed_ptr,
src_ptr,
(n as usize) - K_UNROLL,
);
flush::<K_FAST_FLUSH>(&c, &mut bp, dst_ptr, &mut byte_pos, end_pos);
let mut c1: u64 = 0;
let mut bp1: u64 = 0;
for u in 1..K_UNROLL {
add_fast(
&mut c1,
&mut bp1,
packed_ptr,
src_ptr,
(n as usize) - K_UNROLL - u,
);
}
add_last::<K_LAST_FAST>(
&mut c1,
&mut bp1,
packed_ptr,
src_ptr,
(n as usize) - 2 * K_UNROLL,
);
merge_index1(&mut c, &mut bp, c1, bp1);
flush::<K_FAST_FLUSH>(&c, &mut bp, dst_ptr, &mut byte_pos, end_pos);
n -= 2 * K_UNROLL as isize;
}
c >>= 1u64;
c |= 1u64 << 63;
bp = bp.wrapping_add(1);
flush::<false>(&c, &mut bp, dst_ptr, &mut byte_pos, end_pos);
}
if byte_pos >= end_pos {
return 0;
}
byte_pos + usize::from((bp & 7) > 0)
}
#[inline(always)]
fn write_segment_length(dst: &mut [u8], offset: usize, value: usize) {
debug_assert!(value <= u16::MAX as usize);
dst[offset..offset + 2].copy_from_slice(&(value as u16).to_le_bytes());
}
fn compress_4x_using_ctable(
dst: &mut [u8],
src: &[u8],
ctable: &[CElt; SYMBOLVALUE_MAX + 1],
table_log: u32,
) -> usize {
if dst.len() < BLOCKBOUND_MIN || src.len() < 12 {
return 0;
}
let mut packed = [0u64; SYMBOLVALUE_MAX + 1];
for i in 0..=SYMBOLVALUE_MAX {
let nb = ctable[i].nb_bits as u32;
let val = ctable[i].val as u64;
if nb > 0 {
packed[i] = (val << (64 - nb)) | nb as u64;
}
}
let segment_size = src.len().div_ceil(4);
let mut op = 6usize;
let c_size1 = compress_1x_packed(&mut dst[op..], &src[..segment_size], &packed, table_log);
if c_size1 == 0 || c_size1 > u16::MAX as usize {
return 0;
}
write_segment_length(dst, 0, c_size1);
op += c_size1;
let c_size2 = compress_1x_packed(
&mut dst[op..],
&src[segment_size..segment_size * 2],
&packed,
table_log,
);
if c_size2 == 0 || c_size2 > u16::MAX as usize {
return 0;
}
write_segment_length(dst, 2, c_size2);
op += c_size2;
let c_size3 = compress_1x_packed(
&mut dst[op..],
&src[segment_size * 2..segment_size * 3],
&packed,
table_log,
);
if c_size3 == 0 || c_size3 > u16::MAX as usize {
return 0;
}
write_segment_length(dst, 4, c_size3);
op += c_size3;
let c_size4 = compress_1x_packed(&mut dst[op..], &src[segment_size * 3..], &packed, table_log);
if c_size4 == 0 {
return 0;
}
op + c_size4
}
#[allow(dead_code)]
fn compress_internal(
dst: &mut [u8],
src: &[u8],
mut max_symbol_value: u32,
mut huff_log: u32,
) -> Result<usize> {
if src.is_empty() || dst.is_empty() {
return Ok(0);
}
if src.len() > BLOCKSIZE_MAX {
return Err(Error::SrcSizeWrong);
}
if huff_log as usize > TABLELOG_MAX {
return Err(Error::TableLogTooLarge);
}
if max_symbol_value as usize > SYMBOLVALUE_MAX {
return Err(Error::MaxSymbolValueTooLarge);
}
if max_symbol_value == 0 {
max_symbol_value = SYMBOLVALUE_MAX as u32;
}
if huff_log == 0 {
huff_log = TABLELOG_DEFAULT as u32;
}
let mut workspace = CompressWorkspace::default();
let largest = count_wksp(
&mut workspace.count,
&mut max_symbol_value,
src,
&mut workspace.hist,
)?;
if largest as usize == src.len() {
return Ok(0);
}
if largest as usize <= (src.len() >> 7) + 4 {
return Ok(0);
}
huff_log = optimal_table_log(huff_log, src.len(), max_symbol_value);
huff_log = build_ctable(
&mut workspace.ctable,
&workspace.count,
max_symbol_value,
huff_log,
&mut workspace.build,
)?;
workspace.ctable[(max_symbol_value as usize + 1)..].fill(CElt::default());
let header_size = match write_ctable(
dst,
&workspace.ctable,
max_symbol_value,
huff_log,
&mut workspace.weights,
) {
Ok(size) => size,
Err(Error::Generic) => return Ok(0),
Err(err) => return Err(err),
};
if header_size + 12 >= src.len() {
return Ok(0);
}
let compressed_size =
compress_4x_using_ctable(&mut dst[header_size..], src, &workspace.ctable, huff_log);
if compressed_size == 0 {
return Ok(0);
}
let total = header_size + compressed_size;
if total >= src.len().saturating_sub(1) {
return Ok(0);
}
Ok(total)
}
fn estimate_compressed_size(
ctable: &[CElt; SYMBOLVALUE_MAX + 1],
count: &[u32; SYMBOLVALUE_MAX + 1],
max_symbol_value: u32,
) -> usize {
let mut nb_bits = 0usize;
for symbol in 0..=max_symbol_value as usize {
nb_bits += ctable[symbol].nb_bits as usize * count[symbol] as usize;
}
nb_bits >> 3
}
fn optimal_table_log(max_table_log: u32, src_size: usize, max_symbol_value: u32) -> u32 {
debug_assert!(src_size > 1);
let mut table_log = max_table_log;
let max_bits_src = highbit32((src_size - 1) as u32).saturating_sub(1);
let min_bits_src = highbit32(src_size as u32) + 1;
let min_bits_symbols = highbit32(max_symbol_value) + 2;
let min_bits = cmp::min(min_bits_src, min_bits_symbols);
if max_bits_src < table_log {
table_log = max_bits_src;
}
if min_bits > table_log {
table_log = min_bits;
}
table_log.clamp(5, TABLELOG_MAX as u32)
}
fn optimal_table_log_search(
max_table_log: u32,
count: &[u32; SYMBOLVALUE_MAX + 1],
max_symbol_value: u32,
) -> u32 {
let cardinality = count[..=max_symbol_value as usize]
.iter()
.filter(|&&c| c > 0)
.count() as u32;
let min_table_log = if cardinality == 0 {
1
} else {
highbit32(cardinality) + 1
};
let mut opt_size = usize::MAX - 1;
let mut opt_log = max_table_log;
let mut ctable = [CElt::default(); SYMBOLVALUE_MAX + 1];
let mut build_ws = BuildCTableWorkspace::default();
let mut weight_ws = WeightCompressionWorkspace::default();
for log_guess in min_table_log..=max_table_log {
let Ok(max_bits) = build_ctable(
&mut ctable,
count,
max_symbol_value,
log_guess,
&mut build_ws,
) else {
continue;
};
if max_bits < log_guess && log_guess > min_table_log {
break;
}
let data_size = estimate_compressed_size(&ctable, count, max_symbol_value);
let header_size = match write_ctable(
&mut [0u8; 256],
&ctable,
max_symbol_value,
max_bits,
&mut weight_ws,
) {
Ok(s) => s,
Err(_) => continue,
};
let new_size = data_size + header_size;
if new_size > opt_size + 1 {
break;
}
if new_size < opt_size {
opt_size = new_size;
opt_log = log_guess;
}
}
opt_log
}
fn read_node(nodes: &[NodeElt; CTABLE_WORKSPACE_SIZE_U32], idx: i32) -> NodeElt {
if idx < 0 {
nodes[0]
} else {
nodes[idx as usize + 1]
}
}
fn write_node_mut(nodes: &mut [NodeElt; CTABLE_WORKSPACE_SIZE_U32], idx: usize) -> &mut NodeElt {
&mut nodes[idx + 1]
}
fn rank_index(count: u32) -> u32 {
if count < RANK_POSITION_DISTINCT_COUNT_CUTOFF {
count
} else {
highbit32(count) + RANK_POSITION_LOG_BUCKETS_BEGIN
}
}
fn insertion_sort_nodes(nodes: &mut [NodeElt], low: isize, high: isize) {
let size = high - low + 1;
for i in 1..size {
let key = nodes[(low + i) as usize];
let mut j = i - 1;
while j >= 0 && nodes[(low + j) as usize].count < key.count {
nodes[(low + j + 1) as usize] = nodes[(low + j) as usize];
j -= 1;
}
nodes[(low + j + 1) as usize] = key;
}
}
fn partition_nodes(nodes: &mut [NodeElt], low: isize, high: isize) -> isize {
let pivot = nodes[high as usize].count;
let mut boundary = low - 1;
for j in low..high {
if nodes[j as usize].count > pivot {
boundary += 1;
nodes.swap(boundary as usize, j as usize);
}
}
nodes.swap((boundary + 1) as usize, high as usize);
boundary + 1
}
fn quick_sort_nodes(nodes: &mut [NodeElt], mut low: isize, mut high: isize) {
const INSERTION_SORT_THRESHOLD: isize = 8;
if high - low < INSERTION_SORT_THRESHOLD {
insertion_sort_nodes(nodes, low, high);
return;
}
while low < high {
let pivot = partition_nodes(nodes, low, high);
if pivot - low < high - pivot {
quick_sort_nodes(nodes, low, pivot - 1);
low = pivot + 1;
} else {
quick_sort_nodes(nodes, pivot + 1, high);
high = pivot - 1;
}
}
}
fn sort_nodes(
nodes: &mut [NodeElt; CTABLE_WORKSPACE_SIZE_U32],
count: &[u32; SYMBOLVALUE_MAX + 1],
max_symbol_value: u32,
rank_position: &mut [RankPos; RANK_POSITION_TABLE_SIZE],
) {
rank_position.fill(RankPos::default());
for &c in &count[..=max_symbol_value as usize] {
rank_position[rank_index(c) as usize].base += 1;
}
for n in (1..RANK_POSITION_TABLE_SIZE).rev() {
rank_position[n - 1].base += rank_position[n].base;
rank_position[n - 1].current = rank_position[n - 1].base;
}
for (symbol, &c) in count[..=max_symbol_value as usize].iter().enumerate() {
let rank = rank_index(c) as usize + 1;
let position = rank_position[rank].current as usize;
rank_position[rank].current += 1;
nodes[position + 1].count = c;
nodes[position + 1].byte = symbol as u8;
}
for n in RANK_POSITION_DISTINCT_COUNT_CUTOFF as usize..RANK_POSITION_TABLE_SIZE - 1 {
let bucket_size = (rank_position[n].current - rank_position[n].base) as isize;
let bucket_start = rank_position[n].base as usize;
if bucket_size > 1 {
quick_sort_nodes(&mut nodes[bucket_start + 1..], 0, bucket_size - 1);
}
}
}
fn set_max_height(
nodes: &mut [NodeElt; CTABLE_WORKSPACE_SIZE_U32],
last_non_null: usize,
max_nb_bits: u32,
) -> u32 {
let largest_bits = nodes[last_non_null + 1].nb_bits as u32;
if largest_bits <= max_nb_bits {
return largest_bits;
}
let mut total_cost = 0i32;
let base_cost = 1i32 << (largest_bits - max_nb_bits);
let mut n = last_non_null as i32;
while read_node(nodes, n).nb_bits as u32 > max_nb_bits {
let node = read_node(nodes, n);
total_cost += base_cost - (1i32 << (largest_bits - node.nb_bits as u32));
write_node_mut(nodes, n as usize).nb_bits = max_nb_bits as u8;
n -= 1;
}
while n >= 0 && read_node(nodes, n).nb_bits as u32 == max_nb_bits {
n -= 1;
}
total_cost >>= largest_bits - max_nb_bits;
const NO_SYMBOL: usize = usize::MAX;
let mut rank_last = [NO_SYMBOL; TABLELOG_MAX + 2];
let mut current_nb_bits = max_nb_bits;
let mut pos = n;
while pos >= 0 {
let nb_bits = read_node(nodes, pos).nb_bits as u32;
if nb_bits < current_nb_bits {
current_nb_bits = nb_bits;
rank_last[(max_nb_bits - current_nb_bits) as usize] = pos as usize;
}
pos -= 1;
}
while total_cost > 0 {
let mut n_bits_to_decrease = highbit32(total_cost as u32) + 1;
while n_bits_to_decrease > 1 {
let high_pos = rank_last[n_bits_to_decrease as usize];
let low_pos = rank_last[(n_bits_to_decrease - 1) as usize];
if high_pos == NO_SYMBOL {
n_bits_to_decrease -= 1;
continue;
}
if low_pos == NO_SYMBOL {
break;
}
let high_total = nodes[high_pos + 1].count;
let low_total = 2 * nodes[low_pos + 1].count;
if high_total <= low_total {
break;
}
n_bits_to_decrease -= 1;
}
while n_bits_to_decrease as usize <= TABLELOG_MAX
&& rank_last[n_bits_to_decrease as usize] == NO_SYMBOL
{
n_bits_to_decrease += 1;
}
total_cost -= 1 << (n_bits_to_decrease - 1);
if rank_last[(n_bits_to_decrease - 1) as usize] == NO_SYMBOL {
rank_last[(n_bits_to_decrease - 1) as usize] = rank_last[n_bits_to_decrease as usize];
}
let idx = rank_last[n_bits_to_decrease as usize] + 1;
nodes[idx].nb_bits += 1;
if rank_last[n_bits_to_decrease as usize] == 0 {
rank_last[n_bits_to_decrease as usize] = NO_SYMBOL;
} else {
rank_last[n_bits_to_decrease as usize] -= 1;
if nodes[rank_last[n_bits_to_decrease as usize] + 1].nb_bits as u32
!= max_nb_bits - n_bits_to_decrease
{
rank_last[n_bits_to_decrease as usize] = NO_SYMBOL;
}
}
}
while total_cost < 0 {
if rank_last[1] == NO_SYMBOL {
while n >= 0 && read_node(nodes, n).nb_bits as u32 == max_nb_bits {
n -= 1;
}
nodes[n as usize + 2].nb_bits -= 1;
rank_last[1] = n as usize + 1;
total_cost += 1;
continue;
}
nodes[rank_last[1] + 2].nb_bits -= 1;
rank_last[1] += 1;
total_cost += 1;
}
max_nb_bits
}
fn build_ctable(
tree: &mut [CElt; SYMBOLVALUE_MAX + 1],
count: &[u32; SYMBOLVALUE_MAX + 1],
max_symbol_value: u32,
mut max_nb_bits: u32,
workspace: &mut BuildCTableWorkspace,
) -> Result<u32> {
if max_nb_bits == 0 {
max_nb_bits = TABLELOG_DEFAULT as u32;
}
if max_symbol_value as usize > SYMBOLVALUE_MAX {
return Err(Error::MaxSymbolValueTooLarge);
}
workspace.nodes.fill(NodeElt::default());
sort_nodes(
&mut workspace.nodes,
count,
max_symbol_value,
&mut workspace.rank_position,
);
let mut non_null_rank = max_symbol_value as i32;
while workspace.nodes[non_null_rank as usize + 1].count == 0 {
non_null_rank -= 1;
}
let mut low_s = non_null_rank;
let mut node_nb = STARTNODE as i32;
let node_root = node_nb + low_s - 1;
let mut low_n = node_nb;
write_node_mut(&mut workspace.nodes, node_nb as usize).count =
read_node(&workspace.nodes, low_s).count + read_node(&workspace.nodes, low_s - 1).count;
write_node_mut(&mut workspace.nodes, low_s as usize).parent = node_nb as u16;
write_node_mut(&mut workspace.nodes, (low_s - 1) as usize).parent = node_nb as u16;
node_nb += 1;
low_s -= 2;
for n in node_nb..=node_root {
write_node_mut(&mut workspace.nodes, n as usize).count = 1u32 << 30;
}
workspace.nodes[0].count = 1u32 << 31;
while node_nb <= node_root {
let n1 = if read_node(&workspace.nodes, low_s).count
< read_node(&workspace.nodes, low_n).count
{
let value = low_s;
low_s -= 1;
value
} else {
let value = low_n;
low_n += 1;
value
};
let n2 = if read_node(&workspace.nodes, low_s).count
< read_node(&workspace.nodes, low_n).count
{
let value = low_s;
low_s -= 1;
value
} else {
let value = low_n;
low_n += 1;
value
};
write_node_mut(&mut workspace.nodes, node_nb as usize).count =
read_node(&workspace.nodes, n1).count + read_node(&workspace.nodes, n2).count;
write_node_mut(&mut workspace.nodes, n1 as usize).parent = node_nb as u16;
write_node_mut(&mut workspace.nodes, n2 as usize).parent = node_nb as u16;
node_nb += 1;
}
write_node_mut(&mut workspace.nodes, node_root as usize).nb_bits = 0;
for n in (STARTNODE as i32..node_root).rev() {
let parent = read_node(&workspace.nodes, n).parent as i32;
write_node_mut(&mut workspace.nodes, n as usize).nb_bits =
read_node(&workspace.nodes, parent).nb_bits + 1;
}
for n in 0..=non_null_rank as usize {
let parent = workspace.nodes[n + 1].parent as i32;
workspace.nodes[n + 1].nb_bits = read_node(&workspace.nodes, parent).nb_bits + 1;
}
max_nb_bits = set_max_height(&mut workspace.nodes, non_null_rank as usize, max_nb_bits);
let mut nb_per_rank = [0u16; TABLELOG_MAX + 1];
let mut val_per_rank = [0u16; TABLELOG_MAX + 1];
let alphabet_size = max_symbol_value as usize + 1;
if max_nb_bits as usize > TABLELOG_MAX {
return Err(Error::Generic);
}
for n in 0..=non_null_rank as usize {
nb_per_rank[workspace.nodes[n + 1].nb_bits as usize] += 1;
}
let mut min = 0u16;
for n in (1..=max_nb_bits as usize).rev() {
val_per_rank[n] = min;
min = (min + nb_per_rank[n]) >> 1;
}
for n in 0..alphabet_size {
tree[workspace.nodes[n + 1].byte as usize].nb_bits = workspace.nodes[n + 1].nb_bits;
}
for item in tree.iter_mut().take(alphabet_size) {
item.val = val_per_rank[item.nb_bits as usize];
val_per_rank[item.nb_bits as usize] += 1;
}
Ok(max_nb_bits)
}
fn write_ctable(
dst: &mut [u8],
ctable: &[CElt; SYMBOLVALUE_MAX + 1],
max_symbol_value: u32,
huff_log: u32,
workspace: &mut WeightCompressionWorkspace,
) -> Result<usize> {
if dst.is_empty() {
return Err(Error::DstSizeTooSmall);
}
let mut bits_to_weight = [0u8; TABLELOG_MAX + 1];
let mut huff_weight = [0u8; SYMBOLVALUE_MAX + 1];
for n in 1..=huff_log as usize {
bits_to_weight[n] = (huff_log as usize + 1 - n) as u8;
}
for n in 0..max_symbol_value as usize {
huff_weight[n] = bits_to_weight[ctable[n].nb_bits as usize];
}
let compressed_size = compress_weights(
&mut dst[1..],
&huff_weight[..max_symbol_value as usize],
workspace,
)?;
if compressed_size > 1 && compressed_size < (max_symbol_value as usize / 2) {
dst[0] = compressed_size as u8;
return Ok(compressed_size + 1);
}
write_ctable_raw(dst, &huff_weight, max_symbol_value)
}
fn compress_weights(
dst: &mut [u8],
weight_table: &[u8],
workspace: &mut WeightCompressionWorkspace,
) -> Result<usize> {
if weight_table.len() <= 1 {
return Ok(0);
}
workspace.count.fill(0);
let mut max_symbol_value = 0u32;
let mut max_count = 0u32;
for &weight in weight_table {
let slot = workspace
.count
.get_mut(weight as usize)
.ok_or(Error::Generic)?;
*slot += 1;
max_count = max_count.max(*slot);
max_symbol_value = max_symbol_value.max(weight as u32);
}
while max_symbol_value > 0 && workspace.count[max_symbol_value as usize] == 0 {
max_symbol_value -= 1;
}
if max_count as usize == weight_table.len() {
return Ok(1);
}
if max_count == 1 {
return Ok(0);
}
let table_log = fse::optimal_table_log(
MAX_FSE_TABLELOG_FOR_HUFF_HEADER as u32,
weight_table.len(),
max_symbol_value,
);
fse::normalize_count(
&mut workspace.norm,
table_log,
&workspace.count,
weight_table.len(),
max_symbol_value,
false,
)?;
let header_size = fse::write_ncount(dst, &workspace.norm, max_symbol_value, table_log)?;
fse::build_ctable(
&mut workspace.ctable,
&workspace.norm,
max_symbol_value,
table_log,
)?;
let compressed_size =
fse::compress_using_ctable(&mut dst[header_size..], weight_table, &workspace.ctable)?;
if compressed_size == 0 {
return Ok(0);
}
Ok(header_size + compressed_size)
}
fn write_ctable_raw(
dst: &mut [u8],
huff_weight: &[u8; SYMBOLVALUE_MAX + 1],
max_symbol_value: u32,
) -> Result<usize> {
if max_symbol_value > 127 {
return Err(Error::Generic);
}
if dst.is_empty() {
return Err(Error::DstSizeTooSmall);
}
let raw_size = (max_symbol_value as usize).div_ceil(2) + 1;
if raw_size > dst.len() || max_symbol_value == 0 {
return Err(Error::DstSizeTooSmall);
}
dst[0] = 128u8 + (max_symbol_value as u8 - 1);
let mut huff_weight = *huff_weight;
huff_weight[max_symbol_value as usize] = 0;
for n in (0..max_symbol_value as usize).step_by(2) {
dst[(n / 2) + 1] = (huff_weight[n] << 4) | huff_weight[n + 1];
}
Ok(raw_size)
}
fn build_ctable_from_weights(
ctable: &mut [CElt; SYMBOLVALUE_MAX + 1],
huff_weight: &[u8; SYMBOLVALUE_MAX + 1],
nb_symbols: usize,
table_log: u32,
) -> Result<()> {
if table_log == 0 || table_log as usize > TABLELOG_MAX {
return Err(Error::Corruption("invalid Huff0 table log"));
}
ctable.fill(CElt::default());
let mut nb_per_rank = [0u16; TABLELOG_MAX + 1];
let mut val_per_rank = [0u16; TABLELOG_MAX + 1];
for &weight in &huff_weight[..nb_symbols] {
if weight == 0 {
continue;
}
if weight as u32 > table_log {
return Err(Error::Corruption("invalid Huff0 weight"));
}
let nb_bits = (table_log + 1 - u32::from(weight)) as usize;
if nb_bits == 0 || nb_bits > TABLELOG_MAX {
return Err(Error::Corruption("invalid Huff0 weight"));
}
nb_per_rank[nb_bits] += 1;
}
let mut min = 0u16;
for n in (1..=table_log as usize).rev() {
val_per_rank[n] = min;
min = (min + nb_per_rank[n]) >> 1;
}
for symbol in 0..nb_symbols {
if huff_weight[symbol] == 0 {
continue;
}
let nb_bits = (table_log + 1 - u32::from(huff_weight[symbol])) as usize;
ctable[symbol].nb_bits = nb_bits as u8;
ctable[symbol].val = val_per_rank[nb_bits];
val_per_rank[nb_bits] += 1;
}
Ok(())
}
fn table_supports_all_symbols(ctable: &CTableX1, src: &[u8]) -> bool {
src.iter()
.all(|&symbol| ctable.entries[symbol as usize].nb_bits != 0)
}
fn table_covers_counted_symbols(
ctable: &CTableX1,
count: &[u32; SYMBOLVALUE_MAX + 1],
max_symbol_value: u32,
) -> bool {
let last = max_symbol_value as usize;
!count[..=last]
.iter()
.zip(&ctable.entries[..=last])
.any(|(&frequency, entry)| frequency != 0 && entry.nb_bits == 0)
}
#[cfg(test)]
mod tests {
use std::{fs, path::Path};
use super::*;
#[test]
fn tied_symbol_counts_take_upstream_code_lengths() {
let mut count = [0u32; SYMBOLVALUE_MAX + 1];
for (symbol, frequency) in [
(b'0', 172),
(b'1', 171),
(b'2', 169),
(b'3', 173),
(b'4', 178),
(b'5', 166),
(b'6', 176),
(b'7', 405),
(b'8', 294),
(b'9', 170),
(b'a', 169),
(b'b', 182),
(b'c', 169),
(b'd', 179),
(b'e', 171),
(b'f', 175),
] {
count[symbol as usize] = frequency;
}
let mut workspace = CompressWorkspace::default();
workspace
.build_literal_ctable(&count, b'f' as u32, TABLELOG_DEFAULT as u32)
.unwrap();
let lengths: Vec<(u8, u8)> = (b'0'..=b'f')
.filter(|symbol| count[*symbol as usize] != 0)
.map(|symbol| (symbol, workspace.ctable[symbol as usize].nb_bits))
.collect();
let expected: Vec<(u8, u8)> = [
(b'0', 4),
(b'1', 4),
(b'2', 4),
(b'3', 4),
(b'4', 4),
(b'5', 5),
(b'6', 4),
(b'7', 3),
(b'8', 4),
(b'9', 4),
(b'a', 5),
(b'b', 4),
(b'c', 4),
(b'd', 4),
(b'e', 4),
(b'f', 4),
]
.into_iter()
.collect();
assert_eq!(lengths, expected);
}
#[test]
fn decompress_special_cases() {
let mut dst = [0u8; 8];
assert_eq!(decompress_into(&mut dst, b"x").unwrap(), 8);
assert_eq!(dst, [b'x'; 8]);
let src = *b"rawblock";
let mut out = [0u8; 8];
assert_eq!(decompress_into(&mut out, &src).unwrap(), 8);
assert_eq!(out, src);
}
#[test]
fn decodes_sibling_huff0_fixture_when_present() {
let root = Path::new(env!("CARGO_MANIFEST_DIR")).join("../Huff0/tests/data");
if !root.exists() {
eprintln!("skipping Huff0 fixture test: sibling Huff0 checkout not found");
return;
}
let raw = fs::read(root.join("c_fixture_raw.bin")).unwrap();
let compressed = fs::read(root.join("c_fixture_huf.bin")).unwrap();
let mut decoded = vec![0u8; raw.len()];
let written = decompress_into(&mut decoded, &compressed).unwrap();
assert_eq!(written, raw.len());
assert_eq!(decoded, raw);
}
#[test]
fn compresses_and_roundtrips_small_alphabet_data() {
let raw = (0..12_000)
.map(|index| match index & 0x0f {
0..=8 => b'A',
9..=12 => b'B',
13..=14 => b'C',
_ => b'D',
})
.collect::<Vec<_>>();
let compressed = compress(&raw)
.unwrap()
.expect("small alphabet input should be Huff0-compressible");
let mut decoded = vec![0u8; raw.len()];
let written = decompress_into(&mut decoded, &compressed).unwrap();
assert_eq!(written, raw.len());
assert_eq!(decoded, raw);
}
#[test]
fn sparse_high_symbols_use_fse_compressed_weight_headers() {
let raw = (0..64 * 1024)
.map(|index| match index % 16 {
0..=13 => 0u8,
14 => 127u8,
_ => 255u8,
})
.collect::<Vec<_>>();
let compressed = compress(&raw)
.unwrap()
.expect("sparse high-symbol input should be Huff0-compressible");
assert!(
compressed[0] < 128,
"expected an FSE-compressed Huffman weight header, got descriptor {}",
compressed[0]
);
let mut ctable = CTableX1::default();
let ctable_header_size = read_ctable_x1(&compressed, &mut ctable).unwrap();
let mut dtable = DTableX1::default();
let dtable_header_size = read_dtable_x1(&compressed, &mut dtable).unwrap();
assert_eq!(ctable_header_size, dtable_header_size);
let mut decoded = vec![0u8; raw.len()];
let written = decompress_into(&mut decoded, &compressed).unwrap();
assert_eq!(written, raw.len());
assert_eq!(decoded, raw);
}
#[test]
fn small_dense_alphabet_keeps_raw_weight_headers() {
let raw = (0..16_000)
.map(|index| match index % 8 {
0..=3 => 0u8,
4..=5 => 1u8,
6 => 2u8,
_ => 3u8,
})
.collect::<Vec<_>>();
let compressed = compress(&raw)
.unwrap()
.expect("small dense input should be Huff0-compressible");
assert!(
compressed[0] >= 128,
"expected a raw Huffman weight header, got descriptor {}",
compressed[0]
);
let mut decoded = vec![0u8; raw.len()];
let written = decompress_into(&mut decoded, &compressed).unwrap();
assert_eq!(written, raw.len());
assert_eq!(decoded, raw);
}
#[test]
fn reuses_a_parsed_huffman_table_for_treeless_compression() {
let raw = (0..16_000)
.map(|index| match index % 7 {
0..=3 => b'a',
4 => b'b',
5 => b'c',
_ => b'd',
})
.collect::<Vec<_>>();
let compressed = compress(&raw)
.unwrap()
.expect("test input should be Huff0-compressible");
let mut ctable = CTableX1::default();
let ctable_header_size = read_ctable_x1(&compressed, &mut ctable).unwrap();
let mut dtable = DTableX1::default();
let dtable_header_size = read_dtable_x1(&compressed, &mut dtable).unwrap();
assert_eq!(ctable_header_size, dtable_header_size);
let treeless = compress_with_table(&raw, &ctable)
.unwrap()
.expect("parsed table should support the same alphabet");
let mut decoded = vec![0u8; raw.len()];
let dtable = HuffmanDTable::Single(dtable);
let written = decompress_4x_using_dtable(&mut decoded, &treeless, &dtable).unwrap();
assert_eq!(written, raw.len());
assert_eq!(decoded, raw);
}
#[test]
fn prefer_existing_table_compresses_once_with_reused_table() {
let raw = (0..16_000)
.map(|index| match index % 7 {
0..=3 => b'a',
4 => b'b',
5 => b'c',
_ => b'd',
})
.collect::<Vec<_>>();
let compressed = compress(&raw)
.unwrap()
.expect("test input should be Huff0-compressible");
let mut ctable = CTableX1::default();
let ctable_header_size = read_ctable_x1(&compressed, &mut ctable).unwrap();
let mut dtable = DTableX1::default();
let dtable_header_size = read_dtable_x1(&compressed, &mut dtable).unwrap();
assert_eq!(ctable_header_size, dtable_header_size);
let mut dst = vec![0u8; compress_bound(raw.len())];
let preferred = compress_prefer_existing_table_into(&mut dst, &raw, Some(&ctable))
.unwrap()
.expect("existing table should remain usable");
assert!(preferred.reused_table);
assert_eq!(preferred.table.table_log, ctable.table_log);
let mut decoded = vec![0u8; raw.len()];
let dtable = HuffmanDTable::Single(dtable);
let written =
decompress_4x_using_dtable(&mut decoded, &dst[..preferred.written], &dtable).unwrap();
assert_eq!(written, raw.len());
assert_eq!(decoded, raw);
}
#[allow(unsafe_code)]
fn compress_1x_reference(
dst: &mut [u8],
src: &[u8],
ctable: &[super::CElt; super::SYMBOLVALUE_MAX + 1],
) -> usize {
if dst.len() < 8 {
return 0;
}
let mut bit_c = match super::BitCStream::new(dst) {
Ok(s) => s,
Err(_) => return 0,
};
let src_ptr = src.as_ptr();
let mut n = src.len() & !3;
unsafe {
match src.len() & 3 {
3 => {
super::encode_symbol(&mut bit_c, *src_ptr.add(n + 2), ctable);
super::encode_symbol(&mut bit_c, *src_ptr.add(n + 1), ctable);
super::encode_symbol(&mut bit_c, *src_ptr.add(n), ctable);
bit_c.flush_bits_unchecked();
}
2 => {
super::encode_symbol(&mut bit_c, *src_ptr.add(n + 1), ctable);
super::encode_symbol(&mut bit_c, *src_ptr.add(n), ctable);
bit_c.flush_bits_unchecked();
}
1 => {
super::encode_symbol(&mut bit_c, *src_ptr.add(n), ctable);
bit_c.flush_bits_unchecked();
}
_ => {}
}
while n > 0 {
super::encode_symbol(&mut bit_c, *src_ptr.add(n - 1), ctable);
super::encode_symbol(&mut bit_c, *src_ptr.add(n - 2), ctable);
super::encode_symbol(&mut bit_c, *src_ptr.add(n - 3), ctable);
super::encode_symbol(&mut bit_c, *src_ptr.add(n - 4), ctable);
bit_c.flush_bits_unchecked();
n -= 4;
}
}
bit_c.close()
}
#[test]
fn packed_matches_reference_encoder() {
for &extra in &[0, 1, 2, 3] {
let size = 200 + extra;
let src: Vec<u8> = (0..size)
.map(|i| match i % 5 {
0 => 0,
1 => 1,
2 => 2,
3 => 0,
_ => 1,
})
.collect();
let mut ctable = [super::CElt::default(); super::SYMBOLVALUE_MAX + 1];
ctable[0] = super::CElt { val: 0, nb_bits: 1 };
ctable[1] = super::CElt { val: 2, nb_bits: 2 };
ctable[2] = super::CElt { val: 3, nb_bits: 2 };
let mut ref_dst = vec![0u8; src.len() + 64];
let mut new_dst = vec![0u8; src.len() + 64];
let ref_len = compress_1x_reference(&mut ref_dst, &src, &ctable);
let new_len = super::compress_1x_using_ctable(&mut new_dst, &src, &ctable, 2);
assert_eq!(
new_len, ref_len,
"size={size}: length mismatch new={new_len} ref={ref_len}"
);
if new_dst[..new_len] != ref_dst[..ref_len] {
for i in 0..new_len {
if new_dst[i] != ref_dst[i] {
panic!(
"size={size}: first mismatch at byte {i}: new=0x{:02x} ref=0x{:02x}",
new_dst[i], ref_dst[i]
);
}
}
}
}
let src: Vec<u8> = (0..12_000)
.map(|i| match i & 0x0f {
0..=8 => b'A',
9..=12 => b'B',
13..=14 => b'C',
_ => b'D',
})
.collect();
let mut ctable = [super::CElt::default(); super::SYMBOLVALUE_MAX + 1];
ctable[b'A' as usize] = super::CElt { val: 0, nb_bits: 1 };
ctable[b'B' as usize] = super::CElt { val: 2, nb_bits: 2 };
ctable[b'C' as usize] = super::CElt { val: 6, nb_bits: 3 };
ctable[b'D' as usize] = super::CElt { val: 7, nb_bits: 3 };
let mut ref_dst = vec![0u8; src.len() + 64];
let mut new_dst = vec![0u8; src.len() + 64];
let ref_len = compress_1x_reference(&mut ref_dst, &src, &ctable);
let new_len = super::compress_1x_using_ctable(&mut new_dst, &src, &ctable, 3);
assert_eq!(
new_len, ref_len,
"large: length mismatch new={new_len} ref={ref_len}"
);
if new_dst[..new_len] != ref_dst[..ref_len] {
for i in 0..new_len {
if new_dst[i] != ref_dst[i] {
panic!(
"large: first mismatch at byte {i}: new=0x{:02x} ref=0x{:02x}",
new_dst[i], ref_dst[i]
);
}
}
}
}
#[test]
fn table_log_twelve_fills_the_decode_table_without_overrunning_it() {
let header = [
0x9f, 0xa4, 0x00, 0x00, 0x00, 0x00, 0x01, 0x37, 0x00, 0x00, 0x00, 0x01, 0x00, 0x90,
0x60, 0x28, 0xb5,
];
let mut dtable = DTableX1::default();
let consumed = read_dtable_x1(&header, &mut dtable).expect("table log 12 is representable");
assert_eq!(consumed, header.len());
assert_eq!(dtable.table_log, 12);
assert_eq!(dtable.entries.len(), 1 << TABLELOG_MAX);
assert!(
dtable.entries.iter().all(|entry| entry.nb_bits != 0),
"every slot of a full table log 12 table should have been written"
);
let mut double = DTableX2::default();
let consumed = read_dtable_x2(&header, &mut double).expect("table log 12 is representable");
assert_eq!(consumed, header.len());
assert_eq!(double.table_log, 12);
assert!(
double.entries.iter().all(|entry| entry.nb_bits != 0),
"every slot of a full table log 12 double-symbol table should have been written"
);
}
#[test]
fn four_stream_decode_rejects_outputs_too_small_to_split() {
let mut dtable = DTableX1::default();
read_dtable_x1(&[0x80, 0x10], &mut dtable).expect("two-symbol table is valid");
let dtable = HuffmanDTable::Single(dtable);
let src = [0x01, 0x00, 0x01, 0x00, 0x01, 0x00, 0x01, 0x01, 0x01, 0x01];
let accepted: Vec<usize> = (0..6)
.filter(|&len| {
let mut dst = vec![0u8; len];
decompress_4x_using_dtable(&mut dst, &src, &dtable).is_ok()
})
.collect();
assert!(
accepted.is_empty(),
"outputs of {accepted:?} bytes cannot be split across four streams, \
but were accepted"
);
}
fn incompressible_bytes(len: usize) -> Vec<u8> {
let mut state = 0x2545_f491_4f6c_dd1du64;
(0..len)
.map(|_| {
state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
(state >> 33) as u8
})
.collect()
}
fn english_like_bytes(len: usize) -> Vec<u8> {
let phrase = b"the quick brown fox jumps over the lazy dog, and then it does so again. ";
phrase.iter().copied().cycle().take(len).collect()
}
fn compress_with(src: &[u8], compressibility: Compressibility) -> Option<usize> {
let mut dst = vec![0u8; compress_bound(src.len())];
let mut workspace = CompressWorkspace::default();
compress_prefer_existing_table_into_mode(
&mut dst,
src,
None,
StreamMode::Four,
TableDepth::Estimated,
compressibility,
&mut workspace,
)
.expect("compression must not error")
.map(|choice| choice.written)
}
#[test]
fn sampled_check_agrees_with_the_full_count() {
let incompressible = incompressible_bytes(64 * 1024);
assert_eq!(
compress_with(&incompressible, Compressibility::Unknown),
None
);
assert_eq!(
compress_with(&incompressible, Compressibility::Suspect),
None
);
let compressible = english_like_bytes(64 * 1024);
let full = compress_with(&compressible, Compressibility::Unknown)
.expect("english-like text compresses");
assert_eq!(
compress_with(&compressible, Compressibility::Suspect),
Some(full),
"the sample must not turn away literals the full count would code"
);
}
#[test]
fn sampled_check_is_inert_below_ten_samples() {
let size = SUSPECT_INCOMPRESSIBLE_SAMPLE_SIZE * SUSPECT_INCOMPRESSIBLE_SAMPLE_RATIO;
let mut count = [0u32; SYMBOLVALUE_MAX + 1];
let just_under = incompressible_bytes(size - 1);
assert!(!looks_incompressible_from_sample(&just_under, &mut count));
let just_over = incompressible_bytes(size);
assert!(looks_incompressible_from_sample(&just_over, &mut count));
}
fn alphabets_of_varying_depth() -> Vec<(&'static str, Vec<u8>)> {
let skewed = (0..40_000u32)
.map(
|index| match (index.wrapping_mul(2_654_435_761) >> 24) % 100 {
0..=74 => b'e',
75..=89 => b't',
90..=96 => b'a',
97..=98 => b'o',
_ => b'z',
},
)
.collect::<Vec<_>>();
let two_symbols = (0..20_000u32)
.map(|index| if index % 7 == 0 { 1u8 } else { 0u8 })
.collect::<Vec<_>>();
let full_byte_range = (0..60_000u32)
.map(|index| {
let spread = (index.wrapping_mul(2_246_822_519) >> 20) as u8;
if index % 3 == 0 { spread >> 2 } else { spread }
})
.collect::<Vec<_>>();
let sparse_high = (0..30_000u32)
.map(|index| match index % 23 {
0..=17 => 0u8,
18..=20 => 128u8,
21 => 200u8,
_ => 255u8,
})
.collect::<Vec<_>>();
vec![
("skewed five-symbol", skewed),
("two symbols", two_symbols),
("full byte range", full_byte_range),
("sparse high symbols", sparse_high),
]
}
#[test]
fn both_decode_table_shapes_decode_a_stream_identically() {
for (name, raw) in alphabets_of_varying_depth() {
let compressed = compress(&raw)
.unwrap()
.unwrap_or_else(|| panic!("{name} should be Huff0-compressible"));
let mut single = DTableX1::default();
let single_header = read_dtable_x1(&compressed, &mut single).unwrap();
let mut double = DTableX2::default();
let double_header = read_dtable_x2(&compressed, &mut double).unwrap();
assert_eq!(
single_header, double_header,
"{name}: both shapes read the same description"
);
let streams = &compressed[single_header..];
let mut by_single = vec![0u8; raw.len()];
decompress_4x1_using_dtable(&mut by_single, streams, &single).unwrap();
let mut by_double = vec![0u8; raw.len()];
decompress_4x2_using_dtable(&mut by_double, streams, &double).unwrap();
assert_eq!(by_single, raw, "{name}: single-symbol decode");
assert_eq!(by_double, raw, "{name}: double-symbol decode");
}
}
#[test]
fn the_double_symbol_table_decodes_a_single_stream() {
for (name, raw) in alphabets_of_varying_depth() {
let mut ctable = CTableX1::default();
let compressed = compress(&raw)
.unwrap()
.unwrap_or_else(|| panic!("{name} should be Huff0-compressible"));
let header_size = read_ctable_x1(&compressed, &mut ctable).unwrap();
let single_stream = compress_with_table_mode(&raw, &ctable, StreamMode::Single)
.unwrap()
.unwrap_or_else(|| panic!("{name} should re-encode as one stream"));
let mut double = DTableX2::default();
assert_eq!(
read_dtable_x2(&compressed, &mut double).unwrap(),
header_size
);
let mut decoded = vec![0u8; raw.len()];
decompress_1x2_using_dtable(&mut decoded, &single_stream, &double).unwrap();
assert_eq!(decoded, raw, "{name}: single-stream double-symbol decode");
}
}
#[test]
fn a_shallow_description_is_expanded_so_entries_hold_symbol_pairs() {
let raw = (0..40_000u32)
.map(
|index| match (index.wrapping_mul(2_654_435_761) >> 25) % 8 {
0..=4 => b'x',
5..=6 => b'y',
_ => b'z',
},
)
.collect::<Vec<_>>();
let compressed = compress(&raw).unwrap().expect("compressible");
let mut single = DTableX1::default();
read_dtable_x1(&compressed, &mut single).unwrap();
let mut double = DTableX2::default();
read_dtable_x2(&compressed, &mut double).unwrap();
assert!(
(single.table_log as usize) <= DECODER_FAST_TABLELOG,
"a three-symbol alphabet should not need the full table depth"
);
assert_eq!(
double.table_log as usize, DECODER_FAST_TABLELOG,
"a shallow description should be expanded to the fast depth"
);
let live = &double.entries[..1 << double.table_log];
let paired = live.iter().filter(|entry| entry.length == 2).count();
assert!(
paired * 2 > live.len(),
"expected most of the {} entries to emit a pair, got {paired}",
live.len()
);
}
#[test]
fn the_decoder_shape_selector_matches_upstreams_cost_model() {
assert!(prefers_double_symbol_decoder(32 * 1024, 18 * 1024));
assert!(!prefers_double_symbol_decoder(1024, 576));
assert!(!prefers_double_symbol_decoder(64 * 1024, 64 * 1024));
assert!(!prefers_double_symbol_decoder(0, 0));
}
#[test]
fn switching_table_shape_replaces_the_stored_table() {
let raw = (0..24_000u32)
.map(|index| (index.wrapping_mul(2_654_435_761) >> 28) as u8)
.collect::<Vec<_>>();
let compressed = compress(&raw).unwrap().expect("compressible");
let mut slot = None;
let header = read_dtable_x1(&compressed, HuffmanDTable::single_slot(&mut slot)).unwrap();
assert!(matches!(slot, Some(HuffmanDTable::Single(_))));
assert_eq!(
read_dtable_x2(&compressed, HuffmanDTable::double_slot(&mut slot)).unwrap(),
header
);
assert!(matches!(slot, Some(HuffmanDTable::Double(_))));
let table = slot.expect("installed");
let mut decoded = vec![0u8; raw.len()];
decompress_4x_using_dtable(&mut decoded, &compressed[header..], &table).unwrap();
assert_eq!(decoded, raw);
}
}