cutOracle.c

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

  FileName    [cutOracle.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [K-feasible cut computation package.]

  Synopsis    [Procedures to compute cuts for a node using the oracle.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

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

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

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

#include "cutInt.h"

ABC_NAMESPACE_IMPL_START


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

struct Cut_OracleStruct_t_
{
    // cut comptupatation parameters
    Cut_Params_t *     pParams;
    Vec_Int_t *        vFanCounts;
    int                fSimul;
    // storage for cuts
    Vec_Ptr_t *        vCutsNew;
    Vec_Ptr_t *        vCuts0;
    Vec_Ptr_t *        vCuts1;
    // oracle info 
    Vec_Int_t *        vNodeCuts;
    Vec_Int_t *        vNodeStarts;
    Vec_Int_t *        vCutPairs;
    // memory management
    Extra_MmFixed_t *  pMmCuts;
    int                EntrySize;
    int                nTruthWords;
    // stats
    int                timeTotal;
    int                nCuts;
    int                nCutsTriv;
};

static Cut_Cut_t * Cut_CutStart( Cut_Oracle_t * p );
static Cut_Cut_t * Cut_CutTriv( Cut_Oracle_t * p, int Node );
static Cut_Cut_t * Cut_CutMerge( Cut_Oracle_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 );

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

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

  Synopsis    [Starts the cut oracle.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Cut_Oracle_t * Cut_OracleStart( Cut_Man_t * pMan )
{
    Cut_Oracle_t * p;

    assert( pMan->pParams->nVarsMax >= 3 && pMan->pParams->nVarsMax <= CUT_SIZE_MAX );
    assert( pMan->pParams->fRecord );

    p = ABC_ALLOC( Cut_Oracle_t, 1 );
    memset( p, 0, sizeof(Cut_Oracle_t) );

    // set and correct parameters
    p->pParams     = pMan->pParams;

    // transfer the recording info
    p->vNodeCuts   = pMan->vNodeCuts;    pMan->vNodeCuts   = NULL;
    p->vNodeStarts = pMan->vNodeStarts;  pMan->vNodeStarts = NULL;
    p->vCutPairs   = pMan->vCutPairs;    pMan->vCutPairs   = NULL;

    // prepare storage for cuts
    p->vCutsNew = Vec_PtrAlloc( p->pParams->nIdsMax );
    Vec_PtrFill( p->vCutsNew, p->pParams->nIdsMax, NULL );
    p->vCuts0 = Vec_PtrAlloc( 100 );
    p->vCuts1 = Vec_PtrAlloc( 100 );

    // entry size
    p->EntrySize = sizeof(Cut_Cut_t) + p->pParams->nVarsMax * sizeof(int);
    if ( p->pParams->fTruth )
    {
        if ( p->pParams->nVarsMax > 8 )
        {
            p->pParams->fTruth = 0;
            printf( "Skipping computation of truth table for more than 8 inputs.\n" );
        }
        else
        {
            p->nTruthWords = Cut_TruthWords( p->pParams->nVarsMax );
            p->EntrySize += p->nTruthWords * sizeof(unsigned);
        }
    }
    // memory for cuts
    p->pMmCuts = Extra_MmFixedStart( p->EntrySize );
    return p;
}
/**Function*************************************************************

  Synopsis    [Stop the cut oracle.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Cut_OracleStop( Cut_Oracle_t * p )
{
//    if ( p->pParams->fVerbose )
    {
        printf( "Cut computation statistics with oracle:\n" );
        printf( "Current cuts      = %8d. (Trivial = %d.)\n", p->nCuts-p->nCutsTriv, p->nCutsTriv );
        ABC_PRT( "Total time ", p->timeTotal );
    }

    if ( p->vCuts0 )      Vec_PtrFree( p->vCuts0 );
    if ( p->vCuts1 )      Vec_PtrFree( p->vCuts1 );
    if ( p->vCutsNew )    Vec_PtrFree( p->vCutsNew );
    if ( p->vFanCounts )  Vec_IntFree( p->vFanCounts );

    if ( p->vNodeCuts )   Vec_IntFree( p->vNodeCuts );
    if ( p->vNodeStarts ) Vec_IntFree( p->vNodeStarts );
    if ( p->vCutPairs )   Vec_IntFree( p->vCutPairs );

    Extra_MmFixedStop( p->pMmCuts );
    ABC_FREE( p ); 
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Cut_OracleSetFanoutCounts( Cut_Oracle_t * p, Vec_Int_t * vFanCounts )
{
    p->vFanCounts = vFanCounts;
}

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

  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Cut_OracleReadDrop( Cut_Oracle_t * p )
{
    return p->pParams->fDrop;
}

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

  Synopsis    [Sets the trivial cut for the node.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Cut_OracleNodeSetTriv( Cut_Oracle_t * p, int Node )
{
    assert( Vec_PtrEntry( p->vCutsNew, Node ) == NULL );
    Vec_PtrWriteEntry( p->vCutsNew, Node, Cut_CutTriv(p, Node) );
}



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

  Synopsis    [Allocates the cut.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Cut_Cut_t * Cut_CutStart( Cut_Oracle_t * p )
{
    Cut_Cut_t * pCut;
    // cut allocation
    pCut = (Cut_Cut_t *)Extra_MmFixedEntryFetch( p->pMmCuts );
    memset( pCut, 0, sizeof(Cut_Cut_t) );
    pCut->nVarsMax   = p->pParams->nVarsMax;
    pCut->fSimul     = p->fSimul;
    p->nCuts++;
    return pCut;
}

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

  Synopsis    [Creates the trivial cut.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Cut_Cut_t * Cut_CutTriv( Cut_Oracle_t * p, int Node )
{
    Cut_Cut_t * pCut;
    pCut = Cut_CutStart( p );
    pCut->nLeaves    = 1;
    pCut->pLeaves[0] = Node;
    if ( p->pParams->fTruth )
    {
        unsigned * pTruth = Cut_CutReadTruth(pCut);
        int i;
        for ( i = 0; i < p->nTruthWords; i++ )
            pTruth[i] = 0xAAAAAAAA;
    }
    p->nCutsTriv++;
    return pCut;
} 

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

  Synopsis    [Merges two cuts.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Cut_Cut_t * Cut_CutMerge( Cut_Oracle_t * p, Cut_Cut_t * pCut0, Cut_Cut_t * pCut1 )
{
    Cut_Cut_t * pCut;
    int Limit, i, k, c;
    // create the leaves of the new cut
    pCut = Cut_CutStart( p );
    Limit = p->pParams->nVarsMax;
    for ( i = k = c = 0; c < Limit; c++ )
    {
        if ( k == (int)pCut1->nLeaves )
        {
            if ( i == (int)pCut0->nLeaves )
            {
                pCut->nLeaves = c;
                return pCut;
            }
            pCut->pLeaves[c] = pCut0->pLeaves[i++];
            continue;
        }
        if ( i == (int)pCut0->nLeaves )
        {
            if ( k == (int)pCut1->nLeaves )
            {
                pCut->nLeaves = c;
                return pCut;
            }
            pCut->pLeaves[c] = pCut1->pLeaves[k++];
            continue;
        }
        if ( pCut0->pLeaves[i] < pCut1->pLeaves[k] )
        {
            pCut->pLeaves[c] = pCut0->pLeaves[i++];
            continue;
        }
        if ( pCut0->pLeaves[i] > pCut1->pLeaves[k] )
        {
            pCut->pLeaves[c] = pCut1->pLeaves[k++];
            continue;
        }
        pCut->pLeaves[c] = pCut0->pLeaves[i++]; 
        k++;
    }
    assert( i == (int)pCut0->nLeaves && k == (int)pCut1->nLeaves );
    pCut->nLeaves = c;
    return pCut;
} 

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

  Synopsis    [Reconstruct the cuts of the node.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Cut_Cut_t * Cut_OracleComputeCuts( Cut_Oracle_t * p, int Node, int Node0, int Node1, int fCompl0, int fCompl1 )
{
    Cut_Cut_t * pList = NULL, ** ppTail = &pList;
    Cut_Cut_t * pCut, * pCut0, * pCut1, * pList0, * pList1;
    int iCutStart, nCuts, i, Entry;
    int clk = clock();

    // get the cuts of the children
    pList0 = (Cut_Cut_t *)Vec_PtrEntry( p->vCutsNew, Node0 );
    pList1 = (Cut_Cut_t *)Vec_PtrEntry( p->vCutsNew, Node1 );
    assert( pList0 && pList1 );

    // get the complemented attribute of the cut
    p->fSimul = (fCompl0 ^ pList0->fSimul) & (fCompl1 ^ pList1->fSimul);

    // collect the cuts
    Vec_PtrClear( p->vCuts0 );
    Cut_ListForEachCut( pList0, pCut )
        Vec_PtrPush( p->vCuts0, pCut );
    Vec_PtrClear( p->vCuts1 );
    Cut_ListForEachCut( pList1, pCut )
        Vec_PtrPush( p->vCuts1, pCut );

    // get the first and last cuts of this node
    nCuts = Vec_IntEntry(p->vNodeCuts, Node);
    iCutStart = Vec_IntEntry(p->vNodeStarts, Node);

    // create trivial cut
    assert( Vec_IntEntry(p->vCutPairs, iCutStart) == 0 );
    pCut = Cut_CutTriv( p, Node );
    *ppTail = pCut;
    ppTail = &pCut->pNext;
    // create other cuts
    for ( i = 1; i < nCuts; i++ )
    {
        Entry = Vec_IntEntry( p->vCutPairs, iCutStart + i );
        pCut0 = (Cut_Cut_t *)Vec_PtrEntry( p->vCuts0, Entry & 0xFFFF );
        pCut1 = (Cut_Cut_t *)Vec_PtrEntry( p->vCuts1, Entry >> 16 );
        pCut  = Cut_CutMerge( p, pCut0, pCut1 );
        *ppTail = pCut;
        ppTail = &pCut->pNext;
        // compute the truth table
        if ( p->pParams->fTruth )
            Cut_TruthComputeOld( pCut, pCut0, pCut1, fCompl0, fCompl1 );
    }
    *ppTail = NULL;

    // write the new cut
    assert( Vec_PtrEntry( p->vCutsNew, Node ) == NULL );
    Vec_PtrWriteEntry( p->vCutsNew, Node, pList );
p->timeTotal += clock() - clk;
    return pList;
}

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

  Synopsis    [Deallocates the cuts at the node.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Cut_OracleFreeCuts( Cut_Oracle_t * p, int Node )
{
    Cut_Cut_t * pList, * pCut, * pCut2;
    pList = (Cut_Cut_t *)Vec_PtrEntry( p->vCutsNew, Node );
    if ( pList == NULL )
        return;
    Cut_ListForEachCutSafe( pList, pCut, pCut2 )
        Extra_MmFixedEntryRecycle( p->pMmCuts, (char *)pCut );
    Vec_PtrWriteEntry( p->vCutsNew, Node, pList );
}

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

  Synopsis    [Consider dropping cuts if they are useless by now.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Cut_OracleTryDroppingCuts( Cut_Oracle_t * p, int Node )
{
    int nFanouts;
    assert( p->vFanCounts );
    nFanouts = Vec_IntEntry( p->vFanCounts, Node );
    assert( nFanouts > 0 );
    if ( --nFanouts == 0 )
        Cut_OracleFreeCuts( p, Node );
    Vec_IntWriteEntry( p->vFanCounts, Node, nFanouts );
}

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


ABC_NAMESPACE_IMPL_END