covBuild.c File Reference

#include "cov.h"

Go to the source code of this file.

Functions
ABC_NAMESPACE_IMPL_START Abc_Obj_t *	Abc_NtkCovDeriveCube (Abc_Ntk_t *pNtkNew, Abc_Obj_t *pObj, Min_Cube_t *pCube, Vec_Int_t *vSupp, int fCompl)
	DECLARATIONS ///. More...
Abc_Obj_t *	Abc_NtkCovDeriveNode_rec (Cov_Man_t *p, Abc_Ntk_t *pNtkNew, Abc_Obj_t *pObj, int Level)
Abc_Ntk_t *	Abc_NtkCovDerive (Cov_Man_t *p, Abc_Ntk_t *pNtk)
	FUNCTION DEFINITIONS ///. More...
Abc_Obj_t *	Abc_NtkCovDeriveInv (Abc_Ntk_t *pNtkNew, Abc_Obj_t *pObj, int fCompl)
Abc_Obj_t *	Abc_NtkCovDeriveCubeInv (Abc_Ntk_t *pNtkNew, Abc_Obj_t *pObj, Min_Cube_t *pCube, Vec_Int_t *vSupp)
Abc_Obj_t *	Abc_NtkCovDeriveNodeInv_rec (Cov_Man_t *p, Abc_Ntk_t *pNtkNew, Abc_Obj_t *pObj, int fCompl)
Abc_Ntk_t *	Abc_NtkCovDeriveClean (Cov_Man_t *p, Abc_Ntk_t *pNtk)
Abc_Obj_t *	Abc_NtkCovDerive_rec (Cov_Man_t *p, Abc_Ntk_t *pNtkNew, Abc_Obj_t *pObj)
Abc_Ntk_t *	Abc_NtkCovDeriveRegular (Cov_Man_t *p, Abc_Ntk_t *pNtk)

Function Documentation

Abc_Ntk_t* Abc_NtkCovDerive	(	Cov_Man_t *	p,
		Abc_Ntk_t *	pNtk
	)

FUNCTION DEFINITIONS ///.

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

Synopsis [Derives the decomposed network.]

Description []

SideEffects []

SeeAlso []

Definition at line 183 of file covBuild.c.

{
    Abc_Ntk_t * pNtkNew;
    Abc_Obj_t * pObj;
    int i;
    assert( Abc_NtkIsStrash(pNtk) );
    // perform strashing
    pNtkNew = Abc_NtkStartFrom( pNtk, ABC_NTK_LOGIC, ABC_FUNC_SOP );
    // reconstruct the network
    Abc_NtkForEachCo( pNtk, pObj, i )
    {
        Abc_NtkCovDeriveNode_rec( p, pNtkNew, Abc_ObjFanin0(pObj), 0 );
//        printf( "*** CO %s : %d -> %d \n", Abc_ObjName(pObj), pObj->pCopy->Id, Abc_ObjFanin0(pObj)->pCopy->Id );
    }
    // add the COs
    Abc_NtkFinalize( pNtk, pNtkNew );
    Abc_NtkLogicMakeSimpleCos( pNtkNew, 1 );
    // make sure everything is okay
    if ( !Abc_NtkCheck( pNtkNew ) )
    {
        printf( "Abc_NtkCovDerive: The network check has failed.\n" );
        Abc_NtkDelete( pNtkNew );
        return NULL;
    }
    return pNtkNew;
}

Abc_Obj_t* Abc_NtkCovDerive_rec	(	Cov_Man_t *	p,
		Abc_Ntk_t *	pNtkNew,
		Abc_Obj_t *	pObj
	)

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

Synopsis [Derives the decomposed network.]

Description []

SideEffects []

SeeAlso []

Definition at line 396 of file covBuild.c.

{
    int fVerbose = 0;
    Min_Cube_t * pCover, * pCovers[3];
    Abc_Obj_t * pNodeNew, * pFanin;
    Vec_Int_t * vSupp;
    Vec_Str_t * vCover;
    int i, Entry, nCubes, Type;
    // skip if already computed
    if ( pObj->pCopy )
        return pObj->pCopy;
    assert( Abc_ObjIsNode(pObj) );
    // get the support and the cover
    vSupp  = Abc_ObjGetSupp( pObj ); 
    assert( vSupp );
    // choose the cover to implement
    pCovers[0] = Abc_ObjGetCover( pObj, 0 );
    pCovers[1] = Abc_ObjGetCover( pObj, 1 );
    pCovers[2] = Abc_ObjGetCover2( pObj );
    // use positive polarity
    if ( pCovers[0] 
        && (!pCovers[1] || Min_CoverCountCubes(pCovers[0]) <= Min_CoverCountCubes(pCovers[1]))
        && (!pCovers[2] || Min_CoverCountCubes(pCovers[0]) <= Min_CoverCountCubes(pCovers[2]))   )
    {
        pCover = pCovers[0];
        Type = '1';
    }
    else 
    // use negative polarity
    if ( pCovers[1] 
        && (!pCovers[0] || Min_CoverCountCubes(pCovers[1]) <= Min_CoverCountCubes(pCovers[0]))
        && (!pCovers[2] || Min_CoverCountCubes(pCovers[1]) <= Min_CoverCountCubes(pCovers[2]))   )
    {
        pCover = pCovers[1];
        Type = '0';
    }
    else 
    // use XOR polarity
    if ( pCovers[2] 
        && (!pCovers[0] || Min_CoverCountCubes(pCovers[2]) < Min_CoverCountCubes(pCovers[0]))
        && (!pCovers[1] || Min_CoverCountCubes(pCovers[2]) < Min_CoverCountCubes(pCovers[1]))   )
    {
        pCover = pCovers[2];
        Type = 'x';
    }
    else
        assert( 0 );
    // print the support of this node
    if ( fVerbose )
    {
        printf( "{ " );
        Vec_IntForEachEntry( vSupp, Entry, i )
            printf( "%d ", Entry );
        printf( "}  cubes = %d\n", Min_CoverCountCubes( pCover ) );
    }
    // process the fanins
    Vec_IntForEachEntry( vSupp, Entry, i )
    {
        pFanin = Abc_NtkObj(pObj->pNtk, Entry);
        Abc_NtkCovDerive_rec( p, pNtkNew, pFanin );
    }
    // for each cube, construct the node
    nCubes = Min_CoverCountCubes( pCover );
    if ( nCubes == 0 )
        pNodeNew = Abc_NtkCreateNodeConst0(pNtkNew);
    else if ( nCubes == 1 )
        pNodeNew = Abc_NtkCovDeriveCube( pNtkNew, pObj, pCover, vSupp, Type == '0' );
    else
    {
        // create the node
        pNodeNew = Abc_NtkCreateNode( pNtkNew );
        Vec_IntForEachEntry( vSupp, Entry, i )
        {
            pFanin = Abc_NtkObj(pObj->pNtk, Entry);
            Abc_ObjAddFanin( pNodeNew, pFanin->pCopy );
        }
        // derive the function
        vCover = Vec_StrAlloc( 100 );
        Min_CoverCreate( vCover, pCover, (char)Type );
        pNodeNew->pData = Abc_SopRegister((Mem_Flex_t *)pNtkNew->pManFunc, Vec_StrArray(vCover) );
        Vec_StrFree( vCover );
    }

/*
    printf( "Created node %d(%d) at level %d: ", pNodeNew->Id, pObj->Id, Level );
    Vec_IntForEachEntry( vSupp, Entry, i )
    {
        pFanin = Abc_NtkObj(pObj->pNtk, Entry);
        printf( "%d(%d) ", pFanin->pCopy->Id, pFanin->Id );
    }
    printf( "\n" );
    Min_CoverWrite( stdout, pCover );
*/
    return pObj->pCopy = pNodeNew;
}

Abc_Ntk_t* Abc_NtkCovDeriveClean	(	Cov_Man_t *	p,
		Abc_Ntk_t *	pNtk
	)

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

Synopsis [Derives the decomposed network.]

Description [The resulting network contains only pure AND/OR/EXOR gates and inverters. This procedure is usedful to generate Verilog.]

SideEffects []

SeeAlso []

Definition at line 357 of file covBuild.c.

{
    Abc_Ntk_t * pNtkNew;
    Abc_Obj_t * pObj, * pNodeNew;
    int i;
    assert( Abc_NtkIsStrash(pNtk) );
    // perform strashing
    pNtkNew = Abc_NtkStartFrom( pNtk, ABC_NTK_LOGIC, ABC_FUNC_SOP );
    // reconstruct the network
    Abc_NtkForEachCo( pNtk, pObj, i )
    {
        pNodeNew = Abc_NtkCovDeriveNodeInv_rec( p, pNtkNew, Abc_ObjFanin0(pObj), Abc_ObjFaninC0(pObj) );
        Abc_ObjAddFanin( pObj->pCopy, pNodeNew );
    }
    // add the COs
    Abc_NtkLogicMakeSimpleCos( pNtkNew, 0 );
    // make sure everything is okay
    if ( !Abc_NtkCheck( pNtkNew ) )
    {
        printf( "Abc_NtkCovDeriveInv: The network check has failed.\n" );
        Abc_NtkDelete( pNtkNew );
        return NULL;
    }
    return pNtkNew;
}

ABC_NAMESPACE_IMPL_START Abc_Obj_t* Abc_NtkCovDeriveCube	(	Abc_Ntk_t *	pNtkNew,
		Abc_Obj_t *	pObj,
		Min_Cube_t *	pCube,
		Vec_Int_t *	vSupp,
		int	fCompl
	)

DECLARATIONS ///.

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

FileName [covBuild.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Mapping into network of SOPs/ESOPs.]

Synopsis [Network construction procedures.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id:

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

]FUNCTION DEFINITIONS /// Function*************************************************************

Synopsis [Derives the decomposed network.]

Description []

SideEffects []

SeeAlso []

Definition at line 45 of file covBuild.c.

{
    Vec_Int_t * vLits;
    Abc_Obj_t * pNodeNew, * pFanin;
    int i, iFanin, Lit;
    // create empty cube
    if ( pCube->nLits == 0 )
    {
        if ( fCompl )
            return Abc_NtkCreateNodeConst0(pNtkNew);
        return Abc_NtkCreateNodeConst1(pNtkNew);
    }
    // get the literals of this cube
    vLits = Vec_IntAlloc( 10 );
    Min_CubeGetLits( pCube, vLits );
    assert( pCube->nLits == (unsigned)vLits->nSize );
    // create special case when there is only one literal
    if ( pCube->nLits == 1 )
    {
        iFanin = Vec_IntEntry(vLits,0);
        pFanin = Abc_NtkObj( pObj->pNtk, Vec_IntEntry(vSupp, iFanin) );
        Lit = Min_CubeGetVar(pCube, iFanin);
        assert( Lit == 1 || Lit == 2 );
        Vec_IntFree( vLits );
        if ( (Lit == 1) ^ fCompl )// negative
            return Abc_NtkCreateNodeInv( pNtkNew, pFanin->pCopy );
        return pFanin->pCopy;
    }
    assert( pCube->nLits > 1 );
    // create the AND cube
    pNodeNew = Abc_NtkCreateNode( pNtkNew );
    for ( i = 0; i < vLits->nSize; i++ )
    {
        iFanin = Vec_IntEntry(vLits,i);
        pFanin = Abc_NtkObj( pObj->pNtk, Vec_IntEntry(vSupp, iFanin) );
        Lit = Min_CubeGetVar(pCube, iFanin);
        assert( Lit == 1 || Lit == 2 );
        Vec_IntWriteEntry( vLits, i, Lit==1 );
        Abc_ObjAddFanin( pNodeNew, pFanin->pCopy );
    }
    pNodeNew->pData = Abc_SopCreateAnd( (Mem_Flex_t *)pNtkNew->pManFunc, vLits->nSize, vLits->pArray );
    if ( fCompl )
        Abc_SopComplement( (char *)pNodeNew->pData );
    Vec_IntFree( vLits );
    return pNodeNew;
}

Abc_Obj_t* Abc_NtkCovDeriveCubeInv	(	Abc_Ntk_t *	pNtkNew,
		Abc_Obj_t *	pObj,
		Min_Cube_t *	pCube,
		Vec_Int_t *	vSupp
	)

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

Synopsis [Derives the decomposed network.]

Description []

SideEffects []

SeeAlso []

Definition at line 245 of file covBuild.c.

{
    Vec_Int_t * vLits;
    Abc_Obj_t * pNodeNew, * pFanin;
    int i, iFanin, Lit;
    // create empty cube
    if ( pCube->nLits == 0 )
        return Abc_NtkCreateNodeConst1(pNtkNew);
    // get the literals of this cube
    vLits = Vec_IntAlloc( 10 );
    Min_CubeGetLits( pCube, vLits );
    assert( pCube->nLits == (unsigned)vLits->nSize );
    // create special case when there is only one literal
    if ( pCube->nLits == 1 )
    {
        iFanin = Vec_IntEntry(vLits,0);
        pFanin = Abc_NtkObj( pObj->pNtk, Vec_IntEntry(vSupp, iFanin) );
        Lit = Min_CubeGetVar(pCube, iFanin);
        assert( Lit == 1 || Lit == 2 );
        Vec_IntFree( vLits );
//        if ( Lit == 1 )// negative
//            return Abc_NtkCreateNodeInv( pNtkNew, pFanin->pCopy );
//        return pFanin->pCopy;
        return Abc_NtkCovDeriveInv( pNtkNew, pFanin, Lit==1 );
    }
    assert( pCube->nLits > 1 );
    // create the AND cube
    pNodeNew = Abc_NtkCreateNode( pNtkNew );
    for ( i = 0; i < vLits->nSize; i++ )
    {
        iFanin = Vec_IntEntry(vLits,i);
        pFanin = Abc_NtkObj( pObj->pNtk, Vec_IntEntry(vSupp, iFanin) );
        Lit = Min_CubeGetVar(pCube, iFanin);
        assert( Lit == 1 || Lit == 2 );
        Vec_IntWriteEntry( vLits, i, Lit==1 );
//        Abc_ObjAddFanin( pNodeNew, pFanin->pCopy );
        Abc_ObjAddFanin( pNodeNew, Abc_NtkCovDeriveInv( pNtkNew, pFanin, Lit==1 ) );
    }
//    pNodeNew->pData = Abc_SopCreateAnd( (Mem_Flex_t *)pNtkNew->pManFunc, vLits->nSize, vLits->pArray );
    pNodeNew->pData = Abc_SopCreateAnd( (Mem_Flex_t *)pNtkNew->pManFunc, vLits->nSize, NULL );
    Vec_IntFree( vLits );
    return pNodeNew;
}

Abc_Obj_t* Abc_NtkCovDeriveInv	(	Abc_Ntk_t *	pNtkNew,
		Abc_Obj_t *	pObj,
		int	fCompl
	)

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

Synopsis [Derives the decomposed network.]

Description []

SideEffects []

SeeAlso []

Definition at line 224 of file covBuild.c.

{
    assert( pObj->pCopy );
    if ( !fCompl )
        return pObj->pCopy;
    if ( pObj->pCopy->pCopy == NULL )
        pObj->pCopy->pCopy = Abc_NtkCreateNodeInv( pNtkNew, pObj->pCopy );
    return pObj->pCopy->pCopy;
 }

Abc_Obj_t* Abc_NtkCovDeriveNode_rec	(	Cov_Man_t *	p,
		Abc_Ntk_t *	pNtkNew,
		Abc_Obj_t *	pObj,
		int	Level
	)

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

Synopsis [Derives the decomposed network.]

Description []

SideEffects []

SeeAlso []

Definition at line 103 of file covBuild.c.

{
    Min_Cube_t * pCover, * pCube;
    Abc_Obj_t * pFaninNew, * pNodeNew, * pFanin;
    Vec_Int_t * vSupp;
    int Entry, nCubes, i;

    if ( Abc_ObjIsCi(pObj) )
        return pObj->pCopy;
    assert( Abc_ObjIsNode(pObj) );
    // skip if already computed
    if ( pObj->pCopy )
        return pObj->pCopy;

    // get the support and the cover
    vSupp  = Abc_ObjGetSupp( pObj ); 
    pCover = Abc_ObjGetCover2( pObj );
    assert( vSupp );
/*
    if ( pCover &&  pCover->nVars - Min_CoverSuppVarNum(p->pManMin, pCover) > 0 )
    {
        printf( "%d\n ", pCover->nVars - Min_CoverSuppVarNum(p->pManMin, pCover) );
        Min_CoverWrite( stdout, pCover );
    }
*/
/*
    // print the support of this node
    printf( "{ " );
    Vec_IntForEachEntry( vSupp, Entry, i )
        printf( "%d ", Entry );
    printf( "}  cubes = %d\n", Min_CoverCountCubes( pCover ) );
*/
    // process the fanins
    Vec_IntForEachEntry( vSupp, Entry, i )
    {
        pFanin = Abc_NtkObj(pObj->pNtk, Entry);
        Abc_NtkCovDeriveNode_rec( p, pNtkNew, pFanin, Level+1 );
    }

    // for each cube, construct the node
    nCubes = Min_CoverCountCubes( pCover );
    if ( nCubes == 0 )
        pNodeNew = Abc_NtkCreateNodeConst0(pNtkNew);
    else if ( nCubes == 1 )
        pNodeNew = Abc_NtkCovDeriveCube( pNtkNew, pObj, pCover, vSupp, 0 );
    else
    {
        pNodeNew = Abc_NtkCreateNode( pNtkNew );
        Min_CoverForEachCube( pCover, pCube )
        {
            pFaninNew = Abc_NtkCovDeriveCube( pNtkNew, pObj, pCube, vSupp, 0 );
            Abc_ObjAddFanin( pNodeNew, pFaninNew );
        }
        pNodeNew->pData = Abc_SopCreateXorSpecial( (Mem_Flex_t *)pNtkNew->pManFunc, nCubes );
    }
/*
    printf( "Created node %d(%d) at level %d: ", pNodeNew->Id, pObj->Id, Level );
    Vec_IntForEachEntry( vSupp, Entry, i )
    {
        pFanin = Abc_NtkObj(pObj->pNtk, Entry);
        printf( "%d(%d) ", pFanin->pCopy->Id, pFanin->Id );
    }
    printf( "\n" );
    Min_CoverWrite( stdout, pCover );
*/
    pObj->pCopy = pNodeNew;
    return pNodeNew;
}

Abc_Obj_t* Abc_NtkCovDeriveNodeInv_rec	(	Cov_Man_t *	p,
		Abc_Ntk_t *	pNtkNew,
		Abc_Obj_t *	pObj,
		int	fCompl
	)

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

Synopsis [Derives the decomposed network.]

Description []

SideEffects []

SeeAlso []

Definition at line 300 of file covBuild.c.

{
    Min_Cube_t * pCover, * pCube;
    Abc_Obj_t * pFaninNew, * pNodeNew, * pFanin;
    Vec_Int_t * vSupp;
    int Entry, nCubes, i;

    // skip if already computed
    if ( pObj->pCopy )
        return Abc_NtkCovDeriveInv( pNtkNew, pObj, fCompl );
    assert( Abc_ObjIsNode(pObj) );

    // get the support and the cover
    vSupp  = Abc_ObjGetSupp( pObj ); 
    pCover = Abc_ObjGetCover2( pObj );
    assert( vSupp );

    // process the fanins
    Vec_IntForEachEntry( vSupp, Entry, i )
    {
        pFanin = Abc_NtkObj(pObj->pNtk, Entry);
        Abc_NtkCovDeriveNodeInv_rec( p, pNtkNew, pFanin, 0 );
    }

    // for each cube, construct the node
    nCubes = Min_CoverCountCubes( pCover );
    if ( nCubes == 0 )
        pNodeNew = Abc_NtkCreateNodeConst0(pNtkNew);
    else if ( nCubes == 1 )
        pNodeNew = Abc_NtkCovDeriveCubeInv( pNtkNew, pObj, pCover, vSupp );
    else
    {
        pNodeNew = Abc_NtkCreateNode( pNtkNew );
        Min_CoverForEachCube( pCover, pCube )
        {
            pFaninNew = Abc_NtkCovDeriveCubeInv( pNtkNew, pObj, pCube, vSupp );
            Abc_ObjAddFanin( pNodeNew, pFaninNew );
        }
        pNodeNew->pData = Abc_SopCreateXorSpecial( (Mem_Flex_t *)pNtkNew->pManFunc, nCubes );
    }

    pObj->pCopy = pNodeNew;
    return Abc_NtkCovDeriveInv( pNtkNew, pObj, fCompl );
}

Abc_Ntk_t* Abc_NtkCovDeriveRegular	(	Cov_Man_t *	p,
		Abc_Ntk_t *	pNtk
	)

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

Synopsis [Derives the decomposed network.]

Description []

SideEffects []

SeeAlso []

Definition at line 503 of file covBuild.c.

{
    Abc_Ntk_t * pNtkNew;
    Abc_Obj_t * pObj, * pNodeNew;
    int i;
    assert( Abc_NtkIsStrash(pNtk) );
    // perform strashing
    pNtkNew = Abc_NtkStartFrom( pNtk, ABC_NTK_LOGIC, ABC_FUNC_SOP );
    // reconstruct the network
    if ( Abc_ObjFanoutNum(Abc_AigConst1(pNtk)) > 0 )
        Abc_AigConst1(pNtk)->pCopy = Abc_NtkCreateNodeConst1(pNtkNew);
    Abc_NtkForEachCo( pNtk, pObj, i )
    {
        pNodeNew = Abc_NtkCovDerive_rec( p, pNtkNew, Abc_ObjFanin0(pObj) );
        if ( Abc_ObjFaninC0(pObj) )
        {
            if ( pNodeNew->pData && Abc_ObjFanoutNum(Abc_ObjFanin0(pObj)) == 1 )
                Abc_SopComplement( (char *)pNodeNew->pData );
            else
                pNodeNew = Abc_NtkCreateNodeInv( pNtkNew, pNodeNew );
        }
        Abc_ObjAddFanin( pObj->pCopy, pNodeNew );
    }
    // add the COs
    Abc_NtkLogicMakeSimpleCos( pNtkNew, 0 );
    // make sure everything is okay
    if ( !Abc_NtkCheck( pNtkNew ) )
    {
        printf( "Abc_NtkCovDerive: The network check has failed.\n" );
        Abc_NtkDelete( pNtkNew );
        return NULL;
    }
    return pNtkNew;
}