summaryrefslogtreecommitdiffstats
path: root/src/proof/acec
diff options
context:
space:
mode:
Diffstat (limited to 'src/proof/acec')
-rw-r--r--src/proof/acec/acecBo.c216
-rw-r--r--src/proof/acec/acecCl.c95
-rw-r--r--src/proof/acec/module.make1
3 files changed, 311 insertions, 1 deletions
diff --git a/src/proof/acec/acecBo.c b/src/proof/acec/acecBo.c
new file mode 100644
index 00000000..9cddcd13
--- /dev/null
+++ b/src/proof/acec/acecBo.c
@@ -0,0 +1,216 @@
+/**CFile****************************************************************
+
+ FileName [acecBo.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: acecBo.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "acecInt.h"
+#include "misc/vec/vecWec.h"
+#include "misc/extra/extra.h"
+
+ABC_NAMESPACE_IMPL_START
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Acec_DetectBoothXorMux( Gia_Man_t * p, Gia_Obj_t * pMux, Gia_Obj_t * pXor, int pIns[3] )
+{
+ Gia_Obj_t * pFan0, * pFan1;
+ Gia_Obj_t * pDat0, * pDat1, * pCtrl;
+ if ( !Gia_ObjIsMuxType(pMux) || !Gia_ObjIsMuxType(pXor) )
+ return 0;
+ if ( !Gia_ObjRecognizeExor( pXor, &pFan0, &pFan1 ) )
+ return 0;
+ pFan0 = Gia_Regular(pFan0);
+ pFan1 = Gia_Regular(pFan1);
+ if ( Gia_ObjId(p, pFan0) > Gia_ObjId(p, pFan1) )
+ ABC_SWAP( Gia_Obj_t *, pFan0, pFan1 );
+ if ( !(pCtrl = Gia_ObjRecognizeMux( pMux, &pDat0, &pDat1 )) )
+ return 0;
+ pDat0 = Gia_Regular(pDat0);
+ pDat1 = Gia_Regular(pDat1);
+ pCtrl = Gia_Regular(pCtrl);
+ if ( !Gia_ObjIsAnd(pDat0) || !Gia_ObjIsAnd(pDat1) )
+ return 0;
+ if ( Gia_ObjFaninId0p(p, pDat0) != Gia_ObjFaninId0p(p, pDat1) ||
+ Gia_ObjFaninId1p(p, pDat0) != Gia_ObjFaninId1p(p, pDat1) )
+ return 0;
+ if ( Gia_ObjFaninId0p(p, pDat0) != Gia_ObjId(p, pFan0) ||
+ Gia_ObjFaninId1p(p, pDat0) != Gia_ObjId(p, pFan1) )
+ return 0;
+ pIns[0] = Gia_ObjId(p, pFan0);
+ pIns[1] = Gia_ObjId(p, pFan1);
+ pIns[2] = Gia_ObjId(p, pCtrl);
+ return 1;
+}
+int Acec_DetectBoothXorFanin( Gia_Man_t * p, Gia_Obj_t * pObj, int pIns[5] )
+{
+ Gia_Obj_t * pFan0, * pFan1;
+ //int Id = Gia_ObjId(p, pObj);
+ if ( !Gia_ObjIsAnd(pObj) )
+ return 0;
+ if ( !Gia_ObjFaninC0(pObj) || !Gia_ObjFaninC1(pObj) )
+ return 0;
+ pFan0 = Gia_ObjFanin0(pObj);
+ pFan1 = Gia_ObjFanin1(pObj);
+ if ( !Gia_ObjIsAnd(pFan0) || !Gia_ObjIsAnd(pFan1) )
+ return 0;
+ if ( Acec_DetectBoothXorMux(p, Gia_ObjFanin0(pFan0), Gia_ObjFanin0(pFan1), pIns) )
+ {
+ pIns[3] = Gia_ObjId(p, Gia_ObjFanin1(pFan0));
+ pIns[4] = Gia_ObjId(p, Gia_ObjFanin1(pFan1));
+ return 1;
+ }
+ if ( Acec_DetectBoothXorMux(p, Gia_ObjFanin0(pFan0), Gia_ObjFanin1(pFan1), pIns) )
+ {
+ pIns[3] = Gia_ObjId(p, Gia_ObjFanin1(pFan0));
+ pIns[4] = Gia_ObjId(p, Gia_ObjFanin0(pFan1));
+ return 1;
+ }
+ if ( Acec_DetectBoothXorMux(p, Gia_ObjFanin1(pFan0), Gia_ObjFanin0(pFan1), pIns) )
+ {
+ pIns[3] = Gia_ObjId(p, Gia_ObjFanin0(pFan0));
+ pIns[4] = Gia_ObjId(p, Gia_ObjFanin1(pFan1));
+ return 1;
+ }
+ if ( Acec_DetectBoothXorMux(p, Gia_ObjFanin1(pFan0), Gia_ObjFanin1(pFan1), pIns) )
+ {
+ pIns[3] = Gia_ObjId(p, Gia_ObjFanin0(pFan0));
+ pIns[4] = Gia_ObjId(p, Gia_ObjFanin0(pFan1));
+ return 1;
+ }
+ return 0;
+}
+int Acec_DetectBoothOne( Gia_Man_t * p, Gia_Obj_t * pObj, int pIns[5] )
+{
+ Gia_Obj_t * pFan0, * pFan1;
+ if ( !Gia_ObjRecognizeExor( pObj, &pFan0, &pFan1 ) )
+ return 0;
+ pFan0 = Gia_Regular(pFan0);
+ pFan1 = Gia_Regular(pFan1);
+ if ( Acec_DetectBoothXorFanin( p, pFan0, pIns ) && pIns[2] == Gia_ObjId(p, pFan1) )
+ return 1;
+ if ( Acec_DetectBoothXorFanin( p, pFan1, pIns ) && pIns[2] == Gia_ObjId(p, pFan0) )
+ return 1;
+ return 0;
+}
+
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Acec_DetectBoothTwoXor( Gia_Man_t * p, Gia_Obj_t * pObj, int pIns[5] )
+{
+ Gia_Obj_t * pFan0, * pFan1;
+ if ( !Gia_ObjIsAnd(pObj) )
+ return 0;
+ if ( Gia_ObjRecognizeExor( Gia_ObjFanin0(pObj), &pFan0, &pFan1 ) )
+ {
+ pIns[0] = Gia_ObjId(p, Gia_Regular(pFan0));
+ pIns[1] = Gia_ObjId(p, Gia_Regular(pFan1));
+ pIns[2] = -1;
+ pIns[3] = 0;
+ pIns[4] = Gia_ObjId(p, Gia_ObjFanin1(pObj));
+ return 1;
+ }
+ if ( Gia_ObjRecognizeExor( Gia_ObjFanin1(pObj), &pFan0, &pFan1 ) )
+ {
+ pIns[0] = Gia_ObjId(p, Gia_Regular(pFan0));
+ pIns[1] = Gia_ObjId(p, Gia_Regular(pFan1));
+ pIns[2] = -1;
+ pIns[3] = 0;
+ pIns[4] = Gia_ObjId(p, Gia_ObjFanin0(pObj));
+ return 1;
+ }
+ return 0;
+}
+int Acec_DetectBoothTwo( Gia_Man_t * p, Gia_Obj_t * pObj, int pIns[5] )
+{
+ Gia_Obj_t * pFan0, * pFan1;
+ if ( !Gia_ObjRecognizeExor( pObj, &pFan0, &pFan1 ) )
+ return 0;
+ pFan0 = Gia_Regular(pFan0);
+ pFan1 = Gia_Regular(pFan1);
+ if ( Acec_DetectBoothTwoXor( p, pFan0, pIns ) )
+ {
+ pIns[2] = Gia_ObjId(p, pFan1);
+ return 1;
+ }
+ if ( Acec_DetectBoothTwoXor( p, pFan1, pIns ) )
+ {
+ pIns[2] = Gia_ObjId(p, pFan0);
+ return 1;
+ }
+ return 0;
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Acec_DetectBoothTest( Gia_Man_t * p )
+{
+ Gia_Obj_t * pObj;
+ int i, pIns[5];
+ Gia_ManForEachAnd( p, pObj, i )
+ {
+ if ( !Acec_DetectBoothOne(p, pObj, pIns) && !Acec_DetectBoothTwo(p, pObj, pIns) )
+ continue;
+ printf( "obj = %4d : b0 = %4d b1 = %4d b2 = %4d a0 = %4d a1 = %4d\n",
+ i, pIns[0], pIns[1], pIns[2], pIns[3], pIns[4] );
+ }
+}
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+
diff --git a/src/proof/acec/acecCl.c b/src/proof/acec/acecCl.c
index b60c2bf9..63483d57 100644
--- a/src/proof/acec/acecCl.c
+++ b/src/proof/acec/acecCl.c
@@ -127,7 +127,7 @@ Vec_Int_t * Acec_CollectXorTops( Gia_Man_t * p )
break;
}
Vec_IntPush( vRootXorSet, Gia_ObjId(p, pObj) );
- Vec_IntPush( vRootXorSet, fXor1 ? Gia_ObjId(p, Gia_Regular(pFan1)) : Gia_ObjId(p, Gia_Regular(pFan0)) );
+ Vec_IntPush( vRootXorSet, fXor1 ? Gia_ObjId(p, Gia_Regular(pFan0)) : Gia_ObjId(p, Gia_Regular(pFan1)) );
Vec_IntPush( vRootXorSet, fXor1 ? Gia_ObjId(p, Gia_Regular(pFan10)) : Gia_ObjId(p, Gia_Regular(pFan00)) );
Vec_IntPush( vRootXorSet, fXor1 ? Gia_ObjId(p, Gia_Regular(pFan11)) : Gia_ObjId(p, Gia_Regular(pFan01)) );
}
@@ -173,10 +173,101 @@ int Acec_DetectLitPolarity( Gia_Man_t * p, int Node, int Leaf )
if ( Lit0 != -1 && Lit1 != -1 )
{
assert( Lit0 == Lit1 );
+ printf( "Problem for leaf %d\n", Leaf );
return Lit0;
}
return Lit0 != -1 ? Lit0 : Lit1;
}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Acec_DetectComputeSuppOne_rec( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Int_t * vSupp, Vec_Int_t * vNods )
+{
+ if ( Gia_ObjIsTravIdCurrent(p, pObj) )
+ return;
+ Gia_ObjSetTravIdCurrent(p, pObj);
+ if ( pObj->fMark0 )
+ {
+ Vec_IntPush( vSupp, Gia_ObjId(p, pObj) );
+ return;
+ }
+ assert( Gia_ObjIsAnd(pObj) );
+ Acec_DetectComputeSuppOne_rec( p, Gia_ObjFanin0(pObj), vSupp, vNods );
+ Acec_DetectComputeSuppOne_rec( p, Gia_ObjFanin1(pObj), vSupp, vNods );
+ Vec_IntPush( vNods, Gia_ObjId(p, pObj) );
+}
+void Acec_DetectComputeSupports( Gia_Man_t * p, Vec_Int_t * vRootXorSet )
+{
+ Vec_Int_t * vNods = Vec_IntAlloc( 100 );
+ Vec_Int_t * vPols = Vec_IntAlloc( 100 );
+ Vec_Int_t * vSupp = Vec_IntAlloc( 100 ); int i, k, Node, Pol;
+ for ( i = 0; 4*i < Vec_IntSize(vRootXorSet); i++ )
+ {
+ Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+1) )->fMark0 = 1;
+ Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+2) )->fMark0 = 1;
+ Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+3) )->fMark0 = 1;
+ }
+ for ( i = 1; 4*i < Vec_IntSize(vRootXorSet); i++ )
+ {
+ Vec_IntClear( vSupp );
+ Gia_ManIncrementTravId( p );
+
+ Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+1) )->fMark0 = 0;
+ Acec_DetectComputeSuppOne_rec( p, Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+1) ), vSupp, vNods );
+ Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+1) )->fMark0 = 1;
+
+ Vec_IntSort( vSupp, 0 );
+
+ printf( "Out %4d : %4d \n", i, Vec_IntEntry(vRootXorSet, 4*i+1) );
+ Vec_IntPrint( vSupp );
+
+ printf( "Cone:\n" );
+ Vec_IntForEachEntry( vNods, Node, k )
+ Gia_ObjPrint( p, Gia_ManObj(p, Node) );
+
+
+ Vec_IntClear( vPols );
+ Vec_IntForEachEntry( vSupp, Node, k )
+ Vec_IntPush( vPols, Acec_DetectLitPolarity(p, Vec_IntEntry(vRootXorSet, 4*i+1), Node) );
+
+ Vec_IntForEachEntryTwo( vSupp, vPols, Node, Pol, k )
+ printf( "%d(%d) ", Node, Abc_LitIsCompl(Pol) );
+
+ printf( "\n" );
+
+ Vec_IntPrint( vSupp );
+ }
+ for ( i = 0; 4*i < Vec_IntSize(vRootXorSet); i++ )
+ {
+ Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+1) )->fMark0 = 0;
+ Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+2) )->fMark0 = 0;
+ Gia_ManObj( p, Vec_IntEntry(vRootXorSet, 4*i+3) )->fMark0 = 0;
+ }
+ Vec_IntFree( vSupp );
+ Vec_IntFree( vPols );
+ Vec_IntFree( vNods );
+}
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
Gia_Man_t * Acec_DetectXorBuildNew( Gia_Man_t * p, Vec_Int_t * vRootXorSet )
{
Gia_Man_t * pNew;
@@ -236,6 +327,8 @@ Gia_Man_t * Acec_DetectAdditional( Gia_Man_t * p, int fVerbose )
vRootXorSet = Acec_CollectXorTops( p );
if ( vRootXorSet )
{
+ Acec_DetectComputeSupports( p, vRootXorSet );
+
pNew = Acec_DetectXorBuildNew( p, vRootXorSet );
Vec_IntFree( vRootXorSet );
}
diff --git a/src/proof/acec/module.make b/src/proof/acec/module.make
index df6db695..4003695e 100644
--- a/src/proof/acec/module.make
+++ b/src/proof/acec/module.make
@@ -1,6 +1,7 @@
SRC += src/proof/acec/acecCl.c \
src/proof/acec/acecCore.c \
src/proof/acec/acecCo.c \
+ src/proof/acec/acecBo.c \
src/proof/acec/acecRe.c \
src/proof/acec/acecPa.c \
src/proof/acec/acecPo.c \
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-07 20:03:42 +0000