Decimal Arithmetic with BCD

Details

Although decimal hardware is rare, there are lots of reason to want to work in decimal in software. For example, binary often doesn't give results that are the same as a human would get doing manual arithmetic. For example, if an expression results in 0.1 in decimal this isn't exactly representable in fixed point binary. However, for integer arithmetic binary gives the same result as decimal arithmetic. A better reason for needing decimal is that this is what many sensors deliver to your interface.

Now available as a paperback or ebook from Amazon.

Applying C For The IoT With Linux

Contents

  1. C,IoT, POSIX & LINUX
  2. Kernel Mode, User Mode & SyscallProgram Execution
  3. Execution, Permissions & Systemd
  4. Signals & Exceptions
  5. Integer Arithmetic
  6. Fixed Point
  7. Floating Point
  8. File Descriptors
  9. The Pseudo-File System
  10. Graphics
  11. Sockets
  12. Threading
  13. Cores Atomics & Memory Management
  14. Interupts & Polling
  15. Assembler

For example, a sensor might naturally return some decimal digits to represent a temperature, or a numeric display might need to be fed decimal values. You can avoid decimal arithmetic by always converting to binary and then back to decimal as needed but in many cases it is simpler to stay with the representation the device provides. It is also instructive to see that in C and in low-level programming in general all we have are bit patterns and how you interpret them is up to you.

Binary Coded Decimal is very simple. The bit patterns 0000 to 1001 are used to code 0 to 9. These bit patterns can be stored one per byte or, packed as BCD, as two digits per byte. Four bits are often referred to as a nibble and so we use one nibble to store a digit. Notice that you are not using the full range of the nibble and often the unused values represent symbols such as plus or minus.

To convert a binary value to BCD all you have to do is extract the decimal digits. For example, starting with:

int myVal = 123;

you can get the least significant digit by taking the remainder on division by 10:

myBCD1 = myVal % 10;

The remainder of 123 after division by 10 is 3 and so myBCD1 now contains 3. All we now have to do is repeat after removing the least significant digit:

myVal = myVal / 10;
myBCD1 += (myVal % 10) << 4;

The shift by 4 bits is to move the digit into the next nibble. The next digit is extracted in the same way, but this time is shifted 8 bits to move it to the next nibble:

myVal = myVal / 10;
myBCD1 += (myVal % 10) << 8;

Now you have seen how this works, it is easy to convert it into a loop that will convert any positive binary value to BCD:

int s = 0;
int myBCD1=0;
while (myVal > 0) {
    myBCD1 += (myVal % 10) << s;
    s += 4;
    myVal = myVal / 10;
}
printf("%x\n", myBCD1);

It is worth remembering that to convert BCD to an ASCII char you simply have to add 0011 to the start of each nibble. You also have to unpack each nibble into a byte. One way to do this is to shift right and use a mask:

char myASCII[5] = {0};
int i=0;
while (myBCD1 > 0) {
    myASCII[3-i] = (myBCD1 & 0x0F) | 0x30;
    myBCD1 >>= 4;       
    i++;       
}    
printf("%s\n", myASCII);

To convert to binary you simply proceed as you would with a decimal number, but in this case extracting nibbles for each digit.

myVal=0;
int p=1;
while (myBCD1 > 0) {
   myVal += (myBCD1 & 0x0F)*p;
   myBCD1 >>= 4;       
   p=p*10;       
}
printf("%d\n", myVal);

BCD Arithmetic

Now we come to the difficult topic of how to perform BCD arithmetic. If you have a lot of arithmetic to do then the best solution is to convert to binary, do the arithmetic and then convert back. This has the advantage that you know how to work with binary and the disadvantage that, if it involves division, you might not get the same answer as a human.

In many cases, however, the arithmetic that you want to do is very simple. One way of doing BCD arithmetic is to unpack the nibbles into an array and then add nibbles one by one. The problem with this is that you have to take care of the decimal carries. For example, 9+1 gives you a nibble that isn't a decimal digit i.e. 10 or 1010 in binary or A in hex. To correct this you have to subtract 10 from this nibble and add one to the next nibble so performing a carry. That is, if you add the nibbles together you have to scan for values that are greater than 9 and from each you subtract 10 and add a carry to the next nibble. Notice that as 9+9 is 18 decimal or 0001 0010 you can even overflow 4 bits and so each nibble should be stored in its own byte.

Consider for a moment addition of just two BCD digits each one stored in a byte. For example:

   9  +     9  =   18
0x09  +  0x09  = 0x12

At this point you need to subtract 10 and carry 1 onto the next nibble. However, if you look, the addition has already put a 1 into the next nibble, it is only the original nibble that is wrong. The reason is that the carry 1 into the next highest nibble has actually carried 16 not 10 from the lower nibble - remember this is implemented as binary. To get the correct BCD we have to return 6 to the lower nibble.

   9  +     9  =   18
0x09  +  0x09  = 0x12 + 0x06 = 0x18

If you have implemented BCD arithmetic before, you might have wondered where the mysterious "6" comes from.

int result = myBCD1 + myBCD2;
if(result>9)result=result+6;

You can extend this method so that you can add multiple digits and then correct the result to BCD, but it isn't straightforward as you have to detect the binary carry between the nibbles and add 6 to the lower nibble whenever it has occurred.

If we have two packed BCD values in four byte unsigned ints then we can simply add them together:

unsigned int myBCD1 = 0x90000;
unsigned int myBCD2 = 0x90000;
int result = myBCD1 + myBCD2;

but the result will be incorrect in any nibble that generated a carry to the next nibble. We need to find out where the carries occur. This we can do because we already know that exclusive or (XOR) is addition without taking the carries into account. So:

(myBCD1 ^ myBCD2)

is the addition without carry. If we XOR this with the sum that did include a carry there will only be bits set where they differ, i.e bits that result from a carry:

(myBCD1 ^ myBCD2)^result

This gives a one at every bit that was generated by a carry, but we are only interested in carries from one nibble to the next and these can only be positioned at the first bit of the nibble. To pick just these out we have to use a mask:

int carry = (myBCD1 ^ myBCD2)^result & 0x011111110;

notice that the first nibble cannot have received a carry.

Now we have a carry which has a one in the first bit of any nibble that received a carry from the adjacent nibble. We need to create a mask with a 6 in each position that generated a carry and this we can do using a shift and OR:

int sixmask = (carry >> 2) | (carry >> 3);

Finally we can add the sixes into the result to correct it:

result += sixmask;

Notice that you cannot allow a carry in the final nibble - the result is an overflow.

You can extend this bit manipulation technique to long long types if you need more digits. You can also make it work for subtraction by using ten’s complement, see the next section.

Summary of Chapter That This Article Is Taken From

  • Integer arithmetic is achieved using a full adder. When implemented in software, integer addition is iterative.
  • Binary is not the only possible representation - Binary Coded Decimal is also common.
  • Implementing BCD arithmetic is surprising difficult to do efficiently.
  • There are different ways of representing negative numbers. Sign magnitude is common, but two’s-complement is preferable as it takes care of the sign automatically.
  • What happens when arithmetic results in a value that cannot be represented is a difficult topic. For unsigned arithmetic the standard defines that it should result in a rollover. For signed arithmetic overflow is undefined behavior.
  • Detecting overflow before it happens is an important task and there are many ways of doing the job. There are built-in functions in GCC, but if you don’t want to, or can’t, use them it is possible to test for overflow using conditionals.
  • To avoid problems with undefined behavior, you can always implement signed arithmetic using unsigned operators, or you can increase the precision so that overflow cannot occur.
  • In many cases the operating system will provide a software interrupt, or trap, that you can use to detect and handle signed overflow. In most cases you will also need to use some advanced C to implement a try-catch construct.
  • Although most of the problems are centered on signed overflow, it can be important to detect unsigned overflow.
  • Modular arithmetic is, in fact, what all integer arithmetic is. Integer division and the mod or remainder operator are very useful in general programming.
  • Detecting division by zero should be easy, but it is often difficult to detect it in a way that allows you to handle it in software.

 

 

 

 

comments powered by Disqus