minimize.c

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

	    Aprime->count++;
	    pdest += Aprime->wsize;
	}
    return Aprime;
}

/*
 * ncp_compl-special_cases is to be used only to complement unate functions
 * when the number of literals in the complement are to be restricted to
 * max_lit.
 */
void
ncp_compl_special_cases(T, Tbar, max_lit)
pcube *T;			/* will be disposed of */
pcover *Tbar;			/* returned only if answer determined */
int max_lit;

{
    register pcube *T1, p, ceil, cof=T[0];
    pcover A, ceil_compl;

    /* Check for no cubes in the cover */
    if (T[2] == NULL) {
	*Tbar = sf_addset(new_cover(1), cube.fullset);
	free_cubelist(T);
	return;
    }

    /* Check for only a single cube in the cover */
    if (T[3] == NULL) {
	*Tbar = nc_compl_cube(set_or(cof, cof, T[2]));
	free_cubelist(T);
	return;
    }

    /* Check for a row of all 1's (implies complement is null) */
    for(T1 = T+2; (p = *T1++) != NULL; ) {
	if (full_row(p, cof)) {
	    *Tbar = new_cover(0);
	    free_cubelist(T);
	    return;
	}
    }

    /* Check for a column of all 0's which can be factored out */
    ceil = set_save(cof);
    for(T1 = T+2; (p = *T1++) != NULL; ) {
	INLINEset_or(ceil, ceil, p);
    }
    if (! setp_equal(ceil, cube.fullset)) {
	ceil_compl = nc_compl_cube(ceil);
	(void) set_or(cof, cof, set_diff(ceil, cube.fullset, ceil));
	set_free(ceil);
	ncp_compl_special_cases(T, Tbar, max_lit);
	*Tbar = sf_append(*Tbar, ceil_compl);
	return;
    }
    set_free(ceil);

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

    /* If single active variable not factored out above, then tautology ! */
    if (cdata.vars_active == 1) {
	*Tbar = new_cover(0);
	free_cubelist(T);
	return;

    /* The cover is unate since all else failed */
    } else {
	A = map_cover_to_unate(T);
	free_cubelist(T);
	A = ncp_unate_compl(A, max_lit);
	*Tbar = map_unate_to_cover(A);
	sf_free(A);
	return;
    }

}

/* 
 * nc_super_gasp
 */

pcover
nc_super_gasp(F, D, cost)
pcover F, D;
cost_t *cost;
{
    pcover G, G1;

    EXECUTE(G = nc_reduce_gasp(F, D), GREDUCE_TIME, G, *cost);
    EXECUTE(G1 = nc_all_primes(G), 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;
}

/*
 *  nc_all_primes -- foreach cube in F, generate all of the primes
 *  which cover the cube.
 */

pcover
nc_all_primes(F)
pcover F;
{
    register pcube last, p, RAISE = nc_tmp_cube[24], FREESET = nc_tmp_cube[25];
    pcover Fall_primes, B1;

    Fall_primes = new_cover(F->count);

    foreach_set(F, last, p) {
	if (TESTP(p, PRIME)) {
	    Fall_primes = sf_addset(Fall_primes, p);
	} else {

	    /* Find the blocking matrix */
	    get_ROS1(p, cube.fullset, root);

	    /* Setup for call to essential parts */
	    (void) set_copy(RAISE, p);
	    (void) set_diff(FREESET, cube.fullset, RAISE);
	    setup_BB_CC(ROS, /* CC */ (pcover) NULL);
	    essen_parts(ROS, /* CC */ (pcover) NULL, RAISE, FREESET);

	    /* Find all of the primes, and add them to the prime set */
	    B1 = find_all_primes(ROS, RAISE, FREESET);
	    Fall_primes = sf_append(Fall_primes, B1);

	}
    }

    return Fall_primes;
}

/*
 * Similar to make_sparse except that the complete off_set is
 * not used.
 */

pcover
nc_make_sparse(F, D)
pcover F, D;
{
    cost_t cost, best_cost;

    cover_cost(F, &best_cost);

    do {
	EXECUTE(F = mv_reduce(F, D), MV_REDUCE_TIME, F, cost);
	if (cost.total == best_cost.total)
	    break;
	copy_cost(&cost, &best_cost);

	EXECUTE(F = ncp_expand(F, (pcover)NULL, TRUE), RAISE_IN_TIME, F, cost);
	if (cost.total == best_cost.total)
	    break;
	copy_cost(&cost, &best_cost);
    } while (force_irredundant);

    return F;
}

/*
 *  nc_expand_gasp -- similar to expand_gasp except complete
 *  off set is not used.
 *
 *  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
nc_expand_gasp(F, D, Foriginal)
INOUT pcover F;
IN pcover D;
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++) {
	nc_expand1_gasp(F, D, Foriginal, c1index, &G);
    }
    G = sf_dupl(G);
    G = ncp_expand(G, (pcover)NULL, /*nonsparse*/ FALSE);/* Make them prime ! */
    return G;
}

/*
 *  nc_expand1_gasp -- similar to expand1_gasp
 *
 *  Expand a single cube against the OFF-set, using the gasp strategy
 */
void
nc_expand1_gasp(F, D, Foriginal, c1index, G)
pcover F;		/* reduced cubes of ON-set */
pcover D;		/* DC-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 = nc_tmp_cube[28],
          FREESET = nc_tmp_cube[29],
	  temp = nc_tmp_cube[30];
    pcube *FD, c2essential;
    pcube new_lower = nc_tmp_cube[32];
    pcover F1;

    if (debug & EXPAND1) {
	(void) printf("\nEXPAND1_GASP:    \t%s\n", pc1(GETSET(F, c1index)));
    }

    /* Initialize the raising and unassigned sets */
    (void) set_copy(RAISE, GETSET(F, c1index));
    (void) set_diff(FREESET, cube.fullset, RAISE);

    ROS = get_ROS(c1index, F, (pcover) NULL);

    /* Initialize the Blocking Matrix */
    ROS->active_count = ROS->count;
    foreach_set(ROS, 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);
	}
    }

    /* Determine parts which must be lowered */
    essen_parts(ROS, F, RAISE, FREESET);

    /* Determine parts which can always be raised */
    essen_raising(ROS, 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(ROS, c2under, RAISE, new_lower)) {
		
		/* 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 = nc_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(ROS, c2essential, RAISE, new_lower)) {
		    (void) set_or(temp, RAISE, c2essential);
		    RESET(temp, PRIME);		/* cube not prime */
		    *G = sf_addset(*G, temp);
		}
		set_free(c2essential);
	    }
	}
    }

}

/*
 * nc_last_gasp
 */

pcover
nc_last_gasp(F, D, cost)
pcover F, D;
cost_t *cost;
{
    pcover G, G1;

    EXECUTE(G = nc_reduce_gasp(F, D), GREDUCE_TIME, G, *cost);
    EXECUTE(G1 = nc_expand_gasp(G, D, F), GEXPAND_TIME, G1, *cost);
    free_cover(G);
    EXECUTE(F = irred_gasp(F, D, G1), GIRRED_TIME, F, *cost);
    return F;
}

/*
 *  nc_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.
 */
pcover
nc_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 = nc_reduce_cube(FD, p);
	if (setp_empty(cunder)) {
	    fatal("empty reduction in nc_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) {
	    (void) printf("REDUCE_GASP: %s reduced to %s\n", pc1(p), pc2(cunder));
	}
	free_cube(cunder);
    }

    free_cubelist(FD);
    return G;
}

/*
 * This is similar to reduce, except that it returns pre-reduced
 * cubes in Fold in the same order that the reduced cubes are returned
 * in F.
 *
 * WARNING:
 *    variable toggle used in reduce is defined as a global
 * variable in reduce.c. The variable is not available here so it
 * has been declared as a global variable in this file and set to
 * TRUE. So long as toggle here and toggle in reduce.c have the same value,
 * The order in which cubes are reduced in the two subroutines will
 * be the same. Otherwise, the order will be different.
 */
pcover
nc_reduce(F, Fold, D)
INOUT pcover F;
OUT pcover *Fold;
IN pcover D;
{
    register pcube p, cunder, *FD;
    register index;
    bool inactive;

    /* Order the cubes */
    if (use_random_order)
	F = random_order(F);
    else {
	F = toggle ? sort_reduce(F) : mini_sort(F, descend);
	toggle = ! toggle;
    }

    *Fold = sf_save(F);

    inactive = FALSE;
    /* Try to reduce each cube */
    FD = cube2list(F, D);
    foreachi_set(F, index, p) {
	cunder = nc_reduce_cube(FD, p);		/* reduce the cube */
	if (setp_equal(cunder, p)) {            /* see if it actually did */
	    SET(p, ACTIVE);	/* cube remains active */
	    SET(p, PRIME);	/* cube remains prime ? */
	} else {
	    if (debug & REDUCE) {
		(void) printf("REDUCE: %s to %s %s\n",
		    pc1(p), pc2(cunder), print_time(ptime()));
	    }
	    (void) set_copy(p, cunder);                /* save reduced version */
	    RESET(p, PRIME);                    /* cube is no longer prime */
	    if (setp_empty(cunder)) {
		RESET(p, ACTIVE);               /* if null, kill the cube */
		inactive = TRUE;
	    }
	    else
		SET(p, ACTIVE);                 /* cube is active */
	}
	free_cube(cunder);
    }
    free_cubelist(FD);

    if (inactive) {

	/* Copy the flags from cubes in F to those in Fold */
	foreachi_set(F, index, p) {
            if TESTP(p, ACTIVE)
		SET(GETSET((*Fold), index), ACTIVE);
	    else
		RESET(GETSET((*Fold), index), ACTIVE);
	}

	/* Delete any cubes of F which reduced to the empty cube */
	F = sf_inactive(F);

	/* Also delete old cubes corresponding to the deleted cubes from F */
	*Fold = sf_inactive(*Fold);

    }

    return F;

}

/*
 * Similar to random_order except that it changes the order of cubes in
 * Fold so that the ith cube in Fold is the ith cube in F before reduce.
 */

pcover
nc_random_order(F, Fold)
register pcover F, Fold;
{
    pset temp;
    register int i, k;
#ifdef RANDOM
    long random();
#endif

    temp = set_new(F->sf_size);
    for(i = F->count - 1; i > 0; i--) {
	/* Choose a random number between 0 and i */
#ifdef RANDOM
	k = random() % i;
#else
	/* this is not meant to be really used; just provides an easy
	   "out" if random() and srandom() aren't around
	*/
	k = (i*23 + 997) % i;
#endif
	/* swap sets i and k in F */
	(void) set_copy(temp, GETSET(F, k));
	(void) set_copy(GETSET(F, k), GETSET(F, i));
	(void) set_copy(GETSET(F, i), temp);

	/* swap sets i and k in Fold */
	(void) set_copy(temp, GETSET(Fold, k));
	(void) set_copy(GETSET(Fold, k), GETSET(Fold, i));
	(void) set_copy(GETSET(Fold, i), temp);
    }
    set_free(temp);
    return F;
}

/*
 * The cubes in F1 are permuted in T1 (e.g the first cube in F1 may
 * be in T1[5]).  This subroutine returns a cover G that has the cubes
 * of F2 permuted in the same way as the cubes of F1 are in T1.
 */

pcover
nc_permute(F1, T1, F2)
pcover F1;
pcube *T1;
pcover F2;

{

    pcover G;
    pcube *T;
    int count, diff, i;

    count = F1->count;
    T = ALLOC(pcube, count+1);
    diff = (F2->data) - (F1->data);

    for (i=0; i<count; i++)
	T[i] = T1[i] + diff;
    T[count] = (pcube) NULL;
    
    G = sf_unlist(T, count, cube.size);
    sf_free(F2);

    return(G);

}

/* 
 * nc_mini_sort -- sort cubes according to the heuristics of mini
 * Put cube in G in the same order as the new order for the cubes
 * in F.
 */
pcover
nc_mini_sort(F, G, compare)
pcover F;
pcover *G;
int (*compare)();
{
    register int *count, cnt, n = cube.size, i;
    register pcube p, last;
    pcover F_sorted;
    pcube *F1;

    /* Perform a column sum over the set family */
    count = sf_count(F);

    /* weight is "inner product of the cube and the column sums" */
    foreach_set(F, last, p) {
	cnt = 0;
	for(i = 0; i < n; i++)
	    if (is_in_set(p, i))
		cnt += count[i];
	PUTSIZE(p, cnt);
    }
    FREE(count);

    /* use qsort to sort the array */
    qsort((char *) (F1 = sf_list(F)), F->count, sizeof(pcube), compare);
    *G = nc_permute(F, F1, *G);