use std::sync::{Arc, OnceLock};
use std::time::{Duration, Instant};
use crate::{
decode_out::DecodeOut,
entropy::{
bitstream::{
BitCStream, BitDStreamStatus, CONTAINER_BITS, CONTAINER_BYTES, STREAM_ACCUMULATOR_MIN,
},
fse, huff0,
mem::highbit32,
},
error::{Error, Result},
literals::DecodedLiterals,
outbuf::OutBuf,
window::{ParserStrategy, SeqStore},
};
const LITERAL_LENGTH_BASELINES: [u32; 36] = [
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 18, 20, 22, 24, 28, 32, 40, 48, 64,
128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536,
];
const LITERAL_LENGTH_EXTRA_BITS: [u8; 36] = [
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 4, 6, 7, 8, 9, 10, 11,
12, 13, 14, 15, 16,
];
const MATCH_LENGTH_BASELINES: [u32; 53] = [
3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27,
28, 29, 30, 31, 32, 33, 34, 35, 37, 39, 41, 43, 47, 51, 59, 67, 83, 99, 131, 259, 515, 1027,
2051, 4099, 8195, 16387, 32771, 65539,
];
const MATCH_LENGTH_EXTRA_BITS: [u8; 53] = [
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
];
const LITERAL_LENGTH_DEFAULT_DISTRIBUTION: [i16; 36] = [
4, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 1, 1, 1, 1, 1,
-1, -1, -1, -1,
];
const OFFSET_DEFAULT_DISTRIBUTION: [i16; 29] = [
1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1,
];
const MATCH_LENGTH_DEFAULT_DISTRIBUTION: [i16; 53] = [
1, 4, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -1, -1, -1, -1, -1, -1, -1,
];
const LITERAL_LENGTH_CODE_TABLE: [u8; 64] = [
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 16, 17, 17, 18, 18, 19, 19, 20, 20,
20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22, 22, 22, 23, 23, 23, 23, 23, 23, 23, 23, 24, 24,
24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
];
const MATCH_LENGTH_CODE_TABLE: [u8; 128] = [
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25,
26, 27, 28, 29, 30, 31, 32, 32, 33, 33, 34, 34, 35, 35, 36, 36, 36, 36, 37, 37, 37, 37, 38, 38,
38, 38, 38, 38, 38, 38, 39, 39, 39, 39, 39, 39, 39, 39, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
40, 40, 40, 40, 40, 40, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 42, 42,
42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42,
42, 42, 42, 42, 42, 42,
];
const LL_DEFAULT_LOG: u32 = 6;
const OF_DEFAULT_LOG: u32 = 5;
const ML_DEFAULT_LOG: u32 = 6;
const COST_ACCURACY_LOG: u32 = 8;
const FAST_SELECTOR_REPEAT_MAX_SEQUENCES: usize = 1000;
const INVERSE_PROBABILITY_LOG256: [u16; 256] = [
0, 2048, 1792, 1642, 1536, 1453, 1386, 1329, 1280, 1236, 1197, 1162, 1130, 1100, 1073, 1047,
1024, 1001, 980, 960, 941, 923, 906, 889, 874, 859, 844, 830, 817, 804, 791, 779, 768, 756,
745, 734, 724, 714, 704, 694, 685, 676, 667, 658, 650, 642, 633, 626, 618, 610, 603, 595, 588,
581, 574, 567, 561, 554, 548, 542, 535, 529, 523, 517, 512, 506, 500, 495, 489, 484, 478, 473,
468, 463, 458, 453, 448, 443, 438, 434, 429, 424, 420, 415, 411, 407, 402, 398, 394, 390, 386,
382, 377, 373, 370, 366, 362, 358, 354, 350, 347, 343, 339, 336, 332, 329, 325, 322, 318, 315,
311, 308, 305, 302, 298, 295, 292, 289, 286, 282, 279, 276, 273, 270, 267, 264, 261, 258, 256,
253, 250, 247, 244, 241, 239, 236, 233, 230, 228, 225, 222, 220, 217, 215, 212, 209, 207, 204,
202, 199, 197, 194, 192, 190, 187, 185, 182, 180, 178, 175, 173, 171, 168, 166, 164, 162, 159,
157, 155, 153, 151, 149, 146, 144, 142, 140, 138, 136, 134, 132, 130, 128, 126, 123, 121, 119,
117, 115, 114, 112, 110, 108, 106, 104, 102, 100, 98, 96, 94, 93, 91, 89, 87, 85, 83, 82, 80,
78, 76, 74, 73, 71, 69, 67, 66, 64, 62, 61, 59, 57, 55, 54, 52, 50, 49, 47, 46, 44, 42, 41, 39,
37, 36, 34, 33, 31, 30, 28, 26, 25, 23, 22, 20, 19, 17, 16, 14, 13, 11, 10, 8, 7, 5, 4, 2, 1,
];
static PREDEFINED_SEQUENCE_CTABLES: OnceLock<PredefinedSequenceCTables> = OnceLock::new();
static PREDEFINED_SEQUENCE_DTABLES: OnceLock<PredefinedSequenceDTables> = OnceLock::new();
static PREDEFINED_SEQ_DTABLES: OnceLock<PredefinedSeqDTables> = OnceLock::new();
struct PredefinedSequenceCTables {
literal_lengths: SequenceEncodingTable,
offsets: SequenceEncodingTable,
match_lengths: SequenceEncodingTable,
}
struct PredefinedSequenceDTables {
literal_lengths: fse::DTable,
offsets: fse::DTable,
match_lengths: fse::DTable,
}
struct PredefinedSeqDTables {
literal_lengths: fse::SequenceDTable,
offsets: fse::SequenceDTable,
match_lengths: fse::SequenceDTable,
}
#[derive(Debug, Clone, Copy)]
struct EncodedSequence {
ll_code: u8,
ll_extra: u32,
of_code: u8,
of_extra: u32,
ml_code: u8,
ml_extra: u32,
}
#[derive(Default)]
pub(crate) struct SequenceEncodeScratch {
encoded: Vec<EncodedSequence>,
literal_codes: Vec<u8>,
offset_codes: Vec<u8>,
match_codes: Vec<u8>,
use_direct_path: bool,
table_pool: SequenceTablePool,
}
#[derive(Clone)]
struct SequenceTableChoice {
mode: CompressionMode,
header: Vec<u8>,
encoding: SequenceEncodingTable,
persist_mode: Option<SequenceRepeatMode>,
}
impl SequenceTableChoice {
fn into_part_state(self) -> Option<SequenceEncodingPartState> {
self.persist_mode
.map(|mode| SequenceEncodingPartState::new(self.encoding, mode))
}
}
struct SequenceStatisticsBuild {
literal_choice: SequenceTableChoice,
offset_choice: SequenceTableChoice,
match_choice: SequenceTableChoice,
stats: SequenceSectionStats,
extra_bits: usize,
}
impl SequenceStatisticsBuild {
fn into_next_state(self) -> (SequenceEncodingState, SequenceSectionStats) {
let next_state = SequenceEncodingState::with_states(
self.literal_choice.into_part_state(),
self.offset_choice.into_part_state(),
self.match_choice.into_part_state(),
);
(next_state, self.stats)
}
}
#[derive(Debug, Clone, Copy, Default)]
pub(crate) struct SequenceSectionTimings {
pub(crate) statistics: Duration,
pub(crate) bitstream: Duration,
pub(crate) assembly: Duration,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub(crate) struct SequenceSectionStats {
pub(crate) header_size: usize,
pub(crate) bitstream_size: usize,
pub(crate) last_count_size: usize,
pub(crate) long_offsets: bool,
pub(crate) modes: Option<SequenceCompressionModes>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub(crate) enum SequenceRepeatMode {
#[default]
None,
Check,
Valid,
}
#[derive(Clone)]
pub(crate) struct SequenceEncodingTable {
inner: Arc<SequenceEncodingTableInner>,
}
struct SequenceEncodingTableInner {
table: fse::CTable,
supported_symbols: [bool; fse::SYMBOLVALUE_MAX + 1],
}
impl Default for SequenceEncodingTableInner {
fn default() -> Self {
Self {
table: fse::CTable::default(),
supported_symbols: [false; fse::SYMBOLVALUE_MAX + 1],
}
}
}
impl SequenceEncodingTableInner {
fn fill_from_normalized_counts(
&mut self,
normalized: &[i16; fse::SYMBOLVALUE_MAX + 1],
max_symbol_value: u32,
table_log: u32,
) -> Result<()> {
fse::build_ctable(&mut self.table, normalized, max_symbol_value, table_log)?;
self.supported_symbols.fill(false);
for symbol in 0..=max_symbol_value as usize {
self.supported_symbols[symbol] = normalized[symbol] != 0;
}
Ok(())
}
}
const SEQUENCE_TABLE_POOL_DEPTH: usize = 2;
#[derive(Default)]
struct SequenceTablePool {
slots: [[Option<Arc<SequenceEncodingTableInner>>; SEQUENCE_TABLE_POOL_DEPTH]; 3],
}
impl SequenceTablePool {
fn build(
&mut self,
part: SequencePart,
fill: impl FnOnce(&mut SequenceEncodingTableInner) -> Result<()>,
) -> Result<SequenceEncodingTable> {
let slots = &mut self.slots[part.index()];
let chosen = slots
.iter()
.position(|slot| {
slot.as_ref()
.is_some_and(|inner| Arc::strong_count(inner) == 1)
})
.or_else(|| slots.iter().position(Option::is_none))
.unwrap_or(0);
let mut inner = slots[chosen]
.take()
.filter(|inner| Arc::strong_count(inner) == 1)
.unwrap_or_default();
fill(Arc::get_mut(&mut inner).expect("a reused table has no other holder"))?;
slots[chosen] = Some(Arc::clone(&inner));
Ok(SequenceEncodingTable { inner })
}
}
#[derive(Clone)]
pub(crate) struct SequenceEncodingPartState {
table: SequenceEncodingTable,
repeat_mode: SequenceRepeatMode,
}
pub(crate) struct SequenceCodeStats {
pub(crate) counts: [u32; fse::SYMBOLVALUE_MAX + 1],
pub(crate) max_symbol: u8,
pub(crate) most_frequent: usize,
pub(crate) total: usize,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum SequencePart {
LiteralLength,
Offset,
MatchLength,
}
impl SequencePart {
fn index(self) -> usize {
match self {
Self::LiteralLength => 0,
Self::Offset => 1,
Self::MatchLength => 2,
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum TableTarget {
SequenceOnly,
Both,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) enum CompressionMode {
Predefined,
Rle,
FseCompressed,
Repeat,
}
impl CompressionMode {
fn from_bits(bits: u8) -> Self {
match bits & 0x3 {
0 => Self::Predefined,
1 => Self::Rle,
2 => Self::FseCompressed,
3 => Self::Repeat,
_ => unreachable!(),
}
}
fn bits(self) -> u8 {
match self {
Self::Predefined => 0,
Self::Rle => 1,
Self::FseCompressed => 2,
Self::Repeat => 3,
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct SequenceCompressionModes {
pub(crate) literal_lengths: CompressionMode,
pub(crate) offsets: CompressionMode,
pub(crate) match_lengths: CompressionMode,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct SequenceCommand {
pub(crate) literal_length: u32,
pub(crate) offset_value: u32,
pub(crate) match_length: u32,
}
#[derive(Clone)]
pub(crate) struct SequenceTablesState {
literal_lengths: Option<fse::DTable>,
offsets: Option<fse::DTable>,
match_lengths: Option<fse::DTable>,
seq_ll: fse::SequenceDTable,
seq_of: fse::SequenceDTable,
seq_ml: fse::SequenceDTable,
ll_dirty: bool,
of_dirty: bool,
ml_dirty: bool,
has_ll: bool,
has_of: bool,
has_ml: bool,
}
impl Default for SequenceTablesState {
fn default() -> Self {
Self {
literal_lengths: None,
offsets: None,
match_lengths: None,
seq_ll: fse::SequenceDTable::default(),
seq_of: fse::SequenceDTable::default(),
seq_ml: fse::SequenceDTable::default(),
ll_dirty: true,
of_dirty: true,
ml_dirty: true,
has_ll: false,
has_of: false,
has_ml: false,
}
}
}
impl SequenceTablesState {
pub(crate) fn with_tables(
literal_lengths: Option<fse::DTable>,
offsets: Option<fse::DTable>,
match_lengths: Option<fse::DTable>,
) -> Self {
let has_ll = literal_lengths.is_some();
let has_of = offsets.is_some();
let has_ml = match_lengths.is_some();
Self {
literal_lengths,
offsets,
match_lengths,
seq_ll: fse::SequenceDTable::default(),
seq_of: fse::SequenceDTable::default(),
seq_ml: fse::SequenceDTable::default(),
ll_dirty: true,
of_dirty: true,
ml_dirty: true,
has_ll,
has_of,
has_ml,
}
}
}
#[derive(Default, Clone)]
pub(crate) struct SequenceEncodingState {
literal_lengths: Option<SequenceEncodingPartState>,
offsets: Option<SequenceEncodingPartState>,
match_lengths: Option<SequenceEncodingPartState>,
}
impl SequenceEncodingState {
pub(crate) fn with_states(
literal_lengths: Option<SequenceEncodingPartState>,
offsets: Option<SequenceEncodingPartState>,
match_lengths: Option<SequenceEncodingPartState>,
) -> Self {
Self {
literal_lengths,
offsets,
match_lengths,
}
}
fn entry(&self, part: SequencePart) -> Option<&SequenceEncodingPartState> {
match part {
SequencePart::LiteralLength => self.literal_lengths.as_ref(),
SequencePart::Offset => self.offsets.as_ref(),
SequencePart::MatchLength => self.match_lengths.as_ref(),
}
}
#[cfg_attr(not(test), allow(dead_code))]
fn table(&self, part: SequencePart) -> Option<&SequenceEncodingTable> {
self.entry(part).map(SequenceEncodingPartState::table)
}
}
impl SequenceEncodingTable {
fn new(table: fse::CTable, supported_symbols: [bool; fse::SYMBOLVALUE_MAX + 1]) -> Self {
Self {
inner: Arc::new(SequenceEncodingTableInner {
table,
supported_symbols,
}),
}
}
fn ctable(&self) -> &fse::CTable {
&self.inner.table
}
fn supports_all(&self, codes: &[u8]) -> bool {
codes
.iter()
.all(|&code| self.inner.supported_symbols[code as usize])
}
fn supports_all_from_stats(&self, stats: &SequenceCodeStats) -> bool {
for symbol in 0..=stats.max_symbol as usize {
if stats.counts[symbol] > 0 && !self.inner.supported_symbols[symbol] {
return false;
}
}
true
}
pub(crate) fn from_normalized_counts(
normalized: &[i16; fse::SYMBOLVALUE_MAX + 1],
max_symbol_value: u32,
table_log: u32,
) -> Result<Self> {
let mut inner = SequenceEncodingTableInner::default();
inner.fill_from_normalized_counts(normalized, max_symbol_value, table_log)?;
Ok(Self {
inner: Arc::new(inner),
})
}
}
impl SequenceEncodingPartState {
pub(crate) fn new(table: SequenceEncodingTable, repeat_mode: SequenceRepeatMode) -> Self {
Self { table, repeat_mode }
}
fn table(&self) -> &SequenceEncodingTable {
&self.table
}
fn repeat_mode(&self) -> SequenceRepeatMode {
self.repeat_mode
}
pub(crate) fn fse_ctable(&self) -> &fse::CTable {
self.table.ctable()
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub(crate) struct ParsedSequenceSection<'a> {
pub(crate) number_of_sequences: usize,
pub(crate) header_size: usize,
pub(crate) modes: Option<SequenceCompressionModes>,
pub(crate) bitstream: &'a [u8],
}
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub(crate) struct DecodedSequenceStats {
pub(crate) total_match_bytes: usize,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct RepeatOffsets {
values: [u32; 3],
}
impl Default for RepeatOffsets {
fn default() -> Self {
Self { values: [1, 4, 8] }
}
}
impl RepeatOffsets {
pub(crate) fn from_values(values: [u32; 3]) -> Self {
Self { values }
}
pub(crate) fn values(self) -> [u32; 3] {
self.values
}
#[inline(always)]
pub(crate) fn classify_offset(&self, raw_offset: u32, literal_length: u32) -> u32 {
debug_assert!(raw_offset > 0, "raw_offset must be non-zero");
let [rep1, rep2, rep3] = self.values;
let ll_zero = literal_length == 0;
if !ll_zero && raw_offset == rep1 {
return 1;
}
if raw_offset == rep2 {
return if ll_zero { 1 } else { 2 };
}
if raw_offset == rep3 {
return if ll_zero { 2 } else { 3 };
}
if ll_zero && rep1 > 1 && raw_offset == rep1 - 1 {
return 3;
}
raw_offset + 3
}
#[inline(always)]
pub(crate) fn encode_offset_value_and_update(
&mut self,
raw_offset: u32,
literal_length: u32,
) -> u32 {
debug_assert!(raw_offset > 0, "raw_offset must be non-zero");
let [rep1, rep2, rep3] = self.values;
let ll_zero = literal_length == 0;
if !ll_zero && raw_offset == rep1 {
return 1;
}
if raw_offset == rep2 {
self.values = [rep2, rep1, rep3];
return if ll_zero { 1 } else { 2 };
}
if raw_offset == rep3 {
self.values = [rep3, rep1, rep2];
return if ll_zero { 2 } else { 3 };
}
if ll_zero && rep1 > 1 && raw_offset == rep1 - 1 {
self.values = [rep1 - 1, rep1, rep2];
return 3;
}
self.values = [raw_offset, rep1, rep2];
raw_offset + 3
}
#[inline(always)]
pub(crate) fn update_explicit_offset(&mut self, raw_offset: u32) -> u32 {
debug_assert!(raw_offset > 0, "raw_offset must be non-zero");
let [rep1, rep2, _] = self.values;
self.values = [raw_offset, rep1, rep2];
raw_offset + 3
}
pub(crate) fn encode_offset_value(
&mut self,
raw_offset: u32,
literal_length: u32,
) -> Result<u32> {
if raw_offset == 0 {
return Err(Error::InvalidParameter("raw_offset must be non-zero"));
}
Ok(self.encode_offset_value_and_update(raw_offset, literal_length))
}
#[inline(always)]
#[cfg(test)]
pub(crate) fn resolve_zero_literal_rep2(&mut self) -> Result<u32> {
let [rep1, rep2, rep3] = self.values;
if rep2 == 0 {
return Err(Error::Corruption("repeat offset 2 is zero"));
}
self.values = [rep2, rep1, rep3];
Ok(rep2)
}
pub(crate) fn resolve_zero_literal_rep2_encode(&mut self) -> u32 {
let [rep1, rep2, rep3] = self.values;
debug_assert!(rep2 > 0, "repeat offset 2 is zero");
self.values = [rep2, rep1, rep3];
rep2
}
}
pub(crate) fn parse_sequence_count(src: &[u8]) -> Result<(usize, usize)> {
let byte0 = *src.first().ok_or(Error::UnexpectedEof)?;
if byte0 < 128 {
Ok((byte0 as usize, 1))
} else if byte0 < 255 {
let byte1 = *src.get(1).ok_or(Error::UnexpectedEof)?;
Ok((((byte0 as usize - 128) << 8) + byte1 as usize, 2))
} else {
let byte1 = *src.get(1).ok_or(Error::UnexpectedEof)?;
let byte2 = *src.get(2).ok_or(Error::UnexpectedEof)?;
Ok((0x7F00 + byte1 as usize + ((byte2 as usize) << 8), 3))
}
}
pub(crate) fn parse_sequence_section<'a>(
src: &'a [u8],
tables: &mut SequenceTablesState,
target: TableTarget,
) -> Result<ParsedSequenceSection<'a>> {
let (number_of_sequences, count_size) = parse_sequence_count(src)?;
if number_of_sequences == 0 {
return Ok(ParsedSequenceSection {
number_of_sequences,
header_size: count_size,
modes: None,
bitstream: &[],
});
}
let modes_byte = *src.get(count_size).ok_or(Error::UnexpectedEof)?;
if (modes_byte & 0x3) != 0 {
return Err(Error::Corruption(
"sequence compression modes reserved bits are set",
));
}
let modes = SequenceCompressionModes {
literal_lengths: CompressionMode::from_bits(modes_byte >> 6),
offsets: CompressionMode::from_bits((modes_byte >> 4) & 0x3),
match_lengths: CompressionMode::from_bits((modes_byte >> 2) & 0x3),
};
let mut cursor = count_size + 1;
decode_seq_table_both(
&mut tables.literal_lengths,
&mut tables.seq_ll,
&mut tables.has_ll,
src,
&mut cursor,
SequencePart::LiteralLength,
modes.literal_lengths,
target,
)?;
if modes.literal_lengths != CompressionMode::Repeat {
tables.ll_dirty = false;
}
decode_seq_table_both(
&mut tables.offsets,
&mut tables.seq_of,
&mut tables.has_of,
src,
&mut cursor,
SequencePart::Offset,
modes.offsets,
target,
)?;
if modes.offsets != CompressionMode::Repeat {
tables.of_dirty = false;
}
decode_seq_table_both(
&mut tables.match_lengths,
&mut tables.seq_ml,
&mut tables.has_ml,
src,
&mut cursor,
SequencePart::MatchLength,
modes.match_lengths,
target,
)?;
if modes.match_lengths != CompressionMode::Repeat {
tables.ml_dirty = false;
}
let bitstream = src.get(cursor..).ok_or(Error::UnexpectedEof)?;
if bitstream.is_empty() {
return Err(Error::UnexpectedEof);
}
Ok(ParsedSequenceSection {
number_of_sequences,
header_size: cursor,
modes: Some(modes),
bitstream,
})
}
#[cfg(any(test, feature = "internal-fuzz"))]
pub(crate) fn decode_sequence_commands(
section: &ParsedSequenceSection<'_>,
tables: &SequenceTablesState,
) -> Result<Vec<SequenceCommand>> {
let mut sequences = Vec::new();
decode_sequence_commands_into_stats(section, tables, &mut sequences)?;
Ok(sequences)
}
pub(crate) fn decode_sequence_commands_into_stats(
section: &ParsedSequenceSection<'_>,
tables: &SequenceTablesState,
sequences: &mut Vec<SequenceCommand>,
) -> Result<DecodedSequenceStats> {
sequences.clear();
if section.number_of_sequences == 0 {
return Ok(DecodedSequenceStats::default());
}
let literal_lengths = tables
.literal_lengths
.as_ref()
.ok_or(Error::Corruption("missing literal-length FSE table"))?;
let offsets = tables
.offsets
.as_ref()
.ok_or(Error::Corruption("missing offset FSE table"))?;
let match_lengths = tables
.match_lengths
.as_ref()
.ok_or(Error::Corruption("missing match-length FSE table"))?;
let mut reader = crate::entropy::bitstream::BitDStream::new(section.bitstream)?;
let mut literal_state = fse::init_dstate(&mut reader, literal_lengths);
let mut offset_state = fse::init_dstate(&mut reader, offsets);
let mut match_state = fse::init_dstate(&mut reader, match_lengths);
sequences.reserve(section.number_of_sequences);
let mut total_match_bytes = 0usize;
for index in 0..section.number_of_sequences {
let literal_entry = fse::peek_entry_fast(&literal_state, literal_lengths);
let offset_entry = fse::peek_entry_fast(&offset_state, offsets);
let match_entry = fse::peek_entry_fast(&match_state, match_lengths);
let literal_code = literal_entry.symbol as usize;
let offset_code = offset_entry.symbol as usize;
let match_code = match_entry.symbol as usize;
let match_extra_bits = u32::from(MATCH_LENGTH_EXTRA_BITS[match_code]);
let literal_extra_bits = u32::from(LITERAL_LENGTH_EXTRA_BITS[literal_code]);
let offset_extra = reader.read_bits_fast_zero_safe(offset_code as u32) as u32;
let match_extra = reader.read_bits_fast_zero_safe(match_extra_bits) as u32;
if literal_extra_bits != 0 && !reader.can_read_fast(literal_extra_bits) {
let _ = reader.reload();
}
let literal_extra = reader.read_bits_fast_zero_safe(literal_extra_bits) as u32;
let match_length = MATCH_LENGTH_BASELINES[match_code] + match_extra;
total_match_bytes = total_match_bytes
.checked_add(match_length as usize)
.ok_or(Error::OutputSizeOverflow)?;
sequences.push(SequenceCommand {
literal_length: LITERAL_LENGTH_BASELINES[literal_code] + literal_extra,
offset_value: (1u32 << offset_code) + offset_extra,
match_length,
});
if index + 1 != section.number_of_sequences {
fse::update_state_with_entry_fast(&mut literal_state, &mut reader, literal_entry);
fse::update_state_with_entry_fast(&mut match_state, &mut reader, match_entry);
fse::update_state_with_entry_fast(&mut offset_state, &mut reader, offset_entry);
if reader.reload() == BitDStreamStatus::Overflow {
return Err(corruption_error("sequence bitstream overflow"));
}
}
}
if reader.reload() == BitDStreamStatus::Overflow || !reader.end_of_stream() {
return Err(corruption_error(
"sequence bitstream was not fully consumed",
));
}
Ok(DecodedSequenceStats { total_match_bytes })
}
pub(crate) fn decode_and_execute_sequences(
section: &ParsedSequenceSection<'_>,
tables: &mut SequenceTablesState,
out: &mut DecodeOut<'_>,
frame_start: usize,
window_size: usize,
block_size_max: usize,
dictionary: Option<&[u8]>,
literals: DecodedLiterals<'_>,
repeat_offsets: &mut RepeatOffsets,
limit: OutputLimit,
) -> Result<()> {
if section.number_of_sequences == 0 {
let mut remaining_block_bytes = block_size_max;
let mut remaining_output_bytes = limit.remaining(out.len())?;
return append_trailing_literals(
out,
literals.as_slice(),
0,
&mut remaining_block_bytes,
&mut remaining_output_bytes,
limit,
);
}
decode_and_execute_sequences_unified(
section,
tables,
out,
frame_start,
window_size,
block_size_max,
dictionary,
literals,
repeat_offsets,
limit,
)
}
#[allow(unsafe_code)]
#[cold]
#[inline(never)]
unsafe fn copy_match_by_doubling(dst: *mut u8, src: *const u8, offset: usize, match_length: usize) {
unsafe {
let seed = offset.min(match_length);
core::ptr::copy_nonoverlapping(src, dst, seed);
let mut done = seed;
while done < match_length {
let chunk = done.min(match_length - done);
core::ptr::copy_nonoverlapping(dst, dst.add(done), chunk);
done += chunk;
}
}
}
const PATTERN_DOUBLING_MIN: usize = 4096;
#[allow(unsafe_code)]
#[inline(always)]
unsafe fn copy_match_inline(base: *mut u8, out_pos: usize, match_src: usize, match_length: usize) {
let offset = out_pos - match_src;
unsafe {
let dst = base.add(out_pos);
let src = base.add(match_src);
if match_length >= PATTERN_DOUBLING_MIN {
copy_match_by_doubling(dst, src, offset, match_length);
return;
}
if offset >= 16 {
copy_16(dst, src);
if match_length > 16 {
let mut pos = 16usize;
loop {
copy_16(dst.add(pos), src.add(pos));
pos += 16;
copy_16(dst.add(pos), src.add(pos));
pos += 16;
if pos >= match_length {
break;
}
}
}
} else {
let mut ip = src;
let mut op = dst;
if offset < 8 {
const DEC32TABLE: [u32; 8] = [0, 1, 2, 1, 4, 4, 4, 4];
const DEC64TABLE: [i32; 8] = [8, 8, 8, 7, 8, 9, 10, 11];
*op = *ip;
*op.add(1) = *ip.add(1);
*op.add(2) = *ip.add(2);
*op.add(3) = *ip.add(3);
ip = ip.add(DEC32TABLE[offset] as usize);
core::ptr::copy_nonoverlapping(ip, op.add(4), 4);
ip = ip.offset(8isize - DEC64TABLE[offset] as isize);
} else {
core::ptr::copy_nonoverlapping(ip, op, 8);
ip = ip.add(8);
}
op = op.add(8);
if match_length > 8 {
let end = dst.add(match_length);
while op < end {
core::ptr::copy_nonoverlapping(ip, op, 8);
ip = ip.add(8);
op = op.add(8);
}
}
}
}
}
#[cold]
#[inline(never)]
#[allow(unsafe_code)]
fn execute_dictionary_match(
out: &mut DecodeOut<'_>,
out_pos: usize,
frame_start: usize,
window_size: usize,
dictionary: Option<&[u8]>,
offset: usize,
match_length: usize,
) -> Result<(usize, *mut u8)> {
if offset == OFFSET_SENTINEL {
return Err(corruption_error("repeat offset 1 minus 1 is zero"));
}
let produced_in_frame = out_pos - frame_start;
if let Some(dict) = dictionary {
if produced_in_frame > window_size {
return Err(corruption_error(
"sequence offset exceeds the available history window",
));
}
let available_history = dict
.len()
.checked_add(produced_in_frame)
.ok_or_else(output_size_overflow_error)?;
if offset > available_history {
return Err(corruption_error(
"sequence offset exceeds the available history window",
));
}
unsafe {
out.set_len(out_pos);
}
append_match_from_dictionary_history(out, frame_start, dict, offset, match_length)?;
Ok((out.len(), out.as_mut_ptr()))
} else {
Err(corruption_error(
"sequence offset exceeds the available history window",
))
}
}
#[cold]
#[inline(never)]
#[allow(unsafe_code)]
#[allow(clippy::too_many_arguments)]
fn execute_sequence_exact(
out: &mut DecodeOut<'_>,
out_pos: usize,
literals: *const u8,
literal_length: usize,
offset: usize,
match_length: usize,
frame_start: usize,
window_size: usize,
dictionary: Option<&[u8]>,
) -> Result<(usize, *mut u8)> {
debug_assert!(
!out.is_growable(),
"a growable destination reserves the wildcopy slack, so it never gets here"
);
unsafe {
out.set_len(out_pos);
}
let literal_run = unsafe { core::slice::from_raw_parts(literals, literal_length) };
out.append(literal_run)?;
let out_pos = out.len();
if offset <= out_pos - frame_start && offset <= window_size {
append_match_from_history(out, out_pos - offset, match_length)?;
Ok((out.len(), out.as_mut_ptr()))
} else {
execute_dictionary_match(
out,
out_pos,
frame_start,
window_size,
dictionary,
offset,
match_length,
)
}
}
const OFFSET_SENTINEL: usize = u32::MAX as usize;
#[cold]
#[inline(never)]
fn resolve_rep_offset_decode(
repeat_offsets: &mut RepeatOffsets,
offset_value: u32,
literal_length: usize,
) -> usize {
let [rep1, rep2, rep3] = repeat_offsets.values;
if offset_value == 0 {
return OFFSET_SENTINEL;
}
let rep_index = offset_value + (literal_length == 0) as u32;
if rep_index == 2 {
repeat_offsets.values = [rep2, rep1, rep3];
rep2 as usize
} else if rep_index == 3 {
repeat_offsets.values = [rep3, rep1, rep2];
rep3 as usize
} else {
if rep1 <= 1 {
return OFFSET_SENTINEL;
}
let o = rep1 - 1;
repeat_offsets.values = [o, rep1, rep2];
o as usize
}
}
#[inline(never)]
fn decode_setup(
tables: &mut SequenceTablesState,
out: &mut DecodeOut<'_>,
block_size_max: usize,
limit: OutputLimit,
) -> Result<(
usize, // remaining_block_bytes
usize, // remaining_output_bytes
)> {
if tables.ll_dirty {
let ll = tables
.literal_lengths
.as_ref()
.ok_or(Error::Corruption("missing literal-length FSE table"))?;
fse::build_sequence_dtable_from(
ll,
&LITERAL_LENGTH_BASELINES,
&LITERAL_LENGTH_EXTRA_BITS,
&mut tables.seq_ll,
);
tables.ll_dirty = false;
tables.has_ll = true;
} else if !tables.has_ll {
return Err(Error::Corruption("missing literal-length FSE table"));
}
if tables.of_dirty {
let of = tables
.offsets
.as_ref()
.ok_or(Error::Corruption("missing offset FSE table"))?;
fse::build_offset_sequence_dtable_from(of, &mut tables.seq_of);
tables.of_dirty = false;
tables.has_of = true;
} else if !tables.has_of {
return Err(Error::Corruption("missing offset FSE table"));
}
if tables.ml_dirty {
let ml = tables
.match_lengths
.as_ref()
.ok_or(Error::Corruption("missing match-length FSE table"))?;
fse::build_sequence_dtable_from(
ml,
&MATCH_LENGTH_BASELINES,
&MATCH_LENGTH_EXTRA_BITS,
&mut tables.seq_ml,
);
tables.ml_dirty = false;
tables.has_ml = true;
} else if !tables.has_ml {
return Err(Error::Corruption("missing match-length FSE table"));
}
reserve_block_output(out, block_size_max, limit)?;
let remaining_output_bytes = limit.remaining(out.len())?;
Ok((block_size_max, remaining_output_bytes))
}
#[allow(unsafe_code)]
fn decode_and_execute_sequences_unified(
section: &ParsedSequenceSection<'_>,
tables: &mut SequenceTablesState,
out: &mut DecodeOut<'_>,
frame_start: usize,
window_size: usize,
block_size_max: usize,
dictionary: Option<&[u8]>,
literals: DecodedLiterals<'_>,
repeat_offsets: &mut RepeatOffsets,
limit: OutputLimit,
) -> Result<()> {
debug_assert!(section.number_of_sequences > 0);
let (remaining_block_bytes_init, remaining_output_bytes_init) =
decode_setup(tables, out, block_size_max, limit)?;
let wildcopy_end = out.capacity().saturating_sub(WILDCOPY_OVERLENGTH);
let block_fits_with_slack =
out.len() + remaining_block_bytes_init.min(remaining_output_bytes_init) <= wildcopy_end;
if block_fits_with_slack {
execute_block_sequences::<false>(
section,
tables,
out,
frame_start,
window_size,
dictionary,
literals,
repeat_offsets,
limit,
remaining_block_bytes_init,
remaining_output_bytes_init,
wildcopy_end,
)
} else {
execute_block_sequences::<true>(
section,
tables,
out,
frame_start,
window_size,
dictionary,
literals,
repeat_offsets,
limit,
remaining_block_bytes_init,
remaining_output_bytes_init,
wildcopy_end,
)
}
}
#[allow(unsafe_code)]
#[allow(clippy::too_many_arguments)]
fn execute_block_sequences<const CHECKED: bool>(
section: &ParsedSequenceSection<'_>,
tables: &SequenceTablesState,
out: &mut DecodeOut<'_>,
frame_start: usize,
window_size: usize,
dictionary: Option<&[u8]>,
literals: DecodedLiterals<'_>,
repeat_offsets: &mut RepeatOffsets,
limit: OutputLimit,
remaining_block_bytes_init: usize,
remaining_output_bytes_init: usize,
wildcopy_end: usize,
) -> Result<()> {
let mut reader = crate::entropy::bitstream::BitDStream::new(section.bitstream)?;
let merged_budget_init = remaining_block_bytes_init.min(remaining_output_bytes_init);
let mut remaining_budget = merged_budget_init;
let mut literal_state = fse::init_dstate_seq(&mut reader, &tables.seq_ll);
let mut offset_state = fse::init_dstate_seq(&mut reader, &tables.seq_of);
let mut match_state = fse::init_dstate_seq(&mut reader, &tables.seq_ml);
#[allow(unsafe_code)]
let mut ip = literals.padded_ptr();
#[allow(unsafe_code)]
let ip_end = unsafe { literals.padded_ptr().add(literals.len()) };
let mut out_base = out.as_mut_ptr();
let mut out_pos = out.len();
let [mut rep0, mut rep1, mut rep2] = repeat_offsets.values;
macro_rules! execute_sequence {
($literal_length:expr, $match_length:expr, $offset_value:expr) => {
let literal_length = $literal_length;
let match_length = $match_length;
let offset_value = $offset_value;
let total = literal_length + match_length;
let new_ip = ip.wrapping_add(literal_length);
if total > remaining_budget || new_ip > ip_end {
return Err(if new_ip > ip_end {
corruption_error("sequence literal length exceeds literals buffer")
} else {
sequence_budget_error(
total,
remaining_block_bytes_init - (merged_budget_init - remaining_budget),
out_pos,
limit,
)
});
}
remaining_budget -= total;
let offset = if offset_value > 3 {
let o = offset_value - 3;
rep2 = rep1;
rep1 = rep0;
rep0 = o;
o as usize
} else if offset_value == 1 && literal_length != 0 {
rep0 as usize
} else {
let mut local_reps = RepeatOffsets {
values: [rep0, rep1, rep2],
};
let result =
resolve_rep_offset_decode(&mut local_reps, offset_value, literal_length);
[rep0, rep1, rep2] = local_reps.values;
result
};
unsafe {
prefetch_match(
out_base.wrapping_add((out_pos + literal_length).wrapping_sub(offset)),
);
}
if !CHECKED || out_pos + total <= wildcopy_end {
unsafe {
let lit_dst = out_base.add(out_pos);
copy_16(lit_dst, ip);
if literal_length > 16 {
let mut pos = 16usize;
while pos < literal_length {
copy_16(lit_dst.add(pos), ip.add(pos));
pos += 16;
}
}
}
out_pos += literal_length;
ip = new_ip;
if offset <= out_pos - frame_start && offset <= window_size {
let match_src = out_pos - offset;
unsafe {
copy_match_inline(out_base, out_pos, match_src, match_length);
}
out_pos += match_length;
} else {
repeat_offsets.values = [rep0, rep1, rep2];
(out_pos, out_base) = execute_dictionary_match(
out,
out_pos,
frame_start,
window_size,
dictionary,
offset,
match_length,
)?;
}
} else {
repeat_offsets.values = [rep0, rep1, rep2];
(out_pos, out_base) = execute_sequence_exact(
out,
out_pos,
ip,
literal_length,
offset,
match_length,
frame_start,
window_size,
dictionary,
)?;
ip = new_ip;
}
};
}
let mut lit_raw = unsafe { tables.seq_ll.get_entry_raw(literal_state.state) };
let mut off_raw = unsafe { tables.seq_of.get_entry_raw(offset_state.state) };
let mut ml_raw = unsafe { tables.seq_ml.get_entry_raw(match_state.state) };
macro_rules! decode_sequence {
() => {{
let offset_code = fse::raw_entry_nb_additional_bits(off_raw);
let match_extra_bits = fse::raw_entry_nb_additional_bits(ml_raw);
let literal_extra_bits = fse::raw_entry_nb_additional_bits(lit_raw);
let offset_extra = if offset_code > 0 {
reader.read_bits_fast(offset_code) as u32
} else {
0
};
let match_extra = if match_extra_bits > 0 {
reader.read_bits_fast(match_extra_bits) as u32
} else {
0
};
let combined_om = offset_code + match_extra_bits;
if combined_om + literal_extra_bits >= 31 {
let _ = reader.reload();
}
let literal_extra = if literal_extra_bits > 0 {
reader.read_bits_fast(literal_extra_bits) as u32
} else {
0
};
let literal_length = (fse::raw_entry_baseline(lit_raw) + literal_extra) as usize;
let match_length = (fse::raw_entry_baseline(ml_raw) + match_extra) as usize;
let offset_value = (1u32 << offset_code) + offset_extra;
(literal_length, match_length, offset_value)
}};
}
#[cfg(all(target_arch = "aarch64", not(miri)))]
unsafe {
core::arch::asm!(".p2align 6", options(nomem, nostack, preserves_flags));
}
let mut remaining_sequences = section.number_of_sequences;
while remaining_sequences > 1 {
remaining_sequences -= 1;
let (literal_length, match_length, offset_value) = decode_sequence!();
let ll_bits = fse::raw_entry_nb_bits(lit_raw);
let ml_bits = fse::raw_entry_nb_bits(ml_raw);
let of_bits = fse::raw_entry_nb_bits(off_raw);
let combined_state_bits = ll_bits + ml_bits + of_bits;
let state_val = if combined_state_bits > 0 {
reader.read_bits_fast(combined_state_bits) as usize
} else {
0
};
literal_state.state = fse::raw_entry_new_state(lit_raw)
+ ((state_val >> (ml_bits + of_bits)) & ((1usize << ll_bits).wrapping_sub(1)));
match_state.state = fse::raw_entry_new_state(ml_raw)
+ ((state_val >> of_bits) & ((1usize << ml_bits).wrapping_sub(1)));
offset_state.state =
fse::raw_entry_new_state(off_raw) + (state_val & ((1usize << of_bits).wrapping_sub(1)));
lit_raw = unsafe { tables.seq_ll.get_entry_raw(literal_state.state) };
off_raw = unsafe { tables.seq_of.get_entry_raw(offset_state.state) };
ml_raw = unsafe { tables.seq_ml.get_entry_raw(match_state.state) };
execute_sequence!(literal_length, match_length, offset_value);
if reader.reload() == BitDStreamStatus::Overflow {
return Err(corruption_error("sequence bitstream overflow"));
}
}
let (
last_out_pos,
last_out_base,
last_rep0,
last_rep1,
last_rep2,
last_ip,
last_remaining_budget,
) = decode_and_execute_last_sequence(
&mut reader,
lit_raw,
off_raw,
ml_raw,
out_pos,
out_base,
rep0,
rep1,
rep2,
ip,
ip_end,
remaining_budget,
repeat_offsets,
out,
wildcopy_end,
frame_start,
window_size,
dictionary,
remaining_block_bytes_init - (merged_budget_init - remaining_budget),
limit,
)?;
out_pos = last_out_pos;
let _ = last_out_base;
rep0 = last_rep0;
rep1 = last_rep1;
rep2 = last_rep2;
ip = last_ip;
remaining_budget = last_remaining_budget;
repeat_offsets.values = [rep0, rep1, rep2];
unsafe {
out.set_len(out_pos);
}
if reader.reload() == BitDStreamStatus::Overflow || !reader.end_of_stream() {
return Err(corruption_error(
"sequence bitstream was not fully consumed",
));
}
let consumed = remaining_block_bytes_init.min(remaining_output_bytes_init) - remaining_budget;
let mut remaining_block_bytes = remaining_block_bytes_init - consumed;
let mut remaining_output_bytes = remaining_output_bytes_init - consumed;
#[allow(unsafe_code)]
let literal_cursor = unsafe { ip.offset_from(literals.padded_ptr()) as usize };
append_trailing_literals(
out,
literals.as_slice(),
literal_cursor,
&mut remaining_block_bytes,
&mut remaining_output_bytes,
limit,
)
}
#[cold]
#[inline(never)]
#[allow(clippy::too_many_arguments)]
#[allow(unsafe_code)]
fn decode_and_execute_last_sequence(
reader: &mut crate::entropy::bitstream::BitDStream<'_>,
lit_raw: u64,
off_raw: u64,
ml_raw: u64,
mut out_pos: usize,
mut out_base: *mut u8,
mut rep0: u32,
mut rep1: u32,
mut rep2: u32,
mut ip: *const u8,
ip_end: *const u8,
mut remaining_budget: usize,
repeat_offsets: &mut RepeatOffsets,
out: &mut DecodeOut<'_>,
wildcopy_end: usize,
frame_start: usize,
window_size: usize,
dictionary: Option<&[u8]>,
block_remaining: usize,
limit: OutputLimit,
) -> Result<(usize, *mut u8, u32, u32, u32, *const u8, usize)> {
let offset_code = fse::raw_entry_nb_additional_bits(off_raw);
let match_extra_bits = fse::raw_entry_nb_additional_bits(ml_raw);
let literal_extra_bits = fse::raw_entry_nb_additional_bits(lit_raw);
let offset_extra = if offset_code > 0 {
reader.read_bits_fast(offset_code) as u32
} else {
0
};
let match_extra = if match_extra_bits > 0 {
reader.read_bits_fast(match_extra_bits) as u32
} else {
0
};
let combined_om = offset_code + match_extra_bits;
if combined_om + literal_extra_bits >= 31 {
let _ = reader.reload();
}
let literal_extra = if literal_extra_bits > 0 {
reader.read_bits_fast(literal_extra_bits) as u32
} else {
0
};
let literal_length = (fse::raw_entry_baseline(lit_raw) + literal_extra) as usize;
let match_length = (fse::raw_entry_baseline(ml_raw) + match_extra) as usize;
let offset_value = (1u32 << offset_code) + offset_extra;
let total = literal_length + match_length;
let new_ip = ip.wrapping_add(literal_length);
if total > remaining_budget || new_ip > ip_end {
repeat_offsets.values = [rep0, rep1, rep2];
return Err(if new_ip > ip_end {
corruption_error("sequence literal length exceeds literals buffer")
} else {
sequence_budget_error(total, block_remaining, out_pos, limit)
});
}
remaining_budget -= total;
let offset = if offset_value > 3 {
let o = offset_value - 3;
rep2 = rep1;
rep1 = rep0;
rep0 = o;
o as usize
} else if offset_value == 1 && literal_length != 0 {
rep0 as usize
} else {
repeat_offsets.values = [rep0, rep1, rep2];
let result = resolve_rep_offset_decode(repeat_offsets, offset_value, literal_length);
[rep0, rep1, rep2] = repeat_offsets.values;
result
};
unsafe {
prefetch_match(out_base.wrapping_add((out_pos + literal_length).wrapping_sub(offset)));
}
if out_pos + total <= wildcopy_end {
unsafe {
let lit_dst = out_base.add(out_pos);
copy_16(lit_dst, ip);
if literal_length > 16 {
let mut pos = 16usize;
while pos < literal_length {
copy_16(lit_dst.add(pos), ip.add(pos));
pos += 16;
}
}
}
out_pos += literal_length;
ip = new_ip;
if offset <= out_pos - frame_start && offset <= window_size {
let match_src = out_pos - offset;
unsafe {
copy_match_inline(out_base, out_pos, match_src, match_length);
}
out_pos += match_length;
} else {
repeat_offsets.values = [rep0, rep1, rep2];
(out_pos, out_base) = execute_dictionary_match(
out,
out_pos,
frame_start,
window_size,
dictionary,
offset,
match_length,
)?;
}
} else {
repeat_offsets.values = [rep0, rep1, rep2];
(out_pos, out_base) = execute_sequence_exact(
out,
out_pos,
ip,
literal_length,
offset,
match_length,
frame_start,
window_size,
dictionary,
)?;
ip = new_ip;
}
Ok((out_pos, out_base, rep0, rep1, rep2, ip, remaining_budget))
}
#[cfg_attr(not(test), allow(dead_code))]
pub(crate) fn encode_sequence_section(sequences: &[SequenceCommand]) -> Result<Vec<u8>> {
let (encoded, _) =
encode_sequence_section_with_state(sequences, &SequenceEncodingState::default())?;
Ok(encoded)
}
pub(crate) fn encode_sequence_section_with_state(
sequences: &[SequenceCommand],
state: &SequenceEncodingState,
) -> Result<(Vec<u8>, SequenceEncodingState)> {
encode_sequence_section_with_strategy(sequences, state, ParserStrategy::Lazy)
}
pub(crate) fn encode_sequence_section_with_strategy(
sequences: &[SequenceCommand],
state: &SequenceEncodingState,
parser_strategy: ParserStrategy,
) -> Result<(Vec<u8>, SequenceEncodingState)> {
let mut bitstream_scratch = Vec::new();
let mut encode_scratch = SequenceEncodeScratch::default();
encode_sequence_section_with_strategy_and_scratch(
sequences,
state,
parser_strategy,
&mut bitstream_scratch,
&mut encode_scratch,
)
}
pub(crate) fn encode_sequence_section_with_strategy_and_scratch(
sequences: &[SequenceCommand],
state: &SequenceEncodingState,
parser_strategy: ParserStrategy,
bitstream_scratch: &mut Vec<u8>,
encode_scratch: &mut SequenceEncodeScratch,
) -> Result<(Vec<u8>, SequenceEncodingState)> {
if sequences.is_empty() {
return Ok((vec![0], state.clone()));
}
prepare_sequence_encode_scratch(sequences, encode_scratch)?;
encode_sequence_section_with_strategy_and_prepared_scratch(
state,
parser_strategy,
bitstream_scratch,
encode_scratch,
)
}
fn encode_sequence_section_with_strategy_and_prepared_scratch(
state: &SequenceEncodingState,
parser_strategy: ParserStrategy,
bitstream_scratch: &mut Vec<u8>,
encode_scratch: &mut SequenceEncodeScratch,
) -> Result<(Vec<u8>, SequenceEncodingState)> {
let mut payload = Vec::new();
let (next_state, _) = encode_sequence_section_with_strategy_and_prepared_scratch_into_stats(
&mut payload,
state,
parser_strategy,
bitstream_scratch,
encode_scratch,
)?;
Ok((payload, next_state))
}
fn encode_sequence_section_with_strategy_and_prepared_scratch_into(
payload: &mut Vec<u8>,
state: &SequenceEncodingState,
parser_strategy: ParserStrategy,
bitstream_scratch: &mut Vec<u8>,
encode_scratch: &mut SequenceEncodeScratch,
) -> Result<SequenceEncodingState> {
Ok(
encode_sequence_section_with_strategy_and_prepared_scratch_into_stats(
payload,
state,
parser_strategy,
bitstream_scratch,
encode_scratch,
)?
.0,
)
}
fn encode_sequence_section_with_strategy_and_prepared_scratch_into_stats(
payload: &mut Vec<u8>,
state: &SequenceEncodingState,
parser_strategy: ParserStrategy,
bitstream_scratch: &mut Vec<u8>,
encode_scratch: &mut SequenceEncodeScratch,
) -> Result<(SequenceEncodingState, SequenceSectionStats)> {
let encoded = &encode_scratch.encoded;
let mut build = build_sequences_statistics(
encoded.len(),
&encode_scratch.literal_codes,
&encode_scratch.offset_codes,
&encode_scratch.match_codes,
state,
parser_strategy,
&mut encode_scratch.table_pool,
)?;
encode_sequence_bitstream_into(
bitstream_scratch,
encoded,
build.extra_bits,
build.literal_choice.encoding.ctable(),
build.offset_choice.encoding.ctable(),
build.match_choice.encoding.ctable(),
build.stats.long_offsets,
)?;
build.stats.bitstream_size = bitstream_scratch.len();
let payload_len = build.stats.header_size + bitstream_scratch.len();
payload.clear();
payload.reserve(payload_len);
encode_sequence_count(encoded.len(), &mut OutBuf::growable(payload))?;
payload.push(
(build.literal_choice.mode.bits() << 6)
| (build.offset_choice.mode.bits() << 4)
| (build.match_choice.mode.bits() << 2),
);
payload.extend_from_slice(&build.literal_choice.header);
payload.extend_from_slice(&build.offset_choice.header);
payload.extend_from_slice(&build.match_choice.header);
payload.extend_from_slice(bitstream_scratch);
Ok(build.into_next_state())
}
#[allow(dead_code)]
pub(crate) fn encode_prepared_sequence_section_with_strategy_and_scratch(
state: &SequenceEncodingState,
parser_strategy: ParserStrategy,
bitstream_scratch: &mut Vec<u8>,
encode_scratch: &mut SequenceEncodeScratch,
) -> Result<(Vec<u8>, SequenceEncodingState)> {
if encode_scratch.encoded.is_empty() {
return Ok((vec![0], state.clone()));
}
encode_sequence_section_with_strategy_and_prepared_scratch(
state,
parser_strategy,
bitstream_scratch,
encode_scratch,
)
}
#[allow(dead_code)]
pub(crate) fn encode_prepared_sequence_section_with_strategy_and_scratch_into(
payload: &mut Vec<u8>,
state: &SequenceEncodingState,
parser_strategy: ParserStrategy,
bitstream_scratch: &mut Vec<u8>,
encode_scratch: &mut SequenceEncodeScratch,
) -> Result<SequenceEncodingState> {
if encode_scratch.encoded.is_empty() {
payload.clear();
payload.push(0);
return Ok(state.clone());
}
encode_sequence_section_with_strategy_and_prepared_scratch_into(
payload,
state,
parser_strategy,
bitstream_scratch,
encode_scratch,
)
}
pub(crate) fn prepare_sequence_encode_scratch(
sequences: &[SequenceCommand],
scratch: &mut SequenceEncodeScratch,
) -> Result<()> {
scratch.encoded.clear();
scratch.literal_codes.clear();
scratch.offset_codes.clear();
scratch.match_codes.clear();
scratch.encoded.reserve(sequences.len());
scratch.literal_codes.reserve(sequences.len());
scratch.offset_codes.reserve(sequences.len());
scratch.match_codes.reserve(sequences.len());
for sequence in sequences {
let encoded = encode_sequence_command(sequence)?;
scratch.literal_codes.push(encoded.ll_code);
scratch.offset_codes.push(encoded.of_code);
scratch.match_codes.push(encoded.ml_code);
scratch.encoded.push(encoded);
}
Ok(())
}
pub(crate) fn prepare_seq_store_encode_scratch(
store: &mut SeqStore,
scratch: &mut SequenceEncodeScratch,
) -> Result<()> {
let codes_precomputed = store.literal_codes.len() == store.sequences.len();
scratch.encoded.clear();
if codes_precomputed {
scratch.use_direct_path = true;
} else {
scratch.use_direct_path = false;
scratch.encoded.reserve(store.sequences.len());
store.literal_codes.clear();
store.offset_codes.clear();
store.match_codes.clear();
store.literal_codes.reserve(store.sequences.len());
store.offset_codes.reserve(store.sequences.len());
store.match_codes.reserve(store.sequences.len());
for sequence in &store.sequences {
let encoded = encode_sequence_command(sequence)?;
store.literal_codes.push(encoded.ll_code);
store.offset_codes.push(encoded.of_code);
store.match_codes.push(encoded.ml_code);
scratch.encoded.push(encoded);
}
}
Ok(())
}
pub(crate) fn encode_sequence_section_direct(
out: &mut OutBuf<'_>,
state: &SequenceEncodingState,
parser_strategy: ParserStrategy,
bitstream_scratch: &mut Vec<u8>,
store: &SeqStore,
encode_scratch: &mut SequenceEncodeScratch,
) -> Result<(SequenceEncodingState, SequenceSectionStats)> {
let sequence_count = if encode_scratch.use_direct_path {
store.sequences.len()
} else {
encode_scratch.encoded.len()
};
if sequence_count == 0 {
out.push(0);
return Ok((state.clone(), SequenceSectionStats::default()));
}
let mut build = build_sequences_statistics(
sequence_count,
&store.literal_codes,
&store.offset_codes,
&store.match_codes,
state,
parser_strategy,
&mut encode_scratch.table_pool,
)?;
if encode_scratch.use_direct_path {
encode_sequence_bitstream_direct_into(
bitstream_scratch,
&store.sequences,
&store.literal_codes,
&store.offset_codes,
&store.match_codes,
build.extra_bits,
build.literal_choice.encoding.ctable(),
build.offset_choice.encoding.ctable(),
build.match_choice.encoding.ctable(),
build.stats.long_offsets,
)?;
} else {
encode_sequence_bitstream_into(
bitstream_scratch,
&encode_scratch.encoded,
build.extra_bits,
build.literal_choice.encoding.ctable(),
build.offset_choice.encoding.ctable(),
build.match_choice.encoding.ctable(),
build.stats.long_offsets,
)?;
}
build.stats.bitstream_size = bitstream_scratch.len();
let payload_len = build.stats.header_size + bitstream_scratch.len();
out.reserve(payload_len);
encode_sequence_count(sequence_count, out)?;
out.push(
(build.literal_choice.mode.bits() << 6)
| (build.offset_choice.mode.bits() << 4)
| (build.match_choice.mode.bits() << 2),
);
out.extend_from_slice(&build.literal_choice.header);
out.extend_from_slice(&build.offset_choice.header);
out.extend_from_slice(&build.match_choice.header);
out.extend_from_slice(bitstream_scratch);
Ok(build.into_next_state())
}
pub(crate) fn encode_prepared_seq_store_section_with_strategy_and_scratch_into_stats(
payload: &mut Vec<u8>,
state: &SequenceEncodingState,
parser_strategy: ParserStrategy,
bitstream_scratch: &mut Vec<u8>,
store: &SeqStore,
encode_scratch: &mut SequenceEncodeScratch,
timings: &mut SequenceSectionTimings,
) -> Result<(SequenceEncodingState, SequenceSectionStats)> {
let sequence_count = if encode_scratch.use_direct_path {
store.sequences.len()
} else {
encode_scratch.encoded.len()
};
if sequence_count == 0 {
payload.clear();
payload.push(0);
return Ok((state.clone(), SequenceSectionStats::default()));
}
let statistics_start = Instant::now();
let mut build = build_sequences_statistics(
sequence_count,
&store.literal_codes,
&store.offset_codes,
&store.match_codes,
state,
parser_strategy,
&mut encode_scratch.table_pool,
)?;
timings.statistics = statistics_start.elapsed();
let bitstream_start = Instant::now();
if encode_scratch.use_direct_path {
encode_sequence_bitstream_direct_into(
bitstream_scratch,
&store.sequences,
&store.literal_codes,
&store.offset_codes,
&store.match_codes,
build.extra_bits,
build.literal_choice.encoding.ctable(),
build.offset_choice.encoding.ctable(),
build.match_choice.encoding.ctable(),
build.stats.long_offsets,
)?;
} else {
encode_sequence_bitstream_into(
bitstream_scratch,
&encode_scratch.encoded,
build.extra_bits,
build.literal_choice.encoding.ctable(),
build.offset_choice.encoding.ctable(),
build.match_choice.encoding.ctable(),
build.stats.long_offsets,
)?;
}
timings.bitstream = bitstream_start.elapsed();
build.stats.bitstream_size = bitstream_scratch.len();
let assembly_start = Instant::now();
let payload_len = build.stats.header_size + bitstream_scratch.len();
payload.clear();
payload.reserve(payload_len);
encode_sequence_count(sequence_count, &mut OutBuf::growable(payload))?;
payload.push(
(build.literal_choice.mode.bits() << 6)
| (build.offset_choice.mode.bits() << 4)
| (build.match_choice.mode.bits() << 2),
);
payload.extend_from_slice(&build.literal_choice.header);
payload.extend_from_slice(&build.offset_choice.header);
payload.extend_from_slice(&build.match_choice.header);
payload.extend_from_slice(bitstream_scratch);
timings.assembly = assembly_start.elapsed();
Ok(build.into_next_state())
}
fn build_sequence_part_choice_with_stats(
part: SequencePart,
codes: &[u8],
previous: Option<&SequenceEncodingPartState>,
parser_strategy: ParserStrategy,
stats: &SequenceCodeStats,
pool: &mut SequenceTablePool,
) -> Result<SequenceTableChoice> {
let choice = select_table_choice(part, codes, previous, parser_strategy, stats)?;
build_selected_table_choice(part, codes, previous, stats, choice, pool)
}
fn build_sequences_statistics(
sequence_count: usize,
literal_codes: &[u8],
offset_codes: &[u8],
match_codes: &[u8],
state: &SequenceEncodingState,
parser_strategy: ParserStrategy,
pool: &mut SequenceTablePool,
) -> Result<SequenceStatisticsBuild> {
let (ll_stats, of_stats, ml_stats) =
analyze_all_codes(literal_codes, offset_codes, match_codes);
let literal_choice = build_sequence_part_choice_with_stats(
SequencePart::LiteralLength,
literal_codes,
state.entry(SequencePart::LiteralLength),
parser_strategy,
&ll_stats,
pool,
)?;
let offset_choice = build_sequence_part_choice_with_stats(
SequencePart::Offset,
offset_codes,
state.entry(SequencePart::Offset),
parser_strategy,
&of_stats,
pool,
)?;
let match_choice = build_sequence_part_choice_with_stats(
SequencePart::MatchLength,
match_codes,
state.entry(SequencePart::MatchLength),
parser_strategy,
&ml_stats,
pool,
)?;
let modes = SequenceCompressionModes {
literal_lengths: literal_choice.mode,
offsets: offset_choice.mode,
match_lengths: match_choice.mode,
};
let header_size = encoded_sequence_count_size(sequence_count)
+ 1
+ literal_choice.header.len()
+ offset_choice.header.len()
+ match_choice.header.len();
let last_count_size =
last_compressed_count_size(&literal_choice, &offset_choice, &match_choice);
let long_offsets = detect_long_offsets(offset_codes);
let extra_bits = extra_bits_from_code_counts(&ll_stats, &of_stats, &ml_stats);
Ok(SequenceStatisticsBuild {
literal_choice,
offset_choice,
match_choice,
extra_bits,
stats: SequenceSectionStats {
header_size,
bitstream_size: 0,
last_count_size,
long_offsets,
modes: Some(modes),
},
})
}
fn last_compressed_count_size(
literal_choice: &SequenceTableChoice,
offset_choice: &SequenceTableChoice,
match_choice: &SequenceTableChoice,
) -> usize {
for choice in [match_choice, offset_choice, literal_choice] {
if choice.mode == CompressionMode::FseCompressed {
return choice.header.len();
}
}
0
}
#[cfg(test)]
pub(crate) fn execute_sequences(
out: &mut DecodeOut<'_>,
frame_start: usize,
window_size: usize,
block_size_max: usize,
dictionary: Option<&[u8]>,
literals: &[u8],
sequences: &[SequenceCommand],
repeat_offsets: &mut RepeatOffsets,
max_output_size: Option<usize>,
) -> Result<()> {
let total_match_bytes = sequences.iter().try_fold(0usize, |size, sequence| {
size.checked_add(sequence.match_length as usize)
.ok_or(Error::OutputSizeOverflow)
})?;
execute_sequences_with_total_match_bytes(
out,
frame_start,
window_size,
block_size_max,
dictionary,
literals,
sequences,
repeat_offsets,
max_output_size,
total_match_bytes,
)
}
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
pub(crate) struct SequenceExecuteProfile {
pub(crate) literal_copy: std::time::Duration,
pub(crate) prefix_match_copy: std::time::Duration,
pub(crate) dictionary_match_copy: std::time::Duration,
}
#[cfg(test)]
pub(crate) fn execute_sequences_with_total_match_bytes(
out: &mut DecodeOut<'_>,
frame_start: usize,
window_size: usize,
block_size_max: usize,
dictionary: Option<&[u8]>,
literals: &[u8],
sequences: &[SequenceCommand],
repeat_offsets: &mut RepeatOffsets,
max_output_size: Option<usize>,
total_match_bytes: usize,
) -> Result<()> {
let block_output_size = literals
.len()
.checked_add(total_match_bytes)
.ok_or(Error::OutputSizeOverflow)?;
if block_output_size > block_size_max {
return Err(Error::Corruption(
"compressed block output exceeds the frame block size limit",
));
}
let final_len = out
.len()
.checked_add(block_output_size)
.ok_or(Error::OutputSizeOverflow)?;
if let Some(limit) = max_output_size {
if final_len > limit {
return Err(Error::OutputSizeTooLarge {
output_size: final_len as u64,
max_output_size: limit,
});
}
}
let block_start = out.len();
out.try_reserve(block_output_size + WILDCOPY_OVERLENGTH)?;
let literal_cursor = if let Some(dictionary) = dictionary {
execute_sequences_with_dictionary(
out,
frame_start,
window_size,
dictionary,
literals,
sequences,
repeat_offsets,
)?
} else {
execute_sequences_without_dictionary(
out,
frame_start,
window_size,
literals,
sequences,
repeat_offsets,
)?
};
out.append(literals.get(literal_cursor..).ok_or(Error::Corruption(
"sequence literal cursor exceeded literals buffer",
))?)?;
debug_assert_eq!(out.len() - block_start, block_output_size);
Ok(())
}
pub(crate) fn execute_sequences_with_total_match_bytes_profiled(
out: &mut DecodeOut<'_>,
frame_start: usize,
window_size: usize,
block_size_max: usize,
dictionary: Option<&[u8]>,
literals: &[u8],
sequences: &[SequenceCommand],
repeat_offsets: &mut RepeatOffsets,
max_output_size: Option<usize>,
total_match_bytes: usize,
) -> Result<SequenceExecuteProfile> {
let block_output_size = literals
.len()
.checked_add(total_match_bytes)
.ok_or(Error::OutputSizeOverflow)?;
if block_output_size > block_size_max {
return Err(Error::Corruption(
"compressed block output exceeds the frame block size limit",
));
}
let final_len = out
.len()
.checked_add(block_output_size)
.ok_or(Error::OutputSizeOverflow)?;
if let Some(limit) = max_output_size {
if final_len > limit {
return Err(Error::OutputSizeTooLarge {
output_size: final_len as u64,
max_output_size: limit,
});
}
}
let block_start = out.len();
out.try_reserve(block_output_size + WILDCOPY_OVERLENGTH)?;
let (literal_cursor, profile) = if let Some(dictionary) = dictionary {
execute_sequences_with_dictionary_profiled(
out,
frame_start,
window_size,
dictionary,
literals,
sequences,
repeat_offsets,
)?
} else {
execute_sequences_without_dictionary_profiled(
out,
frame_start,
window_size,
literals,
sequences,
repeat_offsets,
)?
};
let trailing_literals = literals.get(literal_cursor..).ok_or(Error::Corruption(
"sequence literal cursor exceeded literals buffer",
))?;
let literal_start = std::time::Instant::now();
out.append(trailing_literals)?;
let mut profile = profile;
profile.literal_copy += literal_start.elapsed();
debug_assert_eq!(out.len() - block_start, block_output_size);
Ok(profile)
}
#[cfg(test)]
#[allow(unsafe_code)]
fn execute_sequences_without_dictionary(
out: &mut DecodeOut<'_>,
frame_start: usize,
window_size: usize,
literals: &[u8],
sequences: &[SequenceCommand],
repeat_offsets: &mut RepeatOffsets,
) -> Result<usize> {
let mut literal_cursor = 0usize;
for sequence in sequences {
let offset = repeat_offsets.resolve(sequence)? as usize;
let predicted_match_pos =
(out.len() + (sequence.literal_length as usize)).wrapping_sub(offset);
unsafe { crate::entropy::mem::prefetch_l1(out.as_ptr().wrapping_add(predicted_match_pos)) };
literal_cursor = append_sequence_literals(out, literals, literal_cursor, sequence)?;
debug_assert!(out.len() >= frame_start);
let produced_in_frame = out.len() - frame_start;
let available_history = produced_in_frame.min(window_size);
if offset > available_history {
return Err(offset_exceeds_history_error());
}
debug_assert!(out.len() >= offset);
let match_start = out.len() - offset;
append_match_from_history(out, match_start, sequence.match_length as usize)?;
}
Ok(literal_cursor)
}
#[allow(unsafe_code)]
fn execute_sequences_without_dictionary_profiled(
out: &mut DecodeOut<'_>,
frame_start: usize,
window_size: usize,
literals: &[u8],
sequences: &[SequenceCommand],
repeat_offsets: &mut RepeatOffsets,
) -> Result<(usize, SequenceExecuteProfile)> {
let mut literal_cursor = 0usize;
let mut profile = SequenceExecuteProfile::default();
for sequence in sequences {
let offset = repeat_offsets.resolve(sequence)? as usize;
let predicted_match_pos =
(out.len() + (sequence.literal_length as usize)).wrapping_sub(offset);
unsafe { crate::entropy::mem::prefetch_l1(out.as_ptr().wrapping_add(predicted_match_pos)) };
let literal_start = std::time::Instant::now();
literal_cursor = append_sequence_literals(out, literals, literal_cursor, sequence)?;
profile.literal_copy += literal_start.elapsed();
debug_assert!(out.len() >= frame_start);
let produced_in_frame = out.len() - frame_start;
let available_history = produced_in_frame.min(window_size);
if offset > available_history {
return Err(offset_exceeds_history_error());
}
debug_assert!(out.len() >= offset);
let match_start = out.len() - offset;
let match_start_time = std::time::Instant::now();
append_match_from_history(out, match_start, sequence.match_length as usize)?;
profile.prefix_match_copy += match_start_time.elapsed();
}
Ok((literal_cursor, profile))
}
#[cfg(test)]
#[allow(unsafe_code)]
fn execute_sequences_with_dictionary(
out: &mut DecodeOut<'_>,
frame_start: usize,
window_size: usize,
dictionary: &[u8],
literals: &[u8],
sequences: &[SequenceCommand],
repeat_offsets: &mut RepeatOffsets,
) -> Result<usize> {
let mut literal_cursor = 0usize;
for sequence in sequences {
let offset = repeat_offsets.resolve(sequence)? as usize;
let predicted_match_pos =
(out.len() + (sequence.literal_length as usize)).wrapping_sub(offset);
unsafe { crate::entropy::mem::prefetch_l1(out.as_ptr().wrapping_add(predicted_match_pos)) };
literal_cursor = append_sequence_literals(out, literals, literal_cursor, sequence)?;
debug_assert!(out.len() >= frame_start);
let produced_in_frame = out.len() - frame_start;
let available_prefix = produced_in_frame.min(window_size);
if offset <= available_prefix {
debug_assert!(out.len() >= offset);
let match_start = out.len() - offset;
append_match_from_history(out, match_start, sequence.match_length as usize)?;
continue;
}
if produced_in_frame > window_size {
return Err(offset_exceeds_history_error());
}
let available_history = dictionary.len() + produced_in_frame;
if offset > available_history {
return Err(offset_exceeds_history_error());
}
append_match_from_dictionary_history(
out,
frame_start,
dictionary,
offset,
sequence.match_length as usize,
)?;
}
Ok(literal_cursor)
}
#[allow(unsafe_code)]
fn execute_sequences_with_dictionary_profiled(
out: &mut DecodeOut<'_>,
frame_start: usize,
window_size: usize,
dictionary: &[u8],
literals: &[u8],
sequences: &[SequenceCommand],
repeat_offsets: &mut RepeatOffsets,
) -> Result<(usize, SequenceExecuteProfile)> {
let mut literal_cursor = 0usize;
let mut profile = SequenceExecuteProfile::default();
for sequence in sequences {
let offset = repeat_offsets.resolve(sequence)? as usize;
let predicted_match_pos =
(out.len() + (sequence.literal_length as usize)).wrapping_sub(offset);
unsafe { crate::entropy::mem::prefetch_l1(out.as_ptr().wrapping_add(predicted_match_pos)) };
let literal_start = std::time::Instant::now();
literal_cursor = append_sequence_literals(out, literals, literal_cursor, sequence)?;
profile.literal_copy += literal_start.elapsed();
debug_assert!(out.len() >= frame_start);
let produced_in_frame = out.len() - frame_start;
let available_prefix = produced_in_frame.min(window_size);
if offset <= available_prefix {
debug_assert!(out.len() >= offset);
let match_start = out.len() - offset;
let match_start_time = std::time::Instant::now();
append_match_from_history(out, match_start, sequence.match_length as usize)?;
profile.prefix_match_copy += match_start_time.elapsed();
continue;
}
if produced_in_frame > window_size {
return Err(offset_exceeds_history_error());
}
let available_history = dictionary.len() + produced_in_frame;
if offset > available_history {
return Err(offset_exceeds_history_error());
}
let match_start_time = std::time::Instant::now();
append_match_from_dictionary_history(
out,
frame_start,
dictionary,
offset,
sequence.match_length as usize,
)?;
profile.dictionary_match_copy += match_start_time.elapsed();
}
Ok((literal_cursor, profile))
}
fn append_sequence_literals(
out: &mut DecodeOut<'_>,
literals: &[u8],
literal_cursor: usize,
sequence: &SequenceCommand,
) -> Result<usize> {
let literal_length = sequence.literal_length as usize;
let literal_end = literal_cursor
.checked_add(literal_length)
.ok_or_else(output_size_overflow_error)?;
let literal_chunk = literals
.get(literal_cursor..literal_end)
.ok_or_else(literal_length_exceeds_buffer_error)?;
out.append(literal_chunk)?;
Ok(literal_end)
}
#[cold]
#[inline(never)]
fn offset_exceeds_history_error() -> Error {
Error::Corruption("sequence offset exceeds the available history window")
}
#[cold]
#[inline(never)]
fn literal_length_exceeds_buffer_error() -> Error {
Error::Corruption("sequence literal length exceeds literals buffer")
}
impl RepeatOffsets {
#[inline(always)]
pub(crate) fn resolve_values(&mut self, literal_length: u32, offset_value: u32) -> Result<u32> {
let [rep1, rep2, rep3] = self.values;
if offset_value > 3 {
let offset = offset_value - 3;
self.values = [offset, rep1, rep2];
return Ok(offset);
}
if offset_value == 0 {
return Err(corruption_error("sequence offset value is zero"));
}
let ll_zero = literal_length == 0;
let rep_index = offset_value + ll_zero as u32;
let offset = match rep_index {
1 => rep1,
2 => rep2,
3 => rep3,
_ => {
if rep1 <= 1 {
return Err(corruption_error("repeat offset 1 minus 1 is zero"));
}
rep1 - 1
}
};
if rep_index > 1 {
self.values[2] = if rep_index == 2 { rep3 } else { rep2 };
self.values[1] = rep1;
self.values[0] = offset;
}
Ok(offset)
}
#[inline(always)]
pub(crate) fn resolve_encode(&mut self, literal_length: u32, offset_value: u32) -> u32 {
debug_assert!(offset_value > 0, "offset_value must be non-zero");
let [rep1, rep2, rep3] = self.values;
if offset_value > 3 {
let offset = offset_value - 3;
self.values = [offset, rep1, rep2];
return offset;
}
let ll_zero = literal_length == 0;
let rep_index = offset_value + ll_zero as u32;
let offset = match rep_index {
1 => rep1,
2 => rep2,
3 => rep3,
_ => {
debug_assert!(rep1 > 1, "rep1-1 would be zero");
rep1 - 1
}
};
if rep_index > 1 {
self.values[2] = if rep_index == 2 { rep3 } else { rep2 };
self.values[1] = rep1;
self.values[0] = offset;
}
offset
}
#[inline(always)]
pub(crate) fn resolve(&mut self, sequence: &SequenceCommand) -> Result<u32> {
self.resolve_values(sequence.literal_length, sequence.offset_value)
}
}
const WILDCOPY_OVERLENGTH: usize = 32;
#[allow(unsafe_code)]
#[inline(always)]
pub(crate) unsafe fn prefetch_match(ptr: *const u8) {
#[cfg(miri)]
let _ = ptr;
#[cfg(not(miri))]
{
#[cfg(target_arch = "aarch64")]
unsafe {
core::arch::asm!(
"prfm pldl1keep, [{ptr}]",
"prfm pldl1keep, [{ptr}, #64]",
ptr = in(reg) ptr,
options(nostack, preserves_flags),
)
};
#[cfg(target_arch = "x86_64")]
{
#[cfg(target_feature = "sse")]
{
unsafe {
core::arch::x86_64::_mm_prefetch::<{ core::arch::x86_64::_MM_HINT_T0 }>(
ptr as *const i8,
)
};
unsafe {
core::arch::x86_64::_mm_prefetch::<{ core::arch::x86_64::_MM_HINT_T0 }>(
ptr.wrapping_add(64) as *const i8,
)
};
}
}
#[cfg(not(any(
all(target_arch = "x86_64", target_feature = "sse"),
target_arch = "aarch64"
)))]
{
let _ = ptr;
}
}
}
#[allow(unsafe_code)]
#[inline(always)]
unsafe fn copy_16(dst: *mut u8, src: *const u8) {
#[cfg(target_arch = "aarch64")]
unsafe {
let v = core::arch::aarch64::vld1q_u8(src);
core::arch::aarch64::vst1q_u8(dst, v);
}
#[cfg(target_arch = "x86_64")]
{
#[cfg(target_feature = "sse2")]
unsafe {
let v = core::arch::x86_64::_mm_loadu_si128(src as *const core::arch::x86_64::__m128i);
core::arch::x86_64::_mm_storeu_si128(dst as *mut core::arch::x86_64::__m128i, v);
}
#[cfg(not(target_feature = "sse2"))]
unsafe {
core::ptr::copy_nonoverlapping(src, dst, 16)
};
}
#[cfg(not(any(target_arch = "aarch64", target_arch = "x86_64")))]
unsafe {
core::ptr::copy_nonoverlapping(src, dst, 16)
};
}
#[allow(unsafe_code)]
#[inline(always)]
fn append_match_from_history(
out: &mut DecodeOut<'_>,
match_start: usize,
match_length: usize,
) -> Result<()> {
if match_length == 0 {
return Ok(());
}
out.ensure_room(match_length)?;
let out_len = out.len();
let offset = out_len - match_start;
if match_length <= offset {
unsafe {
let base = out.as_mut_ptr();
core::ptr::copy_nonoverlapping(base.add(match_start), base.add(out_len), match_length);
out.set_len(out_len + match_length);
}
return Ok(());
}
if offset == 1 {
let value = out.as_slice()[match_start];
unsafe {
core::ptr::write_bytes(out.as_mut_ptr().add(out_len), value, match_length);
out.set_len(out_len + match_length);
}
return Ok(());
}
unsafe {
let base = out.as_mut_ptr();
let dst = base.add(out_len);
let src_start = base.add(match_start);
core::ptr::copy_nonoverlapping(src_start, dst, offset);
let mut copied = offset;
while copied < match_length {
let chunk = copied.min(match_length - copied);
core::ptr::copy_nonoverlapping(dst, dst.add(copied), chunk);
copied += chunk;
}
out.set_len(out_len + match_length);
}
Ok(())
}
#[inline(always)]
fn append_match_from_dictionary_history(
out: &mut DecodeOut<'_>,
frame_start: usize,
dictionary: &[u8],
offset: usize,
match_length: usize,
) -> Result<()> {
if match_length == 0 {
return Ok(());
}
let history_len = dictionary.len() + (out.len() - frame_start);
let source_index = history_len - offset;
if source_index < dictionary.len() {
let dict_chunk_len = (dictionary.len() - source_index).min(match_length);
out.append(&dictionary[source_index..source_index + dict_chunk_len])?;
let remaining = match_length - dict_chunk_len;
if remaining != 0 {
append_match_from_history(out, frame_start, remaining)?;
}
return Ok(());
}
let match_start = frame_start + (source_index - dictionary.len());
append_match_from_history(out, match_start, match_length)
}
#[derive(Debug, Clone, Copy)]
pub(crate) struct OutputLimit {
produced_before: u64,
max_output_size: Option<usize>,
}
impl OutputLimit {
pub(crate) fn whole_output(max_output_size: Option<usize>) -> Self {
Self {
produced_before: 0,
max_output_size,
}
}
pub(crate) fn after(produced_before: u64, max_output_size: Option<usize>) -> Self {
Self {
produced_before,
max_output_size,
}
}
#[inline(always)]
fn produced(&self, out_len: usize) -> u64 {
self.produced_before.saturating_add(out_len as u64)
}
#[inline(always)]
pub(crate) fn check_total(&self, out_len: usize) -> Result<()> {
let Some(max_output_size) = self.max_output_size else {
return Ok(());
};
let produced = self.produced(out_len);
if produced > max_output_size as u64 {
return Err(Error::OutputSizeTooLarge {
output_size: produced,
max_output_size,
});
}
Ok(())
}
#[inline(always)]
fn remaining(&self, out_len: usize) -> Result<usize> {
let Some(limit) = self.max_output_size else {
return Ok(usize::MAX);
};
let produced = self.produced(out_len);
let remaining = (limit as u64)
.checked_sub(produced)
.ok_or(Error::OutputSizeTooLarge {
output_size: produced,
max_output_size: limit,
})?;
Ok(remaining as usize)
}
}
#[inline(always)]
fn reserve_block_output(
out: &mut DecodeOut<'_>,
block_size_max: usize,
limit: OutputLimit,
) -> Result<()> {
let reserve = limit.remaining(out.len())?.min(block_size_max);
out.try_reserve(reserve + WILDCOPY_OVERLENGTH)
}
#[cold]
#[inline(never)]
fn sequence_budget_error(
additional: usize,
block_remaining: usize,
out_len: usize,
limit: OutputLimit,
) -> Error {
if additional > block_remaining {
return corruption_error("compressed block output exceeds the frame block size limit");
}
if let Some(max_output_size) = limit.max_output_size {
let final_len = limit.produced(out_len).saturating_add(additional as u64);
if final_len > max_output_size as u64 {
return Error::OutputSizeTooLarge {
output_size: final_len,
max_output_size,
};
}
}
corruption_error("compressed block output exceeds the frame block size limit")
}
#[inline(always)]
fn ensure_decode_output_room(
out_len: usize,
additional: usize,
remaining_block_bytes: &mut usize,
remaining_output_bytes: &mut usize,
limit: OutputLimit,
) -> Result<()> {
if additional > *remaining_block_bytes {
return Err(corruption_error(
"compressed block output exceeds the frame block size limit",
));
}
*remaining_block_bytes -= additional;
if additional > *remaining_output_bytes {
let max_output_size = limit
.max_output_size
.expect("output limit present when tracking remaining bytes");
let output_size = limit
.produced(out_len)
.checked_add(additional as u64)
.ok_or_else(output_size_overflow_error)?;
return Err(output_size_too_large_error(output_size, max_output_size));
}
*remaining_output_bytes -= additional;
Ok(())
}
#[inline(always)]
fn append_trailing_literals(
out: &mut DecodeOut<'_>,
literals: &[u8],
literal_cursor: usize,
remaining_block_bytes: &mut usize,
remaining_output_bytes: &mut usize,
limit: OutputLimit,
) -> Result<()> {
let trailing = literals.get(literal_cursor..).ok_or(Error::Corruption(
"sequence literal cursor exceeded literals buffer",
))?;
ensure_decode_output_room(
out.len(),
trailing.len(),
remaining_block_bytes,
remaining_output_bytes,
limit,
)?;
out.append(trailing)
}
fn predefined_sequence_dtable(part: SequencePart) -> &'static fse::DTable {
let tables = PREDEFINED_SEQUENCE_DTABLES.get_or_init(|| {
let mut literal_lengths = fse::DTable::default();
let mut offsets = fse::DTable::default();
let mut match_lengths = fse::DTable::default();
fse::build_dtable(
&mut literal_lengths,
&LITERAL_LENGTH_DEFAULT_DISTRIBUTION,
(LITERAL_LENGTH_DEFAULT_DISTRIBUTION.len() - 1) as u32,
LL_DEFAULT_LOG,
)
.expect("literal-length default dtable must build");
fse::build_dtable(
&mut offsets,
&OFFSET_DEFAULT_DISTRIBUTION,
(OFFSET_DEFAULT_DISTRIBUTION.len() - 1) as u32,
OF_DEFAULT_LOG,
)
.expect("offset default dtable must build");
fse::build_dtable(
&mut match_lengths,
&MATCH_LENGTH_DEFAULT_DISTRIBUTION,
(MATCH_LENGTH_DEFAULT_DISTRIBUTION.len() - 1) as u32,
ML_DEFAULT_LOG,
)
.expect("match-length default dtable must build");
PredefinedSequenceDTables {
literal_lengths,
offsets,
match_lengths,
}
});
match part {
SequencePart::LiteralLength => &tables.literal_lengths,
SequencePart::Offset => &tables.offsets,
SequencePart::MatchLength => &tables.match_lengths,
}
}
fn predefined_seq_dtable(part: SequencePart) -> &'static fse::SequenceDTable {
let tables = PREDEFINED_SEQ_DTABLES.get_or_init(|| {
let mut ll = fse::SequenceDTable::default();
let mut of = fse::SequenceDTable::default();
let mut ml = fse::SequenceDTable::default();
fse::build_sequence_dtable_direct(
&mut ll,
&LITERAL_LENGTH_DEFAULT_DISTRIBUTION,
(LITERAL_LENGTH_DEFAULT_DISTRIBUTION.len() - 1) as u32,
LL_DEFAULT_LOG,
&LITERAL_LENGTH_BASELINES,
&LITERAL_LENGTH_EXTRA_BITS,
)
.expect("literal-length default seq dtable must build");
fse::build_offset_sequence_dtable_direct(
&mut of,
&OFFSET_DEFAULT_DISTRIBUTION,
(OFFSET_DEFAULT_DISTRIBUTION.len() - 1) as u32,
OF_DEFAULT_LOG,
)
.expect("offset default seq dtable must build");
fse::build_sequence_dtable_direct(
&mut ml,
&MATCH_LENGTH_DEFAULT_DISTRIBUTION,
(MATCH_LENGTH_DEFAULT_DISTRIBUTION.len() - 1) as u32,
ML_DEFAULT_LOG,
&MATCH_LENGTH_BASELINES,
&MATCH_LENGTH_EXTRA_BITS,
)
.expect("match-length default seq dtable must build");
PredefinedSeqDTables {
literal_lengths: ll,
offsets: of,
match_lengths: ml,
}
});
match part {
SequencePart::LiteralLength => &tables.literal_lengths,
SequencePart::Offset => &tables.offsets,
SequencePart::MatchLength => &tables.match_lengths,
}
}
fn decode_seq_table_both(
dt_slot: &mut Option<fse::DTable>,
seq_dt: &mut fse::SequenceDTable,
has_table: &mut bool,
src: &[u8],
cursor: &mut usize,
part: SequencePart,
mode: CompressionMode,
target: TableTarget,
) -> Result<()> {
let want_dtable = target == TableTarget::Both;
match mode {
CompressionMode::Predefined => {
if want_dtable {
let precomputed_dt = predefined_sequence_dtable(part);
let dt = dt_slot.get_or_insert_with(fse::DTable::default);
let ts = if precomputed_dt.table_log() == 0 {
1
} else {
1usize << precomputed_dt.table_log()
};
dt.copy_active_from(precomputed_dt, ts);
} else {
*dt_slot = None;
}
let precomputed_seq = predefined_seq_dtable(part);
seq_dt.table_log = precomputed_seq.table_log;
let seq_ts = if precomputed_seq.table_log == 0 {
1
} else {
1usize << precomputed_seq.table_log
};
seq_dt.entries[..seq_ts].copy_from_slice(&precomputed_seq.entries[..seq_ts]);
*has_table = true;
}
CompressionMode::Rle => {
let symbol = *src.get(*cursor).ok_or(Error::UnexpectedEof)?;
if symbol > part.max_symbol_value() {
return Err(Error::Corruption(
"sequence RLE symbol exceeds the supported code range",
));
}
if want_dtable {
let dt = dt_slot.get_or_insert_with(fse::DTable::default);
fse::build_rle_dtable(dt, symbol);
} else {
*dt_slot = None;
}
match part {
SequencePart::Offset => {
fse::build_rle_offset_sequence_dtable(seq_dt, symbol);
}
SequencePart::LiteralLength => {
fse::build_rle_sequence_dtable(
seq_dt,
symbol,
&LITERAL_LENGTH_BASELINES,
&LITERAL_LENGTH_EXTRA_BITS,
);
}
SequencePart::MatchLength => {
fse::build_rle_sequence_dtable(
seq_dt,
symbol,
&MATCH_LENGTH_BASELINES,
&MATCH_LENGTH_EXTRA_BITS,
);
}
}
*has_table = true;
*cursor += 1;
}
CompressionMode::FseCompressed => {
let mut normalized = [0i16; fse::SYMBOLVALUE_MAX + 1];
let mut max_symbol_value = u32::from(part.max_symbol_value());
let mut table_log = 0u32;
let consumed = fse::read_ncount(
&mut normalized,
&mut max_symbol_value,
&mut table_log,
&src[*cursor..],
part.max_accuracy_log(),
)?;
if want_dtable {
let dt = dt_slot.get_or_insert_with(fse::DTable::default);
fse::build_dtable(dt, &normalized, max_symbol_value, table_log)?;
} else {
*dt_slot = None;
}
match part {
SequencePart::Offset => {
fse::build_offset_sequence_dtable_direct(
seq_dt,
&normalized,
max_symbol_value,
table_log,
)?;
}
SequencePart::LiteralLength => {
fse::build_sequence_dtable_direct(
seq_dt,
&normalized,
max_symbol_value,
table_log,
&LITERAL_LENGTH_BASELINES,
&LITERAL_LENGTH_EXTRA_BITS,
)?;
}
SequencePart::MatchLength => {
fse::build_sequence_dtable_direct(
seq_dt,
&normalized,
max_symbol_value,
table_log,
&MATCH_LENGTH_BASELINES,
&MATCH_LENGTH_EXTRA_BITS,
)?;
}
}
*has_table = true;
*cursor += consumed;
}
CompressionMode::Repeat => {
if !*has_table {
return Err(Error::Corruption(
"sequence repeat mode requires a previous FSE table",
));
}
}
}
Ok(())
}
impl SequencePart {
fn max_symbol_value(self) -> u8 {
match self {
Self::LiteralLength => 35,
Self::Offset => 31,
Self::MatchLength => 52,
}
}
fn default_allowed(self, max_symbol: u8) -> bool {
max_symbol <= self.default_max_symbol()
}
fn default_max_symbol(self) -> u8 {
match self {
Self::LiteralLength => 35,
Self::Offset => 28,
Self::MatchLength => 52,
}
}
fn max_accuracy_log(self) -> usize {
match self {
Self::LiteralLength | Self::MatchLength => 9,
Self::Offset => 8,
}
}
fn default_distribution(self) -> (&'static [i16], u32) {
match self {
Self::LiteralLength => (&LITERAL_LENGTH_DEFAULT_DISTRIBUTION, 6),
Self::Offset => (&OFFSET_DEFAULT_DISTRIBUTION, 5),
Self::MatchLength => (&MATCH_LENGTH_DEFAULT_DISTRIBUTION, 6),
}
}
}
fn encode_sequence_count(number_of_sequences: usize, dst: &mut OutBuf<'_>) -> Result<()> {
if number_of_sequences >= (1usize << 16) + 0x7F00 {
return Err(Error::InvalidParameter("too many sequences in one block"));
}
encode_sequence_count_unchecked(number_of_sequences, dst);
Ok(())
}
fn encode_sequence_count_unchecked(number_of_sequences: usize, dst: &mut OutBuf<'_>) {
if number_of_sequences < 128 {
dst.push(number_of_sequences as u8);
} else if number_of_sequences < 0x7F00 {
dst.push(128 + ((number_of_sequences >> 8) as u8));
dst.push((number_of_sequences & 0xFF) as u8);
} else {
let value = number_of_sequences - 0x7F00;
dst.push(255);
dst.push((value & 0xFF) as u8);
dst.push(((value >> 8) & 0xFF) as u8);
}
}
fn encode_sequence_command(sequence: &SequenceCommand) -> Result<EncodedSequence> {
let ll_code = literal_length_code(sequence.literal_length)? as usize;
let ml_code = match_length_code(sequence.match_length)? as usize;
let of_code = offset_code(sequence.offset_value)? as usize;
Ok(EncodedSequence {
ll_code: ll_code as u8,
ll_extra: sequence.literal_length - LITERAL_LENGTH_BASELINES[ll_code],
of_code: of_code as u8,
of_extra: sequence.offset_value - (1u32 << of_code),
ml_code: ml_code as u8,
ml_extra: sequence.match_length - MATCH_LENGTH_BASELINES[ml_code],
})
}
#[cfg(test)]
fn build_sequence_part_choice(
part: SequencePart,
codes: &[u8],
previous: Option<&SequenceEncodingPartState>,
parser_strategy: ParserStrategy,
pool: &mut SequenceTablePool,
) -> Result<SequenceTableChoice> {
let stats = analyze_codes(part, codes)?;
let choice = select_table_choice(part, codes, previous, parser_strategy, &stats)?;
build_selected_table_choice(part, codes, previous, &stats, choice, pool)
}
fn select_table_choice(
part: SequencePart,
codes: &[u8],
previous: Option<&SequenceEncodingPartState>,
parser_strategy: ParserStrategy,
stats: &SequenceCodeStats,
) -> Result<CompressionMode> {
if stats.most_frequent == stats.total {
if part.default_allowed(stats.max_symbol) && stats.total <= 2 {
return Ok(CompressionMode::Predefined);
}
return Ok(CompressionMode::Rle);
}
if let Some(choice) =
select_table_choice_fast_path(part, codes, previous, parser_strategy, stats)
{
return Ok(choice);
}
let basic_cost = if part.default_allowed(stats.max_symbol) {
{
let (default_norm, default_log) = part.default_distribution();
cross_entropy_cost_bits(default_norm, default_log, &stats.counts, stats.max_symbol)
}
} else {
u64::MAX
};
let repeat_choice = previous.filter(|entry| {
entry.repeat_mode() != SequenceRepeatMode::None
&& entry.table().supports_all_from_stats(stats)
});
let repeat_cost = match repeat_choice {
Some(entry) => sequence_table_cost_bits(entry.table(), stats)?,
None => u64::MAX,
};
let compressed_cost = (ncount_cost_bytes(part, stats)? as u64 * 8)
+ entropy_cost_bits(&stats.counts, stats.max_symbol, stats.total);
if basic_cost <= repeat_cost && basic_cost <= compressed_cost {
return Ok(CompressionMode::Predefined);
}
if repeat_cost <= compressed_cost {
return Ok(CompressionMode::Repeat);
}
Ok(CompressionMode::FseCompressed)
}
fn select_table_choice_fast_path(
part: SequencePart,
_codes: &[u8],
previous: Option<&SequenceEncodingPartState>,
parser_strategy: ParserStrategy,
stats: &SequenceCodeStats,
) -> Option<CompressionMode> {
if parser_strategy.zstd_rank() >= ParserStrategy::Lazy.zstd_rank() {
return None;
}
if !part.default_allowed(stats.max_symbol) {
return Some(CompressionMode::FseCompressed);
}
let repeat_choice = previous.filter(|entry| {
entry.repeat_mode() == SequenceRepeatMode::Valid
&& entry.table().supports_all_from_stats(stats)
});
if repeat_choice.is_some() && stats.total < FAST_SELECTOR_REPEAT_MAX_SEQUENCES {
return Some(CompressionMode::Repeat);
}
let (_, default_log) = part.default_distribution();
let multiplier = 10usize.saturating_sub(parser_strategy.zstd_rank() as usize);
let dynamic_fse_nb_seq_min = ((1usize << default_log) * multiplier) >> 3;
if stats.total < dynamic_fse_nb_seq_min
|| stats.most_frequent < (stats.total >> (default_log - 1))
{
return Some(CompressionMode::Predefined);
}
Some(CompressionMode::FseCompressed)
}
fn build_selected_table_choice(
part: SequencePart,
codes: &[u8],
previous: Option<&SequenceEncodingPartState>,
stats: &SequenceCodeStats,
mode: CompressionMode,
pool: &mut SequenceTablePool,
) -> Result<SequenceTableChoice> {
match mode {
CompressionMode::Predefined => Ok(build_predefined_table_choice(part)),
CompressionMode::Rle => build_rle_table_choice(part, stats.max_symbol, pool),
CompressionMode::Repeat => previous
.filter(|entry| entry.repeat_mode() != SequenceRepeatMode::None)
.filter(|entry| entry.table().supports_all(codes))
.map(build_repeat_table_choice)
.ok_or(Error::Generic),
CompressionMode::FseCompressed => {
build_compressed_table_choice(part, codes, stats, pool)?.ok_or(Error::Generic)
}
}
}
#[cfg(test)]
fn analyze_codes(part: SequencePart, codes: &[u8]) -> Result<SequenceCodeStats> {
let max_allowed = part.max_symbol_value();
let mut counts = [0u32; fse::SYMBOLVALUE_MAX + 1];
#[allow(unsafe_code)]
for &code in codes {
debug_assert!(code <= max_allowed);
unsafe { *counts.get_unchecked_mut(code as usize) += 1 };
}
let mut max_symbol = 0u8;
let mut most_frequent = 0u32;
for (symbol, &count) in counts[..=max_allowed as usize].iter().enumerate() {
if count > most_frequent {
most_frequent = count;
max_symbol = symbol as u8;
}
}
for symbol in (0..=max_allowed as usize).rev() {
if counts[symbol] > 0 {
max_symbol = symbol as u8;
break;
}
}
Ok(SequenceCodeStats {
counts,
max_symbol,
most_frequent: most_frequent as usize,
total: codes.len(),
})
}
const HISTOGRAM_LANES: usize = 4;
const HISTOGRAM_LANE_MIN_SEQUENCES: usize = 2048;
type CodeCounts = [u32; fse::SYMBOLVALUE_MAX + 1];
#[inline]
fn count_codes_serial(
literal_codes: &[u8],
offset_codes: &[u8],
match_codes: &[u8],
ll_counts: &mut CodeCounts,
of_counts: &mut CodeCounts,
ml_counts: &mut CodeCounts,
) {
#[allow(unsafe_code)]
for index in 0..literal_codes.len() {
unsafe {
let ll = *literal_codes.get_unchecked(index);
let of = *offset_codes.get_unchecked(index);
let ml = *match_codes.get_unchecked(index);
*ll_counts.get_unchecked_mut(ll as usize) += 1;
*of_counts.get_unchecked_mut(of as usize) += 1;
*ml_counts.get_unchecked_mut(ml as usize) += 1;
}
}
}
#[inline(never)]
fn count_codes_interleaved(
literal_codes: &[u8],
offset_codes: &[u8],
match_codes: &[u8],
ll_counts: &mut CodeCounts,
of_counts: &mut CodeCounts,
ml_counts: &mut CodeCounts,
) {
let total = literal_codes.len();
let mut ll_lanes = [[0u32; fse::SYMBOLVALUE_MAX + 1]; HISTOGRAM_LANES];
let mut of_lanes = [[0u32; fse::SYMBOLVALUE_MAX + 1]; HISTOGRAM_LANES];
let mut ml_lanes = [[0u32; fse::SYMBOLVALUE_MAX + 1]; HISTOGRAM_LANES];
#[allow(unsafe_code)]
{
let whole = total - total % HISTOGRAM_LANES;
let mut index = 0;
while index < whole {
for (lane, ((ll_lane, of_lane), ml_lane)) in ll_lanes
.iter_mut()
.zip(of_lanes.iter_mut())
.zip(ml_lanes.iter_mut())
.enumerate()
{
unsafe {
let ll = *literal_codes.get_unchecked(index + lane);
let of = *offset_codes.get_unchecked(index + lane);
let ml = *match_codes.get_unchecked(index + lane);
*ll_lane.get_unchecked_mut(ll as usize) += 1;
*of_lane.get_unchecked_mut(of as usize) += 1;
*ml_lane.get_unchecked_mut(ml as usize) += 1;
}
}
index += HISTOGRAM_LANES;
}
while index < total {
unsafe {
let ll = *literal_codes.get_unchecked(index);
let of = *offset_codes.get_unchecked(index);
let ml = *match_codes.get_unchecked(index);
*ll_lanes[0].get_unchecked_mut(ll as usize) += 1;
*of_lanes[0].get_unchecked_mut(of as usize) += 1;
*ml_lanes[0].get_unchecked_mut(ml as usize) += 1;
}
index += 1;
}
}
for lane in 0..HISTOGRAM_LANES {
for symbol in 0..=fse::SYMBOLVALUE_MAX {
ll_counts[symbol] += ll_lanes[lane][symbol];
of_counts[symbol] += of_lanes[lane][symbol];
ml_counts[symbol] += ml_lanes[lane][symbol];
}
}
}
pub(crate) fn analyze_all_codes(
literal_codes: &[u8],
offset_codes: &[u8],
match_codes: &[u8],
) -> (SequenceCodeStats, SequenceCodeStats, SequenceCodeStats) {
debug_assert_eq!(literal_codes.len(), offset_codes.len());
debug_assert_eq!(literal_codes.len(), match_codes.len());
let total = literal_codes.len();
let ll_max = SequencePart::LiteralLength.max_symbol_value() as usize;
let of_max = SequencePart::Offset.max_symbol_value() as usize;
let ml_max = SequencePart::MatchLength.max_symbol_value() as usize;
let mut ll_counts = [0u32; fse::SYMBOLVALUE_MAX + 1];
let mut of_counts = [0u32; fse::SYMBOLVALUE_MAX + 1];
let mut ml_counts = [0u32; fse::SYMBOLVALUE_MAX + 1];
if total >= HISTOGRAM_LANE_MIN_SEQUENCES {
count_codes_interleaved(
literal_codes,
offset_codes,
match_codes,
&mut ll_counts,
&mut of_counts,
&mut ml_counts,
);
} else {
count_codes_serial(
literal_codes,
offset_codes,
match_codes,
&mut ll_counts,
&mut of_counts,
&mut ml_counts,
);
}
#[inline(always)]
fn finalize_stats(
counts: [u32; fse::SYMBOLVALUE_MAX + 1],
max_allowed: usize,
total: usize,
) -> SequenceCodeStats {
let mut most_frequent = 0u32;
let mut max_symbol = 0u8;
for symbol in (0..=max_allowed).rev() {
let count = counts[symbol];
if count > 0 && max_symbol == 0 {
max_symbol = symbol as u8;
}
if count > most_frequent {
most_frequent = count;
}
}
SequenceCodeStats {
counts,
max_symbol,
most_frequent: most_frequent as usize,
total,
}
}
(
finalize_stats(ll_counts, ll_max, total),
finalize_stats(of_counts, of_max, total),
finalize_stats(ml_counts, ml_max, total),
)
}
fn cross_entropy_cost_bits(
default_norm: &[i16],
default_log: u32,
counts: &[u32; fse::SYMBOLVALUE_MAX + 1],
max_symbol: u8,
) -> u64 {
let shift = COST_ACCURACY_LOG - default_log;
let mut cost = 0u64;
for symbol in 0..=max_symbol as usize {
let norm_acc = if default_norm[symbol] == -1 {
1u32
} else {
default_norm[symbol] as u32
};
let norm256 = (norm_acc << shift) as usize;
cost += u64::from(counts[symbol]) * u64::from(INVERSE_PROBABILITY_LOG256[norm256]);
}
cost >> COST_ACCURACY_LOG
}
fn entropy_cost_bits(
counts: &[u32; fse::SYMBOLVALUE_MAX + 1],
max_symbol: u8,
total: usize,
) -> u64 {
debug_assert!(total > 0);
let mut cost = 0u64;
for symbol in 0..=max_symbol as usize {
let count = counts[symbol];
if count == 0 {
continue;
}
let mut norm = ((256u64 * u64::from(count)) / total as u64) as usize;
if norm == 0 {
norm = 1;
}
cost += u64::from(count) * u64::from(INVERSE_PROBABILITY_LOG256[norm]);
}
cost >> COST_ACCURACY_LOG
}
fn ncount_cost_bytes(part: SequencePart, stats: &SequenceCodeStats) -> Result<usize> {
let table_log = fse::optimal_table_log(
part.max_accuracy_log() as u32,
stats.total,
stats.max_symbol.into(),
);
let mut normalized = [0i16; fse::SYMBOLVALUE_MAX + 1];
if fse::normalize_count(
&mut normalized,
table_log,
&stats.counts,
stats.total,
stats.max_symbol.into(),
stats.total >= 2048,
)? == 0
{
return Err(Error::Generic);
}
let bound = fse::ncount_write_bound(stats.max_symbol.into(), table_log)?;
let mut header = [0u8; fse::NCOUNT_WRITE_BOUND_MAX];
fse::write_ncount(
&mut header[..bound],
&normalized,
stats.max_symbol.into(),
table_log,
)
}
fn sequence_table_cost_bits(
table: &SequenceEncodingTable,
stats: &SequenceCodeStats,
) -> Result<u64> {
if fse::ctable_max_symbol_value(table.ctable()) < u32::from(stats.max_symbol) {
return Ok(u64::MAX);
}
let bad_cost = (fse::ctable_log(table.ctable()) + 1) << COST_ACCURACY_LOG;
let mut cost = 0u64;
for symbol in 0..=stats.max_symbol as usize {
let count = stats.counts[symbol];
if count == 0 {
continue;
}
let bit_cost = fse::ctable_bit_cost(table.ctable(), symbol as u8, COST_ACCURACY_LOG)?;
if bit_cost >= bad_cost {
return Ok(u64::MAX);
}
cost += u64::from(count) * u64::from(bit_cost);
}
Ok(cost >> COST_ACCURACY_LOG)
}
pub(crate) fn build_literal_offset_table(sequences: &[SequenceCommand]) -> Vec<usize> {
let mut offsets = Vec::with_capacity(sequences.len() + 1);
offsets.push(0);
let mut cum = 0usize;
for seq in sequences {
cum += seq.literal_length as usize;
offsets.push(cum);
}
offsets
}
pub(crate) fn estimate_subblock_cost_bits(
literal_codes: &[u8],
offset_codes: &[u8],
match_codes: &[u8],
literals: &[u8],
prev_seq_tables: Option<&SequenceEncodingState>,
prev_huf_table: Option<&huff0::CTableX1>,
literals_compression_disabled: bool,
) -> u64 {
let nb_seq = literal_codes.len();
if nb_seq == 0 {
return (literals.len() as u64 * 8) + 24 + 24;
}
let (ll_stats, of_stats, ml_stats) =
analyze_all_codes(literal_codes, offset_codes, match_codes);
let ll_est = estimate_part_cost(
SequencePart::LiteralLength,
&ll_stats,
prev_seq_tables.and_then(|s| s.entry(SequencePart::LiteralLength)),
);
let of_est = estimate_part_cost(
SequencePart::Offset,
&of_stats,
prev_seq_tables.and_then(|s| s.entry(SequencePart::Offset)),
);
let ml_est = estimate_part_cost(
SequencePart::MatchLength,
&ml_stats,
prev_seq_tables.and_then(|s| s.entry(SequencePart::MatchLength)),
);
let seq_cost_bytes =
ll_est.symbol_cost_bytes + of_est.symbol_cost_bytes + ml_est.symbol_cost_bytes;
let fse_tables_size = ll_est.header_bytes + of_est.header_bytes + ml_est.header_bytes;
let seq_count_bytes = if nb_seq < 128 {
1u64
} else if nb_seq < 0x7F00 {
2
} else {
3
};
let seq_header = 1 + seq_count_bytes;
let lit_cost_bytes = if literals.is_empty() {
0
} else {
estimate_literal_cost_bytes(literals, prev_huf_table, literals_compression_disabled)
};
let total_bytes = seq_cost_bytes + fse_tables_size + seq_header + lit_cost_bytes + 3;
total_bytes * 8
}
struct PartCostEstimate {
symbol_cost_bytes: u64,
header_bytes: u64,
}
fn estimate_part_cost(
part: SequencePart,
stats: &SequenceCodeStats,
prev_state: Option<&SequenceEncodingPartState>,
) -> PartCostEstimate {
if stats.total == 0 {
return PartCostEstimate {
symbol_cost_bytes: 0,
header_bytes: 0,
};
}
let total_extra_bits: u64 = match part {
SequencePart::LiteralLength => (0..=stats.max_symbol as usize)
.map(|c| u64::from(stats.counts[c]) * u64::from(ll_bits(c as u8)))
.sum(),
SequencePart::Offset => (0..=stats.max_symbol as usize)
.map(|c| u64::from(stats.counts[c]) * c as u64)
.sum(),
SequencePart::MatchLength => (0..=stats.max_symbol as usize)
.map(|c| u64::from(stats.counts[c]) * u64::from(ml_bits(c as u8)))
.sum(),
};
if stats.most_frequent == stats.total {
if part.default_allowed(stats.max_symbol) && stats.total <= 2 {
let (default_norm, default_log) = part.default_distribution();
let basic_bits =
cross_entropy_cost_bits(default_norm, default_log, &stats.counts, stats.max_symbol);
return PartCostEstimate {
symbol_cost_bytes: (basic_bits + total_extra_bits) >> 3,
header_bytes: 0,
};
}
return PartCostEstimate {
symbol_cost_bytes: total_extra_bits >> 3,
header_bytes: 0,
};
}
let basic_cost = if part.default_allowed(stats.max_symbol) {
let (default_norm, default_log) = part.default_distribution();
cross_entropy_cost_bits(default_norm, default_log, &stats.counts, stats.max_symbol)
} else {
u64::MAX
};
let repeat_cost = match prev_state {
Some(entry)
if entry.repeat_mode() != SequenceRepeatMode::None
&& entry.table().supports_all_from_stats(stats) =>
{
sequence_table_cost_bits(entry.table(), stats).unwrap_or(u64::MAX)
}
_ => u64::MAX,
};
let ncount_header_bytes = ncount_cost_bytes(part, stats).unwrap_or(usize::MAX);
let compressed_selection_cost = if ncount_header_bytes < usize::MAX {
let shannon_bits = entropy_cost_bits(&stats.counts, stats.max_symbol, stats.total);
(ncount_header_bytes as u64 * 8).saturating_add(shannon_bits)
} else {
u64::MAX
};
enum SelectedType {
Basic,
Repeat,
Compressed,
}
let selected = if basic_cost <= repeat_cost && basic_cost <= compressed_selection_cost {
SelectedType::Basic
} else if repeat_cost <= compressed_selection_cost {
SelectedType::Repeat
} else {
SelectedType::Compressed
};
match selected {
SelectedType::Basic => {
PartCostEstimate {
symbol_cost_bytes: (basic_cost + total_extra_bits) >> 3,
header_bytes: 0,
}
}
SelectedType::Repeat => {
PartCostEstimate {
symbol_cost_bytes: (repeat_cost + total_extra_bits) >> 3,
header_bytes: 0,
}
}
SelectedType::Compressed => {
let code_cost = estimate_fse_code_cost_bits(part, stats);
PartCostEstimate {
symbol_cost_bytes: (code_cost + total_extra_bits) >> 3,
header_bytes: ncount_header_bytes as u64,
}
}
}
}
fn estimate_fse_code_cost_bits(part: SequencePart, stats: &SequenceCodeStats) -> u64 {
let table_log = fse::optimal_table_log(
part.max_accuracy_log() as u32,
stats.total,
stats.max_symbol.into(),
);
let mut normalized = [0i16; fse::SYMBOLVALUE_MAX + 1];
let effective_table_log = match fse::normalize_count(
&mut normalized,
table_log,
&stats.counts,
stats.total,
stats.max_symbol.into(),
stats.total >= 2048,
) {
Ok(tl) if tl > 0 => tl,
_ => return u64::MAX,
};
let mut ctable = fse::CTable::default();
if fse::build_ctable(
&mut ctable,
&normalized,
stats.max_symbol as u32,
effective_table_log,
)
.is_err()
{
return u64::MAX;
}
let bad_cost = (effective_table_log + 1) << COST_ACCURACY_LOG;
let mut cost = 0u64;
for symbol in 0..=stats.max_symbol as usize {
if stats.counts[symbol] == 0 {
continue;
}
let bit_cost = match fse::ctable_bit_cost(&ctable, symbol as u8, COST_ACCURACY_LOG) {
Ok(c) => c,
Err(_) => return u64::MAX,
};
if bit_cost >= bad_cost {
return u64::MAX;
}
cost += u64::from(stats.counts[symbol]) * u64::from(bit_cost);
}
cost >> COST_ACCURACY_LOG
}
fn estimate_literal_cost_bytes(
literals: &[u8],
prev_huf_table: Option<&huff0::CTableX1>,
literals_compression_disabled: bool,
) -> u64 {
let lit_len = literals.len();
if literals_compression_disabled {
return lit_len as u64;
}
let lit_header_bytes: u64 = 3 + (lit_len >= 1024) as u64 + (lit_len >= 16384) as u64;
match huff0::estimate_literal_section_bytes_with_repeat(literals, prev_huf_table) {
Some(compressed_bytes) => lit_header_bytes + compressed_bytes as u64,
None => {
lit_header_bytes + lit_len as u64
}
}
}
pub(crate) fn reconcile_subblock_repcodes(
sequences: &mut [SequenceCommand],
offset_codes: &mut [u8],
decoder_reps: &mut RepeatOffsets,
compressor_reps: &mut RepeatOffsets,
) {
for (i, seq) in sequences.iter_mut().enumerate() {
let ll0 = seq.literal_length == 0;
if seq.offset_value >= 1 && seq.offset_value <= 3 {
let c_raw = resolve_repcode_to_raw(compressor_reps.values(), seq.offset_value, ll0);
let d_raw = resolve_repcode_to_raw(decoder_reps.values(), seq.offset_value, ll0);
if c_raw != d_raw {
seq.offset_value = c_raw + 3;
offset_codes[i] = offset_code_unchecked(seq.offset_value);
}
}
advance_rep_state(compressor_reps, seq.offset_value, ll0);
advance_rep_state(decoder_reps, seq.offset_value, ll0);
}
}
fn resolve_repcode_to_raw(reps: [u32; 3], offset_value: u32, ll0: bool) -> u32 {
let adj = if ll0 { offset_value } else { offset_value - 1 };
if adj == 3 {
reps[0].saturating_sub(1)
} else {
reps[adj as usize]
}
}
fn advance_rep_state(reps: &mut RepeatOffsets, offset_value: u32, ll0: bool) {
let vals = reps.values();
if offset_value >= 4 {
let raw = offset_value - 3;
*reps = RepeatOffsets::from_values([raw, vals[0], vals[1]]);
} else {
let adj = if ll0 { offset_value } else { offset_value - 1 };
match adj {
0 => { }
1 => *reps = RepeatOffsets::from_values([vals[1], vals[0], vals[2]]),
2 => *reps = RepeatOffsets::from_values([vals[2], vals[0], vals[1]]),
3 => {
let new0 = vals[0].saturating_sub(1);
*reps = RepeatOffsets::from_values([new0, vals[0], vals[1]]);
}
_ => {}
}
}
}
fn detect_long_offsets(offset_codes: &[u8]) -> bool {
offset_codes
.iter()
.copied()
.any(|code| u32::from(code) >= STREAM_ACCUMULATOR_MIN)
}
fn build_predefined_table_choice(part: SequencePart) -> SequenceTableChoice {
let tables = predefined_sequence_ctables();
SequenceTableChoice {
mode: CompressionMode::Predefined,
header: Vec::new(),
encoding: match part {
SequencePart::LiteralLength => tables.literal_lengths.clone(),
SequencePart::Offset => tables.offsets.clone(),
SequencePart::MatchLength => tables.match_lengths.clone(),
},
persist_mode: None,
}
}
fn build_repeat_table_choice(previous: &SequenceEncodingPartState) -> SequenceTableChoice {
SequenceTableChoice {
mode: CompressionMode::Repeat,
header: Vec::new(),
encoding: previous.table().clone(),
persist_mode: Some(previous.repeat_mode()),
}
}
fn build_rle_table_choice(
part: SequencePart,
symbol: u8,
pool: &mut SequenceTablePool,
) -> Result<SequenceTableChoice> {
let encoding = pool.build(part, |inner| {
fse::build_rle_ctable(&mut inner.table, symbol);
inner.supported_symbols.fill(false);
inner.supported_symbols[symbol as usize] = true;
Ok(())
})?;
Ok(SequenceTableChoice {
mode: CompressionMode::Rle,
header: vec![symbol],
encoding,
persist_mode: None,
})
}
fn build_compressed_table_choice(
part: SequencePart,
codes: &[u8],
stats: &SequenceCodeStats,
pool: &mut SequenceTablePool,
) -> Result<Option<SequenceTableChoice>> {
if codes.len() <= 1 {
return Ok(None);
}
let table_log = fse::optimal_table_log(
part.max_accuracy_log() as u32,
codes.len(),
stats.max_symbol.into(),
);
let mut effective_counts = stats.counts;
let last_symbol = *codes.last().ok_or(Error::UnexpectedEof)? as usize;
let mut effective_total = codes.len();
if effective_counts[last_symbol] > 1 {
effective_counts[last_symbol] -= 1;
effective_total -= 1;
}
if effective_total <= 1 {
return Ok(None);
}
let mut normalized = [0i16; fse::SYMBOLVALUE_MAX + 1];
if fse::normalize_count(
&mut normalized,
table_log,
&effective_counts,
effective_total,
stats.max_symbol.into(),
effective_total >= 2048,
)? == 0
{
return Ok(None);
}
let mut header = vec![0u8; fse::ncount_write_bound(stats.max_symbol.into(), table_log)?];
let header_size =
fse::write_ncount(&mut header, &normalized, stats.max_symbol.into(), table_log)?;
header.truncate(header_size);
let encoding = pool.build(part, |inner| {
inner.fill_from_normalized_counts(&normalized, stats.max_symbol.into(), table_log)
})?;
debug_assert_eq!(
encoding.inner.supported_symbols,
supported_symbols_from_codes(codes),
"the table's own symbol coverage must agree with the codes it was built from",
);
Ok(Some(SequenceTableChoice {
mode: CompressionMode::FseCompressed,
header,
encoding,
persist_mode: Some(SequenceRepeatMode::Check),
}))
}
pub(crate) fn repeat_mode_for_normalized_counts(
normalized: &[i16; fse::SYMBOLVALUE_MAX + 1],
dict_max_symbol_value: u32,
required_max_symbol_value: u32,
) -> SequenceRepeatMode {
if dict_max_symbol_value < required_max_symbol_value {
return SequenceRepeatMode::Check;
}
for symbol in 0..=required_max_symbol_value as usize {
if normalized[symbol] == 0 {
return SequenceRepeatMode::Check;
}
}
SequenceRepeatMode::Valid
}
fn all_symbols_supported() -> [bool; fse::SYMBOLVALUE_MAX + 1] {
[true; fse::SYMBOLVALUE_MAX + 1]
}
fn supported_symbols_from_codes(codes: &[u8]) -> [bool; fse::SYMBOLVALUE_MAX + 1] {
let mut supported = [false; fse::SYMBOLVALUE_MAX + 1];
for &code in codes {
supported[code as usize] = true;
}
supported
}
pub(crate) fn literal_length_code(literal_length: u32) -> Result<u32> {
if literal_length <= 63 {
Ok(u32::from(
LITERAL_LENGTH_CODE_TABLE[literal_length as usize],
))
} else if literal_length <= 0x1_FFFF {
Ok(highbit32(literal_length) + 19)
} else {
Err(Error::InvalidParameter(
"literal length exceeds the supported range",
))
}
}
pub(crate) fn match_length_code(match_length: u32) -> Result<u32> {
if match_length < 3 {
return Err(Error::InvalidParameter(
"match length must be at least 3 bytes",
));
}
let ml_base = match_length - 3;
if ml_base <= 127 {
Ok(u32::from(MATCH_LENGTH_CODE_TABLE[ml_base as usize]))
} else if ml_base <= 0x1_FFFF {
Ok(highbit32(ml_base) + 36)
} else {
Err(Error::InvalidParameter(
"match length exceeds the supported range",
))
}
}
pub(crate) fn offset_code(offset_value: u32) -> Result<u32> {
if offset_value == 0 {
return Err(Error::InvalidParameter("offset value must be non-zero"));
}
Ok(highbit32(offset_value))
}
#[inline(always)]
pub(crate) fn literal_length_code_unchecked(literal_length: u32) -> u8 {
if literal_length <= 63 {
LITERAL_LENGTH_CODE_TABLE[literal_length as usize]
} else {
debug_assert!(literal_length <= 0x1_FFFF);
(highbit32(literal_length) + 19) as u8
}
}
#[inline(always)]
pub(crate) fn match_length_code_unchecked(match_length: u32) -> u8 {
debug_assert!(match_length >= 3);
let ml_base = match_length - 3;
if ml_base <= 127 {
MATCH_LENGTH_CODE_TABLE[ml_base as usize]
} else {
debug_assert!(ml_base <= 0x1_FFFF);
(highbit32(ml_base) + 36) as u8
}
}
#[inline(always)]
pub(crate) fn offset_code_unchecked(offset_value: u32) -> u8 {
debug_assert!(offset_value > 0);
highbit32(offset_value) as u8
}
pub(crate) fn estimate_sequence_bit_cost(
raw_offset: u32,
literal_length: u32,
match_length: u32,
repeat_offsets: RepeatOffsets,
) -> Result<u32> {
let mut repeat_offsets = repeat_offsets;
let offset_value = repeat_offsets.encode_offset_value(raw_offset, literal_length)?;
let ll_code = literal_length_code(literal_length)? as u8;
let ml_code = match_length_code(match_length)? as u8;
let of_code = offset_code(offset_value)?;
Ok(ll_bits(ll_code) + ml_bits(ml_code) + of_code + 22)
}
fn encode_sequence_bitstream_into(
dst: &mut Vec<u8>,
sequences: &[EncodedSequence],
extra_bits: usize,
literal_lengths: &fse::CTable,
offsets: &fse::CTable,
match_lengths: &fse::CTable,
long_offsets: bool,
) -> Result<()> {
let bit_capacity = sequence_bitstream_bound_bits(
sequences.len(),
extra_bits,
literal_lengths,
offsets,
match_lengths,
);
let byte_capacity = bit_capacity.div_ceil(8) + CONTAINER_BYTES + 8;
if dst.len() < byte_capacity {
dst.resize(byte_capacity, 0);
}
let written = {
let mut stream = BitCStream::new(&mut dst[..byte_capacity])?;
let last = sequences.last().ok_or(Error::UnexpectedEof)?;
let mut state_match_lengths = fse::CState::default();
let mut state_offsets = fse::CState::default();
let mut state_literal_lengths = fse::CState::default();
fse::init_cstate2(&mut state_match_lengths, match_lengths, last.ml_code)?;
fse::init_cstate2(&mut state_offsets, offsets, last.of_code)?;
fse::init_cstate2(&mut state_literal_lengths, literal_lengths, last.ll_code)?;
add_bits_checked(&mut stream, last.ll_extra.into(), ll_bits(last.ll_code))?;
add_bits_checked(&mut stream, last.ml_extra.into(), ml_bits(last.ml_code))?;
add_offset_bits_checked(
&mut stream,
last.of_extra.into(),
u32::from(last.of_code),
long_offsets,
)?;
stream.flush_bits();
#[allow(unsafe_code)]
if !long_offsets {
for sequence in sequences[..sequences.len() - 1].iter().rev() {
let ml_nbits = ml_bits(sequence.ml_code);
let of_nbits = u32::from(sequence.of_code);
unsafe {
fse::encode_symbol_unchecked(
&mut stream,
&mut state_offsets,
offsets,
sequence.of_code,
);
fse::encode_symbol_unchecked(
&mut stream,
&mut state_match_lengths,
match_lengths,
sequence.ml_code,
);
fse::encode_symbol_unchecked(
&mut stream,
&mut state_literal_lengths,
literal_lengths,
sequence.ll_code,
);
}
stream.add_bits_fast(sequence.ll_extra.into(), ll_bits(sequence.ll_code));
if stream.bit_pos + ml_nbits + of_nbits >= STREAM_ACCUMULATOR_MIN {
stream.flush_bits_fast();
}
stream.add_bits_fast(sequence.ml_extra.into(), ml_nbits);
stream.add_bits_fast(sequence.of_extra.into(), of_nbits);
stream.flush_bits_fast();
}
} else {
for sequence in sequences[..sequences.len() - 1].iter().rev() {
ensure_bits_capacity(&mut stream, fse::ctable_log(offsets))?;
fse::encode_symbol(&mut stream, &mut state_offsets, offsets, sequence.of_code)?;
ensure_bits_capacity(&mut stream, fse::ctable_log(match_lengths))?;
fse::encode_symbol(
&mut stream,
&mut state_match_lengths,
match_lengths,
sequence.ml_code,
)?;
ensure_bits_capacity(&mut stream, fse::ctable_log(literal_lengths))?;
fse::encode_symbol(
&mut stream,
&mut state_literal_lengths,
literal_lengths,
sequence.ll_code,
)?;
add_bits_checked(
&mut stream,
sequence.ll_extra.into(),
ll_bits(sequence.ll_code),
)?;
add_bits_checked(
&mut stream,
sequence.ml_extra.into(),
ml_bits(sequence.ml_code),
)?;
add_offset_bits_checked(
&mut stream,
sequence.of_extra.into(),
u32::from(sequence.of_code),
long_offsets,
)?;
}
}
ensure_bits_capacity(&mut stream, fse::ctable_log(match_lengths))?;
fse::flush_cstate(&mut stream, &state_match_lengths, match_lengths)?;
ensure_bits_capacity(&mut stream, fse::ctable_log(offsets))?;
fse::flush_cstate(&mut stream, &state_offsets, offsets)?;
ensure_bits_capacity(&mut stream, fse::ctable_log(literal_lengths))?;
fse::flush_cstate(&mut stream, &state_literal_lengths, literal_lengths)?;
stream.close()
};
if written == 0 {
return Err(Error::DstSizeTooSmall);
}
dst.truncate(written);
Ok(())
}
fn sequence_bitstream_bound_bits(
sequence_count: usize,
extra_bits: usize,
literal_lengths: &fse::CTable,
offsets: &fse::CTable,
match_lengths: &fse::CTable,
) -> usize {
let state_bits = (fse::ctable_log(literal_lengths)
+ fse::ctable_log(offsets)
+ fse::ctable_log(match_lengths)) as usize;
let mut bits = state_bits + extra_bits;
if sequence_count > 1 {
bits += (sequence_count - 1) * state_bits;
}
bits + 1
}
fn extra_bits_from_code_counts(
literal_stats: &SequenceCodeStats,
offset_stats: &SequenceCodeStats,
match_stats: &SequenceCodeStats,
) -> usize {
fn weighted(stats: &SequenceCodeStats, last: usize, width: impl Fn(usize) -> usize) -> usize {
debug_assert_eq!(
stats.counts[..=last].iter().sum::<u32>() as usize,
stats.total,
"a sequence code outside its alphabet would size the bitstream buffer short"
);
(0..=last)
.map(|code| stats.counts[code] as usize * width(code))
.sum()
}
fn alphabet_end(stats: &SequenceCodeStats, extra_bits: &[u8]) -> usize {
(stats.max_symbol as usize).min(extra_bits.len() - 1)
}
let literal_end = alphabet_end(literal_stats, &LITERAL_LENGTH_EXTRA_BITS);
let match_end = alphabet_end(match_stats, &MATCH_LENGTH_EXTRA_BITS);
weighted(literal_stats, literal_end, |code| {
LITERAL_LENGTH_EXTRA_BITS[code] as usize
}) + weighted(match_stats, match_end, |code| {
MATCH_LENGTH_EXTRA_BITS[code] as usize
})
+ weighted(offset_stats, offset_stats.max_symbol as usize, |code| code)
}
fn encode_sequence_bitstream_direct_into(
dst: &mut Vec<u8>,
sequences: &[SequenceCommand],
ll_codes: &[u8],
of_codes: &[u8],
ml_codes: &[u8],
extra_bits: usize,
literal_lengths_table: &fse::CTable,
offsets_table: &fse::CTable,
match_lengths_table: &fse::CTable,
long_offsets: bool,
) -> Result<()> {
let bit_capacity = sequence_bitstream_bound_bits(
sequences.len(),
extra_bits,
literal_lengths_table,
offsets_table,
match_lengths_table,
);
let byte_capacity = bit_capacity.div_ceil(8) + CONTAINER_BYTES + 8;
if dst.len() < byte_capacity {
dst.resize(byte_capacity, 0);
}
let n = sequences.len();
let written = {
let mut stream = BitCStream::new(&mut dst[..byte_capacity])?;
let mut state_match_lengths = fse::CState::default();
let mut state_offsets = fse::CState::default();
let mut state_literal_lengths = fse::CState::default();
let last_ll_code = ll_codes[n - 1];
let last_of_code = of_codes[n - 1];
let last_ml_code = ml_codes[n - 1];
let last = &sequences[n - 1];
fse::init_cstate2(&mut state_match_lengths, match_lengths_table, last_ml_code)?;
fse::init_cstate2(&mut state_offsets, offsets_table, last_of_code)?;
fse::init_cstate2(
&mut state_literal_lengths,
literal_lengths_table,
last_ll_code,
)?;
let last_ll_extra = last.literal_length - LITERAL_LENGTH_BASELINES[last_ll_code as usize];
let last_of_extra = last.offset_value - (1u32 << last_of_code);
let last_ml_extra = last.match_length - MATCH_LENGTH_BASELINES[last_ml_code as usize];
add_bits_checked(&mut stream, last_ll_extra.into(), ll_bits(last_ll_code))?;
add_bits_checked(&mut stream, last_ml_extra.into(), ml_bits(last_ml_code))?;
add_offset_bits_checked(
&mut stream,
last_of_extra.into(),
u32::from(last_of_code),
long_offsets,
)?;
stream.flush_bits();
#[allow(unsafe_code)]
if !long_offsets {
for i in (0..n - 1).rev() {
unsafe {
let seq = sequences.get_unchecked(i);
let ll_code = *ll_codes.get_unchecked(i);
let of_code = *of_codes.get_unchecked(i);
let ml_code = *ml_codes.get_unchecked(i);
let ml_nbits = ml_bits(ml_code);
let of_nbits = u32::from(of_code);
fse::encode_symbol_unchecked(
&mut stream,
&mut state_offsets,
offsets_table,
of_code,
);
fse::encode_symbol_unchecked(
&mut stream,
&mut state_match_lengths,
match_lengths_table,
ml_code,
);
fse::encode_symbol_unchecked(
&mut stream,
&mut state_literal_lengths,
literal_lengths_table,
ll_code,
);
let ll_extra = seq.literal_length
- *LITERAL_LENGTH_BASELINES.get_unchecked(ll_code as usize);
let of_extra = seq.offset_value - (1u32 << of_code);
let ml_extra =
seq.match_length - *MATCH_LENGTH_BASELINES.get_unchecked(ml_code as usize);
stream.add_bits_fast(ll_extra.into(), ll_bits(ll_code));
if stream.bit_pos + ml_nbits + of_nbits >= STREAM_ACCUMULATOR_MIN {
stream.flush_bits_unchecked();
}
stream.add_bits_fast(ml_extra.into(), ml_nbits);
stream.add_bits_fast(of_extra.into(), of_nbits);
stream.flush_bits_unchecked();
}
}
} else {
for i in (0..n - 1).rev() {
let seq = &sequences[i];
let ll_code = ll_codes[i];
let of_code = of_codes[i];
let ml_code = ml_codes[i];
ensure_bits_capacity(&mut stream, fse::ctable_log(offsets_table))?;
fse::encode_symbol(&mut stream, &mut state_offsets, offsets_table, of_code)?;
ensure_bits_capacity(&mut stream, fse::ctable_log(match_lengths_table))?;
fse::encode_symbol(
&mut stream,
&mut state_match_lengths,
match_lengths_table,
ml_code,
)?;
ensure_bits_capacity(&mut stream, fse::ctable_log(literal_lengths_table))?;
fse::encode_symbol(
&mut stream,
&mut state_literal_lengths,
literal_lengths_table,
ll_code,
)?;
let ll_extra = seq.literal_length - LITERAL_LENGTH_BASELINES[ll_code as usize];
let of_extra = seq.offset_value - (1u32 << of_code);
let ml_extra = seq.match_length - MATCH_LENGTH_BASELINES[ml_code as usize];
add_bits_checked(&mut stream, ll_extra.into(), ll_bits(ll_code))?;
add_bits_checked(&mut stream, ml_extra.into(), ml_bits(ml_code))?;
add_offset_bits_checked(
&mut stream,
of_extra.into(),
u32::from(of_code),
long_offsets,
)?;
}
}
ensure_bits_capacity(&mut stream, fse::ctable_log(match_lengths_table))?;
fse::flush_cstate(&mut stream, &state_match_lengths, match_lengths_table)?;
ensure_bits_capacity(&mut stream, fse::ctable_log(offsets_table))?;
fse::flush_cstate(&mut stream, &state_offsets, offsets_table)?;
ensure_bits_capacity(&mut stream, fse::ctable_log(literal_lengths_table))?;
fse::flush_cstate(&mut stream, &state_literal_lengths, literal_lengths_table)?;
stream.close()
};
if written == 0 {
return Err(Error::DstSizeTooSmall);
}
dst.truncate(written);
Ok(())
}
fn encoded_sequence_count_size(number_of_sequences: usize) -> usize {
if number_of_sequences < 128 {
1
} else if number_of_sequences < 0x7F00 {
2
} else {
3
}
}
fn predefined_sequence_ctables() -> &'static PredefinedSequenceCTables {
PREDEFINED_SEQUENCE_CTABLES.get_or_init(|| {
let mut literal_lengths = fse::CTable::default();
fse::build_ctable(
&mut literal_lengths,
&LITERAL_LENGTH_DEFAULT_DISTRIBUTION,
(LITERAL_LENGTH_DEFAULT_DISTRIBUTION.len() - 1) as u32,
LL_DEFAULT_LOG,
)
.expect("literal-length predefined FSE table is valid");
let mut offsets = fse::CTable::default();
fse::build_ctable(
&mut offsets,
&OFFSET_DEFAULT_DISTRIBUTION,
(OFFSET_DEFAULT_DISTRIBUTION.len() - 1) as u32,
OF_DEFAULT_LOG,
)
.expect("offset predefined FSE table is valid");
let mut match_lengths = fse::CTable::default();
fse::build_ctable(
&mut match_lengths,
&MATCH_LENGTH_DEFAULT_DISTRIBUTION,
(MATCH_LENGTH_DEFAULT_DISTRIBUTION.len() - 1) as u32,
ML_DEFAULT_LOG,
)
.expect("match-length predefined FSE table is valid");
PredefinedSequenceCTables {
literal_lengths: SequenceEncodingTable::new(literal_lengths, all_symbols_supported()),
offsets: SequenceEncodingTable::new(offsets, all_symbols_supported()),
match_lengths: SequenceEncodingTable::new(match_lengths, all_symbols_supported()),
}
})
}
pub(crate) fn ll_bits(code: u8) -> u32 {
u32::from(LITERAL_LENGTH_EXTRA_BITS[code as usize])
}
pub(crate) fn ml_bits(code: u8) -> u32 {
u32::from(MATCH_LENGTH_EXTRA_BITS[code as usize])
}
fn ensure_bits_capacity(bit_c: &mut BitCStream<'_>, nb_bits: u32) -> Result<()> {
if nb_bits >= CONTAINER_BITS {
return Err(Error::InvalidParameter(
"bitstream write exceeds the accumulator width",
));
}
if bit_c.bit_pos + nb_bits >= STREAM_ACCUMULATOR_MIN {
bit_c.flush_bits();
}
Ok(())
}
fn add_bits_checked(bit_c: &mut BitCStream<'_>, value: u64, nb_bits: u32) -> Result<()> {
if nb_bits == 0 {
return Ok(());
}
ensure_bits_capacity(bit_c, nb_bits)?;
bit_c.add_bits(value, nb_bits);
Ok(())
}
fn add_offset_bits_checked(
bit_c: &mut BitCStream<'_>,
value: u64,
nb_bits: u32,
long_offsets: bool,
) -> Result<()> {
if !long_offsets || nb_bits < STREAM_ACCUMULATOR_MIN {
return add_bits_checked(bit_c, value, nb_bits);
}
let extra_bits = nb_bits - (STREAM_ACCUMULATOR_MIN - 1);
if extra_bits != 0 {
add_bits_checked(bit_c, value, extra_bits)?;
bit_c.flush_bits();
}
add_bits_checked(bit_c, value >> extra_bits, nb_bits - extra_bits)
}
#[cold]
#[inline(never)]
fn corruption_error(msg: &'static str) -> Error {
Error::Corruption(msg)
}
#[cold]
#[inline(never)]
fn output_size_overflow_error() -> Error {
Error::OutputSizeOverflow
}
#[cold]
#[inline(never)]
fn output_size_too_large_error(output_size: u64, max_output_size: usize) -> Error {
Error::OutputSizeTooLarge {
output_size,
max_output_size,
}
}
#[cfg(test)]
mod tests {
use crate::{
block::{BlockHeader, BlockType},
decode_all,
entropy::bitstream::BitCStream,
frame::write_single_segment_header,
window::plan_sequences,
};
use super::*;
#[test]
fn parses_zero_sequence_sections_without_touching_table_state() {
let mut tables = SequenceTablesState::default();
let parsed = parse_sequence_section(&[0], &mut tables, TableTarget::Both).unwrap();
assert_eq!(parsed.number_of_sequences, 0);
assert_eq!(parsed.header_size, 1);
assert!(parsed.bitstream.is_empty());
assert!(parsed.modes.is_none());
}
#[test]
fn rejects_reserved_mode_bits() {
let mut tables = SequenceTablesState::default();
let err =
parse_sequence_section(&[1, 0x01, 1], &mut tables, TableTarget::Both).unwrap_err();
assert_eq!(
err,
Error::Corruption("sequence compression modes reserved bits are set")
);
}
#[test]
fn rejects_repeat_mode_without_previous_tables() {
let mut tables = SequenceTablesState::default();
let err = parse_sequence_section(&[1, 0b1111_1100, 1], &mut tables, TableTarget::Both)
.unwrap_err();
assert_eq!(
err,
Error::Corruption("sequence repeat mode requires a previous FSE table")
);
}
#[test]
fn parses_predefined_sequence_tables_and_bitstream() {
let mut tables = SequenceTablesState::default();
let parsed = parse_sequence_section(
&[1, 0b0000_0000, 0, 0, 0, 0, 1],
&mut tables,
TableTarget::Both,
)
.unwrap();
assert_eq!(parsed.number_of_sequences, 1);
assert_eq!(parsed.header_size, 2);
assert_eq!(parsed.bitstream, &[0, 0, 0, 0, 1]);
assert_eq!(
parsed.modes,
Some(SequenceCompressionModes {
literal_lengths: CompressionMode::Predefined,
offsets: CompressionMode::Predefined,
match_lengths: CompressionMode::Predefined,
})
);
}
#[test]
fn repeat_mode_reuses_the_previous_tables() {
let mut tables = SequenceTablesState::default();
parse_sequence_section(
&[1, 0b0000_0000, 0, 0, 0, 0, 1],
&mut tables,
TableTarget::Both,
)
.unwrap();
let parsed = parse_sequence_section(
&[1, 0b1111_1100, 0, 0, 0, 0, 1],
&mut tables,
TableTarget::Both,
)
.unwrap();
assert_eq!(parsed.number_of_sequences, 1);
assert_eq!(parsed.header_size, 2);
}
#[test]
fn parses_rle_modes() {
let mut tables = SequenceTablesState::default();
let parsed = parse_sequence_section(
&[1, 0b0101_0100, 7, 0, 4, 1],
&mut tables,
TableTarget::Both,
)
.unwrap();
assert_eq!(parsed.number_of_sequences, 1);
assert_eq!(parsed.header_size, 5);
assert_eq!(parsed.bitstream, &[1]);
}
#[test]
fn decodes_single_rle_sequence_command() {
let mut tables = SequenceTablesState::default();
let parsed = parse_sequence_section(
&[1, 0b0101_0100, 7, 0, 4, 1],
&mut tables,
TableTarget::Both,
)
.unwrap();
let sequences = decode_sequence_commands(&parsed, &tables).unwrap();
assert_eq!(
sequences,
vec![SequenceCommand {
literal_length: 7,
offset_value: 1,
match_length: 7,
}]
);
}
#[test]
fn decodes_two_rle_sequences() {
let mut tables = SequenceTablesState::default();
let parsed = parse_sequence_section(
&[2, 0b0101_0100, 7, 0, 4, 1],
&mut tables,
TableTarget::Both,
)
.unwrap();
let sequences = decode_sequence_commands(&parsed, &tables).unwrap();
assert_eq!(sequences.len(), 2);
assert_eq!(sequences[0].literal_length, 7);
assert_eq!(sequences[1].match_length, 7);
}
#[test]
fn decodes_predefined_initial_states() {
let mut tables = SequenceTablesState::default();
let bitstream = encode_reverse_bits(&[(0, 6), (0, 5), (0, 6)]);
let mut section = vec![1, 0b0000_0000];
section.extend_from_slice(&bitstream);
let parsed = parse_sequence_section(§ion, &mut tables, TableTarget::Both).unwrap();
let sequences = decode_sequence_commands(&parsed, &tables).unwrap();
assert_eq!(sequences.len(), 1);
}
#[test]
fn rejects_leftover_bits_after_sequence_decode() {
let mut tables = SequenceTablesState::default();
let parsed = parse_sequence_section(
&[1, 0b0101_0100, 7, 0, 4, 0b0000_0011],
&mut tables,
TableTarget::Both,
)
.unwrap();
let err = decode_sequence_commands(&parsed, &tables).unwrap_err();
assert_eq!(
err,
Error::Corruption("sequence bitstream was not fully consumed")
);
}
#[test]
fn repeat_offsets_follow_the_spec_update_rules() {
let mut repeat_offsets = RepeatOffsets::default();
let cases = [
(
SequenceCommand {
literal_length: 11,
offset_value: 1114,
match_length: 3,
},
1111,
[1111, 1, 4],
),
(
SequenceCommand {
literal_length: 22,
offset_value: 1,
match_length: 3,
},
1111,
[1111, 1, 4],
),
(
SequenceCommand {
literal_length: 22,
offset_value: 2225,
match_length: 3,
},
2222,
[2222, 1111, 1],
),
(
SequenceCommand {
literal_length: 111,
offset_value: 1114,
match_length: 3,
},
1111,
[1111, 2222, 1111],
),
(
SequenceCommand {
literal_length: 33,
offset_value: 3336,
match_length: 3,
},
3333,
[3333, 1111, 2222],
),
(
SequenceCommand {
literal_length: 22,
offset_value: 2,
match_length: 3,
},
1111,
[1111, 3333, 2222],
),
(
SequenceCommand {
literal_length: 33,
offset_value: 3,
match_length: 3,
},
2222,
[2222, 1111, 3333],
),
(
SequenceCommand {
literal_length: 0,
offset_value: 3,
match_length: 3,
},
2221,
[2221, 2222, 1111],
),
(
SequenceCommand {
literal_length: 0,
offset_value: 1,
match_length: 3,
},
2222,
[2222, 2221, 1111],
),
];
for (sequence, expected_offset, expected_state) in cases {
let actual_offset = repeat_offsets.resolve(&sequence).unwrap();
assert_eq!(actual_offset, expected_offset);
assert_eq!(repeat_offsets.values(), expected_state);
}
}
#[test]
fn encodes_offset_values_following_the_spec() {
let mut repeat_offsets = RepeatOffsets::from_values([1111, 2222, 3333]);
let cases = [
(1111, 12, 1, [1111, 2222, 3333]),
(2222, 0, 1, [2222, 1111, 3333]),
(2221, 0, 3, [2221, 2222, 1111]),
(3333, 5, 3336, [3333, 2221, 2222]),
(4444, 7, 4447, [4444, 3333, 2221]),
];
for (raw_offset, literal_length, expected, expected_state) in cases {
let actual = repeat_offsets
.encode_offset_value(raw_offset, literal_length)
.unwrap();
assert_eq!(actual, expected);
assert_eq!(repeat_offsets.values(), expected_state);
}
}
#[test]
fn rejects_repeat_offset_one_minus_one_when_it_reaches_zero() {
let mut repeat_offsets = RepeatOffsets::default();
let err = repeat_offsets
.resolve(&SequenceCommand {
literal_length: 0,
offset_value: 3,
match_length: 3,
})
.unwrap_err();
assert_eq!(err, Error::Corruption("repeat offset 1 minus 1 is zero"));
}
#[test]
fn resolves_zero_literal_rep2_like_generic_offset_value_one() {
let mut generic = RepeatOffsets::from_values([1111, 2222, 3333]);
let raw_offset = generic
.resolve(&SequenceCommand {
literal_length: 0,
offset_value: 1,
match_length: 3,
})
.unwrap();
assert_eq!(raw_offset, 2222);
assert_eq!(generic.values(), [2222, 1111, 3333]);
let mut specialized = RepeatOffsets::from_values([1111, 2222, 3333]);
let specialized_raw = specialized.resolve_zero_literal_rep2().unwrap();
assert_eq!(specialized_raw, raw_offset);
assert_eq!(specialized.values(), generic.values());
}
#[test]
fn executes_sequences_with_overlap_and_last_literals() {
let mut repeat_offsets = RepeatOffsets::default();
let mut out = Vec::new();
let sequences = [
SequenceCommand {
literal_length: 1,
offset_value: 4,
match_length: 5,
},
SequenceCommand {
literal_length: 2,
offset_value: 1,
match_length: 4,
},
];
execute_sequences(
&mut DecodeOut::growable(&mut out),
0,
128 * 1024,
128 * 1024,
None,
b"abc",
&sequences,
&mut repeat_offsets,
None,
)
.unwrap();
assert_eq!(out, b"aaaaaabccccc");
assert_eq!(repeat_offsets.values(), [1, 1, 4]);
}
#[test]
fn rejects_sequence_offsets_outside_the_available_window() {
let mut repeat_offsets = RepeatOffsets::default();
let mut out = b"abcdef".to_vec();
let err = execute_sequences(
&mut DecodeOut::growable(&mut out),
0,
4,
128 * 1024,
None,
b"",
&[SequenceCommand {
literal_length: 0,
offset_value: 10,
match_length: 3,
}],
&mut repeat_offsets,
None,
)
.unwrap_err();
assert_eq!(
err,
Error::Corruption("sequence offset exceeds the available history window")
);
}
#[test]
fn executes_dictionary_matches_across_the_prefix_boundary() {
let mut repeat_offsets = RepeatOffsets::default();
let mut out = b"abc".to_vec();
execute_sequences(
&mut DecodeOut::growable(&mut out),
0,
128 * 1024,
128 * 1024,
Some(b"XY"),
b"",
&[SequenceCommand {
literal_length: 0,
offset_value: 8,
match_length: 9,
}],
&mut repeat_offsets,
None,
)
.unwrap();
assert_eq!(out, b"abcXYabcXYab");
}
#[test]
fn executes_dictionary_only_overlap_matches() {
let mut repeat_offsets = RepeatOffsets::default();
let mut out = Vec::new();
execute_sequences(
&mut DecodeOut::growable(&mut out),
0,
128 * 1024,
128 * 1024,
Some(b"wxyz"),
b"",
&[SequenceCommand {
literal_length: 0,
offset_value: 5,
match_length: 6,
}],
&mut repeat_offsets,
None,
)
.unwrap();
assert_eq!(out, b"yzyzyz");
}
#[test]
fn encodes_predefined_sequence_sections_roundtrip() {
let sequences = vec![
SequenceCommand {
literal_length: 3,
offset_value: 7,
match_length: 11,
},
SequenceCommand {
literal_length: 0,
offset_value: 1,
match_length: 7,
},
SequenceCommand {
literal_length: 5,
offset_value: 10,
match_length: 4,
},
];
let encoded = encode_sequence_section(&sequences).unwrap();
let mut tables = SequenceTablesState::default();
let parsed = parse_sequence_section(&encoded, &mut tables, TableTarget::Both).unwrap();
let decoded = decode_sequence_commands(&parsed, &tables).unwrap();
assert_eq!(decoded, sequences);
}
#[test]
fn encodes_planned_sequence_sections_roundtrip() {
let input = build_repeated_chunk_pattern(24_000);
let plan = plan_sequences(&input, RepeatOffsets::default()).unwrap();
let encoded = encode_sequence_section(&plan.sequences).unwrap();
let mut tables = SequenceTablesState::default();
let parsed = parse_sequence_section(&encoded, &mut tables, TableTarget::Both).unwrap();
let decoded = decode_sequence_commands(&parsed, &tables).unwrap();
assert_eq!(decoded, plan.sequences);
}
#[test]
fn encodes_pseudorandom_planned_sequence_sections_roundtrip() {
let input = build_pattern(32_000);
let plan = plan_sequences(&input, RepeatOffsets::default()).unwrap();
let encoded = encode_sequence_section(&plan.sequences).unwrap();
let mut tables = SequenceTablesState::default();
let parsed = parse_sequence_section(&encoded, &mut tables, TableTarget::Both).unwrap();
let decoded = decode_sequence_commands(&parsed, &tables).unwrap();
assert_eq!(decoded, plan.sequences);
}
#[test]
fn encodes_large_sequence_counts_roundtrip() {
let mut encoded = Vec::new();
encode_sequence_count(500, &mut OutBuf::growable(&mut encoded)).unwrap();
assert_eq!(parse_sequence_count(&encoded).unwrap(), (500, 2));
}
#[test]
fn encodes_custom_fse_tables_for_skewed_sequences() {
let sequences = build_skewed_sequence_commands(2048);
let (encoded, next_state) =
encode_sequence_section_with_state(&sequences, &SequenceEncodingState::default())
.unwrap();
let mut tables = SequenceTablesState::default();
let parsed = parse_sequence_section(&encoded, &mut tables, TableTarget::Both).unwrap();
let decoded = decode_sequence_commands(&parsed, &tables).unwrap();
assert_eq!(decoded, sequences);
let modes = parsed.modes.unwrap();
assert!(
[modes.literal_lengths, modes.offsets, modes.match_lengths]
.into_iter()
.any(|mode| mode == CompressionMode::FseCompressed),
"expected at least one custom FSE table mode, got {modes:?}"
);
assert!(next_state.table(SequencePart::LiteralLength).is_some());
assert!(next_state.table(SequencePart::Offset).is_some());
assert!(next_state.table(SequencePart::MatchLength).is_some());
}
#[test]
fn fast_strategy_prefers_predefined_tables_for_small_sequence_sections() {
let sequences = build_skewed_sequence_commands(32);
let (encoded, _) = encode_sequence_section_with_strategy(
&sequences,
&SequenceEncodingState::default(),
ParserStrategy::Fast,
)
.unwrap();
let mut tables = SequenceTablesState::default();
let parsed = parse_sequence_section(&encoded, &mut tables, TableTarget::Both).unwrap();
let decoded = decode_sequence_commands(&parsed, &tables).unwrap();
assert_eq!(decoded, sequences);
assert_eq!(
parsed.modes.unwrap(),
SequenceCompressionModes {
literal_lengths: CompressionMode::Predefined,
offsets: CompressionMode::Predefined,
match_lengths: CompressionMode::Predefined,
}
);
}
#[test]
fn fast_strategy_does_not_auto_repeat_tables_in_check_mode() {
let seed_sequences = build_skewed_sequence_commands(2048);
let (_, state_after_first) = encode_sequence_section_with_strategy(
&seed_sequences,
&SequenceEncodingState::default(),
ParserStrategy::Fast,
)
.unwrap();
assert!(
state_after_first
.table(SequencePart::LiteralLength)
.is_some()
|| state_after_first.table(SequencePart::Offset).is_some()
|| state_after_first.table(SequencePart::MatchLength).is_some()
);
let sequences = build_skewed_sequence_commands(256);
let (encoded, _) = encode_sequence_section_with_strategy(
&sequences,
&state_after_first,
ParserStrategy::Fast,
)
.unwrap();
let mut tables = SequenceTablesState::default();
let seed_encoded = encode_sequence_section_with_strategy(
&seed_sequences,
&SequenceEncodingState::default(),
ParserStrategy::Fast,
)
.unwrap()
.0;
parse_sequence_section(&seed_encoded, &mut tables, TableTarget::Both).unwrap();
let parsed = parse_sequence_section(&encoded, &mut tables, TableTarget::Both).unwrap();
let decoded = decode_sequence_commands(&parsed, &tables).unwrap();
assert_eq!(decoded, sequences);
let modes = parsed.modes.unwrap();
assert!(
[modes.literal_lengths, modes.offsets, modes.match_lengths]
.into_iter()
.all(|mode| mode != CompressionMode::Repeat),
"expected fast strategy to avoid repeat mode when prior tables are only in check mode, got {modes:?}"
);
}
#[test]
fn fast_strategy_reuses_valid_tables_for_small_repeated_sections() {
let seed_sequences = build_skewed_sequence_commands(2048);
let (seed_encoded, mut state_after_first) = encode_sequence_section_with_strategy(
&seed_sequences,
&SequenceEncodingState::default(),
ParserStrategy::Fast,
)
.unwrap();
for entry in [
state_after_first.literal_lengths.as_mut(),
state_after_first.offsets.as_mut(),
state_after_first.match_lengths.as_mut(),
]
.into_iter()
.flatten()
{
entry.repeat_mode = SequenceRepeatMode::Valid;
}
let sequences = build_skewed_sequence_commands(256);
let (encoded, _) = encode_sequence_section_with_strategy(
&sequences,
&state_after_first,
ParserStrategy::Fast,
)
.unwrap();
let mut tables = SequenceTablesState::default();
parse_sequence_section(&seed_encoded, &mut tables, TableTarget::Both).unwrap();
let parsed = parse_sequence_section(&encoded, &mut tables, TableTarget::Both).unwrap();
let decoded = decode_sequence_commands(&parsed, &tables).unwrap();
assert_eq!(decoded, sequences);
let modes = parsed.modes.unwrap();
assert!(
[modes.literal_lengths, modes.offsets, modes.match_lengths]
.into_iter()
.any(|mode| mode == CompressionMode::Repeat),
"expected fast strategy to reuse a valid previous table, got {modes:?}"
);
}
#[test]
fn repeat_cost_rejects_tables_with_zero_probability_symbols() {
let previous_codes = [0u8, 1, 0, 1, 0, 1, 0, 1];
let previous_stats = analyze_codes(SequencePart::LiteralLength, &previous_codes).unwrap();
let mut pool = SequenceTablePool::default();
let previous_choice = build_compressed_table_choice(
SequencePart::LiteralLength,
&previous_codes,
&previous_stats,
&mut pool,
)
.unwrap()
.unwrap();
let previous =
SequenceEncodingPartState::new(previous_choice.encoding, SequenceRepeatMode::Check);
let codes = [0u8, 1, 2, 0, 1, 2, 0, 1];
let choice = build_sequence_part_choice(
SequencePart::LiteralLength,
&codes,
Some(&previous),
ParserStrategy::Lazy,
&mut pool,
)
.unwrap();
assert_ne!(choice.mode, CompressionMode::Repeat);
}
#[test]
fn build_sequences_statistics_tracks_header_order_and_last_count_size() {
let sequences = build_skewed_sequence_commands(2048);
let mut scratch = SequenceEncodeScratch::default();
prepare_sequence_encode_scratch(&sequences, &mut scratch).unwrap();
let build = build_sequences_statistics(
scratch.encoded.len(),
&scratch.literal_codes,
&scratch.offset_codes,
&scratch.match_codes,
&SequenceEncodingState::default(),
ParserStrategy::Lazy,
&mut SequenceTablePool::default(),
)
.unwrap();
let expected_last_count_size = if build.match_choice.mode == CompressionMode::FseCompressed
{
build.match_choice.header.len()
} else if build.offset_choice.mode == CompressionMode::FseCompressed {
build.offset_choice.header.len()
} else if build.literal_choice.mode == CompressionMode::FseCompressed {
build.literal_choice.header.len()
} else {
0
};
assert_eq!(
build.stats.header_size,
encoded_sequence_count_size(scratch.encoded.len())
+ 1
+ build.literal_choice.header.len()
+ build.offset_choice.header.len()
+ build.match_choice.header.len()
);
assert_eq!(build.stats.last_count_size, expected_last_count_size);
assert_eq!(
build.stats.modes,
Some(SequenceCompressionModes {
literal_lengths: build.literal_choice.mode,
offsets: build.offset_choice.mode,
match_lengths: build.match_choice.mode,
})
);
}
#[test]
fn build_sequences_statistics_reuses_seeded_valid_tables_on_the_first_block() {
let seed_sequences = build_skewed_sequence_commands(2048);
let mut seed_scratch = SequenceEncodeScratch::default();
prepare_sequence_encode_scratch(&seed_sequences, &mut seed_scratch).unwrap();
let mut seeded_state = build_sequences_statistics(
seed_scratch.encoded.len(),
&seed_scratch.literal_codes,
&seed_scratch.offset_codes,
&seed_scratch.match_codes,
&SequenceEncodingState::default(),
ParserStrategy::Fast,
&mut SequenceTablePool::default(),
)
.unwrap()
.into_next_state()
.0;
for entry in [
seeded_state.literal_lengths.as_mut(),
seeded_state.offsets.as_mut(),
seeded_state.match_lengths.as_mut(),
]
.into_iter()
.flatten()
{
entry.repeat_mode = SequenceRepeatMode::Valid;
}
let sequences = build_skewed_sequence_commands(256);
let mut scratch = SequenceEncodeScratch::default();
prepare_sequence_encode_scratch(&sequences, &mut scratch).unwrap();
let build = build_sequences_statistics(
scratch.encoded.len(),
&scratch.literal_codes,
&scratch.offset_codes,
&scratch.match_codes,
&seeded_state,
ParserStrategy::Fast,
&mut SequenceTablePool::default(),
)
.unwrap();
let modes = build.stats.modes.unwrap();
assert!(
[modes.literal_lengths, modes.offsets, modes.match_lengths]
.into_iter()
.any(|mode| mode == CompressionMode::Repeat),
"expected seeded valid tables to trigger repeat-mode reuse, got {modes:?}"
);
}
#[test]
fn reusable_sequence_workspace_matches_one_shot_encoding() {
let first_sequences = build_skewed_sequence_commands(2048);
let second_sequences = build_skewed_sequence_commands(257);
let mut bitstream_scratch = Vec::new();
let mut encode_scratch = SequenceEncodeScratch::default();
let (expected_first, expected_first_state) = encode_sequence_section_with_strategy(
&first_sequences,
&SequenceEncodingState::default(),
ParserStrategy::DoubleFast,
)
.unwrap();
let (actual_first, actual_first_state) = encode_sequence_section_with_strategy_and_scratch(
&first_sequences,
&SequenceEncodingState::default(),
ParserStrategy::DoubleFast,
&mut bitstream_scratch,
&mut encode_scratch,
)
.unwrap();
assert_eq!(actual_first, expected_first);
assert_eq!(
actual_first_state
.table(SequencePart::LiteralLength)
.is_some(),
expected_first_state
.table(SequencePart::LiteralLength)
.is_some()
);
assert_eq!(
actual_first_state.table(SequencePart::Offset).is_some(),
expected_first_state.table(SequencePart::Offset).is_some()
);
assert_eq!(
actual_first_state
.table(SequencePart::MatchLength)
.is_some(),
expected_first_state
.table(SequencePart::MatchLength)
.is_some()
);
let (expected_second, expected_second_state) = encode_sequence_section_with_strategy(
&second_sequences,
&expected_first_state,
ParserStrategy::DoubleFast,
)
.unwrap();
let (actual_second, actual_second_state) =
encode_sequence_section_with_strategy_and_scratch(
&second_sequences,
&actual_first_state,
ParserStrategy::DoubleFast,
&mut bitstream_scratch,
&mut encode_scratch,
)
.unwrap();
assert_eq!(actual_second, expected_second);
assert_eq!(
actual_second_state
.table(SequencePart::LiteralLength)
.is_some(),
expected_second_state
.table(SequencePart::LiteralLength)
.is_some()
);
assert_eq!(
actual_second_state.table(SequencePart::Offset).is_some(),
expected_second_state.table(SequencePart::Offset).is_some()
);
assert_eq!(
actual_second_state
.table(SequencePart::MatchLength)
.is_some(),
expected_second_state
.table(SequencePart::MatchLength)
.is_some()
);
}
#[test]
fn repeated_dynamic_distributions_keep_using_dynamic_sequence_tables() {
let sequences = build_skewed_sequence_commands(2048);
let (_, state_after_first) =
encode_sequence_section_with_state(&sequences, &SequenceEncodingState::default())
.unwrap();
let (encoded, _) =
encode_sequence_section_with_state(&sequences, &state_after_first).unwrap();
let mut tables = SequenceTablesState::default();
let first_encoded =
encode_sequence_section_with_state(&sequences, &SequenceEncodingState::default())
.unwrap()
.0;
parse_sequence_section(&first_encoded, &mut tables, TableTarget::Both).unwrap();
let parsed = parse_sequence_section(&encoded, &mut tables, TableTarget::Both).unwrap();
let decoded = decode_sequence_commands(&parsed, &tables).unwrap();
assert_eq!(decoded, sequences);
let modes = parsed.modes.unwrap();
assert!(
[modes.literal_lengths, modes.offsets, modes.match_lengths]
.into_iter()
.any(|mode| matches!(
mode,
CompressionMode::Repeat | CompressionMode::FseCompressed
)),
"expected the repeated distribution to keep at least one dynamic FSE mode, got {modes:?}"
);
}
#[test]
fn decodes_frames_with_repeated_sequence_tables_across_blocks() {
let (literals, sequences, block_output) = build_repeat_friendly_block(256);
let (first_section, state_after_first) =
encode_sequence_section_with_state(&sequences, &SequenceEncodingState::default())
.unwrap();
let (second_section, _) =
encode_sequence_section_with_state(&sequences, &state_after_first).unwrap();
let mut tables = SequenceTablesState::default();
let first_modes = parse_sequence_section(&first_section, &mut tables, TableTarget::Both)
.unwrap()
.modes
.unwrap();
let second_modes = parse_sequence_section(&second_section, &mut tables, TableTarget::Both)
.unwrap()
.modes
.unwrap();
assert!(
[
first_modes.literal_lengths,
first_modes.offsets,
first_modes.match_lengths
]
.into_iter()
.any(|mode| { matches!(mode, CompressionMode::Rle | CompressionMode::FseCompressed) }),
"expected the first block to seed a reusable table, got {first_modes:?}"
);
assert!(
[
second_modes.literal_lengths,
second_modes.offsets,
second_modes.match_lengths
]
.into_iter()
.any(|mode| mode == CompressionMode::Repeat),
"expected the second block to reuse a previous table, got {second_modes:?}"
);
let literals_section = raw_literals_section(&literals);
let mut first_payload = literals_section.clone();
first_payload.extend_from_slice(&first_section);
let mut second_payload = literals_section;
second_payload.extend_from_slice(&second_section);
let mut frame = Vec::new();
write_single_segment_header(
&mut OutBuf::growable(&mut frame),
(block_output.len() * 2) as u64,
false,
);
BlockHeader {
last_block: false,
block_type: BlockType::Compressed,
block_size: first_payload.len() as u32,
}
.write_to(&mut OutBuf::growable(&mut frame));
frame.extend_from_slice(&first_payload);
BlockHeader {
last_block: true,
block_type: BlockType::Compressed,
block_size: second_payload.len() as u32,
}
.write_to(&mut OutBuf::growable(&mut frame));
frame.extend_from_slice(&second_payload);
let decoded = decode_all(&frame).unwrap();
let mut expected = block_output.clone();
expected.extend_from_slice(&block_output);
assert_eq!(decoded, expected);
}
fn distant_repeat_body() -> Vec<u8> {
const BLOCK: usize = 4096;
let block: Vec<u8> = (0..BLOCK)
.map(|i| ((i as u32).wrapping_mul(2_654_435_761) >> 24) as u8)
.collect();
let mut body = Vec::with_capacity(BLOCK * 3 + 500_000);
body.extend_from_slice(&block);
body.extend(core::iter::repeat_n(0u8, 300_000));
body.extend_from_slice(&block);
body.extend(core::iter::repeat_n(7u8, 200_000));
body.extend_from_slice(&block);
body
}
#[test]
fn a_frame_with_distant_repeats_round_trips() {
let body = distant_repeat_body();
let frame = crate::encode_all(&body).unwrap();
assert!(
frame.len() < 8 * 1024,
"expected the distant copies to be matched, got a {}-byte frame",
frame.len()
);
assert_eq!(decode_all(&frame).unwrap(), body);
}
fn encode_reverse_bits(values: &[(u64, u32)]) -> Vec<u8> {
let mut bytes = vec![0u8; 64];
let written = {
let mut stream = BitCStream::new(&mut bytes).unwrap();
for &(value, nb_bits) in values {
if stream.bit_pos + nb_bits >= STREAM_ACCUMULATOR_MIN {
stream.flush_bits();
}
stream.add_bits(value, nb_bits);
}
stream.close()
};
bytes.truncate(written);
bytes
}
fn build_repeated_chunk_pattern(size: usize) -> Vec<u8> {
const CHUNK: &[u8] = b"zstd-rs-window-repcode-pattern-0123456789ABCDEF";
let mut out = Vec::with_capacity(size);
while out.len() < size {
let remaining = size - out.len();
let take = remaining.min(CHUNK.len());
out.extend_from_slice(&CHUNK[..take]);
}
out
}
fn build_pattern(size: usize) -> Vec<u8> {
(0..size)
.map(|index| ((index * 31) as u8).wrapping_add((index >> 7) as u8))
.collect()
}
fn build_skewed_sequence_commands(count: usize) -> Vec<SequenceCommand> {
(0..count)
.map(|index| SequenceCommand {
literal_length: if index % 31 == 0 {
96
} else if index % 7 == 0 {
12
} else {
0
},
offset_value: if index % 53 == 0 {
1024
} else if index % 9 == 0 {
17
} else {
1
},
match_length: if index % 41 == 0 {
35
} else if index % 5 == 0 {
7
} else {
3
},
})
.collect()
}
fn build_repeat_friendly_block(count: usize) -> (Vec<u8>, Vec<SequenceCommand>, Vec<u8>) {
let mut literals = Vec::new();
let mut sequences = Vec::new();
let mut repeat_offsets = RepeatOffsets::default();
let mut prng = 0x1234_5678u32;
for index in 0..count {
let literal_length = if index == 0 {
1024
} else if index % 31 == 0 {
96
} else if index % 7 == 0 {
12
} else {
1
};
let match_length = if index % 41 == 0 {
35
} else if index % 5 == 0 {
7
} else {
3
};
let raw_offset = if index == 0 || index % 53 == 0 {
1024
} else if index % 9 == 0 {
17
} else {
1024
};
for _ in 0..literal_length {
prng ^= prng << 13;
prng ^= prng >> 17;
prng ^= prng << 5;
literals.push(b'A' + (prng & 0x0f) as u8);
}
let offset_value = repeat_offsets
.encode_offset_value(raw_offset, literal_length as u32)
.unwrap();
sequences.push(SequenceCommand {
literal_length: literal_length as u32,
offset_value,
match_length: match_length as u32,
});
}
let mut output = Vec::new();
let mut decode_repeat_offsets = RepeatOffsets::default();
execute_sequences(
&mut DecodeOut::growable(&mut output),
0,
128 * 1024,
128 * 1024,
None,
&literals,
&sequences,
&mut decode_repeat_offsets,
None,
)
.unwrap();
(literals, sequences, output)
}
fn raw_literals_section(literals: &[u8]) -> Vec<u8> {
let mut payload = Vec::with_capacity(3 + literals.len());
if literals.len() <= 31 {
payload.push((literals.len() as u8) << 3);
} else if literals.len() <= 0x0fff {
let value = (1u32 << 2) | ((literals.len() as u32) << 4);
payload.extend_from_slice(&[(value & 0xff) as u8, ((value >> 8) & 0xff) as u8]);
} else {
let value = (3u32 << 2) | ((literals.len() as u32) << 4);
payload.extend_from_slice(&[
(value & 0xff) as u8,
((value >> 8) & 0xff) as u8,
((value >> 16) & 0xff) as u8,
]);
}
payload.extend_from_slice(literals);
payload
}
}