abc-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Functions
kitGraph.c File Reference
#include "kit.h"

Go to the source code of this file.

Functions

ABC_NAMESPACE_IMPL_START
Kit_Graph_t * 		Kit_GraphCreate (int nLeaves)
 DECLARATIONS ///. More...
 
Kit_Graph_t * Kit_GraphCreateConst0 ()
 
Kit_Graph_t * Kit_GraphCreateConst1 ()
 
Kit_Graph_t * Kit_GraphCreateLeaf (int iLeaf, int nLeaves, int fCompl)
 
void Kit_GraphFree (Kit_Graph_t *pGraph)
 
Kit_Node_t * Kit_GraphAppendNode (Kit_Graph_t *pGraph)
 
Kit_Edge_t Kit_GraphAddNodeAnd (Kit_Graph_t *pGraph, Kit_Edge_t eEdge0, Kit_Edge_t eEdge1)
 
Kit_Edge_t Kit_GraphAddNodeOr (Kit_Graph_t *pGraph, Kit_Edge_t eEdge0, Kit_Edge_t eEdge1)
 
Kit_Edge_t Kit_GraphAddNodeXor (Kit_Graph_t *pGraph, Kit_Edge_t eEdge0, Kit_Edge_t eEdge1, int Type)
 
Kit_Edge_t Kit_GraphAddNodeMux (Kit_Graph_t *pGraph, Kit_Edge_t eEdgeC, Kit_Edge_t eEdgeT, Kit_Edge_t eEdgeE, int Type)
 
unsigned Kit_GraphToTruth (Kit_Graph_t *pGraph)
 
Kit_Graph_t * Kit_TruthToGraph (unsigned *pTruth, int nVars, Vec_Int_t *vMemory)
 
int Kit_GraphLeafDepth_rec (Kit_Graph_t *pGraph, Kit_Node_t *pNode, Kit_Node_t *pLeaf)
 

Function Documentation

Kit_Edge_t Kit_GraphAddNodeAnd ( Kit_Graph_t *  pGraph,
Kit_Edge_t  eEdge0,
Kit_Edge_t  eEdge1 
)

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

Synopsis [Creates an AND node.]

Description []

SideEffects []

SeeAlso []

Definition at line 172 of file kitGraph.c.

173 {
174  Kit_Node_t * pNode;
175  // get the new node
176  pNode = Kit_GraphAppendNode( pGraph );
177  // set the inputs and other info
178  pNode->eEdge0 = eEdge0;
179  pNode->eEdge1 = eEdge1;
180  pNode->fCompl0 = eEdge0.fCompl;
181  pNode->fCompl1 = eEdge1.fCompl;
182  return Kit_EdgeCreate( pGraph->nSize - 1, 0 );
183 }
Kit_Node_t_::fCompl1
unsigned fCompl1
Definition: kit.h:78
Kit_Node_t_::eEdge0
Kit_Edge_t eEdge0
Definition: kit.h:69
Kit_Node_t_::fCompl0
unsigned fCompl0
Definition: kit.h:77
Kit_Node_t_::eEdge1
Kit_Edge_t eEdge1
Definition: kit.h:70
Kit_Graph_t_::nSize
int nSize
Definition: kit.h:90
Kit_Node_t_
Definition: kit.h:67
Kit_EdgeCreate
static Kit_Edge_t Kit_EdgeCreate(int Node, int fCompl)
Definition: kit.h:194
Kit_Edge_t_::fCompl
unsigned fCompl
Definition: kit.h:62
Kit_GraphAppendNode
Kit_Node_t * Kit_GraphAppendNode(Kit_Graph_t *pGraph)
Definition: kitGraph.c:148
Kit_Edge_t Kit_GraphAddNodeMux ( Kit_Graph_t *  pGraph,
Kit_Edge_t  eEdgeC,
Kit_Edge_t  eEdgeT,
Kit_Edge_t  eEdgeE,
int  Type 
)

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

Synopsis [Creates an XOR node.]

Description []

SideEffects []

SeeAlso []

Definition at line 265 of file kitGraph.c.

266 {
267  Kit_Edge_t eNode0, eNode1, eNode;
268  if ( Type == 0 )
269  {
270  // derive the first AND
271  eNode0 = Kit_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeT );
272  // derive the second AND
273  eEdgeC.fCompl ^= 1;
274  eNode1 = Kit_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeE );
275  // derive the final OR
276  eNode = Kit_GraphAddNodeOr( pGraph, eNode0, eNode1 );
277  }
278  else
279  {
280  // complement the arguments
281  eEdgeT.fCompl ^= 1;
282  eEdgeE.fCompl ^= 1;
283  // derive the first AND
284  eNode0 = Kit_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeT );
285  // derive the second AND
286  eEdgeC.fCompl ^= 1;
287  eNode1 = Kit_GraphAddNodeAnd( pGraph, eEdgeC, eEdgeE );
288  // derive the final OR
289  eNode = Kit_GraphAddNodeOr( pGraph, eNode0, eNode1 );
290  eNode.fCompl ^= 1;
291  }
292  return eNode;
293 }
Kit_GraphAddNodeOr
Kit_Edge_t Kit_GraphAddNodeOr(Kit_Graph_t *pGraph, Kit_Edge_t eEdge0, Kit_Edge_t eEdge1)
Definition: kitGraph.c:196
Kit_Edge_t_::fCompl
unsigned fCompl
Definition: kit.h:62
Kit_GraphAddNodeAnd
Kit_Edge_t Kit_GraphAddNodeAnd(Kit_Graph_t *pGraph, Kit_Edge_t eEdge0, Kit_Edge_t eEdge1)
Definition: kitGraph.c:172
Kit_Edge_t_
Definition: kit.h:60
Kit_Edge_t Kit_GraphAddNodeOr ( Kit_Graph_t *  pGraph,
Kit_Edge_t  eEdge0,
Kit_Edge_t  eEdge1 
)

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

Synopsis [Creates an OR node.]

Description []

SideEffects []

SeeAlso []

Definition at line 196 of file kitGraph.c.

197 {
198  Kit_Node_t * pNode;
199  // get the new node
200  pNode = Kit_GraphAppendNode( pGraph );
201  // set the inputs and other info
202  pNode->eEdge0 = eEdge0;
203  pNode->eEdge1 = eEdge1;
204  pNode->fCompl0 = eEdge0.fCompl;
205  pNode->fCompl1 = eEdge1.fCompl;
206  // make adjustments for the OR gate
207  pNode->fNodeOr = 1;
208  pNode->eEdge0.fCompl = !pNode->eEdge0.fCompl;
209  pNode->eEdge1.fCompl = !pNode->eEdge1.fCompl;
210  return Kit_EdgeCreate( pGraph->nSize - 1, 1 );
211 }
Kit_Node_t_::fCompl1
unsigned fCompl1
Definition: kit.h:78
Kit_Node_t_::eEdge0
Kit_Edge_t eEdge0
Definition: kit.h:69
Kit_Node_t_::fNodeOr
unsigned fNodeOr
Definition: kit.h:76
Kit_Node_t_::fCompl0
unsigned fCompl0
Definition: kit.h:77
Kit_Node_t_::eEdge1
Kit_Edge_t eEdge1
Definition: kit.h:70
Kit_Graph_t_::nSize
int nSize
Definition: kit.h:90
Kit_Node_t_
Definition: kit.h:67
Kit_EdgeCreate
static Kit_Edge_t Kit_EdgeCreate(int Node, int fCompl)
Definition: kit.h:194
Kit_Edge_t_::fCompl
unsigned fCompl
Definition: kit.h:62
Kit_GraphAppendNode
Kit_Node_t * Kit_GraphAppendNode(Kit_Graph_t *pGraph)
Definition: kitGraph.c:148
Kit_Edge_t Kit_GraphAddNodeXor ( Kit_Graph_t *  pGraph,
Kit_Edge_t  eEdge0,
Kit_Edge_t  eEdge1,
int  Type 
)

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

Synopsis [Creates an XOR node.]

Description []

SideEffects []

SeeAlso []

Definition at line 224 of file kitGraph.c.

225 {
226  Kit_Edge_t eNode0, eNode1, eNode;
227  if ( Type == 0 )
228  {
229  // derive the first AND
230  eEdge0.fCompl ^= 1;
231  eNode0 = Kit_GraphAddNodeAnd( pGraph, eEdge0, eEdge1 );
232  eEdge0.fCompl ^= 1;
233  // derive the second AND
234  eEdge1.fCompl ^= 1;
235  eNode1 = Kit_GraphAddNodeAnd( pGraph, eEdge0, eEdge1 );
236  // derive the final OR
237  eNode = Kit_GraphAddNodeOr( pGraph, eNode0, eNode1 );
238  }
239  else
240  {
241  // derive the first AND
242  eNode0 = Kit_GraphAddNodeAnd( pGraph, eEdge0, eEdge1 );
243  // derive the second AND
244  eEdge0.fCompl ^= 1;
245  eEdge1.fCompl ^= 1;
246  eNode1 = Kit_GraphAddNodeAnd( pGraph, eEdge0, eEdge1 );
247  // derive the final OR
248  eNode = Kit_GraphAddNodeOr( pGraph, eNode0, eNode1 );
249  eNode.fCompl ^= 1;
250  }
251  return eNode;
252 }
Kit_GraphAddNodeOr
Kit_Edge_t Kit_GraphAddNodeOr(Kit_Graph_t *pGraph, Kit_Edge_t eEdge0, Kit_Edge_t eEdge1)
Definition: kitGraph.c:196
Kit_Edge_t_::fCompl
unsigned fCompl
Definition: kit.h:62
Kit_GraphAddNodeAnd
Kit_Edge_t Kit_GraphAddNodeAnd(Kit_Graph_t *pGraph, Kit_Edge_t eEdge0, Kit_Edge_t eEdge1)
Definition: kitGraph.c:172
Kit_Edge_t_
Definition: kit.h:60
Kit_Node_t* Kit_GraphAppendNode ( Kit_Graph_t *  pGraph)

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

Synopsis [Appends a new node to the graph.]

Description [This procedure is meant for internal use.]

SideEffects []

SeeAlso []

Definition at line 148 of file kitGraph.c.

149 {
150  Kit_Node_t * pNode;
151  if ( pGraph->nSize == pGraph->nCap )
152  {
153  pGraph->pNodes = ABC_REALLOC( Kit_Node_t, pGraph->pNodes, 2 * pGraph->nCap );
154  pGraph->nCap = 2 * pGraph->nCap;
155  }
156  pNode = pGraph->pNodes + pGraph->nSize++;
157  memset( pNode, 0, sizeof(Kit_Node_t) );
158  return pNode;
159 }
memset
char * memset()
Kit_Graph_t_::nCap
int nCap
Definition: kit.h:91
ABC_REALLOC
#define ABC_REALLOC(type, obj, num)
Definition: abc_global.h:233
Kit_Graph_t_::nSize
int nSize
Definition: kit.h:90
Kit_Node_t_
Definition: kit.h:67
Kit_Graph_t_::pNodes
Kit_Node_t * pNodes
Definition: kit.h:92
ABC_NAMESPACE_IMPL_START Kit_Graph_t* Kit_GraphCreate ( int  nLeaves)

DECLARATIONS ///.

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

FileName [kitGraph.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [Computation kit.]

Synopsis [Decomposition graph representation.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - Dec 6, 2006.]

Revision [

Id:
kitGraph.c,v 1.00 2006/12/06 00:00:00 alanmi Exp

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 45 of file kitGraph.c.

46 {
47  Kit_Graph_t * pGraph;
48  pGraph = ABC_ALLOC( Kit_Graph_t, 1 );
49  memset( pGraph, 0, sizeof(Kit_Graph_t) );
50  pGraph->nLeaves = nLeaves;
51  pGraph->nSize = nLeaves;
52  pGraph->nCap = 2 * nLeaves + 50;
53  pGraph->pNodes = ABC_ALLOC( Kit_Node_t, pGraph->nCap );
54  memset( pGraph->pNodes, 0, sizeof(Kit_Node_t) * pGraph->nSize );
55  return pGraph;
56 }
memset
char * memset()
Kit_Graph_t_::nCap
int nCap
Definition: kit.h:91
Kit_Graph_t_
Definition: kit.h:86
Kit_Graph_t_::nSize
int nSize
Definition: kit.h:90
Kit_Node_t_
Definition: kit.h:67
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Kit_Graph_t_::pNodes
Kit_Node_t * pNodes
Definition: kit.h:92
Kit_Graph_t_::nLeaves
int nLeaves
Definition: kit.h:89
Kit_Graph_t* Kit_GraphCreateConst0 ( )

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

Synopsis [Creates constant 0 graph.]

Description []

SideEffects []

SeeAlso []

Definition at line 69 of file kitGraph.c.

70 {
71  Kit_Graph_t * pGraph;
72  pGraph = ABC_ALLOC( Kit_Graph_t, 1 );
73  memset( pGraph, 0, sizeof(Kit_Graph_t) );
74  pGraph->fConst = 1;
75  pGraph->eRoot.fCompl = 1;
76  return pGraph;
77 }
memset
char * memset()
Kit_Graph_t_::eRoot
Kit_Edge_t eRoot
Definition: kit.h:93
Kit_Graph_t_
Definition: kit.h:86
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Kit_Edge_t_::fCompl
unsigned fCompl
Definition: kit.h:62
Kit_Graph_t_::fConst
int fConst
Definition: kit.h:88
Kit_Graph_t* Kit_GraphCreateConst1 ( )

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

Synopsis [Creates constant 1 graph.]

Description []

SideEffects []

SeeAlso []

Definition at line 90 of file kitGraph.c.

91 {
92  Kit_Graph_t * pGraph;
93  pGraph = ABC_ALLOC( Kit_Graph_t, 1 );
94  memset( pGraph, 0, sizeof(Kit_Graph_t) );
95  pGraph->fConst = 1;
96  return pGraph;
97 }
memset
char * memset()
Kit_Graph_t_
Definition: kit.h:86
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition: abc_global.h:229
Kit_Graph_t_::fConst
int fConst
Definition: kit.h:88
Kit_Graph_t* Kit_GraphCreateLeaf ( int  iLeaf,
int  nLeaves,
int  fCompl 
)

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

Synopsis [Creates the literal graph.]

Description []

SideEffects []

SeeAlso []

Definition at line 110 of file kitGraph.c.

111 {
112  Kit_Graph_t * pGraph;
113  assert( 0 <= iLeaf && iLeaf < nLeaves );
114  pGraph = Kit_GraphCreate( nLeaves );
115  pGraph->eRoot.Node = iLeaf;
116  pGraph->eRoot.fCompl = fCompl;
117  return pGraph;
118 }
Kit_Graph_t_::eRoot
Kit_Edge_t eRoot
Definition: kit.h:93
Kit_Graph_t_
Definition: kit.h:86
Kit_Edge_t_::fCompl
unsigned fCompl
Definition: kit.h:62
Kit_Edge_t_::Node
unsigned Node
Definition: kit.h:63
assert
#define assert(ex)
Definition: util_old.h:213
Kit_GraphCreate
ABC_NAMESPACE_IMPL_START Kit_Graph_t * Kit_GraphCreate(int nLeaves)
DECLARATIONS ///.
Definition: kitGraph.c:45
void Kit_GraphFree ( Kit_Graph_t *  pGraph)

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

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

Description []

SideEffects []

SeeAlso []

Definition at line 131 of file kitGraph.c.

132 {
133  ABC_FREE( pGraph->pNodes );
134  ABC_FREE( pGraph );
135 }
Kit_Graph_t_::pNodes
Kit_Node_t * pNodes
Definition: kit.h:92
ABC_FREE
#define ABC_FREE(obj)
Definition: abc_global.h:232
int Kit_GraphLeafDepth_rec ( Kit_Graph_t *  pGraph,
Kit_Node_t *  pNode,
Kit_Node_t *  pLeaf 
)

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

Synopsis [Derives the maximum depth from the leaf to the root.]

Description []

SideEffects []

SeeAlso []

Definition at line 383 of file kitGraph.c.

384 {
385  int Depth0, Depth1, Depth;
386  if ( pNode == pLeaf )
387  return 0;
388  if ( Kit_GraphNodeIsVar(pGraph, pNode) )
389  return -100;
390  Depth0 = Kit_GraphLeafDepth_rec( pGraph, Kit_GraphNodeFanin0(pGraph, pNode), pLeaf );
391  Depth1 = Kit_GraphLeafDepth_rec( pGraph, Kit_GraphNodeFanin1(pGraph, pNode), pLeaf );
392  Depth = KIT_MAX( Depth0, Depth1 );
393  Depth = (Depth == -100) ? -100 : Depth + 1;
394  return Depth;
395 }
KIT_MAX
#define KIT_MAX(a, b)
Definition: kit.h:172
Kit_GraphLeafDepth_rec
int Kit_GraphLeafDepth_rec(Kit_Graph_t *pGraph, Kit_Node_t *pNode, Kit_Node_t *pLeaf)
Definition: kitGraph.c:383
Kit_GraphNodeFanin0
static Kit_Node_t * Kit_GraphNodeFanin0(Kit_Graph_t *pGraph, Kit_Node_t *pNode)
Definition: kit.h:217
Kit_GraphNodeIsVar
static int Kit_GraphNodeIsVar(Kit_Graph_t *pGraph, Kit_Node_t *pNode)
Definition: kit.h:214
Kit_GraphNodeFanin1
static Kit_Node_t * Kit_GraphNodeFanin1(Kit_Graph_t *pGraph, Kit_Node_t *pNode)
Definition: kit.h:218
Depth
static int Depth
Definition: dsdProc.c:56
unsigned Kit_GraphToTruth ( Kit_Graph_t *  pGraph)

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

Synopsis [Derives the truth table.]

Description []

SideEffects []

SeeAlso []

Definition at line 306 of file kitGraph.c.

307 {
308  unsigned uTruths[5] = { 0xAAAAAAAA, 0xCCCCCCCC, 0xF0F0F0F0, 0xFF00FF00, 0xFFFF0000 };
309  unsigned uTruth = 0, uTruth0, uTruth1;
310  Kit_Node_t * pNode;
311  int i;
312 
313  // sanity checks
314  assert( Kit_GraphLeaveNum(pGraph) >= 0 );
315  assert( Kit_GraphLeaveNum(pGraph) <= pGraph->nSize );
316  assert( Kit_GraphLeaveNum(pGraph) <= 5 );
317 
318  // check for constant function
319  if ( Kit_GraphIsConst(pGraph) )
320  return Kit_GraphIsComplement(pGraph)? 0 : ~((unsigned)0);
321  // check for a literal
322  if ( Kit_GraphIsVar(pGraph) )
323  return Kit_GraphIsComplement(pGraph)? ~uTruths[Kit_GraphVarInt(pGraph)] : uTruths[Kit_GraphVarInt(pGraph)];
324 
325  // assign the elementary variables
326  Kit_GraphForEachLeaf( pGraph, pNode, i )
327  pNode->pFunc = (void *)(long)uTruths[i];
328 
329  // compute the function for each internal node
330  Kit_GraphForEachNode( pGraph, pNode, i )
331  {
332  uTruth0 = (unsigned)(long)Kit_GraphNode(pGraph, pNode->eEdge0.Node)->pFunc;
333  uTruth1 = (unsigned)(long)Kit_GraphNode(pGraph, pNode->eEdge1.Node)->pFunc;
334  uTruth0 = pNode->eEdge0.fCompl? ~uTruth0 : uTruth0;
335  uTruth1 = pNode->eEdge1.fCompl? ~uTruth1 : uTruth1;
336  uTruth = uTruth0 & uTruth1;
337  pNode->pFunc = (void *)(long)uTruth;
338  }
339 
340  // complement the result if necessary
341  return Kit_GraphIsComplement(pGraph)? ~uTruth : uTruth;
342 }
Kit_GraphNode
static Kit_Node_t * Kit_GraphNode(Kit_Graph_t *pGraph, int i)
Definition: kit.h:211
Kit_GraphIsComplement
static int Kit_GraphIsComplement(Kit_Graph_t *pGraph)
Definition: kit.h:205
Kit_GraphLeaveNum
static int Kit_GraphLeaveNum(Kit_Graph_t *pGraph)
Definition: kit.h:209
Kit_Graph_t_::nSize
int nSize
Definition: kit.h:90
Kit_Node_t_
Definition: kit.h:67
Kit_GraphIsVar
static int Kit_GraphIsVar(Kit_Graph_t *pGraph)
Definition: kit.h:206
Kit_GraphForEachLeaf
#define Kit_GraphForEachLeaf(pGraph, pLeaf, i)
Definition: kit.h:502
Kit_Node_t_::pFunc
void * pFunc
Definition: kit.h:73
Kit_GraphIsConst
static int Kit_GraphIsConst(Kit_Graph_t *pGraph)
Definition: kit.h:202
Kit_GraphForEachNode
#define Kit_GraphForEachNode(pGraph, pAnd, i)
Definition: kit.h:504
assert
#define assert(ex)
Definition: util_old.h:213
Kit_GraphVarInt
static int Kit_GraphVarInt(Kit_Graph_t *pGraph)
Definition: kit.h:216
Kit_Graph_t* Kit_TruthToGraph ( unsigned *  pTruth,
int  nVars,
Vec_Int_t *  vMemory 
)

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

Synopsis [Derives the factored form from the truth table.]

Description []

SideEffects []

SeeAlso []

Definition at line 355 of file kitGraph.c.

356 {
357  Kit_Graph_t * pGraph;
358  int RetValue;
359  // derive SOP
360  RetValue = Kit_TruthIsop( pTruth, nVars, vMemory, 1 ); // tried 1 and found not useful in "renode"
361  if ( RetValue == -1 )
362  return NULL;
363  if ( Vec_IntSize(vMemory) > (1<<16) )
364  return NULL;
365 // printf( "Isop size = %d.\n", Vec_IntSize(vMemory) );
366  assert( RetValue == 0 || RetValue == 1 );
367  // derive factored form
368  pGraph = Kit_SopFactor( vMemory, RetValue, nVars, vMemory );
369  return pGraph;
370 }
Kit_Graph_t_
Definition: kit.h:86
Kit_TruthIsop
int Kit_TruthIsop(unsigned *puTruth, int nVars, Vec_Int_t *vMemory, int fTryBoth)
FUNCTION DEFINITIONS ///.
Definition: kitIsop.c:55
Vec_IntSize
static int Vec_IntSize(Vec_Int_t *p)
Definition: bblif.c:252
assert
#define assert(ex)
Definition: util_old.h:213
Kit_SopFactor
Kit_Graph_t * Kit_SopFactor(Vec_Int_t *vCover, int fCompl, int nVars, Vec_Int_t *vMemory)
FUNCTION DEFINITIONS ///.
Definition: kitFactor.c:55