src/aig/bdc/bdcInt.h File Reference

#include "kit.h"
#include "bdc.h"
Include dependency graph for bdcInt.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  Bdc_Fun_t_
struct  Bdc_Isf_t_
struct  Bdc_Man_t_

Defines

#define BDC_SCALE   100

Typedefs

typedef struct Bdc_Fun_t_ Bdc_Fun_t
typedef struct Bdc_Isf_t_ Bdc_Isf_t

Enumerations

enum  Bdc_Type_t {
  BDC_TYPE_NONE = 0, BDC_TYPE_CONST1, BDC_TYPE_PI, BDC_TYPE_AND,
  BDC_TYPE_OR, BDC_TYPE_XOR, BDC_TYPE_MUX, BDC_TYPE_OTHER
}

Functions

static int Bdc_IsComplement (Bdc_Fun_t *p)
static Bdc_Fun_t * Bdc_Regular (Bdc_Fun_t *p)
static Bdc_Fun_t * Bdc_Not (Bdc_Fun_t *p)
static Bdc_Fun_t * Bdc_NotCond (Bdc_Fun_t *p, int c)
static Bdc_Fun_t * Bdc_FunNew (Bdc_Man_t *p)
static void Bdc_IsfStart (Bdc_Man_t *p, Bdc_Isf_t *pF)
static void Bdc_IsfClean (Bdc_Isf_t *p)
static void Bdc_IsfCopy (Bdc_Isf_t *p, Bdc_Isf_t *q)
static void Bdc_IsfNot (Bdc_Isf_t *p)
Bdc_Fun_t * Bdc_ManDecompose_rec (Bdc_Man_t *p, Bdc_Isf_t *pIsf)
Bdc_Fun_t * Bdc_TableLookup (Bdc_Man_t *p, Bdc_Isf_t *pIsf)
void Bdc_TableAdd (Bdc_Man_t *p, Bdc_Fun_t *pFunc)
void Bdc_TableClear (Bdc_Man_t *p)
void Bdc_SuppMinimize (Bdc_Man_t *p, Bdc_Isf_t *pIsf)
int Bdc_TableCheckContainment (Bdc_Man_t *p, Bdc_Isf_t *pIsf, unsigned *puTruth)

Define Documentation

#define BDC_SCALE   100

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

FileName [bdcInt.h]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Truth-table-based bi-decomposition engine.]

Synopsis [Internal declarations.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - January 15, 2007.]

Revision [

Id
resInt.h,v 1.00 2007/01/15 00:00:00 alanmi Exp

] INCLUDES /// PARAMETERS ///

Definition at line 39 of file bdcInt.h.

Typedef Documentation

typedef struct Bdc_Fun_t_ Bdc_Fun_t

Definition at line 57 of file bdcInt.h.

typedef struct Bdc_Isf_t_ Bdc_Isf_t

Definition at line 70 of file bdcInt.h.

Enumeration Type Documentation

enum Bdc_Type_t

BASIC TYPES ///

Enumerator:
BDC_TYPE_NONE 
BDC_TYPE_CONST1 
BDC_TYPE_PI 
BDC_TYPE_AND 
BDC_TYPE_OR 
BDC_TYPE_XOR 
BDC_TYPE_MUX 
BDC_TYPE_OTHER 

Definition at line 46 of file bdcInt.h.

00046              { 
00047     BDC_TYPE_NONE = 0,  // 0:  unknown
00048     BDC_TYPE_CONST1,    // 1:  constant 1
00049     BDC_TYPE_PI,        // 2:  primary input
00050     BDC_TYPE_AND,       // 4:  AND-gate
00051     BDC_TYPE_OR,        // 5:  OR-gate (temporary)
00052     BDC_TYPE_XOR,       // 6:  XOR-gate
00053     BDC_TYPE_MUX,       // 7:  MUX-gate
00054     BDC_TYPE_OTHER      // 8:  unused
00055 } Bdc_Type_t;

Function Documentation

static Bdc_Fun_t* Bdc_FunNew ( Bdc_Man_t *  p  )  [inline, static]

Definition at line 118 of file bdcInt.h.

00118 { Bdc_Fun_t * pRes; if ( p->nNodes == p->nNodesLimit ) return NULL; pRes = p->pNodes + p->nNodes++; memset( pRes, 0, sizeof(Bdc_Fun_t) ); p->nNodesNew++; return pRes; }

static int Bdc_IsComplement ( Bdc_Fun_t *  p  )  [inline, static]

Definition at line 113 of file bdcInt.h.

00113 { return (int)((unsigned long)p & (unsigned long)01);              }

static void Bdc_IsfClean ( Bdc_Isf_t *  p  )  [inline, static]

Definition at line 120 of file bdcInt.h.

00120 { p->uSupp = 0; p->Var = 0;                                        }

static void Bdc_IsfCopy ( Bdc_Isf_t *  p,
Bdc_Isf_t *  q 
) [inline, static]

Definition at line 121 of file bdcInt.h.

00121 { Bdc_Isf_t T = *p; *p = *q; *q = T;                               }

static void Bdc_IsfNot ( Bdc_Isf_t *  p  )  [inline, static]

Definition at line 122 of file bdcInt.h.

00122 { unsigned * puT = p->puOn; p->puOn = p->puOff; p->puOff = puT;    }

static void Bdc_IsfStart ( Bdc_Man_t *  p,
Bdc_Isf_t *  pF 
) [inline, static]

Definition at line 119 of file bdcInt.h.

00119 { pF->puOn = Vec_IntFetch( p->vMemory, p->nWords ); pF->puOff = Vec_IntFetch( p->vMemory, p->nWords ); }

Bdc_Fun_t* Bdc_ManDecompose_rec ( Bdc_Man_t *  p,
Bdc_Isf_t *  pIsf 
)

MACRO DEFINITIONS /// FUNCTION DECLARATIONS ///

FUNCTION DEFINITIONS ///Function*************************************************************

Synopsis [Performs one step of bi-decomposition.]

Description []

SideEffects []

SeeAlso []

Definition at line 45 of file bdcDec.c.

00046 {
00047     Bdc_Fun_t * pFunc;
00048     Bdc_Isf_t IsfL, * pIsfL = &IsfL;
00049     Bdc_Isf_t IsfB, * pIsfR = &IsfB;
00050     // check computed results
00051     if ( pFunc = Bdc_TableLookup( p, pIsf ) )
00052         return pFunc;
00053     // decide on the decomposition type
00054     pFunc = Bdc_FunNew( p );
00055     if ( pFunc == NULL )
00056         return NULL;
00057     pFunc->Type = Bdc_DecomposeStep( p, pIsf, pIsfL, pIsfR );
00058     // decompose the left branch
00059     pFunc->pFan0 = Bdc_ManDecompose_rec( p, pIsfL );
00060     if ( pFunc->pFan0 == NULL )
00061         return NULL;
00062     // decompose the right branch
00063     if ( Bdc_DecomposeUpdateRight( p, pIsf, pIsfL, pIsfR, pFunc->pFan0->puFunc, pFunc->Type ) )
00064     {
00065         p->nNodes--;
00066         return pFunc->pFan0;
00067     }
00068     pFunc->pFan1 = Bdc_ManDecompose_rec( p, pIsfL );
00069     if ( pFunc->pFan1 == NULL )
00070         return NULL;
00071     // compute the function of node
00072     pFunc->puFunc = (unsigned *)Vec_IntFetch(p->vMemory, p->nWords); 
00073     if ( pFunc->Type == BDC_TYPE_AND )
00074         Kit_TruthAnd( pFunc->puFunc, pFunc->pFan0->puFunc, pFunc->pFan1->puFunc, p->nVars );
00075     else if ( pFunc->Type == BDC_TYPE_OR )
00076         Kit_TruthOr( pFunc->puFunc, pFunc->pFan0->puFunc, pFunc->pFan1->puFunc, p->nVars );
00077     else 
00078         assert( 0 );
00079     // verify correctness
00080     assert( Bdc_TableCheckContainment(p, pIsf, pFunc->puFunc) );
00081     // convert from OR to AND
00082     if ( pFunc->Type == BDC_TYPE_OR )
00083     {
00084         pFunc->Type = BDC_TYPE_AND;
00085         pFunc->pFan0 = Bdc_Not(pFunc->pFan0);
00086         pFunc->pFan1 = Bdc_Not(pFunc->pFan1);
00087         Kit_TruthNot( pFunc->puFunc, pFunc->puFunc, p->nVars );
00088         pFunc = Bdc_Not(pFunc);
00089     }
00090     Bdc_TableAdd( p, Bdc_Regular(pFunc) );
00091     return pFunc;
00092 }

static Bdc_Fun_t* Bdc_Not ( Bdc_Fun_t *  p  )  [inline, static]

Definition at line 115 of file bdcInt.h.

00115 { return (Bdc_Fun_t *)((unsigned long)p ^  (unsigned long)01);     }

static Bdc_Fun_t* Bdc_NotCond ( Bdc_Fun_t *  p,
int  c 
) [inline, static]

Definition at line 116 of file bdcInt.h.

00116 { return (Bdc_Fun_t *)((unsigned long)p ^  (unsigned long)(c!=0)); }

static Bdc_Fun_t* Bdc_Regular ( Bdc_Fun_t *  p  )  [inline, static]

Definition at line 114 of file bdcInt.h.

00114 { return (Bdc_Fun_t *)((unsigned long)p & ~(unsigned long)01);     }

void Bdc_SuppMinimize ( Bdc_Man_t *  p,
Bdc_Isf_t *  pIsf 
)

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

FileName [bdcTable.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Truth-table-based bi-decomposition engine.]

Synopsis [Hash table for intermediate nodes.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - January 30, 2007.]

Revision [

Id
bdcTable.c,v 1.00 2007/01/30 00:00:00 alanmi Exp

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

Synopsis [Minimizes the support of the ISF.]

Description []

SideEffects []

SeeAlso []

Definition at line 42 of file bdcTable.c.

00043 {
00044     int v;
00045     // go through the support variables
00046     for ( v = 0; v < p->nVars; v++ )
00047     {
00048         if ( (pIsf->uSupp & (1 << v)) == 0 )
00049             continue;
00050         Kit_TruthExistNew( p->puTemp1, pIsf->puOn, p->nVars, v );
00051         Kit_TruthExistNew( p->puTemp2, pIsf->puOff, p->nVars, v );
00052         if ( !Kit_TruthIsDisjoint( p->puTemp1, p->puTemp2, p->nVars ) )
00053             continue;
00054         // remove the variable
00055         Kit_TruthCopy( pIsf->puOn, p->puTemp1, p->nVars );
00056         Kit_TruthCopy( pIsf->puOff, p->puTemp2, p->nVars );
00057         pIsf->uSupp &= ~(1 << v);
00058     }
00059 }

void Bdc_TableAdd ( Bdc_Man_t *  p,
Bdc_Fun_t *  pFunc 
)

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

Synopsis [Adds the new entry to the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 109 of file bdcTable.c.

00110 {
00111     if ( p->pTable[pFunc->uSupp] == NULL )
00112         Vec_IntPush( p->vSpots, pFunc->uSupp );
00113     pFunc->pNext = p->pTable[pFunc->uSupp];
00114     p->pTable[pFunc->uSupp] = pFunc;
00115 }

int Bdc_TableCheckContainment ( Bdc_Man_t *  p,
Bdc_Isf_t *  pIsf,
unsigned *  puTruth 
)

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

Synopsis [Checks containment of the function in the ISF.]

Description []

SideEffects []

SeeAlso []

Definition at line 72 of file bdcTable.c.

00073 {
00074     return Kit_TruthIsImply( pIsf->puOn, puTruth, p->nVars ) &&
00075          Kit_TruthIsDisjoint( pIsf->puOff, puTruth, p->nVars );
00076 }

void Bdc_TableClear ( Bdc_Man_t *  p  ) 

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

Synopsis [Adds the new entry to the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 128 of file bdcTable.c.

00129 {
00130     int Spot, i;
00131     Vec_IntForEachEntry( p->vSpots, Spot, i )
00132         p->pTable[Spot] = NULL;
00133     Vec_IntClear( p->vSpots );
00134 }

Bdc_Fun_t* Bdc_TableLookup ( Bdc_Man_t *  p,
Bdc_Isf_t *  pIsf 
)

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

Synopsis [Adds the new entry to the hash table.]

Description []

SideEffects []

SeeAlso []

Definition at line 89 of file bdcTable.c.

00090 {
00091     Bdc_Fun_t * pFunc;
00092     for ( pFunc = p->pTable[pIsf->uSupp]; pFunc; pFunc = pFunc->pNext )
00093         if ( Bdc_TableCheckContainment( p, pIsf, pFunc->puFunc ) )
00094              return pFunc;
00095     return NULL;
00096 }

Generated on Tue Jan 5 12:18:13 2010 for abc70930 by  doxygen 1.6.1