kitGraph.c File Reference

#include "kit.h"
#include "misc/extra/extra.h"

Include dependency graph for kitGraph.c:

Go to the source code of this file.

Functions
ABC_NAMESPACE_IMPL_START Kit_Graph_t *	Kit_GraphCreate (int nLeaves)
	DECLARATIONS ///.
Kit_Graph_t *	Kit_GraphCreateConst0 ()
Kit_Graph_t *	Kit_GraphCreateConst1 ()
Kit_Graph_t *	Kit_GraphCreateLeaf (int iLeaf, int nLeaves, int fCompl)
void	Kit_GraphFree (Kit_Graph_t *pGraph)
Kit_Node_t *	Kit_GraphAppendNode (Kit_Graph_t *pGraph)
Kit_Edge_t	Kit_GraphAddNodeAnd (Kit_Graph_t *pGraph, Kit_Edge_t eEdge0, Kit_Edge_t eEdge1)
Kit_Edge_t	Kit_GraphAddNodeOr (Kit_Graph_t *pGraph, Kit_Edge_t eEdge0, Kit_Edge_t eEdge1)
Kit_Edge_t	Kit_GraphAddNodeXor (Kit_Graph_t *pGraph, Kit_Edge_t eEdge0, Kit_Edge_t eEdge1, int Type)
Kit_Edge_t	Kit_GraphAddNodeMux (Kit_Graph_t *pGraph, Kit_Edge_t eEdgeC, Kit_Edge_t eEdgeT, Kit_Edge_t eEdgeE, int Type)
unsigned	Kit_GraphToTruth (Kit_Graph_t *pGraph)
Kit_Graph_t *	Kit_TruthToGraph (unsigned *pTruth, int nVars, Vec_Int_t *vMemory)
Kit_Graph_t *	Kit_TruthToGraph2 (unsigned *pTruth0, unsigned *pTruth1, int nVars, Vec_Int_t *vMemory)
int	Kit_GraphLeafDepth_rec (Kit_Graph_t *pGraph, Kit_Node_t *pNode, Kit_Node_t *pLeaf)
int	Kit_GraphLevelNum_rec (Kit_Graph_t *pGraph, Kit_Node_t *pNode)
int	Kit_TruthStats (unsigned *pTruth, int nVars, Vec_Int_t *vMemory)
int *	Kit_TruthStatsArray (unsigned *pArray, int nVars, int nFuncs)
int	Kit_TruthFindVarNum (char *pFileName)
int *	Kit_TruthTest (char *pFileName)
int	Kit_TruthLitNum (unsigned *pTruth, int nVars, Vec_Int_t *vMemory)

Function Documentation

Kit_GraphAddNodeAnd()

Kit_Edge_t Kit_GraphAddNodeAnd	(	Kit_Graph_t *	pGraph,
		Kit_Edge_t	eEdge0,
		Kit_Edge_t	eEdge1 )

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

Synopsis [Creates an AND node.]

Description []

SideEffects []

SeeAlso []

Definition at line 173 of file kitGraph.c.

{
    Kit_Node_t * pNode;
    // get the new node
    pNode = Kit_GraphAppendNode( pGraph );
    // set the inputs and other info
    pNode->eEdge0 = eEdge0;
    pNode->eEdge1 = eEdge1;
    pNode->fCompl0 = eEdge0.fCompl;
    pNode->fCompl1 = eEdge1.fCompl;
    return Kit_EdgeCreate( pGraph->nSize - 1, 0 );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Kit_GraphAddNodeMux()

Kit_Edge_t Kit_GraphAddNodeMux	(	Kit_Graph_t *	pGraph,
		Kit_Edge_t	eEdgeC,
		Kit_Edge_t	eEdgeT,
		Kit_Edge_t	eEdgeE,
		int	Type )

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

Synopsis [Creates an XOR node.]

Description []

SideEffects []

SeeAlso []

Definition at line 266 of file kitGraph.c.

{
    Kit_Edge_t eNode0, eNode1, eNode;
    if ( Type == 0 )
    {
        // derive the first AND
        eNode0 = Kit_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeT );
        // derive the second AND
        eEdgeC.fCompl ^= 1;
        eNode1 = Kit_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeE );
        // derive the final OR
        eNode = Kit_GraphAddNodeOr( pGraph, eNode0, eNode1 );
    }
    else
    {
        // complement the arguments
        eEdgeT.fCompl ^= 1;
        eEdgeE.fCompl ^= 1;
        // derive the first AND
        eNode0 = Kit_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeT );
        // derive the second AND
        eEdgeC.fCompl ^= 1;
        eNode1 = Kit_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeE );
        // derive the final OR
        eNode = Kit_GraphAddNodeOr( pGraph, eNode0, eNode1 );
        eNode.fCompl ^= 1;
    }
    return eNode;
}

Here is the call graph for this function:

Kit_GraphAddNodeOr()

Kit_Edge_t Kit_GraphAddNodeOr	(	Kit_Graph_t *	pGraph,
		Kit_Edge_t	eEdge0,
		Kit_Edge_t	eEdge1 )

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

Synopsis [Creates an OR node.]

Description []

SideEffects []

SeeAlso []

Definition at line 197 of file kitGraph.c.

{
    Kit_Node_t * pNode;
    // get the new node
    pNode = Kit_GraphAppendNode( pGraph );
    // set the inputs and other info
    pNode->eEdge0 = eEdge0;
    pNode->eEdge1 = eEdge1;
    pNode->fCompl0 = eEdge0.fCompl;
    pNode->fCompl1 = eEdge1.fCompl;
    // make adjustments for the OR gate
    pNode->fNodeOr = 1;
    pNode->eEdge0.fCompl = !pNode->eEdge0.fCompl;
    pNode->eEdge1.fCompl = !pNode->eEdge1.fCompl;
    return Kit_EdgeCreate( pGraph->nSize - 1, 1 );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Kit_GraphAddNodeXor()

Kit_Edge_t Kit_GraphAddNodeXor	(	Kit_Graph_t *	pGraph,
		Kit_Edge_t	eEdge0,
		Kit_Edge_t	eEdge1,
		int	Type )

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

Synopsis [Creates an XOR node.]

Description []

SideEffects []

SeeAlso []

Definition at line 225 of file kitGraph.c.

{
    Kit_Edge_t eNode0, eNode1, eNode;
    if ( Type == 0 )
    {
        // derive the first AND
        eEdge0.fCompl ^= 1;
        eNode0 = Kit_GraphAddNodeAnd( pGraph, eEdge0, eEdge1 );
        eEdge0.fCompl ^= 1;
        // derive the second AND
        eEdge1.fCompl ^= 1;
        eNode1 = Kit_GraphAddNodeAnd( pGraph, eEdge0, eEdge1 );
        // derive the final OR
        eNode = Kit_GraphAddNodeOr( pGraph, eNode0, eNode1 );
    }
    else
    {
        // derive the first AND
        eNode0 = Kit_GraphAddNodeAnd( pGraph, eEdge0, eEdge1 );
        // derive the second AND
        eEdge0.fCompl ^= 1;
        eEdge1.fCompl ^= 1;
        eNode1 = Kit_GraphAddNodeAnd( pGraph, eEdge0, eEdge1 );
        // derive the final OR
        eNode = Kit_GraphAddNodeOr( pGraph, eNode0, eNode1 );
        eNode.fCompl ^= 1;
    }
    return eNode;
}

Here is the call graph for this function:

Kit_GraphAppendNode()

Kit_Node_t * Kit_GraphAppendNode

(

Kit_Graph_t *

pGraph

)

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

Synopsis [Appends a new node to the graph.]

Description [This procedure is meant for internal use.]

SideEffects []

SeeAlso []

Definition at line 149 of file kitGraph.c.

{
    Kit_Node_t * pNode;
    if ( pGraph->nSize == pGraph->nCap )
    {
        pGraph->pNodes = ABC_REALLOC( Kit_Node_t, pGraph->pNodes, 2 * pGraph->nCap ); 
        pGraph->nCap   = 2 * pGraph->nCap;
    }
    pNode = pGraph->pNodes + pGraph->nSize++;
    memset( pNode, 0, sizeof(Kit_Node_t) );
    return pNode;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Kit_GraphCreate()

ABC_NAMESPACE_IMPL_START Kit_Graph_t * Kit_GraphCreate

(

int

nLeaves

)

DECLARATIONS ///.

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

FileName [kitGraph.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Computation kit.]

Synopsis [Decomposition graph representation.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - Dec 6, 2006.]

Revision [

Id

kitGraph.c,v 1.00 2006/12/06 00:00:00 alanmi Exp

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

Synopsis [Creates a graph with the given number of leaves.]

Description []

SideEffects []

SeeAlso []

Definition at line 46 of file kitGraph.c.

{
    Kit_Graph_t * pGraph;
    pGraph = ABC_ALLOC( Kit_Graph_t, 1 );
    memset( pGraph, 0, sizeof(Kit_Graph_t) );
    pGraph->nLeaves = nLeaves;
    pGraph->nSize = nLeaves;
    pGraph->nCap = 2 * nLeaves + 50;
    pGraph->pNodes = ABC_ALLOC( Kit_Node_t, pGraph->nCap );
    memset( pGraph->pNodes, 0, sizeof(Kit_Node_t) * pGraph->nSize );
    return pGraph;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Kit_GraphCreateConst0()

Kit_Graph_t * Kit_GraphCreateConst0

(

)

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

Synopsis [Creates constant 0 graph.]

Description []

SideEffects []

SeeAlso []

Definition at line 70 of file kitGraph.c.

{
    Kit_Graph_t * pGraph;
    pGraph = ABC_ALLOC( Kit_Graph_t, 1 );
    memset( pGraph, 0, sizeof(Kit_Graph_t) );
    pGraph->fConst = 1;
    pGraph->eRoot.fCompl = 1;
    return pGraph;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Kit_GraphCreateConst1()

Kit_Graph_t * Kit_GraphCreateConst1

(

)

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

Synopsis [Creates constant 1 graph.]

Description []

SideEffects []

SeeAlso []

Definition at line 91 of file kitGraph.c.

{
    Kit_Graph_t * pGraph;
    pGraph = ABC_ALLOC( Kit_Graph_t, 1 );
    memset( pGraph, 0, sizeof(Kit_Graph_t) );
    pGraph->fConst = 1;
    return pGraph;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Kit_GraphCreateLeaf()

Kit_Graph_t * Kit_GraphCreateLeaf	(	int	iLeaf,
		int	nLeaves,
		int	fCompl )

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

Synopsis [Creates the literal graph.]

Description []

SideEffects []

SeeAlso []

Definition at line 111 of file kitGraph.c.

{
    Kit_Graph_t * pGraph;
    assert( 0 <= iLeaf && iLeaf < nLeaves );
    pGraph = Kit_GraphCreate( nLeaves );
    pGraph->eRoot.Node   = iLeaf;
    pGraph->eRoot.fCompl = fCompl;
    return pGraph;
}

Here is the call graph for this function:

Kit_GraphFree()

void Kit_GraphFree

(

Kit_Graph_t *

pGraph

)

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

Synopsis [Creates a graph with the given number of leaves.]

Description []

SideEffects []

SeeAlso []

Definition at line 132 of file kitGraph.c.

{
    ABC_FREE( pGraph->pNodes );
    ABC_FREE( pGraph );
}

Here is the caller graph for this function:

Kit_GraphLeafDepth_rec()

int Kit_GraphLeafDepth_rec	(	Kit_Graph_t *	pGraph,
		Kit_Node_t *	pNode,
		Kit_Node_t *	pLeaf )

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

Synopsis [Derives the maximum depth from the leaf to the root.]

Description []

SideEffects []

SeeAlso []

Definition at line 412 of file kitGraph.c.

{
    int Depth0, Depth1, Depth;
    if ( pNode == pLeaf )
        return 0;
    if ( Kit_GraphNodeIsVar(pGraph, pNode) )
        return -100;
    Depth0 = Kit_GraphLeafDepth_rec( pGraph, Kit_GraphNodeFanin0(pGraph, pNode), pLeaf );
    Depth1 = Kit_GraphLeafDepth_rec( pGraph, Kit_GraphNodeFanin1(pGraph, pNode), pLeaf );
    Depth = KIT_MAX( Depth0, Depth1 );
    Depth = (Depth == -100) ? -100 : Depth + 1;
    return Depth;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Kit_GraphLevelNum_rec()

int Kit_GraphLevelNum_rec	(	Kit_Graph_t *	pGraph,
		Kit_Node_t *	pNode )

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

Synopsis [Derives logic level of the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 437 of file kitGraph.c.

{
    int Depth0, Depth1;
    if ( Kit_GraphNodeIsVar(pGraph, pNode) )
        return 0;
    Depth0 = Kit_GraphLevelNum_rec( pGraph, Kit_GraphNodeFanin0(pGraph, pNode) );
    Depth1 = Kit_GraphLevelNum_rec( pGraph, Kit_GraphNodeFanin1(pGraph, pNode) );
    return 1 + KIT_MAX( Depth0, Depth1 );
}

Here is the call graph for this function:

Here is the caller graph for this function:

Kit_GraphToTruth()

unsigned Kit_GraphToTruth

(

Kit_Graph_t *

pGraph

)

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

Synopsis [Derives the truth table.]

Description []

SideEffects []

SeeAlso []

Definition at line 307 of file kitGraph.c.

{
    unsigned uTruths[5] = { 0xAAAAAAAA, 0xCCCCCCCC, 0xF0F0F0F0, 0xFF00FF00, 0xFFFF0000 };
    unsigned uTruth = 0, uTruth0, uTruth1;
    Kit_Node_t * pNode;
    int i;
 
    // sanity checks
    assert( Kit_GraphLeaveNum(pGraph) >= 0 );
    assert( Kit_GraphLeaveNum(pGraph) <= pGraph->nSize );
    assert( Kit_GraphLeaveNum(pGraph) <= 5 );
 
    // check for constant function
    if ( Kit_GraphIsConst(pGraph) )
        return Kit_GraphIsComplement(pGraph)? 0 : ~((unsigned)0);
    // check for a literal
    if ( Kit_GraphIsVar(pGraph) )
        return Kit_GraphIsComplement(pGraph)? ~uTruths[Kit_GraphVarInt(pGraph)] : uTruths[Kit_GraphVarInt(pGraph)];
 
    // assign the elementary variables
    Kit_GraphForEachLeaf( pGraph, pNode, i )
        pNode->pFunc = (void *)(long)uTruths[i];
 
    // compute the function for each internal node
    Kit_GraphForEachNode( pGraph, pNode, i )
    {
        uTruth0 = (unsigned)(long)Kit_GraphNode(pGraph, pNode->eEdge0.Node)->pFunc;
        uTruth1 = (unsigned)(long)Kit_GraphNode(pGraph, pNode->eEdge1.Node)->pFunc;
        uTruth0 = pNode->eEdge0.fCompl? ~uTruth0 : uTruth0;
        uTruth1 = pNode->eEdge1.fCompl? ~uTruth1 : uTruth1;
        uTruth = uTruth0 & uTruth1;
        pNode->pFunc = (void *)(long)uTruth;
    }
 
    // complement the result if necessary
    return Kit_GraphIsComplement(pGraph)? ~uTruth : uTruth;
}

Kit_TruthFindVarNum()

int Kit_TruthFindVarNum

(

char *

pFileName

)

Definition at line 476 of file kitGraph.c.

{
    int i;
    for ( i = 0; i < (int)strlen(pFileName); i++ )
        if ( pFileName[i] >= '0' && pFileName[i] <= '9' )
            return atoi(pFileName+i);
    return -1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Kit_TruthLitNum()

int Kit_TruthLitNum	(	unsigned *	pTruth,
		int	nVars,
		Vec_Int_t *	vMemory )

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

Synopsis [Derives the factored form from the truth table.]

Description []

SideEffects []

SeeAlso []

Definition at line 511 of file kitGraph.c.

{
    Kit_Graph_t * pGraph;
    int RetValue, nLits;
    RetValue = Kit_TruthIsop( pTruth, nVars, vMemory, 1 ); 
    if ( RetValue == -1 || Vec_IntSize(vMemory) > (1<<16) )
        return -1;
    assert( RetValue == 0 || RetValue == 1 );
    pGraph = Kit_SopFactor( vMemory, RetValue, nVars, vMemory );
    nLits = 1 + Kit_GraphNodeNum( pGraph );
    Kit_GraphFree( pGraph );
    return nLits;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Kit_TruthStats()

int Kit_TruthStats	(	unsigned *	pTruth,
		int	nVars,
		Vec_Int_t *	vMemory )

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

Synopsis [Returns FF nodes and levels.]

Description []

SideEffects []

SeeAlso []

Definition at line 458 of file kitGraph.c.

{
    Kit_Graph_t * pGraph = Kit_TruthToGraph( pTruth, nVars, vMemory );
    int nNodes  = Kit_GraphNodeNum( pGraph );
    int nLevels = Kit_GraphLevelNum_rec( pGraph, Kit_GraphNodeLast(pGraph) );
    Kit_GraphFree( pGraph );
    return (nLevels << 16) | nNodes;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Kit_TruthStatsArray()

int * Kit_TruthStatsArray	(	unsigned *	pArray,
		int	nVars,
		int	nFuncs )

Definition at line 466 of file kitGraph.c.

{
    int f, * pRes = ABC_CALLOC( int, nFuncs );
    int nInts = Abc_TruthWordNum( nVars );
    Vec_Int_t * vMemory = Vec_IntAlloc( 1 << 16 );
    for ( f = 0; f < nFuncs; f++ )
        pRes[f] = Kit_TruthStats( pArray + f*nInts, nVars, vMemory );
    Vec_IntFree( vMemory );
    return pRes;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Kit_TruthTest()

int * Kit_TruthTest

(

char *

pFileName

)

Definition at line 484 of file kitGraph.c.

{
    abctime clk   = Abc_Clock(); int i;
    int nFileSize = Extra_FileSize( pFileName );
    int nVars     = Kit_TruthFindVarNum( pFileName );
    int nFuncs    = nFileSize / 4 / Abc_TruthWordNum(nVars);
    unsigned * pA = (unsigned *)Extra_FileReadContents( pFileName );
    int * pResult = Kit_TruthStatsArray( pA, nVars, nFuncs );
    printf( "Finished proceessing %d functions with %d variables. ", nFuncs, nVars );
    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
    ABC_FREE( pA );
    for ( i = 0; i < 5; i++ )
        printf( "Function %3d :  AND2 = %3d  Lev = %3d\n", i, pResult[i] & 0xFFFF, pResult[i] >> 16 );
    return pResult;
}

Here is the call graph for this function:

Kit_TruthToGraph()

Kit_Graph_t * Kit_TruthToGraph	(	unsigned *	pTruth,
		int	nVars,
		Vec_Int_t *	vMemory )

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

Synopsis [Derives the factored form from the truth table.]

Description []

SideEffects []

SeeAlso []

Definition at line 356 of file kitGraph.c.

{
    Kit_Graph_t * pGraph;
    int RetValue;
    // derive SOP
    RetValue = Kit_TruthIsop( pTruth, nVars, vMemory, 1 ); // tried 1 and found not useful in "renode"
    if ( RetValue == -1 )
        return NULL;
    if ( Vec_IntSize(vMemory) > (1<<16) )
        return NULL;
//    printf( "Isop size = %d.\n", Vec_IntSize(vMemory) );
    assert( RetValue == 0 || RetValue == 1 );
    // derive factored form
    pGraph = Kit_SopFactor( vMemory, RetValue, nVars, vMemory );
    return pGraph;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Kit_TruthToGraph2()

Kit_Graph_t * Kit_TruthToGraph2	(	unsigned *	pTruth0,
		unsigned *	pTruth1,
		int	nVars,
		Vec_Int_t *	vMemory )

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

Synopsis [Derives the factored form from the truth table.]

Description []

SideEffects []

SeeAlso []

Definition at line 384 of file kitGraph.c.

{
    Kit_Graph_t * pGraph;
    int RetValue;
    // derive SOP
    RetValue = Kit_TruthIsop2( pTruth0, pTruth1, nVars, vMemory, 0, 0 ); // tried 1 and found not useful in "renode"
    if ( RetValue == -1 )
        return NULL;
    if ( Vec_IntSize(vMemory) > (1<<16) )
        return NULL;
//    printf( "Isop size = %d.\n", Vec_IntSize(vMemory) );
    assert( RetValue == 0 || RetValue == 1 );
    // derive factored form
    pGraph = Kit_SopFactor( vMemory, RetValue, nVars, vMemory );
    return pGraph;
}

Here is the call graph for this function:

Here is the caller graph for this function: