Binary-Coded Decimal Addition on Atmel AVR

Display mode

Back to Articles

UPDATE: Nov 2021

Petter Källström emailed me, saying that there are a couple of weirdnesses and inefficiencies in the implementation given at the bottom of this article, and provided alternative code as follows:

Petter's more better implementation

-- input = r18, C and H flag
-- output = r18 and C flag
DAA:
  push r19
  in   r19, SREG    ; Let r19 contain the SREG
  cpi  r18, $9A     ; Set C flag in r19 if r18 >= 9A, and H flag in SREG if lower nibble is < 10
  brlo DAA_endif
  sbr  r19, (1<<SREG_C)
DAA_endif:
  sbrs r19, SREG_H  ; If input H flag was set, then skip the H-flag test
  brhs DAA_hi       ;   If H indicate lower nibble is < 10, then jump over...
  subi r18, -$06    ; adjust (adjust if r19.H-flag set, or if lower nibble >= 10)
DAA_hi:
  sbrc r19, SREG_C  ; If output C=1
  subi r18, -$60    ;   ...adjust
  out  SREG, r19
  pop  r19
  ret

Back to our previously scheduled article:

The Atmel AVR series of microcontrollers can be used in a wide variety of applications, from radios right through to inkjet printers, but a popular application in hobbyist projects is for digital clocks and counters. There are two main portions to any clock or counter program: a piece of code to increment the internal counter, and another piece of code to format and output the counter on a display.

A problem arises where these two portions of code need to interact. If one of these tasks is made less taxing for the microcontroller, the other is made more complicated; as a result, there are two prevailing schools of thought on how to achieve this interaction.

This article will examine the implications of choosing the second method: the use of a BCD number to hold the counter.

Packed BCD digits

The concept behind BCD is a simple one: instead of using a byte to represent any value between 0 and 255, a byte is used to represent the decimal digits only: 0 to 9. This allows for each segment of a multiple-digit display to be tied directly to a byte in the number to show, which greatly simplifies the logic behind showing the number.

Byte-wise BCD
Figure 1: Byte-wise (full) BCD display

The disadvantage of using a full byte to represent each digit is the waste produced: over 95% of the usable range of numbers in a byte is lost, and a large number of bytes have to be stored for a number of significant size. In a microcontroller environment, where memory space is often at such a premium that one extra byte is significant, this wastage is simply untenable.

An alternative scheme is to use each nybble of a byte to store a BCD digit: in this manner, two digits can be stored inside a byte, increasing the range of values available for storage ten-fold. The code required to pull out digits for display is still very straightforward, since simple boolean operations will yield the required result.

Packed BCD
Figure 2: Packed BCD display

A packed BCD number can be held in half the space of the equivalent full-BCD value, and is a viable compromise between the full range of binary numbers and the ease of display of full-BCD. In addition to this, packed BCD (hereafter referred to as simply "BCD") can be trivially conceptualised, through conversion to hexadecimal: as an example, the BCD value 0x93 represents decimal 93.

BCD addition: the problem

Using BCD to display a decimal number may simplify the display logic a great deal compared to the alternative, but a problem arises when calculations need to be done on the numbers. A microcontroller, much like any other computer of the modern age, is a binary machine with a binary arithmetic unit: it has no understanding of BCD, and will dutifully treat each number coming into it as a plain binary number.

Example additions of BCD numbers

0x15 + 0x03 = 0x18
0x72 + 0x07 = 0x79
0x38 + 0x02 = 0x3A

It is in additions that cause a carry between digits that the problem appears. In the above example, the BCD numbers 0x38 and 0x02 should add to 0x40, but the addition has operated instead on the plain numbers and produced the wrong answer. What is required is a method of adjusting the value after addition, to account for the fact that the values being operated on are BCD.

The Intel IA-32 series of microprocessors contains such a method as part of the base instruction set: Decimal Adjust after Addition (DAA). If this instruction is run after an addition, the result stored in the accumulator will be adjusted.

DAA usage on Intel x86

mov al, 38h
add al, 03h

; At this point, al = 0x3B
daa
; al = 0x41

The Atmel AVR doesn't contain such a convenient instruction as DAA, but the algorithm behind the DAA instruction is documented as part of the Intel IA-32 Reference manual, and is simple both to understand and to re-implement.

The decimal adjustment algorithm

DAA will adjust a BCD value that has had a carry occur between digits. There are two situations where this applies:

Most processor architectures maintain a status flag denoting when a byte has carried past its maximum value; many architectures also maintain a half-carry flag, that is set when the lower nybble of a byte carries into the upper nybble. The half-carry flag will be set by a BCD addition that causes a binary carry in the lower digit, so checking for this will satisfy the other half of the DAA check.

If the DAA check finds a digit that needs adjusting, the fix is simple: a further addition onto the nybble in question.

Adjustment of a nybble

0x08 + 0x03 = 0x0B ; Should be 0x11
0x09 + 0x05 = 0x0E ; Should be 0x14
0x09 + 0x08 = 0x11 ; Should be 0x17

In every case, the value is six away from where it should be, so the adjustment adds six to bring the value back into BCD. Applying this process to both nybbles yields the final DAA algorithm.

2-digit BCD decimal adjustment after addition

OLD_value = Value
OLD_carry = Carry from addition

# Check lower nybble
IF (Half-carry set by addition) OR (Lower nybble of Value > 9)
    ADD 6 to Value
FI

# Check upper nybble
# Upper nybble will be over 9 if original Value was over 0x99
IF(OLD_carry) OR (OLD_value > 0x99)
    ADD 0x60 to Value
    Carry = 1 # BCD value carry occurred
ELSE
    Carry = 0
FI

The DAA algoithm sets the carry flag based on whether the upper nybble overflowed; this allows DAA to be used on BCD values across multiple bytes, by employing addition-with-carry on any higher denominations.

Implementing DAA on AVR

Translating DAA from the algorithm detailed above results in the following AVR code.

AVR implementation of DAA

; Parameters: R16 = value to adjust
; Returns: R16 = Adjusted value
;          Carry flag set if adjustment caused BCD carry
DAA:
    push r16
    push r17
    push r18
    push r19

    push r16
    mov r17, r16
    mov r18, r16
    in r19, SREG
    andi r19, (1<<SREG_C)

    clc
    brhs DAA_adjlo
    andi r17, 0x0F
    cpi r17, 10
    brlo DAA_hi
DAA_adjlo:
    ldi r17, 6
    add r16, r17

DAA_hi:
    tst r19
    brne DAA_adjhi
    pop r17
    cpi r17, 0x9A
    brlo DAA_nadjhi
DAA_adjhi:
    ldi r17, 0x60
    add r16, r17
    sec
    rjmp DAA_end
DAA_nadjhi:
    clc

DAA_end:
    pop r19
    pop r18
    pop r17
    pop r16
    ret

Usage of the DAA routine for a two-byte BCD value stored in SRAM, would work like this:

Calling DAA across two BCD bytes

; Add BCD 57 to the value stored at SRAM:0x100
    ldi xl, 0x00
    ldi xh, 0x01

; Read in low byte, add 57 BCD, and store
    ld r16, x
    ldi r17, 0x57
    add r16, r17
    call DAA
    st x+, r16

; Read in high byte, add carry from low byte, and store
    ld r16, x
    clr r17
    adc r16, r17
    call DAA
    st x, r16

Other decimal adjustment routines

The Intel IA-32 instruction set also contains a routine for decimal adjustment after subtraction, which operates in a slightly different manner to that detailed above. Development of such a routine for AVR is beyond the scope of this article, but can be done in a similar vein to DAA by pulling the algorithm from the IA-32 Reference manual.

If this routine proves useful, or if you come across any bugs with its operation, please feel free to let me know.

Imran Nazar <tf@imrannazar.com>, Dec 2009. Code released into the public domain.