summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/base/abci/abc.c3
-rw-r--r--src/base/abci/abcNpn.c23
-rw-r--r--src/bool/kit/kitTruth.c4
-rw-r--r--src/misc/extra/extra.h3
-rw-r--r--src/misc/extra/extraUtilMisc.c87
5 files changed, 111 insertions, 9 deletions
diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c
index dede6c51..3eabc252 100644
--- a/src/base/abci/abc.c
+++ b/src/base/abci/abc.c
@@ -4928,7 +4928,8 @@ usage:
Abc_Print( -2, "\t 0: none (reading and writing the file)\n" );
Abc_Print( -2, "\t 1: semi-canonical form by counting 1s in cofactors\n" );
Abc_Print( -2, "\t 2: semi-canonical form by minimizing truth table value\n" );
- Abc_Print( -2, "\t 3: exact canonical form (slow for more than 6 variables)\n" );
+ Abc_Print( -2, "\t 3: exact canonical form (work only for 6 variables)\n" );
+ Abc_Print( -2, "\t 4: heuristic canonical form (work only for 6 variables)\n" );
Abc_Print( -2, "\t-v : toggle verbose printout [default = %s]\n", fVerbose? "yes": "no" );
Abc_Print( -2, "\t-h : print the command usage\n");
return 1;
diff --git a/src/base/abci/abcNpn.c b/src/base/abci/abcNpn.c
index 5c21d98e..70c08da7 100644
--- a/src/base/abci/abcNpn.c
+++ b/src/base/abci/abcNpn.c
@@ -110,6 +110,8 @@ void Abc_TruthNpnPerform( Abc_TtStore_t * p, int NpnType, int fVerbose )
pAlgoName = "minimizing TT";
else if ( NpnType == 3 )
pAlgoName = "exact NPN ";
+ else if ( NpnType == 4 )
+ pAlgoName = "heuristic NPN";
assert( p->nVars <= 16 );
if ( pAlgoName )
@@ -150,7 +152,7 @@ void Abc_TruthNpnPerform( Abc_TtStore_t * p, int NpnType, int fVerbose )
{
if ( fVerbose )
printf( "%7d : ", i );
- *((word *)p->pFuncs[i]) = Extra_Truth6Minimum( *((word *)p->pFuncs[i]), pComp, pPerm );
+ *((word *)p->pFuncs[i]) = Extra_Truth6MinimumExact( *((word *)p->pFuncs[i]), pComp, pPerm );
if ( fVerbose )
Extra_PrintHex( stdout, (unsigned *)p->pFuncs[i], p->nVars ), printf( "\n" );
}
@@ -160,6 +162,23 @@ void Abc_TruthNpnPerform( Abc_TtStore_t * p, int NpnType, int fVerbose )
ABC_FREE( pComp );
ABC_FREE( pPerm );
}
+ else if ( NpnType == 4 )
+ {
+ if ( p->nVars == 6 )
+ {
+ for ( i = 0; i < p->nFuncs; i++ )
+ {
+ if ( fVerbose )
+ printf( "%7d : ", i );
+ Kit_TruthSemiCanonicize( (unsigned *)p->pFuncs[i], pAux, p->nVars, pCanonPerm, pStore );
+ *((word *)p->pFuncs[i]) = Extra_Truth6MinimumHeuristic( *((word *)p->pFuncs[i]) );
+ if ( fVerbose )
+ Extra_PrintHex( stdout, (unsigned *)p->pFuncs[i], p->nVars ), printf( "\n" );
+ }
+ }
+ else
+ printf( "This feature only works for 6-variable functions.\n" );
+ }
else assert( 0 );
clk = clock() - clk;
@@ -213,7 +232,7 @@ int Abc_NpnTest( char * pFileName, int NpnType, int fVerbose )
printf( "Using truth tables from file \"%s\"...\n", pFileName );
if ( NpnType == 0 )
Abc_TtStoreTest( pFileName );
- else if ( NpnType >= 1 && NpnType <= 3 )
+ else if ( NpnType >= 1 && NpnType <= 4 )
Abc_TruthNpnTest( pFileName, NpnType, fVerbose );
else
printf( "Unknown canonical form value (%d).\n", NpnType );
diff --git a/src/bool/kit/kitTruth.c b/src/bool/kit/kitTruth.c
index bd8bbb1c..258207c2 100644
--- a/src/bool/kit/kitTruth.c
+++ b/src/bool/kit/kitTruth.c
@@ -1685,7 +1685,7 @@ unsigned Kit_TruthSemiCanonicize( unsigned * pInOut, unsigned * pAux, int nVars,
// canonicize phase
for ( i = 0; i < nVars; i++ )
{
- if ( pStore[2*i+0] <= pStore[2*i+1] )
+ if ( pStore[2*i+0] >= pStore[2*i+1] )
continue;
uCanonPhase |= (1 << i);
Temp = pStore[2*i+0];
@@ -1703,7 +1703,7 @@ unsigned Kit_TruthSemiCanonicize( unsigned * pInOut, unsigned * pAux, int nVars,
fChange = 0;
for ( i = 0; i < nVars-1; i++ )
{
- if ( pStore[2*i] <= pStore[2*(i+1)] )
+ if ( pStore[2*i] >= pStore[2*(i+1)] )
continue;
Counter++;
fChange = 1;
diff --git a/src/misc/extra/extra.h b/src/misc/extra/extra.h
index f198c183..8d3ba254 100644
--- a/src/misc/extra/extra.h
+++ b/src/misc/extra/extra.h
@@ -203,7 +203,8 @@ extern void Extra_BubbleSort( int Order[], int Costs[], int nSize, int fI
/* complementation/permutation generation */
extern int * Extra_GreyCodeSchedule( int n );
extern int * Extra_PermSchedule( int n );
-extern word Extra_Truth6Minimum( word t, int * pComp, int * pPerm );
+extern word Extra_Truth6MinimumExact( word t, int * pComp, int * pPerm );
+extern word Extra_Truth6MinimumHeuristic( word t );
/*=== extraUtilCanon.c ========================================================*/
diff --git a/src/misc/extra/extraUtilMisc.c b/src/misc/extra/extraUtilMisc.c
index e484bcb2..c765917c 100644
--- a/src/misc/extra/extraUtilMisc.c
+++ b/src/misc/extra/extraUtilMisc.c
@@ -2283,7 +2283,7 @@ static inline word Extra_Truth6ChangePhase( word t, int v )
assert( v < 6 );
return ((t & ~Truth6[v]) << (1 << v)) | ((t & Truth6[v]) >> (1 << v));
}
-word Extra_Truth6Minimum( word t, int * pComp, int * pPerm )
+word Extra_Truth6MinimumExact( word t, int * pComp, int * pPerm )
{
word tMin = ~(word)0;
word tCur, tTemp1, tTemp2;
@@ -2312,6 +2312,87 @@ word Extra_Truth6Minimum( word t, int * pComp, int * pPerm )
/**Function*************************************************************
+ Synopsis [Perform heuristic TT minimization.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+static inline int Extra_Truth6Ones( word t )
+{
+ t = (t & 0x5555555555555555) + ((t>> 1) & 0x5555555555555555);
+ t = (t & 0x3333333333333333) + ((t>> 2) & 0x3333333333333333);
+ t = (t & 0x0F0F0F0F0F0F0F0F) + ((t>> 4) & 0x0F0F0F0F0F0F0F0F);
+ t = (t & 0x00FF00FF00FF00FF) + ((t>> 8) & 0x00FF00FF00FF00FF);
+ t = (t & 0x0000FFFF0000FFFF) + ((t>>16) & 0x0000FFFF0000FFFF);
+ return (t & 0x00000000FFFFFFFF) + (t>>32);
+}
+static inline word Extra_Truth6MinimumRoundOne( word t, int v )
+{
+ word tCur, tMin = t; // ab
+ assert( v >= 0 && v < 5 );
+
+ tCur = Extra_Truth6ChangePhase( t, v ); // !ab
+ tMin = Abc_MinWord( tMin, tCur );
+ tCur = Extra_Truth6ChangePhase( t, v+1 ); // a!b
+ tMin = Abc_MinWord( tMin, tCur );
+ tCur = Extra_Truth6ChangePhase( tCur, v ); // !a!b
+ tMin = Abc_MinWord( tMin, tCur );
+
+ t = Extra_Truth6SwapAdjacent( t, v ); // ba
+ tMin = Abc_MinWord( tMin, t );
+
+ tCur = Extra_Truth6ChangePhase( t, v ); // !ba
+ tMin = Abc_MinWord( tMin, tCur );
+ tCur = Extra_Truth6ChangePhase( t, v+1 ); // b!a
+ tMin = Abc_MinWord( tMin, tCur );
+ tCur = Extra_Truth6ChangePhase( tCur, v ); // !b!a
+ tMin = Abc_MinWord( tMin, tCur );
+
+ return tMin;
+}
+static inline word Extra_Truth6MinimumRoundMany( word t )
+{
+ int i, k, Limit = 10;
+ word tCur, tMin = t;
+ for ( i = 0; i < Limit; i++ )
+ {
+ word tMin0 = tMin;
+ for ( k = 4; k >= 0; k-- )
+ {
+ tCur = Extra_Truth6MinimumRoundOne( tMin, k );
+ tMin = Abc_MinWord( tMin, tCur );
+ }
+ if ( tMin0 == tMin )
+ break;
+ }
+ return tMin;
+}
+word Extra_Truth6MinimumHeuristic( word t )
+{
+ word tMin1, tMin2;
+ int nOnes = Extra_Truth6Ones( t );
+ if ( nOnes < 32 )
+ return Extra_Truth6MinimumRoundMany( t );
+ if ( nOnes > 32 )
+ return Extra_Truth6MinimumRoundMany( ~t );
+ tMin1 = Extra_Truth6MinimumRoundMany( t );
+ tMin2 = Extra_Truth6MinimumRoundMany( ~t );
+ return Abc_MinWord( tMin1, tMin2 );
+}
+void Extra_Truth6MinimumHeuristicTest()
+{
+ word t = 0x5555555555555555 & ~(0x3333333333333333 & 0x0F0F0F0F0F0F0F0F);
+ Extra_Truth6MinimumRoundMany( t );
+ t = 0;
+}
+
+
+/**Function*************************************************************
+
Synopsis [Reads functions from file.]
Description []
@@ -2387,7 +2468,7 @@ void Extra_NpnTest2()
word tMin, t = 0xa2222aaa08888000;
pComp = Extra_GreyCodeSchedule( 6 );
pPerm = Extra_PermSchedule( 6 );
- tMin = Extra_Truth6Minimum( t, pComp, pPerm );
+ tMin = Extra_Truth6MinimumExact( t, pComp, pPerm );
ABC_FREE( pPerm );
ABC_FREE( pComp );
@@ -2424,7 +2505,7 @@ void Extra_NpnTest()
// compute minimum forms
for ( i = 0; i < nFuncs; i++ )
{
- pFuncs[i] = Extra_Truth6Minimum( pFuncs[i], pComp, pPerm );
+ pFuncs[i] = Extra_Truth6MinimumExact( pFuncs[i], pComp, pPerm );
if ( i % 10000 == 0 )
printf( "%d\n", i );
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-07-01 01:13:51 +0000