From cf6866f033e1946af7f5abf9786c831a20d19f91 Mon Sep 17 00:00:00 2001 From: Mattias Andrée Date: Sun, 7 Dec 2025 00:47:10 +0100 Subject: Add libj2_j2u_to_str and libj2_str_to_j2u MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Mattias Andrée --- Makefile | 7 +- libj2.h | 2 + libj2/strings.h | 91 +++++++++ libj2_j2u_to_str.c | 542 +++++++++++++++++++++++++++++++++++++++++++++++++++++ libj2_str_to_j2u.c | 455 ++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 1095 insertions(+), 2 deletions(-) create mode 100644 libj2/strings.h create mode 100644 libj2_j2u_to_str.c create mode 100644 libj2_str_to_j2u.c diff --git a/Makefile b/Makefile index 82f60d0..b00a8ce 100644 --- a/Makefile +++ b/Makefile @@ -298,7 +298,9 @@ OBJ =\ libj2_ju_sat_mul_j2u_to_j2u.o\ libj2_j2u_sat_mul_j2u_destructive.o\ libj2_j2u_sat_mul_j2u.o\ - libj2_j2u_sat_mul_j2u_to_j2u.o + libj2_j2u_sat_mul_j2u_to_j2u.o\ + libj2_j2u_to_str.o\ + libj2_str_to_j2u.o SUBHDR =\ libj2/constants.h\ @@ -313,7 +315,8 @@ SUBHDR =\ libj2/subtraction.h\ libj2/multiplication.h\ libj2/division.h\ - libj2/saturated-math.h + libj2/saturated-math.h\ + libj2/strings.h HDR =\ $(SUBHDR)\ diff --git a/libj2.h b/libj2.h index a413327..6d45d26 100644 --- a/libj2.h +++ b/libj2.h @@ -3,6 +3,7 @@ #define LIBJ2_H #include +#include #include #include @@ -99,6 +100,7 @@ enum libj2_overflow { #include "libj2/multiplication.h" #include "libj2/division.h" #include "libj2/saturated-math.h" +#include "libj2/strings.h" #if defined(LIBJ2_USE_GCC_INTRINSIC_FUNCTIONS_) diff --git a/libj2/strings.h b/libj2/strings.h new file mode 100644 index 0000000..567cd3d --- /dev/null +++ b/libj2/strings.h @@ -0,0 +1,91 @@ +/* See LICENSE file for copyright and license details. */ +#ifndef LIBJ2_H +# error Do not include this header directly, include instead +#endif + + +/** + * Convert an unsigned double-max precision + * integer to a string + * + * The string will be terminated by a NUL byte + * (unless `bufsize` is 0) and will otherwise + * only contain the digits, and will not contain + * any leading zeroes (except that the value + * zero will be represented as "0") + * + * @param a The integer to convert into a string + * @param buf Buffer for the string + * @param bufsize The size of `buf` + * @param digits List of digits to use, each byte is + * regarded as a symbol, starting from + * the zero-digit. If `NULL`, "0123456789" + * (the decimal system) will be used. Minimum + * length is 2. May not contain duplicates. + * @return The number of digits used to represent + * the integer, even if not all of them + * fit into the buffer; or zero on failure + * (`digits` has a length less than 2 or + * contains duplicate symbols) + * + * This function does not set `errno` + * + * @since 1.1 + */ +#if defined(__GNUC__) +__attribute__((__nonnull__(1))) +#endif +size_t libj2_j2u_to_str(const struct libj2_j2u *a, char *buf, size_t bufsize, const char *digits); + + +/** + * Convert a string into a an unsigned + * double-max precision integer + * + * Any leading ASCII whitespace, as well + * as any leading '+' character, will be + * ignored, the all digits will be parsed + * until any other character is encountered + * + * Parsing will stop after `slen` bytes, + * when a NUL byte is encountered, or a + * non-digit is encountered after any + * leading skipped character; whichever + * comes first + * + * @param s The string to parse + * @param slen The maximum number of bytes to read from `s` + * @param end Output parameter for where parsing stopped + * (pointing to the first byte that is is not + * a leading ASCII whitespace, leading '+' + * character, nor a digit) + * @param digits1 List of digits to use, each byte is + * regarded as a symbol, starting from + * the zero-digit. If `NULL`, "0123456789" + * (the decimal system) will be used. Any + * symbol in this list will be removed from the + * set of ignored leading characeters; minimum + * length is 2. May not contain duplicates. + * @param digits2 List of symbols to use as synonyms for + * the symbols in `digits`, must be of the + * same length as `digits1`, or `NULL` if + * `digit1` is `NULL` or to use no additional + * symbols + * @param a Output parameter for the decoded integer + * @return 0 upon successful completion, or an error + * code on failure + * + * @throws EINVAL `digits1` or `digits2` is misconfigured + * @throws EINVAL No digit was encountered; + * `*a` (unless it's `NULL`) will be set to + * the value zero + * @throws ERANGE The value is too large to be represented; + * `*a` (unless it's `NULL`) will be set to + * the maximum value + * + * This function does not set `errno` + * + * @since 1.1 + */ +int libj2_str_to_j2u(const char *s, size_t slen, char **end, const char *digits1, + const char *digits2, struct libj2_j2u *a); 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 +#include +#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 diff --git a/libj2_str_to_j2u.c b/libj2_str_to_j2u.c new file mode 100644 index 0000000..b7a1bc0 --- /dev/null +++ b/libj2_str_to_j2u.c @@ -0,0 +1,455 @@ +/* See LICENSE file for copyright and license details. */ +#include "common.h" +#include +#ifndef TEST + +/* TODO Add man page */ + + +static int +from_generic(const unsigned char *s, size_t slen, const unsigned char **end, + const intmax_t symbols[256], unsigned radix, struct libj2_j2u *a) +{ + const uintmax_t high_required_at = (UINTMAX_MAX - radix + 1U) / radix; + uintmax_t radix_pow[9]; + uintmax_t v; + size_t i, x; + + for (i = 0; i < slen; i++) + if (symbols[s[i]] < 0) + break; + slen = i; + *end = &s[slen]; + + for (;;) { + if (!slen) + return 0; + a->low *= (uintmax_t)radix; + a->low += (uintmax_t)symbols[*s++]; + slen--; + if (a->low > high_required_at) { + if (!slen) + return 0; + break; + } + } + + radix_pow[0] = 1U; + radix_pow[1] = (uintmax_t)radix; + radix_pow[2] = (uintmax_t)radix * radix_pow[1]; + radix_pow[3] = (uintmax_t)radix * radix_pow[2]; + radix_pow[4] = (uintmax_t)radix * radix_pow[3]; + radix_pow[5] = (uintmax_t)radix * radix_pow[4]; + radix_pow[6] = (uintmax_t)radix * radix_pow[5]; + radix_pow[7] = (uintmax_t)radix * radix_pow[6]; + radix_pow[8] = (uintmax_t)radix * radix_pow[7]; + + x = slen & 7U; + x = x ? x : 8U; + slen -= x; + if (libj2_j2u_mul_ju_overflow(a, radix_pow[x])) + return ERANGE; + v = 0; + switch (x) { + while (slen) { + slen -= 8U; + if (libj2_j2u_mul_ju_overflow(a, radix_pow[8])) + return ERANGE; + v = 0; + /* This isn't even a case, but GCC warns fall-through here */ + /* fall-through */ + case 8: + v += (uintmax_t)symbols[*s++] * radix_pow[7]; /* fall-through */ + case 7: + v += (uintmax_t)symbols[*s++] * radix_pow[6]; /* fall-through */ + case 6: + v += (uintmax_t)symbols[*s++] * radix_pow[5]; /* fall-through */ + case 5: + v += (uintmax_t)symbols[*s++] * radix_pow[4]; /* fall-through */ + case 4: + v += (uintmax_t)symbols[*s++] * radix_pow[3]; /* fall-through */ + case 3: + v += (uintmax_t)symbols[*s++] * radix_pow[2]; /* fall-through */ + case 2: + v += (uintmax_t)symbols[*s++] * radix_pow[1]; /* fall-through */ + case 1: + v += (uintmax_t)symbols[*s++]; + if (libj2_j2u_add_ju_overflow(a, v)) + return ERANGE; + } + } + + return 0; +} + + +static int +from_power_of_two(const unsigned char *s, size_t slen, const unsigned char **end, + const intmax_t symbols[256], unsigned radix, struct libj2_j2u *a) +{ + uintmax_t high_required_at; + uintmax_t v; + unsigned shift, u, shift_mul[9]; + size_t i, x; + + shift = 0; + for (u = radix; u >>= 1;) + shift += 1U; + + for (i = 0; i < slen; i++) + if (symbols[s[i]] < 0) + break; + slen = i; + *end = &s[slen]; + + high_required_at = (uintmax_t)1 << (LIBJ2_JU_BIT - shift); + for (;;) { + if (!slen) + return 0; + a->low <<= shift; + a->low |= (uintmax_t)symbols[*s++]; + slen--; + if (a->low >= high_required_at) { + if (!slen) + return 0; + break; + } + } + + shift_mul[0] = 0U; + shift_mul[1] = shift_mul[0] + shift; + shift_mul[2] = shift_mul[1] + shift; + shift_mul[3] = shift_mul[2] + shift; + shift_mul[4] = shift_mul[3] + shift; + shift_mul[5] = shift_mul[4] + shift; + shift_mul[6] = shift_mul[5] + shift; + shift_mul[7] = shift_mul[6] + shift; + shift_mul[8] = shift_mul[7] + shift; + + x = slen & 7U; + x = x ? x : 8U; + slen -= x; + if (libj2_j2u_lsh_overflow(a, shift_mul[x])) + return ERANGE; + v = 0; + switch (x) { + while (slen) { + slen -= 8U; + if (libj2_j2u_lsh_overflow(a, shift_mul[8])) + return ERANGE; + v = 0; + /* This isn't even a case, but GCC warns fall-through here */ + /* fall-through */ + case 8: + v |= (uintmax_t)symbols[*s++] << shift_mul[7]; /* fall-through */ + case 7: + v |= (uintmax_t)symbols[*s++] << shift_mul[6]; /* fall-through */ + case 6: + v |= (uintmax_t)symbols[*s++] << shift_mul[5]; /* fall-through */ + case 5: + v |= (uintmax_t)symbols[*s++] << shift_mul[4]; /* fall-through */ + case 4: + v |= (uintmax_t)symbols[*s++] << shift_mul[3]; /* fall-through */ + case 3: + v |= (uintmax_t)symbols[*s++] << shift_mul[2]; /* fall-through */ + case 2: + v |= (uintmax_t)symbols[*s++] << shift_mul[1]; /* fall-through */ + case 1: + v |= (uintmax_t)symbols[*s++]; + libj2_j2u_or_ju(a, v); + } + } + + return 0; +} + + +int +libj2_str_to_j2u(const char *str, size_t slen, char **end, const char *digits1, + const char *digits2, struct libj2_j2u *a) +{ + const unsigned char *s = (const unsigned char *)str; + intmax_t symbols[256]; + unsigned i, radix = 0; + struct libj2_j2u a_discard; + char *end_discard; + int r; + + if (!end) + end = &end_discard; + if (!a) + a = &a_discard; + libj2_j2u_zero(a); + + if (!s) + slen = 0; + if (!digits1) { + digits1 = "0123456789"; + if (digits2) + goto einval; + } + + for (i = 0; i < sizeof(symbols) / sizeof(*symbols); i++) + symbols[i] = -2; + symbols[' '] = -1; + symbols['\r'] = -1; + symbols['\t'] = -1; + symbols['\f'] = -1; + symbols['\v'] = -1; + symbols['\n'] = -1; + symbols['+'] = -1; + while (digits1[radix]) { + if (symbols[(unsigned char)digits1[radix]] >= 0) + goto einval; + symbols[(unsigned char)digits1[radix]] = (intmax_t)radix; + radix++; + } + + if (digits2) { + for (i = 0; digits2[i]; i++) { + if (symbols[(unsigned char)digits2[i]] >= 256) + goto einval; + symbols[(unsigned char)digits2[i]] = (intmax_t)(i | 256U); + } + if (i != radix) + goto einval; + for (i = 0; digits2[i]; i++) + symbols[(unsigned char)digits2[i]] &= 255; + } + + if (radix < 2) { + einval: + *(const unsigned char **)(void *)end = s; + return EINVAL; + } + + for (;; slen--, s++) { + if (!slen) + goto einval; + if (symbols[*s] != -1) { + if (symbols[*s] >= 0) + break; + goto einval; + } + } + + while (slen && symbols[*s] == 0) { + s++; + slen--; + } + + if ((radix & (radix - 1U)) == 0U) + r = from_power_of_two(s, slen, (void *)end, symbols, radix, a); + else + r = from_generic(s, slen, (void *)end, symbols, radix, a); + if (r == ERANGE) + libj2_j2u_max(a); + return r; +} + + +#else + +CONST int +main(void) +{ + /* Primarily tested in libj2_j2u_to_str.c */ + + char buf[sizeof(uintmax_t) * 8U]; + struct libj2_j2u a; + char *end; + + a = (struct libj2_j2u){111, 222}; + EXPECT(libj2_str_to_j2u("10000", SIZE_MAX, NULL, NULL, NULL, &a) == 0); + EXPECT(libj2_j2u_eq_ju(&a, 10000)); + + a = (struct libj2_j2u){111, 222}; + EXPECT(libj2_str_to_j2u("10000", 6, NULL, NULL, NULL, &a) == 0); + EXPECT(libj2_j2u_eq_ju(&a, 10000)); + + a = (struct libj2_j2u){111, 222}; + EXPECT(libj2_str_to_j2u("10000", 5, NULL, NULL, NULL, &a) == 0); + EXPECT(libj2_j2u_eq_ju(&a, 10000)); + + a = (struct libj2_j2u){111, 222}; + EXPECT(libj2_str_to_j2u("10000", 4, NULL, NULL, NULL, &a) == 0); + EXPECT(libj2_j2u_eq_ju(&a, 1000)); + + a = (struct libj2_j2u){111, 222}; + end = NULL; + EXPECT(libj2_str_to_j2u("10000", 4, &end, NULL, "0123456789", &a) == EINVAL); + EXPECT(libj2_j2u_is_zero(&a)); + EXPECT(end); + EXPECT(!strcmp(end, "10000")); + + a = (struct libj2_j2u){111, 222}; + EXPECT(libj2_str_to_j2u("10000", 3, NULL, NULL, NULL, &a) == 0); + EXPECT(libj2_j2u_eq_ju(&a, 100)); + + a = (struct libj2_j2u){111, 222}; + EXPECT(libj2_str_to_j2u("10000", 2, NULL, NULL, NULL, &a) == 0); + EXPECT(libj2_j2u_eq_ju(&a, 10)); + + a = (struct libj2_j2u){111, 222}; + EXPECT(libj2_str_to_j2u("10000", 1, NULL, NULL, NULL, &a) == 0); + EXPECT(libj2_j2u_eq_ju(&a, 1)); + + a = (struct libj2_j2u){111, 222}; + EXPECT(libj2_str_to_j2u("10000", 0, NULL, NULL, NULL, &a) == EINVAL); + EXPECT(libj2_j2u_is_zero(&a)); + + a = (struct libj2_j2u){111, 222}; + end = NULL; + EXPECT(libj2_str_to_j2u(" \r\n\v+\t\f + 10000", SIZE_MAX, &end, NULL, NULL, &a) == 0); + EXPECT(libj2_j2u_eq_ju(&a, 10000)); + EXPECT(end); + EXPECT(!*end); + + a = (struct libj2_j2u){111, 222}; + end = NULL; + EXPECT(libj2_str_to_j2u(" \r\n\v+\t\f + 10000 0", SIZE_MAX, &end, NULL, NULL, &a) == 0); + EXPECT(libj2_j2u_eq_ju(&a, 10000)); + EXPECT(end); + EXPECT(!strcmp(end, " 0")); + + a = (struct libj2_j2u){111, 222}; + end = NULL; + EXPECT(libj2_str_to_j2u(" \r\n\v+\t\f + 10000x0", SIZE_MAX, &end, NULL, NULL, &a) == 0); + EXPECT(libj2_j2u_eq_ju(&a, 10000)); + EXPECT(end); + EXPECT(!strcmp(end, "x0")); + + a = (struct libj2_j2u){111, 222}; + end = NULL; + EXPECT(libj2_str_to_j2u(" +-- ", SIZE_MAX, &end, "-+", NULL, &a) == 0); + EXPECT(libj2_j2u_eq_ju(&a, 4)); + EXPECT(end); + EXPECT(!strcmp(end, " ")); + + a = (struct libj2_j2u){111, 222}; + end = NULL; + EXPECT(libj2_str_to_j2u(" +-- ", SIZE_MAX, &end, "- +", NULL, &a) == 0); + EXPECT(libj2_j2u_eq_ju(&a, 136)); + EXPECT(end); + EXPECT(!*end); + + a = (struct libj2_j2u){111, 222}; + end = NULL; + EXPECT(libj2_str_to_j2u("ba", SIZE_MAX, &end, "ab", "ab", &a) == 0); + EXPECT(libj2_j2u_eq_ju(&a, 2)); + EXPECT(end); + EXPECT(!*end); + + a = (struct libj2_j2u){111, 222}; + end = NULL; + EXPECT(libj2_str_to_j2u("ba", SIZE_MAX, &end, "Ab", "Ab", &a) == 0); + EXPECT(libj2_j2u_eq_ju(&a, 1)); + EXPECT(end); + EXPECT(*end == 'a'); + + a = (struct libj2_j2u){111, 222}; + end = NULL; + EXPECT(libj2_str_to_j2u("ba", SIZE_MAX, &end, "ab", "Ab", &a) == 0); + EXPECT(libj2_j2u_eq_ju(&a, 2)); + EXPECT(end); + EXPECT(!*end); + + a = (struct libj2_j2u){111, 222}; + end = NULL; + EXPECT(libj2_str_to_j2u("ba", SIZE_MAX, &end, "ab", "AB", &a) == 0); + EXPECT(libj2_j2u_eq_ju(&a, 2)); + EXPECT(end); + EXPECT(!*end); + + a = (struct libj2_j2u){111, 222}; + end = NULL; + EXPECT(libj2_str_to_j2u("ba", SIZE_MAX, &end, "AB", "AB", &a) == EINVAL); + EXPECT(libj2_j2u_is_zero(&a)); + EXPECT(end); + EXPECT(*end == 'b'); + + a = (struct libj2_j2u){111, 222}; + end = NULL; + EXPECT(libj2_str_to_j2u("ba", SIZE_MAX, &end, "AB", "ab", &a) == 0); + EXPECT(libj2_j2u_eq_ju(&a, 2)); + EXPECT(end); + EXPECT(!*end); + + a = (struct libj2_j2u){111, 222}; + end = NULL; + EXPECT(libj2_str_to_j2u("BA", SIZE_MAX, &end, "ab", "AB", &a) == 0); + EXPECT(libj2_j2u_eq_ju(&a, 2)); + EXPECT(end); + EXPECT(!*end); + + a = (struct libj2_j2u){111, 222}; + end = NULL; + EXPECT(libj2_str_to_j2u("BA", SIZE_MAX, &end, "AB", "AB", &a) == 0); + EXPECT(libj2_j2u_eq_ju(&a, 2)); + EXPECT(end); + EXPECT(!*end); + + a = (struct libj2_j2u){111, 222}; + end = NULL; + EXPECT(libj2_str_to_j2u("BA", SIZE_MAX, &end, "AB", "ab", &a) == 0); + EXPECT(libj2_j2u_eq_ju(&a, 2)); + EXPECT(end); + EXPECT(!*end); + + a = (struct libj2_j2u){111, 222}; + end = NULL; + EXPECT(libj2_str_to_j2u("BA", SIZE_MAX, &end, "ABB", "abb", &a) == EINVAL); + EXPECT(libj2_j2u_is_zero(&a)); + EXPECT(end); + EXPECT(*end == 'B'); + + a = (struct libj2_j2u){111, 222}; + end = NULL; + EXPECT(libj2_str_to_j2u("BA", SIZE_MAX, &end, "AB", "abc", &a) == EINVAL); + EXPECT(libj2_j2u_is_zero(&a)); + EXPECT(end); + EXPECT(*end == 'B'); + + a = (struct libj2_j2u){111, 222}; + end = NULL; + EXPECT(libj2_str_to_j2u("BA", SIZE_MAX, &end, "ABC", "ab", &a) == EINVAL); + EXPECT(libj2_j2u_is_zero(&a)); + EXPECT(end); + EXPECT(*end == 'B'); + + sprintf(buf, "%jx%jx", UINTMAX_MAX, UINTMAX_MAX); + a = (struct libj2_j2u){111, 222}; + end = NULL; + EXPECT(libj2_str_to_j2u(buf, SIZE_MAX, &end, "0123456789abcdef", NULL, &a) == 0); + EXPECT(libj2_j2u_is_max(&a)); + EXPECT(end); + EXPECT(!*end); + + sprintf(buf, "%jx%jx", UINTMAX_MAX, UINTMAX_MAX); + a = (struct libj2_j2u){111, 222}; + end = NULL; + EXPECT(libj2_str_to_j2u(buf, SIZE_MAX, &end, "0123456789abcdefg", NULL, &a) == ERANGE); + EXPECT(libj2_j2u_is_max(&a)); + EXPECT(end); + EXPECT(!*end); + + sprintf(buf, "%jx%jx0", UINTMAX_MAX, UINTMAX_MAX); + a = (struct libj2_j2u){111, 222}; + end = NULL; + EXPECT(libj2_str_to_j2u(buf, SIZE_MAX, &end, "0123456789abcdef", NULL, &a) == ERANGE); + EXPECT(libj2_j2u_is_max(&a)); + EXPECT(end); + EXPECT(!*end); + + sprintf(buf, "1%jx%jx", UINTMAX_MAX, UINTMAX_MAX); + a = (struct libj2_j2u){111, 222}; + end = NULL; + EXPECT(libj2_str_to_j2u(buf, SIZE_MAX, &end, "0123456789abcdef", NULL, &a) == ERANGE); + EXPECT(libj2_j2u_is_max(&a)); + EXPECT(end); + EXPECT(!*end); + + return 0; +} + +#endif -- cgit v1.2.3-70-g09d2