From 38e2f41655d4d44ccfa935b5b8d687596124c169 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Thu, 30 May 2019 19:27:31 -0700 Subject: Updating command 'symfun' to generate symmetric functions and their NPN classes. --- src/base/abci/abc.c | 78 ++++++++++++++++++++++++++++------------- src/base/abci/abcSymm.c | 89 +++++++++++++++++++++++++++++++++++++++++++++++ src/misc/util/utilTruth.h | 27 +++++++++++++- 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] \n" ); - Abc_Print( -2, "\t prints truth table of a symmetric function up to 9 inputs\n" ); - Abc_Print( -2, "\t : 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] \n" ); + Abc_Print( -2, "\t generated a single-output symmetric function\n" ); + Abc_Print( -2, "\t-N : 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 : 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 -- cgit v1.2.3