summaryrefslogtreecommitdiffstats
path: root/src/bool/kit/kitGraph.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/bool/kit/kitGraph.c')
-rw-r--r--src/bool/kit/kitGraph.c402
1 files changed, 402 insertions, 0 deletions
diff --git a/src/bool/kit/kitGraph.c b/src/bool/kit/kitGraph.c
new file mode 100644
index 00000000..e4eea885
--- /dev/null
+++ b/src/bool/kit/kitGraph.c
@@ -0,0 +1,402 @@
+/**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
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-06-30 19:08:25 +0000