1 /**CFile****************************************************************
2
3 FileName [giaRex.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Scalable AIG package.]
8
9 Synopsis [Regular expressions.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: giaRex.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "gia.h"
22 #include "misc/extra/extra.h"
23
24 ABC_NAMESPACE_IMPL_START
25
26
27 ////////////////////////////////////////////////////////////////////////
28 /// DECLARATIONS ///
29 ////////////////////////////////////////////////////////////////////////
30
31 ////////////////////////////////////////////////////////////////////////
32 /// FUNCTION DEFINITIONS ///
33 ////////////////////////////////////////////////////////////////////////
34
35 /**Function*************************************************************
36
37 Synopsis [Simulate AIG with the given sequence.]
38
39 Description []
40
41 SideEffects []
42
43 SeeAlso []
44
45 ***********************************************************************/
Gia_ManAutomSimulate(Gia_Man_t * p,Vec_Int_t * vAlpha,char * pSim)46 void Gia_ManAutomSimulate( Gia_Man_t * p, Vec_Int_t * vAlpha, char * pSim )
47 {
48 Gia_Obj_t * pObj, * pObjRi, * pObjRo;
49 int nInputs = Vec_IntSize(vAlpha);
50 int nFrames = strlen(pSim);
51 int i, k;
52 assert( Gia_ManPiNum(p) == nInputs );
53 printf( "Simulating string \"%s\":\n", pSim );
54 Gia_ManCleanMark0(p);
55 Gia_ManForEachRo( p, pObj, i )
56 pObj->fMark0 = 0;
57 for ( i = 0; i < nFrames; i++ )
58 {
59 Gia_ManForEachPi( p, pObj, k )
60 pObj->fMark0 = (int)(Vec_IntFind(vAlpha, pSim[i]) == k);
61 Gia_ManForEachAnd( p, pObj, k )
62 pObj->fMark0 = (Gia_ObjFanin0(pObj)->fMark0 ^ Gia_ObjFaninC0(pObj)) &
63 (Gia_ObjFanin1(pObj)->fMark0 ^ Gia_ObjFaninC1(pObj));
64 Gia_ManForEachCo( p, pObj, k )
65 pObj->fMark0 = Gia_ObjFanin0(pObj)->fMark0 ^ Gia_ObjFaninC0(pObj);
66 Gia_ManForEachRiRo( p, pObjRi, pObjRo, k )
67 pObjRo->fMark0 = pObjRi->fMark0;
68
69 printf( "Frame %d : %c %d\n", i, pSim[i], Gia_ManPo(p, 0)->fMark0 );
70 }
71 Gia_ManCleanMark0(p);
72 }
73
74 /**Function*************************************************************
75
76 Synopsis [Builds 1-hotness contraint.]
77
78 Description []
79
80 SideEffects []
81
82 SeeAlso []
83
84 ***********************************************************************/
Gia_ManBuild1Hot_rec(Gia_Man_t * p,int * pLits,int nLits,int * pZero,int * pOne)85 void Gia_ManBuild1Hot_rec( Gia_Man_t * p, int * pLits, int nLits, int * pZero, int * pOne )
86 {
87 int Zero0, One0, Zero1, One1;
88 if ( nLits == 1 )
89 {
90 *pZero = Abc_LitNot(pLits[0]);
91 *pOne = pLits[0];
92 return;
93 }
94 Gia_ManBuild1Hot_rec( p, pLits, nLits/2, &Zero0, &One0 );
95 Gia_ManBuild1Hot_rec( p, pLits + nLits/2, nLits - nLits/2, &Zero1, &One1 );
96 *pZero = Gia_ManHashAnd( p, Zero0, Zero1 );
97 *pOne = Gia_ManHashOr( p, Gia_ManHashAnd(p, Zero0, One1), Gia_ManHashAnd(p, Zero1, One0) );
98 }
Gia_ManBuild1Hot(Gia_Man_t * p,Vec_Int_t * vLits)99 int Gia_ManBuild1Hot( Gia_Man_t * p, Vec_Int_t * vLits )
100 {
101 int Zero, One;
102 assert( Vec_IntSize(vLits) > 0 );
103 Gia_ManBuild1Hot_rec( p, Vec_IntArray(vLits), Vec_IntSize(vLits), &Zero, &One );
104 return One;
105 }
106
107 /**Function*************************************************************
108
109 Synopsis [Converting regular expressions into sequential AIGs.]
110
111 Description [http://algs4.cs.princeton.edu/lectures/54RegularExpressions.pdf]
112
113 SideEffects []
114
115 SeeAlso []
116
117 ***********************************************************************/
Gia_SymbSpecial(char c)118 static inline int Gia_SymbSpecial( char c ) { return c == '(' || c == ')' || c == '*' || c == '|'; }
119 // collects info about input alphabet and state of the automaton
Gia_ManRexNumInputs(char * pStr,Vec_Int_t ** pvAlphas,Vec_Int_t ** pvStr2Sta)120 int Gia_ManRexNumInputs( char * pStr, Vec_Int_t ** pvAlphas, Vec_Int_t ** pvStr2Sta )
121 {
122 int i, nStates = 0, Length = strlen(pStr);
123 Vec_Int_t * vAlphas = Vec_IntAlloc( 100 ); // alphabet
124 Vec_Int_t * vStr2Sta = Vec_IntStartFull( Length + 1 ); // symbol to state
125 for ( i = 0; i < Length; i++ )
126 {
127 if ( Gia_SymbSpecial(pStr[i]) )
128 continue;
129 if ( Vec_IntFind(vAlphas, pStr[i]) == -1 )
130 Vec_IntPush( vAlphas, pStr[i] );
131 Vec_IntWriteEntry( vStr2Sta, i, nStates++ );
132 }
133 Vec_IntWriteEntry( vStr2Sta, i, nStates );
134 *pvAlphas = vAlphas;
135 *pvStr2Sta = vStr2Sta;
136 return nStates;
137 }
138 // prints automaton
Gia_ManPrintAutom(char * pStr,Vec_Int_t * vStaTrans)139 void Gia_ManPrintAutom( char * pStr, Vec_Int_t * vStaTrans )
140 {
141 int i = 0, nLength = strlen(pStr);
142 for ( i = 0; i < nLength; i++ )
143 {
144 printf( "%d \'%c\' ", i, pStr[i] );
145 if ( Vec_IntEntry(vStaTrans, i) >= 0 )
146 printf( "-> %d \'%c\' ", Vec_IntEntry(vStaTrans, i), pStr[Vec_IntEntry(vStaTrans, i)] );
147 printf( "\n" );
148 }
149 }
150 // prints states reachable through e-transitions
Gia_ManPrintReached(char * pStr,int iState,Vec_Int_t * vReached)151 void Gia_ManPrintReached( char * pStr, int iState, Vec_Int_t * vReached )
152 {
153 int i, Entry;
154 printf( "Reached from state %d \'%c\': ", iState, pStr[iState] );
155 Vec_IntForEachEntry( vReached, Entry, i )
156 printf( "%d \'%c\' ", Entry, pStr[Entry] );
157 printf( "\n" );
158 }
159 // collect states reachable from the given one by e-transitions
Gia_ManPrintReached_rec(char * pStr,Vec_Int_t * vStaTrans,int iState,Vec_Int_t * vReached,Vec_Int_t * vVisited,int TravId)160 void Gia_ManPrintReached_rec( char * pStr, Vec_Int_t * vStaTrans, int iState, Vec_Int_t * vReached, Vec_Int_t * vVisited, int TravId )
161 {
162 if ( Vec_IntEntry(vVisited, iState) == TravId )
163 return;
164 Vec_IntWriteEntry( vVisited, iState, TravId );
165 if ( !Gia_SymbSpecial(pStr[iState]) ) // read state
166 Vec_IntPush( vReached, iState );
167 if ( pStr[iState] == '\0' )
168 return;
169 if ( Gia_SymbSpecial(pStr[iState]) && pStr[iState] != '|' ) // regular e-transition
170 Gia_ManPrintReached_rec( pStr, vStaTrans, iState + 1, vReached, vVisited, TravId );
171 if ( Vec_IntEntry(vStaTrans, iState) >= 0 ) // additional e-transition
172 Gia_ManPrintReached_rec( pStr, vStaTrans, Vec_IntEntry(vStaTrans, iState), vReached, vVisited, TravId );
173 }
Gia_ManCollectReached(char * pStr,Vec_Int_t * vStaTrans,int iState,Vec_Int_t * vReached,Vec_Int_t * vVisited,int TravId)174 void Gia_ManCollectReached( char * pStr, Vec_Int_t * vStaTrans, int iState, Vec_Int_t * vReached, Vec_Int_t * vVisited, int TravId )
175 {
176 assert( iState == 0 || !Gia_SymbSpecial(pStr[iState]) );
177 assert( Vec_IntEntry(vVisited, iState) != TravId );
178 Vec_IntClear( vReached );
179 Gia_ManPrintReached_rec( pStr, vStaTrans, iState + 1, vReached, vVisited, TravId );
180 }
181 // preprocesses the regular expression
Gia_ManRexPreprocess(char * pStr)182 char * Gia_ManRexPreprocess( char * pStr )
183 {
184 char * pCopy = ABC_CALLOC( char, strlen(pStr) * 2 + 10 );
185 int i, k = 0;
186 pCopy[k++] = '(';
187 pCopy[k++] = '(';
188 for ( i = 0; pStr[i]; i++ )
189 {
190 if ( pStr[i] == '(' )
191 pCopy[k++] = '(';
192 else if ( pStr[i] == ')' )
193 pCopy[k++] = ')';
194 if ( pStr[i] != ' ' && pStr[i] != '\t' && pStr[i] != '\n' && pStr[i] != '\r' )
195 pCopy[k++] = pStr[i];
196 }
197 pCopy[k++] = ')';
198 pCopy[k++] = ')';
199 pCopy[k++] = '\0';
200 return pCopy;
201 }
202 // construct sequential AIG for the automaton
Gia_ManRex2Gia(char * pStrInit,int fOrder,int fVerbose)203 Gia_Man_t * Gia_ManRex2Gia( char * pStrInit, int fOrder, int fVerbose )
204 {
205 Gia_Man_t * pNew = NULL, * pTemp;
206 Vec_Int_t * vAlphas, * vStr2Sta, * vStaLits;
207 Vec_Int_t * vStaTrans, * vStack, * vVisited;
208 Vec_Str_t * vInit;
209 char * pStr = Gia_ManRexPreprocess( pStrInit );
210 int nStates = Gia_ManRexNumInputs( pStr, &vAlphas, &vStr2Sta );
211 int i, k, iLit, Entry, nLength = strlen(pStr), nTravId = 1;
212 if ( fOrder )
213 Vec_IntSort( vAlphas, 0 );
214 // if ( fVerbose )
215 {
216 printf( "Input variable order: " );
217 Vec_IntForEachEntry( vAlphas, Entry, k )
218 printf( "%c", (char)Entry );
219 printf( "\n" );
220 }
221 // start AIG
222 pNew = Gia_ManStart( 1000 );
223 pNew->pName = Abc_UtilStrsav( pStrInit );
224 for ( i = 0; i < Vec_IntSize(vAlphas) + nStates; i++ )
225 Gia_ManAppendCi( pNew );
226 // prepare automaton
227 vStaLits = Vec_IntStart( nStates + 1 );
228 vStaTrans = Vec_IntStartFull( nLength );
229 vStack = Vec_IntAlloc( nLength );
230 vVisited = Vec_IntStartFull( nLength + 1 );
231 for ( i = 0; i < nLength; i++ )
232 {
233 int Lp = i;
234 if ( pStr[i] == '(' || pStr[i] == '|' )
235 Vec_IntPush( vStack, i );
236 else if ( pStr[i] == ')' )
237 {
238 int Or = Vec_IntPop( vStack );
239 if ( pStr[Or] == '|' )
240 {
241 Lp = Vec_IntPop( vStack );
242 Vec_IntWriteEntry( vStaTrans, Lp, Or + 1 );
243 Vec_IntWriteEntry( vStaTrans, Or, i );
244 }
245 else
246 Lp = Or;
247 }
248 if ( i < nLength - 1 && pStr[i+1] == '*' )
249 {
250 Vec_IntWriteEntry( vStaTrans, Lp, i+1 );
251 Vec_IntWriteEntry( vStaTrans, i+1, Lp );
252 }
253 }
254 assert( Vec_IntSize(vStack) == 0 );
255 if ( fVerbose )
256 Gia_ManPrintAutom( pStr, vStaTrans );
257
258 // create next-state functions for each state
259 Gia_ManHashAlloc( pNew );
260 for ( i = 1; i < nLength; i++ )
261 {
262 int iThis, iThat, iThisLit, iInputLit;
263 if ( Gia_SymbSpecial(pStr[i]) )
264 continue;
265 Gia_ManCollectReached( pStr, vStaTrans, i, vStack, vVisited, nTravId++ );
266 if ( fVerbose )
267 Gia_ManPrintReached( pStr, i, vStack );
268 // create transitions from this state under this input
269 iThis = Vec_IntEntry(vStr2Sta, i);
270 iThisLit = Gia_Obj2Lit(pNew, Gia_ManPi(pNew, Vec_IntSize(vAlphas) + iThis));
271 iInputLit = Gia_Obj2Lit(pNew, Gia_ManPi(pNew, Vec_IntFind(vAlphas, pStr[i])));
272 iLit = Gia_ManHashAnd( pNew, iThisLit, iInputLit );
273 Vec_IntForEachEntry( vStack, Entry, k )
274 {
275 iThat = Vec_IntEntry(vStr2Sta, Entry);
276 iLit = Gia_ManHashOr( pNew, iLit, Vec_IntEntry(vStaLits, iThat) );
277 Vec_IntWriteEntry( vStaLits, iThat, iLit );
278 }
279 }
280 // create one-hotness
281 Vec_IntClear( vStack );
282 for ( i = 0; i < Vec_IntSize(vAlphas); i++ )
283 Vec_IntPush( vStack, Gia_Obj2Lit(pNew, Gia_ManPi(pNew, i)) );
284 iLit = Gia_ManBuild1Hot( pNew, vStack );
285 // combine with outputs
286 Vec_IntForEachEntry( vStaLits, Entry, k )
287 Vec_IntWriteEntry( vStaLits, k, Gia_ManHashAnd(pNew, iLit, Entry) );
288 Gia_ManHashStop( pNew );
289
290 // collect initial state
291 Gia_ManCollectReached( pStr, vStaTrans, 0, vStack, vVisited, nTravId++ );
292 if ( fVerbose )
293 Gia_ManPrintReached( pStr, 0, vStack );
294 vInit = Vec_StrStart( nStates + 1 );
295 Vec_StrFill( vInit, nStates, '0' );
296 Vec_IntForEachEntry( vStack, Entry, k )
297 if ( pStr[Entry] != '\0' )
298 Vec_StrWriteEntry( vInit, Vec_IntEntry(vStr2Sta, Entry), '1' );
299 if ( fVerbose )
300 printf( "Init state = %s\n", Vec_StrArray(vInit) );
301
302 // add outputs
303 Vec_IntPushFirst( vStaLits, Vec_IntPop(vStaLits) );
304 assert( Vec_IntSize(vStaLits) == nStates + 1 );
305 Vec_IntForEachEntry( vStaLits, iLit, i )
306 Gia_ManAppendCo( pNew, iLit );
307 Gia_ManSetRegNum( pNew, nStates );
308 pNew = Gia_ManCleanup( pTemp = pNew );
309 Gia_ManStop( pTemp );
310
311 // add initial state
312 pNew = Gia_ManDupZeroUndc( pTemp = pNew, Vec_StrArray(vInit), 0, 0, 0 );
313 Gia_ManStop( pTemp );
314 Vec_StrFree( vInit );
315 /*
316 Gia_ManAutomSimulate( pNew, vAlphas, "0" );
317 Gia_ManAutomSimulate( pNew, vAlphas, "01" );
318 Gia_ManAutomSimulate( pNew, vAlphas, "110" );
319 Gia_ManAutomSimulate( pNew, vAlphas, "011" );
320 Gia_ManAutomSimulate( pNew, vAlphas, "111" );
321 Gia_ManAutomSimulate( pNew, vAlphas, "1111" );
322 Gia_ManAutomSimulate( pNew, vAlphas, "1010" );
323
324 Gia_ManAutomSimulate( pNew, vAlphas, "A" );
325 Gia_ManAutomSimulate( pNew, vAlphas, "AD" );
326 Gia_ManAutomSimulate( pNew, vAlphas, "ABCD" );
327 Gia_ManAutomSimulate( pNew, vAlphas, "BCD" );
328 Gia_ManAutomSimulate( pNew, vAlphas, "CD" );
329 */
330
331 // cleanup
332 Vec_IntFree( vAlphas );
333 Vec_IntFree( vStr2Sta );
334 Vec_IntFree( vStaLits );
335 Vec_IntFree( vStaTrans );
336 Vec_IntFree( vStack );
337 Vec_IntFree( vVisited );
338 ABC_FREE( pStr );
339 return pNew;
340 }
341
342
343 /**Function*************************************************************
344
345 Synopsis [Transposing 64-bit matrix.]
346
347 Description [Borrowed from "Hacker's Delight", by Henry Warren.]
348
349 SideEffects []
350
351 SeeAlso []
352
353 ***********************************************************************/
Gia_ManAutomTranspose64(word A[64])354 void Gia_ManAutomTranspose64( word A[64] )
355 {
356 int j, k;
357 word t, m = 0x00000000FFFFFFFF;
358 for ( j = 32; j != 0; j = j >> 1, m = m ^ (m << j) )
359 {
360 for ( k = 0; k < 64; k = (k + j + 1) & ~j )
361 {
362 t = (A[k] ^ (A[k+j] >> j)) & m;
363 A[k] = A[k] ^ t;
364 A[k+j] = A[k+j] ^ (t << j);
365 }
366 }
367 }
368
369 /**Function*************************************************************
370
371 Synopsis [Simulate AIG with the given sequence.]
372
373 Description []
374
375 SideEffects []
376
377 SeeAlso []
378
379 ***********************************************************************/
Gia_ManAutomSim0(Gia_Man_t * p,Gia_Obj_t * pObj,Vec_Wrd_t * vTemp)380 static inline word Gia_ManAutomSim0( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Wrd_t * vTemp )
381 {
382 return Gia_ObjFaninC0(pObj) ? ~Vec_WrdEntry(vTemp, Gia_ObjFaninId0p(p, pObj)) : Vec_WrdEntry(vTemp, Gia_ObjFaninId0p(p, pObj));
383 }
Gia_ManAutomSim1(Gia_Man_t * p,Gia_Obj_t * pObj,Vec_Wrd_t * vTemp)384 static inline word Gia_ManAutomSim1( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Wrd_t * vTemp )
385 {
386 return Gia_ObjFaninC1(pObj) ? ~Vec_WrdEntry(vTemp, Gia_ObjFaninId1p(p, pObj)) : Vec_WrdEntry(vTemp, Gia_ObjFaninId1p(p, pObj));
387 }
Gia_ManAutomStep(Gia_Man_t * p,word Cur,word * pNext,Vec_Wrd_t * vTemp)388 word Gia_ManAutomStep( Gia_Man_t * p, word Cur, word * pNext, Vec_Wrd_t * vTemp )
389 {
390 Gia_Obj_t * pObj; int i;
391 assert( Gia_ManPoNum(p) == 1 );
392 assert( Vec_WrdSize(vTemp) >= Gia_ManObjNum(p) );
393 Vec_WrdWriteEntry( vTemp, 0, 0 );
394 Gia_ManForEachPi( p, pObj, i )
395 Vec_WrdWriteEntry( vTemp, Gia_ObjId(p, pObj), ((word)1) << (63-i) );
396 Gia_ManForEachRo( p, pObj, i )
397 Vec_WrdWriteEntry( vTemp, Gia_ObjId(p, pObj), ((Cur >> (63-i)) & 1) ? ~((word)0) : 0 );
398 Gia_ManForEachAnd( p, pObj, i )
399 Vec_WrdWriteEntry( vTemp, i, Gia_ManAutomSim0(p, pObj, vTemp) & Gia_ManAutomSim1(p, pObj, vTemp) );
400 Gia_ManForEachRi( p, pObj, i )
401 pNext[i] = Gia_ManAutomSim0(p, pObj, vTemp);
402 for ( ; i < 64; i++ )
403 pNext[i] = 0;
404 // transpose
405 // for ( i = 0; i < 64; i++ )
406 // Extra_PrintBinary( stdout, (unsigned *)&pNext[i], 64 ), Abc_Print( 1, "\n" );
407 // printf( "\n" );
408 Gia_ManAutomTranspose64( pNext );
409 // for ( i = 0; i < 64; i++ )
410 // Extra_PrintBinary( stdout, (unsigned *)&pNext[i], 64 ), Abc_Print( 1, "\n" );
411 // printf( "\n" );
412 // return output values
413 return Gia_ManAutomSim0(p, Gia_ManPo(p, 0), vTemp);
414 }
Gia_ManAutomWalkOne(Gia_Man_t * p,int nSteps,Vec_Wrd_t * vStates,Vec_Int_t * vCounts,Vec_Wrd_t * vTemp,word Init)415 void Gia_ManAutomWalkOne( Gia_Man_t * p, int nSteps, Vec_Wrd_t * vStates, Vec_Int_t * vCounts, Vec_Wrd_t * vTemp, word Init )
416 {
417 word iState = 0, Output, pNext[64];
418 int i, k, kMin, Index, IndexMin;
419 int Count, CountMin;
420 for ( i = 0; i < nSteps; i++ )
421 {
422 Output = Gia_ManAutomStep( p, iState, pNext, vTemp );
423 // check visited states
424 kMin = -1;
425 IndexMin = -1;
426 CountMin = ABC_INFINITY;
427 for ( k = 0; k < Gia_ManPiNum(p); k++ )
428 {
429 if ( pNext[k] == Init )
430 continue;
431 Index = Vec_WrdFind( vStates, pNext[k] );
432 Count = Index == -1 ? 0 : Vec_IntEntry( vCounts, Index );
433 if ( CountMin > Count || (CountMin != ABC_INFINITY && Count && ((float)CountMin / Count) > (float)rand()/RAND_MAX ) )
434 {
435 CountMin = Count;
436 IndexMin = Index;
437 kMin = k;
438 }
439 if ( CountMin == 0 )
440 break;
441 }
442 // choose the best state
443 if ( CountMin == ABC_INFINITY )
444 {
445 for ( k = 0; k < Gia_ManPiNum(p); k++ )
446 if ( (Output >> (63-k)) & 1 )
447 {
448 printf( "%c", 'a' + k );
449 printf( "!" );
450 }
451 break;
452 }
453 assert( CountMin < ABC_INFINITY );
454 if ( IndexMin == -1 )
455 {
456 assert( CountMin == 0 );
457 IndexMin = Vec_IntSize(vCounts);
458 Vec_IntPush( vCounts, 0 );
459 Vec_WrdPush( vStates, pNext[kMin] );
460 }
461 Vec_IntAddToEntry( vCounts, IndexMin, 1 );
462 iState = pNext[kMin];
463 //Extra_PrintBinary( stdout, (unsigned *)&iState, 64 ); printf( "\n" );
464 // print the transition
465 printf( "%c", 'a' + kMin );
466 if ( (Output >> (63-kMin)) & 1 )
467 printf( "!" );
468 }
469 printf( "\n" );
470 }
471 // find flop variables pointed to by negative edges
Gia_ManAutomInit(Gia_Man_t * p)472 word Gia_ManAutomInit( Gia_Man_t * p )
473 {
474 Gia_Obj_t * pObj;
475 int i, Index;
476 word Init = 0;
477 Gia_ManForEachAnd( p, pObj, i )
478 {
479 if ( Gia_ObjFaninC0(pObj) && Gia_ObjIsCi(Gia_ObjFanin0(pObj)) )
480 {
481 Index = Gia_ObjCioId(Gia_ObjFanin0(pObj)) - Gia_ManPiNum(p);
482 if ( Index >= 0 )
483 Init |= ((word)1 << (63-Index));
484 }
485 if ( Gia_ObjFaninC1(pObj) && Gia_ObjIsCi(Gia_ObjFanin1(pObj)) )
486 {
487 Index = Gia_ObjCioId(Gia_ObjFanin1(pObj)) - Gia_ManPiNum(p);
488 if ( Index >= 0 )
489 Init |= ((word)1 << (63-Index));
490 }
491 }
492 return Init;
493 }
Gia_ManAutomWalk(Gia_Man_t * p,int nSteps,int nWalks,int fVerbose)494 void Gia_ManAutomWalk( Gia_Man_t * p, int nSteps, int nWalks, int fVerbose )
495 {
496 Vec_Wrd_t * vTemp, * vStates;
497 Vec_Int_t * vCounts; int i; word Init;
498 if ( Gia_ManPoNum(p) != 1 )
499 {
500 printf( "AIG should have one primary output.\n" );
501 return;
502 }
503 if ( Gia_ManPiNum(p) > 64 )
504 {
505 printf( "Cannot simulate an automaton with more than 64 inputs.\n" );
506 return;
507 }
508 if ( Gia_ManRegNum(p) > 64 )
509 {
510 printf( "Cannot simulate an automaton with more than 63 states.\n" );
511 return;
512 }
513 vTemp = Vec_WrdStart( Gia_ManObjNum(p) );
514 vStates = Vec_WrdAlloc( 1000 );
515 vCounts = Vec_IntAlloc( 1000 );
516 Vec_WrdPush( vStates, 0 );
517 Vec_IntPush( vCounts, 1 );
518 Init = Gia_ManAutomInit( p );
519 for ( i = 0; i < nWalks; i++ )
520 Gia_ManAutomWalkOne( p, nSteps, vStates, vCounts, vTemp, Init );
521 if ( fVerbose )
522 {
523 word State;
524 Vec_WrdForEachEntry( vStates, State, i )
525 {
526 State ^= Init;
527 printf( "%3d : ", i );
528 Extra_PrintBinary( stdout, (unsigned *)&State, 64 );
529 printf( " %d ", Vec_IntEntry(vCounts, i) );
530 printf( "\n" );
531 }
532 printf( "\n" );
533 }
534 Vec_WrdFree( vTemp );
535 Vec_WrdFree( vStates );
536 Vec_IntFree( vCounts );
537 }
538
539 ////////////////////////////////////////////////////////////////////////
540 /// END OF FILE ///
541 ////////////////////////////////////////////////////////////////////////
542
543
544 ABC_NAMESPACE_IMPL_END
545
546