| /**CFile**************************************************************** |
| |
| FileName [acecPolyn.c] |
| |
| SystemName [ABC: Logic synthesis and verification system.] |
| |
| PackageName [CEC for arithmetic circuits.] |
| |
| Synopsis [Polynomial extraction.] |
| |
| Author [Alan Mishchenko] |
| |
| Affiliation [UC Berkeley] |
| |
| Date [Ver. 1.0. Started - June 20, 2005.] |
| |
| Revision [$Id: acecPolyn.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" |
| #include "misc/vec/vecQue.h" |
| |
| ABC_NAMESPACE_IMPL_START |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// DECLARATIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| /* |
| !a -> 1 - a |
| a & b -> ab |
| a | b -> a + b - ab |
| a ^ b -> a + b - 2ab |
| MUX(a, b, c) -> ab | (1 - a)c = ab + (1-a)c - ab(1-a)c = ab + c - ac |
| |
| !a & b -> (1 - a)b = b - ab |
| a & !b -> a(1 - b) = a - ab |
| !a & !b -> 1 - a - b + ab |
| */ |
| |
| typedef struct Pln_Man_t_ Pln_Man_t; |
| struct Pln_Man_t_ |
| { |
| Gia_Man_t * pGia; // AIG manager |
| Hsh_VecMan_t * pHashC; // hash table for constants |
| Hsh_VecMan_t * pHashM; // hash table for monomials |
| Vec_Que_t * vQue; // queue by largest node |
| Vec_Flt_t * vCounts; // largest node |
| Vec_Int_t * vCoefs; // coefficients for each monomial |
| Vec_Int_t * vTempC[2]; // polynomial representation |
| Vec_Int_t * vTempM[4]; // polynomial representation |
| Vec_Int_t * vOrder; // order of collapsing |
| int nBuilds; // built monomials |
| int nUsed; // used monomials |
| }; |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// FUNCTION DEFINITIONS /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| /**Function************************************************************* |
| |
| Synopsis [Computation manager.] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| Pln_Man_t * Pln_ManAlloc( Gia_Man_t * pGia, Vec_Int_t * vOrder ) |
| { |
| Pln_Man_t * p = ABC_CALLOC( Pln_Man_t, 1 ); |
| p->pGia = pGia; |
| p->pHashC = Hsh_VecManStart( 1000 ); |
| p->pHashM = Hsh_VecManStart( 1000 ); |
| p->vQue = Vec_QueAlloc( 1000 ); |
| p->vCounts = Vec_FltAlloc( 1000 ); |
| p->vCoefs = Vec_IntAlloc( 1000 ); |
| p->vTempC[0] = Vec_IntAlloc( 100 ); |
| p->vTempC[1] = Vec_IntAlloc( 100 ); |
| p->vTempM[0] = Vec_IntAlloc( 100 ); |
| p->vTempM[1] = Vec_IntAlloc( 100 ); |
| p->vTempM[2] = Vec_IntAlloc( 100 ); |
| p->vTempM[3] = Vec_IntAlloc( 100 ); |
| p->vOrder = vOrder ? Vec_IntDup(vOrder) : Vec_IntStartNatural( Gia_ManObjNum(pGia) ); |
| assert( Vec_IntSize(p->vOrder) == Gia_ManObjNum(pGia) ); |
| Vec_QueSetPriority( p->vQue, Vec_FltArrayP(p->vCounts) ); |
| // add 0-constant and 1-monomial |
| Hsh_VecManAdd( p->pHashC, p->vTempC[0] ); |
| Hsh_VecManAdd( p->pHashM, p->vTempM[0] ); |
| Vec_FltPush( p->vCounts, 0 ); |
| Vec_IntPush( p->vCoefs, 0 ); |
| return p; |
| } |
| void Pln_ManStop( Pln_Man_t * p ) |
| { |
| Hsh_VecManStop( p->pHashC ); |
| Hsh_VecManStop( p->pHashM ); |
| Vec_QueFree( p->vQue ); |
| Vec_FltFree( p->vCounts ); |
| Vec_IntFree( p->vCoefs ); |
| Vec_IntFree( p->vTempC[0] ); |
| Vec_IntFree( p->vTempC[1] ); |
| Vec_IntFree( p->vTempM[0] ); |
| Vec_IntFree( p->vTempM[1] ); |
| Vec_IntFree( p->vTempM[2] ); |
| Vec_IntFree( p->vTempM[3] ); |
| Vec_IntFree( p->vOrder ); |
| ABC_FREE( p ); |
| } |
| int Pln_ManCompare3( int * pData0, int * pData1 ) |
| { |
| if ( pData0[0] < pData1[0] ) return -1; |
| if ( pData0[0] > pData1[0] ) return 1; |
| if ( pData0[1] < pData1[1] ) return -1; |
| if ( pData0[1] > pData1[1] ) return 1; |
| return 0; |
| } |
| void Pln_ManPrintFinal( Pln_Man_t * p, int fVerbose, int fVeryVerbose ) |
| { |
| Vec_Int_t * vArray; |
| int i, k, Entry, iMono, iConst; |
| // collect triples |
| Vec_Int_t * vPairs = Vec_IntAlloc( 100 ); |
| Vec_IntForEachEntry( p->vCoefs, iConst, iMono ) |
| { |
| if ( iConst == 0 ) |
| continue; |
| vArray = Hsh_VecReadEntry( p->pHashC, iConst ); |
| Vec_IntPush( vPairs, Vec_IntEntry(vArray, 0) ); |
| vArray = Hsh_VecReadEntry( p->pHashM, iMono ); |
| Vec_IntPush( vPairs, Vec_IntSize(vArray) ? Vec_IntEntry(vArray, 0) : 0 ); |
| Vec_IntPushTwo( vPairs, iConst, iMono ); |
| } |
| // sort triples |
| qsort( Vec_IntArray(vPairs), Vec_IntSize(vPairs)/4, 16, (int (*)(const void *, const void *))Pln_ManCompare3 ); |
| // print |
| if ( fVerbose ) |
| Vec_IntForEachEntryDouble( vPairs, iConst, iMono, i ) |
| { |
| if ( i % 4 == 0 ) |
| continue; |
| printf( "%-6d : ", i/4 ); |
| vArray = Hsh_VecReadEntry( p->pHashC, iConst ); |
| Vec_IntForEachEntry( vArray, Entry, k ) |
| printf( "%s%d", Entry < 0 ? "-" : "+", (1 << (Abc_AbsInt(Entry)-1)) ); |
| vArray = Hsh_VecReadEntry( p->pHashM, iMono ); |
| Vec_IntForEachEntry( vArray, Entry, k ) |
| printf( " * %d", Entry ); |
| printf( "\n" ); |
| } |
| printf( "HashC = %d. HashM = %d. Total = %d. Used = %d. ", Hsh_VecSize(p->pHashC), Hsh_VecSize(p->pHashM), p->nBuilds, Vec_IntSize(vPairs)/4 ); |
| Vec_IntFree( vPairs ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| static inline void Vec_IntAppendMinus2x( Vec_Int_t * vVec1, Vec_Int_t * vVec2 ) |
| { |
| int Entry, i; |
| Vec_IntClear( vVec1 ); |
| Vec_IntForEachEntry( vVec2, Entry, i ) |
| Vec_IntPush( vVec1, Entry > 0 ? -Entry-1 : -Entry+1 ); |
| } |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| 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 * vConst, Pln_Man_t * p, int iConstAdd ) |
| { |
| int i, New; |
| Vec_Int_t * vConstAdd = Hsh_VecReadEntry( p->pHashC, iConstAdd ); |
| Vec_IntForEachEntry( vConstAdd, New, i ) |
| { |
| Gia_PolynMergeConstOne( vConst, New ); |
| vConstAdd = Hsh_VecReadEntry( p->pHashC, iConstAdd ); |
| } |
| } |
| static inline void Gia_PolynBuildAdd( Pln_Man_t * p, Vec_Int_t * vTempC, Vec_Int_t * vTempM ) |
| { |
| int iConst, iConstNew, iMono = vTempM ? Hsh_VecManAdd(p->pHashM, vTempM) : 0; |
| p->nBuilds++; |
| if ( iMono == Vec_IntSize(p->vCoefs) ) // new monomial |
| { |
| iConst = Hsh_VecManAdd( p->pHashC, vTempC ); |
| Vec_IntPush( p->vCoefs, iConst ); |
| // Vec_FltPush( p->vCounts, Vec_IntEntryLast(vTempM) ); |
| Vec_FltPush( p->vCounts, (float)Vec_IntEntry(p->vOrder, Vec_IntEntryLast(vTempM)) ); |
| Vec_QuePush( p->vQue, iMono ); |
| // Vec_QueUpdate( p->vQue, iMono ); |
| if ( iConst ) |
| p->nUsed++; |
| return; |
| } |
| // this monomial exists |
| iConst = Vec_IntEntry( p->vCoefs, iMono ); |
| if ( iConst ) |
| Gia_PolynMergeConst( vTempC, p, iConst ); |
| iConstNew = Hsh_VecManAdd( p->pHashC, vTempC ); |
| Vec_IntWriteEntry( p->vCoefs, iMono, iConstNew ); |
| if ( iConst && !iConstNew ) |
| p->nUsed--; |
| else if ( !iConst && iConstNew ) |
| p->nUsed++; |
| //assert( p->nUsed == Vec_IntSize(p->vCoefs) - Vec_IntCountZero(p->vCoefs) ); |
| } |
| void Gia_PolynBuildOne( Pln_Man_t * p, int iMono ) |
| { |
| Gia_Obj_t * pObj; |
| Vec_Int_t * vArray, * vConst; |
| int iFan0, iFan1; |
| int k, iConst, iDriver; |
| |
| assert( Vec_IntSize(p->vCoefs) == Hsh_VecSize(p->pHashM) ); |
| vArray = Hsh_VecReadEntry( p->pHashM, iMono ); |
| iDriver = Vec_IntEntryLast( vArray ); |
| pObj = Gia_ManObj( p->pGia, iDriver ); |
| if ( !Gia_ObjIsAnd(pObj) ) |
| return; |
| assert( !Gia_ObjIsMux(p->pGia, pObj) ); |
| |
| iConst = Vec_IntEntry( p->vCoefs, iMono ); |
| if ( iConst == 0 ) |
| return; |
| Vec_IntWriteEntry( p->vCoefs, iMono, 0 ); |
| p->nUsed--; |
| |
| iFan0 = Gia_ObjFaninId0p(p->pGia, pObj); |
| iFan1 = Gia_ObjFaninId1p(p->pGia, pObj); |
| for ( k = 0; k < 4; k++ ) |
| { |
| Vec_IntClear( p->vTempM[k] ); |
| Vec_IntAppend( p->vTempM[k], vArray ); |
| Vec_IntPop( p->vTempM[k] ); |
| if ( k == 1 || k == 3 ) |
| Vec_IntPushUniqueOrderCost( p->vTempM[k], iFan0, p->vOrder ); // x |
| // Vec_IntPushUniqueOrder( p->vTempM[k], iFan0 ); // x |
| if ( k == 2 || k == 3 ) |
| Vec_IntPushUniqueOrderCost( p->vTempM[k], iFan1, p->vOrder ); // y |
| // Vec_IntPushUniqueOrder( p->vTempM[k], iFan1 ); // y |
| } |
| |
| vConst = Hsh_VecReadEntry( p->pHashC, iConst ); |
| |
| if ( !Gia_ObjIsXor(pObj) ) |
| for ( k = 0; k < 2; k++ ) |
| Vec_IntAppendMinus( p->vTempC[k], vConst, k ); |
| |
| if ( Gia_ObjIsXor(pObj) ) |
| { |
| vConst = Hsh_VecReadEntry( p->pHashC, iConst ); |
| Vec_IntAppendMinus( p->vTempC[0], vConst, 0 ); |
| Gia_PolynBuildAdd( p, p->vTempC[0], p->vTempM[1] ); // C * x |
| |
| vConst = Hsh_VecReadEntry( p->pHashC, iConst ); |
| Vec_IntAppendMinus( p->vTempC[0], vConst, 0 ); |
| Gia_PolynBuildAdd( p, p->vTempC[0], p->vTempM[2] ); // C * y |
| |
| //if ( !p->pGia->vXors || Vec_IntFind(p->pGia->vXors, iDriver) == -1 || Vec_IntFind(p->pGia->vXors, iDriver) == 5 ) |
| { |
| vConst = Hsh_VecReadEntry( p->pHashC, iConst ); |
| Vec_IntAppendMinus2x( p->vTempC[0], vConst ); |
| Gia_PolynBuildAdd( p, p->vTempC[0], p->vTempM[3] ); // -C * x * y |
| } |
| } |
| else if ( Gia_ObjFaninC0(pObj) && Gia_ObjFaninC1(pObj) ) // C * (1 - x) * (1 - y) |
| { |
| Gia_PolynBuildAdd( p, p->vTempC[0], p->vTempM[0] ); // C * 1 |
| Gia_PolynBuildAdd( p, p->vTempC[1], p->vTempM[1] ); // -C * x |
| vConst = Hsh_VecReadEntry( p->pHashC, iConst ); |
| for ( k = 0; k < 2; k++ ) |
| Vec_IntAppendMinus( p->vTempC[k], vConst, k ); |
| Gia_PolynBuildAdd( p, p->vTempC[1], p->vTempM[2] ); // -C * y |
| Gia_PolynBuildAdd( p, p->vTempC[0], p->vTempM[3] ); // C * x * y |
| } |
| else if ( Gia_ObjFaninC0(pObj) && !Gia_ObjFaninC1(pObj) ) // C * (1 - x) * y |
| { |
| Gia_PolynBuildAdd( p, p->vTempC[0], p->vTempM[2] ); // C * y |
| Gia_PolynBuildAdd( p, p->vTempC[1], p->vTempM[3] ); // -C * x * y |
| } |
| else if ( !Gia_ObjFaninC0(pObj) && Gia_ObjFaninC1(pObj) ) // C * x * (1 - y) |
| { |
| Gia_PolynBuildAdd( p, p->vTempC[0], p->vTempM[1] ); // C * x |
| Gia_PolynBuildAdd( p, p->vTempC[1], p->vTempM[3] ); // -C * x * y |
| } |
| else |
| Gia_PolynBuildAdd( p, p->vTempC[0], p->vTempM[3] ); // C * x * y |
| } |
| void Gia_PolynBuild( Gia_Man_t * pGia, Vec_Int_t * vOrder, int fSigned, int fVerbose, int fVeryVerbose ) |
| { |
| abctime clk = Abc_Clock();//, clk2 = 0; |
| Gia_Obj_t * pObj; |
| Vec_Bit_t * vPres = Vec_BitStart( Gia_ManObjNum(pGia) ); |
| int i, iMono, iDriver, LevPrev, LevCur, Iter, Line = 0; |
| Pln_Man_t * p = Pln_ManAlloc( pGia, vOrder ); |
| Gia_ManForEachCoReverse( pGia, pObj, i ) |
| { |
| Vec_IntFill( p->vTempC[0], 1, i+1 ); // 2^i |
| Vec_IntFill( p->vTempC[1], 1, -i-1 ); // -2^i |
| |
| iDriver = Gia_ObjFaninId0p( pGia, pObj ); |
| Vec_IntFill( p->vTempM[0], 1, iDriver ); // Driver |
| |
| if ( fSigned && i == Gia_ManCoNum(pGia)-1 ) |
| { |
| if ( Gia_ObjFaninC0(pObj) ) |
| { |
| Gia_PolynBuildAdd( p, p->vTempC[1], NULL ); // -C |
| Gia_PolynBuildAdd( p, p->vTempC[0], p->vTempM[0] ); // C * Driver |
| } |
| else |
| Gia_PolynBuildAdd( p, p->vTempC[1], p->vTempM[0] ); // -C * Driver |
| } |
| else |
| { |
| if ( Gia_ObjFaninC0(pObj) ) |
| { |
| Gia_PolynBuildAdd( p, p->vTempC[0], NULL ); // C |
| Gia_PolynBuildAdd( p, p->vTempC[1], p->vTempM[0] ); // -C * Driver |
| } |
| else |
| Gia_PolynBuildAdd( p, p->vTempC[0], p->vTempM[0] ); // C * Driver |
| } |
| } |
| LevPrev = -1; |
| for ( Iter = 0; ; Iter++ ) |
| { |
| Vec_Int_t * vTempM; |
| //abctime temp = Abc_Clock(); |
| if ( Vec_QueSize(p->vQue) == 0 ) |
| break; |
| iMono = Vec_QuePop(p->vQue); |
| |
| // report |
| vTempM = Hsh_VecReadEntry( p->pHashM, iMono ); |
| //printf( "Removing var %d\n", Vec_IntEntryLast(vTempM) ); |
| LevCur = Vec_IntEntryLast(vTempM); |
| if ( !Gia_ObjIsAnd(Gia_ManObj(pGia, LevCur)) ) |
| continue; |
| |
| if ( LevPrev != LevCur ) |
| { |
| if ( Vec_BitEntry( vPres, LevCur ) && fVerbose ) |
| printf( "Repeating entry %d\n", LevCur ); |
| else |
| Vec_BitSetEntry( vPres, LevCur, 1 ); |
| |
| if ( fVeryVerbose ) |
| printf( "Line%5d Iter%10d : Obj =%6d. Order =%6d. HashC =%6d. HashM =%10d. Total =%10d. Used =%10d.\n", |
| Line++, Iter, LevCur, Vec_IntEntry(p->vOrder, LevCur), Hsh_VecSize(p->pHashC), Hsh_VecSize(p->pHashM), p->nBuilds, p->nUsed ); |
| } |
| LevPrev = LevCur; |
| |
| Gia_PolynBuildOne( p, iMono ); |
| //clk2 += Abc_Clock() - temp; |
| } |
| //Abc_PrintTime( 1, "Time2", clk2 ); |
| Pln_ManPrintFinal( p, fVerbose, fVeryVerbose ); |
| Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); |
| Pln_ManStop( p ); |
| Vec_BitFree( vPres ); |
| } |
| |
| |
| |
| /**Function************************************************************* |
| |
| Synopsis [] |
| |
| Description [] |
| |
| SideEffects [] |
| |
| SeeAlso [] |
| |
| ***********************************************************************/ |
| void Gia_PolynBuild2( Gia_Man_t * pGia, int fSigned, int fVerbose, int fVeryVerbose ) |
| { |
| Hsh_VecMan_t * pHashC = Hsh_VecManStart( 1000 ); // hash table for constants |
| Hsh_VecMan_t * pHashM = Hsh_VecManStart( 1000 ); // hash table for monomials |
| //Vec_Wec_t * vLit2Mono = Vec_WecStart( Gia_ManObjNum(pGia) * 2 ); |
| |
| Hsh_VecManStop( pHashC ); |
| Hsh_VecManStop( pHashM ); |
| } |
| |
| |
| //////////////////////////////////////////////////////////////////////// |
| /// END OF FILE /// |
| //////////////////////////////////////////////////////////////////////// |
| |
| |
| ABC_NAMESPACE_IMPL_END |
| |
