So, I thought I'd do a separate post about LFSR as it's complicated to explain. For some background reading, see

Linear feedback shift register - Wikipedia, the free encyclopedia especially the section on Galois LFSRs as that's what we'll be using. Now, this will seem very complicated, but actually you don't really need to understand it and it's actually very simple to use...

So, the idea for generating the polynomial is dividing by a polynomial (which is something like

modulo some number). This looks and sounds very scary, but actually if we limit the scope of what we're doing, it becomes very easy (like a lot of things in maths). If we choose the modulus to be 2, we can work easy in binary space and treat a single bit as a term in the polynomial. So, for instance, we can express the polynomial above as 1101. Now, addition modulo 2 is just the XOR operator (1 XOR 0=1, 1 XOR 1=0 just like 1+0=1,1+1=2 but 2 mod 2=0). So we can express addition of this polynomial mod 2 as (n XOR %1101).

I'll gloss over the reasons for what we're doing exactly, but essentially the complicated sounding "dividing the current polynomial c by another polynomial p modulo q" when q=2 turns out to be easily expressible in terms of two cases:

`if c>p: c'=(c>>1) XOR p`

if c<=p: c'=(c>>1)

Moreover, if we choose an arbitrary n, we can find a polynomial with a maximum coefficient of x^n that has a period of (2^n)-1.

This is great for our use, it means if we take n=8 (the size of a byte), we can find a polynomial that gives us a pattern that repeats with period 255. If you look at the table in wikipedia, one such polynomial is:

. If we express this in our binary notation, this becomes 101110001, or in hex #171.

If we were implementing this in C, we could write something like:

`if (c&1)`

c = (c^0x171) >>1; // note that the high bit is always 1

else

c = c>>1; // note that the high bit is always 0

But we can actually make this even better on the Z80. Consider the comments above and the RRCA instruction. RRCA achieves >>1, and it sets carry if we need to do the XOR case, and moreover, it leaves the high bit set correctly. This means, we can then code this as:

` rrca`

jr nc,noxor

xor #38

noxor:

Now, you might wonder where the #38 comes from. This value is actually (#171>>1) XOR #80. As the RRCA has already left the high bit set, we don't need to set it with the XOR, and we also don't need to set the low bit (because we're shifting it away). So that polynomial above of 101110001 we can think of as x0111000x. Discarding the x's, we get %0111000, or #38.

There are other interesting properties of polynomials, e.g. the reverse bit pattern also has the same bit pattern, so 100011101 -> #e is also a suitable value for the XOR.

You can verify the period of this random number generator easily by making a test case and then examining memory:

` org #800`

ld hl,#8100 ; the buffer from #8100 contains the count of each rnd

ld de,#8000 ; the buffer from #8000 contains the sequence of rnd

ld b,0

ld a,1

clear:

ld (hl),e

inc l

djnz clear

loop:

ld (de),a

inc de

ld l,a

inc (hl)

rrca

jr nc,noxor

xor #e

noxor:

djnz loop

ret