satInterB.c File Reference

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "satStore.h"
#include "aig/aig/aig.h"

Go to the source code of this file.

Data Structures
struct	Intb_Man_t_

Functions
static Aig_Obj_t **	Intb_ManAigRead (Intb_Man_t *pMan, Sto_Cls_t *pCls)
static void	Intb_ManAigClear (Intb_Man_t *pMan, Aig_Obj_t **p)
static void	Intb_ManAigFill (Intb_Man_t *pMan, Aig_Obj_t **p)
static void	Intb_ManAigCopy (Intb_Man_t *pMan, Aig_Obj_t **p, Aig_Obj_t **q)
static void	Intb_ManAigAnd (Intb_Man_t *pMan, Aig_Obj_t **p, Aig_Obj_t **q)
static void	Intb_ManAigOr (Intb_Man_t *pMan, Aig_Obj_t **p, Aig_Obj_t **q)
static void	Intb_ManAigOrNot (Intb_Man_t *pMan, Aig_Obj_t **p, Aig_Obj_t **q)
static void	Intb_ManAigOrVar (Intb_Man_t *pMan, Aig_Obj_t **p, int v)
static void	Intb_ManAigOrNotVar (Intb_Man_t *pMan, Aig_Obj_t **p, int v)
static void	Intb_ManAigMux0 (Intb_Man_t *pMan, Aig_Obj_t **p, Aig_Obj_t **q, int v)
static void	Intb_ManAigMux1 (Intb_Man_t *pMan, Aig_Obj_t **p, Aig_Obj_t **q, int v)
static int	Intb_ManProofGet (Intb_Man_t *p, Sto_Cls_t *pCls)
static void	Intb_ManProofSet (Intb_Man_t *p, Sto_Cls_t *pCls, int n)
Intb_Man_t *	Intb_ManAlloc ()
	FUNCTION DEFINITIONS ///. More...
int	Intb_ManGlobalVars (Intb_Man_t *p)
void	Intb_ManResize (Intb_Man_t *p)
void	Intb_ManFree (Intb_Man_t *p)
void	Intb_ManPrintClause (Intb_Man_t *p, Sto_Cls_t *pClause)
void	Intb_ManPrintResolvent (lit *pResLits, int nResLits)
void	Intb_ManPrintInterOne (Intb_Man_t *p, Sto_Cls_t *pClause)
static void	Intb_ManWatchClause (Intb_Man_t *p, Sto_Cls_t *pClause, lit Lit)
static int	Intb_ManEnqueue (Intb_Man_t *p, lit Lit, Sto_Cls_t *pReason)
static void	Intb_ManCancelUntil (Intb_Man_t *p, int Level)
static Sto_Cls_t *	Intb_ManPropagateOne (Intb_Man_t *p, lit Lit)
Sto_Cls_t *	Intb_ManPropagate (Intb_Man_t *p, int Start)
void	Intb_ManProofWriteOne (Intb_Man_t *p, Sto_Cls_t *pClause)
int	Intb_ManGetGlobalVar (Intb_Man_t *p, int Var)
int	Intb_ManProofTraceOne (Intb_Man_t *p, Sto_Cls_t *pConflict, Sto_Cls_t *pFinal)
int	Intb_ManProofRecordOne (Intb_Man_t *p, Sto_Cls_t *pClause)
int	Intb_ManProcessRoots (Intb_Man_t *p)
void	Intb_ManPrepareInter (Intb_Man_t *p)
void *	Intb_ManInterpolate (Intb_Man_t *p, Sto_Man_t *pCnf, void *vVarsAB, int fVerbose)
Aig_Man_t *	Intb_ManDeriveClauses (Intb_Man_t *pMan, Sto_Man_t *pCnf, int fClausesA)

Variables
static ABC_NAMESPACE_IMPL_START const lit	LIT_UNDEF = 0xffffffff
	DECLARATIONS ///. More...

Function Documentation

static void Intb_ManAigAnd ( Intb_Man_t *  pMan, Aig_Obj_t **  p, Aig_Obj_t **  q  )

inlinestatic

Definition at line 83 of file satInterB.c.

{ *p = Aig_And(pMan->pAig, *p, *q);         }

static void Intb_ManAigClear ( Intb_Man_t *  pMan, Aig_Obj_t **  p  )

inlinestatic

Definition at line 80 of file satInterB.c.

{ *p = Aig_ManConst0(pMan->pAig);           }

static void Intb_ManAigCopy ( Intb_Man_t *  pMan, Aig_Obj_t **  p, Aig_Obj_t **  q  )

inlinestatic

Definition at line 82 of file satInterB.c.

{ *p = *q;                                  }

static void Intb_ManAigFill ( Intb_Man_t *  pMan, Aig_Obj_t **  p  )

inlinestatic

Definition at line 81 of file satInterB.c.

{ *p = Aig_ManConst1(pMan->pAig);           }

static void Intb_ManAigMux0 ( Intb_Man_t *  pMan, Aig_Obj_t **  p, Aig_Obj_t **  q, int  v  )

inlinestatic

Definition at line 88 of file satInterB.c.

{ *p = Aig_Mux(pMan->pAig, Aig_IthVar(pMan->pAig, v), *q, *p);     }

static void Intb_ManAigMux1 ( Intb_Man_t *  pMan, Aig_Obj_t **  p, Aig_Obj_t **  q, int  v  )

inlinestatic

Definition at line 89 of file satInterB.c.

{ *p = Aig_Mux(pMan->pAig, Aig_IthVar(pMan->pAig, v), *p, *q);     }

static void Intb_ManAigOr ( Intb_Man_t *  pMan, Aig_Obj_t **  p, Aig_Obj_t **  q  )

inlinestatic

Definition at line 84 of file satInterB.c.

{ *p = Aig_Or(pMan->pAig, *p, *q);          }

static void Intb_ManAigOrNot ( Intb_Man_t *  pMan, Aig_Obj_t **  p, Aig_Obj_t **  q  )

inlinestatic

Definition at line 85 of file satInterB.c.

{ *p = Aig_Or(pMan->pAig, *p, Aig_Not(*q)); }

static void Intb_ManAigOrNotVar ( Intb_Man_t *  pMan, Aig_Obj_t **  p, int  v  )

inlinestatic

Definition at line 87 of file satInterB.c.

{ *p = Aig_Or(pMan->pAig, *p, Aig_Not(Aig_IthVar(pMan->pAig, v))); }

static void Intb_ManAigOrVar ( Intb_Man_t *  pMan, Aig_Obj_t **  p, int  v  )

inlinestatic

Definition at line 86 of file satInterB.c.

{ *p = Aig_Or(pMan->pAig, *p, Aig_IthVar(pMan->pAig, v));          }

static Aig_Obj_t** Intb_ManAigRead ( Intb_Man_t *  pMan, Sto_Cls_t *  pCls  )

inlinestatic

Definition at line 79 of file satInterB.c.

{ return pMan->pInters + pCls->Id;          }

Intb_Man_t* Intb_ManAlloc

(

)

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis [Allocate proof manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 110 of file satInterB.c.

{
    Intb_Man_t * p;
    // allocate the manager
    p = (Intb_Man_t *)ABC_ALLOC( char, sizeof(Intb_Man_t) );
    memset( p, 0, sizeof(Intb_Man_t) );
    // verification
    p->nResLitsAlloc = (1<<16);
    p->pResLits = ABC_ALLOC( lit, p->nResLitsAlloc );
    // parameters
    p->fProofWrite = 0;
    p->fProofVerif = 1;
    return p;    
}

static void Intb_ManCancelUntil ( Intb_Man_t *  p, int  Level  )

inlinestatic

Function*************************************************************

Synopsis [Records implication.]

Description []

SideEffects []

SeeAlso []

Definition at line 397 of file satInterB.c.

{
    lit Lit;
    int i, Var;
    for ( i = p->nTrailSize - 1; i >= Level; i-- )
    {
        Lit = p->pTrail[i];
        Var = lit_var( Lit );
        p->pReasons[Var] = NULL;
        p->pAssigns[Var] = LIT_UNDEF;
//printf( "cancelling var %d\n", Var );
    }
    p->nTrailSize = Level;
}

Aig_Man_t* Intb_ManDeriveClauses	(	Intb_Man_t *	pMan,
		Sto_Man_t *	pCnf,
		int	fClausesA
	)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 1076 of file satInterB.c.

{
    Aig_Man_t * p;
    Aig_Obj_t * pMiter, * pSum, * pLit;
    Sto_Cls_t * pClause;
    int Var, VarAB, v;
    p = Aig_ManStart( 10000 );
    pMiter = Aig_ManConst1(p);
    Sto_ManForEachClauseRoot( pCnf, pClause )
    {
        if ( fClausesA ^ pClause->fA ) // clause of B
            continue;
        // clause of A
        pSum = Aig_ManConst0(p);
        for ( v = 0; v < (int)pClause->nLits; v++ )
        {
            Var = lit_var(pClause->pLits[v]);
            if ( pMan->pVarTypes[Var] < 0 ) // global var
            {
                VarAB = -pMan->pVarTypes[Var]-1;
                assert( VarAB >= 0 && VarAB < Vec_IntSize(pMan->vVarsAB) );
                pLit = Aig_NotCond( Aig_IthVar(p, VarAB), lit_sign(pClause->pLits[v]) );
            }
            else
                pLit = Aig_NotCond( Aig_IthVar(p, Vec_IntSize(pMan->vVarsAB)+1+Var), lit_sign(pClause->pLits[v]) );
            pSum = Aig_Or( p, pSum, pLit );
        }
        pMiter = Aig_And( p, pMiter, pSum );
    }
    Aig_ObjCreateCo( p, pMiter );
    return p;
}

static int Intb_ManEnqueue ( Intb_Man_t *  p, lit  Lit, Sto_Cls_t *  pReason  )

inlinestatic

Function*************************************************************

Synopsis [Records implication.]

Description []

SideEffects []

SeeAlso []

Definition at line 374 of file satInterB.c.

{
    int Var = lit_var(Lit);
    if ( p->pAssigns[Var] != LIT_UNDEF )
        return p->pAssigns[Var] == Lit;
    p->pAssigns[Var] = Lit;
    p->pReasons[Var] = pReason;
    p->pTrail[p->nTrailSize++] = Lit;
//printf( "assigning var %d value %d\n", Var, !lit_sign(Lit) );
    return 1;
}

void Intb_ManFree

(

Intb_Man_t *

p

)

Function*************************************************************

Synopsis [Deallocate proof manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 255 of file satInterB.c.

{
/*
    printf( "Runtime stats:\n" );
ABC_PRT( "BCP     ", p->timeBcp   );
ABC_PRT( "Trace   ", p->timeTrace );
ABC_PRT( "TOTAL   ", p->timeTotal );
*/
    ABC_FREE( p->pInters );
    ABC_FREE( p->pProofNums );
    ABC_FREE( p->pTrail );
    ABC_FREE( p->pAssigns );
    ABC_FREE( p->pSeens );
    ABC_FREE( p->pVarTypes );
    ABC_FREE( p->pReasons );
    ABC_FREE( p->pWatches );
    ABC_FREE( p->pResLits );
    ABC_FREE( p );
}

int Intb_ManGetGlobalVar	(	Intb_Man_t *	p,
		int	Var
	)

Function*************************************************************

Synopsis [Traces the proof for one clause.]

Description []

SideEffects []

SeeAlso []

Definition at line 547 of file satInterB.c.

{
    int VarAB;
    if ( p->pVarTypes[Var] >= 0 ) // global var
        return -1;
    VarAB = -p->pVarTypes[Var]-1;
    assert( VarAB >= 0 && VarAB < Vec_IntSize(p->vVarsAB) );
    return VarAB;
}

int Intb_ManGlobalVars

(

Intb_Man_t *

p

)

Function*************************************************************

Synopsis [Count common variables in the clauses of A and B.]

Description []

SideEffects []

SeeAlso []

Definition at line 136 of file satInterB.c.

{
    Sto_Cls_t * pClause;
    int LargeNum = -100000000;
    int Var, nVarsAB, v;

    // mark the variable encountered in the clauses of A
    Sto_ManForEachClauseRoot( p->pCnf, pClause )
    {
        if ( !pClause->fA )
            break;
        for ( v = 0; v < (int)pClause->nLits; v++ )
            p->pVarTypes[lit_var(pClause->pLits[v])] = 1;
    }

    // check variables that appear in clauses of B
    nVarsAB = 0;
    Sto_ManForEachClauseRoot( p->pCnf, pClause )
    {
        if ( pClause->fA )
            continue;
        for ( v = 0; v < (int)pClause->nLits; v++ )
        {
            Var = lit_var(pClause->pLits[v]);
            if ( p->pVarTypes[Var] == 1 ) // var of A
            {
                // change it into a global variable
                nVarsAB++;
                p->pVarTypes[Var] = LargeNum;
            }
        }
    }
    assert( nVarsAB <= Vec_IntSize(p->vVarsAB) );

    // order global variables
    nVarsAB = 0;
    Vec_IntForEachEntry( p->vVarsAB, Var, v )
        p->pVarTypes[Var] = -(1+nVarsAB++);

    // check that there is no extra global variables
    for ( v = 0; v < p->pCnf->nVars; v++ )
        assert( p->pVarTypes[v] != LargeNum );
    return nVarsAB;
}

void* Intb_ManInterpolate	(	Intb_Man_t *	p,
		Sto_Man_t *	pCnf,
		void *	vVarsAB,
		int	fVerbose
	)

Function*************************************************************

Synopsis [Computes interpolant for the given CNF.]

Description [Takes the interpolation manager, the CNF deriving by the SAT solver, which includes ClausesA, ClausesB, and learned clauses. Additional arguments are the vector of variables common to AB and the verbosiness flag. Returns the AIG manager with a single output, containing the interpolant.]

SideEffects []

SeeAlso []

Definition at line 987 of file satInterB.c.

{
    Aig_Man_t * pRes;
    Aig_Obj_t * pObj;
    Sto_Cls_t * pClause;
    int RetValue = 1;
    abctime clkTotal = Abc_Clock();

    // check that the CNF makes sense
    assert( pCnf->nVars > 0 && pCnf->nClauses > 0 );
    p->pCnf = pCnf;
    p->fVerbose = fVerbose;
    p->vVarsAB = (Vec_Int_t *)vVarsAB;
    p->pAig = pRes = Aig_ManStart( 10000 );
    Aig_IthVar( p->pAig, Vec_IntSize(p->vVarsAB) - 1 );

    // adjust the manager
    Intb_ManResize( p );

    // prepare the interpolant computation
    Intb_ManPrepareInter( p );

    // construct proof for each clause
    // start the proof
    if ( p->fProofWrite )
    {
        p->pFile = fopen( "proof.cnf_", "w" );
        p->Counter = 0;
    }

    // write the root clauses
    Sto_ManForEachClauseRoot( p->pCnf, pClause )
        Intb_ManProofWriteOne( p, pClause );

    // propagate root level assignments
    if ( Intb_ManProcessRoots( p ) )
    {
        // if there is no conflict, consider learned clauses
        Sto_ManForEachClause( p->pCnf, pClause )
        {
            if ( pClause->fRoot )
                continue;
            if ( !Intb_ManProofRecordOne( p, pClause ) )
            {
                RetValue = 0;
                break;
            }
        }
    }

    // stop the proof
    if ( p->fProofWrite )
    { 
        fclose( p->pFile );
//        Sat_ProofChecker( "proof.cnf_" );
        p->pFile = NULL;    
    }

    if ( fVerbose )
    {
//        ABC_PRT( "Interpo", Abc_Clock() - clkTotal );
    printf( "Vars = %d. Roots = %d. Learned = %d. Resol steps = %d.  Ave = %.2f.  Mem = %.2f MB\n", 
        p->pCnf->nVars, p->pCnf->nRoots, p->pCnf->nClauses-p->pCnf->nRoots, p->Counter,  
        1.0*(p->Counter-p->pCnf->nRoots)/(p->pCnf->nClauses-p->pCnf->nRoots), 
        1.0*Sto_ManMemoryReport(p->pCnf)/(1<<20) );
p->timeTotal += Abc_Clock() - clkTotal;
    }

    pObj = *Intb_ManAigRead( p, p->pCnf->pTail );
    Aig_ObjCreateCo( pRes, pObj );
    Aig_ManCleanup( pRes );

    p->pAig = NULL;
    return pRes;
    
}

void Intb_ManPrepareInter

(

Intb_Man_t *

p

)

Function*************************************************************

Synopsis [Records the proof.]

Description []

SideEffects []

SeeAlso []

Definition at line 940 of file satInterB.c.

{
    Sto_Cls_t * pClause;
    int Var, VarAB, v;

    // set interpolants for root clauses
    Sto_ManForEachClauseRoot( p->pCnf, pClause )
    {
        if ( !pClause->fA ) // clause of B
        {
            Intb_ManAigFill( p, Intb_ManAigRead(p, pClause) );
//            Intb_ManPrintInterOne( p, pClause );
            continue;
        }
        // clause of A
        Intb_ManAigClear( p, Intb_ManAigRead(p, pClause) );
        for ( v = 0; v < (int)pClause->nLits; v++ )
        {
            Var = lit_var(pClause->pLits[v]);
            if ( p->pVarTypes[Var] < 0 ) // global var
            {
                VarAB = -p->pVarTypes[Var]-1;
                assert( VarAB >= 0 && VarAB < Vec_IntSize(p->vVarsAB) );
                if ( lit_sign(pClause->pLits[v]) ) // negative var
                    Intb_ManAigOrNotVar( p, Intb_ManAigRead(p, pClause), VarAB );
                else
                    Intb_ManAigOrVar( p, Intb_ManAigRead(p, pClause), VarAB );
            }
        }
//        Intb_ManPrintInterOne( p, pClause );
    }
}

void Intb_ManPrintClause	(	Intb_Man_t *	p,
		Sto_Cls_t *	pClause
	)

Function*************************************************************

Synopsis [Prints the clause.]

Description []

SideEffects []

SeeAlso []

Definition at line 289 of file satInterB.c.

{
    int i;
    printf( "Clause ID = %d. Proof = %d. {", pClause->Id, Intb_ManProofGet(p, pClause) );
    for ( i = 0; i < (int)pClause->nLits; i++ )
        printf( " %d", pClause->pLits[i] );
    printf( " }\n" );
}

void Intb_ManPrintInterOne	(	Intb_Man_t *	p,
		Sto_Cls_t *	pClause
	)

Function*************************************************************

Synopsis [Prints the interpolant for one clause.]

Description []

SideEffects []

SeeAlso []

Definition at line 329 of file satInterB.c.

{
    printf( "Clause %2d :  ", pClause->Id );
//    Extra_PrintBinary___( stdout, Intb_ManAigRead(p, pClause), (1 << p->nVarsAB) );
    printf( "\n" );
}

void Intb_ManPrintResolvent	(	lit *	pResLits,
		int	nResLits
	)

Function*************************************************************

Synopsis [Prints the resolvent.]

Description []

SideEffects []

SeeAlso []

Definition at line 309 of file satInterB.c.

{
    int i;
    printf( "Resolvent: {" );
    for ( i = 0; i < nResLits; i++ )
        printf( " %d", pResLits[i] );
    printf( " }\n" );
}

int Intb_ManProcessRoots

(

Intb_Man_t *

p

)

Function*************************************************************

Synopsis [Propagate the root clauses.]

Description []

SideEffects []

SeeAlso []

Definition at line 867 of file satInterB.c.

{
    Sto_Cls_t * pClause;
    int Counter;

    // make sure the root clauses are preceeding the learnt clauses
    Counter = 0;
    Sto_ManForEachClause( p->pCnf, pClause )
    {
        assert( (int)pClause->fA    == (Counter < (int)p->pCnf->nClausesA) );
        assert( (int)pClause->fRoot == (Counter < (int)p->pCnf->nRoots)    );
        Counter++;
    }
    assert( p->pCnf->nClauses == Counter );

    // make sure the last clause if empty
    assert( p->pCnf->pTail->nLits == 0 );

    // go through the root unit clauses
    p->nTrailSize = 0;
    Sto_ManForEachClauseRoot( p->pCnf, pClause )
    {
        // create watcher lists for the root clauses
        if ( pClause->nLits > 1 )
        {
            Intb_ManWatchClause( p, pClause, pClause->pLits[0] );
            Intb_ManWatchClause( p, pClause, pClause->pLits[1] );
        }
        // empty clause and large clauses
        if ( pClause->nLits != 1 )
            continue;
        // unit clause
        assert( lit_check(pClause->pLits[0], p->pCnf->nVars) );
        if ( !Intb_ManEnqueue( p, pClause->pLits[0], pClause ) )
        {
            // detected root level conflict
//            printf( "Error in Intb_ManProcessRoots(): Detected a root-level conflict too early!\n" );
//            assert( 0 );
            // detected root level conflict
            Intb_ManProofTraceOne( p, pClause, p->pCnf->pEmpty );
            if ( p->fVerbose )
                printf( "Found root level conflict!\n" );
            return 0;
        }
    }

    // propagate the root unit clauses
    pClause = Intb_ManPropagate( p, 0 );
    if ( pClause )
    {
        // detected root level conflict
        Intb_ManProofTraceOne( p, pClause, p->pCnf->pEmpty );
        if ( p->fVerbose )
            printf( "Found root level conflict!\n" );
        return 0;
    }

    // set the root level
    p->nRootSize = p->nTrailSize;
    return 1;
}

static int Intb_ManProofGet ( Intb_Man_t *  p, Sto_Cls_t *  pCls  )

inlinestatic

Definition at line 92 of file satInterB.c.

{ return p->pProofNums[pCls->Id];           }

int Intb_ManProofRecordOne	(	Intb_Man_t *	p,
		Sto_Cls_t *	pClause
	)

Function*************************************************************

Synopsis [Records the proof for one clause.]

Description []

SideEffects []

SeeAlso []

Definition at line 762 of file satInterB.c.

{
    Sto_Cls_t * pConflict;
    int i;

    // empty clause never ends up there
    assert( pClause->nLits > 0 );
    if ( pClause->nLits == 0 )
        printf( "Error: Empty clause is attempted.\n" );

    assert( !pClause->fRoot );
    assert( p->nTrailSize == p->nRootSize );

    // if any of the clause literals are already assumed
    // it means that the clause is redundant and can be skipped
    for ( i = 0; i < (int)pClause->nLits; i++ )
        if ( p->pAssigns[lit_var(pClause->pLits[i])] == pClause->pLits[i] )
            return 1;

    // add assumptions to the trail
    for ( i = 0; i < (int)pClause->nLits; i++ )
        if ( !Intb_ManEnqueue( p, lit_neg(pClause->pLits[i]), NULL ) )
        {
            assert( 0 ); // impossible
            return 0;
        }

    // propagate the assumptions
    pConflict = Intb_ManPropagate( p, p->nRootSize );
    if ( pConflict == NULL )
    {
        assert( 0 ); // cannot prove
        return 0;
    } 

    // skip the clause if it is weaker or the same as the conflict clause
    if ( pClause->nLits >= pConflict->nLits )
    {
        // check if every literal of conflict clause can be found in the given clause
        int j;
        for ( i = 0; i < (int)pConflict->nLits; i++ )
        {
            for ( j = 0; j < (int)pClause->nLits; j++ )
                if ( pConflict->pLits[i] == pClause->pLits[j] )
                    break;
            if ( j == (int)pClause->nLits ) // literal pConflict->pLits[i] is not found
                break;
        }
        if ( i == (int)pConflict->nLits ) // all lits are found
        {
            // undo to the root level
            Intb_ManCancelUntil( p, p->nRootSize );
            return 1;
        }
    }

    // construct the proof
    Intb_ManProofTraceOne( p, pConflict, pClause );

    // undo to the root level
    Intb_ManCancelUntil( p, p->nRootSize );

    // add large clauses to the watched lists
    if ( pClause->nLits > 1 )
    {
        Intb_ManWatchClause( p, pClause, pClause->pLits[0] );
        Intb_ManWatchClause( p, pClause, pClause->pLits[1] );
        return 1;
    }
    assert( pClause->nLits == 1 );

    // if the clause proved is unit, add it and propagate
    if ( !Intb_ManEnqueue( p, pClause->pLits[0], pClause ) )
    {
        assert( 0 ); // impossible
        return 0;
    }

    // propagate the assumption
    pConflict = Intb_ManPropagate( p, p->nRootSize );
    if ( pConflict )
    {
        // construct the proof
        Intb_ManProofTraceOne( p, pConflict, p->pCnf->pEmpty );
//        if ( p->fVerbose )
//            printf( "Found last conflict after adding unit clause number %d!\n", pClause->Id );
        return 0;
    }

    // update the root level
    p->nRootSize = p->nTrailSize;
    return 1;
}

static void Intb_ManProofSet ( Intb_Man_t *  p, Sto_Cls_t *  pCls, int  n  )

inlinestatic

Definition at line 93 of file satInterB.c.

{ p->pProofNums[pCls->Id] = n;              }

int Intb_ManProofTraceOne	(	Intb_Man_t *	p,
		Sto_Cls_t *	pConflict,
		Sto_Cls_t *	pFinal
	)

Function*************************************************************

Synopsis [Traces the proof for one clause.]

Description []

SideEffects []

SeeAlso []

Definition at line 568 of file satInterB.c.

{
    Sto_Cls_t * pReason;
    int i, v, Var, PrevId;
    int fPrint = 0;
    abctime clk = Abc_Clock();

    // collect resolvent literals
    if ( p->fProofVerif )
    {
        assert( (int)pConflict->nLits <= p->nResLitsAlloc );
        memcpy( p->pResLits, pConflict->pLits, sizeof(lit) * pConflict->nLits );
        p->nResLits = pConflict->nLits;
    }

    // mark all the variables in the conflict as seen
    for ( v = 0; v < (int)pConflict->nLits; v++ )
        p->pSeens[lit_var(pConflict->pLits[v])] = 1;

    // start the anticedents
//    pFinal->pAntis = Vec_PtrAlloc( 32 );
//    Vec_PtrPush( pFinal->pAntis, pConflict );

    if ( p->pCnf->nClausesA )
        Intb_ManAigCopy( p, Intb_ManAigRead(p, pFinal), Intb_ManAigRead(p, pConflict) );

    // follow the trail backwards
    PrevId = Intb_ManProofGet(p, pConflict);
    for ( i = p->nTrailSize - 1; i >= 0; i-- )
    {
        // skip literals that are not involved
        Var = lit_var(p->pTrail[i]);
        if ( !p->pSeens[Var] )
            continue;
        p->pSeens[Var] = 0;

        // skip literals of the resulting clause
        pReason = p->pReasons[Var];
        if ( pReason == NULL )
            continue;
        assert( p->pTrail[i] == pReason->pLits[0] );

        // add the variables to seen
        for ( v = 1; v < (int)pReason->nLits; v++ )
            p->pSeens[lit_var(pReason->pLits[v])] = 1;

        // record the reason clause
        assert( Intb_ManProofGet(p, pReason) > 0 );
        p->Counter++;
        if ( p->fProofWrite )
            fprintf( p->pFile, "%d * %d %d 0\n", p->Counter, PrevId, Intb_ManProofGet(p, pReason) );
        PrevId = p->Counter;

        if ( p->pCnf->nClausesA )
        {
            if ( p->pVarTypes[Var] == 1 )// || rand() % 10 == 0 ) // var of A
                Intb_ManAigOr( p, Intb_ManAigRead(p, pFinal), Intb_ManAigRead(p, pReason) );
            else if ( p->pVarTypes[Var] == 0 ) // var of B
                Intb_ManAigAnd( p, Intb_ManAigRead(p, pFinal), Intb_ManAigRead(p, pReason) );
            else
            {
                int VarAB = Intb_ManGetGlobalVar(p, Var);
                // check that the var is present in the reason
                for ( v = 0; v < (int)pReason->nLits; v++ )
                    if ( lit_var(pReason->pLits[v]) == Var )
                        break;
                assert( v < (int)pReason->nLits );
                if ( lit_sign(pReason->pLits[v]) ) // negative polarity
                    Intb_ManAigMux0( p, Intb_ManAigRead(p, pFinal), Intb_ManAigRead(p, pReason), VarAB );
                else
                    Intb_ManAigMux1( p, Intb_ManAigRead(p, pFinal), Intb_ManAigRead(p, pReason), VarAB );
            }
        }
 
        // resolve the temporary resolvent with the reason clause
        if ( p->fProofVerif )
        {
            int v1, v2; 
            if ( fPrint )
                Intb_ManPrintResolvent( p->pResLits, p->nResLits );
            // check that the var is present in the resolvent
            for ( v1 = 0; v1 < p->nResLits; v1++ )
                if ( lit_var(p->pResLits[v1]) == Var )
                    break;
            if ( v1 == p->nResLits )
                printf( "Recording clause %d: Cannot find variable %d in the temporary resolvent.\n", pFinal->Id, Var );
            if ( p->pResLits[v1] != lit_neg(pReason->pLits[0]) )
                printf( "Recording clause %d: The resolved variable %d is in the wrong polarity.\n", pFinal->Id, Var );
            // remove this variable from the resolvent
            assert( lit_var(p->pResLits[v1]) == Var );
            p->nResLits--;
            for ( ; v1 < p->nResLits; v1++ )
                p->pResLits[v1] = p->pResLits[v1+1];
            // add variables of the reason clause
            for ( v2 = 1; v2 < (int)pReason->nLits; v2++ )
            {
                for ( v1 = 0; v1 < p->nResLits; v1++ )
                    if ( lit_var(p->pResLits[v1]) == lit_var(pReason->pLits[v2]) )
                        break;
                // if it is a new variable, add it to the resolvent
                if ( v1 == p->nResLits ) 
                {
                    if ( p->nResLits == p->nResLitsAlloc )
                        printf( "Recording clause %d: Ran out of space for intermediate resolvent.\n", pFinal->Id );
                    p->pResLits[ p->nResLits++ ] = pReason->pLits[v2];
                    continue;
                }
                // if the variable is the same, the literal should be the same too
                if ( p->pResLits[v1] == pReason->pLits[v2] )
                    continue;
                // the literal is different
                printf( "Recording clause %d: Trying to resolve the clause with more than one opposite literal.\n", pFinal->Id );
            }
        }
//        Vec_PtrPush( pFinal->pAntis, pReason );
    }

    // unmark all seen variables
//    for ( i = p->nTrailSize - 1; i >= 0; i-- )
//        p->pSeens[lit_var(p->pTrail[i])] = 0;
    // check that the literals are unmarked
//    for ( i = p->nTrailSize - 1; i >= 0; i-- )
//        assert( p->pSeens[lit_var(p->pTrail[i])] == 0 );

    // use the resulting clause to check the correctness of resolution
    if ( p->fProofVerif )
    {
        int v1, v2; 
        if ( fPrint )
            Intb_ManPrintResolvent( p->pResLits, p->nResLits );
        for ( v1 = 0; v1 < p->nResLits; v1++ )
        {
            for ( v2 = 0; v2 < (int)pFinal->nLits; v2++ )
                if ( pFinal->pLits[v2] == p->pResLits[v1] )
                    break;
            if ( v2 < (int)pFinal->nLits )
                continue;
            break;
        }
        if ( v1 < p->nResLits )
        {
            printf( "Recording clause %d: The final resolvent is wrong.\n", pFinal->Id );
            Intb_ManPrintClause( p, pConflict );
            Intb_ManPrintResolvent( p->pResLits, p->nResLits );
            Intb_ManPrintClause( p, pFinal );
        }

        // if there are literals in the clause that are not in the resolvent
        // it means that the derived resolvent is stronger than the clause
        // we can replace the clause with the resolvent by removing these literals
        if ( p->nResLits != (int)pFinal->nLits )
        {
            for ( v1 = 0; v1 < (int)pFinal->nLits; v1++ )
            {
                for ( v2 = 0; v2 < p->nResLits; v2++ )
                    if ( pFinal->pLits[v1] == p->pResLits[v2] )
                        break;
                if ( v2 < p->nResLits )
                    continue;
                // remove literal v1 from the final clause
                pFinal->nLits--;
                for ( v2 = v1; v2 < (int)pFinal->nLits; v2++ )
                    pFinal->pLits[v2] = pFinal->pLits[v2+1];
                v1--;
            }
            assert( p->nResLits == (int)pFinal->nLits );
        }
    }
p->timeTrace += Abc_Clock() - clk;

    // return the proof pointer 
    if ( p->pCnf->nClausesA )
    {
//        Intb_ManPrintInterOne( p, pFinal );
    }
    Intb_ManProofSet( p, pFinal, p->Counter );
    // make sure the same proof ID is not asssigned to two consecutive clauses
    assert( p->pProofNums[pFinal->Id-1] != p->Counter );
//    if ( p->pProofNums[pFinal->Id] == p->pProofNums[pFinal->Id-1] )
//        p->pProofNums[pFinal->Id] = p->pProofNums[pConflict->Id];
    return p->Counter;
}

void Intb_ManProofWriteOne	(	Intb_Man_t *	p,
		Sto_Cls_t *	pClause
	)

Function*************************************************************

Synopsis [Writes one root clause into a file.]

Description []

SideEffects []

SeeAlso []

Definition at line 522 of file satInterB.c.

{
    Intb_ManProofSet( p, pClause, ++p->Counter );

    if ( p->fProofWrite )
    {
        int v;
        fprintf( p->pFile, "%d", Intb_ManProofGet(p, pClause) );
        for ( v = 0; v < (int)pClause->nLits; v++ )
            fprintf( p->pFile, " %d", lit_print(pClause->pLits[v]) );
        fprintf( p->pFile, " 0 0\n" );
    }
}

Sto_Cls_t* Intb_ManPropagate	(	Intb_Man_t *	p,
		int	Start
	)

Function*************************************************************

Synopsis [Propagate the current assignments.]

Description []

SideEffects []

SeeAlso []

Definition at line 492 of file satInterB.c.

{
    Sto_Cls_t * pClause;
    int i;
    abctime clk = Abc_Clock();
    for ( i = Start; i < p->nTrailSize; i++ )
    {
        pClause = Intb_ManPropagateOne( p, p->pTrail[i] );
        if ( pClause )
        {
p->timeBcp += Abc_Clock() - clk;
            return pClause;
        }
    }
p->timeBcp += Abc_Clock() - clk;
    return NULL;
}

static Sto_Cls_t* Intb_ManPropagateOne ( Intb_Man_t *  p, lit  Lit  )

inlinestatic

Function*************************************************************

Synopsis [Propagate one assignment.]

Description []

SideEffects []

SeeAlso []

Definition at line 423 of file satInterB.c.

{
    Sto_Cls_t ** ppPrev, * pCur, * pTemp;
    lit LitF = lit_neg(Lit);
    int i;
    // iterate through the literals
    ppPrev = p->pWatches + Lit;
    for ( pCur = p->pWatches[Lit]; pCur; pCur = *ppPrev )
    {
        // make sure the false literal is in the second literal of the clause
        if ( pCur->pLits[0] == LitF )
        {
            pCur->pLits[0] = pCur->pLits[1];
            pCur->pLits[1] = LitF;
            pTemp = pCur->pNext0;
            pCur->pNext0 = pCur->pNext1;
            pCur->pNext1 = pTemp;
        }
        assert( pCur->pLits[1] == LitF );

        // if the first literal is true, the clause is satisfied
        if ( pCur->pLits[0] == p->pAssigns[lit_var(pCur->pLits[0])] )
        {
            ppPrev = &pCur->pNext1;
            continue;
        }

        // look for a new literal to watch
        for ( i = 2; i < (int)pCur->nLits; i++ )
        {
            // skip the case when the literal is false
            if ( lit_neg(pCur->pLits[i]) == p->pAssigns[lit_var(pCur->pLits[i])] )
                continue;
            // the literal is either true or unassigned - watch it
            pCur->pLits[1] = pCur->pLits[i];
            pCur->pLits[i] = LitF;
            // remove this clause from the watch list of Lit
            *ppPrev = pCur->pNext1;
            // add this clause to the watch list of pCur->pLits[i] (now it is pCur->pLits[1])
            Intb_ManWatchClause( p, pCur, pCur->pLits[1] );
            break;
        }
        if ( i < (int)pCur->nLits ) // found new watch
            continue;

        // clause is unit - enqueue new implication
        if ( Intb_ManEnqueue(p, pCur->pLits[0], pCur) )
        {
            ppPrev = &pCur->pNext1;
            continue;
        }

        // conflict detected - return the conflict clause
        return pCur;
    }
    return NULL;
}

void Intb_ManResize

(

Intb_Man_t *

p

)

Function*************************************************************

Synopsis [Resize proof manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 192 of file satInterB.c.

{
    p->Counter = 0;
    // check if resizing is needed
    if ( p->nVarsAlloc < p->pCnf->nVars )
    {
        // find the new size
        if ( p->nVarsAlloc == 0 )
            p->nVarsAlloc = 1;
        while ( p->nVarsAlloc < p->pCnf->nVars ) 
            p->nVarsAlloc *= 2;
        // resize the arrays
        p->pTrail    = ABC_REALLOC(lit,         p->pTrail,    p->nVarsAlloc );
        p->pAssigns  = ABC_REALLOC(lit,         p->pAssigns,  p->nVarsAlloc );
        p->pSeens    = ABC_REALLOC(char,        p->pSeens,    p->nVarsAlloc );
        p->pVarTypes = ABC_REALLOC(int,         p->pVarTypes, p->nVarsAlloc );
        p->pReasons  = ABC_REALLOC(Sto_Cls_t *, p->pReasons,  p->nVarsAlloc );
        p->pWatches  = ABC_REALLOC(Sto_Cls_t *, p->pWatches,  p->nVarsAlloc*2 );
    }

    // clean the free space
    memset( p->pAssigns , 0xff, sizeof(lit) * p->pCnf->nVars );
    memset( p->pSeens   , 0,    sizeof(char) * p->pCnf->nVars );
    memset( p->pVarTypes, 0,    sizeof(int) * p->pCnf->nVars );
    memset( p->pReasons , 0,    sizeof(Sto_Cls_t *) * p->pCnf->nVars );
    memset( p->pWatches , 0,    sizeof(Sto_Cls_t *) * p->pCnf->nVars*2 );

    // compute the number of common variables
    Intb_ManGlobalVars( p );

    // check if resizing of clauses is needed
    if ( p->nClosAlloc < p->pCnf->nClauses )
    {
        // find the new size
        if ( p->nClosAlloc == 0 )
            p->nClosAlloc = 1;
        while ( p->nClosAlloc < p->pCnf->nClauses ) 
            p->nClosAlloc *= 2;
        // resize the arrays
        p->pProofNums = ABC_REALLOC( int, p->pProofNums,  p->nClosAlloc );
    }
    memset( p->pProofNums, 0, sizeof(int) * p->pCnf->nClauses );

    // check if resizing of truth tables is needed
    if ( p->nIntersAlloc < p->pCnf->nClauses )
    {
        p->nIntersAlloc = p->pCnf->nClauses;
        p->pInters = ABC_REALLOC( Aig_Obj_t *, p->pInters, p->nIntersAlloc );
    }
    memset( p->pInters, 0, sizeof(Aig_Obj_t *) * p->pCnf->nClauses );
}

static void Intb_ManWatchClause ( Intb_Man_t *  p, Sto_Cls_t *  pClause, lit  Lit  )

inlinestatic

Function*************************************************************

Synopsis [Adds one clause to the watcher list.]

Description []

SideEffects []

SeeAlso []

Definition at line 349 of file satInterB.c.

{
    assert( lit_check(Lit, p->pCnf->nVars) );
    if ( pClause->pLits[0] == Lit )
        pClause->pNext0 = p->pWatches[lit_neg(Lit)];  
    else
    {
        assert( pClause->pLits[1] == Lit );
        pClause->pNext1 = p->pWatches[lit_neg(Lit)];  
    }
    p->pWatches[lit_neg(Lit)] = pClause;
}

Variable Documentation

ABC_NAMESPACE_IMPL_START const lit LIT_UNDEF = 0xffffffff

static

DECLARATIONS ///.

CFile****************************************************************

FileName [satInter.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [SAT sat_solver.]

Synopsis [Interpolation package.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - June 20, 2005.]

Revision [

Id:

satInter.c,v 1.4 2005/09/16 22:55:03 casem Exp

]

Definition at line 37 of file satInterB.c.