mvrutils.c

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

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

  FileName    [mvrUtils.c]

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

  Synopsis    [Functionality of the package to manipulate MV relations.]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

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

  Revision    [$Id: mvrUtils.c,v 1.25 2003/05/27 23:15:20 alanmi Exp $]

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

#include "mvrInt.h"

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

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

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

  Synopsis    [Creates MV relation.]

  Description [The first argument (nVars) is the number of input variables.
  The second argument (pValues) in the number of values for all variables, 
  the input and the output. Note that array pValues contains nVars + 1
  entries, where the last entry in the number of output values.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Mvr_Relation_t * Mvr_RelationCreate( Mvr_Manager_t * pMan, Vmx_VarMap_t * pVmx, DdNode * bRel )
{
    Mvr_Relation_t * pMvr;
    pMvr = Mvr_RelationAlloc();
    pMvr->pMan = pMan;
    pMvr->pVmx = pVmx;
    if ( bRel )
    {
        pMvr->bRel = bRel;   Cudd_Ref( bRel );
    }
    return pMvr;
}

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

  Synopsis    [Creates constant MV relation.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Mvr_Relation_t * Mvr_RelationCreateConstant( Mvr_Manager_t * pMan, Vmx_Manager_t * pManVmx, Vm_Manager_t * pManVm, int nValues, unsigned Pol )
{
    DdManager * dd = pMan->pDdLoc;
    Mvr_Relation_t * pMvr;
    Vm_VarMap_t * pVm;
    DdNode ** pbIsets;
    int i;
    // create the variable map
    pVm = Vm_VarMapLookup( pManVm, 0, 1, &nValues );
    // create the relation
    pMvr = Mvr_RelationAlloc();
    pMvr->pMan  = pMan;
    pMvr->pVmx  = Vmx_VarMapLookup( pManVmx, pVm, -1, NULL );
    // create the constant i-sets according to Polarity
    pbIsets = ALLOC( DdNode *, nValues );
    for ( i = 0; i < nValues; i++ )
    {
        if ( Pol & (1<<i) )
            pbIsets[i] = b1;
        else
            pbIsets[i] = b0;
        Cudd_Ref( pbIsets[i] );
    }
    // create the relation from cofactors
    Mvr_RelationCofactorsDeriveRelation( pMvr, pbIsets, 0, nValues );
    Mvr_RelationCofactorsDeref( pMvr, pbIsets, 0, nValues );
    FREE( pbIsets );
    return pMvr;
}

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

  Synopsis    [Creates relation of the single-output node.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Mvr_Relation_t * Mvr_RelationCreateOneInputOneOutput( Mvr_Manager_t * pMan, Vmx_Manager_t * pManVmx, Vm_Manager_t * pManVm, int nValuesIn, int nValuesOut, unsigned Pols[] )
{
    DdManager * dd = pMan->pDdLoc;
    Mvr_Relation_t * pMvr;
    Vm_VarMap_t * pVm;
    DdNode ** ppCodes;
    DdNode ** pbIsets;
    DdNode * bIset, * bTemp;
    int pValues[2];
    int i, k;

    // create the variable map
    pValues[0] = nValuesIn;
    pValues[1] = nValuesOut;
    pVm = Vm_VarMapLookup( pManVm, 1, 1, pValues );
    // create the relation

    pMvr = Mvr_RelationAlloc();
    pMvr->pMan = pMan;
    pMvr->pVmx = Vmx_VarMapLookup( pManVmx, pVm, -1, NULL );

    // get storage for i-sets
    pbIsets = ALLOC( DdNode *, nValuesOut );
    // get the input encoding cubes
    ppCodes = Vmx_VarMapEncodeVar( dd, pMvr->pVmx, 0 );
    // create the i-sets according to Polarities
    for ( i = 0; i < nValuesOut; i++ )
    {
        bIset = b0;   Cudd_Ref( bIset );
        for ( k = 0; k < nValuesIn; k++ )
            if ( Pols[i] & (1<<k) )
            {
                bIset = Cudd_bddOr( dd, bTemp = bIset, ppCodes[k] );  Cudd_Ref( bIset );
                Cudd_RecursiveDeref( dd, bTemp );
            }
        // set the i-set
        pbIsets[i] = bIset; // takes ref
    }
    // deref the cubes
    Vmx_VarMapEncodeDeref( dd, pMvr->pVmx, ppCodes );

    // create the relation from cofactors
    Mvr_RelationCofactorsDeriveRelation( pMvr, pbIsets, 1, nValuesOut );
    Mvr_RelationCofactorsDeref( pMvr, pbIsets, 1, nValuesOut );
    FREE( pbIsets );
    return pMvr;
}


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

  Synopsis    [Creates relation of the decoder.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Mvr_Relation_t * Mvr_RelationCreateTwoInputBinary( Mvr_Manager_t * pMan, Vmx_Manager_t * pManVmx, Vm_Manager_t * pManVm, unsigned TruthTable )
{
    DdManager * dd = pMan->pDdLoc;
    Mvr_Relation_t * pMvr;
    Vm_VarMap_t * pVm;
    DdNode ** ppCodes;
    DdNode * bOnSet, * bMint, * bVar0, * bVar1, * bTemp;
    int pValues[3];
    int i;
    // create the variable map
    pValues[0] = 2;
    pValues[1] = 2;
    pValues[2] = 2;
    pVm        = Vm_VarMapLookup( pManVm, 2, 1, pValues ); 
    pMvr       = Mvr_RelationAlloc();
    pMvr->pMan = pMan;
    pMvr->pVmx = Vmx_VarMapLookup( pManVmx, pVm, -1, NULL ); 

    // get the input encoding cubes
    ppCodes = Vmx_VarMapEncodeMap( dd, pMvr->pVmx );

    // derive the on-set of the two-input gate
    bOnSet = b0; Cudd_Ref( bOnSet );
    for ( i = 0; i < 4; i++ )
        if ( TruthTable & (1 << i) )
        {
            bVar0 = Cudd_NotCond( ppCodes[1], (i & 1)==0 );
            bVar1 = Cudd_NotCond( ppCodes[3], (i & 2)==0 );
            bMint = Cudd_bddAnd( dd, bVar0, bVar1 );           Cudd_Ref( bMint );
            bOnSet = Cudd_bddOr( dd, bTemp = bOnSet, bMint );  Cudd_Ref( bOnSet );
            Cudd_RecursiveDeref( dd, bTemp );
            Cudd_RecursiveDeref( dd, bMint );
        }
    // derive the relation
    pMvr->bRel = Cudd_bddXnor( dd, bOnSet, ppCodes[5] );  Cudd_Ref( pMvr->bRel );
    Cudd_RecursiveDeref( dd, bOnSet );
    // deref the cubes
    Vmx_VarMapEncodeDeref( dd, pMvr->pVmx, ppCodes );
    return pMvr;
}


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

  Synopsis    [Detects constant-1 i-sets of the relation.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
unsigned Mvr_RelationGetConstant( Mvr_Relation_t * pMvr )
{
    DdManager * dd;
    DdNode **   pbCodes;
    unsigned    iPos;
    int         i, nValues;
    // get the manager
    dd = pMvr->pMan->pDdLoc;
    // get the number of output values
    nValues = pMvr->pVmx->pVm->nValuesOut;
    assert( nValues <= 32 );
    // get the cubes encoding output values
    pbCodes = Vmx_VarMapEncodeVar( dd, pMvr->pVmx, pMvr->pVmx->pVm->nVarsIn );
    // check the containment of output encoding cubes in the relation
    // if some cube is contained, it means that this value is constant-1
    iPos = 0;
    for ( i = 0; i < nValues; ++i )
        if ( Cudd_bddLeq( dd, pbCodes[i], pMvr->bRel ) )
            iPos |= (1<<i);
    // deref the codes
    Vmx_VarMapEncodeDeref( dd, pMvr->pVmx, pbCodes );
    return iPos;
}


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

  Synopsis    [Creates relation of the decoder.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Mvr_Relation_t * Mvr_RelationCreateDecoder( Mvr_Manager_t * pMan, Vmx_Manager_t * pManVmx, Vm_Manager_t * pManVm, int nValues1, int nValues2 )
{
    DdManager * dd = pMan->pDdLoc;
    Mvr_Relation_t * pMvr;
    Vm_VarMap_t * pVm;
    DdNode ** ppCodes;
    DdNode ** pbIsets;
    DdNode * bValue1, * bValue2;
    int pValues[3];
    int i, k;
    // create the variable map
    pValues[0] = nValues1;
    pValues[1] = nValues2;
    pValues[2] = nValues1 * nValues2;
    pVm        = Vm_VarMapLookup( pManVm, 2, 1, pValues );
    pMvr       = Mvr_RelationAlloc();
    pMvr->pMan = pMan;
    pMvr->pVmx = Vmx_VarMapLookup( pManVmx, pVm, -1, NULL );

    // get storage for i-sets
    pbIsets = ALLOC( DdNode *, nValues1 * nValues2 );
    // get the input encoding cubes
    ppCodes = Vmx_VarMapEncodeMap( dd, pMvr->pVmx );
    // create the i-sets according to Polarities
    for ( i = 0; i < nValues1; i++ )
    for ( k = 0; k < nValues2; k++ )
    {
        bValue1 = ppCodes[ pVm->pValuesFirst[0] + i ];
        bValue2 = ppCodes[ pVm->pValuesFirst[1] + k ];
        pbIsets[nValues2*i+k] = Cudd_bddAnd( dd, bValue1, bValue2 );  
        Cudd_Ref( pbIsets[nValues2*i+k] );
    }
    // deref the cubes
    Vmx_VarMapEncodeDeref( dd, pMvr->pVmx, ppCodes );

    // create the relation from cofactors
    Mvr_RelationCofactorsDeriveRelation( pMvr, pbIsets, 2, nValues1 * nValues2 );
    Mvr_RelationCofactorsDeref( pMvr, pbIsets, 2, nValues1 * nValues2 );
    FREE( pbIsets );
    return pMvr;
}

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

  Synopsis    [Creates the relation of the decoder node.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Mvr_Relation_t * Mvr_RelationCreateDecoderGeneral( 
    Mvr_Manager_t * pMan, Vmx_Manager_t * pManVmx, Vm_Manager_t * pManVm, 
    int CodeWidth, int * pValueAssign, int nTotalValues, int nOutputValues )
{
    DdManager * dd = pMan->pDdLoc;
    Mvr_Relation_t * pMvr;
    DdNode ** ppCodes, ** pbIsets;
    DdNode * bMint, * bVar, * bTemp;
    Vmx_VarMap_t * pVmx;
    Vm_VarMap_t * pVm;
    int * pValues;
    int i, k, b;

    // create the var map
    pValues = ALLOC( int, CodeWidth + 1 );
    for ( i = 0; i < CodeWidth; i++ )
        pValues[i] = 2;
    pValues[CodeWidth] = nOutputValues;

    pVm = Vm_VarMapLookup( pManVm, CodeWidth, 1, pValues );
    pVmx = Vmx_VarMapLookup( pManVmx, pVm, -1, NULL ); 
    FREE( pValues );

    // create the relation
    pMvr       = Mvr_RelationAlloc();
    pMvr->pMan = pMan;
    pMvr->pVmx = pVmx;

    // get storage for i-sets
    pbIsets = ALLOC( DdNode *, nOutputValues );
    // initialize i-sets of the decoder to constant-0 BDDs
    for ( k = 0; k < nOutputValues; k++ )
    {
        pbIsets[k] = b0; Cudd_Ref( pbIsets[k] );
    }

    // get the input encoding cubes
    ppCodes = Vmx_VarMapEncodeMap( dd, pMvr->pVmx );
    // create the i-sets according to pValueAssign
    for ( i = 0; i < nTotalValues; i++ )
    {
        // build the BDD minterm representing code minterm i
        bMint = b1; Cudd_Ref( bMint );
        for ( b = 0; b < CodeWidth; b++ )
        {
            if ( i & ( 1 << b ) )
                bVar = ppCodes[2*b+1];
            else
                bVar = ppCodes[2*b];
            bMint = Cudd_bddAnd( dd, bTemp = bMint, bVar );    Cudd_Ref( bMint );
            Cudd_RecursiveDeref( dd, bTemp );
        }

        if ( pValueAssign[i] >= 0 )
        { // add the minterm to one i-set
            k = pValueAssign[i];
            assert( k < nOutputValues );
            pbIsets[k] = Cudd_bddOr( dd, bTemp = pbIsets[k], bMint ); Cudd_Ref( pbIsets[k] );
            Cudd_RecursiveDeref( dd, bTemp );
        }
        else
        { // add this minterm to all i-sets
            for ( k = 0; k < nOutputValues; k++ )
            {
                pbIsets[k] = Cudd_bddOr( dd, bTemp = pbIsets[k], bMint ); Cudd_Ref( pbIsets[k] );
                Cudd_RecursiveDeref( dd, bTemp );
            }
        }

        // deref this minterm
        Cudd_RecursiveDeref( dd, bMint );
    }
    // deref the cubes
    Vmx_VarMapEncodeDeref( dd, pMvr->pVmx, ppCodes );

    // create the relation from cofactors
    Mvr_RelationCofactorsDeriveRelation( pMvr, pbIsets, CodeWidth, nOutputValues );
    Mvr_RelationCofactorsDeref( pMvr, pbIsets, CodeWidth, nOutputValues );
    FREE( pbIsets );
    return pMvr;
}    

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

  Synopsis    [Encodes the relation using the given encoding.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Mvr_RelationCreateEncoded( 
    Mvr_Manager_t * pMan, Vmx_Manager_t * pManVmx, Vm_Manager_t * pManVm, 
    int CodeWidth, int * pValueAssign, int nTotalValues, int nOutputValues,
    Mvr_Relation_t ** ppMvrsRes, Mvr_Relation_t * pMvrInit )
{
    DdManager * dd = pMan->pDdLoc;
    Vm_VarMap_t * pVm, * pVmInit;
    Vmx_VarMap_t * pVmx;
    DdNode * pbIsetsInit[32], * pbIsetsRes[5][2];
    DdNode * bTemp;
    int * pValues, * pTransMap;
    int i, v;

    // get the original var map
    pVmInit = pMvrInit->pVmx->pVm;

    // create the new var map with the same input values as the init map
    // except for the output, which is binary
    pValues = ALLOC( int, pVmInit->nVarsIn + 1 );
    for ( i = 0; i < pVmInit->nVarsIn; i++ )
        pValues[i] = pVmInit->pValues[i]; // the input values
    pValues[pVmInit->nVarsIn] = 2; // the output value

    pVm = Vm_VarMapLookup( pManVm, pVmInit->nVarsIn, 1, pValues );
    pVmx = Vmx_VarMapLookup( pManVmx, pVm, -1, NULL );
    FREE( pValues );


    // cofactor the original relation
    Mvr_RelationCofactorsDerive( pMvrInit, pbIsetsInit, pVmInit->nVarsIn, nOutputValues );

    // remap the cofactors to the new variable map
    pTransMap = ALLOC( int, pVmInit->nVarsIn + 1 );
    for ( i = 0; i < pVmInit->nVarsIn; i++ )
        pTransMap[i] = i;
    pTransMap[pVmInit->nVarsIn] = -1; // unused

    for ( i = 0; i < nOutputValues; i++ )
    {
        pbIsetsInit[i] = Mvr_RelationRemap( pMvrInit, bTemp = pbIsetsInit[i], 
            pMvrInit->pVmx, pVmx, pTransMap );
        Cudd_Ref( pbIsetsInit[i] );
        Cudd_RecursiveDeref( dd, bTemp );
    }
    FREE( pTransMap );

    // clean the cofactors of the resulting relations
    for ( i = 0; i < CodeWidth; i++ )