busybox/miscutils/bc.c
<<
>>
Prefs
   1/* vi: set sw=4 ts=4: */
   2/*
   3 * Licensed under GPLv2 or later, see file LICENSE in this source tree.
   4 * Adapted from https://github.com/gavinhoward/bc
   5 * Original code copyright (c) 2018 Gavin D. Howard and contributors.
   6 */
   7//TODO:
   8// maybe implement a^b for non-integer b? (see zbc_num_p())
   9
  10#define DEBUG_LEXER   0
  11#define DEBUG_COMPILE 0
  12#define DEBUG_EXEC    0
  13// This can be left enabled for production as well:
  14#define SANITY_CHECKS 1
  15
  16//config:config BC
  17//config:       bool "bc (45 kb)"
  18//config:       default y
  19//config:       select FEATURE_DC_BIG
  20//config:       help
  21//config:       bc is a command-line, arbitrary-precision calculator with a
  22//config:       Turing-complete language. See the GNU bc manual
  23//config:       (https://www.gnu.org/software/bc/manual/bc.html) and bc spec
  24//config:       (http://pubs.opengroup.org/onlinepubs/9699919799/utilities/bc.html).
  25//config:
  26//config:       This bc has five differences to the GNU bc:
  27//config:         1) The period (.) is a shortcut for "last", as in the BSD bc.
  28//config:         2) Arrays are copied before being passed as arguments to
  29//config:            functions. This behavior is required by the bc spec.
  30//config:         3) Arrays can be passed to the builtin "length" function to get
  31//config:            the number of elements in the array. This prints "1":
  32//config:               a[0] = 0; length(a[])
  33//config:         4) The precedence of the boolean "not" operator (!) is equal to
  34//config:            that of the unary minus (-) negation operator. This still
  35//config:            allows POSIX-compliant scripts to work while somewhat
  36//config:            preserving expected behavior (versus C) and making parsing
  37//config:            easier.
  38//config:         5) "read()" accepts expressions, not only numeric literals.
  39//config:
  40//config:config DC
  41//config:       bool "dc (36 kb)"
  42//config:       default y
  43//config:       help
  44//config:       dc is a reverse-polish notation command-line calculator which
  45//config:       supports unlimited precision arithmetic. See the FreeBSD man page
  46//config:       (https://www.unix.com/man-page/FreeBSD/1/dc/) and GNU dc manual
  47//config:       (https://www.gnu.org/software/bc/manual/dc-1.05/html_mono/dc.html).
  48//config:
  49//config:       This dc has a few differences from the two above:
  50//config:         1) When printing a byte stream (command "P"), this dc follows what
  51//config:            the FreeBSD dc does.
  52//config:         2) Implements the GNU extensions for divmod ("~") and
  53//config:            modular exponentiation ("|").
  54//config:         3) Implements all FreeBSD extensions, except for "J" and "M".
  55//config:         4) Like the FreeBSD dc, this dc supports extended registers.
  56//config:            However, they are implemented differently. When it encounters
  57//config:            whitespace where a register should be, it skips the whitespace.
  58//config:            If the character following is not a lowercase letter, an error
  59//config:            is issued. Otherwise, the register name is parsed by the
  60//config:            following regex: [a-z][a-z0-9_]*
  61//config:            This generally means that register names will be surrounded by
  62//config:            whitespace. Examples:
  63//config:               l idx s temp L index S temp2 < do_thing
  64//config:            Also note that, like the FreeBSD dc, extended registers are not
  65//config:            allowed unless the "-x" option is given.
  66//config:
  67//config:if BC || DC  # for menuconfig indenting
  68//config:
  69//config:config FEATURE_DC_BIG
  70//config:       bool "Use bc code base for dc (larger, more features)"
  71//config:       default y
  72//config:
  73//config:config FEATURE_DC_LIBM
  74//config:       bool "Enable power and exp functions (requires libm)"
  75//config:       default y
  76//config:       depends on DC && !BC && !FEATURE_DC_BIG
  77//config:       help
  78//config:       Enable power and exp functions.
  79//config:       NOTE: This will require libm to be present for linking.
  80//config:
  81//config:config FEATURE_BC_INTERACTIVE
  82//config:       bool "Interactive mode (+4kb)"
  83//config:       default y
  84//config:       depends on BC || (DC && FEATURE_DC_BIG)
  85//config:       help
  86//config:       Enable interactive mode: when started on a tty,
  87//config:       ^C interrupts execution and returns to command line,
  88//config:       errors also return to command line instead of exiting,
  89//config:       line editing with history is available.
  90//config:
  91//config:       With this option off, input can still be taken from tty,
  92//config:       but all errors are fatal, ^C is fatal,
  93//config:       tty is treated exactly the same as any other
  94//config:       standard input (IOW: no line editing).
  95//config:
  96//config:config FEATURE_BC_LONG_OPTIONS
  97//config:       bool "Enable bc/dc long options"
  98//config:       default y
  99//config:       depends on BC || (DC && FEATURE_DC_BIG)
 100//config:
 101//config:endif
 102
 103//applet:IF_BC(APPLET(bc, BB_DIR_USR_BIN, BB_SUID_DROP))
 104//applet:IF_DC(APPLET(dc, BB_DIR_USR_BIN, BB_SUID_DROP))
 105
 106//kbuild:lib-$(CONFIG_BC) += bc.o
 107//kbuild:lib-$(CONFIG_DC) += bc.o
 108
 109//See www.gnu.org/software/bc/manual/bc.html
 110//usage:#define bc_trivial_usage
 111//usage:       "[-sqlw] [FILE]..."
 112//usage:
 113//usage:#define bc_full_usage "\n"
 114//usage:     "\nArbitrary precision calculator"
 115//usage:     "\n"
 116///////:     "\n        -i      Interactive" - has no effect for now
 117//usage:     "\n        -q      Quiet"
 118//usage:     "\n        -l      Load standard library"
 119//usage:     "\n        -s      Be POSIX compatible"
 120//usage:     "\n        -w      Warn if extensions are used"
 121///////:     "\n        -v      Version"
 122//usage:     "\n"
 123//usage:     "\n$BC_LINE_LENGTH changes output width"
 124//usage:
 125//usage:#define bc_example_usage
 126//usage:       "3 + 4.129\n"
 127//usage:       "1903 - 2893\n"
 128//usage:       "-129 * 213.28935\n"
 129//usage:       "12 / -1932\n"
 130//usage:       "12 % 12\n"
 131//usage:       "34 ^ 189\n"
 132//usage:       "scale = 13\n"
 133//usage:       "ibase = 2\n"
 134//usage:       "obase = A\n"
 135//usage:
 136//usage:#define dc_trivial_usage
 137//usage:       IF_FEATURE_DC_BIG("[-x] ")"[-eSCRIPT]... [-fFILE]... [FILE]..."
 138//usage:
 139//usage:#define dc_full_usage "\n"
 140//usage:     "\nTiny RPN calculator. Operations:"
 141//usage:     "\nArithmetic: + - * / % ^"
 142//usage:        IF_FEATURE_DC_BIG(
 143//usage:     "\n~ - divide with remainder"
 144//usage:     "\n| - modular exponentiation"
 145//usage:     "\nv - square root"
 146////////     "\nA-F -                   digits 10..15
 147////////     "\n_NNN -                  push negative number -NNN
 148////////     "\n[string] -              push string (in FreeBSD, \[, \] and \\ are escapes, not implemented here and in GNU)
 149////////     "\nR - DC_LEX_POP          pop and discard
 150////////     "\nc - DC_LEX_CLEAR_STACK  clear stack
 151////////     "\nd - DC_LEX_DUPLICATE    duplicate top-of-stack
 152////////     "\nr - DC_LEX_SWAP         swap top-of-stack
 153////////     "\n:r - DC_LEX_COLON       pop index, pop value, store to array 'r'
 154////////     "\n;r - DC_LEX_SCOLON      pop index, fetch from array 'r', push
 155////////     "\nLr - DC_LEX_LOAD_POP    pop register 'r', push
 156////////     "\nSr - DC_LEX_STORE_PUSH  pop, push to register 'r'
 157////////     "\nlr - DC_LEX_LOAD        read register 'r', push
 158////////     "\nsr - DC_LEX_OP_ASSIGN   pop, assign to register 'r'
 159////////     "\n? - DC_LEX_READ         read line and execute
 160////////     "\nx - DC_LEX_EXECUTE      pop string and execute
 161////////     "\n<r - XC_LEX_OP_REL_GT   pop, pop, execute register 'r' if top-of-stack was less
 162////////     "\n>r - XC_LEX_OP_REL_LT   pop, pop, execute register 'r' if top-of-stack was greater
 163////////     "\n=r - XC_LEX_OP_REL_EQ   pop, pop, execute register 'r' if equal
 164////////     "\n                        !<r !>r !=r - negated forms
 165////////     "\n                        >tef - "if greater execute register 't' else execute 'f'"
 166////////     "\nQ - DC_LEX_NQUIT        pop, "break N" from macro invocations
 167////////     "\nq - DC_LEX_QUIT         "break 2" (if less than 2 levels of macros, exit dc)
 168////////     "\nX - DC_LEX_SCALE_FACTOR pop, push number of fractional digits
 169////////     "\nZ - DC_LEX_LENGTH       pop, push number of digits it has (or number of characters in string)
 170////////     "\na - DC_LEX_ASCIIFY      pop, push low-order byte as char or 1st char of string
 171////////     "\n( - DC_LEX_LPAREN       (FreeBSD, not in GNU) pop, pop, if top-of-stack was less push 1 else push 0
 172////////     "\n{ - DC_LEX_LBRACE       (FreeBSD, not in GNU) pop, pop, if top-of-stack was less-or-equal push 1 else push 0
 173////////     "\nG - DC_LEX_EQ_NO_REG    (FreeBSD, not in GNU) pop, pop, if equal push 1 else push 0
 174////////     "\nN - DC_LEX_OP_BOOL_NOT  (FreeBSD, not in GNU) pop, if 0 push 1 else push 0
 175////////                                FreeBSD also has J and M commands, used internally by bc
 176////////     "\nn - DC_LEX_PRINT_POP    pop, print without newline
 177////////     "\nP - DC_LEX_PRINT_STREAM pop, print string or hex bytes
 178//usage:        )
 179//usage:     "\np - print top of the stack without popping"
 180//usage:     "\nf - print entire stack"
 181////////     "\nz - DC_LEX_STACK_LEVEL  push stack depth
 182////////     "\nK - DC_LEX_SCALE        push precision
 183////////     "\nI - DC_LEX_IBASE        push input radix
 184////////     "\nO - DC_LEX_OBASE        push output radix
 185//usage:        IF_FEATURE_DC_BIG(
 186//usage:     "\nk - pop the value and set precision"
 187//usage:     "\ni - pop the value and set input radix"
 188//usage:        )
 189//usage:     "\no - pop the value and set output radix"
 190//usage:     "\nExamples: dc -e'2 2 + p' -> 4, dc -e'8 8 * 2 2 + / p' -> 16"
 191//usage:
 192//usage:#define dc_example_usage
 193//usage:       "$ dc -e'2 2 + p'\n"
 194//usage:       "4\n"
 195//usage:       "$ dc -e'8 8 \\* 2 2 + / p'\n"
 196//usage:       "16\n"
 197//usage:       "$ dc -e'0 1 & p'\n"
 198//usage:       "0\n"
 199//usage:       "$ dc -e'0 1 | p'\n"
 200//usage:       "1\n"
 201//usage:       "$ echo '72 9 / 8 * p' | dc\n"
 202//usage:       "64\n"
 203
 204#include "libbb.h"
 205#include "common_bufsiz.h"
 206
 207#if !ENABLE_BC && !ENABLE_FEATURE_DC_BIG
 208# include "dc.c"
 209#else
 210
 211#if DEBUG_LEXER
 212static uint8_t lex_indent;
 213#define dbg_lex(...) \
 214        do { \
 215                fprintf(stderr, "%*s", lex_indent, ""); \
 216                bb_error_msg(__VA_ARGS__); \
 217        } while (0)
 218#define dbg_lex_enter(...) \
 219        do { \
 220                dbg_lex(__VA_ARGS__); \
 221                lex_indent++; \
 222        } while (0)
 223#define dbg_lex_done(...) \
 224        do { \
 225                lex_indent--; \
 226                dbg_lex(__VA_ARGS__); \
 227        } while (0)
 228#else
 229# define dbg_lex(...)       ((void)0)
 230# define dbg_lex_enter(...) ((void)0)
 231# define dbg_lex_done(...)  ((void)0)
 232#endif
 233
 234#if DEBUG_COMPILE
 235# define dbg_compile(...) bb_error_msg(__VA_ARGS__)
 236#else
 237# define dbg_compile(...) ((void)0)
 238#endif
 239
 240#if DEBUG_EXEC
 241# define dbg_exec(...) bb_error_msg(__VA_ARGS__)
 242#else
 243# define dbg_exec(...) ((void)0)
 244#endif
 245
 246typedef enum BcStatus {
 247        BC_STATUS_SUCCESS = 0,
 248        BC_STATUS_FAILURE = 1,
 249} BcStatus;
 250
 251#define BC_VEC_INVALID_IDX  ((size_t) -1)
 252#define BC_VEC_START_CAP    (1 << 5)
 253
 254typedef void (*BcVecFree)(void *) FAST_FUNC;
 255
 256typedef struct BcVec {
 257        char *v;
 258        size_t len;
 259        size_t cap;
 260        size_t size;
 261        BcVecFree dtor;
 262} BcVec;
 263
 264typedef signed char BcDig;
 265
 266typedef struct BcNum {
 267        BcDig *restrict num;
 268        size_t rdx;
 269        size_t len;
 270        size_t cap;
 271        bool neg;
 272} BcNum;
 273
 274#define BC_NUM_MAX_IBASE        36
 275// larger value might speed up BIGNUM calculations a bit:
 276#define BC_NUM_DEF_SIZE         16
 277#define BC_NUM_PRINT_WIDTH      70
 278
 279#define BC_NUM_KARATSUBA_LEN    32
 280
 281typedef enum BcInst {
 282#if ENABLE_BC
 283        BC_INST_INC_PRE,
 284        BC_INST_DEC_PRE,
 285        BC_INST_INC_POST,
 286        BC_INST_DEC_POST,
 287#endif
 288        XC_INST_NEG,            // order
 289
 290        XC_INST_REL_EQ,         // should
 291        XC_INST_REL_LE,         // match
 292        XC_INST_REL_GE,         // LEX
 293        XC_INST_REL_NE,         // constants
 294        XC_INST_REL_LT,         // for
 295        XC_INST_REL_GT,         // these
 296
 297        XC_INST_POWER,          // operations
 298        XC_INST_MULTIPLY,       // |
 299        XC_INST_DIVIDE,         // |
 300        XC_INST_MODULUS,        // |
 301        XC_INST_PLUS,           // |
 302        XC_INST_MINUS,          // |
 303
 304        XC_INST_BOOL_NOT,       // |
 305        XC_INST_BOOL_OR,        // |
 306        XC_INST_BOOL_AND,       // |
 307#if ENABLE_BC
 308        BC_INST_ASSIGN_POWER,   // |
 309        BC_INST_ASSIGN_MULTIPLY,// |
 310        BC_INST_ASSIGN_DIVIDE,  // |
 311        BC_INST_ASSIGN_MODULUS, // |
 312        BC_INST_ASSIGN_PLUS,    // |
 313        BC_INST_ASSIGN_MINUS,   // |
 314#endif
 315        XC_INST_ASSIGN,         // V
 316
 317        XC_INST_NUM,
 318        XC_INST_VAR,
 319        XC_INST_ARRAY_ELEM,
 320        XC_INST_ARRAY,
 321        XC_INST_SCALE_FUNC,
 322
 323        XC_INST_IBASE,       // order of these constans should match other enums
 324        XC_INST_OBASE,       // order of these constans should match other enums
 325        XC_INST_SCALE,       // order of these constans should match other enums
 326        IF_BC(BC_INST_LAST,) // order of these constans should match other enums
 327        XC_INST_LENGTH,
 328        XC_INST_READ,
 329        XC_INST_SQRT,
 330
 331        XC_INST_PRINT,
 332        XC_INST_PRINT_POP,
 333        XC_INST_STR,
 334        XC_INST_PRINT_STR,
 335
 336#if ENABLE_BC
 337        BC_INST_HALT,
 338        BC_INST_JUMP,
 339        BC_INST_JUMP_ZERO,
 340
 341        BC_INST_CALL,
 342        BC_INST_RET0,
 343#endif
 344        XC_INST_RET,
 345
 346        XC_INST_POP,
 347#if ENABLE_DC
 348        DC_INST_POP_EXEC,
 349
 350        DC_INST_MODEXP,
 351        DC_INST_DIVMOD,
 352
 353        DC_INST_EXECUTE,
 354        DC_INST_EXEC_COND,
 355
 356        DC_INST_ASCIIFY,
 357        DC_INST_PRINT_STREAM,
 358
 359        DC_INST_PRINT_STACK,
 360        DC_INST_CLEAR_STACK,
 361        DC_INST_STACK_LEN,
 362        DC_INST_DUPLICATE,
 363        DC_INST_SWAP,
 364
 365        DC_INST_LOAD,
 366        DC_INST_PUSH_VAR,
 367        DC_INST_PUSH_TO_VAR,
 368
 369        DC_INST_QUIT,
 370        DC_INST_NQUIT,
 371
 372        DC_INST_INVALID = -1,
 373#endif
 374} BcInst;
 375
 376typedef struct BcId {
 377        char *name;
 378        size_t idx;
 379} BcId;
 380
 381typedef struct BcFunc {
 382        BcVec code;
 383        IF_BC(BcVec labels;)
 384        IF_BC(BcVec autos;)
 385        IF_BC(BcVec strs;)
 386        IF_BC(BcVec consts;)
 387        IF_BC(size_t nparams;)
 388        IF_BC(bool voidfunc;)
 389} BcFunc;
 390
 391typedef enum BcResultType {
 392        XC_RESULT_TEMP,
 393        IF_BC(BC_RESULT_VOID,) // same as TEMP, but INST_PRINT will ignore it
 394
 395        XC_RESULT_VAR,
 396        XC_RESULT_ARRAY_ELEM,
 397        XC_RESULT_ARRAY,
 398
 399        XC_RESULT_STR,
 400
 401        //code uses "inst - XC_INST_IBASE + XC_RESULT_IBASE" construct,
 402        XC_RESULT_IBASE,       // relative order should match for: XC_INST_IBASE
 403        XC_RESULT_OBASE,       // relative order should match for: XC_INST_OBASE
 404        XC_RESULT_SCALE,       // relative order should match for: XC_INST_SCALE
 405        IF_BC(BC_RESULT_LAST,) // relative order should match for: BC_INST_LAST
 406        XC_RESULT_CONSTANT,
 407        IF_BC(BC_RESULT_ONE,)
 408} BcResultType;
 409
 410typedef union BcResultData {
 411        BcNum n;
 412        BcVec v;
 413        BcId id;
 414} BcResultData;
 415
 416typedef struct BcResult {
 417        BcResultType t;
 418        BcResultData d;
 419} BcResult;
 420
 421typedef struct BcInstPtr {
 422        size_t func;
 423        size_t inst_idx;
 424} BcInstPtr;
 425
 426typedef enum BcType {
 427        BC_TYPE_VAR,
 428        BC_TYPE_ARRAY,
 429        BC_TYPE_REF,
 430} BcType;
 431
 432typedef enum BcLexType {
 433        XC_LEX_EOF,
 434        XC_LEX_INVALID,
 435
 436        XC_LEX_NLINE,
 437        XC_LEX_WHITESPACE,
 438        XC_LEX_STR,
 439        XC_LEX_NAME,
 440        XC_LEX_NUMBER,
 441
 442        XC_LEX_1st_op,
 443        XC_LEX_NEG = XC_LEX_1st_op,     // order
 444
 445        XC_LEX_OP_REL_EQ,               // should
 446        XC_LEX_OP_REL_LE,               // match
 447        XC_LEX_OP_REL_GE,               // INST
 448        XC_LEX_OP_REL_NE,               // constants
 449        XC_LEX_OP_REL_LT,               // for
 450        XC_LEX_OP_REL_GT,               // these
 451
 452        XC_LEX_OP_POWER,                // operations
 453        XC_LEX_OP_MULTIPLY,             // |
 454        XC_LEX_OP_DIVIDE,               // |
 455        XC_LEX_OP_MODULUS,              // |
 456        XC_LEX_OP_PLUS,                 // |
 457        XC_LEX_OP_MINUS,                // |
 458        XC_LEX_OP_last = XC_LEX_OP_MINUS,
 459#if ENABLE_BC
 460        BC_LEX_OP_BOOL_NOT,             // |
 461        BC_LEX_OP_BOOL_OR,              // |
 462        BC_LEX_OP_BOOL_AND,             // |
 463
 464        BC_LEX_OP_ASSIGN_POWER,         // |
 465        BC_LEX_OP_ASSIGN_MULTIPLY,      // |
 466        BC_LEX_OP_ASSIGN_DIVIDE,        // |
 467        BC_LEX_OP_ASSIGN_MODULUS,       // |
 468        BC_LEX_OP_ASSIGN_PLUS,          // |
 469        BC_LEX_OP_ASSIGN_MINUS,         // |
 470
 471        BC_LEX_OP_ASSIGN,               // V
 472
 473        BC_LEX_OP_INC,
 474        BC_LEX_OP_DEC,
 475
 476        BC_LEX_LPAREN, // () are 0x28 and 0x29
 477        BC_LEX_RPAREN, // must be LPAREN+1: code uses (c - '(' + BC_LEX_LPAREN)
 478
 479        BC_LEX_LBRACKET, // [] are 0x5B and 0x5D
 480        BC_LEX_COMMA,
 481        BC_LEX_RBRACKET, // must be LBRACKET+2: code uses (c - '[' + BC_LEX_LBRACKET)
 482
 483        BC_LEX_LBRACE, // {} are 0x7B and 0x7D
 484        BC_LEX_SCOLON,
 485        BC_LEX_RBRACE, // must be LBRACE+2: code uses (c - '{' + BC_LEX_LBRACE)
 486
 487        BC_LEX_KEY_1st_keyword,
 488        BC_LEX_KEY_AUTO = BC_LEX_KEY_1st_keyword,
 489        BC_LEX_KEY_BREAK,
 490        BC_LEX_KEY_CONTINUE,
 491        BC_LEX_KEY_DEFINE,
 492        BC_LEX_KEY_ELSE,
 493        BC_LEX_KEY_FOR,
 494        BC_LEX_KEY_HALT,
 495        // code uses "type - BC_LEX_KEY_IBASE + XC_INST_IBASE" construct,
 496        BC_LEX_KEY_IBASE,    // relative order should match for: XC_INST_IBASE
 497        BC_LEX_KEY_OBASE,    // relative order should match for: XC_INST_OBASE
 498        BC_LEX_KEY_IF,
 499        BC_LEX_KEY_LAST,     // relative order should match for: BC_INST_LAST
 500        BC_LEX_KEY_LENGTH,
 501        BC_LEX_KEY_LIMITS,
 502        BC_LEX_KEY_PRINT,
 503        BC_LEX_KEY_QUIT,
 504        BC_LEX_KEY_READ,
 505        BC_LEX_KEY_RETURN,
 506        BC_LEX_KEY_SCALE,
 507        BC_LEX_KEY_SQRT,
 508        BC_LEX_KEY_WHILE,
 509#endif // ENABLE_BC
 510
 511#if ENABLE_DC
 512        DC_LEX_OP_BOOL_NOT = XC_LEX_OP_last + 1,
 513        DC_LEX_OP_ASSIGN,
 514
 515        DC_LEX_LPAREN,
 516        DC_LEX_SCOLON,
 517        DC_LEX_READ,
 518        DC_LEX_IBASE,
 519        DC_LEX_SCALE,
 520        DC_LEX_OBASE,
 521        DC_LEX_LENGTH,
 522        DC_LEX_PRINT,
 523        DC_LEX_QUIT,
 524        DC_LEX_SQRT,
 525        DC_LEX_LBRACE,
 526
 527        DC_LEX_EQ_NO_REG,
 528        DC_LEX_OP_MODEXP,
 529        DC_LEX_OP_DIVMOD,
 530
 531        DC_LEX_COLON,
 532        DC_LEX_ELSE,
 533        DC_LEX_EXECUTE,
 534        DC_LEX_PRINT_STACK,
 535        DC_LEX_CLEAR_STACK,
 536        DC_LEX_STACK_LEVEL,
 537        DC_LEX_DUPLICATE,
 538        DC_LEX_SWAP,
 539        DC_LEX_POP,
 540
 541        DC_LEX_ASCIIFY,
 542        DC_LEX_PRINT_STREAM,
 543
 544        // code uses "t - DC_LEX_STORE_IBASE + XC_INST_IBASE" construct,
 545        DC_LEX_STORE_IBASE,  // relative order should match for: XC_INST_IBASE
 546        DC_LEX_STORE_OBASE,  // relative order should match for: XC_INST_OBASE
 547        DC_LEX_STORE_SCALE,  // relative order should match for: XC_INST_SCALE
 548        DC_LEX_LOAD,
 549        DC_LEX_LOAD_POP,
 550        DC_LEX_STORE_PUSH,
 551        DC_LEX_PRINT_POP,
 552        DC_LEX_NQUIT,
 553        DC_LEX_SCALE_FACTOR,
 554#endif
 555} BcLexType;
 556// must match order of BC_LEX_KEY_foo etc above
 557#if ENABLE_BC
 558struct BcLexKeyword {
 559        char name8[8];
 560};
 561#define LEX_KW_ENTRY(a, b) \
 562        { .name8 = a /*, .posix = b */ }
 563static const struct BcLexKeyword bc_lex_kws[20] ALIGN8 = {
 564        LEX_KW_ENTRY("auto"    , 1), // 0
 565        LEX_KW_ENTRY("break"   , 1), // 1
 566        LEX_KW_ENTRY("continue", 0), // 2 note: this one has no terminating NUL
 567        LEX_KW_ENTRY("define"  , 1), // 3
 568        LEX_KW_ENTRY("else"    , 0), // 4
 569        LEX_KW_ENTRY("for"     , 1), // 5
 570        LEX_KW_ENTRY("halt"    , 0), // 6
 571        LEX_KW_ENTRY("ibase"   , 1), // 7
 572        LEX_KW_ENTRY("obase"   , 1), // 8
 573        LEX_KW_ENTRY("if"      , 1), // 9
 574        LEX_KW_ENTRY("last"    , 0), // 10
 575        LEX_KW_ENTRY("length"  , 1), // 11
 576        LEX_KW_ENTRY("limits"  , 0), // 12
 577        LEX_KW_ENTRY("print"   , 0), // 13
 578        LEX_KW_ENTRY("quit"    , 1), // 14
 579        LEX_KW_ENTRY("read"    , 0), // 15
 580        LEX_KW_ENTRY("return"  , 1), // 16
 581        LEX_KW_ENTRY("scale"   , 1), // 17
 582        LEX_KW_ENTRY("sqrt"    , 1), // 18
 583        LEX_KW_ENTRY("while"   , 1), // 19
 584};
 585#undef LEX_KW_ENTRY
 586#define STRING_else  (bc_lex_kws[4].name8)
 587#define STRING_for   (bc_lex_kws[5].name8)
 588#define STRING_if    (bc_lex_kws[9].name8)
 589#define STRING_while (bc_lex_kws[19].name8)
 590enum {
 591        POSIX_KWORD_MASK = 0
 592                | (1 << 0)  // 0
 593                | (1 << 1)  // 1
 594                | (0 << 2)  // 2
 595                | (1 << 3)  // 3
 596                | (0 << 4)  // 4
 597                | (1 << 5)  // 5
 598                | (0 << 6)  // 6
 599                | (1 << 7)  // 7
 600                | (1 << 8)  // 8
 601                | (1 << 9)  // 9
 602                | (0 << 10) // 10
 603                | (1 << 11) // 11
 604                | (0 << 12) // 12
 605                | (0 << 13) // 13
 606                | (1 << 14) // 14
 607                | (0 << 15) // 15
 608                | (1 << 16) // 16
 609                | (1 << 17) // 17
 610                | (1 << 18) // 18
 611                | (1 << 19) // 19
 612};
 613#define keyword_is_POSIX(i) ((1 << (i)) & POSIX_KWORD_MASK)
 614
 615// This is a bit array that corresponds to token types. An entry is
 616// true if the token is valid in an expression, false otherwise.
 617// Used to figure out when expr parsing should stop *without error message*
 618// - 0 element indicates this condition. 1 means "this token is to be eaten
 619// as part of the expression", it can then still be determined to be invalid
 620// by later processing.
 621enum {
 622#define EXBITS(a,b,c,d,e,f,g,h) \
 623        ((uint64_t)((a << 0)+(b << 1)+(c << 2)+(d << 3)+(e << 4)+(f << 5)+(g << 6)+(h << 7)))
 624        BC_PARSE_EXPRS_BITS = 0              // corresponding BC_LEX_xyz:
 625        + (EXBITS(0,0,0,0,0,1,1,1) << (0*8)) //  0: EOF    INVAL  NL     WS     STR    NAME   NUM    -
 626        + (EXBITS(1,1,1,1,1,1,1,1) << (1*8)) //  8: ==     <=     >=     !=     <      >      ^      *
 627        + (EXBITS(1,1,1,1,1,1,1,1) << (2*8)) // 16: /      %      +      -      !      ||     &&     ^=
 628        + (EXBITS(1,1,1,1,1,1,1,1) << (3*8)) // 24: *=     /=     %=     +=     -=     =      ++     --
 629        + (EXBITS(1,1,0,0,0,0,0,0) << (4*8)) // 32: (      )      [      ,      ]      {      ;      }
 630        + (EXBITS(0,0,0,0,0,0,0,1) << (5*8)) // 40: auto   break  cont   define else   for    halt   ibase
 631        + (EXBITS(1,0,1,1,0,0,0,1) << (6*8)) // 48: obase  if     last   length limits print  quit   read
 632        + (EXBITS(0,1,1,0,0,0,0,0) << (7*8)) // 56: return scale  sqrt   while
 633#undef EXBITS
 634};
 635static ALWAYS_INLINE long lex_allowed_in_bc_expr(unsigned i)
 636{
 637#if ULONG_MAX > 0xffffffff
 638        // 64-bit version (will not work correctly for 32-bit longs!)
 639        return BC_PARSE_EXPRS_BITS & (1UL << i);
 640#else
 641        // 32-bit version
 642        unsigned long m = (uint32_t)BC_PARSE_EXPRS_BITS;
 643        if (i >= 32) {
 644                m = (uint32_t)(BC_PARSE_EXPRS_BITS >> 32);
 645                i &= 31;
 646        }
 647        return m & (1UL << i);
 648#endif
 649}
 650
 651// This is an array of data for operators that correspond to
 652// [XC_LEX_1st_op...] token types.
 653static const uint8_t bc_ops_prec_and_assoc[] ALIGN1 = {
 654#define OP(p,l) ((int)(l) * 0x10 + (p))
 655        OP(1, false), // neg
 656        OP(6, true ), OP( 6, true  ), OP( 6, true  ), OP( 6, true  ), OP( 6, true  ), OP( 6, true ), // == <= >= != < >
 657        OP(2, false), // pow
 658        OP(3, true ), OP( 3, true  ), OP( 3, true  ), // mul div mod
 659        OP(4, true ), OP( 4, true  ), // + -
 660        OP(1, false), // not
 661        OP(7, true ), OP( 7, true  ), // or and
 662        OP(5, false), OP( 5, false ), OP( 5, false ), OP( 5, false ), OP( 5, false ), // ^= *= /= %= +=
 663        OP(5, false), OP( 5, false ), // -= =
 664        OP(0, false), OP( 0, false ), // inc dec
 665#undef OP
 666};
 667#define bc_operation_PREC(i) (bc_ops_prec_and_assoc[i] & 0x0f)
 668#define bc_operation_LEFT(i) (bc_ops_prec_and_assoc[i] & 0x10)
 669#endif // ENABLE_BC
 670
 671#if ENABLE_DC
 672static const //BcLexType - should be this type
 673uint8_t
 674dc_char_to_LEX[] ALIGN1 = {
 675        // %&'(
 676        XC_LEX_OP_MODULUS, XC_LEX_INVALID, XC_LEX_INVALID, DC_LEX_LPAREN,
 677        // )*+,
 678        XC_LEX_INVALID, XC_LEX_OP_MULTIPLY, XC_LEX_OP_PLUS, XC_LEX_INVALID,
 679        // -./
 680        XC_LEX_OP_MINUS, XC_LEX_INVALID, XC_LEX_OP_DIVIDE,
 681        // 0123456789
 682        XC_LEX_INVALID, XC_LEX_INVALID, XC_LEX_INVALID, XC_LEX_INVALID,
 683        XC_LEX_INVALID, XC_LEX_INVALID, XC_LEX_INVALID, XC_LEX_INVALID,
 684        XC_LEX_INVALID, XC_LEX_INVALID,
 685        // :;<=>?@
 686        DC_LEX_COLON, DC_LEX_SCOLON, XC_LEX_OP_REL_GT, XC_LEX_OP_REL_EQ,
 687        XC_LEX_OP_REL_LT, DC_LEX_READ, XC_LEX_INVALID,
 688        // ABCDEFGH
 689        XC_LEX_INVALID, XC_LEX_INVALID, XC_LEX_INVALID, XC_LEX_INVALID,
 690        XC_LEX_INVALID, XC_LEX_INVALID, DC_LEX_EQ_NO_REG, XC_LEX_INVALID,
 691        // IJKLMNOP
 692        DC_LEX_IBASE, XC_LEX_INVALID, DC_LEX_SCALE, DC_LEX_LOAD_POP,
 693        XC_LEX_INVALID, DC_LEX_OP_BOOL_NOT, DC_LEX_OBASE, DC_LEX_PRINT_STREAM,
 694        // QRSTUVWX
 695        DC_LEX_NQUIT, DC_LEX_POP, DC_LEX_STORE_PUSH, XC_LEX_INVALID,
 696        XC_LEX_INVALID, XC_LEX_INVALID, XC_LEX_INVALID, DC_LEX_SCALE_FACTOR,
 697        // YZ
 698        XC_LEX_INVALID, DC_LEX_LENGTH,
 699        // [\]
 700        XC_LEX_INVALID, XC_LEX_INVALID, XC_LEX_INVALID,
 701        // ^_`
 702        XC_LEX_OP_POWER, XC_LEX_NEG, XC_LEX_INVALID,
 703        // abcdefgh
 704        DC_LEX_ASCIIFY, XC_LEX_INVALID, DC_LEX_CLEAR_STACK, DC_LEX_DUPLICATE,
 705        DC_LEX_ELSE, DC_LEX_PRINT_STACK, XC_LEX_INVALID, XC_LEX_INVALID,
 706        // ijklmnop
 707        DC_LEX_STORE_IBASE, XC_LEX_INVALID, DC_LEX_STORE_SCALE, DC_LEX_LOAD,
 708        XC_LEX_INVALID, DC_LEX_PRINT_POP, DC_LEX_STORE_OBASE, DC_LEX_PRINT,
 709        // qrstuvwx
 710        DC_LEX_QUIT, DC_LEX_SWAP, DC_LEX_OP_ASSIGN, XC_LEX_INVALID,
 711        XC_LEX_INVALID, DC_LEX_SQRT, XC_LEX_INVALID, DC_LEX_EXECUTE,
 712        // yz
 713        XC_LEX_INVALID, DC_LEX_STACK_LEVEL,
 714        // {|}~
 715        DC_LEX_LBRACE, DC_LEX_OP_MODEXP, XC_LEX_INVALID, DC_LEX_OP_DIVMOD,
 716};
 717static const //BcInst - should be this type. Using signed narrow type since DC_INST_INVALID is -1
 718int8_t
 719dc_LEX_to_INST[] ALIGN1 = { //starts at XC_LEX_OP_POWER // corresponding XC/DC_LEX_xyz:
 720        XC_INST_POWER,       XC_INST_MULTIPLY,          // XC_LEX_OP_POWER    XC_LEX_OP_MULTIPLY
 721        XC_INST_DIVIDE,      XC_INST_MODULUS,           // XC_LEX_OP_DIVIDE   XC_LEX_OP_MODULUS
 722        XC_INST_PLUS,        XC_INST_MINUS,             // XC_LEX_OP_PLUS     XC_LEX_OP_MINUS
 723        XC_INST_BOOL_NOT,                               // DC_LEX_OP_BOOL_NOT
 724        DC_INST_INVALID,                                // DC_LEX_OP_ASSIGN
 725        XC_INST_REL_GT,                                 // DC_LEX_LPAREN
 726        DC_INST_INVALID,                                // DC_LEX_SCOLON
 727        DC_INST_INVALID,                                // DC_LEX_READ
 728        XC_INST_IBASE,                                  // DC_LEX_IBASE
 729        XC_INST_SCALE,                                  // DC_LEX_SCALE
 730        XC_INST_OBASE,                                  // DC_LEX_OBASE
 731        XC_INST_LENGTH,                                 // DC_LEX_LENGTH
 732        XC_INST_PRINT,                                  // DC_LEX_PRINT
 733        DC_INST_QUIT,                                   // DC_LEX_QUIT
 734        XC_INST_SQRT,                                   // DC_LEX_SQRT
 735        XC_INST_REL_GE,                                 // DC_LEX_LBRACE
 736        XC_INST_REL_EQ,                                 // DC_LEX_EQ_NO_REG
 737        DC_INST_MODEXP,      DC_INST_DIVMOD,            // DC_LEX_OP_MODEXP   DC_LEX_OP_DIVMOD
 738        DC_INST_INVALID,     DC_INST_INVALID,           // DC_LEX_COLON       DC_LEX_ELSE
 739        DC_INST_EXECUTE,                                // DC_LEX_EXECUTE
 740        DC_INST_PRINT_STACK, DC_INST_CLEAR_STACK,       // DC_LEX_PRINT_STACK DC_LEX_CLEAR_STACK
 741        DC_INST_STACK_LEN,   DC_INST_DUPLICATE,         // DC_LEX_STACK_LEVEL DC_LEX_DUPLICATE
 742        DC_INST_SWAP,        XC_INST_POP,               // DC_LEX_SWAP        DC_LEX_POP
 743        DC_INST_ASCIIFY,     DC_INST_PRINT_STREAM,      // DC_LEX_ASCIIFY     DC_LEX_PRINT_STREAM
 744        DC_INST_INVALID,     DC_INST_INVALID,           // DC_LEX_STORE_IBASE DC_LEX_STORE_OBASE
 745        DC_INST_INVALID,     DC_INST_INVALID,           // DC_LEX_STORE_SCALE DC_LEX_LOAD
 746        DC_INST_INVALID,     DC_INST_INVALID,           // DC_LEX_LOAD_POP    DC_LEX_STORE_PUSH
 747        XC_INST_PRINT,       DC_INST_NQUIT,             // DC_LEX_PRINT_POP   DC_LEX_NQUIT
 748        XC_INST_SCALE_FUNC,                             // DC_LEX_SCALE_FACTOR
 749        // DC_INST_INVALID in this table either means that corresponding LEX
 750        // is not possible for dc, or that it does not compile one-to-one
 751        // to a single INST.
 752};
 753#endif // ENABLE_DC
 754
 755typedef struct BcParse {
 756        smallint lex;      // was BcLexType // first member is most used
 757        smallint lex_last; // was BcLexType
 758        size_t lex_line;
 759        const char *lex_inbuf;
 760        const char *lex_next_at; // last lex_next() was called at this string
 761        const char *lex_filename;
 762        FILE *lex_input_fp;
 763        BcVec  lex_strnumbuf;
 764
 765        BcFunc *func;
 766        size_t fidx;
 767        IF_BC(size_t in_funcdef;)
 768        IF_BC(BcVec exits;)
 769        IF_BC(BcVec conds;)
 770        IF_BC(BcVec ops;)
 771} BcParse;
 772
 773typedef struct BcProgram {
 774        size_t len;
 775        size_t nchars;
 776
 777        size_t scale;
 778        size_t ib_t;
 779        size_t ob_t;
 780
 781        BcVec results;
 782        BcVec exestack;
 783
 784        BcVec fns;
 785        IF_BC(BcVec fn_map;)
 786
 787        BcVec vars;
 788        BcVec var_map;
 789
 790        BcVec arrs;
 791        BcVec arr_map;
 792
 793        IF_DC(BcVec strs;)
 794        IF_DC(BcVec consts;)
 795
 796        BcNum zero;
 797        IF_BC(BcNum one;)
 798        IF_BC(BcNum last;)
 799} BcProgram;
 800
 801struct globals {
 802        BcParse prs; // first member is most used
 803
 804        // For error messages. Can be set to current parsed line,
 805        // or [TODO] to current executing line (can be before last parsed one)
 806        size_t err_line;
 807
 808        BcVec input_buffer;
 809
 810        IF_FEATURE_BC_INTERACTIVE(smallint ttyin;)
 811        IF_FEATURE_CLEAN_UP(smallint exiting;)
 812
 813        BcProgram prog;
 814
 815        BcVec files;
 816
 817        char *env_args;
 818
 819#if ENABLE_FEATURE_EDITING
 820        line_input_t *line_input_state;
 821#endif
 822} FIX_ALIASING;
 823#define G (*ptr_to_globals)
 824#define INIT_G() do { \
 825        SET_PTR_TO_GLOBALS(xzalloc(sizeof(G))); \
 826} while (0)
 827#define FREE_G() do { \
 828        FREE_PTR_TO_GLOBALS(); \
 829} while (0)
 830#define G_posix (ENABLE_BC && (option_mask32 & BC_FLAG_S))
 831#define G_warn  (ENABLE_BC && (option_mask32 & BC_FLAG_W))
 832#define G_exreg (ENABLE_DC && (option_mask32 & DC_FLAG_X))
 833#if ENABLE_FEATURE_BC_INTERACTIVE
 834# define G_interrupt bb_got_signal
 835# define G_ttyin     G.ttyin
 836#else
 837# define G_interrupt 0
 838# define G_ttyin     0
 839#endif
 840#if ENABLE_FEATURE_CLEAN_UP
 841# define G_exiting G.exiting
 842#else
 843# define G_exiting 0
 844#endif
 845#define IS_BC (ENABLE_BC && (!ENABLE_DC || applet_name[0] == 'b'))
 846#define IS_DC (ENABLE_DC && (!ENABLE_BC || applet_name[0] != 'b'))
 847
 848#if ENABLE_BC
 849# define BC_PARSE_REL           (1 << 0)
 850# define BC_PARSE_PRINT         (1 << 1)
 851# define BC_PARSE_ARRAY         (1 << 2)
 852# define BC_PARSE_NOCALL        (1 << 3)
 853#endif
 854
 855#define BC_PROG_MAIN      0
 856#define BC_PROG_READ      1
 857#if ENABLE_DC
 858#define BC_PROG_REQ_FUNCS 2
 859#endif
 860
 861#define BC_FLAG_W (1 << 0)
 862#define BC_FLAG_V (1 << 1)
 863#define BC_FLAG_S (1 << 2)
 864#define BC_FLAG_Q (1 << 3)
 865#define BC_FLAG_L (1 << 4)
 866#define BC_FLAG_I ((1 << 5) * ENABLE_DC)
 867#define DC_FLAG_X ((1 << 6) * ENABLE_DC)
 868
 869#define BC_MAX_OBASE    ((unsigned) 999)
 870#define BC_MAX_DIM      ((unsigned) INT_MAX)
 871#define BC_MAX_SCALE    ((unsigned) UINT_MAX)
 872#define BC_MAX_STRING   ((unsigned) UINT_MAX - 1)
 873#define BC_MAX_NUM      BC_MAX_STRING
 874// Unused apart from "limits" message. Just show a "biggish number" there.
 875//#define BC_MAX_EXP      ((unsigned long) LONG_MAX)
 876//#define BC_MAX_VARS     ((unsigned long) SIZE_MAX - 1)
 877#define BC_MAX_EXP_STR  "999999999"
 878#define BC_MAX_VARS_STR "999999999"
 879
 880#define BC_MAX_OBASE_STR "999"
 881
 882#if INT_MAX == 2147483647
 883# define BC_MAX_DIM_STR "2147483647"
 884#elif INT_MAX == 9223372036854775807
 885# define BC_MAX_DIM_STR "9223372036854775807"
 886#else
 887# error Strange INT_MAX
 888#endif
 889
 890#if UINT_MAX == 4294967295U
 891# define BC_MAX_SCALE_STR  "4294967295"
 892# define BC_MAX_STRING_STR "4294967294"
 893#elif UINT_MAX == 18446744073709551615U
 894# define BC_MAX_SCALE_STR  "18446744073709551615"
 895# define BC_MAX_STRING_STR "18446744073709551614"
 896#else
 897# error Strange UINT_MAX
 898#endif
 899#define BC_MAX_NUM_STR BC_MAX_STRING_STR
 900
 901// In configurations where errors abort instead of propagating error
 902// return code up the call chain, functions returning BC_STATUS
 903// actually don't return anything, they always succeed and return "void".
 904// A macro wrapper is provided, which makes this statement work:
 905//  s = zbc_func(...)
 906// and makes it visible to the compiler that s is always zero,
 907// allowing compiler to optimize dead code after the statement.
 908//
 909// To make code more readable, each such function has a "z"
 910// ("always returning zero") prefix, i.e. zbc_foo or zdc_foo.
 911//
 912#if ENABLE_FEATURE_BC_INTERACTIVE || ENABLE_FEATURE_CLEAN_UP
 913# define ERRORS_ARE_FATAL 0
 914# define ERRORFUNC        /*nothing*/
 915# define IF_ERROR_RETURN_POSSIBLE(a)  a
 916# define BC_STATUS        BcStatus
 917# define RETURN_STATUS(v) return (v)
 918# define COMMA_SUCCESS    /*nothing*/
 919#else
 920# define ERRORS_ARE_FATAL 1
 921# define ERRORFUNC        NORETURN
 922# define IF_ERROR_RETURN_POSSIBLE(a)  /*nothing*/
 923# define BC_STATUS        void
 924# define RETURN_STATUS(v) do { ((void)(v)); return; } while (0)
 925# define COMMA_SUCCESS    ,BC_STATUS_SUCCESS
 926#endif
 927
 928//
 929// Utility routines
 930//
 931
 932#define BC_MAX(a, b) ((a) > (b) ? (a) : (b))
 933#define BC_MIN(a, b) ((a) < (b) ? (a) : (b))
 934
 935static void fflush_and_check(void)
 936{
 937        fflush_all();
 938        if (ferror(stdout) || ferror(stderr))
 939                bb_simple_perror_msg_and_die("output error");
 940}
 941
 942#if ENABLE_FEATURE_CLEAN_UP
 943#define QUIT_OR_RETURN_TO_MAIN \
 944do { \
 945        IF_FEATURE_BC_INTERACTIVE(G_ttyin = 0;) /* do not loop in main loop anymore */ \
 946        G_exiting = 1; \
 947        return BC_STATUS_FAILURE; \
 948} while (0)
 949#else
 950static void quit(void) NORETURN;
 951static void quit(void)
 952{
 953        if (ferror(stdin))
 954                bb_simple_perror_msg_and_die("input error");
 955        fflush_and_check();
 956        dbg_exec("quit(): exiting with exitcode SUCCESS");
 957        exit(0);
 958}
 959#define QUIT_OR_RETURN_TO_MAIN quit()
 960#endif
 961
 962static void bc_verror_msg(const char *fmt, va_list p)
 963{
 964        const char *sv = sv; // for compiler
 965        if (G.prs.lex_filename) {
 966                sv = applet_name;
 967                applet_name = xasprintf("%s: %s:%lu", applet_name,
 968                        G.prs.lex_filename, (unsigned long)G.err_line
 969                );
 970        }
 971        bb_verror_msg(fmt, p, NULL);
 972        if (G.prs.lex_filename) {
 973                free((char*)applet_name);
 974                applet_name = sv;
 975        }
 976}
 977
 978static NOINLINE ERRORFUNC int bc_error_fmt(const char *fmt, ...)
 979{
 980        va_list p;
 981
 982        va_start(p, fmt);
 983        bc_verror_msg(fmt, p);
 984        va_end(p);
 985
 986        if (ENABLE_FEATURE_CLEAN_UP || G_ttyin)
 987                IF_ERROR_RETURN_POSSIBLE(return BC_STATUS_FAILURE);
 988        exit(1);
 989}
 990
 991#if ENABLE_BC
 992static NOINLINE BC_STATUS zbc_posix_error_fmt(const char *fmt, ...)
 993{
 994        va_list p;
 995
 996        // Are non-POSIX constructs totally ok?
 997        if (!(option_mask32 & (BC_FLAG_S|BC_FLAG_W)))
 998                RETURN_STATUS(BC_STATUS_SUCCESS); // yes
 999
1000        va_start(p, fmt);
1001        bc_verror_msg(fmt, p);
1002        va_end(p);
1003
1004        // Do we treat non-POSIX constructs as errors?
1005        if (!(option_mask32 & BC_FLAG_S))
1006                RETURN_STATUS(BC_STATUS_SUCCESS); // no, it's a warning
1007
1008        if (ENABLE_FEATURE_CLEAN_UP || G_ttyin)
1009                RETURN_STATUS(BC_STATUS_FAILURE);
1010        exit(1);
1011}
1012#define zbc_posix_error_fmt(...) (zbc_posix_error_fmt(__VA_ARGS__) COMMA_SUCCESS)
1013#endif
1014
1015// We use error functions with "return bc_error(FMT[, PARAMS])" idiom.
1016// This idiom begs for tail-call optimization, but for it to work,
1017// function must not have caller-cleaned parameters on stack.
1018// Unfortunately, vararg function API does exactly that on most arches.
1019// Thus, use these shims for the cases when we have no vararg PARAMS:
1020static ERRORFUNC int bc_error(const char *msg)
1021{
1022        IF_ERROR_RETURN_POSSIBLE(return) bc_error_fmt("%s", msg);
1023}
1024static ERRORFUNC int bc_error_at(const char *msg)
1025{
1026        const char *err_at = G.prs.lex_next_at;
1027        if (err_at) {
1028                IF_ERROR_RETURN_POSSIBLE(return) bc_error_fmt(
1029                        "%s at '%.*s'",
1030                        msg,
1031                        (int)(strchrnul(err_at, '\n') - err_at),
1032                        err_at
1033                );
1034        }
1035        IF_ERROR_RETURN_POSSIBLE(return) bc_error_fmt("%s", msg);
1036}
1037static ERRORFUNC int bc_error_bad_character(char c)
1038{
1039        if (!c)
1040                IF_ERROR_RETURN_POSSIBLE(return) bc_error("NUL character");
1041        IF_ERROR_RETURN_POSSIBLE(return) bc_error_fmt("bad character '%c'", c);
1042}
1043#if ENABLE_BC
1044static ERRORFUNC int bc_error_bad_function_definition(void)
1045{
1046        IF_ERROR_RETURN_POSSIBLE(return) bc_error_at("bad function definition");
1047}
1048#endif
1049static ERRORFUNC int bc_error_bad_expression(void)
1050{
1051        IF_ERROR_RETURN_POSSIBLE(return) bc_error_at("bad expression");
1052}
1053static ERRORFUNC int bc_error_bad_assignment(void)
1054{
1055        IF_ERROR_RETURN_POSSIBLE(return) bc_error_at(
1056                "bad assignment: left side must be variable or array element"
1057        );
1058}
1059static ERRORFUNC int bc_error_bad_token(void)
1060{
1061        IF_ERROR_RETURN_POSSIBLE(return) bc_error_at("bad token");
1062}
1063static ERRORFUNC int bc_error_stack_has_too_few_elements(void)
1064{
1065        IF_ERROR_RETURN_POSSIBLE(return) bc_error("stack has too few elements");
1066}
1067static ERRORFUNC int bc_error_variable_is_wrong_type(void)
1068{
1069        IF_ERROR_RETURN_POSSIBLE(return) bc_error("variable is wrong type");
1070}
1071#if ENABLE_BC
1072static BC_STATUS zbc_POSIX_requires(const char *msg)
1073{
1074        RETURN_STATUS(zbc_posix_error_fmt("POSIX requires %s", msg));
1075}
1076#define zbc_POSIX_requires(...) (zbc_POSIX_requires(__VA_ARGS__) COMMA_SUCCESS)
1077static BC_STATUS zbc_POSIX_does_not_allow(const char *msg)
1078{
1079        RETURN_STATUS(zbc_posix_error_fmt("%s%s", "POSIX does not allow ", msg));
1080}
1081#define zbc_POSIX_does_not_allow(...) (zbc_POSIX_does_not_allow(__VA_ARGS__) COMMA_SUCCESS)
1082static BC_STATUS zbc_POSIX_does_not_allow_bool_ops_this_is_bad(const char *msg)
1083{
1084        RETURN_STATUS(zbc_posix_error_fmt("%s%s %s", "POSIX does not allow ", "boolean operators; this is bad:", msg));
1085}
1086#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)
1087static BC_STATUS zbc_POSIX_does_not_allow_empty_X_expression_in_for(const char *msg)
1088{
1089        RETURN_STATUS(zbc_posix_error_fmt("%san empty %s expression in 'for()'", "POSIX does not allow ", msg));
1090}
1091#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)
1092#endif
1093
1094static void bc_vec_grow(BcVec *v, size_t n)
1095{
1096        size_t cap = v->cap * 2;
1097        while (cap < v->len + n) cap *= 2;
1098        v->v = xrealloc(v->v, v->size * cap);
1099        v->cap = cap;
1100}
1101
1102static void bc_vec_init(BcVec *v, size_t esize, BcVecFree dtor)
1103{
1104        v->size = esize;
1105        v->cap = BC_VEC_START_CAP;
1106        v->len = 0;
1107        v->dtor = dtor;
1108        v->v = xmalloc(esize * BC_VEC_START_CAP);
1109}
1110
1111static void bc_char_vec_init(BcVec *v)
1112{
1113        bc_vec_init(v, sizeof(char), NULL);
1114}
1115
1116static void bc_vec_expand(BcVec *v, size_t req)
1117{
1118        if (v->cap < req) {
1119                v->v = xrealloc(v->v, v->size * req);
1120                v->cap = req;
1121        }
1122}
1123
1124static void bc_vec_pop(BcVec *v)
1125{
1126        v->len--;
1127        if (v->dtor)
1128                v->dtor(v->v + (v->size * v->len));
1129}
1130
1131static void bc_vec_npop(BcVec *v, size_t n)
1132{
1133        if (!v->dtor)
1134                v->len -= n;
1135        else {
1136                size_t len = v->len - n;
1137                while (v->len > len) v->dtor(v->v + (v->size * --v->len));
1138        }
1139}
1140
1141static void bc_vec_pop_all(BcVec *v)
1142{
1143        bc_vec_npop(v, v->len);
1144}
1145
1146static size_t bc_vec_npush(BcVec *v, size_t n, const void *data)
1147{
1148        size_t len = v->len;
1149        if (len + n > v->cap) bc_vec_grow(v, n);
1150        memmove(v->v + (v->size * len), data, v->size * n);
1151        v->len = len + n;
1152        return len;
1153}
1154
1155static size_t bc_vec_push(BcVec *v, const void *data)
1156{
1157        return bc_vec_npush(v, 1, data);
1158        //size_t len = v->len;
1159        //if (len >= v->cap) bc_vec_grow(v, 1);
1160        //memmove(v->v + (v->size * len), data, v->size);
1161        //v->len = len + 1;
1162        //return len;
1163}
1164
1165// G.prog.results often needs "pop old operand, push result" idiom.
1166// Can do this without a few extra ops
1167static size_t bc_result_pop_and_push(const void *data)
1168{
1169        BcVec *v = &G.prog.results;
1170        char *last;
1171        size_t len = v->len - 1;
1172
1173        last = v->v + (v->size * len);
1174        if (v->dtor)
1175                v->dtor(last);
1176        memmove(last, data, v->size);
1177        return len;
1178}
1179
1180static size_t bc_vec_pushByte(BcVec *v, char data)
1181{
1182        return bc_vec_push(v, &data);
1183}
1184
1185static size_t bc_vec_pushZeroByte(BcVec *v)
1186{
1187        //return bc_vec_pushByte(v, '\0');
1188        // better:
1189        return bc_vec_push(v, &const_int_0);
1190}
1191
1192static void bc_vec_pushAt(BcVec *v, const void *data, size_t idx)
1193{
1194        if (idx == v->len)
1195                bc_vec_push(v, data);
1196        else {
1197                char *ptr;
1198
1199                if (v->len == v->cap) bc_vec_grow(v, 1);
1200
1201                ptr = v->v + v->size * idx;
1202
1203                memmove(ptr + v->size, ptr, v->size * (v->len++ - idx));
1204                memmove(ptr, data, v->size);
1205        }
1206}
1207
1208static void bc_vec_string(BcVec *v, size_t len, const char *str)
1209{
1210        bc_vec_pop_all(v);
1211        bc_vec_expand(v, len + 1);
1212        memcpy(v->v, str, len);
1213        v->len = len;
1214
1215        bc_vec_pushZeroByte(v);
1216}
1217
1218static void *bc_vec_item(const BcVec *v, size_t idx)
1219{
1220        return v->v + v->size * idx;
1221}
1222
1223static void *bc_vec_item_rev(const BcVec *v, size_t idx)
1224{
1225        return v->v + v->size * (v->len - idx - 1);
1226}
1227
1228static void *bc_vec_top(const BcVec *v)
1229{
1230        return v->v + v->size * (v->len - 1);
1231}
1232
1233static FAST_FUNC void bc_vec_free(void *vec)
1234{
1235        BcVec *v = (BcVec *) vec;
1236        bc_vec_pop_all(v);
1237        free(v->v);
1238}
1239
1240static BcFunc* xc_program_func(size_t idx)
1241{
1242        return bc_vec_item(&G.prog.fns, idx);
1243}
1244// BC_PROG_MAIN is zeroth element, so:
1245#define xc_program_func_BC_PROG_MAIN() ((BcFunc*)(G.prog.fns.v))
1246
1247#if ENABLE_BC
1248static BcFunc* bc_program_current_func(void)
1249{
1250        BcInstPtr *ip = bc_vec_top(&G.prog.exestack);
1251        BcFunc *func = xc_program_func(ip->func);
1252        return func;
1253}
1254#endif
1255
1256static char** xc_program_str(size_t idx)
1257{
1258#if ENABLE_BC
1259        if (IS_BC) {
1260                BcFunc *func = bc_program_current_func();
1261                return bc_vec_item(&func->strs, idx);
1262        }
1263#endif
1264        IF_DC(return bc_vec_item(&G.prog.strs, idx);)
1265}
1266
1267static char** xc_program_const(size_t idx)
1268{
1269#if ENABLE_BC
1270        if (IS_BC) {
1271                BcFunc *func = bc_program_current_func();
1272                return bc_vec_item(&func->consts, idx);
1273        }
1274#endif
1275        IF_DC(return bc_vec_item(&G.prog.consts, idx);)
1276}
1277
1278static int bc_id_cmp(const void *e1, const void *e2)
1279{
1280        return strcmp(((const BcId *) e1)->name, ((const BcId *) e2)->name);
1281}
1282
1283static FAST_FUNC void bc_id_free(void *id)
1284{
1285        free(((BcId *) id)->name);
1286}
1287
1288static size_t bc_map_find_ge(const BcVec *v, const void *ptr)
1289{
1290        size_t low = 0, high = v->len;
1291
1292        while (low < high) {
1293                size_t mid = (low + high) / 2;
1294                BcId *id = bc_vec_item(v, mid);
1295                int result = bc_id_cmp(ptr, id);
1296
1297                if (result == 0)
1298                        return mid;
1299                if (result < 0)
1300                        high = mid;
1301                else
1302                        low = mid + 1;
1303        }
1304
1305        return low;
1306}
1307
1308static int bc_map_insert(BcVec *v, const void *ptr, size_t *i)
1309{
1310        size_t n = *i = bc_map_find_ge(v, ptr);
1311
1312        if (n == v->len)
1313                bc_vec_push(v, ptr);
1314        else if (!bc_id_cmp(ptr, bc_vec_item(v, n)))
1315                return 0; // "was not inserted"
1316        else
1317                bc_vec_pushAt(v, ptr, n);
1318        return 1; // "was inserted"
1319}
1320
1321static size_t bc_map_find_exact(const BcVec *v, const void *ptr)
1322{
1323        size_t i = bc_map_find_ge(v, ptr);
1324        if (i >= v->len) return BC_VEC_INVALID_IDX;
1325        return bc_id_cmp(ptr, bc_vec_item(v, i)) ? BC_VEC_INVALID_IDX : i;
1326}
1327
1328static void bc_num_setToZero(BcNum *n, size_t scale)
1329{
1330        n->len = 0;
1331        n->neg = false;
1332        n->rdx = scale;
1333}
1334
1335static void bc_num_zero(BcNum *n)
1336{
1337        bc_num_setToZero(n, 0);
1338}
1339
1340static void bc_num_one(BcNum *n)
1341{
1342        bc_num_setToZero(n, 0);
1343        n->len = 1;
1344        n->num[0] = 1;
1345}
1346
1347// Note: this also sets BcNum to zero
1348static void bc_num_init(BcNum *n, size_t req)
1349{
1350        req = req >= BC_NUM_DEF_SIZE ? req : BC_NUM_DEF_SIZE;
1351        //memset(n, 0, sizeof(BcNum)); - cleared by assignments below
1352        n->num = xmalloc(req);
1353        n->cap = req;
1354        n->rdx = 0;
1355        n->len = 0;
1356        n->neg = false;
1357}
1358
1359static void bc_num_init_DEF_SIZE(BcNum *n)
1360{
1361        bc_num_init(n, BC_NUM_DEF_SIZE);
1362}
1363
1364static void bc_num_expand(BcNum *n, size_t req)
1365{
1366        req = req >= BC_NUM_DEF_SIZE ? req : BC_NUM_DEF_SIZE;
1367        if (req > n->cap) {
1368                n->num = xrealloc(n->num, req);
1369                n->cap = req;
1370        }
1371}
1372
1373static FAST_FUNC void bc_num_free(void *num)
1374{
1375        free(((BcNum *) num)->num);
1376}
1377
1378static void bc_num_copy(BcNum *d, BcNum *s)
1379{
1380        if (d != s) {
1381                bc_num_expand(d, s->cap);
1382                d->len = s->len;
1383                d->neg = s->neg;
1384                d->rdx = s->rdx;
1385                memcpy(d->num, s->num, sizeof(BcDig) * d->len);
1386        }
1387}
1388
1389static void bc_num_init_and_copy(BcNum *d, BcNum *s)
1390{
1391        bc_num_init(d, s->len);
1392        bc_num_copy(d, s);
1393}
1394
1395static BC_STATUS zbc_num_ulong_abs(BcNum *n, unsigned long *result_p)
1396{
1397        size_t i;
1398        unsigned long result;
1399
1400        result = 0;
1401        i = n->len;
1402        while (i > n->rdx) {
1403                unsigned long prev = result;
1404                result = result * 10 + n->num[--i];
1405                // Even overflowed N*10 can still satisfy N*10>=N. For example,
1406                //    0x1ff00000 * 10 is 0x13f600000,
1407                // or 0x3f600000 truncated to 32 bits. Which is larger.
1408                // However, (N*10)/8 < N check is always correct.
1409                if ((result / 8) < prev)
1410                        RETURN_STATUS(bc_error("overflow"));
1411        }
1412        *result_p = result;
1413
1414        RETURN_STATUS(BC_STATUS_SUCCESS);
1415}
1416#define zbc_num_ulong_abs(...) (zbc_num_ulong_abs(__VA_ARGS__) COMMA_SUCCESS)
1417
1418static BC_STATUS zbc_num_ulong(BcNum *n, unsigned long *result_p)
1419{
1420        if (n->neg) RETURN_STATUS(bc_error("negative number"));
1421
1422        RETURN_STATUS(zbc_num_ulong_abs(n, result_p));
1423}
1424#define zbc_num_ulong(...) (zbc_num_ulong(__VA_ARGS__) COMMA_SUCCESS)
1425
1426#if ULONG_MAX == 0xffffffffUL // 10 digits: 4294967295
1427# define ULONG_NUM_BUFSIZE (10 > BC_NUM_DEF_SIZE ? 10 : BC_NUM_DEF_SIZE)
1428#elif ULONG_MAX == 0xffffffffffffffffULL // 20 digits: 18446744073709551615
1429# define ULONG_NUM_BUFSIZE (20 > BC_NUM_DEF_SIZE ? 20 : BC_NUM_DEF_SIZE)
1430#endif
1431// minimum BC_NUM_DEF_SIZE, so that bc_num_expand() in bc_num_ulong2num()
1432// would not hit realloc() code path - not good if num[] is not malloced
1433
1434static void bc_num_ulong2num(BcNum *n, unsigned long val)
1435{
1436        BcDig *ptr;
1437
1438        bc_num_zero(n);
1439
1440        if (val == 0) return;
1441
1442        bc_num_expand(n, ULONG_NUM_BUFSIZE);
1443
1444        ptr = n->num;
1445        for (;;) {
1446                n->len++;
1447                *ptr++ = val % 10;
1448                val /= 10;
1449                if (val == 0) break;
1450        }
1451}
1452
1453static void bc_num_subArrays(BcDig *restrict a, BcDig *restrict b, size_t len)
1454{
1455        size_t i, j;
1456        for (i = 0; i < len; ++i) {
1457                a[i] -= b[i];
1458                for (j = i; a[j] < 0;) {
1459                        a[j++] += 10;
1460                        a[j] -= 1;
1461                }
1462        }
1463}
1464
1465static ssize_t bc_num_compare(BcDig *restrict a, BcDig *restrict b, size_t len)
1466{
1467        size_t i = len;
1468        for (;;) {
1469                int c;
1470                if (i == 0)
1471                        return 0;
1472                i--;
1473                c = a[i] - b[i];
1474                if (c != 0) {
1475                        i++;
1476                        if (c < 0)
1477                                return -i;
1478                        return i;
1479                }
1480        }
1481}
1482
1483#define BC_NUM_NEG(n, neg)      ((((ssize_t)(n)) ^ -((ssize_t)(neg))) + (neg))
1484#define BC_NUM_ONE(n)           ((n)->len == 1 && (n)->rdx == 0 && (n)->num[0] == 1)
1485#define BC_NUM_INT(n)           ((n)->len - (n)->rdx)
1486//#define BC_NUM_AREQ(a, b)       (BC_MAX((a)->rdx, (b)->rdx) + BC_MAX(BC_NUM_INT(a), BC_NUM_INT(b)) + 1)
1487static /*ALWAYS_INLINE*/ size_t BC_NUM_AREQ(BcNum *a, BcNum *b)
1488{
1489        return BC_MAX(a->rdx, b->rdx) + BC_MAX(BC_NUM_INT(a), BC_NUM_INT(b)) + 1;
1490}
1491//#define BC_NUM_MREQ(a, b, scale) (BC_NUM_INT(a) + BC_NUM_INT(b) + BC_MAX((scale), (a)->rdx + (b)->rdx) + 1)
1492static /*ALWAYS_INLINE*/ size_t BC_NUM_MREQ(BcNum *a, BcNum *b, size_t scale)
1493{
1494        return BC_NUM_INT(a) + BC_NUM_INT(b) + BC_MAX(scale, a->rdx + b->rdx) + 1;
1495}
1496
1497static ssize_t bc_num_cmp(BcNum *a, BcNum *b)
1498{
1499        size_t i, min, a_int, b_int, diff;
1500        BcDig *max_num, *min_num;
1501        bool a_max, neg;
1502        ssize_t cmp;
1503
1504        if (a == b) return 0;
1505        if (a->len == 0) return BC_NUM_NEG(!!b->len, !b->neg);
1506        if (b->len == 0) return BC_NUM_NEG(1, a->neg);
1507
1508        if (a->neg != b->neg) // signs of a and b differ
1509                // +a,-b = a>b = 1 or -a,+b = a<b = -1
1510                return (int)b->neg - (int)a->neg;
1511        neg = a->neg; // 1 if both negative, 0 if both positive
1512
1513        a_int = BC_NUM_INT(a);
1514        b_int = BC_NUM_INT(b);
1515        a_int -= b_int;
1516
1517        if (a_int != 0) {
1518                if (neg) return - (ssize_t) a_int;
1519                return (ssize_t) a_int;
1520        }
1521
1522        a_max = (a->rdx > b->rdx);
1523        if (a_max) {
1524                min = b->rdx;
1525                diff = a->rdx - b->rdx;
1526                max_num = a->num + diff;
1527                min_num = b->num;
1528                // neg = (a_max == neg); - NOP (maps 1->1 and 0->0)
1529        } else {
1530                min = a->rdx;
1531                diff = b->rdx - a->rdx;
1532                max_num = b->num + diff;
1533                min_num = a->num;
1534                neg = !neg; // same as "neg = (a_max == neg)"
1535        }
1536
1537        cmp = bc_num_compare(max_num, min_num, b_int + min);
1538        if (cmp != 0) return BC_NUM_NEG(cmp, neg);
1539
1540        for (max_num -= diff, i = diff - 1; i < diff; --i) {
1541                if (max_num[i]) return BC_NUM_NEG(1, neg);
1542        }
1543
1544        return 0;
1545}
1546
1547static void bc_num_truncate(BcNum *n, size_t places)
1548{
1549        if (places == 0) return;
1550
1551        n->rdx -= places;
1552
1553        if (n->len != 0) {
1554                n->len -= places;
1555                memmove(n->num, n->num + places, n->len * sizeof(BcDig));
1556        }
1557}
1558
1559static void bc_num_extend(BcNum *n, size_t places)
1560{
1561        size_t len = n->len + places;
1562
1563        if (places != 0) {
1564                if (n->cap < len) bc_num_expand(n, len);
1565
1566                memmove(n->num + places, n->num, sizeof(BcDig) * n->len);
1567                memset(n->num, 0, sizeof(BcDig) * places);
1568
1569                n->len += places;
1570                n->rdx += places;
1571        }
1572}
1573
1574static void bc_num_clean(BcNum *n)
1575{
1576        while (n->len > 0 && n->num[n->len - 1] == 0) --n->len;
1577        if (n->len == 0)
1578                n->neg = false;
1579        else if (n->len < n->rdx)
1580                n->len = n->rdx;
1581}
1582
1583static void bc_num_retireMul(BcNum *n, size_t scale, bool neg1, bool neg2)
1584{
1585        if (n->rdx < scale)
1586                bc_num_extend(n, scale - n->rdx);
1587        else
1588                bc_num_truncate(n, n->rdx - scale);
1589
1590        bc_num_clean(n);
1591        if (n->len != 0) n->neg = !neg1 != !neg2;
1592}
1593
1594static void bc_num_split(BcNum *restrict n, size_t idx, BcNum *restrict a,
1595                         BcNum *restrict b)
1596{
1597        if (idx < n->len) {
1598                b->len = n->len - idx;
1599                a->len = idx;
1600                a->rdx = b->rdx = 0;
1601
1602                memcpy(b->num, n->num + idx, b->len * sizeof(BcDig));
1603                memcpy(a->num, n->num, idx * sizeof(BcDig));
1604        } else {
1605                bc_num_zero(b);
1606                bc_num_copy(a, n);
1607        }
1608
1609        bc_num_clean(a);
1610        bc_num_clean(b);
1611}
1612
1613static BC_STATUS zbc_num_shift(BcNum *n, size_t places)
1614{
1615        if (places == 0 || n->len == 0) RETURN_STATUS(BC_STATUS_SUCCESS);
1616
1617        // This check makes sense only if size_t is (much) larger than BC_MAX_NUM.
1618        if (SIZE_MAX > (BC_MAX_NUM | 0xff)) {
1619                if (places + n->len > BC_MAX_NUM)
1620                        RETURN_STATUS(bc_error("number too long: must be [1,"BC_MAX_NUM_STR"]"));
1621        }
1622
1623        if (n->rdx >= places)
1624                n->rdx -= places;
1625        else {
1626                bc_num_extend(n, places - n->rdx);
1627                n->rdx = 0;
1628        }
1629
1630        bc_num_clean(n);
1631
1632        RETURN_STATUS(BC_STATUS_SUCCESS);
1633}
1634#define zbc_num_shift(...) (zbc_num_shift(__VA_ARGS__) COMMA_SUCCESS)
1635
1636typedef BC_STATUS (*BcNumBinaryOp)(BcNum *, BcNum *, BcNum *, size_t) FAST_FUNC;
1637
1638static BC_STATUS zbc_num_binary(BcNum *a, BcNum *b, BcNum *c, size_t scale,
1639                              BcNumBinaryOp op, size_t req)
1640{
1641        BcStatus s;
1642        BcNum num2, *ptr_a, *ptr_b;
1643        bool init = false;
1644
1645        if (c == a) {
1646                ptr_a = &num2;
1647                memcpy(ptr_a, c, sizeof(BcNum));
1648                init = true;
1649        } else
1650                ptr_a = a;
1651
1652        if (c == b) {
1653                ptr_b = &num2;
1654                if (c != a) {
1655                        memcpy(ptr_b, c, sizeof(BcNum));
1656                        init = true;
1657                }
1658        } else
1659                ptr_b = b;
1660
1661        if (init)
1662                bc_num_init(c, req);
1663        else
1664                bc_num_expand(c, req);
1665
1666        s = BC_STATUS_SUCCESS;
1667        IF_ERROR_RETURN_POSSIBLE(s =) op(ptr_a, ptr_b, c, scale);
1668
1669        if (init) bc_num_free(&num2);
1670
1671        RETURN_STATUS(s);
1672}
1673#define zbc_num_binary(...) (zbc_num_binary(__VA_ARGS__) COMMA_SUCCESS)
1674
1675static FAST_FUNC BC_STATUS zbc_num_a(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale);
1676static FAST_FUNC BC_STATUS zbc_num_s(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale);
1677static FAST_FUNC BC_STATUS zbc_num_p(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale);
1678static FAST_FUNC BC_STATUS zbc_num_m(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale);
1679static FAST_FUNC BC_STATUS zbc_num_d(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale);
1680static FAST_FUNC BC_STATUS zbc_num_rem(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale);
1681
1682static FAST_FUNC BC_STATUS zbc_num_add(BcNum *a, BcNum *b, BcNum *c, size_t scale)
1683{
1684        BcNumBinaryOp op = (!a->neg == !b->neg) ? zbc_num_a : zbc_num_s;
1685        (void) scale;
1686        RETURN_STATUS(zbc_num_binary(a, b, c, false, op, BC_NUM_AREQ(a, b)));
1687}
1688
1689static FAST_FUNC BC_STATUS zbc_num_sub(BcNum *a, BcNum *b, BcNum *c, size_t scale)
1690{
1691        BcNumBinaryOp op = (!a->neg == !b->neg) ? zbc_num_s : zbc_num_a;
1692        (void) scale;
1693        RETURN_STATUS(zbc_num_binary(a, b, c, true, op, BC_NUM_AREQ(a, b)));
1694}
1695
1696static FAST_FUNC BC_STATUS zbc_num_mul(BcNum *a, BcNum *b, BcNum *c, size_t scale)
1697{
1698        size_t req = BC_NUM_MREQ(a, b, scale);
1699        RETURN_STATUS(zbc_num_binary(a, b, c, scale, zbc_num_m, req));
1700}
1701
1702static FAST_FUNC BC_STATUS zbc_num_div(BcNum *a, BcNum *b, BcNum *c, size_t scale)
1703{
1704        size_t req = BC_NUM_MREQ(a, b, scale);
1705        RETURN_STATUS(zbc_num_binary(a, b, c, scale, zbc_num_d, req));
1706}
1707
1708static FAST_FUNC BC_STATUS zbc_num_mod(BcNum *a, BcNum *b, BcNum *c, size_t scale)
1709{
1710        size_t req = BC_NUM_MREQ(a, b, scale);
1711        RETURN_STATUS(zbc_num_binary(a, b, c, scale, zbc_num_rem, req));
1712}
1713
1714static FAST_FUNC BC_STATUS zbc_num_pow(BcNum *a, BcNum *b, BcNum *c, size_t scale)
1715{
1716        RETURN_STATUS(zbc_num_binary(a, b, c, scale, zbc_num_p, a->len * b->len + 1));
1717}
1718
1719static const BcNumBinaryOp zxc_program_ops[] = {
1720        zbc_num_pow, zbc_num_mul, zbc_num_div, zbc_num_mod, zbc_num_add, zbc_num_sub,
1721};
1722#define zbc_num_add(...) (zbc_num_add(__VA_ARGS__) COMMA_SUCCESS)
1723#define zbc_num_sub(...) (zbc_num_sub(__VA_ARGS__) COMMA_SUCCESS)
1724#define zbc_num_mul(...) (zbc_num_mul(__VA_ARGS__) COMMA_SUCCESS)
1725#define zbc_num_div(...) (zbc_num_div(__VA_ARGS__) COMMA_SUCCESS)
1726#define zbc_num_mod(...) (zbc_num_mod(__VA_ARGS__) COMMA_SUCCESS)
1727#define zbc_num_pow(...) (zbc_num_pow(__VA_ARGS__) COMMA_SUCCESS)
1728
1729static BC_STATUS zbc_num_inv(BcNum *a, BcNum *b, size_t scale)
1730{
1731        BcNum one;
1732        BcDig num[2];
1733
1734        one.cap = 2;
1735        one.num = num;
1736        bc_num_one(&one);
1737
1738        RETURN_STATUS(zbc_num_div(&one, a, b, scale));
1739}
1740#define zbc_num_inv(...) (zbc_num_inv(__VA_ARGS__) COMMA_SUCCESS)
1741
1742static FAST_FUNC BC_STATUS zbc_num_a(BcNum *a, BcNum *b, BcNum *restrict c, size_t sub)
1743{
1744        BcDig *ptr, *ptr_a, *ptr_b, *ptr_c;
1745        size_t i, max, min_rdx, min_int, diff, a_int, b_int;
1746        unsigned carry;
1747
1748        // Because this function doesn't need to use scale (per the bc spec),
1749        // I am hijacking it to say whether it's doing an add or a subtract.
1750
1751        if (a->len == 0) {
1752                bc_num_copy(c, b);
1753                if (sub && c->len) c->neg = !c->neg;
1754                RETURN_STATUS(BC_STATUS_SUCCESS);
1755        }
1756        if (b->len == 0) {
1757                bc_num_copy(c, a);
1758                RETURN_STATUS(BC_STATUS_SUCCESS);
1759        }
1760
1761        c->neg = a->neg;
1762        c->rdx = BC_MAX(a->rdx, b->rdx);
1763        min_rdx = BC_MIN(a->rdx, b->rdx);
1764        c->len = 0;
1765
1766        if (a->rdx > b->rdx) {
1767                diff = a->rdx - b->rdx;
1768                ptr = a->num;
1769                ptr_a = a->num + diff;
1770                ptr_b = b->num;
1771        } else {
1772                diff = b->rdx - a->rdx;
1773                ptr = b->num;
1774                ptr_a = a->num;
1775                ptr_b = b->num + diff;
1776        }
1777
1778        ptr_c = c->num;
1779        for (i = 0; i < diff; ++i, ++c->len)
1780                ptr_c[i] = ptr[i];
1781
1782        ptr_c += diff;
1783        a_int = BC_NUM_INT(a);
1784        b_int = BC_NUM_INT(b);
1785
1786        if (a_int > b_int) {
1787                min_int = b_int;
1788                max = a_int;
1789                ptr = ptr_a;
1790        } else {
1791                min_int = a_int;
1792                max = b_int;
1793                ptr = ptr_b;
1794        }
1795
1796        carry = 0;
1797        for (i = 0; i < min_rdx + min_int; ++i) {
1798                unsigned in = (unsigned)ptr_a[i] + (unsigned)ptr_b[i] + carry;
1799                carry = in / 10;
1800                ptr_c[i] = (BcDig)(in % 10);
1801        }
1802        for (; i < max + min_rdx; ++i) {
1803                unsigned in = (unsigned)ptr[i] + carry;
1804                carry = in / 10;
1805                ptr_c[i] = (BcDig)(in % 10);
1806        }
1807        c->len += i;
1808
1809        if (carry != 0) c->num[c->len++] = (BcDig) carry;
1810
1811        RETURN_STATUS(BC_STATUS_SUCCESS); // can't make void, see zbc_num_binary()
1812}
1813
1814static FAST_FUNC BC_STATUS zbc_num_s(BcNum *a, BcNum *b, BcNum *restrict c, size_t sub)
1815{
1816        ssize_t cmp;
1817        BcNum *minuend, *subtrahend;
1818        size_t start;
1819        bool aneg, bneg, neg;
1820
1821        // Because this function doesn't need to use scale (per the bc spec),
1822        // I am hijacking it to say whether it's doing an add or a subtract.
1823
1824        if (a->len == 0) {
1825                bc_num_copy(c, b);
1826                if (sub && c->len) c->neg = !c->neg;
1827                RETURN_STATUS(BC_STATUS_SUCCESS);
1828        }
1829        if (b->len == 0) {
1830                bc_num_copy(c, a);
1831                RETURN_STATUS(BC_STATUS_SUCCESS);
1832        }
1833
1834        aneg = a->neg;
1835        bneg = b->neg;
1836        a->neg = b->neg = false;
1837
1838        cmp = bc_num_cmp(a, b);
1839
1840        a->neg = aneg;
1841        b->neg = bneg;
1842
1843        if (cmp == 0) {
1844                bc_num_setToZero(c, BC_MAX(a->rdx, b->rdx));
1845                RETURN_STATUS(BC_STATUS_SUCCESS);
1846        }
1847        if (cmp > 0) {
1848                neg = a->neg;
1849                minuend = a;
1850                subtrahend = b;
1851        } else {
1852                neg = b->neg;
1853                if (sub) neg = !neg;
1854                minuend = b;
1855                subtrahend = a;
1856        }
1857
1858        bc_num_copy(c, minuend);
1859        c->neg = neg;
1860
1861        if (c->rdx < subtrahend->rdx) {
1862                bc_num_extend(c, subtrahend->rdx - c->rdx);
1863                start = 0;
1864        } else
1865                start = c->rdx - subtrahend->rdx;
1866
1867        bc_num_subArrays(c->num + start, subtrahend->num, subtrahend->len);
1868
1869        bc_num_clean(c);
1870
1871        RETURN_STATUS(BC_STATUS_SUCCESS); // can't make void, see zbc_num_binary()
1872}
1873
1874static FAST_FUNC BC_STATUS zbc_num_k(BcNum *restrict a, BcNum *restrict b,
1875                         BcNum *restrict c)
1876#define zbc_num_k(...) (zbc_num_k(__VA_ARGS__) COMMA_SUCCESS)
1877{
1878        BcStatus s;
1879        size_t max, max2;
1880        BcNum l1, h1, l2, h2, m2, m1, z0, z1, z2, temp;
1881        bool aone;
1882
1883        if (a->len == 0 || b->len == 0) {
1884                bc_num_zero(c);
1885                RETURN_STATUS(BC_STATUS_SUCCESS);
1886        }
1887        aone = BC_NUM_ONE(a);
1888        if (aone || BC_NUM_ONE(b)) {
1889                bc_num_copy(c, aone ? b : a);
1890                RETURN_STATUS(BC_STATUS_SUCCESS);
1891        }
1892
1893        if (a->len < BC_NUM_KARATSUBA_LEN
1894         || b->len < BC_NUM_KARATSUBA_LEN
1895        /* || a->len + b->len < BC_NUM_KARATSUBA_LEN - redundant check */
1896        ) {
1897                size_t i, j, len;
1898
1899                bc_num_expand(c, a->len + b->len + 1);
1900
1901                memset(c->num, 0, sizeof(BcDig) * c->cap);
1902                c->len = len = 0;
1903
1904                for (i = 0; i < b->len; ++i) {
1905                        unsigned carry = 0;
1906                        for (j = 0; j < a->len; ++j) {
1907                                unsigned in = c->num[i + j];
1908                                in += (unsigned)a->num[j] * (unsigned)b->num[i] + carry;
1909                                // note: compilers prefer _unsigned_ div/const
1910                                carry = in / 10;
1911                                c->num[i + j] = (BcDig)(in % 10);
1912                        }
1913
1914                        c->num[i + j] += (BcDig) carry;
1915                        len = BC_MAX(len, i + j + !!carry);
1916
1917#if ENABLE_FEATURE_BC_INTERACTIVE
1918                        // a=2^1000000
1919                        // a*a <- without check below, this will not be interruptible
1920                        if (G_interrupt) return BC_STATUS_FAILURE;
1921#endif
1922                }
1923
1924                c->len = len;
1925
1926                RETURN_STATUS(BC_STATUS_SUCCESS);
1927        }
1928
1929        max = BC_MAX(a->len, b->len);
1930        bc_num_init(&l1, max);
1931        bc_num_init(&h1, max);
1932        bc_num_init(&l2, max);
1933        bc_num_init(&h2, max);
1934        bc_num_init(&m1, max);
1935        bc_num_init(&m2, max);
1936        bc_num_init(&z0, max);
1937        bc_num_init(&z1, max);
1938        bc_num_init(&z2, max);
1939        bc_num_init(&temp, max + max);
1940
1941        max2 = (max + 1) / 2;
1942        bc_num_split(a, max2, &l1, &h1);
1943        bc_num_split(b, max2, &l2, &h2);
1944
1945        s = zbc_num_add(&h1, &l1, &m1, 0);
1946        if (s) goto err;
1947        s = zbc_num_add(&h2, &l2, &m2, 0);
1948        if (s) goto err;
1949
1950        s = zbc_num_k(&h1, &h2, &z0);
1951        if (s) goto err;
1952        s = zbc_num_k(&m1, &m2, &z1);
1953        if (s) goto err;
1954        s = zbc_num_k(&l1, &l2, &z2);
1955        if (s) goto err;
1956
1957        s = zbc_num_sub(&z1, &z0, &temp, 0);
1958        if (s) goto err;
1959        s = zbc_num_sub(&temp, &z2, &z1, 0);
1960        if (s) goto err;
1961
1962        s = zbc_num_shift(&z0, max2 * 2);
1963        if (s) goto err;
1964        s = zbc_num_shift(&z1, max2);
1965        if (s) goto err;
1966        s = zbc_num_add(&z0, &z1, &temp, 0);
1967        if (s) goto err;
1968        s = zbc_num_add(&temp, &z2, c, 0);
1969 err:
1970        bc_num_free(&temp);
1971        bc_num_free(&z2);
1972        bc_num_free(&z1);
1973        bc_num_free(&z0);
1974        bc_num_free(&m2);
1975        bc_num_free(&m1);
1976        bc_num_free(&h2);
1977        bc_num_free(&l2);
1978        bc_num_free(&h1);
1979        bc_num_free(&l1);
1980        RETURN_STATUS(s);
1981}
1982
1983static FAST_FUNC BC_STATUS zbc_num_m(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale)
1984{
1985        BcStatus s;
1986        BcNum cpa, cpb;
1987        size_t maxrdx = BC_MAX(a->rdx, b->rdx);
1988
1989        scale = BC_MAX(scale, a->rdx);
1990        scale = BC_MAX(scale, b->rdx);
1991        scale = BC_MIN(a->rdx + b->rdx, scale);
1992        maxrdx = BC_MAX(maxrdx, scale);
1993
1994        bc_num_init_and_copy(&cpa, a);
1995        bc_num_init_and_copy(&cpb, b);
1996        cpa.neg = cpb.neg = false;
1997
1998        s = zbc_num_shift(&cpa, maxrdx);
1999        if (s) goto err;
2000        s = zbc_num_shift(&cpb, maxrdx);
2001        if (s) goto err;
2002        s = zbc_num_k(&cpa, &cpb, c);
2003        if (s) goto err;
2004
2005        maxrdx += scale;
2006        bc_num_expand(c, c->len + maxrdx);
2007
2008        if (c->len < maxrdx) {
2009                memset(c->num + c->len, 0, (c->cap - c->len) * sizeof(BcDig));
2010                c->len += maxrdx;
2011        }
2012
2013        c->rdx = maxrdx;
2014        bc_num_retireMul(c, scale, a->neg, b->neg);
2015 err:
2016        bc_num_free(&cpb);
2017        bc_num_free(&cpa);
2018        RETURN_STATUS(s);
2019}
2020#define zbc_num_m(...) (zbc_num_m(__VA_ARGS__) COMMA_SUCCESS)
2021
2022static FAST_FUNC BC_STATUS zbc_num_d(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale)
2023{
2024        BcStatus s;
2025        size_t len, end, i;
2026        BcNum cp;
2027
2028        if (b->len == 0)
2029                RETURN_STATUS(bc_error("divide by zero"));
2030        if (a->len == 0) {
2031                bc_num_setToZero(c, scale);
2032                RETURN_STATUS(BC_STATUS_SUCCESS);
2033        }
2034        if (BC_NUM_ONE(b)) {
2035                bc_num_copy(c, a);
2036                bc_num_retireMul(c, scale, a->neg, b->neg);
2037                RETURN_STATUS(BC_STATUS_SUCCESS);
2038        }
2039
2040        bc_num_init(&cp, BC_NUM_MREQ(a, b, scale));
2041        bc_num_copy(&cp, a);
2042        len = b->len;
2043
2044        if (len > cp.len) {
2045                bc_num_expand(&cp, len + 2);
2046                bc_num_extend(&cp, len - cp.len);
2047        }
2048
2049        if (b->rdx > cp.rdx) bc_num_extend(&cp, b->rdx - cp.rdx);
2050        cp.rdx -= b->rdx;
2051        if (scale > cp.rdx) bc_num_extend(&cp, scale - cp.rdx);
2052
2053        if (b->rdx == b->len) {
2054                for (;;) {
2055                        if (len == 0) break;
2056                        len--;
2057                        if (b->num[len] != 0)
2058                                break;
2059                }
2060                len++;
2061        }
2062
2063        if (cp.cap == cp.len) bc_num_expand(&cp, cp.len + 1);
2064
2065        // We want an extra zero in front to make things simpler.
2066        cp.num[cp.len++] = 0;
2067        end = cp.len - len;
2068
2069        bc_num_expand(c, cp.len);
2070
2071        bc_num_zero(c);
2072        memset(c->num + end, 0, (c->cap - end) * sizeof(BcDig));
2073        c->rdx = cp.rdx;
2074        c->len = cp.len;
2075
2076        s = BC_STATUS_SUCCESS;
2077        for (i = end - 1; i < end; --i) {
2078                BcDig *n, q;
2079                n = cp.num + i;
2080                for (q = 0; n[len] != 0 || bc_num_compare(n, b->num, len) >= 0; ++q)
2081                        bc_num_subArrays(n, b->num, len);
2082                c->num[i] = q;
2083#if ENABLE_FEATURE_BC_INTERACTIVE
2084                // a=2^100000
2085                // scale=40000
2086                // 1/a <- without check below, this will not be interruptible
2087                if (G_interrupt) {
2088                        s = BC_STATUS_FAILURE;
2089                        break;
2090                }
2091#endif
2092        }
2093
2094        bc_num_retireMul(c, scale, a->neg, b->neg);
2095        bc_num_free(&cp);
2096
2097        RETURN_STATUS(s);
2098}
2099#define zbc_num_d(...) (zbc_num_d(__VA_ARGS__) COMMA_SUCCESS)
2100
2101static FAST_FUNC BC_STATUS zbc_num_r(BcNum *a, BcNum *b, BcNum *restrict c,
2102                         BcNum *restrict d, size_t scale, size_t ts)
2103{
2104        BcStatus s;
2105        BcNum temp;
2106        bool neg;
2107
2108        if (b->len == 0)
2109                RETURN_STATUS(bc_error("divide by zero"));
2110
2111        if (a->len == 0) {
2112                bc_num_setToZero(d, ts);
2113                RETURN_STATUS(BC_STATUS_SUCCESS);
2114        }
2115
2116        bc_num_init(&temp, d->cap);
2117        s = zbc_num_d(a, b, c, scale);
2118        if (s) goto err;
2119
2120        if (scale != 0) scale = ts;
2121
2122        s = zbc_num_m(c, b, &temp, scale);
2123        if (s) goto err;
2124        s = zbc_num_sub(a, &temp, d, scale);
2125        if (s) goto err;
2126
2127        if (ts > d->rdx && d->len) bc_num_extend(d, ts - d->rdx);
2128
2129        neg = d->neg;
2130        bc_num_retireMul(d, ts, a->neg, b->neg);
2131        d->neg = neg;
2132 err:
2133        bc_num_free(&temp);
2134        RETURN_STATUS(s);
2135}
2136#define zbc_num_r(...) (zbc_num_r(__VA_ARGS__) COMMA_SUCCESS)
2137
2138static FAST_FUNC BC_STATUS zbc_num_rem(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale)
2139{
2140        BcStatus s;
2141        BcNum c1;
2142        size_t ts = BC_MAX(scale + b->rdx, a->rdx), len = BC_NUM_MREQ(a, b, ts);
2143
2144        bc_num_init(&c1, len);
2145        s = zbc_num_r(a, b, &c1, c, scale, ts);
2146        bc_num_free(&c1);
2147
2148        RETURN_STATUS(s);
2149}
2150#define zbc_num_rem(...) (zbc_num_rem(__VA_ARGS__) COMMA_SUCCESS)
2151
2152static FAST_FUNC BC_STATUS zbc_num_p(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale)
2153{
2154        BcStatus s = BC_STATUS_SUCCESS;
2155        BcNum copy;
2156        unsigned long pow;
2157        size_t i, powrdx, resrdx;
2158        size_t a_rdx;
2159        bool neg;
2160
2161        // GNU bc does not allow 2^2.0 - we do
2162        for (i = 0; i < b->rdx; i++)
2163                if (b->num[i] != 0)
2164                        RETURN_STATUS(bc_error("not an integer"));
2165
2166// a^b for non-integer b (for a>0) can be implemented as exp(ln(a)*b).
2167// Possibly better precision would be given by a^int(b) * exp(ln(a)*frac(b)).
2168
2169        if (b->len == 0) {
2170                bc_num_one(c);
2171                RETURN_STATUS(BC_STATUS_SUCCESS);
2172        }
2173        if (a->len == 0) {
2174                bc_num_setToZero(c, scale);
2175                RETURN_STATUS(BC_STATUS_SUCCESS);
2176        }
2177        if (BC_NUM_ONE(b)) {
2178                if (!b->neg)
2179                        bc_num_copy(c, a);
2180                else
2181                        s = zbc_num_inv(a, c, scale);
2182                RETURN_STATUS(s);
2183        }
2184
2185        neg = b->neg;
2186        s = zbc_num_ulong_abs(b, &pow);
2187        if (s) RETURN_STATUS(s);
2188        // b is not used beyond this point
2189
2190        bc_num_init_and_copy(&copy, a);
2191        a_rdx = a->rdx; // pull it into a CPU register (hopefully)
2192        // a is not used beyond this point
2193
2194        if (!neg) {
2195                unsigned long new_scale;
2196                if (a_rdx > scale)
2197                        scale = a_rdx;
2198                new_scale = a_rdx * pow;
2199                // Don't fall for multiplication overflow. Example:
2200                // 0.01^2147483648 a_rdx:2 pow:0x80000000, 32bit mul is 0.
2201//not that it matters with current algorithm, it would OOM on such large powers,
2202//but it can be improved to detect zero results etc. Example: with scale=0,
2203//result of 0.01^N for any N>1 is 0: 0.01^2 = 0.0001 ~= 0.00 (trunc to scale)
2204//then this would matter:
2205                // if a_rdx != 0 and new_scale < pow, we had overflow,
2206                // correct "new_scale" value is larger than ULONG_MAX,
2207                // thus larger than any possible current value of "scale",
2208                // thus "scale = new_scale" should not be done:
2209                if (a_rdx == 0 || new_scale >= pow)
2210                        if (new_scale < scale)
2211                                scale = new_scale;
2212        }
2213
2214        for (powrdx = a_rdx; !(pow & 1); pow >>= 1) {
2215                powrdx <<= 1;
2216                s = zbc_num_mul(&copy, &copy, &copy, powrdx);
2217                if (s) goto err;
2218                // Not needed: zbc_num_mul() has a check for ^C:
2219                //if (G_interrupt) {
2220                //      s = BC_STATUS_FAILURE;
2221                //      goto err;
2222                //}
2223        }
2224
2225        bc_num_copy(c, &copy);
2226
2227        for (resrdx = powrdx, pow >>= 1; pow != 0; pow >>= 1) {
2228                powrdx <<= 1;
2229                s = zbc_num_mul(&copy, &copy, &copy, powrdx);
2230                if (s) goto err;
2231
2232                if (pow & 1) {
2233                        resrdx += powrdx;
2234                        s = zbc_num_mul(c, &copy, c, resrdx);
2235                        if (s) goto err;
2236                }
2237                // Not needed: zbc_num_mul() has a check for ^C:
2238                //if (G_interrupt) {
2239                //      s = BC_STATUS_FAILURE;
2240                //      goto err;
2241                //}
2242        }
2243
2244        if (neg) {
2245                s = zbc_num_inv(c, c, scale);
2246                if (s) goto err;
2247        }
2248
2249        if (c->rdx > scale) bc_num_truncate(c, c->rdx - scale);
2250
2251        // We can't use bc_num_clean() here.
2252        for (i = 0; i < c->len; ++i)
2253                if (c->num[i] != 0)
2254                        goto skip;
2255        bc_num_setToZero(c, scale);
2256 skip:
2257
2258 err:
2259        bc_num_free(&copy);
2260        RETURN_STATUS(s);
2261}
2262#define zbc_num_p(...) (zbc_num_p(__VA_ARGS__) COMMA_SUCCESS)
2263
2264static NOINLINE BC_STATUS zbc_num_sqrt(BcNum *a, BcNum *restrict b, size_t scale)
2265{
2266        BcStatus s;
2267        BcNum num1, num2, half, f, fprime, *x0, *x1, *temp;
2268        BcDig half_digs[1];
2269        size_t pow, len, digs, digs1, resrdx, req, times;
2270        ssize_t cmp, cmp1, cmp2;
2271
2272        req = BC_MAX(scale, a->rdx) + ((BC_NUM_INT(a) + 1) >> 1) + 1;
2273        bc_num_expand(b, req);
2274
2275        if (a->len == 0) {
2276                bc_num_setToZero(b, scale);
2277                RETURN_STATUS(BC_STATUS_SUCCESS);
2278        }
2279        if (a->neg) {
2280                RETURN_STATUS(bc_error("negative number"));
2281        }
2282        if (BC_NUM_ONE(a)) {
2283                bc_num_one(b);
2284                bc_num_extend(b, scale);
2285                RETURN_STATUS(BC_STATUS_SUCCESS);
2286        }
2287
2288        scale = BC_MAX(scale, a->rdx) + 1;
2289        len = a->len + scale;
2290
2291        bc_num_init(&num1, len);
2292        bc_num_init(&num2, len);
2293
2294        half.cap = ARRAY_SIZE(half_digs);
2295        half.num = half_digs;
2296        bc_num_one(&half);
2297        half_digs[0] = 5;
2298        half.rdx = 1;
2299
2300        bc_num_init(&f, len);
2301        bc_num_init(&fprime, len);
2302
2303        x0 = &num1;
2304        x1 = &num2;
2305
2306        bc_num_one(x0);
2307        pow = BC_NUM_INT(a);
2308
2309        if (pow) {
2310                if (pow & 1)
2311                        x0->num[0] = 2;
2312                else
2313                        x0->num[0] = 6;
2314
2315                pow -= 2 - (pow & 1);
2316
2317                bc_num_extend(x0, pow);
2318
2319                // Make sure to move the radix back.
2320                x0->rdx -= pow;
2321        }
2322
2323        x0->rdx = digs = digs1 = times = 0;
2324        resrdx = scale + 2;
2325        len = x0->len + resrdx - 1;
2326        cmp = 1;
2327        cmp1 = cmp2 = SSIZE_MAX;
2328        do {
2329                s = zbc_num_div(a, x0, &f, resrdx);
2330                if (s) goto err;
2331                s = zbc_num_add(x0, &f, &fprime, resrdx);
2332                if (s) goto err;
2333                s = zbc_num_mul(&fprime, &half, x1, resrdx);
2334                if (s) goto err;
2335
2336                cmp = bc_num_cmp(x1, x0);
2337                digs = x1->len - (unsigned long long) llabs(cmp);
2338
2339                if (cmp == cmp2 && digs == digs1)
2340                        times += 1;
2341                else
2342                        times = 0;
2343
2344                resrdx += times > 4;
2345
2346                cmp2 = cmp1;
2347                cmp1 = cmp;
2348                digs1 = digs;
2349
2350                temp = x0;
2351                x0 = x1;
2352                x1 = temp;
2353        } while (cmp != 0 || digs < len);
2354
2355        bc_num_copy(b, x0);
2356        scale -= 1;
2357        if (b->rdx > scale)
2358                bc_num_truncate(b, b->rdx - scale);
2359 err:
2360        bc_num_free(&fprime);
2361        bc_num_free(&f);
2362        bc_num_free(&num2);
2363        bc_num_free(&num1);
2364        RETURN_STATUS(s);
2365}
2366#define zbc_num_sqrt(...) (zbc_num_sqrt(__VA_ARGS__) COMMA_SUCCESS)
2367
2368static BC_STATUS zbc_num_divmod(BcNum *a, BcNum *b, BcNum *c, BcNum *d,
2369                              size_t scale)
2370{
2371        BcStatus s;
2372        BcNum num2, *ptr_a;
2373        bool init = false;
2374        size_t ts = BC_MAX(scale + b->rdx, a->rdx), len = BC_NUM_MREQ(a, b, ts);
2375
2376        if (c == a) {
2377                memcpy(&num2, c, sizeof(BcNum));
2378                ptr_a = &num2;
2379                bc_num_init(c, len);
2380                init = true;
2381        } else {
2382                ptr_a = a;
2383                bc_num_expand(c, len);
2384        }
2385
2386        s = zbc_num_r(ptr_a, b, c, d, scale, ts);
2387
2388        if (init) bc_num_free(&num2);
2389
2390        RETURN_STATUS(s);
2391}
2392#define zbc_num_divmod(...) (zbc_num_divmod(__VA_ARGS__) COMMA_SUCCESS)
2393
2394#if ENABLE_DC
2395static BC_STATUS zdc_num_modexp(BcNum *a, BcNum *b, BcNum *c, BcNum *restrict d)
2396{
2397        BcStatus s;
2398        BcNum base, exp, two, temp;
2399        BcDig two_digs[1];
2400
2401        if (c->len == 0)
2402                RETURN_STATUS(bc_error("divide by zero"));
2403        if (a->rdx || b->rdx || c->rdx)
2404                RETURN_STATUS(bc_error("not an integer"));
2405        if (b->neg)
2406                RETURN_STATUS(bc_error("negative number"));
2407
2408        bc_num_expand(d, c->len);
2409        bc_num_init(&base, c->len);
2410        bc_num_init(&exp, b->len);
2411        bc_num_init(&temp, b->len);
2412
2413        two.cap = ARRAY_SIZE(two_digs);
2414        two.num = two_digs;
2415        bc_num_one(&two);
2416        two_digs[0] = 2;
2417
2418        bc_num_one(d);
2419
2420        s = zbc_num_rem(a, c, &base, 0);
2421        if (s) goto err;
2422        bc_num_copy(&exp, b);
2423
2424        while (exp.len != 0) {
2425                s = zbc_num_divmod(&exp, &two, &exp, &temp, 0);
2426                if (s) goto err;
2427
2428                if (BC_NUM_ONE(&temp)) {
2429                        s = zbc_num_mul(d, &base, &temp, 0);
2430                        if (s) goto err;
2431                        s = zbc_num_rem(&temp, c, d, 0);
2432                        if (s) goto err;
2433                }
2434
2435                s = zbc_num_mul(&base, &base, &temp, 0);
2436                if (s) goto err;
2437                s = zbc_num_rem(&temp, c, &base, 0);
2438                if (s) goto err;
2439        }
2440 err:
2441        bc_num_free(&temp);
2442        bc_num_free(&exp);
2443        bc_num_free(&base);
2444        RETURN_STATUS(s);
2445}
2446#define zdc_num_modexp(...) (zdc_num_modexp(__VA_ARGS__) COMMA_SUCCESS)
2447#endif // ENABLE_DC
2448
2449static FAST_FUNC void bc_string_free(void *string)
2450{
2451        free(*(char**)string);
2452}
2453
2454static void bc_func_init(BcFunc *f)
2455{
2456        bc_char_vec_init(&f->code);
2457        IF_BC(bc_vec_init(&f->labels, sizeof(size_t), NULL);)
2458        IF_BC(bc_vec_init(&f->autos, sizeof(BcId), bc_id_free);)
2459        IF_BC(bc_vec_init(&f->strs, sizeof(char *), bc_string_free);)
2460        IF_BC(bc_vec_init(&f->consts, sizeof(char *), bc_string_free);)
2461        IF_BC(f->nparams = 0;)
2462}
2463
2464static FAST_FUNC void bc_func_free(void *func)
2465{
2466        BcFunc *f = (BcFunc *) func;
2467        bc_vec_free(&f->code);
2468        IF_BC(bc_vec_free(&f->labels);)
2469        IF_BC(bc_vec_free(&f->autos);)
2470        IF_BC(bc_vec_free(&f->strs);)
2471        IF_BC(bc_vec_free(&f->consts);)
2472}
2473
2474static void bc_array_expand(BcVec *a, size_t len);
2475
2476static void bc_array_init(BcVec *a, bool nums)
2477{
2478        if (nums)
2479                bc_vec_init(a, sizeof(BcNum), bc_num_free);
2480        else
2481                bc_vec_init(a, sizeof(BcVec), bc_vec_free);
2482        bc_array_expand(a, 1);
2483}
2484
2485static void bc_array_expand(BcVec *a, size_t len)
2486{
2487        if (a->dtor == bc_num_free
2488         // && a->size == sizeof(BcNum) - always true
2489        ) {
2490                BcNum n;
2491                while (len > a->len) {
2492                        bc_num_init_DEF_SIZE(&n);
2493                        bc_vec_push(a, &n);
2494                }
2495        } else {
2496                BcVec v;
2497                while (len > a->len) {
2498                        bc_array_init(&v, true);
2499                        bc_vec_push(a, &v);
2500                }
2501        }
2502}
2503
2504static void bc_array_copy(BcVec *d, const BcVec *s)
2505{
2506        BcNum *dnum, *snum;
2507        size_t i;
2508
2509        bc_vec_pop_all(d);
2510        bc_vec_expand(d, s->cap);
2511        d->len = s->len;
2512
2513        dnum = (void*)d->v;
2514        snum = (void*)s->v;
2515        for (i = 0; i < s->len; i++, dnum++, snum++) {
2516                bc_num_init_and_copy(dnum, snum);
2517        }
2518}
2519
2520#if ENABLE_DC
2521static void dc_result_copy(BcResult *d, BcResult *src)
2522{
2523        d->t = src->t;
2524
2525        switch (d->t) {
2526                case XC_RESULT_TEMP:
2527                case XC_RESULT_IBASE:
2528                case XC_RESULT_SCALE:
2529                case XC_RESULT_OBASE:
2530                        bc_num_init_and_copy(&d->d.n, &src->d.n);
2531                        break;
2532                case XC_RESULT_VAR:
2533                case XC_RESULT_ARRAY:
2534                case XC_RESULT_ARRAY_ELEM:
2535                        d->d.id.name = xstrdup(src->d.id.name);
2536                        break;
2537                case XC_RESULT_CONSTANT:
2538                case XC_RESULT_STR:
2539                        memcpy(&d->d.n, &src->d.n, sizeof(BcNum));
2540                        break;
2541                default: // placate compiler
2542                        // BC_RESULT_VOID, BC_RESULT_LAST, BC_RESULT_ONE - do not happen
2543                        break;
2544        }
2545}
2546#endif // ENABLE_DC
2547
2548static FAST_FUNC void bc_result_free(void *result)
2549{
2550        BcResult *r = (BcResult *) result;
2551
2552        switch (r->t) {
2553                case XC_RESULT_TEMP:
2554                IF_BC(case BC_RESULT_VOID:)
2555                case XC_RESULT_IBASE:
2556                case XC_RESULT_SCALE:
2557                case XC_RESULT_OBASE:
2558                        bc_num_free(&r->d.n);
2559                        break;
2560                case XC_RESULT_VAR:
2561                case XC_RESULT_ARRAY:
2562                case XC_RESULT_ARRAY_ELEM:
2563                        free(r->d.id.name);
2564                        break;
2565                default:
2566                        // Do nothing.
2567                        break;
2568        }
2569}
2570
2571static int bad_input_byte(char c)
2572{
2573        if ((c < ' ' && c != '\t' && c != '\r' && c != '\n') // also allow '\v' '\f'?
2574         || c > 0x7e
2575        ) {
2576                bc_error_fmt("illegal character 0x%02x", c);
2577                return 1;
2578        }
2579        return 0;
2580}
2581
2582static void xc_read_line(BcVec *vec, FILE *fp)
2583{
2584 again:
2585        bc_vec_pop_all(vec);
2586        fflush_and_check();
2587
2588#if ENABLE_FEATURE_BC_INTERACTIVE
2589        if (G_interrupt) { // ^C was pressed
2590                if (fp != stdin) {
2591                        // ^C while running a script (bc SCRIPT): die.
2592                        // We do not return to interactive prompt:
2593                        // user might be running us from a shell,
2594                        // and SCRIPT might be intended to terminate
2595                        // (e.g. contain a "halt" stmt).
2596                        // ^C dropping user into a bc prompt instead of
2597                        // the shell would be unexpected.
2598                        xfunc_die();
2599                }
2600                // There was ^C while running calculations
2601                G_interrupt = 0;
2602                // GNU bc says "interrupted execution." (to stdout, not stderr)
2603                // GNU dc says "Interrupt!"
2604                puts("\ninterrupted execution");
2605        }
2606
2607# if ENABLE_FEATURE_EDITING
2608        if (G_ttyin && fp == stdin) {
2609                int n, i;
2610                if (!G.line_input_state)
2611                        G.line_input_state = new_line_input_t(DO_HISTORY);
2612#  define line_buf bb_common_bufsiz1
2613                n = read_line_input(G.line_input_state, "", line_buf, COMMON_BUFSIZE);
2614                if (n <= 0) { // read errors or EOF, or ^D, or ^C
2615                        //GNU bc prints this on ^C:
2616                        //if (n == 0) // ^C
2617                        //      puts("(interrupt) Exiting bc.");
2618                        bc_vec_pushZeroByte(vec);
2619                        return;
2620                }
2621                i = 0;
2622                for (;;) {
2623                        char c = line_buf[i++];
2624                        if (c == '\0') break;
2625                        if (bad_input_byte(c)) goto again;
2626                }
2627                bc_vec_string(vec, n, line_buf);
2628#  undef line_buf
2629        } else
2630# endif
2631#endif
2632        {
2633                int c;
2634                bool bad_chars = 0;
2635
2636                do {
2637 get_char:
2638#if ENABLE_FEATURE_BC_INTERACTIVE
2639                        if (G_interrupt) {
2640                                // ^C was pressed: ignore entire line, get another one
2641                                goto again;
2642                        }
2643#endif
2644                        c = fgetc(fp);
2645                        if (c == '\0')
2646                                goto get_char;
2647                        if (c == EOF) {
2648                                if (ferror(fp))
2649                                        bb_simple_perror_msg_and_die("input error");
2650                                // Note: EOF does not append '\n'
2651                                break;
2652                        }
2653                        bad_chars |= bad_input_byte(c);
2654                        bc_vec_pushByte(vec, (char)c);
2655                } while (c != '\n');
2656
2657                if (bad_chars) {
2658                        // Bad chars on this line
2659                        if (!G.prs.lex_filename) { // stdin
2660                                // ignore entire line, get another one
2661                                goto again;
2662                        }
2663                        bb_perror_msg_and_die("file '%s' is not text", G.prs.lex_filename);
2664                }
2665                bc_vec_pushZeroByte(vec);
2666        }
2667}
2668
2669//
2670// Parsing routines
2671//
2672
2673// "Input numbers may contain the characters 0-9 and A-Z.
2674// (Note: They must be capitals.  Lower case letters are variable names.)
2675// Single digit numbers always have the value of the digit regardless of
2676// the value of ibase. (i.e. A = 10.) For multi-digit numbers, bc changes
2677// all input digits greater or equal to ibase to the value of ibase-1.
2678// This makes the number ZZZ always be the largest 3 digit number of the
2679// input base."
2680static bool xc_num_strValid(const char *val)
2681{
2682        bool radix = false;
2683        for (;;) {
2684                BcDig c = *val++;
2685                if (c == '\0')
2686                        break;
2687                if (c == '.') {
2688                        if (radix) return false;
2689                        radix = true;
2690                        continue;
2691                }
2692                if ((c < '0' || c > '9') && (c < 'A' || c > 'Z'))
2693                        return false;
2694        }
2695        return true;
2696}
2697
2698// Note: n is already "bc_num_zero()"ed,
2699// leading zeroes in "val" are removed
2700static void bc_num_parseDecimal(BcNum *n, const char *val)
2701{
2702        size_t len, i;
2703        const char *ptr;
2704
2705        len = strlen(val);
2706        if (len == 0)
2707                return;
2708
2709        bc_num_expand(n, len + 1); // +1 for e.g. "A" converting into 10
2710
2711        ptr = strchr(val, '.');
2712
2713        n->rdx = 0;
2714        if (ptr != NULL)
2715                n->rdx = (size_t)((val + len) - (ptr + 1));
2716
2717        for (i = 0; val[i]; ++i) {
2718                if (val[i] != '0' && val[i] != '.') {
2719                        // Not entirely zero value - convert it, and exit
2720                        if (len == 1) {
2721                                unsigned c = val[0] - '0';
2722                                n->len = 1;
2723                                if (c > 9) { // A-Z => 10-36
2724                                        n->len = 2;
2725                                        c -= ('A' - '9' - 1);
2726                                        n->num[1] = c/10;
2727                                        c = c%10;
2728                                }
2729                                n->num[0] = c;
2730                                break;
2731                        }
2732                        i = len - 1;
2733                        for (;;) {
2734                                char c = val[i] - '0';
2735                                if (c > 9) // A-Z => 9
2736                                        c = 9;
2737                                n->num[n->len] = c;
2738                                n->len++;
2739 skip_dot:
2740                                if (i == 0) break;
2741                                if (val[--i] == '.') goto skip_dot;
2742                        }
2743                        break;
2744                }
2745        }
2746        // if for() exits without hitting if(), the value is entirely zero
2747}
2748
2749// Note: n is already "bc_num_zero()"ed,
2750// leading zeroes in "val" are removed
2751static void bc_num_parseBase(BcNum *n, const char *val, unsigned base_t)
2752{
2753        BcStatus s;
2754        BcNum mult, result;
2755        BcNum temp;
2756        BcNum base;
2757        BcDig temp_digs[ULONG_NUM_BUFSIZE];
2758        BcDig base_digs[ULONG_NUM_BUFSIZE];
2759        size_t digits;
2760
2761        bc_num_init_DEF_SIZE(&mult);
2762
2763        temp.cap = ARRAY_SIZE(temp_digs);
2764        temp.num = temp_digs;
2765
2766        base.cap = ARRAY_SIZE(base_digs);
2767        base.num = base_digs;
2768        bc_num_ulong2num(&base, base_t);
2769        base_t--;
2770
2771        for (;;) {
2772                unsigned v;
2773                char c;
2774
2775                c = *val++;
2776                if (c == '\0') goto int_err;
2777                if (c == '.') break;
2778
2779                v = (unsigned)(c <= '9' ? c - '0' : c - 'A' + 10);
2780                if (v > base_t) v = base_t;
2781
2782                s = zbc_num_mul(n, &base, &mult, 0);
2783                if (s) goto int_err;
2784                bc_num_ulong2num(&temp, v);
2785                s = zbc_num_add(&mult, &temp, n, 0);
2786                if (s) goto int_err;
2787        }
2788
2789        bc_num_init(&result, base.len);
2790        //bc_num_zero(&result); - already is
2791        bc_num_one(&mult);
2792
2793        digits = 0;
2794        for (;;) {
2795                unsigned v;
2796                char c;
2797
2798                c = *val++;
2799                if (c == '\0') break;
2800                digits++;
2801
2802                v = (unsigned)(c <= '9' ? c - '0' : c - 'A' + 10);
2803                if (v > base_t) v = base_t;
2804
2805                s = zbc_num_mul(&result, &base, &result, 0);
2806                if (s) goto err;
2807                bc_num_ulong2num(&temp, v);
2808                s = zbc_num_add(&result, &temp, &result, 0);
2809                if (s) goto err;
2810                s = zbc_num_mul(&mult, &base, &mult, 0);
2811                if (s) goto err;
2812        }
2813
2814        s = zbc_num_div(&result, &mult, &result, digits);
2815        if (s) goto err;
2816        s = zbc_num_add(n, &result, n, digits);
2817        if (s) goto err;
2818
2819        if (n->len != 0) {
2820                if (n->rdx < digits)
2821                        bc_num_extend(n, digits - n->rdx);
2822        } else
2823                bc_num_zero(n);
2824 err:
2825        bc_num_free(&result);
2826 int_err:
2827        bc_num_free(&mult);
2828}
2829
2830static BC_STATUS zxc_num_parse(BcNum *n, const char *val, unsigned base_t)
2831{
2832        size_t i;
2833
2834        if (!xc_num_strValid(val))
2835                RETURN_STATUS(bc_error("bad number string"));
2836
2837        bc_num_zero(n);
2838        while (*val == '0')
2839                val++;
2840        for (i = 0; ; ++i) {
2841                if (val[i] == '\0')
2842                        RETURN_STATUS(BC_STATUS_SUCCESS);
2843                if (val[i] != '.' && val[i] != '0')
2844                        break;
2845        }
2846
2847        if (base_t == 10 || val[1] == '\0')
2848                // Decimal, or single-digit number
2849                bc_num_parseDecimal(n, val);
2850        else
2851                bc_num_parseBase(n, val, base_t);
2852
2853        RETURN_STATUS(BC_STATUS_SUCCESS);
2854}
2855#define zxc_num_parse(...) (zxc_num_parse(__VA_ARGS__) COMMA_SUCCESS)
2856
2857// p->lex_inbuf points to the current string to be parsed.
2858// if p->lex_inbuf points to '\0', it's either EOF or it points after
2859// last processed line's terminating '\n' (and more reading needs to be done
2860// to get next character).
2861//
2862// If you are in a situation where that is a possibility, call peek_inbuf().
2863// If necessary, it performs more reading and changes p->lex_inbuf,
2864// then it returns *p->lex_inbuf (which will be '\0' only if it's EOF).
2865// After it, just referencing *p->lex_inbuf is valid, and if it wasn't '\0',
2866// it's ok to do p->lex_inbuf++ once without end-of-buffer checking.
2867//
2868// eat_inbuf() is equvalent to "peek_inbuf(); if (c) p->lex_inbuf++":
2869// it returns current char and advances the pointer (if not EOF).
2870// After eat_inbuf(), referencing p->lex_inbuf[-1] and *p->lex_inbuf is valid.
2871//
2872// In many cases, you can use fast *p->lex_inbuf instead of peek_inbuf():
2873// unless prev char might have been '\n', *p->lex_inbuf is '\0' ONLY
2874// on real EOF, not end-of-buffer.
2875//
2876// bc cases to test interactively:
2877// 1 #comment\  - prints "1<newline>" at once (comment is not continued)
2878// 1 #comment/* - prints "1<newline>" at once
2879// 1 #comment"  - prints "1<newline>" at once
2880// 1\#comment   - error at once (\ is not a line continuation)
2881// 1 + /*"*/2   - prints "3<newline>" at once
2882// 1 + /*#*/2   - prints "3<newline>" at once
2883// "str\"       - prints "str\" at once
2884// "str#"       - prints "str#" at once
2885// "str/*"      - prints "str/*" at once
2886// "str#\       - waits for second line
2887// end"         - ...prints "str#\<newline>end"
2888static char peek_inbuf(void)
2889{
2890        if (*G.prs.lex_inbuf == '\0'
2891         && G.prs.lex_input_fp
2892        ) {
2893                xc_read_line(&G.input_buffer, G.prs.lex_input_fp);
2894                G.prs.lex_inbuf = G.input_buffer.v;
2895                if (G.input_buffer.len <= 1) // on EOF, len is 1 (NUL byte)
2896                        G.prs.lex_input_fp = NULL;
2897        }
2898        return *G.prs.lex_inbuf;
2899}
2900static char eat_inbuf(void)
2901{
2902        char c = peek_inbuf();
2903        if (c) G.prs.lex_inbuf++;
2904        return c;
2905}
2906
2907static void xc_lex_lineComment(void)
2908{
2909        BcParse *p = &G.prs;
2910        char c;
2911
2912        // Try: echo -n '#foo' | bc
2913        p->lex = XC_LEX_WHITESPACE;
2914
2915        // Not peek_inbuf(): we depend on input being done in whole lines:
2916        // '\0' which isn't the EOF can only be seen after '\n'.
2917        while ((c = *p->lex_inbuf) != '\n' && c != '\0')
2918                p->lex_inbuf++;
2919}
2920
2921static void xc_lex_whitespace(void)
2922{
2923        BcParse *p = &G.prs;
2924
2925        p->lex = XC_LEX_WHITESPACE;
2926        for (;;) {
2927                // We depend here on input being done in whole lines:
2928                // '\0' which isn't the EOF can only be seen after '\n'.
2929                char c = *p->lex_inbuf;
2930                if (c == '\n') // this is XC_LEX_NLINE, not XC_LEX_WHITESPACE
2931                        break;
2932                if (!isspace(c))
2933                        break;
2934                p->lex_inbuf++;
2935        }
2936}
2937
2938static BC_STATUS zxc_lex_number(char last)
2939{
2940        BcParse *p = &G.prs;
2941        bool pt;
2942        char last_valid_ch;
2943
2944        bc_vec_pop_all(&p->lex_strnumbuf);
2945        bc_vec_pushByte(&p->lex_strnumbuf, last);
2946
2947// bc: "Input numbers may contain the characters 0-9 and A-Z.
2948// (Note: They must be capitals.  Lower case letters are variable names.)
2949// Single digit numbers always have the value of the digit regardless of
2950// the value of ibase. (i.e. A = 10.) For multi-digit numbers, bc changes
2951// all input digits greater or equal to ibase to the value of ibase-1.
2952// This makes the number ZZZ always be the largest 3 digit number of the
2953// input base."
2954// dc only allows A-F, the rules about single-char and multi-char are the same.
2955        last_valid_ch = (IS_BC ? 'Z' : 'F');
2956        pt = (last == '.');
2957        p->lex = XC_LEX_NUMBER;
2958        for (;;) {
2959                // We depend here on input being done in whole lines:
2960                // '\0' which isn't the EOF can only be seen after '\n'.
2961                char c = *p->lex_inbuf;
2962 check_c:
2963                if (c == '\0')
2964                        break;
2965                if (c == '\\' && p->lex_inbuf[1] == '\n') {
2966                        p->lex_inbuf += 2;
2967                        p->lex_line++;
2968                        dbg_lex("++p->lex_line=%zd", p->lex_line);
2969                        c = peek_inbuf(); // force next line to be read
2970                        goto check_c;
2971                }
2972                if (!isdigit(c) && (c < 'A' || c > last_valid_ch)) {
2973                        if (c != '.') break;
2974                        // if '.' was already seen, stop on second one:
2975                        if (pt) break;
2976                        pt = true;
2977                }
2978                // c is one of "0-9A-Z."
2979                last = c;
2980                bc_vec_push(&p->lex_strnumbuf, p->lex_inbuf);
2981                p->lex_inbuf++;
2982        }
2983        if (last == '.') // remove trailing '.' if any
2984                bc_vec_pop(&p->lex_strnumbuf);
2985        bc_vec_pushZeroByte(&p->lex_strnumbuf);
2986
2987        G.err_line = G.prs.lex_line;
2988        RETURN_STATUS(BC_STATUS_SUCCESS);
2989}
2990#define zxc_lex_number(...) (zxc_lex_number(__VA_ARGS__) COMMA_SUCCESS)
2991
2992static void xc_lex_name(void)
2993{
2994        BcParse *p = &G.prs;
2995        size_t i;
2996        const char *buf;
2997
2998        p->lex = XC_LEX_NAME;
2999
3000        // Since names can't cross lines with \<newline>,
3001        // we depend on the fact that whole line is in the buffer
3002        i = 0;
3003        buf = p->lex_inbuf - 1;
3004        for (;;) {
3005                char c = buf[i];
3006                if ((c < 'a' || c > 'z') && !isdigit(c) && c != '_') break;
3007                i++;
3008        }
3009
3010#if 0 // We do not protect against people with gigabyte-long names
3011        // This check makes sense only if size_t is (much) larger than BC_MAX_STRING.
3012        if (SIZE_MAX > (BC_MAX_STRING | 0xff)) {
3013                if (i > BC_MAX_STRING)
3014                        return bc_error("name too long: must be [1,"BC_MAX_STRING_STR"]");
3015        }
3016#endif
3017        bc_vec_string(&p->lex_strnumbuf, i, buf);
3018
3019        // Increment the index. We minus 1 because it has already been incremented.
3020        p->lex_inbuf += i - 1;
3021
3022        //return BC_STATUS_SUCCESS;
3023}
3024
3025IF_BC(static BC_STATUS zbc_lex_token(void);)
3026IF_DC(static BC_STATUS zdc_lex_token(void);)
3027#define zbc_lex_token(...) (zbc_lex_token(__VA_ARGS__) COMMA_SUCCESS)
3028#define zdc_lex_token(...) (zdc_lex_token(__VA_ARGS__) COMMA_SUCCESS)
3029
3030static BC_STATUS zxc_lex_next(void)
3031{
3032        BcParse *p = &G.prs;
3033        BcStatus s;
3034
3035        G.err_line = p->lex_line;
3036        p->lex_last = p->lex;
3037//why?
3038//      if (p->lex_last == XC_LEX_EOF)
3039//              RETURN_STATUS(bc_error("end of file"));
3040
3041        // Loop until failure or we don't have whitespace. This
3042        // is so the parser doesn't get inundated with whitespace.
3043        // Comments are also XC_LEX_WHITESPACE tokens and eaten here.
3044        s = BC_STATUS_SUCCESS;
3045        do {
3046                if (*p->lex_inbuf == '\0') {
3047                        p->lex = XC_LEX_EOF;
3048                        if (peek_inbuf() == '\0')
3049                                RETURN_STATUS(BC_STATUS_SUCCESS);
3050                }
3051                p->lex_next_at = p->lex_inbuf;
3052                dbg_lex("next string to parse:'%.*s'",
3053                        (int)(strchrnul(p->lex_next_at, '\n') - p->lex_next_at),
3054                        p->lex_next_at
3055                );
3056                if (IS_BC) {
3057                        IF_BC(s = zbc_lex_token());
3058                } else {
3059                        IF_DC(s = zdc_lex_token());
3060                }
3061        } while (!s && p->lex == XC_LEX_WHITESPACE);
3062        dbg_lex("p->lex from string:%d", p->lex);
3063
3064        RETURN_STATUS(s);
3065}
3066#define zxc_lex_next(...) (zxc_lex_next(__VA_ARGS__) COMMA_SUCCESS)
3067
3068#if ENABLE_BC
3069static BC_STATUS zbc_lex_skip_if_at_NLINE(void)
3070{
3071        if (G.prs.lex == XC_LEX_NLINE)
3072                RETURN_STATUS(zxc_lex_next());
3073        RETURN_STATUS(BC_STATUS_SUCCESS);
3074}
3075#define zbc_lex_skip_if_at_NLINE(...) (zbc_lex_skip_if_at_NLINE(__VA_ARGS__) COMMA_SUCCESS)
3076
3077static BC_STATUS zbc_lex_next_and_skip_NLINE(void)
3078{
3079        BcStatus s;
3080        s = zxc_lex_next();
3081        if (s) RETURN_STATUS(s);
3082        // if(cond)<newline>stmt is accepted too (but not 2+ newlines)
3083        s = zbc_lex_skip_if_at_NLINE();
3084        RETURN_STATUS(s);
3085}
3086#define zbc_lex_next_and_skip_NLINE(...) (zbc_lex_next_and_skip_NLINE(__VA_ARGS__) COMMA_SUCCESS)
3087
3088static BC_STATUS zbc_lex_identifier(void)
3089{
3090        BcParse *p = &G.prs;
3091        BcStatus s;
3092        unsigned i;
3093        const char *buf = p->lex_inbuf - 1;
3094
3095        for (i = 0; i < ARRAY_SIZE(bc_lex_kws); ++i) {
3096                const char *keyword8 = bc_lex_kws[i].name8;
3097                unsigned j = 0;
3098                while (buf[j] != '\0' && buf[j] == keyword8[j]) {
3099                        j++;
3100                        if (j == 8) goto match;
3101                }
3102                if (keyword8[j] != '\0')
3103                        continue;
3104 match:
3105                // buf starts with keyword bc_lex_kws[i]
3106                if (isalnum(buf[j]) || buf[j]=='_')
3107                        continue; // "ifz" does not match "if" keyword, "if." does
3108                p->lex = BC_LEX_KEY_1st_keyword + i;
3109                if (!keyword_is_POSIX(i)) {
3110                        s = zbc_posix_error_fmt("%sthe '%.8s' keyword", "POSIX does not allow ", bc_lex_kws[i].name8);
3111                        if (s) RETURN_STATUS(s);
3112                }
3113
3114                // We minus 1 because the index has already been incremented.
3115                p->lex_inbuf += j - 1;
3116                RETURN_STATUS(BC_STATUS_SUCCESS);
3117        }
3118
3119        xc_lex_name();
3120        s = BC_STATUS_SUCCESS;
3121
3122        if (p->lex_strnumbuf.len > 2) {
3123                // Prevent this:
3124                // >>> qwe=1
3125                // bc: POSIX only allows one character names; this is bad: 'qwe=1
3126                // '
3127                unsigned len = strchrnul(buf, '\n') - buf;
3128                s = zbc_posix_error_fmt("POSIX only allows one character names; this is bad: '%.*s'", len, buf);
3129        }
3130
3131        RETURN_STATUS(s);
3132}
3133#define zbc_lex_identifier(...) (zbc_lex_identifier(__VA_ARGS__) COMMA_SUCCESS)
3134
3135static BC_STATUS zbc_lex_string(void)
3136{
3137        BcParse *p = &G.prs;
3138
3139        p->lex = XC_LEX_STR;
3140        bc_vec_pop_all(&p->lex_strnumbuf);
3141        for (;;) {
3142                char c = peek_inbuf(); // strings can cross lines
3143                if (c == '\0') {
3144                        RETURN_STATUS(bc_error("unterminated string"));
3145                }
3146                if (c == '"')
3147                        break;
3148                if (c == '\n') {
3149                        p->lex_line++;
3150                        dbg_lex("++p->lex_line=%zd", p->lex_line);
3151                }
3152                bc_vec_push(&p->lex_strnumbuf, p->lex_inbuf);
3153                p->lex_inbuf++;
3154        }
3155        bc_vec_pushZeroByte(&p->lex_strnumbuf);
3156        p->lex_inbuf++;
3157
3158        G.err_line = p->lex_line;
3159        RETURN_STATUS(BC_STATUS_SUCCESS);
3160}
3161#define zbc_lex_string(...) (zbc_lex_string(__VA_ARGS__) COMMA_SUCCESS)
3162
3163static void parse_lex_by_checking_eq_sign(unsigned with_and_without)
3164{
3165        BcParse *p = &G.prs;
3166        if (*p->lex_inbuf == '=') {
3167                // ^^^ not using peek_inbuf() since '==' etc can't be split across lines
3168                p->lex_inbuf++;
3169                with_and_without >>= 8; // store "with" value
3170        } // else store "without" value
3171        p->lex = (with_and_without & 0xff);
3172}
3173#define parse_lex_by_checking_eq_sign(with, without) \
3174        parse_lex_by_checking_eq_sign(((with)<<8)|(without))
3175
3176static BC_STATUS zbc_lex_comment(void)
3177{
3178        BcParse *p = &G.prs;
3179
3180        p->lex = XC_LEX_WHITESPACE;
3181        // here lex_inbuf is at '*' of opening comment delimiter
3182        for (;;) {
3183                char c;
3184
3185                p->lex_inbuf++;
3186                c = peek_inbuf();
3187 check_star:
3188                if (c == '*') {
3189                        p->lex_inbuf++;
3190                        c = *p->lex_inbuf; // no need to peek_inbuf()
3191                        if (c == '/')
3192                                break;
3193                        goto check_star;
3194                }
3195                if (c == '\0') {
3196                        RETURN_STATUS(bc_error("unterminated comment"));
3197                }
3198                if (c == '\n') {
3199                        p->lex_line++;
3200                        dbg_lex("++p->lex_line=%zd", p->lex_line);
3201                }
3202        }
3203        p->lex_inbuf++; // skip trailing '/'
3204
3205        G.err_line = p->lex_line;
3206        RETURN_STATUS(BC_STATUS_SUCCESS);
3207}
3208#define zbc_lex_comment(...) (zbc_lex_comment(__VA_ARGS__) COMMA_SUCCESS)
3209
3210#undef zbc_lex_token
3211static BC_STATUS zbc_lex_token(void)
3212{
3213        BcParse *p = &G.prs;
3214        BcStatus s = BC_STATUS_SUCCESS;
3215        char c = eat_inbuf();
3216        char c2;
3217
3218        // This is the workhorse of the lexer.
3219        switch (c) {
3220//      case '\0': // probably never reached
3221//              p->lex_inbuf--;
3222//              p->lex = XC_LEX_EOF;
3223//              break;
3224        case '\n':
3225                p->lex_line++;
3226                dbg_lex("++p->lex_line=%zd", p->lex_line);
3227                p->lex = XC_LEX_NLINE;
3228                break;
3229        case '\t':
3230        case '\v':
3231        case '\f':
3232        case '\r':
3233        case ' ':
3234                xc_lex_whitespace();
3235                break;
3236        case '!':
3237                parse_lex_by_checking_eq_sign(XC_LEX_OP_REL_NE, BC_LEX_OP_BOOL_NOT);
3238                if (p->lex == BC_LEX_OP_BOOL_NOT) {
3239                        s = zbc_POSIX_does_not_allow_bool_ops_this_is_bad("!");
3240                        if (s) RETURN_STATUS(s);
3241                }
3242                break;
3243        case '"':
3244                s = zbc_lex_string();
3245                break;
3246        case '#':
3247                s = zbc_POSIX_does_not_allow("'#' script comments");
3248                if (s) RETURN_STATUS(s);
3249                xc_lex_lineComment();
3250                break;
3251        case '%':
3252                parse_lex_by_checking_eq_sign(BC_LEX_OP_ASSIGN_MODULUS, XC_LEX_OP_MODULUS);
3253                break;
3254        case '&':
3255                c2 = *p->lex_inbuf;
3256                if (c2 == '&') {
3257                        s = zbc_POSIX_does_not_allow_bool_ops_this_is_bad("&&");
3258                        if (s) RETURN_STATUS(s);
3259                        p->lex_inbuf++;
3260                        p->lex = BC_LEX_OP_BOOL_AND;
3261                } else {
3262                        p->lex = XC_LEX_INVALID;
3263                        s = bc_error_bad_character('&');
3264                }
3265                break;
3266        case '(':
3267        case ')':
3268                p->lex = (BcLexType)(c - '(' + BC_LEX_LPAREN);
3269                break;
3270        case '*':
3271                parse_lex_by_checking_eq_sign(BC_LEX_OP_ASSIGN_MULTIPLY, XC_LEX_OP_MULTIPLY);
3272                break;
3273        case '+':
3274                c2 = *p->lex_inbuf;
3275                if (c2 == '+') {
3276                        p->lex_inbuf++;
3277                        p->lex = BC_LEX_OP_INC;
3278                } else
3279                        parse_lex_by_checking_eq_sign(BC_LEX_OP_ASSIGN_PLUS, XC_LEX_OP_PLUS);
3280                break;
3281        case ',':
3282                p->lex = BC_LEX_COMMA;
3283                break;
3284        case '-':
3285                c2 = *p->lex_inbuf;
3286                if (c2 == '-') {
3287                        p->lex_inbuf++;
3288                        p->lex = BC_LEX_OP_DEC;
3289                } else
3290                        parse_lex_by_checking_eq_sign(BC_LEX_OP_ASSIGN_MINUS, XC_LEX_OP_MINUS);
3291                break;
3292        case '.':
3293                if (isdigit(*p->lex_inbuf))
3294                        s = zxc_lex_number(c);
3295                else {
3296                        p->lex = BC_LEX_KEY_LAST;
3297                        s = zbc_POSIX_does_not_allow("'.' as 'last'");
3298                }
3299                break;
3300        case '/':
3301                c2 = *p->lex_inbuf;
3302                if (c2 == '*')
3303                        s = zbc_lex_comment();
3304                else
3305                        parse_lex_by_checking_eq_sign(BC_LEX_OP_ASSIGN_DIVIDE, XC_LEX_OP_DIVIDE);
3306                break;
3307        case '0':
3308        case '1':
3309        case '2':
3310        case '3':
3311        case '4':
3312        case '5':
3313        case '6':
3314        case '7':
3315        case '8':
3316        case '9':
3317        case 'A':
3318        case 'B':
3319        case 'C':
3320        case 'D':
3321        case 'E':
3322        case 'F':
3323        case 'G':
3324        case 'H':
3325        case 'I':
3326        case 'J':
3327        case 'K':
3328        case 'L':
3329        case 'M':
3330        case 'N':
3331        case 'O':
3332        case 'P':
3333        case 'Q':
3334        case 'R':
3335        case 'S':
3336        case 'T':
3337        case 'U':
3338        case 'V':
3339        case 'W':
3340        case 'X':
3341        case 'Y':
3342        case 'Z':
3343                s = zxc_lex_number(c);
3344                break;
3345        case ';':
3346                p->lex = BC_LEX_SCOLON;
3347                break;
3348        case '<':
3349                parse_lex_by_checking_eq_sign(XC_LEX_OP_REL_LE, XC_LEX_OP_REL_LT);
3350                break;
3351        case '=':
3352                parse_lex_by_checking_eq_sign(XC_LEX_OP_REL_EQ, BC_LEX_OP_ASSIGN);
3353                break;
3354        case '>':
3355                parse_lex_by_checking_eq_sign(XC_LEX_OP_REL_GE, XC_LEX_OP_REL_GT);
3356                break;
3357        case '[':
3358        case ']':
3359                p->lex = (BcLexType)(c - '[' + BC_LEX_LBRACKET);
3360                break;
3361        case '\\':
3362                if (*p->lex_inbuf == '\n') {
3363                        p->lex = XC_LEX_WHITESPACE;
3364                        p->lex_inbuf++;
3365                } else
3366                        s = bc_error_bad_character(c);
3367                break;
3368        case '^':
3369                parse_lex_by_checking_eq_sign(BC_LEX_OP_ASSIGN_POWER, XC_LEX_OP_POWER);
3370                break;
3371        case 'a':
3372        case 'b':
3373        case 'c':
3374        case 'd':
3375        case 'e':
3376        case 'f':
3377        case 'g':
3378        case 'h':
3379        case 'i':
3380        case 'j':
3381        case 'k':
3382        case 'l':
3383        case 'm':
3384        case 'n':
3385        case 'o':
3386        case 'p':
3387        case 'q':
3388        case 'r':
3389        case 's':
3390        case 't':
3391        case 'u':
3392        case 'v':
3393        case 'w':
3394        case 'x':
3395        case 'y':
3396        case 'z':
3397                s = zbc_lex_identifier();
3398                break;
3399        case '{':
3400        case '}':
3401                p->lex = (BcLexType)(c - '{' + BC_LEX_LBRACE);
3402                break;
3403        case '|':
3404                c2 = *p->lex_inbuf;
3405                if (c2 == '|') {
3406                        s = zbc_POSIX_does_not_allow_bool_ops_this_is_bad("||");
3407                        if (s) RETURN_STATUS(s);
3408                        p->lex_inbuf++;
3409                        p->lex = BC_LEX_OP_BOOL_OR;
3410                } else {
3411                        p->lex = XC_LEX_INVALID;
3412                        s = bc_error_bad_character(c);
3413                }
3414                break;
3415        default:
3416                p->lex = XC_LEX_INVALID;
3417                s = bc_error_bad_character(c);
3418                break;
3419        }
3420
3421        RETURN_STATUS(s);
3422}
3423#define zbc_lex_token(...) (zbc_lex_token(__VA_ARGS__) COMMA_SUCCESS)
3424#endif // ENABLE_BC
3425
3426#if ENABLE_DC
3427static BC_STATUS zdc_lex_register(void)
3428{
3429        BcParse *p = &G.prs;
3430        if (G_exreg && isspace(*p->lex_inbuf)) {
3431                xc_lex_whitespace(); // eats whitespace (but not newline)
3432                p->lex_inbuf++; // xc_lex_name() expects this
3433                xc_lex_name();
3434        } else {
3435                bc_vec_pop_all(&p->lex_strnumbuf);
3436                bc_vec_push(&p->lex_strnumbuf, p->lex_inbuf++);
3437                bc_vec_pushZeroByte(&p->lex_strnumbuf);
3438                p->lex = XC_LEX_NAME;
3439        }
3440
3441        RETURN_STATUS(BC_STATUS_SUCCESS);
3442}
3443#define zdc_lex_register(...) (zdc_lex_register(__VA_ARGS__) COMMA_SUCCESS)
3444
3445static BC_STATUS zdc_lex_string(void)
3446{
3447        BcParse *p = &G.prs;
3448        size_t depth;
3449
3450        p->lex = XC_LEX_STR;
3451        bc_vec_pop_all(&p->lex_strnumbuf);
3452
3453        depth = 1;
3454        for (;;) {
3455                char c = peek_inbuf();
3456                if (c == '\0') {
3457                        RETURN_STATUS(bc_error("unterminated string"));
3458                }
3459                if (c == '[') depth++;
3460                if (c == ']')
3461                        if (--depth == 0)
3462                                break;
3463                if (c == '\n') {
3464                        p->lex_line++;
3465                        dbg_lex("++p->lex_line=%zd", p->lex_line);
3466                }
3467                bc_vec_push(&p->lex_strnumbuf, p->lex_inbuf);
3468                p->lex_inbuf++;
3469        }
3470        bc_vec_pushZeroByte(&p->lex_strnumbuf);
3471        p->lex_inbuf++; // skip trailing ']'
3472
3473        G.err_line = p->lex_line;
3474        RETURN_STATUS(BC_STATUS_SUCCESS);
3475}
3476#define zdc_lex_string(...) (zdc_lex_string(__VA_ARGS__) COMMA_SUCCESS)
3477
3478#undef zdc_lex_token
3479static BC_STATUS zdc_lex_token(void)
3480{
3481        static const //BcLexType - should be this type, but narrower type saves size:
3482        uint8_t
3483        dc_lex_regs[] ALIGN1 = {
3484                XC_LEX_OP_REL_EQ, XC_LEX_OP_REL_LE, XC_LEX_OP_REL_GE, XC_LEX_OP_REL_NE,
3485                XC_LEX_OP_REL_LT, XC_LEX_OP_REL_GT, DC_LEX_SCOLON, DC_LEX_COLON,
3486                DC_LEX_ELSE, DC_LEX_LOAD, DC_LEX_LOAD_POP, DC_LEX_OP_ASSIGN,
3487                DC_LEX_STORE_PUSH,
3488        };
3489
3490        BcParse *p = &G.prs;
3491        BcStatus s;
3492        char c, c2;
3493        size_t i;
3494
3495        for (i = 0; i < ARRAY_SIZE(dc_lex_regs); ++i) {
3496                if (p->lex_last == dc_lex_regs[i])
3497                        RETURN_STATUS(zdc_lex_register());
3498        }
3499
3500        s = BC_STATUS_SUCCESS;
3501        c = eat_inbuf();
3502        if (c >= '%' && c <= '~'
3503         && (p->lex = dc_char_to_LEX[c - '%']) != XC_LEX_INVALID
3504        ) {
3505                RETURN_STATUS(s);
3506        }
3507
3508        // This is the workhorse of the lexer.
3509        switch (c) {
3510//      case '\0': // probably never reached
3511//              p->lex = XC_LEX_EOF;
3512//              break;
3513        case '\n':
3514                // '\n' is XC_LEX_NLINE, not XC_LEX_WHITESPACE
3515                // (and "case '\n':" is not just empty here)
3516                // only to allow interactive dc have a way to exit
3517                // "parse" stage of "parse,execute" loop
3518                // on <enter>, not on _next_ token (which would mean
3519                // commands are not executed on pressing <enter>).
3520                // IOW: typing "1p<enter>" should print "1" _at once_,
3521                // not after some more input.
3522                p->lex_line++;
3523                dbg_lex("++p->lex_line=%zd", p->lex_line);
3524                p->lex = XC_LEX_NLINE;
3525                break;
3526        case '\t':
3527        case '\v':
3528        case '\f':
3529        case '\r':
3530        case ' ':
3531                xc_lex_whitespace();
3532                break;
3533        case '!':
3534                c2 = *p->lex_inbuf;
3535                if (c2 == '=')
3536                        p->lex = XC_LEX_OP_REL_NE;
3537                else if (c2 == '<')
3538                        p->lex = XC_LEX_OP_REL_LE;
3539                else if (c2 == '>')
3540                        p->lex = XC_LEX_OP_REL_GE;
3541                else
3542                        RETURN_STATUS(bc_error_bad_character(c));
3543                p->lex_inbuf++;
3544                break;
3545        case '#':
3546                xc_lex_lineComment();
3547                break;
3548        case '.':
3549                if (isdigit(*p->lex_inbuf))
3550                        s = zxc_lex_number(c);
3551                else
3552                        s = bc_error_bad_character(c);
3553                break;
3554        case '0':
3555        case '1':
3556        case '2':
3557        case '3':
3558        case '4':
3559        case '5':
3560        case '6':
3561        case '7':
3562        case '8':
3563        case '9':
3564        case 'A':
3565        case 'B':
3566        case 'C':
3567        case 'D':
3568        case 'E':
3569        case 'F':
3570                s = zxc_lex_number(c);
3571                break;
3572        case '[':
3573                s = zdc_lex_string();
3574                break;
3575        default:
3576                p->lex = XC_LEX_INVALID;
3577                s = bc_error_bad_character(c);
3578                break;
3579        }
3580
3581        RETURN_STATUS(s);
3582}
3583#define zdc_lex_token(...) (zdc_lex_token(__VA_ARGS__) COMMA_SUCCESS)
3584#endif // ENABLE_DC
3585
3586static void xc_parse_push(unsigned i)
3587{
3588        BcVec *code = &G.prs.func->code;
3589        dbg_compile("%s:%d pushing bytecode %zd:%d", __func__, __LINE__, code->len, i);
3590        bc_vec_pushByte(code, (uint8_t)i);
3591}
3592
3593static void xc_parse_pushName(char *name)
3594{
3595#if 1
3596        BcVec *code = &G.prs.func->code;
3597        size_t pos = code->len;
3598        size_t len = strlen(name) + 1;
3599
3600        bc_vec_expand(code, pos + len);
3601        strcpy(code->v + pos, name);
3602        code->len = pos + len;
3603#else
3604        // Smaller code, but way slow:
3605        do {
3606                xc_parse_push(*name);
3607        } while (*name++);
3608#endif
3609}
3610
3611// Indexes < 0xfc are encoded verbatim, else first byte is
3612// 0xfc, 0xfd, 0xfe or 0xff, encoding "1..4 bytes",
3613// followed by that many bytes, lsb first.
3614// (The above describes 32-bit case).
3615#define SMALL_INDEX_LIMIT (0x100 - sizeof(size_t))
3616
3617static void bc_vec_pushIndex(BcVec *v, size_t idx)
3618{
3619        size_t mask;
3620        unsigned amt;
3621
3622        dbg_lex("%s:%d pushing index %zd", __func__, __LINE__, idx);
3623        if (idx < SMALL_INDEX_LIMIT) {
3624                bc_vec_pushByte(v, idx);
3625                return;
3626        }
3627
3628        mask = ((size_t)0xff) << (sizeof(idx) * 8 - 8);
3629        amt = sizeof(idx);
3630        for (;;) {
3631                if (idx & mask) break;
3632                mask >>= 8;
3633                amt--;
3634        }
3635        // amt is at least 1 here - "one byte of length data follows"
3636
3637        bc_vec_pushByte(v, (SMALL_INDEX_LIMIT - 1) + amt);
3638
3639        do {
3640                bc_vec_pushByte(v, (unsigned char)idx);
3641                idx >>= 8;
3642        } while (idx != 0);
3643}
3644
3645static void xc_parse_pushIndex(size_t idx)
3646{
3647        bc_vec_pushIndex(&G.prs.func->code, idx);
3648}
3649
3650static void xc_parse_pushInst_and_Index(unsigned inst, size_t idx)
3651{
3652        xc_parse_push(inst);
3653        xc_parse_pushIndex(idx);
3654}
3655
3656#if ENABLE_BC
3657static void bc_parse_pushJUMP(size_t idx)
3658{
3659        xc_parse_pushInst_and_Index(BC_INST_JUMP, idx);
3660}
3661
3662static void bc_parse_pushJUMP_ZERO(size_t idx)
3663{
3664        xc_parse_pushInst_and_Index(BC_INST_JUMP_ZERO, idx);
3665}
3666
3667static BC_STATUS zbc_parse_pushSTR(void)
3668{
3669        BcParse *p = &G.prs;
3670        char *str = xstrdup(p->lex_strnumbuf.v);
3671
3672        xc_parse_pushInst_and_Index(XC_INST_STR, p->func->strs.len);
3673        bc_vec_push(&p->func->strs, &str);
3674
3675        RETURN_STATUS(zxc_lex_next());
3676}
3677#define zbc_parse_pushSTR(...) (zbc_parse_pushSTR(__VA_ARGS__) COMMA_SUCCESS)
3678#endif
3679
3680static void xc_parse_pushNUM(void)
3681{
3682        BcParse *p = &G.prs;
3683        char *num = xstrdup(p->lex_strnumbuf.v);
3684#if ENABLE_BC && ENABLE_DC
3685        size_t idx = bc_vec_push(IS_BC ? &p->func->consts : &G.prog.consts, &num);
3686#elif ENABLE_BC
3687        size_t idx = bc_vec_push(&p->func->consts, &num);
3688#else // DC
3689        size_t idx = bc_vec_push(&G.prog.consts, &num);
3690#endif
3691        xc_parse_pushInst_and_Index(XC_INST_NUM, idx);
3692}
3693
3694static BC_STATUS zxc_parse_text_init(const char *text)
3695{
3696        G.prs.func = xc_program_func(G.prs.fidx);
3697        G.prs.lex_inbuf = text;
3698        G.prs.lex = G.prs.lex_last = XC_LEX_INVALID;
3699        RETURN_STATUS(zxc_lex_next());
3700}
3701#define zxc_parse_text_init(...) (zxc_parse_text_init(__VA_ARGS__) COMMA_SUCCESS)
3702
3703// Called when parsing or execution detects a failure,
3704// resets execution structures.
3705static void xc_program_reset(void)
3706{
3707        BcFunc *f;
3708        BcInstPtr *ip;
3709
3710        bc_vec_npop(&G.prog.exestack, G.prog.exestack.len - 1);
3711        bc_vec_pop_all(&G.prog.results);
3712
3713        f = xc_program_func_BC_PROG_MAIN();
3714        ip = bc_vec_top(&G.prog.exestack);
3715        ip->inst_idx = f->code.len;
3716}
3717
3718// Called when parsing code detects a failure,
3719// resets parsing structures.
3720static void xc_parse_reset(void)
3721{
3722        BcParse *p = &G.prs;
3723        if (p->fidx != BC_PROG_MAIN) {
3724                bc_func_free(p->func);
3725                bc_func_init(p->func);
3726
3727                p->fidx = BC_PROG_MAIN;
3728                p->func = xc_program_func_BC_PROG_MAIN();
3729        }
3730
3731        p->lex_inbuf += strlen(p->lex_inbuf);
3732        p->lex = XC_LEX_EOF;
3733
3734        IF_BC(bc_vec_pop_all(&p->exits);)
3735        IF_BC(bc_vec_pop_all(&p->conds);)
3736        IF_BC(bc_vec_pop_all(&p->ops);)
3737
3738        xc_program_reset();
3739}
3740
3741static void xc_parse_free(void)
3742{
3743        IF_BC(bc_vec_free(&G.prs.exits);)
3744        IF_BC(bc_vec_free(&G.prs.conds);)
3745        IF_BC(bc_vec_free(&G.prs.ops);)
3746        bc_vec_free(&G.prs.lex_strnumbuf);
3747}
3748
3749static void xc_parse_create(size_t fidx)
3750{
3751        BcParse *p = &G.prs;
3752        memset(p, 0, sizeof(BcParse));
3753
3754        bc_char_vec_init(&p->lex_strnumbuf);
3755        IF_BC(bc_vec_init(&p->exits, sizeof(size_t), NULL);)
3756        IF_BC(bc_vec_init(&p->conds, sizeof(size_t), NULL);)
3757        IF_BC(bc_vec_init(&p->ops, sizeof(BcLexType), NULL);)
3758
3759        p->fidx = fidx;
3760        p->func = xc_program_func(fidx);
3761}
3762
3763static void xc_program_add_fn(void)
3764{
3765        //size_t idx;
3766        BcFunc f;
3767        bc_func_init(&f);
3768        //idx =
3769        bc_vec_push(&G.prog.fns, &f);
3770        //return idx;
3771}
3772
3773#if ENABLE_BC
3774
3775// Note: takes ownership of 'name' (must be malloced)
3776static size_t bc_program_addFunc(char *name)
3777{
3778        size_t idx;
3779        BcId entry, *entry_ptr;
3780        int inserted;
3781
3782        entry.name = name;
3783        entry.idx = G.prog.fns.len;
3784
3785        inserted = bc_map_insert(&G.prog.fn_map, &entry, &idx);
3786        if (!inserted) free(name);
3787
3788        entry_ptr = bc_vec_item(&G.prog.fn_map, idx);
3789        idx = entry_ptr->idx;
3790
3791        if (!inserted) {
3792                // There is already a function with this name.
3793                // It'll be redefined now, clear old definition.
3794                BcFunc *func = xc_program_func(entry_ptr->idx);
3795                bc_func_free(func);
3796                bc_func_init(func);
3797        } else {
3798                xc_program_add_fn();
3799        }
3800
3801        return idx;
3802}
3803
3804#define BC_PARSE_TOP_OP(p) (*(BcLexType*)bc_vec_top(&(p)->ops))
3805// We can calculate the conversion between tokens and exprs by subtracting the
3806// position of the first operator in the lex enum and adding the position of the
3807// first in the expr enum. Note: This only works for binary operators.
3808#define BC_TOKEN_2_INST(t) ((char) ((t) - XC_LEX_OP_POWER + XC_INST_POWER))
3809
3810static BC_STATUS zbc_parse_expr(uint8_t flags);
3811#define zbc_parse_expr(...) (zbc_parse_expr(__VA_ARGS__) COMMA_SUCCESS)
3812
3813static BC_STATUS zbc_parse_stmt_possibly_auto(bool auto_allowed);
3814#define zbc_parse_stmt_possibly_auto(...) (zbc_parse_stmt_possibly_auto(__VA_ARGS__) COMMA_SUCCESS)
3815
3816static BC_STATUS zbc_parse_stmt(void)
3817{
3818        RETURN_STATUS(zbc_parse_stmt_possibly_auto(false));
3819}
3820#define zbc_parse_stmt(...) (zbc_parse_stmt(__VA_ARGS__) COMMA_SUCCESS)
3821
3822static BC_STATUS zbc_parse_stmt_allow_NLINE_before(const char *after_X)
3823{
3824        BcParse *p = &G.prs;
3825        // "if(cond)<newline>stmt" is accepted too, but not 2+ newlines.
3826        // Same for "else", "while()", "for()".
3827        BcStatus s = zbc_lex_next_and_skip_NLINE();
3828        if (s) RETURN_STATUS(s);
3829        if (p->lex == XC_LEX_NLINE)
3830                RETURN_STATUS(bc_error_fmt("no statement after '%s'", after_X));
3831
3832        RETURN_STATUS(zbc_parse_stmt());
3833}
3834#define zbc_parse_stmt_allow_NLINE_before(...) (zbc_parse_stmt_allow_NLINE_before(__VA_ARGS__) COMMA_SUCCESS)
3835
3836static void bc_parse_operator(BcLexType type, size_t start, size_t *nexprs)
3837{
3838        BcParse *p = &G.prs;
3839        char l, r = bc_operation_PREC(type - XC_LEX_1st_op);
3840        bool left = bc_operation_LEFT(type - XC_LEX_1st_op);
3841
3842        while (p->ops.len > start) {
3843                BcLexType t = BC_PARSE_TOP_OP(p);
3844                if (t == BC_LEX_LPAREN) break;
3845
3846                l = bc_operation_PREC(t - XC_LEX_1st_op);
3847                if (l >= r && (l != r || !left)) break;
3848
3849                xc_parse_push(BC_TOKEN_2_INST(t));
3850                bc_vec_pop(&p->ops);
3851                *nexprs -= (t != BC_LEX_OP_BOOL_NOT && t != XC_LEX_NEG);
3852        }
3853
3854        bc_vec_push(&p->ops, &type);
3855}
3856
3857static BC_STATUS zbc_parse_rightParen(size_t ops_bgn, size_t *nexs)
3858{
3859        BcParse *p = &G.prs;
3860        BcLexType top;
3861
3862        if (p->ops.len <= ops_bgn)
3863                RETURN_STATUS(bc_error_bad_expression());
3864        top = BC_PARSE_TOP_OP(p);
3865
3866        while (top != BC_LEX_LPAREN) {
3867                xc_parse_push(BC_TOKEN_2_INST(top));
3868
3869                bc_vec_pop(&p->ops);
3870                *nexs -= (top != BC_LEX_OP_BOOL_NOT && top != XC_LEX_NEG);
3871
3872                if (p->ops.len <= ops_bgn)
3873                        RETURN_STATUS(bc_error_bad_expression());
3874                top = BC_PARSE_TOP_OP(p);
3875        }
3876
3877        bc_vec_pop(&p->ops);
3878
3879        RETURN_STATUS(BC_STATUS_SUCCESS);
3880}
3881#define zbc_parse_rightParen(...) (zbc_parse_rightParen(__VA_ARGS__) COMMA_SUCCESS)
3882
3883static BC_STATUS zbc_parse_params(uint8_t flags)
3884{
3885        BcParse *p = &G.prs;
3886        BcStatus s;
3887        size_t nparams;
3888
3889        dbg_lex("%s:%d p->lex:%d", __func__, __LINE__, p->lex);
3890        flags = (flags & ~(BC_PARSE_PRINT | BC_PARSE_REL)) | BC_PARSE_ARRAY;
3891
3892        s = zxc_lex_next();
3893        if (s) RETURN_STATUS(s);
3894
3895        nparams = 0;
3896        if (p->lex != BC_LEX_RPAREN) {
3897                for (;;) {
3898                        s = zbc_parse_expr(flags);
3899                        if (s) RETURN_STATUS(s);
3900                        nparams++;
3901                        if (p->lex != BC_LEX_COMMA) {
3902                                if (p->lex == BC_LEX_RPAREN)
3903                                        break;
3904                                RETURN_STATUS(bc_error_bad_token());
3905                        }
3906                        s = zxc_lex_next();
3907                        if (s) RETURN_STATUS(s);
3908                }
3909        }
3910
3911        xc_parse_pushInst_and_Index(BC_INST_CALL, nparams);
3912
3913        RETURN_STATUS(BC_STATUS_SUCCESS);
3914}
3915#define zbc_parse_params(...) (zbc_parse_params(__VA_ARGS__) COMMA_SUCCESS)
3916
3917// Note: takes ownership of 'name' (must be malloced)
3918static BC_STATUS zbc_parse_call(char *name, uint8_t flags)
3919{
3920        BcParse *p = &G.prs;
3921        BcStatus s;
3922        BcId entry, *entry_ptr;
3923        size_t idx;
3924
3925        entry.name = name;
3926
3927        s = zbc_parse_params(flags);
3928        if (s) goto err;
3929
3930        if (p->lex != BC_LEX_RPAREN) {
3931                s = bc_error_bad_token();
3932                goto err;
3933        }
3934
3935        idx = bc_map_find_exact(&G.prog.fn_map, &entry);
3936
3937        if (idx == BC_VEC_INVALID_IDX) {
3938                // No such function exists, create an empty one
3939                bc_program_addFunc(name);
3940                idx = bc_map_find_exact(&G.prog.fn_map, &entry);
3941        } else
3942                free(name);
3943
3944        entry_ptr = bc_vec_item(&G.prog.fn_map, idx);
3945        xc_parse_pushIndex(entry_ptr->idx);
3946
3947        RETURN_STATUS(zxc_lex_next());
3948 err:
3949        free(name);
3950        RETURN_STATUS(s);
3951}
3952#define zbc_parse_call(...) (zbc_parse_call(__VA_ARGS__) COMMA_SUCCESS)
3953
3954static BC_STATUS zbc_parse_name(BcInst *type, uint8_t flags)
3955{
3956        BcParse *p = &G.prs;
3957        BcStatus s;
3958        char *name;
3959
3960        name = xstrdup(p->lex_strnumbuf.v);
3961        s = zxc_lex_next();
3962        if (s) goto err;
3963
3964        if (p->lex == BC_LEX_LBRACKET) {
3965                s = zxc_lex_next();
3966                if (s) goto err;
3967
3968                if (p->lex == BC_LEX_RBRACKET) {
3969                        if (!(flags & BC_PARSE_ARRAY)) {
3970                                s = bc_error_bad_expression();
3971                                goto err;
3972                        }
3973                        *type = XC_INST_ARRAY;
3974                } else {
3975                        *type = XC_INST_ARRAY_ELEM;
3976                        flags &= ~(BC_PARSE_PRINT | BC_PARSE_REL);
3977                        s = zbc_parse_expr(flags);
3978                        if (s) goto err;
3979                }
3980                s = zxc_lex_next();
3981                if (s) goto err;
3982                xc_parse_push(*type);
3983                xc_parse_pushName(name);
3984                free(name);
3985        } else if (p->lex == BC_LEX_LPAREN) {
3986                if (flags & BC_PARSE_NOCALL) {
3987                        s = bc_error_bad_token();
3988                        goto err;
3989                }
3990                *type = BC_INST_CALL;
3991                s = zbc_parse_call(name, flags);
3992        } else {
3993                *type = XC_INST_VAR;
3994                xc_parse_push(XC_INST_VAR);
3995                xc_parse_pushName(name);
3996                free(name);
3997        }
3998
3999        RETURN_STATUS(s);
4000 err:
4001        free(name);
4002        RETURN_STATUS(s);
4003}
4004#define zbc_parse_name(...) (zbc_parse_name(__VA_ARGS__) COMMA_SUCCESS)
4005
4006static BC_STATUS zbc_parse_read(void)
4007{
4008        BcParse *p = &G.prs;
4009        BcStatus s;
4010
4011        s = zxc_lex_next();
4012        if (s) RETURN_STATUS(s);
4013        if (p->lex != BC_LEX_LPAREN) RETURN_STATUS(bc_error_bad_token());
4014
4015        s = zxc_lex_next();
4016        if (s) RETURN_STATUS(s);
4017        if (p->lex != BC_LEX_RPAREN) RETURN_STATUS(bc_error_bad_token());
4018
4019        xc_parse_push(XC_INST_READ);
4020
4021        RETURN_STATUS(s);
4022}
4023#define zbc_parse_read(...) (zbc_parse_read(__VA_ARGS__) COMMA_SUCCESS)
4024
4025static BC_STATUS zbc_parse_builtin(BcLexType type, uint8_t flags, BcInst *prev)
4026{
4027        BcParse *p = &G.prs;
4028        BcStatus s;
4029
4030        s = zxc_lex_next();
4031        if (s) RETURN_STATUS(s);
4032        if (p->lex != BC_LEX_LPAREN) RETURN_STATUS(bc_error_bad_token());
4033
4034        flags = (flags & ~(BC_PARSE_PRINT | BC_PARSE_REL)) | BC_PARSE_ARRAY;
4035
4036        s = zxc_lex_next();
4037        if (s) RETURN_STATUS(s);
4038
4039        s = zbc_parse_expr(flags);
4040        if (s) RETURN_STATUS(s);
4041
4042        if (p->lex != BC_LEX_RPAREN) RETURN_STATUS(bc_error_bad_token());
4043
4044        *prev = (type == BC_LEX_KEY_LENGTH) ? XC_INST_LENGTH : XC_INST_SQRT;
4045        xc_parse_push(*prev);
4046
4047        RETURN_STATUS(s);
4048}
4049#define zbc_parse_builtin(...) (zbc_parse_builtin(__VA_ARGS__) COMMA_SUCCESS)
4050
4051static BC_STATUS zbc_parse_scale(BcInst *type, uint8_t flags)
4052{
4053        BcParse *p = &G.prs;
4054        BcStatus s;
4055
4056        s = zxc_lex_next();
4057        if (s) RETURN_STATUS(s);
4058
4059        if (p->lex != BC_LEX_LPAREN) {
4060                *type = XC_INST_SCALE;
4061                xc_parse_push(XC_INST_SCALE);
4062                RETURN_STATUS(BC_STATUS_SUCCESS);
4063        }
4064
4065        *type = XC_INST_SCALE_FUNC;
4066        flags &= ~(BC_PARSE_PRINT | BC_PARSE_REL);
4067
4068        s = zxc_lex_next();
4069        if (s) RETURN_STATUS(s);
4070
4071        s = zbc_parse_expr(flags);
4072        if (s) RETURN_STATUS(s);
4073        if (p->lex != BC_LEX_RPAREN)
4074                RETURN_STATUS(bc_error_bad_token());
4075        xc_parse_push(XC_INST_SCALE_FUNC);
4076
4077        RETURN_STATUS(zxc_lex_next());
4078}
4079#define zbc_parse_scale(...) (zbc_parse_scale(__VA_ARGS__) COMMA_SUCCESS)
4080
4081static BC_STATUS zbc_parse_incdec(BcInst *prev, size_t *nexs, uint8_t flags)
4082{
4083        BcParse *p = &G.prs;
4084        BcStatus s;
4085        BcLexType type;
4086        char inst;
4087        BcInst etype = *prev;
4088
4089        if (etype == XC_INST_VAR || etype == XC_INST_ARRAY_ELEM
4090         || etype == XC_INST_SCALE || etype == BC_INST_LAST
4091         || etype == XC_INST_IBASE || etype == XC_INST_OBASE
4092        ) {
4093                *prev = inst = BC_INST_INC_POST + (p->lex != BC_LEX_OP_INC);
4094                xc_parse_push(inst);
4095                s = zxc_lex_next();
4096        } else {
4097                *prev = inst = BC_INST_INC_PRE + (p->lex != BC_LEX_OP_INC);
4098
4099                s = zxc_lex_next();
4100                if (s) RETURN_STATUS(s);
4101                type = p->lex;
4102
4103                // Because we parse the next part of the expression
4104                // right here, we need to increment this.
4105                *nexs = *nexs + 1;
4106
4107                switch (type) {
4108                case XC_LEX_NAME:
4109                        s = zbc_parse_name(prev, flags | BC_PARSE_NOCALL);
4110                        break;
4111                case BC_LEX_KEY_IBASE:
4112                case BC_LEX_KEY_LAST:
4113                case BC_LEX_KEY_OBASE:
4114                        xc_parse_push(type - BC_LEX_KEY_IBASE + XC_INST_IBASE);
4115                        s = zxc_lex_next();
4116                        break;
4117                case BC_LEX_KEY_SCALE:
4118                        s = zxc_lex_next();
4119                        if (s) RETURN_STATUS(s);
4120                        if (p->lex == BC_LEX_LPAREN)
4121                                s = bc_error_bad_token();
4122                        else
4123                                xc_parse_push(XC_INST_SCALE);
4124                        break;
4125                default:
4126                        s = bc_error_bad_token();
4127                        break;
4128                }
4129
4130                if (!s) xc_parse_push(inst);
4131        }
4132
4133        RETURN_STATUS(s);
4134}
4135#define zbc_parse_incdec(...) (zbc_parse_incdec(__VA_ARGS__) COMMA_SUCCESS)
4136
4137static int bc_parse_inst_isLeaf(BcInst p)
4138{
4139        return (p >= XC_INST_NUM && p <= XC_INST_SQRT)
4140                || p == BC_INST_INC_POST
4141                || p == BC_INST_DEC_POST
4142                ;
4143}
4144#define BC_PARSE_LEAF(prev, bin_last, rparen) \
4145        (!(bin_last) && ((rparen) || bc_parse_inst_isLeaf(prev)))
4146
4147static BC_STATUS zbc_parse_minus(BcInst *prev, size_t ops_bgn,
4148                                bool rparen, bool bin_last, size_t *nexprs)
4149{
4150        BcParse *p = &G.prs;
4151        BcStatus s;
4152        BcLexType type;
4153
4154        s = zxc_lex_next();
4155        if (s) RETURN_STATUS(s);
4156
4157        type = BC_PARSE_LEAF(*prev, bin_last, rparen) ? XC_LEX_OP_MINUS : XC_LEX_NEG;
4158        *prev = BC_TOKEN_2_INST(type);
4159
4160        // We can just push onto the op stack because this is the largest
4161        // precedence operator that gets pushed. Inc/dec does not.
4162        if (type != XC_LEX_OP_MINUS)
4163                bc_vec_push(&p->ops, &type);
4164        else
4165                bc_parse_operator(type, ops_bgn, nexprs);
4166
4167        RETURN_STATUS(s);
4168}
4169#define zbc_parse_minus(...) (zbc_parse_minus(__VA_ARGS__) COMMA_SUCCESS)
4170
4171static BC_STATUS zbc_parse_print(void)
4172{
4173        BcParse *p = &G.prs;
4174        BcStatus s;
4175        BcLexType type;
4176
4177        for (;;) {
4178                s = zxc_lex_next();
4179                if (s) RETURN_STATUS(s);
4180                type = p->lex;
4181                if (type == XC_LEX_STR) {
4182                        s = zbc_parse_pushSTR();
4183                } else {
4184                        s = zbc_parse_expr(0);
4185                }
4186                if (s) RETURN_STATUS(s);
4187                xc_parse_push(XC_INST_PRINT_POP);
4188                if (p->lex != BC_LEX_COMMA)
4189                        break;
4190        }
4191
4192        RETURN_STATUS(s);
4193}
4194#define zbc_parse_print(...) (zbc_parse_print(__VA_ARGS__) COMMA_SUCCESS)
4195
4196static BC_STATUS zbc_parse_return(void)
4197{
4198        BcParse *p = &G.prs;
4199        BcStatus s;
4200        BcLexType t;
4201
4202        dbg_lex_enter("%s:%d entered", __func__, __LINE__);
4203        s = zxc_lex_next();
4204        if (s) RETURN_STATUS(s);
4205
4206        t = p->lex;
4207        if (t == XC_LEX_NLINE || t == BC_LEX_SCOLON || t == BC_LEX_RBRACE)
4208                xc_parse_push(BC_INST_RET0);
4209        else {
4210//TODO: if (p->func->voidfunc) ERROR
4211                s = zbc_parse_expr(0);
4212                if (s) RETURN_STATUS(s);
4213
4214                if (t != BC_LEX_LPAREN   // "return EXPR", no ()
4215                 || p->lex_last != BC_LEX_RPAREN  // example: "return (a) + b"
4216                ) {
4217                        s = zbc_POSIX_requires("parentheses around return expressions");
4218                        if (s) RETURN_STATUS(s);
4219                }
4220
4221                xc_parse_push(XC_INST_RET);
4222        }
4223
4224        dbg_lex_done("%s:%d done", __func__, __LINE__);
4225        RETURN_STATUS(s);
4226}
4227#define zbc_parse_return(...) (zbc_parse_return(__VA_ARGS__) COMMA_SUCCESS)
4228
4229static void rewrite_label_to_current(size_t idx)
4230{
4231        BcParse *p = &G.prs;
4232        size_t *label = bc_vec_item(&p->func->labels, idx);
4233        *label = p->func->code.len;
4234}
4235
4236static BC_STATUS zbc_parse_if(void)
4237{
4238        BcParse *p = &G.prs;
4239        BcStatus s;
4240        size_t ip_idx;
4241
4242        dbg_lex_enter("%s:%d entered", __func__, __LINE__);
4243        s = zxc_lex_next();
4244        if (s) RETURN_STATUS(s);
4245        if (p->lex != BC_LEX_LPAREN) RETURN_STATUS(bc_error_bad_token());
4246
4247        s = zxc_lex_next();
4248        if (s) RETURN_STATUS(s);
4249        s = zbc_parse_expr(BC_PARSE_REL);
4250        if (s) RETURN_STATUS(s);
4251        if (p->lex != BC_LEX_RPAREN) RETURN_STATUS(bc_error_bad_token());
4252
4253        // Encode "if zero, jump to ..."
4254        // Pushed value (destination of the jump) is uninitialized,
4255        // will be rewritten to be address of "end of if()" or of "else".
4256        ip_idx = bc_vec_push(&p->func->labels, &ip_idx);
4257        bc_parse_pushJUMP_ZERO(ip_idx);
4258
4259        s = zbc_parse_stmt_allow_NLINE_before(STRING_if);
4260        if (s) RETURN_STATUS(s);
4261
4262        dbg_lex("%s:%d in if after stmt: p->lex:%d", __func__, __LINE__, p->lex);
4263        if (p->lex == BC_LEX_KEY_ELSE) {
4264                size_t ip2_idx;
4265
4266                // Encode "after then_stmt, jump to end of if()"
4267                ip2_idx = bc_vec_push(&p->func->labels, &ip2_idx);
4268                dbg_lex("%s:%d after if() then_stmt: BC_INST_JUMP to %zd", __func__, __LINE__, ip2_idx);
4269                bc_parse_pushJUMP(ip2_idx);
4270
4271                dbg_lex("%s:%d rewriting 'if_zero' label to jump to 'else'-> %zd", __func__, __LINE__, p->func->code.len);
4272                rewrite_label_to_current(ip_idx);
4273
4274                ip_idx = ip2_idx;
4275
4276                s = zbc_parse_stmt_allow_NLINE_before(STRING_else);
4277                if (s) RETURN_STATUS(s);
4278        }
4279
4280        dbg_lex("%s:%d rewriting label to jump after 'if' body-> %zd", __func__, __LINE__, p->func->code.len);
4281        rewrite_label_to_current(ip_idx);
4282
4283        dbg_lex_done("%s:%d done", __func__, __LINE__);
4284        RETURN_STATUS(s);
4285}
4286#define zbc_parse_if(...) (zbc_parse_if(__VA_ARGS__) COMMA_SUCCESS)
4287
4288static BC_STATUS zbc_parse_while(void)
4289{
4290        BcParse *p = &G.prs;
4291        BcStatus s;
4292        size_t cond_idx;
4293        size_t ip_idx;
4294
4295        s = zxc_lex_next();
4296        if (s) RETURN_STATUS(s);
4297        if (p->lex != BC_LEX_LPAREN) RETURN_STATUS(bc_error_bad_token());
4298        s = zxc_lex_next();
4299        if (s) RETURN_STATUS(s);
4300
4301        cond_idx = bc_vec_push(&p->func->labels, &p->func->code.len);
4302        ip_idx = cond_idx + 1;
4303        bc_vec_push(&p->conds, &cond_idx);
4304
4305        bc_vec_push(&p->exits, &ip_idx);
4306        bc_vec_push(&p->func->labels, &ip_idx);
4307
4308        s = zbc_parse_expr(BC_PARSE_REL);
4309        if (s) RETURN_STATUS(s);
4310        if (p->lex != BC_LEX_RPAREN) RETURN_STATUS(bc_error_bad_token());
4311
4312        bc_parse_pushJUMP_ZERO(ip_idx);
4313
4314        s = zbc_parse_stmt_allow_NLINE_before(STRING_while);
4315        if (s) RETURN_STATUS(s);
4316
4317        dbg_lex("%s:%d BC_INST_JUMP to %zd", __func__, __LINE__, cond_idx);
4318        bc_parse_pushJUMP(cond_idx);
4319
4320        dbg_lex("%s:%d rewriting label-> %zd", __func__, __LINE__, p->func->code.len);
4321        rewrite_label_to_current(ip_idx);
4322
4323        bc_vec_pop(&p->exits);
4324        bc_vec_pop(&p->conds);
4325
4326        RETURN_STATUS(s);
4327}
4328#define zbc_parse_while(...) (zbc_parse_while(__VA_ARGS__) COMMA_SUCCESS)
4329
4330static BC_STATUS zbc_parse_for(void)
4331{
4332        BcParse *p = &G.prs;
4333        BcStatus s;
4334        size_t cond_idx, exit_idx, body_idx, update_idx;
4335
4336        dbg_lex("%s:%d p->lex:%d", __func__, __LINE__, p->lex);
4337        s = zxc_lex_next();
4338        if (s) RETURN_STATUS(s);
4339        if (p->lex != BC_LEX_LPAREN) RETURN_STATUS(bc_error_bad_token());
4340        s = zxc_lex_next();
4341        if (s) RETURN_STATUS(s);
4342
4343        if (p->lex != BC_LEX_SCOLON) {
4344                s = zbc_parse_expr(0);
4345                xc_parse_push(XC_INST_POP);
4346                if (s) RETURN_STATUS(s);
4347        } else {
4348                s = zbc_POSIX_does_not_allow_empty_X_expression_in_for("init");
4349                if (s) RETURN_STATUS(s);
4350        }
4351
4352        if (p->lex != BC_LEX_SCOLON) RETURN_STATUS(bc_error_bad_token());
4353        s = zxc_lex_next();
4354        if (s) RETURN_STATUS(s);
4355
4356        cond_idx = bc_vec_push(&p->func->labels, &p->func->code.len);
4357        update_idx = cond_idx + 1;
4358        body_idx = update_idx + 1;
4359        exit_idx = body_idx + 1;
4360
4361        if (p->lex != BC_LEX_SCOLON)
4362                s = zbc_parse_expr(BC_PARSE_REL);
4363        else {
4364                // Set this for the next call to xc_parse_pushNUM().
4365                // This is safe to set because the current token is a semicolon,
4366                // which has no string requirement.
4367                bc_vec_string(&p->lex_strnumbuf, 1, "1");
4368                xc_parse_pushNUM();
4369                s = zbc_POSIX_does_not_allow_empty_X_expression_in_for("condition");
4370        }
4371        if (s) RETURN_STATUS(s);
4372
4373        if (p->lex != BC_LEX_SCOLON) RETURN_STATUS(bc_error_bad_token());
4374
4375        s = zxc_lex_next();
4376        if (s) RETURN_STATUS(s);
4377
4378        bc_parse_pushJUMP_ZERO(exit_idx);
4379        bc_parse_pushJUMP(body_idx);
4380
4381        bc_vec_push(&p->conds, &update_idx);
4382        bc_vec_push(&p->func->labels, &p->func->code.len);
4383
4384        if (p->lex != BC_LEX_RPAREN) {
4385                s = zbc_parse_expr(0);
4386                if (s) RETURN_STATUS(s);
4387                if (p->lex != BC_LEX_RPAREN) RETURN_STATUS(bc_error_bad_token());
4388                xc_parse_push(XC_INST_POP);
4389        } else {
4390                s = zbc_POSIX_does_not_allow_empty_X_expression_in_for("update");
4391                if (s) RETURN_STATUS(s);
4392        }
4393
4394        bc_parse_pushJUMP(cond_idx);
4395        bc_vec_push(&p->func->labels, &p->func->code.len);
4396
4397        bc_vec_push(&p->exits, &exit_idx);
4398        bc_vec_push(&p->func->labels, &exit_idx);
4399
4400        s = zbc_parse_stmt_allow_NLINE_before(STRING_for);
4401        if (s) RETURN_STATUS(s);
4402
4403        dbg_lex("%s:%d BC_INST_JUMP to %zd", __func__, __LINE__, update_idx);
4404        bc_parse_pushJUMP(update_idx);
4405
4406        dbg_lex("%s:%d rewriting label-> %zd", __func__, __LINE__, p->func->code.len);
4407        rewrite_label_to_current(exit_idx);
4408
4409        bc_vec_pop(&p->exits);
4410        bc_vec_pop(&p->conds);
4411
4412        RETURN_STATUS(BC_STATUS_SUCCESS);
4413}
4414#define zbc_parse_for(...) (zbc_parse_for(__VA_ARGS__) COMMA_SUCCESS)
4415
4416static BC_STATUS zbc_parse_break_or_continue(BcLexType type)
4417{
4418        BcParse *p = &G.prs;
4419        size_t i;
4420
4421        if (type == BC_LEX_KEY_BREAK) {
4422                if (p->exits.len == 0) // none of the enclosing blocks is a loop
4423                        RETURN_STATUS(bc_error_bad_token());
4424                i = *(size_t*)bc_vec_top(&p->exits);
4425        } else {
4426                i = *(size_t*)bc_vec_top(&p->conds);
4427        }
4428        bc_parse_pushJUMP(i);
4429
4430        RETURN_STATUS(zxc_lex_next());
4431}
4432#define zbc_parse_break_or_continue(...) (zbc_parse_break_or_continue(__VA_ARGS__) COMMA_SUCCESS)
4433
4434static BC_STATUS zbc_func_insert(BcFunc *f, char *name, BcType type)
4435{
4436        BcId *autoid;
4437        BcId a;
4438        size_t i;
4439
4440        autoid = (void*)f->autos.v;
4441        for (i = 0; i < f->autos.len; i++, autoid++) {
4442                if (strcmp(name, autoid->name) == 0
4443                 && type == (BcType) autoid->idx
4444                ) {
4445                        RETURN_STATUS(bc_error("duplicate function parameter or auto name"));
4446                }
4447        }
4448
4449        a.idx = type;
4450        a.name = name;
4451
4452        bc_vec_push(&f->autos, &a);
4453
4454        RETURN_STATUS(BC_STATUS_SUCCESS);
4455}
4456#define zbc_func_insert(...) (zbc_func_insert(__VA_ARGS__) COMMA_SUCCESS)
4457
4458static BC_STATUS zbc_parse_funcdef(void)
4459{
4460        BcParse *p = &G.prs;
4461        BcStatus s;
4462        bool comma, voidfunc;
4463        char *name;
4464
4465        dbg_lex_enter("%s:%d entered", __func__, __LINE__);
4466        s = zxc_lex_next();
4467        if (s) RETURN_STATUS(s);
4468        if (p->lex != XC_LEX_NAME)
4469                RETURN_STATUS(bc_error_bad_function_definition());
4470
4471        // To be maximally both POSIX and GNU-compatible,
4472        // "void" is not treated as a normal keyword:
4473        // you can have variable named "void", and even a function
4474        // named "void": "define void() { return 6; }" is ok.
4475        // _Only_ "define void f() ..." syntax treats "void"
4476        // specially.
4477        voidfunc = (strcmp(p->lex_strnumbuf.v, "void") == 0);
4478
4479        s = zxc_lex_next();
4480        if (s) RETURN_STATUS(s);
4481
4482        voidfunc = (voidfunc && p->lex == XC_LEX_NAME);
4483        if (voidfunc) {
4484                s = zxc_lex_next();
4485                if (s) RETURN_STATUS(s);
4486        }
4487
4488        if (p->lex != BC_LEX_LPAREN)
4489                RETURN_STATUS(bc_error_bad_function_definition());
4490
4491        p->fidx = bc_program_addFunc(xstrdup(p->lex_strnumbuf.v));
4492        p->func = xc_program_func(p->fidx);
4493        p->func->voidfunc = voidfunc;
4494
4495        s = zxc_lex_next();
4496        if (s) RETURN_STATUS(s);
4497
4498        comma = false;
4499        while (p->lex != BC_LEX_RPAREN) {
4500                BcType t = BC_TYPE_VAR;
4501
4502                if (p->lex == XC_LEX_OP_MULTIPLY) {
4503                        t = BC_TYPE_REF;
4504                        s = zxc_lex_next();
4505                        if (s) RETURN_STATUS(s);
4506                        s = zbc_POSIX_does_not_allow("references");
4507                        if (s) RETURN_STATUS(s);
4508                }
4509
4510                if (p->lex != XC_LEX_NAME)
4511                        RETURN_STATUS(bc_error_bad_function_definition());
4512
4513                ++p->func->nparams;
4514
4515                name = xstrdup(p->lex_strnumbuf.v);
4516                s = zxc_lex_next();
4517                if (s) goto err;
4518
4519                if (p->lex == BC_LEX_LBRACKET) {
4520                        if (t == BC_TYPE_VAR) t = BC_TYPE_ARRAY;
4521                        s = zxc_lex_next();
4522                        if (s) goto err;
4523
4524                        if (p->lex != BC_LEX_RBRACKET) {
4525                                s = bc_error_bad_function_definition();
4526                                goto err;
4527                        }
4528
4529                        s = zxc_lex_next();
4530                        if (s) goto err;
4531                }
4532                else if (t == BC_TYPE_REF) {
4533                        s = bc_error_at("vars can't be references");
4534                        goto err;
4535                }
4536
4537                comma = p->lex == BC_LEX_COMMA;
4538                if (comma) {
4539                        s = zxc_lex_next();
4540                        if (s) goto err;
4541                }
4542
4543                s = zbc_func_insert(p->func, name, t);
4544                if (s) goto err;
4545        }
4546
4547        if (comma) RETURN_STATUS(bc_error_bad_function_definition());
4548
4549        s = zxc_lex_next();
4550        if (s) RETURN_STATUS(s);
4551
4552        if (p->lex != BC_LEX_LBRACE) {
4553                s = zbc_POSIX_requires("the left brace be on the same line as the function header");
4554                if (s) RETURN_STATUS(s);
4555        }
4556
4557        // Prevent "define z()<newline>" from being interpreted as function with empty stmt as body
4558        s = zbc_lex_skip_if_at_NLINE();
4559        if (s) RETURN_STATUS(s);
4560        // GNU bc requires a {} block even if function body has single stmt, enforce this
4561        if (p->lex != BC_LEX_LBRACE)
4562                RETURN_STATUS(bc_error("function { body } expected"));
4563
4564        p->in_funcdef++; // to determine whether "return" stmt is allowed, and such
4565        s = zbc_parse_stmt_possibly_auto(true);
4566        p->in_funcdef--;
4567        if (s) RETURN_STATUS(s);
4568
4569        xc_parse_push(BC_INST_RET0);
4570
4571        // Subsequent code generation is into main program
4572        p->fidx = BC_PROG_MAIN;
4573        p->func = xc_program_func_BC_PROG_MAIN();
4574
4575        dbg_lex_done("%s:%d done", __func__, __LINE__);
4576        RETURN_STATUS(s);
4577 err:
4578        dbg_lex_done("%s:%d done (error)", __func__, __LINE__);
4579        free(name);
4580        RETURN_STATUS(s);
4581}
4582#define zbc_parse_funcdef(...) (zbc_parse_funcdef(__VA_ARGS__) COMMA_SUCCESS)
4583
4584static BC_STATUS zbc_parse_auto(void)
4585{
4586        BcParse *p = &G.prs;
4587        BcStatus s;
4588        char *name;
4589
4590        dbg_lex_enter("%s:%d entered", __func__, __LINE__);
4591        s = zxc_lex_next();
4592        if (s) RETURN_STATUS(s);
4593
4594        for (;;) {
4595                BcType t;
4596
4597                if (p->lex != XC_LEX_NAME)
4598                        RETURN_STATUS(bc_error_at("bad 'auto' syntax"));
4599
4600                name = xstrdup(p->lex_strnumbuf.v);
4601                s = zxc_lex_next();
4602                if (s) goto err;
4603
4604                t = BC_TYPE_VAR;
4605                if (p->lex == BC_LEX_LBRACKET) {
4606                        t = BC_TYPE_ARRAY;
4607                        s = zxc_lex_next();
4608                        if (s) goto err;
4609
4610                        if (p->lex != BC_LEX_RBRACKET) {
4611                                s = bc_error_at("bad 'auto' syntax");
4612                                goto err;
4613                        }
4614                        s = zxc_lex_next();
4615                        if (s) goto err;
4616                }
4617
4618                s = zbc_func_insert(p->func, name, t);
4619                if (s) goto err;
4620
4621                if (p->lex == XC_LEX_NLINE
4622                 || p->lex == BC_LEX_SCOLON
4623                //|| p->lex == BC_LEX_RBRACE // allow "define f() {auto a}"
4624                ) {
4625                        break;
4626                }
4627                if (p->lex != BC_LEX_COMMA)
4628                        RETURN_STATUS(bc_error_at("bad 'auto' syntax"));
4629                s = zxc_lex_next(); // skip comma
4630                if (s) RETURN_STATUS(s);
4631        }
4632
4633        dbg_lex_done("%s:%d done", __func__, __LINE__);
4634        RETURN_STATUS(BC_STATUS_SUCCESS);
4635 err:
4636        free(name);
4637        dbg_lex_done("%s:%d done (ERROR)", __func__, __LINE__);
4638        RETURN_STATUS(s);
4639}
4640#define zbc_parse_auto(...) (zbc_parse_auto(__VA_ARGS__) COMMA_SUCCESS)
4641
4642#undef zbc_parse_stmt_possibly_auto
4643static BC_STATUS zbc_parse_stmt_possibly_auto(bool auto_allowed)
4644{
4645        BcParse *p = &G.prs;
4646        BcStatus s = BC_STATUS_SUCCESS;
4647
4648        dbg_lex_enter("%s:%d entered, p->lex:%d", __func__, __LINE__, p->lex);
4649
4650        if (p->lex == XC_LEX_NLINE) {
4651                dbg_lex_done("%s:%d done (seen XC_LEX_NLINE)", __func__, __LINE__);
4652                RETURN_STATUS(s);
4653        }
4654        if (p->lex == BC_LEX_SCOLON) {
4655                dbg_lex_done("%s:%d done (seen BC_LEX_SCOLON)", __func__, __LINE__);
4656                RETURN_STATUS(s);
4657        }
4658
4659        if (p->lex == BC_LEX_LBRACE) {
4660                dbg_lex("%s:%d BC_LEX_LBRACE: (auto_allowed:%d)", __func__, __LINE__, auto_allowed);
4661                do {
4662                        s = zxc_lex_next();
4663                        if (s) RETURN_STATUS(s);
4664                } while (p->lex == XC_LEX_NLINE);
4665                if (auto_allowed && p->lex == BC_LEX_KEY_AUTO) {
4666                        dbg_lex("%s:%d calling zbc_parse_auto()", __func__, __LINE__);
4667                        s = zbc_parse_auto();
4668                        if (s) RETURN_STATUS(s);
4669                }
4670                while (p->lex != BC_LEX_RBRACE) {
4671                        dbg_lex("%s:%d block parsing loop", __func__, __LINE__);
4672                        s = zbc_parse_stmt();
4673                        if (s) RETURN_STATUS(s);
4674                        // Check that next token is a correct stmt delimiter -
4675                        // disallows "print 1 print 2" and such.
4676                        if (p->lex == BC_LEX_RBRACE)
4677                                break;
4678                        if (p->lex != BC_LEX_SCOLON
4679                         && p->lex != XC_LEX_NLINE
4680                        ) {
4681                                RETURN_STATUS(bc_error_at("bad statement terminator"));
4682                        }
4683                        s = zxc_lex_next();
4684                        if (s) RETURN_STATUS(s);
4685                }
4686                s = zxc_lex_next();
4687                dbg_lex_done("%s:%d done (seen BC_LEX_RBRACE)", __func__, __LINE__);
4688                RETURN_STATUS(s);
4689        }
4690
4691        dbg_lex("%s:%d p->lex:%d", __func__, __LINE__, p->lex);
4692        switch (p->lex) {
4693        case XC_LEX_OP_MINUS:
4694        case BC_LEX_OP_INC:
4695        case BC_LEX_OP_DEC:
4696        case BC_LEX_OP_BOOL_NOT:
4697        case BC_LEX_LPAREN:
4698        case XC_LEX_NAME:
4699        case XC_LEX_NUMBER:
4700        case BC_LEX_KEY_IBASE:
4701        case BC_LEX_KEY_LAST:
4702        case BC_LEX_KEY_LENGTH:
4703        case BC_LEX_KEY_OBASE:
4704        case BC_LEX_KEY_READ:
4705        case BC_LEX_KEY_SCALE:
4706        case BC_LEX_KEY_SQRT:
4707                s = zbc_parse_expr(BC_PARSE_PRINT);
4708                break;
4709        case XC_LEX_STR:
4710                s = zbc_parse_pushSTR();
4711                xc_parse_push(XC_INST_PRINT_STR);
4712                break;
4713        case BC_LEX_KEY_BREAK:
4714        case BC_LEX_KEY_CONTINUE:
4715                s = zbc_parse_break_or_continue(p->lex);
4716                break;
4717        case BC_LEX_KEY_FOR:
4718                s = zbc_parse_for();
4719                break;
4720        case BC_LEX_KEY_HALT:
4721                xc_parse_push(BC_INST_HALT);
4722                s = zxc_lex_next();
4723                break;
4724        case BC_LEX_KEY_IF:
4725                s = zbc_parse_if();
4726                break;
4727        case BC_LEX_KEY_LIMITS:
4728                // "limits" is a compile-time command,
4729                // the output is produced at _parse time_.
4730                printf(
4731                        "BC_BASE_MAX     = "BC_MAX_OBASE_STR "\n"
4732                        "BC_DIM_MAX      = "BC_MAX_DIM_STR   "\n"
4733                        "BC_SCALE_MAX    = "BC_MAX_SCALE_STR "\n"
4734                        "BC_STRING_MAX   = "BC_MAX_STRING_STR"\n"
4735                //      "BC_NUM_MAX      = "BC_MAX_NUM_STR   "\n" - GNU bc does not show this
4736                        "MAX Exponent    = "BC_MAX_EXP_STR   "\n"
4737                        "Number of vars  = "BC_MAX_VARS_STR  "\n"
4738                );
4739                s = zxc_lex_next();
4740                break;
4741        case BC_LEX_KEY_PRINT:
4742                s = zbc_parse_print();
4743                break;
4744        case BC_LEX_KEY_QUIT:
4745                // "quit" is a compile-time command. For example,
4746                // "if (0 == 1) quit" terminates when parsing the statement,
4747                // not when it is executed
4748                QUIT_OR_RETURN_TO_MAIN;
4749        case BC_LEX_KEY_RETURN:
4750                if (!p->in_funcdef)
4751                        RETURN_STATUS(bc_error("'return' not in a function"));
4752                s = zbc_parse_return();
4753                break;
4754        case BC_LEX_KEY_WHILE:
4755                s = zbc_parse_while();
4756                break;
4757        default:
4758                s = bc_error_bad_token();
4759                break;
4760        }
4761
4762        dbg_lex_done("%s:%d done", __func__, __LINE__);
4763        RETURN_STATUS(s);
4764}
4765#define zbc_parse_stmt_possibly_auto(...) (zbc_parse_stmt_possibly_auto(__VA_ARGS__) COMMA_SUCCESS)
4766
4767static BC_STATUS zbc_parse_stmt_or_funcdef(void)
4768{
4769        BcParse *p = &G.prs;
4770        BcStatus s;
4771
4772        dbg_lex_enter("%s:%d entered", __func__, __LINE__);
4773//why?
4774//      if (p->lex == XC_LEX_EOF)
4775//              s = bc_error("end of file");
4776//      else
4777        if (p->lex == BC_LEX_KEY_DEFINE) {
4778                dbg_lex("%s:%d p->lex:BC_LEX_KEY_DEFINE", __func__, __LINE__);
4779                s = zbc_parse_funcdef();
4780        } else {
4781                dbg_lex("%s:%d p->lex:%d (not BC_LEX_KEY_DEFINE)", __func__, __LINE__, p->lex);
4782                s = zbc_parse_stmt();
4783        }
4784
4785        dbg_lex_done("%s:%d done", __func__, __LINE__);
4786        RETURN_STATUS(s);
4787}
4788#define zbc_parse_stmt_or_funcdef(...) (zbc_parse_stmt_or_funcdef(__VA_ARGS__) COMMA_SUCCESS)
4789
4790#undef zbc_parse_expr
4791static BC_STATUS zbc_parse_expr(uint8_t flags)
4792{
4793        BcParse *p = &G.prs;
4794        BcInst prev = XC_INST_PRINT;
4795        size_t nexprs = 0, ops_bgn = p->ops.len;
4796        unsigned nparens, nrelops;
4797        bool paren_first, rprn, assign, bin_last, incdec;
4798
4799        dbg_lex_enter("%s:%d entered", __func__, __LINE__);
4800        paren_first = (p->lex == BC_LEX_LPAREN);
4801        nparens = nrelops = 0;
4802        rprn = assign = incdec = false;
4803        bin_last = true;
4804
4805        for (;;) {
4806                bool get_token;
4807                BcStatus s;
4808                BcLexType t = p->lex;
4809
4810                if (!lex_allowed_in_bc_expr(t))
4811                        break;
4812
4813                dbg_lex("%s:%d t:%d", __func__, __LINE__, t);
4814                get_token = false;
4815                s = BC_STATUS_SUCCESS;
4816                switch (t) {
4817                case BC_LEX_OP_INC:
4818                case BC_LEX_OP_DEC:
4819                        dbg_lex("%s:%d LEX_OP_INC/DEC", __func__, __LINE__);
4820                        if (incdec) RETURN_STATUS(bc_error_bad_assignment());
4821                        s = zbc_parse_incdec(&prev, &nexprs, flags);
4822                        incdec = true;
4823                        rprn = bin_last = false;
4824                        //get_token = false; - already is
4825                        break;
4826                case XC_LEX_OP_MINUS:
4827                        dbg_lex("%s:%d LEX_OP_MINUS", __func__, __LINE__);
4828                        s = zbc_parse_minus(&prev, ops_bgn, rprn, bin_last, &nexprs);
4829                        rprn = false;
4830                        //get_token = false; - already is
4831                        bin_last = (prev == XC_INST_MINUS);
4832                        if (bin_last) incdec = false;
4833                        break;
4834                case BC_LEX_OP_ASSIGN_POWER:
4835                case BC_LEX_OP_ASSIGN_MULTIPLY:
4836                case BC_LEX_OP_ASSIGN_DIVIDE:
4837                case BC_LEX_OP_ASSIGN_MODULUS:
4838                case BC_LEX_OP_ASSIGN_PLUS:
4839                case BC_LEX_OP_ASSIGN_MINUS:
4840                case BC_LEX_OP_ASSIGN:
4841                        dbg_lex("%s:%d LEX_ASSIGNxyz", __func__, __LINE__);
4842                        if (prev != XC_INST_VAR && prev != XC_INST_ARRAY_ELEM
4843                         && prev != XC_INST_SCALE && prev != XC_INST_IBASE
4844                         && prev != XC_INST_OBASE && prev != BC_INST_LAST
4845                        ) {
4846                                RETURN_STATUS(bc_error_bad_assignment());
4847                        }
4848                // Fallthrough.
4849                case XC_LEX_OP_POWER:
4850                case XC_LEX_OP_MULTIPLY:
4851                case XC_LEX_OP_DIVIDE:
4852                case XC_LEX_OP_MODULUS:
4853                case XC_LEX_OP_PLUS:
4854                case XC_LEX_OP_REL_EQ:
4855                case XC_LEX_OP_REL_LE:
4856                case XC_LEX_OP_REL_GE:
4857                case XC_LEX_OP_REL_NE:
4858                case XC_LEX_OP_REL_LT:
4859                case XC_LEX_OP_REL_GT:
4860                case BC_LEX_OP_BOOL_NOT:
4861                case BC_LEX_OP_BOOL_OR:
4862                case BC_LEX_OP_BOOL_AND:
4863                        dbg_lex("%s:%d LEX_OP_xyz", __func__, __LINE__);
4864                        if (t == BC_LEX_OP_BOOL_NOT) {
4865                                if (!bin_last && p->lex_last != BC_LEX_OP_BOOL_NOT)
4866                                        RETURN_STATUS(bc_error_bad_expression());
4867                        } else if (prev == XC_INST_BOOL_NOT) {
4868                                RETURN_STATUS(bc_error_bad_expression());
4869                        }
4870
4871                        nrelops += (t >= XC_LEX_OP_REL_EQ && t <= XC_LEX_OP_REL_GT);
4872                        prev = BC_TOKEN_2_INST(t);
4873                        bc_parse_operator(t, ops_bgn, &nexprs);
4874                        rprn = incdec = false;
4875                        get_token = true;
4876                        bin_last = (t != BC_LEX_OP_BOOL_NOT);
4877                        break;
4878                case BC_LEX_LPAREN:
4879                        dbg_lex("%s:%d LEX_LPAREN", __func__, __LINE__);
4880                        if (BC_PARSE_LEAF(prev, bin_last, rprn))
4881                                RETURN_STATUS(bc_error_bad_expression());
4882                        bc_vec_push(&p->ops, &t);
4883                        nparens++;
4884                        get_token = true;
4885                        rprn = incdec = false;
4886                        break;
4887                case BC_LEX_RPAREN:
4888                        dbg_lex("%s:%d LEX_RPAREN", __func__, __LINE__);
4889//why?
4890//                      if (p->lex_last == BC_LEX_LPAREN) {
4891//                              RETURN_STATUS(bc_error_at("empty expression"));
4892//                      }
4893                        if (bin_last || prev == XC_INST_BOOL_NOT)
4894                                RETURN_STATUS(bc_error_bad_expression());
4895                        if (nparens == 0) {
4896                                goto exit_loop;
4897                        }
4898                        s = zbc_parse_rightParen(ops_bgn, &nexprs);
4899                        nparens--;
4900                        get_token = true;
4901                        rprn = true;
4902                        bin_last = incdec = false;
4903                        break;
4904                case XC_LEX_NAME:
4905                        dbg_lex("%s:%d LEX_NAME", __func__, __LINE__);
4906                        if (BC_PARSE_LEAF(prev, bin_last, rprn))
4907                                RETURN_STATUS(bc_error_bad_expression());
4908                        s = zbc_parse_name(&prev, flags & ~BC_PARSE_NOCALL);
4909                        rprn = (prev == BC_INST_CALL);
4910                        bin_last = false;
4911                        //get_token = false; - already is
4912                        nexprs++;
4913                        break;
4914                case XC_LEX_NUMBER:
4915                        dbg_lex("%s:%d LEX_NUMBER", __func__, __LINE__);
4916                        if (BC_PARSE_LEAF(prev, bin_last, rprn))
4917                                RETURN_STATUS(bc_error_bad_expression());
4918                        xc_parse_pushNUM();
4919                        prev = XC_INST_NUM;
4920                        get_token = true;
4921                        rprn = bin_last = false;
4922                        nexprs++;
4923                        break;
4924                case BC_LEX_KEY_IBASE:
4925                case BC_LEX_KEY_LAST:
4926                case BC_LEX_KEY_OBASE:
4927                        dbg_lex("%s:%d LEX_IBASE/LAST/OBASE", __func__, __LINE__);
4928                        if (BC_PARSE_LEAF(prev, bin_last, rprn))
4929                                RETURN_STATUS(bc_error_bad_expression());
4930                        prev = (char) (t - BC_LEX_KEY_IBASE + XC_INST_IBASE);
4931                        xc_parse_push((char) prev);
4932                        get_token = true;
4933                        rprn = bin_last = false;
4934                        nexprs++;
4935                        break;
4936                case BC_LEX_KEY_LENGTH:
4937                case BC_LEX_KEY_SQRT:
4938                        dbg_lex("%s:%d LEX_LEN/SQRT", __func__, __LINE__);
4939                        if (BC_PARSE_LEAF(prev, bin_last, rprn))
4940                                RETURN_STATUS(bc_error_bad_expression());
4941                        s = zbc_parse_builtin(t, flags, &prev);
4942                        get_token = true;
4943                        rprn = bin_last = incdec = false;
4944                        nexprs++;
4945                        break;
4946                case BC_LEX_KEY_READ:
4947                        dbg_lex("%s:%d LEX_READ", __func__, __LINE__);
4948                        if (BC_PARSE_LEAF(prev, bin_last, rprn))
4949                                RETURN_STATUS(bc_error_bad_expression());
4950                        s = zbc_parse_read();
4951                        prev = XC_INST_READ;
4952                        get_token = true;
4953                        rprn = bin_last = incdec = false;
4954                        nexprs++;
4955                        break;
4956                case BC_LEX_KEY_SCALE:
4957                        dbg_lex("%s:%d LEX_SCALE", __func__, __LINE__);
4958                        if (BC_PARSE_LEAF(prev, bin_last, rprn))
4959                                RETURN_STATUS(bc_error_bad_expression());
4960                        s = zbc_parse_scale(&prev, flags);
4961                        //get_token = false; - already is
4962                        rprn = bin_last = false;
4963                        nexprs++;
4964                        break;
4965                default:
4966                        RETURN_STATUS(bc_error_bad_token());
4967                }
4968
4969                if (s || G_interrupt) // error, or ^C: stop parsing
4970                        RETURN_STATUS(BC_STATUS_FAILURE);
4971                if (get_token) {
4972                        s = zxc_lex_next();
4973                        if (s) RETURN_STATUS(s);
4974                }
4975        }
4976 exit_loop:
4977
4978        while (p->ops.len > ops_bgn) {
4979                BcLexType top = BC_PARSE_TOP_OP(p);
4980                assign = (top >= BC_LEX_OP_ASSIGN_POWER && top <= BC_LEX_OP_ASSIGN);
4981
4982                if (top == BC_LEX_LPAREN || top == BC_LEX_RPAREN)
4983                        RETURN_STATUS(bc_error_bad_expression());
4984
4985                xc_parse_push(BC_TOKEN_2_INST(top));
4986
4987                nexprs -= (top != BC_LEX_OP_BOOL_NOT && top != XC_LEX_NEG);
4988                bc_vec_pop(&p->ops);
4989        }
4990
4991        if (prev == XC_INST_BOOL_NOT || nexprs != 1)
4992                RETURN_STATUS(bc_error_bad_expression());
4993
4994        if (!(flags & BC_PARSE_REL) && nrelops) {
4995                BcStatus s;
4996                s = zbc_POSIX_does_not_allow("comparison operators outside if or loops");
4997                if (s) RETURN_STATUS(s);
4998        } else if ((flags & BC_PARSE_REL) && nrelops > 1) {
4999                BcStatus s;
5000                s = zbc_POSIX_requires("exactly one comparison operator per condition");
5001                if (s) RETURN_STATUS(s);
5002        }
5003
5004        if (flags & BC_PARSE_PRINT) {
5005                if (paren_first || !assign)
5006                        xc_parse_push(XC_INST_PRINT);
5007                xc_parse_push(XC_INST_POP);
5008        }
5009
5010        dbg_lex_done("%s:%d done", __func__, __LINE__);
5011        RETURN_STATUS(BC_STATUS_SUCCESS);
5012}
5013#define zbc_parse_expr(...) (zbc_parse_expr(__VA_ARGS__) COMMA_SUCCESS)
5014
5015#endif // ENABLE_BC
5016
5017#if ENABLE_DC
5018
5019static BC_STATUS zdc_parse_register(void)
5020{
5021        BcParse *p = &G.prs;
5022        BcStatus s;
5023
5024        s = zxc_lex_next();
5025        if (s) RETURN_STATUS(s);
5026        if (p->lex != XC_LEX_NAME) RETURN_STATUS(bc_error_bad_token());
5027
5028        xc_parse_pushName(p->lex_strnumbuf.v);
5029
5030        RETURN_STATUS(s);
5031}
5032#define zdc_parse_register(...) (zdc_parse_register(__VA_ARGS__) COMMA_SUCCESS)
5033
5034static void dc_parse_string(void)
5035{
5036        BcParse *p = &G.prs;
5037        char *str;
5038        size_t len = G.prog.strs.len;
5039
5040        dbg_lex_enter("%s:%d entered", __func__, __LINE__);
5041
5042        str = xstrdup(p->lex_strnumbuf.v);
5043        xc_parse_pushInst_and_Index(XC_INST_STR, len);
5044        bc_vec_push(&G.prog.strs, &str);
5045
5046        // Add an empty function so that if zdc_program_execStr ever needs to
5047        // parse the string into code (from the 'x' command) there's somewhere
5048        // to store the bytecode.
5049        xc_program_add_fn();
5050        p->func = xc_program_func(p->fidx);
5051
5052        dbg_lex_done("%s:%d done", __func__, __LINE__);
5053}
5054
5055static BC_STATUS zdc_parse_mem(uint8_t inst, bool name, bool store)
5056{
5057        BcStatus s;
5058
5059        xc_parse_push(inst);
5060        if (name) {
5061                s = zdc_parse_register();
5062                if (s) RETURN_STATUS(s);
5063        }
5064
5065        if (store) {
5066                xc_parse_push(DC_INST_SWAP);
5067                xc_parse_push(XC_INST_ASSIGN);
5068                xc_parse_push(XC_INST_POP);
5069        }
5070
5071        RETURN_STATUS(BC_STATUS_SUCCESS);
5072}
5073#define zdc_parse_mem(...) (zdc_parse_mem(__VA_ARGS__) COMMA_SUCCESS)
5074
5075static BC_STATUS zdc_parse_cond(uint8_t inst)
5076{
5077        BcParse *p = &G.prs;
5078        BcStatus s;
5079
5080        xc_parse_push(inst);
5081        xc_parse_push(DC_INST_EXEC_COND);
5082
5083        s = zdc_parse_register();
5084        if (s) RETURN_STATUS(s);
5085
5086        s = zxc_lex_next();
5087        if (s) RETURN_STATUS(s);
5088
5089        // Note that 'else' part can not be on the next line:
5090        // echo -e '[1p]sa [2p]sb 2 1>a eb' | dc - OK, prints "2"
5091        // echo -e '[1p]sa [2p]sb 2 1>a\neb' | dc - parse error
5092        if (p->lex == DC_LEX_ELSE) {
5093                s = zdc_parse_register();
5094                if (s) RETURN_STATUS(s);
5095                s = zxc_lex_next();
5096        } else {
5097                xc_parse_push('\0');
5098        }
5099
5100        RETURN_STATUS(s);
5101}
5102#define zdc_parse_cond(...) (zdc_parse_cond(__VA_ARGS__) COMMA_SUCCESS)
5103
5104static BC_STATUS zdc_parse_token(BcLexType t)
5105{
5106        BcStatus s;
5107        uint8_t inst;
5108        bool assign, get_token;
5109
5110        dbg_lex_enter("%s:%d entered", __func__, __LINE__);
5111        s = BC_STATUS_SUCCESS;
5112        get_token = true;
5113        switch (t) {
5114        case XC_LEX_OP_REL_EQ:
5115        case XC_LEX_OP_REL_LE:
5116        case XC_LEX_OP_REL_GE:
5117        case XC_LEX_OP_REL_NE:
5118        case XC_LEX_OP_REL_LT:
5119        case XC_LEX_OP_REL_GT:
5120                dbg_lex("%s:%d LEX_OP_REL_xyz", __func__, __LINE__);
5121                s = zdc_parse_cond(t - XC_LEX_OP_REL_EQ + XC_INST_REL_EQ);
5122                get_token = false;
5123                break;
5124        case DC_LEX_SCOLON:
5125        case DC_LEX_COLON:
5126                dbg_lex("%s:%d LEX_[S]COLON", __func__, __LINE__);
5127                s = zdc_parse_mem(XC_INST_ARRAY_ELEM, true, t == DC_LEX_COLON);
5128                break;
5129        case XC_LEX_STR:
5130                dbg_lex("%s:%d LEX_STR", __func__, __LINE__);
5131                dc_parse_string();
5132                break;
5133        case XC_LEX_NEG:
5134                dbg_lex("%s:%d LEX_NEG", __func__, __LINE__);
5135                s = zxc_lex_next();
5136                if (s) RETURN_STATUS(s);
5137                if (G.prs.lex != XC_LEX_NUMBER)
5138                        RETURN_STATUS(bc_error_bad_token());
5139                xc_parse_pushNUM();
5140                xc_parse_push(XC_INST_NEG);
5141                break;
5142        case XC_LEX_NUMBER:
5143                dbg_lex("%s:%d LEX_NUMBER", __func__, __LINE__);
5144                xc_parse_pushNUM();
5145                break;
5146        case DC_LEX_READ:
5147                dbg_lex("%s:%d LEX_KEY_READ", __func__, __LINE__);
5148                xc_parse_push(XC_INST_READ);
5149                break;
5150        case DC_LEX_OP_ASSIGN:
5151        case DC_LEX_STORE_PUSH:
5152                dbg_lex("%s:%d LEX_OP_ASSIGN/STORE_PUSH", __func__, __LINE__);
5153                assign = (t == DC_LEX_OP_ASSIGN);
5154                inst = assign ? XC_INST_VAR : DC_INST_PUSH_TO_VAR;
5155                s = zdc_parse_mem(inst, true, assign);
5156                break;
5157        case DC_LEX_LOAD:
5158        case DC_LEX_LOAD_POP:
5159                dbg_lex("%s:%d LEX_OP_LOAD[_POP]", __func__, __LINE__);
5160                inst = t == DC_LEX_LOAD_POP ? DC_INST_PUSH_VAR : DC_INST_LOAD;
5161                s = zdc_parse_mem(inst, true, false);
5162                break;
5163        case DC_LEX_STORE_IBASE:
5164        case DC_LEX_STORE_SCALE:
5165        case DC_LEX_STORE_OBASE:
5166                dbg_lex("%s:%d LEX_OP_STORE_I/OBASE/SCALE", __func__, __LINE__);
5167                inst = t - DC_LEX_STORE_IBASE + XC_INST_IBASE;
5168                s = zdc_parse_mem(inst, false, true);
5169                break;
5170        default:
5171                dbg_lex_done("%s:%d done (bad token)", __func__, __LINE__);
5172                RETURN_STATUS(bc_error_bad_token());
5173        }
5174
5175        if (!s && get_token) s = zxc_lex_next();
5176
5177        dbg_lex_done("%s:%d done", __func__, __LINE__);
5178        RETURN_STATUS(s);
5179}
5180#define zdc_parse_token(...) (zdc_parse_token(__VA_ARGS__) COMMA_SUCCESS)
5181
5182static BC_STATUS zdc_parse_expr(void)
5183{
5184        BcParse *p = &G.prs;
5185        int i;
5186
5187        if (p->lex == XC_LEX_NLINE)
5188                RETURN_STATUS(zxc_lex_next());
5189
5190        i = (int)p->lex - (int)XC_LEX_OP_POWER;
5191        if (i >= 0) {
5192                BcInst inst = dc_LEX_to_INST[i];
5193                if (inst != DC_INST_INVALID) {
5194                        xc_parse_push(inst);
5195                        RETURN_STATUS(zxc_lex_next());
5196                }
5197        }
5198        RETURN_STATUS(zdc_parse_token(p->lex));
5199}
5200#define zdc_parse_expr(...) (zdc_parse_expr(__VA_ARGS__) COMMA_SUCCESS)
5201
5202static BC_STATUS zdc_parse_exprs_until_eof(void)
5203{
5204        BcParse *p = &G.prs;
5205        dbg_lex_enter("%s:%d entered, p->lex:%d", __func__, __LINE__, p->lex);
5206        while (p->lex != XC_LEX_EOF) {
5207                BcStatus s = zdc_parse_expr();
5208                if (s) RETURN_STATUS(s);
5209        }
5210
5211        dbg_lex_done("%s:%d done", __func__, __LINE__);
5212        RETURN_STATUS(BC_STATUS_SUCCESS);
5213}
5214#define zdc_parse_exprs_until_eof(...) (zdc_parse_exprs_until_eof(__VA_ARGS__) COMMA_SUCCESS)
5215
5216#endif // ENABLE_DC
5217
5218//
5219// Execution engine
5220//
5221
5222#define BC_PROG_STR(n) (!(n)->num && !(n)->cap)
5223#define BC_PROG_NUM(r, n) \
5224        ((r)->t != XC_RESULT_ARRAY && (r)->t != XC_RESULT_STR && !BC_PROG_STR(n))
5225
5226#define STACK_HAS_MORE_THAN(s, n)          ((s)->len > ((size_t)(n)))
5227#define STACK_HAS_EQUAL_OR_MORE_THAN(s, n) ((s)->len >= ((size_t)(n)))
5228
5229static size_t xc_program_index(char *code, size_t *bgn)
5230{
5231        unsigned char *bytes = (void*)(code + *bgn);
5232        unsigned amt;
5233        unsigned i;
5234        size_t res;
5235
5236        amt = *bytes++;
5237        if (amt < SMALL_INDEX_LIMIT) {
5238                *bgn += 1;
5239                return amt;
5240        }
5241        amt -= (SMALL_INDEX_LIMIT - 1); // amt is 1 or more here
5242        *bgn += amt + 1;
5243
5244        res = 0;
5245        i = 0;
5246        do {
5247                res |= (size_t)(*bytes++) << i;
5248                i += 8;
5249        } while (--amt != 0);
5250
5251        return res;
5252}
5253
5254static char *xc_program_name(char *code, size_t *bgn)
5255{
5256        code += *bgn;
5257        *bgn += strlen(code) + 1;
5258
5259        return xstrdup(code);
5260}
5261
5262static BcVec* xc_program_dereference(BcVec *vec)
5263{
5264        BcVec *v;
5265        size_t vidx, nidx, i = 0;
5266
5267        //assert(vec->size == sizeof(uint8_t));
5268
5269        vidx = xc_program_index(vec->v, &i);
5270        nidx = xc_program_index(vec->v, &i);
5271
5272        v = bc_vec_item(&G.prog.arrs, vidx);
5273        v = bc_vec_item(v, nidx);
5274
5275        //assert(v->size != sizeof(uint8_t));
5276
5277        return v;
5278}
5279
5280static BcVec* xc_program_search(char *id, BcType type)
5281{
5282        BcId e, *ptr;
5283        BcVec *v, *map;
5284        size_t i;
5285        int new;
5286        bool var = (type == BC_TYPE_VAR);
5287
5288        v = var ? &G.prog.vars : &G.prog.arrs;
5289        map = var ? &G.prog.var_map : &G.prog.arr_map;
5290
5291        e.name = id;
5292        e.idx = v->len;
5293        new = bc_map_insert(map, &e, &i); // 1 if insertion was successful
5294
5295        if (new) {
5296                BcVec v2;
5297                bc_array_init(&v2, var);
5298                bc_vec_push(v, &v2);
5299        }
5300
5301        ptr = bc_vec_item(map, i);
5302        if (new) ptr->name = xstrdup(e.name);
5303        return bc_vec_item(v, ptr->idx);
5304}
5305
5306// 'num' need not be initialized on entry
5307static BC_STATUS zxc_program_num(BcResult *r, BcNum **num)
5308{
5309        switch (r->t) {
5310        case XC_RESULT_STR:
5311        case XC_RESULT_TEMP:
5312        IF_BC(case BC_RESULT_VOID:)
5313        case XC_RESULT_IBASE:
5314        case XC_RESULT_SCALE:
5315        case XC_RESULT_OBASE:
5316                *num = &r->d.n;
5317                break;
5318        case XC_RESULT_CONSTANT: {
5319                BcStatus s;
5320                char *str;
5321                size_t len;
5322
5323                str = *xc_program_const(r->d.id.idx);
5324                len = strlen(str);
5325
5326                bc_num_init(&r->d.n, len);
5327
5328                s = zxc_num_parse(&r->d.n, str, G.prog.ib_t);
5329                if (s) {
5330                        bc_num_free(&r->d.n);
5331                        RETURN_STATUS(s);
5332                }
5333                *num = &r->d.n;
5334                r->t = XC_RESULT_TEMP;
5335                break;
5336        }
5337        case XC_RESULT_VAR:
5338        case XC_RESULT_ARRAY:
5339        case XC_RESULT_ARRAY_ELEM: {
5340                BcType type = (r->t == XC_RESULT_VAR) ? BC_TYPE_VAR : BC_TYPE_ARRAY;
5341                BcVec *v = xc_program_search(r->d.id.name, type);
5342                void *p = bc_vec_top(v);
5343
5344                if (r->t == XC_RESULT_ARRAY_ELEM) {
5345                        size_t idx = r->d.id.idx;
5346
5347                        v = p;
5348                        if (v->size == sizeof(uint8_t))
5349                                v = xc_program_dereference(v);
5350                        //assert(v->size == sizeof(BcNum));
5351                        if (v->len <= idx)
5352                                bc_array_expand(v, idx + 1);
5353                        *num = bc_vec_item(v, idx);
5354                } else {
5355                        *num = p;
5356                }
5357                break;
5358        }
5359#if ENABLE_BC
5360        case BC_RESULT_LAST:
5361                *num = &G.prog.last;
5362                break;
5363        case BC_RESULT_ONE:
5364                *num = &G.prog.one;
5365                break;
5366#endif
5367#if SANITY_CHECKS
5368        default:
5369                // Testing the theory that dc does not reach LAST/ONE
5370                bb_error_msg_and_die("BUG:%d", r->t);
5371#endif
5372        }
5373
5374        RETURN_STATUS(BC_STATUS_SUCCESS);
5375}
5376#define zxc_program_num(...) (zxc_program_num(__VA_ARGS__) COMMA_SUCCESS)
5377
5378static BC_STATUS zxc_program_binOpPrep(BcResult **l, BcNum **ln,
5379                                     BcResult **r, BcNum **rn, bool assign)
5380{
5381        BcStatus s;
5382        BcResultType lt, rt;
5383
5384        if (!STACK_HAS_MORE_THAN(&G.prog.results, 1))
5385                RETURN_STATUS(bc_error_stack_has_too_few_elements());
5386
5387        *r = bc_vec_item_rev(&G.prog.results, 0);
5388        *l = bc_vec_item_rev(&G.prog.results, 1);
5389
5390        s = zxc_program_num(*l, ln);
5391        if (s) RETURN_STATUS(s);
5392        s = zxc_program_num(*r, rn);
5393        if (s) RETURN_STATUS(s);
5394
5395        lt = (*l)->t;
5396        rt = (*r)->t;
5397
5398        // We run this again under these conditions in case any vector has been
5399        // reallocated out from under the BcNums or arrays we had.
5400        if (lt == rt && (lt == XC_RESULT_VAR || lt == XC_RESULT_ARRAY_ELEM)) {
5401                s = zxc_program_num(*l, ln);
5402                if (s) RETURN_STATUS(s);
5403        }
5404
5405        if (!BC_PROG_NUM((*l), (*ln)) && (!assign || (*l)->t != XC_RESULT_VAR))
5406                RETURN_STATUS(bc_error_variable_is_wrong_type());
5407        if (!assign && !BC_PROG_NUM((*r), (*ln)))
5408                RETURN_STATUS(bc_error_variable_is_wrong_type());
5409
5410        RETURN_STATUS(s);
5411}
5412#define zxc_program_binOpPrep(...) (zxc_program_binOpPrep(__VA_ARGS__) COMMA_SUCCESS)
5413
5414static void xc_program_binOpRetire(BcResult *r)
5415{
5416        r->t = XC_RESULT_TEMP;
5417        bc_vec_pop(&G.prog.results);
5418        bc_result_pop_and_push(r);
5419}
5420
5421// Note: *r and *n need not be initialized by caller
5422static BC_STATUS zxc_program_prep(BcResult **r, BcNum **n)
5423{
5424        BcStatus s;
5425
5426        if (!STACK_HAS_MORE_THAN(&G.prog.results, 0))
5427                RETURN_STATUS(bc_error_stack_has_too_few_elements());
5428        *r = bc_vec_top(&G.prog.results);
5429
5430        s = zxc_program_num(*r, n);
5431        if (s) RETURN_STATUS(s);
5432
5433        if (!BC_PROG_NUM((*r), (*n)))
5434                RETURN_STATUS(bc_error_variable_is_wrong_type());
5435
5436        RETURN_STATUS(s);
5437}
5438#define zxc_program_prep(...) (zxc_program_prep(__VA_ARGS__) COMMA_SUCCESS)
5439
5440static void xc_program_retire(BcResult *r, BcResultType t)
5441{
5442        r->t = t;
5443        bc_result_pop_and_push(r);
5444}
5445
5446static BC_STATUS zxc_program_op(char inst)
5447{
5448        BcStatus s;
5449        BcResult *opd1, *opd2, res;
5450        BcNum *n1, *n2;
5451
5452        s = zxc_program_binOpPrep(&opd1, &n1, &opd2, &n2, false);
5453        if (s) RETURN_STATUS(s);
5454        bc_num_init_DEF_SIZE(&res.d.n);
5455
5456        s = BC_STATUS_SUCCESS;
5457        IF_ERROR_RETURN_POSSIBLE(s =) zxc_program_ops[inst - XC_INST_POWER](n1, n2, &res.d.n, G.prog.scale);
5458        if (s) goto err;
5459        xc_program_binOpRetire(&res);
5460
5461        RETURN_STATUS(s);
5462 err:
5463        bc_num_free(&res.d.n);
5464        RETURN_STATUS(s);
5465}
5466#define zxc_program_op(...) (zxc_program_op(__VA_ARGS__) COMMA_SUCCESS)
5467
5468static BC_STATUS zxc_program_read(void)
5469{
5470        BcStatus s;
5471        BcParse sv_parse;
5472        BcVec buf;
5473        BcInstPtr ip;
5474        BcFunc *f;
5475
5476        bc_char_vec_init(&buf);
5477        xc_read_line(&buf, stdin);
5478
5479        f = xc_program_func(BC_PROG_READ);
5480        bc_vec_pop_all(&f->code);
5481
5482        sv_parse = G.prs; // struct copy
5483        xc_parse_create(BC_PROG_READ);
5484        //G.err_line = G.prs.lex_line = 1; - not needed, error line info is not printed for read()
5485
5486        s = zxc_parse_text_init(buf.v);
5487        if (s) goto exec_err;
5488        if (IS_BC) {
5489                IF_BC(s = zbc_parse_expr(0));
5490        } else {
5491                IF_DC(s = zdc_parse_exprs_until_eof());
5492        }
5493        if (s) goto exec_err;
5494        if (G.prs.lex != XC_LEX_NLINE && G.prs.lex != XC_LEX_EOF) {
5495                s = bc_error_at("bad read() expression");
5496                goto exec_err;
5497        }
5498        xc_parse_push(XC_INST_RET);
5499
5500        ip.func = BC_PROG_READ;
5501        ip.inst_idx = 0;
5502        bc_vec_push(&G.prog.exestack, &ip);
5503
5504 exec_err:
5505        xc_parse_free();
5506        G.prs = sv_parse; // struct copy
5507        bc_vec_free(&buf);
5508        RETURN_STATUS(s);
5509}
5510#define zxc_program_read(...) (zxc_program_read(__VA_ARGS__) COMMA_SUCCESS)
5511
5512static void xc_program_printString(const char *str)
5513{
5514#if ENABLE_DC
5515        if (!str[0] && IS_DC) {
5516                // Example: echo '[]ap' | dc
5517                // should print two bytes: 0x00, 0x0A
5518                bb_putchar('\0');
5519                return;
5520        }
5521#endif
5522        while (*str) {
5523                char c = *str++;
5524                if (c == '\\') {
5525                        static const char esc[] ALIGN1 = "nabfrt""e\\";
5526                        char *n;
5527
5528                        c = *str++;
5529                        n = strchr(esc, c); // note: if c is NUL, n = \0 at end of esc
5530                        if (!n || !c) {
5531                                // Just print the backslash and following character
5532                                bb_putchar('\\');
5533                                ++G.prog.nchars;
5534                                // But if we're at the end of the string, stop
5535                                if (!c) break;
5536                        } else {
5537                                if (n - esc == 0) // "\n" ?
5538                                        G.prog.nchars = SIZE_MAX;
5539                                c = "\n\a\b\f\r\t""\\\\""\\"[n - esc];
5540                                //   n a b f r t   e \   \<end of line>
5541                        }
5542                }
5543                putchar(c);
5544                ++G.prog.nchars;
5545        }
5546}
5547
5548static void bc_num_printNewline(void)
5549{
5550        if (G.prog.nchars == G.prog.len - 1) {
5551                bb_putchar('\\');
5552                bb_putchar('\n');
5553                G.prog.nchars = 0;
5554        }
5555}
5556
5557#if ENABLE_DC
5558static FAST_FUNC void dc_num_printChar(size_t num, size_t width, bool radix)
5559{
5560        (void) radix;
5561        bb_putchar((char) num);
5562        G.prog.nchars += width;
5563}
5564#endif
5565
5566static FAST_FUNC void bc_num_printDigits(size_t num, size_t width, bool radix)
5567{
5568        size_t exp, pow;
5569
5570        bc_num_printNewline();
5571        bb_putchar(radix ? '.' : ' ');
5572        ++G.prog.nchars;
5573
5574        bc_num_printNewline();
5575        for (exp = 0, pow = 1; exp < width - 1; ++exp, pow *= 10)
5576                continue;
5577
5578        for (exp = 0; exp < width; pow /= 10, ++G.prog.nchars, ++exp) {
5579                size_t dig;
5580                bc_num_printNewline();
5581                dig = num / pow;
5582                num -= dig * pow;
5583                bb_putchar(((char) dig) + '0');
5584        }
5585}
5586
5587static FAST_FUNC void bc_num_printHex(size_t num, size_t width, bool radix)
5588{
5589        if (radix) {
5590                bc_num_printNewline();
5591                bb_putchar('.');
5592                G.prog.nchars++;
5593        }
5594
5595        bc_num_printNewline();
5596        bb_putchar(bb_hexdigits_upcase[num]);
5597        G.prog.nchars += width;
5598}
5599
5600static void bc_num_printDecimal(BcNum *n)
5601{
5602        size_t i, rdx = n->rdx - 1;
5603
5604        if (n->neg) {
5605                bb_putchar('-');
5606                G.prog.nchars++;
5607        }
5608
5609        for (i = n->len - 1; i < n->len; --i)
5610                bc_num_printHex((size_t) n->num[i], 1, i == rdx);
5611}
5612
5613typedef void (*BcNumDigitOp)(size_t, size_t, bool)