/**CFile**************************************************************** FileName [fraigTable.c] PackageName [FRAIG: Functionally reduced AND-INV graphs.] Synopsis [Structural and functional hash tables.] Author [Alan Mishchenko ] Affiliation [UC Berkeley] Date [Ver. 2.0. Started - October 1, 2004] Revision [$Id: fraigTable.c,v 1.7 2005/07/08 01:01:34 alanmi Exp $] ***********************************************************************/ #include "fraigInt.h" ABC_NAMESPACE_IMPL_START //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// static void Fraig_TableResizeS( Fraig_HashTable_t * p ); static void Fraig_TableResizeF( Fraig_HashTable_t * p, int fUseSimR ); //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* Synopsis [Allocates the hash table.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Fraig_HashTable_t * Fraig_HashTableCreate( int nSize ) { Fraig_HashTable_t * p; // allocate the table p = ABC_ALLOC( Fraig_HashTable_t, 1 ); memset( p, 0, sizeof(Fraig_HashTable_t) ); // allocate and clean the bins p->nBins = Abc_PrimeCudd(nSize); p->pBins = ABC_ALLOC( Fraig_Node_t *, p->nBins ); memset( p->pBins, 0, sizeof(Fraig_Node_t *) * p->nBins ); return p; } /**Function************************************************************* Synopsis [Deallocates the supergate hash table.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Fraig_HashTableFree( Fraig_HashTable_t * p ) { ABC_FREE( p->pBins ); ABC_FREE( p ); } /**Function************************************************************* Synopsis [Looks up an entry in the structural hash table.] Description [If the entry with the same children does not exists, creates it, inserts it into the table, and returns 0. If the entry with the same children exists, finds it, and return 1. In both cases, the new/old entry is returned in ppNodeRes.] SideEffects [] SeeAlso [] ***********************************************************************/ int Fraig_HashTableLookupS( Fraig_Man_t * pMan, Fraig_Node_t * p1, Fraig_Node_t * p2, Fraig_Node_t ** ppNodeRes ) { Fraig_HashTable_t * p = pMan->pTableS; Fraig_Node_t * pEnt; unsigned Key; // order the arguments if ( Fraig_Regular(p1)->Num > Fraig_Regular(p2)->Num ) pEnt = p1, p1 = p2, p2 = pEnt; Key = Fraig_HashKey2( p1, p2, p->nBins ); Fraig_TableBinForEachEntryS( p->pBins[Key], pEnt ) if ( pEnt->p1 == p1 && pEnt->p2 == p2 ) { *ppNodeRes = pEnt; return 1; } // check if it is a good time for table resizing if ( p->nEntries >= 2 * p->nBins ) { Fraig_TableResizeS( p ); Key = Fraig_HashKey2( p1, p2, p->nBins ); } // create the new node pEnt = Fraig_NodeCreate( pMan, p1, p2 ); // add the node to the corresponding linked list in the table pEnt->pNextS = p->pBins[Key]; p->pBins[Key] = pEnt; *ppNodeRes = pEnt; p->nEntries++; return 0; } /**Function************************************************************* Synopsis [Insert the entry in the functional hash table.] Description [If the entry with the same key exists, return it right away. If the entry with the same key does not exists, inserts it and returns NULL. ] SideEffects [] SeeAlso [] ***********************************************************************/ Fraig_Node_t * Fraig_HashTableLookupF( Fraig_Man_t * pMan, Fraig_Node_t * pNode ) { Fraig_HashTable_t * p = pMan->pTableF; Fraig_Node_t * pEnt, * pEntD; unsigned Key; // go through the hash table entries Key = pNode->uHashR % p->nBins; Fraig_TableBinForEachEntryF( p->pBins[Key], pEnt ) { // if their simulation info differs, skip if ( !Fraig_CompareSimInfo( pNode, pEnt, pMan->nWordsRand, 1 ) ) continue; // equivalent up to the complement Fraig_TableBinForEachEntryD( pEnt, pEntD ) { // if their simulation info differs, skip if ( !Fraig_CompareSimInfo( pNode, pEntD, pMan->iWordStart, 0 ) ) continue; // found a simulation-equivalent node return pEntD; } // did not find a simulation equivalent node // add the node to the corresponding linked list pNode->pNextD = pEnt->pNextD; pEnt->pNextD = pNode; // return NULL, because there is no functional equivalence in this case return NULL; } // check if it is a good time for table resizing if ( p->nEntries >= 2 * p->nBins ) { Fraig_TableResizeF( p, 1 ); Key = pNode->uHashR % p->nBins; } // add the node to the corresponding linked list in the table pNode->pNextF = p->pBins[Key]; p->pBins[Key] = pNode; p->nEntries++; // return NULL, because there is no functional equivalence in this case return NULL; } /**Function************************************************************* Synopsis [Insert the entry in the functional hash table.] Description [If the entry with the same key exists, return it right away. If the entry with the same key does not exists, inserts it and returns NULL. ] SideEffects [] SeeAlso [] ***********************************************************************/ Fraig_Node_t * Fraig_HashTableLookupF0( Fraig_Man_t * pMan, Fraig_Node_t * pNode ) { Fraig_HashTable_t * p = pMan->pTableF0; Fraig_Node_t * pEnt; unsigned Key; // go through the hash table entries Key = pNode->uHashD % p->nBins; Fraig_TableBinForEachEntryF( p->pBins[Key], pEnt ) { // if their simulation info differs, skip if ( !Fraig_CompareSimInfo( pNode, pEnt, pMan->iWordStart, 0 ) ) continue; // found a simulation-equivalent node return pEnt; } // check if it is a good time for table resizing if ( p->nEntries >= 2 * p->nBins ) { Fraig_TableResizeF( p, 0 ); Key = pNode->uHashD % p->nBins; } // add the node to the corresponding linked list in the table pNode->pNextF = p->pBins[Key]; p->pBins[Key] = pNode; p->nEntries++; // return NULL, because there is no functional equivalence in this case return NULL; } /**Function************************************************************* Synopsis [Insert the entry in the functional hash table.] Description [Unconditionally add the node to the corresponding linked list in the table.] SideEffects [] SeeAlso [] ***********************************************************************/ void Fraig_HashTableInsertF0( Fraig_Man_t * pMan, Fraig_Node_t * pNode ) { Fraig_HashTable_t * p = pMan->pTableF0; unsigned Key = pNode->uHashD % p->nBins; pNode->pNextF = p->pBins[Key]; p->pBins[Key] = pNode; p->nEntries++; } /**Function************************************************************* Synopsis [Resizes the table.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Fraig_TableResizeS( Fraig_HashTable_t * p ) { Fraig_Node_t ** pBinsNew; Fraig_Node_t * pEnt, * pEnt2; int nBinsNew, Counter, i; abctime clk; unsigned Key; clk = Abc_Clock(); // get the new table size nBinsNew = Abc_PrimeCudd(2 * p->nBins); // allocate a new array pBinsNew = ABC_ALLOC( Fraig_Node_t *, nBinsNew ); memset( pBinsNew, 0, sizeof(Fraig_Node_t *) * nBinsNew ); // rehash the entries from the old table Counter = 0; for ( i = 0; i < p->nBins; i++ ) Fraig_TableBinForEachEntrySafeS( p->pBins[i], pEnt, pEnt2 ) { Key = Fraig_HashKey2( pEnt->p1, pEnt->p2, nBinsNew ); pEnt->pNextS = pBinsNew[Key]; pBinsNew[Key] = pEnt; Counter++; } assert( Counter == p->nEntries ); // printf( "Increasing the structural table size from %6d to %6d. ", p->nBins, nBinsNew ); // ABC_PRT( "Time", Abc_Clock() - clk ); // replace the table and the parameters ABC_FREE( p->pBins ); p->pBins = pBinsNew; p->nBins = nBinsNew; } /**Function************************************************************* Synopsis [Resizes the table.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Fraig_TableResizeF( Fraig_HashTable_t * p, int fUseSimR ) { Fraig_Node_t ** pBinsNew; Fraig_Node_t * pEnt, * pEnt2; int nBinsNew, Counter, i; abctime clk; unsigned Key; clk = Abc_Clock(); // get the new table size nBinsNew = Abc_PrimeCudd(2 * p->nBins); // allocate a new array pBinsNew = ABC_ALLOC( Fraig_Node_t *, nBinsNew ); memset( pBinsNew, 0, sizeof(Fraig_Node_t *) * nBinsNew ); // rehash the entries from the old table Counter = 0; for ( i = 0; i < p->nBins; i++ ) Fraig_TableBinForEachEntrySafeF( p->pBins[i], pEnt, pEnt2 ) { if ( fUseSimR ) Key = pEnt->uHashR % nBinsNew; else Key = pEnt->uHashD % nBinsNew; pEnt->pNextF = pBinsNew[Key]; pBinsNew[Key] = pEnt; Counter++; } assert( Counter == p->nEntries ); // printf( "Increasing the functional table size from %6d to %6d. ", p->nBins, nBinsNew ); // ABC_PRT( "Time", Abc_Clock() - clk ); // replace the table and the parameters ABC_FREE( p->pBins ); p->pBins = pBinsNew; p->nBins = nBinsNew; } /**Function************************************************************* Synopsis [Compares two pieces of simulation info.] Description [Returns 1 if they are equal.] SideEffects [] SeeAlso [] ***********************************************************************/ int Fraig_CompareSimInfo( Fraig_Node_t * pNode1, Fraig_Node_t * pNode2, int iWordLast, int fUseRand ) { int i; assert( !Fraig_IsComplement(pNode1) ); assert( !Fraig_IsComplement(pNode2) ); if ( fUseRand ) { // if their signatures differ, skip if ( pNode1->uHashR != pNode2->uHashR ) return 0; // check the simulation info for ( i = 0; i < iWordLast; i++ ) if ( pNode1->puSimR[i] != pNode2->puSimR[i] ) return 0; } else { // if their signatures differ, skip if ( pNode1->uHashD != pNode2->uHashD ) return 0; // check the simulation info for ( i = 0; i < iWordLast; i++ ) if ( pNode1->puSimD[i] != pNode2->puSimD[i] ) return 0; } return 1; } /**Function************************************************************* Synopsis [Find the number of the different pattern.] Description [Returns -1 if there is no such pattern] SideEffects [] SeeAlso [] ***********************************************************************/ int Fraig_FindFirstDiff( Fraig_Node_t * pNode1, Fraig_Node_t * pNode2, int fCompl, int iWordLast, int fUseRand ) { int i, v; assert( !Fraig_IsComplement(pNode1) ); assert( !Fraig_IsComplement(pNode2) ); // take into account possible internal complementation fCompl ^= pNode1->fInv; fCompl ^= pNode2->fInv; // find the pattern if ( fCompl ) { if ( fUseRand ) { for ( i = 0; i < iWordLast; i++ ) if ( pNode1->puSimR[i] != ~pNode2->puSimR[i] ) for ( v = 0; v < 32; v++ ) if ( (pNode1->puSimR[i] ^ ~pNode2->puSimR[i]) & (1 << v) ) return i * 32 + v; } else { for ( i = 0; i < iWordLast; i++ ) if ( pNode1->puSimD[i] != ~pNode2->puSimD[i] ) for ( v = 0; v < 32; v++ ) if ( (pNode1->puSimD[i] ^ ~pNode2->puSimD[i]) & (1 << v) ) return i * 32 + v; } } else { if ( fUseRand ) { for ( i = 0; i < iWordLast; i++ ) if ( pNode1->puSimR[i] != pNode2->puSimR[i] ) for ( v = 0; v < 32; v++ ) if ( (pNode1->puSimR[i] ^ pNode2->puSimR[i]) & (1 << v) ) return i * 32 + v; } else { for ( i = 0; i < iWordLast; i++ ) if ( pNode1->puSimD[i] != pNode2->puSimD[i] ) for ( v = 0; v < 32; v++ ) if ( (pNode1->puSimD[i] ^ pNode2->puSimD[i]) & (1 << v) ) return i * 32 + v; } } return -1; } /**Function************************************************************* Synopsis [Compares two pieces of simulation info.] Description [Returns 1 if they are equal.] SideEffects [] SeeAlso [] ***********************************************************************/ int Fraig_CompareSimInfoUnderMask( Fraig_Node_t * pNode1, Fraig_Node_t * pNode2, int iWordLast, int fUseRand, unsigned * puMask ) { unsigned * pSims1, * pSims2; int i; assert( !Fraig_IsComplement(pNode1) ); assert( !Fraig_IsComplement(pNode2) ); // get hold of simulation info pSims1 = fUseRand? pNode1->puSimR : pNode1->puSimD; pSims2 = fUseRand? pNode2->puSimR : pNode2->puSimD; // check the simulation info for ( i = 0; i < iWordLast; i++ ) if ( (pSims1[i] & puMask[i]) != (pSims2[i] & puMask[i]) ) return 0; return 1; } /**Function************************************************************* Synopsis [Compares two pieces of simulation info.] Description [Returns 1 if they are equal.] SideEffects [] SeeAlso [] ***********************************************************************/ void Fraig_CollectXors( Fraig_Node_t * pNode1, Fraig_Node_t * pNode2, int iWordLast, int fUseRand, unsigned * puMask ) { unsigned * pSims1, * pSims2; int i; assert( !Fraig_IsComplement(pNode1) ); assert( !Fraig_IsComplement(pNode2) ); // get hold of simulation info pSims1 = fUseRand? pNode1->puSimR : pNode1->puSimD; pSims2 = fUseRand? pNode2->puSimR : pNode2->puSimD; // check the simulation info for ( i = 0; i < iWordLast; i++ ) puMask[i] = ( pSims1[i] ^ pSims2[i] ); } /**Function************************************************************* Synopsis [Prints stats of the structural table.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Fraig_TablePrintStatsS( Fraig_Man_t * pMan ) { Fraig_HashTable_t * pT = pMan->pTableS; Fraig_Node_t * pNode; int i, Counter; printf( "Structural table. Table size = %d. Number of entries = %d.\n", pT->nBins, pT->nEntries ); for ( i = 0; i < pT->nBins; i++ ) { Counter = 0; Fraig_TableBinForEachEntryS( pT->pBins[i], pNode ) Counter++; if ( Counter > 1 ) { printf( "%d ", Counter ); if ( Counter > 50 ) printf( "{%d} ", i ); } } printf( "\n" ); } /**Function************************************************************* Synopsis [Prints stats of the structural table.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Fraig_TablePrintStatsF( Fraig_Man_t * pMan ) { Fraig_HashTable_t * pT = pMan->pTableF; Fraig_Node_t * pNode; int i, Counter; printf( "Functional table. Table size = %d. Number of entries = %d.\n", pT->nBins, pT->nEntries ); for ( i = 0; i < pT->nBins; i++ ) { Counter = 0; Fraig_TableBinForEachEntryF( pT->pBins[i], pNode ) Counter++; if ( Counter > 1 ) printf( "{%d} ", Counter ); } printf( "\n" ); } /**Function************************************************************* Synopsis [Prints stats of the structural table.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Fraig_TablePrintStatsF0( Fraig_Man_t * pMan ) { Fraig_HashTable_t * pT = pMan->pTableF0; Fraig_Node_t * pNode; int i, Counter; printf( "Zero-node table. Table size = %d. Number of entries = %d.\n", pT->nBins, pT->nEntries ); for ( i = 0; i < pT->nBins; i++ ) { Counter = 0; Fraig_TableBinForEachEntryF( pT->pBins[i], pNode ) Counter++; if ( Counter == 0 ) continue; /* printf( "\nBin = %4d : Number of entries = %4d\n", i, Counter ); Fraig_TableBinForEachEntryF( pT->pBins[i], pNode ) printf( "Node %5d. Hash = %10d.\n", pNode->Num, pNode->uHashD ); */ } printf( "\n" ); } /**Function************************************************************* Synopsis [Rehashes the table after the simulation info has changed.] Description [Assumes that the hash values have been updated after performing additional simulation. Rehashes the table using the new hash values. Uses pNextF to link the entries in the bins. Uses pNextD to link the entries with identical hash values. Returns 1 if the identical entries have been found. Note that identical hash values may mean that the simulation data is different.] SideEffects [] SeeAlso [] ***********************************************************************/ int Fraig_TableRehashF0( Fraig_Man_t * pMan, int fLinkEquiv ) { Fraig_HashTable_t * pT = pMan->pTableF0; Fraig_Node_t ** pBinsNew; Fraig_Node_t * pEntF, * pEntF2, * pEnt, * pEntD2, * pEntN; int ReturnValue, Counter, i; unsigned Key; // allocate a new array of bins pBinsNew = ABC_ALLOC( Fraig_Node_t *, pT->nBins ); memset( pBinsNew, 0, sizeof(Fraig_Node_t *) * pT->nBins ); // rehash the entries in the table // go through all the nodes in the F-lists (and possible in D-lists, if used) Counter = 0; ReturnValue = 0; for ( i = 0; i < pT->nBins; i++ ) Fraig_TableBinForEachEntrySafeF( pT->pBins[i], pEntF, pEntF2 ) Fraig_TableBinForEachEntrySafeD( pEntF, pEnt, pEntD2 ) { // decide where to put entry pEnt Key = pEnt->uHashD % pT->nBins; if ( fLinkEquiv ) { // go through the entries in the new bin Fraig_TableBinForEachEntryF( pBinsNew[Key], pEntN ) { // if they have different values skip if ( pEnt->uHashD != pEntN->uHashD ) continue; // they have the same hash value, add pEnt to the D-list pEnt3 pEnt->pNextD = pEntN->pNextD; pEntN->pNextD = pEnt; ReturnValue = 1; Counter++; break; } if ( pEntN != NULL ) // already linked continue; // we did not find equal entry } // link the new entry pEnt->pNextF = pBinsNew[Key]; pBinsNew[Key] = pEnt; pEnt->pNextD = NULL; Counter++; } assert( Counter == pT->nEntries ); // replace the table and the parameters ABC_FREE( pT->pBins ); pT->pBins = pBinsNew; return ReturnValue; } //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// ABC_NAMESPACE_IMPL_END