Version abc50806

1 files changed, 603 insertions, 0 deletions

diff --git a/src/opt/fxu/fxuSelect.c b/src/opt/fxu/fxuSelect.c
new file mode 100644
index 00000000..b56407a9
--- /dev/null
+++ b/src/opt/fxu/fxuSelect.c
@@ -0,0 +1,603 @@
+/**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"
+
+////////////////////////////////////////////////////////////////////////
+///                        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 DEFITIONS                           ///
+////////////////////////////////////////////////////////////////////////
+
+/**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];
+    Fxu_Double * pDoubles[MAX_SIZE_LOOKAHEAD];
+    // the complements
+    Fxu_Double * pSCompl[MAX_SIZE_LOOKAHEAD];
+    Fxu_Single * pDComplS[MAX_SIZE_LOOKAHEAD];
+    Fxu_Double * pDComplD[MAX_SIZE_LOOKAHEAD];
+    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                                ///
+////////////////////////////////////////////////////////////////////////
+
+