use crate::LEAF;
pub(crate) type Lanes = [u8; LEAF];
pub(crate) const GONE: u8 = 0xff;
#[derive(Clone, Copy)]
pub(crate) struct Mask(Bits);
#[cfg(target_arch = "aarch64")]
type Bits = u64;
#[cfg(not(target_arch = "aarch64"))]
type Bits = u32;
#[cfg(target_arch = "aarch64")]
#[inline]
fn lane(b: u32) -> usize {
(b / 4 + 16 * (b >> 1 & 1)) as usize
}
#[cfg(not(target_arch = "aarch64"))]
#[inline]
fn lane(b: u32) -> usize {
b as usize
}
impl Mask {
#[inline]
pub(crate) fn count(self) -> usize {
self.0.count_ones() as usize
}
#[inline]
pub(crate) fn first(self) -> Option<usize> {
(self.0 != 0).then(|| lane(self.0.trailing_zeros()))
}
#[cfg(test)]
pub(crate) fn bits(self) -> u32 {
self.fold(0, |m, i| m | 1 << i)
}
}
impl Iterator for Mask {
type Item = usize;
#[inline]
fn next(&mut self) -> Option<usize> {
let i = self.first()?;
self.0 &= self.0 - 1;
Some(i)
}
}
#[cfg(target_arch = "x86_64")]
mod imp {
use super::{Lanes, Mask};
use std::arch::x86_64::{
__m128i, _mm_and_si128, _mm_andnot_si128, _mm_cmpeq_epi8, _mm_cmplt_epi8,
_mm_loadu_si128, _mm_movemask_epi8, _mm_or_si128, _mm_set1_epi8, _mm_setr_epi8,
_mm_slli_si128, _mm_srli_si128, _mm_storeu_si128, _mm_xor_si128,
};
#[inline]
fn load(x: &Lanes) -> [__m128i; 2] {
unsafe {
[
_mm_loadu_si128(x.as_ptr().cast()),
_mm_loadu_si128(x.as_ptr().add(16).cast()),
]
}
}
#[inline]
fn store(x: &mut Lanes, [lo, hi]: [__m128i; 2]) {
unsafe {
_mm_storeu_si128(x.as_mut_ptr().cast(), lo);
_mm_storeu_si128(x.as_mut_ptr().add(16).cast(), hi);
}
}
#[inline]
fn mask([lo, hi]: [__m128i; 2]) -> Mask {
unsafe {
Mask(_mm_movemask_epi8(lo) as u32 | (_mm_movemask_epi8(hi) as u32) << 16)
}
}
#[inline]
fn index() -> [__m128i; 2] {
unsafe {
let lo = _mm_setr_epi8(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15);
[lo, _mm_or_si128(lo, _mm_set1_epi8(16))]
}
}
#[inline]
pub(crate) fn eq(x: &Lanes, t: u8) -> Mask {
let [lo, hi] = load(x);
unsafe {
let t = _mm_set1_epi8(t as i8);
mask([_mm_cmpeq_epi8(lo, t), _mm_cmpeq_epi8(hi, t)])
}
}
#[inline]
pub(crate) fn below(x: &Lanes, t: u8) -> Mask {
let [lo, hi] = load(x);
unsafe {
let flip = _mm_set1_epi8(i8::MIN);
let t = _mm_set1_epi8((t ^ 0x80) as i8);
let lo = _mm_cmplt_epi8(_mm_xor_si128(lo, flip), t);
let hi = _mm_cmplt_epi8(_mm_xor_si128(hi, flip), t);
mask([lo, hi])
}
}
#[inline]
pub(crate) fn insert(x: &mut Lanes, i: usize, v: u8) {
let [lo, hi] = load(x);
let [ilo, ihi] = index();
unsafe {
let up = [
_mm_slli_si128(lo, 1),
_mm_or_si128(_mm_slli_si128(hi, 1), _mm_srli_si128(lo, 15)),
];
let (at, v) = (_mm_set1_epi8(i as i8), _mm_set1_epi8(v as i8));
let pick = |x, up, idx| {
let (before, here) = (_mm_cmplt_epi8(idx, at), _mm_cmpeq_epi8(idx, at));
let kept = _mm_or_si128(_mm_and_si128(before, x), _mm_and_si128(here, v));
_mm_or_si128(kept, _mm_andnot_si128(_mm_or_si128(before, here), up))
};
store(x, [pick(lo, up[0], ilo), pick(hi, up[1], ihi)]);
}
}
#[inline]
pub(crate) fn remove(x: &mut Lanes, i: usize) {
let [lo, hi] = load(x);
let [ilo, ihi] = index();
unsafe {
let gone = _mm_slli_si128(_mm_set1_epi8(super::GONE as i8), 15);
let down = [
_mm_or_si128(_mm_srli_si128(lo, 1), _mm_slli_si128(hi, 15)),
_mm_or_si128(_mm_srli_si128(hi, 1), gone),
];
let at = _mm_set1_epi8(i as i8);
let pick = |x, down, idx| {
let before = _mm_cmplt_epi8(idx, at);
_mm_or_si128(_mm_and_si128(before, x), _mm_andnot_si128(before, down))
};
store(x, [pick(lo, down[0], ilo), pick(hi, down[1], ihi)]);
}
}
}
#[cfg(target_arch = "aarch64")]
mod imp {
use super::{Lanes, Mask};
use std::arch::aarch64::{
uint8x16_t, vbsl_u8, vbslq_u8, vceqq_u8, vcltq_u8, vdup_n_u8, vdupq_n_u8,
vextq_u8, vget_lane_u64, vld1q_u8, vreinterpret_u64_u8, vreinterpretq_u16_u8,
vshrn_n_u16, vst1q_u8,
};
#[inline]
fn load(x: &Lanes) -> [uint8x16_t; 2] {
unsafe { [vld1q_u8(x.as_ptr()), vld1q_u8(x.as_ptr().add(16))] }
}
#[inline]
fn store(x: &mut Lanes, [lo, hi]: [uint8x16_t; 2]) {
unsafe {
vst1q_u8(x.as_mut_ptr(), lo);
vst1q_u8(x.as_mut_ptr().add(16), hi);
}
}
#[inline]
fn mask([lo, hi]: [uint8x16_t; 2]) -> Mask {
unsafe {
let lo = vshrn_n_u16(vreinterpretq_u16_u8(lo), 4);
let hi = vshrn_n_u16(vreinterpretq_u16_u8(hi), 4);
let both = vbsl_u8(vdup_n_u8(0x33), lo, hi);
Mask(vget_lane_u64(vreinterpret_u64_u8(both), 0) & 0x5555_5555_5555_5555)
}
}
#[inline]
fn index() -> [uint8x16_t; 2] {
const INDEX: [u8; 32] = {
let mut a = [0; 32];
let mut i = 0;
while i < 32 {
a[i] = i as u8;
i += 1;
}
a
};
load(&INDEX)
}
#[inline]
pub(crate) fn eq(x: &Lanes, t: u8) -> Mask {
let [lo, hi] = load(x);
unsafe {
let t = vdupq_n_u8(t);
mask([vceqq_u8(lo, t), vceqq_u8(hi, t)])
}
}
#[inline]
pub(crate) fn below(x: &Lanes, t: u8) -> Mask {
let [lo, hi] = load(x);
unsafe {
let t = vdupq_n_u8(t);
mask([vcltq_u8(lo, t), vcltq_u8(hi, t)])
}
}
#[inline]
pub(crate) fn insert(x: &mut Lanes, i: usize, v: u8) {
let [lo, hi] = load(x);
let [ilo, ihi] = index();
unsafe {
let up = [vextq_u8(vdupq_n_u8(0), lo, 15), vextq_u8(lo, hi, 15)];
let (at, v) = (vdupq_n_u8(i as u8), vdupq_n_u8(v));
let pick = |x, up, idx| {
let moved = vbslq_u8(vceqq_u8(idx, at), v, up);
vbslq_u8(vcltq_u8(idx, at), x, moved)
};
store(x, [pick(lo, up[0], ilo), pick(hi, up[1], ihi)]);
}
}
#[inline]
pub(crate) fn remove(x: &mut Lanes, i: usize) {
let [lo, hi] = load(x);
let [ilo, ihi] = index();
unsafe {
let down = [vextq_u8(lo, hi, 1), vextq_u8(hi, vdupq_n_u8(super::GONE), 1)];
let at = vdupq_n_u8(i as u8);
let pick = |x, down, idx| vbslq_u8(vcltq_u8(idx, at), x, down);
store(x, [pick(lo, down[0], ilo), pick(hi, down[1], ihi)]);
}
}
}
#[cfg(any(test, not(any(target_arch = "x86_64", target_arch = "aarch64"))))]
mod scalar {
use super::Lanes;
use crate::LEAF;
pub(crate) fn eq(x: &Lanes, t: u8) -> u32 {
const LOW: u64 = 0x7f7f_7f7f_7f7f_7f7f;
let mut m = 0;
for (w, chunk) in x.as_chunks::<8>().0.iter().enumerate() {
let x = u64::from_le_bytes(*chunk) ^ (0x0101_0101_0101_0101 * t as u64);
let zero = !(((x & LOW) + LOW) | x | LOW);
m |= (((zero >> 7).wrapping_mul(0x0102_0408_1020_4080) >> 56) as u32)
<< (8 * w);
}
m
}
pub(crate) fn below(x: &Lanes, t: u8) -> u32 {
x.iter().enumerate().fold(0, |m, (i, &x)| m | ((x < t) as u32) << i)
}
pub(crate) fn insert(x: &mut Lanes, i: usize, v: u8) {
x.copy_within(i..LEAF - 1, i + 1);
x[i] = v;
}
pub(crate) fn remove(x: &mut Lanes, i: usize) {
x.copy_within(i + 1.., i);
x[LEAF - 1] = super::GONE;
}
}
#[cfg(test)]
pub(crate) use scalar::{
below as scalar_below, eq as scalar_eq, insert as scalar_insert,
remove as scalar_remove,
};
#[cfg(not(any(target_arch = "x86_64", target_arch = "aarch64")))]
mod imp {
use super::{Lanes, Mask, scalar};
pub(crate) fn eq(x: &Lanes, t: u8) -> Mask {
Mask(scalar::eq(x, t))
}
pub(crate) fn below(x: &Lanes, t: u8) -> Mask {
Mask(scalar::below(x, t))
}
pub(crate) use scalar::{insert, remove};
}
pub(crate) use imp::eq;
pub(crate) use imp::below;
pub(crate) use imp::insert;
pub(crate) use imp::remove;