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