#[inline]
pub fn match_len(a: &[u8], b: &[u8], max: usize) -> usize {
let n = a.len().min(b.len()).min(max);
if n == 0 {
return 0;
}
match_len_inner(a, b, n)
}
#[inline]
fn match_len_inner(a: &[u8], b: &[u8], n: usize) -> usize {
let mut i = 0usize;
#[cfg(feature = "simd")]
while i + 32 <= n {
let x0 = read_u128(a, i);
let y0 = read_u128(b, i);
if x0 != y0 {
return i + first_diff_byte_u128(x0, y0);
}
let x1 = read_u128(a, i + 16);
let y1 = read_u128(b, i + 16);
if x1 != y1 {
return i + 16 + first_diff_byte_u128(x1, y1);
}
i += 32;
}
while i + 16 <= n {
let x = read_u128(a, i);
let y = read_u128(b, i);
if x != y {
return i + first_diff_byte_u128(x, y);
}
i += 16;
}
while i + 8 <= n {
let x = u64::from_le_bytes(a[i..i + 8].try_into().unwrap());
let y = u64::from_le_bytes(b[i..i + 8].try_into().unwrap());
if x != y {
return i + ((x ^ y).trailing_zeros() as usize / 8);
}
i += 8;
}
while i < n && a[i] == b[i] {
i += 1;
}
i
}
#[inline]
pub fn prefetch_read(_ptr: *const u8) {
let _ = _ptr;
}
#[inline]
fn read_u128(data: &[u8], pos: usize) -> u128 {
u128::from_le_bytes(data[pos..pos + 16].try_into().unwrap())
}
#[inline]
fn first_diff_byte_u128(x: u128, y: u128) -> usize {
((x ^ y).trailing_zeros() as usize) / 8
}
#[inline]
pub fn match4(a: &[u8], ap: usize, b: &[u8], bp: usize) -> bool {
u32::from_le_bytes(a[ap..ap + 4].try_into().unwrap())
== u32::from_le_bytes(b[bp..bp + 4].try_into().unwrap())
}
#[inline]
pub fn copy_match(dst: &mut Vec<u8>, offset: usize, len: usize) {
copy_match_with_history(dst, offset, len, &[]);
}
#[inline]
pub fn copy_match_with_history(dst: &mut Vec<u8>, offset: usize, len: usize, dict: &[u8]) {
debug_assert!(offset > 0);
let dlen = dict.len();
debug_assert!(offset <= dlen + dst.len());
if dict.is_empty() && offset == 1 && !dst.is_empty() {
let b = dst[dst.len() - 1];
dst.resize(dst.len() + len, b);
return;
}
if offset <= dst.len() && offset >= len {
let start = dst.len() - offset;
let chunk: Vec<u8> = dst[start..start + len].to_vec();
dst.extend_from_slice(&chunk);
return;
}
dst.reserve(len);
for _ in 0..len {
let from = dlen + dst.len() - offset;
let b = if from < dlen {
dict[from]
} else {
dst[from - dlen]
};
dst.push(b);
}
}
pub fn simd_enabled() -> bool {
cfg!(feature = "simd")
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn match_len_basic() {
let a = b"HelloHelloXXXX";
let b = b"HelloHelloYYYY";
assert_eq!(match_len(a, b, 100), 10);
}
#[test]
fn match_len_long() {
let a = vec![0xABu8; 1000];
let mut b = vec![0xABu8; 1000];
b[777] = 0x00;
assert_eq!(match_len(&a, &b, 1000), 777);
}
#[test]
fn copy_match_rle() {
let mut d = vec![0x41u8];
copy_match(&mut d, 1, 10);
assert_eq!(d, vec![0x41u8; 11]);
}
#[test]
fn copy_match_overlap() {
let mut d = vec![1, 2, 3, 4];
copy_match(&mut d, 3, 6); assert_eq!(&d[..4], &[1, 2, 3, 4]);
assert_eq!(d.len(), 10);
}
}