Computus: Calculating Easter Sunday

Computus is the algorithm used to calculate the date of Easter. Easter Sunday falls on the first Sunday after the full moon following the Spring equinox. For the purpose of the calculation the full moon is defined as day 14 of the lunar month and the Spring equinox as 20th March.

Unfortunately Computus defies any attempt to render it with beautiful code! This C function roughly follows the assembly language so is a little uglier than strictly necessary:

easter(year, month, date)
int year, *month, *date;
{
    int gold,cent,sa,la,epact,a18,da;
    gold = year%19;
    cent = year/100;
    sa = cent-cent/4;
    la = (8*cent+13)/25;
    epact = (19*gold-sa-la+15)%30;
    a18 = (gold+11*epact)/319;
    da = ((cent%4+year%100/4)*2+a18+32-year%4-epact)%7;
    *month = (90+epact+da-a18)/25;
    *date = (*month+19+epact+da-a18)%32;
}

The algorithm is similar to MaybeGauss1 found in J R Stockton's collection of algorithms for Easter Sunday and is valid for the Gregorian calendar well into the fourth millenium. The algorithm can be adapted to calculate a number of other dates:

• Shrove Tuesday - 47 days before Easter Sunday
• First Sunday in Lent - 42 days before
• Palm Sunday - 7 days before
• Whit Sunday - 49 days after

Finally here's the same algorithm in 8086 assembly language, length 128 bytes. On entry, AX is the year. On exit AL is the day, AH is the month:

easter:
  push cx
  push dx
  push bx
  push bp
  push si
  push di

  mov bp,ax     ; bp = year (1583:3999) 

  mov cx,100
  cwd
  div cx
  push dx
  xchg si,ax    ; si = century - 1

  mov ax,bp
  mov cl,19
  cwd           
  div cx
  mov bx,dx     ; bx = golden number - 1
  xchg ax,dx

  mul cl
  add ax,15
                ; ax in range (15:357)
  mov dx,si
  add ax,si
  shr dx,1
  shr dx,1
  sub ax,dx
  push ax
  mov ax,8
  mul si
  add ax,13
  mov cl,25
  div cx                      
  xchg dx,ax
  pop ax
  sub ax,dx
  mov cl,30
  cwd
  div cx
  mov di,dx

  mov al,11
  mul dx
  add ax,bx
  mov cl,206    ; multiply by 206 and discard the
  mul cx        ; lower 16 bits of the result.
                ; shorter than dividing by 319

  sub di,dx
  xchg ax,si
  and al,3 
  pop dx
  shr dx,1
  shr dx,1
  add ax,dx
  shl ax,1
  and bp,3
  lea bp,[bp+di-32]
  sub ax,bp
  mov cl,7
  cwd
  div cx
  xchg ax,dx
  add ax,di
  mov bp,ax
  add al,90
  mov cl,25
  div cl
  mov ah,al
  add al,19
  add ax,bp
  and al,31

  pop di
  pop si
  pop bp
  pop bx
  pop dx
  pop cx
  ret

Itsy-OS Kernel: Preemptive Switcher & Memory Manager

Itsy-OS v0.1 is a small 8086 operating system kernel providing two basic services: a simple preemptive task switcher and memory management. If necessary, simple IPC and task management can be added to provide the features of a traditional microkernel.

Weighing in at about 380 bytes, Itsy should port well to tiny architectures.

Memory Control Blocks

Each block of memory is preceded by a memory control block which is 32 bytes long. The blocks of memory are arranged as a circular linked list. The first memory control block resides in segment 050h.

org 0h
; -----------------------------
; [Master Memory Control Block]
; -----------------------------

M_NEXT:dw 0             ; address of next MCB
M_LAST:dw 0             ; address of previous MCB
M_PARA:dw 0             ; size of this block in paragraphs including MCB
M_FLAG:db 0             ; flags
       db 0             ;
M_NPRO:dw 0             ; next MCB containing process, zero if not in queue
M_LPRO:dw 0             ; previous MCB containing process, or zero
M_STKP:dw 0             ; stack pointer
M_STKS:dw 0             ; stack segment

M_TIME:dw 0             ; time allocated / de-allocated
M_DATE:dw 0             ; date allocated / de-allocated
M_OWNR:dw 0             ; user number who owns this memory
M_NAME:db '          '  ; name of this memory block

; ---------------------------------------------------------------------------

; flag bits
F_FREE equ 01h          ; zero if this is free memory
F_ACTI equ 02h          ; zero if no task ready for CPU

; ---------------------------------------------------------------------------

  jmp E_INIT            ; setup kernel

; ---------------------------------------------------------------------------

; -------------------
; [Nucleus Data Area]
; -------------------

D_PCP:dw 0              ; segment of current process's MCB
D_SWEN:db 0             ; set to zero when switching disabled

Task Switcher

The task switcher is called by the timer interrupt. First it checks whether switching is disabled. If not:

• disable switching
• save the registers of the current task on the stack
• save the stack pointer of the current task in it's MCB
• find the next MCB with an available task
• restore the new task's stack pointer and registers
• enable switching and transfer control to the new task

; ---------------
; [Task Switcher]
; ---------------

E_SWITCHER:
; test if the switcher is enabled or disabled (indivisible test and set)
  pushf
  push cx
  xor cx,cx
  cs xchg cl,byte[D_SWEN]
  jcxz N_NOSWITCH

; save the registers of the current process
  push ax
  push dx
  push bx
  push bp
  push si
  push di
  push es
  push ds

; save the stack of the current process
  mov di,M_STKP
  cs mov ds,word[di+D_PCP-M_STKP]
  mov word[di],sp     ; M_STKP
  mov word[di+2],ss   ; M_STKS


E_SHORTCUT:

; select an active task to switch to
N_SELTASK:
  mov ds,word[di-4]        ; M_NPRO
  test byte[di-6],F_ACTI   ; M_FLAG
  jz N_SELTASK             ; is this task active?
  cs mov word[di+D_PCP-M_STKP],ds

; restore saved state of process being switched to
  mov sp,word[di]          ; M_STKP
  mov ss,word[di+2]        ; M_STKS
  pop ds
  pop es
  pop di
  pop si
  pop bp
  pop bx
  pop dx
  pop ax
  call E_ENABLE
N_NOSWITCH:
  pop cx
  popf
  iret

Deallocate Memory

Called with DS = MCB of memory to free. Deallocated memory is wiped with 0CCh.

Switching is disabled while the memory structure is being modified. If the memory being deallocated contains a process, it is removed from the process queue. If adjacent memory blocks are marked as free, the blocks are combined.

; -------------------
; [deallocate memory]
; -------------------

E_MEMDEALLOC:

  cs mov byte[D_SWEN],0       ; disable switching

  xor di,di                   ; M_NEXT
  mov ax,word[di+M_NPRO]      ; see if there is entry in process queue
  test ax,ax
  jz N_NOPROC                 ; if there isn't, simply free the memory
  mov es,word[di+M_LPRO]      ; and if there is, remove it!
  es mov word[di+M_NPRO],ax
  mov bx,es
  mov es,ax
  es mov word[di+M_LPRO],bx

  mov ax,ds
  cs cmp ax,word[D_PCP]       ; check if process being killed is the current
  jnz N_NOPROC
  cs mov word[D_PCP],bx       ; if so, set last process as current

  call N_NOPROC               ; free the memory,
  mov di,M_STKP
  jmp short E_SHORTCUT        ; and then afterwards, switch to another task


N_NOPROC:
  mov bp,ds                   ; bp = first paragraph to clear
  mov bx,word[di+M_PARA]      ; bx = number of paragraphs to clear

  mov es,word[di]
  es test byte[di+M_FLAG],F_FREE        ; is next block free?
  jnz N_NNOTJOIN                        ; if not, can't join them

  es mov ax,word[di+M_PARA]             ; get size of next block
  add word[di+M_PARA],ax                ; add to size of this block
  es mov ax,word[di]                    ; move M_NEXT of next...
  mov word[di],ax                       ;  ...to M_NEXT of current
  inc bx                                ; an extra 2 paragraphs to clear
  inc bx
N_NNOTJOIN:
  and byte[di+M_FLAG],0FFh-F_FREE-F_ACTI       ; mark as free

  mov es,word[di+M_LAST]
  es test byte[di+M_FLAG],F_FREE        ; is previous block free?
  jnz N_PNOTJOIN                        ; if not, can't join them

  mov ax,word[di+M_PARA]                ; get size of this block
  es add word[di+M_PARA],ax             ; add to size of previous block
  mov ax,word[di]                       ; move M_NEXT of current...
  es mov word[di],ax                    ;  ... to M_NEXT of previous
  jmp short N_EXTRA2P
                                        ; block already marked as free
N_PNOTJOIN:
  inc bp              ; don't clear MCB
  inc bp
  dec bx
  dec bx

N_EXTRA2P:
  cld                 ; clear memory - bp=location, bx=paragraphs
  mov ax,0CCCCh       ; code for an INT3 instruction to fill memory with
  mov dx,01000h
N_CLRGO:
  mov es,bp
  sub bx,dx
  jc N_CLRFIN
  mov cx,08000h
  rep stosw
  add bp,dx
  jmp short N_CLRGO

N_CLRFIN:
  add bx,dx
  mov cl,3
  shl bx,cl
  mov cx,bx
  rep stosw

E_ENABLE:
  cs inc byte[D_SWEN] ; enable switching
  ret

Allocate Memory

Called with AX = number of paragraphs required. Returns DS = location of memory, or DS = 0 if no memory available. Switching is disabled while the memory structure is being modified. Allocation uses a simple best fit algorithm.

; -----------------
; [allocate memory]
; -----------------

E_MEMALLOC:

  cs mov byte[D_SWEN],0       ; disable switching

  xor di,di
  xor dx,dx                    ; segment of current choice
  xor cx,cx                    ; left-over memory from current choice
  inc ax
  inc ax
  mov bx,050                   ; MMCB

N_MOREMEM:
  mov ds,bx
  test byte[di+M_FLAG],F_FREE  ; is the block we are looking at empty?
  jnz N_WONTFIT                ; if it isn't, move on

  mov bx,word[di+M_PARA]
  sub bx,ax                    ; check size
  jc N_WONTFIT
  jz N_EXACT                   ; perfect fit :-)

; ** KLUDGE ***
  cmp bx,3                     ; if leftover memory block smaller than 3
  jc N_WONTFIT                 ; paragraphs, it would be too small to contain
                               ; a MCB.  Maybe handle this better later

  cmp cx,bx                    ; bx= size of potential leftover memory block
  jc N_WONTFIT                 ; have we found a better fit?
  mov cx,bx
  mov dx,ds                    ; if so, then select it!
N_WONTFIT:
  mov bx,word[di]              ; M_NEXT
  cmp bx,050                   ; are we at MMCB?
  jnz N_MOREMEM

  test dx,dx
  jne N_ALLOCIT
  mov ds,dx                   ; out of memory :-(
  jmp short N_ALEXIT
N_ALLOCIT:
  mov ds,dx
  mov es,word[di]              ; M_NEXT, es= next block

  mov bx,word[di+M_PARA]       ; bx= number of paragraphs for this block
  add bx,dx                    ; bx= end of this block
  sub bx,ax                    ; bx= location of new block's MCB        

  es mov word[di+M_LAST],bx    ; point next block to new block
  mov word[di],bx              ; M_NEXT, point this block to new block
  sub word[di+M_PARA],ax       ; resize this block
  push ds
  mov ds,bx                    ; point es to new block
  pop bx

  mov word[di+M_LAST],bx       ; initialise new block's M_LAST
  mov word[di+M_PARA],ax       ; initialise new block's M_PARA
  mov word[di],es              ; initialise new block's M_NEXT

N_EXACT:
  mov byte[di+M_FLAG],F_FREE   ; mark new block as no longer free
  mov word[di+M_NPRO],di
  mov word[di+M_LPRO],di
N_ALEXIT:
  jmp short E_ENABLE

Setup

Simply sets up the timer interrupt.

E_INT1C:
  call E_SWITCHER
  db 0EAh
D_OLDINT1C:
  dw 0,0

; ---------------------------------------------------------------------------

E_INIT:
  push cs
  pop es
  xor ax,ax
  mov ds,ax
  mov si,01Ch*4
  mov di,D_OLDINT1C
  cld
  push si
  movsw
  movsw
  pop di
  cli
  push ds
  pop es
  mov ax,050h
  stosw
  mov ax,E_INT1C
  stosw
  sti
; ...