Update (March 2014): A lot of the Z80 implementation has been superseded by the work of Al Petrofsky documented on another page.
Update (January 2011): At the end of last year I foolishly wrote: "I think the only significant improvements I can make to this code is by using a superoptimiser, which is non-trivial for such a large algorithm." Since then, I've gone back to first principles for the computation and come up with two "better" Z80 implementations. These replace the previously published code.
Computus is the calculation of Easter for any given year. For the purposes of this page, that means Easter Sunday in the Gregorian calendar according to the Book of Common Prayer of the Church of England.
Dr J R Stockton's excellent site covers most of the nuances of this computation, with one of his algorithms being (effectively):
int easter_dm(int year) {
// Based on EasterJRS at http://www.merlyn.demon.co.uk/estr-bcp.htm#A2008
// Returns the "day of March"; > 31 for April
int golden_number = year % 19;
int x = year / 100;
int q = 3 * (x + 1) / 4;
int bcp_cypher = q - (13 + x * 8) / 25;
x = (6 + ((5 * year) / 4) - q) % 7;
int dm = 21 + (golden_number * 19 + bcp_cypher + 15) % 30;
if (golden_number > 10) {
if ((dm + 1) > 49)
dm--;
} else {
if (dm > 49)
dm--;
}
return dm + 1 + (66 - x - dm) % 7
}
With a bit of refactoring, I rewrote this algorithm to use 16-bit unsigned arithmetic:
void easter_u16(u16 year, u16* month, u16* day) {
u16 a = year % 19;
u16 b = year >> 2;
u16 c = (b / 25) + 1;
u16 d = (c * 3) >> 2;
u16 e = ((a * 19) - ((c * 8 + 5) / 25) + d + 15) % 30;
e += (29578 - a - e * 32) >> 10;
e -= ((year % 7) + b - d + e + 2) % 7;
d = e >> 5;
*day = e - d * 31;
*month = d + 3;
}
Why stop there? If you're on a 16-bit machine, perhaps you don't have native division. So, using the "integer division by constants" ideas from Hacker's Delight:
void easter_u16_nodiv(u16 year, u16* month, u16* day) {
u16 a = year >> 1;
u16 b = a >> 1;
u16 c = b + (b >> 2);
u16 d = (a + c + (c >> 4) + (c >> 5) + (c >> 10)) >> 4;
u16 e = d & 255;
u16 f = (year - e * 19) & 255;
if (f >= 19) f = f - 19;
u16 g = (b >> 1) + (b >> 3);
u16 h = (g + (g >> 6) + (g >> 7)) >> 4;
u16 i = (h * 25) & 255;
u16 j = (b - i) & 255;
if (j >= 25) h = h + 1;
u16 k = (h * 3) >> 2;
u16 l = (h * 8) + 5;
u16 m = (l >> 1) + (l >> 3);
u16 n = (m + (m >> 6) + (m >> 7)) >> 4;
u16 o = l - (n * 25);
if (o >= 25) n = n + 1;
u16 p = (f + 5) * 3;
u16 q = (f * 16) + k - n + p;
u16 r = ((q >> 4) + (q >> 8)) & 254;
u16 s = q - (r * 15);
if (s >= 30) s = s - 30;
u16 t = s * 16 + f + 53;
u16 u = ((t >= 512) ? 27 : 28;
u16 v = (year >> 15) + (year & 32767);
v = (v >> 9) + (v & 511);
v = v + u + b - k + 2;
v = (v >> 9) + (v & 511);
v = (v >> 6) + (v & 63);
v = (v >> 3) + (v & 7);
v = (v >> 3) + (v & 7);
if (v != 7) u = u - v;
*day = u;
*month = 3;
if (u & 32) {
*day = u - 31;
*month = 4;
}
}
Some of the above might need a bit of explanation:
The final step was to convert this algorithm into Z80 assembly. The original translation (by hand) weighed in at over 3000 T-cycles and 600 bytes of code, but after quite a bit of optimisation (again, by hand) I got it down to two variations. The first is the shortest code I could come up with (149 code bytes, 8361-8406 T-cycles) whilst the second is the fastest without lookup tables (1799-1843 T-cycles, 355 code bytes):
; EasterZ80_Short
; Compute Gregorian Easter according to
; Book of Common Prayer in Z80 assembly
; Ian Taylor, January 2011
; On entry:
; HL is Gregorian year (0..65535)
; On exit:
; A is "Day of March" for Easter (22..56)
; B is day of month of Easter (1..31)
; C is month of year of Easter (3..4)
; All other registers preserved
; Constraints:
; No memory usage, except 8 stack words
; No use of IX, IY or shadow registers
; No self-modifying code
; Computation time: 8361-8406 T-cycles
; Code bytes used: 149
EasterZ80_Short:
PUSH DE ; Save DE
PUSH HL ; Push Year
CALL EasterZ80_Div ; Let T0 = Year % 19 ...
DB 19 ; A = Year % 19
LD D, B ; D = 0
LD E, A ; DE = T0
POP HL ; Let T1 = Year / 4 ...
PUSH HL ; HL = Year
CALL EasterZ80_Div ; Divide HL by following byte
DB 4 ; HL = Year / 4
PUSH HL ; Push T1
PUSH DE ; Push T0
CALL EasterZ80_Div ; Let T2 = (T1 / 25) + 1 ...
DB 25 ; HL = T1 / 25
INC HL ; HL = T2
PUSH HL ; Push T2
LD A, 3 ; Let T3 = (T2 * 3) / 4 ...
CALL EasterZ80_Mul ; HL = T2 * 2
CALL EasterZ80_Div ; HL = HL / 4
DB 4 ; HL = T3
EX (SP), HL ; Pop T2, Push T3
LD A, 8 ; Let T4 = (T0 * 19) - ((T2 * 8 + 5) / 25) + T3 + 15
CALL EasterZ80_Mul ; HL = T2 * 8
LD C, 5 ; BC = 5
ADD HL, BC ; HL = T2 * 8 + 5
CALL EasterZ80_Div ; HL = HL / 25
DB 25 ; HL = (T2 * 8 + 5) / 25
EX DE, HL ; DE = (T2 * 8 + 5) / 25
LD A, 19 ; A = 19
CALL EasterZ80_Mul ; HL = T0 * 19
SBC HL, DE ; Carry guaranteed to be 0
LD C, 15 ; BC = 15
ADD HL, BC ; HL = (T0 * 19) - ((T2 * 8 + 5) / 25) + 15
POP DE ; Pop T3
ADD HL, DE ; HL = T4
CALL EasterZ80_Div ; Let T5 = T4 % 30
DB 30 ; A = T5
POP BC ; Pop T0
LD L, A ; HL = T5
PUSH HL ; Push T5
LD L, 16 ; Let T6 = (15306 - T0 - T5 * 16) / 512
CALL EasterZ80_Mul ; HL = T5 * 16
PUSH DE ; Push T3
EX DE, HL ; DE = T5 * 16
LD HL, 15306 ; HL = 15306
SBC HL, BC ; Carry guaranteed to be 0
SBC HL, DE ; Carry guaranteed to be 0
LD A, H ; A = HL >> 8
RRA ; A = HL >> 9 (Carry was 0)
POP DE ; Pop T3
POP BC ; Pop T5
ADD A, C ; Let T7 = T5 + T6
LD C, A ; BC = T7
POP HL ; Pop T1
ADD HL, BC ; Let T8 = T7 + T1 - T3 + (Year % 7) + 1
SBC HL, DE ; Carry guaranteed to be 0
EX DE, HL ; DE = T1 + T7 - T3 (Carry was 0)
POP HL ; Pop Year
PUSH BC ; Push T7
PUSH HL ; Push Year
CALL EasterZ80_Div ; Divide HL by following byte
DB 7 ; A = Year % 7
LD H, B ; H = 0
LD L, A ; HL = (Year % 7)
ADD HL, DE ; HL = T8
INC HL ; HL = (Year % 7) + 1
CALL EasterZ80_DivC ; Let T9 = T8 % 7 (C was still 7)
CPL ; Let T10 = T7 - T9 - 1
POP HL ; Pop Year
POP BC ; Pop T7
ADD A, C ; A = T10
POP DE ; Restore DE
LD B, A ; B = T10
LD C, 3 ; C = March
CP 32 ; Compare with 32
RET C ; Return if T10 < 32
RES 5, B ; B = T10 - 32
INC B ; B = T10 - 31
INC C ; C = April
RET ; Return
EasterZ80_Mul: ; Let HL = HL * A : Let A = 0 : Let B = 0
PUSH DE ; Save DE
EX DE, HL ; DE = HL
LD HL, 0 ; HL = 0
LD B, 8 ; Eight bits
L1: ADD HL, HL ; HL <<= 1
ADD A, A ; A <<= 1
JR NC, L2 ; Skip if MSB was 0
ADD HL, DE ; HL = HL + DE
L2: DJNZ L1 ; Loop for each bit in A
POP DE ; Restore DE
RET ; Takes up to 415 T-Cycles
EasterZ80_Div: ; Divide by byte following 'CALL'
EX (SP), HL ; Swap HL with return PC
LD C, (HL) ; C = Following data byte
INC HL ; Skip data byte
EX (SP), HL ; Swap HL with return PC
EasterZ80_DivC: ; Let A = HL % C : Let HL = HL / C : Let B = 0
XOR A ; A = 0
LD B, 16 ; Sixteen bits
L3: ADD HL, HL ; HL <<= 1
ADC A, A ; A <<= 1 with carry
CP C ; Compare with divisor
JR C, L4 ; Skip if A < divisor
SUB C ; A = A - divisor
INC L ; HL = HL + 1 (HL was even)
L4: DJNZ L3 ; Loop for each bit in HL
RET ; Takes up to 768 T-Cycles
I'm particularly happy with the fast version below as it uses the undocumented
Z80 instruction SLIA (shift left inverted arithmetic):
; EasterZ80_Fast
; Compute Gregorian Easter according to
; Book of Common Prayer in Z80 assembly
; Ian Taylor, January 2011
; On entry:
; HL is Gregorian year (0..65535)
; On exit:
; A is "Day of March" for Easter (22..56)
; B is day of month of Easter (1..31)
; C is month of year of Easter (3..4)
; All other registers preserved
; Constraints:
; No memory usage, except 4 stack words
; No use of IX, IY or shadow registers
; No self-modifying code
; No subroutine calls
; Computation time: 1799-1843 T-cycles
; Code bytes used: 355
EasterZ80_Fast:
PUSH DE ; Save DE
LD D, H ; Let T0 = Year >> 1 ...
LD A, L
SRL D
RRA
LD B, D
LD C, A ; BC = T0
SRL D ; Let T1 = T0 >> 1 ...
RRA
LD E, A ; DE = T1
PUSH DE ; Push T1
PUSH HL ; Push Year
LD H, D
LD L, E ; HL = T1
SRL D ; Let T2 = T1 + (T1 >> 2) ...
RRA
SRL D
RRA
LD E, A ; DE = T1 >> 2
ADD HL, DE ; HL = T2
LD D, H ; Let T3 = (T0 + T2 + (T2 >> 4) + (T2 >> 5) + (T2 >> 10)) >> 4 ...
LD A, L
ADD HL, BC
SRL D
RRA
SRL D
RRA
LD B, D
SRL D
RRA
SRL D
RRA
LD E, A ; DE = T2 >> 4
ADD HL, DE
SRL D
RRA
LD E, A ; DE = T2 >> 5
ADD HL, DE
LD D, 0
LD E, B ; DE = T2 >> 10
ADD HL, DE
LD A, L
SRL H
RRA
SRL H
RRA
SRL H
RRA
SRL H
RRA ; A = T3
LD B, A ; Let T4 = T3 & 255 ...
ADD A, A ; Let T5 = (Year - T4 * 19) & 255 ...
LD C, A
ADD A, A
ADD A, A
ADD A, A
ADD A, B
ADD A, C ; A = (T4 * 19) & 255
NEG ; A = -(T4 * 19) & 255
POP HL ; Pop Year
ADD A, L ; A = T5
CP 19 ; If T5 >= 19 Then Let T5 = T5 - 19
JR C, L1
SUB 19
L1: LD C, A ; C = T5
EX (SP), HL ; Let T6 = (T1 >> 1) + (T1 >> 3) ...
PUSH HL ; Pop T1, Push Year, Push T1
LD B, L ; B = T1 & 255
LD A, L
SRL H
RRA
LD D, H
LD E, A
SRL H
RRA
SRL H
RRA
LD L, A
ADD HL, DE ; HL = T6
LD D, 0 ; Let T7 = (T6 + (T6 >> 6) + (T6 >> 7)) >> 4 ...
LD E, H
LD A, L
ADD A, A
EX DE, HL
ADC HL, HL
EX DE, HL ; DE = T6 >> 7
ADD HL, DE
ADD A, A
EX DE, HL
ADC HL, HL ; HL = T6 >> 6
ADD HL, DE
XOR A
ADD HL, HL
ADD HL, HL
ADD HL, HL
ADC A, A
ADD HL, HL
ADC A, A
LD L, H
LD H, A ; HL = T7
LD A, L ; Let T8 = (T7 * 25) & 255 ...
ADD A, A
ADD A, A
ADD A, A
LD D, A
ADD A, A
ADD A, D
ADD A, L ; A = T8
SUB B ; Let T9 = (T1 - T8) & 255 ...
NEG ; A = T9
CP 25 ; If T9 >= 25 Then Let T7 = T7 + 1
JR C, L2
INC HL
L2: INC HL ; Let T7 = T7 + 1 ...
LD D, H ; Let T10 = (T7 * 3) >> 2 ...
LD E, L
ADD HL, HL
EX DE, HL ; DE = T7 * 2
ADD HL, DE ; HL = T7 * 3
LD A, L
SRL H
RRA
SRL H
RRA
LD L, A ; HL = T10
PUSH HL ; Push T10
EX DE, HL ; DE = T10
INC HL ; Let T11 = (T7 * 8) + 5 ...
ADD HL, HL ; HL = T11 >> 1
LD B, L
SLIA B ; Equivalent to SLA B : INC B
LD D, H ; Let T12 = (T11 >> 1) + (T11 >> 3) ...
LD A, L
SRL D
RRA
SRL D
RRA
LD E, A
ADD HL, DE ; HL = T12
LD D, H ; Let T13 = (T12 + (T12 >> 6) + (T12 >> 7)) >> 4 ...
LD E, L
ADD HL, HL
LD A, H
ADD HL, HL
ADD A, H
LD L, A
LD H, 0
ADD HL, DE ; HL >> 4 = T13
LD D, L
ADD HL, HL
ADD HL, HL
ADD HL, HL
ADD HL, HL ; H = T13
LD E, H ; Let T14 = T11 - (T13 * 25) ...
LD A, H
ADD A, A
ADD A, A
ADD A, A
ADD A, H
LD H, A ; H = (T13 * 9) & 255
LD A, D
AND 240 ; A = (T13 * 16) & 255
ADD A, H
SUB B ; (-A & 255) = T14
CP 232 ; If T14 >= 25 Then Let T13 = T13 + 1
JR NC, L3
INC E
L3: LD A, C ; Let T15 = (T5 + 5) * 3 ...
ADD A, A ; Let T16 = (T5 * 16) + T10 - T13 + T15 ...
ADD A, A
ADD A, A
LD H, 0
LD L, A
LD D, H ; DE = T13
ADD HL, HL ; HL = T5 << 4
LD A, 5
ADD A, C
LD B, A
ADD A, A
ADD A, B ; A = T15
SBC HL, DE
LD E, A ; DE = T15
ADD HL, DE
POP DE ; Pop T10
ADD HL, DE ; HL = T16
LD A, H ; Let T17 = ((T16 >> 4) + (T16 >> 8)) & 254 ...
LD B, L
ADD HL, HL
ADD HL, HL
ADD HL, HL
ADD HL, HL
ADD A, H
AND 254 ; A = T17
POP HL ; Pop T1
SBC HL, DE ; HL = T1 - T10
PUSH HL ; Push T1-T10
LD H, 0 ; Let T18 = T16 - (T17 * 15) ...
LD L, A ; HL = T17
LD D, H
LD E, L ; DE = T17
ADD HL, HL
ADD HL, HL
ADD HL, HL
ADD HL, HL
SBC HL, DE ; HL = T17 * 15
LD A, B
SUB L ; A = T18
CP 30 ; If T18 >= 30 Then Let T18 = T18 - 30
JR C, L4
SUB 30
L4: LD B, A ; Let T19 = T18 * 16 + T5 + 53 ...
ADD A, A
ADD A, A
ADD A, A
LD H, D ; H = 0
ADD A, A
RL H
LD L, A ; HL = T18 * 16
LD A, 53
ADD A, C ; A = T5 + 53
LD E, A ; DE = T5 + 53
ADD HL, DE ; HL = T19
LD A, H ; If T19 >= 512 Then T20 = Let T18 + 27 Else Let T20 = T18 + 28
RRA
CPL
ADD A, 29
ADD A, B ; A = T20
LD B, D ; B = 0
POP DE ; Let T21 = (Year >> 15) + (Year & 32767) ...
POP HL ; Pop Year
PUSH HL ; Push Year
BIT 7, H
JR Z, L5
RES 7, H
INC HL
L5: LD C, H ; Let T21 = (T21 >> 9) + (T21 & 511) ...
RR C
LD H, B ; H = 0
RL H
ADD HL, BC ; HL = T21
SCF ; Let T21 = T21 + T20 + T1 - T10 + 2 ...
ADC HL, DE
LD C, A ; BC = T20
SCF
ADC HL, BC ; HL = T21
LD C, H ; Let T21 = (T21 >> 9) + (T21 & 511) ...
RR C
LD H, B
RL H
ADD HL, BC ; HL = T21
LD C, A ; BC = T20
LD A, L ; Let T21 = (T21 >> 6) + (T21 & 63) ...
AND 63
ADD HL, HL
ADD HL, HL
ADD A, H ; A = T21
LD D, 7 ; Let T21 = (T21 >> 3) + (T21 & 7) ...
LD L, A
SRL L
SRL L
SRL L
AND D
ADD A, L ; A = T21
LD L, A ; Let T21 = (T21 >> 3) + (T21 & 7) ...
SRL L
SRL L
SRL L
AND D
ADD A, L
LD L, A ; A = T21
CP D ; If T21 != 7 Then Let T20 = T20 - T21
LD A, C
JR Z, L6
SUB L
L6: POP HL ; Pop Year
POP DE ; Restore DE
LD B, A ; B = T20
LD C, 3 ; C = March
CP 32
RET C
RES 5, B
INC B ; B = T20 - 31
INC C ; C = April
RET
With thanks to Dr J R Stockton.