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