src/opt/lpk/lpkInt.h File Reference

#include "abc.h"
#include "kit.h"
#include "if.h"
#include "lpk.h"
Include dependency graph for lpkInt.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  Lpk_Cut_t_
struct  Lpk_Man_t_
struct  Lpk_Fun_t_
struct  Lpk_Res_t_

Defines

#define LPK_SIZE_MAX   24
#define LPK_CUTS_MAX   512
#define Lpk_CutForEachLeaf(pNtk, pCut, pObj, i)   for ( i = 0; (i < (int)(pCut)->nLeaves) && (((pObj) = Abc_NtkObj(pNtk, (pCut)->pLeaves[i])), 1); i++ )
#define Lpk_CutForEachNode(pNtk, pCut, pObj, i)   for ( i = 0; (i < (int)(pCut)->nNodes) && (((pObj) = Abc_NtkObj(pNtk, (pCut)->pNodes[i])), 1); i++ )
#define Lpk_CutForEachNodeReverse(pNtk, pCut, pObj, i)   for ( i = (int)(pCut)->nNodes - 1; (i >= 0) && (((pObj) = Abc_NtkObj(pNtk, (pCut)->pNodes[i])), 1); i-- )
#define Lpk_SuppForEachVar(Supp, Var)

Typedefs

typedef struct Lpk_Man_t_ Lpk_Man_t
typedef struct Lpk_Cut_t_ Lpk_Cut_t
typedef struct Lpk_Fun_t_ Lpk_Fun_t
typedef struct Lpk_Res_t_ Lpk_Res_t

Functions

static int Lpk_LutNumVars (int nLutsLim, int nLutK)
static int Lpk_LutNumLuts (int nVarsMax, int nLutK)
static unsigned * Lpk_FunTruth (Lpk_Fun_t *p, int Num)
Abc_Obj_t * Lpk_Decompose (Lpk_Man_t *pMan, Abc_Ntk_t *pNtk, Vec_Ptr_t *vLeaves, unsigned *pTruth, unsigned *puSupps, int nLutK, int AreaLim, int DelayLim)
Lpk_Res_t * Lpk_DsdAnalize (Lpk_Man_t *pMan, Lpk_Fun_t *p, int nShared)
Lpk_Fun_t * Lpk_DsdSplit (Lpk_Man_t *pMan, Lpk_Fun_t *p, char *pCofVars, int nCofVars, unsigned uBoundSet)
Lpk_Res_t * Lpk_MuxAnalize (Lpk_Man_t *pMan, Lpk_Fun_t *p)
Lpk_Fun_t * Lpk_MuxSplit (Lpk_Man_t *pMan, Lpk_Fun_t *p, int Var, int Pol)
Lpk_Fun_t * Lpk_FunAlloc (int nVars)
void Lpk_FunFree (Lpk_Fun_t *p)
Lpk_Fun_t * Lpk_FunCreate (Abc_Ntk_t *pNtk, Vec_Ptr_t *vLeaves, unsigned *pTruth, int nLutK, int AreaLim, int DelayLim)
Lpk_Fun_t * Lpk_FunDup (Lpk_Fun_t *p, unsigned *pTruth)
int Lpk_FunSuppMinimize (Lpk_Fun_t *p)
void Lpk_FunComputeCofSupps (Lpk_Fun_t *p)
int Lpk_SuppDelay (unsigned uSupp, char *pDelays)
int Lpk_SuppToVars (unsigned uBoundSet, char *pVars)
unsigned * Lpk_CutTruth (Lpk_Man_t *p, Lpk_Cut_t *pCut, int fInv)
int Lpk_NodeCuts (Lpk_Man_t *p)
Lpk_Man_t * Lpk_ManStart (Lpk_Par_t *pPars)
void Lpk_ManStop (Lpk_Man_t *p)
If_Obj_t * Lpk_MapPrime (Lpk_Man_t *p, unsigned *pTruth, int nVars, If_Obj_t **ppLeaves)
If_Obj_t * Lpk_MapTree_rec (Lpk_Man_t *p, Kit_DsdNtk_t *pNtk, If_Obj_t **ppLeaves, int iLit, If_Obj_t *pResult)
If_Obj_t * Lpk_MapTreeMulti (Lpk_Man_t *p, unsigned *pTruth, int nLeaves, If_Obj_t **ppLeaves)
If_Obj_t * Lpk_MapTreeMux_rec (Lpk_Man_t *p, unsigned *pTruth, int nVars, If_Obj_t **ppLeaves)
If_Obj_t * Lpk_MapSuppRedDec_rec (Lpk_Man_t *p, unsigned *pTruth, int nVars, If_Obj_t **ppLeaves)
unsigned Lpk_MapSuppRedDecSelect (Lpk_Man_t *p, unsigned *pTruth, int nVars, int *piVar, int *piVarReused)

Define Documentation

#define Lpk_CutForEachLeaf ( pNtk,
pCut,
pObj,
i   )     for ( i = 0; (i < (int)(pCut)->nLeaves) && (((pObj) = Abc_NtkObj(pNtk, (pCut)->pLeaves[i])), 1); i++ )

MACRO DEFINITIONS /// ITERATORS ///

Definition at line 187 of file lpkInt.h.

#define Lpk_CutForEachNode ( pNtk,
pCut,
pObj,
i   )     for ( i = 0; (i < (int)(pCut)->nNodes) && (((pObj) = Abc_NtkObj(pNtk, (pCut)->pNodes[i])), 1); i++ )

Definition at line 189 of file lpkInt.h.

#define Lpk_CutForEachNodeReverse ( pNtk,
pCut,
pObj,
i   )     for ( i = (int)(pCut)->nNodes - 1; (i >= 0) && (((pObj) = Abc_NtkObj(pNtk, (pCut)->pNodes[i])), 1); i-- )

Definition at line 191 of file lpkInt.h.

#define LPK_CUTS_MAX   512

Definition at line 46 of file lpkInt.h.

#define LPK_SIZE_MAX   24

CFile****************************************************************

FileName [lpkInt.h]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Fast Boolean matching for LUT structures.]

Synopsis [Internal declarations.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - April 28, 2007.]

Revision [

Id
lpkInt.h,v 1.00 2007/04/28 00:00:00 alanmi Exp

] INCLUDES /// PARAMETERS /// BASIC TYPES ///

Definition at line 45 of file lpkInt.h.

#define Lpk_SuppForEachVar ( Supp,
Var   ) 
Value:
for ( Var = 0; Var < 16; Var++ )\
        if ( !(Supp & (1<<Var)) ) {} else

Definition at line 193 of file lpkInt.h.

Typedef Documentation

typedef struct Lpk_Cut_t_ Lpk_Cut_t

Definition at line 49 of file lpkInt.h.

typedef struct Lpk_Fun_t_ Lpk_Fun_t

Definition at line 141 of file lpkInt.h.

typedef struct Lpk_Man_t_ Lpk_Man_t

Definition at line 48 of file lpkInt.h.

typedef struct Lpk_Res_t_ Lpk_Res_t

Definition at line 160 of file lpkInt.h.

Function Documentation

unsigned* Lpk_CutTruth ( Lpk_Man_t *  p,
Lpk_Cut_t *  pCut,
int  fInv 
)

Function*************************************************************

Synopsis [Computes the truth able of one cut.]

Description []

SideEffects []

SeeAlso []

Definition at line 172 of file lpkCut.c.

00173 {
00174     Hop_Man_t * pManHop = p->pNtk->pManFunc;
00175     Hop_Obj_t * pObjHop;
00176     Abc_Obj_t * pObj, * pFanin;
00177     unsigned * pTruth;
00178     int i, k, iCount = 0;
00179 //    Lpk_NodePrintCut( p, pCut );
00180     assert( pCut->nNodes > 0 );
00181 
00182     // initialize the leaves
00183     Lpk_CutForEachLeaf( p->pNtk, pCut, pObj, i )
00184         pObj->pCopy = Vec_PtrEntry( p->vTtElems, fInv? pCut->nLeaves-1-i : i );
00185 
00186     // construct truth table in the topological order
00187     Lpk_CutForEachNodeReverse( p->pNtk, pCut, pObj, i )
00188     {
00189         // get the local AIG
00190         pObjHop = Hop_Regular(pObj->pData);
00191         // clean the data field of the nodes in the AIG subgraph
00192         Hop_ObjCleanData_rec( pObjHop );
00193         // set the initial truth tables at the fanins
00194         Abc_ObjForEachFanin( pObj, pFanin, k )
00195         {
00196             assert( ((unsigned)pFanin->pCopy) & 0xffff0000 );
00197             Hop_ManPi( pManHop, k )->pData = pFanin->pCopy;
00198         }
00199         // compute the truth table of internal nodes
00200         pTruth = Lpk_CutTruth_rec( pManHop, pObjHop, pCut->nLeaves, p->vTtNodes, &iCount );
00201         if ( Hop_IsComplement(pObj->pData) )
00202             Kit_TruthNot( pTruth, pTruth, pCut->nLeaves );
00203         // set the truth table at the node
00204         pObj->pCopy = (Abc_Obj_t *)pTruth;
00205     }
00206 
00207     // make sure direct truth table is stored elsewhere (assuming the first call for direct truth!!!)
00208     if ( fInv == 0 )
00209     {
00210         pTruth = Vec_PtrEntry( p->vTtNodes, iCount++ );
00211         Kit_TruthCopy( pTruth, (unsigned *)pObj->pCopy, pCut->nLeaves );
00212     }
00213     assert( iCount <= Vec_PtrSize(p->vTtNodes) );
00214     return pTruth;
00215 }

Abc_Obj_t* Lpk_Decompose ( Lpk_Man_t *  p,
Abc_Ntk_t *  pNtk,
Vec_Ptr_t *  vLeaves,
unsigned *  pTruth,
unsigned *  puSupps,
int  nLutK,
int  AreaLim,
int  DelayLim 
)

FUNCTION DECLARATIONS ///

Function*************************************************************

Synopsis [Decomposes the function using recursive MUX decomposition.]

Description []

SideEffects []

SeeAlso []

Definition at line 256 of file lpkAbcDec.c.

00257 {
00258     Lpk_Fun_t * pFun;
00259     Abc_Obj_t * pObjNew = NULL;
00260     int nLeaves = Vec_PtrSize( vLeaves );
00261     pFun = Lpk_FunCreate( pNtk, vLeaves, pTruth, nLutK, AreaLim, DelayLim );
00262     if ( puSupps[0] || puSupps[1] )
00263     {
00264 /*
00265         int i;
00266         Lpk_FunComputeCofSupps( pFun );
00267         for ( i = 0; i < nLeaves; i++ )
00268         {
00269             assert( pFun->puSupps[2*i+0] == puSupps[2*i+0] );
00270             assert( pFun->puSupps[2*i+1] == puSupps[2*i+1] );
00271         }
00272 */
00273         memcpy( pFun->puSupps, puSupps, sizeof(unsigned) * 2 * nLeaves );
00274         pFun->fSupports = 1;
00275     }
00276     Lpk_FunSuppMinimize( pFun );
00277     if ( pFun->nVars <= pFun->nLutK )
00278         pObjNew = Lpk_ImplementFun( p, pNtk, vLeaves, pFun );
00279     else if ( Lpk_Decompose_rec(p, pFun) )
00280         pObjNew = Lpk_Implement( p, pNtk, vLeaves, nLeaves );
00281     Lpk_DecomposeClean( vLeaves, nLeaves );
00282     return pObjNew;
00283 }

Lpk_Res_t* Lpk_DsdAnalize ( Lpk_Man_t *  pMan,
Lpk_Fun_t *  p,
int  nShared 
)

Function*************************************************************

Synopsis [Performs DSD-based decomposition of the function.]

Description []

SideEffects []

SeeAlso []

Definition at line 440 of file lpkAbcDsd.c.

00441 { 
00442     static Lpk_Res_t Res0, * pRes0 = &Res0;
00443     static Lpk_Res_t Res1, * pRes1 = &Res1;
00444     static Lpk_Res_t Res2, * pRes2 = &Res2;
00445     static Lpk_Res_t Res3, * pRes3 = &Res3;
00446     int fUseBackLooking = 1;
00447     Lpk_Res_t * pRes = NULL;
00448     Vec_Int_t * vBSets;
00449     Kit_DsdNtk_t * pNtks[8] = {NULL};
00450     char pCofVars[5];
00451     int i;
00452 
00453     assert( p->nLutK >= 3 );
00454     assert( nShared >= 0 && nShared <= 3 );
00455     assert( p->uSupp == Kit_BitMask(p->nVars) );
00456 
00457     // try decomposition without cofactoring
00458     pNtks[0] = Kit_DsdDecomposeExpand( Lpk_FunTruth( p, 0 ), p->nVars );
00459     if ( pMan->pPars->fVerbose )
00460         pMan->nBlocks[ Kit_DsdNonDsdSizeMax(pNtks[0]) ]++;
00461     vBSets = Lpk_ComputeBoundSets( pNtks[0], p->nLutK );
00462     Lpk_FunCompareBoundSets( p, vBSets, 0, 0xFFFF, Lpk_DsdLateArriving(p), pRes0 );
00463     Vec_IntFree( vBSets );
00464 
00465     // check the result
00466     if ( pRes0->nBSVars == (int)p->nLutK )
00467         { pRes = pRes0; goto finish; }
00468     if ( pRes0->nBSVars == (int)p->nLutK - 1 )
00469         { pRes = pRes0; goto finish; }
00470     if ( nShared == 0 )
00471         goto finish;
00472 
00473     // prepare storage
00474     Kit_TruthCopy( pMan->ppTruths[0][0], Lpk_FunTruth( p, 0 ), p->nVars );
00475 
00476     // cofactor 1 time
00477     if ( !Lpk_DsdAnalizeOne( p, pMan->ppTruths, pNtks, pCofVars, 1, pRes1 ) )
00478         goto finish;
00479     assert( pRes1->nBSVars <= (int)p->nLutK - 1 );
00480     if ( pRes1->nBSVars == (int)p->nLutK - 1 )
00481         { pRes = pRes1; goto finish; }
00482     if ( pRes0->nBSVars == (int)p->nLutK - 2 )
00483         { pRes = pRes0; goto finish; }
00484     if ( pRes1->nBSVars == (int)p->nLutK - 2 )
00485         { pRes = pRes1; goto finish; }
00486     if ( nShared == 1 )
00487         goto finish;
00488 
00489     // cofactor 2 times
00490     if ( p->nLutK >= 4 ) 
00491     {
00492         if ( !Lpk_DsdAnalizeOne( p, pMan->ppTruths, pNtks, pCofVars, 2, pRes2 ) )
00493             goto finish;
00494         assert( pRes2->nBSVars <= (int)p->nLutK - 2 );
00495         if ( pRes2->nBSVars == (int)p->nLutK - 2 )
00496             { pRes = pRes2; goto finish; }
00497         if ( fUseBackLooking )
00498         {
00499             if ( pRes0->nBSVars == (int)p->nLutK - 3 )
00500                 { pRes = pRes0; goto finish; }
00501             if ( pRes1->nBSVars == (int)p->nLutK - 3 )
00502                 { pRes = pRes1; goto finish; }
00503         }
00504         if ( pRes2->nBSVars == (int)p->nLutK - 3 )
00505             { pRes = pRes2; goto finish; }
00506         if ( nShared == 2 )
00507             goto finish;
00508         assert( nShared == 3 );
00509     }
00510 
00511     // cofactor 3 times
00512     if ( p->nLutK >= 5 ) 
00513     {
00514         if ( !Lpk_DsdAnalizeOne( p, pMan->ppTruths, pNtks, pCofVars, 3, pRes3 ) )
00515             goto finish;
00516         assert( pRes3->nBSVars <= (int)p->nLutK - 3 );
00517         if ( pRes3->nBSVars == (int)p->nLutK - 3 )
00518             { pRes = pRes3; goto finish; }
00519         if ( fUseBackLooking )
00520         {
00521             if ( pRes0->nBSVars == (int)p->nLutK - 4 )
00522                 { pRes = pRes0; goto finish; }
00523             if ( pRes1->nBSVars == (int)p->nLutK - 4 )
00524                 { pRes = pRes1; goto finish; }
00525             if ( pRes2->nBSVars == (int)p->nLutK - 4 )
00526                 { pRes = pRes2; goto finish; }
00527         }
00528         if ( pRes3->nBSVars == (int)p->nLutK - 4 )
00529             { pRes = pRes3; goto finish; }
00530     }
00531 
00532 finish:
00533     // free the networks
00534     for ( i = 0; i < (1<<nShared); i++ )
00535         if ( pNtks[i] )
00536             Kit_DsdNtkFree( pNtks[i] );
00537     // choose the best under these conditions
00538     return pRes;
00539 }

Lpk_Fun_t* Lpk_DsdSplit ( Lpk_Man_t *  pMan,
Lpk_Fun_t *  p,
char *  pCofVars,
int  nCofVars,
unsigned  uBoundSet 
)

Function*************************************************************

Synopsis [Splits the function into two subfunctions using DSD.]

Description []

SideEffects []

SeeAlso []

Definition at line 552 of file lpkAbcDsd.c.

00553 {
00554     Lpk_Fun_t * pNew;
00555     Kit_DsdNtk_t * pNtkDec;
00556     int i, k, iVacVar, nCofs;
00557     // prepare storage
00558     Kit_TruthCopy( pMan->ppTruths[0][0], Lpk_FunTruth(p, 0), p->nVars );
00559     // get the vacuous variable
00560     iVacVar = Kit_WordFindFirstBit( uBoundSet );
00561     // compute the cofactors
00562     for ( i = 0; i < nCofVars; i++ )
00563         for ( k = 0; k < (1<<i); k++ )
00564         {
00565             Kit_TruthCofactor0New( pMan->ppTruths[i+1][2*k+0], pMan->ppTruths[i][k], p->nVars, pCofVars[i] );
00566             Kit_TruthCofactor1New( pMan->ppTruths[i+1][2*k+1], pMan->ppTruths[i][k], p->nVars, pCofVars[i] );
00567         }
00568     // decompose each cofactor w.r.t. the bound set
00569     nCofs = (1<<nCofVars);
00570     for ( k = 0; k < nCofs; k++ )
00571     {
00572         pNtkDec = Kit_DsdDecomposeExpand( pMan->ppTruths[nCofVars][k], p->nVars );
00573         Kit_DsdTruthPartialTwo( pMan->pDsdMan, pNtkDec, uBoundSet, iVacVar, pMan->ppTruths[nCofVars+1][k], pMan->ppTruths[nCofVars+1][nCofs+k] );
00574         Kit_DsdNtkFree( pNtkDec );
00575     }
00576     // compute the composition/decomposition functions (they will be in pMan->ppTruths[1][0]/pMan->ppTruths[1][1])
00577     for ( i = nCofVars; i >= 1; i-- )
00578         for ( k = 0; k < (1<<i); k++ )
00579             Kit_TruthMuxVar( pMan->ppTruths[i][k], pMan->ppTruths[i+1][2*k+0], pMan->ppTruths[i+1][2*k+1], p->nVars, pCofVars[i-1] );
00580 
00581     // derive the new component (decomposition function)
00582     pNew = Lpk_FunDup( p, pMan->ppTruths[1][1] );
00583     // update the old component (composition function)
00584     Kit_TruthCopy( Lpk_FunTruth(p, 0), pMan->ppTruths[1][0], p->nVars );
00585     p->uSupp = Kit_TruthSupport( Lpk_FunTruth(p, 0), p->nVars );
00586     p->pFanins[iVacVar] = pNew->Id;
00587     p->pDelays[iVacVar] = Lpk_SuppDelay( pNew->uSupp, pNew->pDelays );
00588     // support minimize both
00589     p->fSupports = 0;
00590     Lpk_FunSuppMinimize( p );
00591     Lpk_FunSuppMinimize( pNew );
00592     // update delay and area requirements
00593     pNew->nDelayLim = p->pDelays[iVacVar];
00594     pNew->nAreaLim = 1;
00595     p->nAreaLim = p->nAreaLim - 1;
00596     return pNew;
00597 }

Lpk_Fun_t* Lpk_FunAlloc ( int  nVars  ) 

CFile****************************************************************

FileName [lpkAbcUtil.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Fast Boolean matching for LUT structures.]

Synopsis [Procedures working on decomposed functions.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - April 28, 2007.]

Revision [

Id
lpkAbcUtil.c,v 1.00 2007/04/28 00:00:00 alanmi Exp

] DECLARATIONS /// FUNCTION DEFINITIONS ///Function*************************************************************

Synopsis [Allocates the function.]

Description []

SideEffects []

SeeAlso []

Definition at line 42 of file lpkAbcUtil.c.

00043 {
00044     Lpk_Fun_t * p;
00045     p = (Lpk_Fun_t *)malloc( sizeof(Lpk_Fun_t) + sizeof(unsigned) * Kit_TruthWordNum(nVars) * 3 );
00046     memset( p, 0, sizeof(Lpk_Fun_t) );
00047     return p;
00048 }

void Lpk_FunComputeCofSupps ( Lpk_Fun_t *  p  ) 

Function*************************************************************

Synopsis [Computes cofactors w.r.t. each variable.]

Description []

SideEffects []

SeeAlso []

Definition at line 183 of file lpkAbcUtil.c.

00184 {
00185     unsigned * pTruth  = Lpk_FunTruth( p, 0 );
00186     unsigned * pTruth0 = Lpk_FunTruth( p, 1 );
00187     unsigned * pTruth1 = Lpk_FunTruth( p, 2 );
00188     int Var;
00189     assert( p->fSupports == 0 );
00190 //    Lpk_SuppForEachVar( p->uSupp, Var )
00191     for ( Var = 0; Var < (int)p->nVars; Var++ )
00192     {
00193         Kit_TruthCofactor0New( pTruth0, pTruth, p->nVars, Var );
00194         Kit_TruthCofactor1New( pTruth1, pTruth, p->nVars, Var );
00195         p->puSupps[2*Var+0] = Kit_TruthSupport( pTruth0, p->nVars );
00196         p->puSupps[2*Var+1] = Kit_TruthSupport( pTruth1, p->nVars );
00197     }
00198     p->fSupports = 1;
00199 }

Lpk_Fun_t* Lpk_FunCreate ( Abc_Ntk_t *  pNtk,
Vec_Ptr_t *  vLeaves,
unsigned *  pTruth,
int  nLutK,
int  AreaLim,
int  DelayLim 
)

Function*************************************************************

Synopsis [Creates the starting function.]

Description []

SideEffects []

SeeAlso []

Definition at line 77 of file lpkAbcUtil.c.

00078 {
00079     Lpk_Fun_t * p;
00080     Abc_Obj_t * pNode;
00081     int i;
00082     p = Lpk_FunAlloc( Vec_PtrSize(vLeaves) );
00083     p->Id = Vec_PtrSize(vLeaves);
00084     p->vNodes = vLeaves;
00085     p->nVars = Vec_PtrSize(vLeaves);
00086     p->nLutK = nLutK;
00087     p->nAreaLim = AreaLim;
00088     p->nDelayLim = DelayLim;
00089     p->uSupp = Kit_TruthSupport( pTruth, p->nVars );
00090     Kit_TruthCopy( Lpk_FunTruth(p,0), pTruth, p->nVars );
00091     Vec_PtrForEachEntry( vLeaves, pNode, i )
00092     {
00093         p->pFanins[i] = i;
00094         p->pDelays[i] = pNode->Level;
00095     }
00096     Vec_PtrPush( p->vNodes, p );
00097     return p;
00098 }

Lpk_Fun_t* Lpk_FunDup ( Lpk_Fun_t *  p,
unsigned *  pTruth 
)

Function*************************************************************

Synopsis [Creates the new function with the given truth table.]

Description []

SideEffects []

SeeAlso []

Definition at line 111 of file lpkAbcUtil.c.

00112 {
00113     Lpk_Fun_t * pNew;
00114     pNew = Lpk_FunAlloc( p->nVars );
00115     pNew->Id = Vec_PtrSize(p->vNodes);
00116     pNew->vNodes = p->vNodes;
00117     pNew->nVars = p->nVars;
00118     pNew->nLutK = p->nLutK;
00119     pNew->nAreaLim = p->nAreaLim;
00120     pNew->nDelayLim = p->nDelayLim;
00121     pNew->uSupp = Kit_TruthSupport( pTruth, p->nVars );
00122     Kit_TruthCopy( Lpk_FunTruth(pNew,0), pTruth, p->nVars );
00123     memcpy( pNew->pFanins, p->pFanins, 16 );
00124     memcpy( pNew->pDelays, p->pDelays, 16 );
00125     Vec_PtrPush( p->vNodes, pNew );
00126     return pNew;
00127 }

void Lpk_FunFree ( Lpk_Fun_t *  p  ) 

Function*************************************************************

Synopsis [Deletes the function]

Description []

SideEffects []

SeeAlso []

Definition at line 61 of file lpkAbcUtil.c.

00062 {
00063     free( p );
00064 }

int Lpk_FunSuppMinimize ( Lpk_Fun_t *  p  ) 

Function*************************************************************

Synopsis [Minimizes support of the function.]

Description []

SideEffects []

SeeAlso []

Definition at line 140 of file lpkAbcUtil.c.

00141 {
00142     int i, k, nVarsNew;
00143     // compress the truth table
00144     if ( p->uSupp == Kit_BitMask(p->nVars) )
00145         return 0;
00146     // invalidate support info
00147     p->fSupports = 0;
00148 //Extra_PrintBinary( stdout, &p->uSupp, p->nVars ); printf( "\n" );
00149     // minimize support
00150     nVarsNew = Kit_WordCountOnes(p->uSupp);
00151     Kit_TruthShrink( Lpk_FunTruth(p, 1), Lpk_FunTruth(p, 0), nVarsNew, p->nVars, p->uSupp, 1 );
00152     k = 0;
00153     Lpk_SuppForEachVar( p->uSupp, i )
00154     {
00155         p->pFanins[k] = p->pFanins[i];
00156         p->pDelays[k] = p->pDelays[i];
00157 /*
00158         if ( p->fSupports )
00159         {
00160             p->puSupps[2*k+0] = p->puSupps[2*i+0];
00161             p->puSupps[2*k+1] = p->puSupps[2*i+1];
00162         }
00163 */
00164         k++;
00165     }
00166     assert( k == nVarsNew );
00167     p->nVars = k;
00168     p->uSupp = Kit_BitMask(p->nVars);
00169     return 1;
00170 }

static unsigned* Lpk_FunTruth ( Lpk_Fun_t *  p,
int  Num 
) [inline, static]

Definition at line 177 of file lpkInt.h.

00177 { assert( Num < 3 ); return p->pTruth + Kit_TruthWordNum(p->nVars) * Num;        }

static int Lpk_LutNumLuts ( int  nVarsMax,
int  nLutK 
) [inline, static]

Definition at line 176 of file lpkInt.h.

00176 { return (nVarsMax - 1) / (nLutK - 1) + (int)((nVarsMax - 1) % (nLutK - 1) > 0); }

static int Lpk_LutNumVars ( int  nLutsLim,
int  nLutK 
) [inline, static]

Definition at line 175 of file lpkInt.h.

00175 { return  nLutsLim * (nLutK - 1) + 1;                                            }

Lpk_Man_t* Lpk_ManStart ( Lpk_Par_t *  pPars  ) 

CFile****************************************************************

FileName [lpkMan.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Fast Boolean matching for LUT structures.]

Synopsis []

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - April 28, 2007.]

Revision [

Id
lpkMan.c,v 1.00 2007/04/28 00:00:00 alanmi Exp

] DECLARATIONS /// FUNCTION DEFINITIONS ///Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 42 of file lpkMan.c.

00043 {
00044     Lpk_Man_t * p;
00045     int i, nWords;
00046     assert( pPars->nLutsMax <= 16 );
00047     assert( pPars->nVarsMax > 0 && pPars->nVarsMax <= 16 );
00048     p = ALLOC( Lpk_Man_t, 1 );
00049     memset( p, 0, sizeof(Lpk_Man_t) );
00050     p->pPars = pPars;
00051     p->nCutsMax = LPK_CUTS_MAX;
00052     p->vTtElems = Vec_PtrAllocTruthTables( pPars->nVarsMax );
00053     p->vTtNodes = Vec_PtrAllocSimInfo( 1024, Abc_TruthWordNum(pPars->nVarsMax) );
00054     p->vCover = Vec_IntAlloc( 1 << 12 );
00055     p->vLeaves = Vec_PtrAlloc( 32 );
00056     for ( i = 0; i < 8; i++ )
00057         p->vSets[i] = Vec_IntAlloc(100);
00058     p->pDsdMan = Kit_DsdManAlloc( pPars->nVarsMax, 64 );
00059     p->vMemory = Vec_IntAlloc( 1024 * 32 );
00060     p->vBddDir = Vec_IntAlloc( 256 );
00061     p->vBddInv = Vec_IntAlloc( 256 );
00062     // allocate temporary storage for truth tables
00063     nWords = Kit_TruthWordNum(pPars->nVarsMax);
00064     p->ppTruths[0][0] = ALLOC( unsigned, 32 * nWords );
00065     p->ppTruths[1][0] = p->ppTruths[0][0] + 1 * nWords;
00066     for ( i = 1; i < 2; i++ )
00067         p->ppTruths[1][i] = p->ppTruths[1][0] + i * nWords;
00068     p->ppTruths[2][0] = p->ppTruths[1][0] + 2 * nWords;
00069     for ( i = 1; i < 4; i++ )
00070         p->ppTruths[2][i] = p->ppTruths[2][0] + i * nWords;
00071     p->ppTruths[3][0] = p->ppTruths[2][0] + 4 * nWords; 
00072     for ( i = 1; i < 8; i++ )
00073         p->ppTruths[3][i] = p->ppTruths[3][0] + i * nWords;
00074     p->ppTruths[4][0] = p->ppTruths[3][0] + 8 * nWords; 
00075     for ( i = 1; i < 16; i++ )
00076         p->ppTruths[4][i] = p->ppTruths[4][0] + i * nWords;
00077     return p;
00078 }

void Lpk_ManStop ( Lpk_Man_t *  p  ) 

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 91 of file lpkMan.c.

00092 {
00093     int i;
00094     free( p->ppTruths[0][0] );
00095     Vec_IntFree( p->vBddDir );
00096     Vec_IntFree( p->vBddInv );
00097     Vec_IntFree( p->vMemory );
00098     Kit_DsdManFree( p->pDsdMan );
00099     for ( i = 0; i < 8; i++ )
00100         Vec_IntFree(p->vSets[i]);
00101     if ( p->pIfMan )
00102     {
00103         void * pPars = p->pIfMan->pPars;
00104         If_ManStop( p->pIfMan );
00105         free( pPars );
00106     }
00107     if ( p->vLevels )
00108         Vec_VecFree( p->vLevels );
00109     if ( p->vVisited )
00110         Vec_VecFree( p->vVisited );
00111     Vec_PtrFree( p->vLeaves );
00112     Vec_IntFree( p->vCover );
00113     Vec_PtrFree( p->vTtElems );
00114     Vec_PtrFree( p->vTtNodes );
00115     free( p );
00116 }

If_Obj_t* Lpk_MapPrime ( Lpk_Man_t *  p,
unsigned *  pTruth,
int  nVars,
If_Obj_t **  ppLeaves 
)

Function*************************************************************

Synopsis [Strashes one logic node using its SOP.]

Description []

SideEffects []

SeeAlso []

Definition at line 76 of file lpkMap.c.

00077 {
00078     Kit_Graph_t * pGraph;
00079     Kit_Node_t * pNode;
00080     If_Obj_t * pRes;
00081     int i;
00082     // derive the factored form
00083     pGraph = Kit_TruthToGraph( pTruth, nVars, p->vCover );
00084     if ( pGraph == NULL )
00085         return NULL;
00086     // collect the fanins
00087     Kit_GraphForEachLeaf( pGraph, pNode, i )
00088         pNode->pFunc = ppLeaves[i];
00089     // perform strashing
00090     pRes = Lpk_MapPrimeInternal( p->pIfMan, pGraph );
00091     pRes = If_NotCond( pRes, Kit_GraphIsComplement(pGraph) );
00092     Kit_GraphFree( pGraph );
00093     return pRes;
00094 }

If_Obj_t* Lpk_MapSuppRedDec_rec ( Lpk_Man_t *  p,
unsigned *  pTruth,
int  nVars,
If_Obj_t **  ppLeaves 
)

Function*************************************************************

Synopsis [Implements support-reducing decomposition.]

Description []

SideEffects []

SeeAlso []

Definition at line 130 of file lpkMux.c.

00131 {
00132     Kit_DsdNtk_t * pNtkDec, * pNtkComp, * ppNtks[2], * pTemp;
00133     If_Obj_t * pObjNew;
00134     unsigned * pCof0 = Vec_PtrEntry( p->vTtNodes,  0 );
00135     unsigned * pCof1 = Vec_PtrEntry( p->vTtNodes,  1 );
00136     unsigned * pDec0 = Vec_PtrEntry( p->vTtNodes,  2 );
00137     unsigned * pDec1 = Vec_PtrEntry( p->vTtNodes,  3 );
00138     unsigned * pDec  = Vec_PtrEntry( p->vTtNodes,  4 );
00139     unsigned * pCo00 = Vec_PtrEntry( p->vTtNodes,  5 );
00140     unsigned * pCo01 = Vec_PtrEntry( p->vTtNodes,  6 );
00141     unsigned * pCo10 = Vec_PtrEntry( p->vTtNodes,  7 );
00142     unsigned * pCo11 = Vec_PtrEntry( p->vTtNodes,  8 );
00143     unsigned * pCo0  = Vec_PtrEntry( p->vTtNodes,  9 );
00144     unsigned * pCo1  = Vec_PtrEntry( p->vTtNodes, 10 );
00145     unsigned * pCo   = Vec_PtrEntry( p->vTtNodes, 11 );
00146     int TrueMint0, TrueMint1, FalseMint0, FalseMint1;
00147     int uSubsets, uSubset0, uSubset1, iVar, iVarReused, i;
00148 
00149     // determine if supp-red decomposition exists
00150     uSubsets = Lpk_MapSuppRedDecSelect( p, pTruth, nVars, &iVar, &iVarReused );
00151     if ( uSubsets == 0 )
00152         return NULL;
00153     p->nCalledSRed++;
00154 
00155     // get the cofactors
00156     Kit_TruthCofactor0New( pCof0, pTruth, nVars, iVar );
00157     Kit_TruthCofactor1New( pCof1, pTruth, nVars, iVar );
00158 
00159     // get the bound sets
00160     uSubset0 = uSubsets & 0xFFFF;
00161     uSubset1 = uSubsets >> 16;
00162 
00163     // compute the decomposed functions
00164     ppNtks[0] = Kit_DsdDecompose( pCof0, nVars );
00165     ppNtks[1] = Kit_DsdDecompose( pCof1, nVars );
00166     ppNtks[0] = Kit_DsdExpand( pTemp = ppNtks[0] );      Kit_DsdNtkFree( pTemp );
00167     ppNtks[1] = Kit_DsdExpand( pTemp = ppNtks[1] );      Kit_DsdNtkFree( pTemp );
00168     Kit_DsdTruthPartial( p->pDsdMan, ppNtks[0], pDec0, uSubset0 );
00169     Kit_DsdTruthPartial( p->pDsdMan, ppNtks[1], pDec1, uSubset1 );
00170 //    Kit_DsdTruthPartialTwo( p->pDsdMan, ppNtks[0], uSubset0, iVarReused, pCo0, pDec0 );
00171 //    Kit_DsdTruthPartialTwo( p->pDsdMan, ppNtks[1], uSubset1, iVarReused, pCo1, pDec1 );
00172     Kit_DsdNtkFree( ppNtks[0] );
00173     Kit_DsdNtkFree( ppNtks[1] );
00174 //Kit_DsdPrintFromTruth( pDec0, nVars );
00175 //Kit_DsdPrintFromTruth( pDec1, nVars );
00176     // get the decomposed function
00177     Kit_TruthMuxVar( pDec, pDec0, pDec1, nVars, iVar );
00178 
00179     // find any true assignments of the decomposed functions
00180     TrueMint0 = Kit_TruthFindFirstBit( pDec0, nVars );
00181     TrueMint1 = Kit_TruthFindFirstBit( pDec1, nVars );
00182     assert( TrueMint0 >= 0 && TrueMint1 >= 0 );
00183     // find any false assignments of the decomposed functions
00184     FalseMint0 = Kit_TruthFindFirstZero( pDec0, nVars );
00185     FalseMint1 = Kit_TruthFindFirstZero( pDec1, nVars );
00186     assert( FalseMint0 >= 0 && FalseMint1 >= 0 );
00187 
00188     // cofactor the cofactors according to these minterms
00189     Kit_TruthCopy( pCo00, pCof0, nVars );
00190     Kit_TruthCopy( pCo01, pCof0, nVars );
00191     for ( i = 0; i < nVars; i++ )
00192         if ( uSubset0 & (1 << i) )
00193         {
00194             if ( FalseMint0 & (1 << i) )
00195                 Kit_TruthCofactor1( pCo00, nVars, i );
00196             else
00197                 Kit_TruthCofactor0( pCo00, nVars, i );
00198             if ( TrueMint0 & (1 << i) )
00199                 Kit_TruthCofactor1( pCo01, nVars, i );
00200             else
00201                 Kit_TruthCofactor0( pCo01, nVars, i );
00202         }
00203     Kit_TruthCopy( pCo10, pCof1, nVars );
00204     Kit_TruthCopy( pCo11, pCof1, nVars );
00205     for ( i = 0; i < nVars; i++ )
00206         if ( uSubset1 & (1 << i) )
00207         {
00208             if ( FalseMint1 & (1 << i) )
00209                 Kit_TruthCofactor1( pCo10, nVars, i );
00210             else
00211                 Kit_TruthCofactor0( pCo10, nVars, i );
00212             if ( TrueMint1 & (1 << i) )
00213                 Kit_TruthCofactor1( pCo11, nVars, i );
00214             else
00215                 Kit_TruthCofactor0( pCo11, nVars, i );
00216         }
00217 
00218     // derive the functions by composing them with the new variable (iVarReused)
00219     Kit_TruthMuxVar( pCo0, pCo00, pCo01, nVars, iVarReused );
00220     Kit_TruthMuxVar( pCo1, pCo10, pCo11, nVars, iVarReused );
00221 //Kit_DsdPrintFromTruth( pCo0, nVars );
00222 //Kit_DsdPrintFromTruth( pCo1, nVars );
00223 
00224     // derive the composition function
00225     Kit_TruthMuxVar( pCo , pCo0 , pCo1 , nVars, iVar );
00226 
00227     // process the decomposed function
00228     pNtkDec = Kit_DsdDecompose( pDec, nVars );
00229     pNtkComp = Kit_DsdDecompose( pCo, nVars );
00230 //Kit_DsdPrint( stdout, pNtkDec );
00231 //Kit_DsdPrint( stdout, pNtkComp );
00232 //printf( "cofactored variable %c\n", 'a' + iVar );
00233 //printf( "reused variable %c\n", 'a' + iVarReused );
00234 
00235     ppLeaves[iVarReused] = Lpk_MapTree_rec( p, pNtkDec, ppLeaves, pNtkDec->Root, NULL );
00236     pObjNew = Lpk_MapTree_rec( p, pNtkComp, ppLeaves, pNtkComp->Root, NULL );
00237 
00238     Kit_DsdNtkFree( pNtkDec );
00239     Kit_DsdNtkFree( pNtkComp );
00240     return pObjNew;
00241 }

unsigned Lpk_MapSuppRedDecSelect ( Lpk_Man_t *  p,
unsigned *  pTruth,
int  nVars,
int *  piVar,
int *  piVarReused 
)

Function*************************************************************

Synopsis [Evaluates the cofactors.]

Description []

SideEffects []

SeeAlso []

Definition at line 320 of file lpkSets.c.

00321 {
00322     static int nStoreSize = 256;
00323     static Lpk_Set_t pStore[256], * pSet, * pSetBest;
00324     Kit_DsdNtk_t * ppNtks[2], * pTemp;
00325     Vec_Int_t * vSets0 = p->vSets[0];
00326     Vec_Int_t * vSets1 = p->vSets[1];
00327     unsigned * pCof0 = Vec_PtrEntry( p->vTtNodes, 0 );
00328     unsigned * pCof1 = Vec_PtrEntry( p->vTtNodes, 1 );
00329     int nSets, i, SizeMax;//, SRedMax;
00330     unsigned Entry;
00331     int fVerbose = p->pPars->fVeryVerbose;
00332 //    int fVerbose = 0;
00333 
00334     // collect decomposable subsets for each pair of cofactors
00335     if ( fVerbose )
00336     {
00337         printf( "\nExploring support-reducing bound-sets of function:\n" );
00338         Kit_DsdPrintFromTruth( pTruth, nVars );
00339     }
00340     nSets = 0;
00341     for ( i = 0; i < nVars; i++ )
00342     {
00343         if ( fVerbose )
00344         printf( "Evaluating variable %c:\n", 'a'+i );
00345         // evaluate the cofactor pair
00346         Kit_TruthCofactor0New( pCof0, pTruth, nVars, i );
00347         Kit_TruthCofactor1New( pCof1, pTruth, nVars, i );
00348         // decompose and expand
00349         ppNtks[0] = Kit_DsdDecompose( pCof0, nVars );
00350         ppNtks[1] = Kit_DsdDecompose( pCof1, nVars );
00351         ppNtks[0] = Kit_DsdExpand( pTemp = ppNtks[0] );      Kit_DsdNtkFree( pTemp );
00352         ppNtks[1] = Kit_DsdExpand( pTemp = ppNtks[1] );      Kit_DsdNtkFree( pTemp );
00353         if ( fVerbose )
00354         Kit_DsdPrint( stdout, ppNtks[0] );
00355         if ( fVerbose )
00356         Kit_DsdPrint( stdout, ppNtks[1] );
00357         // compute subsets
00358         Lpk_ComputeSets( ppNtks[0], vSets0 );
00359         Lpk_ComputeSets( ppNtks[1], vSets1 );
00360         // print subsets
00361         if ( fVerbose )
00362         Lpk_PrintSets( vSets0 );
00363         if ( fVerbose )
00364         Lpk_PrintSets( vSets1 );
00365         // free the networks
00366         Kit_DsdNtkFree( ppNtks[0] );
00367         Kit_DsdNtkFree( ppNtks[1] );
00368         // evaluate the pair
00369         Lpk_ComposeSets( vSets0, vSets1, nVars, i, pStore, &nSets, nStoreSize );
00370     }
00371 
00372     // print the results
00373     if ( fVerbose )
00374     printf( "\n" );
00375     if ( fVerbose )
00376     for ( i = 0; i < nSets; i++ )
00377         Lpk_MapSuppPrintSet( pStore + i, i );
00378 
00379     // choose the best subset
00380     SizeMax = 0;
00381     pSetBest = NULL;
00382     for ( i = 0; i < nSets; i++ )
00383     {
00384         pSet = pStore + i;
00385         if ( pSet->Size > p->pPars->nLutSize - 1 )
00386             continue;
00387         if ( SizeMax < pSet->Size )
00388         {
00389             pSetBest = pSet;
00390             SizeMax = pSet->Size;
00391         }
00392     }
00393 /*
00394     // if the best is not choosen, select the one with largest reduction
00395     SRedMax = 0;
00396     if ( pSetBest == NULL )
00397     {
00398         for ( i = 0; i < nSets; i++ )
00399         {
00400             pSet = pStore + i;
00401             if ( SRedMax < pSet->SRed )
00402             {
00403                 pSetBest = pSet;
00404                 SRedMax = pSet->SRed;
00405             }
00406         }
00407     }
00408 */
00409     if ( pSetBest == NULL )
00410     {
00411         if ( fVerbose )
00412         printf( "Could not select a subset.\n" );
00413         return 0;
00414     }
00415     else
00416     {
00417         if ( fVerbose )
00418         printf( "Selected the following subset:\n" );
00419         if ( fVerbose )
00420         Lpk_MapSuppPrintSet( pSetBest, pSetBest - pStore );
00421     }
00422 
00423     // prepare the return result
00424     // get the remaining variables
00425     Entry = ((pSetBest->uSubset0 >> 16) | (pSetBest->uSubset1 >> 16));
00426     // get the variables to be removed
00427     Entry = Kit_BitMask(nVars) & ~(1<<pSetBest->iVar) & ~Entry;
00428     // make sure there are some - otherwise it is not supp-red
00429     assert( Entry );
00430     // remember the first such variable
00431     *piVarReused = Kit_WordFindFirstBit( Entry );
00432     *piVar = pSetBest->iVar;
00433     return (pSetBest->uSubset1 << 16) | (pSetBest->uSubset0 & 0xFFFF);
00434 }

If_Obj_t* Lpk_MapTree_rec ( Lpk_Man_t *  p,
Kit_DsdNtk_t *  pNtk,
If_Obj_t **  ppLeaves,
int  iLit,
If_Obj_t *  pResult 
)

Function*************************************************************

Synopsis [Prepares the mapping manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 107 of file lpkMap.c.

00108 {
00109     Kit_DsdObj_t * pObj;
00110     If_Obj_t * pObjNew = NULL, * pObjNew2 = NULL, * pFansNew[16];
00111     unsigned i, iLitFanin;
00112 
00113     assert( iLit >= 0 );
00114 
00115     // consider the case of a gate
00116     pObj = Kit_DsdNtkObj( pNtk, Kit_DsdLit2Var(iLit) );
00117     if ( pObj == NULL )
00118     {
00119         pObjNew = ppLeaves[Kit_DsdLit2Var(iLit)];
00120         return If_NotCond( pObjNew, Kit_DsdLitIsCompl(iLit) );
00121     }
00122     if ( pObj->Type == KIT_DSD_CONST1 )
00123     {
00124         return If_NotCond( If_ManConst1(p->pIfMan), Kit_DsdLitIsCompl(iLit) );
00125     }
00126     if ( pObj->Type == KIT_DSD_VAR )
00127     {
00128         pObjNew = ppLeaves[Kit_DsdLit2Var(pObj->pFans[0])];
00129         return If_NotCond( pObjNew, Kit_DsdLitIsCompl(iLit) ^ Kit_DsdLitIsCompl(pObj->pFans[0]) );
00130     }
00131     if ( pObj->Type == KIT_DSD_AND )
00132     {
00133         assert( pObj->nFans == 2 );
00134         pFansNew[0] = Lpk_MapTree_rec( p, pNtk, ppLeaves, pObj->pFans[0], NULL );
00135         pFansNew[1] = pResult? pResult : Lpk_MapTree_rec( p, pNtk, ppLeaves, pObj->pFans[1], NULL );
00136         if ( pFansNew[0] == NULL || pFansNew[1] == NULL )
00137             return NULL;
00138         pObjNew = If_ManCreateAnd( p->pIfMan, pFansNew[0], pFansNew[1] ); 
00139         return If_NotCond( pObjNew, Kit_DsdLitIsCompl(iLit) );
00140     }
00141     if ( pObj->Type == KIT_DSD_XOR )
00142     {
00143         int fCompl = Kit_DsdLitIsCompl(iLit);
00144         assert( pObj->nFans == 2 );
00145         pFansNew[0] = Lpk_MapTree_rec( p, pNtk, ppLeaves, pObj->pFans[0], NULL );
00146         pFansNew[1] = pResult? pResult : Lpk_MapTree_rec( p, pNtk, ppLeaves, pObj->pFans[1], NULL );
00147         if ( pFansNew[0] == NULL || pFansNew[1] == NULL )
00148             return NULL;
00149         fCompl ^= If_IsComplement(pFansNew[0]) ^ If_IsComplement(pFansNew[1]);
00150         pObjNew = If_ManCreateXor( p->pIfMan, If_Regular(pFansNew[0]), If_Regular(pFansNew[1]) );
00151         return If_NotCond( pObjNew, fCompl );
00152     }
00153     assert( pObj->Type == KIT_DSD_PRIME );
00154     p->nBlocks[pObj->nFans]++;
00155 
00156     // solve for the inputs
00157     Kit_DsdObjForEachFanin( pNtk, pObj, iLitFanin, i )
00158     {
00159         if ( i == 0 )
00160             pFansNew[i] = pResult? pResult : Lpk_MapTree_rec( p, pNtk, ppLeaves, iLitFanin, NULL );
00161         else
00162             pFansNew[i] = Lpk_MapTree_rec( p, pNtk, ppLeaves, iLitFanin, NULL );
00163         if ( pFansNew[i] == NULL )
00164             return NULL;
00165     }
00166 /* 
00167     if ( !p->fCofactoring && p->pPars->nVarsShared > 0 && (int)pObj->nFans > p->pPars->nLutSize )
00168     {
00169         pObjNew = Lpk_MapTreeMulti( p, Kit_DsdObjTruth(pObj), pObj->nFans, pFansNew );
00170         return If_NotCond( pObjNew, Kit_DsdLitIsCompl(iLit) );
00171     }
00172 */
00173 /*
00174     if ( (int)pObj->nFans > p->pPars->nLutSize )
00175     {
00176         pObjNew2 = Lpk_MapTreeMux_rec( p, Kit_DsdObjTruth(pObj), pObj->nFans, pFansNew );
00177 //        if ( pObjNew2 )
00178 //            return If_NotCond( pObjNew2, Kit_DsdLitIsCompl(iLit) );
00179     }
00180 */
00181 
00182     // find best cofactoring variable
00183     if ( p->pPars->nVarsShared > 0 && (int)pObj->nFans > p->pPars->nLutSize )
00184     {
00185         pObjNew2 = Lpk_MapSuppRedDec_rec( p, Kit_DsdObjTruth(pObj), pObj->nFans, pFansNew );
00186         if ( pObjNew2 )
00187             return If_NotCond( pObjNew2, Kit_DsdLitIsCompl(iLit) );
00188     }
00189 
00190     pObjNew = Lpk_MapPrime( p, Kit_DsdObjTruth(pObj), pObj->nFans, pFansNew );
00191 
00192     // add choice
00193     if ( pObjNew && pObjNew2 )
00194     {
00195         If_ObjSetChoice( If_Regular(pObjNew), If_Regular(pObjNew2) );
00196         If_ManCreateChoice( p->pIfMan, If_Regular(pObjNew) );
00197     }
00198     return If_NotCond( pObjNew, Kit_DsdLitIsCompl(iLit) );
00199 }

If_Obj_t* Lpk_MapTreeMulti ( Lpk_Man_t *  p,
unsigned *  pTruth,
int  nVars,
If_Obj_t **  ppLeaves 
)

Function*************************************************************

Synopsis [Prepares the mapping manager.]

Description []

SideEffects []

SeeAlso []

Definition at line 344 of file lpkMulti.c.

00345 {
00346     static Counter = 0;
00347     If_Obj_t * pResult;
00348     Kit_DsdNtk_t * ppNtks[8] = {0}, * pTemp;
00349     Kit_DsdObj_t * pRoot;
00350     int piCofVar[4], pPrios[16], pFreqs[16] = {0}, piLits[16];
00351     int i, k, nCBars, nSize, nMemSize;
00352     unsigned * ppCofs[4][8], uSupport;
00353     char pTable[16][16] = {0};
00354     int fVerbose = p->pPars->fVeryVerbose;
00355 
00356     Counter++;
00357 //    printf( "Run %d.\n", Counter );
00358 
00359     // allocate storage for cofactors
00360     nMemSize = Kit_TruthWordNum(nVars);
00361     ppCofs[0][0] = ALLOC( unsigned, 32 * nMemSize );
00362     nSize = 0;
00363     for ( i = 0; i < 4; i++ )
00364     for ( k = 0; k < 8; k++ )
00365         ppCofs[i][k] = ppCofs[0][0] + nMemSize * nSize++;
00366     assert( nSize == 32 );
00367 
00368     // find the best cofactoring variables
00369     nCBars = Kit_DsdCofactoring( pTruth, nVars, piCofVar, p->pPars->nVarsShared, 0 );
00370 //    nCBars = 2;
00371 //    piCofVar[0] = 0;
00372 //    piCofVar[1] = 1;
00373 
00374 
00375     // copy the function
00376     Kit_TruthCopy( ppCofs[0][0], pTruth, nVars );
00377 
00378     // decompose w.r.t. these variables
00379     for ( k = 0; k < nCBars; k++ )
00380     {
00381         nSize = (1 << k);
00382         for ( i = 0; i < nSize; i++ )
00383         {
00384             Kit_TruthCofactor0New( ppCofs[k+1][2*i+0], ppCofs[k][i], nVars, piCofVar[k] );
00385             Kit_TruthCofactor1New( ppCofs[k+1][2*i+1], ppCofs[k][i], nVars, piCofVar[k] );
00386         }
00387     }
00388     nSize = (1 << nCBars);
00389     // compute DSD networks
00390     for ( i = 0; i < nSize; i++ )
00391     {
00392         ppNtks[i] = Kit_DsdDecompose( ppCofs[nCBars][i], nVars );
00393         ppNtks[i] = Kit_DsdExpand( pTemp = ppNtks[i] );
00394         Kit_DsdNtkFree( pTemp );
00395         if ( fVerbose )
00396         {
00397             printf( "Cof%d%d: ", nCBars, i );
00398             Kit_DsdPrint( stdout, ppNtks[i] );
00399         }
00400     }
00401 
00402     // compute variable frequences
00403     for ( i = 0; i < nSize; i++ )
00404     {
00405         uSupport = Kit_TruthSupport( ppCofs[nCBars][i], nVars );
00406         for ( k = 0; k < nVars; k++ )
00407             if ( uSupport & (1<<k) )
00408                 pFreqs[k]++;
00409     }
00410 
00411     // find common variable order
00412     for ( i = 0; i < nSize; i++ )
00413     {
00414         Kit_DsdGetSupports( ppNtks[i] );
00415         Lpk_CreateVarOrder( ppNtks[i], pTable );
00416     }
00417     Lpk_CreateCommonOrder( pTable, piCofVar, nCBars, pPrios, nVars, fVerbose );
00418     // update priorities with frequences
00419     for ( i = 0; i < nVars; i++ )
00420         pPrios[i] = pPrios[i] * 256 + (16 - pFreqs[i]) * 16 + i;
00421 
00422     if ( fVerbose )
00423         printf( "After restructuring with priority:\n" );
00424 
00425     if ( Counter == 1 )
00426     {
00427         int x = 0;
00428     }
00429     // transform all networks according to the variable order
00430     for ( i = 0; i < nSize; i++ )
00431     {
00432         ppNtks[i] = Kit_DsdShrink( pTemp = ppNtks[i], pPrios );
00433         Kit_DsdNtkFree( pTemp );
00434         Kit_DsdGetSupports( ppNtks[i] );
00435         assert( ppNtks[i]->pSupps[0] <= 0xFFFF );
00436         // undec nodes should be rotated in such a way that the first input has as many shared inputs as possible
00437         Kit_DsdRotate( ppNtks[i], pFreqs );
00438         // print the resulting networks
00439         if ( fVerbose )
00440         {
00441             printf( "Cof%d%d: ", nCBars, i );
00442             Kit_DsdPrint( stdout, ppNtks[i] );
00443         }
00444     }
00445  
00446     for ( i = 0; i < nSize; i++ )
00447     {
00448         // collect the roots
00449         pRoot = Kit_DsdNtkRoot(ppNtks[i]);
00450         if ( pRoot->Type == KIT_DSD_CONST1 )
00451             piLits[i] = Kit_DsdLitIsCompl(ppNtks[i]->Root)? -2: -1;
00452         else if ( pRoot->Type == KIT_DSD_VAR )
00453             piLits[i] = Kit_DsdLitNotCond( pRoot->pFans[0], Kit_DsdLitIsCompl(ppNtks[i]->Root) );
00454         else
00455             piLits[i] = ppNtks[i]->Root;
00456     }
00457 
00458 
00459     // recursively construct AIG for mapping
00460     p->fCofactoring = 1;
00461     pResult = Lpk_MapTreeMulti_rec( p, ppNtks, piLits, piCofVar, nCBars, ppLeaves, nVars, pPrios );
00462     p->fCofactoring = 0;
00463 
00464     if ( fVerbose )
00465         printf( "\n" );
00466 
00467     // verify the transformations
00468     nSize = (1 << nCBars);
00469     for ( i = 0; i < nSize; i++ )
00470         Kit_DsdTruth( ppNtks[i], ppCofs[nCBars][i] );
00471     // mux the truth tables
00472     for ( k = nCBars-1; k >= 0; k-- )
00473     {
00474         nSize = (1 << k);
00475         for ( i = 0; i < nSize; i++ )
00476             Kit_TruthMuxVar( ppCofs[k][i], ppCofs[k+1][2*i+0], ppCofs[k+1][2*i+1], nVars, piCofVar[k] );
00477     }
00478     if ( !Extra_TruthIsEqual( pTruth, ppCofs[0][0], nVars ) )
00479         printf( "Verification failed.\n" );
00480 
00481 
00482     // free the networks
00483     for ( i = 0; i < 8; i++ )
00484         if ( ppNtks[i] )
00485             Kit_DsdNtkFree( ppNtks[i] );
00486     free( ppCofs[0][0] );
00487 
00488     return pResult;
00489 }

If_Obj_t* Lpk_MapTreeMux_rec ( Lpk_Man_t *  p,
unsigned *  pTruth,
int  nVars,
If_Obj_t **  ppLeaves 
)

Function*************************************************************

Synopsis [Maps the function by the best cofactoring.]

Description []

SideEffects []

SeeAlso []

Definition at line 86 of file lpkMux.c.

00087 {
00088     unsigned * pCof0 = Vec_PtrEntry( p->vTtNodes, 0 );
00089     unsigned * pCof1 = Vec_PtrEntry( p->vTtNodes, 1 );
00090     If_Obj_t * pObj0, * pObj1;
00091     Kit_DsdNtk_t * ppNtks[2];
00092     int iBestVar;
00093     assert( nVars > 3 );
00094     p->fCalledOnce = 1;
00095     // cofactor w.r.t. the best variable
00096     iBestVar = Lpk_MapTreeBestCofVar( p, pTruth, nVars, pCof0, pCof1 );
00097     if ( iBestVar == -1 )
00098         return NULL;
00099     // decompose the functions
00100     ppNtks[0] = Kit_DsdDecompose( pCof0, nVars );
00101     ppNtks[1] = Kit_DsdDecompose( pCof1, nVars );
00102     if ( p->pPars->fVeryVerbose )
00103     {
00104         printf( "Cofactoring w.r.t. var %c (%d -> %d+%d supp vars):\n", 
00105             'a'+iBestVar, nVars, Kit_TruthSupportSize(pCof0, nVars), Kit_TruthSupportSize(pCof1, nVars) );
00106         Kit_DsdPrintExpanded( ppNtks[0] );
00107         Kit_DsdPrintExpanded( ppNtks[1] );
00108     }
00109     // map the DSD structures
00110     pObj0 = Lpk_MapTree_rec( p, ppNtks[0], ppLeaves, ppNtks[0]->Root, NULL );
00111     pObj1 = Lpk_MapTree_rec( p, ppNtks[1], ppLeaves, ppNtks[1]->Root, NULL );
00112     Kit_DsdNtkFree( ppNtks[0] );
00113     Kit_DsdNtkFree( ppNtks[1] );
00114     return If_ManCreateMux( p->pIfMan, pObj0, pObj1, ppLeaves[iBestVar] );
00115 }

Lpk_Res_t* Lpk_MuxAnalize ( Lpk_Man_t *  pMan,
Lpk_Fun_t *  p 
)

CFile****************************************************************

FileName [lpkAbcMux.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Fast Boolean matching for LUT structures.]

Synopsis [LUT-decomposition based on recursive MUX decomposition.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - April 28, 2007.]

Revision [

Id
lpkAbcMux.c,v 1.00 2007/04/28 00:00:00 alanmi Exp

] DECLARATIONS /// FUNCTION DEFINITIONS ///Function*************************************************************

Synopsis [Checks the possibility of MUX decomposition.]

Description [Returns the best variable to use for MUX decomposition.]

SideEffects []

SeeAlso []

Definition at line 42 of file lpkAbcMux.c.

00043 {
00044     static Lpk_Res_t Res, * pRes = &Res;
00045     int nSuppSize0, nSuppSize1, nSuppSizeS, nSuppSizeL;
00046     int Var, Area, Polarity, Delay, Delay0, Delay1, DelayA, DelayB;
00047     memset( pRes, 0, sizeof(Lpk_Res_t) );
00048     assert( p->uSupp == Kit_BitMask(p->nVars) );
00049     assert( p->fSupports );
00050     // derive the delay and area after MUX-decomp with each var - and find the best var
00051     pRes->Variable = -1;
00052     Lpk_SuppForEachVar( p->uSupp, Var )
00053     {
00054         nSuppSize0 = Kit_WordCountOnes(p->puSupps[2*Var+0]);
00055         nSuppSize1 = Kit_WordCountOnes(p->puSupps[2*Var+1]);
00056         assert( nSuppSize0 < (int)p->nVars );
00057         assert( nSuppSize1 < (int)p->nVars );
00058         if ( nSuppSize0 < 1 || nSuppSize1 < 1 )
00059             continue;
00060 //printf( "%d %d    ", nSuppSize0, nSuppSize1 );
00061         if ( nSuppSize0 <= (int)p->nLutK - 2 && nSuppSize1 <= (int)p->nLutK - 2 )
00062         {
00063             // include cof var into 0-block
00064             DelayA = Lpk_SuppDelay( p->puSupps[2*Var+0] | (1<<Var), p->pDelays );
00065             DelayB = Lpk_SuppDelay( p->puSupps[2*Var+1]           , p->pDelays );
00066             Delay0 = ABC_MAX( DelayA, DelayB + 1 );
00067             // include cof var into 1-block
00068             DelayA = Lpk_SuppDelay( p->puSupps[2*Var+1] | (1<<Var), p->pDelays );
00069             DelayB = Lpk_SuppDelay( p->puSupps[2*Var+0]           , p->pDelays );
00070             Delay1 = ABC_MAX( DelayA, DelayB + 1 );
00071             // get the best delay
00072             Delay = ABC_MIN( Delay0, Delay1 );
00073             Area = 2;
00074             Polarity = (int)(Delay == Delay1);
00075         }
00076         else if ( nSuppSize0 <= (int)p->nLutK - 2 )
00077         {
00078             DelayA = Lpk_SuppDelay( p->puSupps[2*Var+0] | (1<<Var), p->pDelays );
00079             DelayB = Lpk_SuppDelay( p->puSupps[2*Var+1]           , p->pDelays );
00080             Delay = ABC_MAX( DelayA, DelayB + 1 );
00081             Area = 1 + Lpk_LutNumLuts( nSuppSize1, p->nLutK );
00082             Polarity = 0;
00083         }
00084         else if ( nSuppSize1 <= (int)p->nLutK - 2 )
00085         {
00086             DelayA = Lpk_SuppDelay( p->puSupps[2*Var+1] | (1<<Var), p->pDelays );
00087             DelayB = Lpk_SuppDelay( p->puSupps[2*Var+0]           , p->pDelays );
00088             Delay = ABC_MAX( DelayA, DelayB + 1 );
00089             Area = 1 + Lpk_LutNumLuts( nSuppSize0, p->nLutK );
00090             Polarity = 1;
00091         }
00092         else if ( nSuppSize0 <= (int)p->nLutK )
00093         {
00094             DelayA = Lpk_SuppDelay( p->puSupps[2*Var+1] | (1<<Var), p->pDelays );
00095             DelayB = Lpk_SuppDelay( p->puSupps[2*Var+0]           , p->pDelays );
00096             Delay = ABC_MAX( DelayA, DelayB + 1 );
00097             Area = 1 + Lpk_LutNumLuts( nSuppSize1+2, p->nLutK );
00098             Polarity = 1;
00099         }
00100         else if ( nSuppSize1 <= (int)p->nLutK )
00101         {
00102             DelayA = Lpk_SuppDelay( p->puSupps[2*Var+0] | (1<<Var), p->pDelays );
00103             DelayB = Lpk_SuppDelay( p->puSupps[2*Var+1]           , p->pDelays );
00104             Delay = ABC_MAX( DelayA, DelayB + 1 );
00105             Area = 1 + Lpk_LutNumLuts( nSuppSize0+2, p->nLutK );
00106             Polarity = 0;
00107         }
00108         else
00109         {
00110             // include cof var into 0-block
00111             DelayA = Lpk_SuppDelay( p->puSupps[2*Var+0] | (1<<Var), p->pDelays );
00112             DelayB = Lpk_SuppDelay( p->puSupps[2*Var+1]           , p->pDelays );
00113             Delay0 = ABC_MAX( DelayA, DelayB + 1 );
00114             // include cof var into 1-block
00115             DelayA = Lpk_SuppDelay( p->puSupps[2*Var+1] | (1<<Var), p->pDelays );
00116             DelayB = Lpk_SuppDelay( p->puSupps[2*Var+0]           , p->pDelays );
00117             Delay1 = ABC_MAX( DelayA, DelayB + 1 );
00118             // get the best delay
00119             Delay = ABC_MIN( Delay0, Delay1 );
00120             if ( Delay == Delay0 )
00121                 Area = Lpk_LutNumLuts( nSuppSize0+2, p->nLutK ) + Lpk_LutNumLuts( nSuppSize1, p->nLutK );
00122             else
00123                 Area = Lpk_LutNumLuts( nSuppSize1+2, p->nLutK ) + Lpk_LutNumLuts( nSuppSize0, p->nLutK );
00124             Polarity = (int)(Delay == Delay1);
00125         }
00126         // find the best variable
00127         if ( Delay > (int)p->nDelayLim )
00128             continue;
00129         if ( Area > (int)p->nAreaLim )
00130             continue;
00131         nSuppSizeS = ABC_MIN( nSuppSize0 + 2 *!Polarity, nSuppSize1 + 2 * Polarity );
00132         nSuppSizeL = ABC_MAX( nSuppSize0 + 2 *!Polarity, nSuppSize1 + 2 * Polarity );
00133         if ( nSuppSizeL > (int)p->nVars )
00134             continue;
00135         if ( pRes->Variable == -1 || pRes->AreaEst > Area || 
00136             (pRes->AreaEst == Area && pRes->nSuppSizeS + pRes->nSuppSizeL > nSuppSizeS + nSuppSizeL) || 
00137             (pRes->AreaEst == Area && pRes->nSuppSizeS + pRes->nSuppSizeL == nSuppSizeS + nSuppSizeL && pRes->DelayEst > Delay) )
00138         {
00139             pRes->Variable = Var;
00140             pRes->Polarity = Polarity;
00141             pRes->AreaEst  = Area;
00142             pRes->DelayEst = Delay;
00143             pRes->nSuppSizeS = nSuppSizeS;
00144             pRes->nSuppSizeL = nSuppSizeL;
00145         }
00146     }
00147     return pRes->Variable == -1 ? NULL : pRes;
00148 }

Lpk_Fun_t* Lpk_MuxSplit ( Lpk_Man_t *  pMan,
Lpk_Fun_t *  p,
int  Var,
int  Pol 
)

Function*************************************************************

Synopsis [Transforms the function decomposed by the MUX decomposition.]

Description [Returns the best variable to use for MUX decomposition.]

SideEffects []

SeeAlso []

Definition at line 161 of file lpkAbcMux.c.

00162 {
00163     Lpk_Fun_t * pNew;
00164     unsigned * pTruth  = Lpk_FunTruth( p, 0 );
00165     unsigned * pTruth0 = Lpk_FunTruth( p, 1 );
00166     unsigned * pTruth1 = Lpk_FunTruth( p, 2 );
00167 //    unsigned uSupp;
00168     int iVarVac; 
00169     assert( Var >= 0 && Var < (int)p->nVars );
00170     assert( p->nAreaLim >= 2 );
00171     assert( p->uSupp == Kit_BitMask(p->nVars) );
00172     Kit_TruthCofactor0New( pTruth0, pTruth, p->nVars, Var );
00173     Kit_TruthCofactor1New( pTruth1, pTruth, p->nVars, Var );
00174 /*
00175 uSupp = Kit_TruthSupport( pTruth, p->nVars );
00176 Extra_PrintBinary( stdout, &uSupp, 16 ); printf( "\n" );
00177 uSupp = Kit_TruthSupport( pTruth0, p->nVars );
00178 Extra_PrintBinary( stdout, &uSupp, 16 ); printf( "\n" );
00179 uSupp = Kit_TruthSupport( pTruth1, p->nVars );
00180 Extra_PrintBinary( stdout, &uSupp, 16 ); printf( "\n\n" );
00181 */
00182     // derive the new component
00183     pNew = Lpk_FunDup( p, Pol ? pTruth0 : pTruth1 );
00184     // update the support of the old component
00185     p->uSupp  = Kit_TruthSupport( Pol ? pTruth1 : pTruth0, p->nVars );
00186     p->uSupp |= (1 << Var);
00187     // update the truth table of the old component
00188     iVarVac = Kit_WordFindFirstBit( ~p->uSupp );
00189     assert( iVarVac < (int)p->nVars );
00190     p->uSupp |= (1 << iVarVac);
00191     Kit_TruthIthVar( pTruth, p->nVars, iVarVac );
00192     if ( Pol )
00193         Kit_TruthMuxVar( pTruth, pTruth, pTruth1, p->nVars, Var );
00194     else
00195         Kit_TruthMuxVar( pTruth, pTruth0, pTruth, p->nVars, Var );
00196     assert( p->uSupp == Kit_TruthSupport(pTruth, p->nVars) );
00197     // set the decomposed variable
00198     p->pFanins[iVarVac] = pNew->Id;
00199     p->pDelays[iVarVac] = p->nDelayLim - 1;
00200     // support minimize both
00201     p->fSupports = 0;
00202     Lpk_FunSuppMinimize( p );
00203     Lpk_FunSuppMinimize( pNew );
00204     // update delay and area requirements
00205     pNew->nDelayLim = p->nDelayLim - 1;
00206     if ( pNew->nVars <= pNew->nLutK )
00207     {
00208         pNew->nAreaLim = 1;
00209         p->nAreaLim = p->nAreaLim - 1;
00210     }
00211     else if ( p->nVars <= p->nLutK )
00212     {
00213         pNew->nAreaLim = p->nAreaLim - 1;
00214         p->nAreaLim = 1;
00215     }
00216     else if ( p->nVars < pNew->nVars )
00217     {
00218         pNew->nAreaLim = p->nAreaLim / 2 + p->nAreaLim % 2;
00219         p->nAreaLim = p->nAreaLim / 2 - p->nAreaLim % 2;
00220     }
00221     else // if ( pNew->nVars < p->nVars )
00222     {
00223         pNew->nAreaLim = p->nAreaLim / 2 - p->nAreaLim % 2;
00224         p->nAreaLim = p->nAreaLim / 2 + p->nAreaLim % 2;
00225     }
00226     pNew->fMark = 1;
00227     return pNew;
00228 }

int Lpk_NodeCuts ( Lpk_Man_t *  p  ) 

Function*************************************************************

Synopsis [Computes the set of all cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 584 of file lpkCut.c.

00585 {
00586     Lpk_Cut_t * pCut, * pCut2;
00587     int i, k, Temp, nMffc, fChanges;
00588 
00589     // mark the MFFC of the node with the current trav ID
00590     nMffc = p->nMffc = Abc_NodeMffcLabel( p->pObj );
00591     assert( nMffc > 0 );
00592     if ( nMffc == 1 )
00593         return 0;
00594 
00595     // initialize the first cut
00596     pCut = p->pCuts; p->nCuts = 1;
00597     pCut->nNodes = 0; 
00598     pCut->nNodesDup = 0;
00599     pCut->nLeaves = 1;
00600     pCut->pLeaves[0] = p->pObj->Id;
00601     // assign the signature
00602     Lpk_NodeCutSignature( pCut );
00603 
00604     // perform the cut computation
00605     for ( i = 0; i < p->nCuts; i++ )
00606     {
00607         pCut = p->pCuts + i;
00608         if ( pCut->nLeaves == 0 )
00609             continue;
00610 
00611         // try to expand the fanins of this cut
00612         for ( k = 0; k < (int)pCut->nLeaves; k++ )
00613         {
00614             // create a new cut
00615             Lpk_NodeCutsOne( p, pCut, pCut->pLeaves[k] );
00616             // quit if the number of cuts has exceeded the limit
00617             if ( p->nCuts == LPK_CUTS_MAX )
00618                 break;
00619         }
00620         if ( p->nCuts == LPK_CUTS_MAX )
00621             break;
00622     }
00623     if ( p->nCuts == LPK_CUTS_MAX ) 
00624         p->nNodesOver++;
00625 
00626     // record the impact of this node
00627     if ( p->pPars->fSatur )
00628         Lpk_NodeRecordImpact( p );
00629 
00630     // compress the cuts by removing empty ones, those with negative Weight, and decomposable ones
00631     p->nEvals = 0;
00632     for ( i = 0; i < p->nCuts; i++ )
00633     {
00634         pCut = p->pCuts + i;
00635         if ( pCut->nLeaves < 2 )
00636             continue;
00637         // compute the minimum number of LUTs needed to implement this cut
00638         // V = N * (K-1) + 1  ~~~~~  N = Ceiling[(V-1)/(K-1)] = (V-1)/(K-1) + [(V-1)%(K-1) > 0]
00639         pCut->nLuts = Lpk_LutNumLuts( pCut->nLeaves, p->pPars->nLutSize ); 
00640 //        pCut->Weight = (float)1.0 * (pCut->nNodes - pCut->nNodesDup - 1) / pCut->nLuts; //p->pPars->nLutsMax;
00641         pCut->Weight = (float)1.0 * (pCut->nNodes - pCut->nNodesDup) / pCut->nLuts; //p->pPars->nLutsMax;
00642         if ( pCut->Weight <= 1.001 )
00643 //        if ( pCut->Weight <= 0.999 )
00644             continue;
00645         pCut->fHasDsd = Lpk_NodeCutsCheckDsd( p, pCut );
00646         if ( pCut->fHasDsd )
00647             continue;
00648         p->pEvals[p->nEvals++] = i;
00649     }
00650     if ( p->nEvals == 0 )
00651         return 0;
00652 
00653     // sort the cuts by Weight
00654     do {
00655         fChanges = 0;
00656         for ( i = 0; i < p->nEvals - 1; i++ )
00657         {
00658             pCut = p->pCuts + p->pEvals[i];
00659             pCut2 = p->pCuts + p->pEvals[i+1];
00660             if ( pCut->Weight >= pCut2->Weight - 0.001 )
00661                 continue;
00662             Temp = p->pEvals[i];
00663             p->pEvals[i] = p->pEvals[i+1];
00664             p->pEvals[i+1] = Temp;
00665             fChanges = 1;
00666         }
00667     } while ( fChanges );
00668 /*
00669     for ( i = 0; i < p->nEvals; i++ )
00670     {
00671         pCut = p->pCuts + p->pEvals[i];
00672         printf( "Cut %3d : W = %5.2f.\n", i, pCut->Weight );
00673     }
00674     printf( "\n" );
00675 */
00676     return 1;
00677 }

int Lpk_SuppDelay ( unsigned  uSupp,
char *  pDelays 
)

Function*************************************************************

Synopsis [Get the delay of the bound set.]

Description []

SideEffects []

SeeAlso []

Definition at line 212 of file lpkAbcUtil.c.

00213 {
00214     int Delay, Var;
00215     Delay = 0;
00216     Lpk_SuppForEachVar( uSupp, Var )
00217         Delay = ABC_MAX( Delay, pDelays[Var] );
00218     return Delay + 1;
00219 }

int Lpk_SuppToVars ( unsigned  uBoundSet,
char *  pVars 
)

Function*************************************************************

Synopsis [Converts support into variables.]

Description []

SideEffects []

SeeAlso []

Definition at line 232 of file lpkAbcUtil.c.

00233 {
00234     int i, nVars = 0;
00235     Lpk_SuppForEachVar( uBoundSet, i )
00236         pVars[nVars++] = i;
00237     return nVars;
00238 }

Generated on Tue Jan 5 12:19:29 2010 for abc70930 by  doxygen 1.6.1