On 1/10/10 11:21 PM, Frank A. Stevenson wrote:
> On Sun, 2010-01-10 at 22:41 +0100, sascha wrote:
>
>> On Sun, Jan 10, 2010 at 09:36:51PM +0100, Frank A. Stevenson wrote:
>>
>>> I think it is should be compared with what you get from "purely random"
>>> states, it could be that our round function has a propensity for
>>> generating invalid states, and that would be a major flaw in our
>>> approach. (which advance value are you using?)
>>>
>>> F
>>>
>>>
>>>
>> or mail the source code.
>>
>
> Or I could just do it myself, the back stepping source is available on
> http://traxme.net/a5/ . M vd S also mailed me an even faster version of
> this code. It is kind of a problem that there are lots of bits and
> pieces of the kitchen sink laying around in sundry places, but not
> comitted to SVN. Perhaps we should make a "tinkering" folder in the
> repository for these things ?
>
>
Good idea.
I'm not too confident with these numbers flying around all based on my
coding only. Verification of these results is hard and bugs are as easy
to introduce as they are hard to find.
Only if someone were to reproduce my results this could serve as a basis
for a decision on a new table strategy. Sharing the code now would put
us at risk of copying bugs alongside code. (apart from that, all this
statistics code is not a pretty sight at this moment)
The core of my backclocking code is based on Frank's code, with the
ClockBack function replaced by:
int A5Backwards::ClockBack(uint64_t final, int steps, int *maxdepth, int
offset1, int offset2, int offset3)
{
int ret=0;
if ( final )
{
FillBack( final );
*maxdepth = steps;
}
if ( steps < *maxdepth ) *maxdepth = steps;
if ( steps == 0 )
{
uint64_t test = mBack1[offset1] | mBack2[offset2] |
mBack3[offset3];
//std::cout << "Candidate: " << std::hex << test << "\n";
return 1;
}
// since at least 2 lfsr's are shifted at every clock, there are 4
previous states possible. We check here if such previous states would
have resulted in a certain shift.
// states in which - clocked back - we have 2 equal and 1 unequal clock
bits:
if ( CB1S(mBack1[offset1+1]) == CB2S(mBack2[offset2+1]) &&
CB1S(mBack1[offset1+1]) != CB3S(mBack3[offset3]) ) ret +=
ClockBack(0,steps-1,maxdepth,offset1+1,offset2+1,offset3 );
if ( CB1S(mBack1[offset1+1]) == CB3S(mBack3[offset3+1]) &&
CB1S(mBack1[offset1+1]) != CB2S(mBack2[offset2]) ) ret +=
ClockBack(0,steps-1,maxdepth,offset1+1,offset2 ,offset3+1);
if ( CB2S(mBack2[offset2+1]) == CB3S(mBack3[offset3+1]) &&
CB2S(mBack2[offset2+1]) != CB1S(mBack1[offset1]) ) ret +=
ClockBack(0,steps-1,maxdepth,offset1 ,offset2+1,offset3+1);
// states in which - clocked back - we have 3 equal clock bits:
if ( CB1S(mBack1[offset1+1]) == CB2S(mBack2[offset2+1]) &&
CB1S(mBack1[offset1+1]) == CB3S(mBack3[offset3+1]) ) ret +=
ClockBack(0,steps-1,maxdepth,offset1+1,offset2+1,offset3+1);
return ret;
}
This
1) counts the number of possible states at depth steps
2) records the maximum depth reached in *maxdepth
The macro's which make life easier:
#define MASK1 0x7ffff
#define MASK2 0x3fffff
#define MASK3 0x7fffff
#define BITS1 19
#define BITS2 22
#define BITS3 23
#define STATE2LFSR1(state) ((state)&MASK1)
#define STATE2LFSR2(state) (((state)>>BITS1)&MASK2)
#define STATE2LFSR3(state) (((state)>>(BITS1+BITS2))&MASK3)
#define CB1S(state) ((STATE2LFSR1(state)&(1<<8))?1:0)
#define CB2S(state) ((STATE2LFSR2(state)&(1<<10))?1:0)
#define CB3S(state) ((STATE2LFSR3(state)&(1<<10))?1:0)
mBackN is filled with backclockings of individual lfsrs. This is fast
for N-step backclocking with N=large, but slight overkill for checking
one or two states back. This version is more suitable and portable for a
simple 1 clockback check:
#define CB1N(lfsr1,n) ((lfsr1&(1<<(8+n)))?1:0)
#define CB2N(lfsr2,n) ((lfsr2&(1<<(10+n)))?1:0)
#define CB3N(lfsr3,n) ((lfsr3&(1<<(10+n)))?1:0)
int backshifts=0;
// states in which - clocked back - we have 2 equal and 1 unequal clock
bits:
if ( CB1N(lfsr1,1) == CB2N(lfsr2,1) && CB1N(lfsr1,1) !=
CB3N(lfsr3,0) ) backshifts |= 1;
if ( CB1N(lfsr1,1) == CB3N(lfsr3,1) && CB1N(lfsr1,1) !=
CB2N(lfsr2,0) ) backshifts |= 2;
if ( CB2N(lfsr2,1) == CB3N(lfsr3,1) && CB2N(lfsr2,1) !=
CB1N(lfsr1,0) ) backshifts |= 4;
// states in which - clocked back - we have 3 equal clock bits:
if ( CB1N(lfsr1,1) == CB2N(lfsr2,1) && CB1N(lfsr1,1) ==
CB3N(lfsr3,1) ) backshifts |= 8;
Any questions or suggestions welcome.
In light of code sharing and verification, I would like to ask anybody
to try to use some proper macros to separate the bitlogic from the
flow-logic.
Regards, M.
_______________________________________________
A51 mailing list
[email protected]
http://lists.lists.reflextor.com/cgi-bin/mailman/listinfo/a51
