minimize.c

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

    F_sorted = sf_unlist(F1, F->count, F->sf_size);
    free_cover(F);

    return F_sorted;
}

/*
 * nc_reduce_cube -- find the maximal reduction of a cube
 */

pcube
nc_reduce_cube(FD, p)
IN pcube *FD, p;

{
    pcube cunder;

    cunder = nc_sccc(cofactor(FD, p), 1);
    return set_and(cunder, cunder, p);
}


/* nc_sccc -- find Smallest Cube Containing the Complement of a cover */
pcube
nc_sccc(T, level)
INOUT pcube *T;         /* T will be disposed of */
IN int level;
{
    pcube r, *Tl, *Tr;
    register pcube cl, cr;
    register int best;
    static int sccc_level = 0;

    if (debug & REDUCE1) {
	debug_print(T, "SCCC", sccc_level++);
    }

    if (nc_sccc_special_cases(T, &r, level) == MAYBE) {
	cl = new_cube();
	cr = new_cube();
	best = binate_split_select(T, cl, cr, REDUCE1);

	Tl = scofactor(T, cl, best);
	Tr = scofactor(T, cr, best);
	free_cubelist(T);
	    
	r = sccc_merge(nc_sccc(Tl, level+1), nc_sccc(Tr, level+1), cl, cr);
    }

    if (debug & REDUCE1)
	(void) printf("SCCC[%d]: result is %s\n", --sccc_level, pc1(r));
    return r;
}

/*
 *   nc_sccc_special_cases -- check the special cases for sccc
 */

bool
nc_sccc_special_cases(T, result, level)
INOUT pcube *T;                 /* will be disposed if answer is determined */
OUT pcube *result;              /* returned only if answer determined */
IN int level;
{
    register pcube *T1, p, temp = cube.temp[1], ceil, cof = T[0];
    pcube *A, *B;
    int size;

    /* empty cover => complement is universe => SCCC is universe */
    if (T[2] == NULL) {
	*result = set_save(cube.fullset);
	free_cubelist(T);
	return TRUE;
    }

    /* row of 1's => complement is empty => SCCC is empty */
    for(T1 = T+2; (p = *T1++) != NULL; ) {
	if (full_row(p, cof)) {
	    *result = new_cube();
	    free_cubelist(T);
	    return TRUE;
	}
    }

    /* Throw away the unnecessary cubes */
    size = CUBELISTSIZE(T);
    if ((size > 200) || ((level % N_level == 0) && size > 50))
	rem_unnec_r_cubes(T);

    /* Collect column counts, determine unate variables, etc. */
    massive_count(T);

    /* If cover is unate (or single cube), apply simple rules to find SCCCU */
    if (cdata.vars_unate == cdata.vars_active || T[3] == NULL) {
	*result = set_save(cube.fullset);
	for(T1 = T+2; (p = *T1++) != NULL; ) {
	    (void) sccc_cube(*result, set_or(temp, p, cof));
	}
	free_cubelist(T);
	return TRUE;
    }

    /* Check for column of 0's (which can be easily factored( */
    ceil = set_save(cof);
    for(T1 = T+2; (p = *T1++) != NULL; ) {
	INLINEset_or(ceil, ceil, p);
    }
    if (! setp_equal(ceil, cube.fullset)) {
	*result = sccc_cube(set_save(cube.fullset), ceil);
	if (setp_equal(*result, cube.fullset)) {
	    free_cube(ceil);
	} else {
	    *result = sccc_merge(nc_sccc(cofactor(T,ceil), level+1),
			 set_save(cube.fullset), ceil, *result);
	}
	free_cubelist(T);
	return TRUE;
    }
    free_cube(ceil);

    /* Single active column at this point => tautology => SCCC is empty */
    if (cdata.vars_active == 1) {
	*result = new_cube();
	free_cubelist(T);
	return TRUE;
    }

    /* Check for components */
    if (cdata.var_zeros[cdata.best] < CUBELISTSIZE(T)/2) {
	if (cubelist_partition(T, &A, &B, debug & REDUCE1) == 0) {
	    return MAYBE;
	} else {
	    free_cubelist(T);
	    *result = nc_sccc(A, level+1);
	    ceil = nc_sccc(B, level+1);
	    (void) set_and(*result, *result, ceil);
	    set_free(ceil);
	    return TRUE;
	}
    }

    /* Not much we can do about it */
    return MAYBE;
}

/*
 * ncp_expand -- similar to nc_expand but uses ncp_expand1 instead of
 * expand1
 */
pcover
ncp_expand(F, Fold, nonsparse)
INOUT pcover F;
IN pcover Fold;
IN bool nonsparse;              /* expand non-sparse variables only */

{
    register pcube last, p;

    register pcube 
	RAISE = nc_tmp_cube[0],
	FREESET = nc_tmp_cube[1],
	INIT_LOWER = nc_tmp_cube[2],
	SUPER_CUBE = nc_tmp_cube[3],
	OVEREXPANDED_CUBE = nc_tmp_cube[4];

    int var, num_covered;
    int index;
    bool change;

    /* Order the cubes according to "chewing-away from the edges" of mini */
    if (use_random_order) {
	if (Fold != (pcover) NULL)
	    F = nc_random_order(F, Fold);
	else
	    F = random_order(F);
    }
    else {
	if (Fold != (pcover) NULL)
	    F = nc_mini_sort(F, &Fold, ascend);
	else
	    F = mini_sort(F, ascend);
    }

    /* 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 */
    foreachi_set(F, index, p) {
	/* do not expand if PRIME or if covered by previous expansion */
	if (! TESTP(p, PRIME) && ! TESTP(p, COVERED)) {

	    /* find the reduced offset for p */

	    ROS = get_ROS(index, F, Fold);

	    /* expand the cube p, result is RAISE */
	    ncp_expand1(ROS, F, RAISE, FREESET, OVEREXPANDED_CUBE, SUPER_CUBE,
		INIT_LOWER, &num_covered, p);

	    if (debug & EXPAND)
		(void) 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);

    if (Fold != (pcover) NULL)
       sf_free(Fold);

    return F;
}

/*
 *  ncp_expand1 -- Similar to expand1 except that when there are no
 *  more feasible cubes, it goes to mincov even if there are some
 *  yet uncovered cubes left in the cover.
 *
 */

void
ncp_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 */

{

    if (debug & EXPAND1)
	(void) 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);
    }

    /* 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);
}

/*
 *  nc_first_expand -- expand each nonprime cube of F into a prime implicant
 *  
 *  This subroutine differs from expand in that it is not passed on
 *  the global off set. For each cube to be expanded, this subroutine 
 *  computes a subset of off set which is sufficient for the expansion 
 *  of the cube.
 * 
 *  The subset produced is very small is limited by the number of
 *  literal in the cube to be expanded. This is an attempt to handle
 *  functions with very large off sets.
 *
 *  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
nc_first_expand(F, nonsparse)
INOUT pcover F;
IN bool nonsparse;              /* expand non-sparse variables only */

{
    register pcube last, p;

    register pcube 
	RAISE = nc_tmp_cube[0],
	FREESET = nc_tmp_cube[1],
	INIT_LOWER = nc_tmp_cube[2],
	SUPER_CUBE = nc_tmp_cube[3],
	OVEREXPANDED_CUBE = nc_tmp_cube[4],
	overexpanded_cube = nc_tmp_cube[5],
	init_lower = nc_tmp_cube[6];

    pcube q, qlast;
    int var, num_covered;
    int index;
    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);

    /* 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 */
    foreachi_set(F, index, p) {

	if (! TESTP(p, PRIME) && ! TESTP(p, COVERED)) {

	    /* find the overexpanded cube of p */
	    get_OC(p, overexpanded_cube, (pcube) NULL);

	    /* If the overexpanded_cube is the same as p then p cannot 
	       be expanded */
	    if (setp_equal(p, overexpanded_cube)) {
		foreach_set(F, qlast, q)
		    if (setp_implies(q, p))
			SET(q, COVERED);
		SET(p, PRIME);
		RESET(p, COVERED);

		continue;
	    }

	    /* Remove from overexpanded_cube any parts in INIT_LOWER */
	    if (nonsparse) {
		(void) set_diff(init_lower, INIT_LOWER, p);
		(void) set_diff(overexpanded_cube, overexpanded_cube, init_lower);
	    }

	    get_ROS1(p, overexpanded_cube, root);

	    /* If the blocking matrix is empty then p can be expanded to
	       its overexpanded cube */
	    if (ROS->count == 0) {
		(void) set_copy(p, overexpanded_cube);
		foreach_set(F, qlast, q)
		    if (setp_implies(q, p)) SET(q, COVERED);
		SET(p, PRIME);
		RESET(p, COVERED);

		continue;
	    }

	    (void) set_diff(init_lower, cube.fullset, overexpanded_cube);

	    /* expand the cube p, result is RAISE */
	    expand1(ROS, F, RAISE, FREESET, OVEREXPANDED_CUBE, SUPER_CUBE,
		init_lower, &num_covered, p);

	    if (debug & EXPAND)
		(void) 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);

    return F;
}

/*
 * Remove the cubes from T that wont affect the cube p being reduced.
 * These are the cubes that have atleast two variables in which T is
 * unate.
 */
void
rem_unnec_r_cubes(T)
pcube *T;

{

    pcube temp, temp1;
    pcube q, *T1;
    pcube *Tc, *Topen;
    int i;
    int temp_int, last;

    /* If the cubelist is empty or has only one cube, don't do anything */
    if ((T[2] == NULL) || (T[3] == NULL))
      return;

    temp = new_cube();
    temp1 = new_cube();

    (void) set_copy(temp, cube.fullset);

    /* "And" all the cubes together. */
    for (T1=T+2; (q = *T1++) != NULL;)
        (void) set_and(temp, temp, q);

    (void) set_or(temp, temp, T[0]);

    /* Find the non-unate and inactive binary variables. Set their values
       to all 1s in temp1. Set the unate binary variables to their complements.
       Set all mvs to all 1s */

    last = cube.last_word[cube.num_binary_vars-1];
    for (i=1; i<=last; i++) {
	temp_int = (temp[i] & (temp[i] >> 1)) | (~temp[i] & ((~temp[i]) >> 1));
	temp_int &= DISJOINT;
	temp1[i] = ~temp[i] | temp_int | (temp_int << 1);
    }
    (void) set_and(temp1, temp1, cube.fullset); /* Some problem with set_ord if I
					    don't do this */
    (void) set_or(temp1, temp1, cube.mv_mask);

    /* If temp1 has less than two zeros then no cubes will be removed so
       we might as well leave. */
    if (cube.size - set_ord(temp1) < 2) {
	free_cube(temp);
	free_cube(temp1);
	return;
    }

    /* Remove each cube q from the cubelist which has more than two 
       unate variables in it. All such cubes are distance two or more
       from temp1 */

    for (Tc=T+2; (q = *Tc++) != NULL;) {
	if (cdist01(temp1, q) >= 2)
	    break;
    }

    /* If there is no such cube in the cube list, return */
    if (q == NULL) {
	free_cube(temp);
	free_cube(temp1);
	return;
    }

    Topen = Tc - 1;

    while ((q = *Tc++) != NULL) {
	if (cdist01(temp1, q) < 2)
	    *Topen++ = q;
    }

    *Topen++ = (pcube) NULL;
    T[1] = (pcube) Topen;

    free_cube(temp);
    free_cube(temp1);

}