use alloc::vec::Vec;
use crate::utils::security::{MAX_MATCH_LEN, MAX_OFFSET};
use crate::utils::simd;
pub const LDM_MIN_MATCH: usize = 64;
pub const SAMPLE_STEP: usize = 512;
const LDM_HASH_LOG: u32 = 14;
const LDM_HASH_SIZE: usize = 1 << LDM_HASH_LOG;
const BUCKET_DEPTH: usize = 8;
pub const LDM_MIN_BLOCK: usize = 256 * 1024;
pub const LDM_MIN_LEVEL: u8 = 5;
pub struct LdmTable {
buckets: Vec<[u32; BUCKET_DEPTH]>,
}
impl Default for LdmTable {
fn default() -> Self {
Self::new()
}
}
impl LdmTable {
pub fn new() -> Self {
Self {
buckets: vec![[0u32; BUCKET_DEPTH]; 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 {
self.insert(data, pos);
pos += SAMPLE_STEP;
}
if end > start {
let last = end.saturating_sub(1);
let aligned = last.saturating_sub(last % SAMPLE_STEP);
if aligned >= start && aligned + 8 <= data.len() {
self.insert(data, aligned);
}
}
}
#[inline]
pub fn insert(&mut self, data: &[u8], pos: usize) {
if pos + 8 > data.len() {
return;
}
let h = Self::hash8(data, pos);
let bucket = &mut self.buckets[h];
let tag = (pos as u32).wrapping_add(1);
if bucket[0] == tag {
return;
}
let mut tmp = [0u32; BUCKET_DEPTH];
tmp[0] = tag;
let mut o = 1usize;
for &c in bucket.iter() {
if c == 0 || c == tag {
continue;
}
if o < BUCKET_DEPTH {
tmp[o] = c;
o += 1;
}
}
*bucket = tmp;
}
#[inline]
pub fn maybe_insert(&mut self, data: &[u8], pos: usize) {
if pos % SAMPLE_STEP == 0 {
self.insert(data, pos);
}
}
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 bucket = &self.buckets[h];
let mut best: Option<(usize, usize)> = None;
for &cand in bucket {
if cand == 0 {
break; }
let cpos = (cand as usize).wrapping_sub(1);
if cpos >= pos || cpos + 8 > data.len() {
continue;
}
let offset = pos - cpos;
if offset == 0 || offset > MAX_OFFSET {
continue;
}
if data[cpos..cpos + 8] != data[pos..pos + 8] {
continue;
}
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 {
let better = match best {
None => true,
Some((bo, bm)) => ml > bm || (ml == bm && offset < bo),
};
if better {
best = Some((offset, ml));
if ml >= 256 {
break;
}
}
}
}
best
}
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::*;
fn make_distant_pattern_data(gap_size: usize) -> (Vec<u8>, usize, usize) {
let pattern = b"LDM_LONG_DISTANCE_MATCH_TEST_PATTERN_AAABBBCCCDDDEEEFFF_1234567890ABCDEF!";
assert!(pattern.len() >= LDM_MIN_MATCH);
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 repeat_pos = pattern.len() + gap_size;
(data, pattern.len(), repeat_pos)
}
#[test]
fn ldm_finds_distant_match() {
let (data, _plen, repeat_pos) = make_distant_pattern_data(1_000_000);
let mut ldm = LdmTable::new();
ldm.seed(&data, 0, repeat_pos);
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, repeat_pos,
"offset should point back to pattern start"
);
assert_eq!(
&data[repeat_pos - offset..repeat_pos - offset + ml],
&data[repeat_pos..repeat_pos + ml]
);
}
#[test]
fn ldm_survives_hash_collisions_in_full_seed() {
let (data, _plen, repeat_pos) = make_distant_pattern_data(1_000_000);
let mut ldm = LdmTable::new();
ldm.seed(&data, 0, data.len());
let result = ldm.find(&data, repeat_pos, data.len() - repeat_pos);
assert!(
result.is_some(),
"bucket must recover match past hash collisions"
);
let (offset, ml) = result.unwrap();
assert!(ml >= LDM_MIN_MATCH);
assert_eq!(offset, repeat_pos);
}
#[test]
fn ldm_progressive_insert_finds_match() {
let pattern = b"PROG_LDM_PATTERN_XXXXXXXXYYYYYYYYZZZZZZZZ_0123456789ABCDEF_END_PAD!!";
assert!(pattern.len() >= LDM_MIN_MATCH);
let gap = 300_000usize;
let mut data = Vec::new();
data.extend_from_slice(pattern);
for i in 0..gap {
data.push((i.wrapping_mul(31) & 0xFF) as u8);
}
data.extend_from_slice(pattern);
let mut ldm = LdmTable::new();
let search_at = pattern.len() + gap;
let mut pos = 0usize;
while pos < search_at {
ldm.maybe_insert(&data, pos);
pos += 1;
}
ldm.insert(&data, 0);
let r = ldm.find(&data, search_at, pattern.len());
assert!(r.is_some());
let (off, ml) = r.unwrap();
assert!(ml >= LDM_MIN_MATCH);
assert_eq!(off, search_at);
}
#[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));
}
}