NumToString

NumToString.c

/*
Copyright 2022 Dietrich Epp

This file is released under the terms of the Mozilla Public License, version
2.0.

Fast conversion from binary to decimal! This was originally written for a GBA
project. Note that it's fast if you compile it as ARM code, but if you compile
it as Thumb code, it will be significantly slower. The reason is because the
division operation can be optimized out in ARM. In ARM, GCC will replace the
division with a 64-bit multiplication and some shifting. In Thumb, the 64-bit
multiplication isn't available, GCC will emit a call to libgcc to perform
division, and that will be much slower.

This works for any number from 0..MAX_UINT. It will return a string structure
with a pointer to the string and the length of the string. The number will
always be "correct"--there won't be extra leading zeroes, or anything like that,
and the number 0 is correctly output as "0".

This version is just a demo to show how this works, fix it up if you want to use
it.
*/

#pragma GCC diagnostic ignored "-Wmultichar"

// clang-format off
static const unsigned short Digits[100] = {
	'00', '10', '20', '30', '40', '50', '60', '70', '80', '90',
	'01', '11', '21', '31', '41', '51', '61', '71', '81', '91',
	'02', '12', '22', '32', '42', '52', '62', '72', '82', '92',
	'03', '13', '23', '33', '43', '53', '63', '73', '83', '93',
	'04', '14', '24', '34', '44', '54', '64', '74', '84', '94',
	'05', '15', '25', '35', '45', '55', '65', '75', '85', '95',
	'06', '16', '26', '36', '46', '56', '66', '76', '86', '96',
	'07', '17', '27', '37', '47', '57', '67', '77', '87', '97',
	'08', '18', '28', '38', '48', '58', '68', '78', '88', '98',
	'09', '19', '29', '39', '49', '59', '69', '79', '89', '99',
};
// clang-format on

static unsigned short NumToStringBuf[5];

struct String NumToString(unsigned num) {
	unsigned short *ptr = NumToStringBuf + 5;
	char *ret;
	for (;;) {
		if (num < 10) {
			ret = (char *)ptr - 1;
			*ret = num + '0';
			break;
		}
		unsigned x;
		if (num < 100) {
			x = num;
			num = 0;
		} else {
			x = num % 100;
			num /= 100;
		}
		*--ptr = Digits[x];
		if (num == 0) {
			ret = (char *)ptr;
			break;
		}
	}
	return (struct String){
		.ptr = ret,
		.len = (char *)(NumToStringBuf + 5) - ret,
	};
}

NumToString2.c

/*
Copyright 2022 Dietrich Epp

This file is released under the terms of the Mozilla Public License, version
2.0.
  
This version is evene faster. For UINT_MAX, it takes 101 cycles. This is
measured using no$gba, measuring from the first to last instruction.

This shows how the optimizations in GCC work. Instead of dividing a number, you
multiply, and then shift. This version is hierarchical. It converts the number
into three groups of four digits or less, then it converts those groups into
half-groups of two digits, and then it converts those to individual digits using
a lookup table.

The number of digits in each group was chosen for performance. The conversion
from four-digit to two-digit groups requires only 31-bit precision, so it can
actually be done without using a multiply operation--on this target, GCC will
optimize these conversions into a series of additions, subtractions, and bit
shifts. This means that the entire conversion from 32-bit number to string is
done with only two multiplications.
*/

struct String NumToString(unsigned num) {
	unsigned tmp = (num * 3518437209ull) >> 45;
	// g1 - low 4 digits
	// g2 - next 4 digits
	// g3 - top 2 digits
	unsigned g1 = num - tmp * 10000;
	unsigned g3 = (tmp * 429497ull) >> 32;
	unsigned g2 = tmp - g3 * 10000;

	unsigned h1, h2;
	h2 = (g1 * 5243) >> 19;
	h1 = g1 - h2 * 100;
	NumToStringBuf[4] = Digits[h1];
	NumToStringBuf[3] = Digits[h2];
	h2 = (g2 * 5243) >> 19;
	h1 = g2 - h2 * 100;
	NumToStringBuf[2] = Digits[h1];
	NumToStringBuf[1] = Digits[h2];
	NumToStringBuf[0] = Digits[g3];
	char *ptr = (char *)&NumToStringBuf[0];
	char *end = (char *)&NumToStringBuf[5];
	while (ptr < end - 1 && *ptr == '0') {
		ptr++;
	}
	return (struct String){
		.ptr = ptr,
		.len = end - ptr,
	};
}