| /* | |
| module: expand.c | |
| purpose: Perform the Espresso-II Expansion Step | |
| The idea is to take each nonprime cube of the on-set and expand it | |
| into a prime implicant such that we can cover as many other cubes | |
| of the on-set. If no cube of the on-set can be covered, then we | |
| expand each cube into a large prime implicant by transforming the | |
| problem into a minimum covering problem which is solved by the | |
| heuristics of minimum_cover. | |
| These routines revolve around having a representation of the | |
| OFF-set. (In contrast to the Espresso-II manuscript, we do NOT | |
| require an "unwrapped" version of the OFF-set). | |
| Some conventions on variable names: | |
| SUPER_CUBE is the supercube of all cubes which can be covered | |
| by an expansion of the cube being expanded | |
| OVEREXPANDED_CUBE is the cube which would result from expanding | |
| all parts which can expand individually of the cube being expanded | |
| RAISE is the current expansion of the current cube | |
| FREESET is the set of parts which haven't been raised or lowered yet. | |
| INIT_LOWER is a set of parts to be removed from the free parts before | |
| starting the expansion | |
| */ | |
| #include "espresso.h" | |
| /* | |
| expand -- expand each nonprime cube of F into a prime implicant | |
| If nonsparse is true, only the non-sparse variables will be expanded; | |
| this is done by forcing all of the sparse variables out of the free set. | |
| */ | |
| pcover expand(F, R, nonsparse) | |
| INOUT pcover F; | |
| IN pcover R; | |
| IN bool nonsparse; /* expand non-sparse variables only */ | |
| { | |
| register pcube last, p; | |
| pcube RAISE, FREESET, INIT_LOWER, SUPER_CUBE, OVEREXPANDED_CUBE; | |
| int var, num_covered; | |
| bool change; | |
| /* Order the cubes according to "chewing-away from the edges" of mini */ | |
| if (use_random_order) | |
| F = random_order(F); | |
| else | |
| F = mini_sort(F, ascend); | |
| /* Allocate memory for variables needed by expand1() */ | |
| RAISE = new_cube(); | |
| FREESET = new_cube(); | |
| INIT_LOWER = new_cube(); | |
| SUPER_CUBE = new_cube(); | |
| OVEREXPANDED_CUBE = new_cube(); | |
| /* Setup the initial lowering set (differs only for nonsparse) */ | |
| if (nonsparse) | |
| for(var = 0; var < cube.num_vars; var++) | |
| if (cube.sparse[var]) | |
| (void) set_or(INIT_LOWER, INIT_LOWER, cube.var_mask[var]); | |
| /* Mark all cubes as not covered, and maybe essential */ | |
| foreach_set(F, last, p) { | |
| RESET(p, COVERED); | |
| RESET(p, NONESSEN); | |
| } | |
| /* Try to expand each nonprime and noncovered cube */ | |
| foreach_set(F, last, p) { | |
| /* do not expand if PRIME or if covered by previous expansion */ | |
| if (! TESTP(p, PRIME) && ! TESTP(p, COVERED)) { | |
| /* expand the cube p, result is RAISE */ | |
| expand1(R, F, RAISE, FREESET, OVEREXPANDED_CUBE, SUPER_CUBE, | |
| INIT_LOWER, &num_covered, p); | |
| if (debug & EXPAND) | |
| printf("EXPAND: %s (covered %d)\n", pc1(p), num_covered); | |
| (void) set_copy(p, RAISE); | |
| SET(p, PRIME); | |
| RESET(p, COVERED); /* not really necessary */ | |
| /* See if we generated an inessential prime */ | |
| if (num_covered == 0 && ! setp_equal(p, OVEREXPANDED_CUBE)) { | |
| SET(p, NONESSEN); | |
| } | |
| } | |
| } | |
| /* Delete any cubes of F which became covered during the expansion */ | |
| F->active_count = 0; | |
| change = FALSE; | |
| foreach_set(F, last, p) { | |
| if (TESTP(p, COVERED)) { | |
| RESET(p, ACTIVE); | |
| change = TRUE; | |
| } else { | |
| SET(p, ACTIVE); | |
| F->active_count++; | |
| } | |
| } | |
| if (change) | |
| F = sf_inactive(F); | |
| free_cube(RAISE); | |
| free_cube(FREESET); | |
| free_cube(INIT_LOWER); | |
| free_cube(SUPER_CUBE); | |
| free_cube(OVEREXPANDED_CUBE); | |
| return F; | |
| } | |
| /* | |
| expand1 -- Expand a single cube against the OFF-set | |
| */ | |
| void expand1(BB, CC, RAISE, FREESET, OVEREXPANDED_CUBE, SUPER_CUBE, | |
| INIT_LOWER, num_covered, c) | |
| pcover BB; /* Blocking matrix (OFF-set) */ | |
| pcover CC; /* Covering matrix (ON-set) */ | |
| pcube RAISE; /* The current parts which have been raised */ | |
| pcube FREESET; /* The current parts which are free */ | |
| pcube OVEREXPANDED_CUBE; /* Overexpanded cube of c */ | |
| pcube SUPER_CUBE; /* Supercube of all cubes of CC we cover */ | |
| pcube INIT_LOWER; /* Parts to initially remove from FREESET */ | |
| int *num_covered; /* Number of cubes of CC which are covered */ | |
| pcube c; /* The cube to be expanded */ | |
| { | |
| int bestindex; | |
| if (debug & EXPAND1) | |
| printf("\nEXPAND1: \t%s\n", pc1(c)); | |
| /* initialize BB and CC */ | |
| SET(c, PRIME); /* don't try to cover ourself */ | |
| setup_BB_CC(BB, CC); | |
| /* initialize count of # cubes covered, and the supercube of them */ | |
| *num_covered = 0; | |
| (void) set_copy(SUPER_CUBE, c); | |
| /* Initialize the lowering, raising and unassigned sets */ | |
| (void) set_copy(RAISE, c); | |
| (void) set_diff(FREESET, cube.fullset, RAISE); | |
| /* If some parts are forced into lowering set, remove them */ | |
| if (! setp_empty(INIT_LOWER)) { | |
| (void) set_diff(FREESET, FREESET, INIT_LOWER); | |
| elim_lowering(BB, CC, RAISE, FREESET); | |
| } | |
| /* Determine what can be raised, and return the over-expanded cube */ | |
| essen_parts(BB, CC, RAISE, FREESET); | |
| (void) set_or(OVEREXPANDED_CUBE, RAISE, FREESET); | |
| /* While there are still cubes which can be covered, cover them ! */ | |
| if (CC->active_count > 0) { | |
| select_feasible(BB, CC, RAISE, FREESET, SUPER_CUBE, num_covered); | |
| } | |
| /* While there are still cubes covered by the overexpanded cube ... */ | |
| while (CC->active_count > 0) { | |
| bestindex = most_frequent(CC, FREESET); | |
| set_insert(RAISE, bestindex); | |
| set_remove(FREESET, bestindex); | |
| essen_parts(BB, CC, RAISE, FREESET); | |
| } | |
| /* Finally, when all else fails, choose the largest possible prime */ | |
| /* We will loop only if we decide unravelling OFF-set is too expensive */ | |
| while (BB->active_count > 0) { | |
| mincov(BB, RAISE, FREESET); | |
| } | |
| /* Raise any remaining free coordinates */ | |
| (void) set_or(RAISE, RAISE, FREESET); | |
| } | |
| /* | |
| essen_parts -- determine which parts are forced into the lowering | |
| set to insure that the cube be orthognal to the OFF-set. | |
| If any cube of the OFF-set is distance 1 from the raising cube, | |
| then we must lower all parts of the conflicting variable. (If the | |
| cube is distance 0, we detect this error here.) | |
| If there are essentially lowered parts, we can remove from consideration | |
| any cubes of the OFF-set which are more than distance 1 from the | |
| overexpanded cube of RAISE. | |
| */ | |
| void essen_parts(BB, CC, RAISE, FREESET) | |
| pcover BB, CC; | |
| pcube RAISE, FREESET; | |
| { | |
| register pcube p, r = RAISE; | |
| pcube lastp, xlower = cube.temp[0]; | |
| int dist; | |
| (void) set_copy(xlower, cube.emptyset); | |
| foreach_active_set(BB, lastp, p) { | |
| #ifdef NO_INLINE | |
| if ((dist = cdist01(p, r)) > 1) goto exit_if; | |
| #else | |
| {register int w,last;register unsigned int x;dist=0;if((last=cube.inword)!=-1) | |
| {x=p[last]&r[last];if(x=~(x|x>>1)&cube.inmask)if((dist=count_ones(x))>1)goto | |
| exit_if;for(w=1;w<last;w++){x=p[w]&r[w];if(x=~(x|x>>1)&DISJOINT)if(dist==1||( | |
| dist+=count_ones(x))>1)goto exit_if;}}}{register int w,var,last;register pcube | |
| mask;for(var=cube.num_binary_vars;var<cube.num_vars;var++){mask=cube.var_mask[ | |
| var];last=cube.last_word[var];for(w=cube.first_word[var];w<=last;w++)if(p[w]&r[ | |
| w]&mask[w])goto nextvar;if(++dist>1)goto exit_if;nextvar:;}} | |
| #endif | |
| if (dist == 0) { | |
| fatal("ON-set and OFF-set are not orthogonal"); | |
| } else { | |
| (void) force_lower(xlower, p, r); | |
| BB->active_count--; | |
| RESET(p, ACTIVE); | |
| } | |
| exit_if: ; | |
| } | |
| if (! setp_empty(xlower)) { | |
| (void) set_diff(FREESET, FREESET, xlower);/* remove from free set */ | |
| elim_lowering(BB, CC, RAISE, FREESET); | |
| } | |
| if (debug & EXPAND1) | |
| printf("ESSEN_PARTS:\tRAISE=%s FREESET=%s\n", pc1(RAISE), pc2(FREESET)); | |
| } | |
| /* | |
| essen_raising -- determine which parts may always be added to | |
| the raising set without restricting further expansions | |
| General rule: if some part is not blocked by any cube of BB, then | |
| this part can always be raised. | |
| */ | |
| void essen_raising(BB, RAISE, FREESET) | |
| register pcover BB; | |
| pcube RAISE, FREESET; | |
| { | |
| register pcube last, p, xraise = cube.temp[0]; | |
| /* Form union of all cubes of BB, and then take complement wrt FREESET */ | |
| (void) set_copy(xraise, cube.emptyset); | |
| foreach_active_set(BB, last, p) | |
| INLINEset_or(xraise, xraise, p); | |
| (void) set_diff(xraise, FREESET, xraise); | |
| (void) set_or(RAISE, RAISE, xraise); /* add to raising set */ | |
| (void) set_diff(FREESET, FREESET, xraise); /* remove from free set */ | |
| if (debug & EXPAND1) | |
| printf("ESSEN_RAISING:\tRAISE=%s FREESET=%s\n", | |
| pc1(RAISE), pc2(FREESET)); | |
| } | |
| /* | |
| elim_lowering -- after removing parts from FREESET, we can reduce the | |
| size of both BB and CC. | |
| We mark as inactive any cube of BB which does not intersect the | |
| overexpanded cube (i.e., RAISE + FREESET). Likewise, we remove | |
| from CC any cube which is not covered by the overexpanded cube. | |
| */ | |
| void elim_lowering(BB, CC, RAISE, FREESET) | |
| pcover BB, CC; | |
| pcube RAISE, FREESET; | |
| { | |
| register pcube p, r = set_or(cube.temp[0], RAISE, FREESET); | |
| pcube last; | |
| /* | |
| * Remove sets of BB which are orthogonal to future expansions | |
| */ | |
| foreach_active_set(BB, last, p) { | |
| #ifdef NO_INLINE | |
| if (! cdist0(p, r)) | |
| #else | |
| {register int w,lastw;register unsigned int x;if((lastw=cube.inword)!=-1){x=p[ | |
| lastw]&r[lastw];if(~(x|x>>1)&cube.inmask)goto false;for(w=1;w<lastw;w++){x=p[w] | |
| &r[w];if(~(x|x>>1)&DISJOINT)goto false;}}}{register int w,var,lastw;register | |
| pcube mask;for(var=cube.num_binary_vars;var<cube.num_vars;var++){mask=cube. | |
| var_mask[var];lastw=cube.last_word[var];for(w=cube.first_word[var];w<=lastw;w++) | |
| if(p[w]&r[w]&mask[w])goto nextvar;goto false;nextvar:;}}continue;false: | |
| #endif | |
| BB->active_count--, RESET(p, ACTIVE); | |
| } | |
| /* | |
| * Remove sets of CC which cannot be covered by future expansions | |
| */ | |
| if (CC != (pcover) NULL) { | |
| foreach_active_set(CC, last, p) { | |
| #ifdef NO_INLINE | |
| if (! setp_implies(p, r)) | |
| #else | |
| INLINEsetp_implies(p, r, /* when false => */ goto false1); | |
| /* when true => go to end of loop */ continue; | |
| false1: | |
| #endif | |
| CC->active_count--, RESET(p, ACTIVE); | |
| } | |
| } | |
| } | |
| /* | |
| most_frequent -- When all else fails, select a reasonable part to raise | |
| The active cubes of CC are the cubes which are covered by the | |
| overexpanded cube of the original cube (however, we know that none | |
| of them can actually be covered by a feasible expansion of the | |
| original cube). We resort to the MINI strategy of selecting to | |
| raise the part which will cover the same part in the most cubes of CC. | |
| */ | |
| int most_frequent(CC, FREESET) | |
| pcover CC; | |
| pcube FREESET; | |
| { | |
| register int i, best_part, best_count, *count; | |
| register pset p, last; | |
| /* Count occurences of each variable */ | |
| count = ALLOC(int, cube.size); | |
| for(i = 0; i < cube.size; i++) | |
| count[i] = 0; | |
| if (CC != (pcover) NULL) | |
| foreach_active_set(CC, last, p) | |
| set_adjcnt(p, count, 1); | |
| /* Now find which free part occurs most often */ | |
| best_count = best_part = -1; | |
| for(i = 0; i < cube.size; i++) | |
| if (is_in_set(FREESET,i) && count[i] > best_count) { | |
| best_part = i; | |
| best_count = count[i]; | |
| } | |
| FREE(count); | |
| if (debug & EXPAND1) | |
| printf("MOST_FREQUENT:\tbest=%d FREESET=%s\n", best_part, pc2(FREESET)); | |
| return best_part; | |
| } | |
| /* | |
| setup_BB_CC -- set up the blocking and covering set families; | |
| Note that the blocking family is merely the set of cubes of R, and | |
| that CC is the set of cubes of F which might possibly be covered | |
| (i.e., nonprime cubes, and cubes not already covered) | |
| */ | |
| void setup_BB_CC(BB, CC) | |
| register pcover BB, CC; | |
| { | |
| register pcube p, last; | |
| /* Create the block and cover set families */ | |
| BB->active_count = BB->count; | |
| foreach_set(BB, last, p) | |
| SET(p, ACTIVE); | |
| if (CC != (pcover) NULL) { | |
| CC->active_count = CC->count; | |
| foreach_set(CC, last, p) | |
| if (TESTP(p, COVERED) || TESTP(p, PRIME)) | |
| CC->active_count--, RESET(p, ACTIVE); | |
| else | |
| SET(p, ACTIVE); | |
| } | |
| } | |
| /* | |
| select_feasible -- Determine if there are cubes which can be covered, | |
| and if so, raise those parts necessary to cover as many as possible. | |
| We really don't check to maximize the number that can be covered; | |
| instead, we check, for each fcc, how many other fcc remain fcc | |
| after expanding to cover the fcc. (Essentially one-level lookahead). | |
| */ | |
| void select_feasible(BB, CC, RAISE, FREESET, SUPER_CUBE, num_covered) | |
| pcover BB, CC; | |
| pcube RAISE, FREESET, SUPER_CUBE; | |
| int *num_covered; | |
| { | |
| register pcube p, last, bestfeas, *feas; | |
| register int i, j; | |
| pcube *feas_new_lower; | |
| int bestcount, bestsize, count, size, numfeas, lastfeas; | |
| pcover new_lower; | |
| /* Start out with all cubes covered by the over-expanded cube as | |
| * the "possibly" feasibly-covered cubes (pfcc) | |
| */ | |
| feas = ALLOC(pcube, CC->active_count); | |
| numfeas = 0; | |
| foreach_active_set(CC, last, p) | |
| feas[numfeas++] = p; | |
| /* Setup extra cubes to record parts forced low after a covering */ | |
| feas_new_lower = ALLOC(pcube, CC->active_count); | |
| new_lower = new_cover(numfeas); | |
| for(i = 0; i < numfeas; i++) | |
| feas_new_lower[i] = GETSET(new_lower, i); | |
| loop: | |
| /* Find the essentially raised parts -- this might cover some cubes | |
| for us, without having to find out if they are fcc or not | |
| */ | |
| essen_raising(BB, RAISE, FREESET); | |
| /* Now check all "possibly" feasibly covered cubes to check feasibility */ | |
| lastfeas = numfeas; | |
| numfeas = 0; | |
| for(i = 0; i < lastfeas; i++) { | |
| p = feas[i]; | |
| /* Check active because essen_parts might have removed it */ | |
| if (TESTP(p, ACTIVE)) { | |
| /* See if the cube is already covered by RAISE -- | |
| * this can happen because of essen_raising() or because of | |
| * the previous "loop" | |
| */ | |
| if (setp_implies(p, RAISE)) { | |
| (*num_covered) += 1; | |
| (void) set_or(SUPER_CUBE, SUPER_CUBE, p); | |
| CC->active_count--; | |
| RESET(p, ACTIVE); | |
| SET(p, COVERED); | |
| /* otherwise, test if it is feasibly covered */ | |
| } else if (feasibly_covered(BB,p,RAISE,feas_new_lower[numfeas])) { | |
| feas[numfeas] = p; /* save the fcc */ | |
| numfeas++; | |
| } | |
| } | |
| } | |
| if (debug & EXPAND1) | |
| printf("SELECT_FEASIBLE: started with %d pfcc, ended with %d fcc\n", | |
| lastfeas, numfeas); | |
| /* Exit here if there are no feasibly covered cubes */ | |
| if (numfeas == 0) { | |
| FREE(feas); | |
| FREE(feas_new_lower); | |
| free_cover(new_lower); | |
| return; | |
| } | |
| /* Now find which is the best feasibly covered cube */ | |
| bestcount = 0; | |
| bestsize = 9999; | |
| for(i = 0; i < numfeas; i++) { | |
| size = set_dist(feas[i], FREESET); /* # of newly raised parts */ | |
| count = 0; /* # of other cubes which remain fcc after raising */ | |
| #define NEW | |
| #ifdef NEW | |
| for(j = 0; j < numfeas; j++) | |
| if (setp_disjoint(feas_new_lower[i], feas[j])) | |
| count++; | |
| #else | |
| for(j = 0; j < numfeas; j++) | |
| if (setp_implies(feas[j], feas[i])) | |
| count++; | |
| #endif | |
| if (count > bestcount) { | |
| bestcount = count; | |
| bestfeas = feas[i]; | |
| bestsize = size; | |
| } else if (count == bestcount && size < bestsize) { | |
| bestfeas = feas[i]; | |
| bestsize = size; | |
| } | |
| } | |
| /* Add the necessary parts to the raising set */ | |
| (void) set_or(RAISE, RAISE, bestfeas); | |
| (void) set_diff(FREESET, FREESET, RAISE); | |
| if (debug & EXPAND1) | |
| printf("FEASIBLE: \tRAISE=%s FREESET=%s\n", pc1(RAISE), pc2(FREESET)); | |
| essen_parts(BB, CC, RAISE, FREESET); | |
| goto loop; | |
| /* NOTREACHED */ | |
| } | |
| /* | |
| feasibly_covered -- determine if the cube c is feasibly covered | |
| (i.e., if it is possible to raise all of the necessary variables | |
| while still insuring orthogonality with R). Also, if c is feasibly | |
| covered, then compute the new set of parts which are forced into | |
| the lowering set. | |
| */ | |
| bool feasibly_covered(BB, c, RAISE, new_lower) | |
| pcover BB; | |
| pcube c, RAISE, new_lower; | |
| { | |
| register pcube p, r = set_or(cube.temp[0], RAISE, c); | |
| int dist; | |
| pcube lastp; | |
| set_copy(new_lower, cube.emptyset); | |
| foreach_active_set(BB, lastp, p) { | |
| #ifdef NO_INLINE | |
| if ((dist = cdist01(p, r)) > 1) goto exit_if; | |
| #else | |
| {register int w,last;register unsigned int x;dist=0;if((last=cube.inword)!=-1) | |
| {x=p[last]&r[last];if(x=~(x|x>>1)&cube.inmask)if((dist=count_ones(x))>1)goto | |
| exit_if;for(w=1;w<last;w++){x=p[w]&r[w];if(x=~(x|x>>1)&DISJOINT)if(dist==1||( | |
| dist+=count_ones(x))>1)goto exit_if;}}}{register int w,var,last;register pcube | |
| mask;for(var=cube.num_binary_vars;var<cube.num_vars;var++){mask=cube.var_mask[ | |
| var];last=cube.last_word[var];for(w=cube.first_word[var];w<=last;w++)if(p[w]&r[ | |
| w]&mask[w])goto nextvar;if(++dist>1)goto exit_if;nextvar:;}} | |
| #endif | |
| if (dist == 0) | |
| return FALSE; | |
| else | |
| (void) force_lower(new_lower, p, r); | |
| exit_if: ; | |
| } | |
| return TRUE; | |
| } | |
| /* | |
| mincov -- transform the problem of expanding a cube to a maximally- | |
| large prime implicant into the problem of selecting a minimum | |
| cardinality cover over a family of sets. | |
| When we get to this point, we must unravel the remaining off-set. | |
| This may be painful. | |
| */ | |
| void mincov(BB, RAISE, FREESET) | |
| pcover BB; | |
| pcube RAISE, FREESET; | |
| { | |
| int expansion, nset, var, dist; | |
| pset_family B; | |
| register pcube xraise=cube.temp[0], xlower, p, last, plower; | |
| #ifdef RANDOM_MINCOV | |
| dist = random() % set_ord(FREESET); | |
| for(var = 0; var < cube.size && dist >= 0; var++) { | |
| if (is_in_set(FREESET, var)) { | |
| dist--; | |
| } | |
| } | |
| set_insert(RAISE, var); | |
| set_remove(FREESET, var); | |
| (void) essen_parts(BB, /*CC*/ (pcover) NULL, RAISE, FREESET); | |
| #else | |
| /* Create B which are those cubes which we must avoid intersecting */ | |
| B = new_cover(BB->active_count); | |
| foreach_active_set(BB, last, p) { | |
| plower = set_copy(GETSET(B, B->count++), cube.emptyset); | |
| (void) force_lower(plower, p, RAISE); | |
| } | |
| /* Determine how many sets it will blow up into after the unravel */ | |
| nset = 0; | |
| foreach_set(B, last, p) { | |
| expansion = 1; | |
| for(var = cube.num_binary_vars; var < cube.num_vars; var++) { | |
| if ((dist=set_dist(p, cube.var_mask[var])) > 1) { | |
| expansion *= dist; | |
| if (expansion > 500) goto heuristic_mincov; | |
| } | |
| } | |
| nset += expansion; | |
| if (nset > 500) goto heuristic_mincov; | |
| } | |
| B = unravel(B, cube.num_binary_vars); | |
| xlower = do_sm_minimum_cover(B); | |
| /* Add any remaining free parts to the raising set */ | |
| (void) set_or(RAISE, RAISE, set_diff(xraise, FREESET, xlower)); | |
| (void) set_copy(FREESET, cube.emptyset); /* free set is empty */ | |
| BB->active_count = 0; /* BB satisfied */ | |
| if (debug & EXPAND1) { | |
| printf("MINCOV: \tRAISE=%s FREESET=%s\n", pc1(RAISE), pc2(FREESET)); | |
| } | |
| sf_free(B); | |
| set_free(xlower); | |
| return; | |
| heuristic_mincov: | |
| sf_free(B); | |
| /* most_frequent will pick first free part */ | |
| set_insert(RAISE, most_frequent(/*CC*/ (pcover) NULL, FREESET)); | |
| (void) set_diff(FREESET, FREESET, RAISE); | |
| essen_parts(BB, /*CC*/ (pcover) NULL, RAISE, FREESET); | |
| return; | |
| #endif | |
| } | |
| /* | |
| find_all_primes -- find all of the primes which cover the | |
| currently reduced BB | |
| */ | |
| pcover find_all_primes(BB, RAISE, FREESET) | |
| pcover BB; | |
| register pcube RAISE, FREESET; | |
| { | |
| register pset last, p, plower; | |
| pset_family B, B1; | |
| if (BB->active_count == 0) { | |
| B1 = new_cover(1); | |
| p = GETSET(B1, B1->count++); | |
| (void) set_copy(p, RAISE); | |
| SET(p, PRIME); | |
| } else { | |
| B = new_cover(BB->active_count); | |
| foreach_active_set(BB, last, p) { | |
| plower = set_copy(GETSET(B, B->count++), cube.emptyset); | |
| (void) force_lower(plower, p, RAISE); | |
| } | |
| B = sf_rev_contain(unravel(B, cube.num_binary_vars)); | |
| B1 = exact_minimum_cover(B); | |
| foreach_set(B1, last, p) { | |
| INLINEset_diff(p, FREESET, p); | |
| INLINEset_or(p, p, RAISE); | |
| SET(p, PRIME); | |
| } | |
| free_cover(B); | |
| } | |
| return B1; | |
| } | |
| /* | |
| all_primes -- foreach cube in F, generate all of the primes | |
| which cover the cube. | |
| */ | |
| pcover all_primes(F, R) | |
| pcover F, R; | |
| { | |
| register pcube last, p, RAISE, FREESET; | |
| pcover Fall_primes, B1; | |
| FREESET = new_cube(); | |
| RAISE = new_cube(); | |
| Fall_primes = new_cover(F->count); | |
| foreach_set(F, last, p) { | |
| if (TESTP(p, PRIME)) { | |
| Fall_primes = sf_addset(Fall_primes, p); | |
| } else { | |
| /* Setup for call to essential parts */ | |
| (void) set_copy(RAISE, p); | |
| (void) set_diff(FREESET, cube.fullset, RAISE); | |
| setup_BB_CC(R, /* CC */ (pcover) NULL); | |
| essen_parts(R, /* CC */ (pcover) NULL, RAISE, FREESET); | |
| /* Find all of the primes, and add them to the prime set */ | |
| B1 = find_all_primes(R, RAISE, FREESET); | |
| Fall_primes = sf_append(Fall_primes, B1); | |
| } | |
| } | |
| set_free(RAISE); | |
| set_free(FREESET); | |
| return Fall_primes; | |
| } |