VIS
|
#include "ordInt.h"
Go to the source code of this file.
Defines | |
#define | STATE_TEST 0 |
#define | STATE_WAIT 1 |
#define | STATE_IN 2 |
#define | MAX_NAME_LENGTH 32768 |
Functions | |
static array_t * | NodeBuildBddLevelArrayFromNtkNode (Ntk_Node_t *node) |
static array_t * | NodeBuildBddIdArrayFromNtkNode (Ntk_Node_t *node) |
static int | IntegersCompare (const void *obj1, const void *obj2) |
static int | NodesCompareBddLevelArray (lsGeneric node1, lsGeneric node2) |
static array_t * | NodeReadBddLevelArray (Ntk_Node_t *node) |
static void | NodeSetBddLevelArray (Ntk_Node_t *node, array_t *bddLevelArray) |
static boolean | NameStringProcess (char *nameString, Ntk_Network_t *network, lsList nodeList, int verbose) |
int | Ord_NetworkPrintVariableOrder (FILE *fp, Ntk_Network_t *network, Ord_OrderType orderType) |
char ** | Ord_NetworkGetCombInputNamesInOrder (Ntk_Network_t *network) |
boolean | Ord_FileReadNodeList (FILE *fp, Ntk_Network_t *network, lsList *nodeList, int verbose) |
int | OrdMakeNewVariableOrder (mdd_manager *mddMgr, lsList suppliedNodeList, int group, int verbose) |
Variables | |
static char rcsid[] | UNUSED = "$Id: ordIo.c,v 1.15 2004/07/28 20:42:10 jinh Exp $" |
static int IntegersCompare | ( | const void * | obj1, |
const void * | obj2 | ||
) | [static] |
Function********************************************************************
Synopsis [Used to sort an array of integers in ascending order.]
SideEffects []
Definition at line 580 of file ordIo.c.
{ int int1 = *(int *) obj1; int int2 = *(int *) obj2; if (int1 < int2) { return -1; } else if (int1 == int2) { return 0; } else { return 1; } }
static boolean NameStringProcess | ( | char * | nameString, |
Ntk_Network_t * | network, | ||
lsList | nodeList, | ||
int | verbose | ||
) | [static] |
Function********************************************************************
Synopsis [Processes the name of a node.]
Description [Processes the name of a node. If there is no node in network with name nameString, then the function writes a message in error_string, and returns FALSE. If the corresponding node is found, then the node is added to the end of nodeList; else, nothing is done. In either case, TRUE is returned.]
SideEffects []
Definition at line 678 of file ordIo.c.
{ Ntk_Node_t *node = Ntk_NetworkFindNodeByActualName(network, nameString); if (node == NIL(Ntk_Node_t)) { error_append("Node not found for name: "); error_append(nameString); error_append("\n"); return FALSE; } if (verbose > 1) { (void) fprintf(vis_stdout, "Reading node: %s\n", Ntk_NodeReadName(node)); } (void) lsNewEnd(nodeList, (lsGeneric) node, LS_NH); return TRUE; }
static array_t * NodeBuildBddIdArrayFromNtkNode | ( | Ntk_Node_t * | node | ) | [static] |
Function********************************************************************
Synopsis [Gets the indices of the BDD variables corresponding to the MDD variable of a node.]
Description [Returns an array (of int's) of the indices of the BDD variables corresponding to the MDD variable of a node. It is the responsibility of the caller to free this array.]
SideEffects []
Definition at line 549 of file ordIo.c.
{ int i, bddId; Ntk_Network_t *network = Ntk_NodeReadNetwork(node); mdd_manager *mddManager = Ntk_NetworkReadMddManager(network); array_t *mvarArray = mdd_ret_mvar_list(mddManager); int mddId = Ntk_NodeReadMddId(node); mvar_type mv; array_t *bddIdArray; mv = array_fetch(mvar_type, mvarArray, mddId); bddIdArray = array_alloc(int, mv.encode_length); for (i = 0; i < mv.encode_length; i++) { bddId = mdd_ret_bvar_id(&mv, i); array_insert_last(int, bddIdArray, bddId); } return (bddIdArray); }
static array_t * NodeBuildBddLevelArrayFromNtkNode | ( | Ntk_Node_t * | node | ) | [static] |
AutomaticStart
Function********************************************************************
Synopsis [Gets the levels of the BDD variables corresponding to the MDD variable of a node.]
Description [Returns an array (of int's) of the levels of the BDD variables corresponding to the MDD variable of a node. The level of a BDD variable is it place in the current variable ordering of the BDD manager. The returned array is sorted in ascending order. It is the responsibility of the caller to free this array.]
SideEffects []
Definition at line 508 of file ordIo.c.
{ int i; Ntk_Network_t *network = Ntk_NodeReadNetwork(node); mdd_manager *mddManager = Ntk_NetworkReadMddManager(network); array_t *mvarArray = mdd_ret_mvar_list(mddManager); int mddId = Ntk_NodeReadMddId(node); mvar_type mv; array_t *bddLevelArray; mv = array_fetch(mvar_type, mvarArray, mddId); bddLevelArray = array_alloc(int, mv.encode_length); for (i = 0; i < mv.encode_length; i++) { int bddId = mdd_ret_bvar_id(&mv, i); bdd_t *varBdd = bdd_get_variable((bdd_manager *) mddManager, bddId); int varLevel = (int) bdd_top_var_level((bdd_manager *) mddManager, varBdd); bdd_free(varBdd); array_insert_last(int, bddLevelArray, varLevel); } array_sort(bddLevelArray, IntegersCompare); return (bddLevelArray); }
static array_t * NodeReadBddLevelArray | ( | Ntk_Node_t * | node | ) | [static] |
Function********************************************************************
Synopsis [Gets the BDD level array of a node.]
SideEffects []
SeeAlso [NodeSetBddLevelArray NodesCompareBddLevelArray]
Definition at line 639 of file ordIo.c.
{ return ((array_t *) Ntk_NodeReadUndef(node)); }
static int NodesCompareBddLevelArray | ( | lsGeneric | node1, |
lsGeneric | node2 | ||
) | [static] |
Function********************************************************************
Synopsis [Used to sort an array of nodes in ascending order of lowest BDD level.]
SideEffects []
Definition at line 608 of file ordIo.c.
{ array_t *bddLevelArray1 = NodeReadBddLevelArray((Ntk_Node_t *) node1); array_t *bddLevelArray2 = NodeReadBddLevelArray((Ntk_Node_t *) node2); int firstLevel1 = array_fetch(int, bddLevelArray1, 0); int firstLevel2 = array_fetch(int, bddLevelArray2, 0); if (firstLevel1 < firstLevel2) { return -1; } else if (firstLevel1 == firstLevel2) { return 0; } else { return 1; } }
static void NodeSetBddLevelArray | ( | Ntk_Node_t * | node, |
array_t * | bddLevelArray | ||
) | [static] |
Function********************************************************************
Synopsis [Sets the BDD level array of a node.]
SideEffects []
SeeAlso [NodeReadBddLevelArray]
Definition at line 656 of file ordIo.c.
{ Ntk_NodeSetUndef(node, (void *) bddLevelArray); }
boolean Ord_FileReadNodeList | ( | FILE * | fp, |
Ntk_Network_t * | network, | ||
lsList * | nodeList, | ||
int | verbose | ||
) |
Function********************************************************************
Synopsis [Returns a list of nodes corresponding to the names in a file.]
Description [Parses a file and builds a node list corresponding to the names found in the first "column" of each line of the file. Any line starting with the comment character '#' or white space is ignored. If a name is found for which there doesn't exist a corresponding node in network, then a message is written to error_string, the partial node list is freed, and the function returns FALSE; otherwise, it returns TRUE, and a pointer to a list is returned.]
Comment [The parser consists of 3 states. See the documentation accompanying the #defines defining the state names.]
SideEffects []
Definition at line 297 of file ordIo.c.
{ int c; int state; int curPosition = 0; boolean status; char nameString[MAX_NAME_LENGTH]; boolean returnFlag = TRUE; *nodeList = lsCreate(); state = STATE_TEST; while ((c = fgetc(fp)) != EOF) { switch (state) { case STATE_TEST: /* At start of a new line. */ if (c == '#') { /* Line starting with comment character; wait for newline */ state = STATE_WAIT; } else if ((c == ' ') || (c == '\t')) { /* Line starting with white space; wait for newline */ state = STATE_WAIT; } else if (c == '\n') { /* Line starting newline; go to next line */ state = STATE_TEST; } else { /* Assume starting a node name. */ curPosition = 0; nameString[curPosition++] = c; state = STATE_IN; } break; case STATE_WAIT: /* * Waiting for the newline character. */ state = (c == '\n') ? STATE_TEST : STATE_WAIT; break; case STATE_IN: /* * Parsing a node name. If white space reached, then terminate the * node name and process it. Else, continue parsing. */ if ((c == ' ') || (c == '\n') || (c == '\t')) { nameString[curPosition] = '\0'; status = NameStringProcess(nameString, network, *nodeList, verbose); if (status == FALSE) { returnFlag = FALSE; } state = (c == '\n') ? STATE_TEST : STATE_WAIT; } else { nameString[curPosition++] = c; if (curPosition >= MAX_NAME_LENGTH) { error_append("maximum node name length exceeded"); returnFlag = FALSE; } state = STATE_IN; /* redundant, but be explicit */ } break; default: fail("unrecognized state"); } } /* * Handle case where EOF terminates a name. */ if (state == STATE_IN) { nameString[curPosition] = '\0'; status = NameStringProcess(nameString, network, *nodeList, verbose); if (status == FALSE) { returnFlag = FALSE; } } if (returnFlag) { return TRUE; } else { (void) lsDestroy(*nodeList, (void (*) (lsGeneric)) NULL); return FALSE; } }
char** Ord_NetworkGetCombInputNamesInOrder | ( | Ntk_Network_t * | network | ) |
Function********************************************************************
Synopsis [Returns a name array of combinational input variables in order.]
SideEffects []
Definition at line 225 of file ordIo.c.
{ lsGen gen; lsList nodeList; Ntk_Node_t *node; int i; char **names; i = 0; nodeList = lsCreate(); Ntk_NetworkForEachNode(network, gen, node) { if (Ntk_NodeTestIsCombInput(node)) { (void) lsNewEnd(nodeList, (lsGeneric) node, LS_NH); i++; } } names = (char **)ALLOC(char *, i); if (!names) return(NULL); /* * For each node in nodeList, get the array of levels of the BDD variables * which make up the MDD variable of node. */ lsForEachItem(nodeList, gen, node) { array_t *bddLevelArray = NodeBuildBddLevelArrayFromNtkNode(node); NodeSetBddLevelArray(node, bddLevelArray); } /* * Sort the nodes of nodeList in ascending order of the lowest level BDD * variable corresponding to a node's MDD variable. */ (void) lsSort(nodeList, NodesCompareBddLevelArray); /* * Write out the nodes in order. */ i = 0; lsForEachItem(nodeList, gen, node) { names[i] = (char *)malloc(strlen(Ntk_NodeReadName(node)) + 1); strcpy(names[i], Ntk_NodeReadName(node)); i++; } (void) lsDestroy(nodeList, (void (*) (lsGeneric)) NULL); return(names); }
int Ord_NetworkPrintVariableOrder | ( | FILE * | fp, |
Ntk_Network_t * | network, | ||
Ord_OrderType | orderType | ||
) |
AutomaticEnd Function********************************************************************
Synopsis [Prints to a file the current ordering of MDD variables.]
Description [Prints to a file all the nodes specified by orderType. OrderType can be one of Ord_All_c, Ord_InputAndLatch_c or Ord_NextStateNode_c (see ord.h for the meaning of these types). For each node, prints the following: name, node type, MDD id, number of values in the range of the node output, and a list of the levels (in the current ordering) of the BDD variables that constitute this multi-valued variable. The nodes are printed to the file in ascending order of the lowest level corresponding BDD variable. If there exists a node in the class specified by orderType that doesn't have an mddId, then the routine writes a message to error_string, and returns 0. In all other cases, it writes to the file and then returns 1. It is the responsibility of the user to close the file.]
SideEffects []
Definition at line 93 of file ordIo.c.
{ lsGen gen; lsList nodeList; Ntk_Node_t *node; int maxNameLength; time_t now; struct tm *nowStructPtr; char *nowTxt; assert((orderType == Ord_All_c) || (orderType == Ord_InputAndLatch_c) || (orderType == Ord_NextStateNode_c)); /* * First, build up a list of all the nodes covered by orderType. */ if (orderType == Ord_All_c) { nodeList = lsCopy(Ntk_NetworkReadNodes(network), (lsGeneric (*) (lsGeneric)) NULL); } else { nodeList = lsCreate(); Ntk_NetworkForEachNode(network, gen, node) { if (Ntk_NodeTestIsNextStateNode(node) || ((orderType == Ord_InputAndLatch_c) && Ntk_NodeTestIsCombInput(node))) { (void) lsNewEnd(nodeList, (lsGeneric) node, LS_NH); } } } /* * As a sanity check, make sure that all the variables in orderType have an * MDD id. */ lsForEachItem(nodeList, gen, node) { if (Ntk_NodeReadMddId(node) == NTK_UNASSIGNED_MDD_ID) { error_append("node "); error_append(Ntk_NodeReadName(node)); error_append(" not ordered\n"); (void) lsFinish(gen); (void) lsDestroy(nodeList, (void (*) (lsGeneric)) NULL); return (0); } } /* * For each node in nodeList, get the array of levels of the BDD variables * which make up the MDD variable of node. */ lsForEachItem(nodeList, gen, node) { array_t *bddLevelArray = NodeBuildBddLevelArrayFromNtkNode(node); NodeSetBddLevelArray(node, bddLevelArray); } /* * Sort the nodes of nodeList in ascending order of the lowest level BDD * variable corresponding to a node's MDD variable. */ (void) lsSort(nodeList, NodesCompareBddLevelArray); /* * Compute the maximum length of a node name, for pretty printing. */ maxNameLength = 0; lsForEachItem(nodeList, gen, node) { int nameLength = strlen(Ntk_NodeReadName(node)); maxNameLength = (nameLength > maxNameLength) ? nameLength : maxNameLength; } /* * Write out the header for the output file. */ now = time(0); nowStructPtr = localtime(& now); nowTxt = asctime(nowStructPtr); (void) fprintf(fp, "# %s\n", Vm_VisReadVersion()); (void) fprintf(fp, "# network name: %s\n", Ntk_NetworkReadName(network)); (void) fprintf(fp, "# generated: %s", nowTxt); (void) fprintf(fp, "#\n"); (void) fprintf(fp, "# %-*s type mddId vals levs\n", maxNameLength, "name"); /* * Write out the nodes in order. */ lsForEachItem(nodeList, gen, node) { int i; array_t *bddLevelArray = NodeReadBddLevelArray(node); char *nodeType = Ntk_NodeObtainTypeAsString(node); (void) fprintf(fp, "%-*s %-16s %5d %4d ", maxNameLength, Ntk_NodeReadName(node), nodeType, Ntk_NodeReadMddId(node), Var_VariableReadNumValues(Ntk_NodeReadVariable(node))); FREE(nodeType); (void) fprintf(fp, "("); for (i = 0; i < array_n(bddLevelArray); i++) { int level = array_fetch(int, bddLevelArray, i); if (i == 0) { (void) fprintf(fp, "%d", level); } else { (void) fprintf(fp, ", %d", level); } } (void) fprintf(fp, ")\n"); array_free(bddLevelArray); } (void) lsDestroy(nodeList, (void (*) (lsGeneric)) NULL); return (1); }
int OrdMakeNewVariableOrder | ( | mdd_manager * | mddMgr, |
lsList | suppliedNodeList, | ||
int | group, | ||
int | verbose | ||
) |
Function********************************************************************
Synopsis [Makes new variable order.]
Description [Makes new variable order. Returns 1 if not successful.]
SideEffects []
Definition at line 406 of file ordIo.c.
{ int i, nVars; int *invPerm = NIL(int); int *groupInfo = NIL(int); int length, bddId, mvLen; lsGen gen; Ntk_Node_t *node; array_t *bddIdArray; char *name = NIL(char), *prevName = NIL(char), *longName; int len1, len2, minLen; nVars = bdd_num_vars(mddMgr); invPerm = ALLOC(int, nVars); length = 0; if (group) { prevName = NIL(char); groupInfo = ALLOC(int, nVars); memset(groupInfo, 0, sizeof(int) * nVars); } lsForEachItem(suppliedNodeList, gen, node) { bddIdArray = NodeBuildBddIdArrayFromNtkNode(node); mvLen = array_n(bddIdArray); if (group) { name = Ntk_NodeReadName(node); if (prevName) { len1 = strlen(prevName); len2 = strlen(name); if (len1 < len2) { minLen = len1; longName = name; } else { minLen = len2; longName = prevName; } if (strncmp(name, prevName, minLen) == 0) { if (strcmp(longName + minLen, "$NS") == 0) groupInfo[length - mvLen] = mvLen * 2; } } } for (i = 0; i < mvLen; i++) { bddId = array_fetch(int, bddIdArray, i); invPerm[length] = bddId; length++; } array_free(bddIdArray); if (group) prevName = name; } if (length != nVars) { fprintf(vis_stderr, "** ord error: the number of variables does not match\n"); FREE(invPerm); if (group) FREE(groupInfo); return(1); } bdd_discard_all_var_groups(mddMgr); bdd_shuffle_heap(mddMgr, invPerm); if (group) { mdd_t *var; for (i = 0; i < nVars; i++) { if (groupInfo[i]) { var = bdd_var_with_index(mddMgr, invPerm[i]); bdd_new_var_block(var, groupInfo[i]); i += groupInfo[i] - 1; } } FREE(groupInfo); } FREE(invPerm); return(0); }
char rcsid [] UNUSED = "$Id: ordIo.c,v 1.15 2004/07/28 20:42:10 jinh Exp $" [static] |
CFile***********************************************************************
FileName [ordIo.c]
PackageName [ord]
Synopsis [Routines to read and write variable orderings.]
Author [Adnan Aziz, Tom Shiple]
Copyright [Copyright (c) 1994-1996 The Regents of the Univ. of California. All rights reserved.
Permission is hereby granted, without written agreement and without license or royalty fees, to use, copy, modify, and distribute this software and its documentation for any purpose, provided that the above copyright notice and the following two paragraphs appear in all copies of this software.
IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]