text: /**CFile****************************************************************
  
    FileName    [abcLut.c]
  
    SystemName  [ABC: Logic synthesis and verification system.]
  
    PackageName [Network and node package.]
  
    Synopsis    [Superchoicing for K-LUTs.]
  
    Author      [Alan Mishchenko]
    
    Affiliation [UC Berkeley]
  
    Date        [Ver. 1.0. Started - June 20, 2005.]
  
    Revision    [$Id: abcLut.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
  
  ***********************************************************************/
  
  #include "base/abc/abc.h"
  #include "opt/cut/cut.h"
  
  ABC_NAMESPACE_IMPL_START
  
  #define LARGE_LEVEL 1000000
  
  ////////////////////////////////////////////////////////////////////////
  ///                        DECLARATIONS                              ///
  ////////////////////////////////////////////////////////////////////////
  
  #define SCL_LUT_MAX          6   // the maximum LUT size
  #define SCL_VARS_MAX        15   // the maximum number of variables
  #define SCL_NODE_MAX      1000   // the maximum number of nodes
  
  typedef struct Abc_ManScl_t_ Abc_ManScl_t;
  struct Abc_ManScl_t_
  {
      // paramers
      int                nLutSize;    // the LUT size
      int                nCutSizeMax; // the max number of leaves of the cone
      int                nNodesMax;   // the max number of divisors in the cone
      int                nWords;      // the number of machine words in sim info
      // structural representation of the cone
      Vec_Ptr_t *        vLeaves;     // leaves of the cut
      Vec_Ptr_t *        vVolume;     // volume of the cut
      int                pBSet[SCL_VARS_MAX]; // bound set
      // functional representation of the cone
      unsigned *         uTruth;      // truth table of the cone
      // representation of truth tables
      unsigned **        uVars;       // elementary truth tables
      unsigned **        uSims;       // truth tables of the nodes
      unsigned **        uCofs;       // truth tables of the cofactors
  };
  
  static Vec_Ptr_t * s_pLeaves = NULL;
  
  static Cut_Man_t * Abc_NtkStartCutManForScl( Abc_Ntk_t * pNtk, int nLutSize );
  static Abc_ManScl_t * Abc_ManSclStart( int nLutSize, int nCutSizeMax, int nNodesMax );
  static void Abc_ManSclStop( Abc_ManScl_t * p );
  static void Abc_NodeLutMap( Cut_Man_t * pManCuts, Abc_Obj_t * pObj );
  
  static Abc_Obj_t * Abc_NodeSuperChoiceLut( Abc_ManScl_t * pManScl, Abc_Obj_t * pObj );
  static int Abc_NodeDecomposeStep( Abc_ManScl_t * pManScl );
  
  ////////////////////////////////////////////////////////////////////////
  ///                     FUNCTION DEFINITIONS                         ///
  ////////////////////////////////////////////////////////////////////////
  
  /**Function*************************************************************
  
    Synopsis    [Performs superchoicing for K-LUTs.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  int Abc_NtkSuperChoiceLut( Abc_Ntk_t * pNtk, int nLutSize, int nCutSizeMax, int fVerbose )
  {
      ProgressBar * pProgress;
      Abc_ManCut_t * pManCut;
      Abc_ManScl_t * pManScl;
      Cut_Man_t * pManCuts;
      Abc_Obj_t * pObj, * pFanin, * pObjTop;
      int i, LevelMax, nNodes;
      int nNodesTried, nNodesDec, nNodesExist, nNodesUsed;
  
      assert( Abc_NtkIsSopLogic(pNtk) );
      if ( nLutSize < 3 || nLutSize > SCL_LUT_MAX )
      {
          printf( "LUT size (%d) does not belong to the interval: 3 <= LUT size <= %d\n", nLutSize, SCL_LUT_MAX );
          return 0;
      }
      if ( nCutSizeMax <= nLutSize || nCutSizeMax > SCL_VARS_MAX )
      {
          printf( "Cut size (%d) does not belong to the interval: LUT size (%d) < Cut size <= %d\n", nCutSizeMax, nLutSize, SCL_VARS_MAX );
          return 0;
      }
  
      assert( nLutSize <= SCL_LUT_MAX );
      assert( nCutSizeMax <= SCL_VARS_MAX );
      nNodesTried = nNodesDec = nNodesExist = nNodesUsed = 0;
  
      // set the delays of the CIs
      Abc_NtkForEachCi( pNtk, pObj, i )
          pObj->Level = 0;
  
  //Abc_NtkLevel( pNtk );
   
      // start the managers
      pManScl = Abc_ManSclStart( nLutSize, nCutSizeMax, 1000 );
      pManCuts = Abc_NtkStartCutManForScl( pNtk, nLutSize );
      pManCut = Abc_NtkManCutStart( nCutSizeMax, 100000, 100000, 100000 );
      s_pLeaves = Abc_NtkManCutReadCutSmall( pManCut );
      pManScl->vVolume = Abc_NtkManCutReadVisited( pManCut );
  
      // process each internal node (assuming topological order of nodes!!!)
      nNodes = Abc_NtkObjNumMax(pNtk);
      pProgress = Extra_ProgressBarStart( stdout, nNodes );
      Abc_NtkForEachObj( pNtk, pObj, i )
      {
  //        if ( i != nNodes-1 )
  //            continue;
          Extra_ProgressBarUpdate( pProgress, i, NULL );
          if ( i >= nNodes )
              break;
          if ( Abc_ObjFaninNum(pObj) != 2 )
              continue;
          nNodesTried++;
  
          // map this node using regular cuts
  //        pObj->Level = 0;
          Abc_NodeLutMap( pManCuts, pObj );
          // compute the cut
          pManScl->vLeaves = Abc_NodeFindCut( pManCut, pObj, 0 );
          if ( Vec_PtrSize(pManScl->vLeaves) <= nLutSize )
              continue;
          // get the volume of the cut
          if ( Vec_PtrSize(pManScl->vVolume) > SCL_NODE_MAX )
              continue;
          nNodesDec++;
  
          // decompose the cut
          pObjTop = Abc_NodeSuperChoiceLut( pManScl, pObj );
          if ( pObjTop == NULL )
              continue;
          nNodesExist++;
  
          // if there is no delay improvement, skip; otherwise, update level
          if ( pObjTop->Level >= pObj->Level )
          {
              Abc_NtkDeleteObj_rec( pObjTop, 1 );
              continue;
          }
          pObj->Level = pObjTop->Level;
          nNodesUsed++;
      }
      Extra_ProgressBarStop( pProgress );
  
      // delete the managers
      Abc_ManSclStop( pManScl );
      Abc_NtkManCutStop( pManCut );
      Cut_ManStop( pManCuts );
  
      // get the largest arrival time
      LevelMax = 0;
      Abc_NtkForEachCo( pNtk, pObj, i )
      {
          pFanin = Abc_ObjFanin0( pObj );
          // skip inv/buf
          if ( Abc_ObjFaninNum(pFanin) == 1 )
              pFanin = Abc_ObjFanin0( pFanin );
          // get the new level
          LevelMax = Abc_MaxInt( LevelMax, (int)pFanin->Level );
      }
  
      if ( fVerbose )
      printf( "Try = %d. Dec = %d. Exist = %d. Use = %d. SUPER = %d levels of %d-LUTs.\n", 
          nNodesTried, nNodesDec, nNodesExist, nNodesUsed, LevelMax, nLutSize );
  //    if ( fVerbose )
  //    printf( "The network is superchoiced for %d levels of %d-LUTs.\n", LevelMax, nLutSize );
  
      // clean the data field
      Abc_NtkForEachObj( pNtk, pObj, i )
          pObj->pNext = NULL;
  
      // check
      if ( !Abc_NtkCheck( pNtk ) )
      {
          printf( "Abc_NtkSuperChoiceLut: The network check has failed.\n" );
          return 0;
      }
      return 1;
  }
  
  /**Function*************************************************************
  
    Synopsis    [Performs LUT mapping of the node.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  void Abc_NodeLutMap( Cut_Man_t * pManCuts, Abc_Obj_t * pObj )
  {
      Cut_Cut_t * pCut;
      Abc_Obj_t * pFanin;
      int i, DelayMax;
      pCut = (Cut_Cut_t *)Abc_NodeGetCutsRecursive( pManCuts, pObj, 0, 0 );
      assert( pCut != NULL );
      assert( pObj->Level == 0 );
      // go through the cuts
      pObj->Level = LARGE_LEVEL;
      for ( pCut = pCut->pNext; pCut; pCut = pCut->pNext )
      {
          DelayMax = 0;
          for ( i = 0; i < (int)pCut->nLeaves; i++ )
          {
              pFanin = Abc_NtkObj( pObj->pNtk, pCut->pLeaves[i] );
  //            assert( Abc_ObjIsCi(pFanin) || pFanin->Level > 0 ); // should hold if node ordering is topological
              if ( DelayMax < (int)pFanin->Level )
                  DelayMax = pFanin->Level;
          }
          if ( (int)pObj->Level > DelayMax )
              pObj->Level = DelayMax;
      }
      assert( pObj->Level < LARGE_LEVEL );
      pObj->Level++;
  //    printf( "%d(%d) ", pObj->Id, pObj->Level );
  }
  
  /**Function*************************************************************
  
    Synopsis    [Starts the cut manager for rewriting.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  Cut_Man_t * Abc_NtkStartCutManForScl( Abc_Ntk_t * pNtk, int nLutSize )
  {
      static Cut_Params_t Params, * pParams = &Params;
      Cut_Man_t * pManCut;
      Abc_Obj_t * pObj;
      int i;
      // start the cut manager
      memset( pParams, 0, sizeof(Cut_Params_t) );
      pParams->nVarsMax  = nLutSize; // the max cut size ("k" of the k-feasible cuts)
      pParams->nKeepMax  = 500;   // the max number of cuts kept at a node
      pParams->fTruth    = 0;     // compute truth tables
      pParams->fFilter   = 1;     // filter dominated cuts
      pParams->fSeq      = 0;     // compute sequential cuts
      pParams->fDrop     = 0;     // drop cuts on the fly
      pParams->fVerbose  = 0;     // the verbosiness flag
      pParams->nIdsMax   = Abc_NtkObjNumMax( pNtk );
      pManCut = Cut_ManStart( pParams );
      if ( pParams->fDrop )
          Cut_ManSetFanoutCounts( pManCut, Abc_NtkFanoutCounts(pNtk) );
      // set cuts for PIs
      Abc_NtkForEachCi( pNtk, pObj, i )
          if ( Abc_ObjFanoutNum(pObj) > 0 )
              Cut_NodeSetTriv( pManCut, pObj->Id );
      return pManCut;
  }
  
  /**Function*************************************************************
  
    Synopsis    [Starts the manager.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  Abc_ManScl_t * Abc_ManSclStart( int nLutSize, int nCutSizeMax, int nNodesMax )
  {
      Abc_ManScl_t * p;
      int i, k;
      assert( sizeof(unsigned) == 4 );
      p = ABC_ALLOC( Abc_ManScl_t, 1 );
      memset( p, 0, sizeof(Abc_ManScl_t) );
      p->nLutSize    = nLutSize;
      p->nCutSizeMax = nCutSizeMax;
      p->nNodesMax   = nNodesMax;
      p->nWords      = Extra_TruthWordNum(nCutSizeMax);
      // allocate simulation info
      p->uVars = (unsigned **)Extra_ArrayAlloc( nCutSizeMax, p->nWords, 4 );
      p->uSims = (unsigned **)Extra_ArrayAlloc( nNodesMax, p->nWords, 4 );
      p->uCofs = (unsigned **)Extra_ArrayAlloc( 2 << nLutSize, p->nWords, 4 );
      memset( p->uVars[0], 0, nCutSizeMax * p->nWords * 4 );
      // assign elementary truth tables
      for ( k = 0; k < p->nCutSizeMax; k++ )
          for ( i = 0; i < p->nWords * 32; i++ )
              if ( i & (1 << k) )
                  p->uVars[k][i>>5] |= (1 << (i&31));
      // other data structures
  //    p->vBound = Vec_IntAlloc( nCutSizeMax );
      return p;
  }
  
  /**Function*************************************************************
  
    Synopsis    [Stops the manager.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  void Abc_ManSclStop( Abc_ManScl_t * p )
  {
  //    Vec_IntFree( p->vBound );
      ABC_FREE( p->uVars );
      ABC_FREE( p->uSims );
      ABC_FREE( p->uCofs );
      ABC_FREE( p );
  }
  
  
  /**Function*************************************************************
  
    Synopsis    [Performs superchoicing for one node.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  unsigned * Abc_NodeSuperChoiceTruth( Abc_ManScl_t * pManScl )
  {
      Abc_Obj_t * pObj;
      unsigned * puData0, * puData1, * puData = NULL;
      char * pSop;
      int i, k;
      // set elementary truth tables
      Vec_PtrForEachEntry( Abc_Obj_t *, pManScl->vLeaves, pObj, i )
          pObj->pNext = (Abc_Obj_t *)pManScl->uVars[i];
      // compute truth tables for internal nodes
      Vec_PtrForEachEntry( Abc_Obj_t *, pManScl->vVolume, pObj, i )
      {
          // set storage for the node's simulation info
          pObj->pNext = (Abc_Obj_t *)pManScl->uSims[i];
          // get pointer to the simulation info
          puData  = (unsigned *)pObj->pNext;
          puData0 = (unsigned *)Abc_ObjFanin0(pObj)->pNext;
          puData1 = (unsigned *)Abc_ObjFanin1(pObj)->pNext;
          // simulate
          pSop = (char *)pObj->pData;
          if ( pSop[0] == '0' && pSop[1] == '0' )
              for ( k = 0; k < pManScl->nWords; k++ )
                  puData[k] = ~puData0[k] & ~puData1[k];
          else if ( pSop[0] == '0' )
              for ( k = 0; k < pManScl->nWords; k++ )
                  puData[k] = ~puData0[k] & puData1[k];
          else if ( pSop[1] == '0' )
              for ( k = 0; k < pManScl->nWords; k++ )
                  puData[k] = puData0[k] & ~puData1[k];
          else 
              for ( k = 0; k < pManScl->nWords; k++ )
                  puData[k] = puData0[k] & puData1[k];
      }
      return puData;
  }
  
  /**Function*************************************************************
  
    Synopsis    [Performs superchoicing for one node.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  void Abc_NodeSuperChoiceCollect2_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vVolume )
  {
      if ( pObj->fMarkC )
          return;
      pObj->fMarkC = 1;
      assert( Abc_ObjFaninNum(pObj) == 2 );
      Abc_NodeSuperChoiceCollect2_rec( Abc_ObjFanin0(pObj), vVolume );
      Abc_NodeSuperChoiceCollect2_rec( Abc_ObjFanin1(pObj), vVolume );
      Vec_PtrPush( vVolume, pObj );
  }
  
  /**Function*************************************************************
  
    Synopsis    [Performs superchoicing for one node.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  void Abc_NodeSuperChoiceCollect2( Abc_Obj_t * pRoot, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vVolume )
  {
      Abc_Obj_t * pObj;
      int i;
      Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
          pObj->fMarkC = 1;
      Vec_PtrClear( vVolume );
      Abc_NodeSuperChoiceCollect2_rec( pRoot, vVolume );
      Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
          pObj->fMarkC = 0;
      Vec_PtrForEachEntry( Abc_Obj_t *, vVolume, pObj, i )
          pObj->fMarkC = 0;
  }
  
  /**Function*************************************************************
  
    Synopsis    [Performs superchoicing for one node.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  void Abc_NodeSuperChoiceCollect_rec( Abc_Obj_t * pObj, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vVolume )
  {
      if ( pObj->fMarkB )
      {
          Vec_PtrPush( vLeaves, pObj );
          pObj->fMarkB = 0;
      }
      if ( pObj->fMarkC )
          return;
      pObj->fMarkC = 1;
      assert( Abc_ObjFaninNum(pObj) == 2 );
      Abc_NodeSuperChoiceCollect_rec( Abc_ObjFanin0(pObj), vLeaves, vVolume );
      Abc_NodeSuperChoiceCollect_rec( Abc_ObjFanin1(pObj), vLeaves, vVolume );
      Vec_PtrPush( vVolume, pObj );
  }
  
  /**Function*************************************************************
  
    Synopsis    [Performs superchoicing for one node.]
  
    Description [Orders the leaves topologically.]
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  void Abc_NodeSuperChoiceCollect( Abc_Obj_t * pRoot, Vec_Ptr_t * vLeaves, Vec_Ptr_t * vVolume )
  {
      Abc_Obj_t * pObj;
      int i, nLeaves;
      nLeaves = Vec_PtrSize(vLeaves);
      Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
          pObj->fMarkB = pObj->fMarkC = 1;
      Vec_PtrClear( vVolume );
      Vec_PtrClear( vLeaves );
      Abc_NodeSuperChoiceCollect_rec( pRoot, vLeaves, vVolume );
      assert( Vec_PtrSize(vLeaves) == nLeaves );
      Vec_PtrForEachEntry( Abc_Obj_t *, vLeaves, pObj, i )
          pObj->fMarkC = 0;
      Vec_PtrForEachEntry( Abc_Obj_t *, vVolume, pObj, i )
          pObj->fMarkC = 0;
  }
  
  /**Function*************************************************************
  
    Synopsis    [Performs superchoicing for one node.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  void Abc_NodeLeavesRemove( Vec_Ptr_t * vLeaves, unsigned uPhase, int nVars )
  {
      int i;
      for ( i = nVars - 1; i >= 0; i-- )
          if ( uPhase & (1 << i) )
              Vec_PtrRemove( vLeaves, Vec_PtrEntry(vLeaves, i) );
  }
  
  /**Function*************************************************************
  
    Synopsis    [Performs superchoicing for one node.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  int Abc_NodeGetLevel( Abc_Obj_t * pObj )
  {
      Abc_Obj_t * pFanin;
      int i, Level;
      Level = 0;
      Abc_ObjForEachFanin( pObj, pFanin, i )
          Level = Abc_MaxInt( Level, (int)pFanin->Level );
      return Level + 1;
  }
  
  /**Function*************************************************************
  
    Synopsis    [Performs superchoicing for one node.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  Abc_Obj_t * Abc_NodeSuperChoiceLut( Abc_ManScl_t * p, Abc_Obj_t * pObj )
  {
      Abc_Obj_t * pFanin, * pObjNew;
      int i, nVars, uSupport, nSuppVars;
      // collect the cone using DFS (excluding leaves)
      Abc_NodeSuperChoiceCollect2( pObj, p->vLeaves, p->vVolume );
      assert( Vec_PtrEntryLast(p->vVolume) == pObj );  
      // compute the truth table
      p->uTruth = Abc_NodeSuperChoiceTruth( p );
      // get the support of this truth table
      nVars = Vec_PtrSize(p->vLeaves);
      uSupport = Extra_TruthSupport(p->uTruth, nVars);
      nSuppVars = Extra_WordCountOnes(uSupport);
      assert( nSuppVars <= nVars );
      if ( nSuppVars == 0 )
      {
          pObj->Level = 0;
          return NULL;
      }
      if ( nSuppVars == 1 )
      {
          // find the variable
          for ( i = 0; i < nVars; i++ )
              if ( uSupport & (1 << i) )
                  break;
          assert( i < nVars );
          pFanin = (Abc_Obj_t *)Vec_PtrEntry( p->vLeaves, i );
          pObj->Level = pFanin->Level;
          return NULL;
      }
      // support-minimize the truth table
      if ( nSuppVars != nVars )
      {
          Extra_TruthShrink( p->uCofs[0], p->uTruth, nSuppVars, nVars, uSupport );
          Extra_TruthCopy( p->uTruth, p->uCofs[0], nVars );
          Abc_NodeLeavesRemove( p->vLeaves, ((1 << nVars) - 1) & ~uSupport, nVars );
      }
  //    return NULL;
      // decompose the truth table recursively
      while ( Vec_PtrSize(p->vLeaves) > p->nLutSize )
          if ( !Abc_NodeDecomposeStep( p ) )
          {
              Vec_PtrForEachEntry( Abc_Obj_t *, p->vLeaves, pFanin, i )
                  if ( Abc_ObjIsNode(pFanin) && Abc_ObjFanoutNum(pFanin) == 0 )
                      Abc_NtkDeleteObj_rec( pFanin, 1 );
              return NULL;
          }
      // create the topmost node
      pObjNew = Abc_NtkCreateNode( pObj->pNtk );
      Vec_PtrForEachEntry( Abc_Obj_t *, p->vLeaves, pFanin, i )
          Abc_ObjAddFanin( pObjNew, pFanin );
      // create the function
      pObjNew->pData = Abc_SopCreateFromTruth( (Mem_Flex_t *)pObj->pNtk->pManFunc, Vec_PtrSize(p->vLeaves), p->uTruth ); // need ISOP
      pObjNew->Level = Abc_NodeGetLevel( pObjNew );
      return pObjNew;
  }
  
  /**Function*************************************************************
  
    Synopsis    [Procedure used for sorting the nodes in increasing order of levels.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  int Abc_NodeCompareLevelsInc( int * pp1, int * pp2 )
  {
      Abc_Obj_t * pNode1, * pNode2;
      pNode1 = (Abc_Obj_t *)Vec_PtrEntry(s_pLeaves, *pp1);
      pNode2 = (Abc_Obj_t *)Vec_PtrEntry(s_pLeaves, *pp2);
      if ( pNode1->Level < pNode2->Level )
          return -1;
      if ( pNode1->Level > pNode2->Level ) 
          return 1;
      return 0; 
  }
  
  /**Function*************************************************************
  
    Synopsis    [Selects the earliest arriving nodes from the array.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  void Abc_NodeDecomposeSort( Abc_Obj_t ** pLeaves, int nVars, int * pBSet, int nLutSize )
  {
      Abc_Obj_t * pTemp[SCL_VARS_MAX];
      int i, k, kBest, LevelMin;
      assert( nLutSize < nVars );
      assert( nVars <= SCL_VARS_MAX );
      // copy nodes into the internal storage
  //    printf( "(" );
      for ( i = 0; i < nVars; i++ )
      {
          pTemp[i] = pLeaves[i];
  //        printf( " %d", pLeaves[i]->Level );
      }
  //    printf( " )\n" );
      // choose one node at a time
      for ( i = 0; i < nLutSize; i++ )
      {
          kBest = -1;
          LevelMin = LARGE_LEVEL;
          for ( k = 0; k < nVars; k++ )
              if ( pTemp[k] && LevelMin > (int)pTemp[k]->Level )
              {
                  LevelMin = pTemp[k]->Level;
                  kBest = k;
              }
          pBSet[i] = kBest;
          pTemp[kBest] = NULL;
      }
  }
  
  /**Function*************************************************************
  
    Synopsis    [Performs superchoicing for one node.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  int Abc_NodeDecomposeStep( Abc_ManScl_t * p )
  {
      static char pCofClasses[1<<SCL_LUT_MAX][1<<SCL_LUT_MAX];
      static char nCofClasses[1<<SCL_LUT_MAX];
      Abc_Ntk_t * pNtk;
      Abc_Obj_t * pObjNew, * pFanin, * pNodesNew[SCL_LUT_MAX];
      unsigned * pTruthCof, * pTruthClass, * pTruth, uPhase;
      int i, k, c, v, w, nVars, nVarsNew, nClasses, nCofs;
      // set the network
      pNtk = ((Abc_Obj_t *)Vec_PtrEntry(p->vLeaves, 0))->pNtk;
      // find the earliest nodes
      nVars = Vec_PtrSize(p->vLeaves);
      assert( nVars > p->nLutSize );
  /*
      for ( v = 0; v < nVars; v++ )
          p->pBSet[v] = v;
      qsort( (void *)p->pBSet, nVars, sizeof(int), 
              (int (*)(const void *, const void *)) Abc_NodeCompareLevelsInc );
  */
      Abc_NodeDecomposeSort( (Abc_Obj_t **)Vec_PtrArray(p->vLeaves), Vec_PtrSize(p->vLeaves), p->pBSet, p->nLutSize );
      assert( ((Abc_Obj_t *)Vec_PtrEntry(p->vLeaves, p->pBSet[0]))->Level <=
          ((Abc_Obj_t *)Vec_PtrEntry(p->vLeaves, p->pBSet[1]))->Level );
      // cofactor w.r.t. the selected variables
      Extra_TruthCopy( p->uCofs[1], p->uTruth, nVars );
      c = 2;
      for ( v = 0; v < p->nLutSize; v++ )
          for ( k = 0; k < (1<<v); k++ )
          {
              Extra_TruthCopy( p->uCofs[c], p->uCofs[c/2], nVars );
              Extra_TruthCopy( p->uCofs[c+1], p->uCofs[c/2], nVars );
              Extra_TruthCofactor0( p->uCofs[c], nVars, p->pBSet[v] );
              Extra_TruthCofactor1( p->uCofs[c+1], nVars, p->pBSet[v] );
              c += 2;
          }
      assert( c == (2 << p->nLutSize) );
      // count unique cofactors
      nClasses = 0;
      nCofs = (1 << p->nLutSize);
      for ( i = 0; i < nCofs; i++ )
      {
          pTruthCof = p->uCofs[ nCofs + i ];
          for ( k = 0; k < nClasses; k++ )
          {
              pTruthClass = p->uCofs[ nCofs + pCofClasses[k][0] ];
              if ( Extra_TruthIsEqual( pTruthCof, pTruthClass, nVars ) )
              {
                  pCofClasses[k][(int)nCofClasses[k]++ ] = i;
                  break;
              }
          }
          if ( k != nClasses )
              continue;
          // not found
          pCofClasses[nClasses][0] = i;
          nCofClasses[nClasses] = 1;
          nClasses++;
          if ( nClasses > nCofs/2 )
              return 0;
      }
      // the number of cofactors is acceptable
      nVarsNew = Abc_Base2Log( nClasses );
      assert( nVarsNew < p->nLutSize );
      // create the remainder truth table
      // for each class of cofactors, multiply cofactor truth table by its code
      Extra_TruthClear( p->uTruth, nVars );
      for ( k = 0; k < nClasses; k++ )
      {
          pTruthClass = p->uCofs[ nCofs + pCofClasses[k][0] ];
          for ( v = 0; v < nVarsNew; v++ )
              if ( k & (1 << v) )
                  Extra_TruthAnd( pTruthClass, pTruthClass, p->uVars[p->pBSet[v]], nVars );
              else
                  Extra_TruthSharp( pTruthClass, pTruthClass, p->uVars[p->pBSet[v]], nVars );
          Extra_TruthOr( p->uTruth, p->uTruth, pTruthClass, nVars );
      }
      // create nodes
      pTruth = p->uCofs[0];
      for ( v = 0; v < nVarsNew; v++ )
      {
          Extra_TruthClear( pTruth, p->nLutSize );
          for ( k = 0; k < nClasses; k++ )
              if ( k & (1 << v) )
                  for ( i = 0; i < nCofClasses[k]; i++ )
                  {
                      pTruthCof = p->uCofs[1];
                      Extra_TruthFill( pTruthCof, p->nLutSize );
                      for ( w = 0; w < p->nLutSize; w++ )
                          if ( pCofClasses[k][i] & (1 << (p->nLutSize-1-w)) )
                              Extra_TruthAnd( pTruthCof, pTruthCof, p->uVars[w], p->nLutSize );
                          else
                              Extra_TruthSharp( pTruthCof, pTruthCof, p->uVars[w], p->nLutSize );
                      Extra_TruthOr( pTruth, pTruth, pTruthCof, p->nLutSize );
                  }
          // implement the node
          pObjNew = Abc_NtkCreateNode( pNtk );
          for ( i = 0; i < p->nLutSize; i++ )
          {
              pFanin = (Abc_Obj_t *)Vec_PtrEntry( p->vLeaves, p->pBSet[i] );
              Abc_ObjAddFanin( pObjNew, pFanin );
          }
          // create the function
          pObjNew->pData = Abc_SopCreateFromTruth( (Mem_Flex_t *)pNtk->pManFunc, p->nLutSize, pTruth ); // need ISOP
          pObjNew->Level = Abc_NodeGetLevel( pObjNew );
          pNodesNew[v] = pObjNew;
      }
      // put the new nodes back into the list
      for ( v = 0; v < nVarsNew; v++ )
          Vec_PtrWriteEntry( p->vLeaves, p->pBSet[v], pNodesNew[v] );
      // compute the variables that should be removed
      uPhase = 0;
      for ( v = nVarsNew; v < p->nLutSize; v++ )
          uPhase |= (1 << p->pBSet[v]);
      // remove entries from the array
      Abc_NodeLeavesRemove( p->vLeaves, uPhase, nVars );
      // update truth table
      Extra_TruthShrink( p->uCofs[0], p->uTruth, nVars - p->nLutSize + nVarsNew, nVars, ((1 << nVars) - 1) & ~uPhase );
      Extra_TruthCopy( p->uTruth, p->uCofs[0], nVars );
      assert( !Extra_TruthVarInSupport( p->uTruth, nVars, nVars - p->nLutSize + nVarsNew ) );
      return 1;
  }
  
  ////////////////////////////////////////////////////////////////////////
  ///                       END OF FILE                                ///
  ////////////////////////////////////////////////////////////////////////
  
  ABC_NAMESPACE_IMPL_END
  
  
  
  