cuddutil.c

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

  otherwise.]

  SideEffects [None]

  SeeAlso     [Cudd_VectorSupport Cudd_SupportSize]

******************************************************************************/
int
Cudd_VectorSupportSize(
  DdManager * dd /* manager */,
  DdNode ** F /* array of DDs whose support is sought */,
  int  n /* size of the array */)
{
    int	*support;
    int	i;
    int size;
    int count;

    /* Allocate and initialize support array for ddSupportStep. */
    size = ddMax(dd->size, dd->sizeZ);
    support = ALLOC(int,size);
    if (support == NULL) {
	dd->errorCode = CUDD_MEMORY_OUT;
	return(CUDD_OUT_OF_MEM);
    }
    for (i = 0; i < size; i++) {
	support[i] = 0;
    }

    /* Compute support and clean up markers. */
    for (i = 0; i < n; i++) {
	ddSupportStep(Cudd_Regular(F[i]),support);
    }
    for (i = 0; i < n; i++) {
	ddClearFlag(Cudd_Regular(F[i]));
    }

    /* Count vriables in support. */
    count = 0;
    for (i = 0; i < size; i++) {
	if (support[i] == 1) count++;
    }

    FREE(support);
    return(count);

} /* end of Cudd_VectorSupportSize */


/**Function********************************************************************

  Synopsis    [Classifies the variables in the support of two DDs.]

  Description [Classifies the variables in the support of two DDs
  <code>f</code> and <code>g</code>, depending on whther they appear
  in both DDs, only in <code>f</code>, or only in <code>g</code>.
  Returns 1 if successful; 0 otherwise.]

  SideEffects [The cubes of the three classes of variables are
  returned as side effects.]

  SeeAlso     [Cudd_Support Cudd_VectorSupport]

******************************************************************************/
int
Cudd_ClassifySupport(
  DdManager * dd /* manager */,
  DdNode * f /* first DD */,
  DdNode * g /* second DD */,
  DdNode ** common /* cube of shared variables */,
  DdNode ** onlyF /* cube of variables only in f */,
  DdNode ** onlyG /* cube of variables only in g */)
{
    int	*supportF, *supportG;
    DdNode *tmp, *var;
    int	i,j;
    int size;

    /* Allocate and initialize support arrays for ddSupportStep. */
    size = ddMax(dd->size, dd->sizeZ);
    supportF = ALLOC(int,size);
    if (supportF == NULL) {
	dd->errorCode = CUDD_MEMORY_OUT;
	return(0);
    }
    supportG = ALLOC(int,size);
    if (supportG == NULL) {
	dd->errorCode = CUDD_MEMORY_OUT;
	FREE(supportF);
	return(0);
    }
    for (i = 0; i < size; i++) {
	supportF[i] = 0;
	supportG[i] = 0;
    }

    /* Compute supports and clean up markers. */
    ddSupportStep(Cudd_Regular(f),supportF);
    ddClearFlag(Cudd_Regular(f));
    ddSupportStep(Cudd_Regular(g),supportG);
    ddClearFlag(Cudd_Regular(g));

    /* Classify variables and create cubes. */
    *common = *onlyF = *onlyG = DD_ONE(dd);
    cuddRef(*common); cuddRef(*onlyF); cuddRef(*onlyG);
    for (j = size - 1; j >= 0; j--) { /* for each level bottom-up */
	i = (j >= dd->size) ? j : dd->invperm[j];
	if (supportF[i] == 0 && supportG[i] == 0) continue;
	var = cuddUniqueInter(dd,i,dd->one,Cudd_Not(dd->one));
	cuddRef(var);
	if (supportG[i] == 0) {
	    tmp = Cudd_bddAnd(dd,*onlyF,var);
	    if (tmp == NULL) {
		Cudd_RecursiveDeref(dd,*common);
		Cudd_RecursiveDeref(dd,*onlyF);
		Cudd_RecursiveDeref(dd,*onlyG);
		Cudd_RecursiveDeref(dd,var);
		FREE(supportF); FREE(supportG);
		return(0);
	    }
	    cuddRef(tmp);
	    Cudd_RecursiveDeref(dd,*onlyF);
	    *onlyF = tmp;
	} else if (supportF[i] == 0) {
	    tmp = Cudd_bddAnd(dd,*onlyG,var);
	    if (tmp == NULL) {
		Cudd_RecursiveDeref(dd,*common);
		Cudd_RecursiveDeref(dd,*onlyF);
		Cudd_RecursiveDeref(dd,*onlyG);
		Cudd_RecursiveDeref(dd,var);
		FREE(supportF); FREE(supportG);
		return(0);
	    }
	    cuddRef(tmp);
	    Cudd_RecursiveDeref(dd,*onlyG);
	    *onlyG = tmp;
	} else {
	    tmp = Cudd_bddAnd(dd,*common,var);
	    if (tmp == NULL) {
		Cudd_RecursiveDeref(dd,*common);
		Cudd_RecursiveDeref(dd,*onlyF);
		Cudd_RecursiveDeref(dd,*onlyG);
		Cudd_RecursiveDeref(dd,var);
		FREE(supportF); FREE(supportG);
		return(0);
	    }
	    cuddRef(tmp);
	    Cudd_RecursiveDeref(dd,*common);
	    *common = tmp;
	}
	Cudd_RecursiveDeref(dd,var);
    }

    FREE(supportF); FREE(supportG);
    cuddDeref(*common); cuddDeref(*onlyF); cuddDeref(*onlyG);
    return(1);

} /* end of Cudd_ClassifySupport */


/**Function********************************************************************

  Synopsis    [Counts the number of leaves in a DD.]

  Description [Counts the number of leaves in a DD. Returns the number
  of leaves in the DD rooted at node if successful; CUDD_OUT_OF_MEM
  otherwise.]

  SideEffects [None]

  SeeAlso     [Cudd_PrintDebug]

******************************************************************************/
int
Cudd_CountLeaves(
  DdNode * node)
{
    int	i;	

    i = ddLeavesInt(Cudd_Regular(node));
    ddClearFlag(Cudd_Regular(node));
    return(i);

} /* end of Cudd_CountLeaves */


/**Function********************************************************************

  Synopsis    [Picks one on-set cube randomly from the given DD.]

  Description [Picks one on-set cube randomly from the given DD. The
  cube is written into an array of characters.  The array must have at
  least as many entries as there are variables. Returns 1 if
  successful; 0 otherwise.]

  SideEffects [None]

  SeeAlso     [Cudd_bddPickOneMinterm]

******************************************************************************/
int
Cudd_bddPickOneCube(
  DdManager * ddm,
  DdNode * node,
  char * string)
{
    DdNode *N, *T, *E;
    DdNode *one, *bzero;
    char   dir;
    int    i;

    if (string == NULL || node == NULL) return(0);

    /* The constant 0 function has no on-set cubes. */
    one = DD_ONE(ddm);
    bzero = Cudd_Not(one);
    if (node == bzero) return(0);

    for (i = 0; i < ddm->size; i++) string[i] = 2;

    for (;;) {

	if (node == one) break;

	N = Cudd_Regular(node);

	T = cuddT(N); E = cuddE(N);
	if (Cudd_IsComplement(node)) {
	    T = Cudd_Not(T); E = Cudd_Not(E);
	}
	if (T == bzero) {
	    string[N->index] = 0;
	    node = E;
	} else if (E == bzero) {
	    string[N->index] = 1;
	    node = T;
	} else {
	    dir = (char) ((Cudd_Random() & 0x2000) >> 13);
	    string[N->index] = dir;
	    node = dir ? T : E;
	}
    }
    return(1);

} /* end of Cudd_bddPickOneCube */


/**Function********************************************************************

  Synopsis    [Picks one on-set minterm randomly from the given DD.]

  Description [Picks one on-set minterm randomly from the given
  DD. The minterm is in terms of <code>vars</code>. The array
  <code>vars</code> should contain at least all variables in the
  support of <code>f</code>; if this condition is not met the minterm
  built by this procedure may not be contained in
  <code>f</code>. Builds a BDD for the minterm and returns a pointer
  to it if successful; NULL otherwise. There are three reasons why the
  procedure may fail:
  <ul>
  <li> It may run out of memory;
  <li> the function <code>f</code> may be the constant 0;
  <li> the minterm may not be contained in <code>f</code>.
  </ul>]

  SideEffects [None]

  SeeAlso     [Cudd_bddPickOneCube]

******************************************************************************/
DdNode *
Cudd_bddPickOneMinterm(
  DdManager * dd /* manager */,
  DdNode * f /* function from which to pick one minterm */,
  DdNode ** vars /* array of variables */,
  int  n /* size of <code>vars</code> */)
{
    char *string;
    int i, size;
    int *indices;
    int result;
    DdNode *old, *neW;

    size = dd->size;
    string = ALLOC(char, size);
    if (string == NULL) {
	dd->errorCode = CUDD_MEMORY_OUT;
	return(NULL);
    }
    indices = ALLOC(int,n);
    if (indices == NULL) {
	dd->errorCode = CUDD_MEMORY_OUT;
	FREE(string);
	return(NULL);
    }

    for (i = 0; i < n; i++) {
        indices[i] = vars[i]->index;
    }

    result = Cudd_bddPickOneCube(dd,f,string);
    if (result == 0) {
	FREE(string);
	FREE(indices);
	return(NULL);
    }

    /* Randomize choice for don't cares. */
    for (i = 0; i < n; i++) {
	if (string[indices[i]] == 2) 
	    string[indices[i]] = (char) ((Cudd_Random() & 0x20) >> 5);
    }

    /* Build result BDD. */
    old = Cudd_ReadOne(dd);
    cuddRef(old);

    for (i = n-1; i >= 0; i--) {
	neW = Cudd_bddAnd(dd,old,Cudd_NotCond(vars[i],string[indices[i]]==0));
	if (neW == NULL) {
	    FREE(string);
	    FREE(indices);
	    Cudd_RecursiveDeref(dd,old);
	    return(NULL);
	}
	cuddRef(neW);
	Cudd_RecursiveDeref(dd,old);
	old = neW;
    }

#ifdef DD_DEBUG
    /* Test. */
    if (Cudd_bddLeq(dd,old,f)) {
	cuddDeref(old);
    } else {
	Cudd_RecursiveDeref(dd,old);
	old = NULL;
    }
#else
    cuddDeref(old);
#endif

    FREE(string);
    FREE(indices);
    return(old);

}  /* end of Cudd_bddPickOneMinterm */


/**Function********************************************************************

  Synopsis    [Picks k on-set minterms evenly distributed from given DD.]

  Description [Picks k on-set minterms evenly distributed from given DD.
  The minterms are in terms of <code>vars</code>. The array
  <code>vars</code> should contain at least all variables in the
  support of <code>f</code>; if this condition is not met the minterms
  built by this procedure may not be contained in
  <code>f</code>. Builds an array of BDDs for the minterms and returns a
  pointer to it if successful; NULL otherwise. There are three reasons
  why the procedure may fail:
  <ul>
  <li> It may run out of memory;
  <li> the function <code>f</code> may be the constant 0;
  <li> the minterms may not be contained in <code>f</code>.
  </ul>]

  SideEffects [None]

  SeeAlso     [Cudd_bddPickOneMinterm Cudd_bddPickOneCube]

******************************************************************************/
DdNode **
Cudd_bddPickArbitraryMinterms(
  DdManager * dd /* manager */,
  DdNode * f /* function from which to pick k minterms */,
  DdNode ** vars /* array of variables */,
  int  n /* size of <code>vars</code> */,
  int  k /* number of minterms to find */)
{
    char **string;
    int i, j, l, size;
    int *indices;
    int result;
    DdNode **old, *neW;
    double minterms;
    char *saveString;
    int saveFlag, savePoint, isSame;

    minterms = Cudd_CountMinterm(dd,f,n);
    if ((double)k > minterms) {
	return(NULL);
    }

    size = dd->size;
    string = ALLOC(char *, k);
    if (string == NULL) {
	dd->errorCode = CUDD_MEMORY_OUT;
	return(NULL);
    }
    for (i = 0; i < k; i++) {
	string[i] = ALLOC(char, size + 1);
	if (string[i] == NULL) {
	    for (j = 0; j < i; j++)
		FREE(string[i]);
	    FREE(string);
	    dd->errorCode = CUDD_MEMORY_OUT;
	    return(NULL);
	}
	for (j = 0; j < size; j++) string[i][j] = '2';
	string[i][size] = '\0';
    }
    indices = ALLOC(int,n);
    if (indices == NULL) {
	dd->errorCode = CUDD_MEMORY_OUT;
	for (i = 0; i < k; i++)
	    FREE(string[i]);
	FREE(string);
	return(NULL);
    }

    for (i = 0; i < n; i++) {
        indices[i] = vars[i]->index;
    }

    result = ddPickArbitraryMinterms(dd,f,n,k,string);
    if (result == 0) {
	for (i = 0; i < k; i++)
	    FREE(string[i]);
	FREE(string);
	FREE(indices);
	return(NULL);
    }

    old = ALLOC(DdNode *, k);
    if (old == NULL) {
	dd->errorCode = CUDD_MEMORY_OUT;
	for (i = 0; i < k; i++)
	    FREE(string[i]);
	FREE(string);
	FREE(indices);
	return(NULL);
    }
    saveString = ALLOC(char, size + 1);
    if (saveString == NULL) {
	dd->errorCode = CUDD_MEMORY_OUT;
	for (i = 0; i < k; i++)
	    FREE(string[i]);
	FREE(string);
	FREE(indices);
	FREE(old);
	return(NULL);
    }
    saveFlag = 0;

    /* Build result BDD array. */
    for (i = 0; i < k; i++) {
	isSame = 0;
	if (!saveFlag) {
	    for (j = i + 1; j < k; j++) {
		if (strcmp(string[i], string[j]) == 0) {
		    savePoint = i;
		    strcpy(saveString, string[i]);
		    saveFlag = 1;
		    break;
		}
	    }
	} else {
	    if (strcmp(string[i], saveString) == 0) {
		isSame = 1;
	    } else {
		saveFlag = 0;
		for (j = i + 1; j < k; j++) {
		    if (strcmp(string[i], string[j]) == 0) {
			savePoint = i;
			strcpy(saveString, string[i]);
			saveFlag = 1;
			break;
		    }
		}
	    }
	}
	/* Randomize choice for don't cares. */
	for (j = 0; j < n; j++) {
	    if (string[i][indices[j]] == '2')
		string[i][indices[j]] = (Cudd_Random() & 0x20) ? '1' : '0';