mapperCanon.c

/**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 $]

***********************************************************************/

#include "mapperInt.h"

ABC_NAMESPACE_IMPL_START


////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

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[] );

////////////////////////////////////////////////////////////////////////
///                     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     []

***********************************************************************/
int Map_CanonComputeSlow( unsigned uTruths[][2], int nVarsMax, int nVarsReal, unsigned uTruth[], unsigned char * puPhases, unsigned uTruthRes[] )
{
    unsigned  uTruthPerm[2];
    int nMints, nPhases, m;

    nPhases = 0;
    nMints = (1 << nVarsReal);
    if ( nVarsMax < 6 )
    {
        uTruthRes[0] = MAP_MASK(32);
        for ( m = 0; m < nMints; m++ )
        {
            uTruthPerm[0] = Map_CanonComputePhase( uTruths, nVarsMax, uTruth[0], m );
            if ( uTruthRes[0] > uTruthPerm[0] )
            {
                uTruthRes[0] = uTruthPerm[0];
                nPhases      = 0;
                puPhases[nPhases++] = (unsigned char)m;
            }
            else if ( uTruthRes[0] == uTruthPerm[0] )
            {
                if ( nPhases < 4 ) // the max number of phases in Map_Super_t
                    puPhases[nPhases++] = (unsigned char)m;
            }
        }
        uTruthRes[1] = uTruthRes[0];
    }
    else
    {
        uTruthRes[0] = MAP_MASK(32);
        uTruthRes[1] = MAP_MASK(32);
        for ( m = 0; m < nMints; m++ )
        {
            Map_CanonComputePhase6( uTruths, nVarsMax, uTruth, m, uTruthPerm );
            if ( uTruthRes[1] > uTruthPerm[1] || (uTruthRes[1] == uTruthPerm[1] && uTruthRes[0] > uTruthPerm[0]) )
            {
                uTruthRes[0] = uTruthPerm[0];
                uTruthRes[1] = uTruthPerm[1];
                nPhases      = 0;
                puPhases[nPhases++] = (unsigned char)m;
            }
            else if ( uTruthRes[1] == uTruthPerm[1] && uTruthRes[0] == uTruthPerm[0] )
            {
                if ( nPhases < 4 ) // the max number of phases in Map_Super_t
                    puPhases[nPhases++] = (unsigned char)m;
            }
        }
    }
    assert( nPhases > 0 );
//    printf( "%d ", nPhases );
    return nPhases;
}

/**Function*************************************************************

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
unsigned Map_CanonComputePhase( unsigned uTruths[][2], int nVars, unsigned uTruth, unsigned uPhase )
{
    int v, Shift;
    for ( v = 0, Shift = 1; v < nVars; v++, Shift <<= 1 )
        if ( uPhase & Shift )
            uTruth = (((uTruth & ~uTruths[v][0]) << Shift) | ((uTruth & uTruths[v][0]) >> Shift));
    return uTruth;
}

/**Function*************************************************************

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

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Map_CanonComputePhase6( unsigned uTruths[][2], int nVars, unsigned uTruth[], unsigned uPhase, unsigned uTruthRes[] )
{
    unsigned uTemp;
    int v, Shift;

    // initialize the result
    uTruthRes[0] = uTruth[0];
    uTruthRes[1] = uTruth[1];
    if ( uPhase == 0 )
        return;
    // compute the phase 
    for ( v = 0, Shift = 1; v < nVars; v++, Shift <<= 1 )
        if ( uPhase & Shift )
        {
            if ( Shift < 32 )
            {
                uTruthRes[0] = (((uTruthRes[0] & ~uTruths[v][0]) << Shift) | ((uTruthRes[0] & uTruths[v][0]) >> Shift));
                uTruthRes[1] = (((uTruthRes[1] & ~uTruths[v][1]) << Shift) | ((uTruthRes[1] & uTruths[v][1]) >> Shift));
            }
            else
            {
                uTemp        = uTruthRes[0];
                uTruthRes[0] = uTruthRes[1];
                uTruthRes[1] = uTemp;
            }
        }
}

/**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     []

***********************************************************************/
int Map_CanonComputeFast( Map_Man_t * p, int nVarsMax, int nVarsReal, unsigned uTruth[], unsigned char * puPhases, unsigned uTruthRes[] )
{
    unsigned uTruth0, uTruth1;
    unsigned uCanon0, uCanon1, uCanonBest;
    unsigned uPhaseBest = 16; // Suppress "might be used uninitialized" (asserts require < 16)
    int i, Limit;

    if ( nVarsMax == 6 )
        return Map_CanonComputeSlow( p->uTruths, nVarsMax, nVarsReal, uTruth, puPhases, uTruthRes );

    if ( nVarsReal < 5 )
    {
//        return Map_CanonComputeSlow( p->uTruths, nVarsMax, nVarsReal, uTruth, puPhases, uTruthRes );

        uTruth0 = uTruth[0] & 0xFFFF;
        assert( p->pCounters[uTruth0] > 0 );
        uTruthRes[0] = (p->uCanons[uTruth0] << 16) | p->uCanons[uTruth0];
        uTruthRes[1] = uTruthRes[0];
        puPhases[0] = p->uPhases[uTruth0][0];
        return 1;
    }

    assert( nVarsMax == 5 );
    assert( nVarsReal == 5 );
    uTruth0 = uTruth[0] & 0xFFFF;
    uTruth1 = (uTruth[0] >> 16);
    if ( uTruth1 == 0 )
    {
        uTruthRes[0] = p->uCanons[uTruth0];
        uTruthRes[1] = uTruthRes[0];
        Limit = (p->pCounters[uTruth0] > 4)? 4 : p->pCounters[uTruth0];
        for ( i = 0; i < Limit; i++ )
            puPhases[i] = p->uPhases[uTruth0][i];
        return Limit;
    }
    else if ( uTruth0 == 0 )
    {
        uTruthRes[0] = p->uCanons[uTruth1];
        uTruthRes[1] = uTruthRes[0];
        Limit = (p->pCounters[uTruth1] > 4)? 4 : p->pCounters[uTruth1];
        for ( i = 0; i < Limit; i++ )
        {
            puPhases[i] = p->uPhases[uTruth1][i];
            puPhases[i] |= (1 << 4);
        }
        return Limit;
    }
    uCanon0 = p->uCanons[uTruth0];
    uCanon1 = p->uCanons[uTruth1];
    if ( uCanon0 >= uCanon1 ) // using nCanon1 as the main one
    {
        assert( p->pCounters[uTruth1] > 0 );
        uCanonBest = 0xFFFFFFFF;
        for ( i = 0; i < p->pCounters[uTruth1]; i++ )
        {
            uCanon0 = Extra_TruthPolarize( uTruth0, p->uPhases[uTruth1][i], 4 );
            if ( uCanonBest > uCanon0 )
            {
                uCanonBest = uCanon0;
                uPhaseBest = p->uPhases[uTruth1][i];
                assert( uPhaseBest < 16 );
            }
        }
        uTruthRes[0] = (uCanon1 << 16) | uCanonBest;
        uTruthRes[1] = uTruthRes[0];
        puPhases[0] = uPhaseBest;
        return 1;
    }
    else if ( uCanon0 < uCanon1 )
    {
        assert( p->pCounters[uTruth0] > 0 );
        uCanonBest = 0xFFFFFFFF;
        for ( i = 0; i < p->pCounters[uTruth0]; i++ )
        {
            uCanon1 = Extra_TruthPolarize( uTruth1, p->uPhases[uTruth0][i], 4 );
            if ( uCanonBest > uCanon1 )
            {
                uCanonBest = uCanon1;
                uPhaseBest = p->uPhases[uTruth0][i];
                assert( uPhaseBest < 16 );
            }
        }
        uTruthRes[0] = (uCanon0 << 16) | uCanonBest;
        uTruthRes[1] = uTruthRes[0];
        puPhases[0] = uPhaseBest | (1 << 4);
        return 1;
    }
    else
    {
        assert( 0 );
        return Map_CanonComputeSlow( p->uTruths, nVarsMax, nVarsReal, uTruth, puPhases, uTruthRes );
    }
}





////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


ABC_NAMESPACE_IMPL_END