Memotest 2017  Z80 coding contest

 Posts: 62
 Joined: 08 Jan 2014 20:50
Re: Memotest 2017  Z80 coding contest
Absolute jumps can be used in the Advanced challenge, if needed. (You will not need them in the Basic challenge.) Programming rule 4 ("Your routine must run correctly if placed anywhere in memory") means you cannot choose a specific starting address. Any type of JP to a label within the routine is acceptable.
Re: Memotest 2017  Z80 coding contest
What are the first few results the PRNG17 function should produce...?
I think its
01181
1608D
0A75D
0BF68
1C71D
158E8
028F2
1C4A8
I think its
01181
1608D
0A75D
0BF68
1C71D
158E8
028F2
1C4A8
{{{ Andy

 Posts: 62
 Joined: 08 Jan 2014 20:50
Re: Memotest 2017  Z80 coding contest
Andy, those results are correct.

 Posts: 62
 Joined: 08 Jan 2014 20:50
Re: Memotest 2017  Z80 coding contest
Updates:
* I think we should have an Advanced winner as well as a Basic winner, so now you have two chances to be a victor!
* In post 2, I have listed the first 16 PRNs for both challenges.
* In post 3, I have added the word entirely to Programming rule 2. Your routine must not contain selfmodifying code as it should be able to run entirely in ROM. This means you cannot use the stack now, as it made the Advanced challenge too easy.
* I think we should have an Advanced winner as well as a Basic winner, so now you have two chances to be a victor!
* In post 2, I have listed the first 16 PRNs for both challenges.
* In post 3, I have added the word entirely to Programming rule 2. Your routine must not contain selfmodifying code as it should be able to run entirely in ROM. This means you cannot use the stack now, as it made the Advanced challenge too easy.

 Posts: 62
 Joined: 08 Jan 2014 20:50
Re: Memotest 2017  Z80 coding contest
We are now about halfway through the time allowed for the code challenges. Both of them can be solved without using the stack (not permitted) so that the code could run on a Z80 system with no RAM at all.
If you have completed the basic challenge, you should find the solution to be rather pleasing and I urge you to try the advanced challenge if you have time as it can be equally pleasing. In some ways it is easier than the basic one, in other ways harder.
If you have submitted an entry, are you sure you have saved every last byte possible? Multiple entries are allowed.
If you have completed the basic challenge, you should find the solution to be rather pleasing and I urge you to try the advanced challenge if you have time as it can be equally pleasing. In some ways it is easier than the basic one, in other ways harder.
If you have submitted an entry, are you sure you have saved every last byte possible? Multiple entries are allowed.

 Posts: 62
 Joined: 08 Jan 2014 20:50
Re: Memotest 2017  Z80 coding contest
What makes the advanced challenge harder is that p and q are 17bit, not 16bit. You can represent the two extra state bits however you choose, provided Programming rule 1 is not broken. Remember the aim of the game is to write the smallest and fastest code possible.

 Posts: 62
 Joined: 08 Jan 2014 20:50
Re: Memotest 2017  Z80 coding contest
Please note the following wording in post 2 that has not changed since the start:
"PRNG16 will produce 15 highquality bits every iteration and it is possible to obtain a highquality 16bit result by combining the high bytes from two successive iterations.
An alternative that should be faster is to use 17bit p and q, add them and throw away the lsb to give a highquality 16bit PRN in one go. The advanced test is to write such a routine called PRNG17."
Therefore PRNG17 should be faster than two successive iterations of PRNG16, i.e. T(PRNG17) < 2 * T(PRNG16), otherwise it is pointless.
"PRNG16 will produce 15 highquality bits every iteration and it is possible to obtain a highquality 16bit result by combining the high bytes from two successive iterations.
An alternative that should be faster is to use 17bit p and q, add them and throw away the lsb to give a highquality 16bit PRN in one go. The advanced test is to write such a routine called PRNG17."
Therefore PRNG17 should be faster than two successive iterations of PRNG16, i.e. T(PRNG17) < 2 * T(PRNG16), otherwise it is pointless.

 Posts: 62
 Joined: 08 Jan 2014 20:50
Re: Memotest 2017  Z80 coding contest
Here are the first 16 new p, q and PRN values for PRNG16 when seed is p = 1, q = 0, in hexadecimal and binary:
Code: Select all
p (hex), q (hex), PRN (hex), p (bin), q (bin), PRN (bin)
4005, 0080, 4085, 0100000000000101, 0000000010000000, 0100000010000101
1290, 42A0, 5530, 0001001010010000, 0100001010100000, 0101010100110000
1454, 1828, 2C7C, 0001010001010100, 0001100000101000, 0010110001111100
3899, 3E06, 769F, 0011100010011001, 0011111000000110, 0111011010011111
52C5, 4F83, A248, 0101001011000101, 0100111110000011, 1010001001001000
3CEF, A30E, DFFD, 0011110011101111, 1010001100001110, 1101111111111101
2F5E, F0CF, 202D, 0010111101011110, 1111000011001111, 0010000000101101
2A02, C8EF, F2F1, 0010101000000010, 1100100011101111, 1111001011110001
E3D9, 76F1, 5ACA, 1110001111011001, 0111011011110001, 0101101011001010
B97E, 944A, 4DC8, 1011100101111110, 1001010001001010, 0100110111001000
37BB, 9A16, D1D1, 0011011110111011, 1001101000010110, 1101000111010001
D6F7, D6D6, ADCD, 1101011011110111, 1101011011010110, 1010110111001101
F518, 1080, 0598, 1111010100011000, 0001000010000000, 0000010110011000
4EBE, CC72, 1B30, 0100111010111110, 1100110001110010, 0001101100110000
1A53, 6641, 8094, 0001101001010011, 0110011001000001, 1000000010010100
4ACE, 093E, 540C, 0100101011001110, 0000100100111110, 0101010000001100

 Posts: 62
 Joined: 08 Jan 2014 20:50
Re: Memotest 2017  Z80 coding contest
Thank you to everyone who entered the competition.
Best PRNG16: 37 bytes, 169 Tstates.
Best PRNG17: 51 bytes, 211 Tstates.
More details later.
Best PRNG16: 37 bytes, 169 Tstates.
Best PRNG17: 51 bytes, 211 Tstates.
More details later.
Last edited by Tony Brewer on 16 Oct 2017 00:35, edited 1 time in total.
Re: Memotest 2017  Z80 coding contest
This was my PRNG16 entry, the actual entry is 44 bytes and 177 cycles.
The code here is a little longer, as to prove it was romable, I build and tested it as a paged rom!
The code here is a little longer, as to prove it was romable, I build and tested it as a paged rom!
Code: Select all
NAME TestRom
TYPE rom
p EQU &A000
q EQU &A002
rnd equ &A004
ORG &2000
;if bytes 0  7 are 81 resp. autoboot rom via &2010 on power up/reset
;but after high memory cleared, any variables set will be retained
DB 0,0,0,0,0,0,0,0
; filler bytes
DB 0,0,0,0
; BASIC's ROM command enters at &200C
JP run
DB 0
;at 2010 auto entry point, issue a ret just in case
RET
.run
PUSH HL
PUSH DE
PUSH BC
PUSH AF
ld bc,(q)
LD de,(p)
call calc
ld (q),bc
ld (p),de
ld (rnd),hl
POP AF
POP BC
POP DE
LD L,&00
EX (SP),HL
JP &0089
; RET
; Memofest 2017 coding competition
; Routine entry conditions
; BC = Q
; DE = P
; Routine exit conditions
; BC = new Q
; DE = new P
; HL = rnd16 value
; A register is corrupted
;
; IX,IY and alternate registers are unused
; No stack use other than the return address
; Code is position independant and ROMable
.calc
;step 1 form the T value of p xor q in the HL pair
ld a,b
xor d
ld H,a
ld a,c
xor e
ld l,a ;HL = t with A still holding low byte
;step 2 calculate (p xor q) rol 7 by swapping the bytes then doing (p xor q) ror 1
ld b,l ;and swap the high & low bytes on transfer to BC
ld c,h ;for new Q to be calculated, old Q isn't needed any more
rra ;lowest bit to carry, from the copy in A
rr c ;rotate right the swapped bytes to form T rol 7
rr b ;which is the new Q value
;step 3 calculate (p ROL a) in DE, as the old P isn't needed any more
ld a,e ;get the low byte
rra ;do (p ROR 2) as that's faster than (p ROL 14)
rr d
rr e
rra
rr d
rr e ;DE now holding (P ror 2)=(P rol 14)
;step 4 xor in HL which has the value (p xor q)
ld a,d
xor h
ld d,a
ld a,e
xor l
ld e,a ;DE is now (p rol 14) xor (p xor q)
;step 5 perform SHL 2 on the (p xor p) value in HL as tht's the last use.
add hl,hl
add hl,hl
;step 6 complete the P value
ld a,h
xor d
ld d,a
ld h,a
ld a,l
xor e
ld e,a
ld l,a ;DE and HL now both (P rol 14) xor (p xor q) xor ((p xor q) shl 2)
;final step add P to Q value for the final rnd16 result
add hl,bc
RET
end
Notes:
new p = (p ROL a) XOR (p SHL b) XOR (q SHL b) XOR p XOR q
new Q = (p ROL c) XOR (q rol c)
a=14
b=2
c=7
ROL 14 for 16 bit value = ROR 2
reorganising gives
new p = (p ROR 2) XOR ((p xor q) shl 2) XOR (p xor q)
neq q = (p xor q) ROL 7
replacing (p xor q) with t gives
new p = (p ror 2) XOR (t shl 2) xor t
new q = t rol 7
(t rol 7) can be replaced with (t ror 1) and swapping the byte pairs. ie:
t = abcdefgh ijklmnop
t ROL 7 = hijklmno pabcdefg
t ror 1 = pabcdefg hiljkmno
swap bytes = hijklmno pabcdefg
Z80 has no 16 bit rotate, but can be simulated using an extra register
to rotate the end bit into carry then doing 2 byte wise rotates
a = ijklmnop
b = ijklmnop
c = abcdefgh
after rra
a = ?inklmno cy = p
after rr c
c = pabcdefg cy = h
after rr b
b = hijklmno cy = p