| /**CFile**************************************************************** |
| Copyright (c) The Regents of the University of California. All rights reserved. |
| |
| Permission is hereby granted, without written agreement and without license or |
| royalty fees, to use, copy, modify, and distribute this software and its |
| documentation for any purpose, provided that the above copyright notice and |
| the following two paragraphs appear in all copies of this software. |
| |
| IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR |
| DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF |
| THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF |
| CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| |
| THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, |
| BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, |
| AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, |
| SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS. |
|
|
|
|
| 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.bits.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.bits.Node = iLeaf;
|
| pGraph->eRoot.bits.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.bits.fCompl;
|
| pNode->fCompl1 = eEdge1.bits.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.bits.fCompl;
|
| pNode->fCompl1 = eEdge1.bits.fCompl;
|
| // make adjustments for the OR gate
|
| pNode->fNodeOr = 1;
|
| pNode->eEdge0.bits.fCompl = !pNode->eEdge0.bits.fCompl;
|
| pNode->eEdge1.bits.fCompl = !pNode->eEdge1.bits.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.bits.fCompl ^= 1;
|
| eNode0 = Kit_GraphAddNodeAnd( pGraph, eEdge0, eEdge1 );
|
| eEdge0.bits.fCompl ^= 1;
|
| // derive the second AND
|
| eEdge1.bits.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.bits.fCompl ^= 1;
|
| eEdge1.bits.fCompl ^= 1;
|
| eNode1 = Kit_GraphAddNodeAnd( pGraph, eEdge0, eEdge1 );
|
| // derive the final OR
|
| eNode = Kit_GraphAddNodeOr( pGraph, eNode0, eNode1 );
|
| eNode.bits.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.bits.fCompl ^= 1;
|
| eNode1 = Kit_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeE );
|
| // derive the final OR
|
| eNode = Kit_GraphAddNodeOr( pGraph, eNode0, eNode1 );
|
| }
|
| else
|
| {
|
| // complement the arguments
|
| eEdgeT.bits.fCompl ^= 1;
|
| eEdgeE.bits.fCompl ^= 1;
|
| // derive the first AND
|
| eNode0 = Kit_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeT );
|
| // derive the second AND
|
| eEdgeC.bits.fCompl ^= 1;
|
| eNode1 = Kit_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeE );
|
| // derive the final OR
|
| eNode = Kit_GraphAddNodeOr( pGraph, eNode0, eNode1 );
|
| eNode.bits.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.bits.Node)->pFunc;
|
| uTruth1 = (unsigned)(long)Kit_GraphNode(pGraph, pNode->eEdge1.bits.Node)->pFunc;
|
| uTruth0 = pNode->eEdge0.bits.fCompl? ~uTruth0 : uTruth0;
|
| uTruth1 = pNode->eEdge1.bits.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 []
|
|
|
| ***********************************************************************/
|
| #if 0
|
| 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;
|
| }
|
| #endif
|
|
|
| /**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 ///
|
| ////////////////////////////////////////////////////////////////////////
|
|
|
