acecPa.c

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

  FileName    [acecPa.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [CEC for arithmetic circuits.]

  Synopsis    [Core procedures.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

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

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

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

ABC_NAMESPACE_IMPL_START

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


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

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Pas_ManVerifyPhaseOne_rec( Gia_Man_t * p, Gia_Obj_t * pObj )
{
    int Truth0, Truth1;
    if ( Gia_ObjIsTravIdCurrent(p, pObj) )
        return pObj->Value;
    Gia_ObjSetTravIdCurrent(p, pObj);
    assert( Gia_ObjIsAnd(pObj) );
    assert( !Gia_ObjIsXor(pObj) );
    Truth0 = Pas_ManVerifyPhaseOne_rec( p, Gia_ObjFanin0(pObj) );
    Truth1 = Pas_ManVerifyPhaseOne_rec( p, Gia_ObjFanin1(pObj) );
    Truth0 = Gia_ObjFaninC0(pObj) ? 0xFF & ~Truth0 : Truth0;
    Truth1 = Gia_ObjFaninC1(pObj) ? 0xFF & ~Truth1 : Truth1;
    return (pObj->Value = Truth0 & Truth1);
}
void Pas_ManVerifyPhaseOne( Gia_Man_t * p, Vec_Int_t * vAdds, int iBox, Vec_Bit_t * vPhase )
{
    Gia_Obj_t * pObj;
    unsigned TruthXor, TruthMaj, Truths[3] = { 0xAA, 0xCC, 0xF0 };
    int k, iObj, fFadd = Vec_IntEntry(vAdds, 6*iBox+2) > 0;

    if ( !fFadd )
        return;

    Gia_ManIncrementTravId( p );
    for ( k = 0; k < 3; k++ )
    {
        iObj = Vec_IntEntry( vAdds, 6*iBox+k );
        if ( iObj == 0 )
            continue;
        pObj = Gia_ManObj( p, iObj );
        pObj->Value = Vec_BitEntry(vPhase, iObj) ? 0xFF & ~Truths[k] : Truths[k];
        Gia_ObjSetTravIdCurrent( p, pObj );
    }

    iObj = Vec_IntEntry( vAdds, 6*iBox+3 );
    TruthXor = Pas_ManVerifyPhaseOne_rec( p, Gia_ManObj(p, iObj) );
    TruthXor = Vec_BitEntry(vPhase, iObj) ? 0xFF & ~TruthXor : TruthXor;

    iObj = Vec_IntEntry( vAdds, 6*iBox+4 );
    TruthMaj = Pas_ManVerifyPhaseOne_rec( p, Gia_ManObj(p, iObj) );
    TruthMaj = Vec_BitEntry(vPhase, iObj) ? 0xFF & ~TruthMaj : TruthMaj;

    if ( fFadd ) // FADD
    {
        if ( TruthXor != 0x96 )
            printf( "Fadd %d sum is wrong.\n", iBox );
        if ( TruthMaj != 0xE8 )
            printf( "Fadd %d carry is wrong.\n", iBox );
    }
    else
    {
        if ( TruthXor != 0x66 )
            printf( "Hadd %d sum is wrong.\n", iBox );
        if ( TruthMaj != 0x88 )
            printf( "Hadd %d carry is wrong.\n", iBox );
    }
}
void Pas_ManVerifyPhase( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Int_t * vOrder, Vec_Bit_t * vPhase )
{
    int k, iBox;
    Vec_IntForEachEntry( vOrder, iBox, k )
        Pas_ManVerifyPhaseOne( p, vAdds, iBox, vPhase );
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Pas_ManPhase_rec( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Int_t * vMap, Gia_Obj_t * pObj, int fPhase, Vec_Bit_t * vPhase, Vec_Bit_t * vConstPhase )
{
    int k, iBox, iXor, Sign, fXorPhase;
    assert( pObj != Gia_ManConst0(p) );
    if ( Gia_ObjIsTravIdCurrent(p, pObj) )
        return;
    Gia_ObjSetTravIdCurrent(p, pObj);
    if ( fPhase )
        Vec_BitWriteEntry( vPhase, Gia_ObjId(p, pObj), fPhase );
    if ( !Gia_ObjIsAnd(pObj) )
        return;
    iBox = Vec_IntEntry( vMap, Gia_ObjId(p, pObj) );
    if ( iBox == -1 )
        return;
    iXor = Vec_IntEntry( vAdds, 6*iBox+3 );
    Sign = Vec_IntEntry( vAdds, 6*iBox+5 );
    fXorPhase = ((Sign >> 3) & 1);
    // remember complemented HADD
    if ( Vec_IntEntry(vAdds, 6*iBox+2) == 0 && fPhase )
        Vec_BitWriteEntry( vConstPhase, iBox, 1 );
    for ( k = 0; k < 3; k++ )
    {
        int iObj = Vec_IntEntry( vAdds, 6*iBox+k );
        int fPhaseThis = ((Sign >> k) & 1) ^ fPhase;
        fXorPhase ^= fPhaseThis;
        if ( iObj == 0 )
            continue;
        Pas_ManPhase_rec( p, vAdds, vMap, Gia_ManObj(p, iObj), fPhaseThis, vPhase, vConstPhase );
    }
    Vec_BitWriteEntry( vPhase, iXor, fXorPhase );
}
Vec_Bit_t * Pas_ManPhase( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Int_t * vMap, Vec_Int_t * vRoots, Vec_Bit_t ** pvConstPhase )
{
    Vec_Bit_t * vPhase = Vec_BitStart( Vec_IntSize(vMap) );
    Vec_Bit_t * vConstPhase = Vec_BitStart( Vec_IntSize(vAdds)/6 );
    int i, iRoot;
    Gia_ManIncrementTravId( p );
    Vec_IntForEachEntry( vRoots, iRoot, i )
        Pas_ManPhase_rec( p, vAdds, vMap, Gia_ManObj(p, iRoot), 1, vPhase, vConstPhase );
    *pvConstPhase = vConstPhase;
    return vPhase;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Pas_ManComputeCuts( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Int_t * vOrder, Vec_Int_t * vIns, Vec_Int_t * vOuts )
{
    Vec_Bit_t * vUnique = Vec_BitStart( Gia_ManObjNum(p) );
    Vec_Bit_t * vUsed = Vec_BitStart( Gia_ManObjNum(p) );
    Vec_Int_t * vMap = Vec_IntStartFull( Gia_ManObjNum(p) );
    Vec_Int_t * vRoots = Vec_IntAlloc( 100 );
    Vec_Bit_t * vPhase, * vConstPhase;
    int i, k, Entry, nTrees;

    // map carries into adder indexes and mark driven nodes
    Vec_IntForEachEntry( vOrder, i, k )
    {
        int Carry = Vec_IntEntry(vAdds, 6*i+4);
        if ( Vec_BitEntry(vUnique, Carry) )
            printf( "Carry %d participates more than once.\n", Carry );
        Vec_BitWriteEntry( vUnique, Carry, 1 );
        Vec_IntWriteEntry( vMap, Carry, i );
        // mark driven 
        Vec_BitWriteEntry( vUsed, Vec_IntEntry(vAdds, 6*i+0), 1 );
        Vec_BitWriteEntry( vUsed, Vec_IntEntry(vAdds, 6*i+1), 1 );
        Vec_BitWriteEntry( vUsed, Vec_IntEntry(vAdds, 6*i+2), 1 );
    }
    // collect carries that do not drive other adders
    for ( i = 0; i < Gia_ManObjNum(p); i++ )
        if ( Vec_BitEntry(vUnique, i) && !Vec_BitEntry(vUsed, i) )
            Vec_IntPush( vRoots, i );
    nTrees = Vec_IntSize( vRoots );

    Vec_IntPrint( vRoots );

    // compute phases
    if ( Vec_IntSize(vRoots) > 0 )
    {
        int nCompls = 0;

        vPhase = Pas_ManPhase( p, vAdds, vMap, vRoots, &vConstPhase );
        Pas_ManVerifyPhase( p, vAdds, vOrder, vPhase );

        printf( "Outputs: " );
        Vec_IntForEachEntry( vOuts, Entry, i )
            printf( "%d(%d) ", Entry, Vec_BitEntry(vPhase, Entry) );
        printf( "\n" );

        printf( "Inputs: " );
        Vec_IntForEachEntry( vIns, Entry, i )
        {
            printf( "%d(%d) ", Entry, Vec_BitEntry(vPhase, Entry) );
            nCompls += Vec_BitEntry(vPhase, Entry);
        }
        printf( "   Compl = %d\n", nCompls );

        Vec_BitFreeP( &vPhase );
        Vec_BitFreeP( &vConstPhase );
    }

    Vec_IntFree( vRoots );
    Vec_IntFree( vMap );
    Vec_BitFree( vUnique );
    Vec_BitFree( vUsed );
    return nTrees;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Pas_ManComputeCutsTest( Gia_Man_t * p )
{
    abctime clk = Abc_Clock();
    Vec_Int_t * vAdds = Ree_ManComputeCuts( p, NULL, 1 );
    Vec_Int_t * vIns, * vOuts;
    Vec_Int_t * vOrder = Gia_PolynCoreOrder( p, vAdds, NULL, &vIns, &vOuts );
    int nTrees, nFadds = Ree_ManCountFadds( vAdds );
    //Ree_ManPrintAdders( vAdds, 1 );
    printf( "Detected %d FAs and %d HAs.  Collected %d adders.  ", nFadds, Vec_IntSize(vAdds)/6-nFadds, Vec_IntSize(vOrder) );
    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
    // detect trees
    clk = Abc_Clock();
    nTrees = Pas_ManComputeCuts( p, vAdds, vOrder, vIns, vOuts );
    Vec_IntFree( vAdds );
    Vec_IntFree( vOrder );
    Vec_IntFree( vIns );
    Vec_IntFree( vOuts );

    printf( "Detected %d adder trees. ", nTrees );
    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
}

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


ABC_NAMESPACE_IMPL_END