cuddapa.c

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

  Description [Prints an arbitrary precision integer in hexadecimal format.
  Returns 1 if successful; 0 otherwise.]

  SideEffects [None]

  SeeAlso     [Cudd_ApaPrintDecimal Cudd_ApaPrintExponential]

******************************************************************************/
int
Cudd_ApaPrintHex(
  FILE * fp,
  int  digits,
  DdApaNumber  number)
{
    int i, result;

    for (i = 0; i < digits; i++) {
	result = fprintf(fp,DD_APA_HEXPRINT,number[i]);
	if (result == EOF)
	    return(0);
    }
    return(1);

} /* end of Cudd_ApaPrintHex */


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

  Synopsis    [Prints an arbitrary precision integer in decimal format.]

  Description [Prints an arbitrary precision integer in decimal format.
  Returns 1 if successful; 0 otherwise.]

  SideEffects [None]

  SeeAlso     [Cudd_ApaPrintHex Cudd_ApaPrintExponential]

******************************************************************************/
int
Cudd_ApaPrintDecimal(
  FILE * fp,
  int  digits,
  DdApaNumber  number)
{
    int i, result;
    DdApaDigit remainder;
    DdApaNumber work;
    unsigned char *decimal;
    int leadingzero;
    int decimalDigits = (int) (digits * log10((double) DD_APA_BASE)) + 1;
    
    work = Cudd_NewApaNumber(digits);
    if (work == NULL)
	return(0);
    decimal = ALLOC(unsigned char, decimalDigits);
    if (decimal == NULL) {
	FREE(work);
	return(0);
    }
    Cudd_ApaCopy(digits,number,work);
    for (i = decimalDigits - 1; i >= 0; i--) {
	remainder = Cudd_ApaShortDivision(digits,work,(DdApaDigit) 10,work);
	decimal[i] = remainder;
    }
    FREE(work);

    leadingzero = 1;
    for (i = 0; i < decimalDigits; i++) {
	leadingzero = leadingzero && (decimal[i] == 0);
	if ((!leadingzero) || (i == (decimalDigits - 1))) {
	    result = fprintf(fp,"%1d",decimal[i]);
	    if (result == EOF) {
		FREE(decimal);
		return(0);
	    }
	}
    }
    FREE(decimal);
    return(1);

} /* end of Cudd_ApaPrintDecimal */


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

  Synopsis    [Prints an arbitrary precision integer in exponential format.]

  Description [Prints an arbitrary precision integer in exponential format.
  Returns 1 if successful; 0 otherwise.]

  SideEffects [None]

  SeeAlso     [Cudd_ApaPrintHex Cudd_ApaPrintDecimal]

******************************************************************************/
int
Cudd_ApaPrintExponential(
  FILE * fp,
  int  digits,
  DdApaNumber  number,
  int precision)
{
    int i, first, last, result;
    DdApaDigit remainder;
    DdApaNumber work;
    unsigned char *decimal;
    int decimalDigits = (int) (digits * log10((double) DD_APA_BASE)) + 1;
    
    work = Cudd_NewApaNumber(digits);
    if (work == NULL)
	return(0);
    decimal = ALLOC(unsigned char, decimalDigits);
    if (decimal == NULL) {
	FREE(work);
	return(0);
    }
    Cudd_ApaCopy(digits,number,work);
    first = decimalDigits - 1;
    for (i = decimalDigits - 1; i >= 0; i--) {
	remainder = Cudd_ApaShortDivision(digits,work,(DdApaDigit) 10,work);
	decimal[i] = remainder;
	if (remainder != 0) first = i; /* keep track of MS non-zero */
    }
    FREE(work);
    last = ddMin(first + precision, decimalDigits);

    for (i = first; i < last; i++) {
	result = fprintf(fp,"%s%1d",i == first+1 ? "." : "", decimal[i]);
	if (result == EOF) {
	    FREE(decimal);
	    return(0);
	}
    }
    FREE(decimal);
    result = fprintf(fp,"e+%d",decimalDigits - first - 1);
    if (result == EOF) {
	return(0);
    }
    return(1);

} /* end of Cudd_ApaPrintExponential */


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

  Synopsis    [Counts the number of minterms of a DD.]

  Description [Counts the number of minterms of a DD. The function is
  assumed to depend on nvars variables. The minterm count is
  represented as an arbitrary precision unsigned integer, to allow for
  any number of variables CUDD supports.  Returns a pointer to the
  array representing the number of minterms of the function rooted at
  node if successful; NULL otherwise.]

  SideEffects [The number of digits of the result is returned in
  parameter <code>digits</code>.]

  SeeAlso     [Cudd_CountMinterm]

******************************************************************************/
DdApaNumber
Cudd_ApaCountMinterm(
  DdManager * manager,
  DdNode * node,
  int  nvars,
  int * digits)
{
    DdApaNumber	max, min;
    st_table	*table;
    DdApaNumber	i,count;	

    background = manager->background;
    zero = Cudd_Not(manager->one);

    *digits = Cudd_ApaNumberOfDigits(nvars+1);
    max = Cudd_NewApaNumber(*digits);
    if (max == NULL) {
	return(NULL);
    }
    Cudd_ApaPowerOfTwo(*digits,max,nvars);
    min = Cudd_NewApaNumber(*digits);
    if (min == NULL) {
	FREE(max);
	return(NULL);
    }
    Cudd_ApaSetToLiteral(*digits,min,0);
    table = st_init_table(st_ptrcmp,st_ptrhash);
    if (table == NULL) {
	FREE(max);
	FREE(min);
	return(NULL);
    }
    i = cuddApaCountMintermAux(Cudd_Regular(node),*digits,max,min,table);
    if (i == NULL) {
	FREE(max);
	FREE(min);
	st_foreach(table, cuddApaStCountfree, NULL);
	st_free_table(table);
	return(NULL);
    }
    count = Cudd_NewApaNumber(*digits);
    if (count == NULL) {
	FREE(max);
	FREE(min);
	st_foreach(table, cuddApaStCountfree, NULL);
	st_free_table(table);
	if (Cudd_Regular(node)->ref == 1) FREE(i);
	return(NULL);
    }
    if (Cudd_IsComplement(node)) {
	(void) Cudd_ApaSubtract(*digits,max,i,count);
    } else {
	Cudd_ApaCopy(*digits,i,count);
    }
    FREE(max);
    FREE(min);
    st_foreach(table, cuddApaStCountfree, NULL);
    st_free_table(table);
    if (Cudd_Regular(node)->ref == 1) FREE(i);
    return(count);

} /* end of Cudd_ApaCountMinterm */


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

  Synopsis    [Prints the number of minterms of a BDD or ADD using
  arbitrary precision arithmetic.]

  Description [Prints the number of minterms of a BDD or ADD using
  arbitrary precision arithmetic. Returns 1 if successful; 0 otherwise.]

  SideEffects [None]

  SeeAlso     [Cudd_ApaPrintMintermExp]

******************************************************************************/
int
Cudd_ApaPrintMinterm(
  FILE * fp,
  DdManager * dd,
  DdNode * node,
  int  nvars)
{
    int digits;
    int result;
    DdApaNumber count;

    count = Cudd_ApaCountMinterm(dd,node,nvars,&digits);
    if (count == NULL)
	return(0);
    result = Cudd_ApaPrintDecimal(fp,digits,count);
    FREE(count);
    if (fprintf(fp,"\n") == EOF) {
	return(0);
    }
    return(result);

} /* end of Cudd_ApaPrintMinterm */


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

  Synopsis    [Prints the number of minterms of a BDD or ADD in exponential
  format using arbitrary precision arithmetic.]

  Description [Prints the number of minterms of a BDD or ADD in
  exponential format using arbitrary precision arithmetic. Parameter
  precision controls the number of signficant digits printed. Returns
  1 if successful; 0 otherwise.]

  SideEffects [None]

  SeeAlso     [Cudd_ApaPrintMinterm]

******************************************************************************/
int
Cudd_ApaPrintMintermExp(
  FILE * fp,
  DdManager * dd,
  DdNode * node,
  int  nvars,
  int precision)
{
    int digits;
    int result;
    DdApaNumber count;

    count = Cudd_ApaCountMinterm(dd,node,nvars,&digits);
    if (count == NULL)
	return(0);
    result = Cudd_ApaPrintExponential(fp,digits,count,precision);
    FREE(count);
    if (fprintf(fp,"\n") == EOF) {
	return(0);
    }
    return(result);

} /* end of Cudd_ApaPrintMintermExp */


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

  Synopsis    [Prints the density of a BDD or ADD using
  arbitrary precision arithmetic.]

  Description [Prints the density of a BDD or ADD using
  arbitrary precision arithmetic. Returns 1 if successful; 0 otherwise.]

  SideEffects [None]

  SeeAlso     []

******************************************************************************/
int
Cudd_ApaPrintDensity(
  FILE * fp,
  DdManager * dd,
  DdNode * node,
  int  nvars)
{
    int digits;
    int result;
    DdApaNumber count,density;
    unsigned int size, remainder, fractional;

    count = Cudd_ApaCountMinterm(dd,node,nvars,&digits);
    if (count == NULL)
	return(0);
    size = Cudd_DagSize(node);
    density = Cudd_NewApaNumber(digits);
    remainder = Cudd_ApaIntDivision(digits,count,size,density);
    result = Cudd_ApaPrintDecimal(fp,digits,density);
    FREE(count);
    FREE(density);
    fractional = (unsigned int)((double)remainder / size * 1000000);
    if (fprintf(fp,".%u\n", fractional) == EOF) {
	return(0);
    }
    return(result);

} /* end of Cudd_ApaPrintDensity */


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


/*---------------------------------------------------------------------------*/
/* Definition of static functions                                            */
/*---------------------------------------------------------------------------*/


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

  Synopsis    [Performs the recursive step of Cudd_ApaCountMinterm.]

  Description [Performs the recursive step of Cudd_ApaCountMinterm.
  It is based on the following identity. Let |f| be the
  number of minterms of f. Then:
  <xmp>
    |f| = (|f0|+|f1|)/2
  </xmp>
  where f0 and f1 are the two cofactors of f.
  Uses the identity <code>|f'| = max - |f|</code>.
  The procedure expects the argument "node" to be a regular pointer, and
  guarantees this condition is met in the recursive calls.
  For efficiency, the result of a call is cached only if the node has
  a reference count greater than 1.
  Returns the number of minterms of the function rooted at node.]

  SideEffects [None]

******************************************************************************/
static DdApaNumber
cuddApaCountMintermAux(
  DdNode * node,
  int  digits,
  DdApaNumber  max,
  DdApaNumber  min,
  st_table * table)
{
    DdNode      *Nt, *Ne;
    DdApaNumber	mint, mint1, mint2;
    DdApaDigit	carryout;

    if (cuddIsConstant(node)) {
	if (node == background || node == zero) {
	    return(min);
	} else {
	    return(max);
	}
    }
    if (node->ref > 1 && st_lookup(table, (char *)node, (char **)&mint)) {
	return(mint);
    }

    Nt = cuddT(node); Ne = cuddE(node);

    mint1 = cuddApaCountMintermAux(Nt,  digits, max, min, table);
    if (mint1 == NULL) return(NULL);
    mint2 = cuddApaCountMintermAux(Cudd_Regular(Ne), digits, max, min, table);
    if (mint2 == NULL) {
	if (Nt->ref == 1) FREE(mint1);
	return(NULL);
    }
    mint = Cudd_NewApaNumber(digits);
    if (mint == NULL) {
	if (Nt->ref == 1) FREE(mint1);
	if (Cudd_Regular(Ne)->ref == 1) FREE(mint2);
	return(NULL);
    }
    if (Cudd_IsComplement(Ne)) {
	(void) Cudd_ApaSubtract(digits,max,mint2,mint);
	carryout = Cudd_ApaAdd(digits,mint1,mint,mint);
    } else {
	carryout = Cudd_ApaAdd(digits,mint1,mint2,mint);
    }
    Cudd_ApaShiftRight(digits,carryout,mint,mint);
    /* If the refernce count of a child is 1, its minterm count
    ** hasn't been stored in table.  Therefore, it must be explicitly
    ** freed here. */
    if (Nt->ref == 1) FREE(mint1);
    if (Cudd_Regular(Ne)->ref == 1) FREE(mint2);
    
    if (node->ref > 1) {
	if (st_insert(table, (char *)node, (char *)mint) == ST_OUT_OF_MEM) {
	    FREE(mint);
	    return(NULL);
	}
    }
    return(mint);

} /* end of cuddApaCountMintermAux */


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

  Synopsis [Frees the memory used to store the minterm counts recorded
  in the visited table.]

  Description [Frees the memory used to store the minterm counts
  recorded in the visited table. Returns ST_CONTINUE.]

  SideEffects [None]

******************************************************************************/
static enum st_retval
cuddApaStCountfree(
  char * key,
  char * value,
  char * arg)
{
    DdApaNumber	d;

    d = (DdApaNumber) value;
    FREE(d);
    return(ST_CONTINUE);

} /* end of cuddApaStCountfree */