LFSR (and screen clearing)

[Robin Harbron]

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

[tlr]

Nicely done Robin!

Haven't run it, does it look cool?

[Robin Harbron]

tlr said:

Haven't run it, does it look cool?

Well, it looks kind of nice in warp mode in VICE It's pretty slow at 1 Mhz, but at least each point is plotted in linear time.

I'm sure it could be sped up a lot even in BASIC, never mind switching to ML.

I updated the above post to include a download of the program, so you guys don't have to type it in

[Wonder-Boy]

I have run it and it works exactly as I meant. Good work!
It will take me some time to understand. Thanks for your explanation and the links, I will study them.

[Robin Harbron]

phlegming said:

I have run it and it works exactly as I meant. Good work!
It will take me some time to understand. Thanks for your explanation and the links, I will study them.

Cool, feel free to ask once you've dug in a bit. Lots of good reading linked from that wikipedia page, but I have to admit that a good bit of it goes over my head.

I have a tough time digesting things when it's presented as formal math. Somehow when it goes up on that 40 column blue screen, it all makes sense to me

[oktup]

Hi... o/

New around here.

This thread peaked my interest for something to practise learning assembly language on. I'd never head of LFSR before, but thanks to the excellent BASIC example above I could visualise what it did.

Anyhow, here's the code I cobbled together with some random comments relating to the BASIC program. A PRG is attached also - SYS 49152 to run.

Used DASM for assembler, Crimson Editor for editing and VICE for emulation. Comments welcomed on better ways to code it etcetera. Thanks.

;
; Linear Feedback Shift Register
;

processor 6502

org $c000

ZTEMP equ $fb

; S=1001
start lda #<1001 ; lo-byte seed
sta seed
lda #>1001 ; hi-byte seed
sta seed+1
; GOSUB 1000
loop jsr process
; IF S<1001 ... ?
clc
lda seed+1 ; seed hi-byte
cmp #$03 ; = 768 (hi-byte of 1001)
bcc lesthan ; no, less than
; IF S<>1001 ... ?
clc
lda seed ; seed lo-byte
cmp #$e9 ; = 233 (lo-byte of 1001)
bcc lesthan ; no, less than
beq exit ; yes, we're done, exit
bcs loop ; no, more than, ignore and go-around
; END
exit rts ; done!
; ... THEN POKE S+1023,81
lesthan ; clc - not needed here as calls are always from bcc - save a byte :)
lda seed ; seed lo-byte
adc #$ff ; add 255
sta ZTEMP ; save lo-temp
lda seed+1 ; seed hi-byte
adc #$03 ; add 768 with carry
sta ZTEMP+1 ; save hi-temp

lda #$51 ; CBM 'dot' char
ldy #$00
sta (ZTEMP),y

jmp loop

; A=(S AND 512)/512
process lda seed+1 ; seed hi-byte
and #$02 ; 10th bit
lsr ; /512
sta temp ; save for later
; B=(S AND 64)/64
lda seed ; seed lo-byte
and #$40 ; 7th bit
lsr ; /2
lsr ; /4
lsr ; /8
lsr ; /16
lsr ; /32
lsr ; /64
; C=(A+B) AND 1
clc
adc temp ;
and #$01 ; xor together
sta temp ; save for later
; S=(S*2) AND 1023
clc
asl seed ; seed * 2 lo-byte
rol seed+1 ; seed * 2 hi-byte
lda seed+1 ; get hi-byte
and #$03 ; and 1023
sta seed+1 ; save for later
; S=S+C
clc
lda seed ; get seed lo-byte
adc temp ; add
sta seed ; save
lda seed+1 ; get hi-byte
adc #$00 ; add carry
sta seed+1 ; save
rts

seed dc.w 0 ; seed storage
temp dc.b 0 ; temp storage

[Robin Harbron]

Welcome oktup, nice to see some activity around here!

Well done on your assembly version. Looks like a solid, straight-forward implementation.

The "process" subroutine looked ripe for optimization, so I came up with this:

process 
	ldx #0		;initialize counter
	lda seed+1
	and #$02	;check 10th bit
	beq .ahead1
	inx		
.ahead1	lda seed
	and #$40	;check 7th bit
	beq .ahead2
	inx
.ahead2 txa		;low bit of ACC now equivalent to the 10th and 7th bit XOR'd
	ror		;move bit to carry
	rol seed	;shift low byte of seed, and move carry in
	lda seed+1
	rol		;shift high byte of seed
	and #$03	;chop off high bits
	sta seed+1
	rts

I hope the comments explain things well enough; I'm using the X register in place of the temporary storage you had, and eliminating all the shifts and the XOR. Storing the seed in zero page will shave another 5 bytes off this routine too. Feel free to ask, I can explain more.

BTW, the code tags strip the formatting out on this forum for some reason, so I've been using the pre tags... the small font is annoying, but it's easy to copy and paste it into a text editor this way.

[David Murray]

I couldn't help but make a small modification to the BASIC program. Change line 30 to this:

30 IF S<1001 THEN Q=S+1023:POKE Q,46:POKE W,81: POKE E,160:E=W:W=Q

Makes it look a bit more interesting. Might even look better if we were modifying the color attribute instead of the actual character code.

[dz]

Here's my version in (pseudo) optimized BASIC. The problem is the lack of SHIFT and XOR tokens in the language, which makes the code convoluted and slower. In my emulator it seems slightly faster, though I haven't really benchmarked it, so your mileage may vary.

5 REM 10-BIT LFSR - OPTIMIZED BY DZ.
10 S=1001 : REM SEED (1 < S < 1023)
100 A=0 : IF (S AND 512) THEN A=1 : REM GET 10TH BIT FOR TAP
110 B=0 : IF (S AND 64)  THEN B=1 : REM GET 7TH BIT FOR TAP
120 S=(S*2) AND 1023 : REM SHIFT AND DISCARD MSB
130 IF (A<>B) THEN S=S+1 : REM SHIFT IN THE LSB (SET IF A XOR B)
140 IF (S<1001)  THEN POKE S+1023,81 : REM ONLY VALUES < 1000 ARE VISIBLE
150 IF (S<>1001) THEN GOTO 100 : REM CONTINUE UNTIL WE FINISH THE CYCLE

The differences are:
1. I avoid the GOSUB which will require two jumps (GOTO 10, GOSUB 100), and it also requires pushing the state and return address into the stack.
2. Avoid expensive arithmetic to get tap bits. All we need to know is if the bit is set or clear. Performing a comparison implies a subtraction which is much faster than a division.
3. Avoid expensive arithmetic to simulate XOR. Instead, I get the tap bits and if they are different, shift in a 1 (they can only be 1 or 0 because of the way we set them in lines 100 and 110; so if they are different its the same result as an XOR). This works out because in line 120, when we shift, we clear the high bit, so there is no need to shift in a 0 since it's already there by default.

There are still some problems that may overshadow some of the performance improvements:
1. Too many jumps (each IF-THEN requires a comparison and a jump). Although the comparisons are simple bits, BASIC doesn't know this and will do a full comparison of the integer values.
2. Still too much slow arithmetic. In particular, I hate line 120 but can't think of a better way to shift in BASIC. The problem is that the interpreter is not smart enough to tell that we want to shift left (multiply by 2), so it performs a very expensive multiplication operation.

I'd appreciate any other comments.

-dZ.