giaCof.c File Reference

#include <math.h>
#include "gia.h"

Go to the source code of this file.

Data Structures
struct	Cof_Fan_t_
struct	Cof_Obj_t_
struct	Cof_Man_t_

Macros
#define	Cof_ManForEachObj(p, pObj, i)   for ( i = 0; (i < p->nObjData) && (pObj = Cof_ManObj(p,i)); i += Cof_ObjSize(pObj) )
#define	Cof_ManForEachNode(p, pObj, i)   for ( i = 0; (i < p->nObjData) && (pObj = Cof_ManObj(p,i)); i += Cof_ObjSize(pObj) ) if ( Cof_ObjIsTerm(pObj) ) {} else
#define	Cof_ObjForEachFanin(pObj, pNext, i)   for ( i = 0; (i < (int)pObj->nFanins) && (pNext = Cof_ObjFanin(pObj,i)); i++ )
#define	Cof_ObjForEachFanout(pObj, pNext, i)   for ( i = 0; (i < (int)pObj->nFanouts) && (pNext = Cof_ObjFanout(pObj,i)); i++ )

Typedefs
typedef typedefABC_NAMESPACE_IMPL_START struct Cof_Fan_t_	Cof_Fan_t
	DECLARATIONS ///. More...
typedef struct Cof_Obj_t_	Cof_Obj_t
typedef struct Cof_Man_t_	Cof_Man_t

Functions
static unsigned	Gia_ObjHandle (Gia_Obj_t *pObj)
static int	Cof_ObjLevel (Cof_Man_t *p, Cof_Obj_t *pObj)
static unsigned	Cof_ObjHandle (Cof_Man_t *p, Cof_Obj_t *pObj)
static unsigned	Cof_ObjHandleDiff (Cof_Obj_t *pObj, Cof_Obj_t *pFanin)
static int	Cof_ObjIsTerm (Cof_Obj_t *pObj)
static int	Cof_ObjIsCi (Cof_Obj_t *pObj)
static int	Cof_ObjIsCo (Cof_Obj_t *pObj)
static int	Cof_ObjIsNode (Cof_Obj_t *pObj)
static int	Cof_ObjIsConst0 (Cof_Obj_t *pObj)
static int	Cof_ObjFaninNum (Cof_Obj_t *pObj)
static int	Cof_ObjFanoutNum (Cof_Obj_t *pObj)
static int	Cof_ObjSize (Cof_Obj_t *pObj)
static Cof_Obj_t *	Cof_ManObj (Cof_Man_t *p, unsigned iHandle)
static Cof_Obj_t *	Cof_ObjFanin (Cof_Obj_t *pObj, int i)
static Cof_Obj_t *	Cof_ObjFanout (Cof_Obj_t *pObj, int i)
static int	Cof_ManObjNum (Cof_Man_t *p)
static int	Cof_ManNodeNum (Cof_Man_t *p)
static void	Cof_ManResetTravId (Cof_Man_t *p)
static void	Cof_ManIncrementTravId (Cof_Man_t *p)
static void	Cof_ObjSetTravId (Cof_Obj_t *pObj, int TravId)
static void	Cof_ObjSetTravIdCurrent (Cof_Man_t *p, Cof_Obj_t *pObj)
static void	Cof_ObjSetTravIdPrevious (Cof_Man_t *p, Cof_Obj_t *pObj)
static int	Cof_ObjIsTravIdCurrent (Cof_Man_t *p, Cof_Obj_t *pObj)
static int	Cof_ObjIsTravIdPrevious (Cof_Man_t *p, Cof_Obj_t *pObj)
Cof_Man_t *	Cof_ManCreateLogicSimple (Gia_Man_t *pGia)
	FUNCTION DEFINITIONS ///. More...
void	Cof_ManStop (Cof_Man_t *p)
int	Cof_ManTfoSize_rec (Cof_Man_t *p, Cof_Obj_t *pObj)
int	Cof_ManTfoSize (Cof_Man_t *p, Cof_Obj_t **ppObjs, int nObjs)
int	Cof_ManTfiSize_rec (Cof_Man_t *p, Cof_Obj_t *pObj)
int	Cof_ManTfiSize (Cof_Man_t *p, Cof_Obj_t **ppObjs, int nObjs)
int	Cof_ManSuppSize_rec (Cof_Man_t *p, Cof_Obj_t *pObj)
int	Cof_ManSuppSize (Cof_Man_t *p, Cof_Obj_t **ppObjs, int nObjs)
void	Cof_ManCleanValue (Cof_Man_t *p)
void	Cof_ManInsertEntry_rec (Vec_Ptr_t *vNodes, Cof_Obj_t *pNode, int nNodeMax)
Vec_Ptr_t *	Cof_ManCollectHighFanout (Cof_Man_t *p, int nNodes)
int	Cof_ManCountRemoved (Cof_Man_t *p, Cof_Obj_t *pRoot, int fConst1)
void	Cof_ManPrintHighFanoutOne (Cof_Man_t *p, Cof_Obj_t *pObj)
void	Cof_ManPrintHighFanout (Cof_Man_t *p, int nNodes)
int	Cof_NodeDeref_rec (Cof_Obj_t *pNode)
int	Cof_NodeRef_rec (Cof_Obj_t *pNode)
static int	Cof_ObjMffcSize (Cof_Obj_t *pNode)
void	Cof_ManPrintFanio (Cof_Man_t *p)
void	Gia_ManPrintFanio (Gia_Man_t *pGia, int nNodes)
Gia_Man_t *	Gia_ManDupCofInt (Gia_Man_t *p, int iVar)
Gia_Man_t *	Gia_ManDupCof (Gia_Man_t *p, int iVar)
Vec_Int_t *	Gia_ManCofVars (Gia_Man_t *p, int nFanLim)
Vec_Int_t *	Gia_ManTransfer (Gia_Man_t *pAig, Gia_Man_t *pCof, Gia_Man_t *pNew, Vec_Int_t *vSigs)
Gia_Man_t *	Gia_ManDupCofAllInt (Gia_Man_t *p, Vec_Int_t *vSigs, int fVerbose)
Gia_Man_t *	Gia_ManDupCofAll (Gia_Man_t *p, int nFanLim, int fVerbose)

Macro Definition Documentation

#define Cof_ManForEachNode	(		p,
			pObj,
			i
	)		for ( i = 0; (i < p->nObjData) && (pObj = Cof_ManObj(p,i)); i += Cof_ObjSize(pObj) ) if ( Cof_ObjIsTerm(pObj) ) {} else

Definition at line 104 of file giaCof.c.

#define Cof_ManForEachObj	(		p,
			pObj,
			i
	)		for ( i = 0; (i < p->nObjData) && (pObj = Cof_ManObj(p,i)); i += Cof_ObjSize(pObj) )

Definition at line 102 of file giaCof.c.

#define Cof_ObjForEachFanin	(		pObj,
			pNext,
			i
	)		for ( i = 0; (i < (int)pObj->nFanins) && (pNext = Cof_ObjFanin(pObj,i)); i++ )

Definition at line 106 of file giaCof.c.

#define Cof_ObjForEachFanout	(		pObj,
			pNext,
			i
	)		for ( i = 0; (i < (int)pObj->nFanouts) && (pNext = Cof_ObjFanout(pObj,i)); i++ )

Definition at line 108 of file giaCof.c.

Typedef Documentation

typedef typedefABC_NAMESPACE_IMPL_START struct Cof_Fan_t_ Cof_Fan_t

DECLARATIONS ///.

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

FileName [giaCof.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Scalable AIG package.]

Synopsis [Cofactor estimation procedures.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id:

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

]

Definition at line 31 of file giaCof.c.

typedef struct Cof_Man_t_ Cof_Man_t

Definition at line 55 of file giaCof.c.

typedef struct Cof_Obj_t_ Cof_Obj_t

Definition at line 38 of file giaCof.c.

Function Documentation

void Cof_ManCleanValue

(

Cof_Man_t *

p

)

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

Synopsis [Cleans the value.]

Description []

SideEffects []

SeeAlso []

Definition at line 369 of file giaCof.c.

{
    Cof_Obj_t * pObj;
    int i;
    Cof_ManForEachObj( p, pObj, i )
        pObj->Value = 0;
}

Vec_Ptr_t* Cof_ManCollectHighFanout	(	Cof_Man_t *	p,
		int	nNodes
	)

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

Synopsis [Returns sorted array of node handles with largest fanout.]

Description []

SideEffects []

SeeAlso []

Definition at line 422 of file giaCof.c.

{
    Vec_Ptr_t * vNodes;
    Cof_Obj_t * pObj;
    int i;
    vNodes = Vec_PtrAlloc( nNodes );
    Cof_ManForEachObj( p, pObj, i )
        if ( Cof_ObjIsCi(pObj) || Cof_ObjIsNode(pObj) )
            Cof_ManInsertEntry_rec( vNodes, pObj, nNodes );
    return vNodes;
}

int Cof_ManCountRemoved	(	Cof_Man_t *	p,
		Cof_Obj_t *	pRoot,
		int	fConst1
	)

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

Synopsis [Returns sorted array of node handles with largest fanout.]

Description []

SideEffects []

SeeAlso []

Definition at line 445 of file giaCof.c.

{
    Gia_Obj_t * pNextGia;
    Cof_Obj_t * pTemp, * pNext, * pFanin0, * pFanin1;
    int Counter = 0, LevelStart, LevelNext;
    int i, k, iHandle, iLit0, iLit1, iNextNew;
    // restart the trav ids
    Cof_ManIncrementTravId( p );
    Cof_ObjSetTravIdCurrent( p, pRoot );
    // add the node to the queue
    LevelStart = Cof_ObjLevel(p, pRoot);
    assert( p->pLevels[LevelStart] == 0 );
    pRoot->iNext = 0;
    p->pLevels[LevelStart] = Cof_ObjHandle( p, pRoot );
    // set the new literal
    pRoot->iLit = Abc_Var2Lit( 0, fConst1 );
    // process nodes in the levelized order
    for ( i = LevelStart; i < p->nLevels; i++ )
    {
        for ( iHandle = p->pLevels[i]; 
              iHandle && (pTemp = Cof_ManObj(p, iHandle)); 
              iHandle = pTemp->iNext )
        {
            assert( pTemp->Id != Abc_Lit2Var(pTemp->iLit) );
            Cof_ObjForEachFanout( pTemp, pNext, k )
            {
                if ( Cof_ObjIsCo(pNext) )
                    continue;
                if ( Cof_ObjIsTravIdCurrent(p, pNext) )
                    continue;
                pFanin0 = Cof_ObjFanin( pNext, 0 );
                pFanin1 = Cof_ObjFanin( pNext, 1 );
                assert( pFanin0 == pTemp || pFanin1 == pTemp );
                pNextGia = Gia_ManObj( p->pGia, pNext->Id );
                if ( Cof_ObjIsTravIdCurrent(p, pFanin0) )
                    iLit0 = Abc_LitNotCond( pFanin0->iLit, Gia_ObjFaninC0(pNextGia) );
                else
                    iLit0 = Gia_ObjFaninLit0( pNextGia, pNext->Id );
                if ( Cof_ObjIsTravIdCurrent(p, pFanin1) )
                    iLit1 = Abc_LitNotCond( pFanin1->iLit, Gia_ObjFaninC1(pNextGia) );
                else
                    iLit1 = Gia_ObjFaninLit1( pNextGia, pNext->Id );
                iNextNew = Gia_ManHashAndTry( p->pGia, iLit0, iLit1 );
                if ( iNextNew == -1 )
                    continue;
                Cof_ObjSetTravIdCurrent(p, pNext);
                // set the new literal
                pNext->iLit = iNextNew;
                // add it to be processed
                LevelNext = Cof_ObjLevel( p, pNext );
                assert( LevelNext > i && LevelNext < p->nLevels );
                pNext->iNext = p->pLevels[LevelNext];
                p->pLevels[LevelNext] = Cof_ObjHandle( p, pNext );
                Counter++;
            }
        }
        p->pLevels[i] = 0;
    }
    return Counter;
}

Cof_Man_t* Cof_ManCreateLogicSimple

(

Gia_Man_t *

pGia

)

FUNCTION DEFINITIONS ///.

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

Synopsis [Creates logic network isomorphic to the given AIG.]

Description []

SideEffects []

SeeAlso []

Definition at line 126 of file giaCof.c.

{
    Cof_Man_t * p;
    Cof_Obj_t * pObjLog, * pFanLog;
    Gia_Obj_t * pObj;
    int * pMuxRefs;
    int i, iHandle = 0;
    p = ABC_CALLOC( Cof_Man_t, 1 );
    p->pGia = pGia;
    p->vCis = Vec_IntAlloc( Gia_ManCiNum(pGia) );
    p->vCos = Vec_IntAlloc( Gia_ManCoNum(pGia) );
    p->nObjData = (sizeof(Cof_Obj_t) / 4) * Gia_ManObjNum(pGia) + 4 * Gia_ManAndNum(pGia) + 2 * Gia_ManCoNum(pGia);
    p->pObjData = ABC_CALLOC( int, p->nObjData );
    ABC_FREE( pGia->pRefs );
    Gia_ManCreateRefs( pGia );
    Gia_ManForEachObj( pGia, pObj, i )
    {
        pObj->Value = iHandle;
        pObjLog = Cof_ManObj( p, iHandle );
        pObjLog->nFanins  = 0;
        pObjLog->nFanouts = Gia_ObjRefNum( pGia, pObj );
        pObjLog->Id       = i;
        pObjLog->Value    = 0;
        if ( Gia_ObjIsAnd(pObj) )
        {
            pFanLog = Cof_ManObj( p, Gia_ObjHandle(Gia_ObjFanin0(pObj)) ); 
            pFanLog->Fanios[pFanLog->nFanins + pFanLog->Value++].iFan = 
                pObjLog->Fanios[pObjLog->nFanins].iFan = Cof_ObjHandleDiff( pObjLog, pFanLog );
            pObjLog->Fanios[pObjLog->nFanins++].fCompl = Gia_ObjFaninC0(pObj);

            pFanLog = Cof_ManObj( p, Gia_ObjHandle(Gia_ObjFanin1(pObj)) ); 
            pFanLog->Fanios[pFanLog->nFanins + pFanLog->Value++].iFan = 
                pObjLog->Fanios[pObjLog->nFanins].iFan = Cof_ObjHandleDiff( pObjLog, pFanLog );
            pObjLog->Fanios[pObjLog->nFanins++].fCompl = Gia_ObjFaninC1(pObj);
            p->nNodes++;
        }
        else if ( Gia_ObjIsCo(pObj) )
        {
            pFanLog = Cof_ManObj( p, Gia_ObjHandle(Gia_ObjFanin0(pObj)) ); 
            pFanLog->Fanios[pFanLog->nFanins + pFanLog->Value++].iFan = 
                pObjLog->Fanios[pObjLog->nFanins].iFan = Cof_ObjHandleDiff( pObjLog, pFanLog );
            pObjLog->Fanios[pObjLog->nFanins++].fCompl = Gia_ObjFaninC0(pObj);

            pObjLog->fTerm = 1;
            Vec_IntPush( p->vCos, iHandle );
        }
        else if ( Gia_ObjIsCi(pObj) )
        {
            pObjLog->fTerm = 1;
            Vec_IntPush( p->vCis, iHandle );
        }
        iHandle += Cof_ObjSize( pObjLog );
        p->nObjs++;
    }
    assert( iHandle == p->nObjData );
    pMuxRefs = Gia_ManCreateMuxRefs( pGia );
    Gia_ManForEachObj( pGia, pObj, i )
    {
        pObjLog = Cof_ManObj( p, Gia_ObjHandle(pObj) );
        assert( pObjLog->nFanouts == pObjLog->Value );
        pObjLog->nFanoutsM = pMuxRefs[i];
    }
    ABC_FREE( pMuxRefs );
    return p;
}

static void Cof_ManIncrementTravId ( Cof_Man_t *  p )

inlinestatic

Definition at line 95 of file giaCof.c.

{ p->nTravIds++;                                      }

void Cof_ManInsertEntry_rec	(	Vec_Ptr_t *	vNodes,
		Cof_Obj_t *	pNode,
		int	nNodeMax
	)

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

Synopsis [Returns sorted array of node handles with largest fanout.]

Description []

SideEffects []

SeeAlso []

Definition at line 388 of file giaCof.c.

{
    Cof_Obj_t * pLast;
    if ( Vec_PtrSize(vNodes) == 0 )
    {
        Vec_PtrPush(vNodes, pNode);
        return;
    }
    pLast = (Cof_Obj_t *)Vec_PtrPop(vNodes);
    if ( Cof_ObjFanoutNum(pLast) < Cof_ObjFanoutNum(pNode) )
    {
        Cof_ManInsertEntry_rec( vNodes, pNode, nNodeMax );
        if ( Vec_PtrSize(vNodes) < nNodeMax )
            Vec_PtrPush( vNodes, pLast );
    }
    else
    {
        Vec_PtrPush( vNodes, pLast );
        if ( Vec_PtrSize(vNodes) < nNodeMax )
            Vec_PtrPush( vNodes, pNode );
    }
}

static int Cof_ManNodeNum ( Cof_Man_t *  p )

inlinestatic

Definition at line 92 of file giaCof.c.

{ return p->nNodes;                                   } 

static Cof_Obj_t* Cof_ManObj ( Cof_Man_t *  p, unsigned  iHandle  )

inlinestatic

Definition at line 87 of file giaCof.c.

{ return (Cof_Obj_t *)(p->pObjData + iHandle);        } 

static int Cof_ManObjNum ( Cof_Man_t *  p )

inlinestatic

Definition at line 91 of file giaCof.c.

{ return p->nObjs;                                    } 

void Cof_ManPrintFanio

(

Cof_Man_t *

p

)

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

Synopsis [Prints the distribution of fanins/fanouts in the network.]

Description []

SideEffects []

SeeAlso []

Definition at line 605 of file giaCof.c.

{
    char Buffer[100];
    Cof_Obj_t * pNode;
    Vec_Int_t * vFanins, * vFanouts, * vMffcs;
    int nFanins, nFanouts, nMffcs, nFaninsMax, nFanoutsMax, nMffcsMax, nFaninsAll, nFanoutsAll, nMffcsAll;
    int i, k, nSizeMax, nMffcNodes = 0;

    // determine the largest fanin and fanout
    nFaninsMax = nFanoutsMax = nMffcsMax = 0;
    nFaninsAll = nFanoutsAll = nMffcsAll = 0;
    Cof_ManForEachNode( p, pNode, i )
    {
        if ( i == 0 ) continue;
        nFanins  = Cof_ObjFaninNum(pNode);
        nFanouts = Cof_ObjFanoutNum(pNode);
        nMffcs   = pNode->nFanouts > 1 ? Cof_ObjMffcSize(pNode) : 0;
        nFaninsAll  += nFanins;
        nFanoutsAll += nFanouts;
        nMffcsAll   += nMffcs;
        nFaninsMax   = Abc_MaxInt( nFaninsMax,  nFanins );
        nFanoutsMax  = Abc_MaxInt( nFanoutsMax, nFanouts );
        nMffcsMax    = Abc_MaxInt( nMffcsMax,   nMffcs );
    }

    // allocate storage for fanin/fanout numbers
    nSizeMax = Abc_MaxInt( 10 * (Abc_Base10Log(nFaninsMax) + 1), 10 * (Abc_Base10Log(nFanoutsMax) + 1) );
    nSizeMax = Abc_MaxInt( 10 * (Abc_Base10Log(nMffcsMax) + 1),  nSizeMax );
    vFanins  = Vec_IntStart( nSizeMax );
    vFanouts = Vec_IntStart( nSizeMax );
    vMffcs   = Vec_IntStart( nSizeMax );

    // count the number of fanins and fanouts
    Cof_ManForEachNode( p, pNode, i )
    {
        if ( i == 0 ) continue;
        nFanins  = Cof_ObjFaninNum(pNode);
        nFanouts = Cof_ObjFanoutNum(pNode);
        nMffcs   = pNode->nFanouts > 1 ? Cof_ObjMffcSize(pNode) : 0;

        if ( nFanins < 10 )
            Vec_IntAddToEntry( vFanins, nFanins, 1 );
        else if ( nFanins < 100 )
            Vec_IntAddToEntry( vFanins, 10 + nFanins/10, 1 );
        else if ( nFanins < 1000 )
            Vec_IntAddToEntry( vFanins, 20 + nFanins/100, 1 );
        else if ( nFanins < 10000 )
            Vec_IntAddToEntry( vFanins, 30 + nFanins/1000, 1 );
        else if ( nFanins < 100000 )
            Vec_IntAddToEntry( vFanins, 40 + nFanins/10000, 1 );
        else if ( nFanins < 1000000 )
            Vec_IntAddToEntry( vFanins, 50 + nFanins/100000, 1 );
        else if ( nFanins < 10000000 )
            Vec_IntAddToEntry( vFanins, 60 + nFanins/1000000, 1 );

        if ( nFanouts < 10 )
            Vec_IntAddToEntry( vFanouts, nFanouts, 1 );
        else if ( nFanouts < 100 )
            Vec_IntAddToEntry( vFanouts, 10 + nFanouts/10, 1 );
        else if ( nFanouts < 1000 )
            Vec_IntAddToEntry( vFanouts, 20 + nFanouts/100, 1 );
        else if ( nFanouts < 10000 )
            Vec_IntAddToEntry( vFanouts, 30 + nFanouts/1000, 1 );
        else if ( nFanouts < 100000 )
            Vec_IntAddToEntry( vFanouts, 40 + nFanouts/10000, 1 );
        else if ( nFanouts < 1000000 )
            Vec_IntAddToEntry( vFanouts, 50 + nFanouts/100000, 1 );
        else if ( nFanouts < 10000000 )
            Vec_IntAddToEntry( vFanouts, 60 + nFanouts/1000000, 1 );
       
        if ( nMffcs == 0 )
            continue;
        nMffcNodes++;

        if ( nMffcs < 10 )
            Vec_IntAddToEntry( vMffcs, nMffcs, 1 );
        else if ( nMffcs < 100 )
            Vec_IntAddToEntry( vMffcs, 10 + nMffcs/10, 1 );
        else if ( nMffcs < 1000 )
            Vec_IntAddToEntry( vMffcs, 20 + nMffcs/100, 1 );
        else if ( nMffcs < 10000 )
            Vec_IntAddToEntry( vMffcs, 30 + nMffcs/1000, 1 );
        else if ( nMffcs < 100000 )
            Vec_IntAddToEntry( vMffcs, 40 + nMffcs/10000, 1 );
        else if ( nMffcs < 1000000 )
            Vec_IntAddToEntry( vMffcs, 50 + nMffcs/100000, 1 );
        else if ( nMffcs < 10000000 )
            Vec_IntAddToEntry( vMffcs, 60 + nMffcs/1000000, 1 );
    }

    printf( "The distribution of fanins, fanouts. and MFFCs in the network:\n" );
    printf( "         Number    Nodes with fanin   Nodes with fanout   Nodes with MFFC\n" );

    for ( k = 0; k < nSizeMax; k++ )
    {
        if ( vFanins->pArray[k] == 0 && vFanouts->pArray[k] == 0 && vMffcs->pArray[k] == 0 )
            continue;
        if ( k < 10 )
            printf( "%15d : ", k );
        else
        {
            sprintf( Buffer, "%d - %d", (int)pow((double)10, k/10) * (k%10), (int)pow((double)10, k/10) * (k%10+1) - 1 ); 
            printf( "%15s : ", Buffer );
        }
        if ( vFanins->pArray[k] == 0 )
            printf( "              " );
        else
            printf( "%11d   ", vFanins->pArray[k] );
        printf( "    " );
        if ( vFanouts->pArray[k] == 0 )
            printf( "              " );
        else
            printf( "%12d  ", vFanouts->pArray[k] );
        printf( "    " );
        if ( vMffcs->pArray[k] == 0 )
            printf( "               " );
        else
            printf( "  %12d  ", vMffcs->pArray[k] );
        printf( "\n" );
    }
    Vec_IntFree( vFanins );
    Vec_IntFree( vFanouts );
    Vec_IntFree( vMffcs );

    printf( "Fanins: Max = %d. Ave = %.2f.  Fanouts: Max = %d. Ave =  %.2f.  MFFCs: Max = %d. Ave =  %.2f.\n", 
        nFaninsMax,  1.0*nFaninsAll /Cof_ManNodeNum(p), 
        nFanoutsMax, 1.0*nFanoutsAll/Cof_ManNodeNum(p), 
        nMffcsMax,   1.0*nMffcsAll  /nMffcNodes  );
}

void Cof_ManPrintHighFanout	(	Cof_Man_t *	p,
		int	nNodes
	)

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

Synopsis [Returns sorted array of node handles with largest fanout.]

Description []

SideEffects []

SeeAlso []

Definition at line 541 of file giaCof.c.

{
    Vec_Ptr_t * vNodes;
    Cof_Obj_t * pObj;
    int i;
    vNodes = Cof_ManCollectHighFanout( p, nNodes );
    Vec_PtrForEachEntry( Cof_Obj_t *, vNodes, pObj, i )
        Cof_ManPrintHighFanoutOne( p, pObj );
    Vec_PtrFree( vNodes );
}

void Cof_ManPrintHighFanoutOne	(	Cof_Man_t *	p,
		Cof_Obj_t *	pObj
	)

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

Synopsis [Returns sorted array of node handles with largest fanout.]

Description []

SideEffects []

SeeAlso []

Definition at line 517 of file giaCof.c.

{
    printf( "%7d : ",     pObj->Id );
    printf( "i/o/c =%2d %5d %5d  ",  Cof_ObjFaninNum(pObj), Cof_ObjFanoutNum(pObj), 2*pObj->nFanoutsM );
    printf( "l =%4d  ",   Cof_ObjLevel(p, pObj) );
    printf( "s =%5d  ",   Cof_ManSuppSize(p, &pObj, 1) );
    printf( "TFI =%7d  ", Cof_ManTfiSize(p, &pObj, 1) );
    printf( "TFO =%7d  ", Cof_ManTfoSize(p, &pObj, 1) );
    printf( "C0 =%6d  ",  Cof_ManCountRemoved(p, pObj, 0) );
    printf( "C1 =%6d",    Cof_ManCountRemoved(p, pObj, 1) );
    printf( "\n" );
}

static void Cof_ManResetTravId ( Cof_Man_t *  p )

inlinestatic

Definition at line 94 of file giaCof.c.

{ extern void Cof_ManCleanValue( Cof_Man_t * p ); Cof_ManCleanValue( p ); p->nTravIds = 1;  }

void Cof_ManStop

(

Cof_Man_t *

p

)

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

Synopsis [Creates logic network isomorphic to the given AIG.]

Description []

SideEffects []

SeeAlso []

Definition at line 203 of file giaCof.c.

{
    Vec_IntFree( p->vCis );
    Vec_IntFree( p->vCos );
    ABC_FREE( p->pObjData );
    ABC_FREE( p->pLevels );
    ABC_FREE( p );
}

int Cof_ManSuppSize	(	Cof_Man_t *	p,
		Cof_Obj_t **	ppObjs,
		int	nObjs
	)

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

Synopsis [Collects support nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 345 of file giaCof.c.

{
    int i, Counter = 0; 
    Cof_ManIncrementTravId( p );
    for ( i = 0; i < nObjs; i++ )
        if ( Cof_ObjIsCo(ppObjs[i]) )
            Counter += Cof_ManSuppSize_rec( p, Cof_ObjFanin(ppObjs[i],0) );
        else
            Counter += Cof_ManSuppSize_rec( p, ppObjs[i] );
    return Counter;
}

int Cof_ManSuppSize_rec	(	Cof_Man_t *	p,
		Cof_Obj_t *	pObj
	)

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

Synopsis [Collects support nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 319 of file giaCof.c.

{
    Cof_Obj_t * pNext;
    unsigned i, Counter = 0;
    if ( Cof_ObjIsTravIdCurrent(p, pObj) )
        return 0;
    Cof_ObjSetTravIdCurrent(p, pObj);
    if ( Cof_ObjIsCi(pObj) )
        return 1;
    assert( Cof_ObjIsNode(pObj) );
    Cof_ObjForEachFanin( pObj, pNext, i )
        Counter += Cof_ManSuppSize_rec( p, pNext );
    return Counter;
}

int Cof_ManTfiSize	(	Cof_Man_t *	p,
		Cof_Obj_t **	ppObjs,
		int	nObjs
	)

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

Synopsis [Collects support nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 296 of file giaCof.c.

{
    int i, Counter = 0; 
    Cof_ManIncrementTravId( p );
    for ( i = 0; i < nObjs; i++ )
        if ( Cof_ObjIsCo(ppObjs[i]) )
            Counter += Cof_ManTfiSize_rec( p, Cof_ObjFanin(ppObjs[i],0) );
        else
            Counter += Cof_ManTfiSize_rec( p, ppObjs[i] );
    return Counter;
}

int Cof_ManTfiSize_rec	(	Cof_Man_t *	p,
		Cof_Obj_t *	pObj
	)

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

Synopsis [Collects support nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 270 of file giaCof.c.

{
    Cof_Obj_t * pNext;
    unsigned i, Counter = 0;
    if ( Cof_ObjIsTravIdCurrent(p, pObj) )
        return 0;
    Cof_ObjSetTravIdCurrent(p, pObj);
    if ( Cof_ObjIsCi(pObj) )
        return 0;
    assert( Cof_ObjIsNode(pObj) );
    Cof_ObjForEachFanin( pObj, pNext, i )
        Counter += Cof_ManTfiSize_rec( p, pNext );
    return 1 + Counter;
}

int Cof_ManTfoSize	(	Cof_Man_t *	p,
		Cof_Obj_t **	ppObjs,
		int	nObjs
	)

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

Synopsis [Collects support nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 250 of file giaCof.c.

{
    int i, Counter = 0; 
    Cof_ManIncrementTravId( p );
    for ( i = 0; i < nObjs; i++ )
        Counter += Cof_ManTfoSize_rec( p, ppObjs[i] ) - 1;
    return Counter;
}

int Cof_ManTfoSize_rec	(	Cof_Man_t *	p,
		Cof_Obj_t *	pObj
	)

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

Synopsis [Collects support nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 224 of file giaCof.c.

{
    Cof_Obj_t * pNext;
    unsigned i, Counter = 0;
    if ( Cof_ObjIsTravIdCurrent(p, pObj) )
        return 0;
    Cof_ObjSetTravIdCurrent(p, pObj);
    if ( Cof_ObjIsCo(pObj) )
        return 0;
    assert( Cof_ObjIsCi(pObj) || Cof_ObjIsNode(pObj) );
    Cof_ObjForEachFanout( pObj, pNext, i )
        Counter += Cof_ManTfoSize_rec( p, pNext );
    return 1 + Counter;
}

int Cof_NodeDeref_rec

(

Cof_Obj_t *

pNode

)

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

Synopsis [Compute MFFC size of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 564 of file giaCof.c.

{
    if ( pNode->nFanins == 0 )
        return 0;
    if ( --pNode->nFanouts > 0 )
        return 0;
    return 1 + Cof_NodeDeref_rec( Cof_ObjFanin(pNode, 0) )
             + Cof_NodeDeref_rec( Cof_ObjFanin(pNode, 1) );
}

int Cof_NodeRef_rec

(

Cof_Obj_t *

pNode

)

Definition at line 573 of file giaCof.c.

{
    if ( pNode->nFanins == 0 )
        return 0;
    if ( pNode->nFanouts++ > 0 )
        return 0;
    return 1 + Cof_NodeRef_rec( Cof_ObjFanin(pNode, 0) )
             + Cof_NodeRef_rec( Cof_ObjFanin(pNode, 1) );
}

static Cof_Obj_t* Cof_ObjFanin ( Cof_Obj_t *  pObj, int  i  )

inlinestatic

Definition at line 88 of file giaCof.c.

{ return (Cof_Obj_t *)(((int *)pObj) - pObj->Fanios[i].iFan);               } 

static int Cof_ObjFaninNum ( Cof_Obj_t *  pObj )

inlinestatic

Definition at line 83 of file giaCof.c.

{ return pObj->nFanins;                               } 

static Cof_Obj_t* Cof_ObjFanout ( Cof_Obj_t *  pObj, int  i  )

inlinestatic

Definition at line 89 of file giaCof.c.

{ return (Cof_Obj_t *)(((int *)pObj) + pObj->Fanios[pObj->nFanins+i].iFan); } 

static int Cof_ObjFanoutNum ( Cof_Obj_t *  pObj )

inlinestatic

Definition at line 84 of file giaCof.c.

{ return pObj->nFanouts;                              } 

static unsigned Cof_ObjHandle ( Cof_Man_t *  p, Cof_Obj_t *  pObj  )

inlinestatic

Definition at line 74 of file giaCof.c.

{ return (unsigned)(((int *)pObj) - p->pObjData);     } 

static unsigned Cof_ObjHandleDiff ( Cof_Obj_t *  pObj, Cof_Obj_t *  pFanin  )

inlinestatic

Definition at line 75 of file giaCof.c.

{ return (unsigned)(((int *)pObj) - ((int *)pFanin)); } 

static int Cof_ObjIsCi ( Cof_Obj_t *  pObj )

inlinestatic

Definition at line 78 of file giaCof.c.

{ return pObj->fTerm && pObj->nFanins == 0;           } 

static int Cof_ObjIsCo ( Cof_Obj_t *  pObj )

inlinestatic

Definition at line 79 of file giaCof.c.

{ return pObj->fTerm && pObj->nFanins == 1;           } 

static int Cof_ObjIsConst0 ( Cof_Obj_t *  pObj )

inlinestatic

Definition at line 81 of file giaCof.c.

{ return!pObj->fTerm && pObj->nFanins == 0;           } 

static int Cof_ObjIsNode ( Cof_Obj_t *  pObj )

inlinestatic

Definition at line 80 of file giaCof.c.

{ return!pObj->fTerm && pObj->nFanins > 0;            } 

static int Cof_ObjIsTerm ( Cof_Obj_t *  pObj )

inlinestatic

Definition at line 77 of file giaCof.c.

{ return pObj->fTerm;                                 } 

static int Cof_ObjIsTravIdCurrent ( Cof_Man_t *  p, Cof_Obj_t *  pObj  )

inlinestatic

Definition at line 99 of file giaCof.c.

{ return ((int)pObj->Value == p->nTravIds);           }

static int Cof_ObjIsTravIdPrevious ( Cof_Man_t *  p, Cof_Obj_t *  pObj  )

inlinestatic

Definition at line 100 of file giaCof.c.

{ return ((int)pObj->Value == p->nTravIds - 1);       }

static int Cof_ObjLevel ( Cof_Man_t *  p, Cof_Obj_t *  pObj  )

inlinestatic

Definition at line 72 of file giaCof.c.

{ return Gia_ObjLevel(p->pGia, Gia_ManObj(p->pGia,pObj->Id)); } 

static int Cof_ObjMffcSize ( Cof_Obj_t *  pNode )

inlinestatic

Definition at line 582 of file giaCof.c.

{
    int Count1, Count2, nFanout;
    nFanout = pNode->nFanouts;
    pNode->nFanouts = 1;
    Count1 = Cof_NodeDeref_rec( pNode );
    Count2 = Cof_NodeRef_rec( pNode );
    pNode->nFanouts = nFanout;
    assert( Count1 == Count2 );
    return Count1;
}

static void Cof_ObjSetTravId ( Cof_Obj_t *  pObj, int  TravId  )

inlinestatic

Definition at line 96 of file giaCof.c.

{ pObj->Value = TravId;                               }

static void Cof_ObjSetTravIdCurrent ( Cof_Man_t *  p, Cof_Obj_t *  pObj  )

inlinestatic

Definition at line 97 of file giaCof.c.

{ pObj->Value = p->nTravIds;                          }

static void Cof_ObjSetTravIdPrevious ( Cof_Man_t *  p, Cof_Obj_t *  pObj  )

inlinestatic

Definition at line 98 of file giaCof.c.

{ pObj->Value = p->nTravIds - 1;                      }

static int Cof_ObjSize ( Cof_Obj_t *  pObj )

inlinestatic

Definition at line 85 of file giaCof.c.

{ return sizeof(Cof_Obj_t) / 4 + pObj->nFanins + pObj->nFanouts;  } 

Vec_Int_t* Gia_ManCofVars	(	Gia_Man_t *	p,
		int	nFanLim
	)

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

Synopsis [Determines variables whose fanout count is higher than this.]

Description [Variables are returned in a reverse topological order.]

SideEffects []

SeeAlso []

Definition at line 883 of file giaCof.c.

{
    Vec_Int_t * vVars;
    Gia_Obj_t * pObj;
    int i;
    ABC_FREE( p->pRefs );
    Gia_ManCreateRefs( p );
    vVars = Vec_IntAlloc( 100 );
    Gia_ManForEachObj( p, pObj, i )
        if ( Gia_ObjIsCand(pObj) && Gia_ObjRefNum(p, pObj) >= nFanLim )
            Vec_IntPush( vVars, i );
    ABC_FREE( p->pRefs );
    return vVars;
}

Gia_Man_t* Gia_ManDupCof	(	Gia_Man_t *	p,
		int	iVar
	)

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

Synopsis [Duplicates AIG in the DFS order while putting CIs first.]

Description []

SideEffects []

SeeAlso []

Definition at line 862 of file giaCof.c.

{
    Gia_Man_t * pNew, * pTemp;
    pNew = Gia_ManDupCofInt( p, iVar );
    pNew = Gia_ManCleanup( pTemp = pNew );
    Gia_ManStop( pTemp );
    return pNew;
}

Gia_Man_t* Gia_ManDupCofAll	(	Gia_Man_t *	p,
		int	nFanLim,
		int	fVerbose
	)

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

Synopsis [Cofactors all variables whose fanout is higher than this.]

Description []

SideEffects []

SeeAlso []

Definition at line 987 of file giaCof.c.

{
    Gia_Man_t * pNew;
    Vec_Int_t * vSigs = Gia_ManCofVars( p, nFanLim );
    pNew = Gia_ManDupCofAllInt( p, vSigs, fVerbose );
    Vec_IntFree( vSigs );
    return pNew;
}

Gia_Man_t* Gia_ManDupCofAllInt	(	Gia_Man_t *	p,
		Vec_Int_t *	vSigs,
		int	fVerbose
	)

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

Synopsis [Cofactors selected variables (should be in reverse topo order).]

Description []

SideEffects []

SeeAlso []

Definition at line 936 of file giaCof.c.

{
    Vec_Int_t * vSigsNew, * vTemp;
    Gia_Man_t * pAig, * pCof, * pNew;
    int iVar;
    if ( fVerbose )
    { 
        printf( "Cofactoring %d signals.\n", Vec_IntSize(vSigs) );
        Gia_ManPrintStats( p, NULL );
    }
    if ( Vec_IntSize( vSigs ) > 200 )
    {
        printf( "Too many signals to cofactor.\n" );
        return NULL;
    }
    pAig = Gia_ManDup( p );
    vSigsNew = Vec_IntDup( vSigs );
    while ( Vec_IntSize(vSigsNew) > 0 )
    {
        Vec_IntSort( vSigsNew, 0 );
        iVar = Vec_IntPop( vSigsNew );
//        Gia_ManCreateRefs( pAig );
//        printf( "ref count = %d\n", Gia_ObjRefNum( pAig, Gia_ManObj(pAig, iVar) ) );
//        ABC_FREE( pAig->pRefs );
        pCof = Gia_ManDupCofInt( pAig, iVar );
        pNew = Gia_ManCleanup( pCof );
        vSigsNew = Gia_ManTransfer( pAig, pCof, pNew, vTemp = vSigsNew );
        Vec_IntFree( vTemp );
        Gia_ManStop( pAig );
        Gia_ManStop( pCof );
        pAig = pNew;
        if ( fVerbose )
            printf( "Cofactored variable %d.\n", iVar );
        if ( fVerbose )
            Gia_ManPrintStats( pAig, NULL );
    }
    Vec_IntFree( vSigsNew );
    return pAig;
}

Gia_Man_t* Gia_ManDupCofInt	(	Gia_Man_t *	p,
		int	iVar
	)

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

Synopsis [Duplicates AIG in the DFS order while putting CIs first.]

Description []

SideEffects []

SeeAlso []

Definition at line 780 of file giaCof.c.

{
    Gia_Man_t * pNew;
    Gia_Obj_t * pObj, * pPivot;
    int i, iCofVar = -1;
    if ( !(iVar > 0 && iVar < Gia_ManObjNum(p)) )
    {
        printf( "Gia_ManDupCof(): Variable %d is out of range (%d; %d).\n", iVar, 0, Gia_ManObjNum(p) );
        return NULL;
    }
    // find the cofactoring variable
    pPivot = Gia_ManObj( p, iVar );
    if ( !Gia_ObjIsCand(pPivot) )
    {
        printf( "Gia_ManDupCof(): Variable %d should be a CI or an AND node.\n", iVar );
        return NULL;
    }
    pNew = Gia_ManStart( Gia_ManObjNum(p) );
    pNew->pName = Abc_UtilStrsav( p->pName );
    pNew->pSpec = Abc_UtilStrsav( p->pSpec );
    Gia_ManHashAlloc( pNew );
    Gia_ManFillValue( p );
    Gia_ManConst0(p)->Value = 0;
    // compute negative cofactor
    Gia_ManForEachCi( p, pObj, i )
    {
        pObj->Value = Gia_ManAppendCi(pNew);
        if ( pObj == pPivot )
        {
            iCofVar = pObj->Value;
            pObj->Value = Abc_Var2Lit( 0, 0 );
        }
    }
    Gia_ManForEachAnd( p, pObj, i )
    {
        pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
        if ( pObj == pPivot )
        {
            iCofVar = pObj->Value;
            pObj->Value = Abc_Var2Lit( 0, 0 );
        }
    }
    Gia_ManForEachCo( p, pObj, i )
        pObj->Value = Gia_ObjFanin0Copy(pObj);
    // compute the positive cofactor
    Gia_ManForEachCi( p, pObj, i )
    {
        pObj->Value = Abc_Var2Lit( Gia_ObjId(pNew, Gia_ManCi(pNew, i)), 0 );
        if ( pObj == pPivot )
            pObj->Value = Abc_Var2Lit( 0, 1 );
    }
    Gia_ManForEachAnd( p, pObj, i )
    {
        pObj->Value = Gia_ManHashAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
        if ( pObj == pPivot )
            pObj->Value = Abc_Var2Lit( 0, 1 );
    }
    // create MUXes
    assert( iCofVar > 0 );
    Gia_ManForEachCo( p, pObj, i )
    {
        if ( pObj->Value == (unsigned)Gia_ObjFanin0Copy(pObj) )
            pObj->Value = Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
        else
            pObj->Value = Gia_ManAppendCo( pNew, Gia_ManHashMux(pNew, iCofVar, Gia_ObjFanin0Copy(pObj), pObj->Value) );
    }
    Gia_ManHashStop( pNew );
    Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );
    return pNew;
}

void Gia_ManPrintFanio	(	Gia_Man_t *	pGia,
		int	nNodes
	)

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

Synopsis [Returns sorted array of node handles with largest fanout.]

Description []

SideEffects []

SeeAlso []

Definition at line 746 of file giaCof.c.

{
    Cof_Man_t * p;
    abctime clk = Abc_Clock();
    p = Cof_ManCreateLogicSimple( pGia );
    p->nLevels = 1 + Gia_ManLevelNum( pGia );
    p->pLevels = ABC_CALLOC( int, p->nLevels );
    Cof_ManPrintFanio( p );

    if ( nNodes > 0 )
    {
    Cof_ManResetTravId( p );
    Gia_ManHashStart( pGia );
    Cof_ManPrintHighFanout( p, nNodes );
    Gia_ManHashStop( pGia );
ABC_PRMn( "Memory for logic network", 4*p->nObjData );
ABC_PRT( "Time", Abc_Clock() - clk );
    }

    Cof_ManStop( p );
}

Vec_Int_t* Gia_ManTransfer	(	Gia_Man_t *	pAig,
		Gia_Man_t *	pCof,
		Gia_Man_t *	pNew,
		Vec_Int_t *	vSigs
	)

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

Synopsis [Transfers attributes from the original one to the final one.]

Description []

SideEffects []

SeeAlso []

Definition at line 909 of file giaCof.c.

{
    Vec_Int_t * vSigsNew;
    Gia_Obj_t * pObj, * pObjF;
    int i;
    vSigsNew = Vec_IntAlloc( 100 );
    Gia_ManForEachObjVec( vSigs, pAig, pObj, i )
    {
        assert( Gia_ObjIsCand(pObj) );
        pObjF = Gia_ManObj( pCof, Abc_Lit2Var(pObj->Value) );
        if ( pObjF->Value && ~pObjF->Value )
            Vec_IntPushUnique( vSigsNew, Abc_Lit2Var(pObjF->Value) );
    }
    return vSigsNew;    
}

static unsigned Gia_ObjHandle ( Gia_Obj_t *  pObj )

inlinestatic

Definition at line 70 of file giaCof.c.

{ return pObj->Value;                                 }