/**CFile*********************************************************************** FileName [ tblUtil.c ] PackageName [ tbl ] Synopsis [ This package is used to manipulate the table data structure ] Description [ The table data structure is used to store the information contained in the blif_mv table. This structure supports all constructs in blif_mv including the recursive constructs. This is consistent with the previous version of this data- structure. Note that the table package is in no way concerned with the semantics of the table constructed; it makes no interpretation on the correctness of a table (i.e. does it represent valid hardware)] SeeAlso [ tbl.h, tblEntryUtil.c ] Author [ Gitanjali M. Swamy ] 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.] ******************************************************************************/ #include "tblInt.h" static char rcsid[] UNUSED = "$Id: tblUtil.c,v 1.19 2009/04/11 02:01:29 fabio Exp $"; /*---------------------------------------------------------------------------*/ /* Type declarations */ /*---------------------------------------------------------------------------*/ /* Structure used to sort table inputs. */ typedef struct varOrdStruct { int id; /* input column number */ int rank; /* low-ranked columns should go first */ } Var_Ord_t; /**AutomaticStart*************************************************************/ /*---------------------------------------------------------------------------*/ /* Static function prototypes */ /*---------------------------------------------------------------------------*/ static int TableEntryComputeHashVal(Tbl_Table_t *table, Tbl_Entry_t *entry); static array_t* TableCreatIntArray(int size); static char* TableObtainSignature(Tbl_Table_t * table, int outputColumn); static int varCompare(const void *x, const void *y); /**AutomaticEnd***************************************************************/ /*---------------------------------------------------------------------------*/ /* Definition of exported functions */ /*---------------------------------------------------------------------------*/ /**Function*********************************************************** Synopsis [ Allocate a new table. ] Description [ This functions allocates memory for and returns a new table ] SideEffects [ ] SeeAlso [ Tbl_Free ] **********************************************************************/ Tbl_Table_t* Tbl_TableAlloc(void) { Tbl_Table_t * table; table = ALLOC(Tbl_Table_t,1); table->inputNames = array_alloc(Var_Variable_t*,0); table->outputNames = array_alloc(Var_Variable_t*,0); table->data = ALLOC(Tbl_Data_t,1); TblTableReadDefaults(table) = array_alloc(Tbl_Entry_t*,0); TblTableReadRefCount(table) = 1; TblTableReadData(table) = array_alloc(Tbl_Row_t*,0); return table; } /**Function*********************************************************** Synopsis [ Free a table. ] Description [ Given a table, this routine decreases the table refcount. If the refCount == 1 then it also frees it, i.e. it also frees each and every Tbl_Entry_t entry in the table ] SideEffects [ Does not free the Vars associated with the table. This is the responsibility of the user.] SeeAlso [ Tbl_Alloc ] **********************************************************************/ void Tbl_TableFree( Tbl_Table_t * table /* The table to be freed */) { int i,j,k; Tbl_Row_t * row; Tbl_Entry_t *entry; if (table != NIL(Tbl_Table_t)) { if (TblTableReadRefCount(table) < 2) { Tbl_TableForEachEntry(table,j,i,k,entry) { if (entry != NIL(Tbl_Entry_t)) { Tbl_EntryFree(entry); } } TblTableForEachRow(table,row,i){ array_free(row->inputs); array_free(row->outputs); FREE(row); } Tbl_TableForEachDefaultEntry(table,entry,i) { if (entry != NIL(Tbl_Entry_t)) { Tbl_EntryFree(entry); } } array_free(TblTableReadDefaults(table)); array_free(TblTableReadData(table)); FREE(table->data); } else { TblTableReadRefCount(table)--;; } array_free(table->inputNames); array_free(table->outputNames); FREE(table); } } /**Function*********************************************************** Synopsis [ Soft Duplicate a table. ] Description [ This routines increases the refcounts of the table. ] SideEffects [ Do not modify the soft duplicate tables's entries; it will modify the original table. For this use Tbl_TableHardDup] SeeAlso [ Tbl_TableFree Tbl_TableHardDup] **********************************************************************/ Tbl_Table_t * Tbl_TableSoftDup( Tbl_Table_t * table /* The table to be duplicated */) { Tbl_Table_t *tabledup; assert(TblTableReadRefCount(table) >0); tabledup = ALLOC(Tbl_Table_t,1); tabledup->data = table->data; tabledup->inputNames = array_dup(table->inputNames); tabledup->outputNames = array_dup(table->outputNames); TblTableReadRefCount(table) ++; return tabledup; } /**Function*********************************************************** Synopsis [ Duplicate a table. ] Description [ This routines creates a duplicate of table. However table entries are copied, but not Vars. ] SideEffects [ ] SeeAlso [ Tbl_TableFree Tbl_TableSoftDup] **********************************************************************/ Tbl_Table_t * Tbl_TableHardDup( Tbl_Table_t * table /* The table to be duplicated */) { Tbl_Table_t * tabledup; int i; Tbl_Entry_t *newEntry, *entry; Var_Variable_t *var; Tbl_Row_t *row; tabledup = Tbl_TableAlloc(); Tbl_TableForEachInputVar(table,i,var){ Tbl_TableAddColumn(tabledup,var,0); } Tbl_TableForEachOutputVar(table,i,var){ Tbl_TableAddColumn(tabledup,var,1); } Tbl_TableForEachDefaultEntry(table,entry,i) { if (entry != NIL(Tbl_Entry_t)) { newEntry = Tbl_EntryDup(entry); } else { newEntry = NIL(Tbl_Entry_t); } (void) Tbl_TableDefaultSetEntry(tabledup,newEntry,i); } TblTableForEachRow(table,row,i){ TblTableSetRow(tabledup,TblRowDup(row),i); } return tabledup; } /**Function******************************************************************** Synopsis [Set the default value at given index] Description [Given a Tbl_Table_t, a default Tbl_Entry_t and an index, this sets the value of the default at this index to the entry. If the value of the index is larger than the default array size, this return a 0, else it sets the value and returns a 1.] SideEffects [] SeeAlso [Tbl_TableDefaultReadEntry] ******************************************************************************/ boolean Tbl_TableDefaultSetEntry( Tbl_Table_t *table, Tbl_Entry_t *entry, int index) { if (TblTableReadRefCount(table) > 1) { printf(" WARNING: You are modifying more than one table by re-setting this entry\n"); } if (array_n(TblTableReadDefaults(table)) < index) { return FALSE; } if (entry != NIL(Tbl_Entry_t)) { entry->ioType = 1; entry->varColNum = index; /* debug */ if (entry->type == Tbl_EntryEqual_c) assert(Tbl_EntryReadVarIndex(entry) < Tbl_TableReadNumInputs(table)); } array_insert(Tbl_Entry_t*, TblTableReadDefaults(table),index,entry); return TRUE; } /**Function******************************************************************** Synopsis [Read the default value at given index] Description [Given a Tbl_Table_t and an index, this reads the value of the default entry, and returns it. If the index is larger than the array size, it returns a NIL entry] SideEffects [] SeeAlso [Tbl_TableDefaultSetEntry] ******************************************************************************/ Tbl_Entry_t* Tbl_TableDefaultReadEntry( Tbl_Table_t *table, int index) { if (array_n(TblTableReadDefaults(table)) < index) { return NIL(Tbl_Entry_t); } return (array_fetch(Tbl_Entry_t*, TblTableReadDefaults(table),index)); } /**Function*********************************************************** Synopsis [ Add an empty row (logically inert) to table. ] Description [ Given a table this function adds an empty row at the end of the table. It return the index of the row it creates] SideEffects [ Table has changed, and the one new row needs to be filled in ] SeeAlso [ optional ] **********************************************************************/ int Tbl_TableAddRow( Tbl_Table_t * table) { Tbl_Row_t * row; int i; if (table != NIL(Tbl_Table_t)) { if (TblTableReadRefCount(table) > 1) { printf(" WARNING: You are modifying more than one table by adding this row\n"); } row = ALLOC(Tbl_Row_t,1); row->inputs = array_alloc(Tbl_Entry_t*,0); for (i=0; i < array_n(table->inputNames); i++) { array_insert_last(Tbl_Entry_t*,row->inputs, NIL(Tbl_Entry_t)); } row->outputs = array_alloc(Tbl_Entry_t*,0); for (i=0; i < array_n(table->outputNames); i++) { array_insert_last(Tbl_Entry_t*,row->outputs, NIL(Tbl_Entry_t)); } array_insert_last(Tbl_Row_t*, TblTableReadData(table),row); return ( array_n(TblTableReadData(table)) -1); } else return -1; } /**Function*********************************************************** Synopsis [ Add an empty column with the given Var ] Description [ Given a table this function adds an empty column at the end of all columns, associates this column with a Var_Variable_t (Var). It returns the number of (input or output) columns in the table. If the operation fails, the program is exited. It must also be supplied with a flag to indicate whether an input or output entry is being read. It is the users responsibility to ensure that the same var is not already present; the table package is not concerned with the semantics of the table.] SideEffects [ ] SeeAlso [ optional ] **********************************************************************/ int Tbl_TableAddColumn( Tbl_Table_t * table /* the table */, Var_Variable_t * var /* the Var being added */, int flag /* This flag is set to 0 if it is an input and 1 if it is and output */) { int i, index; Tbl_Row_t *row; array_t *carray; assert(table !=NIL(Tbl_Table_t)); assert((flag==0)||(flag ==1)); if (TblTableReadRefCount(table) > 1) { printf(" WARNING: You may be modifying more than one table by adding this column\n"); } index = 0; for (i=0; i< array_n(TblTableReadData(table)); i++) { row = array_fetch(Tbl_Row_t*,TblTableReadData(table),i); if (flag==0) { carray = row->inputs; } else { carray = row->outputs; } array_insert_last(Tbl_Entry_t*,carray,NIL(Tbl_Entry_t)); } if (flag==0) { array_insert_last(Var_Variable_t*, table->inputNames, var); index = array_n(table->inputNames); } else { array_insert_last(Var_Variable_t*, table->outputNames, var); index = array_n(table->outputNames); array_insert_last(Tbl_Entry_t*, TblTableReadDefaults(table),NIL(Tbl_Entry_t)); } return index; } /**Function******************************************************************** Synopsis [Deletes specified row of table] Description [Deletes a specified row of the table. It creates a new table, and copies all but the the specified row into the new table, and points the original table pointer to the new table. The original table is freed] SideEffects [] SeeAlso [] ******************************************************************************/ Tbl_Table_t * Tbl_TableRowDelete( Tbl_Table_t *originalTable, int rowNumToDelete, array_t *freeArray ) { Tbl_Table_t *newTable; int i, rownum, newRowNum, numInputs, numOutputs; Var_Variable_t *var, *newVar; Tbl_Row_t *row UNUSED; Tbl_Entry_t *newEntry, *origEntry, *entry, *dupEntry; newTable = Tbl_TableAlloc(); Tbl_TableForEachInputVar(originalTable, i, var){ newVar = Var_VariableDup(var, NIL(Hrc_Node_t)); array_insert_last(Var_Variable_t *, freeArray, newVar); (void) Tbl_TableAddColumn(newTable, newVar, 0); } Tbl_TableForEachOutputVar(originalTable, i, var){ newVar = Var_VariableDup(var, NIL(Hrc_Node_t)); array_insert_last(Var_Variable_t *, freeArray, newVar); (void) Tbl_TableAddColumn(newTable, newVar, 1); } for(i = 0; i < Tbl_TableReadNumOutputs(originalTable); i++){ entry = Tbl_TableDefaultReadEntry(originalTable, i); if(entry != NIL(Tbl_Entry_t)){ dupEntry = Tbl_EntryDup(entry); Tbl_TableDefaultSetEntry(newTable, dupEntry, i); } } numInputs = Tbl_TableReadNumInputs(originalTable); numOutputs = Tbl_TableReadNumOutputs(originalTable); TblTableForEachRow(originalTable, row, rownum){ if(rownum != rowNumToDelete){ newRowNum = Tbl_TableAddRow(newTable); for(i = 0; i < numInputs; i++){ origEntry = Tbl_TableReadEntry(originalTable, rownum, i, 0); newEntry = Tbl_EntryDup(origEntry); Tbl_TableSetEntry(newTable, newEntry, newRowNum, i, 0); } for(i = 0; i < numOutputs; i++){ origEntry = Tbl_TableReadEntry(originalTable, rownum, i, 1); newEntry = Tbl_EntryDup(origEntry); Tbl_TableSetEntry(newTable, newEntry, newRowNum, i, 1); } } } Tbl_TableFree(originalTable); return newTable; } /**Function*********************************************************** Synopsis [ Find the Var of the variable (column) associated with the given index. ] Description [ Given an index , this functions returns the Var of the column that is represented by. If any of the input data is incorrect it exits the program. It must also be supplied with a flag to indicate whether an input or output entry is being read.] SideEffects [ ] SeeAlso [ optional ] **********************************************************************/ Var_Variable_t* Tbl_TableReadIndexVar( Tbl_Table_t * table, int index, int flag /* Set to 0 if it is an input Var and 1 if it an output Var */ ) { array_t *carray; assert(table !=NIL(Tbl_Table_t)); assert((flag==0)||(flag ==1)); if (flag==0) { carray = table->inputNames; } else { carray = table->outputNames; } return (array_fetch(Var_Variable_t*,carray,index)); } /**Function******************************************************************** Synopsis [ Returns the entry in row i, input/output column j, ] Description [ This function returns the table entry at row i and column j. The item is of the Tbl_Entry_t. The flag indicates whether it is an input (flag = 0) or and output (flag =1) item. If any of the input data is incorrect it exits the program] SideEffects [ ] SeeAlso [ optional ] ******************************************************************************/ Tbl_Entry_t * Tbl_TableReadEntry( Tbl_Table_t * table , int rowNum, int colNum, int flag ) { Tbl_Row_t *row; Tbl_Entry_t *entry; assert(table !=NIL(Tbl_Table_t)); assert((flag==0)||(flag ==1)); row = TblTableReadRow(table,rowNum); entry = TblRowReadEntry(row,colNum,flag); return entry; } /**Function******************************************************************** Synopsis [ Sets the entry in row i, input/output column j to given entry ] Description [ This function sets the table entry at row i and column j to given Tbl_Entry_t. The flag indicates whether it is an input or and output item. If any of the input data is incorrect it return a FALSE] SideEffects [ Old Value is lost ] SeeAlso [ optional ] ******************************************************************************/ boolean Tbl_TableSetEntry( Tbl_Table_t * table /* The Table to be examined */, Tbl_Entry_t * newEntry, int i /* Row Id */, int j /* Column Id */, int flag /* flag indicating whether it is an input or output */) { Tbl_Row_t *row; Tbl_Entry_t *entry; assert(table !=NIL(Tbl_Table_t)); assert((flag==0)||(flag ==1)); if (TblTableReadRefCount(table) > 1) { printf(" WARNING: You are modifying more than one table by re-setting this entry\n"); } entry = Tbl_TableReadEntry(table ,i,j,flag); if (entry != NIL(Tbl_Entry_t)) { Tbl_EntryFree(entry); } row = TblTableReadRow(table,i); newEntry->ioType = flag; newEntry->varColNum = j; TblRowSetEntry(row,newEntry,j,flag); return TRUE; } /**Function******************************************************************** Synopsis [ Sets the entry in row i, column j, to a don't care. ] Description [ This function sets the table entry at row i and column j. The item is of the Tbl_Entry_t. The flag indicates whether it is an input or and output item. If any of the input data is incorrect it exits the program] SideEffects [ ] SeeAlso [ Tbl_EntrySetValue ] ******************************************************************************/ boolean Tbl_TableSetEntryDc( Tbl_Table_t * table, int i, int j, int flag) { array_t *ioarray; int range; Tbl_Entry_t *entry; assert(table !=NIL(Tbl_Table_t)); assert((flag==0)||(flag ==1)); if (TblTableReadRefCount(table) > 1) { printf(" WARNING: You are modifying more than one table by re-setting this entry\n"); } if (flag==0) { ioarray = table->inputNames; } else { ioarray = table->outputNames; } range = Var_VariableReadNumValues(array_fetch(Var_Variable_t*,ioarray,j)); entry = Tbl_TableReadEntry(table,i,j,flag); Tbl_EntrySetValue(entry,0,range-1); return TRUE; } /**Function******************************************************************** Synopsis [ Adds the range val1-val2 to the union in row i, column j. ] Description [ This function when supplied with row i,col j, a table and a range specified by integers val1 and val2, will add range val1-val2 to the i,j th entry in the table. It must also be supplied with a flag to indicate whether an input or output entry is being read.] SideEffects [ ] SeeAlso [ ] ******************************************************************************/ void Tbl_TableAddEntryRange( Tbl_Table_t * table, int i, int j, int val1, int val2, int flag) { Tbl_Entry_t *entry; if (TblTableReadRefCount(table) > 1) { printf(" WARNING: You are modifying more than one table by changing the re-setting this entry\n"); } entry = Tbl_TableReadEntry(table,i,j,flag); Tbl_EntrySetValue(entry,val1,val2); } /**Function******************************************************************** Synopsis [ Complements the constant or union in row i, input/output column j. ] Description [ This function whether supplied with row i,col j, a table will complement the i,j th entry in the table. It must also be supplied with a flag to indicate whether an input or output entry is being read.] SideEffects [ ] SeeAlso [ optional ] ******************************************************************************/ void Tbl_TableComplementEntry( Tbl_Table_t * table, int i, int j, int flag) { Tbl_Entry_t *entry; entry = Tbl_TableReadEntry(table,i,j,flag); Tbl_EntryComplement(entry,0,(Var_VariableReadNumValues(Tbl_EntryReadActualVar(table, entry))) -1 ); } /**Function******************************************************************** Synopsis [ Sets the io entry row i, output column j to be equal to the given Var. ] Description [ This function sets the entry in row i and column j to be equal to the entry specified by the given var] SideEffects [ ] SeeAlso [ ] ******************************************************************************/ void Tbl_TableSetEquality( Tbl_Table_t * table, int i, int j, int flag, Var_Variable_t * var) { Tbl_Entry_t *entry; int index,check; Var_Variable_t *tblVar; check =0; entry = Tbl_TableReadEntry(table,i,j,flag); Tbl_TableForEachInputVar(table, index,tblVar) { if (tblVar == var) { Tbl_EntrySetEqual(entry,index); check =1; break; } } if (check == 0) { printf(" WARNING: Output Equal Another Output not supported, no change made\n "); } } /**Function******************************************************************** Synopsis [ Returns 1 if the entry in row i, input/output column j is a don't care. ] Description [ This function returns 1 if the entry in row i and col j is a DC, 0 if it isn't and -1 if it does not exist. It must also be supplied with a flag to indicate whether an input or output entry is being read.] SideEffects [ ] SeeAlso [ optional ] ******************************************************************************/ boolean Tbl_TableEntryIsDc( Tbl_Table_t * table, int i, int j, int flag) { Tbl_Range_t *range; Tbl_Entry_t *entry; lsGen gen; Var_Variable_t *var; assert(table !=NIL(Tbl_Table_t)); entry = Tbl_TableReadEntry(table,i,j,flag); if (lsLength(entry->EntryData.listOfRanges) == 1){ var = Tbl_EntryReadActualVar(table,entry); lsForEachItem(entry->EntryData.listOfRanges, gen, range) { if ((range->begin ==0)&&(range->end == Var_VariableReadNumValues(var)-1)){ lsFinish(gen); return TRUE; } } } return FALSE; } /**Function******************************************************************** Synopsis [ Returns TRUE if the output designated by outputColumnId is a constant. ] Description [ Returns TRUE if the table has no inputs, and exactly one row, and the output entry in row 0 and column outputColumnId is of type normal and takes exactly one value. Note that this test is conservative, because it does not take into account Boolean redundancies. It merely checks for one of the following conditions 1) the table has no inputs and a constant output 2) the table has only - inputs in the one row and the output is constant 3) the table is empty and the default value for the output is constant and 4) the table output has the same constant value for all inputs] SideEffects [ ] SeeAlso [ Tbl_TableTestIsNonDeterministicConstant ] ******************************************************************************/ boolean Tbl_TableTestIsConstant( Tbl_Table_t * table, int outputColumnId) { int colNum, rowNum; boolean check; Tbl_Entry_t *entry; Var_Variable_t *var; Tbl_Range_t *range; lsGen gen; int value, constant,count; assert(table !=NIL(Tbl_Table_t)); assert((outputColumnId >= 0) && (outputColumnId < Tbl_TableReadNumOutputs(table))); if (Tbl_TableReadNumRows(table) == 1) { if (array_n(table->inputNames) == 0) { entry = Tbl_TableReadEntry(table, 0, outputColumnId, 1); if (entry->type == Tbl_EntryNormal_c) { if (Tbl_EntryReadNumValues(entry) == 1) { return TRUE; } } } else { check = TRUE; Tbl_TableForEachInputEntry(table,rowNum,colNum,entry) { if (entry->type != Tbl_EntryNormal_c) { return FALSE; } if (check == TRUE) { check = FALSE; if (lsLength(entry->EntryData.listOfRanges) == 1){ var = Tbl_EntryReadActualVar(table,entry); lsForEachItem(entry->EntryData.listOfRanges, gen, range) { if ((range->begin ==0)&&(range->end == Var_VariableReadNumValues(var)-1)){ check = TRUE; } } } } } if (check) { entry = Tbl_TableReadEntry(table,0,outputColumnId,1); if (entry->type != Tbl_EntryNormal_c) { return FALSE; } if (Tbl_EntryReadNumValues(entry) == 1) { return TRUE; } } } } else if (Tbl_TableReadNumRows(table) == 0) { entry = Tbl_TableDefaultReadEntry(table,outputColumnId); if (entry->type != Tbl_EntryNormal_c) { return FALSE; } if (Tbl_EntryReadNumValues(entry) == 1) { return TRUE; } } else { entry = Tbl_TableDefaultReadEntry(table,outputColumnId); if (entry == NIL(Tbl_Entry_t)){ constant = -1; Tbl_TableForEachOutputEntry(table,rowNum,colNum,entry) { if (colNum == outputColumnId) { if (entry->type != Tbl_EntryNormal_c){ return FALSE; } count = 1; Tbl_EntryForEachValue(entry,value,gen,range) { lsStatus status; if (count > 1) { status = lsFinish(gen); assert(status == LS_OK); return FALSE; } else { if (constant != -1) { if (constant != value) { status = lsFinish(gen); assert(status == LS_OK); return FALSE; } } else { constant = value; } } count ++; } } } return TRUE; } } return FALSE; } /**Function******************************************************************** Synopsis [ Returns TRUE if the output designated by outputColumnId is a nondeterministic constant. ] Description [ Returns TRUE if the table has no inputs, and the output referred to by outputColumnId is not a constant. ] SideEffects [ ] SeeAlso [ Tbl_TableTestIsConstant ] ******************************************************************************/ boolean Tbl_TableTestIsNonDeterministicConstant( Tbl_Table_t * table, int outputColumnId) { assert(table !=NIL(Tbl_Table_t)); if (array_n(table->inputNames) == 0) { if (!Tbl_TableTestIsConstant(table, outputColumnId)) { return TRUE; } } return FALSE; } /**Function******************************************************************** Synopsis [ Returns TRUE if the table is deterministic. ] Description [ This implements a sufficient but not necessary check for determinism. It intersects every pair of inputs rows and compares the outputs to see if they are identical.] SideEffects [ ] SeeAlso [ optional ] ******************************************************************************/ int Tbl_TableTestIsDeterministic( Tbl_Table_t * table) { /* intersect every pair of input rows and then compare outputs if they're not same --- */ /* Sunil Khatri is implementing this */ return 0; } /**Function******************************************************************** Synopsis [Test if given table has a completely specified output space] Description [Given a table, this function will check if the given output has a completely specified output space, i.e. each output combination is present in the table. If this function is called on a table with inputs, it fails and exits. ] SideEffects [required] SeeAlso [optional] ******************************************************************************/ boolean Tbl_TableTestIsOutputSpaceComplete( Tbl_Table_t *table, mdd_manager *mddMgr) { int i, offset,rowNum,colNum,oldRowNum; boolean check; Mvf_Function_t *mvf; mdd_t *temp, *result, *function, *x; Var_Variable_t *var; Tbl_Entry_t *entry; array_t *faninMvfArray ; array_t *mvarValues ; int numOutputs; if (Tbl_TableReadNumInputs(table) != 0) { return FALSE; } x = NIL(mdd_t); faninMvfArray = array_alloc(Mvf_Function_t *, 0); mvarValues = array_alloc(int, 0); numOutputs = Tbl_TableReadNumOutputs(table ); /* Add mdd's for new table input variables. */ Tbl_TableForEachOutputVar(table, colNum, var) { array_insert_last(int, mvarValues, Var_VariableReadNumValues(var)); } offset = array_n(mdd_ret_mvar_list(mddMgr)); mdd_create_variables(mddMgr,mvarValues, NIL(array_t), NIL(array_t)); array_free(mvarValues); /* * Construct an MVF for each table input. The MVF for column i is the MVF * for MDD variable i. */ for (i = 0; i < numOutputs; i++) { Mvf_Function_t *faninMvf = Mvf_FunctionCreateFromVariable(mddMgr, (i+offset)); array_insert_last(Mvf_Function_t *, faninMvfArray, faninMvf); } /* Compute the MVF of the outputs */ /* iterate over output part and compute all mvf's of rows */ /* add to total */ function = mdd_zero(mddMgr); oldRowNum = -1; result = mdd_zero(mddMgr); Tbl_TableForEachOutputEntry(table,rowNum,colNum,entry) { if (rowNum != oldRowNum) { temp =function; function = mdd_or(temp,result, 1,1); mdd_free(temp); mdd_free(result); result = mdd_one(mddMgr); } if (entry->type == Tbl_EntryNormal_c) { mvf = array_fetch(Mvf_Function_t*,faninMvfArray,colNum); x = TblEntryNormalConstructMdd(mddMgr,entry,mvf); } else if (entry->type == Tbl_EntryEqual_c) { printf("Failure: output equal to another output construct not supported\n"); assert(FALSE); } temp = result; result = mdd_and(x,temp,1,1); mdd_free(x); mdd_free(temp); oldRowNum = rowNum; } temp =function; function = mdd_or(temp,result, 1,1); mdd_free(temp); mdd_free(result); check = mdd_is_tautology(function,1); mdd_free(function); for (i=0;i < array_n(faninMvfArray); i++){ Mvf_FunctionFree(array_fetch(Mvf_Function_t *,faninMvfArray,i)); } array_free(faninMvfArray); return check; } /**Function******************************************************************** Synopsis [Computes the inputs in the true support of a given output of a table.] Description [Computes the inputs in the true support of a given output of a table. This is done by building the MVF for the output in terms of the MVFs of the inputs, where each input is treated as a free variable. Next the function Mvf_FunctionComputeSupport is called on the mvf. The support is returned as an array of integers corresponding to the input columns in the true support. This function must also be supplied with an mdd_manager. If the output is a constant, then this function returns a NIL(array_t), and puts the constant value in the int *value that is passed in.] SideEffects [It is the user's responsibility to free the mdd_manager supplied, (use mdd_quit)] SeeAlso [Tbl_TableBuildMvfFromFanins] ******************************************************************************/ array_t * Tbl_TableComputeMvfAndInputDependenciesOfOutput( Tbl_Table_t *table, mdd_manager *mddMgr, int outIndex, int *value) { int i, offset; Mvf_Function_t *outMvf; Var_Variable_t *var; int colNum; array_t *faninMvfArray = array_alloc(Mvf_Function_t *, 0); array_t *mvarValues = array_alloc(int, 0); array_t *totalSupportArray = array_alloc(int, 0); int numInputs = Tbl_TableReadNumInputs(table ); /* Add mdd's for new table input variables. */ Tbl_TableForEachInputVar(table, colNum, var) { array_insert_last(int, mvarValues, Var_VariableReadNumValues(var)); } offset = array_n(mdd_ret_mvar_list(mddMgr)); mdd_create_variables(mddMgr,mvarValues, NIL(array_t), NIL(array_t)); array_free(mvarValues); /* * Construct an MVF for each table input. The MVF for column i is the MVF * for MDD variable i. */ for (i = 0; i < numInputs; i++) { Mvf_Function_t *faninMvf = Mvf_FunctionCreateFromVariable(mddMgr, (i+offset)); array_insert_last(Mvf_Function_t *, faninMvfArray, faninMvf); } /* Compute the MVF of the output indexed by outIndex. */ outMvf = Tbl_TableBuildMvfFromFanins(table, outIndex, faninMvfArray, mddMgr); Mvf_FunctionArrayFree(faninMvfArray); totalSupportArray = Mvf_FunctionComputeSupport(outMvf,mddMgr,value); Mvf_FunctionFree(outMvf); return totalSupportArray; } /**Function******************************************************************** Synopsis [Given an output column (and maybe its mvf) return a table with the true support inputs of the given output.] Description [If a NIL(Mvf_Function_t) is supplied as input to this function , it uses Tbl_TableComputeMvfAndInputDependenciesOfOutput to compute the true support of the given output (outIndex), and then creates a new table for this output with only the true inputs. Given a non-nil Mvf of the table output, this function uses Mvf_FunctionComputeSupport to compute the true support of the given output (index), and then creates a new table for this output with only the true inputs. It returns the new table for the output of given index. If the output is a constant, then this function returns a constant table. If a non-nil mvf is supplied, then the function must also be supplied with an int offset, such that for mddid of column j is (j+offset) in the mvf supplied.] SideEffects [Variables may be added to the mdd manager] SeeAlso [Tbl_TableComputeMvfAndInputDependenciesOfOutput] ******************************************************************************/ Tbl_Table_t* Tbl_TableCreateTrueSupportTableForOutput( Tbl_Table_t *table, Mvf_Function_t *outMvf, mdd_manager *mddMgr, int offset, int outIndex, array_t *varMap /* maps input column to mdd id */ ) { array_t *support; Tbl_Table_t * newTable; int i, inputId, rowNum, colNum, newColNum, newEqColNum, value, eqColNum; Tbl_Entry_t *newEntry, *entry; Var_Variable_t *var; Tbl_Row_t *row UNUSED; st_table *supLookup; newTable = Tbl_TableAlloc(); /* compute dependancies and put in a hash table */ if (outMvf != NIL(Mvf_Function_t)) { support = Mvf_FunctionComputeSupport(outMvf,mddMgr,&value); } else { offset = array_n(mdd_ret_mvar_list(mddMgr)); support = Tbl_TableComputeMvfAndInputDependenciesOfOutput(table,mddMgr,outIndex,&value); } if(support == NIL(array_t)) { /* create a constant table */ var = Tbl_TableReadIndexVar(table,outIndex,1); Tbl_TableAddColumn(newTable,var,1); i = Tbl_TableAddRow(newTable); newEntry = Tbl_EntryAlloc(Tbl_EntryNormal_c); Tbl_TableSetEntry(newTable, newEntry, 0, 0, 1); Tbl_TableAddEntryRange(newTable,0,0,value,value,1); newEntry = NIL(Tbl_Entry_t); (void) Tbl_TableDefaultSetEntry(newTable,newEntry,0); return newTable; } supLookup = st_init_table(st_numcmp, st_numhash); arrayForEachItem(int, support, i, inputId) { st_insert(supLookup,(char*)((long)(inputId - offset)),(char*)((long)i)); } array_free(support); /* Account for multiple columns mapping to the same MDD variable. * There are two reasons why there may be fewer variables in the MVF * than there are input columns in a table: * 1. Multiple columns are tied to the same Var_Variable_t and hence * get the same MDD variable. * 2. Variables that are in the apparent support of the table are not * in the true support of the MVF. * The first reason is captured by varMap, the second by supLookup. * Now we merge the two and replace supLookup with the resulting table. */ if (varMap != NIL(array_t)) { int mapped; int nCol = 0; Var_Ord_t *varArray = ALLOC(Var_Ord_t, array_n(varMap)); arrayForEachItem(int, varMap, i, mapped) { int position; if (st_lookup_int(supLookup, (char*)(long) mapped, &position) == 1) { varArray[nCol].id = i; varArray[nCol].rank = position; nCol++; } } qsort((void *)varArray, nCol, sizeof(Var_Ord_t), varCompare); st_free_table(supLookup); supLookup = st_init_table(st_numcmp, st_numhash); for (i=0; i < nCol; i++) { st_insert(supLookup, (char*)((long)varArray[i].id), (char*)((long)i)); } FREE(varArray); } /* foreach input var check if in true support and then insert */ Tbl_TableForEachInputVar(table,i,var){ if (st_lookup_int(supLookup, (char*)(long) i, &newColNum) == 1) { Tbl_TableAddColumn(newTable,var,0); } } /* insert only specified output */ Tbl_TableForEachOutputVar(table,i,var){ if (i == outIndex) { Tbl_TableAddColumn(newTable,var,1); } } /* add rows to this table */ TblTableForEachRow(table, row, rowNum){ i = Tbl_TableAddRow(newTable); } for (rowNum =0; rowNum < Tbl_TableReadNumRows(table); rowNum++ ) { for (colNum =0; colNum < Tbl_TableReadNumInputs(table); colNum++) { if (st_lookup_int(supLookup, (char*)(long) colNum, &newColNum) == 1) { entry = Tbl_TableReadEntry(table,rowNum, colNum, 0); newEntry = Tbl_EntryDup(entry); if (Tbl_EntryIsEqual(entry)) { eqColNum = Tbl_EntryReadVarIndex(entry); if (st_lookup_int(supLookup,(char*)(long)eqColNum,&newEqColNum) == 0) { fail("Entry Equal Var not in True Support\n"); } else { Tbl_EntrySetEqual(newEntry,newEqColNum); } } Tbl_TableSetEntry(newTable, newEntry, rowNum, newColNum, 0); } } } for (rowNum =0; rowNum < Tbl_TableReadNumRows(table); rowNum++ ) { entry = Tbl_TableReadEntry(table,rowNum, outIndex, 1); newEntry = Tbl_EntryDup(entry); if (entry->type == Tbl_EntryEqual_c) { eqColNum = Tbl_EntryReadVarIndex(entry); if (st_lookup_int(supLookup,(char*)(long)eqColNum,&newEqColNum) == 0) { fail("Entry Equal Var not in True Support\n"); } else { Tbl_EntrySetEqual(newEntry,newEqColNum); } } Tbl_TableSetEntry(newTable, newEntry, rowNum, 0, 1); } st_free_table(supLookup); Tbl_TableForEachDefaultEntry(table,entry,i) { if (i==outIndex) { if (entry != NIL(Tbl_Entry_t)) { if (entry->type != Tbl_EntryEqual_c) { newEntry = Tbl_EntryDup(entry); } else{ eqColNum = Tbl_TableReadVarIndex(newTable,Tbl_EntryReadVar(table,entry),0); if (eqColNum != -1) { newEntry = Tbl_EntryDup(entry); Tbl_EntrySetEqual(newEntry,eqColNum); } else { newEntry = NIL(Tbl_Entry_t); } } } else { newEntry = NIL(Tbl_Entry_t); } (void) Tbl_TableDefaultSetEntry(newTable,newEntry,0); } } return newTable; } /**Function******************************************************************** Synopsis [ Swap rows i and j. ] Description [ This function swaps rows i and j and return true if successful. It exits the program if data is incorrectly supplied.] SideEffects [ ] SeeAlso [ optional ] ******************************************************************************/ boolean Tbl_TableSwapRows( Tbl_Table_t * table, int i, int j) { Tbl_Row_t *rowi, *rowj; assert(table !=NIL(Tbl_Table_t)); if (TblTableReadRefCount(table) > 1) { printf(" WARNING: You are modifying more than one table by swapping these rows\n"); } rowi = TblTableReadRow(table,i); rowj = TblTableReadRow(table,j); TblTableSetRow(table,rowi,j); TblTableSetRow(table,rowj,i); return TRUE; } /**Function******************************************************************** Synopsis [ Swap input/output columns i and j. ] Description [ This functions swaps columns i and j and return true if sucessfull. It must also be supplied with a flag to indicate whether an input or output entry is being read.]] SideEffects [ ] SeeAlso [ optional ] ******************************************************************************/ boolean Tbl_TableSwapColumns( Tbl_Table_t * table, int i, int j, int flag) { int k, rowNum,colNum,flag2; Tbl_Row_t *row UNUSED; Tbl_Entry_t *coli, *colj, *entry; array_t *rowArray; Var_Variable_t *vari, *varj; assert(table !=NIL(Tbl_Table_t)); assert((flag==0)||(flag ==1)); if (TblTableReadRefCount(table) > 1) { printf(" WARNING: You are modifying more than one table by swapping rows\n"); } TblTableForEachRow(table,row,k) { coli = Tbl_EntryDup(Tbl_TableReadEntry(table,k,i,flag)); colj = Tbl_EntryDup(Tbl_TableReadEntry(table,k,j,flag)); Tbl_TableSetEntry(table,coli,k,j,flag); Tbl_TableSetEntry(table,colj,k,i,flag); } if (flag == 0) { rowArray = table->inputNames; } else { rowArray = table->outputNames; } vari = array_fetch(Var_Variable_t*,rowArray,i); varj = array_fetch(Var_Variable_t*,rowArray,j); array_insert(Var_Variable_t*,rowArray,i,varj); array_insert(Var_Variable_t*,rowArray,j,vari); /* Correct Equal entries */ Tbl_TableForEachEntry(table,rowNum,colNum,flag2,entry) { if (entry->type == Tbl_EntryEqual_c) { if (Tbl_EntryReadVarIndex(entry)==i){ Tbl_EntrySetEqual(entry,j); } else if (Tbl_EntryReadVarIndex(entry)==j){ Tbl_EntrySetEqual(entry,i); } } } Tbl_TableForEachDefaultEntry(table,entry,colNum) { if (entry != NIL(Tbl_Entry_t)) { if (entry->type == Tbl_EntryEqual_c) { if (Tbl_EntryReadVarIndex(entry)==i){ Tbl_EntrySetEqual(entry,j); } else if (Tbl_EntryReadVarIndex(entry)==j){ Tbl_EntrySetEqual(entry,i); } } } } return TRUE; } /**Function****************************************************************** Synopsis [ Semi-canonicalize a table] Description [ Given a table (Tbl_Table_t), this function will return the semi-canonical form of the table by ordering the rows and columns.The canonicaliztion process, assigns a linear order to the table rows an columns, based on the value of their entries. For a table with binary valued entries, this value is exactly the number of 1's in the row or column. Once this linear order is assigned, the rows and columns of the table are swapped so as to order rows and columns with higher value at the beginning of the corresponding row or column order. It is called semi-canonicalization because two tables representing the same logic function need not have the same canonical form. ] SideEffects [ The original table is destroyed. The user must duplicate a table before canonicalizing, to preserve it.] SeeAlso [ ] ****************************************************************************/ void Tbl_TableCanonicalize( Tbl_Table_t * table) { int numRows, numInputs, numOutputs, rowNum, colNum; array_t *rowValArray; Tbl_Row_t *colVal; int i, val1,val2; numRows = Tbl_TableReadNumRows(table); numInputs = Tbl_TableReadNumInputs(table); numOutputs = Tbl_TableReadNumOutputs(table); rowValArray = TableCreatIntArray(numRows); colVal = ALLOC(Tbl_Row_t,1); colVal->inputs= TableCreatIntArray(numInputs); colVal->outputs= TableCreatIntArray(numOutputs); for(i=0; i< numRows; i++) { for(rowNum=0; rowNum< numRows-1; rowNum++) { if (Tbl_TableRowDominatesRow(table,rowNum,rowNum+1,rowValArray)) { Tbl_TableSwapRows(table,rowNum,rowNum+1); val1 = array_fetch(int,rowValArray,rowNum); val2 =array_fetch(int,rowValArray,rowNum+1); array_insert(int,rowValArray,rowNum,val2); array_insert(int,rowValArray,rowNum+1,val1); } } } for(i=0; i< numInputs; i++) { for(colNum=0; colNum< numInputs-1; colNum++) { if (Tbl_TableColDominatesCol(table,colNum,colNum+1,0,colVal)) { Tbl_TableSwapColumns(table,colNum,colNum+1,0); val1 = array_fetch(int,TblRowReadInputs(colVal),colNum); val2 = array_fetch(int,TblRowReadInputs(colVal),colNum+1); array_insert(int,TblRowReadInputs(colVal),colNum,val2); array_insert(int,TblRowReadInputs(colVal),colNum+1,val1); } } } for(i=0; i< numOutputs; i++) { for(colNum=0; colNum< numOutputs-1; colNum++) { if (Tbl_TableColDominatesCol(table,colNum,colNum+1,1,colVal)) { Tbl_TableSwapColumns(table,colNum,colNum+1,1); val1 = array_fetch(int,TblRowReadOutputs(colVal),colNum); val2 = array_fetch(int,TblRowReadOutputs(colVal),colNum+1); array_insert(int,TblRowReadOutputs(colVal),colNum,val2); array_insert(int,TblRowReadOutputs(colVal),colNum+1,val1); } } } TblRowFree(colVal); array_free(rowValArray); } /**Function******************************************************************** Synopsis [To determine if one row dominates another] Description [Given a table and two row number rowa and rowb, this function returns a TRUE if rowa dominates rowb and FALSE otherwise] SideEffects [] SeeAlso [Tbl_TableColDominatesCol] ******************************************************************************/ boolean Tbl_TableRowDominatesRow( Tbl_Table_t *table, int rowa, int rowb, array_t *rowValArray) { int valuea, valueb, totala, totalb; Tbl_Entry_t *entrya, *entryb; int colNum; valuea = array_fetch(int,rowValArray,rowa); totala = valuea; if (valuea == -1) { totala =0; Tbl_RowForEachInputEntry(table,rowa,entrya,colNum) { valuea = TableEntryComputeHashVal(table,entrya); totala = valuea + totala; } Tbl_RowForEachOutputEntry(table,rowa,entrya,colNum) { valuea = TableEntryComputeHashVal(table,entrya); totala = valuea + totala; } array_insert(int, rowValArray,rowa,totala); } valueb = array_fetch(int,rowValArray,rowb); totalb = valueb; if (valueb == -1) { totalb =0; Tbl_RowForEachInputEntry(table,rowb,entryb,colNum) { valueb = TableEntryComputeHashVal(table,entryb); totalb = valueb + totalb; } Tbl_RowForEachOutputEntry(table,rowb,entryb,colNum) { valueb = TableEntryComputeHashVal(table,entryb); totalb = valueb + totalb; } array_insert(int, rowValArray,rowb,totalb); } if (totala < totalb ) { return FALSE; } else { return TRUE; } } /**Function******************************************************************** Synopsis [To determine if one Col dominates another] Description [Given a table, two integers for column number cola colb, and a flag set to 0 to indicate input and 1 for output this function returns a TRUE if Cola dominates Colb and FALSE otherwise] SideEffects [] SeeAlso [Tbl_TableRowDominatesRow] ******************************************************************************/ boolean Tbl_TableColDominatesCol( Tbl_Table_t *table, int cola, int colb, int flag, Tbl_Row_t *colValArray) { int valuea, valueb, totala, totalb; Tbl_Entry_t *entrya, *entryb; int colNum, rowNum; if (flag == 0) { valuea = array_fetch(int,TblRowReadInputs(colValArray),cola); } else { valuea = array_fetch(int,TblRowReadOutputs(colValArray),cola); } totala = valuea; if (valuea == -1) { totala =0; if (flag ==0) { Tbl_TableForEachInputEntry(table,rowNum,colNum,entrya){ if (colNum == cola) { valuea = TableEntryComputeHashVal(table,entrya); totala = valuea + totala; } } array_insert(int, TblRowReadInputs(colValArray),cola,totala); } else if (flag ==1) { Tbl_TableForEachOutputEntry(table,rowNum,colNum,entrya){ if (colNum == cola) { valuea = TableEntryComputeHashVal(table,entrya); totala = valuea + totala; } } array_insert(int, TblRowReadOutputs(colValArray),cola,totala); } } if (flag ==0) { valueb = array_fetch(int,TblRowReadInputs(colValArray),colb); } else { valueb = array_fetch(int,TblRowReadOutputs(colValArray),colb); } totalb = valueb; if (valueb == -1) { totalb =0; if (flag ==0) { Tbl_TableForEachInputEntry(table,rowNum,colNum,entryb){ if (colNum == colb) { valueb = TableEntryComputeHashVal(table,entryb); totalb = valueb + totalb; } } array_insert(int, TblRowReadInputs(colValArray),colb,totalb); } else if (flag ==1) { Tbl_TableForEachOutputEntry(table,rowNum,colNum,entryb){ if (colNum == colb) { valuea = TableEntryComputeHashVal(table,entryb); totalb = valueb + totalb; } } array_insert(int, TblRowReadOutputs(colValArray),colb,totalb); } } if (totala < totalb ) { return FALSE; } else { return TRUE; } } /**Function****************************************************************** Synopsis [ Compare two tables.] Description [ Given two Tbl_Table_t's tablea and tableb, this function will compare the two tables to determine if they are the same. It returns a TRUE if they are and a FALSE if not.] SideEffects [ ] SeeAlso [ ] ****************************************************************************/ boolean Tbl_TablesAreIdentical( Tbl_Table_t *tablea, Tbl_Table_t *tableb, int a, int b) { char *signaturea; char *signatureb; signaturea = TableObtainSignature(tablea, a); signatureb = TableObtainSignature(tableb, b); if (strcmp(signaturea, signatureb) == 0) { FREE(signaturea); FREE(signatureb); return TRUE; } FREE(signaturea); FREE(signatureb); return FALSE; } /**Function******************************************************************** Synopsis [ Returns an mdd for a table row ] Description [ Given a row id i, a table, an mdd manager and an array of arrays of mdd_t*, this function returns the mdd for the corresponding row. The array of arrays of mdd_t* gives the onsets for different values of the multivalued var of each column.] SideEffects [ ] SeeAlso [ ] ******************************************************************************/ mdd_t * Tbl_TableRowToMdd( Tbl_Table_t * table, mdd_manager * manager, int i, array_t * svArray /* array of array of mdd_t to be used */) { mdd_t *result, *finalResult, *temp; int j,k; Tbl_Entry_t *entry; Mvf_Function_t *mvf1, *mvf2; result = NIL(mdd_t); finalResult = mdd_one(manager); Tbl_RowForEachInputEntry(table,i,entry,j) { if ((entry->type) == Tbl_EntryNormal_c) { mvf1 = array_fetch(Mvf_Function_t*,svArray,j); result = TblEntryNormalConstructMdd(manager,entry,mvf1); } else if ((entry->type == Tbl_EntryEqual_c)) { k = Tbl_EntryReadVarIndex(entry); mvf1 = array_fetch(Mvf_Function_t*,svArray,j); mvf2 = array_fetch(Mvf_Function_t*,svArray,k); result = Mvf_FunctionsComputeEquivalentSet(mvf1,mvf2); } else if (entry->type == Tbl_EntryUnassigned_c) { return NIL(mdd_t); } temp = finalResult; finalResult = mdd_and(temp,result,1,1); mdd_free(temp); mdd_free(result); } Tbl_RowForEachOutputEntry(table,i,entry,j) { if ((entry->type) == Tbl_EntryNormal_c) { mvf1 = array_fetch(Mvf_Function_t*,svArray,j); result = TblEntryNormalConstructMdd(manager,entry,mvf1); } else if ((entry->type == Tbl_EntryEqual_c)) { k = Tbl_EntryReadVarIndex(entry); mvf1 = array_fetch(Mvf_Function_t*,svArray,j); mvf2 = array_fetch(Mvf_Function_t*,svArray,k); result = Mvf_FunctionsComputeEquivalentSet(mvf1,mvf2); } else if (entry->type == Tbl_EntryUnassigned_c) { return NIL(mdd_t); } temp = finalResult; finalResult = mdd_and(temp,result,1,1); mdd_free(temp); mdd_free(result); } return finalResult; } /**Function******************************************************************** Synopsis [Compute the Mvf_Function_t for a non-deterministic constant.] Description [Given a Tbl_Table_t, an integer for the table output value index, an integer MddId, and an mdd Manager, this function builds the Mvf_Function_t associated with the output. The table cannot have any inputs; the function fails if it does. The output cannot be equal to another output, because this would make the table a relation, and that is not permissible. If this occurs, the function will fail on an assert statement.] SideEffects [ Table must have no inputs.] SeeAlso [] ******************************************************************************/ Mvf_Function_t * Tbl_TableBuildNonDetConstantMvf( Tbl_Table_t * table, int outIndex, int mddId, mdd_manager * mddMgr) { lsGen gen; Tbl_Entry_t *entry; Tbl_Range_t *range; int value, rowNum, colNum; mdd_t *x; Mvf_Function_t *function; assert(Tbl_TableReadNumInputs(table) ==0); value = Var_VariableReadNumValues(Tbl_TableReadIndexVar(table,outIndex,1)); function = Mvf_FunctionAlloc(mddMgr,value); Tbl_TableForEachOutputEntry(table,rowNum,colNum,entry) { if (colNum == outIndex) { assert(entry->type == Tbl_EntryNormal_c); Tbl_EntryForEachValue(entry,value,gen,range) { x = mdd_eq_c(mddMgr,mddId,value); Mvf_FunctionAddMintermsToComponent(function, value,x); mdd_free(x); } } } return function; } /**Function******************************************************************** Synopsis [Compute the Mvf_Function_t for a table output in terms of fanins] Description [Given a Tbl_Table_t, an integer for the table output value index, an array of fanin mdd_t* , and an mdd Manager, this function builds the Mvf_Function_t associated with the output. The output cannot be equal to another output, because this would make the table a relation, and that is not permissible. For each row, the function will build the mdd_t for the inputs using their Mvf_Function_t's and AND them together. If the input is of the type equal, it will build the equivalent set Mdd (see See Also) and AND it in.] SideEffects [ ] SeeAlso [ Mvf_FunctionComputeEquivalentSet, TblEntryNormalConstructMdd] ******************************************************************************/ Mvf_Function_t * Tbl_TableBuildMvfFromFanins( Tbl_Table_t * table, int outIndex, array_t * faninArray, mdd_manager * mddMgr) { lsGen gen; Tbl_Entry_t *entry, *entry2,*inputEntry; Tbl_Range_t *range; int value, rowNum, colNum, rowColNum, i; mdd_t *x, *result, *temp; Mvf_Function_t *function, *mvf1, *mvf2; x = NIL(mdd_t); value = Var_VariableReadNumValues(Tbl_TableReadIndexVar(table,outIndex,1)); function = Mvf_FunctionAlloc(mddMgr,value); Tbl_TableForEachOutputEntry(table,rowNum,colNum,entry) { if (colNum == outIndex) { if (entry->type == Tbl_EntryNormal_c) { result = mdd_one(mddMgr); Tbl_RowForEachInputEntry(table,rowNum,inputEntry,rowColNum) { if (inputEntry->type == Tbl_EntryNormal_c) { mvf1 = array_fetch(Mvf_Function_t*,faninArray,rowColNum); x = TblEntryNormalConstructMdd(mddMgr,inputEntry,mvf1); } else if (inputEntry->type == Tbl_EntryEqual_c) { value =Tbl_EntryReadVarIndex(inputEntry); mvf1 = array_fetch(Mvf_Function_t*,faninArray,rowColNum); mvf2 = array_fetch(Mvf_Function_t*,faninArray,value); x = Mvf_FunctionsComputeEquivalentSet(mvf1,mvf2); } temp = result; result = mdd_and(x,temp,1,1); mdd_free(temp); mdd_free(x); } Tbl_EntryForEachValue(entry,value,gen,range) { Mvf_FunctionAddMintermsToComponent(function, value,result); } mdd_free(result); } else if (entry->type == Tbl_EntryEqual_c) { value = Tbl_EntryReadVarIndex(entry); if (value == -1) { fail("Failure: Not equal to any input var in this table\n"); } /* must be equal to an input */ entry2 = Tbl_TableReadEntry(table,rowNum,value,0); result = mdd_one(mddMgr); Tbl_RowForEachInputEntry(table,rowNum,inputEntry,rowColNum) { if (inputEntry->type == Tbl_EntryNormal_c) { mvf1 = array_fetch(Mvf_Function_t*,faninArray,rowColNum); x = TblEntryNormalConstructMdd(mddMgr,inputEntry,mvf1); } else if (inputEntry->type == Tbl_EntryEqual_c) { value =Tbl_EntryReadVarIndex(inputEntry); mvf1 = array_fetch(Mvf_Function_t*,faninArray,rowColNum); mvf2 = array_fetch(Mvf_Function_t*,faninArray,value); x = Mvf_FunctionsComputeEquivalentSet(mvf1,mvf2); } temp = result; result = mdd_and(x,temp,1,1); mdd_free(temp); mdd_free(x); } rowColNum = Tbl_EntryReadVarIndex(entry); mvf1 = array_fetch(Mvf_Function_t*,faninArray,rowColNum); value = Var_VariableReadNumValues(Tbl_EntryReadActualVar(table,entry2)); temp = result; for(i=0; i< value; i++) { x = Mvf_FunctionReadComponent(mvf1,i); result = mdd_and(temp,x,1,1); Mvf_FunctionAddMintermsToComponent(function, i,result); mdd_free(result); } mdd_free(temp); } } } /* accounting for the defaults */ entry = Tbl_TableDefaultReadEntry(table,outIndex); if (entry != NIL(Tbl_Entry_t)) { temp = Mvf_FunctionComputeDomain(function); result = mdd_not(temp); mdd_free(temp); if (entry->type == Tbl_EntryNormal_c) { Tbl_EntryForEachValue(entry,value,gen,range) { Mvf_FunctionAddMintermsToComponent(function, value,result); } } else { value = Tbl_EntryReadVarIndex(entry); if (value == -1) { fail("Failure: Not equal to any input var in this table\n"); } mvf1 = array_fetch(Mvf_Function_t*,faninArray,value); Mvf_FunctionForEachComponent(mvf1,i,x) { temp = mdd_and(x,result,1,1); Mvf_FunctionAddMintermsToComponent(function, i ,temp); mdd_free(temp); } } mdd_free(result); } return function; } /**Function******************************************************************** Synopsis [ Return the constant value associated with an output] Description [ Given a table that has no inputs and an output column index, this function returns the constant value associated with the output. It returns a -1 if the value is not a constant. Note that this test is conservative, because it does not take into account Boolean redundancies. It merely checks for one of the following conditions 1) the table has no inputs and a constant output 2) the table has only - inputs in the one row and the output is constant 3) the table is empty and the default value for the output is constant and 4) the table output has the same constant value for all inputs] SideEffects [] SeeAlso [] ******************************************************************************/ int Tbl_TableReadConstValue( Tbl_Table_t * table, int outputColumnId) { int colNum, rowNum; boolean check; Tbl_Entry_t *entry; Var_Variable_t *var; Tbl_Range_t *range; lsGen gen; int value, constant,count; constant = -1; assert(table !=NIL(Tbl_Table_t)); assert((outputColumnId >= 0) && (outputColumnId < Tbl_TableReadNumOutputs(table))); if (Tbl_TableReadNumRows(table) == 1) { if (array_n(table->inputNames) == 0) { entry = Tbl_TableReadEntry(table, 0, outputColumnId, 1); if (entry->type == Tbl_EntryNormal_c) { if (Tbl_EntryReadNumValues(entry) == 1) { Tbl_EntryForEachValue(entry,value,gen,range) { constant = value; } return constant; } } } else { check = TRUE; Tbl_TableForEachInputEntry(table,rowNum,colNum,entry) { if (entry->type != Tbl_EntryNormal_c) { return -1; } if (check == TRUE) { check = -1; if (lsLength(entry->EntryData.listOfRanges) == 1){ var = Tbl_EntryReadActualVar(table,entry); lsForEachItem(entry->EntryData.listOfRanges, gen, range) { if ((range->begin ==0)&&(range->end == Var_VariableReadNumValues(var)-1)){ check = TRUE; } } } } } if (check) { entry = Tbl_TableReadEntry(table,0,outputColumnId,1); if (entry->type != Tbl_EntryNormal_c) { return -1; } if (Tbl_EntryReadNumValues(entry) == 1) { Tbl_EntryForEachValue(entry,value,gen,range) { constant = value; } return constant; } } } } else if (Tbl_TableReadNumRows(table) == 0) { entry = Tbl_TableDefaultReadEntry(table,outputColumnId); if (entry->type != Tbl_EntryNormal_c) { return -1; } if (Tbl_EntryReadNumValues(entry) == 1) { Tbl_EntryForEachValue(entry,value,gen,range) { constant = value; } return constant; } } else { entry = Tbl_TableDefaultReadEntry(table,outputColumnId); if (entry == NIL(Tbl_Entry_t)){ constant = -1; Tbl_TableForEachOutputEntry(table,rowNum,colNum,entry) { if (colNum == outputColumnId) { count = 1; if (entry->type != Tbl_EntryNormal_c){ return -1; } Tbl_EntryForEachValue(entry,value,gen,range) { lsStatus status; if (count > 1) { status = lsFinish(gen); assert(status == LS_OK); return -1; } else { if (constant != -1) { if (constant != value) { status = lsFinish(gen); assert(status == LS_OK); return -1; } } else { constant = value; } } count ++; } } } return constant; } } return -1; } /**Function******************************************************************** Synopsis [ Returns a table for an mdd ] Description [ ] SideEffects [ ] SeeAlso [ ] ******************************************************************************/ Tbl_Table_t * Tbl_MddToTable( mdd_t * mdd, mdd_manager * manager, st_table * idtoVar, array_t * inputids) { /**Fix*******Gitanjali***********************************************************/ /* use foreach cube */ printf("Not implemented as yet, contact gms@ic\n"); return NIL(Tbl_Table_t); } /**Function******************************************************************** Synopsis [ Substitute the oldVar with the newVar. Return TRUE if successful. ] Description [ Given a table and Var_variable_t's oldVar and newVar, it replaces the oldVar with the newVar in the table. It returns true if sucessful and false otherwise.] SideEffects [ The oldVar is not freed, it is the user's responsibility ] SeeAlso [ ] ******************************************************************************/ boolean Tbl_TableSubstituteVar( Tbl_Table_t * table, Var_Variable_t * oldVar, Var_Variable_t * newVar) { int i,k; int flag; Var_Variable_t *var; k = -1; flag =0; var = NIL(Var_Variable_t); if (!Var_VariablesTestHaveSameDomain(oldVar,newVar)) return FALSE; if (table != NIL(Tbl_Table_t)) { Tbl_TableForEachInputVar(table,i,var) { if (var == oldVar) { k = i; i = Tbl_TableReadNumInputs(table); flag = 0; } } if (k == -1) { Tbl_TableForEachOutputVar(table,i,var) { if (var == oldVar) { k = i; i = Tbl_TableReadNumOutputs(table); flag = 1; } } } if (k != -1) { Tbl_TableSetVar(table,k,newVar,flag); /* traverse all the entries of the table and change all the references to the old variable in the equal-to construct to the new variable */ /* The above no longer has to be done as the entry refers to an index rather than the var */ return TRUE; } else { return FALSE; } } return FALSE; } /**Function******************************************************************** Synopsis [Set the var in given column to given var] Description [Given a table, an index and a new var for the index, this function sets the var in the table ] SideEffects [The previously set var is lost] SeeAlso [] ******************************************************************************/ void Tbl_TableSetVar( Tbl_Table_t * table, int i, Var_Variable_t * sv, int flag) { array_t *svarray; if (flag==0){ svarray = Tbl_TableReadInputVars(table); } else { svarray = Tbl_TableReadOutputVars(table); } array_insert(Var_Variable_t*,svarray,i,sv); } /**Function******************************************************************** Synopsis [ Split a multi-output table into a set of single output tables. ] Description [ Given a deterministic multi-output table this function splits it into an array of single-output tables.] SideEffects [ Determinism is required for this to be sucessful. The user is responsible for freeing the original table] SeeAlso [ ] ******************************************************************************/ array_t * Tbl_TableSplit( Tbl_Table_t * table) { int i,j, rowNum, colNum; array_t *resArray; Tbl_Table_t *newtable; Var_Variable_t *output, *input; Tbl_Entry_t *entry, *newEntry; resArray = array_alloc(Tbl_Table_t*,0); Tbl_TableForEachOutputVar(table,i,output) { newtable = Tbl_TableAlloc(); Tbl_TableAddColumn(newtable,output,1); Tbl_TableForEachInputVar(table,colNum,input) { Tbl_TableAddColumn(newtable,input,0); } for (rowNum =0; rowNum < Tbl_TableReadNumRows(table); rowNum++) { (void) Tbl_TableAddRow(newtable); } Tbl_TableForEachEntry(table,rowNum,colNum,j,entry) { if (j==0) { newEntry = Tbl_EntryDup(entry); Tbl_TableSetEntry(newtable,newEntry,rowNum,colNum,0); } else { if (colNum ==i) { newEntry = Tbl_EntryDup(entry); Tbl_TableSetEntry(newtable,newEntry,rowNum,0,1); } } } entry = Tbl_TableDefaultReadEntry(table,i); if (entry != NIL(Tbl_Entry_t)) { newEntry = Tbl_EntryDup(entry); Tbl_TableDefaultSetEntry(newtable,newEntry,0); } array_insert_last(Tbl_Table_t*,resArray,newtable); } return resArray; } /**Function******************************************************************** Synopsis [ Return the number of inputs. ] Description [ ] SideEffects [ ] SeeAlso [ ] ******************************************************************************/ int Tbl_TableReadNumInputs( Tbl_Table_t * table) { return(array_n(table->inputNames)); } /**Function******************************************************************** Synopsis [ Return the number of outputs. ] Description [ ] SideEffects [ ] SeeAlso [ ] ******************************************************************************/ int Tbl_TableReadNumOutputs( Tbl_Table_t * table) { return(array_n(table->outputNames)); } /**Function******************************************************************** Synopsis [return the number of input/output Vars] Description [Given a table and a flag set to 0 for input and 1 for output this function returns the number of inputs or outputs.] SideEffects [] SeeAlso [Tbl_TableReadNumInputs Tbl_TableReadNumOutputs] ******************************************************************************/ int Tbl_TableReadNumVars( Tbl_Table_t *table, int flag) { if (flag==0) { return Tbl_TableReadNumInputs(table); } else { return Tbl_TableReadNumOutputs(table); } } /**Function******************************************************************** Synopsis [ Return the number of rows. ] Description [ ] SideEffects [ ] SeeAlso [ ] ******************************************************************************/ int Tbl_TableReadNumRows( Tbl_Table_t * table) { return(array_n(TblTableReadData(table))); } /**Function*********************************************************** Synopsis [ Find the index of the variable (column) associated with the given Var. ] Description [ Given a Var_Variable_t, this functions returns the index of the column that is represented by. The function returns -1 if the var does not belong to the table. It must also be supplied with a flag to indicate whether an input or output entry is being read.] SideEffects [ ] SeeAlso [ optional ] **********************************************************************/ int Tbl_TableReadVarIndex( Tbl_Table_t * table, Var_Variable_t * var, int flag /* Set to 0 if it is an input Var and 1 if it an output Var */ ) { int i; array_t *carray; Var_Variable_t *aVar; assert(table !=NIL(Tbl_Table_t)); assert((flag==0)||(flag ==1)); if (flag==0) { carray = table->inputNames; } else { carray = table->outputNames; } for (i=0; i< array_n(carray);i++) { aVar = array_fetch(Var_Variable_t*,carray,i); if (var==aVar) { return i; } } return -1; } /**Function******************************************************************** Synopsis [Print table statistics] Description [ Prints the following information to the file: number of input columns, number of output columns, number of rows, name and cardinality of domain, of each input column, name and cardinality of domain, of each output, percentage of mxn entries with non-DC information (gives measure of sparsity)] SideEffects [] SeeAlso [] ******************************************************************************/ void Tbl_TablePrintStats( Tbl_Table_t *table, FILE *fp) { int rowNum, colNum,i,dc, total; Tbl_Entry_t *entry; Var_Variable_t *var; lsGen gen; Tbl_Range_t *range; fprintf(fp,"Table Stats\n"); fprintf(fp,"Number of Inputs = %d\n",Tbl_TableReadNumInputs(table)); fprintf(fp,"Inputs :"); Tbl_TableForEachInputVar(table,colNum,var){ fprintf(fp,"%s ",Var_VariableReadName(var)); } fprintf(fp,"\n"); fprintf(fp,"Values :"); Tbl_TableForEachInputVar(table,colNum,var){ fprintf(fp,"%d ",Var_VariableReadNumValues(var)); } fprintf(fp,"\n"); fprintf(fp,"Number of Outputs = %d\n",Tbl_TableReadNumOutputs(table)); fprintf(fp,"Outputs :"); Tbl_TableForEachOutputVar(table,colNum,var){ fprintf(fp,"%s ",Var_VariableReadName(var)); } fprintf(fp,"\n"); fprintf(fp,"Values :"); Tbl_TableForEachOutputVar(table,colNum,var){ fprintf(fp,"%d ",Var_VariableReadNumValues(var)); } fprintf(fp,"\n"); fprintf(fp,"Number of Rows = %d\n",Tbl_TableReadNumRows(table)); dc = 0; total =0; Tbl_TableForEachEntry(table,rowNum,colNum,i,entry) { total++; if(entry->type == Tbl_EntryNormal_c) { if (lsLength(entry->EntryData.listOfRanges) == 1){ var = Tbl_EntryReadActualVar(table,entry); lsForEachItem(entry->EntryData.listOfRanges, gen, range) { if ((range->begin ==0)&&(range->end == Var_VariableReadNumValues(var)-1)){ dc++; } } } } } if (total > 0) { i = 100 *dc/total; } else { i = 0; } fprintf(fp,"# Don't Care entries = %d\n",dc); fprintf(fp,"Percent Don't Care entries = %d\n",i); } /**Function******************************************************************** Synopsis [Print table to file specified by fp in blif mv format. Appends the chars "_bufin" to the end of the output variables.] Description [Given a table and file ptr, this function will print this table in blif_mv form to a file specified by the ptr. If stdout is specified this table will print it to stdout.It must also be supplied with a flag to indicate the nature of the table. If this flag is a 0, it indicates that the table is of the type .table if it is a 1, then it indicates that the table is of the type .reset.] SideEffects [] SeeAlso [TblEntryPrint TblEntryWriteBlif Tbl_TablePrintl] ******************************************************************************/ void Tbl_TableWriteBlifMvToFileSpecial( Tbl_Table_t *table, int flag, FILE *fp) { int rowNum, colNum,i; Tbl_Entry_t *entry; Var_Variable_t *var; if (flag ==0) { fprintf(fp,".table "); } else { fprintf(fp,".reset "); } Tbl_TableForEachInputVar(table,colNum,var){ fprintf(fp,"%s ",Var_VariableReadName(var)); } fprintf(fp,"->"); Tbl_TableForEachOutputVar(table,colNum,var){ fprintf(fp,"%s_bufin ",Var_VariableReadName(var)); } fprintf(fp,"\n"); if ((array_fetch(Tbl_Entry_t*, TblTableReadDefaults(table),0)) != NIL(Tbl_Entry_t)) { fprintf(fp,".default "); Tbl_TableForEachDefaultEntry(table,entry,colNum) { TblEntryWriteBlifMv(table,entry,fp); fprintf(fp," "); } fprintf(fp,"\n"); } Tbl_TableForEachEntry(table, rowNum,colNum,i,entry) { TblEntryWriteBlifMv(table,entry,fp); fprintf(fp," "); if ((colNum == (Tbl_TableReadNumOutputs(table) -1))&&(i==1)) { fprintf(fp,"\n"); } } } /**Function******************************************************************** Synopsis [Print table to file specified by fp in blif-mv format] Description [Given a table and file ptr, this function will print this table in blif_mv form to a file specified by the ptr. If stdout is specified this table will print it to stdout. It must also be supplied with a flag to indicate the nature of the table. If this flag is a 0, it indicates that the table is of the type .table. If it is a 1, then it indicates that the table is of the type .reset. Finally, if flag is 2, the table should be printed without header.] SideEffects [] SeeAlso [TblEntryPrint TblEntryWriteBlif Tbl_TablePrintl] ******************************************************************************/ void Tbl_TableWriteBlifMvToFile( Tbl_Table_t *table, int flag, FILE *fp) { int rowNum, colNum,i; Tbl_Entry_t *entry; Var_Variable_t *var; if (flag == 0) { fprintf(fp,".table "); } else if (flag == 1) { fprintf(fp,".reset "); } if (flag < 2) { Tbl_TableForEachInputVar(table,colNum,var){ fprintf(fp,"%s ",Var_VariableReadName(var)); } fprintf(fp,"->"); Tbl_TableForEachOutputVar(table,colNum,var){ fprintf(fp," %s",Var_VariableReadName(var)); } fprintf(fp,"\n"); } if ((array_fetch(Tbl_Entry_t*, TblTableReadDefaults(table),0)) != NIL(Tbl_Entry_t)) { fprintf(fp,".default"); Tbl_TableForEachDefaultEntry(table,entry,colNum) { fprintf(fp," "); TblEntryWriteBlifMv(table,entry,fp); } fprintf(fp,"\n"); } Tbl_TableForEachEntry(table,rowNum,colNum,i,entry) { TblEntryWriteBlifMv(table,entry,fp); if ((colNum == (Tbl_TableReadNumOutputs(table) -1))&&(i==1)) { fprintf(fp,"\n"); } else { fprintf(fp," "); } } } /**Function******************************************************************** Synopsis [Print table to file specified by fp in smv format] Description [Given a table and file ptr, this function will print this table in smv form to a file specified by the ptr. If stdout is specified this table will print it to stdout.It must also be supplied with a flag to indicate the nature of the table. If this flag is a 0, it indicates that the table is of the type .table if it is a 1, then it indicates that the table is of the type .reset.] SideEffects [] SeeAlso [TblEntryPrint TblEntryWriteBlif Tbl_TablePrintl] ******************************************************************************/ void Tbl_TableWriteSmvToFile( Tbl_Table_t *table, int flag, FILE *fp) { int rowNum, colNum,i; Tbl_Entry_t *entry; Var_Variable_t *var; if (flag ==0) { fprintf(fp,"\n-- Table for "); } else { fprintf(fp,"\n-- Reset table for "); } Tbl_TableForEachInputVar(table,colNum,var){ fprintf(fp,"%s ",Var_VariableReadName(var)); } fprintf(fp,"->"); Tbl_TableForEachOutputVar(table,colNum,var){ fprintf(fp,"%s ",Var_VariableReadName(var)); } fprintf(fp,"\n"); if (flag ==0) { fprintf(fp, "INVAR\n( "); Tbl_TableForEachEntry(table, rowNum,colNum,i,entry) { TblEntryWriteSmv(table,entry,0,fp); if ((colNum == (Tbl_TableReadNumOutputs(table) -1))&&(i==1)) { if(rowNum < Tbl_TableReadNumRows(table) -1) { fprintf(fp,") |\n( "); } } else { fprintf(fp,"& "); } } if ((array_fetch(Tbl_Entry_t*, TblTableReadDefaults(table),0)) != NIL(Tbl_Entry_t)) { fprintf(fp,") |\n( "); if (Tbl_TableReadNumInputs(table) > 0) { fprintf(fp,"!( ("); } Tbl_TableForEachInputEntry(table, rowNum,colNum,entry) { TblEntryWriteSmv(table,entry,0,fp); if (colNum == (Tbl_TableReadNumInputs(table) -1)) { if(rowNum < Tbl_TableReadNumRows(table) -1) { fprintf(fp,") | ( "); } } else { fprintf(fp,"& "); } } if (Tbl_TableReadNumInputs(table) > 0) { fprintf(fp,") ) & "); } Tbl_TableForEachDefaultEntry(table,entry,colNum) { TblEntryWriteSmv(table,entry,0,fp); if (colNum < (Tbl_TableReadNumOutputs(table) -1)) { fprintf(fp,"& "); } } } fprintf(fp,")\n"); } else { fprintf(fp,"case\n"); Tbl_TableForEachEntry(table, rowNum,colNum,i,entry) { TblEntryWriteSmv(table,entry,i,fp); if ((colNum == (Tbl_TableReadNumInputs(table) -1))&&(i==0)) { fprintf(fp,": "); } else if ((colNum == (Tbl_TableReadNumOutputs(table) -1))&&(i==1)) { fprintf(fp,";\n"); } else { fprintf(fp,"& "); } } if ((array_fetch(Tbl_Entry_t*, TblTableReadDefaults(table),0)) != NIL(Tbl_Entry_t)) { fprintf(fp,"1 : "); Tbl_TableForEachDefaultEntry(table,entry,colNum) { TblEntryWriteSmv(table,entry,1,fp); } fprintf(fp,";\n"); } fprintf(fp,"esac;\n"); } } /**Function******************************************************************** Synopsis [Writes out a table to a named blif file] Description [Writes out blif files corresponding to the table given.] SideEffects [] SeeAlso [] ******************************************************************************/ void Tbl_TableWriteBlifToFile( Tbl_Table_t *table, FILE *fp ) { int numInputs, numOutputs, numRows, colnum, i, j; Var_Variable_t *var; Tbl_Entry_t *entry; lsGen gen; Tbl_Range_t *range; int value, flag; fprintf(fp,".names "); for (colnum=0; colnum < Tbl_TableReadNumInputs(table); colnum++) { var = Tbl_TableReadIndexVar(table, colnum, 0); fprintf(fp,"%s ",Var_VariableReadName(var)); } for (colnum=0; colnum < Tbl_TableReadNumOutputs(table); colnum++) { var = Tbl_TableReadIndexVar(table, colnum, 1); fprintf(fp,"%s ",Var_VariableReadName(var)); } fprintf(fp,"\n"); numInputs = Tbl_TableReadNumInputs(table); numOutputs = Tbl_TableReadNumOutputs(table); numRows = Tbl_TableReadNumRows(table); for (i=0; i < numRows; i++) { flag =1; if (numOutputs == 1) { entry = Tbl_TableReadEntry(table, i, 0, 1); if (Tbl_EntryReadNumValues(entry) ==1 ){ Tbl_EntryForEachValue(entry,value,gen,range){ if (value ==0) { flag = 0; } } } } if (flag ==1) { for(j = 0; j < numInputs; j++){ entry = Tbl_TableReadEntry(table, i, j, 0); TblEntryWriteBlif(table,entry,fp); } fprintf(fp," "); for(j = 0; j < numOutputs; j++){ entry = Tbl_TableReadEntry(table, i, j, 1); TblEntryWriteBlif(table,entry,fp); } fprintf(fp,"\n"); } } } /**Function******************************************************************** Synopsis [Return the defaults array associated with a table.] Description [] SideEffects [This array is NOT to be modified. The user is encouraged not to use this function. It is exported so as to make the macros for iteration over items in the table possible. The user should use these macros for accessing data. The macros that can be used are mentioned in the SeeAlso list] SeeAlso [Tbl_TableForEachEntry Tbl_TableForEachInputEntry Tbl_TableForEachOutputEntry Tbl_TableForEachInputVar Tbl_TableForEachOutputVar Tbl_TableForEachDefault] ******************************************************************************/ array_t* Tbl_TableReadDefaults( Tbl_Table_t * table) { return (table->data->defaults); } /**Function******************************************************************** Synopsis [Return the input Var_Variable_t array associated with a table.] Description [] SideEffects [This array is NOT to be modified. The user is encouraged not to use this function. It is exported so as to make the macros for iteration over items in the table possible. The user should use these macros for accessing data. The macros that can be used are mentioned in the SeeAlso list] SeeAlso [Tbl_TableForEachEntry Tbl_TableForEachInputEntry Tbl_TableForEachOutputEntry Tbl_TableForEachInputVar Tbl_TableForEachOutputVar Tbl_TableForEachDefault] ******************************************************************************/ array_t* Tbl_TableReadInputVars( Tbl_Table_t * table) { return (table->inputNames); } /**Function******************************************************************** Synopsis [Return the output Var_Variable_t array associated with a table.] Description [] SideEffects [This array is NOT to be modified. The user is encouraged not to use this function. It is exported so as to make the macros for iteration over items in the table possible. The user should use these macros for accessing data. The macros that can be used are mentioned in the SeeAlso list] SeeAlso [Tbl_TableForEachEntry Tbl_TableForEachInputEntry Tbl_TableForEachOutputEntry Tbl_TableForEachInputVar Tbl_TableForEachOutputVar Tbl_TableForEachDefault] ******************************************************************************/ array_t* Tbl_TableReadOutputVars( Tbl_Table_t * table) { return (table->outputNames); } /**Function******************************************************************** Synopsis [Checks to see if the input parts of two rows intersect] Description [Given two rows, this function checks to see if their input parts intersect, returns a 0 if they don't, and 1 if they do] SideEffects [] SeeAlso [Tbl_TableIsDet] ******************************************************************************/ boolean Tbl_RowInputIntersect( Tbl_Table_t * table, int a, int b) { int colNum, check; Tbl_Entry_t *entrya, *entryb; Tbl_Row_t *rowb; check = FALSE; rowb = TblTableReadRow(table,b); Tbl_RowForEachInputEntry(table,a, entrya, colNum){ entryb = TblRowReadEntry(rowb,colNum,0); check = Tbl_EntryTestIntersectEntry(entrya,entryb); if (check == FALSE) { return FALSE; } } return TRUE; } /**Function******************************************************************** Synopsis [Checks to see if the output parts of two rows intersect] Description [Given two rows, this function checks to see if their output parts intersect, returns a 0 if they don't, and 1 if they do] SideEffects [] SeeAlso [Tbl_TableIsDet] ******************************************************************************/ boolean Tbl_RowOutputIntersect( Tbl_Table_t * table, int a, int b) { int colNum, check; Tbl_Entry_t *entrya, *entryb; Tbl_Row_t *rowb; check = FALSE; rowb = TblTableReadRow(table,b); Tbl_RowForEachOutputEntry(table,a, entrya, colNum){ entryb = TblRowReadEntry(rowb,colNum,1); check = Tbl_EntryTestIntersectEntry(entrya,entryb); if (check == FALSE) { return FALSE; } } return TRUE; } /*---------------------------------------------------------------------------*/ /* Definition of internal functions */ /*---------------------------------------------------------------------------*/ /**Function******************************************************************** Synopsis [Set a Row] Description [Given a table, a row and an index , this function sets the row in the table] SideEffects [ The previously set row is lost ] SeeAlso [] ******************************************************************************/ void TblTableSetRow( Tbl_Table_t *table, Tbl_Row_t *row, int i) { array_insert(Tbl_Row_t*, TblTableReadData(table),i,row); } /**Function******************************************************************** Synopsis [Return the output array associated with a row.] Description [] SideEffects [This array is NOT to be modified. The user is encouraged not to use this function. It is exported so as to make the macros for iteration over items in the table possible. The user should use these macros for accessing data. The macros that can be used are mentioned in the SeeAlso list] SeeAlso [Tbl_TableForEachEntry Tbl_TableForEachInputEntry Tbl_TableForEachOutputEntry Tbl_TableForEachInputVar Tbl_TableForEachOutputVar Tbl_TableForEachDefault] ******************************************************************************/ array_t* TblRowReadOutputs( Tbl_Row_t * row) { return (row->outputs); } /**Function******************************************************************** Synopsis [Return the input array associated with a row.] Description [] SideEffects [This array is NOT to be modified. The user is encouraged not to use this function. It is exported so as to make the macros for iteration over items in the table possible. The user should use these macros for accessing data. The macros that can be used are mentioned in the SeeAlso list] SeeAlso [Tbl_TableForEachEntry Tbl_TableForEachInputEntry Tbl_TableForEachOutputEntry Tbl_TableForEachInputVar Tbl_TableForEachOutputVar Tbl_TableForEachDefault] ******************************************************************************/ array_t* TblRowReadInputs( Tbl_Row_t * row) { return (row->inputs); } /**Function******************************************************************** Synopsis [Read a table row] Description [Given a table and an integer rowNum, this return the rowNumth Tbl_Row_t] SideEffects [] SeeAlso [] ******************************************************************************/ Tbl_Row_t* TblTableReadRow( Tbl_Table_t *table, int rowNum) { return(array_fetch(Tbl_Row_t*,TblTableReadData(table),rowNum)); } /**Function******************************************************************** Synopsis [Allocate space for a row] Description [] SideEffects [] SeeAlso [] ******************************************************************************/ Tbl_Row_t* TblRowAlloc(void) { Tbl_Row_t *row; row = ALLOC(Tbl_Row_t,1); row->inputs = array_alloc(Tbl_Entry_t*,0); row->outputs = array_alloc(Tbl_Entry_t*,0); return row; } /**Function******************************************************************** Synopsis [Duplicate a table row] Description [] SideEffects [] SeeAlso [] ******************************************************************************/ Tbl_Row_t* TblRowDup( Tbl_Row_t * row) { Tbl_Row_t *newrow; Tbl_Entry_t *newEntry, *entry; int i; newrow = TblRowAlloc(); for (i=0; i < array_n(row->inputs); i++){ entry = array_fetch(Tbl_Entry_t*,row->inputs,i); if (entry != NIL(Tbl_Entry_t)) { newEntry= Tbl_EntryDup(entry); } else { newEntry = NIL(Tbl_Entry_t); } TblRowSetEntry(newrow,newEntry,i,0); } for (i=0; i < array_n(row->outputs); i++){ entry = array_fetch(Tbl_Entry_t*,row->outputs,i); if (entry != NIL(Tbl_Entry_t)) { newEntry = Tbl_EntryDup(entry); } else { newEntry = NIL(Tbl_Entry_t); } TblRowSetEntry(newrow,newEntry,i,1); } return newrow; } /**Function******************************************************************** Synopsis [Sets the entry in the given row at the given index] Description [Given a row, an entry , a flag set to 0 to indicate input and 1 for output, and an index, this function sets the entry in the row at the index.] SideEffects [The previous entry item at the index is lost] SeeAlso [] ******************************************************************************/ void TblRowSetEntry( Tbl_Row_t *row, Tbl_Entry_t * entry, int i, int flag) { array_t *carray; if (flag ==0) { carray = TblRowReadInputs(row); } else { carray = TblRowReadOutputs(row); } if (i < array_n(carray)){ array_insert(Tbl_Entry_t*,carray,i,entry); } else { array_insert_last(Tbl_Entry_t*,carray,entry); } } /**Function******************************************************************** Synopsis [Free a Tbl_Row_t] Description [Given a Tbl_Row_t, this function frees all memory associated with it. ] SideEffects [] SeeAlso [TblRowAlloc] ******************************************************************************/ void TblRowFree( Tbl_Row_t *row) { assert(row != NIL(Tbl_Row_t)); array_free(row->inputs); array_free(row->outputs); FREE(row); } /**Function******************************************************************** Synopsis [Read the specified index entry in the given row] Description [Given a Tbl_Row_t* and an integer i, this function returns the Tbl_Entry_t* at the ith position in the row.It must also be supplied with a flag to indicate whether an input or output entry is being read.] SideEffects [] SeeAlso [] ******************************************************************************/ Tbl_Entry_t* TblRowReadEntry( Tbl_Row_t *row, int i, int flag) { if (flag==0) { return(array_fetch(Tbl_Entry_t*,TblRowReadInputs(row),i)); } else { return(array_fetch(Tbl_Entry_t*, TblRowReadOutputs(row),i)); } } /*---------------------------------------------------------------------------*/ /* Definition of static functions */ /*---------------------------------------------------------------------------*/ /**Function******************************************************************** Synopsis [To compute a hash value for a table entry] Description [Given a Tbl_Table_t *table, and a Tbl_Entry_t *entry, this function computes the hash value for the corresponding entry] SideEffects [] SeeAlso [] ******************************************************************************/ static int TableEntryComputeHashVal( Tbl_Table_t *table, Tbl_Entry_t *entry) { int numRows, numCols; lsGen gen; int value; Tbl_Range_t *range; int total; numRows = Tbl_TableReadNumRows(table); numCols = Tbl_TableReadNumInputs(table) + Tbl_TableReadNumOutputs(table) + numRows+1; total = 0; if(entry->type == Tbl_EntryNormal_c) { Tbl_EntryForEachValue(entry,value,gen,range) { total = total + (int) pow(numCols,value); } } else if(entry->type == Tbl_EntryEqual_c) { value = Var_VariableReadNumValues(Tbl_EntryReadActualVar(table,entry)); total = total + (int) pow(numCols,value); } return total; } /**Function******************************************************************** Synopsis [Create a array of size entries, each intialized to -1] Description [Given an integer size, this function returns an array of size that has all entries intialized to -1] SideEffects [] SeeAlso [] ******************************************************************************/ static array_t* TableCreatIntArray( int size) { array_t *result; int i; result = array_alloc(int,0); for (i=0; i < size; i++) { array_insert_last(int,result,-1); } return result; } /**Function******************************************************************** Synopsis [Get table signature as a string] Description [optional] SideEffects [required] SeeAlso [optional] ******************************************************************************/ static char* TableObtainSignature(Tbl_Table_t * table, int outputColumn) { char * signature; char * sig; /* Signature under construction */ int row; /* locations in the table */ int column; Tbl_Entry_t * entry; /* Entry at row, column */ int value; /* Value of an entry */ lsGen gen; /* For Tbl_EntryForEachValue */ Tbl_Range_t * range; int varIndex; /* Index of the column of this variable */ /* * TODO: This is unsafe! */ signature = ALLOC( char, 10000 ); sig = signature; for ( row = Tbl_TableReadNumRows( table ) ; --row >=0 ; ) { /* * Print each of the inputs in this row */ Tbl_RowForEachInputEntry( table, row, entry, column ) { switch ( Tbl_EntryReadType( entry ) ) { /* * An equality entry ("this column is equal to that column") */ case Tbl_EntryEqual_c: /* * Find the column index, first assuming it's an input */ varIndex = Tbl_EntryReadVarIndex(entry); sprintf( sig, "=%d", varIndex ); sig += strlen( sig ); break; /* * A normal range entry - print a comma-separated list of values */ case Tbl_EntryNormal_c: Tbl_EntryForEachValue( entry, value, gen, range ) { sprintf(sig, "%d,", value ); sig += strlen( sig ); } break; /* * Unassigned -- append a "?" */ case Tbl_EntryUnassigned_c: sig[0] = '?'; sig++; break; /* * None of the Above -- we're in trouble */ default: assert(0); break; } /* * Separate entries with spaces */ sig[0] = ' '; sig++; } /* * Print the output column's entry */ entry = Tbl_TableReadEntry( table, row, outputColumn, 1 ); switch ( Tbl_EntryReadType( entry ) ) { /* * An equality entry ("this column is equal to that column") */ case Tbl_EntryEqual_c: /* * Find the column index, first assuming it's an input */ varIndex = Tbl_EntryReadVarIndex(entry); sprintf( sig, "=%d", varIndex ); sig += strlen( sig ); break; /* * A normal range entry - print a comma-separated list of values */ case Tbl_EntryNormal_c: Tbl_EntryForEachValue( entry, value, gen, range ) { sprintf(sig, "%d,", value ); sig += strlen( sig ); } break; /* * Unassigned -- append a "?" */ case Tbl_EntryUnassigned_c: sig[0] = '?'; sig++; break; /* * None of the Above -- we're in trouble */ default: assert(0); break; } /* * Separate rows with newlines */ sig[0] = '\n'; sig++; } /* * Terminate the signature string */ sig[0] = '\0'; return signature; } /**Function*********************************************************** Synopsis [Comparison function for qsort.] Description [This function is used by qsort to order table inputs according to the MDD variable order in the support of the MVF.] SideEffects [none] SeeAlso [Tbl_TableCreateTrueSupportTableForOutput] **********************************************************************/ static int varCompare(const void *x, const void *y) { Var_Ord_t *a = (Var_Ord_t *) x; Var_Ord_t *b = (Var_Ord_t *) y; return(a->rank - b->rank); }