giaHash.c File Reference

#include "gia.h"

Include dependency graph for giaHash.c:

Go to the source code of this file.

Functions
int	Gia_ManHashLookupInt (Gia_Man_t *p, int iLit0, int iLit1)
int	Gia_ManHashLookup (Gia_Man_t *p, Gia_Obj_t *p0, Gia_Obj_t *p1)
void	Gia_ManHashAlloc (Gia_Man_t *p)
void	Gia_ManHashStart (Gia_Man_t *p)
void	Gia_ManHashStop (Gia_Man_t *p)
void	Gia_ManHashResize (Gia_Man_t *p)
void	Gia_ManHashProfile (Gia_Man_t *p)
int	Gia_ManHashXorReal (Gia_Man_t *p, int iLit0, int iLit1)
int	Gia_ManHashMuxReal (Gia_Man_t *p, int iLitC, int iLit1, int iLit0)
int	Gia_ManHashAnd (Gia_Man_t *p, int iLit0, int iLit1)
int	Gia_ManHashOr (Gia_Man_t *p, int iLit0, int iLit1)
int	Gia_ManHashAndTry (Gia_Man_t *p, int iLit0, int iLit1)
int	Gia_ManHashXor (Gia_Man_t *p, int iLit0, int iLit1)
int	Gia_ManHashMux (Gia_Man_t *p, int iCtrl, int iData1, int iData0)
int	Gia_ManHashMaj (Gia_Man_t *p, int iData0, int iData1, int iData2)
Gia_Man_t *	Gia_ManRehash (Gia_Man_t *p, int fAddStrash)
int	Gia_ManHashAndMulti (Gia_Man_t *p, Vec_Int_t *vLits)
int	Gia_ManHashAndMulti2 (Gia_Man_t *p, Vec_Int_t *vLits)
int	Gia_ManHashDualMiter (Gia_Man_t *p, Vec_Int_t *vOuts)
int *	Gia_ManCollectLiterals (int nVars)
int *	Gia_ManGenZero (int nBits)
int *	Gia_ManGenPerm (int nBits)
int *	Gia_ManGenPerm2 (int nBits)
int	Gia_ManMultiCheck (int *pPerm, int nPerm)
int	Gia_ManMultiInputPerm (Gia_Man_t *pNew, int *pVars, int nVars, int *pPerm, int fOr, int fXor)
Gia_Man_t *	Gia_ManMultiInputTest (int nBits)
int	Gia_ManCube (Gia_Man_t *pNew, int Vars, int nVars, int *pLits)
int	Gia_ManMuxTree_rec (Gia_Man_t *pNew, int *pCtrl, int nCtrl, int *pData)
void	Gia_ManUsePerm (int *pTree, int nBits, int *pPerm)
int	Gia_ManFindCond (int *pLits, int nBits, int iLate1, int iLate2)
int	Gia_ManLatest (int *pPerm, int nVars, int iPrev1, int iPrev2, int iPrev3)
int	Gia_ManEarliest (int *pPerm, int nVars)
int	Gia_ManDecompOne (Gia_Man_t *pNew, int *pTree, int nBits, int *pPerm, int iLate)
int	Gia_ManDecompTwo (Gia_Man_t *pNew, int *pTree, int nBits, int *pPerm, int iLate1, int iLate2)
int	Gia_ManDecompThree (Gia_Man_t *pNew, int *pTree, int nBits, int *pPerm, int iLate1, int iLate2, int iLate3)
int	Gia_ManDecomp (Gia_Man_t *pNew, int *pTree, int nBits, int *pPerm)
Gia_Man_t *	Gia_ManMuxTreeTest (int nBits)

Function Documentation

Gia_ManCollectLiterals()

int * Gia_ManCollectLiterals

(

int

nVars

)

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

Synopsis [Create multi-input tree.]

Description []

SideEffects []

SeeAlso []

Definition at line 830 of file giaHash.c.

{
    int i, * pRes = ABC_CALLOC( int, nVars );
    for ( i = 0; i < nVars; i++ )
        pRes[i] = Abc_Var2Lit( i+1, 0 );
    return pRes;
}

Here is the caller graph for this function:

Gia_ManCube()

int Gia_ManCube	(	Gia_Man_t *	pNew,
		int	Vars,
		int	nVars,
		int *	pLits )

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

Synopsis [Create MUX tree.]

Description []

SideEffects []

SeeAlso []

Definition at line 958 of file giaHash.c.

{
    int i, iLit = 1;
    for ( i = 0; i < nVars; i++ )
        iLit = Gia_ManHashAnd( pNew, iLit, Abc_LitNotCond(pLits[i], !((Vars >> i) & 1)) );
    return iLit;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Gia_ManDecomp()

int Gia_ManDecomp	(	Gia_Man_t *	pNew,
		int *	pTree,
		int	nBits,
		int *	pPerm )

Definition at line 1089 of file giaHash.c.

{
    if ( nBits == 2 )
        return Gia_ManMuxTree_rec( pNew, pTree, nBits, pTree+nBits );
    else
    {
        int iBase  = Gia_ManEarliest( pPerm+nBits, 1<<nBits ), BaseValue = pPerm[nBits+iBase];
        int iLate1 = Gia_ManLatest( pPerm+nBits, 1<<nBits, -1, -1, -1 );
        int iLate2 = Gia_ManLatest( pPerm+nBits, 1<<nBits, iLate1, -1, -1 );
        int iLate3 = Gia_ManLatest( pPerm+nBits, 1<<nBits, iLate1, iLate2, -1 );
        int iLate4 = Gia_ManLatest( pPerm+nBits, 1<<nBits, iLate1, iLate2, iLate3 );
        if ( 0 )
        {
            int i;
            for ( i = 0; i < (1<<nBits); i++ )
                printf( "%d ", pPerm[nBits+i] );
            printf( "\n" );
        }
        if ( pPerm[nBits+iLate1] > BaseValue && pPerm[nBits+iLate2] > BaseValue && pPerm[nBits+iLate3] > BaseValue && pPerm[nBits+iLate4] == BaseValue )
            return Gia_ManDecompThree( pNew, pTree, nBits, pPerm, iLate1, iLate2, iLate3 );
        if ( pPerm[nBits+iLate1] > BaseValue && pPerm[nBits+iLate2] > BaseValue && pPerm[nBits+iLate3] == BaseValue )
            return Gia_ManDecompTwo( pNew, pTree, nBits, pPerm, iLate1, iLate2 );
        if ( pPerm[nBits+iLate1] > BaseValue && pPerm[nBits+iLate2] == BaseValue )
            return Gia_ManDecompOne( pNew, pTree, nBits, pPerm, iLate1 );
        return Gia_ManMuxTree_rec( pNew, pTree, nBits, pTree+nBits );
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Gia_ManDecompOne()

int Gia_ManDecompOne	(	Gia_Man_t *	pNew,
		int *	pTree,
		int	nBits,
		int *	pPerm,
		int	iLate )

Definition at line 1039 of file giaHash.c.

{
    int iRes, iData;
    assert( iLate >= 0 && iLate < (1<<nBits) );
    iData = pTree[nBits+iLate];
    pTree[nBits+iLate] = pTree[nBits+(iLate^1)];
    iRes = Gia_ManMuxTree_rec( pNew, pTree, nBits, pTree+nBits );
    return Gia_ManHashMux( pNew, Gia_ManCube(pNew, iLate, nBits, pTree), iData, iRes );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Gia_ManDecompThree()

int Gia_ManDecompThree	(	Gia_Man_t *	pNew,
		int *	pTree,
		int	nBits,
		int *	pPerm,
		int	iLate1,
		int	iLate2,
		int	iLate3 )

Definition at line 1064 of file giaHash.c.

{
    int iRes, iData1, iData2, iData3, iCube1, iCube2, iCube3, iCtrl0, iCtrl1, iMux10, iMux11;
    assert( iLate1 != iLate2 );
    assert( iLate1 != iLate3 );
    assert( iLate2 != iLate3 );
    assert( iLate1 >= 0 && iLate1 < (1<<nBits) );
    assert( iLate2 >= 0 && iLate2 < (1<<nBits) );
    assert( iLate3 >= 0 && iLate3 < (1<<nBits) );
    iData1 = pTree[nBits+iLate1];
    iData2 = pTree[nBits+iLate2];
    iData3 = pTree[nBits+iLate3];
    pTree[nBits+iLate1] = pTree[nBits+(iLate1^1)];
    pTree[nBits+iLate2] = pTree[nBits+(iLate2^1)];
    pTree[nBits+iLate3] = pTree[nBits+(iLate3^1)];
    iRes   = Gia_ManMuxTree_rec( pNew, pTree, nBits, pTree+nBits );
    iCube1 = Gia_ManCube( pNew, iLate1, nBits, pTree );
    iCube2 = Gia_ManCube( pNew, iLate2, nBits, pTree );
    iCube3 = Gia_ManCube( pNew, iLate3, nBits, pTree );
    iCtrl0 = Gia_ManHashOr( pNew, iCube1, iCube3 );
    iCtrl1 = Gia_ManHashOr( pNew, iCube2, iCube3 );
    iMux10 = Gia_ManHashMux( pNew, iCtrl0, iData1, iRes );
    iMux11 = Gia_ManHashMux( pNew, iCtrl0, iData3, iData2 );
    return Gia_ManHashMux( pNew, iCtrl1, iMux11, iMux10 );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Gia_ManDecompTwo()

int Gia_ManDecompTwo	(	Gia_Man_t *	pNew,
		int *	pTree,
		int	nBits,
		int *	pPerm,
		int	iLate1,
		int	iLate2 )

Definition at line 1048 of file giaHash.c.

{
    int iRes, iData1, iData2, iData, iCond, iCond2;
    assert( iLate1 != iLate2 );
    assert( iLate1 >= 0 && iLate1 < (1<<nBits) );
    assert( iLate2 >= 0 && iLate2 < (1<<nBits) );
    iData1 = pTree[nBits+iLate1];
    iData2 = pTree[nBits+iLate2];
    pTree[nBits+iLate1] = pTree[nBits+(iLate1^1)];
    pTree[nBits+iLate2] = pTree[nBits+(iLate2^1)];
    iRes   = Gia_ManMuxTree_rec( pNew, pTree, nBits, pTree+nBits );
    iCond  = Gia_ManHashOr( pNew, Gia_ManCube(pNew, iLate1, nBits, pTree), Gia_ManCube(pNew, iLate2, nBits, pTree) ); 
    iCond2 = Gia_ManFindCond( pTree, nBits, iLate1, iLate2 );
    iData  = Gia_ManHashMux( pNew, iCond2, iData2, iData1 );
    return Gia_ManHashMux( pNew, iCond, iData, iRes );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Gia_ManEarliest()

int Gia_ManEarliest	(	int *	pPerm,
		int	nVars )

Definition at line 1028 of file giaHash.c.

{
    int i, Value = ABC_INFINITY, iLate = -1;
    for ( i = 0; i < nVars; i++ )
        if ( Value > pPerm[i] )
        {
            Value = pPerm[i];
            iLate = i;
        }
    return iLate;
}

Here is the caller graph for this function:

Gia_ManFindCond()

int Gia_ManFindCond	(	int *	pLits,
		int	nBits,
		int	iLate1,
		int	iLate2 )

Definition at line 1008 of file giaHash.c.

{
    int i;
    assert( iLate1 != iLate2 );
    for ( i = 0; i < nBits; i++ )
        if ( (((iLate1 ^ iLate2) >> i) & 1) )
            return Abc_LitNotCond( pLits[i], (iLate1 >> i) & 1 );
    return -1;
}

Here is the caller graph for this function:

Gia_ManGenPerm()

int * Gia_ManGenPerm

(

int

nBits

)

Definition at line 841 of file giaHash.c.

{
    int i, * pRes = ABC_CALLOC( int, nBits );
    srand( time(NULL) );
    for ( i = 0; i < nBits; i++ )
        pRes[i] = i;
    for ( i = 0; i < nBits; i++ )
    {
        int iPerm = rand() % nBits;
        ABC_SWAP( int, pRes[i], pRes[iPerm] );
    }
    return pRes;
}

Here is the caller graph for this function:

Gia_ManGenPerm2()

int * Gia_ManGenPerm2

(

int

nBits

)

Definition at line 854 of file giaHash.c.

{
    int i, * pRes = ABC_CALLOC( int, nBits );
    srand( time(NULL) );
    for ( i = 0; i < nBits; i++ )
        pRes[i] = rand() % nBits;
    return pRes;
}

Here is the caller graph for this function:

Gia_ManGenZero()

int * Gia_ManGenZero

(

int

nBits

)

Definition at line 837 of file giaHash.c.

{
    return ABC_CALLOC( int, nBits );
}

Gia_ManHashAlloc()

void Gia_ManHashAlloc

(

Gia_Man_t *

p

)

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

Synopsis [Starts the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 105 of file giaHash.c.

{
    assert( Vec_IntSize(&p->vHTable) == 0 );
    Vec_IntFill( &p->vHTable, Abc_PrimeCudd( Gia_ManAndNum(p) ? Gia_ManAndNum(p) + 1000 : p->nObjsAlloc ), 0 );
    Vec_IntGrow( &p->vHash, Abc_MaxInt(Vec_IntSize(&p->vHTable), Gia_ManObjNum(p)) );
    Vec_IntFill( &p->vHash, Gia_ManObjNum(p), 0 );
//printf( "Alloced table with %d entries.\n", Vec_IntSize(&p->vHTable) );
}

Gia_ManHashAnd()

int Gia_ManHashAnd	(	Gia_Man_t *	p,
		int	iLit0,
		int	iLit1 )

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

Synopsis [Hashes AND gate.]

Description []

SideEffects []

SeeAlso []

Definition at line 576 of file giaHash.c.

{ 
    if ( iLit0 < 2 )
        return iLit0 ? iLit1 : 0;
    if ( iLit1 < 2 )
        return iLit1 ? iLit0 : 0;
    if ( iLit0 == iLit1 )
        return iLit1;
    if ( iLit0 == Abc_LitNot(iLit1) )
        return 0;
    if ( p->fGiaSimple )
    {
        assert( Vec_IntSize(&p->vHTable) == 0 );
        return Gia_ManAppendAnd( p, iLit0, iLit1 );
    }
    if ( (p->nObjs & 0xFF) == 0 && 2 * Vec_IntSize(&p->vHTable) < Gia_ManAndNum(p) )
        Gia_ManHashResize( p );
    if ( p->fAddStrash )
    {
        Gia_Obj_t * pObj = Gia_ManAddStrash( p, Gia_ObjFromLit(p, iLit0), Gia_ObjFromLit(p, iLit1) );
        if ( pObj != NULL )
            return Gia_ObjToLit( p, pObj );
    }
    if ( iLit0 > iLit1 )
        iLit0 ^= iLit1, iLit1 ^= iLit0, iLit0 ^= iLit1;
    {
        int * pPlace = Gia_ManHashFind( p, iLit0, iLit1, -1 );
        if ( *pPlace )
        {
            p->nHashHit++;
            return Abc_Var2Lit( *pPlace, 0 );
        }
        p->nHashMiss++;
        if ( Vec_IntSize(&p->vHash) < Vec_IntCap(&p->vHash) )
            *pPlace = Abc_Lit2Var( Gia_ManAppendAnd( p, iLit0, iLit1 ) );
        else
        {
            int iNode = Gia_ManAppendAnd( p, iLit0, iLit1 );
            pPlace = Gia_ManHashFind( p, iLit0, iLit1, -1 );
            assert( *pPlace == 0 );
            *pPlace = Abc_Lit2Var( iNode );
        }
        return Abc_Var2Lit( *pPlace, 0 );
    }
}

Here is the call graph for this function:

Gia_ManHashAndMulti()

int Gia_ManHashAndMulti	(	Gia_Man_t *	p,
		Vec_Int_t *	vLits )

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

Synopsis [Creates well-balanced AND gate.]

Description []

SideEffects []

SeeAlso []

Definition at line 783 of file giaHash.c.

{
    if ( Vec_IntSize(vLits) == 0 )
        return 0;
    while ( Vec_IntSize(vLits) > 1 )
    {
        int i, k = 0, Lit1, Lit2, LitRes;
        Vec_IntForEachEntryDouble( vLits, Lit1, Lit2, i )
        {
            LitRes = Gia_ManHashAnd( p, Lit1, Lit2 );
            Vec_IntWriteEntry( vLits, k++, LitRes );
        }
        if ( Vec_IntSize(vLits) & 1 )
            Vec_IntWriteEntry( vLits, k++, Vec_IntEntryLast(vLits) );
        Vec_IntShrink( vLits, k );
    }
    assert( Vec_IntSize(vLits) == 1 );
    return Vec_IntEntry(vLits, 0);
}

Here is the call graph for this function:

Here is the caller graph for this function:

Gia_ManHashAndMulti2()

int Gia_ManHashAndMulti2	(	Gia_Man_t *	p,
		Vec_Int_t *	vLits )

Definition at line 802 of file giaHash.c.

{
    int i, iLit, iRes = 1;
    Vec_IntForEachEntry( vLits, iLit, i )
        iRes = Gia_ManHashAnd( p, iRes, iLit );
    return iRes;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Gia_ManHashAndTry()

int Gia_ManHashAndTry	(	Gia_Man_t *	p,
		int	iLit0,
		int	iLit1 )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 637 of file giaHash.c.

{ 
    if ( iLit0 < 2 )
        return iLit0 ? iLit1 : 0;
    if ( iLit1 < 2 )
        return iLit1 ? iLit0 : 0;
    if ( iLit0 == iLit1 )
        return iLit1;
    if ( iLit0 == Abc_LitNot(iLit1) )
        return 0;
    if ( iLit0 > iLit1 )
        iLit0 ^= iLit1, iLit1 ^= iLit0, iLit0 ^= iLit1;
    {
        int * pPlace = Gia_ManHashFind( p, iLit0, iLit1, -1 );
        if ( *pPlace ) 
            return Abc_Var2Lit( *pPlace, 0 );
        return -1;
    }
}

Here is the caller graph for this function:

Gia_ManHashDualMiter()

int Gia_ManHashDualMiter	(	Gia_Man_t *	p,
		Vec_Int_t *	vOuts )

Definition at line 809 of file giaHash.c.

{
    int i, iLit0, iLit1, iRes = 0;
    Vec_IntForEachEntryDouble( vOuts, iLit0, iLit1, i )
        iRes = Gia_ManHashOr( p, iRes, Gia_ManHashXor(p, iLit0, iLit1) );
    return iRes;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Gia_ManHashLookup()

int Gia_ManHashLookup	(	Gia_Man_t *	p,
		Gia_Obj_t *	p0,
		Gia_Obj_t *	p1 )

Definition at line 87 of file giaHash.c.

{
    int iLit0 = Gia_ObjToLit( p, p0 );
    int iLit1 = Gia_ObjToLit( p, p1 );
    return Gia_ManHashLookupInt( p, iLit0, iLit1 );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Gia_ManHashLookupInt()

int Gia_ManHashLookupInt	(	Gia_Man_t *	p,
		int	iLit0,
		int	iLit1 )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 81 of file giaHash.c.

{
    if ( iLit0 > iLit1 )
        iLit0 ^= iLit1, iLit1 ^= iLit0, iLit0 ^= iLit1;
    return Abc_Var2Lit( *Gia_ManHashFind( p, iLit0, iLit1, -1 ), 0 );
}

Here is the caller graph for this function:

Gia_ManHashMaj()

int Gia_ManHashMaj	(	Gia_Man_t *	p,
		int	iData0,
		int	iData1,
		int	iData2 )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 720 of file giaHash.c.

{ 
    int iTemp0 = Gia_ManHashOr( p, iData1, iData2 );
    int iTemp1 = Gia_ManHashAnd( p, iData0, iTemp0 );
    int iTemp2 = Gia_ManHashAnd( p, iData1, iData2 );
    return Gia_ManHashOr( p, iTemp1, iTemp2 );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Gia_ManHashMux()

int Gia_ManHashMux	(	Gia_Man_t *	p,
		int	iCtrl,
		int	iData1,
		int	iData0 )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 692 of file giaHash.c.

{ 
    if ( p->fGiaSimple )
        return Gia_ManHashOr(p, Gia_ManHashAnd(p, iCtrl, iData1), Gia_ManHashAnd(p, Abc_LitNot(iCtrl), iData0) );
    else
    {
        int iTemp0, iTemp1, fCompl = 0;
        if ( iData0 > iData1 )
            iData0 ^= iData1, iData1 ^= iData0, iData0 ^= iData1, iCtrl = Abc_LitNot(iCtrl);
        if ( Abc_LitIsCompl(iData1) )
            iData0 = Abc_LitNot(iData0), iData1 = Abc_LitNot(iData1), fCompl = 1;
        iTemp0 = Gia_ManHashAnd( p, Abc_LitNot(iCtrl), iData0 );
        iTemp1 = Gia_ManHashAnd( p, iCtrl, iData1 );
        return Abc_LitNotCond( Gia_ManHashAnd( p, Abc_LitNot(iTemp0), Abc_LitNot(iTemp1) ), !fCompl );
    }
}

Here is the call graph for this function:

Gia_ManHashMuxReal()

int Gia_ManHashMuxReal	(	Gia_Man_t *	p,
		int	iLitC,
		int	iLit1,
		int	iLit0 )

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

Synopsis [Hashes MUX gate.]

Description []

SideEffects []

SeeAlso []

Definition at line 521 of file giaHash.c.

{
    int fCompl = 0;
    assert( p->fAddStrash == 0 );
    if ( iLitC < 2 )
        return iLitC ? iLit1 : iLit0;
    if ( iLit0 < 2 )
        return iLit0 ? Gia_ManHashOr(p, Abc_LitNot(iLitC), iLit1) : Gia_ManHashAnd(p, iLitC, iLit1);
    if ( iLit1 < 2 )
        return iLit1 ? Gia_ManHashOr(p, iLitC, iLit0) : Gia_ManHashAnd(p, Abc_LitNot(iLitC), iLit0);
    assert( iLit0 > 1 && iLit1 > 1 && iLitC > 1 );
    if ( iLit0 == iLit1 )
        return iLit0;
    if ( iLitC == iLit0 || iLitC == Abc_LitNot(iLit1) )
        return Gia_ManHashAnd(p, iLit0, iLit1);
    if ( iLitC == iLit1 || iLitC == Abc_LitNot(iLit0) )
        return Gia_ManHashOr(p, iLit0, iLit1);
    if ( Abc_Lit2Var(iLit0) == Abc_Lit2Var(iLit1) )
        return Gia_ManHashXorReal( p, iLitC, iLit0 );
    if ( iLit0 > iLit1 )
        iLit0 ^= iLit1, iLit1 ^= iLit0, iLit0 ^= iLit1, iLitC = Abc_LitNot(iLitC);
    if ( Abc_LitIsCompl(iLit1) )
        iLit0 = Abc_LitNot(iLit0), iLit1 = Abc_LitNot(iLit1), fCompl = 1;
    {
        int *pPlace = Gia_ManHashFind( p, iLit0, iLit1, iLitC );
        if ( *pPlace )
        {
            p->nHashHit++;
            return Abc_Var2Lit( *pPlace, fCompl );
        }
        p->nHashMiss++;
        if ( Vec_IntSize(&p->vHash) < Vec_IntCap(&p->vHash) )
            *pPlace = Abc_Lit2Var( Gia_ManAppendMuxReal( p, iLitC, iLit1, iLit0 ) );
        else
        {
            int iNode = Gia_ManAppendMuxReal( p, iLitC, iLit1, iLit0 );
            pPlace = Gia_ManHashFind( p, iLit0, iLit1, iLitC );
            assert( *pPlace == 0 );
            *pPlace = Abc_Lit2Var( iNode );
        }
        return Abc_Var2Lit( *pPlace, fCompl );
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Gia_ManHashOr()

int Gia_ManHashOr	(	Gia_Man_t *	p,
		int	iLit0,
		int	iLit1 )

Definition at line 621 of file giaHash.c.

{ 
    return Abc_LitNot(Gia_ManHashAnd( p, Abc_LitNot(iLit0), Abc_LitNot(iLit1) ));
}

Here is the call graph for this function:

Gia_ManHashProfile()

void Gia_ManHashProfile

(

Gia_Man_t *

p

)

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

Synopsis [Profiles the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 207 of file giaHash.c.

{
    int iEntry;
    int i, Counter, Limit;
    printf( "Table size = %d. Entries = %d. ", Vec_IntSize(&p->vHTable), Gia_ManAndNum(p) );
    printf( "Hits = %d. Misses = %d.\n", (int)p->nHashHit, (int)p->nHashMiss );
    Limit = Abc_MinInt( 1000, Vec_IntSize(&p->vHTable) );
    for ( i = 0; i < Limit; i++ )
    {
        Counter = 0;
        for ( iEntry = Vec_IntEntry(&p->vHTable, i); 
              iEntry; 
              iEntry = iEntry? Vec_IntEntry(&p->vHash, iEntry) : 0 )
            Counter++;
        if ( Counter ) 
            printf( "%d ", Counter );
    }
    printf( "\n" );
}

Gia_ManHashResize()

void Gia_ManHashResize

(

Gia_Man_t *

p

)

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

Synopsis [Resizes the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 166 of file giaHash.c.

{
    int i, iThis, iNext, Counter, Counter2, * pPlace;
    Vec_Int_t vOld = p->vHTable;
    assert( Vec_IntSize(&vOld) > 0 );
    // replace the table
    Vec_IntZero( &p->vHTable );
    Vec_IntFill( &p->vHTable, Abc_PrimeCudd( 2 * Gia_ManAndNum(p) ), 0 ); 
    // rehash the entries from the old table
    Counter = 0;
    Vec_IntForEachEntry( &vOld, iThis, i )
        for ( iNext = Vec_IntEntry(&p->vHash, iThis);  
              iThis;  iThis = iNext,   
              iNext = Vec_IntEntry(&p->vHash, iThis)  )
        {
            Gia_Obj_t * pThis0 = Gia_ManObj( p, iThis );
            Vec_IntWriteEntry( &p->vHash, iThis, 0 );
            pPlace = Gia_ManHashFind( p, Gia_ObjFaninLit0(pThis0, iThis), Gia_ObjFaninLit1(pThis0, iThis), Gia_ObjFaninLit2p(p, pThis0) );
            assert( *pPlace == 0 ); // should not be there
            *pPlace = iThis;
            assert( *pPlace != 0 );
            Counter++;
        }
    Counter2 = Gia_ManAndNum(p) - Gia_ManBufNum(p);
    assert( Counter == Counter2 );
//    if ( p->fVerbose )
//        printf( "Resizing GIA hash table: %d -> %d.\n", Vec_IntSize(&vOld), Vec_IntSize(&p->vHTable) );
    Vec_IntErase( &vOld );
}

Here is the caller graph for this function:

Gia_ManHashStart()

void Gia_ManHashStart

(

Gia_Man_t *

p

)

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

Synopsis [Starts the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 125 of file giaHash.c.

{
    Gia_Obj_t * pObj;
    int * pPlace, i;
    Gia_ManHashAlloc( p );
    Gia_ManForEachAnd( p, pObj, i )
    {
        pPlace = Gia_ManHashFind( p, Gia_ObjFaninLit0(pObj, i), Gia_ObjFaninLit1(pObj, i), Gia_ObjFaninLit2(p, i) );
        assert( *pPlace == 0 );
        *pPlace = i;
    }
}

Here is the call graph for this function:

Gia_ManHashStop()

void Gia_ManHashStop

(

Gia_Man_t *

p

)

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

Synopsis [Stops the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 149 of file giaHash.c.

{
    Vec_IntErase( &p->vHTable );
    Vec_IntErase( &p->vHash );
}

Gia_ManHashXor()

int Gia_ManHashXor	(	Gia_Man_t *	p,
		int	iLit0,
		int	iLit1 )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 668 of file giaHash.c.

{ 
    if ( p->fGiaSimple )
        return Gia_ManHashOr(p, Gia_ManHashAnd(p, iLit0, Abc_LitNot(iLit1)), Gia_ManHashAnd(p, Abc_LitNot(iLit0), iLit1) );
    else
    {
        int fCompl = Abc_LitIsCompl(iLit0) ^ Abc_LitIsCompl(iLit1);
        int iTemp0 = Gia_ManHashAnd( p, Abc_LitRegular(iLit0), Abc_LitNot(Abc_LitRegular(iLit1)) );
        int iTemp1 = Gia_ManHashAnd( p, Abc_LitRegular(iLit1), Abc_LitNot(Abc_LitRegular(iLit0)) );
        return Abc_LitNotCond( Gia_ManHashAnd( p, Abc_LitNot(iTemp0), Abc_LitNot(iTemp1) ), !fCompl );
    }
}

Here is the call graph for this function:

Gia_ManHashXorReal()

int Gia_ManHashXorReal	(	Gia_Man_t *	p,
		int	iLit0,
		int	iLit1 )

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

Synopsis [Hashes XOR gate.]

Description []

SideEffects []

SeeAlso []

Definition at line 469 of file giaHash.c.

{ 
    int fCompl = 0;
    assert( p->fAddStrash == 0 );
    if ( iLit0 < 2 )
        return iLit0 ? Abc_LitNot(iLit1) : iLit1;
    if ( iLit1 < 2 )
        return iLit1 ? Abc_LitNot(iLit0) : iLit0;
    if ( iLit0 == iLit1 )
        return 0;
    if ( iLit0 == Abc_LitNot(iLit1) )
        return 1;
    if ( (p->nObjs & 0xFF) == 0 && 2 * Vec_IntSize(&p->vHTable) < Gia_ManAndNum(p) )
        Gia_ManHashResize( p );
    if ( iLit0 < iLit1 )
        iLit0 ^= iLit1, iLit1 ^= iLit0, iLit0 ^= iLit1;
    if ( Abc_LitIsCompl(iLit0) )
        iLit0 = Abc_LitNot(iLit0), fCompl ^= 1;
    if ( Abc_LitIsCompl(iLit1) )
        iLit1 = Abc_LitNot(iLit1), fCompl ^= 1;
    {
        int *pPlace = Gia_ManHashFind( p, iLit0, iLit1, -1 );
        if ( *pPlace )
        {
            p->nHashHit++;
            return Abc_Var2Lit( *pPlace, fCompl );
        }
        p->nHashMiss++;
        if ( Vec_IntSize(&p->vHash) < Vec_IntCap(&p->vHash) )
            *pPlace = Abc_Lit2Var( Gia_ManAppendXorReal( p, iLit0, iLit1 ) );
        else
        {
            int iNode = Gia_ManAppendXorReal( p, iLit0, iLit1 );
            pPlace = Gia_ManHashFind( p, iLit0, iLit1, -1 );
            assert( *pPlace == 0 );
            *pPlace = Abc_Lit2Var( iNode );
        }
        return Abc_Var2Lit( *pPlace, fCompl );
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

Gia_ManLatest()

int Gia_ManLatest	(	int *	pPerm,
		int	nVars,
		int	iPrev1,
		int	iPrev2,
		int	iPrev3 )

Definition at line 1017 of file giaHash.c.

{
    int i, Value = -1, iLate = -1;
    for ( i = 0; i < nVars; i++ )
        if ( Value < pPerm[i] && i != iPrev1 && i != iPrev2 && i != iPrev3 )
        {
            Value = pPerm[i];
            iLate = i;
        }
    return iLate;
}

Here is the caller graph for this function:

Gia_ManMultiCheck()

int Gia_ManMultiCheck	(	int *	pPerm,
		int	nPerm )

Definition at line 862 of file giaHash.c.

{
    int i;
    for ( i = 1; i < nPerm; i++ )
        if ( pPerm[i-1] <= pPerm[i] )
            return 0;
    return 1;
}

Gia_ManMultiInputPerm()

int Gia_ManMultiInputPerm	(	Gia_Man_t *	pNew,
		int *	pVars,
		int	nVars,
		int *	pPerm,
		int	fOr,
		int	fXor )

Definition at line 870 of file giaHash.c.

{
    int fPrint = 1;
    int i, iLit;
    if ( fPrint )
    {
        for ( i = 0; i < nVars; i++ )
            printf( "%d ", pPerm[i] );
        printf( "\n" );
    }
    while ( 1 )
    {
        for ( i = 1; i < nVars; i++ )
            if ( pPerm[i-1] >= pPerm[i] )
                break;
        if ( i == nVars )
            break;
        assert( pPerm[i-1] >= pPerm[i] );
        if ( pPerm[i-1] > pPerm[i] )
        {
            ABC_SWAP( int, pPerm[i-1], pPerm[i] );
            ABC_SWAP( int, pVars[i-1], pVars[i] );
        }
        else
        {
            assert( pPerm[i-1] == pPerm[i] );
            pPerm[i-1]++;
            if ( fXor )
                pVars[i-1] = Gia_ManHashXor( pNew, pVars[i-1], pVars[i] );
            else if ( fOr )
                pVars[i-1] = Gia_ManHashOr( pNew, pVars[i-1], pVars[i] );
            else
                pVars[i-1] = Gia_ManHashAnd( pNew, pVars[i-1], pVars[i] );
            for ( i = i+1; i < nVars; i++ )
            {
                pPerm[i-1] = pPerm[i];
                pVars[i-1] = pVars[i];
            }
            nVars--;
        }
        if ( fPrint )
        {
            for ( i = 0; i < nVars; i++ )
                printf( "%d ", pPerm[i] );
            printf( "\n" );
        }
    }
    iLit = pVars[0];
    for ( i = 1; i < nVars; i++ )
        if ( fXor )
            iLit = Gia_ManHashXor( pNew, iLit, pVars[i] );
        else if ( fOr )
            iLit = Gia_ManHashOr( pNew, iLit, pVars[i] );
        else
            iLit = Gia_ManHashAnd( pNew, iLit, pVars[i] );
    return iLit;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Gia_ManMultiInputTest()

Gia_Man_t * Gia_ManMultiInputTest

(

int

nBits

)

Definition at line 927 of file giaHash.c.

{
    Gia_Man_t * pNew;
    int i, iRes, * pPerm;
    int * pMulti = Gia_ManCollectLiterals( nBits );
    pNew = Gia_ManStart( 1000 );
    pNew->pName = Abc_UtilStrsav( "multi" );
    for ( i = 0; i < nBits; i++ )
        Gia_ManAppendCi( pNew );
    Gia_ManHashAlloc( pNew );
    pPerm = Gia_ManGenPerm2( nBits );
    //pPerm = Gia_ManGenZero( nBits );
    iRes = Gia_ManMultiInputPerm( pNew, pMulti, nBits, pPerm, 0, 0 );
    Gia_ManAppendCo( pNew, iRes );
    ABC_FREE( pPerm );
    ABC_FREE( pMulti );
    return pNew;
}

Here is the call graph for this function:

Gia_ManMuxTree_rec()

int Gia_ManMuxTree_rec	(	Gia_Man_t *	pNew,
		int *	pCtrl,
		int	nCtrl,
		int *	pData )

Definition at line 965 of file giaHash.c.

{
    int iLit0, iLit1;
    if ( nCtrl == 0 )
        return pData[0];
    iLit0 = Gia_ManMuxTree_rec( pNew, pCtrl, nCtrl-1, pData );
    iLit1 = Gia_ManMuxTree_rec( pNew, pCtrl, nCtrl-1, pData + (1<<(nCtrl-1)) );
    return Gia_ManHashMux( pNew, pCtrl[nCtrl-1], iLit1, iLit0 );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Gia_ManMuxTreeTest()

Gia_Man_t * Gia_ManMuxTreeTest

(

int

nBits

)

Definition at line 1116 of file giaHash.c.

{
    Gia_Man_t * pNew;
    int i, iLit, nVars = nBits + (1 << nBits);
    int * pPerm, * pTree = Gia_ManCollectLiterals( nVars );
    pNew = Gia_ManStart( 1000 );
    pNew->pName = Abc_UtilStrsav( "mux_tree" );
    for ( i = 0; i < nVars; i++ )
        Gia_ManAppendCi( pNew );
    Gia_ManHashAlloc( pNew );
    pPerm = Gia_ManGenPerm( nVars );
    //pPerm = Gia_ManGenZero( nVars );
    pPerm[nBits+1] = 100;
    pPerm[nBits+5] = 100;
    pPerm[nBits+4] = 100;
    Gia_ManUsePerm( pTree, nBits, pPerm );
    iLit = Gia_ManDecomp( pNew, pTree, nBits, pPerm );
    Gia_ManAppendCo( pNew, iLit );
    ABC_FREE( pPerm );
    ABC_FREE( pTree );
    return pNew;
}

Here is the call graph for this function:

Gia_ManRehash()

Gia_Man_t * Gia_ManRehash	(	Gia_Man_t *	p,
		int	fAddStrash )

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

Synopsis [Rehashes AIG.]

Description []

SideEffects []

SeeAlso []

Definition at line 739 of file giaHash.c.

{
    Gia_Man_t * pNew, * pTemp;
    Gia_Obj_t * pObj;
    int i;
    pNew = Gia_ManStart( Gia_ManObjNum(p) );
    pNew->pName = Abc_UtilStrsav( p->pName );
    pNew->pSpec = Abc_UtilStrsav( p->pSpec );
    pNew->fAddStrash = fAddStrash;
    Gia_ManHashAlloc( pNew );
    Gia_ManConst0(p)->Value = 0;
    Gia_ManForEachObj( p, pObj, i )
    {
        //if ( Gia_ObjIsBuf(pObj) )
        //    pObj->Value = Gia_ManAppendBuf( pNew, Gia_ObjFanin0Copy(pObj) );
        //else 
        if ( Gia_ObjIsAnd(pObj) )
            pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
        else if ( Gia_ObjIsCi(pObj) )
            pObj->Value = Gia_ManAppendCi( pNew );
        else if ( Gia_ObjIsCo(pObj) )
            pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
    }
    Gia_ManHashStop( pNew );
    pNew->fAddStrash = 0;
    Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
//    printf( "Top gate is %s\n", Gia_ObjFaninC0(Gia_ManCo(pNew, 0))? "OR" : "AND" );
    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:

Gia_ManUsePerm()

void Gia_ManUsePerm	(	int *	pTree,
		int	nBits,
		int *	pPerm )

Definition at line 974 of file giaHash.c.

{
    int fPrint = 0;
    int i, k, m, nVars = nBits + (1 << nBits);
    if ( fPrint )
    {
        for ( i = 0; i < nVars; i++ )
            printf( "%d ", pPerm[i] );
        printf( "\n" );
    }
    for ( i = 0; i < nBits; i++ )
    {
        for ( k = i+1; k < nBits; k++ )
            if ( pPerm[i] > pPerm[k] )
                break;
        if ( k == nBits )
            break;
        assert( pPerm[i] > pPerm[k] );
        ABC_SWAP( int, pPerm[i], pPerm[k] );
        ABC_SWAP( int, pTree[i], pTree[k] );
        for ( m = 0; m < (1 << nBits); m++ )
            if ( ((m >> i) & 1) && !((m >> k) & 1) )
            {
                ABC_SWAP( int, pTree[nBits+m], pTree[nBits+(m^(1<<i)^(1<<k))] );
                ABC_SWAP( int, pPerm[nBits+m], pPerm[nBits+(m^(1<<i)^(1<<k))] );
            }
    }
    if ( fPrint )
    {
        for ( i = 0; i < nVars; i++ )
            printf( "%d ", pPerm[i] );
        printf( "\n" );
    }
}

Here is the caller graph for this function: