6502.org Forum  Projects  Code  Documents  Tools  Forum
It is currently Fri Nov 22, 2024 8:29 am

All times are UTC




Post new topic Reply to topic  [ 245 posts ]  Go to page Previous  1, 2, 3, 4, 5, 6, 7, 8 ... 17  Next
Author Message
PostPosted: Tue Mar 21, 2023 5:14 pm 
Offline

Joined: Mon Mar 13, 2023 9:38 pm
Posts: 80
Arlet wrote:
Quote:
so I could easily see how the state vector evolves (especially with numbers other than 0x45)

If you have a real random source, you could remove the LDA #$45 line, and just call the subroutine with a value in A. Even if it's a mediocre source of randomness, once it makes its way through the state machine, it will be pretty good. Just make sure you get a regular supply of odd numbers in there, or set bit 0 yourself.


It's an interesting algorithm, I've never seen it in the books and it passes all the statistical tests. How did you come up with this idea?


Top
 Profile  
Reply with quote  
PostPosted: Tue Mar 21, 2023 5:37 pm 
Offline
User avatar

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands
Quote:
How did you come up with this idea?

Basically by looking at the 6502 instruction set, and looking for anything that could be helpful. The ADC instruction jumps out as the most useful one. If you add a number to itself, you have a rotate left, which means that you can build a LFSR with it. Internally, it's made from full adders, which have XOR, AND, OR as building blocks, so it's quite a mixed bag. I started building a chain of ADCs and noticed some interesting results, but not quite good enough by itself. Then I started looking at ways to mix things up a bit, so went back to the instruction set, and picked EOR as a companion. I also tried the rotate and shift instructions, but they all mess up the carry flag.

With PractRand, it's easy to test a few ideas. If they suck, then it only takes 5 seconds before it tells you. I started with the basic ADC chain, and then inserted a few EORs here and there.


Top
 Profile  
Reply with quote  
PostPosted: Tue Mar 21, 2023 8:11 pm 
Offline

Joined: Mon Mar 13, 2023 9:38 pm
Posts: 80
Arlet, what command line do you use with PractRand to test your PRNG ?


Top
 Profile  
Reply with quote  
PostPosted: Tue Mar 21, 2023 8:12 pm 
Offline
User avatar

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands
my_test | RNG_test stdin


Top
 Profile  
Reply with quote  
PostPosted: Tue Mar 21, 2023 8:22 pm 
Offline

Joined: Mon Mar 13, 2023 9:38 pm
Posts: 80
Arlet wrote:
my_test | RNG_test stdin


is it the same as my_test | RNG_test stdin8 ?


Top
 Profile  
Reply with quote  
PostPosted: Tue Mar 21, 2023 8:24 pm 
Offline
User avatar

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands
I think stdin8 is more optimized for finding faults in 8 bit wide inputs, so that's probably better.


Top
 Profile  
Reply with quote  
PostPosted: Tue Mar 21, 2023 8:37 pm 
Offline

Joined: Mon Mar 13, 2023 9:38 pm
Posts: 80
Arlet wrote:
Quote:
How did you come up with this idea?

Basically by looking at the 6502 instruction set, and looking for anything that could be helpful. The ADC instruction jumps out as the most useful one. If you add a number to itself, you have a rotate left, which means that you can build a LFSR with it. Internally, it's made from full adders, which have XOR, AND, OR as building blocks, so it's quite a mixed bag. I started building a chain of ADCs and noticed some interesting results, but not quite good enough by itself. Then I started looking at ways to mix things up a bit, so went back to the instruction set, and picked EOR as a companion. I also tried the rotate and shift instructions, but they all mess up the carry flag.

With PractRand, it's easy to test a few ideas. If they suck, then it only takes 5 seconds before it tells you. I started with the basic ADC chain, and then inserted a few EORs here and there.


The problem is that since it is not based on sound mathematics, we do not know if there are loops for some seeds or not. It would be necessary to test all the seeds of 1 to $FFFFFF and check if for each seed we obtain 2^32 bytes without loop. So you should run rng_test for each 2^32 seed.


Top
 Profile  
Reply with quote  
PostPosted: Tue Mar 21, 2023 9:37 pm 
Offline
User avatar

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands
Alex1 wrote:
The problem is that since it is not based on sound mathematics, we do not know if there are loops for some seeds or not. It would be necessary to test all the seeds of 1 to $FFFFFF and check if for each seed we obtain 2^32 bytes without loop. So you should run rng_test for each 2^32 seed.


Not quite. You can prove that the ADC chain goes through all possible states before repeating. That is this part, which has 32 bits.
Code:
        ADD( s0, 0x45 );
        ADC( s1, s0 );
        ADC( s2, s1 );
        ADC( s3, s2 );

This property breaks with the next line, because it has a feedback from s6, resulting in chaotic behavior and shorter loops.
Code:
ADC( s4, s3 ^ s6 );

Whatever happens in s4, s5, s6 is random, but s0-s3 are counting systematically. You can see this by skipping ahead 256 steps, and notice that every time s1 is incremented by same amount. This can be explained mathematically. Starting with s0=0, after 256 steps, the variable 's0' will be back at 0, having gone through every other number exactly once. That means that a value of 0+1+2+...+255 has been added to s1, which is equal to 255*256/2 = 32640 is equal to 128 modulo 256. So, without any carries, when s0 loops around, s1 will be 0x80 higher. Now, adding the carries, when you add 256 times 0x45, you will overflow exactly 0x45 times, producing 0x45 carries to s1. So, including the carries, s1 will be 0xc5 (mod 256) higher, and because that's an odd number, you need to repeat that 256 times before s1 is back at 0.

The same argument goes for s1->s2 and s2->s3.


Last edited by Arlet on Wed Mar 22, 2023 9:25 am, edited 1 time in total.

Top
 Profile  
Reply with quote  
PostPosted: Tue Mar 21, 2023 11:38 pm 
Offline

Joined: Fri Jul 09, 2021 10:12 pm
Posts: 741
That's neat - you're proving first that the cycle length must be a multiple of 256 (so that s0 returns to zero), then that it must be a further multiple of 256 more (so that s1 returns to zero at the same time as s0), then x256 more so that s2 returns to zero at the same time, and finally another x256 so that s3 also returns to zero at this time. So the period is maximised and hence there are no short loops for these four bytes, every state is part of the same cycle, and the only thing you relied on was that the amount added to s0 each time was odd.

It's still not clear to me that we can guarantee that the rest of the longer chain of adds with feedback doesn't ever reduce this period at the output end, but I'm no expert on this!


Top
 Profile  
Reply with quote  
PostPosted: Wed Mar 22, 2023 5:36 am 
Offline
User avatar

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands
Quote:
It's still not clear to me that we can guarantee that the rest of the longer chain of adds with feedback doesn't ever reduce this period

During the 2^32 cycles where s0-s3 are guaranteed to get different values, s4-s6 will bounce along, and never get stuck in short loops, because it is constantly fed from the s0-s3 states that are producing 4GB of unique patterns.

Worst case is when you stop after 2^32 rounds, and then s4-s6 happen to have the same values as in the beginning, which makes 4GB the shortest possible period.


Top
 Profile  
Reply with quote  
PostPosted: Wed Mar 22, 2023 3:50 pm 
Offline
User avatar

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands
Here's a version that only requires 6 bytes of RAM, and 1 less instruction. Also, just for fun, only uses ADC. Passes PractRand <= 4GB then fails hard.
Code:
CLC
LDA #&45
ADC seed+0
STA seed+0
ADC seed+1
STA seed+1
ADC seed+2
STA seed+2
ADC seed+3
STA seed+3
ADC seed+4
ADC seed+5
STA seed+4
ADC seed+5
STA seed+5
ADC seed+4
ADC seed+2
RTS

Working Owlet BBC code


Top
 Profile  
Reply with quote  
PostPosted: Wed Mar 22, 2023 4:48 pm 
Offline
User avatar

Joined: Thu Dec 11, 2008 1:28 pm
Posts: 10985
Location: England
Quick thought: if you take only the MSBits, or conversely only the LSBits, are they also adequately random as a bitstream?


Top
 Profile  
Reply with quote  
PostPosted: Wed Mar 22, 2023 4:58 pm 
Offline
User avatar

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands
PractRand does extensive testing for isolated lower bits, so I would think so. It doesn't test the MSBits separately, I think, but I would expect those to be better quality.

For instance, this is a typical failure output message:
Code:
[Low1/8]BCFN(2+6,13-0,T)          R= +30.4  p =  9.1e-16    FAIL           

The "Low1/8" part means that for each byte, the least significant bit was isolated, and all those single bits were then fed into the "BCFN" test.


Top
 Profile  
Reply with quote  
PostPosted: Wed Mar 22, 2023 6:00 pm 
Offline
User avatar

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands
Got rid of one more instruction. First couple of output bytes don't look so good with all-zero seed value, but it still (barely) passes PractRand to 4GB. I don't think any more cycles can be removed unless you don't mind a somewhat lower quality (which could be fine for a lot of purposes).
Code:
CLC
LDA #&45
ADC seed+0
STA seed+0
ADC seed+1
STA seed+1
ADC seed+2
STA seed+2
ADC seed+3
STA seed+3
EOR seed+4
ADC seed+5
STA seed+4
ADC seed+5
EOR seed+2
STA seed+5
RTS

BBC code


Top
 Profile  
Reply with quote  
PostPosted: Thu Mar 23, 2023 5:10 pm 
Offline

Joined: Mon Mar 13, 2023 9:38 pm
Posts: 80
I feel like there's a bug somewhere. I used my code in C (which is a literal translation of your 6502 code to C) and your code in C. I have the same output on both sides up to byte 326 and then it's different. My byte 326 is at $46 and yours is at $45. Do you know what could be the problem?

My C code :

Attachment:
Sélection_011.png
Sélection_011.png [ 34.35 KiB | Viewed 3303 times ]


Your C code:

Attachment:
Sélection_012.png
Sélection_012.png [ 33.58 KiB | Viewed 3303 times ]


And with your C code i've loops :

Quote:
Found '008AA873' at index 0 !
Found '008AA873' at index 11EC9D07 !
Found '008AA873' at index 36982356 !
Found '008AA873' at index B20751BF !


But not with my C code.


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 245 posts ]  Go to page Previous  1, 2, 3, 4, 5, 6, 7, 8 ... 17  Next

All times are UTC


Who is online

Users browsing this forum: No registered users and 10 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to: