cuddexport.c

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

    /* Write rank info: All nodes with the same index have the same rank. */
    for (i = 0; i < nvars; i++) {
        if (sorted[dd->invperm[i]]) {
	    retval = fprintf(fp,"{ rank = same; ");
	    if (retval == EOF) goto failure;
	    if (inames == NULL || inames[dd->invperm[i]] == NULL) {
		retval = fprintf(fp,"\" %d \";\n", dd->invperm[i]);
	    } else {
		retval = fprintf(fp,"\" %s \";\n", inames[dd->invperm[i]]);
	    }
            if (retval == EOF) goto failure;
	    nodelist = dd->subtables[i].nodelist;
	    slots = dd->subtables[i].slots;
	    for (j = 0; j < slots; j++) {
		scan = nodelist[j];
		while (scan != NULL) {
		    if (st_is_member(visited,(char *) scan)) {
			retval = fprintf(fp,"\"%lx\";\n", (mask & (long) scan) / sizeof(DdNode));
			if (retval == EOF) goto failure;
		    }
		    scan = scan->next;
		}
	    }
	    retval = fprintf(fp,"}\n");
	    if (retval == EOF) goto failure;
	}
    }

    /* All constants have the same rank. */
    retval = fprintf(fp,
	"{ rank = same; \"CONST NODES\";\n{ node [shape = box]; ");
    if (retval == EOF) goto failure;
    nodelist = dd->constants.nodelist;
    slots = dd->constants.slots;
    for (j = 0; j < slots; j++) {
	scan = nodelist[j];
	while (scan != NULL) {
	    if (st_is_member(visited,(char *) scan)) {
		retval = fprintf(fp,"\"%lx\";\n", (mask & (long) scan) / sizeof(DdNode));
		if (retval == EOF) goto failure;
	    }
	    scan = scan->next;
	}
    }
    retval = fprintf(fp,"}\n}\n");
    if (retval == EOF) goto failure;

    /* Write edge info. */
    /* Edges from the output nodes. */
    for (i = 0; i < n; i++) {
	if (onames == NULL) {
	    retval = fprintf(fp,"\"F%d\"", i);
	} else {
	    retval = fprintf(fp,"\"  %s  \"", onames[i]);
	}
	if (retval == EOF) goto failure;
	/* Account for the possible complement on the root. */
	if (Cudd_IsComplement(f[i])) {
	    retval = fprintf(fp," -> \"%lx\" [style = dotted];\n",
		(mask & (long) f[i]) / sizeof(DdNode));
	} else {
	    retval = fprintf(fp," -> \"%lx\" [style = solid];\n",
		(mask & (long) f[i]) / sizeof(DdNode));
	}
	if (retval == EOF) goto failure;
    }

    /* Edges from internal nodes. */
    for (i = 0; i < nvars; i++) {
        if (sorted[dd->invperm[i]]) {
	    nodelist = dd->subtables[i].nodelist;
	    slots = dd->subtables[i].slots;
	    for (j = 0; j < slots; j++) {
		scan = nodelist[j];
		while (scan != NULL) {
		    if (st_is_member(visited,(char *) scan)) {
			retval = fprintf(fp,
			    "\"%lx\" -> \"%lx\";\n",
			    (mask & (long) scan) / sizeof(DdNode),
			    (mask & (long) cuddT(scan)) / sizeof(DdNode));
			if (retval == EOF) goto failure;
			if (Cudd_IsComplement(cuddE(scan))) {
			    retval = fprintf(fp,
				"\"%lx\" -> \"%lx\" [style = dotted];\n",
				(mask & (long) scan) / sizeof(DdNode),
				(mask & (long) cuddE(scan)) / sizeof(DdNode));
			} else {
			    retval = fprintf(fp,
				"\"%lx\" -> \"%lx\" [style = dashed];\n",
				(mask & (long) scan) / sizeof(DdNode),
				(mask & (long) cuddE(scan)) / sizeof(DdNode));
			}
			if (retval == EOF) goto failure;
		    }
		    scan = scan->next;
		}
	    }
	}
    }

    /* Write constant labels. */
    nodelist = dd->constants.nodelist;
    slots = dd->constants.slots;
    for (j = 0; j < slots; j++) {
	scan = nodelist[j];
	while (scan != NULL) {
	    if (st_is_member(visited,(char *) scan)) {
		retval = fprintf(fp,"\"%lx\" [label = \"%g\"];\n",
		    (mask & (long) scan) / sizeof(DdNode), cuddV(scan));
		if (retval == EOF) goto failure;
	    }
	    scan = scan->next;
	}
    }

    /* Write trailer and return. */
    retval = fprintf(fp,"}\n");
    if (retval == EOF) goto failure;

    st_free_table(visited);
    FREE(sorted);
    return(1);

failure:
    if (sorted != NULL) FREE(sorted);
    if (support != NULL) Cudd_RecursiveDeref(dd,support);
    if (visited != NULL) st_free_table(visited);
    return(0);

} /* end of Cudd_DumpDot */


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

  Synopsis    [Writes a daVinci file representing the argument BDDs.]

  Description [Writes a daVinci file representing the argument BDDs.
  It returns 1 in case of success; 0 otherwise (e.g., out-of-memory or
  file system full).  Cudd_DumpDaVinci does not close the file: This
  is the caller responsibility. Cudd_DumpDaVinci uses a minimal unique
  subset of the hexadecimal address of a node as name for it.  If the
  argument inames is non-null, it is assumed to hold the pointers to
  the names of the inputs. Similarly for onames.]

  SideEffects [None]

  SeeAlso     [Cudd_DumpDot Cudd_PrintDebug Cudd_DumpBlif Cudd_DumpDDcal
  Cudd_DumpFactoredForm]

******************************************************************************/
int
Cudd_DumpDaVinci(
  DdManager * dd /* manager */,
  int  n /* number of output nodes to be dumped */,
  DdNode ** f /* array of output nodes to be dumped */,
  char ** inames /* array of input names (or NULL) */,
  char ** onames /* array of output names (or NULL) */,
  FILE * fp /* pointer to the dump file */)
{
    DdNode	*support = NULL;
    DdNode	*scan;
    st_table	*visited = NULL;
    int		retval;
    int		i;
    st_generator *gen;
    long	refAddr, diff, mask;

    /* Initialize symbol table for visited nodes. */
    visited = st_init_table(st_ptrcmp, st_ptrhash);
    if (visited == NULL) goto failure;

    /* Collect all the nodes of this DD in the symbol table. */
    for (i = 0; i < n; i++) {
	retval = cuddCollectNodes(Cudd_Regular(f[i]),visited);
	if (retval == 0) goto failure;
    }

    /* Find how many most significant hex digits are identical
    ** in the addresses of all the nodes. Build a mask based
    ** on this knowledge, so that digits that carry no information
    ** will not be printed. This is done in two steps.
    **  1. We scan the symbol table to find the bits that differ
    **     in at least 2 addresses.
    **  2. We choose one of the possible masks. There are 8 possible
    **     masks for 32-bit integer, and 16 possible masks for 64-bit
    **     integers.
    */

    /* Find the bits that are different. */
    refAddr = (long) Cudd_Regular(f[0]);
    diff = 0;
    gen = st_init_gen(visited);
    while (st_gen(gen, (char **) &scan, NULL)) {
	diff |= refAddr ^ (long) scan;
    }
    st_free_gen(gen);

    /* Choose the mask. */
    for (i = 0; (unsigned) i < 8 * sizeof(long); i += 4) {
	mask = (1 << i) - 1;
	if (diff <= mask) break;
    }
    st_free_table(visited);

    /* Initialize symbol table for visited nodes. */
    visited = st_init_table(st_ptrcmp, st_ptrhash);
    if (visited == NULL) goto failure;

    retval = fprintf(fp, "[");
    if (retval == EOF) goto failure;
    /* Call the function that really gets the job done. */
    for (i = 0; i < n; i++) {
	if (onames == NULL) {
	    retval = fprintf(fp,
			     "l(\"f%d\",n(\"root\",[a(\"OBJECT\",\"f%d\")],",
			     i,i);
	} else {
	    retval = fprintf(fp,
			     "l(\"%s\",n(\"root\",[a(\"OBJECT\",\"%s\")],",
			     onames[i], onames[i]);
	}
	if (retval == EOF) goto failure;
	retval = fprintf(fp, "[e(\"edge\",[a(\"EDGECOLOR\",\"%s\"),a(\"_DIR\",\"none\")],",
			 Cudd_IsComplement(f[i]) ? "red" : "blue");
	if (retval == EOF) goto failure;
	retval = ddDoDumpDaVinci(dd,Cudd_Regular(f[i]),fp,visited,inames,mask);
	if (retval == 0) goto failure;
	retval = fprintf(fp, ")]))%s", i == n-1 ? "" : ",");
	if (retval == EOF) goto failure;
    }

    /* Write trailer and return. */
    retval = fprintf(fp, "]\n");
    if (retval == EOF) goto failure;

    st_free_table(visited);
    return(1);

failure:
    if (support != NULL) Cudd_RecursiveDeref(dd,support);
    if (visited != NULL) st_free_table(visited);
    return(0);

} /* end of Cudd_DumpDaVinci */


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

  Synopsis    [Writes a DDcal file representing the argument BDDs.]

  Description [Writes a DDcal file representing the argument BDDs.
  It returns 1 in case of success; 0 otherwise (e.g., out-of-memory or
  file system full).  Cudd_DumpDDcal does not close the file: This
  is the caller responsibility. Cudd_DumpDDcal uses a minimal unique
  subset of the hexadecimal address of a node as name for it.  If the
  argument inames is non-null, it is assumed to hold the pointers to
  the names of the inputs. Similarly for onames.]

  SideEffects [None]

  SeeAlso     [Cudd_DumpDot Cudd_PrintDebug Cudd_DumpBlif Cudd_DumpDaVinci
  Cudd_DumpFactoredForm]

******************************************************************************/
int
Cudd_DumpDDcal(
  DdManager * dd /* manager */,
  int  n /* number of output nodes to be dumped */,
  DdNode ** f /* array of output nodes to be dumped */,
  char ** inames /* array of input names (or NULL) */,
  char ** onames /* array of output names (or NULL) */,
  FILE * fp /* pointer to the dump file */)
{
    DdNode	*support = NULL;
    DdNode	*scan;
    int		*sorted = NULL;
    int		nvars = dd->size;
    st_table	*visited = NULL;
    int		retval;
    int		i;
    st_generator *gen;
    long	refAddr, diff, mask;

    /* Initialize symbol table for visited nodes. */
    visited = st_init_table(st_ptrcmp, st_ptrhash);
    if (visited == NULL) goto failure;

    /* Collect all the nodes of this DD in the symbol table. */
    for (i = 0; i < n; i++) {
	retval = cuddCollectNodes(Cudd_Regular(f[i]),visited);
	if (retval == 0) goto failure;
    }

    /* Find how many most significant hex digits are identical
    ** in the addresses of all the nodes. Build a mask based
    ** on this knowledge, so that digits that carry no information
    ** will not be printed. This is done in two steps.
    **  1. We scan the symbol table to find the bits that differ
    **     in at least 2 addresses.
    **  2. We choose one of the possible masks. There are 8 possible
    **     masks for 32-bit integer, and 16 possible masks for 64-bit
    **     integers.
    */

    /* Find the bits that are different. */
    refAddr = (long) Cudd_Regular(f[0]);
    diff = 0;
    gen = st_init_gen(visited);
    while (st_gen(gen, (char **) &scan, NULL)) {
	diff |= refAddr ^ (long) scan;
    }
    st_free_gen(gen);

    /* Choose the mask. */
    for (i = 0; (unsigned) i < 8 * sizeof(long); i += 4) {
	mask = (1 << i) - 1;
	if (diff <= mask) break;
    }
    st_free_table(visited);

    /* Build a bit array with the support of f. */
    sorted = ALLOC(int,nvars);
    if (sorted == NULL) {
	dd->errorCode = CUDD_MEMORY_OUT;
	goto failure;
    }
    for (i = 0; i < nvars; i++) sorted[i] = 0;

    /* Take the union of the supports of each output function. */
    support = Cudd_VectorSupport(dd,f,n);
    if (support == NULL) goto failure;
    cuddRef(support);
    scan = support;
    while (!cuddIsConstant(scan)) {
	sorted[scan->index] = 1;
	scan = cuddT(scan);
    }
    Cudd_RecursiveDeref(dd,support);
    support = NULL; /* so that we do not try to free it in case of failure */
    for (i = 0; i < nvars; i++) {
        if (sorted[dd->invperm[i]]) {
	    if (inames == NULL || inames[dd->invperm[i]] == NULL) {
		retval = fprintf(fp,"v%d", dd->invperm[i]);
	    } else {
		retval = fprintf(fp,"%s", inames[dd->invperm[i]]);
	    }
            if (retval == EOF) goto failure;
        }
	retval = fprintf(fp,"%s", i == nvars - 1 ? "\n" : " * ");
	if (retval == EOF) goto failure;
    }
    FREE(sorted);
    sorted = NULL;

    /* Initialize symbol table for visited nodes. */
    visited = st_init_table(st_ptrcmp, st_ptrhash);
    if (visited == NULL) goto failure;

    /* Call the function that really gets the job done. */
    for (i = 0; i < n; i++) {
	retval = ddDoDumpDDcal(dd,Cudd_Regular(f[i]),fp,visited,inames,mask);
	if (retval == 0) goto failure;
	if (onames == NULL) {
	    retval = fprintf(fp, "f%d = ", i);
	} else {
	    retval = fprintf(fp, "%s = ", onames[i]);
	}
	if (retval == EOF) goto failure;
	retval = fprintf(fp, "n%lx%s\n",
			 ((long) f[i] & mask) / sizeof(DdNode),
			 Cudd_IsComplement(f[i]) ? "'" : "");
	if (retval == EOF) goto failure;
    }

    /* Write trailer and return. */
    retval = fprintf(fp, "[");
    if (retval == EOF) goto failure;
    for (i = 0; i < n; i++) {
	if (onames == NULL) {
	    retval = fprintf(fp, "f%d", i);
	} else {
	    retval = fprintf(fp, "%s", onames[i]);
	}
	retval = fprintf(fp, "%s", i == n-1 ? "" : " ");
	if (retval == EOF) goto failure;
    }
    retval = fprintf(fp, "]\n");
    if (retval == EOF) goto failure;

    st_free_table(visited);
    return(1);

failure:
    if (sorted != NULL) FREE(sorted);
    if (support != NULL) Cudd_RecursiveDeref(dd,support);
    if (visited != NULL) st_free_table(visited);
    return(0);

} /* end of Cudd_DumpDDcal */


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

  Synopsis    [Writes factored forms representing the argument BDDs.]

  Description [Writes factored forms representing the argument BDDs.
  The format of the factored form is the one used in the genlib files
  for technology mapping in sis.  It returns 1 in case of success; 0
  otherwise (e.g., file system full).  Cudd_DumpFactoredForm does not
  close the file: This is the caller responsibility. Caution must be
  exercised because a factored form may be exponentially larger than
  the argument BDD.  If the argument inames is non-null, it is assumed
  to hold the pointers to the names of the inputs. Similarly for
  onames.]

  SideEffects [None]

  SeeAlso     [Cudd_DumpDot Cudd_PrintDebug Cudd_DumpBlif Cudd_DumpDaVinci
  Cudd_DumpDDcal]

******************************************************************************/
int
Cudd_DumpFactoredForm(
  DdManager * dd /* manager */,
  int  n /* number of output nodes to be dumped */,
  DdNode ** f /* array of output nodes to be dumped */,
  char ** inames /* array of input names (or NULL) */,
  char ** onames /* array of output names (or NULL) */,
  FILE * fp /* pointer to the dump file */)