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
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.
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
It is in additions that cause a carry between digits that the problem appears. In the above example, the BCD numbers
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
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:
- 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.
Adjustment of a nybble
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
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
Usage of the DAA routine for a two-byte BCD value stored in SRAM, would work like this:
Calling DAA across two BCD bytes
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 <email@example.com>, Dec 2009. Code released into the public domain.
Article dated: 19th Dec 2009