| /* vi: set sw=4 ts=4: */ |
| /* |
| * Licensed under GPLv2 or later, see file LICENSE in this source tree. |
| * Adapted from https://github.com/gavinhoward/bc |
| * Original code copyright (c) 2018 Gavin D. Howard and contributors. |
| */ |
| //TODO: |
| // maybe implement a^b for non-integer b? |
| |
| #define DEBUG_LEXER 0 |
| #define DEBUG_COMPILE 0 |
| #define DEBUG_EXEC 0 |
| // This can be left enabled for production as well: |
| #define SANITY_CHECKS 1 |
| |
| //config:config BC |
| //config: bool "bc (45 kb)" |
| //config: default y |
| //config: select FEATURE_DC_BIG |
| //config: help |
| //config: bc is a command-line, arbitrary-precision calculator with a |
| //config: Turing-complete language. See the GNU bc manual |
| //config: (https://www.gnu.org/software/bc/manual/bc.html) and bc spec |
| //config: (http://pubs.opengroup.org/onlinepubs/9699919799/utilities/bc.html). |
| //config: |
| //config: This bc has five differences to the GNU bc: |
| //config: 1) The period (.) is a shortcut for "last", as in the BSD bc. |
| //config: 2) Arrays are copied before being passed as arguments to |
| //config: functions. This behavior is required by the bc spec. |
| //config: 3) Arrays can be passed to the builtin "length" function to get |
| //config: the number of elements in the array. This prints "1": |
| //config: a[0] = 0; length(a[]) |
| //config: 4) The precedence of the boolean "not" operator (!) is equal to |
| //config: that of the unary minus (-) negation operator. This still |
| //config: allows POSIX-compliant scripts to work while somewhat |
| //config: preserving expected behavior (versus C) and making parsing |
| //config: easier. |
| //config: 5) "read()" accepts expressions, not only numeric literals. |
| //config: |
| //config:config DC |
| //config: bool "dc (36 kb)" |
| //config: default y |
| //config: help |
| //config: dc is a reverse-polish notation command-line calculator which |
| //config: supports unlimited precision arithmetic. See the FreeBSD man page |
| //config: (https://www.unix.com/man-page/FreeBSD/1/dc/) and GNU dc manual |
| //config: (https://www.gnu.org/software/bc/manual/dc-1.05/html_mono/dc.html). |
| //config: |
| //config: This dc has a few differences from the two above: |
| //config: 1) When printing a byte stream (command "P"), this dc follows what |
| //config: the FreeBSD dc does. |
| //config: 2) Implements the GNU extensions for divmod ("~") and |
| //config: modular exponentiation ("|"). |
| //config: 3) Implements all FreeBSD extensions, except for "J" and "M". |
| //config: 4) Like the FreeBSD dc, this dc supports extended registers. |
| //config: However, they are implemented differently. When it encounters |
| //config: whitespace where a register should be, it skips the whitespace. |
| //config: If the character following is not a lowercase letter, an error |
| //config: is issued. Otherwise, the register name is parsed by the |
| //config: following regex: [a-z][a-z0-9_]* |
| //config: This generally means that register names will be surrounded by |
| //config: whitespace. Examples: |
| //config: l idx s temp L index S temp2 < do_thing |
| //config: Also note that, like the FreeBSD dc, extended registers are not |
| //config: allowed unless the "-x" option is given. |
| //config: |
| //config:if BC || DC # for menuconfig indenting |
| //config: |
| //config:config FEATURE_DC_BIG |
| //config: bool "Use bc code base for dc (larger, more features)" |
| //config: default y |
| //config: |
| //config:config FEATURE_DC_LIBM |
| //config: bool "Enable power and exp functions (requires libm)" |
| //config: default y |
| //config: depends on DC && !BC && !FEATURE_DC_BIG |
| //config: help |
| //config: Enable power and exp functions. |
| //config: NOTE: This will require libm to be present for linking. |
| //config: |
| //config:config FEATURE_BC_INTERACTIVE |
| //config: bool "Interactive mode (+4kb)" |
| //config: default y |
| //config: depends on BC || (DC && FEATURE_DC_BIG) |
| //config: help |
| //config: Enable interactive mode: when started on a tty, |
| //config: ^C interrupts execution and returns to command line, |
| //config: errors also return to command line instead of exiting, |
| //config: line editing with history is available. |
| //config: |
| //config: With this option off, input can still be taken from tty, |
| //config: but all errors are fatal, ^C is fatal, |
| //config: tty is treated exactly the same as any other |
| //config: standard input (IOW: no line editing). |
| //config: |
| //config:config FEATURE_BC_LONG_OPTIONS |
| //config: bool "Enable bc/dc long options" |
| //config: default y |
| //config: depends on BC || (DC && FEATURE_DC_BIG) |
| //config: |
| //config:endif |
| |
| //applet:IF_BC(APPLET(bc, BB_DIR_USR_BIN, BB_SUID_DROP)) |
| //applet:IF_DC(APPLET(dc, BB_DIR_USR_BIN, BB_SUID_DROP)) |
| |
| //kbuild:lib-$(CONFIG_BC) += bc.o |
| //kbuild:lib-$(CONFIG_DC) += bc.o |
| |
| //See www.gnu.org/software/bc/manual/bc.html |
| //usage:#define bc_trivial_usage |
| //usage: "[-sqlw] FILE..." |
| //usage: |
| //usage:#define bc_full_usage "\n" |
| //usage: "\nArbitrary precision calculator" |
| //usage: "\n" |
| ///////: "\n -i Interactive" - has no effect for now |
| //usage: "\n -q Quiet" |
| //usage: "\n -l Load standard math library" |
| //usage: "\n -s Be POSIX compatible" |
| //usage: "\n -w Warn if extensions are used" |
| ///////: "\n -v Version" |
| //usage: "\n" |
| //usage: "\n$BC_LINE_LENGTH changes output width" |
| //usage: |
| //usage:#define bc_example_usage |
| //usage: "3 + 4.129\n" |
| //usage: "1903 - 2893\n" |
| //usage: "-129 * 213.28935\n" |
| //usage: "12 / -1932\n" |
| //usage: "12 % 12\n" |
| //usage: "34 ^ 189\n" |
| //usage: "scale = 13\n" |
| //usage: "ibase = 2\n" |
| //usage: "obase = A\n" |
| //usage: |
| //usage:#define dc_trivial_usage |
| //usage: IF_FEATURE_DC_BIG("[-x] ")"[-eSCRIPT]... [-fFILE]... [FILE]..." |
| //usage: |
| //usage:#define dc_full_usage "\n" |
| //usage: "\nTiny RPN calculator. Operations:" |
| //usage: "\n+, -, *, /, %, ~, ^," IF_FEATURE_DC_BIG(" |,") |
| //usage: "\np - print top of the stack without popping" |
| //usage: "\nf - print entire stack" |
| //usage: "\nk - pop the value and set the precision" |
| //usage: "\ni - pop the value and set input radix" |
| //usage: "\no - pop the value and set output radix" |
| //usage: "\nExamples: dc -e'2 2 + p' -> 4, dc -e'8 8 * 2 2 + / p' -> 16" |
| //usage: |
| //usage:#define dc_example_usage |
| //usage: "$ dc -e'2 2 + p'\n" |
| //usage: "4\n" |
| //usage: "$ dc -e'8 8 \\* 2 2 + / p'\n" |
| //usage: "16\n" |
| //usage: "$ dc -e'0 1 & p'\n" |
| //usage: "0\n" |
| //usage: "$ dc -e'0 1 | p'\n" |
| //usage: "1\n" |
| //usage: "$ echo '72 9 / 8 * p' | dc\n" |
| //usage: "64\n" |
| |
| #include "libbb.h" |
| #include "common_bufsiz.h" |
| |
| #if !ENABLE_BC && !ENABLE_FEATURE_DC_BIG |
| # include "dc.c" |
| #else |
| |
| #if DEBUG_LEXER |
| static uint8_t lex_indent; |
| #define dbg_lex(...) \ |
| do { \ |
| fprintf(stderr, "%*s", lex_indent, ""); \ |
| bb_error_msg(__VA_ARGS__); \ |
| } while (0) |
| #define dbg_lex_enter(...) \ |
| do { \ |
| dbg_lex(__VA_ARGS__); \ |
| lex_indent++; \ |
| } while (0) |
| #define dbg_lex_done(...) \ |
| do { \ |
| lex_indent--; \ |
| dbg_lex(__VA_ARGS__); \ |
| } while (0) |
| #else |
| # define dbg_lex(...) ((void)0) |
| # define dbg_lex_enter(...) ((void)0) |
| # define dbg_lex_done(...) ((void)0) |
| #endif |
| |
| #if DEBUG_COMPILE |
| # define dbg_compile(...) bb_error_msg(__VA_ARGS__) |
| #else |
| # define dbg_compile(...) ((void)0) |
| #endif |
| |
| #if DEBUG_EXEC |
| # define dbg_exec(...) bb_error_msg(__VA_ARGS__) |
| #else |
| # define dbg_exec(...) ((void)0) |
| #endif |
| |
| typedef enum BcStatus { |
| BC_STATUS_SUCCESS = 0, |
| BC_STATUS_FAILURE = 1, |
| } BcStatus; |
| |
| #define BC_VEC_INVALID_IDX ((size_t) -1) |
| #define BC_VEC_START_CAP (1 << 5) |
| |
| typedef void (*BcVecFree)(void *) FAST_FUNC; |
| |
| typedef struct BcVec { |
| char *v; |
| size_t len; |
| size_t cap; |
| size_t size; |
| BcVecFree dtor; |
| } BcVec; |
| |
| typedef signed char BcDig; |
| |
| typedef struct BcNum { |
| BcDig *restrict num; |
| size_t rdx; |
| size_t len; |
| size_t cap; |
| bool neg; |
| } BcNum; |
| |
| #define BC_NUM_MAX_IBASE 36 |
| // larger value might speed up BIGNUM calculations a bit: |
| #define BC_NUM_DEF_SIZE 16 |
| #define BC_NUM_PRINT_WIDTH 69 |
| |
| #define BC_NUM_KARATSUBA_LEN 32 |
| |
| typedef enum BcInst { |
| #if ENABLE_BC |
| BC_INST_INC_PRE, |
| BC_INST_DEC_PRE, |
| BC_INST_INC_POST, |
| BC_INST_DEC_POST, |
| #endif |
| XC_INST_NEG, // order |
| |
| XC_INST_REL_EQ, // should |
| XC_INST_REL_LE, // match |
| XC_INST_REL_GE, // LEX |
| XC_INST_REL_NE, // constants |
| XC_INST_REL_LT, // for |
| XC_INST_REL_GT, // these |
| |
| XC_INST_POWER, // operations |
| XC_INST_MULTIPLY, // | |
| XC_INST_DIVIDE, // | |
| XC_INST_MODULUS, // | |
| XC_INST_PLUS, // | |
| XC_INST_MINUS, // | |
| |
| XC_INST_BOOL_NOT, // | |
| XC_INST_BOOL_OR, // | |
| XC_INST_BOOL_AND, // | |
| #if ENABLE_BC |
| BC_INST_ASSIGN_POWER, // | |
| BC_INST_ASSIGN_MULTIPLY,// | |
| BC_INST_ASSIGN_DIVIDE, // | |
| BC_INST_ASSIGN_MODULUS, // | |
| BC_INST_ASSIGN_PLUS, // | |
| BC_INST_ASSIGN_MINUS, // | |
| #endif |
| XC_INST_ASSIGN, // V |
| |
| XC_INST_NUM, |
| XC_INST_VAR, |
| XC_INST_ARRAY_ELEM, |
| XC_INST_ARRAY, |
| XC_INST_SCALE_FUNC, |
| |
| XC_INST_IBASE, // order of these constans should match other enums |
| XC_INST_OBASE, // order of these constans should match other enums |
| XC_INST_SCALE, // order of these constans should match other enums |
| IF_BC(BC_INST_LAST,) // order of these constans should match other enums |
| XC_INST_LENGTH, |
| XC_INST_READ, |
| XC_INST_SQRT, |
| |
| XC_INST_PRINT, |
| XC_INST_PRINT_POP, |
| XC_INST_STR, |
| XC_INST_PRINT_STR, |
| |
| #if ENABLE_BC |
| BC_INST_HALT, |
| BC_INST_JUMP, |
| BC_INST_JUMP_ZERO, |
| |
| BC_INST_CALL, |
| BC_INST_RET0, |
| #endif |
| XC_INST_RET, |
| |
| XC_INST_POP, |
| #if ENABLE_DC |
| DC_INST_POP_EXEC, |
| |
| DC_INST_MODEXP, |
| DC_INST_DIVMOD, |
| |
| DC_INST_EXECUTE, |
| DC_INST_EXEC_COND, |
| |
| DC_INST_ASCIIFY, |
| DC_INST_PRINT_STREAM, |
| |
| DC_INST_PRINT_STACK, |
| DC_INST_CLEAR_STACK, |
| DC_INST_STACK_LEN, |
| DC_INST_DUPLICATE, |
| DC_INST_SWAP, |
| |
| DC_INST_LOAD, |
| DC_INST_PUSH_VAR, |
| DC_INST_PUSH_TO_VAR, |
| |
| DC_INST_QUIT, |
| DC_INST_NQUIT, |
| |
| DC_INST_INVALID = -1, |
| #endif |
| } BcInst; |
| |
| typedef struct BcId { |
| char *name; |
| size_t idx; |
| } BcId; |
| |
| typedef struct BcFunc { |
| BcVec code; |
| IF_BC(BcVec labels;) |
| IF_BC(BcVec autos;) |
| IF_BC(BcVec strs;) |
| IF_BC(BcVec consts;) |
| IF_BC(size_t nparams;) |
| IF_BC(bool voidfunc;) |
| } BcFunc; |
| |
| typedef enum BcResultType { |
| XC_RESULT_TEMP, |
| IF_BC(BC_RESULT_VOID,) // same as TEMP, but INST_PRINT will ignore it |
| |
| XC_RESULT_VAR, |
| XC_RESULT_ARRAY_ELEM, |
| XC_RESULT_ARRAY, |
| |
| XC_RESULT_STR, |
| |
| //code uses "inst - XC_INST_IBASE + XC_RESULT_IBASE" construct, |
| XC_RESULT_IBASE, // relative order should match for: XC_INST_IBASE |
| XC_RESULT_OBASE, // relative order should match for: XC_INST_OBASE |
| XC_RESULT_SCALE, // relative order should match for: XC_INST_SCALE |
| IF_BC(BC_RESULT_LAST,) // relative order should match for: BC_INST_LAST |
| XC_RESULT_CONSTANT, |
| IF_BC(BC_RESULT_ONE,) |
| } BcResultType; |
| |
| typedef union BcResultData { |
| BcNum n; |
| BcVec v; |
| BcId id; |
| } BcResultData; |
| |
| typedef struct BcResult { |
| BcResultType t; |
| BcResultData d; |
| } BcResult; |
| |
| typedef struct BcInstPtr { |
| size_t func; |
| size_t inst_idx; |
| } BcInstPtr; |
| |
| typedef enum BcType { |
| BC_TYPE_VAR, |
| BC_TYPE_ARRAY, |
| BC_TYPE_REF, |
| } BcType; |
| |
| typedef enum BcLexType { |
| XC_LEX_EOF, |
| XC_LEX_INVALID, |
| |
| XC_LEX_NLINE, |
| XC_LEX_WHITESPACE, |
| XC_LEX_STR, |
| XC_LEX_NAME, |
| XC_LEX_NUMBER, |
| |
| XC_LEX_1st_op, |
| XC_LEX_NEG = XC_LEX_1st_op, // order |
| |
| XC_LEX_OP_REL_EQ, // should |
| XC_LEX_OP_REL_LE, // match |
| XC_LEX_OP_REL_GE, // INST |
| XC_LEX_OP_REL_NE, // constants |
| XC_LEX_OP_REL_LT, // for |
| XC_LEX_OP_REL_GT, // these |
| |
| XC_LEX_OP_POWER, // operations |
| XC_LEX_OP_MULTIPLY, // | |
| XC_LEX_OP_DIVIDE, // | |
| XC_LEX_OP_MODULUS, // | |
| XC_LEX_OP_PLUS, // | |
| XC_LEX_OP_MINUS, // | |
| XC_LEX_OP_last = XC_LEX_OP_MINUS, |
| #if ENABLE_BC |
| BC_LEX_OP_BOOL_NOT, // | |
| BC_LEX_OP_BOOL_OR, // | |
| BC_LEX_OP_BOOL_AND, // | |
| |
| BC_LEX_OP_ASSIGN_POWER, // | |
| BC_LEX_OP_ASSIGN_MULTIPLY, // | |
| BC_LEX_OP_ASSIGN_DIVIDE, // | |
| BC_LEX_OP_ASSIGN_MODULUS, // | |
| BC_LEX_OP_ASSIGN_PLUS, // | |
| BC_LEX_OP_ASSIGN_MINUS, // | |
| |
| BC_LEX_OP_ASSIGN, // V |
| |
| BC_LEX_OP_INC, |
| BC_LEX_OP_DEC, |
| |
| BC_LEX_LPAREN, // () are 0x28 and 0x29 |
| BC_LEX_RPAREN, // must be LPAREN+1: code uses (c - '(' + BC_LEX_LPAREN) |
| |
| BC_LEX_LBRACKET, // [] are 0x5B and 0x5D |
| BC_LEX_COMMA, |
| BC_LEX_RBRACKET, // must be LBRACKET+2: code uses (c - '[' + BC_LEX_LBRACKET) |
| |
| BC_LEX_LBRACE, // {} are 0x7B and 0x7D |
| BC_LEX_SCOLON, |
| BC_LEX_RBRACE, // must be LBRACE+2: code uses (c - '{' + BC_LEX_LBRACE) |
| |
| BC_LEX_KEY_1st_keyword, |
| BC_LEX_KEY_AUTO = BC_LEX_KEY_1st_keyword, |
| BC_LEX_KEY_BREAK, |
| BC_LEX_KEY_CONTINUE, |
| BC_LEX_KEY_DEFINE, |
| BC_LEX_KEY_ELSE, |
| BC_LEX_KEY_FOR, |
| BC_LEX_KEY_HALT, |
| // code uses "type - BC_LEX_KEY_IBASE + XC_INST_IBASE" construct, |
| BC_LEX_KEY_IBASE, // relative order should match for: XC_INST_IBASE |
| BC_LEX_KEY_OBASE, // relative order should match for: XC_INST_OBASE |
| BC_LEX_KEY_IF, |
| BC_LEX_KEY_LAST, // relative order should match for: BC_INST_LAST |
| BC_LEX_KEY_LENGTH, |
| BC_LEX_KEY_LIMITS, |
| BC_LEX_KEY_PRINT, |
| BC_LEX_KEY_QUIT, |
| BC_LEX_KEY_READ, |
| BC_LEX_KEY_RETURN, |
| BC_LEX_KEY_SCALE, |
| BC_LEX_KEY_SQRT, |
| BC_LEX_KEY_WHILE, |
| #endif // ENABLE_BC |
| |
| #if ENABLE_DC |
| DC_LEX_OP_BOOL_NOT = XC_LEX_OP_last + 1, |
| DC_LEX_OP_ASSIGN, |
| |
| DC_LEX_LPAREN, |
| DC_LEX_SCOLON, |
| DC_LEX_READ, |
| DC_LEX_IBASE, |
| DC_LEX_SCALE, |
| DC_LEX_OBASE, |
| DC_LEX_LENGTH, |
| DC_LEX_PRINT, |
| DC_LEX_QUIT, |
| DC_LEX_SQRT, |
| DC_LEX_LBRACE, |
| |
| DC_LEX_EQ_NO_REG, |
| DC_LEX_OP_MODEXP, |
| DC_LEX_OP_DIVMOD, |
| |
| DC_LEX_COLON, |
| DC_LEX_ELSE, |
| DC_LEX_EXECUTE, |
| DC_LEX_PRINT_STACK, |
| DC_LEX_CLEAR_STACK, |
| DC_LEX_STACK_LEVEL, |
| DC_LEX_DUPLICATE, |
| DC_LEX_SWAP, |
| DC_LEX_POP, |
| |
| DC_LEX_ASCIIFY, |
| DC_LEX_PRINT_STREAM, |
| |
| // code uses "t - DC_LEX_STORE_IBASE + XC_INST_IBASE" construct, |
| DC_LEX_STORE_IBASE, // relative order should match for: XC_INST_IBASE |
| DC_LEX_STORE_OBASE, // relative order should match for: XC_INST_OBASE |
| DC_LEX_STORE_SCALE, // relative order should match for: XC_INST_SCALE |
| DC_LEX_LOAD, |
| DC_LEX_LOAD_POP, |
| DC_LEX_STORE_PUSH, |
| DC_LEX_PRINT_POP, |
| DC_LEX_NQUIT, |
| DC_LEX_SCALE_FACTOR, |
| #endif |
| } BcLexType; |
| // must match order of BC_LEX_KEY_foo etc above |
| #if ENABLE_BC |
| struct BcLexKeyword { |
| char name8[8]; |
| }; |
| #define LEX_KW_ENTRY(a, b) \ |
| { .name8 = a /*, .posix = b */ } |
| static const struct BcLexKeyword bc_lex_kws[20] = { |
| LEX_KW_ENTRY("auto" , 1), // 0 |
| LEX_KW_ENTRY("break" , 1), // 1 |
| LEX_KW_ENTRY("continue", 0), // 2 note: this one has no terminating NUL |
| LEX_KW_ENTRY("define" , 1), // 3 |
| LEX_KW_ENTRY("else" , 0), // 4 |
| LEX_KW_ENTRY("for" , 1), // 5 |
| LEX_KW_ENTRY("halt" , 0), // 6 |
| LEX_KW_ENTRY("ibase" , 1), // 7 |
| LEX_KW_ENTRY("obase" , 1), // 8 |
| LEX_KW_ENTRY("if" , 1), // 9 |
| LEX_KW_ENTRY("last" , 0), // 10 |
| LEX_KW_ENTRY("length" , 1), // 11 |
| LEX_KW_ENTRY("limits" , 0), // 12 |
| LEX_KW_ENTRY("print" , 0), // 13 |
| LEX_KW_ENTRY("quit" , 1), // 14 |
| LEX_KW_ENTRY("read" , 0), // 15 |
| LEX_KW_ENTRY("return" , 1), // 16 |
| LEX_KW_ENTRY("scale" , 1), // 17 |
| LEX_KW_ENTRY("sqrt" , 1), // 18 |
| LEX_KW_ENTRY("while" , 1), // 19 |
| }; |
| #undef LEX_KW_ENTRY |
| #define STRING_else (bc_lex_kws[4].name8) |
| #define STRING_for (bc_lex_kws[5].name8) |
| #define STRING_if (bc_lex_kws[9].name8) |
| #define STRING_while (bc_lex_kws[19].name8) |
| enum { |
| POSIX_KWORD_MASK = 0 |
| | (1 << 0) // 0 |
| | (1 << 1) // 1 |
| | (0 << 2) // 2 |
| | (1 << 3) // 3 |
| | (0 << 4) // 4 |
| | (1 << 5) // 5 |
| | (0 << 6) // 6 |
| | (1 << 7) // 7 |
| | (1 << 8) // 8 |
| | (1 << 9) // 9 |
| | (0 << 10) // 10 |
| | (1 << 11) // 11 |
| | (0 << 12) // 12 |
| | (0 << 13) // 13 |
| | (1 << 14) // 14 |
| | (0 << 15) // 15 |
| | (1 << 16) // 16 |
| | (1 << 17) // 17 |
| | (1 << 18) // 18 |
| | (1 << 19) // 19 |
| }; |
| #define keyword_is_POSIX(i) ((1 << (i)) & POSIX_KWORD_MASK) |
| |
| // This is a bit array that corresponds to token types. An entry is |
| // true if the token is valid in an expression, false otherwise. |
| // Used to figure out when expr parsing should stop *without error message* |
| // - 0 element indicates this condition. 1 means "this token is to be eaten |
| // as part of the expression", it can then still be determined to be invalid |
| // by later processing. |
| enum { |
| #define EXBITS(a,b,c,d,e,f,g,h) \ |
| ((uint64_t)((a << 0)+(b << 1)+(c << 2)+(d << 3)+(e << 4)+(f << 5)+(g << 6)+(h << 7))) |
| BC_PARSE_EXPRS_BITS = 0 // corresponding BC_LEX_xyz: |
| + (EXBITS(0,0,0,0,0,1,1,1) << (0*8)) // 0: EOF INVAL NL WS STR NAME NUM - |
| + (EXBITS(1,1,1,1,1,1,1,1) << (1*8)) // 8: == <= >= != < > ^ * |
| + (EXBITS(1,1,1,1,1,1,1,1) << (2*8)) // 16: / % + - ! || && ^= |
| + (EXBITS(1,1,1,1,1,1,1,1) << (3*8)) // 24: *= /= %= += -= = ++ -- |
| + (EXBITS(1,1,0,0,0,0,0,0) << (4*8)) // 32: ( ) [ , ] { ; } |
| + (EXBITS(0,0,0,0,0,0,0,1) << (5*8)) // 40: auto break cont define else for halt ibase |
| + (EXBITS(1,0,1,1,0,0,0,1) << (6*8)) // 48: obase if last length limits print quit read |
| + (EXBITS(0,1,1,0,0,0,0,0) << (7*8)) // 56: return scale sqrt while |
| #undef EXBITS |
| }; |
| static ALWAYS_INLINE long lex_allowed_in_bc_expr(unsigned i) |
| { |
| #if ULONG_MAX > 0xffffffff |
| // 64-bit version (will not work correctly for 32-bit longs!) |
| return BC_PARSE_EXPRS_BITS & (1UL << i); |
| #else |
| // 32-bit version |
| unsigned long m = (uint32_t)BC_PARSE_EXPRS_BITS; |
| if (i >= 32) { |
| m = (uint32_t)(BC_PARSE_EXPRS_BITS >> 32); |
| i &= 31; |
| } |
| return m & (1UL << i); |
| #endif |
| } |
| |
| // This is an array of data for operators that correspond to |
| // [XC_LEX_1st_op...] token types. |
| static const uint8_t bc_ops_prec_and_assoc[] ALIGN1 = { |
| #define OP(p,l) ((int)(l) * 0x10 + (p)) |
| OP(1, false), // neg |
| OP(6, true ), OP( 6, true ), OP( 6, true ), OP( 6, true ), OP( 6, true ), OP( 6, true ), // == <= >= != < > |
| OP(2, false), // pow |
| OP(3, true ), OP( 3, true ), OP( 3, true ), // mul div mod |
| OP(4, true ), OP( 4, true ), // + - |
| OP(1, false), // not |
| OP(7, true ), OP( 7, true ), // or and |
| OP(5, false), OP( 5, false ), OP( 5, false ), OP( 5, false ), OP( 5, false ), // ^= *= /= %= += |
| OP(5, false), OP( 5, false ), // -= = |
| OP(0, false), OP( 0, false ), // inc dec |
| #undef OP |
| }; |
| #define bc_operation_PREC(i) (bc_ops_prec_and_assoc[i] & 0x0f) |
| #define bc_operation_LEFT(i) (bc_ops_prec_and_assoc[i] & 0x10) |
| #endif // ENABLE_BC |
| |
| #if ENABLE_DC |
| static const //BcLexType - should be this type |
| uint8_t |
| dc_char_to_LEX[] ALIGN1 = { |
| // %&'( |
| XC_LEX_OP_MODULUS, XC_LEX_INVALID, XC_LEX_INVALID, DC_LEX_LPAREN, |
| // )*+, |
| XC_LEX_INVALID, XC_LEX_OP_MULTIPLY, XC_LEX_OP_PLUS, XC_LEX_INVALID, |
| // -./ |
| XC_LEX_OP_MINUS, XC_LEX_INVALID, XC_LEX_OP_DIVIDE, |
| // 0123456789 |
| XC_LEX_INVALID, XC_LEX_INVALID, XC_LEX_INVALID, XC_LEX_INVALID, |
| XC_LEX_INVALID, XC_LEX_INVALID, XC_LEX_INVALID, XC_LEX_INVALID, |
| XC_LEX_INVALID, XC_LEX_INVALID, |
| // :;<=>?@ |
| DC_LEX_COLON, DC_LEX_SCOLON, XC_LEX_OP_REL_GT, XC_LEX_OP_REL_EQ, |
| XC_LEX_OP_REL_LT, DC_LEX_READ, XC_LEX_INVALID, |
| // ABCDEFGH |
| XC_LEX_INVALID, XC_LEX_INVALID, XC_LEX_INVALID, XC_LEX_INVALID, |
| XC_LEX_INVALID, XC_LEX_INVALID, DC_LEX_EQ_NO_REG, XC_LEX_INVALID, |
| // IJKLMNOP |
| DC_LEX_IBASE, XC_LEX_INVALID, DC_LEX_SCALE, DC_LEX_LOAD_POP, |
| XC_LEX_INVALID, DC_LEX_OP_BOOL_NOT, DC_LEX_OBASE, DC_LEX_PRINT_STREAM, |
| // QRSTUVWX |
| DC_LEX_NQUIT, DC_LEX_POP, DC_LEX_STORE_PUSH, XC_LEX_INVALID, |
| XC_LEX_INVALID, XC_LEX_INVALID, XC_LEX_INVALID, DC_LEX_SCALE_FACTOR, |
| // YZ |
| XC_LEX_INVALID, DC_LEX_LENGTH, |
| // [\] |
| XC_LEX_INVALID, XC_LEX_INVALID, XC_LEX_INVALID, |
| // ^_` |
| XC_LEX_OP_POWER, XC_LEX_NEG, XC_LEX_INVALID, |
| // abcdefgh |
| DC_LEX_ASCIIFY, XC_LEX_INVALID, DC_LEX_CLEAR_STACK, DC_LEX_DUPLICATE, |
| DC_LEX_ELSE, DC_LEX_PRINT_STACK, XC_LEX_INVALID, XC_LEX_INVALID, |
| // ijklmnop |
| DC_LEX_STORE_IBASE, XC_LEX_INVALID, DC_LEX_STORE_SCALE, DC_LEX_LOAD, |
| XC_LEX_INVALID, DC_LEX_PRINT_POP, DC_LEX_STORE_OBASE, DC_LEX_PRINT, |
| // qrstuvwx |
| DC_LEX_QUIT, DC_LEX_SWAP, DC_LEX_OP_ASSIGN, XC_LEX_INVALID, |
| XC_LEX_INVALID, DC_LEX_SQRT, XC_LEX_INVALID, DC_LEX_EXECUTE, |
| // yz |
| XC_LEX_INVALID, DC_LEX_STACK_LEVEL, |
| // {|}~ |
| DC_LEX_LBRACE, DC_LEX_OP_MODEXP, XC_LEX_INVALID, DC_LEX_OP_DIVMOD, |
| }; |
| static const //BcInst - should be this type. Using signed narrow type since DC_INST_INVALID is -1 |
| int8_t |
| dc_LEX_to_INST[] ALIGN1 = { //starts at XC_LEX_OP_POWER // corresponding XC/DC_LEX_xyz: |
| XC_INST_POWER, XC_INST_MULTIPLY, // XC_LEX_OP_POWER XC_LEX_OP_MULTIPLY |
| XC_INST_DIVIDE, XC_INST_MODULUS, // XC_LEX_OP_DIVIDE XC_LEX_OP_MODULUS |
| XC_INST_PLUS, XC_INST_MINUS, // XC_LEX_OP_PLUS XC_LEX_OP_MINUS |
| XC_INST_BOOL_NOT, // DC_LEX_OP_BOOL_NOT |
| DC_INST_INVALID, // DC_LEX_OP_ASSIGN |
| XC_INST_REL_GT, // DC_LEX_LPAREN |
| DC_INST_INVALID, // DC_LEX_SCOLON |
| DC_INST_INVALID, // DC_LEX_READ |
| XC_INST_IBASE, // DC_LEX_IBASE |
| XC_INST_SCALE, // DC_LEX_SCALE |
| XC_INST_OBASE, // DC_LEX_OBASE |
| XC_INST_LENGTH, // DC_LEX_LENGTH |
| XC_INST_PRINT, // DC_LEX_PRINT |
| DC_INST_QUIT, // DC_LEX_QUIT |
| XC_INST_SQRT, // DC_LEX_SQRT |
| XC_INST_REL_GE, // DC_LEX_LBRACE |
| XC_INST_REL_EQ, // DC_LEX_EQ_NO_REG |
| DC_INST_MODEXP, DC_INST_DIVMOD, // DC_LEX_OP_MODEXP DC_LEX_OP_DIVMOD |
| DC_INST_INVALID, DC_INST_INVALID, // DC_LEX_COLON DC_LEX_ELSE |
| DC_INST_EXECUTE, // DC_LEX_EXECUTE |
| DC_INST_PRINT_STACK, DC_INST_CLEAR_STACK, // DC_LEX_PRINT_STACK DC_LEX_CLEAR_STACK |
| DC_INST_STACK_LEN, DC_INST_DUPLICATE, // DC_LEX_STACK_LEVEL DC_LEX_DUPLICATE |
| DC_INST_SWAP, XC_INST_POP, // DC_LEX_SWAP DC_LEX_POP |
| DC_INST_ASCIIFY, DC_INST_PRINT_STREAM, // DC_LEX_ASCIIFY DC_LEX_PRINT_STREAM |
| DC_INST_INVALID, DC_INST_INVALID, // DC_LEX_STORE_IBASE DC_LEX_STORE_OBASE |
| DC_INST_INVALID, DC_INST_INVALID, // DC_LEX_STORE_SCALE DC_LEX_LOAD |
| DC_INST_INVALID, DC_INST_INVALID, // DC_LEX_LOAD_POP DC_LEX_STORE_PUSH |
| XC_INST_PRINT, DC_INST_NQUIT, // DC_LEX_PRINT_POP DC_LEX_NQUIT |
| XC_INST_SCALE_FUNC, // DC_LEX_SCALE_FACTOR |
| // DC_INST_INVALID in this table either means that corresponding LEX |
| // is not possible for dc, or that it does not compile one-to-one |
| // to a single INST. |
| }; |
| #endif // ENABLE_DC |
| |
| typedef struct BcParse { |
| smallint lex; // was BcLexType // first member is most used |
| smallint lex_last; // was BcLexType |
| size_t lex_line; |
| const char *lex_inbuf; |
| const char *lex_next_at; // last lex_next() was called at this string |
| const char *lex_filename; |
| FILE *lex_input_fp; |
| BcVec lex_strnumbuf; |
| |
| BcFunc *func; |
| size_t fidx; |
| IF_BC(size_t in_funcdef;) |
| IF_BC(BcVec exits;) |
| IF_BC(BcVec conds;) |
| IF_BC(BcVec ops;) |
| } BcParse; |
| |
| typedef struct BcProgram { |
| size_t len; |
| size_t nchars; |
| |
| size_t scale; |
| size_t ib_t; |
| size_t ob_t; |
| |
| BcVec results; |
| BcVec exestack; |
| |
| BcVec fns; |
| IF_BC(BcVec fn_map;) |
| |
| BcVec vars; |
| BcVec var_map; |
| |
| BcVec arrs; |
| BcVec arr_map; |
| |
| IF_DC(BcVec strs;) |
| IF_DC(BcVec consts;) |
| |
| BcNum zero; |
| IF_BC(BcNum one;) |
| IF_BC(BcNum last;) |
| } BcProgram; |
| |
| struct globals { |
| BcParse prs; // first member is most used |
| |
| // For error messages. Can be set to current parsed line, |
| // or [TODO] to current executing line (can be before last parsed one) |
| size_t err_line; |
| |
| BcVec input_buffer; |
| |
| IF_FEATURE_BC_INTERACTIVE(smallint ttyin;) |
| IF_FEATURE_CLEAN_UP(smallint exiting;) |
| |
| BcProgram prog; |
| |
| BcVec files; |
| |
| char *env_args; |
| |
| #if ENABLE_FEATURE_EDITING |
| line_input_t *line_input_state; |
| #endif |
| } FIX_ALIASING; |
| #define G (*ptr_to_globals) |
| #define INIT_G() do { \ |
| SET_PTR_TO_GLOBALS(xzalloc(sizeof(G))); \ |
| } while (0) |
| #define FREE_G() do { \ |
| FREE_PTR_TO_GLOBALS(); \ |
| } while (0) |
| #define G_posix (ENABLE_BC && (option_mask32 & BC_FLAG_S)) |
| #define G_warn (ENABLE_BC && (option_mask32 & BC_FLAG_W)) |
| #define G_exreg (ENABLE_DC && (option_mask32 & DC_FLAG_X)) |
| #if ENABLE_FEATURE_BC_INTERACTIVE |
| # define G_interrupt bb_got_signal |
| # define G_ttyin G.ttyin |
| #else |
| # define G_interrupt 0 |
| # define G_ttyin 0 |
| #endif |
| #if ENABLE_FEATURE_CLEAN_UP |
| # define G_exiting G.exiting |
| #else |
| # define G_exiting 0 |
| #endif |
| #define IS_BC (ENABLE_BC && (!ENABLE_DC || applet_name[0] == 'b')) |
| #define IS_DC (ENABLE_DC && (!ENABLE_BC || applet_name[0] != 'b')) |
| |
| #if ENABLE_BC |
| # define BC_PARSE_REL (1 << 0) |
| # define BC_PARSE_PRINT (1 << 1) |
| # define BC_PARSE_ARRAY (1 << 2) |
| # define BC_PARSE_NOCALL (1 << 3) |
| #endif |
| |
| #define BC_PROG_MAIN 0 |
| #define BC_PROG_READ 1 |
| #if ENABLE_DC |
| #define BC_PROG_REQ_FUNCS 2 |
| #endif |
| |
| #define BC_FLAG_W (1 << 0) |
| #define BC_FLAG_V (1 << 1) |
| #define BC_FLAG_S (1 << 2) |
| #define BC_FLAG_Q (1 << 3) |
| #define BC_FLAG_L (1 << 4) |
| #define BC_FLAG_I ((1 << 5) * ENABLE_DC) |
| #define DC_FLAG_X ((1 << 6) * ENABLE_DC) |
| |
| #define BC_MAX_OBASE ((unsigned) 999) |
| #define BC_MAX_DIM ((unsigned) INT_MAX) |
| #define BC_MAX_SCALE ((unsigned) UINT_MAX) |
| #define BC_MAX_STRING ((unsigned) UINT_MAX - 1) |
| #define BC_MAX_NUM BC_MAX_STRING |
| // Unused apart from "limits" message. Just show a "biggish number" there. |
| //#define BC_MAX_EXP ((unsigned long) LONG_MAX) |
| //#define BC_MAX_VARS ((unsigned long) SIZE_MAX - 1) |
| #define BC_MAX_EXP_STR "999999999" |
| #define BC_MAX_VARS_STR "999999999" |
| |
| #define BC_MAX_OBASE_STR "999" |
| |
| #if INT_MAX == 2147483647 |
| # define BC_MAX_DIM_STR "2147483647" |
| #elif INT_MAX == 9223372036854775807 |
| # define BC_MAX_DIM_STR "9223372036854775807" |
| #else |
| # error Strange INT_MAX |
| #endif |
| |
| #if UINT_MAX == 4294967295U |
| # define BC_MAX_SCALE_STR "4294967295" |
| # define BC_MAX_STRING_STR "4294967294" |
| #elif UINT_MAX == 18446744073709551615U |
| # define BC_MAX_SCALE_STR "18446744073709551615" |
| # define BC_MAX_STRING_STR "18446744073709551614" |
| #else |
| # error Strange UINT_MAX |
| #endif |
| #define BC_MAX_NUM_STR BC_MAX_STRING_STR |
| |
| // In configurations where errors abort instead of propagating error |
| // return code up the call chain, functions returning BC_STATUS |
| // actually don't return anything, they always succeed and return "void". |
| // A macro wrapper is provided, which makes this statement work: |
| // s = zbc_func(...) |
| // and makes it visible to the compiler that s is always zero, |
| // allowing compiler to optimize dead code after the statement. |
| // |
| // To make code more readable, each such function has a "z" |
| // ("always returning zero") prefix, i.e. zbc_foo or zdc_foo. |
| // |
| #if ENABLE_FEATURE_BC_INTERACTIVE || ENABLE_FEATURE_CLEAN_UP |
| # define ERRORS_ARE_FATAL 0 |
| # define ERRORFUNC /*nothing*/ |
| # define IF_ERROR_RETURN_POSSIBLE(a) a |
| # define BC_STATUS BcStatus |
| # define RETURN_STATUS(v) return (v) |
| # define COMMA_SUCCESS /*nothing*/ |
| #else |
| # define ERRORS_ARE_FATAL 1 |
| # define ERRORFUNC NORETURN |
| # define IF_ERROR_RETURN_POSSIBLE(a) /*nothing*/ |
| # define BC_STATUS void |
| # define RETURN_STATUS(v) do { ((void)(v)); return; } while (0) |
| # define COMMA_SUCCESS ,BC_STATUS_SUCCESS |
| #endif |
| |
| // |
| // Utility routines |
| // |
| |
| #define BC_MAX(a, b) ((a) > (b) ? (a) : (b)) |
| #define BC_MIN(a, b) ((a) < (b) ? (a) : (b)) |
| |
| static void fflush_and_check(void) |
| { |
| fflush_all(); |
| if (ferror(stdout) || ferror(stderr)) |
| bb_simple_perror_msg_and_die("output error"); |
| } |
| |
| #if ENABLE_FEATURE_CLEAN_UP |
| #define QUIT_OR_RETURN_TO_MAIN \ |
| do { \ |
| IF_FEATURE_BC_INTERACTIVE(G_ttyin = 0;) /* do not loop in main loop anymore */ \ |
| G_exiting = 1; \ |
| return BC_STATUS_FAILURE; \ |
| } while (0) |
| #else |
| static void quit(void) NORETURN; |
| static void quit(void) |
| { |
| if (ferror(stdin)) |
| bb_simple_perror_msg_and_die("input error"); |
| fflush_and_check(); |
| dbg_exec("quit(): exiting with exitcode SUCCESS"); |
| exit(0); |
| } |
| #define QUIT_OR_RETURN_TO_MAIN quit() |
| #endif |
| |
| static void bc_verror_msg(const char *fmt, va_list p) |
| { |
| const char *sv = sv; // for compiler |
| if (G.prs.lex_filename) { |
| sv = applet_name; |
| applet_name = xasprintf("%s: %s:%lu", applet_name, |
| G.prs.lex_filename, (unsigned long)G.err_line |
| ); |
| } |
| bb_verror_msg(fmt, p, NULL); |
| if (G.prs.lex_filename) { |
| free((char*)applet_name); |
| applet_name = sv; |
| } |
| } |
| |
| static NOINLINE ERRORFUNC int bc_error_fmt(const char *fmt, ...) |
| { |
| va_list p; |
| |
| va_start(p, fmt); |
| bc_verror_msg(fmt, p); |
| va_end(p); |
| |
| if (ENABLE_FEATURE_CLEAN_UP || G_ttyin) |
| IF_ERROR_RETURN_POSSIBLE(return BC_STATUS_FAILURE); |
| exit(1); |
| } |
| |
| #if ENABLE_BC |
| static NOINLINE BC_STATUS zbc_posix_error_fmt(const char *fmt, ...) |
| { |
| va_list p; |
| |
| // Are non-POSIX constructs totally ok? |
| if (!(option_mask32 & (BC_FLAG_S|BC_FLAG_W))) |
| RETURN_STATUS(BC_STATUS_SUCCESS); // yes |
| |
| va_start(p, fmt); |
| bc_verror_msg(fmt, p); |
| va_end(p); |
| |
| // Do we treat non-POSIX constructs as errors? |
| if (!(option_mask32 & BC_FLAG_S)) |
| RETURN_STATUS(BC_STATUS_SUCCESS); // no, it's a warning |
| |
| if (ENABLE_FEATURE_CLEAN_UP || G_ttyin) |
| RETURN_STATUS(BC_STATUS_FAILURE); |
| exit(1); |
| } |
| #define zbc_posix_error_fmt(...) (zbc_posix_error_fmt(__VA_ARGS__) COMMA_SUCCESS) |
| #endif |
| |
| // We use error functions with "return bc_error(FMT[, PARAMS])" idiom. |
| // This idiom begs for tail-call optimization, but for it to work, |
| // function must not have caller-cleaned parameters on stack. |
| // Unfortunately, vararg function API does exactly that on most arches. |
| // Thus, use these shims for the cases when we have no vararg PARAMS: |
| static ERRORFUNC int bc_error(const char *msg) |
| { |
| IF_ERROR_RETURN_POSSIBLE(return) bc_error_fmt("%s", msg); |
| } |
| static ERRORFUNC int bc_error_at(const char *msg) |
| { |
| const char *err_at = G.prs.lex_next_at; |
| if (err_at) { |
| IF_ERROR_RETURN_POSSIBLE(return) bc_error_fmt( |
| "%s at '%.*s'", |
| msg, |
| (int)(strchrnul(err_at, '\n') - err_at), |
| err_at |
| ); |
| } |
| IF_ERROR_RETURN_POSSIBLE(return) bc_error_fmt("%s", msg); |
| } |
| static ERRORFUNC int bc_error_bad_character(char c) |
| { |
| if (!c) |
| IF_ERROR_RETURN_POSSIBLE(return) bc_error("NUL character"); |
| IF_ERROR_RETURN_POSSIBLE(return) bc_error_fmt("bad character '%c'", c); |
| } |
| #if ENABLE_BC |
| static ERRORFUNC int bc_error_bad_function_definition(void) |
| { |
| IF_ERROR_RETURN_POSSIBLE(return) bc_error_at("bad function definition"); |
| } |
| #endif |
| static ERRORFUNC int bc_error_bad_expression(void) |
| { |
| IF_ERROR_RETURN_POSSIBLE(return) bc_error_at("bad expression"); |
| } |
| static ERRORFUNC int bc_error_bad_assignment(void) |
| { |
| IF_ERROR_RETURN_POSSIBLE(return) bc_error_at( |
| "bad assignment: left side must be variable or array element" |
| ); |
| } |
| static ERRORFUNC int bc_error_bad_token(void) |
| { |
| IF_ERROR_RETURN_POSSIBLE(return) bc_error_at("bad token"); |
| } |
| static ERRORFUNC int bc_error_stack_has_too_few_elements(void) |
| { |
| IF_ERROR_RETURN_POSSIBLE(return) bc_error("stack has too few elements"); |
| } |
| static ERRORFUNC int bc_error_variable_is_wrong_type(void) |
| { |
| IF_ERROR_RETURN_POSSIBLE(return) bc_error("variable is wrong type"); |
| } |
| #if ENABLE_BC |
| static BC_STATUS zbc_POSIX_requires(const char *msg) |
| { |
| RETURN_STATUS(zbc_posix_error_fmt("POSIX requires %s", msg)); |
| } |
| #define zbc_POSIX_requires(...) (zbc_POSIX_requires(__VA_ARGS__) COMMA_SUCCESS) |
| static BC_STATUS zbc_POSIX_does_not_allow(const char *msg) |
| { |
| RETURN_STATUS(zbc_posix_error_fmt("%s%s", "POSIX does not allow ", msg)); |
| } |
| #define zbc_POSIX_does_not_allow(...) (zbc_POSIX_does_not_allow(__VA_ARGS__) COMMA_SUCCESS) |
| static BC_STATUS zbc_POSIX_does_not_allow_bool_ops_this_is_bad(const char *msg) |
| { |
| RETURN_STATUS(zbc_posix_error_fmt("%s%s %s", "POSIX does not allow ", "boolean operators; this is bad:", msg)); |
| } |
| #define zbc_POSIX_does_not_allow_bool_ops_this_is_bad(...) (zbc_POSIX_does_not_allow_bool_ops_this_is_bad(__VA_ARGS__) COMMA_SUCCESS) |
| static BC_STATUS zbc_POSIX_does_not_allow_empty_X_expression_in_for(const char *msg) |
| { |
| RETURN_STATUS(zbc_posix_error_fmt("%san empty %s expression in 'for()'", "POSIX does not allow ", msg)); |
| } |
| #define zbc_POSIX_does_not_allow_empty_X_expression_in_for(...) (zbc_POSIX_does_not_allow_empty_X_expression_in_for(__VA_ARGS__) COMMA_SUCCESS) |
| #endif |
| |
| static void bc_vec_grow(BcVec *v, size_t n) |
| { |
| size_t cap = v->cap * 2; |
| while (cap < v->len + n) cap *= 2; |
| v->v = xrealloc(v->v, v->size * cap); |
| v->cap = cap; |
| } |
| |
| static void bc_vec_init(BcVec *v, size_t esize, BcVecFree dtor) |
| { |
| v->size = esize; |
| v->cap = BC_VEC_START_CAP; |
| v->len = 0; |
| v->dtor = dtor; |
| v->v = xmalloc(esize * BC_VEC_START_CAP); |
| } |
| |
| static void bc_char_vec_init(BcVec *v) |
| { |
| bc_vec_init(v, sizeof(char), NULL); |
| } |
| |
| static void bc_vec_expand(BcVec *v, size_t req) |
| { |
| if (v->cap < req) { |
| v->v = xrealloc(v->v, v->size * req); |
| v->cap = req; |
| } |
| } |
| |
| static void bc_vec_pop(BcVec *v) |
| { |
| v->len--; |
| if (v->dtor) |
| v->dtor(v->v + (v->size * v->len)); |
| } |
| |
| static void bc_vec_npop(BcVec *v, size_t n) |
| { |
| if (!v->dtor) |
| v->len -= n; |
| else { |
| size_t len = v->len - n; |
| while (v->len > len) v->dtor(v->v + (v->size * --v->len)); |
| } |
| } |
| |
| static void bc_vec_pop_all(BcVec *v) |
| { |
| bc_vec_npop(v, v->len); |
| } |
| |
| static size_t bc_vec_npush(BcVec *v, size_t n, const void *data) |
| { |
| size_t len = v->len; |
| if (len + n > v->cap) bc_vec_grow(v, n); |
| memmove(v->v + (v->size * len), data, v->size * n); |
| v->len = len + n; |
| return len; |
| } |
| |
| static size_t bc_vec_push(BcVec *v, const void *data) |
| { |
| return bc_vec_npush(v, 1, data); |
| //size_t len = v->len; |
| //if (len >= v->cap) bc_vec_grow(v, 1); |
| //memmove(v->v + (v->size * len), data, v->size); |
| //v->len = len + 1; |
| //return len; |
| } |
| |
| // G.prog.results often needs "pop old operand, push result" idiom. |
| // Can do this without a few extra ops |
| static size_t bc_result_pop_and_push(const void *data) |
| { |
| BcVec *v = &G.prog.results; |
| char *last; |
| size_t len = v->len - 1; |
| |
| last = v->v + (v->size * len); |
| if (v->dtor) |
| v->dtor(last); |
| memmove(last, data, v->size); |
| return len; |
| } |
| |
| static size_t bc_vec_pushByte(BcVec *v, char data) |
| { |
| return bc_vec_push(v, &data); |
| } |
| |
| static size_t bc_vec_pushZeroByte(BcVec *v) |
| { |
| //return bc_vec_pushByte(v, '\0'); |
| // better: |
| return bc_vec_push(v, &const_int_0); |
| } |
| |
| static void bc_vec_pushAt(BcVec *v, const void *data, size_t idx) |
| { |
| if (idx == v->len) |
| bc_vec_push(v, data); |
| else { |
| char *ptr; |
| |
| if (v->len == v->cap) bc_vec_grow(v, 1); |
| |
| ptr = v->v + v->size * idx; |
| |
| memmove(ptr + v->size, ptr, v->size * (v->len++ - idx)); |
| memmove(ptr, data, v->size); |
| } |
| } |
| |
| static void bc_vec_string(BcVec *v, size_t len, const char *str) |
| { |
| bc_vec_pop_all(v); |
| bc_vec_expand(v, len + 1); |
| memcpy(v->v, str, len); |
| v->len = len; |
| |
| bc_vec_pushZeroByte(v); |
| } |
| |
| static void *bc_vec_item(const BcVec *v, size_t idx) |
| { |
| return v->v + v->size * idx; |
| } |
| |
| static void *bc_vec_item_rev(const BcVec *v, size_t idx) |
| { |
| return v->v + v->size * (v->len - idx - 1); |
| } |
| |
| static void *bc_vec_top(const BcVec *v) |
| { |
| return v->v + v->size * (v->len - 1); |
| } |
| |
| static FAST_FUNC void bc_vec_free(void *vec) |
| { |
| BcVec *v = (BcVec *) vec; |
| bc_vec_pop_all(v); |
| free(v->v); |
| } |
| |
| static BcFunc* xc_program_func(size_t idx) |
| { |
| return bc_vec_item(&G.prog.fns, idx); |
| } |
| // BC_PROG_MAIN is zeroth element, so: |
| #define xc_program_func_BC_PROG_MAIN() ((BcFunc*)(G.prog.fns.v)) |
| |
| #if ENABLE_BC |
| static BcFunc* bc_program_current_func(void) |
| { |
| BcInstPtr *ip = bc_vec_top(&G.prog.exestack); |
| BcFunc *func = xc_program_func(ip->func); |
| return func; |
| } |
| #endif |
| |
| static char** xc_program_str(size_t idx) |
| { |
| #if ENABLE_BC |
| if (IS_BC) { |
| BcFunc *func = bc_program_current_func(); |
| return bc_vec_item(&func->strs, idx); |
| } |
| #endif |
| IF_DC(return bc_vec_item(&G.prog.strs, idx);) |
| } |
| |
| static char** xc_program_const(size_t idx) |
| { |
| #if ENABLE_BC |
| if (IS_BC) { |
| BcFunc *func = bc_program_current_func(); |
| return bc_vec_item(&func->consts, idx); |
| } |
| #endif |
| IF_DC(return bc_vec_item(&G.prog.consts, idx);) |
| } |
| |
| static int bc_id_cmp(const void *e1, const void *e2) |
| { |
| return strcmp(((const BcId *) e1)->name, ((const BcId *) e2)->name); |
| } |
| |
| static FAST_FUNC void bc_id_free(void *id) |
| { |
| free(((BcId *) id)->name); |
| } |
| |
| static size_t bc_map_find_ge(const BcVec *v, const void *ptr) |
| { |
| size_t low = 0, high = v->len; |
| |
| while (low < high) { |
| size_t mid = (low + high) / 2; |
| BcId *id = bc_vec_item(v, mid); |
| int result = bc_id_cmp(ptr, id); |
| |
| if (result == 0) |
| return mid; |
| if (result < 0) |
| high = mid; |
| else |
| low = mid + 1; |
| } |
| |
| return low; |
| } |
| |
| static int bc_map_insert(BcVec *v, const void *ptr, size_t *i) |
| { |
| size_t n = *i = bc_map_find_ge(v, ptr); |
| |
| if (n == v->len) |
| bc_vec_push(v, ptr); |
| else if (!bc_id_cmp(ptr, bc_vec_item(v, n))) |
| return 0; // "was not inserted" |
| else |
| bc_vec_pushAt(v, ptr, n); |
| return 1; // "was inserted" |
| } |
| |
| static size_t bc_map_find_exact(const BcVec *v, const void *ptr) |
| { |
| size_t i = bc_map_find_ge(v, ptr); |
| if (i >= v->len) return BC_VEC_INVALID_IDX; |
| return bc_id_cmp(ptr, bc_vec_item(v, i)) ? BC_VEC_INVALID_IDX : i; |
| } |
| |
| static void bc_num_setToZero(BcNum *n, size_t scale) |
| { |
| n->len = 0; |
| n->neg = false; |
| n->rdx = scale; |
| } |
| |
| static void bc_num_zero(BcNum *n) |
| { |
| bc_num_setToZero(n, 0); |
| } |
| |
| static void bc_num_one(BcNum *n) |
| { |
| bc_num_setToZero(n, 0); |
| n->len = 1; |
| n->num[0] = 1; |
| } |
| |
| // Note: this also sets BcNum to zero |
| static void bc_num_init(BcNum *n, size_t req) |
| { |
| req = req >= BC_NUM_DEF_SIZE ? req : BC_NUM_DEF_SIZE; |
| //memset(n, 0, sizeof(BcNum)); - cleared by assignments below |
| n->num = xmalloc(req); |
| n->cap = req; |
| n->rdx = 0; |
| n->len = 0; |
| n->neg = false; |
| } |
| |
| static void bc_num_init_DEF_SIZE(BcNum *n) |
| { |
| bc_num_init(n, BC_NUM_DEF_SIZE); |
| } |
| |
| static void bc_num_expand(BcNum *n, size_t req) |
| { |
| req = req >= BC_NUM_DEF_SIZE ? req : BC_NUM_DEF_SIZE; |
| if (req > n->cap) { |
| n->num = xrealloc(n->num, req); |
| n->cap = req; |
| } |
| } |
| |
| static FAST_FUNC void bc_num_free(void *num) |
| { |
| free(((BcNum *) num)->num); |
| } |
| |
| static void bc_num_copy(BcNum *d, BcNum *s) |
| { |
| if (d != s) { |
| bc_num_expand(d, s->cap); |
| d->len = s->len; |
| d->neg = s->neg; |
| d->rdx = s->rdx; |
| memcpy(d->num, s->num, sizeof(BcDig) * d->len); |
| } |
| } |
| |
| static BC_STATUS zbc_num_ulong_abs(BcNum *n, unsigned long *result_p) |
| { |
| size_t i; |
| unsigned long result; |
| |
| result = 0; |
| i = n->len; |
| while (i > n->rdx) { |
| unsigned long prev = result; |
| result = result * 10 + n->num[--i]; |
| // Even overflowed N*10 can still satisfy N*10>=N. For example, |
| // 0x1ff00000 * 10 is 0x13f600000, |
| // or 0x3f600000 truncated to 32 bits. Which is larger. |
| // However, (N*10)/8 < N check is always correct. |
| if ((result / 8) < prev) |
| RETURN_STATUS(bc_error("overflow")); |
| } |
| *result_p = result; |
| |
| RETURN_STATUS(BC_STATUS_SUCCESS); |
| } |
| #define zbc_num_ulong_abs(...) (zbc_num_ulong_abs(__VA_ARGS__) COMMA_SUCCESS) |
| |
| static BC_STATUS zbc_num_ulong(BcNum *n, unsigned long *result_p) |
| { |
| if (n->neg) RETURN_STATUS(bc_error("negative number")); |
| |
| RETURN_STATUS(zbc_num_ulong_abs(n, result_p)); |
| } |
| #define zbc_num_ulong(...) (zbc_num_ulong(__VA_ARGS__) COMMA_SUCCESS) |
| |
| #if ULONG_MAX == 0xffffffffUL // 10 digits: 4294967295 |
| # define ULONG_NUM_BUFSIZE (10 > BC_NUM_DEF_SIZE ? 10 : BC_NUM_DEF_SIZE) |
| #elif ULONG_MAX == 0xffffffffffffffffULL // 20 digits: 18446744073709551615 |
| # define ULONG_NUM_BUFSIZE (20 > BC_NUM_DEF_SIZE ? 20 : BC_NUM_DEF_SIZE) |
| #endif |
| // minimum BC_NUM_DEF_SIZE, so that bc_num_expand() in bc_num_ulong2num() |
| // would not hit realloc() code path - not good if num[] is not malloced |
| |
| static void bc_num_ulong2num(BcNum *n, unsigned long val) |
| { |
| BcDig *ptr; |
| |
| bc_num_zero(n); |
| |
| if (val == 0) return; |
| |
| bc_num_expand(n, ULONG_NUM_BUFSIZE); |
| |
| ptr = n->num; |
| for (;;) { |
| n->len++; |
| *ptr++ = val % 10; |
| val /= 10; |
| if (val == 0) break; |
| } |
| } |
| |
| static void bc_num_subArrays(BcDig *restrict a, BcDig *restrict b, size_t len) |
| { |
| size_t i, j; |
| for (i = 0; i < len; ++i) { |
| a[i] -= b[i]; |
| for (j = i; a[j] < 0;) { |
| a[j++] += 10; |
| a[j] -= 1; |
| } |
| } |
| } |
| |
| static ssize_t bc_num_compare(BcDig *restrict a, BcDig *restrict b, size_t len) |
| { |
| size_t i = len; |
| for (;;) { |
| int c; |
| if (i == 0) |
| return 0; |
| i--; |
| c = a[i] - b[i]; |
| if (c != 0) { |
| i++; |
| if (c < 0) |
| return -i; |
| return i; |
| } |
| } |
| } |
| |
| #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; |
| BcDig *max_num, *min_num; |
| bool a_max, neg; |
| ssize_t cmp; |
| |
| if (a == b) return 0; |
| if (a->len == 0) return BC_NUM_NEG(!!b->len, !b->neg); |
| if (b->len == 0) return BC_NUM_NEG(1, a->neg); |
| |
| if (a->neg != b->neg) // signs of a and b differ |
| // +a,-b = a>b = 1 or -a,+b = a<b = -1 |
| return (int)b->neg - (int)a->neg; |
| neg = a->neg; // 1 if both negative, 0 if both positive |
| |
| a_int = BC_NUM_INT(a); |
| b_int = BC_NUM_INT(b); |
| a_int -= b_int; |
| |
| if (a_int != 0) { |
| if (neg) return - (ssize_t) a_int; |
| return (ssize_t) a_int; |
| } |
| |
| a_max = (a->rdx > b->rdx); |
| if (a_max) { |
| min = b->rdx; |
| diff = a->rdx - b->rdx; |
| max_num = a->num + diff; |
| min_num = b->num; |
| // neg = (a_max == neg); - NOP (maps 1->1 and 0->0) |
| } else { |
| min = a->rdx; |
| diff = b->rdx - a->rdx; |
| max_num = b->num + diff; |
| min_num = a->num; |
| neg = !neg; // same as "neg = (a_max == neg)" |
| } |
| |
| cmp = bc_num_compare(max_num, min_num, b_int + min); |
| if (cmp != 0) return BC_NUM_NEG(cmp, neg); |
| |
| for (max_num -= diff, i = diff - 1; i < diff; --i) { |
| if (max_num[i]) return BC_NUM_NEG(1, neg); |
| } |
| |
| return 0; |
| } |
| |
| static void bc_num_truncate(BcNum *n, size_t places) |
| { |
| if (places == 0) return; |
| |
| n->rdx -= places; |
| |
| if (n->len != 0) { |
| n->len -= places; |
| memmove(n->num, n->num + places, n->len * sizeof(BcDig)); |
| } |
| } |
| |
| static void bc_num_extend(BcNum *n, size_t places) |
| { |
| size_t len = n->len + places; |
| |
| if (places != 0) { |
| if (n->cap < len) bc_num_expand(n, len); |
| |
| memmove(n->num + places, n->num, sizeof(BcDig) * n->len); |
| memset(n->num, 0, sizeof(BcDig) * places); |
| |
| n->len += places; |
| n->rdx += places; |
| } |
| } |
| |
| static void bc_num_clean(BcNum *n) |
| { |
| while (n->len > 0 && n->num[n->len - 1] == 0) --n->len; |
| if (n->len == 0) |
| n->neg = false; |
| else if (n->len < n->rdx) |
| n->len = n->rdx; |
| } |
| |
| static void bc_num_retireMul(BcNum *n, size_t scale, bool neg1, bool neg2) |
| { |
| if (n->rdx < scale) |
| bc_num_extend(n, scale - n->rdx); |
| else |
| bc_num_truncate(n, n->rdx - scale); |
| |
| bc_num_clean(n); |
| if (n->len != 0) n->neg = !neg1 != !neg2; |
| } |
| |
| static void bc_num_split(BcNum *restrict n, size_t idx, BcNum *restrict a, |
| BcNum *restrict b) |
| { |
| if (idx < n->len) { |
| b->len = n->len - idx; |
| a->len = idx; |
| a->rdx = b->rdx = 0; |
| |
| memcpy(b->num, n->num + idx, b->len * sizeof(BcDig)); |
| memcpy(a->num, n->num, idx * sizeof(BcDig)); |
| } else { |
| bc_num_zero(b); |
| bc_num_copy(a, n); |
| } |
| |
| bc_num_clean(a); |
| bc_num_clean(b); |
| } |
| |
| static BC_STATUS zbc_num_shift(BcNum *n, size_t places) |
| { |
| if (places == 0 || n->len == 0) RETURN_STATUS(BC_STATUS_SUCCESS); |
| |
| // This check makes sense only if size_t is (much) larger than BC_MAX_NUM. |
| if (SIZE_MAX > (BC_MAX_NUM | 0xff)) { |
| if (places + n->len > BC_MAX_NUM) |
| RETURN_STATUS(bc_error("number too long: must be [1,"BC_MAX_NUM_STR"]")); |
| } |
| |
| if (n->rdx >= places) |
| n->rdx -= places; |
| else { |
| bc_num_extend(n, places - n->rdx); |
| n->rdx = 0; |
| } |
| |
| bc_num_clean(n); |
| |
| RETURN_STATUS(BC_STATUS_SUCCESS); |
| } |
| #define zbc_num_shift(...) (zbc_num_shift(__VA_ARGS__) COMMA_SUCCESS) |
| |
| 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) |
| { |
| BcStatus s; |
| BcNum num2, *ptr_a, *ptr_b; |
| bool init = false; |
| |
| if (c == a) { |
| ptr_a = &num2; |
| memcpy(ptr_a, c, sizeof(BcNum)); |
| init = true; |
| } else |
| ptr_a = a; |
| |
| if (c == b) { |
| ptr_b = &num2; |
| if (c != a) { |
| memcpy(ptr_b, c, sizeof(BcNum)); |
| init = true; |
| } |
| } else |
| ptr_b = b; |
| |
| if (init) |
| bc_num_init(c, req); |
| else |
| bc_num_expand(c, req); |
| |
| s = BC_STATUS_SUCCESS; |
| IF_ERROR_RETURN_POSSIBLE(s =) op(ptr_a, ptr_b, c, scale); |
| |
| if (init) bc_num_free(&num2); |
| |
| RETURN_STATUS(s); |
| } |
| #define zbc_num_binary(...) (zbc_num_binary(__VA_ARGS__) COMMA_SUCCESS) |
| |
| 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 zxc_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; |
| } |
| |
| ptr_c = c->num; |
| for (i = 0; i < diff; ++i, ++c->len) |
| ptr_c[i] = ptr[i]; |
| |
| ptr_c += diff; |
| a_int = BC_NUM_INT(a); |
| b_int = BC_NUM_INT(b); |
| |
| if (a_int > b_int) { |
| min_int = b_int; |
| max = a_int; |
| ptr = ptr_a; |
| } else { |
| min_int = a_int; |
| max = b_int; |
| ptr = ptr_b; |
| } |
| |
| carry = 0; |
| for (i = 0; i < min_rdx + min_int; ++i) { |
| unsigned in = (unsigned)ptr_a[i] + (unsigned)ptr_b[i] + carry; |
| carry = in / 10; |
| ptr_c[i] = (BcDig)(in % 10); |
| } |
| for (; i < max + min_rdx; ++i) { |
| unsigned in = (unsigned)ptr[i] + carry; |
| carry = in / 10; |
| ptr_c[i] = (BcDig)(in % 10); |
| } |
| c->len += i; |
| |
| if (carry != 0) c->num[c->len++] = (BcDig) carry; |
| |
| RETURN_STATUS(BC_STATUS_SUCCESS); // can't make void, see zbc_num_binary() |
| } |
| |
| static FAST_FUNC BC_STATUS zbc_num_s(BcNum *a, BcNum *b, BcNum *restrict c, size_t sub) |
| { |
| ssize_t cmp; |
| BcNum *minuend, *subtrahend; |
| size_t start; |
| bool aneg, bneg, neg; |
| |
| // 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); |
| } |
| |
| aneg = a->neg; |
| bneg = b->neg; |
| a->neg = b->neg = false; |
| |
| cmp = bc_num_cmp(a, b); |
| |
| a->neg = aneg; |
| b->neg = bneg; |
| |
| if (cmp == 0) { |
| bc_num_setToZero(c, BC_MAX(a->rdx, b->rdx)); |
| RETURN_STATUS(BC_STATUS_SUCCESS); |
| } |
| if (cmp > 0) { |
| neg = a->neg; |
| minuend = a; |
| subtrahend = b; |
| } else { |
| neg = b->neg; |
| if (sub) neg = !neg; |
| minuend = b; |
| subtrahend = a; |
| } |
| |
| bc_num_copy(c, minuend); |
| c->neg = neg; |
| |
| if (c->rdx < subtrahend->rdx) { |
| bc_num_extend(c, subtrahend->rdx - c->rdx); |
| start = 0; |
| } else |
| start = c->rdx - subtrahend->rdx; |
| |
| bc_num_subArrays(c->num + start, subtrahend->num, subtrahend->len); |
| |
| bc_num_clean(c); |
| |
| RETURN_STATUS(BC_STATUS_SUCCESS); // can't make void, see zbc_num_binary() |
| } |
| |
| static FAST_FUNC BC_STATUS zbc_num_k(BcNum *restrict a, BcNum *restrict b, |
| BcNum *restrict c) |
| #define zbc_num_k(...) (zbc_num_k(__VA_ARGS__) COMMA_SUCCESS) |
| { |
| BcStatus s; |
| size_t max = BC_MAX(a->len, b->len), max2 = (max + 1) / 2; |
| BcNum l1, h1, l2, h2, m2, m1, z0, z1, z2, temp; |
| bool aone; |
| |
| if (a->len == 0 || b->len == 0) { |
| bc_num_zero(c); |
| RETURN_STATUS(BC_STATUS_SUCCESS); |
| } |
| aone = BC_NUM_ONE(a); |
| if (aone || BC_NUM_ONE(b)) { |
| bc_num_copy(c, aone ? b : a); |
| RETURN_STATUS(BC_STATUS_SUCCESS); |
| } |
| |
| if (a->len + b->len < BC_NUM_KARATSUBA_LEN |
| || a->len < BC_NUM_KARATSUBA_LEN |
| || b->len < BC_NUM_KARATSUBA_LEN |
| ) { |
| size_t i, j, len; |
| |
| bc_num_expand(c, a->len + b->len + 1); |
| |
| memset(c->num, 0, sizeof(BcDig) * c->cap); |
| c->len = len = 0; |
| |
| for (i = 0; i < b->len; ++i) { |
| unsigned carry = 0; |
| for (j = 0; j < a->len; ++j) { |
| unsigned in = c->num[i + j]; |
| in += (unsigned)a->num[j] * (unsigned)b->num[i] + carry; |
| // note: compilers prefer _unsigned_ div/const |
| carry = in / 10; |
| c->num[i + j] = (BcDig)(in % 10); |
| } |
| |
| c->num[i + j] += (BcDig) carry; |
| len = BC_MAX(len, i + j + !!carry); |
| |
| #if ENABLE_FEATURE_BC_INTERACTIVE |
| // a=2^1000000 |
| // a*a <- without check below, this will not be interruptible |
| if (G_interrupt) return BC_STATUS_FAILURE; |
| #endif |
| } |
| |
| c->len = len; |
| |
| RETURN_STATUS(BC_STATUS_SUCCESS); |
| } |
| |
| bc_num_init(&l1, max); |
| bc_num_init(&h1, max); |
| bc_num_init(&l2, max); |
| bc_num_init(&h2, max); |
| bc_num_init(&m1, max); |
| bc_num_init(&m2, max); |
| bc_num_init(&z0, max); |
| bc_num_init(&z1, max); |
| bc_num_init(&z2, max); |
| bc_num_init(&temp, max + max); |
| |
| bc_num_split(a, max2, &l1, &h1); |
| bc_num_split(b, max2, &l2, &h2); |
| |
| s = zbc_num_add(&h1, &l1, &m1, 0); |
| if (s) goto err; |
| s = zbc_num_add(&h2, &l2, &m2, 0); |
| if (s) goto err; |
| |
| s = zbc_num_k(&h1, &h2, &z0); |
| if (s) goto err; |
| s = zbc_num_k(&m1, &m2, &z1); |
| if (s) goto err; |
| s = zbc_num_k(&l1, &l2, &z2); |
| if (s) goto err; |
| |
| s = zbc_num_sub(&z1, &z0, &temp, 0); |
| if (s) goto err; |
| s = zbc_num_sub(&temp, &z2, &z1, 0); |
| if (s) goto err; |
| |
| s = zbc_num_shift(&z0, max2 * 2); |
| if (s) goto err; |
| s = zbc_num_shift(&z1, max2); |
| if (s) goto err; |
| s = zbc_num_add(&z0, &z1, &temp, 0); |
| if (s) goto err; |
| s = zbc_num_add(&temp, &z2, c, 0); |
| err: |
| bc_num_free(&temp); |
| bc_num_free(&z2); |
| bc_num_free(&z1); |
| bc_num_free(&z0); |
| bc_num_free(&m2); |
| bc_num_free(&m1); |
| bc_num_free(&h2); |
| bc_num_free(&l2); |
| bc_num_free(&h1); |
| bc_num_free(&l1); |
| RETURN_STATUS(s); |
| } |
| |
| static FAST_FUNC BC_STATUS zbc_num_m(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale) |
| { |
| BcStatus s; |
| BcNum cpa, cpb; |
| size_t maxrdx = BC_MAX(a->rdx, b->rdx); |
| |
| scale = BC_MAX(scale, a->rdx); |
| scale = BC_MAX(scale, b->rdx); |
| scale = BC_MIN(a->rdx + b->rdx, scale); |
| maxrdx = BC_MAX(maxrdx, scale); |
| |
| bc_num_init(&cpa, a->len); |
| bc_num_init(&cpb, b->len); |
| |
| bc_num_copy(&cpa, a); |
| bc_num_copy(&cpb, b); |
| cpa.neg = cpb.neg = false; |
| |
| s = zbc_num_shift(&cpa, maxrdx); |
| if (s) goto err; |
| s = zbc_num_shift(&cpb, maxrdx); |
| if (s) goto err; |
| s = zbc_num_k(&cpa, &cpb, c); |
| if (s) goto err; |
| |
| maxrdx += scale; |
| bc_num_expand(c, c->len + maxrdx); |
| |
| if (c->len < maxrdx) { |
| memset(c->num + c->len, 0, (c->cap - c->len) * sizeof(BcDig)); |
| c->len += maxrdx; |
| } |
| |
| c->rdx = maxrdx; |
| bc_num_retireMul(c, scale, a->neg, b->neg); |
| err: |
| bc_num_free(&cpb); |
| bc_num_free(&cpa); |
| RETURN_STATUS(s); |
| } |
| #define zbc_num_m(...) (zbc_num_m(__VA_ARGS__) COMMA_SUCCESS) |
| |
| static FAST_FUNC BC_STATUS zbc_num_d(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale) |
| { |
| BcStatus s; |
| size_t len, end, i; |
| BcNum cp; |
| |
| if (b->len == 0) |
| RETURN_STATUS(bc_error("divide by zero")); |
| if (a->len == 0) { |
| bc_num_setToZero(c, scale); |
| RETURN_STATUS(BC_STATUS_SUCCESS); |
| } |
| if (BC_NUM_ONE(b)) { |
| bc_num_copy(c, a); |
| bc_num_retireMul(c, scale, a->neg, b->neg); |
| RETURN_STATUS(BC_STATUS_SUCCESS); |
| } |
| |
| bc_num_init(&cp, BC_NUM_MREQ(a, b, scale)); |
| bc_num_copy(&cp, a); |
| len = b->len; |
| |
| if (len > cp.len) { |
| bc_num_expand(&cp, len + 2); |
| bc_num_extend(&cp, len - cp.len); |
| } |
| |
| if (b->rdx > cp.rdx) bc_num_extend(&cp, b->rdx - cp.rdx); |
| cp.rdx -= b->rdx; |
| if (scale > cp.rdx) bc_num_extend(&cp, scale - cp.rdx); |
| |
| if (b->rdx == b->len) { |
| for (;;) { |
| if (len == 0) break; |
| len--; |
| if (b->num[len] != 0) |
| break; |
| } |
| len++; |
| } |
| |
| if (cp.cap == cp.len) bc_num_expand(&cp, cp.len + 1); |
| |
| // We want an extra zero in front to make things simpler. |
| cp.num[cp.len++] = 0; |
| end = cp.len - len; |
| |
| bc_num_expand(c, cp.len); |
| |
| bc_num_zero(c); |
| memset(c->num + end, 0, (c->cap - end) * sizeof(BcDig)); |
| c->rdx = cp.rdx; |
| c->len = cp.len; |
| |
| s = BC_STATUS_SUCCESS; |
| for (i = end - 1; i < end; --i) { |
| BcDig *n, q; |
| n = cp.num + i; |
| for (q = 0; n[len] != 0 || bc_num_compare(n, b->num, len) >= 0; ++q) |
| bc_num_subArrays(n, b->num, len); |
| c->num[i] = q; |
| #if ENABLE_FEATURE_BC_INTERACTIVE |
| // a=2^100000 |
| // scale=40000 |
| // 1/a <- without check below, this will not be interruptible |
| if (G_interrupt) { |
| s = BC_STATUS_FAILURE; |
| break; |
| } |
| #endif |
| } |
| |
| bc_num_retireMul(c, scale, a->neg, b->neg); |
| bc_num_free(&cp); |
| |
| RETURN_STATUS(s); |
| } |
| #define zbc_num_d(...) (zbc_num_d(__VA_ARGS__) COMMA_SUCCESS) |
| |
| static FAST_FUNC BC_STATUS zbc_num_r(BcNum *a, BcNum *b, BcNum *restrict c, |
| BcNum *restrict d, size_t scale, size_t ts) |
| { |
| BcStatus s; |
| BcNum temp; |
| bool neg; |
| |
| if (b->len == 0) |
| RETURN_STATUS(bc_error("divide by zero")); |
| |
| if (a->len == 0) { |
| bc_num_setToZero(d, ts); |
| RETURN_STATUS(BC_STATUS_SUCCESS); |
| } |
| |
| bc_num_init(&temp, d->cap); |
| s = zbc_num_d(a, b, c, scale); |
| if (s) goto err; |
| |
| if (scale != 0) scale = ts; |
| |
| s = zbc_num_m(c, b, &temp, scale); |
| if (s) goto err; |
| s = zbc_num_sub(a, &temp, d, scale); |
| if (s) goto err; |
| |
| if (ts > d->rdx && d->len) bc_num_extend(d, ts - d->rdx); |
| |
| neg = d->neg; |
| bc_num_retireMul(d, ts, a->neg, b->neg); |
| d->neg = neg; |
| err: |
| bc_num_free(&temp); |
| RETURN_STATUS(s); |
| } |
| #define zbc_num_r(...) (zbc_num_r(__VA_ARGS__) COMMA_SUCCESS) |
| |
| static FAST_FUNC BC_STATUS zbc_num_rem(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale) |
| { |
| BcStatus s; |
| BcNum c1; |
| size_t ts = BC_MAX(scale + b->rdx, a->rdx), len = BC_NUM_MREQ(a, b, ts); |
| |
| bc_num_init(&c1, len); |
| s = zbc_num_r(a, b, &c1, c, scale, ts); |
| bc_num_free(&c1); |
| |
| RETURN_STATUS(s); |
| } |
| #define zbc_num_rem(...) (zbc_num_rem(__VA_ARGS__) COMMA_SUCCESS) |
| |
| static FAST_FUNC BC_STATUS zbc_num_p(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale) |
| { |
| BcStatus s = BC_STATUS_SUCCESS; |
| BcNum copy; |
| unsigned long pow; |
| size_t i, powrdx, resrdx; |
| bool neg; |
| |
| // GNU bc does not allow 2^2.0 - we do |
| for (i = 0; i < b->rdx; i++) |
| if (b->num[i] != 0) |
| RETURN_STATUS(bc_error("not an integer")); |
| |
| if (b->len == 0) { |
| bc_num_one(c); |
| RETURN_STATUS(BC_STATUS_SUCCESS); |
| } |
| if (a->len == 0) { |
| bc_num_setToZero(c, scale); |
| RETURN_STATUS(BC_STATUS_SUCCESS); |
| } |
| if (BC_NUM_ONE(b)) { |
| if (!b->neg) |
| bc_num_copy(c, a); |
| else |
| s = zbc_num_inv(a, c, scale); |
| RETURN_STATUS(s); |
| } |
| |
| neg = b->neg; |
| s = zbc_num_ulong_abs(b, &pow); |
| if (s) RETURN_STATUS(s); |
| // b is not used beyond this point |
| |
| bc_num_init(©, a->len); |
| bc_num_copy(©, a); |
| |
| if (!neg) { |
| if (a->rdx > scale) |
| scale = a->rdx; |
| if (a->rdx * pow < scale) |
| scale = a->rdx * pow; |
| } |
| |
| |
| for (powrdx = a->rdx; !(pow & 1); pow >>= 1) { |
| powrdx <<= 1; |
| s = zbc_num_mul(©, ©, ©, powrdx); |
| if (s) goto err; |
| // Not needed: zbc_num_mul() has a check for ^C: |
| //if (G_interrupt) { |
| // s = BC_STATUS_FAILURE; |
| // goto err; |
| //} |
| } |
| |
| bc_num_copy(c, ©); |
| |
| for (resrdx = powrdx, pow >>= 1; pow != 0; pow >>= 1) { |
| powrdx <<= 1; |
| s = zbc_num_mul(©, ©, ©, powrdx); |
| if (s) goto err; |
| |
| if (pow & 1) { |
| resrdx += powrdx; |
| s = zbc_num_mul(c, ©, c, resrdx); |
| if (s) goto err; |
| } |
| // Not needed: zbc_num_mul() has a check for ^C: |
| //if (G_interrupt) { |
| // s = BC_STATUS_FAILURE; |
| // goto err; |
| //} |
| } |
| |
| if (neg) { |
| s = zbc_num_inv(c, c, scale); |
| if (s) goto err; |
| } |
| |
| if (c->rdx > scale) bc_num_truncate(c, c->rdx - scale); |
| |
| // We can't use bc_num_clean() here. |
| for (i = 0; i < c->len; ++i) |
| if (c->num[i] != 0) |
| goto skip; |
| bc_num_setToZero(c, scale); |
| skip: |
| |
| err: |
| bc_num_free(©); |
| RETURN_STATUS(s); |
| } |
| #define zbc_num_p(...) (zbc_num_p(__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; |
| BcDig half_digs[1]; |
| 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); |
| |
| half.cap = ARRAY_SIZE(half_digs); |
| half.num = half_digs; |
| bc_num_one(&half); |
| half_digs[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(&num2); |
| bc_num_free(&num1); |
| RETURN_STATUS(s); |
| } |
| #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) |
| { |
| BcStatus s; |
| BcNum num2, *ptr_a; |
| bool init = false; |
| size_t ts = BC_MAX(scale + b->rdx, a->rdx), len = BC_NUM_MREQ(a, b, ts); |
| |
| if (c == a) { |
| memcpy(&num2, c, sizeof(BcNum)); |
| ptr_a = &num2; |
| bc_num_init(c, len); |
| init = true; |
| } else { |
| ptr_a = a; |
| bc_num_expand(c, len); |
| } |
| |
| s = zbc_num_r(ptr_a, b, c, d, scale, ts); |
| |
| if (init) bc_num_free(&num2); |
| |
| RETURN_STATUS(s); |
| } |
| #define zbc_num_divmod(...) (zbc_num_divmod(__VA_ARGS__) COMMA_SUCCESS) |
| |
| #if ENABLE_DC |
| static BC_STATUS zdc_num_modexp(BcNum *a, BcNum *b, BcNum *c, BcNum *restrict d) |
| { |
| BcStatus s; |
| BcNum base, exp, two, temp; |
| BcDig two_digs[1]; |
| |
| if (c->len == 0) |
| RETURN_STATUS(bc_error("divide by zero")); |
| if (a->rdx || b->rdx || c->rdx) |
| RETURN_STATUS(bc_error("not an integer")); |
| if (b->neg) |
| RETURN_STATUS(bc_error("negative number")); |
| |
| bc_num_expand(d, c->len); |
| bc_num_init(&base, c->len); |
| bc_num_init(&exp, b->len); |
| bc_num_init(&temp, b->len); |
| |
| two.cap = ARRAY_SIZE(two_digs); |
| two.num = two_digs; |
| bc_num_one(&two); |
| two_digs[0] = 2; |
| |
| bc_num_one(d); |
| |
| s = zbc_num_rem(a, c, &base, 0); |
| if (s) goto err; |
| bc_num_copy(&exp, b); |
| |
| while (exp.len != 0) { |
| s = zbc_num_divmod(&exp, &two, &exp, &temp, 0); |
| if (s) goto err; |
| |
| if (BC_NUM_ONE(&temp)) { |
| s = zbc_num_mul(d, &base, &temp, 0); |
| if (s) goto err; |
| s = zbc_num_rem(&temp, c, d, 0); |
| if (s) goto err; |
| } |
| |
| s = zbc_num_mul(&base, &base, &temp, 0); |
| if (s) goto err; |
| s = zbc_num_rem(&temp, c, &base, 0); |
| if (s) goto err; |
| } |
| err: |
| bc_num_free(&temp); |
| bc_num_free(&exp); |
| bc_num_free(&base); |
| RETURN_STATUS(s); |
| } |
| #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 XC_RESULT_TEMP: |
| case XC_RESULT_IBASE: |
| case XC_RESULT_SCALE: |
| case XC_RESULT_OBASE: |
| bc_num_init(&d->d.n, src->d.n.len); |
| bc_num_copy(&d->d.n, &src->d.n); |
| break; |
| case XC_RESULT_VAR: |
| case XC_RESULT_ARRAY: |
| case XC_RESULT_ARRAY_ELEM: |
| d->d.id.name = xstrdup(src->d.id.name); |
| break; |
| case XC_RESULT_CONSTANT: |
| case XC_RESULT_STR: |
| memcpy(&d->d.n, &src->d.n, sizeof(BcNum)); |
| break; |
| default: // placate compiler |
| // BC_RESULT_VOID, BC_RESULT_LAST, BC_RESULT_ONE - do not happen |
| break; |
| } |
| } |
| #endif // ENABLE_DC |
| |
| static FAST_FUNC void bc_result_free(void *result) |
| { |
| BcResult *r = (BcResult *) result; |
| |
| switch (r->t) { |
| case XC_RESULT_TEMP: |
| IF_BC(case BC_RESULT_VOID:) |
| case XC_RESULT_IBASE: |
| case XC_RESULT_SCALE: |
| case XC_RESULT_OBASE: |
| bc_num_free(&r->d.n); |
| break; |
| case XC_RESULT_VAR: |
| case XC_RESULT_ARRAY: |
| case XC_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; |
| } |
| |
| static void xc_read_line(BcVec *vec, FILE *fp) |
| { |
| again: |
| bc_vec_pop_all(vec); |
| fflush_and_check(); |
| |
| #if ENABLE_FEATURE_BC_INTERACTIVE |
| if (G_interrupt) { // ^C was pressed |
| # if ENABLE_FEATURE_EDITING |
| intr: |
| # endif |
| 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 == '\0') break; |
| if (bad_input_byte(c)) goto again; |
| } |
| bc_vec_string(vec, n, line_buf); |
| # undef line_buf |
| } else |
| # endif |
| #endif |
| { |
| int c; |
| bool bad_chars = 0; |
| |
| do { |
| get_char: |
| #if ENABLE_FEATURE_BC_INTERACTIVE |
| if (G_interrupt) { |
| // ^C was pressed: ignore entire line, get another one |
| goto again; |
| } |
| #endif |
| c = fgetc(fp); |
| if (c == '\0') |
| goto get_char; |
| if (c == EOF) { |
| if (ferror(fp)) |
| bb_simple_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.prs.lex_filename) { // stdin |
| // ignore entire line, get another one |
| goto again; |
| } |
| bb_perror_msg_and_die("file '%s' is not text", G.prs.lex_filename); |
| } |
| bc_vec_pushZeroByte(vec); |
| } |
| } |
| |
| // |
| // Parsing routines |
| // |
| |
| // "Input numbers may contain the characters 0-9 and A-Z. |
| // (Note: They must be capitals. Lower case letters are variable names.) |
| // Single digit numbers always have the value of the digit regardless of |
| // the value of ibase. (i.e. A = 10.) For multi-digit numbers, bc changes |
| // all input digits greater or equal to ibase to the value of ibase-1. |
| // This makes the number ZZZ always be the largest 3 digit number of the |
| // input base." |
| static bool xc_num_strValid(const char *val) |
| { |
| bool radix = false; |
| for (;;) { |
| BcDig c = *val++; |
| if (c == '\0') |
| break; |
| if (c == '.') { |
| if (radix) return false; |
| radix = true; |
| continue; |
| } |
| if ((c < '0' || c > '9') && (c < 'A' || c > 'Z')) |
| return false; |
| } |
| 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; |
| |
| len = strlen(val); |
| if (len == 0) |
| return; |
| |
| bc_num_expand(n, len + 1); // +1 for e.g. "A" converting into 10 |
| |
| ptr = strchr(val, '.'); |
| |
| n->rdx = 0; |
| if (ptr != NULL) |
| n->rdx = (size_t)((val + len) - (ptr + 1)); |
| |
| for (i = 0; val[i]; ++i) { |
| if (val[i] != '0' && val[i] != '.') { |
| // Not entirely zero value - convert it, and exit |
| if (len == 1) { |
| unsigned c = val[0] - '0'; |
| n->len = 1; |
| if (c > 9) { // A-Z => 10-36 |
| n->len = 2; |
| c -= ('A' - '9' - 1); |
| n->num[1] = c/10; |
| c = c%10; |
| } |
| n->num[0] = c; |
| break; |
| } |
| i = len - 1; |
| for (;;) { |
| char c = val[i] - '0'; |
| if (c > 9) // A-Z => 9 |
| c = 9; |
| n->num[n->len] = c; |
| 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 |
| } |
| |
| // 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 mult, result; |
| BcNum temp; |
| BcNum base; |
| BcDig temp_digs[ULONG_NUM_BUFSIZE]; |
| BcDig base_digs[ULONG_NUM_BUFSIZE]; |
| size_t digits; |
| |
| bc_num_init_DEF_SIZE(&mult); |
| |
| temp.cap = ARRAY_SIZE(temp_digs); |
| temp.num = temp_digs; |
| |
| base.cap = ARRAY_SIZE(base_digs); |
| base.num = base_digs; |
| bc_num_ulong2num(&base, base_t); |
| base_t--; |
| |
| for (;;) { |
| unsigned v; |
| char c; |
| |
| c = *val++; |
| if (c == '\0') goto int_err; |
| if (c == '.') break; |
| |
| v = (unsigned)(c <= '9' ? c - '0' : c - 'A' + 10); |
| if (v > base_t) v = base_t; |
| |
| 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 (;;) { |
| unsigned v; |
| char c; |
| |
| c = *val++; |
| if (c == '\0') break; |
| digits++; |
| |
| v = (unsigned)(c <= '9' ? c - '0' : c - 'A' + 10); |
| if (v > base_t) v = base_t; |
| |
| 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); |
| } |
| |
| static BC_STATUS zxc_num_parse(BcNum *n, const char *val, unsigned base_t) |
| { |
| size_t i; |
| |
| if (!xc_num_strValid(val)) |
| RETURN_STATUS(bc_error("bad number string")); |
| |
| bc_num_zero(n); |
| while (*val == '0') |
| val++; |
| for (i = 0; ; ++i) { |
| if (val[i] == '\0') |
| RETURN_STATUS(BC_STATUS_SUCCESS); |
| if (val[i] != '.' && val[i] != '0') |
| break; |
| } |
| |
| if (base_t == 10 || val[1] == '\0') |
| // Decimal, or single-digit number |
| bc_num_parseDecimal(n, val); |
| else |
| bc_num_parseBase(n, val, base_t); |
| |
| RETURN_STATUS(BC_STATUS_SUCCESS); |
| } |
| #define zxc_num_parse(...) (zxc_num_parse(__VA_ARGS__) COMMA_SUCCESS) |
| |
| // p->lex_inbuf points to the current string to be parsed. |
| // if p->lex_inbuf points to '\0', it's either EOF or it points after |
| // last processed line's terminating '\n' (and more reading needs to be done |
| // to get next character). |
| // |
| // If you are in a situation where that is a possibility, call peek_inbuf(). |
| // If necessary, it performs more reading and changes p->lex_inbuf, |
| // then it returns *p->lex_inbuf (which will be '\0' only if it's EOF). |
| // After it, just referencing *p->lex_inbuf is valid, and if it wasn't '\0', |
| // it's ok to do p->lex_inbuf++ once without end-of-buffer checking. |
| // |
| // eat_inbuf() is equvalent to "peek_inbuf(); if (c) p->lex_inbuf++": |
| // it returns current char and advances the pointer (if not EOF). |
| // After eat_inbuf(), referencing p->lex_inbuf[-1] and *p->lex_inbuf is valid. |
| // |
| // In many cases, you can use fast *p->lex_inbuf instead of peek_inbuf(): |
| // unless prev char might have been '\n', *p->lex_inbuf is '\0' ONLY |
| // on real EOF, not end-of-buffer. |
| // |
| // bc cases to test interactively: |
| // 1 #comment\ - prints "1<newline>" at once (comment is not continued) |
| // 1 #comment/* - prints "1<newline>" at once |
| // 1 #comment" - prints "1<newline>" at once |
| // 1\#comment - error at once (\ is not a line continuation) |
| // 1 + /*"*/2 - prints "3<newline>" at once |
| // 1 + /*#*/2 - prints "3<newline>" at once |
| // "str\" - prints "str\" at once |
| // "str#" - prints "str#" at once |
| // "str/*" - prints "str/*" at once |
| // "str#\ - waits for second line |
| // end" - ...prints "str#\<newline>end" |
| static char peek_inbuf(void) |
| { |
| if (*G.prs.lex_inbuf == '\0' |
| && G.prs.lex_input_fp |
| ) { |
| xc_read_line(&G.input_buffer, G.prs.lex_input_fp); |
| G.prs.lex_inbuf = G.input_buffer.v; |
| if (G.input_buffer.len <= 1) // on EOF, len is 1 (NUL byte) |
| G.prs.lex_input_fp = NULL; |
| } |
| return *G.prs.lex_inbuf; |
| } |
| static char eat_inbuf(void) |
| { |
| char c = peek_inbuf(); |
| if (c) G.prs.lex_inbuf++; |
| return c; |
| } |
| |
| static void xc_lex_lineComment(void) |
| { |
| BcParse *p = &G.prs; |
| char c; |
| |
| // Try: echo -n '#foo' | bc |
| p->lex = XC_LEX_WHITESPACE; |
| |
| // Not peek_inbuf(): we depend on input being done in whole lines: |
| // '\0' which isn't the EOF can only be seen after '\n'. |
| while ((c = *p->lex_inbuf) != '\n' && c != '\0') |
| p->lex_inbuf++; |
| } |
| |
| static void xc_lex_whitespace(void) |
| { |
| BcParse *p = &G.prs; |
| |
| p->lex = XC_LEX_WHITESPACE; |
| for (;;) { |
| // We depend here on input being done in whole lines: |
| // '\0' which isn't the EOF can only be seen after '\n'. |
| char c = *p->lex_inbuf; |
| if (c == '\n') // this is XC_LEX_NLINE, not XC_LEX_WHITESPACE |
| break; |
| if (!isspace(c)) |
| break; |
| p->lex_inbuf++; |
| } |
| } |
| |
| static BC_STATUS zxc_lex_number(char last) |
| { |
| BcParse *p = &G.prs; |
| bool pt; |
| char last_valid_ch; |
| |
| bc_vec_pop_all(&p->lex_strnumbuf); |
| bc_vec_pushByte(&p->lex_strnumbuf, last); |
| |
| // bc: "Input numbers may contain the characters 0-9 and A-Z. |
| // (Note: They must be capitals. Lower case letters are variable names.) |
| // Single digit numbers always have the value of the digit regardless of |
| // the value of ibase. (i.e. A = 10.) For multi-digit numbers, bc changes |
| // all input digits greater or equal to ibase to the value of ibase-1. |
| // This makes the number ZZZ always be the largest 3 digit number of the |
| // input base." |
| // dc only allows A-F, the rules about single-char and multi-char are the same. |
| last_valid_ch = (IS_BC ? 'Z' : 'F'); |
| pt = (last == '.'); |
| p->lex = XC_LEX_NUMBER; |
| for (;;) { |
| // We depend here on input being done in whole lines: |
| // '\0' which isn't the EOF can only be seen after '\n'. |
| char c = *p->lex_inbuf; |
| check_c: |
| if (c == '\0') |
| break; |
| if (c == '\\' && p->lex_inbuf[1] == '\n') { |
| p->lex_inbuf += 2; |
| p->lex_line++; |
| dbg_lex("++p->lex_line=%zd", p->lex_line); |
| c = peek_inbuf(); // force next line to be read |
| goto check_c; |
| } |
| if (!isdigit(c) && (c < 'A' || c > last_valid_ch)) { |
| if (c != '.') break; |
| // if '.' was already seen, stop on second one: |
| if (pt) break; |
| pt = true; |
| } |
| // c is one of "0-9A-Z." |
| last = c; |
| bc_vec_push(&p->lex_strnumbuf, p->lex_inbuf); |
| p->lex_inbuf++; |
| } |
| if (last == '.') // remove trailing '.' if any |
| bc_vec_pop(&p->lex_strnumbuf); |
| bc_vec_pushZeroByte(&p->lex_strnumbuf); |
| |
| G.err_line = G.prs.lex_line; |
| RETURN_STATUS(BC_STATUS_SUCCESS); |
| } |
| #define zxc_lex_number(...) (zxc_lex_number(__VA_ARGS__) COMMA_SUCCESS) |
| |
| static void xc_lex_name(void) |
| { |
| BcParse *p = &G.prs; |
| size_t i; |
| const char *buf; |
| |
| p->lex = XC_LEX_NAME; |
| |
| // Since names can't cross lines with \<newline>, |
| // we depend on the fact that whole line is in the buffer |
| i = 0; |
| buf = p->lex_inbuf - 1; |
| for (;;) { |
| char c = buf[i]; |
| if ((c < 'a' || c > 'z') && !isdigit(c) && c != '_') break; |
| i++; |
| } |
| |
| #if 0 // We do not protect against people with gigabyte-long names |
| // This check makes sense only if size_t is (much) larger than BC_MAX_STRING. |
| if (SIZE_MAX > (BC_MAX_STRING | 0xff)) { |
| if (i > BC_MAX_STRING) |
| return bc_error("name too long: must be [1,"BC_MAX_STRING_STR"]"); |
| } |
| #endif |
| bc_vec_string(&p->lex_strnumbuf, i, buf); |
| |
| // Increment the index. We minus 1 because it has already been incremented. |
| p->lex_inbuf += i - 1; |
| |
| //return BC_STATUS_SUCCESS; |
| } |
| |
| IF_BC(static BC_STATUS zbc_lex_token(void);) |
| IF_DC(static BC_STATUS zdc_lex_token(void);) |
| #define zbc_lex_token(...) (zbc_lex_token(__VA_ARGS__) COMMA_SUCCESS) |
| #define zdc_lex_token(...) (zdc_lex_token(__VA_ARGS__) COMMA_SUCCESS) |
| |
| static BC_STATUS zxc_lex_next(void) |
| { |
| BcParse *p = &G.prs; |
| BcStatus s; |
| |
| G.err_line = p->lex_line; |
|