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.