vyre_primitives/bitset/
equal.rs

1//! `bitset_equal`  -  exact-equality check, writes 1 to `out_scalar`
2//! iff every word of `lhs` equals the corresponding word of `rhs`.
3//!
4//! Used by fixpoint convergence checks: "did the frontier change?"
5//! is `bitset_equal(prev, current, out_scalar)` then "if out == 1 stop."
6
7use vyre_foundation::ir::Program;
8
9use crate::bitset::relation::{bitset_relation_program, BitsetRelation};
10
11/// Canonical op id.
12pub const OP_ID: &str = "vyre-primitives::bitset::equal";
13
14/// Build a Program: `out_scalar[0] = (forall w: lhs[w] == rhs[w]) ? 1 : 0`.
15///
16/// One-dispatch reduction: lane 0 initializes the output to true, then
17/// every lane scans its chunk-strided words and atomically ANDs its
18/// equality predicate into the scalar.
19#[must_use]
20pub fn bitset_equal(lhs: &str, rhs: &str, out_scalar: &str, words: u32) -> Program {
21    bitset_relation_program(OP_ID, lhs, rhs, out_scalar, words, BitsetRelation::Equal)
22}
23
24/// Return whether `program` advertises the canonical `bitset_equal` op id.
25///
26/// Consumer crates should use this semantic tag helper instead of inspecting
27/// the raw IR entry shape.
28#[must_use]
29pub fn is_bitset_equal_program(program: &Program) -> bool {
30    if program.entry_op_id.as_deref() == Some(OP_ID) {
31        return true;
32    }
33    matches!(
34        program.entry.as_slice(),
35        [vyre_foundation::ir::Node::Region { generator, .. }] if generator.as_ref() == OP_ID
36    )
37}
38
39/// CPU reference: returns 1 iff every word matches, 0 otherwise.
40#[cfg(any(test, feature = "cpu-parity"))]
41#[must_use]
42pub fn cpu_ref(lhs: &[u32], rhs: &[u32]) -> u32 {
43    if lhs.len() != rhs.len() {
44        return 0;
45    }
46    if lhs.iter().zip(rhs.iter()).all(|(a, b)| a == b) {
47        1
48    } else {
49        0
50    }
51}
52
53#[cfg(feature = "inventory-registry")]
54inventory::submit! {
55    vyre_foundation::operation::OperationRegistration::primitive(
56        OP_ID,
57        || bitset_equal("lhs", "rhs", "out", 2),
58        Some(|| {
59            let to_bytes = |w: &[u32]| crate::wire::pack_u32_slice(w);
60            vec![vec![
61                to_bytes(&[0xFFFF, 0xF0F0]),
62                to_bytes(&[0xFFFF, 0xF0F0]),
63                to_bytes(&[0]),
64            ]]
65        }),
66        Some(|| {
67            let to_bytes = |w: &[u32]| crate::wire::pack_u32_slice(w);
68            vec![vec![to_bytes(&[1])]]
69        }),
70    )
71}
72
73#[cfg(test)]
74mod tests {
75    use super::*;
76    use vyre_foundation::ir::Node;
77
78    #[test]
79    fn identical_returns_one() {
80        assert_eq!(cpu_ref(&[0xDEAD, 0xBEEF], &[0xDEAD, 0xBEEF]), 1);
81    }
82
83    #[test]
84    fn differs_in_first_word_returns_zero() {
85        assert_eq!(cpu_ref(&[0xDEAD, 0xBEEF], &[0xDEAE, 0xBEEF]), 0);
86    }
87
88    #[test]
89    fn differs_in_last_word_returns_zero() {
90        assert_eq!(cpu_ref(&[0, 0, 1], &[0, 0, 0]), 0);
91    }
92
93    #[test]
94    fn empty_pair_returns_one() {
95        assert_eq!(cpu_ref(&[], &[]), 1);
96    }
97
98    #[test]
99    fn length_mismatch_returns_zero() {
100        assert_eq!(cpu_ref(&[0], &[0, 0]), 0);
101    }
102
103    #[test]
104    fn preserves_wrapper_op_id() {
105        let program = bitset_equal("lhs", "rhs", "out", 2);
106        let generator = match &program.entry[0] {
107            Node::Region { generator, .. } => generator.to_string(),
108            other => panic!("Fix: bitset_equal must build a Region entry, got {other:?}."),
109        };
110        assert_eq!(generator, OP_ID);
111        assert!(is_bitset_equal_program(&program));
112    }
113
114    #[test]
115    fn generated_adversarial_pairs_match_exact_equality_contract() {
116        let mut state = 0xA5A5_5A5A_u32;
117        for case in 0..4096 {
118            state = state.wrapping_mul(1_664_525).wrapping_add(1_013_904_223);
119            let len = (state as usize % 17) + 1;
120            let mut lhs = Vec::with_capacity(len);
121            let mut rhs = Vec::with_capacity(len);
122            for word in 0..len {
123                state = state.rotate_left(5) ^ (case as u32).wrapping_mul(0x9E37_79B9);
124                let value = state ^ (word as u32).wrapping_mul(0x85EB_CA6B);
125                lhs.push(value);
126                rhs.push(if case % 4 == 0 {
127                    value
128                } else {
129                    value ^ (1_u32 << ((case + word) & 31))
130                });
131            }
132            let expected = u32::from(lhs == rhs);
133            assert_eq!(cpu_ref(&lhs, &rhs), expected, "case {case}");
134        }
135    }
136}
vyre_primitives/bitset/equal.rs

vyre_primitives/bitset/
equal.rs
