fast_boolean_anf_transform/
lib.rs

1//! # Fast Boolean Algebraic Normal Form (ANF) Transformation functions
2//! This crate provides two functions to transform cellular automata truth tables expressed as unsigned integers or boolean arrays into their Algebraic Normal Form (ANF) representation.
3
4use std::mem::size_of;
5use num_traits::{AsPrimitive, Bounded, NumCast, Unsigned};
6
7/// Fast ANF transformation for cellular automata truth table rules expressed as unsigned integers
8/// # Arguments
9/// * `rule_number` - The rule number truth table to transform
10/// * `num_variables_function` - The number of variables in the cellular automata function
11/// # Returns
12/// The ANF transformed rule number, as unsigned integer
13/// # Panics
14/// Panics if the unsigned type is not large enough to hold the rule number (debug only)
15/// Panics if the rule number is greater than or equal to 2^(2^n), n being the number of variables in the function, as the rule number cannot exist (debug only)
16/// # Example
17/// ```
18/// use fast_boolean_anf_transform::fast_bool_anf_transform_unsigned;
19/// assert_eq!(fast_bool_anf_transform_unsigned(3u32, 2), 5); // rule 3: 1 ^ x1
20/// ```
21pub fn fast_bool_anf_transform_unsigned<
22    U: Unsigned
23        + std::ops::Shr<U, Output = U>
24        + std::ops::Shl<U, Output = U>
25        + std::ops::BitOr<U, Output = U>
26        + std::ops::BitAnd<U, Output = U>
27        + PartialOrd<U>
28        + std::ops::Not<Output = U>
29        + NumCast
30        + Bounded
31        + AsPrimitive<usize>
32        + Copy,
33>(
34    rule_number: U,
35    num_variables_function: usize,
36) -> U
37{
38    let u0: U = U::from(0).unwrap();
39    let u1: U = U::from(1).unwrap();
40    let unum_variables_function = U::from(num_variables_function).unwrap();
41
42    #[cfg(debug_assertions)]
43    if (size_of::<U>() << 3) < (1 << num_variables_function) {
44        panic!("Unsigned type is not large enough to hold the rule number, please use a larger unsigned type");
45    }
46
47    #[cfg(debug_assertions)]
48    if rule_number > (U::max_value() >> U::from((size_of::<U>() << 3) - (1 << num_variables_function)).unwrap()) {
49        panic!("The rule number must be less than 2^(2^n), n being the number of variables in the function");
50    }
51
52    let mut blocksize = u1;
53    let mut final_f = rule_number;
54    for _ in 0..num_variables_function {
55        let mut source = u0;
56        while source < (u1 << unum_variables_function) {
57            let target = source + blocksize;
58            for i in 0..blocksize.as_() {
59                let i = U::from(i).unwrap();
60                let f_target_i: bool = ((final_f >> (target + i)) & u1) != u0;
61                let f_source_i: bool = ((final_f >> (source + i)) & u1) != u0;
62                let f_target_i_xor_f_source_i = f_target_i ^ f_source_i;
63                if f_target_i_xor_f_source_i {
64                    final_f = final_f | (u1 << (target + i));
65                } else {
66                    final_f = final_f & !(u1 << (target + i));
67                }
68            }
69            source = source + (blocksize << u1);
70        }
71        blocksize = blocksize << u1;
72    }
73    final_f
74}
75
76/// Fast ANF transformation for cellular automata truth table rules expressed as boolean arrays
77/// # Arguments
78/// * `rule_truth_table` - The rule truth table to transform, first element is the output for input 0, second element is the output for input 1, etc.
79/// # Returns
80/// The ANF transformed rule truth table, as boolean array
81/// # Panics
82/// Panics if the rule truth table length is not equal to 2^n, n being the number of variables in the function (debug only)
83/// # Example
84/// ```
85/// use fast_boolean_anf_transform::fast_bool_anf_transform_bool_array;
86/// let mut rule_truth_table = [false, true, false, false];
87/// fast_bool_anf_transform_bool_array(&mut rule_truth_table);
88/// assert_eq!(rule_truth_table, [false, true, false, true]); // rule 2: x0 ^ (x0 . x1)
89pub fn fast_bool_anf_transform_bool_array(rule_truth_table: &mut [bool]) {
90    let mut blocksize = 1;
91    let input_size = rule_truth_table.len().trailing_zeros() as usize;
92
93    #[cfg(debug_assertions)]
94    if rule_truth_table.len() != 1 << input_size {
95        panic!("The input truth table must have a size of 2^n, n being the number of variables in the function");
96    }
97
98    for _ in 0..input_size {
99        let mut source = 0;
100        while source < (1<<input_size) {
101            let target = source + blocksize;
102            for i in 0..blocksize {
103                rule_truth_table[target + i] ^= rule_truth_table[source + i];
104            }
105            source = source + (blocksize << 1);
106        }
107        blocksize = blocksize << 1;
108    }
109}
110
111#[cfg(test)]
112mod tests {
113    use super::{fast_bool_anf_transform_bool_array, fast_bool_anf_transform_unsigned};
114    #[test]
115    fn test_fast_bool_anf_transform_unsigned() {
116        assert_eq!(fast_bool_anf_transform_unsigned(0u32, 2), 0);
117        assert_eq!(fast_bool_anf_transform_unsigned(1u32, 2), 15);
118        assert_eq!(fast_bool_anf_transform_unsigned(2u32, 2), 10);
119        assert_eq!(fast_bool_anf_transform_unsigned(3u32, 2), 5);
120        assert_eq!(fast_bool_anf_transform_unsigned(4u32, 2), 12);
121        assert_eq!(fast_bool_anf_transform_unsigned(5u32, 2), 3);
122        assert_eq!(fast_bool_anf_transform_unsigned(6u32, 2), 6);
123        assert_eq!(fast_bool_anf_transform_unsigned(7u32, 2), 9);
124        assert_eq!(fast_bool_anf_transform_unsigned(8u32, 2), 8);
125        assert_eq!(fast_bool_anf_transform_unsigned(9u32, 2), 7);
126        assert_eq!(fast_bool_anf_transform_unsigned(10u32, 2), 2);
127        assert_eq!(fast_bool_anf_transform_unsigned(11u32, 2), 13);
128        assert_eq!(fast_bool_anf_transform_unsigned(12u32, 2), 4);
129        assert_eq!(fast_bool_anf_transform_unsigned(13u32, 2), 11);
130        assert_eq!(fast_bool_anf_transform_unsigned(14u32, 2), 14);
131        assert_eq!(fast_bool_anf_transform_unsigned(15u32, 2), 1);
132
133        assert_eq!(fast_bool_anf_transform_unsigned(240u32, 3), 16);
134        assert_eq!(fast_bool_anf_transform_unsigned(30u32, 3), 30);
135        assert_eq!(fast_bool_anf_transform_unsigned(30u8, 3), 30);
136    }
137
138    #[test]
139    #[should_panic]
140    fn test_fast_bool_anf_transform_unsigned_rule_number_too_large() {
141        let _ = fast_bool_anf_transform_unsigned(16 as u32, 2);
142    }
143
144    #[test]
145    #[should_panic]
146    fn test_fast_bool_anf_transform_unsigned_not_enough_bits() {
147        let _ = fast_bool_anf_transform_unsigned(16 as u16, 5);
148    }
149
150    #[test]
151    fn test_fast_bool_anf_transform_bool_array() {
152        let mut rule_truth_table = [false, false, false, false];
153        fast_bool_anf_transform_bool_array(&mut rule_truth_table);
154        assert_eq!(rule_truth_table, [false, false, false, false]);
155
156        rule_truth_table = [true, false, false, false];
157        fast_bool_anf_transform_bool_array(&mut rule_truth_table);
158        assert_eq!(rule_truth_table, [true, true, true, true]);
159
160        rule_truth_table = [false, true, false, false];
161        fast_bool_anf_transform_bool_array(&mut rule_truth_table);
162        assert_eq!(rule_truth_table, [false, true, false, true]);
163
164        rule_truth_table = [true, true, false, false];
165        fast_bool_anf_transform_bool_array(&mut rule_truth_table);
166        assert_eq!(rule_truth_table, [true, false, true, false]);
167
168        let mut rule_truth_table = [false, false, true, false];
169        fast_bool_anf_transform_bool_array(&mut rule_truth_table);
170        assert_eq!(rule_truth_table, [false, false, true, true]);
171
172        rule_truth_table = [true, false, true, false];
173        fast_bool_anf_transform_bool_array(&mut rule_truth_table);
174        assert_eq!(rule_truth_table, [true, true, false, false]);
175
176        rule_truth_table = [false, true, true, false];
177        fast_bool_anf_transform_bool_array(&mut rule_truth_table);
178        assert_eq!(rule_truth_table, [false, true, true, false]);
179
180        rule_truth_table = [true, true, true, false];
181        fast_bool_anf_transform_bool_array(&mut rule_truth_table);
182        assert_eq!(rule_truth_table, [true, false, false, true]);
183
184        let mut rule_truth_table = [false, false, false, true];
185        fast_bool_anf_transform_bool_array(&mut rule_truth_table);
186        assert_eq!(rule_truth_table, [false, false, false, true]);
187
188        rule_truth_table = [true, false, false, true];
189        fast_bool_anf_transform_bool_array(&mut rule_truth_table);
190        assert_eq!(rule_truth_table, [true, true, true, false]);
191
192        rule_truth_table = [false, true, false, true];
193        fast_bool_anf_transform_bool_array(&mut rule_truth_table);
194        assert_eq!(rule_truth_table, [false, true, false, false]);
195
196        rule_truth_table = [true, true, false, true];
197        fast_bool_anf_transform_bool_array(&mut rule_truth_table);
198        assert_eq!(rule_truth_table, [true, false, true, true]);
199
200        let mut rule_truth_table = [false, false, true, true];
201        fast_bool_anf_transform_bool_array(&mut rule_truth_table);
202        assert_eq!(rule_truth_table, [false, false, true, false]);
203
204        rule_truth_table = [true, false, true, true];
205        fast_bool_anf_transform_bool_array(&mut rule_truth_table);
206        assert_eq!(rule_truth_table, [true, true, false, true]);
207
208        rule_truth_table = [false, true, true, true];
209        fast_bool_anf_transform_bool_array(&mut rule_truth_table);
210        assert_eq!(rule_truth_table, [false, true, true, true]);
211
212        rule_truth_table = [true, true, true, true];
213        fast_bool_anf_transform_bool_array(&mut rule_truth_table);
214        assert_eq!(rule_truth_table, [true, false, false, false]);
215
216        let mut rule_truth_table = [false, false, false, false, true, true, true, true]; // 240
217        fast_bool_anf_transform_bool_array(&mut rule_truth_table);
218        assert_eq!(rule_truth_table, [false, false, false, false, true, false, false, false]);
219
220        let mut rule_truth_table = [false, true, true, true, true, false, false, false]; // 30
221        fast_bool_anf_transform_bool_array(&mut rule_truth_table);
222        assert_eq!(rule_truth_table, [false, true, true, true, true, false, false, false]);
223    }
224
225    #[test]
226    #[should_panic]
227    fn test_fast_bool_anf_transform_bool_array_wrong_input_size() {
228        let mut rule_truth_table = [false, false, false, false, true, true, true];
229        fast_bool_anf_transform_bool_array(&mut rule_truth_table);
230    }
231}
fast_boolean_anf_transform/lib.rs

fast_boolean_anf_transform/
lib.rs
