text: /**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"
  #include "misc/extra/extra.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 factored form from the truth table.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  Kit_Graph_t * Kit_TruthToGraph2( unsigned * pTruth0, unsigned * pTruth1, int nVars, Vec_Int_t * vMemory )
  {
      Kit_Graph_t * pGraph;
      int RetValue;
      // derive SOP
      RetValue = Kit_TruthIsop2( pTruth0, pTruth1, nVars, vMemory, 0, 0 ); // 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;
  }
  
  /**Function*************************************************************
  
    Synopsis    [Derives logic level of the node.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  int Kit_GraphLevelNum_rec( Kit_Graph_t * pGraph, Kit_Node_t * pNode )
  {
      int Depth0, Depth1;
      if ( Kit_GraphNodeIsVar(pGraph, pNode) )
          return 0;
      Depth0 = Kit_GraphLevelNum_rec( pGraph, Kit_GraphNodeFanin0(pGraph, pNode) );
      Depth1 = Kit_GraphLevelNum_rec( pGraph, Kit_GraphNodeFanin1(pGraph, pNode) );
      return 1 + KIT_MAX( Depth0, Depth1 );
  }
  
  /**Function*************************************************************
  
    Synopsis    [Returns FF nodes and levels.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  int Kit_TruthStats( unsigned * pTruth, int nVars, Vec_Int_t * vMemory )
  {
      Kit_Graph_t * pGraph = Kit_TruthToGraph( pTruth, nVars, vMemory );
      int nNodes  = Kit_GraphNodeNum( pGraph );
      int nLevels = Kit_GraphLevelNum_rec( pGraph, Kit_GraphNodeLast(pGraph) );
      Kit_GraphFree( pGraph );
      return (nLevels << 16) | nNodes;
  }
  int * Kit_TruthStatsArray( unsigned * pArray, int nVars, int nFuncs )
  {
      int f, * pRes = ABC_CALLOC( int, nFuncs );
      int nInts = Abc_TruthWordNum( nVars );
      Vec_Int_t * vMemory = Vec_IntAlloc( 1 << 16 );
      for ( f = 0; f < nFuncs; f++ )
          pRes[f] = Kit_TruthStats( pArray + f*nInts, nVars, vMemory );
      Vec_IntFree( vMemory );
      return pRes;
  }
  int Kit_TruthFindVarNum( char * pFileName )
  {
      int i;
      for ( i = 0; i < (int)strlen(pFileName); i++ )
          if ( pFileName[i] >= '0' && pFileName[i] <= '9' )
              return atoi(pFileName+i);
      return -1;
  }
  int * Kit_TruthTest( char * pFileName )
  {
      abctime clk   = Abc_Clock(); int i;
      int nFileSize = Extra_FileSize( pFileName );
      int nVars     = Kit_TruthFindVarNum( pFileName );
      int nFuncs    = nFileSize / 4 / Abc_TruthWordNum(nVars);
      unsigned * pA = (unsigned *)Extra_FileReadContents( pFileName );
      int * pResult = Kit_TruthStatsArray( pA, nVars, nFuncs );
      printf( "Finished proceessing %d functions with %d variables. ", nFuncs, nVars );
      Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
      ABC_FREE( pA );
      for ( i = 0; i < 5; i++ )
          printf( "Function %3d :  AND2 = %3d  Lev = %3d\n", i, pResult[i] & 0xFFFF, pResult[i] >> 16 );
      return pResult;
  }
  
  /**Function*************************************************************
  
    Synopsis    [Derives the factored form from the truth table.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  int Kit_TruthLitNum( unsigned * pTruth, int nVars, Vec_Int_t * vMemory )
  {
      Kit_Graph_t * pGraph;
      int RetValue, nLits;
      RetValue = Kit_TruthIsop( pTruth, nVars, vMemory, 1 ); 
      if ( RetValue == -1 || Vec_IntSize(vMemory) > (1<<16) )
          return -1;
      assert( RetValue == 0 || RetValue == 1 );
      pGraph = Kit_SopFactor( vMemory, RetValue, nVars, vMemory );
      nLits = 1 + Kit_GraphNodeNum( pGraph );
      Kit_GraphFree( pGraph );
      return nLits;
  }
  
  ////////////////////////////////////////////////////////////////////////
  ///                       END OF FILE                                ///
  ////////////////////////////////////////////////////////////////////////
  
  ABC_NAMESPACE_IMPL_END
  
  