From 8014f25f6db719fa62336f997963532a14c568f6 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sat, 21 Jan 2012 04:30:10 -0800 Subject: Major restructuring of the code. --- src/opt/dar/darPrec.c | 394 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 394 insertions(+) create mode 100644 src/opt/dar/darPrec.c (limited to 'src/opt/dar/darPrec.c') diff --git a/src/opt/dar/darPrec.c b/src/opt/dar/darPrec.c new file mode 100644 index 00000000..4d164123 --- /dev/null +++ b/src/opt/dar/darPrec.c @@ -0,0 +1,394 @@ +/**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" + +ABC_NAMESPACE_IMPL_START + + +//////////////////////////////////////////////////////////////////////// +/// 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 = ABC_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 ABC_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 = ABC_ALLOC( int, nMints ); + pMintsP = ABC_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]); + } + + ABC_FREE( pMints ); + ABC_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 = ABC_CALLOC( unsigned short, nFuncs ); + uPhases = ABC_CALLOC( char, nFuncs ); + uPerms = ABC_CALLOC( char, nFuncs ); + uMap = ABC_CALLOC( 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; + uMap[uPerm] = uMap[uTruth]; + + uPerm = ~uPerm & 0xFFFF; + uCanons[uPerm] = uTruth; + uPhases[uPerm] = i | 16; + uPerms[uPerm] = k; + uMap[uPerm] = uMap[uTruth]; + } + 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; + uMap[uPerm] = uMap[uTruth]; + + uPerm = ~uPerm & 0xFFFF; + uCanons[uPerm] = uTruth; + uPhases[uPerm] = i | 16; + uPerms[uPerm] = k; + uMap[uPerm] = uMap[uTruth]; + } + else + assert( uCanons[uPerm] == uTruth ); + } + } + } + for ( uTruth = 1; uTruth < 0xffff; uTruth++ ) + assert( uMap[uTruth] != 0 ); + uPhases[(1<<16)-1] = 16; + assert( nClasses == 222 ); + ABC_FREE( pPerms4 ); + if ( puCanons ) + *puCanons = uCanons; + else + ABC_FREE( uCanons ); + if ( puPhases ) + *puPhases = uPhases; + else + ABC_FREE( uPhases ); + if ( puPerms ) + *puPerms = uPerms; + else + ABC_FREE( uPerms ); + if ( puMap ) + *puMap = uMap; + else + ABC_FREE( uMap ); +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + +ABC_NAMESPACE_IMPL_END + -- cgit v1.2.3