libreda-logic 0.0.3

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

//! Simulate logic networks.
//!
//! ```
//! use libreda_logic::network::*;
//! use libreda_logic::networks::mig::*;
//! use libreda_logic::network_simulator::*;
//!
//! // Create a new logic network based on majority gates and inverters.
//! let mut mig = Mig::new();
//!
//! // Create some primary inputs.
//! let [a, b, c, d] = mig.create_primary_inputs();
//!
//! // Construct the network.
//! let maj = mig.create_maj3(a, b, c);
//! let maj_or_d = mig.create_or(maj, d);
//!
//! // Create primary outputs.
//! mig.create_primary_output(maj);
//! mig.create_primary_output(maj_or_d);
//!
//! // Wrap the network into a network simulator.
//! let simulator = RecursiveSim::new(&mig);
//!
//! // Evaluate the network by simulation.
//! let output_values: Vec<_> = simulator
//!     .simulate(&[maj, maj_or_d], &[true, false, false, true])
//!     .collect();
//! assert_eq!(output_values, vec![false, true]);
//!
//! ```

use fnv::FnvHashMap;
use smallvec::{smallvec, SmallVec};

use crate::{
    network::{EdgeWithInversion, Network},
    traits::{
        BooleanFunction, BooleanSystem, LogicValue, NumInputs, NumOutputs, PartialBooleanSystem,
    },
};

/// Very simple network simulator. Not so efficient though.
pub struct RecursiveSim<'a, N> {
    network: &'a N,
}

impl<'a, N> RecursiveSim<'a, N> {
    /// Create a new simulator for the network.
    pub fn new(network: &'a N) -> Self {
        Self { network }
    }
}

impl<'a, N> RecursiveSim<'a, N>
where
    N: Network<LogicValue = bool>,
    N::Signal: EdgeWithInversion,
{
    /// Simulate the values of the specified `outputs` given the primary inputs.
    pub fn simulate(
        &self,
        outputs: &'a [N::Signal],
        inputs: &[N::LogicValue],
    ) -> impl Iterator<Item = N::LogicValue> + 'a {
        assert_eq!(
            self.network.num_primary_inputs(),
            inputs.len(),
            "input value vector must match the number of primary inputs"
        );

        let mut cache: FnvHashMap<N::Signal, N::LogicValue> = Default::default();

        let mut stack = outputs.to_vec();

        let net = self.network;

        // Fill the cache with the primary input values.
        cache.extend(
            (0..net.num_primary_inputs())
                .map(|i| net.get_primary_input(i).non_inverted())
                .zip(inputs.iter().copied()),
        );

        // Resolve the values of the output signals:
        //
        // * Take the top signal from the stack.
        // * Get it's input signals.
        // * If the input values are known, compute the output value.
        // * Otherwise push the top signal on the stack and push the unknown input signals on the stack.
        while let Some(signal) = stack.pop() {
            let node = net.get_source_node(&signal);

            if cache.contains_key(&signal.non_inverted()) {
                // Value is known already.
                continue;
            } else {
                let operands =
                    (0..net.num_node_inputs(&node)).map(|i| net.get_node_input(&node, i));

                // Buffer for node-input values.
                let mut buf: SmallVec<[N::LogicValue; 16]> = smallvec![];

                let mut values_complete = true;

                for in_sig in operands {
                    if let Some(value) = net.get_constant_value(in_sig) {
                        buf.push(value);
                    } else if let Some(value) = cache.get(&in_sig.non_inverted()) {
                        let v = *value ^ in_sig.is_inverted(); // Re-apply inversion if there was one.

                        buf.push(v);
                    } else {
                        buf.push(N::LogicValue::zero());

                        debug_assert!(
                            !net.is_input(in_sig),
                            "primary inputs must be added to the cache already"
                        );

                        if values_complete {
                            // Need to compute this signal later.
                            stack.push(signal);
                        }

                        values_complete = false;
                        stack.push(in_sig);
                    }
                }

                if values_complete {
                    // Compute node output.
                    let node = net.get_source_node(&signal);
                    let operator = net.node_function(node);

                    let value = operator.eval(&buf);

                    cache.insert(signal.non_inverted(), value);
                }
            }
        }

        // Now all primary outputs should be in the cache.
        outputs
            .iter()
            .map(move |o| cache[&o.non_inverted()] ^ o.is_inverted())
    }
}

impl<'a, N: Network> NumInputs for RecursiveSim<'a, N> {
    fn num_inputs(&self) -> usize {
        self.network.num_primary_inputs()
    }
}

impl<'a, N: Network> NumOutputs for RecursiveSim<'a, N> {
    fn num_outputs(&self) -> usize {
        self.network.num_primary_outputs()
    }
}

impl<'a, N> PartialBooleanSystem for RecursiveSim<'a, N>
where
    N: Network<LogicValue = bool>,
    N::Signal: EdgeWithInversion + Ord,
{
    type LiteralId = usize;

    type TermId = N::Signal;

    fn evaluate_term_partial(&self, term: &Self::TermId, input_values: &[bool]) -> Option<bool> {
        Some(self.evaluate_term(term, input_values))
    }
}

impl<'a, N> BooleanSystem for RecursiveSim<'a, N>
where
    N: Network<LogicValue = bool>,
    N::Signal: EdgeWithInversion + Ord,
{
    fn evaluate_term(&self, term: &Self::TermId, input_values: &[bool]) -> bool {
        self.simulate(&[*term], input_values).next().unwrap()
    }
}

#[test]
fn test_recursive_simulator() {
    use crate::network::*;
    use crate::networks::mig::*;

    let mut mig = Mig::new();

    let [a, b, c, d] = mig.create_primary_inputs();

    let maj = mig.create_maj3(a, b, c);
    let maj_or_d = mig.create_or(maj, d);

    mig.create_primary_output(maj);
    mig.create_primary_output(maj_or_d);

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

    let output_values: Vec<_> = simulator
        .simulate(&[maj, maj_or_d], &[true, false, false, true])
        .collect();
    assert_eq!(output_values, vec![false, true]);

    let output_values: Vec<_> = simulator
        .simulate(&[maj, maj_or_d], &[true, true, false, false])
        .collect();
    assert_eq!(output_values, vec![true, true]);
}