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

prjunnamed_netlist/
logic.rs
