fpgaCut.c

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

  FileName    [fpgaCut.c]

  PackageName [MVSIS 1.3: Multi-valued logic synthesis system.]

  Synopsis    [Generic technology mapping engine.]

  Author      [MVSIS Group]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 2.0. Started - August 18, 2004.]

  Revision    [$Id: fpgaCut.c,v 1.3 2004/07/06 04:55:57 alanmi Exp $]

***********************************************************************/
 
#include "fpgaInt.h"

ABC_NAMESPACE_IMPL_START


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

typedef struct Fpga_CutTableStrutct_t Fpga_CutTable_t;
struct Fpga_CutTableStrutct_t
{
    Fpga_Cut_t ** pBins;        // the table used for linear probing
    int           nBins;        // the size of the table
    int *         pCuts;        // the array of cuts currently stored 
    int           nCuts;        // the number of cuts currently stored 
    Fpga_Cut_t ** pArray;       // the temporary array of cuts
    Fpga_Cut_t ** pCuts1;       // the temporary array of cuts
    Fpga_Cut_t ** pCuts2;       // the temporary array of cuts
};

// the largest number of cuts considered
//#define  FPGA_CUTS_MAX_COMPUTE   500
#define  FPGA_CUTS_MAX_COMPUTE   2000
// the largest number of cuts used
//#define  FPGA_CUTS_MAX_USE       200
#define  FPGA_CUTS_MAX_USE       1000

// primes used to compute the hash key
static int s_HashPrimes[10] = { 109, 499, 557, 619, 631, 709, 797, 881, 907, 991 };

static int bit_count[256] = {
  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,
  1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
  1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
  2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
  1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
  2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
  2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
  3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
};

#define FPGA_COUNT_ONES(u) (bit_count[(u)&255]+bit_count[((u)>>8)&255]+bit_count[((u)>>16)&255]+bit_count[(u)>>24])

static Fpga_Cut_t *      Fpga_CutCompute( Fpga_Man_t * p, Fpga_CutTable_t * pTable, Fpga_Node_t * pNode );
static void              Fpga_CutFilter( Fpga_Man_t * p, Fpga_Node_t * pNode );
static Fpga_Cut_t *      Fpga_CutMergeLists( Fpga_Man_t * p, Fpga_CutTable_t * pTable, Fpga_Cut_t * pList1, Fpga_Cut_t * pList2, int fComp1, int fComp2, int fPivot1, int fPivot2 );
static int               Fpga_CutMergeTwo( Fpga_Cut_t * pCut1, Fpga_Cut_t * pCut2, Fpga_Node_t * ppNodes[], int nNodesMax );
static Fpga_Cut_t *      Fpga_CutUnionLists( Fpga_Cut_t * pList1, Fpga_Cut_t * pList2 );
static int               Fpga_CutBelongsToList( Fpga_Cut_t * pList, Fpga_Node_t * ppNodes[], int nNodes );
extern Fpga_Cut_t *      Fpga_CutAlloc( Fpga_Man_t * p );
extern int               Fpga_CutCountAll( Fpga_Man_t * pMan );

static void              Fpga_CutListPrint( Fpga_Man_t * pMan, Fpga_Node_t * pRoot );
static void              Fpga_CutListPrint2( Fpga_Man_t * pMan, Fpga_Node_t * pRoot );
static void              Fpga_CutPrint_( Fpga_Man_t * pMan, Fpga_Cut_t * pCut, Fpga_Node_t * pRoot );

static Fpga_CutTable_t * Fpga_CutTableStart( Fpga_Man_t * pMan );
static void              Fpga_CutTableStop( Fpga_CutTable_t * p );
static unsigned          Fpga_CutTableHash( Fpga_Node_t * ppNodes[], int nNodes );
static int               Fpga_CutTableLookup( Fpga_CutTable_t * p, Fpga_Node_t * ppNodes[], int nNodes );
static Fpga_Cut_t *      Fpga_CutTableConsider( Fpga_Man_t * pMan, Fpga_CutTable_t * p, Fpga_Node_t * ppNodes[], int nNodes );
static void              Fpga_CutTableRestart( Fpga_CutTable_t * p );

static int               Fpga_CutSortCutsCompare( Fpga_Cut_t ** pC1, Fpga_Cut_t ** pC2 );
static Fpga_Cut_t *      Fpga_CutSortCuts( Fpga_Man_t * pMan, Fpga_CutTable_t * p, Fpga_Cut_t * pList );
static int               Fpga_CutList2Array( Fpga_Cut_t ** pArray, Fpga_Cut_t * pList );
static Fpga_Cut_t *      Fpga_CutArray2List( Fpga_Cut_t ** pArray, int nCuts );


// iterator through all the cuts of the list
#define Fpga_ListForEachCut( pList, pCut )                \
    for ( pCut = pList;                                   \
          pCut;                                           \
          pCut = pCut->pNext )
#define Fpga_ListForEachCutSafe( pList, pCut, pCut2 )     \
    for ( pCut = pList,                                   \
          pCut2 = pCut? pCut->pNext: NULL;                \
          pCut;                                           \
          pCut = pCut2,                                   \
          pCut2 = pCut? pCut->pNext: NULL )


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

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

  Synopsis    [Computes the cuts for each node in the object graph.]

  Description [The cuts are computed in one sweep over the mapping graph. 
  First, the elementary cuts, which include the node itself, are assigned 
  to the PI nodes. The internal nodes are considered in the DFS order.
  Each node is two-input AND-gate. So to compute the cuts at a node, we
  need to merge the sets of cuts of its two predecessors. The merged set
  contains only unique cuts with the number of inputs equal to k or less.
  Finally, the elementary cut, composed of the node itself, is added to
  the set of cuts for the node.
  
  This procedure is pretty fast for 5-feasible cuts, but it dramatically
  slows down on some "dense" networks when computing 6-feasible cuts.
  The problem is that there are too many cuts in this case. We should
  think how to heuristically trim the number of cuts in such cases, 
  to have reasonable runtime.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fpga_MappingCuts( Fpga_Man_t * p )
{
    ProgressBar * pProgress;
    Fpga_CutTable_t * pTable;
    Fpga_Node_t * pNode;
    int nCuts, nNodes, i;
    clock_t clk = clock();

    // set the elementary cuts for the PI variables
    assert( p->nVarsMax > 1 && p->nVarsMax < 11 );
    Fpga_MappingCreatePiCuts( p );

    // compute the cuts for the internal nodes
    nNodes = p->vAnds->nSize;
    pProgress = Extra_ProgressBarStart( stdout, nNodes );
    pTable = Fpga_CutTableStart( p );
    for ( i = 0; i < nNodes; i++ )
    {
        Extra_ProgressBarUpdate( pProgress, i, "Cuts ..." );
        pNode = p->vAnds->pArray[i];
        if ( !Fpga_NodeIsAnd( pNode ) )
            continue;
        Fpga_CutCompute( p, pTable, pNode );
    }
    Extra_ProgressBarStop( pProgress );
    Fpga_CutTableStop( pTable );

    // report the stats
    if ( p->fVerbose )
    {
        nCuts = Fpga_CutCountAll(p);
        printf( "Nodes = %6d. Total %d-cuts = %d. Cuts per node = %.1f. ", 
               p->nNodes, p->nVarsMax, nCuts, ((float)nCuts)/p->nNodes );
        ABC_PRT( "Time", clock() - clk );
    }

    // print the cuts for the first primary output
//    Fpga_CutListPrint( p, Fpga_Regular(p->pOutputs[0]) );
}

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

  Synopsis    [Performs technology mapping for variable-size-LUTs.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fpga_MappingCreatePiCuts( Fpga_Man_t * p )
{
    Fpga_Cut_t * pCut;
    int i;

    // set the elementary cuts for the PI variables
    for ( i = 0; i < p->nInputs; i++ )
    {
        pCut = Fpga_CutAlloc( p );
        pCut->nLeaves = 1;
        pCut->ppLeaves[0] = p->pInputs[i];
        pCut->uSign = (1 << (i%31));
        p->pInputs[i]->pCuts   = pCut;
        p->pInputs[i]->pCutBest = pCut;
        // set the input arrival times
//        p->pInputs[i]->pCut[1]->tArrival = p->pInputArrivals[i];
    }
}

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

  Synopsis    [Computes the cuts for one node.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Fpga_Cut_t * Fpga_CutCompute( Fpga_Man_t * p, Fpga_CutTable_t * pTable, Fpga_Node_t * pNode )
{
    Fpga_Node_t * pTemp;
    Fpga_Cut_t * pList, * pList1, * pList2;
    Fpga_Cut_t * pCut;
    int fTree = 0;
    int fPivot1 = fTree && (Fpga_NodeReadRef(pNode->p1)>2);
    int fPivot2 = fTree && (Fpga_NodeReadRef(pNode->p2)>2);

    // if the cuts are computed return them
    if ( pNode->pCuts )
        return pNode->pCuts;

    // compute the cuts for the children
    pList1 = Fpga_Regular(pNode->p1)->pCuts;
    pList2 = Fpga_Regular(pNode->p2)->pCuts;
    // merge the lists
    pList = Fpga_CutMergeLists( p, pTable, pList1, pList2, 
        Fpga_IsComplement(pNode->p1), Fpga_IsComplement(pNode->p2),
        fPivot1, fPivot2 );
    // if there are functionally equivalent nodes, union them with this list
    assert( pList );
    // only add to the list of cuts if the node is a representative one
    if ( pNode->pRepr == NULL )
    {
        for ( pTemp = pNode->pNextE; pTemp; pTemp = pTemp->pNextE )
        {
            assert( pTemp->pCuts );
            pList = Fpga_CutUnionLists( pList, pTemp->pCuts );
            assert( pTemp->pCuts );
            pList = Fpga_CutSortCuts( p, pTable, pList );
        }
    }
    // add the new cut
    pCut = Fpga_CutAlloc( p );
    pCut->nLeaves = 1;
    pCut->ppLeaves[0] = pNode;
    pCut->uSign = (1 << (pNode->Num%31));
    pCut->fLevel = (float)pCut->ppLeaves[0]->Level;
    // append (it is important that the elementary cut is appended first)
    pCut->pNext = pList;
    // set at the node
    pNode->pCuts = pCut;
    // remove the dominated cuts
//    Fpga_CutFilter( p, pNode );
    // set the phase correctly
    if ( pNode->pRepr && Fpga_NodeComparePhase(pNode, pNode->pRepr) )
    {
        Fpga_ListForEachCut( pNode->pCuts, pCut )
            pCut->Phase = 1;
    }


/*
    { 
        Fpga_Cut_t * pPrev;
        int i, Counter = 0;
        for ( pCut = pNode->pCuts->pNext, pPrev = pNode->pCuts; pCut; pCut = pCut->pNext )
        {
            for ( i = 0; i < pCut->nLeaves; i++ )
                if ( pCut->ppLeaves[i]->Level >= pNode->Level )
                    break;
            if ( i != pCut->nLeaves )
                pPrev->pNext = pCut->pNext;
            else 
                pPrev = pCut; 
        }
    }
    { 
        int i, Counter = 0;;
        for ( pCut = pNode->pCuts->pNext; pCut; pCut = pCut->pNext )
            for ( i = 0; i < pCut->nLeaves; i++ )
                Counter += (pCut->ppLeaves[i]->Level >= pNode->Level);
        if ( Counter )
            printf( " %d", Counter );
    }
*/

    return pCut;
}

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

  Synopsis    [Filter the cuts using dominance.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fpga_CutFilter( Fpga_Man_t * p, Fpga_Node_t * pNode )
{ 
    Fpga_Cut_t * pTemp, * pPrev, * pCut, * pCut2;
    int i, k, Counter;

    Counter = 0;
    pPrev = pNode->pCuts;
    Fpga_ListForEachCutSafe( pNode->pCuts->pNext, pCut, pCut2 )
    {
        // go through all the previous cuts up to pCut
        for ( pTemp = pNode->pCuts->pNext; pTemp != pCut; pTemp = pTemp->pNext )
        {
            // check if every node in pTemp is contained in pCut
            for ( i = 0; i < pTemp->nLeaves; i++ )
            {
                for ( k = 0; k < pCut->nLeaves; k++ )
                    if ( pTemp->ppLeaves[i] == pCut->ppLeaves[k] )
                        break;
                if ( k == pCut->nLeaves ) // node i in pTemp is not contained in pCut
                    break;
            }
            if ( i == pTemp->nLeaves ) // every node in pTemp is contained in pCut
            {
                Counter++;
                break;
            }
        }
        if ( pTemp != pCut ) // pTemp contain pCut
        {
            pPrev->pNext = pCut->pNext;  // skip pCut
            // recycle pCut
            Fpga_CutFree( p, pCut );
        }
        else 
            pPrev = pCut; 
    }
//  printf( "Dominated = %3d. \n", Counter );
}


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

  Synopsis    [Merges two lists of cuts.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Fpga_Cut_t * Fpga_CutMergeLists( Fpga_Man_t * p, Fpga_CutTable_t * pTable, 
    Fpga_Cut_t * pList1, Fpga_Cut_t * pList2, int fComp1, int fComp2, int fPivot1, int fPivot2 )
{
    Fpga_Node_t * ppNodes[FPGA_MAX_LEAVES];
    Fpga_Cut_t * pListNew, ** ppListNew, * pLists[FPGA_MAX_LEAVES+1] = { NULL };
    Fpga_Cut_t * pCut, * pPrev, * pTemp1, * pTemp2;
    int nNodes, Counter, i;
    Fpga_Cut_t ** ppArray1, ** ppArray2, ** ppArray3;
    int nCuts1, nCuts2, nCuts3, k, fComp3;

    ppArray1 = pTable->pCuts1;
    ppArray2 = pTable->pCuts2;
    nCuts1 = Fpga_CutList2Array( ppArray1, pList1 );
    nCuts2 = Fpga_CutList2Array( ppArray2, pList2 );
    if ( fPivot1 )
        nCuts1 = 1;
    if ( fPivot2 )
        nCuts2 = 1;
    // swap the lists based on their length
    if ( nCuts1 > nCuts2 )
    {
         ppArray3 = ppArray1;
         ppArray1 = ppArray2;
         ppArray2 = ppArray3;

         nCuts3 = nCuts1;
         nCuts1 = nCuts2;
         nCuts2 = nCuts3;

         fComp3 = fComp1;
         fComp1 = fComp2;
         fComp2 = fComp3;
    }
    // pList1 is shorter or equal length compared to pList2
 
    // prepare the manager for the cut computation
    Fpga_CutTableRestart( pTable );
    // go through the cut pairs
    Counter = 0;
//    for ( pTemp1 = pList1; pTemp1; pTemp1 = fPivot1? NULL: pTemp1->pNext )
//        for ( pTemp2 = pList2; pTemp2; pTemp2 = fPivot2? NULL: pTemp2->pNext )
    for ( i = 0; i < nCuts1; i++ )
    {
        for ( k = 0; k <= i; k++ )
        {
            pTemp1 = ppArray1[i];
            pTemp2 = ppArray2[k];

            if ( pTemp1->nLeaves == p->nVarsMax && pTemp2->nLeaves == p->nVarsMax )
            {
                if ( pTemp1->ppLeaves[0] != pTemp2->ppLeaves[0] )
                    continue;
                if ( pTemp1->ppLeaves[1] != pTemp2->ppLeaves[1] )
                    continue;
            }

            // check if k-feasible cut exists
            nNodes = Fpga_CutMergeTwo( pTemp1, pTemp2, ppNodes, p->nVarsMax );
            if ( nNodes == 0 )
                continue;
            // consider the cut for possible addition to the set of new cuts
            pCut = Fpga_CutTableConsider( p, pTable, ppNodes, nNodes );
            if ( pCut == NULL )
                continue;
            // add data to the cut
            pCut->pOne = Fpga_CutNotCond( pTemp1, fComp1 );
            pCut->pTwo = Fpga_CutNotCond( pTemp2, fComp2 );
            // create the signature
            pCut->uSign = pTemp1->uSign | pTemp2->uSign;
            // add it to the corresponding list
            pCut->pNext = pLists[(int)pCut->nLeaves];
            pLists[(int)pCut->nLeaves] = pCut;
            // count this cut and quit if limit is reached
            Counter++;
            if ( Counter == FPGA_CUTS_MAX_COMPUTE )
                goto QUITS;
        }
        for ( k = 0; k < i; k++ )
        {
            pTemp1 = ppArray1[k];
            pTemp2 = ppArray2[i];

            if ( pTemp1->nLeaves == p->nVarsMax && pTemp2->nLeaves == p->nVarsMax )
            {
                if ( pTemp1->ppLeaves[0] != pTemp2->ppLeaves[0] )
                    continue;
                if ( pTemp1->ppLeaves[1] != pTemp2->ppLeaves[1] )
                    continue;
            }


            // check if k-feasible cut exists
            nNodes = Fpga_CutMergeTwo( pTemp1, pTemp2, ppNodes, p->nVarsMax );
            if ( nNodes == 0 )
                continue;
            // consider the cut for possible addition to the set of new cuts
            pCut = Fpga_CutTableConsider( p, pTable, ppNodes, nNodes );
            if ( pCut == NULL )
                continue;
            // add data to the cut
            pCut->pOne = Fpga_CutNotCond( pTemp1, fComp1 );
            pCut->pTwo = Fpga_CutNotCond( pTemp2, fComp2 );
            // create the signature
            pCut->uSign = pTemp1->uSign | pTemp2->uSign;
            // add it to the corresponding list
            pCut->pNext = pLists[(int)pCut->nLeaves];
            pLists[(int)pCut->nLeaves] = pCut;
            // count this cut and quit if limit is reached
            Counter++;
            if ( Counter == FPGA_CUTS_MAX_COMPUTE )
                goto QUITS;
        }
    }
    // consider the rest of them
    for ( i = nCuts1; i < nCuts2; i++ )
        for ( k = 0; k < nCuts1; k++ )
        {
            pTemp1 = ppArray1[k];
            pTemp2 = ppArray2[i];

            if ( pTemp1->nLeaves == p->nVarsMax && pTemp2->nLeaves == p->nVarsMax )
            {
                if ( pTemp1->ppLeaves[0] != pTemp2->ppLeaves[0] )
                    continue;
                if ( pTemp1->ppLeaves[1] != pTemp2->ppLeaves[1] )
                    continue;
                if ( pTemp1->ppLeaves[2] != pTemp2->ppLeaves[2] )
                    continue;
            }


            // check if k-feasible cut exists
            nNodes = Fpga_CutMergeTwo( pTemp1, pTemp2, ppNodes, p->nVarsMax );
            if ( nNodes == 0 )
                continue;
            // consider the cut for possible addition to the set of new cuts
            pCut = Fpga_CutTableConsider( p, pTable, ppNodes, nNodes );
            if ( pCut == NULL )
                continue;
            // add data to the cut
            pCut->pOne = Fpga_CutNotCond( pTemp1, fComp1 );
            pCut->pTwo = Fpga_CutNotCond( pTemp2, fComp2 );
            // create the signature
            pCut->uSign = pTemp1->uSign | pTemp2->uSign;
            // add it to the corresponding list
            pCut->pNext = pLists[(int)pCut->nLeaves];
            pLists[(int)pCut->nLeaves] = pCut;
            // count this cut and quit if limit is reached
            Counter++;
            if ( Counter == FPGA_CUTS_MAX_COMPUTE )
                goto QUITS;
        }
QUITS :
    // combine all the lists into one
    pListNew  = NULL;
    ppListNew = &pListNew;
    for ( i = 1; i <= p->nVarsMax; i++ )
    {
        if ( pLists[i] == NULL )
            continue;
        // find the last entry
        for ( pPrev = pLists[i], pCut = pPrev->pNext; pCut; 
            pPrev = pCut, pCut = pCut->pNext );
        // connect these lists
        *ppListNew = pLists[i];
        ppListNew  = &pPrev->pNext;
    }
    *ppListNew = NULL;
    // sort the cuts by arrival times and use only the first FPGA_CUTS_MAX_USE
    pListNew = Fpga_CutSortCuts( p, pTable, pListNew );
    return pListNew;
}


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

  Synopsis    [Merges two lists of cuts.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Fpga_Cut_t * Fpga_CutMergeLists2( Fpga_Man_t * p, Fpga_CutTable_t * pTable, 
    Fpga_Cut_t * pList1, Fpga_Cut_t * pList2, int fComp1, int fComp2, int fPivot1, int fPivot2 )
{
    Fpga_Node_t * ppNodes[FPGA_MAX_LEAVES];
    Fpga_Cut_t * pListNew, ** ppListNew, * pLists[FPGA_MAX_LEAVES+1] = { NULL };
    Fpga_Cut_t * pCut, * pPrev, * pTemp1, * pTemp2;
    int nNodes, Counter, i;

    // prepare the manager for the cut computation
    Fpga_CutTableRestart( pTable );
    // go through the cut pairs
    Counter = 0;
    for ( pTemp1 = pList1; pTemp1; pTemp1 = fPivot1? NULL: pTemp1->pNext )
        for ( pTemp2 = pList2; pTemp2; pTemp2 = fPivot2? NULL: pTemp2->pNext )
        {
            // check if k-feasible cut exists
            nNodes = Fpga_CutMergeTwo( pTemp1, pTemp2, ppNodes, p->nVarsMax );
            if ( nNodes == 0 )
                continue;
            // consider the cut for possible addition to the set of new cuts
            pCut = Fpga_CutTableConsider( p, pTable, ppNodes, nNodes );
            if ( pCut == NULL )
                continue;
            // add data to the cut
            pCut->pOne = Fpga_CutNotCond( pTemp1, fComp1 );
            pCut->pTwo = Fpga_CutNotCond( pTemp2, fComp2 );
            // add it to the corresponding list
            pCut->pNext = pLists[(int)pCut->nLeaves];
            pLists[(int)pCut->nLeaves] = pCut;
            // count this cut and quit if limit is reached
            Counter++;
            if ( Counter == FPGA_CUTS_MAX_COMPUTE )
                goto QUITS;
        }
QUITS :
    // combine all the lists into one
    pListNew  = NULL;
    ppListNew = &pListNew;
    for ( i = 1; i <= p->nVarsMax; i++ )
    {
        if ( pLists[i] == NULL )
            continue;
        // find the last entry
        for ( pPrev = pLists[i], pCut = pPrev->pNext; pCut; 
            pPrev = pCut, pCut = pCut->pNext );
        // connect these lists
        *ppListNew = pLists[i];
        ppListNew  = &pPrev->pNext;
    }
    *ppListNew = NULL;
    // sort the cuts by arrival times and use only the first FPGA_CUTS_MAX_USE
    pListNew = Fpga_CutSortCuts( p, pTable, pListNew );
    return pListNew;
}

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

  Synopsis    [Merges two cuts.]

  Description [Returns the number of nodes in the resulting cut, or 0 if the
  cut is infeasible. Returns the resulting nodes in the array ppNodes[].]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Fpga_CutMergeTwo( Fpga_Cut_t * pCut1, Fpga_Cut_t * pCut2, Fpga_Node_t * ppNodes[], int nNodesMax )
{
    Fpga_Node_t * pNodeTemp;
    int nTotal, i, k, min, Counter;
    unsigned uSign;

    // use quick prefiltering
    uSign = pCut1->uSign | pCut2->uSign;
    Counter = FPGA_COUNT_ONES(uSign);
    if ( Counter > nNodesMax )
        return 0;
/*
    // check the special case when at least of the cuts is the largest
    if ( pCut1->nLeaves == nNodesMax )
    {
        if ( pCut2->nLeaves == nNodesMax )
        {
            // return 0 if the cuts are different
            for ( i = 0; i < nNodesMax; i++ )
                if ( pCut1->ppLeaves[i] != pCut2->ppLeaves[i] )
                    return 0;
            // return nNodesMax if they are the same
            for ( i = 0; i < nNodesMax; i++ )
                ppNodes[i] = pCut1->ppLeaves[i];
            return nNodesMax;
        }
        else if ( pCut2->nLeaves == nNodesMax - 1 ) 
        {
            // return 0 if the cuts are different
            fMismatch = 0;
            for ( i = 0; i < nNodesMax; i++ )
                if ( pCut1->ppLeaves[i] != pCut2->ppLeaves[i - fMismatch] )
                {
                    if ( fMismatch == 1 )
                        return 0;
                    fMismatch = 1;
                }
            // return nNodesMax if they are the same
            for ( i = 0; i < nNodesMax; i++ )
                ppNodes[i] = pCut1->ppLeaves[i];
            return nNodesMax;
        }
    }
    else if ( pCut1->nLeaves == nNodesMax - 1 && pCut2->nLeaves == nNodesMax )
    {
        // return 0 if the cuts are different
        fMismatch = 0;
        for ( i = 0; i < nNodesMax; i++ )
            if ( pCut1->ppLeaves[i - fMismatch] != pCut2->ppLeaves[i] )
            {
                if ( fMismatch == 1 )
                    return 0;
                fMismatch = 1;
            }
        // return nNodesMax if they are the same
        for ( i = 0; i < nNodesMax; i++ )
            ppNodes[i] = pCut2->ppLeaves[i];
        return nNodesMax;
    }
*/
    // count the number of unique entries in pCut2
    nTotal = pCut1->nLeaves;
    for ( i = 0; i < pCut2->nLeaves; i++ )
    {
        // try to find this entry among the leaves of pCut1
        for ( k = 0; k < pCut1->nLeaves; k++ )
            if ( pCut2->ppLeaves[i] == pCut1->ppLeaves[k] )
                break;
        if ( k < pCut1->nLeaves ) // found
            continue;
        // we found a new entry to add
        if ( nTotal == nNodesMax )
            return 0;
        ppNodes[nTotal++] = pCut2->ppLeaves[i];
    }
    // we know that the feasible cut exists

    // add the starting entries
    for ( k = 0; k < pCut1->nLeaves; k++ )
        ppNodes[k] = pCut1->ppLeaves[k];

    // selection-sort the entries
    for ( i = 0; i < nTotal - 1; i++ )
    {
        min = i;
        for ( k = i+1; k < nTotal; k++ )
//            if ( ppNodes[k] < ppNodes[min] ) // reported bug fix (non-determinism!)
            if ( ppNodes[k]->Num < ppNodes[min]->Num )
                min = k;
        pNodeTemp    = ppNodes[i];
        ppNodes[i]   = ppNodes[min];
        ppNodes[min] = pNodeTemp;
    }

    return nTotal;
}

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

  Synopsis    [Computes the union of the two lists of cuts.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Fpga_Cut_t * Fpga_CutUnionLists( Fpga_Cut_t * pList1, Fpga_Cut_t * pList2 )
{
    Fpga_Cut_t * pTemp, * pRoot;
    // find the last cut in the first list
    pRoot = pList1;
    Fpga_ListForEachCut( pList1, pTemp )
        pRoot = pTemp;
    // attach the non-trival part of the second cut to the end of the first
    assert( pRoot->pNext == NULL );
    pRoot->pNext = pList2->pNext;   
    pList2->pNext = NULL;
    return pList1;
}


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

  Synopsis    [Checks whether the given cut belongs to the list.]

  Description [This procedure takes most of the runtime in the cut 
  computation.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Fpga_CutBelongsToList( Fpga_Cut_t * pList, Fpga_Node_t * ppNodes[], int nNodes )
{
    Fpga_Cut_t * pTemp;
    int i;
    for ( pTemp = pList; pTemp; pTemp = pTemp->pNext )
    {
        for ( i = 0; i < nNodes; i++ )
            if ( pTemp->ppLeaves[i] != ppNodes[i] )
                break;
        if ( i == nNodes )
            return 1;
    }
    return 0;
}

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

  Synopsis    [Counts all the cuts.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Fpga_CutCountAll( Fpga_Man_t * pMan )
{
    Fpga_Node_t * pNode;
    Fpga_Cut_t * pCut;
    int i, nCuts;
    // go through all the nodes in the unique table of the manager
    nCuts = 0;
    for ( i = 0; i < pMan->nBins; i++ )
        for ( pNode = pMan->pBins[i]; pNode; pNode = pNode->pNext )
            for ( pCut = pNode->pCuts; pCut; pCut = pCut->pNext )
                if ( pCut->nLeaves > 1 ) // skip the elementary cuts
                {
//                    Fpga_CutVolume( pCut );
                    nCuts++;
                }
    return nCuts;
}


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

  Synopsis    [Clean the signatures.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fpga_CutsCleanSign( Fpga_Man_t * pMan )
{
    Fpga_Node_t * pNode;
    Fpga_Cut_t * pCut;
    int i;
    for ( i = 0; i < pMan->nBins; i++ )
        for ( pNode = pMan->pBins[i]; pNode; pNode = pNode->pNext )
            for ( pCut = pNode->pCuts; pCut; pCut = pCut->pNext )
                pCut->uSign = 0;
}

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

  Synopsis    [Clean the signatures.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fpga_CutsCleanRoot( Fpga_Man_t * pMan )
{
    Fpga_Node_t * pNode;
    Fpga_Cut_t * pCut;
    int i;
    for ( i = 0; i < pMan->nBins; i++ )
        for ( pNode = pMan->pBins[i]; pNode; pNode = pNode->pNext )
            for ( pCut = pNode->pCuts; pCut; pCut = pCut->pNext )
                pCut->pRoot = NULL;
}



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

  Synopsis    [Prints the cuts in the list.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fpga_CutListPrint( Fpga_Man_t * pMan, Fpga_Node_t * pRoot )
{
    Fpga_Cut_t * pTemp;
    int Counter;
    for ( Counter = 0, pTemp = pRoot->pCuts; pTemp; pTemp = pTemp->pNext, Counter++ )
    {
        printf( "%2d : ", Counter + 1 );
        Fpga_CutPrint_( pMan, pTemp, pRoot );
    }
}

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

  Synopsis    [Prints the cuts in the list.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fpga_CutListPrint2( Fpga_Man_t * pMan, Fpga_Node_t * pRoot )
{
    Fpga_Cut_t * pTemp;
    int Counter;
    for ( Counter = 0, pTemp = pRoot->pCuts; pTemp; pTemp = pTemp->pNext, Counter++ )
    {
        printf( "%2d : ", Counter + 1 );
        Fpga_CutPrint_( pMan, pTemp, pRoot );
    }
}

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

  Synopsis    [Prints the cut.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fpga_CutPrint_( Fpga_Man_t * pMan, Fpga_Cut_t * pCut, Fpga_Node_t * pRoot )
{
    int i;
    printf( "(%3d)  {", pRoot->Num );
    for ( i = 0; i < pMan->nVarsMax; i++ )
        if ( pCut->ppLeaves[i] )
            printf( " %3d", pCut->ppLeaves[i]->Num );
    printf( " }\n" );
}








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

  Synopsis    [Starts the hash table to canonicize cuts.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Fpga_CutTable_t * Fpga_CutTableStart( Fpga_Man_t * pMan )
{
    Fpga_CutTable_t * p;
    // allocate the table
    p = ABC_ALLOC( Fpga_CutTable_t, 1 );
    memset( p, 0, sizeof(Fpga_CutTable_t) );
    p->nBins = Abc_PrimeCudd( 10 * FPGA_CUTS_MAX_COMPUTE );
    p->pBins = ABC_ALLOC( Fpga_Cut_t *, p->nBins );
    memset( p->pBins, 0, sizeof(Fpga_Cut_t *) * p->nBins );
    p->pCuts = ABC_ALLOC( int, 2 * FPGA_CUTS_MAX_COMPUTE );
    p->pArray = ABC_ALLOC( Fpga_Cut_t *, 2 * FPGA_CUTS_MAX_COMPUTE );
    p->pCuts1 = ABC_ALLOC( Fpga_Cut_t *, 2 * FPGA_CUTS_MAX_COMPUTE );
    p->pCuts2 = ABC_ALLOC( Fpga_Cut_t *, 2 * FPGA_CUTS_MAX_COMPUTE );
    return p;
}

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

  Synopsis    [Stops the hash table.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Fpga_CutTableStop( Fpga_CutTable_t * p )
{
    ABC_FREE( p->pCuts1 );
    ABC_FREE( p->pCuts2 );
    ABC_FREE( p->pArray );
    ABC_FREE( p->pBins );
    ABC_FREE( p->pCuts );
    ABC_FREE( p );
}

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

  Synopsis    [Computes the hash value of the cut.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
unsigned Fpga_CutTableHash( Fpga_Node_t * ppNodes[], int nNodes )
{
    unsigned uRes;
    int i;
    uRes = 0;
    for ( i = 0; i < nNodes; i++ )
        uRes += s_HashPrimes[i] * ppNodes[i]->Num;
    return uRes;
}

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

  Synopsis    [Looks up the table for the available cut.]

  Description [Returns -1 if the same cut is found. Returns the index
  of the cell where the cut should be added, if it does not exist.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Fpga_CutTableLookup( Fpga_CutTable_t * p, Fpga_Node_t * ppNodes[], int nNodes )
{
    Fpga_Cut_t * pCut;
    unsigned Key;
    int b, i;

    Key = Fpga_CutTableHash(ppNodes, nNodes) % p->nBins; 
    for ( b = Key; p->pBins[b]; b = (b+1) % p->nBins )
    {
        pCut = p->pBins[b];
        if ( pCut->nLeaves != nNodes )
            continue;
        for ( i = 0; i < nNodes; i++ )
            if ( pCut->ppLeaves[i] != ppNodes[i] )
                break;
        if ( i == nNodes )