src/opt/dec/dec.h File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  Dec_Edge_t_
struct  Dec_Node_t_
struct  Dec_Graph_t_
struct  Dec_Man_t_

Defines

#define Dec_GraphForEachLeaf(pGraph, pLeaf, i)   for ( i = 0; (i < (pGraph)->nLeaves) && (((pLeaf) = Dec_GraphNode(pGraph, i)), 1); i++ )
#define Dec_GraphForEachNode(pGraph, pAnd, i)   for ( i = (pGraph)->nLeaves; (i < (pGraph)->nSize) && (((pAnd) = Dec_GraphNode(pGraph, i)), 1); i++ )

Typedefs

typedef struct Dec_Edge_t_ Dec_Edge_t
typedef struct Dec_Node_t_ Dec_Node_t
typedef struct Dec_Graph_t_ Dec_Graph_t
typedef struct Dec_Man_t_ Dec_Man_t

Functions

Abc_Obj_t * Dec_GraphToNetwork (Abc_Ntk_t *pNtk, Dec_Graph_t *pGraph)
Abc_Obj_t * Dec_GraphToNetworkNoStrash (Abc_Ntk_t *pNtk, Dec_Graph_t *pGraph)
int Dec_GraphToNetworkCount (Abc_Obj_t *pRoot, Dec_Graph_t *pGraph, int NodeMax, int LevelMax)
void Dec_GraphUpdateNetwork (Abc_Obj_t *pRoot, Dec_Graph_t *pGraph, bool fUpdateLevel, int nGain)
Dec_Graph_t * Dec_Factor (char *pSop)
Dec_Man_t * Dec_ManStart ()
void Dec_ManStop (Dec_Man_t *p)
void Dec_GraphPrint (FILE *pFile, Dec_Graph_t *pGraph, char *pNamesIn[], char *pNameOut)
DdNode * Dec_GraphDeriveBdd (DdManager *dd, Dec_Graph_t *pGraph)
unsigned Dec_GraphDeriveTruth (Dec_Graph_t *pGraph)
static Dec_Edge_t Dec_EdgeCreate (int Node, int fCompl)
static unsigned Dec_EdgeToInt (Dec_Edge_t eEdge)
static Dec_Edge_t Dec_IntToEdge (unsigned Edge)
static unsigned Dec_EdgeToInt_ (Dec_Edge_t eEdge)
static Dec_Edge_t Dec_IntToEdge_ (unsigned Edge)
static Dec_Graph_t * Dec_GraphCreate (int nLeaves)
static Dec_Graph_t * Dec_GraphCreateConst0 ()
static Dec_Graph_t * Dec_GraphCreateConst1 ()
static Dec_Graph_t * Dec_GraphCreateLeaf (int iLeaf, int nLeaves, int fCompl)
static void Dec_GraphFree (Dec_Graph_t *pGraph)
static bool Dec_GraphIsConst (Dec_Graph_t *pGraph)
static bool Dec_GraphIsConst0 (Dec_Graph_t *pGraph)
static bool Dec_GraphIsConst1 (Dec_Graph_t *pGraph)
static bool Dec_GraphIsComplement (Dec_Graph_t *pGraph)
static void Dec_GraphComplement (Dec_Graph_t *pGraph)
static int Dec_GraphLeaveNum (Dec_Graph_t *pGraph)
static int Dec_GraphNodeNum (Dec_Graph_t *pGraph)
static Dec_Node_t * Dec_GraphNode (Dec_Graph_t *pGraph, int i)
static Dec_Node_t * Dec_GraphNodeLast (Dec_Graph_t *pGraph)
static int Dec_GraphNodeInt (Dec_Graph_t *pGraph, Dec_Node_t *pNode)
static bool Dec_GraphIsVar (Dec_Graph_t *pGraph)
static bool Dec_GraphNodeIsVar (Dec_Graph_t *pGraph, Dec_Node_t *pNode)
static Dec_Node_t * Dec_GraphVar (Dec_Graph_t *pGraph)
static int Dec_GraphVarInt (Dec_Graph_t *pGraph)
static void Dec_GraphSetRoot (Dec_Graph_t *pGraph, Dec_Edge_t eRoot)
static Dec_Node_t * Dec_GraphAppendNode (Dec_Graph_t *pGraph)
static Dec_Edge_t Dec_GraphAddNodeAnd (Dec_Graph_t *pGraph, Dec_Edge_t eEdge0, Dec_Edge_t eEdge1)
static Dec_Edge_t Dec_GraphAddNodeOr (Dec_Graph_t *pGraph, Dec_Edge_t eEdge0, Dec_Edge_t eEdge1)
static Dec_Edge_t Dec_GraphAddNodeXor (Dec_Graph_t *pGraph, Dec_Edge_t eEdge0, Dec_Edge_t eEdge1, int Type)
static Dec_Edge_t Dec_GraphAddNodeMux (Dec_Graph_t *pGraph, Dec_Edge_t eEdgeC, Dec_Edge_t eEdgeT, Dec_Edge_t eEdgeE, int Type)

Define Documentation

#define Dec_GraphForEachLeaf ( pGraph,
pLeaf,
i   )     for ( i = 0; (i < (pGraph)->nLeaves) && (((pLeaf) = Dec_GraphNode(pGraph, i)), 1); i++ )

ITERATORS ///

Definition at line 95 of file dec.h.

#define Dec_GraphForEachNode ( pGraph,
pAnd,
i   )     for ( i = (pGraph)->nLeaves; (i < (pGraph)->nSize) && (((pAnd) = Dec_GraphNode(pGraph, i)), 1); i++ )

Definition at line 98 of file dec.h.

Typedef Documentation

typedef struct Dec_Edge_t_ Dec_Edge_t

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

FileName [dec.h]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [A simple decomposition tree/node data structure and its APIs.]

Synopsis [External declarations.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id
dec.h,v 1.00 2005/06/20 00:00:00 alanmi Exp

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

Definition at line 40 of file dec.h.

typedef struct Dec_Graph_t_ Dec_Graph_t

Definition at line 65 of file dec.h.

typedef struct Dec_Man_t_ Dec_Man_t

Definition at line 76 of file dec.h.

typedef struct Dec_Node_t_ Dec_Node_t

Definition at line 47 of file dec.h.

Function Documentation

static Dec_Edge_t Dec_EdgeCreate ( int  Node,
int  fCompl 
) [inline, static]

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

Synopsis [Creates an edge pointing to the node in the given polarity.]

Description []

SideEffects []

SeeAlso []

Definition at line 136 of file dec.h.

00137 {
00138     Dec_Edge_t eEdge = { fCompl, Node }; 
00139     return eEdge; 
00140 }

static unsigned Dec_EdgeToInt ( Dec_Edge_t  eEdge  )  [inline, static]

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

Synopsis [Converts the edge into unsigned integer.]

Description []

SideEffects []

SeeAlso []

Definition at line 153 of file dec.h.

00154 {
00155     return (eEdge.Node << 1) | eEdge.fCompl; 
00156 }

static unsigned Dec_EdgeToInt_ ( Dec_Edge_t  eEdge  )  [inline, static]

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

Synopsis [Converts the edge into unsigned integer.]

Description []

SideEffects []

SeeAlso []

Definition at line 185 of file dec.h.

00186 {
00187     return *(unsigned *)&eEdge;
00188 }

Dec_Graph_t* Dec_Factor ( char *  pSop  ) 

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

Synopsis [Factors the cover.]

Description []

SideEffects []

SeeAlso []

Definition at line 51 of file decFactor.c.

00052 {
00053     Mvc_Cover_t * pCover;
00054     Dec_Graph_t * pFForm;
00055     Dec_Edge_t eRoot;
00056 
00057     // derive the cover from the SOP representation
00058     pCover = Dec_ConvertSopToMvc( pSop );
00059 
00060     // make sure the cover is CCS free (should be done before CST)
00061     Mvc_CoverContain( pCover );
00062     // check for trivial functions
00063     if ( Mvc_CoverIsEmpty(pCover) )
00064     {
00065         Mvc_CoverFree( pCover );
00066         return Dec_GraphCreateConst0();
00067     }
00068     if ( Mvc_CoverIsTautology(pCover) )
00069     {
00070         Mvc_CoverFree( pCover );
00071         return Dec_GraphCreateConst1();
00072     }
00073 
00074     // perform CST
00075     Mvc_CoverInverse( pCover ); // CST
00076     // start the factored form
00077     pFForm = Dec_GraphCreate( Abc_SopGetVarNum(pSop) );
00078     // factor the cover
00079     eRoot = Dec_Factor_rec( pFForm, pCover );
00080     // finalize the factored form
00081     Dec_GraphSetRoot( pFForm, eRoot );
00082     // complement the factored form if SOP is complemented
00083     if ( Abc_SopIsComplement(pSop) )
00084         Dec_GraphComplement( pFForm );
00085     // verify the factored form
00086 //    if ( !Dec_FactorVerify( pSop, pFForm ) )
00087 //        printf( "Verification has failed.\n" );
00088 //    Mvc_CoverInverse( pCover ); // undo CST
00089     Mvc_CoverFree( pCover );
00090     return pFForm;
00091 }

static Dec_Edge_t Dec_GraphAddNodeAnd ( Dec_Graph_t *  pGraph,
Dec_Edge_t  eEdge0,
Dec_Edge_t  eEdge1 
) [inline, static]

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

Synopsis [Creates an AND node.]

Description []

SideEffects []

SeeAlso []

Definition at line 587 of file dec.h.

00588 {
00589     Dec_Node_t * pNode;
00590     // get the new node
00591     pNode = Dec_GraphAppendNode( pGraph );
00592     // set the inputs and other info
00593     pNode->eEdge0 = eEdge0;
00594     pNode->eEdge1 = eEdge1;
00595     pNode->fCompl0 = eEdge0.fCompl;
00596     pNode->fCompl1 = eEdge1.fCompl;
00597     return Dec_EdgeCreate( pGraph->nSize - 1, 0 );
00598 }

static Dec_Edge_t Dec_GraphAddNodeMux ( Dec_Graph_t *  pGraph,
Dec_Edge_t  eEdgeC,
Dec_Edge_t  eEdgeT,
Dec_Edge_t  eEdgeE,
int  Type 
) [inline, static]

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

Synopsis [Creates an XOR node.]

Description []

SideEffects []

SeeAlso []

Definition at line 680 of file dec.h.

00681 {
00682     Dec_Edge_t eNode0, eNode1, eNode;
00683     if ( Type == 0 )
00684     {
00685         // derive the first AND
00686         eNode0 = Dec_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeT );
00687         // derive the second AND
00688         eEdgeC.fCompl ^= 1;
00689         eNode1 = Dec_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeE );
00690         // derive the final OR
00691         eNode = Dec_GraphAddNodeOr( pGraph, eNode0, eNode1 );
00692     }
00693     else
00694     {
00695         // complement the arguments
00696         eEdgeT.fCompl ^= 1;
00697         eEdgeE.fCompl ^= 1;
00698         // derive the first AND
00699         eNode0 = Dec_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeT );
00700         // derive the second AND
00701         eEdgeC.fCompl ^= 1;
00702         eNode1 = Dec_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeE );
00703         // derive the final OR
00704         eNode = Dec_GraphAddNodeOr( pGraph, eNode0, eNode1 );
00705         eNode.fCompl ^= 1;
00706     }
00707     return eNode;
00708 }

static Dec_Edge_t Dec_GraphAddNodeOr ( Dec_Graph_t *  pGraph,
Dec_Edge_t  eEdge0,
Dec_Edge_t  eEdge1 
) [inline, static]

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

Synopsis [Creates an OR node.]

Description []

SideEffects []

SeeAlso []

Definition at line 611 of file dec.h.

00612 {
00613     Dec_Node_t * pNode;
00614     // get the new node
00615     pNode = Dec_GraphAppendNode( pGraph );
00616     // set the inputs and other info
00617     pNode->eEdge0 = eEdge0;
00618     pNode->eEdge1 = eEdge1;
00619     pNode->fCompl0 = eEdge0.fCompl;
00620     pNode->fCompl1 = eEdge1.fCompl;
00621     // make adjustments for the OR gate
00622     pNode->fNodeOr = 1;
00623     pNode->eEdge0.fCompl = !pNode->eEdge0.fCompl;
00624     pNode->eEdge1.fCompl = !pNode->eEdge1.fCompl;
00625     return Dec_EdgeCreate( pGraph->nSize - 1, 1 );
00626 }

static Dec_Edge_t Dec_GraphAddNodeXor ( Dec_Graph_t *  pGraph,
Dec_Edge_t  eEdge0,
Dec_Edge_t  eEdge1,
int  Type 
) [inline, static]

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

Synopsis [Creates an XOR node.]

Description []

SideEffects []

SeeAlso []

Definition at line 639 of file dec.h.

00640 {
00641     Dec_Edge_t eNode0, eNode1, eNode;
00642     if ( Type == 0 )
00643     {
00644         // derive the first AND
00645         eEdge0.fCompl ^= 1;
00646         eNode0 = Dec_GraphAddNodeAnd( pGraph, eEdge0, eEdge1 );
00647         eEdge0.fCompl ^= 1;
00648         // derive the second AND
00649         eEdge1.fCompl ^= 1;
00650         eNode1 = Dec_GraphAddNodeAnd( pGraph, eEdge0, eEdge1 );
00651         // derive the final OR
00652         eNode = Dec_GraphAddNodeOr( pGraph, eNode0, eNode1 );
00653     }
00654     else
00655     {
00656         // derive the first AND
00657         eNode0 = Dec_GraphAddNodeAnd( pGraph, eEdge0, eEdge1 );
00658         // derive the second AND
00659         eEdge0.fCompl ^= 1;
00660         eEdge1.fCompl ^= 1;
00661         eNode1 = Dec_GraphAddNodeAnd( pGraph, eEdge0, eEdge1 );
00662         // derive the final OR
00663         eNode = Dec_GraphAddNodeOr( pGraph, eNode0, eNode1 );
00664         eNode.fCompl ^= 1;
00665     }
00666     return eNode;
00667 }

static Dec_Node_t* Dec_GraphAppendNode ( Dec_Graph_t *  pGraph  )  [inline, static]

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

Synopsis [Appends a new node to the graph.]

Description [This procedure is meant for internal use.]

SideEffects []

SeeAlso []

Definition at line 563 of file dec.h.

00564 {
00565     Dec_Node_t * pNode;
00566     if ( pGraph->nSize == pGraph->nCap )
00567     {
00568         pGraph->pNodes = REALLOC( Dec_Node_t, pGraph->pNodes, 2 * pGraph->nCap ); 
00569         pGraph->nCap   = 2 * pGraph->nCap;
00570     }
00571     pNode = pGraph->pNodes + pGraph->nSize++;
00572     memset( pNode, 0, sizeof(Dec_Node_t) );
00573     return pNode;
00574 }

static void Dec_GraphComplement ( Dec_Graph_t *  pGraph  )  [inline, static]

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

Synopsis [Checks if the graph is complemented.]

Description []

SideEffects []

SeeAlso []

Definition at line 384 of file dec.h.

00385 {
00386     pGraph->eRoot.fCompl ^= 1;
00387 }

static Dec_Graph_t* Dec_GraphCreate ( int  nLeaves  )  [inline, static]

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

Synopsis [Creates a graph with the given number of leaves.]

Description []

SideEffects []

SeeAlso []

Definition at line 217 of file dec.h.

00218 {
00219     Dec_Graph_t * pGraph;
00220     pGraph = ALLOC( Dec_Graph_t, 1 );
00221     memset( pGraph, 0, sizeof(Dec_Graph_t) );
00222     pGraph->nLeaves = nLeaves;
00223     pGraph->nSize = nLeaves;
00224     pGraph->nCap = 2 * nLeaves + 50;
00225     pGraph->pNodes = ALLOC( Dec_Node_t, pGraph->nCap );
00226     memset( pGraph->pNodes, 0, sizeof(Dec_Node_t) * pGraph->nSize );
00227     return pGraph;
00228 }

static Dec_Graph_t* Dec_GraphCreateConst0 (  )  [inline, static]

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

Synopsis [Creates constant 0 graph.]

Description []

SideEffects []

SeeAlso []

Definition at line 241 of file dec.h.

00242 {
00243     Dec_Graph_t * pGraph;
00244     pGraph = ALLOC( Dec_Graph_t, 1 );
00245     memset( pGraph, 0, sizeof(Dec_Graph_t) );
00246     pGraph->fConst = 1;
00247     pGraph->eRoot.fCompl = 1;
00248     return pGraph;
00249 }

static Dec_Graph_t* Dec_GraphCreateConst1 (  )  [inline, static]

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

Synopsis [Creates constant 1 graph.]

Description []

SideEffects []

SeeAlso []

Definition at line 262 of file dec.h.

00263 {
00264     Dec_Graph_t * pGraph;
00265     pGraph = ALLOC( Dec_Graph_t, 1 );
00266     memset( pGraph, 0, sizeof(Dec_Graph_t) );
00267     pGraph->fConst = 1;
00268     return pGraph;
00269 }

static Dec_Graph_t* Dec_GraphCreateLeaf ( int  iLeaf,
int  nLeaves,
int  fCompl 
) [inline, static]

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

Synopsis [Creates the literal graph.]

Description []

SideEffects []

SeeAlso []

Definition at line 282 of file dec.h.

00283 {
00284     Dec_Graph_t * pGraph;
00285     assert( 0 <= iLeaf && iLeaf < nLeaves );
00286     pGraph = Dec_GraphCreate( nLeaves );
00287     pGraph->eRoot.Node   = iLeaf;
00288     pGraph->eRoot.fCompl = fCompl;
00289     return pGraph;
00290 }

DdNode* Dec_GraphDeriveBdd ( DdManager *  dd,
Dec_Graph_t *  pGraph 
)

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

FileName [decUtil.c]

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

Synopsis [Decomposition unitilies.]

Author [MVSIS Group]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - February 1, 2003.]

Revision [

Id
decUtil.c,v 1.1 2003/05/22 19:20:05 alanmi Exp

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

Synopsis [Converts graph to BDD.]

Description []

SideEffects []

SeeAlso []

Definition at line 41 of file decUtil.c.

00042 {
00043     DdNode * bFunc, * bFunc0, * bFunc1;
00044     Dec_Node_t * pNode;
00045     int i;
00046 
00047     // sanity checks
00048     assert( Dec_GraphLeaveNum(pGraph) >= 0 );
00049     assert( Dec_GraphLeaveNum(pGraph) <= pGraph->nSize );
00050 
00051     // check for constant function
00052     if ( Dec_GraphIsConst(pGraph) )
00053         return Cudd_NotCond( b1, Dec_GraphIsComplement(pGraph) );
00054     // check for a literal
00055     if ( Dec_GraphIsVar(pGraph) )
00056         return Cudd_NotCond( Cudd_bddIthVar(dd, Dec_GraphVarInt(pGraph)), Dec_GraphIsComplement(pGraph) );
00057 
00058     // assign the elementary variables
00059     Dec_GraphForEachLeaf( pGraph, pNode, i )
00060         pNode->pFunc = Cudd_bddIthVar( dd, i );
00061 
00062     // compute the function for each internal node
00063     Dec_GraphForEachNode( pGraph, pNode, i )
00064     {
00065         bFunc0 = Cudd_NotCond( Dec_GraphNode(pGraph, pNode->eEdge0.Node)->pFunc, pNode->eEdge0.fCompl ); 
00066         bFunc1 = Cudd_NotCond( Dec_GraphNode(pGraph, pNode->eEdge1.Node)->pFunc, pNode->eEdge1.fCompl ); 
00067         pNode->pFunc = Cudd_bddAnd( dd, bFunc0, bFunc1 );   Cudd_Ref( pNode->pFunc );
00068     }
00069 
00070     // deref the intermediate results
00071     bFunc = pNode->pFunc;   Cudd_Ref( bFunc );
00072     Dec_GraphForEachNode( pGraph, pNode, i )
00073         Cudd_RecursiveDeref( dd, pNode->pFunc );
00074     Cudd_Deref( bFunc );
00075 
00076     // complement the result if necessary
00077     return Cudd_NotCond( bFunc, Dec_GraphIsComplement(pGraph) );
00078 }

unsigned Dec_GraphDeriveTruth ( Dec_Graph_t *  pGraph  ) 

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

Synopsis [Derives the truth table.]

Description []

SideEffects []

SeeAlso []

Definition at line 91 of file decUtil.c.

00092 {
00093     unsigned uTruths[5] = { 0xAAAAAAAA, 0xCCCCCCCC, 0xF0F0F0F0, 0xFF00FF00, 0xFFFF0000 };
00094     unsigned uTruth, uTruth0, uTruth1;
00095     Dec_Node_t * pNode;
00096     int i;
00097 
00098     // sanity checks
00099     assert( Dec_GraphLeaveNum(pGraph) >= 0 );
00100     assert( Dec_GraphLeaveNum(pGraph) <= pGraph->nSize );
00101     assert( Dec_GraphLeaveNum(pGraph) <= 5 );
00102 
00103     // check for constant function
00104     if ( Dec_GraphIsConst(pGraph) )
00105         return Dec_GraphIsComplement(pGraph)? 0 : ~((unsigned)0);
00106     // check for a literal
00107     if ( Dec_GraphIsVar(pGraph) )
00108         return Dec_GraphIsComplement(pGraph)? ~uTruths[Dec_GraphVarInt(pGraph)] : uTruths[Dec_GraphVarInt(pGraph)];
00109 
00110     // assign the elementary variables
00111     Dec_GraphForEachLeaf( pGraph, pNode, i )
00112         pNode->pFunc = (void *)uTruths[i];
00113 
00114     // compute the function for each internal node
00115     Dec_GraphForEachNode( pGraph, pNode, i )
00116     {
00117         uTruth0 = (unsigned)Dec_GraphNode(pGraph, pNode->eEdge0.Node)->pFunc;
00118         uTruth1 = (unsigned)Dec_GraphNode(pGraph, pNode->eEdge1.Node)->pFunc;
00119         uTruth0 = pNode->eEdge0.fCompl? ~uTruth0 : uTruth0;
00120         uTruth1 = pNode->eEdge1.fCompl? ~uTruth1 : uTruth1;
00121         uTruth = uTruth0 & uTruth1;
00122         pNode->pFunc = (void *)uTruth;
00123     }
00124 
00125     // complement the result if necessary
00126     return Dec_GraphIsComplement(pGraph)? ~uTruth : uTruth;
00127 }

static void Dec_GraphFree ( Dec_Graph_t *  pGraph  )  [inline, static]

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

Synopsis [Creates a graph with the given number of leaves.]

Description []

SideEffects []

SeeAlso []

Definition at line 303 of file dec.h.

00304 {
00305     FREE( pGraph->pNodes );
00306     free( pGraph );
00307 }

static bool Dec_GraphIsComplement ( Dec_Graph_t *  pGraph  )  [inline, static]

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

Synopsis [Returns 1 if the graph is complemented.]

Description []

SideEffects []

SeeAlso []

Definition at line 368 of file dec.h.

00369 {
00370     return pGraph->eRoot.fCompl;
00371 }

static bool Dec_GraphIsConst ( Dec_Graph_t *  pGraph  )  [inline, static]

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

Synopsis [Returns 1 if the graph is a constant.]

Description []

SideEffects []

SeeAlso []

Definition at line 320 of file dec.h.

00321 {
00322     return pGraph->fConst;
00323 }

static bool Dec_GraphIsConst0 ( Dec_Graph_t *  pGraph  )  [inline, static]

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

Synopsis [Returns 1 if the graph is constant 0.]

Description []

SideEffects []

SeeAlso []

Definition at line 336 of file dec.h.

00337 {
00338     return pGraph->fConst && pGraph->eRoot.fCompl;
00339 }

static bool Dec_GraphIsConst1 ( Dec_Graph_t *  pGraph  )  [inline, static]

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

Synopsis [Returns 1 if the graph is constant 1.]

Description []

SideEffects []

SeeAlso []

Definition at line 352 of file dec.h.

00353 {
00354     return pGraph->fConst && !pGraph->eRoot.fCompl;
00355 }

static bool Dec_GraphIsVar ( Dec_Graph_t *  pGraph  )  [inline, static]

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

Synopsis [Check if the graph represents elementary variable.]

Description []

SideEffects []

SeeAlso []

Definition at line 481 of file dec.h.

00482 {
00483     return pGraph->eRoot.Node < (unsigned)pGraph->nLeaves;
00484 }

static int Dec_GraphLeaveNum ( Dec_Graph_t *  pGraph  )  [inline, static]

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

Synopsis [Returns the number of leaves.]

Description []

SideEffects []

SeeAlso []

Definition at line 401 of file dec.h.

00402 {
00403     return pGraph->nLeaves;
00404 }

static Dec_Node_t* Dec_GraphNode ( Dec_Graph_t *  pGraph,
int  i 
) [inline, static]

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

Synopsis [Returns the pointer to the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 433 of file dec.h.

00434 {
00435     return pGraph->pNodes + i;
00436 }

static int Dec_GraphNodeInt ( Dec_Graph_t *  pGraph,
Dec_Node_t *  pNode 
) [inline, static]

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

Synopsis [Returns the number of the given node.]

Description []

SideEffects []

SeeAlso []

Definition at line 465 of file dec.h.

00466 {
00467     return pNode - pGraph->pNodes;
00468 }

static bool Dec_GraphNodeIsVar ( Dec_Graph_t *  pGraph,
Dec_Node_t *  pNode 
) [inline, static]

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

Synopsis [Check if the graph represents elementary variable.]

Description []

SideEffects []

SeeAlso []

Definition at line 497 of file dec.h.

00498 {
00499     return Dec_GraphNodeInt(pGraph,pNode) < pGraph->nLeaves;
00500 }

static Dec_Node_t* Dec_GraphNodeLast ( Dec_Graph_t *  pGraph  )  [inline, static]

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

Synopsis [Returns the pointer to the node.]

Description []

SideEffects []

SeeAlso []

Definition at line 449 of file dec.h.

00450 {
00451     return pGraph->pNodes + pGraph->nSize - 1;
00452 }

static int Dec_GraphNodeNum ( Dec_Graph_t *  pGraph  )  [inline, static]

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

Synopsis [Returns the number of internal nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 417 of file dec.h.

00418 {
00419     return pGraph->nSize - pGraph->nLeaves;
00420 }

void Dec_GraphPrint ( FILE *  pFile,
Dec_Graph_t *  pGraph,
char *  pNamesIn[],
char *  pNameOut 
)

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

Synopsis [Prints the decomposition graph.]

Description []

SideEffects []

SeeAlso []

Definition at line 46 of file decPrint.c.

00047 {
00048     Vec_Ptr_t * vNamesIn = NULL;
00049     int LitSizeMax, LitSizeCur, Pos, i;
00050 
00051     // create the names if not given by the user
00052     if ( pNamesIn == NULL )
00053     {
00054         vNamesIn = Abc_NodeGetFakeNames( Dec_GraphLeaveNum(pGraph) );
00055         pNamesIn = (char **)vNamesIn->pArray;
00056     }
00057     if ( pNameOut == NULL )
00058         pNameOut = "F";
00059 
00060     // get the size of the longest literal
00061     LitSizeMax = 0;
00062     for ( i = 0; i < Dec_GraphLeaveNum(pGraph); i++ )
00063     {
00064         LitSizeCur = strlen(pNamesIn[i]);
00065         if ( LitSizeMax < LitSizeCur )
00066             LitSizeMax = LitSizeCur;
00067     }
00068     if ( LitSizeMax > 50 )
00069         LitSizeMax = 20;
00070 
00071     // write the decomposition graph (factored form)
00072     if ( Dec_GraphIsConst(pGraph) ) // constant
00073     {
00074         Pos = Dec_GraphPrintOutputName( pFile, pNameOut, 0 );
00075         fprintf( pFile, "Constant %d", !Dec_GraphIsComplement(pGraph) );
00076     }
00077     else if ( Dec_GraphIsVar(pGraph) ) // literal
00078     {
00079         Pos = Dec_GraphPrintOutputName( pFile, pNameOut, 0 );
00080         Dec_GraphPrintGetLeafName( pFile, Dec_GraphVarInt(pGraph), Dec_GraphIsComplement(pGraph), pNamesIn );
00081     }
00082     else
00083     {
00084         Pos = Dec_GraphPrintOutputName( pFile, pNameOut, Dec_GraphIsComplement(pGraph) );
00085         Dec_GraphPrint_rec( pFile, pGraph, Dec_GraphNodeLast(pGraph), 0, pNamesIn, &Pos, LitSizeMax );
00086     }
00087     fprintf( pFile, "\n" );
00088 
00089     if ( vNamesIn )
00090         Abc_NodeFreeNames( vNamesIn );
00091 }

static void Dec_GraphSetRoot ( Dec_Graph_t *  pGraph,
Dec_Edge_t  eRoot 
) [inline, static]

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

Synopsis [Sets the root of the graph.]

Description []

SideEffects []

SeeAlso []

Definition at line 547 of file dec.h.

00548 {
00549     pGraph->eRoot = eRoot;
00550 }

Abc_Obj_t* Dec_GraphToNetwork ( Abc_Ntk_t *  pNtk,
Dec_Graph_t *  pGraph 
)

FUNCTION DECLARATIONS ///

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

FileName [decAbc.c]

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

Synopsis [Interface between the decomposition package and ABC network.]

Author [MVSIS Group]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - February 1, 2003.]

Revision [

Id
decAbc.c,v 1.1 2003/05/22 19:20:05 alanmi Exp

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

Synopsis [Transforms the decomposition graph into the AIG.]

Description [AIG nodes for the fanins should be assigned to pNode->pFunc of the leaves of the graph before calling this procedure.]

SideEffects []

SeeAlso []

Definition at line 43 of file decAbc.c.

00044 {
00045     Abc_Obj_t * pAnd0, * pAnd1;
00046     Dec_Node_t * pNode;
00047     int i;
00048     // check for constant function
00049     if ( Dec_GraphIsConst(pGraph) )
00050         return Abc_ObjNotCond( Abc_AigConst1(pNtk), Dec_GraphIsComplement(pGraph) );
00051     // check for a literal
00052     if ( Dec_GraphIsVar(pGraph) )
00053         return Abc_ObjNotCond( Dec_GraphVar(pGraph)->pFunc, Dec_GraphIsComplement(pGraph) );
00054     // build the AIG nodes corresponding to the AND gates of the graph
00055     Dec_GraphForEachNode( pGraph, pNode, i )
00056     {
00057         pAnd0 = Abc_ObjNotCond( Dec_GraphNode(pGraph, pNode->eEdge0.Node)->pFunc, pNode->eEdge0.fCompl ); 
00058         pAnd1 = Abc_ObjNotCond( Dec_GraphNode(pGraph, pNode->eEdge1.Node)->pFunc, pNode->eEdge1.fCompl ); 
00059         pNode->pFunc = Abc_AigAnd( pNtk->pManFunc, pAnd0, pAnd1 );
00060     }
00061     // complement the result if necessary
00062     return Abc_ObjNotCond( pNode->pFunc, Dec_GraphIsComplement(pGraph) );
00063 }

int Dec_GraphToNetworkCount ( Abc_Obj_t *  pRoot,
Dec_Graph_t *  pGraph,
int  NodeMax,
int  LevelMax 
)

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

Synopsis [Counts the number of new nodes added when using this graph.]

Description [AIG nodes for the fanins should be assigned to pNode->pFunc of the leaves of the graph before calling this procedure. Returns -1 if the number of nodes and levels exceeded the given limit or the number of levels exceeded the maximum allowed level.]

SideEffects []

SeeAlso []

Definition at line 117 of file decAbc.c.

00118 {
00119     Abc_Aig_t * pMan = pRoot->pNtk->pManFunc;
00120     Dec_Node_t * pNode, * pNode0, * pNode1;
00121     Abc_Obj_t * pAnd, * pAnd0, * pAnd1;
00122     int i, Counter, LevelNew, LevelOld;
00123     // check for constant function or a literal
00124     if ( Dec_GraphIsConst(pGraph) || Dec_GraphIsVar(pGraph) )
00125         return 0;
00126     // set the levels of the leaves
00127     Dec_GraphForEachLeaf( pGraph, pNode, i )
00128         pNode->Level = Abc_ObjRegular(pNode->pFunc)->Level;
00129     // compute the AIG size after adding the internal nodes
00130     Counter = 0;
00131     Dec_GraphForEachNode( pGraph, pNode, i )
00132     {
00133         // get the children of this node
00134         pNode0 = Dec_GraphNode( pGraph, pNode->eEdge0.Node );
00135         pNode1 = Dec_GraphNode( pGraph, pNode->eEdge1.Node );
00136         // get the AIG nodes corresponding to the children 
00137         pAnd0 = pNode0->pFunc; 
00138         pAnd1 = pNode1->pFunc; 
00139         if ( pAnd0 && pAnd1 )
00140         {
00141             // if they are both present, find the resulting node
00142             pAnd0 = Abc_ObjNotCond( pAnd0, pNode->eEdge0.fCompl );
00143             pAnd1 = Abc_ObjNotCond( pAnd1, pNode->eEdge1.fCompl );
00144             pAnd  = Abc_AigAndLookup( pMan, pAnd0, pAnd1 );
00145             // return -1 if the node is the same as the original root
00146             if ( Abc_ObjRegular(pAnd) == pRoot )
00147                 return -1;
00148         }
00149         else
00150             pAnd = NULL;
00151         // count the number of added nodes
00152         if ( pAnd == NULL || Abc_NodeIsTravIdCurrent(Abc_ObjRegular(pAnd)) )
00153         {
00154             if ( ++Counter > NodeMax )
00155                 return -1;
00156         }
00157         // count the number of new levels
00158         LevelNew = 1 + ABC_MAX( pNode0->Level, pNode1->Level );
00159         if ( pAnd )
00160         {
00161             if ( Abc_ObjRegular(pAnd) == Abc_AigConst1(pRoot->pNtk) )
00162                 LevelNew = 0;
00163             else if ( Abc_ObjRegular(pAnd) == Abc_ObjRegular(pAnd0) )
00164                 LevelNew = (int)Abc_ObjRegular(pAnd0)->Level;
00165             else if ( Abc_ObjRegular(pAnd) == Abc_ObjRegular(pAnd1) )
00166                 LevelNew = (int)Abc_ObjRegular(pAnd1)->Level;
00167             LevelOld = (int)Abc_ObjRegular(pAnd)->Level;
00168 //            assert( LevelNew == LevelOld );
00169         }
00170         if ( LevelNew > LevelMax )
00171             return -1;
00172         pNode->pFunc = pAnd;
00173         pNode->Level = LevelNew;
00174     }
00175     return Counter;
00176 }

Abc_Obj_t* Dec_GraphToNetworkNoStrash ( Abc_Ntk_t *  pNtk,
Dec_Graph_t *  pGraph 
)

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

Synopsis [Transforms the decomposition graph into the AIG.]

Description [AIG nodes for the fanins should be assigned to pNode->pFunc of the leaves of the graph before calling this procedure.]

SideEffects []

SeeAlso []

Definition at line 77 of file decAbc.c.

00078 {
00079     Abc_Obj_t * pAnd, * pAnd0, * pAnd1;
00080     Dec_Node_t * pNode;
00081     int i;
00082     // check for constant function
00083     if ( Dec_GraphIsConst(pGraph) )
00084         return Abc_ObjNotCond( Abc_AigConst1(pNtk), Dec_GraphIsComplement(pGraph) );
00085     // check for a literal
00086     if ( Dec_GraphIsVar(pGraph) )
00087         return Abc_ObjNotCond( Dec_GraphVar(pGraph)->pFunc, Dec_GraphIsComplement(pGraph) );
00088     // build the AIG nodes corresponding to the AND gates of the graph
00089     Dec_GraphForEachNode( pGraph, pNode, i )
00090     {
00091         pAnd0 = Abc_ObjNotCond( Dec_GraphNode(pGraph, pNode->eEdge0.Node)->pFunc, pNode->eEdge0.fCompl ); 
00092         pAnd1 = Abc_ObjNotCond( Dec_GraphNode(pGraph, pNode->eEdge1.Node)->pFunc, pNode->eEdge1.fCompl ); 
00093 //        pNode->pFunc = Abc_AigAnd( pNtk->pManFunc, pAnd0, pAnd1 );
00094         pAnd = Abc_NtkCreateNode( pNtk );
00095         Abc_ObjAddFanin( pAnd, pAnd0 );
00096         Abc_ObjAddFanin( pAnd, pAnd1 );
00097         pNode->pFunc = pAnd;
00098     }
00099     // complement the result if necessary
00100     return Abc_ObjNotCond( pNode->pFunc, Dec_GraphIsComplement(pGraph) );
00101 }

void Dec_GraphUpdateNetwork ( Abc_Obj_t *  pRoot,
Dec_Graph_t *  pGraph,
bool  fUpdateLevel,
int  nGain 
)

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

Synopsis [Replaces MFFC of the node by the new factored form.]

Description []

SideEffects []

SeeAlso []

Definition at line 190 of file decAbc.c.

00191 {
00192     Abc_Obj_t * pRootNew;
00193     Abc_Ntk_t * pNtk = pRoot->pNtk;
00194     int nNodesNew, nNodesOld;
00195     nNodesOld = Abc_NtkNodeNum(pNtk);
00196     // create the new structure of nodes
00197     pRootNew = Dec_GraphToNetwork( pNtk, pGraph );
00198     // remove the old nodes
00199     Abc_AigReplace( pNtk->pManFunc, pRoot, pRootNew, fUpdateLevel );
00200     // compare the gains
00201     nNodesNew = Abc_NtkNodeNum(pNtk);
00202     assert( nGain <= nNodesOld - nNodesNew );
00203 }

static Dec_Node_t* Dec_GraphVar ( Dec_Graph_t *  pGraph  )  [inline, static]

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

Synopsis [Returns the elementary variable elementary variable.]

Description []

SideEffects []

SeeAlso []

Definition at line 513 of file dec.h.

00514 {
00515     assert( Dec_GraphIsVar( pGraph ) );
00516     return Dec_GraphNode( pGraph, pGraph->eRoot.Node );
00517 }

static int Dec_GraphVarInt ( Dec_Graph_t *  pGraph  )  [inline, static]

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

Synopsis [Returns the number of the elementary variable.]

Description []

SideEffects []

SeeAlso []

Definition at line 530 of file dec.h.

00531 {
00532     assert( Dec_GraphIsVar( pGraph ) );
00533     return Dec_GraphNodeInt( pGraph, Dec_GraphVar(pGraph) );
00534 }

static Dec_Edge_t Dec_IntToEdge ( unsigned  Edge  )  [inline, static]

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

Synopsis [Converts unsigned integer into the edge.]

Description []

SideEffects []

SeeAlso []

Definition at line 169 of file dec.h.

00170 {
00171     return Dec_EdgeCreate( Edge >> 1, Edge & 1 ); 
00172 }

static Dec_Edge_t Dec_IntToEdge_ ( unsigned  Edge  )  [inline, static]

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

Synopsis [Converts unsigned integer into the edge.]

Description []

SideEffects []

SeeAlso []

Definition at line 201 of file dec.h.

00202 {
00203     return *(Dec_Edge_t *)&Edge;
00204 }

Dec_Man_t* Dec_ManStart (  ) 

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

FileName [decMan.c]

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

Synopsis [Decomposition manager.]

Author [MVSIS Group]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - February 1, 2003.]

Revision [

Id
decMan.c,v 1.1 2003/05/22 19:20:05 alanmi Exp

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

Synopsis [Start the MVC manager used in the factoring package.]

Description []

SideEffects []

SeeAlso []

Definition at line 42 of file decMan.c.

00043 {
00044     Dec_Man_t * p;
00045     int clk = clock();
00046     p = ALLOC( Dec_Man_t, 1 );
00047     p->pMvcMem = Mvc_ManagerStart();
00048     p->vCubes = Vec_IntAlloc( 8 );
00049     p->vLits = Vec_IntAlloc( 8 );
00050     // canonical forms, phases, perms
00051     Extra_Truth4VarNPN( &p->puCanons, &p->pPhases, &p->pPerms, &p->pMap );
00052 //PRT( "NPN classes precomputation time", clock() - clk ); 
00053     return p;
00054 }

void Dec_ManStop ( Dec_Man_t *  p  ) 

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

Synopsis [Stops the MVC maanager used in the factoring package.]

Description []

SideEffects []

SeeAlso []

Definition at line 67 of file decMan.c.

00068 {
00069     Mvc_ManagerFree( p->pMvcMem );
00070     Vec_IntFree( p->vCubes );
00071     Vec_IntFree( p->vLits );
00072     free( p->puCanons );
00073     free( p->pPhases );
00074     free( p->pPerms );
00075     free( p->pMap );
00076     free( p );
00077 }

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