src/misc/extra/extraUtilMisc.c File Reference

#include "extra.h"
Include dependency graph for extraUtilMisc.c:

Go to the source code of this file.

Functions

static void Extra_Permutations_rec (char **pRes, int nFact, int n, char Array[])
int Extra_Base2Log (unsigned Num)
int Extra_Base2LogDouble (double Num)
int Extra_Base10Log (unsigned Num)
double Extra_Power2 (int Degree)
int Extra_Power3 (int Num)
int Extra_NumCombinations (int k, int n)
int * Extra_DeriveRadixCode (int Number, int Radix, int nDigits)
int Extra_CountOnes (unsigned char *pBytes, int nBytes)
int Extra_Factorial (int n)
char ** Extra_Permutations (int n)
void Extra_TruthPermute_int (int *pMints, int nMints, char *pPerm, int nVars, int *pMintsP)
unsigned Extra_TruthPermute (unsigned Truth, char *pPerms, int nVars, int fReverse)
unsigned Extra_TruthPolarize (unsigned uTruth, int Polarity, int nVars)
unsigned Extra_TruthCanonN (unsigned uTruth, int nVars)
unsigned Extra_TruthCanonNN (unsigned uTruth, int nVars)
unsigned Extra_TruthCanonP (unsigned uTruth, int nVars)
unsigned Extra_TruthCanonNP (unsigned uTruth, int nVars)
unsigned Extra_TruthCanonNPN (unsigned uTruth, int nVars)
void Extra_Truth4VarNPN (unsigned short **puCanons, char **puPhases, char **puPerms, unsigned char **puMap)
void Extra_Truth3VarN (unsigned **puCanons, char ***puPhases, char **ppCounters)
void Extra_Truth4VarN (unsigned short **puCanons, char ***puPhases, char **ppCounters, int nPhasesMax)
void ** Extra_ArrayAlloc (int nCols, int nRows, int Size)
unsigned short Extra_TruthPerm4One (unsigned uTruth, int Phase)
unsigned Extra_TruthPerm5One (unsigned uTruth, int Phase)
void Extra_TruthPerm6One (unsigned *uTruth, int Phase, unsigned *uTruthRes)
void Extra_TruthExpand (int nVars, int nWords, unsigned *puTruth, unsigned uPhase, unsigned *puTruthR)
unsigned short ** Extra_TruthPerm43 ()
unsigned ** Extra_TruthPerm53 ()
unsigned ** Extra_TruthPerm54 ()
unsigned ** Extra_TruthPerm63 ()
unsigned ** Extra_Truths8 ()
void Extra_BubbleSort (int Order[], int Costs[], int nSize, int fIncreasing)
unsigned int Cudd_PrimeCopy (unsigned int p)
void Extra_TruthExpandGeneratePermTable ()

Function Documentation

unsigned int Cudd_PrimeCopy ( unsigned int  p  ) 

Function*************************************************************

Synopsis [Returns the smallest prime larger than the number.]

Description []

SideEffects []

SeeAlso []

Definition at line 2131 of file extraUtilMisc.c.

02132 {
02133     int i,pn;
02134 
02135     p--;
02136     do {
02137         p++;
02138         if (p&1) {
02139             pn = 1;
02140             i = 3;
02141             while ((unsigned) (i * i) <= p) {
02142                 if (p % i == 0) {
02143                     pn = 0;
02144                     break;
02145                 }
02146                 i += 2;
02147             }
02148         } else {
02149             pn = 0;
02150         }
02151     } while (!pn);
02152     return(p);
02153 
02154 } /* end of Cudd_Prime */

void** Extra_ArrayAlloc ( int  nCols,
int  nRows,
int  Size 
)

Function*************************************************************

Synopsis [Allocated one-memory-chunk array.]

Description []

SideEffects []

SeeAlso []

Definition at line 918 of file extraUtilMisc.c.

00919 {
00920     char ** pRes;
00921     char * pBuffer;
00922     int i;
00923     assert( nCols > 0 && nRows > 0 && Size > 0 );
00924     pBuffer = ALLOC( char, nCols * (sizeof(void *) + nRows * Size) );
00925     pRes = (char **)pBuffer;
00926     pRes[0] = pBuffer + nCols * sizeof(void *);
00927     for ( i = 1; i < nCols; i++ )
00928         pRes[i] = pRes[0] + i * nRows * Size;
00929     return pRes;
00930 }

int Extra_Base10Log ( unsigned  Num  ) 

Function********************************************************************

Synopsis [Finds the smallest integer larger of equal than the logarithm.]

Description [Returns [Log10(Num)].]

SideEffects []

SeeAlso []

Definition at line 115 of file extraUtilMisc.c.

00116 {
00117     int Res;
00118     assert( Num >= 0 );
00119     if ( Num == 0 ) return 0;
00120     if ( Num == 1 ) return 1;
00121         for ( Res = 0, Num--;  Num;  Num /= 10,  Res++ );
00122     return Res;
00123 } /* end of Extra_Base2Log */

int Extra_Base2Log ( unsigned  Num  ) 

Function********************************************************************

Synopsis [Finds the smallest integer larger of equal than the logarithm.]

Description [Returns [Log2(Num)].]

SideEffects []

SeeAlso []

Definition at line 70 of file extraUtilMisc.c.

00071 {
00072     int Res;
00073     assert( Num >= 0 );
00074     if ( Num == 0 ) return 0;
00075     if ( Num == 1 ) return 1;
00076     for ( Res = 0, Num--; Num; Num >>= 1, Res++ );
00077     return Res;
00078 } /* end of Extra_Base2Log */

int Extra_Base2LogDouble ( double  Num  ) 

Function********************************************************************

Synopsis [Finds the smallest integer larger of equal than the logarithm.]

Description []

SideEffects []

SeeAlso []

Definition at line 91 of file extraUtilMisc.c.

00092 {
00093     double Res;
00094     int ResInt;
00095 
00096     Res    = log(Num)/log(2.0);
00097     ResInt = (int)Res;
00098     if ( ResInt == Res )
00099         return ResInt;
00100     else 
00101         return ResInt+1;
00102 }

void Extra_BubbleSort ( int  Order[],
int  Costs[],
int  nSize,
int  fIncreasing 
)

Function*************************************************************

Synopsis [Bubble-sorts components by scores in increasing order.]

Description []

SideEffects []

SeeAlso []

Definition at line 2082 of file extraUtilMisc.c.

02083 {
02084     int i, Temp, fChanges;
02085     assert( nSize < 1000 );
02086     for ( i = 0; i < nSize; i++ )
02087         Order[i] = i;
02088     if ( fIncreasing )
02089     {
02090         do {
02091             fChanges = 0;
02092             for ( i = 0; i < nSize - 1; i++ )
02093             {
02094                 if ( Costs[Order[i]] <= Costs[Order[i+1]] )
02095                     continue;
02096                 Temp = Order[i];
02097                 Order[i] = Order[i+1];
02098                 Order[i+1] = Temp;
02099                 fChanges = 1;
02100             }
02101         } while ( fChanges );
02102     }
02103     else
02104     {
02105         do {
02106             fChanges = 0;
02107             for ( i = 0; i < nSize - 1; i++ )
02108             {
02109                 if ( Costs[Order[i]] >= Costs[Order[i+1]] )
02110                     continue;
02111                 Temp = Order[i];
02112                 Order[i] = Order[i+1];
02113                 Order[i+1] = Temp;
02114                 fChanges = 1;
02115             }
02116         } while ( fChanges );
02117     }
02118 }

int Extra_CountOnes ( unsigned char *  pBytes,
int  nBytes 
)

Function*************************************************************

Synopsis [Counts the number of ones in the bitstring.]

Description []

SideEffects []

SeeAlso []

Definition at line 223 of file extraUtilMisc.c.

00224 {
00225     static int bit_count[256] = {
00226       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,
00227       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,
00228       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,
00229       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,
00230       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,
00231       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,
00232       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,
00233       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
00234     };
00235 
00236     int i, Counter;
00237     Counter = 0;
00238     for ( i = 0; i < nBytes; i++ )
00239         Counter += bit_count[ *(pBytes+i) ];
00240     return Counter;
00241 }

int* Extra_DeriveRadixCode ( int  Number,
int  Radix,
int  nDigits 
)

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 198 of file extraUtilMisc.c.

00199 {
00200     static int Code[100];
00201     int i;
00202     assert( nDigits < 100 );
00203     for ( i = 0; i < nDigits; i++ )
00204     {
00205         Code[i] = Number % Radix;
00206         Number  = Number / Radix;
00207     }
00208     assert( Number == 0 );
00209     return Code;
00210 }

int Extra_Factorial ( int  n  ) 

Function********************************************************************

Synopsis [Computes the factorial.]

Description []

SideEffects []

SeeAlso []

Definition at line 254 of file extraUtilMisc.c.

00255 {
00256     int i, Res = 1;
00257     for ( i = 1; i <= n; i++ )
00258         Res *= i;
00259     return Res;
00260 }

int Extra_NumCombinations ( int  k,
int  n 
)

Function********************************************************************

Synopsis [Finds the number of combinations of k elements out of n.]

Description []

SideEffects []

SeeAlso []

Definition at line 179 of file extraUtilMisc.c.

00180 {
00181     int i, Res = 1;
00182     for ( i = 1; i <= k; i++ )
00183             Res = Res * (n-i+1) / i;
00184     return Res;
00185 } /* end of Extra_NumCombinations */

char** Extra_Permutations ( int  n  ) 

Function********************************************************************

Synopsis [Computes the set of all permutations.]

Description [The number of permutations in the array is n!. The number of entries in each permutation is n. Therefore, the resulting array is a two-dimentional array of the size: n! x n. To free the resulting array, call free() on the pointer returned by this procedure.]

SideEffects []

SeeAlso []

Definition at line 276 of file extraUtilMisc.c.

00277 {
00278     char Array[50];
00279     char ** pRes;
00280     int nFact, i;
00281     // allocate memory
00282     nFact = Extra_Factorial( n );
00283     pRes  = (char **)Extra_ArrayAlloc( nFact, n, sizeof(char) );
00284     // fill in the permutations
00285     for ( i = 0; i < n; i++ )
00286         Array[i] = i;
00287     Extra_Permutations_rec( pRes, nFact, n, Array );
00288     // print the permutations
00289 /*
00290     {
00291     int i, k;
00292     for ( i = 0; i < nFact; i++ )
00293     {
00294         printf( "{" );
00295         for ( k = 0; k < n; k++ )
00296             printf( " %d", pRes[i][k] );
00297         printf( " }\n" );
00298     }
00299     }
00300 */
00301     return pRes;
00302 }

void Extra_Permutations_rec ( char **  pRes,
int  nFact,
int  n,
char  Array[] 
) [static]

CFile****************************************************************

FileName [extraUtilMisc.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [extra]

Synopsis [Misc procedures.]

Author [Alan Mishchenko]

Affiliation [UC Berkeley]

Date [Ver. 1.0. Started - June 20, 2005.]

Revision [

Id
extraUtilMisc.c,v 1.0 2003/09/01 00:00:00 alanmi Exp

]AutomaticStart AutomaticEnd

Function********************************************************************

Synopsis [Fills in the array of permutations.]

Description []

SideEffects []

SeeAlso []

Definition at line 315 of file extraUtilMisc.c.

00316 {
00317     char ** pNext;
00318     int nFactNext;
00319     int iTemp, iCur, iLast, k;
00320 
00321     if ( n == 1 )
00322     {
00323         pRes[0][0] = Array[0];
00324         return;
00325     }
00326 
00327     // get the next factorial
00328     nFactNext = nFact / n;
00329     // get the last entry
00330     iLast = n - 1;
00331 
00332     for ( iCur = 0; iCur < n; iCur++ )
00333     {
00334         // swap Cur and Last
00335         iTemp        = Array[iCur];
00336         Array[iCur]  = Array[iLast];
00337         Array[iLast] = iTemp;
00338 
00339         // get the pointer to the current section
00340         pNext = pRes + (n - 1 - iCur) * nFactNext;
00341 
00342         // set the last entry 
00343         for ( k = 0; k < nFactNext; k++ )
00344             pNext[k][iLast] = Array[iLast];
00345 
00346         // call recursively for this part
00347         Extra_Permutations_rec( pNext, nFactNext, n - 1, Array );
00348 
00349         // swap them back
00350         iTemp        = Array[iCur];
00351         Array[iCur]  = Array[iLast];
00352         Array[iLast] = iTemp;
00353     }
00354 }

double Extra_Power2 ( int  Degree  ) 

Function********************************************************************

Synopsis [Returns the power of two as a double.]

Description []

SideEffects []

SeeAlso []

Definition at line 136 of file extraUtilMisc.c.

00137 {
00138     double Res;
00139     assert( Degree >= 0 );
00140     if ( Degree < 32 )
00141         return (double)(01<<Degree); 
00142     for ( Res = 1.0; Degree; Res *= 2.0, Degree-- );
00143     return Res;
00144 }

int Extra_Power3 ( int  Num  ) 

Function*************************************************************

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 158 of file extraUtilMisc.c.

00159 {
00160     int i;
00161     int Res;
00162     Res = 1;
00163     for ( i = 0; i < Num; i++ )
00164         Res *= 3;
00165     return Res;
00166 }

void Extra_Truth3VarN ( unsigned **  puCanons,
char ***  puPhases,
char **  ppCounters 
)

Function*************************************************************

Synopsis [Computes NPN canonical forms for 4-variable functions.]

Description []

SideEffects []

SeeAlso []

Definition at line 784 of file extraUtilMisc.c.

00785 {
00786     int nPhasesMax = 8;
00787     unsigned * uCanons;
00788     unsigned uTruth, uPhase, uTruth32;
00789     char ** uPhases, * pCounters;
00790     int nFuncs, nClasses, i;
00791 
00792     nFuncs  = (1 << 8);
00793     uCanons = ALLOC( unsigned, nFuncs );
00794     memset( uCanons, 0, sizeof(unsigned) * nFuncs );
00795     pCounters = ALLOC( char, nFuncs );
00796     memset( pCounters, 0, sizeof(char) * nFuncs );
00797     uPhases = (char **)Extra_ArrayAlloc( nFuncs, nPhasesMax, sizeof(char) );
00798     nClasses = 0;
00799     for ( uTruth = 0; uTruth < (unsigned)nFuncs; uTruth++ )
00800     {
00801         // skip already assigned
00802         uTruth32 = ((uTruth << 24) | (uTruth << 16) | (uTruth << 8) | uTruth);
00803         if ( uCanons[uTruth] )
00804         {
00805             assert( uTruth32 > uCanons[uTruth] );
00806             continue;
00807         }
00808         nClasses++;
00809         for ( i = 0; i < 8; i++ )
00810         {
00811             uPhase = Extra_TruthPolarize( uTruth, i, 3 );
00812             if ( uCanons[uPhase] == 0 && (uTruth || i==0) )
00813             {
00814                 uCanons[uPhase]    = uTruth32;
00815                 uPhases[uPhase][0] = i;
00816                 pCounters[uPhase]  = 1;
00817             }
00818             else
00819             {
00820                 assert( uCanons[uPhase] == uTruth32 );
00821                 if ( pCounters[uPhase] < nPhasesMax )
00822                     uPhases[uPhase][ pCounters[uPhase]++ ] = i;
00823             }
00824         }
00825     }
00826     if ( puCanons ) 
00827         *puCanons = uCanons;
00828     else
00829         free( uCanons );
00830     if ( puPhases ) 
00831         *puPhases = uPhases;
00832     else
00833         free( uPhases );
00834     if ( ppCounters ) 
00835         *ppCounters = pCounters;
00836     else
00837         free( pCounters );
00838 //    printf( "The number of 3N-classes = %d.\n", nClasses );
00839 }

void Extra_Truth4VarN ( unsigned short **  puCanons,
char ***  puPhases,
char **  ppCounters,
int  nPhasesMax 
)

Function*************************************************************

Synopsis [Computes NPN canonical forms for 4-variable functions.]

Description []

SideEffects []

SeeAlso []

Definition at line 852 of file extraUtilMisc.c.

00853 {
00854     unsigned short * uCanons;
00855     unsigned uTruth, uPhase;
00856     char ** uPhases, * pCounters;
00857     int nFuncs, nClasses, i;
00858 
00859     nFuncs  = (1 << 16);
00860     uCanons = ALLOC( unsigned short, nFuncs );
00861     memset( uCanons, 0, sizeof(unsigned short) * nFuncs );
00862     pCounters = ALLOC( char, nFuncs );
00863     memset( pCounters, 0, sizeof(char) * nFuncs );
00864     uPhases = (char **)Extra_ArrayAlloc( nFuncs, nPhasesMax, sizeof(char) );
00865     nClasses = 0;
00866     for ( uTruth = 0; uTruth < (unsigned)nFuncs; uTruth++ )
00867     {
00868         // skip already assigned
00869         if ( uCanons[uTruth] )
00870         {
00871             assert( uTruth > uCanons[uTruth] );
00872             continue;
00873         }
00874         nClasses++;
00875         for ( i = 0; i < 16; i++ )
00876         {
00877             uPhase = Extra_TruthPolarize( uTruth, i, 4 );
00878             if ( uCanons[uPhase] == 0 && (uTruth || i==0) )
00879             {
00880                 uCanons[uPhase]    = uTruth;
00881                 uPhases[uPhase][0] = i;
00882                 pCounters[uPhase]  = 1;
00883             }
00884             else
00885             {
00886                 assert( uCanons[uPhase] == uTruth );
00887                 if ( pCounters[uPhase] < nPhasesMax )
00888                     uPhases[uPhase][ pCounters[uPhase]++ ] = i;
00889             }
00890         }
00891     }
00892     if ( puCanons ) 
00893         *puCanons = uCanons;
00894     else
00895         free( uCanons );
00896     if ( puPhases ) 
00897         *puPhases = uPhases;
00898     else
00899         free( uPhases );
00900     if ( ppCounters ) 
00901         *ppCounters = pCounters;
00902     else
00903         free( pCounters );
00904 //    printf( "The number of 4N-classes = %d.\n", nClasses );
00905 }

void Extra_Truth4VarNPN ( unsigned short **  puCanons,
char **  puPhases,
char **  puPerms,
unsigned char **  puMap 
)

Function*************************************************************

Synopsis [Computes NPN canonical forms for 4-variable functions.]

Description []

SideEffects []

SeeAlso []

Definition at line 680 of file extraUtilMisc.c.

00681 {
00682     unsigned short * uCanons;
00683     unsigned char * uMap;
00684     unsigned uTruth, uPhase, uPerm;
00685     char ** pPerms4, * uPhases, * uPerms;
00686     int nFuncs, nClasses;
00687     int i, k;
00688 
00689     nFuncs  = (1 << 16);
00690     uCanons = ALLOC( unsigned short, nFuncs );
00691     uPhases = ALLOC( char, nFuncs );
00692     uPerms  = ALLOC( char, nFuncs );
00693     uMap    = ALLOC( unsigned char, nFuncs );
00694     memset( uCanons, 0, sizeof(unsigned short) * nFuncs );
00695     memset( uPhases, 0, sizeof(char) * nFuncs );
00696     memset( uPerms,  0, sizeof(char) * nFuncs );
00697     memset( uMap,    0, sizeof(unsigned char) * nFuncs );
00698     pPerms4 = Extra_Permutations( 4 );
00699 
00700     nClasses = 1;
00701     nFuncs = (1 << 15);
00702     for ( uTruth = 1; uTruth < (unsigned)nFuncs; uTruth++ )
00703     {
00704         // skip already assigned
00705         if ( uCanons[uTruth] )
00706         {
00707             assert( uTruth > uCanons[uTruth] );
00708             uMap[~uTruth & 0xFFFF] = uMap[uTruth] = uMap[uCanons[uTruth]];
00709             continue;
00710         }
00711         uMap[uTruth] = nClasses++;
00712         for ( i = 0; i < 16; i++ )
00713         {
00714             uPhase = Extra_TruthPolarize( uTruth, i, 4 );
00715             for ( k = 0; k < 24; k++ )
00716             {
00717                 uPerm = Extra_TruthPermute( uPhase, pPerms4[k], 4, 0 );
00718                 if ( uCanons[uPerm] == 0 )
00719                 {
00720                     uCanons[uPerm] = uTruth;
00721                     uPhases[uPerm] = i;
00722                     uPerms[uPerm]  = k;
00723 
00724                     uPerm = ~uPerm & 0xFFFF;
00725                     uCanons[uPerm] = uTruth;
00726                     uPhases[uPerm] = i | 16;
00727                     uPerms[uPerm]  = k;
00728                 }
00729                 else
00730                     assert( uCanons[uPerm] == uTruth );
00731             }
00732             uPhase = Extra_TruthPolarize( ~uTruth & 0xFFFF, i, 4 ); 
00733             for ( k = 0; k < 24; k++ )
00734             {
00735                 uPerm = Extra_TruthPermute( uPhase, pPerms4[k], 4, 0 );
00736                 if ( uCanons[uPerm] == 0 )
00737                 {
00738                     uCanons[uPerm] = uTruth;
00739                     uPhases[uPerm] = i;
00740                     uPerms[uPerm]  = k;
00741 
00742                     uPerm = ~uPerm & 0xFFFF;
00743                     uCanons[uPerm] = uTruth;
00744                     uPhases[uPerm] = i | 16;
00745                     uPerms[uPerm]  = k;
00746                 }
00747                 else
00748                     assert( uCanons[uPerm] == uTruth );
00749             }
00750         }
00751     }
00752     uPhases[(1<<16)-1] = 16;
00753     assert( nClasses == 222 );
00754     free( pPerms4 );
00755     if ( puCanons ) 
00756         *puCanons = uCanons;
00757     else
00758         free( uCanons );
00759     if ( puPhases ) 
00760         *puPhases = uPhases;
00761     else
00762         free( uPhases );
00763     if ( puPerms ) 
00764         *puPerms = uPerms;
00765     else
00766         free( uPerms );
00767     if ( puMap ) 
00768         *puMap = uMap;
00769     else
00770         free( uMap );
00771 }

unsigned Extra_TruthCanonN ( unsigned  uTruth,
int  nVars 
)

Function*************************************************************

Synopsis [Computes N-canonical form using brute-force methods.]

Description []

SideEffects []

SeeAlso []

Definition at line 477 of file extraUtilMisc.c.

00478 {
00479     unsigned uTruthMin, uPhase;
00480     int nMints, i;
00481     nMints    = (1 << nVars);
00482     uTruthMin = 0xFFFFFFFF;
00483     for ( i = 0; i < nMints; i++ )
00484     {
00485         uPhase = Extra_TruthPolarize( uTruth, i, nVars ); 
00486         if ( uTruthMin > uPhase )
00487             uTruthMin = uPhase;
00488     }
00489     return uTruthMin;
00490 }

unsigned Extra_TruthCanonNN ( unsigned  uTruth,
int  nVars 
)

Function*************************************************************

Synopsis [Computes NN-canonical form using brute-force methods.]

Description []

SideEffects []

SeeAlso []

Definition at line 503 of file extraUtilMisc.c.

00504 {
00505     unsigned uTruthMin, uTruthC, uPhase;
00506     int nMints, i;
00507     nMints    = (1 << nVars);
00508     uTruthC   = (unsigned)( (~uTruth) & ((~((unsigned)0)) >> (32-nMints)) );
00509     uTruthMin = 0xFFFFFFFF;
00510     for ( i = 0; i < nMints; i++ )
00511     {
00512         uPhase = Extra_TruthPolarize( uTruth, i, nVars ); 
00513         if ( uTruthMin > uPhase )
00514             uTruthMin = uPhase;
00515         uPhase = Extra_TruthPolarize( uTruthC, i, nVars ); 
00516         if ( uTruthMin > uPhase )
00517             uTruthMin = uPhase;
00518     }
00519     return uTruthMin;
00520 }

unsigned Extra_TruthCanonNP ( unsigned  uTruth,
int  nVars 
)

Function*************************************************************

Synopsis [Computes NP-canonical form using brute-force methods.]

Description []

SideEffects []

SeeAlso []

Definition at line 576 of file extraUtilMisc.c.

00577 {
00578     static int nVarsOld, nPerms;
00579     static char ** pPerms = NULL;
00580 
00581     unsigned uTruthMin, uPhase, uPerm;
00582     int nMints, k, i;
00583 
00584     if ( pPerms == NULL )
00585     {
00586         nPerms = Extra_Factorial( nVars );   
00587         pPerms = Extra_Permutations( nVars );
00588         nVarsOld = nVars;
00589     }
00590     else if ( nVarsOld != nVars )
00591     {
00592         free( pPerms );
00593         nPerms = Extra_Factorial( nVars );   
00594         pPerms = Extra_Permutations( nVars );
00595         nVarsOld = nVars;
00596     }
00597 
00598     nMints    = (1 << nVars);
00599     uTruthMin = 0xFFFFFFFF;
00600     for ( i = 0; i < nMints; i++ )
00601     {
00602         uPhase = Extra_TruthPolarize( uTruth, i, nVars ); 
00603         for ( k = 0; k < nPerms; k++ )
00604         {
00605             uPerm = Extra_TruthPermute( uPhase, pPerms[k], nVars, 0 );
00606             if ( uTruthMin > uPerm )
00607                 uTruthMin = uPerm;
00608         }
00609     }
00610     return uTruthMin;
00611 }

unsigned Extra_TruthCanonNPN ( unsigned  uTruth,
int  nVars 
)

Function*************************************************************

Synopsis [Computes NPN-canonical form using brute-force methods.]

Description []

SideEffects []

SeeAlso []

Definition at line 624 of file extraUtilMisc.c.

00625 {
00626     static int nVarsOld, nPerms;
00627     static char ** pPerms = NULL;
00628 
00629     unsigned uTruthMin, uTruthC, uPhase, uPerm;
00630     int nMints, k, i;
00631 
00632     if ( pPerms == NULL )
00633     {
00634         nPerms = Extra_Factorial( nVars );   
00635         pPerms = Extra_Permutations( nVars );
00636         nVarsOld = nVars;
00637     }
00638     else if ( nVarsOld != nVars )
00639     {
00640         free( pPerms );
00641         nPerms = Extra_Factorial( nVars );   
00642         pPerms = Extra_Permutations( nVars );
00643         nVarsOld = nVars;
00644     }
00645 
00646     nMints    = (1 << nVars);
00647     uTruthC   = (unsigned)( (~uTruth) & ((~((unsigned)0)) >> (32-nMints)) );
00648     uTruthMin = 0xFFFFFFFF;
00649     for ( i = 0; i < nMints; i++ )
00650     {
00651         uPhase = Extra_TruthPolarize( uTruth, i, nVars ); 
00652         for ( k = 0; k < nPerms; k++ )
00653         {
00654             uPerm = Extra_TruthPermute( uPhase, pPerms[k], nVars, 0 );
00655             if ( uTruthMin > uPerm )
00656                 uTruthMin = uPerm;
00657         }
00658         uPhase = Extra_TruthPolarize( uTruthC, i, nVars ); 
00659         for ( k = 0; k < nPerms; k++ )
00660         {
00661             uPerm = Extra_TruthPermute( uPhase, pPerms[k], nVars, 0 );
00662             if ( uTruthMin > uPerm )
00663                 uTruthMin = uPerm;
00664         }
00665     }
00666     return uTruthMin;
00667 }

unsigned Extra_TruthCanonP ( unsigned  uTruth,
int  nVars 
)

Function*************************************************************

Synopsis [Computes P-canonical form using brute-force methods.]

Description []

SideEffects []

SeeAlso []

Definition at line 533 of file extraUtilMisc.c.

00534 {
00535     static int nVarsOld, nPerms;
00536     static char ** pPerms = NULL;
00537 
00538     unsigned uTruthMin, uPerm;
00539     int k;
00540 
00541     if ( pPerms == NULL )
00542     {
00543         nPerms = Extra_Factorial( nVars );   
00544         pPerms = Extra_Permutations( nVars );
00545         nVarsOld = nVars;
00546     }
00547     else if ( nVarsOld != nVars )
00548     {
00549         free( pPerms );
00550         nPerms = Extra_Factorial( nVars );   
00551         pPerms = Extra_Permutations( nVars );
00552         nVarsOld = nVars;
00553     }
00554 
00555     uTruthMin = 0xFFFFFFFF;
00556     for ( k = 0; k < nPerms; k++ )
00557     {
00558         uPerm = Extra_TruthPermute( uTruth, pPerms[k], nVars, 0 );
00559         if ( uTruthMin > uPerm )
00560             uTruthMin = uPerm;
00561     }
00562     return uTruthMin;
00563 }

void Extra_TruthExpand ( int  nVars,
int  nWords,
unsigned *  puTruth,
unsigned  uPhase,
unsigned *  puTruthR 
)

Function*************************************************************

Synopsis [Computes a phase of the 8-var function.]

Description []

SideEffects []

SeeAlso []

Definition at line 1317 of file extraUtilMisc.c.

01318 {
01319     // elementary truth tables
01320     static unsigned uTruths[8][8] = {
01321         { 0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA },
01322         { 0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC },
01323         { 0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0 },
01324         { 0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00 },
01325         { 0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000 }, 
01326         { 0x00000000,0xFFFFFFFF,0x00000000,0xFFFFFFFF,0x00000000,0xFFFFFFFF,0x00000000,0xFFFFFFFF }, 
01327         { 0x00000000,0x00000000,0xFFFFFFFF,0xFFFFFFFF,0x00000000,0x00000000,0xFFFFFFFF,0xFFFFFFFF }, 
01328         { 0x00000000,0x00000000,0x00000000,0x00000000,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF } 
01329     };
01330     static char Cases[256] = {
01331          0, // 00000000
01332          0, // 00000001
01333          1, // 00000010
01334          0, // 00000011
01335          2, // 00000100
01336         -1, // 00000101
01337         -1, // 00000110
01338          0, // 00000111
01339          3, // 00001000
01340         -1, // 00001001
01341         -1, // 00001010
01342         -1, // 00001011
01343         -1, // 00001100
01344         -1, // 00001101
01345         -1, // 00001110
01346          0, // 00001111
01347          4, // 00010000
01348         -1, // 00010001
01349         -1, // 00010010
01350         -1, // 00010011
01351         -1, // 00010100
01352         -1, // 00010101
01353         -1, // 00010110
01354         -1, // 00010111
01355         -1, // 00011000
01356         -1, // 00011001
01357         -1, // 00011010
01358         -1, // 00011011
01359         -1, // 00011100
01360         -1, // 00011101
01361         -1, // 00011110
01362          0, // 00011111
01363          5, // 00100000
01364         -1, // 00100001
01365         -1, // 00100010
01366         -1, // 00100011
01367         -1, // 00100100
01368         -1, // 00100101
01369         -1, // 00100110
01370         -1, // 00100111
01371         -1, // 00101000
01372         -1, // 00101001
01373         -1, // 00101010
01374         -1, // 00101011
01375         -1, // 00101100
01376         -1, // 00101101
01377         -1, // 00101110
01378         -1, // 00101111
01379         -1, // 00110000
01380         -1, // 00110001
01381         -1, // 00110010
01382         -1, // 00110011
01383         -1, // 00110100
01384         -1, // 00110101
01385         -1, // 00110110
01386         -1, // 00110111
01387         -1, // 00111000
01388         -1, // 00111001
01389         -1, // 00111010
01390         -1, // 00111011
01391         -1, // 00111100
01392         -1, // 00111101
01393         -1, // 00111110
01394          0, // 00111111
01395          6, // 01000000
01396         -1, // 01000001
01397         -1, // 01000010
01398         -1, // 01000011
01399         -1, // 01000100
01400         -1, // 01000101
01401         -1, // 01000110
01402         -1, // 01000111
01403         -1, // 01001000
01404         -1, // 01001001
01405         -1, // 01001010
01406         -1, // 01001011
01407         -1, // 01001100
01408         -1, // 01001101
01409         -1, // 01001110
01410         -1, // 01001111
01411         -1, // 01010000
01412         -1, // 01010001
01413         -1, // 01010010
01414         -1, // 01010011
01415         -1, // 01010100
01416         -1, // 01010101
01417         -1, // 01010110
01418         -1, // 01010111
01419         -1, // 01011000
01420         -1, // 01011001
01421         -1, // 01011010
01422         -1, // 01011011
01423         -1, // 01011100
01424         -1, // 01011101
01425         -1, // 01011110
01426         -1, // 01011111
01427         -1, // 01100000
01428         -1, // 01100001
01429         -1, // 01100010
01430         -1, // 01100011
01431         -1, // 01100100
01432         -1, // 01100101
01433         -1, // 01100110
01434         -1, // 01100111
01435         -1, // 01101000
01436         -1, // 01101001
01437         -1, // 01101010
01438         -1, // 01101011
01439         -1, // 01101100
01440         -1, // 01101101
01441         -1, // 01101110
01442         -1, // 01101111
01443         -1, // 01110000
01444         -1, // 01110001
01445         -1, // 01110010
01446         -1, // 01110011
01447         -1, // 01110100
01448         -1, // 01110101
01449         -1, // 01110110
01450         -1, // 01110111
01451         -1, // 01111000
01452         -1, // 01111001
01453         -1, // 01111010
01454         -1, // 01111011
01455         -1, // 01111100
01456         -1, // 01111101
01457         -1, // 01111110
01458          0, // 01111111
01459          7, // 10000000
01460         -1, // 10000001
01461         -1, // 10000010
01462         -1, // 10000011
01463         -1, // 10000100
01464         -1, // 10000101
01465         -1, // 10000110
01466         -1, // 10000111
01467         -1, // 10001000
01468         -1, // 10001001
01469         -1, // 10001010
01470         -1, // 10001011
01471         -1, // 10001100
01472         -1, // 10001101
01473         -1, // 10001110
01474         -1, // 10001111
01475         -1, // 10010000
01476         -1, // 10010001
01477         -1, // 10010010
01478         -1, // 10010011
01479         -1, // 10010100
01480         -1, // 10010101
01481         -1, // 10010110
01482         -1, // 10010111
01483         -1, // 10011000
01484         -1, // 10011001
01485         -1, // 10011010
01486         -1, // 10011011
01487         -1, // 10011100
01488         -1, // 10011101
01489         -1, // 10011110
01490         -1, // 10011111
01491         -1, // 10100000
01492         -1, // 10100001
01493         -1, // 10100010
01494         -1, // 10100011
01495         -1, // 10100100
01496         -1, // 10100101
01497         -1, // 10100110
01498         -1, // 10100111
01499         -1, // 10101000
01500         -1, // 10101001
01501         -1, // 10101010
01502         -1, // 10101011
01503         -1, // 10101100
01504         -1, // 10101101
01505         -1, // 10101110
01506         -1, // 10101111
01507         -1, // 10110000
01508         -1, // 10110001
01509         -1, // 10110010
01510         -1, // 10110011
01511         -1, // 10110100
01512         -1, // 10110101
01513         -1, // 10110110
01514         -1, // 10110111
01515         -1, // 10111000
01516         -1, // 10111001
01517         -1, // 10111010
01518         -1, // 10111011
01519         -1, // 10111100
01520         -1, // 10111101
01521         -1, // 10111110
01522         -1, // 10111111
01523         -1, // 11000000
01524         -1, // 11000001
01525         -1, // 11000010
01526         -1, // 11000011
01527         -1, // 11000100
01528         -1, // 11000101
01529         -1, // 11000110
01530         -1, // 11000111
01531         -1, // 11001000
01532         -1, // 11001001
01533         -1, // 11001010
01534         -1, // 11001011
01535         -1, // 11001100
01536         -1, // 11001101
01537         -1, // 11001110
01538         -1, // 11001111
01539         -1, // 11010000
01540         -1, // 11010001
01541         -1, // 11010010
01542         -1, // 11010011
01543         -1, // 11010100
01544         -1, // 11010101
01545         -1, // 11010110
01546         -1, // 11010111
01547         -1, // 11011000
01548         -1, // 11011001
01549         -1, // 11011010
01550         -1, // 11011011
01551         -1, // 11011100
01552         -1, // 11011101
01553         -1, // 11011110
01554         -1, // 11011111
01555         -1, // 11100000
01556         -1, // 11100001
01557         -1, // 11100010
01558         -1, // 11100011
01559         -1, // 11100100
01560         -1, // 11100101
01561         -1, // 11100110
01562         -1, // 11100111
01563         -1, // 11101000
01564         -1, // 11101001
01565         -1, // 11101010
01566         -1, // 11101011
01567         -1, // 11101100
01568         -1, // 11101101
01569         -1, // 11101110
01570         -1, // 11101111
01571         -1, // 11110000
01572         -1, // 11110001
01573         -1, // 11110010
01574         -1, // 11110011
01575         -1, // 11110100
01576         -1, // 11110101
01577         -1, // 11110110
01578         -1, // 11110111
01579         -1, // 11111000
01580         -1, // 11111001
01581         -1, // 11111010
01582         -1, // 11111011
01583         -1, // 11111100
01584         -1, // 11111101
01585         -1, // 11111110
01586          0  // 11111111
01587     };
01588     static char Perms[256][8] = {
01589         { 0, 1, 2, 3, 4, 5, 6, 7 }, // 00000000
01590         { 0, 1, 2, 3, 4, 5, 6, 7 }, // 00000001
01591         { 1, 0, 2, 3, 4, 5, 6, 7 }, // 00000010
01592         { 0, 1, 2, 3, 4, 5, 6, 7 }, // 00000011
01593         { 1, 2, 0, 3, 4, 5, 6, 7 }, // 00000100
01594         { 0, 2, 1, 3, 4, 5, 6, 7 }, // 00000101
01595         { 2, 0, 1, 3, 4, 5, 6, 7 }, // 00000110
01596         { 0, 1, 2, 3, 4, 5, 6, 7 }, // 00000111
01597         { 1, 2, 3, 0, 4, 5, 6, 7 }, // 00001000
01598         { 0, 2, 3, 1, 4, 5, 6, 7 }, // 00001001
01599         { 2, 0, 3, 1, 4, 5, 6, 7 }, // 00001010
01600         { 0, 1, 3, 2, 4, 5, 6, 7 }, // 00001011
01601         { 2, 3, 0, 1, 4, 5, 6, 7 }, // 00001100
01602         { 0, 3, 1, 2, 4, 5, 6, 7 }, // 00001101
01603         { 3, 0, 1, 2, 4, 5, 6, 7 }, // 00001110
01604         { 0, 1, 2, 3, 4, 5, 6, 7 }, // 00001111
01605         { 1, 2, 3, 4, 0, 5, 6, 7 }, // 00010000
01606         { 0, 2, 3, 4, 1, 5, 6, 7 }, // 00010001
01607         { 2, 0, 3, 4, 1, 5, 6, 7 }, // 00010010
01608         { 0, 1, 3, 4, 2, 5, 6, 7 }, // 00010011
01609         { 2, 3, 0, 4, 1, 5, 6, 7 }, // 00010100
01610         { 0, 3, 1, 4, 2, 5, 6, 7 }, // 00010101
01611         { 3, 0, 1, 4, 2, 5, 6, 7 }, // 00010110
01612         { 0, 1, 2, 4, 3, 5, 6, 7 }, // 00010111
01613         { 2, 3, 4, 0, 1, 5, 6, 7 }, // 00011000
01614         { 0, 3, 4, 1, 2, 5, 6, 7 }, // 00011001
01615         { 3, 0, 4, 1, 2, 5, 6, 7 }, // 00011010
01616         { 0, 1, 4, 2, 3, 5, 6, 7 }, // 00011011
01617         { 3, 4, 0, 1, 2, 5, 6, 7 }, // 00011100
01618         { 0, 4, 1, 2, 3, 5, 6, 7 }, // 00011101
01619         { 4, 0, 1, 2, 3, 5, 6, 7 }, // 00011110
01620         { 0, 1, 2, 3, 4, 5, 6, 7 }, // 00011111
01621         { 1, 2, 3, 4, 5, 0, 6, 7 }, // 00100000
01622         { 0, 2, 3, 4, 5, 1, 6, 7 }, // 00100001
01623         { 2, 0, 3, 4, 5, 1, 6, 7 }, // 00100010
01624         { 0, 1, 3, 4, 5, 2, 6, 7 }, // 00100011
01625         { 2, 3, 0, 4, 5, 1, 6, 7 }, // 00100100
01626         { 0, 3, 1, 4, 5, 2, 6, 7 }, // 00100101
01627         { 3, 0, 1, 4, 5, 2, 6, 7 }, // 00100110
01628         { 0, 1, 2, 4, 5, 3, 6, 7 }, // 00100111
01629         { 2, 3, 4, 0, 5, 1, 6, 7 }, // 00101000
01630         { 0, 3, 4, 1, 5, 2, 6, 7 }, // 00101001
01631         { 3, 0, 4, 1, 5, 2, 6, 7 }, // 00101010
01632         { 0, 1, 4, 2, 5, 3, 6, 7 }, // 00101011
01633         { 3, 4, 0, 1, 5, 2, 6, 7 }, // 00101100
01634         { 0, 4, 1, 2, 5, 3, 6, 7 }, // 00101101
01635         { 4, 0, 1, 2, 5, 3, 6, 7 }, // 00101110
01636         { 0, 1, 2, 3, 5, 4, 6, 7 }, // 00101111
01637         { 2, 3, 4, 5, 0, 1, 6, 7 }, // 00110000
01638         { 0, 3, 4, 5, 1, 2, 6, 7 }, // 00110001
01639         { 3, 0, 4, 5, 1, 2, 6, 7 }, // 00110010
01640         { 0, 1, 4, 5, 2, 3, 6, 7 }, // 00110011
01641         { 3, 4, 0, 5, 1, 2, 6, 7 }, // 00110100
01642         { 0, 4, 1, 5, 2, 3, 6, 7 }, // 00110101
01643         { 4, 0, 1, 5, 2, 3, 6, 7 }, // 00110110
01644         { 0, 1, 2, 5, 3, 4, 6, 7 }, // 00110111
01645         { 3, 4, 5, 0, 1, 2, 6, 7 }, // 00111000
01646         { 0, 4, 5, 1, 2, 3, 6, 7 }, // 00111001
01647         { 4, 0, 5, 1, 2, 3, 6, 7 }, // 00111010
01648         { 0, 1, 5, 2, 3, 4, 6, 7 }, // 00111011
01649         { 4, 5, 0, 1, 2, 3, 6, 7 }, // 00111100
01650         { 0, 5, 1, 2, 3, 4, 6, 7 }, // 00111101
01651         { 5, 0, 1, 2, 3, 4, 6, 7 }, // 00111110
01652         { 0, 1, 2, 3, 4, 5, 6, 7 }, // 00111111
01653         { 1, 2, 3, 4, 5, 6, 0, 7 }, // 01000000
01654         { 0, 2, 3, 4, 5, 6, 1, 7 }, // 01000001
01655         { 2, 0, 3, 4, 5, 6, 1, 7 }, // 01000010
01656         { 0, 1, 3, 4, 5, 6, 2, 7 }, // 01000011
01657         { 2, 3, 0, 4, 5, 6, 1, 7 }, // 01000100
01658         { 0, 3, 1, 4, 5, 6, 2, 7 }, // 01000101
01659         { 3, 0, 1, 4, 5, 6, 2, 7 }, // 01000110
01660         { 0, 1, 2, 4, 5, 6, 3, 7 }, // 01000111
01661         { 2, 3, 4, 0, 5, 6, 1, 7 }, // 01001000
01662         { 0, 3, 4, 1, 5, 6, 2, 7 }, // 01001001
01663         { 3, 0, 4, 1, 5, 6, 2, 7 }, // 01001010
01664         { 0, 1, 4, 2, 5, 6, 3, 7 }, // 01001011
01665         { 3, 4, 0, 1, 5, 6, 2, 7 }, // 01001100
01666         { 0, 4, 1, 2, 5, 6, 3, 7 }, // 01001101
01667         { 4, 0, 1, 2, 5, 6, 3, 7 }, // 01001110
01668         { 0, 1, 2, 3, 5, 6, 4, 7 }, // 01001111
01669         { 2, 3, 4, 5, 0, 6, 1, 7 }, // 01010000
01670         { 0, 3, 4, 5, 1, 6, 2, 7 }, // 01010001
01671         { 3, 0, 4, 5, 1, 6, 2, 7 }, // 01010010
01672         { 0, 1, 4, 5, 2, 6, 3, 7 }, // 01010011
01673         { 3, 4, 0, 5, 1, 6, 2, 7 }, // 01010100
01674         { 0, 4, 1, 5, 2, 6, 3, 7 }, // 01010101
01675         { 4, 0, 1, 5, 2, 6, 3, 7 }, // 01010110
01676         { 0, 1, 2, 5, 3, 6, 4, 7 }, // 01010111
01677         { 3, 4, 5, 0, 1, 6, 2, 7 }, // 01011000
01678         { 0, 4, 5, 1, 2, 6, 3, 7 }, // 01011001
01679         { 4, 0, 5, 1, 2, 6, 3, 7 }, // 01011010
01680         { 0, 1, 5, 2, 3, 6, 4, 7 }, // 01011011
01681         { 4, 5, 0, 1, 2, 6, 3, 7 }, // 01011100
01682         { 0, 5, 1, 2, 3, 6, 4, 7 }, // 01011101
01683         { 5, 0, 1, 2, 3, 6, 4, 7 }, // 01011110
01684         { 0, 1, 2, 3, 4, 6, 5, 7 }, // 01011111
01685         { 2, 3, 4, 5, 6, 0, 1, 7 }, // 01100000
01686         { 0, 3, 4, 5, 6, 1, 2, 7 }, // 01100001
01687         { 3, 0, 4, 5, 6, 1, 2, 7 }, // 01100010
01688         { 0, 1, 4, 5, 6, 2, 3, 7 }, // 01100011
01689         { 3, 4, 0, 5, 6, 1, 2, 7 }, // 01100100
01690         { 0, 4, 1, 5, 6, 2, 3, 7 }, // 01100101
01691         { 4, 0, 1, 5, 6, 2, 3, 7 }, // 01100110
01692         { 0, 1, 2, 5, 6, 3, 4, 7 }, // 01100111
01693         { 3, 4, 5, 0, 6, 1, 2, 7 }, // 01101000
01694         { 0, 4, 5, 1, 6, 2, 3, 7 }, // 01101001
01695         { 4, 0, 5, 1, 6, 2, 3, 7 }, // 01101010
01696         { 0, 1, 5, 2, 6, 3, 4, 7 }, // 01101011
01697         { 4, 5, 0, 1, 6, 2, 3, 7 }, // 01101100
01698         { 0, 5, 1, 2, 6, 3, 4, 7 }, // 01101101
01699         { 5, 0, 1, 2, 6, 3, 4, 7 }, // 01101110
01700         { 0, 1, 2, 3, 6, 4, 5, 7 }, // 01101111
01701         { 3, 4, 5, 6, 0, 1, 2, 7 }, // 01110000
01702         { 0, 4, 5, 6, 1, 2, 3, 7 }, // 01110001
01703         { 4, 0, 5, 6, 1, 2, 3, 7 }, // 01110010
01704         { 0, 1, 5, 6, 2, 3, 4, 7 }, // 01110011
01705         { 4, 5, 0, 6, 1, 2, 3, 7 }, // 01110100
01706         { 0, 5, 1, 6, 2, 3, 4, 7 }, // 01110101
01707         { 5, 0, 1, 6, 2, 3, 4, 7 }, // 01110110
01708         { 0, 1, 2, 6, 3, 4, 5, 7 }, // 01110111
01709         { 4, 5, 6, 0, 1, 2, 3, 7 }, // 01111000
01710         { 0, 5, 6, 1, 2, 3, 4, 7 }, // 01111001
01711         { 5, 0, 6, 1, 2, 3, 4, 7 }, // 01111010
01712         { 0, 1, 6, 2, 3, 4, 5, 7 }, // 01111011
01713         { 5, 6, 0, 1, 2, 3, 4, 7 }, // 01111100
01714         { 0, 6, 1, 2, 3, 4, 5, 7 }, // 01111101
01715         { 6, 0, 1, 2, 3, 4, 5, 7 }, // 01111110
01716         { 0, 1, 2, 3, 4, 5, 6, 7 }, // 01111111
01717         { 1, 2, 3, 4, 5, 6, 7, 0 }, // 10000000
01718         { 0, 2, 3, 4, 5, 6, 7, 1 }, // 10000001
01719         { 2, 0, 3, 4, 5, 6, 7, 1 }, // 10000010
01720         { 0, 1, 3, 4, 5, 6, 7, 2 }, // 10000011
01721         { 2, 3, 0, 4, 5, 6, 7, 1 }, // 10000100
01722         { 0, 3, 1, 4, 5, 6, 7, 2 }, // 10000101
01723         { 3, 0, 1, 4, 5, 6, 7, 2 }, // 10000110
01724         { 0, 1, 2, 4, 5, 6, 7, 3 }, // 10000111
01725         { 2, 3, 4, 0, 5, 6, 7, 1 }, // 10001000
01726         { 0, 3, 4, 1, 5, 6, 7, 2 }, // 10001001
01727         { 3, 0, 4, 1, 5, 6, 7, 2 }, // 10001010
01728         { 0, 1, 4, 2, 5, 6, 7, 3 }, // 10001011
01729         { 3, 4, 0, 1, 5, 6, 7, 2 }, // 10001100
01730         { 0, 4, 1, 2, 5, 6, 7, 3 }, // 10001101
01731         { 4, 0, 1, 2, 5, 6, 7, 3 }, // 10001110
01732         { 0, 1, 2, 3, 5, 6, 7, 4 }, // 10001111
01733         { 2, 3, 4, 5, 0, 6, 7, 1 }, // 10010000
01734         { 0, 3, 4, 5, 1, 6, 7, 2 }, // 10010001
01735         { 3, 0, 4, 5, 1, 6, 7, 2 }, // 10010010
01736         { 0, 1, 4, 5, 2, 6, 7, 3 }, // 10010011
01737         { 3, 4, 0, 5, 1, 6, 7, 2 }, // 10010100
01738         { 0, 4, 1, 5, 2, 6, 7, 3 }, // 10010101
01739         { 4, 0, 1, 5, 2, 6, 7, 3 }, // 10010110
01740         { 0, 1, 2, 5, 3, 6, 7, 4 }, // 10010111
01741         { 3, 4, 5, 0, 1, 6, 7, 2 }, // 10011000
01742         { 0, 4, 5, 1, 2, 6, 7, 3 }, // 10011001
01743         { 4, 0, 5, 1, 2, 6, 7, 3 }, // 10011010
01744         { 0, 1, 5, 2, 3, 6, 7, 4 }, // 10011011
01745         { 4, 5, 0, 1, 2, 6, 7, 3 }, // 10011100
01746         { 0, 5, 1, 2, 3, 6, 7, 4 }, // 10011101
01747         { 5, 0, 1, 2, 3, 6, 7, 4 }, // 10011110
01748         { 0, 1, 2, 3, 4, 6, 7, 5 }, // 10011111
01749         { 2, 3, 4, 5, 6, 0, 7, 1 }, // 10100000
01750         { 0, 3, 4, 5, 6, 1, 7, 2 }, // 10100001
01751         { 3, 0, 4, 5, 6, 1, 7, 2 }, // 10100010
01752         { 0, 1, 4, 5, 6, 2, 7, 3 }, // 10100011
01753         { 3, 4, 0, 5, 6, 1, 7, 2 }, // 10100100
01754         { 0, 4, 1, 5, 6, 2, 7, 3 }, // 10100101
01755         { 4, 0, 1, 5, 6, 2, 7, 3 }, // 10100110
01756         { 0, 1, 2, 5, 6, 3, 7, 4 }, // 10100111
01757         { 3, 4, 5, 0, 6, 1, 7, 2 }, // 10101000
01758         { 0, 4, 5, 1, 6, 2, 7, 3 }, // 10101001
01759         { 4, 0, 5, 1, 6, 2, 7, 3 }, // 10101010
01760         { 0, 1, 5, 2, 6, 3, 7, 4 }, // 10101011
01761         { 4, 5, 0, 1, 6, 2, 7, 3 }, // 10101100
01762         { 0, 5, 1, 2, 6, 3, 7, 4 }, // 10101101
01763         { 5, 0, 1, 2, 6, 3, 7, 4 }, // 10101110
01764         { 0, 1, 2, 3, 6, 4, 7, 5 }, // 10101111
01765         { 3, 4, 5, 6, 0, 1, 7, 2 }, // 10110000
01766         { 0, 4, 5, 6, 1, 2, 7, 3 }, // 10110001
01767         { 4, 0, 5, 6, 1, 2, 7, 3 }, // 10110010
01768         { 0, 1, 5, 6, 2, 3, 7, 4 }, // 10110011
01769         { 4, 5, 0, 6, 1, 2, 7, 3 }, // 10110100
01770         { 0, 5, 1, 6, 2, 3, 7, 4 }, // 10110101
01771         { 5, 0, 1, 6, 2, 3, 7, 4 }, // 10110110
01772         { 0, 1, 2, 6, 3, 4, 7, 5 }, // 10110111
01773         { 4, 5, 6, 0, 1, 2, 7, 3 }, // 10111000
01774         { 0, 5, 6, 1, 2, 3, 7, 4 }, // 10111001
01775         { 5, 0, 6, 1, 2, 3, 7, 4 }, // 10111010
01776         { 0, 1, 6, 2, 3, 4, 7, 5 }, // 10111011
01777         { 5, 6, 0, 1, 2, 3, 7, 4 }, // 10111100
01778         { 0, 6, 1, 2, 3, 4, 7, 5 }, // 10111101
01779         { 6, 0, 1, 2, 3, 4, 7, 5 }, // 10111110
01780         { 0, 1, 2, 3, 4, 5, 7, 6 }, // 10111111
01781         { 2, 3, 4, 5, 6, 7, 0, 1 }, // 11000000
01782         { 0, 3, 4, 5, 6, 7, 1, 2 }, // 11000001
01783         { 3, 0, 4, 5, 6, 7, 1, 2 }, // 11000010
01784         { 0, 1, 4, 5, 6, 7, 2, 3 }, // 11000011
01785         { 3, 4, 0, 5, 6, 7, 1, 2 }, // 11000100
01786         { 0, 4, 1, 5, 6, 7, 2, 3 }, // 11000101
01787         { 4, 0, 1, 5, 6, 7, 2, 3 }, // 11000110
01788         { 0, 1, 2, 5, 6, 7, 3, 4 }, // 11000111
01789         { 3, 4, 5, 0, 6, 7, 1, 2 }, // 11001000
01790         { 0, 4, 5, 1, 6, 7, 2, 3 }, // 11001001
01791         { 4, 0, 5, 1, 6, 7, 2, 3 }, // 11001010
01792         { 0, 1, 5, 2, 6, 7, 3, 4 }, // 11001011
01793         { 4, 5, 0, 1, 6, 7, 2, 3 }, // 11001100
01794         { 0, 5, 1, 2, 6, 7, 3, 4 }, // 11001101
01795         { 5, 0, 1, 2, 6, 7, 3, 4 }, // 11001110
01796         { 0, 1, 2, 3, 6, 7, 4, 5 }, // 11001111
01797         { 3, 4, 5, 6, 0, 7, 1, 2 }, // 11010000
01798         { 0, 4, 5, 6, 1, 7, 2, 3 }, // 11010001
01799         { 4, 0, 5, 6, 1, 7, 2, 3 }, // 11010010
01800         { 0, 1, 5, 6, 2, 7, 3, 4 }, // 11010011
01801         { 4, 5, 0, 6, 1, 7, 2, 3 }, // 11010100
01802         { 0, 5, 1, 6, 2, 7, 3, 4 }, // 11010101
01803         { 5, 0, 1, 6, 2, 7, 3, 4 }, // 11010110
01804         { 0, 1, 2, 6, 3, 7, 4, 5 }, // 11010111
01805         { 4, 5, 6, 0, 1, 7, 2, 3 }, // 11011000
01806         { 0, 5, 6, 1, 2, 7, 3, 4 }, // 11011001
01807         { 5, 0, 6, 1, 2, 7, 3, 4 }, // 11011010
01808         { 0, 1, 6, 2, 3, 7, 4, 5 }, // 11011011
01809         { 5, 6, 0, 1, 2, 7, 3, 4 }, // 11011100
01810         { 0, 6, 1, 2, 3, 7, 4, 5 }, // 11011101
01811         { 6, 0, 1, 2, 3, 7, 4, 5 }, // 11011110
01812         { 0, 1, 2, 3, 4, 7, 5, 6 }, // 11011111
01813         { 3, 4, 5, 6, 7, 0, 1, 2 }, // 11100000
01814         { 0, 4, 5, 6, 7, 1, 2, 3 }, // 11100001
01815         { 4, 0, 5, 6, 7, 1, 2, 3 }, // 11100010
01816         { 0, 1, 5, 6, 7, 2, 3, 4 }, // 11100011
01817         { 4, 5, 0, 6, 7, 1, 2, 3 }, // 11100100
01818         { 0, 5, 1, 6, 7, 2, 3, 4 }, // 11100101
01819         { 5, 0, 1, 6, 7, 2, 3, 4 }, // 11100110
01820         { 0, 1, 2, 6, 7, 3, 4, 5 }, // 11100111
01821         { 4, 5, 6, 0, 7, 1, 2, 3 }, // 11101000
01822         { 0, 5, 6, 1, 7, 2, 3, 4 }, // 11101001
01823         { 5, 0, 6, 1, 7, 2, 3, 4 }, // 11101010
01824         { 0, 1, 6, 2, 7, 3, 4, 5 }, // 11101011
01825         { 5, 6, 0, 1, 7, 2, 3, 4 }, // 11101100
01826         { 0, 6, 1, 2, 7, 3, 4, 5 }, // 11101101
01827         { 6, 0, 1, 2, 7, 3, 4, 5 }, // 11101110
01828         { 0, 1, 2, 3, 7, 4, 5, 6 }, // 11101111
01829         { 4, 5, 6, 7, 0, 1, 2, 3 }, // 11110000
01830         { 0, 5, 6, 7, 1, 2, 3, 4 }, // 11110001
01831         { 5, 0, 6, 7, 1, 2, 3, 4 }, // 11110010
01832         { 0, 1, 6, 7, 2, 3, 4, 5 }, // 11110011
01833         { 5, 6, 0, 7, 1, 2, 3, 4 }, // 11110100
01834         { 0, 6, 1, 7, 2, 3, 4, 5 }, // 11110101
01835         { 6, 0, 1, 7, 2, 3, 4, 5 }, // 11110110
01836         { 0, 1, 2, 7, 3, 4, 5, 6 }, // 11110111
01837         { 5, 6, 7, 0, 1, 2, 3, 4 }, // 11111000
01838         { 0, 6, 7, 1, 2, 3, 4, 5 }, // 11111001
01839         { 6, 0, 7, 1, 2, 3, 4, 5 }, // 11111010
01840         { 0, 1, 7, 2, 3, 4, 5, 6 }, // 11111011
01841         { 6, 7, 0, 1, 2, 3, 4, 5 }, // 11111100
01842         { 0, 7, 1, 2, 3, 4, 5, 6 }, // 11111101
01843         { 7, 0, 1, 2, 3, 4, 5, 6 }, // 11111110
01844         { 0, 1, 2, 3, 4, 5, 6, 7 }  // 11111111
01845     };
01846 
01847     assert( uPhase > 0 && uPhase < (unsigned)(1 << nVars) );
01848 
01849     // the same function
01850     if ( Cases[uPhase] == 0 )
01851     {
01852         int i;
01853         for ( i = 0; i < nWords; i++ )
01854             puTruthR[i] = puTruth[i];
01855         return;
01856     }
01857 
01858     // an elementary variable
01859     if ( Cases[uPhase] > 0 )
01860     {
01861         int i;
01862         for ( i = 0; i < nWords; i++ )
01863             puTruthR[i] = uTruths[Cases[uPhase]][i];
01864         return;
01865     }
01866 
01867     // truth table takes one word
01868     if ( nWords == 1 )
01869     {
01870         int i, k, nMints, iRes;
01871         char * pPerm = Perms[uPhase];
01872         puTruthR[0] = 0;
01873         nMints = (1 << nVars);
01874         for ( i = 0; i < nMints; i++ )
01875             if ( puTruth[0] & (1 << i) )
01876             {
01877                 for ( iRes = 0, k = 0; k < nVars; k++ )
01878                     if ( i & (1 << pPerm[k]) )
01879                         iRes |= (1 << k);
01880                 puTruthR[0] |= (1 << iRes);
01881             }
01882         return;
01883     }
01884     else if ( nWords == 2 )
01885     {
01886         int i, k, iRes;
01887         char * pPerm = Perms[uPhase];
01888         puTruthR[0] = puTruthR[1] = 0;
01889         for ( i = 0; i < 32; i++ )
01890         {
01891             if ( puTruth[0] & (1 << i) )
01892             {
01893                 for ( iRes = 0, k = 0; k < 6; k++ )
01894                     if ( i & (1 << pPerm[k]) )
01895                         iRes |= (1 << k);
01896                 if ( iRes < 32 )
01897                     puTruthR[0] |= (1 << iRes);
01898                 else
01899                     puTruthR[1] |= (1 << (iRes-32));
01900             }
01901         }
01902         for ( ; i < 64; i++ )
01903         {
01904             if ( puTruth[1] & (1 << (i-32)) )
01905             {
01906                 for ( iRes = 0, k = 0; k < 6; k++ )
01907                     if ( i & (1 << pPerm[k]) )
01908                         iRes |= (1 << k);
01909                 if ( iRes < 32 )
01910                     puTruthR[0] |= (1 << iRes);
01911                 else
01912                     puTruthR[1] |= (1 << (iRes-32));
01913             }
01914         }
01915     }
01916     // truth table takes more than one word
01917     else
01918     {
01919         int i, k, nMints, iRes;
01920         char * pPerm = Perms[uPhase];
01921         for ( i = 0; i < nWords; i++ )
01922             puTruthR[i] = 0;
01923         nMints = (1 << nVars);
01924         for ( i = 0; i < nMints; i++ )
01925             if ( puTruth[i>>5] & (1 << (i&31)) )
01926             {
01927                 for ( iRes = 0, k = 0; k < 5; k++ )
01928                     if ( i & (1 << pPerm[k]) )
01929                         iRes |= (1 << k);
01930                 puTruthR[iRes>>5] |= (1 << (iRes&31));
01931             }
01932     }
01933 }

void Extra_TruthExpandGeneratePermTable (  ) 

Function*************************************************************

Synopsis [Computes the permutation table for 8 variables.]

Description []

SideEffects []

SeeAlso []

Definition at line 2176 of file extraUtilMisc.c.

02177 {
02178     int i, k, nOnes, Last1, First0;
02179     int iOne, iZero;
02180 
02181     printf( "\nstatic char Cases[256] = {\n" );
02182     for ( i = 0; i < 256; i++ )
02183     {
02184         nOnes = 0;
02185         Last1 = First0 = -1;
02186         for ( k = 0; k < 8; k++ )
02187         {
02188             if ( i & (1 << k) )
02189             {
02190                 nOnes++;
02191                 Last1 = k;
02192             }
02193             else if ( First0 == -1 )
02194                 First0 = k;
02195         }
02196         if ( Last1 + 1 == First0 || i == 255 )
02197             printf( "     %d%s", 0, (i==255? " ":",") );
02198         else if ( nOnes == 1 )
02199             printf( "     %d,", Last1 );
02200         else
02201             printf( "    -%d,", 1 );
02202         printf( " // " );
02203         Extra_PrintBinary( stdout, (unsigned*)&i, 8 );
02204         printf( "\n" );
02205     }
02206     printf( "};\n" );
02207 
02208     printf( "\nstatic char Perms[256][8] = {\n" );
02209     for ( i = 0; i < 256; i++ )
02210     {
02211         printf( "    {" );
02212         nOnes = 0;
02213         for ( k = 0; k < 8; k++ )
02214             if ( i & (1 << k) )
02215                 nOnes++;
02216         iOne = 0;
02217         iZero = nOnes;
02218         for ( k = 0; k < 8; k++ )
02219             if ( i & (1 << k) )
02220                 printf( "%s %d", (k==0? "":","), iOne++ );
02221             else
02222                 printf( "%s %d", (k==0? "":","), iZero++ );
02223         assert( iOne + iZero == 8 );
02224         printf( " }%s // ", (i==255? " ":",") );
02225         Extra_PrintBinary( stdout, (unsigned*)&i, 8 );
02226         printf( "\n" );
02227     }
02228     printf( "};\n" );
02229 }

unsigned short** Extra_TruthPerm43 (  ) 

Function*************************************************************

Synopsis [Allocated lookup table for truth table permutation.]

Description []

SideEffects []

SeeAlso []

Definition at line 1946 of file extraUtilMisc.c.

01947 {
01948     unsigned short ** pTable;
01949     unsigned uTruth;
01950     int i, k;
01951     pTable = (unsigned short **)Extra_ArrayAlloc( 256, 16, 2 );
01952     for ( i = 0; i < 256; i++ )
01953     {
01954         uTruth = (i << 8) | i;
01955         for ( k = 0; k < 16; k++ )
01956             pTable[i][k] = Extra_TruthPerm4One( uTruth, k );
01957     }
01958     return pTable;
01959 }

unsigned short Extra_TruthPerm4One ( unsigned  uTruth,
int  Phase 
)

Function*************************************************************

Synopsis [Computes a phase of the 3-var function.]

Description []

SideEffects []

SeeAlso []

Definition at line 943 of file extraUtilMisc.c.

00944 {
00945     // cases
00946     static unsigned short Cases[16] = {
00947         0,      // 0000  - skip
00948         0,      // 0001  - skip
00949         0xCCCC, // 0010  - single var
00950         0,      // 0011  - skip
00951         0xF0F0, // 0100  - single var
00952         1,      // 0101
00953         1,      // 0110
00954         0,      // 0111  - skip
00955         0xFF00, // 1000  - single var
00956         1,      // 1001
00957         1,      // 1010
00958         1,      // 1011
00959         1,      // 1100
00960         1,      // 1101
00961         1,      // 1110
00962         0       // 1111  - skip
00963     };
00964     // permutations
00965     static int Perms[16][4] = {
00966         { 0, 0, 0, 0 }, // 0000  - skip
00967         { 0, 0, 0, 0 }, // 0001  - skip
00968         { 0, 0, 0, 0 }, // 0010  - single var
00969         { 0, 0, 0, 0 }, // 0011  - skip
00970         { 0, 0, 0, 0 }, // 0100  - single var
00971         { 0, 2, 1, 3 }, // 0101
00972         { 2, 0, 1, 3 }, // 0110
00973         { 0, 0, 0, 0 }, // 0111  - skip
00974         { 0, 0, 0, 0 }, // 1000  - single var
00975         { 0, 2, 3, 1 }, // 1001
00976         { 2, 0, 3, 1 }, // 1010
00977         { 0, 1, 3, 2 }, // 1011
00978         { 2, 3, 0, 1 }, // 1100
00979         { 0, 3, 1, 2 }, // 1101
00980         { 3, 0, 1, 2 }, // 1110
00981         { 0, 0, 0, 0 }  // 1111  - skip
00982     };
00983     int i, k, iRes;
00984     unsigned uTruthRes;
00985     assert( Phase >= 0 && Phase < 16 );
00986     if ( Cases[Phase] == 0 )
00987         return uTruth;
00988     if ( Cases[Phase] > 1 )
00989         return Cases[Phase];
00990     uTruthRes = 0;
00991     for ( i = 0; i < 16; i++ )
00992         if ( uTruth & (1 << i) )
00993         {
00994             for ( iRes = 0, k = 0; k < 4; k++ )
00995                 if ( i & (1 << Perms[Phase][k]) )
00996                     iRes |= (1 << k);
00997             uTruthRes |= (1 << iRes);
00998         }
00999     return uTruthRes;
01000 }

unsigned** Extra_TruthPerm53 (  ) 

Function*************************************************************

Synopsis [Allocated lookup table for truth table permutation.]

Description []

SideEffects []

SeeAlso []

Definition at line 1972 of file extraUtilMisc.c.

01973 {
01974     unsigned ** pTable;
01975     unsigned uTruth;
01976     int i, k;
01977     pTable = (unsigned **)Extra_ArrayAlloc( 256, 32, 4 );
01978     for ( i = 0; i < 256; i++ )
01979     {
01980         uTruth = (i << 24) | (i << 16) | (i << 8) | i;
01981         for ( k = 0; k < 32; k++ )
01982             pTable[i][k] = Extra_TruthPerm5One( uTruth, k );
01983     }
01984     return pTable;
01985 }

unsigned** Extra_TruthPerm54 (  ) 

Function*************************************************************

Synopsis [Allocated lookup table for truth table permutation.]

Description []

SideEffects []

SeeAlso []

Definition at line 1998 of file extraUtilMisc.c.

01999 {
02000     unsigned ** pTable;
02001     unsigned uTruth;
02002     int i;
02003     pTable = (unsigned **)Extra_ArrayAlloc( 256*256, 4, 4 );
02004     for ( i = 0; i < 256*256; i++ )
02005     {
02006         uTruth = (i << 16) | i;
02007         pTable[i][0] = Extra_TruthPerm5One( uTruth, 31-8 );
02008         pTable[i][1] = Extra_TruthPerm5One( uTruth, 31-4 );
02009         pTable[i][2] = Extra_TruthPerm5One( uTruth, 31-2 );
02010         pTable[i][3] = Extra_TruthPerm5One( uTruth, 31-1 );
02011     }
02012     return pTable;
02013 }

unsigned Extra_TruthPerm5One ( unsigned  uTruth,
int  Phase 
)

Function*************************************************************

Synopsis [Computes a phase of the 3-var function.]

Description []

SideEffects []

SeeAlso []

Definition at line 1013 of file extraUtilMisc.c.

01014 {
01015     // cases
01016     static unsigned Cases[32] = {
01017         0,          // 00000  - skip
01018         0,          // 00001  - skip
01019         0xCCCCCCCC, // 00010  - single var
01020         0,          // 00011  - skip
01021         0xF0F0F0F0, // 00100  - single var
01022         1,          // 00101
01023         1,          // 00110
01024         0,          // 00111  - skip
01025         0xFF00FF00, // 01000  - single var
01026         1,          // 01001
01027         1,          // 01010
01028         1,          // 01011
01029         1,          // 01100
01030         1,          // 01101
01031         1,          // 01110
01032         0,          // 01111  - skip
01033         0xFFFF0000, // 10000  - skip
01034         1,          // 10001
01035         1,          // 10010
01036         1,          // 10011
01037         1,          // 10100
01038         1,          // 10101
01039         1,          // 10110
01040         1,          // 10111  - four var
01041         1,          // 11000
01042         1,          // 11001
01043         1,          // 11010
01044         1,          // 11011  - four var
01045         1,          // 11100
01046         1,          // 11101  - four var
01047         1,          // 11110  - four var
01048         0           // 11111  - skip
01049     };
01050     // permutations
01051     static int Perms[32][5] = {
01052         { 0, 0, 0, 0, 0 }, // 00000  - skip
01053         { 0, 0, 0, 0, 0 }, // 00001  - skip
01054         { 0, 0, 0, 0, 0 }, // 00010  - single var
01055         { 0, 0, 0, 0, 0 }, // 00011  - skip
01056         { 0, 0, 0, 0, 0 }, // 00100  - single var
01057         { 0, 2, 1, 3, 4 }, // 00101
01058         { 2, 0, 1, 3, 4 }, // 00110
01059         { 0, 0, 0, 0, 0 }, // 00111  - skip
01060         { 0, 0, 0, 0, 0 }, // 01000  - single var
01061         { 0, 2, 3, 1, 4 }, // 01001
01062         { 2, 0, 3, 1, 4 }, // 01010
01063         { 0, 1, 3, 2, 4 }, // 01011
01064         { 2, 3, 0, 1, 4 }, // 01100
01065         { 0, 3, 1, 2, 4 }, // 01101
01066         { 3, 0, 1, 2, 4 }, // 01110
01067         { 0, 0, 0, 0, 0 }, // 01111  - skip
01068         { 0, 0, 0, 0, 0 }, // 10000  - single var
01069         { 0, 4, 2, 3, 1 }, // 10001
01070         { 4, 0, 2, 3, 1 }, // 10010
01071         { 0, 1, 3, 4, 2 }, // 10011
01072         { 2, 3, 0, 4, 1 }, // 10100
01073         { 0, 3, 1, 4, 2 }, // 10101
01074         { 3, 0, 1, 4, 2 }, // 10110
01075         { 0, 1, 2, 4, 3 }, // 10111  - four var
01076         { 2, 3, 4, 0, 1 }, // 11000
01077         { 0, 3, 4, 1, 2 }, // 11001
01078         { 3, 0, 4, 1, 2 }, // 11010
01079         { 0, 1, 4, 2, 3 }, // 11011  - four var
01080         { 3, 4, 0, 1, 2 }, // 11100
01081         { 0, 4, 1, 2, 3 }, // 11101  - four var
01082         { 4, 0, 1, 2, 3 }, // 11110  - four var
01083         { 0, 0, 0, 0, 0 }  // 11111  - skip
01084     };
01085     int i, k, iRes;
01086     unsigned uTruthRes;
01087     assert( Phase >= 0 && Phase < 32 );
01088     if ( Cases[Phase] == 0 )
01089         return uTruth;
01090     if ( Cases[Phase] > 1 )
01091         return Cases[Phase];
01092     uTruthRes = 0;
01093     for ( i = 0; i < 32; i++ )
01094         if ( uTruth & (1 << i) )
01095         {
01096             for ( iRes = 0, k = 0; k < 5; k++ )
01097                 if ( i & (1 << Perms[Phase][k]) )
01098                     iRes |= (1 << k);
01099             uTruthRes |= (1 << iRes);
01100         }
01101     return uTruthRes;
01102 }

unsigned** Extra_TruthPerm63 (  ) 

Function*************************************************************

Synopsis [Allocated lookup table for truth table permutation.]

Description []

SideEffects []

SeeAlso []

Definition at line 2026 of file extraUtilMisc.c.

02027 {
02028     unsigned ** pTable;
02029     unsigned uTruth[2];
02030     int i, k;
02031     pTable = (unsigned **)Extra_ArrayAlloc( 256, 64, 8 );
02032     for ( i = 0; i < 256; i++ )
02033     {
02034         uTruth[0] = (i << 24) | (i << 16) | (i << 8) | i;
02035         uTruth[1] = uTruth[0];
02036         for ( k = 0; k < 64; k++ )
02037             Extra_TruthPerm6One( uTruth, k, &pTable[i][k] );
02038     }
02039     return pTable;
02040 }

void Extra_TruthPerm6One ( unsigned *  uTruth,
int  Phase,
unsigned *  uTruthRes 
)

Function*************************************************************

Synopsis [Computes a phase of the 3-var function.]

Description []

SideEffects []

SeeAlso []

Definition at line 1115 of file extraUtilMisc.c.

01116 {
01117     // cases
01118     static unsigned Cases[64] = {
01119         0,          // 000000  - skip
01120         0,          // 000001  - skip
01121         0xCCCCCCCC, // 000010  - single var
01122         0,          // 000011  - skip
01123         0xF0F0F0F0, // 000100  - single var
01124         1,          // 000101
01125         1,          // 000110
01126         0,          // 000111  - skip
01127         0xFF00FF00, // 001000  - single var
01128         1,          // 001001
01129         1,          // 001010
01130         1,          // 001011
01131         1,          // 001100
01132         1,          // 001101
01133         1,          // 001110
01134         0,          // 001111  - skip
01135         0xFFFF0000, // 010000  - skip
01136         1,          // 010001
01137         1,          // 010010
01138         1,          // 010011
01139         1,          // 010100
01140         1,          // 010101
01141         1,          // 010110
01142         1,          // 010111  - four var
01143         1,          // 011000
01144         1,          // 011001
01145         1,          // 011010
01146         1,          // 011011  - four var
01147         1,          // 011100
01148         1,          // 011101  - four var
01149         1,          // 011110  - four var
01150         0,          // 011111  - skip
01151         0xFFFFFFFF, // 100000  - single var
01152         1,          // 100001 
01153         1,          // 100010  
01154         1,          // 100011  
01155         1,          // 100100  
01156         1,          // 100101
01157         1,          // 100110
01158         1,          // 100111  
01159         1,          // 101000  
01160         1,          // 101001
01161         1,          // 101010
01162         1,          // 101011
01163         1,          // 101100
01164         1,          // 101101
01165         1,          // 101110
01166         1,          // 101111  
01167         1,          // 110000  
01168         1,          // 110001
01169         1,          // 110010
01170         1,          // 110011
01171         1,          // 110100
01172         1,          // 110101
01173         1,          // 110110
01174         1,          // 110111  
01175         1,          // 111000
01176         1,          // 111001
01177         1,          // 111010
01178         1,          // 111011  
01179         1,          // 111100
01180         1,          // 111101  
01181         1,          // 111110  
01182         0           // 111111  - skip
01183     };
01184     // permutations
01185     static int Perms[64][6] = {
01186         { 0, 0, 0, 0, 0, 0 }, // 000000  - skip
01187         { 0, 0, 0, 0, 0, 0 }, // 000001  - skip
01188         { 0, 0, 0, 0, 0, 0 }, // 000010  - single var
01189         { 0, 0, 0, 0, 0, 0 }, // 000011  - skip
01190         { 0, 0, 0, 0, 0, 0 }, // 000100  - single var
01191         { 0, 2, 1, 3, 4, 5 }, // 000101
01192         { 2, 0, 1, 3, 4, 5 }, // 000110
01193         { 0, 0, 0, 0, 0, 0 }, // 000111  - skip
01194         { 0, 0, 0, 0, 0, 0 }, // 001000  - single var
01195         { 0, 2, 3, 1, 4, 5 }, // 001001
01196         { 2, 0, 3, 1, 4, 5 }, // 001010
01197         { 0, 1, 3, 2, 4, 5 }, // 001011
01198         { 2, 3, 0, 1, 4, 5 }, // 001100
01199         { 0, 3, 1, 2, 4, 5 }, // 001101
01200         { 3, 0, 1, 2, 4, 5 }, // 001110
01201         { 0, 0, 0, 0, 0, 0 }, // 001111  - skip
01202         { 0, 0, 0, 0, 0, 0 }, // 010000  - skip
01203         { 0, 4, 2, 3, 1, 5 }, // 010001
01204         { 4, 0, 2, 3, 1, 5 }, // 010010
01205         { 0, 1, 3, 4, 2, 5 }, // 010011
01206         { 2, 3, 0, 4, 1, 5 }, // 010100
01207         { 0, 3, 1, 4, 2, 5 }, // 010101
01208         { 3, 0, 1, 4, 2, 5 }, // 010110
01209         { 0, 1, 2, 4, 3, 5 }, // 010111  - four var
01210         { 2, 3, 4, 0, 1, 5 }, // 011000
01211         { 0, 3, 4, 1, 2, 5 }, // 011001
01212         { 3, 0, 4, 1, 2, 5 }, // 011010
01213         { 0, 1, 4, 2, 3, 5 }, // 011011  - four var
01214         { 3, 4, 0, 1, 2, 5 }, // 011100
01215         { 0, 4, 1, 2, 3, 5 }, // 011101  - four var
01216         { 4, 0, 1, 2, 3, 5 }, // 011110  - four var
01217         { 0, 0, 0, 0, 0, 0 }, // 011111  - skip
01218         { 0, 0, 0, 0, 0, 0 }, // 100000  - single var
01219         { 0, 2, 3, 4, 5, 1 }, // 100001 
01220         { 2, 0, 3, 4, 5, 1 }, // 100010  
01221         { 0, 1, 3, 4, 5, 2 }, // 100011  
01222         { 2, 3, 0, 4, 5, 1 }, // 100100  
01223         { 0, 3, 1, 4, 5, 2 }, // 100101
01224         { 3, 0, 1, 4, 5, 2 }, // 100110
01225         { 0, 1, 2, 4, 5, 3 }, // 100111  
01226         { 2, 3, 4, 0, 5, 1 }, // 101000  
01227         { 0, 3, 4, 1, 5, 2 }, // 101001
01228         { 3, 0, 4, 1, 5, 2 }, // 101010
01229         { 0, 1, 4, 2, 5, 3 }, // 101011
01230         { 3, 4, 0, 1, 5, 2 }, // 101100
01231         { 0, 4, 1, 2, 5, 3 }, // 101101
01232         { 4, 0, 1, 2, 5, 3 }, // 101110
01233         { 0, 1, 2, 3, 5, 4 }, // 101111  
01234         { 2, 3, 4, 5, 0, 1 }, // 110000  
01235         { 0, 3, 4, 5, 1, 2 }, // 110001
01236         { 3, 0, 4, 5, 1, 2 }, // 110010
01237         { 0, 1, 4, 5, 2, 3 }, // 110011
01238         { 3, 4, 0, 5, 1, 2 }, // 110100
01239         { 0, 4, 1, 5, 2, 3 }, // 110101
01240         { 4, 0, 1, 5, 2, 3 }, // 110110
01241         { 0, 1, 2, 5, 3, 4 }, // 110111  
01242         { 3, 4, 5, 0, 1, 2 }, // 111000
01243         { 0, 4, 5, 1, 2, 3 }, // 111001
01244         { 4, 0, 5, 1, 2, 3 }, // 111010
01245         { 0, 1, 5, 2, 3, 4 }, // 111011  
01246         { 4, 5, 0, 1, 2, 3 }, // 111100
01247         { 0, 5, 1, 2, 3, 4 }, // 111101  
01248         { 5, 0, 1, 2, 3, 4 }, // 111110  
01249         { 0, 0, 0, 0, 0, 0 }  // 111111  - skip
01250     };
01251     int i, k, iRes;
01252     assert( Phase >= 0 && Phase < 64 );
01253     if ( Cases[Phase] == 0 )
01254     {
01255         uTruthRes[0] = uTruth[0];
01256         uTruthRes[1] = uTruth[1];
01257         return;
01258     }
01259     if ( Cases[Phase] > 1 )
01260     {
01261         if ( Phase == 32 )
01262         {
01263             uTruthRes[0] = 0x00000000;
01264             uTruthRes[1] = 0xFFFFFFFF;
01265         }
01266         else
01267         {
01268             uTruthRes[0] = Cases[Phase];
01269             uTruthRes[1] = Cases[Phase];
01270         }
01271         return;
01272     }
01273     uTruthRes[0] = 0;
01274     uTruthRes[1] = 0;
01275     for ( i = 0; i < 64; i++ )
01276     {
01277         if ( i < 32 )
01278         {
01279             if ( uTruth[0] & (1 << i) )
01280             {
01281                 for ( iRes = 0, k = 0; k < 6; k++ )
01282                     if ( i & (1 << Perms[Phase][k]) )
01283                         iRes |= (1 << k);
01284                 if ( iRes < 32 )
01285                     uTruthRes[0] |= (1 << iRes);
01286                 else
01287                     uTruthRes[1] |= (1 << (iRes-32));
01288             }
01289         }
01290         else
01291         {
01292             if ( uTruth[1] & (1 << (i-32)) )
01293             {
01294                 for ( iRes = 0, k = 0; k < 6; k++ )
01295                     if ( i & (1 << Perms[Phase][k]) )
01296                         iRes |= (1 << k);
01297                 if ( iRes < 32 )
01298                     uTruthRes[0] |= (1 << iRes);
01299                 else
01300                     uTruthRes[1] |= (1 << (iRes-32));
01301             }
01302         }
01303     }
01304 }

unsigned Extra_TruthPermute ( unsigned  Truth,
char *  pPerms,
int  nVars,
int  fReverse 
)

Function*************************************************************

Synopsis [Permutes the function.]

Description []

SideEffects []

SeeAlso []

Definition at line 390 of file extraUtilMisc.c.

00391 {
00392     unsigned Result;
00393     int * pMints;
00394     int * pMintsP;
00395     int nMints;
00396     int i, m;
00397 
00398     assert( nVars < 6 );
00399     nMints  = (1 << nVars);
00400     pMints  = ALLOC( int, nMints );
00401     pMintsP = ALLOC( int, nMints );
00402     for ( i = 0; i < nMints; i++ )
00403         pMints[i] = i;
00404 
00405     Extra_TruthPermute_int( pMints, nMints, pPerms, nVars, pMintsP );
00406 
00407     Result = 0;
00408     if ( fReverse )
00409     {
00410         for ( m = 0; m < nMints; m++ )
00411             if ( Truth & (1 << pMintsP[m]) )
00412                 Result |= (1 << m);
00413     }
00414     else
00415     {
00416         for ( m = 0; m < nMints; m++ )
00417             if ( Truth & (1 << m) )
00418                 Result |= (1 << pMintsP[m]);
00419     }
00420 
00421     free( pMints );
00422     free( pMintsP );
00423 
00424     return Result;
00425 }

void Extra_TruthPermute_int ( int *  pMints,
int  nMints,
char *  pPerm,
int  nVars,
int *  pMintsP 
)

Function*************************************************************

Synopsis [Permutes the given vector of minterms.]

Description []

SideEffects []

SeeAlso []

Definition at line 367 of file extraUtilMisc.c.

00368 {
00369     int m, v;
00370     // clean the storage for minterms
00371     memset( pMintsP, 0, sizeof(int) * nMints );
00372     // go through minterms and add the variables
00373     for ( m = 0; m < nMints; m++ )
00374         for ( v = 0; v < nVars; v++ )
00375             if ( pMints[m] & (1 << v) )
00376                 pMintsP[m] |= (1 << pPerm[v]);
00377 }

unsigned Extra_TruthPolarize ( unsigned  uTruth,
int  Polarity,
int  nVars 
)

Function*************************************************************

Synopsis [Changes the phase of the function.]

Description []

SideEffects []

SeeAlso []

Definition at line 438 of file extraUtilMisc.c.

00439 {
00440     // elementary truth tables
00441     static unsigned Signs[5] = {
00442         0xAAAAAAAA,    // 1010 1010 1010 1010 1010 1010 1010 1010
00443         0xCCCCCCCC,    // 1010 1010 1010 1010 1010 1010 1010 1010
00444         0xF0F0F0F0,    // 1111 0000 1111 0000 1111 0000 1111 0000
00445         0xFF00FF00,    // 1111 1111 0000 0000 1111 1111 0000 0000
00446         0xFFFF0000     // 1111 1111 1111 1111 0000 0000 0000 0000
00447     };
00448     unsigned uTruthRes, uCof0, uCof1;
00449     int nMints, Shift, v;
00450     assert( nVars < 6 );
00451     nMints = (1 << nVars);
00452     uTruthRes = uTruth;
00453     for ( v = 0; v < nVars; v++ )
00454         if ( Polarity & (1 << v) )
00455         {
00456             uCof0  = uTruth & ~Signs[v];
00457             uCof1  = uTruth &  Signs[v];
00458             Shift  = (1 << v);
00459             uCof0 <<= Shift;
00460             uCof1 >>= Shift;
00461             uTruth = uCof0 | uCof1;
00462         }
00463     return uTruth;
00464 }

unsigned** Extra_Truths8 (  ) 

Function*************************************************************

Synopsis [Returns the pointer to the elementary truth tables.]

Description []

SideEffects []

SeeAlso []

Definition at line 2053 of file extraUtilMisc.c.

02054 {
02055     static unsigned uTruths[8][8] = {
02056         { 0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA,0xAAAAAAAA },
02057         { 0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC,0xCCCCCCCC },
02058         { 0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0,0xF0F0F0F0 },
02059         { 0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00,0xFF00FF00 },
02060         { 0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000,0xFFFF0000 }, 
02061         { 0x00000000,0xFFFFFFFF,0x00000000,0xFFFFFFFF,0x00000000,0xFFFFFFFF,0x00000000,0xFFFFFFFF }, 
02062         { 0x00000000,0x00000000,0xFFFFFFFF,0xFFFFFFFF,0x00000000,0x00000000,0xFFFFFFFF,0xFFFFFFFF }, 
02063         { 0x00000000,0x00000000,0x00000000,0x00000000,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF } 
02064     };
02065     static unsigned * puResult[8] = {
02066         uTruths[0], uTruths[1], uTruths[2], uTruths[3], uTruths[4], uTruths[5], uTruths[6], uTruths[7] 
02067     };
02068     return (unsigned **)puResult;
02069 }

Generated on Tue Jan 5 12:19:15 2010 for abc70930 by  doxygen 1.6.1