diff options
Diffstat (limited to 'src/map/amap/amapParse.c')
| -rw-r--r-- | src/map/amap/amapParse.c | 457 |
1 files changed, 457 insertions, 0 deletions
diff --git a/src/map/amap/amapParse.c b/src/map/amap/amapParse.c new file mode 100644 index 00000000..262fbd5a --- /dev/null +++ b/src/map/amap/amapParse.c @@ -0,0 +1,457 @@ +/**CFile**************************************************************** + + FileName [amapParse.c] + + SystemName [ABC: Logic synthesis and verification system.] + + PackageName [Technology mapper for standard cells.] + + Synopsis [Parses representations of gates.] + + Author [Alan Mishchenko] + + Affiliation [UC Berkeley] + + Date [Ver. 1.0. Started - June 20, 2005.] + + Revision [$Id: amapParse.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $] + +***********************************************************************/ + +#include "amapInt.h" +#include "hop.h" + +//////////////////////////////////////////////////////////////////////// +/// DECLARATIONS /// +//////////////////////////////////////////////////////////////////////// + +// the list of operation symbols to be used in expressions +#define AMAP_EQN_SYM_OPEN '(' // opening paranthesis +#define AMAP_EQN_SYM_CLOSE ')' // closing paranthesis +#define AMAP_EQN_SYM_CONST0 '0' // constant 0 +#define AMAP_EQN_SYM_CONST1 '1' // constant 1 +#define AMAP_EQN_SYM_NEG '!' // negation before the variable +#define AMAP_EQN_SYM_NEGAFT '\'' // negation after the variable +#define AMAP_EQN_SYM_AND '*' // logic AND +#define AMAP_EQN_SYM_XOR '^' // logic XOR +#define AMAP_EQN_SYM_OR '+' // logic OR + +// the list of opcodes (also specifying operation precedence) +#define AMAP_EQN_OPER_NEG 10 // negation +#define AMAP_EQN_OPER_AND 9 // logic AND +#define AMAP_EQN_OPER_XOR 8 // logic XOR +#define AMAP_EQN_OPER_OR 7 // logic OR +#define AMAP_EQN_OPER_MARK 1 // OpStack token standing for an opening paranthesis + +// these are values of the internal Flag +#define AMAP_EQN_FLAG_START 1 // after the opening parenthesis +#define AMAP_EQN_FLAG_VAR 2 // after operation is received +#define AMAP_EQN_FLAG_OPER 3 // after operation symbol is received +#define AMAP_EQN_FLAG_ERROR 4 // when error is detected + +//////////////////////////////////////////////////////////////////////// +/// FUNCTION DEFINITIONS /// +//////////////////////////////////////////////////////////////////////// + +/**Function************************************************************* + + Synopsis [Performs the operation on the top entries in the stack.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Hop_Obj_t * Amap_ParseFormulaOper( Hop_Man_t * pMan, Vec_Ptr_t * pStackFn, int Oper ) +{ + Hop_Obj_t * gArg1, * gArg2, * gFunc; + // perform the given operation + gArg2 = Vec_PtrPop( pStackFn ); + gArg1 = Vec_PtrPop( pStackFn ); + if ( Oper == AMAP_EQN_OPER_AND ) + gFunc = Hop_And( pMan, gArg1, gArg2 ); + else if ( Oper == AMAP_EQN_OPER_OR ) + gFunc = Hop_Or( pMan, gArg1, gArg2 ); + else if ( Oper == AMAP_EQN_OPER_XOR ) + gFunc = Hop_Exor( pMan, gArg1, gArg2 ); + else + return NULL; +// Cudd_Ref( gFunc ); +// Cudd_RecursiveDeref( dd, gArg1 ); +// Cudd_RecursiveDeref( dd, gArg2 ); + Vec_PtrPush( pStackFn, gFunc ); + return gFunc; +} + +/**Function************************************************************* + + Synopsis [Derives the AIG corresponding to the equation.] + + Description [Takes the stream to output messages, the formula, the vector + of variable names and the AIG manager.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Hop_Obj_t * Amap_ParseFormula( FILE * pOutput, char * pFormInit, Vec_Ptr_t * vVarNames, Hop_Man_t * pMan ) +{ + char * pFormula; + Vec_Ptr_t * pStackFn; + Vec_Int_t * pStackOp; + Hop_Obj_t * gFunc; + char * pTemp, * pName; + int nParans, fFound, Flag; + int Oper, Oper1, Oper2; + int i, v; + + // make sure that the number of opening and closing parantheses is the same + nParans = 0; + for ( pTemp = pFormInit; *pTemp; pTemp++ ) + if ( *pTemp == '(' ) + nParans++; + else if ( *pTemp == ')' ) + nParans--; + if ( nParans != 0 ) + { + fprintf( pOutput, "Amap_ParseFormula(): Different number of opening and closing parantheses ().\n" ); + return NULL; + } + + // copy the formula + pFormula = ALLOC( char, strlen(pFormInit) + 3 ); + sprintf( pFormula, "(%s)", pFormInit ); + + // start the stacks + pStackFn = Vec_PtrAlloc( 100 ); + pStackOp = Vec_IntAlloc( 100 ); + + Flag = AMAP_EQN_FLAG_START; + for ( pTemp = pFormula; *pTemp; pTemp++ ) + { + switch ( *pTemp ) + { + // skip all spaces, tabs, and end-of-lines + case ' ': + case '\t': + case '\r': + case '\n': + continue; + case AMAP_EQN_SYM_CONST0: + Vec_PtrPush( pStackFn, Hop_ManConst0(pMan) ); // Cudd_Ref( b0 ); + if ( Flag == AMAP_EQN_FLAG_VAR ) + { + fprintf( pOutput, "Amap_ParseFormula(): No operation symbol before constant 0.\n" ); + Flag = AMAP_EQN_FLAG_ERROR; + break; + } + Flag = AMAP_EQN_FLAG_VAR; + break; + case AMAP_EQN_SYM_CONST1: + Vec_PtrPush( pStackFn, Hop_ManConst1(pMan) ); // Cudd_Ref( b1 ); + if ( Flag == AMAP_EQN_FLAG_VAR ) + { + fprintf( pOutput, "Amap_ParseFormula(): No operation symbol before constant 1.\n" ); + Flag = AMAP_EQN_FLAG_ERROR; + break; + } + Flag = AMAP_EQN_FLAG_VAR; + break; + case AMAP_EQN_SYM_NEG: + if ( Flag == AMAP_EQN_FLAG_VAR ) + {// if NEGBEF follows a variable, AND is assumed + Vec_IntPush( pStackOp, AMAP_EQN_OPER_AND ); + Flag = AMAP_EQN_FLAG_OPER; + } + Vec_IntPush( pStackOp, AMAP_EQN_OPER_NEG ); + break; + case AMAP_EQN_SYM_NEGAFT: + if ( Flag != AMAP_EQN_FLAG_VAR ) + {// if there is no variable before NEGAFT, it is an error + fprintf( pOutput, "Amap_ParseFormula(): No variable is specified before the negation suffix.\n" ); + Flag = AMAP_EQN_FLAG_ERROR; + break; + } + else // if ( Flag == PARSE_FLAG_VAR ) + Vec_PtrPush( pStackFn, Hop_Not( Vec_PtrPop(pStackFn) ) ); + break; + case AMAP_EQN_SYM_AND: + case AMAP_EQN_SYM_OR: + case AMAP_EQN_SYM_XOR: + if ( Flag != AMAP_EQN_FLAG_VAR ) + { + fprintf( pOutput, "Amap_ParseFormula(): There is no variable before AND, EXOR, or OR.\n" ); + Flag = AMAP_EQN_FLAG_ERROR; + break; + } + if ( *pTemp == AMAP_EQN_SYM_AND ) + Vec_IntPush( pStackOp, AMAP_EQN_OPER_AND ); + else if ( *pTemp == AMAP_EQN_SYM_OR ) + Vec_IntPush( pStackOp, AMAP_EQN_OPER_OR ); + else //if ( *pTemp == AMAP_EQN_SYM_XOR ) + Vec_IntPush( pStackOp, AMAP_EQN_OPER_XOR ); + Flag = AMAP_EQN_FLAG_OPER; + break; + case AMAP_EQN_SYM_OPEN: + if ( Flag == AMAP_EQN_FLAG_VAR ) + { +// Vec_IntPush( pStackOp, AMAP_EQN_OPER_AND ); + fprintf( pOutput, "Amap_ParseFormula(): An opening paranthesis follows a var without operation sign.\n" ); + Flag = AMAP_EQN_FLAG_ERROR; + break; + } + Vec_IntPush( pStackOp, AMAP_EQN_OPER_MARK ); + // after an opening bracket, it feels like starting over again + Flag = AMAP_EQN_FLAG_START; + break; + case AMAP_EQN_SYM_CLOSE: + if ( Vec_IntSize( pStackOp ) != 0 ) + { + while ( 1 ) + { + if ( Vec_IntSize( pStackOp ) == 0 ) + { + fprintf( pOutput, "Amap_ParseFormula(): There is no opening paranthesis\n" ); + Flag = AMAP_EQN_FLAG_ERROR; + break; + } + Oper = Vec_IntPop( pStackOp ); + if ( Oper == AMAP_EQN_OPER_MARK ) + break; + + // perform the given operation + if ( Amap_ParseFormulaOper( pMan, pStackFn, Oper ) == NULL ) + { + fprintf( pOutput, "Amap_ParseFormula(): Unknown operation\n" ); + free( pFormula ); + return NULL; + } + } + } + else + { + fprintf( pOutput, "Amap_ParseFormula(): There is no opening paranthesis\n" ); + Flag = AMAP_EQN_FLAG_ERROR; + break; + } + if ( Flag != AMAP_EQN_FLAG_ERROR ) + Flag = AMAP_EQN_FLAG_VAR; + break; + + + default: + // scan the next name + for ( i = 0; pTemp[i] && + pTemp[i] != ' ' && pTemp[i] != '\t' && pTemp[i] != '\r' && pTemp[i] != '\n' && + pTemp[i] != AMAP_EQN_SYM_AND && pTemp[i] != AMAP_EQN_SYM_OR && + pTemp[i] != AMAP_EQN_SYM_XOR && pTemp[i] != AMAP_EQN_SYM_CLOSE; i++ ) + { + if ( pTemp[i] == AMAP_EQN_SYM_NEG || pTemp[i] == AMAP_EQN_SYM_OPEN ) + { + fprintf( pOutput, "Amap_ParseFormula(): The negation sign or an opening paranthesis inside the variable name.\n" ); + Flag = AMAP_EQN_FLAG_ERROR; + break; + } + } + // variable name is found + fFound = 0; + Vec_PtrForEachEntry( vVarNames, pName, v ) + if ( strncmp(pTemp, pName, i) == 0 && strlen(pName) == (unsigned)i ) + { + pTemp += i-1; + fFound = 1; + break; + } + if ( !fFound ) + { + fprintf( pOutput, "Amap_ParseFormula(): The parser cannot find var \"%s\" in the input var list.\n", pTemp ); + Flag = AMAP_EQN_FLAG_ERROR; + break; + } + if ( Flag == AMAP_EQN_FLAG_VAR ) + { + fprintf( pOutput, "Amap_ParseFormula(): The variable name \"%s\" follows another var without operation sign.\n", pTemp ); + Flag = AMAP_EQN_FLAG_ERROR; + break; + } + Vec_PtrPush( pStackFn, Hop_IthVar( pMan, v ) ); // Cudd_Ref( pbVars[v] ); + Flag = AMAP_EQN_FLAG_VAR; + break; + } + + if ( Flag == AMAP_EQN_FLAG_ERROR ) + break; // error exit + else if ( Flag == AMAP_EQN_FLAG_START ) + continue; // go on parsing + else if ( Flag == AMAP_EQN_FLAG_VAR ) + while ( 1 ) + { // check if there are negations in the OpStack + if ( Vec_IntSize( pStackOp ) == 0 ) + break; + Oper = Vec_IntPop( pStackOp ); + if ( Oper != AMAP_EQN_OPER_NEG ) + { + Vec_IntPush( pStackOp, Oper ); + break; + } + else + { + Vec_PtrPush( pStackFn, Hop_Not(Vec_PtrPop(pStackFn)) ); + } + } + else // if ( Flag == AMAP_EQN_FLAG_OPER ) + while ( 1 ) + { // execute all the operations in the OpStack + // with precedence higher or equal than the last one + Oper1 = Vec_IntPop( pStackOp ); // the last operation + if ( Vec_IntSize( pStackOp ) == 0 ) + { // if it is the only operation, push it back + Vec_IntPush( pStackOp, Oper1 ); + break; + } + Oper2 = Vec_IntPop( pStackOp ); // the operation before the last one + if ( Oper2 >= Oper1 ) + { // if Oper2 precedence is higher or equal, execute it + if ( Amap_ParseFormulaOper( pMan, pStackFn, Oper2 ) == NULL ) + { + fprintf( pOutput, "Amap_ParseFormula(): Unknown operation\n" ); + free( pFormula ); + return NULL; + } + Vec_IntPush( pStackOp, Oper1 ); // push the last operation back + } + else + { // if Oper2 precedence is lower, push them back and done + Vec_IntPush( pStackOp, Oper2 ); + Vec_IntPush( pStackOp, Oper1 ); + break; + } + } + } + + if ( Flag != AMAP_EQN_FLAG_ERROR ) + { + if ( Vec_PtrSize(pStackFn) != 0 ) + { + gFunc = Vec_PtrPop(pStackFn); + if ( Vec_PtrSize(pStackFn) == 0 ) + if ( Vec_IntSize( pStackOp ) == 0 ) + { + Vec_PtrFree(pStackFn); + Vec_IntFree(pStackOp); +// Cudd_Deref( gFunc ); + free( pFormula ); + return gFunc; + } + else + fprintf( pOutput, "Amap_ParseFormula(): Something is left in the operation stack\n" ); + else + fprintf( pOutput, "Amap_ParseFormula(): Something is left in the function stack\n" ); + } + else + fprintf( pOutput, "Amap_ParseFormula(): The input string is empty\n" ); + } + free( pFormula ); + return NULL; +} + +/**Function************************************************************* + + Synopsis [Parses equations for the gates.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +int Amap_LibParseEquations( Amap_Lib_t * p, int fVerbose ) +{ + extern int Kit_TruthSupportSize( unsigned * pTruth, int nVars ); + Hop_Man_t * pMan; + Hop_Obj_t * pObj; + Vec_Ptr_t * vNames; + Vec_Int_t * vTruth; + Amap_Gat_t * pGate; + Amap_Pin_t * pPin; + unsigned * pTruth; + int i, nPinMax; + nPinMax = Amap_LibNumPinsMax(p); + if ( nPinMax > AMAP_MAXINS ) + printf( "Gates with more than %d inputs will be ignored.\n", AMAP_MAXINS ); + vTruth = Vec_IntAlloc( 1 << 16 ); + vNames = Vec_PtrAlloc( 100 ); + pMan = Hop_ManStart(); + Hop_IthVar( pMan, nPinMax - 1 ); + Vec_PtrForEachEntry( p->vGates, pGate, i ) + { + if ( pGate->nPins == 0 ) + { + pGate->pFunc = (unsigned *)Aig_MmFlexEntryFetch( p->pMemGates, 4 ); + if ( strcmp( pGate->pForm, AMAP_STRING_CONST0 ) == 0 ) + pGate->pFunc[0] = 0; + else if ( strcmp( pGate->pForm, AMAP_STRING_CONST1 ) == 0 ) + pGate->pFunc[0] = ~0; + else + { + printf( "Cannot parse formula \"%s\" of gate \"%s\" with no pins.\n", pGate->pForm, pGate->pName ); + break; + } + continue; + } + if ( pGate->nPins > AMAP_MAXINS ) + continue; + Vec_PtrClear( vNames ); + Amap_GateForEachPin( pGate, pPin ) + Vec_PtrPush( vNames, pPin->pName ); + pObj = Amap_ParseFormula( stdout, pGate->pForm, vNames, pMan ); + if ( pObj == NULL ) + break; + pTruth = Hop_ManConvertAigToTruth( pMan, pObj, pGate->nPins, vTruth, 0 ); + if ( Kit_TruthSupportSize(pTruth, pGate->nPins) < (int)pGate->nPins ) + { + printf( "Skipping gate \"%s\" because its formula \"%s\" does not depend on some pin variables.\n", pGate->pName, pGate->pForm ); + continue; + } + pGate->pFunc = (unsigned *)Aig_MmFlexEntryFetch( p->pMemGates, sizeof(unsigned)*Aig_TruthWordNum(pGate->nPins) ); + memcpy( pGate->pFunc, pTruth, sizeof(unsigned)*Aig_TruthWordNum(pGate->nPins) ); + } + Vec_PtrFree( vNames ); + Vec_IntFree( vTruth ); + Hop_ManStop( pMan ); + return i == Vec_PtrSize(p->vGates); +} + +/**Function************************************************************* + + Synopsis [Parses equations for the gates.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Amap_LibParseTest( char * pFileName ) +{ + int fVerbose = 1; + Amap_Lib_t * p; + int clk = clock(); + p = Amap_LibReadFile( pFileName, fVerbose ); + if ( p == NULL ) + return; + Amap_LibParseEquations( p, fVerbose ); + Amap_LibFree( p ); + PRT( "Total time", clock() - clk ); +} + +//////////////////////////////////////////////////////////////////////// +/// END OF FILE /// +//////////////////////////////////////////////////////////////////////// + + |