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

Go to the source code of this file.

Data Structures

struct  Dau_Dsd_t_
 

Typedefs

typedef
typedefABC_NAMESPACE_IMPL_START
struct Dau_Dsd_t_ 
Dau_Dsd_t
 DECLARATIONS ///. More...
 

Functions

static void Dau_DsdClean (Dau_Dsd_t *p)
 
int Dau_DsdCountAnd (Dau_Dsd_t *p)
 FUNCTION DEFINITIONS ///. More...
 
int Dau_DsdConstruct (char *pDsd, Dau_Dsd_t *pStore)
 
void Dau_DsdPrint (Dau_Dsd_t *p)
 
void Dau_DsdDepth (Dau_Dsd_t *p)
 
void Dau_DsdRemoveUseless (Dau_Dsd_t *p)
 
void Dau_DsdTest22 ()
 

Typedef Documentation

typedef typedefABC_NAMESPACE_IMPL_START struct Dau_Dsd_t_ Dau_Dsd_t

DECLARATIONS ///.

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

FileName [dauArray.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [DAG-aware unmapping.]

Synopsis [Array representation of DSD.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

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

Revision [

Id:
dauArray.c,v 1.00 2005/06/20 00:00:00 alanmi Exp

]

Definition at line 29 of file dauArray.c.

Function Documentation

static void Dau_DsdClean ( Dau_Dsd_t p)
inlinestatic

Definition at line 42 of file dauArray.c.

42 { *((int *)p) = 0; }
static Llb_Mgr_t * p
Definition: llb3Image.c:950
int Dau_DsdConstruct ( char *  pDsd,
Dau_Dsd_t pStore 
)

Definition at line 76 of file dauArray.c.

77 {
78  Dau_Dsd_t * pLevel[DAU_MAX_VAR];
79  Dau_Dsd_t * q = pStore;
80  int d = -1, fCompl = 0;
81  if ( Dau_DsdIsConst(pDsd) )
82  {
83  Dau_DsdClean( q );
84  q->Type = DAU_DSD_CONST0;
85  q->fCompl = Dau_DsdIsConst1(pDsd);
86  return 1;
87  }
88  for ( --q; *pDsd; pDsd++ )
89  {
90  if ( *pDsd == '!' )
91  {
92  fCompl ^= 1;
93  continue;
94  }
95  if ( *pDsd == ')' || *pDsd == ']' || *pDsd == '>' || *pDsd == '}' )
96  {
97  assert( fCompl == 0 );
98  if ( --d >= 0 )
99  {
100  pLevel[d]->nFans++;
101  if ( pLevel[d]->Data > pLevel[d+1]->Data )
102  pLevel[d]->Data = pLevel[d+1]->Data;
103  }
104  continue;
105  }
106  Dau_DsdClean( ++q );
107  q->Data = 31;
108  q->fCompl = fCompl;
109  fCompl = 0;
110  if ( *pDsd >= 'a' && *pDsd <= 'z' )
111  {
112  q->Type = DAU_DSD_VAR;
113  q->iVar = *pDsd - 'a';
114  q->Depth = d + 1;
115  if ( d >= 0 )
116  {
117  pLevel[d]->nFans++;
118  if ( pLevel[d]->Data > q->iVar )
119  pLevel[d]->Data = q->iVar;
120  }
121  continue;
122  }
123  if ( *pDsd == '(' )
124  q->Type = DAU_DSD_AND;
125  else if ( *pDsd == '[' )
126  q->Type = DAU_DSD_XOR;
127  else if ( *pDsd == '<' )
128  q->Type = DAU_DSD_MUX;
129  else if ( *pDsd == '{' )
130  q->Type = DAU_DSD_PRIME;
131  else assert( 0 );
132  pLevel[++d] = q;
133  q->Depth = d;
134  }
135  assert( d == -1 );
136  Dau_DsdClean( ++q );
137  return q - pStore;
138 }
typedefABC_NAMESPACE_IMPL_START struct Dau_Dsd_t_ Dau_Dsd_t
DECLARATIONS ///.
Definition: dauArray.c:29
static int Dau_DsdIsConst(char *p)
MACRO DEFINITIONS ///.
Definition: dau.h:67
static void Dau_DsdClean(Dau_Dsd_t *p)
Definition: dauArray.c:42
#define DAU_MAX_VAR
INCLUDES ///.
Definition: dau.h:42
static int Dau_DsdIsConst1(char *p)
Definition: dau.h:69
#define assert(ex)
Definition: util_old.h:213
int Dau_DsdCountAnd ( Dau_Dsd_t p)

FUNCTION DEFINITIONS ///.

Definition at line 48 of file dauArray.c.

49 {
50  int Count, Costs[7] = {0, 0, 0, 1, 3, 3, 3};
51  for ( Count = 0; p->Type; p++ )
52  Count += Costs[p->Type];
53  return Count;
54 }
static Llb_Mgr_t * p
Definition: llb3Image.c:950
void Dau_DsdDepth ( Dau_Dsd_t p)

Definition at line 175 of file dauArray.c.

176 {
177  int d, pVisits[DAU_MAX_VAR];
178  if ( p->Type == DAU_DSD_CONST0 )
179  return;
180  pVisits[0] = 1;
181  for ( d = 0; p->Type; p++ )
182  {
183  p->Depth = d;
184  if ( p->Type == DAU_DSD_VAR )
185  while ( d > 0 && --pVisits[d] == 0 )
186  d--;
187  else
188  pVisits[++d] = p->nFans;
189  }
190  assert( d == 0 );
191 }
static Llb_Mgr_t * p
Definition: llb3Image.c:950
#define DAU_MAX_VAR
INCLUDES ///.
Definition: dau.h:42
#define assert(ex)
Definition: util_old.h:213
void Dau_DsdPrint ( Dau_Dsd_t p)

Definition at line 140 of file dauArray.c.

141 {
142  char OpenType[7] = {0, 0, 0, '(', '[', '<', '{'};
143  char CloseType[7] = {0, 0, 0, ')', ']', '>', '}'};
144  char pTypes[DAU_MAX_VAR];
145  int d, pVisits[DAU_MAX_VAR];
146  if ( p->Type == DAU_DSD_CONST0 )
147  {
148  printf( "%d\n", p->fCompl );
149  return;
150  }
151  pVisits[0] = 1;
152  for ( d = 0; p->Type; p++ )
153  {
154  if ( p->fCompl )
155  printf( "!" );
156  if ( p->Type == DAU_DSD_VAR )
157  {
158  printf( "%c", 'a' + p->iVar );
159  while ( d > 0 && --pVisits[d] == 0 )
160  printf( "%c", pTypes[d--] );
161  }
162  else
163  {
164  pVisits[++d] = p->nFans;
165  printf( "%c", OpenType[p->Type] );
166  printf( "%c", 'a' + p->Data );
167  printf( "%d", p->Depth );
168  pTypes[d] = CloseType[p->Type];
169  }
170  }
171  assert( d == 0 );
172  printf( "\n" );
173 }
static Llb_Mgr_t * p
Definition: llb3Image.c:950
#define DAU_MAX_VAR
INCLUDES ///.
Definition: dau.h:42
#define assert(ex)
Definition: util_old.h:213
void Dau_DsdRemoveUseless ( Dau_Dsd_t p)

Definition at line 193 of file dauArray.c.

194 {
195  Dau_Dsd_t * q = p, * pLevel[DAU_MAX_VAR];
196  int d, fChange = 0, pVisits[DAU_MAX_VAR];
197  if ( p->Type == DAU_DSD_CONST0 )
198  return;
199  pVisits[0] = 1;
200  for ( d = 0; p->Type; p++ )
201  {
202  p->Depth = d;
203  if ( p->Type == DAU_DSD_VAR )
204  while ( d > 0 && --pVisits[d] == 0 )
205  d--;
206  else
207  {
208  if ( d > 0 && (pLevel[d-1]->Type == DAU_DSD_XOR && p->Type == DAU_DSD_XOR ||
209  pLevel[d-1]->Type == DAU_DSD_AND && p->Type == DAU_DSD_AND && !p->fCompl) )
210  {
211  pLevel[d-1]->nFans += p->nFans - 1;
212  pVisits[d] += p->nFans - 1;
213  p->fUnused = 1;
214  fChange = 1;
215  }
216  else
217  {
218  pLevel[d++] = p;
219  pVisits[d] = p->nFans;
220  }
221  }
222  }
223  assert( d == 0 );
224  // compact
225  if ( fChange )
226  {
227  for ( p = q; p->Type; p++ )
228  if ( !p->fUnused )
229  *q++ = *p;
230  Dau_DsdClean( q );
231  }
232 }
typedefABC_NAMESPACE_IMPL_START struct Dau_Dsd_t_ Dau_Dsd_t
DECLARATIONS ///.
Definition: dauArray.c:29
static Llb_Mgr_t * p
Definition: llb3Image.c:950
static void Dau_DsdClean(Dau_Dsd_t *p)
Definition: dauArray.c:42
#define DAU_MAX_VAR
INCLUDES ///.
Definition: dau.h:42
#define assert(ex)
Definition: util_old.h:213
void Dau_DsdTest22 ( )

Definition at line 234 of file dauArray.c.

235 {
236  Dau_Dsd_t pStore[2 * DAU_MAX_VAR];
237 // char * pDsd = "[(ab)c(f!(he))]";
238 // char * pDsd = "[(abd)cf(f!{she})]";
239  char * pDsd = "[(abd)[cf](f(sg(he)))]";
240 // char * pDsd = "[(ab)[cf]]";
241  int i, nSize = Dau_DsdConstruct( pDsd, pStore );
242 // Dau_DsdDepth( pStore );
243  Dau_DsdPrint( pStore );
244 
245  Dau_DsdRemoveUseless( pStore );
246 
247  Dau_DsdPrint( pStore );
248  i = 0;
249 }
typedefABC_NAMESPACE_IMPL_START struct Dau_Dsd_t_ Dau_Dsd_t
DECLARATIONS ///.
Definition: dauArray.c:29
void Dau_DsdPrint(Dau_Dsd_t *p)
Definition: dauArray.c:140
void Dau_DsdRemoveUseless(Dau_Dsd_t *p)
Definition: dauArray.c:193
#define DAU_MAX_VAR
INCLUDES ///.
Definition: dau.h:42
int Dau_DsdConstruct(char *pDsd, Dau_Dsd_t *pStore)
Definition: dauArray.c:76