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