libreda_logic/networks/
generic_network.rs

1// SPDX-FileCopyrightText: 2022 Thomas Kramer <code@tkramer.ch>
2//
3// SPDX-License-Identifier: AGPL-3.0-or-later
4
5//! Generic data-structure for logic networks. The node type is a type parameter.
6
7use crate::linked_lists::{ElementIndex, LinkedLists, ListIndex};
8use crate::network_simulator;
9use crate::traits::{BooleanSystem, NumInputs, NumOutputs, PartialBooleanSystem};
10use crate::truth_table::small_lut::truth_table_library;
11
12use crate::network::*;
13use crate::truth_table::small_lut::SmallTruthTable;
14use itertools::Itertools;
15use smallvec::SmallVec;
16
17use fnv::FnvHashMap;
18use std::hash::Hash;
19
20use super::SimplifyResult;
21
22/// An implementation of logic networks which is parameterized with the type of the logic node.
23#[derive(Clone, Default)]
24pub struct LogicNetwork<Node> {
25    storage: Vec<NodeWithReferences<Node>>,
26    primary_inputs: Vec<NodeId>,
27    primary_outputs: Vec<NodeId>,
28    /// Table for structural hashing.
29    /// Structural hashing helps de-duplicating nodes.
30    hash_table: FnvHashMap<Node, NodeId>,
31
32    /// Storage for reverse graph edges.
33    references: LinkedLists<NodeId>,
34    edges: LinkedLists<(NodeId, ElementIndex)>,
35}
36
37impl<Node> LogicNetwork<Node> {
38    /// Create a new and empty logic network.
39    pub fn new() -> Self {
40        Self {
41            storage: Default::default(),
42            primary_inputs: Default::default(),
43            primary_outputs: Default::default(),
44            hash_table: Default::default(),
45            references: Default::default(),
46            edges: Default::default(),
47        }
48    }
49}
50
51/// Associate a list of incoming edges with a network node.
52#[derive(Clone, Default)]
53struct NodeWithReferences<N> {
54    /// The network node.
55    node: N,
56    /// Pointer to the start of a linked list. The linked list is stored in `LogicNetwork::references`.
57    /// The list contains the indices of the nodes which use this node.
58    references: ListIndex,
59    outgoing_edges: ListIndex,
60}
61
62impl<N> From<N> for NodeWithReferences<N> {
63    fn from(n: N) -> Self {
64        Self {
65            node: n,
66            references: ListIndex::Empty,
67            outgoing_edges: ListIndex::Empty,
68        }
69    }
70}
71
72/// ID of a signal in the logic network.
73/// An ID can point to the output of a node as well as to a primary input or a constant.
74/// The ID encodes if the signal is inverted.
75#[derive(Clone, Copy, Hash, PartialEq, PartialOrd, Eq, Ord)]
76pub struct NodeId {
77    /// ID of the graph edge. This encodes the index into the storage array, an inversion bit and an 'input' bit.
78    index: usize,
79}
80
81impl std::fmt::Debug for NodeId {
82    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
83        if self.is_constant() {
84            write!(
85                f,
86                "NodeId(constant = {})",
87                if self.is_zero() { "0" } else { "1" }
88            )
89        } else if self.is_input() {
90            write!(
91                f,
92                "NodeId(input({}), inverted = {})",
93                self.input_index().unwrap(),
94                self.is_inverted()
95            )
96        } else {
97            write!(
98                f,
99                "NodeId(index: {}, is_inverted: {})",
100                self.node_index().unwrap(),
101                self.is_inverted(),
102            )
103        }
104    }
105}
106
107impl NodeId {
108    /// Get the ID for the constant 0.
109    pub(super) fn zero() -> Self {
110        Self { index: 0 }
111    }
112
113    /// Get the index into the storage array.
114    /// Return `None` if the ID points to a constant or an input.
115    pub(super) fn node_index(&self) -> Option<usize> {
116        (!self.is_constant() && !self.is_input()).then(|| {
117            let masked = self.index >> 1; // Strip away the 'input' and 'inversion' bits.
118            masked - 1
119        })
120    }
121
122    /// Get the index of the primary input if this node ID represents a primary input.
123    pub fn input_index(&self) -> Option<usize> {
124        self.is_input().then(|| {
125            let input_marker_bit = 1 << (usize::BITS - 1);
126            (!input_marker_bit & self.index) >> 1 // Strip away the 'input' and 'inversion' bits.
127        })
128    }
129
130    /// Create a new node ID which points to the node stored at `index`.
131    pub(super) fn new_node_id(index: usize) -> Self {
132        let index = index + 1; // index 0 is reserved for the constant 0.
133        let index = index << 1; // LSB is used for marking signals as 'inverted'.
134        assert!(
135            index < (1 << (usize::BITS - 1)),
136            "index out of supported range"
137        );
138        Self { index }
139    }
140
141    /// Create a pointer to an input node.
142    pub(super) fn new_input_node(index: usize) -> Self {
143        let index = index << 1; // LSB is used for marking signals as 'inverted'.
144        assert!(
145            index < (1 << (usize::BITS - 1)),
146            "index out of supported range"
147        );
148        let input_marker_bit = 1 << (usize::BITS - 1);
149
150        Self {
151            index: index | input_marker_bit,
152        }
153    }
154
155    /// Check if the ID points to an input node.
156    pub fn is_input(&self) -> bool {
157        let input_marker_bit = 1 << (usize::BITS - 1);
158        (self.index & input_marker_bit) != 0
159    }
160
161    /// Check if this ID points to the constant 0 or 1.
162    pub fn is_constant(&self) -> bool {
163        self.is_zero() || self.is_one()
164    }
165
166    /// Check if the signal represents the constant 0.
167    pub fn is_zero(&self) -> bool {
168        self.index == 0
169    }
170
171    /// Check if the signal represents the constant 1.
172    pub fn is_one(&self) -> bool {
173        self.invert().index == 0
174    }
175}
176
177impl<Node> LogicNetwork<Node>
178where
179    Node: NetworkNode + Hash + MutNetworkNodeWithReferenceCount + IntoIterator<Item = NodeId>,
180{
181    /// Insert a node in the storage.
182    /// The node should have been normalized beforehand in order to make structural hashing effective. E.g. inputs of commutative nodes should be sorted.
183    fn insert_node(&mut self, node: Node) -> NodeId {
184        //debug_assert!(
185        //    (0..node.num_inputs())
186        //        .skip(1)
187        //        .all(|i| node.get_input(i - 1) <= node.get_input(i)),
188        //    "inputs must be sorted"  // TODO: This should hold only for commutative nodes.
189        //);
190
191        let index = self.storage.len();
192        self.storage.push(node.clone().into());
193        let new_id = NodeId::new_node_id(index);
194        let old_node = self.hash_table.insert(node.clone(), new_id);
195        debug_assert!(old_node.is_none(), "node already exists");
196
197        // Update reference counters of used nodes.
198        // Update references.
199        {
200            // Iterate over fan-ins.
201            node.into_iter()
202                .dedup()
203                .filter_map(|fan_in_node_id| fan_in_node_id.node_index())
204                .for_each(|fan_in_node_index| {
205                    self.insert_reverse_edge(new_id, fan_in_node_index);
206                })
207        }
208
209        new_id
210    }
211
212    /// Enables traversing the DAG in opposite direction of the directed edges.
213    fn insert_reverse_edge(&mut self, node_id: NodeId, fan_in_node: usize) {
214        // Increment the reference counter.
215        self.storage[fan_in_node].node.reference();
216
217        // Create an edge from the input node to the new node.
218        let list_of_references = &mut self.storage[fan_in_node].references;
219        let edge_id = self.references.prepend(list_of_references, node_id);
220
221        let list_of_edges = &mut self.storage[fan_in_node].outgoing_edges;
222        self.edges
223            .prepend(list_of_edges, (NodeId::new_node_id(fan_in_node), edge_id));
224    }
225
226    /// If the node already exists in the graph, replace it with the node ID.
227    /// Note: Normalize the node first to increase chances that an already existing equal node can be found.
228    fn simplify_node_with_hashtable(&self, node: Node) -> SimplifyResult<Node, NodeId> {
229        self.hash_table
230            .get(&node)
231            .map(|s| SimplifyResult::Simplified(*s, false))
232            .unwrap_or(SimplifyResult::new_node(node))
233    }
234}
235
236impl<Node> ReferenceCounted for LogicNetwork<Node>
237where
238    Node: NetworkNode<NodeId = NodeId> + NetworkNodeWithReferenceCount,
239{
240    fn num_references(&self, a: Self::Signal) -> usize {
241        if let Some(idx) = a.node_index() {
242            self.storage[idx].node.num_references()
243        } else {
244            // TODO: Reference counts for inputs and constants.
245            0
246        }
247    }
248}
249
250impl<Node> LogicNetwork<Node> {
251    /// Get the node value of the given `node_id`.
252    pub fn get_node(&self, node_id: NodeId) -> GeneralNode<&Node> {
253        if let Some(idx) = node_id.node_index() {
254            GeneralNode::Node(&self.storage[idx].node)
255        } else if let Some(idx) = node_id.input_index() {
256            GeneralNode::Input(idx)
257        } else {
258            assert!(node_id.is_constant());
259            GeneralNode::Constant(!node_id.is_zero())
260        }
261    }
262
263    /// Get a mutable reference to the logic node with the given ID.
264    /// Returns `None` if the node is an input, a constant or non-existent.
265    pub fn get_logic_node_mut(&mut self, node_id: NodeId) -> Option<&mut Node> {
266        node_id.node_index().map(|idx| &mut self.storage[idx].node)
267    }
268}
269
270impl Edge for NodeId {}
271
272impl EdgeWithInversion for NodeId {
273    fn is_inverted(&self) -> bool {
274        self.index & 0b1 == 1
275    }
276
277    fn invert(self) -> Self {
278        Self {
279            index: self.index ^ 0b1,
280        }
281    }
282
283    /// Make the signal non-inverted.
284    fn non_inverted(self) -> Self {
285        Self {
286            index: self.index & !0b1,
287        }
288    }
289}
290
291/// A node, input or constant in the logic network.
292#[derive(Copy, Clone, Debug, Hash, Eq, PartialEq, Ord, PartialOrd)]
293pub enum GeneralNode<Node> {
294    /// A logic node.
295    Node(Node),
296    /// A primary input.
297    Input(usize),
298    /// A constant value, either `false` or `true`.
299    Constant(bool),
300}
301
302impl<Node> GeneralNode<Node> {
303    /// Convert to a logic node, if possible.
304    pub fn to_logic_node(self) -> Option<Node> {
305        match self {
306            Self::Node(m) => Some(m),
307            _ => None,
308        }
309    }
310    /// Convert to a constant, if possible.
311    pub fn to_constant(self) -> Option<bool> {
312        match self {
313            Self::Constant(c) => Some(c),
314            _ => None,
315        }
316    }
317    /// Convert to an index of a primary input.
318    pub fn to_input(self) -> Option<usize> {
319        match self {
320            Self::Input(idx) => Some(idx),
321            _ => None,
322        }
323    }
324}
325
326impl<Node> Network for LogicNetwork<Node>
327where
328    Node: NetworkNode<NodeId = NodeId>,
329{
330    type Node = Node;
331    type NodeId = NodeId;
332    type Signal = NodeId;
333    type LogicValue = bool;
334    type NodeFunction = SmallTruthTable;
335
336    fn num_gates(&self) -> usize {
337        self.storage.len()
338    }
339
340    fn num_primary_inputs(&self) -> usize {
341        self.primary_inputs.len()
342    }
343
344    fn num_primary_outputs(&self) -> usize {
345        self.primary_outputs.len()
346    }
347
348    fn foreach_gate(&self, f: impl Fn(Self::Signal)) {
349        (0..self.storage.len()).map(NodeId::new_node_id).for_each(f)
350    }
351
352    fn foreach_node(&self, f: impl Fn(&Self::Node)) {
353        self.storage.iter().for_each(|n| f(&n.node));
354    }
355
356    fn get_constant(&self, value: Self::LogicValue) -> Self::Signal {
357        match value {
358            false => NodeId::zero(),
359            true => NodeId::zero().invert(),
360        }
361    }
362
363    fn get_constant_value(&self, signal: Self::Signal) -> Option<Self::LogicValue> {
364        if signal.is_zero() {
365            Some(false)
366        } else if signal.is_one() {
367            Some(true)
368        } else {
369            None
370        }
371    }
372
373    fn get_node_input(&self, node: &Self::Signal, input_index: usize) -> Self::Signal {
374        match self.get_node(*node) {
375            GeneralNode::Node(n) => n.get_input(input_index),
376            GeneralNode::Input(_) => panic!("primary input has no inputs"),
377            GeneralNode::Constant(_) => panic!("constant has no inputs"),
378        }
379    }
380
381    fn get_source_node(&self, signal: &Self::Signal) -> Self::NodeId {
382        signal.non_inverted()
383    }
384
385    fn get_primary_input(&self, index: usize) -> Self::Signal {
386        self.primary_inputs[index]
387    }
388
389    fn get_primary_output(&self, index: usize) -> Self::Signal {
390        self.primary_outputs[index]
391    }
392
393    fn is_constant(&self, signal: Self::Signal) -> bool {
394        signal.is_constant()
395    }
396
397    fn is_input(&self, signal: Self::Signal) -> bool {
398        signal.is_input()
399    }
400
401    fn node_function(&self, node: Self::Signal) -> Self::NodeFunction {
402        match self.get_node(node) {
403            GeneralNode::Node(n) => n.function(),
404            GeneralNode::Input(_) => truth_table_library::identity1(),
405            GeneralNode::Constant(c) => SmallTruthTable::new(|[]| c),
406        }
407    }
408
409    fn num_node_inputs(&self, node: &Self::Signal) -> usize {
410        match self.get_node(*node) {
411            GeneralNode::Node(n) => n.num_inputs(),
412            GeneralNode::Input(_) => 0,
413            GeneralNode::Constant(_) => 0,
414        }
415    }
416
417    fn get_node_output(&self, node: &Self::NodeId) -> Self::Signal {
418        *node
419    }
420}
421
422impl<Node> NumInputs for LogicNetwork<Node> {
423    fn num_inputs(&self) -> usize {
424        self.primary_inputs.len()
425    }
426}
427
428impl<Node> NumOutputs for LogicNetwork<Node> {
429    fn num_outputs(&self) -> usize {
430        self.primary_outputs.len()
431    }
432}
433
434impl<Node> PartialBooleanSystem for LogicNetwork<Node>
435where
436    Node: NetworkNode<NodeId = NodeId>,
437{
438    type LiteralId = NodeId;
439
440    type TermId = NodeId;
441
442    fn evaluate_term_partial(&self, term: &Self::TermId, input_values: &[bool]) -> Option<bool> {
443        // The logic function of a MIG is always fully specified.
444        Some(self.evaluate_term(term, input_values))
445    }
446}
447
448impl<Node> BooleanSystem for LogicNetwork<Node>
449where
450    Node: NetworkNode<NodeId = NodeId>,
451{
452    fn evaluate_term(&self, term: &Self::TermId, input_values: &[bool]) -> bool {
453        let simulator = network_simulator::RecursiveSim::new(self);
454
455        assert_eq!(input_values.len(), self.num_primary_inputs());
456
457        let outputs: SmallVec<[_; 1]> = simulator.simulate(&[*term], input_values).collect();
458
459        outputs[0]
460    }
461}
462
463impl<Node> NetworkEdit for LogicNetwork<Node>
464where
465    Node: NetworkNode<NodeId = NodeId>
466        + Hash
467        + Eq
468        + MutNetworkNodeWithReferenceCount
469        + IntoIterator<Item = NodeId>,
470{
471    fn create_primary_input(&mut self) -> Self::Signal {
472        let idx = self.primary_inputs.len();
473        let signal = NodeId::new_input_node(idx);
474        self.primary_inputs.push(signal);
475        signal
476    }
477
478    fn create_primary_output(&mut self, signal: Self::Signal) -> Self::Signal {
479        self.primary_outputs.push(signal);
480        signal
481    }
482
483    fn substitute(&mut self, old: Self::Signal, new: Self::Signal) {
484        if let Some(idx) = old.node_index() {
485            let list_of_references = &mut self.storage[idx].references;
486            let list_of_edges = &mut self.storage[idx].outgoing_edges;
487        } else {
488            todo!()
489        }
490    }
491
492    fn create_node(&mut self, node: Self::Node) -> Self::NodeId {
493        match self.simplify_node_with_hashtable(node) {
494            SimplifyResult::Node(n, inv) => self.insert_node(n).invert_if(inv),
495            SimplifyResult::Simplified(node_id, inv) => node_id.invert_if(inv),
496        }
497    }
498
499    fn foreach_node_mut(&mut self, f: impl Fn(&mut Self::Node)) {
500        self.storage.iter_mut().for_each(|n| f(&mut n.node))
501    }
502}
503
504// impl<Node> GraphBase for LogicNetwork<Node> {
505//     type EdgeId = NodeId;
506//     type NodeId = NodeId;
507// }
508//
509// impl<Node> IntoNeighbors for &LogicNetwork<Node> {
510//     type Neighbors;
511//
512//     fn neighbors(self, a: Self::NodeId) -> Self::Neighbors {
513//         todo!()
514//     }
515// }
516//
517// impl<Node> IntoNeighborsDirected for &LogicNetwork<Node> {
518//     type NeighborsDirected;
519//
520//     fn neighbors_directed(
521//         self,
522//         n: Self::NodeId,
523//         d: petgraph::Direction,
524//     ) -> Self::NeighborsDirected {
525//         todo!()
526//     }
527// }
528//
529// impl<Node> IntoNodeIdentifiers for &LogicNetwork<Node> {
530//     type NodeIdentifiers;
531//
532//     fn node_identifiers(self) -> Self::NodeIdentifiers {
533//         todo!()
534//     }
535// }
536//
libreda_logic/networks/generic_network.rs

libreda_logic/networks/
generic_network.rs
