use std::simd::cmp::{SimdPartialEq, SimdPartialOrd};
use std::simd::{simd_swizzle, u8x16, u8x32, u8x8, Select, Simd};
use crate::alphabet::{DP_CLASS, DP_PLAIN};
pub const LANES: usize = 16;
const NIBBLE_BITS: [u8; 16] = [1, 2, 4, 8, 16, 32, 64, 128, 0, 0, 0, 0, 0, 0, 0, 0];
#[derive(Clone, Copy)]
pub struct SkipSet {
lo: u8x16,
}
impl SkipSet {
pub fn new() -> Self {
const PLAIN_LO: [u8; 16] = {
let mut lo = [0u8; 16];
let mut b = 0usize;
while b < 128 {
if DP_CLASS[b] == DP_PLAIN {
lo[b & 15] |= 1 << (b >> 4);
}
b += 1;
}
lo
};
SkipSet { lo: u8x16::from_array(PLAIN_LO) }
}
#[inline]
pub fn account(&mut self, b: u8) {
let mut lo = self.lo.to_array();
lo[(b & 15) as usize] |= 1 << (b >> 4);
self.lo = u8x16::from_array(lo);
}
#[inline]
pub fn skippable(&self, w: &[u8; LANES + 1]) -> usize {
let cur = u8x16::from_slice(&w[1..]);
let prev = u8x16::from_slice(&w[..LANES]);
let lo = self.lo.swizzle_dyn(cur & Simd::splat(15));
let bits = Simd::from_array(NIBBLE_BITS).swizzle_dyn(cur >> Simd::splat(4));
let accounted = (lo & bits).simd_gt(Simd::splat(0));
let opens_run = cur.simd_eq(prev);
let stops = !(accounted & !opens_run);
(stops.to_bitmask().trailing_zeros() as usize).min(LANES)
}
}
pub const SKIP_BYTES: usize = 32;
pub const SKIP_WINDOW: usize = SKIP_BYTES + 8;
#[inline]
pub fn groups_may_hold(w: &[u8; SKIP_WINDOW]) -> bool {
let v = u8x32::from_slice(&w[..SKIP_BYTES]);
let tails: u8x8 = simd_swizzle!(v, [2, 6, 10, 14, 18, 22, 26, 30]);
if tails.simd_eq(Simd::splat(0)).any() {
return true;
}
let firsts: u8x8 = simd_swizzle!(v, [0, 4, 8, 12, 16, 20, 24, 28]);
let seconds: u8x8 = simd_swizzle!(v, [1, 5, 9, 13, 17, 21, 25, 29]);
if firsts.simd_eq(seconds).any() {
return true;
}
let in_range = |x: u8x32| {
(x.simd_ge(Simd::splat(0x09)) & x.simd_le(Simd::splat(0x7E))).to_bitmask()
};
let bits = in_range(v) | (in_range(u8x32::from_slice(&w[8..8 + SKIP_BYTES])) << 8);
let runs = {
let two = bits & (bits >> 1);
let four = two & (two >> 2);
four & (four >> 4)
};
runs & 0x1111_1111 != 0
}
#[inline]
pub fn translate(pairs: &[(u8, u8)], src: &[u8], dst: &mut [u8]) {
debug_assert_eq!(src.len(), dst.len());
let (s_chunks, s_rest) = src.as_chunks::<LANES>();
let (d_chunks, d_rest) = dst.as_chunks_mut::<LANES>();
for (s, d) in s_chunks.iter().zip(d_chunks) {
let mut v = u8x16::from_array(*s) & Simd::splat(0x7f);
for &(rset, donor) in pairs {
let hit = v.simd_eq(Simd::splat(rset));
v = hit.select(Simd::splat(donor), v);
}
*d = v.to_array();
}
for (o, &b) in d_rest.iter_mut().zip(s_rest.iter()) {
let b = b & 0x7f;
*o = pairs.iter().find(|&&(rset, _)| rset == b).map_or(b, |&(_, donor)| donor);
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::alphabet::DP_STOP;
fn scalar_skippable(uninteresting: &[bool; 256], w: &[u8; LANES + 1]) -> usize {
let mut n = 0;
while n < LANES {
let b = w[n + 1];
if !uninteresting[b as usize] || b == w[n] {
break;
}
n += 1;
}
n
}
struct Rng(u64);
impl Rng {
fn next(&mut self) -> u64 {
self.0 ^= self.0 << 13;
self.0 ^= self.0 >> 7;
self.0 ^= self.0 << 17;
self.0
}
}
fn reference(accounted: &[u8]) -> [bool; 256] {
let mut table = [false; 256];
for b in 0..=255u8 {
table[b as usize] = DP_CLASS[b as usize] == DP_PLAIN;
}
for &b in accounted {
table[b as usize] = true;
}
table
}
fn scalar_groups_may_hold(w: &[u8; SKIP_WINDOW]) -> bool {
(0..8).any(|g| {
let q = 4 * g;
w[q + 2] == 0
|| w[q + 1] == w[q]
|| (0..8).all(|i| (0x09..=0x7E).contains(&w[q + i]))
})
}
#[test]
fn groups_may_hold_never_rules_out_a_group_the_scalar_test_keeps() {
let mut rng = Rng(0x1234_5678_9ABC_DEF1);
for case in 0..crate::tests::cases(50_000) {
let mut w = [0u8; SKIP_WINDOW];
for slot in w.iter_mut() {
*slot = match rng.next() % 6 {
0..=2 => (rng.next() % 256) as u8,
3 | 4 => b"abcdefghijklmnopqrstuvwxyz .,"[(rng.next() % 29) as usize],
_ => [0u8, 0, 0xFF, b'a'][(rng.next() % 4) as usize],
};
}
if rng.next().is_multiple_of(4) {
let at = 4 * ((rng.next() % 8) as usize);
let b = w[at];
for i in 0..1 + (rng.next() % 6) as usize {
if at + i < SKIP_WINDOW {
w[at + i] = b;
}
}
}
assert_eq!(
groups_may_hold(&w),
scalar_groups_may_hold(&w),
"case {case}: {w:?}"
);
}
}
#[test]
fn every_gate_is_seen_at_every_group_position() {
let background: Vec<u8> = (0..SKIP_WINDOW).map(|i| 0x81 + (i % 7) as u8).collect();
let mut base = [0u8; SKIP_WINDOW];
base.copy_from_slice(&background);
assert!(!groups_may_hold(&base), "the background itself wakes a gate");
for g in 0..8 {
let q = 4 * g;
let mut zero_tail = base;
zero_tail[q + 2] = 0;
assert!(groups_may_hold(&zero_tail), "tail gate missed at group {g}");
let mut pair = base;
pair[q + 1] = pair[q];
assert!(groups_may_hold(&pair), "solid Fill gate missed at group {g}");
let mut run = base;
for i in 0..8 {
run[q + i] = b'a';
}
assert!(groups_may_hold(&run), "passthrough gate missed at group {g}");
}
}
#[test]
fn skippable_answers_what_the_scalar_loop_would() {
let mut rng = Rng(0x2545_F491_4F6C_DD1D);
let interesting: Vec<u8> = (0..=255u8)
.filter(|&b| DP_CLASS[b as usize] != DP_PLAIN && DP_CLASS[b as usize] != DP_STOP)
.collect();
for case in 0..crate::tests::cases(20_000) {
let mut accounted = Vec::new();
let mut set = SkipSet::new();
for _ in 0..(rng.next() % 6) {
let b = interesting[(rng.next() % interesting.len() as u64) as usize];
accounted.push(b);
set.account(b);
}
let table = reference(&accounted);
let mut w = [0u8; LANES + 1];
for slot in w.iter_mut() {
*slot = match rng.next() % 8 {
0 => (rng.next() % 256) as u8,
1 => interesting[(rng.next() % interesting.len() as u64) as usize],
2 => 0x80u8.wrapping_add((rng.next() % 128) as u8),
_ => b"abcdefghijklmnopqrstuvwxyz0123456789"
[(rng.next() % 36) as usize],
};
}
if rng.next().is_multiple_of(3) {
let at = (rng.next() % LANES as u64) as usize;
w[at + 1] = w[at];
}
assert_eq!(
set.skippable(&w),
scalar_skippable(&table, &w),
"case {case}: window {w:?}, accounted {accounted:?}"
);
}
}
#[test]
fn every_byte_is_classified_as_the_scalar_loop_classifies_it() {
for b in 0..=255u8 {
for account_it in [false, true] {
let mut set = SkipSet::new();
let mut accounted = Vec::new();
if account_it && DP_CLASS[b as usize] != DP_STOP {
set.account(b);
accounted.push(b);
}
let table = reference(&accounted);
let mut w = [b'a'; LANES + 1];
w[0] = if b == b'b' { b'c' } else { b'b' };
w[1] = b;
assert_eq!(
set.skippable(&w),
scalar_skippable(&table, &w),
"{b:#04x}, accounted {account_it}"
);
let mut w = [b'a'; LANES + 1];
w[0] = b;
w[1] = b;
assert_eq!(set.skippable(&w), 0, "{b:#04x} opened a run and was skipped");
}
}
}
}