From f0cc98cfcd5a2a15e4b7d3deeee700ff77433536 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Thu, 24 Apr 2014 20:05:47 -0700 Subject: Experiments with permutations. --- src/misc/extra/extraUtilCube.c | 141 +++++++++++++++++++++++++++-------------- 1 file changed, 92 insertions(+), 49 deletions(-) (limited to 'src/misc/extra/extraUtilCube.c') diff --git a/src/misc/extra/extraUtilCube.c b/src/misc/extra/extraUtilCube.c index 98ef0780..c053e23a 100644 --- a/src/misc/extra/extraUtilCube.c +++ b/src/misc/extra/extraUtilCube.c @@ -57,8 +57,8 @@ void Abc_EnumerateCubeStates2() { {2,14}, {2,24}, {2,12}, {3,13}, {3,23}, {3,10}, {1,15}, {1,22}, {1,11} }, { {1,10}, {1, 7}, {1, 4}, {3,12}, {3, 9}, {3, 6}, {2,11}, {2, 8}, {2, 5} } }; - Vec_Int_t * vData = Vec_IntStart( 6 * (1 << 22) ); - Hsh_IntMan_t * vHash = Hsh_IntManStart( vData, 6, 1 << 22 ); + Vec_Int_t * vData = Vec_IntStart( 6 * (1 << 22) ); // 96 MB + Hsh_IntMan_t * vHash = Hsh_IntManStart( vData, 6, 1 << 22 ); // 32 MB int i, k, v, RetValue, Beg, End, Counter = 0; char pStart[24], pFirst[9][24]; abctime clk = Abc_Clock(); @@ -160,70 +160,113 @@ Iter 12 -> 3674160 Time = 70.48 sec ***********************************************************************/ static inline int Abc_DataHasBit( word * p, word i ) { return (p[(i)>>6] & (1<<((i) & 63))) > 0; } -static inline void Abc_DataSetBit( word * p, word i ) { p[(i)>>6] |= (1<<((i) & 63)); } static inline void Abc_DataXorBit( word * p, word i ) { p[(i)>>6] ^= (1<<((i) & 63)); } static inline int Abc_DataGetCube( word w, int i ) { return (w >> (5*i)) & 31; } static inline word Abc_DataXorCube( word w, int i, int c ) { return w ^ (((word)c) << (5*i)); } +static inline word Abc_CubeGenerateSign( char * pState ) +{ + static int Var2Cor[24] = { 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, -1, -1, -1, 6, 6, 6 }; + static int Var2Per[24] = { 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, -1, -1, -1, 0, 1, 2 }; + word Res = 0; + Res = Abc_DataXorCube( Res, 0, (Var2Cor[(int)pState[ 0]] << 2) | Var2Per[(int)pState[ 0]] ); + Res = Abc_DataXorCube( Res, 1, (Var2Cor[(int)pState[ 3]] << 2) | Var2Per[(int)pState[ 3]] ); + Res = Abc_DataXorCube( Res, 2, (Var2Cor[(int)pState[ 6]] << 2) | Var2Per[(int)pState[ 6]] ); + Res = Abc_DataXorCube( Res, 3, (Var2Cor[(int)pState[ 9]] << 2) | Var2Per[(int)pState[ 9]] ); + Res = Abc_DataXorCube( Res, 4, (Var2Cor[(int)pState[12]] << 2) | Var2Per[(int)pState[12]] ); + Res = Abc_DataXorCube( Res, 5, (Var2Cor[(int)pState[15]] << 2) | Var2Per[(int)pState[15]] ); + Res = Abc_DataXorCube( Res, 6, (Var2Cor[(int)pState[21]] << 2) | Var2Per[(int)pState[21]] ); + return Res; +} + +/**Function************************************************************* + + Synopsis [] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ void Abc_EnumerateCubeStates() { - extern word Aig_ManRandom64( int fReset ); - - int pXYZ[3][4][3] = { - { {0, 4, 0}, {4, 6, 0}, {6, 3, 1}, {3, 0,-1} }, - { {1, 3, 1}, {3, 6, 0}, {6, 5, 0}, {5, 1,-1} }, - { {2, 5, 0}, {5, 6,-1}, {6, 4, 1}, {4, 2, 0} } - }; - int pPerms[9][4][3] = {0}; - int i, k, v, u, Beg, End, Cube0, Cube1; - Vec_Wrd_t * vStates = Vec_WrdAlloc( 1 << 22 ); // 16 MB - word * pHash = ABC_CALLOC( word, 1 << 29 ); // 4 GB - word New, Init = 0; - - // estimate - int Counter = 0; + int pXYZ[3][9][2] = { + { {3, 5}, {3,17}, {3,15}, {1, 6}, {1,16}, {1,14}, {2, 4}, {2,18}, {2,13} }, + { {2,14}, {2,24}, {2,12}, {3,13}, {3,23}, {3,10}, {1,15}, {1,22}, {1,11} }, + { {1,10}, {1, 7}, {1, 4}, {3,12}, {3, 9}, {3, 6}, {2,11}, {2, 8}, {2, 5} } }; + + Vec_Int_t * vData = Vec_IntStart( 6 * (1 << 22) ); // 96 MB + word State, * pHash = ABC_CALLOC( word, 1 << 29 ); // 4 GB + int i, k, v, Beg, End, Counter = 0; + char * pPrev, * pState, pStart[24], pFirst[9][24]; abctime clk = Abc_Clock(); - Aig_ManRandom64( 1 ); - for ( i = 0; i < 3674160; i++ ) + printf( "Enumerating states of 2x2x2 cube.\n" ); + // init state + for ( v = 0; v < 24; v++ ) + pStart[v] = v; + Abc_StatePush( vData, pStart, Counter ); + Abc_DataXorBit( pHash, Abc_CubeGenerateSign(pStart) ); + Counter++; + // first nine states + for ( i = 0; i < 3; i++ ) + { + memcpy( pFirst[i], pStart, 24 ); for ( v = 0; v < 9; v++ ) - { - Init = Aig_ManRandom64( 0 ) & ABC_CONST(0x7FFFFFFFF); - if ( Abc_DataHasBit(pHash, Init) ) - Counter++; - else - Abc_DataSetBit(pHash, Init); - } - printf( "Counter = %d ", Counter ); - Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); + ABC_SWAP( char, pFirst[i][pXYZ[i][v][0]-1], pFirst[i][pXYZ[i][v][1]-1] ); + Abc_StatePush( vData, pFirst[i], Counter ); + Abc_DataXorBit( pHash, Abc_CubeGenerateSign(pFirst[i]) ); + Counter++; + //Abc_StatePrint( pFirst[i] ); - if ( Counter == -1 ) - { - for ( i = 0; i < 7; i++ ) - Init = Abc_DataXorCube( Init, i, i << 2 ); - Vec_WrdPush( vStates, Init ); - Abc_DataSetBit( pHash, Init ); - Beg = 0; End = 1; - for ( i = 1; i <= 100; i++ ) + memcpy( pFirst[3+i], pFirst[i], 24 ); + for ( v = 0; v < 9; v++ ) + ABC_SWAP( char, pFirst[3+i][pXYZ[i][v][0]-1], pFirst[3+i][pXYZ[i][v][1]-1] ); + Abc_StatePush( vData, pFirst[3+i], Counter ); + Abc_DataXorBit( pHash, Abc_CubeGenerateSign(pFirst[3+i]) ); + Counter++; + //Abc_StatePrint( pFirst[3+i] ); + + memcpy( pFirst[6+i], pFirst[3+i], 24 ); + for ( v = 0; v < 9; v++ ) + ABC_SWAP( char, pFirst[6+i][pXYZ[i][v][0]-1], pFirst[6+i][pXYZ[i][v][1]-1] ); + Abc_StatePush( vData, pFirst[6+i], Counter ); + Abc_DataXorBit( pHash, Abc_CubeGenerateSign(pFirst[6+i]) ); + Counter++; + //Abc_StatePrint( pFirst[6+i] ); + } + printf( "Iter %2d -> %8d ", 0, 1 ); + Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); + printf( "Iter %2d -> %8d ", 1, Counter ); + Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); + Beg = 1; End = 10; + for ( i = 2; i <= 100; i++ ) { if ( Beg == End ) break; - Vec_WrdForEachEntryStartStop( vStates, Init, k, Beg, End ) + for ( k = Beg; k < End; k++ ) + { + pPrev = (char *)Vec_IntEntryP(vData, 6*k); for ( v = 0; v < 9; v++ ) { - New = Init; - for ( u = 0; u < 4; u++ ) + pState = (char *)Vec_IntEntryP(vData, 6*Counter); + Abc_StatePerm( pPrev, pFirst[v], pState ); + State = Abc_CubeGenerateSign( pState ); + if ( !Abc_DataHasBit(pHash, State) ) + Abc_DataXorBit(pHash, State), Counter++; + if ( Counter == (1<<22) ) { - Cube0 = Abc_DataGetCube( Init, pPerms[v][u][0] ); - Cube1 = Abc_DataGetCube( Init, pPerms[v][u][1] ); - New = Abc_DataXorCube( New, pPerms[v][u][1], Cube0 - pPerms[v][u][2] ); - New = Abc_DataXorCube( New, pPerms[v][u][0], Cube1 + pPerms[v][u][2] ); + printf( "Did not converge. " ); + Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); + return; } - if ( !Abc_DataHasBit( pHash, New ) ) - Vec_WrdPush( vStates, New ); } + } + Beg = End; End = Counter; + printf( "Iter %2d -> %8d ", i, Counter ); + Abc_PrintTime( 1, "Time", Abc_Clock() - clk ); } - } - - Vec_WrdFree( vStates ); + Vec_IntFree( vData ); ABC_FREE( pHash ); } -- cgit v1.2.3