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-CyclesI'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 RETWith thanks to Dr J R Stockton.