Thanks lidnariq! I actually ended up using one of the polynomials from 32stages.txt. Specifically, [32, 23, 21, 16].
Ok everybody, I have a working 32-bit lfsr using the shortcut method I figured out. I'll need to see if I can improvie it at all, since this was just quick and dirty. However, it runs in constant time, and it probably could be simplified even more, I'd just need to look at it some more.
Code: Select all
game_random2
txa
pha
lda rnd4 ;3
tax ;2 5
eor rnd2 ;3 8
sta rnd2 ;3 11
lsr rnd4 ;5 16
ror ;2 18
lsr rnd4 ;5 23
ror ;2 25
pha ;3 28
txa ;2 30
eor rnd4 ;3 33
sta rnd4 ;3 36
pla ;4 40
lsr rnd4 ;5 45
ror ;2 47
and #$e0 ;2 49
eor rnd2 ;3 52
pha ;3 55
lda rnd4 ;3 58
eor rnd3 ;3 61
sta rnd4 ;3 64
pla ;4 68
sta rnd3 ;3 71
lda random ;3 74
sta rnd2 ;3 77
txa ;2 79
sta random ;3 82
pla
tax
lda random
rts
I've had a simple NES program (the one this routine is for, actually) running a loop where it begins by copying 8 random bytes generated from this routine, and then repeatedly reads from the routine, looking for anything that matches this 8-byte string. After 10 minutes, it's still looking, so I think this has more than enough of a period for non-repeating randomness. However, I don't know how well the values are distributed; they look pretty random to me!
For the record, the above code is the equivalent of a Galois LFSR that uses $00A10001 as its XOR, where each byte of output is the result of 8 shifts.
If anyone wants to use this code or run some tests on it, be my guest.
(Also, if anyone wants me to explain how I came up with this code, I'll be happy to explain; I just don't want to post a wall of text if nobody's interested.
)
Edit: One last thing! You need to initialize this routine by writing a nonzero value to random, rnd2, rnd3, or rnd4. I did it by writing $80 to rnd4.