1 /**CFile****************************************************************
2
3 FileName [abcSop.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [Network and node package.]
8
9 Synopsis [Implementation of a simple SOP representation of nodes.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: abcSop.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include "abc.h"
22 #include "bool/kit/kit.h"
23
24 ABC_NAMESPACE_IMPL_START
25
26
27 /*
28 The SOPs in this package are represented using char * strings.
29 For example, the SOP of the node:
30
31 .names c d0 d1 MUX
32 01- 1
33 1-1 1
34
35 is the string: "01- 1\n1-1 1\n" where '\n' is a single char.
36 */
37
38 ////////////////////////////////////////////////////////////////////////
39 /// DECLARATIONS ///
40 ////////////////////////////////////////////////////////////////////////
41
42 ////////////////////////////////////////////////////////////////////////
43 /// FUNCTION DEFINITIONS ///
44 ////////////////////////////////////////////////////////////////////////
45
46 /**Function*************************************************************
47
48 Synopsis [Registers the cube string with the network.]
49
50 Description []
51
52 SideEffects []
53
54 SeeAlso []
55
56 ***********************************************************************/
Abc_SopRegister(Mem_Flex_t * pMan,const char * pName)57 char * Abc_SopRegister( Mem_Flex_t * pMan, const char * pName )
58 {
59 char * pRegName;
60 if ( pName == NULL ) return NULL;
61 pRegName = Mem_FlexEntryFetch( pMan, strlen(pName) + 1 );
62 strcpy( pRegName, pName );
63 return pRegName;
64 }
65
66 /**Function*************************************************************
67
68 Synopsis [Creates the constant 1 cover with the given number of variables and cubes.]
69
70 Description []
71
72 SideEffects []
73
74 SeeAlso []
75
76 ***********************************************************************/
Abc_SopStart(Mem_Flex_t * pMan,int nCubes,int nVars)77 char * Abc_SopStart( Mem_Flex_t * pMan, int nCubes, int nVars )
78 {
79 char * pSopCover, * pCube;
80 int i, Length;
81
82 Length = nCubes * (nVars + 3);
83 pSopCover = Mem_FlexEntryFetch( pMan, Length + 1 );
84 memset( pSopCover, '-', (size_t)Length );
85 pSopCover[Length] = 0;
86
87 for ( i = 0; i < nCubes; i++ )
88 {
89 pCube = pSopCover + i * (nVars + 3);
90 pCube[nVars + 0] = ' ';
91 pCube[nVars + 1] = '1';
92 pCube[nVars + 2] = '\n';
93 }
94 return pSopCover;
95 }
96
97 /**Function*************************************************************
98
99 Synopsis [Creates the constant 1 cover with 0 variables.]
100
101 Description []
102
103 SideEffects []
104
105 SeeAlso []
106
107 ***********************************************************************/
Abc_SopCreateConst1(Mem_Flex_t * pMan)108 char * Abc_SopCreateConst1( Mem_Flex_t * pMan )
109 {
110 return Abc_SopRegister( pMan, " 1\n" );
111 }
112
113 /**Function*************************************************************
114
115 Synopsis [Creates the constant 1 cover with 0 variables.]
116
117 Description []
118
119 SideEffects []
120
121 SeeAlso []
122
123 ***********************************************************************/
Abc_SopCreateConst0(Mem_Flex_t * pMan)124 char * Abc_SopCreateConst0( Mem_Flex_t * pMan )
125 {
126 return Abc_SopRegister( pMan, " 0\n" );
127 }
128
129 /**Function*************************************************************
130
131 Synopsis [Creates the AND2 cover.]
132
133 Description []
134
135 SideEffects []
136
137 SeeAlso []
138
139 ***********************************************************************/
Abc_SopCreateAnd2(Mem_Flex_t * pMan,int fCompl0,int fCompl1)140 char * Abc_SopCreateAnd2( Mem_Flex_t * pMan, int fCompl0, int fCompl1 )
141 {
142 char Buffer[6];
143 Buffer[0] = '1' - fCompl0;
144 Buffer[1] = '1' - fCompl1;
145 Buffer[2] = ' ';
146 Buffer[3] = '1';
147 Buffer[4] = '\n';
148 Buffer[5] = 0;
149 return Abc_SopRegister( pMan, Buffer );
150 }
151
152 /**Function*************************************************************
153
154 Synopsis [Creates the multi-input AND cover.]
155
156 Description []
157
158 SideEffects []
159
160 SeeAlso []
161
162 ***********************************************************************/
Abc_SopCreateAnd(Mem_Flex_t * pMan,int nVars,int * pfCompl)163 char * Abc_SopCreateAnd( Mem_Flex_t * pMan, int nVars, int * pfCompl )
164 {
165 char * pSop;
166 int i;
167 pSop = Abc_SopStart( pMan, 1, nVars );
168 for ( i = 0; i < nVars; i++ )
169 pSop[i] = '1' - (pfCompl? pfCompl[i] : 0);
170 pSop[nVars + 1] = '1';
171 return pSop;
172 }
173
174 /**Function*************************************************************
175
176 Synopsis [Creates the multi-input NAND cover.]
177
178 Description []
179
180 SideEffects []
181
182 SeeAlso []
183
184 ***********************************************************************/
Abc_SopCreateNand(Mem_Flex_t * pMan,int nVars)185 char * Abc_SopCreateNand( Mem_Flex_t * pMan, int nVars )
186 {
187 char * pSop;
188 int i;
189 pSop = Abc_SopStart( pMan, 1, nVars );
190 for ( i = 0; i < nVars; i++ )
191 pSop[i] = '1';
192 pSop[nVars + 1] = '0';
193 return pSop;
194 }
195
196 /**Function*************************************************************
197
198 Synopsis [Creates the multi-input OR cover.]
199
200 Description []
201
202 SideEffects []
203
204 SeeAlso []
205
206 ***********************************************************************/
Abc_SopCreateOr(Mem_Flex_t * pMan,int nVars,int * pfCompl)207 char * Abc_SopCreateOr( Mem_Flex_t * pMan, int nVars, int * pfCompl )
208 {
209 char * pSop;
210 int i;
211 pSop = Abc_SopStart( pMan, 1, nVars );
212 for ( i = 0; i < nVars; i++ )
213 pSop[i] = '0' + (pfCompl? pfCompl[i] : 0);
214 pSop[nVars + 1] = '0';
215 return pSop;
216 }
217
218 /**Function*************************************************************
219
220 Synopsis [Creates the multi-input OR cover.]
221
222 Description []
223
224 SideEffects []
225
226 SeeAlso []
227
228 ***********************************************************************/
Abc_SopCreateOrMultiCube(Mem_Flex_t * pMan,int nVars,int * pfCompl)229 char * Abc_SopCreateOrMultiCube( Mem_Flex_t * pMan, int nVars, int * pfCompl )
230 {
231 char * pSop, * pCube;
232 int i;
233 pSop = Abc_SopStart( pMan, nVars, nVars );
234 i = 0;
235 Abc_SopForEachCube( pSop, nVars, pCube )
236 {
237 pCube[i] = '1' - (pfCompl? pfCompl[i] : 0);
238 i++;
239 }
240 return pSop;
241 }
242
243 /**Function*************************************************************
244
245 Synopsis [Creates the multi-input NOR cover.]
246
247 Description []
248
249 SideEffects []
250
251 SeeAlso []
252
253 ***********************************************************************/
Abc_SopCreateNor(Mem_Flex_t * pMan,int nVars)254 char * Abc_SopCreateNor( Mem_Flex_t * pMan, int nVars )
255 {
256 char * pSop;
257 int i;
258 pSop = Abc_SopStart( pMan, 1, nVars );
259 for ( i = 0; i < nVars; i++ )
260 pSop[i] = '0';
261 return pSop;
262 }
263
264 /**Function*************************************************************
265
266 Synopsis [Creates the multi-input XOR cover.]
267
268 Description []
269
270 SideEffects []
271
272 SeeAlso []
273
274 ***********************************************************************/
Abc_SopCreateXor(Mem_Flex_t * pMan,int nVars)275 char * Abc_SopCreateXor( Mem_Flex_t * pMan, int nVars )
276 {
277 assert( nVars == 2 );
278 return Abc_SopRegister(pMan, "01 1\n10 1\n");
279 }
280
281 /**Function*************************************************************
282
283 Synopsis [Creates the multi-input XOR cover (special case).]
284
285 Description []
286
287 SideEffects []
288
289 SeeAlso []
290
291 ***********************************************************************/
Abc_SopCreateXorSpecial(Mem_Flex_t * pMan,int nVars)292 char * Abc_SopCreateXorSpecial( Mem_Flex_t * pMan, int nVars )
293 {
294 char * pSop;
295 pSop = Abc_SopCreateAnd( pMan, nVars, NULL );
296 pSop[nVars+1] = 'x';
297 assert( pSop[nVars+2] == '\n' );
298 return pSop;
299 }
300
301 /**Function*************************************************************
302
303 Synopsis [Creates the multi-input XNOR cover.]
304
305 Description []
306
307 SideEffects []
308
309 SeeAlso []
310
311 ***********************************************************************/
Abc_SopCreateNxor(Mem_Flex_t * pMan,int nVars)312 char * Abc_SopCreateNxor( Mem_Flex_t * pMan, int nVars )
313 {
314 assert( nVars == 2 );
315 return Abc_SopRegister(pMan, "11 1\n00 1\n");
316 }
317
318 /**Function*************************************************************
319
320 Synopsis [Creates the MUX cover.]
321
322 Description [The first input of MUX is the control. The second input
323 is DATA1. The third input is DATA0.]
324
325 SideEffects []
326
327 SeeAlso []
328
329 ***********************************************************************/
Abc_SopCreateMux(Mem_Flex_t * pMan)330 char * Abc_SopCreateMux( Mem_Flex_t * pMan )
331 {
332 return Abc_SopRegister(pMan, "11- 1\n0-1 1\n");
333 }
334
335 /**Function*************************************************************
336
337 Synopsis [Creates the inv cover.]
338
339 Description []
340
341 SideEffects []
342
343 SeeAlso []
344
345 ***********************************************************************/
Abc_SopCreateInv(Mem_Flex_t * pMan)346 char * Abc_SopCreateInv( Mem_Flex_t * pMan )
347 {
348 return Abc_SopRegister(pMan, "0 1\n");
349 }
350
351 /**Function*************************************************************
352
353 Synopsis [Creates the buf cover.]
354
355 Description []
356
357 SideEffects []
358
359 SeeAlso []
360
361 ***********************************************************************/
Abc_SopCreateBuf(Mem_Flex_t * pMan)362 char * Abc_SopCreateBuf( Mem_Flex_t * pMan )
363 {
364 return Abc_SopRegister(pMan, "1 1\n");
365 }
366
367 /**Function*************************************************************
368
369 Synopsis [Creates the arbitrary cover from the truth table.]
370
371 Description []
372
373 SideEffects []
374
375 SeeAlso []
376
377 ***********************************************************************/
Abc_SopCreateFromTruth(Mem_Flex_t * pMan,int nVars,unsigned * pTruth)378 char * Abc_SopCreateFromTruth( Mem_Flex_t * pMan, int nVars, unsigned * pTruth )
379 {
380 char * pSop, * pCube;
381 int nMints, Counter, i, k;
382 if ( nVars == 0 )
383 return pTruth[0] ? Abc_SopCreateConst1(pMan) : Abc_SopCreateConst0(pMan);
384 // count the number of true minterms
385 Counter = 0;
386 nMints = (1 << nVars);
387 for ( i = 0; i < nMints; i++ )
388 Counter += ((pTruth[i>>5] & (1 << (i&31))) > 0);
389 // SOP is not well-defined if the truth table is constant 0
390 assert( Counter > 0 );
391 if ( Counter == 0 )
392 return NULL;
393 // start the cover
394 pSop = Abc_SopStart( pMan, Counter, nVars );
395 // create true minterms
396 Counter = 0;
397 for ( i = 0; i < nMints; i++ )
398 if ( (pTruth[i>>5] & (1 << (i&31))) > 0 )
399 {
400 pCube = pSop + Counter * (nVars + 3);
401 for ( k = 0; k < nVars; k++ )
402 pCube[k] = '0' + ((i & (1 << k)) > 0);
403 Counter++;
404 }
405 return pSop;
406 }
407
408 /**Function*************************************************************
409
410 Synopsis [Creates the cover from the ISOP computed from TT.]
411
412 Description []
413
414 SideEffects []
415
416 SeeAlso []
417
418 ***********************************************************************/
Abc_SopCreateFromIsop(Mem_Flex_t * pMan,int nVars,Vec_Int_t * vCover)419 char * Abc_SopCreateFromIsop( Mem_Flex_t * pMan, int nVars, Vec_Int_t * vCover )
420 {
421 char * pSop, * pCube;
422 int i, k, Entry, Literal;
423 assert( Vec_IntSize(vCover) > 0 );
424 if ( Vec_IntSize(vCover) == 0 )
425 return NULL;
426 // start the cover
427 pSop = Abc_SopStart( pMan, Vec_IntSize(vCover), nVars );
428 // create cubes
429 Vec_IntForEachEntry( vCover, Entry, i )
430 {
431 pCube = pSop + i * (nVars + 3);
432 for ( k = 0; k < nVars; k++ )
433 {
434 Literal = 3 & (Entry >> (k << 1));
435 if ( Literal == 1 )
436 pCube[k] = '0';
437 else if ( Literal == 2 )
438 pCube[k] = '1';
439 else if ( Literal != 0 )
440 assert( 0 );
441 }
442 }
443 return pSop;
444 }
445
446 /**Function*************************************************************
447
448 Synopsis [Creates the cover from the ISOP computed from TT.]
449
450 Description []
451
452 SideEffects []
453
454 SeeAlso []
455
456 ***********************************************************************/
Abc_SopCreateFromTruthIsop(Mem_Flex_t * pMan,int nVars,word * pTruth,Vec_Int_t * vCover)457 char * Abc_SopCreateFromTruthIsop( Mem_Flex_t * pMan, int nVars, word * pTruth, Vec_Int_t * vCover )
458 {
459 char * pSop = NULL;
460 int w, nWords = Abc_Truth6WordNum( nVars );
461 assert( nVars < 16 );
462
463 for ( w = 0; w < nWords; w++ )
464 if ( pTruth[w] )
465 break;
466 if ( w == nWords )
467 return Abc_SopRegister( pMan, " 0\n" );
468
469 for ( w = 0; w < nWords; w++ )
470 if ( ~pTruth[w] )
471 break;
472 if ( w == nWords )
473 return Abc_SopRegister( pMan, " 1\n" );
474
475 {
476 int RetValue = Kit_TruthIsop( (unsigned *)pTruth, nVars, vCover, 1 );
477 assert( nVars > 0 );
478 assert( RetValue == 0 || RetValue == 1 );
479 pSop = Abc_SopCreateFromIsop( pMan, nVars, vCover );
480 if ( RetValue )
481 Abc_SopComplement( pSop );
482 }
483 return pSop;
484 }
485
486 /**Function*************************************************************
487
488 Synopsis [Creates the cover from the ISOP computed from TT.]
489
490 Description []
491
492 SideEffects []
493
494 SeeAlso []
495
496 ***********************************************************************/
Abc_SopToIsop(char * pSop,Vec_Int_t * vCover)497 void Abc_SopToIsop( char * pSop, Vec_Int_t * vCover )
498 {
499 char * pCube;
500 int k, nVars, Entry;
501 nVars = Abc_SopGetVarNum( pSop );
502 assert( nVars > 0 );
503 // create cubes
504 Vec_IntClear( vCover );
505 for ( pCube = pSop; *pCube; pCube += nVars + 3 )
506 {
507 Entry = 0;
508 for ( k = nVars - 1; k >= 0; k-- )
509 if ( pCube[k] == '0' )
510 Entry = (Entry << 2) | 1;
511 else if ( pCube[k] == '1' )
512 Entry = (Entry << 2) | 2;
513 else if ( pCube[k] == '-' )
514 Entry = (Entry << 2);
515 else
516 assert( 0 );
517 Vec_IntPush( vCover, Entry );
518 }
519 }
520
521 /**Function*************************************************************
522
523 Synopsis [Reads the number of cubes in the cover.]
524
525 Description []
526
527 SideEffects []
528
529 SeeAlso []
530
531 ***********************************************************************/
Abc_SopGetCubeNum(char * pSop)532 int Abc_SopGetCubeNum( char * pSop )
533 {
534 char * pCur;
535 int nCubes = 0;
536 if ( pSop == NULL )
537 return 0;
538 for ( pCur = pSop; *pCur; pCur++ )
539 nCubes += (*pCur == '\n');
540 return nCubes;
541 }
542
543 /**Function*************************************************************
544
545 Synopsis [Reads the number of SOP literals in the cover.]
546
547 Description []
548
549 SideEffects []
550
551 SeeAlso []
552
553 ***********************************************************************/
Abc_SopGetLitNum(char * pSop)554 int Abc_SopGetLitNum( char * pSop )
555 {
556 char * pCur;
557 int nLits = 0;
558 if ( pSop == NULL )
559 return 0;
560 for ( pCur = pSop; *pCur; pCur++ )
561 {
562 nLits -= (*pCur == '\n');
563 nLits += (*pCur == '0' || *pCur == '1');
564 }
565 return nLits;
566 }
567
568 /**Function*************************************************************
569
570 Synopsis [Reads the number of variables in the cover.]
571
572 Description []
573
574 SideEffects []
575
576 SeeAlso []
577
578 ***********************************************************************/
Abc_SopGetVarNum(char * pSop)579 int Abc_SopGetVarNum( char * pSop )
580 {
581 char * pCur;
582 for ( pCur = pSop; *pCur != '\n'; pCur++ )
583 if ( *pCur == 0 )
584 return -1;
585 return pCur - pSop - 2;
586 }
587
588 /**Function*************************************************************
589
590 Synopsis [Reads the phase of the cover.]
591
592 Description []
593
594 SideEffects []
595
596 SeeAlso []
597
598 ***********************************************************************/
Abc_SopGetPhase(char * pSop)599 int Abc_SopGetPhase( char * pSop )
600 {
601 int nVars = Abc_SopGetVarNum( pSop );
602 if ( pSop[nVars+1] == '0' || pSop[nVars+1] == 'n' )
603 return 0;
604 if ( pSop[nVars+1] == '1' || pSop[nVars+1] == 'x' )
605 return 1;
606 assert( 0 );
607 return -1;
608 }
609
610 /**Function*************************************************************
611
612 Synopsis [Returns the i-th literal of the cover.]
613
614 Description []
615
616 SideEffects []
617
618 SeeAlso []
619
620 ***********************************************************************/
Abc_SopGetIthCareLit(char * pSop,int i)621 int Abc_SopGetIthCareLit( char * pSop, int i )
622 {
623 char * pCube;
624 int nVars;
625 nVars = Abc_SopGetVarNum( pSop );
626 Abc_SopForEachCube( pSop, nVars, pCube )
627 if ( pCube[i] != '-' )
628 return pCube[i] - '0';
629 return -1;
630 }
631
632 /**Function*************************************************************
633
634 Synopsis []
635
636 Description []
637
638 SideEffects []
639
640 SeeAlso []
641
642 ***********************************************************************/
Abc_SopComplement(char * pSop)643 void Abc_SopComplement( char * pSop )
644 {
645 char * pCur;
646 for ( pCur = pSop; *pCur; pCur++ )
647 if ( *pCur == '\n' )
648 {
649 if ( *(pCur - 1) == '0' )
650 *(pCur - 1) = '1';
651 else if ( *(pCur - 1) == '1' )
652 *(pCur - 1) = '0';
653 else if ( *(pCur - 1) == 'x' )
654 *(pCur - 1) = 'n';
655 else if ( *(pCur - 1) == 'n' )
656 *(pCur - 1) = 'x';
657 else
658 assert( 0 );
659 }
660 }
661
662 /**Function*************************************************************
663
664 Synopsis []
665
666 Description []
667
668 SideEffects []
669
670 SeeAlso []
671
672 ***********************************************************************/
Abc_SopComplementVar(char * pSop,int iVar)673 void Abc_SopComplementVar( char * pSop, int iVar )
674 {
675 char * pCube;
676 int nVars = Abc_SopGetVarNum(pSop);
677 assert( iVar < nVars );
678 Abc_SopForEachCube( pSop, nVars, pCube )
679 {
680 if ( pCube[iVar] == '0' )
681 pCube[iVar] = '1';
682 else if ( pCube[iVar] == '1' )
683 pCube[iVar] = '0';
684 }
685 }
686
687 /**Function*************************************************************
688
689 Synopsis []
690
691 Description []
692
693 SideEffects []
694
695 SeeAlso []
696
697 ***********************************************************************/
Abc_SopIsComplement(char * pSop)698 int Abc_SopIsComplement( char * pSop )
699 {
700 char * pCur;
701 for ( pCur = pSop; *pCur; pCur++ )
702 if ( *pCur == '\n' )
703 return (int)(*(pCur - 1) == '0' || *(pCur - 1) == 'n');
704 assert( 0 );
705 return 0;
706 }
707
708 /**Function*************************************************************
709
710 Synopsis [Checks if the cover is constant 0.]
711
712 Description []
713
714 SideEffects []
715
716 SeeAlso []
717
718 ***********************************************************************/
Abc_SopIsConst0(char * pSop)719 int Abc_SopIsConst0( char * pSop )
720 {
721 return pSop[0] == ' ' && pSop[1] == '0';
722 }
723
724 /**Function*************************************************************
725
726 Synopsis [Checks if the cover is constant 1.]
727
728 Description []
729
730 SideEffects []
731
732 SeeAlso []
733
734 ***********************************************************************/
Abc_SopIsConst1(char * pSop)735 int Abc_SopIsConst1( char * pSop )
736 {
737 return pSop[0] == ' ' && pSop[1] == '1';
738 }
739
740 /**Function*************************************************************
741
742 Synopsis [Checks if the cover is constant 1.]
743
744 Description []
745
746 SideEffects []
747
748 SeeAlso []
749
750 ***********************************************************************/
Abc_SopIsBuf(char * pSop)751 int Abc_SopIsBuf( char * pSop )
752 {
753 if ( pSop[4] != 0 )
754 return 0;
755 if ( (pSop[0] == '1' && pSop[2] == '1') || (pSop[0] == '0' && pSop[2] == '0') )
756 return 1;
757 return 0;
758 }
759
760 /**Function*************************************************************
761
762 Synopsis [Checks if the cover is constant 1.]
763
764 Description []
765
766 SideEffects []
767
768 SeeAlso []
769
770 ***********************************************************************/
Abc_SopIsInv(char * pSop)771 int Abc_SopIsInv( char * pSop )
772 {
773 if ( pSop[4] != 0 )
774 return 0;
775 if ( (pSop[0] == '0' && pSop[2] == '1') || (pSop[0] == '1' && pSop[2] == '0') )
776 return 1;
777 return 0;
778 }
779
780 /**Function*************************************************************
781
782 Synopsis [Checks if the cover is AND with possibly complemented inputs.]
783
784 Description []
785
786 SideEffects []
787
788 SeeAlso []
789
790 ***********************************************************************/
Abc_SopIsAndType(char * pSop)791 int Abc_SopIsAndType( char * pSop )
792 {
793 char * pCur;
794 if ( Abc_SopGetCubeNum(pSop) != 1 )
795 return 0;
796 for ( pCur = pSop; *pCur != ' '; pCur++ )
797 if ( *pCur == '-' )
798 return 0;
799 if ( pCur[1] != '1' )
800 return 0;
801 return 1;
802 }
803
804 /**Function*************************************************************
805
806 Synopsis [Checks if the cover is OR with possibly complemented inputs.]
807
808 Description []
809
810 SideEffects []
811
812 SeeAlso []
813
814 ***********************************************************************/
Abc_SopIsOrType(char * pSop)815 int Abc_SopIsOrType( char * pSop )
816 {
817 char * pCube, * pCur;
818 int nVars, nLits;
819 nVars = Abc_SopGetVarNum( pSop );
820 if ( nVars != Abc_SopGetCubeNum(pSop) )
821 return 0;
822 Abc_SopForEachCube( pSop, nVars, pCube )
823 {
824 // count the number of literals in the cube
825 nLits = 0;
826 for ( pCur = pCube; *pCur != ' '; pCur++ )
827 nLits += ( *pCur != '-' );
828 if ( nLits != 1 )
829 return 0;
830 }
831 return 1;
832 }
833
834 /**Function*************************************************************
835
836 Synopsis []
837
838 Description []
839
840 SideEffects []
841
842 SeeAlso []
843
844 ***********************************************************************/
Abc_SopIsExorType(char * pSop)845 int Abc_SopIsExorType( char * pSop )
846 {
847 char * pCur;
848 for ( pCur = pSop; *pCur; pCur++ )
849 if ( *pCur == '\n' )
850 return (int)(*(pCur - 1) == 'x' || *(pCur - 1) == 'n');
851 assert( 0 );
852 return 0;
853 }
854
855 /**Function*************************************************************
856
857 Synopsis []
858
859 Description []
860
861 SideEffects []
862
863 SeeAlso []
864
865 ***********************************************************************/
Abc_SopCheck(char * pSop,int nFanins)866 int Abc_SopCheck( char * pSop, int nFanins )
867 {
868 char * pCubes, * pCubesOld;
869 int fFound0 = 0, fFound1 = 0;
870
871 // check the logic function of the node
872 for ( pCubes = pSop; *pCubes; pCubes++ )
873 {
874 // get the end of the next cube
875 for ( pCubesOld = pCubes; *pCubes != ' '; pCubes++ );
876 // compare the distance
877 if ( pCubes - pCubesOld != nFanins )
878 {
879 fprintf( stdout, "Abc_SopCheck: SOP has a mismatch between its cover size (%d) and its fanin number (%d).\n",
880 (int)(ABC_PTRDIFF_T)(pCubes - pCubesOld), nFanins );
881 return 0;
882 }
883 // check the output values for this cube
884 pCubes++;
885 if ( *pCubes == '0' )
886 fFound0 = 1;
887 else if ( *pCubes == '1' )
888 fFound1 = 1;
889 else if ( *pCubes != 'x' && *pCubes != 'n' )
890 {
891 fprintf( stdout, "Abc_SopCheck: SOP has a strange character (%c) in the output part of its cube.\n", *pCubes );
892 return 0;
893 }
894 // check the last symbol (new line)
895 pCubes++;
896 if ( *pCubes != '\n' )
897 {
898 fprintf( stdout, "Abc_SopCheck: SOP has a cube without new line in the end.\n" );
899 return 0;
900 }
901 }
902 if ( fFound0 && fFound1 )
903 {
904 fprintf( stdout, "Abc_SopCheck: SOP has cubes in both phases.\n" );
905 return 0;
906 }
907 return 1;
908 }
909
910
911 /**Function*************************************************************
912
913 Synopsis [Derives SOP from the truth table representation.]
914
915 Description [Truth table is expected to be in the hexadecimal notation.]
916
917 SideEffects []
918
919 SeeAlso []
920
921 ***********************************************************************/
Abc_SopFromTruthBin(char * pTruth)922 char * Abc_SopFromTruthBin( char * pTruth )
923 {
924 char * pSopCover, * pCube;
925 int nTruthSize, nVars, Digit, Length, Mint, i, b;
926 Vec_Int_t * vMints;
927
928 // get the number of variables
929 nTruthSize = strlen(pTruth);
930 nVars = Abc_Base2Log( nTruthSize );
931 if ( nTruthSize != (1 << (nVars)) )
932 {
933 printf( "String %s does not look like a truth table of a %d-variable function.\n", pTruth, nVars );
934 return NULL;
935 }
936
937 // collect the on-set minterms
938 vMints = Vec_IntAlloc( 100 );
939 for ( i = 0; i < nTruthSize; i++ )
940 {
941 if ( pTruth[i] >= '0' && pTruth[i] <= '1' )
942 Digit = pTruth[i] - '0';
943 else
944 {
945 Vec_IntFree( vMints );
946 printf( "String %s does not look like a binary representation of the truth table.\n", pTruth );
947 return NULL;
948 }
949 if ( Digit == 1 )
950 Vec_IntPush( vMints, nTruthSize - 1 - i );
951 }
952 if ( Vec_IntSize( vMints ) == 0 || Vec_IntSize( vMints ) == nTruthSize )
953 {
954 Vec_IntFree( vMints );
955 printf( "Cannot create constant function.\n" );
956 return NULL;
957 }
958
959 // create the SOP representation of the minterms
960 Length = Vec_IntSize(vMints) * (nVars + 3);
961 pSopCover = ABC_ALLOC( char, Length + 1 );
962 pSopCover[Length] = 0;
963 Vec_IntForEachEntry( vMints, Mint, i )
964 {
965 pCube = pSopCover + i * (nVars + 3);
966 for ( b = 0; b < nVars; b++ )
967 if ( Mint & (1 << (nVars-1-b)) )
968 // if ( Mint & (1 << b) )
969 pCube[b] = '1';
970 else
971 pCube[b] = '0';
972 pCube[nVars + 0] = ' ';
973 pCube[nVars + 1] = '1';
974 pCube[nVars + 2] = '\n';
975 }
976 Vec_IntFree( vMints );
977 return pSopCover;
978 }
979
980 /**Function*************************************************************
981
982 Synopsis [Derives SOP from the truth table representation.]
983
984 Description [Truth table is expected to be in the hexadecimal notation.]
985
986 SideEffects []
987
988 SeeAlso []
989
990 ***********************************************************************/
Abc_SopFromTruthHex(char * pTruth)991 char * Abc_SopFromTruthHex( char * pTruth )
992 {
993 char * pSopCover, * pCube;
994 int nTruthSize, nVars, Digit, Length, Mint, i, b;
995 Vec_Int_t * vMints;
996
997 // get the number of variables
998 nTruthSize = strlen(pTruth);
999 nVars = (nTruthSize < 2) ? 2 : Abc_Base2Log(nTruthSize) + 2;
1000 if ( nTruthSize != (1 << (nVars-2)) )
1001 {
1002 printf( "String %s does not look like a truth table of a %d-variable function.\n", pTruth, nVars );
1003 return NULL;
1004 }
1005
1006 // collect the on-set minterms
1007 vMints = Vec_IntAlloc( 100 );
1008 for ( i = 0; i < nTruthSize; i++ )
1009 {
1010 if ( pTruth[i] >= '0' && pTruth[i] <= '9' )
1011 Digit = pTruth[i] - '0';
1012 else if ( pTruth[i] >= 'a' && pTruth[i] <= 'f' )
1013 Digit = 10 + pTruth[i] - 'a';
1014 else if ( pTruth[i] >= 'A' && pTruth[i] <= 'F' )
1015 Digit = 10 + pTruth[i] - 'A';
1016 else
1017 {
1018 printf( "String %s does not look like a hexadecimal representation of the truth table.\n", pTruth );
1019 return NULL;
1020 }
1021 for ( b = 0; b < 4; b++ )
1022 if ( Digit & (1 << b) )
1023 Vec_IntPush( vMints, 4*(nTruthSize-1-i)+b );
1024 }
1025
1026 // create the SOP representation of the minterms
1027 Length = Vec_IntSize(vMints) * (nVars + 3);
1028 pSopCover = ABC_ALLOC( char, Length + 1 );
1029 pSopCover[Length] = 0;
1030 Vec_IntForEachEntry( vMints, Mint, i )
1031 {
1032 pCube = pSopCover + i * (nVars + 3);
1033 for ( b = 0; b < nVars; b++ )
1034 // if ( Mint & (1 << (nVars-1-b)) )
1035 if ( Mint & (1 << b) )
1036 pCube[b] = '1';
1037 else
1038 pCube[b] = '0';
1039 pCube[nVars + 0] = ' ';
1040 pCube[nVars + 1] = '1';
1041 pCube[nVars + 2] = '\n';
1042 }
1043 /*
1044 // create TT representation
1045 {
1046 extern void Bdc_ManDecomposeTest( unsigned uTruth, int nVars );
1047 unsigned uTruth = 0;
1048 int nVarsAll = 4;
1049 assert( nVarsAll == 4 );
1050 assert( nVars <= nVarsAll );
1051 Vec_IntForEachEntry( vMints, Mint, i )
1052 uTruth |= (1 << Mint);
1053 // uTruth = uTruth | (uTruth << 8) | (uTruth << 16) | (uTruth << 24);
1054 uTruth = uTruth | (uTruth << 16);
1055 Bdc_ManDecomposeTest( uTruth, nVarsAll );
1056 }
1057 */
1058 Vec_IntFree( vMints );
1059 return pSopCover;
1060 }
1061
1062 /**Function*************************************************************
1063
1064 Synopsis [Creates one encoder node.]
1065
1066 Description [Produces MV-SOP for BLIF-MV representation.]
1067
1068 SideEffects []
1069
1070 SeeAlso []
1071
1072 ***********************************************************************/
Abc_SopEncoderPos(Mem_Flex_t * pMan,int iValue,int nValues)1073 char * Abc_SopEncoderPos( Mem_Flex_t * pMan, int iValue, int nValues )
1074 {
1075 char Buffer[32];
1076 assert( iValue < nValues );
1077 sprintf( Buffer, "d0\n%d 1\n", iValue );
1078 return Abc_SopRegister( pMan, Buffer );
1079 }
1080
1081 /**Function*************************************************************
1082
1083 Synopsis [Creates one encoder node.]
1084
1085 Description [Produces MV-SOP for BLIF-MV representation.]
1086
1087 SideEffects []
1088
1089 SeeAlso []
1090
1091 ***********************************************************************/
Abc_SopEncoderLog(Mem_Flex_t * pMan,int iBit,int nValues)1092 char * Abc_SopEncoderLog( Mem_Flex_t * pMan, int iBit, int nValues )
1093 {
1094 char * pResult;
1095 Vec_Str_t * vSop;
1096 int v, Counter, fFirst = 1, nBits = Abc_Base2Log(nValues);
1097 assert( iBit < nBits );
1098 // count the number of literals
1099 Counter = 0;
1100 for ( v = 0; v < nValues; v++ )
1101 Counter += ( (v & (1 << iBit)) > 0 );
1102 // create the cover
1103 vSop = Vec_StrAlloc( 100 );
1104 Vec_StrPrintStr( vSop, "d0\n" );
1105 if ( Counter > 1 )
1106 Vec_StrPrintStr( vSop, "(" );
1107 for ( v = 0; v < nValues; v++ )
1108 if ( v & (1 << iBit) )
1109 {
1110 if ( fFirst )
1111 fFirst = 0;
1112 else
1113 Vec_StrPush( vSop, ',' );
1114 Vec_StrPrintNum( vSop, v );
1115 }
1116 if ( Counter > 1 )
1117 Vec_StrPrintStr( vSop, ")" );
1118 Vec_StrPrintStr( vSop, " 1\n" );
1119 Vec_StrPush( vSop, 0 );
1120 pResult = Abc_SopRegister( pMan, Vec_StrArray(vSop) );
1121 Vec_StrFree( vSop );
1122 return pResult;
1123 }
1124
1125 /**Function*************************************************************
1126
1127 Synopsis [Creates the decoder node.]
1128
1129 Description [Produces MV-SOP for BLIF-MV representation.]
1130
1131 SideEffects []
1132
1133 SeeAlso []
1134
1135 ***********************************************************************/
Abc_SopDecoderPos(Mem_Flex_t * pMan,int nValues)1136 char * Abc_SopDecoderPos( Mem_Flex_t * pMan, int nValues )
1137 {
1138 char * pResult;
1139 Vec_Str_t * vSop;
1140 int i, k;
1141 assert( nValues > 1 );
1142 vSop = Vec_StrAlloc( 100 );
1143 for ( i = 0; i < nValues; i++ )
1144 {
1145 for ( k = 0; k < nValues; k++ )
1146 {
1147 if ( k == i )
1148 Vec_StrPrintStr( vSop, "1 " );
1149 else
1150 Vec_StrPrintStr( vSop, "- " );
1151 }
1152 Vec_StrPrintNum( vSop, i );
1153 Vec_StrPush( vSop, '\n' );
1154 }
1155 Vec_StrPush( vSop, 0 );
1156 pResult = Abc_SopRegister( pMan, Vec_StrArray(vSop) );
1157 Vec_StrFree( vSop );
1158 return pResult;
1159 }
1160
1161 /**Function*************************************************************
1162
1163 Synopsis [Creates the decover node.]
1164
1165 Description [Produces MV-SOP for BLIF-MV representation.]
1166
1167 SideEffects []
1168
1169 SeeAlso []
1170
1171 ***********************************************************************/
Abc_SopDecoderLog(Mem_Flex_t * pMan,int nValues)1172 char * Abc_SopDecoderLog( Mem_Flex_t * pMan, int nValues )
1173 {
1174 char * pResult;
1175 Vec_Str_t * vSop;
1176 int i, b, nBits = Abc_Base2Log(nValues);
1177 assert( nValues > 1 && nValues <= (1<<nBits) );
1178 vSop = Vec_StrAlloc( 100 );
1179 for ( i = 0; i < nValues; i++ )
1180 {
1181 for ( b = 0; b < nBits; b++ )
1182 {
1183 Vec_StrPrintNum( vSop, (int)((i & (1 << b)) > 0) );
1184 Vec_StrPush( vSop, ' ' );
1185 }
1186 Vec_StrPrintNum( vSop, i );
1187 Vec_StrPush( vSop, '\n' );
1188 }
1189 Vec_StrPush( vSop, 0 );
1190 pResult = Abc_SopRegister( pMan, Vec_StrArray(vSop) );
1191 Vec_StrFree( vSop );
1192 return pResult;
1193 }
1194
1195 /**Function*************************************************************
1196
1197 Synopsis [Computes truth table of the node.]
1198
1199 Description []
1200
1201 SideEffects []
1202
1203 SeeAlso []
1204
1205 ***********************************************************************/
Abc_SopToTruth(char * pSop,int nInputs)1206 word Abc_SopToTruth( char * pSop, int nInputs )
1207 {
1208 static word Truth[8] = {
1209 ABC_CONST(0xAAAAAAAAAAAAAAAA),
1210 ABC_CONST(0xCCCCCCCCCCCCCCCC),
1211 ABC_CONST(0xF0F0F0F0F0F0F0F0),
1212 ABC_CONST(0xFF00FF00FF00FF00),
1213 ABC_CONST(0xFFFF0000FFFF0000),
1214 ABC_CONST(0xFFFFFFFF00000000),
1215 ABC_CONST(0x0000000000000000),
1216 ABC_CONST(0xFFFFFFFFFFFFFFFF)
1217 };
1218 word Cube, Result = 0;
1219 int v, lit = 0;
1220 int nVars = Abc_SopGetVarNum(pSop);
1221 assert( nVars >= 0 && nVars <= 6 );
1222 assert( nVars == nInputs );
1223 do {
1224 Cube = Truth[7];
1225 for ( v = 0; v < nVars; v++, lit++ )
1226 {
1227 if ( pSop[lit] == '1' )
1228 Cube &= Truth[v];
1229 else if ( pSop[lit] == '0' )
1230 Cube &= ~Truth[v];
1231 else if ( pSop[lit] != '-' )
1232 assert( 0 );
1233 }
1234 Result |= Cube;
1235 assert( pSop[lit] == ' ' );
1236 lit++;
1237 lit++;
1238 assert( pSop[lit] == '\n' );
1239 lit++;
1240 } while ( pSop[lit] );
1241 if ( Abc_SopIsComplement(pSop) )
1242 Result = ~Result;
1243 return Result;
1244 }
1245
1246 /**Function*************************************************************
1247
1248 Synopsis [Computes truth table of the node.]
1249
1250 Description []
1251
1252 SideEffects []
1253
1254 SeeAlso []
1255
1256 ***********************************************************************/
Abc_SopToTruth7(char * pSop,int nInputs,word r[2])1257 void Abc_SopToTruth7( char * pSop, int nInputs, word r[2] )
1258 {
1259 static word Truth[7][2] = {
1260 {ABC_CONST(0xAAAAAAAAAAAAAAAA),ABC_CONST(0xAAAAAAAAAAAAAAAA)},
1261 {ABC_CONST(0xCCCCCCCCCCCCCCCC),ABC_CONST(0xCCCCCCCCCCCCCCCC)},
1262 {ABC_CONST(0xF0F0F0F0F0F0F0F0),ABC_CONST(0xF0F0F0F0F0F0F0F0)},
1263 {ABC_CONST(0xFF00FF00FF00FF00),ABC_CONST(0xFF00FF00FF00FF00)},
1264 {ABC_CONST(0xFFFF0000FFFF0000),ABC_CONST(0xFFFF0000FFFF0000)},
1265 {ABC_CONST(0xFFFFFFFF00000000),ABC_CONST(0xFFFFFFFF00000000)},
1266 {ABC_CONST(0x0000000000000000),ABC_CONST(0xFFFFFFFFFFFFFFFF)},
1267 };
1268 word Cube[2];
1269 int v, lit = 0;
1270 int nVars = Abc_SopGetVarNum(pSop);
1271 assert( nVars >= 0 && nVars <= 7 );
1272 assert( nVars == nInputs );
1273 r[0] = r[1] = 0;
1274 do {
1275 Cube[0] = Cube[1] = ~(word)0;
1276 for ( v = 0; v < nVars; v++, lit++ )
1277 {
1278 if ( pSop[lit] == '1' )
1279 {
1280 Cube[0] &= Truth[v][0];
1281 Cube[1] &= Truth[v][1];
1282 }
1283 else if ( pSop[lit] == '0' )
1284 {
1285 Cube[0] &= ~Truth[v][0];
1286 Cube[1] &= ~Truth[v][1];
1287 }
1288 else if ( pSop[lit] != '-' )
1289 assert( 0 );
1290 }
1291 r[0] |= Cube[0];
1292 r[1] |= Cube[1];
1293 assert( pSop[lit] == ' ' );
1294 lit++;
1295 lit++;
1296 assert( pSop[lit] == '\n' );
1297 lit++;
1298 } while ( pSop[lit] );
1299 if ( Abc_SopIsComplement(pSop) )
1300 {
1301 r[0] = ~r[0];
1302 r[1] = ~r[1];
1303 }
1304 }
1305
1306 /**Function*************************************************************
1307
1308 Synopsis [Computes truth table of the node.]
1309
1310 Description []
1311
1312 SideEffects []
1313
1314 SeeAlso []
1315
1316 ***********************************************************************/
Abc_SopToTruthBig(char * pSop,int nInputs,word ** pVars,word * pCube,word * pRes)1317 void Abc_SopToTruthBig( char * pSop, int nInputs, word ** pVars, word * pCube, word * pRes )
1318 {
1319 int nVars = Abc_SopGetVarNum(pSop);
1320 int nWords = nVars <= 6 ? 1 : 1 << (nVars-6);
1321 int v, i, lit = 0;
1322 assert( nVars >= 0 && nVars <= 16 );
1323 assert( nVars == nInputs );
1324 for ( i = 0; i < nWords; i++ )
1325 pRes[i] = 0;
1326 do {
1327 for ( i = 0; i < nWords; i++ )
1328 pCube[i] = ~(word)0;
1329 for ( v = 0; v < nVars; v++, lit++ )
1330 {
1331 if ( pSop[lit] == '1' )
1332 {
1333 for ( i = 0; i < nWords; i++ )
1334 pCube[i] &= pVars[v][i];
1335 }
1336 else if ( pSop[lit] == '0' )
1337 {
1338 for ( i = 0; i < nWords; i++ )
1339 pCube[i] &= ~pVars[v][i];
1340 }
1341 else if ( pSop[lit] != '-' )
1342 assert( 0 );
1343 }
1344 for ( i = 0; i < nWords; i++ )
1345 pRes[i] |= pCube[i];
1346 assert( pSop[lit] == ' ' );
1347 lit++;
1348 lit++;
1349 assert( pSop[lit] == '\n' );
1350 lit++;
1351 } while ( pSop[lit] );
1352 if ( Abc_SopIsComplement(pSop) )
1353 {
1354 for ( i = 0; i < nWords; i++ )
1355 pRes[i] = ~pRes[i];
1356 }
1357 }
1358
1359 ////////////////////////////////////////////////////////////////////////
1360 /// END OF FILE ///
1361 ////////////////////////////////////////////////////////////////////////
1362
1363
1364 ABC_NAMESPACE_IMPL_END
1365
1366