mvcutils.c

主要进行大规模的电路综合

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

  FileName    [mvcUtils.c]

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

  Synopsis    [Various cover handling utilities.]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

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

  Revision    [$Id: mvcUtils.c,v 1.14 2003/05/27 23:15:17 alanmi Exp $]

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

#include "mvc.h"

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

static int bit_count[256] = {
  0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
  1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
  1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
  2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
  1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
  2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
  2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
  3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
};


static void Mvc_CoverCopyColumn( Mvc_Cover_t * pCoverOld, Mvc_Cover_t * pCoverNew, int iColOld, int iColNew );


////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFITIONS                           ///
////////////////////////////////////////////////////////////////////////

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Mvc_CoverSupport( Mvc_Cover_t * pCover, Mvc_Cube_t * pSupp )
{
    Mvc_Cube_t * pCube;
    // clean the support
    Mvc_CubeBitClean( pSupp );
    // collect the support
    Mvc_CoverForEachCube( pCover, pCube )
        Mvc_CubeBitOr( pSupp, pSupp, pCube );
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Mvc_CoverCommonCube( Mvc_Cover_t * pCover, Mvc_Cube_t * pComCube )
{
    Mvc_Cube_t * pCube;
    // clean the support
    Mvc_CubeBitFill( pComCube );
    // collect the support
    Mvc_CoverForEachCube( pCover, pCube )
        Mvc_CubeBitAnd( pComCube, pComCube, pCube );
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
bool Mvc_CoverIsCubeFree( Mvc_Cover_t * pCover )
{
    bool Result;
    // get the common cube
    Mvc_CoverAllocateMask( pCover );
    Mvc_CoverCommonCube( pCover, pCover->pMask );
    // check whether the common cube is empty
    Mvc_CubeBitEmpty( Result, pCover->pMask );
    return Result;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Mvc_CoverMakeCubeFree( Mvc_Cover_t * pCover )
{
    Mvc_Cube_t * pCube;
    // get the common cube
    Mvc_CoverAllocateMask( pCover );
    Mvc_CoverCommonCube( pCover, pCover->pMask );
    // remove this cube from the cubes in the cover
    Mvc_CoverForEachCube( pCover, pCube )
        Mvc_CubeBitSharp( pCube, pCube, pCover->pMask );
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Mvc_Cover_t * Mvc_CoverCommonCubeCover( Mvc_Cover_t * pCover )
{
    Mvc_Cover_t * pRes;
    Mvc_Cube_t * pCube;
    // create the new cover
    pRes = Mvc_CoverClone( pCover );
    // get the new cube
    pCube = Mvc_CubeAlloc( pRes );
    // get the common cube
    Mvc_CoverCommonCube( pCover, pCube );
    // add the cube to the cover
    Mvc_CoverAddCubeTail( pRes, pCube );
    return pRes;
}


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

  Synopsis    [Returns 1 if the support of cover2 is contained in the support of cover1.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
bool Mvc_CoverCheckSuppContainment( Mvc_Cover_t * pCover1, Mvc_Cover_t * pCover2 )
{
    bool Result;
    assert( pCover1->nBits == pCover2->nBits );
    // set the supports
    Mvc_CoverAllocateMask( pCover1 );
    Mvc_CoverSupport( pCover1, pCover1->pMask );
    Mvc_CoverAllocateMask( pCover2 );
    Mvc_CoverSupport( pCover2, pCover2->pMask );
    // check the containment
    Mvc_CubeBitNotImpl( Result, pCover2->pMask, pCover1->pMask );
    return !Result;
}

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

  Synopsis    [Counts the cube sizes.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Mvc_CoverSetCubeSizes( Mvc_Cover_t * pCover )
{
    Mvc_Cube_t * pCube;
    uint8 * pByte, * pByteStart, * pByteStop;
    int nBytes, nOnes;

    // get the number of unsigned chars in the cube's bit strings
    nBytes = pCover->nBits / (8 * sizeof(uint8)) + (int)(pCover->nBits % (8 * sizeof(uint8)) > 0);
    // iterate through the cubes
    Mvc_CoverForEachCube( pCover, pCube )
    {
        // clean the counter of ones
        nOnes = 0;
        // set the starting and stopping positions
        pByteStart = (uint8 *)pCube->pData;
        pByteStop  = pByteStart + nBytes;
        // iterate through the positions
        for ( pByte = pByteStart; pByte < pByteStop; pByte++ )
            nOnes += bit_count[*pByte];
        // set the nOnes
        Mvc_CubeSetSize( pCube, nOnes );
    }
    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
  after they are made cube free.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Mvc_CoverCountCubePairDiffs( Mvc_Cover_t * pCover, unsigned char pDiffs[] )
{
    Mvc_Cube_t * pCube1;
    Mvc_Cube_t * pCube2;
    Mvc_Cube_t * pMask;
    uint8 * pByte, * pByteStart, * pByteStop;
    int nBytes, nOnes;
    int nCubePairs;

    // allocate a temporary mask
    pMask = Mvc_CubeAlloc( pCover );
    // get the number of unsigned chars in the cube's bit strings
    nBytes = pCover->nBits / (8 * sizeof(uint8)) + (int)(pCover->nBits % (8 * sizeof(uint8)) > 0);
    // iterate through the cubes
    nCubePairs = 0;
    Mvc_CoverForEachCube( pCover, pCube1 )
    {
        Mvc_CoverForEachCubeStart( Mvc_CubeReadNext(pCube1), pCube2 )
        {
            // find the bit-wise exor of cubes
            Mvc_CubeBitExor( pMask, pCube1, pCube2 );
            // set the starting and stopping positions
            pByteStart = (uint8 *)pMask->pData;
            pByteStop  = pByteStart + nBytes;
            // clean the counter of ones
            nOnes = 0;
            // iterate through the positions
            for ( pByte = pByteStart; pByte < pByteStop; pByte++ )
                nOnes += bit_count[*pByte];
            // set the nOnes
            pDiffs[nCubePairs++] = nOnes;
        }
    }
    // deallocate the mask
    Mvc_CubeFree( pCover, pMask );
    return 1;
}


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

  Synopsis    [Creates a new cover containing some literals of the old cover.]

  Description [Creates the new cover containing the given number (nVarsRem)
  literals of the old cover. All the bits of the new cover are initialized
  to "1". The selected bits from the old cover are copied on top. The numbers
  of the selected bits to copy are given in the array pVarsRem. The i-set
  entry in this array is the index of the bit in the old cover which goes
  to the i-th place in the new cover. If the i-th entry in pVarsRem is -1, 
  it means that the i-th bit does not change (remains composed of all 1's).
  This is a useful feature to speed up remapping covers, which are known
  to depend only on a subset of input variables.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Mvc_Cover_t * Mvc_CoverRemap( Mvc_Cover_t * p, int * pVarsRem, int nVarsRem )
{
    Mvc_Cover_t * pCover;
    Mvc_Cube_t * pCube, * pCubeCopy;
    int i;
    // clone the cover
    pCover = Mvc_CoverAlloc( p->pMem, nVarsRem );
    // copy the cube list
    Mvc_CoverForEachCube( p, pCube )
    {
        pCubeCopy = Mvc_CubeAlloc( pCover );
        //Mvc_CubeBitClean( pCubeCopy );   //changed by wjiang
        Mvc_CubeBitFill( pCubeCopy );      //changed by wjiang
        Mvc_CoverAddCubeTail( pCover, pCubeCopy );
    }
    // copy the corresponding columns
    for ( i = 0; i < nVarsRem; i++ )
    {
        if (pVarsRem[i] < 0) 
            continue;     //added by wjiang
        assert( pVarsRem[i] >= 0 && pVarsRem[i] < p->nBits );
        Mvc_CoverCopyColumn( p, pCover, pVarsRem[i], i );
    }
    return pCover;
}

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

  Synopsis    [Copies a column from the old cover to the new cover.]

  Description [Copies the column (iColOld) of the old cover (pCoverOld)
  into the column (iColNew) of the new cover (pCoverNew). Assumes that 
  the number of cubes is the same in both covers. Makes no assuptions 
  about the current contents of the column in the new cover.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Mvc_CoverCopyColumn( Mvc_Cover_t * pCoverOld, Mvc_Cover_t * pCoverNew, 
                         int iColOld, int iColNew )
{
    Mvc_Cube_t * pCubeOld, * pCubeNew;
    int iWordOld, iWordNew, iBitOld, iBitNew;

    assert( Mvc_CoverReadCubeNum(pCoverOld) == Mvc_CoverReadCubeNum(pCoverNew) );

    // get the place of the old and new columns
    iWordOld = Mvc_CubeWhichWord(iColOld);
    iBitOld  = Mvc_CubeWhichBit(iColOld);
    iWordNew = Mvc_CubeWhichWord(iColNew);
    iBitNew  = Mvc_CubeWhichBit(iColNew);