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