Updating command 'symfun' to generate symmetric functions and their NPN classes.

3 files changed, 168 insertions, 26 deletions

diff --git a/src/base/abci/abc.c b/src/base/abci/abc.c
index 429b48d9..085bb0f0 100644
--- a/src/base/abci/abc.c
+++ b/src/base/abci/abc.c
@@ -22974,12 +22974,12 @@ usage:
 ***********************************************************************/
 int Abc_CommandSymFun( Abc_Frame_t * pAbc, int argc, char ** argv )
 {
-    Vec_Bit_t * vMints;
-    char * pStr;
-    int nVars = 5;
-    int c, m, k, Count;
+    extern void Ntk_SymFunGenerate( int nVars );
+    word * pFun = NULL;
+    char * pStr,  * pTruth, * pCommand;
+    int c, k, nVars = -1, fVerbose = 1;
     Extra_UtilGetoptReset();
-    while ( ( c = Extra_UtilGetopt( argc, argv, "Nh" ) ) != EOF )
+    while ( ( c = Extra_UtilGetopt( argc, argv, "Nvh" ) ) != EOF )
     {
         switch ( c )
         {
@@ -22992,6 +22992,9 @@ int Abc_CommandSymFun( Abc_Frame_t * pAbc, int argc, char ** argv )
             nVars = atoi(argv[globalUtilOptind]);
             globalUtilOptind++;
             break;
+        case 'v':
+            fVerbose ^= 1;
+            break;
         case 'h':
             goto usage;
         default:
@@ -22999,39 +23002,64 @@ int Abc_CommandSymFun( Abc_Frame_t * pAbc, int argc, char ** argv )
             goto usage;
         }
     }
+    if ( nVars != -1 )
+    {
+        if ( nVars < 1 || nVars > 16 )
+        {
+            printf( "Cannot generate functions for less than 1 and more than %d variables.\n", nVars );
+            return 1;
+        }
+        Ntk_SymFunGenerate( nVars );
+        return 0;
+    }
     if ( argc != globalUtilOptind + 1 )
     {
         Abc_Print( -1, "Not enough command-line arguments.\n" );
         return 1;
     }
-    if ( nVars < 2 || nVars > 9 )
+    // make sure the string is composed of N+1 zeros and ones
+    pStr = argv[globalUtilOptind];
+    nVars = strlen(pStr) - 1;
+    for ( k = 0; k <= nVars; k++ )
+        if ( pStr[k] != '0' && pStr[k] != '1' )
+            break;
+    if ( k <= nVars )
     {
-        Abc_Print( -1, "The number of variables should be between 2 and 9.\n" );
+        Abc_Print( -1, "The string should be composed of zeros and ones.\n" );
         return 1;
     }
-    vMints = Vec_BitStart( 1 << nVars );
-    pStr = argv[globalUtilOptind];
-    while ( *pStr )
+    // generate and print one function
+    pFun = Abc_TtSymFunGenerate( pStr, nVars );
+    pTruth = ABC_CALLOC( char, nVars > 2 ? (1 << (nVars-2)) + 1 : 2 );
+    Extra_PrintHexadecimalString( pTruth, (unsigned *)pFun, nVars );
+    ABC_FREE( pFun );
+    if ( fVerbose )
     {
-        for ( m = 0; m < (1 << nVars); m++ )
-        {
-            Count = 0;
-            for ( k = 0; k < nVars; k++ )
-                Count += (m >> k) & 1;
-            if ( *pStr == '0' + Count )
-                Vec_BitWriteEntry( vMints, m, 1 );
-        }
-        pStr++;
+        if ( nVars > 6 )
+            printf( "Generated truth table of the %d-variable function and set it as the current network.\n", nVars );
+        else
+            printf( "Generated truth table of the %d-variable function (%s) and set it as the current network\n", nVars, pTruth );
     }
-    Extra_PrintHex( stdout, (unsigned *)Vec_BitArray(vMints), nVars ); printf( "\n" );
-    Vec_BitFree( vMints );
+    else
+        printf( "%s\n", pTruth );
+    // read the truth table to be the current network in ABC
+    pCommand = ABC_CALLOC( char, strlen(pTruth) + 100 );
+    sprintf( pCommand, "read_truth %s", pTruth );
+    Cmd_CommandExecute( pAbc, pCommand );
+    ABC_FREE( pCommand );
+    ABC_FREE( pTruth );
     return 0;
 
 usage:
-    Abc_Print( -2, "usage: symfun [-h] <ones>\n" );
-    Abc_Print( -2, "\t         prints truth table of a symmetric function up to 9 inputs\n" );
-    Abc_Print( -2, "\t<ones> : the counts of ones in the inputs when the function is one\n" );
-    Abc_Print( -2, "\t-h     : print the command usage\n");
+    Abc_Print( -2, "usage: symfun [-N num] [-vh] <ones>\n" );
+    Abc_Print( -2, "\t           generated a single-output symmetric function\n" );
+    Abc_Print( -2, "\t-N <num> : prints truth tables of all N-var symmetric functions [default = not used]\n" );
+    Abc_Print( -2, "\t-v       : toggle verbose output [default = %s]\n", fVerbose? "yes": "no" );
+    Abc_Print( -2, "\t-h       : print the command usage\n");
+    Abc_Print( -2, "\t<ones>   : the string of N+1 zeros and ones, where N is the number of variables\n" );
+    Abc_Print( -2, "\t           For example, to get 3-input NAND-gate, use \"symfun 1000\".\n" );
+    Abc_Print( -2, "\t           To get 5-input majority gate, use \"symfun 000111\".\n" );
+
     return 1;
 }
 /**Function*************************************************************
diff --git a/src/base/abci/abcSymm.c b/src/base/abci/abcSymm.c
index 36a5ee3e..92dc57d8 100644
--- a/src/base/abci/abcSymm.c
+++ b/src/base/abci/abcSymm.c
@@ -20,6 +20,8 @@
 
 #include "base/abc/abc.h"
 #include "opt/sim/sim.h"
+#include "opt/dau/dau.h"
+#include "misc/util/utilTruth.h"
 
 #ifdef ABC_USE_CUDD
 #include "bdd/extrab/extraBdd.h"
@@ -237,6 +239,93 @@ void Abc_NtkSymmetries( Abc_Ntk_t * pNtk, int fUseBdds, int fNaive, int fReorder
 
 #endif
 
+/**Function*************************************************************
+
+  Synopsis    [Generating NPN classes of all symmetric function of N variables.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+void Ntk_SymFunGenerate( int nVars )
+{
+    char Ones[100] = {0};
+    word * pFun;
+    int k, m, * pComp, * pPerm, Func;
+    Vec_Wrd_t * vCanons = NULL;
+    Abc_TtHieMan_t * pMan;
+    assert( !(nVars < 1 || nVars > 16) );
+	pMan = Abc_TtHieManStart(nVars, 5);
+    printf( "Generating truth tables of all symmetric functions of %d variables.\n", nVars );
+    pComp = nVars == 6 ? Extra_GreyCodeSchedule( 6 ) : NULL;
+    pPerm = nVars == 6 ? Extra_PermSchedule( 6 )     : NULL;
+    vCanons = Vec_WrdAlloc( 100 );
+    for ( m = 0; m < (1 << (nVars+1)); m++ )
+    {
+        for ( k = 0; k <= nVars; k++ )
+            Ones[k] = '0' + ((m >> k) & 1);
+        printf( "%s : ", Ones );
+        pFun = Abc_TtSymFunGenerate( Ones, nVars );
+        Extra_PrintHex( stdout, (unsigned *)pFun, nVars );
+        // compute NPN canicical form
+        if ( nVars < 6 )
+        {
+            unsigned Canon = Extra_TruthCanonNPN( (unsigned)Abc_Tt6Stretch(pFun[0], nVars), nVars );
+            printf( " : NPN " );
+            Extra_PrintHex( stdout, &Canon, nVars );
+            if ( (Func = Vec_WrdFind(vCanons, (word)Canon)) == -1 )
+            {
+                Func = Vec_WrdSize(vCanons);
+                Vec_WrdPush( vCanons, (word)Canon );
+            }
+            printf( "  Class %3d", Func );
+        }
+        else if ( nVars == 6 )
+        {
+            word Canon = Extra_Truth6MinimumExact( pFun[0], pComp, pPerm );
+            printf( " : NPN " );
+            Extra_PrintHex( stdout, (unsigned *)&Canon, nVars );
+            if ( (Func = Vec_WrdFind(vCanons, (word)Canon)) == -1 )
+            {
+                Func = Vec_WrdSize(vCanons);
+                Vec_WrdPush( vCanons, (word)Canon );
+            }
+            printf( "  Class %3d", Func );
+        }
+        if ( 0 )
+        {
+            unsigned Abc_TtCanonicizeWrap(TtCanonicizeFunc func, Abc_TtHieMan_t * p, word * pTruth, int nVars, char * pCanonPerm, int flag);
+            unsigned Abc_TtCanonicizeAda(Abc_TtHieMan_t * p, word * pTruth, int nVars, char * pCanonPerm, int iThres);
+            char pCanonPerm[16];
+            unsigned uCanonPhase;
+            if ( nVars < 6 )
+            {
+                word Truth = Abc_Tt6Stretch(pFun[0], nVars);
+                uCanonPhase = Abc_TtCanonicizeWrap(Abc_TtCanonicizeAda, pMan, &Truth, nVars, pCanonPerm, 1199); // -A 9, adjustable algorithm (exact)
+                printf( " : NPN " );
+                Extra_PrintHex( stdout, (unsigned *)&Truth, nVars );
+            }
+            else
+            {
+                uCanonPhase = Abc_TtCanonicizeWrap(Abc_TtCanonicizeAda, pMan, pFun, nVars, pCanonPerm, 1199); // -A 9, adjustable algorithm (exact)
+                printf( " : NPN " );
+                Extra_PrintHex( stdout, (unsigned *)pFun, nVars );
+            }
+        }
+        printf( "\n" );
+        ABC_FREE( pFun );
+    }
+	Abc_TtHieManStop(pMan);
+    if ( Vec_WrdSize(vCanons) )
+        printf( "The number of different NPN classes is %d.\n", Vec_WrdSize(vCanons) );
+    Vec_WrdFreeP( &vCanons );
+    ABC_FREE( pPerm );
+    ABC_FREE( pComp );
+}
+
 ////////////////////////////////////////////////////////////////////////
 ///                       END OF FILE                                ///
 ////////////////////////////////////////////////////////////////////////
diff --git a/src/misc/util/utilTruth.h b/src/misc/util/utilTruth.h
index 8d28d33e..6fa5e0a3 100644
--- a/src/misc/util/utilTruth.h
+++ b/src/misc/util/utilTruth.h
@@ -3191,7 +3191,32 @@ static inline void Abc_TtTestFullySymmetric()
 }
 
 
-/*=== utilTruth.c ===========================================================*/
+/**Function*************************************************************
+
+  Synopsis    [Generates truth table of a symmetric function.]
+
+  Description []
+               
+  SideEffects []
+
+  SeeAlso     []
+
+***********************************************************************/
+static inline word * Abc_TtSymFunGenerate( char * pOnes, int nVars )
+{
+    int m, k, Count;
+    word * pTruth = ABC_CALLOC( word, Abc_TtWordNum(nVars) );
+    assert( (int)strlen(pOnes) == nVars + 1 );
+    for ( m = 0; m < (1 << nVars); m++ )
+    {
+        Count = 0;
+        for ( k = 0; k < nVars; k++ )
+            Count += (m >> k) & 1;
+        if ( pOnes[Count] == '1' )
+            Abc_TtXorBit( pTruth, m );
+    }
+    return pTruth;
+}
 
 
 ABC_NAMESPACE_HEADER_END