abcLut.c

/**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