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
lsr
bcs .skipEor
eor #$b2 ; various values possible here
.skipEor:
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...
http://www.ece.cmu.edu/~koopman/lfsr/8.txt
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 ;
.skipOr
