cuddsat.c

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

/**CFile***********************************************************************

  FileName    [cuddSat.c]

  PackageName [cudd]

  Synopsis    [Functions for the solution of satisfiability related
  problems.]

  Description [External procedures included in this file:
		<ul>
		<li> Cudd_Eval()
		<li> Cudd_ShortestPath()
		<li> Cudd_LargestCube()
		<li> Cudd_ShortestLength()
		<li> Cudd_Decreasing()
		<li> Cudd_Increasing()
		<li> Cudd_EquivDC()
		<li> Cudd_bddLeqUnless()
		<li> Cudd_EqualSupNorm()
		<li> Cudd_bddMakePrime()
		</ul>
	Internal procedures included in this module:
	        <ul>
		<li> cuddBddMakePrime()
		</ul>
	Static procedures included in this module:
		<ul>
		<li> freePathPair()
		<li> getShortest()
		<li> getPath()
		<li> getLargest()
		<li> getCube()
		</ul>]

  Author      [Seh-Woong Jeong, Fabio Somenzi]

  Copyright   [This file was created at the University of Colorado at
  Boulder.  The University of Colorado at Boulder makes no warranty
  about the suitability of this software for any purpose.  It is
  presented on an AS IS basis.]

******************************************************************************/

#include "util.h"
#include "cuddInt.h"

/*---------------------------------------------------------------------------*/
/* Constant declarations                                                     */
/*---------------------------------------------------------------------------*/

#define	DD_BIGGY	1000000

/*---------------------------------------------------------------------------*/
/* Stucture declarations                                                     */
/*---------------------------------------------------------------------------*/

/*---------------------------------------------------------------------------*/
/* Type declarations                                                         */
/*---------------------------------------------------------------------------*/

typedef struct cuddPathPair {
    int	pos;
    int	neg;
} cuddPathPair;

/*---------------------------------------------------------------------------*/
/* Variable declarations                                                     */
/*---------------------------------------------------------------------------*/

#ifndef lint
static char rcsid[] DD_UNUSED = "$Id: cuddSat.c,v 1.1.1.1 2003/02/24 22:23:53 wjiang Exp $";
#endif

static	DdNode	*one, *zero;

/*---------------------------------------------------------------------------*/
/* Macro declarations                                                        */
/*---------------------------------------------------------------------------*/

#define WEIGHT(weight, col)	((weight) == NULL ? 1 : weight[col])

/**AutomaticStart*************************************************************/

/*---------------------------------------------------------------------------*/
/* Static function prototypes                                                */
/*---------------------------------------------------------------------------*/

static enum st_retval freePathPair ARGS((char *key, char *value, char *arg));
static cuddPathPair getShortest ARGS((DdNode *root, int *cost, int *support, st_table *visited));
static DdNode * getPath ARGS((DdManager *manager, st_table *visited, DdNode *f, int *weight, int cost));
static cuddPathPair getLargest ARGS((DdNode *root, st_table *visited));
static DdNode * getCube ARGS((DdManager *manager, st_table *visited, DdNode *f, int cost));

/**AutomaticEnd***************************************************************/


/*---------------------------------------------------------------------------*/
/* Definition of exported functions                                          */
/*---------------------------------------------------------------------------*/


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

  Synopsis    [Returns the value of a DD for a given variable assignment.]

  Description [Finds the value of a DD for a given variable
  assignment. The variable assignment is passed in an array of int's,
  that should specify a zero or a one for each variable in the support
  of the function. Returns a pointer to a constant node. No new nodes
  are produced.]

  SideEffects [None]

  SeeAlso     [Cudd_bddLeq Cudd_addEvalConst]

******************************************************************************/
DdNode *
Cudd_Eval(
  DdManager * dd,
  DdNode * f,
  int * inputs)
{
    int comple;
    DdNode *ptr;

    comple = Cudd_IsComplement(f);
    ptr = Cudd_Regular(f);

    while (!cuddIsConstant(ptr)) {
	if (inputs[ptr->index] == 1) {
	    ptr = cuddT(ptr);
	} else {
	    comple ^= Cudd_IsComplement(cuddE(ptr));
	    ptr = Cudd_Regular(cuddE(ptr));
	}
    }
    return(Cudd_NotCond(ptr,comple));

} /* end of Cudd_Eval */


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

  Synopsis    [Finds a shortest path in a DD.]

  Description [Finds a shortest path in a DD. f is the DD we want to
  get the shortest path for; weight\[i\] is the weight of the THEN arc
  coming from the node whose index is i. If weight is NULL, then unit
  weights are assumed for all THEN arcs. All ELSE arcs have 0 weight.
  If non-NULL, both weight and support should point to arrays with at
  least as many entries as there are variables in the manager.
  Returns the shortest path as the BDD of a cube.]

  SideEffects [support contains on return the true support of f.
  If support is NULL on entry, then Cudd_ShortestPath does not compute
  the true support info. length contains the length of the path.]

  SeeAlso     [Cudd_ShortestLength Cudd_LargestCube]

******************************************************************************/
DdNode *
Cudd_ShortestPath(
  DdManager * manager,
  DdNode * f,
  int * weight,
  int * support,
  int * length)
{
    register 	DdNode	*F;
    st_table	*visited;
    DdNode	*sol;
    cuddPathPair *rootPair;
    int		complement, cost;
    int		i;

    one = DD_ONE(manager);
    zero = DD_ZERO(manager);

    /* Initialize support. */
    if (support) {
	for (i = 0; i < manager->size; i++) {
	    support[i] = 0;
	}
    }

    if (f == Cudd_Not(one) || f == zero) {
	*length = DD_BIGGY;
	return(Cudd_Not(one));
    }
    /* From this point on, a path exists. */

    /* Initialize visited table. */
    visited = st_init_table(st_ptrcmp, st_ptrhash);

    /* Now get the length of the shortest path(s) from f to 1. */
    (void) getShortest(f, weight, support, visited);

    complement = Cudd_IsComplement(f);

    F = Cudd_Regular(f);

    st_lookup(visited, (char *)F, (char **)&rootPair);
    
    if (complement) {
	cost = rootPair->neg;
    } else {
	cost = rootPair->pos;
    }

    /* Recover an actual shortest path. */
    do {
	manager->reordered = 0;
	sol = getPath(manager,visited,f,weight,cost);
    } while (manager->reordered == 1);

    st_foreach(visited, freePathPair, NULL);
    st_free_table(visited);

    *length = cost;
    return(sol);

} /* end of Cudd_ShortestPath */


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

  Synopsis    [Finds a largest cube in a DD.]

  Description [Finds a largest cube in a DD. f is the DD we want to
  get the largest cube for. The problem is translated into the one of
  finding a shortest path in f, when both THEN and ELSE arcs are assumed to
  have unit length. This yields a largest cube in the disjoint cover
  corresponding to the DD. Therefore, it is not necessarily the largest
  implicant of f.  Returns the largest cube as a BDD.]

  SideEffects [The number of literals of the cube is returned in length.]

  SeeAlso     [Cudd_ShortestPath]

******************************************************************************/
DdNode *
Cudd_LargestCube(
  DdManager * manager,
  DdNode * f,
  int * length)
{
    register 	DdNode	*F;
    st_table	*visited;
    DdNode	*sol;
    cuddPathPair *rootPair;
    int		complement, cost;

    one = DD_ONE(manager);
    zero = DD_ZERO(manager);

    if (f == Cudd_Not(one) || f == zero) {
	*length = DD_BIGGY;
	return(Cudd_Not(one));
    }
    /* From this point on, a path exists. */

    /* Initialize visited table. */
    visited = st_init_table(st_ptrcmp, st_ptrhash);

    /* Now get the length of the shortest path(s) from f to 1. */
    (void) getLargest(f, visited);

    complement = Cudd_IsComplement(f);

    F = Cudd_Regular(f);

    st_lookup(visited, (char *)F, (char **)&rootPair);
    
    if (complement) {
	cost = rootPair->neg;
    } else {
	cost = rootPair->pos;
    }

    /* Recover an actual shortest path. */
    do {
	manager->reordered = 0;
	sol = getCube(manager,visited,f,cost);
    } while (manager->reordered == 1);

    st_foreach(visited, freePathPair, NULL);
    st_free_table(visited);

    *length = cost;
    return(sol);

} /* end of Cudd_LargestCube */


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

  Synopsis    [Find the length of the shortest path(s) in a DD.]

  Description [Find the length of the shortest path(s) in a DD. f is
  the DD we want to get the shortest path for; weight\[i\] is the
  weight of the THEN edge coming from the node whose index is i. All
  ELSE edges have 0 weight. Returns the length of the shortest
  path(s) if successful; CUDD_OUT_OF_MEM otherwise.]

  SideEffects [None]

  SeeAlso     [Cudd_ShortestPath]

******************************************************************************/
int
Cudd_ShortestLength(
  DdManager * manager,
  DdNode * f,
  int * weight)
{
    register 	DdNode	*F;
    st_table	*visited;
    cuddPathPair *my_pair;
    int		complement, cost;

    one = DD_ONE(manager);
    zero = DD_ZERO(manager);

    if (f == Cudd_Not(one) || f == zero) {
	return(DD_BIGGY);
    }

    /* From this point on, a path exists. */
    /* Initialize visited table and support. */
    visited = st_init_table(st_ptrcmp, st_ptrhash);

    /* Now get the length of the shortest path(s) from f to 1. */
    (void) getShortest(f, weight, NULL, visited);

    complement = Cudd_IsComplement(f);

    F = Cudd_Regular(f);

    st_lookup(visited, (char *)F, (char **)&my_pair);
    
    if (complement) {
	cost = my_pair->neg;
    } else {
	cost = my_pair->pos;
    }

    st_foreach(visited, freePathPair, NULL);
    st_free_table(visited);

    return(cost);

} /* end of Cudd_ShortestLength */


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

  Synopsis    [Determines whether a BDD is negative unate in a
  variable.]

  Description [Determines whether the function represented by BDD f is
  negative unate (monotonic decreasing) in variable i. Returns the
  constant one is f is unate and the (logical) constant zero if it is not.
  This function does not generate any new nodes.]

  SideEffects [None]

  SeeAlso     [Cudd_Increasing]

******************************************************************************/
DdNode *
Cudd_Decreasing(
  DdManager * dd,
  DdNode * f,
  int  i)
{
    unsigned int topf, level;
    DdNode *F, *fv, *fvn, *res;
    DdNode *(*cacheOp)(DdManager *, DdNode *, DdNode *);

    statLine(dd);
#ifdef DD_DEBUG
    assert(0 <= i && i < dd->size);
#endif

    F = Cudd_Regular(f);
    topf = cuddI(dd,F->index);

    /* Check terminal case. If topf > i, f does not depend on var.
    ** Therefore, f is unate in i.
    */
    level = (unsigned) dd->perm[i];
    if (topf > level) {
	return(DD_ONE(dd));
    }

    /* From now on, f is not constant. */

    /* Check cache. */
    cacheOp = (DdNode *(*)(DdManager *, DdNode *, DdNode *)) Cudd_Decreasing;
    res = cuddCacheLookup2(dd,cacheOp,f,dd->vars[i]);
    if (res != NULL) {
	return(res);
    }

    /* Compute cofactors. */
    fv = cuddT(F); fvn = cuddE(F);
    if (F != f) {
	fv = Cudd_Not(fv);
	fvn = Cudd_Not(fvn);
    }

    if (topf == (unsigned) level) {
	/* Special case: if fv is regular, fv(1,...,1) = 1;
	** If in addition fvn is complemented, fvn(1,...,1) = 0.
	** But then f(1,1,...,1) > f(0,1,...,1). Hence f is not
	** monotonic decreasing in i.
	*/
	if (!Cudd_IsComplement(fv) && Cudd_IsComplement(fvn)) {
	    return(Cudd_Not(DD_ONE(dd)));
	}
	res = Cudd_bddLeq(dd,fv,fvn) ? DD_ONE(dd) : Cudd_Not(DD_ONE(dd));
    } else {
	res = Cudd_Decreasing(dd,fv,i);
	if (res == DD_ONE(dd)) {
	    res = Cudd_Decreasing(dd,fvn,i);
	}
    }

    cuddCacheInsert2(dd,cacheOp,f,dd->vars[i],res);
    return(res);

} /* end of Cudd_Decreasing */


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