covMinEsop.c File Reference

#include "covInt.h"

Go to the source code of this file.

Functions
static ABC_NAMESPACE_IMPL_START void	Min_EsopRewrite (Min_Man_t *p)
	DECLARATIONS ///. More...
void	Min_EsopMinimize (Min_Man_t *p)
	FUNCTION DEFINITIONS ///. More...
int	Min_EsopAddCubeInt (Min_Man_t *p, Min_Cube_t *pCube)
void	Min_EsopAddCube (Min_Man_t *p, Min_Cube_t *pCube)

Function Documentation

void Min_EsopAddCube	(	Min_Man_t *	p,
		Min_Cube_t *	pCube
	)

Function*************************************************************

Synopsis [Adds the cube to storage.]

Description []

SideEffects []

SeeAlso []

Definition at line 291 of file covMinEsop.c.

{
    assert( pCube != p->pBubble );
    assert( (int)pCube->nLits == Min_CubeCountLits(pCube) );
    while ( Min_EsopAddCubeInt( p, pCube ) );
}

int Min_EsopAddCubeInt	(	Min_Man_t *	p,
		Min_Cube_t *	pCube
	)

Function*************************************************************

Synopsis [Adds the cube to storage.]

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. Do not forget to clean the storage!]

SideEffects []

SeeAlso []

Definition at line 220 of file covMinEsop.c.

{
    Min_Cube_t * pThis, ** ppPrev;
    // try to find the identical cube
    Min_CoverForEachCubePrev( p->ppStore[pCube->nLits], pThis, ppPrev )
    {
        if ( Min_CubesAreEqual( pCube, pThis ) )
        {
            *ppPrev = pThis->pNext;
            Min_CubeRecycle( p, pCube );
            Min_CubeRecycle( p, pThis );
            p->nCubes--;
            return 0;
        }
    }
    // find a distance-1 cube if it exists
    if ( pCube->nLits < pCube->nVars )
    Min_CoverForEachCubePrev( p->ppStore[pCube->nLits+1], pThis, ppPrev )
    {
        if ( Min_CubesDistOne( pCube, pThis, p->pTemp ) )
        {
            *ppPrev = pThis->pNext;
            Min_CubesTransform( pCube, pThis, p->pTemp );
            pCube->nLits++;
            Min_CubeRecycle( p, pThis );
            p->nCubes--;
            return 1;
        }
    }
    Min_CoverForEachCubePrev( p->ppStore[pCube->nLits], pThis, ppPrev )
    {
        if ( Min_CubesDistOne( pCube, pThis, p->pTemp ) )
        {
            *ppPrev = pThis->pNext;
            Min_CubesTransform( pCube, pThis, p->pTemp );
            pCube->nLits--;
            Min_CubeRecycle( p, pThis );
            p->nCubes--;
            return 1;
        }
    }
    if ( pCube->nLits > 0 )
    Min_CoverForEachCubePrev( p->ppStore[pCube->nLits-1], pThis, ppPrev )
    {
        if ( Min_CubesDistOne( pCube, pThis, p->pTemp ) )
        {
            *ppPrev = pThis->pNext;
            Min_CubesTransform( pCube, pThis, p->pTemp );
            Min_CubeRecycle( p, pThis );
            p->nCubes--;
            return 1;
        }
    }
    // add the cube
    pCube->pNext = p->ppStore[pCube->nLits];
    p->ppStore[pCube->nLits] = pCube;
    p->nCubes++;
    return 0;
}

void Min_EsopMinimize

(

Min_Man_t *

p

)

FUNCTION DEFINITIONS ///.

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 47 of file covMinEsop.c.

{
    int nCubesInit, nCubesOld, nIter;
    if ( p->nCubes < 3 )
        return;
    nIter = 0;
    nCubesInit = p->nCubes;
    do {
        nCubesOld = p->nCubes;
        Min_EsopRewrite( p );
        nIter++;
    }
    while ( 100.0*(nCubesOld - p->nCubes)/nCubesOld > 3.0 );

//    printf( "%d:%d->%d ", nIter, nCubesInit, p->nCubes );
}

void Min_EsopRewrite ( Min_Man_t *  p )

static

DECLARATIONS ///.

CFile****************************************************************

FileName [covMinEsop.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Mapping into network of SOPs/ESOPs.]

Synopsis [ESOP manipulation.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - June 20, 2005.]

Revision [

Id:

covMinEsop.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

]

Function*************************************************************

Synopsis [Performs one round of rewriting using distance 2 cubes.]

Description [The weakness of this procedure is that it tries each cube with only one distance-2 cube. If this pair does not lead to improvement the cube is inserted into the cover anyhow, and we try another pair. A possible improvement would be to try this cube with all distance-2 cubes, until an improvement is found, or until all such cubes are tried.]

SideEffects []

SeeAlso []

Definition at line 79 of file covMinEsop.c.

{
    Min_Cube_t * pCube, ** ppPrev;
    Min_Cube_t * pThis, ** ppPrevT;
    int v00, v01, v10, v11, Var0, Var1, Index, nCubesOld;
    int nPairs = 0;

    // insert the bubble before the first cube
    p->pBubble->pNext = p->ppStore[0];
    p->ppStore[0] = p->pBubble;
    p->pBubble->nLits = 0;

    // go through the cubes
    while ( 1 )
    {
        // get the index of the bubble
        Index = p->pBubble->nLits;

        // find the bubble
        Min_CoverForEachCubePrev( p->ppStore[Index], pCube, ppPrev )
            if ( pCube == p->pBubble )
                break;
        assert( pCube == p->pBubble );

        // remove the bubble, get the next cube after the bubble
        *ppPrev = p->pBubble->pNext;
        pCube = p->pBubble->pNext;
        if ( pCube == NULL )
            for ( Index++; Index <= p->nVars; Index++ )
                if ( p->ppStore[Index] )
                {
                    ppPrev = &(p->ppStore[Index]);
                    pCube = p->ppStore[Index];
                    break;
                }
        // stop if there is no more cubes
        if ( pCube == NULL )
            break;

        // find the first dist2 cube
        Min_CoverForEachCubePrev( pCube->pNext, pThis, ppPrevT )
            if ( Min_CubesDistTwo( pCube, pThis, &Var0, &Var1 ) )
                break;
        if ( pThis == NULL && Index < p->nVars )
        Min_CoverForEachCubePrev( p->ppStore[Index+1], pThis, ppPrevT )
            if ( Min_CubesDistTwo( pCube, pThis, &Var0, &Var1 ) )
                break;
        if ( pThis == NULL && Index < p->nVars - 1 )
        Min_CoverForEachCubePrev( p->ppStore[Index+2], pThis, ppPrevT )
            if ( Min_CubesDistTwo( pCube, pThis, &Var0, &Var1 ) )
                break;
        // continue if there is no dist2 cube
        if ( pThis == NULL )
        {
            // insert the bubble after the cube
            p->pBubble->pNext = pCube->pNext;
            pCube->pNext = p->pBubble;
            p->pBubble->nLits = pCube->nLits;
            continue;
        }
        nPairs++;

        // remove the cubes, insert the bubble instead of pCube
        *ppPrevT = pThis->pNext;
        *ppPrev = p->pBubble;
        p->pBubble->pNext = pCube->pNext;
        p->pBubble->nLits = pCube->nLits;
        p->nCubes -= 2;

        // Exorlink-2:
        // A{v00}     B{v01}      +  A{v10}     B{v11}     =
        // A{v00+v10} B{v01}      +  A{v10}     B{v01+v11} =
        // A{v00}     B{v01+v11}  +  A{v00+v10} B{v11}

        // save the dist2 parameters
        v00 = Min_CubeGetVar( pCube, Var0 );
        v01 = Min_CubeGetVar( pCube, Var1 );
        v10 = Min_CubeGetVar( pThis, Var0 );
        v11 = Min_CubeGetVar( pThis, Var1 );
//printf( "\n" );
//Min_CubeWrite( stdout, pCube );
//Min_CubeWrite( stdout, pThis );

        // derive the first pair of resulting cubes
        Min_CubeXorVar( pCube, Var0, v10 );
        pCube->nLits -= (v00 != 3);
        pCube->nLits += ((v00 ^ v10) != 3);
        Min_CubeXorVar( pThis, Var1, v01 );
        pThis->nLits -= (v11 != 3);
        pThis->nLits += ((v01 ^ v11) != 3);

        // add the cubes
        nCubesOld = p->nCubes;
        Min_EsopAddCube( p, pCube );
        Min_EsopAddCube( p, pThis );
        // check if the cubes were absorbed
        if ( p->nCubes < nCubesOld + 2 )
            continue;

        // pull out both cubes
        assert( pThis == p->ppStore[pThis->nLits] );
        p->ppStore[pThis->nLits] = pThis->pNext;
        assert( pCube == p->ppStore[pCube->nLits] );
        p->ppStore[pCube->nLits] = pCube->pNext;
        p->nCubes -= 2;

        // derive the second pair of resulting cubes
        Min_CubeXorVar( pCube, Var0, v10 );
        pCube->nLits -= ((v00 ^ v10) != 3);
        pCube->nLits += (v00 != 3);
        Min_CubeXorVar( pCube, Var1, v11 );
        pCube->nLits -= (v01 != 3);
        pCube->nLits += ((v01 ^ v11) != 3);

        Min_CubeXorVar( pThis, Var0, v00 );
        pThis->nLits -= (v10 != 3);
        pThis->nLits += ((v00 ^ v10) != 3);
        Min_CubeXorVar( pThis, Var1, v01 );
        pThis->nLits -= ((v01 ^ v11) != 3);
        pThis->nLits += (v11 != 3);

        // add them anyhow
        Min_EsopAddCube( p, pCube );
        Min_EsopAddCube( p, pThis );
    }
//    printf( "Pairs = %d  ", nPairs );
}