use crate::{
dictionary::EncoderDictionary,
encode::{
CompressionLevel, CompressionParameters, EncoderOptions, EntropyEncodeScratch,
compression_parameters_for_dictionary_training, count_dictionary_entropy_stats,
encode_all_with_prepared_dict_and_options,
},
entropy::{fse, huff0, mem::highbit32},
error::{Error, Result},
xxhash::xxh64,
};
pub const DICTIONARY_SIZE_MIN: usize = 256;
const OFFCODE_MAX: usize = 30;
const MAX_MATCH_LENGTH_CODE: usize = 52;
const MAX_LITERAL_LENGTH_CODE: usize = 35;
const OFFSET_FSE_LOG: u32 = 8;
const MATCH_LENGTH_FSE_LOG: u32 = 9;
const LITERAL_LENGTH_FSE_LOG: u32 = 9;
const HUFFMAN_LOG: u32 = 11;
const REPEAT_OFFSET_START: [u32; 3] = [1, 4, 8];
const HEADER_BUFFER_SIZE: usize = 256;
const FASTCOVER_MAX_F: u32 = 31;
const FASTCOVER_MAX_ACCEL: u32 = 10;
const FASTCOVER_DEFAULT_SPLITPOINT: f64 = 0.75;
const DEFAULT_F: u32 = 20;
const DEFAULT_ACCEL: u32 = 1;
const ACCEL_PARAMETERS: [(u32, u32); (FASTCOVER_MAX_ACCEL + 1) as usize] = [
(100, 0),
(100, 0),
(50, 1),
(34, 2),
(25, 3),
(20, 4),
(17, 5),
(14, 6),
(13, 7),
(11, 8),
(10, 9),
];
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct DictionaryTrainingParameters {
pub k: u32,
pub d: u32,
pub f: u32,
pub accel: u32,
pub steps: u32,
pub split_point: f64,
pub compression_level: CompressionLevel,
pub dictionary_id: u32,
}
impl Default for DictionaryTrainingParameters {
fn default() -> Self {
Self {
k: 0,
d: 0,
f: 0,
accel: 0,
steps: 0,
split_point: 0.0,
compression_level: CompressionLevel::DEFAULT,
dictionary_id: 0,
}
}
}
#[derive(Debug, Clone)]
pub struct TrainedDictionary {
dictionary: Vec<u8>,
k: u32,
d: u32,
total_compressed_size: usize,
}
impl TrainedDictionary {
pub fn as_bytes(&self) -> &[u8] {
&self.dictionary
}
pub fn into_bytes(self) -> Vec<u8> {
self.dictionary
}
pub fn k(&self) -> u32 {
self.k
}
pub fn d(&self) -> u32 {
self.d
}
pub fn total_compressed_size(&self) -> usize {
self.total_compressed_size
}
}
pub fn train_dictionary(samples: &[&[u8]], capacity: usize) -> Result<Vec<u8>> {
let parameters = DictionaryTrainingParameters {
d: 8,
steps: 4,
..DictionaryTrainingParameters::default()
};
Ok(train_dictionary_with_parameters(samples, capacity, parameters)?.into_bytes())
}
pub fn train_dictionary_with_parameters(
samples: &[&[u8]],
capacity: usize,
parameters: DictionaryTrainingParameters,
) -> Result<TrainedDictionary> {
let resolved = ResolvedParameters::resolve(parameters, capacity, samples.len())?;
let corpus = Corpus::new(samples);
let mut best: Option<Candidate> = None;
let mut scratch = TrainingScratch::default();
for d in (resolved.min_d..=resolved.max_d).step_by(2) {
let context =
FrequencyContext::build(&corpus, d, resolved.f, resolved.split_point, resolved.skip)?;
let mut k = resolved.min_k;
while k <= resolved.max_k {
if let Some(candidate) =
context.try_segment_size(k, capacity, &resolved, &mut scratch)?
{
if best
.as_ref()
.is_none_or(|b| candidate.total_compressed_size < b.total_compressed_size)
{
best = Some(candidate);
}
}
match k.checked_add(resolved.k_step) {
Some(next) => k = next,
None => break,
}
}
}
let best = best.ok_or(Error::InvalidParameter(
"no dictionary could be trained from these samples",
))?;
Ok(TrainedDictionary {
dictionary: best.dictionary,
k: best.k,
d: best.d,
total_compressed_size: best.total_compressed_size,
})
}
struct Candidate {
dictionary: Vec<u8>,
k: u32,
d: u32,
total_compressed_size: usize,
}
#[derive(Default)]
struct TrainingScratch {
freqs: Vec<u32>,
segment_freqs: Vec<u32>,
content: Vec<u8>,
encode: EntropyEncodeScratch,
block: Vec<u8>,
}
struct ResolvedParameters {
min_d: u32,
max_d: u32,
min_k: u32,
max_k: u32,
k_step: u32,
f: u32,
skip: u32,
finalize_percent: u32,
split_point: f64,
compression_level: CompressionLevel,
dictionary_id: u32,
}
impl ResolvedParameters {
fn resolve(
parameters: DictionaryTrainingParameters,
capacity: usize,
sample_count: usize,
) -> Result<Self> {
if sample_count == 0 {
return Err(Error::InvalidParameter(
"training needs at least one sample",
));
}
if capacity < DICTIONARY_SIZE_MIN {
return Err(Error::DstSizeTooSmall);
}
let split_point = if parameters.split_point <= 0.0 {
FASTCOVER_DEFAULT_SPLITPOINT
} else {
parameters.split_point
};
if split_point > 1.0 {
return Err(Error::InvalidParameter("split_point must be in (0, 1]"));
}
let accel = if parameters.accel == 0 {
DEFAULT_ACCEL
} else {
parameters.accel
};
if accel > FASTCOVER_MAX_ACCEL {
return Err(Error::InvalidParameter("accel must be in 1..=10"));
}
let f = if parameters.f == 0 {
DEFAULT_F
} else {
parameters.f
};
if f > FASTCOVER_MAX_F {
return Err(Error::InvalidParameter("f must be in 1..=31"));
}
if parameters.d != 0 && parameters.d != 6 && parameters.d != 8 {
return Err(Error::InvalidParameter("d must be 6 or 8"));
}
let (min_d, max_d) = if parameters.d == 0 {
(6, 8)
} else {
(parameters.d, parameters.d)
};
let (min_k, max_k) = if parameters.k == 0 {
(50, 2000)
} else {
(parameters.k, parameters.k)
};
if min_k < max_d || max_k < min_k {
return Err(Error::InvalidParameter("k must be at least d"));
}
let steps = if parameters.steps == 0 {
40
} else {
parameters.steps
};
let (finalize_percent, skip) = ACCEL_PARAMETERS[accel as usize];
Ok(Self {
min_d,
max_d,
min_k,
max_k,
k_step: ((max_k - min_k) / steps).max(1),
f,
skip,
finalize_percent,
split_point,
compression_level: parameters.compression_level,
dictionary_id: parameters.dictionary_id,
})
}
}
struct Corpus {
bytes: Vec<u8>,
offsets: Vec<usize>,
}
impl Corpus {
fn new(samples: &[&[u8]]) -> Self {
let total = samples.iter().map(|sample| sample.len()).sum();
let mut bytes = Vec::with_capacity(total);
let mut offsets = Vec::with_capacity(samples.len() + 1);
offsets.push(0);
for sample in samples {
bytes.extend_from_slice(sample);
offsets.push(bytes.len());
}
Self { bytes, offsets }
}
fn count(&self) -> usize {
self.offsets.len() - 1
}
fn sample(&self, index: usize) -> &[u8] {
&self.bytes[self.offsets[index]..self.offsets[index + 1]]
}
}
#[inline]
fn hash_to_index(bytes: &[u8], pos: usize, f: u32, d: u32) -> usize {
const PRIME_6_BYTES: u64 = 227_718_039_650_203;
const PRIME_8_BYTES: u64 = 0xCF1B_BCDC_B7A5_6463;
let value = u64::from_le_bytes(bytes[pos..pos + 8].try_into().expect("eight bytes"));
let hashed = if d == 6 {
(value << 16).wrapping_mul(PRIME_6_BYTES)
} else {
value.wrapping_mul(PRIME_8_BYTES)
};
(hashed >> (64 - f)) as usize
}
struct FrequencyContext<'a> {
corpus: &'a Corpus,
train_samples: usize,
dmers: usize,
freqs: Vec<u32>,
d: u32,
f: u32,
}
impl<'a> FrequencyContext<'a> {
fn build(corpus: &'a Corpus, d: u32, f: u32, split_point: f64, skip: u32) -> Result<Self> {
let sample_count = corpus.count();
let (train_samples, test_samples) = if split_point < 1.0 {
let train = (sample_count as f64 * split_point) as usize;
(train, sample_count - train)
} else {
(sample_count, sample_count)
};
let training_bytes = corpus.offsets[train_samples];
let read_length = (d as usize).max(8);
if corpus.bytes.len() < read_length || corpus.bytes.len() >= u32::MAX as usize {
return Err(Error::SrcSizeWrong);
}
if train_samples < 5 {
return Err(Error::InvalidParameter(
"training needs at least 5 training samples",
));
}
if test_samples < 1 {
return Err(Error::InvalidParameter(
"training needs at least one sample held back for measurement",
));
}
if training_bytes < read_length {
return Err(Error::InvalidParameter(
"the training samples are too small to count substrings in",
));
}
let mut freqs = zeroed_u32_table(1usize << f)?;
for index in 0..train_samples {
let mut start = corpus.offsets[index];
let end = corpus.offsets[index + 1];
while start + read_length <= end {
freqs[hash_to_index(&corpus.bytes, start, f, d)] += 1;
start += skip as usize + 1;
}
}
Ok(Self {
corpus,
train_samples,
dmers: training_bytes - read_length + 1,
freqs,
d,
f,
})
}
}
struct Epochs {
count: u32,
size: u32,
}
fn compute_epochs(max_dict_size: u32, dmers: u32, k: u32, passes: u32) -> Epochs {
let min_epoch_size = k.saturating_mul(10);
let count = (max_dict_size / k / passes).max(1);
let size = dmers / count;
if size >= min_epoch_size {
return Epochs { count, size };
}
let size = min_epoch_size.min(dmers);
Epochs {
count: dmers / size,
size,
}
}
#[derive(Clone, Copy, Default)]
struct Segment {
begin: u32,
end: u32,
score: u32,
}
impl FrequencyContext<'_> {
fn select_segment(
&self,
freqs: &mut [u32],
segment_freqs: &mut [u32],
begin: u32,
end: u32,
k: u32,
) -> Segment {
let dmers_in_k = k - self.d + 1;
let mut best = Segment::default();
let mut active = Segment {
begin,
end: begin,
score: 0,
};
while active.end < end {
let index = hash_to_index(&self.corpus.bytes, active.end as usize, self.f, self.d);
if segment_freqs[index] == 0 {
active.score = active.score.wrapping_add(freqs[index]);
}
active.end += 1;
segment_freqs[index] += 1;
if active.end - active.begin == dmers_in_k + 1 {
let removed =
hash_to_index(&self.corpus.bytes, active.begin as usize, self.f, self.d);
segment_freqs[removed] -= 1;
if segment_freqs[removed] == 0 {
active.score = active.score.wrapping_sub(freqs[removed]);
}
active.begin += 1;
}
if active.score > best.score {
best = active;
}
}
while active.begin < end {
let removed = hash_to_index(&self.corpus.bytes, active.begin as usize, self.f, self.d);
segment_freqs[removed] -= 1;
active.begin += 1;
}
for pos in best.begin..best.end {
let index = hash_to_index(&self.corpus.bytes, pos as usize, self.f, self.d);
freqs[index] = 0;
}
best
}
fn build_content(
&self,
freqs: &mut [u32],
segment_freqs: &mut [u32],
content: &mut [u8],
k: u32,
) -> usize {
let capacity = content.len();
let mut tail = capacity;
let epochs = compute_epochs(capacity as u32, self.dmers as u32, k, 1);
const MAX_ZERO_SCORE_RUN: usize = 10;
let mut zero_score_run = 0;
let mut epoch = 0u32;
while tail > 0 {
let begin = epoch * epochs.size;
let segment = self.select_segment(freqs, segment_freqs, begin, begin + epochs.size, k);
epoch = (epoch + 1) % epochs.count;
if segment.score == 0 {
zero_score_run += 1;
if zero_score_run >= MAX_ZERO_SCORE_RUN {
break;
}
continue;
}
zero_score_run = 0;
let size = ((segment.end - segment.begin + self.d - 1) as usize).min(tail);
if size < self.d as usize {
break;
}
tail -= size;
let from = segment.begin as usize;
content[tail..tail + size].copy_from_slice(&self.corpus.bytes[from..from + size]);
}
tail
}
fn try_segment_size(
&self,
k: u32,
capacity: usize,
resolved: &ResolvedParameters,
scratch: &mut TrainingScratch,
) -> Result<Option<Candidate>> {
if k < self.d || k as usize > capacity {
return Ok(None);
}
scratch.freqs.clear();
scratch.freqs.extend_from_slice(&self.freqs);
scratch.segment_freqs.clear();
scratch
.segment_freqs
.try_reserve_exact(1usize << self.f)
.map_err(|_| Error::Generic)?;
scratch.segment_freqs.resize(1usize << self.f, 0);
scratch.content.clear();
scratch.content.resize(capacity, 0);
let tail = self.build_content(
&mut scratch.freqs,
&mut scratch.segment_freqs,
&mut scratch.content,
k,
);
let content_size = capacity - tail;
if content_size == 0 {
return Ok(None);
}
let finalize_samples = (self.train_samples * resolved.finalize_percent as usize / 100)
.min(self.corpus.count());
let dictionary = finalize_dictionary(
&scratch.content[tail..],
self.corpus,
finalize_samples,
capacity,
resolved,
&mut scratch.encode,
&mut scratch.block,
)?;
let total_compressed_size = self.measure(&dictionary, resolved)?;
Ok(Some(Candidate {
dictionary,
k,
d: self.d,
total_compressed_size,
}))
}
fn measure(&self, dictionary: &[u8], resolved: &ResolvedParameters) -> Result<usize> {
let prepared = EncoderDictionary::new(dictionary)?;
let options = EncoderOptions::default().with_compression_level(resolved.compression_level);
let mut total = dictionary.len();
let first = if resolved.split_point < 1.0 {
self.train_samples
} else {
0
};
for index in first..self.corpus.count() {
let sample = self.corpus.sample(index);
total += encode_all_with_prepared_dict_and_options(sample, &prepared, options)?.len();
}
Ok(total)
}
}
pub(crate) struct EntropyStats {
pub(crate) literals: [u32; 256],
pub(crate) offset_codes: [u32; OFFCODE_MAX + 1],
pub(crate) match_lengths: [u32; MAX_MATCH_LENGTH_CODE + 1],
pub(crate) literal_lengths: [u32; MAX_LITERAL_LENGTH_CODE + 1],
}
impl EntropyStats {
fn new(offcode_max: usize) -> Self {
let mut offset_codes = [0u32; OFFCODE_MAX + 1];
for slot in offset_codes.iter_mut().take(offcode_max + 1) {
*slot = 1;
}
Self {
literals: [1; 256],
offset_codes,
match_lengths: [1; MAX_MATCH_LENGTH_CODE + 1],
literal_lengths: [1; MAX_LITERAL_LENGTH_CODE + 1],
}
}
fn flatten_literals(&mut self) {
self.literals = [2; 256];
self.literals[0] = 4;
self.literals[253] = 1;
self.literals[254] = 1;
}
}
fn finalize_dictionary(
content: &[u8],
corpus: &Corpus,
finalize_samples: usize,
capacity: usize,
resolved: &ResolvedParameters,
scratch: &mut EntropyEncodeScratch,
block: &mut Vec<u8>,
) -> Result<Vec<u8>> {
if capacity < DICTIONARY_SIZE_MIN {
return Err(Error::DstSizeTooSmall);
}
let mut header = [0u8; HEADER_BUFFER_SIZE];
header[..4].copy_from_slice(&crate::dictionary::ZSTD_DICTIONARY_MAGIC.to_le_bytes());
let dictionary_id = if resolved.dictionary_id != 0 {
resolved.dictionary_id
} else {
let hashed = xxh64(content, 0);
((hashed % ((1u64 << 31) - 32768)) + 32768) as u32
};
header[4..8].copy_from_slice(&dictionary_id.to_le_bytes());
let mut header_size = 8;
header_size += analyze_entropy(
&mut header[header_size..],
content,
corpus,
finalize_samples,
resolved,
scratch,
block,
)?;
let content = &content[..content.len().min(capacity - header_size)];
let min_content_size = REPEAT_OFFSET_START.iter().copied().max().unwrap_or(0) as usize;
let padding_size = if content.len() < min_content_size {
if header_size + min_content_size > capacity {
return Err(Error::DstSizeTooSmall);
}
min_content_size - content.len()
} else {
0
};
let mut dictionary = Vec::with_capacity(header_size + padding_size + content.len());
dictionary.extend_from_slice(&header[..header_size]);
dictionary.resize(header_size + padding_size, 0);
dictionary.extend_from_slice(content);
Ok(dictionary)
}
fn analyze_entropy(
dst: &mut [u8],
content: &[u8],
corpus: &Corpus,
finalize_samples: usize,
resolved: &ResolvedParameters,
scratch: &mut EntropyEncodeScratch,
block: &mut Vec<u8>,
) -> Result<usize> {
let offcode_max = highbit32((content.len() + (128 << 10)) as u32) as usize;
if offcode_max > OFFCODE_MAX {
return Err(Error::InvalidParameter(
"dictionary is too large to describe its offset codes",
));
}
let total_size: usize = (0..finalize_samples).map(|i| corpus.sample(i).len()).sum();
let average_size = total_size / finalize_samples.max(1);
let prepared = EncoderDictionary::raw_content(content);
let params: CompressionParameters = compression_parameters_for_dictionary_training(
resolved.compression_level,
Some(average_size),
prepared.as_inner(),
);
let mut stats = EntropyStats::new(offcode_max);
for index in 0..finalize_samples {
let sample = corpus.sample(index);
if sample.is_empty() {
continue;
}
count_dictionary_entropy_stats(sample, &prepared, params, scratch, block, &mut stats)?;
}
let mut written = 0usize;
let mut huffman_workspace = huff0::CompressWorkspace::default();
let mut huffman_log = HUFFMAN_LOG;
{
let mut max_bits =
huffman_workspace.build_literal_ctable(&stats.literals, 255, huffman_log)?;
if max_bits == 8 {
stats.flatten_literals();
max_bits = huffman_workspace.build_literal_ctable(&stats.literals, 255, huffman_log)?;
}
huffman_log = max_bits;
written += huffman_workspace.write_literal_ctable(dst, 255, huffman_log)?;
}
written += write_normalized_table(
&mut dst[written..],
&stats.offset_codes[..=offcode_max],
OFFSET_FSE_LOG,
offcode_max as u32,
OFFCODE_MAX as u32,
)?;
written += write_normalized_table(
&mut dst[written..],
&stats.match_lengths,
MATCH_LENGTH_FSE_LOG,
MAX_MATCH_LENGTH_CODE as u32,
MAX_MATCH_LENGTH_CODE as u32,
)?;
written += write_normalized_table(
&mut dst[written..],
&stats.literal_lengths,
LITERAL_LENGTH_FSE_LOG,
MAX_LITERAL_LENGTH_CODE as u32,
MAX_LITERAL_LENGTH_CODE as u32,
)?;
if dst.len() < written + 12 {
return Err(Error::DstSizeTooSmall);
}
for (index, offset) in REPEAT_OFFSET_START.iter().enumerate() {
let at = written + index * 4;
dst[at..at + 4].copy_from_slice(&offset.to_le_bytes());
}
Ok(written + 12)
}
#[cfg(any(feature = "internal-trace", test))]
#[doc(hidden)]
pub type DictionaryEntropyHistograms = (Vec<u32>, Vec<u32>, Vec<u32>, Vec<u32>);
#[cfg(any(feature = "internal-trace", test))]
#[cfg_attr(not(feature = "internal-trace"), allow(dead_code))]
#[doc(hidden)]
pub fn trace_dictionary_entropy_stats(
content: &[u8],
samples: &[&[u8]],
level: CompressionLevel,
) -> Result<DictionaryEntropyHistograms> {
let total: usize = samples.iter().map(|sample| sample.len()).sum();
let average = total / samples.len().max(1);
let offcode_max = highbit32((content.len() + (128 << 10)) as u32) as usize;
let prepared = EncoderDictionary::raw_content(content);
let params =
compression_parameters_for_dictionary_training(level, Some(average), prepared.as_inner());
let mut stats = EntropyStats::new(offcode_max);
let mut scratch = EntropyEncodeScratch::default();
let mut block = Vec::new();
for sample in samples {
if sample.is_empty() {
continue;
}
count_dictionary_entropy_stats(
sample,
&prepared,
params,
&mut scratch,
&mut block,
&mut stats,
)?;
}
Ok((
stats.literals.to_vec(),
stats.offset_codes.to_vec(),
stats.match_lengths.to_vec(),
stats.literal_lengths.to_vec(),
))
}
fn zeroed_u32_table(len: usize) -> Result<Vec<u32>> {
let mut table = Vec::new();
table.try_reserve_exact(len).map_err(|_| Error::Generic)?;
table.resize(len, 0);
Ok(table)
}
fn write_normalized_table(
dst: &mut [u8],
counts: &[u32],
table_log: u32,
normalize_max: u32,
write_max: u32,
) -> Result<usize> {
let total: u32 = counts.iter().sum();
let mut normalized = vec![0i16; write_max as usize + 1];
let table_log = fse::normalize_count(
&mut normalized,
table_log,
counts,
total as usize,
normalize_max,
true,
)?;
fse::write_ncount(dst, &normalized, write_max, table_log)
}
#[cfg(test)]
mod tests;