sbdLut.c

/**CFile****************************************************************

  FileName    [sbdLut.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [SAT-based optimization using internal don't-cares.]

  Synopsis    [CNF computation.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

  Revision    [$Id: sbdLut.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]

***********************************************************************/

#include "sbdInt.h"
#include "misc/util/utilTruth.h"

ABC_NAMESPACE_IMPL_START

////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
// count the number of parameter variables in the structure
int Sbd_ProblemCountParams( int nStrs, Sbd_Str_t * pStr0 )
{
    Sbd_Str_t * pStr;  int nPars = 0;
    for ( pStr = pStr0; pStr < pStr0 + nStrs; pStr++ )
        nPars += pStr->fLut ? 1 << pStr->nVarIns : pStr->nVarIns;
    return nPars;
}
// add clauses for the structure
int Sbd_ProblemAddClauses( sat_solver * pSat, int nVars, int nStrs, int * pVars, Sbd_Str_t * pStr0 )
{   
    // variable order:  inputs, structure outputs, parameters
    Sbd_Str_t * pStr;
    int VarOut = nVars;
    int VarPar = nVars + nStrs;
    int m, k, n, status, pLits[SBD_SIZE_MAX+2];
//printf( "Start par = %d.  ", VarPar );
    for ( pStr = pStr0; pStr < pStr0 + nStrs; pStr++, VarOut++ )
    {
        if ( pStr->fLut )
        {
            int nMints = 1 << pStr->nVarIns;
            assert( pStr->nVarIns <= 6 );
            for ( m = 0; m < nMints; m++, VarPar++ )
            {
                for ( k = 0; k < pStr->nVarIns; k++ )
                    pLits[k] = Abc_Var2Lit( pVars[pStr->VarIns[k]], (m >> k) & 1 ); 
                for ( n = 0; n < 2; n++ )
                {
                    pLits[pStr->nVarIns]   = Abc_Var2Lit( pVars[VarPar], n );
                    pLits[pStr->nVarIns+1] = Abc_Var2Lit( pVars[VarOut], !n );
                    status = sat_solver_addclause( pSat, pLits, pLits + pStr->nVarIns + 2 );
                    if ( !status )
                        return 0;
                }
            }
        }
        else
        {
            assert( pStr->nVarIns <= SBD_DIV_MAX );
            for ( k = 0; k < pStr->nVarIns; k++, VarPar++ )
            {
                for ( n = 0; n < 2; n++ )
                {
                    pLits[0] = Abc_Var2Lit( pVars[VarPar], 1 );
                    pLits[1] = Abc_Var2Lit( pVars[VarOut], n );
                    pLits[2] = Abc_Var2Lit( pVars[pStr->VarIns[k]], !n );
                    status = sat_solver_addclause( pSat, pLits, pLits + 3 );
                    if ( !status )
                        return 0;
                }
            }
        }
    }
    return 1;
}
void Sbd_ProblemAddClausesInit( sat_solver * pSat, int nVars, int nStrs, int * pVars, Sbd_Str_t * pStr0 )
{
    Sbd_Str_t * pStr;
    int VarPar = nVars + nStrs;
    int m, m2, status, pLits[SBD_DIV_MAX];
    // make sure selector parameters are mutually exclusive
    for ( pStr = pStr0; pStr < pStr0 + nStrs; VarPar += pStr->fLut ? 1 << pStr->nVarIns : pStr->nVarIns, pStr++ )
    {
        if ( pStr->fLut )
            continue;
        // one variable should be selected
        assert( pStr->nVarIns <= SBD_DIV_MAX );
        for ( m = 0; m < pStr->nVarIns; m++ )
            pLits[m] = Abc_Var2Lit( pVars[VarPar + m], 0 );
        status = sat_solver_addclause( pSat, pLits, pLits + pStr->nVarIns );
        assert( status );
        // two variables cannot be selected
        for ( m = 0; m < pStr->nVarIns; m++ )
        for ( m2 = m+1; m2 < pStr->nVarIns; m2++ )
        {
            pLits[0] = Abc_Var2Lit( pVars[VarPar + m], 1 );
            pLits[1] = Abc_Var2Lit( pVars[VarPar + m2], 1 );
            status = sat_solver_addclause( pSat, pLits, pLits + 2 );
            assert( status );
        }
    }
}
void Sbd_ProblemPrintSolution( int nStrs, Sbd_Str_t * pStr0, Vec_Int_t * vLits )
{
    Sbd_Str_t * pStr;
    int m, nIters, iLit = 0;
    printf( "Solution found:\n" );
    for ( pStr = pStr0; pStr < pStr0 + nStrs; pStr++ )
    {
        nIters = pStr->fLut ? 1 << pStr->nVarIns : pStr->nVarIns;
        printf( "%s%d : ", pStr->fLut ? "LUT":"SEL", (int)(pStr-pStr0) );
        for ( m = 0; m < nIters; m++, iLit++ )
            printf( "%d", !Abc_LitIsCompl(Vec_IntEntry(vLits, iLit)) );
        printf( "    {" );
        for ( m = 0; m < pStr->nVarIns; m++ )
            printf( " %d", pStr->VarIns[m] );
        printf( " }\n" );
    }
    assert( iLit == Vec_IntSize(vLits) );
}
void Sbd_ProblemCollectSolution( int nStrs, Sbd_Str_t * pStr0, Vec_Int_t * vLits )
{
    Sbd_Str_t * pStr;
    int m, nIters, iLit = 0;
    for ( pStr = pStr0; pStr < pStr0 + nStrs; pStr++ )
    {
        pStr->Res = 0;
        if ( pStr->fLut )
        {
            nIters = 1 << pStr->nVarIns;
            for ( m = 0; m < nIters; m++, iLit++ )
                if ( !Abc_LitIsCompl(Vec_IntEntry(vLits, iLit)) )
                    Abc_TtSetBit( &pStr->Res, m );
            pStr->Res = Abc_Tt6Stretch( pStr->Res, pStr->nVarIns );
        }
        else
        {
            nIters = 0;
            for ( m = 0; m < pStr->nVarIns; m++, iLit++ )
                if ( !Abc_LitIsCompl(Vec_IntEntry(vLits, iLit)) )
                {
                    pStr->Res = pStr->VarIns[m];
                    nIters++;
                }
            assert( nIters == 1 );
        }
    }
    assert( iLit == Vec_IntSize(vLits) );
}

/**Function*************************************************************

  Synopsis    [Solves QBF problem for the given window.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Sbd_ProblemSolve( Gia_Man_t * p, Vec_Int_t * vMirrors, 
                       int Pivot, Vec_Int_t * vWinObjs, Vec_Int_t * vObj2Var, 
                       Vec_Int_t * vTfo, Vec_Int_t * vRoots, 
                       Vec_Int_t * vDivSet, int nStrs, Sbd_Str_t * pStr0 )  // divisors, structures
{
    extern sat_solver * Sbd_ManSatSolver( sat_solver * pSat, Gia_Man_t * p, Vec_Int_t * vMirrors, int Pivot, Vec_Int_t * vWinObjs, Vec_Int_t * vObj2Var, Vec_Int_t * vTfo, Vec_Int_t * vRoots, int fQbf );
    
    int fVerbose = 0;
    abctime clk = Abc_Clock();
    Vec_Int_t * vLits    = Vec_IntAlloc( 100 );
    sat_solver * pSatCec = Sbd_ManSatSolver( NULL, p, vMirrors, Pivot, vWinObjs, vObj2Var, vTfo, vRoots, 1 );
    sat_solver * pSatQbf = sat_solver_new();

    int nVars      = Vec_IntSize( vDivSet );
    int nPars      = Sbd_ProblemCountParams( nStrs, pStr0 );

    int VarCecOut  = Vec_IntSize(vWinObjs) + Vec_IntSize(vTfo) + Vec_IntSize(vRoots);
    int VarCecPar  = VarCecOut + nStrs;

    int VarQbfPar  = 0;
    int VarQbfFree = nPars;

    int pVarsCec[256];
    int pVarsQbf[256];
    int i, iVar, iLit, nIters;
    int RetValue = 0;

    assert( Vec_IntSize(vDivSet) <= SBD_DIV_MAX );
    assert( nVars + nStrs + nPars <= 256 );

    // collect CEC variables
    Vec_IntForEachEntry( vDivSet, iVar, i )
        pVarsCec[i] = iVar;
    for ( i = 0; i < nStrs; i++ )
        pVarsCec[nVars + i] = VarCecOut + i;
    for ( i = 0; i < nPars; i++ )
        pVarsCec[nVars + nStrs + i] = VarCecPar + i;

    // collect QBF variables
    for ( i = 0; i < nVars + nStrs; i++ )
        pVarsQbf[i] = -1;
    for ( i = 0; i < nPars; i++ )
        pVarsQbf[nVars + nStrs + i] = VarQbfPar + i;

    // add clauses to the CEC problem
    Sbd_ProblemAddClauses( pSatCec, nVars, nStrs, pVarsCec, pStr0 );

    // create QBF solver
    sat_solver_setnvars( pSatQbf, 1000 );
    Sbd_ProblemAddClausesInit( pSatQbf, nVars, nStrs, pVarsQbf, pStr0 );

    // assume all parameter variables are 0
    Vec_IntClear( vLits );
    for ( i = 0; i < nPars; i++ )
        Vec_IntPush( vLits, Abc_Var2Lit(VarCecPar + i, 1) );
    for ( nIters = 0; nIters < (1 << nVars); nIters++ )
    {
        // check if these parameters solve the problem
        int status = sat_solver_solve( pSatCec, Vec_IntArray(vLits), Vec_IntLimit(vLits), 0, 0, 0, 0 );
        if ( status == l_False ) // solution found
            break;
        assert( status == l_True );

        if ( fVerbose )
        {
            printf( "Iter %3d : ", nIters );
            for ( i = 0; i < nPars; i++ )
                printf( "%d", !Abc_LitIsCompl(Vec_IntEntry(vLits, i)) );
            printf( "    " );
        }

        Vec_IntClear( vLits );
        // create new QBF variables
        for ( i = 0; i < nVars + nStrs; i++ )
            pVarsQbf[i] = VarQbfFree++;
        // set their values
        Vec_IntForEachEntry( vDivSet, iVar, i )
        {
            iLit = Abc_Var2Lit( pVarsQbf[i], !sat_solver_var_value(pSatCec, iVar) );
            status = sat_solver_addclause( pSatQbf, &iLit, &iLit + 1 );
            assert( status );
            if ( fVerbose )
                printf( "%d", sat_solver_var_value(pSatCec, iVar) );
        }
        iLit = Abc_Var2Lit( pVarsQbf[nVars], sat_solver_var_value(pSatCec, VarCecOut) );
        status = sat_solver_addclause( pSatQbf, &iLit, &iLit + 1 );
        assert( status );
        if ( fVerbose )
            printf( " %d\n", !sat_solver_var_value(pSatCec, VarCecOut) );
        // add clauses to the QBF problem
        if ( !Sbd_ProblemAddClauses( pSatQbf, nVars, nStrs, pVarsQbf, pStr0 ) )
            break; // solution does not exist
        // check if solution still exists
        status = sat_solver_solve( pSatQbf, NULL, NULL, 0, 0, 0, 0 );
        if ( status == l_False ) // solution does not exist
            break;
        assert( status == l_True ); 
        // find the new values of parameters
        assert( Vec_IntSize(vLits) == 0 );
        for ( i = 0; i < nPars; i++ )
            Vec_IntPush( vLits, Abc_Var2Lit(VarCecPar + i, !sat_solver_var_value(pSatQbf, VarQbfPar + i)) );
    }
    if ( Vec_IntSize(vLits) > 0 )
    {
        //Sbd_ProblemPrintSolution( nStrs, pStr0, vLits );
        Sbd_ProblemCollectSolution( nStrs, pStr0, vLits );
        RetValue = 1;
    }
    sat_solver_delete( pSatCec );
    sat_solver_delete( pSatQbf );
    Vec_IntFree( vLits );

    if ( fVerbose )
        Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
    return RetValue;
}


////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


ABC_NAMESPACE_IMPL_END