Jump to content
RevEng

LFSR6502

Recommended Posts

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.

  • Like 1

Share this post


Link to post
Share on other sites
Posted (edited)

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 by Thomas Jentzsch

Share this post


Link to post
Share on other sites

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!

Share this post


Link to post
Share on other sites
3 hours ago, Thomas Jentzsch said:

BTW: Adding River Raid would be nice.

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

Share this post


Link to post
Share on other sites

Yup, as written in my disassembly from 2001. ;) 

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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

 

batari8.png.ae508553ec4d23c31fbf4dd662466a68.png

batari Basic 8-bit Galois LFSR

 

 

pitfall8left.png.afa1b7ae4d1ab4921d0fad9a3370ff1e.png

pitfall left 8-bit LFSR

 

 

batari16.thumb.png.10d6ab4ef98aebd153c3d301cf538ee5.png

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

 

riverraid16.thumb.png.61abddac75aba9bd86ee0b148122312d.png

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.

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...