diff options
Diffstat (limited to 'src/misc/espresso/expand.c')
| -rw-r--r-- | src/misc/espresso/expand.c | 693 |
1 files changed, 0 insertions, 693 deletions
diff --git a/src/misc/espresso/expand.c b/src/misc/espresso/expand.c deleted file mode 100644 index 2765d71c..00000000 --- a/src/misc/espresso/expand.c +++ /dev/null @@ -1,693 +0,0 @@ -/* - * Revision Control Information - * - * $Source$ - * $Author$ - * $Revision$ - * $Date$ - * - */ -/* - 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 -#if defined(_POSIX_SOURCE) || defined(__SVR4) - dist = rand() % set_ord(FREESET); -#else - dist = random() % set_ord(FREESET); -#endif - 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; -} |