itoa.c

#include <sys/types.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>

inline int
my_log10(uint64_t n)
{
	if (n < 10000000000000000ULL) {
		if (n < 100000000) {
			if (n < 10000) {
				if (n < 100) {
					if (n < 10) {
						return 1;
					} else {
						return 2;
					}
				} else {
					if (n < 1000) {
						return 3;
					} else {
						return 4;
					}
				}
			} else {
				if (n < 1000000) {
					if (n < 100000) {
						return 5;
					} else {
						return 6;
					}
				} else {
					if (n < 10000000) {
						return 7;
					} else {
						return 8;
					}
				}
			}
		} else {
			if (n < 1000000000000ULL) {
				if (n < 10000000000ULL) {
					if (n < 1000000000ULL) {
						return 9;
					} else {
						return 10;
					}
				} else {
					if (n < 100000000000ULL) {
						return 11;
					} else {
						return 12;
					}
				}
			} else {
				if (n < 100000000000000ULL) {
					if (n < 10000000000000ULL) {
						return 13;
					} else {
						return 14;
					}
				} else {
					if (n < 1000000000000000ULL) {
						return 15;
					} else {
						return 16;
					}
				}
			}
		}
	}

	if (n < 1000000000000000000ULL) {
		if (n < 100000000000000000ULL)
			return 17;
		return 18;
	}

	if (n < 10000000000000000000ULL)
		return 19;
	return 20;
}

char *
sprintf_wrap(char *dst, uint64_t n)
{
	sprintf(dst, "%llu", (unsigned long long)n);
	return NULL;
}

char *
str_uint64(char *dst, uint64_t n)
{
	int l;
	char *p;

	l = my_log10(n);

	dst += l;
	p = dst;
	*dst-- = '\0';
	for (; l > 0; l--) {
		*dst-- = (n % 10) + '0';
		n /= 10;
	}

	return p;
}

char *
str_uint64_nodiv(char *dst, uint64_t n)
{
	int q;
	char *p;
	int pad;

	pad = 0;
	p = dst;

	/*
	 * max uint64 is 18446744073709551615,
	 * most significant digit is 1 or 0.
	 */
	if (n >= 10000000000000000000ULL) {
		*p++ = '1';
		n -= 10000000000000000000ULL;
		pad = 1;
	}

#define QOUTPUT(X)				\
	if (n >= X) {				\
		q = 0;				\
		do {				\
			q++;			\
			n -= X;			\
		} while (n >= X);		\
		*p++ = q + '0';			\
		pad = 1;			\
	} else if (pad) {			\
		*p++ = '0';			\
	}

	QOUTPUT(1000000000000000000ULL);
	QOUTPUT(100000000000000000ULL);
	QOUTPUT(10000000000000000ULL);
	QOUTPUT(1000000000000000ULL);
	QOUTPUT(100000000000000ULL);
	QOUTPUT(10000000000000ULL);
	QOUTPUT(1000000000000ULL);
	QOUTPUT(100000000000ULL);
	QOUTPUT(10000000000ULL);
	QOUTPUT(1000000000ULL);
	QOUTPUT(100000000ULL);
	QOUTPUT(10000000ULL);
	QOUTPUT(1000000ULL);
	QOUTPUT(100000ULL);
	QOUTPUT(10000ULL);
	QOUTPUT(1000ULL);
	QOUTPUT(100ULL);
	QOUTPUT(10ULL);

	*p++ = n + '0';
	*p = '\0';
	return p;
}

char *
str_uint64_memcpy(char *dst, uint64_t n)
{
	int l;
	char *p, *q;

	p = q = dst + 20;	/* 20 = maximum length of decimal UINT64_MAX */

	do {
		*--p = (n % 10) + '0';
		n /= 10;
	} while (n != 0);
	l = q - p;
	memcpy(dst, p, l);
	dst[l] = '\0';
	return &dst[l];
}

unsigned long long
diff_timeval(struct timeval *now, struct timeval *last)
{
	struct timeval v;
	timersub(last, now, &v);
	return v.tv_usec + v.tv_sec * 1000000;
}

struct {
	char *description;
	char *(*targetfunc)(char *, uint64_t);
} func_table[] = {
	{	"sprintf",		sprintf_wrap		},
	{	"str_uint64_log10",	str_uint64		},
	{	"str_uint64_nodiv",	str_uint64_nodiv	},
	{	"str_uint64_memcpy",	str_uint64_memcpy	},
	{	NULL,	NULL	}
};

struct {
	uint64_t n;
	const char *ok;
} testpattern[] = {
	{	1234567890ULL,			"1234567890"		},
	{	12345678901234567890ULL,	"12345678901234567890"	},
	{	987654321098765ULL,		"987654321098765"	},
	{	101010101010101010ULL,		"101010101010101010"	},
	{	0ULL,				"0"			},
	{	18446744073709551615ULL,	"18446744073709551615"	},
	{	0,				NULL			}
};

int
main(int argc, char *argv[])
{
	char buf[1024];
	struct timeval start, end;
	int i, j;

	for (i = 0; func_table[i].targetfunc != NULL; i++) {

		/* TEST */
		for (j = 0; testpattern[j].ok != NULL; j++) {

			func_table[i].targetfunc(buf, testpattern[j].n);

			if (strcmp(testpattern[j].ok, buf) != 0) {
				fprintf(stderr, "%s: implementation error: %llu\n",
				    func_table[i].description, (unsigned long long)testpattern[j].n);
				exit(1);
			}
		}

		gettimeofday(&start, NULL);
		for (j = 0; j < 500000; j++) {
			/* TEST CODE BEGIN */

			func_table[i].targetfunc(buf, 12345678901234567890ULL);
			func_table[i].targetfunc(buf, 1234567890123456789ULL);
			func_table[i].targetfunc(buf, 123456789012345678ULL);
			func_table[i].targetfunc(buf, 12345678901234567ULL);
			func_table[i].targetfunc(buf, 1234567890123456ULL);
			func_table[i].targetfunc(buf, 123456789012345ULL);
			func_table[i].targetfunc(buf, 12345678901234ULL);
			func_table[i].targetfunc(buf, 1234567890123ULL);
			func_table[i].targetfunc(buf, 123456789012ULL);
			func_table[i].targetfunc(buf, 12345678901ULL);
			func_table[i].targetfunc(buf, 1234567890ULL);
			func_table[i].targetfunc(buf, 123456789ULL);
			func_table[i].targetfunc(buf, 12345678ULL);
			func_table[i].targetfunc(buf, 1234567ULL);
			func_table[i].targetfunc(buf, 123456ULL);
			func_table[i].targetfunc(buf, 12345ULL);
			func_table[i].targetfunc(buf, 1234ULL);
			func_table[i].targetfunc(buf, 123ULL);
			func_table[i].targetfunc(buf, 12ULL);
			func_table[i].targetfunc(buf, 1ULL);

			/* TEST CODE END */
		}
		gettimeofday(&end, NULL);

		printf("time: %5llu.%03llu ms: %s\n",
		    diff_timeval(&start, &end) / 1000,
		    diff_timeval(&start, &end) % 1000,
		    func_table[i].description);
	}

	return 0;
}

result

==== i7-4770S 3.10GHz ====
time:   798.094 ms: sprintf
time:   161.885 ms: str_uint64_log10
time:   246.327 ms: str_uint64_nodiv
time:   238.388 ms: str_uint64_memcpy

==== PhenomII X4 955 3624.50 MHz ====
time:  1216.803 ms: sprintf
time:   322.900 ms: str_uint64_log10
time:   497.329 ms: str_uint64_nodiv
time:   500.729 ms: str_uint64_memcpy

==== Cortex-A9 r3p10 (Cortex V7A core) 792 MHz ====
time: 77556.070 ms: sprintf
time: 79491.341 ms: str_uint64_log10
time:  4168.171 ms: str_uint64_nodiv
time: 79869.892 ms: str_uint64_memcpy

==== Octeon 300MHz ====
time: 55617.713 ms: sprintf
time:  8748.082 ms: str_uint64_log10
time: 13105.686 ms: str_uint64_nodiv
time:  9051.623 ms: str_uint64_memcpy