diff options
Diffstat (limited to 'vendor/quine-mc_cluskey')
-rw-r--r-- | vendor/quine-mc_cluskey/.cargo-checksum.json | 1 | ||||
-rw-r--r-- | vendor/quine-mc_cluskey/Cargo.toml | 11 | ||||
-rw-r--r-- | vendor/quine-mc_cluskey/README.md | 68 | ||||
-rw-r--r-- | vendor/quine-mc_cluskey/src/lib.rs | 504 |
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, + } +} |