giaEsop.c File Reference

#include "gia.h"
#include "misc/extra/extra.h"
#include "misc/vec/vecHsh.h"
#include "misc/vec/vecWec.h"

Include dependency graph for giaEsop.c:

Go to the source code of this file.

Classes
struct	Eso_Man_t_

Typedefs
typedef typedefABC_NAMESPACE_IMPL_START struct Eso_Man_t_	Eso_Man_t
	DECLARATIONS ///.

Functions
Eso_Man_t *	Eso_ManAlloc (Gia_Man_t *pGia)
	FUNCTION DEFINITIONS ///.
void	Eso_ManStop (Eso_Man_t *p)
void	Eso_ManCoverPrint (Eso_Man_t *p, Vec_Int_t *vEsop)
Vec_Wec_t *	Eso_ManCoverDerive (Eso_Man_t *p, Vec_Ptr_t *vCover)
Gia_Man_t *	Eso_ManCoverConvert (Eso_Man_t *p, Vec_Ptr_t *vCover)
int	Eso_ManFindDistOneLitEqual (int *pCube1, int *pCube2, int nLits)
int	Eso_ManFindDistOneLitNotEqual (int *pCube1, int *pCube2, int nLits)
void	Eso_ManMinimizeAdd (Eso_Man_t *p, int Cube)
void	Eso_ManMinimizeCopy (Eso_Man_t *p, Vec_Int_t *vEsop)
int	Eso_ManComputeAnd (Eso_Man_t *p, Vec_Int_t *vCube1, Vec_Int_t *vCube2, Vec_Int_t *vCube)
void	Eso_ManComputeOne (Eso_Man_t *p, Vec_Int_t *vEsop1, Vec_Int_t *vEsop2, Vec_Int_t *vEsop)
Vec_Int_t *	Eso_ManTransformOne (Eso_Man_t *p, Vec_Int_t *vEsop, int fCompl, Vec_Int_t *vRes)
Gia_Man_t *	Eso_ManCompute (Gia_Man_t *pGia, int fVerbose, Vec_Wec_t **pvRes)

Typedef Documentation

Eso_Man_t

typedef typedefABC_NAMESPACE_IMPL_START struct Eso_Man_t_ Eso_Man_t

DECLARATIONS ///.

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

FileName [giaEsop.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Scalable AIG package.]

Synopsis [ESOP computation.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id

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

]

Definition at line 33 of file giaEsop.c.

Function Documentation

Eso_ManAlloc()

Eso_Man_t * Eso_ManAlloc

(

Gia_Man_t *

pGia

)

FUNCTION DEFINITIONS ///.

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

Synopsis [Computation manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 65 of file giaEsop.c.

{
    int i, n, Id;
    Eso_Man_t * p = ABC_CALLOC( Eso_Man_t, 1 );
    p->pGia   = pGia;
    p->nVars  = Gia_ManCiNum(pGia);
    p->Cube1  = ABC_INFINITY;
    p->vEsops = Vec_WecStart( Gia_ManObjNum(pGia) );
    p->pHash  = Hsh_VecManStart( 1000 );
    p->vCubes = Vec_WecStart(Gia_ManCiNum(pGia)+1);
    p->vCube1 = Vec_IntAlloc(Gia_ManCiNum(pGia));
    p->vCube2 = Vec_IntAlloc(Gia_ManCiNum(pGia));
    p->vCube  = Vec_IntAlloc(Gia_ManCiNum(pGia));
    Gia_ManForEachCiId( pGia, Id, i )
    {
        for ( n = 0; n < 2; n++ )
        {
            Vec_IntFill( p->vCube, 1, Abc_Var2Lit(i, n) );
            Hsh_VecManAdd( p->pHash, p->vCube );
        }
        Vec_IntPush( Vec_WecEntry(p->vEsops, Id), Abc_Var2Lit(i, 0) );
    }
    return p;
}

Here is the caller graph for this function:

Eso_ManCompute()

Gia_Man_t * Eso_ManCompute	(	Gia_Man_t *	pGia,
		int	fVerbose,
		Vec_Wec_t **	pvRes )

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

Synopsis [Computes ESOP from AIG.]

Description []

SideEffects []

SeeAlso []

Definition at line 489 of file giaEsop.c.

{
    abctime clk = Abc_Clock();
    Vec_Ptr_t * vCover;
    Gia_Man_t * pNew = NULL;
    Gia_Obj_t * pObj; 
    int i, nCubes = 0, nCubesUsed = 0;
    Vec_Int_t * vEsop1, * vEsop2, * vEsop;
    Eso_Man_t * p = Eso_ManAlloc( pGia ); 
    Gia_ManForEachAnd( pGia, pObj, i )
    {
        vEsop1 = Vec_WecEntry( p->vEsops, Gia_ObjFaninId0(pObj, i) );
        vEsop2 = Vec_WecEntry( p->vEsops, Gia_ObjFaninId1(pObj, i) );
        vEsop1 = Eso_ManTransformOne( p, vEsop1, Gia_ObjFaninC0(pObj), p->vCube1 );
        vEsop2 = Eso_ManTransformOne( p, vEsop2, Gia_ObjFaninC1(pObj), p->vCube2 );
        vEsop  = Vec_WecEntry( p->vEsops, i );
        Eso_ManComputeOne( p, vEsop1, vEsop2, vEsop );
        nCubes += Vec_IntSize(vEsop);
    }
    vCover = Vec_PtrAlloc( Gia_ManCoNum(pGia) );
    Gia_ManForEachCo( pGia, pObj, i )
    {
        vEsop1 = Vec_WecEntry( p->vEsops, Gia_ObjFaninId0p(pGia, pObj) );
        vEsop1 = Eso_ManTransformOne( p, vEsop1, Gia_ObjFaninC0(pObj), p->vCube1 );
        if ( fVerbose )
            printf( "Output %3d:  ESOP has %5d cubes\n", i, Vec_IntSize(vEsop1) );
//        if ( fVerbose )
//            Eso_ManCoverPrint( p, vEsop1 );
        Vec_PtrPush( vCover, Vec_IntDup(vEsop1) );
        nCubesUsed += Vec_IntSize(vEsop1);
    }
    if ( fVerbose )
    {
        printf( "Outs = %d.  Cubes = %d.  Used = %d.  Hashed = %d. ", 
            Gia_ManCoNum(pGia), nCubes, nCubesUsed, Hsh_VecSize(p->pHash) );
        Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
    }
    if ( pvRes )
        *pvRes = Eso_ManCoverDerive( p, vCover );
    else
        pNew = Eso_ManCoverConvert( p, vCover );
    Vec_VecFree( (Vec_Vec_t *)vCover );
    Eso_ManStop( p );
    return pNew;
}

Here is the call graph for this function:

Eso_ManComputeAnd()

int Eso_ManComputeAnd	(	Eso_Man_t *	p,
		Vec_Int_t *	vCube1,
		Vec_Int_t *	vCube2,
		Vec_Int_t *	vCube )

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

Synopsis [Compute the produce of two covers.]

Description []

SideEffects []

SeeAlso []

Definition at line 381 of file giaEsop.c.

{
    int * pBeg  = vCube->pArray;
    int * pBeg1 = vCube1->pArray;
    int * pBeg2 = vCube2->pArray;
    int * pEnd1 = vCube1->pArray + vCube1->nSize;
    int * pEnd2 = vCube2->pArray + vCube2->nSize;
    while ( pBeg1 < pEnd1 && pBeg2 < pEnd2 )
    {
        if ( *pBeg1 == *pBeg2 )
            *pBeg++ = *pBeg1++, pBeg2++;
        else if ( Abc_Lit2Var(*pBeg1) == Abc_Lit2Var(*pBeg2) )
            return -1;
        else if ( *pBeg1 < *pBeg2 )
            *pBeg++ = *pBeg1++;
        else 
            *pBeg++ = *pBeg2++;
    }
    while ( pBeg1 < pEnd1 )
        *pBeg++ = *pBeg1++;
    while ( pBeg2 < pEnd2 )
        *pBeg++ = *pBeg2++;
    vCube->nSize = pBeg - vCube->pArray;
    assert( vCube->nSize <= vCube->nCap );
    assert( vCube->nSize >= vCube1->nSize );
    assert( vCube->nSize >= vCube2->nSize );
    return Hsh_VecManAdd( p->pHash, vCube );
}

Here is the caller graph for this function:

Eso_ManComputeOne()

void Eso_ManComputeOne	(	Eso_Man_t *	p,
		Vec_Int_t *	vEsop1,
		Vec_Int_t *	vEsop2,
		Vec_Int_t *	vEsop )

Definition at line 409 of file giaEsop.c.

{
    Vec_Int_t vCube1, vCube2;
    int i, k, Cube1, Cube2, Cube;
    Vec_IntClear( vEsop );
    if ( Vec_IntSize(vEsop1) == 0 || Vec_IntSize(vEsop2) == 0 )
        return;
    Cube1 = Vec_IntEntry(vEsop1, 0);
    Cube2 = Vec_IntEntry(vEsop2, 0);
    Vec_IntForEachEntry( vEsop1, Cube1, i )
    {
        if ( Cube1 == p->Cube1 )
        {
            Vec_IntForEachEntry( vEsop2, Cube2, k )
                Eso_ManMinimizeAdd( p, Cube2 );
            continue;
        }
        Vec_IntForEachEntry( vEsop2, Cube2, k )
        {
            if ( Cube2 == p->Cube1 )
            {
                Eso_ManMinimizeAdd( p, Cube1 );
                continue;
            }
            vCube1 = *Hsh_VecReadEntry( p->pHash, Cube1 );
            vCube2 = *Hsh_VecReadEntry( p->pHash, Cube2 );
            Cube = Eso_ManComputeAnd( p, &vCube1, &vCube2, p->vCube );
            if ( Cube >= 0 )
                Eso_ManMinimizeAdd( p, Cube );
        }
    }
    Eso_ManMinimizeCopy( p, vEsop );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Eso_ManCoverConvert()

Gia_Man_t * Eso_ManCoverConvert	(	Eso_Man_t *	p,
		Vec_Ptr_t *	vCover )

Definition at line 173 of file giaEsop.c.

{
    Vec_Int_t * vEsop;
    Gia_Man_t * pNew, * pTemp;
    Gia_Obj_t * pObj;  int i;
    pNew = Gia_ManStart( Gia_ManObjNum(p->pGia) );
    pNew->pName = Abc_UtilStrsav( p->pGia->pName );
    pNew->pSpec = Abc_UtilStrsav( p->pGia->pSpec );
    Gia_ManHashAlloc( pNew );
    Gia_ManConst0(p->pGia)->Value = 0;
    Gia_ManForEachCi( p->pGia, pObj, i )
        pObj->Value = Gia_ManAppendCi(pNew);
    Vec_PtrForEachEntry( Vec_Int_t *, vCover, vEsop, i )
    {
        if ( Vec_IntSize(vEsop) > 0 )
        {
            int c, Cube, iRoot = 0;
            Vec_IntForEachEntry( vEsop, Cube, c )
            {
                int k, Lit, iAnd = 1;
                if ( Cube != p->Cube1 )
                {
                    Vec_Int_t * vCube = Eso_ManCube( p, Cube );
                    Vec_IntForEachEntry( vCube, Lit, k )
                        iAnd = Gia_ManHashAnd( pNew, iAnd, Lit + 2 );
                }
                iRoot = Gia_ManHashXor( pNew, iRoot, iAnd );
            }
            Gia_ManAppendCo( pNew, iRoot );
        }
        else
            Gia_ManAppendCo( pNew, 0 );
    }
    // cleanup
    pNew = Gia_ManCleanup( pTemp = pNew );
    Gia_ManStop( pTemp );
    return pNew;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Eso_ManCoverDerive()

Vec_Wec_t * Eso_ManCoverDerive	(	Eso_Man_t *	p,
		Vec_Ptr_t *	vCover )

Definition at line 146 of file giaEsop.c.

{
    Vec_Wec_t * vRes;
    Vec_Int_t * vEsop, * vLevel;  int i;
    vRes = Vec_WecAlloc( Vec_VecSizeSize((Vec_Vec_t *)vCover) );
    Vec_PtrForEachEntry( Vec_Int_t *, vCover, vEsop, i )
    {
        if ( Vec_IntSize(vEsop) > 0 )
        {
            int c, Cube;
            Vec_IntForEachEntry( vEsop, Cube, c )
            {
                vLevel = Vec_WecPushLevel( vRes );
                if ( Cube != p->Cube1 )
                {
                    int k, Lit;
                    Vec_Int_t * vCube = Eso_ManCube( p, Cube );
                    Vec_IntForEachEntry( vCube, Lit, k )
                        Vec_IntPush( vLevel, Lit );
                }
                Vec_IntPush( vLevel, -i-1 );
            }
        }
    }
    //assert( Abc_MaxInt(Vec_WecSize(vRes), 8) == Vec_WecCap(vRes) );
    return vRes;
}

Here is the caller graph for this function:

Eso_ManCoverPrint()

void Eso_ManCoverPrint	(	Eso_Man_t *	p,
		Vec_Int_t *	vEsop )

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

Synopsis [Printing/transforming the cover.]

Description []

SideEffects []

SeeAlso []

Definition at line 112 of file giaEsop.c.

{
    Vec_Str_t * vStr;
    Vec_Int_t * vCube;
    int i, k, Lit, Cube;
    if ( Vec_IntSize(vEsop) == 0 )
    {
        printf( "Const 0\n" );
        return;
    }
    vStr = Vec_StrAlloc( p->nVars + 4 );
    Vec_StrFill( vStr, p->nVars, '-' );
    Vec_StrPush( vStr, ' ' );
    Vec_StrPush( vStr, '1' );
    Vec_StrPush( vStr, '\n' );
    Vec_StrPush( vStr, '\0' );
    assert( Vec_IntSize(vEsop) > 0 );
    Vec_IntForEachEntry( vEsop, Cube, i )
    {
        if ( Cube == p->Cube1 )
            printf( "%s", Vec_StrArray(vStr) );
        else 
        {
            vCube = Eso_ManCube( p, Cube );
            Vec_IntForEachEntry( vCube, Lit, k )
                Vec_StrWriteEntry( vStr, Abc_Lit2Var(Lit), (char)(Abc_LitIsCompl(Lit)?'0':'1') );
            printf( "%s", Vec_StrArray(vStr) );
            Vec_IntForEachEntry( vCube, Lit, k )
                Vec_StrWriteEntry( vStr, Abc_Lit2Var(Lit), '-' );
        }
    }
    printf( "\n" );
    Vec_StrFree( vStr );
}

Eso_ManFindDistOneLitEqual()

int Eso_ManFindDistOneLitEqual	(	int *	pCube1,
		int *	pCube2,
		int	nLits )

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

Synopsis [Minimization.]

Description []

SideEffects []

SeeAlso []

Definition at line 223 of file giaEsop.c.

{
    int i, iDiff = -1;
    for ( i = 0; i < nLits; i++ )
        if ( pCube1[i] != pCube2[i] )
        {
            if ( iDiff != -1 )
                return -1;
            if ( Abc_Lit2Var(pCube1[i]) != Abc_Lit2Var(pCube2[i]) )
                return -1;
            iDiff = i;
        }
    return iDiff;
}

Here is the caller graph for this function:

Eso_ManFindDistOneLitNotEqual()

int Eso_ManFindDistOneLitNotEqual	(	int *	pCube1,
		int *	pCube2,
		int	nLits )

Definition at line 237 of file giaEsop.c.

{
    int i, k, iDiff = -1;
    for ( i = k = 0; i < nLits; i++, k++ )
        if ( pCube1[i] != pCube2[k] )
        {
            if ( iDiff != -1 )
                return -1;
            iDiff = i;
            i--;
        }
    if ( iDiff == -1 )
        iDiff = nLits;
    return iDiff;
}

Here is the caller graph for this function:

Eso_ManMinimizeAdd()

void Eso_ManMinimizeAdd	(	Eso_Man_t *	p,
		int	Cube )

Definition at line 252 of file giaEsop.c.

{
    int fMimimize = 1;
    Vec_Int_t * vCube      = (Cube == p->Cube1) ? NULL : Eso_ManCube(p, Cube); 
    int * pCube2, * pCube  = (Cube == p->Cube1) ? NULL : Vec_IntArray(vCube); 
    int Cube2, nLits       = (Cube == p->Cube1) ? 0 : Vec_IntSize(vCube);
    Vec_Int_t * vLevel     = Vec_WecEntry( p->vCubes, nLits );
    int c, k, iLit, iPlace = Vec_IntFind( vLevel, Cube );
    if ( iPlace >= 0 ) // identical found
    {
        Vec_IntDrop( vLevel, iPlace );
        return;
    }
    if ( Cube == p->Cube1 ) // simple case
    {
        assert( Vec_IntSize(vLevel) == 0 );
        Vec_IntPush( vLevel, Cube );
        return;
    }
    // look for distance-1 in next bin
    if ( fMimimize && nLits < p->nVars - 1 )
    {
        Vec_Int_t * vLevel = Vec_WecEntry( p->vCubes, nLits+1 );
        Vec_IntForEachEntry( vLevel, Cube2, c )
        {
            pCube2 = Hsh_VecReadArray( p->pHash, Cube2 ); 
            iLit = Eso_ManFindDistOneLitNotEqual( pCube, pCube2, nLits );
            if ( iLit == -1 )
                continue;
            // remove this cube
            Vec_IntDrop( vLevel, c );
            // create new cube
            Vec_IntClear( p->vCube );
            for ( k = 0; k <= nLits; k++ )
                Vec_IntPush( p->vCube, Abc_LitNotCond(pCube2[k], k == iLit) );
            Cube = Hsh_VecManAdd( p->pHash, p->vCube );
            // try to add new cube
            Eso_ManMinimizeAdd( p, Cube );
            return;
        }
    }
    // look for distance-1 in the same bin
    if ( fMimimize )
    {
        Vec_IntForEachEntry( vLevel, Cube2, c )
        {
            pCube2 = Hsh_VecReadArray( p->pHash, Cube2 ); 
            iLit = Eso_ManFindDistOneLitEqual( pCube2, pCube, nLits );
            if ( iLit == -1 )
                continue;
            // remove this cube
            Vec_IntDrop( vLevel, c );
            // create new cube
            Vec_IntClear( p->vCube );
            for ( k = 0; k < nLits; k++ )
                if ( k != iLit )
                    Vec_IntPush( p->vCube, pCube[k] );
            if ( Vec_IntSize(p->vCube) == 0 )
                Cube = p->Cube1;
            else
                Cube = Hsh_VecManAdd( p->pHash, p->vCube );
            // try to add new cube
            Eso_ManMinimizeAdd( p, Cube );
            return;
        }
    }
    assert( nLits > 0 );
    if ( fMimimize && nLits > 0 )
    {
        // look for distance-1 in the previous bin
        Vec_Int_t * vLevel = Vec_WecEntry( p->vCubes, nLits-1 );
        // check for the case of one-literal cube
        if ( nLits == 1 && Vec_IntSize(vLevel) == 1 )
        {
            Vec_IntDrop( vLevel, 0 );
            Cube = Abc_LitNot( Cube );
        }
        else
        Vec_IntForEachEntry( vLevel, Cube2, c )
        {
            pCube2 = Hsh_VecReadArray( p->pHash, Cube2 ); 
            iLit = Eso_ManFindDistOneLitNotEqual( pCube2, pCube, nLits-1 );
            if ( iLit == -1 )
                continue;
            // remove this cube
            Vec_IntDrop( vLevel, c );
            // create new cube
            Vec_IntClear( p->vCube );
            for ( k = 0; k < nLits; k++ )
                Vec_IntPush( p->vCube, Abc_LitNotCond(pCube[k], k == iLit) );
            Cube = Hsh_VecManAdd( p->pHash, p->vCube );
            // try to add new cube
            Eso_ManMinimizeAdd( p, Cube );
            return;
        }
    }
    // could not find - simply add this cube
    Vec_IntPush( vLevel, Cube );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Eso_ManMinimizeCopy()

void Eso_ManMinimizeCopy	(	Eso_Man_t *	p,
		Vec_Int_t *	vEsop )

Definition at line 352 of file giaEsop.c.

{
    Vec_Int_t * vLevel;
    int i;
    Vec_IntClear( vEsop );
    Vec_WecForEachLevel( p->vCubes, vLevel, i )
    {
        Vec_IntAppend( vEsop, vLevel );
        if ( i > 0 )
        {
            int k, Cube;
            Vec_IntForEachEntry( vLevel, Cube, k )
                assert( Vec_IntSize(Eso_ManCube(p, Cube)) == i );
        }
        Vec_IntClear( vLevel );
    }
}

Here is the caller graph for this function:

Eso_ManStop()

void Eso_ManStop

(

Eso_Man_t *

p

)

Definition at line 89 of file giaEsop.c.

{
    Vec_WecFree( p->vEsops );
    Hsh_VecManStop( p->pHash );
    Vec_WecFree( p->vCubes );
    Vec_IntFree( p->vCube1 );
    Vec_IntFree( p->vCube2 );
    Vec_IntFree( p->vCube );
    ABC_FREE( p );
}

Here is the caller graph for this function:

Eso_ManTransformOne()

Vec_Int_t * Eso_ManTransformOne	(	Eso_Man_t *	p,
		Vec_Int_t *	vEsop,
		int	fCompl,
		Vec_Int_t *	vRes )

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

Synopsis [Complements the cover if needed, or just copy it.]

Description []

SideEffects []

SeeAlso []

Definition at line 454 of file giaEsop.c.

{
    int i, Cube, Start = 0;
    Vec_IntClear( vRes );
    if ( fCompl )
    {
        if ( Vec_IntSize(vEsop) == 0 )
            Vec_IntPush( vRes, p->Cube1 );
        else
        {
            Cube = Vec_IntEntry(vEsop, 0);
            if ( Cube == p->Cube1 )
                Start = 1;
            else if ( Cube < 2 * p->nVars )
                Vec_IntPush( vRes, Abc_LitNot(Cube) ), Start = 1;
            else
                Vec_IntPush( vRes, p->Cube1 );
        }
    }
    Vec_IntForEachEntryStart( vEsop, Cube, i, Start )
        Vec_IntPush( vRes, Cube );
    return vRes;
}

Here is the caller graph for this function: