From 857688b95e6a3eb60c06ccc24be21b6267a02f26 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sat, 26 Apr 2014 19:21:06 -0700 Subject: Exploration of functions. --- src/misc/extra/extraUtilEnum.c | 358 +++++++++++++++++++++++++++++++++++++++++ src/misc/extra/module.make | 1 + 2 files changed, 359 insertions(+) create mode 100644 src/misc/extra/extraUtilEnum.c (limited to 'src/misc') diff --git a/src/misc/extra/extraUtilEnum.c b/src/misc/extra/extraUtilEnum.c new file mode 100644 index 00000000..8af700a7 --- /dev/null +++ b/src/misc/extra/extraUtilEnum.c @@ -0,0 +1,358 @@ +/**CFile**************************************************************** + + FileName [extraUtilEnum.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [extra] + + Synopsis [Function enumeration.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: extraUtilEnum.c,v 1.0 2003/02/01 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include +#include +#include +#include +#include "misc/vec/vec.h" +#include "misc/vec/vecHsh.h" + +ABC_NAMESPACE_IMPL_START + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_GetFirst( int * pnVars, int * pnMints, int * pnFuncs, unsigned * pVars, unsigned * pMints, unsigned * pFuncs ) +{ + int nVars = 8; + int nMints = 16; + int nFuncs = 8; + char * pMintStrs[16] = { + "1-1-1-1-", + "1-1--11-", + "1-1-1--1", + "1-1--1-1", + + "-11-1-1-", + "-11--11-", + "-11-1--1", + "-11--1-1", + + "1--11-1-", + "1--1-11-", + "1--11--1", + "1--1-1-1", + + "-1-11-1-", + "-1-1-11-", + "-1-11--1", + "-1-1-1-1" + }; + char * pFuncStrs[8] = { + "1111101011111010", + "0000010100000101", + "1111110010101001", + "0000001101010110", + "1111111111001101", + "0000000000110010", + "1111111111111110", + "0000000000000001", + }; + int i, k; + *pnVars = nVars; + *pnMints = nMints; + *pnFuncs = nFuncs; + // extract mints + for ( i = 0; i < nMints; i++ ) + for ( k = 0; k < nVars; k++ ) + if ( pMintStrs[i][k] == '1' ) + pMints[i] |= (1 << k), pVars[k] |= (1 << i); + // extract funcs + for ( i = 0; i < nFuncs; i++ ) + for ( k = 0; k < nMints; k++ ) + if ( pFuncStrs[i][k] == '1' ) + pFuncs[i] |= (1 << k); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_GetSecond( int * pnVars, int * pnMints, int * pnFuncs, unsigned * pVars, unsigned * pMints, unsigned * pFuncs ) +{ + int nVars = 10; + int nMints = 32; + int nFuncs = 7; + char * pMintStrs[32] = { + "1-1---1---", + "1-1----1--", + "1-1-----1-", + "1-1------1", + + "1--1--1---", + "1--1---1--", + "1--1----1-", + "1--1-----1", + + "1---1-1---", + "1---1--1--", + "1---1---1-", + "1---1----1", + + "1----11---", + "1----1-1--", + "1----1--1-", + "1----1---1", + + + "-11---1---", + "-11----1--", + "-11-----1-", + "-11------1", + + "-1-1--1---", + "-1-1---1--", + "-1-1----1-", + "-1-1-----1", + + "-1--1-1---", + "-1--1--1--", + "-1--1---1-", + "-1--1----1", + + "-1---11---", + "-1---1-1--", + "-1---1--1-", + "-1---1---1" + }; + char * pFuncStrs[7] = { + "11111110110010001110110010000000", + "00000001001101110001001101111111", + "10000001001001000001001001001000", + "01001000000100101000000100100100", + "00100100100000010100100000010010", + "00010010010010000010010010000001", + "11111111111111111111000000000000" + }; + int i, k; + *pnVars = nVars; + *pnMints = nMints; + *pnFuncs = nFuncs; + // extract mints + for ( i = 0; i < nMints; i++ ) + for ( k = 0; k < nVars; k++ ) + if ( pMintStrs[i][k] == '1' ) + pMints[i] |= (1 << k), pVars[k] |= (1 << i); + // extract funcs + for ( i = 0; i < nFuncs; i++ ) + for ( k = 0; k < nMints; k++ ) + if ( pFuncStrs[i][k] == '1' ) + pFuncs[i] |= (1 << k); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_EnumPrint_rec( Vec_Int_t * vGates, int i, int nVars ) +{ + int Fan0 = Vec_IntEntry(vGates, 2*i); + int Fan1 = Vec_IntEntry(vGates, 2*i+1); + char * pOper = Fan0 < Fan1 ? "" : "+"; + if ( Fan0 > Fan1 ) + ABC_SWAP( int, Fan0, Fan1 ); + if ( Fan0 < nVars ) + printf( "%c", 'a'+Fan0 ); + else + { + printf( "(" ); + Abc_EnumPrint_rec( vGates, Fan0, nVars ); + printf( ")" ); + } + printf( "%s", pOper ); + if ( Fan1 < nVars ) + printf( "%c", 'a'+Fan1 ); + else + { + printf( "(" ); + Abc_EnumPrint_rec( vGates, Fan1, nVars ); + printf( ")" ); + } +} +void Abc_EnumPrint( Vec_Int_t * vGates, int i, int nVars ) +{ + assert( 2*i < Vec_IntSize(vGates) ); + Abc_EnumPrint_rec( vGates, i, nVars ); + printf( "\n" ); +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline int Abc_DataHasBit( word * p, word i ) { return (p[(i)>>6] & (1<<((i) & 63))) > 0; } +static inline void Abc_DataXorBit( word * p, word i ) { p[(i)>>6] ^= (1<<((i) & 63)); } + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Abc_EnumerateFunctions() +{ + int nVars; + int nMints; + int nFuncs; + unsigned pVars[100] = {0}; + unsigned pMints[100] = {0}; + unsigned pFuncs[100] = {0}; + unsigned Truth; + int FuncDone[100] = {0}; + int GateCount[100] = {0}; + int i, k, n, a, b, v; + abctime clk = Abc_Clock(); + Vec_Int_t * vGates = Vec_IntAlloc( 100000 ); + Vec_Int_t * vTruths = Vec_IntAlloc( 100000 ); +// Vec_Int_t * vHash = Vec_IntStartFull( 1 << 16 ); + word * pHash; + + // extract data +// Abc_GetFirst( &nVars, &nMints, &nFuncs, pVars, pMints, pFuncs ); + Abc_GetSecond( &nVars, &nMints, &nFuncs, pVars, pMints, pFuncs ); + + // create hash table + assert( nMints == 16 || nMints == 32 ); + pHash = (word *)ABC_CALLOC( char, 1 << (nMints-3) ); + + // create elementary gates + for ( k = 0; k < nVars; k++ ) + { +// Vec_IntWriteEntry( vHash, pVars[k], k ); + Abc_DataXorBit( pHash, pVars[k] ); + Vec_IntPush( vTruths, pVars[k] ); + Vec_IntPush( vGates, -1 ); + Vec_IntPush( vGates, -1 ); + } + + // go through different number of variables + GateCount[0] = 0; + GateCount[1] = nVars; + assert( Vec_IntSize(vTruths) == nVars ); + for ( n = 0; n < 10; n++ ) + { + for ( a = 0; a <= n; a++ ) + for ( b = a; b <= n; b++ ) + if ( a + b == n ) + { + printf( "Trying %d + %d + 1 = %d\n", a, b, n+1 ); + for ( i = GateCount[a]; i < GateCount[a+1]; i++ ) + for ( k = GateCount[b]; k < GateCount[b+1]; k++ ) + if ( i < k ) + { + Truth = Vec_IntEntry(vTruths, i) & Vec_IntEntry(vTruths, k); +// if ( Vec_IntEntry(vHash, Truth) == -1 ) + if ( !Abc_DataHasBit(pHash, Truth) ) + { +// Vec_IntWriteEntry( vHash, Truth, Vec_IntSize(vTruths) ); + Abc_DataXorBit( pHash, Truth ); + Vec_IntPush( vTruths, Truth ); + Vec_IntPush( vGates, i ); + Vec_IntPush( vGates, k ); + + for ( v = 0; v < nFuncs; v++ ) + if ( !FuncDone[v] && Truth == pFuncs[v] ) + { + printf( "Found function %d with %d gates: ", v, n+1 ); + Abc_EnumPrint( vGates, Vec_IntSize(vTruths)-1, nVars ); + FuncDone[v] = 1; + } + } + Truth = Vec_IntEntry(vTruths, i) | Vec_IntEntry(vTruths, k); +// if ( Vec_IntEntry(vHash, Truth) == -1 ) + if ( !Abc_DataHasBit(pHash, Truth) ) + { +// Vec_IntWriteEntry( vHash, Truth, Vec_IntSize(vTruths) ); + Abc_DataXorBit( pHash, Truth ); + Vec_IntPush( vTruths, Truth ); + Vec_IntPush( vGates, k ); + Vec_IntPush( vGates, i ); + + for ( v = 0; v < nFuncs; v++ ) + if ( !FuncDone[v] && Truth == pFuncs[v] ) + { + printf( "Found function %d with %d gates: ", v, n+1 ); + Abc_EnumPrint( vGates, Vec_IntSize(vTruths)-1, nVars ); + FuncDone[v] = 1; + } + } + } + } + GateCount[n+2] = Vec_IntSize(vTruths); + printf( "Finished %d gates. Truths = %10d. ", n+1, Vec_IntSize(vTruths) ); + Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); + } + ABC_FREE( pHash ); +// Vec_IntFree( vHash ); + Vec_IntFree( vGates ); + Vec_IntFree( vTruths ); +} + + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + +ABC_NAMESPACE_IMPL_END + diff --git a/src/misc/extra/module.make b/src/misc/extra/module.make index 8a66c4b7..466d2279 100644 --- a/src/misc/extra/module.make +++ b/src/misc/extra/module.make @@ -10,6 +10,7 @@ SRC += src/misc/extra/extraBddAuto.c \ src/misc/extra/extraUtilCanon.c \ src/misc/extra/extraUtilCube.c \ src/misc/extra/extraUtilDsd.c \ + src/misc/extra/extraUtilEnum.c \ src/misc/extra/extraUtilFile.c \ src/misc/extra/extraUtilMemory.c \ src/misc/extra/extraUtilMisc.c \ -- cgit v1.2.3