extraUtilSupp.c 16.2 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
/**CFile****************************************************************

  FileName    [extraUtilSupp.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [extra]

  Synopsis    [Support minimization.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

  Revision    [$Id: extraUtilSupp.c,v 1.0 2003/02/01 00:00:00 alanmi Exp $]

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

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "misc/vec/vec.h"
26
#include "misc/vec/vecWec.h"
27
#include "extra.h"
28 29 30 31 32 33 34

ABC_NAMESPACE_IMPL_START

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

35 36 37
extern void         Extra_PrintBinary( FILE * pFile, unsigned Sign[], int nBits );


38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

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

  Synopsis    [Generate m-out-of-n vectors.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int Abc_SuppCountOnes( unsigned i )
{
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    i = ((i + (i >> 4)) & 0x0F0F0F0F);
    return (i*(0x01010101))>>24;
}
60
Vec_Wrd_t * Abc_SuppGen( int m, int n )
61
{
62
    Vec_Wrd_t * vRes = Vec_WrdAlloc( 1000 );
63 64 65
    int i, Size = (1 << n);
    for ( i = 0; i < Size; i++ )
        if ( Abc_SuppCountOnes(i) == m )
66
            Vec_WrdPush( vRes, i );
67 68 69 70 71
    return vRes;
}

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

72 73 74 75 76 77 78 79 80
  Synopsis    [Perform verification.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
81
void Abc_SuppVerify( Vec_Wrd_t * p, word * pMatrix, int nVars, int nVarsMin )
82
{
83 84 85 86 87 88
    Vec_Wrd_t * pNew;
    word * pLimit, * pEntry1, * pEntry2;
    word Entry, EntryNew;
    int i, k, v, Value, Counter = 0;
    pNew = Vec_WrdAlloc( Vec_WrdSize(p) );
    Vec_WrdForEachEntry( p, Entry, i )
89 90 91 92 93 94 95 96 97
    {
        EntryNew = 0;
        for ( v = 0; v < nVarsMin; v++ )
        {
            Value = 0;
            for ( k = 0; k < nVars; k++ )
                if ( ((pMatrix[v] >> k) & 1) && ((Entry >> k) & 1) )
                    Value ^= 1;
            if ( Value )
98
                EntryNew |= (((word)1) << v);            
99
        }
100
        Vec_WrdPush( pNew, EntryNew );
101 102
    }
    // check that they are disjoint
103 104
    pLimit  = Vec_WrdLimit(pNew);
    pEntry1 = Vec_WrdArray(pNew);
105 106 107 108 109 110 111 112
    for ( ; pEntry1 < pLimit; pEntry1++ )
    for ( pEntry2 = pEntry1 + 1; pEntry2 < pLimit; pEntry2++ )
        if ( *pEntry1 == *pEntry2 )
            Counter++;
    if ( Counter )
        printf( "The total of %d pairs fail verification.\n", Counter );
    else
        printf( "Verification successful.\n" );
113
    Vec_WrdFree( pNew );
114 115 116 117
}

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

118 119 120 121 122 123 124 125 126
  Synopsis    [Generate pairs.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
127
Vec_Wrd_t * Abc_SuppGenPairs( Vec_Wrd_t * p, int nBits )
128
{
129
    Vec_Wrd_t * vRes = Vec_WrdAlloc( 1000 );
130
    unsigned * pMap = ABC_CALLOC( unsigned, 1 << Abc_MaxInt(0,nBits-5) ); 
131 132 133
    word * pLimit = Vec_WrdLimit(p);
    word * pEntry1 = Vec_WrdArray(p);
    word * pEntry2, Value;
134 135 136 137
    for ( ; pEntry1 < pLimit; pEntry1++ )
    for ( pEntry2 = pEntry1 + 1; pEntry2 < pLimit; pEntry2++ )
    {
        Value = *pEntry1 ^ *pEntry2;
138
        if ( Abc_InfoHasBit(pMap, (int)Value) )
139
            continue;
140 141
        Abc_InfoXorBit( pMap, (int)Value );
        Vec_WrdPush( vRes, Value );
142 143 144 145
    }
    ABC_FREE( pMap );
    return vRes;
}
146
Vec_Wrd_t * Abc_SuppGenPairs2( int nOnes, int nBits )
Alan Mishchenko committed
147
{
148
    Vec_Wrd_t * vRes = Vec_WrdAlloc( 1000 );
Alan Mishchenko committed
149 150 151 152 153 154 155 156
    int i, k, Size = (1 << nBits), Value;
    for ( i = 0; i < Size; i++ )
    {
        Value = Abc_SuppCountOnes(i);
        for ( k = 1; k <= nOnes; k++ )
            if ( Value == 2*k )
                break;
        if ( k <= nOnes )
157
            Vec_WrdPush( vRes, i );
Alan Mishchenko committed
158 159 160
    }
    return vRes;
}
161 162 163 164 165 166 167 168 169 170 171 172

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

  Synopsis    [Select variable.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
173
void Abc_SuppPrintMask( word uMask, int nBits )
174 175 176
{
    int i;
    for ( i = 0; i < nBits; i++ )
Alan Mishchenko committed
177
        printf( "%d", (int)((uMask >> i) & 1) );
178 179
    printf( "\n" );
}
180
void Abc_SuppGenProfile( Vec_Wrd_t * p, int nBits, int * pCounts )
181
{
182 183 184
    word Ent;
    int i, k, b;
    Vec_WrdForEachEntry( p, Ent, i )
185 186 187
        for ( b = ((Ent >> nBits) & 1), k = 0; k < nBits; k++ )
            pCounts[k] += ((Ent >> k) & 1) ^ b;
}
188
void Abc_SuppPrintProfile( Vec_Wrd_t * p, int nBits )
189
{
190
    int k, Counts[64] = {0};
191 192
    Abc_SuppGenProfile( p, nBits, Counts );
    for ( k = 0; k < nBits; k++ )
193
        printf( "%2d : %6d  %6.2f %%\n", k, Counts[k], 100.0 * Counts[k] / Vec_WrdSize(p) );
194
}
195
int Abc_SuppGenFindBest( Vec_Wrd_t * p, int nBits, int * pMerit )
196
{
197
    int k, kBest = 0, Counts[64] = {0};
198 199 200 201 202 203 204
    Abc_SuppGenProfile( p, nBits, Counts );
    for ( k = 1; k < nBits; k++ )
        if ( Counts[kBest] < Counts[k] )
            kBest = k;
    *pMerit = Counts[kBest];
    return kBest;
}
205
void Abc_SuppGenSelectVar( Vec_Wrd_t * p, int nBits, int iVar )
206
{
207 208
    word * pEntry = Vec_WrdArray(p);
    word * pLimit = Vec_WrdLimit(p);
209 210
    for ( ; pEntry < pLimit; pEntry++ )
        if ( (*pEntry >> iVar) & 1 )
211
            *pEntry ^= (((word)1) << nBits);
212
}
213
void Abc_SuppGenFilter( Vec_Wrd_t * p, int nBits )
214
{
215 216 217
    word Ent;
    int i, k = 0;
    Vec_WrdForEachEntry( p, Ent, i )
218
        if ( ((Ent >> nBits) & 1) == 0 )
219 220
            Vec_WrdWriteEntry( p, k++, Ent );
    Vec_WrdShrink( p, k );
221
}
222
word Abc_SuppFindOne( Vec_Wrd_t * p, int nBits )
223
{
224
    word uMask = 0;
225 226 227 228 229 230 231 232
    int Prev = -1, This, Var;
    while ( 1 )
    {
        Var = Abc_SuppGenFindBest( p, nBits, &This );
        if ( Prev >= This )
            break;
        Prev = This;
        Abc_SuppGenSelectVar( p, nBits, Var );
233
        uMask |= (((word)1) << Var);
234 235 236
    }
    return uMask;
}
237
int Abc_SuppMinimize( word * pMatrix, Vec_Wrd_t * p, int nBits, int fVerbose )
238
{
239
    int i;
240
    for ( i = 0; Vec_WrdSize(p) > 0; i++ )
241 242
    {
//        Abc_SuppPrintProfile( p, nBits );
243
        pMatrix[i] = Abc_SuppFindOne( p, nBits );
244 245 246 247 248
        Abc_SuppGenFilter( p, nBits );   
        if ( !fVerbose )
            continue;
        // print stats
        printf( "%2d : ", i );
249
        printf( "%6d  ", Vec_WrdSize(p) );
250
        Abc_SuppPrintMask( pMatrix[i], nBits );
251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266
//        printf( "\n" );
    }
    return i;
}

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

  Synopsis    [Create representation.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
267
void Abc_SuppTest( int nOnes, int nVars, int fUseSimple, int fCheck, int fVerbose )
268 269
{
    int nVarsMin;
270
    word Matrix[64];
271 272
    abctime clk = Abc_Clock();
    // create the problem
273 274
    Vec_Wrd_t * vRes = Abc_SuppGen( nOnes, nVars );
    Vec_Wrd_t * vPairs = fUseSimple ? Abc_SuppGenPairs2( nOnes, nVars ) : Abc_SuppGenPairs( vRes, nVars );
275
    assert( nVars < 100 );
276
    printf( "M = %2d  N = %2d : ", nOnes, nVars );
277 278 279
    printf( "K = %6d   ",  Vec_WrdSize(vRes) );
    printf( "Total = %12.0f  ", 0.5 * Vec_WrdSize(vRes) * (Vec_WrdSize(vRes) - 1) );
    printf( "Distinct = %8d  ",  Vec_WrdSize(vPairs) );
280 281 282
    Abc_PrintTime( 1, "Reduction time", Abc_Clock() - clk );
    // solve the problem
    clk = Abc_Clock();
283
    nVarsMin = Abc_SuppMinimize( Matrix, vPairs, nVars, fVerbose );
284 285
    printf( "Solution with %d variables found.  ", nVarsMin );
    Abc_PrintTime( 1, "Covering time", Abc_Clock() - clk );
286 287
    if ( fCheck )
        Abc_SuppVerify( vRes, Matrix, nVars, nVarsMin );
288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404
    Vec_WrdFree( vPairs );
    Vec_WrdFree( vRes );
}


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

  Synopsis    [Reads the input part of the cubes specified in MIN format.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Wrd_t * Abc_SuppReadMin( char * pFileName, int * pnVars )
{
    Vec_Wrd_t * vRes; word uCube;
    int nCubes = 0, nVars = -1, iVar;
    char * pCur, * pToken, * pStart = "INPUT F-COVER";
    char * pStr = Extra_FileReadContents( pFileName );
    if ( pStr == NULL )
        { printf( "Cannot open input file (%s).\n", pFileName ); return NULL; }
    pCur = strstr( pStr, pStart );
    if ( pCur == NULL )
        { printf( "Cannot find beginning of cube cover (%s).\n", pStart ); return NULL; }
    pToken = strtok( pCur + strlen(pStart), " \t\r\n," );
    nCubes = atoi( pToken );
    if ( nCubes < 1 || nCubes > 1000000 )
        { printf( "The number of cubes in not in the range [1; 1000000].\n" ); return NULL; }
    vRes = Vec_WrdAlloc( 1000 );
    uCube = 0; iVar = 0;
    while ( (pToken = strtok(NULL, " \t\r\n,")) != NULL )
    {
        if ( strlen(pToken) > 2 )
        {
            if ( !strncmp(pToken, "INPUT", strlen("INPUT")) )
                break;
            if ( iVar > 64 )
                { printf( "The number of inputs (%d) is too high.\n", iVar ); Vec_WrdFree(vRes); return NULL; }
            if ( nVars == -1 )
                nVars = iVar;
            else if ( nVars != iVar )
                { printf( "The number of inputs (%d) does not match declaration (%d).\n", nVars, iVar ); Vec_WrdFree(vRes); return NULL; }
            Vec_WrdPush( vRes, uCube );
            uCube = 0; iVar = 0;
            continue;
        }
        if ( pToken[1] == '0' && pToken[0] == '1' ) // value 1
            uCube |= (((word)1) << iVar);
        else if ( pToken[1] != '1' || pToken[0] != '0' ) // value 0
            { printf( "Strange literal representation (%s) of cube %d.\n", pToken, nCubes ); Vec_WrdFree(vRes); return NULL; }
        iVar++;
    }
    ABC_FREE( pStr );
    if ( Vec_WrdSize(vRes) != nCubes )
        { printf( "The number of cubes (%d) does not match declaration (%d).\n", Vec_WrdSize(vRes), nCubes ); Vec_WrdFree(vRes); return NULL; }
    else
        printf( "Successfully parsed function with %d inputs and %d cubes.\n", nVars, nCubes );
    *pnVars = nVars;
    return vRes;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Wrd_t * Abc_SuppDiffMatrix( Vec_Wrd_t * vCubes )
{
    abctime clk = Abc_Clock();
    word * pEnt2, * pEnt = Vec_WrdArray( vCubes );
    word * pLimit = Vec_WrdLimit( vCubes );
    Vec_Wrd_t * vRes, * vPairs = Vec_WrdAlloc( Vec_WrdSize(vCubes) * (Vec_WrdSize(vCubes) - 1) / 2 );
    word * pStore = Vec_WrdArray( vPairs );
    for ( ; pEnt < pLimit; pEnt++ )
    for ( pEnt2 = pEnt+1; pEnt2 < pLimit; pEnt2++ )
        *pStore++ = *pEnt ^ *pEnt2;
    vPairs->nSize = Vec_WrdCap(vPairs);
    assert( pStore == Vec_WrdLimit(vPairs) );
//    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
//    vRes = Vec_WrdUniqifyHash( vPairs, 1 );
    vRes = Vec_WrdDup( vPairs );
    printf( "Successfully generated diff matrix with %10d rows (%6.2f %%).  ", 
        Vec_WrdSize(vRes), 100.0 * Vec_WrdSize(vRes) / Vec_WrdSize(vPairs) );
    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
    Vec_WrdFree( vPairs );
    return vRes;    
}

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

  Synopsis    [Solve difference matrix.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int Abc_SuppCountOnes64( word i )
{
    i = i - ((i >> 1) & 0x5555555555555555);
    i = (i & 0x3333333333333333) + ((i >> 2) & 0x3333333333333333);
    i = ((i + (i >> 4)) & 0x0F0F0F0F0F0F0F0F);
    return (i*(0x0101010101010101))>>56;
}
int Abc_SuppFindVar( Vec_Wec_t * pS, Vec_Wec_t * pD, int nVars )
{
Alan Mishchenko committed
405
    int v, vBest = -1, dBest = -1;
406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505
    for ( v = 0; v < nVars; v++ )
    {
        if ( Vec_WecLevelSize(pS, v) )
            continue;
        if ( vBest == -1 || dBest > Vec_WecLevelSize(pD, v) )
            vBest = v, dBest = Vec_WecLevelSize(pD, v);
    }
    return vBest;
}
void Abc_SuppRemove( Vec_Wrd_t * p, int * pCounts, Vec_Wec_t * pS, Vec_Wec_t * pD, int iVar, int nVars )
{
    word Entry; int i, v;
    assert( Vec_WecLevelSize(pS, iVar) == 0 );
    Vec_IntClear( Vec_WecEntry(pD, iVar) );
    Vec_WrdForEachEntry( p, Entry, i )
    {
        if ( ((Entry >> iVar) & 1) == 0 )
            continue;
        pCounts[i]--;
        if ( pCounts[i] == 1 )
        {
            for ( v = 0; v < nVars; v++ )
                if ( (Entry >> v) & 1 )
                {
                    Vec_IntRemove( Vec_WecEntry(pD, v), i );
                    Vec_WecPush( pS, v, i );
                }
        }
        else if ( pCounts[i] == 2 )
        {
            for ( v = 0; v < nVars; v++ )
                if ( (Entry >> v) & 1 )
                    Vec_WecPush( pD, v, i );
        }        
    }
}
void Abc_SuppProfile( Vec_Wec_t * pS, Vec_Wec_t * pD, int nVars )
{
    int v;
    for ( v = 0; v < nVars; v++ )
        printf( "%2d : S = %3d  D = %3d\n", v, Vec_WecLevelSize(pS, v), Vec_WecLevelSize(pD, v) );
}
int Abc_SuppSolve( Vec_Wrd_t * p, int nVars )
{
    abctime clk = Abc_Clock();
    Vec_Wrd_t * pNew = Vec_WrdDup( p );
    Vec_Wec_t * vSingles = Vec_WecStart( 64 );
    Vec_Wec_t * vDoubles = Vec_WecStart( 64 );
    word Entry; int i, v, iVar, nVarsNew = nVars;
    int * pCounts = ABC_ALLOC( int, Vec_WrdSize(p) );
    Vec_WrdForEachEntry( p, Entry, i )
    {
        pCounts[i] = Abc_SuppCountOnes64( Entry );
        if ( pCounts[i] == 1 )
        {
            for ( v = 0; v < nVars; v++ )
                if ( (Entry >> v) & 1 )
                    Vec_WecPush( vSingles, v, i );
        }
        else if ( pCounts[i] == 2 )
        {
            for ( v = 0; v < nVars; v++ )
                if ( (Entry >> v) & 1 )
                    Vec_WecPush( vDoubles, v, i );
        }
    }
    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
//    Abc_SuppProfile( vSingles, vDoubles, nVars );
    // find variable in 0 singles and the smallest doubles
    while ( 1 )
    {
        iVar = Abc_SuppFindVar( vSingles, vDoubles, nVars );
        if ( iVar == -1 )
            break;
//        printf( "Selected variable %d.\n", iVar );
        Abc_SuppRemove( pNew, pCounts, vSingles, vDoubles, iVar, nVars );
//        Abc_SuppProfile( vSingles, vDoubles, nVars );
        nVarsNew--;
    }
//    printf( "Result = %d (out of %d)\n", nVarsNew, nVars );
    Vec_WecFree( vSingles );
    Vec_WecFree( vDoubles );
    Vec_WrdFree( pNew );
    ABC_FREE( pCounts );
    return nVarsNew;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Abc_SuppReadMinTest( char * pFileName )
{
Alan Mishchenko committed
506
//    int fVerbose = 0;
507
    abctime clk = Abc_Clock();
508
//    word Matrix[64];
509 510 511 512 513 514 515 516 517 518 519 520 521 522 523
    int nVars, nVarsMin;
    Vec_Wrd_t * vPairs, * vCubes;
    vCubes = Abc_SuppReadMin( pFileName, &nVars );
    if ( vCubes == NULL )
        return;
    vPairs = Abc_SuppDiffMatrix( vCubes );
    Vec_WrdFreeP( &vCubes );
    // solve the problem
    clk = Abc_Clock();
//    nVarsMin = Abc_SuppMinimize( Matrix, vPairs, nVars, fVerbose );
    nVarsMin = Abc_SuppSolve( vPairs, nVars );
    printf( "Solution with %d variables found.  ", nVarsMin );
    Abc_PrintTime( 1, "Covering time", Abc_Clock() - clk );

    Vec_WrdFreeP( &vPairs );
524 525 526 527 528 529 530 531 532
}

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


ABC_NAMESPACE_IMPL_END