How to convert a 128-bit integer to a decimal ascii string in C?

Question

I'm trying to convert a 128-bit unsigned integer stored as an array of 4 unsigned ints to the decimal string representation in C:

unsigned int src[] = { 0x12345678, 0x90abcdef, 0xfedcba90, 0x8765421 };
printf("%s", some_func(src)); // gives "53072739890371098123344"

(The input and output examples above are completely fictional; I have no idea what that input would produce.)

If I was going to hex, binary or octal, this would be a simple matter of masks and bit shifts to peel of the least significant characters. However, it seems to me that I need to do base-10 division. Unfortunately, I can't remember how to do that across multiple ints, and the system I'm using doesn't support data types larger than 32-bits, so using a 128-bit type is not possible. Using a different language is also out, and I'd rather avoid a big number library just for this one operation.

Answer 1

Division is not necessary:

#include <string.h>
#include <stdio.h>

typedef unsigned long uint32;

/* N[0] - contains least significant bits, N[3] - most significant */
char* Bin128ToDec(const uint32 N[4])
{
  // log10(x) = log2(x) / log2(10) ~= log2(x) / 3.322
  static char s[128 / 3 + 1 + 1];
  uint32 n[4];
  char* p = s;
  int i;

  memset(s, '0', sizeof(s) - 1);
  s[sizeof(s) - 1] = '\0';

  memcpy(n, N, sizeof(n));

  for (i = 0; i < 128; i++)
  {
    int j, carry;

    carry = (n[3] >= 0x80000000);
    // Shift n[] left, doubling it
    n[3] = ((n[3] << 1) & 0xFFFFFFFF) + (n[2] >= 0x80000000);
    n[2] = ((n[2] << 1) & 0xFFFFFFFF) + (n[1] >= 0x80000000);
    n[1] = ((n[1] << 1) & 0xFFFFFFFF) + (n[0] >= 0x80000000);
    n[0] = ((n[0] << 1) & 0xFFFFFFFF);

    // Add s[] to itself in decimal, doubling it
    for (j = sizeof(s) - 2; j >= 0; j--)
    {
      s[j] += s[j] - '0' + carry;

      carry = (s[j] > '9');

      if (carry)
      {
        s[j] -= 10;
      }
    }
  }

  while ((p[0] == '0') && (p < &s[sizeof(s) - 2]))
  {
    p++;
  }

  return p;
}

int main(void)
{
  static const uint32 testData[][4] =
  {
    { 0, 0, 0, 0 },
    { 1048576, 0, 0, 0 },
    { 0xFFFFFFFF, 0, 0, 0 },
    { 0, 1, 0, 0 },
    { 0x12345678, 0x90abcdef, 0xfedcba90, 0x8765421 }
  };
  printf("%s\n", Bin128ToDec(testData[0]));
  printf("%s\n", Bin128ToDec(testData[1]));
  printf("%s\n", Bin128ToDec(testData[2]));
  printf("%s\n", Bin128ToDec(testData[3]));
  printf("%s\n", Bin128ToDec(testData[4]));
  return 0;
}

Output:

0
1048576
4294967295
4294967296
11248221411398543556294285637029484152

Answer 2

Straightforward division base 2^32, prints decimal digits in reverse order, uses 64-bit arithmetic, complexity O(n) where n is the number of decimal digits in the representation:

#include <stdio.h>

unsigned int a [] = { 0x12345678, 0x12345678, 0x12345678, 0x12345678 };

/* 24197857161011715162171839636988778104 */

int
main ()
{
  unsigned long long d, r;

  do
    {
      r = a [0];

      d = r / 10;
      r = ((r - d * 10) << 32) + a [1];
      a [0] = d;

      d = r / 10;
      r = ((r - d * 10) << 32) + a [2];
      a [1] = d;

      d = r / 10;
      r = ((r - d * 10) << 32) + a [3];
      a [2] = d;

      d = r / 10;
      r = r - d * 10;
      a [3] = d;

      printf ("%d\n", (unsigned int) r);
    }
  while (a[0] || a[1] || a[2] || a[3]);

  return 0;
}

EDIT: Corrected the loop so it displays a 0 if the array a contains only zeros. Also, the array is read left to right, a[0] is most-significant, a[3] is least significant digits.

Answer 3

A slow but simple approach is to just printing digits from most significant to least significant using subtraction. Basically you need a function for checking if x >= y and another for computing x -= y when that is the case. Then you can start counting how many times you can subtract 10^38 (and this will be most significant digit), then how many times you can subtract 10^37 ... down to how many times you can subtract 1.

The following is a full implementation of this approach:

#include <stdio.h>

typedef unsigned ui128[4];

int ge128(ui128 a, ui128 b)
{
    int i = 3;
    while (i >= 0 && a[i] == b[i])
        --i;
    return i < 0 ? 1 : a[i] >= b[i];
}

void sub128(ui128 a, ui128 b)
{
    int i = 0;
    int borrow = 0;
    while (i < 4)
    {
        int next_borrow = (borrow && a[i] <= b[i]) || (!borrow && a[i] < b[i]);
        a[i] -= b[i] + borrow;
        borrow = next_borrow;
        i += 1;
    }
}

ui128 deci128[] = {{1u,0u,0u,0u},
                   {10u,0u,0u,0u},
                   {100u,0u,0u,0u},
                   {1000u,0u,0u,0u},
                   {10000u,0u,0u,0u},
                   {100000u,0u,0u,0u},
                   {1000000u,0u,0u,0u},
                   {10000000u,0u,0u,0u},
                   {100000000u,0u,0u,0u},
                   {1000000000u,0u,0u,0u},
                   {1410065408u,2u,0u,0u},
                   {1215752192u,23u,0u,0u},
                   {3567587328u,232u,0u,0u},
                   {1316134912u,2328u,0u,0u},
                   {276447232u,23283u,0u,0u},
                   {2764472320u,232830u,0u,0u},
                   {1874919424u,2328306u,0u,0u},
                   {1569325056u,23283064u,0u,0u},
                   {2808348672u,232830643u,0u,0u},
                   {2313682944u,2328306436u,0u,0u},
                   {1661992960u,1808227885u,5u,0u},
                   {3735027712u,902409669u,54u,0u},
                   {2990538752u,434162106u,542u,0u},
                   {4135583744u,46653770u,5421u,0u},
                   {2701131776u,466537709u,54210u,0u},
                   {1241513984u,370409800u,542101u,0u},
                   {3825205248u,3704098002u,5421010u,0u},
                   {3892314112u,2681241660u,54210108u,0u},
                   {268435456u,1042612833u,542101086u,0u},
                   {2684354560u,1836193738u,1126043566u,1u},
                   {1073741824u,1182068202u,2670501072u,12u},
                   {2147483648u,3230747430u,935206946u,126u},
                   {0u,2242703233u,762134875u,1262u},
                   {0u,952195850u,3326381459u,12621u},
                   {0u,932023908u,3199043520u,126217u},
                   {0u,730304488u,1925664130u,1262177u},
                   {0u,3008077584u,2076772117u,12621774u},
                   {0u,16004768u,3587851993u,126217744u},
                   {0u,160047680u,1518781562u,1262177448u}};

void print128(ui128 x)
{
    int i = 38;
    int z = 0;
    while (i >= 0)
    {
        int c = 0;
        while (ge128(x, deci128[i]))
        {
            c++; sub128(x, deci128[i]);
        }
        if (i==0 || z || c > 0)
        {
            z = 1; putchar('0' + c);
        }
        --i;
    }
}

int main(int argc, const char *argv[])
{
    ui128 test = { 0x12345678, 0x90abcdef, 0xfedcba90, 0x8765421 };
    print128(test);
    return 0;
}

That number in the problem text in decimal becomes

11248221411398543556294285637029484152

and Python agrees this is the correct value (this of course doesn't mean the code is correct!!! ;-) )

Answer 4

Same thing, but with 32-bit integer arithmetic:

#include <stdio.h>

unsigned short a [] = { 
  0x0876, 0x5421,
  0xfedc, 0xba90,
  0x90ab, 0xcdef,
  0x1234, 0x5678
};

int
main ()
{
  unsigned int d, r;

  do
    {
      r = a [0];

      d = r / 10;
      r = ((r - d * 10) << 16) + a [1];
      a [0] = d;

      d = r / 10;
      r = ((r - d * 10) << 16) + a [2];
      a [1] = d;

      d = r / 10;
      r = ((r - d * 10) << 16) + a [3];
      a [2] = d;

      d = r / 10;
      r = ((r - d * 10) << 16) + a [4];
      a [3] = d;

      d = r / 10;
      r = ((r - d * 10) << 16) + a [5];
      a [4] = d;

      d = r / 10;
      r = ((r - d * 10) << 16) + a [6];
      a [5] = d;

      d = r / 10;
      r = ((r - d * 10) << 16) + a [7];
      a [6] = d;

      d = r / 10;
      r = r - d * 10;
      a [7] = d;

      printf ("%d\n", r);
    }
  while (a[0] || a[1] || a[2] || a[3] || a [4] || a [5] || a[6] || a[7]);


  return 0;
}

Answer 5

@Alexey Frunze's method is easy but it's very slow. You should use @chill's 32-bit integer method above. Another easy method without any multiplication or division is double dabble. This may work slower than chill's algorithm but much faster than Alexey's one. After running you'll have a packed BCD of the decimal number

Answer 6

On github is an open source project (c++) which provides a class for a datatype uint265_t and uint128_t.

https://github.com/calccrypto/uint256_t

No, I' not affiliated with that project, but I was using it for such a purpose, but I guess it could be usefull for others as well.

Answer 7

You actually don't need to implement long division. You need to implement multiplication by a power of two, and addition. You have four uint_32. First convert each of them to a string. Multiply them by (2^32)^3, (2^32)^2, (2^32)^1, and (2^32)^0 respectively, then add them together. You don't need to do the base conversion, you just need to handle putting the four pieces together. You'll obviously need to make sure the strings can handle a number up to UINT_32_MAX*(2^32)^3.

Answer 8

Supposing you have a fast 32-bit multiplication and division the result can be computed 4 digits at a time by implementing a bigint division/modulo 10000 and then using (s)printf for output of digit groups.

This approach is also trivial to extend to higher (or even variable) precision...

#include <stdio.h>

typedef unsigned long bigint[4];

void print_bigint(bigint src)
{
    unsigned long int x[8];   // expanded version (16 bit per element)
    int result[12];           // 4 digits per element
    int done = 0;             // did we finish?
    int i = 0;                // digit group counter

    /* expand to 16-bit per element */
    x[0] = src[0] & 65535;
    x[1] = src[0] >> 16;
    x[2] = src[1] & 65535;
    x[3] = src[1] >> 16;
    x[4] = src[2] & 65535;
    x[5] = src[2] >> 16;
    x[6] = src[3] & 65535;
    x[7] = src[3] >> 16;

    while (!done)
    {
        done = 1;
        {
            unsigned long carry = 0;
            int j;
            for (j=7; j>=0; j--)
            {
                unsigned long d = (carry << 16) + x[j];
                x[j] = d / 10000;
                carry = d - x[j] * 10000;
                if (x[j]) done = 0;
            }
            result[i++] = carry;
        }
    }

    printf ("%i", result[--i]);
    while (i > 0)
    {
        printf("%04i", result[--i]);
    }
}

int main(int argc, const char *argv[])
{
    bigint tests[] = { { 0, 0, 0, 0 },
                       { 0xFFFFFFFFUL, 0, 0, 0 },
                       { 0, 1, 0, 0 },
                       { 0x12345678UL, 0x90abcdefUL, 0xfedcba90UL, 0x8765421UL } };
    {
        int i;
        for (i=0; i<4; i++)
        {
            print_bigint(tests[i]);
            printf("\n");
        }
    }
    return 0;
}