This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

LSFR, Random, RC4

LSFR, Random, RC4
by on (#69871)
I need a source of random values between $00 and $0f. Initially, I found some simple LFSRs and tried them. However, the byte stream output masked down to 4 bits repeated too frequently to be useful. I tried tweaking the LFSR, but did not have much luck. I use the data to populate parts of the name-table with background tiles, so patterns emerge visually really quick.

I got frustrated and implemented the full RC4 byte-stream generator as my pseudo-random number generator. The result works BEAUTIFULLY. But it is probably overkill. It is probably the most hard-core random number generator ever implemented on a NES (well, it could be?)

If anyone wants the rc4 code, I'll post it when I have time. It is tweaked for my specific use and not for doing real encryption (although changing it to do crypto would not be difficult). I always thought that it would be neat to encrypt level data and in-game text in such a way that one can't just "skip ahead". That the key to decrypt this text is large and the result of the game's state machine at the successful completion of some game objective. So that level 2 map won't be available until level-1 is won, and level-3 requires level-2 and so on. I like rc4 for this because it is easy to implement in C and not too bad in hand-coded 6502 asm. However, it does require 258 bytes of state (2 bytes in ZP and an entire page at $0700).

I was doing some further research (ok, googling and blindly changing the xor polynomials) and found a post from 2001 on an Atari 2600 forum by kevtris:

http://www.biglist.com/lists/stella/arc ... 00121.html

Has anyone else had success with large-period (2^16-1 or greater) LFSRs and would be willing to share their wisdom?

My main concern is that while a 16-bit LSFR might have a period of 2^16-1, but the period of that LSFR mod $0010 would be smaller. I have not written any test code for this yet (beyond my one failed experiment).
Re: LSFR, Random, RC4
by on (#69873)
clueless wrote:
Has anyone else had success with large-period (2^16-1 or greater) LFSRs and would be willing to share their wisdom?

I wrote a period 2^32-1 LFSR for LJ65 and reused it in Concentration Room and the game I'm working on for Jeroen's competition. It's based on the CRC-32-IEEE 802.3 polynomial.

Alleged RC4 is a memory hog compared to RNGs commonly used in NES games; its state occupies one-eighth of the NES's internal RAM. After its use in WEP and early WPA, researchers discovered numerous flaws, and Alleged RC4 has since been deprecated.

by on (#69925)
I disabled my RC4 stream generator and used the following (modified from Kevtris's 2001 Atari post mentioned above). The results are sufficient and the code is much faster. I've omitted the code that seeds to lfsr and other syntactic pleasantries.

Thoughts?

Code:

.segment "ZEROPAGE"
lfsr: .byte 0,0,0,0

.segment "DATA"
.align 256
buffer:   .res 192

.segment "CODE"
                ldy     #$c0                    ; Index into buffer, and count of tiles to make.
L0:             lda     lfsr + 3
                rol
                rol
                eor     lfsr + 3
                rol
                rol
                rol     lfsr + 0
                rol     lfsr + 1
                rol     lfsr + 2
                rol     lfsr + 3

                lda     lfsr + 3
                asl
                asl
                eor     lfsr + 1

                and     #$07      ; 8 tiles to choose from = 3 bits
                ora     #$10      ; tiles are $10 to $17 in char-rom.
                dey
                sta     buffer, y
                bne     L0
                rts