fxuselect.c

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

    // 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 )
{
    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                                ///
////////////////////////////////////////////////////////////////////////