Memotest 2017 - Z80 coding contest

Everything about programming, including VDP and Sound programming.
Tony Brewer
Posts: 108
Joined: 08 Jan 2014 20:50

Re: Memotest 2017 - Z80 coding contest

Post by Tony Brewer »

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.
User avatar
AndyKey
Posts: 74
Joined: 12 Aug 2012 01:29
Location: Southampton, UK
Contact:

Re: Memotest 2017 - Z80 coding contest

Post by AndyKey »

What are the first few results the PRNG17 function should produce...?

I think its
01181
1608D
0A75D
0BF68
1C71D
158E8
028F2
1C4A8
{{{ Andy
Tony Brewer
Posts: 108
Joined: 08 Jan 2014 20:50

Re: Memotest 2017 - Z80 coding contest

Post by Tony Brewer »

Andy, those results are correct.
Tony Brewer
Posts: 108
Joined: 08 Jan 2014 20:50

Re: Memotest 2017 - Z80 coding contest

Post by Tony Brewer »

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 self-modifying 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.
Tony Brewer
Posts: 108
Joined: 08 Jan 2014 20:50

Re: Memotest 2017 - Z80 coding contest

Post by Tony Brewer »

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.
Tony Brewer
Posts: 108
Joined: 08 Jan 2014 20:50

Re: Memotest 2017 - Z80 coding contest

Post by Tony Brewer »

What makes the advanced challenge harder is that p and q are 17-bit, not 16-bit. 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.
Tony Brewer
Posts: 108
Joined: 08 Jan 2014 20:50

Re: Memotest 2017 - Z80 coding contest

Post by Tony Brewer »

Please note the following wording in post 2 that has not changed since the start:

"PRNG16 will produce 15 high-quality bits every iteration and it is possible to obtain a high-quality 16-bit result 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 high-quality 16-bit 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.
Tony Brewer
Posts: 108
Joined: 08 Jan 2014 20:50

Re: Memotest 2017 - Z80 coding contest

Post by Tony Brewer »

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

Tony Brewer
Posts: 108
Joined: 08 Jan 2014 20:50

Re: Memotest 2017 - Z80 coding contest

Post by Tony Brewer »

Thank you to everyone who entered the competition.

Best PRNG16: 37 bytes, 169 T-states.
Best PRNG17: 51 bytes, 211 T-states.

More details later.
Last edited by Tony Brewer on 16 Oct 2017 00:35, edited 1 time in total.
Martin A
Posts: 799
Joined: 09 Nov 2013 21:03

Re: Memotest 2017 - Z80 coding contest

Post by Martin A »

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!

Code: Select all

NAME TestRom

TYPE rom

p   EQU &A000
q   EQU &A002
rnd equ &A004

ORG &2000
;if bytes 0 - 7 are 8-1 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

re-organising 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
Post Reply