Version abc71001

1 files changed, 397 insertions, 0 deletions

diff --git a/src/aig/kit/kitGraph.c b/src/aig/kit/kitGraph.c
new file mode 100644
index 00000000..80dcbdc0
--- /dev/null
+++ b/src/aig/kit/kitGraph.c
@@ -0,0 +1,397 @@
+/**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"
+
+////////////////////////////////////////////////////////////////////////
+///                        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 = 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 = 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 = 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 = 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 )   
+{
+    FREE( pGraph->pNodes );
+    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 = 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) > 128 )
+        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                                ///
+////////////////////////////////////////////////////////////////////////
+