volute 1.2.1

Boolean functions implementation, represented as lookup tables (LUT) or sum-of-products (SOP)
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

use crate::operations::*;

/// A helper function to many properties of an input using the cofactors
/// * Insensitive to input: c0 == c1
/// * And/Or/Nand/Nor canalizing: c0 or c1 is 0 or 1
/// * Xor-separable: c0 == !c1
/// * Positive/negative unate: c0 | !c1 or !c0 | c1
///
/// The given operation takes two words of the cofactor and returns one word with a bit set for all positions that match
pub fn input_property_helper<F>(num_vars: usize, table: &[u64], ind: usize, op: F) -> bool
where
    F: Fn(u64, u64) -> u64,
{
    assert!(table.len() == table_size(num_vars));
    assert!(ind < num_vars);
    let mask = num_vars_mask(num_vars);
    let mut ret = true;
    if ind <= 5 {
        let shift = 1 << ind;
        let m1 = VAR_MASK[ind];
        let m0 = !VAR_MASK[ind];
        for t in table {
            let c1 = ((*t & m1) >> shift) | (*t & m1);
            let c0 = ((*t & m0) << shift) | (*t & m0);
            ret &= !op(c0, c1) & mask == 0;
        }
    } else {
        let stride = 1 << (ind - 6);
        for i in 0..table.len() {
            if i & stride == 0 {
                let c0 = table[i];
                let c1 = table[i + stride];
                ret &= !op(c0, c1) & mask == 0;
            }
        }
    }
    ret
}

pub fn input_independent(num_vars: usize, table: &[u64], ind: usize) -> bool {
    input_property_helper(num_vars, table, ind, |c0, c1| !(c0 ^ c1))
}

pub fn input_and(num_vars: usize, table: &[u64], ind: usize) -> bool {
    input_property_helper(num_vars, table, ind, |c0, _| !c0)
}

pub fn input_or(num_vars: usize, table: &[u64], ind: usize) -> bool {
    input_property_helper(num_vars, table, ind, |_, c1| c1)
}

pub fn input_nand(num_vars: usize, table: &[u64], ind: usize) -> bool {
    input_property_helper(num_vars, table, ind, |c0, _| c0)
}

pub fn input_nor(num_vars: usize, table: &[u64], ind: usize) -> bool {
    input_property_helper(num_vars, table, ind, |_, c1| !c1)
}

pub fn input_xor(num_vars: usize, table: &[u64], ind: usize) -> bool {
    input_property_helper(num_vars, table, ind, |c0, c1| c0 ^ c1)
}

pub fn input_pos_unate(num_vars: usize, table: &[u64], ind: usize) -> bool {
    input_property_helper(num_vars, table, ind, |c0, c1| !c0 | c1)
}

pub fn input_neg_unate(num_vars: usize, table: &[u64], ind: usize) -> bool {
    input_property_helper(num_vars, table, ind, |c0, c1| !c1 | c0)
}

/// Basic boolean function families to describe decompositions
#[derive(Debug, PartialEq, Eq, Hash)]
pub enum DecompositionType {
    /// No valid decomposition with this variable
    None,
    /// The function is independent of this variable
    Independent,
    /// The function returns this variable
    Identity,
    /// The function returns the negation of this variable
    Negation,
    /// Decomposition possible as And
    And,
    /// Decomposition possible as Or
    Or,
    /// Decomposition possible as Less-Or-Equal (equivalent to Nand for a top decomposition)
    Le,
    /// Decomposition possible as Less-Than (equivalent to Nor for a top decomposition)
    Lt,
    /// Decomposition possible as Xor
    Xor,
}

impl DecompositionType {
    /// Returns whether the decomposition is trivial (independent, x or !x)
    pub fn is_trivial(&self) -> bool {
        [Self::Independent, Self::Identity, Self::Negation].contains(self)
    }

    /// Returns whether the decomposition is based on an and gate or similar
    pub fn is_and_type(&self) -> bool {
        [Self::And, Self::Or, Self::Le, Self::Lt].contains(self)
    }

    /// Returns whether the decomposition is based on a xor gate
    pub fn is_xor_type(&self) -> bool {
        [Self::Xor].contains(self)
    }

    /// Returns whether the decomposition is based on any 2-input gate
    pub fn is_simple_gate(&self) -> bool {
        [Self::And, Self::Or, Self::Le, Self::Lt, Self::Xor].contains(self)
    }
}

pub fn top_decomposition(num_vars: usize, table: &[u64], ind: usize) -> DecompositionType {
    let indep: bool = input_independent(num_vars, table, ind);
    let and = input_and(num_vars, table, ind);
    let or = input_or(num_vars, table, ind);
    let nand = input_nand(num_vars, table, ind);
    let nor = input_nor(num_vars, table, ind);
    let xor = input_xor(num_vars, table, ind);

    if indep {
        DecompositionType::Independent
    } else if and && or {
        DecompositionType::Identity
    } else if nand && nor {
        DecompositionType::Negation
    } else if and {
        DecompositionType::And
    } else if or {
        DecompositionType::Or
    } else if nand {
        DecompositionType::Le
    } else if nor {
        DecompositionType::Lt
    } else if xor {
        DecompositionType::Xor
    } else {
        DecompositionType::None
    }
}