Fast cycling through decimal digits for printing (embedded)

Question

In my FW for real-time embedded processor I need formatted print of decimal number. Standard printf/sprintf are not available in toolchain, so I need implement it myself.

I used naive approach of dividing by tens and taking remainder. But my target processor doesn't support division natively and software implementation take very long time (more than 200us) to compute. I wonder if there is quick way to fetch decimal digits from a number without division?

char* os_prn_decimal(char* outBuf, const char* end, uint32 v)
{
    uint32 dgtIdx = 1000000000;

    do
    {
        uint8 dgt = (uint8)(v / dgtIdx);

        *outBuf = dgt + '0';
        ++outBuf;

       v = v % dgtIdx;
        dgtIdx /= 10;
    } while (outBuf < end && dgtIdx > 0);
    return outBuf;
}

Answer 1

Your solution generates the digits in the right order directly, but at a cost of a variable divide (v / dgtIdx), a variable modulo (which has the same or greater cost than a divide), and a divide by 10. That is three expensive operations.

It may be less expensive to generate the digits from the least-significant digit first, then reverse the digits after. That will then require only a divide by 10 and a modulo 10 operation. Using the solution at Divide by 10 using bit shifts? and modifying it to obtain the remainder in the same operation as the quotient:

uint32_t div10_rem( uint32_t dividend, int* remainder )
{
    uint32_t quotient = (uint32_t)((0x1999999Aull * dividend) >> 32) ;
    *remainder = dividend - (quotient * 10) ;

    return quotient ;
}

Then the conversion to a displayable decimal string might be:

char* int2dec( uint32_t val, char* buffer )
{
    char reverse_digits[10] = {0} ;
    uint32_t u = val ;
    size_t digit_count = 0 ;

    while( u > 0 )
    {
        int d = 0 ;
        u = div10_rem( u, &d ) ;
        reverse_digits[digit_count] = d + '0' ;
        digit_count++ ;
    }

    buffer[digit_count] = '\0' ;
    size_t i = 0 ;
    for( size_t i = 0; i < digit_count; i++ )
    {
        buffer[i] = reverse_digits[digit_count - i - 1] ;
    }

    return buffer ;
}

Then an example usage:

    char buffer[11] ;
    printf( "%s", int2dec( val, buffer) ) ;

It is possible to avoid the digit reversal if a static buffer is suitable:

#define MAX_DIGITS 10
const char* int2dec( uint32_t val )
{
    static char digits[MAX_DIGITS + 1] = {0} ;
    uint32_t u = val ;
    size_t digit_index = MAX_DIGITS - 1 ;

    while( u > 0 )
    {
        int d = 0 ;
        u = div10_rem( u, &d ) ;
        digits[digit_index] = d + '0' ;
        digit_index-- ;
    }

    return &digits[digit_index + 1] ;
}

Then, for example:

    printf( "%s", int2dec( val ) ) ;

Answer 2

A hint from daShier helped me to rectify my googling and I found this article https://forum.arduino.cc/index.php?topic=167414.0 that describes interesting approach to division by 10, which provides both quotient and modulo. Best part of it is complete lack of multiplications, divisions and cycles.

UPD: simulation measurement showed ~2X better performance of this solution compared to alternative solution and ~6X better performance over my original implementation.

void divmod10(uint32_t in, uint32_t &div, uint32_t &mod)
{
 // q = in * 0.8;
 uint32_t q = (in >> 1) + (in >> 2);
 q = q + (q >> 4);
 q = q + (q >> 8);
 q = q + (q >> 16);  // not needed for 16 bit version

 // q = q / 8;  ==> q =  in *0.1;
 q = q >> 3;

 // determine error
 uint32_t  r = in - ((q << 3) + (q << 1));   // r = in - q*10;
 div = q + (r > 9);
 if (r > 9) mod = r - 10;
 else mod = r;
}