src/map/mapper/mapperCanon.c File Reference

#include "mapperInt.h"
Include dependency graph for mapperCanon.c:

Go to the source code of this file.

Functions

static unsigned Map_CanonComputePhase (unsigned uTruths[][2], int nVars, unsigned uTruth, unsigned uPhase)
static void Map_CanonComputePhase6 (unsigned uTruths[][2], int nVars, unsigned uTruth[], unsigned uPhase, unsigned uTruthRes[])
int Map_CanonComputeSlow (unsigned uTruths[][2], int nVarsMax, int nVarsReal, unsigned uTruth[], unsigned char *puPhases, unsigned uTruthRes[])
int Map_CanonComputeFast (Map_Man_t *p, int nVarsMax, int nVarsReal, unsigned uTruth[], unsigned char *puPhases, unsigned uTruthRes[])

Function Documentation

int Map_CanonComputeFast ( Map_Man_t *  p,
int  nVarsMax,
int  nVarsReal,
unsigned  uTruth[],
unsigned char *  puPhases,
unsigned  uTruthRes[] 
)

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

Synopsis [Computes the N-canonical form of the Boolean function.]

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.]

SideEffects []

SeeAlso []

Definition at line 170 of file mapperCanon.c.

00171 {
00172     unsigned uTruth0, uTruth1;
00173     unsigned uCanon0, uCanon1, uCanonBest, uPhaseBest;
00174     int i, Limit;
00175 
00176     if ( nVarsMax == 6 )
00177         return Map_CanonComputeSlow( p->uTruths, nVarsMax, nVarsReal, uTruth, puPhases, uTruthRes );
00178 
00179     if ( nVarsReal < 5 )
00180     {
00181 //        return Map_CanonComputeSlow( p->uTruths, nVarsMax, nVarsReal, uTruth, puPhases, uTruthRes );
00182 
00183         uTruth0 = uTruth[0] & 0xFFFF;
00184         assert( p->pCounters[uTruth0] > 0 );
00185         uTruthRes[0] = (p->uCanons[uTruth0] << 16) | p->uCanons[uTruth0];
00186         uTruthRes[1] = uTruthRes[0];
00187         puPhases[0] = p->uPhases[uTruth0][0];
00188         return 1;
00189     }
00190 
00191     assert( nVarsMax == 5 );
00192     assert( nVarsReal == 5 );
00193     uTruth0 = uTruth[0] & 0xFFFF;
00194     uTruth1 = (uTruth[0] >> 16);
00195     if ( uTruth1 == 0 )
00196     {
00197         uTruthRes[0] = p->uCanons[uTruth0];
00198         uTruthRes[1] = uTruthRes[0];
00199         Limit = (p->pCounters[uTruth0] > 4)? 4 : p->pCounters[uTruth0];
00200         for ( i = 0; i < Limit; i++ )
00201             puPhases[i] = p->uPhases[uTruth0][i];
00202         return Limit;
00203     }
00204     else if ( uTruth0 == 0 )
00205     {
00206         uTruthRes[0] = p->uCanons[uTruth1];
00207         uTruthRes[1] = uTruthRes[0];
00208         Limit = (p->pCounters[uTruth1] > 4)? 4 : p->pCounters[uTruth1];
00209         for ( i = 0; i < Limit; i++ )
00210         {
00211             puPhases[i] = p->uPhases[uTruth1][i];
00212             puPhases[i] |= (1 << 4);
00213         }
00214         return Limit;
00215     }
00216     uCanon0 = p->uCanons[uTruth0];
00217     uCanon1 = p->uCanons[uTruth1];
00218     if ( uCanon0 >= uCanon1 ) // using nCanon1 as the main one
00219     {
00220         assert( p->pCounters[uTruth1] > 0 );
00221         uCanonBest = 0xFFFFFFFF;
00222         for ( i = 0; i < p->pCounters[uTruth1]; i++ )
00223         {
00224             uCanon0 = Extra_TruthPolarize( uTruth0, p->uPhases[uTruth1][i], 4 );
00225             if ( uCanonBest > uCanon0 )
00226             {
00227                 uCanonBest = uCanon0;
00228                 uPhaseBest = p->uPhases[uTruth1][i];
00229                 assert( uPhaseBest < 16 );
00230             }
00231         }
00232         uTruthRes[0] = (uCanon1 << 16) | uCanonBest;
00233         uTruthRes[1] = uTruthRes[0];
00234         puPhases[0] = uPhaseBest;
00235         return 1;
00236     }
00237     else if ( uCanon0 < uCanon1 )
00238     {
00239         assert( p->pCounters[uTruth0] > 0 );
00240         uCanonBest = 0xFFFFFFFF;
00241         for ( i = 0; i < p->pCounters[uTruth0]; i++ )
00242         {
00243             uCanon1 = Extra_TruthPolarize( uTruth1, p->uPhases[uTruth0][i], 4 );
00244             if ( uCanonBest > uCanon1 )
00245             {
00246                 uCanonBest = uCanon1;
00247                 uPhaseBest = p->uPhases[uTruth0][i];
00248                 assert( uPhaseBest < 16 );
00249             }
00250         }
00251         uTruthRes[0] = (uCanon0 << 16) | uCanonBest;
00252         uTruthRes[1] = uTruthRes[0];
00253         puPhases[0] = uPhaseBest | (1 << 4);
00254         return 1;
00255     }
00256     else
00257     {
00258         assert( 0 );
00259         return Map_CanonComputeSlow( p->uTruths, nVarsMax, nVarsReal, uTruth, puPhases, uTruthRes );
00260     }
00261 }

unsigned Map_CanonComputePhase ( unsigned  uTruths[][2],
int  nVars,
unsigned  uTruth,
unsigned  uPhase 
) [static]

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

FileName [mapperCanon.c]

PackageName [MVSIS 1.3: Multi-valued logic synthesis system.]

Synopsis [Generic technology mapping engine.]

Author [MVSIS Group]

Affiliation [UC Berkeley]

Date [Ver. 2.0. Started - June 1, 2004.]

Revision [

Id
mapperCanon.c,v 1.2 2005/01/23 06:59:42 alanmi Exp

] DECLARATIONS ///

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

Synopsis [Performs phase transformation for one function of less than 6 variables.]

Description []

SideEffects []

SeeAlso []

Definition at line 109 of file mapperCanon.c.

00110 {
00111     int v, Shift;
00112     for ( v = 0, Shift = 1; v < nVars; v++, Shift <<= 1 )
00113         if ( uPhase & Shift )
00114             uTruth = (((uTruth & ~uTruths[v][0]) << Shift) | ((uTruth & uTruths[v][0]) >> Shift));
00115     return uTruth;
00116 }

void Map_CanonComputePhase6 ( unsigned  uTruths[][2],
int  nVars,
unsigned  uTruth[],
unsigned  uPhase,
unsigned  uTruthRes[] 
) [static]

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

Synopsis [Performs phase transformation for one function of 6 variables.]

Description []

SideEffects []

SeeAlso []

Definition at line 129 of file mapperCanon.c.

00130 {
00131     unsigned uTemp;
00132     int v, Shift;
00133 
00134     // initialize the result
00135     uTruthRes[0] = uTruth[0];
00136     uTruthRes[1] = uTruth[1];
00137     if ( uPhase == 0 )
00138         return;
00139     // compute the phase 
00140     for ( v = 0, Shift = 1; v < nVars; v++, Shift <<= 1 )
00141         if ( uPhase & Shift )
00142         {
00143             if ( Shift < 32 )
00144             {
00145                 uTruthRes[0] = (((uTruthRes[0] & ~uTruths[v][0]) << Shift) | ((uTruthRes[0] & uTruths[v][0]) >> Shift));
00146                 uTruthRes[1] = (((uTruthRes[1] & ~uTruths[v][1]) << Shift) | ((uTruthRes[1] & uTruths[v][1]) >> Shift));
00147             }
00148             else
00149             {
00150                 uTemp        = uTruthRes[0];
00151                 uTruthRes[0] = uTruthRes[1];
00152                 uTruthRes[1] = uTemp;
00153             }
00154         }
00155 }

int Map_CanonComputeSlow ( unsigned  uTruths[][2],
int  nVarsMax,
int  nVarsReal,
unsigned  uTruth[],
unsigned char *  puPhases,
unsigned  uTruthRes[] 
)

FUNCTION DEFINITIONS ///Function*************************************************************

Synopsis [Computes the N-canonical form of the Boolean function.]

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.]

SideEffects []

SeeAlso []

Definition at line 45 of file mapperCanon.c.

00046 {
00047     unsigned  uTruthPerm[2];
00048     int nMints, nPhases, m;
00049 
00050     nPhases = 0;
00051     nMints = (1 << nVarsReal);
00052     if ( nVarsMax < 6 )
00053     {
00054         uTruthRes[0] = MAP_MASK(32);
00055         for ( m = 0; m < nMints; m++ )
00056         {
00057             uTruthPerm[0] = Map_CanonComputePhase( uTruths, nVarsMax, uTruth[0], m );
00058             if ( uTruthRes[0] > uTruthPerm[0] )
00059             {
00060                 uTruthRes[0] = uTruthPerm[0];
00061                 nPhases      = 0;
00062                 puPhases[nPhases++] = (unsigned char)m;
00063             }
00064             else if ( uTruthRes[0] == uTruthPerm[0] )
00065             {
00066                 if ( nPhases < 4 ) // the max number of phases in Map_Super_t
00067                     puPhases[nPhases++] = (unsigned char)m;
00068             }
00069         }
00070         uTruthRes[1] = uTruthRes[0];
00071     }
00072     else
00073     {
00074         uTruthRes[0] = MAP_MASK(32);
00075         uTruthRes[1] = MAP_MASK(32);
00076         for ( m = 0; m < nMints; m++ )
00077         {
00078             Map_CanonComputePhase6( uTruths, nVarsMax, uTruth, m, uTruthPerm );
00079             if ( uTruthRes[1] > uTruthPerm[1] || uTruthRes[1] == uTruthPerm[1] && uTruthRes[0] > uTruthPerm[0] )
00080             {
00081                 uTruthRes[0] = uTruthPerm[0];
00082                 uTruthRes[1] = uTruthPerm[1];
00083                 nPhases      = 0;
00084                 puPhases[nPhases++] = (unsigned char)m;
00085             }
00086             else if ( uTruthRes[1] == uTruthPerm[1] && uTruthRes[0] == uTruthPerm[0] )
00087             {
00088                 if ( nPhases < 4 ) // the max number of phases in Map_Super_t
00089                     puPhases[nPhases++] = (unsigned char)m;
00090             }
00091         }
00092     }
00093     assert( nPhases > 0 );
00094 //    printf( "%d ", nPhases );
00095     return nPhases;
00096 }

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