Tinkering: 2020-10-15: Assembler Gems: 8-Bit BCD Calendar Function Snippets

So, I am building a clock again. As usual, it is based on an Atmel AVR 8-bit µC, and I program it in assembly language. As usual, I have an RTC and a DCF77 receiver, both of which use BCD encoded time and date.

This time, I wanted (limited) time zone support. DCF77 is in CET/CEST (i.e., including DST switching), and I was thinking to also support to display the time in UTC, UTC+1 and UTC+2. This requires computing the previous day, e.g., Mar 1st, 2000, 0:30 CET as received from the DCF77 is Feb 29, 2000, 23:30 UTC. I already have procedures for computing the next day – the clock needs that for normal time keeping as time moves forward – but going backwards is new.

On my journey, I discovered the following gems. These are short assembler sequences that use no auxiliary registers or table lookups to handle Gregorian calendar corner cases. In fact, the whole function for computing the previous hour does not use any auxiliary register.

BCD Decrement

Let's start easy. How to decrement in BCD without clobbering any additional register? The AVR has a half-carry flag, i.e., a nibble over/underflow bit, so BCD arithmetics are relatively easy. The following procedure is for months, i.e., in range 0x01..0x12:

  ; input:  r17: month
  ; output: r17: decremented month
  subi    r17, 1
  brhc    hc             ; branch if half carry is clear
  subi    r17, 6
hc:
  brnz    done
  ldi     r17, 0x12
  ; decrement year here
done:

The subtracts one in binary, and if there was a nibble underflow, subtracts another 6 (the difference between the basis 16 and 10). There is no carry handling, because at 0x00, the value is reset to 0x12.

The next steps are less easy: decrementing the day of the month when it's the 1st, i.e., the switch from 0x01 to the previous month's last day.

Last Day of Previous Month

Assume it's not March 1st, but it's any other month's 1st. We want to go back one day, so what is the date of the last day of the previous month? Well, let's compute it in 8-bit AVR assembly. I'll put explanations for uncommon instructions are abbreviations in comments.

  ; input:  r17: cur month in BCD 0x01..0x12, but not 0x03 (March).
  ; output: r16: last day of previous month: 0x30 or 0x31
  mov     r16, r17
  subi    r16, 2
  subi    r16, 7
  sbci    r16, 1         ; subtract with carry immediate
  andi    r16, 1
  subi    r16, -0x30     ; there's no 'addi' instruction

Isn't that a gem? It's only 6 cycles. Additional to no auxiliary registers and no table lookup, this is free of branches.

But how does that work? I think a table is necessary to show the computations. Each line is one step, the columns are for the input months:

  cur month:    01    02    03    04    05    06    07    08    09    10    11    12
  subi 2        FF    00    01    02    03    04    05    06    07    0E    0F    10
  subi 7        F8    F9    FA    FB    FC    FD    FE    FF    00    07    08    09
              C=0     1     1     1     1     1     1     1     0     0     0     0
  sbci 1        F7    F7    F8    F9    FA    FB    FC    FD    FF    06    07    08
  andi 1        01    01    00    01    00    01    00    01    01    00    01    00
  subi -0x30    31    31    30    31    30    31    30    31    31    30    31    30

Starting at the bottom, the goal is to exploit that, if viewed from a distance, every second month is 31 days, and the others are 30. So we try to get 0 or 1 into r16 and then add 0x30. That's the last two instructions. The task for the instructions before that is to set bit 0 correctly: 1 for 31 days and 0 for 30 days.

Let's move in closer: months 01 and 02 both require 31 days in the preceeding month, but their bit 0 is different. The same holds for months 08 and 09. To fix, the code will flip the lowest bit in months 02..08. To flip a bit selectively, a 'subtract with carry' is used, so that the carry bit marks which lowest bits to flip. And to get the carry bit indicate that, the code uses 'subi 2' to make the value 01 large (i.e., 0xFF) but keep all other values small so that a subsequent 'subi 7' underflows exactly for those months where we want to flip the lowest bit.

So now let's move on to Februaries, i.e., to leap year checks!

Last Day of February (Except in Centurial Years)

If we're on March 1st and want to go back one day, the previous section does not help, because the previous month is February. For February, the number of days also depends on the year. Let us ignore the century rule for a second (years divisible by 100 are special), because DCF77 and the RTC in use (DS3234) use 2-digit years, so there is no century information. And the turn of the next century is also far away!

Here's the code to compute the number of days in February from the 2-digit BCD-encoded year.

  ; input:  r18: 2-digit year in BCD: 0x00..0x99
  ; output: r16: last day of February: 0x28 or 0x29
  mov     r16, r18
  sbrc    r18, 4        ; skip next instr. if bit 4 in register r18 is clear
  subi    r16, -2
  andi    r16, 3
  neg     r16
  ldi     r16, 0x29
  sbci    r16, 0x00

This is just 7 cycles! To me this feels less fancy than the month code with its weird double 'subi' to get the carry right. But we're getting there, just wait for it.

A table is helpful again to see what's happening:

  year & 0x1f:      00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19
  sbrc 4; subi -2   00 01 02 03 04 05 06 07 08 09 12 13 14 15 16 17 18 19 1A 1B
  andi 3            00 01 02 03 00 01 02 03 00 01 02 03 00 01 02 03 00 01 02 03
  neg            C= 0  1  1  1  0  1  1  1  0  1  1  1  0  1  1  1  0  1  1  1
  ldi 0x29          29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29 29
  sbci 0            29 28 28 28 29 28 28 28 29 28 28 28 29 28 28 28 29 28 28 28
  leap:             y  n  n  n  y  n  n  n  y  n  n  n  y  n  n  n  y  n  n  n

The first observation is that the leap year pattern repeats every 20 years, because 20 is divisible by 4. We only need to have a table that looks at the lower 5 bits of the BCD encoded year, values 0x00..0x19, i.e., 0x20, 0x40, 0x60, 0x80 work just like 0x00 etc.

The goal is to have 0x29 in r16 if the year is divisible by 4 (i.e., in binary, the lower 2 bits are 0), and 0x28 if it is not. The problem is: this is BCD, so checking the lower 2 bits does not work: 0x10 is divisible by 4, but 10 is not a leap year – 12 is. So the first thing to do is to adjust this: if bit 4 is set, we add 2 to shift the offset.

The rest is easy: mask out the lower 2 bits, negate to get the carry bit indicate 'is not zero', load 0x29, and subtract the carry.

Beautiful!

And there's more, because it bugged me that the code does not properly handle the century rules.

Last February of a Centurial Year

If the year is divisible by 100, the Gregorian calendar has special leap year rules: if the year is divisible by 400, it is leap, otherwise, it is not. So let's do that in assembler.

But wait, we only have two digit years in the RTC and the DCF77, so we cannot check whether the year is divisible by 400!

Well, we do have the week day: 1=Mon, 2=Tue, ..., 7=Sun from the DCF77 (the RTC can do week days, too).

It turns out that the week day can be used in a surprisingly simple way for find out the date before March 1st:

  ; input:  r19: week day (1 (Mon), 2 (Tue),...,7 (Sun)) of day before March 1st
  ; output: r16: last day of february: 0x28 or 0x29
  ldi     r16, 0x28
  cpi     r19, 2
  brne    1f
  ldi     r16, 0x29
1:

Yes, really, if the day before March 1st is a Tuesday, then and only then, it's a leap year, so it's Feb 29th. The reason that checking week days works is that the Gregorian calendar repeats every 400 years, i.e., the number of days in 400 Gregorian years is divisible by 7. So there are only four cases for week days for the day before March 1st in a centurial year:

 year          : day before March 1st
 (% 400) ==   0: Tue (2)
 (% 400) == 100: Sun (7)
 (% 400) == 200: Fri (5)
 (% 400) == 300: Wed (3)

So now we have this incredibly short sequence for centurial Februaries, and we need glue code to combine this with the other code for February (cpi r18, 0x00 ; breq centurial_februar). Glue code, really? Let's make it one complicated code sequence instead...

Last Day of February

The goal is to modify the sequence for February to incorporate week day information in centurial years. The following code is the result:

  ; input:  r18: 2-digit year in BCD: 0x00..0x99
  ; input:  r19: week day: 1 (Mon), 2 (Tue),...,7 (Sun) of day before Mar 1st
  ; output: r16: last day of February: 0x28 or 0x29
  mov     r16, r18
  cpi     r18, 0
  brne    not_century
  sbrs    r19, 0       ; skip next instr. if bit 0 in register r19 is set
not_century:
  sbrc    r18, 4
  subi    r16, -2
  andi    r16, 3
  neg     r16
  ldi     r16, 0x29
  sbci    r16, 0x00

That's only 10 cycles! The week day trick adds just three instructions to the normal code.

The idea behind this is to somehow modify the value of r16 before the division by 4 check so that for a normal centurial year (one that's not divisible by 400), the value is not divisible. And for a year divisible by 400 (i.e., if the week day before March 1st is a Tuesday), it behaves just like a normal leap year check.

The code uses a normal compare + branch to check for value 0x00 – boring, I know. Two instructions. This is the glue code that we need. The fancy thing is the next single instruction: 'sbrs r19, 0' skips the next instruction if the week day's bit 0 is set – if you look at the table again: the week day before March 1st in a leap centurial year is not only a Tuesday, but it is also the only even week day. So instead of '== 2', we can also check bit 0 for 0, and AVR has a skip instruction for that. (Note that this code does not work if you encode Sun as 0 instead of 7, but for DCF77 encoding and for the DS3234 RTC, it works.)

The code gets more complicated here: the centurial leap week day skip skips a skip instruction to compensate the BCD encoding of the year: the +2 we do to shift the 0x1* values into position for a divisible-by-4 test. So this skip is skipped. It means that +2 is done exceptionally also in non-leap centurial years, so the value changes from 0x00 to 0x02, which is not divisible by 4 anymore, and the rest of the code then results in 0x28 instead of 0x29.

There's still more.

We can do one cycle less if we have a register that is always 0x00. Let's call that register rZERO. The sequence 'cpi 0 ; brne' can be replaced by 'cpse' (compare and skip if equal) if done correctly to also get rid of that boring instruction sequence:

  ; input:  r18: 2-digit year in BCD: 0x00..0x99
  ; input:  r19: week day: 1 (Mon), 2 (Tue),...,7 (Sun) of day before Mar 1st
  ; input:  rZERO: 0x00
  ; output: r16: last day of February: 0x28 or 0x29
  mov     r16, r18
  sbrc    r19, 0        ; skip if bit in reg is clear
  cpse    r18, rZERO    ; compare, skip next instr. if equal
  sbrc    r18, 4        ; skip if bit in reg is clear
  subi    r16, -2
  andi    r16, 3
  neg     r16
  ldi     r16, 0x29
  sbci    r16, 0x00

This code now has a skip that skips a skip that skips a skip. I think it's the first time I am doing that. But that's 9 cycles for the complete leap year logic necessary when computing the previous date of March 1st!

A final note on stack usage: the sequences above are all designed such that the next level of decrementing (e.g., the year decrement after the month decrement) is done at the end of the sequence, so that the code can continue with a branch (tail call). This way, stack usage is constant, and no additional call/ret pairs are executed. E.g., when starting with the decremented month, computing the days of that month needs one 'subi' less. But it would require decrementing the month first, then returning and computing the number of days, which would require a call+ret, which uses stack and also takes around 4 cycles longer than a tail call branch.

I hope you had as much fun as me!