libreda_logic/
network_simulator.rs

1// SPDX-FileCopyrightText: 2022 Thomas Kramer <code@tkramer.ch>
2//
3// SPDX-License-Identifier: AGPL-3.0-or-later
4
5//! Simulate logic networks.
6//!
7//! ```
8//! use libreda_logic::network::*;
9//! use libreda_logic::networks::mig::*;
10//! use libreda_logic::network_simulator::*;
11//!
12//! // Create a new logic network based on majority gates and inverters.
13//! let mut mig = Mig::new();
14//!
15//! // Create some primary inputs.
16//! let [a, b, c, d] = mig.create_primary_inputs();
17//!
18//! // Construct the network.
19//! let maj = mig.create_maj3(a, b, c);
20//! let maj_or_d = mig.create_or(maj, d);
21//!
22//! // Create primary outputs.
23//! mig.create_primary_output(maj);
24//! mig.create_primary_output(maj_or_d);
25//!
26//! // Wrap the network into a network simulator.
27//! let simulator = RecursiveSim::new(&mig);
28//!
29//! // Evaluate the network by simulation.
30//! let output_values: Vec<_> = simulator
31//!     .simulate(&[maj, maj_or_d], &[true, false, false, true])
32//!     .collect();
33//! assert_eq!(output_values, vec![false, true]);
34//!
35//! ```
36
37use fnv::FnvHashMap;
38use smallvec::{smallvec, SmallVec};
39
40use crate::{
41    network::{EdgeWithInversion, Network},
42    traits::{
43        BooleanFunction, BooleanSystem, LogicValue, NumInputs, NumOutputs, PartialBooleanSystem,
44    },
45};
46
47/// Very simple network simulator. Not so efficient though.
48pub struct RecursiveSim<'a, N> {
49    network: &'a N,
50}
51
52impl<'a, N> RecursiveSim<'a, N> {
53    /// Create a new simulator for the network.
54    pub fn new(network: &'a N) -> Self {
55        Self { network }
56    }
57}
58
59impl<'a, N> RecursiveSim<'a, N>
60where
61    N: Network<LogicValue = bool>,
62    N::Signal: EdgeWithInversion,
63{
64    /// Simulate the values of the specified `outputs` given the primary inputs.
65    pub fn simulate(
66        &self,
67        outputs: &'a [N::Signal],
68        inputs: &[N::LogicValue],
69    ) -> impl Iterator<Item = N::LogicValue> + 'a {
70        assert_eq!(
71            self.network.num_primary_inputs(),
72            inputs.len(),
73            "input value vector must match the number of primary inputs"
74        );
75
76        let mut cache: FnvHashMap<N::Signal, N::LogicValue> = Default::default();
77
78        let mut stack = outputs.to_vec();
79
80        let net = self.network;
81
82        // Fill the cache with the primary input values.
83        cache.extend(
84            (0..net.num_primary_inputs())
85                .map(|i| net.get_primary_input(i).non_inverted())
86                .zip(inputs.iter().copied()),
87        );
88
89        // Resolve the values of the output signals:
90        //
91        // * Take the top signal from the stack.
92        // * Get it's input signals.
93        // * If the input values are known, compute the output value.
94        // * Otherwise push the top signal on the stack and push the unknown input signals on the stack.
95        while let Some(signal) = stack.pop() {
96            let node = net.get_source_node(&signal);
97
98            if cache.contains_key(&signal.non_inverted()) {
99                // Value is known already.
100                continue;
101            } else {
102                let operands =
103                    (0..net.num_node_inputs(&node)).map(|i| net.get_node_input(&node, i));
104
105                // Buffer for node-input values.
106                let mut buf: SmallVec<[N::LogicValue; 16]> = smallvec![];
107
108                let mut values_complete = true;
109
110                for in_sig in operands {
111                    if let Some(value) = net.get_constant_value(in_sig) {
112                        buf.push(value);
113                    } else if let Some(value) = cache.get(&in_sig.non_inverted()) {
114                        let v = *value ^ in_sig.is_inverted(); // Re-apply inversion if there was one.
115
116                        buf.push(v);
117                    } else {
118                        buf.push(N::LogicValue::zero());
119
120                        debug_assert!(
121                            !net.is_input(in_sig),
122                            "primary inputs must be added to the cache already"
123                        );
124
125                        if values_complete {
126                            // Need to compute this signal later.
127                            stack.push(signal);
128                        }
129
130                        values_complete = false;
131                        stack.push(in_sig);
132                    }
133                }
134
135                if values_complete {
136                    // Compute node output.
137                    let node = net.get_source_node(&signal);
138                    let operator = net.node_function(node);
139
140                    let value = operator.eval(&buf);
141
142                    cache.insert(signal.non_inverted(), value);
143                }
144            }
145        }
146
147        // Now all primary outputs should be in the cache.
148        outputs
149            .iter()
150            .map(move |o| cache[&o.non_inverted()] ^ o.is_inverted())
151    }
152}
153
154impl<'a, N: Network> NumInputs for RecursiveSim<'a, N> {
155    fn num_inputs(&self) -> usize {
156        self.network.num_primary_inputs()
157    }
158}
159
160impl<'a, N: Network> NumOutputs for RecursiveSim<'a, N> {
161    fn num_outputs(&self) -> usize {
162        self.network.num_primary_outputs()
163    }
164}
165
166impl<'a, N> PartialBooleanSystem for RecursiveSim<'a, N>
167where
168    N: Network<LogicValue = bool>,
169    N::Signal: EdgeWithInversion + Ord,
170{
171    type LiteralId = usize;
172
173    type TermId = N::Signal;
174
175    fn evaluate_term_partial(&self, term: &Self::TermId, input_values: &[bool]) -> Option<bool> {
176        Some(self.evaluate_term(term, input_values))
177    }
178}
179
180impl<'a, N> BooleanSystem for RecursiveSim<'a, N>
181where
182    N: Network<LogicValue = bool>,
183    N::Signal: EdgeWithInversion + Ord,
184{
185    fn evaluate_term(&self, term: &Self::TermId, input_values: &[bool]) -> bool {
186        self.simulate(&[*term], input_values).next().unwrap()
187    }
188}
189
190#[test]
191fn test_recursive_simulator() {
192    use crate::network::*;
193    use crate::networks::mig::*;
194
195    let mut mig = Mig::new();
196
197    let [a, b, c, d] = mig.create_primary_inputs();
198
199    let maj = mig.create_maj3(a, b, c);
200    let maj_or_d = mig.create_or(maj, d);
201
202    mig.create_primary_output(maj);
203    mig.create_primary_output(maj_or_d);
204
205    let simulator = RecursiveSim::new(&mig);
206
207    let output_values: Vec<_> = simulator
208        .simulate(&[maj, maj_or_d], &[true, false, false, true])
209        .collect();
210    assert_eq!(output_values, vec![false, true]);
211
212    let output_values: Vec<_> = simulator
213        .simulate(&[maj, maj_or_d], &[true, true, false, false])
214        .collect();
215    assert_eq!(output_values, vec![true, true]);
216}
libreda_logic/network_simulator.rs

libreda_logic/
network_simulator.rs
