summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--abclib.dsp12
-rw-r--r--src/base/abci/abc.c53
-rw-r--r--src/base/exor/exor.c2
-rw-r--r--src/proof/acec/acecCo.c317
-rw-r--r--src/proof/acec/acecPo.c563
-rw-r--r--src/proof/acec/acecRe.c436
-rw-r--r--src/proof/acec/module.make3
7 files changed, 1386 insertions, 0 deletions
diff --git a/abclib.dsp b/abclib.dsp
index 7d1c1551..8f51bf81 100644
--- a/abclib.dsp
+++ b/abclib.dsp
@@ -5351,6 +5351,10 @@ SOURCE=.\src\proof\acec\acec.h
# End Source File
# Begin Source File
+SOURCE=.\src\proof\acec\acecCo.c
+# End Source File
+# Begin Source File
+
SOURCE=.\src\proof\acec\acecCore.c
# End Source File
# Begin Source File
@@ -5371,10 +5375,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/base/abci/abc.c b/src/base/abci/abc.c
index 97d6b157..8322f27c 100644
--- a/src/base/abci/abc.c
+++ b/src/base/abci/abc.c
@@ -476,6 +476,7 @@ static int Abc_CommandAbc9PoXsim ( Abc_Frame_t * pAbc, int argc, cha
static int Abc_CommandAbc9Demiter ( Abc_Frame_t * pAbc, int argc, char ** argv );
static int Abc_CommandAbc9Fadds ( Abc_Frame_t * pAbc, int argc, char ** argv );
static int Abc_CommandAbc9Polyn ( Abc_Frame_t * pAbc, int argc, char ** argv );
+static int Abc_CommandAbc9ATree ( Abc_Frame_t * pAbc, int argc, char ** argv );
static int Abc_CommandAbc9Acec ( Abc_Frame_t * pAbc, int argc, char ** argv );
static int Abc_CommandAbc9Esop ( Abc_Frame_t * pAbc, int argc, char ** argv );
static int Abc_CommandAbc9Exorcism ( Abc_Frame_t * pAbc, int argc, char ** argv );
@@ -1116,6 +1117,7 @@ void Abc_Init( Abc_Frame_t * pAbc )
Cmd_CommandAdd( pAbc, "ABC9", "&demiter", Abc_CommandAbc9Demiter, 0 );
Cmd_CommandAdd( pAbc, "ABC9", "&fadds", Abc_CommandAbc9Fadds, 0 );
Cmd_CommandAdd( pAbc, "ABC9", "&polyn", Abc_CommandAbc9Polyn, 0 );
+ Cmd_CommandAdd( pAbc, "ABC9", "&atree", Abc_CommandAbc9ATree, 0 );
Cmd_CommandAdd( pAbc, "ABC9", "&acec", Abc_CommandAbc9Acec, 0 );
Cmd_CommandAdd( pAbc, "ABC9", "&esop", Abc_CommandAbc9Esop, 0 );
Cmd_CommandAdd( pAbc, "ABC9", "&exorcism", Abc_CommandAbc9Exorcism, 0 );
@@ -40236,6 +40238,57 @@ usage:
SeeAlso []
***********************************************************************/
+int Abc_CommandAbc9ATree( Abc_Frame_t * pAbc, int argc, char ** argv )
+{
+ extern Gia_Man_t * Gia_PolynCoreDetectTest( Gia_Man_t * pGia );
+ Gia_Man_t * pTemp = NULL;
+ int c, fVerbose = 0, fVeryVerbose = 0;
+ Extra_UtilGetoptReset();
+ while ( ( c = Extra_UtilGetopt( argc, argv, "vwh" ) ) != EOF )
+ {
+ switch ( c )
+ {
+ case 'v':
+ fVerbose ^= 1;
+ break;
+ case 'w':
+ fVeryVerbose ^= 1;
+ break;
+ case 'h':
+ goto usage;
+ default:
+ goto usage;
+ }
+ }
+ if ( pAbc->pGia == NULL )
+ {
+ Abc_Print( -1, "Abc_CommandAbc9Esop(): There is no AIG.\n" );
+ return 0;
+ }
+ pTemp = Gia_PolynCoreDetectTest( pAbc->pGia );
+ Abc_FrameUpdateGia( pAbc, pTemp );
+ return 0;
+
+usage:
+ Abc_Print( -2, "usage: &atree [-vwh]\n" );
+ Abc_Print( -2, "\t extracts adder tree rooting in primary outputs\n" );
+ Abc_Print( -2, "\t-v : toggles printing verbose information [default = %s]\n", fVerbose? "yes": "no" );
+ Abc_Print( -2, "\t-w : toggles printing very verbose information [default = %s]\n", fVeryVerbose? "yes": "no" );
+ Abc_Print( -2, "\t-h : print the command usage\n");
+ return 1;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
int Abc_CommandAbc9Acec( Abc_Frame_t * pAbc, int argc, char ** argv )
{
FILE * pFile;
diff --git a/src/base/exor/exor.c b/src/base/exor/exor.c
index 052362e5..2310de5f 100644
--- a/src/base/exor/exor.c
+++ b/src/base/exor/exor.c
@@ -78,6 +78,7 @@ extern int s_fDecreaseLiterals;
SeeAlso []
***********************************************************************/
+/*
static int QCost[16][16] =
{
{ 1}, // 0
@@ -90,6 +91,7 @@ static int QCost[16][16] =
{ 56, 56, 56, 56, 58, 60, 62, 64}, // 7
{ 0 }
};
+*/
int GetQCost( int nVars, int nNegs )
{
int Extra;
diff --git a/src/proof/acec/acecCo.c b/src/proof/acec/acecCo.c
new file mode 100644
index 00000000..14eecc9c
--- /dev/null
+++ b/src/proof/acec/acecCo.c
@@ -0,0 +1,317 @@
+/**CFile****************************************************************
+
+ FileName [acecCo.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: acecCo.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "acecInt.h"
+#include "misc/vec/vecWec.h"
+
+ABC_NAMESPACE_IMPL_START
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Collect non-XOR inputs.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Gia_PolynCoreNonXors_rec( Gia_Man_t * pGia, Gia_Obj_t * pObj, Vec_Int_t * vXorPairs )
+{
+ Gia_Obj_t * pFan0, * pFan1;
+ if ( !Gia_ObjRecognizeExor(pObj, &pFan0, &pFan1) )
+ return;
+ Gia_PolynCoreNonXors_rec( pGia, Gia_Regular(pFan0), vXorPairs );
+ Gia_PolynCoreNonXors_rec( pGia, Gia_Regular(pFan1), vXorPairs );
+ Vec_IntPushTwo( vXorPairs, Gia_ObjId(pGia, Gia_Regular(pFan0)), Gia_ObjId(pGia, Gia_Regular(pFan1)) );
+}
+Vec_Int_t * Gia_PolynAddHaRoots( Gia_Man_t * pGia )
+{
+ int i, iFan0, iFan1;
+ Vec_Int_t * vNewOuts = Vec_IntAlloc( 100 );
+ Vec_Int_t * vXorPairs = Vec_IntAlloc( 100 );
+ Gia_Obj_t * pObj = Gia_ManCo( pGia, Gia_ManCoNum(pGia)-1 );
+ Gia_PolynCoreNonXors_rec( pGia, Gia_ObjFanin0(pObj), vXorPairs );
+ // add new outputs
+ Gia_ManSetPhase( pGia );
+ Vec_IntForEachEntryDouble( vXorPairs, iFan0, iFan1, i )
+ {
+ Gia_Obj_t * pFan0 = Gia_ManObj( pGia, iFan0 );
+ Gia_Obj_t * pFan1 = Gia_ManObj( pGia, iFan1 );
+ int iLit0 = Abc_Var2Lit( iFan0, pFan0->fPhase );
+ int iLit1 = Abc_Var2Lit( iFan1, pFan1->fPhase );
+ int iRoot = Gia_ManAppendAnd( pGia, iLit0, iLit1 );
+ Vec_IntPush( vNewOuts, Abc_Lit2Var(iRoot) );
+ }
+ Vec_IntFree( vXorPairs );
+ printf( "On top of %d COs, created %d new adder outputs.\n", Gia_ManCoNum(pGia), Vec_IntSize(vNewOuts) );
+ return vNewOuts;
+}
+
+
+/**Function*************************************************************
+
+ Synopsis [Detects the order of adders.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Vec_Int_t * Gia_PolynCoreOrder( Gia_Man_t * pGia, Vec_Int_t * vAdds, Vec_Int_t * vAddCos, Vec_Int_t ** pvIns, Vec_Int_t ** pvOuts )
+{
+ Vec_Int_t * vOrder = Vec_IntAlloc( 1000 );
+ Vec_Bit_t * vIsRoot = Vec_BitStart( Gia_ManObjNum(pGia) );
+ Vec_Int_t * vRoots = Vec_IntAlloc( 5 * Gia_ManCoNum(pGia) );
+ Vec_Int_t * vLeaves = Vec_IntAlloc( 2 * Gia_ManCiNum(pGia) );
+ Vec_Wec_t * vMap = Vec_WecStart( Gia_ManObjNum(pGia) );
+ int i, k, Index, Driver, Entry1, Entry2 = -1;
+ // nodes driven by adders into adder indexes
+ for ( i = 0; 5*i < Vec_IntSize(vAdds); i++ )
+ {
+ Entry1 = Vec_IntEntry( vAdds, 5*i + 3 );
+ Entry2 = Vec_IntEntry( vAdds, 5*i + 4 );
+ Vec_WecPush( vMap, Entry1, i );
+ Vec_WecPush( vMap, Entry1, Entry2 );
+ Vec_WecPush( vMap, Entry2, i );
+ Vec_WecPush( vMap, Entry2, Entry1 );
+ }
+ // collect roots
+ Gia_ManForEachCoDriverId( pGia, Driver, i )
+ {
+ Vec_IntPush( vRoots, Driver );
+ Vec_BitWriteEntry( vIsRoot, Driver, 1 );
+ }
+ // collect additional outputs
+ Vec_IntForEachEntry( vAddCos, Driver, i )
+ {
+ Vec_IntPush( vRoots, Driver );
+ Vec_BitWriteEntry( vIsRoot, Driver, 1 );
+ }
+ // detect full adder tree
+ *pvOuts = Vec_IntDup( vRoots );
+ while ( 1 )
+ {
+ // iterate through boxes driving this one
+ Vec_IntForEachEntry( vRoots, Entry1, i )
+ {
+ Vec_Int_t * vLevel = Vec_WecEntry( vMap, Entry1 );
+ Vec_IntForEachEntryDouble( vLevel, Index, Entry2, k )
+ if ( Vec_BitEntry(vIsRoot, Entry2) )
+ break;
+ if ( k == Vec_IntSize(vLevel) )
+ continue;
+ assert( Vec_BitEntry(vIsRoot, Entry1) );
+ assert( Vec_BitEntry(vIsRoot, Entry2) );
+ // collect adder
+ Vec_IntPush( vOrder, Index );
+ // clean marks
+ Vec_BitWriteEntry( vIsRoot, Entry1, 0 );
+ Vec_BitWriteEntry( vIsRoot, Entry2, 0 );
+ Vec_IntRemove( vRoots, Entry1 );
+ Vec_IntRemove( vRoots, Entry2 );
+ // set new marks
+ Entry1 = Vec_IntEntry( vAdds, 5*Index + 0 );
+ Entry2 = Vec_IntEntry( vAdds, 5*Index + 1 );
+ Driver = Vec_IntEntry( vAdds, 5*Index + 2 );
+ Vec_BitWriteEntry( vIsRoot, Entry1, 1 );
+ Vec_BitWriteEntry( vIsRoot, Entry2, 1 );
+ Vec_BitWriteEntry( vIsRoot, Driver, 1 );
+ Vec_IntPushUnique( vRoots, Entry1 );
+ Vec_IntPushUnique( vRoots, Entry2 );
+ Vec_IntPushUnique( vRoots, Driver );
+ break;
+ }
+ if ( i == Vec_IntSize(vRoots) )
+ break;
+ }
+ // collect remaining leaves
+ Vec_BitForEachEntryStart( vIsRoot, Driver, i, 1 )
+ if ( Driver )
+ Vec_IntPush( vLeaves, i );
+ *pvIns = vLeaves;
+ // cleanup
+ Vec_BitFree( vIsRoot );
+ Vec_IntFree( vRoots );
+ Vec_WecFree( vMap );
+ return vOrder;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Collect internal node order.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Gia_PolynCoreCollect_rec( Gia_Man_t * pGia, int iObj, Vec_Int_t * vNodes, Vec_Bit_t * vVisited )
+{
+ if ( Vec_BitEntry(vVisited, iObj) )
+ return;
+ Vec_BitSetEntry( vVisited, iObj, 1 );
+ Gia_PolynCoreCollect_rec( pGia, Gia_ObjFaninId0p(pGia, Gia_ManObj(pGia, iObj)), vNodes, vVisited );
+ Gia_PolynCoreCollect_rec( pGia, Gia_ObjFaninId1p(pGia, Gia_ManObj(pGia, iObj)), vNodes, vVisited );
+ Vec_IntPush( vNodes, iObj );
+}
+Vec_Int_t * Gia_PolynCoreCollect( Gia_Man_t * pGia, Vec_Int_t * vAdds, Vec_Int_t * vOrder )
+{
+ Vec_Int_t * vNodes = Vec_IntAlloc( 1000 );
+ Vec_Bit_t * vVisited = Vec_BitStart( Gia_ManObjNum(pGia) );
+ int i, Index, Entry1, Entry2, Entry3;
+ Vec_IntForEachEntryReverse( vOrder, Index, i )
+ {
+ // mark inputs
+ Entry1 = Vec_IntEntry( vAdds, 5*Index + 0 );
+ Entry2 = Vec_IntEntry( vAdds, 5*Index + 1 );
+ Entry3 = Vec_IntEntry( vAdds, 5*Index + 2 );
+ Vec_BitWriteEntry( vVisited, Entry1, 1 );
+ Vec_BitWriteEntry( vVisited, Entry2, 1 );
+ Vec_BitWriteEntry( vVisited, Entry3, 1 );
+ // traverse from outputs
+ Entry1 = Vec_IntEntry( vAdds, 5*Index + 3 );
+ Entry2 = Vec_IntEntry( vAdds, 5*Index + 4 );
+ Gia_PolynCoreCollect_rec( pGia, Entry1, vNodes, vVisited );
+ Gia_PolynCoreCollect_rec( pGia, Entry2, vNodes, vVisited );
+ }
+ Vec_BitFree( vVisited );
+ return vNodes;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Gia_PolynCorePrintCones( Gia_Man_t * pGia, Vec_Int_t * vLeaves )
+{
+ int i, iObj;
+ Vec_IntForEachEntry( vLeaves, iObj, i )
+ {
+ printf( "%4d : ", i );
+ printf( "Supp = %3d ", Gia_ManSuppSize(pGia, &iObj, 1) );
+ printf( "Cone = %3d ", Gia_ManConeSize(pGia, &iObj, 1) );
+ printf( "\n" );
+ }
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Gia_Man_t * Gia_PolynCoreDupTree( Gia_Man_t * p, Vec_Int_t * vAddCos, Vec_Int_t * vLeaves, Vec_Int_t * vNodes )
+{
+ Gia_Man_t * pNew;
+ Gia_Obj_t * pObj;
+ int i;
+ assert( Gia_ManRegNum(p) == 0 );
+ Gia_ManFillValue( p );
+ pNew = Gia_ManStart( Gia_ManObjNum(p) );
+ pNew->pName = Abc_UtilStrsav( p->pName );
+ pNew->pSpec = Abc_UtilStrsav( p->pSpec );
+ Gia_ManConst0(p)->Value = 0;
+ Gia_ManForEachObjVec( vLeaves, p, pObj, i )
+ pObj->Value = Gia_ManAppendCi(pNew);
+ Gia_ManForEachObjVec( vNodes, p, pObj, i )
+ pObj->Value = Gia_ManAppendAnd( pNew, Gia_ObjFanin0Copy(pObj), Gia_ObjFanin1Copy(pObj) );
+ Gia_ManForEachCo( p, pObj, i )
+ Gia_ManAppendCo( pNew, Gia_ObjFanin0Copy(pObj) );
+ Gia_ManForEachObjVec( vAddCos, p, pObj, i )
+ Gia_ManAppendCo( pNew, pObj->Value );
+ return pNew;
+
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+Gia_Man_t * Gia_PolynCoreDetectTest_int( Gia_Man_t * pGia, Vec_Int_t * vAddCos )
+{
+ extern Vec_Int_t * Ree_ManComputeCuts( Gia_Man_t * p, int fVerbose );
+ abctime clk = Abc_Clock();
+ Gia_Man_t * pNew;
+ Vec_Int_t * vAdds = Ree_ManComputeCuts( pGia, 1 );
+ Vec_Int_t * vLeaves, * vRoots, * vOrder = Gia_PolynCoreOrder( pGia, vAdds, vAddCos, &vLeaves, &vRoots );
+ Vec_Int_t * vNodes = Gia_PolynCoreCollect( pGia, vAdds, vOrder );
+ printf( "Detected %d FAs/HAs. Roots = %d. Leaves = %d. Nodes = %d. Adds = %d. ",
+ Vec_IntSize(vAdds), Vec_IntSize(vLeaves), Vec_IntSize(vRoots), Vec_IntSize(vNodes), Vec_IntSize(vOrder) );
+ Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
+
+ Gia_PolynCorePrintCones( pGia, vLeaves );
+
+ pNew = Gia_PolynCoreDupTree( pGia, vAddCos, vLeaves, vNodes );
+
+ Vec_IntFree( vAdds );
+ Vec_IntFree( vLeaves );
+ Vec_IntFree( vRoots );
+ Vec_IntFree( vOrder );
+ Vec_IntFree( vNodes );
+ return pNew;
+}
+Gia_Man_t * Gia_PolynCoreDetectTest( Gia_Man_t * pGia )
+{
+ Vec_Int_t * vAddCos = Gia_PolynAddHaRoots( pGia );
+ Gia_Man_t * pNew = Gia_PolynCoreDetectTest_int( pGia, vAddCos );
+ Vec_IntFree( vAddCos );
+ return pNew;
+}
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
diff --git a/src/proof/acec/acecPo.c b/src/proof/acec/acecPo.c
new file mode 100644
index 00000000..1e77ab20
--- /dev/null
+++ b/src/proof/acec/acecPo.c
@@ -0,0 +1,563 @@
+/**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 )
+ {
+ 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
+
diff --git a/src/proof/acec/module.make b/src/proof/acec/module.make
index 900d3f5f..36137676 100644
--- a/src/proof/acec/module.make
+++ b/src/proof/acec/module.make
@@ -1,4 +1,7 @@
SRC += src/proof/acec/acecCore.c \
+ src/proof/acec/acecCo.c \
+ src/proof/acec/acecRe.c \
+ src/proof/acec/acecPo.c \
src/proof/acec/acecCover.c \
src/proof/acec/acecFadds.c \
src/proof/acec/acecOrder.c \