#![cfg(any(test, feature = "cpu-parity"))]
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(crate) enum CsrClosureDirection {
Forward,
Reverse,
}
#[must_use]
pub(crate) fn csr_bitset_closure(
context: &'static str,
node_count: u32,
edge_offsets: &[u32],
edge_targets: &[u32],
edge_kind_mask: &[u32],
seed_bits: &[u32],
required_edge_mask: u32,
direction: CsrClosureDirection,
) -> Vec<u32> {
let nodes = u32_to_usize(node_count, context, "node count");
let words = bitset_words(nodes, context);
crate::dispatch_decode::require_csr_shape(
context,
node_count,
edge_offsets,
edge_targets,
edge_kind_mask,
)
.unwrap_or_else(|error| panic!("{context} oracle received malformed CSR graph: {error}"));
crate::dispatch_decode::require_bitset_words(context, seed_bits, words)
.unwrap_or_else(|error| panic!("{context} oracle received malformed seed bitset: {error}"));
let mut reached = zeroed_u32_vec(words, context, "reached bitset");
reached.copy_from_slice(seed_bits);
mask_unused_tail_bits(&mut reached, node_count);
match direction {
CsrClosureDirection::Forward => {
let mut queue = initial_queue(&reached, node_count, context);
#[cfg(all(feature = "simd-oracle", target_arch = "x86_64"))]
{
simd::propagate_forward_fast(
node_count,
edge_offsets,
edge_targets,
edge_kind_mask,
required_edge_mask,
&mut reached,
&mut queue,
);
}
#[cfg(not(all(feature = "simd-oracle", target_arch = "x86_64")))]
{
propagate_forward(
context,
node_count,
edge_offsets,
edge_targets,
edge_kind_mask,
required_edge_mask,
&mut reached,
&mut queue,
);
}
}
CsrClosureDirection::Reverse => {
let reverse = ReverseCsr::build(
context,
nodes,
edge_offsets,
edge_targets,
edge_kind_mask,
required_edge_mask,
);
let mut queue = initial_queue(&reached, node_count, context);
#[cfg(all(feature = "simd-oracle", target_arch = "x86_64"))]
{
simd::propagate_reverse_fast(&reverse, &mut reached, &mut queue);
}
#[cfg(not(all(feature = "simd-oracle", target_arch = "x86_64")))]
{
propagate_reverse(context, &reverse, &mut reached, &mut queue);
}
}
}
reached
}
pub fn propagate_forward(
context: &'static str,
node_count: u32,
edge_offsets: &[u32],
edge_targets: &[u32],
edge_kind_mask: &[u32],
required_edge_mask: u32,
reached: &mut [u32],
queue: &mut Vec<u32>,
) {
let mut cursor = 0usize;
while cursor < queue.len() {
let node = queue[cursor];
cursor += 1;
let node_index = u32_to_usize(node, context, "CSR node index");
let next_node = node.checked_add(1).unwrap_or_else(|| {
panic!(
"{context} oracle CSR node successor index overflowed for node {node}. Fix: shard the graph before CPU parity."
)
});
let next_node_index = u32_to_usize(next_node, context, "CSR next-node index");
let start = u32_to_usize(edge_offsets[node_index], context, "CSR edge start offset");
let end = u32_to_usize(
edge_offsets[next_node_index],
context,
"CSR edge end offset",
);
for edge_index in start..end {
if !edge_matches(edge_kind_mask[edge_index], required_edge_mask) {
continue;
}
let target = edge_targets[edge_index];
if target < node_count && set_bit_once(reached, target, context) {
queue.push(target);
}
}
}
}
fn propagate_reverse(
context: &'static str,
reverse: &ReverseCsr,
reached: &mut [u32],
queue: &mut Vec<u32>,
) {
let mut cursor = 0usize;
while cursor < queue.len() {
let node = u32_to_usize(queue[cursor], context, "reverse closure queue node");
cursor += 1;
for edge_index in reverse.offsets[node]..reverse.offsets[node + 1] {
let source = reverse.sources[edge_index];
if set_bit_once(reached, source, context) {
queue.push(source);
}
}
}
}
#[cfg(all(feature = "simd-oracle", target_arch = "x86_64"))]
mod simd {
use super::*;
use std::arch::x86_64::*;
#[inline]
pub fn propagate_forward_fast(
node_count: u32,
edge_offsets: &[u32],
edge_targets: &[u32],
edge_kind_mask: &[u32],
required_edge_mask: u32,
reached: &mut [u32],
queue: &mut Vec<u32>,
) {
if std::is_x86_feature_detected!("avx2") {
propagate_forward_avx2(
node_count,
edge_offsets,
edge_targets,
edge_kind_mask,
required_edge_mask,
reached,
queue,
);
} else if std::is_x86_feature_detected!("sse2") {
propagate_forward_sse2(
node_count,
edge_offsets,
edge_targets,
edge_kind_mask,
required_edge_mask,
reached,
queue,
);
} else {
propagate_forward(
"simd-fallback",
node_count,
edge_offsets,
edge_targets,
edge_kind_mask,
required_edge_mask,
reached,
queue,
);
}
}
#[inline]
pub(crate) fn propagate_reverse_fast(
reverse: &ReverseCsr,
reached: &mut [u32],
queue: &mut Vec<u32>,
) {
if std::is_x86_feature_detected!("avx2") {
propagate_reverse_avx2(reverse, reached, queue);
} else if std::is_x86_feature_detected!("sse2") {
propagate_reverse_sse2(reverse, reached, queue);
} else {
propagate_reverse("simd-fallback", reverse, reached, queue);
}
}
#[inline]
pub fn propagate_forward_avx2(
node_count: u32,
edge_offsets: &[u32],
edge_targets: &[u32],
edge_kind_mask: &[u32],
required_edge_mask: u32,
reached: &mut [u32],
queue: &mut Vec<u32>,
) {
let node_count = node_count as usize;
let mut cursor = 0usize;
if required_edge_mask == 0 {
while cursor < queue.len() {
let node = queue[cursor] as usize;
cursor += 1;
let start = edge_offsets[node] as usize;
let end = edge_offsets[node + 1] as usize;
let mut ei = start;
while ei + 8 <= end {
let masks = unsafe {
_mm256_loadu_si256(edge_kind_mask.as_ptr().add(ei) as *const __m256i)
};
let zero = unsafe { _mm256_setzero_si256() };
let cmp = unsafe { _mm256_cmpeq_epi32(masks, zero) };
let invalid_mask = unsafe { _mm256_movemask_epi8(cmp) };
if invalid_mask == 0 {
for j in 0..8 {
let target = unsafe { *edge_targets.get_unchecked(ei + j) } as usize;
if target < node_count {
let wi = target >> 5;
let m = 1u32 << (target & 31);
let word = unsafe { reached.get_unchecked_mut(wi) };
if *word & m == 0 {
*word |= m;
queue.push(target as u32);
}
}
}
} else if invalid_mask != -1 {
for j in 0..8 {
let mask = unsafe { *edge_kind_mask.get_unchecked(ei + j) };
if mask != 0 {
let target =
unsafe { *edge_targets.get_unchecked(ei + j) } as usize;
if target < node_count {
let wi = target >> 5;
let m = 1u32 << (target & 31);
let word = unsafe { reached.get_unchecked_mut(wi) };
if *word & m == 0 {
*word |= m;
queue.push(target as u32);
}
}
}
}
}
ei += 8;
}
while ei < end {
let mask = unsafe { *edge_kind_mask.get_unchecked(ei) };
if mask != 0 {
let target = unsafe { *edge_targets.get_unchecked(ei) } as usize;
if target < node_count {
let wi = target >> 5;
let m = 1u32 << (target & 31);
let word = unsafe { reached.get_unchecked_mut(wi) };
if *word & m == 0 {
*word |= m;
queue.push(target as u32);
}
}
}
ei += 1;
}
}
} else {
let req_vec = unsafe { _mm256_set1_epi32(required_edge_mask as i32) };
while cursor < queue.len() {
let node = queue[cursor] as usize;
cursor += 1;
let start = edge_offsets[node] as usize;
let end = edge_offsets[node + 1] as usize;
let mut ei = start;
while ei + 8 <= end {
let masks = unsafe {
_mm256_loadu_si256(edge_kind_mask.as_ptr().add(ei) as *const __m256i)
};
let anded = unsafe { _mm256_and_si256(masks, req_vec) };
let zero = unsafe { _mm256_setzero_si256() };
let cmp = unsafe { _mm256_cmpeq_epi32(anded, zero) };
let invalid_mask = unsafe { _mm256_movemask_epi8(cmp) };
if invalid_mask == 0 {
for j in 0..8 {
let target = unsafe { *edge_targets.get_unchecked(ei + j) } as usize;
if target < node_count {
let wi = target >> 5;
let m = 1u32 << (target & 31);
let word = unsafe { reached.get_unchecked_mut(wi) };
if *word & m == 0 {
*word |= m;
queue.push(target as u32);
}
}
}
} else if invalid_mask != -1 {
for j in 0..8 {
let mask = unsafe { *edge_kind_mask.get_unchecked(ei + j) };
if mask & required_edge_mask != 0 {
let target =
unsafe { *edge_targets.get_unchecked(ei + j) } as usize;
if target < node_count {
let wi = target >> 5;
let m = 1u32 << (target & 31);
let word = unsafe { reached.get_unchecked_mut(wi) };
if *word & m == 0 {
*word |= m;
queue.push(target as u32);
}
}
}
}
}
ei += 8;
}
while ei < end {
let mask = unsafe { *edge_kind_mask.get_unchecked(ei) };
if mask & required_edge_mask != 0 {
let target = unsafe { *edge_targets.get_unchecked(ei) } as usize;
if target < node_count {
let wi = target >> 5;
let m = 1u32 << (target & 31);
let word = unsafe { reached.get_unchecked_mut(wi) };
if *word & m == 0 {
*word |= m;
queue.push(target as u32);
}
}
}
ei += 1;
}
}
}
}
#[inline]
pub fn propagate_forward_sse2(
node_count: u32,
edge_offsets: &[u32],
edge_targets: &[u32],
edge_kind_mask: &[u32],
required_edge_mask: u32,
reached: &mut [u32],
queue: &mut Vec<u32>,
) {
let node_count = node_count as usize;
let mut cursor = 0usize;
if required_edge_mask == 0 {
while cursor < queue.len() {
let node = queue[cursor] as usize;
cursor += 1;
let start = edge_offsets[node] as usize;
let end = edge_offsets[node + 1] as usize;
let mut ei = start;
while ei + 4 <= end {
let masks = unsafe {
_mm_loadu_si128(edge_kind_mask.as_ptr().add(ei) as *const __m128i)
};
let zero = unsafe { _mm_setzero_si128() };
let cmp = unsafe { _mm_cmpeq_epi32(masks, zero) };
let invalid_mask = unsafe { _mm_movemask_ps(_mm_castsi128_ps(cmp)) };
if invalid_mask == 0 {
for j in 0..4 {
let target = unsafe { *edge_targets.get_unchecked(ei + j) } as usize;
if target < node_count {
let wi = target >> 5;
let m = 1u32 << (target & 31);
let word = unsafe { reached.get_unchecked_mut(wi) };
if *word & m == 0 {
*word |= m;
queue.push(target as u32);
}
}
}
} else if invalid_mask != 0xF {
for j in 0..4 {
let mask = unsafe { *edge_kind_mask.get_unchecked(ei + j) };
if mask != 0 {
let target =
unsafe { *edge_targets.get_unchecked(ei + j) } as usize;
if target < node_count {
let wi = target >> 5;
let m = 1u32 << (target & 31);
let word = unsafe { reached.get_unchecked_mut(wi) };
if *word & m == 0 {
*word |= m;
queue.push(target as u32);
}
}
}
}
}
ei += 4;
}
while ei < end {
let mask = unsafe { *edge_kind_mask.get_unchecked(ei) };
if mask != 0 {
let target = unsafe { *edge_targets.get_unchecked(ei) } as usize;
if target < node_count {
let wi = target >> 5;
let m = 1u32 << (target & 31);
let word = unsafe { reached.get_unchecked_mut(wi) };
if *word & m == 0 {
*word |= m;
queue.push(target as u32);
}
}
}
ei += 1;
}
}
} else {
let req_vec = unsafe { _mm_set1_epi32(required_edge_mask as i32) };
while cursor < queue.len() {
let node = queue[cursor] as usize;
cursor += 1;
let start = edge_offsets[node] as usize;
let end = edge_offsets[node + 1] as usize;
let mut ei = start;
while ei + 4 <= end {
let masks = unsafe {
_mm_loadu_si128(edge_kind_mask.as_ptr().add(ei) as *const __m128i)
};
let anded = unsafe { _mm_and_si128(masks, req_vec) };
let zero = unsafe { _mm_setzero_si128() };
let cmp = unsafe { _mm_cmpeq_epi32(anded, zero) };
let invalid_mask = unsafe { _mm_movemask_ps(_mm_castsi128_ps(cmp)) };
if invalid_mask == 0 {
for j in 0..4 {
let target = unsafe { *edge_targets.get_unchecked(ei + j) } as usize;
if target < node_count {
let wi = target >> 5;
let m = 1u32 << (target & 31);
let word = unsafe { reached.get_unchecked_mut(wi) };
if *word & m == 0 {
*word |= m;
queue.push(target as u32);
}
}
}
} else if invalid_mask != 0xF {
for j in 0..4 {
let mask = unsafe { *edge_kind_mask.get_unchecked(ei + j) };
if mask & required_edge_mask != 0 {
let target =
unsafe { *edge_targets.get_unchecked(ei + j) } as usize;
if target < node_count {
let wi = target >> 5;
let m = 1u32 << (target & 31);
let word = unsafe { reached.get_unchecked_mut(wi) };
if *word & m == 0 {
*word |= m;
queue.push(target as u32);
}
}
}
}
}
ei += 4;
}
while ei < end {
let mask = unsafe { *edge_kind_mask.get_unchecked(ei) };
if mask & required_edge_mask != 0 {
let target = unsafe { *edge_targets.get_unchecked(ei) } as usize;
if target < node_count {
let wi = target >> 5;
let m = 1u32 << (target & 31);
let word = unsafe { reached.get_unchecked_mut(wi) };
if *word & m == 0 {
*word |= m;
queue.push(target as u32);
}
}
}
ei += 1;
}
}
}
}
#[inline]
pub(crate) fn propagate_reverse_avx2(
reverse: &ReverseCsr,
reached: &mut [u32],
queue: &mut Vec<u32>,
) {
let mut cursor = 0usize;
while cursor < queue.len() {
let node = queue[cursor] as usize;
cursor += 1;
let start = reverse.offsets[node];
let end = reverse.offsets[node + 1];
for edge_index in start..end {
let source = unsafe { *reverse.sources.get_unchecked(edge_index) } as usize;
let wi = source >> 5;
let mask = 1u32 << (source & 31);
let word = unsafe { reached.get_unchecked_mut(wi) };
if *word & mask == 0 {
*word |= mask;
queue.push(source as u32);
}
}
}
}
#[inline]
pub(crate) fn propagate_reverse_sse2(
reverse: &ReverseCsr,
reached: &mut [u32],
queue: &mut Vec<u32>,
) {
propagate_reverse_avx2(reverse, reached, queue);
}
}
#[cfg(all(feature = "simd-oracle", target_arch = "x86_64"))]
pub use simd::{propagate_forward_avx2, propagate_forward_fast, propagate_forward_sse2};
pub(crate) struct ReverseCsr {
offsets: Vec<usize>,
sources: Vec<u32>,
}
impl ReverseCsr {
fn build(
context: &'static str,
nodes: usize,
edge_offsets: &[u32],
edge_targets: &[u32],
edge_kind_mask: &[u32],
required_edge_mask: u32,
) -> Self {
let mut counts = zeroed_usize_vec(nodes, context, "reverse predecessor counts");
for source in 0..nodes {
let start = u32_to_usize(edge_offsets[source], context, "reverse edge start offset");
let end = u32_to_usize(edge_offsets[source + 1], context, "reverse edge end offset");
for edge in start..end {
if !edge_matches(edge_kind_mask[edge], required_edge_mask) {
continue;
}
let target = u32_to_usize(edge_targets[edge], context, "reverse edge target");
if target < nodes {
counts[target] = counts[target].checked_add(1).unwrap_or_else(|| {
panic!(
"{context} reverse predecessor count overflowed for node {target}. Fix: shard the graph before CPU parity."
)
});
}
}
}
let mut offsets = zeroed_usize_vec(nodes.saturating_add(1), context, "reverse offsets");
for node in 0..nodes {
offsets[node + 1] = offsets[node].checked_add(counts[node]).unwrap_or_else(|| {
panic!(
"{context} reverse offset overflowed at node {node}. Fix: shard the graph before CPU parity."
)
});
}
let edge_count = offsets[nodes];
let mut sources = zeroed_u32_vec(edge_count, context, "reverse sources");
let mut cursors = offsets.clone();
for source in 0..nodes {
let source_u32 = usize_to_u32(source, context, "reverse source node");
let start = u32_to_usize(edge_offsets[source], context, "reverse fill edge start");
let end = u32_to_usize(edge_offsets[source + 1], context, "reverse fill edge end");
for edge in start..end {
if !edge_matches(edge_kind_mask[edge], required_edge_mask) {
continue;
}
let target = u32_to_usize(edge_targets[edge], context, "reverse fill target");
if target < nodes {
let slot = cursors[target];
sources[slot] = source_u32;
cursors[target] += 1;
}
}
}
Self { offsets, sources }
}
}
fn initial_queue(bits: &[u32], node_count: u32, context: &'static str) -> Vec<u32> {
let mut queue = crate::staging_reserve::reserved_vec(
u32_to_usize(node_count, context, "initial queue node count"),
context,
)
.unwrap_or_else(|error| panic!("{context} initial queue reservation failed: {error}"));
let words = bits.len();
for word_idx in 0..words {
let mut w = bits[word_idx];
if w == 0 {
continue;
}
let base = word_idx * 32;
while w != 0 {
let tz = w.trailing_zeros();
queue.push((base + tz as usize) as u32);
w &= w - 1;
}
}
while let Some(&last) = queue.last() {
if last >= node_count {
queue.pop();
} else {
break;
}
}
queue
}
#[inline(always)]
fn edge_matches(edge_kind: u32, required_edge_mask: u32) -> bool {
if required_edge_mask == 0 {
edge_kind != 0
} else {
edge_kind & required_edge_mask != 0
}
}
fn set_bit_once(bits: &mut [u32], node: u32, context: &'static str) -> bool {
let word_index = bitset_word_index(node, context);
let mask = 1u32 << (node % 32);
let word = &mut bits[word_index];
if *word & mask != 0 {
return false;
}
*word |= mask;
true
}
fn bitset_words(nodes: usize, context: &'static str) -> usize {
nodes
.checked_add(31)
.unwrap_or_else(|| {
panic!(
"{context} node count overflows host bitset word calculation. Fix: shard the oracle graph."
)
})
/ 32
}
fn bitset_word_index(node: u32, context: &'static str) -> usize {
u32_to_usize(node / 32, context, "bitset word index")
}
fn mask_unused_tail_bits(bits: &mut [u32], node_count: u32) {
let used = node_count % 32;
if used == 0 || bits.is_empty() {
return;
}
let mask = (1u32 << used) - 1;
if let Some(last) = bits.last_mut() {
*last &= mask;
}
}
fn zeroed_u32_vec(len: usize, context: &'static str, label: &'static str) -> Vec<u32> {
let mut out = crate::staging_reserve::reserved_vec(len, label)
.unwrap_or_else(|error| panic!("{context} {label} reservation failed: {error}"));
out.resize(len, 0);
out
}
fn zeroed_usize_vec(len: usize, context: &'static str, label: &'static str) -> Vec<usize> {
let mut out = crate::staging_reserve::reserved_vec(len, label)
.unwrap_or_else(|error| panic!("{context} {label} reservation failed: {error}"));
out.resize(len, 0);
out
}
fn u32_to_usize(value: u32, context: &'static str, label: &'static str) -> usize {
usize::try_from(value).unwrap_or_else(|source| {
panic!(
"{context} {label} value {value} cannot fit usize: {source}. Fix: shard the graph before CPU parity."
)
})
}
fn usize_to_u32(value: usize, context: &'static str, label: &'static str) -> u32 {
u32::try_from(value).unwrap_or_else(|source| {
panic!(
"{context} {label} value {value} cannot fit u32: {source}. Fix: shard the graph before CPU parity."
)
})
}
#[cfg(test)]
mod tests {
use super::*;
use vyre_primitives::predicate::edge_kind::CONTROL;
#[test]
fn forward_closure_masks_seed_tail_bits_and_follows_matching_edges() {
let out = csr_bitset_closure(
"test_forward_closure",
3,
&[0, 1, 2, 2],
&[1, 2],
&[CONTROL, CONTROL],
&[0xFFFF_FFFF],
CONTROL,
CsrClosureDirection::Forward,
);
assert_eq!(out, vec![0b111]);
}
#[test]
fn reverse_closure_follows_predecessors_without_reverse_oracle_duplication() {
let out = csr_bitset_closure(
"test_reverse_closure",
4,
&[0, 1, 2, 3, 3],
&[1, 2, 3],
&[CONTROL, CONTROL, 0],
&[0b0100],
CONTROL,
CsrClosureDirection::Reverse,
);
assert_eq!(out, vec![0b0111]);
}
#[test]
fn malformed_seed_is_rejected_before_closure_allocation() {
let panic = std::panic::catch_unwind(|| {
let _ = csr_bitset_closure(
"test_malformed_seed",
1_000_000_000,
&[],
&[],
&[],
&[],
CONTROL,
CsrClosureDirection::Forward,
);
})
.expect_err("Fix: malformed CSR/seed must be rejected before closure allocation.");
let message = if let Some(message) = panic.downcast_ref::<String>() {
message.as_str()
} else if let Some(message) = panic.downcast_ref::<&'static str>() {
*message
} else {
"<non-string panic payload>"
};
assert!(
message.contains("malformed CSR graph"),
"Fix: shared closure oracle must validate CSR shape before allocating reached bitsets; got {message}"
);
}
#[test]
fn malformed_csr_rejects_nonzero_first_offset() {
let panic = std::panic::catch_unwind(|| {
let _ = csr_bitset_closure(
"test_malformed_csr",
2,
&[1, 1, 1],
&[0],
&[0],
&[0b1],
CONTROL,
CsrClosureDirection::Forward,
);
})
.expect_err("nonzero first offset must panic");
let msg = panic_message(&panic);
assert!(msg.contains("edge_offsets[0]"), "got {msg}");
}
#[test]
fn malformed_seed_bitset_rejects_wrong_length() {
let panic = std::panic::catch_unwind(|| {
let _ = csr_bitset_closure(
"test_malformed_seed_len",
3,
&[0, 1, 2, 2],
&[1, 2],
&[CONTROL, CONTROL],
&[0b1, 0b0],
CONTROL,
CsrClosureDirection::Forward,
);
})
.expect_err("wrong seed bitset length must panic");
let msg = panic_message(&panic);
assert!(msg.contains("malformed seed bitset"), "got {msg}");
}
#[test]
fn forward_closure_with_zero_node_count_and_empty_seed() {
let out = csr_bitset_closure(
"test_zero_nodes",
0,
&[0],
&[],
&[],
&[],
CONTROL,
CsrClosureDirection::Forward,
);
assert_eq!(out, Vec::<u32>::new());
}
#[test]
fn reverse_closure_with_zero_node_count_and_empty_seed() {
let out = csr_bitset_closure(
"test_zero_nodes_reverse",
0,
&[0],
&[],
&[],
&[],
CONTROL,
CsrClosureDirection::Reverse,
);
assert_eq!(out, Vec::<u32>::new());
}
#[test]
fn forward_closure_rejects_target_out_of_bounds() {
let panic = std::panic::catch_unwind(|| {
let _ = csr_bitset_closure(
"test_oob_target",
2,
&[0, 1, 1],
&[2],
&[CONTROL],
&[0b1],
CONTROL,
CsrClosureDirection::Forward,
);
})
.expect_err("OOB target must panic");
let msg = panic_message(&panic);
assert!(msg.contains("targets node 2"), "got {msg}");
}
#[test]
fn reverse_closure_rejects_target_out_of_bounds() {
let panic = std::panic::catch_unwind(|| {
let _ = csr_bitset_closure(
"test_oob_target_reverse",
2,
&[0, 1, 1],
&[2],
&[CONTROL],
&[0b1],
CONTROL,
CsrClosureDirection::Reverse,
);
})
.expect_err("OOB target must panic");
let msg = panic_message(&panic);
assert!(msg.contains("targets node 2"), "got {msg}");
}
#[cfg(all(feature = "simd-oracle", target_arch = "x86_64"))]
mod simd_parity {
use super::*;
fn run_both_forward(
node_count: u32,
edge_offsets: &[u32],
edge_targets: &[u32],
edge_kind_mask: &[u32],
seed_bits: &[u32],
required_edge_mask: u32,
) -> (Vec<u32>, Vec<u32>) {
let words = ((node_count + 31) / 32) as usize;
let mut reached_scalar = vec![0u32; words];
reached_scalar.copy_from_slice(seed_bits);
let mut queue_scalar = vec![0u32];
propagate_forward(
"parity",
node_count,
edge_offsets,
edge_targets,
edge_kind_mask,
required_edge_mask,
&mut reached_scalar,
&mut queue_scalar,
);
let mut reached_simd = vec![0u32; words];
reached_simd.copy_from_slice(seed_bits);
let mut queue_simd = vec![0u32];
simd::propagate_forward_fast(
node_count,
edge_offsets,
edge_targets,
edge_kind_mask,
required_edge_mask,
&mut reached_simd,
&mut queue_simd,
);
(reached_scalar, reached_simd)
}
#[test]
fn simd_parity_chain_1k() {
let n = 1_000u32;
let mut offsets = vec![0u32; n as usize + 1];
let mut targets = Vec::with_capacity(n as usize);
let mut masks = Vec::with_capacity(n as usize);
for i in 0..n {
if i + 1 < n {
targets.push(i + 1);
masks.push(CONTROL);
offsets[i as usize + 1] = offsets[i as usize] + 1;
} else {
offsets[i as usize + 1] = offsets[i as usize];
}
}
let words = ((n + 31) / 32) as usize;
let mut seed = vec![0u32; words];
seed[0] = 1;
let (scalar, simd) = run_both_forward(n, &offsets, &targets, &masks, &seed, CONTROL);
assert_eq!(scalar, simd, "SIMD parity mismatch on chain 1k");
}
#[test]
fn simd_parity_chain_100k() {
let n = 100_000u32;
let mut offsets = vec![0u32; n as usize + 1];
let mut targets = Vec::with_capacity(n as usize);
let mut masks = Vec::with_capacity(n as usize);
for i in 0..n {
if i + 1 < n {
targets.push(i + 1);
masks.push(CONTROL);
offsets[i as usize + 1] = offsets[i as usize] + 1;
} else {
offsets[i as usize + 1] = offsets[i as usize];
}
}
let words = ((n + 31) / 32) as usize;
let mut seed = vec![0u32; words];
seed[0] = 1;
let (scalar, simd) = run_both_forward(n, &offsets, &targets, &masks, &seed, CONTROL);
assert_eq!(scalar, simd, "SIMD parity mismatch on chain 100k");
}
#[test]
fn simd_parity_chain_1m() {
let n = 1_000_000u32;
let mut offsets = vec![0u32; n as usize + 1];
let mut targets = Vec::with_capacity(n as usize);
let mut masks = Vec::with_capacity(n as usize);
for i in 0..n {
if i + 1 < n {
targets.push(i + 1);
masks.push(CONTROL);
offsets[i as usize + 1] = offsets[i as usize] + 1;
} else {
offsets[i as usize + 1] = offsets[i as usize];
}
}
let words = ((n + 31) / 32) as usize;
let mut seed = vec![0u32; words];
seed[0] = 1;
let (scalar, simd) = run_both_forward(n, &offsets, &targets, &masks, &seed, CONTROL);
assert_eq!(scalar, simd, "SIMD parity mismatch on chain 1M");
}
#[test]
fn simd_parity_fanout_100k() {
let n = 100_000u32;
let mut offsets = vec![0u32; n as usize + 1];
let mut targets = Vec::with_capacity(n as usize * 3);
let mut masks = Vec::with_capacity(n as usize * 3);
for i in 0..n {
let row_start = targets.len() as u32;
for delta in 1..=3 {
let dst = i.saturating_add(delta);
if dst < n {
targets.push(dst);
masks.push(CONTROL);
}
}
offsets[i as usize + 1] = row_start + (targets.len() as u32 - row_start);
}
let words = ((n + 31) / 32) as usize;
let mut seed = vec![0u32; words];
seed[0] = 1;
let (scalar, simd) = run_both_forward(n, &offsets, &targets, &masks, &seed, CONTROL);
assert_eq!(scalar, simd, "SIMD parity mismatch on fanout 100k");
}
#[test]
fn simd_parity_with_filtered_edges() {
let n = 1_000u32;
let mut offsets = vec![0u32; n as usize + 1];
let mut targets = Vec::with_capacity(n as usize);
let mut masks = Vec::with_capacity(n as usize);
for i in 0..n {
if i + 1 < n {
targets.push(i + 1);
masks.push(if i % 2 == 0 { CONTROL } else { 0 });
offsets[i as usize + 1] = offsets[i as usize] + 1;
} else {
offsets[i as usize + 1] = offsets[i as usize];
}
}
let words = ((n + 31) / 32) as usize;
let mut seed = vec![0u32; words];
seed[0] = 1;
let (scalar, simd) = run_both_forward(n, &offsets, &targets, &masks, &seed, CONTROL);
assert_eq!(scalar, simd, "SIMD parity mismatch on filtered edges");
}
#[test]
fn simd_parity_dense_frontier() {
let n = 1_024u32;
let mut offsets = vec![0u32; n as usize + 1];
let mut targets = Vec::with_capacity(n as usize);
let mut masks = Vec::with_capacity(n as usize);
for i in 0..n {
let row_start = targets.len() as u32;
for delta in 1..=16 {
let dst = i.saturating_add(delta);
if dst < n {
targets.push(dst);
masks.push(CONTROL);
}
}
offsets[i as usize + 1] = row_start + (targets.len() as u32 - row_start);
}
let words = ((n + 31) / 32) as usize;
let seed = vec![0xFFFF_FFFFu32; words];
let (scalar, simd) = run_both_forward(n, &offsets, &targets, &masks, &seed, CONTROL);
assert_eq!(scalar, simd, "SIMD parity mismatch on dense frontier");
}
fn run_both_reverse(
node_count: u32,
edge_offsets: &[u32],
edge_targets: &[u32],
edge_kind_mask: &[u32],
seed_bits: &[u32],
required_edge_mask: u32,
) -> (Vec<u32>, Vec<u32>) {
let nodes = node_count as usize;
let words = ((node_count + 31) / 32) as usize;
let reverse_scalar = ReverseCsr::build(
"parity",
nodes,
edge_offsets,
edge_targets,
edge_kind_mask,
required_edge_mask,
);
let mut reached_scalar = vec![0u32; words];
reached_scalar.copy_from_slice(seed_bits);
let mut queue_scalar = vec![0u32];
propagate_reverse(
"parity",
&reverse_scalar,
&mut reached_scalar,
&mut queue_scalar,
);
let reverse_simd = ReverseCsr::build(
"parity",
nodes,
edge_offsets,
edge_targets,
edge_kind_mask,
required_edge_mask,
);
let mut reached_simd = vec![0u32; words];
reached_simd.copy_from_slice(seed_bits);
let mut queue_simd = vec![0u32];
simd::propagate_reverse_fast(&reverse_simd, &mut reached_simd, &mut queue_simd);
(reached_scalar, reached_simd)
}
#[test]
fn simd_parity_reverse_chain_100k() {
let n = 100_000u32;
let mut offsets = vec![0u32; n as usize + 1];
let mut targets = Vec::with_capacity(n as usize);
let mut masks = Vec::with_capacity(n as usize);
for i in 0..n {
if i + 1 < n {
targets.push(i + 1);
masks.push(CONTROL);
offsets[i as usize + 1] = offsets[i as usize] + 1;
} else {
offsets[i as usize + 1] = offsets[i as usize];
}
}
let words = ((n + 31) / 32) as usize;
let mut seed = vec![0u32; words];
seed[((n - 1) / 32) as usize] |= 1u32 << ((n - 1) % 32);
let (scalar, simd) = run_both_reverse(n, &offsets, &targets, &masks, &seed, CONTROL);
assert_eq!(scalar, simd, "SIMD parity mismatch on reverse chain 100k");
}
#[test]
fn simd_parity_reverse_fanout_100k() {
let n = 100_000u32;
let mut offsets = vec![0u32; n as usize + 1];
let mut targets = Vec::with_capacity(n as usize * 3);
let mut masks = Vec::with_capacity(n as usize * 3);
for i in 0..n {
let row_start = targets.len() as u32;
for delta in 1..=3 {
let dst = i.saturating_add(delta);
if dst < n {
targets.push(dst);
masks.push(CONTROL);
}
}
offsets[i as usize + 1] = row_start + (targets.len() as u32 - row_start);
}
let words = ((n + 31) / 32) as usize;
let mut seed = vec![0u32; words];
seed[((n - 1) / 32) as usize] |= 1u32 << ((n - 1) % 32);
let (scalar, simd) = run_both_reverse(n, &offsets, &targets, &masks, &seed, CONTROL);
assert_eq!(scalar, simd, "SIMD parity mismatch on reverse fanout 100k");
}
}
fn panic_message(panic: &Box<dyn std::any::Any + Send>) -> String {
if let Some(s) = (**panic).downcast_ref::<String>() {
s.clone()
} else if let Some(s) = (**panic).downcast_ref::<&'static str>() {
(*s).to_string()
} else {
"<non-string>".to_string()
}
}
}