expand.c

主要进行大规模的电路综合

    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)
	(void) 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)
	(void) 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)
	(void) 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;

    (void) 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) {
	(void) 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;
}