From 746707b383e97800b9f0f60bb0a43fd8990564dc Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Fri, 20 Feb 2015 08:45:13 -0800 Subject: Experiments with cube hashing. --- src/misc/extra/extraUtilPrime.c | 293 +++++++++++++++++++++++++++++++++++++++- 1 file changed, 292 insertions(+), 1 deletion(-) (limited to 'src/misc/extra') diff --git a/src/misc/extra/extraUtilPrime.c b/src/misc/extra/extraUtilPrime.c index 3b969401..862ac562 100644 --- a/src/misc/extra/extraUtilPrime.c +++ b/src/misc/extra/extraUtilPrime.c @@ -82,9 +82,12 @@ void Abc_GenCountHits1( Vec_Bit_t * vMap, Vec_Int_t * vPrimes, int nVars ) { for ( k = 0; k < nVars; k++ ) if ( !Vec_BitEntry(vMap, Prime ^ (1< cube + lit + lit) + int Degree; // degree of 2 larger than log2(nCubes) + int Mask; // table size (2^Degree) + int nEnts; // number of entries +}; +struct Tab_Ent_t_ +{ + int Table; + int Cube; + unsigned VarA : 16; + unsigned VarB : 16; + int Next; +}; + +static inline int * Tab_ManCube( Tab_Man_t * p, int i ) { return p->pCubes + i * (p->nVars + 1); } +static inline int Tab_ManValue( Tab_Man_t * p, int a ) +{ + return (a + 53) * s_1kPrimes[a]; +} +static inline int Tab_ManFinal( Tab_Man_t * p, int a ) +{ +// return (a ^ (a >> p->Degree)) & p->Mask; + return a & p->Mask; +} +static inline int Tab_ManHashValue( Tab_Man_t * p, int * pCube ) +{ + unsigned Value = 0; int i; + for ( i = 1; i <= pCube[0]; i++ ) + Value += Tab_ManValue( p, pCube[i] ); + return Value; +} +static inline void Tab_ManHashAdd( Tab_Man_t * p, int Value, int Cube, int VarA, int VarB ) +{ + Tab_Ent_t * pCell = p->pTable + p->nEnts; + Tab_Ent_t * pBin = p->pTable + Value; + if ( pBin->Table ) + pCell->Next = pBin->Table; + pBin->Table = p->nEnts++; + pCell->Cube = Cube; + pCell->VarA = VarA; + pCell->VarB = VarB; +} +static inline void Tab_ManPrintCube( Tab_Man_t * p, int c, int Var ) +{ + int i, * pCube = Tab_ManCube( p, c ); + for ( i = 1; i <= pCube[0]; i++ ) + if ( i == Var + 1 ) + printf( "-" ); + else + printf( "%d", !Abc_LitIsCompl(pCube[i]) ); +} +static inline void Tab_ManPrintEntry( Tab_Man_t * p, int e ) +{ + printf( "Entry %4d : ", e ); + printf( "%3d ", p->pTable[e].Cube ); + Tab_ManPrintCube( p, p->pTable[e].Cube, p->pTable[e].VarA ); + printf( " " ); + if ( p->pTable[e].VarA != 0xFFFF ) + printf( "%2d ", p->pTable[e].VarA ); + else + printf( " " ); + if ( p->pTable[e].VarB != 0xFFFF ) + printf( "%2d ", p->pTable[e].VarB ); + else + printf( " " ); + printf( "\n" ); +} + +/**Function************************************************************* + + Synopsis [Table decomposition.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +Tab_Man_t * Tab_ManAlloc( int nVars, int nCubes ) +{ + Tab_Man_t * p = ABC_CALLOC( Tab_Man_t, 1 ); + p->nVars = nVars; + p->nCubes = nCubes; + p->Degree = Abc_Base2Log((p->nVars + 1) * p->nCubes + 1) + 3; + p->Mask = (1 << p->Degree) - 1; + p->nEnts = 1; + p->pCubes = ABC_ALLOC( int, p->nCubes * (p->nVars + 1) ); + p->pValues = ABC_ALLOC( int, p->nCubes ); + p->pTable = ABC_CALLOC( Tab_Ent_t, (p->Mask + 1) ); + printf( "Allocated %.2f MB for table with %d entries (degree %d) (expected %d).\n", 16.0 * (p->Mask + 1) / (1 << 20), p->Mask + 1, p->Degree, p->nCubes * (p->nVars + 1) ); + return p; +} +void Tab_ManFree( Tab_Man_t * p ) +{ + ABC_FREE( p->pCubes ); + ABC_FREE( p->pValues ); + ABC_FREE( p->pTable ); + ABC_FREE( p ); +} +void Tab_ManStart( Tab_Man_t * p, Vec_Int_t * vCubes ) +{ + int Count0 = 0, Count1 = 0, Count2 = 0, Count3 = 0; + int * pCube, Cube, c, v; + Vec_IntForEachEntry( vCubes, Cube, c ) + { + pCube = Tab_ManCube( p, c ); + pCube[0] = p->nVars; + for ( v = 0; v < p->nVars; v++ ) + pCube[v+1] = Abc_Var2Lit( v, !((Cube >> v) & 1) ); + p->pValues[c] = Tab_ManHashValue( p, pCube ); + Tab_ManHashAdd( p, Tab_ManFinal(p, p->pValues[c]), c, TAB_UNUSED, TAB_UNUSED ); + // add distance-1 + for ( v = 0; v < p->nVars; v++ ) + Tab_ManHashAdd( p, Tab_ManFinal(p, p->pValues[c] - Tab_ManValue(p, pCube[v+1])), c, v, TAB_UNUSED ); +//printf( "%3d : %3d ", c, Cube ); +//Tab_ManPrintCube( p, c, TAB_UNUSED ); +//printf( "\n" ); + } + // count empty cell, one-entry cells, and multi-entry cells + for ( v = 0; v <= p->Mask; v++ ) + { +/* + int i, iStart = p->pTable[v].Table; + for ( i = 0; iStart; i++, iStart = p->pTable[iStart].Next ); + printf( "%d ", i ); +*/ +/* + if ( v < 100 ) + { + int i, iStart = p->pTable[v].Table; + if ( iStart ) + printf( "\nBin %d\n", v ); + for ( i = 0; iStart; i++, iStart = p->pTable[iStart].Next ) + Tab_ManPrintEntry( p, iStart ); + } +*/ + if ( p->pTable[v].Table == 0 ) + Count0++; + else if ( p->pTable[p->pTable[v].Table].Next == 0 ) + Count1++; + else if ( p->pTable[p->pTable[p->pTable[v].Table].Next].Next == 0 ) + Count2++; + else + Count3++; + } + printf( "0 = %d. 1 = %d. 2 = %d. 3+ = %d.\n", Count0, Count1, Count2, Count3 ); +} + + +/**Function************************************************************* + + Synopsis [Table decomposition.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Tab_DecomposeTest() +{ + int nVars = 20;// no more than 13 + abctime clk = Abc_Clock(); + Vec_Int_t * vPrimes = Abc_GenPrimes( nVars ); + Tab_Man_t * p = Tab_ManAlloc( nVars, Vec_IntSize(vPrimes) ); + Tab_ManStart( p, vPrimes ); + printf( "Added %d entries.\n", p->nEnts ); + Tab_ManFree( p ); + Vec_IntFree( vPrimes ); + Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); +} + + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// -- cgit v1.2.3