use alloc::vec::Vec;
#[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 {
#[cfg(all(target_arch = "x86_64", feature = "simd", feature = "std"))]
{
if std::is_x86_feature_detected!("avx2") {
return unsafe { arch_x86::match_len_avx2(a, b, n) };
}
}
#[cfg(all(target_arch = "x86_64", feature = "simd"))]
{
return unsafe { arch_x86::match_len_sse2(a, b, n) };
}
#[cfg(all(target_arch = "aarch64", feature = "simd"))]
{
return unsafe { arch_aarch64::match_len_neon(a, b, n) };
}
#[allow(unreachable_code)]
match_len_portable(a, b, n)
}
#[inline]
fn match_len_portable(a: &[u8], b: &[u8], n: usize) -> usize {
let mut i = 0usize;
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
}
#[cfg(all(target_arch = "x86_64", feature = "simd"))]
mod arch_x86 {
use super::match_len_portable;
use core::arch::x86_64::*;
#[cfg(feature = "std")]
#[target_feature(enable = "avx2")]
pub unsafe fn match_len_avx2(a: &[u8], b: &[u8], n: usize) -> usize {
let mut i = 0usize;
while i + 32 <= n {
let x = unsafe { _mm256_loadu_si256(a.as_ptr().add(i).cast()) };
let y = unsafe { _mm256_loadu_si256(b.as_ptr().add(i).cast()) };
let eq = _mm256_cmpeq_epi8(x, y);
let mask = _mm256_movemask_epi8(eq) as u32;
if mask != u32::MAX {
return i + (!mask).trailing_zeros() as usize;
}
i += 32;
}
i + match_len_portable(&a[i..], &b[i..], n - i)
}
#[target_feature(enable = "sse2")]
pub unsafe fn match_len_sse2(a: &[u8], b: &[u8], n: usize) -> usize {
let mut i = 0usize;
while i + 16 <= n {
let x = unsafe { _mm_loadu_si128(a.as_ptr().add(i).cast()) };
let y = unsafe { _mm_loadu_si128(b.as_ptr().add(i).cast()) };
let eq = _mm_cmpeq_epi8(x, y);
let mask = _mm_movemask_epi8(eq) as u32 & 0xFFFF;
if mask != 0xFFFF {
return i + (!mask & 0xFFFF).trailing_zeros() as usize;
}
i += 16;
}
i + match_len_portable(&a[i..], &b[i..], n - i)
}
}
#[cfg(all(target_arch = "aarch64", feature = "simd"))]
mod arch_aarch64 {
use super::match_len_portable;
use core::arch::aarch64::*;
#[target_feature(enable = "neon")]
pub unsafe fn match_len_neon(a: &[u8], b: &[u8], n: usize) -> usize {
let mut i = 0usize;
while i + 16 <= n {
let x = unsafe { vld1q_u8(a.as_ptr().add(i)) };
let y = unsafe { vld1q_u8(b.as_ptr().add(i)) };
let eq = unsafe { vceqq_u8(x, y) };
let min = unsafe { vminvq_u8(eq) };
if min == 0 {
for k in 0..16 {
if a[i + k] != b[i + k] {
return i + k;
}
}
unreachable!("vminvq_u8 reported a mismatch but byte scan found none");
}
i += 16;
}
i + match_len_portable(&a[i..], &b[i..], n - i)
}
}
#[inline]
pub fn prefetch_read(ptr: *const u8) {
#[cfg(target_arch = "x86_64")]
{
unsafe {
::core::arch::x86_64::_mm_prefetch::<{ ::core::arch::x86_64::_MM_HINT_T0 }>(
ptr.cast::<i8>(),
);
}
}
#[cfg(target_arch = "aarch64")]
{
let _ = ptr;
}
#[cfg(not(any(target_arch = "x86_64", target_arch = "aarch64")))]
{
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 match_len_vector_width_boundaries() {
for total in [0usize, 1, 7, 8, 15, 16, 17, 31, 32, 33, 63, 64, 65, 100] {
for diff_at in 0..total {
let a = vec![0x5Au8; total];
let mut b = a.clone();
b[diff_at] = 0xA5;
assert_eq!(
match_len(&a, &b, total),
diff_at,
"total={total} diff_at={diff_at}"
);
}
let a = vec![0x5Au8; total];
let b = a.clone();
assert_eq!(match_len(&a, &b, total), total, "total={total} no diff");
}
}
#[test]
fn match_len_respects_max_cap() {
let a = vec![0x11u8; 100];
let b = vec![0x11u8; 100];
assert_eq!(match_len(&a, &b, 40), 40);
}
#[test]
#[cfg(all(target_arch = "x86_64", feature = "simd", feature = "std"))]
fn match_len_x86_paths_agree_with_portable() {
for total in [0usize, 1, 15, 16, 17, 31, 32, 33, 65, 100] {
for diff_at in 0..total {
let a = vec![0x5Au8; total];
let mut b = a.clone();
b[diff_at] = 0xA5;
let expected = match_len_portable(&a, &b, total);
assert_eq!(expected, diff_at);
if std::is_x86_feature_detected!("avx2") {
let got = unsafe { arch_x86::match_len_avx2(&a, &b, total) };
assert_eq!(got, expected, "avx2 total={total} diff_at={diff_at}");
}
if std::is_x86_feature_detected!("sse2") {
let got = unsafe { arch_x86::match_len_sse2(&a, &b, total) };
assert_eq!(got, expected, "sse2 total={total} diff_at={diff_at}");
}
}
}
}
#[test]
#[cfg(all(target_arch = "x86_64", feature = "simd"))]
fn match_len_sse2_agrees_with_portable_no_std() {
for total in [0usize, 1, 15, 16, 17, 31, 32, 33, 65, 100] {
for diff_at in 0..total {
let a = vec![0x5Au8; total];
let mut b = a.clone();
b[diff_at] = 0xA5;
let expected = match_len_portable(&a, &b, total);
let got = unsafe { arch_x86::match_len_sse2(&a, &b, total) };
assert_eq!(got, expected, "sse2 total={total} diff_at={diff_at}");
}
}
}
#[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);
}
}