From d0af09a20977a2afd1d8f056bf22dc7428d246e3 Mon Sep 17 00:00:00 2001 From: Alan Mishchenko Date: Sat, 26 Sep 2015 14:55:07 -0700 Subject: New command &rexwalk. --- src/aig/gia/giaRex.c | 197 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 197 insertions(+) (limited to 'src/aig/gia/giaRex.c') diff --git a/src/aig/gia/giaRex.c b/src/aig/gia/giaRex.c index 5f50f520..d228642f 100644 --- a/src/aig/gia/giaRex.c +++ b/src/aig/gia/giaRex.c @@ -338,6 +338,203 @@ Gia_Man_t * Gia_ManRex2Gia( char * pStrInit, int fOrder, int fVerbose ) return pNew; } + +/**Function************************************************************* + + Synopsis [Transposing 64-bit matrix.] + + Description [Borrowed from "Hacker's Delight", by Henry Warren.] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +void Gia_ManAutomTranspose64( word A[64] ) +{ + int j, k; + word t, m = 0x00000000FFFFFFFF; + for ( j = 32; j != 0; j = j >> 1, m = m ^ (m << j) ) + { + for ( k = 0; k < 64; k = (k + j + 1) & ~j ) + { + t = (A[k] ^ (A[k+j] >> j)) & m; + A[k] = A[k] ^ t; + A[k+j] = A[k+j] ^ (t << j); + } + } +} + +/**Function************************************************************* + + Synopsis [Simulate AIG with the given sequence.] + + Description [] + + SideEffects [] + + SeeAlso [] + +***********************************************************************/ +static inline word Gia_ManAutomSim0( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Wrd_t * vTemp ) +{ + return Gia_ObjFaninC0(pObj) ? ~Vec_WrdEntry(vTemp, Gia_ObjFaninId0p(p, pObj)) : Vec_WrdEntry(vTemp, Gia_ObjFaninId0p(p, pObj)); +} +static inline word Gia_ManAutomSim1( Gia_Man_t * p, Gia_Obj_t * pObj, Vec_Wrd_t * vTemp ) +{ + return Gia_ObjFaninC1(pObj) ? ~Vec_WrdEntry(vTemp, Gia_ObjFaninId1p(p, pObj)) : Vec_WrdEntry(vTemp, Gia_ObjFaninId1p(p, pObj)); +} +word Gia_ManAutomStep( Gia_Man_t * p, word Cur, word * pNext, Vec_Wrd_t * vTemp ) +{ + Gia_Obj_t * pObj; int i; + assert( Gia_ManPoNum(p) == 1 ); + assert( Vec_WrdSize(vTemp) >= Gia_ManObjNum(p) ); + Vec_WrdWriteEntry( vTemp, 0, 0 ); + Gia_ManForEachPi( p, pObj, i ) + Vec_WrdWriteEntry( vTemp, Gia_ObjId(p, pObj), ((word)1) << (63-i) ); + Gia_ManForEachRo( p, pObj, i ) + Vec_WrdWriteEntry( vTemp, Gia_ObjId(p, pObj), ((Cur >> (63-i)) & 1) ? ~((word)0) : 0 ); + Gia_ManForEachAnd( p, pObj, i ) + Vec_WrdWriteEntry( vTemp, i, Gia_ManAutomSim0(p, pObj, vTemp) & Gia_ManAutomSim1(p, pObj, vTemp) ); + Gia_ManForEachRi( p, pObj, i ) + pNext[i] = Gia_ManAutomSim0(p, pObj, vTemp); + for ( ; i < 64; i++ ) + pNext[i] = 0; + // transpose +// for ( i = 0; i < 64; i++ ) +// Extra_PrintBinary( stdout, (unsigned *)&pNext[i], 64 ), Abc_Print( 1, "\n" ); +// printf( "\n" ); + Gia_ManAutomTranspose64( pNext ); +// for ( i = 0; i < 64; i++ ) +// Extra_PrintBinary( stdout, (unsigned *)&pNext[i], 64 ), Abc_Print( 1, "\n" ); +// printf( "\n" ); + // return output values + return Gia_ManAutomSim0(p, Gia_ManPo(p, 0), vTemp); +} +void Gia_ManAutomWalkOne( Gia_Man_t * p, int nSteps, Vec_Wrd_t * vStates, Vec_Int_t * vCounts, Vec_Wrd_t * vTemp, word Init ) +{ + word iState = 0, Output, pNext[64]; + int i, k, kMin, Index, IndexMin; + int Count, CountMin; + for ( i = 0; i < nSteps; i++ ) + { + Output = Gia_ManAutomStep( p, iState, pNext, vTemp ); + // check visited states + kMin = -1; + IndexMin = -1; + CountMin = ABC_INFINITY; + for ( k = 0; k < Gia_ManPiNum(p); k++ ) + { + if ( pNext[k] == Init ) + continue; + Index = Vec_WrdFind( vStates, pNext[k] ); + Count = Index == -1 ? 0 : Vec_IntEntry( vCounts, Index ); + if ( CountMin > Count || (CountMin != ABC_INFINITY && Count && ((float)CountMin / Count) > (float)rand()/RAND_MAX ) ) + { + CountMin = Count; + IndexMin = Index; + kMin = k; + } + if ( CountMin == 0 ) + break; + } + // choose the best state + if ( CountMin == ABC_INFINITY ) + { + for ( k = 0; k < Gia_ManPiNum(p); k++ ) + if ( (Output >> (63-k)) & 1 ) + { + printf( "%c", 'a' + k ); + printf( "!" ); + } + break; + } + assert( CountMin < ABC_INFINITY ); + if ( IndexMin == -1 ) + { + assert( CountMin == 0 ); + IndexMin = Vec_IntSize(vCounts); + Vec_IntPush( vCounts, 0 ); + Vec_WrdPush( vStates, pNext[kMin] ); + } + Vec_IntAddToEntry( vCounts, IndexMin, 1 ); + iState = pNext[kMin]; +//Extra_PrintBinary( stdout, (unsigned *)&iState, 64 ); printf( "\n" ); + // print the transition + printf( "%c", 'a' + kMin ); + if ( (Output >> (63-kMin)) & 1 ) + printf( "!" ); + } + printf( "\n" ); +} +// find flop variables pointed to by negative edges +word Gia_ManAutomInit( Gia_Man_t * p ) +{ + Gia_Obj_t * pObj; + int i, Index; + word Init = 0; + Gia_ManForEachAnd( p, pObj, i ) + { + if ( Gia_ObjFaninC0(pObj) && Gia_ObjIsCi(Gia_ObjFanin0(pObj)) ) + { + Index = Gia_ObjCioId(Gia_ObjFanin0(pObj)) - Gia_ManPiNum(p); + if ( Index >= 0 ) + Init |= ((word)1 << (63-Index)); + } + if ( Gia_ObjFaninC1(pObj) && Gia_ObjIsCi(Gia_ObjFanin1(pObj)) ) + { + Index = Gia_ObjCioId(Gia_ObjFanin1(pObj)) - Gia_ManPiNum(p); + if ( Index >= 0 ) + Init |= ((word)1 << (63-Index)); + } + } + return Init; +} +void Gia_ManAutomWalk( Gia_Man_t * p, int nSteps, int nWalks, int fVerbose ) +{ + Vec_Wrd_t * vTemp, * vStates; + Vec_Int_t * vCounts; int i; word Init; + if ( Gia_ManPoNum(p) != 1 ) + { + printf( "AIG should have one primary output.\n" ); + return; + } + if ( Gia_ManPiNum(p) > 64 ) + { + printf( "Cannot simulate an automaton with more than 64 inputs.\n" ); + return; + } + if ( Gia_ManRegNum(p) > 64 ) + { + printf( "Cannot simulate an automaton with more than 63 states.\n" ); + return; + } + vTemp = Vec_WrdStart( Gia_ManObjNum(p) ); + vStates = Vec_WrdAlloc( 1000 ); + vCounts = Vec_IntAlloc( 1000 ); + Vec_WrdPush( vStates, 0 ); + Vec_IntPush( vCounts, 1 ); + Init = Gia_ManAutomInit( p ); + for ( i = 0; i < nWalks; i++ ) + Gia_ManAutomWalkOne( p, nSteps, vStates, vCounts, vTemp, Init ); + if ( fVerbose ) + { + word State; + Vec_WrdForEachEntry( vStates, State, i ) + { + State ^= Init; + printf( "%3d : ", i ); + Extra_PrintBinary( stdout, (unsigned *)&State, 64 ); + printf( " %d ", Vec_IntEntry(vCounts, i) ); + printf( "\n" ); + } + printf( "\n" ); + } + Vec_WrdFree( vTemp ); + Vec_WrdFree( vStates ); + Vec_IntFree( vCounts ); +} + //////////////////////////////////////////////////////////////////////// /// END OF FILE /// //////////////////////////////////////////////////////////////////////// -- cgit v1.2.3