libreda_logic/
network.rs

1// SPDX-FileCopyrightText: 2022 Thomas Kramer <code@tkramer.ch>
2//
3// SPDX-License-Identifier: AGPL-3.0-or-later
4
5//! Abstraction of logic networks.
6
7use blanket::blanket;
8
9use std::hash::Hash;
10use std::ops::*;
11
12use crate::networks::SimplifyResult;
13use crate::traits::BooleanFunction;
14use crate::traits::LogicValue;
15
16use crate::{traits::IdType, truth_table::small_lut::SmallTruthTable};
17
18/// Basic properties of a logic network.
19#[blanket(derive(Ref, Mut))]
20pub trait Network {
21    /// Type of the logic node.
22    type Node: NetworkNode<NodeId = Self::Signal>;
23    /// Identifier of a logic node in this network.
24    type NodeId: Clone + PartialEq + Eq + Hash + Send + Sync + std::fmt::Debug + 'static;
25    /// Type which represents the outputs of network nodes, e.g. signals. In contrast to a `NodeId` a `Signal` might also encode a logic inversion.
26    type Signal: Copy + Clone + PartialEq + Eq + Hash + Send + Sync + std::fmt::Debug + 'static;
27    /// Type of signal values. Typically this might be `bool`.
28    type LogicValue: LogicValue;
29    /// Type which represents the logic function of nodes in the network.
30    type NodeFunction: BooleanFunction;
31
32    /// Visit all network gates in an undefined order.
33    /// Each gate is visited exactly once.
34    fn foreach_gate(&self, f: impl Fn(Self::Signal));
35
36    /// Visit all logic nodes.
37    fn foreach_node(&self, f: impl Fn(&Self::Node));
38
39    /// Get a graph signal which represents the constant `value`.
40    fn get_constant(&self, value: Self::LogicValue) -> Self::Signal;
41
42    /// Get the value of a signal if it is a constant.
43    fn get_constant_value(&self, signal: Self::Signal) -> Option<Self::LogicValue>;
44
45    /// Get an input value of a node.
46    fn get_node_input(&self, node: &Self::NodeId, input_index: usize) -> Self::Signal;
47
48    /// Get the output signal of a node.
49    fn get_node_output(&self, node: &Self::NodeId) -> Self::Signal;
50
51    /// Get the node which computes a signal.
52    fn get_source_node(&self, signal: &Self::Signal) -> Self::NodeId;
53
54    /// Get a primary input by its index.
55    fn get_primary_input(&self, index: usize) -> Self::Signal;
56
57    /// Get a primary output by its index.
58    fn get_primary_output(&self, index: usize) -> Self::Signal;
59
60    /// Tell if the signal is directly connected to a constant.
61    fn is_constant(&self, signal: Self::Signal) -> bool {
62        self.get_constant_value(signal).is_some()
63    }
64
65    /// Check if the signal is a primary input.
66    fn is_input(&self, signal: Self::Signal) -> bool;
67
68    /// Get the logic function implemented by the given node.
69    fn node_function(&self, node: Self::NodeId) -> Self::NodeFunction;
70
71    /// Number of gates present in the network.
72    fn num_gates(&self) -> usize;
73
74    /// Number of inputs into the given node.
75    fn num_node_inputs(&self, node: &Self::NodeId) -> usize;
76
77    /// Number of input into the network.
78    fn num_primary_inputs(&self) -> usize;
79
80    /// Number of outputs from the network.
81    fn num_primary_outputs(&self) -> usize;
82}
83
84/// A logic network where all nodes implement the same boolean function.
85pub trait HomogeneousNetwork: Network {
86    /// Number of inputs of a node.
87    const NUM_NODE_INPUTS: usize;
88
89    /// Get the logic function of a node.
90    fn function(&self) -> Self::NodeFunction;
91}
92
93/// Get the inverse of a signal without modifying the network.
94/// This can typically be done if the inversion is stored in the signal identifier.
95pub trait ImmutableNot: Network {
96    /// Get the inverted signal.
97    fn get_inverted(&self, a: Self::Signal) -> Self::Signal;
98
99    /// Check if this signal is inverted.
100    fn is_inverted(&self, a: Self::Signal) -> bool;
101}
102
103/// Provide the number of nodes which have a given node in their fan-in.
104pub trait ReferenceCounted: Network {
105    /// Count the number of nodes which have the signal `a` in their fan-in.
106    fn num_references(&self, a: Self::Signal) -> usize;
107}
108
109/// Generic functions to manipulate a logic network.
110#[blanket(derive(Mut))]
111pub trait NetworkEdit: Network {
112    /// Create a new input into the network.
113    fn create_primary_input(&mut self) -> Self::Signal;
114
115    /// Create an output of the network.
116    fn create_primary_output(&mut self, signal: Self::Signal) -> Self::Signal;
117
118    /// Substitute the `old` signal with the `new` signal in all nodes.
119    fn substitute(&mut self, old: Self::Signal, new: Self::Signal);
120
121    /// Insert a new node into the network.
122    /// Returns the ID of the new node. This function can also return IDs that already existed before.
123    /// For example if there is already a node with the same inputs.
124    fn create_node(&mut self, node: Self::Node) -> Self::NodeId;
125
126    /// Visit all logic nodes as mutable references.
127    fn foreach_node_mut(&mut self, f: impl Fn(&mut Self::Node));
128}
129
130/// A network which supports substituting input signals of nodes.
131#[blanket(derive(Mut))]
132pub trait SubstituteInNode: Network {
133    /// Substitute a signal with another signal in the given node.
134    fn substitute_in_node(
135        &mut self,
136        node: Self::NodeId,
137        old_signal: Self::Signal,
138        new_signal: Self::Signal,
139    );
140}
141
142/// Convenience functions implemented on top of the `Network` trait.
143pub trait NetworkShortcuts: Network {
144    /// Iterator over all primary inputs of the network.
145    fn primary_inputs(&self) -> Box<dyn Iterator<Item = Self::NodeId> + '_> {
146        Box::new(
147            (0..self.num_primary_inputs())
148                .map(|i| self.get_source_node(&self.get_primary_input(i))),
149        )
150    }
151
152    /// Iterator over all primary outputs of the network.
153    fn primary_outputs(&self) -> Box<dyn Iterator<Item = Self::Signal> + '_> {
154        Box::new((0..self.num_primary_outputs()).map(|i| self.get_primary_output(i)))
155    }
156}
157impl<T> NetworkShortcuts for T where T: Network {}
158
159/// Convenience functions implemented on top of the `NetworkEdit` trait.
160pub trait NetworkEditShortcuts: NetworkEdit {
161    /// Create many inputs at once.
162    fn create_primary_inputs<const NUM_INPUTS: usize>(&mut self) -> [Self::Signal; NUM_INPUTS] {
163        [(); NUM_INPUTS].map(|_| self.create_primary_input())
164    }
165}
166
167impl<T> NetworkEditShortcuts for T where T: NetworkEdit {}
168
169/// Unary logic operations.
170#[blanket(derive(Mut))]
171pub trait UnaryOp: NetworkEdit {
172    /// Replicate the signal.
173    fn create_buffer(&mut self, signal: Self::Signal) -> Self::Signal {
174        signal
175    }
176    /// Invert the signal.
177    fn create_not(&mut self, signal: Self::Signal) -> Self::Signal;
178}
179
180/// Binary logic operations.
181#[blanket(derive(Mut))]
182pub trait BinaryOp: UnaryOp {
183    /// Create the logic AND of `a` and `b`.
184    fn create_and(&mut self, a: Self::Signal, b: Self::Signal) -> Self::Signal;
185    /// Create the logic OR of `a` and `b`.
186    fn create_or(&mut self, a: Self::Signal, b: Self::Signal) -> Self::Signal;
187    /// Create the logic NAND of `a` and `b`.
188    fn create_nand(&mut self, a: Self::Signal, b: Self::Signal) -> Self::Signal;
189    /// Create the logic NOR of `a` and `b`.
190    fn create_nor(&mut self, a: Self::Signal, b: Self::Signal) -> Self::Signal;
191    /// Create the logic XOR of `a` and `b`.
192    fn create_xor(&mut self, a: Self::Signal, b: Self::Signal) -> Self::Signal;
193
194    /// Create XNOR gate.
195    fn create_xnor(&mut self, a: Self::Signal, b: Self::Signal) -> Self::Signal {
196        let xor = self.create_xor(a, b);
197        self.create_not(xor)
198    }
199    /// Less-than: Create a signal which is 1 only if `a == 0` and `b == 1`.
200    fn create_lt(&mut self, a: Self::Signal, b: Self::Signal) -> Self::Signal {
201        let a_not = self.create_not(a);
202        self.create_and(a_not, b)
203    }
204    /// Less-than-or-equal
205    fn create_le(&mut self, a: Self::Signal, b: Self::Signal) -> Self::Signal {
206        let a_not = self.create_not(a);
207        self.create_or(a_not, b)
208    }
209    /// Greater-than
210    fn create_gt(&mut self, a: Self::Signal, b: Self::Signal) -> Self::Signal {
211        self.create_lt(b, a)
212    }
213    /// Greater-than-or-equal
214    fn create_ge(&mut self, a: Self::Signal, b: Self::Signal) -> Self::Signal {
215        self.create_le(b, a)
216    }
217
218    /// Create a signal which is 1 only iff `a -> b`.
219    fn create_implies(&mut self, a: Self::Signal, b: Self::Signal) -> Self::Signal {
220        let a_not = self.create_not(a);
221        self.create_or(a_not, b)
222    }
223}
224
225/// Logic operations with three inputs.
226#[blanket(derive(Mut))]
227pub trait TernaryOp: BinaryOp {
228    /// Create three-input majority gate.
229    fn create_maj3(&mut self, a: Self::Signal, b: Self::Signal, c: Self::Signal) -> Self::Signal {
230        // Default implementation.
231        let ab = self.create_and(a, b);
232        let bc = self.create_and(b, c);
233        let ac = self.create_and(a, c);
234
235        let bc_or_ac = self.create_or(bc, ac);
236
237        self.create_or(ab, bc_or_ac)
238    }
239
240    /// Create if-then-else.
241    fn create_ite(
242        &mut self,
243        condition: Self::Signal,
244        then: Self::Signal,
245        otherwise: Self::Signal,
246    ) -> Self::Signal {
247        // Default implementation
248        let condition_not = self.create_not(condition);
249        let a = self.create_and(condition, then);
250        let b = self.create_and(condition_not, otherwise);
251        self.create_or(a, b)
252    }
253
254    /// Create three-input XOR.
255    fn create_xor3(&mut self, a: Self::Signal, b: Self::Signal, c: Self::Signal) -> Self::Signal {
256        let axb = self.create_xor(a, b);
257        self.create_xor(axb, c)
258    }
259}
260
261/// Logic operations with N inputs.
262#[blanket(derive(Mut))]
263pub trait NAryOp: TernaryOp {
264    /// Create the logic AND of all provided inputs.
265    fn create_nary_and(&mut self, inputs: impl Iterator<Item = Self::Signal>) -> Self::Signal {
266        // TODO: reduce as balanced tree
267        inputs
268            .reduce(|acc, s| self.create_and(acc, s))
269            .unwrap_or(self.get_constant(<Self as Network>::LogicValue::one()))
270    }
271
272    /// Create the logic OR of all provided inputs.
273    fn create_nary_or(&mut self, inputs: impl Iterator<Item = Self::Signal>) -> Self::Signal {
274        // TODO: reduce as balanced tree
275        inputs
276            .reduce(|acc, s| self.create_or(acc, s))
277            .unwrap_or(self.get_constant(<Self as Network>::LogicValue::zero()))
278    }
279}
280
281/// Basic trait of a node in a logic network.
282pub trait NetworkNode: Clone + Eq + PartialEq {
283    /// ID type used to identify nodes in the network.
284    type NodeId: IdType;
285
286    /// Get the number of inputs into this node.
287    fn num_inputs(&self) -> usize;
288
289    /// Get the i-th input.
290    /// # Panics
291    /// Panics if `i > self.num_inputs()`.
292    fn get_input(&self, i: usize) -> Self::NodeId;
293
294    /// Get the logic function of the node.
295    fn function(&self) -> SmallTruthTable;
296
297    /// Bring the node into a canonical form by reordering and inverting the inputs (if possible).
298    /// This increases the effectiveness of structural hashing.
299    ///
300    /// The node can also be simplified to a single signal (i.e. an AND node with one input set to constant `0` would reduce to `0`).
301    ///
302    /// Returns a tuple with the normalized node and a boolean which is `true` iff the output of the node has been inverted by the normalization.
303    fn normalized(self) -> SimplifyResult<Self, Self::NodeId>;
304}
305
306/// Mutable node in a logic network.
307pub trait MutNetworkNode: NetworkNode {
308    /// Set the input of a node.
309    fn set_input(&mut self, i: usize, signal: Self::NodeId);
310}
311
312/// Trait for a node which knows the number of its references.
313pub trait NetworkNodeWithReferenceCount: NetworkNode {
314    /// Get the number of references to this node.
315    fn num_references(&self) -> usize;
316}
317
318/// A logic node which implements a function known at compile time.
319pub trait StaticFunction {
320    // TODO const FUNCTION: TruthTable = ...
321}
322
323/// A logic node with a number of inputs known at compile time.
324pub trait StaticInputDegree<const NUM_INPUTS: usize>: NetworkNode {
325    /// Get node inputs as an array.
326    fn to_array(&self) -> [Self::NodeId; NUM_INPUTS];
327}
328
329/// Trait for a node which allows changing its reference counter.
330pub trait MutNetworkNodeWithReferenceCount: NetworkNodeWithReferenceCount {
331    /// Increment the reference counter.
332    fn reference(&mut self);
333
334    /// Decrement the reference counter.
335    /// # Panics
336    /// Panics if the reference counter is already 0.
337    fn dereference(&mut self);
338}
339
340/// Representation of a signal in a logic network.
341pub trait Edge: Sized {}
342
343/// Trait for an edge ID which encodes an optional inversion of the signal.
344pub trait EdgeWithInversion: Edge {
345    /// Check if the signal is inverted along the edge.
346    fn is_inverted(&self) -> bool;
347
348    /// Create the inverted version of this edge.
349    fn invert(self) -> Self;
350
351    /// Create the inverted version of this edge iff `condition` is set to `true`, otherwise return a copy of the edge.
352    fn invert_if(self, condition: bool) -> Self {
353        if condition {
354            self.invert()
355        } else {
356            self
357        }
358    }
359
360    /// Get the non-inverted version of this edge.
361    fn non_inverted(self) -> Self {
362        // Default implementation.
363        if self.is_inverted() {
364            self.invert()
365        } else {
366            self
367        }
368    }
369}
libreda_logic/network.rs

libreda_logic/
network.rs
