vmxcode.c

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

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

  FileName    [vmx.c]

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

  Synopsis    [The extended variable map (VMX) package.]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

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

  Revision    [$Id: vmxCode.c,v 1.10 2003/05/27 23:15:26 alanmi Exp $]

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

#include "vmxInt.h"

/*
    Encoding and decoding procedures in this file assume the same kind
    of minimum-length (logarithmic) encoding with well-ballanced distribution
    of code minterms. For example, if 5-values are encoded using 2 bits,
    the following codes are used:
    value0 = 00-
    value1 = 01-
    value2 = 10-
    value3 = 110
    value4 = 111
             | |------------- least significant bit
             |--------------- most significant bit
*/

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

static void Vmx_VarMapEncode( DdManager * dd, DdNode * pbVars[], Vmx_VarMap_t * pVmx, int iVar, DdNode ** pbCodes );

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

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

  Synopsis    [Create the encoding of an VM using bits of VMX.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
DdNode ** Vmx_VarMapEncodeMap( DdManager * dd, Vmx_VarMap_t * pVmx )
{
    DdNode ** pbCodes;
    int * pValuesFirst;
    int nVars, v, i;

    // extend the local manager if necessary
    if ( dd->size < pVmx->nBits )
    {
        for ( i = dd->size; i < pVmx->nBits + 10; i++ )
            Cudd_bddIthVar( dd, i );
        Cudd_zddVarsFromBddVars( dd, 2 );
    }

    // get the parameters
    pbCodes      = pVmx->pMan->pbCodes;
    pValuesFirst = pVmx->pVm->pValuesFirst;
    nVars        = pVmx->pVm->nVarsIn + pVmx->pVm->nVarsOut;

    // derive the encoding
    for ( v = 0; v < nVars; v++ )
        Vmx_VarMapEncode( dd, dd->vars, pVmx, v, pbCodes + pValuesFirst[v] );
/*    
    // print out the variable value codes
	for ( i = 0; i < pVm->nVarsIn + pVm->nVarsOut; i++ )
	{
		printf( "VARIABLE #%d:\n", i );
		for ( v = 0; v < pVmx->pVm->pValues[i]; v++ )
		{
			printf( "Value %d:  ", v );
			PRB( dd, pbCodes[ pVmx->pVm->pValuesFirst[i] + v ] );
		}
	}
*/
    return pbCodes;
}


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

  Synopsis    [Create the encoding of an VM using bits of VMX.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
DdNode ** Vmx_VarMapEncodeMapUsingVars( DdManager * dd, DdNode * pbVars[], Vmx_VarMap_t * pVmx )
{
    DdNode ** pbCodes;
    int * pValuesFirst;
    int nVars, v;

    // the manager should be extended
    assert( dd->size >= pVmx->nBits );

    // get the parameters
    pbCodes      = pVmx->pMan->pbCodes;
    pValuesFirst = pVmx->pVm->pValuesFirst;
    nVars        = pVmx->pVm->nVarsIn + pVmx->pVm->nVarsOut;

    // derive the encoding
    for ( v = 0; v < nVars; v++ )
        Vmx_VarMapEncode( dd, pbVars, pVmx, v, pbCodes + pValuesFirst[v] );
    return pbCodes;
}

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

  Synopsis    [Derives encoding for one MV variable.]

  Description [Derives the encoding cubes to represent the MV variable 
  using binary variables. The BDD manager is used to build the cubes.
  The VMX (pVmx) contains information about the binary variables
  which are used to encode the MV variables of the VM (pVm).
  Uses two adjacent minterms to encode one value whenever possible.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
DdNode ** Vmx_VarMapEncodeVar( DdManager * dd, Vmx_VarMap_t * pVmx, int iVar )
{
    DdNode ** pbCodes;
    int * pValuesFirst;
    // derive the encoding
    pbCodes      = pVmx->pMan->pbCodes;
    pValuesFirst = pVmx->pVm->pValuesFirst;
    Vmx_VarMapEncode( dd, dd->vars, pVmx, iVar, pbCodes + pValuesFirst[iVar] );
    return pbCodes + pValuesFirst[iVar];
}

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

  Synopsis    [Derives encoding for one MV variable.]

  Description [Derives the encoding cubes to represent the MV variable 
  using binary variables. The BDD manager is used to build the cubes.
  The VMX (pVmx) contains information about the binary variables
  which are used to encode the MV variables of the VM (pVm).
  Uses two adjacent minterms to encode one value whenever possible.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Vmx_VarMapEncode( DdManager * dd, DdNode * pbVars[], Vmx_VarMap_t * pVmx, int iVar, DdNode ** pbCodes )
{
    Vmx_Manager_t * pMan;
    DdNode * bVar, * bCode, * bTemp;
    int nValues, nBits, nBitsFirst;
	int nValCube, nMinterms, iMint;
    int b, i;

    // general parameters
    pMan       = pVmx->pMan;
    // encoding parameters
    nValues    = pVmx->pVm->pValues[iVar]; // the number of values to encode
    nBits      = pVmx->pBits[iVar];        // the number of bits to use
	nBitsFirst = pVmx->pBitsFirst[iVar];   // the first bit
    nMinterms  = (1 << nBits);             // the number of minterms for codes
    nValCube   = nMinterms - nValues;      // the number of spare minterms (also, the number of values to be endoded with two minterms)

    // encode the values
    iMint = 0;
    for ( i = 0; i < nValues; i++ )
    {
        bCode = b1;   Cudd_Ref( bCode );
        // do not include the first bit into the set
        // for the codes of values encoded with two minterms
        for ( b = ((i < nValCube)? 1 : 0); b < nBits; b++ )
        {
            bVar = pbVars[ pVmx->pBitsOrder[nBitsFirst + b] ];
            if ( (iMint & (1<<b)) == 0 )
                bVar = Cudd_Not( bVar );
            bCode = Cudd_bddAnd( dd, bTemp = bCode, bVar );  Cudd_Ref( bCode );
            Cudd_RecursiveDeref( dd, bTemp );
        }
        // assign the code
        assert( pbCodes[i] == NULL );
        pbCodes[i] = bCode;
        // for the first codes, scroll through two minterms
        if ( i < nValCube )
            iMint += 2;
        else
            iMint += 1;
    }
}

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

  Synopsis    [Derefs the cubes associated with the variable map.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Vmx_VarMapEncodeDeref( DdManager * dd, Vmx_VarMap_t * pVmx, DdNode ** pbCodes )
{
    int i;
    // iterate through the referenced values
    for ( i = 0; pbCodes[i]; i++ )
    {
        Cudd_RecursiveDeref( dd, pbCodes[i] );
        pbCodes[i] = NULL;
    }
}

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

  Synopsis    [Returns the positive polarity cube, composed of binary vars representing the MV var.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
DdNode * Vmx_VarMapCharCube( DdManager * dd, Vmx_VarMap_t * pVmx, int iVar )
{
    DdNode * bCube, * bTemp, * bVar;
    int v;

    bCube = b1;  Cudd_Ref( bCube );
    for ( v = 0; v < pVmx->pBits[iVar]; v++ )
    {
        bVar = dd->vars[ pVmx->pBitsOrder[pVmx->pBitsFirst[iVar] + v] ];
        bCube = Cudd_bddAnd( dd, bTemp = bCube, bVar );  Cudd_Ref( bCube );
        Cudd_RecursiveDeref( dd, bTemp );
    }

    Cudd_Deref( bCube );
    return bCube;
}

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

  Synopsis    [Returns the positive polarity cube, composed of binary vars representing the MV var.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
DdNode * Vmx_VarMapCharCubeInput( DdManager * dd, Vmx_VarMap_t * pVmx )
{
    DdNode * bCube, * bTemp, * bComp;
    int v;

    bCube = b1;  Cudd_Ref( bCube );
    for ( v = 0; v < pVmx->pVm->nVarsIn; v++ )
    {
        bComp = Vmx_VarMapCharCube( dd, pVmx, v );       Cudd_Ref( bComp );
        bCube = Cudd_bddAnd( dd, bTemp = bCube, bComp ); Cudd_Ref( bCube );
        Cudd_RecursiveDeref( dd, bTemp );
        Cudd_RecursiveDeref( dd, bComp );
    }

    Cudd_Deref( bCube );
    return bCube;
}

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

  Synopsis    [Returns the positive polarity cube, composed of binary vars representing the MV var.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
DdNode * Vmx_VarMapCharCubeOutput( DdManager * dd, Vmx_VarMap_t * pVmx )
{
    DdNode * bCube, * bTemp, * bComp;
    int v;

    bCube = b1;  Cudd_Ref( bCube );
    for ( v = pVmx->pVm->nVarsIn; v < pVmx->pVm->nVarsIn + pVmx->pVm->nVarsOut; v++ )
    {
        bComp = Vmx_VarMapCharCube( dd, pVmx, v );       Cudd_Ref( bComp );
        bCube = Cudd_bddAnd( dd, bTemp = bCube, bComp ); Cudd_Ref( bCube );
        Cudd_RecursiveDeref( dd, bTemp );
        Cudd_RecursiveDeref( dd, bComp );
    }

    Cudd_Deref( bCube );
    return bCube;
}


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

  Synopsis    [Decodes the log-encoded binary cube into the positional MV cube.]

  Description [This procedure decodes the MV cube var values found in 
  pCubeBin and writes the input MV variable value sets into pCubeMv. 
  The decoding provided by this function is compatible with the encoding 
  performed by Vmx_VarMaEncode().]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Vmx_VarMapDecode( Vmx_VarMap_t * pVmx, int * pCubeBin, int * pCubeMv )
{
    Vm_VarMap_t * pVm = pVmx->pVm;
    unsigned MaskSign;   // signature of the bit-encoded value set
    unsigned MaskPolar;  // polarity of the bit-encoded value set
    unsigned Minterm1, Minterm2, Bit;
    int ValueSplit, ValueMax, Value;
    int i, b, v, nVars;

    nVars = pVmx->pVm->nVarsIn + pVmx->pVm->nVarsOut;
    for ( i = 0; i < nVars; i++ )
    {
        // get the mask
        MaskSign  = 0;
        MaskPolar = 0;
        for ( b = 0; b < pVmx->pBits[i]; b++ )
        {
            Value = pCubeBin[ pVmx->pBitsOrder[pVmx->pBitsFirst[i] + b] ];
//          Bit   = (1 << (pVmx->pBits[i]-1-b));
            Bit   = (1 << (b));

            if ( Value == 0 )
            {
                MaskSign |= Bit;
            }
            else if ( Value == 1 )
            {
                MaskSign  |= Bit;
                MaskPolar |= Bit;
            }
            else if ( Value != 2 )
            {
                assert( 0 );
            }
        }

        ValueSplit = ( 1 << pVmx->pBits[i] ) - pVm->pValues[i];

        // check what values overlap with the mask
        // these are those values that are encoded with two minterms each
        for ( v = 0; v < ValueSplit; v++ )
        {
            Minterm1 = (v<<1);
            Minterm2 = (v<<1) | 1;

            if ( ((MaskPolar ^ Minterm1) & MaskSign) == 0 || ((MaskPolar ^ Minterm2) & MaskSign) == 0 )
                pCubeMv[ pVm->pValuesFirst[i] + v ] = 1;
            else
                pCubeMv[ pVm->pValuesFirst[i] + v ] = 0;
        }

        // the remaining values are encoded with one minterm each
        ValueMax = (1 << pVmx->pBits[i]);
        for ( v = (v<<1); v < ValueMax; v++ )
            if ( ((MaskPolar ^ v) & MaskSign) == 0 )
                pCubeMv[ pVm->pValuesFirst[i] + v - ValueSplit ] = 1;
            else
                pCubeMv[ pVm->pValuesFirst[i] + v - ValueSplit ] = 0;
    }
}


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