#[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 truffle_ssse3<const REVERT: bool>(
lower: &[u8; 16],
upper: &[u8; 16],
haystack: &[u8],
) -> Option<usize> {
if haystack.len() < 4 {
return super::super::search_fallback::<REVERT>(lower, upper, haystack);
}
unsafe {
search128::<REVERT>(
_mm_loadu_si128(lower.as_ptr().cast()),
_mm_loadu_si128(upper.as_ptr().cast()),
haystack,
)
}
}
#[inline(always)]
unsafe fn search128<const REVERT: bool>(
lower: __m128i,
upper: __m128i,
haystack: &[u8],
) -> Option<usize> {
unsafe {
let ptr = haystack.as_ptr();
let len = haystack.len();
if len < 16 {
return search_short::<REVERT>(lower, upper, haystack);
}
let mask = mask16::<REVERT>(lower, upper, _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>(lower, upper, _mm_load_si128(ptr.add(start).cast()));
if mask != 0 {
return Some(start + mask.trailing_zeros() as usize);
}
start += 16;
}
let mask = mask16::<REVERT>(lower, upper, _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 rtruffle_ssse3<const REVERT: bool>(
lower: &[u8; 16],
upper: &[u8; 16],
haystack: &[u8],
) -> Option<usize> {
if haystack.len() < 4 {
return super::super::rsearch_fallback::<REVERT>(lower, upper, haystack);
}
unsafe {
rsearch128::<REVERT>(
_mm_loadu_si128(lower.as_ptr().cast()),
_mm_loadu_si128(upper.as_ptr().cast()),
haystack,
)
}
}
#[inline(always)]
unsafe fn rsearch128<const REVERT: bool>(
lower: __m128i,
upper: __m128i,
haystack: &[u8],
) -> Option<usize> {
unsafe {
let ptr = haystack.as_ptr();
let len = haystack.len();
if len < 16 {
return rsearch_short::<REVERT>(lower, upper, haystack);
}
let last = len - 16;
let mask = mask16::<REVERT>(lower, upper, _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>(lower, upper, _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>(lower, upper, _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>(
lower: __m128i,
upper: __m128i,
haystack: &[u8],
) -> Option<usize> {
unsafe {
let len = haystack.len();
if len < 8 {
let mask = mask8_overlap::<REVERT>(lower, upper, haystack);
return if mask != 0 {
Some(mask.trailing_zeros() as usize)
} else {
None
};
}
let mask = mask16_overlap::<REVERT>(lower, upper, haystack);
if mask != 0 {
Some(mask.trailing_zeros() as usize)
} else {
None
}
}
}
#[inline(always)]
pub(super) unsafe fn rsearch_short<const REVERT: bool>(
lower: __m128i,
upper: __m128i,
haystack: &[u8],
) -> Option<usize> {
unsafe {
let len = haystack.len();
if len < 8 {
let mask = mask8_overlap::<REVERT>(lower, upper, haystack);
return if mask != 0 {
Some((7 - mask.leading_zeros()) as usize)
} else {
None
};
}
let mask = mask16_overlap::<REVERT>(lower, upper, haystack);
if mask != 0 {
Some((15 - mask.leading_zeros()) as usize)
} else {
None
}
}
}
#[inline(always)]
unsafe fn mask8_overlap<const REVERT: bool>(lower: __m128i, upper: __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>(lower, upper, _mm_unpacklo_epi32(prefix, suffix)) as u8;
(mask & 0b0000_1111) | ((mask >> 4) << last)
}
}
#[inline(always)]
unsafe fn mask16_overlap<const REVERT: bool>(
lower: __m128i,
upper: __m128i,
haystack: &[u8],
) -> u16 {
unsafe {
let last = haystack.len() - 8;
let prefix = _mm_loadl_epi64(haystack.as_ptr().cast());
let suffix = _mm_loadl_epi64(haystack.as_ptr().add(last).cast());
let bytes = _mm_unpacklo_epi64(prefix, suffix);
let mask = mask16::<REVERT>(lower, upper, bytes);
(mask & 0b1111_1111) | ((mask >> 8) << last)
}
}
#[inline(always)]
unsafe fn mask16<const REVERT: bool>(lower: __m128i, upper: __m128i, bytes: __m128i) -> u16 {
unsafe {
let top = _mm_set1_epi8(0b1000_0000u8 as i8);
let bits = _mm_set1_epi64x(u64::from_le_bytes([
1 << 0,
1 << 1,
1 << 2,
1 << 3,
1 << 4,
1 << 5,
1 << 6,
1 << 7,
]) as i64);
let lower = _mm_shuffle_epi8(lower, bytes);
let upper = _mm_shuffle_epi8(upper, _mm_xor_si128(bytes, top));
let index = _mm_andnot_si128(top, _mm_srli_epi64::<4>(bytes));
let selected = _mm_shuffle_epi8(bits, index);
let member = _mm_and_si128(_mm_or_si128(lower, upper), selected);
let matches = if REVERT {
_mm_cmpeq_epi8(member, _mm_setzero_si128())
} else {
_mm_cmpeq_epi8(member, selected)
};
_mm_movemask_epi8(matches) as u16
}
}
#[cfg(test)]
mod tests {
use super::{
_mm_loadu_si128, _mm_set1_epi8, mask16, mask16_overlap, mask8_overlap, rsearch_short,
search_short,
};
use crate::{truffle::TruffleTable, SimdBackend};
#[test]
fn mask16_selects_the_top_membership_bit_in_either_table() {
if !SimdBackend::Ssse3.is_available() {
return;
}
for byte in [0b0111_0000u8, 0b1111_0000] {
let actual = unsafe {
let table = _mm_set1_epi8(0b1000_0000u8 as i8);
mask16::<false>(table, table, _mm_set1_epi8(byte as i8))
};
assert_eq!(actual, u16::MAX, "every lane must select byte {byte:#010b}");
}
}
#[test]
fn search_short_returns_none_when_no_short_input_byte_matches() {
if !SimdBackend::Ssse3.is_available() {
return;
}
let table = TruffleTable::new(b"a");
let haystack = [b'!'; 15];
for len in 4..=15 {
let position = unsafe {
search_short::<false>(
_mm_loadu_si128(table.lower().as_ptr().cast()),
_mm_loadu_si128(table.upper().as_ptr().cast()),
&haystack[..len],
)
};
assert_eq!(position, None);
}
}
#[test]
fn rsearch_short_returns_the_last_of_fifteen_members() {
if !SimdBackend::Ssse3.is_available() {
return;
}
let table = TruffleTable::new(b"a");
let haystack = [b'a'; 15];
let position = unsafe {
rsearch_short::<false>(
_mm_loadu_si128(table.lower().as_ptr().cast()),
_mm_loadu_si128(table.upper().as_ptr().cast()),
&haystack,
)
};
assert_eq!(position, Some(14));
}
#[test]
fn mask8_overlap_preserves_each_nonmembers_position() {
if !SimdBackend::Ssse3.is_available() {
return;
}
let table = TruffleTable::new(b"a");
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.lower().as_ptr().cast()),
_mm_loadu_si128(table.upper().as_ptr().cast()),
&haystack[..len],
)
};
assert_eq!(mask, 1 << position, "len={len}, position={position}");
}
}
}
#[test]
fn mask8_overlap_preserves_each_members_position() {
if !SimdBackend::Ssse3.is_available() {
return;
}
let table = TruffleTable::new(b"a");
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.lower().as_ptr().cast()),
_mm_loadu_si128(table.upper().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 = TruffleTable::new(&[0]);
let haystack = [b'!'; 7];
for len in 4..8 {
let mask = unsafe {
mask8_overlap::<false>(
_mm_loadu_si128(table.lower().as_ptr().cast()),
_mm_loadu_si128(table.upper().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 = TruffleTable::new(b"a");
let haystack = [b'a'; 7];
let mask = unsafe {
mask8_overlap::<true>(
_mm_loadu_si128(table.lower().as_ptr().cast()),
_mm_loadu_si128(table.upper().as_ptr().cast()),
&haystack,
)
};
assert_eq!(mask, 0);
}
#[test]
fn mask16_overlap_preserves_each_nonmembers_position() {
if !SimdBackend::Ssse3.is_available() {
return;
}
let table = TruffleTable::new(b"a");
for len in 8..=15 {
for position in 0..len {
let mut haystack = [b'a'; 15];
haystack[position] = b'!';
let mask = unsafe {
mask16_overlap::<true>(
_mm_loadu_si128(table.lower().as_ptr().cast()),
_mm_loadu_si128(table.upper().as_ptr().cast()),
&haystack[..len],
)
};
assert_eq!(mask, 1 << position, "len={len}, position={position}");
}
}
}
#[test]
fn mask16_overlap_preserves_each_members_position() {
if !SimdBackend::Ssse3.is_available() {
return;
}
let table = TruffleTable::new(b"a");
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.lower().as_ptr().cast()),
_mm_loadu_si128(table.upper().as_ptr().cast()),
&haystack[..len],
)
};
assert_eq!(mask, 1 << position, "len={len}, byte={position}");
}
}
}
#[test]
fn mask16_overlap_excludes_the_sixteenth_lane_for_fifteen_nonmembers() {
if !SimdBackend::Ssse3.is_available() {
return;
}
let table = TruffleTable::new(b"a");
let haystack = [b'!'; 15];
let mask = unsafe {
mask16_overlap::<true>(
_mm_loadu_si128(table.lower().as_ptr().cast()),
_mm_loadu_si128(table.upper().as_ptr().cast()),
&haystack,
)
};
assert_eq!(mask, 0b0111_1111_1111_1111);
}
}