absRpm.c

/**CFile****************************************************************

  FileName    [absRpm.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Abstraction package.]

  Synopsis    [Structural reparameterization.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

  Revision    [$Id: absRpm.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]

***********************************************************************/
 
#include "abs.h"
#include "misc/vec/vecWec.h"

ABC_NAMESPACE_IMPL_START 

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

static inline int   Gia_ObjDom( Gia_Man_t * p, Gia_Obj_t * pObj )            { return Vec_IntEntry(p->vDoms, Gia_ObjId(p, pObj));   }
static inline void  Gia_ObjSetDom( Gia_Man_t * p, Gia_Obj_t * pObj, int d )  { Vec_IntWriteEntry(p->vDoms, Gia_ObjId(p, pObj), d);  }

static int Abs_ManSupport2( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSupp );
static int Abs_GiaObjDeref_rec( Gia_Man_t * p, Gia_Obj_t * pNode );
static int Abs_GiaObjRef_rec( Gia_Man_t * p, Gia_Obj_t * pNode );

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

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

  Synopsis    [Computes one-node dominators.]

  Description [For each node, computes the closest one-node dominator,
  which can be the node itself if the node has no other dominators.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Gia_ManAddDom( Gia_Man_t * p, Gia_Obj_t * pObj, int iDom0 )
{
    int iDom1, iDomNext;
    if ( Gia_ObjDom(p, pObj) == -1 )
    {
        Gia_ObjSetDom( p, pObj, iDom0 );
        return;
    }
    iDom1 = Gia_ObjDom( p, pObj );
    while ( 1 )
    {
        if ( iDom0 > iDom1 )
        {
            iDomNext = Gia_ObjDom( p, Gia_ManObj(p, iDom1) );
            if ( iDomNext == iDom1 )
                break;
            iDom1 = iDomNext;
            continue;
        }
        if ( iDom1 > iDom0 )
        {
            iDomNext = Gia_ObjDom( p, Gia_ManObj(p, iDom0) );
            if ( iDomNext == iDom0 )
                break;
            iDom0 = iDomNext;
            continue;
        }
        assert( iDom0 == iDom1 );
        Gia_ObjSetDom( p, pObj, iDom0 );
        return;
    }
    Gia_ObjSetDom( p, pObj, Gia_ObjId(p, pObj) );
}
void Gia_ManComputeDoms( Gia_Man_t * p )
{
    Gia_Obj_t * pObj;
    int i;
    if ( p->vDoms == NULL )
        p->vDoms = Vec_IntAlloc( 0 );
    Vec_IntFill( p->vDoms, Gia_ManObjNum(p), -1 );
    Gia_ManForEachObjReverse( p, pObj, i )
    {
        if ( i == 0 || Gia_ObjIsCi(pObj) )
            continue;
        if ( pObj->fMark1 || (p->pRefs && Gia_ObjIsAnd(pObj) && Gia_ObjRefNum(p, pObj) == 0) )
            continue;
        if ( Gia_ObjIsCo(pObj) )
        {
            Gia_ObjSetDom( p, pObj, i );
            Gia_ManAddDom( p, Gia_ObjFanin0(pObj), i );
            continue;
        }
        assert( Gia_ObjIsAnd(pObj) );
        Gia_ManAddDom( p, Gia_ObjFanin0(pObj), i );
        Gia_ManAddDom( p, Gia_ObjFanin1(pObj), i );
    }
}


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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Wec_t * Gia_ManCreateSupps( Gia_Man_t * p, int fVerbose )
{
    abctime clk = Abc_Clock();
    Gia_Obj_t * pObj; int i, Id;
    Vec_Wec_t * vSupps = Vec_WecStart( Gia_ManObjNum(p) );
    Gia_ManForEachCiId( p, Id, i )
        Vec_IntPush( Vec_WecEntry(vSupps, Id), i );
    Gia_ManForEachAnd( p, pObj, Id )
        Vec_IntTwoMerge2( Vec_WecEntry(vSupps, Gia_ObjFaninId0(pObj, Id)), 
                          Vec_WecEntry(vSupps, Gia_ObjFaninId1(pObj, Id)), 
                          Vec_WecEntry(vSupps, Id) ); 
//    Gia_ManForEachCo( p, pObj, i )
//        Vec_IntAppend( Vec_WecEntry(vSupps, Gia_ObjId(p, pObj)), Vec_WecEntry(vSupps, Gia_ObjFaninId0p(p, pObj)) );
    if ( fVerbose )
        Abc_PrintTime( 1, "Support computation", Abc_Clock() - clk );
    return vSupps;
}
void Gia_ManDomTest( Gia_Man_t * p )
{
    Vec_Int_t * vDoms = Vec_IntAlloc( 100 );
    Vec_Int_t * vSupp = Vec_IntAlloc( 100 );
    Vec_Wec_t * vSupps = Gia_ManCreateSupps( p, 1 );
    Vec_Wec_t * vDomeds = Vec_WecStart( Gia_ManObjNum(p) );
    Gia_Obj_t * pObj, * pDom; int i, Id, nMffcSize;
    Gia_ManCreateRefs( p );
    Gia_ManComputeDoms( p );
    Gia_ManForEachCi( p, pObj, i )
    {
        if ( Gia_ObjDom(p, pObj) == -1 )
            continue;
        for ( pDom = Gia_ManObj(p, Gia_ObjDom(p, pObj)); Gia_ObjIsAnd(pDom); pDom = Gia_ManObj(p, Gia_ObjDom(p, pDom)) )
            Vec_IntPush( Vec_WecEntry(vDomeds, Gia_ObjId(p, pDom)), i );
    }
    Gia_ManForEachAnd( p, pObj, i )
        if ( Vec_IntEqual(Vec_WecEntry(vSupps, i), Vec_WecEntry(vDomeds, i)) )
            Vec_IntPush( vDoms, i );
    Vec_WecFree( vSupps );
    Vec_WecFree( vDomeds );

    // check MFFC sizes
    Vec_IntForEachEntry( vDoms, Id, i )
        Gia_ObjRefInc( p, Gia_ManObj(p, Id) );
    Vec_IntForEachEntry( vDoms, Id, i )
    {
        nMffcSize = Gia_NodeMffcSizeSupp( p, Gia_ManObj(p, Id), vSupp );
        printf( "%d(%d:%d) ", Id, Vec_IntSize(vSupp), nMffcSize );
    }
    printf( "\n" );
    Vec_IntForEachEntry( vDoms, Id, i )
        Gia_ObjRefDec( p, Gia_ManObj(p, Id) );

//    Vec_IntPrint( vDoms );
    Vec_IntFree( vDoms );
    Vec_IntFree( vSupp );
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Gia_ManTestDoms2( Gia_Man_t * p )
{
    Vec_Int_t * vNodes;
    Gia_Obj_t * pObj, * pDom;
    abctime clk = Abc_Clock();
    int i;
    assert( p->vDoms == NULL );
    Gia_ManComputeDoms( p );
/*
    Gia_ManForEachPi( p, pObj, i )
        if ( Gia_ObjId(p, pObj) != Gia_ObjDom(p, pObj) )
            printf( "PI =%6d  Id =%8d. Dom =%8d.\n", i, Gia_ObjId(p, pObj), Gia_ObjDom(p, pObj) );
*/
    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
    // for each dominated PI, when if the PIs is in a leaf of the MFFC of the dominator
    Gia_ManCleanMark1( p );
    Gia_ManForEachPi( p, pObj, i )
        pObj->fMark1 = 1;
    vNodes = Vec_IntAlloc( 100 );
    Gia_ManCreateRefs( p );
    Gia_ManForEachPi( p, pObj, i )
    {
        if ( Gia_ObjId(p, pObj) == Gia_ObjDom(p, pObj) )
            continue;

        pDom = Gia_ManObj(p, Gia_ObjDom(p, pObj));
        if ( Gia_ObjIsCo(pDom) )
        {
            assert( Gia_ObjFanin0(pDom) == pObj );
            continue;
        }
        assert( Gia_ObjIsAnd(pDom) );
        Abs_GiaObjDeref_rec( p, pDom );
        Abs_ManSupport2( p, pDom, vNodes );
        Abs_GiaObjRef_rec( p, pDom );

        if ( Vec_IntFind(vNodes, Gia_ObjId(p, pObj)) == -1 )
            printf( "FAILURE.\n" );
//        else
//            printf( "Success.\n" );
    }
    Vec_IntFree( vNodes );
    Gia_ManCleanMark1( p );
}

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

  Synopsis    [Collect PI doms.]

  Description [Assumes that some PIs and ANDs are marked with fMark1.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Int_t * Gia_ManCollectDoms( Gia_Man_t * p )
{
    Vec_Int_t * vNodes;
    Gia_Obj_t * pObj;
    int Lev, LevMax = ABC_INFINITY;
    int i, iDom, iDomNext;
    vNodes = Vec_IntAlloc( 100 );
    Gia_ManForEachObj( p, pObj, i )
    {
        if ( !pObj->fMark1 )
            continue;
        if ( p->pRefs && Gia_ObjRefNum(p, pObj) == 0 )
            continue;
        iDom = Gia_ObjDom(p, pObj);
        if ( iDom == -1 )
            continue;
        if ( iDom == i )
            continue;
        for ( Lev = 0; Lev < LevMax && Gia_ObjIsAnd( Gia_ManObj(p, iDom) ); Lev++ )
        {
            Vec_IntPush( vNodes, iDom );
            iDomNext = Gia_ObjDom( p, Gia_ManObj(p, iDom) );
            if ( iDomNext == iDom )
                break;
            iDom = iDomNext;
        }
    }
    Vec_IntUniqify( vNodes );
    return vNodes;
}
Vec_Int_t * Gia_ManComputePiDoms( Gia_Man_t * p )
{
    Vec_Int_t * vNodes;
    Gia_ManComputeDoms( p );
    vNodes = Gia_ManCollectDoms( p );
//    Vec_IntPrint( vNodes );
    return vNodes;
}
void Gia_ManTestDoms( Gia_Man_t * p )
{
    Vec_Int_t * vNodes;
    Gia_Obj_t * pObj;
    int i;
    // mark PIs
//    Gia_ManCreateRefs( p );
    Gia_ManCleanMark1( p );
    Gia_ManForEachPi( p, pObj, i )
        pObj->fMark1 = 1;
    // compute dominators
    assert( p->vDoms == NULL );
    vNodes = Gia_ManComputePiDoms( p );
//    printf( "Nodes = %d. Doms = %d.\n", Gia_ManAndNum(p), Vec_IntSize(vNodes) );
    Vec_IntFree( vNodes );
    // unmark PIs
    Gia_ManCleanMark1( p );
}


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

  Synopsis    [Counts flops without fanout.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Gia_ManCountFanoutlessFlops( Gia_Man_t * p )
{
    Gia_Obj_t * pObj;
    int i;
    int Counter = 0;
    Gia_ManCreateRefs( p );
    Gia_ManForEachRo( p, pObj, i )
        if ( Gia_ObjRefNum(p, pObj) == 0 )
            Counter++;
    printf( "Fanoutless flops = %d.\n", Counter );
    ABC_FREE( p->pRefs );
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Gia_ManCountPisNodes_rec( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vPis, Vec_Int_t * vAnds )
{
    if ( Gia_ObjIsTravIdCurrent(p, pObj) )
        return;
    Gia_ObjSetTravIdCurrent(p, pObj);
    if ( pObj->fMark1 )
    {
        Vec_IntPush( vPis, Gia_ObjId(p, pObj) );
        return;
    }
    assert( Gia_ObjIsAnd(pObj) );
    Gia_ManCountPisNodes_rec( p, Gia_ObjFanin0(pObj), vPis, vAnds );
    Gia_ManCountPisNodes_rec( p, Gia_ObjFanin1(pObj), vPis, vAnds );
    Vec_IntPush( vAnds, Gia_ObjId(p, pObj) );
}
void Gia_ManCountPisNodes( Gia_Man_t * p, Vec_Int_t * vPis, Vec_Int_t * vAnds )
{
    Gia_Obj_t * pObj;
    int i;
    // mark const0 and flop output
    Gia_ManIncrementTravId( p );
    Gia_ObjSetTravIdCurrent( p, Gia_ManConst0(p) );
    Gia_ManForEachRo( p, pObj, i )
        Gia_ObjSetTravIdCurrent( p, pObj );
    // count PIs and internal nodes reachable from COs
    Vec_IntClear( vPis );
    Vec_IntClear( vAnds );
    Gia_ManForEachCo( p, pObj, i )
        Gia_ManCountPisNodes_rec( p, Gia_ObjFanin0(pObj), vPis, vAnds );
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abs_GiaObjDeref_rec( Gia_Man_t * p, Gia_Obj_t * pNode )
{
    Gia_Obj_t * pFanin;
    int Counter = 0;
    if ( pNode->fMark1 || Gia_ObjIsRo(p, pNode) )
        return 0;
    assert( Gia_ObjIsAnd(pNode) );
    pFanin = Gia_ObjFanin0(pNode);
    assert( Gia_ObjRefNum(p, pFanin) > 0 );
    if ( Gia_ObjRefDec(p, pFanin) == 0 )
        Counter += Abs_GiaObjDeref_rec( p, pFanin );
    pFanin = Gia_ObjFanin1(pNode);
    assert( Gia_ObjRefNum(p, pFanin) > 0 );
    if ( Gia_ObjRefDec(p, pFanin) == 0 )
        Counter += Abs_GiaObjDeref_rec( p, pFanin );
    return Counter + 1;
}
int Abs_GiaObjRef_rec( Gia_Man_t * p, Gia_Obj_t * pNode )
{
    Gia_Obj_t * pFanin;
    int Counter = 0;
    if ( pNode->fMark1 || Gia_ObjIsRo(p, pNode) )
        return 0;
    assert( Gia_ObjIsAnd(pNode) );
    pFanin = Gia_ObjFanin0(pNode);
    if ( Gia_ObjRefInc(p, pFanin) == 0 )
        Counter += Abs_GiaObjRef_rec( p, pFanin );
    pFanin = Gia_ObjFanin1(pNode);
    if ( Gia_ObjRefInc(p, pFanin) == 0 )
        Counter += Abs_GiaObjRef_rec( p, pFanin );
    return Counter + 1;
}

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

  Synopsis    [Returns the number of nodes with zero refs.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abs_GiaSortNodes( Gia_Man_t * p, Vec_Int_t * vSupp )
{
    Gia_Obj_t * pObj;
    int nSize = Vec_IntSize(vSupp);
    int i, RetValue;
    Gia_ManForEachObjVec( vSupp, p, pObj, i )
        if ( i < nSize && Gia_ObjRefNum(p, pObj) == 0 && !Gia_ObjIsRo(p, pObj) ) // add removable leaves
        {
            assert( pObj->fMark1 );
            Vec_IntPush( vSupp, Gia_ObjId(p, pObj) );
        }
    RetValue = Vec_IntSize(vSupp) - nSize;
    Gia_ManForEachObjVec( vSupp, p, pObj, i )
        if ( i < nSize && !(Gia_ObjRefNum(p, pObj) == 0 && !Gia_ObjIsRo(p, pObj)) ) // add non-removable leaves
            Vec_IntPush( vSupp, Gia_ObjId(p, pObj) );
    assert( Vec_IntSize(vSupp) == 2 * nSize );
    memmove( Vec_IntArray(vSupp), Vec_IntArray(vSupp) + nSize, sizeof(int) * nSize );
    Vec_IntShrink( vSupp, nSize );
    return RetValue;
}


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

  Synopsis    [Computes support in terms of PIs and flops.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abs_ManSupport1_rec( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSupp )
{
    if ( Gia_ObjIsTravIdCurrent(p, pObj) )
        return;
    Gia_ObjSetTravIdCurrent(p, pObj);
    if ( pObj->fMark1 || Gia_ObjIsRo(p, pObj) )
    {
        Vec_IntPush( vSupp, Gia_ObjId(p, pObj) );
        return;
    }
    assert( Gia_ObjIsAnd(pObj) );
    Abs_ManSupport1_rec( p, Gia_ObjFanin0(pObj), vSupp );
    Abs_ManSupport1_rec( p, Gia_ObjFanin1(pObj), vSupp );
}
int Abs_ManSupport1( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSupp )
{
    assert( Gia_ObjIsAnd(pObj) );
    Vec_IntClear( vSupp );
    Gia_ManIncrementTravId( p );
    Abs_ManSupport1_rec( p, pObj, vSupp );
    return Vec_IntSize(vSupp);
}

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

  Synopsis    [Computes support of the MFFC.]

  Description [Should be called when pObj's cone is dereferenced.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abs_ManSupport2_rec( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSupp )
{
    if ( Gia_ObjIsTravIdCurrent(p, pObj) )
        return;
    Gia_ObjSetTravIdCurrent(p, pObj);
    if ( pObj->fMark1 || Gia_ObjIsRo(p, pObj) || Gia_ObjRefNum(p, pObj) > 0 )
    {
        Vec_IntPush( vSupp, Gia_ObjId(p, pObj) );
        return;
    }
    assert( Gia_ObjIsAnd(pObj) );
    Abs_ManSupport2_rec( p, Gia_ObjFanin0(pObj), vSupp );
    Abs_ManSupport2_rec( p, Gia_ObjFanin1(pObj), vSupp );
}
int Abs_ManSupport2( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSupp )
{
    assert( Gia_ObjIsAnd(pObj) );
    Vec_IntClear( vSupp );
    Gia_ManIncrementTravId( p );
    Abs_ManSupport2_rec( p, Gia_ObjFanin0(pObj), vSupp );
    Abs_ManSupport2_rec( p, Gia_ObjFanin1(pObj), vSupp );
    Gia_ObjSetTravIdCurrent(p, pObj);
    return Vec_IntSize(vSupp);
}

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

  Synopsis    [Computes support of the extended MFFC.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abs_ManSupport3( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSupp )
{
    Gia_Obj_t * pTemp, * pFan0, * pFan1;
    int i, nSize0;
    // collect MFFC
    Abs_ManSupport2( p, pObj, vSupp );
    // move dominated to the front
    nSize0 = Abs_GiaSortNodes( p, vSupp );
    assert( nSize0 > 0 );
    // consider remaining nodes
    while ( 1 )
    {
        int fChanges = 0;
        Gia_ManForEachObjVec( vSupp, p, pTemp, i )
        {
            if ( i < nSize0 )
                continue;
            if ( !Gia_ObjIsAnd(pTemp) )
                continue;
            assert( !pTemp->fMark1 );
            assert( Gia_ObjRefNum(p, pTemp) > 0 );
            pFan0 = Gia_ObjFanin0(pTemp);
            pFan1 = Gia_ObjFanin1(pTemp);
            if ( Gia_ObjIsTravIdCurrent(p, pFan0) && Gia_ObjIsTravIdCurrent(p, pFan1) )
            {
                Vec_IntRemove( vSupp, Gia_ObjId(p, pTemp) );
                fChanges = 1;
                break;
            }
            if ( Gia_ObjIsTravIdCurrent(p, pFan0) )
            {
                Vec_IntRemove( vSupp, Gia_ObjId(p, pTemp) );
                Vec_IntPush( vSupp, Gia_ObjId(p, pFan1) );
                assert( !Gia_ObjIsTravIdCurrent(p, pFan1) );
                Gia_ObjSetTravIdCurrent(p, pFan1);
                fChanges = 1;
                break;
            }
            if ( Gia_ObjIsTravIdCurrent(p, pFan1) )
            {
                Vec_IntRemove( vSupp, Gia_ObjId(p, pTemp) );
                Vec_IntPush( vSupp, Gia_ObjId(p, pFan0) );
                assert( !Gia_ObjIsTravIdCurrent(p, pFan0) );
                Gia_ObjSetTravIdCurrent(p, pFan0);
                fChanges = 1;
                break;
            }
        }
        if ( !fChanges )
            break;
    }
    return Vec_IntSize(vSupp);
}


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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abs_GiaCofPrint( word * pTruth, int nSize, int nSize0, int Res )
{
    int i, Bit;
    int nBits = (1 << nSize);
    int nStep = (1 << nSize0);
    int Mark[2] = {1,1};
    for ( i = 0; i < nBits; i++ )
    {
        if ( i % nStep == 0 )
        {
            printf( " " );
            assert( Res || (Mark[0] && Mark[1]) );
            Mark[0] = Mark[1] = 0;
        }
        Bit = Abc_InfoHasBit((unsigned *)pTruth, i);
        Mark[Bit] = 1;
        printf( "%d", Bit );
    }
    printf( "\n" );
    assert( Res || (Mark[0] && Mark[1]) );
    return 1;
}

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

  Synopsis    [Returns 1 if truth table has no const cofactors.]

  Description [The cofactoring variables are the (nSize-nSize0)
  most significant vars.  Each cofactor depends on nSize0 vars.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Abs_GiaCheckTruth( word * pTruth, int nSize, int nSize0 )
{
    unsigned char * pStr = (unsigned char *)pTruth;
    int nStr = (nSize >= 3 ? (1 << (nSize - 3)) : 1);
    int i, k, nSteps;
    assert( nSize0 > 0 && nSize0 <= nSize );
    if ( nSize0 == 1 )
    {
        for ( i = 0; i < nStr; i++ )
            if ( (((unsigned)pStr[i] ^ ((unsigned)pStr[i] >> 1)) & 0x55) != 0x55 )
                return 0;
        return 1;
    }
    if ( nSize0 == 2 )
    {
        for ( i = 0; i < nStr; i++ )
            if ( ((unsigned)pStr[i] & 0xF) == 0x0 || (((unsigned)pStr[i] >> 4) & 0xF) == 0x0 || 
                 ((unsigned)pStr[i] & 0xF) == 0xF || (((unsigned)pStr[i] >> 4) & 0xF) == 0xF  )
                return 0;
        return 1;
    }
    assert( nSize0 >= 3 );
    nSteps = (1 << (nSize0 - 3));
    for ( i = 0; i < nStr; i += nSteps )
    {
        for ( k = 0; k < nSteps; k++ )
            if ( ((unsigned)pStr[i+k] & 0xFF) != 0x00 )
                break;
        if ( k == nSteps )
            break;
        for ( k = 0; k < nSteps; k++ )
            if ( ((unsigned)pStr[i+k] & 0xFF) != 0xFF )
                break;
        if ( k == nSteps )
            break;
    }
    assert( i <= nStr );
    return (int)( i == nStr );
}

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

  Synopsis    [Returns 1 if truth table has const cofactors.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abs_RpmPerformMark( Gia_Man_t * p, int nCutMax, int fVerbose, int fVeryVerbose )
{
    Vec_Int_t * vPis, * vAnds, * vDoms;
    Vec_Int_t * vSupp, * vSupp1, * vSupp2;
    Gia_Obj_t * pObj;
    word * pTruth;
    int Iter, i, nSize0, nNodes;
    int fHasConst, fChanges = 1;
    Gia_ManCreateRefs( p );
    Gia_ManCleanMark1( p );
    Gia_ManForEachPi( p, pObj, i )
        pObj->fMark1 = 1;
    vPis = Vec_IntAlloc( 100 );
    vAnds = Vec_IntAlloc( 100 );
    vSupp1 = Vec_IntAlloc( 100 );
    vSupp2 = Vec_IntAlloc( 100 );
    for ( Iter = 0; fChanges; Iter++ )
    {
        fChanges = 0;
        vDoms = Gia_ManComputePiDoms( p );
        // count the number of PIs and internal nodes
        if ( fVerbose || fVeryVerbose )
        {
            Gia_ManCountPisNodes( p, vPis, vAnds );
            printf( "Iter %3d :  ", Iter );
            printf( "PI = %5d  (%6.2f %%)  ",  Vec_IntSize(vPis),  100.0 * Vec_IntSize(vPis)  / Gia_ManPiNum(p)  );
            printf( "And = %6d  (%6.2f %%) ",  Vec_IntSize(vAnds), 100.0 * Vec_IntSize(vAnds) / Gia_ManAndNum(p) );
            printf( "Dom = %5d  (%6.2f %%)  ", Vec_IntSize(vDoms), 100.0 * Vec_IntSize(vDoms) / Gia_ManAndNum(p)  );
            printf( "\n" );
        }
//        pObj = Gia_ObjFanin0( Gia_ManPo(p, 1) );
        Gia_ManForEachObjVec( vDoms, p, pObj, i )
        {
            assert( !pObj->fMark1 );
            assert( Gia_ObjRefNum( p, pObj ) > 0 );
            // dereference root node
            nNodes = Abs_GiaObjDeref_rec( p, pObj );
/*
            // compute support of full cone
            if ( Abs_ManSupport1(p, pObj, vSupp1) > nCutMax )
//            if ( 1 )
            {
                // check support of MFFC
                if ( Abs_ManSupport2(p, pObj, vSupp2) > nCutMax )
//                if ( 1 )
                {
                    Abs_GiaObjRef_rec( p, pObj );
                    continue;
                }
                vSupp = vSupp2;
//                printf( "-" );
            }
            else
            {
                vSupp = vSupp1;
//                printf( "+" );
            }
*/
            if ( Abs_ManSupport2(p, pObj, vSupp2) > nCutMax )
            {
                Abs_GiaObjRef_rec( p, pObj );
                continue;
            }
            vSupp = vSupp2;

            // order nodes by their ref counts
            nSize0 = Abs_GiaSortNodes( p, vSupp );
            assert( nSize0 > 0 && nSize0 <= nCutMax );
            // check if truth table has const cofs
            pTruth = Gia_ObjComputeTruthTableCut( p, pObj, vSupp );
            if ( pTruth == NULL )
            {
                Abs_GiaObjRef_rec( p, pObj );
                continue;
            }
            fHasConst = !Abs_GiaCheckTruth( pTruth, Vec_IntSize(vSupp), nSize0 );
            if ( fVeryVerbose )
            {
                printf( "Nodes =%3d ",  nNodes );
                printf( "Size =%3d ",   Vec_IntSize(vSupp) );
                printf( "Size0 =%3d  ", nSize0 );
                printf( "%3s", fHasConst ? "yes" : "no" );
                Abs_GiaCofPrint( pTruth, Vec_IntSize(vSupp), nSize0, fHasConst );
            }
            if ( fHasConst )
            {
                Abs_GiaObjRef_rec( p, pObj );
                continue;
            }
            // pObj can be reparamed
            pObj->fMark1 = 1;
            fChanges = 1;
        }
        Vec_IntFree( vDoms );
    }
    // count the number of PIs and internal nodes
    if ( fVeryVerbose )
    {
        Gia_ManCountPisNodes( p, vPis, vAnds );
        printf( "Iter %3d :  ", Iter );
        printf( "PI = %5d  (%6.2f %%)  ",  Vec_IntSize(vPis),  100.0 * Vec_IntSize(vPis)  / Gia_ManPiNum(p)  );
        printf( "And = %6d  (%6.2f %%) ",  Vec_IntSize(vAnds), 100.0 * Vec_IntSize(vAnds) / Gia_ManAndNum(p) );
//        printf( "Dom = %5d  (%6.2f %%)  ", Vec_IntSize(vDoms), 100.0 * Vec_IntSize(vDoms) / Gia_ManAndNum(p)  );
        printf( "\n" );
    }
    // cleanup
    Vec_IntFree( vPis );
    Vec_IntFree( vAnds );
    Vec_IntFree( vSupp1 );
    Vec_IntFree( vSupp2 );
//    Gia_ManCleanMark1( p ); // this will erase markings
    ABC_FREE( p->pRefs );
}

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

  Synopsis    [Assumed that fMark1 marks the internal PIs.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Gia_Man_t * Gia_ManDupRpm( Gia_Man_t * p )
{
    Vec_Int_t * vPis, * vAnds;
    Gia_Man_t * pNew;
    Gia_Obj_t * pObj;
    int i;
    // derive PIs and internal nodes
    vPis = Vec_IntAlloc( 100 );
    vAnds = Vec_IntAlloc( 100 );
    Gia_ManCountPisNodes( p, vPis, vAnds );

    // duplicate AIG
    Gia_ManFillValue( p );
    pNew = Gia_ManStart( Gia_ManObjNum(p) );
    pNew->pName = Abc_UtilStrsav( p->pName );
    pNew->pSpec = Abc_UtilStrsav( p->pSpec );
    Gia_ManConst0(p)->Value = 0;
    // create PIs
    Gia_ManForEachObjVec( vPis, p, pObj, i )
        pObj->Value = Gia_ManAppendCi(pNew);
    // create flops
    Gia_ManForEachRo( p, pObj, i )
        pObj->Value = Gia_ManAppendCi( pNew );
    // create internal nodes
    Gia_ManForEachObjVec( vAnds, p, pObj, i )
        pObj->Value = Gia_ManAppendAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
    // create COs
    Gia_ManForEachCo( p, pObj, i )
        Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
    Gia_ManSetRegNum( pNew, Gia_ManRegNum(p) );

    // cleanup
    Vec_IntFree( vPis );
    Vec_IntFree( vAnds );
    return pNew;
}

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

  Synopsis    [Performs structural reparametrization.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Gia_Man_t * Abs_RpmPerform( Gia_Man_t * p, int nCutMax, int fVerbose, int fVeryVerbose )
{
    Gia_Man_t * pNew;
//    Gia_ManTestDoms( p );
//    return NULL;
    // perform structural analysis
    Gia_ObjComputeTruthTableStart( p, nCutMax );
    Abs_RpmPerformMark( p, nCutMax, fVerbose, fVeryVerbose );
    Gia_ObjComputeTruthTableStop( p );
    // derive new AIG
    pNew = Gia_ManDupRpm( p );
    Gia_ManCleanMark1( p );
    return pNew;
}

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


ABC_NAMESPACE_IMPL_END