satUtil.c 11 KB
Newer Older
Alan Mishchenko committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
/**CFile****************************************************************

  FileName    [satUtil.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [C-language MiniSat solver.]

  Synopsis    [Additional SAT solver procedures.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

  Revision    [$Id: satUtil.c,v 1.4 2005/09/16 22:55:03 casem Exp $]

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

#include <stdio.h>
#include <assert.h>
#include "satSolver.h"
24
#include "satSolver2.h"
Alan Mishchenko committed
25

26 27 28
ABC_NAMESPACE_IMPL_START


Alan Mishchenko committed
29 30 31 32
////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

33
static void Sat_SolverClauseWriteDimacs( FILE * pFile, clause * pC, int fIncrement );
Alan Mishchenko committed
34 35 36 37 38 39 40

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

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

41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
  Synopsis    [Writes the given clause in a file in DIMACS format.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Sat_SolverClauseWriteDimacs( FILE * pFile, clause * pC, int fIncrement )
{
    int i;
    for ( i = 0; i < (int)pC->size; i++ )
        fprintf( pFile, "%s%d ", (lit_sign(pC->lits[i])? "-": ""),  lit_var(pC->lits[i]) + (fIncrement>0) );
    if ( fIncrement )
        fprintf( pFile, "0" );
    fprintf( pFile, "\n" );
}

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

Alan Mishchenko committed
62 63 64 65 66 67 68 69 70
  Synopsis    [Write the clauses in the solver into a file in DIMACS format.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
71
void Sat_SolverWriteDimacs( sat_solver * p, char * pFileName, lit* assumpBegin, lit* assumpEnd, int incrementVars )
Alan Mishchenko committed
72
{
73
    Sat_Mem_t * pMem = &p->Mem;
Alan Mishchenko committed
74
    FILE * pFile;
75
    clause * c;
76 77 78 79 80 81 82
    int i, k, nUnits;

    // count the number of unit clauses
    nUnits = 0;
    for ( i = 0; i < p->size; i++ )
        if ( p->levels[i] == 0 && p->assigns[i] != l_Undef )
            nUnits++;
83 84 85 86 87 88 89 90 91

    // start the file
    pFile = fopen( pFileName, "wb" );
    if ( pFile == NULL )
    {
        printf( "Sat_SolverWriteDimacs(): Cannot open the ouput file.\n" );
        return;
    }
//    fprintf( pFile, "c CNF generated by ABC on %s\n", Extra_TimeStamp() );
92
    fprintf( pFile, "p cnf %d %d\n", p->size, Sat_MemEntryNum(&p->Mem, 0)+Sat_MemEntryNum(&p->Mem, 1)+nUnits+(int)(assumpEnd-assumpBegin) );
93 94 95 96 97 98 99 100

    // write the original clauses
    Sat_MemForEachClause( pMem, c, i, k )
        Sat_SolverClauseWriteDimacs( pFile, c, incrementVars );

    // write the learned clauses
    Sat_MemForEachLearned( pMem, c, i, k )
        Sat_SolverClauseWriteDimacs( pFile, c, incrementVars );
Alan Mishchenko committed
101

102
    // write zero-level assertions
Alan Mishchenko committed
103 104
    for ( i = 0; i < p->size; i++ )
        if ( p->levels[i] == 0 && p->assigns[i] != l_Undef )
105 106 107 108 109
            fprintf( pFile, "%s%d%s\n",
                     (p->assigns[i] == l_False)? "-": "",
                     i + (int)(incrementVars>0),
                     (incrementVars) ? " 0" : "");

110 111 112
    // write the assump
    if (assumpBegin) {
        for (; assumpBegin != assumpEnd; assumpBegin++) {
113
            fprintf( pFile, "%s%d%s\n",
114 115
                     lit_sign(*assumpBegin)? "-": "",
                     lit_var(*assumpBegin) + (int)(incrementVars>0),
116 117 118 119 120 121 122
                     (incrementVars) ? " 0" : "");
        }
    }

    fprintf( pFile, "\n" );
    fclose( pFile );
} 
123
void Sat_Solver2WriteDimacs( sat_solver2 * p, char * pFileName, lit* assumpBegin, lit* assumpEnd, int incrementVars )
124 125 126 127
{
    Sat_Mem_t * pMem = &p->Mem;
    FILE * pFile;
    clause * c;
128 129 130 131 132 133 134
    int i, k, nUnits;

    // count the number of unit clauses
    nUnits = 0;
    for ( i = 0; i < p->size; i++ )
        if ( p->levels[i] == 0 && p->assigns[i] != l_Undef )
            nUnits++;
Alan Mishchenko committed
135 136 137 138 139 140 141 142

    // start the file
    pFile = fopen( pFileName, "wb" );
    if ( pFile == NULL )
    {
        printf( "Sat_SolverWriteDimacs(): Cannot open the ouput file.\n" );
        return;
    }
Alan Mishchenko committed
143
//    fprintf( pFile, "c CNF generated by ABC on %s\n", Extra_TimeStamp() );
144
    fprintf( pFile, "p cnf %d %d\n", p->size, Sat_MemEntryNum(&p->Mem, 0)+Sat_MemEntryNum(&p->Mem, 1)+nUnits+(int)(assumpEnd-assumpBegin) );
Alan Mishchenko committed
145 146

    // write the original clauses
147 148
    Sat_MemForEachClause2( pMem, c, i, k )
        Sat_SolverClauseWriteDimacs( pFile, c, incrementVars );
Alan Mishchenko committed
149 150

    // write the learned clauses
151 152
    Sat_MemForEachLearned( pMem, c, i, k )
        Sat_SolverClauseWriteDimacs( pFile, c, incrementVars );
Alan Mishchenko committed
153 154 155 156 157 158 159 160 161

    // write zero-level assertions
    for ( i = 0; i < p->size; i++ )
        if ( p->levels[i] == 0 && p->assigns[i] != l_Undef )
            fprintf( pFile, "%s%d%s\n",
                     (p->assigns[i] == l_False)? "-": "",
                     i + (int)(incrementVars>0),
                     (incrementVars) ? " 0" : "");

162 163 164
    // write the assump
    if (assumpBegin) {
        for (; assumpBegin != assumpEnd; assumpBegin++) {
Alan Mishchenko committed
165
            fprintf( pFile, "%s%d%s\n",
166 167
                     lit_sign(*assumpBegin)? "-": "",
                     lit_var(*assumpBegin) + (int)(incrementVars>0),
Alan Mishchenko committed
168 169 170 171 172 173 174
                     (incrementVars) ? " 0" : "");
        }
    }

    fprintf( pFile, "\n" );
    fclose( pFile );
}   
175
  
Alan Mishchenko committed
176 177 178 179 180 181 182 183 184 185 186 187 188 189

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

  Synopsis    [Writes the given clause in a file in DIMACS format.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Sat_SolverPrintStats( FILE * pFile, sat_solver * p )
{
190 191 192 193 194
//    printf( "calls         : %10d (%d)\n", (int)p->nCalls, (int)p->nCalls2 );
    printf( "starts        : %10d\n", (int)p->stats.starts );
    printf( "conflicts     : %10d\n", (int)p->stats.conflicts );
    printf( "decisions     : %10d\n", (int)p->stats.decisions );
    printf( "propagations  : %10d\n", (int)p->stats.propagations );
195
//    printf( "inspects      : %10d\n", (int)p->stats.inspects );
196 197 198 199 200 201 202 203 204 205 206 207 208 209
//    printf( "inspects2     : %10d\n", (int)p->stats.inspects2 );
}

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

  Synopsis    [Writes the given clause in a file in DIMACS format.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
210
void Sat_Solver2PrintStats( FILE * pFile, sat_solver2 * s )
211
{
212 213 214 215 216 217
    printf( "starts        : %10d\n", (int)s->stats.starts );
    printf( "conflicts     : %10d\n", (int)s->stats.conflicts );
    printf( "decisions     : %10d\n", (int)s->stats.decisions );
    printf( "propagations  : %10d\n", (int)s->stats.propagations );
//    printf( "inspects      : %10d\n", (int)s->stats.inspects );
//    printf( "inspects2     : %10d\n", (int)s->stats.inspects2 );
218
/*
219
    printf( "memory for variables %.1f MB (free %6.2f %%) and clauses %.1f MB (free %6.2f %%)\n", 
220 221 222 223 224 225
        1.0 * Sat_Solver2GetVarMem(s) * s->size / (1<<20),
        100.0 * (s->cap - s->size) / s->cap,
        4.0 * (s->clauses.cap + s->learnts.cap) / (1<<20),
        100.0 * (s->clauses.cap - s->clauses.size + 
                 s->learnts.cap - s->learnts.size) / 
                (s->clauses.cap + s->learnts.cap) );
226
*/
Alan Mishchenko committed
227 228
}

Alan Mishchenko committed
229 230
/**Function*************************************************************

231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256
  Synopsis    [Returns the number of bytes used for each variable.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Sat_Solver2GetVarMem( sat_solver2 * s )
{
    int Mem = 0;
    Mem += (sizeof(s->activity[0]) == 4) ? sizeof(unsigned) : sizeof(double);  // activity
    Mem += 2 * sizeof(veci); // wlists
    Mem += sizeof(int);      // vi (variable info)
    Mem += sizeof(int);      // trail
    Mem += sizeof(int);      // orderpos
    Mem += sizeof(int);      // reasons
    Mem += sizeof(int);      // units
    Mem += sizeof(int);      // order
    Mem += sizeof(int);      // model
    return Mem;
}

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

Alan Mishchenko committed
257 258 259 260 261 262 263 264 265 266 267 268 269
  Synopsis    [Returns a counter-example.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int * Sat_SolverGetModel( sat_solver * p, int * pVars, int nVars )
{
    int * pModel;
    int i;
270
    pModel = ABC_CALLOC( int, nVars+1 );
Alan Mishchenko committed
271
    for ( i = 0; i < nVars; i++ )
272
        pModel[i] = sat_solver_var_value(p, pVars[i]);
Alan Mishchenko committed
273 274 275 276 277
    return pModel;    
}

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

278 279 280 281 282 283 284 285 286 287 288 289 290 291 292
  Synopsis    [Returns a counter-example.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int * Sat_Solver2GetModel( sat_solver2 * p, int * pVars, int nVars )
{
    int * pModel;
    int i;
    pModel = ABC_CALLOC( int, nVars+1 );
    for ( i = 0; i < nVars; i++ )
293
        pModel[i] = sat_solver2_var_value(p, pVars[i]);
294 295 296 297 298
    return pModel;    
}

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

Alan Mishchenko committed
299 300 301 302 303 304 305 306 307 308 309
  Synopsis    [Duplicates all clauses, complements unit clause of the given var.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Sat_SolverDoubleClauses( sat_solver * p, int iVar )
{
310
    assert( 0 );
311
/*
Alan Mishchenko committed
312
    clause * pClause;
Alan Mishchenko committed
313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333
    lit Lit, * pLits;
    int RetValue, nClauses, nVarsOld, nLitsOld, nLits, c, v;
    // get the number of variables
    nVarsOld = p->size;
    nLitsOld = 2 * p->size;
    // extend the solver to depend on two sets of variables
    sat_solver_setnvars( p, 2 * p->size );
    // duplicate implications
    for ( v = 0; v < nVarsOld; v++ )
        if ( p->assigns[v] != l_Undef )
        {
            Lit = nLitsOld + toLitCond( v, p->assigns[v]==l_False );
            if ( v == iVar )
                Lit = lit_neg(Lit);
            RetValue = sat_solver_addclause( p, &Lit, &Lit + 1 );
            assert( RetValue );
        }
    // duplicate clauses
    nClauses = vecp_size(&p->clauses);
    for ( c = 0; c < nClauses; c++ )
    {
334
        pClause = (clause *)p->clauses.ptr[c];
Alan Mishchenko committed
335 336
        nLits = clause_size(pClause);
        pLits = clause_begin(pClause);
Alan Mishchenko committed
337 338 339 340 341 342 343
        for ( v = 0; v < nLits; v++ )
            pLits[v] += nLitsOld;
        RetValue = sat_solver_addclause( p, pLits, pLits + nLits );
        assert( RetValue );
        for ( v = 0; v < nLits; v++ )
            pLits[v] -= nLitsOld;
    }
344
*/
Alan Mishchenko committed
345 346
}

Alan Mishchenko committed
347 348 349 350 351 352

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


353 354
ABC_NAMESPACE_IMPL_END