summaryrefslogtreecommitdiffstats
path: root/src/aig/dar/darPrec.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/aig/dar/darPrec.c')
-rw-r--r--src/aig/dar/darPrec.c387
1 files changed, 387 insertions, 0 deletions
diff --git a/src/aig/dar/darPrec.c b/src/aig/dar/darPrec.c
new file mode 100644
index 00000000..8c3a4ce3
--- /dev/null
+++ b/src/aig/dar/darPrec.c
@@ -0,0 +1,387 @@
+/**CFile****************************************************************
+
+ FileName [darPrec.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [DAG-aware AIG rewriting.]
+
+ Synopsis [Truth table precomputation.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - April 28, 2007.]
+
+ Revision [$Id: darPrec.c,v 1.00 2007/04/28 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "darInt.h"
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis [Allocated one-memory-chunk array.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+char ** Dar_ArrayAlloc( int nCols, int nRows, int Size )
+{
+ char ** pRes;
+ char * pBuffer;
+ int i;
+ assert( nCols > 0 && nRows > 0 && Size > 0 );
+ pBuffer = ALLOC( char, nCols * (sizeof(void *) + nRows * Size) );
+ pRes = (char **)pBuffer;
+ pRes[0] = pBuffer + nCols * sizeof(void *);
+ for ( i = 1; i < nCols; i++ )
+ pRes[i] = pRes[0] + i * nRows * Size;
+ return pRes;
+}
+
+/**Function********************************************************************
+
+ Synopsis [Computes the factorial.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+******************************************************************************/
+int Dar_Factorial( int n )
+{
+ int i, Res = 1;
+ for ( i = 1; i <= n; i++ )
+ Res *= i;
+ return Res;
+}
+
+/**Function********************************************************************
+
+ Synopsis [Fills in the array of permutations.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+******************************************************************************/
+void Dar_Permutations_rec( char ** pRes, int nFact, int n, char Array[] )
+{
+ char ** pNext;
+ int nFactNext;
+ int iTemp, iCur, iLast, k;
+
+ if ( n == 1 )
+ {
+ pRes[0][0] = Array[0];
+ return;
+ }
+
+ // get the next factorial
+ nFactNext = nFact / n;
+ // get the last entry
+ iLast = n - 1;
+
+ for ( iCur = 0; iCur < n; iCur++ )
+ {
+ // swap Cur and Last
+ iTemp = Array[iCur];
+ Array[iCur] = Array[iLast];
+ Array[iLast] = iTemp;
+
+ // get the pointer to the current section
+ pNext = pRes + (n - 1 - iCur) * nFactNext;
+
+ // set the last entry
+ for ( k = 0; k < nFactNext; k++ )
+ pNext[k][iLast] = Array[iLast];
+
+ // call recursively for this part
+ Dar_Permutations_rec( pNext, nFactNext, n - 1, Array );
+
+ // swap them back
+ iTemp = Array[iCur];
+ Array[iCur] = Array[iLast];
+ Array[iLast] = iTemp;
+ }
+}
+
+/**Function********************************************************************
+
+ Synopsis [Computes the set of all permutations.]
+
+ Description [The number of permutations in the array is n!. The number of
+ entries in each permutation is n. Therefore, the resulting array is a
+ two-dimentional array of the size: n! x n. To free the resulting array,
+ call free() on the pointer returned by this procedure.]
+
+ SideEffects []
+
+ SeeAlso []
+
+******************************************************************************/
+char ** Dar_Permutations( int n )
+{
+ char Array[50];
+ char ** pRes;
+ int nFact, i;
+ // allocate memory
+ nFact = Dar_Factorial( n );
+ pRes = Dar_ArrayAlloc( nFact, n, sizeof(char) );
+ // fill in the permutations
+ for ( i = 0; i < n; i++ )
+ Array[i] = i;
+ Dar_Permutations_rec( pRes, nFact, n, Array );
+ // print the permutations
+/*
+ {
+ int i, k;
+ for ( i = 0; i < nFact; i++ )
+ {
+ printf( "{" );
+ for ( k = 0; k < n; k++ )
+ printf( " %d", pRes[i][k] );
+ printf( " }\n" );
+ }
+ }
+*/
+ return pRes;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Permutes the given vector of minterms.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Dar_TruthPermute_int( int * pMints, int nMints, char * pPerm, int nVars, int * pMintsP )
+{
+ int m, v;
+ // clean the storage for minterms
+ memset( pMintsP, 0, sizeof(int) * nMints );
+ // go through minterms and add the variables
+ for ( m = 0; m < nMints; m++ )
+ for ( v = 0; v < nVars; v++ )
+ if ( pMints[m] & (1 << v) )
+ pMintsP[m] |= (1 << pPerm[v]);
+}
+
+/**Function*************************************************************
+
+ Synopsis [Permutes the function.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+unsigned Dar_TruthPermute( unsigned Truth, char * pPerms, int nVars, int fReverse )
+{
+ unsigned Result;
+ int * pMints;
+ int * pMintsP;
+ int nMints;
+ int i, m;
+
+ assert( nVars < 6 );
+ nMints = (1 << nVars);
+ pMints = ALLOC( int, nMints );
+ pMintsP = ALLOC( int, nMints );
+ for ( i = 0; i < nMints; i++ )
+ pMints[i] = i;
+
+ Dar_TruthPermute_int( pMints, nMints, pPerms, nVars, pMintsP );
+
+ Result = 0;
+ if ( fReverse )
+ {
+ for ( m = 0; m < nMints; m++ )
+ if ( Truth & (1 << pMintsP[m]) )
+ Result |= (1 << m);
+ }
+ else
+ {
+ for ( m = 0; m < nMints; m++ )
+ if ( Truth & (1 << m) )
+ Result |= (1 << pMintsP[m]);
+ }
+
+ free( pMints );
+ free( pMintsP );
+
+ return Result;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Changes the phase of the function.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+unsigned Dar_TruthPolarize( unsigned uTruth, int Polarity, int nVars )
+{
+ // elementary truth tables
+ static unsigned Signs[5] = {
+ 0xAAAAAAAA, // 1010 1010 1010 1010 1010 1010 1010 1010
+ 0xCCCCCCCC, // 1010 1010 1010 1010 1010 1010 1010 1010
+ 0xF0F0F0F0, // 1111 0000 1111 0000 1111 0000 1111 0000
+ 0xFF00FF00, // 1111 1111 0000 0000 1111 1111 0000 0000
+ 0xFFFF0000 // 1111 1111 1111 1111 0000 0000 0000 0000
+ };
+ unsigned uTruthRes, uCof0, uCof1;
+ int nMints, Shift, v;
+ assert( nVars < 6 );
+ nMints = (1 << nVars);
+ uTruthRes = uTruth;
+ for ( v = 0; v < nVars; v++ )
+ if ( Polarity & (1 << v) )
+ {
+ uCof0 = uTruth & ~Signs[v];
+ uCof1 = uTruth & Signs[v];
+ Shift = (1 << v);
+ uCof0 <<= Shift;
+ uCof1 >>= Shift;
+ uTruth = uCof0 | uCof1;
+ }
+ return uTruth;
+}
+
+/**Function*************************************************************
+
+ Synopsis [Computes NPN canonical forms for 4-variable functions.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+void Dar_Truth4VarNPN( unsigned short ** puCanons, char ** puPhases, char ** puPerms, unsigned char ** puMap )
+{
+ unsigned short * uCanons;
+ unsigned char * uMap;
+ unsigned uTruth, uPhase, uPerm;
+ char ** pPerms4, * uPhases, * uPerms;
+ int nFuncs, nClasses;
+ int i, k;
+
+ nFuncs = (1 << 16);
+ uCanons = ALLOC( unsigned short, nFuncs );
+ uPhases = ALLOC( char, nFuncs );
+ uPerms = ALLOC( char, nFuncs );
+ uMap = ALLOC( unsigned char, nFuncs );
+ memset( uCanons, 0, sizeof(unsigned short) * nFuncs );
+ memset( uPhases, 0, sizeof(char) * nFuncs );
+ memset( uPerms, 0, sizeof(char) * nFuncs );
+ memset( uMap, 0, sizeof(unsigned char) * nFuncs );
+ pPerms4 = Dar_Permutations( 4 );
+
+ nClasses = 1;
+ nFuncs = (1 << 15);
+ for ( uTruth = 1; uTruth < (unsigned)nFuncs; uTruth++ )
+ {
+ // skip already assigned
+ if ( uCanons[uTruth] )
+ {
+ assert( uTruth > uCanons[uTruth] );
+ uMap[~uTruth & 0xFFFF] = uMap[uTruth] = uMap[uCanons[uTruth]];
+ continue;
+ }
+ uMap[uTruth] = nClasses++;
+ for ( i = 0; i < 16; i++ )
+ {
+ uPhase = Dar_TruthPolarize( uTruth, i, 4 );
+ for ( k = 0; k < 24; k++ )
+ {
+ uPerm = Dar_TruthPermute( uPhase, pPerms4[k], 4, 0 );
+ if ( uCanons[uPerm] == 0 )
+ {
+ uCanons[uPerm] = uTruth;
+ uPhases[uPerm] = i;
+ uPerms[uPerm] = k;
+
+ uPerm = ~uPerm & 0xFFFF;
+ uCanons[uPerm] = uTruth;
+ uPhases[uPerm] = i | 16;
+ uPerms[uPerm] = k;
+ }
+ else
+ assert( uCanons[uPerm] == uTruth );
+ }
+ uPhase = Dar_TruthPolarize( ~uTruth & 0xFFFF, i, 4 );
+ for ( k = 0; k < 24; k++ )
+ {
+ uPerm = Dar_TruthPermute( uPhase, pPerms4[k], 4, 0 );
+ if ( uCanons[uPerm] == 0 )
+ {
+ uCanons[uPerm] = uTruth;
+ uPhases[uPerm] = i;
+ uPerms[uPerm] = k;
+
+ uPerm = ~uPerm & 0xFFFF;
+ uCanons[uPerm] = uTruth;
+ uPhases[uPerm] = i | 16;
+ uPerms[uPerm] = k;
+ }
+ else
+ assert( uCanons[uPerm] == uTruth );
+ }
+ }
+ }
+ uPhases[(1<<16)-1] = 16;
+ assert( nClasses == 222 );
+ free( pPerms4 );
+ if ( puCanons )
+ *puCanons = uCanons;
+ else
+ free( uCanons );
+ if ( puPhases )
+ *puPhases = uPhases;
+ else
+ free( uPhases );
+ if ( puPerms )
+ *puPerms = uPerms;
+ else
+ free( uPerms );
+ if ( puMap )
+ *puMap = uMap;
+ else
+ free( uMap );
+}
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-26 15:30:05 +0000