Version abc71001

1 files changed, 402 insertions, 0 deletions

diff --git a/src/map/mapper/mapperTable.c b/src/map/mapper/mapperTable.c
new file mode 100644
index 00000000..d0cb7a01
--- /dev/null
+++ b/src/map/mapper/mapperTable.c
@@ -0,0 +1,402 @@
+/**CFile****************************************************************
+
+  FileName    [mapperTable.c]
+
+  PackageName [MVSIS 1.3: Multi-valued logic synthesis system.]
+
+  Synopsis    [Generic technology mapping engine.]
+
+  Author      [MVSIS Group]
+  
+  Affiliation [UC Berkeley]
+
+  Date        [Ver. 2.0. Started - June 1, 2004.]
+
+  Revision    [$Id: mapperTable.c,v 1.6 2005/01/23 06:59:44 alanmi Exp $]
+
+***********************************************************************/
+
+#include "mapperInt.h"
+
+////////////////////////////////////////////////////////////////////////
+///                        DECLARATIONS                              ///
+////////////////////////////////////////////////////////////////////////
+
+// the table function for the tables
+#define  MAP_TABLE_HASH(u1,u2,nSize)  (((u1) + 2003 * (u2)) % nSize)
+
+static void Map_SuperTableResize( Map_HashTable_t * pLib );
+
+////////////////////////////////////////////////////////////////////////
+///                     FUNCTION DEFINITIONS                         ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+  Synopsis    [Creates the hash table for supergates.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Map_HashTable_t * Map_SuperTableCreate( Map_SuperLib_t * pLib )
+{
+    Map_HashTable_t * p;
+    // allocate the table
+    p = ALLOC( Map_HashTable_t, 1 );
+    memset( p, 0, sizeof(Map_HashTable_t) );
+    p->mmMan = pLib->mmEntries;
+    // allocate and clean the bins
+    p->nBins = Cudd_Prime(20000);
+    p->pBins = ALLOC( Map_HashEntry_t *, p->nBins );
+    memset( p->pBins, 0, sizeof(Map_HashEntry_t *) * p->nBins );
+    return p;
+}
+
+
+/**Function*************************************************************
+
+  Synopsis    [Deallocates the supergate hash table.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Map_SuperTableFree( Map_HashTable_t * p )
+{
+    FREE( p->pBins );
+    FREE( p );
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Inserts a new entry into the hash table.]
+
+  Description [This function inserts the new gate (pGate), which will be
+  accessible through its canonical form (uTruthC).]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Map_SuperTableInsertC( Map_HashTable_t * p, unsigned uTruthC[], Map_Super_t * pGate )
+{
+    Map_HashEntry_t * pEnt;
+    unsigned Key;
+    // resize the table
+    if ( p->nEntries >= 2 * p->nBins )
+        Map_SuperTableResize( p );
+    // check if another supergate with the same canonical form exists
+    Key = MAP_TABLE_HASH( uTruthC[0], uTruthC[1], p->nBins );
+    for ( pEnt = p->pBins[Key]; pEnt; pEnt = pEnt->pNext )
+        if ( pEnt->uTruth[0] == uTruthC[0] && pEnt->uTruth[1] == uTruthC[1] )
+            break;
+    // create a new entry if it does not exist
+    if ( pEnt == NULL )
+    {
+        // add the new entry to the table
+        pEnt = (Map_HashEntry_t *)Extra_MmFixedEntryFetch( p->mmMan );
+        memset( pEnt, 0, sizeof(Map_HashEntry_t) );
+        pEnt->uTruth[0] = uTruthC[0];
+        pEnt->uTruth[1] = uTruthC[1];
+        // add the hash table entry to the corresponding linked list in the table
+        pEnt->pNext   = p->pBins[Key];
+        p->pBins[Key] = pEnt;
+        p->nEntries++;
+    }
+    // add the supergate to the entry
+    pGate->pNext = pEnt->pGates;
+    pEnt->pGates = pGate;
+    return 0;
+}
+
+
+
+/**Function*************************************************************
+
+  Synopsis    [Inserts a new entry into the library.]
+
+  Description [This function inserts the new gate (pGate), which will be
+  accessible through its unfolded function (uTruth).]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Map_SuperTableInsert( Map_HashTable_t * p, unsigned uTruth[], Map_Super_t * pGate, unsigned uPhase )
+{
+    Map_HashEntry_t * pEnt;
+    unsigned Key;
+    // resize the table
+    if ( p->nEntries >= 2 * p->nBins )
+        Map_SuperTableResize( p );
+    // check if this entry already exists
+    Key = MAP_TABLE_HASH( uTruth[0], uTruth[1], p->nBins );
+    for ( pEnt = p->pBins[Key]; pEnt; pEnt = pEnt->pNext )
+        if ( pEnt->uTruth[0] == uTruth[0] && pEnt->uTruth[1] == uTruth[1] )
+            return 1;
+    // add the new hash table entry to the table
+    pEnt = (Map_HashEntry_t *)Extra_MmFixedEntryFetch( p->mmMan );
+    memset( pEnt, 0, sizeof(Map_HashEntry_t) );
+    pEnt->uTruth[0] = uTruth[0];
+    pEnt->uTruth[1] = uTruth[1];
+    pEnt->pGates    = pGate;
+    pEnt->uPhase    = uPhase;
+    // add the hash table to the corresponding linked list in the table
+    pEnt->pNext   = p->pBins[Key];
+    p->pBins[Key] = pEnt;
+    p->nEntries++;
+/*
+printf( "Adding gate: %10u ", Key );
+Map_LibraryPrintSupergate( pGate );
+Extra_PrintBinary( stdout, uTruth, 32 );
+printf( "\n" );
+*/
+    return 0;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Looks up an entry in the library.]
+
+  Description [This function looks up the function, given by its truth table,
+  and return two things: (1) the linked list of supergates, which can implement
+  the functions of this N-class; (2) the phase, which should be applied to the
+  given function, in order to derive the canonical form of this N-class.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Map_Super_t * Map_SuperTableLookupC( Map_SuperLib_t * p, unsigned uTruth[] )
+{
+    Map_HashEntry_t * pEnt;
+    unsigned Key;
+    Key = MAP_TABLE_HASH( uTruth[0], uTruth[1], p->tTableC->nBins );
+    for ( pEnt = p->tTableC->pBins[Key]; pEnt; pEnt = pEnt->pNext )
+        if ( pEnt->uTruth[0] == uTruth[0] && pEnt->uTruth[1] == uTruth[1] )
+            return pEnt->pGates;
+    return NULL;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Looks up an entry in the library.]
+
+  Description [This function looks up the function, given by its truth table,
+  and return two things: (1) the linked list of supergates, which can implement
+  the functions of this N-class; (2) the phase, which should be applied to the
+  given function, in order to derive the canonical form of this N-class.]
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Map_Super_t * Map_SuperTableLookup( Map_HashTable_t * p, unsigned uTruth[], unsigned * puPhase )
+{
+    Map_HashEntry_t * pEnt;
+    unsigned Key;
+    Key = MAP_TABLE_HASH( uTruth[0], uTruth[1], p->nBins );
+    for ( pEnt = p->pBins[Key]; pEnt; pEnt = pEnt->pNext )
+        if ( pEnt->uTruth[0] == uTruth[0] && pEnt->uTruth[1] == uTruth[1] )
+        {
+            *puPhase = pEnt->uPhase;
+            return pEnt->pGates;
+        }
+    return NULL;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Resizes the table.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Map_SuperTableResize( Map_HashTable_t * p )
+{
+    Map_HashEntry_t ** pBinsNew;
+    Map_HashEntry_t * pEnt, * pEnt2;
+    int nBinsNew, Counter, i, clk = clock();
+    unsigned Key;
+    // get the new table size
+    nBinsNew = Cudd_Prime(2 * p->nBins); 
+    // allocate a new array
+    pBinsNew = ALLOC( Map_HashEntry_t *, nBinsNew );
+    memset( pBinsNew, 0, sizeof(Map_HashEntry_t *) * nBinsNew );
+    // rehash the entries from the old table
+    Counter = 0;
+    for ( i = 0; i < p->nBins; i++ )
+        for ( pEnt = p->pBins[i], pEnt2 = pEnt? pEnt->pNext: NULL; pEnt; 
+              pEnt = pEnt2, pEnt2 = pEnt? pEnt->pNext: NULL )
+        {
+            Key = MAP_TABLE_HASH( pEnt->uTruth[0], pEnt->uTruth[1], nBinsNew );
+            pEnt->pNext   = pBinsNew[Key];
+            pBinsNew[Key] = pEnt;
+            Counter++;
+        }
+    assert( Counter == p->nEntries );
+    // replace the table and the parameters
+    free( p->pBins );
+    p->pBins = pBinsNew;
+    p->nBins = nBinsNew;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Compares the supergates by the number of times they are used.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Map_SuperTableCompareSupergates( Map_Super_t ** ppS1, Map_Super_t ** ppS2 )
+{
+    if ( (*ppS1)->nUsed > (*ppS2)->nUsed )
+        return -1;
+    if ( (*ppS1)->nUsed < (*ppS2)->nUsed )
+        return 1;
+    return 0;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Compares the supergates by the number of times they are used.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+int Map_SuperTableCompareGatesInList( Map_Super_t ** ppS1, Map_Super_t ** ppS2 )
+{
+//   if ( (*ppS1)->tDelayMax.Rise > (*ppS2)->tDelayMax.Rise )
+    if ( (*ppS1)->Area > (*ppS2)->Area )
+        return -1;
+//   if ( (*ppS1)->tDelayMax.Rise < (*ppS2)->tDelayMax.Rise )
+    if ( (*ppS1)->Area < (*ppS2)->Area )
+        return 1;
+    return 0;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Sorts supergates by usefulness and prints out most useful.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Map_SuperTableSortSupergates( Map_HashTable_t * p, int nSupersMax )
+{
+    Map_HashEntry_t * pEnt;
+    Map_Super_t ** ppSupers;
+    Map_Super_t * pSuper;
+    int nSupers, i;
+
+    // copy all the supergates into one array
+    ppSupers = ALLOC( Map_Super_t *, nSupersMax );
+    nSupers = 0;
+    for ( i = 0; i < p->nBins; i++ )
+        for ( pEnt = p->pBins[i]; pEnt; pEnt = pEnt->pNext )
+            for ( pSuper = pEnt->pGates; pSuper; pSuper = pSuper->pNext )
+                ppSupers[nSupers++] = pSuper;
+
+    // sort by usage
+    qsort( (void *)ppSupers, nSupers, sizeof(Map_Super_t *), 
+            (int (*)(const void *, const void *)) Map_SuperTableCompareSupergates );
+    assert( Map_SuperTableCompareSupergates( ppSupers, ppSupers + nSupers - 1 ) <= 0 );
+
+    // print out the "top ten"
+//    for ( i = 0; i < nSupers; i++ )
+    for ( i = 0; i < 10; i++ )
+    {
+        if ( ppSupers[i]->nUsed == 0 )
+            break;
+        printf( "%5d : ",        ppSupers[i]->nUsed );
+        printf( "%5d   ",        ppSupers[i]->Num );
+        printf( "A = %5.2f   ",  ppSupers[i]->Area );
+        printf( "D = %5.2f   ",  ppSupers[i]->tDelayMax.Rise );
+        printf( "%s",            ppSupers[i]->pFormula );
+        printf( "\n" );
+    }
+    free( ppSupers );
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Sorts supergates by max delay for each truth table.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Map_SuperTableSortSupergatesByDelay( Map_HashTable_t * p, int nSupersMax )
+{
+    Map_HashEntry_t * pEnt;
+    Map_Super_t ** ppSupers;
+    Map_Super_t * pSuper;
+    int nSupers, i, k;
+
+    ppSupers = ALLOC( Map_Super_t *, nSupersMax );
+    for ( i = 0; i < p->nBins; i++ )
+        for ( pEnt = p->pBins[i]; pEnt; pEnt = pEnt->pNext )
+        {
+            // collect the gates in this entry
+            nSupers = 0;
+            for ( pSuper = pEnt->pGates; pSuper; pSuper = pSuper->pNext )
+            {
+                // skip supergates, whose root is the AND gate
+//                if ( strcmp( Mio_GateReadName(pSuper->pRoot), "and" ) == 0 )
+//                    continue;
+                ppSupers[nSupers++] = pSuper;
+            }
+            pEnt->pGates = NULL;
+            if ( nSupers == 0 )
+                continue;
+            // sort the gates by delay
+            qsort( (void *)ppSupers, nSupers, sizeof(Map_Super_t *), 
+                    (int (*)(const void *, const void *)) Map_SuperTableCompareGatesInList );
+            assert( Map_SuperTableCompareGatesInList( ppSupers, ppSupers + nSupers - 1 ) <= 0 );
+            // link them in the reverse order
+            for ( k = 0; k < nSupers; k++ )
+            {
+                ppSupers[k]->pNext = pEnt->pGates;
+                pEnt->pGates = ppSupers[k];
+            }
+            // save the number of supergates in the list
+            pEnt->pGates->nSupers = nSupers;
+        }
+    FREE( ppSupers );
+}
+
+////////////////////////////////////////////////////////////////////////
+///                       END OF FILE                                ///
+////////////////////////////////////////////////////////////////////////
+
+