# Binary-Coded Decimal Addition on Atmel AVR

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
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.

• Easier to calculate: A simple binary number can be held by the controller, which is very easy to increment. This forces the display code to iteratively divide the number down by ten, in order to extract the digits for display.
• Easier to display: A packed binary-coded decimal (BCD) number can be used instead to hold the counter; this simplifies the display logic, but incrementing the number requires an adjustment process to be run in order to correctly align the BCD segments.

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.

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.

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.

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

; 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.

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

• BCD carry: This occurs in a situation much like the one detailed above, where a result is too large to fit into a BCD digit but is still large enough for a binary nybble. Checking for this is simple: if the nybble has a value over 9, BCD carry has occurred.
• Binary carry: This will happen if a BCD digit addition result is not just larger than a BCD digit, but larger than 15: the nybble containing the BCD digit will itself carry, and end up with a value lower than 9. Results of this type would not be caught by the check for values over 9.

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.

```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.

```OLD_value = Value

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

# Check upper nybble
# Upper nybble will be over 9 if original Value was over 0x99
IF(OLD_carry) OR (OLD_value > 0x99)
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
andi r17, 0x0F
cpi r17, 10
brlo DAA_hi
ldi r17, 6

DAA_hi:
tst r19
pop r17
cpi r17, 0x9A
ldi r17, 0x60
sec
rjmp DAA_end
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

ld r16, x
ldi r17, 0x57
call DAA
st x+, r16

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