1 /**CFile****************************************************************
2
3 FileName [extraUtilMisc.c]
4
5 SystemName [ABC: Logic synthesis and verification system.]
6
7 PackageName [extra]
8
9 Synopsis [Misc procedures.]
10
11 Author [Alan Mishchenko]
12
13 Affiliation [UC Berkeley]
14
15 Date [Ver. 1.0. Started - June 20, 2005.]
16
17 Revision [$Id: extraUtilMisc.c,v 1.0 2003/09/01 00:00:00 alanmi Exp $]
18
19 ***********************************************************************/
20
21 #include <math.h>
22
23 #include "extra.h"
24 #include "misc/vec/vec.h"
25
26 ABC_NAMESPACE_IMPL_START
27
28
29 /*---------------------------------------------------------------------------*/
30 /* Constant declarations */
31 /*---------------------------------------------------------------------------*/
32
33 /*---------------------------------------------------------------------------*/
34 /* Stucture declarations */
35 /*---------------------------------------------------------------------------*/
36
37 /*---------------------------------------------------------------------------*/
38 /* Type declarations */
39 /*---------------------------------------------------------------------------*/
40
41 /*---------------------------------------------------------------------------*/
42 /* Variable declarations */
43 /*---------------------------------------------------------------------------*/
44
45 /*---------------------------------------------------------------------------*/
46 /* Macro declarations */
47 /*---------------------------------------------------------------------------*/
48
49
50 /**AutomaticStart*************************************************************/
51
52 /*---------------------------------------------------------------------------*/
53 /* Static function prototypes */
54 /*---------------------------------------------------------------------------*/
55
56 /**AutomaticEnd***************************************************************/
57
58 static void Extra_Permutations_rec( char ** pRes, int nFact, int n, char Array[] );
59
60 /*---------------------------------------------------------------------------*/
61 /* Definition of exported functions */
62 /*---------------------------------------------------------------------------*/
63
64 /**Function********************************************************************
65
66 Synopsis [Finds the smallest integer larger of equal than the logarithm.]
67
68 Description []
69
70 SideEffects []
71
72 SeeAlso []
73
74 ******************************************************************************/
Extra_Base2LogDouble(double Num)75 int Extra_Base2LogDouble( double Num )
76 {
77 double Res;
78 int ResInt;
79
80 Res = log(Num)/log(2.0);
81 ResInt = (int)Res;
82 if ( ResInt == Res )
83 return ResInt;
84 else
85 return ResInt+1;
86 }
87
88 /**Function********************************************************************
89
90 Synopsis [Returns the power of two as a double.]
91
92 Description []
93
94 SideEffects []
95
96 SeeAlso []
97
98 ******************************************************************************/
Extra_Power2(int Degree)99 double Extra_Power2( int Degree )
100 {
101 double Res;
102 assert( Degree >= 0 );
103 if ( Degree < 32 )
104 return (double)(01<<Degree);
105 for ( Res = 1.0; Degree; Res *= 2.0, Degree-- );
106 return Res;
107 }
108
109
110 /**Function*************************************************************
111
112 Synopsis []
113
114 Description []
115
116 SideEffects []
117
118 SeeAlso []
119
120 ***********************************************************************/
Extra_Power3(int Num)121 int Extra_Power3( int Num )
122 {
123 int i;
124 int Res;
125 Res = 1;
126 for ( i = 0; i < Num; i++ )
127 Res *= 3;
128 return Res;
129 }
130
131 /**Function********************************************************************
132
133 Synopsis [Finds the number of combinations of k elements out of n.]
134
135 Description []
136
137 SideEffects []
138
139 SeeAlso []
140
141 ******************************************************************************/
Extra_NumCombinations(int k,int n)142 int Extra_NumCombinations( int k, int n )
143 {
144 int i, Res = 1;
145 for ( i = 1; i <= k; i++ )
146 Res = Res * (n-i+1) / i;
147 return Res;
148 } /* end of Extra_NumCombinations */
149
150 /**Function*************************************************************
151
152 Synopsis []
153
154 Description []
155
156 SideEffects []
157
158 SeeAlso []
159
160 ***********************************************************************/
Extra_DeriveRadixCode(int Number,int Radix,int nDigits)161 int * Extra_DeriveRadixCode( int Number, int Radix, int nDigits )
162 {
163 static int Code[100];
164 int i;
165 assert( nDigits < 100 );
166 for ( i = 0; i < nDigits; i++ )
167 {
168 Code[i] = Number % Radix;
169 Number = Number / Radix;
170 }
171 assert( Number == 0 );
172 return Code;
173 }
174
175 /**Function*************************************************************
176
177 Synopsis [Counts the number of ones in the bitstring.]
178
179 Description []
180
181 SideEffects []
182
183 SeeAlso []
184
185 ***********************************************************************/
Extra_CountOnes(unsigned char * pBytes,int nBytes)186 int Extra_CountOnes( unsigned char * pBytes, int nBytes )
187 {
188 static int bit_count[256] = {
189 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,
190 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
191 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
192 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
193 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,
194 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
195 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,
196 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
197 };
198
199 int i, Counter;
200 Counter = 0;
201 for ( i = 0; i < nBytes; i++ )
202 Counter += bit_count[ *(pBytes+i) ];
203 return Counter;
204 }
205
206 /**Function********************************************************************
207
208 Synopsis [Computes the factorial.]
209
210 Description []
211
212 SideEffects []
213
214 SeeAlso []
215
216 ******************************************************************************/
Extra_Factorial(int n)217 int Extra_Factorial( int n )
218 {
219 int i, Res = 1;
220 for ( i = 1; i <= n; i++ )
221 Res *= i;
222 return Res;
223 }
224
225 /**Function********************************************************************
226
227 Synopsis [Computes the set of all permutations.]
228
229 Description [The number of permutations in the array is n!. The number of
230 entries in each permutation is n. Therefore, the resulting array is a
231 two-dimentional array of the size: n! x n. To free the resulting array,
232 call ABC_FREE() on the pointer returned by this procedure.]
233
234 SideEffects []
235
236 SeeAlso []
237
238 ******************************************************************************/
Extra_Permutations(int n)239 char ** Extra_Permutations( int n )
240 {
241 char Array[50];
242 char ** pRes;
243 int nFact, i;
244 // allocate memory
245 nFact = Extra_Factorial( n );
246 pRes = (char **)Extra_ArrayAlloc( nFact, n, sizeof(char) );
247 // fill in the permutations
248 for ( i = 0; i < n; i++ )
249 Array[i] = i;
250 Extra_Permutations_rec( pRes, nFact, n, Array );
251 // print the permutations
252 /*
253 {
254 int i, k;
255 for ( i = 0; i < nFact; i++ )
256 {
257 printf( "{" );
258 for ( k = 0; k < n; k++ )
259 printf( " %d", pRes[i][k] );
260 printf( " }\n" );
261 }
262 }
263 */
264 return pRes;
265 }
266
267 /**Function********************************************************************
268
269 Synopsis [Fills in the array of permutations.]
270
271 Description []
272
273 SideEffects []
274
275 SeeAlso []
276
277 ******************************************************************************/
Extra_Permutations_rec(char ** pRes,int nFact,int n,char Array[])278 void Extra_Permutations_rec( char ** pRes, int nFact, int n, char Array[] )
279 {
280 char ** pNext;
281 int nFactNext;
282 int iTemp, iCur, iLast, k;
283
284 if ( n == 1 )
285 {
286 pRes[0][0] = Array[0];
287 return;
288 }
289
290 // get the next factorial
291 nFactNext = nFact / n;
292 // get the last entry
293 iLast = n - 1;
294
295 for ( iCur = 0; iCur < n; iCur++ )
296 {
297 // swap Cur and Last
298 iTemp = Array[iCur];
299 Array[iCur] = Array[iLast];
300 Array[iLast] = iTemp;
301
302 // get the pointer to the current section
303 pNext = pRes + (n - 1 - iCur) * nFactNext;
304
305 // set the last entry
306 for ( k = 0; k < nFactNext; k++ )
307 pNext[k][iLast] = Array[iLast];
308
309 // call recursively for this part
310 Extra_Permutations_rec( pNext, nFactNext, n - 1, Array );
311
312 // swap them back
313 iTemp = Array[iCur];
314 Array[iCur] = Array[iLast];
315 Array[iLast] = iTemp;
316 }
317 }
318
319 /**Function*************************************************************
320
321 Synopsis [Permutes the given vector of minterms.]
322
323 Description []
324
325 SideEffects []
326
327 SeeAlso []
328
329 ***********************************************************************/
Extra_TruthPermute_int(int * pMints,int nMints,char * pPerm,int nVars,int * pMintsP)330 void Extra_TruthPermute_int( int * pMints, int nMints, char * pPerm, int nVars, int * pMintsP )
331 {
332 int m, v;
333 // clean the storage for minterms
334 memset( pMintsP, 0, sizeof(int) * nMints );
335 // go through minterms and add the variables
336 for ( m = 0; m < nMints; m++ )
337 for ( v = 0; v < nVars; v++ )
338 if ( pMints[m] & (1 << v) )
339 pMintsP[m] |= (1 << pPerm[v]);
340 }
341
342 /**Function*************************************************************
343
344 Synopsis [Permutes the function.]
345
346 Description []
347
348 SideEffects []
349
350 SeeAlso []
351
352 ***********************************************************************/
Extra_TruthPermute(unsigned Truth,char * pPerms,int nVars,int fReverse)353 unsigned Extra_TruthPermute( unsigned Truth, char * pPerms, int nVars, int fReverse )
354 {
355 unsigned Result;
356 int * pMints;
357 int * pMintsP;
358 int nMints;
359 int i, m;
360
361 assert( nVars < 6 );
362 nMints = (1 << nVars);
363 pMints = ABC_ALLOC( int, nMints );
364 pMintsP = ABC_ALLOC( int, nMints );
365 for ( i = 0; i < nMints; i++ )
366 pMints[i] = i;
367
368 Extra_TruthPermute_int( pMints, nMints, pPerms, nVars, pMintsP );
369
370 Result = 0;
371 if ( fReverse )
372 {
373 for ( m = 0; m < nMints; m++ )
374 if ( Truth & (1 << pMintsP[m]) )
375 Result |= (1 << m);
376 }
377 else
378 {
379 for ( m = 0; m < nMints; m++ )
380 if ( Truth & (1 << m) )
381 Result |= (1 << pMintsP[m]);
382 }
383
384 ABC_FREE( pMints );
385 ABC_FREE( pMintsP );
386
387 return Result;
388 }
389
390 /**Function*************************************************************
391
392 Synopsis [Changes the phase of the function.]
393
394 Description []
395
396 SideEffects []
397
398 SeeAlso []
399
400 ***********************************************************************/
Extra_TruthPolarize(unsigned uTruth,int Polarity,int nVars)401 unsigned Extra_TruthPolarize( unsigned uTruth, int Polarity, int nVars )
402 {
403 // elementary truth tables
404 static unsigned Signs[5] = {
405 0xAAAAAAAA, // 1010 1010 1010 1010 1010 1010 1010 1010
406 0xCCCCCCCC, // 1010 1010 1010 1010 1010 1010 1010 1010
407 0xF0F0F0F0, // 1111 0000 1111 0000 1111 0000 1111 0000
408 0xFF00FF00, // 1111 1111 0000 0000 1111 1111 0000 0000
409 0xFFFF0000 // 1111 1111 1111 1111 0000 0000 0000 0000
410 };
411 unsigned uTruthRes, uCof0, uCof1;
412 int nMints, Shift, v;
413 assert( nVars < 6 );
414 nMints = (1 << nVars);
415 uTruthRes = uTruth;
416 for ( v = 0; v < nVars; v++ )
417 if ( Polarity & (1 << v) )
418 {
419 uCof0 = uTruth & ~Signs[v];
420 uCof1 = uTruth & Signs[v];
421 Shift = (1 << v);
422 uCof0 <<= Shift;
423 uCof1 >>= Shift;
424 uTruth = uCof0 | uCof1;
425 }
426 return uTruth;
427 }
428
429 /**Function*************************************************************
430
431 Synopsis [Computes N-canonical form using brute-force methods.]
432
433 Description []
434
435 SideEffects []
436
437 SeeAlso []
438
439 ***********************************************************************/
Extra_TruthCanonN(unsigned uTruth,int nVars)440 unsigned Extra_TruthCanonN( unsigned uTruth, int nVars )
441 {
442 unsigned uTruthMin, uPhase;
443 int nMints, i;
444 nMints = (1 << nVars);
445 uTruthMin = 0xFFFFFFFF;
446 for ( i = 0; i < nMints; i++ )
447 {
448 uPhase = Extra_TruthPolarize( uTruth, i, nVars );
449 if ( uTruthMin > uPhase )
450 uTruthMin = uPhase;
451 }
452 return uTruthMin;
453 }
454
455 /**Function*************************************************************
456
457 Synopsis [Computes NN-canonical form using brute-force methods.]
458
459 Description []
460
461 SideEffects []
462
463 SeeAlso []
464
465 ***********************************************************************/
Extra_TruthCanonNN(unsigned uTruth,int nVars)466 unsigned Extra_TruthCanonNN( unsigned uTruth, int nVars )
467 {
468 unsigned uTruthMin, uTruthC, uPhase;
469 int nMints, i;
470 nMints = (1 << nVars);
471 uTruthC = (unsigned)( (~uTruth) & ((~((unsigned)0)) >> (32-nMints)) );
472 uTruthMin = 0xFFFFFFFF;
473 for ( i = 0; i < nMints; i++ )
474 {
475 uPhase = Extra_TruthPolarize( uTruth, i, nVars );
476 if ( uTruthMin > uPhase )
477 uTruthMin = uPhase;
478 uPhase = Extra_TruthPolarize( uTruthC, i, nVars );
479 if ( uTruthMin > uPhase )
480 uTruthMin = uPhase;
481 }
482 return uTruthMin;
483 }
484
485 /**Function*************************************************************
486
487 Synopsis [Computes P-canonical form using brute-force methods.]
488
489 Description []
490
491 SideEffects []
492
493 SeeAlso []
494
495 ***********************************************************************/
Extra_TruthCanonP(unsigned uTruth,int nVars)496 unsigned Extra_TruthCanonP( unsigned uTruth, int nVars )
497 {
498 static int nVarsOld, nPerms;
499 static char ** pPerms = NULL;
500
501 unsigned uTruthMin, uPerm;
502 int k;
503
504 if ( pPerms == NULL )
505 {
506 nPerms = Extra_Factorial( nVars );
507 pPerms = Extra_Permutations( nVars );
508 nVarsOld = nVars;
509 }
510 else if ( nVarsOld != nVars )
511 {
512 ABC_FREE( pPerms );
513 nPerms = Extra_Factorial( nVars );
514 pPerms = Extra_Permutations( nVars );
515 nVarsOld = nVars;
516 }
517
518 uTruthMin = 0xFFFFFFFF;
519 for ( k = 0; k < nPerms; k++ )
520 {
521 uPerm = Extra_TruthPermute( uTruth, pPerms[k], nVars, 0 );
522 if ( uTruthMin > uPerm )
523 uTruthMin = uPerm;
524 }
525 return uTruthMin;
526 }
527
528 /**Function*************************************************************
529
530 Synopsis [Computes NP-canonical form using brute-force methods.]
531
532 Description []
533
534 SideEffects []
535
536 SeeAlso []
537
538 ***********************************************************************/
Extra_TruthCanonNP(unsigned uTruth,int nVars)539 unsigned Extra_TruthCanonNP( unsigned uTruth, int nVars )
540 {
541 static int nVarsOld, nPerms;
542 static char ** pPerms = NULL;
543
544 unsigned uTruthMin, uPhase, uPerm;
545 int nMints, k, i;
546
547 if ( pPerms == NULL )
548 {
549 nPerms = Extra_Factorial( nVars );
550 pPerms = Extra_Permutations( nVars );
551 nVarsOld = nVars;
552 }
553 else if ( nVarsOld != nVars )
554 {
555 ABC_FREE( pPerms );
556 nPerms = Extra_Factorial( nVars );
557 pPerms = Extra_Permutations( nVars );
558 nVarsOld = nVars;
559 }
560
561 nMints = (1 << nVars);
562 uTruthMin = 0xFFFFFFFF;
563 for ( i = 0; i < nMints; i++ )
564 {
565 uPhase = Extra_TruthPolarize( uTruth, i, nVars );
566 for ( k = 0; k < nPerms; k++ )
567 {
568 uPerm = Extra_TruthPermute( uPhase, pPerms[k], nVars, 0 );
569 if ( uTruthMin > uPerm )
570 uTruthMin = uPerm;
571 }
572 }
573 return uTruthMin;
574 }
575
576 /**Function*************************************************************
577
578 Synopsis [Computes NPN-canonical form using brute-force methods.]
579
580 Description []
581
582 SideEffects []
583
584 SeeAlso []
585
586 ***********************************************************************/
Extra_TruthCanonNPN(unsigned uTruth,int nVars)587 unsigned Extra_TruthCanonNPN( unsigned uTruth, int nVars )
588 {
589 static int nVarsOld, nPerms;
590 static char ** pPerms = NULL;
591
592 unsigned uTruthMin, uTruthC, uPhase, uPerm;
593 int nMints, k, i;
594
595 if ( pPerms == NULL )
596 {
597 nPerms = Extra_Factorial( nVars );
598 pPerms = Extra_Permutations( nVars );
599 nVarsOld = nVars;
600 }
601 else if ( nVarsOld != nVars )
602 {
603 ABC_FREE( pPerms );
604 nPerms = Extra_Factorial( nVars );
605 pPerms = Extra_Permutations( nVars );
606 nVarsOld = nVars;
607 }
608
609 nMints = (1 << nVars);
610 uTruthC = (unsigned)( (~uTruth) & ((~((unsigned)0)) >> (32-nMints)) );
611 uTruthMin = 0xFFFFFFFF;
612 for ( i = 0; i < nMints; i++ )
613 {
614 uPhase = Extra_TruthPolarize( uTruth, i, nVars );
615 for ( k = 0; k < nPerms; k++ )
616 {
617 uPerm = Extra_TruthPermute( uPhase, pPerms[k], nVars, 0 );
618 if ( uTruthMin > uPerm )
619 uTruthMin = uPerm;
620 }
621 uPhase = Extra_TruthPolarize( uTruthC, i, nVars );
622 for ( k = 0; k < nPerms; k++ )
623 {
624 uPerm = Extra_TruthPermute( uPhase, pPerms[k], nVars, 0 );
625 if ( uTruthMin > uPerm )
626 uTruthMin = uPerm;
627 }
628 }
629 return uTruthMin;
630 }
631
632 /**Function*************************************************************
633
634 Synopsis [Computes NPN canonical forms for 4-variable functions.]
635
636 Description []
637
638 SideEffects []
639
640 SeeAlso []
641
642 ***********************************************************************/
Extra_Truth4VarNPN(unsigned short ** puCanons,char ** puPhases,char ** puPerms,unsigned char ** puMap)643 void Extra_Truth4VarNPN( unsigned short ** puCanons, char ** puPhases, char ** puPerms, unsigned char ** puMap )
644 {
645 unsigned short * uCanons;
646 unsigned char * uMap;
647 unsigned uTruth, uPhase, uPerm;
648 char ** pPerms4, * uPhases, * uPerms;
649 int nFuncs, nClasses;
650 int i, k;
651
652 nFuncs = (1 << 16);
653 uCanons = ABC_ALLOC( unsigned short, nFuncs );
654 uPhases = ABC_ALLOC( char, nFuncs );
655 uPerms = ABC_ALLOC( char, nFuncs );
656 uMap = ABC_ALLOC( unsigned char, nFuncs );
657 memset( uCanons, 0, sizeof(unsigned short) * nFuncs );
658 memset( uPhases, 0, sizeof(char) * nFuncs );
659 memset( uPerms, 0, sizeof(char) * nFuncs );
660 memset( uMap, 0, sizeof(unsigned char) * nFuncs );
661 pPerms4 = Extra_Permutations( 4 );
662
663 nClasses = 1;
664 nFuncs = (1 << 15);
665 for ( uTruth = 1; uTruth < (unsigned)nFuncs; uTruth++ )
666 {
667 // skip already assigned
668 if ( uCanons[uTruth] )
669 {
670 assert( uTruth > uCanons[uTruth] );
671 uMap[~uTruth & 0xFFFF] = uMap[uTruth] = uMap[uCanons[uTruth]];
672 continue;
673 }
674 uMap[uTruth] = nClasses++;
675 for ( i = 0; i < 16; i++ )
676 {
677 uPhase = Extra_TruthPolarize( uTruth, i, 4 );
678 for ( k = 0; k < 24; k++ )
679 {
680 uPerm = Extra_TruthPermute( uPhase, pPerms4[k], 4, 0 );
681 if ( uCanons[uPerm] == 0 )
682 {
683 uCanons[uPerm] = uTruth;
684 uPhases[uPerm] = i;
685 uPerms[uPerm] = k;
686
687 uPerm = ~uPerm & 0xFFFF;
688 uCanons[uPerm] = uTruth;
689 uPhases[uPerm] = i | 16;
690 uPerms[uPerm] = k;
691 }
692 else
693 assert( uCanons[uPerm] == uTruth );
694 }
695 uPhase = Extra_TruthPolarize( ~uTruth & 0xFFFF, i, 4 );
696 for ( k = 0; k < 24; k++ )
697 {
698 uPerm = Extra_TruthPermute( uPhase, pPerms4[k], 4, 0 );
699 if ( uCanons[uPerm] == 0 )
700 {
701 uCanons[uPerm] = uTruth;
702 uPhases[uPerm] = i;
703 uPerms[uPerm] = k;
704
705 uPerm = ~uPerm & 0xFFFF;
706 uCanons[uPerm] = uTruth;
707 uPhases[uPerm] = i | 16;
708 uPerms[uPerm] = k;
709 }
710 else
711 assert( uCanons[uPerm] == uTruth );
712 }
713 }
714 }
715 uPhases[(1<<16)-1] = 16;
716 assert( nClasses == 222 );
717 ABC_FREE( pPerms4 );
718 if ( puCanons )
719 *puCanons = uCanons;
720 else
721 ABC_FREE( uCanons );
722 if ( puPhases )
723 *puPhases = uPhases;
724 else
725 ABC_FREE( uPhases );
726 if ( puPerms )
727 *puPerms = uPerms;
728 else
729 ABC_FREE( uPerms );
730 if ( puMap )
731 *puMap = uMap;
732 else
733 ABC_FREE( uMap );
734 }
735
736 /**Function*************************************************************
737
738 Synopsis [Computes NPN canonical forms for 4-variable functions.]
739
740 Description []
741
742 SideEffects []
743
744 SeeAlso []
745
746 ***********************************************************************/
Extra_Truth3VarN(unsigned ** puCanons,char *** puPhases,char ** ppCounters)747 void Extra_Truth3VarN( unsigned ** puCanons, char *** puPhases, char ** ppCounters )
748 {
749 int nPhasesMax = 8;
750 unsigned * uCanons;
751 unsigned uTruth, uPhase, uTruth32;
752 char ** uPhases, * pCounters;
753 int nFuncs, nClasses, i;
754
755 nFuncs = (1 << 8);
756 uCanons = ABC_ALLOC( unsigned, nFuncs );
757 memset( uCanons, 0, sizeof(unsigned) * nFuncs );
758 pCounters = ABC_ALLOC( char, nFuncs );
759 memset( pCounters, 0, sizeof(char) * nFuncs );
760 uPhases = (char **)Extra_ArrayAlloc( nFuncs, nPhasesMax, sizeof(char) );
761 nClasses = 0;
762 for ( uTruth = 0; uTruth < (unsigned)nFuncs; uTruth++ )
763 {
764 // skip already assigned
765 uTruth32 = ((uTruth << 24) | (uTruth << 16) | (uTruth << 8) | uTruth);
766 if ( uCanons[uTruth] )
767 {
768 assert( uTruth32 > uCanons[uTruth] );
769 continue;
770 }
771 nClasses++;
772 for ( i = 0; i < 8; i++ )
773 {
774 uPhase = Extra_TruthPolarize( uTruth, i, 3 );
775 if ( uCanons[uPhase] == 0 && (uTruth || i==0) )
776 {
777 uCanons[uPhase] = uTruth32;
778 uPhases[uPhase][0] = i;
779 pCounters[uPhase] = 1;
780 }
781 else
782 {
783 assert( uCanons[uPhase] == uTruth32 );
784 if ( pCounters[uPhase] < nPhasesMax )
785 uPhases[uPhase][ (int)pCounters[uPhase]++ ] = i;
786 }
787 }
788 }
789 if ( puCanons )
790 *puCanons = uCanons;
791 else
792 ABC_FREE( uCanons );
793 if ( puPhases )
794 *puPhases = uPhases;
795 else
796 ABC_FREE( uPhases );
797 if ( ppCounters )
798 *ppCounters = pCounters;
799 else
800 ABC_FREE( pCounters );
801 // printf( "The number of 3N-classes = %d.\n", nClasses );
802 }
803
804 /**Function*************************************************************
805
806 Synopsis [Computes NPN canonical forms for 4-variable functions.]
807
808 Description []
809
810 SideEffects []
811
812 SeeAlso []
813
814 ***********************************************************************/
Extra_Truth4VarN(unsigned short ** puCanons,char *** puPhases,char ** ppCounters,int nPhasesMax)815 void Extra_Truth4VarN( unsigned short ** puCanons, char *** puPhases, char ** ppCounters, int nPhasesMax )
816 {
817 unsigned short * uCanons;
818 unsigned uTruth, uPhase;
819 char ** uPhases, * pCounters;
820 int nFuncs, nClasses, i;
821
822 nFuncs = (1 << 16);
823 uCanons = ABC_ALLOC( unsigned short, nFuncs );
824 memset( uCanons, 0, sizeof(unsigned short) * nFuncs );
825 pCounters = ABC_ALLOC( char, nFuncs );
826 memset( pCounters, 0, sizeof(char) * nFuncs );
827 uPhases = (char **)Extra_ArrayAlloc( nFuncs, nPhasesMax, sizeof(char) );
828 nClasses = 0;
829 for ( uTruth = 0; uTruth < (unsigned)nFuncs; uTruth++ )
830 {
831 // skip already assigned
832 if ( uCanons[uTruth] )
833 {
834 assert( uTruth > uCanons[uTruth] );
835 continue;
836 }
837 nClasses++;
838 for ( i = 0; i < 16; i++ )
839 {
840 uPhase = Extra_TruthPolarize( uTruth, i, 4 );
841 if ( uCanons[uPhase] == 0 && (uTruth || i==0) )
842 {
843 uCanons[uPhase] = uTruth;
844 uPhases[uPhase][0] = i;
845 pCounters[uPhase] = 1;
846 }
847 else
848 {
849 assert( uCanons[uPhase] == uTruth );
850 if ( pCounters[uPhase] < nPhasesMax )
851 uPhases[uPhase][ (int)pCounters[uPhase]++ ] = i;
852 }
853 }
854 }
855 if ( puCanons )
856 *puCanons = uCanons;
857 else
858 ABC_FREE( uCanons );
859 if ( puPhases )
860 *puPhases = uPhases;
861 else
862 ABC_FREE( uPhases );
863 if ( ppCounters )
864 *ppCounters = pCounters;
865 else
866 ABC_FREE( pCounters );
867 // printf( "The number of 4N-classes = %d.\n", nClasses );
868 }
869
870 /**Function*************************************************************
871
872 Synopsis [Allocated one-memory-chunk array.]
873
874 Description []
875
876 SideEffects []
877
878 SeeAlso []
879
880 ***********************************************************************/
Extra_ArrayAlloc(int nCols,int nRows,int Size)881 void ** Extra_ArrayAlloc( int nCols, int nRows, int Size )
882 {
883 void ** pRes;
884 char * pBuffer;
885 int i;
886 assert( nCols > 0 && nRows > 0 && Size > 0 );
887 pBuffer = ABC_ALLOC( char, nCols * (sizeof(void *) + nRows * Size) );
888 pRes = (void **)pBuffer;
889 pRes[0] = pBuffer + nCols * sizeof(void *);
890 for ( i = 1; i < nCols; i++ )
891 pRes[i] = (void *)((char *)pRes[0] + i * nRows * Size);
892 return pRes;
893 }
894
895 /**Function*************************************************************
896
897 Synopsis [Computes a phase of the 3-var function.]
898
899 Description []
900
901 SideEffects []
902
903 SeeAlso []
904
905 ***********************************************************************/
Extra_TruthPerm4One(unsigned uTruth,int Phase)906 unsigned short Extra_TruthPerm4One( unsigned uTruth, int Phase )
907 {
908 // cases
909 static unsigned short Cases[16] = {
910 0, // 0000 - skip
911 0, // 0001 - skip
912 0xCCCC, // 0010 - single var
913 0, // 0011 - skip
914 0xF0F0, // 0100 - single var
915 1, // 0101
916 1, // 0110
917 0, // 0111 - skip
918 0xFF00, // 1000 - single var
919 1, // 1001
920 1, // 1010
921 1, // 1011
922 1, // 1100
923 1, // 1101
924 1, // 1110
925 0 // 1111 - skip
926 };
927 // permutations
928 static int Perms[16][4] = {
929 { 0, 0, 0, 0 }, // 0000 - skip
930 { 0, 0, 0, 0 }, // 0001 - skip
931 { 0, 0, 0, 0 }, // 0010 - single var
932 { 0, 0, 0, 0 }, // 0011 - skip
933 { 0, 0, 0, 0 }, // 0100 - single var
934 { 0, 2, 1, 3 }, // 0101
935 { 2, 0, 1, 3 }, // 0110
936 { 0, 0, 0, 0 }, // 0111 - skip
937 { 0, 0, 0, 0 }, // 1000 - single var
938 { 0, 2, 3, 1 }, // 1001
939 { 2, 0, 3, 1 }, // 1010
940 { 0, 1, 3, 2 }, // 1011
941 { 2, 3, 0, 1 }, // 1100
942 { 0, 3, 1, 2 }, // 1101
943 { 3, 0, 1, 2 }, // 1110
944 { 0, 0, 0, 0 } // 1111 - skip
945 };
946 int i, k, iRes;
947 unsigned uTruthRes;
948 assert( Phase >= 0 && Phase < 16 );
949 if ( Cases[Phase] == 0 )
950 return uTruth;
951 if ( Cases[Phase] > 1 )
952 return Cases[Phase];
953 uTruthRes = 0;
954 for ( i = 0; i < 16; i++ )
955 if ( uTruth & (1 << i) )
956 {
957 for ( iRes = 0, k = 0; k < 4; k++ )
958 if ( i & (1 << Perms[Phase][k]) )
959 iRes |= (1 << k);
960 uTruthRes |= (1 << iRes);
961 }
962 return uTruthRes;
963 }
964
965 /**Function*************************************************************
966
967 Synopsis [Computes a phase of the 3-var function.]
968
969 Description []
970
971 SideEffects []
972
973 SeeAlso []
974
975 ***********************************************************************/
Extra_TruthPerm5One(unsigned uTruth,int Phase)976 unsigned Extra_TruthPerm5One( unsigned uTruth, int Phase )
977 {
978 // cases
979 static unsigned Cases[32] = {
980 0, // 00000 - skip
981 0, // 00001 - skip
982 0xCCCCCCCC, // 00010 - single var
983 0, // 00011 - skip
984 0xF0F0F0F0, // 00100 - single var
985 1, // 00101
986 1, // 00110
987 0, // 00111 - skip
988 0xFF00FF00, // 01000 - single var
989 1, // 01001
990 1, // 01010
991 1, // 01011
992 1, // 01100
993 1, // 01101
994 1, // 01110
995 0, // 01111 - skip
996 0xFFFF0000, // 10000 - skip
997 1, // 10001
998 1, // 10010
999 1, // 10011
1000 1, // 10100
1001 1, // 10101
1002 1, // 10110
1003 1, // 10111 - four var
1004 1, // 11000
1005 1, // 11001
1006 1, // 11010
1007 1, // 11011 - four var
1008 1, // 11100
1009 1, // 11101 - four var
1010 1, // 11110 - four var
1011 0 // 11111 - skip
1012 };
1013 // permutations
1014 static int Perms[32][5] = {
1015 { 0, 0, 0, 0, 0 }, // 00000 - skip
1016 { 0, 0, 0, 0, 0 }, // 00001 - skip
1017 { 0, 0, 0, 0, 0 }, // 00010 - single var
1018 { 0, 0, 0, 0, 0 }, // 00011 - skip
1019 { 0, 0, 0, 0, 0 }, // 00100 - single var
1020 { 0, 2, 1, 3, 4 }, // 00101
1021 { 2, 0, 1, 3, 4 }, // 00110
1022 { 0, 0, 0, 0, 0 }, // 00111 - skip
1023 { 0, 0, 0, 0, 0 }, // 01000 - single var
1024 { 0, 2, 3, 1, 4 }, // 01001
1025 { 2, 0, 3, 1, 4 }, // 01010
1026 { 0, 1, 3, 2, 4 }, // 01011
1027 { 2, 3, 0, 1, 4 }, // 01100
1028 { 0, 3, 1, 2, 4 }, // 01101
1029 { 3, 0, 1, 2, 4 }, // 01110
1030 { 0, 0, 0, 0, 0 }, // 01111 - skip
1031 { 0, 0, 0, 0, 0 }, // 10000 - single var
1032 { 0, 4, 2, 3, 1 }, // 10001
1033 { 4, 0, 2, 3, 1 }, // 10010
1034 { 0, 1, 3, 4, 2 }, // 10011
1035 { 2, 3, 0, 4, 1 }, // 10100
1036 { 0, 3, 1, 4, 2 }, // 10101
1037 { 3, 0, 1, 4, 2 }, // 10110
1038 { 0, 1, 2, 4, 3 }, // 10111 - four var
1039 { 2, 3, 4, 0, 1 }, // 11000
1040 { 0, 3, 4, 1, 2 }, // 11001
1041 { 3, 0, 4, 1, 2 }, // 11010
1042 { 0, 1, 4, 2, 3 }, // 11011 - four var
1043 { 3, 4, 0, 1, 2 }, // 11100
1044 { 0, 4, 1, 2, 3 }, // 11101 - four var
1045 { 4, 0, 1, 2, 3 }, // 11110 - four var
1046 { 0, 0, 0, 0, 0 } // 11111 - skip
1047 };
1048 int i, k, iRes;
1049 unsigned uTruthRes;
1050 assert( Phase >= 0 && Phase < 32 );
1051 if ( Cases[Phase] == 0 )
1052 return uTruth;
1053 if ( Cases[Phase] > 1 )
1054 return Cases[Phase];
1055 uTruthRes = 0;
1056 for ( i = 0; i < 32; i++ )
1057 if ( uTruth & (1 << i) )
1058 {
1059 for ( iRes = 0, k = 0; k < 5; k++ )
1060 if ( i & (1 << Perms[Phase][k]) )
1061 iRes |= (1 << k);
1062 uTruthRes |= (1 << iRes);
1063 }
1064 return uTruthRes;
1065 }
1066
1067 /**Function*************************************************************
1068
1069 Synopsis [Computes a phase of the 3-var function.]
1070
1071 Description []
1072
1073 SideEffects []
1074
1075 SeeAlso []
1076
1077 ***********************************************************************/
Extra_TruthPerm6One(unsigned * uTruth,int Phase,unsigned * uTruthRes)1078 void Extra_TruthPerm6One( unsigned * uTruth, int Phase, unsigned * uTruthRes )
1079 {
1080 // cases
1081 static unsigned Cases[64] = {
1082 0, // 000000 - skip
1083 0, // 000001 - skip
1084 0xCCCCCCCC, // 000010 - single var
1085 0, // 000011 - skip
1086 0xF0F0F0F0, // 000100 - single var
1087 1, // 000101
1088 1, // 000110
1089 0, // 000111 - skip
1090 0xFF00FF00, // 001000 - single var
1091 1, // 001001
1092 1, // 001010
1093 1, // 001011
1094 1, // 001100
1095 1, // 001101
1096 1, // 001110
1097 0, // 001111 - skip
1098 0xFFFF0000, // 010000 - skip
1099 1, // 010001
1100 1, // 010010
1101 1, // 010011
1102 1, // 010100
1103 1, // 010101
1104 1, // 010110
1105 1, // 010111 - four var
1106 1, // 011000
1107 1, // 011001
1108 1, // 011010
1109 1, // 011011 - four var
1110 1, // 011100
1111 1, // 011101 - four var
1112 1, // 011110 - four var
1113 0, // 011111 - skip
1114 0xFFFFFFFF, // 100000 - single var
1115 1, // 100001
1116 1, // 100010
1117 1, // 100011
1118 1, // 100100
1119 1, // 100101
1120 1, // 100110
1121 1, // 100111
1122 1, // 101000
1123 1, // 101001
1124 1, // 101010
1125 1, // 101011
1126 1, // 101100
1127 1, // 101101
1128 1, // 101110
1129 1, // 101111
1130 1, // 110000
1131 1, // 110001
1132 1, // 110010
1133 1, // 110011
1134 1, // 110100
1135 1, // 110101
1136 1, // 110110
1137 1, // 110111
1138 1, // 111000
1139 1, // 111001
1140 1, // 111010
1141 1, // 111011
1142 1, // 111100
1143 1, // 111101
1144 1, // 111110
1145 0 // 111111 - skip
1146 };
1147 // permutations
1148 static int Perms[64][6] = {
1149 { 0, 0, 0, 0, 0, 0 }, // 000000 - skip
1150 { 0, 0, 0, 0, 0, 0 }, // 000001 - skip
1151 { 0, 0, 0, 0, 0, 0 }, // 000010 - single var
1152 { 0, 0, 0, 0, 0, 0 }, // 000011 - skip
1153 { 0, 0, 0, 0, 0, 0 }, // 000100 - single var
1154 { 0, 2, 1, 3, 4, 5 }, // 000101
1155 { 2, 0, 1, 3, 4, 5 }, // 000110
1156 { 0, 0, 0, 0, 0, 0 }, // 000111 - skip
1157 { 0, 0, 0, 0, 0, 0 }, // 001000 - single var
1158 { 0, 2, 3, 1, 4, 5 }, // 001001
1159 { 2, 0, 3, 1, 4, 5 }, // 001010
1160 { 0, 1, 3, 2, 4, 5 }, // 001011
1161 { 2, 3, 0, 1, 4, 5 }, // 001100
1162 { 0, 3, 1, 2, 4, 5 }, // 001101
1163 { 3, 0, 1, 2, 4, 5 }, // 001110
1164 { 0, 0, 0, 0, 0, 0 }, // 001111 - skip
1165 { 0, 0, 0, 0, 0, 0 }, // 010000 - skip
1166 { 0, 4, 2, 3, 1, 5 }, // 010001
1167 { 4, 0, 2, 3, 1, 5 }, // 010010
1168 { 0, 1, 3, 4, 2, 5 }, // 010011
1169 { 2, 3, 0, 4, 1, 5 }, // 010100
1170 { 0, 3, 1, 4, 2, 5 }, // 010101
1171 { 3, 0, 1, 4, 2, 5 }, // 010110
1172 { 0, 1, 2, 4, 3, 5 }, // 010111 - four var
1173 { 2, 3, 4, 0, 1, 5 }, // 011000
1174 { 0, 3, 4, 1, 2, 5 }, // 011001
1175 { 3, 0, 4, 1, 2, 5 }, // 011010
1176 { 0, 1, 4, 2, 3, 5 }, // 011011 - four var
1177 { 3, 4, 0, 1, 2, 5 }, // 011100
1178 { 0, 4, 1, 2, 3, 5 }, // 011101 - four var
1179 { 4, 0, 1, 2, 3, 5 }, // 011110 - four var
1180 { 0, 0, 0, 0, 0, 0 }, // 011111 - skip
1181 { 0, 0, 0, 0, 0, 0 }, // 100000 - single var
1182 { 0, 2, 3, 4, 5, 1 }, // 100001
1183 { 2, 0, 3, 4, 5, 1 }, // 100010
1184 { 0, 1, 3, 4, 5, 2 }, // 100011
1185 { 2, 3, 0, 4, 5, 1 }, // 100100
1186 { 0, 3, 1, 4, 5, 2 }, // 100101
1187 { 3, 0, 1, 4, 5, 2 }, // 100110
1188 { 0, 1, 2, 4, 5, 3 }, // 100111
1189 { 2, 3, 4, 0, 5, 1 }, // 101000
1190 { 0, 3, 4, 1, 5, 2 }, // 101001
1191 { 3, 0, 4, 1, 5, 2 }, // 101010
1192 { 0, 1, 4, 2, 5, 3 }, // 101011
1193 { 3, 4, 0, 1, 5, 2 }, // 101100
1194 { 0, 4, 1, 2, 5, 3 }, // 101101
1195 { 4, 0, 1, 2, 5, 3 }, // 101110
1196 { 0, 1, 2, 3, 5, 4 }, // 101111
1197 { 2, 3, 4, 5, 0, 1 }, // 110000
1198 { 0, 3, 4, 5, 1, 2 }, // 110001
1199 { 3, 0, 4, 5, 1, 2 }, // 110010
1200 { 0, 1, 4, 5, 2, 3 }, // 110011
1201 { 3, 4, 0, 5, 1, 2 }, // 110100
1202 { 0, 4, 1, 5, 2, 3 }, // 110101
1203 { 4, 0, 1, 5, 2, 3 }, // 110110
1204 { 0, 1, 2, 5, 3, 4 }, // 110111
1205 { 3, 4, 5, 0, 1, 2 }, // 111000
1206 { 0, 4, 5, 1, 2, 3 }, // 111001
1207 { 4, 0, 5, 1, 2, 3 }, // 111010
1208 { 0, 1, 5, 2, 3, 4 }, // 111011
1209 { 4, 5, 0, 1, 2, 3 }, // 111100
1210 { 0, 5, 1, 2, 3, 4 }, // 111101
1211 { 5, 0, 1, 2, 3, 4 }, // 111110
1212 { 0, 0, 0, 0, 0, 0 } // 111111 - skip
1213 };
1214 int i, k, iRes;
1215 assert( Phase >= 0 && Phase < 64 );
1216 if ( Cases[Phase] == 0 )
1217 {
1218 uTruthRes[0] = uTruth[0];
1219 uTruthRes[1] = uTruth[1];
1220 return;
1221 }
1222 if ( Cases[Phase] > 1 )
1223 {
1224 if ( Phase == 32 )
1225 {
1226 uTruthRes[0] = 0x00000000;
1227 uTruthRes[1] = 0xFFFFFFFF;
1228 }
1229 else
1230 {
1231 uTruthRes[0] = Cases[Phase];
1232 uTruthRes[1] = Cases[Phase];
1233 }
1234 return;
1235 }
1236 uTruthRes[0] = 0;
1237 uTruthRes[1] = 0;
1238 for ( i = 0; i < 64; i++ )
1239 {
1240 if ( i < 32 )
1241 {
1242 if ( uTruth[0] & (1 << i) )
1243 {
1244 for ( iRes = 0, k = 0; k < 6; k++ )
1245 if ( i & (1 << Perms[Phase][k]) )
1246 iRes |= (1 << k);
1247 if ( iRes < 32 )
1248 uTruthRes[0] |= (1 << iRes);
1249 else
1250 uTruthRes[1] |= (1 << (iRes-32));
1251 }
1252 }
1253 else
1254 {
1255 if ( uTruth[1] & (1 << (i-32)) )
1256 {
1257 for ( iRes = 0, k = 0; k < 6; k++ )
1258 if ( i & (1 << Perms[Phase][k]) )
1259 iRes |= (1 << k);
1260 if ( iRes < 32 )
1261 uTruthRes[0] |= (1 << iRes);
1262 else
1263 uTruthRes[1] |= (1 << (iRes-32));
1264 }
1265 }
1266 }
1267 }
1268
1269 /**Function*************************************************************
1270
1271 Synopsis [Computes a phase of the 8-var function.]
1272
1273 Description []
1274
1275 SideEffects []
1276
1277 SeeAlso []
1278
1279 ***********************************************************************/
Extra_TruthExpand(int nVars,int nWords,unsigned * puTruth,unsigned uPhase,unsigned * puTruthR)1280 void Extra_TruthExpand( int nVars, int nWords, unsigned * puTruth, unsigned uPhase, unsigned * puTruthR )
1281 {
1282 // elementary truth tables
1283 static unsigned uTruths[8][8] = {
1284 { 0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA },
1285 { 0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC },
1286 { 0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0 },
1287 { 0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00 },
1288 { 0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000 },
1289 { 0x00000000,0xFFFFFFFF,0x00000000,0xFFFFFFFF,0x00000000,0xFFFFFFFF,0x00000000,0xFFFFFFFF },
1290 { 0x00000000,0x00000000,0xFFFFFFFF,0xFFFFFFFF,0x00000000,0x00000000,0xFFFFFFFF,0xFFFFFFFF },
1291 { 0x00000000,0x00000000,0x00000000,0x00000000,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF }
1292 };
1293 static char Cases[256] = {
1294 0, // 00000000
1295 0, // 00000001
1296 1, // 00000010
1297 0, // 00000011
1298 2, // 00000100
1299 -1, // 00000101
1300 -1, // 00000110
1301 0, // 00000111
1302 3, // 00001000
1303 -1, // 00001001
1304 -1, // 00001010
1305 -1, // 00001011
1306 -1, // 00001100
1307 -1, // 00001101
1308 -1, // 00001110
1309 0, // 00001111
1310 4, // 00010000
1311 -1, // 00010001
1312 -1, // 00010010
1313 -1, // 00010011
1314 -1, // 00010100
1315 -1, // 00010101
1316 -1, // 00010110
1317 -1, // 00010111
1318 -1, // 00011000
1319 -1, // 00011001
1320 -1, // 00011010
1321 -1, // 00011011
1322 -1, // 00011100
1323 -1, // 00011101
1324 -1, // 00011110
1325 0, // 00011111
1326 5, // 00100000
1327 -1, // 00100001
1328 -1, // 00100010
1329 -1, // 00100011
1330 -1, // 00100100
1331 -1, // 00100101
1332 -1, // 00100110
1333 -1, // 00100111
1334 -1, // 00101000
1335 -1, // 00101001
1336 -1, // 00101010
1337 -1, // 00101011
1338 -1, // 00101100
1339 -1, // 00101101
1340 -1, // 00101110
1341 -1, // 00101111
1342 -1, // 00110000
1343 -1, // 00110001
1344 -1, // 00110010
1345 -1, // 00110011
1346 -1, // 00110100
1347 -1, // 00110101
1348 -1, // 00110110
1349 -1, // 00110111
1350 -1, // 00111000
1351 -1, // 00111001
1352 -1, // 00111010
1353 -1, // 00111011
1354 -1, // 00111100
1355 -1, // 00111101
1356 -1, // 00111110
1357 0, // 00111111
1358 6, // 01000000
1359 -1, // 01000001
1360 -1, // 01000010
1361 -1, // 01000011
1362 -1, // 01000100
1363 -1, // 01000101
1364 -1, // 01000110
1365 -1, // 01000111
1366 -1, // 01001000
1367 -1, // 01001001
1368 -1, // 01001010
1369 -1, // 01001011
1370 -1, // 01001100
1371 -1, // 01001101
1372 -1, // 01001110
1373 -1, // 01001111
1374 -1, // 01010000
1375 -1, // 01010001
1376 -1, // 01010010
1377 -1, // 01010011
1378 -1, // 01010100
1379 -1, // 01010101
1380 -1, // 01010110
1381 -1, // 01010111
1382 -1, // 01011000
1383 -1, // 01011001
1384 -1, // 01011010
1385 -1, // 01011011
1386 -1, // 01011100
1387 -1, // 01011101
1388 -1, // 01011110
1389 -1, // 01011111
1390 -1, // 01100000
1391 -1, // 01100001
1392 -1, // 01100010
1393 -1, // 01100011
1394 -1, // 01100100
1395 -1, // 01100101
1396 -1, // 01100110
1397 -1, // 01100111
1398 -1, // 01101000
1399 -1, // 01101001
1400 -1, // 01101010
1401 -1, // 01101011
1402 -1, // 01101100
1403 -1, // 01101101
1404 -1, // 01101110
1405 -1, // 01101111
1406 -1, // 01110000
1407 -1, // 01110001
1408 -1, // 01110010
1409 -1, // 01110011
1410 -1, // 01110100
1411 -1, // 01110101
1412 -1, // 01110110
1413 -1, // 01110111
1414 -1, // 01111000
1415 -1, // 01111001
1416 -1, // 01111010
1417 -1, // 01111011
1418 -1, // 01111100
1419 -1, // 01111101
1420 -1, // 01111110
1421 0, // 01111111
1422 7, // 10000000
1423 -1, // 10000001
1424 -1, // 10000010
1425 -1, // 10000011
1426 -1, // 10000100
1427 -1, // 10000101
1428 -1, // 10000110
1429 -1, // 10000111
1430 -1, // 10001000
1431 -1, // 10001001
1432 -1, // 10001010
1433 -1, // 10001011
1434 -1, // 10001100
1435 -1, // 10001101
1436 -1, // 10001110
1437 -1, // 10001111
1438 -1, // 10010000
1439 -1, // 10010001
1440 -1, // 10010010
1441 -1, // 10010011
1442 -1, // 10010100
1443 -1, // 10010101
1444 -1, // 10010110
1445 -1, // 10010111
1446 -1, // 10011000
1447 -1, // 10011001
1448 -1, // 10011010
1449 -1, // 10011011
1450 -1, // 10011100
1451 -1, // 10011101
1452 -1, // 10011110
1453 -1, // 10011111
1454 -1, // 10100000
1455 -1, // 10100001
1456 -1, // 10100010
1457 -1, // 10100011
1458 -1, // 10100100
1459 -1, // 10100101
1460 -1, // 10100110
1461 -1, // 10100111
1462 -1, // 10101000
1463 -1, // 10101001
1464 -1, // 10101010
1465 -1, // 10101011
1466 -1, // 10101100
1467 -1, // 10101101
1468 -1, // 10101110
1469 -1, // 10101111
1470 -1, // 10110000
1471 -1, // 10110001
1472 -1, // 10110010
1473 -1, // 10110011
1474 -1, // 10110100
1475 -1, // 10110101
1476 -1, // 10110110
1477 -1, // 10110111
1478 -1, // 10111000
1479 -1, // 10111001
1480 -1, // 10111010
1481 -1, // 10111011
1482 -1, // 10111100
1483 -1, // 10111101
1484 -1, // 10111110
1485 -1, // 10111111
1486 -1, // 11000000
1487 -1, // 11000001
1488 -1, // 11000010
1489 -1, // 11000011
1490 -1, // 11000100
1491 -1, // 11000101
1492 -1, // 11000110
1493 -1, // 11000111
1494 -1, // 11001000
1495 -1, // 11001001
1496 -1, // 11001010
1497 -1, // 11001011
1498 -1, // 11001100
1499 -1, // 11001101
1500 -1, // 11001110
1501 -1, // 11001111
1502 -1, // 11010000
1503 -1, // 11010001
1504 -1, // 11010010
1505 -1, // 11010011
1506 -1, // 11010100
1507 -1, // 11010101
1508 -1, // 11010110
1509 -1, // 11010111
1510 -1, // 11011000
1511 -1, // 11011001
1512 -1, // 11011010
1513 -1, // 11011011
1514 -1, // 11011100
1515 -1, // 11011101
1516 -1, // 11011110
1517 -1, // 11011111
1518 -1, // 11100000
1519 -1, // 11100001
1520 -1, // 11100010
1521 -1, // 11100011
1522 -1, // 11100100
1523 -1, // 11100101
1524 -1, // 11100110
1525 -1, // 11100111
1526 -1, // 11101000
1527 -1, // 11101001
1528 -1, // 11101010
1529 -1, // 11101011
1530 -1, // 11101100
1531 -1, // 11101101
1532 -1, // 11101110
1533 -1, // 11101111
1534 -1, // 11110000
1535 -1, // 11110001
1536 -1, // 11110010
1537 -1, // 11110011
1538 -1, // 11110100
1539 -1, // 11110101
1540 -1, // 11110110
1541 -1, // 11110111
1542 -1, // 11111000
1543 -1, // 11111001
1544 -1, // 11111010
1545 -1, // 11111011
1546 -1, // 11111100
1547 -1, // 11111101
1548 -1, // 11111110
1549 0 // 11111111
1550 };
1551 static char Perms[256][8] = {
1552 { 0, 1, 2, 3, 4, 5, 6, 7 }, // 00000000
1553 { 0, 1, 2, 3, 4, 5, 6, 7 }, // 00000001
1554 { 1, 0, 2, 3, 4, 5, 6, 7 }, // 00000010
1555 { 0, 1, 2, 3, 4, 5, 6, 7 }, // 00000011
1556 { 1, 2, 0, 3, 4, 5, 6, 7 }, // 00000100
1557 { 0, 2, 1, 3, 4, 5, 6, 7 }, // 00000101
1558 { 2, 0, 1, 3, 4, 5, 6, 7 }, // 00000110
1559 { 0, 1, 2, 3, 4, 5, 6, 7 }, // 00000111
1560 { 1, 2, 3, 0, 4, 5, 6, 7 }, // 00001000
1561 { 0, 2, 3, 1, 4, 5, 6, 7 }, // 00001001
1562 { 2, 0, 3, 1, 4, 5, 6, 7 }, // 00001010
1563 { 0, 1, 3, 2, 4, 5, 6, 7 }, // 00001011
1564 { 2, 3, 0, 1, 4, 5, 6, 7 }, // 00001100
1565 { 0, 3, 1, 2, 4, 5, 6, 7 }, // 00001101
1566 { 3, 0, 1, 2, 4, 5, 6, 7 }, // 00001110
1567 { 0, 1, 2, 3, 4, 5, 6, 7 }, // 00001111
1568 { 1, 2, 3, 4, 0, 5, 6, 7 }, // 00010000
1569 { 0, 2, 3, 4, 1, 5, 6, 7 }, // 00010001
1570 { 2, 0, 3, 4, 1, 5, 6, 7 }, // 00010010
1571 { 0, 1, 3, 4, 2, 5, 6, 7 }, // 00010011
1572 { 2, 3, 0, 4, 1, 5, 6, 7 }, // 00010100
1573 { 0, 3, 1, 4, 2, 5, 6, 7 }, // 00010101
1574 { 3, 0, 1, 4, 2, 5, 6, 7 }, // 00010110
1575 { 0, 1, 2, 4, 3, 5, 6, 7 }, // 00010111
1576 { 2, 3, 4, 0, 1, 5, 6, 7 }, // 00011000
1577 { 0, 3, 4, 1, 2, 5, 6, 7 }, // 00011001
1578 { 3, 0, 4, 1, 2, 5, 6, 7 }, // 00011010
1579 { 0, 1, 4, 2, 3, 5, 6, 7 }, // 00011011
1580 { 3, 4, 0, 1, 2, 5, 6, 7 }, // 00011100
1581 { 0, 4, 1, 2, 3, 5, 6, 7 }, // 00011101
1582 { 4, 0, 1, 2, 3, 5, 6, 7 }, // 00011110
1583 { 0, 1, 2, 3, 4, 5, 6, 7 }, // 00011111
1584 { 1, 2, 3, 4, 5, 0, 6, 7 }, // 00100000
1585 { 0, 2, 3, 4, 5, 1, 6, 7 }, // 00100001
1586 { 2, 0, 3, 4, 5, 1, 6, 7 }, // 00100010
1587 { 0, 1, 3, 4, 5, 2, 6, 7 }, // 00100011
1588 { 2, 3, 0, 4, 5, 1, 6, 7 }, // 00100100
1589 { 0, 3, 1, 4, 5, 2, 6, 7 }, // 00100101
1590 { 3, 0, 1, 4, 5, 2, 6, 7 }, // 00100110
1591 { 0, 1, 2, 4, 5, 3, 6, 7 }, // 00100111
1592 { 2, 3, 4, 0, 5, 1, 6, 7 }, // 00101000
1593 { 0, 3, 4, 1, 5, 2, 6, 7 }, // 00101001
1594 { 3, 0, 4, 1, 5, 2, 6, 7 }, // 00101010
1595 { 0, 1, 4, 2, 5, 3, 6, 7 }, // 00101011
1596 { 3, 4, 0, 1, 5, 2, 6, 7 }, // 00101100
1597 { 0, 4, 1, 2, 5, 3, 6, 7 }, // 00101101
1598 { 4, 0, 1, 2, 5, 3, 6, 7 }, // 00101110
1599 { 0, 1, 2, 3, 5, 4, 6, 7 }, // 00101111
1600 { 2, 3, 4, 5, 0, 1, 6, 7 }, // 00110000
1601 { 0, 3, 4, 5, 1, 2, 6, 7 }, // 00110001
1602 { 3, 0, 4, 5, 1, 2, 6, 7 }, // 00110010
1603 { 0, 1, 4, 5, 2, 3, 6, 7 }, // 00110011
1604 { 3, 4, 0, 5, 1, 2, 6, 7 }, // 00110100
1605 { 0, 4, 1, 5, 2, 3, 6, 7 }, // 00110101
1606 { 4, 0, 1, 5, 2, 3, 6, 7 }, // 00110110
1607 { 0, 1, 2, 5, 3, 4, 6, 7 }, // 00110111
1608 { 3, 4, 5, 0, 1, 2, 6, 7 }, // 00111000
1609 { 0, 4, 5, 1, 2, 3, 6, 7 }, // 00111001
1610 { 4, 0, 5, 1, 2, 3, 6, 7 }, // 00111010
1611 { 0, 1, 5, 2, 3, 4, 6, 7 }, // 00111011
1612 { 4, 5, 0, 1, 2, 3, 6, 7 }, // 00111100
1613 { 0, 5, 1, 2, 3, 4, 6, 7 }, // 00111101
1614 { 5, 0, 1, 2, 3, 4, 6, 7 }, // 00111110
1615 { 0, 1, 2, 3, 4, 5, 6, 7 }, // 00111111
1616 { 1, 2, 3, 4, 5, 6, 0, 7 }, // 01000000
1617 { 0, 2, 3, 4, 5, 6, 1, 7 }, // 01000001
1618 { 2, 0, 3, 4, 5, 6, 1, 7 }, // 01000010
1619 { 0, 1, 3, 4, 5, 6, 2, 7 }, // 01000011
1620 { 2, 3, 0, 4, 5, 6, 1, 7 }, // 01000100
1621 { 0, 3, 1, 4, 5, 6, 2, 7 }, // 01000101
1622 { 3, 0, 1, 4, 5, 6, 2, 7 }, // 01000110
1623 { 0, 1, 2, 4, 5, 6, 3, 7 }, // 01000111
1624 { 2, 3, 4, 0, 5, 6, 1, 7 }, // 01001000
1625 { 0, 3, 4, 1, 5, 6, 2, 7 }, // 01001001
1626 { 3, 0, 4, 1, 5, 6, 2, 7 }, // 01001010
1627 { 0, 1, 4, 2, 5, 6, 3, 7 }, // 01001011
1628 { 3, 4, 0, 1, 5, 6, 2, 7 }, // 01001100
1629 { 0, 4, 1, 2, 5, 6, 3, 7 }, // 01001101
1630 { 4, 0, 1, 2, 5, 6, 3, 7 }, // 01001110
1631 { 0, 1, 2, 3, 5, 6, 4, 7 }, // 01001111
1632 { 2, 3, 4, 5, 0, 6, 1, 7 }, // 01010000
1633 { 0, 3, 4, 5, 1, 6, 2, 7 }, // 01010001
1634 { 3, 0, 4, 5, 1, 6, 2, 7 }, // 01010010
1635 { 0, 1, 4, 5, 2, 6, 3, 7 }, // 01010011
1636 { 3, 4, 0, 5, 1, 6, 2, 7 }, // 01010100
1637 { 0, 4, 1, 5, 2, 6, 3, 7 }, // 01010101
1638 { 4, 0, 1, 5, 2, 6, 3, 7 }, // 01010110
1639 { 0, 1, 2, 5, 3, 6, 4, 7 }, // 01010111
1640 { 3, 4, 5, 0, 1, 6, 2, 7 }, // 01011000
1641 { 0, 4, 5, 1, 2, 6, 3, 7 }, // 01011001
1642 { 4, 0, 5, 1, 2, 6, 3, 7 }, // 01011010
1643 { 0, 1, 5, 2, 3, 6, 4, 7 }, // 01011011
1644 { 4, 5, 0, 1, 2, 6, 3, 7 }, // 01011100
1645 { 0, 5, 1, 2, 3, 6, 4, 7 }, // 01011101
1646 { 5, 0, 1, 2, 3, 6, 4, 7 }, // 01011110
1647 { 0, 1, 2, 3, 4, 6, 5, 7 }, // 01011111
1648 { 2, 3, 4, 5, 6, 0, 1, 7 }, // 01100000
1649 { 0, 3, 4, 5, 6, 1, 2, 7 }, // 01100001
1650 { 3, 0, 4, 5, 6, 1, 2, 7 }, // 01100010
1651 { 0, 1, 4, 5, 6, 2, 3, 7 }, // 01100011
1652 { 3, 4, 0, 5, 6, 1, 2, 7 }, // 01100100
1653 { 0, 4, 1, 5, 6, 2, 3, 7 }, // 01100101
1654 { 4, 0, 1, 5, 6, 2, 3, 7 }, // 01100110
1655 { 0, 1, 2, 5, 6, 3, 4, 7 }, // 01100111
1656 { 3, 4, 5, 0, 6, 1, 2, 7 }, // 01101000
1657 { 0, 4, 5, 1, 6, 2, 3, 7 }, // 01101001
1658 { 4, 0, 5, 1, 6, 2, 3, 7 }, // 01101010
1659 { 0, 1, 5, 2, 6, 3, 4, 7 }, // 01101011
1660 { 4, 5, 0, 1, 6, 2, 3, 7 }, // 01101100
1661 { 0, 5, 1, 2, 6, 3, 4, 7 }, // 01101101
1662 { 5, 0, 1, 2, 6, 3, 4, 7 }, // 01101110
1663 { 0, 1, 2, 3, 6, 4, 5, 7 }, // 01101111
1664 { 3, 4, 5, 6, 0, 1, 2, 7 }, // 01110000
1665 { 0, 4, 5, 6, 1, 2, 3, 7 }, // 01110001
1666 { 4, 0, 5, 6, 1, 2, 3, 7 }, // 01110010
1667 { 0, 1, 5, 6, 2, 3, 4, 7 }, // 01110011
1668 { 4, 5, 0, 6, 1, 2, 3, 7 }, // 01110100
1669 { 0, 5, 1, 6, 2, 3, 4, 7 }, // 01110101
1670 { 5, 0, 1, 6, 2, 3, 4, 7 }, // 01110110
1671 { 0, 1, 2, 6, 3, 4, 5, 7 }, // 01110111
1672 { 4, 5, 6, 0, 1, 2, 3, 7 }, // 01111000
1673 { 0, 5, 6, 1, 2, 3, 4, 7 }, // 01111001
1674 { 5, 0, 6, 1, 2, 3, 4, 7 }, // 01111010
1675 { 0, 1, 6, 2, 3, 4, 5, 7 }, // 01111011
1676 { 5, 6, 0, 1, 2, 3, 4, 7 }, // 01111100
1677 { 0, 6, 1, 2, 3, 4, 5, 7 }, // 01111101
1678 { 6, 0, 1, 2, 3, 4, 5, 7 }, // 01111110
1679 { 0, 1, 2, 3, 4, 5, 6, 7 }, // 01111111
1680 { 1, 2, 3, 4, 5, 6, 7, 0 }, // 10000000
1681 { 0, 2, 3, 4, 5, 6, 7, 1 }, // 10000001
1682 { 2, 0, 3, 4, 5, 6, 7, 1 }, // 10000010
1683 { 0, 1, 3, 4, 5, 6, 7, 2 }, // 10000011
1684 { 2, 3, 0, 4, 5, 6, 7, 1 }, // 10000100
1685 { 0, 3, 1, 4, 5, 6, 7, 2 }, // 10000101
1686 { 3, 0, 1, 4, 5, 6, 7, 2 }, // 10000110
1687 { 0, 1, 2, 4, 5, 6, 7, 3 }, // 10000111
1688 { 2, 3, 4, 0, 5, 6, 7, 1 }, // 10001000
1689 { 0, 3, 4, 1, 5, 6, 7, 2 }, // 10001001
1690 { 3, 0, 4, 1, 5, 6, 7, 2 }, // 10001010
1691 { 0, 1, 4, 2, 5, 6, 7, 3 }, // 10001011
1692 { 3, 4, 0, 1, 5, 6, 7, 2 }, // 10001100
1693 { 0, 4, 1, 2, 5, 6, 7, 3 }, // 10001101
1694 { 4, 0, 1, 2, 5, 6, 7, 3 }, // 10001110
1695 { 0, 1, 2, 3, 5, 6, 7, 4 }, // 10001111
1696 { 2, 3, 4, 5, 0, 6, 7, 1 }, // 10010000
1697 { 0, 3, 4, 5, 1, 6, 7, 2 }, // 10010001
1698 { 3, 0, 4, 5, 1, 6, 7, 2 }, // 10010010
1699 { 0, 1, 4, 5, 2, 6, 7, 3 }, // 10010011
1700 { 3, 4, 0, 5, 1, 6, 7, 2 }, // 10010100
1701 { 0, 4, 1, 5, 2, 6, 7, 3 }, // 10010101
1702 { 4, 0, 1, 5, 2, 6, 7, 3 }, // 10010110
1703 { 0, 1, 2, 5, 3, 6, 7, 4 }, // 10010111
1704 { 3, 4, 5, 0, 1, 6, 7, 2 }, // 10011000
1705 { 0, 4, 5, 1, 2, 6, 7, 3 }, // 10011001
1706 { 4, 0, 5, 1, 2, 6, 7, 3 }, // 10011010
1707 { 0, 1, 5, 2, 3, 6, 7, 4 }, // 10011011
1708 { 4, 5, 0, 1, 2, 6, 7, 3 }, // 10011100
1709 { 0, 5, 1, 2, 3, 6, 7, 4 }, // 10011101
1710 { 5, 0, 1, 2, 3, 6, 7, 4 }, // 10011110
1711 { 0, 1, 2, 3, 4, 6, 7, 5 }, // 10011111
1712 { 2, 3, 4, 5, 6, 0, 7, 1 }, // 10100000
1713 { 0, 3, 4, 5, 6, 1, 7, 2 }, // 10100001
1714 { 3, 0, 4, 5, 6, 1, 7, 2 }, // 10100010
1715 { 0, 1, 4, 5, 6, 2, 7, 3 }, // 10100011
1716 { 3, 4, 0, 5, 6, 1, 7, 2 }, // 10100100
1717 { 0, 4, 1, 5, 6, 2, 7, 3 }, // 10100101
1718 { 4, 0, 1, 5, 6, 2, 7, 3 }, // 10100110
1719 { 0, 1, 2, 5, 6, 3, 7, 4 }, // 10100111
1720 { 3, 4, 5, 0, 6, 1, 7, 2 }, // 10101000
1721 { 0, 4, 5, 1, 6, 2, 7, 3 }, // 10101001
1722 { 4, 0, 5, 1, 6, 2, 7, 3 }, // 10101010
1723 { 0, 1, 5, 2, 6, 3, 7, 4 }, // 10101011
1724 { 4, 5, 0, 1, 6, 2, 7, 3 }, // 10101100
1725 { 0, 5, 1, 2, 6, 3, 7, 4 }, // 10101101
1726 { 5, 0, 1, 2, 6, 3, 7, 4 }, // 10101110
1727 { 0, 1, 2, 3, 6, 4, 7, 5 }, // 10101111
1728 { 3, 4, 5, 6, 0, 1, 7, 2 }, // 10110000
1729 { 0, 4, 5, 6, 1, 2, 7, 3 }, // 10110001
1730 { 4, 0, 5, 6, 1, 2, 7, 3 }, // 10110010
1731 { 0, 1, 5, 6, 2, 3, 7, 4 }, // 10110011
1732 { 4, 5, 0, 6, 1, 2, 7, 3 }, // 10110100
1733 { 0, 5, 1, 6, 2, 3, 7, 4 }, // 10110101
1734 { 5, 0, 1, 6, 2, 3, 7, 4 }, // 10110110
1735 { 0, 1, 2, 6, 3, 4, 7, 5 }, // 10110111
1736 { 4, 5, 6, 0, 1, 2, 7, 3 }, // 10111000
1737 { 0, 5, 6, 1, 2, 3, 7, 4 }, // 10111001
1738 { 5, 0, 6, 1, 2, 3, 7, 4 }, // 10111010
1739 { 0, 1, 6, 2, 3, 4, 7, 5 }, // 10111011
1740 { 5, 6, 0, 1, 2, 3, 7, 4 }, // 10111100
1741 { 0, 6, 1, 2, 3, 4, 7, 5 }, // 10111101
1742 { 6, 0, 1, 2, 3, 4, 7, 5 }, // 10111110
1743 { 0, 1, 2, 3, 4, 5, 7, 6 }, // 10111111
1744 { 2, 3, 4, 5, 6, 7, 0, 1 }, // 11000000
1745 { 0, 3, 4, 5, 6, 7, 1, 2 }, // 11000001
1746 { 3, 0, 4, 5, 6, 7, 1, 2 }, // 11000010
1747 { 0, 1, 4, 5, 6, 7, 2, 3 }, // 11000011
1748 { 3, 4, 0, 5, 6, 7, 1, 2 }, // 11000100
1749 { 0, 4, 1, 5, 6, 7, 2, 3 }, // 11000101
1750 { 4, 0, 1, 5, 6, 7, 2, 3 }, // 11000110
1751 { 0, 1, 2, 5, 6, 7, 3, 4 }, // 11000111
1752 { 3, 4, 5, 0, 6, 7, 1, 2 }, // 11001000
1753 { 0, 4, 5, 1, 6, 7, 2, 3 }, // 11001001
1754 { 4, 0, 5, 1, 6, 7, 2, 3 }, // 11001010
1755 { 0, 1, 5, 2, 6, 7, 3, 4 }, // 11001011
1756 { 4, 5, 0, 1, 6, 7, 2, 3 }, // 11001100
1757 { 0, 5, 1, 2, 6, 7, 3, 4 }, // 11001101
1758 { 5, 0, 1, 2, 6, 7, 3, 4 }, // 11001110
1759 { 0, 1, 2, 3, 6, 7, 4, 5 }, // 11001111
1760 { 3, 4, 5, 6, 0, 7, 1, 2 }, // 11010000
1761 { 0, 4, 5, 6, 1, 7, 2, 3 }, // 11010001
1762 { 4, 0, 5, 6, 1, 7, 2, 3 }, // 11010010
1763 { 0, 1, 5, 6, 2, 7, 3, 4 }, // 11010011
1764 { 4, 5, 0, 6, 1, 7, 2, 3 }, // 11010100
1765 { 0, 5, 1, 6, 2, 7, 3, 4 }, // 11010101
1766 { 5, 0, 1, 6, 2, 7, 3, 4 }, // 11010110
1767 { 0, 1, 2, 6, 3, 7, 4, 5 }, // 11010111
1768 { 4, 5, 6, 0, 1, 7, 2, 3 }, // 11011000
1769 { 0, 5, 6, 1, 2, 7, 3, 4 }, // 11011001
1770 { 5, 0, 6, 1, 2, 7, 3, 4 }, // 11011010
1771 { 0, 1, 6, 2, 3, 7, 4, 5 }, // 11011011
1772 { 5, 6, 0, 1, 2, 7, 3, 4 }, // 11011100
1773 { 0, 6, 1, 2, 3, 7, 4, 5 }, // 11011101
1774 { 6, 0, 1, 2, 3, 7, 4, 5 }, // 11011110
1775 { 0, 1, 2, 3, 4, 7, 5, 6 }, // 11011111
1776 { 3, 4, 5, 6, 7, 0, 1, 2 }, // 11100000
1777 { 0, 4, 5, 6, 7, 1, 2, 3 }, // 11100001
1778 { 4, 0, 5, 6, 7, 1, 2, 3 }, // 11100010
1779 { 0, 1, 5, 6, 7, 2, 3, 4 }, // 11100011
1780 { 4, 5, 0, 6, 7, 1, 2, 3 }, // 11100100
1781 { 0, 5, 1, 6, 7, 2, 3, 4 }, // 11100101
1782 { 5, 0, 1, 6, 7, 2, 3, 4 }, // 11100110
1783 { 0, 1, 2, 6, 7, 3, 4, 5 }, // 11100111
1784 { 4, 5, 6, 0, 7, 1, 2, 3 }, // 11101000
1785 { 0, 5, 6, 1, 7, 2, 3, 4 }, // 11101001
1786 { 5, 0, 6, 1, 7, 2, 3, 4 }, // 11101010
1787 { 0, 1, 6, 2, 7, 3, 4, 5 }, // 11101011
1788 { 5, 6, 0, 1, 7, 2, 3, 4 }, // 11101100
1789 { 0, 6, 1, 2, 7, 3, 4, 5 }, // 11101101
1790 { 6, 0, 1, 2, 7, 3, 4, 5 }, // 11101110
1791 { 0, 1, 2, 3, 7, 4, 5, 6 }, // 11101111
1792 { 4, 5, 6, 7, 0, 1, 2, 3 }, // 11110000
1793 { 0, 5, 6, 7, 1, 2, 3, 4 }, // 11110001
1794 { 5, 0, 6, 7, 1, 2, 3, 4 }, // 11110010
1795 { 0, 1, 6, 7, 2, 3, 4, 5 }, // 11110011
1796 { 5, 6, 0, 7, 1, 2, 3, 4 }, // 11110100
1797 { 0, 6, 1, 7, 2, 3, 4, 5 }, // 11110101
1798 { 6, 0, 1, 7, 2, 3, 4, 5 }, // 11110110
1799 { 0, 1, 2, 7, 3, 4, 5, 6 }, // 11110111
1800 { 5, 6, 7, 0, 1, 2, 3, 4 }, // 11111000
1801 { 0, 6, 7, 1, 2, 3, 4, 5 }, // 11111001
1802 { 6, 0, 7, 1, 2, 3, 4, 5 }, // 11111010
1803 { 0, 1, 7, 2, 3, 4, 5, 6 }, // 11111011
1804 { 6, 7, 0, 1, 2, 3, 4, 5 }, // 11111100
1805 { 0, 7, 1, 2, 3, 4, 5, 6 }, // 11111101
1806 { 7, 0, 1, 2, 3, 4, 5, 6 }, // 11111110
1807 { 0, 1, 2, 3, 4, 5, 6, 7 } // 11111111
1808 };
1809
1810 assert( uPhase > 0 && uPhase < (unsigned)(1 << nVars) );
1811
1812 // the same function
1813 if ( Cases[uPhase] == 0 )
1814 {
1815 int i;
1816 for ( i = 0; i < nWords; i++ )
1817 puTruthR[i] = puTruth[i];
1818 return;
1819 }
1820
1821 // an elementary variable
1822 if ( Cases[uPhase] > 0 )
1823 {
1824 int i;
1825 for ( i = 0; i < nWords; i++ )
1826 puTruthR[i] = uTruths[(int)Cases[uPhase]][i];
1827 return;
1828 }
1829
1830 // truth table takes one word
1831 if ( nWords == 1 )
1832 {
1833 int i, k, nMints, iRes;
1834 char * pPerm = Perms[uPhase];
1835 puTruthR[0] = 0;
1836 nMints = (1 << nVars);
1837 for ( i = 0; i < nMints; i++ )
1838 if ( puTruth[0] & (1 << i) )
1839 {
1840 for ( iRes = 0, k = 0; k < nVars; k++ )
1841 if ( i & (1 << pPerm[k]) )
1842 iRes |= (1 << k);
1843 puTruthR[0] |= (1 << iRes);
1844 }
1845 return;
1846 }
1847 else if ( nWords == 2 )
1848 {
1849 int i, k, iRes;
1850 char * pPerm = Perms[uPhase];
1851 puTruthR[0] = puTruthR[1] = 0;
1852 for ( i = 0; i < 32; i++ )
1853 {
1854 if ( puTruth[0] & (1 << i) )
1855 {
1856 for ( iRes = 0, k = 0; k < 6; k++ )
1857 if ( i & (1 << pPerm[k]) )
1858 iRes |= (1 << k);
1859 if ( iRes < 32 )
1860 puTruthR[0] |= (1 << iRes);
1861 else
1862 puTruthR[1] |= (1 << (iRes-32));
1863 }
1864 }
1865 for ( ; i < 64; i++ )
1866 {
1867 if ( puTruth[1] & (1 << (i-32)) )
1868 {
1869 for ( iRes = 0, k = 0; k < 6; k++ )
1870 if ( i & (1 << pPerm[k]) )
1871 iRes |= (1 << k);
1872 if ( iRes < 32 )
1873 puTruthR[0] |= (1 << iRes);
1874 else
1875 puTruthR[1] |= (1 << (iRes-32));
1876 }
1877 }
1878 }
1879 // truth table takes more than one word
1880 else
1881 {
1882 int i, k, nMints, iRes;
1883 char * pPerm = Perms[uPhase];
1884 for ( i = 0; i < nWords; i++ )
1885 puTruthR[i] = 0;
1886 nMints = (1 << nVars);
1887 for ( i = 0; i < nMints; i++ )
1888 if ( puTruth[i>>5] & (1 << (i&31)) )
1889 {
1890 for ( iRes = 0, k = 0; k < 5; k++ )
1891 if ( i & (1 << pPerm[k]) )
1892 iRes |= (1 << k);
1893 puTruthR[iRes>>5] |= (1 << (iRes&31));
1894 }
1895 }
1896 }
1897
1898 /**Function*************************************************************
1899
1900 Synopsis [Allocated lookup table for truth table permutation.]
1901
1902 Description []
1903
1904 SideEffects []
1905
1906 SeeAlso []
1907
1908 ***********************************************************************/
Extra_TruthPerm43()1909 unsigned short ** Extra_TruthPerm43()
1910 {
1911 unsigned short ** pTable;
1912 unsigned uTruth;
1913 int i, k;
1914 pTable = (unsigned short **)Extra_ArrayAlloc( 256, 16, 2 );
1915 for ( i = 0; i < 256; i++ )
1916 {
1917 uTruth = (i << 8) | i;
1918 for ( k = 0; k < 16; k++ )
1919 pTable[i][k] = Extra_TruthPerm4One( uTruth, k );
1920 }
1921 return pTable;
1922 }
1923
1924 /**Function*************************************************************
1925
1926 Synopsis [Allocated lookup table for truth table permutation.]
1927
1928 Description []
1929
1930 SideEffects []
1931
1932 SeeAlso []
1933
1934 ***********************************************************************/
Extra_TruthPerm53()1935 unsigned ** Extra_TruthPerm53()
1936 {
1937 unsigned ** pTable;
1938 unsigned uTruth;
1939 int i, k;
1940 pTable = (unsigned **)Extra_ArrayAlloc( 256, 32, 4 );
1941 for ( i = 0; i < 256; i++ )
1942 {
1943 uTruth = (i << 24) | (i << 16) | (i << 8) | i;
1944 for ( k = 0; k < 32; k++ )
1945 pTable[i][k] = Extra_TruthPerm5One( uTruth, k );
1946 }
1947 return pTable;
1948 }
1949
1950 /**Function*************************************************************
1951
1952 Synopsis [Allocated lookup table for truth table permutation.]
1953
1954 Description []
1955
1956 SideEffects []
1957
1958 SeeAlso []
1959
1960 ***********************************************************************/
Extra_TruthPerm54()1961 unsigned ** Extra_TruthPerm54()
1962 {
1963 unsigned ** pTable;
1964 unsigned uTruth;
1965 int i;
1966 pTable = (unsigned **)Extra_ArrayAlloc( 256*256, 4, 4 );
1967 for ( i = 0; i < 256*256; i++ )
1968 {
1969 uTruth = (i << 16) | i;
1970 pTable[i][0] = Extra_TruthPerm5One( uTruth, 31-8 );
1971 pTable[i][1] = Extra_TruthPerm5One( uTruth, 31-4 );
1972 pTable[i][2] = Extra_TruthPerm5One( uTruth, 31-2 );
1973 pTable[i][3] = Extra_TruthPerm5One( uTruth, 31-1 );
1974 }
1975 return pTable;
1976 }
1977
1978 /**Function*************************************************************
1979
1980 Synopsis [Allocated lookup table for truth table permutation.]
1981
1982 Description []
1983
1984 SideEffects []
1985
1986 SeeAlso []
1987
1988 ***********************************************************************/
Extra_TruthPerm63()1989 unsigned ** Extra_TruthPerm63()
1990 {
1991 unsigned ** pTable;
1992 unsigned uTruth[2];
1993 int i, k;
1994 pTable = (unsigned **)Extra_ArrayAlloc( 256, 64, 8 );
1995 for ( i = 0; i < 256; i++ )
1996 {
1997 uTruth[0] = (i << 24) | (i << 16) | (i << 8) | i;
1998 uTruth[1] = uTruth[0];
1999 for ( k = 0; k < 64; k++ )
2000 Extra_TruthPerm6One( uTruth, k, &pTable[i][k] );
2001 }
2002 return pTable;
2003 }
2004
2005 /**Function*************************************************************
2006
2007 Synopsis [Returns the pointer to the elementary truth tables.]
2008
2009 Description []
2010
2011 SideEffects []
2012
2013 SeeAlso []
2014
2015 ***********************************************************************/
Extra_Truths8()2016 unsigned ** Extra_Truths8()
2017 {
2018 static unsigned uTruths[8][8] = {
2019 { 0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA },
2020 { 0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC },
2021 { 0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0 },
2022 { 0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00 },
2023 { 0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000 },
2024 { 0x00000000,0xFFFFFFFF,0x00000000,0xFFFFFFFF,0x00000000,0xFFFFFFFF,0x00000000,0xFFFFFFFF },
2025 { 0x00000000,0x00000000,0xFFFFFFFF,0xFFFFFFFF,0x00000000,0x00000000,0xFFFFFFFF,0xFFFFFFFF },
2026 { 0x00000000,0x00000000,0x00000000,0x00000000,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF }
2027 };
2028 static unsigned * puResult[8] = {
2029 uTruths[0], uTruths[1], uTruths[2], uTruths[3], uTruths[4], uTruths[5], uTruths[6], uTruths[7]
2030 };
2031 return (unsigned **)puResult;
2032 }
2033
2034 /**Function*************************************************************
2035
2036 Synopsis [Bubble-sorts components by scores in increasing order.]
2037
2038 Description []
2039
2040 SideEffects []
2041
2042 SeeAlso []
2043
2044 ***********************************************************************/
Extra_BubbleSort(int Order[],int Costs[],int nSize,int fIncreasing)2045 void Extra_BubbleSort( int Order[], int Costs[], int nSize, int fIncreasing )
2046 {
2047 int i, Temp, fChanges;
2048 assert( nSize < 1000 );
2049 for ( i = 0; i < nSize; i++ )
2050 Order[i] = i;
2051 if ( fIncreasing )
2052 {
2053 do {
2054 fChanges = 0;
2055 for ( i = 0; i < nSize - 1; i++ )
2056 {
2057 if ( Costs[Order[i]] <= Costs[Order[i+1]] )
2058 continue;
2059 Temp = Order[i];
2060 Order[i] = Order[i+1];
2061 Order[i+1] = Temp;
2062 fChanges = 1;
2063 }
2064 } while ( fChanges );
2065 }
2066 else
2067 {
2068 do {
2069 fChanges = 0;
2070 for ( i = 0; i < nSize - 1; i++ )
2071 {
2072 if ( Costs[Order[i]] >= Costs[Order[i+1]] )
2073 continue;
2074 Temp = Order[i];
2075 Order[i] = Order[i+1];
2076 Order[i+1] = Temp;
2077 fChanges = 1;
2078 }
2079 } while ( fChanges );
2080 }
2081 }
2082
2083
2084 /*---------------------------------------------------------------------------*/
2085 /* Definition of internal functions */
2086 /*---------------------------------------------------------------------------*/
2087
2088 /*---------------------------------------------------------------------------*/
2089 /* Definition of static Functions */
2090 /*---------------------------------------------------------------------------*/
2091
2092
2093 /**Function*************************************************************
2094
2095 Synopsis [Computes the permutation table for 8 variables.]
2096
2097 Description []
2098
2099 SideEffects []
2100
2101 SeeAlso []
2102
2103 ***********************************************************************/
Extra_TruthExpandGeneratePermTable()2104 void Extra_TruthExpandGeneratePermTable()
2105 {
2106 int i, k, nOnes, Last1, First0;
2107 int iOne, iZero;
2108
2109 printf( "\nstatic char Cases[256] = {\n" );
2110 for ( i = 0; i < 256; i++ )
2111 {
2112 nOnes = 0;
2113 Last1 = First0 = -1;
2114 for ( k = 0; k < 8; k++ )
2115 {
2116 if ( i & (1 << k) )
2117 {
2118 nOnes++;
2119 Last1 = k;
2120 }
2121 else if ( First0 == -1 )
2122 First0 = k;
2123 }
2124 if ( Last1 + 1 == First0 || i == 255 )
2125 printf( " %d%s", 0, (i==255? " ":",") );
2126 else if ( nOnes == 1 )
2127 printf( " %d,", Last1 );
2128 else
2129 printf( " -%d,", 1 );
2130 printf( " // " );
2131 Extra_PrintBinary( stdout, (unsigned*)&i, 8 );
2132 printf( "\n" );
2133 }
2134 printf( "};\n" );
2135
2136 printf( "\nstatic char Perms[256][8] = {\n" );
2137 for ( i = 0; i < 256; i++ )
2138 {
2139 printf( " {" );
2140 nOnes = 0;
2141 for ( k = 0; k < 8; k++ )
2142 if ( i & (1 << k) )
2143 nOnes++;
2144 iOne = 0;
2145 iZero = nOnes;
2146 for ( k = 0; k < 8; k++ )
2147 if ( i & (1 << k) )
2148 printf( "%s %d", (k==0? "":","), iOne++ );
2149 else
2150 printf( "%s %d", (k==0? "":","), iZero++ );
2151 assert( iOne + iZero == 8 );
2152 printf( " }%s // ", (i==255? " ":",") );
2153 Extra_PrintBinary( stdout, (unsigned*)&i, 8 );
2154 printf( "\n" );
2155 }
2156 printf( "};\n" );
2157 }
2158
2159 /**Function*************************************************************
2160
2161 Synopsis [Computes complementation schedule for 2^n Grey codes.]
2162
2163 Description []
2164
2165 SideEffects []
2166
2167 SeeAlso []
2168
2169 ***********************************************************************/
Extra_GreyCodeSchedule(int n)2170 int * Extra_GreyCodeSchedule( int n )
2171 {
2172 int * pRes = ABC_ALLOC( int, (1<<n) );
2173 int i, k, b = 0;
2174 // pRes[b++] = -1;
2175 for ( k = 0; k < n; k++ )
2176 for ( pRes[b++] = k, i = 1; i < (1<<k); i++ )
2177 pRes[b++] = pRes[i-1]; // pRes[i];
2178 pRes[b++] = n-1;
2179 assert( b == (1<<n) );
2180
2181 if ( 0 )
2182 {
2183 unsigned uSign = 0;
2184 for ( b = 0; b < (1<<n); b++ )
2185 {
2186 uSign ^= (1 << pRes[b]);
2187 printf( "%3d %3d ", b, pRes[b] );
2188 Extra_PrintBinary( stdout, &uSign, n );
2189 printf( "\n" );
2190 }
2191 }
2192 return pRes;
2193 }
2194
2195 /**Function*************************************************************
2196
2197 Synopsis [Computes permutation schedule for n! permutations.]
2198
2199 Description []
2200
2201 SideEffects []
2202
2203 SeeAlso []
2204
2205 ***********************************************************************/
Extra_PermSchedule(int n)2206 int * Extra_PermSchedule( int n )
2207 {
2208 int nFact = Extra_Factorial(n);
2209 int nGroups = nFact / n / 2;
2210 int * pRes = ABC_ALLOC( int, nFact );
2211 int * pRes0, i, k, b = 0;
2212 assert( n > 0 );
2213 if ( n == 1 )
2214 {
2215 pRes[0] = 0;
2216 return pRes;
2217 }
2218 if ( n == 2 )
2219 {
2220 pRes[0] = pRes[1] = 0;
2221 return pRes;
2222 }
2223 pRes0 = Extra_PermSchedule( n-1 );
2224 for ( k = 0; k < nGroups; k++ )
2225 {
2226 for ( i = n-1; i > 0; i-- )
2227 pRes[b++] = i-1;
2228 pRes[b++] = pRes0[2*k]+1;
2229 for ( i = 0; i < n-1; i++ )
2230 pRes[b++] = i;
2231 pRes[b++] = pRes0[2*k+1];
2232 }
2233 ABC_FREE( pRes0 );
2234 assert( b == nFact );
2235
2236 if ( 0 )
2237 {
2238 int Perm[16];
2239 for ( i = 0; i < n; i++ )
2240 Perm[i] = i;
2241 for ( b = 0; b < nFact; b++ )
2242 {
2243 ABC_SWAP( int, Perm[pRes[b]], Perm[pRes[b]+1] );
2244 printf( "%3d %3d ", b, pRes[b] );
2245 for ( i = 0; i < n; i++ )
2246 printf( "%d", Perm[i] );
2247 printf( "\n" );
2248 }
2249 }
2250 return pRes;
2251 }
2252
2253
2254 /**Function*************************************************************
2255
2256 Synopsis [Finds minimum form of a 6-input function.]
2257
2258 Description []
2259
2260 SideEffects []
2261
2262 SeeAlso []
2263
2264 ***********************************************************************/
Extra_Truth6SwapAdjacent(word t,int v)2265 static inline word Extra_Truth6SwapAdjacent( word t, int v )
2266 {
2267 // variable swapping code
2268 static word PMasks[5][3] = {
2269 { ABC_CONST(0x9999999999999999), ABC_CONST(0x2222222222222222), ABC_CONST(0x4444444444444444) },
2270 { ABC_CONST(0xC3C3C3C3C3C3C3C3), ABC_CONST(0x0C0C0C0C0C0C0C0C), ABC_CONST(0x3030303030303030) },
2271 { ABC_CONST(0xF00FF00FF00FF00F), ABC_CONST(0x00F000F000F000F0), ABC_CONST(0x0F000F000F000F00) },
2272 { ABC_CONST(0xFF0000FFFF0000FF), ABC_CONST(0x0000FF000000FF00), ABC_CONST(0x00FF000000FF0000) },
2273 { ABC_CONST(0xFFFF00000000FFFF), ABC_CONST(0x00000000FFFF0000), ABC_CONST(0x0000FFFF00000000) }
2274 };
2275 assert( v < 5 );
2276 return (t & PMasks[v][0]) | ((t & PMasks[v][1]) << (1 << v)) | ((t & PMasks[v][2]) >> (1 << v));
2277 }
Extra_Truth6ChangePhase(word t,int v)2278 static inline word Extra_Truth6ChangePhase( word t, int v )
2279 {
2280 // elementary truth tables
2281 static word Truth6[6] = {
2282 ABC_CONST(0xAAAAAAAAAAAAAAAA),
2283 ABC_CONST(0xCCCCCCCCCCCCCCCC),
2284 ABC_CONST(0xF0F0F0F0F0F0F0F0),
2285 ABC_CONST(0xFF00FF00FF00FF00),
2286 ABC_CONST(0xFFFF0000FFFF0000),
2287 ABC_CONST(0xFFFFFFFF00000000)
2288 };
2289 assert( v < 6 );
2290 return ((t & ~Truth6[v]) << (1 << v)) | ((t & Truth6[v]) >> (1 << v));
2291 }
Extra_Truth6MinimumExact(word t,int * pComp,int * pPerm)2292 word Extra_Truth6MinimumExact( word t, int * pComp, int * pPerm )
2293 {
2294 word tMin = ~(word)0;
2295 word tCur, tTemp1, tTemp2;
2296 int i, p, c;
2297 for ( i = 0; i < 2; i++ )
2298 {
2299 tCur = i ? ~t : t;
2300 tTemp1 = tCur;
2301 for ( p = 0; p < 720; p++ )
2302 {
2303 // printf( "Trying perm %d:\n", p );
2304 // Kit_DsdPrintFromTruth( &tCur, 6 ), printf( "\n" );;
2305 tTemp2 = tCur;
2306 for ( c = 0; c < 64; c++ )
2307 {
2308 tMin = Abc_MinWord( tMin, tCur );
2309 tCur = Extra_Truth6ChangePhase( tCur, pComp[c] );
2310 }
2311 assert( tTemp2 == tCur );
2312 tCur = Extra_Truth6SwapAdjacent( tCur, pPerm[p] );
2313 }
2314 assert( tTemp1 == tCur );
2315 }
2316 return tMin;
2317 }
2318
2319 /**Function*************************************************************
2320
2321 Synopsis [Perform heuristic TT minimization.]
2322
2323 Description []
2324
2325 SideEffects []
2326
2327 SeeAlso []
2328
2329 ***********************************************************************/
Extra_Truth6Ones(word t)2330 static inline int Extra_Truth6Ones( word t )
2331 {
2332 t = (t & ABC_CONST(0x5555555555555555)) + ((t>> 1) & ABC_CONST(0x5555555555555555));
2333 t = (t & ABC_CONST(0x3333333333333333)) + ((t>> 2) & ABC_CONST(0x3333333333333333));
2334 t = (t & ABC_CONST(0x0F0F0F0F0F0F0F0F)) + ((t>> 4) & ABC_CONST(0x0F0F0F0F0F0F0F0F));
2335 t = (t & ABC_CONST(0x00FF00FF00FF00FF)) + ((t>> 8) & ABC_CONST(0x00FF00FF00FF00FF));
2336 t = (t & ABC_CONST(0x0000FFFF0000FFFF)) + ((t>>16) & ABC_CONST(0x0000FFFF0000FFFF));
2337 return (t & ABC_CONST(0x00000000FFFFFFFF)) + (t>>32);
2338 }
Extra_Truth6MinimumRoundOne(word t,int v)2339 static inline word Extra_Truth6MinimumRoundOne( word t, int v )
2340 {
2341 word tCur, tMin = t; // ab
2342 assert( v >= 0 && v < 5 );
2343
2344 tCur = Extra_Truth6ChangePhase( t, v ); // !ab
2345 tMin = Abc_MinWord( tMin, tCur );
2346 tCur = Extra_Truth6ChangePhase( t, v+1 ); // a!b
2347 tMin = Abc_MinWord( tMin, tCur );
2348 tCur = Extra_Truth6ChangePhase( tCur, v ); // !a!b
2349 tMin = Abc_MinWord( tMin, tCur );
2350
2351 t = Extra_Truth6SwapAdjacent( t, v ); // ba
2352 tMin = Abc_MinWord( tMin, t );
2353
2354 tCur = Extra_Truth6ChangePhase( t, v ); // !ba
2355 tMin = Abc_MinWord( tMin, tCur );
2356 tCur = Extra_Truth6ChangePhase( t, v+1 ); // b!a
2357 tMin = Abc_MinWord( tMin, tCur );
2358 tCur = Extra_Truth6ChangePhase( tCur, v ); // !b!a
2359 tMin = Abc_MinWord( tMin, tCur );
2360
2361 return tMin;
2362 }
Extra_Truth6MinimumRoundMany(word t)2363 static inline word Extra_Truth6MinimumRoundMany( word t )
2364 {
2365 int i, k, Limit = 10;
2366 word tCur, tMin = t;
2367 for ( i = 0; i < Limit; i++ )
2368 {
2369 word tMin0 = tMin;
2370 for ( k = 4; k >= 0; k-- )
2371 {
2372 tCur = Extra_Truth6MinimumRoundOne( tMin, k );
2373 tMin = Abc_MinWord( tMin, tCur );
2374 }
2375 if ( tMin0 == tMin )
2376 break;
2377 }
2378 return tMin;
2379 }
Extra_Truth6MinimumHeuristic(word t)2380 word Extra_Truth6MinimumHeuristic( word t )
2381 {
2382 word tMin1, tMin2;
2383 int nOnes = Extra_Truth6Ones( t );
2384 if ( nOnes < 32 )
2385 return Extra_Truth6MinimumRoundMany( t );
2386 if ( nOnes > 32 )
2387 return Extra_Truth6MinimumRoundMany( ~t );
2388 tMin1 = Extra_Truth6MinimumRoundMany( t );
2389 tMin2 = Extra_Truth6MinimumRoundMany( ~t );
2390 return Abc_MinWord( tMin1, tMin2 );
2391 }
Extra_Truth6MinimumHeuristicTest()2392 void Extra_Truth6MinimumHeuristicTest()
2393 {
2394 word t = ABC_CONST(0x5555555555555555) & ~(ABC_CONST(0x3333333333333333) & ABC_CONST(0x0F0F0F0F0F0F0F0F));
2395 Extra_Truth6MinimumRoundMany( t );
2396 t = 0;
2397 }
2398
2399
2400 /**Function*************************************************************
2401
2402 Synopsis [Reads functions from file.]
2403
2404 Description []
2405
2406 SideEffects []
2407
2408 SeeAlso []
2409
2410 ***********************************************************************/
Extra_NpnRead(char * pFileName,int nFuncs)2411 word * Extra_NpnRead( char * pFileName, int nFuncs )
2412 {
2413 FILE * pFile;
2414 word * pFuncs;
2415 char pBuffer[100];
2416 int i = 0;
2417 pFuncs = ABC_CALLOC( word, nFuncs );
2418 pFile = fopen( pFileName, "rb" );
2419 while ( fgets( pBuffer, 100, pFile ) )
2420 Extra_ReadHex( (unsigned *)(pFuncs + i++), (pBuffer[1] == 'x' ? pBuffer+2 : pBuffer), 16 );
2421 fclose( pFile );
2422 assert( i == nFuncs );
2423 for ( i = 0; i < Abc_MinInt(nFuncs, 10); i++ )
2424 {
2425 printf( "Line %d : ", i );
2426 Extra_PrintHex( stdout, (unsigned *)(pFuncs + i), 6 ), printf( "\n" );
2427 }
2428 return pFuncs;
2429 }
2430
2431 /**Function*************************************************************
2432
2433 Synopsis [Comparison for words.]
2434
2435 Description []
2436
2437 SideEffects []
2438
2439 SeeAlso []
2440
2441 ***********************************************************************/
CompareWords(void * p1,void * p2)2442 int CompareWords( void * p1, void * p2 )
2443 {
2444 word Word1 = *(word *)p1;
2445 word Word2 = *(word *)p2;
2446 if ( Word1 < Word2 )
2447 return -1;
2448 if ( Word1 > Word2 )
2449 return 1;
2450 return 0;
2451 }
2452
2453 /**Function*************************************************************
2454
2455 Synopsis [Computes the permutation table for 8 variables.]
2456
2457 Description []
2458
2459 SideEffects []
2460
2461 SeeAlso []
2462
2463 ***********************************************************************/
Extra_NpnTest1()2464 void Extra_NpnTest1()
2465 {
2466 int * pComp;
2467 pComp = Extra_PermSchedule( 5 );
2468 // pComp = Extra_GreyCodeSchedule( 5 );
2469 ABC_FREE( pComp );
2470 }
Extra_NpnTest2()2471 void Extra_NpnTest2()
2472 {
2473 int * pComp, * pPerm;
2474 word tMin, t = ABC_CONST(0xa2222aaa08888000);
2475 pComp = Extra_GreyCodeSchedule( 6 );
2476 pPerm = Extra_PermSchedule( 6 );
2477 tMin = Extra_Truth6MinimumExact( t, pComp, pPerm );
2478 ABC_FREE( pPerm );
2479 ABC_FREE( pComp );
2480
2481 Extra_PrintHex( stdout, (unsigned *)&t, 6 ), printf( "\n" );
2482 Extra_PrintHex( stdout, (unsigned *)&tMin, 6 ), printf( "\n" );
2483 }
Extra_NpnTest()2484 void Extra_NpnTest()
2485 {
2486 // int nFuncs = 5687661;
2487 // int nFuncs = 400777;
2488 int nFuncs = 10;
2489 abctime clk = Abc_Clock();
2490 word * pFuncs;
2491 int * pComp, * pPerm;
2492 int i;//, k, nUnique = 0;
2493 /*
2494 // read functions
2495 pFuncs = Extra_NpnRead( "C:\\_projects\\abc\\_TEST\\allan\\lib6var5M.txt", nFuncs );
2496 // pFuncs = Extra_NpnRead( "C:\\_projects\\abc\\_TEST\\allan\\lib6var5M_out_Total_minimal.txt", nFuncs );
2497 qsort( (void *)pFuncs, (size_t)nFuncs, sizeof(word), (int(*)(const void *,const void *))CompareWords );
2498
2499 // count unique
2500 k = 1;
2501 for ( i = 1; i < nFuncs; i++ )
2502 if ( pFuncs[i] != pFuncs[i-1] )
2503 pFuncs[k++] = pFuncs[i];
2504 nFuncs = k;
2505 printf( "Total number of unique functions = %d\n", nFuncs );
2506 */
2507 // pFuncs = Extra_NpnRead( "C:\\_projects\\abc\\_TEST\\allan\\lib6var5M_out_Total_minimal.txt", nFuncs );
2508 pFuncs = Extra_NpnRead( "C:\\_projects\\abc\\_TEST\\allan\\test.txt", nFuncs );
2509 pComp = Extra_GreyCodeSchedule( 6 );
2510 pPerm = Extra_PermSchedule( 6 );
2511 // compute minimum forms
2512 for ( i = 0; i < nFuncs; i++ )
2513 {
2514 pFuncs[i] = Extra_Truth6MinimumExact( pFuncs[i], pComp, pPerm );
2515 if ( i % 10000 == 0 )
2516 printf( "%d\n", i );
2517 }
2518 printf( "Finished deriving minimum form\n" );
2519 /*
2520 // sort them by value
2521 qsort( (void *)pFuncs, (size_t)nFuncs, sizeof(word), (int(*)(const void *,const void *))CompareWords );
2522 // count unique
2523 nUnique = nFuncs;
2524 for ( i = 1; i < nFuncs; i++ )
2525 if ( pFuncs[i] == pFuncs[i-1] )
2526 nUnique--;
2527 printf( "Total number of unique ones = %d\n", nUnique );
2528 */
2529 for ( i = 0; i < Abc_MinInt(nFuncs, 10); i++ )
2530 {
2531 printf( "Line %d : ", i );
2532 Extra_PrintHex( stdout, (unsigned *)(pFuncs + i), 6 ), printf( "\n" );
2533 }
2534 ABC_FREE( pPerm );
2535 ABC_FREE( pComp );
2536 ABC_FREE( pFuncs );
2537 Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
2538 }
2539
2540
2541 /**Function*************************************************************
2542
2543 Synopsis []
2544
2545 Description []
2546
2547 SideEffects []
2548
2549 SeeAlso []
2550
2551 ***********************************************************************/
Extra_NtkPrintBin(word * pT,int nBits)2552 void Extra_NtkPrintBin( word * pT, int nBits )
2553 {
2554 int i;
2555 for ( i = nBits - 1; i >= 0; i-- )
2556 printf( "%d", (int)((*pT >> i) & 1) );
2557 }
Extra_NtkPowerTest()2558 void Extra_NtkPowerTest()
2559 {
2560 int i, j, k, n = 4;
2561 for ( i = 0; i < (1<<n); i++ )
2562 for ( j = 0; j < (1<<n); j++ )
2563 {
2564 word t = (word)i;
2565 for ( k = 1; k < j; k++ )
2566 t *= (word)i;
2567 Extra_NtkPrintBin( (word *)&i, n );
2568 Extra_NtkPrintBin( (word *)&j, n );
2569 printf( " " );
2570 Extra_NtkPrintBin( (word *)&t, 64 );
2571 printf( "\n" );
2572 }
2573 }
2574
2575
2576 /**Function*************************************************************
2577
2578 Synopsis [Tranposing bit matrix.]
2579
2580 Description [Borrowed from "Hacker's Delight", by Henry S. Warren Jr.]
2581
2582 SideEffects []
2583
2584 SeeAlso []
2585
2586 ***********************************************************************/
Extra_Transpose64Simple(word A[64],word B[64])2587 static inline void Extra_Transpose64Simple( word A[64], word B[64] )
2588 {
2589 int i, k;
2590 for ( i = 0; i < 64; i++ )
2591 B[i] = 0;
2592 for ( i = 0; i < 64; i++ )
2593 for ( k = 0; k < 64; k++ )
2594 if ( (A[i] >> k) & 1 )
2595 B[k] |= ((word)1 << (63-i));
2596 }
Extra_Transpose32(unsigned a[32])2597 void Extra_Transpose32( unsigned a[32] )
2598 {
2599 int j, k;
2600 unsigned long m, t;
2601 for ( j = 16, m = 0x0000FFFF; j; j >>= 1, m ^= m << j )
2602 {
2603 for ( k = 0; k < 32; k = ((k | j) + 1) & ~j )
2604 {
2605 t = (a[k] ^ (a[k|j] >> j)) & m;
2606 a[k] ^= t;
2607 a[k|j] ^= (t << j);
2608 }
2609 }
2610 }
Extra_Transpose64(word A[64])2611 void Extra_Transpose64( word A[64] )
2612 {
2613 int j, k;
2614 word t, m = 0x00000000FFFFFFFF;
2615 for ( j = 32; j != 0; j = j >> 1, m = m ^ (m << j) )
2616 {
2617 for ( k = 0; k < 64; k = (k + j + 1) & ~j )
2618 {
2619 t = (A[k] ^ (A[k+j] >> j)) & m;
2620 A[k] = A[k] ^ t;
2621 A[k+j] = A[k+j] ^ (t << j);
2622 }
2623 }
2624 }
Extra_Transpose64p(word * A[64])2625 void Extra_Transpose64p( word * A[64] )
2626 {
2627 int j, k;
2628 word t, m = 0x00000000FFFFFFFF;
2629 for ( j = 32; j != 0; j = j >> 1, m = m ^ (m << j) )
2630 {
2631 for ( k = 0; k < 64; k = (k + j + 1) & ~j )
2632 {
2633 t = (A[k][0] ^ (A[k+j][0] >> j)) & m;
2634 A[k][0] = A[k][0] ^ t;
2635 A[k+j][0] = A[k+j][0] ^ (t << j);
2636 }
2637 }
2638 }
Extra_BitMatrixTransposeP(Vec_Wrd_t * vSimsIn,int nWordsIn,Vec_Wrd_t * vSimsOut,int nWordsOut)2639 void Extra_BitMatrixTransposeP( Vec_Wrd_t * vSimsIn, int nWordsIn, Vec_Wrd_t * vSimsOut, int nWordsOut )
2640 {
2641 word * pM[64]; int i, y, x;
2642 assert( Vec_WrdSize(vSimsIn) == Vec_WrdSize(vSimsOut) );
2643 assert( Vec_WrdSize(vSimsIn) / nWordsIn == 64 * nWordsOut );
2644 assert( Vec_WrdSize(vSimsOut) / nWordsOut == 64 * nWordsIn );
2645 for ( y = 0; y < nWordsIn; y++ )
2646 for ( x = 0; x < nWordsOut; x++ )
2647 {
2648 for ( i = 0; i < 64; i++ )
2649 {
2650 pM[i] = Vec_WrdEntryP( vSimsOut, (64*y+i)*nWordsOut + x );
2651 pM[i][0] = Vec_WrdEntry ( vSimsIn, (64*x+i)*nWordsIn + y );
2652 }
2653 Extra_Transpose64p( pM );
2654 }
2655 }
Extra_BitMatrixTransposePP(Vec_Ptr_t * vSimsIn,int nWordsIn,Vec_Wrd_t * vSimsOut,int nWordsOut)2656 void Extra_BitMatrixTransposePP( Vec_Ptr_t * vSimsIn, int nWordsIn, Vec_Wrd_t * vSimsOut, int nWordsOut )
2657 {
2658 word * pM[64]; int i, y, x;
2659 assert( Vec_WrdSize(vSimsOut) / nWordsOut == 64 * nWordsIn );
2660 for ( y = 0; y < nWordsIn; y++ )
2661 for ( x = 0; x < nWordsOut; x++ )
2662 {
2663 for ( i = 0; i < 64; i++ )
2664 {
2665 pM[i] = Vec_WrdEntryP( vSimsOut, (64*y+i)*nWordsOut + x );
2666 pM[i][0] = ((word *)Vec_PtrEntry( vSimsIn, 64*x+i ))[y];
2667 }
2668 Extra_Transpose64p( pM );
2669 }
2670 }
Extra_BitMatrixTransposeTest()2671 void Extra_BitMatrixTransposeTest()
2672 {
2673 int nWordsIn = 1;
2674 int nWordsOut = 2;
2675 int i, k, nItems = 64 * nWordsIn * nWordsOut;
2676
2677 Vec_Wrd_t * vSimsIn = Vec_WrdStart( nItems );
2678 Vec_Wrd_t * vSimsOut = Vec_WrdStart( nItems );
2679
2680 Abc_RandomW(1);
2681 for ( i = 0; i < nItems; i++ )
2682 Vec_WrdWriteEntry( vSimsIn, i, Abc_RandomW(0) );
2683
2684 Extra_BitMatrixTransposeP( vSimsIn, nWordsIn, vSimsOut, nWordsOut );
2685
2686 nItems = Vec_WrdSize(vSimsIn) / nWordsIn;
2687 for ( i = 0; i < nItems; i++ )
2688 {
2689 if ( i%64 == 0 )
2690 Abc_Print( 1, "\n" );
2691 for ( k = 0; k < nWordsIn; k++ )
2692 {
2693 Extra_PrintBinary( stdout, (unsigned *)Vec_WrdEntryP(vSimsIn, i*nWordsIn+k), 64 );
2694 Abc_Print( 1, " " );
2695 }
2696 Abc_Print( 1, "\n" );
2697 }
2698 Abc_Print( 1, "\n" );
2699
2700 nItems = Vec_WrdSize(vSimsOut) / nWordsOut;
2701 for ( i = 0; i < nItems; i++ )
2702 {
2703 if ( i%64 == 0 )
2704 Abc_Print( 1, "\n" );
2705 for ( k = 0; k < nWordsOut; k++ )
2706 {
2707 Extra_PrintBinary( stdout, (unsigned *)Vec_WrdEntryP(vSimsOut, i*nWordsOut+k), 64 );
2708 Abc_Print( 1, " " );
2709 }
2710 Abc_Print( 1, "\n" );
2711 }
2712 Abc_Print( 1, "\n" );
2713
2714 Vec_WrdFree( vSimsIn );
2715 Vec_WrdFree( vSimsOut );
2716 }
2717
2718 ////////////////////////////////////////////////////////////////////////
2719 /// END OF FILE ///
2720 ////////////////////////////////////////////////////////////////////////
2721
2722
2723 ABC_NAMESPACE_IMPL_END
2724
2725