text: /**CFile****************************************************************
  
    FileName    [ivyMulti.c]
  
    SystemName  [ABC: Logic synthesis and verification system.]
  
    PackageName [And-Inverter Graph package.]
  
    Synopsis    [Constructing multi-input AND/EXOR gates.]
  
    Author      [Alan Mishchenko]
    
    Affiliation [UC Berkeley]
  
    Date        [Ver. 1.0. Started - May 11, 2006.]
  
    Revision    [$Id: ivyMulti.c,v 1.00 2006/05/11 00:00:00 alanmi Exp $]
  
  ***********************************************************************/
  
  #include "ivy.h"
  
  ////////////////////////////////////////////////////////////////////////
  ///                        DECLARATIONS                              ///
  ////////////////////////////////////////////////////////////////////////
  
  typedef struct Ivy_Eval_t_ Ivy_Eval_t;
  struct Ivy_Eval_t_
  {
      unsigned Mask   :  5;  // the mask of covered nodes
      unsigned Weight :  3;  // the number of covered nodes
      unsigned Cost   :  4;  // the number of overlapping nodes
      unsigned Level  : 12;  // the level of this node
      unsigned Fan0   :  4;  // the first fanin
      unsigned Fan1   :  4;  // the second fanin
  };
  
  static Ivy_Obj_t * Ivy_MultiBuild_rec( Ivy_Eval_t * pEvals, int iNum, Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type );
  static void        Ivy_MultiSort( Ivy_Obj_t ** pArgs, int nArgs );
  static int         Ivy_MultiPushUniqueOrderByLevel( Ivy_Obj_t ** pArray, int nArgs, Ivy_Obj_t * pNode );
  static Ivy_Obj_t * Ivy_MultiEval( Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type );
  
  
  ////////////////////////////////////////////////////////////////////////
  ///                     FUNCTION DEFINITIONS                         ///
  ////////////////////////////////////////////////////////////////////////
  
  /**Function*************************************************************
  
    Synopsis    [Constructs the well-balanced tree of gates.]
  
    Description [Disregards levels and possible logic sharing.]
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  Ivy_Obj_t * Ivy_Multi_rec( Ivy_Obj_t ** ppObjs, int nObjs, Ivy_Type_t Type )
  {
      Ivy_Obj_t * pObj1, * pObj2;
      if ( nObjs == 1 )
          return ppObjs[0];
      pObj1 = Ivy_Multi_rec( ppObjs,           nObjs/2,         Type );
      pObj2 = Ivy_Multi_rec( ppObjs + nObjs/2, nObjs - nObjs/2, Type );
      return Ivy_Oper( pObj1, pObj2, Type );
  }
  
  /**Function*************************************************************
  
    Synopsis    [Constructs a balanced tree while taking sharing into account.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  Ivy_Obj_t * Ivy_Multi( Ivy_Obj_t ** pArgsInit, int nArgs, Ivy_Type_t Type )
  {
      static char NumBits[32] = {0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5};
      static Ivy_Eval_t pEvals[15+15*14/2];
      static Ivy_Obj_t * pArgs[16];
      Ivy_Eval_t * pEva, * pEvaBest;
      int nArgsNew, nEvals, i, k;
      Ivy_Obj_t * pTemp;
  
      // consider the case of one argument
      assert( nArgs > 0 );
      if ( nArgs == 1 )
          return pArgsInit[0];
      // consider the case of two arguments
      if ( nArgs == 2 )
          return Ivy_Oper( pArgsInit[0], pArgsInit[1], Type );
  
  //Ivy_MultiEval( pArgsInit, nArgs, Type ); printf( "\n" );
  
      // set the initial ones
      for ( i = 0; i < nArgs; i++ )
      {
          pArgs[i] = pArgsInit[i];
          pEva = pEvals + i;
          pEva->Mask   = (1 << i);
          pEva->Weight = 1;
          pEva->Cost   = 0; 
          pEva->Level  = Ivy_Regular(pArgs[i])->Level; 
          pEva->Fan0   = 0; 
          pEva->Fan1   = 0; 
      }
  
      // find the available nodes
      pEvaBest = pEvals;
      nArgsNew = nArgs;
      for ( i = 1; i < nArgsNew; i++ )
      for ( k = 0; k < i; k++ )
          if ( pTemp = Ivy_TableLookup(Ivy_ObjCreateGhost(pArgs[k], pArgs[i], Type, IVY_INIT_NONE)) )
          {
              pEva = pEvals + nArgsNew;
              pEva->Mask   = pEvals[k].Mask | pEvals[i].Mask;
              pEva->Weight = NumBits[pEva->Mask];
              pEva->Cost   = pEvals[k].Cost + pEvals[i].Cost + NumBits[pEvals[k].Mask & pEvals[i].Mask]; 
              pEva->Level  = 1 + IVY_MAX(pEvals[k].Level, pEvals[i].Level); 
              pEva->Fan0   = k; 
              pEva->Fan1   = i; 
  //            assert( pEva->Level == (unsigned)Ivy_ObjLevel(pTemp) );
              // compare
              if ( pEvaBest->Weight < pEva->Weight ||
                   pEvaBest->Weight == pEva->Weight && pEvaBest->Cost > pEva->Cost ||
                   pEvaBest->Weight == pEva->Weight && pEvaBest->Cost == pEva->Cost && pEvaBest->Level > pEva->Level )
                   pEvaBest = pEva;
              // save the argument
              pArgs[nArgsNew++] = pTemp;
              if ( nArgsNew == 15 )
                  goto Outside;
          }
  Outside:
  
  //    printf( "Best = %d.\n", pEvaBest - pEvals );
  
      // the case of no common nodes
      if ( nArgsNew == nArgs )
      {
          Ivy_MultiSort( pArgs, nArgs );
          return Ivy_MultiBalance_rec( pArgs, nArgs, Type );
      }
      // the case of one common node
      if ( nArgsNew == nArgs + 1 )
      {
          assert( pEvaBest - pEvals == nArgs );
          k = 0;
          for ( i = 0; i < nArgs; i++ )
              if ( i != (int)pEvaBest->Fan0 && i != (int)pEvaBest->Fan1 )
                  pArgs[k++] = pArgs[i];
          pArgs[k++] = pArgs[nArgs];
          assert( k == nArgs - 1 );
          nArgs = k;
          Ivy_MultiSort( pArgs, nArgs );
          return Ivy_MultiBalance_rec( pArgs, nArgs, Type );
      }
      // the case when there is a node that covers everything
      if ( (int)pEvaBest->Mask == ((1 << nArgs) - 1) )
          return Ivy_MultiBuild_rec( pEvals, pEvaBest - pEvals, pArgs, nArgsNew, Type ); 
  
      // evaluate node pairs
      nEvals = nArgsNew;
      for ( i = 1; i < nArgsNew; i++ )
      for ( k = 0; k < i; k++ )
      {
          pEva = pEvals + nEvals;
          pEva->Mask   = pEvals[k].Mask | pEvals[i].Mask;
          pEva->Weight = NumBits[pEva->Mask];
          pEva->Cost   = pEvals[k].Cost + pEvals[i].Cost + NumBits[pEvals[k].Mask & pEvals[i].Mask]; 
          pEva->Level  = 1 + IVY_MAX(pEvals[k].Level, pEvals[i].Level); 
          pEva->Fan0   = k; 
          pEva->Fan1   = i; 
          // compare
          if ( pEvaBest->Weight < pEva->Weight ||
               pEvaBest->Weight == pEva->Weight && pEvaBest->Cost > pEva->Cost ||
               pEvaBest->Weight == pEva->Weight && pEvaBest->Cost == pEva->Cost && pEvaBest->Level > pEva->Level )
               pEvaBest = pEva;
          // save the argument
          nEvals++;
      }
      assert( pEvaBest - pEvals >= nArgsNew );
  
  //    printf( "Used (%d, %d).\n", pEvaBest->Fan0, pEvaBest->Fan1 );
  
      // get the best implementation
      pTemp = Ivy_MultiBuild_rec( pEvals, pEvaBest - pEvals, pArgs, nArgsNew, Type );
  
      // collect those not covered by EvaBest
      k = 0;
      for ( i = 0; i < nArgs; i++ )
          if ( (pEvaBest->Mask & (1 << i)) == 0 )
              pArgs[k++] = pArgs[i];
      pArgs[k++] = pTemp;
      assert( k == nArgs - (int)pEvaBest->Weight + 1 );
      nArgs = k;
      Ivy_MultiSort( pArgs, nArgs );
      return Ivy_MultiBalance_rec( pArgs, nArgs, Type );
  }
  
  /**Function*************************************************************
  
    Synopsis    [Implements multi-input AND/EXOR operation.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  Ivy_Obj_t * Ivy_MultiBuild_rec( Ivy_Eval_t * pEvals, int iNum, Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type )
  {
      Ivy_Obj_t * pNode0, * pNode1;
      if ( iNum < nArgs )
          return pArgs[iNum];
      pNode0 = Ivy_MultiBuild_rec( pEvals, pEvals[iNum].Fan0, pArgs, nArgs, Type );
      pNode1 = Ivy_MultiBuild_rec( pEvals, pEvals[iNum].Fan1, pArgs, nArgs, Type );
      return Ivy_Oper( pNode0, pNode1, Type );
  }
  
  /**Function*************************************************************
  
    Synopsis    [Selection-sorts the nodes in the decreasing over of level.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  void Ivy_MultiSort( Ivy_Obj_t ** pArgs, int nArgs )
  {
      Ivy_Obj_t * pTemp;
      int i, j, iBest;
  
      for ( i = 0; i < nArgs-1; i++ )
      {
          iBest = i;
          for ( j = i+1; j < nArgs; j++ )
              if ( Ivy_Regular(pArgs[j])->Level > Ivy_Regular(pArgs[iBest])->Level )
                  iBest = j;
          pTemp = pArgs[i]; 
          pArgs[i] = pArgs[iBest]; 
          pArgs[iBest] = pTemp;
      }
  }
  
  /**Function*************************************************************
  
    Synopsis    [Inserts a new node in the order by levels.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  int Ivy_MultiPushUniqueOrderByLevel( Ivy_Obj_t ** pArray, int nArgs, Ivy_Obj_t * pNode )
  {
      Ivy_Obj_t * pNode1, * pNode2;
      int i;
      // try to find the node in the array
      for ( i = 0; i < nArgs; i++ )
          if ( pArray[i] == pNode )
              return nArgs;
      // put the node last
      pArray[nArgs++] = pNode;
      // find the place to put the new node
      for ( i = nArgs-1; i > 0; i-- )
      {
          pNode1 = pArray[i  ];
          pNode2 = pArray[i-1];
          if ( Ivy_Regular(pNode1)->Level <= Ivy_Regular(pNode2)->Level )
              break;
          pArray[i  ] = pNode2;
          pArray[i-1] = pNode1;
      }
      return nArgs;
  }
  
  /**Function*************************************************************
  
    Synopsis    [Balances the array recursively.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  Ivy_Obj_t * Ivy_MultiBalance_rec( Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type )
  {
      Ivy_Obj_t * pNodeNew;
      // consider the case of one argument
      assert( nArgs > 0 );
      if ( nArgs == 1 )
          return pArgs[0];
      // consider the case of two arguments
      if ( nArgs == 2 )
          return Ivy_Oper( pArgs[0], pArgs[1], Type );
      // get the last two nodes
      pNodeNew = Ivy_Oper( pArgs[nArgs-1], pArgs[nArgs-2], Type );
      // add the new node
      nArgs = Ivy_MultiPushUniqueOrderByLevel( pArgs, nArgs - 2, pNodeNew );
      return Ivy_MultiBalance_rec( pArgs, nArgs, Type );
  }
  
  /**Function*************************************************************
  
    Synopsis    [Implements multi-input AND/EXOR operation.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  Ivy_Obj_t * Ivy_MultiEval( Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type )
  {
      Ivy_Obj_t * pTemp;
      int i, k;
      int nArgsOld = nArgs;
      for ( i = 0; i < nArgs; i++ )
          printf( "%d[%d] ", i, Ivy_Regular(pArgs[i])->Level );
      for ( i = 1; i < nArgs; i++ )
          for ( k = 0; k < i; k++ )
          {
              pTemp = Ivy_TableLookup(Ivy_ObjCreateGhost(pArgs[k], pArgs[i], Type, IVY_INIT_NONE));
              if ( pTemp != NULL )
              {
                  printf( "%d[%d]=(%d,%d) ", nArgs, Ivy_Regular(pTemp)->Level, k, i );
                  pArgs[nArgs++] = pTemp;
              }
          }
      printf( "     ((%d/%d))    ", nArgsOld, nArgs-nArgsOld );
      return NULL;
  }
  
  
  
  /**Function*************************************************************
  
    Synopsis    [Old code.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  Ivy_Obj_t * Ivy_Multi1( Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type )
  {
      Ivy_Obj_t * pArgsRef[5], * pTemp;
      int i, k, m, nArgsNew, Counter = 0;
   
      
  //Ivy_MultiEval( pArgs, nArgs, Type );  printf( "\n" );
  
  
      assert( Type == IVY_AND || Type == IVY_EXOR );
      assert( nArgs > 0 );
      if ( nArgs == 1 )
          return pArgs[0];
  
      // find the nodes with more than one fanout
      nArgsNew = 0;
      for ( i = 0; i < nArgs; i++ )
          if ( Ivy_ObjRefs( Ivy_Regular(pArgs[i]) ) > 0 )
              pArgsRef[nArgsNew++] = pArgs[i];
  
      // go through pairs
      if ( nArgsNew >= 2 )
      for ( i = 0; i < nArgsNew; i++ )
      for ( k = i + 1; k < nArgsNew; k++ )
          if ( pTemp = Ivy_TableLookup(Ivy_ObjCreateGhost(pArgsRef[i], pArgsRef[k], Type, IVY_INIT_NONE)) )
              Counter++;
  //    printf( "%d", Counter );
              
      // go through pairs
      if ( nArgsNew >= 2 )
      for ( i = 0; i < nArgsNew; i++ )
      for ( k = i + 1; k < nArgsNew; k++ )
          if ( pTemp = Ivy_TableLookup(Ivy_ObjCreateGhost(pArgsRef[i], pArgsRef[k], Type, IVY_INIT_NONE)) )
          {
              nArgsNew = 0;
              for ( m = 0; m < nArgs; m++ )
                  if ( pArgs[m] != pArgsRef[i] && pArgs[m] != pArgsRef[k] )
                      pArgs[nArgsNew++] = pArgs[m];
              pArgs[nArgsNew++] = pTemp;
              assert( nArgsNew == nArgs - 1 );
              return Ivy_Multi1( pArgs, nArgsNew, Type );
          }
      return Ivy_Multi_rec( pArgs, nArgs, Type );
  }
  
  /**Function*************************************************************
  
    Synopsis    [Old code.]
  
    Description []
                 
    SideEffects []
  
    SeeAlso     []
  
  ***********************************************************************/
  Ivy_Obj_t * Ivy_Multi2( Ivy_Obj_t ** pArgs, int nArgs, Ivy_Type_t Type )
  {
      assert( Type == IVY_AND || Type == IVY_EXOR );
      assert( nArgs > 0 );
      return Ivy_Multi_rec( pArgs, nArgs, Type );
  }
  
  ////////////////////////////////////////////////////////////////////////
  ///                       END OF FILE                                ///
  ////////////////////////////////////////////////////////////////////////
  
  
  