From e54d9691616b9a0326e2fdb3156bb4eeb8abfcd7 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sun, 30 Sep 2007 08:01:00 -0700 Subject: Version abc70930 --- src/map/super/superAnd.c | 696 ----------------------------------------------- 1 file changed, 696 deletions(-) delete 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 deleted file mode 100644 index 52473fba..00000000 --- a/src/map/super/superAnd.c +++ /dev/null @@ -1,696 +0,0 @@ -/**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