giaKf.c

/**CFile****************************************************************

  FileName    [giaKf.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Scalable AIG package.]

  Synopsis    [Cut computation.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - June 20, 2005.]

  Revision    [$Id: giaKf.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]

***********************************************************************/

#include "gia.h"
#include "misc/vec/vecSet.h"

#ifdef ABC_USE_PTHREADS

#ifdef _WIN32
#include "../lib/pthread.h"
#else
#include <pthread.h>
#include <unistd.h>
#endif

#endif

ABC_NAMESPACE_IMPL_START

////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

#ifndef ABC_USE_PTHREADS

void Kf_ManSetDefaultPars( Jf_Par_t * pPars ) {}
Gia_Man_t * Kf_ManPerformMapping( Gia_Man_t * pGia, Jf_Par_t * pPars ) { return NULL; }

#else // pthreads are used

#define KF_LEAF_MAX  16
#define KF_CUT_MAX   32
#define KF_PROC_MAX  32
#define KF_WORD_MAX  ((KF_LEAF_MAX > 6) ? 1 << (KF_LEAF_MAX-6) : 1)
#define KF_LOG_TABLE  8

#define KF_ADD_ON1    2  // offset in cut storage for each node (cut count; best cut)
#define KF_ADD_ON2    4  // offset in cut storage for each cut (leaf count; function, cut delay; cut area)

typedef struct Kf_Cut_t_ Kf_Cut_t; 
typedef struct Kf_Set_t_ Kf_Set_t; 
typedef struct Kf_Man_t_ Kf_Man_t; 

struct Kf_Cut_t_
{
    word            Sign;        // signature
    int             Polar;       // polarity
    int             Delay;       // delay
    float           Area;        // area 
    int             iFunc;       // function 
    int             iNext;       // next cut
    int             nLeaves;     // number of leaves
    int             pLeaves[KF_LEAF_MAX]; 
};
struct Kf_Set_t_
{
    Kf_Man_t *      pMan;        // manager
    unsigned short  nLutSize;    // lut size
    unsigned short  nCutNum;     // cut count
    int             nCuts0;      // fanin0 cut count
    int             nCuts1;      // fanin1 cut count
    int             nCuts;       // resulting cut count
    int             nTEntries;   // hash table entries 
    int             TableMask;   // hash table mask
    int             pTable[1 << KF_LOG_TABLE];
    int             pValue[1 << KF_LOG_TABLE];
    int             pPlace[KF_LEAF_MAX];
    int             pList [KF_LEAF_MAX+1];
    Kf_Cut_t        pCuts0[KF_CUT_MAX];
    Kf_Cut_t        pCuts1[KF_CUT_MAX];
    Kf_Cut_t        pCutsR[KF_CUT_MAX*KF_CUT_MAX];
    Kf_Cut_t *      ppCuts[KF_CUT_MAX];
    Kf_Cut_t *      pCutBest;
    word            CutCount[4]; // statistics
};
struct Kf_Man_t_
{
    Gia_Man_t *     pGia;        // user's manager
    Jf_Par_t *      pPars;       // user's parameters
    Vec_Set_t       pMem;        // cut storage
    Vec_Int_t       vCuts;       // node params
    Vec_Int_t       vTime;       // node params
    Vec_Flt_t       vArea;       // node params
    Vec_Flt_t       vRefs;       // node params
    Vec_Int_t *     vTemp;       // temporary
    abctime         clkStart;    // starting time
    Kf_Set_t        pSett[KF_PROC_MAX];
};

static inline int   Kf_SetCutId( Kf_Set_t * p, Kf_Cut_t * pCut )           { return pCut - p->pCutsR;               }
static inline Kf_Cut_t * Kf_SetCut( Kf_Set_t * p, int i )                  { return i >= 0 ? p->pCutsR + i : NULL;  }

static inline int   Kf_ObjTime( Kf_Man_t * p, int i )                      { return Vec_IntEntry(&p->vTime, i);     }
static inline float Kf_ObjArea( Kf_Man_t * p, int i )                      { return Vec_FltEntry(&p->vArea, i);     }
static inline float Kf_ObjRefs( Kf_Man_t * p, int i )                      { return Vec_FltEntry(&p->vRefs, i);     }

static inline void  Kf_ObjSetCuts( Kf_Man_t * p, int i, Vec_Int_t * vVec ) { Vec_IntWriteEntry(&p->vCuts, i, Vec_SetAppend(&p->pMem, Vec_IntArray(vVec), Vec_IntSize(vVec)));  }
static inline int * Kf_ObjCuts( Kf_Man_t * p, int i )                      { return (int *)Vec_SetEntry(&p->pMem, Vec_IntEntry(&p->vCuts, i));    }
static inline int * Kf_ObjCuts0( Kf_Man_t * p, int i )                     { return Kf_ObjCuts(p, Gia_ObjFaninId0(Gia_ManObj(p->pGia, i), i));    }
static inline int * Kf_ObjCuts1( Kf_Man_t * p, int i )                     { return Kf_ObjCuts(p, Gia_ObjFaninId1(Gia_ManObj(p->pGia, i), i));    }
static inline int * Kf_ObjCutBest( Kf_Man_t * p, int i )                   { int * pCuts = Kf_ObjCuts(p, i); return pCuts + pCuts[1];             }

#define Kf_ObjForEachCutInt( pList, pCut, i )        for ( i = 0, pCut = pList + KF_ADD_ON1; i < pList[0]; i++, pCut += pCut[0] + KF_ADD_ON2 )
#define Kf_ListForEachCut( p, iList, pCut )          for ( pCut = Kf_SetCut(p, p->pList[iList]); pCut; pCut = Kf_SetCut(p, pCut->iNext) )
#define Kf_ListForEachCutP( p, iList, pCut, pPlace ) for ( pPlace = p->pList+iList, pCut = Kf_SetCut(p, *pPlace); pCut; pCut = Kf_SetCut(p, *pPlace) )

////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int Kf_SetLoadCuts( Kf_Cut_t * pCuts, int * pIntCuts )
{
    Kf_Cut_t * pCut;
    int k, * pIntCut, nCuts = 0; 
    Kf_ObjForEachCutInt( pIntCuts, pIntCut, nCuts )
    {
        pCut = pCuts + nCuts;
        pCut->Sign  = 0;
        pCut->Polar = 0;
        pCut->iFunc = pIntCut[pIntCut[0] + 1];
        pCut->Delay = pIntCut[pIntCut[0] + 2];
        pCut->Area  = Abc_Int2Float(pIntCut[pIntCut[0] + 3]);
        pCut->nLeaves = pIntCut[0];    
        for ( k = 0; k < pIntCut[0]; k++ )
        {
            pCut->pLeaves[k] = Abc_Lit2Var(pIntCut[k+1]);
            pCut->Sign |= ((word)1) << (pCut->pLeaves[k] & 0x3F);
            if ( Abc_LitIsCompl(pIntCut[k+1]) )
                pCut->Polar |= (1 << k);
        }
    }
    return nCuts;
}
static inline void Kf_SetPrepare( Kf_Set_t * p, int * pCuts0, int * pCuts1 )
{
    int i;
    // prepare hash table
//    for ( i = 0; i <= p->TableMask; i++ )
//        assert( p->pTable[i] == 0 );
    // prepare cut storage
    for ( i = 0; i <= p->nLutSize; i++ )
        p->pList[i] = -1;
    // transfer cuts
    p->nCuts0 = Kf_SetLoadCuts( p->pCuts0, pCuts0 );
    p->nCuts1 = Kf_SetLoadCuts( p->pCuts1, pCuts1 );
    p->nCuts = 0;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline void Kf_ManStoreStart( Vec_Int_t * vTemp, int nCuts )
{
    Vec_IntClear( vTemp );
    Vec_IntPush( vTemp, nCuts );                // cut count
    Vec_IntPush( vTemp, -1 );                   // best offset
}
static inline void Kf_ManStoreAddUnit( Vec_Int_t * vTemp, int iObj, int Time, float Area )
{
    Vec_IntAddToEntry( vTemp, 0, 1 );
    Vec_IntPush( vTemp, 1 );                    // cut size
    Vec_IntPush( vTemp, Abc_Var2Lit(iObj, 0) ); // leaf
    Vec_IntPush( vTemp, 2 );                    // function
    Vec_IntPush( vTemp, Time );                 // delay
    Vec_IntPush( vTemp, Abc_Float2Int(Area) );  // area
}
static inline void Kf_ManSaveResults( Kf_Cut_t ** ppCuts, int nCuts, Kf_Cut_t * pCutBest, Vec_Int_t * vTemp )
{
    int i, k;
    assert( nCuts > 0 && nCuts < KF_CUT_MAX );
    Kf_ManStoreStart( vTemp, nCuts );
    for ( i = 0; i < nCuts; i++ )
    {
        if ( ppCuts[i] == pCutBest )
            Vec_IntWriteEntry( vTemp, 1, Vec_IntSize(vTemp) );
        Vec_IntPush( vTemp, ppCuts[i]->nLeaves );
//        Vec_IntPushArray( vTemp, ppCuts[i]->pLeaves, ppCuts[i]->nLeaves );
        for ( k = 0; k < ppCuts[i]->nLeaves; k++ )
            Vec_IntPush( vTemp, Abc_Var2Lit(ppCuts[i]->pLeaves[k], 0) );
        Vec_IntPush( vTemp, ppCuts[i]->iFunc );
        Vec_IntPush( vTemp, ppCuts[i]->Delay );
        Vec_IntPush( vTemp, Abc_Float2Int(ppCuts[i]->Area) );
    }
    assert( Vec_IntEntry(vTemp, 1) > 0 );
}
static inline int Kf_SetCompareCuts( Kf_Cut_t * p1, Kf_Cut_t * p2 )
{
    if ( p1 == NULL || p2 == NULL )
        return (p1 != NULL) - (p2 != NULL);
    if ( p1->nLeaves != p2->nLeaves )
        return p1->nLeaves - p2->nLeaves;
    return memcmp( p1->pLeaves, p2->pLeaves, sizeof(int)*p1->nLeaves );
}
static inline void Kf_SetAddToList( Kf_Set_t * p, Kf_Cut_t * pCut, int fSort )
{
    if ( !fSort )
        pCut->iNext = p->pList[pCut->nLeaves], p->pList[pCut->nLeaves] = Kf_SetCutId(p, pCut);
    else
    {
        int Value, * pPlace;
        Kf_Cut_t * pTemp;
        Vec_IntSelectSort( pCut->pLeaves, pCut->nLeaves );
        Kf_ListForEachCutP( p, pCut->nLeaves, pTemp, pPlace )
        {
            if ( (Value = Kf_SetCompareCuts(pTemp, pCut)) > 0 )
                break;
            assert( Value < 0 );
            pPlace = &pTemp->iNext;
        }
        pCut->iNext = *pPlace, *pPlace = Kf_SetCutId(p, pCut);
    }
}
static inline int Kf_CutCompare( Kf_Cut_t * pCut0, Kf_Cut_t * pCut1, int fArea )
{
    if ( fArea )
    {
        if ( pCut0->Area    < pCut1->Area )    return -1;
        if ( pCut0->Area    > pCut1->Area )    return  1;
        if ( pCut0->Delay   < pCut1->Delay )   return -1;
        if ( pCut0->Delay   > pCut1->Delay )   return  1;
        if ( pCut0->nLeaves < pCut1->nLeaves ) return -1;
        if ( pCut0->nLeaves > pCut1->nLeaves ) return  1;
    }
    else
    {
        if ( pCut0->Delay   < pCut1->Delay )   return -1;
        if ( pCut0->Delay   > pCut1->Delay )   return  1;
        if ( pCut0->nLeaves < pCut1->nLeaves ) return -1;
        if ( pCut0->nLeaves > pCut1->nLeaves ) return  1;
        if ( pCut0->Area    < pCut1->Area )    return -1;
        if ( pCut0->Area    > pCut1->Area )    return  1;
    }
    return 0;
}
static inline int Kf_SetStoreAddOne( Kf_Set_t * p, int nCuts, int nCutNum, Kf_Cut_t * pCut, int fArea )
{
    int i;
    p->ppCuts[nCuts] = pCut;
    if ( nCuts == 0 )
        return 1;
    for ( i = nCuts; i > 0; i-- )
        if ( Kf_CutCompare(p->ppCuts[i-1], p->ppCuts[i], fArea) > 0 )
            ABC_SWAP( Kf_Cut_t *, p->ppCuts[i-1], p->ppCuts[i] )
        else
            break;
    return Abc_MinInt( nCuts+1, nCutNum );
}
static inline void Kf_SetSelectBest( Kf_Set_t * p, int fArea, int fSort )
{
//    int fArea = p->pMan->pPars->fArea;
    Kf_Cut_t * pCut;
    int i, nCuts = 0;
    for ( i = 0; i <= p->nLutSize; i++ )
        Kf_ListForEachCut( p, i, pCut )
            nCuts = Kf_SetStoreAddOne( p, nCuts, p->nCutNum-1, pCut, fArea );
    assert( nCuts > 0 && nCuts < p->nCutNum );
    p->nCuts = nCuts;
    p->pCutBest = p->ppCuts[0];
    if ( !fSort )
        return;
    // sort by size in the reverse order
    for ( i = 0; i <= p->nLutSize; i++ )
        p->pList[i] = -1;
    for ( i = 0; i < nCuts; i++ )
        Kf_SetAddToList( p, p->ppCuts[i], 0 );
    p->nCuts = 0;
    for ( i = p->nLutSize; i >= 0; i-- )
        Kf_ListForEachCut( p, i, pCut )
            p->ppCuts[p->nCuts++] = pCut;
    assert( p->nCuts == nCuts );
}

/**Function*************************************************************

  Synopsis    [Check correctness of cuts.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int Kf_CheckCut( Kf_Cut_t * pBase, Kf_Cut_t * pCut ) // check if pCut is contained in pBase
{
    int nSizeB = pBase->nLeaves;
    int nSizeC = pCut->nLeaves;
    int * pB = pBase->pLeaves;
    int * pC = pCut->pLeaves;
    int i, k;
    for ( i = 0; i < nSizeC; i++ )
    {
        for ( k = 0; k < nSizeB; k++ )
            if ( pC[i] == pB[k] )
                break;
        if ( k == nSizeB )
            return 0;
    }
    return 1;
}
static inline int Kf_CheckCuts( Kf_Set_t * p )
{
    Kf_Cut_t * pCut0, * pCut1; 
    int i, k, m, n, Value;
    assert( p->nCuts > 0 );
    for ( i = 0; i <= p->nLutSize; i++ )
    Kf_ListForEachCut( p, i, pCut0 )
    {
        // check duplicates
        for ( m = 0; m < pCut0->nLeaves; m++ )
        for ( n = m+1; n < pCut0->nLeaves; n++ )
            assert( pCut0->pLeaves[m] != pCut0->pLeaves[n] );
        // check pairs
        for ( k = 0; k <= p->nLutSize; k++ )
        Kf_ListForEachCut( p, k, pCut1 )
        {
            if ( pCut0 == pCut1 )
                continue;
            // check containments
            Value = Kf_CheckCut( pCut0, pCut1 );
            assert( Value == 0 );
        }
    }
    return 1;
}

/**Function*************************************************************

  Synopsis    [Hash table.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int Kf_HashLookup( Kf_Set_t * p, int i )
{
    int k;
    assert( i > 0 );
    for ( k = i & p->TableMask; p->pTable[k]; k = (k + 1) & p->TableMask )
        if ( p->pTable[k] == i )
            return -1;
    return k;
}
static inline int Kf_HashFindOrAdd( Kf_Set_t * p, int i )
{
    int k = Kf_HashLookup( p, i );
    if ( k == -1 )
        return 0;
    if ( p->nTEntries == p->nLutSize )
        return 1;
    assert( p->pTable[k] == 0 );
    p->pTable[k] = i;
    p->pPlace[p->nTEntries] = k;
    p->pValue[k] = p->nTEntries++;
    return 0;
}
static inline void Kf_HashPopulate( Kf_Set_t * p, Kf_Cut_t * pCut )
{
    int i;
    assert( p->nTEntries == 0 );
    for ( i = 0; i < pCut->nLeaves; i++ )
        Kf_HashFindOrAdd( p, pCut->pLeaves[i] );
    assert( p->nTEntries == pCut->nLeaves );
}
static inline void Kf_HashCleanup( Kf_Set_t * p, int iStart )
{
    int i;
    for ( i = iStart; i < p->nTEntries; i++ )
        p->pTable[p->pPlace[i]] = 0;
    p->nTEntries = iStart;
}

/**Function*************************************************************

  Synopsis    [Cut merging with arbitary order.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int Kf_SetCountBits( word i )
{
    i = i - ((i >> 1) & 0x5555555555555555);
    i = (i & 0x3333333333333333) + ((i >> 2) & 0x3333333333333333);
    i = ((i + (i >> 4)) & 0x0F0F0F0F0F0F0F0F);
    return (i*(0x0101010101010101))>>56;
}
static inline word Kf_SetCutGetSign( Kf_Cut_t * p )
{
    word Sign = 0; int i; 
    for ( i = 0; i < p->nLeaves; i++ )
        Sign |= ((word)1) << (p->pLeaves[i] & 0x3F);
    return Sign;
}
// returns 1 if the cut in hash table is dominated by the given one
static inline int Kf_SetCutDominatedByThis( Kf_Set_t * p, Kf_Cut_t * pCut )
{
    int i;
    for ( i = 0; i < pCut->nLeaves; i++ )
        if ( Kf_HashLookup(p, pCut->pLeaves[i]) >= 0 )
            return 0;
    return 1;
}
static inline int Kf_SetRemoveDuplicates( Kf_Set_t * p, int nLeaves, word Sign )
{
    Kf_Cut_t * pCut; 
    Kf_ListForEachCut( p, nLeaves, pCut )
        if ( pCut->Sign == Sign && Kf_SetCutDominatedByThis(p, pCut) )
            return 1;
    return 0;
}
static inline void Kf_SetFilter( Kf_Set_t * p )
{
    Kf_Cut_t * pCut0, * pCut1; 
    int i, k, * pPlace;
    assert( p->nCuts > 0 );
    for ( i = 0; i <= p->nLutSize; i++ )
        Kf_ListForEachCutP( p, i, pCut0, pPlace )
        {
            Kf_HashPopulate( p, pCut0 );
            for ( k = 0; k < pCut0->nLeaves; k++ )
                Kf_ListForEachCut( p, k, pCut1 )
                    if ( (pCut0->Sign & pCut1->Sign) == pCut1->Sign && Kf_SetCutDominatedByThis(p, pCut1) )
                        { k = pCut0->nLeaves; p->nCuts--; break; }
            if ( k == pCut0->nLeaves + 1 ) // remove pCut0
                *pPlace = pCut0->iNext;
            else
                pPlace = &pCut0->iNext;
            Kf_HashCleanup( p, 0 );
        }
    assert( p->nCuts > 0 );
}
static inline void Kf_SetMergePairs( Kf_Set_t * p, Kf_Cut_t * pCut0, Kf_Cut_t * pCuts, int nCuts, int fArea )
{
    Kf_Cut_t * pCut1, * pCutR;  int i;
    Kf_HashPopulate( p, pCut0 );
    for ( pCut1 = pCuts; pCut1 < pCuts + nCuts; pCut1++ )
    {
        if ( pCut0->nLeaves + pCut1->nLeaves > p->nLutSize && Kf_SetCountBits(pCut0->Sign | pCut1->Sign) > p->nLutSize )
            continue;
        Kf_HashCleanup( p, pCut0->nLeaves );
        for ( i = 0; i < pCut1->nLeaves; i++ )
            if ( Kf_HashFindOrAdd(p, pCut1->pLeaves[i]) )
                break;
        if ( i < pCut1->nLeaves )
            continue;
        p->CutCount[1]++;        
        if ( Kf_SetRemoveDuplicates(p, p->nTEntries, pCut0->Sign | pCut1->Sign) )
            continue;
        // create new cut
        pCutR = p->pCutsR + p->nCuts++;
        pCutR->nLeaves = p->nTEntries;
        for ( i = 0; i < p->nTEntries; i++ )
            pCutR->pLeaves[i] = p->pTable[p->pPlace[i]];
        pCutR->Sign  = pCut0->Sign | pCut1->Sign;
        pCutR->Delay = Abc_MaxInt(pCut0->Delay, pCut1->Delay);
        pCutR->Area  = pCut0->Area + pCut1->Area;
        // add new cut
        Kf_SetAddToList( p, pCutR, 0 );
    }
    Kf_HashCleanup( p, 0 );
}
static inline void Kf_SetMerge( Kf_Set_t * p, int * pCuts0, int * pCuts1, int fArea, int fCutMin )
{
    int c0, c1;
    Kf_SetPrepare( p, pCuts0, pCuts1 );
    p->CutCount[0] += p->nCuts0 * p->nCuts1;
//    for ( c0 = 1; c0 < p->nCuts0; c0++ )
//        assert( p->pCuts0[c0-1].nLeaves >= p->pCuts0[c0].nLeaves );
    for ( c0 = c1 = 0; c0 < p->nCuts0 && c1 < p->nCuts1; )
    {
        if ( p->pCuts0[c0].nLeaves >= p->pCuts1[c1].nLeaves )
            Kf_SetMergePairs( p, p->pCuts0 + c0++, p->pCuts1 + c1, p->nCuts1 - c1, fArea );
        else 
            Kf_SetMergePairs( p, p->pCuts1 + c1++, p->pCuts0 + c0, p->nCuts0 - c0, fArea );
    }
    p->CutCount[2] += p->nCuts;        
    Kf_SetFilter( p );
//    Kf_CheckCuts( p );
    p->CutCount[3] += Abc_MinInt( p->nCuts, p->nCutNum-1 );
    Kf_SetSelectBest( p, fArea, 1 );
}

/**Function*************************************************************

  Synopsis    [Cut merging with fixed order.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int Kf_SetCutIsContainedSimple( Kf_Cut_t * pBase, Kf_Cut_t * pCut ) // check if pCut is contained in pBase
{
    int nSizeB = pBase->nLeaves;
    int nSizeC = pCut->nLeaves;
    int * pB = pBase->pLeaves;
    int * pC = pCut->pLeaves;
    int i, k;
    assert( nSizeB >= nSizeC ); 
    for ( i = 0; i < nSizeC; i++ )
    {
        for ( k = 0; k < nSizeB; k++ )
            if ( pC[i] == pB[k] )
                break;
        if ( k == nSizeB )
            return 0;
    }
    return 1;
}
static inline int Kf_SetMergeSimpleOne( Kf_Cut_t * pCut0, Kf_Cut_t * pCut1, Kf_Cut_t * pCut, int nLutSize )
{ 
    int nSize0 = pCut0->nLeaves;
    int nSize1 = pCut1->nLeaves;
    int * pC0 = pCut0->pLeaves;
    int * pC1 = pCut1->pLeaves;
    int * pC = pCut->pLeaves;
    int i, k, c;
    // compare two cuts with different numbers
    c = nSize0;
    for ( i = 0; i < nSize1; i++ )
    {
        for ( k = 0; k < nSize0; k++ )
            if ( pC1[i] == pC0[k] )
                break;
        if ( k < nSize0 )
            continue;
        if ( c == nLutSize )
            return 0;
        pC[c++] = pC1[i];
    }
    for ( i = 0; i < nSize0; i++ )
        pC[i] = pC0[i];
    pCut->nLeaves = c;
    return 1;
}
static inline int Kf_SetRemoveDuplicatesSimple( Kf_Set_t * p, Kf_Cut_t * pCutNew )
{
    Kf_Cut_t * pCut;
    Kf_ListForEachCut( p, pCutNew->nLeaves, pCut )
        if ( pCut->Sign == pCutNew->Sign && Kf_SetCutIsContainedSimple(pCut, pCutNew) )
            return 1;
    return 0;
}
static inline void Kf_SetFilterSimple( Kf_Set_t * p )
{
    Kf_Cut_t * pCut0, * pCut1; 
    int i, k, * pPlace;
    assert( p->nCuts > 0 );
    for ( i = 0; i <= p->nLutSize; i++ )
        Kf_ListForEachCutP( p, i, pCut0, pPlace )
        {
            for ( k = 0; k < pCut0->nLeaves; k++ )
                Kf_ListForEachCut( p, k, pCut1 )
                    if ( (pCut0->Sign & pCut1->Sign) == pCut1->Sign && Kf_SetCutIsContainedSimple(pCut0, pCut1) )
                        { k = pCut0->nLeaves; p->nCuts--; break; }
            if ( k == pCut0->nLeaves + 1 ) // remove pCut0
                *pPlace = pCut0->iNext;
            else
                pPlace = &pCut0->iNext;
        }
    assert( p->nCuts > 0 );
}
static inline void Kf_SetMergeSimple( Kf_Set_t * p, int * pCuts0, int * pCuts1, int fArea, int fCutMin )
{
    Kf_Cut_t * pCut0, * pCut1, * pCutR;
    Kf_SetPrepare( p, pCuts0, pCuts1 );
    p->CutCount[0] += p->nCuts0 * p->nCuts1;
    for ( pCut0 = p->pCuts0; pCut0 < p->pCuts0 + p->nCuts0; pCut0++ )
    for ( pCut1 = p->pCuts1; pCut1 < p->pCuts1 + p->nCuts1; pCut1++ )
    {
        if ( pCut0->nLeaves + pCut1->nLeaves > p->nLutSize && Kf_SetCountBits(pCut0->Sign | pCut1->Sign) > p->nLutSize )
            continue;
        p->CutCount[1]++;        
        pCutR = p->pCutsR + p->nCuts;
        if ( !Kf_SetMergeSimpleOne(pCut0, pCut1, pCutR, p->nLutSize) )
            continue;
        p->CutCount[2]++;        
        pCutR->Sign = pCut0->Sign | pCut1->Sign;
        if ( Kf_SetRemoveDuplicatesSimple(p, pCutR) )
            continue;
        p->nCuts++;
        if ( fCutMin )
        {
            int nOldSupp = pCutR->nLeaves;
//            pCutR->iFunc = Kf_SetComputeTruth( p, pCut0->iFunc, pCut1->iFunc, pCut0, pCut1, pCutR );
            assert( pCutR->nLeaves <= nOldSupp );
            if ( pCutR->nLeaves < nOldSupp )
                pCutR->Sign = Kf_SetCutGetSign( pCutR );
            // delay and area are inaccurate
        }
        assert( pCutR->nLeaves > 1 );
        pCutR->Delay = Abc_MaxInt(pCut0->Delay, pCut1->Delay);
        pCutR->Area  = pCut0->Area + pCut1->Area;
        // add new cut
        Kf_SetAddToList( p, pCutR, 0 );
    }
    Kf_SetFilterSimple( p );
//    Kf_CheckCuts( p );
    p->CutCount[3] += Abc_MinInt( p->nCuts, p->nCutNum-1 );
    Kf_SetSelectBest( p, fArea, 1 );
}

/**Function*************************************************************

  Synopsis    [Cut merging with fixed order.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int Kf_SetCutIsContainedOrder( Kf_Cut_t * pBase, Kf_Cut_t * pCut ) // check if pCut is contained in pBase
{
    int nSizeB = pBase->nLeaves;
    int nSizeC = pCut->nLeaves;
    int i, k;
    if ( nSizeB == nSizeC )
    {
        for ( i = 0; i < nSizeB; i++ )
            if ( pBase->pLeaves[i] != pCut->pLeaves[i] )
                return 0;
        return 1;
    }
    assert( nSizeB > nSizeC ); 
    for ( i = k = 0; i < nSizeB; i++ )
    {
        if ( pBase->pLeaves[i] > pCut->pLeaves[k] )
            return 0;
        if ( pBase->pLeaves[i] == pCut->pLeaves[k] )
        {
            if ( ++k == nSizeC )
                return 1;
        }
    }
    return 0;
}
static inline int Kf_SetMergeOrderOne( Kf_Cut_t * pCut0, Kf_Cut_t * pCut1, Kf_Cut_t * pCut, int nLutSize )
{ 
    int nSize0 = pCut0->nLeaves;
    int nSize1 = pCut1->nLeaves;
    int * pC0 = pCut0->pLeaves;
    int * pC1 = pCut1->pLeaves;
    int * pC = pCut->pLeaves;
    int i, k, c;
    // the case of the largest cut sizes
    if ( nSize0 == nLutSize && nSize1 == nLutSize )
    {
        for ( i = 0; i < nSize0; i++ )
        {
            if ( pC0[i] != pC1[i] )  return 0;
            pC[i] = pC0[i];
        }
        pCut->nLeaves = nLutSize;
        return 1;
    }
    // compare two cuts with different numbers
    i = k = c = 0;
    while ( 1 )
    {
        if ( c == nLutSize ) return 0;
        if ( pC0[i] < pC1[k] )
        {
            pC[c++] = pC0[i++];
            if ( i >= nSize0 ) goto FlushCut1;
        }
        else if ( pC0[i] > pC1[k] )
        {
            pC[c++] = pC1[k++];
            if ( k >= nSize1 ) goto FlushCut0;
        }
        else
        {
            pC[c++] = pC0[i++]; k++;
            if ( i >= nSize0 ) goto FlushCut1;
            if ( k >= nSize1 ) goto FlushCut0;
        }
    }

FlushCut0:
    if ( c + nSize0 > nLutSize + i ) return 0;
    while ( i < nSize0 )
        pC[c++] = pC0[i++];
    pCut->nLeaves = c;
    return 1;

FlushCut1:
    if ( c + nSize1 > nLutSize + k ) return 0;
    while ( k < nSize1 )
        pC[c++] = pC1[k++];
    pCut->nLeaves = c;
    return 1;
}
static inline int Kf_SetRemoveDuplicatesOrder( Kf_Set_t * p, Kf_Cut_t * pCutNew )
{
    Kf_Cut_t * pCut;
    Kf_ListForEachCut( p, pCutNew->nLeaves, pCut )
        if ( pCut->Sign == pCutNew->Sign && Kf_SetCutIsContainedOrder(pCut, pCutNew) )
            return 1;
    return 0;
}
static inline void Kf_SetFilterOrder( Kf_Set_t * p )
{
    Kf_Cut_t * pCut0, * pCut1; 
    int i, k, * pPlace;
    assert( p->nCuts > 0 );
    for ( i = 0; i <= p->nLutSize; i++ )
        Kf_ListForEachCutP( p, i, pCut0, pPlace )
        {
            for ( k = 0; k < pCut0->nLeaves; k++ )
                Kf_ListForEachCut( p, k, pCut1 )
                    if ( (pCut0->Sign & pCut1->Sign) == pCut1->Sign && Kf_SetCutIsContainedOrder(pCut0, pCut1) )
                        { k = pCut0->nLeaves; p->nCuts--; break; }
            if ( k == pCut0->nLeaves + 1 ) // remove pCut0
                *pPlace = pCut0->iNext;
            else
                pPlace = &pCut0->iNext;
        }
    assert( p->nCuts > 0 );
}
/*
int Kf_SetComputeTruth( Kf_Man_t * p, int iFuncLit0, int iFuncLit1, int * pCut0, int * pCut1, int * pCutOut )
{
    word uTruth[JF_WORD_MAX], uTruth0[JF_WORD_MAX], uTruth1[JF_WORD_MAX];
    int fCompl, truthId;
    int LutSize    = p->pPars->nLutSize;
    int nWords     = Abc_Truth6WordNum(p->pPars->nLutSize);
    word * pTruth0 = Vec_MemReadEntry(p->vTtMem, Abc_Lit2Var(iFuncLit0));
    word * pTruth1 = Vec_MemReadEntry(p->vTtMem, Abc_Lit2Var(iFuncLit1));
    Abc_TtCopy( uTruth0, pTruth0, nWords, Abc_LitIsCompl(iFuncLit0) );
    Abc_TtCopy( uTruth1, pTruth1, nWords, Abc_LitIsCompl(iFuncLit1) );
    Abc_TtExpand( uTruth0, LutSize, pCut0 + 1, Kf_CutSize(pCut0), pCutOut + 1, Kf_CutSize(pCutOut) );
    Abc_TtExpand( uTruth1, LutSize, pCut1 + 1, Kf_CutSize(pCut1), pCutOut + 1, Kf_CutSize(pCutOut) );
    fCompl         = (int)(uTruth0[0] & uTruth1[0] & 1);
    Abc_TtAnd( uTruth, uTruth0, uTruth1, nWords, fCompl );
    pCutOut[0]     = Abc_TtMinBase( uTruth, pCutOut + 1, pCutOut[0], LutSize );
    assert( (uTruth[0] & 1) == 0 );
    truthId        = Vec_MemHashInsert(p->vTtMem, uTruth);
    return Abc_Var2Lit( truthId, fCompl );
}
*/
static inline void Kf_SetMergeOrder( Kf_Set_t * p, int * pCuts0, int * pCuts1, int fArea, int fCutMin )
{
    Kf_Cut_t * pCut0, * pCut1, * pCutR;
    Kf_SetPrepare( p, pCuts0, pCuts1 );
    p->CutCount[0] += p->nCuts0 * p->nCuts1;
    for ( pCut0 = p->pCuts0; pCut0 < p->pCuts0 + p->nCuts0; pCut0++ )
    for ( pCut1 = p->pCuts1; pCut1 < p->pCuts1 + p->nCuts1; pCut1++ )
    {
        if ( pCut0->nLeaves + pCut1->nLeaves > p->nLutSize && Kf_SetCountBits(pCut0->Sign | pCut1->Sign) > p->nLutSize )
            continue;
        p->CutCount[1]++;        
        pCutR = p->pCutsR + p->nCuts;
        if ( !Kf_SetMergeOrderOne(pCut0, pCut1, pCutR, p->nLutSize) )
            continue;
        p->CutCount[2]++;        
        pCutR->Sign = pCut0->Sign | pCut1->Sign;
        if ( Kf_SetRemoveDuplicatesOrder(p, pCutR) )
            continue;
        p->nCuts++;
        if ( fCutMin )
        {
            int nOldSupp = pCutR->nLeaves;
//            pCutR->iFunc = Kf_SetComputeTruth( p, pCut0->iFunc, pCut1->iFunc, pCut0, pCut1, pCutR );
            assert( pCutR->nLeaves <= nOldSupp );
            if ( pCutR->nLeaves < nOldSupp )
                pCutR->Sign = Kf_SetCutGetSign( pCutR );
            // delay and area are inaccurate
        }
        assert( pCutR->nLeaves > 1 );
        pCutR->Delay = Abc_MaxInt(pCut0->Delay, pCut1->Delay);
        pCutR->Area  = pCut0->Area + pCut1->Area;
        // add new cut
        Kf_SetAddToList( p, pCutR, 0 );
    }
    Kf_SetFilterOrder( p );
//    Kf_CheckCuts( p );
    p->CutCount[3] += Abc_MinInt( p->nCuts, p->nCutNum-1 );
    Kf_SetSelectBest( p, fArea, 1 );
}


/**Function*************************************************************

  Synopsis    [Cut operations.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
static inline int  Kf_CutSize( int * pCut )         { return pCut[0];                          } 
static inline int  Kf_CutFunc( int * pCut )         { return pCut[pCut[0] + 1];                } 
static inline int  Kf_CutLeaf( int * pCut, int i )  { assert(i); return Abc_Lit2Var(pCut[i]);  }
static inline int  Kf_CutTime( Kf_Man_t * p, int * pCut )
{
    int i, Time = 0;
    for ( i = 1; i <= Kf_CutSize(pCut); i++ )
        Time = Abc_MaxInt( Time, Kf_ObjTime(p, Kf_CutLeaf(pCut, i)) );
    return Time + 1; 
}
static inline void Kf_CutRef( Kf_Man_t * p, int * pCut )
{
    int i;
    for ( i = 1; i <= Kf_CutSize(pCut); i++ )
        Gia_ObjRefIncId( p->pGia, Kf_CutLeaf(pCut, i) );
}
static inline void Kf_CutDeref( Kf_Man_t * p, int * pCut )
{
    int i;
    for ( i = 1; i <= Kf_CutSize(pCut); i++ )
        Gia_ObjRefDecId( p->pGia, Kf_CutLeaf(pCut, i) );
}
static inline void Kf_CutPrint( int * pCut )
{
    int i; 
    printf( "%d {", Kf_CutSize(pCut) );
    for ( i = 1; i <= Kf_CutSize(pCut); i++ )
        printf( " %d", Kf_CutLeaf(pCut, i) );
    printf( " } Func = %d\n", Kf_CutFunc(pCut) );
}
static inline void Gia_CutSetPrint( int * pCuts )
{
    int i, * pCut; 
    Kf_ObjForEachCutInt( pCuts, pCut, i )
        Kf_CutPrint( pCut );
    printf( "\n" );
}

/**Function*************************************************************

  Synopsis    [Computing delay/area.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Kf_ManComputeDelay( Kf_Man_t * p, int fEval )
{
    Gia_Obj_t * pObj; 
    int i, Delay = 0;
    if ( fEval )
    {
        Gia_ManForEachAnd( p->pGia, pObj, i )
            if ( Gia_ObjRefNum(p->pGia, pObj) > 0 )
                Vec_IntWriteEntry( &p->vTime, i, Kf_CutTime(p, Kf_ObjCutBest(p, i)) );
    }
    Gia_ManForEachCoDriver( p->pGia, pObj, i )
    {
        assert( Gia_ObjRefNum(p->pGia, pObj) > 0 );
        Delay = Abc_MaxInt( Delay, Kf_ObjTime(p, Gia_ObjId(p->pGia, pObj)) );
    }
    return Delay;
}
int Kf_ManComputeRefs( Kf_Man_t * p )
{
    Gia_Obj_t * pObj; 
    float nRefsNew; int i, * pCut;
    float * pRefs = Vec_FltArray(&p->vRefs);
    float * pFlow = Vec_FltArray(&p->vArea);
    assert( p->pGia->pRefs != NULL );
    memset( p->pGia->pRefs, 0, sizeof(int) * Gia_ManObjNum(p->pGia) );
    p->pPars->Area = p->pPars->Edge = 0;
    Gia_ManForEachObjReverse( p->pGia, pObj, i )
    {
        if ( Gia_ObjIsCo(pObj) || Gia_ObjIsBuf(pObj) )
            Gia_ObjRefInc( p->pGia, Gia_ObjFanin0(pObj) );
        else if ( Gia_ObjIsAnd(pObj) && Gia_ObjRefNum(p->pGia, pObj) > 0 )
        {
            pCut = Kf_ObjCutBest(p, i);
            Kf_CutRef( p, pCut );
            p->pPars->Edge += Kf_CutSize(pCut);
            p->pPars->Area++;
        }
    }
    // blend references and normalize flow
    for ( i = 0; i < Gia_ManObjNum(p->pGia); i++ )
    {
        if ( p->pPars->fOptEdge )
            nRefsNew = Abc_MaxFloat( 1, 0.8 * pRefs[i] + 0.2 * p->pGia->pRefs[i] );
        else
            nRefsNew = Abc_MaxFloat( 1, 0.2 * pRefs[i] + 0.8 * p->pGia->pRefs[i] );
        pFlow[i] = pFlow[i] * pRefs[i] / nRefsNew;
        pRefs[i] = nRefsNew;
        assert( pFlow[i] >= 0 );
    }
    // compute delay
    p->pPars->Delay = Kf_ManComputeDelay( p, 1 );
    return p->pPars->Area;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
#define PAR_THR_MAX 100
typedef struct Kf_ThData_t_
{
    Kf_Set_t *  pSett;
    int         Id;
    int         Status;
    abctime     clkUsed;
} Kf_ThData_t;
void * Kf_WorkerThread( void * pArg )
{
    Kf_ThData_t * pThData = (Kf_ThData_t *)pArg;
    Kf_Man_t * pMan = pThData->pSett->pMan;
    int fAreaOnly = pThData->pSett->pMan->pPars->fAreaOnly;
    int fCutMin = pThData->pSett->pMan->pPars->fCutMin;
    volatile int * pPlace = &pThData->Status;
    abctime clk;
    while ( 1 )
    {
        while ( *pPlace == 0 );
        assert( pThData->Status == 1 );
        if ( pThData->Id == -1 )
        {
            pthread_exit( NULL );
            assert( 0 );
            return NULL;
        }
        assert( pThData->Id >= 0 );
        clk = Abc_Clock();
        Kf_SetMergeOrder( pThData->pSett, Kf_ObjCuts0(pMan, pThData->Id), Kf_ObjCuts1(pMan, pThData->Id), fAreaOnly, fCutMin );
        pThData->clkUsed += Abc_Clock() - clk;
        pThData->Status = 0;
//        printf( "Finished object %d\n", pThData->Id );
    }
    assert( 0 );
    return NULL;
}
Vec_Int_t * Kf_ManCreateFaninCounts( Gia_Man_t * p )  
{
    Vec_Int_t * vCounts;
    Gia_Obj_t * pObj; int i;
    vCounts = Vec_IntAlloc( Gia_ManObjNum(p) );
    Gia_ManForEachObj( p, pObj, i )
    {
        if ( Gia_ObjIsAnd(pObj) )
            Vec_IntPush( vCounts, 2 - Gia_ObjIsCi(Gia_ObjFanin0(pObj)) - Gia_ObjIsCi(Gia_ObjFanin1(pObj)) );
        else
            Vec_IntPush( vCounts, 0 );
    }
    assert( Vec_IntSize(vCounts) == Gia_ManObjNum(p) );
    return vCounts;
}
void Kf_ManComputeCuts( Kf_Man_t * p )
{
    pthread_t WorkerThread[PAR_THR_MAX];
    Kf_ThData_t ThData[PAR_THR_MAX];
    Vec_Int_t * vStack, * vFanins;
    Gia_Obj_t * pObj;
    int nProcs = p->pPars->nProcNum;
    int i, k, iFan, status, nCountFanins, fRunning;
    abctime clk, clkUsed = 0;
    assert( nProcs <= PAR_THR_MAX );
    // start fanins
    vFanins = Kf_ManCreateFaninCounts( p->pGia );
    Gia_ManStaticFanoutStart( p->pGia );
    // start the stack
    vStack = Vec_IntAlloc( 1000 );
    Gia_ManForEachObjReverse( p->pGia, pObj, k )
        if ( Gia_ObjIsAnd(pObj) && Vec_IntEntry(vFanins, k) == 0 )
            Vec_IntPush( vStack, k );
    // start the threads
    for ( i = 0; i < nProcs; i++ )
    {
        ThData[i].pSett = p->pSett + i;
        ThData[i].Id = -1;
        ThData[i].Status = 0;
        ThData[i].clkUsed = 0;
        status = pthread_create( WorkerThread + i, NULL, Kf_WorkerThread, (void *)(ThData + i) );  assert( status == 0 );
    }
    nCountFanins = Vec_IntSum(vFanins);
    fRunning = 1;
    while ( nCountFanins > 0 || Vec_IntSize(vStack) > 0 || fRunning )
    {
        for ( i = 0; i < nProcs; i++ )
        {
            if ( ThData[i].Status )
                continue;
            assert( ThData[i].Status == 0 );
            if ( ThData[i].Id >= 0 )
            {
                int iObj = ThData[i].Id;
                Kf_Set_t * pSett = p->pSett + i;
                //printf( "Closing obj %d with Thread %d:\n", iObj, i );
                clk = Abc_Clock();
                // finalize the results
                Kf_ManSaveResults( pSett->ppCuts, pSett->nCuts, pSett->pCutBest, p->vTemp );
                Vec_IntWriteEntry( &p->vTime, iObj, pSett->pCutBest->Delay + 1 );
                Vec_FltWriteEntry( &p->vArea, iObj, (pSett->pCutBest->Area + 1)/Kf_ObjRefs(p, iObj) );
                if ( pSett->pCutBest->nLeaves > 1 )
                    Kf_ManStoreAddUnit( p->vTemp, iObj, Kf_ObjTime(p, iObj), Kf_ObjArea(p, iObj) );
                Kf_ObjSetCuts( p, iObj, p->vTemp );
                //Gia_CutSetPrint( Kf_ObjCuts(p, iObj) );
                clkUsed += Abc_Clock() - clk;
                // schedule other nodes
                Gia_ObjForEachFanoutStaticId( p->pGia, iObj, iFan, k )
                {
                    if ( !Gia_ObjIsAnd(Gia_ManObj(p->pGia, iFan)) )
                        continue;
                    assert( Vec_IntEntry(vFanins, iFan) > 0 );
                    if ( Vec_IntAddToEntry(vFanins, iFan, -1) == 0 )
                        Vec_IntPush( vStack, iFan );
                    assert( nCountFanins > 0 );
                    nCountFanins--;
                }
                ThData[i].Id = -1;
            }
            if ( Vec_IntSize(vStack) > 0 )
            {
                ThData[i].Id = Vec_IntPop( vStack );
                ThData[i].Status = 1;
                //printf( "Scheduling %d for Thread %d\n", ThData[i].Id, i );
            }
        }
        fRunning = 0;
        for ( i = 0; i < nProcs; i++ )
            if ( ThData[i].Status == 1 || (ThData[i].Status == 0 && ThData[i].Id >= 0) )
                fRunning = 1;
//        printf( "fRunning %d\n", fRunning );
    }
    Vec_IntForEachEntry( vFanins, iFan, k )
        if ( iFan != 0 )
        {
            printf( "%d -> %d    ", k, iFan );
            Gia_ObjPrint( p->pGia, Gia_ManObj(p->pGia, k) );
        }
    assert( Vec_IntSum(vFanins) == 0 );
    // stop the threads
    for ( i = 0; i < nProcs; i++ )
    {
        assert( ThData[i].Status == 0 );
        ThData[i].Id = -1;
        ThData[i].Status = 1;
    }
    Gia_ManStaticFanoutStop( p->pGia );
    Vec_IntFree( vStack );
    Vec_IntFree( vFanins );
    if ( !p->pPars->fVerbose )
        return;
    // print runtime statistics
    printf( "Main     : " );
    Abc_PrintTime( 1, "Time", clkUsed );
    for ( i = 0; i < nProcs; i++ )
    {
        printf( "Thread %d : ", i );
        Abc_PrintTime( 1, "Time", ThData[i].clkUsed );
    }

}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Kf_ManPrintStats( Kf_Man_t * p, char * pTitle )
{
    if ( !p->pPars->fVerbose )
        return;
    printf( "%s :  ", pTitle );
    printf( "Level =%6lu   ", p->pPars->Delay );
    printf( "Area =%9lu   ",  p->pPars->Area );
    printf( "Edge =%9lu   ",  p->pPars->Edge );
    Abc_PrintTime( 1, "Time", Abc_Clock() - p->clkStart );
    fflush( stdout );
}
void Kf_ManComputeMapping( Kf_Man_t * p )
{
    Gia_Obj_t * pObj; int i, iPi;
    if ( p->pPars->fVerbose )
    {
        printf( "Aig: CI = %d  CO = %d  AND = %d    ", Gia_ManCiNum(p->pGia), Gia_ManCoNum(p->pGia), Gia_ManAndNum(p->pGia) );
        printf( "LutSize = %d  CutMax = %d  Threads = %d\n", p->pPars->nLutSize, p->pPars->nCutNum, p->pPars->nProcNum );
        printf( "Computing cuts...\r" );
        fflush( stdout );
    }
    Gia_ManForEachCi( p->pGia, pObj, iPi )
    {
        i = Gia_ObjId(p->pGia, pObj);
        Kf_ManStoreStart( p->vTemp, 0 );
        Kf_ManStoreAddUnit( p->vTemp, i, 0, 0 );
        assert( Vec_IntSize(p->vTemp) == 1 + KF_ADD_ON1 + KF_ADD_ON2 );
        Kf_ObjSetCuts( p, i, p->vTemp );
    }
    if ( p->pPars->nProcNum > 0 )
        Kf_ManComputeCuts( p );
    else
    {
        Gia_ManForEachAnd( p->pGia, pObj, i )
        {
            if ( p->pPars->fCutHashing )
                Kf_SetMerge( p->pSett, Kf_ObjCuts0(p, i), Kf_ObjCuts1(p, i), p->pPars->fAreaOnly, p->pPars->fCutMin );
            else if ( p->pPars->fCutSimple )
                Kf_SetMergeSimple( p->pSett, Kf_ObjCuts0(p, i), Kf_ObjCuts1(p, i), p->pPars->fAreaOnly, p->pPars->fCutMin );
            else 
                Kf_SetMergeOrder( p->pSett, Kf_ObjCuts0(p, i), Kf_ObjCuts1(p, i), p->pPars->fAreaOnly, p->pPars->fCutMin );
            Kf_ManSaveResults( p->pSett->ppCuts, p->pSett->nCuts, p->pSett->pCutBest, p->vTemp );
            Vec_IntWriteEntry( &p->vTime, i, p->pSett->pCutBest->Delay + 1 );
            Vec_FltWriteEntry( &p->vArea, i, (p->pSett->pCutBest->Area + 1)/Kf_ObjRefs(p, i) );
            if ( p->pSett->pCutBest->nLeaves > 1 )
                Kf_ManStoreAddUnit( p->vTemp, i, Kf_ObjTime(p, i), Kf_ObjArea(p, i) );
            Kf_ObjSetCuts( p, i, p->vTemp );
            //Gia_CutSetPrint( Kf_ObjCuts(p, i) );
        }
    }
    Kf_ManComputeRefs( p );
    if ( p->pPars->fVerbose )
    {
        printf( "CutPair = %lu  ", p->pSett->CutCount[0] );
        printf( "Merge = %lu  ",   p->pSett->CutCount[1] );
        printf( "Eval = %lu  ",    p->pSett->CutCount[2] );
        printf( "Cut = %lu  ",     p->pSett->CutCount[3] );
        Abc_PrintTime( 1, "Time",  Abc_Clock() - p->clkStart );
        printf( "Memory:  " );
        printf( "Gia = %.2f MB  ", Gia_ManMemory(p->pGia) / (1<<20) );
        printf( "Man = %.2f MB  ", 4.0 * sizeof(int) * Gia_ManObjNum(p->pGia) / (1<<20) );
        printf( "Cuts = %.2f MB  ",Vec_ReportMemory(&p->pMem) / (1<<20) );
        printf( "Set = %.2f KB  ", 1.0 * sizeof(Kf_Set_t) / (1<<10) );
        printf( "\n" );
        fflush( stdout );
        Kf_ManPrintStats( p, "Start" );
    }
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Kf_ManSetInitRefs( Gia_Man_t * p, Vec_Flt_t * vRefs )
{
    Gia_Obj_t * pObj, * pCtrl, * pData0, * pData1; int i;
    Vec_FltFill( vRefs, Gia_ManObjNum(p), 0 );
    Gia_ManForEachAnd( p, pObj, i )
    {
        Vec_FltAddToEntry( vRefs, Gia_ObjFaninId0(pObj, i), 1 );
        Vec_FltAddToEntry( vRefs, Gia_ObjFaninId1(pObj, i), 1 );
        if ( !Gia_ObjIsMuxType(pObj) )
            continue;
        // discount XOR/MUX
        pCtrl = Gia_ObjRecognizeMux( pObj, &pData1, &pData0 );
        Vec_FltAddToEntry( vRefs, Gia_ObjId(p, Gia_Regular(pCtrl)), -1 );
        if ( Gia_Regular(pData0) == Gia_Regular(pData1) )
            Vec_FltAddToEntry( vRefs, Gia_ObjId(p, Gia_Regular(pData0)), -1 );
    }
    Gia_ManForEachCo( p, pObj, i )
        Vec_FltAddToEntry( vRefs, Gia_ObjFaninId0(pObj, Gia_ObjId(p, pObj)), 1 );
    for ( i = 0; i < Gia_ManObjNum(p); i++ )
        Vec_FltUpdateEntry( vRefs, i, 1 );
}
Kf_Man_t * Kf_ManAlloc( Gia_Man_t * pGia, Jf_Par_t * pPars )
{
    Kf_Man_t * p; int i;
    assert( pPars->nLutSize <= KF_LEAF_MAX );
    assert( pPars->nCutNum  <= KF_CUT_MAX  );
    assert( pPars->nProcNum <= KF_PROC_MAX );
    Vec_IntFreeP( &pGia->vMapping );
    p = ABC_CALLOC( Kf_Man_t, 1 );
    p->clkStart  = Abc_Clock();
    p->pGia      = pGia;
    p->pPars     = pPars;
    Vec_SetAlloc_( &p->pMem, 20 );
    Vec_IntFill( &p->vCuts, Gia_ManObjNum(pGia), 0 );
    Vec_IntFill( &p->vTime, Gia_ManObjNum(pGia), 0 );
    Vec_FltFill( &p->vArea, Gia_ManObjNum(pGia), 0 );
    Kf_ManSetInitRefs( pGia, &p->vRefs );
    p->vTemp     = Vec_IntAlloc( 1000 );
    pGia->pRefs  = ABC_CALLOC( int, Gia_ManObjNum(pGia) );
    // prepare cut sets
    for ( i = 0; i < Abc_MaxInt(1, pPars->nProcNum); i++ )
    {
        (p->pSett + i)->pMan      = p;
        (p->pSett + i)->nLutSize  = (unsigned short)pPars->nLutSize;
        (p->pSett + i)->nCutNum   = (unsigned short)pPars->nCutNum;
        (p->pSett + i)->TableMask = (1 << KF_LOG_TABLE) - 1;
    }
    return p;
}
void Kf_ManFree( Kf_Man_t * p )
{
    ABC_FREE( p->pGia->pRefs );
    ABC_FREE( p->vCuts.pArray );
    ABC_FREE( p->vTime.pArray );
    ABC_FREE( p->vArea.pArray );
    ABC_FREE( p->vRefs.pArray );
    Vec_IntFreeP( &p->vTemp );
    Vec_SetFree_( &p->pMem );
    ABC_FREE( p );
}
Gia_Man_t * Kf_ManDerive( Kf_Man_t * p )
{
    Vec_Int_t * vMapping;
    Gia_Obj_t * pObj; 
    int i, k, * pCut;
    assert( !p->pPars->fCutMin );
    vMapping = Vec_IntAlloc( Gia_ManObjNum(p->pGia) + (int)p->pPars->Edge + (int)p->pPars->Area * 2 );
    Vec_IntFill( vMapping, Gia_ManObjNum(p->pGia), 0 );
    Gia_ManForEachAnd( p->pGia, pObj, i )
    {
        if ( Gia_ObjIsBuf(pObj) || Gia_ObjRefNum(p->pGia, pObj) == 0 )
            continue;
        pCut = Kf_ObjCutBest( p, i );
        Vec_IntWriteEntry( vMapping, i, Vec_IntSize(vMapping) );
        Vec_IntPush( vMapping, Kf_CutSize(pCut) );
        for ( k = 1; k <= Kf_CutSize(pCut); k++ )
            Vec_IntPush( vMapping, Kf_CutLeaf(pCut, k) );
        Vec_IntPush( vMapping, i );
    }
    assert( Vec_IntCap(vMapping) == 16 || Vec_IntSize(vMapping) == Vec_IntCap(vMapping) );
    p->pGia->vMapping = vMapping;
//    Gia_ManMappingVerify( p->pGia );
    return p->pGia;
}

/**Function*************************************************************

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Kf_ManSetDefaultPars( Jf_Par_t * pPars )
{
    memset( pPars, 0, sizeof(Jf_Par_t) );
    pPars->nLutSize     =  6;
    pPars->nCutNum      =  8;
    pPars->nProcNum     =  0;
    pPars->nRounds      =  1;
    pPars->nVerbLimit   =  5;
    pPars->DelayTarget  = -1;
    pPars->fAreaOnly    =  0;
    pPars->fOptEdge     =  1; 
    pPars->fCoarsen     =  0;
    pPars->fCutMin      =  0;
    pPars->fFuncDsd     =  0;
    pPars->fGenCnf      =  0;
    pPars->fPureAig     =  0;
    pPars->fCutHashing  =  0;
    pPars->fCutSimple   =  0;
    pPars->fVerbose     =  0;
    pPars->fVeryVerbose =  0;
    pPars->nLutSizeMax  =  KF_LEAF_MAX;
    pPars->nCutNumMax   =  KF_CUT_MAX;
    pPars->nProcNumMax  =  KF_PROC_MAX;
}
Gia_Man_t * Kf_ManPerformMapping( Gia_Man_t * pGia, Jf_Par_t * pPars )
{
    Kf_Man_t * p;
    Gia_Man_t * pNew;
    p = Kf_ManAlloc( pGia, pPars );
    Kf_ManComputeMapping( p );
    pNew = Kf_ManDerive( p );
    Kf_ManFree( p );
    return pNew;
}

////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////

#endif // pthreads are used

ABC_NAMESPACE_IMPL_END