abcNpn.c File Reference

#include "misc/extra/extra.h"
#include "misc/vec/vec.h"
#include "bool/kit/kit.h"
#include "bool/lucky/lucky.h"
#include "opt/dau/dau.h"

Include dependency graph for abcNpn.c:

Go to the source code of this file.

Classes
struct	Abc_TtStore_t_

Functions
Abc_TtStore_t *	Abc_TtStoreLoad (char *pFileName, int nVarNum)
void	Abc_TtStoreFree (Abc_TtStore_t *p, int nVarNum)
void	Abc_TtStoreWrite (char *pFileName, Abc_TtStore_t *p, int fBinary)
int	Abc_TruthNpnCountUnique (Abc_TtStore_t *p)
int	Abc_TruthCompare (word **p1, word **p2)
int	Abc_TruthNpnCountUniqueSort (Abc_TtStore_t *p)
void	Abc_TruthNpnPrint (char *pCanonPermInit, unsigned uCanonPhase, int nVars)
void	Abc_TruthNpnPerform (Abc_TtStore_t *p, int NpnType, int fVerbose)
void	Abc_TruthNpnTest (char *pFileName, int NpnType, int nVarNum, int fDumpRes, int fBinary, int fVerbose)
int	Abc_NpnTest (char *pFileName, int NpnType, int nVarNum, int fDumpRes, int fBinary, int fVerbose)

Variables
int	nWords = 0

Function Documentation

Abc_NpnTest()

int Abc_NpnTest	(	char *	pFileName,
		int	NpnType,
		int	nVarNum,
		int	fDumpRes,
		int	fBinary,
		int	fVerbose )

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

Synopsis [Testbench for decomposition algorithms.]

Description []

SideEffects []

SeeAlso []

Definition at line 431 of file abcNpn.c.

{
    if ( fVerbose )
        printf( "Using truth tables from file \"%s\"...\n", pFileName );
    if ( NpnType >= 0 && NpnType <= 12 )
        Abc_TruthNpnTest( pFileName, NpnType, nVarNum, fDumpRes, fBinary, fVerbose );
    else
        printf( "Unknown canonical form value (%d).\n", NpnType );
    fflush( stdout );
    return 0;
}

Here is the call graph for this function:

Abc_TruthCompare()

int Abc_TruthCompare	(	word **	p1,
		word **	p2 )

Definition at line 128 of file abcNpn.c.

{ return memcmp(*p1, *p2, sizeof(word) * nWords); }

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_TruthNpnCountUnique()

int Abc_TruthNpnCountUnique

(

Abc_TtStore_t *

p

)

Definition at line 90 of file abcNpn.c.

{
    // allocate hash table
    int nTableSize = Abc_PrimeCudd(p->nFuncs);
    int * pTable = ABC_FALLOC( int, nTableSize );
    int * pNexts = ABC_FALLOC( int, nTableSize );
    // hash functions
    int i, k, Key;
    for ( i = 0; i < p->nFuncs; i++ )
    {
        Key = Abc_TruthHashKey( p->pFuncs[i], p->nWords, nTableSize );
        if ( Abc_TruthHashLookup( p->pFuncs, i, p->nWords, pTable, pNexts, Key ) ) // found equal
            p->pFuncs[i] = NULL;
        else // there is no equal (the first time this one occurs so far)
            pNexts[i] = pTable[Key], pTable[Key] = i;
    }
    ABC_FREE( pTable );
    ABC_FREE( pNexts );
    // count the number of unqiue functions
    assert( p->pFuncs[0] != NULL );
    for ( i = k = 1; i < p->nFuncs; i++ )
        if ( p->pFuncs[i] != NULL )
            p->pFuncs[k++] = p->pFuncs[i];
    return (p->nFuncs = k);
}

Here is the caller graph for this function:

Abc_TruthNpnCountUniqueSort()

int Abc_TruthNpnCountUniqueSort

(

Abc_TtStore_t *

p

)

Definition at line 129 of file abcNpn.c.

{
    int i, k;
    // sort them by value
    nWords = p->nWords;
    assert( nWords > 0 );
    qsort( (void *)p->pFuncs, (size_t)p->nFuncs, sizeof(word *), (int(*)(const void *,const void *))Abc_TruthCompare );
    // count the number of unqiue functions
    for ( i = k = 1; i < p->nFuncs; i++ )
        if ( memcmp( p->pFuncs[i-1], p->pFuncs[i], sizeof(word) * nWords ) )
            p->pFuncs[k++] = p->pFuncs[i];
    return (p->nFuncs = k);
}

Here is the call graph for this function:

Abc_TruthNpnPerform()

void Abc_TruthNpnPerform	(	Abc_TtStore_t *	p,
		int	NpnType,
		int	fVerbose )

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

Synopsis [Apply decomposition to the truth table.]

Description [Returns the number of AIG nodes.]

SideEffects []

SeeAlso []

Definition at line 177 of file abcNpn.c.

{
    unsigned pAux[2048];
    word pAuxWord[1024], pAuxWord1[1024];
    char pCanonPerm[16];
    unsigned uCanonPhase=0;
    abctime clk = Abc_Clock();
    int i;
 
    char * pAlgoName = NULL;
    if ( NpnType == 0 )
        pAlgoName = "uniqifying          ";
    else if ( NpnType == 1 )
        pAlgoName = "exact NPN           ";
    else if ( NpnType == 2 )
        pAlgoName = "counting 1s         ";
    else if ( NpnType == 3 )
        pAlgoName = "Jake's hybrid fast  ";
    else if ( NpnType == 4 )
        pAlgoName = "Jake's hybrid good  ";
    else if ( NpnType == 5 )
        pAlgoName = "new hybrid fast     ";
    else if ( NpnType == 6 )
        pAlgoName = "new phase flipping  ";
    else if ( NpnType == 7 )
        pAlgoName = "new hier. matching  ";
    else if ( NpnType == 8 )
        pAlgoName = "new adap. matching  ";
    else if ( NpnType == 9 )
        pAlgoName = "adjustable algorithm (heuristic) ";
    else if ( NpnType == 10 )
        pAlgoName = "adjustable algorithm (exact)     ";
    else if ( NpnType == 11 )
        pAlgoName = "new cost-aware exact algorithm   ";
    else if ( NpnType == 12 )
        pAlgoName = "new hybrid fast (P) ";
 
    assert( p->nVars <= 16 );
    if ( pAlgoName )
        printf( "Applying %-20s to %8d func%s of %2d vars...  ",  
            pAlgoName, p->nFuncs, (p->nFuncs == 1 ? "":"s"), p->nVars );
    if ( fVerbose )
        printf( "\n" );
 
    if ( NpnType == 0 )
    {
        for ( i = 0; i < p->nFuncs; i++ )
        {
            if ( fVerbose )
                printf( "%7d : ", i );
            if ( fVerbose )
                Extra_PrintHex( stdout, (unsigned *)p->pFuncs[i], p->nVars ), printf( "\n" );
        }
    }
    else if ( NpnType == 1 )
    {
        permInfo* pi; 
        Abc_TruthNpnCountUnique(p);
        pi = setPermInfoPtr(p->nVars);
        for ( i = 0; i < p->nFuncs; i++ )
        {
            if ( fVerbose )
                printf( "%7d : ", i );
            simpleMinimal(p->pFuncs[i], pAuxWord, pAuxWord1, pi, p->nVars);
            if ( fVerbose )
                Extra_PrintHex( stdout, (unsigned *)p->pFuncs[i], p->nVars ), Abc_TruthNpnPrint(pCanonPerm, uCanonPhase, p->nVars), printf( "\n" );
        }
        freePermInfoPtr(pi);
    }
    else if ( NpnType == 2 )
    {
        for ( i = 0; i < p->nFuncs; i++ )
        {
            if ( fVerbose )
                printf( "%7d : ", i );
            resetPCanonPermArray(pCanonPerm, p->nVars);
            uCanonPhase = Kit_TruthSemiCanonicize( (unsigned *)p->pFuncs[i], pAux, p->nVars, pCanonPerm );
            if ( fVerbose )
                Extra_PrintHex( stdout, (unsigned *)p->pFuncs[i], p->nVars ), Abc_TruthNpnPrint(pCanonPerm, uCanonPhase, p->nVars), printf( "\n" );
        }
    }
    else if ( NpnType == 3 )
    {
        for ( i = 0; i < p->nFuncs; i++ )
        {
            if ( fVerbose )
                printf( "%7d : ", i );
            resetPCanonPermArray(pCanonPerm, p->nVars);
            uCanonPhase = luckyCanonicizer_final_fast( p->pFuncs[i], p->nVars, pCanonPerm );
            if ( fVerbose )
                Extra_PrintHex( stdout, (unsigned *)p->pFuncs[i], p->nVars ), Abc_TruthNpnPrint(pCanonPerm, uCanonPhase, p->nVars), printf( "\n" );
        }
    }
    else if ( NpnType == 4 )
    {
        for ( i = 0; i < p->nFuncs; i++ )
        {
            if ( fVerbose )
                printf( "%7d : ", i );
            resetPCanonPermArray(pCanonPerm, p->nVars);
            uCanonPhase = luckyCanonicizer_final_fast1( p->pFuncs[i], p->nVars, pCanonPerm );
            if ( fVerbose )
                Extra_PrintHex( stdout, (unsigned *)p->pFuncs[i], p->nVars ), Abc_TruthNpnPrint(pCanonPerm, uCanonPhase, p->nVars), printf( "\n" );
        }
    }
    else if ( NpnType == 5 )
    {
        for ( i = 0; i < p->nFuncs; i++ )
        {
            if ( fVerbose )
                printf( "%7d : ", i );
            uCanonPhase = Abc_TtCanonicize( p->pFuncs[i], p->nVars, pCanonPerm );
            if ( fVerbose )
                Extra_PrintHex( stdout, (unsigned *)p->pFuncs[i], p->nVars ), Abc_TruthNpnPrint(pCanonPerm, uCanonPhase, p->nVars), printf( "\n" );
        }
    }
    else if ( NpnType == 6 )
    {
        for ( i = 0; i < p->nFuncs; i++ )
        {
            if ( fVerbose )
                printf( "%7d : ", i );
            uCanonPhase = Abc_TtCanonicizePhase( p->pFuncs[i], p->nVars );
            if ( fVerbose )
                Extra_PrintHex( stdout, (unsigned *)p->pFuncs[i], p->nVars ), Abc_TruthNpnPrint(NULL, uCanonPhase, p->nVars), printf( "\n" );
        }
    }
    else if ( NpnType == 7 )
    {
        int fExact = 0;
        Abc_TtHieMan_t * pMan = Abc_TtHieManStart( p->nVars, 5 );
        for ( i = 0; i < p->nFuncs; i++ )
        {
            if ( fVerbose )
                printf( "%7d : ", i );
            uCanonPhase = Abc_TtCanonicizeHie( pMan, p->pFuncs[i], p->nVars, pCanonPerm, fExact );
            if ( fVerbose )
//                Extra_PrintHex( stdout, (unsigned *)p->pFuncs[i], p->nVars ), Abc_TruthNpnPrint(NULL, uCanonPhase, p->nVars), printf( "\n" );
                printf( "\n" );
        }
        // nClasses = Abc_TtManNumClasses( pMan );
        Abc_TtHieManStop( pMan );
    }
    else if ( NpnType == 8 )
    {
//        typedef unsigned(*TtCanonicizeFunc)(Abc_TtHieMan_t * p, word * pTruth, int nVars, char * pCanonPerm, int flag);
        unsigned Abc_TtCanonicizeWrap(TtCanonicizeFunc func, Abc_TtHieMan_t * p, word * pTruth, int nVars, char * pCanonPerm, int flag);
        unsigned Abc_TtCanonicizeAda(Abc_TtHieMan_t * p, word * pTruth, int nVars, char * pCanonPerm, int iThres);
        
        int fHigh = 1, iEnumThres = 25;
        Abc_TtHieMan_t * pMan = Abc_TtHieManStart(p->nVars, 5);
        for ( i = 0; i < p->nFuncs; i++ )
        {
            if ( fVerbose )
                printf( "%7d : ", i );
            uCanonPhase = Abc_TtCanonicizeWrap(Abc_TtCanonicizeAda, pMan, p->pFuncs[i], p->nVars, pCanonPerm, fHigh*100 + iEnumThres);
            if ( fVerbose )
                Extra_PrintHex( stdout, (unsigned *)p->pFuncs[i], p->nVars ), Abc_TruthNpnPrint(pCanonPerm, uCanonPhase, p->nVars), printf( "\n" );
        }
        Abc_TtHieManStop(pMan);
    }
    else if ( NpnType == 9 || NpnType == 10 || NpnType == 11 )
    {
//        typedef unsigned(*TtCanonicizeFunc)(Abc_TtHieMan_t * p, word * pTruth, int nVars, char * pCanonPerm, int flag);
        unsigned Abc_TtCanonicizeWrap(TtCanonicizeFunc func, Abc_TtHieMan_t * p, word * pTruth, int nVars, char * pCanonPerm, int flag);
        unsigned Abc_TtCanonicizeAda(Abc_TtHieMan_t * p, word * pTruth, int nVars, char * pCanonPerm, int iThres);
        unsigned Abc_TtCanonicizeCA(Abc_TtHieMan_t * p, word * pTruth, int nVars, char * pCanonPerm, int iThres);
        
        Abc_TtHieMan_t * pMan = Abc_TtHieManStart(p->nVars, 5);
        for ( i = 0; i < p->nFuncs; i++ )
        {
            if ( fVerbose )
                printf( "%7d : ", i );
            if ( NpnType == 9 )
                uCanonPhase = Abc_TtCanonicizeWrap(Abc_TtCanonicizeAda, pMan, p->pFuncs[i], p->nVars, pCanonPerm,  125); // -A 8, adjustable algorithm (heuristic)
            else if ( NpnType == 10 )
                uCanonPhase = Abc_TtCanonicizeWrap(Abc_TtCanonicizeAda, pMan, p->pFuncs[i], p->nVars, pCanonPerm, 1199); // -A 9, adjustable algorithm (exact)
            else if ( NpnType == 11 )
                uCanonPhase = Abc_TtCanonicizeWrap(Abc_TtCanonicizeCA,  pMan, p->pFuncs[i], p->nVars, pCanonPerm,    1); // -A 10, new cost-aware exact algorithm
            if ( fVerbose )
                Extra_PrintHex( stdout, (unsigned *)p->pFuncs[i], p->nVars ), Abc_TruthNpnPrint(pCanonPerm, uCanonPhase, p->nVars), printf( "\n" );
        }
        Abc_TtHieManStop(pMan);
    }
    else if ( NpnType == 12 )
    {
        for ( i = 0; i < p->nFuncs; i++ )
        {
            if ( fVerbose )
                printf( "%7d : ", i );
            uCanonPhase = Abc_TtCanonicizePerm( p->pFuncs[i], p->nVars, pCanonPerm );
            if ( fVerbose )
                Extra_PrintHex( stdout, (unsigned *)p->pFuncs[i], p->nVars ), Abc_TruthNpnPrint(pCanonPerm, uCanonPhase, p->nVars), printf( "\n" );
        }
    }
    else assert( 0 );
    clk = Abc_Clock() - clk;
    printf( "Classes =%9d  ", Abc_TruthNpnCountUnique(p) );
    Abc_PrintTime( 1, "Time", clk );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_TruthNpnPrint()

void Abc_TruthNpnPrint	(	char *	pCanonPermInit,
		unsigned	uCanonPhase,
		int	nVars )

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

Synopsis [Prints out one NPN transform.]

Description []

SideEffects []

SeeAlso []

Definition at line 154 of file abcNpn.c.

{
    char pCanonPerm[16]; int i;
    assert( nVars <= 16 );
    for ( i = 0; i < nVars; i++ )
        pCanonPerm[i] = pCanonPermInit ? pCanonPermInit[i] : 'a' + i;
    printf( "   %c = ( ", Abc_InfoHasBit(&uCanonPhase, nVars) ? 'Z':'z' );
    for ( i = 0; i < nVars; i++ )
        printf( "%c%s", pCanonPerm[i] + ('A'-'a') * Abc_InfoHasBit(&uCanonPhase, pCanonPerm[i]-'a'), i == nVars-1 ? "":"," );
    printf( " )  " );
}

Here is the caller graph for this function:

Abc_TruthNpnTest()

void Abc_TruthNpnTest	(	char *	pFileName,
		int	NpnType,
		int	nVarNum,
		int	fDumpRes,
		int	fBinary,
		int	fVerbose )

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

Synopsis [Apply decomposition to truth tables.]

Description []

SideEffects []

SeeAlso []

Definition at line 389 of file abcNpn.c.

{
    Abc_TtStore_t * p;
    char * pFileNameOut;
 
    // read info from file
    p = Abc_TtStoreLoad( pFileName, nVarNum );
    if ( p == NULL )
        return;
 
    // consider functions from the file
    Abc_TruthNpnPerform( p, NpnType, fVerbose );
 
    // write the result
    if ( fDumpRes )
    {
        if ( fBinary )
            pFileNameOut = Extra_FileNameGenericAppend( pFileName, "_out.tt" );
        else
            pFileNameOut = Extra_FileNameGenericAppend( pFileName, "_out.txt" );
        Abc_TtStoreWrite( pFileNameOut, p, fBinary );
        if ( fVerbose )
            printf( "The resulting functions are written into file \"%s\".\n", pFileNameOut );
    }
 
    // delete data-structure
    Abc_TtStoreFree( p, nVarNum );
//    printf( "Finished computing canonical forms for functions from file \"%s\".\n", pFileName );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_TtStoreFree()

void Abc_TtStoreFree ( Abc_TtStore_t * p, int nVarNum )

extern

Definition at line 176 of file abcDec.c.

{
    if ( nVarNum >= 0 )
        ABC_FREE( p->pFuncs[0] );
    ABC_FREE( p->pFuncs );
    ABC_FREE( p );
}

Here is the caller graph for this function:

Abc_TtStoreLoad()

Abc_TtStore_t * Abc_TtStoreLoad ( char * pFileName, int nVarNum )

extern

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

Synopsis [Read truth tables from input file and write them into output file.]

Description []

SideEffects []

SeeAlso []

Definition at line 396 of file abcDec.c.

{ 
    Abc_TtStore_t * p;
    if ( nVarNum < 0 )
    {
        int nVars, nTruths;
        // figure out how many truth table and how many variables
        Abc_TruthGetParams( pFileName, &nVars, &nTruths );
        if ( nVars < 2 || nVars > 16 || nTruths == 0 )
            return NULL;
        // allocate data-structure
        p = Abc_TruthStoreAlloc( nVars, nTruths );
        // read info from file
        Abc_TruthStoreRead( pFileName, p );
    }
    else
    { 
        char * pBuffer;
        int nFileSize = Abc_FileSize( pFileName );
        int nBytes = (1 << (nVarNum-3));
        int nTruths = nFileSize / nBytes;
        if ( nFileSize == -1 )
            return NULL;
        assert( nVarNum >= 6 );
        if ( nFileSize % nBytes != 0 ) 
            Abc_Print( 0, "The file size (%d) is divided by the truth table size (%d) with remainder (%d).\n", 
                nFileSize, nBytes, nFileSize % nBytes );
        // read file contents
        pBuffer = Abc_FileRead( pFileName );
        // allocate data-structure
        p = Abc_TruthStoreAlloc2( nVarNum, nTruths, (word *)pBuffer );
    }
    return p;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Abc_TtStoreWrite()

void Abc_TtStoreWrite ( char * pFileName, Abc_TtStore_t * p, int fBinary )

extern

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

Synopsis [Write truth tables into file.]

Description []

SideEffects []

SeeAlso []

Definition at line 359 of file abcDec.c.

{
    FILE * pFile;
    char pBuffer[1000];
    int i, nBytes = 8 * Abc_Truth6WordNum( p->nVars );
    pFile = fopen( pFileName, "wb" );
    if ( pFile == NULL )
    {
        printf( "Cannot open file \"%s\" for writing.\n", pFileName );
        return;
    }
    for ( i = 0; i < p->nFuncs; i++ )
    {
        if ( fBinary )
            fwrite( p->pFuncs[i], nBytes, 1, pFile );
        else
        {
            Abc_TruthWriteHex( pFile, p->pFuncs[i], p->nVars ), fprintf( pFile, "    " );
            Dau_DsdDecompose( p->pFuncs[i], p->nVars, 0, (int)(p->nVars <= 10), pBuffer );
            fprintf( pFile, "%s\n", pBuffer );
        }
    }
    fclose( pFile );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Variable Documentation

nWords

int nWords = 0

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

Synopsis [Counts the number of unique truth tables.]

Description []

SideEffects []

SeeAlso []

Definition at line 127 of file abcNpn.c.