acecStruct.c

Go to the documentation of this file.

 
#include "acecInt.h"
#include "misc/vec/vecWec.h"
#include "misc/extra/extra.h"
 
ABC_NAMESPACE_IMPL_START

 


Vec_Int_t * Acec_StructDetectXorRoots( Gia_Man_t * p )
{
    Vec_Int_t * vXors = Vec_IntAlloc( 100 );
    Vec_Bit_t * vXorIns = Vec_BitStart( Gia_ManObjNum(p) );
    Gia_Obj_t * pFan0, * pFan1, * pObj; 
    int i, k = 0, Entry;
    Gia_ManForEachAnd( p, pObj, i )
    {
        if ( !Gia_ObjRecognizeExor(pObj, &pFan0, &pFan1) )
            continue;
        Vec_IntPush( vXors, i );
        Vec_BitWriteEntry( vXorIns, Gia_ObjId(p, Gia_Regular(pFan0)), 1 );
        Vec_BitWriteEntry( vXorIns, Gia_ObjId(p, Gia_Regular(pFan1)), 1 );
    }
    // collect XORs that not inputs of other XORs
    Vec_IntForEachEntry( vXors, Entry, i )
        if ( !Vec_BitEntry(vXorIns, Entry) )
            Vec_IntWriteEntry( vXors, k++, Entry );
    Vec_IntShrink( vXors, k );
    Vec_BitFree( vXorIns );
    return vXors;
}

Vec_Int_t * Acec_StructAssignRanks( Gia_Man_t * p, Vec_Int_t * vXorRoots )
{
    Vec_Int_t * vDoubles = Vec_IntAlloc( 100 );
    Gia_Obj_t * pFan0, * pFan1, * pObj; 
    int i, k, Fanins[2], Entry, Rank;
    // map roots into their ranks
    Vec_Int_t * vRanks = Vec_IntStartFull( Gia_ManObjNum(p) ); 
    Vec_IntForEachEntry( vXorRoots, Entry, i )
        Vec_IntWriteEntry( vRanks, Entry, i );
    // map nodes into their ranks
    Gia_ManForEachAndReverse( p, pObj, i )
    {
        if ( !Gia_ObjRecognizeExor(pObj, &pFan0, &pFan1) )
            continue;
        Rank = Vec_IntEntry( vRanks, i );
        // skip XORs that are not part of any tree
        if ( Rank == -1 )
            continue;
        // iterate through XOR inputs
        Fanins[0] = Gia_ObjId(p, Gia_Regular(pFan0));
        Fanins[1] = Gia_ObjId(p, Gia_Regular(pFan1));
        for ( k = 0; k < 2; k++ )
        {
            Entry = Vec_IntEntry( vRanks, Fanins[k] );
            if ( Entry == Rank ) // the same tree -- allow fanout in this tree
                continue;
            if ( Entry == -1 )
                Vec_IntWriteEntry( vRanks, Fanins[k], Rank );
            else
                Vec_IntPush( vDoubles, Fanins[k] );
            if ( Entry != -1 && Gia_ObjIsAnd(Gia_ManObj(p, Fanins[k])))
            printf( "Xor node %d belongs to Tree %d and Tree %d.\n", Fanins[k], Entry, Rank );
        }
    }
    // remove duplicated entries
    Vec_IntForEachEntry( vDoubles, Entry, i )
        Vec_IntWriteEntry( vRanks, Entry, -1 );
    Vec_IntFree( vDoubles );
    return vRanks;
}

Vec_Wec_t * Acec_FindTreeLeaves( Gia_Man_t * p, Vec_Int_t * vXorRoots, Vec_Int_t * vRanks )
{
    Vec_Bit_t * vMapXors = Vec_BitStart( Gia_ManObjNum(p) );
    Vec_Wec_t * vTreeLeaves = Vec_WecStart( Vec_IntSize(vXorRoots) );
    Gia_Obj_t * pFan0, * pFan1, * pObj; 
    int i, k, Fanins[2], Rank;
    Gia_ManForEachAnd( p, pObj, i )
    {
        if ( !Gia_ObjRecognizeExor(pObj, &pFan0, &pFan1) )
            continue;
        Vec_BitWriteEntry( vMapXors, i, 1 );
        Rank = Vec_IntEntry( vRanks, i );
        // skip XORs that are not part of any tree
        if ( Rank == -1 )
            continue;
        // iterate through XOR inputs
        Fanins[0] = Gia_ObjId(p, Gia_Regular(pFan0));
        Fanins[1] = Gia_ObjId(p, Gia_Regular(pFan1));
        for ( k = 0; k < 2; k++ )
        {
            if ( Vec_BitEntry(vMapXors, Fanins[k]) )
            {
                assert( Rank == Vec_IntEntry(vRanks, Fanins[k]) );
                continue;
            }
            Vec_WecPush( vTreeLeaves, Rank, Fanins[k] );
        }
    }
    Vec_BitFree( vMapXors );
    return vTreeLeaves;
}

Vec_Int_t * Acec_FindShadows( Gia_Man_t * p, Vec_Int_t * vRanks )
{
    Vec_Int_t * vShadows = Vec_IntDup( vRanks );
    Gia_Obj_t * pObj; int i, Shad0, Shad1;
    Gia_ManForEachCi( p, pObj, i )
        Vec_IntWriteEntry( vShadows, Gia_ObjId(p, pObj), -1 );
    Gia_ManForEachAnd( p, pObj, i )
    {
        if ( Vec_IntEntry(vShadows, i) >= 0 )
            continue;
        Shad0 = Vec_IntEntry(vShadows, Gia_ObjFaninId0(pObj, i));
        Shad1 = Vec_IntEntry(vShadows, Gia_ObjFaninId1(pObj, i));
        if ( Shad0 == Shad1 && Shad0 != -1 )
            Vec_IntWriteEntry(vShadows, i, Shad0);
    }
    return vShadows;
}

int Acec_CollectSupp_rec( Gia_Man_t * p, int iNode, int Rank, Vec_Int_t * vRanks )
{
    Gia_Obj_t * pObj;
    int nSize;
    if ( Gia_ObjIsTravIdCurrentId(p, iNode) )
        return 0;
    Gia_ObjSetTravIdCurrentId(p, iNode);
    pObj = Gia_ManObj(p, iNode);
    assert( Gia_ObjIsAnd(pObj) );
    if ( Vec_IntEntry(vRanks, iNode) == Rank )
        return 1;
    nSize = Acec_CollectSupp_rec( p, Gia_ObjFaninId0(pObj, iNode), Rank, vRanks );
    nSize += Acec_CollectSupp_rec( p, Gia_ObjFaninId1(pObj, iNode), Rank, vRanks );
    return nSize;
}
Vec_Wec_t * Acec_FindNexts( Gia_Man_t * p, Vec_Int_t * vRanks, Vec_Int_t * vShadows, Vec_Wec_t * vTreeLeaves )
{
    Vec_Wec_t * vNexts = Vec_WecStart( Vec_WecSize(vTreeLeaves) );
    Vec_Int_t * vTree;
    int i, k, Node, Fanins[2], Shad0, Shad1, Rank, nSupp;
    Vec_WecForEachLevel( vTreeLeaves, vTree, i )
        Vec_IntForEachEntry( vTree, Node, k )
        {
            Gia_Obj_t * pObj = Gia_ManObj(p, Node);
            if ( !Gia_ObjIsAnd(pObj) )
                continue;
            Fanins[0] = Gia_ObjFaninId0(pObj, Node);
            Fanins[1] = Gia_ObjFaninId1(pObj, Node);
            Shad0 = Vec_IntEntry(vShadows, Fanins[0]);
            Shad1 = Vec_IntEntry(vShadows, Fanins[1]);
            if ( Shad0 != Shad1 || Shad0 == -1 )
                continue;
            // check support size of Node in terms of the shadow of its fanins
            Rank = Vec_IntEntry( vRanks, Node );
            assert( Rank != Shad0 );
            Gia_ManIncrementTravId( p );
            nSupp = Acec_CollectSupp_rec( p, Node, Shad0, vRanks );
            assert( nSupp > 1 );
            if ( nSupp > 3 )
                continue;
            Vec_IntPushUniqueOrder( Vec_WecEntry(vNexts, Shad0), Rank );
        }
    return vNexts;
}

void Acec_StructTest( Gia_Man_t * p )
{
}

 
 
ABC_NAMESPACE_IMPL_END