From 12c776ed6e5a17a491fdb986ccce99649a06850e Mon Sep 17 00:00:00 2001
From: Alan Mishchenko <alanmi@berkeley.edu>
Date: Thu, 23 Aug 2012 22:20:27 -0700
Subject: Added new algorithm for NPN semi-canonical form computation.

---
 src/base/abci/abc.c    |  3 ++-
 src/base/abci/abcNpn.c | 23 +++++++++++++++++++++--
 2 files changed, 23 insertions(+), 3 deletions(-)

(limited to 'src/base/abci')

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 );
-- 
cgit v1.2.3