/**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 $]
***********************************************************************/
#include "fxuInt.h"
#include "misc/vec/vec.h"
ABC_NAMESPACE_IMPL_START
////////////////////////////////////////////////////////////////////////
/// DECLARATIONS ///
////////////////////////////////////////////////////////////////////////
static void Fxu_MatrixComputeSinglesOneCollect( Fxu_Matrix * p, Fxu_Var * pVar, Vec_Ptr_t * vSingles );
////////////////////////////////////////////////////////////////////////
/// 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 []
***********************************************************************/
void Fxu_MatrixComputeSingles( Fxu_Matrix * p, int fUse0, int nSingleMax )
{
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 );
}
/**Function*************************************************************
Synopsis [Adds the single-cube divisors associated with a new column.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Fxu_MatrixComputeSinglesOneCollect( Fxu_Matrix * p, Fxu_Var * pVar, Vec_Ptr_t * vSingles )
{
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 );
}
/**Function*************************************************************
Synopsis [Adds the single-cube divisors associated with a new column.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
void Fxu_MatrixComputeSinglesOne( Fxu_Matrix * p, Fxu_Var * pVar )
{
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 );
}
/**Function*************************************************************
Synopsis [Computes the coincidence count of two columns.]
Description []
SideEffects []
SeeAlso []
***********************************************************************/
int Fxu_SingleCountCoincidence( Fxu_Matrix * p, Fxu_Var * pVar1, Fxu_Var * pVar2 )
{
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;
}
////////////////////////////////////////////////////////////////////////
/// END OF FILE ///
////////////////////////////////////////////////////////////////////////
ABC_NAMESPACE_IMPL_END