| /* |
| module: essen.c |
| purpose: Find essential primes in a multiple-valued function |
| */ |
| |
| #include "espresso.h" |
| |
| /* |
| essential -- return a cover consisting of the cubes of F which are |
| essential prime implicants (with respect to F u D); Further, remove |
| these cubes from the ON-set F, and add them to the OFF-set D. |
| |
| Sometimes EXPAND can determine that a cube is not an essential prime. |
| If so, it will set the "NONESSEN" flag in the cube. |
| |
| We count on IRREDUNDANT to have set the flag RELESSEN to indicate |
| that a prime was relatively essential (i.e., covers some minterm |
| not contained in any other prime in the current cover), or to have |
| reset the flag to indicate that a prime was relatively redundant |
| (i.e., all minterms covered by other primes in the current cover). |
| Of course, after executing irredundant, all of the primes in the |
| cover are relatively essential, but we can mark the primes which |
| were redundant at the start of irredundant and avoid an extra check |
| on these primes for essentiality. |
| */ |
| |
| pcover essential(Fp, Dp) |
| IN pcover *Fp, *Dp; |
| { |
| register pcube last, p; |
| pcover E, F = *Fp, D = *Dp; |
| |
| /* set all cubes in F active */ |
| (void) sf_active(F); |
| |
| /* Might as well start out with some cubes in E */ |
| E = new_cover(10); |
| |
| foreach_set(F, last, p) { |
| /* don't test a prime which EXPAND says is nonessential */ |
| if (! TESTP(p, NONESSEN)) { |
| /* only test a prime which was relatively essential */ |
| if (TESTP(p, RELESSEN)) { |
| /* Check essentiality */ |
| if (essen_cube(F, D, p)) { |
| if (debug & ESSEN) |
| printf("ESSENTIAL: %s\n", pc1(p)); |
| E = sf_addset(E, p); |
| RESET(p, ACTIVE); |
| F->active_count--; |
| } |
| } |
| } |
| } |
| |
| *Fp = sf_inactive(F); /* delete the inactive cubes from F */ |
| *Dp = sf_join(D, E); /* add the essentials to D */ |
| sf_free(D); |
| return E; |
| } |
| |
| /* |
| essen_cube -- check if a single cube is essential or not |
| |
| The prime c is essential iff |
| |
| consensus((F u D) # c, c) u D |
| |
| does not contain c. |
| */ |
| bool essen_cube(F, D, c) |
| IN pcover F, D; |
| IN pcube c; |
| { |
| pcover H, FD; |
| pcube *H1; |
| bool essen; |
| |
| /* Append F and D together, and take the sharp-consensus with c */ |
| FD = sf_join(F, D); |
| H = cb_consensus(FD, c); |
| free_cover(FD); |
| |
| /* Add the don't care set, and see if this covers c */ |
| H1 = cube2list(H, D); |
| essen = ! cube_is_covered(H1, c); |
| free_cubelist(H1); |
| |
| free_cover(H); |
| return essen; |
| } |
| |
| |
| /* |
| * cb_consensus -- compute consensus(T # c, c) |
| */ |
| pcover cb_consensus(T, c) |
| register pcover T; |
| register pcube c; |
| { |
| register pcube temp, last, p; |
| register pcover R; |
| |
| R = new_cover(T->count*2); |
| temp = new_cube(); |
| foreach_set(T, last, p) { |
| if (p != c) { |
| switch (cdist01(p, c)) { |
| case 0: |
| /* distance-0 needs special care */ |
| R = cb_consensus_dist0(R, p, c); |
| break; |
| |
| case 1: |
| /* distance-1 is easy because no sharping required */ |
| consensus(temp, p, c); |
| R = sf_addset(R, temp); |
| break; |
| } |
| } |
| } |
| set_free(temp); |
| return R; |
| } |
| |
| |
| /* |
| * form the sharp-consensus for p and c when they intersect |
| * What we are forming is consensus(p # c, c). |
| */ |
| pcover cb_consensus_dist0(R, p, c) |
| pcover R; |
| register pcube p, c; |
| { |
| int var; |
| bool got_one; |
| register pcube temp, mask; |
| register pcube p_diff_c=cube.temp[0], p_and_c=cube.temp[1]; |
| |
| /* If c contains p, then this gives us no information for essential test */ |
| if (setp_implies(p, c)) { |
| return R; |
| } |
| |
| /* For the multiple-valued variables */ |
| temp = new_cube(); |
| got_one = FALSE; |
| INLINEset_diff(p_diff_c, p, c); |
| INLINEset_and(p_and_c, p, c); |
| |
| for(var = cube.num_binary_vars; var < cube.num_vars; var++) { |
| /* Check if c(var) is contained in p(var) -- if so, no news */ |
| mask = cube.var_mask[var]; |
| if (! setp_disjoint(p_diff_c, mask)) { |
| INLINEset_merge(temp, c, p_and_c, mask); |
| R = sf_addset(R, temp); |
| got_one = TRUE; |
| } |
| } |
| |
| /* if no cube so far, add one for the intersection */ |
| if (! got_one && cube.num_binary_vars > 0) { |
| /* Add a single cube for the intersection of p and c */ |
| INLINEset_and(temp, p, c); |
| R = sf_addset(R, temp); |
| } |
| |
| set_free(temp); |
| return R; |
| } |