abc70930: src/aig/kit/kitGraph.c Source File

00001 
00021 #include "kit.h"
00022 
00026 
00030 
00042 Kit_Graph_t * Kit_GraphCreate( int nLeaves )   
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 }
00054 
00066 Kit_Graph_t * Kit_GraphCreateConst0()   
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 }
00075 
00087 Kit_Graph_t * Kit_GraphCreateConst1()   
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 }
00095 
00107 Kit_Graph_t * Kit_GraphCreateLeaf( int iLeaf, int nLeaves, int fCompl )   
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 }
00116 
00128 void Kit_GraphFree( Kit_Graph_t * pGraph )   
00129 {
00130     FREE( pGraph->pNodes );
00131     free( pGraph );
00132 }
00133 
00145 Kit_Node_t * Kit_GraphAppendNode( Kit_Graph_t * pGraph )   
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 }
00157 
00169 Kit_Edge_t Kit_GraphAddNodeAnd( Kit_Graph_t * pGraph, Kit_Edge_t eEdge0, Kit_Edge_t eEdge1 )
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 }
00181 
00193 Kit_Edge_t Kit_GraphAddNodeOr( Kit_Graph_t * pGraph, Kit_Edge_t eEdge0, Kit_Edge_t eEdge1 )
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 }
00209 
00221 Kit_Edge_t Kit_GraphAddNodeXor( Kit_Graph_t * pGraph, Kit_Edge_t eEdge0, Kit_Edge_t eEdge1, int Type )
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 }
00250 
00262 Kit_Edge_t Kit_GraphAddNodeMux( Kit_Graph_t * pGraph, Kit_Edge_t eEdgeC, Kit_Edge_t eEdgeT, Kit_Edge_t eEdgeE, int Type )
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 }
00291 
00303 unsigned Kit_GraphToTruth( Kit_Graph_t * pGraph )
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 }
00340 
00352 Kit_Graph_t * Kit_TruthToGraph( unsigned * pTruth, int nVars, Vec_Int_t * vMemory )
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 }
00368 
00380 int Kit_GraphLeafDepth_rec( Kit_Graph_t * pGraph, Kit_Node_t * pNode, Kit_Node_t * pLeaf )
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 }
00393 
00397