| /**CFile**************************************************************** | |
| FileName [ Fxch.h ] | |
| PackageName [ Fast eXtract with Cube Hashing (FXCH) ] | |
| Synopsis [ External declarations of fast extract with cube hashing. ] | |
| Author [ Bruno Schmitt - boschmitt at inf.ufrgs.br ] | |
| Affiliation [ UFRGS ] | |
| Date [ Ver. 1.0. Started - March 6, 2016. ] | |
| Revision [] | |
| ***********************************************************************/ | |
| #ifndef ABC__opt__fxch__fxch_h | |
| #define ABC__opt__fxch__fxch_h | |
| #include "base/abc/abc.h" | |
| #include "misc/vec/vecHsh.h" | |
| #include "misc/vec/vecQue.h" | |
| #include "misc/vec/vecVec.h" | |
| #include "misc/vec/vecWec.h" | |
| ABC_NAMESPACE_HEADER_START | |
| typedef unsigned char uint8_t; | |
| typedef unsigned int uint32_t; | |
| //////////////////////////////////////////////////////////////////////// | |
| /// TYPEDEF DECLARATIONS /// | |
| //////////////////////////////////////////////////////////////////////// | |
| typedef struct Fxch_Man_t_ Fxch_Man_t; | |
| typedef struct Fxch_SubCube_t_ Fxch_SubCube_t; | |
| typedef struct Fxch_SCHashTable_t_ Fxch_SCHashTable_t; | |
| typedef struct Fxch_SCHashTable_Entry_t_ Fxch_SCHashTable_Entry_t; | |
| //////////////////////////////////////////////////////////////////////// | |
| /// STRUCTURES DEFINITIONS /// | |
| //////////////////////////////////////////////////////////////////////// | |
| /* Sub-Cube Structure | |
| * | |
| * In the context of this program, a sub-cube is a cube derived from | |
| * another cube by removing one or two literals. Since a cube is represented | |
| * as a vector of literals, one might think that a sub-cube would also be | |
| * represented in the same way. However, in order to same memory, we only | |
| * store a sub-cube identifier and the data necessary to generate the sub-cube: | |
| * - The index number of the orignal cube in the cover. (iCube) | |
| * - Identifiers of which literal(s) was(were) removed. (iLit0, iLit1) | |
| * | |
| * The sub-cube identifier is generated by adding the unique identifiers of | |
| * its literals. | |
| * | |
| */ | |
| struct Fxch_SubCube_t_ | |
| { | |
| uint32_t Id, | |
| iCube; | |
| uint32_t iLit0 : 16, | |
| iLit1 : 16; | |
| }; | |
| /* Sub-cube Hash Table | |
| */ | |
| struct Fxch_SCHashTable_Entry_t_ | |
| { | |
| Fxch_SubCube_t* vSCData; | |
| uint32_t Size : 16, | |
| Cap : 16; | |
| }; | |
| struct Fxch_SCHashTable_t_ | |
| { | |
| Fxch_Man_t* pFxchMan; | |
| /* Internal data */ | |
| Fxch_SCHashTable_Entry_t* pBins; | |
| unsigned int nEntries, | |
| SizeMask; | |
| /* Temporary data */ | |
| Vec_Int_t vSubCube0; | |
| Vec_Int_t vSubCube1; | |
| }; | |
| struct Fxch_Man_t_ | |
| { | |
| /* user's data */ | |
| Vec_Wec_t* vCubes; | |
| int nCubesInit; | |
| int LitCountMax; | |
| /* internal data */ | |
| Fxch_SCHashTable_t* pSCHashTable; | |
| Vec_Wec_t* vLits; /* lit -> cube */ | |
| Vec_Int_t* vLitCount; /* literal counts (currently not used) */ | |
| Vec_Int_t* vLitHashKeys; /* Literal hash keys used to generate subcube hash */ | |
| Hsh_VecMan_t* pDivHash; | |
| Vec_Flt_t* vDivWeights; /* divisor weights */ | |
| Vec_Que_t* vDivPrio; /* priority queue for divisors by weight */ | |
| Vec_Wec_t* vDivCubePairs; /* cube pairs for each div */ | |
| Vec_Int_t* vLevels; /* variable levels */ | |
| // Cube Grouping | |
| Vec_Int_t* vTranslation; | |
| Vec_Int_t* vOutputID; | |
| int* pTempOutputID; | |
| int nSizeOutputID; | |
| // temporary data to update the data-structure when a divisor is extracted | |
| Vec_Int_t* vCubesS; /* cubes for the given single cube divisor */ | |
| Vec_Int_t* vPairs; /* cube pairs for the given double cube divisor */ | |
| Vec_Int_t* vCubeFree; // cube-free divisor | |
| Vec_Int_t* vDiv; // selected divisor | |
| Vec_Int_t* vCubesToRemove; | |
| Vec_Int_t* vCubesToUpdate; | |
| Vec_Int_t* vSCC; | |
| /* Statistics */ | |
| abctime timeInit; /* Initialization time */ | |
| abctime timeExt; /* Extraction time */ | |
| int nVars; // original problem variables | |
| int nLits; // the number of SOP literals | |
| int nPairsS; // number of lit pairs | |
| int nPairsD; // number of cube pairs | |
| int nExtDivs; /* Number of extracted divisor */ | |
| }; | |
| //////////////////////////////////////////////////////////////////////// | |
| /// FUNCTION DEFINITIONS /// | |
| //////////////////////////////////////////////////////////////////////// | |
| /* The following functions are from abcFx.c | |
| * They are use in order to retrive SOP information for fast_extract | |
| * Since I want an implementation that change only the core part of | |
| * the algorithm I'm using this */ | |
| extern Vec_Wec_t* Abc_NtkFxRetrieve( Abc_Ntk_t* pNtk ); | |
| extern void Abc_NtkFxInsert( Abc_Ntk_t* pNtk, Vec_Wec_t* vCubes ); | |
| extern int Abc_NtkFxCheck( Abc_Ntk_t* pNtk ); | |
| static inline int Fxch_CountOnes( unsigned num ) | |
| { | |
| num = ( num & 0x55555555 ) + ( ( num >> 1) & 0x55555555 ); | |
| num = ( num & 0x33333333 ) + ( ( num >> 2) & 0x33333333 ); | |
| num = ( num & 0x0F0F0F0F ) + ( ( num >> 4) & 0x0F0F0F0F ); | |
| num = ( num & 0x00FF00FF ) + ( ( num >> 8) & 0x00FF00FF ); | |
| return ( num & 0x0000FFFF ) + ( num >> 16 ); | |
| } | |
| /*===== Fxch.c =======================================================*/ | |
| int Abc_NtkFxchPerform( Abc_Ntk_t* pNtk, int nMaxDivExt, int fVerbose, int fVeryVerbose ); | |
| int Fxch_FastExtract( Vec_Wec_t* vCubes, int ObjIdMax, int nMaxDivExt, int fVerbose, int fVeryVerbose ); | |
| /*===== FxchDiv.c ====================================================================================================*/ | |
| int Fxch_DivCreate( Fxch_Man_t* pFxchMan, Fxch_SubCube_t* pSubCube0, Fxch_SubCube_t* pSubCube1 ); | |
| int Fxch_DivAdd( Fxch_Man_t* pFxchMan, int fUpdate, int fSingleCube, int fBase ); | |
| int Fxch_DivRemove( Fxch_Man_t* pFxchMan, int fUpdate, int fSingleCube, int fBase ); | |
| void Fxch_DivSepareteCubes( Vec_Int_t* vDiv, Vec_Int_t* vCube0, Vec_Int_t* vCube1 ); | |
| int Fxch_DivRemoveLits( Vec_Int_t* vCube0, Vec_Int_t* vCube1, Vec_Int_t* vDiv, int *fCompl ); | |
| void Fxch_DivPrint( Fxch_Man_t* pFxchMan, int iDiv ); | |
| int Fxch_DivIsNotConstant1( Vec_Int_t* vDiv ); | |
| /*===== FxchMan.c ====================================================================================================*/ | |
| Fxch_Man_t* Fxch_ManAlloc( Vec_Wec_t* vCubes ); | |
| void Fxch_ManFree( Fxch_Man_t* pFxchMan ); | |
| void Fxch_ManMapLiteralsIntoCubes( Fxch_Man_t* pFxchMan, int nVars ); | |
| void Fxch_ManGenerateLitHashKeys( Fxch_Man_t* pFxchMan ); | |
| void Fxch_ManSCHashTablesInit( Fxch_Man_t* pFxchMan ); | |
| void Fxch_ManSCHashTablesFree( Fxch_Man_t* pFxchMan ); | |
| void Fxch_ManDivCreate( Fxch_Man_t* pFxchMan ); | |
| int Fxch_ManComputeLevelDiv( Fxch_Man_t* pFxchMan, Vec_Int_t* vCubeFree ); | |
| int Fxch_ManComputeLevelCube( Fxch_Man_t* pFxchMan, Vec_Int_t* vCube ); | |
| void Fxch_ManComputeLevel( Fxch_Man_t* pFxchMan ); | |
| void Fxch_ManUpdate( Fxch_Man_t* pFxchMan, int iDiv ); | |
| void Fxch_ManPrintDivs( Fxch_Man_t* pFxchMan ); | |
| void Fxch_ManPrintStats( Fxch_Man_t* pFxchMan ); | |
| static inline Vec_Int_t* Fxch_ManGetCube( Fxch_Man_t* pFxchMan, | |
| int iCube ) | |
| { | |
| return Vec_WecEntry( pFxchMan->vCubes, iCube ); | |
| } | |
| static inline int Fxch_ManGetLit( Fxch_Man_t* pFxchMan, | |
| int iCube, | |
| int iLit ) | |
| { | |
| return Vec_IntEntry( Vec_WecEntry(pFxchMan->vCubes, iCube), iLit ); | |
| } | |
| /*===== FxchSCHashTable.c ============================================*/ | |
| Fxch_SCHashTable_t* Fxch_SCHashTableCreate( Fxch_Man_t* pFxchMan, int nEntries ); | |
| void Fxch_SCHashTableDelete( Fxch_SCHashTable_t* ); | |
| int Fxch_SCHashTableInsert( Fxch_SCHashTable_t* pSCHashTable, | |
| Vec_Wec_t* vCubes, | |
| uint32_t SubCubeID, | |
| uint32_t iCube, | |
| uint32_t iLit0, | |
| uint32_t iLit1, | |
| char fUpdate ); | |
| int Fxch_SCHashTableRemove( Fxch_SCHashTable_t* pSCHashTable, | |
| Vec_Wec_t* vCubes, | |
| uint32_t SubCubeID, | |
| uint32_t iCube, | |
| uint32_t iLit0, | |
| uint32_t iLit1, | |
| char fUpdate ); | |
| unsigned int Fxch_SCHashTableMemory( Fxch_SCHashTable_t* ); | |
| void Fxch_SCHashTablePrint( Fxch_SCHashTable_t* ); | |
| ABC_NAMESPACE_HEADER_END | |
| #endif | |
| //////////////////////////////////////////////////////////////////////// | |
| /// END OF FILE /// | |
| //////////////////////////////////////////////////////////////////////// | |