From 2097ac8d9e07320ff0f087bd6b3f6987aa02eb69 Mon Sep 17 00:00:00 2001 From: Denys Vlasenko Date: Mon, 24 Dec 2018 05:00:36 +0100 Subject: bc: move functions/macros around, no code changes Order now is: enums/structures/defines, utility/common functions, parsing, execution, main loop, main() Signed-off-by: Denys Vlasenko --- miscutils/bc.c | 1210 ++++++++++++++++++++++++++++---------------------------- 1 file changed, 609 insertions(+), 601 deletions(-) diff --git a/miscutils/bc.c b/miscutils/bc.c index 7d3b6b7ed..7a69a0816 100644 --- a/miscutils/bc.c +++ b/miscutils/bc.c @@ -877,82 +877,9 @@ struct globals { # define COMMA_SUCCESS ,BC_STATUS_SUCCESS #endif -#define STACK_HAS_MORE_THAN(s, n) ((s)->len > ((size_t)(n))) -#define STACK_HAS_EQUAL_OR_MORE_THAN(s, n) ((s)->len >= ((size_t)(n))) - -#define BC_NUM_NEG(n, neg) ((((ssize_t)(n)) ^ -((ssize_t)(neg))) + (neg)) -#define BC_NUM_ONE(n) ((n)->len == 1 && (n)->rdx == 0 && (n)->num[0] == 1) -#define BC_NUM_INT(n) ((n)->len - (n)->rdx) -//#define BC_NUM_AREQ(a, b) (BC_MAX((a)->rdx, (b)->rdx) + BC_MAX(BC_NUM_INT(a), BC_NUM_INT(b)) + 1) -static /*ALWAYS_INLINE*/ size_t BC_NUM_AREQ(BcNum *a, BcNum *b) -{ - return BC_MAX(a->rdx, b->rdx) + BC_MAX(BC_NUM_INT(a), BC_NUM_INT(b)) + 1; -} -//#define BC_NUM_MREQ(a, b, scale) (BC_NUM_INT(a) + BC_NUM_INT(b) + BC_MAX((scale), (a)->rdx + (b)->rdx) + 1) -static /*ALWAYS_INLINE*/ size_t BC_NUM_MREQ(BcNum *a, BcNum *b, size_t scale) -{ - return BC_NUM_INT(a) + BC_NUM_INT(b) + BC_MAX(scale, a->rdx + b->rdx) + 1; -} - -typedef void (*BcNumDigitOp)(size_t, size_t, bool) FAST_FUNC; - -typedef BC_STATUS (*BcNumBinaryOp)(BcNum *, BcNum *, BcNum *, size_t) FAST_FUNC; - -static BC_STATUS zbc_num_binary(BcNum *a, BcNum *b, BcNum *c, size_t scale, - BcNumBinaryOp op, size_t req); -static FAST_FUNC BC_STATUS zbc_num_a(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale); -static FAST_FUNC BC_STATUS zbc_num_s(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale); -static FAST_FUNC BC_STATUS zbc_num_p(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale); -static FAST_FUNC BC_STATUS zbc_num_m(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale); -static FAST_FUNC BC_STATUS zbc_num_d(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale); -static FAST_FUNC BC_STATUS zbc_num_rem(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale); - -static FAST_FUNC BC_STATUS zbc_num_add(BcNum *a, BcNum *b, BcNum *c, size_t scale) -{ - BcNumBinaryOp op = (!a->neg == !b->neg) ? zbc_num_a : zbc_num_s; - (void) scale; - RETURN_STATUS(zbc_num_binary(a, b, c, false, op, BC_NUM_AREQ(a, b))); -} - -static FAST_FUNC BC_STATUS zbc_num_sub(BcNum *a, BcNum *b, BcNum *c, size_t scale) -{ - BcNumBinaryOp op = (!a->neg == !b->neg) ? zbc_num_s : zbc_num_a; - (void) scale; - RETURN_STATUS(zbc_num_binary(a, b, c, true, op, BC_NUM_AREQ(a, b))); -} - -static FAST_FUNC BC_STATUS zbc_num_mul(BcNum *a, BcNum *b, BcNum *c, size_t scale) -{ - size_t req = BC_NUM_MREQ(a, b, scale); - RETURN_STATUS(zbc_num_binary(a, b, c, scale, zbc_num_m, req)); -} - -static FAST_FUNC BC_STATUS zbc_num_div(BcNum *a, BcNum *b, BcNum *c, size_t scale) -{ - size_t req = BC_NUM_MREQ(a, b, scale); - RETURN_STATUS(zbc_num_binary(a, b, c, scale, zbc_num_d, req)); -} - -static FAST_FUNC BC_STATUS zbc_num_mod(BcNum *a, BcNum *b, BcNum *c, size_t scale) -{ - size_t req = BC_NUM_MREQ(a, b, scale); - RETURN_STATUS(zbc_num_binary(a, b, c, scale, zbc_num_rem, req)); -} - -static FAST_FUNC BC_STATUS zbc_num_pow(BcNum *a, BcNum *b, BcNum *c, size_t scale) -{ - RETURN_STATUS(zbc_num_binary(a, b, c, scale, zbc_num_p, a->len * b->len + 1)); -} - -static const BcNumBinaryOp zbc_program_ops[] = { - zbc_num_pow, zbc_num_mul, zbc_num_div, zbc_num_mod, zbc_num_add, zbc_num_sub, -}; -#define zbc_num_add(...) (zbc_num_add(__VA_ARGS__) COMMA_SUCCESS) -#define zbc_num_sub(...) (zbc_num_sub(__VA_ARGS__) COMMA_SUCCESS) -#define zbc_num_mul(...) (zbc_num_mul(__VA_ARGS__) COMMA_SUCCESS) -#define zbc_num_div(...) (zbc_num_div(__VA_ARGS__) COMMA_SUCCESS) -#define zbc_num_mod(...) (zbc_num_mod(__VA_ARGS__) COMMA_SUCCESS) -#define zbc_num_pow(...) (zbc_num_pow(__VA_ARGS__) COMMA_SUCCESS) +// +// Utility routines +// static void fflush_and_check(void) { @@ -1324,102 +1251,6 @@ static size_t bc_map_find_exact(const BcVec *v, const void *ptr) } #endif -static int bad_input_byte(char c) -{ - if ((c < ' ' && c != '\t' && c != '\r' && c != '\n') // also allow '\v' '\f'? - || c > 0x7e - ) { - bc_error_fmt("illegal character 0x%02x", c); - return 1; - } - return 0; -} - -// Note: it _appends_ data from fp to vec. -static void bc_read_line(BcVec *vec, FILE *fp) -{ - again: - fflush_and_check(); - -#if ENABLE_FEATURE_BC_SIGNALS - if (G_interrupt) { // ^C was pressed - intr: - if (fp != stdin) { - // ^C while running a script (bc SCRIPT): die. - // We do not return to interactive prompt: - // user might be running us from a shell, - // and SCRIPT might be intended to terminate - // (e.g. contain a "halt" stmt). - // ^C dropping user into a bc prompt instead of - // the shell would be unexpected. - xfunc_die(); - } - // ^C while interactive input - G_interrupt = 0; - // GNU bc says "interrupted execution." - // GNU dc says "Interrupt!" - fputs("\ninterrupted execution\n", stderr); - } - -# if ENABLE_FEATURE_EDITING - if (G_ttyin && fp == stdin) { - int n, i; -# define line_buf bb_common_bufsiz1 - n = read_line_input(G.line_input_state, "", line_buf, COMMON_BUFSIZE); - if (n <= 0) { // read errors or EOF, or ^D, or ^C - if (n == 0) // ^C - goto intr; - bc_vec_pushZeroByte(vec); // ^D or EOF (or error) - return; - } - i = 0; - for (;;) { - char c = line_buf[i++]; - if (!c) break; - if (bad_input_byte(c)) goto again; - } - bc_vec_concat(vec, line_buf); -# undef line_buf - } else -# endif -#endif - { - int c; - bool bad_chars = 0; - size_t len = vec->len; - - do { -#if ENABLE_FEATURE_BC_SIGNALS - if (G_interrupt) { - // ^C was pressed: ignore entire line, get another one - vec->len = len; - goto intr; - } -#endif - do c = fgetc(fp); while (c == '\0'); - if (c == EOF) { - if (ferror(fp)) - bb_perror_msg_and_die("input error"); - // Note: EOF does not append '\n' - break; - } - bad_chars |= bad_input_byte(c); - bc_vec_pushByte(vec, (char)c); - } while (c != '\n'); - - if (bad_chars) { - // Bad chars on this line - if (!G.prog.file) { // stdin - // ignore entire line, get another one - vec->len = len; - goto again; - } - bb_perror_msg_and_die("file '%s' is not text", G.prog.file); - } - bc_vec_pushZeroByte(vec); - } -} - static void bc_num_setToZero(BcNum *n, size_t scale) { n->len = 0; @@ -1569,6 +1400,20 @@ static ssize_t bc_num_compare(BcDig *restrict a, BcDig *restrict b, size_t len) } } +#define BC_NUM_NEG(n, neg) ((((ssize_t)(n)) ^ -((ssize_t)(neg))) + (neg)) +#define BC_NUM_ONE(n) ((n)->len == 1 && (n)->rdx == 0 && (n)->num[0] == 1) +#define BC_NUM_INT(n) ((n)->len - (n)->rdx) +//#define BC_NUM_AREQ(a, b) (BC_MAX((a)->rdx, (b)->rdx) + BC_MAX(BC_NUM_INT(a), BC_NUM_INT(b)) + 1) +static /*ALWAYS_INLINE*/ size_t BC_NUM_AREQ(BcNum *a, BcNum *b) +{ + return BC_MAX(a->rdx, b->rdx) + BC_MAX(BC_NUM_INT(a), BC_NUM_INT(b)) + 1; +} +//#define BC_NUM_MREQ(a, b, scale) (BC_NUM_INT(a) + BC_NUM_INT(b) + BC_MAX((scale), (a)->rdx + (b)->rdx) + 1) +static /*ALWAYS_INLINE*/ size_t BC_NUM_MREQ(BcNum *a, BcNum *b, size_t scale) +{ + return BC_NUM_INT(a) + BC_NUM_INT(b) + BC_MAX(scale, a->rdx + b->rdx) + 1; +} + static ssize_t bc_num_cmp(BcNum *a, BcNum *b) { size_t i, min, a_int, b_int, diff; @@ -1705,52 +1550,145 @@ static BC_STATUS zbc_num_shift(BcNum *n, size_t places) } #define zbc_num_shift(...) (zbc_num_shift(__VA_ARGS__) COMMA_SUCCESS) -static BC_STATUS zbc_num_inv(BcNum *a, BcNum *b, size_t scale) +typedef BC_STATUS (*BcNumBinaryOp)(BcNum *, BcNum *, BcNum *, size_t) FAST_FUNC; + +static BC_STATUS zbc_num_binary(BcNum *a, BcNum *b, BcNum *c, size_t scale, + BcNumBinaryOp op, size_t req) { - BcNum one; - BcDig num[2]; + BcStatus s; + BcNum num2, *ptr_a, *ptr_b; + bool init = false; - one.cap = 2; - one.num = num; - bc_num_one(&one); + if (c == a) { + ptr_a = &num2; + memcpy(ptr_a, c, sizeof(BcNum)); + init = true; + } else + ptr_a = a; - RETURN_STATUS(zbc_num_div(&one, a, b, scale)); -} -#define zbc_num_inv(...) (zbc_num_inv(__VA_ARGS__) COMMA_SUCCESS) + if (c == b) { + ptr_b = &num2; + if (c != a) { + memcpy(ptr_b, c, sizeof(BcNum)); + init = true; + } + } else + ptr_b = b; -static FAST_FUNC BC_STATUS zbc_num_a(BcNum *a, BcNum *b, BcNum *restrict c, size_t sub) -{ - BcDig *ptr, *ptr_a, *ptr_b, *ptr_c; - size_t i, max, min_rdx, min_int, diff, a_int, b_int; - unsigned carry; + if (init) + bc_num_init(c, req); + else + bc_num_expand(c, req); - // Because this function doesn't need to use scale (per the bc spec), - // I am hijacking it to say whether it's doing an add or a subtract. + s = BC_STATUS_SUCCESS; + IF_ERROR_RETURN_POSSIBLE(s =) op(ptr_a, ptr_b, c, scale); - if (a->len == 0) { - bc_num_copy(c, b); - if (sub && c->len) c->neg = !c->neg; - RETURN_STATUS(BC_STATUS_SUCCESS); - } - if (b->len == 0) { - bc_num_copy(c, a); - RETURN_STATUS(BC_STATUS_SUCCESS); - } + if (init) bc_num_free(&num2); - c->neg = a->neg; - c->rdx = BC_MAX(a->rdx, b->rdx); - min_rdx = BC_MIN(a->rdx, b->rdx); - c->len = 0; + RETURN_STATUS(s); +} +#define zbc_num_binary(...) (zbc_num_binary(__VA_ARGS__) COMMA_SUCCESS) - if (a->rdx > b->rdx) { - diff = a->rdx - b->rdx; - ptr = a->num; - ptr_a = a->num + diff; - ptr_b = b->num; - } else { - diff = b->rdx - a->rdx; - ptr = b->num; - ptr_a = a->num; +static FAST_FUNC BC_STATUS zbc_num_a(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale); +static FAST_FUNC BC_STATUS zbc_num_s(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale); +static FAST_FUNC BC_STATUS zbc_num_p(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale); +static FAST_FUNC BC_STATUS zbc_num_m(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale); +static FAST_FUNC BC_STATUS zbc_num_d(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale); +static FAST_FUNC BC_STATUS zbc_num_rem(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale); + +static FAST_FUNC BC_STATUS zbc_num_add(BcNum *a, BcNum *b, BcNum *c, size_t scale) +{ + BcNumBinaryOp op = (!a->neg == !b->neg) ? zbc_num_a : zbc_num_s; + (void) scale; + RETURN_STATUS(zbc_num_binary(a, b, c, false, op, BC_NUM_AREQ(a, b))); +} + +static FAST_FUNC BC_STATUS zbc_num_sub(BcNum *a, BcNum *b, BcNum *c, size_t scale) +{ + BcNumBinaryOp op = (!a->neg == !b->neg) ? zbc_num_s : zbc_num_a; + (void) scale; + RETURN_STATUS(zbc_num_binary(a, b, c, true, op, BC_NUM_AREQ(a, b))); +} + +static FAST_FUNC BC_STATUS zbc_num_mul(BcNum *a, BcNum *b, BcNum *c, size_t scale) +{ + size_t req = BC_NUM_MREQ(a, b, scale); + RETURN_STATUS(zbc_num_binary(a, b, c, scale, zbc_num_m, req)); +} + +static FAST_FUNC BC_STATUS zbc_num_div(BcNum *a, BcNum *b, BcNum *c, size_t scale) +{ + size_t req = BC_NUM_MREQ(a, b, scale); + RETURN_STATUS(zbc_num_binary(a, b, c, scale, zbc_num_d, req)); +} + +static FAST_FUNC BC_STATUS zbc_num_mod(BcNum *a, BcNum *b, BcNum *c, size_t scale) +{ + size_t req = BC_NUM_MREQ(a, b, scale); + RETURN_STATUS(zbc_num_binary(a, b, c, scale, zbc_num_rem, req)); +} + +static FAST_FUNC BC_STATUS zbc_num_pow(BcNum *a, BcNum *b, BcNum *c, size_t scale) +{ + RETURN_STATUS(zbc_num_binary(a, b, c, scale, zbc_num_p, a->len * b->len + 1)); +} + +static const BcNumBinaryOp zbc_program_ops[] = { + zbc_num_pow, zbc_num_mul, zbc_num_div, zbc_num_mod, zbc_num_add, zbc_num_sub, +}; +#define zbc_num_add(...) (zbc_num_add(__VA_ARGS__) COMMA_SUCCESS) +#define zbc_num_sub(...) (zbc_num_sub(__VA_ARGS__) COMMA_SUCCESS) +#define zbc_num_mul(...) (zbc_num_mul(__VA_ARGS__) COMMA_SUCCESS) +#define zbc_num_div(...) (zbc_num_div(__VA_ARGS__) COMMA_SUCCESS) +#define zbc_num_mod(...) (zbc_num_mod(__VA_ARGS__) COMMA_SUCCESS) +#define zbc_num_pow(...) (zbc_num_pow(__VA_ARGS__) COMMA_SUCCESS) + +static BC_STATUS zbc_num_inv(BcNum *a, BcNum *b, size_t scale) +{ + BcNum one; + BcDig num[2]; + + one.cap = 2; + one.num = num; + bc_num_one(&one); + + RETURN_STATUS(zbc_num_div(&one, a, b, scale)); +} +#define zbc_num_inv(...) (zbc_num_inv(__VA_ARGS__) COMMA_SUCCESS) + +static FAST_FUNC BC_STATUS zbc_num_a(BcNum *a, BcNum *b, BcNum *restrict c, size_t sub) +{ + BcDig *ptr, *ptr_a, *ptr_b, *ptr_c; + size_t i, max, min_rdx, min_int, diff, a_int, b_int; + unsigned carry; + + // Because this function doesn't need to use scale (per the bc spec), + // I am hijacking it to say whether it's doing an add or a subtract. + + if (a->len == 0) { + bc_num_copy(c, b); + if (sub && c->len) c->neg = !c->neg; + RETURN_STATUS(BC_STATUS_SUCCESS); + } + if (b->len == 0) { + bc_num_copy(c, a); + RETURN_STATUS(BC_STATUS_SUCCESS); + } + + c->neg = a->neg; + c->rdx = BC_MAX(a->rdx, b->rdx); + min_rdx = BC_MIN(a->rdx, b->rdx); + c->len = 0; + + if (a->rdx > b->rdx) { + diff = a->rdx - b->rdx; + ptr = a->num; + ptr_a = a->num + diff; + ptr_b = b->num; + } else { + diff = b->rdx - a->rdx; + ptr = b->num; + ptr_a = a->num; ptr_b = b->num + diff; } @@ -2224,295 +2162,106 @@ static FAST_FUNC BC_STATUS zbc_num_p(BcNum *a, BcNum *b, BcNum *restrict c, size } #define zbc_num_p(...) (zbc_num_p(__VA_ARGS__) COMMA_SUCCESS) -static BC_STATUS zbc_num_binary(BcNum *a, BcNum *b, BcNum *c, size_t scale, - BcNumBinaryOp op, size_t req) +static BC_STATUS zbc_num_sqrt(BcNum *a, BcNum *restrict b, size_t scale) { BcStatus s; - BcNum num2, *ptr_a, *ptr_b; - bool init = false; + BcNum num1, num2, half, f, fprime, *x0, *x1, *temp; + size_t pow, len, digs, digs1, resrdx, req, times = 0; + ssize_t cmp = 1, cmp1 = SSIZE_MAX, cmp2 = SSIZE_MAX; - if (c == a) { - ptr_a = &num2; - memcpy(ptr_a, c, sizeof(BcNum)); - init = true; - } else - ptr_a = a; + req = BC_MAX(scale, a->rdx) + ((BC_NUM_INT(a) + 1) >> 1) + 1; + bc_num_expand(b, req); - if (c == b) { - ptr_b = &num2; - if (c != a) { - memcpy(ptr_b, c, sizeof(BcNum)); - init = true; - } - } else - ptr_b = b; + if (a->len == 0) { + bc_num_setToZero(b, scale); + RETURN_STATUS(BC_STATUS_SUCCESS); + } + if (a->neg) { + RETURN_STATUS(bc_error("negative number")); + } + if (BC_NUM_ONE(a)) { + bc_num_one(b); + bc_num_extend(b, scale); + RETURN_STATUS(BC_STATUS_SUCCESS); + } - if (init) - bc_num_init(c, req); - else - bc_num_expand(c, req); + scale = BC_MAX(scale, a->rdx) + 1; + len = a->len + scale; - s = BC_STATUS_SUCCESS; - IF_ERROR_RETURN_POSSIBLE(s =) op(ptr_a, ptr_b, c, scale); + bc_num_init(&num1, len); + bc_num_init(&num2, len); + bc_num_init_DEF_SIZE(&half); - if (init) bc_num_free(&num2); + bc_num_one(&half); + half.num[0] = 5; + half.rdx = 1; - RETURN_STATUS(s); -} -#define zbc_num_binary(...) (zbc_num_binary(__VA_ARGS__) COMMA_SUCCESS) + bc_num_init(&f, len); + bc_num_init(&fprime, len); -static bool bc_num_strValid(const char *val, size_t base) -{ - BcDig b; - bool radix; + x0 = &num1; + x1 = &num2; - b = (BcDig)(base <= 10 ? base + '0' : base - 10 + 'A'); - radix = false; - for (;;) { - BcDig c = *val++; - if (c == '\0') - break; - if (c == '.') { - if (radix) return false; - radix = true; - continue; - } - if (c < '0' || c >= b || (c > '9' && c < 'A')) - return false; + bc_num_one(x0); + pow = BC_NUM_INT(a); + + if (pow) { + if (pow & 1) + x0->num[0] = 2; + else + x0->num[0] = 6; + + pow -= 2 - (pow & 1); + + bc_num_extend(x0, pow); + + // Make sure to move the radix back. + x0->rdx -= pow; } - return true; -} -// Note: n is already "bc_num_zero()"ed, -// leading zeroes in "val" are removed -static void bc_num_parseDecimal(BcNum *n, const char *val) -{ - size_t len, i; - const char *ptr; + x0->rdx = digs = digs1 = 0; + resrdx = scale + 2; + len = BC_NUM_INT(x0) + resrdx - 1; - len = strlen(val); - if (len == 0) - return; + while (cmp != 0 || digs < len) { + s = zbc_num_div(a, x0, &f, resrdx); + if (s) goto err; + s = zbc_num_add(x0, &f, &fprime, resrdx); + if (s) goto err; + s = zbc_num_mul(&fprime, &half, x1, resrdx); + if (s) goto err; - bc_num_expand(n, len); + cmp = bc_num_cmp(x1, x0); + digs = x1->len - (unsigned long long) llabs(cmp); - ptr = strchr(val, '.'); + if (cmp == cmp2 && digs == digs1) + times += 1; + else + times = 0; - n->rdx = 0; - if (ptr != NULL) - n->rdx = (size_t)((val + len) - (ptr + 1)); + resrdx += times > 4; - for (i = 0; val[i]; ++i) { - if (val[i] != '0' && val[i] != '.') { - // Not entirely zero value - convert it, and exit - i = len - 1; - for (;;) { - n->num[n->len] = val[i] - '0'; - ++n->len; - skip_dot: - if (i == 0) break; - if (val[--i] == '.') goto skip_dot; - } - break; - } + cmp2 = cmp1; + cmp1 = cmp; + digs1 = digs; + + temp = x0; + x0 = x1; + x1 = temp; } - // if for() exits without hitting if(), the value is entirely zero + + bc_num_copy(b, x0); + scale -= 1; + if (b->rdx > scale) bc_num_truncate(b, b->rdx - scale); + err: + bc_num_free(&fprime); + bc_num_free(&f); + bc_num_free(&half); + bc_num_free(&num2); + bc_num_free(&num1); + RETURN_STATUS(s); } - -// Note: n is already "bc_num_zero()"ed, -// leading zeroes in "val" are removed -static void bc_num_parseBase(BcNum *n, const char *val, unsigned base_t) -{ - BcStatus s; - BcNum temp, mult, result; - BcNum base; - BcDig base_digs[ULONG_NUM_BUFSIZE]; - BcDig c = '\0'; - unsigned long v; - size_t i, digits; - - for (i = 0; ; ++i) { - if (val[i] == '\0') - return; - if (val[i] != '.' && val[i] != '0') - break; - } - - bc_num_init_DEF_SIZE(&temp); - bc_num_init_DEF_SIZE(&mult); - base.cap = ARRAY_SIZE(base_digs); - base.num = base_digs; - bc_num_ulong2num(&base, base_t); - - for (;;) { - c = *val++; - if (c == '\0') goto int_err; - if (c == '.') break; - - v = (unsigned long) (c <= '9' ? c - '0' : c - 'A' + 10); - - s = zbc_num_mul(n, &base, &mult, 0); - if (s) goto int_err; - bc_num_ulong2num(&temp, v); - s = zbc_num_add(&mult, &temp, n, 0); - if (s) goto int_err; - } - - bc_num_init(&result, base.len); - //bc_num_zero(&result); - already is - bc_num_one(&mult); - - digits = 0; - for (;;) { - c = *val++; - if (c == '\0') break; - digits++; - - v = (unsigned long) (c <= '9' ? c - '0' : c - 'A' + 10); - - s = zbc_num_mul(&result, &base, &result, 0); - if (s) goto err; - bc_num_ulong2num(&temp, v); - s = zbc_num_add(&result, &temp, &result, 0); - if (s) goto err; - s = zbc_num_mul(&mult, &base, &mult, 0); - if (s) goto err; - } - - s = zbc_num_div(&result, &mult, &result, digits); - if (s) goto err; - s = zbc_num_add(n, &result, n, digits); - if (s) goto err; - - if (n->len != 0) { - if (n->rdx < digits) - bc_num_extend(n, digits - n->rdx); - } else - bc_num_zero(n); - err: - bc_num_free(&result); - int_err: - bc_num_free(&mult); - bc_num_free(&temp); -} - -static BC_STATUS zbc_num_parse(BcNum *n, const char *val, unsigned base_t) -{ - if (!bc_num_strValid(val, base_t)) - RETURN_STATUS(bc_error("bad number string")); - - bc_num_zero(n); - while (*val == '0') val++; - - if (base_t == 10) - bc_num_parseDecimal(n, val); - else - bc_num_parseBase(n, val, base_t); - - RETURN_STATUS(BC_STATUS_SUCCESS); -} -#define zbc_num_parse(...) (zbc_num_parse(__VA_ARGS__) COMMA_SUCCESS) - -static BC_STATUS zbc_num_sqrt(BcNum *a, BcNum *restrict b, size_t scale) -{ - BcStatus s; - BcNum num1, num2, half, f, fprime, *x0, *x1, *temp; - size_t pow, len, digs, digs1, resrdx, req, times = 0; - ssize_t cmp = 1, cmp1 = SSIZE_MAX, cmp2 = SSIZE_MAX; - - req = BC_MAX(scale, a->rdx) + ((BC_NUM_INT(a) + 1) >> 1) + 1; - bc_num_expand(b, req); - - if (a->len == 0) { - bc_num_setToZero(b, scale); - RETURN_STATUS(BC_STATUS_SUCCESS); - } - if (a->neg) { - RETURN_STATUS(bc_error("negative number")); - } - if (BC_NUM_ONE(a)) { - bc_num_one(b); - bc_num_extend(b, scale); - RETURN_STATUS(BC_STATUS_SUCCESS); - } - - scale = BC_MAX(scale, a->rdx) + 1; - len = a->len + scale; - - bc_num_init(&num1, len); - bc_num_init(&num2, len); - bc_num_init_DEF_SIZE(&half); - - bc_num_one(&half); - half.num[0] = 5; - half.rdx = 1; - - bc_num_init(&f, len); - bc_num_init(&fprime, len); - - x0 = &num1; - x1 = &num2; - - bc_num_one(x0); - pow = BC_NUM_INT(a); - - if (pow) { - if (pow & 1) - x0->num[0] = 2; - else - x0->num[0] = 6; - - pow -= 2 - (pow & 1); - - bc_num_extend(x0, pow); - - // Make sure to move the radix back. - x0->rdx -= pow; - } - - x0->rdx = digs = digs1 = 0; - resrdx = scale + 2; - len = BC_NUM_INT(x0) + resrdx - 1; - - while (cmp != 0 || digs < len) { - s = zbc_num_div(a, x0, &f, resrdx); - if (s) goto err; - s = zbc_num_add(x0, &f, &fprime, resrdx); - if (s) goto err; - s = zbc_num_mul(&fprime, &half, x1, resrdx); - if (s) goto err; - - cmp = bc_num_cmp(x1, x0); - digs = x1->len - (unsigned long long) llabs(cmp); - - if (cmp == cmp2 && digs == digs1) - times += 1; - else - times = 0; - - resrdx += times > 4; - - cmp2 = cmp1; - cmp1 = cmp; - digs1 = digs; - - temp = x0; - x0 = x1; - x1 = temp; - } - - bc_num_copy(b, x0); - scale -= 1; - if (b->rdx > scale) bc_num_truncate(b, b->rdx - scale); - err: - bc_num_free(&fprime); - bc_num_free(&f); - bc_num_free(&half); - bc_num_free(&num2); - bc_num_free(&num1); - RETURN_STATUS(s); -} -#define zbc_num_sqrt(...) (zbc_num_sqrt(__VA_ARGS__) COMMA_SUCCESS) +#define zbc_num_sqrt(...) (zbc_num_sqrt(__VA_ARGS__) COMMA_SUCCESS) static BC_STATUS zbc_num_divmod(BcNum *a, BcNum *b, BcNum *c, BcNum *d, size_t scale) @@ -2592,153 +2341,382 @@ static BC_STATUS zdc_num_modexp(BcNum *a, BcNum *b, BcNum *c, BcNum *restrict d) bc_num_free(&base); RETURN_STATUS(s); } -#define zdc_num_modexp(...) (zdc_num_modexp(__VA_ARGS__) COMMA_SUCCESS) -#endif // ENABLE_DC +#define zdc_num_modexp(...) (zdc_num_modexp(__VA_ARGS__) COMMA_SUCCESS) +#endif // ENABLE_DC + +static FAST_FUNC void bc_string_free(void *string) +{ + free(*(char**)string); +} + +static void bc_func_init(BcFunc *f) +{ + bc_char_vec_init(&f->code); + IF_BC(bc_vec_init(&f->labels, sizeof(size_t), NULL);) + IF_BC(bc_vec_init(&f->autos, sizeof(BcId), bc_id_free);) + IF_BC(bc_vec_init(&f->strs, sizeof(char *), bc_string_free);) + IF_BC(bc_vec_init(&f->consts, sizeof(char *), bc_string_free);) + IF_BC(f->nparams = 0;) +} + +static FAST_FUNC void bc_func_free(void *func) +{ + BcFunc *f = (BcFunc *) func; + bc_vec_free(&f->code); + IF_BC(bc_vec_free(&f->labels);) + IF_BC(bc_vec_free(&f->autos);) + IF_BC(bc_vec_free(&f->strs);) + IF_BC(bc_vec_free(&f->consts);) +} + +static void bc_array_expand(BcVec *a, size_t len); + +static void bc_array_init(BcVec *a, bool nums) +{ + if (nums) + bc_vec_init(a, sizeof(BcNum), bc_num_free); + else + bc_vec_init(a, sizeof(BcVec), bc_vec_free); + bc_array_expand(a, 1); +} + +static void bc_array_expand(BcVec *a, size_t len) +{ + if (a->dtor == bc_num_free + // && a->size == sizeof(BcNum) - always true + ) { + BcNum n; + while (len > a->len) { + bc_num_init_DEF_SIZE(&n); + bc_vec_push(a, &n); + } + } else { + BcVec v; + while (len > a->len) { + bc_array_init(&v, true); + bc_vec_push(a, &v); + } + } +} + +static void bc_array_copy(BcVec *d, const BcVec *s) +{ + BcNum *dnum, *snum; + size_t i; + + bc_vec_pop_all(d); + bc_vec_expand(d, s->cap); + d->len = s->len; + + dnum = (void*)d->v; + snum = (void*)s->v; + for (i = 0; i < s->len; i++, dnum++, snum++) { + bc_num_init(dnum, snum->len); + bc_num_copy(dnum, snum); + } +} + +#if ENABLE_DC +static void dc_result_copy(BcResult *d, BcResult *src) +{ + d->t = src->t; + + switch (d->t) { + case BC_RESULT_TEMP: + case BC_RESULT_IBASE: + case BC_RESULT_SCALE: + case BC_RESULT_OBASE: + bc_num_init(&d->d.n, src->d.n.len); + bc_num_copy(&d->d.n, &src->d.n); + break; + case BC_RESULT_VAR: + case BC_RESULT_ARRAY: + case BC_RESULT_ARRAY_ELEM: + d->d.id.name = xstrdup(src->d.id.name); + break; + case BC_RESULT_CONSTANT: + IF_BC(case BC_RESULT_LAST:) + case BC_RESULT_ONE: + case BC_RESULT_STR: + memcpy(&d->d.n, &src->d.n, sizeof(BcNum)); + break; + } +} +#endif // ENABLE_DC + +static FAST_FUNC void bc_result_free(void *result) +{ + BcResult *r = (BcResult *) result; + + switch (r->t) { + case BC_RESULT_TEMP: + case BC_RESULT_IBASE: + case BC_RESULT_SCALE: + case BC_RESULT_OBASE: + bc_num_free(&r->d.n); + break; + case BC_RESULT_VAR: + case BC_RESULT_ARRAY: + case BC_RESULT_ARRAY_ELEM: + free(r->d.id.name); + break; + default: + // Do nothing. + break; + } +} + +static int bad_input_byte(char c) +{ + if ((c < ' ' && c != '\t' && c != '\r' && c != '\n') // also allow '\v' '\f'? + || c > 0x7e + ) { + bc_error_fmt("illegal character 0x%02x", c); + return 1; + } + return 0; +} + +// Note: it _appends_ data from fp to vec. +static void bc_read_line(BcVec *vec, FILE *fp) +{ + again: + fflush_and_check(); + +#if ENABLE_FEATURE_BC_SIGNALS + if (G_interrupt) { // ^C was pressed + intr: + if (fp != stdin) { + // ^C while running a script (bc SCRIPT): die. + // We do not return to interactive prompt: + // user might be running us from a shell, + // and SCRIPT might be intended to terminate + // (e.g. contain a "halt" stmt). + // ^C dropping user into a bc prompt instead of + // the shell would be unexpected. + xfunc_die(); + } + // ^C while interactive input + G_interrupt = 0; + // GNU bc says "interrupted execution." + // GNU dc says "Interrupt!" + fputs("\ninterrupted execution\n", stderr); + } + +# if ENABLE_FEATURE_EDITING + if (G_ttyin && fp == stdin) { + int n, i; +# define line_buf bb_common_bufsiz1 + n = read_line_input(G.line_input_state, "", line_buf, COMMON_BUFSIZE); + if (n <= 0) { // read errors or EOF, or ^D, or ^C + if (n == 0) // ^C + goto intr; + bc_vec_pushZeroByte(vec); // ^D or EOF (or error) + return; + } + i = 0; + for (;;) { + char c = line_buf[i++]; + if (!c) break; + if (bad_input_byte(c)) goto again; + } + bc_vec_concat(vec, line_buf); +# undef line_buf + } else +# endif +#endif + { + int c; + bool bad_chars = 0; + size_t len = vec->len; + + do { +#if ENABLE_FEATURE_BC_SIGNALS + if (G_interrupt) { + // ^C was pressed: ignore entire line, get another one + vec->len = len; + goto intr; + } +#endif + do c = fgetc(fp); while (c == '\0'); + if (c == EOF) { + if (ferror(fp)) + bb_perror_msg_and_die("input error"); + // Note: EOF does not append '\n' + break; + } + bad_chars |= bad_input_byte(c); + bc_vec_pushByte(vec, (char)c); + } while (c != '\n'); + + if (bad_chars) { + // Bad chars on this line + if (!G.prog.file) { // stdin + // ignore entire line, get another one + vec->len = len; + goto again; + } + bb_perror_msg_and_die("file '%s' is not text", G.prog.file); + } + bc_vec_pushZeroByte(vec); + } +} + +// +// Parsing routines +// + +static bool bc_num_strValid(const char *val, size_t base) +{ + BcDig b; + bool radix; + + b = (BcDig)(base <= 10 ? base + '0' : base - 10 + 'A'); + radix = false; + for (;;) { + BcDig c = *val++; + if (c == '\0') + break; + if (c == '.') { + if (radix) return false; + radix = true; + continue; + } + if (c < '0' || c >= b || (c > '9' && c < 'A')) + return false; + } + return true; +} -#if ENABLE_BC -static BC_STATUS zbc_func_insert(BcFunc *f, char *name, bool var) +// Note: n is already "bc_num_zero()"ed, +// leading zeroes in "val" are removed +static void bc_num_parseDecimal(BcNum *n, const char *val) { - BcId *autoid; - BcId a; - size_t i; + size_t len, i; + const char *ptr; - autoid = (void*)f->autos.v; - for (i = 0; i < f->autos.len; i++, autoid++) { - if (strcmp(name, autoid->name) == 0) - RETURN_STATUS(bc_error("function parameter or auto var has the same name as another")); - } + len = strlen(val); + if (len == 0) + return; - a.idx = var; - a.name = name; + bc_num_expand(n, len); - bc_vec_push(&f->autos, &a); + ptr = strchr(val, '.'); - RETURN_STATUS(BC_STATUS_SUCCESS); -} -#define zbc_func_insert(...) (zbc_func_insert(__VA_ARGS__) COMMA_SUCCESS) -#endif + n->rdx = 0; + if (ptr != NULL) + n->rdx = (size_t)((val + len) - (ptr + 1)); -static FAST_FUNC void bc_string_free(void *string) -{ - free(*(char**)string); + for (i = 0; val[i]; ++i) { + if (val[i] != '0' && val[i] != '.') { + // Not entirely zero value - convert it, and exit + i = len - 1; + for (;;) { + n->num[n->len] = val[i] - '0'; + ++n->len; + skip_dot: + if (i == 0) break; + if (val[--i] == '.') goto skip_dot; + } + break; + } + } + // if for() exits without hitting if(), the value is entirely zero } -static void bc_func_init(BcFunc *f) +// Note: n is already "bc_num_zero()"ed, +// leading zeroes in "val" are removed +static void bc_num_parseBase(BcNum *n, const char *val, unsigned base_t) { - bc_char_vec_init(&f->code); - IF_BC(bc_vec_init(&f->labels, sizeof(size_t), NULL);) - IF_BC(bc_vec_init(&f->autos, sizeof(BcId), bc_id_free);) - IF_BC(bc_vec_init(&f->strs, sizeof(char *), bc_string_free);) - IF_BC(bc_vec_init(&f->consts, sizeof(char *), bc_string_free);) - IF_BC(f->nparams = 0;) -} + BcStatus s; + BcNum temp, mult, result; + BcNum base; + BcDig base_digs[ULONG_NUM_BUFSIZE]; + BcDig c = '\0'; + unsigned long v; + size_t i, digits; -static FAST_FUNC void bc_func_free(void *func) -{ - BcFunc *f = (BcFunc *) func; - bc_vec_free(&f->code); - IF_BC(bc_vec_free(&f->labels);) - IF_BC(bc_vec_free(&f->autos);) - IF_BC(bc_vec_free(&f->strs);) - IF_BC(bc_vec_free(&f->consts);) -} + for (i = 0; ; ++i) { + if (val[i] == '\0') + return; + if (val[i] != '.' && val[i] != '0') + break; + } -static void bc_array_expand(BcVec *a, size_t len); + bc_num_init_DEF_SIZE(&temp); + bc_num_init_DEF_SIZE(&mult); + base.cap = ARRAY_SIZE(base_digs); + base.num = base_digs; + bc_num_ulong2num(&base, base_t); -static void bc_array_init(BcVec *a, bool nums) -{ - if (nums) - bc_vec_init(a, sizeof(BcNum), bc_num_free); - else - bc_vec_init(a, sizeof(BcVec), bc_vec_free); - bc_array_expand(a, 1); -} + for (;;) { + c = *val++; + if (c == '\0') goto int_err; + if (c == '.') break; -static void bc_array_expand(BcVec *a, size_t len) -{ - if (a->dtor == bc_num_free - // && a->size == sizeof(BcNum) - always true - ) { - BcNum n; - while (len > a->len) { - bc_num_init_DEF_SIZE(&n); - bc_vec_push(a, &n); - } - } else { - BcVec v; - while (len > a->len) { - bc_array_init(&v, true); - bc_vec_push(a, &v); - } + v = (unsigned long) (c <= '9' ? c - '0' : c - 'A' + 10); + + s = zbc_num_mul(n, &base, &mult, 0); + if (s) goto int_err; + bc_num_ulong2num(&temp, v); + s = zbc_num_add(&mult, &temp, n, 0); + if (s) goto int_err; } -} -static void bc_array_copy(BcVec *d, const BcVec *s) -{ - BcNum *dnum, *snum; - size_t i; + bc_num_init(&result, base.len); + //bc_num_zero(&result); - already is + bc_num_one(&mult); - bc_vec_pop_all(d); - bc_vec_expand(d, s->cap); - d->len = s->len; + digits = 0; + for (;;) { + c = *val++; + if (c == '\0') break; + digits++; - dnum = (void*)d->v; - snum = (void*)s->v; - for (i = 0; i < s->len; i++, dnum++, snum++) { - bc_num_init(dnum, snum->len); - bc_num_copy(dnum, snum); + v = (unsigned long) (c <= '9' ? c - '0' : c - 'A' + 10); + + s = zbc_num_mul(&result, &base, &result, 0); + if (s) goto err; + bc_num_ulong2num(&temp, v); + s = zbc_num_add(&result, &temp, &result, 0); + if (s) goto err; + s = zbc_num_mul(&mult, &base, &mult, 0); + if (s) goto err; } -} -#if ENABLE_DC -static void dc_result_copy(BcResult *d, BcResult *src) -{ - d->t = src->t; + s = zbc_num_div(&result, &mult, &result, digits); + if (s) goto err; + s = zbc_num_add(n, &result, n, digits); + if (s) goto err; - switch (d->t) { - case BC_RESULT_TEMP: - case BC_RESULT_IBASE: - case BC_RESULT_SCALE: - case BC_RESULT_OBASE: - bc_num_init(&d->d.n, src->d.n.len); - bc_num_copy(&d->d.n, &src->d.n); - break; - case BC_RESULT_VAR: - case BC_RESULT_ARRAY: - case BC_RESULT_ARRAY_ELEM: - d->d.id.name = xstrdup(src->d.id.name); - break; - case BC_RESULT_CONSTANT: - IF_BC(case BC_RESULT_LAST:) - case BC_RESULT_ONE: - case BC_RESULT_STR: - memcpy(&d->d.n, &src->d.n, sizeof(BcNum)); - break; - } + if (n->len != 0) { + if (n->rdx < digits) + bc_num_extend(n, digits - n->rdx); + } else + bc_num_zero(n); + err: + bc_num_free(&result); + int_err: + bc_num_free(&mult); + bc_num_free(&temp); } -#endif // ENABLE_DC -static FAST_FUNC void bc_result_free(void *result) +static BC_STATUS zbc_num_parse(BcNum *n, const char *val, unsigned base_t) { - BcResult *r = (BcResult *) result; + if (!bc_num_strValid(val, base_t)) + RETURN_STATUS(bc_error("bad number string")); - switch (r->t) { - case BC_RESULT_TEMP: - case BC_RESULT_IBASE: - case BC_RESULT_SCALE: - case BC_RESULT_OBASE: - bc_num_free(&r->d.n); - break; - case BC_RESULT_VAR: - case BC_RESULT_ARRAY: - case BC_RESULT_ARRAY_ELEM: - free(r->d.id.name); - break; - default: - // Do nothing. - break; - } + bc_num_zero(n); + while (*val == '0') val++; + + if (base_t == 10) + bc_num_parseDecimal(n, val); + else + bc_num_parseBase(n, val, base_t); + + RETURN_STATUS(BC_STATUS_SUCCESS); } +#define zbc_num_parse(...) (zbc_num_parse(__VA_ARGS__) COMMA_SUCCESS) static void bc_lex_lineComment(BcLex *l) { @@ -4333,6 +4311,27 @@ static BC_STATUS zbc_parse_break_or_continue(BcParse *p, BcLexType type) } #define zbc_parse_break_or_continue(...) (zbc_parse_break_or_continue(__VA_ARGS__) COMMA_SUCCESS) +static BC_STATUS zbc_func_insert(BcFunc *f, char *name, bool var) +{ + BcId *autoid; + BcId a; + size_t i; + + autoid = (void*)f->autos.v; + for (i = 0; i < f->autos.len; i++, autoid++) { + if (strcmp(name, autoid->name) == 0) + RETURN_STATUS(bc_error("function parameter or auto var has the same name as another")); + } + + a.idx = var; + a.name = name; + + bc_vec_push(&f->autos, &a); + + RETURN_STATUS(BC_STATUS_SUCCESS); +} +#define zbc_func_insert(...) (zbc_func_insert(__VA_ARGS__) COMMA_SUCCESS) + static BC_STATUS zbc_parse_funcdef(BcParse *p) { BcStatus s; @@ -5010,6 +5009,13 @@ static BC_STATUS zdc_parse_exprs_until_eof(BcParse *p) #endif // ENABLE_DC +// +// Execution engine +// + +#define STACK_HAS_MORE_THAN(s, n) ((s)->len > ((size_t)(n))) +#define STACK_HAS_EQUAL_OR_MORE_THAN(s, n) ((s)->len >= ((size_t)(n))) + static BcVec* bc_program_search(char *id, bool var) { BcId e, *ptr; @@ -5400,6 +5406,8 @@ static void bc_num_printDecimal(BcNum *n) bc_num_printHex((size_t) n->num[i], 1, i == rdx); } +typedef void (*BcNumDigitOp)(size_t, size_t, bool) FAST_FUNC; + static BC_STATUS zbc_num_printNum(BcNum *n, unsigned base_t, size_t width, BcNumDigitOp print) { BcStatus s; -- cgit v1.2.3