Skip to main content

faultscope_core/
expr.rs

1use crate::Mask;
2use smallvec::{smallvec, SmallVec};
3
4#[derive(Clone, Debug, Default, PartialEq, Eq)]
5pub struct Expr {
6    terms: SmallVec<[usize; 4]>,
7    constant: bool,
8}
9
10impl Expr {
11    pub fn constant(value: bool) -> Self {
12        Self {
13            terms: SmallVec::new(),
14            constant: value,
15        }
16    }
17
18    pub fn random(source: usize) -> Self {
19        Self {
20            terms: smallvec![source],
21            constant: false,
22        }
23    }
24
25    pub fn terms(&self) -> &[usize] {
26        &self.terms
27    }
28
29    pub fn constant_value(&self) -> bool {
30        self.constant
31    }
32
33    pub fn xor_assign(&mut self, other: &Expr) {
34        self.constant ^= other.constant;
35        if other.terms.is_empty() {
36            return;
37        }
38        if self.terms.is_empty() {
39            self.terms.clone_from(&other.terms);
40            return;
41        }
42        if self.terms.len() + other.terms.len() <= 4 {
43            for term in other.terms.iter().copied() {
44                self.toggle_term(term);
45            }
46            return;
47        }
48        let left = std::mem::take(&mut self.terms);
49        let mut out = SmallVec::with_capacity(left.len() + other.terms.len());
50        let mut left_idx = 0;
51        let mut right_idx = 0;
52        while left_idx < left.len() && right_idx < other.terms.len() {
53            match left[left_idx].cmp(&other.terms[right_idx]) {
54                std::cmp::Ordering::Less => {
55                    out.push(left[left_idx]);
56                    left_idx += 1;
57                }
58                std::cmp::Ordering::Greater => {
59                    out.push(other.terms[right_idx]);
60                    right_idx += 1;
61                }
62                std::cmp::Ordering::Equal => {
63                    left_idx += 1;
64                    right_idx += 1;
65                }
66            }
67        }
68        out.extend_from_slice(&left[left_idx..]);
69        out.extend_from_slice(&other.terms[right_idx..]);
70        self.terms = out;
71    }
72
73    pub(crate) fn toggle_term(&mut self, term: usize) {
74        match self.terms.binary_search(&term) {
75            Ok(index) => {
76                self.terms.remove(index);
77            }
78            Err(index) => self.terms.insert(index, term),
79        }
80    }
81
82    pub fn toggle_constant(&mut self) {
83        self.constant ^= true;
84    }
85
86    pub fn eval(&self, random_masks: &[Mask], words: usize, all_mask: &Mask) -> Mask {
87        let mut out = Mask::zero(words);
88        if self.constant {
89            out.xor_assign(all_mask);
90        }
91        for source in &self.terms {
92            out.xor_assign(&random_masks[*source]);
93        }
94        out
95    }
96
97    pub(crate) fn eval_flat(&self, random_masks: &[u64], words: usize, all_mask: &Mask) -> Mask {
98        let mut out = Mask::zero(words);
99        if self.constant {
100            out.xor_assign(all_mask);
101        }
102        for source in &self.terms {
103            let start = source * words;
104            for (target, random) in out
105                .words
106                .iter_mut()
107                .zip(&random_masks[start..start + words])
108            {
109                *target ^= random;
110            }
111        }
112        out
113    }
114}
115
116#[cfg(test)]
117mod tests {
118    use super::*;
119
120    #[test]
121    fn xor_assign_cancels_duplicate_terms() {
122        let mut expr = Expr::random(2);
123        expr.xor_assign(&Expr::random(1));
124        expr.xor_assign(&Expr::random(2));
125
126        assert_eq!(expr.terms(), &[1]);
127        assert!(!expr.constant_value());
128    }
129
130    #[test]
131    fn xor_assign_merges_sorted_terms_by_symmetric_difference() {
132        let mut left = Expr {
133            terms: vec![1, 3, 5, 8].into(),
134            constant: true,
135        };
136        let right = Expr {
137            terms: vec![0, 3, 4, 8, 9].into(),
138            constant: true,
139        };
140
141        left.xor_assign(&right);
142
143        assert_eq!(left.terms(), &[0, 1, 4, 5, 9]);
144        assert!(!left.constant_value());
145    }
146
147    #[test]
148    fn xor_assign_matches_randomized_symmetric_differences() {
149        let mut state = 0x9e37_79b9_7f4a_7c15u64;
150        for _ in 0..128 {
151            let mut left_terms = Vec::new();
152            let mut right_terms = Vec::new();
153            let mut expected = Vec::new();
154            for term in 0..96 {
155                state = state
156                    .wrapping_mul(6_364_136_223_846_793_005)
157                    .wrapping_add(1);
158                let in_left = state >> 63 != 0;
159                state = state
160                    .wrapping_mul(6_364_136_223_846_793_005)
161                    .wrapping_add(1);
162                let in_right = state >> 63 != 0;
163                if in_left {
164                    left_terms.push(term);
165                }
166                if in_right {
167                    right_terms.push(term);
168                }
169                if in_left ^ in_right {
170                    expected.push(term);
171                }
172            }
173            let mut left = Expr {
174                terms: left_terms.into(),
175                constant: false,
176            };
177            left.xor_assign(&Expr {
178                terms: right_terms.into(),
179                constant: true,
180            });
181            assert_eq!(left.terms(), expected);
182            assert!(left.constant_value());
183        }
184    }
185
186    #[test]
187    fn eval_includes_constant_mask() {
188        let expr = Expr::constant(true);
189        let all = Mask { words: vec![0b101] };
190
191        assert_eq!(expr.eval(&[], 1, &all), all);
192    }
193}