diff options
author | Alan Mishchenko <alanmi@berkeley.edu> | 2006-12-06 08:01:00 -0800 |
---|---|---|
committer | Alan Mishchenko <alanmi@berkeley.edu> | 2006-12-06 08:01:00 -0800 |
commit | 4cf99cae95c629b31d6d89c5dcea2eeb17654c85 (patch) | |
tree | dd5984cdf1b9332b800921fd89cf190aa2c4d8d9 /src/opt/kit/kitGraph.c | |
parent | 38254947a57b9899909d8fbabfbf784690ed5a68 (diff) | |
download | abc-4cf99cae95c629b31d6d89c5dcea2eeb17654c85.tar.gz abc-4cf99cae95c629b31d6d89c5dcea2eeb17654c85.tar.bz2 abc-4cf99cae95c629b31d6d89c5dcea2eeb17654c85.zip |
Version abc61206
Diffstat (limited to 'src/opt/kit/kitGraph.c')
-rw-r--r-- | src/opt/kit/kitGraph.c | 367 |
1 files changed, 367 insertions, 0 deletions
diff --git a/src/opt/kit/kitGraph.c b/src/opt/kit/kitGraph.c new file mode 100644 index 00000000..e2172ca3 --- /dev/null +++ b/src/opt/kit/kitGraph.c @@ -0,0 +1,367 @@ +/**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, 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 *)uTruths[i]; + + // compute the function for each internal node + Kit_GraphForEachNode( pGraph, pNode, i ) + { + uTruth0 = (unsigned)Kit_GraphNode(pGraph, pNode->eEdge0.Node)->pFunc; + uTruth1 = (unsigned)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 *)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, 0 ); + assert( RetValue == 0 ); + // derive factored form + pGraph = Kit_SopFactor( vMemory, 0, nVars, vMemory ); + return pGraph; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + |