volute/sop/
cube.rs

1//! Compact representation of And functions
2
3use std::{cmp::max, fmt, ops::BitAnd};
4
5use crate::Lut;
6
7/// Representation of the And of variables (a cube in Sum-of-Products representations)
8///
9/// Each variable is represented by a pair of bits, representing respectively the positive
10/// and negative literal. If none is set, the variable is unused. If both are set, the cube is 0.
11///
12/// It only supports And operations. Anything else must be implemented by more complex
13/// representations that use it, such as sum-of-products.
14#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, Debug)]
15pub struct Cube {
16    pos: u32,
17    neg: u32,
18}
19
20impl Cube {
21    /// The empty cube
22    pub fn one() -> Cube {
23        Cube { pos: 0, neg: 0 }
24    }
25
26    /// The zero cube (not strictly a cube, so it gets a special representation)
27    pub fn zero() -> Cube {
28        Cube { pos: !0, neg: !0 }
29    }
30
31    /// Check whether the cube is a constant
32    pub fn is_constant(&self) -> bool {
33        self.is_one() || self.is_zero()
34    }
35
36    /// Check whether the cube is a constant zero
37    ///
38    /// This can happen after And operations, so we check if any variable has the two bits set.
39    pub fn is_zero(&self) -> bool {
40        self.pos & self.neg != 0
41    }
42
43    /// Check whether the cube is the constant one
44    pub fn is_one(&self) -> bool {
45        self.pos == 0 && self.neg == 0
46    }
47
48    /// Return the cube representing the nth variable
49    pub fn nth_var(var: usize) -> Cube {
50        Cube {
51            pos: 1 << var,
52            neg: 0,
53        }
54    }
55
56    /// Return the cube representing the nth variable, inverted
57    pub fn nth_var_inv(var: usize) -> Cube {
58        Cube {
59            pos: 0,
60            neg: 1 << var,
61        }
62    }
63
64    /// Obtain the minterm for a value of the variables
65    pub fn minterm(num_vars: usize, mask: usize) -> Cube {
66        let m = mask as u32;
67        let tot = (1 << num_vars) - 1;
68        Cube {
69            pos: m & tot,
70            neg: !m & tot,
71        }
72    }
73
74    /// Get the value of the Cube for these inputs (input bits packed in the mask)
75    pub fn value(&self, mask: usize) -> bool {
76        let m = mask as u32;
77        (self.pos & m) | !self.pos == !0 && (self.neg & !m) | !self.neg == !0
78    }
79
80    /// Build a cube from the literals in it
81    pub fn from_vars(pos_vars: &[usize], neg_vars: &[usize]) -> Cube {
82        let mut pos = 0;
83        for p in pos_vars {
84            pos |= 1 << p;
85        }
86        let mut neg = 0;
87        for p in neg_vars {
88            neg |= 1 << p;
89        }
90        let c = Cube { pos, neg };
91        if c.is_zero() {
92            Cube::zero()
93        } else {
94            c
95        }
96    }
97
98    /// Build a cube directly from the integer masks
99    pub fn from_mask(pos: u32, neg: u32) -> Cube {
100        let c = Cube { pos, neg };
101        if c.is_zero() {
102            Cube::zero()
103        } else {
104            c
105        }
106    }
107
108    /// Return the number of literals
109    pub fn num_lits(&self) -> usize {
110        if self.is_zero() {
111            0
112        } else {
113            self.pos.count_ones() as usize + self.neg.count_ones() as usize
114        }
115    }
116
117    /// Return the number of And2 gates necessary to implement the cube
118    pub fn num_gates(&self) -> usize {
119        return max(self.num_lits(), 1) - 1;
120    }
121
122    /// Returns the variables that are positive in the cube
123    pub fn pos_vars(&self) -> impl Iterator<Item = usize> + '_ {
124        (0..32).filter(|v| (self.pos >> v & 1) != 0)
125    }
126
127    /// Returns the variables that are negative in the cube
128    pub fn neg_vars(&self) -> impl Iterator<Item = usize> + '_ {
129        (0..32).filter(|v| (self.neg >> v & 1) != 0)
130    }
131
132    /// Returns whether the cube intersects another
133    pub fn intersects(&self, o: Cube) -> bool {
134        self & o != Cube::zero()
135    }
136
137    /// Returns whether the cube implies another
138    pub fn implies(&self, o: Cube) -> bool {
139        self.pos | o.pos == self.pos && self.neg | o.neg == self.neg
140    }
141
142    /// Return whether the cube implies the given Lut
143    pub fn implies_lut(&self, lut: &Lut) -> bool {
144        for i in 0..lut.num_bits() {
145            if self.value(i) && !lut.value(i) {
146                return false;
147            }
148        }
149        return true;
150    }
151
152    /// Perform the and operation on two cubes
153    fn and(a: Cube, b: Cube) -> Cube {
154        let ret = Cube {
155            pos: a.pos | b.pos,
156            neg: a.neg | b.neg,
157        };
158        if ret.is_zero() {
159            // Normalize any zero cube to the standard zero
160            Cube::zero()
161        } else {
162            ret
163        }
164    }
165
166    /// Return all possible cubes with a given number of variables
167    pub fn all(vars: usize) -> impl Iterator<Item = Cube> {
168        let mx: u32 = 1 << vars;
169        (0..mx)
170            .flat_map(move |i| (0..mx).map(move |j| (i, j)))
171            .map(|(i, j)| Cube { pos: i, neg: j })
172            .filter(|c| !c.is_zero())
173    }
174}
175
176impl BitAnd<Cube> for Cube {
177    type Output = Cube;
178    fn bitand(self, rhs: Cube) -> Self::Output {
179        Cube::and(self, rhs)
180    }
181}
182
183impl BitAnd<Cube> for &Cube {
184    type Output = Cube;
185    fn bitand(self, rhs: Cube) -> Self::Output {
186        Cube::and(*self, rhs)
187    }
188}
189
190impl BitAnd<&Cube> for &Cube {
191    type Output = Cube;
192    fn bitand(self, rhs: &Cube) -> Self::Output {
193        Cube::and(*self, *rhs)
194    }
195}
196
197impl BitAnd<&Cube> for Cube {
198    type Output = Cube;
199    fn bitand(self, rhs: &Cube) -> Self::Output {
200        Cube::and(self, *rhs)
201    }
202}
203
204impl fmt::Display for Cube {
205    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
206        if self.is_one() {
207            write!(f, "1")?;
208            return Ok(());
209        }
210        if self.is_zero() {
211            write!(f, "0")?;
212            return Ok(());
213        }
214        let mut pos = self.pos;
215        let mut neg = self.neg;
216        let mut i = 0;
217        while pos != 0 || neg != 0 {
218            if pos & 1 != 0 {
219                write!(f, "x{}", i)?;
220            }
221            if neg & 1 != 0 {
222                write!(f, "!x{}", i)?;
223            }
224            i += 1;
225            pos >>= 1;
226            neg >>= 1;
227        }
228        Ok(())
229    }
230}
231
232#[cfg(test)]
233mod tests {
234    use super::Cube;
235
236    #[test]
237    fn test_zero_one() {
238        assert!(Cube::zero().is_zero());
239        assert!(!Cube::one().is_zero());
240        assert!(!Cube::zero().is_one());
241        assert!(Cube::one().is_one());
242        for i in 0..32 {
243            assert!(!Cube::nth_var(i).is_zero());
244            assert!(!Cube::nth_var(i).is_one());
245            assert!(!Cube::nth_var_inv(i).is_zero());
246            assert!(!Cube::nth_var_inv(i).is_one());
247        }
248    }
249
250    #[test]
251    fn test_display() {
252        assert_eq!(format!("{}", Cube::zero()), "0");
253        assert_eq!(format!("{}", Cube::one()), "1");
254        for i in 0..32 {
255            assert_eq!(format!("{}", Cube::nth_var(i)), format!("x{}", i));
256            assert_eq!(format!("{}", Cube::nth_var_inv(i)), format!("!x{}", i));
257        }
258        for i in 0..32 {
259            for j in i + 1..32 {
260                assert_eq!(
261                    format!("{}", Cube::from_vars(&[i, j], &[])),
262                    format!("x{}x{}", i, j)
263                );
264                assert_eq!(
265                    format!("{}", Cube::from_vars(&[i], &[j])),
266                    format!("x{}!x{}", i, j)
267                );
268                assert_eq!(
269                    format!("{}", Cube::from_vars(&[j], &[i])),
270                    format!("!x{}x{}", i, j)
271                );
272                assert_eq!(
273                    format!("{}", Cube::from_vars(&[], &[i, j])),
274                    format!("!x{}!x{}", i, j)
275                );
276            }
277        }
278    }
279
280    #[test]
281    fn test_num_lits() {
282        assert_eq!(Cube::zero().num_lits(), 0);
283        assert_eq!(Cube::one().num_lits(), 0);
284        for i in 0..32 {
285            assert_eq!(Cube::nth_var(i).num_lits(), 1);
286            assert_eq!(Cube::nth_var_inv(i).num_lits(), 1);
287        }
288        for i in 0..32 {
289            for j in i + 1..32 {
290                assert_eq!(Cube::from_vars(&[i, j], &[]).num_lits(), 2);
291                assert_eq!(Cube::from_vars(&[i], &[j]).num_lits(), 2);
292                assert_eq!(Cube::from_vars(&[j], &[i]).num_lits(), 2);
293                assert_eq!(Cube::from_vars(&[], &[i, j]).num_lits(), 2);
294            }
295        }
296    }
297
298    #[test]
299    fn test_implies() {
300        for i in 0..32 {
301            assert!(!Cube::one().implies(Cube::nth_var(i)));
302            assert!(!Cube::one().implies(Cube::nth_var_inv(i)));
303            assert!(Cube::zero().implies(Cube::nth_var(i)));
304            assert!(Cube::zero().implies(Cube::nth_var_inv(i)));
305            assert!(Cube::nth_var(i).implies(Cube::one()));
306            assert!(Cube::nth_var_inv(i).implies(Cube::one()));
307            assert!(!Cube::nth_var(i).implies(Cube::zero()));
308            assert!(!Cube::nth_var_inv(i).implies(Cube::zero()));
309        }
310        for i in 0..32 {
311            for j in i + 1..32 {
312                assert!(Cube::from_vars(&[i, j], &[]).implies(Cube::nth_var(i)));
313                assert!(Cube::from_vars(&[i, j], &[]).implies(Cube::nth_var(j)));
314                assert!(!Cube::from_vars(&[i, j], &[]).implies(Cube::nth_var_inv(i)));
315                assert!(!Cube::from_vars(&[i, j], &[]).implies(Cube::nth_var_inv(j)));
316                assert!(Cube::from_vars(&[], &[i, j]).implies(Cube::nth_var_inv(i)));
317                assert!(Cube::from_vars(&[], &[i, j]).implies(Cube::nth_var_inv(j)));
318                assert!(!Cube::from_vars(&[], &[i, j]).implies(Cube::nth_var(i)));
319                assert!(!Cube::from_vars(&[], &[i, j]).implies(Cube::nth_var(j)));
320            }
321        }
322    }
323
324    #[test]
325    fn test_and() {
326        for i in 0..32 {
327            let vi = Cube::nth_var(i);
328            let vin = Cube::nth_var_inv(i);
329            assert_eq!(vi, vi & vi);
330            assert_eq!(vin, vin & vin);
331            assert_eq!(Cube::zero(), vi & vin);
332            for j in i + 1..32 {
333                let vj = Cube::nth_var(j);
334                let vjn = Cube::nth_var_inv(j);
335                assert_eq!(Cube::from_vars(&[i, j], &[]), vi & vj);
336                assert_eq!(Cube::from_vars(&[i], &[j]), vi & vjn);
337                assert_eq!(Cube::from_vars(&[j], &[i]), vin & vj);
338                assert_eq!(Cube::from_vars(&[], &[i, j]), vin & vjn);
339            }
340        }
341    }
342
343    #[test]
344    fn test_value() {
345        for i in 0..32 {
346            let vi = Cube::nth_var(i);
347            let vin = Cube::nth_var_inv(i);
348            assert!(vi.value(1 << i));
349            assert!(!vi.value(!(1 << i)));
350            assert!(!vin.value(1 << i));
351            assert!(vin.value(!(1 << i)));
352            for j in i + 1..32 {
353                let vj = Cube::nth_var(j);
354                let vjn = Cube::nth_var_inv(j);
355                assert!((vi & vj).value(1 << i | 1 << j));
356                assert!(!(vi & vj).value(1 << i));
357                assert!(!(vi & vj).value(1 << j));
358                assert!((vin & vjn).value(!(1 << i | 1 << j)));
359                assert!(!(vin & vjn).value(!(1 << i)));
360                assert!(!(vin & vjn).value(!(1 << j)));
361            }
362        }
363    }
364
365    #[test]
366    fn test_num() {
367        assert_eq!(Cube::all(0).count(), 1);
368        assert_eq!(Cube::all(1).count(), 3);
369        assert_eq!(Cube::all(2).count(), 9);
370        assert_eq!(Cube::all(3).count(), 27);
371    }
372
373    #[test]
374    fn test_intersects() {
375        for i in 0..32 {
376            let vi = Cube::nth_var(i);
377            let vin = Cube::nth_var_inv(i);
378            assert!(vi.intersects(vi));
379            assert!(vin.intersects(vin));
380            assert!(!vin.intersects(vi));
381            assert!(!vi.intersects(vin));
382            for j in i + 1..32 {
383                let vj = Cube::nth_var(j);
384                let vjn = Cube::nth_var_inv(j);
385                assert!(vi.intersects(vj));
386                assert!(vin.intersects(vj));
387                assert!(vi.intersects(vjn));
388                assert!(vin.intersects(vjn));
389            }
390        }
391    }
392}
volute/sop/cube.rs

volute/sop/
cube.rs
