Convert Decimal to Hex when no datatype can hold the full number

Question

This is an almost exact duplicate of my own question a few weeks ago.

http://stackoverflow.com/questions/1143302/convert-hex-to-decimal-when-no-datatype-can-hold-the-full-number

This time, it is the reverse. I have the number (in a handy null terminated string) and I need the bytes that make this number. However, I am working in a 32 bits architecture for a micro controller, therefore I don't have the possibility of using the atoi, as the number is larger than 32 bits.

Does anyone have an idea on how to reverse the algorithm provided in the first link, as to get back the original result? My modulo arithmetic skills are failing me.

Quick Example: 155.207.231.135 to 0x[24][23][12][66][9F] (the brackets separate the bytes)

Answer 1

You'll need assembler for this one. Pseudocode:

int low = 0 // lower 32 bit
int high = 0 // higher 32 bit

for (int i=0; i<string.length(); i++) {
    int digit = string.get(i) - '0';
    int a = low;
    int b = high;
    a <<= 1; b += overflow;             // *2
    a <<= 1; b += overflow;             // *4
    a += low; b += overflow; b += high; // *5
    a <<= 1; b += overflow;             // *10
    a += digit; b += overflow;          // +digit
    low = a; high = b;
}

So basically, you create a 64bit register using two 32bit ints. For each loop, you:

    value *= 10 + digit;

Afterwards, you only need to skip the 0 bytes at the beginning of the resulting value to get the bytes you seek.

Answer 2

You can do something similar to BigInt division.

a = atoi of lower 7 decimal digits
b = atoi of remaining upper decimal digits


for (int i = 0; i < 5; i++)
{
    a += 10000000 * (b % 256);
    b /= 256;
    Result[i] = a % 256;
    a /= 256;
}

Answer 3

Just parse the string from left to right, multiplying the previous result by ten and adding the digit.

Here's some code in C# to show the concept. First two methods to to math on an array:

static void Mul(byte[] data, int num) {
   int n = 0;
   for (int i = data.Length - 1; i >= 0; i--) {
      n += (int)data[i] * num;
      data[i] = (byte)n;
      n >>= 8;
   }
}

static void Add(byte[] data, int num) {
   for (int i = data.Length - 1; num > 0; i-- ) {
      num += (int)data[i];
      data[i] = (byte)num;
      num >>= 8;
   }
}

Then you just do:

string s = "155207231135";
byte[] result = new byte[16];
foreach (char c in s) {
   Mul(result, 10);
   Add(result, c - '0');
}

The result is in the result array, padded with zero bytes to the left.

It shouldn't bee to hard to translate to C... :)