#[inline]
pub fn find_child_node16(keys: &[u8; 16], num_children: usize, needle: u8) -> Option<usize> {
#[cfg(all(target_arch = "x86_64", target_feature = "sse2"))]
{
find_child_x86_sse2(keys, num_children, needle)
}
#[cfg(all(target_arch = "aarch64", target_feature = "neon"))]
{
find_child_neon(keys, num_children, needle)
}
#[cfg(not(any(
all(target_arch = "x86_64", target_feature = "sse2"),
all(target_arch = "aarch64", target_feature = "neon")
)))]
{
find_child_scalar(keys, num_children, needle)
}
}
#[inline]
#[allow(dead_code)]
pub fn find_child_scalar(keys: &[u8; 16], num_children: usize, needle: u8) -> Option<usize> {
for (i, &k) in keys[..num_children].iter().enumerate() {
if k == needle {
return Some(i);
}
}
None
}
#[cfg(all(target_arch = "x86_64", target_feature = "sse2"))]
#[inline]
fn find_child_x86_sse2(keys: &[u8; 16], num_children: usize, needle: u8) -> Option<usize> {
#[cfg(target_arch = "x86_64")]
use std::arch::x86_64::{
__m128i, _mm_cmpeq_epi8, _mm_loadu_si128, _mm_movemask_epi8, _mm_set1_epi8,
};
unsafe {
let needle_vec = _mm_set1_epi8(needle as i8);
let keys_vec = _mm_loadu_si128(keys.as_ptr() as *const __m128i);
let cmp = _mm_cmpeq_epi8(keys_vec, needle_vec);
let mask = _mm_movemask_epi8(cmp) as u32;
let valid_mask = (1u32 << num_children).wrapping_sub(1);
let matches = mask & valid_mask;
if matches != 0 {
Some(matches.trailing_zeros() as usize)
} else {
None
}
}
}
#[cfg(all(target_arch = "aarch64", target_feature = "neon"))]
#[inline]
fn find_child_neon(keys: &[u8; 16], num_children: usize, needle: u8) -> Option<usize> {
#[cfg(target_arch = "aarch64")]
use std::arch::aarch64::{
vceqq_u8, vdupq_n_u8, vgetq_lane_u64, vld1q_u8, vreinterpretq_u64_u8,
};
unsafe {
let needle_vec = vdupq_n_u8(needle);
let keys_vec = vld1q_u8(keys.as_ptr());
let cmp = vceqq_u8(keys_vec, needle_vec);
let lo = vgetq_lane_u64(vreinterpretq_u64_u8(cmp), 0);
let hi = vgetq_lane_u64(vreinterpretq_u64_u8(cmp), 1);
if lo != 0 {
let idx = (lo.trailing_zeros() >> 3) as usize;
if idx < num_children {
return Some(idx);
}
} else if hi != 0 {
let idx = 8 + (hi.trailing_zeros() >> 3) as usize;
if idx < num_children {
return Some(idx);
}
}
None
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_find_child_node16() {
let mut keys = [0u8; 16];
keys[0] = b'a';
keys[1] = b'c';
keys[2] = b'f';
keys[3] = b'z';
assert_eq!(find_child_node16(&keys, 4, b'a'), Some(0));
assert_eq!(find_child_node16(&keys, 4, b'c'), Some(1));
assert_eq!(find_child_node16(&keys, 4, b'f'), Some(2));
assert_eq!(find_child_node16(&keys, 4, b'z'), Some(3));
assert_eq!(find_child_node16(&keys, 4, b'b'), None);
assert_eq!(find_child_node16(&keys, 4, b'm'), None);
keys[4] = b'x';
assert_eq!(find_child_node16(&keys, 4, b'x'), None);
assert_eq!(find_child_node16(&keys, 5, b'x'), Some(4));
}
#[test]
fn simd_matches_linear_search_exhaustively() {
let keys = [
0x05, 0x12, 0x24, 0x33, 0x48, 0x5a, 0x67, 0x7e, 0x89, 0x9f, 0xab, 0xb0, 0xcd, 0xde,
0xef, 0xfc,
];
for count in 0..=16 {
for byte in 0u8..=255 {
assert_eq!(
find_child_node16(&keys, count, byte),
keys[..count].iter().position(|&k| k == byte),
"byte {byte:#04x}, count {count}"
);
assert_eq!(
find_child_scalar(&keys, count, byte),
keys[..count].iter().position(|&k| k == byte)
);
}
}
}
}