Algorithm for converting an arbitrarily long String representing a decimal number into a String representing a hexadecimal number

Question

I am currently working on a program in C17, which receives a string from the command line, lets call it st_in. I know that st_in will only contain chars in range [0x30, 0x39], thus represent a decimal number of arbitrary size. I want to convert this string into a string st_out which does represent the same value in hexadecimal, eg. f("123") would yield "7B". The caveat comes from the fact that st_in and st_out can be really big. So I need to convert them digitwise. Is there a standard way of doing it?

All my previous attempts at solving the problem lead me to very complex "ripple-back" ideas, which I can barely grasp conceptually, let alone write down in good ol' C. I also don't really know how to allocate the memory correctly (if n = strlen(st_in) I have found that the maximum number of digits would be ceil(n * log_2(10). But then I need to free just "some" of the memory if the string is shorter.

Answer 1

An algorithm is:

• Calculate a maximum length that might be needed for the output, including space for terminating null character.
• Initialize last to point to the end of that space.
• Initialize first to point one beyond last, indicating the output string is currently empty. (If first and last pointed to the same place, there would be one digit there. When first points beyond last, it means there are no digits yet.)
• While there is another input digit to process:
  • Convert the input digit from a decimal character to an integer in 0-9.
  • Using algorithm below, multiply the output string by ten and add the new input digit.
• Move the output string in positions first to last to the beginning of the allocated space (because it grew at the end and might not have reached the front, depending on how whether the maximum length was calculated exactly or not).
• Convert the output string from integers in 0-15 to hexadecimal characters.
• Write a null character to mark the end of the string.
• If desired, and the output length was not initially calculated exactly, reallocate the space to just fit.

To multiply the output string by ten and add the new input digit:

• Initialize carry to the current input digit, as an integer in 0-9.
• For each position p from last down to to first, inclusive:
  • Set carry to be 10 times the digit in position p plus carry. (carry is temporarily a larger amount than will be carried.)
  • Find the low hexadecimal digit of carry by taking the remainder modulo 16. Store that in position p.
  • Find the high hexadecimal digit of carry by dividing it by 16, with truncation.
• If carry is not zero, the output has grown left one digit. Decrement first by one and store carry at the new position.