| /**CFile**************************************************************** | |
| FileName [cutMerge.c] | |
| SystemName [ABC: Logic synthesis and verification system.] | |
| PackageName [K-feasible cut computation package.] | |
| Synopsis [Procedure to merge two cuts.] | |
| Author [Alan Mishchenko] | |
| Affiliation [UC Berkeley] | |
| Date [Ver. 1.0. Started - June 20, 2005.] | |
| Revision [$Id: cutMerge.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] | |
| ***********************************************************************/ | |
| #include "cutInt.h" | |
| ABC_NAMESPACE_IMPL_START | |
| //////////////////////////////////////////////////////////////////////// | |
| /// DECLARATIONS /// | |
| //////////////////////////////////////////////////////////////////////// | |
| //////////////////////////////////////////////////////////////////////// | |
| /// FUNCTION DEFINITIONS /// | |
| //////////////////////////////////////////////////////////////////////// | |
| /**Function************************************************************* | |
| Synopsis [Merges two cuts.] | |
| Description [This procedure works.] | |
| SideEffects [] | |
| SeeAlso [] | |
| ***********************************************************************/ | |
| Cut_Cut_t * Cut_CutMergeTwo2( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ) | |
| { | |
| static int M[7][3] = {{0},{0},{0},{0},{0},{0},{0}}; | |
| Cut_Cut_t * pRes; | |
| int * pRow; | |
| int nLeaves0, nLeaves1, Limit; | |
| int i, k, Count, nNodes; | |
| assert( pCut0->nLeaves >= pCut1->nLeaves ); | |
| // the case of the largest cut sizes | |
| Limit = p->pParams->nVarsMax; | |
| nLeaves0 = pCut0->nLeaves; | |
| nLeaves1 = pCut1->nLeaves; | |
| if ( nLeaves0 == Limit && nLeaves1 == Limit ) | |
| { | |
| for ( i = 0; i < nLeaves0; i++ ) | |
| if ( pCut0->pLeaves[i] != pCut1->pLeaves[i] ) | |
| return NULL; | |
| pRes = Cut_CutAlloc( p ); | |
| for ( i = 0; i < nLeaves0; i++ ) | |
| pRes->pLeaves[i] = pCut0->pLeaves[i]; | |
| pRes->nLeaves = nLeaves0; | |
| return pRes; | |
| } | |
| // the case when one of the cuts is the largest | |
| if ( nLeaves0 == Limit ) | |
| { | |
| for ( i = 0; i < nLeaves1; i++ ) | |
| { | |
| for ( k = nLeaves0 - 1; k >= 0; k-- ) | |
| if ( pCut0->pLeaves[k] == pCut1->pLeaves[i] ) | |
| break; | |
| if ( k == -1 ) // did not find | |
| return NULL; | |
| } | |
| pRes = Cut_CutAlloc( p ); | |
| for ( i = 0; i < nLeaves0; i++ ) | |
| pRes->pLeaves[i] = pCut0->pLeaves[i]; | |
| pRes->nLeaves = nLeaves0; | |
| return pRes; | |
| } | |
| // other cases | |
| nNodes = nLeaves0; | |
| for ( i = 0; i < nLeaves1; i++ ) | |
| { | |
| for ( k = nLeaves0 - 1; k >= 0; k-- ) | |
| { | |
| if ( pCut0->pLeaves[k] > pCut1->pLeaves[i] ) | |
| continue; | |
| if ( pCut0->pLeaves[k] < pCut1->pLeaves[i] ) | |
| { | |
| pRow = M[k+1]; | |
| if ( pRow[0] == 0 ) | |
| pRow[0] = pCut1->pLeaves[i], pRow[1] = 0; | |
| else if ( pRow[1] == 0 ) | |
| pRow[1] = pCut1->pLeaves[i], pRow[2] = 0; | |
| else if ( pRow[2] == 0 ) | |
| pRow[2] = pCut1->pLeaves[i]; | |
| else | |
| assert( 0 ); | |
| if ( ++nNodes > Limit ) | |
| { | |
| for ( i = 0; i <= nLeaves0; i++ ) | |
| M[i][0] = 0; | |
| return NULL; | |
| } | |
| } | |
| break; | |
| } | |
| if ( k == -1 ) | |
| { | |
| pRow = M[0]; | |
| if ( pRow[0] == 0 ) | |
| pRow[0] = pCut1->pLeaves[i], pRow[1] = 0; | |
| else if ( pRow[1] == 0 ) | |
| pRow[1] = pCut1->pLeaves[i], pRow[2] = 0; | |
| else if ( pRow[2] == 0 ) | |
| pRow[2] = pCut1->pLeaves[i]; | |
| else | |
| assert( 0 ); | |
| if ( ++nNodes > Limit ) | |
| { | |
| for ( i = 0; i <= nLeaves0; i++ ) | |
| M[i][0] = 0; | |
| return NULL; | |
| } | |
| continue; | |
| } | |
| } | |
| pRes = Cut_CutAlloc( p ); | |
| for ( Count = 0, i = 0; i <= nLeaves0; i++ ) | |
| { | |
| if ( i > 0 ) | |
| pRes->pLeaves[Count++] = pCut0->pLeaves[i-1]; | |
| pRow = M[i]; | |
| if ( pRow[0] ) | |
| { | |
| pRes->pLeaves[Count++] = pRow[0]; | |
| if ( pRow[1] ) | |
| { | |
| pRes->pLeaves[Count++] = pRow[1]; | |
| if ( pRow[2] ) | |
| pRes->pLeaves[Count++] = pRow[2]; | |
| } | |
| pRow[0] = 0; | |
| } | |
| } | |
| assert( Count == nNodes ); | |
| pRes->nLeaves = nNodes; | |
| return pRes; | |
| } | |
| /**Function************************************************************* | |
| Synopsis [Merges two cuts.] | |
| Description [] | |
| SideEffects [] | |
| SeeAlso [] | |
| ***********************************************************************/ | |
| Cut_Cut_t * Cut_CutMergeTwo( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ) | |
| { | |
| Cut_Cut_t * pRes; | |
| int * pLeaves; | |
| int Limit, nLeaves0, nLeaves1; | |
| int i, k, c; | |
| assert( pCut0->nLeaves >= pCut1->nLeaves ); | |
| // consider two cuts | |
| nLeaves0 = pCut0->nLeaves; | |
| nLeaves1 = pCut1->nLeaves; | |
| // the case of the largest cut sizes | |
| Limit = p->pParams->nVarsMax; | |
| if ( nLeaves0 == Limit && nLeaves1 == Limit ) | |
| { | |
| for ( i = 0; i < nLeaves0; i++ ) | |
| if ( pCut0->pLeaves[i] != pCut1->pLeaves[i] ) | |
| return NULL; | |
| pRes = Cut_CutAlloc( p ); | |
| for ( i = 0; i < nLeaves0; i++ ) | |
| pRes->pLeaves[i] = pCut0->pLeaves[i]; | |
| pRes->nLeaves = pCut0->nLeaves; | |
| return pRes; | |
| } | |
| // the case when one of the cuts is the largest | |
| if ( nLeaves0 == Limit ) | |
| { | |
| for ( i = 0; i < nLeaves1; i++ ) | |
| { | |
| for ( k = nLeaves0 - 1; k >= 0; k-- ) | |
| if ( pCut0->pLeaves[k] == pCut1->pLeaves[i] ) | |
| break; | |
| if ( k == -1 ) // did not find | |
| return NULL; | |
| } | |
| pRes = Cut_CutAlloc( p ); | |
| for ( i = 0; i < nLeaves0; i++ ) | |
| pRes->pLeaves[i] = pCut0->pLeaves[i]; | |
| pRes->nLeaves = pCut0->nLeaves; | |
| return pRes; | |
| } | |
| // prepare the cut | |
| if ( p->pReady == NULL ) | |
| p->pReady = Cut_CutAlloc( p ); | |
| pLeaves = p->pReady->pLeaves; | |
| // compare two cuts with different numbers | |
| i = k = 0; | |
| for ( c = 0; c < Limit; c++ ) | |
| { | |
| if ( k == nLeaves1 ) | |
| { | |
| if ( i == nLeaves0 ) | |
| { | |
| p->pReady->nLeaves = c; | |
| pRes = p->pReady; p->pReady = NULL; | |
| return pRes; | |
| } | |
| pLeaves[c] = pCut0->pLeaves[i++]; | |
| continue; | |
| } | |
| if ( i == nLeaves0 ) | |
| { | |
| if ( k == nLeaves1 ) | |
| { | |
| p->pReady->nLeaves = c; | |
| pRes = p->pReady; p->pReady = NULL; | |
| return pRes; | |
| } | |
| pLeaves[c] = pCut1->pLeaves[k++]; | |
| continue; | |
| } | |
| if ( pCut0->pLeaves[i] < pCut1->pLeaves[k] ) | |
| { | |
| pLeaves[c] = pCut0->pLeaves[i++]; | |
| continue; | |
| } | |
| if ( pCut0->pLeaves[i] > pCut1->pLeaves[k] ) | |
| { | |
| pLeaves[c] = pCut1->pLeaves[k++]; | |
| continue; | |
| } | |
| pLeaves[c] = pCut0->pLeaves[i++]; | |
| k++; | |
| } | |
| if ( i < nLeaves0 || k < nLeaves1 ) | |
| return NULL; | |
| p->pReady->nLeaves = c; | |
| pRes = p->pReady; p->pReady = NULL; | |
| return pRes; | |
| } | |
| /**Function************************************************************* | |
| Synopsis [Merges two cuts.] | |
| Description [] | |
| SideEffects [] | |
| SeeAlso [] | |
| ***********************************************************************/ | |
| Cut_Cut_t * Cut_CutMergeTwo3( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ) | |
| { | |
| Cut_Cut_t * pRes; | |
| int * pLeaves; | |
| int Limit, nLeaves0, nLeaves1; | |
| int i, k, c; | |
| assert( pCut0->nLeaves >= pCut1->nLeaves ); | |
| // prepare the cut | |
| if ( p->pReady == NULL ) | |
| p->pReady = Cut_CutAlloc( p ); | |
| pLeaves = p->pReady->pLeaves; | |
| // consider two cuts | |
| Limit = p->pParams->nVarsMax; | |
| nLeaves0 = pCut0->nLeaves; | |
| nLeaves1 = pCut1->nLeaves; | |
| if ( nLeaves0 == Limit ) | |
| { // the case when one of the cuts is the largest | |
| if ( nLeaves1 == Limit ) | |
| { // the case when both cuts are the largest | |
| for ( i = 0; i < nLeaves0; i++ ) | |
| { | |
| pLeaves[i] = pCut0->pLeaves[i]; | |
| if ( pLeaves[i] != pCut1->pLeaves[i] ) | |
| return NULL; | |
| } | |
| } | |
| else | |
| { | |
| for ( i = k = 0; i < nLeaves0; i++ ) | |
| { | |
| pLeaves[i] = pCut0->pLeaves[i]; | |
| if ( k == (int)nLeaves1 ) | |
| continue; | |
| if ( pLeaves[i] < pCut1->pLeaves[k] ) | |
| continue; | |
| if ( pLeaves[i] == pCut1->pLeaves[k++] ) | |
| continue; | |
| return NULL; | |
| } | |
| if ( k < nLeaves1 ) | |
| return NULL; | |
| } | |
| p->pReady->nLeaves = nLeaves0; | |
| pRes = p->pReady; p->pReady = NULL; | |
| return pRes; | |
| } | |
| // compare two cuts with different numbers | |
| i = k = 0; | |
| for ( c = 0; c < Limit; c++ ) | |
| { | |
| if ( k == nLeaves1 ) | |
| { | |
| if ( i == nLeaves0 ) | |
| { | |
| p->pReady->nLeaves = c; | |
| pRes = p->pReady; p->pReady = NULL; | |
| return pRes; | |
| } | |
| pLeaves[c] = pCut0->pLeaves[i++]; | |
| continue; | |
| } | |
| if ( i == nLeaves0 ) | |
| { | |
| if ( k == nLeaves1 ) | |
| { | |
| p->pReady->nLeaves = c; | |
| pRes = p->pReady; p->pReady = NULL; | |
| return pRes; | |
| } | |
| pLeaves[c] = pCut1->pLeaves[k++]; | |
| continue; | |
| } | |
| if ( pCut0->pLeaves[i] < pCut1->pLeaves[k] ) | |
| { | |
| pLeaves[c] = pCut0->pLeaves[i++]; | |
| continue; | |
| } | |
| if ( pCut0->pLeaves[i] > pCut1->pLeaves[k] ) | |
| { | |
| pLeaves[c] = pCut1->pLeaves[k++]; | |
| continue; | |
| } | |
| pLeaves[c] = pCut0->pLeaves[i++]; | |
| k++; | |
| } | |
| if ( i < nLeaves0 || k < nLeaves1 ) | |
| return NULL; | |
| p->pReady->nLeaves = c; | |
| pRes = p->pReady; p->pReady = NULL; | |
| return pRes; | |
| } | |
| /**Function************************************************************* | |
| Synopsis [Merges two cuts.] | |
| Description [] | |
| SideEffects [] | |
| SeeAlso [] | |
| ***********************************************************************/ | |
| Cut_Cut_t * Cut_CutMergeTwo4( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ) | |
| { | |
| Cut_Cut_t * pRes; | |
| int * pLeaves; | |
| int i, k, min, NodeTemp, Limit, nTotal; | |
| assert( pCut0->nLeaves >= pCut1->nLeaves ); | |
| // prepare the cut | |
| if ( p->pReady == NULL ) | |
| p->pReady = Cut_CutAlloc( p ); | |
| pLeaves = p->pReady->pLeaves; | |
| // consider two cuts | |
| Limit = p->pParams->nVarsMax; | |
| if ( pCut0->nLeaves == (unsigned)Limit ) | |
| { // the case when one of the cuts is the largest | |
| if ( pCut1->nLeaves == (unsigned)Limit ) | |
| { // the case when both cuts are the largest | |
| for ( i = 0; i < (int)pCut0->nLeaves; i++ ) | |
| { | |
| pLeaves[i] = pCut0->pLeaves[i]; | |
| if ( pLeaves[i] != pCut1->pLeaves[i] ) | |
| return NULL; | |
| } | |
| } | |
| else | |
| { | |
| for ( i = k = 0; i < (int)pCut0->nLeaves; i++ ) | |
| { | |
| pLeaves[i] = pCut0->pLeaves[i]; | |
| if ( k == (int)pCut1->nLeaves ) | |
| continue; | |
| if ( pLeaves[i] < pCut1->pLeaves[k] ) | |
| continue; | |
| if ( pLeaves[i] == pCut1->pLeaves[k++] ) | |
| continue; | |
| return NULL; | |
| } | |
| if ( k < (int)pCut1->nLeaves ) | |
| return NULL; | |
| } | |
| p->pReady->nLeaves = pCut0->nLeaves; | |
| pRes = p->pReady; p->pReady = NULL; | |
| return pRes; | |
| } | |
| // count the number of unique entries in pCut1 | |
| nTotal = pCut0->nLeaves; | |
| for ( i = 0; i < (int)pCut1->nLeaves; i++ ) | |
| { | |
| // try to find this entry among the leaves of pCut0 | |
| for ( k = 0; k < (int)pCut0->nLeaves; k++ ) | |
| if ( pCut1->pLeaves[i] == pCut0->pLeaves[k] ) | |
| break; | |
| if ( k < (int)pCut0->nLeaves ) // found | |
| continue; | |
| // we found a new entry to add | |
| if ( nTotal == Limit ) | |
| return NULL; | |
| pLeaves[nTotal++] = pCut1->pLeaves[i]; | |
| } | |
| // we know that the feasible cut exists | |
| // add the starting entries | |
| for ( k = 0; k < (int)pCut0->nLeaves; k++ ) | |
| pLeaves[k] = pCut0->pLeaves[k]; | |
| // selection-sort the entries | |
| for ( i = 0; i < nTotal - 1; i++ ) | |
| { | |
| min = i; | |
| for ( k = i+1; k < nTotal; k++ ) | |
| if ( pLeaves[k] < pLeaves[min] ) | |
| min = k; | |
| NodeTemp = pLeaves[i]; | |
| pLeaves[i] = pLeaves[min]; | |
| pLeaves[min] = NodeTemp; | |
| } | |
| p->pReady->nLeaves = nTotal; | |
| pRes = p->pReady; p->pReady = NULL; | |
| return pRes; | |
| } | |
| /**Function************************************************************* | |
| Synopsis [Merges two cuts.] | |
| Description [This procedure works.] | |
| SideEffects [] | |
| SeeAlso [] | |
| ***********************************************************************/ | |
| Cut_Cut_t * Cut_CutMergeTwo5( Cut_Man_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 ) | |
| { | |
| static int M[7][3] = {{0},{0},{0},{0},{0},{0},{0}}; | |
| Cut_Cut_t * pRes; | |
| int * pRow; | |
| unsigned uSign0, uSign1; | |
| int i, k, nNodes, Count; | |
| unsigned Limit = p->pParams->nVarsMax; | |
| assert( pCut0->nLeaves >= pCut1->nLeaves ); | |
| // the case of the largest cut sizes | |
| if ( pCut0->nLeaves == Limit && pCut1->nLeaves == Limit ) | |
| { | |
| for ( i = 0; i < (int)pCut0->nLeaves; i++ ) | |
| if ( pCut0->pLeaves[i] != pCut1->pLeaves[i] ) | |
| return NULL; | |
| pRes = Cut_CutAlloc( p ); | |
| for ( i = 0; i < (int)pCut0->nLeaves; i++ ) | |
| pRes->pLeaves[i] = pCut0->pLeaves[i]; | |
| pRes->nLeaves = pCut0->nLeaves; | |
| return pRes; | |
| } | |
| // the case when one of the cuts is the largest | |
| if ( pCut0->nLeaves == Limit ) | |
| { | |
| if ( !p->pParams->fTruth ) | |
| { | |
| for ( i = 0; i < (int)pCut1->nLeaves; i++ ) | |
| { | |
| for ( k = pCut0->nLeaves - 1; k >= 0; k-- ) | |
| if ( pCut0->pLeaves[k] == pCut1->pLeaves[i] ) | |
| break; | |
| if ( k == -1 ) // did not find | |
| return NULL; | |
| } | |
| pRes = Cut_CutAlloc( p ); | |
| } | |
| else | |
| { | |
| uSign1 = 0; | |
| for ( i = 0; i < (int)pCut1->nLeaves; i++ ) | |
| { | |
| for ( k = pCut0->nLeaves - 1; k >= 0; k-- ) | |
| if ( pCut0->pLeaves[k] == pCut1->pLeaves[i] ) | |
| { | |
| uSign1 |= (1 << i); | |
| break; | |
| } | |
| if ( k == -1 ) // did not find | |
| return NULL; | |
| } | |
| pRes = Cut_CutAlloc( p ); | |
| pRes->Num1 = uSign1; | |
| } | |
| for ( i = 0; i < (int)pCut0->nLeaves; i++ ) | |
| pRes->pLeaves[i] = pCut0->pLeaves[i]; | |
| pRes->nLeaves = pCut0->nLeaves; | |
| return pRes; | |
| } | |
| // other cases | |
| nNodes = pCut0->nLeaves; | |
| for ( i = 0; i < (int)pCut1->nLeaves; i++ ) | |
| { | |
| for ( k = pCut0->nLeaves - 1; k >= 0; k-- ) | |
| { | |
| if ( pCut0->pLeaves[k] > pCut1->pLeaves[i] ) | |
| continue; | |
| if ( pCut0->pLeaves[k] < pCut1->pLeaves[i] ) | |
| { | |
| pRow = M[k+1]; | |
| if ( pRow[0] == 0 ) | |
| pRow[0] = pCut1->pLeaves[i], pRow[1] = 0; | |
| else if ( pRow[1] == 0 ) | |
| pRow[1] = pCut1->pLeaves[i], pRow[2] = 0; | |
| else if ( pRow[2] == 0 ) | |
| pRow[2] = pCut1->pLeaves[i]; | |
| else | |
| assert( 0 ); | |
| if ( ++nNodes > (int)Limit ) | |
| { | |
| for ( i = 0; i <= (int)pCut0->nLeaves; i++ ) | |
| M[i][0] = 0; | |
| return NULL; | |
| } | |
| } | |
| break; | |
| } | |
| if ( k == -1 ) | |
| { | |
| pRow = M[0]; | |
| if ( pRow[0] == 0 ) | |
| pRow[0] = pCut1->pLeaves[i], pRow[1] = 0; | |
| else if ( pRow[1] == 0 ) | |
| pRow[1] = pCut1->pLeaves[i], pRow[2] = 0; | |
| else if ( pRow[2] == 0 ) | |
| pRow[2] = pCut1->pLeaves[i]; | |
| else | |
| assert( 0 ); | |
| if ( ++nNodes > (int)Limit ) | |
| { | |
| for ( i = 0; i <= (int)pCut0->nLeaves; i++ ) | |
| M[i][0] = 0; | |
| return NULL; | |
| } | |
| continue; | |
| } | |
| } | |
| pRes = Cut_CutAlloc( p ); | |
| if ( !p->pParams->fTruth ) | |
| { | |
| for ( Count = 0, i = 0; i <= (int)pCut0->nLeaves; i++ ) | |
| { | |
| if ( i > 0 ) | |
| pRes->pLeaves[Count++] = pCut0->pLeaves[i-1]; | |
| pRow = M[i]; | |
| if ( pRow[0] ) | |
| { | |
| pRes->pLeaves[Count++] = pRow[0]; | |
| if ( pRow[1] ) | |
| { | |
| pRes->pLeaves[Count++] = pRow[1]; | |
| if ( pRow[2] ) | |
| pRes->pLeaves[Count++] = pRow[2]; | |
| } | |
| pRow[0] = 0; | |
| } | |
| } | |
| assert( Count == nNodes ); | |
| pRes->nLeaves = nNodes; | |
| /* | |
| // make sure that the cut is correct | |
| { | |
| for ( i = 1; i < (int)pRes->nLeaves; i++ ) | |
| if ( pRes->pLeaves[i-1] >= pRes->pLeaves[i] ) | |
| { | |
| int v = 0; | |
| } | |
| } | |
| */ | |
| return pRes; | |
| } | |
| uSign0 = uSign1 = 0; | |
| for ( Count = 0, i = 0; i <= (int)pCut0->nLeaves; i++ ) | |
| { | |
| if ( i > 0 ) | |
| { | |
| uSign0 |= (1 << Count); | |
| pRes->pLeaves[Count++] = pCut1->pLeaves[i-1]; | |
| } | |
| pRow = M[i]; | |
| if ( pRow[0] ) | |
| { | |
| uSign1 |= (1 << Count); | |
| pRes->pLeaves[Count++] = pRow[0]; | |
| if ( pRow[1] ) | |
| { | |
| uSign1 |= (1 << Count); | |
| pRes->pLeaves[Count++] = pRow[1]; | |
| if ( pRow[2] ) | |
| { | |
| uSign1 |= (1 << Count); | |
| pRes->pLeaves[Count++] = pRow[2]; | |
| } | |
| } | |
| pRow[0] = 0; | |
| } | |
| } | |
| assert( Count == nNodes ); | |
| pRes->nLeaves = nNodes; | |
| pRes->Num1 = uSign1; | |
| pRes->Num0 = uSign0; | |
| return pRes; | |
| } | |
| //////////////////////////////////////////////////////////////////////// | |
| /// END OF FILE /// | |
| //////////////////////////////////////////////////////////////////////// | |
| ABC_NAMESPACE_IMPL_END | |