Write an optimized C program to convert a base 16 number to its base 10 equivalent, without using the standard C libraries, i.e. don’t use scanf(“%x”). The program should allow the user to input the number. State any assumptions you made when writing the program. Use 23DA as a test number.
Assumptions:
1. I can skip checks for output errors.
2. I can use getchar()
and putchar().
3. getchar() returns character codes that fit in an
unsigned char.
4. An input character that is not a valid hex
digit indicates the end of input.
5. By optimized, you mean optimized for
execution time.
6. It is sufficient to convert numbers with 32
bits or less of precision (the minimum precision of a long allowed by ANSI C).
7. I can write a program (which is not overly
optimized and which uses fprintf()) that outputs a
header file for the conversion program.
8. ‘d’ – ‘0’ = d
for d in 0, 1, 2, … 9.
To convert hex
digit character codes to binary values, I use a (sparse) lookup table.
To avoid
dividing by 10, I use “8-bit BCD” arithmetic to accumulate the
number being converted. By 8-bit BCD, I
mean the following representation of a number:
|
|
most
significant |
|
|
least significant |
|
Low |
d4 |
d3 |
d2 |
d1 |
|
Middle |
d8 |
d7 |
d6 |
d5 |
|
High |
0 |
0 |
d10 |
d9 |
d1, d2,
… d10 are the decimal digits of the number from least to most
significant. Each row in this table
represents an unsigned long. Each cell
represents an 8-bit field. I use a
lookup table to implement the following function:
f(hex_digit, n) → 8-bit BCD representation of (hex_digit * 16n)
I add together
the 8-bit BCD representations of the digits (with their place value) in the hex
number. I add low to low, middle to
middle, and high to high, without renormalizing the 8-bit fields to decimal
digits. Since there are at most 8 hex
digits, each field will have a maximum value of
8 x 9 or 72 in the resulting sum.
Thus no field will overflow. I
then renormalize the 8-bit BCD sum and put the resulting digits into a byte
array (in one step). I use a lookup
table to do the division by 10. Since
each field has a maximum value of 72, and the maximum carry is 7, the
“divide by 10” lookup table has a maximum index of 79.
Here is the
program that generates the include file “hextodec.h”,
which contains the lookup tables described above.
#include <stdio.h>
#include <limits.h>
typedef unsigned long ulong;
/* Given a value, output (as text) the 8-bit BCD representation of
the
** value in the format "{low,middle,high}"
*/
void bcd8bit(FILE *fp, ulong val)
{
ulong
v;
unsigned i, shft;
fprintf(fp, "{");
for (i
= 0; ; i++)
{
v = 0;
for (shft = 0; shft < 32; shft += 8)
{
v += (val % 10) << shft;
val /= 10;
}
fprintf(fp, "0x%lx", v);
if (i == 2)
break;
fprintf(fp, ",");
}
fprintf(fp, "}");
}
int main()
{
int
i;
ulong
hdig, pow16;
int
d, r;
FILE *fp
= fopen("hextodec.h",
"w");
/* Output lookup table
from character codes to binary values of
** hex digits. If a character is not a hex digit, you get -1
when
** you look it up. */
fprintf(fp, "const signed char hex_val[]
= {\n");
#define X(CHAR, VAL) case
CHAR : fprintf(fp, #VAL);
break;
for (i
= 0; ; i++)
{
switch (i)
{
X('0', 0)
X('1', 1)
X('2', 2)
X('3', 3)
X('4', 4)
X('5', 5)
X('6', 6)
X('7', 7)
X('8', 8)
X('9', 9)
X('a', 10)
X('b', 11)
X('c', 12)
X('d', 13)
X('e', 14)
X('f', 15)
X('A', 10)
X('B', 11)
X('C', 12)
X('D', 13)
X('E', 14)
X('F', 15)
default: fprintf(fp, "-1");
}
if (i == UCHAR_MAX)
break;
fprintf(fp, ",\n");
}
fprintf(fp, "};\n\n");
fprintf(fp, "typedef unsigned long ulong;\n\n");
/* Output lookup table
that, given a hex digit and the number of digits
** to the right of it,
yields the place value of the digit as an 8-bit
** BCD value.
** usage: cvt_bcd[(digits to the right) * 15 + (digit value)] ->
** place value of digit as 8-bit BCD value.
*/
fprintf(fp,
"const struct cvt_bcd_S { ulong low, mid, hi; }
cvt_bcd[] = {\n");
for (pow16 = 1; ; pow16
<<= 4)
{
for (hdig = 0; ; hdig++)
{
bcd8bit(fp, hdig * pow16);
if (hdig == 15)
break;
fprintf(fp, ",\n");
}
if (pow16 ==
0x10000000L)
break;
fprintf(fp, ",\n");
}
fprintf(fp, "};\n");
/* Output lookup table
for dividing by 10.
** Usage: div10[N] -> { N / 10, N % 10 }
*/
fprintf(fp,
"const struct
div10_S { unsigned char div, rem; } div10[] =
{\n");
d = 0;
r = 0;
for ( ; ; )
{
fprintf(fp, "{%d,%d}", d, r);
if ((d == 7)
&& (r == 9))
break;
fprintf(fp, ",\n");
if (r == 9)
{
r = 0;
d++;
}
else
r++;
}
fprintf(fp, "};\n");
fclose(fp);
return(0);
}
Here is the
program that does the actual conversion.
#include <limits.h>
#include <stdio.h>
#include "hextodec.h"
int main()
{
/* Hex digits: binary encoded, [0] is most significant.
** Decimal digits: binary encoded, [0] is least significant. */
unsigned char dig[10];
/* Accumulator for number
to convert as 8-bit BCD. accum[0] is
** low, accum[1] is middle, accum[2] is
high. */
ulong
accum[3];
/* Scratch variables. */
unsigned char y;
int
c;
do
{
/* Read hex digits of
number to convert from standard input. */
{
signed char sb;
y = 0;
for ( ; ; )
{
c = getchar();
if ((c < 0)
|| (c >= UCHAR_MAX))
break;
sb = hex_val[c];
if (sb < 0)
break;
dig[y++] = sb;
if (y == 8)
break;
}
}
/* If a number was
read... */
if (y)
{
/* Accumulate the
value of each hex digit, without normalizing
** the sum. */
{
const struct cvt_bcd_S *p_cvt_pow = cvt_bcd, *p_cvt_dig;
accum[0] = 0;
accum[1] = 0;
accum[2] = 0;
for ( ; ; )
{
p_cvt_dig = p_cvt_pow + dig[--y];
accum[0] += p_cvt_dig->low;
accum[1] += p_cvt_dig->mid;
accum[2] += p_cvt_dig->hi;
if (y == 0)
break;
p_cvt_pow += 16;
}
}
{
ulong *p_accum = accum;
ulong *p_accum_end = accum + 2;
const struct
div10_S *p_div10;
unsigned char
carry;
putchar('\n');
/* Ignore high,
or high and middle, in accumulator if they are
** zero. */
while (!*p_accum_end)
if (p_accum_end == accum)
{
/* The
number being converted is zero. */
putchar('0');
goto ZERO;
}
else
p_accum_end--;
/* Normalize
accumulator, placing resulting digits in a
** byte array.
*/
y = 0;
carry = 0;
for ( ; ; )
{
p_div10 =
div10 + ((*p_accum & 0xFF) + carry);
dig[y++] = p_div10->rem;
carry = p_div10->div;
if (!(y
& 3))
{
p_accum++;
if (p_accum > p_accum_end)
break;
}
else
{
*p_accum >>= 8;
if ((!*p_accum) && (p_accum == p_accum_end))
break;
}
}
/* Output
decimal value. */
if (carry)
putchar(carry + '0');
do
putchar(dig[--y] + '0');
while (y);
ZERO:
putchar('\n');
}
}
}
while (c != EOF);
return(0);
}
23DA hex is
9178 decimal. I tested this solution
against the straightforward one on my (Pentium-based) PC, and this solution is
faster. This solution (when you count
the lookup tables) is much bigger, so performance is potentially dependent on
processor cache size.