itoa.c

// Implementation of itoa (int to ASCII), which converts an 64-bit to decimal string.
//
// Based on Tigran Hayrapetyan Algorithm: `34% faster Integer to String conversion algorithm`
// ref: https://towardsdatascience.com/34-faster-integer-to-string-conversion-algorithm-c72453d25352/
//
// @author Lohann Paterno Coutinho Ferreira <[email protected]>
#include "itoa.h"

// lookup table of powers of 10, used by `ilog10` and `itoa`.
static uint64_t const powers_of10[20] = {
    1ULL,
    10ULL,
    100ULL,
    1000ULL,
    10000ULL,
    100000ULL,
    1000000ULL,
    10000000ULL,
    100000000ULL,
    1000000000ULL,
    10000000000ULL,
    100000000000ULL,
    1000000000000ULL,
    10000000000000ULL,
    100000000000000ULL,
    1000000000000000ULL,
    10000000000000000ULL,
    100000000000000000ULL,
    1000000000000000000ULL,
    10000000000000000000ULL,
};

/*!
 * Compute integer log base 10 of an integer using log2 and lookup tables.
 *
 * Reference:
 * https://graphics.stanford.edu/~seander/bithacks.html#IntegerLogDeBruijn
 *
 * @param v integer to calculate log10
 * @return floor(log10(v))
 */
int ilog10(uint64_t v)
{
    // Log10 DeBruijn Sequence, generated using `n = 6` and `CCR1`
    // Generator: http://combos.org/bruijn 
    static const unsigned char debruijn_bit_pos[64] = {
        0,15,0,12,15,3,0,11,12,7,16,6,3,13,1,18,11,10,12,9,7,
        8,16,14,6,9,4,5,13,17,1,18,15,11,3,10,7,6,12,18,10,9,
        8,14,8,4,16,15,3,6,5,18,9,14,4,2,5,17,13,2,17,2,1,19
    };
    
    // first round down to one less than a power of 2
    // computes: t = 2 ** floor(log2(v * 2)) - 1
    uint64_t t = v;
    t |= t >> 1;
    t |= t >> 2;
    t |= t >> 4;
    t |= t >> 8;
    t |= t >> 16;
    t |= t >> 32;
    
    // DeBruijn Lookup, approximates log10(v) by compute:
    // t = log10(v) = (1233 * floor(log2(v * 2))) / (2 ** 12)
    t *= 0x03f1b995a913b0bdULL;
    t = (uint64_t) debruijn_bit_pos[t >> 58];
    
    // Table Lookup, round down when v < 10 ** t
    return (int)t - (v < powers_of10[t]);
}

/*!
 * Fast conversion of 64-bit integer to decimal strings
 *
 * @param out Buffer that will store the value in ASCII.
 * @param len Length of `out` in bytes.
 * @param num Value to convert to ASCII string.
 *
 * @return Total number of digits of `num` that should be written to `out`,
 *         it was done this way to make truncation detection simple.
 */
int itoa(char *out, size_t len, uint64_t num)
{
    const uint64_t *power_ptr, *end;
    uint64_t digit;
    int digits;
    
    // Compute: log10(num)
    digits = ilog10(num) + (int)(num == 0);
    
    // Compute: 10 ** log10(num)
    power_ptr = &powers_of10[digits++];

    // Return if `out` length is zero.
    if (!len)
        return digits;
    
    // leave room for `\0` suffix.
    len--;
    
    // Truncate `num` if `digits > len`
    len = len < digits ? digits - len : 0;
    
    // Compute: 10 ** len
    end = &powers_of10[len];
    
    // Convert integer to decimal digits using this algorithm:
    // https://towardsdatascience.com/34-faster-integer-to-string-conversion-algorithm-c72453d25352/
    for (; power_ptr >= end; --power_ptr) {
        digit = num / *power_ptr;
        num -= digit * (*power_ptr);
        *(out++) = ((char) digit) + '0';
    }
    *out = '\0';
    return digits;
}

int main()
{
    int digits, i;
    char buffer[1024];
    uint64_t values[] = {
        123456789ULL,
        18446744073709551615ULL,
        0ULL,
        1ULL,
        987ULL,
        1337ULL,
    };
    
    for (i=0; i < (sizeof(values)/sizeof(values[0])); i++) {
        memset((void*)buffer, 0, sizeof(buffer));
        digits = itoa(buffer, sizeof(buffer), values[i]);
        printf("    value: '%s', digits: %d\n", buffer, digits);
        
        memset((void*)buffer, 0, sizeof(buffer));
        digits = itoa(buffer, (size_t)digits, values[i]);
        printf("truncated: '%s', digits: %d\n", buffer, digits);
        
        memset((void*)buffer, 0, sizeof(buffer));
        digits = itoa(buffer, 0ULL, values[i]);
        printf("    empty: '%s', digits: %d\n\n", buffer, digits);
    }
    return 0;
}

itoa.h

// Implementation of itoa (int to ASCII), a fast conversion from 64-bit integer to decimal string.
//
// Based on Tigran Hayrapetyan Algorithm: `34% faster Integer to String conversion algorithm`
// ref: https://towardsdatascience.com/34-faster-integer-to-string-conversion-algorithm-c72453d25352/
//
// @author Lohann Paterno Coutinho Ferreira <[email protected]>

#ifndef _ITOA_H_
#define _ITOA_H_

#if defined (__cplusplus)
extern "C" {
#endif

/*****************************
 * define size_t and uint64_t
 ******************************/

/* define 64-bit integer type */
#include <stddef.h> /* size_t */

/* define 64-bit integer type */
#if !defined (__VMS) \
  && (defined (__cplusplus) \
  || (defined (__STDC_VERSION__) && (__STDC_VERSION__ >= 199901L) /* C99 */) )
#ifdef _AIX
#include <inttypes.h> /* uint64_t */
#else
#include <stdint.h> /* uint64_t */
#endif
#else
#include <limits.h>
#if defined(__LP64__) && ULONG_MAX == 0xFFFFFFFFFFFFFFFFULL
    /* LP64 ABI says uint64_t is unsigned long */
    typedef unsigned long uint64_t;
#else
    /* the following type must have a width of 64-bit */
    typedef unsigned long long uint64_t;
#endif
#endif

/*!
 * Fast conversion of 64-bit integer to decimal strings
 *
 * @param out Buffer that will store the value in ASCII.
 * @param len Length of `out` in bytes.
 * @param num Value to convert to ASCII string.
 *
 * @return Total number of digits of `num` that should be written to `out`,
 *         it was done this way to make truncation detection simple.
 */
int itoa(char *out, size_t len, uint64_t num);

#if defined (__cplusplus)
} /* extern "C" */
#endif

#endif /* _ITOA_H_ */