src/misc/extra/extraUtilCanon.c File Reference

#include "extra.h"

Include dependency graph for extraUtilCanon.c:

Functions
static int	Extra_TruthCanonN_rec (int nVars, unsigned char pt, unsigned pptRes, char *ppfRes, int Flag)
int	Extra_TruthCanonFastN (int nVarsMax, int nVarsReal, unsigned pt, unsigned pptRes, char *ppfRes)
void	Map_Var3Print ()
void	Map_Var3Test ()
void	Map_Var4Test ()
Variables
static unsigned	s_Truths3 [256]
static char	s_Phases3 [256][9]

Function Documentation

int Extra_TruthCanonFastN	(	int	nVarsMax,
		int	nVarsReal,
		unsigned *	pt,
		unsigned **	pptRes,
		char **	ppfRes
	)

AutomaticEnd Function********************************************************************

Synopsis [Computes the N-canonical form of the Boolean function up to 6 inputs.]

Description [The N-canonical form is defined as the truth table with the minimum integer value. This function exhaustively enumerates through the complete set of 2^N phase assignments. Returns pointers to the static storage to the truth table and phases. This data should be used before the function is called again.]

SideEffects []

SeeAlso []

Definition at line 76 of file extraUtilCanon.c.

00077 {
00078     static unsigned uTruthStore6[2];
00079     int RetValue;
00080     assert( nVarsMax <= 6 );
00081     assert( nVarsReal <= nVarsMax );
00082     RetValue = Extra_TruthCanonN_rec( nVarsReal <= 3? 3: nVarsReal, (unsigned char *)pt, pptRes, ppfRes, 0 );
00083     if ( nVarsMax == 6 && nVarsReal < nVarsMax )
00084     {
00085         uTruthStore6[0] = **pptRes;
00086         uTruthStore6[1] = **pptRes;
00087         *pptRes = uTruthStore6;
00088     }
00089     return RetValue;
00090 }

int Extra_TruthCanonN_rec	(	int	nVars,
		unsigned char *	pt,
		unsigned **	pptRes,
		char **	ppfRes,
		int	Flag
	)			`[static]`

AutomaticStart

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

Synopsis [Recursive implementation of the above.]

Description []

SideEffects [This procedure has a bug, which shows on Solaris. Most likely has something to do with the casts, i.g *((unsigned *)pt0)]

SeeAlso []

Definition at line 108 of file extraUtilCanon.c.

00110 00111 00112 00113 00114 00115 00116 00117 00118 00119 00120 00121     { 00122 00123 00124 00125     } 00126 00127 00128 00129 00130 00131 00132 00133 00134 00135 00136     { 00137 00138 00139     } 00140 00141     { 00142 00143 00144     } 00145 00146     { 00147 00148 00149     } 00150 00151 00152 00153 00154 00155 00156 00157     { 00158 00159 00160 00161 00162 00163 00164 00165     } 00166 00167     { 00168 00169 00170 00171 00172 00173 00174 00175     } 00176 00177 00178     { 00179 00180 00181 00182 00183 00184 00185 00186     } 00187 00188     { 00189 00190 00191 00192 00193 00194 00195 00196     } 00197 00198 00199 00200 00201 00202 00203 00204     { 00205 00206 00207 00208         { 00209 00210 00211 00212 00213 00214 00215 00216 00217 00218         } 00219 00220     } 00221 00222     { 00223 00224 00225 00226         { 00227 00228 00229 00230 00231 00232 00233 00234 00235 00236         } 00237 00238     } 00239 00240     { 00241 00242 00243 00244 00245 00246 00247 00248 00249     } 00250 00251 finish : 00252 00253     { 00254 00255 00256 00257 00258     } 00259 00260     { 00261 00262 00263 00264     } 00265 00266     { 00267 00268 00269     } 00270 00271 00272 00273 00274 }

class="fragment">00109 { static unsigned uTruthStore[7][2][2]; static char uPhaseStore[7][2][64]; unsigned char * pt0, * pt1; unsigned * ptRes0, * ptRes1, * ptRes; unsigned uInit0, uInit1, uTruth0, uTruth1, uTemp; char * pfRes0, * pfRes1, * pfRes; int nf0, nf1, nfRes, i, nVarsN; // table lookup for three vars if ( nVars == 3 ) *pptRes = &s_Truths3[*pt]; *ppfRes = s_Phases3[*pt]+1; return s_Phases3[*pt][0]; // number of vars for the next call nVarsN = nVars-1; // truth table for the next call pt0 = pt; pt1 = pt + (1 << nVarsN) / 8; // 5-var truth tables for this call // uInit0 = *((unsigned *)pt0); // uInit1 = *((unsigned *)pt1); if ( nVarsN == 3 ) uInit0 = (pt0[0] << 24) | (pt0[0] << 16) | (pt0[0] << 8) | pt0[0]; uInit1 = (pt1[0] << 24) | (pt1[0] << 16) | (pt1[0] << 8) | pt1[0]; else if ( nVarsN == 4 ) uInit0 = (pt0[1] << 24) | (pt0[0] << 16) | (pt0[1] << 8) | pt0[0]; uInit1 = (pt1[1] << 24) | (pt1[0] << 16) | (pt1[1] << 8) | pt1[0]; else uInit0 = (pt0[3] << 24) | (pt0[2] << 16) | (pt0[1] << 8) | pt0[0]; uInit1 = (pt1[3] << 24) | (pt1[2] << 16) | (pt1[1] << 8) | pt1[0]; // storage for truth tables and phases ptRes = uTruthStore[nVars][Flag]; pfRes = uPhaseStore[nVars][Flag]; // solve trivial cases if ( uInit1 == 0 ) nf0 = Extra_TruthCanonN_rec( nVarsN, pt0, &ptRes0, &pfRes0, 0 ); uTruth1 = uInit1; uTruth0 = *ptRes0; nfRes = 0; for ( i = 0; i < nf0; i++ ) pfRes[nfRes++] = pfRes0[i]; goto finish; if ( uInit0 == 0 ) nf1 = Extra_TruthCanonN_rec( nVarsN, pt1, &ptRes1, &pfRes1, 1 ); uTruth1 = uInit0; uTruth0 = *ptRes1; nfRes = 0; for ( i = 0; i < nf1; i++ ) pfRes[nfRes++] = pfRes1[i] | (1<<nVarsN); goto finish; if ( uInit1 == 0xFFFFFFFF ) nf0 = Extra_TruthCanonN_rec( nVarsN, pt0, &ptRes0, &pfRes0, 0 ); uTruth1 = *ptRes0; uTruth0 = uInit1; nfRes = 0; for ( i = 0; i < nf0; i++ ) pfRes[nfRes++] = pfRes0[i] | (1<<nVarsN); goto finish; if ( uInit0 == 0xFFFFFFFF ) nf1 = Extra_TruthCanonN_rec( nVarsN, pt1, &ptRes1, &pfRes1, 1 ); uTruth1 = *ptRes1; uTruth0 = uInit0; nfRes = 0; for ( i = 0; i < nf1; i++ ) pfRes[nfRes++] = pfRes1[i]; goto finish; // solve the problem for cofactors nf0 = Extra_TruthCanonN_rec( nVarsN, pt0, &ptRes0, &pfRes0, 0 ); nf1 = Extra_TruthCanonN_rec( nVarsN, pt1, &ptRes1, &pfRes1, 1 ); // combine the result if ( *ptRes1 < *ptRes0 ) uTruth0 = 0xFFFFFFFF; nfRes = 0; for ( i = 0; i < nf1; i++ ) uTemp = Extra_TruthPolarize( uInit0, pfRes1[i], nVarsN ); if ( uTruth0 > uTemp ) { nfRes = 0; uTruth0 = uTemp; pfRes[nfRes++] = pfRes1[i]; } else if ( uTruth0 == uTemp ) pfRes[nfRes++] = pfRes1[i]; uTruth1 = *ptRes1; else if ( *ptRes1 > *ptRes0 ) uTruth0 = 0xFFFFFFFF; nfRes = 0; for ( i = 0; i < nf0; i++ ) uTemp = Extra_TruthPolarize( uInit1, pfRes0[i], nVarsN ); if ( uTruth0 > uTemp ) { nfRes = 0; uTruth0 = uTemp; pfRes[nfRes++] = pfRes0[i] | (1<<nVarsN); } else if ( uTruth0 == uTemp ) pfRes[nfRes++] = pfRes0[i] | (1<<nVarsN); uTruth1 = *ptRes0; else assert( nf0 == nf1 ); nfRes = 0; for ( i = 0; i < nf1; i++ ) pfRes[nfRes++] = pfRes1[i]; for ( i = 0; i < nf0; i++ ) pfRes[nfRes++] = pfRes0[i] | (1<<nVarsN); uTruth0 = Extra_TruthPolarize( uInit0, pfRes1[0], nVarsN ); uTruth1 = *ptRes0; if ( nVarsN == 3 ) uTruth0 &= 0xFF; uTruth1 &= 0xFF; uTemp = (uTruth1 << 8) | uTruth0; *ptRes = (uTemp << 16) | uTemp; else if ( nVarsN == 4 ) uTruth0 &= 0xFFFF; uTruth1 &= 0xFFFF; *ptRes = (uTruth1 << 16) | uTruth0; else if ( nVarsN == 5 ) *(ptRes+0) = uTruth0; *(ptRes+1) = uTruth1; *pptRes = ptRes; *ppfRes = pfRes; return nfRes;

void Map_Var3Print ( )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 287 of file extraUtilCanon.c.

00288 {
00289     extern void Extra_Truth3VarN( unsigned ** puCanons, char *** puPhases, char ** ppCounters );
00290 
00291     unsigned * uCanons;
00292     char ** uPhases;
00293     char * pCounters;
00294     int i, k;
00295 
00296     Extra_Truth3VarN( &uCanons, &uPhases, &pCounters );
00297 
00298     for ( i = 0; i < 256; i++ )
00299     {
00300         if ( i % 8 == 0 )
00301             printf( "\n" );
00302         Extra_PrintHex( stdout, uCanons[i], 5 ); 
00303         printf( ", " );
00304     }
00305     printf( "\n" );
00306 
00307     for ( i = 0; i < 256; i++ )
00308     {
00309         printf( "%3d */  { %2d,   ", i, pCounters[i] );
00310         for ( k = 0; k < pCounters[i]; k++ )            
00311             printf( "%s%d", k? ", ":"", uPhases[i][k] );
00312         printf( " }\n" );
00313     }
00314     printf( "\n" );
00315 }

void Map_Var3Test ( )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 328 of file extraUtilCanon.c.

00329 {
00330     extern void Extra_Truth3VarN( unsigned ** puCanons, char *** puPhases, char ** ppCounters );
00331 
00332     unsigned * uCanons;
00333     char ** uPhases;
00334     char * pCounters;
00335     int i;
00336     unsigned * ptRes;
00337     char * pfRes;
00338     unsigned uTruth;
00339     int Count;
00340 
00341     Extra_Truth3VarN( &uCanons, &uPhases, &pCounters );
00342 
00343     for ( i = 0; i < 256; i++ )
00344     {
00345         uTruth = i;
00346         Count =  Extra_TruthCanonFastN( 5, 3, &uTruth, &ptRes, &pfRes );
00347         if ( *ptRes != uCanons[i] || Count != pCounters[i] )
00348         {
00349             int k = 0;
00350         }
00351     }
00352 }

void Map_Var4Test ( )

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

Synopsis []

Description []

SideEffects []

SeeAlso []

Definition at line 365 of file extraUtilCanon.c.

00366 {
00367     extern void Extra_Truth4VarN( unsigned short ** puCanons, char *** puPhases, char ** ppCounters, int PhaseMax );
00368 
00369     unsigned short * uCanons;
00370     char ** uPhases;
00371     char * pCounters;
00372     int i, k;
00373     unsigned * ptRes;
00374     char * pfRes;
00375     unsigned uTruth;
00376     int Count;
00377 
00378     Extra_Truth4VarN( &uCanons, &uPhases, &pCounters, 16 );
00379 
00380     for ( i = 0; i < 256*256; i++ )
00381     {
00382         uTruth = i;
00383         Count =  Extra_TruthCanonFastN( 5, 4, &uTruth, &ptRes, &pfRes );
00384         if ( (*ptRes & 0xFFFF) != uCanons[i] || Count != pCounters[i] )
00385         {
00386             int k = 0;
00387         }
00388         for ( k = 0; k < Count; k++ )
00389             if ( uPhases[i][k] != pfRes[k] )
00390             {
00391                 int v = 0;
00392             }
00393     }
00394 }

Variable Documentation

static char s_Phases3 [static]

Definition at line 40 of file extraUtilCanon.c.

static unsigned s_Truths3 [static]

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

FileName [extraUtilMisc.c]

SystemName [ABC: Logic synthesis and verification system.]

PackageName [extra]

Synopsis [Computing canonical forms of Boolean functions using truth tables.]

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

]

Definition at line 39 of file extraUtilCanon.c.

src/misc/extra/extraUtilCanon.c File Reference

Functions

Variables

Function Documentation

Variable Documentation