]>
Commit | Line | Data |
---|---|---|
f20569fa XL |
1 | #[derive(Eq, Clone)] |
2 | pub enum Bool { | |
3 | True, | |
4 | False, | |
5 | /// can be any number in `0..32`, anything else will cause panics or wrong results | |
6 | Term(u8), | |
7 | /// needs to contain at least two elements | |
8 | And(Vec<Bool>), | |
9 | /// needs to contain at least two elements | |
10 | Or(Vec<Bool>), | |
11 | Not(Box<Bool>), | |
12 | } | |
13 | ||
14 | #[cfg(feature="quickcheck")] | |
15 | extern crate quickcheck; | |
16 | ||
17 | #[cfg(feature="quickcheck")] | |
18 | impl quickcheck::Arbitrary for Bool { | |
19 | fn arbitrary<G: quickcheck::Gen>(g: &mut G) -> Self { | |
20 | let mut terms = 0; | |
21 | arbitrary_bool(g, 10, &mut terms) | |
22 | } | |
23 | fn shrink(&self) -> Box<Iterator<Item=Self>> { | |
24 | match *self { | |
25 | Bool::And(ref v) => Box::new(v.shrink().filter(|v| v.len() > 2).map(Bool::And)), | |
26 | Bool::Or(ref v) => Box::new(v.shrink().filter(|v| v.len() > 2).map(Bool::Or)), | |
27 | Bool::Not(ref inner) => Box::new(inner.shrink().map(|b| Bool::Not(Box::new(b)))), | |
28 | _ => quickcheck::empty_shrinker(), | |
29 | } | |
30 | } | |
31 | } | |
32 | ||
33 | #[cfg(feature="quickcheck")] | |
34 | fn arbitrary_bool<G: quickcheck::Gen>(g: &mut G, depth: usize, terms: &mut u8) -> Bool { | |
35 | if depth == 0 { | |
36 | match g.gen_range(0, 3) { | |
37 | 0 => Bool::True, | |
38 | 1 => Bool::False, | |
39 | 2 => arbitrary_term(g, terms), | |
40 | _ => unreachable!(), | |
41 | } | |
42 | } else { | |
43 | match g.gen_range(0, 6) { | |
44 | 0 => Bool::True, | |
45 | 1 => Bool::False, | |
46 | 2 => arbitrary_term(g, terms), | |
47 | 3 => Bool::And(arbitrary_vec(g, depth - 1, terms)), | |
48 | 4 => Bool::Or(arbitrary_vec(g, depth - 1, terms)), | |
49 | 5 => Bool::Not(Box::new(arbitrary_bool(g, depth - 1, terms))), | |
50 | _ => unreachable!(), | |
51 | } | |
52 | } | |
53 | } | |
54 | ||
55 | #[cfg(feature="quickcheck")] | |
56 | fn arbitrary_term<G: quickcheck::Gen>(g: &mut G, terms: &mut u8) -> Bool { | |
57 | if *terms == 0 { | |
58 | Bool::Term(*terms) | |
59 | } else if *terms < 32 && g.gen_weighted_bool(3) { | |
60 | *terms += 1; | |
61 | // every term needs to show up at least once | |
62 | Bool::Term(*terms - 1) | |
63 | } else { | |
64 | Bool::Term(g.gen_range(0, *terms)) | |
65 | } | |
66 | } | |
67 | ||
68 | #[cfg(feature="quickcheck")] | |
69 | fn arbitrary_vec<G: quickcheck::Gen>(g: &mut G, depth: usize, terms: &mut u8) -> Vec<Bool> { | |
70 | (0..g.gen_range(2, 20)).map(|_| arbitrary_bool(g, depth, terms)).collect() | |
71 | } | |
72 | ||
73 | impl PartialEq for Bool { | |
74 | fn eq(&self, other: &Self) -> bool { | |
75 | use self::Bool::*; | |
76 | match (self, other) { | |
77 | (&True, &True) | | |
78 | (&False, &False) => true, | |
79 | (&Term(a), &Term(b)) => a == b, | |
80 | (&Not(ref a), &Not(ref b)) => a == b, | |
81 | (&And(ref a), &And(ref b)) | | |
82 | (&Or(ref a), &Or(ref b)) => { | |
83 | if a.len() != b.len() { | |
84 | return false; | |
85 | } | |
86 | for a in a { | |
87 | if !b.iter().any(|b| b == a) { | |
88 | return false; | |
89 | } | |
90 | } | |
91 | true | |
92 | }, | |
93 | _ => false, | |
94 | } | |
95 | } | |
96 | } | |
97 | ||
98 | impl std::ops::Not for Bool { | |
99 | type Output = Bool; | |
100 | fn not(self) -> Bool { | |
101 | use self::Bool::*; | |
102 | match self { | |
103 | True => False, | |
104 | False => True, | |
105 | t @ Term(_) => Not(Box::new(t)), | |
106 | And(mut v) => { | |
107 | for el in &mut v { | |
108 | *el = !std::mem::replace(el, False); | |
109 | } | |
110 | Or(v) | |
111 | }, | |
112 | Or(mut v) => { | |
113 | for el in &mut v { | |
114 | *el = !std::mem::replace(el, False); | |
115 | } | |
116 | And(v) | |
117 | }, | |
118 | Not(inner) => *inner, | |
119 | } | |
120 | } | |
121 | } | |
122 | ||
123 | impl std::ops::BitAnd for Bool { | |
124 | type Output = Self; | |
125 | fn bitand(self, rhs: Bool) -> Bool { | |
126 | use self::Bool::*; | |
127 | match (self, rhs) { | |
128 | (And(mut v), And(rhs)) => { | |
129 | v.extend(rhs); | |
130 | And(v) | |
131 | }, | |
132 | (False, _) | | |
133 | (_, False) => False, | |
134 | (b, True) | | |
135 | (True, b) => b, | |
136 | (other, And(mut v)) | | |
137 | (And(mut v), other) => { | |
138 | v.push(other); | |
139 | And(v) | |
140 | }, | |
141 | (a, b) => And(vec![a, b]), | |
142 | } | |
143 | } | |
144 | } | |
145 | ||
146 | impl std::ops::BitOr for Bool { | |
147 | type Output = Self; | |
148 | fn bitor(self, rhs: Bool) -> Bool { | |
149 | use self::Bool::*; | |
150 | match (self, rhs) { | |
151 | (Or(mut v), Or(rhs)) => { | |
152 | v.extend(rhs); | |
153 | Or(v) | |
154 | }, | |
155 | (False, b) | | |
156 | (b, False) => b, | |
157 | (_, True) | | |
158 | (True, _) => True, | |
159 | (other, Or(mut v)) | | |
160 | (Or(mut v), other) => { | |
161 | v.push(other); | |
162 | Or(v) | |
163 | }, | |
164 | (a, b) => Or(vec![a, b]), | |
165 | } | |
166 | } | |
167 | } | |
168 | ||
169 | impl Bool { | |
170 | pub fn terms(&self) -> u32 { | |
171 | use self::Bool::*; | |
172 | match *self { | |
173 | Term(u) => 1 << u, | |
174 | Or(ref a) | | |
175 | And(ref a) => a.iter().fold(0, |state, item| { state | item.terms() }), | |
176 | Not(ref a) => a.terms(), | |
177 | True | False => 0, | |
178 | } | |
179 | } | |
180 | ||
181 | pub fn eval(&self, terms: u32) -> bool { | |
182 | use self::Bool::*; | |
183 | match *self { | |
184 | True => true, | |
185 | False => false, | |
186 | Term(i) => (terms & (1 << i)) != 0, | |
187 | And(ref a) => a.iter().all(|item| item.eval(terms)), | |
188 | Or(ref a) => a.iter().any(|item| item.eval(terms)), | |
189 | Not(ref a) => !a.eval(terms), | |
190 | } | |
191 | } | |
192 | ||
193 | pub fn minterms(&self) -> Vec<Term> { | |
194 | let terms = self.terms(); | |
195 | let number_of_terms = terms.count_ones(); | |
196 | assert!((0..number_of_terms).all(|i| (terms & (1 << i)) != 0), "non-continuous naming scheme"); | |
197 | (0..(1 << number_of_terms)).filter(|&i| self.eval(i)).map(Term::new).collect() | |
198 | } | |
199 | ||
200 | pub fn simplify(&self) -> Vec<Bool> { | |
201 | let minterms = self.minterms(); | |
202 | if minterms.is_empty() { | |
203 | return vec![Bool::False]; | |
204 | } | |
205 | let variables = self.terms().count_ones(); | |
206 | if variables == 0 { | |
207 | return vec![Bool::True]; | |
208 | } | |
209 | let essentials = essential_minterms(minterms); | |
210 | let expr = essentials.prime_implicant_expr(); | |
211 | let simple = simplify_prime_implicant_expr(expr); | |
212 | let shortest = simple.iter().map(Vec::len).min().unwrap(); | |
213 | simple.into_iter() | |
214 | .filter(|v| v.len() == shortest) | |
215 | .map(|v| { | |
216 | let mut v = v.into_iter() | |
217 | .map(|i| essentials.essentials[i as usize] | |
218 | .to_bool_expr(variables)); | |
219 | if v.len() == 1 { | |
220 | v.next().unwrap() | |
221 | } else { | |
222 | Bool::Or(v.collect()) | |
223 | } | |
224 | }).collect() | |
225 | } | |
226 | } | |
227 | ||
228 | impl std::fmt::Debug for Bool { | |
229 | fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result { | |
230 | use self::Bool::*; | |
231 | match *self { | |
232 | True => write!(fmt, "T"), | |
233 | False => write!(fmt, "F"), | |
234 | Term(i) if i > 32 => write!(fmt, "<bad term id {}>", i), | |
235 | Term(i) => write!(fmt, "{}", "abcdefghijklmnopqrstuvwxyzαβγδεζη".chars().nth(i as usize).unwrap()), | |
236 | Not(ref a) => match **a { | |
237 | And(_) | Or(_) => write!(fmt, "({:?})'", a), | |
238 | _ => write!(fmt, "{:?}'", a), | |
239 | }, | |
240 | And(ref a) => { | |
241 | for a in a { | |
242 | match *a { | |
243 | And(_) | Or(_) => try!(write!(fmt, "({:?})", a)), | |
244 | _ => try!(write!(fmt, "{:?}", a)), | |
245 | } | |
246 | } | |
247 | Ok(()) | |
248 | }, | |
249 | Or(ref a) => { | |
250 | try!(write!(fmt, "{:?}", a[0])); | |
251 | for a in &a[1..] { | |
252 | match *a { | |
253 | Or(_) => try!(write!(fmt, " + ({:?})", a)), | |
254 | _ => try!(write!(fmt, " + {:?}", a)), | |
255 | } | |
256 | } | |
257 | Ok(()) | |
258 | } | |
259 | } | |
260 | } | |
261 | } | |
262 | ||
263 | #[derive(Debug)] | |
264 | pub struct Essentials { | |
265 | pub minterms: Vec<Term>, | |
266 | pub essentials: Vec<Term>, | |
267 | } | |
268 | ||
269 | pub fn simplify_prime_implicant_expr(mut e: Vec<Vec<Vec<u32>>>) -> Vec<Vec<u32>> { | |
270 | loop { | |
271 | let a = e.pop().unwrap(); | |
272 | if let Some(b) = e.pop() { | |
273 | let distributed = distribute(&a, &b); | |
274 | let simplified = simplify(distributed); | |
275 | e.push(simplified); | |
276 | } else { | |
277 | return a; | |
278 | } | |
279 | } | |
280 | } | |
281 | ||
282 | // AA -> A | |
283 | // A + AB -> A | |
284 | // A + A -> A | |
285 | fn simplify(mut e: Vec<Vec<u32>>) -> Vec<Vec<u32>> { | |
286 | for e in &mut e { | |
287 | e.sort(); | |
288 | e.dedup(); | |
289 | } | |
290 | e.sort(); | |
291 | e.dedup(); | |
292 | let mut del = Vec::new(); | |
293 | for (i, a) in e.iter().enumerate() { | |
294 | for (j, b) in e[i..].iter().enumerate() { | |
295 | if a.len() < b.len() { | |
296 | // A + AB -> delete AB | |
297 | if a.iter().all(|x| b.iter().any(|y| y == x)) { | |
298 | del.push(j + i); | |
299 | } | |
300 | } else if b.len() < a.len() && b.iter().all(|x| a.iter().any(|y| y == x)) { | |
301 | // AB + A -> delete AB | |
302 | del.push(i); | |
303 | } | |
304 | } | |
305 | } | |
306 | del.sort(); | |
307 | del.dedup(); | |
308 | for del in del.into_iter().rev() { | |
309 | e.swap_remove(del); | |
310 | } | |
311 | e | |
312 | } | |
313 | ||
314 | // (AB + CD)(EF + GH) -> ABEF + ABGH + CDEF + CDGH | |
315 | fn distribute(l: &[Vec<u32>], r: &[Vec<u32>]) -> Vec<Vec<u32>> { | |
316 | let mut ret = Vec::new(); | |
317 | assert!(!l.is_empty()); | |
318 | assert!(!r.is_empty()); | |
319 | for l in l { | |
320 | for r in r { | |
321 | ret.push(l.iter().chain(r).cloned().collect()); | |
322 | } | |
323 | } | |
324 | ret | |
325 | } | |
326 | ||
327 | ||
328 | impl Essentials { | |
329 | pub fn prime_implicant_expr(&self) -> Vec<Vec<Vec<u32>>> { | |
330 | let mut v = Vec::new(); | |
331 | for t in &self.minterms { | |
332 | let mut w = Vec::new(); | |
333 | for (i, e) in self.essentials.iter().enumerate() { | |
334 | if e.contains(t) { | |
335 | assert_eq!(i as u32 as usize, i); | |
336 | w.push(vec![i as u32]); | |
337 | } | |
338 | } | |
339 | v.push(w); | |
340 | } | |
341 | v | |
342 | } | |
343 | } | |
344 | ||
345 | #[derive(Clone, Eq, Ord)] | |
346 | pub struct Term { | |
347 | dontcare: u32, | |
348 | term: u32, | |
349 | } | |
350 | ||
351 | #[cfg(feature="quickcheck")] | |
352 | impl quickcheck::Arbitrary for Term { | |
353 | fn arbitrary<G: quickcheck::Gen>(g: &mut G) -> Self { | |
354 | Term { | |
355 | dontcare: u32::arbitrary(g), | |
356 | term: u32::arbitrary(g), | |
357 | } | |
358 | } | |
359 | } | |
360 | ||
361 | impl std::cmp::PartialOrd for Term { | |
362 | fn partial_cmp(&self, rhs: &Self) -> Option<std::cmp::Ordering> { | |
363 | use std::cmp::Ordering::*; | |
364 | match self.dontcare.partial_cmp(&rhs.dontcare) { | |
365 | Some(Equal) => {}, | |
366 | other => return other, | |
367 | } | |
368 | let l = self.term & !self.dontcare; | |
369 | let r = rhs.term & !rhs.dontcare; | |
370 | l.partial_cmp(&r) | |
371 | } | |
372 | } | |
373 | ||
374 | impl std::fmt::Debug for Term { | |
375 | fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result { | |
376 | for i in (0..32).rev() { | |
377 | if (self.dontcare & (1 << i)) == 0 { | |
378 | if (self.term & (1 << i)) == 0 { | |
379 | try!(write!(fmt, "0")); | |
380 | } else { | |
381 | try!(write!(fmt, "1")); | |
382 | } | |
383 | } else { | |
384 | try!(write!(fmt, "-")); | |
385 | } | |
386 | } | |
387 | Ok(()) | |
388 | } | |
389 | } | |
390 | ||
391 | impl std::cmp::PartialEq for Term { | |
392 | fn eq(&self, other: &Self) -> bool { | |
393 | (self.dontcare == other.dontcare) && ((self.term & !self.dontcare) == (other.term & !other.dontcare)) | |
394 | } | |
395 | } | |
396 | ||
397 | #[derive(Debug, Eq, PartialEq)] | |
398 | pub enum TermFromStrError { | |
399 | Only32TermsSupported, | |
400 | UnsupportedCharacter(char), | |
401 | } | |
402 | ||
403 | impl std::str::FromStr for Term { | |
404 | type Err = TermFromStrError; | |
405 | fn from_str(s: &str) -> Result<Self, Self::Err> { | |
406 | if s.len() > 32 { | |
407 | return Err(TermFromStrError::Only32TermsSupported); | |
408 | } | |
409 | let mut term = Term::new(0); | |
410 | for (i, c) in s.chars().rev().enumerate() { | |
411 | match c { | |
412 | '-' => term.dontcare |= 1 << i, | |
413 | '1' => term.term |= 1 << i, | |
414 | '0' => {}, | |
415 | c => return Err(TermFromStrError::UnsupportedCharacter(c)), | |
416 | } | |
417 | } | |
418 | Ok(term) | |
419 | } | |
420 | } | |
421 | ||
422 | impl Term { | |
423 | pub fn new(i: u32) -> Self { | |
424 | Term { | |
425 | dontcare: 0, | |
426 | term: i, | |
427 | } | |
428 | } | |
429 | ||
430 | pub fn with_dontcare(term: u32, dontcare: u32) -> Self { | |
431 | Term { | |
432 | dontcare: dontcare, | |
433 | term: term, | |
434 | } | |
435 | } | |
436 | ||
437 | pub fn combine(&self, other: &Term) -> Option<Term> { | |
438 | let dc = self.dontcare ^ other.dontcare; | |
439 | let term = self.term ^ other.term; | |
440 | let dc_mask = self.dontcare | other.dontcare; | |
441 | match (dc.count_ones(), (!dc_mask & term).count_ones()) { | |
442 | (0, 1) | | |
443 | (1, 0) => Some(Term { | |
444 | dontcare: dc_mask | term, | |
445 | term: self.term, | |
446 | }), | |
447 | _ => None, | |
448 | } | |
449 | } | |
450 | ||
451 | pub fn contains(&self, other: &Self) -> bool { | |
452 | ((self.dontcare | other.dontcare) == self.dontcare) && | |
453 | (((self.term ^ other.term) & !self.dontcare) == 0) | |
454 | } | |
455 | ||
456 | pub fn to_bool_expr(&self, n_variables: u32) -> Bool { | |
457 | assert!(self.dontcare < (1 << n_variables)); | |
458 | assert!(self.term < (1 << n_variables)); | |
459 | let mut v = Vec::new(); | |
460 | for bit in 0..n_variables { | |
461 | if (self.dontcare & (1 << bit)) == 0 { | |
462 | if (self.term & (1 << bit)) == 0 { | |
463 | v.push(Bool::Not(Box::new(Bool::Term(bit as u8)))) | |
464 | } else { | |
465 | v.push(Bool::Term(bit as u8)) | |
466 | } | |
467 | } | |
468 | } | |
469 | match v.len() { | |
470 | 0 => Bool::True, | |
471 | 1 => v.into_iter().next().unwrap(), | |
472 | _ => Bool::And(v), | |
473 | } | |
474 | } | |
475 | } | |
476 | ||
477 | pub fn essential_minterms(mut minterms: Vec<Term>) -> Essentials { | |
478 | minterms.sort(); | |
479 | let minterms = minterms; | |
480 | let mut terms = minterms.clone(); | |
481 | let mut essentials: Vec<Term> = Vec::new(); | |
482 | while !terms.is_empty() { | |
483 | let old = std::mem::replace(&mut terms, Vec::new()); | |
484 | let mut combined_terms = std::collections::BTreeSet::new(); | |
485 | for (i, term) in old.iter().enumerate() { | |
486 | for (other_i, other) in old[i..].iter().enumerate() { | |
487 | if let Some(new_term) = term.combine(other) { | |
488 | terms.push(new_term); | |
489 | combined_terms.insert(other_i + i); | |
490 | combined_terms.insert(i); | |
491 | } | |
492 | } | |
493 | if !combined_terms.contains(&i) { | |
494 | essentials.push(term.clone()); | |
495 | } | |
496 | } | |
497 | terms.sort(); | |
498 | terms.dedup(); | |
499 | } | |
500 | Essentials { | |
501 | minterms: minterms, | |
502 | essentials: essentials, | |
503 | } | |
504 | } |