src/aig/kit/kitGraph.c File Reference

#include "kit.h"
Include dependency graph for kitGraph.c:

Go to the source code of this file.

Functions

Kit_Graph_t * Kit_GraphCreate (int nLeaves)
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)
int Kit_GraphLeafDepth_rec (Kit_Graph_t *pGraph, Kit_Node_t *pNode, Kit_Node_t *pLeaf)

Function Documentation

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 169 of file kitGraph.c.

00170 {
00171     Kit_Node_t * pNode;
00172     // get the new node
00173     pNode = Kit_GraphAppendNode( pGraph );
00174     // set the inputs and other info
00175     pNode->eEdge0 = eEdge0;
00176     pNode->eEdge1 = eEdge1;
00177     pNode->fCompl0 = eEdge0.fCompl;
00178     pNode->fCompl1 = eEdge1.fCompl;
00179     return Kit_EdgeCreate( pGraph->nSize - 1, 0 );
00180 }

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 262 of file kitGraph.c.

00263 {
00264     Kit_Edge_t eNode0, eNode1, eNode;
00265     if ( Type == 0 )
00266     {
00267         // derive the first AND
00268         eNode0 = Kit_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeT );
00269         // derive the second AND
00270         eEdgeC.fCompl ^= 1;
00271         eNode1 = Kit_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeE );
00272         // derive the final OR
00273         eNode = Kit_GraphAddNodeOr( pGraph, eNode0, eNode1 );
00274     }
00275     else
00276     {
00277         // complement the arguments
00278         eEdgeT.fCompl ^= 1;
00279         eEdgeE.fCompl ^= 1;
00280         // derive the first AND
00281         eNode0 = Kit_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeT );
00282         // derive the second AND
00283         eEdgeC.fCompl ^= 1;
00284         eNode1 = Kit_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeE );
00285         // derive the final OR
00286         eNode = Kit_GraphAddNodeOr( pGraph, eNode0, eNode1 );
00287         eNode.fCompl ^= 1;
00288     }
00289     return eNode;
00290 }

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 193 of file kitGraph.c.

00194 {
00195     Kit_Node_t * pNode;
00196     // get the new node
00197     pNode = Kit_GraphAppendNode( pGraph );
00198     // set the inputs and other info
00199     pNode->eEdge0 = eEdge0;
00200     pNode->eEdge1 = eEdge1;
00201     pNode->fCompl0 = eEdge0.fCompl;
00202     pNode->fCompl1 = eEdge1.fCompl;
00203     // make adjustments for the OR gate
00204     pNode->fNodeOr = 1;
00205     pNode->eEdge0.fCompl = !pNode->eEdge0.fCompl;
00206     pNode->eEdge1.fCompl = !pNode->eEdge1.fCompl;
00207     return Kit_EdgeCreate( pGraph->nSize - 1, 1 );
00208 }

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 221 of file kitGraph.c.

00222 {
00223     Kit_Edge_t eNode0, eNode1, eNode;
00224     if ( Type == 0 )
00225     {
00226         // derive the first AND
00227         eEdge0.fCompl ^= 1;
00228         eNode0 = Kit_GraphAddNodeAnd( pGraph, eEdge0, eEdge1 );
00229         eEdge0.fCompl ^= 1;
00230         // derive the second AND
00231         eEdge1.fCompl ^= 1;
00232         eNode1 = Kit_GraphAddNodeAnd( pGraph, eEdge0, eEdge1 );
00233         // derive the final OR
00234         eNode = Kit_GraphAddNodeOr( pGraph, eNode0, eNode1 );
00235     }
00236     else
00237     {
00238         // derive the first AND
00239         eNode0 = Kit_GraphAddNodeAnd( pGraph, eEdge0, eEdge1 );
00240         // derive the second AND
00241         eEdge0.fCompl ^= 1;
00242         eEdge1.fCompl ^= 1;
00243         eNode1 = Kit_GraphAddNodeAnd( pGraph, eEdge0, eEdge1 );
00244         // derive the final OR
00245         eNode = Kit_GraphAddNodeOr( pGraph, eNode0, eNode1 );
00246         eNode.fCompl ^= 1;
00247     }
00248     return eNode;
00249 }

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 145 of file kitGraph.c.

00146 {
00147     Kit_Node_t * pNode;
00148     if ( pGraph->nSize == pGraph->nCap )
00149     {
00150         pGraph->pNodes = REALLOC( Kit_Node_t, pGraph->pNodes, 2 * pGraph->nCap ); 
00151         pGraph->nCap   = 2 * pGraph->nCap;
00152     }
00153     pNode = pGraph->pNodes + pGraph->nSize++;
00154     memset( pNode, 0, sizeof(Kit_Node_t) );
00155     return pNode;
00156 }

Kit_Graph_t* Kit_GraphCreate ( int  nLeaves  ) 

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

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 42 of file kitGraph.c.

00043 {
00044     Kit_Graph_t * pGraph;
00045     pGraph = ALLOC( Kit_Graph_t, 1 );
00046     memset( pGraph, 0, sizeof(Kit_Graph_t) );
00047     pGraph->nLeaves = nLeaves;
00048     pGraph->nSize = nLeaves;
00049     pGraph->nCap = 2 * nLeaves + 50;
00050     pGraph->pNodes = ALLOC( Kit_Node_t, pGraph->nCap );
00051     memset( pGraph->pNodes, 0, sizeof(Kit_Node_t) * pGraph->nSize );
00052     return pGraph;
00053 }

Kit_Graph_t* Kit_GraphCreateConst0 (  ) 

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

Synopsis [Creates constant 0 graph.]

Description []

SideEffects []

SeeAlso []

Definition at line 66 of file kitGraph.c.

00067 {
00068     Kit_Graph_t * pGraph;
00069     pGraph = ALLOC( Kit_Graph_t, 1 );
00070     memset( pGraph, 0, sizeof(Kit_Graph_t) );
00071     pGraph->fConst = 1;
00072     pGraph->eRoot.fCompl = 1;
00073     return pGraph;
00074 }

Kit_Graph_t* Kit_GraphCreateConst1 (  ) 

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

Synopsis [Creates constant 1 graph.]

Description []

SideEffects []

SeeAlso []

Definition at line 87 of file kitGraph.c.

00088 {
00089     Kit_Graph_t * pGraph;
00090     pGraph = ALLOC( Kit_Graph_t, 1 );
00091     memset( pGraph, 0, sizeof(Kit_Graph_t) );
00092     pGraph->fConst = 1;
00093     return pGraph;
00094 }

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

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

Synopsis [Creates the literal graph.]

Description []

SideEffects []

SeeAlso []

Definition at line 107 of file kitGraph.c.

00108 {
00109     Kit_Graph_t * pGraph;
00110     assert( 0 <= iLeaf && iLeaf < nLeaves );
00111     pGraph = Kit_GraphCreate( nLeaves );
00112     pGraph->eRoot.Node   = iLeaf;
00113     pGraph->eRoot.fCompl = fCompl;
00114     return pGraph;
00115 }

void Kit_GraphFree ( Kit_Graph_t *  pGraph  ) 

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 128 of file kitGraph.c.

00129 {
00130     FREE( pGraph->pNodes );
00131     free( pGraph );
00132 }

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 380 of file kitGraph.c.

00381 {
00382     int Depth0, Depth1, Depth;
00383     if ( pNode == pLeaf )
00384         return 0;
00385     if ( Kit_GraphNodeIsVar(pGraph, pNode) )
00386         return -100;
00387     Depth0 = Kit_GraphLeafDepth_rec( pGraph, Kit_GraphNodeFanin0(pGraph, pNode), pLeaf );
00388     Depth1 = Kit_GraphLeafDepth_rec( pGraph, Kit_GraphNodeFanin1(pGraph, pNode), pLeaf );
00389     Depth = KIT_MAX( Depth0, Depth1 );
00390     Depth = (Depth == -100) ? -100 : Depth + 1;
00391     return Depth;
00392 }

unsigned Kit_GraphToTruth ( Kit_Graph_t *  pGraph  ) 

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

Synopsis [Derives the truth table.]

Description []

SideEffects []

SeeAlso []

Definition at line 303 of file kitGraph.c.

00304 {
00305     unsigned uTruths[5] = { 0xAAAAAAAA, 0xCCCCCCCC, 0xF0F0F0F0, 0xFF00FF00, 0xFFFF0000 };
00306     unsigned uTruth = 0, uTruth0, uTruth1;
00307     Kit_Node_t * pNode;
00308     int i;
00309 
00310     // sanity checks
00311     assert( Kit_GraphLeaveNum(pGraph) >= 0 );
00312     assert( Kit_GraphLeaveNum(pGraph) <= pGraph->nSize );
00313     assert( Kit_GraphLeaveNum(pGraph) <= 5 );
00314 
00315     // check for constant function
00316     if ( Kit_GraphIsConst(pGraph) )
00317         return Kit_GraphIsComplement(pGraph)? 0 : ~((unsigned)0);
00318     // check for a literal
00319     if ( Kit_GraphIsVar(pGraph) )
00320         return Kit_GraphIsComplement(pGraph)? ~uTruths[Kit_GraphVarInt(pGraph)] : uTruths[Kit_GraphVarInt(pGraph)];
00321 
00322     // assign the elementary variables
00323     Kit_GraphForEachLeaf( pGraph, pNode, i )
00324         pNode->pFunc = (void *)(long)uTruths[i];
00325 
00326     // compute the function for each internal node
00327     Kit_GraphForEachNode( pGraph, pNode, i )
00328     {
00329         uTruth0 = (unsigned)(long)Kit_GraphNode(pGraph, pNode->eEdge0.Node)->pFunc;
00330         uTruth1 = (unsigned)(long)Kit_GraphNode(pGraph, pNode->eEdge1.Node)->pFunc;
00331         uTruth0 = pNode->eEdge0.fCompl? ~uTruth0 : uTruth0;
00332         uTruth1 = pNode->eEdge1.fCompl? ~uTruth1 : uTruth1;
00333         uTruth = uTruth0 & uTruth1;
00334         pNode->pFunc = (void *)(long)uTruth;
00335     }
00336 
00337     // complement the result if necessary
00338     return Kit_GraphIsComplement(pGraph)? ~uTruth : uTruth;
00339 }

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 352 of file kitGraph.c.

00353 {
00354     Kit_Graph_t * pGraph;
00355     int RetValue;
00356     // derive SOP
00357     RetValue = Kit_TruthIsop( pTruth, nVars, vMemory, 1 ); // tried 1 and found not useful in "renode"
00358     if ( RetValue == -1 )
00359         return NULL;
00360     if ( Vec_IntSize(vMemory) > 128 )
00361         return NULL;
00362 //    printf( "Isop size = %d.\n", Vec_IntSize(vMemory) );
00363     assert( RetValue == 0 || RetValue == 1 );
00364     // derive factored form
00365     pGraph = Kit_SopFactor( vMemory, RetValue, nVars, vMemory );
00366     return pGraph;
00367 }

Generated on Tue Jan 5 12:18:28 2010 for abc70930 by  doxygen 1.6.1