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