cuddsubsethb.c

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

  SideEffects [Changes the size of pages, page, page index, maximum
  number of pages freeing stuff in case of memory out. ]

  SeeAlso     []

******************************************************************************/
static void
ResizeNodeDataPages(
   )
{
    int i;
    NodeData_t **newNodeDataPages;

    nodeDataPage++;
    /* If the current page index is larger than the number of pages
     * allocated, allocate a new page array. Page numbers are incremented by
     * INITIAL_PAGES
     */
    if (nodeDataPage == maxNodeDataPages) {
	newNodeDataPages = ALLOC(NodeData_t *,maxNodeDataPages + INITIAL_PAGES);
	if (newNodeDataPages == NULL) {
	    for (i = 0; i < nodeDataPage; i++) FREE(nodeDataPages[i]);
	    FREE(nodeDataPages);
	    memOut = 1;
	    return;
	} else {
	    for (i = 0; i < maxNodeDataPages; i++) {
		newNodeDataPages[i] = nodeDataPages[i];
	    }
	    /* Increase total page count */
	    maxNodeDataPages += INITIAL_PAGES;
	    FREE(nodeDataPages);
	    nodeDataPages = newNodeDataPages;
	}
    }
    /* Allocate a new page */
    currentNodeDataPage = nodeDataPages[nodeDataPage] =
	ALLOC(NodeData_t ,nodeDataPageSize);
    if (currentNodeDataPage == NULL) {
	for (i = 0; i < nodeDataPage; i++) FREE(nodeDataPages[i]);
	FREE(nodeDataPages);
	memOut = 1;
	return;
    }
    /* reset page index */
    nodeDataPageIndex = 0;
    return;

} /* end of ResizeNodeDataPages */


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

  Synopsis    [Resize the number of pages allocated to store the minterm
  counts. ]

  Description [Resize the number of pages allocated to store the minterm
  counts.  The procedure  moves the counter to the next page when the
  end of the page is reached and allocates new pages when necessary.]

  SideEffects [Changes the size of minterm pages, page, page index, maximum 
  number of pages freeing stuff in case of memory out. ]

  SeeAlso     []

******************************************************************************/
static void
ResizeCountMintermPages(
   )
{
    int i;
    double **newMintermPages;

    page++;
    /* If the current page index is larger than the number of pages
     * allocated, allocate a new page array. Page numbers are incremented by
     * INITIAL_PAGES
     */
    if (page == maxPages) {
	newMintermPages = ALLOC(double *,maxPages + INITIAL_PAGES);
	if (newMintermPages == NULL) {
	    for (i = 0; i < page; i++) FREE(mintermPages[i]);
	    FREE(mintermPages);
	    memOut = 1;
	    return;
	} else {
	    for (i = 0; i < maxPages; i++) {
		newMintermPages[i] = mintermPages[i];
	    }
	    /* Increase total page count */
	    maxPages += INITIAL_PAGES;
	    FREE(mintermPages);
	    mintermPages = newMintermPages;
	}
    }
    /* Allocate a new page */
    currentMintermPage = mintermPages[page] = ALLOC(double,pageSize);
    if (currentMintermPage == NULL) {
	for (i = 0; i < page; i++) FREE(mintermPages[i]);
	FREE(mintermPages);
	memOut = 1;
	return;
    }
    /* reset page index */
    pageIndex = 0;
    return;

} /* end of ResizeCountMintermPages */


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

  Synopsis    [Resize the number of pages allocated to store the node counts.]

  Description [Resize the number of pages allocated to store the node counts.
  The procedure  moves the counter to the next page when the end of
  the page is reached and allocates new pages when necessary.]

  SideEffects [Changes the size of pages, page, page index, maximum
  number of pages freeing stuff in case of memory out.]

  SeeAlso     []

******************************************************************************/
static void
ResizeCountNodePages(
   )
{
    int i;
    int **newNodePages;

    page++;

    /* If the current page index is larger than the number of pages
     * allocated, allocate a new page array. The number of pages is incremented
     * by INITIAL_PAGES.
     */
    if (page == maxPages) {
	newNodePages = ALLOC(int *,maxPages + INITIAL_PAGES);
	if (newNodePages == NULL) {
	    for (i = 0; i < page; i++) FREE(nodePages[i]);
	    FREE(nodePages);
	    for (i = 0; i < page; i++) FREE(lightNodePages[i]);
	    FREE(lightNodePages);
	    memOut = 1;
	    return;
	} else {
	    for (i = 0; i < maxPages; i++) {
		newNodePages[i] = nodePages[i];
	    }
	    FREE(nodePages);
	    nodePages = newNodePages;
	}

	newNodePages = ALLOC(int *,maxPages + INITIAL_PAGES);
	if (newNodePages == NULL) {
	    for (i = 0; i < page; i++) FREE(nodePages[i]);
	    FREE(nodePages);
	    for (i = 0; i < page; i++) FREE(lightNodePages[i]);
	    FREE(lightNodePages);
	    memOut = 1;
	    return;
	} else {
	    for (i = 0; i < maxPages; i++) {
		newNodePages[i] = lightNodePages[i];
	    }
	    FREE(lightNodePages);
	    lightNodePages = newNodePages;
	}
	/* Increase total page count */
	maxPages += INITIAL_PAGES;
    }
    /* Allocate a new page */
    currentNodePage = nodePages[page] = ALLOC(int,pageSize);
    if (currentNodePage == NULL) {
	for (i = 0; i < page; i++) FREE(nodePages[i]);
	FREE(nodePages);
	for (i = 0; i < page; i++) FREE(lightNodePages[i]);
	FREE(lightNodePages);
	memOut = 1;
	return;
    }
    /* Allocate a new page */
    currentLightNodePage = lightNodePages[page] = ALLOC(int,pageSize);
    if (currentLightNodePage == NULL) {
	for (i = 0; i <= page; i++) FREE(nodePages[i]);
	FREE(nodePages);
	for (i = 0; i < page; i++) FREE(lightNodePages[i]);
	FREE(lightNodePages);
	memOut = 1;
	return;
    }
    /* reset page index */
    pageIndex = 0;
    return;

} /* end of ResizeCountNodePages */


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

  Synopsis    [Recursively counts minterms of each node in the DAG.]

  Description [Recursively counts minterms of each node in the DAG.
  Similar to the cuddCountMintermAux which recursively counts the
  number of minterms for the dag rooted at each node in terms of the
  total number of variables (max). This procedure creates the node
  data structure and stores the minterm count as part of the node
  data structure. ]

  SideEffects [Creates structures of type node quality and fills the st_table]

  SeeAlso     [SubsetCountMinterm]

******************************************************************************/
static double
SubsetCountMintermAux(
  DdNode * node /* function to analyze */,
  double  max /* number of minterms of constant 1 */,
  st_table * table /* visitedTable table */)
{

    DdNode	*N,*Nv,*Nnv; /* nodes to store cofactors  */
    double	min,*pmin; /* minterm count */
    double	min1, min2; /* minterm count */
    NodeData_t *dummy;
    NodeData_t *newEntry;
    int i;

#ifdef DEBUG
    num_calls++;
#endif

    /* Constant case */
    if (Cudd_IsConstant(node)) {
	if (node == zero) {
	    return(0.0);
	} else {
	    return(max);
	}
    } else {

	/* check if entry for this node exists */
	if (st_lookup(table,(char *)node, (char **)&dummy)) {
	    min = *(dummy->mintermPointer);
	    return(min);
	}

	/* Make the node regular to extract cofactors */
	N = Cudd_Regular(node);

	/* store the cofactors */
	Nv = Cudd_T(N);
	Nnv = Cudd_E(N);
	
	Nv = Cudd_NotCond(Nv, Cudd_IsComplement(node));
	Nnv = Cudd_NotCond(Nnv, Cudd_IsComplement(node));

	min1 =  SubsetCountMintermAux(Nv, max,table)/2.0;
	if (memOut) return(0.0);
	min2 =  SubsetCountMintermAux(Nnv,max,table)/2.0;
	if (memOut) return(0.0);
	min = (min1+min2);

	/* if page index is at the bottom, then create a new page */
	if (pageIndex == pageSize) ResizeCountMintermPages();
	if (memOut) {
	    for (i = 0; i <= nodeDataPage; i++) FREE(nodeDataPages[i]);
	    FREE(nodeDataPages);
	    st_free_table(table);
	    return(0.0);
	}

	/* point to the correct location in the page */
	pmin = currentMintermPage+pageIndex;
	pageIndex++;

	/* store the minterm count of this node in the page */
	*pmin = min;

	/* Note I allocate the struct here. Freeing taken care of later */
	if (nodeDataPageIndex == nodeDataPageSize) ResizeNodeDataPages();
	if (memOut) {
	    for (i = 0; i <= page; i++) FREE(mintermPages[i]);
	    FREE(mintermPages);
	    st_free_table(table);
	    return(0.0);
	}

	newEntry = currentNodeDataPage + nodeDataPageIndex;
	nodeDataPageIndex++;

	/* points to the correct location in the page */
	newEntry->mintermPointer = pmin;
	/* initialize this field of the Node Quality structure */
	newEntry->nodesPointer = NULL;

	/* insert entry for the node in the table */
	if (st_insert(table,(char *)node, (char *)newEntry) == ST_OUT_OF_MEM) {
	    memOut = 1;
	    for (i = 0; i <= page; i++) FREE(mintermPages[i]);
	    FREE(mintermPages);
	    for (i = 0; i <= nodeDataPage; i++) FREE(nodeDataPages[i]);
	    FREE(nodeDataPages);
	    st_free_table(table);
	    return(0.0);
	}
	return(min);
    }

} /* end of SubsetCountMintermAux */


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

  Synopsis    [Counts minterms of each node in the DAG]

  Description [Counts minterms of each node in the DAG. Similar to the
  Cudd_CountMinterm procedure except this returns the minterm count for
  all the nodes in the bdd in an st_table.]

  SideEffects [none]

  SeeAlso     [SubsetCountMintermAux]

******************************************************************************/
static st_table *
SubsetCountMinterm(
  DdNode * node /* function to be analyzed */,
  int nvars /* number of variables node depends on */)
{
    st_table	*table;
    double	num;
    int i;


#ifdef DEBUG
    num_calls = 0;
#endif

    max = pow(2.0,(double) nvars);
    table = st_init_table(st_ptrcmp,st_ptrhash);
    if (table == NULL) goto OUT_OF_MEM;
    maxPages = INITIAL_PAGES;
    mintermPages = ALLOC(double *,maxPages);
    if (mintermPages == NULL) {
	st_free_table(table);
	goto OUT_OF_MEM;
    }
    page = 0;
    currentMintermPage = ALLOC(double,pageSize);
    mintermPages[page] = currentMintermPage;
    if (currentMintermPage == NULL) {
	FREE(mintermPages);
	st_free_table(table);
	goto OUT_OF_MEM;
    }
    pageIndex = 0;
    maxNodeDataPages = INITIAL_PAGES;
    nodeDataPages = ALLOC(NodeData_t *, maxNodeDataPages);
    if (nodeDataPages == NULL) {
	for (i = 0; i <= page ; i++) FREE(mintermPages[i]);
	FREE(mintermPages);
	st_free_table(table);
	goto OUT_OF_MEM;
    }
    nodeDataPage = 0;
    currentNodeDataPage = ALLOC(NodeData_t ,nodeDataPageSize);
    nodeDataPages[nodeDataPage] = currentNodeDataPage;
    if (currentNodeDataPage == NULL) {
	for (i = 0; i <= page ; i++) FREE(mintermPages[i]);
	FREE(mintermPages);
	FREE(nodeDataPages);
	st_free_table(table);
	goto OUT_OF_MEM;
    }
    nodeDataPageIndex = 0;

    num = SubsetCountMintermAux(node,max,table);
    if (memOut) goto OUT_OF_MEM;
    return(table);

OUT_OF_MEM:
    memOut = 1;
    return(NULL);

} /* end of SubsetCountMinterm */


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

  Synopsis    [Recursively counts the number of nodes under the dag.
  Also counts the number of nodes under the lighter child of
  this node.]

  Description [Recursively counts the number of nodes under the dag.
  Also counts the number of nodes under the lighter child of
  this node. . Note that the same dag may be the lighter child of two
  different nodes and have different counts. As with the minterm counts,
  the node counts are stored in pages to be space efficient and the
  address for these node counts are stored in an st_table associated
  to each node. ]

  SideEffects [Updates the node data table with node counts]

  SeeAlso     [SubsetCountNodes]

******************************************************************************/
static int
SubsetCountNodesAux(
  DdNode * node /* current node */,
  st_table * table /* table to update node count, also serves as visited table. */,
  double  max /* maximum number of variables */)
{
    int tval, eval, i;
    DdNode *N, *Nv, *Nnv;
    double minNv, minNnv;
    NodeData_t *dummyN, *dummyNv, *dummyNnv, *dummyNBar;
    int *pmin, *pminBar, *val;

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

    /* if this node has been processed do nothing */
    if (st_lookup(table, (char *)node, (char **)&dummyN) == 1) {
	val = dummyN->nodesPointer;
	if (val != NULL)
	    return(0);
    } else {
	return(0);
    }

    N  = Cudd_Regular(node);
    Nv = Cudd_T(N);
    Nnv = Cudd_E(N);
    
    Nv = Cudd_NotCond(Nv, Cudd_IsComplement(node));
    Nnv = Cudd_NotCond(Nnv, Cudd_IsComplement(node));