From efdd26f86d3dbbde1626fe6a84304bc700b97479 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Mon, 23 Mar 2015 18:40:38 +0700 Subject: Scalable SOP manipulation package. --- src/base/pla/plaHash.c | 144 ++++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 136 insertions(+), 8 deletions(-) (limited to 'src/base/pla/plaHash.c') diff --git a/src/base/pla/plaHash.c b/src/base/pla/plaHash.c index d05bd9c9..b51ba4c1 100644 --- a/src/base/pla/plaHash.c +++ b/src/base/pla/plaHash.c @@ -63,7 +63,7 @@ static unsigned s_PlaHashValues[PLA_HASH_VALUE_NUM] = 0xd0fa29f1,0x804cac5e,0x2c226798,0x462f624c,0xad05b377,0x22924fcd,0xfbea205c,0x1b47586d }; -static inline int Pla_HashValue( int i ) { assert( i >= 0 && i < PLA_HASH_VALUE_NUM ); return s_PlaHashValues[i] & 0xFFFFFF; } +static inline int Pla_HashValue( int i ) { assert( i >= 0 && i < PLA_HASH_VALUE_NUM ); return s_PlaHashValues[i] & 0x3FFFFFF; } #define PLA_LIT_UNUSED 0xFFFF @@ -107,7 +107,7 @@ static inline Tab_Obj_t * Tab_ManEntry( Tab_Man_t * p, int i ) { return i ? p static inline Tab_Man_t * Tab_ManAlloc( int LogSize, Pla_Man_t * pMan ) { Tab_Man_t * p = ABC_CALLOC( Tab_Man_t, 1 ); - assert( LogSize >= 4 && LogSize <= 24 ); + assert( LogSize >= 4 && LogSize <= 26 ); p->SizeMask = (1 << LogSize) - 1; p->pBins = ABC_CALLOC( Tab_Obj_t, p->SizeMask + 1 ); p->nBins = 1; @@ -119,11 +119,12 @@ static inline void Tab_ManFree( Tab_Man_t * p ) ABC_FREE( p->pBins ); ABC_FREE( p ); } -static inline void Tab_ManHashInsert( Tab_Man_t * p, int Value, int iCube ) +static inline void Tab_ManHashInsert( Tab_Man_t * p, int Value, int iCube, int iVar ) { Tab_Obj_t * pBin = Tab_ManBin( p, Value ); Tab_Obj_t * pCell = p->pBins + p->nBins; pCell->Cube = iCube; + pCell->VarA = iVar; pCell->Next = pBin->Table; pBin->Table = p->nBins++; } @@ -131,10 +132,17 @@ static inline int Tab_ManHashLookup( Tab_Man_t * p, int Value, Vec_Int_t * vCube { Tab_Obj_t * pEnt, * pBin = Tab_ManBin( p, Value ); for ( pEnt = Tab_ManEntry(p, pBin->Table); pEnt; pEnt = Tab_ManEntry(p, pEnt->Next) ) - if ( Vec_IntEqual( Vec_WecEntry(&p->pMan->vLits, pEnt->Cube), vCube ) ) + if ( Vec_IntEqual( Vec_WecEntry(&p->pMan->vCubeLits, pEnt->Cube), vCube ) ) return 1; return 0; } +static inline void Tab_ManHashCollect( Tab_Man_t * p, int iBin, Vec_Int_t * vEntries ) +{ + Tab_Obj_t * pEnt, * pBin = Tab_ManBin( p, iBin ); + Vec_IntClear( vEntries ); + for ( pEnt = Tab_ManEntry(p, pBin->Table); pEnt; pEnt = Tab_ManEntry(p, pEnt->Next) ) + Vec_IntPushTwo( vEntries, pEnt->Cube, pEnt->VarA ); +} /**Function************************************************************* @@ -160,11 +168,11 @@ void Pla_ManHashCubes( Pla_Man_t * p, Tab_Man_t * pTab ) Vec_Int_t * vCube; int i, Value; Vec_IntClear( &p->vHashes ); Vec_IntGrow( &p->vHashes, Pla_ManCubeNum(p) ); - Vec_WecForEachLevel( &p->vLits, vCube, i ) + Vec_WecForEachLevel( &p->vCubeLits, vCube, i ) { Value = Pla_CubeHashValue(vCube); Vec_IntPush( &p->vHashes, Value ); - Tab_ManHashInsert( pTab, Value, i ); + Tab_ManHashInsert( pTab, Value, i, PLA_LIT_UNUSED ); } } int Pla_ManHashDistance1( Pla_Man_t * p ) @@ -174,11 +182,11 @@ int Pla_ManHashDistance1( Pla_Man_t * p ) Vec_Int_t * vCubeCopy = Vec_IntAlloc( p->nIns ); int nBits = Abc_Base2Log( Pla_ManCubeNum(p) ) + 2; int i, k, Lit, Value, ValueCopy, Count = 0; - assert( nBits <= 24 ); + assert( nBits <= 26 ); pTab = Tab_ManAlloc( nBits, p ); Pla_ManConvertFromBits( p ); Pla_ManHashCubes( p, pTab ); - Vec_WecForEachLevel( &p->vLits, vCube, i ) + Vec_WecForEachLevel( &p->vCubeLits, vCube, i ) { Vec_IntClear( vCubeCopy ); Vec_IntAppend( vCubeCopy, vCube ); @@ -210,6 +218,126 @@ int Pla_ManHashDist1NumTest( Pla_Man_t * p ) return 1; } +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Pla_PrintCube( Vec_Int_t * vLits, int nVars, int iVar ) +{ + int v, Lit; + Vec_Str_t * vStr = Vec_StrStart( nVars + 1 ); + Vec_StrFill( vStr, nVars, '-' ); + Vec_IntForEachEntry( vLits, Lit, v ) + Vec_StrWriteEntry( vStr, Abc_Lit2Var(Lit), (char)(Abc_LitIsCompl(Lit) ? '0' : '1') ); + fprintf( stdout, "%s %d\n", Vec_StrArray(vStr), iVar ); + Vec_StrFree( vStr ); +} +void Pla_ManHashCubes2( Pla_Man_t * p, Tab_Man_t * pTab ) +{ + Vec_Int_t * vCube; + int i, v, Lit, Value; + Vec_WecForEachLevel( &p->vCubeLits, vCube, i ) + { + Value = Pla_CubeHashValue(vCube); + Vec_IntForEachEntry( vCube, Lit, v ) + { + Value -= Pla_HashValue(Lit); + Tab_ManHashInsert( pTab, Value, i, v ); + Value += Pla_HashValue(Lit); + } + } +} +void Vec_IntCopySkip( Vec_Int_t * vCube, int iVar, Vec_Int_t * vRes ) +{ + int i; + Vec_IntClear( vRes ); + for ( i = 0; i < Vec_IntSize(vCube); i++ ) + if ( i != iVar ) + Vec_IntPush( vRes, Vec_IntEntry(vCube, i) ); +} +Vec_Int_t * Pla_ManComputeDistance1Int( Pla_Man_t * p ) +{ + Tab_Man_t * pTab; + Vec_Int_t * vCube1, * vCube2; + Vec_Int_t * vTemp1 = Vec_IntAlloc( 100 ); + Vec_Int_t * vTemp2 = Vec_IntAlloc( 100 ); + Vec_Int_t * vPairs = Vec_IntAlloc( 1000 ); + Vec_Int_t * vCounts = Vec_IntStart( Vec_WecSize(&p->vCubeLits) ); + Vec_Int_t * vEntries = Vec_IntAlloc( p->nIns ); + int nBits = Abc_Base2Log( Vec_WecSizeSize(&p->vCubeLits) ) + 2; + int v, i, k, Count = 0; + int iCube1, iCube2, iVar1, iVar2; + assert( nBits <= 26 ); + pTab = Tab_ManAlloc( nBits, p ); + //Pla_ManConvertFromBits( p ); + Pla_ManHashCubes2( p, pTab ); + // iterate through the hash bins + for ( v = 0; v <= pTab->SizeMask; v++ ) + { + Tab_ManHashCollect( pTab, v, vEntries ); + for ( i = 0; i < Vec_IntSize(vEntries)/2; i++ ) + for ( k = i+1; k < Vec_IntSize(vEntries)/2; k++ ) + { + iCube1 = Vec_IntEntry(vEntries, 2*i); + iCube2 = Vec_IntEntry(vEntries, 2*k); + iVar1 = Vec_IntEntry(vEntries, 2*i+1); + iVar2 = Vec_IntEntry(vEntries, 2*k+1); + + vCube1 = Vec_WecEntry(&p->vCubeLits, iCube1); + vCube2 = Vec_WecEntry(&p->vCubeLits, iCube2); +/* + Pla_PrintCube( vCube1, p->nIns, iVar1 ); + Pla_PrintCube( vCube2, p->nIns, iVar2 ); + printf( "\n" ); +*/ + if ( Vec_IntSize(vCube1) != Vec_IntSize(vCube2) ) + continue; + Vec_IntCopySkip( vCube1, iVar1, vTemp1 ); + Vec_IntCopySkip( vCube2, iVar2, vTemp2 ); + if ( !Vec_IntEqual( vTemp1, vTemp2 ) ) + continue; + + printf( "%d %d ", iCube1, iCube2 ); + + Vec_IntPushTwo( vPairs, iCube1, iVar1 ); + Vec_IntPushTwo( vPairs, iCube2, iVar2 ); + + Vec_IntAddToEntry( vCounts, iCube1, 1 ); + Vec_IntAddToEntry( vCounts, iCube2, 1 ); + } + } + Vec_IntPrint( vCounts ); + + Vec_IntFree( vCounts ); + Vec_IntFree( vTemp1 ); + Vec_IntFree( vTemp2 ); + Vec_IntFree( vEntries ); + Tab_ManFree( pTab ); + return vPairs; +} +Vec_Int_t * Pla_ManComputeDistance1( Pla_Man_t * p ) +{ + abctime clk = Abc_Clock(); + Vec_Int_t * vPairs = Pla_ManComputeDistance1Int( p ); + printf( "Found %d pairs among %d cubes using cube hashing. ", Vec_IntSize(vPairs)/4, Pla_ManCubeNum(p) ); + Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); + return vPairs; +} +void Pla_ManComputeDist1Test( Pla_Man_t * p ) +{ + Vec_Int_t * vPairs; + Pla_ManConvertFromBits( p ); + vPairs = Pla_ManComputeDistance1( p ); + Vec_IntFree( vPairs ); +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// -- cgit v1.2.3