text: /**CFile****************************************************************
  
    FileName    [lpkAbcDec.c]
  
    SystemName  [ABC: Logic synthesis and verification system.]
  
    PackageName [Fast Boolean matching for LUT structures.]
  
    Synopsis    [The new core procedure.]
  
    Author      [Alan Mishchenko]
    
    Affiliation [UC Berkeley]
  
    Date        [Ver. 1.0. Started - April 28, 2007.]
  
    Revision    [$Id: lpkAbcDec.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $]
  
  ***********************************************************************/
   
  #include "lpkInt.h"
  
  ABC_NAMESPACE_IMPL_START
  
  
  ////////////////////////////////////////////////////////////////////////
  ///                        DECLARATIONS                              ///
  ////////////////////////////////////////////////////////////////////////
  
  ////////////////////////////////////////////////////////////////////////
  ///                     FUNCTION DEFINITIONS                         ///
  ////////////////////////////////////////////////////////////////////////
  
  /**Function*************************************************************
  
    Synopsis    [Implements the function.]
  
    Description [Returns the node implementing this function.]
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  Abc_Obj_t * Lpk_ImplementFun( Lpk_Man_t * pMan, Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, Lpk_Fun_t * p )
  {
      extern Hop_Obj_t * Kit_TruthToHop( Hop_Man_t * pMan, unsigned * pTruth, int nVars, Vec_Int_t * vMemory );
      unsigned * pTruth;
      Abc_Obj_t * pObjNew;
      int i;
      if ( p->fMark )
          pMan->nMuxes++;
      else
          pMan->nDsds++;
      // create the new node
      pObjNew = Abc_NtkCreateNode( pNtk );
      for ( i = 0; i < (int)p->nVars; i++ )
          Abc_ObjAddFanin( pObjNew, Abc_ObjRegular((Abc_Obj_t *)Vec_PtrEntry(vLeaves, p->pFanins[i])) );
      Abc_ObjSetLevel( pObjNew, Abc_ObjLevelNew(pObjNew) );
      // assign the node's function
      pTruth = Lpk_FunTruth(p, 0);
      if ( p->nVars == 0 )
      {
          pObjNew->pData = Hop_NotCond( Hop_ManConst1((Hop_Man_t *)pNtk->pManFunc), !(pTruth[0] & 1) );
          return pObjNew;
      }
      if ( p->nVars == 1 )
      {
          pObjNew->pData = Hop_NotCond( Hop_ManPi((Hop_Man_t *)pNtk->pManFunc, 0), (pTruth[0] & 1) );
          return pObjNew;
      }
      // create the logic function
      pObjNew->pData = Kit_TruthToHop( (Hop_Man_t *)pNtk->pManFunc, pTruth, p->nVars, NULL );
      return pObjNew;
  }
  
  /**Function*************************************************************
  
    Synopsis    [Implements the function.]
  
    Description [Returns the node implementing this function.]
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  Abc_Obj_t * Lpk_Implement_rec( Lpk_Man_t * pMan, Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, Lpk_Fun_t * pFun )
  {
      Abc_Obj_t * pFanin, * pRes;
      int i;
      // prepare the leaves of the function
      for ( i = 0; i < (int)pFun->nVars; i++ )
      {
          pFanin = (Abc_Obj_t *)Vec_PtrEntry( vLeaves, pFun->pFanins[i] );
          if ( !Abc_ObjIsComplement(pFanin) )
              Lpk_Implement_rec( pMan, pNtk, vLeaves, (Lpk_Fun_t *)pFanin );
          pFanin = (Abc_Obj_t *)Vec_PtrEntry( vLeaves, pFun->pFanins[i] );
          assert( Abc_ObjIsComplement(pFanin) );
      }
      // construct the function
      pRes = Lpk_ImplementFun( pMan, pNtk, vLeaves, pFun );
      // replace the function
      Vec_PtrWriteEntry( vLeaves, pFun->Id, Abc_ObjNot(pRes) );
      Lpk_FunFree( pFun );
      return pRes;
  }
  
  /**Function*************************************************************
  
    Synopsis    [Implements the function.]
  
    Description [Returns the node implementing this function.]
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  Abc_Obj_t * Lpk_Implement( Lpk_Man_t * pMan, Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, int nLeavesOld )
  {
      Abc_Obj_t * pFanin, * pRes;
      int i;
      assert( nLeavesOld < Vec_PtrSize(vLeaves) );
      // mark implemented nodes
      Vec_PtrForEachEntryStop( Abc_Obj_t *, vLeaves, pFanin, i, nLeavesOld )
          Vec_PtrWriteEntry( vLeaves, i, Abc_ObjNot(pFanin) );
      // recursively construct starting from the first entry
      pRes = Lpk_Implement_rec( pMan, pNtk, vLeaves, (Lpk_Fun_t *)Vec_PtrEntry( vLeaves, nLeavesOld ) );
      Vec_PtrShrink( vLeaves, nLeavesOld );
      return pRes;
  }
  
  /**Function*************************************************************
  
    Synopsis    [Decomposes the function using recursive MUX decomposition.]
  
    Description [Returns the ID of the top-most decomposition node 
    implementing this function, or 0 if there is no decomposition satisfying
    the constraints on area and delay.]
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  int Lpk_Decompose_rec( Lpk_Man_t * pMan, Lpk_Fun_t * p )
  {
      Lpk_Res_t * pResMux, * pResDsd;
      Lpk_Fun_t * p2;
      abctime clk;
  
      // is only called for non-trivial blocks
      assert( p->nLutK >= 3 && p->nLutK <= 6 );
      assert( p->nVars > p->nLutK );
      // skip if area bound is exceeded
      if ( Lpk_LutNumLuts(p->nVars, p->nLutK) > (int)p->nAreaLim )
          return 0;
      // skip if delay bound is exceeded
      if ( Lpk_SuppDelay(p->uSupp, p->pDelays) > (int)p->nDelayLim )
          return 0;
  
      // compute supports if needed
      if ( !p->fSupports )
          Lpk_FunComputeCofSupps( p );
  
      // check DSD decomposition
  clk = Abc_Clock();
      pResDsd = Lpk_DsdAnalize( pMan, p, pMan->pPars->nVarsShared );
  pMan->timeEvalDsdAn += Abc_Clock() - clk;
      if ( pResDsd && (pResDsd->nBSVars == (int)p->nLutK || pResDsd->nBSVars == (int)p->nLutK - 1) && 
            pResDsd->AreaEst <= (int)p->nAreaLim && pResDsd->DelayEst <= (int)p->nDelayLim )
      {
  clk = Abc_Clock();
          p2 = Lpk_DsdSplit( pMan, p, pResDsd->pCofVars, pResDsd->nCofVars, pResDsd->BSVars );
  pMan->timeEvalDsdSp += Abc_Clock() - clk;
          assert( p2->nVars <= (int)p->nLutK );
          if ( p->nVars > p->nLutK && !Lpk_Decompose_rec( pMan, p ) )
              return 0;
          return 1;
      }
  
      // check MUX decomposition
  clk = Abc_Clock();
      pResMux = Lpk_MuxAnalize( pMan, p );
  pMan->timeEvalMuxAn += Abc_Clock() - clk;
  //    pResMux = NULL;
      assert( !pResMux || (pResMux->DelayEst <= (int)p->nDelayLim && pResMux->AreaEst <= (int)p->nAreaLim) );
      // accept MUX decomposition if it is "good"
      if ( pResMux && pResMux->nSuppSizeS <= (int)p->nLutK && pResMux->nSuppSizeL <= (int)p->nLutK )
          pResDsd = NULL;
      else if ( pResMux && pResDsd )
      {
          // compare two decompositions
          if ( pResMux->AreaEst < pResDsd->AreaEst || 
              (pResMux->AreaEst == pResDsd->AreaEst && pResMux->nSuppSizeL < pResDsd->nSuppSizeL) || 
              (pResMux->AreaEst == pResDsd->AreaEst && pResMux->nSuppSizeL == pResDsd->nSuppSizeL && pResMux->DelayEst < pResDsd->DelayEst) )
              pResDsd = NULL;
          else
              pResMux = NULL;
      }
      assert( pResMux == NULL || pResDsd == NULL );
      if ( pResMux )
      {
  clk = Abc_Clock();
          p2 = Lpk_MuxSplit( pMan, p, pResMux->Variable, pResMux->Polarity );
  pMan->timeEvalMuxSp += Abc_Clock() - clk;
          if ( p2->nVars > p->nLutK && !Lpk_Decompose_rec( pMan, p2 ) )
              return 0;
          if ( p->nVars > p->nLutK && !Lpk_Decompose_rec( pMan, p ) )
              return 0;
          return 1;
      }
      if ( pResDsd )
      {
  clk = Abc_Clock();
          p2 = Lpk_DsdSplit( pMan, p, pResDsd->pCofVars, pResDsd->nCofVars, pResDsd->BSVars );
  pMan->timeEvalDsdSp += Abc_Clock() - clk;
          assert( p2->nVars <= (int)p->nLutK );
          if ( p->nVars > p->nLutK && !Lpk_Decompose_rec( pMan, p ) )
              return 0;
          return 1;
      }
      return 0;
  }
  
  /**Function*************************************************************
  
    Synopsis    [Removes decomposed nodes from the array of fanins.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  void Lpk_DecomposeClean( Vec_Ptr_t * vLeaves, int nLeavesOld )
  {
      Lpk_Fun_t * pFunc;
      int i;
      Vec_PtrForEachEntryStart( Lpk_Fun_t *, vLeaves, pFunc, i, nLeavesOld )
          Lpk_FunFree( pFunc );
      Vec_PtrShrink( vLeaves, nLeavesOld );
  }
  
  /**Function*************************************************************
  
    Synopsis    [Decomposes the function using recursive MUX decomposition.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  Abc_Obj_t * Lpk_Decompose( Lpk_Man_t * p, Abc_Ntk_t * pNtk, Vec_Ptr_t * vLeaves, unsigned * pTruth, unsigned * puSupps, int nLutK, int AreaLim, int DelayLim )
  {
      Lpk_Fun_t * pFun;
      Abc_Obj_t * pObjNew = NULL;
      int nLeaves = Vec_PtrSize( vLeaves );
      pFun = Lpk_FunCreate( pNtk, vLeaves, pTruth, nLutK, AreaLim, DelayLim );
      if ( puSupps[0] || puSupps[1] )
      {
  /*
          int i;
          Lpk_FunComputeCofSupps( pFun );
          for ( i = 0; i < nLeaves; i++ )
          {
              assert( pFun->puSupps[2*i+0] == puSupps[2*i+0] );
              assert( pFun->puSupps[2*i+1] == puSupps[2*i+1] );
          }
  */
          memcpy( pFun->puSupps, puSupps, sizeof(unsigned) * 2 * nLeaves );
          pFun->fSupports = 1;
      }
      Lpk_FunSuppMinimize( pFun );
      if ( pFun->nVars <= pFun->nLutK )
          pObjNew = Lpk_ImplementFun( p, pNtk, vLeaves, pFun );
      else if ( Lpk_Decompose_rec(p, pFun) )
          pObjNew = Lpk_Implement( p, pNtk, vLeaves, nLeaves );
      Lpk_DecomposeClean( vLeaves, nLeaves );
      return pObjNew;
  }
  
  
  ////////////////////////////////////////////////////////////////////////
  ///                       END OF FILE                                ///
  ////////////////////////////////////////////////////////////////////////
  
  
  ABC_NAMESPACE_IMPL_END
  
  