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}