boolean_circuit/
builder.rs

1use crate::Gate;
2
3/// Constructs a gate that evaluates to `true` if and only if `x` and `y`
4/// evaluate to the same value.
5pub fn eq(x: &Gate, y: &Gate) -> Gate {
6    !(x ^ y)
7}
8
9/// Constructs a gate that evaluates to `true` if and only if all of the
10/// gates returned by `i` evaulate to `true`.
11///
12/// The construction has logarithmic depth in the length if `i`.
13pub fn reduce_conjunction(i: impl IntoIterator<Item = Gate>) -> Gate {
14    reduce_associative(i.into_iter().collect::<Vec<_>>().as_slice(), |x, y| x & y)
15        .unwrap_or_else(|| true.into())
16}
17
18/// Constructs a gate that evaluates to `true` if and only if at least one of the
19/// gates returned by `i` evaulates to `true`.
20///
21/// The construction has logarithmic depth in the length if `i`.
22pub fn reduce_disjunction(i: impl IntoIterator<Item = Gate>) -> Gate {
23    reduce_associative(i.into_iter().collect::<Vec<_>>().as_slice(), |x, y| x | y)
24        .unwrap_or_else(|| false.into())
25}
26
27/// Constructs a gate that evaluates to `true` if and only if an odd number of the
28/// gates returned by `i` evaulate to `true`.
29///
30/// The construction has logarithmic depth in the length if `i`.
31pub fn reduce_xor(i: impl IntoIterator<Item = Gate>) -> Gate {
32    reduce_associative(i.into_iter().collect::<Vec<_>>().as_slice(), |x, y| x ^ y).unwrap()
33}
34
35fn reduce_associative<T: Clone>(i: &[T], op: fn(&T, &T) -> T) -> Option<T> {
36    match i.len() {
37        0 => None,
38        1 => Some(i[0].clone()),
39        _ => {
40            let mid = i.len() / 2;
41            Some(op(
42                &reduce_associative(&i[..mid], op).unwrap(),
43                &reduce_associative(&i[mid..], op).unwrap(),
44            ))
45        }
46    }
47}
boolean_circuit/builder.rs

boolean_circuit/
builder.rs
