/**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