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