libreda_logic/networks/
klut.rs

1// SPDX-FileCopyrightText: 2022 Thomas Kramer <code@tkramer.ch>
2//
3// SPDX-License-Identifier: AGPL-3.0-or-later
4
5//! A logic network built from k-input lookup-tables ('k-LUT').
6
7use smallvec::{smallvec, SmallVec};
8
9use crate::network::NetworkEdit;
10use crate::truth_table::bitflip_iter::BitFlippable;
11use crate::truth_table::small_lut::SmallTT;
12use crate::{
13    network::{
14        BinaryOp, EdgeWithInversion, MutNetworkNodeWithReferenceCount, NetworkNode,
15        NetworkNodeWithReferenceCount, TernaryOp, UnaryOp,
16    },
17    traits::*,
18    truth_table::small_lut::{truth_table_library, SmallTruthTable},
19};
20use truth_table_library as ttlib;
21
22use super::generic_network::{LogicNetwork, NodeId};
23use super::SimplifyResult;
24
25/// A logic network which consists of `k`-input lookup-tables.
26pub type KLutNetwork = LogicNetwork<LutNode<NodeId>>;
27
28impl KLutNetwork {
29    /// Normalize the node and insert it.
30    fn insert_node_normalized(&mut self, node: LutNode<NodeId>) -> NodeId {
31        match node.normalized() {
32            SimplifyResult::Node(n, inv) => self.create_node(n).invert_if(inv),
33            SimplifyResult::Simplified(id, inv) => id.invert_if(inv),
34        }
35    }
36}
37
38/// Step of a boolean chain. The operator implemented by the step is represented by a truth-table.
39#[derive(Clone, Hash, PartialEq, Eq)]
40pub struct LutNode<NodeId> {
41    /// Truth-table of the operator.
42    truth_table: SmallTruthTable,
43    inputs: SmallVec<[NodeId; 6]>, // Can have up to 6 inputs.
44    num_references: usize,         // TODO: Move this to some `GeneralNode<Function>`
45}
46
47impl<NodeId> LutNode<NodeId> {
48    /// Create a new `k-LUT` node. The node function is specified by the `truth_table`.
49    pub fn new(truth_table: SmallTruthTable, inputs: SmallVec<[NodeId; 6]>) -> Self {
50        Self {
51            truth_table,
52            inputs,
53            num_references: 0,
54        }
55    }
56}
57
58impl<NodeId: EdgeWithInversion + Copy + Ord> LutNode<NodeId> {
59    /// Normalize the node by flipping the inputs to their non-inverted version and ordering the inputs lexicographically.
60    /// This also modifies the truth-table of the node.
61    ///
62    fn normalize(self) -> SimplifyResult<Self, NodeId> {
63        let Self {
64            mut truth_table,
65            mut inputs,
66            num_references,
67        } = self;
68
69        // Normalize polarities of inputs.
70        // Flip inputs to their non-inverted version.
71        inputs.iter_mut().enumerate().for_each(|(idx, input)| {
72            if input.is_inverted() {
73                *input = input.invert();
74                truth_table.flip_bit(idx);
75            }
76        });
77
78        // Normalize ordering of inputs.
79        // Sort the inputs by swapping pairs of inputs.
80        for i in 0..inputs.len().saturating_sub(1) {
81            // Find the smallest signal ID in the remaining list.
82            let min_idx = inputs[i..]
83                .iter()
84                .enumerate()
85                .min_by_key(|(_pos, input)| *input)
86                .map(|(pos, _)| pos + i)
87                .unwrap();
88
89            if min_idx != i {
90                // Swap inputs if necessary.
91                inputs.swap(i, min_idx);
92                truth_table.swap_inputs(i, min_idx);
93            }
94        }
95
96        // Invert the output value.
97        let truth_table_inv = truth_table.invert();
98
99        let (truth_table, inverted) = if truth_table < truth_table_inv {
100            (truth_table, false)
101        } else {
102            (truth_table_inv, true)
103        };
104
105        let normalized = Self {
106            truth_table,
107            inputs,
108            num_references,
109        };
110
111        SimplifyResult::Node(normalized, inverted)
112    }
113}
114
115#[test]
116fn test_normalize_lut_node() {
117    let a = NodeId::new_node_id(2);
118    let b = NodeId::new_node_id(1);
119    let c = NodeId::new_node_id(3);
120
121    {
122        let maj3 = SmallTruthTable::new(|[a, b, c]| (a as u8) + (b as u8) + (c as u8) >= 2);
123        let maj3_modified =
124            SmallTruthTable::new(|[b, a, c]| (!a as u8) + (b as u8) + (c as u8) >= 2);
125
126        let node = LutNode::new(maj3, smallvec![a, b.invert(), c]);
127
128        match node.normalize() {
129            SimplifyResult::Node(node, inverted) => {
130                assert_eq!(node.inputs.as_slice(), [b, a, c].as_slice());
131                assert_eq!(node.truth_table, maj3_modified.invert_if(inverted));
132            }
133            SimplifyResult::Simplified(_, _) => assert!(false),
134        }
135    }
136}
137
138impl<NodeId: IdType + EdgeWithInversion> NetworkNode for LutNode<NodeId> {
139    type NodeId = NodeId;
140
141    fn num_inputs(&self) -> usize {
142        self.truth_table.num_inputs()
143    }
144
145    fn get_input(&self, i: usize) -> Self::NodeId {
146        self.inputs[i]
147    }
148
149    fn function(&self) -> SmallTruthTable {
150        self.truth_table
151    }
152
153    fn normalized(self) -> SimplifyResult<Self, Self::NodeId> {
154        self.normalize()
155    }
156}
157
158impl<NodeId> IntoIterator for LutNode<NodeId> {
159    type Item = NodeId;
160
161    type IntoIter = smallvec::IntoIter<[NodeId; 6]>;
162
163    fn into_iter(self) -> Self::IntoIter {
164        self.inputs.into_iter()
165    }
166}
167
168impl<NodeId: IdType + EdgeWithInversion> NetworkNodeWithReferenceCount for LutNode<NodeId> {
169    fn num_references(&self) -> usize {
170        self.num_references
171    }
172}
173
174impl<NodeId: IdType + EdgeWithInversion> MutNetworkNodeWithReferenceCount for LutNode<NodeId> {
175    fn reference(&mut self) {
176        self.num_references += 1
177    }
178
179    fn dereference(&mut self) {
180        self.num_references -= 1
181    }
182}
183
184impl UnaryOp for KLutNetwork {
185    fn create_not(&mut self, signal: Self::Signal) -> Self::Signal {
186        signal.invert()
187    }
188}
189
190impl BinaryOp for KLutNetwork {
191    fn create_and(&mut self, a: Self::Signal, b: Self::Signal) -> Self::Signal {
192        let node = LutNode::new(ttlib::and2(), smallvec![a, b]);
193        self.insert_node_normalized(node)
194    }
195
196    fn create_or(&mut self, a: Self::Signal, b: Self::Signal) -> Self::Signal {
197        let node = LutNode::new(ttlib::or2(), smallvec![a, b]);
198        self.insert_node_normalized(node)
199    }
200
201    fn create_nand(&mut self, a: Self::Signal, b: Self::Signal) -> Self::Signal {
202        let node = LutNode::new(ttlib::nand2(), smallvec![a, b]);
203        self.insert_node_normalized(node)
204    }
205
206    fn create_nor(&mut self, a: Self::Signal, b: Self::Signal) -> Self::Signal {
207        let node = LutNode::new(ttlib::nor2(), smallvec![a, b]);
208        self.insert_node_normalized(node)
209    }
210
211    fn create_xor(&mut self, a: Self::Signal, b: Self::Signal) -> Self::Signal {
212        let node = LutNode::new(ttlib::xor2(), smallvec![a, b]);
213        self.insert_node_normalized(node)
214    }
215}
216
217impl TernaryOp for KLutNetwork {
218    fn create_maj3(&mut self, a: Self::Signal, b: Self::Signal, c: Self::Signal) -> Self::Signal {
219        let node = LutNode::new(ttlib::maj3(), smallvec![a, b, c]);
220        self.insert_node_normalized(node)
221    }
222
223    fn create_ite(
224        &mut self,
225        condition: Self::Signal,
226        then: Self::Signal,
227        otherwise: Self::Signal,
228    ) -> Self::Signal {
229        let tt = SmallTruthTable::new(|[a, b, c]| if a { b } else { c });
230        self.insert_node_normalized(LutNode::new(tt, smallvec![condition, then, otherwise]))
231    }
232
233    fn create_xor3(&mut self, a: Self::Signal, b: Self::Signal, c: Self::Signal) -> Self::Signal {
234        let tt = SmallTruthTable::new(|[a, b, c]| a ^ b ^ c);
235        self.insert_node_normalized(LutNode::new(tt, smallvec![a, b, c]))
236    }
237}
238
239#[test]
240fn test_simulate_klut_graph() {
241    use crate::native_boolean_functions::NativeBooleanFunction;
242    use crate::network::NetworkEdit;
243    use crate::network::NetworkEditShortcuts;
244    use crate::traits::BooleanSystem;
245
246    // Construct a one-bit full adder.
247    let mut g = KLutNetwork::new();
248    let [in1, in2, carry_in] = g.create_primary_inputs();
249
250    let sum = g.create_xor3(in1, in2, carry_in);
251    let carry = g.create_maj3(in1, in2, carry_in);
252
253    let output_sum = g.create_primary_output(sum);
254    let output_carry = g.create_primary_output(carry);
255
256    let simulator = crate::network_simulator::RecursiveSim::new(&g);
257
258    // Reference model of the full adder.
259    fn full_adder([a, b, c]: [bool; 3]) -> [bool; 2] {
260        let sum = (a as usize) + (b as usize) + (c as usize);
261        [
262            sum & 0b1 == 1,
263            sum & 0b10 == 0b10, // carry
264        ]
265    }
266
267    let reference = NativeBooleanFunction::new(full_adder);
268
269    for i in 0..(1 << 3) {
270        let inputs = [0, 1, 2].map(|idx| (i >> idx) & 1 == 1);
271
272        let exptected_output = [0, 1].map(|out| reference.evaluate_term(&out, &inputs));
273        let actual_output: Vec<_> = simulator
274            .simulate(&[output_sum, output_carry], &inputs)
275            .collect();
276
277        dbg!(inputs);
278
279        assert_eq!(exptected_output.as_slice(), actual_output.as_slice());
280    }
281}
libreda_logic/networks/klut.rs

libreda_logic/networks/
klut.rs
