use crate::utils::security::{MAX_MATCH_LEN, MAX_OFFSET};
use crate::utils::simd;
pub const LDM_MIN_MATCH: usize = 64;
const SAMPLE_STEP: usize = 512;
const LDM_HASH_LOG: u32 = 14;
const LDM_HASH_SIZE: usize = 1 << LDM_HASH_LOG;
pub const LDM_MIN_BLOCK: usize = 256 * 1024;
pub const LDM_MIN_LEVEL: u8 = 5;
pub struct LdmTable {
table: Vec<u32>,
}
impl LdmTable {
pub fn new() -> Self {
Self {
table: vec![0u32; LDM_HASH_SIZE],
}
}
#[inline]
fn hash8(data: &[u8], pos: usize) -> usize {
if pos + 8 > data.len() {
return 0;
}
let lo = u32::from_le_bytes(data[pos..pos + 4].try_into().unwrap());
let hi = u32::from_le_bytes(data[pos + 4..pos + 8].try_into().unwrap());
let h = lo.wrapping_mul(0x9E37_79B1) ^ hi.wrapping_mul(0x85EB_CA77);
(h >> (32 - LDM_HASH_LOG)) as usize
}
pub fn seed(&mut self, data: &[u8], start: usize, end: usize) {
let end = end.min(data.len().saturating_sub(8));
let mut pos = start;
while pos < end {
let h = Self::hash8(data, pos);
self.table[h] = (pos as u32).wrapping_add(1);
pos += SAMPLE_STEP;
}
}
#[inline]
pub fn insert(&mut self, data: &[u8], pos: usize) {
if pos + 8 <= data.len() {
let h = Self::hash8(data, pos);
self.table[h] = (pos as u32).wrapping_add(1);
}
}
pub fn find(
&self,
data: &[u8],
pos: usize,
max_len: usize,
) -> Option<(usize, usize)> {
if pos + 8 > data.len() || max_len < LDM_MIN_MATCH {
return None;
}
let h = Self::hash8(data, pos);
let cand = self.table[h];
if cand == 0 {
return None;
}
let cpos = (cand as usize).wrapping_sub(1);
if cpos >= pos {
return None;
}
let offset = pos - cpos;
if offset == 0 || offset > MAX_OFFSET {
return None;
}
if pos + 8 > data.len() || cpos + 8 > data.len() {
return None;
}
if data[cpos..cpos + 8] != data[pos..pos + 8] {
return None;
}
let max_ml = max_len.min(MAX_MATCH_LEN);
let ml = 8 + simd::match_len(
&data[cpos + 8..],
&data[pos + 8..],
max_ml.saturating_sub(8),
);
if ml >= LDM_MIN_MATCH {
Some((offset, ml))
} else {
None
}
}
pub fn should_use(level: u8, block_len: usize) -> bool {
level >= LDM_MIN_LEVEL && block_len >= LDM_MIN_BLOCK
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn ldm_finds_distant_match() {
let pattern = b"LDM_LONG_DISTANCE_MATCH_TEST_PATTERN_AAABBBCCCDDDEEEFFF_1234567890ABCDEF!";
let gap_size = 1_000_000; let mut data = Vec::with_capacity(gap_size + pattern.len() * 2);
data.extend_from_slice(pattern);
let mut x = 0xDEAD_BEEFu32;
for _ in 0..gap_size {
x = x.wrapping_mul(1664525).wrapping_add(1013904223);
data.push((x >> 24) as u8);
}
data.extend_from_slice(pattern);
let mut ldm = LdmTable::new();
ldm.seed(&data, 0, data.len());
let repeat_pos = pattern.len() + gap_size;
let remain = data.len() - repeat_pos;
let result = ldm.find(&data, repeat_pos, remain);
assert!(
result.is_some(),
"LDM should find the distant pattern match"
);
let (offset, ml) = result.unwrap();
assert!(
ml >= LDM_MIN_MATCH,
"match length {ml} should be >= {LDM_MIN_MATCH}"
);
assert_eq!(
offset, gap_size + pattern.len(),
"offset should point back to pattern start"
);
}
#[test]
fn ldm_no_match_random() {
let mut data = Vec::with_capacity(100_000);
let mut x = 0xC0FFEEu32;
for _ in 0..100_000 {
x = x.wrapping_mul(1664525).wrapping_add(1013904223);
data.push((x >> 24) as u8);
}
let mut ldm = LdmTable::new();
ldm.seed(&data, 0, data.len());
let mut found = 0;
for pos in (50_000..90_000).step_by(512) {
if ldm.find(&data, pos, data.len() - pos).is_some() {
found += 1;
}
}
assert!(found < 3, "random data should have very few LDM matches, got {found}");
}
#[test]
fn ldm_activation_check() {
assert!(!LdmTable::should_use(4, 1_000_000));
assert!(!LdmTable::should_use(5, 100_000));
assert!(LdmTable::should_use(5, 300_000));
assert!(LdmTable::should_use(9, 1_000_000));
}
}