diff options
Diffstat (limited to 'src/opt/xyz/xyzMinSop.c')
| -rw-r--r-- | src/opt/xyz/xyzMinSop.c | 346 |
1 files changed, 310 insertions, 36 deletions
diff --git a/src/opt/xyz/xyzMinSop.c b/src/opt/xyz/xyzMinSop.c index 1c5951fe..a5d57c66 100644 --- a/src/opt/xyz/xyzMinSop.c +++ b/src/opt/xyz/xyzMinSop.c @@ -52,10 +52,11 @@ void Min_SopMinimize( Min_Man_t * p ) nCubesOld = p->nCubes; Min_SopRewrite( p ); nIter++; +// printf( "%d:%d->%d ", nIter, nCubesInit, p->nCubes ); } while ( 100.0*(nCubesOld - p->nCubes)/nCubesOld > 3.0 ); +// printf( "\n" ); -// printf( "%d:%d->%d ", nIter, nCubesInit, p->nCubes ); } /**Function************************************************************* @@ -74,8 +75,17 @@ void Min_SopRewrite( Min_Man_t * p ) Min_Cube_t * pCube, ** ppPrev; Min_Cube_t * pThis, ** ppPrevT; Min_Cube_t * pTemp; - int v00, v01, v10, v11, Var0, Var1, Index; + int v00, v01, v10, v11, Var0, Var1, Index, fCont0, fCont1, nCubesOld; int nPairs = 0; +/* + { + Min_Cube_t * pCover; + pCover = Min_CoverCollect( p, p->nVars ); +printf( "\n\n" ); +Min_CoverWrite( stdout, pCover ); + Min_CoverExpand( p, pCover ); + } +*/ // insert the bubble before the first cube p->pBubble->pNext = p->ppStore[0]; @@ -127,7 +137,11 @@ void Min_SopRewrite( Min_Man_t * p ) continue; } nPairs++; - +/* +printf( "\n" ); +Min_CubeWrite( stdout, pCube ); +Min_CubeWrite( stdout, pThis ); +*/ // remove the cubes, insert the bubble instead of pCube *ppPrevT = pThis->pNext; *ppPrev = p->pBubble; @@ -135,6 +149,8 @@ void Min_SopRewrite( Min_Man_t * p ) p->pBubble->nLits = pCube->nLits; p->nCubes -= 2; + assert( pCube != p->pBubble && pThis != p->pBubble ); + // save the dist2 parameters v00 = Min_CubeGetVar( pCube, Var0 ); @@ -145,22 +161,83 @@ void Min_SopRewrite( Min_Man_t * p ) assert( v00 != 3 || v01 != 3 ); assert( v10 != 3 || v11 != 3 ); - // skip the case when rewriting is impossible +//printf( "\n" ); +//Min_CubeWrite( stdout, pCube ); +//Min_CubeWrite( stdout, pThis ); + +//printf( "\n" ); +//Min_CubeWrite( stdout, pCube ); +//Min_CubeWrite( stdout, pThis ); + + // consider the case when both cubes have non-empty literals if ( v00 != 3 && v01 != 3 && v10 != 3 && v11 != 3 ) + { + assert( v00 == (v10 ^ 3) ); + assert( v01 == (v11 ^ 3) ); + // create the temporary cube equal to the first corner + Min_CubeXorVar( pCube, Var0, 3 ); + // check if this cube is contained + fCont0 = Min_CoverContainsCube( p, pCube ); + // create the temporary cube equal to the first corner + Min_CubeXorVar( pCube, Var0, 3 ); + Min_CubeXorVar( pCube, Var1, 3 ); +//printf( "\n" ); +//Min_CubeWrite( stdout, pCube ); +//Min_CubeWrite( stdout, pThis ); + // check if this cube is contained + fCont1 = Min_CoverContainsCube( p, pCube ); + // undo the change + Min_CubeXorVar( pCube, Var1, 3 ); + + // check if the cubes can be overwritten + if ( fCont0 && fCont1 ) + { + // one of the cubes can be recycled, the other expanded and added + Min_CubeRecycle( p, pThis ); + // remove the literals + Min_CubeXorVar( pCube, Var0, v00 ^ 3 ); + Min_CubeXorVar( pCube, Var1, v01 ^ 3 ); + pCube->nLits -= 2; + Min_SopAddCube( p, pCube ); + } + else if ( fCont0 ) + { + // expand both cubes and add them + Min_CubeXorVar( pCube, Var0, v00 ^ 3 ); + pCube->nLits--; + Min_SopAddCube( p, pCube ); + Min_CubeXorVar( pThis, Var1, v11 ^ 3 ); + pThis->nLits--; + Min_SopAddCube( p, pThis ); + } + else if ( fCont1 ) + { + // expand both cubes and add them + Min_CubeXorVar( pCube, Var1, v01 ^ 3 ); + pCube->nLits--; + Min_SopAddCube( p, pCube ); + Min_CubeXorVar( pThis, Var0, v10 ^ 3 ); + pThis->nLits--; + Min_SopAddCube( p, pThis ); + } + else + { + Min_SopAddCube( p, pCube ); + Min_SopAddCube( p, pThis ); + } + // otherwise, no change is possible continue; + } // if one of them does not have DC lit, move it if ( v00 != 3 && v01 != 3 ) { + assert( v10 == 3 || v11 == 3 ); pTemp = pCube; pCube = pThis; pThis = pTemp; Index = v00; v00 = v10; v10 = Index; Index = v01; v01 = v11; v11 = Index; } -//printf( "\n" ); -//Min_CubeWrite( stdout, pCube ); -//Min_CubeWrite( stdout, pThis ); - // make sure the first cube has first var DC if ( v00 != 3 ) { @@ -174,13 +251,93 @@ void Min_SopRewrite( Min_Man_t * p ) if ( v00 == 3 && v11 == 3 ) { assert( v01 != 3 && v10 != 3 ); - // try two reduced cubes - + // try the remaining minterm + // create the temporary cube equal to the first corner + Min_CubeXorVar( pCube, Var0, v10 ); + Min_CubeXorVar( pCube, Var1, 3 ); + pCube->nLits++; + // check if this cube is contained + fCont0 = Min_CoverContainsCube( p, pCube ); + // undo the cube transformations + Min_CubeXorVar( pCube, Var0, v10 ); + Min_CubeXorVar( pCube, Var1, 3 ); + pCube->nLits--; + // check the case when both are covered + if ( fCont0 ) + { + // one of the cubes can be recycled, the other expanded and added + Min_CubeRecycle( p, pThis ); + // remove the literals + Min_CubeXorVar( pCube, Var1, v01 ^ 3 ); + pCube->nLits--; + Min_SopAddCube( p, pCube ); + } + else + { + // try two reduced cubes + Min_CubeXorVar( pCube, Var0, v10 ); + pCube->nLits++; + // remember the cubes + nCubesOld = p->nCubes; + Min_SopAddCube( p, pCube ); + // check if the cube is absorbed + if ( p->nCubes < nCubesOld + 1 ) + { // absorbed - add the second cube + Min_SopAddCube( p, pThis ); + } + else + { // remove this cube, and try another one + assert( pCube == p->ppStore[pCube->nLits] ); + p->ppStore[pCube->nLits] = pCube->pNext; + p->nCubes--; + + // return the cube to the previous state + Min_CubeXorVar( pCube, Var0, v10 ); + pCube->nLits--; + + // generate another reduced cube + Min_CubeXorVar( pThis, Var1, v01 ); + pThis->nLits++; + + // add both cubes + Min_SopAddCube( p, pCube ); + Min_SopAddCube( p, pThis ); + } + } } else // the first cube has DC lit { assert( v01 != 3 && v10 != 3 && v11 != 3 ); - // try reduced and expanded cube + // try the remaining minterm + // create the temporary cube equal to the minterm + Min_CubeXorVar( pThis, Var0, 3 ); + // check if this cube is contained + fCont0 = Min_CoverContainsCube( p, pThis ); + // undo the cube transformations + Min_CubeXorVar( pThis, Var0, 3 ); + // check the case when both are covered + if ( fCont0 ) + { + // one of the cubes can be recycled, the other expanded and added + Min_CubeRecycle( p, pThis ); + // remove the literals + Min_CubeXorVar( pCube, Var1, v01 ^ 3 ); + pCube->nLits--; + Min_SopAddCube( p, pCube ); + } + else + { + // try reshaping the cubes + // reduce the first cube + Min_CubeXorVar( pCube, Var0, v10 ); + pCube->nLits++; + // expand the second cube + Min_CubeXorVar( pThis, Var1, v11 ^ 3 ); + pThis->nLits--; + // add both cubes + Min_SopAddCube( p, pCube ); + Min_SopAddCube( p, pThis ); + } } } // printf( "Pairs = %d ", nPairs ); @@ -188,26 +345,80 @@ void Min_SopRewrite( Min_Man_t * p ) /**Function************************************************************* - Synopsis [] + Synopsis [Adds cube to the SOP cover stored in the manager.] - Description [] + Description [Returns 0 if the cube is added or removed. Returns 1 + if the cube is glued with some other cube and has to be added again.] SideEffects [] SeeAlso [] ***********************************************************************/ -int Min_SopAddCube( Min_Man_t * p, Min_Cube_t * pCube ) +int Min_SopAddCubeInt( Min_Man_t * p, Min_Cube_t * pCube ) { - return 1; -} - + Min_Cube_t * pThis, * pThis2, ** ppPrev; + int i; + // try to find the identical cube + Min_CoverForEachCube( p->ppStore[pCube->nLits], pThis ) + { + if ( Min_CubesAreEqual( pCube, pThis ) ) + { + Min_CubeRecycle( p, pCube ); + return 0; + } + } + // try to find a containing cube + for ( i = 0; i < (int)pCube->nLits; i++ ) + Min_CoverForEachCube( p->ppStore[i], pThis ) + { + if ( pThis != p->pBubble && Min_CubeIsContained( pThis, pCube ) ) + { + Min_CubeRecycle( p, pCube ); + return 0; + } + } + // try to find distance one in the same bin + Min_CoverForEachCubePrev( p->ppStore[pCube->nLits], pThis, ppPrev ) + { + if ( Min_CubesDistOne( pCube, pThis, NULL ) ) + { + *ppPrev = pThis->pNext; + Min_CubesTransformOr( pCube, pThis ); + pCube->nLits--; + Min_CubeRecycle( p, pThis ); + p->nCubes--; + return 1; + } + } + // clean the other cubes using this one + for ( i = pCube->nLits + 1; i <= (int)pCube->nVars; i++ ) + { + ppPrev = &p->ppStore[i]; + Min_CoverForEachCubeSafe( p->ppStore[i], pThis, pThis2 ) + { + if ( pThis != p->pBubble && Min_CubeIsContained( pCube, pThis ) ) + { + *ppPrev = pThis->pNext; + Min_CubeRecycle( p, pThis ); + p->nCubes--; + } + else + ppPrev = &pThis->pNext; + } + } + // add the cube + pCube->pNext = p->ppStore[pCube->nLits]; + p->ppStore[pCube->nLits] = pCube; + p->nCubes++; + return 0; +} /**Function************************************************************* - Synopsis [] + Synopsis [Adds the cube to storage.] Description [] @@ -216,27 +427,18 @@ int Min_SopAddCube( Min_Man_t * p, Min_Cube_t * pCube ) SeeAlso [] ***********************************************************************/ -void Min_SopDist1Merge( Min_Man_t * p ) +void Min_SopAddCube( Min_Man_t * p, Min_Cube_t * pCube ) { - Min_Cube_t * pCube, * pCube2, * pCubeNew; - int i; - for ( i = p->nVars; i >= 0; i-- ) - { - Min_CoverForEachCube( p->ppStore[i], pCube ) - Min_CoverForEachCube( pCube->pNext, pCube2 ) - { - assert( pCube->nLits == pCube2->nLits ); - if ( !Min_CubesDistOne( pCube, pCube2, NULL ) ) - continue; - pCubeNew = Min_CubesXor( p, pCube, pCube2 ); - assert( pCubeNew->nLits == pCube->nLits - 1 ); - pCubeNew->pNext = p->ppStore[pCubeNew->nLits]; - p->ppStore[pCubeNew->nLits] = pCubeNew; - p->nCubes++; - } - } + assert( Min_CubeCheck( pCube ) ); + assert( pCube != p->pBubble ); + assert( (int)pCube->nLits == Min_CubeCountLits(pCube) ); + while ( Min_SopAddCubeInt( p, pCube ) ); } + + + + /**Function************************************************************* Synopsis [] @@ -286,6 +488,38 @@ void Min_SopContain( Min_Man_t * p ) SeeAlso [] ***********************************************************************/ +void Min_SopDist1Merge( Min_Man_t * p ) +{ + Min_Cube_t * pCube, * pCube2, * pCubeNew; + int i; + for ( i = p->nVars; i >= 0; i-- ) + { + Min_CoverForEachCube( p->ppStore[i], pCube ) + Min_CoverForEachCube( pCube->pNext, pCube2 ) + { + assert( pCube->nLits == pCube2->nLits ); + if ( !Min_CubesDistOne( pCube, pCube2, NULL ) ) + continue; + pCubeNew = Min_CubesXor( p, pCube, pCube2 ); + assert( pCubeNew->nLits == pCube->nLits - 1 ); + pCubeNew->pNext = p->ppStore[pCubeNew->nLits]; + p->ppStore[pCubeNew->nLits] = pCubeNew; + p->nCubes++; + } + } +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ Min_Cube_t * Min_SopComplement( Min_Man_t * p, Min_Cube_t * pSharp ) { Vec_Int_t * vVars; @@ -334,6 +568,46 @@ Min_Cube_t * Min_SopComplement( Min_Man_t * p, Min_Cube_t * pSharp ) return Min_CoverCollect( p, p->nVars ); } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Min_SopCheck( Min_Man_t * p ) +{ + Min_Cube_t * pCube, * pThis; + int i; + + pCube = Min_CubeAlloc( p ); + Min_CubeXorBit( pCube, 2*0+1 ); + Min_CubeXorBit( pCube, 2*1+1 ); + Min_CubeXorBit( pCube, 2*2+0 ); + Min_CubeXorBit( pCube, 2*3+0 ); + Min_CubeXorBit( pCube, 2*4+0 ); + Min_CubeXorBit( pCube, 2*5+1 ); + Min_CubeXorBit( pCube, 2*6+1 ); + pCube->nLits = 7; + +// Min_CubeWrite( stdout, pCube ); + + // check that the cubes contain it + for ( i = 0; i <= p->nVars; i++ ) + Min_CoverForEachCube( p->ppStore[i], pThis ) + if ( pThis != p->pBubble && Min_CubeIsContained( pThis, pCube ) ) + { + Min_CubeRecycle( p, pCube ); + return 1; + } + Min_CubeRecycle( p, pCube ); + return 0; +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// |