Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

4 files changed, 584 insertions, 0 deletions

diff --git a/vendor/quine-mc_cluskey/.cargo-checksum.json b/vendor/quine-mc_cluskey/.cargo-checksum.json
new file mode 100644
index 000000000..4dc33618e
--- /dev/null
+++ b/vendor/quine-mc_cluskey/.cargo-checksum.json
@@ -0,0 +1 @@
+{"files":{"Cargo.toml":"984ce07c3f160379daaed7b10e09007c83aab14e7797537c011873e7e0f1f083","README.md":"328585acf6737abd09af8b200a1ce1dc3e1c019b8504559caa0b8ccd9d6dd7ac","src/lib.rs":"812c60fe1fc3018f88416655eaad746a8f825f9705f6d45d96c6dc8a765f6090"},"package":"07589615d719a60c8dd8a4622e7946465dfef20d1a428f969e3443e7386d5f45"}
\ No newline at end of file
diff --git a/vendor/quine-mc_cluskey/Cargo.toml b/vendor/quine-mc_cluskey/Cargo.toml
new file mode 100644
index 000000000..b01fb398c
--- /dev/null
+++ b/vendor/quine-mc_cluskey/Cargo.toml
@@ -0,0 +1,11 @@
+[package]
+name = "quine-mc_cluskey"
+version = "0.2.4"
+authors = ["Oliver Schneider <git-spam-no-reply9815368754983@oli-obk.de>"]
+description = "Rust implementation of the Quine-McCluskey algorithm and Petrick's method"
+license = "MIT"
+repository = "https://github.com/oli-obk/quine-mc_cluskey"
+documentation = "https://oli-obk.github.io/quine-mc_cluskey"
+
+[dependencies]
+quickcheck = { version = "0.3.1", optional = true }
diff --git a/vendor/quine-mc_cluskey/README.md b/vendor/quine-mc_cluskey/README.md
new file mode 100644
index 000000000..cf562665a
--- /dev/null
+++ b/vendor/quine-mc_cluskey/README.md
@@ -0,0 +1,68 @@
+[![Clippy Linting Result](https://clippy.bashy.io/github/oli-obk/quine-mc_cluskey/master/badge.svg)](https://clippy.bashy.io/github/oli-obk/quine-mc_cluskey/master/log)
+[![Current Version](http://meritbadge.herokuapp.com/quine-mc_cluskey)](https://crates.io/crates/quine-mc_cluskey)
+[![Build Status](https://travis-ci.org/oli-obk/quine-mc_cluskey.svg?branch=master)](https://travis-ci.org/oli-obk/quine-mc_cluskey)
+
+An algorithm to automatically minimize boolean expressions.
+
+# Example
+
+```rust
+extern crate quine_mc_cluskey;
+
+use quine_mc_cluskey::*;
+use quine_mc_cluskey::Bool::{And, Or, Not, True, False};
+
+fn main() {
+    // !false => true
+    assert_eq!(
+        Not(Box::new(False)).simplify(),
+        vec![True]
+    );
+
+    // a && (b || a) => a
+    assert_eq!(
+        And(vec![Bool::Term(0),
+        Or(vec![Bool::Term(1), Bool::Term(0)])]).simplify(), vec![Bool::Term(0)]
+    );
+}
+```
+
+# Obtaining a minimal "and of or" form
+
+Sometimes an expression of the form `a && (b || c)` is shorter than the `a && b || a && c` form.
+We can simply negate the original expression and negate all the resulting simplified expressions to obtain that form.
+
+```rust
+extern crate quine_mc_cluskey;
+use quine_mc_cluskey::Bool;
+
+fn main() {
+    let a: Bool = Bool::And(vec![Bool::True, Bool::True]);
+    let simplified: Vec<Bool> = Bool::Not(Box::new(a)).simplify()
+        .iter().map(simple_negate).collect();
+}
+
+fn simple_negate(b: &Bool) -> Bool {
+    use quine_mc_cluskey::Bool::*;
+    let b = b.clone();
+
+    match b {
+        True => False,
+        False => True,
+        t @ Term(_) => Not(Box::new(t)),
+        And(mut v) => {
+            for el in &mut v {
+                *el = simple_negate(el);
+            }
+            Or(v)
+        },
+        Or(mut v) => {
+            for el in &mut v {
+                *el = simple_negate(el);
+            }
+            And(v)
+        },
+        Not(inner) => *inner,
+    }
+}
+```
diff --git a/vendor/quine-mc_cluskey/src/lib.rs b/vendor/quine-mc_cluskey/src/lib.rs
new file mode 100644
index 000000000..d371d0396
--- /dev/null
+++ b/vendor/quine-mc_cluskey/src/lib.rs
@@ -0,0 +1,504 @@
+#[derive(Eq, Clone)]
+pub enum Bool {
+    True,
+    False,
+    /// can be any number in `0..32`, anything else will cause panics or wrong results
+    Term(u8),
+    /// needs to contain at least two elements
+    And(Vec<Bool>),
+    /// needs to contain at least two elements
+    Or(Vec<Bool>),
+    Not(Box<Bool>),
+}
+
+#[cfg(feature="quickcheck")]
+extern crate quickcheck;
+
+#[cfg(feature="quickcheck")]
+impl quickcheck::Arbitrary for Bool {
+    fn arbitrary<G: quickcheck::Gen>(g: &mut G) -> Self {
+        let mut terms = 0;
+        arbitrary_bool(g, 10, &mut terms)
+    }
+    fn shrink(&self) -> Box<Iterator<Item=Self>> {
+        match *self {
+            Bool::And(ref v) => Box::new(v.shrink().filter(|v| v.len() > 2).map(Bool::And)),
+            Bool::Or(ref v) => Box::new(v.shrink().filter(|v| v.len() > 2).map(Bool::Or)),
+            Bool::Not(ref inner) => Box::new(inner.shrink().map(|b| Bool::Not(Box::new(b)))),
+            _ => quickcheck::empty_shrinker(),
+        }
+    }
+}
+
+#[cfg(feature="quickcheck")]
+fn arbitrary_bool<G: quickcheck::Gen>(g: &mut G, depth: usize, terms: &mut u8) -> Bool {
+    if depth == 0 {
+        match g.gen_range(0, 3) {
+            0 => Bool::True,
+            1 => Bool::False,
+            2 => arbitrary_term(g, terms),
+            _ => unreachable!(),
+        }
+    } else {
+        match g.gen_range(0, 6) {
+            0 => Bool::True,
+            1 => Bool::False,
+            2 => arbitrary_term(g, terms),
+            3 => Bool::And(arbitrary_vec(g, depth - 1, terms)),
+            4 => Bool::Or(arbitrary_vec(g, depth - 1, terms)),
+            5 => Bool::Not(Box::new(arbitrary_bool(g, depth - 1, terms))),
+            _ => unreachable!(),
+        }
+    }
+}
+
+#[cfg(feature="quickcheck")]
+fn arbitrary_term<G: quickcheck::Gen>(g: &mut G, terms: &mut u8) -> Bool {
+    if *terms == 0 {
+        Bool::Term(*terms)
+    } else if *terms < 32 && g.gen_weighted_bool(3) {
+        *terms += 1;
+        // every term needs to show up at least once
+        Bool::Term(*terms - 1)
+    } else {
+        Bool::Term(g.gen_range(0, *terms))
+    }
+}
+
+#[cfg(feature="quickcheck")]
+fn arbitrary_vec<G: quickcheck::Gen>(g: &mut G, depth: usize, terms: &mut u8) -> Vec<Bool> {
+    (0..g.gen_range(2, 20)).map(|_| arbitrary_bool(g, depth, terms)).collect()
+}
+
+impl PartialEq for Bool {
+    fn eq(&self, other: &Self) -> bool {
+        use self::Bool::*;
+        match (self, other) {
+            (&True, &True) |
+            (&False, &False) => true,
+            (&Term(a), &Term(b)) => a == b,
+            (&Not(ref a), &Not(ref b)) => a == b,
+            (&And(ref a), &And(ref b)) |
+            (&Or(ref a), &Or(ref b)) => {
+                if a.len() != b.len() {
+                    return false;
+                }
+                for a in a {
+                    if !b.iter().any(|b| b == a) {
+                        return false;
+                    }
+                }
+                true
+            },
+            _ => false,
+        }
+    }
+}
+
+impl std::ops::Not for Bool {
+    type Output = Bool;
+    fn not(self) -> Bool {
+        use self::Bool::*;
+        match self {
+            True => False,
+            False => True,
+            t @ Term(_) => Not(Box::new(t)),
+            And(mut v) => {
+                for el in &mut v {
+                    *el = !std::mem::replace(el, False);
+                }
+                Or(v)
+            },
+            Or(mut v) => {
+                for el in &mut v {
+                    *el = !std::mem::replace(el, False);
+                }
+                And(v)
+            },
+            Not(inner) => *inner,
+        }
+    }
+}
+
+impl std::ops::BitAnd for Bool {
+    type Output = Self;
+    fn bitand(self, rhs: Bool) -> Bool {
+        use self::Bool::*;
+        match (self, rhs) {
+            (And(mut v), And(rhs)) => {
+                v.extend(rhs);
+                And(v)
+            },
+            (False, _) |
+            (_, False) => False,
+            (b, True) |
+            (True, b) => b,
+            (other, And(mut v)) |
+            (And(mut v), other) => {
+                v.push(other);
+                And(v)
+            },
+            (a, b) => And(vec![a, b]),
+        }
+    }
+}
+
+impl std::ops::BitOr for Bool {
+    type Output = Self;
+    fn bitor(self, rhs: Bool) -> Bool {
+        use self::Bool::*;
+        match (self, rhs) {
+            (Or(mut v), Or(rhs)) => {
+                v.extend(rhs);
+                Or(v)
+            },
+            (False, b) |
+            (b, False) => b,
+            (_, True) |
+            (True, _) => True,
+            (other, Or(mut v)) |
+            (Or(mut v), other) => {
+                v.push(other);
+                Or(v)
+            },
+            (a, b) => Or(vec![a, b]),
+        }
+    }
+}
+
+impl Bool {
+    pub fn terms(&self) -> u32 {
+        use self::Bool::*;
+        match *self {
+            Term(u) => 1 << u,
+            Or(ref a) |
+            And(ref a) => a.iter().fold(0, |state, item| { state | item.terms() }),
+            Not(ref a) => a.terms(),
+            True | False => 0,
+        }
+    }
+
+    pub fn eval(&self, terms: u32) -> bool {
+        use self::Bool::*;
+        match *self {
+            True => true,
+            False => false,
+            Term(i) => (terms & (1 << i)) != 0,
+            And(ref a) => a.iter().all(|item| item.eval(terms)),
+            Or(ref a) => a.iter().any(|item| item.eval(terms)),
+            Not(ref a) => !a.eval(terms),
+        }
+    }
+
+    pub fn minterms(&self) -> Vec<Term> {
+        let terms = self.terms();
+        let number_of_terms = terms.count_ones();
+        assert!((0..number_of_terms).all(|i| (terms & (1 << i)) != 0), "non-continuous naming scheme");
+        (0..(1 << number_of_terms)).filter(|&i| self.eval(i)).map(Term::new).collect()
+    }
+
+    pub fn simplify(&self) -> Vec<Bool> {
+        let minterms = self.minterms();
+        if minterms.is_empty() {
+            return vec![Bool::False];
+        }
+        let variables = self.terms().count_ones();
+        if variables == 0 {
+            return vec![Bool::True];
+        }
+        let essentials = essential_minterms(minterms);
+        let expr = essentials.prime_implicant_expr();
+        let simple = simplify_prime_implicant_expr(expr);
+        let shortest = simple.iter().map(Vec::len).min().unwrap();
+        simple.into_iter()
+              .filter(|v| v.len() == shortest)
+              .map(|v| {
+                  let mut v = v.into_iter()
+                               .map(|i| essentials.essentials[i as usize]
+                                                  .to_bool_expr(variables));
+                  if v.len() == 1 {
+                      v.next().unwrap()
+                  } else {
+                      Bool::Or(v.collect())
+                  }
+              }).collect()
+    }
+}
+
+impl std::fmt::Debug for Bool {
+    fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result {
+        use self::Bool::*;
+        match *self {
+            True => write!(fmt, "T"),
+            False => write!(fmt, "F"),
+            Term(i) if i > 32 => write!(fmt, "<bad term id {}>", i),
+            Term(i) => write!(fmt, "{}", "abcdefghijklmnopqrstuvwxyzαβγδεζη".chars().nth(i as usize).unwrap()),
+            Not(ref a) => match **a {
+                And(_) | Or(_) => write!(fmt, "({:?})'", a),
+                _ => write!(fmt, "{:?}'", a),
+            },
+            And(ref a) => {
+                for a in a {
+                    match *a {
+                        And(_) | Or(_) => try!(write!(fmt, "({:?})", a)),
+                        _ => try!(write!(fmt, "{:?}", a)),
+                    }
+                }
+                Ok(())
+            },
+            Or(ref a) => {
+                try!(write!(fmt, "{:?}", a[0]));
+                for a in &a[1..] {
+                    match *a {
+                        Or(_) => try!(write!(fmt, " + ({:?})", a)),
+                        _ => try!(write!(fmt, " + {:?}", a)),
+                    }
+                }
+                Ok(())
+            }
+        }
+    }
+}
+
+#[derive(Debug)]
+pub struct Essentials {
+    pub minterms: Vec<Term>,
+    pub essentials: Vec<Term>,
+}
+
+pub fn simplify_prime_implicant_expr(mut e: Vec<Vec<Vec<u32>>>) -> Vec<Vec<u32>> {
+    loop {
+        let a = e.pop().unwrap();
+        if let Some(b) = e.pop() {
+            let distributed = distribute(&a, &b);
+            let simplified = simplify(distributed);
+            e.push(simplified);
+        } else {
+            return a;
+        }
+    }
+}
+
+// AA     -> A
+// A + AB -> A
+// A + A  -> A
+fn simplify(mut e: Vec<Vec<u32>>) -> Vec<Vec<u32>> {
+    for e in &mut e {
+        e.sort();
+        e.dedup();
+    }
+    e.sort();
+    e.dedup();
+    let mut del = Vec::new();
+    for (i, a) in e.iter().enumerate() {
+        for (j, b) in e[i..].iter().enumerate() {
+            if a.len() < b.len() {
+                // A + AB -> delete AB
+                if a.iter().all(|x| b.iter().any(|y| y == x)) {
+                    del.push(j + i);
+                }
+            } else if b.len() < a.len() && b.iter().all(|x| a.iter().any(|y| y == x)) {
+                // AB + A -> delete AB
+                del.push(i);
+            }
+        }
+    }
+    del.sort();
+    del.dedup();
+    for del in del.into_iter().rev() {
+        e.swap_remove(del);
+    }
+    e
+}
+
+// (AB + CD)(EF + GH) -> ABEF + ABGH + CDEF + CDGH
+fn distribute(l: &[Vec<u32>], r: &[Vec<u32>]) -> Vec<Vec<u32>> {
+    let mut ret = Vec::new();
+    assert!(!l.is_empty());
+    assert!(!r.is_empty());
+    for l in l {
+        for r in r {
+            ret.push(l.iter().chain(r).cloned().collect());
+        }
+    }
+    ret
+}
+
+
+impl Essentials {
+    pub fn prime_implicant_expr(&self) -> Vec<Vec<Vec<u32>>> {
+        let mut v = Vec::new();
+        for t in &self.minterms {
+            let mut w = Vec::new();
+            for (i, e) in self.essentials.iter().enumerate() {
+                if e.contains(t) {
+                    assert_eq!(i as u32 as usize, i);
+                    w.push(vec![i as u32]);
+                }
+            }
+            v.push(w);
+        }
+        v
+    }
+}
+
+#[derive(Clone, Eq, Ord)]
+pub struct Term {
+    dontcare: u32,
+    term: u32,
+}
+
+#[cfg(feature="quickcheck")]
+impl quickcheck::Arbitrary for Term {
+    fn arbitrary<G: quickcheck::Gen>(g: &mut G) -> Self {
+        Term {
+            dontcare: u32::arbitrary(g),
+            term: u32::arbitrary(g),
+        }
+    }
+}
+
+impl std::cmp::PartialOrd for Term {
+    fn partial_cmp(&self, rhs: &Self) -> Option<std::cmp::Ordering> {
+        use std::cmp::Ordering::*;
+        match self.dontcare.partial_cmp(&rhs.dontcare) {
+            Some(Equal) => {},
+            other => return other,
+        }
+        let l = self.term & !self.dontcare;
+        let r = rhs.term & !rhs.dontcare;
+        l.partial_cmp(&r)
+    }
+}
+
+impl std::fmt::Debug for Term {
+    fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result {
+        for i in (0..32).rev() {
+            if (self.dontcare & (1 << i)) == 0 {
+                if (self.term & (1 << i)) == 0 {
+                    try!(write!(fmt, "0"));
+                } else {
+                    try!(write!(fmt, "1"));
+                }
+            } else {
+                try!(write!(fmt, "-"));
+            }
+        }
+        Ok(())
+    }
+}
+
+impl std::cmp::PartialEq for Term {
+    fn eq(&self, other: &Self) -> bool {
+        (self.dontcare == other.dontcare) && ((self.term & !self.dontcare) == (other.term & !other.dontcare))
+    }
+}
+
+#[derive(Debug, Eq, PartialEq)]
+pub enum TermFromStrError {
+    Only32TermsSupported,
+    UnsupportedCharacter(char),
+}
+
+impl std::str::FromStr for Term {
+    type Err = TermFromStrError;
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        if s.len() > 32 {
+            return Err(TermFromStrError::Only32TermsSupported);
+        }
+        let mut term = Term::new(0);
+        for (i, c) in s.chars().rev().enumerate() {
+            match c {
+                '-' => term.dontcare |= 1 << i,
+                '1' => term.term |= 1 << i,
+                '0' => {},
+                c => return Err(TermFromStrError::UnsupportedCharacter(c)),
+            }
+        }
+        Ok(term)
+    }
+}
+
+impl Term {
+    pub fn new(i: u32) -> Self {
+        Term {
+            dontcare: 0,
+            term: i,
+        }
+    }
+
+    pub fn with_dontcare(term: u32, dontcare: u32) -> Self {
+        Term {
+            dontcare: dontcare,
+            term: term,
+        }
+    }
+
+    pub fn combine(&self, other: &Term) -> Option<Term> {
+        let dc = self.dontcare ^ other.dontcare;
+        let term = self.term ^ other.term;
+        let dc_mask = self.dontcare | other.dontcare;
+        match (dc.count_ones(), (!dc_mask & term).count_ones()) {
+            (0, 1) |
+            (1, 0) => Some(Term {
+                dontcare: dc_mask | term,
+                term: self.term,
+            }),
+            _ => None,
+        }
+    }
+
+    pub fn contains(&self, other: &Self) -> bool {
+        ((self.dontcare | other.dontcare) == self.dontcare) &&
+        (((self.term ^ other.term) & !self.dontcare) == 0)
+    }
+
+    pub fn to_bool_expr(&self, n_variables: u32) -> Bool {
+        assert!(self.dontcare < (1 << n_variables));
+        assert!(self.term < (1 << n_variables));
+        let mut v = Vec::new();
+        for bit in 0..n_variables {
+            if (self.dontcare & (1 << bit)) == 0 {
+                if (self.term & (1 << bit)) == 0 {
+                    v.push(Bool::Not(Box::new(Bool::Term(bit as u8))))
+                } else {
+                    v.push(Bool::Term(bit as u8))
+                }
+            }
+        }
+        match v.len() {
+            0 => Bool::True,
+            1 => v.into_iter().next().unwrap(),
+            _ => Bool::And(v),
+        }
+    }
+}
+
+pub fn essential_minterms(mut minterms: Vec<Term>) -> Essentials {
+    minterms.sort();
+    let minterms = minterms;
+    let mut terms = minterms.clone();
+    let mut essentials: Vec<Term> = Vec::new();
+    while !terms.is_empty() {
+        let old = std::mem::replace(&mut terms, Vec::new());
+        let mut combined_terms = std::collections::BTreeSet::new();
+        for (i, term) in old.iter().enumerate() {
+            for (other_i, other) in old[i..].iter().enumerate() {
+                if let Some(new_term) = term.combine(other) {
+                    terms.push(new_term);
+                    combined_terms.insert(other_i + i);
+                    combined_terms.insert(i);
+                }
+            }
+            if !combined_terms.contains(&i) {
+                essentials.push(term.clone());
+            }
+        }
+        terms.sort();
+        terms.dedup();
+    }
+    Essentials {
+        minterms: minterms,
+        essentials: essentials,
+    }
+}