mapperTable.c

/**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"

ABC_NAMESPACE_IMPL_START


////////////////////////////////////////////////////////////////////////
///                        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 = ABC_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 = ABC_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 )
{
    ABC_FREE( p->pBins );
    ABC_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;
    unsigned Key;
    // get the new table size
    nBinsNew = Cudd_Prime(2 * p->nBins); 
    // allocate a new array
    pBinsNew = ABC_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
    ABC_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 = ABC_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" );
    }
    ABC_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 = ABC_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;
        }
    ABC_FREE( ppSupers );
}

////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


ABC_NAMESPACE_IMPL_END