| /* |
| module: gasp.c |
| |
| The "last_gasp" heuristic computes the reduction of each cube in |
| the cover (without replacement) and then performs an expansion of |
| these cubes. The cubes which expand to cover some other cube are |
| added to the original cover and irredundant finds a minimal subset. |
| |
| If one of the reduced cubes expands to cover some other reduced |
| cube, then the new prime thus generated is a candidate for reducing |
| the size of the cover. |
| |
| super_gasp is a variation on this strategy which extracts a minimal |
| subset from the set of all prime implicants which cover all |
| maximally reduced cubes. |
| */ |
| |
| #include "espresso.h" |
| |
| |
| /* |
| * reduce_gasp -- compute the maximal reduction of each cube of F |
| * |
| * If a cube does not reduce, it remains prime; otherwise, it is marked |
| * as nonprime. If the cube is redundant (should NEVER happen here) we |
| * just crap out ... |
| * |
| * A cover with all of the cubes of F is returned. Those that did |
| * reduce are marked "NONPRIME"; those that reduced are marked "PRIME". |
| * The cubes are in the same order as in F. |
| */ |
| static pcover reduce_gasp(F, D) |
| pcover F, D; |
| { |
| pcube p, last, cunder, *FD; |
| pcover G; |
| |
| G = new_cover(F->count); |
| FD = cube2list(F, D); |
| |
| /* Reduce cubes of F without replacement */ |
| foreach_set(F, last, p) { |
| cunder = reduce_cube(FD, p); |
| if (setp_empty(cunder)) { |
| fatal("empty reduction in reduce_gasp, shouldn't happen"); |
| } else if (setp_equal(cunder, p)) { |
| SET(cunder, PRIME); /* just to make sure */ |
| G = sf_addset(G, p); /* it did not reduce ... */ |
| } else { |
| RESET(cunder, PRIME); /* it reduced ... */ |
| G = sf_addset(G, cunder); |
| } |
| if (debug & GASP) { |
| printf("REDUCE_GASP: %s reduced to %s\n", pc1(p), pc2(cunder)); |
| } |
| free_cube(cunder); |
| } |
| |
| free_cubelist(FD); |
| return G; |
| } |
| |
| /* |
| * expand_gasp -- expand each nonprime cube of F into a prime implicant |
| * |
| * The gasp strategy differs in that only those cubes which expand to |
| * cover some other cube are saved; also, all cubes are expanded |
| * regardless of whether they become covered or not. |
| */ |
| |
| pcover expand_gasp(F, D, R, Foriginal) |
| INOUT pcover F; |
| IN pcover D; |
| IN pcover R; |
| IN pcover Foriginal; |
| { |
| int c1index; |
| pcover G; |
| |
| /* Try to expand each nonprime and noncovered cube */ |
| G = new_cover(10); |
| for(c1index = 0; c1index < F->count; c1index++) { |
| expand1_gasp(F, D, R, Foriginal, c1index, &G); |
| } |
| G = sf_dupl(G); |
| G = expand(G, R, /*nonsparse*/ FALSE); /* Make them prime ! */ |
| return G; |
| } |
| |
| |
| |
| /* |
| * expand1 -- Expand a single cube against the OFF-set, using the gasp strategy |
| */ |
| void expand1_gasp(F, D, R, Foriginal, c1index, G) |
| pcover F; /* reduced cubes of ON-set */ |
| pcover D; /* DC-set */ |
| pcover R; /* OFF-set */ |
| pcover Foriginal; /* ON-set before reduction (same order as F) */ |
| int c1index; /* which index of F (or Freduced) to be checked */ |
| pcover *G; |
| { |
| register int c2index; |
| register pcube p, last, c2under; |
| pcube RAISE, FREESET, temp, *FD, c2essential; |
| pcover F1; |
| |
| if (debug & EXPAND1) { |
| printf("\nEXPAND1_GASP: \t%s\n", pc1(GETSET(F, c1index))); |
| } |
| |
| RAISE = new_cube(); |
| FREESET = new_cube(); |
| temp = new_cube(); |
| |
| /* Initialize the OFF-set */ |
| R->active_count = R->count; |
| foreach_set(R, last, p) { |
| SET(p, ACTIVE); |
| } |
| /* Initialize the reduced ON-set, all nonprime cubes become active */ |
| F->active_count = F->count; |
| foreachi_set(F, c2index, c2under) { |
| if (c1index == c2index || TESTP(c2under, PRIME)) { |
| F->active_count--; |
| RESET(c2under, ACTIVE); |
| } else { |
| SET(c2under, ACTIVE); |
| } |
| } |
| |
| /* Initialize the raising and unassigned sets */ |
| (void) set_copy(RAISE, GETSET(F, c1index)); |
| (void) set_diff(FREESET, cube.fullset, RAISE); |
| |
| /* Determine parts which must be lowered */ |
| essen_parts(R, F, RAISE, FREESET); |
| |
| /* Determine parts which can always be raised */ |
| essen_raising(R, RAISE, FREESET); |
| |
| /* See which, if any, of the reduced cubes we can cover */ |
| foreachi_set(F, c2index, c2under) { |
| if (TESTP(c2under, ACTIVE)) { |
| /* See if this cube can be covered by an expansion */ |
| if (setp_implies(c2under, RAISE) || |
| feasibly_covered(R, c2under, RAISE, temp)) { |
| |
| /* See if c1under can expanded to cover c2 reduced against |
| * (F - c1) u c1under; if so, c2 can definitely be removed ! |
| */ |
| |
| /* Copy F and replace c1 with c1under */ |
| F1 = sf_save(Foriginal); |
| (void) set_copy(GETSET(F1, c1index), GETSET(F, c1index)); |
| |
| /* Reduce c2 against ((F - c1) u c1under) */ |
| FD = cube2list(F1, D); |
| c2essential = reduce_cube(FD, GETSET(F1, c2index)); |
| free_cubelist(FD); |
| sf_free(F1); |
| |
| /* See if c2essential is covered by an expansion of c1under */ |
| if (feasibly_covered(R, c2essential, RAISE, temp)) { |
| (void) set_or(temp, RAISE, c2essential); |
| RESET(temp, PRIME); /* cube not prime */ |
| *G = sf_addset(*G, temp); |
| } |
| set_free(c2essential); |
| } |
| } |
| } |
| |
| free_cube(RAISE); |
| free_cube(FREESET); |
| free_cube(temp); |
| } |
| |
| /* irred_gasp -- Add new primes to F and find an irredundant subset */ |
| pcover irred_gasp(F, D, G) |
| pcover F, D, G; /* G is disposed of */ |
| { |
| if (G->count != 0) |
| F = irredundant(sf_append(F, G), D); |
| else |
| free_cover(G); |
| return F; |
| } |
| |
| |
| /* last_gasp */ |
| pcover last_gasp(F, D, R, cost) |
| pcover F, D, R; |
| cost_t *cost; |
| { |
| pcover G, G1; |
| |
| EXECUTE(G = reduce_gasp(F, D), GREDUCE_TIME, G, *cost); |
| EXECUTE(G1 = expand_gasp(G, D, R, F), GEXPAND_TIME, G1, *cost); |
| free_cover(G); |
| EXECUTE(F = irred_gasp(F, D, G1), GIRRED_TIME, F, *cost); |
| return F; |
| } |
| |
| |
| /* super_gasp */ |
| pcover super_gasp(F, D, R, cost) |
| pcover F, D, R; |
| cost_t *cost; |
| { |
| pcover G, G1; |
| |
| EXECUTE(G = reduce_gasp(F, D), GREDUCE_TIME, G, *cost); |
| EXECUTE(G1 = all_primes(G, R), GEXPAND_TIME, G1, *cost); |
| free_cover(G); |
| EXEC(G = sf_dupl(sf_append(F, G1)), "NEWPRIMES", G); |
| EXECUTE(F = irredundant(G, D), IRRED_TIME, F, *cost); |
| return F; |
| } |