ABC: A System for Sequential Synthesis and Verification
 
Loading...
Searching...
No Matches
acecPo.c
Go to the documentation of this file.
1
20
21#include "acecInt.h"
22#include "misc/vec/vecWec.h"
23#include "misc/vec/vecHsh.h"
24
25ABC_NAMESPACE_IMPL_START
26
30
34
46void Acec_ParseSignatureMono( char * p, char * pStop, Vec_Int_t * vLevel )
47{
48 char * pTemp = p;
49 int Const = ABC_INFINITY;
50 int fMinus = pTemp[0] == '-';
51 if ( pTemp[0] == '+' || pTemp[0] == '-' || pTemp[0] == '(' )
52 pTemp++;
53 while ( pTemp < pStop )
54 {
55 if ( pTemp[0] == 'i' ) // input
56 Vec_IntPush( vLevel, -1-atoi(++pTemp) );
57 else if ( pTemp[0] == 'o' ) // output
58 Vec_IntPush( vLevel, atoi(++pTemp) );
59 else // coefficient
60 {
61 assert( Const == ABC_INFINITY );
62 Const = 1 + atoi(pTemp);
63 }
64 while ( pTemp[0] >= '0' && pTemp[0] <= '9' )
65 pTemp++;
66 assert( pTemp == pStop || pTemp[0] == '*' );
67 pTemp++;
68 }
69 assert( Const != ABC_INFINITY );
70 Vec_IntPush( vLevel, fMinus ? -Const : Const );
71}
72Vec_Wec_t * Acec_ParseSignatureOne( char * p, char * pStop )
73{
74 Vec_Wec_t * vMonos = Vec_WecAlloc( 10 );
75 char * pTemp = p, * pNext;
76 assert( p[0] == '(' && pStop[0] == ')' );
77 while ( pTemp[0] != ')' )
78 {
79 for ( pNext = pTemp+1; pNext < pStop; pNext++ )
80 if ( pNext[0] == '+' || pNext[0] == '-' )
81 break;
82 assert( pNext[0] == '+' || pNext[0] == '-' || pNext[0] == ')' );
83 Acec_ParseSignatureMono( pTemp, pNext, Vec_WecPushLevel(vMonos) );
84 pTemp = pNext;
85 }
86 return vMonos;
87}
88Vec_Wec_t * Acec_ParseDistribute( Vec_Wec_t * vM1, Vec_Wec_t * vM2, Vec_Wec_t * vAdd )
89{
90 Vec_Wec_t * vMonos = Vec_WecAlloc( 10 );
91 Vec_Int_t * vLevel1, * vLevel2, * vLevel;
92 int i, k, n, Entry;
93 Vec_WecForEachLevel( vM1, vLevel1, i )
94 Vec_WecForEachLevel( vM2, vLevel2, k )
95 {
96 vLevel = Vec_WecPushLevel(vMonos);
97 Vec_IntForEachEntryStop( vLevel1, Entry, n, Vec_IntSize(vLevel1)-1 )
98 Vec_IntPush(vLevel, Entry);
99 Vec_IntForEachEntryStop( vLevel2, Entry, n, Vec_IntSize(vLevel2)-1 )
100 Vec_IntPush(vLevel, Entry);
101 Vec_IntPush(vLevel, Vec_IntEntryLast(vLevel1)+Vec_IntEntryLast(vLevel2)-1);
102 }
103 Vec_WecForEachLevel( vAdd, vLevel1, k )
104 {
105 vLevel = Vec_WecPushLevel(vMonos);
106 Vec_IntForEachEntry( vLevel1, Entry, n )
107 Vec_IntPush(vLevel, Entry);
108 }
109 return vMonos;
110}
111Vec_Wec_t * Acec_ParseSignature( char * p )
112{
113 Vec_Wec_t * vAdd = NULL, * vTemp1, * vTemp2, * vRes;
114 if ( p[0] == '(' )
115 {
116 char * pStop = strstr(p, ")");
117 if ( pStop == NULL )
118 return NULL;
119 vTemp1 = Acec_ParseSignatureOne( p, pStop );
120 if ( pStop[1] == 0 )
121 return vTemp1;
122 if ( pStop[1] == '*' )
123 {
124 char * p2 = pStop + 2;
125 char * pStop2 = strstr(p2, ")");
126 if ( p2[0] != '(' )
127 return NULL;
128 if ( pStop2 == NULL )
129 return NULL;
130 vTemp2 = Acec_ParseSignatureOne( p2, pStop2 );
131 if ( pStop2[1] == 0 )
132 {
133 vRes = Acec_ParseDistribute( vTemp1, vTemp2, vAdd );
134 Vec_WecFree( vTemp1 );
135 Vec_WecFree( vTemp2 );
136 return vRes;
137 }
138 if ( pStop2[1] == '+' )
139 {
140 char * p3 = pStop2 + 2;
141 char * pStop3 = strstr(p3, ")");
142 if ( p3[0] != '(' )
143 return NULL;
144 if ( pStop3 == NULL )
145 return NULL;
146 vAdd = Acec_ParseSignatureOne( p3, pStop3 );
147 vRes = Acec_ParseDistribute( vTemp1, vTemp2, vAdd );
148 Vec_WecFree( vTemp1 );
149 Vec_WecFree( vTemp2 );
150 Vec_WecFree( vAdd );
151 return vRes;
152 }
153 assert( 0 );
154 }
155 assert( 0 );
156 }
157 else
158 {
159 int Len = strlen(p);
160 char * pCopy = ABC_ALLOC( char, Len+3 );
161 pCopy[0] = '(';
162 strcpy( pCopy+1, p );
163 pCopy[Len+1] = ')';
164 pCopy[Len+2] = '\0';
165 vRes = Acec_ParseSignatureOne( pCopy, pCopy + Len + 1 );
166 ABC_FREE( pCopy );
167 return vRes;
168 }
169 return NULL;
170}
171void Acec_PrintSignature( Vec_Wec_t * vMonos )
172{
173 Vec_Int_t * vLevel; int i, k, Entry;
174 printf( "Output signature with %d monomials:\n", Vec_WecSize(vMonos) );
175 Vec_WecForEachLevel( vMonos, vLevel, i )
176 {
177 printf( " %s2^%d", Vec_IntEntryLast(vLevel) > 0 ? "+":"-", Abc_AbsInt(Vec_IntEntryLast(vLevel))-1 );
178 Vec_IntForEachEntryStop( vLevel, Entry, k, Vec_IntSize(vLevel)-1 )
179 {
180 printf( " * " );
181 if ( Entry < 0 )
182 printf( "i%d", -Entry-1 );
183 else
184 printf( "o%d", Entry );
185 }
186 printf( "\n" );
187 }
188}
189void Acec_ParseSignatureTest()
190{
191 char * pSign = "(4*o1+2*o2+1*o3)*(4*i4+2*i5+1*i6)+(4*o4+2*o5+1*o6)";
192 Vec_Wec_t * vMonos = Acec_ParseSignature( pSign );
193 Acec_PrintSignature( vMonos );
194 Vec_WecFree( vMonos );
195}
196
208static inline void Vec_IntPushOrderAbs( Vec_Int_t * p, int Entry )
209{
210 int i;
211 for ( i = 0; i < p->nSize; i++ )
212 assert( Entry != p->pArray[i] );
213 if ( p->nSize == p->nCap )
214 {
215 if ( p->nCap < 16 )
216 Vec_IntGrow( p, 16 );
217 else
218 Vec_IntGrow( p, 2 * p->nCap );
219 }
220 p->nSize++;
221 for ( i = p->nSize-2; i >= 0; i-- )
222 if ( Abc_AbsInt(p->pArray[i]) < Abc_AbsInt(Entry) )
223 p->pArray[i+1] = p->pArray[i];
224 else
225 break;
226 p->pArray[i+1] = Entry;
227}
228static inline void Vec_IntAppendMinusAbs( Vec_Int_t * vVec1, Vec_Int_t * vVec2, int fMinus )
229{
230 int Entry, i;
231 Vec_IntClear( vVec1 );
232 Vec_IntForEachEntry( vVec2, Entry, i )
233 Vec_IntPushOrderAbs( vVec1, fMinus ? -Entry : Entry );
234}
235static inline void Vec_IntCheckUniqueOrderAbs( Vec_Int_t * p )
236{
237 int i;
238 for ( i = 1; i < p->nSize; i++ )
239 assert( Abc_AbsInt(p->pArray[i-1]) > Abc_AbsInt(p->pArray[i]) );
240}
241static inline void Vec_IntCheckUniqueOrder( Vec_Int_t * p )
242{
243 int i;
244 for ( i = 1; i < p->nSize; i++ )
245 assert( p->pArray[i-1] < p->pArray[i] );
246}
247
259void Gia_PolynPrintMono( Vec_Int_t * vConst, Vec_Int_t * vMono, int Prev )
260{
261 int k, Entry;
262 printf( "%c ", Prev != Abc_AbsInt(Vec_IntEntry(vConst, 0)) ? '|' : ' ' );
263 Vec_IntForEachEntry( vConst, Entry, k )
264 printf( "%s2^%d", Entry < 0 ? "-" : "+", Abc_AbsInt(Entry)-1 );
265 Vec_IntForEachEntry( vMono, Entry, k )
266 printf( " * i%d", Entry-1 );
267 printf( "\n" );
268}
269void Gia_PolynPrint( Vec_Wec_t * vPolyn )
270{
271 Vec_Int_t * vConst, * vMono;
272 int i, Prev = -1;
273 printf( "Polynomial with %d monomials:\n", Vec_WecSize(vPolyn)/2 );
274 for ( i = 0; i < Vec_WecSize(vPolyn)/2; i++ )
275 {
276 vConst = Vec_WecEntry( vPolyn, 2*i+0 );
277 vMono = Vec_WecEntry( vPolyn, 2*i+1 );
278 Gia_PolynPrintMono( vConst, vMono, Prev );
279 Prev = Abc_AbsInt( Vec_IntEntry(vConst, 0) );
280 }
281}
282void Gia_PolynPrintStats( Vec_Wec_t * vPolyn )
283{
284 Vec_Int_t * vConst, * vCountsP, * vCountsN;
285 int i, Entry, Max = 0;
286 printf( "Input signature with %d monomials:\n", Vec_WecSize(vPolyn)/2 );
287 for ( i = 0; i < Vec_WecSize(vPolyn)/2; i++ )
288 {
289 vConst = Vec_WecEntry( vPolyn, 2*i+0 );
290 Max = Abc_MaxInt( Max, Abc_AbsInt(Abc_AbsInt(Vec_IntEntry(vConst, 0))) );
291 }
292 vCountsP = Vec_IntStart( Max + 1 );
293 vCountsN = Vec_IntStart( Max + 1 );
294 for ( i = 0; i < Vec_WecSize(vPolyn)/2; i++ )
295 {
296 vConst = Vec_WecEntry( vPolyn, 2*i+0 );
297 Entry = Vec_IntEntry(vConst, 0);
298 if ( Entry > 0 )
299 Vec_IntAddToEntry( vCountsP, Entry, 1 );
300 else
301 Vec_IntAddToEntry( vCountsN, -Entry, 1 );
302 }
303 Vec_IntForEachEntry( vCountsN, Entry, i )
304 if ( Entry )
305 printf( " -2^%d appears %d times\n", Abc_AbsInt(i)-1, Entry );
306 Vec_IntForEachEntry( vCountsP, Entry, i )
307 if ( Entry )
308 printf( " +2^%d appears %d times\n", Abc_AbsInt(i)-1, Entry );
309 Vec_IntFree( vCountsP );
310 Vec_IntFree( vCountsN );
311}
312
325int Gia_PolynGetResultCompare( int * p0, int * p1 )
326{
327 if ( p0[2] < p1[2] ) return -1;
328 if ( p0[2] > p1[2] ) return 1;
329 return 0;
330}
331Vec_Wec_t * Gia_PolynGetResult( Hsh_VecMan_t * pHashC, Hsh_VecMan_t * pHashM, Vec_Int_t * vCoefs )
332{
333 Vec_Int_t * vClass, * vLevel, * vArray;
334 Vec_Wec_t * vPolyn, * vSorted;
335 int i, k, iConst, iMono, iFirst;
336 // find the largest
337 int nLargest = 0, nNonConst = 0;
338 Vec_IntForEachEntry( vCoefs, iConst, iMono )
339 {
340 //Vec_IntPrint( Hsh_VecReadEntry(pHashM, iMono) );
341 if ( iConst == 0 )
342 continue;
343 vArray = Hsh_VecReadEntry( pHashC, iConst );
344 nLargest = Abc_MaxInt( nLargest, Abc_AbsInt(Vec_IntEntry(vArray, 0)) );
345 nNonConst++;
346 }
347 // sort by the size of the largest coefficient
348 vSorted = Vec_WecStart( nLargest+1 );
349 Vec_IntForEachEntry( vCoefs, iConst, iMono )
350 {
351 if ( iConst == 0 )
352 continue;
353 vArray = Hsh_VecReadEntry( pHashC, iConst );
354 vLevel = Vec_WecEntry( vSorted, Abc_AbsInt(Vec_IntEntry(vArray, 0)) );
355 vArray = Hsh_VecReadEntry( pHashM, iMono );
356 iFirst = Vec_IntSize(vArray) ? Vec_IntEntry(vArray, 0) : -1;
357 Vec_IntPushThree( vLevel, iConst, iMono, iFirst );
358 }
359 // reload in the given order
360 vPolyn = Vec_WecAlloc( 2*nNonConst );
361 Vec_WecForEachLevel( vSorted, vClass, i )
362 {
363 // sort monomials by the index of the first variable
364 qsort( Vec_IntArray(vClass), (size_t)(Vec_IntSize(vClass)/3), 12, (int (*)(const void *, const void *))Gia_PolynGetResultCompare );
365 Vec_IntForEachEntryTriple( vClass, iConst, iMono, iFirst, k )
366 {
367 vArray = Hsh_VecReadEntry( pHashC, iConst );
368 Vec_IntCheckUniqueOrderAbs( vArray );
369 vLevel = Vec_WecPushLevel( vPolyn );
370 Vec_IntGrow( vLevel, Vec_IntSize(vArray) );
371 Vec_IntAppend( vLevel, vArray );
372
373 vArray = Hsh_VecReadEntry( pHashM, iMono );
374 Vec_IntCheckUniqueOrder( vArray );
375 vLevel = Vec_WecPushLevel( vPolyn );
376 Vec_IntGrow( vLevel, Vec_IntSize(vArray) );
377 Vec_IntAppend( vLevel, vArray );
378 }
379 }
380 assert( Vec_WecSize(vPolyn) == 2*nNonConst );
381 Vec_WecFree( vSorted );
382 return vPolyn;
383}
384
385
397static inline void Gia_PolynMergeConstOne( Vec_Int_t * vConst, int New )
398{
399 int i, Old;
400 assert( New != 0 );
401 Vec_IntForEachEntry( vConst, Old, i )
402 {
403 assert( Old != 0 );
404 if ( Old == New ) // A == B
405 {
406 Vec_IntDrop( vConst, i );
407 Gia_PolynMergeConstOne( vConst, New > 0 ? New + 1 : New - 1 );
408 return;
409 }
410 if ( Abc_AbsInt(Old) == Abc_AbsInt(New) ) // A == -B
411 {
412 Vec_IntDrop( vConst, i );
413 return;
414 }
415 if ( Old + New == 1 || Old + New == -1 ) // sign(A) != sign(B) && abs(abs(A)-abs(B)) == 1
416 {
417 int Value = Abc_MinInt( Abc_AbsInt(Old), Abc_AbsInt(New) );
418 Vec_IntDrop( vConst, i );
419 Gia_PolynMergeConstOne( vConst, (Old + New == 1) ? Value : -Value );
420 return;
421 }
422 }
423 Vec_IntPushOrderAbs( vConst, New );
424}
425static inline void Gia_PolynMergeConst( Vec_Int_t * vTempC, Hsh_VecMan_t * pHashC, int iConstAdd )
426{
427 int i, New;
428 Vec_Int_t * vConstAdd = Hsh_VecReadEntry( pHashC, iConstAdd );
429 Vec_IntForEachEntry( vConstAdd, New, i )
430 {
431 Gia_PolynMergeConstOne( vTempC, New );
432 vConstAdd = Hsh_VecReadEntry( pHashC, iConstAdd );
433 }
434 Vec_IntCheckUniqueOrderAbs( vConstAdd );
435 //Vec_IntPrint( vConstAdd );
436}
437static inline int Gia_PolynBuildAdd( Hsh_VecMan_t * pHashC, Hsh_VecMan_t * pHashM, Vec_Int_t * vCoefs,
438 Vec_Wec_t * vLit2Mono, Vec_Int_t * vTempC, Vec_Int_t * vTempM )
439{
440 int i, iLit, iConst, iConstNew;
441 int iMono = Hsh_VecManAdd(pHashM, vTempM);
442 if ( iMono == Vec_IntSize(vCoefs) ) // new monomial
443 {
444 // map monomial into a constant
445 assert( Vec_IntSize(vTempC) > 0 );
446 iConst = Hsh_VecManAdd( pHashC, vTempC );
447 Vec_IntPush( vCoefs, iConst );
448 // map literals into monomial
449 assert( Vec_IntSize(vTempM) > 0 );
450 Vec_IntForEachEntry( vTempM, iLit, i )
451 Vec_WecPush( vLit2Mono, iLit, iMono );
452 //printf( "New monomial: \n" );
453 //Gia_PolynPrintMono( vTempC, vTempM );
454 return 1;
455 }
456 // this monomial exists
457 iConst = Vec_IntEntry( vCoefs, iMono );
458 if ( iConst )
459 Gia_PolynMergeConst( vTempC, pHashC, iConst );
460 iConstNew = Hsh_VecManAdd( pHashC, vTempC );
461 Vec_IntWriteEntry( vCoefs, iMono, iConstNew );
462 //printf( "Old monomial: \n" );
463 //Gia_PolynPrintMono( vTempC, vTempM );
464 if ( iConst && !iConstNew )
465 return -1;
466 if ( !iConst && iConstNew )
467 return 1;
468 return 0;
469}
470
482static inline int Gia_PolynHandleOne( Hsh_VecMan_t * pHashC, Hsh_VecMan_t * pHashM, Vec_Int_t * vCoefs,
483 Vec_Wec_t * vLit2Mono, Vec_Int_t * vTempC, Vec_Int_t * vTempM,
484 int iMono, int iLitOld, int iLitNew0, int iLitNew1 )
485{
486 int status, iConst = Vec_IntEntry( vCoefs, iMono );
487 Vec_Int_t * vArrayC = Hsh_VecReadEntry( pHashC, iConst );
488 Vec_Int_t * vArrayM = Hsh_VecReadEntry( pHashM, iMono );
489 // create new monomial
490 Vec_IntClear( vTempM );
491 Vec_IntAppend( vTempM, vArrayM );
492 status = Vec_IntRemove( vTempM, iLitOld );
493 assert( status );
494 // create new monomial
495 if ( iLitNew0 == -1 && iLitNew1 == -1 ) // no new lit - the same const
496 Vec_IntAppendMinusAbs( vTempC, vArrayC, 0 );
497 else if ( iLitNew0 > -1 && iLitNew1 == -1 ) // one new lit - opposite const
498 {
499 Vec_IntAppendMinusAbs( vTempC, vArrayC, 1 );
500 Vec_IntPushUniqueOrder( vTempM, iLitNew0 );
501 }
502 else if ( iLitNew0 > -1 && iLitNew1 > -1 ) // both new lit - the same const
503 {
504 Vec_IntAppendMinusAbs( vTempC, vArrayC, 0 );
505 Vec_IntPushUniqueOrder( vTempM, iLitNew0 );
506 Vec_IntPushUniqueOrder( vTempM, iLitNew1 );
507 }
508 else assert( 0 );
509 return Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC, vTempM );
510}
511
512Vec_Wec_t * Gia_PolynBuildNew2( Gia_Man_t * pGia, Vec_Int_t * vRootLits, int nExtra, Vec_Int_t * vLeaves, Vec_Int_t * vNodes, int fSigned, int fVerbose, int fVeryVerbose )
513{
514 abctime clk = Abc_Clock();
515 Vec_Wec_t * vPolyn;
516 Vec_Wec_t * vLit2Mono = Vec_WecStart( 2 * Gia_ManObjNum(pGia) ); // mapping AIG literals into monomials
517 Hsh_VecMan_t * pHashC = Hsh_VecManStart( 1000 ); // hash table for constants
518 Hsh_VecMan_t * pHashM = Hsh_VecManStart( 1000 ); // hash table for monomials
519 Vec_Int_t * vCoefs = Vec_IntAlloc( 1000 ); // monomial coefficients
520 Vec_Int_t * vTempC = Vec_IntAlloc( 10 ); // temporary array
521 Vec_Int_t * vTempM = Vec_IntAlloc( 10 ); // temporary array
522 int i, k, iObj, iLit, iMono, nMonos = 0, nBuilds = 0;
523
524 // add 0-constant and 1-monomial
525 Hsh_VecManAdd( pHashC, vTempC );
526 Hsh_VecManAdd( pHashM, vTempM );
527 Vec_IntPush( vCoefs, 0 );
528
529 // create output signature
530 Vec_IntForEachEntry( vRootLits, iLit, i )
531 {
532 int Value = 1 + Abc_MinInt( i, Vec_IntSize(vRootLits)-nExtra );
533 Vec_IntFill( vTempC, 1, (fSigned && i == Vec_IntSize(vRootLits)-1-nExtra) ? -Value : Value );
534 Vec_IntFill( vTempM, 1, iLit );
535 nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC, vTempM );
536 nBuilds++;
537 }
538
539 // perform construction for internal nodes
540 Vec_IntForEachEntryReverse( vNodes, iObj, i )
541 {
542 Gia_Obj_t * pObj = Gia_ManObj( pGia, iObj );
543 int iLits[2] = { Abc_Var2Lit(iObj, 0), Abc_Var2Lit(iObj, 1) };
544 int iFans[2] = { Gia_ObjFaninLit0(pObj, iObj), Gia_ObjFaninLit1(pObj, iObj) };
545 // add inverter
546 Vec_Int_t * vArray = Vec_WecEntry( vLit2Mono, iLits[1] );
547 Vec_IntForEachEntry( vArray, iMono, k )
548 if ( Vec_IntEntry(vCoefs, iMono) > 0 )
549 {
550 nMonos += Gia_PolynHandleOne( pHashC, pHashM, vCoefs, vLit2Mono, vTempC, vTempM, iMono, iLits[1], -1, -1 );
551 nMonos += Gia_PolynHandleOne( pHashC, pHashM, vCoefs, vLit2Mono, vTempC, vTempM, iMono, iLits[1], iLits[0], -1 );
552 Vec_IntWriteEntry( vCoefs, iMono, 0 );
553 nMonos--;
554 nBuilds++;
555 nBuilds++;
556 }
557 // add AND gate
558 vArray = Vec_WecEntry( vLit2Mono, iLits[0] );
559 Vec_IntForEachEntry( vArray, iMono, k )
560 if ( Vec_IntEntry(vCoefs, iMono) > 0 )
561 {
562 nMonos += Gia_PolynHandleOne( pHashC, pHashM, vCoefs, vLit2Mono, vTempC, vTempM, iMono, iLits[0], iFans[0], iFans[1] );
563 Vec_IntWriteEntry( vCoefs, iMono, 0 );
564 nMonos--;
565 nBuilds++;
566 }
567 //printf( "Obj %5d : nMonos = %6d nUsed = %6d\n", iObj, nBuilds, nMonos );
568 }
569
570 // complement leave nodes
571 Vec_IntForEachEntry( vLeaves, iObj, i )
572 {
573 int iLits[2] = { Abc_Var2Lit(iObj, 0), Abc_Var2Lit(iObj, 1) };
574 // add inverter
575 Vec_Int_t * vArray = Vec_WecEntry( vLit2Mono, iLits[1] );
576 Vec_IntForEachEntry( vArray, iMono, k )
577 if ( Vec_IntEntry(vCoefs, iMono) > 0 )
578 {
579 nMonos += Gia_PolynHandleOne( pHashC, pHashM, vCoefs, vLit2Mono, vTempC, vTempM, iMono, iLits[1], -1, -1 );
580 nMonos += Gia_PolynHandleOne( pHashC, pHashM, vCoefs, vLit2Mono, vTempC, vTempM, iMono, iLits[1], iLits[0], -1 );
581 Vec_IntWriteEntry( vCoefs, iMono, 0 );
582 nMonos--;
583 nBuilds++;
584 }
585 }
586
587 // get the results
588 vPolyn = Gia_PolynGetResult( pHashC, pHashM, vCoefs );
589
590 printf( "HashC = %d. HashM = %d. Total = %d. Left = %d. Used = %d. ",
591 Hsh_VecSize(pHashC), Hsh_VecSize(pHashM), nBuilds, nMonos, Vec_WecSize(vPolyn)/2 );
592 Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
593
594 Vec_IntFree( vTempC );
595 Vec_IntFree( vTempM );
596 Vec_IntFree( vCoefs );
597 Vec_WecFree( vLit2Mono );
598 Hsh_VecManStop( pHashC );
599 Hsh_VecManStop( pHashM );
600 return vPolyn;
601}
602
603
615static inline void Gia_PolynPrepare2( Vec_Int_t * vTempC[2], Vec_Int_t * vTempM[2], int iObj, int iCst )
616{
617 Vec_IntFill( vTempC[0], 1, iCst );
618 Vec_IntFill( vTempC[1], 1, -iCst );
619 Vec_IntClear( vTempM[0] );
620 Vec_IntFill( vTempM[1], 1, iObj );
621}
622static inline void Gia_PolynPrepare4( Vec_Int_t * vTempC[4], Vec_Int_t * vTempM[4], Vec_Int_t * vConst, Vec_Int_t * vMono, int iObj, int iFan0, int iFan1 )
623{
624 int i, k, Entry;
625 for ( i = 0; i < 4; i++ )
626 Vec_IntAppendMinusAbs( vTempC[i], vConst, i & 1 );
627 for ( i = 0; i < 4; i++ )
628 Vec_IntClear( vTempM[i] );
629 Vec_IntForEachEntry( vMono, Entry, k )
630 if ( Entry != iObj )
631 for ( i = 0; i < 4; i++ )
632 Vec_IntPush( vTempM[i], Entry );
633 Vec_IntPushUniqueOrder( vTempM[1], iFan0 );
634 Vec_IntPushUniqueOrder( vTempM[2], iFan1 );
635 Vec_IntPushUniqueOrder( vTempM[3], iFan0 );
636 Vec_IntPushUniqueOrder( vTempM[3], iFan1 );
637}
638
639Vec_Wec_t * Gia_PolynBuildNew( Gia_Man_t * pGia, Vec_Wec_t * vSign, Vec_Int_t * vRootLits, int nExtra, Vec_Int_t * vLeaves, Vec_Int_t * vNodes, int fSigned, int fVerbose, int fVeryVerbose )
640{
641 abctime clk = Abc_Clock();
642 Vec_Wec_t * vPolyn;
643 Vec_Wec_t * vLit2Mono = Vec_WecStart( Gia_ManObjNum(pGia) ); // mapping AIG literals into monomials
644 Hsh_VecMan_t * pHashC = Hsh_VecManStart( 1000 ); // hash table for constants
645 Hsh_VecMan_t * pHashM = Hsh_VecManStart( 1000 ); // hash table for monomials
646 Vec_Int_t * vCoefs = Vec_IntAlloc( 1000 ); // monomial coefficients
647 Vec_Int_t * vTempC[4], * vTempM[4]; // temporary array
648 int i, k, iObj, iLit, iMono, iConst, nMonos = 0, nBuilds = 0;
649 for ( i = 0; i < 4; i++ )
650 vTempC[i] = Vec_IntAlloc( 10 );
651 for ( i = 0; i < 4; i++ )
652 vTempM[i] = Vec_IntAlloc( 10 );
653
654 // add 0-constant and 1-monomial
655 Hsh_VecManAdd( pHashC, vTempC[0] );
656 Hsh_VecManAdd( pHashM, vTempM[0] );
657 Vec_IntPush( vCoefs, 0 );
658
659 if ( nExtra )
660 printf( "Assigning %d outputs from %d to %d rank %d.\n", nExtra, Vec_IntSize(vRootLits)-nExtra, Vec_IntSize(vRootLits)-1, Vec_IntSize(vRootLits)-nExtra );
661
662 // create output signature
663 if ( vSign )
664 {
665 Vec_Int_t * vLevel; int Entry, OutLit;
666 Vec_WecForEachLevel( vSign, vLevel, i )
667 {
668 OutLit = -1;
669 Vec_IntClear( vTempM[0] );
670 Vec_IntFill( vTempC[0], 1, Vec_IntEntryLast(vLevel) );
671 Vec_IntForEachEntryStop( vLevel, Entry, k, Vec_IntSize(vLevel)-1 )
672 {
673 if ( Entry < 0 ) // input
674 Vec_IntPushUniqueOrder( vTempM[0], Vec_IntEntry(vLeaves, -1-Entry) );
675 else // output
676 {
677 assert( OutLit == -1 ); // only one output literal is expected
678 OutLit = Vec_IntEntry(vRootLits, Entry);
679 }
680 }
681 if ( OutLit == -1 )
682 nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[0], vTempM[0] ); // mono without out
683 else if ( !Abc_LitIsCompl(OutLit) ) // positive literal
684 {
685 Vec_IntPushUniqueOrder( vTempM[0], Abc_Lit2Var(OutLit) );
686 nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[0], vTempM[0] ); // mono with pos out
687 }
688 else // negative literal
689 {
690 // first monomial
691 nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[0], vTempM[0] ); // mono without out
692 // second monomial
693 Vec_IntFill( vTempC[0], 1, -Vec_IntEntryLast(vLevel) );
694 Vec_IntPushUniqueOrder( vTempM[0], Abc_Lit2Var(OutLit) );
695 nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[0], vTempM[0] ); // mono with neg out
696 }
697 nBuilds++;
698 }
699 }
700 else
701 Vec_IntForEachEntry( vRootLits, iLit, i )
702 {
703 int Value = 1 + Abc_MinInt( i, Vec_IntSize(vRootLits)-nExtra );
704 Gia_PolynPrepare2( vTempC, vTempM, Abc_Lit2Var(iLit), Value );
705 if ( fSigned && i >= Vec_IntSize(vRootLits)-nExtra-1 )
706 {
707 if ( fVeryVerbose ) printf( "Out %d : Negative Value = %d\n", i, Value-1 );
708 if ( Abc_LitIsCompl(iLit) )
709 {
710 nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[1], vTempM[0] ); // -C
711 nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[0], vTempM[1] ); // C * Driver
712 nBuilds++;
713 }
714 else
715 nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[1], vTempM[1] ); // -C * Driver
716 }
717 else
718 {
719 if ( fVeryVerbose ) printf( "Out %d : Positive Value = %d\n", i, Value-1 );
720 if ( Abc_LitIsCompl(iLit) )
721 {
722 nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[0], vTempM[0] ); // C
723 nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[1], vTempM[1] ); // -C * Driver
724 nBuilds++;
725 }
726 else
727 nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[0], vTempM[1] ); // C * Driver
728 }
729 nBuilds++;
730 }
731
732 // perform construction for internal nodes
733 Vec_IntForEachEntryReverse( vNodes, iObj, i )
734 {
735 Gia_Obj_t * pObj = Gia_ManObj( pGia, iObj );
736 Vec_Int_t * vArray = Vec_WecEntry( vLit2Mono, iObj );
737 Vec_IntForEachEntry( vArray, iMono, k )
738 if ( (iConst = Vec_IntEntry(vCoefs, iMono)) > 0 )
739 {
740 Vec_Int_t * vArrayC = Hsh_VecReadEntry( pHashC, iConst );
741 Vec_Int_t * vArrayM = Hsh_VecReadEntry( pHashM, iMono );
742 Gia_PolynPrepare4( vTempC, vTempM, vArrayC, vArrayM, iObj, Gia_ObjFaninId0(pObj, iObj), Gia_ObjFaninId1(pObj, iObj) );
743 if ( Gia_ObjIsXor(pObj) )
744 {
745 }
746 else if ( Gia_ObjFaninC0(pObj) && Gia_ObjFaninC1(pObj) ) // C * (1 - x) * (1 - y)
747 {
748 nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[0], vTempM[0] ); // C * 1
749 nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[1], vTempM[1] ); // -C * x
750 nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[3], vTempM[2] ); // -C * y
751 nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[2], vTempM[3] ); // C * x * y
752 nBuilds += 3;
753 }
754 else if ( Gia_ObjFaninC0(pObj) && !Gia_ObjFaninC1(pObj) ) // C * (1 - x) * y
755 {
756 nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[0], vTempM[2] ); // C * y
757 nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[1], vTempM[3] ); // -C * x * y
758 nBuilds += 2;
759 }
760 else if ( !Gia_ObjFaninC0(pObj) && Gia_ObjFaninC1(pObj) ) // C * x * (1 - y)
761 {
762 nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[0], vTempM[1] ); // C * x
763 nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[1], vTempM[3] ); // -C * x * y
764 nBuilds++;
765 }
766 else
767 nMonos += Gia_PolynBuildAdd( pHashC, pHashM, vCoefs, vLit2Mono, vTempC[0], vTempM[3] ); // C * x * y
768 Vec_IntWriteEntry( vCoefs, iMono, 0 );
769 nMonos--;
770 nBuilds++;
771 }
772 //printf( "Obj %5d : nMonos = %6d nUsed = %6d\n", iObj, nBuilds, nMonos );
773 }
774
775 // get the results
776 vPolyn = Gia_PolynGetResult( pHashC, pHashM, vCoefs );
777
778 printf( "HashC = %d. HashM = %d. Total = %d. Left = %d. Used = %d. ",
779 Hsh_VecSize(pHashC), Hsh_VecSize(pHashM), nBuilds, nMonos, Vec_WecSize(vPolyn)/2 );
780 Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
781
782 for ( i = 0; i < 4; i++ )
783 Vec_IntFree( vTempC[i] );
784 for ( i = 0; i < 4; i++ )
785 Vec_IntFree( vTempM[i] );
786 Vec_IntFree( vCoefs );
787 Vec_WecFree( vLit2Mono );
788 Hsh_VecManStop( pHashC );
789 Hsh_VecManStop( pHashM );
790 return vPolyn;
791}
792
804void Gia_PolynBuild2Test( Gia_Man_t * pGia, char * pSign, int nExtra, int fSigned, int fVerbose, int fVeryVerbose )
805{
806 Vec_Wec_t * vPolyn;
807 Vec_Int_t * vRootLits = Vec_IntAlloc( Gia_ManCoNum(pGia) );
808 Vec_Int_t * vLeaves = Vec_IntAlloc( Gia_ManCiNum(pGia) );
809 Vec_Int_t * vNodes = Vec_IntAlloc( Gia_ManAndNum(pGia) );
810 Gia_Obj_t * pObj;
811 Vec_Wec_t * vMonos = NULL;
812 int i;
813
814 if ( pSign != NULL && (vMonos = Acec_ParseSignature(pSign)) == NULL )
815 {
816 printf( "Canont parse the output signatures.\n" );
817 return;
818 }
819 if ( vMonos && fVerbose )
820 Acec_PrintSignature( vMonos );
821
822 // print logic level
823 if ( nExtra == -1 )
824 {
825 int LevelMax = -1, iMax = -1;
826 Gia_ManLevelNum( pGia );
827 Gia_ManForEachCo( pGia, pObj, i )
828 if ( LevelMax < Gia_ObjLevel(pGia, pObj) )
829 {
830 LevelMax = Gia_ObjLevel(pGia, pObj);
831 iMax = i;
832 }
833 nExtra = Gia_ManCoNum(pGia) - iMax - 1;
834 printf( "Determined the number of extra outputs to be %d.\n", nExtra );
835 }
836
837 Gia_ManForEachObj( pGia, pObj, i )
838 if ( Gia_ObjIsCi(pObj) )
839 Vec_IntPush( vLeaves, i );
840 else if ( Gia_ObjIsAnd(pObj) )
841 Vec_IntPush( vNodes, i );
842 else if ( Gia_ObjIsCo(pObj) )
843 Vec_IntPush( vRootLits, Gia_ObjFaninLit0p(pGia, pObj) );
844
845 vPolyn = Gia_PolynBuildNew( pGia, vMonos, vRootLits, nExtra, vLeaves, vNodes, fSigned, fVerbose, fVeryVerbose );
846 //printf( "Polynomial has %d monomials.\n", Vec_WecSize(vPolyn)/2 );
847 if ( fVerbose || fVeryVerbose )
848 Gia_PolynPrintStats( vPolyn );
849 if ( fVeryVerbose )
850 Gia_PolynPrint( vPolyn );
851 Vec_WecFree( vPolyn );
852
853 Vec_IntFree( vRootLits );
854 Vec_IntFree( vLeaves );
855 Vec_IntFree( vNodes );
856 Vec_WecFreeP( &vMonos );
857}
858
862
863
864ABC_NAMESPACE_IMPL_END
865
abctime
ABC_INT64_T abctime
Definition abc_global.h:332
ABC_ALLOC
#define ABC_ALLOC(type, num)
Definition abc_global.h:264
ABC_INFINITY
#define ABC_INFINITY
MACRO DEFINITIONS ///.
Definition abc_global.h:250
ABC_FREE
#define ABC_FREE(obj)
Definition abc_global.h:267
ABC_NAMESPACE_IMPL_START
#define ABC_NAMESPACE_IMPL_START
Definition abc_namespaces.h:54
ABC_NAMESPACE_IMPL_END
#define ABC_NAMESPACE_IMPL_END
Definition abc_namespaces.h:55
Acec_ParseSignature
Vec_Wec_t * Acec_ParseSignature(char *p)
Definition acecPo.c:111
Gia_PolynGetResultCompare
int Gia_PolynGetResultCompare(int *p0, int *p1)
Definition acecPo.c:325
Acec_ParseSignatureMono
ABC_NAMESPACE_IMPL_START void Acec_ParseSignatureMono(char *p, char *pStop, Vec_Int_t *vLevel)
DECLARATIONS ///.
Definition acecPo.c:46
Gia_PolynBuildNew2
Vec_Wec_t * Gia_PolynBuildNew2(Gia_Man_t *pGia, Vec_Int_t *vRootLits, int nExtra, Vec_Int_t *vLeaves, Vec_Int_t *vNodes, int fSigned, int fVerbose, int fVeryVerbose)
Definition acecPo.c:512
Gia_PolynBuild2Test
void Gia_PolynBuild2Test(Gia_Man_t *pGia, char *pSign, int nExtra, int fSigned, int fVerbose, int fVeryVerbose)
Definition acecPo.c:804
Gia_PolynGetResult
Vec_Wec_t * Gia_PolynGetResult(Hsh_VecMan_t *pHashC, Hsh_VecMan_t *pHashM, Vec_Int_t *vCoefs)
Definition acecPo.c:331
Gia_PolynPrintMono
void Gia_PolynPrintMono(Vec_Int_t *vConst, Vec_Int_t *vMono, int Prev)
Definition acecPo.c:259
Acec_ParseSignatureTest
void Acec_ParseSignatureTest()
Definition acecPo.c:189
Acec_ParseDistribute
Vec_Wec_t * Acec_ParseDistribute(Vec_Wec_t *vM1, Vec_Wec_t *vM2, Vec_Wec_t *vAdd)
Definition acecPo.c:88
Acec_ParseSignatureOne
Vec_Wec_t * Acec_ParseSignatureOne(char *p, char *pStop)
Definition acecPo.c:72
Gia_PolynBuildNew
Vec_Wec_t * Gia_PolynBuildNew(Gia_Man_t *pGia, Vec_Wec_t *vSign, Vec_Int_t *vRootLits, int nExtra, Vec_Int_t *vLeaves, Vec_Int_t *vNodes, int fSigned, int fVerbose, int fVeryVerbose)
Definition acecPo.c:639
Acec_PrintSignature
void Acec_PrintSignature(Vec_Wec_t *vMonos)
Definition acecPo.c:171
Gia_PolynPrint
void Gia_PolynPrint(Vec_Wec_t *vPolyn)
Definition acecPo.c:269
Gia_PolynPrintStats
void Gia_PolynPrintStats(Vec_Wec_t *vPolyn)
Definition acecPo.c:282
Vec_Int_t
typedefABC_NAMESPACE_IMPL_START struct Vec_Int_t_ Vec_Int_t
DECLARATIONS ///.
Definition bblif.c:37
Len
#define Len
Definition deflate.h:78
p
Cube * p
Definition exorList.c:222
Gia_Obj_t
struct Gia_Obj_t_ Gia_Obj_t
Definition gia.h:76
Gia_Man_t
struct Gia_Man_t_ Gia_Man_t
Definition gia.h:96
Gia_ManForEachObj
#define Gia_ManForEachObj(p, pObj, i)
MACRO DEFINITIONS ///.
Definition gia.h:1190
Gia_ManForEachCo
#define Gia_ManForEachCo(p, pObj, i)
Definition gia.h:1236
Gia_ManLevelNum
int Gia_ManLevelNum(Gia_Man_t *p)
Definition giaUtil.c:546
assert
#define assert(ex)
Definition util_old.h:213
strlen
int strlen()
strstr
char * strstr()
strcpy
char * strcpy()
Hsh_VecMan_t
struct Hsh_VecMan_t_ Hsh_VecMan_t
Definition vecHsh.h:85
Vec_IntForEachEntry
#define Vec_IntForEachEntry(vVec, Entry, i)
MACRO DEFINITIONS ///.
Definition vecInt.h:54
Vec_IntForEachEntryStop
#define Vec_IntForEachEntryStop(vVec, Entry, i, Stop)
Definition vecInt.h:58
Vec_IntForEachEntryReverse
#define Vec_IntForEachEntryReverse(vVec, pEntry, i)
Definition vecInt.h:62
Vec_IntForEachEntryTriple
#define Vec_IntForEachEntryTriple(vVec, Entry1, Entry2, Entry3, i)
Definition vecInt.h:76
Vec_WecForEachLevel
#define Vec_WecForEachLevel(vGlob, vVec, i)
MACRO DEFINITIONS ///.
Definition vecWec.h:55
Vec_Wec_t
typedefABC_NAMESPACE_HEADER_START struct Vec_Wec_t_ Vec_Wec_t
INCLUDES ///.
Definition vecWec.h:42