abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
decUtil.c
Go to the documentation of this file.
1 /**CFile****************************************************************
2 
3  FileName [decUtil.c]
4 
5  PackageName [MVSIS 2.0: Multi-valued logic synthesis system.]
6 
7  Synopsis [Decomposition unitilies.]
8 
9  Author [MVSIS Group]
10 
11  Affiliation [UC Berkeley]
12 
13  Date [Ver. 1.0. Started - February 1, 2003.]
14 
15  Revision [$Id: decUtil.c,v 1.1 2003/05/22 19:20:05 alanmi Exp $]
16 
17 ***********************************************************************/
18 
19 #include "base/abc/abc.h"
20 #include "misc/extra/extraBdd.h"
21 #include "dec.h"
22 
24 
25 
26 ////////////////////////////////////////////////////////////////////////
27 /// DECLARATIONS ///
28 ////////////////////////////////////////////////////////////////////////
29 
30 ////////////////////////////////////////////////////////////////////////
31 /// FUNCTION DEFINITIONS ///
32 ////////////////////////////////////////////////////////////////////////
33 
34 /**Function*************************************************************
35 
36  Synopsis [Converts graph to BDD.]
37 
38  Description []
39 
40  SideEffects []
41 
42  SeeAlso []
43 
44 ***********************************************************************/
46 {
47  DdNode * bFunc, * bFunc0, * bFunc1;
48  Dec_Node_t * pNode = NULL; // Suppress "might be used uninitialized"
49  int i;
50 
51  // sanity checks
52  assert( Dec_GraphLeaveNum(pGraph) >= 0 );
53  assert( Dec_GraphLeaveNum(pGraph) <= pGraph->nSize );
54 
55  // check for constant function
56  if ( Dec_GraphIsConst(pGraph) )
57  return Cudd_NotCond( b1, Dec_GraphIsComplement(pGraph) );
58  // check for a literal
59  if ( Dec_GraphIsVar(pGraph) )
60  return Cudd_NotCond( Cudd_bddIthVar(dd, Dec_GraphVarInt(pGraph)), Dec_GraphIsComplement(pGraph) );
61 
62  // assign the elementary variables
63  Dec_GraphForEachLeaf( pGraph, pNode, i )
64  pNode->pFunc = Cudd_bddIthVar( dd, i );
65 
66  // compute the function for each internal node
67  Dec_GraphForEachNode( pGraph, pNode, i )
68  {
69  bFunc0 = Cudd_NotCond( Dec_GraphNode(pGraph, pNode->eEdge0.Node)->pFunc, pNode->eEdge0.fCompl );
70  bFunc1 = Cudd_NotCond( Dec_GraphNode(pGraph, pNode->eEdge1.Node)->pFunc, pNode->eEdge1.fCompl );
71  pNode->pFunc = Cudd_bddAnd( dd, bFunc0, bFunc1 ); Cudd_Ref( (DdNode *)pNode->pFunc );
72  }
73 
74  // deref the intermediate results
75  bFunc = (DdNode *)pNode->pFunc; Cudd_Ref( bFunc );
76  Dec_GraphForEachNode( pGraph, pNode, i )
77  Cudd_RecursiveDeref( dd, (DdNode *)pNode->pFunc );
78  Cudd_Deref( bFunc );
79 
80  // complement the result if necessary
81  return Cudd_NotCond( bFunc, Dec_GraphIsComplement(pGraph) );
82 }
83 
84 /**Function*************************************************************
85 
86  Synopsis [Derives the truth table.]
87 
88  Description []
89 
90  SideEffects []
91 
92  SeeAlso []
93 
94 ***********************************************************************/
95 unsigned Dec_GraphDeriveTruth( Dec_Graph_t * pGraph )
96 {
97  unsigned uTruths[5] = { 0xAAAAAAAA, 0xCCCCCCCC, 0xF0F0F0F0, 0xFF00FF00, 0xFFFF0000 };
98  unsigned uTruth = 0; // Suppress "might be used uninitialized"
99  unsigned uTruth0, uTruth1;
100  Dec_Node_t * pNode;
101  int i;
102 
103  // sanity checks
104  assert( Dec_GraphLeaveNum(pGraph) >= 0 );
105  assert( Dec_GraphLeaveNum(pGraph) <= pGraph->nSize );
106  assert( Dec_GraphLeaveNum(pGraph) <= 5 );
107 
108  // check for constant function
109  if ( Dec_GraphIsConst(pGraph) )
110  return Dec_GraphIsComplement(pGraph)? 0 : ~((unsigned)0);
111  // check for a literal
112  if ( Dec_GraphIsVar(pGraph) )
113  return Dec_GraphIsComplement(pGraph)? ~uTruths[Dec_GraphVarInt(pGraph)] : uTruths[Dec_GraphVarInt(pGraph)];
114 
115  // assign the elementary variables
116  Dec_GraphForEachLeaf( pGraph, pNode, i )
117  pNode->pFunc = (void *)(ABC_PTRUINT_T)uTruths[i];
118 
119  // compute the function for each internal node
120  Dec_GraphForEachNode( pGraph, pNode, i )
121  {
122  uTruth0 = (unsigned)(ABC_PTRUINT_T)Dec_GraphNode(pGraph, pNode->eEdge0.Node)->pFunc;
123  uTruth1 = (unsigned)(ABC_PTRUINT_T)Dec_GraphNode(pGraph, pNode->eEdge1.Node)->pFunc;
124  uTruth0 = pNode->eEdge0.fCompl? ~uTruth0 : uTruth0;
125  uTruth1 = pNode->eEdge1.fCompl? ~uTruth1 : uTruth1;
126  uTruth = uTruth0 & uTruth1;
127  pNode->pFunc = (void *)(ABC_PTRUINT_T)uTruth;
128  }
129 
130  // complement the result if necessary
131  return Dec_GraphIsComplement(pGraph)? ~uTruth : uTruth;
132 }
133 
134 
135 ////////////////////////////////////////////////////////////////////////
136 /// END OF FILE ///
137 ////////////////////////////////////////////////////////////////////////
138 
139 
141 
static int Dec_GraphVarInt(Dec_Graph_t *pGraph)
Definition: dec.h:534
void Cudd_RecursiveDeref(DdManager *table, DdNode *n)
Definition: cuddRef.c:154
unsigned Dec_GraphDeriveTruth(Dec_Graph_t *pGraph)
Definition: decUtil.c:95
Definition: cudd.h:278
void Cudd_Deref(DdNode *node)
Definition: cuddRef.c:438
#define b1
Definition: extraBdd.h:76
static int Dec_GraphIsConst(Dec_Graph_t *pGraph)
Definition: dec.h:324
int nSize
Definition: dec.h:73
static int Dec_GraphIsComplement(Dec_Graph_t *pGraph)
Definition: dec.h:372
#define ABC_NAMESPACE_IMPL_END
Definition: abc_global.h:108
Dec_Edge_t eEdge0
Definition: dec.h:52
#define ABC_NAMESPACE_IMPL_START
Definition: abc_global.h:107
#define Dec_GraphForEachNode(pGraph, pAnd, i)
Definition: dec.h:101
void * pFunc
Definition: dec.h:56
#define Dec_GraphForEachLeaf(pGraph, pLeaf, i)
ITERATORS ///.
Definition: dec.h:98
DdNode * Cudd_bddIthVar(DdManager *dd, int i)
Definition: cuddAPI.c:416
static int Dec_GraphLeaveNum(Dec_Graph_t *pGraph)
Definition: dec.h:405
#define Cudd_NotCond(node, c)
Definition: cudd.h:383
DdNode * Cudd_bddAnd(DdManager *dd, DdNode *f, DdNode *g)
Definition: cuddBddIte.c:314
static int Dec_GraphIsVar(Dec_Graph_t *pGraph)
Definition: dec.h:485
#define assert(ex)
Definition: util_old.h:213
static Dec_Node_t * Dec_GraphNode(Dec_Graph_t *pGraph, int i)
Definition: dec.h:437
void Cudd_Ref(DdNode *n)
Definition: cuddRef.c:129
Dec_Edge_t eEdge1
Definition: dec.h:53
ABC_NAMESPACE_IMPL_START DdNode * Dec_GraphDeriveBdd(DdManager *dd, Dec_Graph_t *pGraph)
DECLARATIONS ///.
Definition: decUtil.c:45