A General Purpose BCD-To-Binary Routine
Marvin L. De Jong
Department of Mathematics-Physics
The School of the Ozarks
Pt. Lookout, MO
A number of routines have been published^{1,2,3} that will convert either a two-digit number or a four-digit number in BCD code to a binary number, and Butterfield^{4} has published a routine to handle a six-digit BCD number. The routine described here can be easily modified to handle any number of BCD digits. It is a 6502 assembly language interpretation of an algorithm found in Peatman's^{5} book. The BCD-to-binary routine assumes its importance from the fact that human beings usually input numbers to a computer in a decimal representation. A number of scientific instruments have BCD outputs that may be interfaced to a microcomputer, requiring some kind of conversion routine before the data from such a device can be processed. Finally, if you want to interface some of the calculator chips to a microprocessor in order to do more complex arithmetic, you will very likely need a BCD-to-binary routine somewhere in your software. A 6502 assembly language routine to go the other way (binary-to-BCD) can be found as a subroutine in reference six at the end of this article.
The BCD-to-binary routine is based on a familiar technique for converting a base-ten number to a base-two number. The decimal number is successively divided by two, and the remainders are noted as either a one or a zero. Each division gives the next more significant binary digit or bit. Example 1 illustrates the process.
Example 1. Convert 59_{ten} to a binary number.
Solution: Successively divide 59_{ten} by two, with the divisions beginning from the right and proceeding to the left.
Referring to Example 1 it can be seen that the algorithm requires that the BCD number be successively divided by two and the remainders are saved to become the binary number. The first division remainder is the least significant bit, while the remainder from the last division is the most significant bit. If in Example 1 we wanted to convert 59_{ten} to an eight-bit binary number, namely 0011 1011, we would simply perform two more divisions than shown, providing the two leading zeros in the eight-bit representation.
If you are mildly familiar with BCD numbers you will recall that each digit requires four bits (or one nibble). So an eight-digit decimal number requires four memory locations. Conversely, four memory locations can represent a decimal number as large as 99999999, which is more easily expressed as 10^{8} -1. Question: How many bits are needed to represent a given number of decimal digits? Let N be the largest number of decimal digits that we need for our particular application, so the largest decimal number is (10^{N}-1). Let n be the number of binary digits (bits) needed to represent the same number. By analogy, the largest binary number that can be represented by n bits is (2^{n}-1). Since we wish to represent the same number, we may equate (10^{N}-1) and (2^{n}-1) and then solve for n. Thus, with some mathematical magic, the answer to the question posed above is
N = N/log 2 = N/0.30103
where a base ten logarithm is implied.
If N = 8 then n = 26.6 which becomes n = 27 when rounded upward (fractional numbers of bits are not allowed as answers for this problem). Twenty-seven bits can be handled quite nicely by four bytes, but please do not create your own theorem that the number of memory locations needed to represent a number in binary is equal to the number of memory locations to represent the same number in binary-coded decimal (BCD). Use the equation, and be sure to allocate enough memory to handle the number in either binary or BCD representations. Note that, in the program described by Listing 1, we assume an eight-digit decimal number is being converted to a binary number that will also be stored in four memory locations. The program is easily modified to handle situations where the number of memory locations needed for the BCD number is different than the number of memory locations needed for the binary number. Using the immortal words of many authors, "we leave this problem for the student."
So we know how many memory locations to assign to represent the number, and we have a simple algorithm (divide by two and store the remainder) to perform the conversion. Enter some corollary to Murphy's Laws: "nothing is as simple as it seems." Dividing by two is neat and easy for a binary number: successive shifts to the right (LSR or ROR) give successive divisions by two. Dividing by two is considerably more complex for a BCD number. Fortunately, Peatman^{5} has pointed out a few tricks that accomplish division-by-two for a BCD number.
The eight bit "weights" in a byte of memory that represent a binary number are 1, 2, 4, 8, 16, 32, 64, and 128, proceeding from the right-most bit to the left-most bit. Clearly, shifting the number to the right divides each bit weight by two. That is why an LSR or an ROR instruction may be used to divide a binary number by two. However, if the same memory location represents a BCD number, then the bit weights are 1, 2, 4, 8, 10, 20, 40, 80. consequently, a shift-right or a rotate-right instruction results in division-by-two only for bits zero, one, two, three, five, six, and seven. Shifting bit four (with a weight of ten) to the right changes its weight to eight. Eight is three more than five, the number you usually get when you divide ten by two. So, the trick to dividing a BCD number by two is to shift right or rotate right as usual, but if a one is shifted from bit four to bit three, then you must subtract three from the shifted-right result to get the correct answer. That's it folks. I wish I could say it was my idea, but I found it in Peatman's^{5} book.
If the BCD number is to be represented by several bytes, an added complication occurs. Bit seven in the least-significant byte has a weight of 80. Bit zero in the next most significant byte has a weight of 100. Clearly, shifting a one from bit zero of this byte to bit seven of the least-significant byte does not result in a division-by-two because 100/2 is not 80. However, if we subtract 30 after the shift we do get the correct answer. When performing a divide-by-two operation on a multi-byte BCD number, each byte in the number must be tested to see if a one was shifted into either bit three or bit seven, and then the appropriate remedies must be applied if the tests are positive. In short, if a one is shifted into the most-significant bit position of any of the N nibbles used to represent the N digits in BCD, then the nibble must be corrected by subtracting three.
One other point remains to be made. From Example 1 it is clear that we are interested in the remainder after division-by-two. When dividing by two, the remainder is either zero (even dividend) or one (odd dividend). The remainder will be found in the carry flag after a shift-right operation.
Although the comments should make most of the routine understandable, a brief explanation follows. The first instruction in Listing 1 is not needed if the program is already in the binary mode, in which case the routine starts by clearing the locations used to store the binary number. Rather than inserting some kind of loop counter to keep track of the number of divisions-by-two (refer to Example 1), the carry is set by the instruction location at $0D0A, and the remainders are rotated into the binary number until the carry bit that was initially set has rotated through the binary number and into the carry flag once more. Thus, the conversion stops at the BCS OUT instruction at location $0D12. The division-by-two routine takes up the remainder of the program. Note that the carry flag holds the remainder, and it is stored on the stack while the division-by-two routine is finished, after which it is rotated into the binary number in the RETURN loop.
Very likely some improvements in the speed of the routine could be made. In most cases the number of bytes needed for the binary number will be sufficiently close to the number of bytes occupied by the BCD number that no modification will be needed on that score. Remember, BYTE is the twos complement of the number of bytes used to represent the BCD number and the binary number. The BCD number is stored in locations $0000 - $0003 in Listing 1, in the sense that the least-significant digit is in the low-order nibble of location $0003 and the most-significant digit is in the high-order nibble of location $0000. These locations must be filled before the routine is called.
REFERENCES
1. Programming and Interfacing the 6502, With Experiments, De Jong, Marvin L., Howard W. Sams & Co., Inc., Indianapolis, 1980, p 129.
2. 6502 Assembly Language Programming, Leventhal, Lance A., Osborne/McGraw-Hill, Inc., Berkeley, 1979, p 7-9.
3. 6502 Software Design, Scanlon, Leo J., Howard W. Sams & Co., Inc., Indianapolis, 1980, p 147.
4. "Multi-Mode Adder," Butterfield, Jim, 6502 User Notes, No. 13, p 23.
5. Microcomputer-Based Design, Peatman, John B., McGraw Hill, New York, 1977, p 400.
6. "A Floating-Point Binary to BCD Routine," De Jong, Marvin L., COMPUTE!, 1981, in press.
BCDNUM = $0000; | Base address of the BCD number to be converted to binary. The most-significant digit of an N digit BCD number is in the high-order nibble of BCDNUM. |
BINUM = $0010; | Base address of the binary number whose most-significant byte will be in BINUM. |
BYTE = $FC; | Twos complement of the number of bytes needed to hold the BCD number; in this program four bytes ($0000 - $0003) are used. |
$ 0D00 D8 | START | CLD | Clear decimal mode. |
0D01 A9 00 | LDA #00 | Clear locations that will hold the binary number. | |
0D03 A2 FC | LDX #BYTE | ||
0D05 95 14 | BACK | STA BINUM + 4,X | |
0D07 E8 | INX | ||
0D08 D0 FB | BNEBACK | Locations have been cleared. | |
0D0A 38 | SEC | ||
0D0B A2 FC | THERE | LDX # BYTE | Rotate the binary number right, moving the remainder from the BCD division into the binary number. |
0D0D 76 14 | RETURN | ROR BINUM + 4, X | |
0D0F E8 | INX | ||
0D10 D0 FB | BNE RETURN | ||
0D12 B0 2B | BCS OUT | If the carry is set, the conversion is complete. | |
0D14 A2 FC | LDX #BYTE | ||
0D16 76 04 | AGAIN | ROR BCDNUM + 4,X | Start the division-by-two by shifting BCD number right. |
0D18 E8 | INX | ||
0D19 D0 FB | BNE AGAIN | Remainder will be in carry flag so save it on the stack. | |
0D1B 08 | PHP | ||
0D1C A2 FC | LDX # BYTE | Test bit three of each byte to see if a one was shifted in. | |
0D1E 38 | SEC | ||
0D1F B5 04 | LAKE | LDA BCDNUM+ 4,X | |
0D21 29 08 | AND #08 | If so, subtract three. | |
0D23 F0 06 | BEQ FORWD | If not, no correction needed, so test bit seven of each byte to see if a one was shifted in. | |
0D25 B5 04 | LDA BCDNUM + 4,X | ||
0D27 E9 03 | SBC #03 | ||
0D29 95 04 | STA BCDNUM + 4,X | ||
0D2B B5 04 | FORWD | LDA BCDNUM + 4,X | Here bit seven is checked. |
0D2D 29 80 | AND # $80 | ||
0D2F F0 06 | BEQ ARND | No correction. | |
0D31 B5 04 | LDA BCDNUM + 4,X | Correction: subtract 30. | |
0D33 E9 30 | SBC #$30 | ||
0D35 95 04 | STA BCDNUM + 4,X | ||
0D37 E8 | ARND | INX | |
0D38 D0 E5 | BNE LAKE | Repeat for all N bytes. | |
0D3A 28 | PLP | Get the carry back because it held the remainder. | |
0D3B B0 CE | BCC THERE | ||
0D3D 90 CC | BCC THERE | Go back and put it in the binary number. Then finish. | |
0D3F 60 | OUT | RTS |