ZX Spectrum Flags of the European Union

Someone, somewhere, out there on the Internet, is looking for the flags of the twenty-eight (current) member countries of the European Union  ... in the original Sinclair ZX Spectrum SCREEN$ format. Surely...

Computus 3

It's been a few years since my last look at calculating the date of Easter Sunday using only Z80 machine code, but I thought I'd finally re-visit it. In particular, I wanted to look in detail at Al Petrofsky's awesome optimizations of my lame attempts.

If you want a master-class in optimizing integer calculations on archaic CPUs (and who doesn't?) look no further than Al's solution. It's the product of deep understanding of:

• The Z80 instruction set,
• Integer multiplication-by-constants,
• Integer division-by-constants,
• Modulo arithmetic, and
• Easter computus.

At only two hundred or so opcodes, and no branches, it's a beautiful distillation.

Z80 Easter Egg T-Shirt

It's the Z80 asssembler for calculating the date of Easter Sunday:

16-bit Shifts on Z80

One would think that 16-bit, unsigned, binary shifts on a Z80 microprocessor would be as trivial as it comes. But I've only recently realised just how little has been actually written down about optimising Z80 code for even these simplest of cases. So here's a quick guide; alas, probably thirty years too late!

The reason these shifts aren't obvious is because of the inherent asymmetry in the Z80 processor. Although it has a fairly orthogonal 8-bit ALU, its 16-bit (address) pipeline only has a simple adder. Multiplying HL by two (a left shift) is trivial: ADD HL, HL. Shifting right is a whole can of worms; to shift a 16-bit quantity to the right, it is sometimes quicker (and/or shorter) to shift/rotate left and adjust.

I've written a library of routines to perform the shifts, including some that use self-modifying code to eke out a few more T-cycles. I believe they're optimal. Anyone out there know different?

Computus 3

After reminiscing with Dr J R Stockton about old computers, it got to converting my 16-bit algorithm for Easter to 8-bit Z80 assembly language. I spent quite some time hand-optimising it (which is an enjoyable past-time in itself, if there's no deadline involved!) and posted the code with a short commentary.

I had thought about writing a bespoke super-optimiser to try to find the "ultimate" Z80 code, but with just under 500 bytes of machine code, that's over 10¹⁰⁰⁰ permutations. I think I might have to divide and conquer!

Modulo Arithmetic in Z80 assembler

I've done a little 8-bit assembly coding in the past, mostly Z80 (on Sinclair machines) and 6502 (on BBC Micro), but I've never really thought about arithmetic optimisations for those platforms as much as I have the last couple of months.

Imagine that you are (in the 21st century) writing Z80 date manipulation functions where the day of the week was important. You'd naturally want to perform "modulo 7" arithmetic on 16-bit quantities. If you had a routine to perform integer division by 7, you might find "z = x mod 7" given "y = floor(x / 7)" for unsigned 16-bit values as follows:

; Z80 assembly to compute 'x mod 7' from 'x' and 'x div 7'
; 'x' in HL
; 'x div 7' in DE
LD B, D       ;  4T 1B -- Take a copy of DE
LD C, E       ;  4T 1B -- BC := x div 7 
EX DE, HL     ;  4T 1B -- DE := x, HL := x div 7 
ADD HL, HL    ; 11T 1B -- HL := (x div 7) * 2
ADD HL, HL    ; 11T 1B -- HL := (x div 7) * 4
ADD HL, HL    ; 11T 1B -- HL := (x div 7) * 8
AND A         ;  4T 1B -- Clear carry flag
SBC HL, BC    ; 15T 2B -- HL := (x div 7) * 7
EX DE, HL     ;  4T 1B -- HL := x, DE := (x div 7) * 7
AND A         ;  4T 1B -- Clear carry flag
SBC HL, BC    ; 15T 2B -- HL := x - (x div 7) * 7
LD A, L       ;  4T 1B -- A:= x mod 7
; 'x mod 7' in A

At first glance, this seems fairly fast, compact code (91 T-cycles and 14 code bytes), but notice that, by the end of it, one side-effect is setting H to zero. Not very surprising as "x mod 7" is clearly an 8-bit quantity. So why go to the trouble of computing full 16-bit intermediates that have only partial bearing on the final result? Providing that the upper eight bits don't "pollute" the lower eight (e.g. during division or change of sign), you need not compute them. Especially as 16-bit arithmetic is disproportionately expensive on Z80:

• Obviously uses more precious registers,
• Addition of 16-bit quantites takes at least 11 T-cycles compared to 4 T-cycles for 8-bit quantities,
• Subtraction via 'SBC' requires worrying about the carry flag as there is no 16-bit 'SUB' instruction,
• Shifting 16-bit quantities (multiplication and division by two) other than 'ADD HL, HL' requires two, long instructions.

So the 8-bit equivalent could be:

 

; Z80 assembly to compute 'x mod 7' from 'x' and 'x div 7'
; 'x' in HL
; 'x div 7' in DE
LD A, E       ;  4T 1B -- A := x div 7 [low bits]
ADD A, A      ;  4T 1B -- A := (x div 7) * 2 [low bits]
ADD A, A      ;  4T 1B -- A := (x div 7) * 4 [low bits]
ADD A, A      ;  4T 1B -- A := (x div 7) * 8 [low bits]
SUB E         ;  4T 1B -- A := (x div 7) * 7 [low bits]
NEG           ;  8T 2B -- A := (x div 7) * -7 [low bits]
ADD A, L      ;  4T 1B -- A := x mod 7
; 'x mod 7' in A 

 

 

This is both faster and smaller (32 T-cycles and 8 code bytes) with no loss of accuracy, so I'm a bit bemused that it's taken me nearly three decades to stumble across it. And a lot of good it will do me too!

P.S. Why is 'NEG' so expensive on Z80? Given that 'CPL' is only 4 T-cycles and 2 code bytes, it seems a waste to dedicate precious silicon on a similar instruction that can be represented with existing instructions ('CPL' then 'INC A') for the same cost. Bah humbug!