libreda_logic/networks/mig/

mod.rs

// SPDX-FileCopyrightText: 2022 Thomas Kramer <code@tkramer.ch>
//
// SPDX-License-Identifier: AGPL-3.0-or-later

//! Majority-inverter graph (MIG) data structures.

use crate::{
    helpers::sort3,
    network::*,
    networks::generic_network::*,
    truth_table::small_lut::{truth_table_library, SmallTruthTable},
};

use super::SimplifyResult;

mod transforms;

/// Majority-inverter graph.
///
/// A logic network consisting of three-input majority nodes.
///
/// # Examples
/// ```
/// use libreda_logic::traits::*;
/// use libreda_logic::network::*;
/// use libreda_logic::networks::mig::*;
///
/// // Create an empty network.
/// let mut mig = Mig::new();
///
/// // Create two inputs.
/// let a = mig.create_primary_input();
/// let b = mig.create_primary_input();
///
/// // Create the boolean AND of the two inputs.
/// let a_and_b = mig.create_and(a, b);
/// ```
pub type Mig = LogicNetwork<Maj3Node>;

/// Identifier for nodes in the majority-inverter graph.
pub type MigNodeId = NodeId;

/// Node in the majority-inverter graph.
#[derive(Clone, Copy, Debug, Hash, PartialEq, PartialOrd, Eq, Ord)]
pub struct Maj3Node {
    pub(super) a: MigNodeId,
    pub(super) b: MigNodeId,
    pub(super) c: MigNodeId,
    /// Number of nodes which reference to this node.
    num_references: usize,
}

impl Maj3Node {
    /// Create a new three-input majority node.
    fn new([a, b, c]: [MigNodeId; 3]) -> Self {
        Self {
            a,
            b,
            c,
            num_references: 0,
        }
    }

    /// Get the child node IDs as an array.
    pub(crate) fn to_array(self) -> [MigNodeId; 3] {
        [self.a, self.b, self.c]
    }

    /// Get an array of mutable references to the node inputs.
    pub(crate) fn to_array_mut(&mut self) -> [&mut MigNodeId; 3] {
        [&mut self.a, &mut self.b, &mut self.c]
    }
}

impl NetworkNode for Maj3Node {
    type NodeId = MigNodeId;

    fn num_inputs(&self) -> usize {
        3
    }

    fn get_input(&self, i: usize) -> Self::NodeId {
        match i {
            0 => self.a,
            1 => self.b,
            2 => self.c,
            _ => panic!("index out of bounds"),
        }
    }

    fn function(&self) -> SmallTruthTable {
        truth_table_library::maj3()
    }

    fn normalized(self) -> SimplifyResult<Self, Self::NodeId> {
        Mig::simplify_node(self)
    }
}

impl MutNetworkNode for Maj3Node {
    fn set_input(&mut self, i: usize, signal: Self::NodeId) {
        let input = match i {
            0 => &mut self.a,
            1 => &mut self.b,
            2 => &mut self.c,
            _ => panic!("index out of bounds"),
        };

        *input = signal;
    }
}

impl NetworkNodeWithReferenceCount for Maj3Node {
    fn num_references(&self) -> usize {
        self.num_references
    }
}

impl MutNetworkNodeWithReferenceCount for Maj3Node {
    fn reference(&mut self) {
        self.num_references += 1;
    }

    fn dereference(&mut self) {
        self.num_references -= 1;
    }
}

impl IntoIterator for Maj3Node {
    type Item = MigNodeId;

    type IntoIter = std::array::IntoIter<MigNodeId, 3>;

    fn into_iter(self) -> Self::IntoIter {
        // Sanity check: inputs must be sorted.
        debug_assert_eq!(
            self.to_array(),
            sort3(self.to_array()),
            "inputs must be sorted"
        );

        self.to_array().into_iter()
    }
}

impl Mig {
    /// Simplify the node without making changes to the graph.
    ///
    /// Either returns the ID of an existing node which is equivalent to the given node,
    /// or returns a node with simplified input, or returns the unmodified node.
    fn simplify_node(node: Maj3Node) -> SimplifyResult<Maj3Node, NodeId> {
        SimplifyResult::new_node(node)
            // Use majority rule
            .and_then(Self::simplify_node_by_majority)
            .and_then(Self::normalize_by_input_inversions)
            .map_unsimplified(Self::normalize_node_by_commutativity) // TODO: Is this necessary? Might be done in simplify_node_with_hashtable
    }

    /// Invert the inputs such that
    /// the majority of inputs is not inverted.
    /// Returns a tuple `(n, need_inversion)`. Where `n` is the modified node and `need_inversion` is set to true
    /// iff the node inputs have been inverted.
    fn normalize_by_input_inversions(node: Maj3Node) -> SimplifyResult<Maj3Node, NodeId> {
        let [a, b, c] = node.to_array();

        // Convert inputs into a unique form.
        // * sort them
        // * enventually invert this signal output such that the majority of the inputs is not inverted
        let (a, b, c, invert_output) = {
            let num_inversions =
                (a.is_inverted() as u8) + (b.is_inverted() as u8) + (c.is_inverted() as u8);

            let (a, b, c, invert_output) = if num_inversions >= 2 {
                (a.invert(), b.invert(), c.invert(), true)
            } else {
                (a, b, c, false)
            };
            (a, b, c, invert_output)
        };

        let node = Maj3Node::new([a, b, c]);
        SimplifyResult::Node(node, invert_output)
    }

    /// Sort the inputs of the node.
    /// Use the rule `M(x, y, z) == M(y, z, x) == M(z, y, x)`.
    fn normalize_node_by_commutativity(node: Maj3Node) -> Maj3Node {
        let [a, b, c] = sort3(node.to_array());
        Maj3Node { a, b, c, ..node }
    }

    /// Simplify the node to a single signal if there are either two equal inputs or an input `x` and another input `y'`.
    /// Both cases decide the majority function.
    /// Returns a node ID if simplification was successful, otherwise returns the original node.
    ///
    /// Majority rule:
    /// * if (x == y): M(x, y, z) = x = y
    /// * if (x == y'): M(x, y, z) = z
    fn simplify_node_by_majority(node: Maj3Node) -> SimplifyResult<Maj3Node, NodeId> {
        let [a, b, c] = [node.a, node.b, node.c];
        match [a, b, c] {
            // M(x, x, _) => x
            [x, y, _] | [y, _, x] | [_, x, y] if x == y => SimplifyResult::new_id(x),
            // M(x, x', z) => z
            [x, y, z] | [y, z, x] | [z, x, y] if x == y.invert() => SimplifyResult::new_id(z),
            _ => SimplifyResult::new_node(node),
        }
    }
}

impl HomogeneousNetwork for Mig {
    const NUM_NODE_INPUTS: usize = 3;

    fn function(&self) -> Self::NodeFunction {
        crate::truth_table::small_lut::truth_table_library::maj3()
    }
}

impl SubstituteInNode for Mig {
    fn substitute_in_node(
        &mut self,
        node: Self::NodeId,
        old_signal: Self::Signal,
        new_signal: Self::Signal,
    ) {
        if let Some(n) = self.get_logic_node_mut(node) {
            // Replace the each occurrence of the old signal with the new signal.
            n.to_array_mut()
                .into_iter()
                .filter(|input| **input == old_signal)
                .for_each(|input| *input = new_signal);
        }
    }
}

impl UnaryOp for Mig {
    fn create_not(&mut self, signal: Self::Signal) -> Self::Signal {
        signal.invert()
    }
}

impl BinaryOp for Mig {
    fn create_and(&mut self, a: Self::Signal, b: Self::Signal) -> Self::Signal {
        self.create_maj3(MigNodeId::zero(), a, b)
    }

    fn create_or(&mut self, a: Self::Signal, b: Self::Signal) -> Self::Signal {
        self.create_maj3(MigNodeId::zero().invert(), a, b)
    }

    fn create_nand(&mut self, a: Self::Signal, b: Self::Signal) -> Self::Signal {
        self.create_and(a, b).invert()
    }

    fn create_nor(&mut self, a: Self::Signal, b: Self::Signal) -> Self::Signal {
        self.create_or(a, b).invert()
    }

    fn create_xor(&mut self, a: Self::Signal, b: Self::Signal) -> Self::Signal {
        let x = self.create_and(a, b.invert());
        let y = self.create_and(a.invert(), b);
        self.create_or(x, y)
    }
}

impl TernaryOp for Mig {
    fn create_maj3(&mut self, a: Self::Signal, b: Self::Signal, c: Self::Signal) -> Self::Signal {
        let node = Maj3Node::new([a, b, c]);

        // TODO: doing double the work. Normalization is already called by `create_node`
        match Self::simplify_node(node) {
            SimplifyResult::Node(n, invert) => self.create_node(n).invert_if(invert),
            SimplifyResult::Simplified(s, invert) => s.invert_if(invert),
        }
    }
}

#[test]
fn test_mig_create_constants() {
    let mig = Mig::new();

    let zero = mig.get_constant(false);
    let one = mig.get_constant(true);

    assert!(zero.is_constant());
    assert!(one.is_constant());

    assert!(zero.is_zero());

    assert_ne!(zero, one);
    assert_eq!(zero.invert(), one);
}

#[test]
fn test_mig_create_primary_inputs() {
    let mut mig = Mig::new();
    let a = mig.create_primary_input();
    let b = mig.create_primary_input();
    let c = mig.create_primary_input();

    assert_ne!(a, b);
    assert_ne!(b, c);

    assert!(mig.is_input(a));
    assert!(mig.is_input(b));
    assert!(mig.is_input(c));

    assert!(!mig.is_constant(a));
}

#[test]
fn test_mig_node_deduplication() {
    let mut mig = Mig::new();

    let a = mig.create_primary_input();
    let b = mig.create_primary_input();
    let c = mig.create_primary_input();

    let maj_abc_1 = mig.create_maj3(a, b, c);
    let maj_abc_2 = mig.create_maj3(a, b, c);

    assert_eq!(maj_abc_1, maj_abc_2);
}

#[test]
fn test_mig_node_simplification_by_commutativity() {
    let mut mig = Mig::new();

    let a = mig.create_primary_input();
    let b = mig.create_primary_input();
    let c = mig.create_primary_input();

    let maj_abc = mig.create_maj3(a, b, c);

    // Deduplication under permutation of inputs.
    assert_eq!(maj_abc, mig.create_maj3(c, b, a));

    // Deduplication under permutation and inversion of inputs.
    // M(a, b, c) == M(a', b', c')'
    assert_eq!(
        maj_abc,
        mig.create_maj3(c.invert(), b.invert(), a.invert()).invert()
    );
}

#[test]
fn test_mig_node_simplification_by_majority() {
    let mut mig = Mig::new();

    let a = mig.create_primary_input();
    let b = mig.create_primary_input();

    let maj_aab = mig.create_maj3(a, a, b);
    assert_eq!(maj_aab, a);
}

#[test]
fn test_mig_node_simplification_with_constants() {
    let mut mig = Mig::new();

    let a = mig.create_primary_input();

    let zero = mig.get_constant(false);

    let a_and_zero = mig.create_and(a, zero);
    //let a_or_zero = mig.create_or(a, zero);

    assert_eq!(a_and_zero, zero);
    //assert_eq!(a_or_zero, a);
}

#[test]
fn test_mig_simulation() {
    use crate::native_boolean_functions::NativeBooleanFunction;
    use crate::traits::BooleanSystem;

    // Construct a one-bit full adder.
    let mut mig = Mig::new();
    let [in1, in2, carry_in] = mig.create_primary_inputs();

    let sum = mig.create_xor3(in1, in2, carry_in);
    let carry = mig.create_maj3(in1, in2, carry_in);

    let output_sum = mig.create_primary_output(sum);
    let output_carry = mig.create_primary_output(carry);

    let simulator = crate::network_simulator::RecursiveSim::new(&mig);

    // Reference model of the full adder.
    fn full_adder([a, b, c]: [bool; 3]) -> [bool; 2] {
        let sum = (a as usize) + (b as usize) + (c as usize);
        [
            sum & 0b1 == 1,
            sum & 0b10 == 0b10, // carry
        ]
    }

    let reference = NativeBooleanFunction::new(full_adder);

    for i in 0..(1 << 3) {
        let inputs = [0, 1, 2].map(|idx| (i >> idx) & 1 == 1);

        let exptected_output = [0, 1].map(|out| reference.evaluate_term(&out, &inputs));
        let actual_output: Vec<_> = simulator
            .simulate(&[output_sum, output_carry], &inputs)
            .collect();

        dbg!(inputs);

        assert_eq!(exptected_output.as_slice(), actual_output.as_slice());
    }
}