ros.c

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

    int left, right;

    mask = new_cube();
    temp = new_cube();

    /* Set up the mask */
    (void) set_diff(mask, cube.fullset, T[0]);
    set_remove(mask, 2*var);
    set_remove(mask, 2*var+1);

    /* Setup Tl and Tr */
    size = CUBELISTSIZE(T) + 5;

    Tleft = *Tl = ALLOC(pcube, size);
    Tright = *Tr = ALLOC(pcube, size);

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

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

    left = GETINPUT(cleft, var);
    right = GETINPUT(cright, var);

    /* Set Tc to the location of the first cube that can not be in both lists */
    Tc = T+2;
    while (((p = *Tc) != NULL) && (GETINPUT(p, var) == 3)) Tc++;

    /* Make one pass through T to remove cubes which can be in Tleft
       or Tright but not in both */

    Tlc = Tleft+2;
    Trc = Tright+2;

    for (T1=Tc; (p = *T1++) != NULL;) {
	value = GETINPUT(p, var);
	if (value == left) *Tlc++ = p;
	else if (value == right) *Trc++ = p;
	else *Tc++ = p;
    }

    *Tc = NULL;
    T[1] = (pcube) (Tc+1);
    Tld = Tlc;
    Trd = Trc;

    /* Make one more pass through the remaining cubes in T to copy
       them into Tleft and Tright provided they are not covered by
       any cube that was moved to Tleft or Tright in the first pass */

    for (T1 = T+2; (p = *T1++) != NULL;) { 

	(void) set_and(temp, mask, p);

        for (Ttmp=Tleft+2; Ttmp<Tld; Ttmp++)
	    if (setp_implies(temp, *Ttmp)) goto skipl;
	
	*Tlc++ = p;

    skipl:

        for (Ttmp=Tright+2; Ttmp<Trd; Ttmp++)
	    if (setp_implies(temp, *Ttmp)) goto skipr;
	
	*Trc++ = p;
    
    skipr:;

    }

    /* Wrap up and leave */
    *Tlc++ = NULL;
    *Trc++ = NULL;
    Tleft[1] = (pcube) Tlc;
    Tright[1] = (pcube) Trc;
    free_cube(mask);
    free_cube(temp);

}

/*
 * Make cofactor T minimum w.r.t single cube containment
 */

void
nc_cof_contain(T)
INOUT pcube *T;

{

    register pcube *Tc, *Topen, *Tp, c, p, temp = nc_tmp_cube[23];

    for (Tp = T+2; (p = *Tp++) != NULL;) {

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

	/* Find the first cube contained in temp other than p */
	for (Tc=T+2; (c = *Tc++) != NULL;) 
	    if (setp_implies(c, temp) && (p != c)) break;

	/* No cube is contained in p so go to the next cube
	   in the cubelist */
	if (c == NULL) continue;

	Topen = Tc - 1;
	while ((c = *Tc++) != NULL)
	    if ( p == c ) {
		Tp = Topen;
		*Topen++ = c;
	    }
	    else if (!setp_implies(c, temp)) *Topen++ = c;

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

    }

}

/*
 * Find if the cube p and q are distance zero away from each other
 * in variable var. If so return some non-zero integer, otherwise,
 * return zero.
 */

bool
cdist0v(p, q, var)
pcube p, q;
int var;

{

    int k, last_word;
    pcube mask;

    if (var < cube.num_binary_vars)
	return((GETINPUT(p, var)) & (GETINPUT(q, var)));

    last_word = cube.last_word[var];
    mask = cube.var_mask[var];
    for (k = cube.first_word[var]; k <= last_word; k++) {
	if (p[k] & q[k] & mask[k])
	    return(TRUE);
    }

    return(FALSE);

}

/*
 * Remove the cubes from T that don't contain the cube p. p is the node
 * to be expanded. All cubes in the unate leafs of the cofactors of T
 * that are derived from such cubes will not contain p and will be thrown
 * away if kept. Therefore, removing such cubes may decrease the paths to 
 * unate leafs.
 */

void
nc_rem_unnec_cubes(p, T)
pcube p;
pcube *T;

{

    pcube temp, temp1;
    pcube q, *T1;
    pcube *Tc, *Topen;
    int i, j, is_zero;
    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 variables.
       Set their values to all 0s in temp1 */

    /* Copy the binary part of p to temp1 */
    (void) set_and(temp1, p, cube.binary_mask);

    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_int | (temp_int << 1));
    }

    temp1[last] &= cube.binary_mask[last];

    /* insert unate parts in the unate variables */
    for (i=cube.num_binary_vars; i<cube.num_vars; i++) {
	is_zero = 0;
	for (j=cube.first_part[i]; j<=cube.last_part[i]; j++) {
	    if (!is_in_set(temp, j)) {
		if (is_zero) goto next_var;
		else is_zero = j+1;
	    }
	}
	if (is_zero) {
	    is_zero--;
	    if (is_in_set(p, is_zero))
		set_insert(temp1, is_zero);
	}
    next_var:;
    }

    /* If temp1 is contained in temp then for each cube q in the cofactor,
       q contains temp1. In this case no cubes will be removed */
    if (setp_implies(temp1, temp)) {
	free_cube(temp);
	free_cube(temp1);
	return;
    }

    /* Remove each cube q from the cubelist which does not contain temp1 */

    /* Find the first cube q such that q does not contain temp1 */
    for (Tc=T+2; (q = *Tc++) != NULL;) {
	if (!setp_implies(temp1, q))
	    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 (setp_implies(temp1, q)) *Topen++ = q;
    }

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

    free_cube(temp);
    free_cube(temp1);

}

/*
 * Form or of all the cubes that will not be removed by nc_rem_unnec
 * while expanding c.
 * If All the cubes in T are such that they will be droped by nc_rem_unnec
 * then set orred_cube to fullset.
 */

void
nc_or_unnec(c, T, orred_cube)
pcube c, *T, orred_cube;

{

    register pcube temp = nc_tmp_cube[26];
    register pcube *T1, p;
    register bool empty;

    (void) set_copy(orred_cube, T[0]);

    (void) set_diff(temp, cube.fullset, T[0]);
    (void) set_and(temp, temp, c);

    /* Loop for each cube in the list. Determine suitability and or */

    empty = TRUE;
    for (T1 = T+2; (p = *T1++) != NULL;)
	if (setp_implies(temp, p)) {
	    (void) set_or(orred_cube, orred_cube, p);
            empty = FALSE;
        }

    if (empty)
	(void) set_copy(orred_cube, cube.fullset);
}

/*
 * Find if there is a cube in T that will not be removed by nc_copy_unnec
 * while expanding c. If so, return TRUE, else return FALSE.
 */

bool
nc_is_nec(c, T)
pcube c, *T;

{

    register pcube *T1, p, temp = nc_tmp_cube[27];

    (void) set_diff(temp, cube.fullset, T[0]);
    (void) set_and(temp, temp, c);

    /* Loop for each cube in the list. Return TRUE if the cube qualifies */

    for (T1 = T+2; (p = *T1++) != NULL;)
	if (setp_implies(temp, p)) {
	    return(TRUE);
	}

    return(FALSE);

}

/*
 * Multiply a set_family by a single variable cube.
 */

void
nc_sf_multiply(A, c, var)
pset_family A;
pcube c;
int var;

{

    pcube p, last, temp;
    int fword, lword, i;

    temp = new_cube();
    (void) set_diff(temp, cube.fullset, cube.var_mask[var]);
    (void) set_or(temp, temp, c);

    fword = cube.first_word[var];
    lword = cube.last_word[var];

    foreach_set(A, last, p)
	for (i=fword; i<= lword; i++) p[i] &= temp[i];

    free_cube(temp);

}

/*
 * Remove all the cubes from T that don't contain p.
 */

void
nc_rem_noncov_cubes(p, T)
pcube p, *T;

{

    pcube temp, q;
    pcube *Tc, *Topen;

    temp = new_cube();

    /* Remove each cube q from the cubelist which does not contain p */

    /* Knock out variables that have been cofactored out */
    (void) set_diff(temp, p, T[0]);

    /* Find the first cube q such that q does not contain temp */
    for (Tc=T+2; (q = *Tc++) != NULL;) {
	if (!setp_implies(temp, q))
	    break;
    }

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

    /* Go through the rest of the cubelist, saving those cubes
       that contain temp */
    Topen = Tc - 1;
    while ((q = *Tc++) != NULL) {
	if (setp_implies(temp, q)) *Topen++ = q;
    }

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

    free_cube(temp);

}

/*
 * nc_compl_special_cases is to be called only when the cubelist
 * T is known to have only one cube or is known to be unate.
 * max_lit is the number of maximum literals allowed in any cube in
 * the complement.
 */
void
nc_compl_special_cases(T, Tbar)
pcube *T;			/* will be disposed if answer is determined */
pcover *Tbar;			/* returned only if answer determined */

{
    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);
	nc_compl_special_cases(T, Tbar);
	*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 = unate_compl(A);
	*Tbar = map_unate_to_cover(A);
	sf_free(A);
	return;
    }

}

/*
 * Copy cubelist T. Return the copy.
 */
pcube *
nc_copy_cubelist(T)
pcube *T;

{

    pcube *Tc, *Tc_save;
    register pcube p, *T1;
    int listlen;

    listlen = CUBELISTSIZE(T) + 5;

    /* Allocate a new list of cube pointers (max size is previous size) */
    Tc_save = Tc = ALLOC(pcube, listlen);

    /* pass on which variables have been cofactored against */
    *Tc++ = set_copy(new_cube(), T[0]);
    Tc++;

    /* Loop for each cube in the list and save */
    for(T1 = T+2; (p = *T1++) != NULL; ) *Tc++ = p;

    *Tc++ = (pcube) NULL;                       /* sentinel */
    Tc_save[1] = (pcube) Tc;                    /* save pointer to last */
    return Tc_save;
}

/*
 * Assign memory to temporary cubes to be used in subroutines in
 * this file.
 */

void
nc_setup_tmp_cubes(num)
int num;

{
 
    int i;

    nc_tmp_cube = ALLOC(pcube, num);

    for (i=0; i<num; i++)
	nc_tmp_cube[i] = new_cube();
}

/*
 * Free memory assigned to the temporary cubes to be used in subroutines
 * in this file.
 */

void
nc_free_tmp_cubes(num)
int num;

{

    int i;

    for (i=0; i<num; i++)
	free_cube(nc_tmp_cube[i]);
    
    FREE(nc_tmp_cube);
}