/**CFile**************************************************************** FileName [bblif.c] SystemName [ABC: Logic synthesis and verification system.] PackageName [Binary BLIF representation for logic networks.] Synopsis [Main implementation module.] Author [Alan Mishchenko] Affiliation [UC Berkeley] Date [Ver. 1.0. Started - February 28, 2009.] Revision [$Id: bblif.c,v 1.00 2009/02/28 00:00:00 alanmi Exp $] ***********************************************************************/ #include #include #include #include #include "misc/util/abc_global.h" #include "bblif.h" ABC_NAMESPACE_IMPL_START //////////////////////////////////////////////////////////////////////// /// DECLARATIONS /// //////////////////////////////////////////////////////////////////////// // vector of integers typedef struct Vec_Int_t_ Vec_Int_t; struct Vec_Int_t_ { int nCap; int nSize; int * pArray; }; // vector of characters typedef struct Vec_Str_t_ Vec_Str_t; struct Vec_Str_t_ { int nCap; int nSize; char * pArray; }; // network object struct Bbl_Obj_t_ { int Id; // user ID int Fnc; // functionality unsigned fCi : 1; // combinational input unsigned fCo : 1; // combinational output unsigned fBox : 1; // subcircuit unsigned fMark : 1; // temporary mark unsigned nFanins : 28; // fanin number int pFanins[0]; // fanin array }; // object function typedef struct Bbl_Fnc_t_ Bbl_Fnc_t; struct Bbl_Fnc_t_ { int nWords; // word number int pWords[0]; // word array }; // object function typedef struct Bbl_Ent_t_ Bbl_Ent_t; struct Bbl_Ent_t_ { int iFunc; // function handle int iNext; // next entry handle }; // data manager struct Bbl_Man_t_ { // data pool Vec_Str_t * pName; // design name Vec_Str_t * pObjs; // vector of objects Vec_Str_t * pFncs; // vector of functions // construction Vec_Int_t * vId2Obj; // mapping user IDs into objects Vec_Int_t * vObj2Id; // mapping objects into user IDs Vec_Int_t * vFaninNums; // mapping user IDs into fanin number // file contents int nFileSize; // file size char * pFileData; // file contents // other data Vec_Str_t * pEnts; // vector of entries int SopMap[17][17]; // mapping vars x cubes into entry handles }; static inline int Bbl_ObjIsCi( Bbl_Obj_t * pObj ) { return pObj->fCi; } static inline int Bbl_ObjIsCo( Bbl_Obj_t * pObj ) { return pObj->fCo; } static inline int Bbl_ObjIsNode( Bbl_Obj_t * pObj ) { return!pObj->fCi && !pObj->fCo; } static inline int Bbl_ObjFaninNum( Bbl_Obj_t * pObj ) { return pObj->nFanins; } static inline Bbl_Obj_t * Bbl_ObjFanin( Bbl_Obj_t * pObj, int i ) { return (Bbl_Obj_t *)(((char *)pObj) - pObj->pFanins[i]); } static inline int Bbl_ObjSize( Bbl_Obj_t * pObj ) { return sizeof(Bbl_Obj_t) + sizeof(int) * pObj->nFanins; } static inline int Bbl_FncSize( Bbl_Fnc_t * pFnc ) { return sizeof(Bbl_Fnc_t) + sizeof(int) * pFnc->nWords; } static inline Bbl_Obj_t * Bbl_VecObj( Vec_Str_t * p, int h ) { return (Bbl_Obj_t *)(p->pArray + h); } static inline Bbl_Fnc_t * Bbl_VecFnc( Vec_Str_t * p, int h ) { return (Bbl_Fnc_t *)(p->pArray + h); } static inline Bbl_Ent_t * Bbl_VecEnt( Vec_Str_t * p, int h ) { return (Bbl_Ent_t *)(p->pArray + h); } static inline char * Bbl_ManSop( Bbl_Man_t * p, int h ) { return (char *)Bbl_VecFnc(p->pFncs, h)->pWords; } static inline Bbl_Obj_t * Bbl_ManObj( Bbl_Man_t * p, int Id ) { return Bbl_VecObj(p->pObjs, p->vId2Obj->pArray[Id]); } #define Bbl_ManForEachObj_int( p, pObj, h ) \ for ( h = 0; (h < p->nSize) && (pObj = Bbl_VecObj(p,h)); h += Bbl_ObjSize(pObj) ) #define Bbl_ManForEachFnc_int( p, pObj, h ) \ for ( h = 0; (h < p->nSize) && (pObj = Bbl_VecFnc(p,h)); h += Bbl_FncSize(pObj) ) #define Bbl_ObjForEachFanin_int( pObj, pFanin, i ) \ for ( i = 0; (i < (int)pObj->nFanins) && (pFanin = Bbl_ObjFanin(pObj,i)); i++ ) #define BBLIF_ALLOC(type, num) ((type *) malloc(sizeof(type) * (num))) #define BBLIF_CALLOC(type, num) ((type *) calloc((num), sizeof(type))) #define BBLIF_FALLOC(type, num) ((type *) memset(malloc(sizeof(type) * (num)), 0xff, sizeof(type) * (num))) #define BBLIF_FREE(obj) ((obj) ? (free((char *) (obj)), (obj) = 0) : 0) #define BBLIF_REALLOC(type, obj, num) \ ((obj) ? ((type *) realloc((char *)(obj), sizeof(type) * (num))) : \ ((type *) malloc(sizeof(type) * (num)))) //////////////////////////////////////////////////////////////////////// /// FUNCTION DEFINITIONS /// //////////////////////////////////////////////////////////////////////// /**Function************************************************************* Synopsis [Allocates a vector with the given capacity.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline Vec_Int_t * Vec_IntAlloc( int nCap ) { Vec_Int_t * p; p = BBLIF_ALLOC( Vec_Int_t, 1 ); if ( nCap > 0 && nCap < 16 ) nCap = 16; p->nSize = 0; p->nCap = nCap; p->pArray = p->nCap? BBLIF_ALLOC( int, p->nCap ) : NULL; return p; } /**Function************************************************************* Synopsis [Allocates a vector with the given size and cleans it.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline Vec_Int_t * Vec_IntStart( int nSize ) { Vec_Int_t * p; p = Vec_IntAlloc( nSize ); p->nSize = nSize; memset( p->pArray, 0, sizeof(int) * nSize ); return p; } /**Function************************************************************* Synopsis [Allocates a vector with the given size and cleans it.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline Vec_Int_t * Vec_IntStartNatural( int nSize ) { Vec_Int_t * p; int i; p = Vec_IntAlloc( nSize ); p->nSize = nSize; for ( i = 0; i < nSize; i++ ) p->pArray[i] = i; return p; } /**Function************************************************************* Synopsis [Creates the vector from an integer array of the given size.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline Vec_Int_t * Vec_IntAllocArray( int * pArray, int nSize ) { Vec_Int_t * p; p = BBLIF_ALLOC( Vec_Int_t, 1 ); p->nSize = nSize; p->nCap = nSize; p->pArray = pArray; return p; } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline void Vec_IntFree( Vec_Int_t * p ) { BBLIF_FREE( p->pArray ); BBLIF_FREE( p ); } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline int Vec_IntSize( Vec_Int_t * p ) { return p->nSize; } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline int Vec_IntEntry( Vec_Int_t * p, int i ) { assert( i >= 0 && i < p->nSize ); return p->pArray[i]; } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline void Vec_IntWriteEntry( Vec_Int_t * p, int i, int Entry ) { assert( i >= 0 && i < p->nSize ); p->pArray[i] = Entry; } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline void Vec_IntAddToEntry( Vec_Int_t * p, int i, int Addition ) { assert( i >= 0 && i < p->nSize ); p->pArray[i] += Addition; } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline int Vec_IntEntryLast( Vec_Int_t * p ) { assert( p->nSize > 0 ); return p->pArray[p->nSize-1]; } /**Function************************************************************* Synopsis [Resizes the vector to the given capacity.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline void Vec_IntGrow( Vec_Int_t * p, int nCapMin ) { if ( p->nCap >= nCapMin ) return; p->pArray = BBLIF_REALLOC( int, p->pArray, nCapMin ); assert( p->pArray ); p->nCap = nCapMin; } /**Function************************************************************* Synopsis [Fills the vector with given number of entries.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline void Vec_IntFill( Vec_Int_t * p, int nSize, int Fill ) { int i; Vec_IntGrow( p, nSize ); for ( i = 0; i < nSize; i++ ) p->pArray[i] = Fill; p->nSize = nSize; } /**Function************************************************************* Synopsis [Fills the vector with given number of entries.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline void Vec_IntFillExtra( Vec_Int_t * p, int nSize, int Fill ) { int i; if ( p->nSize >= nSize ) return; if ( nSize > 2 * p->nCap ) Vec_IntGrow( p, nSize ); else if ( nSize > p->nCap ) Vec_IntGrow( p, 2 * p->nCap ); for ( i = p->nSize; i < nSize; i++ ) p->pArray[i] = Fill; p->nSize = nSize; } /**Function************************************************************* Synopsis [Returns the entry even if the place not exist.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline int Vec_IntGetEntry( Vec_Int_t * p, int i ) { Vec_IntFillExtra( p, i + 1, 0 ); return Vec_IntEntry( p, i ); } /**Function************************************************************* Synopsis [Inserts the entry even if the place does not exist.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline void Vec_IntSetEntry( Vec_Int_t * p, int i, int Entry ) { Vec_IntFillExtra( p, i + 1, 0 ); Vec_IntWriteEntry( p, i, Entry ); } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline void Vec_IntShrink( Vec_Int_t * p, int nSizeNew ) { assert( p->nSize >= nSizeNew ); p->nSize = nSizeNew; } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline void Vec_IntClear( Vec_Int_t * p ) { p->nSize = 0; } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline void Vec_IntPush( Vec_Int_t * p, int Entry ) { if ( p->nSize == p->nCap ) { if ( p->nCap < 16 ) Vec_IntGrow( p, 16 ); else Vec_IntGrow( p, 2 * p->nCap ); } p->pArray[p->nSize++] = Entry; } /**Function************************************************************* Synopsis [Allocates a vector with the given capacity.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline Vec_Str_t * Vec_StrAlloc( int nCap ) { Vec_Str_t * p; p = BBLIF_ALLOC( Vec_Str_t, 1 ); if ( nCap > 0 && nCap < 16 ) nCap = 16; p->nSize = 0; p->nCap = nCap; p->pArray = p->nCap? BBLIF_ALLOC( char, p->nCap ) : NULL; return p; } /**Function************************************************************* Synopsis [Creates the vector from an array of the given size.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline Vec_Str_t * Vec_StrAllocArray( char * pArray, int nSize ) { Vec_Str_t * p; p = BBLIF_ALLOC( Vec_Str_t, 1 ); p->nSize = nSize; p->nCap = nSize; p->pArray = pArray; return p; } /**Fnction************************************************************* Synopsis [Returns a piece of memory.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ char * Vec_StrFetch( Vec_Str_t * p, int nBytes ) { while ( p->nSize + nBytes > p->nCap ) { p->pArray = BBLIF_REALLOC( char, p->pArray, 3 * p->nCap ); p->nCap *= 3; } p->nSize += nBytes; return p->pArray + p->nSize - nBytes; } /**Fnction************************************************************* Synopsis [Write vector into file.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Vec_StrWrite( FILE * pFile, Vec_Str_t * p ) { fwrite( &p->nSize, sizeof(int), 1, pFile ); fwrite( p->pArray, sizeof(char), p->nSize, pFile ); } /**Fnction************************************************************* Synopsis [Write vector into file.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Vec_Str_t * Vec_StrRead( char ** ppStr ) { Vec_Str_t * p; char * pStr = *ppStr; p = Vec_StrAlloc( 0 ); p->nSize = *(int *)pStr; p->pArray = pStr + sizeof(int); *ppStr = pStr + sizeof(int) + p->nSize * sizeof(char); return p; } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline int Vec_StrSize( Vec_Str_t * p ) { return p->nSize; } /**Function************************************************************* Synopsis [] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline void Vec_StrFree( Vec_Str_t * p ) { BBLIF_FREE( p->pArray ); BBLIF_FREE( p ); } /**Fnction************************************************************* Synopsis [Returns the file size.] Description [The file should be closed.] SideEffects [] SeeAlso [] ***********************************************************************/ int Bbl_ManFileSize( char * pFileName ) { FILE * pFile; int nFileSize; pFile = fopen( pFileName, "r" ); if ( pFile == NULL ) { printf( "Bbl_ManFileSize(): The file is unavailable (absent or open).\n" ); return 0; } fseek( pFile, 0, SEEK_END ); nFileSize = ftell( pFile ); fclose( pFile ); return nFileSize; } /**Fnction************************************************************* Synopsis [Read data from file.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ char * Bbl_ManFileRead( char * pFileName ) { FILE * pFile; char * pContents; int nFileSize; int RetValue; nFileSize = Bbl_ManFileSize( pFileName ); pFile = fopen( pFileName, "rb" ); pContents = BBLIF_ALLOC( char, nFileSize ); RetValue = fread( pContents, nFileSize, 1, pFile ); fclose( pFile ); return pContents; } /**Fnction************************************************************* Synopsis [Writes data into file.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Bbl_ManDumpBinaryBlif( Bbl_Man_t * p, char * pFileName ) { FILE * pFile; pFile = fopen( pFileName, "wb" ); Vec_StrWrite( pFile, p->pName ); Vec_StrWrite( pFile, p->pObjs ); Vec_StrWrite( pFile, p->pFncs ); fclose( pFile ); } /**Fnction************************************************************* Synopsis [Creates manager after reading.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Bbl_Man_t * Bbl_ManReadBinaryBlif( char * pFileName ) { Bbl_Man_t * p; Bbl_Obj_t * pObj; char * pBuffer; int h; p = BBLIF_ALLOC( Bbl_Man_t, 1 ); memset( p, 0, sizeof(Bbl_Man_t) ); p->nFileSize = Bbl_ManFileSize( pFileName ); p->pFileData = Bbl_ManFileRead( pFileName ); // extract three managers pBuffer = p->pFileData; p->pName = Vec_StrRead( &pBuffer ); p->pObjs = Vec_StrRead( &pBuffer ); p->pFncs = Vec_StrRead( &pBuffer ); assert( pBuffer - p->pFileData == p->nFileSize ); // remember original IDs in the objects p->vObj2Id = Vec_IntAlloc( 1000 ); Bbl_ManForEachObj_int( p->pObjs, pObj, h ) { Vec_IntPush( p->vObj2Id, pObj->Id ); pObj->Id = Vec_IntSize(p->vObj2Id) - 1; } return p; } /**Fnction************************************************************* Synopsis [Prints stats of the manager.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Bbl_ManPrintStats( Bbl_Man_t * p ) { Bbl_Obj_t * pObj; Bbl_Fnc_t * pFnc; int h, nFuncs = 0, nNodes = 0, nObjs = 0; Bbl_ManForEachObj_int( p->pObjs, pObj, h ) nObjs++, nNodes += Bbl_ObjIsNode(pObj); Bbl_ManForEachFnc_int( p->pFncs, pFnc, h ) nFuncs++; printf( "Total objects = %7d. Total nodes = %7d. Unique functions = %7d.\n", nObjs, nNodes, nFuncs ); printf( "Name manager = %5.2f MB\n", 1.0*Vec_StrSize(p->pName)/(1 << 20) ); printf( "Objs manager = %5.2f MB\n", 1.0*Vec_StrSize(p->pObjs)/(1 << 20) ); printf( "Fncs manager = %5.2f MB\n", 1.0*Vec_StrSize(p->pFncs)/(1 << 20) ); } /**Fnction************************************************************* Synopsis [Deletes the manager.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Bbl_ManStop( Bbl_Man_t * p ) { if ( p->vId2Obj ) Vec_IntFree( p->vId2Obj ); if ( p->vObj2Id ) Vec_IntFree( p->vObj2Id ); if ( p->vFaninNums ) Vec_IntFree( p->vFaninNums ); if ( p->pFileData ) { BBLIF_FREE( p->pFileData ); p->pName->pArray = NULL; p->pObjs->pArray = NULL; p->pFncs->pArray = NULL; } if ( p->pEnts ) Vec_StrFree( p->pEnts ); Vec_StrFree( p->pName ); Vec_StrFree( p->pObjs ); Vec_StrFree( p->pFncs ); BBLIF_FREE( p ); } /**Fnction************************************************************* Synopsis [Creates manager.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Bbl_Man_t * Bbl_ManStart( char * pName ) { Bbl_Man_t * p; int nLength; p = BBLIF_ALLOC( Bbl_Man_t, 1 ); memset( p, 0, sizeof(Bbl_Man_t) ); nLength = pName? 4 * ((strlen(pName) + 1) / 4 + 1) : 0; p->pName = Vec_StrAlloc( nLength ); p->pName->nSize = p->pName->nCap; if ( pName ) strcpy( p->pName->pArray, pName ); p->pObjs = Vec_StrAlloc( 1 << 16 ); p->pFncs = Vec_StrAlloc( 1 << 16 ); p->pEnts = Vec_StrAlloc( 1 << 16 ); p->pEnts->nSize = 1; p->vId2Obj = Vec_IntStart( 1 << 10 ); p->vFaninNums = Vec_IntStart( 1 << 10 ); return p; } /**Function************************************************************* Synopsis [Performs selection sort on the array of cubes.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Bbl_ManSortCubes( char ** pCubes, int nCubes, int nVars ) { char * pTemp; int i, j, best_i; for ( i = 0; i < nCubes-1; i++ ) { best_i = i; for (j = i+1; j < nCubes; j++) if ( memcmp( pCubes[j], pCubes[best_i], nVars ) < 0 ) best_i = j; pTemp = pCubes[i]; pCubes[i] = pCubes[best_i]; pCubes[best_i] = pTemp; } } /**Function************************************************************* Synopsis [Sorts the cubes in the SOP to uniqify them to some extent.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ char * Bbl_ManSortSop( char * pSop, int nVars ) { char ** pCubes, * pSopNew; int c, Length, nCubes; Length = strlen(pSop); assert( Length % (nVars + 3) == 0 ); nCubes = Length / (nVars + 3); if ( nCubes < 2 ) { pSopNew = BBLIF_ALLOC( char, Length + 1 ); memcpy( pSopNew, pSop, Length + 1 ); return pSopNew; } pCubes = BBLIF_ALLOC( char *, nCubes ); for ( c = 0; c < nCubes; c++ ) pCubes[c] = pSop + c * (nVars + 3); if ( nCubes < 300 ) Bbl_ManSortCubes( pCubes, nCubes, nVars ); pSopNew = BBLIF_ALLOC( char, Length + 1 ); for ( c = 0; c < nCubes; c++ ) memcpy( pSopNew + c * (nVars + 3), pCubes[c], nVars + 3 ); BBLIF_FREE( pCubes ); pSopNew[nCubes * (nVars + 3)] = 0; return pSopNew; } /**Fnction************************************************************* Synopsis [Saves one entry.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Bbl_ManCreateEntry( Bbl_Man_t * p, int iFunc, int iNext ) { Bbl_Ent_t * pEnt; pEnt = (Bbl_Ent_t *)Vec_StrFetch( p->pEnts, 2 * sizeof(int) ); pEnt->iFunc = iFunc; pEnt->iNext = iNext; return (char *)pEnt - p->pEnts->pArray; } /**Function************************************************************* Synopsis [Sorts the cubes in the SOP to uniqify them to some extent.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Bbl_ManSopCheckUnique( Bbl_Man_t * p, char * pSop, int nVars, int nCubes, int iFunc ) { Bbl_Fnc_t * pFnc; Bbl_Ent_t * pEnt; int h, Length = strlen(pSop) + 1; int nWords = (Length / 4 + (Length % 4 > 0)); if ( nVars > 16 ) nVars = 16; if ( nCubes > 16 ) nCubes = 16; // if ( nVars == 16 && nCubes == 16 ) // return iFunc; for ( h = p->SopMap[nVars][nCubes]; h; h = pEnt->iNext ) { pEnt = Bbl_VecEnt( p->pEnts, h ); pFnc = Bbl_VecFnc( p->pFncs, pEnt->iFunc ); assert( nVars == 16 || nCubes == 16 || pFnc->nWords == nWords ); if ( pFnc->nWords == nWords && memcmp( pFnc->pWords, pSop, Length ) == 0 ) return pEnt->iFunc; } p->SopMap[nVars][nCubes] = Bbl_ManCreateEntry( p, iFunc, p->SopMap[nVars][nCubes] ); return iFunc; } /**Fnction************************************************************* Synopsis [Saves one SOP.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Bbl_ManSaveSop( Bbl_Man_t * p, char * pSop, int nVars ) { Bbl_Fnc_t * pFnc; char * pSopNew; int iFunc, Length = strlen(pSop) + 1; int nWords = Length / 4 + (Length % 4 > 0); // reorder cubes to semi-canicize SOPs pSopNew = Bbl_ManSortSop( pSop, nVars ); // get the candidate location iFunc = Bbl_ManSopCheckUnique( p, pSopNew, nVars, Length / (nVars + 3), Vec_StrSize(p->pFncs) ); // iFunc = Vec_StrSize(p->pFncs); if ( iFunc == Vec_StrSize(p->pFncs) ) { // store this SOP pFnc = (Bbl_Fnc_t *)Vec_StrFetch( p->pFncs, sizeof(Bbl_Fnc_t) + nWords * sizeof(int) ); pFnc->pWords[nWords-1] = 0; pFnc->nWords = nWords; strcpy( (char *)pFnc->pWords, pSopNew ); assert( iFunc == (char *)pFnc - p->pFncs->pArray ); } BBLIF_FREE( pSopNew ); return iFunc; } /**Fnction************************************************************* Synopsis [Adds one object.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Bbl_ManCreateObject( Bbl_Man_t * p, Bbl_Type_t Type, int ObjId, int nFanins, char * pSop ) { Bbl_Obj_t * pObj; if ( Type == BBL_OBJ_CI && nFanins != 0 ) { printf( "Attempting to create a combinational input with %d fanins (should be 0).\n", nFanins ); return; } if ( Type == BBL_OBJ_CO && nFanins != 1 ) { printf( "Attempting to create a combinational output with %d fanins (should be 1).\n", nFanins ); return; } pObj = (Bbl_Obj_t *)Vec_StrFetch( p->pObjs, sizeof(Bbl_Obj_t) + nFanins * sizeof(int) ); memset( pObj, 0, sizeof(Bbl_Obj_t) ); Vec_IntSetEntry( p->vId2Obj, ObjId, (char *)pObj - p->pObjs->pArray ); Vec_IntSetEntry( p->vFaninNums, ObjId, 0 ); pObj->fCi = (Type == BBL_OBJ_CI); pObj->fCo = (Type == BBL_OBJ_CO); pObj->Id = ObjId; pObj->Fnc = pSop? Bbl_ManSaveSop(p, pSop, nFanins) : -1; pObj->nFanins = nFanins; } /**Fnction************************************************************* Synopsis [Creates fanin/fanout relationship between two objects.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Bbl_ManAddFanin( Bbl_Man_t * p, int ObjId, int FaninId ) { Bbl_Obj_t * pObj, * pFanin; int iFanin; pObj = Bbl_ManObj( p, ObjId ); if ( Bbl_ObjIsCi(pObj) ) { printf( "Bbl_ManAddFanin(): Cannot add fanin of the combinational input (Id = %d).\n", ObjId ); return; } pFanin = Bbl_ManObj( p, FaninId ); if ( Bbl_ObjIsCo(pFanin) ) { printf( "Bbl_ManAddFanin(): Cannot add fanout of the combinational output (Id = %d).\n", FaninId ); return; } iFanin = Vec_IntEntry( p->vFaninNums, ObjId ); if ( iFanin >= (int)pObj->nFanins ) { printf( "Bbl_ManAddFanin(): Trying to add more fanins to object (Id = %d) than declared (%d).\n", ObjId, pObj->nFanins ); return; } assert( iFanin < (int)pObj->nFanins ); Vec_IntWriteEntry( p->vFaninNums, ObjId, iFanin+1 ); pObj->pFanins[iFanin] = (char *)pObj - (char *)pFanin; } /**Fnction************************************************************* Synopsis [Returns 1 if the manager was created correctly.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Bbl_ManCheck( Bbl_Man_t * p ) { Bbl_Obj_t * pObj; int h, RetValue = 1; Bbl_ManForEachObj_int( p->pObjs, pObj, h ) { if ( Bbl_ObjIsNode(pObj) && pObj->Fnc == -1 ) RetValue = 0, printf( "Bbl_ManCheck(): Node %d does not have function specified.\n", pObj->Id ); if ( Bbl_ObjIsCi(pObj) && pObj->Fnc != -1 ) RetValue = 0, printf( "Bbl_ManCheck(): CI with %d has function specified.\n", pObj->Id ); if ( Bbl_ObjIsCo(pObj) && pObj->Fnc != -1 ) RetValue = 0, printf( "Bbl_ManCheck(): CO with %d has function specified.\n", pObj->Id ); if ( Vec_IntEntry(p->vFaninNums, pObj->Id) != (int)pObj->nFanins ) RetValue = 0, printf( "Bbl_ManCheck(): Object %d has less fanins (%d) than declared (%d).\n", pObj->Id, Vec_IntEntry(p->vFaninNums, pObj->Id), pObj->nFanins ); } return RetValue; } /**Fnction************************************************************* Synopsis [Misc APIs.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Bbl_ObjIsInput( Bbl_Obj_t * p ) { return Bbl_ObjIsCi(p); } int Bbl_ObjIsOutput( Bbl_Obj_t * p ) { return Bbl_ObjIsCo(p); } int Bbl_ObjIsLut( Bbl_Obj_t * p ) { return Bbl_ObjIsNode(p); } int Bbl_ObjId( Bbl_Obj_t * p ) { return p->Id; } int Bbl_ObjIdOriginal( Bbl_Man_t * pMan, Bbl_Obj_t * p ) { assert(0); return Vec_IntEntry(pMan->vObj2Id, p->Id); } int Bbl_ObjFaninNumber( Bbl_Obj_t * p ) { return Bbl_ObjFaninNum(p); } char * Bbl_ObjSop( Bbl_Man_t * pMan, Bbl_Obj_t * p ) { return Bbl_ManSop(pMan, p->Fnc); } int Bbl_ObjIsMarked( Bbl_Obj_t * p ) { return p->fMark; } void Bbl_ObjMark( Bbl_Obj_t * p ) { p->fMark = 1; } int Bbl_ObjFncHandle( Bbl_Obj_t * p ) { return p->Fnc; } /**Fnction************************************************************* Synopsis [Returns the name of the design.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ char * Bbl_ManName( Bbl_Man_t * p ) { return p->pName->pArray; } /**Fnction************************************************************* Synopsis [Returns the maximum handle of the SOP.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ int Bbl_ManFncSize( Bbl_Man_t * p ) { return p->pFncs->nSize; } /**Fnction************************************************************* Synopsis [Returns the first object.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Bbl_Obj_t * Bbl_ManObjFirst( Bbl_Man_t * p ) { return Bbl_VecObj( p->pObjs, 0 ); } /**Fnction************************************************************* Synopsis [Returns the next object.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Bbl_Obj_t * Bbl_ManObjNext( Bbl_Man_t * p, Bbl_Obj_t * pObj ) { char * pNext = (char *)pObj + Bbl_ObjSize(pObj); char * pEdge = p->pObjs->pArray + p->pObjs->nSize; return (Bbl_Obj_t *)(pNext < pEdge ? pNext : NULL); } /**Fnction************************************************************* Synopsis [Returns the first fanin.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Bbl_Obj_t * Bbl_ObjFaninFirst( Bbl_Obj_t * p ) { return Bbl_ObjFaninNum(p) ? Bbl_ObjFanin( p, 0 ) : NULL; } /**Fnction************************************************************* Synopsis [Returns the next fanin.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ Bbl_Obj_t * Bbl_ObjFaninNext( Bbl_Obj_t * p, Bbl_Obj_t * pPrev ) { Bbl_Obj_t * pFanin; int i; Bbl_ObjForEachFanin_int( p, pFanin, i ) if ( pFanin == pPrev ) break; return i < Bbl_ObjFaninNum(p) - 1 ? Bbl_ObjFanin( p, i+1 ) : NULL; } /**Fnction************************************************************* Synopsis [Drives text BLIF file for debugging.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ void Bbl_ManDumpBlif( Bbl_Man_t * p, char * pFileName ) { FILE * pFile; Bbl_Obj_t * pObj, * pFanin; pFile = fopen( pFileName, "w" ); fprintf( pFile, "# Test file written by Bbl_ManDumpBlif() in ABC.\n" ); fprintf( pFile, ".model %s\n", Bbl_ManName(p) ); // write objects Bbl_ManForEachObj( p, pObj ) { if ( Bbl_ObjIsInput(pObj) ) fprintf( pFile, ".inputs %d\n", Bbl_ObjId(pObj) ); else if ( Bbl_ObjIsOutput(pObj) ) fprintf( pFile, ".outputs %d\n", Bbl_ObjId(pObj) ); else if ( Bbl_ObjIsLut(pObj) ) { fprintf( pFile, ".names" ); Bbl_ObjForEachFanin( pObj, pFanin ) fprintf( pFile, " %d", Bbl_ObjId(pFanin) ); fprintf( pFile, " %d\n", Bbl_ObjId(pObj) ); fprintf( pFile, "%s", Bbl_ObjSop(p, pObj) ); } else assert( 0 ); } // write output drivers Bbl_ManForEachObj( p, pObj ) { if ( !Bbl_ObjIsOutput(pObj) ) continue; fprintf( pFile, ".names" ); Bbl_ObjForEachFanin( pObj, pFanin ) fprintf( pFile, " %d", Bbl_ObjId(pFanin) ); fprintf( pFile, " %d\n", Bbl_ObjId(pObj) ); fprintf( pFile, "1 1\n" ); } fprintf( pFile, ".end\n" ); fclose( pFile ); } /**Fnction************************************************************* Synopsis [Converting truth table into an SOP.] Description [The truth table is given as a bit-string pTruth composed of 2^nVars bits. The result is an SOP derived by collecting minterms appearing in the truth table. The SOP is represented as a C-string, as documented in file "bblif.h". It is recommended to limit the use of this procedure to Boolean functions up to 6 inputs.] SideEffects [] SeeAlso [] ***********************************************************************/ char * Bbl_ManTruthToSop( unsigned * pTruth, int nVars ) { char * pResult, * pTemp; int nMints, nOnes, b, v; assert( nVars >= 0 && nVars <= 16 ); nMints = (1 << nVars); // count the number of ones nOnes = 0; for ( b = 0; b < nMints; b++ ) nOnes += ((pTruth[b>>5] >> (b&31)) & 1); // handle constants if ( nOnes == 0 || nOnes == nMints ) { pResult = pTemp = BBLIF_ALLOC( char, nVars + 4 ); for ( v = 0; v < nVars; v++ ) *pTemp++ = '-'; *pTemp++ = ' '; *pTemp++ = nOnes? '1' : '0'; *pTemp++ = '\n'; *pTemp++ = 0; assert( pTemp - pResult == nVars + 4 ); return pResult; } pResult = pTemp = BBLIF_ALLOC( char, nOnes * (nVars + 3) + 1 ); for ( b = 0; b < nMints; b++ ) { if ( ((pTruth[b>>5] >> (b&31)) & 1) == 0 ) continue; for ( v = 0; v < nVars; v++ ) *pTemp++ = ((b >> v) & 1)? '1' : '0'; *pTemp++ = ' '; *pTemp++ = '1'; *pTemp++ = '\n'; } *pTemp++ = 0; assert( pTemp - pResult == nOnes * (nVars + 3) + 1 ); return pResult; } /**Function************************************************************* Synopsis [Allocates the array of truth tables for the given number of vars.] Description [] SideEffects [] SeeAlso [] ***********************************************************************/ static inline void Bbl_ManSopToTruthElem( int nVars, unsigned ** pVars ) { unsigned Masks[5] = { 0xAAAAAAAA, 0xCCCCCCCC, 0xF0F0F0F0, 0xFF00FF00, 0xFFFF0000 }; int i, k, nWords; nWords = (nVars <= 5 ? 1 : (1 << (nVars - 5))); for ( i = 0; i < nVars; i++ ) { if ( i < 5 ) { for ( k = 0; k < nWords; k++ ) pVars[i][k] = Masks[i]; } else { for ( k = 0; k < nWords; k++ ) if ( k & (1 << (i-5)) ) pVars[i][k] = ~(unsigned)0; else pVars[i][k] = 0; } } } /**Fnction************************************************************* Synopsis [Converting SOP into a truth table.] Description [The SOP is represented as a C-string, as documented in file "bblif.h". The truth table is returned as a bit-string composed of 2^nVars bits. For functions of less than 6 variables, the full machine word is returned. (The truth table looks as if the function had 5 variables.) The use of this procedure should be limited to Boolean functions with no more than 16 inputs.] SideEffects [] SeeAlso [] ***********************************************************************/ unsigned * Bbl_ManSopToTruth( char * pSop, int nVars ) { unsigned * pTruth, * pCube, * pVars[16]; int nWords = nVars <= 5 ? 1 : (1 << (nVars - 5)); int v, c, w, nCubes, fCompl = 0; if ( pSop == NULL ) return NULL; if ( strlen(pSop) % (nVars + 3) != 0 ) { printf( "Bbl_ManSopToTruth(): SOP is represented incorrectly.\n" ); return NULL; } // create storage for TTs of the result, elementary variables and the temp cube pTruth = BBLIF_ALLOC( unsigned, nWords ); pVars[0] = BBLIF_ALLOC( unsigned, nWords * (nVars+1) ); for ( v = 1; v < nVars; v++ ) pVars[v] = pVars[v-1] + nWords; pCube = pVars[v-1] + nWords; Bbl_ManSopToTruthElem( nVars, pVars ); // iterate through the cubes memset( pTruth, 0, sizeof(unsigned) * nWords ); nCubes = strlen(pSop) / (nVars + 3); for ( c = 0; c < nCubes; c++ ) { fCompl = (pSop[nVars+1] == '0'); memset( pCube, 0xff, sizeof(unsigned) * nWords ); // iterate through the literals of the cube for ( v = 0; v < nVars; v++ ) if ( pSop[v] == '1' ) for ( w = 0; w < nWords; w++ ) pCube[w] &= pVars[v][w]; else if ( pSop[v] == '0' ) for ( w = 0; w < nWords; w++ ) pCube[w] &= ~pVars[v][w]; // add cube to storage for ( w = 0; w < nWords; w++ ) pTruth[w] |= pCube[w]; // go to the next cube pSop += (nVars + 3); } BBLIF_FREE( pVars[0] ); if ( fCompl ) for ( w = 0; w < nWords; w++ ) pTruth[w] = ~pTruth[w]; return pTruth; } /**Fnction************************************************************* Synopsis [Checks the truth table computation.] Description [We construct the logic network for the half-adder represnted using the BLIF file below] SideEffects [] SeeAlso [] ***********************************************************************/ void Bbl_ManTestTruth( char * pSop, int nVars ) { unsigned * pTruth; char * pSopNew; pTruth = Bbl_ManSopToTruth( pSop, nVars ); pSopNew = Bbl_ManTruthToSop( pTruth, nVars ); printf( "Old SOP:\n%s\n", pSop ); printf( "New SOP:\n%s\n", pSopNew ); BBLIF_FREE( pSopNew ); BBLIF_FREE( pTruth ); } /**Fnction************************************************************* Synopsis [This demo shows using the internal to construct a half-adder.] Description [We construct the logic network for the half-adder represnted using the BLIF file below] SideEffects [] SeeAlso [] ***********************************************************************/ void Bbl_ManSimpleDemo() { /* # There are contents of a BLIF file representing a half-adder: .model hadder .inputs a // ID = 1 .inputs b // ID = 2 .inputs cin // ID = 3 .outputs s // ID = 4 .outputs cout // ID = 5 .names a b cin s_driver // ID = 6 100 1 010 1 001 1 111 1 .names a b cin cout_driver // ID = 7 -11 1 1-1 1 11- 1 .names s_driver s 1 1 .names cout_driver cout 1 1 .end */ Bbl_Man_t * p; // start the data manager p = Bbl_ManStart( "hadder" ); // create CIs Bbl_ManCreateObject( p, BBL_OBJ_CI, 1, 0, NULL ); // a Bbl_ManCreateObject( p, BBL_OBJ_CI, 2, 0, NULL ); // b Bbl_ManCreateObject( p, BBL_OBJ_CI, 3, 0, NULL ); // cin // create COs Bbl_ManCreateObject( p, BBL_OBJ_CO, 4, 1, NULL ); // s Bbl_ManCreateObject( p, BBL_OBJ_CO, 5, 1, NULL ); // cout // create internal nodes Bbl_ManCreateObject( p, BBL_OBJ_NODE, 6, 3, "100 1\n010 1\n001 1\n111 1\n" ); // s_driver Bbl_ManCreateObject( p, BBL_OBJ_NODE, 7, 3, "-11 1\n1-1 1\n11- 1\n" ); // cout_driver // add fanins of node 6 Bbl_ManAddFanin( p, 6, 1 ); // s_driver <- a Bbl_ManAddFanin( p, 6, 2 ); // s_driver <- b Bbl_ManAddFanin( p, 6, 3 ); // s_driver <- cin // add fanins of node 7 Bbl_ManAddFanin( p, 7, 1 ); // cout_driver <- a Bbl_ManAddFanin( p, 7, 2 ); // cout_driver <- b Bbl_ManAddFanin( p, 7, 3 ); // cout_driver <- cin // add fanins of COs Bbl_ManAddFanin( p, 4, 6 ); // s <- s_driver Bbl_ManAddFanin( p, 5, 7 ); // cout <- cout_driver // sanity check Bbl_ManCheck( p ); // write BLIF file as a sanity check Bbl_ManDumpBlif( p, "hadder.blif" ); // write binary BLIF file Bbl_ManDumpBinaryBlif( p, "hadder.bblif" ); // remove the manager Bbl_ManStop( p ); // Bbl_ManTestTruth( "100 1\n010 1\n001 1\n111 1\n", 3 ); // Bbl_ManTestTruth( "-11 0\n1-1 0\n11- 0\n", 3 ); // Bbl_ManTestTruth( "--- 1\n", 3 ); } //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// ABC_NAMESPACE_IMPL_END