diff options
| -rw-r--r-- | abclib.dsp | 8 | ||||
| -rw-r--r-- | src/proof/acec/acecPo.c | 564 | ||||
| -rw-r--r-- | src/proof/acec/acecRe.c | 436 |
3 files changed, 1008 insertions, 0 deletions
@@ -5371,10 +5371,18 @@ SOURCE=.\src\proof\acec\acecOrder.c # End Source File # Begin Source File +SOURCE=.\src\proof\acec\acecPo.c +# End Source File +# Begin Source File + SOURCE=.\src\proof\acec\acecPolyn.c # End Source File # Begin Source File +SOURCE=.\src\proof\acec\acecRe.c +# End Source File +# Begin Source File + SOURCE=.\src\proof\acec\acecUtil.c # End Source File # End Group diff --git a/src/proof/acec/acecPo.c b/src/proof/acec/acecPo.c new file mode 100644 index 00000000..96e40405 --- /dev/null +++ b/src/proof/acec/acecPo.c @@ -0,0 +1,564 @@ +/**CFile**************************************************************** + + FileName [acecPo.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: acecPo.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "acecInt.h" +#include "misc/vec/vecWec.h" +#include "misc/vec/vecHsh.h" + +ABC_NAMESPACE_IMPL_START + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Prints polynomial.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Gia_PolynPrintMono( Vec_Int_t * vConst, Vec_Int_t * vMono ) +{ + int k, Entry; + Vec_IntForEachEntry( vConst, Entry, k ) + printf( "%s2^%d", Entry < 0 ? "-" : "+", Abc_AbsInt(Entry)-1 ); + Vec_IntForEachEntry( vMono, Entry, k ) + printf( " * %d", Entry ); + printf( "\n" ); +} +void Gia_PolynPrint( Vec_Wec_t * vPolyn ) +{ + Vec_Int_t * vConst, * vMono; int i; + printf( "Polynomial with %d monomials:\n", Vec_WecSize(vPolyn)/2 ); + for ( i = 0; i < Vec_WecSize(vPolyn)/2; i++ ) + { + vConst = Vec_WecEntry( vPolyn, 2*i+0 ); + vMono = Vec_WecEntry( vPolyn, 2*i+1 ); + Gia_PolynPrintMono( vConst, vMono ); + } +} +void Gia_PolynPrintStats( Vec_Wec_t * vPolyn ) +{ + Vec_Int_t * vConst, * vCountsP, * vCountsN; + int i, Entry, Max = 0; + printf( "Polynomial with %d monomials:\n", Vec_WecSize(vPolyn)/2 ); + for ( i = 0; i < Vec_WecSize(vPolyn)/2; i++ ) + { + vConst = Vec_WecEntry( vPolyn, 2*i+0 ); + Max = Abc_MaxInt( Max, Abc_AbsInt(Abc_AbsInt(Vec_IntEntry(vConst, 0))) ); + } + vCountsP = Vec_IntStart( Max + 1 ); + vCountsN = Vec_IntStart( Max + 1 ); + for ( i = 0; i < Vec_WecSize(vPolyn)/2; i++ ) + { + vConst = Vec_WecEntry( vPolyn, 2*i+0 ); + Entry = Vec_IntEntry(vConst, 0); + if ( Entry > 0 ) + Vec_IntAddToEntry( vCountsP, Entry, 1 ); + else + Vec_IntAddToEntry( vCountsN, -Entry, 1 ); + } + Vec_IntForEachEntry( vCountsN, Entry, i ) + if ( Entry ) + printf( "-2^%d appears %d times\n", Abc_AbsInt(i)-1, Entry ); + Vec_IntForEachEntry( vCountsP, Entry, i ) + if ( Entry ) + printf( "+2^%d appears %d times\n", Abc_AbsInt(i)-1, Entry ); + Vec_IntFree( vCountsP ); + Vec_IntFree( vCountsN ); +} + +/**Function************************************************************* + + Synopsis [Collects polynomial.] + + Description [Collects non-trivial monomials in the increasing order + of the absolute value of the their first coefficients.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Wec_t * Gia_PolynGetResult( Hsh_VecMan_t * pHashC, Hsh_VecMan_t * pHashM, Vec_Int_t * vCoefs ) +{ + Vec_Int_t * vClass, * vLevel, * vArray; + Vec_Wec_t * vPolyn, * vSorted; + int i, k, iConst, iMono; + // find the largest + int nLargest = 0, nNonConst = 0; + Vec_IntForEachEntry( vCoefs, iConst, iMono ) + { + //Vec_IntPrint( Hsh_VecReadEntry(pHashM, iMono) ); + if ( iConst == 0 ) + continue; + vArray = Hsh_VecReadEntry( pHashC, iConst ); + nLargest = Abc_MaxInt( nLargest, Abc_AbsInt(Vec_IntEntry(vArray, 0)) ); + nNonConst++; + } + // sort by the size of the largest coefficient + vSorted = Vec_WecStart( nLargest+1 ); + Vec_IntForEachEntry( vCoefs, iConst, iMono ) + { + if ( iConst == 0 ) + continue; + vArray = Hsh_VecReadEntry( pHashC, iConst ); + vLevel = Vec_WecEntry( vSorted, Abc_AbsInt(Vec_IntEntry(vArray, 0)) ); + Vec_IntPushTwo( vLevel, iConst, iMono ); + } + // reload in the given order + vPolyn = Vec_WecAlloc( 2*nNonConst ); + Vec_WecForEachLevel( vSorted, vClass, i ) + { + Vec_IntForEachEntryDouble( vClass, iConst, iMono, k ) + { + vArray = Hsh_VecReadEntry( pHashC, iConst ); + vLevel = Vec_WecPushLevel( vPolyn ); + Vec_IntGrow( vLevel, Vec_IntSize(vArray) ); + Vec_IntAppend( vLevel, vArray ); + + vArray = Hsh_VecReadEntry( pHashM, iMono ); + vLevel = Vec_WecPushLevel( vPolyn ); + Vec_IntGrow( vLevel, Vec_IntSize(vArray) ); + Vec_IntAppend( vLevel, vArray ); + } + } + assert( Vec_WecSize(vPolyn) == 2*nNonConst ); + Vec_WecFree( vSorted ); + return vPolyn; +} + + +/**Function************************************************************* + + Synopsis [Derives new constant.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Gia_PolynMergeConstOne( Vec_Int_t * vConst, int New ) +{ + int i, Old; + assert( New != 0 ); + Vec_IntForEachEntry( vConst, Old, i ) + { + assert( Old != 0 ); + if ( Old == New ) // A == B + { + Vec_IntDrop( vConst, i ); + Gia_PolynMergeConstOne( vConst, New > 0 ? New + 1 : New - 1 ); + return; + } + if ( Abc_AbsInt(Old) == Abc_AbsInt(New) ) // A == -B + { + Vec_IntDrop( vConst, i ); + return; + } + if ( Old + New == 1 || Old + New == -1 ) // sign(A) != sign(B) && abs(abs(A)-abs(B)) == 1 + { + int Value = Abc_MinInt( Abc_AbsInt(Old), Abc_AbsInt(New) ); + Vec_IntDrop( vConst, i ); + Gia_PolynMergeConstOne( vConst, (Old + New == 1) ? Value : -Value ); + return; + } + } + Vec_IntPushUniqueOrder( vConst, New ); +} +static inline void Gia_PolynMergeConst( Vec_Int_t * vTempC, Hsh_VecMan_t * pHashC, int iConstAdd ) +{ + int i, New; + Vec_Int_t * vConstAdd = Hsh_VecReadEntry( pHashC, iConstAdd ); + Vec_IntForEachEntry( vConstAdd, New, i ) + { + Gia_PolynMergeConstOne( vTempC, New ); + vConstAdd = Hsh_VecReadEntry( pHashC, iConstAdd ); + } +} +static inline int Gia_PolynBuildAdd( Hsh_VecMan_t * pHashC, Hsh_VecMan_t * pHashM, Vec_Int_t * vCoefs, + Vec_Wec_t * vLit2Mono, Vec_Int_t * vTempC, Vec_Int_t * vTempM ) +{ + int i, iLit, iConst, iConstNew; + int iMono = Hsh_VecManAdd(pHashM, vTempM); + if ( iMono == Vec_IntSize(vCoefs) ) // new monomial + { + // map monomial into a constant + assert( Vec_IntSize(vTempC) > 0 ); + iConst = Hsh_VecManAdd( pHashC, vTempC ); + Vec_IntPush( vCoefs, iConst ); + // map literals into monomial + assert( Vec_IntSize(vTempM) > 0 ); + Vec_IntForEachEntry( vTempM, iLit, i ) + Vec_WecPush( vLit2Mono, iLit, iMono ); + //printf( "New monomial: \n" ); + //Gia_PolynPrintMono( vTempC, vTempM ); + return 1; + } + // this monomial exists + iConst = Vec_IntEntry( vCoefs, iMono ); + if ( iConst ) + Gia_PolynMergeConst( vTempC, pHashC, iConst ); + iConstNew = Hsh_VecManAdd( pHashC, vTempC ); + Vec_IntWriteEntry( vCoefs, iMono, iConstNew ); + //printf( "Old monomial: \n" ); + //Gia_PolynPrintMono( vTempC, vTempM ); + if ( iConst && !iConstNew ) + return -1; + if ( !iConst && iConstNew ) + return 1; + return 0; +} + +/**Function************************************************************* + + Synopsis [Computing for literals.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Gia_PolynHandleOne( Hsh_VecMan_t * pHashC, Hsh_VecMan_t * pHashM, Vec_Int_t * vCoefs, + Vec_Wec_t * vLit2Mono, Vec_Int_t * vTempC, Vec_Int_t * vTempM, + int iMono, int iLitOld, int iLitNew0, int iLitNew1 ) +{ + int status, iConst = Vec_IntEntry( vCoefs, iMono ); + Vec_Int_t * vArrayC = Hsh_VecReadEntry( pHashC, iConst ); + Vec_Int_t * vArrayM = Hsh_VecReadEntry( pHashM, iMono ); + // create new monomial + Vec_IntClear( vTempM ); + Vec_IntAppend( vTempM, vArrayM ); + status = Vec_IntRemove( vTempM, iLitOld ); + assert( status ); + // create new monomial + if ( iLitNew0 == -1 && iLitNew1 == -1 ) // no new lit - the same const + Vec_IntAppendMinus( vTempC, vArrayC, 0 ); + else if ( iLitNew0 > -1 && iLitNew1 == -1 ) // one new lit - opposite const + { + Vec_IntAppendMinus( vTempC, vArrayC, 1 ); + Vec_IntPushUniqueOrder( vTempM, iLitNew0 ); + } + else if ( iLitNew0 > -1 && iLitNew1 > -1 ) // both new lit - the same const + { + Vec_IntAppendMinus( vTempC, vArrayC, 0 ); + Vec_IntPushUniqueOrder( vTempM, iLitNew0 ); + Vec_IntPushUniqueOrder( vTempM, iLitNew1 ); + } + else assert( 0 ); + return Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC, vTempM ); +} + +Vec_Wec_t * Gia_PolynBuildNew2( Gia_Man_t * pGia, Vec_Int_t * vRootLits, Vec_Int_t * vLeaves, Vec_Int_t * vNodes, int fSigned, int fVerbose, int fVeryVerbose ) +{ + abctime clk = Abc_Clock(); + Vec_Wec_t * vPolyn; + Vec_Wec_t * vLit2Mono = Vec_WecStart( 2 * Gia_ManObjNum(pGia) ); // mapping AIG literals into monomials + Hsh_VecMan_t * pHashC = Hsh_VecManStart( 1000 ); // hash table for constants + Hsh_VecMan_t * pHashM = Hsh_VecManStart( 1000 ); // hash table for monomials + Vec_Int_t * vCoefs = Vec_IntAlloc( 1000 ); // monomial coefficients + Vec_Int_t * vTempC = Vec_IntAlloc( 10 ); // temporary array + Vec_Int_t * vTempM = Vec_IntAlloc( 10 ); // temporary array + int i, k, iObj, iLit, iMono, nMonos = 0, nBuilds = 0; + + // add 0-constant and 1-monomial + Hsh_VecManAdd( pHashC, vTempC ); + Hsh_VecManAdd( pHashM, vTempM ); + Vec_IntPush( vCoefs, 0 ); + + // create output signature + Vec_IntForEachEntry( vRootLits, iLit, i ) + { + Vec_IntFill( vTempC, 1, (fSigned && i == Vec_IntSize(vRootLits)-1) ? -i-1 : i+1 ); + Vec_IntFill( vTempM, 1, iLit ); + nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC, vTempM ); + nBuilds++; + } + + // perform construction for internal nodes + Vec_IntForEachEntryReverse( vNodes, iObj, i ) + { + Gia_Obj_t * pObj = Gia_ManObj( pGia, iObj ); + int iLits[2] = { Abc_Var2Lit(iObj, 0), Abc_Var2Lit(iObj, 1) }; + int iFans[2] = { Gia_ObjFaninLit0(pObj, iObj), Gia_ObjFaninLit1(pObj, iObj) }; + // add inverter + Vec_Int_t * vArray = Vec_WecEntry( vLit2Mono, iLits[1] ); + Vec_IntForEachEntry( vArray, iMono, k ) + if ( Vec_IntEntry(vCoefs, iMono) > 0 ) + { + nMonos += Gia_PolynHandleOne( pHashC, pHashM, vCoefs, vLit2Mono, vTempC, vTempM, iMono, iLits[1], -1, -1 ); + nMonos += Gia_PolynHandleOne( pHashC, pHashM, vCoefs, vLit2Mono, vTempC, vTempM, iMono, iLits[1], iLits[0], -1 ); + Vec_IntWriteEntry( vCoefs, iMono, 0 ); + nMonos--; + nBuilds++; + nBuilds++; + } + // add AND gate + vArray = Vec_WecEntry( vLit2Mono, iLits[0] ); + Vec_IntForEachEntry( vArray, iMono, k ) + if ( Vec_IntEntry(vCoefs, iMono) > 0 ) + { + nMonos += Gia_PolynHandleOne( pHashC, pHashM, vCoefs, vLit2Mono, vTempC, vTempM, iMono, iLits[0], iFans[0], iFans[1] ); + Vec_IntWriteEntry( vCoefs, iMono, 0 ); + nMonos--; + nBuilds++; + } + //printf( "Obj %5d : nMonos = %6d nUsed = %6d\n", iObj, nBuilds, nMonos ); + } + + // complement leave nodes + Vec_IntForEachEntry( vLeaves, iObj, i ) + { + Gia_Obj_t * pObj = Gia_ManObj( pGia, iObj ); + int iLits[2] = { Abc_Var2Lit(iObj, 0), Abc_Var2Lit(iObj, 1) }; + // add inverter + Vec_Int_t * vArray = Vec_WecEntry( vLit2Mono, iLits[1] ); + Vec_IntForEachEntry( vArray, iMono, k ) + if ( Vec_IntEntry(vCoefs, iMono) > 0 ) + { + nMonos += Gia_PolynHandleOne( pHashC, pHashM, vCoefs, vLit2Mono, vTempC, vTempM, iMono, iLits[1], -1, -1 ); + nMonos += Gia_PolynHandleOne( pHashC, pHashM, vCoefs, vLit2Mono, vTempC, vTempM, iMono, iLits[1], iLits[0], -1 ); + Vec_IntWriteEntry( vCoefs, iMono, 0 ); + nMonos--; + nBuilds++; + } + } + + // get the results + vPolyn = Gia_PolynGetResult( pHashC, pHashM, vCoefs ); + + printf( "HashC = %d. HashM = %d. Total = %d. Left = %d. Used = %d. ", + Hsh_VecSize(pHashC), Hsh_VecSize(pHashM), nBuilds, nMonos, Vec_WecSize(vPolyn)/2 ); + Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); + + Vec_IntFree( vTempC ); + Vec_IntFree( vTempM ); + Vec_IntFree( vCoefs ); + Vec_WecFree( vLit2Mono ); + Hsh_VecManStop( pHashC ); + Hsh_VecManStop( pHashM ); + return vPolyn; +} + + +/**Function************************************************************* + + Synopsis [Computing for objects.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline void Gia_PolynPrepare2( Vec_Int_t * vTempC[2], Vec_Int_t * vTempM[2], int iObj, int iCst ) +{ + Vec_IntFill( vTempC[0], 1, iCst ); + Vec_IntFill( vTempC[1], 1, -iCst ); + Vec_IntClear( vTempM[0] ); + Vec_IntFill( vTempM[1], 1, iObj ); +} +static inline void Gia_PolynPrepare4( Vec_Int_t * vTempC[4], Vec_Int_t * vTempM[4], Vec_Int_t * vConst, Vec_Int_t * vMono, int iObj, int iFan0, int iFan1 ) +{ + int i, k, Entry; + for ( i = 0; i < 4; i++ ) + Vec_IntAppendMinus( vTempC[i], vConst, i & 1 ); + for ( i = 0; i < 4; i++ ) + Vec_IntClear( vTempM[i] ); + Vec_IntForEachEntry( vMono, Entry, k ) + if ( Entry != iObj ) + for ( i = 0; i < 4; i++ ) + Vec_IntPush( vTempM[i], Entry ); + Vec_IntPushUniqueOrder( vTempM[1], iFan0 ); + Vec_IntPushUniqueOrder( vTempM[2], iFan1 ); + Vec_IntPushUniqueOrder( vTempM[3], iFan0 ); + Vec_IntPushUniqueOrder( vTempM[3], iFan1 ); +} + +Vec_Wec_t * Gia_PolynBuildNew( Gia_Man_t * pGia, Vec_Int_t * vRootLits, Vec_Int_t * vLeaves, Vec_Int_t * vNodes, int fSigned, int fVerbose, int fVeryVerbose ) +{ + abctime clk = Abc_Clock(); + Vec_Wec_t * vPolyn; + Vec_Wec_t * vLit2Mono = Vec_WecStart( Gia_ManObjNum(pGia) ); // mapping AIG literals into monomials + Hsh_VecMan_t * pHashC = Hsh_VecManStart( 1000 ); // hash table for constants + Hsh_VecMan_t * pHashM = Hsh_VecManStart( 1000 ); // hash table for monomials + Vec_Int_t * vCoefs = Vec_IntAlloc( 1000 ); // monomial coefficients + Vec_Int_t * vTempC[4], * vTempM[4]; // temporary array + int i, k, iObj, iLit, iMono, iConst, nMonos = 0, nBuilds = 0; + for ( i = 0; i < 4; i++ ) + vTempC[i] = Vec_IntAlloc( 10 ); + for ( i = 0; i < 4; i++ ) + vTempM[i] = Vec_IntAlloc( 10 ); + + // add 0-constant and 1-monomial + Hsh_VecManAdd( pHashC, vTempC[0] ); + Hsh_VecManAdd( pHashM, vTempM[0] ); + Vec_IntPush( vCoefs, 0 ); + + // create output signature + Vec_IntForEachEntry( vRootLits, iLit, i ) + { + Gia_PolynPrepare2( vTempC, vTempM, Abc_Lit2Var(iLit), i+1 ); + if ( fSigned && i == Vec_IntSize(vRootLits)-1 ) + { + if ( Abc_LitIsCompl(iLit) ) + { + nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[1], vTempM[0] ); // -C + nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[0], vTempM[1] ); // C * Driver + nBuilds++; + } + else + nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[1], vTempM[1] ); // -C * Driver + } + else + { + if ( Abc_LitIsCompl(iLit) ) + { + nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[0], vTempM[0] ); // C + nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[1], vTempM[1] ); // -C * Driver + nBuilds++; + } + else + nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[0], vTempM[1] ); // C * Driver + } + nBuilds++; + } + + // perform construction for internal nodes + Vec_IntForEachEntryReverse( vNodes, iObj, i ) + { + Gia_Obj_t * pObj = Gia_ManObj( pGia, iObj ); + Vec_Int_t * vArray = Vec_WecEntry( vLit2Mono, iObj ); + Vec_IntForEachEntry( vArray, iMono, k ) + if ( (iConst = Vec_IntEntry(vCoefs, iMono)) > 0 ) + { + Vec_Int_t * vArrayC = Hsh_VecReadEntry( pHashC, iConst ); + Vec_Int_t * vArrayM = Hsh_VecReadEntry( pHashM, iMono ); + Gia_PolynPrepare4( vTempC, vTempM, vArrayC, vArrayM, iObj, Gia_ObjFaninId0(pObj, iObj), Gia_ObjFaninId1(pObj, iObj) ); + if ( Gia_ObjIsXor(pObj) ) + { + } + else if ( Gia_ObjFaninC0(pObj) && Gia_ObjFaninC1(pObj) ) // C * (1 - x) * (1 - y) + { + nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[0], vTempM[0] ); // C * 1 + nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[1], vTempM[1] ); // -C * x + nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[3], vTempM[2] ); // -C * y + nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[2], vTempM[3] ); // C * x * y + nBuilds += 3; + } + else if ( Gia_ObjFaninC0(pObj) && !Gia_ObjFaninC1(pObj) ) // C * (1 - x) * y + { + nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[0], vTempM[2] ); // C * y + nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[1], vTempM[3] ); // -C * x * y + nBuilds += 2; + } + else if ( !Gia_ObjFaninC0(pObj) && Gia_ObjFaninC1(pObj) ) // C * x * (1 - y) + { + nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[0], vTempM[1] ); // C * x + nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[1], vTempM[3] ); // -C * x * y + nBuilds++; + } + else + nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[0], vTempM[3] ); // C * x * y + Vec_IntWriteEntry( vCoefs, iMono, 0 ); + nMonos--; + nBuilds++; + } + //printf( "Obj %5d : nMonos = %6d nUsed = %6d\n", iObj, nBuilds, nMonos ); + } + + // get the results + vPolyn = Gia_PolynGetResult( pHashC, pHashM, vCoefs ); + + printf( "HashC = %d. HashM = %d. Total = %d. Left = %d. Used = %d. ", + Hsh_VecSize(pHashC), Hsh_VecSize(pHashM), nBuilds, nMonos, Vec_WecSize(vPolyn)/2 ); + Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); + + for ( i = 0; i < 4; i++ ) + Vec_IntFree( vTempC[i] ); + for ( i = 0; i < 4; i++ ) + Vec_IntFree( vTempM[i] ); + Vec_IntFree( vCoefs ); + Vec_WecFree( vLit2Mono ); + Hsh_VecManStop( pHashC ); + Hsh_VecManStop( pHashM ); + return vPolyn; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Gia_PolynBuild2Test( Gia_Man_t * pGia ) +{ + Vec_Wec_t * vPolyn; + Vec_Int_t * vRootLits = Vec_IntAlloc( Gia_ManCoNum(pGia) ); + Vec_Int_t * vLeaves = Vec_IntAlloc( Gia_ManCiNum(pGia) ); + Vec_Int_t * vNodes = Vec_IntAlloc( Gia_ManAndNum(pGia) ); + Gia_Obj_t * pObj; + int i; + + Gia_ManForEachObj( pGia, pObj, i ) + if ( Gia_ObjIsCi(pObj) ) + Vec_IntPush( vLeaves, i ); + else if ( Gia_ObjIsAnd(pObj) ) + Vec_IntPush( vNodes, i ); + else if ( Gia_ObjIsCo(pObj) ) + Vec_IntPush( vRootLits, Gia_ObjFaninLit0p(pGia, pObj) ); + + vPolyn = Gia_PolynBuildNew( pGia, vRootLits, vLeaves, vNodes, 0, 0, 0 ); +// printf( "Polynomial has %d monomials.\n", Vec_WecSize(vPolyn)/2 ); +// Gia_PolynPrintStats( vPolyn ); +// Gia_PolynPrint( vPolyn ); + Vec_WecFree( vPolyn ); + + Vec_IntFree( vRootLits ); + Vec_IntFree( vLeaves ); + Vec_IntFree( vNodes ); +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + +ABC_NAMESPACE_IMPL_END + diff --git a/src/proof/acec/acecRe.c b/src/proof/acec/acecRe.c new file mode 100644 index 00000000..1f10d249 --- /dev/null +++ b/src/proof/acec/acecRe.c @@ -0,0 +1,436 @@ +/**CFile**************************************************************** + + FileName [acecRe.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: acecRe.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "acecInt.h" +#include "misc/vec/vecHash.h" +#include "misc/util/utilTruth.h" + +ABC_NAMESPACE_IMPL_START + + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +#define Ree_ForEachCut( pList, pCut, i ) for ( i = 0, pCut = pList + 1; i < pList[0]; i++, pCut += pCut[0] + 2 ) + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Detecting FADDs in the AIG.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Ree_TruthPrecompute() +{ + word Truths[8] = { 0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77 }; + word Truth; + int i; + for ( i = 0; i < 8; i++ ) + { + Truth = Truths[i]; + Truth = Abc_Tt6SwapAdjacent( Truth, 1 ); + Abc_TtPrintHexRev( stdout, &Truth, 3 ); + printf( "\n" ); + } + printf( "\n" ); + for ( i = 0; i < 8; i++ ) + { + Truth = Truths[i]; + Truth = Abc_Tt6SwapAdjacent( Truth, 1 ); + Truth = Abc_Tt6SwapAdjacent( Truth, 0 ); + Abc_TtPrintHexRev( stdout, &Truth, 3 ); + printf( "\n" ); + } + printf( "\n" ); +} + +/**Function************************************************************* + + Synopsis [Detecting FADDs in the AIG.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Ree_ManCutMergeOne( int * pCut0, int * pCut1, int * pCut ) +{ + int i, k; + for ( k = 0; k <= pCut1[0]; k++ ) + pCut[k] = pCut1[k]; + for ( i = 1; i <= pCut0[0]; i++ ) + { + for ( k = 1; k <= pCut1[0]; k++ ) + if ( pCut0[i] == pCut1[k] ) + break; + if ( k <= pCut1[0] ) + continue; + if ( pCut[0] == 3 ) + return 0; + pCut[1+pCut[0]++] = pCut0[i]; + } + assert( pCut[0] == 2 || pCut[0] == 3 ); + if ( pCut[1] > pCut[2] ) + ABC_SWAP( int, pCut[1], pCut[2] ); + assert( pCut[1] < pCut[2] ); + if ( pCut[0] == 2 ) + return 1; + if ( pCut[2] > pCut[3] ) + ABC_SWAP( int, pCut[2], pCut[3] ); + if ( pCut[1] > pCut[2] ) + ABC_SWAP( int, pCut[1], pCut[2] ); + assert( pCut[1] < pCut[2] ); + assert( pCut[2] < pCut[3] ); + return 1; +} +static inline int Ree_ManCutCheckEqual( Vec_Int_t * vCuts, int * pCutNew ) +{ + int * pList = Vec_IntArray( vCuts ); + int i, k, * pCut; + Ree_ForEachCut( pList, pCut, i ) + { + for ( k = 0; k <= pCut[0]; k++ ) + if ( pCut[k] != pCutNew[k] ) + break; + if ( k > pCut[0] ) + return 1; + } + return 0; +} +static inline int Ree_ManCutFind( int iObj, int * pCut ) +{ + if ( pCut[1] == iObj ) return 0; + if ( pCut[2] == iObj ) return 1; + if ( pCut[3] == iObj ) return 2; + assert( 0 ); + return -1; +} +static inline int Ree_ManCutNotFind( int iObj1, int iObj2, int * pCut ) +{ + if ( pCut[3] != iObj1 && pCut[3] != iObj2 ) return 0; + if ( pCut[2] != iObj1 && pCut[2] != iObj2 ) return 1; + if ( pCut[1] != iObj1 && pCut[1] != iObj2 ) return 2; + assert( 0 ); + return -1; +} +static inline int Ree_ManCutTruthOne( int * pCut0, int * pCut ) +{ + int Truth0 = pCut0[pCut0[0]+1]; + int fComp0 = (Truth0 >> 7) & 1; + if ( pCut0[0] == 3 ) + return Truth0; + Truth0 = fComp0 ? ~Truth0 : Truth0; + if ( pCut0[0] == 2 ) + { + int Truths[3][8] = { + { 0x00, 0x11, 0x22, 0x33, 0x44, 0x55, 0x66, 0x77 }, // {0,1,-} + { 0x00, 0x05, 0x0A, 0x0F, 0x50, 0x55, 0x5A, 0x5F }, // {0,-,1} + { 0x00, 0x03, 0x0C, 0x0F, 0x30, 0x33, 0x3C, 0x3F } // {-,0,1} + }; + int Truth = Truths[Ree_ManCutNotFind(pCut0[1], pCut0[2], pCut)][Truth0 & 0x7]; + return 0xFF & (fComp0 ? ~Truth : Truth); + } + if ( pCut0[0] == 1 ) + { + int Truths[3] = { 0x55, 0x33, 0x0F }; + int Truth = Truths[Ree_ManCutFind(pCut0[1], pCut)]; + return 0xFF & (fComp0 ? ~Truth : Truth); + } + assert( 0 ); + return -1; +} +static inline int Ree_ManCutTruth( Gia_Obj_t * pObj, int * pCut0, int * pCut1, int * pCut ) +{ + int Truth0 = Ree_ManCutTruthOne( pCut0, pCut ); + int Truth1 = Ree_ManCutTruthOne( pCut1, pCut ); + Truth0 = Gia_ObjFaninC0(pObj) ? ~Truth0 : Truth0; + Truth1 = Gia_ObjFaninC1(pObj) ? ~Truth1 : Truth1; + return 0xFF & (Gia_ObjIsXor(pObj) ? Truth0 ^ Truth1 : Truth0 & Truth1); +} + +#if 0 + +int Ree_ObjComputeTruth_rec( Gia_Obj_t * pObj ) +{ + int Truth0, Truth1; + if ( pObj->Value ) + return pObj->Value; + assert( Gia_ObjIsAnd(pObj) ); + Truth0 = Ree_ObjComputeTruth_rec( Gia_ObjFanin0(pObj) ); + Truth1 = Ree_ObjComputeTruth_rec( Gia_ObjFanin1(pObj) ); + if ( Gia_ObjIsXor(pObj) ) + return (pObj->Value = (Gia_ObjFaninC0(pObj) ? ~Truth0 : Truth0) ^ (Gia_ObjFaninC1(pObj) ? ~Truth1 : Truth1)); + else + return (pObj->Value = (Gia_ObjFaninC0(pObj) ? ~Truth0 : Truth0) & (Gia_ObjFaninC1(pObj) ? ~Truth1 : Truth1)); +} +void Ree_ObjCleanTruth_rec( Gia_Obj_t * pObj ) +{ + if ( !pObj->Value ) + return; + pObj->Value = 0; + if ( !Gia_ObjIsAnd(pObj) ) + return; + Ree_ObjCleanTruth_rec( Gia_ObjFanin0(pObj) ); + Ree_ObjCleanTruth_rec( Gia_ObjFanin1(pObj) ); +} +int Ree_ObjComputeTruth( Gia_Man_t * p, int iObj, int * pCut ) +{ + unsigned Truth, Truths[3] = { 0xAA, 0xCC, 0xF0 }; int i; + for ( i = 1; i <= pCut[0]; i++ ) + Gia_ManObj(p, pCut[i])->Value = Truths[i-1]; + Truth = 0xFF & Ree_ObjComputeTruth_rec( Gia_ManObj(p, iObj) ); + Ree_ObjCleanTruth_rec( Gia_ManObj(p, iObj) ); + return Truth; +} + +#endif + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Ree_ManCutPrint( int * pCut, int Count, word Truth ) +{ + int c; + printf( "%d : ", Count ); + for ( c = 1; c <= pCut[0]; c++ ) + printf( "%3d ", pCut[c] ); + for ( ; c <= 4; c++ ) + printf( " " ); + printf( "0x" ); + Abc_TtPrintHexRev( stdout, &Truth, 3 ); + printf( "\n" ); +} +void Ree_ManCutMerge( Gia_Man_t * p, int iObj, int * pList0, int * pList1, Vec_Int_t * vCuts, Hash_IntMan_t * pHash, Vec_Int_t * vData ) +{ + int fVerbose = 0; + int i, k, c, Value, Truth, TruthC, * pCut0, * pCut1, pCut[5], Count = 0; + if ( fVerbose ) + printf( "Object %d\n", iObj ); + Vec_IntFill( vCuts, 2, 1 ); + Vec_IntPush( vCuts, iObj ); + Vec_IntPush( vCuts, 0xAA ); + Ree_ForEachCut( pList0, pCut0, i ) + Ree_ForEachCut( pList1, pCut1, k ) + { + if ( !Ree_ManCutMergeOne(pCut0, pCut1, pCut) ) + continue; + if ( Ree_ManCutCheckEqual(vCuts, pCut) ) + continue; + Truth = TruthC = Ree_ManCutTruth(Gia_ManObj(p, iObj), pCut0, pCut1, pCut); + //assert( Truth == Ree_ObjComputeTruth(p, iObj, pCut) ); + Vec_IntAddToEntry( vCuts, 0, 1 ); + for ( c = 0; c <= pCut[0]; c++ ) + Vec_IntPush( vCuts, pCut[c] ); + Vec_IntPush( vCuts, Truth ); + if ( Truth & 0x80 ) + Truth = 0xFF & ~Truth; + if ( (Truth == 0x66 || Truth == 0x11 || Truth == 0x22 || Truth == 0x44 || Truth == 0x77) && pCut[0] == 2 ) + { + assert( pCut[0] == 2 ); + Value = Hsh_Int3ManInsert( pHash, pCut[1], pCut[2], 0 ); + Vec_IntPushThree( vData, iObj, Value, TruthC ); + } + else if ( Truth == 0x69 || Truth == 0x17 || Truth == 0x2B || Truth == 0x4D || Truth == 0x71 ) + { + assert( pCut[0] == 3 ); + Value = Hsh_Int3ManInsert( pHash, pCut[1], pCut[2], pCut[3] ); + Vec_IntPushThree( vData, iObj, Value, TruthC ); + } + if ( fVerbose ) + Ree_ManCutPrint( pCut, ++Count, TruthC ); + } +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Vec_Int_t * Ree_ManDeriveAdds( Hash_IntMan_t * p, Vec_Int_t * vData ) +{ + int i, j, k, iObj, iObj2, Value, Truth, CountX, CountM, Index = 0; + int nEntries = Hash_IntManEntryNum(p); + Vec_Int_t * vAdds = Vec_IntAlloc( 1000 ); + Vec_Int_t * vXors = Vec_IntStart( nEntries + 1 ); + Vec_Int_t * vMajs = Vec_IntStart( nEntries + 1 ); + Vec_Int_t * vIndex = Vec_IntStartFull( nEntries + 1 ); + Vec_Int_t * vIndexRev = Vec_IntAlloc( 1000 ); + Vec_Wec_t * vXorMap, * vMajMap; + Vec_IntForEachEntryTriple( vData, iObj, Value, Truth, i ) + { + assert( Value <= nEntries ); + if ( Truth == 0x66 || Truth == 0x99 || Truth == 0x69 || Truth == 0x96 ) + Vec_IntAddToEntry( vXors, Value, 1 ); + else + Vec_IntAddToEntry( vMajs, Value, 1 ); + } + // remap these into indexes + Vec_IntForEachEntryTwo( vXors, vMajs, CountX, CountM, i ) + if ( CountX && CountM ) + { + Vec_IntPush( vIndexRev, i ); + Vec_IntWriteEntry( vIndex, i, Index++ ); + } + Vec_IntFree( vXors ); + Vec_IntFree( vMajs ); + printf( "Detected %d shared cuts among %d hashed cuts.\n", Index, nEntries ); + // collect nodes + vXorMap = Vec_WecStart( Index ); + vMajMap = Vec_WecStart( Index ); + Vec_IntForEachEntryTriple( vData, iObj, Value, Truth, i ) + { + Index = Vec_IntEntry( vIndex, Value ); + if ( Index == -1 ) + continue; + if ( Truth == 0x66 || Truth == 0x99 || Truth == 0x69 || Truth == 0x96 ) + Vec_WecPush( vXorMap, Index, iObj ); + else + Vec_WecPush( vMajMap, Index, iObj ); + } + Vec_IntFree( vIndex ); + // create pairs + Vec_IntForEachEntry( vIndexRev, Value, i ) + { + Vec_Int_t * vXorOne = Vec_WecEntry( vXorMap, i ); + Vec_Int_t * vMajOne = Vec_WecEntry( vMajMap, i ); + Hash_IntObj_t * pObj = Hash_IntObj( p, Value ); + Vec_IntForEachEntry( vXorOne, iObj, j ) + Vec_IntForEachEntry( vMajOne, iObj2, k ) + { + Vec_IntPushThree( vAdds, pObj->iData0, pObj->iData1, pObj->iData2 ); + Vec_IntPushTwo( vAdds, iObj, iObj2 ); + } + } + Vec_IntFree( vIndexRev ); + Vec_WecFree( vXorMap ); + Vec_WecFree( vMajMap ); + return vAdds; +} +Vec_Int_t * Ree_ManComputeCuts( Gia_Man_t * p, int fVerbose ) +{ + Gia_Obj_t * pObj; + int * pList0, * pList1, i, nCuts = 0; + Hash_IntMan_t * pHash = Hash_IntManStart( 1000 ); + Vec_Int_t * vAdds; + Vec_Int_t * vTemp = Vec_IntAlloc( 1000 ); + Vec_Int_t * vData = Vec_IntAlloc( 1000 ); + Vec_Int_t * vCuts = Vec_IntAlloc( 30 * Gia_ManAndNum(p) ); + Vec_IntFill( vCuts, Gia_ManObjNum(p), 0 ); + Gia_ManCleanValue( p ); + Gia_ManForEachCi( p, pObj, i ) + { + Vec_IntWriteEntry( vCuts, Gia_ObjId(p, pObj), Vec_IntSize(vCuts) ); + Vec_IntPush( vCuts, 1 ); + Vec_IntPush( vCuts, 1 ); + Vec_IntPush( vCuts, Gia_ObjId(p, pObj) ); + Vec_IntPush( vCuts, 0xAA ); + } + Gia_ManForEachAnd( p, pObj, i ) + { + pList0 = Vec_IntEntryP( vCuts, Vec_IntEntry(vCuts, Gia_ObjFaninId0(pObj, i)) ); + pList1 = Vec_IntEntryP( vCuts, Vec_IntEntry(vCuts, Gia_ObjFaninId1(pObj, i)) ); + Ree_ManCutMerge( p, i, pList0, pList1, vTemp, pHash, vData ); + Vec_IntWriteEntry( vCuts, i, Vec_IntSize(vCuts) ); + Vec_IntAppend( vCuts, vTemp ); + nCuts += Vec_IntEntry( vTemp, 0 ); + } + if ( fVerbose ) + printf( "Nodes = %d. Cuts = %d. Cuts/Node = %.2f. Ints/Node = %.2f.\n", + Gia_ManAndNum(p), nCuts, 1.0*nCuts/Gia_ManAndNum(p), 1.0*Vec_IntSize(vCuts)/Gia_ManAndNum(p) ); + Vec_IntFree( vTemp ); + Vec_IntFree( vCuts ); + vAdds = Ree_ManDeriveAdds( pHash, vData ); + if ( fVerbose ) + printf( "Adds = %d. Total = %d. Hashed = %d. Hashed/Adds = %.2f.\n", + Vec_IntSize(vAdds)/5, Vec_IntSize(vData)/3, Hash_IntManEntryNum(pHash), 5.0*Hash_IntManEntryNum(pHash)/Vec_IntSize(vAdds) ); + Vec_IntFree( vData ); + Hash_IntManStop( pHash ); + return vAdds; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Ree_ManComputeCutsTest( Gia_Man_t * p ) +{ + abctime clk = Abc_Clock(); + Vec_Int_t * vAdds = Ree_ManComputeCuts( p, 1 ); + int i, Count = 0; + for ( i = 0; 5*i < Vec_IntSize(vAdds); i++ ) + { + if ( Vec_IntEntry(vAdds, 5*i+2) == 0 ) + continue; + Count++; + continue; + printf( "%6d : ", i ); + printf( "%6d ", Vec_IntEntry(vAdds, 5*i+0) ); + printf( "%6d ", Vec_IntEntry(vAdds, 5*i+1) ); + printf( "%6d ", Vec_IntEntry(vAdds, 5*i+2) ); + printf( " -> " ); + printf( "%6d ", Vec_IntEntry(vAdds, 5*i+3) ); + printf( "%6d ", Vec_IntEntry(vAdds, 5*i+4) ); + printf( "\n" ); + } + Vec_IntFree( vAdds ); + printf( "Detected %d FAs and %d HAs. ", Count, Vec_IntSize(vAdds)/5-Count ); + Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + +ABC_NAMESPACE_IMPL_END + |