Fxch.c

Go to the documentation of this file.

#include "Fxch.h"
 
ABC_NAMESPACE_IMPL_START


void Fxch_CubesGruping(Fxch_Man_t* pFxchMan)
{
    Vec_Int_t* vCube;
    int iCube, nOutputs, SizeOutputID;
    Hsh_VecMan_t* pCubeHash;
 
    /* Identify the number of Outputs and create the translation table */
    pFxchMan->vTranslation = Vec_IntAlloc( 32 );
    Vec_WecForEachLevel( pFxchMan->vCubes, vCube, iCube )
    {
        int Id = Vec_IntEntry( vCube, 0 );
        int iTranslation = Vec_IntFind( pFxchMan->vTranslation, Id );
 
        if ( iTranslation == -1 )
            Vec_IntPush( pFxchMan->vTranslation, Id );
    }
    nOutputs = Vec_IntSize( pFxchMan->vTranslation );
 
    /* Size of the OutputID in number o ints */
    SizeOutputID = ( nOutputs >> 5 ) + ( ( nOutputs & 31 ) > 0 );
 
    /* Initialize needed structures */
    pFxchMan->vOutputID = Vec_IntAlloc( 4096 );
    pFxchMan->pTempOutputID = ABC_CALLOC( int, SizeOutputID );
    pFxchMan->nSizeOutputID = SizeOutputID;
 
    pCubeHash =  Hsh_VecManStart( 1024 );
 
    /* Identify equal cubes */
    Vec_WecForEachLevel( pFxchMan->vCubes, vCube, iCube )
    {
        int Id = Vec_IntEntry( vCube, 0 );
        int iTranslation = Vec_IntFind( pFxchMan->vTranslation, Id );
        int i, iCubeNoID, Temp, * pEntry;
        Vec_IntWriteEntry( vCube, 0, 0 ); // Clear ID, Outputs will be identified by it later
 
        iCubeNoID = Hsh_VecManAdd( pCubeHash, vCube );
        Temp = ( 1 << ( iTranslation & 31 ) );
        if ( iCubeNoID == Vec_IntSize( pFxchMan->vOutputID ) / SizeOutputID )
        {
            for ( i = 0; i < SizeOutputID; i++ )
                pFxchMan->pTempOutputID[i] = 0;
 
            pFxchMan->pTempOutputID[ iTranslation >> 5 ] = Temp;
            Vec_IntPushArray( pFxchMan->vOutputID, pFxchMan->pTempOutputID, SizeOutputID ); 
        }
        else
        {
            Vec_IntClear( vCube );
            pEntry = Vec_IntEntryP( pFxchMan->vOutputID, ( iCubeNoID * SizeOutputID ) + ( iTranslation >> 5 ) );
            *pEntry |= Temp;
        }
    }
 
    Hsh_VecManStop( pCubeHash );
    Vec_WecRemoveEmpty( pFxchMan->vCubes );
}

void Fxch_CubesUnGruping(Fxch_Man_t* pFxchMan)
{
    int iCube;
    int i, j;
    Vec_Int_t* vCube;
    Vec_Int_t* vNewCube;
 
    assert( Vec_WecSize( pFxchMan->vCubes ) == ( Vec_IntSize( pFxchMan->vOutputID ) / pFxchMan->nSizeOutputID ) );
    Vec_WecForEachLevel( pFxchMan->vCubes, vCube, iCube )
    {
        int * pOutputID, nOnes;
        if ( Vec_IntSize( vCube ) == 0 || Vec_IntEntry( vCube, 0 ) != 0 )
            continue;
 
        pOutputID = Vec_IntEntryP( pFxchMan->vOutputID, iCube * pFxchMan->nSizeOutputID );
        nOnes = 0;
 
        for ( i = 0; i < pFxchMan->nSizeOutputID; i++ )
            nOnes += Fxch_CountOnes( (unsigned int) pOutputID[i] );
 
        for ( i = 0; i < pFxchMan->nSizeOutputID && nOnes; i++ )
            for ( j = 0; j < 32 && nOnes; j++ )
                if ( pOutputID[i] & ( 1 << j ) )
                {
                    if ( nOnes == 1 )
                        Vec_IntWriteEntry( vCube, 0, Vec_IntEntry( pFxchMan->vTranslation, ( i << 5 ) | j ) );
                    else
                    {
                        vNewCube = Vec_WecPushLevel( pFxchMan->vCubes );
                        Vec_IntAppend( vNewCube, vCube );
                        Vec_IntWriteEntry( vNewCube, 0, Vec_IntEntry( pFxchMan->vTranslation, (i << 5 ) | j ) );
                    }
                    nOnes -= 1;
                }
    }
 
    Vec_IntFree( pFxchMan->vTranslation );
    Vec_IntFree( pFxchMan->vOutputID );
    ABC_FREE( pFxchMan->pTempOutputID );
    return;
}

int Fxch_FastExtract( Vec_Wec_t* vCubes,
                      int ObjIdMax,
                      int nMaxDivExt,
                      int fVerbose,
                      int fVeryVerbose )
{
    abctime TempTime;
    Fxch_Man_t* pFxchMan = Fxch_ManAlloc( vCubes );
    int i;
 
    TempTime = Abc_Clock();
    Fxch_CubesGruping( pFxchMan );
    Fxch_ManMapLiteralsIntoCubes( pFxchMan, ObjIdMax );
    Fxch_ManGenerateLitHashKeys( pFxchMan );
    Fxch_ManComputeLevel( pFxchMan );
    Fxch_ManSCHashTablesInit( pFxchMan );
    Fxch_ManDivCreate( pFxchMan );
    pFxchMan->timeInit = Abc_Clock() - TempTime;
 
    if ( fVeryVerbose )
        Fxch_ManPrintDivs( pFxchMan );
 
    if ( fVerbose )
        Fxch_ManPrintStats( pFxchMan );
 
    TempTime = Abc_Clock();
    
    for ( i = 0; (!nMaxDivExt || i < nMaxDivExt) && Vec_QueTopPriority( pFxchMan->vDivPrio ) > 0.0; i++ )
    {
        int iDiv = Vec_QuePop( pFxchMan->vDivPrio );
 
        if ( fVeryVerbose )
            Fxch_DivPrint( pFxchMan, iDiv );
 
        Fxch_ManUpdate( pFxchMan, iDiv );
    }
   
    pFxchMan->timeExt = Abc_Clock() - TempTime;
 
    if ( fVerbose )
    {
        Fxch_ManPrintStats( pFxchMan );
        Abc_PrintTime( 1, "\n[FXCH] Elapsed Time", pFxchMan->timeInit + pFxchMan->timeExt );
        Abc_PrintTime( 1, "[FXCH]    +-> Init", pFxchMan->timeInit );
        Abc_PrintTime( 1, "[FXCH]    +-> Extr", pFxchMan->timeExt );
    }
 
    Fxch_CubesUnGruping( pFxchMan );
    Fxch_ManSCHashTablesFree( pFxchMan );
    Fxch_ManFree( pFxchMan );
 
    Vec_WecRemoveEmpty( vCubes );
    Vec_WecSortByFirstInt( vCubes, 0 );
 
    return 1;
}

int Abc_NtkFxchPerform( Abc_Ntk_t* pNtk,
                        int nMaxDivExt,
                        int fVerbose,
                        int fVeryVerbose )
{
    Vec_Wec_t* vCubes;
 
    assert( Abc_NtkIsSopLogic( pNtk ) );
 
    if ( !Abc_NtkFxCheck( pNtk ) )
    {
        printf( "Abc_NtkFxchPerform(): Nodes have duplicated fanins. FXCH is not performed.\n" );
        return 0;
    }
 
    vCubes = Abc_NtkFxRetrieve( pNtk );
    if ( Fxch_FastExtract( vCubes, Abc_NtkObjNumMax( pNtk ), nMaxDivExt, fVerbose, fVeryVerbose ) > 0 )
    {
        Abc_NtkFxInsert( pNtk, vCubes );
        Vec_WecFree( vCubes );
 
        if ( !Abc_NtkCheck( pNtk ) )
            printf( "Abc_NtkFxchPerform(): The network check has failed.\n" );
 
        return 1;
    }
    else
        printf( "Warning: The network has not been changed by \"fxch\".\n" );
 
    Vec_WecFree( vCubes );
 
    return 0;
}

 
ABC_NAMESPACE_IMPL_END