#![forbid(unsafe_code)]
use alloc::vec::Vec;
use crate::dict::DICT_MAGIC;
use crate::fse::{LL_DEFAULT_ACCURACY, ML_DEFAULT_ACCURACY, OF_DEFAULT_ACCURACY};
use crate::fse::{LL_DEFAULT_DIST, ML_DEFAULT_DIST, OF_DEFAULT_DIST};
use crate::huffman::encode::HuffmanEncodeTable;
pub fn finalize_dictionary(content: &[u8], samples: &[&[u8]], dict_size: usize) -> Vec<u8> {
let content_len = content.len().min(dict_size.saturating_sub(256));
let rep_offsets = compute_rep_offsets(content, samples);
let dict_id = compute_dict_id(content, samples);
let mut dict = Vec::with_capacity(dict_size);
dict.extend_from_slice(&DICT_MAGIC.to_le_bytes());
dict.extend_from_slice(&dict_id.to_le_bytes());
let content_start = content.len().saturating_sub(content_len);
let kept = &content[content_start..];
dict.extend_from_slice(literal_table(kept, samples).weights_description());
let of_bytes = crate::fse::table_builder::serialize_fse_table_description(
&OF_DEFAULT_DIST,
OF_DEFAULT_ACCURACY,
);
dict.extend_from_slice(&of_bytes);
let ml_bytes = crate::fse::table_builder::serialize_fse_table_description(
&ML_DEFAULT_DIST,
ML_DEFAULT_ACCURACY,
);
dict.extend_from_slice(&ml_bytes);
let ll_bytes = crate::fse::table_builder::serialize_fse_table_description(
&LL_DEFAULT_DIST,
LL_DEFAULT_ACCURACY,
);
dict.extend_from_slice(&ll_bytes);
dict.extend_from_slice(&rep_offsets[0].to_le_bytes());
dict.extend_from_slice(&rep_offsets[1].to_le_bytes());
dict.extend_from_slice(&rep_offsets[2].to_le_bytes());
dict.extend_from_slice(kept);
dict
}
const LITERAL_MIN_MATCH: usize = 5;
const FLAT_LITERALS: [u32; 256] = {
let mut counts = [2; 256];
counts[0] = 4;
counts[253] = 1;
counts[254] = 1;
counts
};
fn literal_table(content: &[u8], samples: &[&[u8]]) -> HuffmanEncodeTable {
let counts = literal_counts(content, samples);
HuffmanEncodeTable::from_histogram(&counts)
.or_else(|| HuffmanEncodeTable::from_histogram(&FLAT_LITERALS))
.expect("flat literal counts build a table")
}
fn literal_counts(content: &[u8], samples: &[&[u8]]) -> [u32; 256] {
const CONTENT_LOG: u32 = 16;
const SAMPLE_LOG: u32 = 12;
let hash = |b: &[u8], log: u32| {
let v = u32::from_le_bytes([b[0], b[1], b[2], b[3]]);
(v.wrapping_mul(0x9E37_79B1) >> (32 - log)) as usize
};
let common = |a: &[u8], b: &[u8]| a.iter().zip(b).take_while(|(x, y)| x == y).count();
let mut in_content = alloc::vec![usize::MAX; 1 << CONTENT_LOG];
for i in 0..content.len().saturating_sub(LITERAL_MIN_MATCH - 1) {
in_content[hash(&content[i..], CONTENT_LOG)] = i;
}
let mut counts = [1u32; 256];
let mut in_sample = alloc::vec![usize::MAX; 1 << SAMPLE_LOG];
for sample in samples {
in_sample.fill(usize::MAX);
let mut i = 0;
while i < sample.len() {
let mut len = 0;
if i + LITERAL_MIN_MATCH <= sample.len() {
let rest = &sample[i..];
let c = in_content[hash(rest, CONTENT_LOG)];
if c != usize::MAX {
len = common(rest, &content[c..]);
}
let h = hash(rest, SAMPLE_LOG);
let p = in_sample[h];
if p != usize::MAX {
len = len.max(common(rest, &sample[p..]));
}
in_sample[h] = i;
}
if len >= LITERAL_MIN_MATCH {
i += len;
} else {
counts[usize::from(sample[i])] = counts[usize::from(sample[i])].saturating_add(1);
i += 1;
}
}
}
counts
}
fn compute_rep_offsets(content: &[u8], samples: &[&[u8]]) -> [u32; 3] {
let max_offset = content.len().min(1024);
if max_offset == 0 {
return [1, 4, 8];
}
let mut offset_scores = Vec::with_capacity(max_offset);
let content_len = content.len();
for offset in 1..=max_offset as u32 {
let mut total_matches = 0u32;
for &sample in samples.iter().take(50) {
let check_len = sample.len().min(128);
let start_in_content = content_len - offset as usize;
let comparable = check_len.min(content_len - start_in_content);
let content_slice = &content[start_in_content..start_in_content + comparable];
let sample_slice = &sample[..comparable];
let mut m = 0;
while m < comparable && content_slice[m] == sample_slice[m] {
m += 1;
}
if m >= 4 {
total_matches += m as u32;
}
}
if total_matches > 0 {
offset_scores.push((offset, total_matches));
}
}
offset_scores.sort_unstable_by_key(|e| core::cmp::Reverse(e.1));
let mut rep = [1u32, 4, 8];
let mut found = 0usize;
for &(offset, _) in &offset_scores {
if offset != rep[0] && offset != rep[1] && offset != rep[2] {
rep[found] = offset;
found += 1;
if found == 3 {
break;
}
}
}
rep
}
fn compute_dict_id(content: &[u8], samples: &[&[u8]]) -> u32 {
let mut h = 0x811c_9dc5_u32;
for &b in content {
h ^= b as u32;
h = h.wrapping_mul(0x0100_0193);
}
for &sample in samples.iter().take(10) {
for &b in sample {
h ^= b as u32;
h = h.wrapping_mul(0x0100_0193);
}
}
if h == 0 {
h = 1;
}
h
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn flat_literal_counts_build_a_table() {
assert!(HuffmanEncodeTable::from_histogram(&[1; 256]).is_none());
let table = HuffmanEncodeTable::from_histogram(&FLAT_LITERALS).unwrap();
assert!(table.estimate_bits(&[1; 256]).is_some(), "codes every byte");
}
#[test]
fn samples_without_literals_get_the_flat_table() {
let content: Vec<u8> = (0..4096u32).map(|i| (i * 7 % 251) as u8).collect();
let flat = HuffmanEncodeTable::from_histogram(&FLAT_LITERALS).unwrap();
for samples in [&[][..], &[&b""[..]], &[&content[100..200]]] {
let table = literal_table(&content, samples);
assert_eq!(table.weights_description(), flat.weights_description());
}
}
}