path: root/src/aig/gia/giaCof.c

/**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 $]

***********************************************************************/

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

ABC_NAMESPACE_IMPL_START


////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

typedef struct Cof_Fan_t_ Cof_Fan_t;
struct Cof_Fan_t_
{
    unsigned       iFan     : 31;    // ID of the fanin/fanout
    unsigned       fCompl   :  1;    // complemented attribute
};

typedef struct Cof_Obj_t_ Cof_Obj_t;
struct Cof_Obj_t_
{
    unsigned       fTerm    :  1;    // terminal node (CI/CO)
    unsigned       fPhase   :  1;    // value under 000 pattern
    unsigned       fMark0   :  1;    // first user-controlled mark
    unsigned       fMark1   :  1;    // second user-controlled mark
    unsigned       nFanins  :  4;    // the number of fanins
    unsigned       nFanouts : 24;    // total number of fanouts
    unsigned       nFanoutsM;        // total number of MUX ctrl fanouts
    unsigned       Value;            // application specific data
    int            Id;               // ID of the node
    int            iNext;            // next one in the linked list
    int            iLit;             // literal of the node after rehashing
    Cof_Fan_t      Fanios[0];        // the array of fanins/fanouts
};

typedef struct Cof_Man_t_ Cof_Man_t;
struct Cof_Man_t_
{
    Gia_Man_t *    pGia;             // the original AIG manager
    Vec_Int_t *    vCis;             // the vector of CIs (PIs + LOs)
    Vec_Int_t *    vCos;             // the vector of COs (POs + LIs)
    int            nObjs;            // the number of objects
    int            nNodes;           // the number of nodes
    int            nTravIds;         // traversal ID of the network
    int *          pObjData;         // the logic network defined for the AIG
    int            nObjData;         // the size of array to store the logic network
    int *          pLevels;          // the linked lists of levels
    int            nLevels;          // the max number of logic levels
};

static inline unsigned    Gia_ObjHandle( Gia_Obj_t * pObj )                           { return pObj->Value;                                 } 

static inline int         Cof_ObjLevel( Cof_Man_t * p, Cof_Obj_t * pObj )             { return Gia_ObjLevel(p->pGia, Gia_ManObj(p->pGia,pObj->Id)); } 

static inline unsigned    Cof_ObjHandle( Cof_Man_t * p, Cof_Obj_t * pObj )            { return (unsigned)(((int *)pObj) - p->pObjData);     } 
static inline unsigned    Cof_ObjHandleDiff( Cof_Obj_t * pObj, Cof_Obj_t * pFanin )   { return (unsigned)(((int *)pObj) - ((int *)pFanin)); } 

static inline int         Cof_ObjIsTerm( Cof_Obj_t * pObj )                           { return pObj->fTerm;                                 } 
static inline int         Cof_ObjIsCi( Cof_Obj_t * pObj )                             { return pObj->fTerm && pObj->nFanins == 0;           } 
static inline int         Cof_ObjIsCo( Cof_Obj_t * pObj )                             { return pObj->fTerm && pObj->nFanins == 1;           } 
static inline int         Cof_ObjIsNode( Cof_Obj_t * pObj )                           { return!pObj->fTerm && pObj->nFanins > 0;            } 
static inline int         Cof_ObjIsConst0( Cof_Obj_t * pObj )                         { return!pObj->fTerm && pObj->nFanins == 0;           } 

static inline int         Cof_ObjFaninNum( Cof_Obj_t * pObj )                         { return pObj->nFanins;                               } 
static inline int         Cof_ObjFanoutNum( Cof_Obj_t * pObj )                        { return pObj->nFanouts;                              } 
static inline int         Cof_ObjSize( Cof_Obj_t * pObj )                             { return sizeof(Cof_Obj_t) / 4 + pObj->nFanins + pObj->nFanouts;  } 

static inline Cof_Obj_t * Cof_ManObj( Cof_Man_t * p, unsigned iHandle )               { return (Cof_Obj_t *)(p->pObjData + iHandle);        } 
static inline Cof_Obj_t * Cof_ObjFanin( Cof_Obj_t * pObj, int i )                     { return (Cof_Obj_t *)(((int *)pObj) - pObj->Fanios[i].iFan);               } 
static inline Cof_Obj_t * Cof_ObjFanout( Cof_Obj_t * pObj, int i )                    { return (Cof_Obj_t *)(((int *)pObj) + pObj->Fanios[pObj->nFanins+i].iFan); } 

static inline int         Cof_ManObjNum( Cof_Man_t * p )                              { return p->nObjs;                                    } 
static inline int         Cof_ManNodeNum( Cof_Man_t * p )                             { return p->nNodes;                                   } 

static inline void        Cof_ManResetTravId( Cof_Man_t * p )                         { extern void Cof_ManCleanValue( Cof_Man_t * p ); Cof_ManCleanValue( p ); p->nTravIds = 1;  }
static inline void        Cof_ManIncrementTravId( Cof_Man_t * p )                     { p->nTravIds++;                                      }
static inline void        Cof_ObjSetTravId( Cof_Obj_t * pObj, int TravId )            { pObj->Value = TravId;                               }
static inline void        Cof_ObjSetTravIdCurrent( Cof_Man_t * p, Cof_Obj_t * pObj )  { pObj->Value = p->nTravIds;                          }
static inline void        Cof_ObjSetTravIdPrevious( Cof_Man_t * p, Cof_Obj_t * pObj ) { pObj->Value = p->nTravIds - 1;                      }
static inline int         Cof_ObjIsTravIdCurrent( Cof_Man_t * p, Cof_Obj_t * pObj )   { return ((int)pObj->Value == p->nTravIds);           }
static inline int         Cof_ObjIsTravIdPrevious( Cof_Man_t * p, Cof_Obj_t * pObj )  { return ((int)pObj->Value == p->nTravIds - 1);       }

#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++ )

////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

/**Function*************************************************************

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Cof_Man_t * Cof_ManCreateLogicSimple( Gia_Man_t * pGia )
{
    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;
}

/**Function*************************************************************

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Cof_ManStop( Cof_Man_t * p )
{
    Vec_IntFree( p->vCis );
    Vec_IntFree( p->vCos );
    ABC_FREE( p->pObjData );
    ABC_FREE( p->pLevels );
    ABC_FREE( p );
}


/**Function*************************************************************

  Synopsis    [Collects support nodes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Cof_ManTfoSize_rec( Cof_Man_t * p, Cof_Obj_t * pObj )
{
    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;
}

/**Function*************************************************************

  Synopsis    [Collects support nodes.]

  Description []
               
  SideEffects []

  SeeAlso     []

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

/**Function*************************************************************

  Synopsis    [Collects support nodes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Cof_ManTfiSize_rec( Cof_Man_t * p, Cof_Obj_t * pObj )
{
    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;
}

/**Function*************************************************************

  Synopsis    [Collects support nodes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Cof_ManTfiSize( Cof_Man_t * p, Cof_Obj_t ** ppObjs, int nObjs )
{
    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;
}

/**Function*************************************************************

  Synopsis    [Collects support nodes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Cof_ManSuppSize_rec( Cof_Man_t * p, Cof_Obj_t * pObj )
{
    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;
}

/**Function*************************************************************

  Synopsis    [Collects support nodes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Cof_ManSuppSize( Cof_Man_t * p, Cof_Obj_t ** ppObjs, int nObjs )
{
    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;
}


/**Function*************************************************************

  Synopsis    [Cleans the value.]

  Description []
               
  SideEffects []

  SeeAlso     []

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

/**Function*************************************************************

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Cof_ManInsertEntry_rec( Vec_Ptr_t * vNodes, Cof_Obj_t * pNode, int nNodeMax )
{
    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 );
    }
}

/**Function*************************************************************

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Ptr_t * Cof_ManCollectHighFanout( Cof_Man_t * p, int nNodes )
{
    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;
}

/**Function*************************************************************

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Cof_ManCountRemoved( Cof_Man_t * p, Cof_Obj_t * pRoot, int fConst1 )
{
    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;
}

/**Function*************************************************************

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Cof_ManPrintHighFanoutOne( Cof_Man_t * p, Cof_Obj_t * pObj )
{
    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" );
}

/**Function*************************************************************

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Cof_ManPrintHighFanout( Cof_Man_t * p, int nNodes )
{
    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 );
}

/**Function*************************************************************

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Cof_ManPrintFanio( Cof_Man_t * p )
{
    char Buffer[100];
    Cof_Obj_t * pNode;
    Vec_Int_t * vFanins, * vFanouts;
    int nFanins, nFanouts, nFaninsMax, nFanoutsMax, nFaninsAll, nFanoutsAll;
    int i, k, nSizeMax;

    // determine the largest fanin and fanout
    nFaninsMax = nFanoutsMax = 0;
    nFaninsAll = nFanoutsAll = 0;
    Cof_ManForEachNode( p, pNode, i )
    {
        if ( i == 0 ) continue;
        nFanins  = Cof_ObjFaninNum(pNode);
        nFanouts = Cof_ObjFanoutNum(pNode);
        nFaninsAll  += nFanins;
        nFanoutsAll += nFanouts;
        nFaninsMax   = Abc_MaxInt( nFaninsMax, nFanins );
        nFanoutsMax  = Abc_MaxInt( nFanoutsMax, nFanouts );
    }

    // allocate storage for fanin/fanout numbers
    nSizeMax = Abc_MaxInt( 10 * (Abc_Base10Log(nFaninsMax) + 1), 10 * (Abc_Base10Log(nFanoutsMax) + 1) );
    vFanins  = Vec_IntStart( nSizeMax );
    vFanouts = 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);
//            nFanouts = Cof_NodeMffcSize(pNode);

        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 );
    }

    printf( "The distribution of fanins and fanouts in the network:\n" );
    printf( "         Number   Nodes with fanin  Nodes with fanout\n" );
    for ( k = 0; k < nSizeMax; k++ )
    {
        if ( vFanins->pArray[k] == 0 && vFanouts->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( "%12d  ", vFanins->pArray[k] );
        printf( "    " );
        if ( vFanouts->pArray[k] == 0 )
            printf( "              " );
        else
            printf( "%12d  ", vFanouts->pArray[k] );
        printf( "\n" );
    }
    Vec_IntFree( vFanins );
    Vec_IntFree( vFanouts );

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

/**Function*************************************************************

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Gia_ManPrintFanio( Gia_Man_t * pGia, int nNodes )
{
    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 );

    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 );
}


/**Function*************************************************************

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Gia_Man_t * Gia_ManDupCofInt( Gia_Man_t * p, int iVar )
{
    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;
}

/**Function*************************************************************

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

  Description []
               
  SideEffects []

  SeeAlso     []

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


/**Function*************************************************************

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

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

  SeeAlso     []

***********************************************************************/
Vec_Int_t * Gia_ManCofVars( Gia_Man_t * p, int nFanLim )
{
    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;
}

/**Function*************************************************************

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Int_t * Gia_ManTransfer( Gia_Man_t * pAig, Gia_Man_t * pCof, Gia_Man_t * pNew, Vec_Int_t * vSigs )
{
    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;    
}

/**Function*************************************************************

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Gia_Man_t * Gia_ManDupCofAllInt( Gia_Man_t * p, Vec_Int_t * vSigs, int fVerbose )
{
    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;
}

/**Function*************************************************************

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

  Description []
               
  SideEffects []

  SeeAlso     []

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

////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


ABC_NAMESPACE_IMPL_END