### Post by Robin Harbron on Mar 17, 2007 14:16:48 GMT -5

Prompted by phlegming's question and tlr's suggestion in this thread I thought I'd try coding a Linear Feedback Shift Register in BASIC.

I first heard about these when reading about some of my favourite Atari 2600 programmers from way back when. These routines were used to generate a predictable yet seemingly random sequence of numbers. These numbers were then used as a seed to generate the screen display. This allowed Pitfall! to cram 256 screens worth of game into a 4K cartridge, and same thing for the extremely long scrolling world in River Raid.

I used a LFSR in my original 2K version of Minima to generate a 256*96 (24k) tilemap to wander RPG-style. That same LFSR was used in my 1k game Splatform to generate the nine 256 character wide scrolling levels.

I found this explanation the most helpful: homepage.mac.com/afj/lfsr.html

A 10-bit LFSR made the most sense for the screen-clear idea because it gives 1023 values (note that you can never have a 0 in a LFSR, as the register will just return zeros forever after that... that's why there's always 2^n-1 valid combinations).

So I consulted this table to find out what bits to "tap" to get a maximal length sequence. 10 and 7 according to the chart. Note that the bits are numbered from 1, instead of 0 as we're used to in programming.

So anyway, here's an attempt to write one in BASIC. It's really not optimized, but that will be left as "an exercise for the reader"

5 REM 10-BIT LFSR BY ROBIN HARBRON 20070317

10 S=1001 : REM SEED CAN BE ANYTHING > 0 AND < 1024 (2^10)

20 GOSUB 1000

30 IF S<1001 THEN POKE S+1023,81 : REM DON'T USE THE VALUES ABOVE 1000 (WON'T FIT ON SCREEN)

40 IF S<>1001 THEN GOTO 20 : REM CHECK IF WHOLE SEQUENCE HAS RUN

50 END

1000 A=(S AND 512)/512 : REM GET 10TH BIT FOR TAP

1010 B=(S AND 64)/64 : REM GET 7TH BIT FOR TAP

1020 C=(A+B) AND 1 : REM XOR TWO BITS TOGETHER

1030 S=(S*2) AND 1023 : REM SHIFT AND TOSS HIGH BIT

1040 S=S+C : REM FEED TAPS BACK INTO LOW BIT

1050 RETURN

I don't suggest that this is the end-all and be all of implementations, just something that should be helpful to experiment with.

**UPDATE** You can download the above program here: psw.ca/prg/lfsr.zip

I first heard about these when reading about some of my favourite Atari 2600 programmers from way back when. These routines were used to generate a predictable yet seemingly random sequence of numbers. These numbers were then used as a seed to generate the screen display. This allowed Pitfall! to cram 256 screens worth of game into a 4K cartridge, and same thing for the extremely long scrolling world in River Raid.

I used a LFSR in my original 2K version of Minima to generate a 256*96 (24k) tilemap to wander RPG-style. That same LFSR was used in my 1k game Splatform to generate the nine 256 character wide scrolling levels.

I found this explanation the most helpful: homepage.mac.com/afj/lfsr.html

A 10-bit LFSR made the most sense for the screen-clear idea because it gives 1023 values (note that you can never have a 0 in a LFSR, as the register will just return zeros forever after that... that's why there's always 2^n-1 valid combinations).

So I consulted this table to find out what bits to "tap" to get a maximal length sequence. 10 and 7 according to the chart. Note that the bits are numbered from 1, instead of 0 as we're used to in programming.

So anyway, here's an attempt to write one in BASIC. It's really not optimized, but that will be left as "an exercise for the reader"

5 REM 10-BIT LFSR BY ROBIN HARBRON 20070317

10 S=1001 : REM SEED CAN BE ANYTHING > 0 AND < 1024 (2^10)

20 GOSUB 1000

30 IF S<1001 THEN POKE S+1023,81 : REM DON'T USE THE VALUES ABOVE 1000 (WON'T FIT ON SCREEN)

40 IF S<>1001 THEN GOTO 20 : REM CHECK IF WHOLE SEQUENCE HAS RUN

50 END

1000 A=(S AND 512)/512 : REM GET 10TH BIT FOR TAP

1010 B=(S AND 64)/64 : REM GET 7TH BIT FOR TAP

1020 C=(A+B) AND 1 : REM XOR TWO BITS TOGETHER

1030 S=(S*2) AND 1023 : REM SHIFT AND TOSS HIGH BIT

1040 S=S+C : REM FEED TAPS BACK INTO LOW BIT

1050 RETURN

I don't suggest that this is the end-all and be all of implementations, just something that should be helpful to experiment with.

**UPDATE** You can download the above program here: psw.ca/prg/lfsr.zip