fxuSelect.c

Go to the documentation of this file.

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

  FileName    [fxuSelect.c]

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

  Synopsis    [Procedures to select the best divisor/complement pair.]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

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

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

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

#include "fxuInt.h"

ABC_NAMESPACE_IMPL_START


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

#define MAX_SIZE_LOOKAHEAD      20

static int Fxu_MatrixFindComplement( Fxu_Matrix * p, int iVar );

static Fxu_Double * Fxu_MatrixFindComplementSingle( Fxu_Matrix * p, Fxu_Single * pSingle );
static Fxu_Single * Fxu_MatrixFindComplementDouble2( Fxu_Matrix * p, Fxu_Double * pDouble );
static Fxu_Double * Fxu_MatrixFindComplementDouble4( Fxu_Matrix * p, Fxu_Double * pDouble );

Fxu_Double * Fxu_MatrixFindDouble( Fxu_Matrix * p, 
     int piVarsC1[], int piVarsC2[], int nVarsC1, int nVarsC2 );
void Fxu_MatrixGetDoubleVars( Fxu_Matrix * p, Fxu_Double * pDouble, 
    int piVarsC1[], int piVarsC2[], int * pnVarsC1, int * pnVarsC2 );


////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

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

  Synopsis    [Selects the best pair (Single,Double) and returns their weight.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Fxu_Select( Fxu_Matrix * p, Fxu_Single ** ppSingle, Fxu_Double ** ppDouble )
{
    // the top entries
    Fxu_Single * pSingles[MAX_SIZE_LOOKAHEAD] = {0};
    Fxu_Double * pDoubles[MAX_SIZE_LOOKAHEAD] = {0};
    // the complements
    Fxu_Double * pSCompl[MAX_SIZE_LOOKAHEAD] = {0};
    Fxu_Single * pDComplS[MAX_SIZE_LOOKAHEAD] = {0};
    Fxu_Double * pDComplD[MAX_SIZE_LOOKAHEAD] = {0};
    Fxu_Pair * pPair;
    int nSingles;
    int nDoubles;
    int i;
    int WeightBest;
    int WeightCur;
    int iNum, fBestS;

    // collect the top entries from the queues
    for ( nSingles = 0; nSingles < MAX_SIZE_LOOKAHEAD; nSingles++ )
    {
        pSingles[nSingles] = Fxu_HeapSingleGetMax( p->pHeapSingle );
        if ( pSingles[nSingles] == NULL )
            break;
    }
    // put them back into the queue
    for ( i = 0; i < nSingles; i++ )
        if ( pSingles[i] )
            Fxu_HeapSingleInsert( p->pHeapSingle, pSingles[i] );
        
    // the same for doubles
    // collect the top entries from the queues
    for ( nDoubles = 0; nDoubles < MAX_SIZE_LOOKAHEAD; nDoubles++ )
    {
        pDoubles[nDoubles] = Fxu_HeapDoubleGetMax( p->pHeapDouble );
        if ( pDoubles[nDoubles] == NULL )
            break;
    }
    // put them back into the queue
    for ( i = 0; i < nDoubles; i++ )
        if ( pDoubles[i] )
            Fxu_HeapDoubleInsert( p->pHeapDouble, pDoubles[i] );

    // for each single, find the complement double (if any)
    for ( i = 0; i < nSingles; i++ )
        if ( pSingles[i] )
            pSCompl[i] = Fxu_MatrixFindComplementSingle( p, pSingles[i] );

    // for each double, find the complement single or double (if any)
    for ( i = 0; i < nDoubles; i++ )
        if ( pDoubles[i] )
        {
            pPair = pDoubles[i]->lPairs.pHead;
            if ( pPair->nLits1 == 1 && pPair->nLits2 == 1 )
            {
                pDComplS[i] = Fxu_MatrixFindComplementDouble2( p, pDoubles[i] );
                pDComplD[i] = NULL;
            }
//            else if ( pPair->nLits1 == 2 && pPair->nLits2 == 2 )
//            {
//                pDComplS[i] = NULL;
//                pDComplD[i] = Fxu_MatrixFindComplementDouble4( p, pDoubles[i] );
//            }
            else
            {
                pDComplS[i] = NULL;
                pDComplD[i] = NULL;
            }
        }

    // select the best pair
    WeightBest = -1;
    for ( i = 0; i < nSingles; i++ )
    {
        WeightCur = pSingles[i]->Weight;
        if ( pSCompl[i] )
        {
            // add the weight of the double
            WeightCur += pSCompl[i]->Weight;
            // there is no need to implement this double, so...
            pPair      = pSCompl[i]->lPairs.pHead;
            WeightCur += pPair->nLits1 + pPair->nLits2;
        }
        if ( WeightBest < WeightCur )
        {
            WeightBest = WeightCur;
            *ppSingle = pSingles[i];
            *ppDouble = pSCompl[i];
            fBestS = 1;
            iNum = i;
        }
    }
    for ( i = 0; i < nDoubles; i++ )
    {
        WeightCur = pDoubles[i]->Weight;
        if ( pDComplS[i] )
        {
            // add the weight of the single
            WeightCur += pDComplS[i]->Weight;
            // there is no need to implement this double, so...
            pPair      = pDoubles[i]->lPairs.pHead;
            WeightCur += pPair->nLits1 + pPair->nLits2;
        }
        if ( WeightBest < WeightCur )
        {
            WeightBest = WeightCur;
            *ppSingle = pDComplS[i];
            *ppDouble = pDoubles[i];
            fBestS = 0;
            iNum = i;
        }
    }
/*
    // print the statistics
    printf( "\n" );
    for ( i = 0; i < nSingles; i++ )
    {
        printf( "Single #%d: Weight = %3d. ", i, pSingles[i]->Weight );
        printf( "Compl: " );
        if ( pSCompl[i] == NULL )
            printf( "None." );
        else
            printf( "D  Weight = %3d  Sum = %3d", 
                pSCompl[i]->Weight, pSCompl[i]->Weight + pSingles[i]->Weight );
        printf( "\n" );
    }
    printf( "\n" );
    for ( i = 0; i < nDoubles; i++ )
    {
        printf( "Double #%d: Weight = %3d. ", i, pDoubles[i]->Weight );
        printf( "Compl: " );
        if ( pDComplS[i] == NULL && pDComplD[i] == NULL )
            printf( "None." );
        else if ( pDComplS[i] )
            printf( "S  Weight = %3d  Sum = %3d", 
                pDComplS[i]->Weight, pDComplS[i]->Weight + pDoubles[i]->Weight );
        else if ( pDComplD[i] )
            printf( "D  Weight = %3d  Sum = %3d", 
                pDComplD[i]->Weight, pDComplD[i]->Weight + pDoubles[i]->Weight );
        printf( "\n" );
    }
    if ( WeightBest == -1 )
        printf( "Selected NONE\n" );
    else
    {
        printf( "Selected = %s.  ", fBestS? "S": "D" );
        printf( "Number = %d.  ", iNum );
        printf( "Weight = %d.\n", WeightBest );
    }
    printf( "\n" );
*/
    return WeightBest;
}


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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Fxu_Double * Fxu_MatrixFindComplementSingle( Fxu_Matrix * p, Fxu_Single * pSingle )
{
//    int * pValue2Node = p->pValue2Node;
    int iVar1,  iVar2;
    int iVar1C, iVar2C;
    // get the variables of this single div
    iVar1  = pSingle->pVar1->iVar;
    iVar2  = pSingle->pVar2->iVar;
    iVar1C = Fxu_MatrixFindComplement( p, iVar1 );
    iVar2C = Fxu_MatrixFindComplement( p, iVar2 );
    if ( iVar1C == -1 || iVar2C == -1 )
        return NULL;
    assert( iVar1C < iVar2C );
    return Fxu_MatrixFindDouble( p, &iVar1C, &iVar2C, 1, 1 );
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Fxu_Single * Fxu_MatrixFindComplementDouble2( Fxu_Matrix * p, Fxu_Double * pDouble )
{
//    int * pValue2Node = p->pValue2Node;
    int piVarsC1[10], piVarsC2[10];
    int nVarsC1, nVarsC2;
    int iVar1,  iVar2, iVarTemp;
    int iVar1C, iVar2C;
    Fxu_Single * pSingle;

    // get the variables of this double div
    Fxu_MatrixGetDoubleVars( p, pDouble, piVarsC1, piVarsC2, &nVarsC1, &nVarsC2 );
    assert( nVarsC1 == 1 );
    assert( nVarsC2 == 1 );
    iVar1 = piVarsC1[0];
    iVar2 = piVarsC2[0];
    assert( iVar1 < iVar2 );

    iVar1C = Fxu_MatrixFindComplement( p, iVar1 );
    iVar2C = Fxu_MatrixFindComplement( p, iVar2 );
    if ( iVar1C == -1 || iVar2C == -1 )
        return NULL;
 
    // go through the queque and find this one
//    assert( iVar1C < iVar2C );
    if ( iVar1C > iVar2C )
    {
        iVarTemp = iVar1C;
        iVar1C = iVar2C;
        iVar2C = iVarTemp;
    }

    Fxu_MatrixForEachSingle( p, pSingle )
        if ( pSingle->pVar1->iVar == iVar1C && pSingle->pVar2->iVar == iVar2C )
            return pSingle;
    return NULL;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Fxu_Double * Fxu_MatrixFindComplementDouble4( Fxu_Matrix * p, Fxu_Double * pDouble )
{
//    int * pValue2Node = p->pValue2Node;
    int piVarsC1[10], piVarsC2[10];
    int nVarsC1, nVarsC2;
    int iVar11,  iVar12,  iVar21,  iVar22;
    int iVar11C, iVar12C, iVar21C, iVar22C;
    int RetValue;

    // get the variables of this double div
    Fxu_MatrixGetDoubleVars( p, pDouble, piVarsC1, piVarsC2, &nVarsC1, &nVarsC2 );
    assert( nVarsC1 == 2 && nVarsC2 == 2 );

    iVar11 = piVarsC1[0];
    iVar12 = piVarsC1[1];
    iVar21 = piVarsC2[0];
    iVar22 = piVarsC2[1];
    assert( iVar11 < iVar21 );

    iVar11C = Fxu_MatrixFindComplement( p, iVar11 );
    iVar12C = Fxu_MatrixFindComplement( p, iVar12 );
    iVar21C = Fxu_MatrixFindComplement( p, iVar21 );
    iVar22C = Fxu_MatrixFindComplement( p, iVar22 );
    if ( iVar11C == -1 || iVar12C == -1 || iVar21C == -1 || iVar22C == -1 )
        return NULL;
    if ( iVar11C != iVar21 || iVar12C != iVar22 || 
         iVar21C != iVar11 || iVar22C != iVar12 )
         return NULL;

    // a'b' + ab   =>  a'b  + ab'
    // a'b  + ab'  =>  a'b' + ab
    // swap the second pair in each cube
    RetValue    = piVarsC1[1];
    piVarsC1[1] = piVarsC2[1];
    piVarsC2[1] = RetValue;

    return Fxu_MatrixFindDouble( p, piVarsC1, piVarsC2, 2, 2 );
}


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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Fxu_MatrixFindComplement( Fxu_Matrix * p, int iVar )
{
    return iVar ^ 1;
/*
//    int * pValue2Node = p->pValue2Node;
    int iVarC;
    int iNode;
    int Beg, End;

    // get the nodes
    iNode = pValue2Node[iVar];
    // get the first node with the same var
    for ( Beg = iVar; Beg >= 0; Beg-- )
        if ( pValue2Node[Beg] != iNode )
        {
            Beg++;
            break;
        }
    // get the last node with the same var
    for ( End = iVar;          ; End++ )
        if ( pValue2Node[End] != iNode )
        {
            End--;
            break;
        }

    // if one of the vars is not binary, quit
    if ( End - Beg > 1 )
        return -1;

    // get the complements
    if ( iVar == Beg )
        iVarC = End;
    else if ( iVar == End ) 
        iVarC = Beg;
    else
    {
        assert( 0 );
    }
    return iVarC;
*/
}


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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fxu_MatrixGetDoubleVars( Fxu_Matrix * p, Fxu_Double * pDouble, 
    int piVarsC1[], int piVarsC2[], int * pnVarsC1, int * pnVarsC2 )
{
    Fxu_Pair * pPair;
    Fxu_Lit * pLit1, * pLit2;
    int nLits1, nLits2;

    // get the first pair
    pPair = pDouble->lPairs.pHead;
    // init the parameters
    nLits1 = 0;
    nLits2 = 0;
    pLit1 = pPair->pCube1->lLits.pHead;
    pLit2 = pPair->pCube2->lLits.pHead;
    while ( 1 )
    {
        if ( pLit1 && pLit2 )
        {
            if ( pLit1->iVar == pLit2->iVar )
            { // ensure cube-free
                pLit1 = pLit1->pHNext;
                pLit2 = pLit2->pHNext;
            }
            else if ( pLit1->iVar < pLit2->iVar )
            {
                piVarsC1[nLits1++] = pLit1->iVar;
                pLit1 = pLit1->pHNext;
           }
            else
            {
                piVarsC2[nLits2++] = pLit2->iVar;
                pLit2 = pLit2->pHNext;
            }
        }
        else if ( pLit1 && !pLit2 )
        {
            piVarsC1[nLits1++] = pLit1->iVar;
            pLit1 = pLit1->pHNext;
        }
        else if ( !pLit1 && pLit2 )
        {
            piVarsC2[nLits2++] = pLit2->iVar;
            pLit2 = pLit2->pHNext;
        }
        else
            break;
    }
    *pnVarsC1 = nLits1;
    *pnVarsC2 = nLits2;
}


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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Fxu_Double * Fxu_MatrixFindDouble( Fxu_Matrix * p, 
     int piVarsC1[], int piVarsC2[], int nVarsC1, int nVarsC2 )
{
    int piVarsC1_[100], piVarsC2_[100];
    int nVarsC1_, nVarsC2_, i;
    Fxu_Double * pDouble;
    Fxu_Pair * pPair;
    unsigned Key;

    assert( nVarsC1 > 0 );
    assert( nVarsC2 > 0 );
    assert( piVarsC1[0] < piVarsC2[0] );

    // get the hash key
    Key = Fxu_PairHashKeyArray( p, piVarsC1, piVarsC2, nVarsC1, nVarsC2 );
    
    // check if the divisor for this pair already exists
    Key %= p->nTableSize;
    Fxu_TableForEachDouble( p, Key, pDouble )
    {
        pPair = pDouble->lPairs.pHead;
        if ( pPair->nLits1 != nVarsC1 )
            continue;
        if ( pPair->nLits2 != nVarsC2 )
            continue;
        // get the cubes of this divisor
        Fxu_MatrixGetDoubleVars( p, pDouble, piVarsC1_, piVarsC2_, &nVarsC1_, &nVarsC2_ );
        // compare lits of the first cube
        for ( i = 0; i < nVarsC1; i++ )
            if ( piVarsC1[i] != piVarsC1_[i] )
                break;
        if ( i != nVarsC1 )
            continue;
        // compare lits of the second cube
        for ( i = 0; i < nVarsC2; i++ )
            if ( piVarsC2[i] != piVarsC2_[i] )
                break;
        if ( i != nVarsC2 )
            continue;
        return pDouble;
    }
    return NULL;
}





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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Fxu_SelectSCD( Fxu_Matrix * p, int WeightLimit, Fxu_Var ** ppVar1, Fxu_Var ** ppVar2 )
{
//    int * pValue2Node = p->pValue2Node;
    Fxu_Var * pVar1;
    Fxu_Var * pVar2, * pVarTemp;
    Fxu_Lit * pLitV, * pLitH;
    int Coin;
    int CounterAll;
    int CounterTest;
    int WeightCur;
    int WeightBest;

    CounterAll = 0;
    CounterTest = 0;

    WeightBest = -10;
    
    // iterate through the columns in the matrix
    Fxu_MatrixForEachVariable( p, pVar1 )
    {
        // start collecting the affected vars
        Fxu_MatrixRingVarsStart( p );

        // go through all the literals of this variable
        for ( pLitV = pVar1->lLits.pHead; pLitV; pLitV = pLitV->pVNext )
        {
            // for this literal, go through all the horizontal literals
            for ( pLitH = pLitV->pHNext; pLitH; pLitH = pLitH->pHNext )
            {
                // get another variable
                pVar2 = pLitH->pVar;
                CounterAll++;
                // skip the var if it is already used
                if ( pVar2->pOrder )
                    continue;
                // skip the var if it belongs to the same node
//                if ( pValue2Node[pVar1->iVar] == pValue2Node[pVar2->iVar] )
//                    continue;
                // collect the var
                Fxu_MatrixRingVarsAdd( p, pVar2 );
            }
        }
        // stop collecting the selected vars
        Fxu_MatrixRingVarsStop( p );

        // iterate through the selected vars
        Fxu_MatrixForEachVarInRing( p, pVar2 )
        {
            CounterTest++;

            // count the coincidence
            Coin = Fxu_SingleCountCoincidence( p, pVar1, pVar2 );
            assert( Coin > 0 );

            // get the new weight
            WeightCur = Coin - 2;

            // compare the weights
            if ( WeightBest < WeightCur )
            {
                WeightBest = WeightCur;
                *ppVar1 = pVar1;
                *ppVar2 = pVar2;
            }
        }
        // unmark the vars
        Fxu_MatrixForEachVarInRingSafe( p, pVar2, pVarTemp )
            pVar2->pOrder = NULL;
        Fxu_MatrixRingVarsReset( p );
    }

//    if ( WeightBest == WeightLimit )
//        return -1;
    return WeightBest;
}


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


ABC_NAMESPACE_IMPL_END