ros.c

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

	    free_cube(temp);
	}

    }

    if (pNode->cubelist != NULL) { /* A leaf */

	/* Remove those cubes from the cover that don't contain p */
	if (level < Max_level) { /* A unate leaf */

	    T = nc_copy_cubelist(pNode->cubelist);
	    nc_rem_noncov_cubes(p, T);

	    if (T[2] == (pcube) NULL) { /* Empty cubelist. Compl is tautology */
		is_taut = TRUE;
		*BB = sf_addset(new_cover(1), cube.fullset);
		free_cubelist(T);
		return(TRUE);
	    }

	    else {
		is_taut = FALSE;
	    }

	    temp = new_cube();
	    (void) set_or(T[0], T[0], set_diff(temp, cube.fullset, overexpanded_cube));

	    nc_compl_special_cases(T, BB);

	    free_cube(temp);
	    return(TRUE);
	
	}
	else { /* The leaf is not necessarily unate. Switch to dynamic mode */

	    temp = set_diff(new_cube(), cube.fullset, pNode->cubelist[0]);

	    /* If all variables in overexpanded_cube have been cofactored out
	       then cofactoring will not gain anything. The test below is
	       sufficient because the cofactoring cube is dist 0 from 
	       overexpanded cube. */

	    if (setp_implies(temp, overexpanded_cube)) {
		free_cube(temp);
		T = nc_copy_cubelist(pNode->cubelist);
		*BB = setupBB_dyn(p, overexpanded_cube, T, level+1);
	    }
	    else {
		free_cube(temp);
		T = cofactor(pNode->cubelist, overexpanded_cube);
		*BB = setupBB_dyn(p, overexpanded_cube, T, level+1);
	    }

	    return(TRUE);

	}

    }

    return(FALSE);

}

/*
 * Get the overexpanded cube.
 * 
 * This subroutine uses global variable root.
 */

void
get_OC(p, overexpanded_cube, old_cube)
pcube p, overexpanded_cube, old_cube;

{


    long t;

    if (trace) {
	t = ptime();
    }
	
    if (old_cube == (pcube) NULL) {
	(void) set_copy(overexpanded_cube, cube.fullset);
	find_overexpanded_cube(p, overexpanded_cube, root,
						    (pcube) NULL, 0, 0, 1);
    } else {

	/* Temporarily remove all the parts from overexpanded cube
	   present in the cube before reduce. These parts cannot
	   be in the overexpanded cube. They are put in the overexpanded
	   cube to speed up its computation */

	(void) set_diff(overexpanded_cube, cube.fullset, old_cube);
	(void) set_or(overexpanded_cube, overexpanded_cube, p);

	find_overexpanded_cube(p, overexpanded_cube, root,
						    (pcube) NULL, 0, 0, 1);

	/* Put back the parts into overexpanded cube that were 
	   temporarily removed from it */

	(void) set_or(overexpanded_cube, overexpanded_cube, old_cube);

    }

    if (trace) {
	OC_time = ptime() - t;
	OC_count++;
    }

}

/*
 * Partition the cubelist in two parts such that no-nonunate variables are
 * shared. If such a partition exist, find reduced offset for each part
 * and multiply the two reduced offsets.
 */
bool
partition_ROS(p, overexpanded_cube, level, T, R)
pcube p, overexpanded_cube;
int level;
pcube *T;
pcover *R;

{

    pcube temp, temp1, cof;
    pcube q, *T1;
    pcube *A, *B;
    pcover RA, RB;
    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(FALSE);

    temp = new_cube();
    temp1 = new_cube();
    cof = 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 0s in temp1. Set all mvs to all 0s */

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

    /* Mask out the unate variables by fixing T[0]. */
    (void) set_copy(cof, T[0]); /* Save T[0] in cof */
    (void) set_or(T[0], T[0], set_diff(temp, cube.fullset, temp1));

    /* Partition T. */
    if (!nc_cubelist_partition(T, &A, &B, FALSE)) {
	(void) set_copy(T[0], cof);
	free_cube(temp);
	free_cube(temp1);
	free_cube(cof);
	return(FALSE);
    }

    /* Free T */
    free_cubelist(T);

    /* Restore the cofactoring cube */
    (void) set_copy(A[0], cof);
    (void) set_copy(B[0], cof);

    /* Find reduced offsets for A and B */
    RA = setupBB_dyn(p, overexpanded_cube, A, level);

    if (RA->count == 0) { /* The product of RA and RB will be Null */
	*R = RA;
	free_cubelist(B);
	is_taut = FALSE;
    } else if (is_taut) { /* No need to multiply RA and RB */
	*R = setupBB_dyn(p, overexpanded_cube, B, level);
	sf_free(RA);
    } else {
	RB = setupBB_dyn(p, overexpanded_cube, B, level);
	/* Multiply A and B together */
	*R = multiply2_sf(RA, RB);
	is_taut = FALSE;
    }

    free_cube(temp);
    free_cube(temp1);
    free_cube(cof);
    return(TRUE);

}

/*
 * multiply2_sf -- multiply two set families. Return the result.
 * Assume that no cube in one set family is orthagonal to any one in
 * the other set family.
 */

pcover
multiply2_sf(A, B)
pcover A, B; /* Disposes of A and B */

{

    pcover C, R;
    pcube pA, pB, lastA, lastB;

    /* If either A or B is Null, the product is Null */
    if (A->count == 0) {
	sf_free(B);
	return(A);
    }

    if (B->count == 0) {
       sf_free(A);
       return(B);
    }

    A = sf_contain(A);
    B = sf_contain(B);

    /* If B->count is less than A->count, swap A and B */
    if (B->count < A->count) {
	C = A;
	A = B;
	B = C;
    }

    if (A->sf_size != B->sf_size)
      fatal("multiply2_sf: sf_size mismatch");

    R = sf_new(A->count * B->count, A->sf_size);

    /* Multiply them together */

    foreach_set(A, lastA, pA)
        foreach_set(B, lastB, pB)
            set_and(GETSET(R, R->count++), pB, pA);
    R->active_count = A->active_count * B->active_count;

    sf_free(A);
    sf_free(B);

    return(R);

}
/*
 *  cubelist_partition -- take a cubelist T and see if it has any components;
 *  if so, return cubelist's of the two partitions A and B; the return value
 *  is the size of the partition; if not, A and B
 *  are undefined and the return value is 0
 */

int
nc_cubelist_partition(T, A, B, comp_debug)
pcube *T;			/* a list of cubes */
pcube **A, **B;			/* cubelist of partition and remainder */
unsigned int comp_debug;
{
    register pcube *T1, p, seed, cof;
    pcube *A1, *B1;
    bool change;
    int count, numcube;

    numcube = CUBELISTSIZE(T);

    /* Mark all cubes -- covered cubes belong to the partition */
    for(T1 = T+2; (p = *T1++) != NULL; ) {
	RESET(p, COVERED);
    }

    /* Pick a seed that is not a row of all 1s */
    seed = new_cube();
    for (T1 = T+2; (p = *T1++) != NULL; ) {
	(void) set_or(seed, p, T[0]);
	if (!setp_equal(seed, cube.fullset)) {
	    (void) set_copy(seed, p);
	    SET(p, COVERED);
	    break;
	}
    }

    /*
     *  Extract a partition from the cubelist T; start with the first cube as a
     *  seed, and then pull in all cubes which share a variable with the seed;
     *  iterate until no new cubes are brought into the partition.
     */

    cof = T[0];
    count = 1;

    do {
	change = FALSE;
	for(T1 = T+2; (p = *T1++) != NULL; ) {
	    if (! TESTP(p, COVERED) && ccommon(p, seed, cof)) {
		INLINEset_and(seed, seed, p);
		SET(p, COVERED);
		change = TRUE;
		count++;
	    }
	
	}
    } while (change);

    set_free(seed);

    if (comp_debug) {
	(void) printf("COMPONENT_REDUCTION: split into %d %d\n",
	    count, numcube - count);
    }

    if (count != numcube) {
	/* Allocate and setup the cubelist's for the two partitions */
	*A = A1 = ALLOC(pcube, numcube+3);
	*B = B1 = ALLOC(pcube, numcube+3);
	(*A)[0] = set_save(T[0]);
	(*B)[0] = set_save(T[0]);
	A1 = *A + 2;
	B1 = *B + 2;

	/* Loop over the cubes in T and distribute to A and B */
	for(T1 = T+2; (p = *T1++) != NULL; ) {
	    if (TESTP(p, COVERED)) {
		*A1++ = p;
	    } else {
		*B1++ = p;
	    }
	}

	/* Stuff needed at the end of the cubelist's */
	*A1++ = NULL;
	(*A)[1] = (pcube) A1;
	*B1++ = NULL;
	(*B)[1] = (pcube) B1;
    }

    /* Mark all the cubes non-covered */
    for(T1 = T+2; (p = *T1++) != NULL; ) {
	RESET(p, COVERED);
    }

    return numcube - count;
}

/*
 * This routine recursively generates unate cofactors of T.
 * The cofactors are stored at the leafs.
 */

void
nc_generate_cof_tree(pNode, T, level)
pnc_node pNode;
pcube *T;
int level;

{

    register pcube cl, cr;
    register int best;
    pcube *Tl, *Tr;

    /* If the level is not less than Max_level, store the cubelist and leave. */
    if (level == Max_level) {
	pNode->cubelist = T;
	pNode->cof = T[0];
	return;
    }

    /* Check for empty cubelist */
    if (T[2] == NULL) {
	pNode->cubelist = T;
	pNode->cof = T[0];
	return;
    }

    /* Check for only a single cube in the cover */
    if (T[3] == NULL) {
	pNode->cubelist = T;
	pNode->cof = T[0];
	return;
    }

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

    /* Check for unate cover */
    if (cdata.vars_unate == cdata.vars_active) { /* T is unate */
	pNode->cubelist = T;
	pNode->cof = T[0];
	return;
    }

    /* Store the cofactoring cube */
    pNode->cof = set_copy(new_cube(), T[0]);


    /* Allocate space for the partition cubes */
    cl = new_cube();
    cr = new_cube();

    best = binate_split_select(T, cl, cr, COMPL);

    if (best < cube.num_binary_vars) {
	nc_bin_cof(T, &Tl, &Tr, cl, cr, best);
    }
    else {
	Tl = scofactor(T, cl, best);
	nc_cof_contain(Tl);
	Tr = scofactor(T, cr, best);
	nc_cof_contain(Tr);
    }

    free_cubelist(T);
	
    /* Save the splitting variable */
    pNode->var = best;

    /* Allocate space for the children of *pNode */
    pNode->child[RIGHT] = ALLOC(nc_node_t, 1);
    pNode->child[LEFT] = ALLOC(nc_node_t, 1);

    /* Store the partition cubes */
    pNode->part_cube[LEFT] = cl;
    pNode->part_cube[RIGHT] = cr;

    /* Just to be suer that the cubelist pointer is NULL */
    pNode->cubelist = NULL;

    /* Generate cofactoring tree recursively at the children */
    nc_generate_cof_tree(pNode->child[LEFT], Tl, level+1);
    nc_generate_cof_tree(pNode->child[RIGHT], Tr, level+1);

    return;

}

/* 
 * nc_compl_cube -- return the complement of a single cube (De Morgan's law)
 */
pcover
nc_compl_cube(p)
register pcube p;
{
    register pcube diff=cube.temp[7], pdest, mask, full=cube.fullset;
    int var;
    pcover R;

    /* Allocate worst-case size cover (to avoid checking overflow) */
    R = new_cover(cube.num_vars);

    /* Compute bit-wise complement of the cube */
    INLINEset_diff(diff, full, p);

    for(var = 0; var < cube.num_vars; var++) {
	mask = cube.var_mask[var];
	/* If the bit-wise complement is not empty in var ... */
	if (! setp_disjoint(diff, mask)) {
	    pdest = GETSET(R, R->count++);
	    INLINEset_merge(pdest, diff, full, mask);
	}
    }
    return R;
}

/*
 * Free the unate tree.
 */

void
nc_free_unate_tree(pNode)
pnc_node pNode;

{

    if (pNode->cubelist == NULL) { /* Not a leaf */

	/* Free the left and right subtrees */
	nc_free_unate_tree(pNode->child[LEFT]);
	nc_free_unate_tree(pNode->child[RIGHT]);

	/* Free all the partition cubes at this node */
	free_cube(pNode->part_cube[LEFT]);
	free_cube(pNode->part_cube[RIGHT]);
	free_cube(pNode->cof);

    }

    else {  /* A leaf of the tree */

	/* Free the cubelist */
	free_cubelist(pNode->cubelist);

    }

    /* Free the node itself */
    FREE(pNode);

}

/*
 * Cofactor the given cubelist T with respect to the binary
 * variable var.
 *
 * The resulting cubelists should be minimum with respect to single
 * cube containment assuming that T is minimum w.r.t single cube containment.
 */

void
nc_bin_cof(T, Tl, Tr, cleft, cright, var)
pcube *T, **Tl, **Tr;
pcube cleft, cright;
int var;

{

    pcube *T1, *Tc, *Tlc, *Trc, *Tld, *Trd, *Ttmp;
    pcube *Tleft, *Tright;
    pcube p, mask, temp;
    int size, value;