Re: [stella] incoming source

Subject: Re: [stella] incoming source
From: David Galloway <davidgalloway@xxxxxxxxxxxxxx>
Date: Sun, 12 Dec 2004 16:18:01 -0800
Thomas Boutell wrote:

Works just as well in firefox.

It looks like as soon as the same number comes up, the entire sequence
repeats. And I saw a repetition after only 128 values. So some bytes
must never come up. None of which matters if all you need is a reasonably
random-looking bit or two with a periodicity of at least 128, and I think you definitely have that in the rightmost bits at least. Very
nifty routine for 2600 purposes.

A couple of things regarding the Linear Feedback Shift Register (LFSR). First of all Lee's example page uses 123 ($7b) as the default constant and that means it repeats after (2^7 -1) or 127 iterations. The example code that Mr. Jentzsch provided used the constant $b2 which repeats after (2^8-1) or 255 iterations

For every iteration of (2^n-1) you will get every value in that range with no repeats. This is an important property and was a reason that this algorithm was used as type of counter in the TIA hardware, the HSync counter for instance. (This type of counter can't be checked for LESS THAN or GREATER THAN but can be used if you are using EQUALS)

This property can also be used to shuffle cards in a card game or do a bitmap dissolve of a display where you can guarantee that every pixel will be erased in a constant time.

Now a comment about Mr. Jentzsch's code
Here is the code again.

2. Random number generation:
This code should do the whole job and is *much* shorter:
 lda random    ; initialize to non-zero at start
 bcs .skipEor
 eor #$b2      ; various values possible here
 sta random

The caution in the comment to initialize to non-zero isnt' neccesary since a bcs is being used. Clearly, a zero will fall into the eor #$b2. If a bcc was used, then the comment would be valid and random would stick on zero. Both a BCC and BCS work by the way in that you get a full sequence. BCS includes zero in the sequence but not 255, BCC includes 255 in the sequence but not zero.

Like Thomas mentioned the other 2^8 constants are listed here...

Ok this next bit isn't useful but some whimsy. To code the TIA LFSR in 6502. I didn't do a thorough analysis but could not quickly find an equivalent constant in above routine to generate the same values as the TIA HSync counter LFSR, so I have directly coded an equivalent to the hardware.

The hardware implementation in the TIA has the requirement of the LFSR value not initialized as 63 because it would stick on 63.
Only 0 to 56 are used.

; TIA HSync LFSR in 6502. Just for the hell of it. Code not tested or optimized
; Kind of clumsy so you can see it's better to use
; the simpler LFSR code above. However, in hardware this method is simpler. Refer to TIA schematic

; The hardware does this: next_bit5 = not(bit0 XOR bit1)
; lfsr cannot be initialized to 63

lsr lfsr ; always shift lfsr and put bit0 into carry
lda lfsr ; get bit1 (now in bit0 position)
adc #$00 ; add bit0 (in carry) with bit one (effectively bit0 XOR bit1)
lsr ; (bit0 XOR bit1) now in carry
bcs .skipOr ; lda lfsr ;
ora #$20 ; set bit 5 if result was zero
sta lfsr ;

Current Thread