LFSR6502

[RevEng]

I put together a program for easier design and testing of 6502 LFSRs on modern computers, called lfsr6502. I figured it might appeal to some others in the dasm club. The README.txt covers off the usage, but the quick summary is it allows easy embedding of 6502 LFSRs into the C code, which makes it much easier to evaluate, graph, and otherwise test the data with modern tools.

 

As an example, here's the pitfall8left LFSR that comes bundled. The original 6502 code is in the comment for each line.

 

void runpitfall8left(void)
{
    LDA (randv[0]);             //  LDA randv0
    ASL (A);                    //  ASL
    EOR (randv[0]);             //  EOR randv0
    ASL (A);                    //  ASL
    EOR (randv[0]);             //  EOR randv0
    ASL (A);                    //  ASL
    ASL (A);                    //  ASL
    ROL (A);                    //  ROL
    EOR (randv[0]);             //  EOR randv0
    LSR (A);                    //  LSR
    ROR (randv[0]);             //  ROR randv0
    LDA (randv[0]);             //  LDA randv0
}

As you can see, the syntax of the LFSR in C is very close to the original assembly code, which means translation back and forth between C and assembly is a lot less error-prone.

 

Using this tool, I came up with "xhybrid24", a fairly compact 24-bit LFSR that scores quite well in the dieharder random number test suite.

 

Of note for the AA crowd, lfsr6502 also bundles a LFSR that runs backwards from the bB rand8 sequence, so one could use it for pitfall type algorithmic generation.

 

If anyone is interested, you can grab binaries or source from the github releases page.

[Thomas Jentzsch]

It would be cool if you could also check the randomness (using some standard test) of the generated byte or bit sequences. I am sure there are quite some differences.

 

BTW: Adding River Raid would be nice.

Edited May 19, 2020 by Thomas Jentzsch

[RevEng]

It does support raw output, so the dieharder tests I mentioned above are an option. But any 8 bit or 16 bit LFSR is going to fail those miserably, due to the short period. I agree that some internal report that reports a score on certain qualities might be good.

 

The River Raid LFSR looks different than the others, so I'll add that in. Thanks for the suggestions!

[RevEng]

3 hours ago, Thomas Jentzsch said:

BTW: Adding River Raid would be nice.

Rather unexpectedly, the riverraid16 LFSR has a period of 57337!

[Thomas Jentzsch]

Yup, as written in my disassembly from 2001.  

[RevEng]

Ah, good work. I didn't see that comment.

[RevEng]

I've added a LFSR bitmap-output feature...

 

batari Basic 8-bit Galois LFSR

 

 

pitfall left 8-bit LFSR

 

 

batari Basic 16-bit (8-bit Galois extended to 16)

 

RiverRaid 16-bit 

 

The bytes run top to bottom, left to right. 8-bit LFSRs get turned into a 48x48 image, 16+ bit LFSRs get turned into 640x640. Dimensions were selected to more or less fit within the LFSR period, and were also selected to be divisible by 8, to highlight any byte-based patterns.

 

The seeming repeated blobs in the pitfall LFSR aren't on an 8-pixel boundary, but rather they're 9 pixels apart, which isn't all that surprising given they're arising from shifting.

 

The RiverRaid distribution is quasi-patterned, but that's probably more of a feature than a bug, considering it's used for algorithmic level generation. Same with the pitfall LFSR.

[Thomas Jentzsch]

I don't think the patterns are intentional, I suppose the knowledge we have now wasn't there back then. 

[RevEng]

Yeah, I didn't mean the patterns were intentional; just that these LFSRs are fit for their purpose. i.e. The patterns weren't a reason to scrap the approach and try again. Having repeated but different runs in terrain generation would likely lead to a "hey, that's cool" reaction by the programmers.

[Thomas Jentzsch]

I doubt anyone back then even noticed a pattern. Neither the developers and nor the players.