prjunnamed_lut/
lib.rs

1use std::{
2    borrow::Cow,
3    collections::{hash_map, HashMap},
4};
5
6use prjunnamed_netlist::{Cell, Const, ControlNet, Net, Trit, Value};
7
8#[derive(Debug, Clone)]
9enum SwizzleInput {
10    Zero,
11    One,
12    NewInput(Vec<usize>),
13}
14
15fn swizzle(old_table: &Const, old_inputs: &[SwizzleInput], new_inputs_len: usize) -> Const {
16    assert_eq!(old_table.len(), 1 << old_inputs.len());
17    let mut result = Const::new();
18    'bits: for index in 0..(1 << new_inputs_len) {
19        let mut old_index = 0;
20        for (old_bit_index, old_input) in old_inputs.iter().enumerate() {
21            let input_value = match old_input {
22                SwizzleInput::Zero => false,
23                SwizzleInput::One => true,
24                SwizzleInput::NewInput(new_inputs) => {
25                    let input_value1 = ((index >> new_inputs[0]) & 1) != 0;
26                    for &new_input in new_inputs {
27                        assert!(new_input < new_inputs_len);
28                        let input_value2 = ((index >> new_input) & 1) != 0;
29                        if input_value2 != input_value1 {
30                            // impossible combination, go eat an X
31                            result.extend([Trit::Undef]);
32                            continue 'bits;
33                        }
34                    }
35                    input_value1
36                }
37            };
38            if input_value {
39                old_index |= 1 << old_bit_index;
40            }
41        }
42        result.extend([old_table[old_index]]);
43    }
44    result
45}
46
47#[derive(Debug, Clone, PartialEq, Eq)]
48pub struct Lut {
49    inputs: Value,
50    table: Const,
51}
52
53impl Lut {
54    pub fn new(inputs: impl Into<Value>, table: impl Into<Const>) -> Lut {
55        let (inputs, table) = (inputs.into(), table.into());
56        assert_eq!(1 << inputs.len(), table.len());
57        let mut lut = Lut { inputs, table };
58        lut.simplify();
59        lut
60    }
61
62    pub fn new_fixed(inputs: impl Into<Value>, table: impl Into<Const>) -> Lut {
63        let (inputs, table) = (inputs.into(), table.into());
64        assert_eq!(1 << inputs.len(), table.len());
65        Lut { inputs, table }
66    }
67
68    pub fn lut1(in0: impl Into<Net>, table: impl Into<Const>) -> Lut {
69        Self::new([in0.into()].as_ref(), table)
70    }
71
72    pub fn lut2(in0: impl Into<Net>, in1: impl Into<Net>, table: impl Into<Const>) -> Lut {
73        Self::new([in0.into(), in1.into()].as_ref(), table)
74    }
75
76    pub fn lut3(in0: impl Into<Net>, in1: impl Into<Net>, in2: impl Into<Net>, table: impl Into<Const>) -> Lut {
77        Self::new([in0.into(), in1.into(), in2.into()].as_ref(), table)
78    }
79
80    pub fn lut4(
81        in0: impl Into<Net>,
82        in1: impl Into<Net>,
83        in2: impl Into<Net>,
84        in3: impl Into<Net>,
85        table: impl Into<Const>,
86    ) -> Lut {
87        Self::new([in0.into(), in1.into(), in2.into(), in3.into()].as_ref(), table)
88    }
89
90    pub fn inputs(&self) -> &Value {
91        &self.inputs
92    }
93
94    pub fn table(&self) -> &Const {
95        &self.table
96    }
97
98    pub fn from_cell<'a>(cell: impl Into<Cow<'a, Cell>>) -> Option<Lut> {
99        let cell = cell.into();
100        assert_eq!(cell.output_len(), 1);
101        Some(match &*cell {
102            Cell::Buf(arg) => Self::lut1(arg[0], Const::lit("10")),
103            Cell::Not(arg) => Self::lut1(arg[0], Const::lit("01")),
104            Cell::And(arg1, arg2) => Self::lut2(arg1[0], arg2[0], Const::lit("1000")),
105            Cell::Or(arg1, arg2) => Self::lut2(arg1[0], arg2[0], Const::lit("1110")),
106            Cell::Xor(arg1, arg2) => Self::lut2(arg1[0], arg2[0], Const::lit("0110")),
107            Cell::Mux(arg1, arg2, arg3) => Self::lut3(arg3[0], arg2[0], *arg1, Const::lit("11001010")),
108            Cell::Aig(arg1, arg2) => Self::lut2(
109                arg1.net(),
110                arg2.net(),
111                Const::lit(match (arg1, arg2) {
112                    (ControlNet::Neg(_), ControlNet::Neg(_)) => "0001",
113                    (ControlNet::Neg(_), ControlNet::Pos(_)) => "0010",
114                    (ControlNet::Pos(_), ControlNet::Neg(_)) => "0100",
115                    (ControlNet::Pos(_), ControlNet::Pos(_)) => "1000",
116                }),
117            ),
118            _ => return None,
119        })
120    }
121
122    fn split(&self, input_index: usize) -> (Value, Const, Const) {
123        let mut old_inputs = Vec::from_iter((0..self.inputs.len()).map(|index| {
124            if index == input_index {
125                SwizzleInput::Zero
126            } else if index < input_index {
127                SwizzleInput::NewInput(vec![index])
128            } else {
129                SwizzleInput::NewInput(vec![index - 1])
130            }
131        }));
132        let table0 = swizzle(&self.table, &old_inputs, self.inputs.len() - 1);
133        old_inputs[input_index] = SwizzleInput::One;
134        let table1 = swizzle(&self.table, &old_inputs, self.inputs.len() - 1);
135        let inputs = self.inputs.slice(..input_index).concat(self.inputs.slice(input_index + 1..));
136        (inputs, table0, table1)
137    }
138
139    pub fn simplify(&mut self) {
140        let mut old_inputs = vec![];
141        let mut new_inputs = Value::new();
142        let mut new_inputs_index = HashMap::new();
143        for input in &self.inputs {
144            if input == Net::ZERO {
145                old_inputs.push(SwizzleInput::Zero);
146            } else if input == Net::ONE {
147                old_inputs.push(SwizzleInput::One);
148            } else {
149                match new_inputs_index.entry(input) {
150                    hash_map::Entry::Occupied(entry) => {
151                        old_inputs.push(SwizzleInput::NewInput(vec![*entry.get()]));
152                    }
153                    hash_map::Entry::Vacant(entry) => {
154                        let index = new_inputs.len();
155                        old_inputs.push(SwizzleInput::NewInput(vec![index]));
156                        entry.insert(index);
157                        new_inputs.extend([input]);
158                    }
159                }
160            }
161        }
162        self.table = swizzle(&self.table, &old_inputs, new_inputs.len());
163        self.inputs = new_inputs;
164        for input_index in (0..self.inputs.len()).rev() {
165            let (inputs, table0, table1) = self.split(input_index);
166            let input = self.inputs[input_index];
167            let table = if input == Net::UNDEF {
168                (Trit::Undef).mux(table0, table1)
169            } else if let Some(table) = Const::combine(table0, table1) {
170                table
171            } else {
172                continue;
173            };
174            self.inputs = inputs;
175            self.table = table;
176        }
177    }
178
179    pub fn expand_with_fixed(&self, inputs: &[Option<Net>]) -> Option<Lut> {
180        let mut inputs = inputs.to_vec();
181        let mut input_to_index: HashMap<Net, Vec<usize>> = HashMap::new();
182        for (index, &input) in inputs.iter().enumerate() {
183            if let Some(input) = input {
184                input_to_index.entry(input).or_default().push(index);
185            }
186        }
187        let mut old_inputs = vec![];
188        'inputs: for input in &self.inputs {
189            if let Some(indices) = input_to_index.get(&input) {
190                old_inputs.push(SwizzleInput::NewInput(indices.clone()));
191                continue;
192            }
193            for (index, cur_input) in inputs.iter().enumerate() {
194                if cur_input.is_none() {
195                    inputs[index] = Some(input);
196                    old_inputs.push(SwizzleInput::NewInput(vec![index]));
197                    continue 'inputs;
198                }
199            }
200            // out of space.
201            return None;
202        }
203        let table = swizzle(&self.table, &old_inputs, inputs.len());
204        Some(Lut { inputs: Value::from_iter(inputs.into_iter().map(|x| x.unwrap_or(Net::UNDEF))), table })
205    }
206
207    pub fn expand_to(&self, width: usize) -> Option<Lut> {
208        self.expand_with_fixed(&vec![None; width])
209    }
210
211    pub fn merge(&self, input_index: usize, other: &Lut) -> Lut {
212        let (mut inputs, table0, table1) = self.split(input_index);
213        inputs.extend(&other.inputs);
214        let tablex = (Trit::Undef).mux(&table0, &table1);
215        let table = Const::from_iter(other.table.iter().flat_map(|bit| match bit {
216            Trit::Undef => &tablex,
217            Trit::Zero => &table0,
218            Trit::One => &table1,
219        }));
220        Lut::new(inputs, table)
221    }
222}
prjunnamed_lut/lib.rs

prjunnamed_lut/
lib.rs
