luckySwap.c

Go to the documentation of this file.

/**CFile****************************************************************

  FileName    [luckySwap.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Semi-canonical form computation package.]

  Synopsis    [Swapping variables in the truth table.]

  Author      [Jake]

  Date        [Started - August 2012]

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

#include "luckyInt.h"


ABC_NAMESPACE_IMPL_START


static word mask0[6] = { ABC_CONST(0x5555555555555555),ABC_CONST(0x3333333333333333), ABC_CONST(0x0F0F0F0F0F0F0F0F),ABC_CONST(0x00FF00FF00FF00FF),ABC_CONST(0x0000FFFF0000FFFF), ABC_CONST(0x00000000FFFFFFFF)};  
/*
static word mask1[6] = { 0xAAAAAAAAAAAAAAAA,0xCCCCCCCCCCCCCCCC, 0xF0F0F0F0F0F0F0F0,0xFF00FF00FF00FF00,0xFFFF0000FFFF0000, 0xFFFFFFFF00000000 };
static word mask[6][2] =   {
    {0x5555555555555555,0xAAAAAAAAAAAAAAAA},
    {0x3333333333333333,0xCCCCCCCCCCCCCCCC},
    {0x0F0F0F0F0F0F0F0F,0xF0F0F0F0F0F0F0F0},
    {0x00FF00FF00FF00FF,0xFF00FF00FF00FF00},
    {0x0000FFFF0000FFFF,0xFFFF0000FFFF0000},
    {0x00000000FFFFFFFF,0xFFFFFFFF00000000}
};
*/

int Kit_TruthWordNum_64bit( int nVars )  { return nVars <= 6 ? 1 : (1 << (nVars - 6));}

int Kit_WordCountOnes_64bit(word x)
{
    x = x - ((x >> 1) & ABC_CONST(0x5555555555555555));   
    x = (x & ABC_CONST(0x3333333333333333)) + ((x >> 2) & ABC_CONST(0x3333333333333333));    
    x = (x + (x >> 4)) & ABC_CONST(0x0F0F0F0F0F0F0F0F);    
    x = x + (x >> 8);
    x = x + (x >> 16);
    x = x + (x >> 32); 
    return (int)(x & 0xFF);
}

int Kit_TruthCountOnes_64bit( word* pIn, int nVars )
{
    int w, Counter = 0;
    for ( w = Kit_TruthWordNum_64bit(nVars)-1; w >= 0; w-- )
        Counter += Kit_WordCountOnes_64bit(pIn[w]);
    return Counter;
}

void Kit_TruthCountOnesInCofs_64bit( word * pTruth, int nVars, int * pStore )
{    
    int nWords = Kit_TruthWordNum_64bit( nVars );
    int i, k, Counter;
    memset( pStore, 0, sizeof(int) * nVars );
    if ( nVars <= 6 )
    {
        if ( nVars > 0 )        
            pStore[0] = Kit_WordCountOnes_64bit( pTruth[0] & ABC_CONST(0x5555555555555555) );  
        if ( nVars > 1 )       
            pStore[1] = Kit_WordCountOnes_64bit( pTruth[0] & ABC_CONST(0x3333333333333333) );     
        if ( nVars > 2 )       
            pStore[2] = Kit_WordCountOnes_64bit( pTruth[0] & ABC_CONST(0x0F0F0F0F0F0F0F0F) );   
        if ( nVars > 3 )       
            pStore[3] = Kit_WordCountOnes_64bit( pTruth[0] & ABC_CONST(0x00FF00FF00FF00FF) );     
        if ( nVars > 4 )       
            pStore[4] = Kit_WordCountOnes_64bit( pTruth[0] & ABC_CONST(0x0000FFFF0000FFFF) ); 
        if ( nVars > 5 )       
            pStore[5] = Kit_WordCountOnes_64bit( pTruth[0] & ABC_CONST(0x00000000FFFFFFFF) );      
        return;
    }
    // nVars > 6
    // count 1's for all other variables
    for ( k = 0; k < nWords; k++ )
    {
        Counter = Kit_WordCountOnes_64bit( pTruth[k] );
        for ( i = 6; i < nVars; i++ )
            if ( (k & (1 << (i-6))) == 0)
                pStore[i] += Counter;
    }
    // count 1's for the first six variables
    for ( k = nWords/2; k>0; k-- )
    {
        pStore[0] += Kit_WordCountOnes_64bit( (pTruth[0] & ABC_CONST(0x5555555555555555)) | ((pTruth[1] & ABC_CONST(0x5555555555555555)) <<  1) );
        pStore[1] += Kit_WordCountOnes_64bit( (pTruth[0] & ABC_CONST(0x3333333333333333)) | ((pTruth[1] & ABC_CONST(0x3333333333333333)) <<  2) );
        pStore[2] += Kit_WordCountOnes_64bit( (pTruth[0] & ABC_CONST(0x0F0F0F0F0F0F0F0F)) | ((pTruth[1] & ABC_CONST(0x0F0F0F0F0F0F0F0F)) <<  4) );
        pStore[3] += Kit_WordCountOnes_64bit( (pTruth[0] & ABC_CONST(0x00FF00FF00FF00FF)) | ((pTruth[1] & ABC_CONST(0x00FF00FF00FF00FF)) <<  8) );
        pStore[4] += Kit_WordCountOnes_64bit( (pTruth[0] & ABC_CONST(0x0000FFFF0000FFFF)) | ((pTruth[1] & ABC_CONST(0x0000FFFF0000FFFF)) <<  16) );
        pStore[5] += Kit_WordCountOnes_64bit( (pTruth[0] & ABC_CONST(0x00000000FFFFFFFF)) | ((pTruth[1] & ABC_CONST(0x00000000FFFFFFFF)) <<  32) );  
        pTruth += 2;
    }
}

void Kit_TruthChangePhase_64bit( word * pInOut, int nVars, int iVar )
{
    int nWords = Kit_TruthWordNum_64bit( nVars );
    int i, Step,SizeOfBlock;
    word Temp[512];
    
    assert( iVar < nVars );
    if(iVar<=5)
    {
        for ( i = 0; i < nWords; i++ )
            pInOut[i] = ((pInOut[i] & mask0[iVar]) << (1<<(iVar))) | ((pInOut[i] & ~mask0[iVar]) >> (1<<(iVar)));
    }
    else
    {
        Step = (1 << (iVar - 6));
        SizeOfBlock = sizeof(word)*Step;
        for ( i = 0; i < nWords; i += 2*Step )
        {   
            memcpy(Temp,pInOut,SizeOfBlock);
            memcpy(pInOut,pInOut+Step,SizeOfBlock);
            memcpy(pInOut+Step,Temp,SizeOfBlock);
            //          Temp = pInOut[i];
            //          pInOut[i] = pInOut[Step+i];
            //          pInOut[Step+i] = Temp;          
            pInOut += 2*Step;
        }
    }
    
}

void Kit_TruthNot_64bit(word * pIn, int nVars )
{
    int w;
    for ( w = Kit_TruthWordNum_64bit(nVars)-1; w >= 0; w-- )
        pIn[w] = ~pIn[w];
}
void Kit_TruthCopy_64bit( word * pOut, word * pIn, int nVars )
{ 
    memcpy(pOut,pIn,Kit_TruthWordNum_64bit(nVars)*sizeof(word));
}

void Kit_TruthSwapAdjacentVars_64bit( word * pInOut, int nVars, int iVar )
{
    int i, Step, Shift, SizeOfBlock;                   //
    word temp[256];                   // to make only pInOut possible
    static word PMasks[5][3] = {
        { ABC_CONST(0x9999999999999999), ABC_CONST(0x2222222222222222), ABC_CONST(0x4444444444444444) },
        { ABC_CONST(0xC3C3C3C3C3C3C3C3), ABC_CONST(0x0C0C0C0C0C0C0C0C), ABC_CONST(0x3030303030303030) },
        { ABC_CONST(0xF00FF00FF00FF00F), ABC_CONST(0x00F000F000F000F0), ABC_CONST(0x0F000F000F000F00) },
        { ABC_CONST(0xFF0000FFFF0000FF), ABC_CONST(0x0000FF000000FF00), ABC_CONST(0x00FF000000FF0000) },
        { ABC_CONST(0xFFFF00000000FFFF), ABC_CONST(0x00000000FFFF0000), ABC_CONST(0x0000FFFF00000000) }
    };
    int nWords = Kit_TruthWordNum_64bit( nVars ); 
    
    assert( iVar < nVars - 1 );
    if ( iVar < 5 )
    {
        Shift = (1 << iVar);
        for ( i = 0; i < nWords; i++ )
            pInOut[i] = (pInOut[i] & PMasks[iVar][0]) | ((pInOut[i] & PMasks[iVar][1]) << Shift) | ((pInOut[i] & PMasks[iVar][2]) >> Shift);
    }
    else if ( iVar > 5 )
    {
        Step = 1 << (iVar - 6);
        SizeOfBlock = sizeof(word)*Step;
        pInOut += 2*Step;
        for(i=2*Step; i<nWords; i+=4*Step)
        {           
            memcpy(temp,pInOut-Step,SizeOfBlock);
            memcpy(pInOut-Step,pInOut,SizeOfBlock);
            memcpy(pInOut,temp,SizeOfBlock);
            pInOut += 4*Step;
        }
    }
    else // if ( iVar == 5 )
    {
        for ( i = 0; i < nWords; i += 2 )
        {
            temp[0] = pInOut[i+1] << 32;
            pInOut[i+1] ^= (temp[0] ^ pInOut[i]) >> 32;
            pInOut[i] = (pInOut[i] & 0x00000000FFFFFFFF) | temp[0];
            
        }
    }
}

unsigned  Kit_TruthSemiCanonicize_Yasha( word* pInOut, int nVars, char * pCanonPerm )
{
    int pStore[16];
    int nWords = Kit_TruthWordNum_64bit( nVars );
    int i, Temp, fChange, nOnes;
    unsigned  uCanonPhase=0;
    assert( nVars <= 16 );
    
    nOnes = Kit_TruthCountOnes_64bit(pInOut, nVars);
    
    if ( (nOnes > nWords * 32) )
    {
        uCanonPhase |= (1 << nVars);
        Kit_TruthNot_64bit( pInOut, nVars );
        nOnes = nWords*64 - nOnes;
    }
    
    // collect the minterm counts
    Kit_TruthCountOnesInCofs_64bit( pInOut, nVars, pStore );
    
    // canonicize phase
    for ( i = 0; i < nVars; i++ )
    {
        if ( pStore[i] >= nOnes-pStore[i])
            continue;
        uCanonPhase |= (1 << i);
        pStore[i] = nOnes-pStore[i]; 
        Kit_TruthChangePhase_64bit( pInOut, nVars, i );
    }  
    
    do {
        fChange = 0;
        for ( i = 0; i < nVars-1; i++ )
        {
            if ( pStore[i] <= pStore[i+1] )
                continue;            
            fChange = 1;
            
            Temp = pCanonPerm[i];
            pCanonPerm[i] = pCanonPerm[i+1];
            pCanonPerm[i+1] = Temp;
            
            Temp = pStore[i];
            pStore[i] = pStore[i+1];
            pStore[i+1] = Temp;
            
            // if the polarity of variables is different, swap them
            if ( ((uCanonPhase & (1 << i)) > 0) != ((uCanonPhase & (1 << (i+1))) > 0) )
            {
                uCanonPhase ^= (1 << i);
                uCanonPhase ^= (1 << (i+1));
            }
            
            Kit_TruthSwapAdjacentVars_64bit( pInOut, nVars, i );            
        }
    } while ( fChange );
    return uCanonPhase;
}

unsigned  Kit_TruthSemiCanonicize_Yasha1( word* pInOut, int nVars, char * pCanonPerm, int * pStore )
{
    int nWords = Kit_TruthWordNum_64bit( nVars );
    int i, fChange, nOnes;
    int Temp;
    unsigned  uCanonPhase=0;
    assert( nVars <= 16 );
    
    nOnes = Kit_TruthCountOnes_64bit(pInOut, nVars);
    if ( nOnes == nWords * 32 )
        uCanonPhase |= (1 << (nVars+2));
    
    else if ( (nOnes > nWords * 32) )
    {
        uCanonPhase |= (1 << nVars);
        Kit_TruthNot_64bit( pInOut, nVars );
        nOnes = nWords*64 - nOnes;
    }
    
    // collect the minterm counts
    Kit_TruthCountOnesInCofs_64bit( pInOut, nVars, pStore );
    
    // canonicize phase
    for ( i = 0; i < nVars; i++ )
    {
        if (  2*pStore[i]  == nOnes)
        {
            uCanonPhase |= (1 << (nVars+1));
            continue;
        }
        if ( pStore[i] > nOnes-pStore[i])
            continue;
        uCanonPhase |= (1 << i);
        pStore[i] = nOnes-pStore[i]; 
        Kit_TruthChangePhase_64bit( pInOut, nVars, i );
    }  
    
    do {
        fChange = 0;
        for ( i = 0; i < nVars-1; i++ )
        {
            if ( pStore[i] <= pStore[i+1] )
                continue;            
            fChange = 1;
            
            Temp = pCanonPerm[i];
            pCanonPerm[i] = pCanonPerm[i+1];
            pCanonPerm[i+1] = Temp;
            
            Temp = pStore[i];
            pStore[i] = pStore[i+1];
            pStore[i+1] = Temp;
            
            // if the polarity of variables is different, swap them
            if ( ((uCanonPhase & (1 << i)) > 0) != ((uCanonPhase & (1 << (i+1))) > 0) )
            {
                uCanonPhase ^= (1 << i);
                uCanonPhase ^= (1 << (i+1));
            }
            
            Kit_TruthSwapAdjacentVars_64bit( pInOut, nVars, i );            
        }
    } while ( fChange );
    return uCanonPhase;
}


// unsigned  Kit_TruthSemiCanonicize_Yasha_simple( word* pInOut, int nVars, char * pCanonPerm )
// {
//     unsigned uCanonPhase = 0;
//     int pStore[16];
//     int nWords = Kit_TruthWordNum_64bit( nVars );
//     int i, Temp, fChange, nOnes; 
//  assert( nVars <= 16 );
//  
//     nOnes = Kit_TruthCountOnes_64bit(pInOut, nVars);
//  
//     if ( (nOnes > nWords * 32) )
//     { 
//         Kit_TruthNot_64bit( pInOut, nVars );
//      nOnes = nWords*64 - nOnes;
//     }
//  
//     // collect the minterm counts
//     Kit_TruthCountOnesInCofs_64bit( pInOut, nVars, pStore );
//  
//     // canonicize phase
//     for ( i = 0; i < nVars; i++ )
//     {
//         if ( pStore[i] >= nOnes-pStore[i])
//             continue;        
//         pStore[i] = nOnes-pStore[i]; 
//         Kit_TruthChangePhase_64bit( pInOut, nVars, i );
//     }  
//  
//     do {
//         fChange = 0;
//         for ( i = 0; i < nVars-1; i++ )
//         {
//             if ( pStore[i] <= pStore[i+1] )
//                 continue;            
//             fChange = 1;         
//          
//             Temp = pStore[i];
//             pStore[i] = pStore[i+1];
//             pStore[i+1] = Temp;
//          
//             Kit_TruthSwapAdjacentVars_64bit( pInOut, nVars, i );             
//         }
//     } while ( fChange ); 
//     return uCanonPhase;
// }

void  Kit_TruthSemiCanonicize_Yasha_simple( word* pInOut, int nVars, int * pStore )
{
    int nWords = Kit_TruthWordNum_64bit( nVars );
    int i, Temp, fChange, nOnes; 
    assert( nVars <= 16 );
    
    nOnes = Kit_TruthCountOnes_64bit(pInOut, nVars);
    
    if ( (nOnes > nWords * 32) )
    { 
        Kit_TruthNot_64bit( pInOut, nVars );
        nOnes = nWords*64 - nOnes;
    }
    
    // collect the minterm counts
    Kit_TruthCountOnesInCofs_64bit( pInOut, nVars, pStore );
    
    // canonicize phase
    for ( i = 0; i < nVars; i++ )
    {
        if ( pStore[i] >= nOnes-pStore[i])
            continue;        
        pStore[i] = nOnes-pStore[i]; 
        Kit_TruthChangePhase_64bit( pInOut, nVars, i );
    }  
    
    do {
        fChange = 0;
        for ( i = 0; i < nVars-1; i++ )
        {
            if ( pStore[i] <= pStore[i+1] )
                continue;            
            fChange = 1;            
            
            Temp = pStore[i];
            pStore[i] = pStore[i+1];
            pStore[i+1] = Temp;
            
            Kit_TruthSwapAdjacentVars_64bit( pInOut, nVars, i );            
        }
    } while ( fChange ); 
}


ABC_NAMESPACE_IMPL_END