From 4812c90424dfc40d26725244723887a2d16ddfd9 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Mon, 1 Oct 2007 08:01:00 -0700 Subject: Version abc71001 --- src/map/super/superAnd.c | 696 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 696 insertions(+) create mode 100644 src/map/super/superAnd.c (limited to 'src/map/super/superAnd.c') diff --git a/src/map/super/superAnd.c b/src/map/super/superAnd.c new file mode 100644 index 00000000..52473fba --- /dev/null +++ b/src/map/super/superAnd.c @@ -0,0 +1,696 @@ +/**CFile**************************************************************** + + FileName [superAnd.c] + + PackageName [MVSIS 1.3: Multi-valued logic synthesis system.] + + Synopsis [Pre-computation of supergates.] + + Author [MVSIS Group] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - September 8, 2003.] + + Revision [$Id: superAnd.c,v 1.3 2004/06/28 14:20:25 alanmi Exp $] + +***********************************************************************/ + +#include "superInt.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +// the bit masks +#define SUPER_MASK(n) ((~((unsigned)0)) >> (32-n)) +#define SUPER_FULL (~((unsigned)0)) + +// data structure for AND2 subgraph precomputation +typedef struct Super2_ManStruct_t_ Super2_Man_t; // manager +typedef struct Super2_LibStruct_t_ Super2_Lib_t; // library +typedef struct Super2_GateStruct_t_ Super2_Gate_t; // supergate + +struct Super2_ManStruct_t_ +{ + Extra_MmFixed_t * pMem; // memory manager for all supergates + stmm_table * tTable; // mapping of truth tables into gates + int nTried; // the total number of tried +}; + +struct Super2_LibStruct_t_ +{ + int i; // used to iterate through the table + int k; // used to iterate through the table + int nInputs; // the number of inputs + int nMints; // the number of minterms + int nLevels; // the number of logic levels + int nGates; // the number of gates in the library + int nGatesAlloc; // the number of allocated places + Super2_Gate_t ** pGates; // the gates themselves + unsigned uMaskBit; // the mask used to determine the compl bit +}; + +struct Super2_GateStruct_t_ +{ + unsigned uTruth; // the truth table of this supergate + Super2_Gate_t * pOne; // the left wing + Super2_Gate_t * pTwo; // the right wing + Super2_Gate_t * pNext; // the next gate in the table +}; + + +// manipulation of complemented attributes +#define Super2_IsComplement(p) (((int)((unsigned long) (p) & 01))) +#define Super2_Regular(p) ((Super2_Gate_t *)((unsigned long)(p) & ~01)) +#define Super2_Not(p) ((Super2_Gate_t *)((unsigned long)(p) ^ 01)) +#define Super2_NotCond(p,c) ((Super2_Gate_t *)((unsigned long)(p) ^ (c))) + +// iterating through the gates in the library +#define Super2_LibForEachGate( Lib, Gate ) \ + for ( Lib->i = 0; \ + Lib->i < Lib->nGates && (Gate = Lib->pGates[Lib->i]); \ + Lib->i++ ) +#define Super2_LibForEachGate2( Lib, Gate2 ) \ + for ( Lib->k = 0; \ + Lib->k < Lib->i && (Gate2 = Lib->pGates[Lib->k]); \ + Lib->k++ ) + +// static functions +static Super2_Man_t * Super2_ManStart(); +static void Super2_ManStop( Super2_Man_t * pMan ); +static Super2_Lib_t * Super2_LibStart(); +static Super2_Lib_t * Super2_LibDup( Super2_Lib_t * pLib ); +static void Super2_LibStop( Super2_Lib_t * pLib ); +static void Super2_LibAddGate( Super2_Lib_t * pLib, Super2_Gate_t * pGate ); +static Super2_Lib_t * Super2_LibFirst( Super2_Man_t * pMan, int nInputs ); +static Super2_Lib_t * Super2_LibCompute( Super2_Man_t * pMan, Super2_Lib_t * pLib ); + +static void Super2_LibWrite( Super2_Lib_t * pLib ); +static void Super2_LibWriteGate( FILE * pFile, Super2_Lib_t * pLib, Super2_Gate_t * pGate ); +static char * Super2_LibWriteGate_rec( Super2_Gate_t * pGate, int fInv, int Level ); +static int Super2_LibWriteCompare( char * pStr1, char * pStr2 ); +static int Super2_LibCompareGates( Super2_Gate_t ** ppG1, Super2_Gate_t ** ppG2 ); + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Precomputes the library of AND2 gates.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Super2_Precompute( int nInputs, int nLevels, int fVerbose ) +{ + Super2_Man_t * pMan; + Super2_Lib_t * pLibCur, * pLibNext; + int Level; + int clk; + + assert( nInputs < 6 ); + + // start the manager + pMan = Super2_ManStart(); + + // get the starting supergates + pLibCur = Super2_LibFirst( pMan, nInputs ); + + // perform the computation of supergates +printf( "Computing supergates for %d inputs and %d levels:\n", nInputs, nLevels ); + for ( Level = 1; Level <= nLevels; Level++ ) + { +clk = clock(); + pLibNext = Super2_LibCompute( pMan, pLibCur ); + pLibNext->nLevels = Level; + Super2_LibStop( pLibCur ); + pLibCur = pLibNext; +printf( "Level %d: Tried = %7d. Computed = %7d. ", Level, pMan->nTried, pLibCur->nGates ); +PRT( "Runtime", clock() - clk ); +fflush( stdout ); + } + +printf( "Writing the output file...\n" ); +fflush( stdout ); + // write them into a file + Super2_LibWrite( pLibCur ); + Super2_LibStop( pLibCur ); + + // stop the manager + Super2_ManStop( pMan ); +} + + + + +/**Function************************************************************* + + Synopsis [Starts the manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Super2_Man_t * Super2_ManStart() +{ + Super2_Man_t * pMan; + pMan = ALLOC( Super2_Man_t, 1 ); + memset( pMan, 0, sizeof(Super2_Man_t) ); + pMan->pMem = Extra_MmFixedStart( sizeof(Super2_Gate_t) ); + pMan->tTable = stmm_init_table( st_ptrcmp, st_ptrhash ); + return pMan; +} + +/**Function************************************************************* + + Synopsis [Stops the manager.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Super2_ManStop( Super2_Man_t * pMan ) +{ + Extra_MmFixedStop( pMan->pMem ); + stmm_free_table( pMan->tTable ); + free( pMan ); +} + +/**Function************************************************************* + + Synopsis [Starts the library.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Super2_Lib_t * Super2_LibStart() +{ + Super2_Lib_t * pLib; + pLib = ALLOC( Super2_Lib_t, 1 ); + memset( pLib, 0, sizeof(Super2_Lib_t) ); + return pLib; +} + +/**Function************************************************************* + + Synopsis [Duplicates the library.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Super2_Lib_t * Super2_LibDup( Super2_Lib_t * pLib ) +{ + Super2_Lib_t * pLibNew; + pLibNew = Super2_LibStart(); + pLibNew->nInputs = pLib->nInputs; + pLibNew->nMints = pLib->nMints; + pLibNew->nLevels = pLib->nLevels; + pLibNew->nGates = pLib->nGates; + pLibNew->uMaskBit = pLib->uMaskBit; + pLibNew->nGatesAlloc = 1000 + pLib->nGatesAlloc; + pLibNew->pGates = ALLOC( Super2_Gate_t *, pLibNew->nGatesAlloc ); + memcpy( pLibNew->pGates, pLib->pGates, pLibNew->nGates * sizeof(Super2_Gate_t *) ); + return pLibNew; +} + +/**Function************************************************************* + + Synopsis [Add gate to the library.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Super2_LibAddGate( Super2_Lib_t * pLib, Super2_Gate_t * pGate ) +{ + if ( pLib->nGates == pLib->nGatesAlloc ) + { + pLib->pGates = REALLOC( Super2_Gate_t *, pLib->pGates, 3 * pLib->nGatesAlloc ); + pLib->nGatesAlloc *= 3; + } + pLib->pGates[ pLib->nGates++ ] = pGate; +} + +/**Function************************************************************* + + Synopsis [Stops the library.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Super2_LibStop( Super2_Lib_t * pLib ) +{ + free( pLib->pGates ); + free( pLib ); +} + +/**Function************************************************************* + + Synopsis [Derives the starting supergates.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Super2_Lib_t * Super2_LibFirst( Super2_Man_t * pMan, int nInputs ) +{ + Super2_Lib_t * pLib; + int v, m; + + // start the library + pLib = Super2_LibStart(); + + // create the starting supergates + pLib->nInputs = nInputs; + pLib->nMints = (1 << nInputs); + pLib->nLevels = 0; + pLib->nGates = nInputs + 1; + pLib->nGatesAlloc = nInputs + 1; + pLib->uMaskBit = (1 << (pLib->nMints-1)); + pLib->pGates = ALLOC( Super2_Gate_t *, nInputs + 1 ); + // add the constant 0 + pLib->pGates[0] = (Super2_Gate_t *)Extra_MmFixedEntryFetch( pMan->pMem ); + memset( pLib->pGates[0], 0, sizeof(Super2_Gate_t) ); + // add the elementary gates + for ( v = 0; v < nInputs; v++ ) + { + pLib->pGates[v+1] = (Super2_Gate_t *)Extra_MmFixedEntryFetch( pMan->pMem ); + memset( pLib->pGates[v+1], 0, sizeof(Super2_Gate_t) ); + pLib->pGates[v+1]->pTwo = (Super2_Gate_t *)v; + } + + // set up their truth tables + for ( m = 0; m < pLib->nMints; m++ ) + for ( v = 0; v < nInputs; v++ ) + if ( m & (1 << v) ) + pLib->pGates[v+1]->uTruth |= (1 << m); + return pLib; +} + +/**Function************************************************************* + + Synopsis [Precomputes one level of supergates.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Super2_Lib_t * Super2_LibCompute( Super2_Man_t * pMan, Super2_Lib_t * pLib ) +{ + Super2_Lib_t * pLibNew; + Super2_Gate_t * pGate1, * pGate2, * pGateNew; + Super2_Gate_t ** ppGate; + unsigned Mask = SUPER_MASK(pLib->nMints); + unsigned uTruth, uTruthR, uTruth1, uTruth2, uTruth1c, uTruth2c; + + // start the new library + pLibNew = Super2_LibDup( pLib ); + + // reset the hash table + stmm_free_table( pMan->tTable ); + pMan->tTable = stmm_init_table( st_ptrcmp, st_ptrhash ); + // set the starting things into the hash table + Super2_LibForEachGate( pLibNew, pGate1 ) + { + uTruthR = ((pGate1->uTruth & pLibNew->uMaskBit)? Mask & ~pGate1->uTruth : pGate1->uTruth); + + if ( stmm_lookup( pMan->tTable, (char *)uTruthR, (char **)&pGate2 ) ) + { + printf( "New gate:\n" ); + Super2_LibWriteGate( stdout, pLibNew, pGate1 ); + printf( "Gate in the table:\n" ); + Super2_LibWriteGate( stdout, pLibNew, pGate2 ); + assert( 0 ); + } + stmm_insert( pMan->tTable, (char *)uTruthR, (char *)pGate1 ); + } + + + // set the number of gates tried + pMan->nTried = pLibNew->nGates; + + // go through the gate pairs + Super2_LibForEachGate( pLib, pGate1 ) + { + if ( pLib->i && pLib->i % 300 == 0 ) + { + printf( "Tried %5d first gates...\n", pLib->i ); + fflush( stdout ); + } + + Super2_LibForEachGate2( pLib, pGate2 ) + { + uTruth1 = pGate1->uTruth; + uTruth2 = pGate2->uTruth; + uTruth1c = Mask & ~uTruth1; + uTruth2c = Mask & ~uTruth2; + + // none complemented + uTruth = uTruth1 & uTruth2; + uTruthR = ((uTruth & pLibNew->uMaskBit)? Mask & ~uTruth : uTruth); + + if ( !stmm_find_or_add( pMan->tTable, (char *)uTruthR, (char ***)&ppGate ) ) + { + pGateNew = (Super2_Gate_t *)Extra_MmFixedEntryFetch( pMan->pMem ); + pGateNew->pOne = pGate1; + pGateNew->pTwo = pGate2; + pGateNew->uTruth = uTruth; + *ppGate = pGateNew; + Super2_LibAddGate( pLibNew, pGateNew ); + } + + // one complemented + uTruth = uTruth1c & uTruth2; + uTruthR = ((uTruth & pLibNew->uMaskBit)? Mask & ~uTruth : uTruth); + + if ( !stmm_find_or_add( pMan->tTable, (char *)uTruthR, (char ***)&ppGate ) ) + { + pGateNew = (Super2_Gate_t *)Extra_MmFixedEntryFetch( pMan->pMem ); + pGateNew->pOne = Super2_Not(pGate1); + pGateNew->pTwo = pGate2; + pGateNew->uTruth = uTruth; + *ppGate = pGateNew; + Super2_LibAddGate( pLibNew, pGateNew ); + } + + // another complemented + uTruth = uTruth1 & uTruth2c; + uTruthR = ((uTruth & pLibNew->uMaskBit)? Mask & ~uTruth : uTruth); + + if ( !stmm_find_or_add( pMan->tTable, (char *)uTruthR, (char ***)&ppGate ) ) + { + pGateNew = (Super2_Gate_t *)Extra_MmFixedEntryFetch( pMan->pMem ); + pGateNew->pOne = pGate1; + pGateNew->pTwo = Super2_Not(pGate2); + pGateNew->uTruth = uTruth; + *ppGate = pGateNew; + Super2_LibAddGate( pLibNew, pGateNew ); + } + + // both complemented + uTruth = uTruth1c & uTruth2c; + uTruthR = ((uTruth & pLibNew->uMaskBit)? Mask & ~uTruth : uTruth); + + if ( !stmm_find_or_add( pMan->tTable, (char *)uTruthR, (char ***)&ppGate ) ) + { + pGateNew = (Super2_Gate_t *)Extra_MmFixedEntryFetch( pMan->pMem ); + pGateNew->pOne = Super2_Not(pGate1); + pGateNew->pTwo = Super2_Not(pGate2); + pGateNew->uTruth = uTruth; + *ppGate = pGateNew; + Super2_LibAddGate( pLibNew, pGateNew ); + } + + pMan->nTried += 4; + } + } + return pLibNew; +} + + +static unsigned s_uMaskBit; +static unsigned s_uMaskAll; + +/**Function************************************************************* + + Synopsis [Writes the library into the file.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Super2_LibWrite( Super2_Lib_t * pLib ) +{ + Super2_Gate_t * pGate; + FILE * pFile; + char FileName[100]; + int clk; + + if ( pLib->nLevels > 5 ) + { + printf( "Cannot write file for %d levels.\n", pLib->nLevels ); + return; + } + +clk = clock(); + // sort the supergates by truth table + s_uMaskBit = pLib->uMaskBit; + s_uMaskAll = SUPER_MASK(pLib->nMints); + qsort( (void *)pLib->pGates, pLib->nGates, sizeof(Super2_Gate_t *), + (int (*)(const void *, const void *)) Super2_LibCompareGates ); + assert( Super2_LibCompareGates( pLib->pGates, pLib->pGates + pLib->nGates - 1 ) < 0 ); +PRT( "Sorting", clock() - clk ); + + + // start the file + sprintf( FileName, "superI%dL%d", pLib->nInputs, pLib->nLevels ); + pFile = fopen( FileName, "w" ); + fprintf( pFile, "# AND2/INV supergates derived on %s.\n", Extra_TimeStamp() ); + fprintf( pFile, "# Command line: \"super2 -i %d -l %d\".\n", pLib->nInputs, pLib->nLevels ); + fprintf( pFile, "# The number of inputs = %6d.\n", pLib->nInputs ); + fprintf( pFile, "# The number of levels = %6d.\n", pLib->nLevels ); + fprintf( pFile, "# The number of supergates = %6d.\n", pLib->nGates ); + fprintf( pFile, "# The total functions = %6d.\n", (1<<(pLib->nMints-1)) ); + fprintf( pFile, "\n" ); + fprintf( pFile, "%6d\n", pLib->nGates ); + + // print the gates + Super2_LibForEachGate( pLib, pGate ) + Super2_LibWriteGate( pFile, pLib, pGate ); + fclose( pFile ); + + printf( "The supergates are written into file \"%s\" ", FileName ); + printf( "(%0.2f Mb).\n", ((double)Extra_FileSize(FileName))/(1<<20) ); +} + +/**Function************************************************************* + + Synopsis [Writes the gate into the file.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Super2_LibCompareGates( Super2_Gate_t ** ppG1, Super2_Gate_t ** ppG2 ) +{ + Super2_Gate_t * pG1 = *ppG1; + Super2_Gate_t * pG2 = *ppG2; + unsigned uTruth1, uTruth2; + + uTruth1 = (pG1->uTruth & s_uMaskBit)? s_uMaskAll & ~pG1->uTruth : pG1->uTruth; + uTruth2 = (pG2->uTruth & s_uMaskBit)? s_uMaskAll & ~pG2->uTruth : pG2->uTruth; + + if ( uTruth1 < uTruth2 ) + return -1; + return 1; +} + +/**Function************************************************************* + + Synopsis [Writes the gate into the file.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Super2_LibWriteGate( FILE * pFile, Super2_Lib_t * pLib, Super2_Gate_t * pGate ) +{ +// unsigned uTruthR; + unsigned uTruth; + int fInv; + + // check whether the gate need complementation + fInv = (int)(pGate->uTruth & pLib->uMaskBit); + uTruth = (fInv? ~pGate->uTruth : pGate->uTruth); +/* + // reverse the truth table + uTruthR = 0; + for ( m = 0; m < pLib->nMints; m++ ) + if ( uTruth & (1 << m) ) + uTruthR |= (1 << (pLib->nMints-1-m)); +*/ + // write the truth table + Extra_PrintBinary( pFile, &uTruth, pLib->nMints ); + fprintf( pFile, " " ); + // write the symbolic expression + fprintf( pFile, "%s", Super2_LibWriteGate_rec( pGate, fInv, pLib->nLevels ) ); + fprintf( pFile, "\n" ); +} + + +/**Function************************************************************* + + Synopsis [Recursively writes the gate into the file.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +char * Super2_LibWriteGate_rec( Super2_Gate_t * pGate, int fInv, int Level ) +{ + static char Buff01[ 3], Buff02[ 3]; // Max0 = 1 + static char Buff11[ 6], Buff12[ 6]; // Max1 = 2*Max0 + 2 = 4 + static char Buff21[ 12], Buff22[ 12]; // Max2 = 2*Max1 + 2 = 10 + static char Buff31[ 25], Buff32[ 25]; // Max3 = 2*Max2 + 2 = 22 + static char Buff41[ 50], Buff42[ 50]; // Max4 = 2*Max3 + 2 = 46 + static char Buff51[100], Buff52[100]; // Max5 = 2*Max4 + 2 = 94 + static char * pBuffs1[6] = { Buff01, Buff11, Buff21, Buff31, Buff41, Buff51 }; + static char * pBuffs2[6] = { Buff02, Buff12, Buff22, Buff32, Buff42, Buff52 }; + char * pBranch; + char * pBuffer1 = pBuffs1[Level]; + char * pBuffer2 = pBuffs2[Level]; + Super2_Gate_t * pGateNext1, * pGateNext2; + int fInvNext1, fInvNext2; + int RetValue; + + // consider the last level + assert( Level >= 0 ); + if ( pGate->pOne == NULL ) + { + if ( pGate->uTruth == 0 ) + { + pBuffer1[0] = (fInv? '1': '0'); + pBuffer1[1] = '$'; + pBuffer1[2] = 0; + } + else + { + pBuffer1[0] = (fInv? 'A' + ((int)pGate->pTwo): 'a' + ((int)pGate->pTwo)); + pBuffer1[1] = 0; + } + return pBuffer1; + } + assert( Level > 0 ); + + + // get the left branch + pGateNext1 = Super2_Regular(pGate->pOne); + fInvNext1 = Super2_IsComplement(pGate->pOne); + pBranch = Super2_LibWriteGate_rec(pGateNext1, fInvNext1, Level - 1); + // copy into Buffer1 + strcpy( pBuffer1, pBranch ); + + // get the right branch + pGateNext2 = Super2_Regular(pGate->pTwo); + fInvNext2 = Super2_IsComplement(pGate->pTwo); + pBranch = Super2_LibWriteGate_rec(pGateNext2, fInvNext2, Level - 1); + + // consider the case when comparison is not necessary + if ( fInvNext1 ^ fInvNext2 ) + { + if ( fInvNext1 > fInvNext2 ) + sprintf( pBuffer2, "%c%s%s%c", (fInv? '<': '('), pBuffer1, pBranch, (fInv? '>': ')') ); + else + sprintf( pBuffer2, "%c%s%s%c", (fInv? '<': '('), pBranch, pBuffer1, (fInv? '>': ')') ); + } + else + { + // compare the two branches + RetValue = Super2_LibWriteCompare( pBuffer1, pBranch ); + if ( RetValue == 1 ) + sprintf( pBuffer2, "%c%s%s%c", (fInv? '<': '('), pBuffer1, pBranch, (fInv? '>': ')') ); + else // if ( RetValue == -1 ) + { + sprintf( pBuffer2, "%c%s%s%c", (fInv? '<': '('), pBranch, pBuffer1, (fInv? '>': ')') ); + if ( RetValue == 0 ) + printf( "Strange!\n" ); + } + } + return pBuffer2; +} + +/**Function************************************************************* + + Synopsis [Compares the two branches of the tree.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Super2_LibWriteCompare( char * pStr1, char * pStr2 ) +{ + while ( 1 ) + { + // skip extra symbols + while ( *pStr1 && *pStr1 < 'A' ) + pStr1++; + while ( *pStr2 && *pStr2 < 'A' ) + pStr2++; + + // check if any one is finished + if ( *pStr1 == 0 || *pStr2 == 0 ) + { + if ( *pStr2 ) + return 1; + return -1; + } + + // compare + if ( *pStr1 == *pStr2 ) + { + pStr1++; + pStr2++; + } + else + { + if ( *pStr1 < *pStr2 ) + return 1; + return -1; + } + } + return 0; +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + -- cgit v1.2.3