2
\$\begingroup\$

I need to print signed 64-bit numbers in decimal form. Program runs in freestanding environment (no C library available, libgcc may be unavailable too, or may not work correctly). So I can't use printf(3) function.

I'am trying to write function, which will be able to convert number from binary form (int64_t) to ascii. Simple solution is to divide number by 10, and use remainder as next digit (from left to right, iteratively).

Unfortunately, processor doesn't have 64 bit division, and I can't rely on libgcc in that (__udivdi3 function). So I invented other way to perform binary->decimal conversion, by using binary coded decimal (BCD) numbers. First I convert binary number to BCD form (bit by bit, need 64 iterations, and need to sum BCD numbers), then convert BCD to ASCII.

Source code is following:

/*static*/ void _print_dec(intmax_t num)
{
    char *p;
    char buf[24 /* > log10(2^64) */];
    uint_fast8_t r;
    uint64_t n = num < 0 ? -num : +num;

    uint_fast16_t result_h = 0, digit_h = 0;
    uint64_t result = 0, digit = 1;
    while (n != 0)
    {
        /* sum bcd numbers: r = a + b, where r should be L-value  */
        #define BCD_ADD(type, r, a, b) do { \
            type t1 = a + (type)(0x6666666666666666 & ((type)-1 >> 4)), t2 = t1 ^ b; \
            t1 += b, t2 = ~(t1 ^ t2) & (type)0x1111111111111110; r = t1 - (t2>>2 | t2>>3); \
        } while (0);

        /* this macro computes rh:rl = ah:al + bh:bl (sum of compound BCD number), rh:rl should be L-value */
        #define BCD_ADD_COMPOUND(type_h, type, rh, rl, ah, al, bh, bl) do { \
            uint_fast8_t c = 0; \
            type t1 = al, t2 = bl; \
            BCD_ADD(type, rl, al, bl); \
            c = rl >> (sizeof(type)*CHAR_BIT-4); \
            BCD_ADD(type_h, rh, ah, bh); \
            if (c >= 10 || (rl < t1 && rl < t2)) { \
                rl = (rl & ((type)-1 >> 4)) | ((c - 10ULL) << (sizeof(type)*CHAR_BIT-4)); \
                BCD_ADD(type_h, rh, rh, 1); \
            } \
        } while (0)

        if (n & 1)
            BCD_ADD_COMPOUND(uint_fast16_t, uint64_t, result_h, result, result_h, result, digit_h, digit);

        BCD_ADD_COMPOUND(uint_fast16_t, uint64_t, digit_h, digit, digit_h, digit, digit_h, digit);
        n >>= 1;
    }

    p = &buf[sizeof(buf) - 1];
    *p = 0;
    do {
        r = result & 0x0f;
        *--p = r + '0';
        result = (result >> 4) | ((uint64_t)(result_h & 0x0f) << (sizeof(uint64_t)*CHAR_BIT-4));
        result_h = result_h >> 4;

    } while (result_h != 0 || result != 0);

    if (num < 0) *--p = '-';
    print_cstr(p);
}
#define print_dec(num) DECL_FUNC(_print_dec, num)

I hope, that somebody suggests me some improvements...

\$\endgroup\$
  • 8
    \$\begingroup\$ Hello and welcome to Code Review! Does this code work correctly? Your question is a little unclear in that regard. Also, it would be nice of you to expand your code into a minimal verifiable example, i.e. a small program that can be compiled and tested by us to make sure your code actually compiles and works. \$\endgroup\$ – Ben Steffan Aug 24 '18 at 13:47
3
\$\begingroup\$

How can I print 64-bit decimal numbers in freestanding environment?
suggests me some improvements...

Create test cases

Post lacks a good way to assess its correctness. Since the goal is to print rather than form a string, that is later printed, (a better function IMO), we will do things the simply, but a bit the hard way and visually compare output.

Test case code

#include <inttypes.h>
#include <limits.h>
#include <stdint.h>
#include <stdio.h>

void print_uint64_dec(uint64_t u) {
  if (u >= 10) {
    uint64_t udiv10 = u/10;
    u %= 10;
    print_uint64_dec(udiv10);
  }
  putchar((int)u + '0');
}

void print_int64_dec(int64_t i) {
  uint64_t u = (uint64_t) i;
  if (i < 0) {
    putchar('-');
    u = -u;
  }
  print_uint64_dec(u);
}

int main(void) {
  int64_t ia[] = {INT64_MIN + 1, 0, 10, INT64_MAX/2, INT64_MAX - 1};
  for (size_t index = 0; index< sizeof ia/sizeof ia[0]; index++) {
    int64_t i = ia[index];
    print_int64_dec(i-1); putchar('\n');
    print_int64_dec(i+0); putchar('\n');
    print_int64_dec(i+1); putchar('\n');
  }
}

And its output:

-9223372036854775808
-9223372036854775807
-9223372036854775806
-1
0
1
9
10
11
4611686018427387902
4611686018427387903
4611686018427387904
9223372036854775805
9223372036854775806
9223372036854775807

OP code produced the same results.


Plan for the future

"processor doesn't have 64 bit division, and I can't rely on libgcc" --> accepting this as a given, this curious restriction could easily be removed later. To that end, recommend to encapsulate this specialized code - and only the specialized part needed - the divide and mod of a int64_t, without the print part.

Something like

static unsigned mod10(uint64_t *u) {
  uint64_t dividend = *u;
  uint64_t quo = 0;
  uint64_t div = 0xA000000000000000; //largest shifted 10
  while (div >= 10) {
    quo <<= 1; // quo *= 2;
    if (dividend >= div) {
      dividend -= div;
      quo++;
    }
    div >>= 1;
  }
  *u = quo;
  return (unsigned) dividend;
}

void print_uint64_dec(uint64_t u) {
  if (u >= 10) {
    #if CURIOUS_CODE_NEEDED
      uint64_t udiv10 = u;
      u = mod10(&udiv10);
    #else
      uint64_t udiv10 = u/10;
      u %= 10;
    #endif
    print_uint64_dec(udiv10);
  }
  putchar((int)u + '0');
}

Simplify

I just had too much trouble following the "invented other way". I recommend to re-write to only replace the missing /10, mod 10 functionality in a stand-alone function. When a target platform lacks standard functionality, do not entangle your fill-in-the-gap code with the rest of user code. Keep them separate.


Minor - Use consistent types

Code converts intmax_t to uint64_t as if intmax_t is always a 64-bit type. (u)intmax_t is at least a 64-bit type. Choose (u)intmax_t or (u)int64_t.

Minor - Avoid UB

intmax_t num ... -num is UB when num == INTMAX_MIN. Simply enough to fix. Negate an unsigned type

// uint64_t n = num < 0 ? -num : +num;
uint64_t n = num;
if (num < 0) n = -n;
// OR
uint64_t n = num < 0 ? -(uintmax_t)num : num;
// Or various other approaches.

Minor - Missing headers

I needed the below to compile your code.

#include <limits.h>
#include <stdint.h>
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.