Version abc80919

7 files changed, 178 insertions, 16 deletions

diff --git a/src/aig/int/int.h b/src/aig/int/int.h
index bc9c1237..e0c4e960 100644
--- a/src/aig/int/int.h
+++ b/src/aig/int/int.h
@@ -70,7 +70,7 @@ struct Inter_ManParams_t_
 
 /*=== intCore.c ==========================================================*/
 extern void       Inter_ManSetDefaultParams( Inter_ManParams_t * p );
-extern int        Inter_ManPerformInterpolation( Aig_Man_t * pAig, Inter_ManParams_t * pPars, int * pDepth );
+extern int        Inter_ManPerformInterpolation( Aig_Man_t * pAig, Inter_ManParams_t * pPars, int * piFrame );
 
 
 #ifdef __cplusplus
diff --git a/src/aig/int/intContain.c b/src/aig/int/intContain.c
index fa52e2b6..dcc80b29 100644
--- a/src/aig/int/intContain.c
+++ b/src/aig/int/intContain.c
@@ -200,19 +200,19 @@ int Inter_ManCheckInductiveContainment( Aig_Man_t * pTrans, Aig_Man_t * pInter,
     assert( Vec_PtrSize(vMapRegs) == (nSteps + 1) * nRegs );
     // add main constraints to the timeframes
     ppNodes = (Aig_Obj_t **)Vec_PtrArray(vMapRegs);
-    if ( fBackward )
-    {
-        // p -> !p -> ... -> !p
-        Inter_ManAppendCone( pInter, pFrames, ppNodes + 0 * nRegs, 1 );
-        for ( f = 1; f <= nSteps; f++ )
+    if ( !fBackward )
+    { 
+        // forward inductive check: p -> p -> ... -> !p
+        for ( f = 0; f < nSteps; f++ )
             Inter_ManAppendCone( pInter, pFrames, ppNodes + f * nRegs, 0 );
+        Inter_ManAppendCone( pInter, pFrames, ppNodes + f * nRegs, 1 );
     }
     else
     {
-        // !p -> p -> ... -> p
-        for ( f = 0; f < nSteps; f++ )
+        // backward inductive check: p -> !p -> ... -> !p
+        Inter_ManAppendCone( pInter, pFrames, ppNodes + 0 * nRegs, 1 );
+        for ( f = 1; f <= nSteps; f++ )
             Inter_ManAppendCone( pInter, pFrames, ppNodes + f * nRegs, 0 );
-        Inter_ManAppendCone( pInter, pFrames, ppNodes + f * nRegs, 1 );
     }
     Vec_PtrFree( vMapRegs );
     Aig_ManCleanup( pFrames );
diff --git a/src/aig/int/intCore.c b/src/aig/int/intCore.c
index d959ff07..cc6c5f5b 100644
--- a/src/aig/int/intCore.c
+++ b/src/aig/int/intCore.c
@@ -40,13 +40,13 @@
 
 ***********************************************************************/
 void Inter_ManSetDefaultParams( Inter_ManParams_t * p )
-{
+{ 
     memset( p, 0, sizeof(Inter_ManParams_t) );
     p->nBTLimit     = 10000; // limit on the number of conflicts
     p->nFramesMax   = 40;    // the max number timeframes to unroll
     p->nFramesK     = 1;     // the number of timeframes to use in induction
     p->fRewrite     = 0;     // use additional rewriting to simplify timeframes
-    p->fTransLoop   = 1;     // add transition into the init state under new PI var
+    p->fTransLoop   = 0;     // add transition into the init state under new PI var
     p->fUsePudlak   = 0;     // use Pudluk interpolation procedure
     p->fUseOther    = 0;     // use other undisclosed option
     p->fUseMiniSat  = 0;     // use MiniSat-1.14p instead of internal proof engine
@@ -67,7 +67,7 @@ void Inter_ManSetDefaultParams( Inter_ManParams_t * p )
   SeeAlso     []
 
 ***********************************************************************/
-int Inter_ManPerformInterpolation( Aig_Man_t * pAig, Inter_ManParams_t * pPars, int * pDepth )
+int Inter_ManPerformInterpolation( Aig_Man_t * pAig, Inter_ManParams_t * pPars, int * piFrame )
 {
     extern int Inter_ManCheckInductiveContainment( Aig_Man_t * pTrans, Aig_Man_t * pInter, int nSteps, int fBackward );
     Inter_Man_t * p;
@@ -109,7 +109,7 @@ p->timeCnf += clock() - clk;
     }
 
     // derive interpolant
-    *pDepth = -1;
+    *piFrame = -1;
     p->nFrames = 1;
     for ( s = 0; ; s++ )
     {
@@ -183,9 +183,10 @@ p->timeCnf += clock() - clk;
                 if ( i == 0 ) // real counterexample
                 {
                     if ( pPars->fVerbose )
-                        printf( "Found a real counterexample in the first frame.\n" );
+                        printf( "Found a real counterexample in frame %d.\n", p->nFrames );
                     p->timeTotal = clock() - clkTotal;
-                    *pDepth = p->nFrames + 1;
+                    *piFrame = p->nFrames;
+                    pAig->pSeqModel = Inter_ManGetCounterExample( pAig, p->nFrames+1, pPars->fVerbose );
                     Inter_ManStop( p );
                     return 0;
                 }
diff --git a/src/aig/int/intCtrex.c b/src/aig/int/intCtrex.c
new file mode 100644
index 00000000..5e417ce0
--- /dev/null
+++ b/src/aig/int/intCtrex.c
@@ -0,0 +1,157 @@
+/**CFile****************************************************************
+
+  FileName    [intCtrex.c]
+
+  SystemName  [ABC: Logic synthesis and verification system.]
+
+  PackageName [Interpolation engine.]
+
+  Synopsis    [Counter-example generation after disproving the property.]
+
+  Author      [Alan Mishchenko]
+  
+  Affiliation [UC Berkeley]
+
+  Date        [Ver. 1.0. Started - June 24, 2008.]
+
+  Revision    [$Id: intCtrex.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "intInt.h"
+#include "ssw.h"
+
+////////////////////////////////////////////////////////////////////////
+///                        DECLARATIONS                              ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+///                     FUNCTION DEFINITIONS                         ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+  Synopsis    [Unroll the circuit the given number of timeframes.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+Aig_Man_t * Inter_ManFramesBmc( Aig_Man_t * pAig, int nFrames )
+{
+    Aig_Man_t * pFrames;
+    Aig_Obj_t * pObj, * pObjLi, * pObjLo;
+    int i, f;
+    assert( Saig_ManRegNum(pAig) > 0 );
+    assert( Saig_ManPoNum(pAig) == 1 );
+    pFrames = Aig_ManStart( Aig_ManNodeNum(pAig) * nFrames );
+    // map the constant node
+    Aig_ManConst1(pAig)->pData = Aig_ManConst1( pFrames );
+    // create variables for register outputs
+    Saig_ManForEachLo( pAig, pObj, i )
+        pObj->pData = Aig_ManConst0( pFrames );
+    // add timeframes
+    for ( f = 0; f < nFrames; f++ )
+    {
+        // create PI nodes for this frame
+        Saig_ManForEachPi( pAig, pObj, i )
+            pObj->pData = Aig_ObjCreatePi( pFrames );
+        // add internal nodes of this frame
+        Aig_ManForEachNode( pAig, pObj, i )
+            pObj->pData = Aig_And( pFrames, Aig_ObjChild0Copy(pObj), Aig_ObjChild1Copy(pObj) );
+        if ( f == nFrames - 1 )
+            break;
+        // transfer to register outputs
+        Saig_ManForEachLiLo(  pAig, pObjLi, pObjLo, i )
+            pObjLo->pData = pObjLi->pData = Aig_ObjChild0Copy(pObjLi);
+    }
+    // create POs for the output of the last frame
+    pObj = Aig_ManPo( pAig, 0 );
+    Aig_ObjCreatePo( pFrames, Aig_ObjChild0Copy(pObj) );
+    Aig_ManCleanup( pFrames );
+    return pFrames;
+}
+
+/**Function*************************************************************
+
+  Synopsis    [Run the SAT solver on the unrolled instance.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void * Inter_ManGetCounterExample( Aig_Man_t * pAig, int nFrames, int fVerbose )
+{
+    int nConfLimit = 1000000;
+    Ssw_Cex_t * pCtrex = NULL;
+    Aig_Man_t * pFrames;
+    sat_solver * pSat;
+    Cnf_Dat_t * pCnf;
+    int status, clk = clock();
+    Vec_Int_t * vCiIds;
+    // create timeframes
+    assert( Saig_ManPoNum(pAig) == 1 );
+    pFrames = Inter_ManFramesBmc( pAig, nFrames );
+    // derive CNF
+    pCnf = Cnf_Derive( pFrames, 0 );
+    Cnf_DataTranformPolarity( pCnf, 0 );
+    vCiIds = Cnf_DataCollectPiSatNums( pCnf, pFrames );
+    Aig_ManStop( pFrames );
+    // convert into SAT solver
+    pSat = Cnf_DataWriteIntoSolver( pCnf, 1, 0 );
+    Cnf_DataFree( pCnf );
+    if ( pSat == NULL )
+    {
+        Vec_IntFree( vCiIds );
+        return NULL;
+    }
+    // simplify the problem
+    status = sat_solver_simplify(pSat);
+    if ( status == 0 )
+    {
+        Vec_IntFree( vCiIds );
+        sat_solver_delete( pSat );
+        return NULL;
+    }
+    // solve the miter
+    status = sat_solver_solve( pSat, NULL, NULL, (sint64)nConfLimit, (sint64)0, (sint64)0, (sint64)0 );
+    // if the problem is SAT, get the counterexample
+    if ( status == l_True )
+    {
+        int i, * pModel = Sat_SolverGetModel( pSat, vCiIds->pArray, vCiIds->nSize );
+        pCtrex = Ssw_SmlAllocCounterExample( Saig_ManRegNum(pAig), Saig_ManPiNum(pAig), nFrames );
+        pCtrex->iFrame = nFrames - 1;
+        pCtrex->iPo = 0;
+        for ( i = 0; i < Vec_IntSize(vCiIds); i++ )
+            if ( pModel[i] )
+                Aig_InfoSetBit( pCtrex->pData, Saig_ManRegNum(pAig) + i );
+        free( pModel );
+    }
+    // free the sat_solver
+    sat_solver_delete( pSat );
+    Vec_IntFree( vCiIds );
+    // verify counter-example
+    status = Ssw_SmlRunCounterExample( pAig, pCtrex );
+    if ( status == 0 )
+        printf( "Inter_ManGetCounterExample(): Counter-example verification has FAILED.\n" );
+    // report the results
+    if ( fVerbose )
+    {
+        PRT( "Total ctrex generation time", clock() - clk );
+    }
+    return pCtrex;
+
+}
+
+
+////////////////////////////////////////////////////////////////////////
+///                       END OF FILE                                ///
+////////////////////////////////////////////////////////////////////////
+
+
diff --git a/src/aig/int/intInt.h b/src/aig/int/intInt.h
index dbb4301e..c84fef2d 100644
--- a/src/aig/int/intInt.h
+++ b/src/aig/int/intInt.h
@@ -90,6 +90,9 @@ extern int           Inter_ManCheckContainment( Aig_Man_t * pNew, Aig_Man_t * pO
 extern int           Inter_ManCheckEquivalence( Aig_Man_t * pNew, Aig_Man_t * pOld );
 extern int           Inter_ManCheckInductiveContainment( Aig_Man_t * pTrans, Aig_Man_t * pInter, int nSteps, int fBackward );
 
+/*=== intCtrex.c ==========================================================*/
+extern void *        Inter_ManGetCounterExample( Aig_Man_t * pAig, int nFrames, int fVerbose );
+
 /*=== intDup.c ==========================================================*/
 extern Aig_Man_t *   Inter_ManStartInitState( int nRegs );
 extern Aig_Man_t *   Inter_ManStartDuplicated( Aig_Man_t * p );
diff --git a/src/aig/int/intM114p.c b/src/aig/int/intM114p.c
index 77776f7e..6818fdce 100644
--- a/src/aig/int/intM114p.c
+++ b/src/aig/int/intM114p.c
@@ -108,7 +108,7 @@ M114p_Solver_t Inter_ManDeriveSatSolverM114p(
     }
     // connector clauses
     Aig_ManForEachPi( pFrames, pObj, i )
-    {
+    { 
         if ( i == Aig_ManRegNum(pAig) )
             break;
 //        Vec_IntPush( vVarsAB, pCnfFrames->pVarNums[pObj->Id] );
diff --git a/src/aig/int/module.make b/src/aig/int/module.make
index 0652ab39..cf0f827f 100644
--- a/src/aig/int/module.make
+++ b/src/aig/int/module.make
@@ -1,5 +1,6 @@
 SRC +=    src/aig/int/intContain.c \
     src/aig/int/intCore.c \
+    src/aig/int/intCtrex.c \
     src/aig/int/intDup.c \
     src/aig/int/intFrames.c \
     src/aig/int/intInter.c \