Fast Binary to Radix Converter

The function fast_binary_to_bcd() converts a 32-bit (long unsigned int) to 11 digits of the specified radix (unsigned char). The specified radix may be 8, 10 or 16.

Two digits are compacted into each byte. The eight least significant digits are returned in R4...R7 so as to be compatible with Keil function return value standards for an unsigned long int. The three most significant digits are returned in R2 and R3.

fast_binary_to_radix() uses the currently selected register bank, the Data Pointer (DPL and DPH) and general purpose registers. No memory or stack is required.

The function is written in a Keil "shell" and may easily be incorporated into a Keil C51 based project. However, all the functionality is expressed in assembler and the function may easily be converted to work with any assembly language environment.

A test harness is also provided.

How fast_binary_to_radix() Works - Overview

fast_binary_to_radix() is invoked with the 32-bit binary value in registers R4...R7 where R4 is the most significant byte.

Digits are obtained by successive division of value by radix; on each division the remainder gives the next digit. The digits thus obtained give the least significant digit first.

The digits are stored in R2...R6. Obviously, this overlaps with the registers used to store value. However, as value is successively divided by radix, the number of bytes need to store it reduces, the function takes advantage of this fact by both using the freed bytes of value to store digits and by processing no more bytes of value than is actually required. This also helps to make fast_binary_to_radix() fast.

At the end of the function, the registers are rearranged to place the digits in their final places for return to the caller.

How fast_binary_to_bcd() Works - Detail

I would be the first to admit that just how this function works is not very clear, at least at first. Much clarity has been sacrificed for size and speed.

Conversion to radix 16 is a special case requiring trivial processing.

fast_binary_to_radix() uses register bank select bits in the PSW to generate pointers into the current register bank. This technique allows the function to remain compact while requiring no extra memory.

radix_pointer (R0) points to the bytes containing compact digits and is initialised to point to register R2.

hex_pointer (R1) points to the bytes containing value. hex_pointer is reinitialised for each division by 10 and starts out pointing to R4 or radix_pointer+1 whichever is greatest.

The division by radix works in much the same way as doing division by hand. The division process divides one hexadecimal digit (i.e. 4 bits) at a time. The remainder from division of one hexadecimal digit is carried forward to when the next digit is divided. Because the remainder from dividing a single hexadecimal digit cannot exceed 0x0F, it is always possible to do the division using an 8-bit by 8-bit divide at each stage. Two DIV instructions are required for each byte of value to be processed. This method of division is particularly fast.

Each division by radix yields one digit. The flag F0 (in the PSW) is used to provide two iterations that provide the two digits for one byte of compact digits.

The function iterates until the eight least significant digits have been generated. By this time, value has been divided by at least 16777216 (i.e. 8^8) and cannot be greater than 255. The final three digits are extracted by twice dividing the last byte of value (in R7) by radix.

Note that the value of the pointers radix_pointer and hex_pointer are used to control the number of iterations rather than having separate loop counters. This reduces the number of registers/memory locations that would otherwise be required.

Applications

The most obvious application is preparation of a 32-bit value for conversion to a sequence of ASCII characters of a specified radix. Once the 32-bit value has been converted to compact digits, it may readily be converted to a sequence of ASCII characters where the most significant digit can conveniently be generated first. fast_binary_to_radix() performs the required radix conversion quickly and without requiring any extra memory to store intermediate results.