A Fast, Multibyte Binary to Binary-Coded-Decimal Conversion Routine

Michael R McQuade
School of Electrical Engineering
Van Leer Building
Georgia Institute of Technology
Atlanla GA 30332

A problem which has confronted users of small computer systems over the years has been the incompatibility of the number representation required by output devices and that used for internal processing. Output devices used by the small systems need to receive binary-coded-decimal (BCD) or ASCII (American Standard Code for Information Interchange) data representations, while the microprocessor is most efficient when handling a straight binary number. Several solutions to the problem exist, and as would be expected, each has its own advantages and disadvantages.

Some users choose to initially store all numbers in their binary-coded-decimal representation and do all subsequent processing in this format. This has the advantage of easy and quick conversion of the numbers into the required output format. At worst, the binary-coded-decimal represented number must be converted to an ASCII format. This requires attaching a fixed 4-bit prefix to each binary-coded-decimal digit.

A disadvantage associated with this approach is that arithmetic operations take longer to perform, since the results must be decimally adjusted after each operation. Also, more memory is required to store the binary-coded-decimal form of the number than is required for its straight binary equivalent. A direct result of this increased memory requirement is the need to perform more memory-access operations to transfer the numbers into and out of the processor. Memory accesses are a very time-consuming operation.

For the users who choose a straight, binary-number representation for internal storage, the advantages of efficient memory utilization and straightforward arithmetic are gained. The question of how to convert the numbers to an acceptable output format for the display device still remains to be answered. This question basically reduces down to converting the binary numbers to binary-coded-decimal form.

About the Author

Mike McQuade is currently working towards a PhD degree in the Computer Architecture Laboratory at the School of Electrical Engineering at the Georgia Institute of Technology. He has instructed computer courses there, and has taught short microprocessor courses for the Institute of Eectrical and Electronics Engineers at both national and regional levels.

Methode of Conversion

There are three basic approaches in wide use. The first approach is to count the binary number down to 0 while incrementing its binary-coded-decimal counterpart up from 0 using modulo-10 counting. Modulo-10 counting performs a decimal-adjust operation after each incremental addition. This method is conceptually easy and requires a minimum of program code if the microprocessor has a decimal-adjust instruction. The counting method can, however, be very time-consuming if large numbers are being converted. For some applications this time penalty would be irrelevant (eg: if the output device is very slow when compared to the processor's cycle time). For a slow output device, any time savings realized by using a faster conversion routine usually has to be wasted in a wait loop.

The second approach is to use some form of table lookup routine. Assuming that the table is extensive enough, the lookup technique performs a very fast conversion. The drawback to this technique is that as the size of the numbers being handled gets larger, either a great deal of memory must be dedicated to the table, or some type of divide-with-remainder scheme must be implemented. The division scheme allows the table size to remain small, bu it causes the conversion time to increase. As was pointed out earlier, this may not be important. If the processor being used does not have a decimal-adjust instruction and the numbers encountered are not too large, this second method is very popular.

The third approach in converting from straight binary to binary-coded decimal is to use an algorithm based on the structure of the binary nurnber system. Given the binary number:

b_n b_n-1 b_n-2 ... b₂ b₁ b₀

where each of the bs can represent either a 1 or a 0, and b_n is the most significant bit, it can be expanded as:

b_n × 2ⁿ + b_n-1 × 2^n-1 + ... + b₁ × 2¹ + b₀× 2⁰

(Form I).

Form I is not conducive to an iterative-type binary to binary-coded decimal conversion routine, but can be rewritten as:

(...((b_n × 2) + b_n-1) × 2 + ... + b₁) × 2 + b₀

(Form II).

Form II contains only the decimal numbers 0, 1, and 2, which have the same representations in either straight binary ar binary-coded decimal. Straight binary and binary-coded-decimal representations of a number differ only for numbers greater than 9. While straight binary adheres strictly to position weighting in powers of 2, binary-coded decimal treats each decimal digit of the number independently and represents if as a 4-bit straight binary number.

If Form II is implemented using binary-coded-decimal arithmetic (performing a decimal adjust after each addition), the final result will be in binary-coded-decimal representation. Form II lends itself to an iterative-type implementation which allows it to be coded to easily accommodate any size number.

Carry	Auxiliary Carry	Correction Factor
0	0	10011010
0	1	10100000
1	0	11111010
1	1	00000000

Table 1: Correction factors in binary for the binary to trinary-caded-decimal (BCD) conversion algorithm.

Much has been said about performing a decimal-adjust operation when operating on numbers in the binary-coded-decimal format. When two binary-coded-decimal numbers are added by the processor's straight binary-adding accumulator, the result is not in binary-coded-decimal form. If is necessary to perform one more operation after each addition to correct for the fact that the processor's arithmetic logic is designed to add straight binary numbers. This extra operation is the decimal adjust. Many of the microprocessors on the market today have the decimal-adjust operation contained in their instruction sets.

If the processor being used does not contain a decimal-adjust instruction, it is still possible to perforrn a decimal-adjust operation. What must be done is to allow for the fact that a binary-coded-decimal number uses only ten of the sixteen possibie 4-bit cornbinations for each digit. If two binary-coded-decimal numbers are added together, and the least significant 4 bits of the result have a value greater than 9, then 6 must be added to the result. It is necessary to add 6 to skip over the six unallowed BCD bit combinations. The next 4 bits of the result are then tested, and 6 is added to them if necessary. This is repeated across the entire result.

A Better Method

The above method works in theory but is rather awkvvard to program. Let us examine a method based on the above theory which lends itself to straightforward programming. The method will be for 8-bit processors since they are the most popular. First it is necessary to keep track not only of the carry out of the eighth bit position, but also the carry from the fourth to fifth bit position. This second carry will be referred to as the auxiliary carry.

(1)	Add the binary number 01100110 to the first number.
(2)	Add the second number to the result generated in step 1. Keep track of both the carry and auxiliary carry from this addition. The carry generated here is the true carry to the next higher digit.
(3)	Based on the carry and auxiliary carry generated in step 2, add one of the correction factors shown in tabie 1 to the result of step 2.

The result has now been decimally adjusted.

The program shown in listing 1 and the flowchart shown in figure 1 provide an implementation of Form II using binary-coded-decimal arithmetic for the Intel 8080 microprocessor. It uses the decimal-adjust (DAA) instruction in the 8080's instruction set. A simple program shown in listing 2 converts data from binary-coded dedrnal to ASCII representation. The conversion from binary-coded-decimal to ASCII entails taking each of the two 4-bit, binary-coded-decimal digits, putting them in a byte, and appending the binary prefix 0011. Both programs are coded as subroutines, since these forms are usually more convenient to include in larger programs.

Listing 1: The multibyte binary to binary-coded-dedmal (BCD) conversion algarithm coded as a suhroutine for the 8080 microprocessor.
[8080 and Z80 source]

                ;THE SUBROUTINES ALWAYS SAVE THE CONTENTS OF REGISTER A
                ;D E H L AND THE STATUS FLAGS.  IF THE CONTENTS OF REGISTERS
                ;B C NEED TO BE SAVED THE CALLING ROUTINE MUST EXPLICITLY DO IT.
                
                ;******************BINARY TO BCD CONVERSION SUBROUTINE******************
                
                ;THE SUBROUTINE CONVERTS A MULTI-BYTE BINARY NUMBER TO ITS EQUIVALENT
                ;MULTI-BYTE BINARY CODED DECIMAL (BCD) REPRESENTATION.  THE BYTES
                ;OF BOTH NUMBERS ARE STORED IN MEMORY IN ASCENDING ORDER WITH
                ;THE LEAST SIGNIFICANT BYTE IN THE LOW END OF THE MEMORY STACK.   THE
                ;REQUIRED PARAMETERS NEEDED TO TO BE PASSED ARE:
                
                ;		H L GETS ADDRESS OF LOW ORDER BYTE OF BINARY NUMBER
                ;		D GETS NUMBER OF BYTES IN BINARY NUMBER
                ;		E GETS NUMBER OF BYTES IN BCD RESULT AREA
                
                ;THE SUBROUTINE ASSUMES THAT THE BINARY NUMBER WILL FIT IN THE SUPPLIED
                ;NUMBER OF BCD BYTES.  THE ROUTINE WILL FILL IN THE BCD BYTES WITH
                ;LEADING ZEROS IF NECESSARY.
                
                
 0000 F5        BNBC:	PUSH	PSW		;SAVE STATUS
 0001 4B        	MOV	C,E		;COPY # BCD BYTES TO C
 0002 E5        	PUSH	H		;SAVE ADDR OF BINARY # ON STACK
 0003 216400    	LXI	H,BCDNL		;LOAD HL WITH ADDR OF BCD
 0006 3600      LAB16:	MVI	M,0		;ZERO OUT MEMORY LOCATION
 0008 23        	INX	H		;INCREMENT HL
 0009 0D        	DCR	C		;DECREMENT C
 000A C20600    	JNZ	LAB16		;IF C=0 BRANCH FROM LOOP
 000D 7A        	MOV	A,D		;PUT # OF BINARY BYTES IN A
 000E 87        	ADD	A
 000F 87        	ADD	A		;MULTIPLY BY 8 TO GET # OF BITS
 0010 87        	ADD	A
 0011 47        	MOV	B,A		;STORE # OF BITS IN B
 0012 AF        	XRA	A		;SET CARRY TO ZERO
 0013 4A        MLOOP:	MOV	C,D		;PUT # OF BINARY BYTES IN C
 0014 E1        	POP	H		;RESTORE ADDR OF BINARY # TO HL
 0015 3B        	DCX	SP
 0016 3B        	DCX	SP		;LEAVE HL ON STACK
 0017 7E        RLOOP:	MOV	A,M		;PUT BINARY BYTE IN A
 0018 8F        	ADC	A		;SHIFT BYTE LEFT & FILL WITH CARRY
 0019 77        	MOV	M,A		;REPLACE BYTE
 001A 0D        	DCR	C		;DECREMENT C
 001B CA2200    	JZ	LAB17		;BRANCH FROM LOOP IF LAST BYTE
 001E 23        	INX	H		;INCREMENT HL
 001F C31700    	JMP	RLOOP		;JUMP TO START OF ROTATE LOOP
 0022 E1        LAB17:	POP	H		;RESTORE HL POINTER  TO LOW ORDER BINARY BYTE
 0023 3B        	DCX	SP
 0024 3B        	DCX	SP		;LEAVE HL ON STACK
 0025 D22900    	JNC	LAB18		;SKIP FILL WITH ONE IF NO CARRY
 0028 34        	INR	M		;FILL WITH ONE
 0029 4B        LAB18:	MOV	C,E		;PUT # OF BCD IN C
 002A 216400    	LXI	H,BCDNL		;LOAD HL WITH ADDR OF BCD
 002D 3E00      LAB20:	MVI	A,0		;ZERO OUT A
 002F 8E        	ADC	M		;ADD BCD BYTE TO A WITH CARRY
 0030 27        	DAA			;CONVERT RESULT TO BCD
 0031 77        	MOV	M,A		;SAVE NEW BCD BYTE
 0032 D23A00    	JNC	LAB19		;SKIP REST IF NO CARRY
 0035 23        	INX	H		;POINT TO NEXT BCD BYTE
 0036 0D        	DCR	C		;DECREMENT C
 0037 C22D00    	JNZ	LAB20		;IF C=0 LEAVE LOOP
 003A 4B        LAB19:	MOV	C,E		;PUT # OF BCD BYTE IN C
 003B 05        	DCR	B		;DECREMENT BIT COUNT
 003C CA4E00    	JZ	LAB40		;EXIT MAIN LOOP IF COUNT = 0
 003F 216400    	LXI	H,BCDNL		;LOAD HL WITH ADDR OF BCD
                				;CARRY=0 ENTERING NEXT LOOP WHICH
                				;MULTIPLIES BCD # BY TWO
 0042 7E        LAB21:	MOV	A,M		;PUT BCD BYTE IN A
 0043 8E        	ADC	M		;ADD BCD BYTE TO ITSELF WITH CARRY
 0044 27        	DAA			;CONVERT RESULT TO BCD
 0045 77        	MOV	M,A		;SAVE NEW BCD BYTE
 0046 23        	INX	H		;POINT TO NEXT BCD BYTE
 0047 0D        	DCR	C		;DECREMENT C
 0048 C24200    	JNZ	LAB21		;IF C=0 LEAVE LOOP
 004B C31300    	JMP	MLOOP		;DO FOR ALL BITS OF BINARY #
 004E E1        LAB40:	POP	H		;RESTORE HL
 004F F1        	POP	PSW		;RESTORE STATUS
 0050 C9        	RET			;RETURN

Figure 1: Flowchart of the algorithm for the binary to binary-coded-decimal (BCD) conversion subroutine.

The binary-to-binary-coded-decimal subroutine of listing 1 requires contiguous memory locations to hold the binary-coded-decimal result. The address of the memory location for the low-order byte of the binary-coded-decimal number has been labeled BCDNL (binary-coded-decimal number location) in the subroutine. The number is ordered upwards in memory. Register E must contain the number of bytes in the binary-coded-decimal number when the subroutine is called. If more bytes are specified than are needed, the extra will be filled with leading zeros.

The other parameters which must be passed to the subroutine are the number of bytes in the binary number and the address of the low-order byte of the binary number. The number of bytes in the binary number is to be in register D, while the address of the low-order byte is in register pair HL. The binary number is assumed to be stored in memory using the same convention as the binary-coded-decimal number. The more significant bytes are found at increasing memory addresses.

By having register pair HL point to the binary number, the routine can be used to convert all binary numbers required by the user's program without moving them to a specific location. All results are put in the same location, since this is temporary storage needed only until the number is sent to the display device.

Listing 2: A subroutine to convert a single-byte, 2-digit, binary-coded-decimal number to two single-byte ASCII characters, coded for the 8080 microprocessor.
[8080 and Z80 source]

                ;******************BCD TO ASCII SUBROUTINE******************
                
                ;THE SUBROUTINE TAKES A TWO DIGIT BCD NUMBER IN MEMORY POINTED TO BY
                ;HL AND CONVERTS IT TO ASCII.  THE MOST SIGNIFICANT DIGIT IS PUT
                ;IN REGISTER B WHILE THE LEAST SIGNIFICANT DIGIT IS PUT IN REGISTER C.
                
 0051 F5        ASCII:	PUSH	PSW		;SAVE STATUS
 0052 3E0F      	MVI	A,00001111B	;PUT LEAST SIGNIFICANT DIGIT MASK IN A
 0054 A6        	ANA	M		;MASK OFF LEAST SIGNIFICANT DIGIT
 0055 F630      	ORI	00110000B	;CONVERT TO ASCII
 0057 4F        	MOV	C,A		;PUT IN REG C
 0058 3EF0      	MVI	A,11110000B	;PUT MOST SIGNIFICANT DIGIT MASK IN A
 005A A6        	ANA	M		;MASK OFF MOST SIGNIFICANT DIGIT
 005B 0F        	RRC
 005C 0F        	RRC
 005D 0F        	RRC
 005E 0F        	RRC			;ROTATE RIGHT FOUR PLACES
 005F F630      	ORI	00110000B	;CONVERT TO ASCII
 0061 47        	MOV	B,A		;PUT IN REG B
 0062 F1        	POP	PSW		;RESTORE STATUS
 0063 C9        	RET			;RETURN
 0064           BCDNL:	DS	31		;START OF BCD NUMBER
 0083           	END

[Complete 8080 and Z80 source]

The binary to binary-coded-decimal conversion subroutine provided can handle binary numbers of any length up to and including 31 bytes. This corresponds to a decimal number in excess of 4.5 × 10⁷⁵ with a full 75 significant digits. This should be adequate to handle any physical quantity encountered. To establish a reference, it is only about 1.5 × 10²¹ angstroms from the earth to the sun. (An angstrom is one ten-billionth of a meter, that is 1/10⁹, and is normally used to measure the wavelength of light.)

The routines provided have been tested using a high-speed line printer as an output device. The routines were fast enough to allow the line printer not to wait when being sent a stream of 6-digit numbers. While the routines have been tested and were fast enough for the desired applications, an extensive effort was not made to eliminate every unneeded processor cycle. The object code provided in listings 1 and 2 will also execute on an Intel 8085 or a Zilog Z80 microprocessor.