#![allow(dead_code)]
use crate::encode::UpstreamStrategy;
use crate::window::max_table_log;
pub(crate) const LDM_DEFAULT_WINDOW_LOG: u32 = 27;
const LDM_MIN_MATCH_LENGTH: u32 = 64;
const LDM_BUCKET_SIZE_LOG: u32 = 4;
const LDM_BUCKET_SIZE_LOG_MAX: u32 = 8;
const HASH_LOG_MIN: u32 = 6;
const HASH_LOG_MAX: u32 = 30;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum LdmMode {
#[default]
Auto,
Enabled,
Disabled,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub(crate) struct LdmParameterOverrides {
pub(crate) hash_log: Option<u32>,
pub(crate) min_match_length: Option<u32>,
pub(crate) bucket_size_log: Option<u32>,
pub(crate) hash_rate_log: Option<u32>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct LdmParameters {
pub(crate) window_log: u32,
pub(crate) hash_log: u32,
pub(crate) min_match_length: u32,
pub(crate) bucket_size_log: u32,
pub(crate) hash_rate_log: u32,
}
pub(crate) fn resolve_enable_ldm(
mode: LdmMode,
strategy: UpstreamStrategy,
window_log: u32,
) -> bool {
match mode {
LdmMode::Enabled => true,
LdmMode::Disabled => false,
LdmMode::Auto => strategy >= UpstreamStrategy::BinaryTreeOpt && window_log >= 27,
}
}
pub(crate) fn force_window_log(mode: LdmMode, window_log: u32) -> u32 {
if matches!(mode, LdmMode::Enabled) {
LDM_DEFAULT_WINDOW_LOG
} else {
window_log
}
}
impl LdmParameters {
pub(crate) fn resolve(
overrides: LdmParameterOverrides,
strategy: UpstreamStrategy,
window_log: u32,
) -> Self {
let overrides = LdmParameterOverrides {
hash_log: overrides.hash_log.filter(|&value| value != 0),
min_match_length: overrides.min_match_length.filter(|&value| value != 0),
bucket_size_log: overrides.bucket_size_log.filter(|&value| value != 0),
hash_rate_log: overrides.hash_rate_log.filter(|&value| value != 0),
};
let mut hash_rate_log = overrides.hash_rate_log.unwrap_or(0);
if hash_rate_log == 0 {
hash_rate_log = match overrides.hash_log {
Some(hash_log) if window_log > hash_log => window_log - hash_log,
Some(_) => 0,
None => 7 - (strategy.as_upstream_code() / 3),
};
}
let hash_log = overrides.hash_log.unwrap_or_else(|| {
window_log
.saturating_sub(hash_rate_log)
.clamp(HASH_LOG_MIN, HASH_LOG_MAX)
});
let min_match_length = overrides.min_match_length.unwrap_or({
if strategy >= UpstreamStrategy::BinaryTreeUltra {
LDM_MIN_MATCH_LENGTH / 2
} else {
LDM_MIN_MATCH_LENGTH
}
});
let bucket_size_log = overrides.bucket_size_log.unwrap_or_else(|| {
strategy
.as_upstream_code()
.clamp(LDM_BUCKET_SIZE_LOG, LDM_BUCKET_SIZE_LOG_MAX)
});
Self {
window_log,
hash_log,
min_match_length,
bucket_size_log: bucket_size_log.min(hash_log),
hash_rate_log,
}
}
}
#[rustfmt::skip]
const GEAR_TAB: [u64; 256] = [
0xf5b8f72c5f77775c, 0x84935f266b7ac412, 0xb647ada9ca730ccc, 0xb065bb4b114fb1de,
0x34584e7e8c3a9fd0, 0x4e97e17c6ae26b05, 0x3a03d743bc99a604, 0xcecd042422c4044f,
0x76de76c58524259e, 0x9c8528f65badeaca, 0x86563706e2097529, 0x2902475fa375d889,
0xafb32a9739a5ebe6, 0xce2714da3883e639, 0x21eaf821722e69e, 0x37b628620b628,
0x49a8d455d88caf5, 0x8556d711e6958140, 0x4f7ae74fc605c1f, 0x829f0c3468bd3a20,
0x4ffdc885c625179e, 0x8473de048a3daf1b, 0x51008822b05646b2, 0x69d75d12b2d1cc5f,
0x8c9d4a19159154bc, 0xc3cc10f4abbd4003, 0xd06ddc1cecb97391, 0xbe48e6e7ed80302e,
0x3481db31cee03547, 0xacc3f67cdaa1d210, 0x65cb771d8c7f96cc, 0x8eb27177055723dd,
0xc789950d44cd94be, 0x934feadc3700b12b, 0x5e485f11edbdf182, 0x1e2e2a46fd64767a,
0x2969ca71d82efa7c, 0x9d46e9935ebbba2e, 0xe056b67e05e6822b, 0x94d73f55739d03a0,
0xcd7010bdb69b5a03, 0x455ef9fcd79b82f4, 0x869cb54a8749c161, 0x38d1a4fa6185d225,
0xb475166f94bbe9bb, 0xa4143548720959f1, 0x7aed4780ba6b26ba, 0xd0ce264439e02312,
0x84366d746078d508, 0xa8ce973c72ed17be, 0x21c323a29a430b01, 0x9962d617e3af80ee,
0xab0ce91d9c8cf75b, 0x530e8ee6d19a4dbc, 0x2ef68c0cf53f5d72, 0xc03a681640a85506,
0x496e4e9f9c310967, 0x78580472b59b14a0, 0x273824c23b388577, 0x66bf923ad45cb553,
0x47ae1a5a2492ba86, 0x35e304569e229659, 0x4765182a46870b6f, 0x6cbab625e9099412,
0xddac9a2e598522c1, 0x7172086e666624f2, 0xdf5003ca503b7837, 0x88c0c1db78563d09,
0x58d51865acfc289d, 0x177671aec65224f1, 0xfb79d8a241e967d7, 0x2be1e101cad9a49a,
0x6625682f6e29186b, 0x399553457ac06e50, 0x35dffb4c23abb74, 0x429db2591f54aade,
0xc52802a8037d1009, 0x6acb27381f0b25f3, 0xf45e2551ee4f823b, 0x8b0ea2d99580c2f7,
0x3bed519cbcb4e1e1, 0xff452823dbb010a, 0x9d42ed614f3dd267, 0x5b9313c06257c57b,
0xa114b8008b5e1442, 0xc1fe311c11c13d4b, 0x66e8763ea34c5568, 0x8b982af1c262f05d,
0xee8876faaa75fbb7, 0x8a62a4d0d172bb2a, 0xc13d94a3b7449a97, 0x6dbbba9dc15d037c,
0xc786101f1d92e0f1, 0xd78681a907a0b79b, 0xf61aaf2962c9abb9, 0x2cfd16fcd3cb7ad9,
0x868c5b6744624d21, 0x25e650899c74ddd7, 0xba042af4a7c37463, 0x4eb1a539465a3eca,
0xbe09dbf03b05d5ca, 0x774e5a362b5472ba, 0x47a1221229d183cd, 0x504b0ca18ef5a2df,
0xdffbdfbde2456eb9, 0x46cd2b2fbee34634, 0xf2aef8fe819d98c3, 0x357f5276d4599d61,
0x24a5483879c453e3, 0x88026889192b4b9, 0x28da96671782dbec, 0x4ef37c40588e9aaa,
0x8837b90651bc9fb3, 0xc164f741d3f0e5d6, 0xbc135a0a704b70ba, 0x69cd868f7622ada,
0xbc37ba89e0b9c0ab, 0x47c14a01323552f6, 0x4f00794bacee98bb, 0x7107de7d637a69d5,
0x88af793bb6f2255e, 0xf3c6466b8799b598, 0xc288c616aa7f3b59, 0x81ca63cf42fca3fd,
0x88d85ace36a2674b, 0xd056bd3792389e7, 0xe55c396c4e9dd32d, 0xbefb504571e6c0a6,
0x96ab32115e91e8cc, 0xbf8acb18de8f38d1, 0x66dae58801672606, 0x833b6017872317fb,
0xb87c16f2d1c92864, 0xdb766a74e58b669c, 0x89659f85c61417be, 0xc8daad856011ea0c,
0x76a4b565b6fe7eae, 0xa469d085f6237312, 0xaaf0365683a3e96c, 0x4dbb746f8424f7b8,
0x638755af4e4acc1, 0x3d7807f5bde64486, 0x17be6d8f5bbb7639, 0x903f0cd44dc35dc,
0x67b672eafdf1196c, 0xa676ff93ed4c82f1, 0x521d1004c5053d9d, 0x37ba9ad09ccc9202,
0x84e54d297aacfb51, 0xa0b4b776a143445, 0x820d471e20b348e, 0x1874383cb83d46dc,
0x97edeec7a1efe11c, 0xb330e50b1bdc42aa, 0x1dd91955ce70e032, 0xa514cdb88f2939d5,
0x2791233fd90db9d3, 0x7b670a4cc50f7a9b, 0x77c07d2a05c6dfa5, 0xe3778b6646d0a6fa,
0xb39c8eda47b56749, 0x933ed448addbef28, 0xaf846af6ab7d0bf4, 0xe5af208eb666e49,
0x5e6622f73534cd6a, 0x297daeca42ef5b6e, 0x862daef3d35539a6, 0xe68722498f8e1ea9,
0x981c53093dc0d572, 0xfa09b0bfbf86fbf5, 0x30b1e96166219f15, 0x70e7d466bdc4fb83,
0x5a66736e35f2a8e9, 0xcddb59d2b7c1baef, 0xd6c7d247d26d8996, 0xea4e39eac8de1ba3,
0x539c8bb19fa3aff2, 0x9f90e4c5fd508d8, 0xa34e5956fbaf3385, 0x2e2f8e151d3ef375,
0x173691e9b83faec1, 0xb85a8d56bf016379, 0x8382381267408ae3, 0xb90f901bbdc0096d,
0x7c6ad32933bcec65, 0x76bb5e2f2c8ad595, 0x390f851a6cf46d28, 0xc3e6064da1c2da72,
0xc52a0c101cfa5389, 0xd78eaf84a3fbc530, 0x3781b9e2288b997e, 0x73c2f6dea83d05c4,
0x4228e364c5b5ed7, 0x9d7a3edf0da43911, 0x8edcfeda24686756, 0x5e7667a7b7a9b3a1,
0x4c4f389fa143791d, 0xb08bc1023da7cddc, 0x7ab4be3ae529b1cc, 0x754e6132dbe74ff9,
0x71635442a839df45, 0x2f6fb1643fbe52de, 0x961e0a42cf7a8177, 0xf3b45d83d89ef2ea,
0xee3de4cf4a6e3e9b, 0xcd6848542c3295e7, 0xe4cee1664c78662f, 0x9947548b474c68c4,
0x25d73777a5ed8b0b, 0xc915b1d636b7fc, 0x21c2ba75d9b0d2da, 0x5f6b5dcf608a64a1,
0xdcf333255ff9570c, 0x633b922418ced4ee, 0xc136dde0b004b34a, 0x58cc83b05d4b2f5a,
0x5eb424dda28e42d2, 0x62df47369739cd98, 0xb4e0b42485e4ce17, 0x16e1f0c1f9a8d1e7,
0x8ec3916707560ebf, 0x62ba6e2df2cc9db3, 0xcbf9f4ff77d83a16, 0x78d9d7d07d2bbcc4,
0xef554ce1e02c41f4, 0x8d7581127eccf94d, 0xa9b53336cb3c8a05, 0x38c42c0bf45c4f91,
0x640893cdf4488863, 0x80ec34bc575ea568, 0x39f324f5b48eaa40, 0xe9d9ed1f8eff527f,
0x9224fc058cc5a214, 0xbaba00b04cfe7741, 0x309a9f120fcf52af, 0xa558f3ec65626212,
0x424bec8b7adabe2f, 0x41622513a6aea433, 0xb88da2d5324ca798, 0xd287733b245528a4,
0x9a44697e6d68aec3, 0x7b1093be2f49bb28, 0x50bbec632e3d8aad, 0x6cd90723e1ea8283,
0x897b9e7431b02bf3, 0x219efdcb338a7047, 0x3b0311f0a27c0656, 0xdb17bf91c0db96e7,
0x8cd4fd6b4e85a5b2, 0xfab071054ba6409d, 0x40d6fe831fa9dfd9, 0xaf358debad7d791e,
0xeb8d0e25a65e3e58, 0xbbcbd3df14e08580, 0xcf751f27ecdab2b, 0x2b4da14f2613d8f4,
];
const LDM_BATCH_SIZE: usize = 64;
const LDM_MAX_CHUNK_SIZE: usize = 1 << 20;
const HASH_READ_SIZE: usize = 8;
#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
struct LdmEntry {
offset: u32,
checksum: u32,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub(crate) struct RawSequence {
pub(crate) literal_length: u32,
pub(crate) match_length: u32,
pub(crate) offset: u32,
}
#[derive(Debug, Clone)]
pub(crate) struct RawSequenceCursor<'a> {
sequences: &'a [RawSequence],
index: usize,
offset_in_sequence: u32,
}
impl<'a> RawSequenceCursor<'a> {
pub(crate) fn new(sequences: &'a [RawSequence]) -> Self {
Self {
sequences,
index: 0,
offset_in_sequence: 0,
}
}
pub(crate) fn current(&self) -> Option<RawSequence> {
self.sequences.get(self.index).copied()
}
pub(crate) fn offset_in_sequence(&self) -> u32 {
self.offset_in_sequence
}
pub(crate) fn skip_bytes(&mut self, bytes: usize) {
let mut remaining = self.offset_in_sequence as usize + bytes;
while remaining > 0 {
let Some(sequence) = self.sequences.get(self.index) else {
break;
};
let span = (sequence.literal_length + sequence.match_length) as usize;
if remaining < span {
self.offset_in_sequence = remaining as u32;
return;
}
remaining -= span;
self.index += 1;
}
self.offset_in_sequence = 0;
}
}
#[derive(Debug, Clone, Copy)]
struct BucketMatch {
match_pos: usize,
forward: usize,
backward: usize,
}
impl BucketMatch {
fn total(self) -> usize {
self.forward + self.backward
}
}
#[derive(Debug, Clone, Copy)]
struct GearHash {
rolling: u64,
stop_mask: u64,
}
impl GearHash {
fn new(params: LdmParameters) -> Self {
let max_bits_in_mask = params.min_match_length.min(64);
let rate = params.hash_rate_log;
let stop_mask = if rate > 0 && rate <= max_bits_in_mask {
((1u64 << rate) - 1) << (max_bits_in_mask - rate)
} else {
(1u64 << rate) - 1
};
Self {
rolling: u64::from(u32::MAX),
stop_mask,
}
}
const fn upstream_reset_is_a_noop() {}
fn feed(&mut self, data: &[u8], splits: &mut Vec<usize>) -> usize {
let mut hash = self.rolling;
let mask = self.stop_mask;
let mut n = 0usize;
while n < data.len() {
hash = (hash << 1).wrapping_add(GEAR_TAB[usize::from(data[n])]);
n += 1;
if hash & mask == 0 {
splits.push(n);
if splits.len() == LDM_BATCH_SIZE {
break;
}
}
}
self.rolling = hash;
n
}
}
#[derive(Debug, Clone)]
pub(crate) struct LdmTable {
entries: Vec<LdmEntry>,
bucket_cursors: Vec<u8>,
bucket_size_log: u32,
hash_bits: u32,
}
const MAX_HASH_LOG: u32 = max_table_log(size_of::<LdmEntry>());
impl LdmTable {
fn geometry(params: LdmParameters) -> (u32, u32) {
let hash_log = params.hash_log.min(MAX_HASH_LOG);
(hash_log, params.bucket_size_log.min(hash_log))
}
pub(crate) fn new(params: LdmParameters) -> Self {
let (hash_log, bucket_size_log) = Self::geometry(params);
let hash_bits = hash_log - bucket_size_log;
Self {
entries: vec![LdmEntry::default(); 1usize << hash_log],
bucket_cursors: vec![0u8; 1usize << hash_bits],
bucket_size_log,
hash_bits,
}
}
fn bucket(&self, hash: u32) -> &[LdmEntry] {
let start = (hash as usize) << self.bucket_size_log;
&self.entries[start..start + (1usize << self.bucket_size_log)]
}
fn reduce(&mut self, reducer: u32) {
for entry in &mut self.entries {
entry.offset = entry.offset.saturating_sub(reducer);
}
}
fn insert(&mut self, hash: u32, entry: LdmEntry) {
let cursor = &mut self.bucket_cursors[hash as usize];
let slot = ((hash as usize) << self.bucket_size_log) + usize::from(*cursor);
self.entries[slot] = entry;
*cursor = ((usize::from(*cursor) + 1) & ((1usize << self.bucket_size_log) - 1)) as u8;
}
}
#[derive(Debug, Clone, Copy)]
pub(crate) struct LdmSource<'a> {
dictionary: &'a [u8],
frame: &'a [u8],
}
impl<'a> LdmSource<'a> {
pub(crate) fn contiguous(frame: &'a [u8]) -> Self {
Self {
dictionary: &[],
frame,
}
}
pub(crate) fn with_dictionary(dictionary: &'a [u8], frame: &'a [u8]) -> Self {
Self { dictionary, frame }
}
pub(crate) fn frame_start(&self) -> usize {
self.dictionary.len()
}
pub(crate) fn len(&self) -> usize {
self.dictionary.len() + self.frame.len()
}
fn byte(&self, pos: usize) -> u8 {
match pos.checked_sub(self.dictionary.len()) {
Some(in_frame) => self.frame[in_frame],
None => self.dictionary[pos],
}
}
fn frame_range(&self, from: usize, to: usize) -> &'a [u8] {
&self.frame[from - self.dictionary.len()..to - self.dictionary.len()]
}
fn count_forwards(&self, pos: usize, match_pos: usize, end: usize) -> usize {
let frame_start = self.frame_start();
if match_pos >= frame_start {
let (pos, match_pos, end) = (
pos - frame_start,
match_pos - frame_start,
end - frame_start,
);
let mut count = 0usize;
while pos + count < end && self.frame[pos + count] == self.frame[match_pos + count] {
count += 1;
}
return count;
}
let mut count = 0usize;
while pos + count < end && self.byte(pos + count) == self.byte(match_pos + count) {
count += 1;
}
count
}
fn count_backwards(
&self,
pos: usize,
anchor: usize,
match_pos: usize,
window_low: usize,
) -> usize {
let mut count = 0usize;
if window_low >= self.frame_start() {
let frame_start = self.frame_start();
let (pos, anchor, match_pos, window_low) = (
pos - frame_start,
anchor - frame_start,
match_pos - frame_start,
window_low - frame_start,
);
while pos - count > anchor
&& match_pos - count > window_low
&& self.frame[pos - count - 1] == self.frame[match_pos - count - 1]
{
count += 1;
}
return count;
}
while pos - count > anchor
&& match_pos - count > window_low
&& self.byte(pos - count - 1) == self.byte(match_pos - count - 1)
{
count += 1;
}
count
}
}
#[derive(Debug, Clone)]
pub(crate) struct LdmState {
table: LdmTable,
params: LdmParameters,
loaded_dict_end: usize,
}
impl LdmState {
pub(crate) fn new(params: LdmParameters) -> Self {
Self {
table: LdmTable::new(params),
params,
loaded_dict_end: 0,
}
}
pub(crate) fn fill_from_dictionary(&mut self, dictionary: &[u8]) {
let min_match = self.params.min_match_length as usize;
let hash_mask = (1u32 << self.table.hash_bits).wrapping_sub(1);
let mut hash = GearHash::new(self.params);
let mut ip = 0usize;
let mut splits: Vec<usize> = Vec::with_capacity(LDM_BATCH_SIZE);
while ip < dictionary.len() {
splits.clear();
let hashed = hash.feed(&dictionary[ip..], &mut splits);
for &split_offset in &splits {
if ip + split_offset < min_match {
continue;
}
let split = ip + split_offset - min_match;
let xxhash = crate::xxhash::xxh64(&dictionary[split..split + min_match], 0);
self.table.insert(
(xxhash as u32) & hash_mask,
LdmEntry {
offset: split as u32,
checksum: (xxhash >> 32) as u32,
},
);
}
ip += hashed;
}
self.loaded_dict_end = dictionary.len();
}
pub(crate) fn parameters(&self) -> LdmParameters {
self.params
}
pub(crate) fn shift_positions(&mut self, dropped: usize) {
self.table.reduce(
u32::try_from(dropped).expect("a buffer this encoder can hold is addressable in u32"),
);
self.loaded_dict_end = 0;
}
fn generate_into(
&mut self,
src: LdmSource<'_>,
start: usize,
end: usize,
window_low: usize,
out: &mut Vec<RawSequence>,
) -> usize {
let min_match = self.params.min_match_length as usize;
let entries_per_bucket = 1usize << self.table.bucket_size_log;
let hash_mask = (1u32 << self.table.hash_bits).wrapping_sub(1);
if end.saturating_sub(start) < min_match {
return end.saturating_sub(start);
}
let mut anchor = start;
let mut ip = start;
let mut hash = GearHash::new(self.params);
GearHash::upstream_reset_is_a_noop();
ip += min_match;
let limit = end.saturating_sub(HASH_READ_SIZE);
let mut splits: Vec<usize> = Vec::with_capacity(LDM_BATCH_SIZE);
while ip < limit {
splits.clear();
let hashed = hash.feed(src.frame_range(ip, limit), &mut splits);
let mut restart = None;
for &split_offset in &splits {
let split = ip + split_offset - min_match;
let xxhash = crate::xxhash::xxh64(src.frame_range(split, split + min_match), 0);
let bucket_hash = (xxhash as u32) & hash_mask;
let checksum = (xxhash >> 32) as u32;
let new_entry = LdmEntry {
offset: split as u32,
checksum,
};
if split < anchor {
self.table.insert(bucket_hash, new_entry);
continue;
}
let mut best: Option<BucketMatch> = None;
for index in 0..entries_per_bucket {
let candidate = self.table.bucket(bucket_hash)[index];
if candidate.checksum != checksum || (candidate.offset as usize) <= window_low {
continue;
}
let match_pos = candidate.offset as usize;
debug_assert!(
match_pos < split,
"a long-distance table entry outlived the buffer it names"
);
let forward = src.count_forwards(split, match_pos, end);
if forward < min_match {
continue;
}
let backward = src.count_backwards(split, anchor, match_pos, window_low);
if best.is_none_or(|best| forward + backward > best.total()) {
best = Some(BucketMatch {
match_pos,
forward,
backward,
});
}
}
let Some(BucketMatch {
match_pos,
forward,
backward,
}) = best
else {
self.table.insert(bucket_hash, new_entry);
continue;
};
out.push(RawSequence {
literal_length: (split - backward - anchor) as u32,
match_length: (forward + backward) as u32,
offset: (split - match_pos) as u32,
});
self.table.insert(bucket_hash, new_entry);
anchor = split + forward;
if anchor > ip + hashed {
GearHash::upstream_reset_is_a_noop();
restart = Some(anchor - hashed);
break;
}
}
ip = restart.unwrap_or(ip) + hashed;
}
end - anchor
}
pub(crate) fn generate_sequences(
&mut self,
src: LdmSource<'_>,
start: usize,
end: usize,
max_distance: usize,
out: &mut Vec<RawSequence>,
) {
let mut leftover_literals = 0u32;
let mut chunk_start = start;
while chunk_start < end {
let chunk_end = (chunk_start + LDM_MAX_CHUNK_SIZE).min(end);
let window_low = if chunk_end > max_distance + self.loaded_dict_end {
self.loaded_dict_end = 0;
chunk_end - max_distance
} else {
0
};
let before = out.len();
let leftover = self.generate_into(src, chunk_start, chunk_end, window_low, out);
if out.len() > before {
out[before].literal_length += leftover_literals;
leftover_literals = leftover as u32;
} else {
leftover_literals += (chunk_end - chunk_start) as u32;
}
chunk_start = chunk_end;
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn no_ldm_hash_log_in_range_asks_for_a_table_past_the_address_space() {
for hash_log in 6..=30u32 {
let (built, bucket_size_log) = LdmTable::geometry(LdmParameters {
window_log: 27,
hash_log,
min_match_length: 64,
bucket_size_log: 3,
hash_rate_log: 0,
});
assert_eq!(built, hash_log.min(MAX_HASH_LOG));
assert!(bucket_size_log <= built);
let bytes = (1usize << built).checked_mul(size_of::<LdmEntry>());
assert!(
bytes.is_some_and(|bytes| bytes <= isize::MAX as usize),
"ldm_hash_log {hash_log} sizes the table past isize::MAX"
);
}
}
#[cfg(target_pointer_width = "32")]
#[test]
fn a_wide_ldm_hash_log_encodes_instead_of_aborting() {
let options = crate::EncoderOptions {
compression_level: crate::CompressionLevel::try_new(3).unwrap(),
parameters: crate::ParameterOverrides {
long_distance_matching: LdmMode::Enabled,
ldm_hash_log: Some(28),
..Default::default()
},
..Default::default()
};
let input = b"a wide ldm hash log encodes a wide ldm hash log encodes";
let encoded = crate::encode_all_with_options(input, options).unwrap();
assert_eq!(crate::decode_all(&encoded).unwrap(), input);
}
#[test]
fn the_hash_rate_falls_in_steps_of_three_strategies() {
let rate = |strategy| {
LdmParameters::resolve(LdmParameterOverrides::default(), strategy, 27).hash_rate_log
};
assert_eq!(rate(UpstreamStrategy::Fast), 7);
assert_eq!(rate(UpstreamStrategy::DoubleFast), 7);
assert_eq!(rate(UpstreamStrategy::Greedy), 6);
assert_eq!(rate(UpstreamStrategy::Lazy2), 6);
assert_eq!(rate(UpstreamStrategy::BinaryTreeLazy2), 5);
assert_eq!(rate(UpstreamStrategy::BinaryTreeUltra), 5);
assert_eq!(rate(UpstreamStrategy::BinaryTreeUltra2), 4);
}
#[test]
fn a_supplied_hash_log_derives_the_rate_from_the_window() {
let resolved = LdmParameters::resolve(
LdmParameterOverrides {
hash_log: Some(20),
..LdmParameterOverrides::default()
},
UpstreamStrategy::Fast,
27,
);
assert_eq!(resolved.hash_log, 20);
assert_eq!(resolved.hash_rate_log, 27 - 20);
}
#[test]
fn a_hash_log_wider_than_the_window_leaves_the_rate_at_zero() {
let resolved = LdmParameters::resolve(
LdmParameterOverrides {
hash_log: Some(27),
..LdmParameterOverrides::default()
},
UpstreamStrategy::Fast,
27,
);
assert_eq!(resolved.hash_rate_log, 0);
}
#[test]
fn the_minimum_match_halves_from_btultra_up() {
let min_match = |strategy| {
LdmParameters::resolve(LdmParameterOverrides::default(), strategy, 27).min_match_length
};
assert_eq!(min_match(UpstreamStrategy::BinaryTreeOpt), 64);
assert_eq!(min_match(UpstreamStrategy::BinaryTreeUltra), 32);
assert_eq!(min_match(UpstreamStrategy::BinaryTreeUltra2), 32);
}
#[test]
fn the_bucket_size_is_clamped_into_four_to_eight() {
let bucket = |strategy| {
LdmParameters::resolve(LdmParameterOverrides::default(), strategy, 27).bucket_size_log
};
assert_eq!(bucket(UpstreamStrategy::Fast), 4);
assert_eq!(bucket(UpstreamStrategy::Lazy), 4);
assert_eq!(bucket(UpstreamStrategy::Lazy2), 5);
assert_eq!(bucket(UpstreamStrategy::BinaryTreeUltra2), 8);
}
#[test]
fn the_hash_log_caps_even_a_supplied_bucket_size() {
let resolved = LdmParameters::resolve(
LdmParameterOverrides {
hash_log: Some(6),
bucket_size_log: Some(8),
..LdmParameterOverrides::default()
},
UpstreamStrategy::BinaryTreeUltra2,
27,
);
assert_eq!(resolved.hash_log, 6);
assert_eq!(
resolved.bucket_size_log, 6,
"the cap applies to a supplied value"
);
}
#[test]
fn the_auto_rule_needs_both_a_wide_window_and_an_optimal_strategy() {
use UpstreamStrategy::{BinaryTreeLazy2, BinaryTreeOpt, BinaryTreeUltra2};
assert!(resolve_enable_ldm(LdmMode::Auto, BinaryTreeOpt, 27));
assert!(resolve_enable_ldm(LdmMode::Auto, BinaryTreeUltra2, 27));
assert!(!resolve_enable_ldm(LdmMode::Auto, BinaryTreeUltra2, 26));
assert!(!resolve_enable_ldm(LdmMode::Auto, BinaryTreeLazy2, 27));
}
#[test]
fn the_explicit_modes_ignore_the_parameters() {
for window_log in [10u32, 27] {
for strategy in [UpstreamStrategy::Fast, UpstreamStrategy::BinaryTreeUltra2] {
assert!(resolve_enable_ldm(LdmMode::Enabled, strategy, window_log));
assert!(!resolve_enable_ldm(LdmMode::Disabled, strategy, window_log));
}
}
}
#[test]
fn only_an_explicit_enable_pins_the_window() {
assert_eq!(force_window_log(LdmMode::Enabled, 10), 27);
assert_eq!(force_window_log(LdmMode::Enabled, 27), 27);
assert_eq!(force_window_log(LdmMode::Auto, 10), 10);
assert_eq!(force_window_log(LdmMode::Disabled, 10), 10);
}
}
#[cfg(test)]
#[test]
#[ignore]
fn print_resolution_grid() {
const WINDOWS: [u32; 4] = [10, 15, 20, 27];
const HASH_LOGS: [u32; 4] = [0, 6, 20, 27];
const BUCKETS: [u32; 4] = [0, 1, 4, 8];
const RATES: [u32; 3] = [0, 3, 7];
const MIN_MATCH: [u32; 3] = [0, 4, 4096];
const STRATEGIES: [UpstreamStrategy; 9] = [
UpstreamStrategy::Fast,
UpstreamStrategy::DoubleFast,
UpstreamStrategy::Greedy,
UpstreamStrategy::Lazy,
UpstreamStrategy::Lazy2,
UpstreamStrategy::BinaryTreeLazy2,
UpstreamStrategy::BinaryTreeOpt,
UpstreamStrategy::BinaryTreeUltra,
UpstreamStrategy::BinaryTreeUltra2,
];
for strategy in STRATEGIES {
for window_log in WINDOWS {
for hash_log in HASH_LOGS {
for bucket_size_log in BUCKETS {
for hash_rate_log in RATES {
for min_match_length in MIN_MATCH {
let resolved = LdmParameters::resolve(
LdmParameterOverrides {
hash_log: Some(hash_log),
min_match_length: Some(min_match_length),
bucket_size_log: Some(bucket_size_log),
hash_rate_log: Some(hash_rate_log),
},
strategy,
window_log,
);
println!(
"{},{window_log},{hash_log},{bucket_size_log},{hash_rate_log},\
{min_match_length},{},{},{},{}",
strategy.as_upstream_code(),
resolved.hash_log,
resolved.min_match_length,
resolved.bucket_size_log,
resolved.hash_rate_log,
);
}
}
}
}
}
}
}
#[cfg(test)]
mod matcher_tests {
use super::*;
fn params_for(strategy: UpstreamStrategy, window_log: u32) -> LdmParameters {
LdmParameters::resolve(LdmParameterOverrides::default(), strategy, window_log)
}
fn filler(len: usize, seed: u64) -> Vec<u8> {
let mut out = Vec::with_capacity(len);
let mut state = seed | 1;
while out.len() < len {
state ^= state << 13;
state ^= state >> 7;
state ^= state << 17;
out.extend_from_slice(&state.to_le_bytes());
}
out.truncate(len);
out
}
fn assert_sequences_are_real(src: &[u8], sequences: &[RawSequence], window_log: u32) {
let mut pos = 0usize;
for (index, seq) in sequences.iter().enumerate() {
pos += seq.literal_length as usize;
let offset = seq.offset as usize;
let length = seq.match_length as usize;
assert!(offset > 0, "sequence {index} has a zero offset");
assert!(
offset <= pos,
"sequence {index}: offset {offset} reaches before the frame at {pos}"
);
assert!(
offset <= 1usize << window_log,
"sequence {index}: offset {offset} exceeds the {} window",
1usize << window_log
);
assert!(
pos + length <= src.len(),
"sequence {index} runs past the input"
);
for k in 0..length {
assert_eq!(
src[pos + k],
src[pos - offset + k],
"sequence {index} byte {k}: not a real match"
);
}
pos += length;
}
}
#[test]
fn a_repeat_far_past_a_block_is_found() {
const GAP: usize = 3 << 20;
let planted = filler(1 << 16, 0x5EED);
let mut src = planted.clone();
src.extend_from_slice(&filler(GAP, 0xA11CE));
src.extend_from_slice(&planted);
let params = params_for(UpstreamStrategy::BinaryTreeUltra2, 27);
let mut state = LdmState::new(params);
let mut sequences = Vec::new();
state.generate_sequences(
LdmSource::contiguous(&src),
0,
src.len(),
1 << params.window_log,
&mut sequences,
);
assert!(
!sequences.is_empty(),
"no long-distance match found across a {GAP}-byte gap"
);
assert_sequences_are_real(&src, &sequences, params.window_log);
let longest = sequences.iter().map(|s| s.match_length).max().unwrap() as usize;
assert!(
longest >= planted.len(),
"longest match {longest} does not cover the {}-byte planted repeat",
planted.len()
);
let far = sequences
.iter()
.filter(|s| s.offset as usize > 1 << 20)
.count();
assert!(far > 0, "no sequence reached past a megabyte");
}
fn generate_with_dictionary(
dictionary: &[u8],
frame: &[u8],
strategy: UpstreamStrategy,
window_log: u32,
) -> (Vec<RawSequence>, Vec<u8>) {
let params = params_for(strategy, window_log);
let mut state = LdmState::new(params);
state.fill_from_dictionary(dictionary);
let mut sequences = Vec::new();
state.generate_sequences(
LdmSource::with_dictionary(dictionary, frame),
dictionary.len(),
dictionary.len() + frame.len(),
1 << params.window_log,
&mut sequences,
);
let mut joint = dictionary.to_vec();
joint.extend_from_slice(frame);
(sequences, joint)
}
fn assert_sequences_are_real_across(joint: &[u8], from: usize, sequences: &[RawSequence]) {
let mut pos = from;
for (index, seq) in sequences.iter().enumerate() {
pos += seq.literal_length as usize;
let (offset, length) = (seq.offset as usize, seq.match_length as usize);
assert!(
offset <= pos,
"sequence {index}: offset {offset} reaches before the dictionary at {pos}"
);
assert!(
pos + length <= joint.len(),
"sequence {index} runs past the joint buffer"
);
for k in 0..length {
assert_eq!(
joint[pos + k],
joint[pos - offset + k],
"sequence {index} byte {k}: not a real match"
);
}
pos += length;
}
}
#[test]
fn a_match_is_found_in_the_dictionary() {
let planted = filler(1 << 16, 0x5EED);
let mut dictionary = planted.clone();
dictionary.extend_from_slice(&filler(1 << 16, 0x0DDBA11));
let mut frame = filler(1 << 19, 0xA11CE);
frame.extend_from_slice(&planted);
let (sequences, joint) =
generate_with_dictionary(&dictionary, &frame, UpstreamStrategy::BinaryTreeUltra2, 27);
assert!(!sequences.is_empty(), "no match found in the dictionary");
assert_sequences_are_real_across(&joint, dictionary.len(), &sequences);
let into_dictionary = sequences
.iter()
.filter(|seq| seq.offset as usize > frame.len() - planted.len())
.count();
assert!(
into_dictionary > 0,
"every match stayed inside the frame; the dictionary was never searched"
);
}
#[test]
fn a_match_runs_from_the_dictionary_into_the_frame() {
let planted = filler(1 << 16, 0xC0FFEE);
let mut dictionary = filler(1 << 16, 0xBEEF);
dictionary.extend_from_slice(&planted);
let mut frame = planted.clone();
frame.extend_from_slice(&filler(1 << 19, 0xA11CE));
frame.extend_from_slice(&planted);
frame.extend_from_slice(&planted);
let (sequences, joint) =
generate_with_dictionary(&dictionary, &frame, UpstreamStrategy::BinaryTreeUltra2, 27);
assert!(!sequences.is_empty(), "no match found");
assert_sequences_are_real_across(&joint, dictionary.len(), &sequences);
let mut position = dictionary.len();
let mut crossing = false;
for seq in &sequences {
position += seq.literal_length as usize;
let match_start = position - seq.offset as usize;
crossing |= match_start < dictionary.len()
&& match_start + seq.match_length as usize > dictionary.len();
position += seq.match_length as usize;
}
assert!(
crossing,
"no match crossed the dictionary boundary, so the joining is untested"
);
}
#[test]
fn the_dictionary_stops_being_reachable_once_the_frame_outgrows_the_window() {
const WINDOW_LOG: u32 = 18;
let planted = filler(1 << 16, 0x5EED);
let dictionary = planted.clone();
let mut early = filler(1 << 15, 0xA11CE);
early.extend_from_slice(&planted);
let (found_early, joint) = generate_with_dictionary(
&dictionary,
&early,
UpstreamStrategy::BinaryTreeUltra2,
WINDOW_LOG,
);
assert_sequences_are_real_across(&joint, dictionary.len(), &found_early);
assert!(
!found_early.is_empty(),
"the dictionary was unreachable while it still held its credit"
);
let mut late = filler(3 << WINDOW_LOG, 0xA11CE);
late.extend_from_slice(&planted);
let (found_late, joint) = generate_with_dictionary(
&dictionary,
&late,
UpstreamStrategy::BinaryTreeUltra2,
WINDOW_LOG,
);
assert_sequences_are_real_across(&joint, dictionary.len(), &found_late);
assert!(
found_late.is_empty(),
"the dictionary was still reachable {} bytes into a {} window",
late.len(),
1usize << WINDOW_LOG
);
}
#[test]
fn filling_from_a_dictionary_is_not_the_walk_generation_makes() {
let bytes = filler(1 << 18, 0x1234);
let params = params_for(UpstreamStrategy::BinaryTreeUltra2, 27);
let mut filled = LdmState::new(params);
filled.fill_from_dictionary(&bytes);
let mut generated = LdmState::new(params);
let mut sequences = Vec::new();
generated.generate_sequences(
LdmSource::contiguous(&bytes),
0,
bytes.len(),
1 << params.window_log,
&mut sequences,
);
assert_ne!(
filled.table.entries, generated.table.entries,
"the two walks filed the same positions, so one of them is not what it claims"
);
}
#[test]
fn unrepeating_input_yields_no_sequences() {
let src = filler(1 << 20, 0xD1CE);
let params = params_for(UpstreamStrategy::BinaryTreeUltra2, 27);
let mut state = LdmState::new(params);
let mut sequences = Vec::new();
state.generate_sequences(
LdmSource::contiguous(&src),
0,
src.len(),
1 << params.window_log,
&mut sequences,
);
assert!(
sequences.is_empty(),
"found {} matches in unrepeating input",
sequences.len()
);
}
#[test]
fn a_repeat_further_than_the_window_is_not_reported() {
const WINDOW_LOG: u32 = 20;
let planted = filler(1 << 16, 0x5EED);
let mut src = planted.clone();
src.extend_from_slice(&filler(3 << 20, 0xA11CE));
src.extend_from_slice(&planted);
let params = params_for(UpstreamStrategy::BinaryTreeUltra2, WINDOW_LOG);
let mut state = LdmState::new(params);
let mut sequences = Vec::new();
state.generate_sequences(
LdmSource::contiguous(&src),
0,
src.len(),
1 << params.window_log,
&mut sequences,
);
assert_sequences_are_real(&src, &sequences, WINDOW_LOG);
}
#[test]
fn a_single_repeated_byte_terminates() {
let src = vec![0u8; 1 << 20];
let params = params_for(UpstreamStrategy::BinaryTreeUltra2, 27);
let mut state = LdmState::new(params);
let mut sequences = Vec::new();
state.generate_sequences(
LdmSource::contiguous(&src),
0,
src.len(),
1 << params.window_log,
&mut sequences,
);
assert_sequences_are_real(&src, &sequences, params.window_log);
}
#[test]
fn per_block_calls_find_the_same_matches_as_one_call() {
let planted = filler(1 << 15, 0x5EED);
let mut src = planted.clone();
src.extend_from_slice(&filler(1 << 19, 0xA11CE));
src.extend_from_slice(&planted);
let params = params_for(UpstreamStrategy::BinaryTreeUltra2, 27);
const BLOCK: usize = 128 << 10;
let mut whole = Vec::new();
LdmState::new(params).generate_sequences(
LdmSource::contiguous(&src),
0,
src.len(),
1 << params.window_log,
&mut whole,
);
assert!(!whole.is_empty(), "the planted repeat produced no match");
let mut blocked = Vec::new();
let mut state = LdmState::new(params);
let mut start = 0usize;
while start < src.len() {
let end = (start + BLOCK).min(src.len());
let mut block = Vec::new();
state.generate_sequences(
LdmSource::contiguous(&src),
start,
end,
1 << params.window_log,
&mut block,
);
let covered: usize = block
.iter()
.map(|seq: &RawSequence| (seq.literal_length + seq.match_length) as usize)
.sum();
assert!(
covered <= end - start,
"block [{start}, {end}) produced {covered} bytes of sequences"
);
let mut position = start;
for seq in &block {
position += seq.literal_length as usize;
blocked.push((position, seq.match_length, seq.offset));
position += seq.match_length as usize;
}
start = end;
}
let mut position = 0usize;
let expected: Vec<_> = whole
.iter()
.map(|seq| {
position += seq.literal_length as usize;
let at = position;
position += seq.match_length as usize;
(at, seq.match_length, seq.offset)
})
.collect();
assert_eq!(
expected, blocked,
"block-at-a-time generation found different matches"
);
}
}
#[cfg(test)]
#[test]
#[ignore]
fn print_sequences_for_corpus() {
let path = std::env::var("ZSTANDARD_LDM_CORPUS").expect("ZSTANDARD_LDM_CORPUS");
let window_log: u32 = std::env::var("ZSTANDARD_LDM_WINDOW_LOG")
.expect("ZSTANDARD_LDM_WINDOW_LOG")
.parse()
.expect("a window log");
let strategy_code: u32 = std::env::var("ZSTANDARD_LDM_STRATEGY")
.expect("ZSTANDARD_LDM_STRATEGY")
.parse()
.expect("a strategy code");
const STRATEGIES: [UpstreamStrategy; 9] = [
UpstreamStrategy::Fast,
UpstreamStrategy::DoubleFast,
UpstreamStrategy::Greedy,
UpstreamStrategy::Lazy,
UpstreamStrategy::Lazy2,
UpstreamStrategy::BinaryTreeLazy2,
UpstreamStrategy::BinaryTreeOpt,
UpstreamStrategy::BinaryTreeUltra,
UpstreamStrategy::BinaryTreeUltra2,
];
let strategy = STRATEGIES[(strategy_code - 1) as usize];
let src = std::fs::read(&path).expect("corpus");
let block_size: usize = std::env::var("ZSTANDARD_LDM_BLOCK_SIZE")
.ok()
.and_then(|value| value.parse().ok())
.filter(|&value| value != 0)
.unwrap_or(src.len());
let supplied = |name: &str| {
std::env::var(name)
.ok()
.map(|value| {
value
.parse::<u32>()
.unwrap_or_else(|_| panic!("{name} must be an integer, got {value:?}"))
})
.filter(|&value| value != 0)
};
let overrides = LdmParameterOverrides {
hash_log: supplied("ZSTANDARD_LDM_HASH_LOG"),
min_match_length: supplied("ZSTANDARD_LDM_MIN_MATCH"),
bucket_size_log: supplied("ZSTANDARD_LDM_BUCKET_SIZE_LOG"),
hash_rate_log: supplied("ZSTANDARD_LDM_HASH_RATE_LOG"),
};
let dict_size: usize = std::env::var("ZSTANDARD_LDM_DICT_SIZE")
.ok()
.and_then(|value| value.parse().ok())
.unwrap_or(0)
.min(src.len());
let (dictionary, frame) = src.split_at(dict_size);
let source = LdmSource::with_dictionary(dictionary, frame);
let params = LdmParameters::resolve(overrides, strategy, window_log);
let mut state = LdmState::new(params);
if dict_size > 0 {
state.fill_from_dictionary(dictionary);
}
let mut sequences = Vec::new();
let mut start = dict_size;
while start < src.len() {
let end = (start + block_size).min(src.len());
sequences.clear();
state.generate_sequences(source, start, end, 1 << params.window_log, &mut sequences);
for seq in &sequences {
println!(
"{},{},{},{}",
start, seq.literal_length, seq.match_length, seq.offset
);
}
start = end;
}
}
#[cfg(test)]
#[test]
#[ignore]
fn write_benchmark_corpus() {
#[path = "../support/corpora.rs"]
mod corpora;
let name = std::env::var("ZSTANDARD_LDM_CORPUS_NAME").expect("ZSTANDARD_LDM_CORPUS_NAME");
let out = std::env::var("ZSTANDARD_LDM_CORPUS_OUT").expect("ZSTANDARD_LDM_CORPUS_OUT");
let size: usize = std::env::var("ZSTANDARD_LDM_CORPUS_SIZE")
.ok()
.and_then(|value| value.parse().ok())
.unwrap_or(1 << 20);
let case = corpora::benchmark_report_cases(1 << 20)
.into_iter()
.find(|case| case.name == name)
.expect("a corpus by that name");
std::fs::write(&out, &case.input[..size.min(case.input.len())]).expect("write the corpus");
}