#[cfg(target_arch = "x86")]
use core::arch::x86::*;
#[cfg(target_arch = "x86_64")]
use core::arch::x86_64::*;
#[target_feature(enable = "ssse3")]
pub(in super::super) fn shufti_ssse3<const REVERT: bool>(
low: &[u8; 16],
high: &[u8; 16],
haystack: &[u8],
) -> Option<usize> {
if haystack.len() < 4 {
return super::super::search_fallback::<REVERT>(low, high, haystack);
}
if haystack.len() < 16 {
return unsafe {
search_short::<REVERT>(
_mm_loadu_si128(low.as_ptr().cast()),
_mm_loadu_si128(high.as_ptr().cast()),
haystack,
)
};
}
unsafe {
search128::<REVERT>(
_mm_loadu_si128(low.as_ptr().cast()),
_mm_loadu_si128(high.as_ptr().cast()),
haystack,
)
}
}
#[inline(always)]
unsafe fn search128<const REVERT: bool>(
low: __m128i,
high: __m128i,
haystack: &[u8],
) -> Option<usize> {
unsafe {
let ptr = haystack.as_ptr();
let len = haystack.len();
let mask = mask16::<REVERT>(low, high, _mm_loadu_si128(ptr.cast()));
if mask != 0 {
return Some(mask.trailing_zeros() as usize);
}
let mut start = 16 - (ptr as usize & 0b00001111);
let last = len - 16;
while start < last {
let mask = mask16::<REVERT>(low, high, _mm_load_si128(ptr.add(start).cast()));
if mask != 0 {
return Some(start + mask.trailing_zeros() as usize);
}
start += 16;
}
let mask = mask16::<REVERT>(low, high, _mm_loadu_si128(ptr.add(last).cast()));
if mask != 0 {
Some(last + mask.trailing_zeros() as usize)
} else {
None
}
}
}
#[target_feature(enable = "ssse3")]
pub(in super::super) fn rshufti_ssse3<const REVERT: bool>(
low: &[u8; 16],
high: &[u8; 16],
haystack: &[u8],
) -> Option<usize> {
if haystack.len() < 4 {
return super::super::rsearch_fallback::<REVERT>(low, high, haystack);
}
if haystack.len() < 16 {
return unsafe {
rsearch_short::<REVERT>(
_mm_loadu_si128(low.as_ptr().cast()),
_mm_loadu_si128(high.as_ptr().cast()),
haystack,
)
};
}
unsafe {
rsearch128::<REVERT>(
_mm_loadu_si128(low.as_ptr().cast()),
_mm_loadu_si128(high.as_ptr().cast()),
haystack,
)
}
}
#[inline(always)]
unsafe fn rsearch128<const REVERT: bool>(
low: __m128i,
high: __m128i,
haystack: &[u8],
) -> Option<usize> {
unsafe {
let ptr = haystack.as_ptr();
let len = haystack.len();
let last = len - 16;
let mask = mask16::<REVERT>(low, high, _mm_loadu_si128(ptr.add(last).cast()));
if mask != 0 {
return Some(last + (31 - (mask as u32).leading_zeros()) as usize);
}
let mut end = len - (ptr.add(len) as usize & 0b00001111);
while end > 16 {
end -= 16;
let mask = mask16::<REVERT>(low, high, _mm_load_si128(ptr.add(end).cast()));
if mask != 0 {
return Some(end + (31 - (mask as u32).leading_zeros()) as usize);
}
}
let mask = mask16::<REVERT>(low, high, _mm_loadu_si128(ptr.cast()));
if mask != 0 {
Some((31 - (mask as u32).leading_zeros()) as usize)
} else {
None
}
}
}
#[inline(always)]
pub(super) unsafe fn search_short<const REVERT: bool>(
low: __m128i,
high: __m128i,
haystack: &[u8],
) -> Option<usize> {
if haystack.len() < 8 {
let mask = unsafe { mask8_overlap::<REVERT>(low, high, haystack) };
return if mask != 0 {
Some(mask.trailing_zeros() as usize)
} else {
None
};
}
let mask = unsafe { mask16_overlap::<REVERT>(low, high, haystack) };
if mask != 0 {
Some(mask.trailing_zeros() as usize)
} else {
None
}
}
#[inline(always)]
pub(super) unsafe fn rsearch_short<const REVERT: bool>(
low: __m128i,
high: __m128i,
haystack: &[u8],
) -> Option<usize> {
if haystack.len() < 8 {
let mask = unsafe { mask8_overlap::<REVERT>(low, high, haystack) };
return if mask != 0 {
Some((7 - mask.leading_zeros()) as usize)
} else {
None
};
}
let mask = unsafe { mask16_overlap::<REVERT>(low, high, haystack) };
if mask != 0 {
Some((15 - mask.leading_zeros()) as usize)
} else {
None
}
}
#[inline(always)]
unsafe fn mask8_overlap<const REVERT: bool>(low: __m128i, high: __m128i, haystack: &[u8]) -> u8 {
unsafe {
let ptr = haystack.as_ptr();
let last = haystack.len() - 4;
let prefix = _mm_loadu_si32(ptr.cast());
let suffix = _mm_loadu_si32(ptr.add(last).cast());
let mask = mask16::<REVERT>(low, high, _mm_unpacklo_epi32(prefix, suffix)) as u8;
(mask & 0b0000_1111) | ((mask >> 4) << last)
}
}
#[inline(always)]
unsafe fn mask16_overlap<const REVERT: bool>(low: __m128i, high: __m128i, haystack: &[u8]) -> u16 {
unsafe {
let ptr = haystack.as_ptr();
let last = haystack.len() - 8;
let prefix = _mm_loadl_epi64(ptr.cast());
let suffix = _mm_loadl_epi64(ptr.add(last).cast());
let mask = mask16::<REVERT>(low, high, _mm_unpacklo_epi64(prefix, suffix));
(mask & 0b1111_1111) | ((mask >> 8) << last)
}
}
#[inline(always)]
unsafe fn mask16<const REVERT: bool>(low: __m128i, high: __m128i, bytes: __m128i) -> u16 {
unsafe {
let nibble = _mm_set1_epi8(0b0000_1111);
let low = _mm_shuffle_epi8(low, _mm_and_si128(bytes, nibble));
let high = _mm_shuffle_epi8(high, _mm_srli_epi64::<4>(_mm_andnot_si128(nibble, bytes)));
let member = _mm_and_si128(low, high);
let selected = if REVERT {
_mm_cmpeq_epi8(member, _mm_setzero_si128())
} else {
_mm_add_epi8(member, _mm_set1_epi8(0b0111_1111))
};
_mm_movemask_epi8(selected) as u16
}
}
#[cfg(test)]
mod tests {
use super::{
_mm_loadu_si128, _mm_set1_epi8, _mm_setzero_si128, mask16, mask16_overlap, mask8_overlap,
rsearch_short, search_short,
};
use crate::{shufti::ShuftiTable, SimdBackend};
#[test]
fn mask16_selects_each_group_flag() {
if !SimdBackend::Ssse3.is_available() {
return;
}
for group in 0..8 {
let flag = 1u8 << group;
let actual = unsafe {
let table = _mm_set1_epi8(flag as i8);
mask16::<false>(table, table, _mm_setzero_si128())
};
assert_eq!(actual, u16::MAX, "every lane must select flag {flag:#010b}");
}
}
#[test]
fn search_short_returns_none_when_no_bytes_match() {
if !SimdBackend::Ssse3.is_available() {
return;
}
let table = ShuftiTable::new(b"a").unwrap();
let haystack = [b'!'; 15];
for len in 4..16 {
let actual = unsafe {
search_short::<false>(
_mm_loadu_si128(table.low().as_ptr().cast()),
_mm_loadu_si128(table.high().as_ptr().cast()),
&haystack[..len],
)
};
assert_eq!(actual, None);
}
}
#[test]
fn rsearch_short_excludes_bits_past_the_input() {
if !SimdBackend::Ssse3.is_available() {
return;
}
let table = ShuftiTable::new(b"a").unwrap();
let haystack = [b'a'; 15];
for len in 4..16 {
let actual = unsafe {
rsearch_short::<false>(
_mm_loadu_si128(table.low().as_ptr().cast()),
_mm_loadu_si128(table.high().as_ptr().cast()),
&haystack[..len],
)
};
assert_eq!(actual, Some(len - 1));
}
}
#[test]
fn mask8_overlap_preserves_each_nonmembers_position() {
if !SimdBackend::Ssse3.is_available() {
return;
}
let table = ShuftiTable::new(b"a").unwrap();
for len in 4..8 {
for position in 0..len {
let mut haystack = [b'a'; 7];
haystack[position] = b'!';
let mask = unsafe {
mask8_overlap::<true>(
_mm_loadu_si128(table.low().as_ptr().cast()),
_mm_loadu_si128(table.high().as_ptr().cast()),
&haystack[..len],
)
};
assert_eq!(mask, 1 << position, "len={len}, byte={position}");
}
}
}
#[test]
fn mask8_overlap_preserves_each_members_position() {
if !SimdBackend::Ssse3.is_available() {
return;
}
let table = ShuftiTable::new(b"a").unwrap();
for len in 4..8 {
for position in 0..len {
let mut haystack = [b'!'; 7];
haystack[position] = b'a';
let mask = unsafe {
mask8_overlap::<false>(
_mm_loadu_si128(table.low().as_ptr().cast()),
_mm_loadu_si128(table.high().as_ptr().cast()),
&haystack[..len],
)
};
assert_eq!(mask, 1 << position, "len={len}, byte={position}");
}
}
}
#[test]
fn mask8_overlap_excludes_matching_zero_filled_lanes() {
if !SimdBackend::Ssse3.is_available() {
return;
}
let table = ShuftiTable::new(&[0]).unwrap();
let haystack = [b'!'; 7];
for len in 4..8 {
let mask = unsafe {
mask8_overlap::<false>(
_mm_loadu_si128(table.low().as_ptr().cast()),
_mm_loadu_si128(table.high().as_ptr().cast()),
&haystack[..len],
)
};
assert_eq!(mask, 0, "len={len}");
}
}
#[test]
fn mask8_overlap_excludes_zero_filled_lanes() {
if !SimdBackend::Ssse3.is_available() {
return;
}
let table = ShuftiTable::new(b"a").unwrap();
let haystack = [b'a'; 7];
let mask = unsafe {
mask8_overlap::<true>(
_mm_loadu_si128(table.low().as_ptr().cast()),
_mm_loadu_si128(table.high().as_ptr().cast()),
&haystack,
)
};
assert_eq!(mask, 0);
}
#[test]
fn mask16_overlap_preserves_each_nonmembers_position() {
if !SimdBackend::Ssse3.is_available() {
return;
}
let table = ShuftiTable::new(b"a").unwrap();
for len in 8..16 {
for position in 0..len {
let mut haystack = [b'a'; 15];
haystack[position] = b'!';
let mask = unsafe {
mask16_overlap::<true>(
_mm_loadu_si128(table.low().as_ptr().cast()),
_mm_loadu_si128(table.high().as_ptr().cast()),
&haystack[..len],
)
};
assert_eq!(mask, 1 << position, "len={len}, byte={position}");
}
}
}
#[test]
fn mask16_overlap_preserves_each_members_position() {
if !SimdBackend::Ssse3.is_available() {
return;
}
let table = ShuftiTable::new(b"a").unwrap();
for len in 8..16 {
for position in 0..len {
let mut haystack = [b'!'; 15];
haystack[position] = b'a';
let mask = unsafe {
mask16_overlap::<false>(
_mm_loadu_si128(table.low().as_ptr().cast()),
_mm_loadu_si128(table.high().as_ptr().cast()),
&haystack[..len],
)
};
assert_eq!(mask, 1 << position, "len={len}, byte={position}");
}
}
}
#[test]
fn mask16_overlap_clears_bits_past_the_input() {
if !SimdBackend::Ssse3.is_available() {
return;
}
let table = ShuftiTable::new(b"a").unwrap();
let haystack = [b'!'; 15];
let mask = unsafe {
mask16_overlap::<true>(
_mm_loadu_si128(table.low().as_ptr().cast()),
_mm_loadu_si128(table.high().as_ptr().cast()),
&haystack,
)
};
assert_eq!(mask, 0b0111_1111_1111_1111);
}
}