use std::{
collections::HashMap,
sync::{Arc, Mutex},
};
use crate::{
encode::{EncoderOptions, compression_parameters_for_options},
entropy::{
fse,
huff0::{CTableX1, HuffmanDTable, read_ctable_x1_with_repeat_validity, read_dtable_x2},
mem::highbit32,
},
error::{Error, Result},
frame::read_u32_le,
literals::LiteralsState,
sequence::{
RepeatOffsets, SequenceEncodingPartState, SequenceEncodingState, SequenceEncodingTable,
SequenceTablesState, repeat_mode_for_normalized_counts,
},
window::{
DictionaryPriceSeed, MatchFinderParameters, PreparedDictionaryMatchState,
PreparedDictionaryMatchStateKey, build_prepared_dictionary_match_state,
},
};
pub(crate) const ZSTD_DICTIONARY_MAGIC: u32 = 0xEC30_A437;
const OFFSET_MAX_SYMBOL_VALUE: u32 = 31;
const OFFSET_MAX_TABLE_LOG: usize = 8;
const MATCH_LENGTH_MAX_SYMBOL_VALUE: u32 = 52;
const MATCH_LENGTH_MAX_TABLE_LOG: usize = 9;
const LITERAL_LENGTH_MAX_SYMBOL_VALUE: u32 = 35;
const LITERAL_LENGTH_MAX_TABLE_LOG: usize = 9;
#[derive(Clone)]
pub struct EncoderDictionary<'a> {
dictionary: Dictionary<'a>,
prepared_match_states:
Arc<Mutex<HashMap<PreparedDictionaryMatchStateKey, Arc<PreparedDictionaryMatchState>>>>,
}
#[derive(Clone)]
pub struct DecoderDictionary<'a> {
dictionary: Dictionary<'a>,
}
impl<'a> EncoderDictionary<'a> {
pub fn new(src: &'a [u8]) -> Result<Self> {
Ok(Self {
dictionary: Dictionary::parse(src, TableDirection::Encoding)?,
prepared_match_states: Arc::new(Mutex::new(HashMap::new())),
})
}
pub fn from_shared(bytes: impl Into<Arc<[u8]>>) -> Result<EncoderDictionary<'static>> {
Ok(EncoderDictionary {
dictionary: Dictionary::parse_shared(bytes.into(), TableDirection::Encoding)?,
prepared_match_states: Arc::new(Mutex::new(HashMap::new())),
})
}
pub fn prepare(&self, options: EncoderOptions) {
let params = compression_parameters_for_options(options, None, Some(&self.dictionary));
self.prepared_match_state(params.match_finder);
}
pub(crate) fn raw_content(src: &'a [u8]) -> Self {
Self {
dictionary: Dictionary::raw(src),
prepared_match_states: Arc::new(Mutex::new(HashMap::new())),
}
}
pub fn id(&self) -> u32 {
self.dictionary.id()
}
pub fn is_raw_content(&self) -> bool {
self.dictionary.is_raw_content()
}
pub(crate) fn as_inner(&self) -> &Dictionary<'a> {
&self.dictionary
}
pub(crate) fn prepared_match_state(
&self,
params: MatchFinderParameters,
) -> Option<Arc<PreparedDictionaryMatchState>> {
if self.dictionary.is_raw_content() || self.dictionary.content().is_empty() {
return None;
}
let key = PreparedDictionaryMatchStateKey::new(params);
if let Some(state) = self
.prepared_match_states
.lock()
.expect("prepared dictionary cache lock poisoned")
.get(&key)
.cloned()
{
return Some(state);
}
let state = Arc::new(build_prepared_dictionary_match_state(
self.dictionary.matching_content(),
params,
)?);
self.prepared_match_states
.lock()
.expect("prepared dictionary cache lock poisoned")
.insert(key, state.clone());
Some(state)
}
#[cfg(test)]
fn cached_geometries(&self) -> Vec<PreparedDictionaryMatchStateKey> {
self.prepared_match_states
.lock()
.expect("prepared dictionary cache lock poisoned")
.keys()
.copied()
.collect()
}
}
impl<'a> DecoderDictionary<'a> {
pub fn new(src: &'a [u8]) -> Result<Self> {
Ok(Self {
dictionary: Dictionary::parse(src, TableDirection::Decoding)?,
})
}
pub fn from_shared(bytes: impl Into<Arc<[u8]>>) -> Result<DecoderDictionary<'static>> {
Ok(DecoderDictionary {
dictionary: Dictionary::parse_shared(bytes.into(), TableDirection::Decoding)?,
})
}
pub fn id(&self) -> u32 {
self.dictionary.id()
}
pub fn is_raw_content(&self) -> bool {
self.dictionary.is_raw_content()
}
pub(crate) fn as_inner(&self) -> &Dictionary<'a> {
&self.dictionary
}
}
impl<'a> TryFrom<&'a [u8]> for EncoderDictionary<'a> {
type Error = Error;
fn try_from(value: &'a [u8]) -> Result<Self> {
Self::new(value)
}
}
impl<'a> TryFrom<&'a [u8]> for DecoderDictionary<'a> {
type Error = Error;
fn try_from(value: &'a [u8]) -> Result<Self> {
Self::new(value)
}
}
#[derive(Clone)]
enum DictionaryBytes<'a> {
Borrowed(&'a [u8]),
Shared(Arc<[u8]>),
}
impl DictionaryBytes<'_> {
#[inline]
fn as_slice(&self) -> &[u8] {
match self {
Self::Borrowed(bytes) => bytes,
Self::Shared(bytes) => bytes,
}
}
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub(crate) enum TableDirection {
Encoding,
Decoding,
}
pub(crate) struct DecoderTables {
huffman_table: Option<HuffmanDTable>,
offset_table: fse::DTable,
match_length_table: fse::DTable,
literal_length_table: fse::DTable,
}
pub(crate) struct EncoderTables {
huffman_encoding_table: CTableX1,
huffman_repeat_valid: bool,
offset_encoding_state: SequenceEncodingPartState,
match_length_encoding_state: SequenceEncodingPartState,
literal_length_encoding_state: SequenceEncodingPartState,
}
const DECODER_TABLES_MISSING: &str =
"decode path read a dictionary parsed for encoding; it needs a DecoderDictionary";
const ENCODER_TABLES_MISSING: &str =
"encode path read a dictionary parsed for decoding; it needs an EncoderDictionary";
#[derive(Clone)]
pub(crate) struct Dictionary<'a> {
id: u32,
source_size: usize,
source: DictionaryBytes<'a>,
content_start: usize,
raw_content: bool,
decoder_tables: Option<Arc<DecoderTables>>,
encoder_tables: Option<Arc<EncoderTables>>,
repeat_offsets: RepeatOffsets,
}
impl<'a> Dictionary<'a> {
pub(crate) fn parse(src: &'a [u8], direction: TableDirection) -> Result<Self> {
if src.len() < 8 || read_u32_le(src) != ZSTD_DICTIONARY_MAGIC {
return Ok(Self::raw(src));
}
let mut cursor = 8usize;
let dictionary_id = read_u32_le(&src[4..8]);
let mut huffman_table = None;
let mut huffman_encoding = None;
let huffman_size = match direction {
TableDirection::Decoding => read_dtable_x2(
&src[cursor..],
HuffmanDTable::double_slot(&mut huffman_table),
)?,
TableDirection::Encoding => {
let mut table = CTableX1::default();
let (size, repeat_valid) =
read_ctable_x1_with_repeat_validity(&src[cursor..], &mut table)?;
huffman_encoding = Some((table, repeat_valid));
size
}
};
cursor += huffman_size;
let (offset_counts, offset_size) = read_sequence_counts(
&src[cursor..],
OFFSET_MAX_SYMBOL_VALUE,
OFFSET_MAX_TABLE_LOG,
)?;
cursor += offset_size;
let (match_length_counts, match_length_size) = read_sequence_counts(
&src[cursor..],
MATCH_LENGTH_MAX_SYMBOL_VALUE,
MATCH_LENGTH_MAX_TABLE_LOG,
)?;
cursor += match_length_size;
let (literal_length_counts, literal_length_size) = read_sequence_counts(
&src[cursor..],
LITERAL_LENGTH_MAX_SYMBOL_VALUE,
LITERAL_LENGTH_MAX_TABLE_LOG,
)?;
cursor += literal_length_size;
let reps_end = cursor.checked_add(12).ok_or(Error::OutputSizeOverflow)?;
if reps_end > src.len() {
return Err(Error::Corruption("dictionary is truncated"));
}
let content = &src[reps_end..];
let rep1 = read_u32_le(&src[cursor..cursor + 4]);
let rep2 = read_u32_le(&src[cursor + 4..cursor + 8]);
let rep3 = read_u32_le(&src[cursor + 8..reps_end]);
for rep in [rep1, rep2, rep3] {
if rep == 0 || rep as usize > content.len() {
return Err(Error::Corruption(
"dictionary repeat offset exceeds dictionary content",
));
}
}
let offset_required_max_symbol = dictionary_offset_required_max_symbol(content.len());
let (decoder_tables, encoder_tables) = match direction {
TableDirection::Decoding => (
Some(Arc::new(DecoderTables {
huffman_table,
offset_table: offset_counts.dtable()?,
match_length_table: match_length_counts.dtable()?,
literal_length_table: literal_length_counts.dtable()?,
})),
None,
),
TableDirection::Encoding => {
let (huffman_encoding_table, huffman_repeat_valid) = huffman_encoding
.expect("the encoding arm above sets this before the cursor advances");
(
None,
Some(Arc::new(EncoderTables {
huffman_encoding_table,
huffman_repeat_valid,
offset_encoding_state: offset_counts
.encoding_state(offset_required_max_symbol)?,
match_length_encoding_state: match_length_counts
.encoding_state(MATCH_LENGTH_MAX_SYMBOL_VALUE)?,
literal_length_encoding_state: literal_length_counts
.encoding_state(LITERAL_LENGTH_MAX_SYMBOL_VALUE)?,
})),
)
}
};
Ok(Self {
id: dictionary_id,
source_size: src.len(),
source: DictionaryBytes::Borrowed(src),
content_start: src.len() - content.len(),
raw_content: false,
decoder_tables,
encoder_tables,
repeat_offsets: RepeatOffsets::from_values([rep1, rep2, rep3]),
})
}
fn parse_shared(bytes: Arc<[u8]>, direction: TableDirection) -> Result<Dictionary<'static>> {
let Dictionary {
id,
source_size,
source: _,
content_start,
raw_content,
decoder_tables,
encoder_tables,
repeat_offsets,
} = Dictionary::parse(&bytes, direction)?;
Ok(Dictionary {
id,
source_size,
source: DictionaryBytes::Shared(bytes),
content_start,
raw_content,
decoder_tables,
encoder_tables,
repeat_offsets,
})
}
pub(crate) fn id(&self) -> u32 {
self.id
}
pub(crate) fn frame_dictionary_id(&self) -> Option<u32> {
(self.id != 0).then_some(self.id)
}
pub(crate) fn source_size(&self) -> usize {
self.source_size
}
pub(crate) fn is_raw_content(&self) -> bool {
self.raw_content
}
pub(crate) fn content(&self) -> &[u8] {
&self.source.as_slice()[self.content_start..]
}
pub(crate) fn matching_content(&self) -> &[u8] {
if self.is_raw_content() || self.content().is_empty() {
return self.content();
}
let content_start = self.content_start;
let match_start = content_start.saturating_sub(2);
&self.source.as_slice()[match_start..]
}
fn decoder_tables(&self) -> Option<&DecoderTables> {
if self.raw_content {
return None;
}
Some(
self.decoder_tables
.as_deref()
.expect(DECODER_TABLES_MISSING),
)
}
fn encoder_tables(&self) -> Option<&EncoderTables> {
if self.raw_content {
return None;
}
Some(
self.encoder_tables
.as_deref()
.expect(ENCODER_TABLES_MISSING),
)
}
pub(crate) fn literals_state(&self) -> LiteralsState {
LiteralsState::with_huffman_table(
self.decoder_tables()
.and_then(|tables| tables.huffman_table),
)
}
pub(crate) fn huffman_encoding_table(&self) -> Option<&CTableX1> {
self.encoder_tables()
.map(|tables| &tables.huffman_encoding_table)
}
pub(crate) fn huffman_repeat_valid(&self) -> bool {
self.encoder_tables()
.is_some_and(|tables| tables.huffman_repeat_valid)
}
pub(crate) fn sequence_tables(&self) -> SequenceTablesState {
match self.decoder_tables() {
Some(tables) => SequenceTablesState::with_tables(
Some(tables.literal_length_table.clone()),
Some(tables.offset_table.clone()),
Some(tables.match_length_table.clone()),
),
None => SequenceTablesState::with_tables(None, None, None),
}
}
pub(crate) fn sequence_encoding_state(&self) -> SequenceEncodingState {
match self.encoder_tables() {
Some(tables) => SequenceEncodingState::with_states(
Some(tables.literal_length_encoding_state.clone()),
Some(tables.offset_encoding_state.clone()),
Some(tables.match_length_encoding_state.clone()),
),
None => SequenceEncodingState::with_states(None, None, None),
}
}
pub(crate) fn repeat_offsets(&self) -> RepeatOffsets {
self.repeat_offsets
}
pub(crate) fn optimal_price_seed(&self) -> Option<DictionaryPriceSeed> {
let tables = self.encoder_tables()?;
if !tables.huffman_repeat_valid {
return None;
}
let huf = &tables.huffman_encoding_table;
let ll_state = &tables.literal_length_encoding_state;
let ml_state = &tables.match_length_encoding_state;
let of_state = &tables.offset_encoding_state;
let mut lit_freq = [0u32; 256];
let mut lit_sum = 0u32;
for lit in 0u16..256 {
let bit_cost = huf.symbol_nb_bits(lit as u8) as u32;
let freq = if bit_cost > 0 {
1u32 << (11u32.saturating_sub(bit_cost))
} else {
1
};
lit_freq[lit as usize] = freq;
lit_sum += freq;
}
let ll_ct = ll_state.fse_ctable();
let mut ll_freq = [0u32; 36];
let mut ll_sum = 0u32;
for ll in 0..36 {
let bit_cost = ll_ct.max_nb_bits(ll);
let freq = if bit_cost > 0 {
1u32 << (10u32.saturating_sub(bit_cost))
} else {
1
};
ll_freq[ll] = freq;
ll_sum += freq;
}
let ml_ct = ml_state.fse_ctable();
let mut ml_freq = [0u32; 53];
let mut ml_sum = 0u32;
for ml in 0..53 {
let bit_cost = ml_ct.max_nb_bits(ml);
let freq = if bit_cost > 0 {
1u32 << (10u32.saturating_sub(bit_cost))
} else {
1
};
ml_freq[ml] = freq;
ml_sum += freq;
}
let of_ct = of_state.fse_ctable();
let mut of_freq = [0u32; 32];
let mut of_sum = 0u32;
for of in 0..32 {
let bit_cost = of_ct.max_nb_bits(of);
let freq = if bit_cost > 0 {
1u32 << (10u32.saturating_sub(bit_cost))
} else {
1
};
of_freq[of] = freq;
of_sum += freq;
}
Some(DictionaryPriceSeed {
lit_freq,
lit_sum,
ll_freq,
ll_sum,
ml_freq,
ml_sum,
of_freq,
of_sum,
})
}
fn raw(content: &'a [u8]) -> Self {
Self {
id: 0,
source_size: content.len(),
source: DictionaryBytes::Borrowed(content),
content_start: 0,
raw_content: true,
decoder_tables: None,
encoder_tables: None,
repeat_offsets: RepeatOffsets::default(),
}
}
}
struct ParsedCounts {
normalized: [i16; fse::SYMBOLVALUE_MAX + 1],
max_symbol_value: u32,
table_log: u32,
}
impl ParsedCounts {
fn dtable(&self) -> Result<fse::DTable> {
let mut dtable = fse::DTable::default();
fse::build_dtable(
&mut dtable,
&self.normalized,
self.max_symbol_value,
self.table_log,
)?;
Ok(dtable)
}
fn encoding_state(&self, required_max_symbol: u32) -> Result<SequenceEncodingPartState> {
let ctable = SequenceEncodingTable::from_normalized_counts(
&self.normalized,
self.max_symbol_value,
self.table_log,
)?;
Ok(SequenceEncodingPartState::new(
ctable,
repeat_mode_for_normalized_counts(
&self.normalized,
self.max_symbol_value,
required_max_symbol,
),
))
}
}
fn read_sequence_counts(
src: &[u8],
max_symbol_value: u32,
max_table_log: usize,
) -> Result<(ParsedCounts, usize)> {
let mut normalized = [0i16; fse::SYMBOLVALUE_MAX + 1];
let mut max_symbol_value = max_symbol_value;
let mut table_log = 0u32;
let consumed = fse::read_ncount(
&mut normalized,
&mut max_symbol_value,
&mut table_log,
src,
max_table_log,
)?;
Ok((
ParsedCounts {
normalized,
max_symbol_value,
table_log,
},
consumed,
))
}
fn dictionary_offset_required_max_symbol(content_len: usize) -> u32 {
if content_len <= (u32::MAX as usize).saturating_sub(128 * 1024) {
let max_offset = content_len as u32 + 128 * 1024;
highbit32(max_offset).min(OFFSET_MAX_SYMBOL_VALUE)
} else {
OFFSET_MAX_SYMBOL_VALUE
}
}
impl std::fmt::Debug for EncoderDictionary<'_> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("EncoderDictionary")
.field("id", &self.id())
.field("content_len", &self.as_inner().content().len())
.finish_non_exhaustive()
}
}
impl std::fmt::Debug for DecoderDictionary<'_> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.debug_struct("DecoderDictionary")
.field("id", &self.id())
.field("content_len", &self.as_inner().content().len())
.finish_non_exhaustive()
}
}
#[cfg(test)]
mod tests {
use super::*;
fn training_samples() -> Vec<Vec<u8>> {
(0..64)
.map(|index| {
format!(
"{{\"region\":\"us-east-{}\",\"tier\":\"gold\",\"amount\":{}}}\n",
index % 4,
index * 7,
)
.into_bytes()
})
.collect()
}
fn trained_dictionary_bytes() -> Vec<u8> {
let owned = training_samples();
let samples: Vec<&[u8]> = owned.iter().map(Vec::as_slice).collect();
crate::train_dictionary(&samples, 4 * 1024)
.expect("training a dictionary from these samples must succeed")
}
fn body_of(len: usize) -> Vec<u8> {
training_samples()
.concat()
.into_iter()
.cycle()
.take(len)
.collect()
}
fn options_at(level: i32) -> EncoderOptions {
EncoderOptions {
compression_level: crate::CompressionLevel::try_new(level).unwrap(),
..Default::default()
}
}
#[test]
fn one_preparation_covers_every_source_size() {
let dictionary = EncoderDictionary::from_shared(trained_dictionary_bytes()).unwrap();
let options = options_at(5);
dictionary.prepare(options);
let prepared = dictionary.cached_geometries();
assert_eq!(
prepared.len(),
1,
"preparing one level should hold tables for one geometry, got {prepared:?}"
);
for size in [1usize, 64, 700, 4096, 8 * 1024, 40_000, 300_000] {
crate::encode_all_with_prepared_dict_and_options(&body_of(size), &dictionary, options)
.expect("encoding against a prepared dictionary must succeed");
assert_eq!(
dictionary.cached_geometries(),
prepared,
"a {size}-byte source wanted a geometry the preparation did not cover"
);
}
assert!(
!dictionary.is_raw_content(),
"training produced raw content, so no tables were ever built"
);
}
#[test]
fn preparing_does_not_change_the_frame() {
let bytes = trained_dictionary_bytes();
let body = body_of(20_000);
for level in [1i32, 3, 5, 9, 12, 19] {
let options = options_at(level);
let lazy = EncoderDictionary::new(&bytes).unwrap();
let eager = EncoderDictionary::new(&bytes).unwrap();
eager.prepare(options);
assert_eq!(
crate::encode_all_with_prepared_dict_and_options(&body, &lazy, options).unwrap(),
crate::encode_all_with_prepared_dict_and_options(&body, &eager, options).unwrap(),
"preparing at level {level} changed the frame",
);
}
}
#[test]
fn preparing_one_level_does_not_cover_a_different_geometry() {
let dictionary = EncoderDictionary::from_shared(trained_dictionary_bytes()).unwrap();
dictionary.prepare(options_at(5));
let after_first = dictionary.cached_geometries();
assert_eq!(after_first.len(), 1);
dictionary.prepare(options_at(19));
let after_second = dictionary.cached_geometries();
assert_eq!(
after_second.len(),
2,
"a second geometry should be held alongside the first, got {after_second:?}"
);
assert!(
after_second.contains(&after_first[0]),
"preparing a second level discarded the first level's tables"
);
}
#[test]
fn preparing_a_raw_dictionary_builds_nothing() {
let dictionary = EncoderDictionary::new(b"raw dictionary content").unwrap();
dictionary.prepare(EncoderOptions::default());
assert!(dictionary.is_raw_content());
assert!(dictionary.cached_geometries().is_empty());
}
#[test]
fn a_shared_dictionary_matches_the_borrowed_one() {
let owned: Vec<Vec<u8>> = (0..64)
.map(|index| {
format!(
"{{\"region\":\"us-east-{}\",\"tier\":\"gold\",\"amount\":{}}}\n",
index % 4,
index * 7,
)
.into_bytes()
})
.collect();
let samples: Vec<&[u8]> = owned.iter().map(Vec::as_slice).collect();
let trained = crate::train_dictionary(&samples, 4 * 1024)
.expect("training a dictionary from these samples must succeed");
let bytes = &trained[..];
let borrowed = EncoderDictionary::new(bytes).unwrap();
let shared = EncoderDictionary::from_shared(bytes.to_vec()).unwrap();
assert_eq!(borrowed.id(), shared.id());
assert_eq!(borrowed.is_raw_content(), shared.is_raw_content());
assert_eq!(
borrowed.as_inner().content(),
shared.as_inner().content(),
"the content offset did not survive the rebuild"
);
assert_eq!(
borrowed.as_inner().matching_content(),
shared.as_inner().matching_content(),
"the two-byte match-start bias did not survive the rebuild"
);
let body = samples.concat();
let from_borrowed = crate::encode_all_with_prepared_dict(&body, &borrowed).unwrap();
let from_shared = crate::encode_all_with_prepared_dict(&body, &shared).unwrap();
assert_eq!(
from_borrowed, from_shared,
"the same dictionary compressed the same body to different bytes"
);
let decoding = DecoderDictionary::from_shared(bytes.to_vec()).unwrap();
assert_eq!(
crate::decode_all_with_prepared_dict(&from_shared, &decoding).unwrap(),
body,
);
assert!(
!borrowed.as_inner().content().is_empty(),
"the trained dictionary carried no content, so nothing above is a test"
);
assert!(
!borrowed.is_raw_content(),
"training produced raw content, so the content offset was never exercised"
);
}
#[test]
#[cfg_attr(target_family = "wasm", ignore = "no thread spawn on wasm")]
fn a_shared_dictionary_is_static_and_sendable() {
fn assert_static_send_sync<T: Send + Sync + 'static>(_: &T) {}
let dictionary = {
let bytes = b"raw shared dictionary content".to_vec();
EncoderDictionary::from_shared(bytes).unwrap()
};
assert_static_send_sync(&dictionary);
let cloned = dictionary.clone();
let echoed = std::thread::spawn(move || cloned.as_inner().content().to_vec())
.join()
.expect("the dictionary must survive the move onto another thread");
assert_eq!(echoed, b"raw shared dictionary content");
}
#[test]
fn parses_raw_content_dictionaries() {
let dictionary = Dictionary::parse(b"raw dictionary", TableDirection::Decoding).unwrap();
assert_eq!(dictionary.id(), 0);
assert_eq!(dictionary.content(), b"raw dictionary");
assert!(dictionary.decoder_tables.is_none());
assert!(dictionary.is_raw_content());
}
#[test]
fn prepares_raw_content_dictionaries() {
let dictionary = EncoderDictionary::new(b"raw dictionary").unwrap();
assert_eq!(dictionary.id(), 0);
assert!(dictionary.is_raw_content());
}
#[test]
fn rejects_bogus_formatted_dictionaries() {
let mut dictionary = Vec::new();
dictionary.extend_from_slice(&ZSTD_DICTIONARY_MAGIC.to_le_bytes());
dictionary.extend_from_slice(&7u32.to_le_bytes());
dictionary.push(0x82);
dictionary.push(0x11);
dictionary.extend_from_slice(&[0x24, 0x25, 0x25]);
dictionary.extend_from_slice(&[0x24, 0x25, 0x25]);
dictionary.extend_from_slice(&[0x24, 0x25, 0x25]);
dictionary.extend_from_slice(&9u32.to_le_bytes());
dictionary.extend_from_slice(&4u32.to_le_bytes());
dictionary.extend_from_slice(&8u32.to_le_bytes());
dictionary.extend_from_slice(b"content");
assert!(Dictionary::parse(&dictionary, TableDirection::Decoding).is_err());
assert!(Dictionary::parse(&dictionary, TableDirection::Encoding).is_err());
}
#[test]
fn the_two_directions_agree_on_where_content_starts() {
let bytes = trained_dictionary_bytes();
let encoding = Dictionary::parse(&bytes, TableDirection::Encoding).unwrap();
let decoding = Dictionary::parse(&bytes, TableDirection::Decoding).unwrap();
assert_eq!(encoding.content_start, decoding.content_start);
assert_eq!(encoding.content(), decoding.content());
assert_eq!(encoding.id(), decoding.id());
assert_eq!(encoding.repeat_offsets(), decoding.repeat_offsets());
assert!(
!encoding.content().is_empty(),
"the fixture must carry content"
);
}
#[test]
fn each_direction_builds_only_its_own_tables() {
let bytes = trained_dictionary_bytes();
let encoding = Dictionary::parse(&bytes, TableDirection::Encoding).unwrap();
assert!(encoding.encoder_tables.is_some());
assert!(
encoding.decoder_tables.is_none(),
"an encoding parse built decoding tables nothing on that path can read"
);
let decoding = Dictionary::parse(&bytes, TableDirection::Decoding).unwrap();
assert!(decoding.decoder_tables.is_some());
assert!(
decoding.encoder_tables.is_none(),
"a decoding parse built encoding tables nothing on that path can read"
);
let raw = Dictionary::raw(b"raw content");
assert!(raw.is_raw_content());
assert!(raw.encoder_tables.is_none() && raw.decoder_tables.is_none());
assert!(!encoding.is_raw_content() && !decoding.is_raw_content());
}
#[test]
fn the_two_directions_accept_and_reject_the_same_dictionaries() {
let valid = trained_dictionary_bytes();
let mut cases: Vec<Vec<u8>> = vec![
valid.clone(),
b"raw content, no magic".to_vec(),
Vec::new(),
ZSTD_DICTIONARY_MAGIC.to_le_bytes().to_vec(),
];
for cut in [8, 9, 12, 20, 40, 80, valid.len() / 2, valid.len() - 1] {
if cut < valid.len() {
cases.push(valid[..cut].to_vec());
}
}
for at in [8, 9, 10, 16, 24] {
if at < valid.len() {
let mut broken = valid.clone();
broken[at] ^= 0xff;
cases.push(broken);
}
}
let mut disagreements = Vec::new();
for (index, case) in cases.iter().enumerate() {
let encoding = Dictionary::parse(case, TableDirection::Encoding).is_ok();
let decoding = Dictionary::parse(case, TableDirection::Decoding).is_ok();
if encoding != decoding {
disagreements.push(format!(
"case {index} ({} bytes): encoding accepted={encoding}, decoding accepted={decoding}",
case.len()
));
}
}
assert!(
disagreements.is_empty(),
"the two directions disagreed on {} of {} dictionaries:\n{}",
disagreements.len(),
cases.len(),
disagreements.join("\n"),
);
}
}