Add libj2_j2u_to_str and libj2_str_to_j2u

Signed-off-by: Mattias Andrée <m@maandree.se>

1 files changed, 542 insertions, 0 deletions

diff --git a/libj2_j2u_to_str.c b/libj2_j2u_to_str.c
new file mode 100644
index 0000000..ab963fd
--- /dev/null
+++ b/libj2_j2u_to_str.c
@@ -0,0 +1,542 @@
+/* See LICENSE file for copyright and license details. */
+#include "common.h"
+#include <errno.h>
+#include <stdio.h>
+#ifndef TEST
+
+/* TODO Add man page */
+
+
+static size_t
+to_power_of_two(const struct libj2_j2u *a, char *buf, size_t bufsize, const char *digits, unsigned radix)
+{
+	unsigned i, shift, bits, mask;
+	unsigned ret, cur_shift;
+	uintmax_t v;
+
+	shift = 0;
+	for (i = radix; i >>= 1;)
+		shift += 1U;
+
+	mask = radix - 1U;
+	bits = libj2_fls_j2u(a);
+	if (bits % shift)
+		bits += shift - bits % shift;
+	cur_shift = bits;
+	ret = bits / shift;
+
+	do {
+		if (!bufsize)
+			break;
+		cur_shift -= shift;
+		if (cur_shift >= LIBJ2_JU_BIT) {
+			v = a->high >> (cur_shift - LIBJ2_JU_BIT);
+		} else if (cur_shift + shift <= LIBJ2_JU_BIT) {
+			v = a->low >> cur_shift;
+		} else {
+			v = a->low >> cur_shift;
+			v |= a->high << (LIBJ2_JU_BIT % shift);
+		}
+		v &= mask;
+		*buf++ = digits[v];
+		bufsize--;
+	} while (cur_shift);
+
+	return (size_t)ret;
+}
+
+
+static size_t
+to_generic(const struct libj2_j2u *a, char *buf, size_t bufsize, const char *digits, unsigned radix)
+{
+	struct libj2_j2u v = *a, digit;
+	uintmax_t b = (uintmax_t)radix;
+	char charstack[LIBJ2_J2U_BIT];
+	size_t n = 0, i;
+
+	while (v.high) {
+		libj2_j2u_divmod_ju_to_j2u_j2u(&v, b, &v, &digit);
+		charstack[n++] = digits[digit.low];
+	}
+	while (v.low) {
+		charstack[n++] = digits[v.low % b];
+		v.low /= b;
+	}
+
+	for (i = n; i && bufsize; bufsize--)
+		*buf++ = charstack[--i];
+
+	return n;
+}
+
+
+static size_t
+to_decimal(const struct libj2_j2u *a, char *buf, size_t bufsize)
+{
+#define C(X)  X"0" X"1" X"2" X"3" X"4" X"5" X"6" X"7" X"8" X"9"
+#define B(X)  C(X"0") C(X"1") C(X"2") C(X"3") C(X"4") C(X"5") C(X"6") C(X"7") C(X"8") C(X"9")
+#define A()   B("0") B("1") B("2") B("3") B("4") B("5") B("6") B("7") B("8") B("9")
+
+	static const char text[] = A();
+
+#undef A
+#undef B
+#undef C
+
+	struct libj2_j2u v = *a, digits;
+	char charstack[LIBJ2_J2U_BIT];
+	size_t n = 0, i;
+
+	while (v.high) {
+		libj2_j2u_divmod_ju_to_j2u_j2u(&v, 1000, &v, &digits);
+		charstack[n++] = text[digits.low * 3U + 2U];
+		charstack[n++] = text[digits.low * 3U + 1U];
+		charstack[n++] = text[digits.low * 3U + 0U];
+	}
+	while (v.low) {
+		digits.low = v.low % 1000;
+		v.low /= 1000;
+		charstack[n++] = text[digits.low * 3U + 2U];
+		charstack[n++] = text[digits.low * 3U + 1U];
+		charstack[n++] = text[digits.low * 3U + 0U];
+	}
+
+	while (charstack[n - 1U] == '0')
+		n -= 1U;
+	for (i = n; i && bufsize; bufsize--)
+		*buf++ = charstack[--i];
+
+	return n;
+}
+
+
+size_t
+libj2_j2u_to_str(const struct libj2_j2u *a, char *buf, size_t bufsize, const char *digits)
+{
+	char symbols[256];
+	unsigned i, radix = 0;
+	size_t n, bufsize_m1;
+
+	if (!buf)
+		bufsize = 0;
+	if (!digits)
+		digits = "0123456789";
+
+	for (i = 0; i < sizeof(symbols); i++)
+		symbols[i] = 0;
+	while (digits[radix]) {
+		if (symbols[(unsigned char)digits[radix]])
+			return 0;
+		symbols[(unsigned char)digits[radix]] = 1;
+		radix++;
+	}
+
+	if (radix < 2)
+		return 0;
+
+	if (libj2_j2u_is_zero(a)) {
+		if (bufsize) {
+			buf[0] = digits[0];
+			buf[bufsize > 1] = '\0';
+		}
+		return 1U;
+	}
+
+	bufsize_m1 = bufsize - (size_t)(bufsize > 0);
+	if ((radix & (radix - 1U)) == 0U) {
+		n = to_power_of_two(a, buf, bufsize_m1, digits, radix);
+		goto out;
+	}
+	if (radix != 10)
+		goto generic;
+	for (i = 0; i < 10; i++)
+		if (digits[i] != (char)((unsigned)'0' + i))
+			goto generic;
+	n = to_decimal(a, buf, bufsize_m1);
+	goto out;
+generic:
+	n = to_generic(a, buf, bufsize_m1, digits, radix);
+out:
+	if (bufsize)
+		buf[n < bufsize_m1 ? n : bufsize_m1] = '\0';
+	return n;
+}
+
+
+#else
+
+#define BUFFER_SIZE 1024
+
+
+static uintmax_t
+random_ju(void)
+{
+	size_t n = LIBJ2_JU_BIT;
+	uintmax_t r = 0;
+	while (n--)
+		if (rand() < rand())
+			r |= (uintmax_t)1 << n;
+	return r;
+}
+
+
+static void
+check_(struct libj2_j2u *a, size_t bufsize, const char *digits, const char *expected_s, size_t expected_n)
+{
+	char buf[BUFFER_SIZE], *end;
+	struct libj2_j2u a_saved = *a, v;
+	size_t n;
+
+	memset(buf, '~', sizeof(buf));
+	EXPECT(libj2_j2u_to_str(a, buf, bufsize, digits) == expected_n);
+	EXPECT(libj2_j2u_eq_j2u(a, &a_saved));
+	if (expected_s) {
+		n = strlen(expected_s);
+		EXPECT(!memcmp(buf, expected_s, n));
+		EXPECT(buf[n] == '\0');
+		EXPECT(buf[n + 1U] == '~');
+
+		if (!n)
+			return;
+
+		v = (struct libj2_j2u){111, 222};
+		end = NULL;
+		EXPECT(libj2_str_to_j2u(expected_s, strlen(expected_s), &end, digits, NULL, &v) == 0);
+		EXPECT(libj2_j2u_eq_j2u(&v, a));
+		EXPECT(end);
+		EXPECT(!*end);
+	} else {
+		EXPECT(buf[0] == '~');
+		return;
+	}
+
+	for (; n; n--) {
+		memset(buf, '~', sizeof(buf));
+		EXPECT(libj2_j2u_to_str(a, buf, n + 1U, digits) == expected_n);
+		EXPECT(libj2_j2u_eq_j2u(a, &a_saved));
+		EXPECT(!memcmp(buf, expected_s, n));
+		EXPECT(buf[n] == '\0');
+		EXPECT(buf[n + 1U] == '~');
+	}
+
+	memset(buf, '~', sizeof(buf));
+	EXPECT(libj2_j2u_to_str(a, buf, 1, digits) == expected_n);
+	EXPECT(libj2_j2u_eq_j2u(a, &a_saved));
+	EXPECT(buf[0] == '\0');
+	EXPECT(buf[1] == '~');
+
+	memset(buf, '~', sizeof(buf));
+	EXPECT(libj2_j2u_to_str(a, buf, 0, digits) == expected_n);
+	EXPECT(libj2_j2u_eq_j2u(a, &a_saved));
+	EXPECT(buf[0] == '~');
+}
+
+
+static void
+check(struct libj2_j2u *a, size_t bufsize, const char *digits, const char *expected_s, size_t expected_n)
+{
+	char buf[BUFFER_SIZE], alphabet[17];
+	size_t i;
+	struct libj2_j2u a_saved = *a;
+
+	check_(a, bufsize, digits, expected_s, expected_n);
+	EXPECT(libj2_j2u_eq_j2u(a, &a_saved));
+
+	if (!digits)
+		digits = "0123456789";
+	if (strlen(digits) > sizeof(alphabet) - 1U)
+		return;
+	if (!expected_s)
+		return;
+
+	for (i = 0; digits[i]; i++) {
+		alphabet[i] = (char)((unsigned)'a' + i);
+		if (i < 10) {
+			if (digits[i] != (char)((unsigned)'0' + i))
+				return;
+		} else if (digits[i] != (char)((unsigned)'a' + i - 10)) {
+			if (digits[i] != (char)((unsigned)'A' + i - 10))
+				return;
+		}
+	}
+	alphabet[i] = '\0';
+
+	for (i = 0; expected_s[i]; i++) {
+		if (expected_s[i] <= '9')
+			buf[i] = (char)('a' - '0' + expected_s[i]);
+		else if (expected_s[i] <= 'Z')
+			buf[i] = (char)('k' - 'A' + expected_s[i]);
+		else
+			buf[i] = (char)('k' - 'a' + expected_s[i]);
+	}
+	buf[i] = '\0';
+
+	check_(a, bufsize, alphabet, buf, expected_n);
+	EXPECT(libj2_j2u_eq_j2u(a, &a_saved));
+}
+
+
+static void
+check_zero_low(const struct libj2_j2u *a_with_low, const char *digits, const char *expected)
+{
+	char buf1[BUFFER_SIZE], buf2[BUFFER_SIZE], *e;
+	struct libj2_j2u a;
+	size_t i, j, ndigits = strlen(digits);
+	int borrow;
+
+	for (i = 0; i < ndigits; i++)
+		EXPECT(digits[i] == (char)((unsigned)'0' + i));
+
+	a = *a_with_low;
+	a.high = 0;
+	EXPECT(libj2_j2u_to_str(&a, buf1, BUFFER_SIZE, digits) > 0);
+	i = strlen(expected);
+	j = strlen(buf1);
+	EXPECT(j <= i);
+
+	memcpy(buf2, expected, i + 1U);
+	borrow = 0;
+	while (i--, j--) {
+		int x = (int)(buf2[i] - '0');
+		int y = (int)(buf1[j] - '0');
+		int z = x - y - borrow;
+		borrow = z < 0;
+		if (borrow)
+			z += (int)ndigits;
+		buf2[i] = digits[z];
+	}
+	if (borrow) {
+		while (buf2[i] == '0')
+			buf2[i--] = digits[ndigits - 1U];
+		buf2[i] = (char)((int)buf2[i] - 1);
+	}
+	e = buf2;
+	while (e[0] == '0' && e[1])
+		e++;
+	EXPECT(*e);
+
+	a = *a_with_low;
+	a.low = 0;
+	check(&a, BUFFER_SIZE, digits, e, strlen(e));
+}
+
+
+int
+main(void)
+{
+	char expected[BUFFER_SIZE];
+	struct libj2_j2u a;
+	unsigned i, j;
+	uintmax_t t;
+	int n, m;
+
+	srand((unsigned)time(NULL));
+
+	libj2_j2u_zero(&a);
+	EXPECT(libj2_j2u_to_str(&a, NULL, SIZE_MAX, "") == 0);
+	EXPECT(libj2_j2u_is_zero(&a));
+	EXPECT(libj2_j2u_to_str(&a, NULL, SIZE_MAX, "0") == 0);
+	EXPECT(libj2_j2u_is_zero(&a));
+	EXPECT(libj2_j2u_to_str(&a, NULL, SIZE_MAX, "01") == 1);
+	EXPECT(libj2_j2u_is_zero(&a));
+	EXPECT(libj2_j2u_to_str(&a, NULL, SIZE_MAX, "01234") == 1);
+	EXPECT(libj2_j2u_is_zero(&a));
+	EXPECT(libj2_j2u_to_str(&a, NULL, SIZE_MAX, "01234567") == 1);
+	EXPECT(libj2_j2u_is_zero(&a));
+	EXPECT(libj2_j2u_to_str(&a, NULL, SIZE_MAX, "0123456789") == 1);
+	EXPECT(libj2_j2u_is_zero(&a));
+	EXPECT(libj2_j2u_to_str(&a, NULL, SIZE_MAX, "00") == 0);
+	EXPECT(libj2_j2u_is_zero(&a));
+
+	libj2_j2u_zero(&a);
+	check(&a, BUFFER_SIZE, "", NULL, 0);
+	check(&a, BUFFER_SIZE, "0", NULL, 0);
+	check(&a, BUFFER_SIZE, "01", "0", 1);
+	check(&a, BUFFER_SIZE, "01234", "0", 1);
+	check(&a, BUFFER_SIZE, "01234567", "0", 1);
+	check(&a, BUFFER_SIZE, "0123456789", "0", 1);
+	check(&a, BUFFER_SIZE, "0123456789ab", "0", 1);
+	check(&a, BUFFER_SIZE, NULL, "0", 1);
+
+	libj2_j2u_zero(&a);
+	check(&a, 2, "", NULL, 0);
+	check(&a, 2, "0", NULL, 0);
+	check(&a, 2, "01", "0", 1);
+	check(&a, 2, "01234", "0", 1);
+	check(&a, 2, "01234567", "0", 1);
+	check(&a, 2, "0123456789", "0", 1);
+	check(&a, 2, "0123456789ab", "0", 1);
+	check(&a, 2, NULL, "0", 1);
+
+	libj2_j2u_zero(&a);
+	check(&a, 2, "ab", "a", 1);
+	check(&a, 2, "abcde", "a", 1);
+	check(&a, 2, "abcdefgh", "a", 1);
+	check(&a, 2, "abcdefghij", "a", 1);
+	check(&a, 2, "abcdefghijkl", "a", 1);
+
+	libj2_j2u_zero(&a);
+	check(&a, 1, "", NULL, 0);
+	check(&a, 1, "0", NULL, 0);
+	check(&a, 1, "01", "", 1);
+	check(&a, 1, "01234", "", 1);
+	check(&a, 1, "01234567", "", 1);
+	check(&a, 1, "0123456789", "", 1);
+	check(&a, 1, "0123456789ab", "", 1);
+	check(&a, 1, NULL, "", 1);
+
+	for (i = 0; i < 32; i++) {
+		a.high = UINTMAX_MAX ^ (UINTMAX_MAX >> 1);
+		a.high |= random_ju();
+		a.low = 0;
+
+		for (j = 0; j < LIBJ2_JU_BIT - 1U; j++) {
+			n = sprintf(expected, "%jx%0*jx", a.high, (int)LIBJ2_JU_BIT / 4, a.low);
+			EXPECT(n > 0);
+			check(&a, BUFFER_SIZE, "0123456789abcdef", expected, (size_t)n);
+
+			n = sprintf(expected, "%jX%0*jX", a.high, (int)LIBJ2_JU_BIT / 4, a.low);
+			EXPECT(n > 0);
+			check(&a, BUFFER_SIZE, "0123456789ABCDEF", expected, (size_t)n);
+
+			a.high >>= 1;
+		}
+
+		a.high = UINTMAX_MAX ^ (UINTMAX_MAX >> 1);
+		a.high |= random_ju();
+		a.low = random_ju();
+
+		for (j = 0; j < LIBJ2_JU_BIT - 1U; j++) {
+			n = sprintf(expected, "%jx%0*jx", a.high, (int)LIBJ2_JU_BIT / 4, a.low);
+			EXPECT(n > 0);
+			check(&a, BUFFER_SIZE, "0123456789abcdef", expected, (size_t)n);
+
+			n = sprintf(expected, "%jX%0*jX", a.high, (int)LIBJ2_JU_BIT / 4, a.low);
+			EXPECT(n > 0);
+			check(&a, BUFFER_SIZE, "0123456789ABCDEF", expected, (size_t)n);
+
+			a.high >>= 1;
+		}
+
+		for (j = 0; j < LIBJ2_J2U_BIT; j++) {
+			a.low >>= 1;
+			a.low |= (a.high & 1U) << (LIBJ2_JU_BIT - 1U);
+			a.high >>= 1;
+
+			n = sprintf(expected, "%jx", a.low);
+			EXPECT(n > 0);
+			check(&a, BUFFER_SIZE, "0123456789abcdef", expected, (size_t)n);
+
+			n = sprintf(expected, "%jX", a.low);
+			EXPECT(n > 0);
+			check(&a, BUFFER_SIZE, "0123456789ABCDEF", expected, (size_t)n);
+
+			n = sprintf(expected, "%jo", a.low);
+			EXPECT(n > 0);
+			check(&a, BUFFER_SIZE, "01234567", expected, (size_t)n);
+
+			n = sprintf(expected, "%ju", a.low);
+			EXPECT(n > 0);
+			check(&a, BUFFER_SIZE, "0123456789", expected, (size_t)n);
+
+			n = sprintf(expected, "%ju", a.low);
+			EXPECT(n > 0);
+			check(&a, BUFFER_SIZE, NULL, expected, (size_t)n);
+		}
+
+		a.high = 0;
+		a.low = random_ju();
+		a.low |= UINTMAX_MAX ^ (UINTMAX_MAX >> 1);
+		n = sprintf(expected, "%jo", a.low);
+		EXPECT(n > 0);
+		libj2_j2u_lsh(&a, LIBJ2_JU_BIT - LIBJ2_JU_BIT % 3U);
+		t = ((uintmax_t)1 << ((LIBJ2_JU_BIT - LIBJ2_JU_BIT % 3) / 3U)) - 1U;
+		t &= random_ju();
+		m = sprintf(&expected[n], "%0*jo", (int)LIBJ2_JU_BIT / 3, t);
+		EXPECT(m > 0);
+		n += m;
+		libj2_j2u_or_ju(&a, t);
+		check(&a, BUFFER_SIZE, "01234567", expected, (size_t)n);
+		while (libj2_j2u_rsh(&a, 3), !libj2_j2u_is_zero(&a)) {
+			expected[--n] = '\0';
+			check(&a, BUFFER_SIZE, "01234567", expected, (size_t)n);
+		}
+
+		a.high = 0;
+		do {
+			a.low = random_ju();
+		} while (!a.low);
+		n = sprintf(expected, "%ju", a.low);
+		EXPECT(n > 0);
+		while (!libj2_j2u_mul_ju_overflow_p(&a, 10)) {
+			libj2_j2u_mul_ju(&a, 10);
+			j = (unsigned)random_ju() % 10U;
+			if (libj2_j2u_add_ju_overflow_p(&a, j)) {
+				expected[n++] = '0';
+				break;
+			}
+			libj2_j2u_add_ju(&a, j);
+			expected[n++] = (char)((unsigned)'0' + j);
+		}
+		expected[n] = '\0';
+		check(&a, BUFFER_SIZE, "0123456789", expected, (size_t)n);
+		check(&a, BUFFER_SIZE, NULL, expected, (size_t)n);
+		check_zero_low(&a, "0123456789", expected);
+		while (libj2_j2u_div_ju(&a, 10), !libj2_j2u_is_zero(&a)) {
+			expected[--n] = '\0';
+			check(&a, BUFFER_SIZE, NULL, expected, (size_t)n);
+		}
+
+		a.high = 0;
+		do {
+			a.low = random_ju() % 5U;
+		} while (!a.low);
+		n = 0;
+		expected[n++] = (char)((unsigned)'0' + a.low);
+		expected[n] = '\0';
+		check(&a, BUFFER_SIZE, "01234", expected, (size_t)n);
+		while (!libj2_j2u_mul_ju_overflow_p(&a, 5)) {
+			libj2_j2u_mul_ju(&a, 5);
+			j = (unsigned)random_ju() % 5U;
+			if (libj2_j2u_add_ju_overflow_p(&a, j)) {
+				expected[n++] = '0';
+				expected[n] = '\0';
+				check(&a, BUFFER_SIZE, "01234", expected, (size_t)n);
+				break;
+			}
+			libj2_j2u_add_ju(&a, j);
+			expected[n++] = (char)((unsigned)'0' + j);
+			expected[n] = '\0';
+			check(&a, BUFFER_SIZE, "01234", expected, (size_t)n);
+		}
+		check_zero_low(&a, "01234", expected);
+
+		a.high = 0;
+		do {
+			a.low = random_ju() % 11U;
+		} while (!a.low);
+		n = 0;
+		expected[n++] = (char)((unsigned)'0' + a.low);
+		expected[n] = '\0';
+		check(&a, BUFFER_SIZE, "0123456789:", expected, (size_t)n);
+		while (!libj2_j2u_mul_ju_overflow_p(&a, 11)) {
+			libj2_j2u_mul_ju(&a, 11);
+			j = (unsigned)random_ju() % 11U;
+			if (libj2_j2u_add_ju_overflow_p(&a, j)) {
+				expected[n++] = '0';
+				expected[n] = '\0';
+				check(&a, BUFFER_SIZE, "0123456789:", expected, (size_t)n);
+				break;
+			}
+			libj2_j2u_add_ju(&a, j);
+			expected[n++] = (char)((unsigned)'0' + j);
+			expected[n] = '\0';
+			check(&a, BUFFER_SIZE, "0123456789:", expected, (size_t)n);
+		}
+		check_zero_low(&a, "0123456789:", expected);
+	}
+
+	return 0;
+}
+
+#endif