superAnd.c

Go to the documentation of this file.

/**CFile****************************************************************

  FileName    [superAnd.c]

  PackageName [MVSIS 1.3: Multi-valued logic synthesis system.]

  Synopsis    [Pre-computation of supergates.]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - September 8, 2003.]

  Revision    [$Id: superAnd.c,v 1.3 2004/06/28 14:20:25 alanmi Exp $]

***********************************************************************/

#include "superInt.h"

ABC_NAMESPACE_IMPL_START


////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

// the bit masks
#define SUPER_MASK(n)     ((~((unsigned)0)) >> (32-n))
#define SUPER_FULL         (~((unsigned)0))

// data structure for AND2 subgraph precomputation
typedef struct Super2_ManStruct_t_     Super2_Man_t;   // manager
typedef struct Super2_LibStruct_t_     Super2_Lib_t;   // library
typedef struct Super2_GateStruct_t_    Super2_Gate_t;  // supergate

struct Super2_ManStruct_t_
{
    Extra_MmFixed_t *   pMem;         // memory manager for all supergates
    stmm_table *        tTable;       // mapping of truth tables into gates
    int                 nTried;       // the total number of tried
};

struct Super2_LibStruct_t_
{
    int                 i;            // used to iterate through the table
    int                 k;            // used to iterate through the table
    int                 nInputs;      // the number of inputs
    int                 nMints;       // the number of minterms
    int                 nLevels;      // the number of logic levels
    int                 nGates;       // the number of gates in the library
    int                 nGatesAlloc;  // the number of allocated places
    Super2_Gate_t **    pGates;       // the gates themselves
    unsigned            uMaskBit;     // the mask used to determine the compl bit
};

struct Super2_GateStruct_t_
{
    unsigned            uTruth;       // the truth table of this supergate
    Super2_Gate_t *     pOne;         // the left wing
    Super2_Gate_t *     pTwo;         // the right wing
    Super2_Gate_t *     pNext;        // the next gate in the table
};


// manipulation of complemented attributes
#define Super2_IsComplement(p)    (((int)((ABC_PTRUINT_T) (p) & 01)))
#define Super2_Regular(p)         ((Super2_Gate_t *)((ABC_PTRUINT_T)(p) & ~01)) 
#define Super2_Not(p)             ((Super2_Gate_t *)((ABC_PTRUINT_T)(p) ^ 01)) 
#define Super2_NotCond(p,c)       ((Super2_Gate_t *)((ABC_PTRUINT_T)(p) ^ (c)))

// iterating through the gates in the library
#define Super2_LibForEachGate( Lib, Gate )                        \
    for ( Lib->i = 0;                                             \
          Lib->i < Lib->nGates && (Gate = Lib->pGates[Lib->i]);   \
          Lib->i++ )
#define Super2_LibForEachGate2( Lib, Gate2 )                      \
    for ( Lib->k = 0;                                             \
          Lib->k < Lib->i && (Gate2 = Lib->pGates[Lib->k]);       \
          Lib->k++ )

// static functions
static Super2_Man_t * Super2_ManStart();
static void           Super2_ManStop( Super2_Man_t * pMan );
static Super2_Lib_t * Super2_LibStart();
static Super2_Lib_t * Super2_LibDup( Super2_Lib_t * pLib );
static void           Super2_LibStop( Super2_Lib_t * pLib );
static void           Super2_LibAddGate( Super2_Lib_t * pLib, Super2_Gate_t * pGate );
static Super2_Lib_t * Super2_LibFirst( Super2_Man_t * pMan, int nInputs );
static Super2_Lib_t * Super2_LibCompute( Super2_Man_t * pMan, Super2_Lib_t * pLib );

static void           Super2_LibWrite( Super2_Lib_t * pLib );
static void           Super2_LibWriteGate( FILE * pFile, Super2_Lib_t * pLib, Super2_Gate_t * pGate );
static char *         Super2_LibWriteGate_rec( Super2_Gate_t * pGate, int fInv, int Level );
static int            Super2_LibWriteCompare( char * pStr1, char * pStr2 );
static int            Super2_LibCompareGates( Super2_Gate_t ** ppG1, Super2_Gate_t ** ppG2 );

////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

/**Function*************************************************************

  Synopsis    [Precomputes the library of AND2 gates.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Super2_Precompute( int nInputs, int nLevels, int fVerbose )
{
    Super2_Man_t * pMan;
    Super2_Lib_t * pLibCur, * pLibNext;
    int Level;
    abctime clk;

    assert( nInputs < 6 );

    // start the manager
    pMan = Super2_ManStart();

    // get the starting supergates
    pLibCur = Super2_LibFirst( pMan, nInputs );

    // perform the computation of supergates
printf( "Computing supergates for %d inputs and %d levels:\n", nInputs, nLevels );
    for ( Level = 1; Level <= nLevels; Level++ )
    {
clk = Abc_Clock();
        pLibNext = Super2_LibCompute( pMan, pLibCur );
        pLibNext->nLevels = Level;
        Super2_LibStop( pLibCur );
        pLibCur = pLibNext;
printf( "Level %d:  Tried = %7d.  Computed = %7d.  ", Level, pMan->nTried, pLibCur->nGates );
ABC_PRT( "Runtime", Abc_Clock() - clk );
fflush( stdout );
    }

printf( "Writing the output file...\n" );
fflush( stdout );
    // write them into a file
    Super2_LibWrite( pLibCur );
    Super2_LibStop( pLibCur );

    // stop the manager
    Super2_ManStop( pMan );
}




/**Function*************************************************************

  Synopsis    [Starts the manager.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Super2_Man_t * Super2_ManStart()
{
    Super2_Man_t * pMan;
    pMan = ABC_ALLOC( Super2_Man_t, 1 );
    memset( pMan, 0, sizeof(Super2_Man_t) );
    pMan->pMem   = Extra_MmFixedStart( sizeof(Super2_Gate_t) );
    pMan->tTable = stmm_init_table( st__ptrcmp, st__ptrhash );
    return pMan;
}

/**Function*************************************************************

  Synopsis    [Stops the manager.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Super2_ManStop( Super2_Man_t * pMan )
{
    Extra_MmFixedStop( pMan->pMem );
    stmm_free_table( pMan->tTable );
    ABC_FREE( pMan );
}

/**Function*************************************************************

  Synopsis    [Starts the library.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Super2_Lib_t * Super2_LibStart()
{
    Super2_Lib_t * pLib;
    pLib = ABC_ALLOC( Super2_Lib_t, 1 );
    memset( pLib, 0, sizeof(Super2_Lib_t) );
    return pLib;
}

/**Function*************************************************************

  Synopsis    [Duplicates the library.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Super2_Lib_t * Super2_LibDup( Super2_Lib_t * pLib )
{
    Super2_Lib_t * pLibNew;
    pLibNew = Super2_LibStart();
    pLibNew->nInputs     = pLib->nInputs;
    pLibNew->nMints      = pLib->nMints;
    pLibNew->nLevels     = pLib->nLevels;
    pLibNew->nGates      = pLib->nGates;
    pLibNew->uMaskBit    = pLib->uMaskBit;
    pLibNew->nGatesAlloc = 1000 + pLib->nGatesAlloc;
    pLibNew->pGates      = ABC_ALLOC( Super2_Gate_t *, pLibNew->nGatesAlloc );
    memcpy( pLibNew->pGates, pLib->pGates, pLibNew->nGates * sizeof(Super2_Gate_t *) );
    return pLibNew;
}

/**Function*************************************************************

  Synopsis    [Add gate to the library.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Super2_LibAddGate( Super2_Lib_t * pLib, Super2_Gate_t * pGate )
{
    if ( pLib->nGates == pLib->nGatesAlloc )
    {
        pLib->pGates  = ABC_REALLOC( Super2_Gate_t *, pLib->pGates,  3 * pLib->nGatesAlloc );
        pLib->nGatesAlloc *= 3;
    }
    pLib->pGates[ pLib->nGates++ ] = pGate;
}

/**Function*************************************************************

  Synopsis    [Stops the library.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Super2_LibStop( Super2_Lib_t * pLib )
{
    ABC_FREE( pLib->pGates );
    ABC_FREE( pLib );
}

/**Function*************************************************************

  Synopsis    [Derives the starting supergates.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Super2_Lib_t * Super2_LibFirst( Super2_Man_t * pMan, int nInputs )
{
    Super2_Lib_t * pLib;
    int v, m;    

    // start the library
    pLib = Super2_LibStart();

    // create the starting supergates
    pLib->nInputs     = nInputs;
    pLib->nMints      = (1 << nInputs);
    pLib->nLevels     = 0;
    pLib->nGates      = nInputs + 1;
    pLib->nGatesAlloc = nInputs + 1;
    pLib->uMaskBit    = (1 << (pLib->nMints-1));
    pLib->pGates      = ABC_ALLOC( Super2_Gate_t *, nInputs + 1 );
    // add the constant 0
    pLib->pGates[0] = (Super2_Gate_t *)Extra_MmFixedEntryFetch( pMan->pMem );
    memset( pLib->pGates[0], 0, sizeof(Super2_Gate_t) );
    // add the elementary gates
    for ( v = 0; v < nInputs; v++ )
    {
        pLib->pGates[v+1] = (Super2_Gate_t *)Extra_MmFixedEntryFetch( pMan->pMem );
        memset( pLib->pGates[v+1], 0, sizeof(Super2_Gate_t) );
        pLib->pGates[v+1]->pTwo = (Super2_Gate_t *)(ABC_PTRUINT_T)v;
    }

    // set up their truth tables
    for ( m = 0; m < pLib->nMints; m++ )
        for ( v = 0; v < nInputs; v++ )
            if ( m & (1 << v) )
                pLib->pGates[v+1]->uTruth |= (1 << m);
    return pLib;
}

/**Function*************************************************************

  Synopsis    [Precomputes one level of supergates.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Super2_Lib_t * Super2_LibCompute( Super2_Man_t * pMan, Super2_Lib_t * pLib )
{
    Super2_Lib_t * pLibNew;
    Super2_Gate_t * pGate1, * pGate2, * pGateNew;
    Super2_Gate_t ** ppGate;
    unsigned Mask = SUPER_MASK(pLib->nMints);
    unsigned uTruth, uTruthR, uTruth1, uTruth2, uTruth1c, uTruth2c;

    // start the new library
    pLibNew = Super2_LibDup( pLib );

    // reset the hash table
    stmm_free_table( pMan->tTable );
    pMan->tTable = stmm_init_table( st__ptrcmp, st__ptrhash );
    // set the starting things into the hash table
    Super2_LibForEachGate( pLibNew, pGate1 )
    {
        uTruthR = ((pGate1->uTruth & pLibNew->uMaskBit)? Mask & ~pGate1->uTruth : pGate1->uTruth);

        if ( stmm_lookup( pMan->tTable, (char *)(ABC_PTRUINT_T)uTruthR, (char **)&pGate2 ) )
        {
            printf( "New gate:\n" );
            Super2_LibWriteGate( stdout, pLibNew, pGate1 );
            printf( "Gate in the table:\n" );
            Super2_LibWriteGate( stdout, pLibNew, pGate2 );
            assert( 0 );
        }
        stmm_insert( pMan->tTable, (char *)(ABC_PTRUINT_T)uTruthR, (char *)(ABC_PTRUINT_T)pGate1 );
    }


    // set the number of gates tried
    pMan->nTried = pLibNew->nGates;

    // go through the gate pairs
    Super2_LibForEachGate( pLib, pGate1 )
    {
        if ( pLib->i && pLib->i % 300 == 0 )
        {
            printf( "Tried %5d first gates...\n", pLib->i );
            fflush( stdout );
        }

        Super2_LibForEachGate2( pLib, pGate2 )
        {
            uTruth1  = pGate1->uTruth;
            uTruth2  = pGate2->uTruth;
            uTruth1c = Mask & ~uTruth1;
            uTruth2c = Mask & ~uTruth2;

            // none complemented
            uTruth  = uTruth1  & uTruth2;
            uTruthR = ((uTruth & pLibNew->uMaskBit)? Mask & ~uTruth : uTruth);

            if ( !stmm_find_or_add( pMan->tTable, (char *)(ABC_PTRUINT_T)uTruthR, (char ***)&ppGate ) )
            {
                pGateNew = (Super2_Gate_t *)Extra_MmFixedEntryFetch( pMan->pMem );
                pGateNew->pOne  = pGate1;
                pGateNew->pTwo  = pGate2;
                pGateNew->uTruth = uTruth;
                *ppGate = pGateNew;
                Super2_LibAddGate( pLibNew, pGateNew );
            }                

            // one complemented
            uTruth  = uTruth1c & uTruth2;
            uTruthR = ((uTruth & pLibNew->uMaskBit)? Mask & ~uTruth : uTruth);

            if ( !stmm_find_or_add( pMan->tTable, (char *)(ABC_PTRUINT_T)uTruthR, (char ***)&ppGate ) )
            {
                pGateNew = (Super2_Gate_t *)Extra_MmFixedEntryFetch( pMan->pMem );
                pGateNew->pOne  = Super2_Not(pGate1);
                pGateNew->pTwo  = pGate2;
                pGateNew->uTruth = uTruth;
                *ppGate = pGateNew;
                Super2_LibAddGate( pLibNew, pGateNew );
            }                

            // another complemented
            uTruth  = uTruth1  & uTruth2c;
            uTruthR = ((uTruth & pLibNew->uMaskBit)? Mask & ~uTruth : uTruth);

            if ( !stmm_find_or_add( pMan->tTable, (char *)(ABC_PTRUINT_T)uTruthR, (char ***)&ppGate ) )
            {
                pGateNew = (Super2_Gate_t *)Extra_MmFixedEntryFetch( pMan->pMem );
                pGateNew->pOne  = pGate1;
                pGateNew->pTwo  = Super2_Not(pGate2);
                pGateNew->uTruth = uTruth;
                *ppGate = pGateNew;
                Super2_LibAddGate( pLibNew, pGateNew );
            }                

            // both complemented
            uTruth  = uTruth1c & uTruth2c;
            uTruthR = ((uTruth & pLibNew->uMaskBit)? Mask & ~uTruth : uTruth);

            if ( !stmm_find_or_add( pMan->tTable, (char *)(ABC_PTRUINT_T)uTruthR, (char ***)&ppGate ) )
            {
                pGateNew = (Super2_Gate_t *)Extra_MmFixedEntryFetch( pMan->pMem );
                pGateNew->pOne  = Super2_Not(pGate1);
                pGateNew->pTwo  = Super2_Not(pGate2);
                pGateNew->uTruth = uTruth;
                *ppGate = pGateNew;
                Super2_LibAddGate( pLibNew, pGateNew );
            }                

            pMan->nTried += 4;
        }
    }
    return pLibNew;
}


static unsigned s_uMaskBit;
static unsigned s_uMaskAll;

/**Function*************************************************************

  Synopsis    [Writes the library into the file.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Super2_LibWrite( Super2_Lib_t * pLib )
{
    Super2_Gate_t * pGate;
    FILE * pFile;
    char FileName[100];
    abctime clk;

    if ( pLib->nLevels > 5 )
    {
        printf( "Cannot write file for %d levels.\n", pLib->nLevels );
        return;
    }

clk = Abc_Clock();
    // sort the supergates by truth table
    s_uMaskBit = pLib->uMaskBit;
    s_uMaskAll = SUPER_MASK(pLib->nMints);
    qsort( (void *)pLib->pGates, pLib->nGates, sizeof(Super2_Gate_t *), 
            (int (*)(const void *, const void *)) Super2_LibCompareGates );
    assert( Super2_LibCompareGates( pLib->pGates, pLib->pGates + pLib->nGates - 1 ) < 0 );
ABC_PRT( "Sorting", Abc_Clock() - clk );


    // start the file
    sprintf( FileName, "superI%dL%d", pLib->nInputs, pLib->nLevels );
    pFile = fopen( FileName, "w" );
    fprintf( pFile, "# AND2/INV supergates derived on %s.\n", Extra_TimeStamp() );
    fprintf( pFile, "# Command line: \"super2 -i %d -l %d\".\n", pLib->nInputs, pLib->nLevels );
    fprintf( pFile, "# The number of inputs     = %6d.\n", pLib->nInputs );
    fprintf( pFile, "# The number of levels     = %6d.\n", pLib->nLevels );
    fprintf( pFile, "# The number of supergates = %6d.\n", pLib->nGates  );
    fprintf( pFile, "# The total functions      = %6d.\n", (1<<(pLib->nMints-1)) );
    fprintf( pFile, "\n" );
    fprintf( pFile, "%6d\n", pLib->nGates );

    // print the gates
    Super2_LibForEachGate( pLib, pGate )
        Super2_LibWriteGate( pFile, pLib, pGate );
    fclose( pFile );

    printf( "The supergates are written into file \"%s\" ", FileName );
    printf( "(%0.2f MB).\n", ((double)Extra_FileSize(FileName))/(1<<20) );
}

/**Function*************************************************************

  Synopsis    [Writes the gate into the file.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Super2_LibCompareGates( Super2_Gate_t ** ppG1, Super2_Gate_t ** ppG2 )
{
    Super2_Gate_t * pG1  = *ppG1;
    Super2_Gate_t * pG2  = *ppG2;
    unsigned uTruth1, uTruth2;

    uTruth1 = (pG1->uTruth & s_uMaskBit)? s_uMaskAll & ~pG1->uTruth : pG1->uTruth;
    uTruth2 = (pG2->uTruth & s_uMaskBit)? s_uMaskAll & ~pG2->uTruth : pG2->uTruth;

    if ( uTruth1 < uTruth2 )
        return -1;
    return 1;
}

/**Function*************************************************************

  Synopsis    [Writes the gate into the file.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Super2_LibWriteGate( FILE * pFile, Super2_Lib_t * pLib, Super2_Gate_t * pGate )
{
//    unsigned uTruthR;
    unsigned uTruth;
    int fInv;

    // check whether the gate need complementation
    fInv = (int)(pGate->uTruth & pLib->uMaskBit);
    uTruth = (fInv? ~pGate->uTruth : pGate->uTruth);
/*
    // reverse the truth table
    uTruthR = 0;
    for ( m = 0; m < pLib->nMints; m++ )
        if ( uTruth & (1 << m) )
            uTruthR |= (1 << (pLib->nMints-1-m));
*/
    // write the truth table
    Extra_PrintBinary( pFile, &uTruth, pLib->nMints );
    fprintf( pFile, "   " );
    // write the symbolic expression
    fprintf( pFile, "%s", Super2_LibWriteGate_rec( pGate, fInv, pLib->nLevels ) );
    fprintf( pFile, "\n" );
}


/**Function*************************************************************

  Synopsis    [Recursively writes the gate into the file.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
char * Super2_LibWriteGate_rec( Super2_Gate_t * pGate, int fInv, int Level )
{
    static char Buff01[  3], Buff02[  3];    // Max0              =  1
    static char Buff11[  6], Buff12[  6];    // Max1 = 2*Max0 + 2 =  4
    static char Buff21[ 12], Buff22[ 12];    // Max2 = 2*Max1 + 2 = 10
    static char Buff31[ 25], Buff32[ 25];    // Max3 = 2*Max2 + 2 = 22
    static char Buff41[ 50], Buff42[ 50];    // Max4 = 2*Max3 + 2 = 46
    static char Buff51[100], Buff52[100];    // Max5 = 2*Max4 + 2 = 94
    static char * pBuffs1[6] = { Buff01, Buff11, Buff21, Buff31, Buff41, Buff51 };
    static char * pBuffs2[6] = { Buff02, Buff12, Buff22, Buff32, Buff42, Buff52 };
    char * pBranch;
    char * pBuffer1 = pBuffs1[Level];
    char * pBuffer2 = pBuffs2[Level];
    Super2_Gate_t * pGateNext1, * pGateNext2;
    int fInvNext1, fInvNext2;
    int RetValue;

    // consider the last level
    assert( Level >= 0 );
    if ( pGate->pOne == NULL )
    {
        if ( pGate->uTruth == 0 )
        {
            pBuffer1[0] = (fInv? '1': '0');
            pBuffer1[1] = '$';
            pBuffer1[2] = 0;
        }
        else
        {
            pBuffer1[0] = (fInv? 'A' + ((int)(ABC_PTRUINT_T)pGate->pTwo): 'a' + ((int)(ABC_PTRUINT_T)pGate->pTwo));
            pBuffer1[1] = 0;
        }
        return pBuffer1;
    }
    assert( Level > 0 );


    // get the left branch
    pGateNext1 = Super2_Regular(pGate->pOne);
    fInvNext1  = Super2_IsComplement(pGate->pOne);
    pBranch    = Super2_LibWriteGate_rec(pGateNext1, fInvNext1, Level - 1);
    // copy into Buffer1
    strcpy( pBuffer1, pBranch );

    // get the right branch
    pGateNext2 = Super2_Regular(pGate->pTwo);
    fInvNext2  = Super2_IsComplement(pGate->pTwo);
    pBranch    = Super2_LibWriteGate_rec(pGateNext2, fInvNext2, Level - 1);

    // consider the case when comparison is not necessary
    if ( fInvNext1 ^ fInvNext2 )
    {
        if ( fInvNext1 > fInvNext2 )
            sprintf( pBuffer2, "%c%s%s%c", (fInv? '<': '('), pBuffer1, pBranch, (fInv? '>': ')') );
        else
            sprintf( pBuffer2, "%c%s%s%c", (fInv? '<': '('), pBranch, pBuffer1, (fInv? '>': ')') );
    }
    else
    {
        // compare the two branches
        RetValue = Super2_LibWriteCompare( pBuffer1, pBranch );
        if ( RetValue == 1 )
            sprintf( pBuffer2, "%c%s%s%c", (fInv? '<': '('), pBuffer1, pBranch, (fInv? '>': ')') );
        else // if ( RetValue == -1 )
        {
            sprintf( pBuffer2, "%c%s%s%c", (fInv? '<': '('), pBranch, pBuffer1, (fInv? '>': ')') );
            if ( RetValue == 0 )
                printf( "Strange!\n" );
        }
    }
    return pBuffer2;
}

/**Function*************************************************************

  Synopsis    [Compares the two branches of the tree.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Super2_LibWriteCompare( char * pStr1, char * pStr2 )
{
    while ( 1 )
    {
        // skip extra symbols
        while ( *pStr1 && *pStr1 < 'A' )
            pStr1++;
        while ( *pStr2 && *pStr2 < 'A' )
            pStr2++;

        // check if any one is finished
        if ( *pStr1 == 0 || *pStr2 == 0 )
        {
            if ( *pStr2 )
                return 1;
            return -1;
        }

        // compare
        if ( *pStr1 == *pStr2 )
        {
            pStr1++;
            pStr2++;
        }
        else
        {
            if ( *pStr1 < *pStr2 )
                return 1;
            return -1;
        }
    }
    return 0;
}

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


ABC_NAMESPACE_IMPL_END