*** M E M O R U M ***

EDIT:
The competition has now closed but if you have just found this page and enjoy Z80 programming why not have a go anyway?

Memotest 2017

This is a Z80 assembly language challenge, intended to be a fun test of your ability to write the smallest and fastest code possible for a pseudo-random number generator (PRNG) using an algorithm invented in 2016.

This algorithm differs from a simple linear feedback shift register (LFSR) in at least two respects: how it works and its vastly improved quality. Instead of using the previous pseudo-random number (PRN) to generate the next, there are two variables, p and q, that are added together to give the PRN. The next state is derived from the current state as follows:

p := (p ROL a) XOR (p SHL b) XOR (q SHL b) XOR p XOR q
q := (p ROL c) XOR (q ROL c)

where

p ROL a = p rotated left by a bits
p SHL b = p shifted left by b bits (arithmetic)
q SHL b = q shifted left by b bits (arithmetic)
p ROL c = p rotated left by c bits
q ROL c = q rotated left by c bits

a, b and c are constants.
p and q have the same number of bits.

A set of constants can be chosen so that the sequence is full-period and the resulting PRNs perform best in randomness tests. The initial state or seed cannot be all zeroes, thus p = 0, q = 0 is not allowed. Although the seed cannot be zero, the PRN can be.

Hint
XOR is associative and commutative.

Basic challenge

Write code for a routine called PRNG16. p, q and the PRN are all 16-bit. Remember a new PRN is obtained just by adding the new p and q. Ignore the carry from the addition as it is very unrandom. p, q and the PRN should be kept in registers. You can use whichever you prefer, however see rules below.

The [a,b,c] constants are [14,2,7].

To check your code is working, here are the first sixteen PRNs when the seed is p = 1, q = 0:
4085, 5530, 2C7C, 769F, A248, DFFD, 202D, F2F1, 5ACA, 4DC8, D1D1, ADCD, 0598, 1B30, 8094, 540C

It will take 2^32-1 or 4294967295 iterations before the p and q outputs are the same as the initial p and q inputs.

Advanced challenge (optional)

A feature of this PRNG algorithm is that the more significant the bit or byte, the more random it is. Bit 0 fails a particular randomness test and a higher-quality 16-bit result can be achieved by combining the high bytes from two successive iterations.

An alternative that should be faster is to use 17-bit p and q, add them and throw away the lsb to give a higher-quality 16-bit PRN in one go. The advanced test is to write such a routine called PRNG17.

The [a,b,c] constants are [7,8,12].

Here are the first sixteen PRNs (top 16 bits of 17-bit sum) when the seed is p = 1, q = 0:
08C0, B046, 53AE, 5FB4, E38E, AC74, 1479, E254, E127, A736, FC9C, F89A, 3D47, 3466, AA02, EC84

It will take 2^34-1 or 17179869183 iterations before the p and q outputs are the same as the initial p and q inputs.

Programming rules

1. Your routine must exit with the new p and q in the same registers as they were on entry. The new PRN is an output only, p and q are both inputs and outputs.
(Most people used DE = p, BC = q, HL = PRN in the Basic challenge.)

2. Your routine must not contain self-modifying code as it should be able to run entirely in ROM.

3. Your routine must be self-contained and not call or jump to any address outside the routine itself.

4. Your routine must run correctly if placed anywhere in memory.

5. Your routine must run correctly thousands of millions of times.

Contest Rules

1. Please do NOT post any of the following either here or on the Memotech Facebook page:

* Your source code
* Tips or spoilers
* The number of bytes in your solution

2. Send your source code to me by a private message here or on Facebook (click on my name) any time before the end of Friday October 13th 2017.

3. I prefer Z80 instructions to be in upper-case, indented by one tab. Multiple entries are allowed, should you find a better solution. Please include in the source code your name and the number of bytes in your routine (excluding RET).

4. The Basic or Advanced winner will be the person or persons who can beat or match my smallest code for the Basic or Advanced challenge, to be announced during Memofest. The number of T-states will act as a tie-breaker, if necessary.

reserved

Is there any restriction on self modifying code?

Self-modifying code is not allowed in the basic challenge code, which should be able to run in ROM.

New programming rules added to post 2 above.

Are the "undocumented" Z80 instructions allowed?

Things like: LD IXh, A (0xDD, 0x67)

Or "Official" Z80 instructions only?

Any code that will run on a Z80A CPU is permitted, including "undocumented" instructions.