#include "fraigInt.h"

Functions
static ABC_NAMESPACE_IMPL_START void	Fraig_TableResizeS (Fraig_HashTable_t *p)
	DECLARATIONS ///. More...

static void	Fraig_TableResizeF (Fraig_HashTable_t *p, int fUseSimR)

Fraig_HashTable_t *	Fraig_HashTableCreate (int nSize)
	FUNCTION DEFINITIONS ///. More...

void	Fraig_HashTableFree (Fraig_HashTable_t *p)

int	Fraig_HashTableLookupS (Fraig_Man_t pMan, Fraig_Node_t p1, Fraig_Node_t p2, Fraig_Node_t *ppNodeRes)

Fraig_Node_t *	Fraig_HashTableLookupF (Fraig_Man_t pMan, Fraig_Node_t pNode)

Fraig_Node_t *	Fraig_HashTableLookupF0 (Fraig_Man_t pMan, Fraig_Node_t pNode)

void	Fraig_HashTableInsertF0 (Fraig_Man_t pMan, Fraig_Node_t pNode)

int	Fraig_CompareSimInfo (Fraig_Node_t pNode1, Fraig_Node_t pNode2, int iWordLast, int fUseRand)

int	Fraig_FindFirstDiff (Fraig_Node_t pNode1, Fraig_Node_t pNode2, int fCompl, int iWordLast, int fUseRand)

int	Fraig_CompareSimInfoUnderMask (Fraig_Node_t pNode1, Fraig_Node_t pNode2, int iWordLast, int fUseRand, unsigned *puMask)

void	Fraig_CollectXors (Fraig_Node_t pNode1, Fraig_Node_t pNode2, int iWordLast, int fUseRand, unsigned *puMask)

void	Fraig_TablePrintStatsS (Fraig_Man_t *pMan)

void	Fraig_TablePrintStatsF (Fraig_Man_t *pMan)

void	Fraig_TablePrintStatsF0 (Fraig_Man_t *pMan)

int	Fraig_TableRehashF0 (Fraig_Man_t *pMan, int fLinkEquiv)

Function Documentation

void Fraig_CollectXors	(	Fraig_Node_t *	pNode1,
		Fraig_Node_t *	pNode2,
		int	iWordLast,
		int	fUseRand,
		unsigned *	puMask
	)

Function*************************************************************

Synopsis [Compares two pieces of simulation info.]

Description [Returns 1 if they are equal.]

SideEffects []

SeeAlso []

Definition at line 478 of file fraigTable.c.

 {
     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] );
 }

int Fraig_CompareSimInfo	(	Fraig_Node_t *	pNode1,
		Fraig_Node_t *	pNode2,
		int	iWordLast,
		int	fUseRand
	)

Function*************************************************************

Synopsis [Compares two pieces of simulation info.]

Description [Returns 1 if they are equal.]

SideEffects []

SeeAlso []

Definition at line 351 of file fraigTable.c.

 {
     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;
 }

int Fraig_CompareSimInfoUnderMask	(	Fraig_Node_t *	pNode1,
		Fraig_Node_t *	pNode2,
		int	iWordLast,
		int	fUseRand,
		unsigned *	puMask
	)

Function*************************************************************

Synopsis [Compares two pieces of simulation info.]

Description [Returns 1 if they are equal.]

SideEffects []

SeeAlso []

Definition at line 451 of file fraigTable.c.

 {
     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;
 }

int Fraig_FindFirstDiff	(	Fraig_Node_t *	pNode1,
		Fraig_Node_t *	pNode2,
		int	fCompl,
		int	iWordLast,
		int	fUseRand
	)

Function*************************************************************

Synopsis [Find the number of the different pattern.]

Description [Returns -1 if there is no such pattern]

SideEffects []

SeeAlso []

Definition at line 390 of file fraigTable.c.

 {
     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;
 }

Fraig_HashTable_t* Fraig_HashTableCreate ( int nSize )

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis [Allocates the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 46 of file fraigTable.c.

 {
     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;
 }

void Fraig_HashTableFree ( Fraig_HashTable_t * p )

Function*************************************************************

Synopsis [Deallocates the supergate hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 70 of file fraigTable.c.

 {
     ABC_FREE( p->pBins );
     ABC_FREE( p );
 }

void Fraig_HashTableInsertF0	(	Fraig_Man_t *	pMan,
		Fraig_Node_t *	pNode
	)

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 []

Definition at line 237 of file fraigTable.c.

 {
     Fraig_HashTable_t * p = pMan->pTableF0;
     unsigned Key = pNode->uHashD % p->nBins;
 
     pNode->pNextF = p->pBins[Key];
     p->pBins[Key] = pNode;
     p->nEntries++;
 }

Fraig_Node_t* Fraig_HashTableLookupF	(	Fraig_Man_t *	pMan,
		Fraig_Node_t *	pNode
	)

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 []

Definition at line 136 of file fraigTable.c.

 {
     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;
 }

Fraig_Node_t* Fraig_HashTableLookupF0	(	Fraig_Man_t *	pMan,
		Fraig_Node_t *	pNode
	)

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 []

Definition at line 193 of file fraigTable.c.

 {
     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;
 }

int Fraig_HashTableLookupS	(	Fraig_Man_t *	pMan,
		Fraig_Node_t *	p1,
		Fraig_Node_t *	p2,
		Fraig_Node_t **	ppNodeRes
	)

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 []

Definition at line 90 of file fraigTable.c.

 {
     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;
 }

void Fraig_TablePrintStatsF ( Fraig_Man_t * pMan )

Function*************************************************************

Synopsis [Prints stats of the structural table.]

Description []

SideEffects []

SeeAlso []

Definition at line 537 of file fraigTable.c.

 {
     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" );
 }

void Fraig_TablePrintStatsF0 ( Fraig_Man_t * pMan )

Function*************************************************************

Synopsis [Prints stats of the structural table.]

Description []

SideEffects []

SeeAlso []

Definition at line 566 of file fraigTable.c.

 {
     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" );
 }

void Fraig_TablePrintStatsS ( Fraig_Man_t * pMan )

Function*************************************************************

Synopsis [Prints stats of the structural table.]

Description []

SideEffects []

SeeAlso []

Definition at line 504 of file fraigTable.c.

 {
     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" );
 }

int Fraig_TableRehashF0	(	Fraig_Man_t *	pMan,
		int	fLinkEquiv
	)

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 []

Definition at line 604 of file fraigTable.c.

 {
     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;
 }

void Fraig_TableResizeF	(	Fraig_HashTable_t *	p,
		int	fUseSimR
	)

static

Function*************************************************************

Synopsis [Resizes the table.]

Description []

SideEffects []

SeeAlso []

Definition at line 303 of file fraigTable.c.

 {
     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;
 }

void Fraig_TableResizeS ( Fraig_HashTable_t * p )

static

DECLARATIONS ///.

CFile****************************************************************

FileName [fraigTable.c]

PackageName [FRAIG: Functionally reduced AND-INV graphs.]

Synopsis [Structural and functional hash tables.]

Author [Alan Mishchenko alanm.nosp@m.i@ee.nosp@m.cs.be.nosp@m.rkel.nosp@m.ey.ed.nosp@m.u]

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

]

Function*************************************************************

Synopsis [Resizes the table.]

Description []

SideEffects []

SeeAlso []

Definition at line 259 of file fraigTable.c.

 {
     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;
 }

Functions

Function Documentation