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

  FileName    [giaPack.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Scalable AIG package.]

  Synopsis    [LUT packing.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

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

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

#include "gia.h"

ABC_NAMESPACE_IMPL_START


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

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

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

  Synopsis    [Collects LUT nodes in the increasing order of distance from COs.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Int_t * Gia_ManLutCollect2( Gia_Man_t * p )
{
    Gia_Obj_t * pObj;
    Vec_Int_t * vOrder;
    int i, k, Id, iFan;
    vOrder = Vec_IntAlloc( Gia_ManLutNum(p) );
    Gia_ManIncrementTravId( p );
    Gia_ManForEachCoDriver( p, pObj, i )
    {
        if ( !Gia_ObjIsAnd(pObj) )
            continue;
        Id = Gia_ObjId( p, pObj );
        assert( Gia_ObjIsLut(p, Id) );
        if ( Gia_ObjIsTravIdCurrentId(p, Id) )
            continue;
        Gia_ObjSetTravIdCurrentId(p, Id);
        Vec_IntPush( vOrder, Id );
    }
    Vec_IntForEachEntry( vOrder, Id, i )
    {
        Gia_LutForEachFanin( p, Id, iFan, k )
        {
            if ( !Gia_ObjIsAnd(Gia_ManObj(p, iFan)) )
                continue;
            assert( Gia_ObjIsLut(p, iFan) );
            if ( Gia_ObjIsTravIdCurrentId(p, iFan) )
                continue;
            Gia_ObjSetTravIdCurrentId(p, iFan);
            Vec_IntPush( vOrder, iFan );
        }
    }
    assert( Vec_IntCap(vOrder) == 16 || Vec_IntSize(vOrder) == Vec_IntCap(vOrder) );
    Vec_IntReverseOrder( vOrder );
    return vOrder;
}
Vec_Int_t * Gia_ManLutCollect( Gia_Man_t * p )
{
    Vec_Int_t * vLuts, * vDist, * vOrder;
    int i, k, Id, iFan, * pPerm;
    // collect LUTs
    vLuts = Vec_IntAlloc( Gia_ManAndNum(p) );
    Gia_ManForEachLut( p, Id )
        Vec_IntPush( vLuts, Id );
    // propagate distance
    vDist = Vec_IntStart( Gia_ManObjNum(p) );
    Gia_ManForEachCoDriverId( p, Id, i )
        Vec_IntWriteEntry( vDist, Id, 1 );
    Vec_IntForEachEntryReverse( vLuts, Id, i )
    {
        int Dist = 1 + Vec_IntEntry(vDist, Id);
        Gia_LutForEachFanin( p, Id, iFan, k )
            Vec_IntUpdateEntry( vDist, iFan, Dist );
    }
    // sort LUTs by distance
    k = 0;
    Vec_IntForEachEntry( vLuts, Id, i )
        Vec_IntWriteEntry( vDist, k++, -Vec_IntEntry(vDist, Id) );
    Vec_IntShrink( vDist, k );
    pPerm = Abc_MergeSortCost( Vec_IntArray(vDist), Vec_IntSize(vDist) );
    // collect
    vOrder = Vec_IntAlloc( Vec_IntSize(vLuts) );
    for ( i = 0; i < Vec_IntSize(vLuts); i++ )
        Vec_IntPush( vOrder, Vec_IntEntry(vLuts, pPerm[i]) );
    Vec_IntFree( vDist );
    Vec_IntFree( vLuts );
    ABC_FREE( pPerm );
    return vOrder;
}

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

  Synopsis    [LUT packing algorithm.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Gia_ManLutPacking( Gia_Man_t * p, int nBlockSize, int DelayRoute, int DelayDir, int fVerbose )
{
    int Delays[32], Perm[32];
    Vec_Int_t * vPacking, * vStarts;
    Vec_Int_t * vOrder = Gia_ManLutCollect( p );
    Vec_Int_t * vDelay = Vec_IntStart( Gia_ManObjNum(p) );
    Vec_Int_t * vBlock = Vec_IntStart( Gia_ManObjNum(p) );
    Vec_Int_t * vBSize = Vec_IntAlloc( 2 * Vec_IntSize(vOrder) / nBlockSize );
    int i, k, Id, iFan, nSize, iBlock, Delay, DelayMax = 0;
    // create blocks
    Vec_IntForEachEntry( vOrder, Id, i )
    {
        nSize = Gia_ObjLutSize( p, Id );
        assert( nSize <= 32 );
        Gia_LutForEachFanin( p, Id, iFan, k )
        {
            Delays[k] = Vec_IntEntry(vDelay, iFan);
            Perm[k] = iFan;
        }
        Vec_IntSelectSortCost2Reverse( Perm, nSize, Delays );
        assert( nSize < 2 || Delays[0] >= Delays[nSize-1] );
        assert( Delays[0] >= 0 && Delays[nSize-1] >= 0 );
        // check if we can reduce delay by adding it to the same bin as the latest one
        iBlock = Vec_IntEntry( vBlock, Perm[0] );
        if ( Delays[0] > 0 && Delays[0] > Delays[1] && Vec_IntEntry(vBSize, iBlock) < nBlockSize )
        {
            Delay = Delays[0] + DelayDir;
            Vec_IntWriteEntry( vBlock, Id, iBlock );
            Vec_IntAddToEntry( vBSize, iBlock, 1 );
        }
        else // clean new block
        {
            Delay = Delays[0] + DelayRoute;
            Vec_IntWriteEntry( vBlock, Id, Vec_IntSize(vBSize) );
            Vec_IntPush( vBSize, 1 );
        }
        // calculate delay
        for ( k = 1; k < nSize; k++ )
            Delay = Abc_MaxInt( Delay, Delays[k] + DelayRoute );
        Vec_IntWriteEntry( vDelay, Id, Delay );
        DelayMax = Abc_MaxInt( DelayMax, Delay );
    }
    assert( Vec_IntSum(vBSize) == Vec_IntSize(vOrder) );
    // create packing info
    vPacking = Vec_IntAlloc( Vec_IntSize(vBSize) + Vec_IntSize(vOrder) + 1 );
    Vec_IntPush( vPacking, Vec_IntSize(vBSize) );
    // create starting places for each block
    vStarts = Vec_IntAlloc( Vec_IntSize(vBSize) );
    Vec_IntForEachEntry( vBSize, nSize, i )
    {
        Vec_IntPush( vPacking, nSize );
        Vec_IntPush( vStarts, Vec_IntSize(vPacking) );
        Vec_IntFillExtra( vPacking, Vec_IntSize(vPacking) + nSize, -1 );
    }
    assert( Vec_IntCap(vPacking) == 16 || Vec_IntSize(vPacking) == Vec_IntCap(vPacking) );
    // collect LUTs from the block
    Vec_IntForEachEntryReverse( vOrder, Id, i )
    {
        int Block = Vec_IntEntry( vBlock, Id );
        int Start = Vec_IntEntry( vStarts, Block );
        assert( Vec_IntEntry(vPacking, Start) == -1 );
        Vec_IntWriteEntry( vPacking, Start, Id );
        Vec_IntAddToEntry( vStarts, Block, 1 );
    }
    assert( Vec_IntCountEntry(vPacking, -1) == 0 );
    // cleanup
    Vec_IntFree( vOrder );
    Vec_IntFree( vDelay );
    Vec_IntFree( vBlock );
    Vec_IntFree( vBSize );
    Vec_IntFree( vStarts );
    Vec_IntFreeP( &p->vPacking );
    p->vPacking = vPacking;
    printf( "Global delay = %d.\n", DelayMax );
}

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


ABC_NAMESPACE_IMPL_END