prjunnamed_netlist/
logic.rs

1use std::{
2    borrow::Cow,
3    fmt::{Debug, Display},
4    ops::{Index, IndexMut},
5    slice::SliceIndex,
6    str::FromStr,
7};
8
9use crate::Net;
10
11/// An extended binary value.
12///
13/// In addition to the usual `0` and `1`, the `X` value (also known as "undef") means that either `0` and `1`
14/// may be encountered. The undef value is used in both optimization and simulation, and its exact semantics
15/// depends on the context where it is used.
16#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
17pub enum Trit {
18    Undef = -1,
19    Zero = 0,
20    One = 1,
21}
22
23#[derive(Debug, Copy, Clone)]
24pub struct InvalidTritCharacter;
25
26impl Trit {
27    pub fn from_char(chr: char) -> Result<Self, InvalidTritCharacter> {
28        match chr {
29            '0' => Ok(Trit::Zero),
30            '1' => Ok(Trit::One),
31            'X' => Ok(Trit::Undef),
32            _ => Err(InvalidTritCharacter),
33        }
34    }
35
36    pub fn lit(chr: char) -> Self {
37        Self::from_char(chr).unwrap()
38    }
39
40    pub fn combine(lft: Trit, rgt: Trit) -> Option<Trit> {
41        match (lft, rgt) {
42            (Trit::Undef, trit) | (trit, Trit::Undef) => Some(trit),
43            _ if lft == rgt => Some(lft),
44            _ => None,
45        }
46    }
47
48    pub fn mux<'a, 'b>(self, arg1: impl Into<Cow<'a, Const>>, arg2: impl Into<Cow<'b, Const>>) -> Const {
49        let arg1 = arg1.into();
50        let arg2 = arg2.into();
51        match self {
52            Trit::One => arg1.into_owned(),
53            Trit::Zero => arg2.into_owned(),
54            Trit::Undef => {
55                Const::from_iter(arg1.iter().zip(arg2.iter()).map(|(x, y)| if x == y { x } else { Trit::Undef }))
56            }
57        }
58    }
59}
60
61impl Display for Trit {
62    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
63        match self {
64            Trit::Undef => write!(f, "X"),
65            Trit::Zero => write!(f, "0"),
66            Trit::One => write!(f, "1"),
67        }
68    }
69}
70
71impl FromStr for Trit {
72    type Err = ();
73
74    fn from_str(s: &str) -> Result<Self, Self::Err> {
75        match s {
76            "X" => Ok(Trit::Undef),
77            "0" => Ok(Trit::Zero),
78            "1" => Ok(Trit::One),
79            _ => Err(()),
80        }
81    }
82}
83
84impl From<bool> for Trit {
85    fn from(value: bool) -> Self {
86        match value {
87            false => Trit::Zero,
88            true => Trit::One,
89        }
90    }
91}
92
93impl TryFrom<Net> for Trit {
94    type Error = ();
95
96    fn try_from(value: Net) -> Result<Self, Self::Error> {
97        if value == Net::UNDEF {
98            Ok(Trit::Undef)
99        } else if value == Net::ZERO {
100            Ok(Trit::Zero)
101        } else if value == Net::ONE {
102            Ok(Trit::One)
103        } else {
104            Err(())
105        }
106    }
107}
108
109impl std::ops::Not for Trit {
110    type Output = Trit;
111
112    fn not(self) -> Self::Output {
113        match self {
114            Trit::One => Trit::Zero,
115            Trit::Zero => Trit::One,
116            Trit::Undef => Trit::Undef,
117        }
118    }
119}
120
121impl std::ops::BitAnd<Trit> for Trit {
122    type Output = Trit;
123
124    fn bitand(self, rhs: Trit) -> Self::Output {
125        match (self, rhs) {
126            (Trit::Zero, _) => Trit::Zero,
127            (_, Trit::Zero) => Trit::Zero,
128            (Trit::Undef, _) => Trit::Undef,
129            (_, Trit::Undef) => Trit::Undef,
130            (Trit::One, Trit::One) => Trit::One,
131        }
132    }
133}
134
135impl std::ops::BitOr<Trit> for Trit {
136    type Output = Trit;
137
138    fn bitor(self, rhs: Trit) -> Self::Output {
139        match (self, rhs) {
140            (Trit::One, _) => Trit::One,
141            (_, Trit::One) => Trit::One,
142            (Trit::Undef, _) => Trit::Undef,
143            (_, Trit::Undef) => Trit::Undef,
144            (Trit::Zero, Trit::Zero) => Trit::Zero,
145        }
146    }
147}
148
149impl std::ops::BitXor<Trit> for Trit {
150    type Output = Trit;
151
152    fn bitxor(self, rhs: Trit) -> Self::Output {
153        match (self, rhs) {
154            (Trit::Undef, _) => Trit::Undef,
155            (_, Trit::Undef) => Trit::Undef,
156            (Trit::One, Trit::One) => Trit::Zero,
157            (Trit::One, Trit::Zero) => Trit::One,
158            (Trit::Zero, Trit::One) => Trit::One,
159            (Trit::Zero, Trit::Zero) => Trit::Zero,
160        }
161    }
162}
163
164/// A constant is a (possibly empty) sequence of [`Trit`]s.
165#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
166pub struct Const {
167    trits: Vec<Trit>,
168}
169
170impl Const {
171    /// Creates an empty constant.
172    pub const fn new() -> Self {
173        Self { trits: vec![] }
174    }
175
176    /// Creates an all-`0` constant of given width.
177    pub fn zero(width: usize) -> Self {
178        Self::from_iter(std::iter::repeat_n(Trit::Zero, width))
179    }
180
181    /// Creates an all-`1` constant of given width.
182    pub fn ones(width: usize) -> Self {
183        Self::from_iter(std::iter::repeat_n(Trit::One, width))
184    }
185
186    /// Creates an all-`X` constant of given width.
187    pub fn undef(width: usize) -> Self {
188        Self::from_iter(std::iter::repeat_n(Trit::Undef, width))
189    }
190
191    /// Creates a constant of given width that has a `1` at position `hot_at` and `0` elsewhere.
192    pub fn one_hot(width: usize, hot_at: usize) -> Self {
193        assert!(hot_at < width);
194        Self::from_iter((0..width).map(|index| if index == hot_at { Trit::One } else { Trit::Zero }))
195    }
196
197    /// Expands the constant by a single position with the given value.
198    pub fn push(&mut self, trit: impl Into<Trit>) {
199        self.trits.push(trit.into());
200    }
201
202    pub fn from_uint(val: u128, bits: usize) -> Self {
203        let mut trits = vec![];
204        if bits < 128 {
205            assert!(val < (1 << bits));
206        }
207        for i in 0..bits {
208            let trit = if i < u128::BITS as usize && ((val >> i) & 1) != 0 { Trit::One } else { Trit::Zero };
209            trits.push(trit);
210        }
211        Self { trits }
212    }
213
214    pub fn lit(value: &str) -> Self {
215        value.parse().unwrap()
216    }
217
218    pub fn len(&self) -> usize {
219        self.trits.len()
220    }
221
222    pub fn is_empty(&self) -> bool {
223        self.trits.is_empty()
224    }
225
226    pub fn iter(&self) -> impl DoubleEndedIterator<Item = Trit> + ExactSizeIterator + '_ {
227        self.trits.iter().copied()
228    }
229
230    pub fn lsb(&self) -> Trit {
231        self.trits[0]
232    }
233
234    pub fn msb(&self) -> Trit {
235        self.trits[self.len() - 1]
236    }
237
238    pub fn is_zero(&self) -> bool {
239        self.trits.iter().all(|&trit| trit == Trit::Zero)
240    }
241
242    pub fn is_ones(&self) -> bool {
243        self.trits.iter().all(|&trit| trit == Trit::One)
244    }
245
246    pub fn is_undef(&self) -> bool {
247        self.trits.iter().all(|&trit| trit == Trit::Undef)
248    }
249
250    pub fn has_undef(&self) -> bool {
251        self.trits.contains(&Trit::Undef)
252    }
253
254    pub fn as_power_of_two(&self) -> Option<u32> {
255        let mut result = None;
256        for (offset, trit) in self.trits.iter().copied().enumerate() {
257            if trit == Trit::Undef {
258                return None;
259            }
260            if trit == Trit::One {
261                if result.is_some() {
262                    return None;
263                }
264                result = Some(offset as u32);
265            }
266        }
267        result
268    }
269
270    pub fn concat<'a>(&self, other: impl Into<Cow<'a, Const>>) -> Self {
271        Self::from_iter(self.iter().chain(other.into().iter()))
272    }
273
274    pub fn repeat(&self, count: usize) -> Self {
275        Const::from_iter((0..count).flat_map(|_| self))
276    }
277
278    pub fn slice(&self, range: impl std::ops::RangeBounds<usize>) -> Const {
279        Const::from_iter(self[(range.start_bound().cloned(), range.end_bound().cloned())].iter().copied())
280    }
281
282    pub fn combine<'a, 'b>(lft: impl Into<Cow<'a, Const>>, rgt: impl Into<Cow<'b, Const>>) -> Option<Const> {
283        let (lft, rgt) = (lft.into(), rgt.into());
284        assert_eq!(lft.len(), rgt.len());
285        let mut trits = vec![];
286        for (lft, rgt) in std::iter::zip(lft.iter(), rgt.iter()) {
287            trits.push(Trit::combine(lft, rgt)?);
288        }
289        Some(Const { trits })
290    }
291
292    pub fn not(&self) -> Const {
293        Const::from_iter(self.iter().map(|x| !x))
294    }
295
296    pub fn and<'a>(&self, other: impl Into<Cow<'a, Const>>) -> Const {
297        let other = other.into();
298        assert_eq!(self.len(), other.len());
299        Const::from_iter(self.iter().zip(other.iter()).map(|(x, y)| x & y))
300    }
301
302    pub fn or<'a>(&self, other: impl Into<Cow<'a, Const>>) -> Const {
303        let other = other.into();
304        assert_eq!(self.len(), other.len());
305        Const::from_iter(self.iter().zip(other.iter()).map(|(x, y)| x | y))
306    }
307
308    pub fn xor<'a>(&self, other: impl Into<Cow<'a, Const>>) -> Const {
309        let other = other.into();
310        assert_eq!(self.len(), other.len());
311        Const::from_iter(self.iter().zip(other.iter()).map(|(x, y)| x ^ y))
312    }
313
314    pub fn adc<'a>(&self, other: impl Into<Cow<'a, Const>>, ci: Trit) -> Const {
315        let other = other.into();
316        assert_eq!(self.len(), other.len());
317        let mut sum = vec![];
318        let mut carry = ci;
319        for (a, b) in self.iter().zip(other.iter()) {
320            let (y, co) = match (a, b, carry) {
321                (Trit::Undef, _, _) => (Trit::Undef, Trit::Undef),
322                (_, Trit::Undef, _) => (Trit::Undef, Trit::Undef),
323                (_, _, Trit::Undef) => (Trit::Undef, Trit::Undef),
324                (Trit::Zero, Trit::Zero, s) => (s, Trit::Zero),
325                (Trit::Zero, s, Trit::Zero) => (s, Trit::Zero),
326                (s, Trit::Zero, Trit::Zero) => (s, Trit::Zero),
327                (Trit::One, Trit::One, s) => (s, Trit::One),
328                (Trit::One, s, Trit::One) => (s, Trit::One),
329                (s, Trit::One, Trit::One) => (s, Trit::One),
330            };
331            carry = co;
332            sum.push(y);
333        }
334        sum.push(carry);
335        Const::from_iter(sum)
336    }
337
338    pub fn eq<'a>(&self, other: impl Into<Cow<'a, Const>>) -> Trit {
339        let other = other.into();
340        assert_eq!(self.len(), other.len());
341        let mut undef = false;
342        for (x, y) in self.iter().zip(other.iter()) {
343            if x == Trit::Undef || y == Trit::Undef {
344                undef = true;
345            } else if x != y {
346                return Trit::Zero;
347            }
348        }
349        if undef { Trit::Undef } else { Trit::One }
350    }
351
352    pub fn ult<'a>(&self, other: impl Into<Cow<'a, Const>>) -> Trit {
353        let other = other.into();
354        assert_eq!(self.len(), other.len());
355        if self.has_undef() || other.has_undef() {
356            Trit::Undef
357        } else {
358            for (x, y) in self.iter().zip(other.iter()).rev() {
359                if x != y {
360                    return Trit::from(x < y);
361                }
362            }
363            Trit::Zero
364        }
365    }
366
367    pub fn slt<'a>(&self, other: impl Into<Cow<'a, Const>>) -> Trit {
368        let other = other.into();
369        assert_eq!(self.len(), other.len());
370        if self.has_undef() || other.has_undef() {
371            Trit::Undef
372        } else if self.msb() != other.msb() {
373            Trit::from(self.msb() > other.msb())
374        } else {
375            for (x, y) in self.iter().zip(other.iter()).rev() {
376                if x != y {
377                    return Trit::from(x < y);
378                }
379            }
380            Trit::Zero
381        }
382    }
383
384    pub fn mul<'a>(&self, other: impl Into<Cow<'a, Const>>) -> Const {
385        let other = other.into();
386        assert_eq!(self.len(), other.len());
387        if self.has_undef() || other.has_undef() {
388            Const::undef(self.len())
389        } else {
390            let mut res = Const::zero(self.len());
391            for (i, bit) in other.iter().enumerate() {
392                if bit == Trit::One {
393                    res = res.adc(Const::zero(i).concat(self), Trit::Zero);
394                } else {
395                    res.trits.push(Trit::Zero);
396                }
397            }
398            res.slice(..self.len())
399        }
400    }
401}
402
403impl Debug for Const {
404    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
405        write!(f, "Const::from_iter([")?;
406        for (index, trit) in self.trits.iter().enumerate() {
407            if index != 0 {
408                write!(f, ", ")?;
409            }
410            write!(f, "{trit:?}")?;
411        }
412        write!(f, "])")?;
413        Ok(())
414    }
415}
416
417impl Display for Const {
418    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
419        for trit in self.trits.iter().rev() {
420            write!(f, "{trit}")?;
421        }
422        Ok(())
423    }
424}
425
426impl FromStr for Const {
427    type Err = InvalidTritCharacter;
428
429    fn from_str(s: &str) -> Result<Self, Self::Err> {
430        let mut trits = vec![];
431        for char in s.chars().rev() {
432            trits.push(Trit::from_char(char)?)
433        }
434        Ok(Const { trits })
435    }
436}
437
438#[derive(Debug, Copy, Clone)]
439pub enum ConstToIntError {
440    HasUndef,
441    Overflow,
442}
443
444impl TryFrom<&Const> for u64 {
445    type Error = ConstToIntError;
446
447    fn try_from(value: &Const) -> Result<Self, Self::Error> {
448        if value.has_undef() {
449            return Err(ConstToIntError::HasUndef);
450        }
451        let mut result = 0;
452        for (index, trit) in value.iter().enumerate() {
453            if trit == Trit::One {
454                if index >= 64 {
455                    return Err(ConstToIntError::Overflow);
456                }
457                result |= 1 << index;
458            }
459        }
460        Ok(result)
461    }
462}
463
464impl TryFrom<&Const> for i64 {
465    type Error = ConstToIntError;
466
467    fn try_from(value: &Const) -> Result<Self, Self::Error> {
468        if value.has_undef() {
469            return Err(ConstToIntError::HasUndef);
470        }
471        let mut width = value.len();
472        while width > 1 && value[width - 1] == value[width - 2] {
473            width -= 1;
474        }
475        if width > Self::BITS as usize {
476            return Err(ConstToIntError::Overflow);
477        }
478        let mut result = 0;
479        for (index, trit) in value.iter().enumerate() {
480            if trit == Trit::One {
481                if index == width - 1 {
482                    result |= -1 << index;
483                } else {
484                    result |= 1 << index;
485                }
486            }
487        }
488        Ok(result)
489    }
490}
491
492impl<I: SliceIndex<[Trit]>> Index<I> for Const {
493    type Output = I::Output;
494
495    fn index(&self, index: I) -> &Self::Output {
496        &self.trits[index]
497    }
498}
499
500impl<I: SliceIndex<[Trit]>> IndexMut<I> for Const {
501    fn index_mut(&mut self, index: I) -> &mut Self::Output {
502        &mut self.trits[index]
503    }
504}
505
506impl Extend<Trit> for Const {
507    fn extend<T: IntoIterator<Item = Trit>>(&mut self, iter: T) {
508        for trit in iter {
509            self.trits.push(trit);
510        }
511    }
512}
513
514impl From<Trit> for Const {
515    fn from(trit: Trit) -> Self {
516        Const { trits: vec![trit] }
517    }
518}
519
520impl From<Vec<Trit>> for Const {
521    fn from(trits: Vec<Trit>) -> Self {
522        Const { trits }
523    }
524}
525
526impl From<Trit> for Cow<'_, Const> {
527    fn from(value: Trit) -> Self {
528        Cow::Owned(Const::from(value))
529    }
530}
531
532impl From<Const> for Cow<'_, Const> {
533    fn from(value: Const) -> Self {
534        Cow::Owned(value)
535    }
536}
537
538impl<'a> From<&'a Const> for Cow<'a, Const> {
539    fn from(value: &'a Const) -> Self {
540        Cow::Borrowed(value)
541    }
542}
543
544impl FromIterator<Trit> for Const {
545    fn from_iter<T: IntoIterator<Item = Trit>>(iter: T) -> Self {
546        Const { trits: iter.into_iter().collect() }
547    }
548}
549
550impl IntoIterator for &Const {
551    type Item = Trit;
552    type IntoIter = std::vec::IntoIter<Trit>;
553
554    fn into_iter(self) -> Self::IntoIter {
555        self.trits.clone().into_iter()
556    }
557}
558
559impl IntoIterator for Const {
560    type Item = Trit;
561    type IntoIter = std::vec::IntoIter<Trit>;
562
563    fn into_iter(self) -> Self::IntoIter {
564        self.trits.into_iter()
565    }
566}
567
568#[cfg(test)]
569mod test {
570    use crate::{Const, Trit};
571
572    #[test]
573    fn test_not() {
574        for (a, y) in [("", ""), ("01", "10"), ("X10", "X01")] {
575            assert_eq!(Const::lit(a).not(), Const::lit(y));
576        }
577    }
578
579    #[test]
580    fn test_and() {
581        for (a, b, y) in [("", "", ""), ("1010", "1100", "1000"), ("X0X0", "XX00", "X000"), ("X1X1", "XX11", "XXX1")] {
582            assert_eq!(Const::lit(a).and(Const::lit(b)), Const::lit(y));
583        }
584    }
585
586    #[test]
587    fn test_or() {
588        for (a, b, y) in [("", "", ""), ("1010", "1100", "1110"), ("X0X0", "XX00", "XXX0"), ("X1X1", "XX11", "X111")] {
589            assert_eq!(Const::lit(a).or(Const::lit(b)), Const::lit(y));
590        }
591    }
592
593    #[test]
594    fn test_xor() {
595        for (a, b, y) in [("", "", ""), ("1010", "1100", "0110"), ("X0X0", "XX00", "XXX0"), ("X1X1", "XX11", "XXX0")] {
596            assert_eq!(Const::lit(a).xor(Const::lit(b)), Const::lit(y));
597        }
598    }
599
600    #[test]
601    fn test_mux() {
602        for (s, a, b, y) in [
603            ('0', "", "", ""),
604            ('0', "XXX101010", "X10XX1100", "X10XX1100"),
605            ('1', "XXX101010", "X10XX1100", "XXX101010"),
606            ('X', "XXX101010", "X10XX1100", "XXXXX1XX0"),
607        ] {
608            assert_eq!(Trit::lit(s).mux(Const::lit(a), Const::lit(b)), Const::lit(y));
609        }
610    }
611
612    #[test]
613    fn test_adc() {
614        for (a, b, c, y) in [
615            ("", "", '0', "0"),
616            ("", "", '1', "1"),
617            ("10101010", "11001100", '0', "101110110"),
618            ("1101", "1111", '1', "11101"),
619            ("1010X010", "11001100", '0', "XXXXXX110"),
620        ] {
621            assert_eq!(Const::lit(a).adc(Const::lit(b), Trit::lit(c)), Const::lit(y));
622        }
623    }
624
625    #[test]
626    fn test_mul() {
627        for (a, b, y) in [("", "", ""), ("0011", "0011", "1001"), ("0X11", "0011", "XXXX"), ("1101", "1101", "1001")] {
628            assert_eq!(Const::lit(a).mul(Const::lit(b)), Const::lit(y));
629        }
630    }
631}
prjunnamed_netlist/logic.rs

prjunnamed_netlist/
logic.rs
