abcDec.c File Reference

#include "misc/extra/extra.h"
#include "misc/vec/vec.h"
#include "bool/bdc/bdc.h"
#include "bool/dec/dec.h"
#include "bool/kit/kit.h"
#include "opt/dau/dau.h"
#include "misc/util/utilTruth.h"

Go to the source code of this file.

Data Structures
struct	Abc_TtStore_t_

Typedefs
typedef typedefABC_NAMESPACE_IMPL_START struct Abc_TtStore_t_	Abc_TtStore_t
	DECLARATIONS ///. More...

Functions
static int	Abc_TruthGetBit (word *p, int i)
static void	Abc_TruthSetBit (word *p, int i)
static void	Abc_TruthXorBit (word *p, int i)
static int	Abc_TruthGetHex (word *p, int k)
static void	Abc_TruthSetHex (word *p, int k, int d)
static void	Abc_TruthXorHex (word *p, int k, int d)
static int	Abc_TruthReadHexDigit (char HexChar)
	FUNCTION DEFINITIONS ///. More...
static void	Abc_TruthWriteHexDigit (FILE *pFile, int HexDigit)
void	Abc_TruthReadHex (word *pTruth, char *pString, int nVars)
void	Abc_TruthWriteHex (FILE *pFile, word *pTruth, int nVars)
Abc_TtStore_t *	Abc_TruthStoreAlloc (int nVars, int nFuncs)
Abc_TtStore_t *	Abc_TruthStoreAlloc2 (int nVars, int nFuncs, word *pBuffer)
void	Abc_TtStoreFree (Abc_TtStore_t *p, int nVarNum)
int	Abc_FileSize (char *pFileName)
char *	Abc_FileRead (char *pFileName)
void	Abc_TruthGetParams (char *pFileName, int *pnVars, int *pnTruths)
void	Abc_TruthStoreRead (char *pFileName, Abc_TtStore_t *p)
void	Abc_TtStoreWrite (char *pFileName, Abc_TtStore_t *p, int fBinary)
Abc_TtStore_t *	Abc_TtStoreLoad (char *pFileName, int nVarNum)
void	Abc_TtStoreTest (char *pFileName)
void	Abc_TruthDecPerform (Abc_TtStore_t *p, int DecType, int fVerbose)
void	Abc_TruthDecTest (char *pFileName, int DecType, int nVarNum, int fVerbose)
int	Abc_DecTest (char *pFileName, int DecType, int nVarNum, int fVerbose)

Typedef Documentation

typedef typedefABC_NAMESPACE_IMPL_START struct Abc_TtStore_t_ Abc_TtStore_t

DECLARATIONS ///.

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

FileName [abcDec.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Network and node package.]

Synopsis [Procedures for testing and comparing decomposition algorithms.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - June 20, 2005.]

Revision [

Id:

abcDec.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

]

Definition at line 44 of file abcDec.c.

Function Documentation

int Abc_DecTest	(	char *	pFileName,
		int	DecType,
		int	nVarNum,
		int	fVerbose
	)

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

Synopsis [Testbench for decomposition algorithms.]

Description []

SideEffects []

SeeAlso []

Definition at line 626 of file abcDec.c.

{
    if ( fVerbose )
        printf( "Using truth tables from file \"%s\"...\n", pFileName );
    if ( DecType == 0 )
        { if ( nVarNum < 0 ) Abc_TtStoreTest( pFileName ); }
    else if ( DecType >= 1 && DecType <= 5 )
        Abc_TruthDecTest( pFileName, DecType, nVarNum, fVerbose );
    else
        printf( "Unknown decomposition type value (%d).\n", DecType );
    fflush( stdout );
    return 0;
}

char* Abc_FileRead

(

char *

pFileName

)

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

Synopsis [Read file contents.]

Description []

SideEffects []

SeeAlso []

Definition at line 222 of file abcDec.c.

{
    FILE * pFile;
    char * pBuffer;
    int nFileSize, RetValue;
    pFile = fopen( pFileName, "rb" );
    if ( pFile == NULL )
    {
        printf( "Cannot open file \"%s\" for reading.\n", pFileName );
        return NULL;
    }
    // get the file size, in bytes
    fseek( pFile, 0, SEEK_END );  
    nFileSize = ftell( pFile );  
    // move the file current reading position to the beginning
    rewind( pFile ); 
    // load the contents of the file into memory
    pBuffer = (char *)malloc( nFileSize + 3 );
    RetValue = fread( pBuffer, nFileSize, 1, pFile );
    // add several empty lines at the end
    // (these will be used to signal the end of parsing)
    pBuffer[ nFileSize + 0] = '\n';
    pBuffer[ nFileSize + 1] = '\n';
    // terminate the string with '\0'
    pBuffer[ nFileSize + 2] = '\0';
    fclose( pFile );
    return pBuffer;
}

int Abc_FileSize

(

char *

pFileName

)

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

Synopsis [Read file contents.]

Description []

SideEffects []

SeeAlso []

Definition at line 194 of file abcDec.c.

{
    FILE * pFile;
    int nFileSize;
    pFile = fopen( pFileName, "rb" );
    if ( pFile == NULL )
    {
        printf( "Cannot open file \"%s\" for reading.\n", pFileName );
        return -1;
    }
    // get the file size, in bytes
    fseek( pFile, 0, SEEK_END );  
    nFileSize = ftell( pFile );  
    fclose( pFile );
    return nFileSize;
}

void Abc_TruthDecPerform	(	Abc_TtStore_t *	p,
		int	DecType,
		int	fVerbose
	)

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

Synopsis [Apply decomposition to the truth table.]

Description [Returns the number of AIG nodes.]

SideEffects []

SeeAlso []

Definition at line 471 of file abcDec.c.

{
    abctime clk = Abc_Clock();
    int i, nNodes = 0;

    char * pAlgoName = NULL;
    if ( DecType == 1 )
        pAlgoName = "factoring";
    else if ( DecType == 2 )
        pAlgoName = "bi-decomp";
    else if ( DecType == 3 )
        pAlgoName = "DSD";
    else if ( DecType == 4 )
        pAlgoName = "fast DSD";
    else if ( DecType == 5 )
        pAlgoName = "analysis";

    if ( pAlgoName )
        printf( "Applying %-10s to %8d func%s of %2d vars...  ",  
            pAlgoName, p->nFuncs, (p->nFuncs == 1 ? "":"s"), p->nVars );
    if ( fVerbose )
        printf( "\n" );

    if ( DecType == 1 )
    {
        // perform algebraic factoring and count AIG nodes
        Dec_Graph_t * pFForm;
        Vec_Int_t * vCover;
        Vec_Str_t * vStr;
        char * pSopStr;
        vStr = Vec_StrAlloc( 10000 );
        vCover = Vec_IntAlloc( 1 << 16 );
        for ( i = 0; i < p->nFuncs; i++ )
        {
//            extern int Abc_IsopTest( word * pFunc, int nVars, Vec_Int_t * vCover );
//            if ( i == 0 ) printf( "\n" );
//            Abc_IsopTest( p->pFuncs[i], p->nVars, vCover );
//            continue;
            if ( fVerbose )
                printf( "%7d : ", i );
            pSopStr = Kit_PlaFromTruthNew( (unsigned *)p->pFuncs[i], p->nVars, vCover, vStr );
            pFForm = Dec_Factor( pSopStr );
            nNodes += Dec_GraphNodeNum( pFForm );
            if ( fVerbose )
                Dec_GraphPrint( stdout, pFForm, NULL, NULL );
            Dec_GraphFree( pFForm );
        }
        Vec_IntFree( vCover );
        Vec_StrFree( vStr );
    }
    else if ( DecType == 2 )
    {
        // perform bi-decomposition and count AIG nodes
        Bdc_Man_t * pManDec;
        Bdc_Par_t Pars = {0}, * pPars = &Pars;
        pPars->nVarsMax = p->nVars;
        pManDec = Bdc_ManAlloc( pPars );
        for ( i = 0; i < p->nFuncs; i++ )
        {
            if ( fVerbose )
                printf( "%7d :      ", i );
            Bdc_ManDecompose( pManDec, (unsigned *)p->pFuncs[i], NULL, p->nVars, NULL, 1000 );
            nNodes += Bdc_ManAndNum( pManDec );
            if ( fVerbose )
                Bdc_ManDecPrint( pManDec );
        }
        Bdc_ManFree( pManDec );
    }
    else if ( DecType == 3 )
    {
        // perform disjoint-support decomposition and count AIG nodes
        // (non-DSD blocks are decomposed into 2:1 MUXes, each counting as 3 AIG nodes)
        Kit_DsdNtk_t * pNtk;
        for ( i = 0; i < p->nFuncs; i++ )
        {
            if ( fVerbose )
                printf( "%7d :      ", i );
            pNtk = Kit_DsdDecomposeMux( (unsigned *)p->pFuncs[i], p->nVars, 3 );
            if ( fVerbose )
                Kit_DsdPrintExpanded( pNtk ), printf( "\n" );
            nNodes += Kit_DsdCountAigNodes( pNtk );
            Kit_DsdNtkFree( pNtk );
        }
    }
    else if ( DecType == 4 )
    {
        char pDsd[DAU_MAX_STR];
        for ( i = 0; i < p->nFuncs; i++ )
        {
            if ( fVerbose )
                printf( "%7d :      ", i );
            Dau_DsdDecompose( p->pFuncs[i], p->nVars, 0, 1, pDsd );
            if ( fVerbose )
                printf( "%s\n", pDsd );
            nNodes += Dau_DsdCountAnds( pDsd );
        }
    }
    else if ( DecType == 5 )
    {
        for ( i = 0; i < p->nFuncs; i++ )
        {
            extern void Dau_DecTrySets( word * pInit, int nVars, int fVerbose );
            int nSuppSize = Abc_TtSupportSize( p->pFuncs[i], p->nVars );
            if ( fVerbose )
                printf( "%7d :      ", i );
            Dau_DecTrySets( p->pFuncs[i], nSuppSize, fVerbose );
            if ( fVerbose )
                printf( "\n" );
        }
    }
    else assert( 0 );

    printf( "AIG nodes =%9d  ", nNodes );
    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
}

void Abc_TruthDecTest	(	char *	pFileName,
		int	DecType,
		int	nVarNum,
		int	fVerbose
	)

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

Synopsis [Apply decomposition to truth tables.]

Description []

SideEffects []

SeeAlso []

Definition at line 598 of file abcDec.c.

{
    Abc_TtStore_t * p;

    // allocate data-structure
    p = Abc_TtStoreLoad( pFileName, nVarNum );
    if ( p == NULL ) return;

    // consider functions from the file
    Abc_TruthDecPerform( p, DecType, fVerbose );

    // delete data-structure
    Abc_TtStoreFree( p, nVarNum );
//    printf( "Finished decomposing truth tables from file \"%s\".\n", pFileName );
}

static int Abc_TruthGetBit ( word *  p, int  i  )

inlinestatic

Definition at line 54 of file abcDec.c.

{ return (int)(p[i>>6] >> (i & 63)) & 1;        }

static int Abc_TruthGetHex ( word *  p, int  k  )

inlinestatic

Definition at line 59 of file abcDec.c.

{ return (int)(p[k>>4] >> ((k<<2) & 63)) & 15;  }

void Abc_TruthGetParams	(	char *	pFileName,
		int *	pnVars,
		int *	pnTruths
	)

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

Synopsis [Determine the number of variables by reading the first line.]

Description [Determine the number of functions by counting the lines.]

SideEffects []

SeeAlso []

Definition at line 262 of file abcDec.c.

{
    char * pContents;
    int i, nVars, nLines;
    // prepare the output 
    if ( pnVars )
        *pnVars = 0;
    if ( pnTruths )
        *pnTruths = 0;
    // read data from file
    pContents = Abc_FileRead( pFileName );
    if ( pContents == NULL )
        return;
    // count the number of symbols before the first space or new-line
    // (note that on Windows symbols '\r' can be inserted before each '\n')
    for ( i = 0; pContents[i]; i++ )
        if ( pContents[i] == ' ' || pContents[i] == '\n' || pContents[i] == '\r' )
            break;
    if ( pContents[i] == 0 )
        printf( "Strange, the input file does not have spaces and new-lines...\n" );

    // acount for the fact that truth tables may have "0x" at the beginning of each line
    if ( pContents[0] == '0' && pContents[1] == 'x' )
        i = i - 2;

    // determine the number of variables
    for ( nVars = 0; nVars < 32; nVars++ )
        if ( 4 * i == (1 << nVars) ) // the number of bits equal to the size of truth table
            break;
    if ( nVars < 2 || nVars > 16 )
    {
        printf( "Does not look like the input file contains truth tables...\n" );
        return;
    }
    if ( pnVars )
        *pnVars = nVars;

    // determine the number of functions by counting the lines
    nLines = 0;
    for ( i = 0; pContents[i]; i++ )
        nLines += (pContents[i] == '\n');
    if ( pnTruths )
        *pnTruths = nLines;
    ABC_FREE( pContents );
}

void Abc_TruthReadHex	(	word *	pTruth,
		char *	pString,
		int	nVars
	)

Definition at line 91 of file abcDec.c.

{
    int nWords = (nVars < 7)? 1 : (1 << (nVars-6));
    int k, Digit, nDigits = (nWords << 4);
    char EndSymbol;
    // skip the first 2 symbols if they are "0x"
    if ( pString[0] == '0' && pString[1] == 'x' )
        pString += 2;
    // get the last symbol
    EndSymbol = pString[nDigits];
    // the end symbol of the TT (the one immediately following hex digits)
    // should be one of the following: space, a new-line, or a zero-terminator
    // (note that on Windows symbols '\r' can be inserted before each '\n')
    assert( EndSymbol == ' ' || EndSymbol == '\n' || EndSymbol == '\r' || EndSymbol == '\0' );
    // read hexadecimal digits in the reverse order
    // (the last symbol in the string is the least significant digit)
    for ( k = 0; k < nDigits; k++ )
    {
        Digit = Abc_TruthReadHexDigit( pString[nDigits - 1 - k] );
        assert( Digit >= 0 && Digit < 16 );
        Abc_TruthSetHex( pTruth, k, Digit );
    }
}

static int Abc_TruthReadHexDigit ( char  HexChar )

inlinestatic

FUNCTION DEFINITIONS ///.

Definition at line 68 of file abcDec.c.

{
    if ( HexChar >= '0' && HexChar <= '9' )
        return HexChar - '0';
    if ( HexChar >= 'A' && HexChar <= 'F' )
        return HexChar - 'A' + 10;
    if ( HexChar >= 'a' && HexChar <= 'f' )
        return HexChar - 'a' + 10;
    assert( 0 ); // not a hexadecimal symbol
    return -1; // return value which makes no sense
}

static void Abc_TruthSetBit ( word *  p, int  i  )

inlinestatic

Definition at line 55 of file abcDec.c.

{ p[i>>6] |= (((word)1)<<(i & 63));             }

static void Abc_TruthSetHex ( word *  p, int  k, int  d  )

inlinestatic

Definition at line 60 of file abcDec.c.

{ p[k>>4] |= (((word)d)<<((k<<2) & 63));        }

Abc_TtStore_t* Abc_TruthStoreAlloc	(	int	nVars,
		int	nFuncs
	)

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

Synopsis [Allocate/Deallocate storage for truth tables..]

Description []

SideEffects []

SeeAlso []

Definition at line 140 of file abcDec.c.

{
    Abc_TtStore_t * p;
    int i;
    p = (Abc_TtStore_t *)malloc( sizeof(Abc_TtStore_t) );
    p->nVars  =  nVars;
    p->nWords = (nVars < 7) ? 1 : (1 << (nVars-6));
    p->nFuncs =  nFuncs;
    // alloc storage for 'nFuncs' truth tables as one chunk of memory
    p->pFuncs = (word **)malloc( (sizeof(word *) + sizeof(word) * p->nWords) * p->nFuncs );
    // assign and clean the truth table storage
    p->pFuncs[0] = (word *)(p->pFuncs + p->nFuncs);
    memset( p->pFuncs[0], 0, sizeof(word) * p->nWords * p->nFuncs );
    // split it up into individual truth tables
    for ( i = 1; i < p->nFuncs; i++ )
        p->pFuncs[i] = p->pFuncs[i-1] + p->nWords;
    return p;
}

Abc_TtStore_t* Abc_TruthStoreAlloc2	(	int	nVars,
		int	nFuncs,
		word *	pBuffer
	)

Definition at line 158 of file abcDec.c.

{
    Abc_TtStore_t * p;
    int i;
    p = (Abc_TtStore_t *)malloc( sizeof(Abc_TtStore_t) );
    p->nVars  =  nVars;
    p->nWords = (nVars < 7) ? 1 : (1 << (nVars-6));
    p->nFuncs =  nFuncs;
    // alloc storage for 'nFuncs' truth tables as one chunk of memory
    p->pFuncs = (word **)malloc( sizeof(word *) * p->nFuncs );
    // assign and clean the truth table storage
    p->pFuncs[0] = pBuffer;
    // split it up into individual truth tables
    for ( i = 1; i < p->nFuncs; i++ )
        p->pFuncs[i] = p->pFuncs[i-1] + p->nWords;
    return p;
}

void Abc_TruthStoreRead	(	char *	pFileName,
		Abc_TtStore_t *	p
	)

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

Synopsis [Read truth tables from file.]

Description []

SideEffects []

SeeAlso []

Definition at line 320 of file abcDec.c.

{
    char * pContents;
    int i, nLines;
    pContents = Abc_FileRead( pFileName );
    if ( pContents == NULL )
        return;
    // here it is assumed (without checking!) that each line of the file 
    // begins with a string of hexadecimal chars followed by space

    // the file will be read till the first empty line (pContents[i] == '\n')
    // (note that Abc_FileRead() added several empty lines at the end of the file contents)
    for ( nLines = i = 0; pContents[i] != '\n'; )
    {
        // read one line
        Abc_TruthReadHex( p->pFuncs[nLines++], &pContents[i], p->nVars );
        // skip till after the end-of-line symbol
        // (note that end-of-line symbol is also skipped)
        while ( pContents[i++] != '\n' );
    }
    // adjust the number of functions read 
    // (we may have allocated more storage because some lines in the file were empty)
    assert( p->nFuncs >= nLines );
    p->nFuncs = nLines;
    ABC_FREE( pContents );
}

void Abc_TruthWriteHex	(	FILE *	pFile,
		word *	pTruth,
		int	nVars
	)

Definition at line 116 of file abcDec.c.

{
    int nDigits, Digit, k;
    nDigits = (1 << (nVars-2));
    for ( k = 0; k < nDigits; k++ )
    {
        Digit = Abc_TruthGetHex( pTruth, k );
        assert( Digit >= 0 && Digit < 16 );
        Abc_TruthWriteHexDigit( pFile, Digit );
    }
}

static void Abc_TruthWriteHexDigit ( FILE *  pFile, int  HexDigit  )

inlinestatic

Definition at line 81 of file abcDec.c.

{
    assert( HexDigit >= 0 && HexDigit < 16 );
    if ( HexDigit < 10 )
        fprintf( pFile, "%d", HexDigit );
    else
        fprintf( pFile, "%c", 'A' + HexDigit-10 );
}

static void Abc_TruthXorBit ( word *  p, int  i  )

inlinestatic

Definition at line 56 of file abcDec.c.

{ p[i>>6] ^= (((word)1)<<(i & 63));             }

static void Abc_TruthXorHex ( word *  p, int  k, int  d  )

inlinestatic

Definition at line 61 of file abcDec.c.

{ p[k>>4] ^= (((word)d)<<((k<<2) & 63));        }

void Abc_TtStoreFree	(	Abc_TtStore_t *	p,
		int	nVarNum
	)

Definition at line 175 of file abcDec.c.

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

Abc_TtStore_t* Abc_TtStoreLoad	(	char *	pFileName,
		int	nVarNum
	)

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 395 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;
}

void Abc_TtStoreTest

(

char *

pFileName

)

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 441 of file abcDec.c.

{ 
    Abc_TtStore_t * p;
    char * pFileInput  = pFileName;
    char * pFileOutput = "out.txt";

    // read info from file
    p = Abc_TtStoreLoad( pFileInput, -1 );
    if ( p == NULL )
        return;

    // write into another file
    Abc_TtStoreWrite( pFileOutput, p, 0 );

    // delete data-structure
    Abc_TtStoreFree( p, -1 );
    printf( "Input file \"%s\" was copied into output file \"%s\".\n", pFileInput, pFileOutput );
}

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

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

Synopsis [Write truth tables into file.]

Description []

SideEffects []

SeeAlso []

Definition at line 358 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 );
}