/**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 $] ***********************************************************************/ #include "kit.h" ABC_NAMESPACE_IMPL_START //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* Synopsis [Creates a graph with the given number of leaves.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Kit_Graph_t * Kit_GraphCreate( int nLeaves ) { 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; } /**Function************************************************************* Synopsis [Creates constant 0 graph.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Kit_Graph_t * Kit_GraphCreateConst0() { 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; } /**Function************************************************************* Synopsis [Creates constant 1 graph.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Kit_Graph_t * Kit_GraphCreateConst1() { Kit_Graph_t * pGraph; pGraph = ABC_ALLOC( Kit_Graph_t, 1 ); memset( pGraph, 0, sizeof(Kit_Graph_t) ); pGraph->fConst = 1; return pGraph; } /**Function************************************************************* Synopsis [Creates the literal graph.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Kit_Graph_t * Kit_GraphCreateLeaf( int iLeaf, int nLeaves, int fCompl ) { Kit_Graph_t * pGraph; assert( 0 <= iLeaf && iLeaf < nLeaves ); pGraph = Kit_GraphCreate( nLeaves ); pGraph->eRoot.Node = iLeaf; pGraph->eRoot.fCompl = fCompl; return pGraph; } /**Function************************************************************* Synopsis [Creates a graph with the given number of leaves.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Kit_GraphFree( Kit_Graph_t * pGraph ) { ABC_FREE( pGraph->pNodes ); ABC_FREE( pGraph ); } /**Function************************************************************* Synopsis [Appends a new node to the graph.] Description [This procedure is meant for internal use.] SideEffects [] SeeAlso [] ***********************************************************************/ Kit_Node_t * Kit_GraphAppendNode( Kit_Graph_t * pGraph ) { 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; } /**Function************************************************************* Synopsis [Creates an AND node.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Kit_Edge_t Kit_GraphAddNodeAnd( Kit_Graph_t * pGraph, Kit_Edge_t eEdge0, Kit_Edge_t eEdge1 ) { 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 ); } /**Function************************************************************* Synopsis [Creates an OR node.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Kit_Edge_t Kit_GraphAddNodeOr( Kit_Graph_t * pGraph, Kit_Edge_t eEdge0, Kit_Edge_t eEdge1 ) { 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 ); } /**Function************************************************************* Synopsis [Creates an XOR node.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Kit_Edge_t Kit_GraphAddNodeXor( Kit_Graph_t * pGraph, Kit_Edge_t eEdge0, Kit_Edge_t eEdge1, int Type ) { 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; } /**Function************************************************************* Synopsis [Creates an XOR node.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Kit_Edge_t Kit_GraphAddNodeMux( Kit_Graph_t * pGraph, Kit_Edge_t eEdgeC, Kit_Edge_t eEdgeT, Kit_Edge_t eEdgeE, int Type ) { 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; } /**Function************************************************************* Synopsis [Derives the truth table.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ unsigned Kit_GraphToTruth( Kit_Graph_t * pGraph ) { 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; } /**Function************************************************************* Synopsis [Derives the factored form from the truth table.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Kit_Graph_t * Kit_TruthToGraph( unsigned * pTruth, int nVars, Vec_Int_t * vMemory ) { 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; } /**Function************************************************************* Synopsis [Derives the maximum depth from the leaf to the root.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Kit_GraphLeafDepth_rec( Kit_Graph_t * pGraph, Kit_Node_t * pNode, Kit_Node_t * pLeaf ) { 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; } //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// ABC_NAMESPACE_IMPL_END