fxuSingle.c File Reference

#include "fxuInt.h"
#include "misc/vec/vec.h"

Go to the source code of this file.

Functions
static ABC_NAMESPACE_IMPL_START void	Fxu_MatrixComputeSinglesOneCollect (Fxu_Matrix *p, Fxu_Var *pVar, Vec_Ptr_t *vSingles)
	DECLARATIONS ///. More...
void	Fxu_MatrixComputeSingles (Fxu_Matrix *p, int fUse0, int nSingleMax)
	FUNCTION DEFINITIONS ///. More...
void	Fxu_MatrixComputeSinglesOne (Fxu_Matrix *p, Fxu_Var *pVar)
int	Fxu_SingleCountCoincidence (Fxu_Matrix *p, Fxu_Var *pVar1, Fxu_Var *pVar2)

Function Documentation

void Fxu_MatrixComputeSingles	(	Fxu_Matrix *	p,
		int	fUse0,
		int	nSingleMax
	)

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis [Computes and adds all single-cube divisors to storage.]

Description [This procedure should be called once when the matrix is already contructed before the process of logic extraction begins..]

SideEffects []

SeeAlso []

Definition at line 47 of file fxuSingle.c.

{
    Fxu_Var * pVar;
    Vec_Ptr_t * vSingles;
    int i, k;
    // set the weight limit
    p->nWeightLimit = 1 - fUse0;
    // iterate through columns in the matrix and collect single-cube divisors
    vSingles = Vec_PtrAlloc( 10000 );
    Fxu_MatrixForEachVariable( p, pVar )
        Fxu_MatrixComputeSinglesOneCollect( p, pVar, vSingles );
    p->nSingleTotal = Vec_PtrSize(vSingles) / 3;
    // check if divisors should be filtered
    if ( Vec_PtrSize(vSingles) > nSingleMax )
    {
        int * pWeigtCounts, nDivCount, Weight, i, c;;
        assert( Vec_PtrSize(vSingles) % 3 == 0 );
        // count how many divisors have the given weight
        pWeigtCounts = ABC_ALLOC( int, 1000 );
        memset( pWeigtCounts, 0, sizeof(int) * 1000 );
        for ( i = 2; i < Vec_PtrSize(vSingles); i += 3 )
        {
            Weight = (int)(ABC_PTRUINT_T)Vec_PtrEntry(vSingles, i);
            if ( Weight >= 999 )
                pWeigtCounts[999]++;
            else
                pWeigtCounts[Weight]++;
        }
        // select the bound on the weight (above this bound, singles will be included)
        nDivCount = 0;
        for ( c = 999; c >= 0; c-- )
        {
            nDivCount += pWeigtCounts[c];
            if ( nDivCount >= nSingleMax )
                break;
        }
        ABC_FREE( pWeigtCounts );
        // collect singles with the given costs
        k = 0;
        for ( i = 2; i < Vec_PtrSize(vSingles); i += 3 )
        {
            Weight = (int)(ABC_PTRUINT_T)Vec_PtrEntry(vSingles, i);
            if ( Weight < c )
                continue;
            Vec_PtrWriteEntry( vSingles, k++, Vec_PtrEntry(vSingles, i-2) );
            Vec_PtrWriteEntry( vSingles, k++, Vec_PtrEntry(vSingles, i-1) );
            Vec_PtrWriteEntry( vSingles, k++, Vec_PtrEntry(vSingles, i) );
            if ( k/3 == nSingleMax )
                break;
        }
        Vec_PtrShrink( vSingles, k );
        // adjust the weight limit
        p->nWeightLimit = c;
    }
    // collect the selected divisors
    assert( Vec_PtrSize(vSingles) % 3 == 0 );
    for ( i = 0; i < Vec_PtrSize(vSingles); i += 3 )
    {
        Fxu_MatrixAddSingle( p, 
            (Fxu_Var *)Vec_PtrEntry(vSingles,i), 
            (Fxu_Var *)Vec_PtrEntry(vSingles,i+1), 
            (int)(ABC_PTRUINT_T)Vec_PtrEntry(vSingles,i+2) );
    }
    Vec_PtrFree( vSingles );
}

void Fxu_MatrixComputeSinglesOne	(	Fxu_Matrix *	p,
		Fxu_Var *	pVar
	)

Function*************************************************************

Synopsis [Adds the single-cube divisors associated with a new column.]

Description []

SideEffects []

SeeAlso []

Definition at line 184 of file fxuSingle.c.

{
    Fxu_Lit * pLitV, * pLitH;
    Fxu_Var * pVar2;
    int Coin;
    int WeightCur;

    // start collecting the affected vars
    Fxu_MatrixRingVarsStart( p );
    // go through all the literals of this variable
    for ( pLitV = pVar->lLits.pHead; pLitV; pLitV = pLitV->pVNext )
        // for this literal, go through all the horizontal literals
        for ( pLitH = pLitV->pHPrev; pLitH; pLitH = pLitH->pHPrev )
        {
            // get another variable
            pVar2 = pLitH->pVar;
            // skip the var if it is already used
            if ( pVar2->pOrder )
                continue;
            // skip the var if it belongs to the same node
//            if ( pValue2Node[pVar->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 )
    {
        // count the coincidence
        Coin = Fxu_SingleCountCoincidence( p, pVar2, pVar );
        assert( Coin > 0 );
        // get the new weight
        WeightCur = Coin - 2;
        // peformance fix (August 24, 2007)
//        if ( WeightCur >= 0 )
//        Fxu_MatrixAddSingle( p, pVar2, pVar, WeightCur );
        if ( WeightCur >= p->nWeightLimit )
            Fxu_MatrixAddSingle( p, pVar2, pVar, WeightCur );
    }
    // unmark the vars
    Fxu_MatrixRingVarsUnmark( p );
}

void Fxu_MatrixComputeSinglesOneCollect ( Fxu_Matrix *  p, Fxu_Var *  pVar, Vec_Ptr_t *  vSingles  )

static

DECLARATIONS ///.

CFile****************************************************************

FileName [fxuSingle.c]

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

Synopsis [Procedures to compute the set of single-cube divisors.]

Author [MVSIS Group]

Affiliation [UC Berkeley]

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

Revision [

Id:

fxuSingle.c,v 1.0 2003/02/01 00:00:00 alanmi Exp

]

Function*************************************************************

Synopsis [Adds the single-cube divisors associated with a new column.]

Description []

SideEffects []

SeeAlso []

Definition at line 124 of file fxuSingle.c.

{
    Fxu_Lit * pLitV, * pLitH;
    Fxu_Var * pVar2;
    int Coin;
    int WeightCur;

    // start collecting the affected vars
    Fxu_MatrixRingVarsStart( p );
    // go through all the literals of this variable
    for ( pLitV = pVar->lLits.pHead; pLitV; pLitV = pLitV->pVNext )
        // for this literal, go through all the horizontal literals
        for ( pLitH = pLitV->pHPrev; pLitH; pLitH = pLitH->pHPrev )
        {
            // get another variable
            pVar2 = pLitH->pVar;
            // skip the var if it is already used
            if ( pVar2->pOrder )
                continue;
            // skip the var if it belongs to the same node
//            if ( pValue2Node[pVar->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 )
    {
        // count the coincidence
        Coin = Fxu_SingleCountCoincidence( p, pVar2, pVar );
        assert( Coin > 0 );
        // get the new weight
        WeightCur = Coin - 2;
        // peformance fix (August 24, 2007)
        if ( WeightCur >= p->nWeightLimit )
        {
            Vec_PtrPush( vSingles, pVar2 );
            Vec_PtrPush( vSingles, pVar );
            Vec_PtrPush( vSingles, (void *)(ABC_PTRUINT_T)WeightCur );
        }
    }

    // unmark the vars
    Fxu_MatrixRingVarsUnmark( p );
}

int Fxu_SingleCountCoincidence	(	Fxu_Matrix *	p,
		Fxu_Var *	pVar1,
		Fxu_Var *	pVar2
	)

Function*************************************************************

Synopsis [Computes the coincidence count of two columns.]

Description []

SideEffects []

SeeAlso []

Definition at line 241 of file fxuSingle.c.

{
    Fxu_Lit * pLit1, * pLit2;
    int Result;

    // compute the coincidence count
    Result = 0;
    pLit1  = pVar1->lLits.pHead;
    pLit2  = pVar2->lLits.pHead;
    while ( 1 )
    {
        if ( pLit1 && pLit2 )
        {
            if ( pLit1->pCube->pVar->iVar == pLit2->pCube->pVar->iVar )
            { // the variables are the same
                if ( pLit1->iCube == pLit2->iCube )
                { // the literals are the same
                    pLit1 = pLit1->pVNext;
                    pLit2 = pLit2->pVNext;
                    // add this literal to the coincidence
                    Result++;
                }
                else if ( pLit1->iCube < pLit2->iCube )
                    pLit1 = pLit1->pVNext;
                else
                    pLit2 = pLit2->pVNext;
            }
            else if ( pLit1->pCube->pVar->iVar < pLit2->pCube->pVar->iVar )
                pLit1 = pLit1->pVNext;
            else
                pLit2 = pLit2->pVNext;
        }
        else if ( pLit1 && !pLit2 )
            pLit1 = pLit1->pVNext;
        else if ( !pLit1 && pLit2 )
            pLit2 = pLit2->pVNext;
        else
            break;
    }
    return Result;
}