fxuReduce.c 7.34 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
/**CFile****************************************************************

  FileName    [fxuReduce.c]

  PackageName [MVSIS 2.0: Multi-valued logic synthesis system.]

  Synopsis    [Procedures to reduce the number of considered cube pairs.]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - February 1, 2003.]

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

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

#include "abc.h"
#include "fxuInt.h"
#include "fxu.h"

23 24 25
ABC_NAMESPACE_IMPL_START


Alan Mishchenko committed
26 27 28 29 30 31 32
////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

static int Fxu_CountPairDiffs( char * pCover, unsigned char pDiffs[] );

////////////////////////////////////////////////////////////////////////
Alan Mishchenko committed
33
///                     FUNCTION DEFINITIONS                         ///
Alan Mishchenko committed
34 35 36 37 38 39 40 41 42 43 44 45
////////////////////////////////////////////////////////////////////////

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

  Synopsis    [Precomputes the pairs to use for creating two-cube divisors.]

  Description [This procedure takes the matrix with variables and cubes 
  allocated (p), the original covers of the nodes (i-sets) and their number 
  (ppCovers,nCovers). The maximum number of pairs to compute and the total 
  number of pairs in existence. This procedure adds to the storage of
  divisors exactly the given number of pairs (nPairsMax) while taking
  first those pairs that have the smallest number of literals in their
46
  cube-free form.]
Alan Mishchenko committed
47 48 49 50 51 52 53 54 55 56 57 58 59 60
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Fxu_PreprocessCubePairs( Fxu_Matrix * p, Vec_Ptr_t * vCovers, int nPairsTotal, int nPairsMax )
{
    unsigned char * pnLitsDiff;   // storage for the counters of diff literals
    int * pnPairCounters;         // the counters of pairs for each number of diff literals
    Fxu_Cube * pCubeFirst, * pCubeLast;
    Fxu_Cube * pCube1, * pCube2;
    Fxu_Var * pVar;
    int nCubes, nBitsMax, nSum;
Alan Mishchenko committed
61
    int CutOffNum = -1, CutOffQuant = -1; // Suppress "might be used uninitialized"
Alan Mishchenko committed
62
    int iPair, iQuant, k, c;
Alan Mishchenko committed
63
//    int clk = clock();
Alan Mishchenko committed
64 65 66 67 68 69
    char * pSopCover;
    int nFanins;

    assert( nPairsMax < nPairsTotal );

    // allocate storage for counter of diffs
70
    pnLitsDiff = ABC_FALLOC( unsigned char, nPairsTotal );
Alan Mishchenko committed
71 72 73 74
    // go through the covers and precompute the distances between the pairs
    iPair    =  0;
    nBitsMax = -1;
    for ( c = 0; c < vCovers->nSize; c++ )
75
        if ( (pSopCover = (char *)vCovers->pArray[c]) )
Alan Mishchenko committed
76 77 78 79 80 81 82 83 84 85 86 87 88
        {
            nFanins = Abc_SopGetVarNum(pSopCover);
            // precompute the differences
            Fxu_CountPairDiffs( pSopCover, pnLitsDiff + iPair );
            // update the counter
            nCubes = Abc_SopGetCubeNum( pSopCover );
            iPair += nCubes * (nCubes - 1) / 2;
            if ( nBitsMax < nFanins )
                nBitsMax = nFanins;
        }
    assert( iPair == nPairsTotal );

    // allocate storage for counters of cube pairs by difference
89
    pnPairCounters = ABC_FALLOC( int, 2 * nBitsMax );
Alan Mishchenko committed
90 91 92 93 94 95
    memset( pnPairCounters, 0, sizeof(int) * 2 * nBitsMax );
    // count the number of different pairs
    for ( k = 0; k < nPairsTotal; k++ )
        pnPairCounters[ pnLitsDiff[k] ]++;
    // determine what pairs to take starting from the lower
    // so that there would be exactly pPairsMax pairs
Alan Mishchenko committed
96 97
    if ( pnPairCounters[0] != 0 )
    {
98 99
        ABC_FREE( pnLitsDiff );
        ABC_FREE( pnPairCounters );
Alan Mishchenko committed
100
        printf( "The SOPs of the nodes are not cube-ABC_FREE. Run \"bdd; sop\" before \"fx\".\n" );
Alan Mishchenko committed
101 102 103 104
        return 0;
    }
    if ( pnPairCounters[1] != 0 )
    {
105 106
        ABC_FREE( pnLitsDiff );
        ABC_FREE( pnPairCounters );
Alan Mishchenko committed
107
        printf( "The SOPs of the nodes are not SCC-ABC_FREE. Run \"bdd; sop\" before \"fx\".\n" );
Alan Mishchenko committed
108 109
        return 0;
    }
Alan Mishchenko committed
110 111
    assert( pnPairCounters[0] == 0 ); // otherwise, covers are not dup-ABC_FREE
    assert( pnPairCounters[1] == 0 ); // otherwise, covers are not SCC-ABC_FREE
Alan Mishchenko committed
112 113 114 115 116 117 118 119 120 121 122
    nSum = 0;
    for ( k = 0; k < 2 * nBitsMax; k++ )
    {
        nSum += pnPairCounters[k];
        if ( nSum >= nPairsMax )
        {
            CutOffNum   = k;
            CutOffQuant = pnPairCounters[k] - (nSum - nPairsMax);
            break;
        }
    }
Alan Mishchenko committed
123
    ABC_FREE( pnPairCounters );
Alan Mishchenko committed
124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144

    // set to 0 all the pairs above the cut-off number and quantity
    iQuant = 0;
    iPair  = 0;
    for ( k = 0; k < nPairsTotal; k++ )
        if ( pnLitsDiff[k] > CutOffNum ) 
            pnLitsDiff[k] = 0;
        else if ( pnLitsDiff[k] == CutOffNum )
        {
            if ( iQuant++ >= CutOffQuant )
                pnLitsDiff[k] = 0;
            else
                iPair++;
        }
        else
            iPair++;
    assert( iPair == nPairsMax );

    // collect the corresponding pairs and add the divisors
    iPair = 0;
    for ( c = 0; c < vCovers->nSize; c++ )
145
        if ( (pSopCover = (char *)vCovers->pArray[c]) )
Alan Mishchenko committed
146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165
        {
            // get the var
            pVar = p->ppVars[2*c+1];
            // get the first cube
            pCubeFirst = pVar->pFirst;
            // get the last cube
            pCubeLast = pCubeFirst;
            for ( k = 0; k < pVar->nCubes; k++ )
                pCubeLast = pCubeLast->pNext;
            assert( pCubeLast == NULL || pCubeLast->pVar != pVar );

            // go through the cube pairs
            for ( pCube1 = pCubeFirst; pCube1 != pCubeLast; pCube1 = pCube1->pNext )
                for ( pCube2 = pCube1->pNext; pCube2 != pCubeLast; pCube2 = pCube2->pNext )
                    if ( pnLitsDiff[iPair++] )
                    {   // create the divisors for this pair
                        Fxu_MatrixAddDivisor( p, pCube1, pCube2 );
                    }
        }
    assert( iPair == nPairsTotal );
Alan Mishchenko committed
166 167
    ABC_FREE( pnLitsDiff );
//ABC_PRT( "Preprocess", clock() - clk );
Alan Mishchenko committed
168 169 170 171 172 173 174 175 176 177 178 179 180
    return 1;
}


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

  Synopsis    [Counts the differences in each cube pair in the cover.]

  Description [Takes the cover (pCover) and the array where the
  diff counters go (pDiffs). The array pDiffs should have as many
  entries as there are different pairs of cubes in the cover: n(n-1)/2.
  Fills out the array pDiffs with the following info: For each cube
  pair, included in the array is the number of literals in both cubes
Alan Mishchenko committed
181
  after they are made cube ABC_FREE.]
Alan Mishchenko committed
182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Fxu_CountPairDiffs( char * pCover, unsigned char pDiffs[] )
{
    char * pCube1, * pCube2;
    int nOnes, nCubePairs, nFanins, v;
    nCubePairs = 0;
    nFanins = Abc_SopGetVarNum(pCover);
    Abc_SopForEachCube( pCover, nFanins, pCube1 )
    Abc_SopForEachCube( pCube1, nFanins, pCube2 )
    {
        if ( pCube1 == pCube2 )
            continue;
        nOnes = 0;
        for ( v = 0; v < nFanins; v++ )
            nOnes += (pCube1[v] != pCube2[v]);
        pDiffs[nCubePairs++] = nOnes;
    }
    return 1;
}

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


212 213
ABC_NAMESPACE_IMPL_END