Printing 64-bit decimal numbers in freestanding environment

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...

• 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. – Ben Steffan Aug 24 '18 at 13:47

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; 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>