From 82bea0ebf89f68a59365ac38f4c56f9be2bc75fa Mon Sep 17 00:00:00 2001 From: Mikhail Romanko Date: Sat, 15 Mar 2025 18:06:16 +0300 Subject: Refactor bigints, add int and float conv functions Added functions to convert from/to ints/floats. Floats are converted according to basic Steele&White algorithm (without speedup). --- CMakeLists.txt | 4 + include/BH/String.h | 84 ++++++ include/BH/Util.h | 18 ++ src/String/Core.c | 21 ++ src/String/Float.c | 814 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/String/Int.c | 234 +++++++++++++++ src/String/Int1120.c | 488 ------------------------------ src/String/String.h | 163 ---------- src/Util.c | 31 ++ test/src/TestString.c | 320 ++++++++++++++++++++ 10 files changed, 1526 insertions(+), 651 deletions(-) create mode 100644 src/String/Core.c create mode 100644 src/String/Float.c create mode 100644 src/String/Int.c delete mode 100644 src/String/Int1120.c delete mode 100644 src/String/String.h create mode 100644 test/src/TestString.c diff --git a/CMakeLists.txt b/CMakeLists.txt index b3f7f6a..94399fb 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -92,6 +92,9 @@ set(BH_SOURCE src/Math/Vec4i.c src/Queue.c src/Util.c + src/String/Int.c + src/String/Float.c + src/String/Core.c ) set(BH_HEADER @@ -104,6 +107,7 @@ set(BH_HEADER include/BH/Queue.h include/BH/Util.h include/BH/Thread.h + include ) set(BH_SOURCE_DUMMY diff --git a/include/BH/String.h b/include/BH/String.h index 021429c..70cb922 100644 --- a/include/BH/String.h +++ b/include/BH/String.h @@ -5,4 +5,88 @@ #include "Common.h" +void BH_StringFree(char *string); + + +char *BH_StringCopy(const char *string); + + +char *BH_StringFromDouble(double value, + char format, + int precision); + + +double BH_StringToDouble(const char *string, + size_t *size); + + +char *BH_StringFromInt8s(int8_t value, + int base); + + +char *BH_StringFromInt32s(int32_t value, + int base); + +char *BH_StringFromInt64s(int64_t value, + int base); + +char *BH_StringFromInt16s(int16_t value, + int base); + +char *BH_StringFromInt8u(uint8_t value, + int base); + + +char *BH_StringFromInt16u(uint16_t value, + int base); + + +char *BH_StringFromInt32u(uint32_t value, + int base); + + +char *BH_StringFromInt64u(uint64_t value, + int base); + + +int8_t BH_StringToInt8s(const char *string, + size_t *size, + int base); + + +int16_t BH_StringToInt16s(const char *string, + size_t *size, + int base); + + +int32_t BH_StringToInt32s(const char *string, + size_t *size, + int base); + + +int64_t BH_StringToInt64s(const char *string, + size_t *size, + int base); + + +uint8_t BH_StringToInt8u(const char *string, + size_t *size, + int base); + + +uint16_t BH_StringToInt16u(const char *string, + size_t *size, + int base); + + +uint32_t BH_StringToInt32u(const char *string, + size_t *size, + int base); + + +uint64_t BH_StringToInt64u(const char *string, + size_t *size, + int base); + + #endif /* BH_STRING_H */ diff --git a/include/BH/Util.h b/include/BH/Util.h index d88e47a..08ffb5c 100644 --- a/include/BH/Util.h +++ b/include/BH/Util.h @@ -5,6 +5,24 @@ #include "Common.h" +#define BH_FP_NORMAL 0x0000 +#define BH_FP_INFINITE 0x0001 +#define BH_FP_NAN 0x0002 +#define BH_FP_ZERO 0x0010 +#define BH_FP_NEGATIVE 0x0020 + + +/** + * Classifies the floating point \a value. + * + * \param value Value + * + * \return On success, returns BH_FP_NORMAL, BH_FP_ZERO, BH_FP_INFINITE, + * BH_FP_NAN or BH_FP_NEGATIVE. + */ +int BH_ClassifyDouble(double value); + + /** * Reads 16-bit unsigned integer from the \a buffer in little-endian format. * diff --git a/src/String/Core.c b/src/String/Core.c new file mode 100644 index 0000000..4dfef4b --- /dev/null +++ b/src/String/Core.c @@ -0,0 +1,21 @@ +#include +#include +#include + + +void BH_StringFree(char *string) +{ + free(string); +} + + +char *BH_StringCopy(const char *string) +{ + char *result; + + result = malloc(strlen(string) + 1); + if (result) + strcpy(result, string); + + return result; +} diff --git a/src/String/Float.c b/src/String/Float.c new file mode 100644 index 0000000..cb05017 --- /dev/null +++ b/src/String/Float.c @@ -0,0 +1,814 @@ +#include +#include +#include +#include +#include +#include +#include +#include + + +#define MAX(a,b) (((a)>(b))?(a):(b)) +#define MIN(a,b) (((a)<(b))?(a):(b)) +#define BUFSIZE 309 +#define DIGITS 70 +#define NORMAL 0 +#define ABSOLUTE 1 +#define RELATIVE 2 + + +typedef struct BInt { + int size; + uint16_t data[DIGITS]; +} BInt; + + +struct DragonState +{ + BInt r; + BInt s; + BInt mm; + BInt mp; + BInt tmp[5]; + int cutoff; + int k; +}; + + +static const BInt BInt1 = {1, {1}}; +static const BInt BInt10 = {1, {10}}; + + +static const uint8_t clzLookup[256] = +{ + 8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, + 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, + 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, + 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 +}; + + +static int BIntClz(uint16_t value) +{ + if (value & 0xFF00) + return clzLookup[(value >> 8) & 0xFF]; + else + return 8 + clzLookup[value & 0xFF]; +} + + +static void BIntTrim(BInt *in) +{ + while (in->size && !in->data[in->size - 1]) + in->size--; +} + + +static int BIntCompare(const BInt *a, + const BInt *b) +{ + int i; + + /* Compare by lengths */ + i = a->size - b->size; + if (a->size - b->size) + return a->size - b->size; + + /* Compare by blocks */ + for (i = a->size; i; i--) + { + if (a->data[i - 1] < b->data[i - 1]) + return -1; + else if (a->data[i - 1] > b->data[i - 1]) + return 1; + } + + return 0; +} + + +static void BIntAdd(const BInt *a, + const BInt *b, + BInt *out) +{ + uint32_t carry; + int i; + + assert(a->size + 1 <= DIGITS); + assert(b->size + 1 <= DIGITS); + + /* Addition loop */ + carry = 0; + for (i = 0; i < a->size || i < b->size; i++) + { + if (i < a->size) + carry += a->data[i]; + if (i < b->size) + carry += b->data[i]; + + out->data[i] = carry & 0xFFFF; + carry = (carry >> 16); + } + + /* Handle new digit */ + if (carry) + out->data[i++] = carry; + + out->size = i; +} + + +static void BIntSub(const BInt *a, + const BInt *b, + BInt *out) +{ + uint32_t carry; + int i; + + /* Main subtraction loop */ + carry = 0; + for (i = 0; i < a->size || i < b->size; i++) + { + if (i < a->size) + carry += a->data[i]; + if (i < b->size) + carry -= b->data[i]; + + out->data[i] = carry & 0xFFFF; + carry = (carry & 0xFFFF0000) | (carry >> 16); + } + + /* Trim leading zeros */ + out->size = a->size; + BIntTrim(out); +} + + +static void BIntMul(const BInt *a, + const BInt *b, + BInt *out) +{ + uint32_t carry; + int i, j; + + assert(a->size + b->size <= DIGITS); + + /* Zero out the result */ + memset(out->data, 0, sizeof(out->data)); + for (i = 0; i < DIGITS; i++) + out->data[i] = 0; + + /* Multiplication loop */ + for (i = 0; i < a->size; i++) + { + carry = 0; + for (j = 0; j < b->size; j++) + { + carry += out->data[i + j]; + carry += (uint32_t)a->data[i] * (uint32_t)b->data[j]; + out->data[i + j] = carry & 0xFFFF; + carry = (carry >> 16); + } + out->data[i + j] += carry; + } + + /* Trim leading zeros */ + out->size = a->size + b->size; + BIntTrim(out); +} + + +static void BIntMulDigit(const BInt *a, + uint16_t b, + BInt *out) +{ + uint32_t carry; + int i; + + assert(a->size + 1 <= DIGITS); + + /* Multiplication loop */ + carry = 0; + for (i = 0; i < a->size; i++) + { + carry += (uint32_t)a->data[i] * b; + out->data[i] = carry & 0xFFFF; + carry = (carry >> 16); + } + out->data[i] = carry; + + /* Trim leading zeros */ + out->size = a->size + 1; + BIntTrim(out); +} + + +static void BIntLsh(const BInt *in, + int amount, + BInt *out) +{ + int blocks, bits, i; + uint16_t low, high; + + blocks = amount / 16; + bits = amount % 16; + + assert(in->size + blocks + (bits > 0) <= DIGITS); + + if (!in->size) + { + out->size = 0; + return; + } + + /* Main shift loop */ + if (bits) + { + high = 0; + for (i = in->size + blocks; i > blocks; i--) + { + low = in->data[i - blocks - 1] >> (16 - bits); + out->data[i] = low | high; + high = in->data[i - blocks - 1] << bits; + } + out->data[i] = high; + out->size = in->size + blocks + 1; + } + else + { + for (i = in->size; i; i--) + out->data[i - 1 + blocks] = in->data[i - 1]; + out->size = in->size + blocks; + } + + /* Trim leading zeros and zero out lower blocks */ + BIntTrim(out); + for (i = blocks; i; i--) + out->data[i - 1] = 0; +} + + +static void BIntRsh(const BInt *in, + int amount, + BInt *out) +{ + int blocks, bits, i; + uint16_t low, high; + + blocks = amount / 16; + bits = amount % 16; + + /* Zero size input or shift is bigger then input */ + if (in->size == 0 || in->size <= blocks) + { + out->size = 0; + return; + } + + /* Shift and copy parts of two blocks */ + low = in->data[blocks] >> bits; + high = 0; + for (i = 0; i < in->size - blocks - 1; i++) + { + high = in->data[i + blocks + 1] << (16 - bits); + out->data[i] = low | high; + low = in->data[i + blocks + 1] >> bits; + } + out->data[in->size - blocks - 1] = low; + + /* Trim leading zeros */ + out->size = in->size - blocks; + BIntTrim(out); +} + + +static uint16_t BIntGuess(const BInt *a, + const BInt *b) +{ + uint32_t tmp; + + if (BIntCompare(a, b) < 0) + return 0; + + tmp = a->data[a->size - 1]; + if (a->size != b->size) + tmp = tmp << 16 | a->data[a->size - 2]; + + return tmp / b->data[b->size - 1]; +} + + +static void BIntDiv(const BInt *a, + const BInt *b, + BInt *q, + BInt *r, + BInt *tmp) +{ + uint16_t digit; + int shift; + + /* Handle case where a is less then b */ + if (BIntCompare(a, b) < 0) + { + *r = *a; + q->size = 0; + return; + } + + /* Normilize input to reduce tries */ + shift = BIntClz(b->data[b->size - 1]); + BIntLsh(a, shift, &tmp[0]); + BIntLsh(b, shift, &tmp[1]); + + /* Prepare first step of the division */ + q->size = 0; + r->size = 0; + while (BIntCompare(r, &tmp[1]) < 0) + { + BIntLsh(r, 16, r); + r->data[0] = tmp[0].data[--tmp[0].size]; + r->size += !r->size; + } + + while (1) + { + /* Make a guess and check */ + digit = BIntGuess(r, &tmp[1]); + BIntMulDigit(&tmp[1], digit, &tmp[2]); + while (BIntCompare(r, &tmp[2]) < 0) + { + --digit; + BIntSub(&tmp[2], &tmp[1], &tmp[2]); + } + + /* Store digit in quotient */ + BIntSub(r, &tmp[2], r); + BIntLsh(q, 16, q); + q->data[0] = digit; + q->size += !q->size; + + /* Fetch next digit or exit */ + if (!tmp[0].size) + break; + + BIntLsh(r, 16, r); + r->data[0] = tmp[0].data[--tmp[0].size]; + if (!r->size) + r->size = 1; + } + + /* Normilize remainder */ + BIntRsh(r, shift, r); +} + + +static void dragonFixup(struct DragonState *state, + int precision, + int mode, + uint64_t f) +{ + if (f == (((uint64_t)1) << 52)) + { + BIntLsh(&state->mp, 1, &state->mp); + BIntLsh(&state->r, 1, &state->r); + BIntLsh(&state->s, 1, &state->s); + } + state->k = 0; + + BIntDiv(&state->s, &BInt10, &state->tmp[0], &state->tmp[1], state->tmp + 2); + if (state->tmp[1].size) + BIntAdd(&state->tmp[0], &BInt1, &state->tmp[0]); + + while (BIntCompare(&state->r, &state->tmp[0]) < 0) + { + state->k -= 1; + BIntMulDigit(&state->r, 10, &state->r); + BIntMulDigit(&state->mm, 10, &state->mm); + BIntMulDigit(&state->mp, 10, &state->mp); + BIntDiv(&state->s, &BInt10, &state->tmp[0], &state->tmp[1], state->tmp + 2); + if (state->tmp[1].size) + BIntAdd(&state->tmp[0], &BInt1, &state->tmp[0]); + } + + BIntLsh(&state->r, 1, &state->tmp[0]); + BIntAdd(&state->tmp[0], &state->mp, &state->tmp[0]); + BIntLsh(&state->s, 1, &state->tmp[1]); + while (BIntCompare(&state->tmp[0], &state->tmp[1]) >= 0) + { + state->k += 1; + BIntMulDigit(&state->s, 10, &state->s); + BIntLsh(&state->s, 1, &state->tmp[1]); + } + + if (mode == NORMAL) + state->cutoff = state->k - BUFSIZE; + else if (mode == RELATIVE) + state->cutoff = state->k - precision; + else + state->cutoff = -precision; +} + + +static void dragonRound(struct DragonState *state, + char *buffer, + int *k, + int *size, + int high, + int low, + char s) +{ + int i; + + /* Check if rounding up required */ + if (high == low) + { + BIntLsh(&state->r, 1, &state->tmp[0]); + i = BIntCompare(&state->tmp[0], &state->s); + if (i < 0) { low = 1; high = 0; } + else if (i > 0) { low = 0; high = 1; } + else low = (((s - '0') & 0x1) == 0); + } + + /* Perform rounding up */ + if (!low) + { + for (i = *size; i && buffer[i - 1] == '9'; i--) + buffer[i - 1] = '0'; + + if (i > 0) + buffer[i - 1]++; + else + { + buffer[0] = '1'; + (*k)++; + } + } +} + + +static void dragon(double value, + int precision, + int mode, + char *buffer, + int *size, + int *k) +{ + struct DragonState state; + int low, high, e; + uint64_t f; + char s; + + *k = 0; + *size = low = high = 0; + + /* If value is zero - do nothing */ + if (!value) + { + buffer[(*size)++] = '0'; + return; + } + + /* Prepare dragon */ + f = frexp(value, &e) * ((uint64_t)1 << 53); + state.r.data[0] = f & 0xFFFF; state.r.data[1] = (f >> 16) & 0xFFFF; + state.r.data[2] = (f >> 32) & 0xFFFF; state.r.data[3] = (f >> 48) & 0xFFFF; + state.r.size = 4; BIntTrim(&state.r); + + BIntLsh(&state.r, MAX(e - 53, 0), &state.r); + BIntLsh(&BInt1, MAX(0, -(e - 53)), &state.s); + BIntLsh(&BInt1, MAX(e - 53, 0), &state.mm); + BIntLsh(&BInt1, MAX(e - 53, 0), &state.mp); + dragonFixup(&state, precision, mode, f); + + /* Main digit generation loop */ + *k = state.k - 1; + while(1) + { + state.k -= 1; + BIntMulDigit(&state.r, 10, &state.r); + BIntDiv(&state.r, &state.s, &state.tmp[0], &state.r, state.tmp + 1); + + s = '0'; + if (state.tmp[0].size) + s += state.tmp[0].data[0]; + buffer[(*size)++] = s; + + if (mode == NORMAL) + { + BIntLsh(&state.r, 1, &state.tmp[1]); + BIntLsh(&state.s, 1, &state.tmp[2]); + BIntSub(&state.tmp[2], &state.mp, &state.tmp[2]); + BIntMulDigit(&state.mm, 10, &state.mm); + BIntMulDigit(&state.mp, 10, &state.mp); + low = BIntCompare(&state.tmp[1], &state.mm) < 0; + high = BIntCompare(&state.tmp[1], &state.tmp[2]) > 0; + if (low || high || state.k == state.cutoff || *size >= BUFSIZE) + break; + } + else + { + if (!state.r.size || state.k == state.cutoff || *size >= BUFSIZE) + break; + } + } + + /* Round digits if required */ + dragonRound(&state, buffer, k, size, high, low, s); +} + + +static char *formatF(char buffer[BUFSIZE], + int precision, + int sign, + int k, + int size) +{ + char *result, *current; + int i; + + result = malloc(MAX(0, k) + 5 + sign + precision); + current = result; + if (!result) + return NULL; + + /* Add sign */ + if (sign) + *(current++) = '-'; + + /* Pad if exponent is small */ + if (k < 0) + { + *(current++) = '0'; + + if (precision > 0) + *(current++) = '.'; + + for (i = 0; i < MIN(-k - 1, precision); i++) + *(current++) = '0'; + } + + /* Add digits */ + for (i = 0; k >= -precision; i++, k--) + { + if (i < size) + *(current++) = buffer[i]; + else + *(current++) = '0'; + + if (k == 0 && precision > 0) + *(current++) = '.'; + } + + *(current++) = 0; + return result; +} + + +static char *formatE(char buffer[BUFSIZE], + int precision, + int sign, + int k, + int size, + int upper) +{ + char *result, *current; + int i; + + result = malloc(9 + sign + precision); + current = result; + if (!result) + return NULL; + + /* Add sign and digits */ + if (sign) + *(current++) = '-'; + + for (i = 0; i < size; i++) + { + *(current++) = buffer[i]; + if (i == 0 && precision > 0) + *(current++) = '.'; + } + + /* Pad to specified precision */ + for (; i < precision + 1; i++) + *(current++) = '0'; + + /* Add exponent symbol and sign */ + *(current++) = "eE"[upper]; + if (k < 0) + { + *(current++) = '-'; + k = -k; + } + else + *(current++) = '+'; + + /* Convert exponent to digits and add them */ + for (size = 0; k || size < 2; size++) + { + buffer[size] = '0' + k % 10; + k = k / 10; + } + for (; size; size--) + *(current++) = buffer[size - 1]; + + *(current++) = 0; + return result; +} + + +static char *generateF(double value, + int precision, + int sign) +{ + char buffer[BUFSIZE]; + int size, k; + + /* Call Dragon4 and format the digits */ + if (precision < 0) + dragon(value, 0, NORMAL, buffer, &size, &k); + else + dragon(value, precision, ABSOLUTE, buffer, &size, &k); + + if (precision < 0) + precision = MAX(0, size - k - 1); + + return formatF(buffer, precision, sign, k, size); +} + + +static char *generateE(double value, + int precision, + int upper, + int sign) +{ + char buffer[BUFSIZE]; + int size, k; + + /* Adjust precision and call Dragon4 to generate digits */ + if (precision < 0) + dragon(value, 0, NORMAL, buffer, &size, &k); + else + dragon(value, (precision + 1), RELATIVE, buffer, &size, &k); + + if (precision < 0) + precision = size - 1; + + return formatE(buffer, precision, sign, k, size, upper); +} + + +static char *generateG(double value, + int precision, + int upper, + int sign) +{ + char buffer[BUFSIZE]; + int size, k, fixed; + + if (precision == 0) + precision = 1; + + /* Call Dragon4 to generate digits */ + if (precision < 0) + { + dragon(value, 0, NORMAL, buffer, &size, &k); + fixed = k >= -4 && k <= (size - 1); + } + else + { + dragon(value, precision, RELATIVE, buffer, &size, &k); + fixed = k >= -4 && k < precision; + + /* Remove trailing zeros and adjust precision */ + for (; size && precision > 0 && buffer[size - 1] == '0'; size--, precision--); + } + + if (fixed) + { + precision = MAX(0, size - k - 1); + return formatF(buffer, precision, sign, k, size); + } + else + { + precision = MAX(0, size - 1); + return formatE(buffer, precision, sign, k, size, upper); + } +} + + +char *BH_StringFromDouble(double value, + char format, + int precision) +{ + static const char *infStrings[] = { "inf", "-inf", "INF", "-INF" }; + static const char *nanStrings[] = { "nan", "NAN" }; + int sign, type, upper; + + type = BH_ClassifyDouble(value); + upper = isupper(format) > 0; + sign = (type & BH_FP_NEGATIVE) != 0; + + if (sign) + value = fabs(value); + + /* Handle NaN and Inf */ + if (type == BH_FP_INFINITE) + return BH_StringCopy(infStrings[upper * 2 + sign]); + else if (type == BH_FP_NAN) + return BH_StringCopy(nanStrings[upper]); + + if (format == 'g' || format == 'G') + return generateG(value, precision, upper, sign); + else if (format == 'e' || format == 'E') + return generateE(value, precision, upper, sign); + else + return generateF(value, precision, sign); +} + + +double BH_StringToDouble(const char *string, + size_t *size) +{ + int nsign, esign, e, dot; + const char *current; + char buffer[4]; + size_t count; + + nsign = 0; esign = 0; e = 0; count = 0; dot = 0; + current = string; + + /* Skip whitespace */ + while (isspace(*current)) + current++; + + /* Leading sign */ + if (*current == '+' || *current == '-') + { + if (*current == '-') + nsign = 1; + current++; + } + + /* Read integer part of the float */ + for (; isdigit(*current); current++) + { + if (count < sizeof(buffer) && (count || *current != '0')) + buffer[count++] = *current; + else if (count >= sizeof(buffer)) + dot--; + } + + /* Read fract part of the float */ + if (*current == '.') + current++; + + for (; isdigit(*current); current++) + { + if ((count < sizeof(buffer))) + { + dot++; + if ((count || *current != '0')) + buffer[count++] = *current; + } + } + + /* Read exp part of the float */ + if (*current == 'e' || *current == 'E') + { + current++; + if (*current == '+' || *current == '-') + { + if (*current == '-') + esign = 1; + current++; + } + + for (; isdigit(*current); current++) + e = e * 10 + *current - '0'; + } + + if (esign) + e = -e; + e -= dot; + + if (size) + *size = current - string; + + BH_UNUSED(nsign); + BH_UNUSED(BIntMul); + return 0.0; +} diff --git a/src/String/Int.c b/src/String/Int.c new file mode 100644 index 0000000..90379d9 --- /dev/null +++ b/src/String/Int.c @@ -0,0 +1,234 @@ +#include +#include +#include +#include +#include + + +static const char digits[] = "0123456789abcdefghijklmnopqrstuvwxyz"; +static const char lookup[] = +{ + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, + -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, + 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, -1, -1, -1, -1, -1, -1, + -1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, + 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, -1, -1, -1, -1, -1, + -1, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, + 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, -1, -1, -1, -1, -1, +}; + + +static void skipSpace(const char **string, + size_t *size) +{ + while (isspace(**string)) + { + (*string)++; + if (size) (*size)++; + } +} + + +static void handleSign(const char **string, + size_t *size, + int *sign) +{ + *sign = 1; + if (**string == '-') + { + *sign = -1; (*string)++; + if (size) (*size)++; + } +} + + +static void guessBase(const char **string, + size_t *size, + int *base) +{ + if (*base != 0) + return; + + *base = 10; + if (**string != '0') + return; + + (*string)++; + if (size) + (*size)++; + + switch (**string) + { + case 'x': case 'X': + *base = 16; + (*string)++; + if (size) + (*size)++; + break; + + case 'b': case 'B': + *base = 2; + (*string)++; + if (size) + (*size)++; + break; + + default: + *base = 8; + } +} + + +#define TEMPLATE_IMPL \ + char tmp[sizeof(value) * CHAR_BIT + 1]; char *current, *end, *result; \ + int sign; end = tmp + sizeof(tmp); current = end; sign = 0; \ + if (value < 0) { sign = 1; value = -value; } while (value) { \ + *(--current) = digits[value % base]; value /= base; } \ + if (sign) { *(--current) = '-'; } result = malloc(end - current + 1); \ + if (!result) { return NULL; } memcpy(result, current, end - current); \ + result[end - current] = 0; return result; + + +char *BH_StringFromInt8s(int8_t value, + int base) +{ + TEMPLATE_IMPL +} + + +char *BH_StringFromInt16s(int16_t value, + int base) +{ + TEMPLATE_IMPL +} + + +char *BH_StringFromInt32s(int32_t value, + int base) +{ + TEMPLATE_IMPL +} + + +char *BH_StringFromInt64s(int64_t value, + int base) +{ + TEMPLATE_IMPL +} + + +#undef TEMPLATE_IMPL +#define TEMPLATE_IMPL \ + char tmp[sizeof(value) * CHAR_BIT]; char *current, *end, *result; \ + end = tmp + sizeof(tmp); current = end; while (value) { \ + *(--current) = digits[value % base]; value /= base; } \ + result = malloc(end - current + 1); if (!result) { return NULL; } \ + memcpy(result, current, end - current); result[end - current] = 0; \ + return result; + + +char *BH_StringFromInt8u(uint8_t value, + int base) +{ + TEMPLATE_IMPL +} + + +char *BH_StringFromInt16u(uint16_t value, + int base) +{ + TEMPLATE_IMPL +} + + +char *BH_StringFromInt32u(uint32_t value, + int base) +{ + TEMPLATE_IMPL +} + + +char *BH_StringFromInt64u(uint64_t value, + int base) +{ + TEMPLATE_IMPL +} + + +#undef TEMPLATE_IMPL +#define TEMPLATE_IMPL(type) \ + type result = 0; int sign, flag = 0; char sym; *size = 0; \ + if (base != 0 && (base < 2 || base > 36)) { return 0; } \ + skipSpace(&string, size); handleSign(&string, size, &sign); \ + guessBase(&string, size, &base); while(*string) { sym = *(string++); \ + sym = lookup[(unsigned int)sym]; if (sym >= base || sym == -1) { break; } \ + if (size) { (*size)++; } result = result * base + sym; flag = 1; } \ + if (!result && !flag && size) { *size = 0; } return result * sign; + + +int8_t BH_StringToInt8s(const char *string, + size_t *size, + int base) +{ + TEMPLATE_IMPL(int8_t) +} + + +int16_t BH_StringToInt16s(const char *string, + size_t *size, + int base) +{ + TEMPLATE_IMPL(int16_t) +} + + +int32_t BH_StringToInt32s(const char *string, + size_t *size, + int base) +{ + TEMPLATE_IMPL(int32_t) +} + + +int64_t BH_StringToInt64s(const char *string, + size_t *size, + int base) +{ + TEMPLATE_IMPL(int64_t) +} + + +uint8_t BH_StringToInt8u(const char *string, + size_t *size, + int base) +{ + TEMPLATE_IMPL(uint8_t) +} + + +uint16_t BH_StringToInt16u(const char *string, + size_t *size, + int base) +{ + TEMPLATE_IMPL(uint16_t) +} + + +uint32_t BH_StringToInt32u(const char *string, + size_t *size, + int base) +{ + TEMPLATE_IMPL(uint32_t) +} + + +uint64_t BH_StringToInt64u(const char *string, + size_t *size, + int base) +{ + TEMPLATE_IMPL(uint64_t) +} + + +#undef TEMPLATE_IMPL diff --git a/src/String/Int1120.c b/src/String/Int1120.c deleted file mode 100644 index 4a8e2ca..0000000 --- a/src/String/Int1120.c +++ /dev/null @@ -1,488 +0,0 @@ -#include "String.h" - -#include -#include -#include - - -static const uint8_t clzLookup[256] = -{ - 8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4, - 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, - 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, - 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, - 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, - 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, - 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, - 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, - 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 -}; - - -static const uint16_t pow10Data[] = -{ - 0x0001, 0x000A, 0x0064, 0x2710, 0xE100, 0x05F5, 0x0000, 0x6FC1, - 0x86F2, 0x0023, 0x0000, 0x0000, 0xEF81, 0x85AC, 0x415B, 0x2D6D, - 0x04EE, 0x0000, 0x0000, 0x0000, 0x0000, 0x1F01, 0xBF6A, 0xED64, - 0x6E38, 0x97ED, 0xDAA7, 0xF9F4, 0xE93F, 0x4F03, 0x0018, 0x0000, - 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x3E01, - 0x2E95, 0x9909, 0x03DF, 0x38FD, 0x0F15, 0xE42F, 0x2374, 0xF5EC, - 0xD3CF, 0xDC08, 0xC404, 0xB0DA, 0xBCCD, 0x7F19, 0xA633, 0x2603, - 0xE91F, 0x024E, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, - 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, - 0x0000, 0x0000, 0x7C01, 0x982E, 0x875B, 0xBED3, 0x9F72, 0xD8D9, - 0x2F87, 0x1215, 0x50C6, 0x6BDE, 0x6E70, 0xCF4A, 0xD80F, 0xD595, - 0x716E, 0x26B2, 0x66B0, 0xADC6, 0x3624, 0x1D15, 0xD35A, 0x3C42, - 0x540E, 0x63FF, 0x73C0, 0xCC55, 0xEF17, 0x65F9, 0x28F2, 0x55BC, - 0xC7F7, 0x80DC, 0xEDDC, 0xF46E, 0xEFCE, 0x5FDC, 0x53F7, 0x0005, -}; - - -static const int pow10Index[] = -{ - 0, 1, 2, 3, 4, 6, 10, 17, 31, 58, -}; - - -static const int pow10Size[] = -{ - 1, 1, 1, 1, 2, 4, 7, 14, 27, 54, -}; - - -static void pow10Set(int index, - BH_Int1120 *out) -{ - out->size = pow10Size[index]; - memcpy(out->digits, pow10Data + pow10Index[index], out->size * sizeof(uint16_t)); -} - - -int BH_Int1120Clz(const uint16_t value) -{ - - - if (value & 0xFF00) - return clzLookup[(value >> 8) & 0xFF]; - else - return 8 + clzLookup[value & 0xFF]; -} - - -int BH_Int1120Compare(const BH_Int1120 *a, - const BH_Int1120 *b) -{ - int i, result; - - /* Compare by lengths */ - result = a->size - b->size; - if (result) - return result; - - /* Compare by blocks */ - for (i = a->size; i; i--) - { - if (a->digits[i - 1] < b->digits[i - 1]) - return -1; - else if (a->digits[i - 1] > b->digits[i - 1]) - return 1; - } - - return 0; -} - - -void BH_Int1120Add(const BH_Int1120 *a, - const BH_Int1120 *b, - BH_Int1120 *out) -{ - const BH_Int1120 *small, *big; - uint32_t carry, tmp; - int i; - - small = b; - big = a; - - assert(a->size + 1 <= BH_INT1120_DIGITS); - assert(b->size + 1 <= BH_INT1120_DIGITS); - - /* Find smaller interger */ - if (a->size < b->size) - { - small = a; - big = b; - } - - /* Main addition loop */ - carry = 0; - for (i = 0; i < small->size; i++) - { - tmp = (uint32_t)small->digits[i] + (uint32_t)big->digits[i] + carry; - carry = (tmp >> 16) & 0xFFFF; - out->digits[i] = tmp & 0xFFFF; - } - - /* Carry propogation */ - for (; i < big->size; i++) - { - tmp = (uint32_t)big->digits[i] + carry; - carry = (tmp >> 16) & 0xFFFF; - out->digits[i] = tmp & 0xFFFF; - } - - /* Handle carry */ - if (carry) - out->digits[i++] = carry; - - out->size = i; -} - - -void BH_Int1120Sub(const BH_Int1120 *a, - const BH_Int1120 *b, - BH_Int1120 *out) -{ - uint32_t carry, tmp; - int i; - - /* Main subtraction loop */ - carry = 0; - for (i = 0; i < b->size; i++) - { - tmp = (uint32_t)a->digits[i] - (uint32_t)b->digits[i] - carry; - carry = (tmp >> 31) & 0x1; - out->digits[i] = tmp & 0xFFFF; - } - - /* Carry propogation */ - for (; i < a->size; i++) - { - tmp = (uint32_t)a->digits[i] - carry; - carry = (tmp >> 31) & 0x1; - out->digits[i] = tmp & 0xFFFF; - } - - /* Truncate length on empty blocks */ - out->size = a->size; - while(out->size && !out->digits[out->size - 1]) - out->size--; -} - - -void BH_Int1120Mul(const BH_Int1120 *a, - const BH_Int1120 *b, - BH_Int1120 *out) -{ - int i, j; - uint32_t tmp, carry; - - assert(a->size + b->size <= BH_INT1120_DIGITS); - - for (i = 0; i < BH_INT1120_DIGITS; i++) - out->digits[i] = 0; - - for (i = 0; i < a->size; i++) - { - carry = 0; - - /* Multiplication loop */ - for (j = 0; j < b->size; j++) - { - carry += (uint32_t)out->digits[i + j]; - tmp = (uint32_t)a->digits[i] * (uint32_t)b->digits[j] + carry; - carry = (tmp >> 16) & 0xFFFF; - out->digits[i + j] = tmp & 0xFFFF; - } - - /* Carry propagation */ - if (carry) - { - tmp = (uint32_t)out->digits[i + j] + carry; - out->digits[i + j] = tmp & 0xFFFF; - } - } - - out->size = a->size + b->size; - if (!out->digits[out->size - 1]) - out->size--; -} - - -void BH_Int1120MulDigit(const BH_Int1120 *in, - uint16_t digit, - BH_Int1120 *out) -{ - int i; - uint32_t tmp, carry; - - assert(in->size + 1 <= BH_INT1120_DIGITS); - - for (i = 0; i < BH_INT1120_DIGITS; i++) - out->digits[i] = 0; - - /* Multiplication loop */ - carry = 0; - for (i = 0; i < in->size; i++) - { - carry += (uint32_t)out->digits[i]; - tmp = (uint32_t)in->digits[i] * digit + carry; - carry = (tmp >> 16) & 0xFFFF; - out->digits[i] = tmp & 0xFFFF; - } - - /* Carry propagation */ - if (carry) - { - tmp = (uint32_t)out->digits[i] + carry; - out->digits[i] = tmp & 0xFFFF; - } - - out->size = in->size + 1; - if (!out->digits[out->size - 1]) - out->size--; -} - - -static uint16_t BH_Int1120DivGuess(const BH_Int1120 *a, - const BH_Int1120 *b) -{ - uint32_t tmp; - - /* Compare two values */ - if (BH_Int1120Compare(a, b) < 0) - return 0; - - /* Make a guess */ - tmp = a->digits[a->size - 1]; - if (a->size != b->size) - tmp = tmp << 16 | a->digits[a->size - 2]; - - return tmp / b->digits[b->size - 1]; -} - - -void BH_Int1120Div(const BH_Int1120 *a, - const BH_Int1120 *b, - BH_Int1120 *q, - BH_Int1120 *r) -{ - BH_Int1120 left, right, tmp; - uint16_t guess; - int shift; - - assert(a->size >= b->size); - assert(b->size > 0); - - /* Normilize input to reduce tries */ - shift = BH_Int1120Clz(b->digits[b->size - 1]); - BH_Int1120Lsh(a, shift, &left); - BH_Int1120Lsh(b, shift, &right); - - /* Prepare first step of the division */ - q->size = 0; - r->size = 0; - while (BH_Int1120Compare(r, &right) < 0) - { - BH_Int1120Lsh(r, 16, r); - r->digits[0] = left.digits[--left.size]; - - if (!r->size) - r->size = 1; - } - - while (1) - { - /* Make a guess and check */ - guess = BH_Int1120DivGuess(r, &right); - BH_Int1120MulDigit(&right, guess, &tmp); - - /* If the guess was wrong - decrement guess and try again */ - while (BH_Int1120Compare(r, &tmp) < 0) - BH_Int1120MulDigit(&right, --guess, &tmp); - - /* Store digit in quotient */ - BH_Int1120Lsh(q, 16, q); - q->digits[0] = guess; - if (!q->size) - q->size = 1; - - /* Adjust remainder */ - BH_Int1120Sub(r, &tmp, r); - - /* Fetch next digit or exit */ - if (!left.size) - break; - - BH_Int1120Lsh(r, 16, r); - r->digits[0] = left.digits[--left.size]; - if (!r->size) - r->size = 1; - } - - /* Normilize remainder */ - BH_Int1120Rsh(r, shift, r); -} - - -void BH_Int1120Pow10(int exponent, - BH_Int1120 *out) -{ - BH_Int1120 one; - - one.digits[0] = 1; - one.size = 1; - BH_Int1120MulPow10(&one, exponent, out); -} - - -void BH_Int1120MulPow10(const BH_Int1120 *in, - int exponent, - BH_Int1120 *out) -{ - BH_Int1120 *current, *next, *swap; - BH_Int1120 tmp[2], factor; - int index; - - /* Make sure exponent is low, otherwise we get an overflow */ - assert(exponent < 512); - - /* Prepare variables and temporaries */ - current = tmp; - next = tmp + 1; - index = 0; - *current = *in; - - /* Main multiply loop */ - while (exponent) - { - if (exponent & 0x1) - { - pow10Set(index, &factor); - BH_Int1120Mul(current, &factor, next); - swap = current; - current = next; - next = swap; - } - index++; - exponent >>= 1; - } - *out = *current; -} - - -void BH_Int1120Pow2(int exponent, - BH_Int1120 *out) -{ - int blocks, bits, i; - - assert(exponent < 1120); - blocks = exponent / 16; - bits = exponent % 16; - - /* Zero out blocks and set one bit */ - for (i = 0; i < blocks; i++) - out->digits[i] = 0; - - out->digits[blocks] = (1 << bits); - out->size = blocks; -} - - -void BH_Int1120Lsh(const BH_Int1120 *in, - int amount, - BH_Int1120 *out) -{ - int blocks, bits, i; - uint16_t low, high; - - /* No input - no output */ - if (in->size == 0) - return; - - blocks = amount / 16; - bits = amount % 16; - - assert(in->size + blocks + (bits > 0) <= BH_INT1120_DIGITS); - - if (bits) - { - /* Shift and copy parts of two blocks */ - low = 0; - high = in->digits[in->size - 1] >> (16 - bits); - for (i = in->size; i > 1; i--) - { - out->digits[i + blocks] = high | low; - low = in->digits[i - 1] << bits; - high = in->digits[i - 2] >> (16 - bits); - } - out->digits[blocks + 1] = high | low; - out->digits[blocks] = in->digits[0] << bits; - out->size = in->size + blocks + 1; - } - else - { - /* Copy whole blocks */ - for (i = in->size; i; i--) - out->digits[i - 1 + blocks] = in->digits[i - 1]; - out->size = in->size + blocks; - } - - /* Check upper block */ - if (!out->digits[out->size - 1]) - out->size--; - - /* Zero out lower blocks */ - for (i = blocks; i; i--) - out->digits[i - 1] = 0; -} - - -void BH_Int1120Rsh(const BH_Int1120 *in, - int amount, - BH_Int1120 *out) -{ - int blocks, bits, i; - uint16_t low, high; - - /* No input - no output */ - if (in->size == 0) - return; - - blocks = amount / 16; - bits = amount % 16; - - if (bits) - { - /* Shift and copy parts of two blocks */ - low = in->digits[blocks] >> bits; - high = in->digits[blocks + 1] << (16 - bits); - - for (i = 0; i < in->size - blocks - 2; i++) - { - out->digits[i] = low | high; - low = in->digits[i + blocks + 1] >> bits; - high = in->digits[i + blocks + 2] << (16 - bits); - } - - out->digits[in->size - blocks - 2] = low | high; - out->digits[in->size - blocks - 1] = in->digits[in->size - 1] >> bits; - } - else - { - /* Copy whole blocks */ - for (i = 0; i < in->size - blocks; i++) - out->digits[i] = in->digits[i + blocks]; - } - - /* Check upper block */ - out->size = in->size - blocks; - if (!out->digits[out->size - 1]) - out->size--; -} diff --git a/src/String/String.h b/src/String/String.h deleted file mode 100644 index a7cad55..0000000 --- a/src/String/String.h +++ /dev/null @@ -1,163 +0,0 @@ -#ifndef BH_STRING_STRING_H -#define BH_STRING_STRING_H - - -#include - - -#define BH_INT1120_DIGITS 70 - - -typedef struct BH_Int1120 -{ - int size; - uint16_t digits[BH_INT1120_DIGITS]; -} BH_Int1120; - - -/** - * Counts the number of leading zero bits. - * - * \param value Value - * - * \return Count of leading zeros. - */ -int BH_Int1120Clz(const uint16_t value); - - -/** - * Compares big integers \a a and \a b. - * - * \param a A integer - * \param b B integer - * - * \return Negative if \a a is less than \a b - * \return Positive if \a a is greater than \a b - * \return Zero if \a a and \a b are equal. - */ -int BH_Int1120Compare(const BH_Int1120 *a, - const BH_Int1120 *b); - - -/** - * Adds two big integers \a a and \a b and stores result into \a out. - * - * \param a A integer - * \param b B integer - * \param out Result integer - */ -void BH_Int1120Add(const BH_Int1120 *a, - const BH_Int1120 *b, - BH_Int1120 *out); - - -/** - * Subtracts two big integers \a a and \a b and stores result into \a out. - * - * \param a A integer - * \param b B integer - * \param out Result integer - */ -void BH_Int1120Sub(const BH_Int1120 *a, - const BH_Int1120 *b, - BH_Int1120 *out); - - -/** - * Multiplies two big integers \a a and \a b and stores result into \a out. - * - * \param a A integer - * \param b B integer - * \param out Result integer - */ -void BH_Int1120Mul(const BH_Int1120 *a, - const BH_Int1120 *b, - BH_Int1120 *out); - - -/** - * Multiplies big integer \a a by \a digit and stores result into \a out. - * - * \param in Input integer - * \param digit Digit - * \param out Result integer - */ -void BH_Int1120MulDigit(const BH_Int1120 *in, - uint16_t digit, - BH_Int1120 *out); - - -/** - * Divides two big integers \a a and \a b and stores quotient into \a q and - * remainder into \a r. - * - * \param a A integer - * \param b B integer - * \param q Output quotient integer - * \param r Output remainder integer - */ -void BH_Int1120Div(const BH_Int1120 *a, - const BH_Int1120 *b, - BH_Int1120 *q, - BH_Int1120 *r); - - -/** - * Computes 10 to the power of \a exponent. - * - * \param exponent Exponent - * \param out Result integer - */ -void BH_Int1120Pow10(int exponent, - BH_Int1120 *out); - - -/** - * Multiplies a big integer \a in by 10 to the power of \a exponent. - * - * \param in Input integer - * \param exponent Exponent - * \param out Result integer - */ -void BH_Int1120MulPow10(const BH_Int1120 *in, - int exponent, - BH_Int1120 *out); - - -/** - * Computes 2 to the power of \a exponent. - * - * \param exponent Exponent - * \param out Result integer - */ -void BH_Int1120Pow2(int exponent, - BH_Int1120 *out); - - -/** - * Left shifts big integer \a in by \a amount places and stores result into - * \a out. - * - * \param in Input integer - * \param amount Shift amount - * \param out Result integer - */ -void BH_Int1120Lsh(const BH_Int1120 *in, - int amount, - BH_Int1120 *out); - - -/** - * Right shifts big integer \a in by \a amount places and stores result into - * \a out. - * - * \param in Input integer - * \param amount Shift amount - * \param out Result integer - */ -void BH_Int1120Rsh(const BH_Int1120 *in, - int amount, - BH_Int1120 *out); - - -#endif /* BH_STRING_STRING_H */ diff --git a/src/Util.c b/src/Util.c index b388fed..a615308 100644 --- a/src/Util.c +++ b/src/Util.c @@ -23,6 +23,37 @@ union I64 }; +union F64 +{ + double f; + uint64_t u64; +}; + + +int BH_ClassifyDouble(double value) +{ + union F64 tmp; + uint64_t fract; + int exp, negative; + + tmp.f = value; + exp = (tmp.u64 >> 52) & 0x7FF; + fract = (tmp.u64 & (((uint64_t)1 << 52) - 1)); + negative = (tmp.u64 >> 63) ? (BH_FP_NEGATIVE) : (0); + + if (exp == 0 && fract == 0) + return BH_FP_ZERO | negative; + + if (exp == 2047 && fract == 0) + return BH_FP_INFINITE | negative; + + if (exp == 2047 && fract) + return BH_FP_NAN; + + return BH_FP_NORMAL | negative; +} + + uint16_t BH_Read16LEu(const char *buffer) { union I16 tmp; diff --git a/test/src/TestString.c b/test/src/TestString.c new file mode 100644 index 0000000..53811cf --- /dev/null +++ b/test/src/TestString.c @@ -0,0 +1,320 @@ +#include +#include +#include +#include +#include +#include + + +static int compareString(double value, + int format, + int precision, + const char *ref) +{ + int result; + char *str; + + str = BH_StringFromDouble(value, format, precision); + result = strcmp(str, ref); + if (result) + printf("Value: %.17g\tReference: %s\tGot: %s\n", value, ref, str); + + BH_StringFree(str); + + return result; +} + + +static int roundtripString(double value, + int format) +{ + double result; + char *str; + + str = BH_StringFromDouble(value, format, -1); + result = strtod(str, NULL); + if (result != value) + printf("Value: %.17g\tGot: %.17g\tStr: %s\n", value, result, str); + + BH_StringFree(str); + + return result != value; +} + + +BH_UNIT_TEST(FixedFormat) +{ + BH_VERIFY(compareString(30.0159265358979323846, 'f', 0, "30") == 0); + BH_VERIFY(compareString(30.0159265358979323846, 'f', 1, "30.0") == 0); + BH_VERIFY(compareString(30.0159265358979323846, 'f', 2, "30.02") == 0); + BH_VERIFY(compareString(30.0159265358979323846, 'f', 3, "30.016") == 0); + BH_VERIFY(compareString(30.0159265358979323846, 'f', 4, "30.0159") == 0); + BH_VERIFY(compareString(30.0159265358979323846, 'f', 5, "30.01593") == 0); + BH_VERIFY(compareString(-30.0159265358979323846, 'f', 0, "-30") == 0); + BH_VERIFY(compareString(-30.0159265358979323846, 'f', 1, "-30.0") == 0); + BH_VERIFY(compareString(-30.0159265358979323846, 'f', 2, "-30.02") == 0); + BH_VERIFY(compareString(-30.0159265358979323846, 'f', 3, "-30.016") == 0); + BH_VERIFY(compareString(-30.0159265358979323846, 'f', 4, "-30.0159") == 0); + BH_VERIFY(compareString(-30.0159265358979323846, 'f', 5, "-30.01593") == 0); + + BH_VERIFY(compareString(0.0, 'f', 0, "0") == 0); + BH_VERIFY(compareString(0.0, 'f', 1, "0.0") == 0); + BH_VERIFY(compareString(-0.0, 'f', 0, "-0") == 0); + BH_VERIFY(compareString(-0.0, 'f', 1, "-0.0") == 0); + + BH_VERIFY(compareString(0.00015425, 'f', 0, "0") == 0); + BH_VERIFY(compareString(0.00015425, 'f', 1, "0.0") == 0); + BH_VERIFY(compareString(0.00015425, 'f', 2, "0.00") == 0); + BH_VERIFY(compareString(0.00015425, 'f', 3, "0.000") == 0); + BH_VERIFY(compareString(0.00015425, 'f', 4, "0.0002") == 0); + BH_VERIFY(compareString(0.00015425, 'f', 5, "0.00015") == 0); + BH_VERIFY(compareString(-0.00015425, 'f', 0, "-0") == 0); + BH_VERIFY(compareString(-0.00015425, 'f', 1, "-0.0") == 0); + BH_VERIFY(compareString(-0.00015425, 'f', 2, "-0.00") == 0); + BH_VERIFY(compareString(-0.00015425, 'f', 3, "-0.000") == 0); + BH_VERIFY(compareString(-0.00015425, 'f', 4, "-0.0002") == 0); + BH_VERIFY(compareString(-0.00015425, 'f', 5, "-0.00015") == 0); + + BH_VERIFY(compareString(1234567.1234, 'f', 0, "1234567") == 0); + BH_VERIFY(compareString(-1234567.1234, 'f', 0, "-1234567") == 0); + BH_VERIFY(compareString(1230000000.00123, 'f', 0, "1230000000") == 0); + BH_VERIFY(compareString(1230000000.00123, 'f', 1, "1230000000.0") == 0); + BH_VERIFY(compareString(1230000000.00123, 'f', 2, "1230000000.00") == 0); + BH_VERIFY(compareString(1230000000.00123, 'f', 3, "1230000000.001") == 0); + BH_VERIFY(compareString(-1230000000.00123, 'f', 0, "-1230000000") == 0); + BH_VERIFY(compareString(-1230000000.00123, 'f', 1, "-1230000000.0") == 0); + BH_VERIFY(compareString(-1230000000.00123, 'f', 2, "-1230000000.00") == 0); + BH_VERIFY(compareString(-1230000000.00123, 'f', 3, "-1230000000.001") == 0); + + return 0; +} + + +BH_UNIT_TEST(FixedRoundTrip) +{ + BH_VERIFY(roundtripString(1.0, 'f') == 0); + BH_VERIFY(roundtripString(-1.0, 'f') == 0); + BH_VERIFY(roundtripString(DBL_MIN, 'f') == 0); + BH_VERIFY(roundtripString(-DBL_MIN, 'f') == 0); + BH_VERIFY(roundtripString(DBL_MAX, 'f') == 0); + BH_VERIFY(roundtripString(-DBL_MAX, 'f') == 0); + BH_VERIFY(roundtripString(0.0, 'f') == 0); + BH_VERIFY(roundtripString(-0.0, 'f') == 0); + BH_VERIFY(roundtripString(3.14159, 'f') == 0); + BH_VERIFY(roundtripString(-3.14159, 'f') == 0); + BH_VERIFY(roundtripString(123000000.0, 'f') == 0); + BH_VERIFY(roundtripString(-123000000.0, 'f') == 0); + BH_VERIFY(roundtripString(0.81, 'f') == 0); + BH_VERIFY(roundtripString(-0.81, 'f') == 0); + BH_VERIFY(roundtripString(0.81, 'f') == 0); + BH_VERIFY(roundtripString(-0.81, 'f') == 0); + BH_VERIFY(roundtripString(144115188075855877, 'f') == 0); + BH_VERIFY(roundtripString(-144115188075855877, 'f') == 0); + + return 0; +} + + +BH_UNIT_TEST(ScientificFormat) +{ + BH_VERIFY(compareString(30.0159265358979323846, 'e', 0, "3e+01") == 0); + BH_VERIFY(compareString(30.0159265358979323846, 'e', 1, "3.0e+01") == 0); + BH_VERIFY(compareString(30.0159265358979323846, 'e', 2, "3.00e+01") == 0); + BH_VERIFY(compareString(30.0159265358979323846, 'e', 3, "3.002e+01") == 0); + BH_VERIFY(compareString(30.0159265358979323846, 'e', 4, "3.0016e+01") == 0); + BH_VERIFY(compareString(30.0159265358979323846, 'e', 5, "3.00159e+01") == 0); + BH_VERIFY(compareString(-30.0159265358979323846, 'e', 0, "-3e+01") == 0); + BH_VERIFY(compareString(-30.0159265358979323846, 'e', 1, "-3.0e+01") == 0); + BH_VERIFY(compareString(-30.0159265358979323846, 'e', 2, "-3.00e+01") == 0); + BH_VERIFY(compareString(-30.0159265358979323846, 'e', 3, "-3.002e+01") == 0); + BH_VERIFY(compareString(-30.0159265358979323846, 'e', 4, "-3.0016e+01") == 0); + BH_VERIFY(compareString(-30.0159265358979323846, 'e', 5, "-3.00159e+01") == 0); + + BH_VERIFY(compareString(0.0, 'e', 0, "0e+00") == 0); + BH_VERIFY(compareString(0.0, 'e', 1, "0.0e+00") == 0); + BH_VERIFY(compareString(-0.0, 'e', 0, "-0e+00") == 0); + BH_VERIFY(compareString(-0.0, 'e', 1, "-0.0e+00") == 0); + + BH_VERIFY(compareString(0.00015425, 'e', 0, "2e-04") == 0); + BH_VERIFY(compareString(0.00015425, 'e', 1, "1.5e-04") == 0); + BH_VERIFY(compareString(0.00015425, 'e', 2, "1.54e-04") == 0); + BH_VERIFY(compareString(0.00015425, 'e', 3, "1.543e-04") == 0); + BH_VERIFY(compareString(0.00015425, 'e', 4, "1.5425e-04") == 0); + BH_VERIFY(compareString(0.00015425, 'e', 5, "1.54250e-04") == 0); + BH_VERIFY(compareString(-0.00015425, 'e', 0, "-2e-04") == 0); + BH_VERIFY(compareString(-0.00015425, 'e', 1, "-1.5e-04") == 0); + BH_VERIFY(compareString(-0.00015425, 'e', 2, "-1.54e-04") == 0); + BH_VERIFY(compareString(-0.00015425, 'e', 3, "-1.543e-04") == 0); + BH_VERIFY(compareString(-0.00015425, 'e', 4, "-1.5425e-04") == 0); + BH_VERIFY(compareString(-0.00015425, 'e', 5, "-1.54250e-04") == 0); + + BH_VERIFY(compareString(1234567.1234, 'e', 0, "1e+06") == 0); + BH_VERIFY(compareString(-1234567.1234, 'e', 0, "-1e+06") == 0); + BH_VERIFY(compareString(1230000000.00123, 'e', 0, "1e+09") == 0); + BH_VERIFY(compareString(1230000000.00123, 'e', 1, "1.2e+09") == 0); + BH_VERIFY(compareString(1230000000.00123, 'e', 2, "1.23e+09") == 0); + BH_VERIFY(compareString(1230000000.00123, 'e', 3, "1.230e+09") == 0); + BH_VERIFY(compareString(-1230000000.00123, 'e', 0, "-1e+09") == 0); + BH_VERIFY(compareString(-1230000000.00123, 'e', 1, "-1.2e+09") == 0); + BH_VERIFY(compareString(-1230000000.00123, 'e', 2, "-1.23e+09") == 0); + BH_VERIFY(compareString(-1230000000.00123, 'e', 3, "-1.230e+09") == 0); + + return 0; +} + + +BH_UNIT_TEST(ShortestFormat) +{ + BH_VERIFY(compareString(30.0159265358979323846, 'g', 0, "3e+01") == 0); + BH_VERIFY(compareString(30.0159265358979323846, 'g', 1, "3e+01") == 0); + BH_VERIFY(compareString(30.0159265358979323846, 'g', 2, "30") == 0); + BH_VERIFY(compareString(30.0159265358979323846, 'g', 3, "30") == 0); + BH_VERIFY(compareString(30.0159265358979323846, 'g', 4, "30.02") == 0); + BH_VERIFY(compareString(30.0159265358979323846, 'g', 5, "30.016") == 0); + BH_VERIFY(compareString(-30.0159265358979323846, 'g', 0, "-3e+01") == 0); + BH_VERIFY(compareString(-30.0159265358979323846, 'g', 1, "-3e+01") == 0); + BH_VERIFY(compareString(-30.0159265358979323846, 'g', 2, "-30") == 0); + BH_VERIFY(compareString(-30.0159265358979323846, 'g', 3, "-30") == 0); + BH_VERIFY(compareString(-30.0159265358979323846, 'g', 4, "-30.02") == 0); + BH_VERIFY(compareString(-30.0159265358979323846, 'g', 5, "-30.016") == 0); + + BH_VERIFY(compareString(0.0, 'g', 0, "0") == 0); + BH_VERIFY(compareString(0.0, 'g', 1, "0") == 0); + BH_VERIFY(compareString(-0.0, 'g', 0, "-0") == 0); + BH_VERIFY(compareString(-0.0, 'g', 1, "-0") == 0); + + BH_VERIFY(compareString(0.00015425, 'g', 0, "0.0002") == 0); + BH_VERIFY(compareString(0.00015425, 'g', 1, "0.0002") == 0); + BH_VERIFY(compareString(0.00015425, 'g', 2, "0.00015") == 0); + BH_VERIFY(compareString(0.00015425, 'g', 3, "0.000154") == 0); + BH_VERIFY(compareString(0.00015425, 'g', 4, "0.0001543") == 0); + BH_VERIFY(compareString(0.00015425, 'g', 5, "0.00015425") == 0); + BH_VERIFY(compareString(-0.00015425, 'g', 0, "-0.0002") == 0); + BH_VERIFY(compareString(-0.00015425, 'g', 1, "-0.0002") == 0); + BH_VERIFY(compareString(-0.00015425, 'g', 2, "-0.00015") == 0); + BH_VERIFY(compareString(-0.00015425, 'g', 3, "-0.000154") == 0); + BH_VERIFY(compareString(-0.00015425, 'g', 4, "-0.0001543") == 0); + BH_VERIFY(compareString(-0.00015425, 'g', 5, "-0.00015425") == 0); + + BH_VERIFY(compareString(1234567.1234, 'g', 0, "1e+06") == 0); + BH_VERIFY(compareString(-1234567.1234, 'g', 0, "-1e+06") == 0); + BH_VERIFY(compareString(1230000000.00123, 'g', 0, "1e+09") == 0); + BH_VERIFY(compareString(1230000000.00123, 'g', 1, "1e+09") == 0); + BH_VERIFY(compareString(1230000000.00123, 'g', 2, "1.2e+09") == 0); + BH_VERIFY(compareString(1230000000.00123, 'g', 3, "1.23e+09") == 0); + BH_VERIFY(compareString(-1230000000.00123, 'g', 0, "-1e+09") == 0); + BH_VERIFY(compareString(-1230000000.00123, 'g', 1, "-1e+09") == 0); + BH_VERIFY(compareString(-1230000000.00123, 'g', 2, "-1.2e+09") == 0); + BH_VERIFY(compareString(-1230000000.00123, 'g', 3, "-1.23e+09") == 0); + BH_VERIFY(compareString(144115188075855877, 'g', 17, "1.4411518807585587e+17") == 0); + BH_VERIFY(compareString(-144115188075855877, 'g', 17, "-1.4411518807585587e+17") == 0); + + return 0; +} + + +BH_UNIT_TEST(ScientificRoundTrip) +{ + BH_VERIFY(roundtripString(1.0, 'e') == 0); + BH_VERIFY(roundtripString(-1.0, 'e') == 0); + BH_VERIFY(roundtripString(DBL_MIN, 'e') == 0); + BH_VERIFY(roundtripString(-DBL_MIN, 'e') == 0); + BH_VERIFY(roundtripString(DBL_MAX, 'e') == 0); + BH_VERIFY(roundtripString(-DBL_MAX, 'e') == 0); + BH_VERIFY(roundtripString(0.0, 'e') == 0); + BH_VERIFY(roundtripString(-0.0, 'e') == 0); + BH_VERIFY(roundtripString(3.14159, 'e') == 0); + BH_VERIFY(roundtripString(-3.14159, 'e') == 0); + BH_VERIFY(roundtripString(123000000.0, 'e') == 0); + BH_VERIFY(roundtripString(-123000000.0, 'e') == 0); + BH_VERIFY(roundtripString(0.81, 'e') == 0); + BH_VERIFY(roundtripString(-0.81, 'e') == 0); + BH_VERIFY(roundtripString(0.81, 'e') == 0); + BH_VERIFY(roundtripString(-0.81, 'e') == 0); + BH_VERIFY(roundtripString(144115188075855877, 'e') == 0); + BH_VERIFY(roundtripString(-144115188075855877, 'e') == 0); + + return 0; +} + + +BH_UNIT_TEST(ShortestRoundTrip) +{ + BH_VERIFY(roundtripString(1.0, 'g') == 0); + BH_VERIFY(roundtripString(-1.0, 'g') == 0); + BH_VERIFY(roundtripString(DBL_MIN, 'g') == 0); + BH_VERIFY(roundtripString(-DBL_MIN, 'g') == 0); + BH_VERIFY(roundtripString(DBL_MAX, 'g') == 0); + BH_VERIFY(roundtripString(-DBL_MAX, 'g') == 0); + BH_VERIFY(roundtripString(0.0, 'g') == 0); + BH_VERIFY(roundtripString(-0.0, 'g') == 0); + BH_VERIFY(roundtripString(3.14159, 'g') == 0); + BH_VERIFY(roundtripString(-3.14159, 'g') == 0); + BH_VERIFY(roundtripString(123000000.0, 'g') == 0); + BH_VERIFY(roundtripString(-123000000.0, 'g') == 0); + BH_VERIFY(roundtripString(0.81, 'g') == 0); + BH_VERIFY(roundtripString(-0.81, 'g') == 0); + BH_VERIFY(roundtripString(0.81, 'g') == 0); + BH_VERIFY(roundtripString(-0.81, 'g') == 0); + BH_VERIFY(roundtripString(144115188075855877, 'g') == 0); + BH_VERIFY(roundtripString(-144115188075855877, 'g') == 0); + + return 0; +} + + +BH_UNIT_TEST(Parity) +{ + char buffer[16], output[2000]; + uint64_t frac; + double value; + int i, j, k; + + for (i = 0; i < 100; i++) + { + frac = (rand() & 0x7FFF); + frac = (frac << 15) | (rand() & 0x7FFF); + frac = (frac << 15) | (rand() & 0x7FFF); + frac = (frac << 15) | (rand() & 0x7FFF); + + for (j = 0; j < 100; j++) + { + value = frac * pow(2, (rand() % 2046) - 1024); + + for (k = 0; k < 18; k++) + { + char *str; + + sprintf(buffer, "%%.%dg", k); + str = BH_StringFromDouble(value, 'g', k); + sprintf(output, buffer, value); + + if (strcmp(str, output)) + { + printf("(%.17g) (%d) %s vs %s\n", value, k, str, output); + BH_FAIL("Not equal"); + } + BH_StringFree(str); + } + } + } + + return 0; +} + + +int main(int argc, char **argv) +{ + BH_UNUSED(argc); + BH_UNUSED(argv); + + BH_UNIT_ADD(FixedFormat); + BH_UNIT_ADD(FixedRoundTrip); + BH_UNIT_ADD(ScientificFormat); + BH_UNIT_ADD(ScientificRoundTrip); + BH_UNIT_ADD(ShortestFormat); + BH_UNIT_ADD(ShortestRoundTrip); + BH_UNIT_ADD(Parity); + + return BH_UnitRun(); +} -- cgit v1.2.3