cuddpriority.c

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

    /* Loop to build the rest of the BDD. */
    for (i = N-2; i >= 0; i--) {
	z1 = Cudd_bddIte(dd, z[i], one, Cudd_Not(x1));
	if (z1 == NULL) {
	    Cudd_RecursiveDeref(dd, x1);
	    return(NULL);
	}
	cuddRef(z1);
	z2 = Cudd_bddIte(dd, z[i], x1, one);
	if (z2 == NULL) {
	    Cudd_RecursiveDeref(dd, x1);
	    Cudd_RecursiveDeref(dd, z1);
	    return(NULL);
	}
	cuddRef(z2);
	z3 = Cudd_bddIte(dd, z[i], one, x1);
	if (z3 == NULL) {
	    Cudd_RecursiveDeref(dd, x1);
	    Cudd_RecursiveDeref(dd, z1);
	    Cudd_RecursiveDeref(dd, z2);
	    return(NULL);
	}
	cuddRef(z3);
	z4 = Cudd_bddIte(dd, z[i], x1, zero);
	if (z4 == NULL) {
	    Cudd_RecursiveDeref(dd, x1);
	    Cudd_RecursiveDeref(dd, z1);
	    Cudd_RecursiveDeref(dd, z2);
	    Cudd_RecursiveDeref(dd, z3);
	    return(NULL);
	}
	cuddRef(z4);
	Cudd_RecursiveDeref(dd, x1);
	y1_ = Cudd_bddIte(dd, y[i], z2, Cudd_Not(z1));
	if (y1_ == NULL) {
	    Cudd_RecursiveDeref(dd, z1);
	    Cudd_RecursiveDeref(dd, z2);
	    Cudd_RecursiveDeref(dd, z3);
	    Cudd_RecursiveDeref(dd, z4);
	    return(NULL);
	}
	cuddRef(y1_);
	y2 = Cudd_bddIte(dd, y[i], z4, z3);
	if (y2 == NULL) {
	    Cudd_RecursiveDeref(dd, z1);
	    Cudd_RecursiveDeref(dd, z2);
	    Cudd_RecursiveDeref(dd, z3);
	    Cudd_RecursiveDeref(dd, z4);
	    Cudd_RecursiveDeref(dd, y1_);
	    return(NULL);
	}
	cuddRef(y2);
	Cudd_RecursiveDeref(dd, z1);
	Cudd_RecursiveDeref(dd, z2);
	Cudd_RecursiveDeref(dd, z3);
	Cudd_RecursiveDeref(dd, z4);
	x1 = Cudd_bddIte(dd, x[i], y1_, y2);
	if (x1 == NULL) {
	    Cudd_RecursiveDeref(dd, y1_);
	    Cudd_RecursiveDeref(dd, y2);
	    return(NULL);
	}
	cuddRef(x1);
	Cudd_RecursiveDeref(dd, y1_);
	Cudd_RecursiveDeref(dd, y2);
    }
    cuddDeref(x1);
    return(Cudd_Not(x1));

} /* end of Cudd_Dxygtdxz */


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

  Synopsis    [Generates a BDD for the function d(x,y) > d(y,z).]

  Description [This function generates a BDD for the function d(x,y)
  > d(y,z);
  x, y, and z are N-bit numbers, x\[0\] x\[1\] ... x\[N-1\],
  y\[0\] y\[1\] ...  y\[N-1\], and z\[0\] z\[1\] ...  z\[N-1\],
  with 0 the most significant bit.
  The distance d(x,y) is defined as:
	\sum_{i=0}^{N-1}(|x_i - y_i| \cdot 2^{N-i-1}).
  The BDD is built bottom-up.
  It has 7*N-3 internal nodes, if the variables are ordered as follows: 
  x\[0\] y\[0\] z\[0\] x\[1\] y\[1\] z\[1\] ... x\[N-1\] y\[N-1\] z\[N-1\]. ]

  SideEffects [None]

  SeeAlso     [Cudd_PrioritySelect Cudd_Dxygtdxz Cudd_Xgty Cudd_bddAdjPermuteX]

******************************************************************************/
DdNode *
Cudd_Dxygtdyz(
  DdManager * dd /* DD manager */,
  int  N /* number of x, y, and z variables */,
  DdNode ** x /* array of x variables */,
  DdNode ** y /* array of y variables */,
  DdNode ** z /* array of z variables */)
{
    DdNode *one, *zero;
    DdNode *z1, *z2, *z3, *z4, *y1_, *y2, *x1;
    int     i;

    one = DD_ONE(dd);
    zero = Cudd_Not(one);

    /* Build bottom part of BDD outside loop. */
    y1_ = Cudd_bddIte(dd, y[N-1], one, z[N-1]);
    if (y1_ == NULL) return(NULL);
    cuddRef(y1_);
    y2 = Cudd_bddIte(dd, y[N-1], z[N-1], zero);
    if (y2 == NULL) {
	Cudd_RecursiveDeref(dd, y1_);
	return(NULL);
    }
    cuddRef(y2);
    x1 = Cudd_bddIte(dd, x[N-1], y1_, Cudd_Not(y2));
    if (x1 == NULL) {
	Cudd_RecursiveDeref(dd, y1_);
	Cudd_RecursiveDeref(dd, y2);
	return(NULL);
    }
    cuddRef(x1);
    Cudd_RecursiveDeref(dd, y1_);
    Cudd_RecursiveDeref(dd, y2);

    /* Loop to build the rest of the BDD. */
    for (i = N-2; i >= 0; i--) {
	z1 = Cudd_bddIte(dd, z[i], x1, zero);
	if (z1 == NULL) {
	    Cudd_RecursiveDeref(dd, x1);
	    return(NULL);
	}
	cuddRef(z1);
	z2 = Cudd_bddIte(dd, z[i], x1, one);
	if (z2 == NULL) {
	    Cudd_RecursiveDeref(dd, x1);
	    Cudd_RecursiveDeref(dd, z1);
	    return(NULL);
	}
	cuddRef(z2);
	z3 = Cudd_bddIte(dd, z[i], one, x1);
	if (z3 == NULL) {
	    Cudd_RecursiveDeref(dd, x1);
	    Cudd_RecursiveDeref(dd, z1);
	    Cudd_RecursiveDeref(dd, z2);
	    return(NULL);
	}
	cuddRef(z3);
	z4 = Cudd_bddIte(dd, z[i], one, Cudd_Not(x1));
	if (z4 == NULL) {
	    Cudd_RecursiveDeref(dd, x1);
	    Cudd_RecursiveDeref(dd, z1);
	    Cudd_RecursiveDeref(dd, z2);
	    Cudd_RecursiveDeref(dd, z3);
	    return(NULL);
	}
	cuddRef(z4);
	Cudd_RecursiveDeref(dd, x1);
	y1_ = Cudd_bddIte(dd, y[i], z2, z1);
	if (y1_ == NULL) {
	    Cudd_RecursiveDeref(dd, z1);
	    Cudd_RecursiveDeref(dd, z2);
	    Cudd_RecursiveDeref(dd, z3);
	    Cudd_RecursiveDeref(dd, z4);
	    return(NULL);
	}
	cuddRef(y1_);
	y2 = Cudd_bddIte(dd, y[i], z4, Cudd_Not(z3));
	if (y2 == NULL) {
	    Cudd_RecursiveDeref(dd, z1);
	    Cudd_RecursiveDeref(dd, z2);
	    Cudd_RecursiveDeref(dd, z3);
	    Cudd_RecursiveDeref(dd, z4);
	    Cudd_RecursiveDeref(dd, y1_);
	    return(NULL);
	}
	cuddRef(y2);
	Cudd_RecursiveDeref(dd, z1);
	Cudd_RecursiveDeref(dd, z2);
	Cudd_RecursiveDeref(dd, z3);
	Cudd_RecursiveDeref(dd, z4);
	x1 = Cudd_bddIte(dd, x[i], y1_, Cudd_Not(y2));
	if (x1 == NULL) {
	    Cudd_RecursiveDeref(dd, y1_);
	    Cudd_RecursiveDeref(dd, y2);
	    return(NULL);
	}
	cuddRef(x1);
	Cudd_RecursiveDeref(dd, y1_);
	Cudd_RecursiveDeref(dd, y2);
    }
    cuddDeref(x1);
    return(Cudd_Not(x1));

} /* end of Cudd_Dxygtdyz */


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

  Synopsis    [Computes the compatible projection of R w.r.t. cube Y.]

  Description [Computes the compatible projection of relation R with
  respect to cube Y. Returns a pointer to the c-projection if
  successful; NULL otherwise. For a comparison between Cudd_CProjection
  and Cudd_PrioritySelect, see the documentation of the latter.]

  SideEffects [None]

  SeeAlso     [Cudd_PrioritySelect]

******************************************************************************/
DdNode *
Cudd_CProjection(
  DdManager * dd,
  DdNode * R,
  DdNode * Y)
{
    DdNode *res;
    DdNode *support;

    if (cuddCheckCube(dd,Y) == 0) {
	(void) fprintf(dd->err,
	"Error: The third argument of Cudd_CProjection should be a cube\n");
	dd->errorCode = CUDD_INVALID_ARG;
	return(NULL);
    }

    /* Compute the support of Y, which is used by the abstraction step
    ** in cuddCProjectionRecur.
    */
    support = Cudd_Support(dd,Y);
    if (support == NULL) return(NULL);
    cuddRef(support);

    do {
	dd->reordered = 0;
	res = cuddCProjectionRecur(dd,R,Y,support);
    } while (dd->reordered == 1);

    if (res == NULL) {
	Cudd_RecursiveDeref(dd,support);
	return(NULL);
    }
    cuddRef(res);
    Cudd_RecursiveDeref(dd,support);
    cuddDeref(res);

    return(res);

} /* end of Cudd_CProjection */


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

  Synopsis    [Computes the Hamming distance ADD.]

  Description [Computes the Hamming distance ADD. Returns an ADD that
  gives the Hamming distance between its two arguments if successful;
  NULL otherwise. The two vectors xVars and yVars identify the variables
  that form the two arguments.]

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
DdNode *
Cudd_addHamming(
  DdManager * dd,
  DdNode ** xVars,
  DdNode ** yVars,
  int  nVars)
{
    DdNode  *result,*tempBdd;
    DdNode  *tempAdd,*temp;
    int     i;

    result = DD_ZERO(dd);
    cuddRef(result);

    for (i = 0; i < nVars; i++) {
	tempBdd = Cudd_bddIte(dd,xVars[i],Cudd_Not(yVars[i]),yVars[i]);
	if (tempBdd == NULL) {
	    Cudd_RecursiveDeref(dd,result);
	    return(NULL);
	}
	cuddRef(tempBdd);
	tempAdd = Cudd_BddToAdd(dd,tempBdd);
	if (tempAdd == NULL) {
	    Cudd_RecursiveDeref(dd,tempBdd);
	    Cudd_RecursiveDeref(dd,result);
	    return(NULL);
	}
	cuddRef(tempAdd);
	Cudd_RecursiveDeref(dd,tempBdd);
	temp = Cudd_addApply(dd,Cudd_addPlus,tempAdd,result);
	if (temp == NULL) {
	    Cudd_RecursiveDeref(dd,tempAdd);
	    Cudd_RecursiveDeref(dd,result);
	    return(NULL);
	}
	cuddRef(temp);
	Cudd_RecursiveDeref(dd,tempAdd);
	Cudd_RecursiveDeref(dd,result);
	result = temp;
    }

    cuddDeref(result);
    return(result);

} /* end of Cudd_addHamming */


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

  Synopsis    [Returns the minimum Hamming distance between f and minterm.]

  Description [Returns the minimum Hamming distance between the
  minterms of a function f and a reference minterm. The function is
  given as a BDD; the minterm is given as an array of integers, one
  for each variable in the manager.  Returns the minimum distance if
  it is less than the upper bound; the upper bound if the minimum
  distance is at least as large; CUDD_OUT_OF_MEM in case of failure.]

  SideEffects [None]

  SeeAlso     [Cudd_addHamming Cudd_bddClosestCube]

******************************************************************************/
int
Cudd_MinHammingDist(
  DdManager *dd /* DD manager */,
  DdNode *f /* function to examine */,
  int *minterm /* reference minterm */,
  int upperBound /* distance above which an approximate answer is OK */)
{
    DdHashTable *table;
    CUDD_VALUE_TYPE epsilon;
    int res;

    table = cuddHashTableInit(dd,1,2);
    if (table == NULL) {
	return(CUDD_OUT_OF_MEM);
    }
    epsilon = Cudd_ReadEpsilon(dd);
    Cudd_SetEpsilon(dd,(CUDD_VALUE_TYPE)0.0);
    res = cuddMinHammingDistRecur(f,minterm,table,upperBound);
    cuddHashTableQuit(table);
    Cudd_SetEpsilon(dd,epsilon);

    return(res);
    
} /* end of Cudd_MinHammingDist */


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

  Synopsis    [Finds a cube of f at minimum Hamming distance from g.]

  Description [Finds a cube of f at minimum Hamming distance from the
  minterms of g.  All the minterms of the cube are at the minimum
  distance.  If the distance is 0, the cube belongs to the
  intersection of f and g.  Returns the cube if successful; NULL
  otherwise.]

  SideEffects [The distance is returned as a side effect.]

  SeeAlso     [Cudd_MinHammingDist]

******************************************************************************/
DdNode *
Cudd_bddClosestCube(
  DdManager *dd,
  DdNode * f,
  DdNode *g,
  int *distance)
{
    DdNode *res, *acube;
    CUDD_VALUE_TYPE rdist;

    /* Compute the cube and distance as a single ADD. */
    do {
	dd->reordered = 0;
	res = cuddBddClosestCube(dd,f,g,CUDD_CONST_INDEX + 1.0);
    } while (dd->reordered == 1);
    if (res == NULL) return(NULL);
    cuddRef(res);

    /* Unpack distance and cube. */
    do {
	dd->reordered = 0;
	acube = separateCube(dd, res, &rdist);
    } while (dd->reordered == 1);
    if (acube == NULL) {
	Cudd_RecursiveDeref(dd, res);
	return(NULL);
    }
    cuddRef(acube);
    Cudd_RecursiveDeref(dd, res);

    /* Convert cube from ADD to BDD. */
    do {
	dd->reordered = 0;
	res = cuddAddBddDoPattern(dd, acube);
    } while (dd->reordered == 1);
    if (res == NULL) {
	Cudd_RecursiveDeref(dd, acube);
	return(NULL);
    }
    cuddRef(res);
    Cudd_RecursiveDeref(dd, acube);

    *distance = (int) rdist;
    cuddDeref(res);
    return(res);

} /* end of Cudd_bddClosestCube */


/*---------------------------------------------------------------------------*/
/* Definition of internal functions                                          */
/*---------------------------------------------------------------------------*/


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

  Synopsis    [Performs the recursive step of Cudd_CProjection.]

  Description [Performs the recursive step of Cudd_CProjection. Returns
  the projection if successful; NULL otherwise.]

  SideEffects [None]

  SeeAlso     [Cudd_CProjection]

******************************************************************************/
DdNode *
cuddCProjectionRecur(
  DdManager * dd,
  DdNode * R,
  DdNode * Y,
  DdNode * Ysupp)
{
    DdNode *res, *res1, *res2, *resA;
    DdNode *r, *y, *RT, *RE, *YT, *YE, *Yrest, *Ra, *Ran, *Gamma, *Alpha;
    unsigned int topR, topY, top, index;
    DdNode *one = DD_ONE(dd);

    statLine(dd);
    if (Y == one) return(R);

#ifdef DD_DEBUG
    assert(!Cudd_IsConstant(Y));
#endif

    if (R == Cudd_Not(one)) return(R);

    res = cuddCacheLookup2(dd, Cudd_CProjection, R, Y);
    if (res != NULL) return(res);

    r = Cudd_Regular(R);
    topR = cuddI(dd,r->index);
    y = Cudd_Regular(Y);
    topY = cuddI(dd,y->index);

    top = ddMin(topR, topY);

    /* Compute the cofactors of R */
    if (topR == top) {
	index = r->index;
	RT = cuddT(r);
	RE = cuddE(r);
	if (r != R) {
	    RT = Cudd_Not(RT); RE = Cudd_Not(RE);
	}
    } else {
	RT = RE = R;
    }

    if (topY > top) {
	/* Y does not depend on the current top variable.
	** We just need to compute the results on the two cofactors of R
	** and make them the children of a node labeled r->index.
	*/
	res1 = cuddCProjectionRecur(dd,RT,Y,Ysupp);
	if (res1 == NULL) return(NULL);
	cuddRef(res1);
	res2 = cuddCProjectionRecur(dd,RE,Y,Ysupp);
	if (res2 == NULL) {
	    Cudd_RecursiveDeref(dd,res1);