miscutils/bc.c

   1 /* vi: set sw=4 ts=4: */
   2 /*
   3  * Licensed under GPLv2 or later, see file LICENSE in this source tree.
   4  * Copyright (c) 2018 Gavin D. Howard and contributors.
   5  *
   6  * ** Automatically generated from https://github.com/gavinhoward/bc **
   7  * **        Do not edit unless you know what you are doing.         **
   8  */
   9 //config:config BC
  10 //config:       bool "bc (45 kb; 49 kb when combined with dc)"
  11 //config:       default y
  12 //config:       help
  13 //config:       bc is a command-line, arbitrary-precision calculator with a
  14 //config:       Turing-complete language. See the GNU bc manual
  15 //config:       (https://www.gnu.org/software/bc/manual/bc.html) and bc spec
  16 //config:       (http://pubs.opengroup.org/onlinepubs/9699919799/utilities/bc.html)
  17 //config:       for details.
  18 //config:
  19 //config:       This bc has four differences to the GNU bc:
  20 //config:
  21 //config:         1) The period (.) can also be used as a shortcut for "last", as in
  22 //config:            the BSD bc.
  23 //config:         2) Arrays are copied before being passed as arguments to
  24 //config:            functions. This behavior is required by the bc spec.
  25 //config:         3) Arrays can be passed to the builtin "length" function to get
  26 //config:            the number of elements currently in the array. The following
  27 //config:            example prints "1":
  28 //config:
  29 //config:              a[0] = 0
  30 //config:              length(a[])
  31 //config:
  32 //config:         4) The precedence of the boolean "not" operator (!) is equal to
  33 //config:            that of the unary minus (-), or negation, operator. This still
  34 //config:            allows POSIX-compliant scripts to work while somewhat
  35 //config:            preserving expected behavior (versus C) and making parsing
  36 //config:            easier.
  37 //config:
  38 //config:       Options:
  39 //config:
  40 //config:         -i  --interactive  force interactive mode
  41 //config:         -l  --mathlib      use predefined math routines:
  42 //config:
  43 //config:                              s(expr)  =  sine of expr in radians
  44 //config:                              c(expr)  =  cosine of expr in radians
  45 //config:                              a(expr)  =  arctangent of expr, returning
  46 //config:                                          radians
  47 //config:                              l(expr)  =  natural log of expr
  48 //config:                              e(expr)  =  raises e to the power of expr
  49 //config:                              j(n, x)  =  Bessel function of integer order
  50 //config:                                          n of x
  51 //config:
  52 //config:         -q  --quiet        don't print version and copyright.
  53 //config:         -s  --standard     error if any non-POSIX extensions are used.
  54 //config:         -w  --warn         warn if any non-POSIX extensions are used.
  55 //config:         -v  --version      print version and copyright and exit.
  56 //config:
  57 //config:       Long options are only available if FEATURE_BC_LONG_OPTIONS is
  58 //config:       enabled.
  59 //config:
  60 //config:config DC
  61 //config:       bool "dc (38 kb; 49 kb when combined with bc)"
  62 //config:       default y
  63 //config:       help
  64 //config:       dc is a reverse-polish notation command-line calculator which
  65 //config:       supports unlimited precision arithmetic. See the FreeBSD man page
  66 //config:       (https://www.unix.com/man-page/FreeBSD/1/dc/) and GNU dc manual
  67 //config:       (https://www.gnu.org/software/bc/manual/dc-1.05/html_mono/dc.html)
  68 //config:       for details.
  69 //config:
  70 //config:       This dc has a few differences from the two above:
  71 //config:
  72 //config:         1) When printing a byte stream (command "P"), this bc follows what
  73 //config:            the FreeBSD dc does.
  74 //config:         2) This dc implements the GNU extensions for divmod ("~") and
  75 //config:            modular exponentiation ("|").
  76 //config:         3) This dc implements all FreeBSD extensions, except for "J" and
  77 //config:            "M".
  78 //config:         4) Like the FreeBSD dc, this dc supports extended registers.
  79 //config:            However, they are implemented differently. When it encounters
  80 //config:            whitespace where a register should be, it skips the whitespace.
  81 //config:            If the character following is not a lowercase letter, an error
  82 //config:            is issued. Otherwise, the register name is parsed by the
  83 //config:            following regex:
  84 //config:
  85 //config:              [a-z][a-z0-9_]*
  86 //config:
  87 //config:            This generally means that register names will be surrounded by
  88 //config:            whitespace.
  89 //config:
  90 //config:            Examples:
  91 //config:
  92 //config:              l idx s temp L index S temp2 < do_thing
  93 //config:
  94 //config:            Also note that, like the FreeBSD dc, extended registers are not
  95 //config:            allowed unless the "-x" option is given.
  96 //config:
  97 //config:config FEATURE_BC_SIGNALS
  98 //config:       bool "Enable bc/dc signal handling"
  99 //config:       default y
 100 //config:       depends on BC || DC
 101 //config:       help
 102 //config:       Enable signal handling for bc and dc.
 103 //config:
 104 //config:config FEATURE_BC_LONG_OPTIONS
 105 //config:       bool "Enable bc/dc long options"
 106 //config:       default y
 107 //config:       depends on BC || DC
 108 //config:       help
 109 //config:       Enable long options for bc and dc.
 110
 111 //applet:IF_BC(APPLET(bc, BB_DIR_USR_BIN, BB_SUID_DROP))
 112 //applet:IF_DC(APPLET(dc, BB_DIR_USR_BIN, BB_SUID_DROP))
 113
 114 //kbuild:lib-$(CONFIG_BC) += bc.o
 115 //kbuild:lib-$(CONFIG_DC) += bc.o
 116
 117 //See www.gnu.org/software/bc/manual/bc.html
 118 //usage:#define bc_trivial_usage
 119 //usage:       "[-sqli] FILE..."
 120 //usage:
 121 //usage:#define bc_full_usage "\n"
 122 //usage:     "\nArbitrary precision calculator"
 123 //usage:     "\n"
 124 //usage:     "\n        -i      Interactive"
 125 //usage:     "\n        -l      Load standard math library"
 126 //usage:     "\n        -s      Be POSIX compatible"
 127 //usage:     "\n        -q      Quiet"
 128 //usage:     "\n        -w      Warn if extensions are used"
 129 ///////:     "\n        -v      Version"
 130 //usage:
 131 //usage:#define bc_example_usage
 132 //usage:       "3 + 4.129\n"
 133 //usage:       "1903 - 2893\n"
 134 //usage:       "-129 * 213.28935\n"
 135 //usage:       "12 / -1932\n"
 136 //usage:       "12 % 12\n"
 137 //usage:       "34 ^ 189\n"
 138 //usage:       "scale = 13\n"
 139 //usage:       "ibase = 2\n"
 140 //usage:       "obase = A\n"
 141 //usage:
 142 //usage:#define dc_trivial_usage
 143 //usage:       "EXPRESSION..."
 144 //usage:
 145 //usage:#define dc_full_usage "\n\n"
 146 //usage:       "Tiny RPN calculator. Operations:\n"
 147 //usage:       "+, add, -, sub, *, mul, /, div, %, mod, ^, exp, ~, divmod, |, "
 148 //usage:       "modular exponentiation,\n"
 149 //usage:       "p - print top of the stack (without popping),\n"
 150 //usage:       "f - print entire stack,\n"
 151 //usage:       "k - pop the value and set the precision.\n"
 152 //usage:       "i - pop the value and set input radix.\n"
 153 //usage:       "o - pop the value and set output radix.\n"
 154 //usage:       "Examples: 'dc 2 2 add p' -> 4, 'dc 8 8 mul 2 2 + / p' -> 16"
 155 //usage:
 156 //usage:#define dc_example_usage
 157 //usage:       "$ dc 2 2 + p\n"
 158 //usage:       "4\n"
 159 //usage:       "$ dc 8 8 \\* 2 2 + / p\n"
 160 //usage:       "16\n"
 161 //usage:       "$ dc 0 1 and p\n"
 162 //usage:       "0\n"
 163 //usage:       "$ dc 0 1 or p\n"
 164 //usage:       "1\n"
 165 //usage:       "$ echo 72 9 div 8 mul p | dc\n"
 166 //usage:       "64\n"
 167
 168 #include "libbb.h"
 169
 170 typedef enum BcStatus {
 171         BC_STATUS_SUCCESS = 0,
 172         BC_STATUS_FAILURE = 1,
 173         BC_STATUS_PARSE_EMPTY_EXP = 2, // bc_parse_expr() uses this
 174 } BcStatus;
 175
 176 #define BC_VEC_INVALID_IDX ((size_t) -1)
 177 #define BC_VEC_START_CAP (1 << 5)
 178
 179 typedef void (*BcVecFree)(void *);
 180
 181 typedef struct BcVec {
 182         char *v;
 183         size_t len;
 184         size_t cap;
 185         size_t size;
 186         BcVecFree dtor;
 187 } BcVec;
 188
 189 #define bc_vec_pop(v) (bc_vec_npop((v), 1))
 190 #define bc_vec_top(v) (bc_vec_item_rev((v), 0))
 191
 192 typedef signed char BcDig;
 193
 194 typedef struct BcNum {
 195         BcDig *restrict num;
 196         size_t rdx;
 197         size_t len;
 198         size_t cap;
 199         bool neg;
 200 } BcNum;
 201
 202 #define BC_NUM_MIN_BASE ((unsigned long) 2)
 203 #define BC_NUM_MAX_IBASE ((unsigned long) 16)
 204 #define BC_NUM_DEF_SIZE (16)
 205 #define BC_NUM_PRINT_WIDTH (69)
 206
 207 #define BC_NUM_KARATSUBA_LEN (32)
 208
 209 #define BC_NUM_NEG(n, neg) ((((ssize_t)(n)) ^ -((ssize_t)(neg))) + (neg))
 210 #define BC_NUM_ONE(n) ((n)->len == 1 && (n)->rdx == 0 && (n)->num[0] == 1)
 211 #define BC_NUM_INT(n) ((n)->len - (n)->rdx)
 212 #define BC_NUM_AREQ(a, b) \
 213         (BC_MAX((a)->rdx, (b)->rdx) + BC_MAX(BC_NUM_INT(a), BC_NUM_INT(b)) + 1)
 214 #define BC_NUM_MREQ(a, b, scale) \
 215         (BC_NUM_INT(a) + BC_NUM_INT(b) + BC_MAX((scale), (a)->rdx + (b)->rdx) + 1)
 216
 217 typedef BcStatus (*BcNumBinaryOp)(BcNum *, BcNum *, BcNum *, size_t);
 218 typedef void (*BcNumDigitOp)(size_t, size_t, bool, size_t *, size_t);
 219
 220 static void bc_num_init(BcNum *n, size_t req);
 221 static void bc_num_expand(BcNum *n, size_t req);
 222 static void bc_num_copy(BcNum *d, BcNum *s);
 223 static void bc_num_free(void *num);
 224
 225 static BcStatus bc_num_ulong(BcNum *n, unsigned long *result);
 226 static void bc_num_ulong2num(BcNum *n, unsigned long val);
 227
 228 static BcStatus bc_num_add(BcNum *a, BcNum *b, BcNum *c, size_t scale);
 229 static BcStatus bc_num_sub(BcNum *a, BcNum *b, BcNum *c, size_t scale);
 230 static BcStatus bc_num_mul(BcNum *a, BcNum *b, BcNum *c, size_t scale);
 231 static BcStatus bc_num_div(BcNum *a, BcNum *b, BcNum *c, size_t scale);
 232 static BcStatus bc_num_mod(BcNum *a, BcNum *b, BcNum *c, size_t scale);
 233 static BcStatus bc_num_pow(BcNum *a, BcNum *b, BcNum *c, size_t scale);
 234 static BcStatus bc_num_sqrt(BcNum *a, BcNum *b, size_t scale);
 235 static BcStatus bc_num_divmod(BcNum *a, BcNum *b, BcNum *c, BcNum *d,
 236                               size_t scale);
 237
 238 typedef enum BcInst {
 239
 240 #if ENABLE_BC
 241         BC_INST_INC_PRE,
 242         BC_INST_DEC_PRE,
 243         BC_INST_INC_POST,
 244         BC_INST_DEC_POST,
 245 #endif
 246
 247         BC_INST_NEG,
 248
 249         BC_INST_POWER,
 250         BC_INST_MULTIPLY,
 251         BC_INST_DIVIDE,
 252         BC_INST_MODULUS,
 253         BC_INST_PLUS,
 254         BC_INST_MINUS,
 255
 256         BC_INST_REL_EQ,
 257         BC_INST_REL_LE,
 258         BC_INST_REL_GE,
 259         BC_INST_REL_NE,
 260         BC_INST_REL_LT,
 261         BC_INST_REL_GT,
 262
 263         BC_INST_BOOL_NOT,
 264         BC_INST_BOOL_OR,
 265         BC_INST_BOOL_AND,
 266
 267 #if ENABLE_BC
 268         BC_INST_ASSIGN_POWER,
 269         BC_INST_ASSIGN_MULTIPLY,
 270         BC_INST_ASSIGN_DIVIDE,
 271         BC_INST_ASSIGN_MODULUS,
 272         BC_INST_ASSIGN_PLUS,
 273         BC_INST_ASSIGN_MINUS,
 274 #endif
 275         BC_INST_ASSIGN,
 276
 277         BC_INST_NUM,
 278         BC_INST_VAR,
 279         BC_INST_ARRAY_ELEM,
 280         BC_INST_ARRAY,
 281
 282         BC_INST_SCALE_FUNC,
 283         BC_INST_IBASE,
 284         BC_INST_SCALE,
 285         BC_INST_LAST,
 286         BC_INST_LENGTH,
 287         BC_INST_READ,
 288         BC_INST_OBASE,
 289         BC_INST_SQRT,
 290
 291         BC_INST_PRINT,
 292         BC_INST_PRINT_POP,
 293         BC_INST_STR,
 294         BC_INST_PRINT_STR,
 295
 296 #if ENABLE_BC
 297         BC_INST_JUMP,
 298         BC_INST_JUMP_ZERO,
 299
 300         BC_INST_CALL,
 301
 302         BC_INST_RET,
 303         BC_INST_RET0,
 304
 305         BC_INST_HALT,
 306 #endif
 307
 308         BC_INST_POP,
 309         BC_INST_POP_EXEC,
 310
 311 #if ENABLE_DC
 312         BC_INST_MODEXP,
 313         BC_INST_DIVMOD,
 314
 315         BC_INST_EXECUTE,
 316         BC_INST_EXEC_COND,
 317
 318         BC_INST_ASCIIFY,
 319         BC_INST_PRINT_STREAM,
 320
 321         BC_INST_PRINT_STACK,
 322         BC_INST_CLEAR_STACK,
 323         BC_INST_STACK_LEN,
 324         BC_INST_DUPLICATE,
 325         BC_INST_SWAP,
 326
 327         BC_INST_LOAD,
 328         BC_INST_PUSH_VAR,
 329         BC_INST_PUSH_TO_VAR,
 330
 331         BC_INST_QUIT,
 332         BC_INST_NQUIT,
 333
 334         BC_INST_INVALID = -1,
 335 #endif
 336
 337 } BcInst;
 338
 339 typedef struct BcId {
 340         char *name;
 341         size_t idx;
 342 } BcId;
 343
 344 typedef struct BcFunc {
 345         BcVec code;
 346         BcVec labels;
 347         size_t nparams;
 348         BcVec autos;
 349 } BcFunc;
 350
 351 typedef enum BcResultType {
 352
 353         BC_RESULT_TEMP,
 354
 355         BC_RESULT_VAR,
 356         BC_RESULT_ARRAY_ELEM,
 357         BC_RESULT_ARRAY,
 358
 359         BC_RESULT_STR,
 360
 361         BC_RESULT_IBASE,
 362         BC_RESULT_SCALE,
 363         BC_RESULT_LAST,
 364
 365         // These are between to calculate ibase, obase, and last from instructions.
 366         BC_RESULT_CONSTANT,
 367         BC_RESULT_ONE,
 368
 369         BC_RESULT_OBASE,
 370
 371 } BcResultType;
 372
 373 typedef union BcResultData {
 374         BcNum n;
 375         BcVec v;
 376         BcId id;
 377 } BcResultData;
 378
 379 typedef struct BcResult {
 380         BcResultType t;
 381         BcResultData d;
 382 } BcResult;
 383
 384 typedef struct BcInstPtr {
 385         size_t func;
 386         size_t idx;
 387         size_t len;
 388 } BcInstPtr;
 389
 390 static void bc_array_expand(BcVec *a, size_t len);
 391 static int bc_id_cmp(const void *e1, const void *e2);
 392
 393 // BC_LEX_NEG is not used in lexing; it is only for parsing.
 394 typedef enum BcLexType {
 395
 396         BC_LEX_EOF,
 397         BC_LEX_INVALID,
 398
 399         BC_LEX_OP_INC,
 400         BC_LEX_OP_DEC,
 401
 402         BC_LEX_NEG,
 403
 404         BC_LEX_OP_POWER,
 405         BC_LEX_OP_MULTIPLY,
 406         BC_LEX_OP_DIVIDE,
 407         BC_LEX_OP_MODULUS,
 408         BC_LEX_OP_PLUS,
 409         BC_LEX_OP_MINUS,
 410
 411         BC_LEX_OP_REL_EQ,
 412         BC_LEX_OP_REL_LE,
 413         BC_LEX_OP_REL_GE,
 414         BC_LEX_OP_REL_NE,
 415         BC_LEX_OP_REL_LT,
 416         BC_LEX_OP_REL_GT,
 417
 418         BC_LEX_OP_BOOL_NOT,
 419         BC_LEX_OP_BOOL_OR,
 420         BC_LEX_OP_BOOL_AND,
 421
 422         BC_LEX_OP_ASSIGN_POWER,
 423         BC_LEX_OP_ASSIGN_MULTIPLY,
 424         BC_LEX_OP_ASSIGN_DIVIDE,
 425         BC_LEX_OP_ASSIGN_MODULUS,
 426         BC_LEX_OP_ASSIGN_PLUS,
 427         BC_LEX_OP_ASSIGN_MINUS,
 428         BC_LEX_OP_ASSIGN,
 429
 430         BC_LEX_NLINE,
 431         BC_LEX_WHITESPACE,
 432
 433         BC_LEX_LPAREN,
 434         BC_LEX_RPAREN,
 435
 436         BC_LEX_LBRACKET,
 437         BC_LEX_COMMA,
 438         BC_LEX_RBRACKET,
 439
 440         BC_LEX_LBRACE,
 441         BC_LEX_SCOLON,
 442         BC_LEX_RBRACE,
 443
 444         BC_LEX_STR,
 445         BC_LEX_NAME,
 446         BC_LEX_NUMBER,
 447
 448         BC_LEX_KEY_1st_keyword,
 449         BC_LEX_KEY_AUTO = BC_LEX_KEY_1st_keyword,
 450         BC_LEX_KEY_BREAK,
 451         BC_LEX_KEY_CONTINUE,
 452         BC_LEX_KEY_DEFINE,
 453         BC_LEX_KEY_ELSE,
 454         BC_LEX_KEY_FOR,
 455         BC_LEX_KEY_HALT,
 456         // code uses "type - BC_LEX_KEY_IBASE + BC_INST_IBASE" construct,
 457         BC_LEX_KEY_IBASE,  // relative order should match for: BC_INST_IBASE
 458         BC_LEX_KEY_IF,
 459         BC_LEX_KEY_LAST,   // relative order should match for: BC_INST_LAST
 460         BC_LEX_KEY_LENGTH,
 461         BC_LEX_KEY_LIMITS,
 462         BC_LEX_KEY_OBASE,  // relative order should match for: BC_INST_OBASE
 463         BC_LEX_KEY_PRINT,
 464         BC_LEX_KEY_QUIT,
 465         BC_LEX_KEY_READ,
 466         BC_LEX_KEY_RETURN,
 467         BC_LEX_KEY_SCALE,
 468         BC_LEX_KEY_SQRT,
 469         BC_LEX_KEY_WHILE,
 470
 471 #if ENABLE_DC
 472         BC_LEX_EQ_NO_REG,
 473         BC_LEX_OP_MODEXP,
 474         BC_LEX_OP_DIVMOD,
 475
 476         BC_LEX_COLON,
 477         BC_LEX_ELSE,
 478         BC_LEX_EXECUTE,
 479         BC_LEX_PRINT_STACK,
 480         BC_LEX_CLEAR_STACK,
 481         BC_LEX_STACK_LEVEL,
 482         BC_LEX_DUPLICATE,
 483         BC_LEX_SWAP,
 484         BC_LEX_POP,
 485
 486         BC_LEX_ASCIIFY,
 487         BC_LEX_PRINT_STREAM,
 488
 489         BC_LEX_STORE_IBASE,
 490         BC_LEX_STORE_SCALE,
 491         BC_LEX_LOAD,
 492         BC_LEX_LOAD_POP,
 493         BC_LEX_STORE_PUSH,
 494         BC_LEX_STORE_OBASE,
 495         BC_LEX_PRINT_POP,
 496         BC_LEX_NQUIT,
 497         BC_LEX_SCALE_FACTOR,
 498 #endif
 499 } BcLexType;
 500 // must match order of BC_LEX_KEY_foo etc above
 501 #if ENABLE_BC
 502 struct BcLexKeyword {
 503         char name8[8];
 504 };
 505 #define BC_LEX_KW_ENTRY(a, b, c)            \
 506         { .name8 = a /*, .len = b, .posix = c*/ }
 507 static const struct BcLexKeyword bc_lex_kws[20] = {
 508         BC_LEX_KW_ENTRY("auto"    , 4, 1), // 0
 509         BC_LEX_KW_ENTRY("break"   , 5, 1), // 1
 510         BC_LEX_KW_ENTRY("continue", 8, 0), // 2 note: this one has no terminating NUL
 511         BC_LEX_KW_ENTRY("define"  , 6, 1), // 3
 512
 513         BC_LEX_KW_ENTRY("else"    , 4, 0), // 4
 514         BC_LEX_KW_ENTRY("for"     , 3, 1), // 5
 515         BC_LEX_KW_ENTRY("halt"    , 4, 0), // 6
 516         BC_LEX_KW_ENTRY("ibase"   , 5, 1), // 7
 517
 518         BC_LEX_KW_ENTRY("if"      , 2, 1), // 8
 519         BC_LEX_KW_ENTRY("last"    , 4, 0), // 9
 520         BC_LEX_KW_ENTRY("length"  , 6, 1), // 10
 521         BC_LEX_KW_ENTRY("limits"  , 6, 0), // 11
 522
 523         BC_LEX_KW_ENTRY("obase"   , 5, 1), // 12
 524         BC_LEX_KW_ENTRY("print"   , 5, 0), // 13
 525         BC_LEX_KW_ENTRY("quit"    , 4, 1), // 14
 526         BC_LEX_KW_ENTRY("read"    , 4, 0), // 15
 527
 528         BC_LEX_KW_ENTRY("return"  , 6, 1), // 16
 529         BC_LEX_KW_ENTRY("scale"   , 5, 1), // 17
 530         BC_LEX_KW_ENTRY("sqrt"    , 4, 1), // 18
 531         BC_LEX_KW_ENTRY("while"   , 5, 1), // 19
 532 };
 533 enum {
 534         POSIX_KWORD_MASK = 0
 535                 | (1 << 0)
 536                 | (1 << 1)
 537                 | (0 << 2)
 538                 | (1 << 3)
 539                 \
 540                 | (0 << 4)
 541                 | (1 << 5)
 542                 | (0 << 6)
 543                 | (1 << 7)
 544                 \
 545                 | (1 << 8)
 546                 | (0 << 9)
 547                 | (1 << 10)
 548                 | (0 << 11)
 549                 \
 550                 | (1 << 12)
 551                 | (0 << 13)
 552                 | (1 << 14)
 553                 | (0 << 15)
 554                 \
 555                 | (1 << 16)
 556                 | (1 << 17)
 557                 | (1 << 18)
 558                 | (1 << 19)
 559 };
 560 #endif
 561
 562 struct BcLex;
 563 typedef BcStatus (*BcLexNext)(struct BcLex *);
 564
 565 typedef struct BcLex {
 566
 567         const char *buf;
 568         size_t i;
 569         size_t line;
 570         size_t len;
 571         bool newline;
 572
 573         struct {
 574                 BcLexType t;
 575                 BcLexType last;
 576                 BcVec v;
 577         } t;
 578
 579         BcLexNext next;
 580
 581 } BcLex;
 582
 583 #define BC_PARSE_STREND ((char) UCHAR_MAX)
 584
 585 #define bc_parse_push(p, i) (bc_vec_pushByte(&(p)->func->code, (char) (i)))
 586 #define bc_parse_updateFunc(p, f) \
 587         ((p)->func = bc_vec_item(&G.prog.fns, ((p)->fidx = (f))))
 588
 589 #define BC_PARSE_REL (1 << 0)
 590 #define BC_PARSE_PRINT (1 << 1)
 591 #define BC_PARSE_NOCALL (1 << 2)
 592 #define BC_PARSE_NOREAD (1 << 3)
 593 #define BC_PARSE_ARRAY (1 << 4)
 594
 595 #define BC_PARSE_TOP_FLAG_PTR(parse) ((uint8_t *) bc_vec_top(&(parse)->flags))
 596 #define BC_PARSE_TOP_FLAG(parse) (*(BC_PARSE_TOP_FLAG_PTR(parse)))
 597
 598 #define BC_PARSE_FLAG_FUNC_INNER (1 << 0)
 599 #define BC_PARSE_FUNC_INNER(parse) \
 600         (BC_PARSE_TOP_FLAG(parse) & BC_PARSE_FLAG_FUNC_INNER)
 601
 602 #define BC_PARSE_FLAG_FUNC (1 << 1)
 603 #define BC_PARSE_FUNC(parse) (BC_PARSE_TOP_FLAG(parse) & BC_PARSE_FLAG_FUNC)
 604
 605 #define BC_PARSE_FLAG_BODY (1 << 2)
 606 #define BC_PARSE_BODY(parse) (BC_PARSE_TOP_FLAG(parse) & BC_PARSE_FLAG_BODY)
 607
 608 #define BC_PARSE_FLAG_LOOP (1 << 3)
 609 #define BC_PARSE_LOOP(parse) (BC_PARSE_TOP_FLAG(parse) & BC_PARSE_FLAG_LOOP)
 610
 611 #define BC_PARSE_FLAG_LOOP_INNER (1 << 4)
 612 #define BC_PARSE_LOOP_INNER(parse) \
 613         (BC_PARSE_TOP_FLAG(parse) & BC_PARSE_FLAG_LOOP_INNER)
 614
 615 #define BC_PARSE_FLAG_IF (1 << 5)
 616 #define BC_PARSE_IF(parse) (BC_PARSE_TOP_FLAG(parse) & BC_PARSE_FLAG_IF)
 617
 618 #define BC_PARSE_FLAG_ELSE (1 << 6)
 619 #define BC_PARSE_ELSE(parse) (BC_PARSE_TOP_FLAG(parse) & BC_PARSE_FLAG_ELSE)
 620
 621 #define BC_PARSE_FLAG_IF_END (1 << 7)
 622 #define BC_PARSE_IF_END(parse) (BC_PARSE_TOP_FLAG(parse) & BC_PARSE_FLAG_IF_END)
 623
 624 #define BC_PARSE_CAN_EXEC(parse)                                             \
 625         (!(BC_PARSE_TOP_FLAG(parse) &                                            \
 626            (BC_PARSE_FLAG_FUNC_INNER | BC_PARSE_FLAG_FUNC | BC_PARSE_FLAG_BODY | \
 627             BC_PARSE_FLAG_LOOP | BC_PARSE_FLAG_LOOP_INNER | BC_PARSE_FLAG_IF |   \
 628             BC_PARSE_FLAG_ELSE | BC_PARSE_FLAG_IF_END)))
 629
 630 typedef struct BcOp {
 631         char prec;
 632         bool left;
 633 } BcOp;
 634
 635 typedef struct BcParseNext {
 636         uint32_t len;
 637         BcLexType tokens[4];
 638 } BcParseNext;
 639
 640 #define BC_PARSE_NEXT_TOKENS(...) .tokens = { __VA_ARGS__ }
 641 #define BC_PARSE_NEXT(a, ...)                         \
 642         {                                                 \
 643                 .len = (a), BC_PARSE_NEXT_TOKENS(__VA_ARGS__) \
 644         }
 645
 646 struct BcParse;
 647
 648 struct BcProgram;
 649
 650 typedef BcStatus (*BcParseParse)(struct BcParse *);
 651
 652 typedef struct BcParse {
 653
 654         BcParseParse parse;
 655
 656         BcLex l;
 657
 658         BcVec flags;
 659
 660         BcVec exits;
 661         BcVec conds;
 662
 663         BcVec ops;
 664
 665         BcFunc *func;
 666         size_t fidx;
 667
 668         size_t nbraces;
 669         bool auto_part;
 670
 671 } BcParse;
 672
 673 #if ENABLE_BC
 674
 675 static BcStatus bc_lex_token(BcLex *l);
 676
 677 #define BC_PARSE_TOP_OP(p) (*((BcLexType *) bc_vec_top(&(p)->ops)))
 678 #define BC_PARSE_LEAF(p, rparen)                                \
 679         (((p) >= BC_INST_NUM && (p) <= BC_INST_SQRT) || (rparen) || \
 680          (p) == BC_INST_INC_POST || (p) == BC_INST_DEC_POST)
 681
 682 // We can calculate the conversion between tokens and exprs by subtracting the
 683 // position of the first operator in the lex enum and adding the position of the
 684 // first in the expr enum. Note: This only works for binary operators.
 685 #define BC_PARSE_TOKEN_INST(t) ((char) ((t) -BC_LEX_NEG + BC_INST_NEG))
 686
 687 static BcStatus bc_parse_expr(BcParse *p, uint8_t flags, BcParseNext next);
 688
 689 #endif // ENABLE_BC
 690
 691 #if ENABLE_DC
 692
 693 #define DC_PARSE_BUF_LEN ((int) (sizeof(uint32_t) * CHAR_BIT))
 694
 695 static BcStatus dc_lex_token(BcLex *l);
 696
 697 static BcStatus dc_parse_expr(BcParse *p, uint8_t flags);
 698
 699 #endif // ENABLE_DC
 700
 701 typedef struct BcProgram {
 702
 703         size_t len;
 704         size_t scale;
 705
 706         BcNum ib;
 707         size_t ib_t;
 708         BcNum ob;
 709         size_t ob_t;
 710
 711         BcNum hexb;
 712
 713 #if ENABLE_DC
 714         BcNum strmb;
 715 #endif
 716
 717         BcVec results;
 718         BcVec stack;
 719
 720         BcVec fns;
 721         BcVec fn_map;
 722
 723         BcVec vars;
 724         BcVec var_map;
 725
 726         BcVec arrs;
 727         BcVec arr_map;
 728
 729         BcVec strs;
 730         BcVec consts;
 731
 732         const char *file;
 733
 734         BcNum last;
 735         BcNum zero;
 736         BcNum one;
 737
 738         size_t nchars;
 739
 740 } BcProgram;
 741
 742 #define BC_PROG_STACK(s, n) ((s)->len >= ((size_t) n))
 743
 744 #define BC_PROG_MAIN (0)
 745 #define BC_PROG_READ (1)
 746
 747 #if ENABLE_DC
 748 #define BC_PROG_REQ_FUNCS (2)
 749 #endif
 750
 751 #define BC_PROG_STR(n) (!(n)->num && !(n)->cap)
 752 #define BC_PROG_NUM(r, n) \
 753         ((r)->t != BC_RESULT_ARRAY && (r)->t != BC_RESULT_STR && !BC_PROG_STR(n))
 754
 755 typedef unsigned long (*BcProgramBuiltIn)(BcNum *);
 756
 757 static void bc_program_addFunc(char *name, size_t *idx);
 758 static void bc_program_reset(void);
 759
 760 #define BC_FLAG_X (1 << 0)
 761 #define BC_FLAG_W (1 << 1)
 762 #define BC_FLAG_V (1 << 2)
 763 #define BC_FLAG_S (1 << 3)
 764 #define BC_FLAG_Q (1 << 4)
 765 #define BC_FLAG_L (1 << 5)
 766 #define BC_FLAG_I (1 << 6)
 767
 768 #define BC_MAX(a, b) ((a) > (b) ? (a) : (b))
 769 #define BC_MIN(a, b) ((a) < (b) ? (a) : (b))
 770
 771 #define BC_MAX_OBASE  ((unsigned) 999)
 772 #define BC_MAX_DIM    ((unsigned) INT_MAX)
 773 #define BC_MAX_SCALE  ((unsigned) UINT_MAX)
 774 #define BC_MAX_STRING ((unsigned) UINT_MAX - 1)
 775 #define BC_MAX_NAME   BC_MAX_STRING
 776 #define BC_MAX_NUM    BC_MAX_STRING
 777 #define BC_MAX_EXP    ((unsigned long) LONG_MAX)
 778 #define BC_MAX_VARS   ((unsigned long) SIZE_MAX - 1)
 779
 780 struct globals {
 781         smallint ttyin;
 782         smallint eof;
 783         char sbgn;
 784         char send;
 785
 786         BcParse prs;
 787         BcProgram prog;
 788
 789         // For error messages. Can be set to current parsed line,
 790         // or [TODO] to current executing line (can be before last parsed one)
 791         unsigned err_line;
 792
 793         BcVec files;
 794
 795         char *env_args;
 796 } FIX_ALIASING;
 797 #define G (*ptr_to_globals)
 798 #define INIT_G() do { \
 799         SET_PTR_TO_GLOBALS(xzalloc(sizeof(G))); \
 800 } while (0)
 801 #define G_posix (ENABLE_BC && (option_mask32 & BC_FLAG_S))
 802 #define G_warn  (ENABLE_BC && (option_mask32 & BC_FLAG_W))
 803 #define G_exreg (ENABLE_DC && (option_mask32 & BC_FLAG_X))
 804 #define G_interrupt (ENABLE_FEATURE_BC_SIGNALS ? bb_got_signal : 0)
 805
 806
 807 #define IS_BC (ENABLE_BC && (!ENABLE_DC || applet_name[0] == 'b'))
 808
 809 static void bc_vm_info(void);
 810
 811 #if ENABLE_BC
 812
 813 // This is an array that corresponds to token types. An entry is
 814 // true if the token is valid in an expression, false otherwise.
 815 static const bool bc_parse_exprs[] = {
 816         false, false, true, true, true, true, true, true, true, true, true, true,
 817         true, true, true, true, true, true, true, true, true, true, true, true,
 818         true, true, true, false, false, true, true, false, false, false, false,
 819         false, false, false, true, true, false, false, false, false, false, false,
 820         false, true, false, true, true, true, true, false, false, true, false, true,
 821         true, false,
 822 };
 823
 824 // This is an array of data for operators that correspond to token types.
 825 static const BcOp bc_parse_ops[] = {
 826         { 0, false }, { 0, false },
 827         { 1, false },
 828         { 2, false },
 829         { 3, true }, { 3, true }, { 3, true },
 830         { 4, true }, { 4, true },
 831         { 6, true }, { 6, true }, { 6, true }, { 6, true }, { 6, true }, { 6, true },
 832         { 1, false },
 833         { 7, true }, { 7, true },
 834         { 5, false }, { 5, false }, { 5, false }, { 5, false }, { 5, false },
 835         { 5, false }, { 5, false },
 836 };
 837
 838 // These identify what tokens can come after expressions in certain cases.
 839 static const BcParseNext bc_parse_next_expr =
 840         BC_PARSE_NEXT(4, BC_LEX_NLINE, BC_LEX_SCOLON, BC_LEX_RBRACE, BC_LEX_EOF);
 841 static const BcParseNext bc_parse_next_param =
 842         BC_PARSE_NEXT(2, BC_LEX_RPAREN, BC_LEX_COMMA);
 843 static const BcParseNext bc_parse_next_print =
 844         BC_PARSE_NEXT(4, BC_LEX_COMMA, BC_LEX_NLINE, BC_LEX_SCOLON, BC_LEX_EOF);
 845 static const BcParseNext bc_parse_next_rel = BC_PARSE_NEXT(1, BC_LEX_RPAREN);
 846 static const BcParseNext bc_parse_next_elem = BC_PARSE_NEXT(1, BC_LEX_RBRACKET);
 847 static const BcParseNext bc_parse_next_for = BC_PARSE_NEXT(1, BC_LEX_SCOLON);
 848 static const BcParseNext bc_parse_next_read =
 849         BC_PARSE_NEXT(2, BC_LEX_NLINE, BC_LEX_EOF);
 850 #endif // ENABLE_BC
 851
 852 #if ENABLE_DC
 853 static const BcLexType dc_lex_regs[] = {
 854         BC_LEX_OP_REL_EQ, BC_LEX_OP_REL_LE, BC_LEX_OP_REL_GE, BC_LEX_OP_REL_NE,
 855         BC_LEX_OP_REL_LT, BC_LEX_OP_REL_GT, BC_LEX_SCOLON, BC_LEX_COLON,
 856         BC_LEX_ELSE, BC_LEX_LOAD, BC_LEX_LOAD_POP, BC_LEX_OP_ASSIGN,
 857         BC_LEX_STORE_PUSH,
 858 };
 859
 860 static const BcLexType dc_lex_tokens[] = {
 861         BC_LEX_OP_MODULUS, BC_LEX_INVALID, BC_LEX_INVALID, BC_LEX_LPAREN,
 862         BC_LEX_INVALID, BC_LEX_OP_MULTIPLY, BC_LEX_OP_PLUS, BC_LEX_INVALID,
 863         BC_LEX_OP_MINUS, BC_LEX_INVALID, BC_LEX_OP_DIVIDE,
 864         BC_LEX_INVALID, BC_LEX_INVALID, BC_LEX_INVALID, BC_LEX_INVALID,
 865         BC_LEX_INVALID, BC_LEX_INVALID, BC_LEX_INVALID, BC_LEX_INVALID,
 866         BC_LEX_INVALID, BC_LEX_INVALID,
 867         BC_LEX_COLON, BC_LEX_SCOLON, BC_LEX_OP_REL_GT, BC_LEX_OP_REL_EQ,
 868         BC_LEX_OP_REL_LT, BC_LEX_KEY_READ, BC_LEX_INVALID,
 869         BC_LEX_INVALID, BC_LEX_INVALID, BC_LEX_INVALID, BC_LEX_INVALID,
 870         BC_LEX_INVALID, BC_LEX_INVALID, BC_LEX_EQ_NO_REG, BC_LEX_INVALID,
 871         BC_LEX_KEY_IBASE, BC_LEX_INVALID, BC_LEX_KEY_SCALE, BC_LEX_LOAD_POP,
 872         BC_LEX_INVALID, BC_LEX_OP_BOOL_NOT, BC_LEX_KEY_OBASE, BC_LEX_PRINT_STREAM,
 873         BC_LEX_NQUIT, BC_LEX_POP, BC_LEX_STORE_PUSH, BC_LEX_INVALID, BC_LEX_INVALID,
 874         BC_LEX_INVALID, BC_LEX_INVALID, BC_LEX_SCALE_FACTOR, BC_LEX_INVALID,
 875         BC_LEX_KEY_LENGTH, BC_LEX_INVALID, BC_LEX_INVALID, BC_LEX_INVALID,
 876         BC_LEX_OP_POWER, BC_LEX_NEG, BC_LEX_INVALID,
 877         BC_LEX_ASCIIFY, BC_LEX_INVALID, BC_LEX_CLEAR_STACK, BC_LEX_DUPLICATE,
 878         BC_LEX_ELSE, BC_LEX_PRINT_STACK, BC_LEX_INVALID, BC_LEX_INVALID,
 879         BC_LEX_STORE_IBASE, BC_LEX_INVALID, BC_LEX_STORE_SCALE, BC_LEX_LOAD,
 880         BC_LEX_INVALID, BC_LEX_PRINT_POP, BC_LEX_STORE_OBASE, BC_LEX_KEY_PRINT,
 881         BC_LEX_KEY_QUIT, BC_LEX_SWAP, BC_LEX_OP_ASSIGN, BC_LEX_INVALID,
 882         BC_LEX_INVALID, BC_LEX_KEY_SQRT, BC_LEX_INVALID, BC_LEX_EXECUTE,
 883         BC_LEX_INVALID, BC_LEX_STACK_LEVEL,
 884         BC_LEX_LBRACE, BC_LEX_OP_MODEXP, BC_LEX_INVALID, BC_LEX_OP_DIVMOD,
 885         BC_LEX_INVALID
 886 };
 887
 888 static const BcInst dc_parse_insts[] = {
 889         BC_INST_INVALID, BC_INST_INVALID, BC_INST_INVALID, BC_INST_REL_GE,
 890         BC_INST_INVALID, BC_INST_POWER, BC_INST_MULTIPLY, BC_INST_DIVIDE,
 891         BC_INST_MODULUS, BC_INST_PLUS, BC_INST_MINUS,
 892         BC_INST_INVALID, BC_INST_INVALID, BC_INST_INVALID, BC_INST_INVALID,
 893         BC_INST_INVALID, BC_INST_INVALID,
 894         BC_INST_BOOL_NOT, BC_INST_INVALID, BC_INST_INVALID,
 895         BC_INST_INVALID, BC_INST_INVALID, BC_INST_INVALID, BC_INST_INVALID,
 896         BC_INST_INVALID, BC_INST_INVALID, BC_INST_INVALID,
 897         BC_INST_INVALID, BC_INST_INVALID, BC_INST_REL_GT, BC_INST_INVALID,
 898         BC_INST_INVALID, BC_INST_INVALID, BC_INST_INVALID, BC_INST_REL_GE,
 899         BC_INST_INVALID, BC_INST_INVALID,
 900         BC_INST_INVALID, BC_INST_INVALID, BC_INST_INVALID,
 901         BC_INST_INVALID, BC_INST_INVALID, BC_INST_INVALID, BC_INST_INVALID,
 902         BC_INST_INVALID, BC_INST_INVALID, BC_INST_INVALID, BC_INST_IBASE,
 903         BC_INST_INVALID, BC_INST_INVALID, BC_INST_LENGTH, BC_INST_INVALID,
 904         BC_INST_OBASE, BC_INST_PRINT, BC_INST_QUIT, BC_INST_INVALID,
 905         BC_INST_INVALID, BC_INST_SCALE, BC_INST_SQRT, BC_INST_INVALID,
 906         BC_INST_REL_EQ, BC_INST_MODEXP, BC_INST_DIVMOD, BC_INST_INVALID,
 907         BC_INST_INVALID, BC_INST_EXECUTE, BC_INST_PRINT_STACK, BC_INST_CLEAR_STACK,
 908         BC_INST_STACK_LEN, BC_INST_DUPLICATE, BC_INST_SWAP, BC_INST_POP,
 909         BC_INST_ASCIIFY, BC_INST_PRINT_STREAM, BC_INST_INVALID, BC_INST_INVALID,
 910         BC_INST_INVALID, BC_INST_INVALID, BC_INST_INVALID, BC_INST_INVALID,
 911         BC_INST_PRINT, BC_INST_NQUIT, BC_INST_SCALE_FUNC,
 912 };
 913 #endif // ENABLE_DC
 914
 915 static const BcNumBinaryOp bc_program_ops[] = {
 916         bc_num_pow, bc_num_mul, bc_num_div, bc_num_mod, bc_num_add, bc_num_sub,
 917 };
 918
 919 static void fflush_and_check(void)
 920 {
 921         fflush_all();
 922         if (ferror(stdout) || ferror(stderr))
 923                 bb_perror_msg_and_die("output error");
 924 }
 925
 926 static void quit(void) NORETURN;
 927 static void quit(void)
 928 {
 929         if (ferror(stdin))
 930                 bb_perror_msg_and_die("input error");
 931         fflush_and_check();
 932         exit(0);
 933 }
 934
 935 static void bc_verror_msg(const char *fmt, va_list p)
 936 {
 937         const char *sv = sv; /* for compiler */
 938         if (G.prog.file) {
 939                 sv = applet_name;
 940                 applet_name = xasprintf("%s: %s:%u", applet_name, G.prog.file, G.err_line);
 941         }
 942         bb_verror_msg(fmt, p, NULL);
 943         if (G.prog.file) {
 944                 free((char*)applet_name);
 945                 applet_name = sv;
 946         }
 947 }
 948
 949 static NOINLINE int bc_error_fmt(const char *fmt, ...)
 950 {
 951         va_list p;
 952
 953         va_start(p, fmt);
 954         bc_verror_msg(fmt, p);
 955         va_end(p);
 956
 957         if (!G.ttyin)
 958                 exit(1);
 959         return BC_STATUS_FAILURE;
 960 }
 961
 962 static NOINLINE int bc_posix_error_fmt(const char *fmt, ...)
 963 {
 964         va_list p;
 965
 966         // Are non-POSIX constructs totally ok?
 967         if (!(option_mask32 & (BC_FLAG_S|BC_FLAG_W)))
 968                 return BC_STATUS_SUCCESS; // yes
 969
 970         va_start(p, fmt);
 971         bc_verror_msg(fmt, p);
 972         va_end(p);
 973
 974         // Do we treat non-POSIX constructs as errors?
 975         if (!(option_mask32 & BC_FLAG_S))
 976                 return BC_STATUS_SUCCESS; // no, it's a warning
 977         if (!G.ttyin)
 978                 exit(1);
 979         return BC_STATUS_FAILURE;
 980 }
 981
 982 // We use error functions with "return bc_error(FMT[, PARAMS])" idiom.
 983 // This idiom begs for tail-call optimization, but for it to work,
 984 // function must not have calller-cleaned parameters on stack.
 985 // Unfortunately, vararg functions do exactly that on most arches.
 986 // Thus, these shims for the cases when we have no PARAMS:
 987 static int bc_error(const char *msg)
 988 {
 989         return bc_error_fmt("%s", msg);
 990 }
 991 static int bc_posix_error(const char *msg)
 992 {
 993         return bc_posix_error_fmt("%s", msg);
 994 }
 995 static int bc_POSIX_does_not_allow(const char *msg)
 996 {
 997         return bc_posix_error_fmt("%s%s", "POSIX does not allow ", msg);
 998 }
 999 static int bc_POSIX_does_not_allow_bool_ops_this_is_bad(const char *msg)
1000 {
1001         return bc_posix_error_fmt("%s%s %s", "POSIX does not allow ", "boolean operators; the following is bad:", msg);
1002 }
1003 static int bc_POSIX_does_not_allow_empty_X_expression_in_for(const char *msg)
1004 {
1005         return bc_posix_error_fmt("%san empty %s expression in a for loop", "POSIX does not allow ", msg);
1006 }
1007 static int bc_error_bad_character(char c)
1008 {
1009         return bc_error_fmt("bad character '%c'", c);
1010 }
1011 static int bc_error_bad_expression(void)
1012 {
1013         return bc_error("bad expression");
1014 }
1015 static int bc_error_bad_token(void)
1016 {
1017         return bc_error("bad token");
1018 }
1019 static int bc_error_stack_has_too_few_elements(void)
1020 {
1021         return bc_error("stack has too few elements");
1022 }
1023 static int bc_error_variable_is_wrong_type(void)
1024 {
1025         return bc_error("variable is wrong type");
1026 }
1027 static int bc_error_nested_read_call(void)
1028 {
1029         return bc_error("read() call inside of a read() call");
1030 }
1031
1032 static void bc_vec_grow(BcVec *v, size_t n)
1033 {
1034         size_t cap = v->cap * 2;
1035         while (cap < v->len + n) cap *= 2;
1036         v->v = xrealloc(v->v, v->size * cap);
1037         v->cap = cap;
1038 }
1039
1040 static void bc_vec_init(BcVec *v, size_t esize, BcVecFree dtor)
1041 {
1042         v->size = esize;
1043         v->cap = BC_VEC_START_CAP;
1044         v->len = 0;
1045         v->dtor = dtor;
1046         v->v = xmalloc(esize * BC_VEC_START_CAP);
1047 }
1048
1049 static void bc_char_vec_init(BcVec *v)
1050 {
1051         bc_vec_init(v, sizeof(char), NULL);
1052 }
1053
1054 static void bc_vec_expand(BcVec *v, size_t req)
1055 {
1056         if (v->cap < req) {
1057                 v->v = xrealloc(v->v, v->size * req);
1058                 v->cap = req;
1059         }
1060 }
1061
1062 static void bc_vec_npop(BcVec *v, size_t n)
1063 {
1064         if (!v->dtor)
1065                 v->len -= n;
1066         else {
1067                 size_t len = v->len - n;
1068                 while (v->len > len) v->dtor(v->v + (v->size * --v->len));
1069         }
1070 }
1071
1072 static void bc_vec_pop_all(BcVec *v)
1073 {
1074         bc_vec_npop(v, v->len);
1075 }
1076
1077 static void bc_vec_push(BcVec *v, const void *data)
1078 {
1079         if (v->len + 1 > v->cap) bc_vec_grow(v, 1);
1080         memmove(v->v + (v->size * v->len), data, v->size);
1081         v->len += 1;
1082 }
1083
1084 static void bc_vec_pushByte(BcVec *v, char data)
1085 {
1086         bc_vec_push(v, &data);
1087 }
1088
1089 static void bc_vec_pushZeroByte(BcVec *v)
1090 {
1091         //bc_vec_pushByte(v, '\0');
1092         // better:
1093         bc_vec_push(v, &const_int_0);
1094 }
1095
1096 static void bc_vec_pushAt(BcVec *v, const void *data, size_t idx)
1097 {
1098         if (idx == v->len)
1099                 bc_vec_push(v, data);
1100         else {
1101
1102                 char *ptr;
1103
1104                 if (v->len == v->cap) bc_vec_grow(v, 1);
1105
1106                 ptr = v->v + v->size * idx;
1107
1108                 memmove(ptr + v->size, ptr, v->size * (v->len++ - idx));
1109                 memmove(ptr, data, v->size);
1110         }
1111 }
1112
1113 static void bc_vec_string(BcVec *v, size_t len, const char *str)
1114 {
1115         bc_vec_pop_all(v);
1116         bc_vec_expand(v, len + 1);
1117         memcpy(v->v, str, len);
1118         v->len = len;
1119
1120         bc_vec_pushZeroByte(v);
1121 }
1122
1123 static void bc_vec_concat(BcVec *v, const char *str)
1124 {
1125         size_t len;
1126
1127         if (v->len == 0) bc_vec_pushZeroByte(v);
1128
1129         len = v->len + strlen(str);
1130
1131         if (v->cap < len) bc_vec_grow(v, len - v->len);
1132         strcat(v->v, str);
1133
1134         v->len = len;
1135 }
1136
1137 static void *bc_vec_item(const BcVec *v, size_t idx)
1138 {
1139         return v->v + v->size * idx;
1140 }
1141
1142 static void *bc_vec_item_rev(const BcVec *v, size_t idx)
1143 {
1144         return v->v + v->size * (v->len - idx - 1);
1145 }
1146
1147 static void bc_vec_free(void *vec)
1148 {
1149         BcVec *v = (BcVec *) vec;
1150         bc_vec_pop_all(v);
1151         free(v->v);
1152 }
1153
1154 static size_t bc_map_find(const BcVec *v, const void *ptr)
1155 {
1156         size_t low = 0, high = v->len;
1157
1158         while (low < high) {
1159
1160                 size_t mid = (low + high) / 2;
1161                 BcId *id = bc_vec_item(v, mid);
1162                 int result = bc_id_cmp(ptr, id);
1163
1164                 if (result == 0)
1165                         return mid;
1166                 else if (result < 0)
1167                         high = mid;
1168                 else
1169                         low = mid + 1;
1170         }
1171
1172         return low;
1173 }
1174
1175 static int bc_map_insert(BcVec *v, const void *ptr, size_t *i)
1176 {
1177         size_t n = *i = bc_map_find(v, ptr);
1178
1179         if (n == v->len)
1180                 bc_vec_push(v, ptr);
1181         else if (!bc_id_cmp(ptr, bc_vec_item(v, n)))
1182                 return 0; // "was not inserted"
1183         else
1184                 bc_vec_pushAt(v, ptr, n);
1185         return 1; // "was inserted"
1186 }
1187
1188 static size_t bc_map_index(const BcVec *v, const void *ptr)
1189 {
1190         size_t i = bc_map_find(v, ptr);
1191         if (i >= v->len) return BC_VEC_INVALID_IDX;
1192         return bc_id_cmp(ptr, bc_vec_item(v, i)) ? BC_VEC_INVALID_IDX : i;
1193 }
1194
1195 static BcStatus bc_read_line(BcVec *vec, const char *prompt)
1196 {
1197         bool bad_chars;
1198
1199         do {
1200                 int i;
1201
1202                 bad_chars = 0;
1203                 bc_vec_pop_all(vec);
1204
1205                 fflush_and_check();
1206 #if ENABLE_FEATURE_BC_SIGNALS
1207                 if (bb_got_signal) { // ^C was pressed
1208  intr:
1209                         bb_got_signal = 0; // resets G_interrupt to zero
1210                         fputs(IS_BC
1211                                 ? "\ninterrupt (type \"quit\" to exit)\n"
1212                                 : "\ninterrupt (type \"q\" to exit)\n"
1213                                 , stderr);
1214                 }
1215 #endif
1216                 if (G.ttyin && !G_posix)
1217                         fputs(prompt, stderr);
1218
1219 #if ENABLE_FEATURE_BC_SIGNALS
1220                 errno = 0;
1221 #endif
1222                 do {
1223                         i = fgetc(stdin);
1224                         if (i == EOF) {
1225 #if ENABLE_FEATURE_BC_SIGNALS
1226                                 // Both conditions appear simultaneously, check both just in case
1227                                 if (errno == EINTR || bb_got_signal) {
1228                                         // ^C was pressed
1229                                         clearerr(stdin);
1230                                         goto intr;
1231                                 }
1232 #endif
1233                                 if (ferror(stdin))
1234                                         quit(); // this emits error message
1235                                 G.eof = 1;
1236                                 // Note: EOF does not append '\n', therefore:
1237                                 // printf 'print 123\n' | bc - works
1238                                 // printf 'print 123' | bc   - fails (syntax error)
1239                                 break;
1240                         }
1241
1242                         if ((i < ' ' && i != '\t' && i != '\r' && i != '\n') // also allow '\v' '\f'?
1243                          || i > 0x7e
1244                         ) {
1245                                 // Bad chars on this line, ignore entire line
1246                                 bc_error_fmt("illegal character 0x%02x", i);
1247                                 bad_chars = 1;
1248                         }
1249                         bc_vec_pushByte(vec, (char)i);
1250                 } while (i != '\n');
1251         } while (bad_chars);
1252
1253         bc_vec_pushZeroByte(vec);
1254
1255         return BC_STATUS_SUCCESS;
1256 }
1257
1258 static char* bc_read_file(const char *path)
1259 {
1260         char *buf;
1261         size_t size = ((size_t) -1);
1262         size_t i;
1263
1264         buf = xmalloc_open_read_close(path, &size);
1265
1266         for (i = 0; i < size; ++i) {
1267                 char c = buf[i];
1268                 if ((c < ' ' && c != '\t' && c != '\r' && c != '\n') // also allow '\v' '\f'?
1269                  || c > 0x7e
1270                 ) {
1271                         free(buf);
1272                         buf = NULL;
1273                         break;
1274                 }
1275         }
1276
1277         return buf;
1278 }
1279
1280 static void bc_args(int argc, char **argv)
1281 {
1282         unsigned opts;
1283         int i;
1284
1285         GETOPT_RESET();
1286 #if ENABLE_FEATURE_BC_LONG_OPTIONS
1287         opts = getopt32long(argv, "xwvsqli",
1288                 "extended-register\0" No_argument "x"
1289                 "warn\0"              No_argument "w"
1290                 "version\0"           No_argument "v"
1291                 "standard\0"          No_argument "s"
1292                 "quiet\0"             No_argument "q"
1293                 "mathlib\0"           No_argument "l"
1294                 "interactive\0"       No_argument "i"
1295         );
1296 #else
1297         opts = getopt32(argv, "xwvsqli");
1298 #endif
1299         if (getenv("POSIXLY_CORRECT"))
1300                 option_mask32 |= BC_FLAG_S;
1301
1302         if (opts & BC_FLAG_V) bc_vm_info();
1303         // should not be necessary, getopt32() handles this??
1304         //if (argv[optind] && !strcmp(argv[optind], "--")) ++optind;
1305
1306         for (i = optind; i < argc; ++i)
1307                 bc_vec_push(&G.files, argv + i);
1308 }
1309
1310 static void bc_num_setToZero(BcNum *n, size_t scale)
1311 {
1312         n->len = 0;
1313         n->neg = false;
1314         n->rdx = scale;
1315 }
1316
1317 static void bc_num_zero(BcNum *n)
1318 {
1319         bc_num_setToZero(n, 0);
1320 }
1321
1322 static void bc_num_one(BcNum *n)
1323 {
1324         bc_num_setToZero(n, 0);
1325         n->len = 1;
1326         n->num[0] = 1;
1327 }
1328
1329 static void bc_num_ten(BcNum *n)
1330 {
1331         bc_num_setToZero(n, 0);
1332         n->len = 2;
1333         n->num[0] = 0;
1334         n->num[1] = 1;
1335 }
1336
1337 static void bc_num_subArrays(BcDig *restrict a, BcDig *restrict b,
1338                                  size_t len)
1339 {
1340         size_t i, j;
1341         for (i = 0; i < len; ++i) {
1342                 for (a[i] -= b[i], j = 0; a[i + j] < 0;) {
1343                         a[i + j++] += 10;
1344                         a[i + j] -= 1;
1345                 }
1346         }
1347 }
1348
1349 static ssize_t bc_num_compare(BcDig *restrict a, BcDig *restrict b, size_t len)
1350 {
1351         size_t i;
1352         int c = 0;
1353         for (i = len - 1; i < len && !(c = a[i] - b[i]); --i);
1354         return BC_NUM_NEG(i + 1, c < 0);
1355 }
1356
1357 static ssize_t bc_num_cmp(BcNum *a, BcNum *b)
1358 {
1359         size_t i, min, a_int, b_int, diff;
1360         BcDig *max_num, *min_num;
1361         bool a_max, neg = false;
1362         ssize_t cmp;
1363
1364         if (a == b) return 0;
1365         if (a->len == 0) return BC_NUM_NEG(!!b->len, !b->neg);
1366         if (b->len == 0) return BC_NUM_NEG(1, a->neg);
1367         if (a->neg) {
1368                 if (b->neg)
1369                         neg = true;
1370                 else
1371                         return -1;
1372         }
1373         else if (b->neg)
1374                 return 1;
1375
1376         a_int = BC_NUM_INT(a);
1377         b_int = BC_NUM_INT(b);
1378         a_int -= b_int;
1379         a_max = (a->rdx > b->rdx);
1380
1381         if (a_int != 0) return (ssize_t) a_int;
1382
1383         if (a_max) {
1384                 min = b->rdx;
1385                 diff = a->rdx - b->rdx;
1386                 max_num = a->num + diff;
1387                 min_num = b->num;
1388         }
1389         else {
1390                 min = a->rdx;
1391                 diff = b->rdx - a->rdx;
1392                 max_num = b->num + diff;
1393                 min_num = a->num;
1394         }
1395
1396         cmp = bc_num_compare(max_num, min_num, b_int + min);
1397         if (cmp != 0) return BC_NUM_NEG(cmp, (!a_max) != neg);
1398
1399         for (max_num -= diff, i = diff - 1; i < diff; --i) {
1400                 if (max_num[i]) return BC_NUM_NEG(1, (!a_max) != neg);
1401         }
1402
1403         return 0;
1404 }
1405
1406 static void bc_num_truncate(BcNum *n, size_t places)
1407 {
1408         if (places == 0) return;
1409
1410         n->rdx -= places;
1411
1412         if (n->len != 0) {
1413                 n->len -= places;
1414                 memmove(n->num, n->num + places, n->len * sizeof(BcDig));
1415         }
1416 }
1417
1418 static void bc_num_extend(BcNum *n, size_t places)
1419 {
1420         size_t len = n->len + places;
1421
1422         if (places != 0) {
1423
1424                 if (n->cap < len) bc_num_expand(n, len);
1425
1426                 memmove(n->num + places, n->num, sizeof(BcDig) * n->len);
1427                 memset(n->num, 0, sizeof(BcDig) * places);
1428
1429                 n->len += places;
1430                 n->rdx += places;
1431         }
1432 }
1433
1434 static void bc_num_clean(BcNum *n)
1435 {
1436         while (n->len > 0 && n->num[n->len - 1] == 0) --n->len;
1437         if (n->len == 0)
1438                 n->neg = false;
1439         else if (n->len < n->rdx)
1440                 n->len = n->rdx;
1441 }
1442
1443 static void bc_num_retireMul(BcNum *n, size_t scale, bool neg1, bool neg2)
1444 {
1445         if (n->rdx < scale)
1446                 bc_num_extend(n, scale - n->rdx);
1447         else
1448                 bc_num_truncate(n, n->rdx - scale);
1449
1450         bc_num_clean(n);
1451         if (n->len != 0) n->neg = !neg1 != !neg2;
1452 }
1453
1454 static void bc_num_split(BcNum *restrict n, size_t idx, BcNum *restrict a,
1455                          BcNum *restrict b)
1456 {
1457         if (idx < n->len) {
1458
1459                 b->len = n->len - idx;
1460                 a->len = idx;
1461                 a->rdx = b->rdx = 0;
1462
1463                 memcpy(b->num, n->num + idx, b->len * sizeof(BcDig));
1464                 memcpy(a->num, n->num, idx * sizeof(BcDig));
1465         }
1466         else {
1467                 bc_num_zero(b);
1468                 bc_num_copy(a, n);
1469         }
1470
1471         bc_num_clean(a);
1472         bc_num_clean(b);
1473 }
1474
1475 static BcStatus bc_num_shift(BcNum *n, size_t places)
1476 {
1477         if (places == 0 || n->len == 0) return BC_STATUS_SUCCESS;
1478         if (places + n->len > BC_MAX_NUM)
1479                 return bc_error("number too long: must be [1, BC_NUM_MAX]");
1480
1481         if (n->rdx >= places)
1482                 n->rdx -= places;
1483         else {
1484                 bc_num_extend(n, places - n->rdx);
1485                 n->rdx = 0;
1486         }
1487
1488         bc_num_clean(n);
1489
1490         return BC_STATUS_SUCCESS;
1491 }
1492
1493 static BcStatus bc_num_inv(BcNum *a, BcNum *b, size_t scale)
1494 {
1495         BcNum one;
1496         BcDig num[2];
1497
1498         one.cap = 2;
1499         one.num = num;
1500         bc_num_one(&one);
1501
1502         return bc_num_div(&one, a, b, scale);
1503 }
1504
1505 static BcStatus bc_num_a(BcNum *a, BcNum *b, BcNum *restrict c, size_t sub)
1506 {
1507         BcDig *ptr, *ptr_a, *ptr_b, *ptr_c;
1508         size_t i, max, min_rdx, min_int, diff, a_int, b_int;
1509         int carry, in;
1510
1511         // Because this function doesn't need to use scale (per the bc spec),
1512         // I am hijacking it to say whether it's doing an add or a subtract.
1513
1514         if (a->len == 0) {
1515                 bc_num_copy(c, b);
1516                 if (sub && c->len) c->neg = !c->neg;
1517                 return BC_STATUS_SUCCESS;
1518         }
1519         else if (b->len == 0) {
1520                 bc_num_copy(c, a);
1521                 return BC_STATUS_SUCCESS;
1522         }
1523
1524         c->neg = a->neg;
1525         c->rdx = BC_MAX(a->rdx, b->rdx);
1526         min_rdx = BC_MIN(a->rdx, b->rdx);
1527         c->len = 0;
1528
1529         if (a->rdx > b->rdx) {
1530                 diff = a->rdx - b->rdx;
1531                 ptr = a->num;
1532                 ptr_a = a->num + diff;
1533                 ptr_b = b->num;
1534         }
1535         else {
1536                 diff = b->rdx - a->rdx;
1537                 ptr = b->num;
1538                 ptr_a = a->num;
1539                 ptr_b = b->num + diff;
1540         }
1541
1542         for (ptr_c = c->num, i = 0; i < diff; ++i, ++c->len) ptr_c[i] = ptr[i];
1543
1544         ptr_c += diff;
1545         a_int = BC_NUM_INT(a);
1546         b_int = BC_NUM_INT(b);
1547
1548         if (a_int > b_int) {
1549                 min_int = b_int;
1550                 max = a_int;
1551                 ptr = ptr_a;
1552         }
1553         else {
1554                 min_int = a_int;
1555                 max = b_int;
1556                 ptr = ptr_b;
1557         }
1558
1559         for (carry = 0, i = 0; i < min_rdx + min_int; ++i, ++c->len) {
1560                 in = ((int) ptr_a[i]) + ((int) ptr_b[i]) + carry;
1561                 carry = in / 10;
1562                 ptr_c[i] = (BcDig)(in % 10);
1563         }
1564
1565         for (; i < max + min_rdx; ++i, ++c->len) {
1566                 in = ((int) ptr[i]) + carry;
1567                 carry = in / 10;
1568                 ptr_c[i] = (BcDig)(in % 10);
1569         }
1570
1571         if (carry != 0) c->num[c->len++] = (BcDig) carry;
1572
1573         return BC_STATUS_SUCCESS; // can't make void, see bc_num_binary()
1574 }
1575
1576 static BcStatus bc_num_s(BcNum *a, BcNum *b, BcNum *restrict c, size_t sub)
1577 {
1578         ssize_t cmp;
1579         BcNum *minuend, *subtrahend;
1580         size_t start;
1581         bool aneg, bneg, neg;
1582
1583         // Because this function doesn't need to use scale (per the bc spec),
1584         // I am hijacking it to say whether it's doing an add or a subtract.
1585
1586         if (a->len == 0) {
1587                 bc_num_copy(c, b);
1588                 if (sub && c->len) c->neg = !c->neg;
1589                 return BC_STATUS_SUCCESS;
1590         }
1591         else if (b->len == 0) {
1592                 bc_num_copy(c, a);
1593                 return BC_STATUS_SUCCESS;
1594         }
1595
1596         aneg = a->neg;
1597         bneg = b->neg;
1598         a->neg = b->neg = false;
1599
1600         cmp = bc_num_cmp(a, b);
1601
1602         a->neg = aneg;
1603         b->neg = bneg;
1604
1605         if (cmp == 0) {
1606                 bc_num_setToZero(c, BC_MAX(a->rdx, b->rdx));
1607                 return BC_STATUS_SUCCESS;
1608         }
1609         else if (cmp > 0) {
1610                 neg = a->neg;
1611                 minuend = a;
1612                 subtrahend = b;
1613         }
1614         else {
1615                 neg = b->neg;
1616                 if (sub) neg = !neg;
1617                 minuend = b;
1618                 subtrahend = a;
1619         }
1620
1621         bc_num_copy(c, minuend);
1622         c->neg = neg;
1623
1624         if (c->rdx < subtrahend->rdx) {
1625                 bc_num_extend(c, subtrahend->rdx - c->rdx);
1626                 start = 0;
1627         }
1628         else
1629                 start = c->rdx - subtrahend->rdx;
1630
1631         bc_num_subArrays(c->num + start, subtrahend->num, subtrahend->len);
1632
1633         bc_num_clean(c);
1634
1635         return BC_STATUS_SUCCESS; // can't make void, see bc_num_binary()
1636 }
1637
1638 static BcStatus bc_num_k(BcNum *restrict a, BcNum *restrict b,
1639                          BcNum *restrict c)
1640 {
1641         BcStatus s;
1642         int carry;
1643         size_t i, j, len, max = BC_MAX(a->len, b->len), max2 = (max + 1) / 2;
1644         BcNum l1, h1, l2, h2, m2, m1, z0, z1, z2, temp;
1645         bool aone = BC_NUM_ONE(a);
1646
1647         if (a->len == 0 || b->len == 0) {
1648                 bc_num_zero(c);
1649                 return BC_STATUS_SUCCESS;
1650         }
1651         else if (aone || BC_NUM_ONE(b)) {
1652                 bc_num_copy(c, aone ? b : a);
1653                 return BC_STATUS_SUCCESS;
1654         }
1655
1656         if (a->len + b->len < BC_NUM_KARATSUBA_LEN ||
1657             a->len < BC_NUM_KARATSUBA_LEN || b->len < BC_NUM_KARATSUBA_LEN)
1658         {
1659                 bc_num_expand(c, a->len + b->len + 1);
1660
1661                 memset(c->num, 0, sizeof(BcDig) * c->cap);
1662                 c->len = carry = len = 0;
1663
1664                 for (i = 0; i < b->len; ++i) {
1665
1666                         for (j = 0; j < a->len; ++j) {
1667                                 int in = (int) c->num[i + j];
1668                                 in += ((int) a->num[j]) * ((int) b->num[i]) + carry;
1669                                 carry = in / 10;
1670                                 c->num[i + j] = (BcDig)(in % 10);
1671                         }
1672
1673                         c->num[i + j] += (BcDig) carry;
1674                         len = BC_MAX(len, i + j + !!carry);
1675                         carry = 0;
1676                 }
1677
1678                 c->len = len;
1679
1680                 return BC_STATUS_SUCCESS;
1681         }
1682
1683         bc_num_init(&l1, max);
1684         bc_num_init(&h1, max);
1685         bc_num_init(&l2, max);
1686         bc_num_init(&h2, max);
1687         bc_num_init(&m1, max);
1688         bc_num_init(&m2, max);
1689         bc_num_init(&z0, max);
1690         bc_num_init(&z1, max);
1691         bc_num_init(&z2, max);
1692         bc_num_init(&temp, max + max);
1693
1694         bc_num_split(a, max2, &l1, &h1);
1695         bc_num_split(b, max2, &l2, &h2);
1696
1697         s = bc_num_add(&h1, &l1, &m1, 0);
1698         if (s) goto err;
1699         s = bc_num_add(&h2, &l2, &m2, 0);
1700         if (s) goto err;
1701
1702         s = bc_num_k(&h1, &h2, &z0);
1703         if (s) goto err;
1704         s = bc_num_k(&m1, &m2, &z1);
1705         if (s) goto err;
1706         s = bc_num_k(&l1, &l2, &z2);
1707         if (s) goto err;
1708
1709         s = bc_num_sub(&z1, &z0, &temp, 0);
1710         if (s) goto err;
1711         s = bc_num_sub(&temp, &z2, &z1, 0);
1712         if (s) goto err;
1713
1714         s = bc_num_shift(&z0, max2 * 2);
1715         if (s) goto err;
1716         s = bc_num_shift(&z1, max2);
1717         if (s) goto err;
1718         s = bc_num_add(&z0, &z1, &temp, 0);
1719         if (s) goto err;
1720         s = bc_num_add(&temp, &z2, c, 0);
1721
1722 err:
1723         bc_num_free(&temp);
1724         bc_num_free(&z2);
1725         bc_num_free(&z1);
1726         bc_num_free(&z0);
1727         bc_num_free(&m2);
1728         bc_num_free(&m1);
1729         bc_num_free(&h2);
1730         bc_num_free(&l2);
1731         bc_num_free(&h1);
1732         bc_num_free(&l1);
1733         return s;
1734 }
1735
1736 static BcStatus bc_num_m(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale)
1737 {
1738         BcStatus s;
1739         BcNum cpa, cpb;
1740         size_t maxrdx = BC_MAX(a->rdx, b->rdx);
1741
1742         scale = BC_MAX(scale, a->rdx);
1743         scale = BC_MAX(scale, b->rdx);
1744         scale = BC_MIN(a->rdx + b->rdx, scale);
1745         maxrdx = BC_MAX(maxrdx, scale);
1746
1747         bc_num_init(&cpa, a->len);
1748         bc_num_init(&cpb, b->len);
1749
1750         bc_num_copy(&cpa, a);
1751         bc_num_copy(&cpb, b);
1752         cpa.neg = cpb.neg = false;
1753
1754         s = bc_num_shift(&cpa, maxrdx);
1755         if (s) goto err;
1756         s = bc_num_shift(&cpb, maxrdx);
1757         if (s) goto err;
1758         s = bc_num_k(&cpa, &cpb, c);
1759         if (s) goto err;
1760
1761         maxrdx += scale;
1762         bc_num_expand(c, c->len + maxrdx);
1763
1764         if (c->len < maxrdx) {
1765                 memset(c->num + c->len, 0, (c->cap - c->len) * sizeof(BcDig));
1766                 c->len += maxrdx;
1767         }
1768
1769         c->rdx = maxrdx;
1770         bc_num_retireMul(c, scale, a->neg, b->neg);
1771
1772 err:
1773         bc_num_free(&cpb);
1774         bc_num_free(&cpa);
1775         return s;
1776 }
1777
1778 static BcStatus bc_num_d(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale)
1779 {
1780         BcStatus s = BC_STATUS_SUCCESS;
1781         BcDig *n, *p, q;
1782         size_t len, end, i;
1783         BcNum cp;
1784         bool zero = true;
1785
1786         if (b->len == 0)
1787                 return bc_error("divide by zero");
1788         else if (a->len == 0) {
1789                 bc_num_setToZero(c, scale);
1790                 return BC_STATUS_SUCCESS;
1791         }
1792         else if (BC_NUM_ONE(b)) {
1793                 bc_num_copy(c, a);
1794                 bc_num_retireMul(c, scale, a->neg, b->neg);
1795                 return BC_STATUS_SUCCESS;
1796         }
1797
1798         bc_num_init(&cp, BC_NUM_MREQ(a, b, scale));
1799         bc_num_copy(&cp, a);
1800         len = b->len;
1801
1802         if (len > cp.len) {
1803                 bc_num_expand(&cp, len + 2);
1804                 bc_num_extend(&cp, len - cp.len);
1805         }
1806
1807         if (b->rdx > cp.rdx) bc_num_extend(&cp, b->rdx - cp.rdx);
1808         cp.rdx -= b->rdx;
1809         if (scale > cp.rdx) bc_num_extend(&cp, scale - cp.rdx);
1810
1811         if (b->rdx == b->len) {
1812                 for (i = 0; zero && i < len; ++i) zero = !b->num[len - i - 1];
1813                 len -= i - 1;
1814         }
1815
1816         if (cp.cap == cp.len) bc_num_expand(&cp, cp.len + 1);
1817
1818         // We want an extra zero in front to make things simpler.
1819         cp.num[cp.len++] = 0;
1820         end = cp.len - len;
1821
1822         bc_num_expand(c, cp.len);
1823
1824         bc_num_zero(c);
1825         memset(c->num + end, 0, (c->cap - end) * sizeof(BcDig));
1826         c->rdx = cp.rdx;
1827         c->len = cp.len;
1828         p = b->num;
1829
1830         for (i = end - 1; !s && i < end; --i) {
1831                 n = cp.num + i;
1832                 for (q = 0; (!s && n[len] != 0) || bc_num_compare(n, p, len) >= 0; ++q)
1833                         bc_num_subArrays(n, p, len);
1834                 c->num[i] = q;
1835         }
1836
1837         bc_num_retireMul(c, scale, a->neg, b->neg);
1838         bc_num_free(&cp);
1839
1840         return BC_STATUS_SUCCESS; // can't make void, see bc_num_binary()
1841 }
1842
1843 static BcStatus bc_num_r(BcNum *a, BcNum *b, BcNum *restrict c,
1844                          BcNum *restrict d, size_t scale, size_t ts)
1845 {
1846         BcStatus s;
1847         BcNum temp;
1848         bool neg;
1849
1850         if (b->len == 0)
1851                 return bc_error("divide by zero");
1852
1853         if (a->len == 0) {
1854                 bc_num_setToZero(d, ts);
1855                 return BC_STATUS_SUCCESS;
1856         }
1857
1858         bc_num_init(&temp, d->cap);
1859         bc_num_d(a, b, c, scale);
1860
1861         if (scale != 0) scale = ts;
1862
1863         s = bc_num_m(c, b, &temp, scale);
1864         if (s) goto err;
1865         s = bc_num_sub(a, &temp, d, scale);
1866         if (s) goto err;
1867
1868         if (ts > d->rdx && d->len) bc_num_extend(d, ts - d->rdx);
1869
1870         neg = d->neg;
1871         bc_num_retireMul(d, ts, a->neg, b->neg);
1872         d->neg = neg;
1873
1874 err:
1875         bc_num_free(&temp);
1876         return s;
1877 }
1878
1879 static BcStatus bc_num_rem(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale)
1880 {
1881         BcStatus s;
1882         BcNum c1;
1883         size_t ts = BC_MAX(scale + b->rdx, a->rdx), len = BC_NUM_MREQ(a, b, ts);
1884
1885         bc_num_init(&c1, len);
1886         s = bc_num_r(a, b, &c1, c, scale, ts);
1887         bc_num_free(&c1);
1888
1889         return s;
1890 }
1891
1892 static BcStatus bc_num_p(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale)
1893 {
1894         BcStatus s = BC_STATUS_SUCCESS;
1895         BcNum copy;
1896         unsigned long pow;
1897         size_t i, powrdx, resrdx;
1898         bool neg, zero;
1899
1900         if (b->rdx) return bc_error("non integer number");
1901
1902         if (b->len == 0) {
1903                 bc_num_one(c);
1904                 return BC_STATUS_SUCCESS;
1905         }
1906         else if (a->len == 0) {
1907                 bc_num_setToZero(c, scale);
1908                 return BC_STATUS_SUCCESS;
1909         }
1910         else if (BC_NUM_ONE(b)) {
1911                 if (!b->neg)
1912                         bc_num_copy(c, a);
1913                 else
1914                         s = bc_num_inv(a, c, scale);
1915                 return s;
1916         }
1917
1918         neg = b->neg;
1919         b->neg = false;
1920
1921         s = bc_num_ulong(b, &pow);
1922         if (s) return s;
1923
1924         bc_num_init(&copy, a->len);
1925         bc_num_copy(&copy, a);
1926
1927         if (!neg) scale = BC_MIN(a->rdx * pow, BC_MAX(scale, a->rdx));
1928
1929         b->neg = neg;
1930
1931         for (powrdx = a->rdx; !(pow & 1); pow >>= 1) {
1932                 powrdx <<= 1;
1933                 s = bc_num_mul(&copy, &copy, &copy, powrdx);
1934                 if (s) goto err;
1935                 // It is too slow to handle ^C only after entire "2^1000000" completes
1936                 if (G_interrupt) {
1937                         s = BC_STATUS_FAILURE;
1938                         goto err;
1939                 }
1940         }
1941
1942         bc_num_copy(c, &copy);
1943
1944         for (resrdx = powrdx, pow >>= 1; pow != 0; pow >>= 1) {
1945
1946                 powrdx <<= 1;
1947                 s = bc_num_mul(&copy, &copy, &copy, powrdx);
1948                 if (s) goto err;
1949
1950                 if (pow & 1) {
1951                         resrdx += powrdx;
1952                         s = bc_num_mul(c, &copy, c, resrdx);
1953                         if (s) goto err;
1954                 }
1955                 // It is too slow to handle ^C only after entire "2^1000000" completes
1956                 if (G_interrupt) {
1957                         s = BC_STATUS_FAILURE;
1958                         goto err;
1959                 }
1960         }
1961
1962         if (neg) {
1963                 s = bc_num_inv(c, c, scale);
1964                 if (s) goto err;
1965         }
1966
1967         if (c->rdx > scale) bc_num_truncate(c, c->rdx - scale);
1968
1969         // We can't use bc_num_clean() here.
1970         for (zero = true, i = 0; zero && i < c->len; ++i) zero = !c->num[i];
1971         if (zero) bc_num_setToZero(c, scale);
1972
1973 err:
1974         bc_num_free(&copy);
1975         return s;
1976 }
1977
1978 static BcStatus bc_num_binary(BcNum *a, BcNum *b, BcNum *c, size_t scale,
1979                               BcNumBinaryOp op, size_t req)
1980 {
1981         BcStatus s;
1982         BcNum num2, *ptr_a, *ptr_b;
1983         bool init = false;
1984
1985         if (c == a) {
1986                 ptr_a = &num2;
1987                 memcpy(ptr_a, c, sizeof(BcNum));
1988                 init = true;
1989         }
1990         else
1991                 ptr_a = a;
1992
1993         if (c == b) {
1994                 ptr_b = &num2;
1995                 if (c != a) {
1996                         memcpy(ptr_b, c, sizeof(BcNum));
1997                         init = true;
1998                 }
1999         }
2000         else
2001                 ptr_b = b;
2002
2003         if (init)
2004                 bc_num_init(c, req);
2005         else
2006                 bc_num_expand(c, req);
2007
2008         s = op(ptr_a, ptr_b, c, scale);
2009
2010         if (init) bc_num_free(&num2);
2011
2012         return s;
2013 }
2014
2015 static bool bc_num_strValid(const char *val, size_t base)
2016 {
2017         BcDig b;
2018         bool small, radix = false;
2019         size_t i, len = strlen(val);
2020
2021         if (!len) return true;
2022
2023         small = base <= 10;
2024         b = (BcDig)(small ? base + '0' : base - 10 + 'A');
2025
2026         for (i = 0; i < len; ++i) {
2027
2028                 BcDig c = val[i];
2029
2030                 if (c == '.') {
2031
2032                         if (radix) return false;
2033
2034                         radix = true;
2035                         continue;
2036                 }
2037
2038                 if (c < '0' || (small && c >= b) || (c > '9' && (c < 'A' || c >= b)))
2039                         return false;
2040         }
2041
2042         return true;
2043 }
2044
2045 static void bc_num_parseDecimal(BcNum *n, const char *val)
2046 {
2047         size_t len, i;
2048         const char *ptr;
2049         bool zero = true;
2050
2051         for (i = 0; val[i] == '0'; ++i);
2052
2053         val += i;
2054         len = strlen(val);
2055         bc_num_zero(n);
2056
2057         if (len != 0) {
2058                 for (i = 0; zero && i < len; ++i) zero = val[i] == '0' || val[i] == '.';
2059                 bc_num_expand(n, len);
2060         }
2061
2062         ptr = strchr(val, '.');
2063
2064         n->rdx = 0;
2065         if (ptr != NULL)
2066                 n->rdx = (size_t)((val + len) - (ptr + 1));
2067
2068         if (!zero) {
2069                 for (i = len - 1; i < len; ++n->len, i -= 1 + (i && val[i - 1] == '.'))
2070                         n->num[n->len] = val[i] - '0';
2071         }
2072 }
2073
2074 static void bc_num_parseBase(BcNum *n, const char *val, BcNum *base)
2075 {
2076         BcStatus s;
2077         BcNum temp, mult, result;
2078         BcDig c = '\0';
2079         bool zero = true;
2080         unsigned long v;
2081         size_t i, digits, len = strlen(val);
2082
2083         bc_num_zero(n);
2084
2085         for (i = 0; zero && i < len; ++i) zero = (val[i] == '.' || val[i] == '0');
2086         if (zero) return;
2087
2088         bc_num_init(&temp, BC_NUM_DEF_SIZE);
2089         bc_num_init(&mult, BC_NUM_DEF_SIZE);
2090
2091         for (i = 0; i < len; ++i) {
2092
2093                 c = val[i];
2094                 if (c == '.') break;
2095
2096                 v = (unsigned long) (c <= '9' ? c - '0' : c - 'A' + 10);
2097
2098                 s = bc_num_mul(n, base, &mult, 0);
2099                 if (s) goto int_err;
2100                 bc_num_ulong2num(&temp, v);
2101                 s = bc_num_add(&mult, &temp, n, 0);
2102                 if (s) goto int_err;
2103         }
2104
2105         if (i == len) {
2106                 c = val[i];
2107                 if (c == 0) goto int_err;
2108         }
2109
2110         bc_num_init(&result, base->len);
2111         bc_num_zero(&result);
2112         bc_num_one(&mult);
2113
2114         for (i += 1, digits = 0; i < len; ++i, ++digits) {
2115
2116                 c = val[i];
2117                 if (c == 0) break;
2118
2119                 v = (unsigned long) (c <= '9' ? c - '0' : c - 'A' + 10);
2120
2121                 s = bc_num_mul(&result, base, &result, 0);
2122                 if (s) goto err;
2123                 bc_num_ulong2num(&temp, v);
2124                 s = bc_num_add(&result, &temp, &result, 0);
2125                 if (s) goto err;
2126                 s = bc_num_mul(&mult, base, &mult, 0);
2127                 if (s) goto err;
2128         }
2129
2130         s = bc_num_div(&result, &mult, &result, digits);
2131         if (s) goto err;
2132         s = bc_num_add(n, &result, n, digits);
2133         if (s) goto err;
2134
2135         if (n->len != 0) {
2136                 if (n->rdx < digits) bc_num_extend(n, digits - n->rdx);
2137         }
2138         else
2139                 bc_num_zero(n);
2140
2141 err:
2142         bc_num_free(&result);
2143 int_err:
2144         bc_num_free(&mult);
2145         bc_num_free(&temp);
2146 }
2147
2148 static void bc_num_printNewline(size_t *nchars, size_t line_len)
2149 {
2150         if (*nchars == line_len - 1) {
2151                 bb_putchar('\\');
2152                 bb_putchar('\n');
2153                 *nchars = 0;
2154         }
2155 }
2156
2157 #if ENABLE_DC
2158 static void bc_num_printChar(size_t num, size_t width, bool radix,
2159                              size_t *nchars, size_t line_len)
2160 {
2161         (void) radix, (void) line_len;
2162         bb_putchar((char) num);
2163         *nchars = *nchars + width;
2164 }
2165 #endif
2166
2167 static void bc_num_printDigits(size_t num, size_t width, bool radix,
2168                                size_t *nchars, size_t line_len)
2169 {
2170         size_t exp, pow;
2171
2172         bc_num_printNewline(nchars, line_len);
2173         bb_putchar(radix ? '.' : ' ');
2174         ++(*nchars);
2175
2176         bc_num_printNewline(nchars, line_len);
2177         for (exp = 0, pow = 1; exp < width - 1; ++exp, pow *= 10)
2178                 continue;
2179
2180         for (exp = 0; exp < width; pow /= 10, ++(*nchars), ++exp) {
2181                 size_t dig;
2182                 bc_num_printNewline(nchars, line_len);
2183                 dig = num / pow;
2184                 num -= dig * pow;
2185                 bb_putchar(((char) dig) + '0');
2186         }
2187 }
2188
2189 static void bc_num_printHex(size_t num, size_t width, bool radix,
2190                             size_t *nchars, size_t line_len)
2191 {
2192         if (radix) {
2193                 bc_num_printNewline(nchars, line_len);
2194                 bb_putchar('.');
2195                 *nchars += 1;
2196         }
2197
2198         bc_num_printNewline(nchars, line_len);
2199         bb_putchar(bb_hexdigits_upcase[num]);
2200         *nchars = *nchars + width;
2201 }
2202
2203 static void bc_num_printDecimal(BcNum *n, size_t *nchars, size_t len)
2204 {
2205         size_t i, rdx = n->rdx - 1;
2206
2207         if (n->neg) bb_putchar('-');
2208         (*nchars) += n->neg;
2209
2210         for (i = n->len - 1; i < n->len; --i)
2211                 bc_num_printHex((size_t) n->num[i], 1, i == rdx, nchars, len);
2212 }
2213
2214 static BcStatus bc_num_printNum(BcNum *n, BcNum *base, size_t width,
2215                                 size_t *nchars, size_t len, BcNumDigitOp print)
2216 {
2217         BcStatus s;
2218         BcVec stack;
2219         BcNum intp, fracp, digit, frac_len;
2220         unsigned long dig, *ptr;
2221         size_t i;
2222         bool radix;
2223
2224         if (n->len == 0) {
2225                 print(0, width, false, nchars, len);
2226                 return BC_STATUS_SUCCESS;
2227         }
2228
2229         bc_vec_init(&stack, sizeof(long), NULL);
2230         bc_num_init(&intp, n->len);
2231         bc_num_init(&fracp, n->rdx);
2232         bc_num_init(&digit, width);
2233         bc_num_init(&frac_len, BC_NUM_INT(n));
2234         bc_num_copy(&intp, n);
2235         bc_num_one(&frac_len);
2236
2237         bc_num_truncate(&intp, intp.rdx);
2238         s = bc_num_sub(n, &intp, &fracp, 0);
2239         if (s) goto err;
2240
2241         while (intp.len != 0) {
2242                 s = bc_num_divmod(&intp, base, &intp, &digit, 0);
2243                 if (s) goto err;
2244                 s = bc_num_ulong(&digit, &dig);
2245                 if (s) goto err;
2246                 bc_vec_push(&stack, &dig);
2247         }
2248
2249         for (i = 0; i < stack.len; ++i) {
2250                 ptr = bc_vec_item_rev(&stack, i);
2251                 print(*ptr, width, false, nchars, len);
2252         }
2253
2254         if (!n->rdx) goto err;
2255
2256         for (radix = true; frac_len.len <= n->rdx; radix = false) {
2257                 s = bc_num_mul(&fracp, base, &fracp, n->rdx);
2258                 if (s) goto err;
2259                 s = bc_num_ulong(&fracp, &dig);
2260                 if (s) goto err;
2261                 bc_num_ulong2num(&intp, dig);
2262                 s = bc_num_sub(&fracp, &intp, &fracp, 0);
2263                 if (s) goto err;
2264                 print(dig, width, radix, nchars, len);
2265                 s = bc_num_mul(&frac_len, base, &frac_len, 0);
2266                 if (s) goto err;
2267         }
2268
2269 err:
2270         bc_num_free(&frac_len);
2271         bc_num_free(&digit);
2272         bc_num_free(&fracp);
2273         bc_num_free(&intp);
2274         bc_vec_free(&stack);
2275         return s;
2276 }
2277
2278 static BcStatus bc_num_printBase(BcNum *n, BcNum *base, size_t base_t,
2279                                  size_t *nchars, size_t line_len)
2280 {
2281         BcStatus s;
2282         size_t width, i;
2283         BcNumDigitOp print;
2284         bool neg = n->neg;
2285
2286         if (neg) bb_putchar('-');
2287         (*nchars) += neg;
2288
2289         n->neg = false;
2290
2291         if (base_t <= BC_NUM_MAX_IBASE) {
2292                 width = 1;
2293                 print = bc_num_printHex;
2294         }
2295         else {
2296                 for (i = base_t - 1, width = 0; i != 0; i /= 10, ++width);
2297                 print = bc_num_printDigits;
2298         }
2299
2300         s = bc_num_printNum(n, base, width, nchars, line_len, print);
2301         n->neg = neg;
2302
2303         return s;
2304 }
2305
2306 #if ENABLE_DC
2307 static BcStatus bc_num_stream(BcNum *n, BcNum *base, size_t *nchars, size_t len)
2308 {
2309         return bc_num_printNum(n, base, 1, nchars, len, bc_num_printChar);
2310 }
2311 #endif
2312
2313 static void bc_num_init(BcNum *n, size_t req)
2314 {
2315         req = req >= BC_NUM_DEF_SIZE ? req : BC_NUM_DEF_SIZE;
2316         memset(n, 0, sizeof(BcNum));
2317         n->num = xmalloc(req);
2318         n->cap = req;
2319 }
2320
2321 static void bc_num_expand(BcNum *n, size_t req)
2322 {
2323         req = req >= BC_NUM_DEF_SIZE ? req : BC_NUM_DEF_SIZE;
2324         if (req > n->cap) {
2325                 n->num = xrealloc(n->num, req);
2326                 n->cap = req;
2327         }
2328 }
2329
2330 static void bc_num_free(void *num)
2331 {
2332         free(((BcNum *) num)->num);
2333 }
2334
2335 static void bc_num_copy(BcNum *d, BcNum *s)
2336 {
2337         if (d != s) {
2338                 bc_num_expand(d, s->cap);
2339                 d->len = s->len;
2340                 d->neg = s->neg;
2341                 d->rdx = s->rdx;
2342                 memcpy(d->num, s->num, sizeof(BcDig) * d->len);
2343         }
2344 }
2345
2346 static BcStatus bc_num_parse(BcNum *n, const char *val, BcNum *base,
2347                              size_t base_t)
2348 {
2349         if (!bc_num_strValid(val, base_t))
2350                 return bc_error("bad number string");
2351
2352         if (base_t == 10)
2353                 bc_num_parseDecimal(n, val);
2354         else
2355                 bc_num_parseBase(n, val, base);
2356
2357         return BC_STATUS_SUCCESS;
2358 }
2359
2360 static BcStatus bc_num_print(BcNum *n, BcNum *base, size_t base_t, bool newline,
2361                              size_t *nchars, size_t line_len)
2362 {
2363         BcStatus s = BC_STATUS_SUCCESS;
2364
2365         bc_num_printNewline(nchars, line_len);
2366
2367         if (n->len == 0) {
2368                 bb_putchar('0');
2369                 ++(*nchars);
2370         }
2371         else if (base_t == 10)
2372                 bc_num_printDecimal(n, nchars, line_len);
2373         else
2374                 s = bc_num_printBase(n, base, base_t, nchars, line_len);
2375
2376         if (newline) {
2377                 bb_putchar('\n');
2378                 *nchars = 0;
2379         }
2380
2381         return s;
2382 }
2383
2384 static BcStatus bc_num_ulong(BcNum *n, unsigned long *result)
2385 {
2386         size_t i;
2387         unsigned long pow;
2388
2389         if (n->neg) return bc_error("negative number");
2390
2391         for (*result = 0, pow = 1, i = n->rdx; i < n->len; ++i) {
2392
2393                 unsigned long prev = *result, powprev = pow;
2394
2395                 *result += ((unsigned long) n->num[i]) * pow;
2396                 pow *= 10;
2397
2398                 if (*result < prev || pow < powprev)
2399                         return bc_error("overflow");
2400         }
2401
2402         return BC_STATUS_SUCCESS;
2403 }
2404
2405 static void bc_num_ulong2num(BcNum *n, unsigned long val)
2406 {
2407         size_t len;
2408         BcDig *ptr;
2409         unsigned long i;
2410
2411         bc_num_zero(n);
2412
2413         if (val == 0) return;
2414
2415         for (len = 1, i = ULONG_MAX; i != 0; i /= 10, ++len) bc_num_expand(n, len);
2416         for (ptr = n->num, i = 0; val; ++i, ++n->len, val /= 10) ptr[i] = val % 10;
2417 }
2418
2419 static BcStatus bc_num_add(BcNum *a, BcNum *b, BcNum *c, size_t scale)
2420 {
2421         BcNumBinaryOp op = (!a->neg == !b->neg) ? bc_num_a : bc_num_s;
2422         (void) scale;
2423         return bc_num_binary(a, b, c, false, op, BC_NUM_AREQ(a, b));
2424 }
2425
2426 static BcStatus bc_num_sub(BcNum *a, BcNum *b, BcNum *c, size_t scale)
2427 {
2428         BcNumBinaryOp op = (!a->neg == !b->neg) ? bc_num_s : bc_num_a;
2429         (void) scale;
2430         return bc_num_binary(a, b, c, true, op, BC_NUM_AREQ(a, b));
2431 }
2432
2433 static BcStatus bc_num_mul(BcNum *a, BcNum *b, BcNum *c, size_t scale)
2434 {
2435         size_t req = BC_NUM_MREQ(a, b, scale);
2436         return bc_num_binary(a, b, c, scale, bc_num_m, req);
2437 }
2438
2439 static BcStatus bc_num_div(BcNum *a, BcNum *b, BcNum *c, size_t scale)
2440 {
2441         size_t req = BC_NUM_MREQ(a, b, scale);
2442         return bc_num_binary(a, b, c, scale, bc_num_d, req);
2443 }
2444
2445 static BcStatus bc_num_mod(BcNum *a, BcNum *b, BcNum *c, size_t scale)
2446 {
2447         size_t req = BC_NUM_MREQ(a, b, scale);
2448         return bc_num_binary(a, b, c, scale, bc_num_rem, req);
2449 }
2450
2451 static BcStatus bc_num_pow(BcNum *a, BcNum *b, BcNum *c, size_t scale)
2452 {
2453         return bc_num_binary(a, b, c, scale, bc_num_p, a->len * b->len + 1);
2454 }
2455
2456 static BcStatus bc_num_sqrt(BcNum *a, BcNum *restrict b, size_t scale)
2457 {
2458         BcStatus s;
2459         BcNum num1, num2, half, f, fprime, *x0, *x1, *temp;
2460         size_t pow, len, digs, digs1, resrdx, req, times = 0;
2461         ssize_t cmp = 1, cmp1 = SSIZE_MAX, cmp2 = SSIZE_MAX;
2462
2463         req = BC_MAX(scale, a->rdx) + ((BC_NUM_INT(a) + 1) >> 1) + 1;
2464         bc_num_expand(b, req);
2465
2466         if (a->len == 0) {
2467                 bc_num_setToZero(b, scale);
2468                 return BC_STATUS_SUCCESS;
2469         }
2470         else if (a->neg)
2471                 return bc_error("negative number");
2472         else if (BC_NUM_ONE(a)) {
2473                 bc_num_one(b);
2474                 bc_num_extend(b, scale);
2475                 return BC_STATUS_SUCCESS;
2476         }
2477
2478         scale = BC_MAX(scale, a->rdx) + 1;
2479         len = a->len + scale;
2480
2481         bc_num_init(&num1, len);
2482         bc_num_init(&num2, len);
2483         bc_num_init(&half, BC_NUM_DEF_SIZE);
2484
2485         bc_num_one(&half);
2486         half.num[0] = 5;
2487         half.rdx = 1;
2488
2489         bc_num_init(&f, len);
2490         bc_num_init(&fprime, len);
2491
2492         x0 = &num1;
2493         x1 = &num2;
2494
2495         bc_num_one(x0);
2496         pow = BC_NUM_INT(a);
2497
2498         if (pow) {
2499
2500                 if (pow & 1)
2501                         x0->num[0] = 2;
2502                 else
2503                         x0->num[0] = 6;
2504
2505                 pow -= 2 - (pow & 1);
2506
2507                 bc_num_extend(x0, pow);
2508
2509                 // Make sure to move the radix back.
2510                 x0->rdx -= pow;
2511         }
2512
2513         x0->rdx = digs = digs1 = 0;
2514         resrdx = scale + 2;
2515         len = BC_NUM_INT(x0) + resrdx - 1;
2516
2517         while (cmp != 0 || digs < len) {
2518
2519                 s = bc_num_div(a, x0, &f, resrdx);
2520                 if (s) goto err;
2521                 s = bc_num_add(x0, &f, &fprime, resrdx);
2522                 if (s) goto err;
2523                 s = bc_num_mul(&fprime, &half, x1, resrdx);
2524                 if (s) goto err;
2525
2526                 cmp = bc_num_cmp(x1, x0);
2527                 digs = x1->len - (unsigned long long) llabs(cmp);
2528
2529                 if (cmp == cmp2 && digs == digs1)
2530                         times += 1;
2531                 else
2532                         times = 0;
2533
2534                 resrdx += times > 4;
2535
2536                 cmp2 = cmp1;
2537                 cmp1 = cmp;
2538                 digs1 = digs;
2539
2540                 temp = x0;
2541                 x0 = x1;
2542                 x1 = temp;
2543         }
2544
2545         bc_num_copy(b, x0);
2546         scale -= 1;
2547         if (b->rdx > scale) bc_num_truncate(b, b->rdx - scale);
2548
2549 err:
2550         bc_num_free(&fprime);
2551         bc_num_free(&f);
2552         bc_num_free(&half);
2553         bc_num_free(&num2);
2554         bc_num_free(&num1);
2555         return s;
2556 }
2557
2558 static BcStatus bc_num_divmod(BcNum *a, BcNum *b, BcNum *c, BcNum *d,
2559                               size_t scale)
2560 {
2561         BcStatus s;
2562         BcNum num2, *ptr_a;
2563         bool init = false;
2564         size_t ts = BC_MAX(scale + b->rdx, a->rdx), len = BC_NUM_MREQ(a, b, ts);
2565
2566         if (c == a) {
2567                 memcpy(&num2, c, sizeof(BcNum));
2568                 ptr_a = &num2;
2569                 bc_num_init(c, len);
2570                 init = true;
2571         }
2572         else {
2573                 ptr_a = a;
2574                 bc_num_expand(c, len);
2575         }
2576
2577         s = bc_num_r(ptr_a, b, c, d, scale, ts);
2578
2579         if (init) bc_num_free(&num2);
2580
2581         return s;
2582 }
2583
2584 #if ENABLE_DC
2585 static BcStatus bc_num_modexp(BcNum *a, BcNum *b, BcNum *c, BcNum *restrict d)
2586 {
2587         BcStatus s;
2588         BcNum base, exp, two, temp;
2589
2590         if (c->len == 0)
2591                 return bc_error("divide by zero");
2592         if (a->rdx || b->rdx || c->rdx)
2593                 return bc_error("non integer number");
2594         if (b->neg)
2595                 return bc_error("negative number");
2596
2597         bc_num_expand(d, c->len);
2598         bc_num_init(&base, c->len);
2599         bc_num_init(&exp, b->len);
2600         bc_num_init(&two, BC_NUM_DEF_SIZE);
2601         bc_num_init(&temp, b->len);
2602
2603         bc_num_one(&two);
2604         two.num[0] = 2;
2605         bc_num_one(d);
2606
2607         s = bc_num_rem(a, c, &base, 0);
2608         if (s) goto err;
2609         bc_num_copy(&exp, b);
2610
2611         while (exp.len != 0) {
2612
2613                 s = bc_num_divmod(&exp, &two, &exp, &temp, 0);
2614                 if (s) goto err;
2615
2616                 if (BC_NUM_ONE(&temp)) {
2617                         s = bc_num_mul(d, &base, &temp, 0);
2618                         if (s) goto err;
2619                         s = bc_num_rem(&temp, c, d, 0);
2620                         if (s) goto err;
2621                 }
2622
2623                 s = bc_num_mul(&base, &base, &temp, 0);
2624                 if (s) goto err;
2625                 s = bc_num_rem(&temp, c, &base, 0);
2626                 if (s) goto err;
2627         }
2628
2629 err:
2630         bc_num_free(&temp);
2631         bc_num_free(&two);
2632         bc_num_free(&exp);
2633         bc_num_free(&base);
2634         return s;
2635 }
2636 #endif // ENABLE_DC
2637
2638 static int bc_id_cmp(const void *e1, const void *e2)
2639 {
2640         return strcmp(((const BcId *) e1)->name, ((const BcId *) e2)->name);
2641 }
2642
2643 static void bc_id_free(void *id)
2644 {
2645         free(((BcId *) id)->name);
2646 }
2647
2648 static BcStatus bc_func_insert(BcFunc *f, char *name, bool var)
2649 {
2650         BcId a;
2651         size_t i;
2652
2653         for (i = 0; i < f->autos.len; ++i) {
2654                 if (strcmp(name, ((BcId *) bc_vec_item(&f->autos, i))->name) == 0)
2655                         return bc_error("function parameter or auto var has the same name as another");
2656         }
2657
2658         a.idx = var;
2659         a.name = name;
2660
2661         bc_vec_push(&f->autos, &a);
2662
2663         return BC_STATUS_SUCCESS;
2664 }
2665
2666 static void bc_func_init(BcFunc *f)
2667 {
2668         bc_char_vec_init(&f->code);
2669         bc_vec_init(&f->autos, sizeof(BcId), bc_id_free);
2670         bc_vec_init(&f->labels, sizeof(size_t), NULL);
2671         f->nparams = 0;
2672 }
2673
2674 static void bc_func_free(void *func)
2675 {
2676         BcFunc *f = (BcFunc *) func;
2677         bc_vec_free(&f->code);
2678         bc_vec_free(&f->autos);
2679         bc_vec_free(&f->labels);
2680 }
2681
2682 static void bc_array_init(BcVec *a, bool nums)
2683 {
2684         if (nums)
2685                 bc_vec_init(a, sizeof(BcNum), bc_num_free);
2686         else
2687                 bc_vec_init(a, sizeof(BcVec), bc_vec_free);
2688         bc_array_expand(a, 1);
2689 }
2690
2691 static void bc_array_copy(BcVec *d, const BcVec *s)
2692 {
2693         size_t i;
2694
2695         bc_vec_pop_all(d);
2696         bc_vec_expand(d, s->cap);
2697         d->len = s->len;
2698
2699         for (i = 0; i < s->len; ++i) {
2700                 BcNum *dnum = bc_vec_item(d, i), *snum = bc_vec_item(s, i);
2701                 bc_num_init(dnum, snum->len);
2702                 bc_num_copy(dnum, snum);
2703         }
2704 }
2705
2706 static void bc_array_expand(BcVec *a, size_t len)
2707 {
2708         BcResultData data;
2709
2710         if (a->size == sizeof(BcNum) && a->dtor == bc_num_free) {
2711                 while (len > a->len) {
2712                         bc_num_init(&data.n, BC_NUM_DEF_SIZE);
2713                         bc_vec_push(a, &data.n);
2714                 }
2715         }
2716         else {
2717                 while (len > a->len) {
2718                         bc_array_init(&data.v, true);
2719                         bc_vec_push(a, &data.v);
2720                 }
2721         }
2722 }
2723
2724 static void bc_string_free(void *string)
2725 {
2726         free(*((char **) string));
2727 }
2728
2729 #if ENABLE_DC
2730 static void bc_result_copy(BcResult *d, BcResult *src)
2731 {
2732         d->t = src->t;
2733
2734         switch (d->t) {
2735
2736                 case BC_RESULT_TEMP:
2737                 case BC_RESULT_IBASE:
2738                 case BC_RESULT_SCALE:
2739                 case BC_RESULT_OBASE:
2740                 {
2741                         bc_num_init(&d->d.n, src->d.n.len);
2742                         bc_num_copy(&d->d.n, &src->d.n);
2743                         break;
2744                 }
2745
2746                 case BC_RESULT_VAR:
2747                 case BC_RESULT_ARRAY:
2748                 case BC_RESULT_ARRAY_ELEM:
2749                 {
2750                         d->d.id.name = xstrdup(src->d.id.name);
2751                         break;
2752                 }
2753
2754                 case BC_RESULT_CONSTANT:
2755                 case BC_RESULT_LAST:
2756                 case BC_RESULT_ONE:
2757                 case BC_RESULT_STR:
2758                 {
2759                         memcpy(&d->d.n, &src->d.n, sizeof(BcNum));
2760                         break;
2761                 }
2762         }
2763 }
2764 #endif // ENABLE_DC
2765
2766 static void bc_result_free(void *result)
2767 {
2768         BcResult *r = (BcResult *) result;
2769
2770         switch (r->t) {
2771
2772                 case BC_RESULT_TEMP:
2773                 case BC_RESULT_IBASE:
2774                 case BC_RESULT_SCALE:
2775                 case BC_RESULT_OBASE:
2776                 {
2777                         bc_num_free(&r->d.n);
2778                         break;
2779                 }
2780
2781                 case BC_RESULT_VAR:
2782                 case BC_RESULT_ARRAY:
2783                 case BC_RESULT_ARRAY_ELEM:
2784                 {
2785                         free(r->d.id.name);
2786                         break;
2787                 }
2788
2789                 default:
2790                 {
2791                         // Do nothing.
2792                         break;
2793                 }
2794         }
2795 }
2796
2797 static void bc_lex_lineComment(BcLex *l)
2798 {
2799         l->t.t = BC_LEX_WHITESPACE;
2800         while (l->i < l->len && l->buf[l->i++] != '\n');
2801         --l->i;
2802 }
2803
2804 static void bc_lex_whitespace(BcLex *l)
2805 {
2806         char c;
2807         l->t.t = BC_LEX_WHITESPACE;
2808         for (c = l->buf[l->i]; c != '\n' && isspace(c); c = l->buf[++l->i]);
2809 }
2810
2811 static BcStatus bc_lex_number(BcLex *l, char start)
2812 {
2813         const char *buf = l->buf + l->i;
2814         size_t len, hits = 0, bslashes = 0, i = 0, j;
2815         char c = buf[i];
2816         bool last_pt, pt = start == '.';
2817
2818         last_pt = pt;
2819         l->t.t = BC_LEX_NUMBER;
2820
2821         while (c != 0 && (isdigit(c) || (c >= 'A' && c <= 'F') ||
2822                           (c == '.' && !pt) || (c == '\\' && buf[i + 1] == '\n')))
2823         {
2824                 if (c != '\\') {
2825                         last_pt = c == '.';
2826                         pt = pt || last_pt;
2827                 }
2828                 else {
2829                         ++i;
2830                         bslashes += 1;
2831                 }
2832
2833                 c = buf[++i];
2834         }
2835
2836         len = i + !last_pt - bslashes * 2;
2837         if (len > BC_MAX_NUM)
2838                 return bc_error("number too long: must be [1, BC_NUM_MAX]");
2839
2840         bc_vec_pop_all(&l->t.v);
2841         bc_vec_expand(&l->t.v, len + 1);
2842         bc_vec_push(&l->t.v, &start);
2843
2844         for (buf -= 1, j = 1; j < len + hits * 2; ++j) {
2845
2846                 c = buf[j];
2847
2848                 // If we have hit a backslash, skip it. We don't have
2849                 // to check for a newline because it's guaranteed.
2850                 if (hits < bslashes && c == '\\') {
2851                         ++hits;
2852                         ++j;
2853                         continue;
2854                 }
2855
2856                 bc_vec_push(&l->t.v, &c);
2857         }
2858
2859         bc_vec_pushZeroByte(&l->t.v);
2860         l->i += i;
2861
2862         return BC_STATUS_SUCCESS;
2863 }
2864
2865 static BcStatus bc_lex_name(BcLex *l)
2866 {
2867         size_t i = 0;
2868         const char *buf = l->buf + l->i - 1;
2869         char c = buf[i];
2870
2871         l->t.t = BC_LEX_NAME;
2872
2873         while ((c >= 'a' && c <= 'z') || isdigit(c) || c == '_') c = buf[++i];
2874
2875         if (i > BC_MAX_STRING)
2876                 return bc_error("name too long: must be [1, BC_NAME_MAX]");
2877         bc_vec_string(&l->t.v, i, buf);
2878
2879         // Increment the index. We minus 1 because it has already been incremented.
2880         l->i += i - 1;
2881
2882         return BC_STATUS_SUCCESS;
2883 }
2884
2885 static void bc_lex_init(BcLex *l, BcLexNext next)
2886 {
2887         l->next = next;
2888         bc_char_vec_init(&l->t.v);
2889 }
2890
2891 static void bc_lex_free(BcLex *l)
2892 {
2893         bc_vec_free(&l->t.v);
2894 }
2895
2896 static void bc_lex_file(BcLex *l)
2897 {
2898         G.err_line = l->line = 1;
2899         l->newline = false;
2900 }
2901
2902 static BcStatus bc_lex_next(BcLex *l)
2903 {
2904         BcStatus s;
2905
2906         l->t.last = l->t.t;
2907         if (l->t.last == BC_LEX_EOF) return bc_error("end of file");
2908
2909         l->line += l->newline;
2910         G.err_line = l->line;
2911         l->t.t = BC_LEX_EOF;
2912
2913         l->newline = (l->i == l->len);
2914         if (l->newline) return BC_STATUS_SUCCESS;
2915
2916         // Loop until failure or we don't have whitespace. This
2917         // is so the parser doesn't get inundated with whitespace.
2918         do {
2919                 s = l->next(l);
2920         } while (!s && l->t.t == BC_LEX_WHITESPACE);
2921
2922         return s;
2923 }
2924
2925 static BcStatus bc_lex_text(BcLex *l, const char *text)
2926 {
2927         l->buf = text;
2928         l->i = 0;
2929         l->len = strlen(text);
2930         l->t.t = l->t.last = BC_LEX_INVALID;
2931         return bc_lex_next(l);
2932 }
2933
2934 #if ENABLE_BC
2935 static BcStatus bc_lex_identifier(BcLex *l)
2936 {
2937         BcStatus s;
2938         unsigned i;
2939         const char *buf = l->buf + l->i - 1;
2940
2941         for (i = 0; i < ARRAY_SIZE(bc_lex_kws); ++i) {
2942                 const char *keyword8 = bc_lex_kws[i].name8;
2943                 unsigned j = 0;
2944                 while (buf[j] != '\0' && buf[j] == keyword8[j]) {
2945                         j++;
2946                         if (j == 8) goto match;
2947                 }
2948                 if (keyword8[j] != '\0')
2949                         continue;
2950  match:
2951                 // buf starts with keyword bc_lex_kws[i]
2952                 l->t.t = BC_LEX_KEY_1st_keyword + i;
2953                 if (!((1 << i) & POSIX_KWORD_MASK)) {
2954                         s = bc_posix_error_fmt("%sthe '%.8s' keyword", "POSIX does not allow ", bc_lex_kws[i].name8);
2955                         if (s) return s;
2956                 }
2957
2958                 // We minus 1 because the index has already been incremented.
2959                 l->i += j - 1;
2960                 return BC_STATUS_SUCCESS;
2961         }
2962
2963         s = bc_lex_name(l);
2964         if (s) return s;
2965
2966         if (l->t.v.len > 2) {
2967                 // Prevent this:
2968                 // >>> qwe=1
2969                 // bc: POSIX only allows one character names; the following is bad: 'qwe=1
2970                 // '
2971                 unsigned len = strchrnul(buf, '\n') - buf;
2972                 s = bc_posix_error_fmt("POSIX only allows one character names; the following is bad: '%.*s'", len, buf);
2973         }
2974
2975         return s;
2976 }
2977
2978 static BcStatus bc_lex_string(BcLex *l)
2979 {
2980         size_t len, nls = 0, i = l->i;
2981         char c;
2982
2983         l->t.t = BC_LEX_STR;
2984
2985         for (c = l->buf[i]; c != 0 && c != '"'; c = l->buf[++i]) nls += (c == '\n');
2986
2987         if (c == '\0') {
2988                 l->i = i;
2989                 return bc_error("string end could not be found");
2990         }
2991
2992         len = i - l->i;
2993         if (len > BC_MAX_STRING)
2994                 return bc_error("string too long: must be [1, BC_STRING_MAX]");
2995         bc_vec_string(&l->t.v, len, l->buf + l->i);
2996
2997         l->i = i + 1;
2998         l->line += nls;
2999         G.err_line = l->line;
3000
3001         return BC_STATUS_SUCCESS;
3002 }
3003
3004 static void bc_lex_assign(BcLex *l, BcLexType with, BcLexType without)
3005 {
3006         if (l->buf[l->i] == '=') {
3007                 ++l->i;
3008                 l->t.t = with;
3009         }
3010         else
3011                 l->t.t = without;
3012 }
3013
3014 static BcStatus bc_lex_comment(BcLex *l)
3015 {
3016         size_t i, nls = 0;
3017         const char *buf = l->buf;
3018
3019         l->t.t = BC_LEX_WHITESPACE;
3020         i = ++l->i;
3021         for (;;) {
3022                 char c = buf[i];
3023  check_star:
3024                 if (c == '*') {
3025                         c = buf[++i];
3026                         if (c == '/')
3027                                 break;
3028                         goto check_star;
3029                 }
3030                 if (c == '\0') {
3031                         l->i = i;
3032                         return bc_error("comment end could not be found");
3033                 }
3034                 nls += (c == '\n');
3035                 i++;
3036         }
3037
3038         l->i = i + 1;
3039         l->line += nls;
3040         G.err_line = l->line;
3041
3042         return BC_STATUS_SUCCESS;
3043 }
3044
3045 static BcStatus bc_lex_token(BcLex *l)
3046 {
3047         BcStatus s = BC_STATUS_SUCCESS;
3048         char c = l->buf[l->i++], c2;
3049
3050         // This is the workhorse of the lexer.
3051         switch (c) {
3052
3053                 case '\0':
3054                 case '\n':
3055                 {
3056                         l->newline = true;
3057                         l->t.t = !c ? BC_LEX_EOF : BC_LEX_NLINE;
3058                         break;
3059                 }
3060
3061                 case '\t':
3062                 case '\v':
3063                 case '\f':
3064                 case '\r':
3065                 case ' ':
3066                 {
3067                         bc_lex_whitespace(l);
3068                         break;
3069                 }
3070
3071                 case '!':
3072                 {
3073                         bc_lex_assign(l, BC_LEX_OP_REL_NE, BC_LEX_OP_BOOL_NOT);
3074
3075                         if (l->t.t == BC_LEX_OP_BOOL_NOT) {
3076                                 s = bc_POSIX_does_not_allow_bool_ops_this_is_bad("!");
3077                                 if (s) return s;
3078                         }
3079
3080                         break;
3081                 }
3082
3083                 case '"':
3084                 {
3085                         s = bc_lex_string(l);
3086                         break;
3087                 }
3088
3089                 case '#':
3090                 {
3091                         s = bc_POSIX_does_not_allow("'#' script comments");
3092                         if (s) return s;
3093
3094                         bc_lex_lineComment(l);
3095
3096                         break;
3097                 }
3098
3099                 case '%':
3100                 {
3101                         bc_lex_assign(l, BC_LEX_OP_ASSIGN_MODULUS, BC_LEX_OP_MODULUS);
3102                         break;
3103                 }
3104
3105                 case '&':
3106                 {
3107                         c2 = l->buf[l->i];
3108                         if (c2 == '&') {
3109
3110                                 s = bc_POSIX_does_not_allow_bool_ops_this_is_bad("&&");
3111                                 if (s) return s;
3112
3113                                 ++l->i;
3114                                 l->t.t = BC_LEX_OP_BOOL_AND;
3115                         }
3116                         else {
3117                                 l->t.t = BC_LEX_INVALID;
3118                                 s = bc_error_bad_character('&');
3119                         }
3120
3121                         break;
3122                 }
3123
3124                 case '(':
3125                 case ')':
3126                 {
3127                         l->t.t = (BcLexType)(c - '(' + BC_LEX_LPAREN);
3128                         break;
3129                 }
3130
3131                 case '*':
3132                 {
3133                         bc_lex_assign(l, BC_LEX_OP_ASSIGN_MULTIPLY, BC_LEX_OP_MULTIPLY);
3134                         break;
3135                 }
3136
3137                 case '+':
3138                 {
3139                         c2 = l->buf[l->i];
3140                         if (c2 == '+') {
3141                                 ++l->i;
3142                                 l->t.t = BC_LEX_OP_INC;
3143                         }
3144                         else
3145                                 bc_lex_assign(l, BC_LEX_OP_ASSIGN_PLUS, BC_LEX_OP_PLUS);
3146                         break;
3147                 }
3148
3149                 case ',':
3150                 {
3151                         l->t.t = BC_LEX_COMMA;
3152                         break;
3153                 }
3154
3155                 case '-':
3156                 {
3157                         c2 = l->buf[l->i];
3158                         if (c2 == '-') {
3159                                 ++l->i;
3160                                 l->t.t = BC_LEX_OP_DEC;
3161                         }
3162                         else
3163                                 bc_lex_assign(l, BC_LEX_OP_ASSIGN_MINUS, BC_LEX_OP_MINUS);
3164                         break;
3165                 }
3166
3167                 case '.':
3168                 {
3169                         if (isdigit(l->buf[l->i]))
3170                                 s = bc_lex_number(l, c);
3171                         else {
3172                                 l->t.t = BC_LEX_KEY_LAST;
3173                                 s = bc_POSIX_does_not_allow("a period ('.') as a shortcut for the last result");
3174                         }
3175                         break;
3176                 }
3177
3178                 case '/':
3179                 {
3180                         c2 = l->buf[l->i];
3181                         if (c2 == '*')
3182                                 s = bc_lex_comment(l);
3183                         else
3184                                 bc_lex_assign(l, BC_LEX_OP_ASSIGN_DIVIDE, BC_LEX_OP_DIVIDE);
3185                         break;
3186                 }
3187
3188                 case '0':
3189                 case '1':
3190                 case '2':
3191                 case '3':
3192                 case '4':
3193                 case '5':
3194                 case '6':
3195                 case '7':
3196                 case '8':
3197                 case '9':
3198                 case 'A':
3199                 case 'B':
3200                 case 'C':
3201                 case 'D':
3202                 case 'E':
3203                 case 'F':
3204                 {
3205                         s = bc_lex_number(l, c);
3206                         break;
3207                 }
3208
3209                 case ';':
3210                 {
3211                         l->t.t = BC_LEX_SCOLON;
3212                         break;
3213                 }
3214
3215                 case '<':
3216                 {
3217                         bc_lex_assign(l, BC_LEX_OP_REL_LE, BC_LEX_OP_REL_LT);
3218                         break;
3219                 }
3220
3221                 case '=':
3222                 {
3223                         bc_lex_assign(l, BC_LEX_OP_REL_EQ, BC_LEX_OP_ASSIGN);
3224                         break;
3225                 }
3226
3227                 case '>':
3228                 {
3229                         bc_lex_assign(l, BC_LEX_OP_REL_GE, BC_LEX_OP_REL_GT);
3230                         break;
3231                 }
3232
3233                 case '[':
3234                 case ']':
3235                 {
3236                         l->t.t = (BcLexType)(c - '[' + BC_LEX_LBRACKET);
3237                         break;
3238                 }
3239
3240                 case '\\':
3241                 {
3242                         if (l->buf[l->i] == '\n') {
3243                                 l->t.t = BC_LEX_WHITESPACE;
3244                                 ++l->i;
3245                         }
3246                         else
3247                                 s = bc_error_bad_character(c);
3248                         break;
3249                 }
3250
3251                 case '^':
3252                 {
3253                         bc_lex_assign(l, BC_LEX_OP_ASSIGN_POWER, BC_LEX_OP_POWER);
3254                         break;
3255                 }
3256
3257                 case 'a':
3258                 case 'b':
3259                 case 'c':
3260                 case 'd':
3261                 case 'e':
3262                 case 'f':
3263                 case 'g':
3264                 case 'h':
3265                 case 'i':
3266                 case 'j':
3267                 case 'k':
3268                 case 'l':
3269                 case 'm':
3270                 case 'n':
3271                 case 'o':
3272                 case 'p':
3273                 case 'q':
3274                 case 'r':
3275                 case 's':
3276                 case 't':
3277                 case 'u':
3278                 case 'v':
3279                 case 'w':
3280                 case 'x':
3281                 case 'y':
3282                 case 'z':
3283                 {
3284                         s = bc_lex_identifier(l);
3285                         break;
3286                 }
3287
3288                 case '{':
3289                 case '}':
3290                 {
3291                         l->t.t = (BcLexType)(c - '{' + BC_LEX_LBRACE);
3292                         break;
3293                 }
3294
3295                 case '|':
3296                 {
3297                         c2 = l->buf[l->i];
3298
3299                         if (c2 == '|') {
3300                                 s = bc_POSIX_does_not_allow_bool_ops_this_is_bad("||");
3301                                 if (s) return s;
3302
3303                                 ++l->i;
3304                                 l->t.t = BC_LEX_OP_BOOL_OR;
3305                         }
3306                         else {
3307                                 l->t.t = BC_LEX_INVALID;
3308                                 s = bc_error_bad_character(c);
3309                         }
3310
3311                         break;
3312                 }
3313
3314                 default:
3315                 {
3316                         l->t.t = BC_LEX_INVALID;
3317                         s = bc_error_bad_character(c);
3318                         break;
3319                 }
3320         }
3321
3322         return s;
3323 }
3324 #endif // ENABLE_BC
3325
3326 #if ENABLE_DC
3327 static BcStatus dc_lex_register(BcLex *l)
3328 {
3329         BcStatus s = BC_STATUS_SUCCESS;
3330
3331         if (isspace(l->buf[l->i - 1])) {
3332                 bc_lex_whitespace(l);
3333                 ++l->i;
3334                 if (!G_exreg)
3335                         s = bc_error("extended register");
3336                 else
3337                         s = bc_lex_name(l);
3338         }
3339         else {
3340                 bc_vec_pop_all(&l->t.v);
3341                 bc_vec_pushByte(&l->t.v, l->buf[l->i - 1]);
3342                 bc_vec_pushZeroByte(&l->t.v);
3343                 l->t.t = BC_LEX_NAME;
3344         }
3345
3346         return s;
3347 }
3348
3349 static BcStatus dc_lex_string(BcLex *l)
3350 {
3351         size_t depth = 1, nls = 0, i = l->i;
3352         char c;
3353
3354         l->t.t = BC_LEX_STR;
3355         bc_vec_pop_all(&l->t.v);
3356
3357         for (c = l->buf[i]; c != 0 && depth; c = l->buf[++i]) {
3358
3359                 depth += (c == '[' && (i == l->i || l->buf[i - 1] != '\\'));
3360                 depth -= (c == ']' && (i == l->i || l->buf[i - 1] != '\\'));
3361                 nls += (c == '\n');
3362
3363                 if (depth) bc_vec_push(&l->t.v, &c);
3364         }
3365
3366         if (c == '\0') {
3367                 l->i = i;
3368                 return bc_error("string end could not be found");
3369         }
3370
3371         bc_vec_pushZeroByte(&l->t.v);
3372         if (i - l->i > BC_MAX_STRING)
3373                 return bc_error("string too long: must be [1, BC_STRING_MAX]");
3374
3375         l->i = i;
3376         l->line += nls;
3377         G.err_line = l->line;
3378
3379         return BC_STATUS_SUCCESS;
3380 }
3381
3382 static BcStatus dc_lex_token(BcLex *l)
3383 {
3384         BcStatus s = BC_STATUS_SUCCESS;
3385         char c = l->buf[l->i++], c2;
3386         size_t i;
3387
3388         for (i = 0; i < ARRAY_SIZE(dc_lex_regs); ++i) {
3389                 if (l->t.last == dc_lex_regs[i])
3390                         return dc_lex_register(l);
3391         }
3392
3393         if (c >= '%' && c <= '~' &&
3394             (l->t.t = dc_lex_tokens[(c - '%')]) != BC_LEX_INVALID)
3395         {
3396                 return s;
3397         }
3398
3399         // This is the workhorse of the lexer.
3400         switch (c) {
3401
3402                 case '\0':
3403                 {
3404                         l->t.t = BC_LEX_EOF;
3405                         break;
3406                 }
3407
3408                 case '\n':
3409                 case '\t':
3410                 case '\v':
3411                 case '\f':
3412                 case '\r':
3413                 case ' ':
3414                 {
3415                         l->newline = (c == '\n');
3416                         bc_lex_whitespace(l);
3417                         break;
3418                 }
3419
3420                 case '!':
3421                 {
3422                         c2 = l->buf[l->i];
3423
3424                         if (c2 == '=')
3425                                 l->t.t = BC_LEX_OP_REL_NE;
3426                         else if (c2 == '<')
3427                                 l->t.t = BC_LEX_OP_REL_LE;
3428                         else if (c2 == '>')
3429                                 l->t.t = BC_LEX_OP_REL_GE;
3430                         else
3431                                 return bc_error_bad_character(c);
3432
3433                         ++l->i;
3434                         break;
3435                 }
3436
3437                 case '#':
3438                 {
3439                         bc_lex_lineComment(l);
3440                         break;
3441                 }
3442
3443                 case '.':
3444                 {
3445                         if (isdigit(l->buf[l->i]))
3446                                 s = bc_lex_number(l, c);
3447                         else
3448                                 s = bc_error_bad_character(c);
3449                         break;
3450                 }
3451
3452                 case '0':
3453                 case '1':
3454                 case '2':
3455                 case '3':
3456                 case '4':
3457                 case '5':
3458                 case '6':
3459                 case '7':
3460                 case '8':
3461                 case '9':
3462                 case 'A':
3463                 case 'B':
3464                 case 'C':
3465                 case 'D':
3466                 case 'E':
3467                 case 'F':
3468                 {
3469                         s = bc_lex_number(l, c);
3470                         break;
3471                 }
3472
3473                 case '[':
3474                 {
3475                         s = dc_lex_string(l);
3476                         break;
3477                 }
3478
3479                 default:
3480                 {
3481                         l->t.t = BC_LEX_INVALID;
3482                         s = bc_error_bad_character(c);
3483                         break;
3484                 }
3485         }
3486
3487         return s;
3488 }
3489 #endif // ENABLE_DC
3490
3491 static void bc_parse_addFunc(BcParse *p, char *name, size_t *idx)
3492 {
3493         bc_program_addFunc(name, idx);
3494         p->func = bc_vec_item(&G.prog.fns, p->fidx);
3495 }
3496
3497 static void bc_parse_pushName(BcParse *p, char *name)
3498 {
3499         size_t i = 0, len = strlen(name);
3500
3501         for (; i < len; ++i) bc_parse_push(p, name[i]);
3502         bc_parse_push(p, BC_PARSE_STREND);
3503
3504         free(name);
3505 }
3506
3507 static void bc_parse_pushIndex(BcParse *p, size_t idx)
3508 {
3509         unsigned char amt, i, nums[sizeof(size_t)];
3510
3511         for (amt = 0; idx; ++amt) {
3512                 nums[amt] = (char) idx;
3513                 idx = (idx & ((unsigned long) ~(UCHAR_MAX))) >> sizeof(char) * CHAR_BIT;
3514         }
3515
3516         bc_parse_push(p, amt);
3517         for (i = 0; i < amt; ++i) bc_parse_push(p, nums[i]);
3518 }
3519
3520 static void bc_parse_number(BcParse *p, BcInst *prev, size_t *nexs)
3521 {
3522         char *num = xstrdup(p->l.t.v.v);
3523         size_t idx = G.prog.consts.len;
3524
3525         bc_vec_push(&G.prog.consts, &num);
3526
3527         bc_parse_push(p, BC_INST_NUM);
3528         bc_parse_pushIndex(p, idx);
3529
3530         ++(*nexs);
3531         (*prev) = BC_INST_NUM;
3532 }
3533
3534 static BcStatus bc_parse_text(BcParse *p, const char *text)
3535 {
3536         BcStatus s;
3537
3538         p->func = bc_vec_item(&G.prog.fns, p->fidx);
3539
3540         if (!text[0] && !BC_PARSE_CAN_EXEC(p)) {
3541                 p->l.t.t = BC_LEX_INVALID;
3542                 s = p->parse(p);
3543                 if (s) return s;
3544                 if (!BC_PARSE_CAN_EXEC(p))
3545                         return bc_error("file is not executable");
3546         }
3547
3548         return bc_lex_text(&p->l, text);
3549 }
3550
3551 // Called when bc/dc_parse_parse() detects a failure,
3552 // resets parsing structures.
3553 static void bc_parse_reset(BcParse *p)
3554 {
3555         if (p->fidx != BC_PROG_MAIN) {
3556                 p->func->nparams = 0;
3557                 bc_vec_pop_all(&p->func->code);
3558                 bc_vec_pop_all(&p->func->autos);
3559                 bc_vec_pop_all(&p->func->labels);
3560
3561                 bc_parse_updateFunc(p, BC_PROG_MAIN);
3562         }
3563
3564         p->l.i = p->l.len;
3565         p->l.t.t = BC_LEX_EOF;
3566         p->auto_part = (p->nbraces = 0);
3567
3568         bc_vec_npop(&p->flags, p->flags.len - 1);
3569         bc_vec_pop_all(&p->exits);
3570         bc_vec_pop_all(&p->conds);
3571         bc_vec_pop_all(&p->ops);
3572
3573         bc_program_reset();
3574 }
3575
3576 static void bc_parse_free(BcParse *p)
3577 {
3578         bc_vec_free(&p->flags);
3579         bc_vec_free(&p->exits);
3580         bc_vec_free(&p->conds);
3581         bc_vec_free(&p->ops);
3582         bc_lex_free(&p->l);
3583 }
3584
3585 static void bc_parse_create(BcParse *p, size_t func,
3586                             BcParseParse parse, BcLexNext next)
3587 {
3588         memset(p, 0, sizeof(BcParse));
3589
3590         bc_lex_init(&p->l, next);
3591         bc_vec_init(&p->flags, sizeof(uint8_t), NULL);
3592         bc_vec_init(&p->exits, sizeof(BcInstPtr), NULL);
3593         bc_vec_init(&p->conds, sizeof(size_t), NULL);
3594         bc_vec_pushZeroByte(&p->flags);
3595         bc_vec_init(&p->ops, sizeof(BcLexType), NULL);
3596
3597         p->parse = parse;
3598         // p->auto_part = p->nbraces = 0; - already is
3599         bc_parse_updateFunc(p, func);
3600 }
3601
3602 #if ENABLE_BC
3603 static BcStatus bc_parse_else(BcParse *p);
3604 static BcStatus bc_parse_stmt(BcParse *p);
3605
3606 static BcStatus bc_parse_operator(BcParse *p, BcLexType type, size_t start,
3607                                   size_t *nexprs, bool next)
3608 {
3609         BcStatus s = BC_STATUS_SUCCESS;
3610         BcLexType t;
3611         char l, r = bc_parse_ops[type - BC_LEX_OP_INC].prec;
3612         bool left = bc_parse_ops[type - BC_LEX_OP_INC].left;
3613
3614         while (p->ops.len > start) {
3615
3616                 t = BC_PARSE_TOP_OP(p);
3617                 if (t == BC_LEX_LPAREN) break;
3618
3619                 l = bc_parse_ops[t - BC_LEX_OP_INC].prec;
3620                 if (l >= r && (l != r || !left)) break;
3621
3622                 bc_parse_push(p, BC_PARSE_TOKEN_INST(t));
3623                 bc_vec_pop(&p->ops);
3624                 *nexprs -= t != BC_LEX_OP_BOOL_NOT && t != BC_LEX_NEG;
3625         }
3626
3627         bc_vec_push(&p->ops, &type);
3628         if (next) s = bc_lex_next(&p->l);
3629
3630         return s;
3631 }
3632
3633 static BcStatus bc_parse_rightParen(BcParse *p, size_t ops_bgn, size_t *nexs)
3634 {
3635         BcLexType top;
3636
3637         if (p->ops.len <= ops_bgn)
3638                 return bc_error_bad_expression();
3639         top = BC_PARSE_TOP_OP(p);
3640
3641         while (top != BC_LEX_LPAREN) {
3642
3643                 bc_parse_push(p, BC_PARSE_TOKEN_INST(top));
3644
3645                 bc_vec_pop(&p->ops);
3646                 *nexs -= top != BC_LEX_OP_BOOL_NOT && top != BC_LEX_NEG;
3647
3648                 if (p->ops.len <= ops_bgn)
3649                         return bc_error_bad_expression();
3650                 top = BC_PARSE_TOP_OP(p);
3651         }
3652
3653         bc_vec_pop(&p->ops);
3654
3655         return bc_lex_next(&p->l);
3656 }
3657
3658 static BcStatus bc_parse_params(BcParse *p, uint8_t flags)
3659 {
3660         BcStatus s;
3661         bool comma = false;
3662         size_t nparams;
3663
3664         s = bc_lex_next(&p->l);
3665         if (s) return s;
3666
3667         for (nparams = 0; p->l.t.t != BC_LEX_RPAREN; ++nparams) {
3668
3669                 flags = (flags & ~(BC_PARSE_PRINT | BC_PARSE_REL)) | BC_PARSE_ARRAY;
3670                 s = bc_parse_expr(p, flags, bc_parse_next_param);
3671                 if (s) return s;
3672
3673                 comma = p->l.t.t == BC_LEX_COMMA;
3674                 if (comma) {
3675                         s = bc_lex_next(&p->l);
3676                         if (s) return s;
3677                 }
3678         }
3679
3680         if (comma) return bc_error_bad_token();
3681         bc_parse_push(p, BC_INST_CALL);
3682         bc_parse_pushIndex(p, nparams);
3683
3684         return BC_STATUS_SUCCESS;
3685 }
3686
3687 static BcStatus bc_parse_call(BcParse *p, char *name, uint8_t flags)
3688 {
3689         BcStatus s;
3690         BcId entry, *entry_ptr;
3691         size_t idx;
3692
3693         entry.name = name;
3694
3695         s = bc_parse_params(p, flags);
3696         if (s) goto err;
3697
3698         if (p->l.t.t != BC_LEX_RPAREN) {
3699                 s = bc_error_bad_token();
3700                 goto err;
3701         }
3702
3703         idx = bc_map_index(&G.prog.fn_map, &entry);
3704
3705         if (idx == BC_VEC_INVALID_IDX) {
3706                 name = xstrdup(entry.name);
3707                 bc_parse_addFunc(p, name, &idx);
3708                 idx = bc_map_index(&G.prog.fn_map, &entry);
3709                 free(entry.name);
3710         }
3711         else
3712                 free(name);
3713
3714         entry_ptr = bc_vec_item(&G.prog.fn_map, idx);
3715         bc_parse_pushIndex(p, entry_ptr->idx);
3716
3717         return bc_lex_next(&p->l);
3718
3719 err:
3720         free(name);
3721         return s;
3722 }
3723
3724 static BcStatus bc_parse_name(BcParse *p, BcInst *type, uint8_t flags)
3725 {
3726         BcStatus s;
3727         char *name;
3728
3729         name = xstrdup(p->l.t.v.v);
3730         s = bc_lex_next(&p->l);
3731         if (s) goto err;
3732
3733         if (p->l.t.t == BC_LEX_LBRACKET) {
3734
3735                 s = bc_lex_next(&p->l);
3736                 if (s) goto err;
3737
3738                 if (p->l.t.t == BC_LEX_RBRACKET) {
3739
3740                         if (!(flags & BC_PARSE_ARRAY)) {
3741                                 s = bc_error_bad_expression();
3742                                 goto err;
3743                         }
3744
3745                         *type = BC_INST_ARRAY;
3746                 }
3747                 else {
3748
3749                         *type = BC_INST_ARRAY_ELEM;
3750
3751                         flags &= ~(BC_PARSE_PRINT | BC_PARSE_REL);
3752                         s = bc_parse_expr(p, flags, bc_parse_next_elem);
3753                         if (s) goto err;
3754                 }
3755
3756                 s = bc_lex_next(&p->l);
3757                 if (s) goto err;
3758                 bc_parse_push(p, *type);
3759                 bc_parse_pushName(p, name);
3760         }
3761         else if (p->l.t.t == BC_LEX_LPAREN) {
3762
3763                 if (flags & BC_PARSE_NOCALL) {
3764                         s = bc_error_bad_token();
3765                         goto err;
3766                 }
3767
3768                 *type = BC_INST_CALL;
3769                 s = bc_parse_call(p, name, flags);
3770         }
3771         else {
3772                 *type = BC_INST_VAR;
3773                 bc_parse_push(p, BC_INST_VAR);
3774                 bc_parse_pushName(p, name);
3775         }
3776
3777         return s;
3778
3779 err:
3780         free(name);
3781         return s;
3782 }
3783
3784 static BcStatus bc_parse_read(BcParse *p)
3785 {
3786         BcStatus s;
3787
3788         s = bc_lex_next(&p->l);
3789         if (s) return s;
3790         if (p->l.t.t != BC_LEX_LPAREN) return bc_error_bad_token();
3791
3792         s = bc_lex_next(&p->l);
3793         if (s) return s;
3794         if (p->l.t.t != BC_LEX_RPAREN) return bc_error_bad_token();
3795
3796         bc_parse_push(p, BC_INST_READ);
3797
3798         return bc_lex_next(&p->l);
3799 }
3800
3801 static BcStatus bc_parse_builtin(BcParse *p, BcLexType type, uint8_t flags,
3802                                  BcInst *prev)
3803 {
3804         BcStatus s;
3805
3806         s = bc_lex_next(&p->l);
3807         if (s) return s;
3808         if (p->l.t.t != BC_LEX_LPAREN) return bc_error_bad_token();
3809
3810         flags = (flags & ~(BC_PARSE_PRINT | BC_PARSE_REL)) | BC_PARSE_ARRAY;
3811
3812         s = bc_lex_next(&p->l);
3813         if (s) return s;
3814
3815         s = bc_parse_expr(p, flags, bc_parse_next_rel);
3816         if (s) return s;
3817
3818         if (p->l.t.t != BC_LEX_RPAREN) return bc_error_bad_token();
3819
3820         *prev = (type == BC_LEX_KEY_LENGTH) ? BC_INST_LENGTH : BC_INST_SQRT;
3821         bc_parse_push(p, *prev);
3822
3823         return bc_lex_next(&p->l);
3824 }
3825
3826 static BcStatus bc_parse_scale(BcParse *p, BcInst *type, uint8_t flags)
3827 {
3828         BcStatus s;
3829
3830         s = bc_lex_next(&p->l);
3831         if (s) return s;
3832
3833         if (p->l.t.t != BC_LEX_LPAREN) {
3834                 *type = BC_INST_SCALE;
3835                 bc_parse_push(p, BC_INST_SCALE);
3836                 return BC_STATUS_SUCCESS;
3837         }
3838
3839         *type = BC_INST_SCALE_FUNC;
3840         flags &= ~(BC_PARSE_PRINT | BC_PARSE_REL);
3841
3842         s = bc_lex_next(&p->l);
3843         if (s) return s;
3844
3845         s = bc_parse_expr(p, flags, bc_parse_next_rel);
3846         if (s) return s;
3847         if (p->l.t.t != BC_LEX_RPAREN) return bc_error_bad_token();
3848         bc_parse_push(p, BC_INST_SCALE_FUNC);
3849
3850         return bc_lex_next(&p->l);
3851 }
3852
3853 static BcStatus bc_parse_incdec(BcParse *p, BcInst *prev, bool *paren_expr,
3854                                 size_t *nexprs, uint8_t flags)
3855 {
3856         BcStatus s;
3857         BcLexType type;
3858         char inst;
3859         BcInst etype = *prev;
3860
3861         if (etype == BC_INST_VAR || etype == BC_INST_ARRAY_ELEM ||
3862             etype == BC_INST_SCALE || etype == BC_INST_LAST ||
3863             etype == BC_INST_IBASE || etype == BC_INST_OBASE)
3864         {
3865                 *prev = inst = BC_INST_INC_POST + (p->l.t.t != BC_LEX_OP_INC);
3866                 bc_parse_push(p, inst);
3867                 s = bc_lex_next(&p->l);
3868         }
3869         else {
3870
3871                 *prev = inst = BC_INST_INC_PRE + (p->l.t.t != BC_LEX_OP_INC);
3872                 *paren_expr = true;
3873
3874                 s = bc_lex_next(&p->l);
3875                 if (s) return s;
3876                 type = p->l.t.t;
3877
3878                 // Because we parse the next part of the expression
3879                 // right here, we need to increment this.
3880                 *nexprs = *nexprs + 1;
3881
3882                 switch (type) {
3883
3884                         case BC_LEX_NAME:
3885                         {
3886                                 s = bc_parse_name(p, prev, flags | BC_PARSE_NOCALL);
3887                                 break;
3888                         }
3889
3890                         case BC_LEX_KEY_IBASE:
3891                         case BC_LEX_KEY_LAST:
3892                         case BC_LEX_KEY_OBASE:
3893                         {
3894                                 bc_parse_push(p, type - BC_LEX_KEY_IBASE + BC_INST_IBASE);
3895                                 s = bc_lex_next(&p->l);
3896                                 break;
3897                         }
3898
3899                         case BC_LEX_KEY_SCALE:
3900                         {
3901                                 s = bc_lex_next(&p->l);
3902                                 if (s) return s;
3903                                 if (p->l.t.t == BC_LEX_LPAREN)
3904                                         s = bc_error_bad_token();
3905                                 else
3906                                         bc_parse_push(p, BC_INST_SCALE);
3907                                 break;
3908                         }
3909
3910                         default:
3911                         {
3912                                 s = bc_error_bad_token();
3913                                 break;
3914                         }
3915                 }
3916
3917                 if (!s) bc_parse_push(p, inst);
3918         }
3919
3920         return s;
3921 }
3922
3923 static BcStatus bc_parse_minus(BcParse *p, BcInst *prev, size_t ops_bgn,
3924                                bool rparen, size_t *nexprs)
3925 {
3926         BcStatus s;
3927         BcLexType type;
3928         BcInst etype = *prev;
3929
3930         s = bc_lex_next(&p->l);
3931         if (s) return s;
3932
3933         type = rparen || etype == BC_INST_INC_POST || etype == BC_INST_DEC_POST ||
3934                        (etype >= BC_INST_NUM && etype <= BC_INST_SQRT) ?
3935                    BC_LEX_OP_MINUS :
3936                    BC_LEX_NEG;
3937         *prev = BC_PARSE_TOKEN_INST(type);
3938
3939         // We can just push onto the op stack because this is the largest
3940         // precedence operator that gets pushed. Inc/dec does not.
3941         if (type != BC_LEX_OP_MINUS)
3942                 bc_vec_push(&p->ops, &type);
3943         else
3944                 s = bc_parse_operator(p, type, ops_bgn, nexprs, false);
3945
3946         return s;
3947 }
3948
3949 static BcStatus bc_parse_string(BcParse *p, char inst)
3950 {
3951         char *str = xstrdup(p->l.t.v.v);
3952
3953         bc_parse_push(p, BC_INST_STR);
3954         bc_parse_pushIndex(p, G.prog.strs.len);
3955         bc_vec_push(&G.prog.strs, &str);
3956         bc_parse_push(p, inst);
3957
3958         return bc_lex_next(&p->l);
3959 }
3960
3961 static BcStatus bc_parse_print(BcParse *p)
3962 {
3963         BcStatus s;
3964         BcLexType type;
3965         bool comma = false;
3966
3967         s = bc_lex_next(&p->l);
3968         if (s) return s;
3969
3970         type = p->l.t.t;
3971
3972         if (type == BC_LEX_SCOLON || type == BC_LEX_NLINE)
3973                 return bc_error("bad print statement");
3974
3975         while (!s && type != BC_LEX_SCOLON && type != BC_LEX_NLINE) {
3976
3977                 if (type == BC_LEX_STR)
3978                         s = bc_parse_string(p, BC_INST_PRINT_POP);
3979                 else {
3980                         s = bc_parse_expr(p, 0, bc_parse_next_print);
3981                         if (s) return s;
3982                         bc_parse_push(p, BC_INST_PRINT_POP);
3983                 }
3984
3985                 if (s) return s;
3986
3987                 comma = p->l.t.t == BC_LEX_COMMA;
3988                 if (comma) s = bc_lex_next(&p->l);
3989                 type = p->l.t.t;
3990         }
3991
3992         if (s) return s;
3993         if (comma) return bc_error_bad_token();
3994
3995         return bc_lex_next(&p->l);
3996 }
3997
3998 static BcStatus bc_parse_return(BcParse *p)
3999 {
4000         BcStatus s;
4001         BcLexType t;
4002         bool paren;
4003
4004         if (!BC_PARSE_FUNC(p)) return bc_error_bad_token();
4005
4006         s = bc_lex_next(&p->l);
4007         if (s) return s;
4008
4009         t = p->l.t.t;
4010         paren = t == BC_LEX_LPAREN;
4011
4012         if (t == BC_LEX_NLINE || t == BC_LEX_SCOLON)
4013                 bc_parse_push(p, BC_INST_RET0);
4014         else {
4015
4016                 s = bc_parse_expr(p, 0, bc_parse_next_expr);
4017                 if (s && s != BC_STATUS_PARSE_EMPTY_EXP)
4018                         return s;
4019
4020                 if (s == BC_STATUS_PARSE_EMPTY_EXP) {
4021                         bc_parse_push(p, BC_INST_RET0);
4022                         s = bc_lex_next(&p->l);
4023                         if (s) return s;
4024                 }
4025
4026                 if (!paren || p->l.t.last != BC_LEX_RPAREN) {
4027                         s = bc_posix_error("POSIX requires parentheses around return expressions");
4028                         if (s) return s;
4029                 }
4030
4031                 bc_parse_push(p, BC_INST_RET);
4032         }
4033
4034         return s;
4035 }
4036
4037 static BcStatus bc_parse_endBody(BcParse *p, bool brace)
4038 {
4039         BcStatus s = BC_STATUS_SUCCESS;
4040
4041         if (p->flags.len <= 1 || (brace && p->nbraces == 0))
4042                 return bc_error_bad_token();
4043
4044         if (brace) {
4045
4046                 if (p->l.t.t == BC_LEX_RBRACE) {
4047                         if (!p->nbraces) return bc_error_bad_token();
4048                         --p->nbraces;
4049                         s = bc_lex_next(&p->l);
4050                         if (s) return s;
4051                 }
4052                 else
4053                         return bc_error_bad_token();
4054         }
4055
4056         if (BC_PARSE_IF(p)) {
4057
4058                 uint8_t *flag_ptr;
4059
4060                 while (p->l.t.t == BC_LEX_NLINE) {
4061                         s = bc_lex_next(&p->l);
4062                         if (s) return s;
4063                 }
4064
4065                 bc_vec_pop(&p->flags);
4066
4067                 flag_ptr = BC_PARSE_TOP_FLAG_PTR(p);
4068                 *flag_ptr = (*flag_ptr | BC_PARSE_FLAG_IF_END);
4069
4070                 if (p->l.t.t == BC_LEX_KEY_ELSE) s = bc_parse_else(p);
4071         }
4072         else if (BC_PARSE_ELSE(p)) {
4073
4074                 BcInstPtr *ip;
4075                 size_t *label;
4076
4077                 bc_vec_pop(&p->flags);
4078
4079                 ip = bc_vec_top(&p->exits);
4080                 label = bc_vec_item(&p->func->labels, ip->idx);
4081                 *label = p->func->code.len;
4082
4083                 bc_vec_pop(&p->exits);
4084         }
4085         else if (BC_PARSE_FUNC_INNER(p)) {
4086                 bc_parse_push(p, BC_INST_RET0);
4087                 bc_parse_updateFunc(p, BC_PROG_MAIN);
4088                 bc_vec_pop(&p->flags);
4089         }
4090         else {
4091
4092                 BcInstPtr *ip = bc_vec_top(&p->exits);
4093                 size_t *label = bc_vec_top(&p->conds);
4094
4095                 bc_parse_push(p, BC_INST_JUMP);
4096                 bc_parse_pushIndex(p, *label);
4097
4098                 label = bc_vec_item(&p->func->labels, ip->idx);
4099                 *label = p->func->code.len;
4100
4101                 bc_vec_pop(&p->flags);
4102                 bc_vec_pop(&p->exits);
4103                 bc_vec_pop(&p->conds);
4104         }
4105
4106         return s;
4107 }
4108
4109 static void bc_parse_startBody(BcParse *p, uint8_t flags)
4110 {
4111         uint8_t *flag_ptr = BC_PARSE_TOP_FLAG_PTR(p);
4112         flags |= (*flag_ptr & (BC_PARSE_FLAG_FUNC | BC_PARSE_FLAG_LOOP));
4113         flags |= BC_PARSE_FLAG_BODY;
4114         bc_vec_push(&p->flags, &flags);
4115 }
4116
4117 static void bc_parse_noElse(BcParse *p)
4118 {
4119         BcInstPtr *ip;
4120         size_t *label;
4121         uint8_t *flag_ptr = BC_PARSE_TOP_FLAG_PTR(p);
4122
4123         *flag_ptr = (*flag_ptr & ~(BC_PARSE_FLAG_IF_END));
4124
4125         ip = bc_vec_top(&p->exits);
4126         label = bc_vec_item(&p->func->labels, ip->idx);
4127         *label = p->func->code.len;
4128
4129         bc_vec_pop(&p->exits);
4130 }
4131
4132 static BcStatus bc_parse_if(BcParse *p)
4133 {
4134         BcStatus s;
4135         BcInstPtr ip;
4136
4137         s = bc_lex_next(&p->l);
4138         if (s) return s;
4139         if (p->l.t.t != BC_LEX_LPAREN) return bc_error_bad_token();
4140
4141         s = bc_lex_next(&p->l);
4142         if (s) return s;
4143         s = bc_parse_expr(p, BC_PARSE_REL, bc_parse_next_rel);
4144         if (s) return s;
4145         if (p->l.t.t != BC_LEX_RPAREN) return bc_error_bad_token();
4146
4147         s = bc_lex_next(&p->l);
4148         if (s) return s;
4149         bc_parse_push(p, BC_INST_JUMP_ZERO);
4150
4151         ip.idx = p->func->labels.len;
4152         ip.func = ip.len = 0;
4153
4154         bc_parse_pushIndex(p, ip.idx);
4155         bc_vec_push(&p->exits, &ip);
4156         bc_vec_push(&p->func->labels, &ip.idx);
4157         bc_parse_startBody(p, BC_PARSE_FLAG_IF);
4158
4159         return BC_STATUS_SUCCESS;
4160 }
4161
4162 static BcStatus bc_parse_else(BcParse *p)
4163 {
4164         BcInstPtr ip;
4165
4166         if (!BC_PARSE_IF_END(p)) return bc_error_bad_token();
4167
4168         ip.idx = p->func->labels.len;
4169         ip.func = ip.len = 0;
4170
4171         bc_parse_push(p, BC_INST_JUMP);
4172         bc_parse_pushIndex(p, ip.idx);
4173
4174         bc_parse_noElse(p);
4175
4176         bc_vec_push(&p->exits, &ip);
4177         bc_vec_push(&p->func->labels, &ip.idx);
4178         bc_parse_startBody(p, BC_PARSE_FLAG_ELSE);
4179
4180         return bc_lex_next(&p->l);
4181 }
4182
4183 static BcStatus bc_parse_while(BcParse *p)
4184 {
4185         BcStatus s;
4186         BcInstPtr ip;
4187
4188         s = bc_lex_next(&p->l);
4189         if (s) return s;
4190         if (p->l.t.t != BC_LEX_LPAREN) return bc_error_bad_token();
4191         s = bc_lex_next(&p->l);
4192         if (s) return s;
4193
4194         ip.idx = p->func->labels.len;
4195
4196         bc_vec_push(&p->func->labels, &p->func->code.len);
4197         bc_vec_push(&p->conds, &ip.idx);
4198
4199         ip.idx = p->func->labels.len;
4200         ip.func = 1;
4201         ip.len = 0;
4202
4203         bc_vec_push(&p->exits, &ip);
4204         bc_vec_push(&p->func->labels, &ip.idx);
4205
4206         s = bc_parse_expr(p, BC_PARSE_REL, bc_parse_next_rel);
4207         if (s) return s;
4208         if (p->l.t.t != BC_LEX_RPAREN) return bc_error_bad_token();
4209         s = bc_lex_next(&p->l);
4210         if (s) return s;
4211
4212         bc_parse_push(p, BC_INST_JUMP_ZERO);
4213         bc_parse_pushIndex(p, ip.idx);
4214         bc_parse_startBody(p, BC_PARSE_FLAG_LOOP | BC_PARSE_FLAG_LOOP_INNER);
4215
4216         return BC_STATUS_SUCCESS;
4217 }
4218
4219 static BcStatus bc_parse_for(BcParse *p)
4220 {
4221         BcStatus s;
4222         BcInstPtr ip;
4223         size_t cond_idx, exit_idx, body_idx, update_idx;
4224
4225         s = bc_lex_next(&p->l);
4226         if (s) return s;
4227         if (p->l.t.t != BC_LEX_LPAREN) return bc_error_bad_token();
4228         s = bc_lex_next(&p->l);
4229         if (s) return s;
4230
4231         if (p->l.t.t != BC_LEX_SCOLON)
4232                 s = bc_parse_expr(p, 0, bc_parse_next_for);
4233         else
4234                 s = bc_POSIX_does_not_allow_empty_X_expression_in_for("init");
4235
4236         if (s) return s;
4237         if (p->l.t.t != BC_LEX_SCOLON) return bc_error_bad_token();
4238         s = bc_lex_next(&p->l);
4239         if (s) return s;
4240
4241         cond_idx = p->func->labels.len;
4242         update_idx = cond_idx + 1;
4243         body_idx = update_idx + 1;
4244         exit_idx = body_idx + 1;
4245
4246         bc_vec_push(&p->func->labels, &p->func->code.len);
4247
4248         if (p->l.t.t != BC_LEX_SCOLON)
4249                 s = bc_parse_expr(p, BC_PARSE_REL, bc_parse_next_for);
4250         else
4251                 s = bc_POSIX_does_not_allow_empty_X_expression_in_for("condition");
4252
4253         if (s) return s;
4254         if (p->l.t.t != BC_LEX_SCOLON) return bc_error_bad_token();
4255
4256         s = bc_lex_next(&p->l);
4257         if (s) return s;
4258
4259         bc_parse_push(p, BC_INST_JUMP_ZERO);
4260         bc_parse_pushIndex(p, exit_idx);
4261         bc_parse_push(p, BC_INST_JUMP);
4262         bc_parse_pushIndex(p, body_idx);
4263
4264         ip.idx = p->func->labels.len;
4265
4266         bc_vec_push(&p->conds, &update_idx);
4267         bc_vec_push(&p->func->labels, &p->func->code.len);
4268
4269         if (p->l.t.t != BC_LEX_RPAREN)
4270                 s = bc_parse_expr(p, 0, bc_parse_next_rel);
4271         else
4272                 s = bc_POSIX_does_not_allow_empty_X_expression_in_for("update");
4273
4274         if (s) return s;
4275
4276         if (p->l.t.t != BC_LEX_RPAREN) return bc_error_bad_token();
4277         bc_parse_push(p, BC_INST_JUMP);
4278         bc_parse_pushIndex(p, cond_idx);
4279         bc_vec_push(&p->func->labels, &p->func->code.len);
4280
4281         ip.idx = exit_idx;
4282         ip.func = 1;
4283         ip.len = 0;
4284
4285         bc_vec_push(&p->exits, &ip);
4286         bc_vec_push(&p->func->labels, &ip.idx);
4287         bc_lex_next(&p->l);
4288         bc_parse_startBody(p, BC_PARSE_FLAG_LOOP | BC_PARSE_FLAG_LOOP_INNER);
4289
4290         return BC_STATUS_SUCCESS;
4291 }
4292
4293 static BcStatus bc_parse_loopExit(BcParse *p, BcLexType type)
4294 {
4295         BcStatus s;
4296         size_t i;
4297         BcInstPtr *ip;
4298
4299         if (!BC_PARSE_LOOP(p)) return bc_error_bad_token();
4300
4301         if (type == BC_LEX_KEY_BREAK) {
4302
4303                 if (p->exits.len == 0) return bc_error_bad_token();
4304
4305                 i = p->exits.len - 1;
4306                 ip = bc_vec_item(&p->exits, i);
4307
4308                 while (!ip->func && i < p->exits.len) ip = bc_vec_item(&p->exits, i--);
4309                 if (i >= p->exits.len && !ip->func) return bc_error_bad_token();
4310
4311                 i = ip->idx;
4312         }
4313         else
4314                 i = *((size_t *) bc_vec_top(&p->conds));
4315
4316         bc_parse_push(p, BC_INST_JUMP);
4317         bc_parse_pushIndex(p, i);
4318
4319         s = bc_lex_next(&p->l);
4320         if (s) return s;
4321
4322         if (p->l.t.t != BC_LEX_SCOLON && p->l.t.t != BC_LEX_NLINE)
4323                 return bc_error_bad_token();
4324
4325         return bc_lex_next(&p->l);
4326 }
4327
4328 static BcStatus bc_parse_func(BcParse *p)
4329 {
4330         BcStatus s;
4331         bool var, comma = false;
4332         uint8_t flags;
4333         char *name;
4334
4335         s = bc_lex_next(&p->l);
4336         if (s) return s;
4337         if (p->l.t.t != BC_LEX_NAME)
4338                 return bc_error("bad function definition");
4339
4340         name = xstrdup(p->l.t.v.v);
4341         bc_parse_addFunc(p, name, &p->fidx);
4342
4343         s = bc_lex_next(&p->l);
4344         if (s) return s;
4345         if (p->l.t.t != BC_LEX_LPAREN)
4346                 return bc_error("bad function definition");
4347         s = bc_lex_next(&p->l);
4348         if (s) return s;
4349
4350         while (p->l.t.t != BC_LEX_RPAREN) {
4351
4352                 if (p->l.t.t != BC_LEX_NAME)
4353                         return bc_error("bad function definition");
4354
4355                 ++p->func->nparams;
4356
4357                 name = xstrdup(p->l.t.v.v);
4358                 s = bc_lex_next(&p->l);
4359                 if (s) goto err;
4360
4361                 var = p->l.t.t != BC_LEX_LBRACKET;
4362
4363                 if (!var) {
4364
4365                         s = bc_lex_next(&p->l);
4366                         if (s) goto err;
4367
4368                         if (p->l.t.t != BC_LEX_RBRACKET) {
4369                                 s = bc_error("bad function definition");
4370                                 goto err;
4371                         }
4372
4373                         s = bc_lex_next(&p->l);
4374                         if (s) goto err;
4375                 }
4376
4377                 comma = p->l.t.t == BC_LEX_COMMA;
4378                 if (comma) {
4379                         s = bc_lex_next(&p->l);
4380                         if (s) goto err;
4381                 }
4382
4383                 s = bc_func_insert(p->func, name, var);
4384                 if (s) goto err;
4385         }
4386
4387         if (comma) return bc_error("bad function definition");
4388
4389         flags = BC_PARSE_FLAG_FUNC | BC_PARSE_FLAG_FUNC_INNER | BC_PARSE_FLAG_BODY;
4390         bc_parse_startBody(p, flags);
4391
4392         s = bc_lex_next(&p->l);
4393         if (s) return s;
4394
4395         if (p->l.t.t != BC_LEX_LBRACE)
4396                 s = bc_posix_error("POSIX requires the left brace be on the same line as the function header");
4397
4398         return s;
4399
4400 err:
4401         free(name);
4402         return s;
4403 }
4404
4405 static BcStatus bc_parse_auto(BcParse *p)
4406 {
4407         BcStatus s;
4408         bool comma, var, one;
4409         char *name;
4410
4411         if (!p->auto_part) return bc_error_bad_token();
4412         s = bc_lex_next(&p->l);
4413         if (s) return s;
4414
4415         p->auto_part = comma = false;
4416         one = p->l.t.t == BC_LEX_NAME;
4417
4418         while (p->l.t.t == BC_LEX_NAME) {
4419
4420                 name = xstrdup(p->l.t.v.v);
4421                 s = bc_lex_next(&p->l);
4422                 if (s) goto err;
4423
4424                 var = p->l.t.t != BC_LEX_LBRACKET;
4425                 if (!var) {
4426
4427                         s = bc_lex_next(&p->l);
4428                         if (s) goto err;
4429
4430                         if (p->l.t.t != BC_LEX_RBRACKET) {
4431                                 s = bc_error("bad function definition");
4432                                 goto err;
4433                         }
4434
4435                         s = bc_lex_next(&p->l);
4436                         if (s) goto err;
4437                 }
4438
4439                 comma = p->l.t.t == BC_LEX_COMMA;
4440                 if (comma) {
4441                         s = bc_lex_next(&p->l);
4442                         if (s) goto err;
4443                 }
4444
4445                 s = bc_func_insert(p->func, name, var);
4446                 if (s) goto err;
4447         }
4448
4449         if (comma) return bc_error("bad function definition");
4450         if (!one) return bc_error("no auto variable found");
4451
4452         if (p->l.t.t != BC_LEX_NLINE && p->l.t.t != BC_LEX_SCOLON)
4453                 return bc_error_bad_token();
4454
4455         return bc_lex_next(&p->l);
4456
4457 err:
4458         free(name);
4459         return s;
4460 }
4461
4462 static BcStatus bc_parse_body(BcParse *p, bool brace)
4463 {
4464         BcStatus s = BC_STATUS_SUCCESS;
4465         uint8_t *flag_ptr = bc_vec_top(&p->flags);
4466
4467         *flag_ptr &= ~(BC_PARSE_FLAG_BODY);
4468
4469         if (*flag_ptr & BC_PARSE_FLAG_FUNC_INNER) {
4470
4471                 if (!brace) return bc_error_bad_token();
4472                 p->auto_part = p->l.t.t != BC_LEX_KEY_AUTO;
4473
4474                 if (!p->auto_part) {
4475                         s = bc_parse_auto(p);
4476                         if (s) return s;
4477                 }
4478
4479                 if (p->l.t.t == BC_LEX_NLINE) s = bc_lex_next(&p->l);
4480         }
4481         else {
4482                 s = bc_parse_stmt(p);
4483                 if (!s && !brace) s = bc_parse_endBody(p, false);
4484         }
4485
4486         return s;
4487 }
4488
4489 static BcStatus bc_parse_stmt(BcParse *p)
4490 {
4491         BcStatus s = BC_STATUS_SUCCESS;
4492
4493         switch (p->l.t.t) {
4494
4495                 case BC_LEX_NLINE:
4496                 {
4497                         return bc_lex_next(&p->l);
4498                 }
4499
4500                 case BC_LEX_KEY_ELSE:
4501                 {
4502                         p->auto_part = false;
4503                         break;
4504                 }
4505
4506                 case BC_LEX_LBRACE:
4507                 {
4508                         if (!BC_PARSE_BODY(p)) return bc_error_bad_token();
4509
4510                         ++p->nbraces;
4511                         s = bc_lex_next(&p->l);
4512                         if (s) return s;
4513
4514                         return bc_parse_body(p, true);
4515                 }
4516
4517                 case BC_LEX_KEY_AUTO:
4518                 {
4519                         return bc_parse_auto(p);
4520                 }
4521
4522                 default:
4523                 {
4524                         p->auto_part = false;
4525
4526                         if (BC_PARSE_IF_END(p)) {
4527                                 bc_parse_noElse(p);
4528                                 return BC_STATUS_SUCCESS;
4529                         }
4530                         else if (BC_PARSE_BODY(p))
4531                                 return bc_parse_body(p, false);
4532
4533                         break;
4534                 }
4535         }
4536
4537         switch (p->l.t.t) {
4538
4539                 case BC_LEX_OP_INC:
4540                 case BC_LEX_OP_DEC:
4541                 case BC_LEX_OP_MINUS:
4542                 case BC_LEX_OP_BOOL_NOT:
4543                 case BC_LEX_LPAREN:
4544                 case BC_LEX_NAME:
4545                 case BC_LEX_NUMBER:
4546                 case BC_LEX_KEY_IBASE:
4547                 case BC_LEX_KEY_LAST:
4548                 case BC_LEX_KEY_LENGTH:
4549                 case BC_LEX_KEY_OBASE:
4550                 case BC_LEX_KEY_READ:
4551                 case BC_LEX_KEY_SCALE:
4552                 case BC_LEX_KEY_SQRT:
4553                 {
4554                         s = bc_parse_expr(p, BC_PARSE_PRINT, bc_parse_next_expr);
4555                         break;
4556                 }
4557
4558                 case BC_LEX_KEY_ELSE:
4559                 {
4560                         s = bc_parse_else(p);
4561                         break;
4562                 }
4563
4564                 case BC_LEX_SCOLON:
4565                 {
4566                         while (!s && p->l.t.t == BC_LEX_SCOLON) s = bc_lex_next(&p->l);
4567                         break;
4568                 }
4569
4570                 case BC_LEX_RBRACE:
4571                 {
4572                         s = bc_parse_endBody(p, true);
4573                         break;
4574                 }
4575
4576                 case BC_LEX_STR:
4577                 {
4578                         s = bc_parse_string(p, BC_INST_PRINT_STR);
4579                         break;
4580                 }
4581
4582                 case BC_LEX_KEY_BREAK:
4583                 case BC_LEX_KEY_CONTINUE:
4584                 {
4585                         s = bc_parse_loopExit(p, p->l.t.t);
4586                         break;
4587                 }
4588
4589                 case BC_LEX_KEY_FOR:
4590                 {
4591                         s = bc_parse_for(p);
4592                         break;
4593                 }
4594
4595                 case BC_LEX_KEY_HALT:
4596                 {
4597                         bc_parse_push(p, BC_INST_HALT);
4598                         s = bc_lex_next(&p->l);
4599                         break;
4600                 }
4601
4602                 case BC_LEX_KEY_IF:
4603                 {
4604                         s = bc_parse_if(p);
4605                         break;
4606                 }
4607
4608                 case BC_LEX_KEY_LIMITS:
4609                 {
4610                         // "limits" is a compile-time command,
4611                         // the output is produced at _parse time_.
4612                         s = bc_lex_next(&p->l);
4613                         if (s) return s;
4614                         printf("BC_BASE_MAX     = %u\n", BC_MAX_OBASE);
4615                         printf("BC_DIM_MAX      = %u\n", BC_MAX_DIM);
4616                         printf("BC_SCALE_MAX    = %u\n", BC_MAX_SCALE);
4617                         printf("BC_STRING_MAX   = %u\n", BC_MAX_STRING);
4618                         printf("BC_NAME_MAX     = %u\n", BC_MAX_NAME);
4619                         printf("BC_NUM_MAX      = %u\n", BC_MAX_NUM);
4620                         printf("MAX Exponent    = %lu\n", BC_MAX_EXP);
4621                         printf("Number of vars  = %lu\n", BC_MAX_VARS);
4622                         break;
4623                 }
4624
4625                 case BC_LEX_KEY_PRINT:
4626                 {
4627                         s = bc_parse_print(p);
4628                         break;
4629                 }
4630
4631                 case BC_LEX_KEY_QUIT:
4632                 {
4633                         // "quit" is a compile-time command. For example,
4634                         // "if (0 == 1) quit" terminates when parsing the statement,
4635                         // not when it is executed
4636                         quit();
4637                 }
4638
4639                 case BC_LEX_KEY_RETURN:
4640                 {
4641                         s = bc_parse_return(p);
4642                         break;
4643                 }
4644
4645                 case BC_LEX_KEY_WHILE:
4646                 {
4647                         s = bc_parse_while(p);
4648                         break;
4649                 }
4650
4651                 default:
4652                 {
4653                         s = bc_error_bad_token();
4654                         break;
4655                 }
4656         }
4657
4658         return s;
4659 }
4660
4661 static BcStatus bc_parse_parse(BcParse *p)
4662 {
4663         BcStatus s;
4664
4665         if (p->l.t.t == BC_LEX_EOF)
4666                 s = p->flags.len > 0 ? bc_error("block end could not be found") : bc_error("end of file");
4667         else if (p->l.t.t == BC_LEX_KEY_DEFINE) {
4668                 if (!BC_PARSE_CAN_EXEC(p)) return bc_error_bad_token();
4669                 s = bc_parse_func(p);
4670         }
4671         else
4672                 s = bc_parse_stmt(p);
4673
4674         if (s || G_interrupt) {
4675                 bc_parse_reset(p);
4676                 s = BC_STATUS_FAILURE;
4677         }
4678
4679         return s;
4680 }
4681
4682 static BcStatus bc_parse_expr(BcParse *p, uint8_t flags, BcParseNext next)
4683 {
4684         BcStatus s = BC_STATUS_SUCCESS;
4685         BcInst prev = BC_INST_PRINT;
4686         BcLexType top, t = p->l.t.t;
4687         size_t nexprs = 0, ops_bgn = p->ops.len;
4688         uint32_t i, nparens, nrelops;
4689         bool paren_first, paren_expr, rprn, done, get_token, assign, bin_last;
4690
4691         paren_first = p->l.t.t == BC_LEX_LPAREN;
4692         nparens = nrelops = 0;
4693         paren_expr = rprn = done = get_token = assign = false;
4694         bin_last = true;
4695
4696         for (; !G_interrupt && !s && !done && bc_parse_exprs[t]; t = p->l.t.t) {
4697                 switch (t) {
4698
4699                         case BC_LEX_OP_INC:
4700                         case BC_LEX_OP_DEC:
4701                         {
4702                                 s = bc_parse_incdec(p, &prev, &paren_expr, &nexprs, flags);
4703                                 rprn = get_token = bin_last = false;
4704                                 break;
4705                         }
4706
4707                         case BC_LEX_OP_MINUS:
4708                         {
4709                                 s = bc_parse_minus(p, &prev, ops_bgn, rprn, &nexprs);
4710                                 rprn = get_token = false;
4711                                 bin_last = prev == BC_INST_MINUS;
4712                                 break;
4713                         }
4714
4715                         case BC_LEX_OP_ASSIGN_POWER:
4716                         case BC_LEX_OP_ASSIGN_MULTIPLY:
4717                         case BC_LEX_OP_ASSIGN_DIVIDE:
4718                         case BC_LEX_OP_ASSIGN_MODULUS:
4719                         case BC_LEX_OP_ASSIGN_PLUS:
4720                         case BC_LEX_OP_ASSIGN_MINUS:
4721                         case BC_LEX_OP_ASSIGN:
4722                         {
4723                                 if (prev != BC_INST_VAR && prev != BC_INST_ARRAY_ELEM &&
4724                                     prev != BC_INST_SCALE && prev != BC_INST_IBASE &&
4725                                     prev != BC_INST_OBASE && prev != BC_INST_LAST)
4726                                 {
4727                                         s = bc_error("bad assignment:"
4728                                                 " left side must be scale,"
4729                                                 " ibase, obase, last, var,"
4730                                                 " or array element"
4731                                         );
4732                                         break;
4733                                 }
4734                         }
4735                         // Fallthrough.
4736                         case BC_LEX_OP_POWER:
4737                         case BC_LEX_OP_MULTIPLY:
4738                         case BC_LEX_OP_DIVIDE:
4739                         case BC_LEX_OP_MODULUS:
4740                         case BC_LEX_OP_PLUS:
4741                         case BC_LEX_OP_REL_EQ:
4742                         case BC_LEX_OP_REL_LE:
4743                         case BC_LEX_OP_REL_GE:
4744                         case BC_LEX_OP_REL_NE:
4745                         case BC_LEX_OP_REL_LT:
4746                         case BC_LEX_OP_REL_GT:
4747                         case BC_LEX_OP_BOOL_NOT:
4748                         case BC_LEX_OP_BOOL_OR:
4749                         case BC_LEX_OP_BOOL_AND:
4750                         {
4751                                 if (((t == BC_LEX_OP_BOOL_NOT) != bin_last)
4752                                  || (t != BC_LEX_OP_BOOL_NOT && prev == BC_INST_BOOL_NOT)
4753                                 ) {
4754                                         return bc_error_bad_expression();
4755                                 }
4756
4757                                 nrelops += t >= BC_LEX_OP_REL_EQ && t <= BC_LEX_OP_REL_GT;
4758                                 prev = BC_PARSE_TOKEN_INST(t);
4759                                 s = bc_parse_operator(p, t, ops_bgn, &nexprs, true);
4760                                 rprn = get_token = false;
4761                                 bin_last = t != BC_LEX_OP_BOOL_NOT;
4762
4763                                 break;
4764                         }
4765
4766                         case BC_LEX_LPAREN:
4767                         {
4768                                 if (BC_PARSE_LEAF(prev, rprn))
4769                                         return bc_error_bad_expression();
4770                                 ++nparens;
4771                                 paren_expr = rprn = bin_last = false;
4772                                 get_token = true;
4773                                 bc_vec_push(&p->ops, &t);
4774
4775                                 break;
4776                         }
4777
4778                         case BC_LEX_RPAREN:
4779                         {
4780                                 if (bin_last || prev == BC_INST_BOOL_NOT)
4781                                         return bc_error_bad_expression();
4782
4783                                 if (nparens == 0) {
4784                                         s = BC_STATUS_SUCCESS;
4785                                         done = true;
4786                                         get_token = false;
4787                                         break;
4788                                 }
4789                                 else if (!paren_expr)
4790                                         return BC_STATUS_PARSE_EMPTY_EXP;
4791
4792                                 --nparens;
4793                                 paren_expr = rprn = true;
4794                                 get_token = bin_last = false;
4795
4796                                 s = bc_parse_rightParen(p, ops_bgn, &nexprs);
4797
4798                                 break;
4799                         }
4800
4801                         case BC_LEX_NAME:
4802                         {
4803                                 if (BC_PARSE_LEAF(prev, rprn))
4804                                         return bc_error_bad_expression();
4805                                 paren_expr = true;
4806                                 rprn = get_token = bin_last = false;
4807                                 s = bc_parse_name(p, &prev, flags & ~BC_PARSE_NOCALL);
4808                                 ++nexprs;
4809
4810                                 break;
4811                         }
4812
4813                         case BC_LEX_NUMBER:
4814                         {
4815                                 if (BC_PARSE_LEAF(prev, rprn))
4816                                         return bc_error_bad_expression();
4817                                 bc_parse_number(p, &prev, &nexprs);
4818                                 paren_expr = get_token = true;
4819                                 rprn = bin_last = false;
4820
4821                                 break;
4822                         }
4823
4824                         case BC_LEX_KEY_IBASE:
4825                         case BC_LEX_KEY_LAST:
4826                         case BC_LEX_KEY_OBASE:
4827                         {
4828                                 if (BC_PARSE_LEAF(prev, rprn))
4829                                         return bc_error_bad_expression();
4830                                 prev = (char) (t - BC_LEX_KEY_IBASE + BC_INST_IBASE);
4831                                 bc_parse_push(p, (char) prev);
4832
4833                                 paren_expr = get_token = true;
4834                                 rprn = bin_last = false;
4835                                 ++nexprs;
4836
4837                                 break;
4838                         }
4839
4840                         case BC_LEX_KEY_LENGTH:
4841                         case BC_LEX_KEY_SQRT:
4842                         {
4843                                 if (BC_PARSE_LEAF(prev, rprn))
4844                                         return bc_error_bad_expression();
4845                                 s = bc_parse_builtin(p, t, flags, &prev);
4846                                 paren_expr = true;
4847                                 rprn = get_token = bin_last = false;
4848                                 ++nexprs;
4849
4850                                 break;
4851                         }
4852
4853                         case BC_LEX_KEY_READ:
4854                         {
4855                                 if (BC_PARSE_LEAF(prev, rprn))
4856                                         return bc_error_bad_expression();
4857                                 else if (flags & BC_PARSE_NOREAD)
4858                                         s = bc_error_nested_read_call();
4859                                 else
4860                                         s = bc_parse_read(p);
4861
4862                                 paren_expr = true;
4863                                 rprn = get_token = bin_last = false;
4864                                 ++nexprs;
4865                                 prev = BC_INST_READ;
4866
4867                                 break;
4868                         }
4869
4870                         case BC_LEX_KEY_SCALE:
4871                         {
4872                                 if (BC_PARSE_LEAF(prev, rprn))
4873                                         return bc_error_bad_expression();
4874                                 s = bc_parse_scale(p, &prev, flags);
4875                                 paren_expr = true;
4876                                 rprn = get_token = bin_last = false;
4877                                 ++nexprs;
4878                                 prev = BC_INST_SCALE;
4879
4880                                 break;
4881                         }
4882
4883                         default:
4884                         {
4885                                 s = bc_error_bad_token();
4886                                 break;
4887                         }
4888                 }
4889
4890                 if (!s && get_token) s = bc_lex_next(&p->l);
4891         }
4892
4893         if (s) return s;
4894         if (G_interrupt) return BC_STATUS_FAILURE; // ^C: stop parsing
4895
4896         while (p->ops.len > ops_bgn) {
4897
4898                 top = BC_PARSE_TOP_OP(p);
4899                 assign = top >= BC_LEX_OP_ASSIGN_POWER && top <= BC_LEX_OP_ASSIGN;
4900
4901                 if (top == BC_LEX_LPAREN || top == BC_LEX_RPAREN)
4902                         return bc_error_bad_expression();
4903
4904                 bc_parse_push(p, BC_PARSE_TOKEN_INST(top));
4905
4906                 nexprs -= top != BC_LEX_OP_BOOL_NOT && top != BC_LEX_NEG;
4907                 bc_vec_pop(&p->ops);
4908         }
4909
4910         if (prev == BC_INST_BOOL_NOT || nexprs != 1)
4911                 return bc_error_bad_expression();
4912
4913         for (i = 0; i < next.len; ++i)
4914                 if (t == next.tokens[i])
4915                         goto ok;
4916         return bc_error_bad_expression();
4917  ok:
4918
4919         if (!(flags & BC_PARSE_REL) && nrelops) {
4920                 s = bc_POSIX_does_not_allow("comparison operators outside if or loops");
4921                 if (s) return s;
4922         }
4923         else if ((flags & BC_PARSE_REL) && nrelops > 1) {
4924                 s = bc_posix_error("POSIX requires exactly one comparison operator per condition");
4925                 if (s) return s;
4926         }
4927
4928         if (flags & BC_PARSE_PRINT) {
4929                 if (paren_first || !assign) bc_parse_push(p, BC_INST_PRINT);
4930                 bc_parse_push(p, BC_INST_POP);
4931         }
4932
4933         return s;
4934 }
4935
4936 static void bc_parse_init(BcParse *p, size_t func)
4937 {
4938         bc_parse_create(p, func, bc_parse_parse, bc_lex_token);
4939 }
4940
4941 static BcStatus bc_parse_expression(BcParse *p, uint8_t flags)
4942 {
4943         return bc_parse_expr(p, flags, bc_parse_next_read);
4944 }
4945 #endif // ENABLE_BC
4946
4947 #if ENABLE_DC
4948 static BcStatus dc_parse_register(BcParse *p)
4949 {
4950         BcStatus s;
4951         char *name;
4952
4953         s = bc_lex_next(&p->l);
4954         if (s) return s;
4955         if (p->l.t.t != BC_LEX_NAME) return bc_error_bad_token();
4956
4957         name = xstrdup(p->l.t.v.v);
4958         bc_parse_pushName(p, name);
4959
4960         return s;
4961 }
4962
4963 static BcStatus dc_parse_string(BcParse *p)
4964 {
4965         char *str, *name, b[DC_PARSE_BUF_LEN + 1];
4966         size_t idx, len = G.prog.strs.len;
4967
4968         sprintf(b, "%0*zu", DC_PARSE_BUF_LEN, len);
4969         name = xstrdup(b);
4970
4971         str = xstrdup(p->l.t.v.v);
4972         bc_parse_push(p, BC_INST_STR);
4973         bc_parse_pushIndex(p, len);
4974         bc_vec_push(&G.prog.strs, &str);
4975         bc_parse_addFunc(p, name, &idx);
4976
4977         return bc_lex_next(&p->l);
4978 }
4979
4980 static BcStatus dc_parse_mem(BcParse *p, uint8_t inst, bool name, bool store)
4981 {
4982         BcStatus s;
4983
4984         bc_parse_push(p, inst);
4985         if (name) {
4986                 s = dc_parse_register(p);
4987                 if (s) return s;
4988         }
4989
4990         if (store) {
4991                 bc_parse_push(p, BC_INST_SWAP);
4992                 bc_parse_push(p, BC_INST_ASSIGN);
4993                 bc_parse_push(p, BC_INST_POP);
4994         }
4995
4996         return bc_lex_next(&p->l);
4997 }
4998
4999 static BcStatus dc_parse_cond(BcParse *p, uint8_t inst)
5000 {
5001         BcStatus s;
5002
5003         bc_parse_push(p, inst);
5004         bc_parse_push(p, BC_INST_EXEC_COND);
5005
5006         s = dc_parse_register(p);
5007         if (s) return s;
5008
5009         s = bc_lex_next(&p->l);
5010         if (s) return s;
5011
5012         if (p->l.t.t == BC_LEX_ELSE) {
5013                 s = dc_parse_register(p);
5014                 if (s) return s;
5015                 s = bc_lex_next(&p->l);
5016         }
5017         else
5018                 bc_parse_push(p, BC_PARSE_STREND);
5019
5020         return s;
5021 }
5022
5023 static BcStatus dc_parse_token(BcParse *p, BcLexType t, uint8_t flags)
5024 {
5025         BcStatus s = BC_STATUS_SUCCESS;
5026         BcInst prev;
5027         uint8_t inst;
5028         bool assign, get_token = false;
5029
5030         switch (t) {
5031
5032                 case BC_LEX_OP_REL_EQ:
5033                 case BC_LEX_OP_REL_LE:
5034                 case BC_LEX_OP_REL_GE:
5035                 case BC_LEX_OP_REL_NE:
5036                 case BC_LEX_OP_REL_LT:
5037                 case BC_LEX_OP_REL_GT:
5038                 {
5039                         s = dc_parse_cond(p, t - BC_LEX_OP_REL_EQ + BC_INST_REL_EQ);
5040                         break;
5041                 }
5042
5043                 case BC_LEX_SCOLON:
5044                 case BC_LEX_COLON:
5045                 {
5046                         s = dc_parse_mem(p, BC_INST_ARRAY_ELEM, true, t == BC_LEX_COLON);
5047                         break;
5048                 }
5049
5050                 case BC_LEX_STR:
5051                 {
5052                         s = dc_parse_string(p);
5053                         break;
5054                 }
5055
5056                 case BC_LEX_NEG:
5057                 case BC_LEX_NUMBER:
5058                 {
5059                         if (t == BC_LEX_NEG) {
5060                                 s = bc_lex_next(&p->l);
5061                                 if (s) return s;
5062                                 if (p->l.t.t != BC_LEX_NUMBER)
5063                                         return bc_error_bad_token();
5064                         }
5065
5066                         bc_parse_number(p, &prev, &p->nbraces);
5067
5068                         if (t == BC_LEX_NEG) bc_parse_push(p, BC_INST_NEG);
5069                         get_token = true;
5070
5071                         break;
5072                 }
5073
5074                 case BC_LEX_KEY_READ:
5075                 {
5076                         if (flags & BC_PARSE_NOREAD)
5077                                 s = bc_error_nested_read_call();
5078                         else
5079                                 bc_parse_push(p, BC_INST_READ);
5080                         get_token = true;
5081                         break;
5082                 }
5083
5084                 case BC_LEX_OP_ASSIGN:
5085                 case BC_LEX_STORE_PUSH:
5086                 {
5087                         assign = t == BC_LEX_OP_ASSIGN;
5088                         inst = assign ? BC_INST_VAR : BC_INST_PUSH_TO_VAR;
5089                         s = dc_parse_mem(p, inst, true, assign);
5090                         break;
5091                 }
5092
5093                 case BC_LEX_LOAD:
5094                 case BC_LEX_LOAD_POP:
5095                 {
5096                         inst = t == BC_LEX_LOAD_POP ? BC_INST_PUSH_VAR : BC_INST_LOAD;
5097                         s = dc_parse_mem(p, inst, true, false);
5098                         break;
5099                 }
5100
5101                 case BC_LEX_STORE_IBASE:
5102                 case BC_LEX_STORE_SCALE:
5103                 case BC_LEX_STORE_OBASE:
5104                 {
5105                         inst = t - BC_LEX_STORE_IBASE + BC_INST_IBASE;
5106                         s = dc_parse_mem(p, inst, false, true);
5107                         break;
5108                 }
5109
5110                 default:
5111                 {
5112                         s = bc_error_bad_token();
5113                         get_token = true;
5114                         break;
5115                 }
5116         }
5117
5118         if (!s && get_token) s = bc_lex_next(&p->l);
5119
5120         return s;
5121 }
5122
5123 static BcStatus dc_parse_expr(BcParse *p, uint8_t flags)
5124 {
5125         BcStatus s = BC_STATUS_SUCCESS;
5126         BcInst inst;
5127         BcLexType t;
5128
5129         if (flags & BC_PARSE_NOCALL) p->nbraces = G.prog.results.len;
5130
5131         for (t = p->l.t.t; !s && t != BC_LEX_EOF; t = p->l.t.t) {
5132
5133                 inst = dc_parse_insts[t];
5134
5135                 if (inst != BC_INST_INVALID) {
5136                         bc_parse_push(p, inst);
5137                         s = bc_lex_next(&p->l);
5138                 }
5139                 else
5140                         s = dc_parse_token(p, t, flags);
5141         }
5142
5143         if (!s && p->l.t.t == BC_LEX_EOF && (flags & BC_PARSE_NOCALL))
5144                 bc_parse_push(p, BC_INST_POP_EXEC);
5145
5146         return s;
5147 }
5148
5149 static BcStatus dc_parse_parse(BcParse *p)
5150 {
5151         BcStatus s;
5152
5153         if (p->l.t.t == BC_LEX_EOF)
5154                 s = bc_error("end of file");
5155         else
5156                 s = dc_parse_expr(p, 0);
5157
5158         if (s || G_interrupt) {
5159                 bc_parse_reset(p);
5160                 s = BC_STATUS_FAILURE;
5161         }
5162
5163         return s;
5164 }
5165
5166 static void dc_parse_init(BcParse *p, size_t func)
5167 {
5168         bc_parse_create(p, func, dc_parse_parse, dc_lex_token);
5169 }
5170 #endif // ENABLE_DC
5171
5172 static void common_parse_init(BcParse *p, size_t func)
5173 {
5174         if (IS_BC) {
5175                 bc_parse_init(p, func);
5176         } else {
5177                 dc_parse_init(p, func);
5178         }
5179 }
5180
5181 static BcStatus common_parse_expr(BcParse *p, uint8_t flags)
5182 {
5183         if (IS_BC) {
5184                 return bc_parse_expression(p, flags);
5185         } else {
5186                 return dc_parse_expr(p, flags);
5187         }
5188 }
5189
5190 static BcVec* bc_program_search(char *id, bool var)
5191 {
5192         BcId e, *ptr;
5193         BcVec *v, *map;
5194         size_t i;
5195         BcResultData data;
5196         int new;
5197
5198         v = var ? &G.prog.vars : &G.prog.arrs;
5199         map = var ? &G.prog.var_map : &G.prog.arr_map;
5200
5201         e.name = id;
5202         e.idx = v->len;
5203         new = bc_map_insert(map, &e, &i); // 1 if insertion was successful
5204
5205         if (new) {
5206                 bc_array_init(&data.v, var);
5207                 bc_vec_push(v, &data.v);
5208         }
5209
5210         ptr = bc_vec_item(map, i);
5211         if (new) ptr->name = xstrdup(e.name);
5212         return bc_vec_item(v, ptr->idx);
5213 }
5214
5215 static BcStatus bc_program_num(BcResult *r, BcNum **num, bool hex)
5216 {
5217         BcStatus s = BC_STATUS_SUCCESS;
5218
5219         switch (r->t) {
5220
5221                 case BC_RESULT_STR:
5222                 case BC_RESULT_TEMP:
5223                 case BC_RESULT_IBASE:
5224                 case BC_RESULT_SCALE:
5225                 case BC_RESULT_OBASE:
5226                 {
5227                         *num = &r->d.n;
5228                         break;
5229                 }
5230
5231                 case BC_RESULT_CONSTANT:
5232                 {
5233                         char **str = bc_vec_item(&G.prog.consts, r->d.id.idx);
5234                         size_t base_t, len = strlen(*str);
5235                         BcNum *base;
5236
5237                         bc_num_init(&r->d.n, len);
5238
5239                         hex = hex && len == 1;
5240                         base = hex ? &G.prog.hexb : &G.prog.ib;
5241                         base_t = hex ? BC_NUM_MAX_IBASE : G.prog.ib_t;
5242                         s = bc_num_parse(&r->d.n, *str, base, base_t);
5243
5244                         if (s) {
5245                                 bc_num_free(&r->d.n);
5246                                 return s;
5247                         }
5248
5249                         *num = &r->d.n;
5250                         r->t = BC_RESULT_TEMP;
5251
5252                         break;
5253                 }
5254
5255                 case BC_RESULT_VAR:
5256                 case BC_RESULT_ARRAY:
5257                 case BC_RESULT_ARRAY_ELEM:
5258                 {
5259                         BcVec *v;
5260
5261                         v = bc_program_search(r->d.id.name, r->t == BC_RESULT_VAR);
5262
5263                         if (r->t == BC_RESULT_ARRAY_ELEM) {
5264                                 v = bc_vec_top(v);
5265                                 if (v->len <= r->d.id.idx) bc_array_expand(v, r->d.id.idx + 1);
5266                                 *num = bc_vec_item(v, r->d.id.idx);
5267                         }
5268                         else
5269                                 *num = bc_vec_top(v);
5270
5271                         break;
5272                 }
5273
5274                 case BC_RESULT_LAST:
5275                 {
5276                         *num = &G.prog.last;
5277                         break;
5278                 }
5279
5280                 case BC_RESULT_ONE:
5281                 {
5282                         *num = &G.prog.one;
5283                         break;
5284                 }
5285         }
5286
5287         return s;
5288 }
5289
5290 static BcStatus bc_program_binOpPrep(BcResult **l, BcNum **ln,
5291                                      BcResult **r, BcNum **rn, bool assign)
5292 {
5293         BcStatus s;
5294         bool hex;
5295         BcResultType lt, rt;
5296
5297         if (!BC_PROG_STACK(&G.prog.results, 2))
5298                 return bc_error_stack_has_too_few_elements();
5299
5300         *r = bc_vec_item_rev(&G.prog.results, 0);
5301         *l = bc_vec_item_rev(&G.prog.results, 1);
5302
5303         lt = (*l)->t;
5304         rt = (*r)->t;
5305         hex = assign && (lt == BC_RESULT_IBASE || lt == BC_RESULT_OBASE);
5306
5307         s = bc_program_num(*l, ln, false);
5308         if (s) return s;
5309         s = bc_program_num(*r, rn, hex);
5310         if (s) return s;
5311
5312         // We run this again under these conditions in case any vector has been
5313         // reallocated out from under the BcNums or arrays we had.
5314         if (lt == rt && (lt == BC_RESULT_VAR || lt == BC_RESULT_ARRAY_ELEM)) {
5315                 s = bc_program_num(*l, ln, false);
5316                 if (s) return s;
5317         }
5318
5319         if (!BC_PROG_NUM((*l), (*ln)) && (!assign || (*l)->t != BC_RESULT_VAR))
5320                 return bc_error_variable_is_wrong_type();
5321         if (!assign && !BC_PROG_NUM((*r), (*ln)))
5322                 return bc_error_variable_is_wrong_type();
5323
5324         return s;
5325 }
5326
5327 static void bc_program_binOpRetire(BcResult *r)
5328 {
5329         r->t = BC_RESULT_TEMP;
5330         bc_vec_pop(&G.prog.results);
5331         bc_vec_pop(&G.prog.results);
5332         bc_vec_push(&G.prog.results, r);
5333 }
5334
5335 static BcStatus bc_program_prep(BcResult **r, BcNum **n)
5336 {
5337         BcStatus s;
5338
5339         if (!BC_PROG_STACK(&G.prog.results, 1))
5340                 return bc_error_stack_has_too_few_elements();
5341         *r = bc_vec_top(&G.prog.results);
5342
5343         s = bc_program_num(*r, n, false);
5344         if (s) return s;
5345
5346         if (!BC_PROG_NUM((*r), (*n)))
5347                 return bc_error_variable_is_wrong_type();
5348
5349         return s;
5350 }
5351
5352 static void bc_program_retire(BcResult *r, BcResultType t)
5353 {
5354         r->t = t;
5355         bc_vec_pop(&G.prog.results);
5356         bc_vec_push(&G.prog.results, r);
5357 }
5358
5359 static BcStatus bc_program_op(char inst)
5360 {
5361         BcStatus s;
5362         BcResult *opd1, *opd2, res;
5363         BcNum *n1, *n2 = NULL;
5364
5365         s = bc_program_binOpPrep(&opd1, &n1, &opd2, &n2, false);
5366         if (s) return s;
5367         bc_num_init(&res.d.n, BC_NUM_DEF_SIZE);
5368
5369         s = bc_program_ops[inst - BC_INST_POWER](n1, n2, &res.d.n, G.prog.scale);
5370         if (s) goto err;
5371         bc_program_binOpRetire(&res);
5372
5373         return s;
5374
5375 err:
5376         bc_num_free(&res.d.n);
5377         return s;
5378 }
5379
5380 static BcStatus bc_program_read(void)
5381 {
5382         const char *sv_file;
5383         BcStatus s;
5384         BcParse parse;
5385         BcVec buf;
5386         BcInstPtr ip;
5387         size_t i;
5388         BcFunc *f = bc_vec_item(&G.prog.fns, BC_PROG_READ);
5389
5390         for (i = 0; i < G.prog.stack.len; ++i) {
5391                 BcInstPtr *ip_ptr = bc_vec_item(&G.prog.stack, i);
5392                 if (ip_ptr->func == BC_PROG_READ)
5393                         return bc_error_nested_read_call();
5394         }
5395
5396         bc_vec_pop_all(&f->code);
5397         bc_char_vec_init(&buf);
5398
5399         sv_file = G.prog.file;
5400         G.prog.file = NULL;
5401
5402         s = bc_read_line(&buf, "read> ");
5403         if (s) goto io_err;
5404
5405         common_parse_init(&parse, BC_PROG_READ);
5406         bc_lex_file(&parse.l);
5407
5408         s = bc_parse_text(&parse, buf.v);
5409         if (s) goto exec_err;
5410         s = common_parse_expr(&parse, BC_PARSE_NOREAD);
5411         if (s) goto exec_err;
5412
5413         if (parse.l.t.t != BC_LEX_NLINE && parse.l.t.t != BC_LEX_EOF) {
5414                 s = bc_error("bad read() expression");
5415                 goto exec_err;
5416         }
5417
5418         ip.func = BC_PROG_READ;
5419         ip.idx = 0;
5420         ip.len = G.prog.results.len;
5421
5422         // Update this pointer, just in case.
5423         f = bc_vec_item(&G.prog.fns, BC_PROG_READ);
5424
5425         bc_vec_pushByte(&f->code, BC_INST_POP_EXEC);
5426         bc_vec_push(&G.prog.stack, &ip);
5427
5428 exec_err:
5429         G.prog.file = sv_file;
5430         bc_parse_free(&parse);
5431 io_err:
5432         bc_vec_free(&buf);
5433         return s;
5434 }
5435
5436 static size_t bc_program_index(char *code, size_t *bgn)
5437 {
5438         char amt = code[(*bgn)++], i = 0;
5439         size_t res = 0;
5440
5441         for (; i < amt; ++i, ++(*bgn))
5442                 res |= (((size_t)((int) code[*bgn]) & UCHAR_MAX) << (i * CHAR_BIT));
5443
5444         return res;
5445 }
5446
5447 static char *bc_program_name(char *code, size_t *bgn)
5448 {
5449         size_t i;
5450         char c, *s, *str = code + *bgn, *ptr = strchr(str, BC_PARSE_STREND);
5451
5452         s = xmalloc(ptr - str + 1);
5453         c = code[(*bgn)++];
5454
5455         for (i = 0; c != 0 && c != BC_PARSE_STREND; c = code[(*bgn)++], ++i)
5456                 s[i] = c;
5457
5458         s[i] = '\0';
5459
5460         return s;
5461 }
5462
5463 static void bc_program_printString(const char *str, size_t *nchars)
5464 {
5465         size_t i, len = strlen(str);
5466
5467 #if ENABLE_DC
5468         if (len == 0) {
5469                 bb_putchar('\0');
5470                 return;
5471         }
5472 #endif
5473
5474         for (i = 0; i < len; ++i, ++(*nchars)) {
5475
5476                 int c = str[i];
5477
5478                 if (c != '\\' || i == len - 1)
5479                         bb_putchar(c);
5480                 else {
5481
5482                         c = str[++i];
5483
5484                         switch (c) {
5485
5486                                 case 'a':
5487                                 {
5488                                         bb_putchar('\a');
5489                                         break;
5490                                 }
5491
5492                                 case 'b':
5493                                 {
5494                                         bb_putchar('\b');
5495                                         break;
5496                                 }
5497
5498                                 case '\\':
5499                                 case 'e':
5500                                 {
5501                                         bb_putchar('\\');
5502                                         break;
5503                                 }
5504
5505                                 case 'f':
5506                                 {
5507                                         bb_putchar('\f');
5508                                         break;
5509                                 }
5510
5511                                 case 'n':
5512                                 {
5513                                         bb_putchar('\n');
5514                                         *nchars = SIZE_MAX;
5515                                         break;
5516                                 }
5517
5518                                 case 'r':
5519                                 {
5520                                         bb_putchar('\r');
5521                                         break;
5522                                 }
5523
5524                                 case 'q':
5525                                 {
5526                                         bb_putchar('"');
5527                                         break;
5528                                 }
5529
5530                                 case 't':
5531                                 {
5532                                         bb_putchar('\t');
5533                                         break;
5534                                 }
5535
5536                                 default:
5537                                 {
5538                                         // Just print the backslash and following character.
5539                                         bb_putchar('\\');
5540                                         ++(*nchars);
5541                                         bb_putchar(c);
5542                                         break;
5543                                 }
5544                         }
5545                 }
5546         }
5547 }
5548
5549 static BcStatus bc_program_print(char inst, size_t idx)
5550 {
5551         BcStatus s = BC_STATUS_SUCCESS;
5552         BcResult *r;
5553         size_t len, i;
5554         char *str;
5555         BcNum *num = NULL;
5556         bool pop = inst != BC_INST_PRINT;
5557
5558         if (!BC_PROG_STACK(&G.prog.results, idx + 1))
5559                 return bc_error_stack_has_too_few_elements();
5560
5561         r = bc_vec_item_rev(&G.prog.results, idx);
5562         s = bc_program_num(r, &num, false);
5563         if (s) return s;
5564
5565         if (BC_PROG_NUM(r, num)) {
5566                 s = bc_num_print(num, &G.prog.ob, G.prog.ob_t, !pop, &G.prog.nchars, G.prog.len);
5567                 if (!s) bc_num_copy(&G.prog.last, num);
5568         }
5569         else {
5570
5571                 idx = (r->t == BC_RESULT_STR) ? r->d.id.idx : num->rdx;
5572                 str = *((char **) bc_vec_item(&G.prog.strs, idx));
5573
5574                 if (inst == BC_INST_PRINT_STR) {
5575                         for (i = 0, len = strlen(str); i < len; ++i) {
5576                                 char c = str[i];
5577                                 bb_putchar(c);
5578                                 if (c == '\n') G.prog.nchars = SIZE_MAX;
5579                                 ++G.prog.nchars;
5580                         }
5581                 }
5582                 else {
5583                         bc_program_printString(str, &G.prog.nchars);
5584                         if (inst == BC_INST_PRINT) bb_putchar('\n');
5585                 }
5586         }
5587
5588         if (!s && pop) bc_vec_pop(&G.prog.results);
5589
5590         return s;
5591 }
5592
5593 static BcStatus bc_program_negate(void)
5594 {
5595         BcStatus s;
5596         BcResult res, *ptr;
5597         BcNum *num = NULL;
5598
5599         s = bc_program_prep(&ptr, &num);
5600         if (s) return s;
5601
5602         bc_num_init(&res.d.n, num->len);
5603         bc_num_copy(&res.d.n, num);
5604         if (res.d.n.len) res.d.n.neg = !res.d.n.neg;
5605
5606         bc_program_retire(&res, BC_RESULT_TEMP);
5607
5608         return s;
5609 }
5610
5611 static BcStatus bc_program_logical(char inst)
5612 {
5613         BcStatus s;
5614         BcResult *opd1, *opd2, res;
5615         BcNum *n1, *n2;
5616         bool cond = 0;
5617         ssize_t cmp;
5618
5619         s = bc_program_binOpPrep(&opd1, &n1, &opd2, &n2, false);
5620         if (s) return s;
5621         bc_num_init(&res.d.n, BC_NUM_DEF_SIZE);
5622
5623         if (inst == BC_INST_BOOL_AND)
5624                 cond = bc_num_cmp(n1, &G.prog.zero) && bc_num_cmp(n2, &G.prog.zero);
5625         else if (inst == BC_INST_BOOL_OR)
5626                 cond = bc_num_cmp(n1, &G.prog.zero) || bc_num_cmp(n2, &G.prog.zero);
5627         else {
5628
5629                 cmp = bc_num_cmp(n1, n2);
5630
5631                 switch (inst) {
5632
5633                         case BC_INST_REL_EQ:
5634                         {
5635                                 cond = cmp == 0;
5636                                 break;
5637                         }
5638
5639                         case BC_INST_REL_LE:
5640                         {
5641                                 cond = cmp <= 0;
5642                                 break;
5643                         }
5644
5645                         case BC_INST_REL_GE:
5646                         {
5647                                 cond = cmp >= 0;
5648                                 break;
5649                         }
5650
5651                         case BC_INST_REL_NE:
5652                         {
5653                                 cond = cmp != 0;
5654                                 break;
5655                         }
5656
5657                         case BC_INST_REL_LT:
5658                         {
5659                                 cond = cmp < 0;
5660                                 break;
5661                         }
5662
5663                         case BC_INST_REL_GT:
5664                         {
5665                                 cond = cmp > 0;
5666                                 break;
5667                         }
5668                 }
5669         }
5670
5671         (cond ? bc_num_one : bc_num_zero)(&res.d.n);
5672
5673         bc_program_binOpRetire(&res);
5674
5675         return s;
5676 }
5677
5678 #if ENABLE_DC
5679 static BcStatus bc_program_assignStr(BcResult *r, BcVec *v,
5680                                      bool push)
5681 {
5682         BcNum n2;
5683         BcResult res;
5684
5685         memset(&n2, 0, sizeof(BcNum));
5686         n2.rdx = res.d.id.idx = r->d.id.idx;
5687         res.t = BC_RESULT_STR;
5688
5689         if (!push) {
5690                 if (!BC_PROG_STACK(&G.prog.results, 2))
5691                         return bc_error_stack_has_too_few_elements();
5692                 bc_vec_pop(v);
5693                 bc_vec_pop(&G.prog.results);
5694         }
5695
5696         bc_vec_pop(&G.prog.results);
5697
5698         bc_vec_push(&G.prog.results, &res);
5699         bc_vec_push(v, &n2);
5700
5701         return BC_STATUS_SUCCESS;
5702 }
5703 #endif // ENABLE_DC
5704
5705 static BcStatus bc_program_copyToVar(char *name, bool var)
5706 {
5707         BcStatus s;
5708         BcResult *ptr, r;
5709         BcVec *v;
5710         BcNum *n;
5711
5712         if (!BC_PROG_STACK(&G.prog.results, 1))
5713                 return bc_error_stack_has_too_few_elements();
5714
5715         ptr = bc_vec_top(&G.prog.results);
5716         if ((ptr->t == BC_RESULT_ARRAY) != !var)
5717                 return bc_error_variable_is_wrong_type();
5718         v = bc_program_search(name, var);
5719
5720 #if ENABLE_DC
5721         if (ptr->t == BC_RESULT_STR && !var)
5722                 return bc_error_variable_is_wrong_type();
5723         if (ptr->t == BC_RESULT_STR) return bc_program_assignStr(ptr, v, true);
5724 #endif
5725
5726         s = bc_program_num(ptr, &n, false);
5727         if (s) return s;
5728
5729         // Do this once more to make sure that pointers were not invalidated.
5730         v = bc_program_search(name, var);
5731
5732         if (var) {
5733                 bc_num_init(&r.d.n, BC_NUM_DEF_SIZE);
5734                 bc_num_copy(&r.d.n, n);
5735         }
5736         else {
5737                 bc_array_init(&r.d.v, true);
5738                 bc_array_copy(&r.d.v, (BcVec *) n);
5739         }
5740
5741         bc_vec_push(v, &r.d);
5742         bc_vec_pop(&G.prog.results);
5743
5744         return s;
5745 }
5746
5747 static BcStatus bc_program_assign(char inst)
5748 {
5749         BcStatus s;
5750         BcResult *left, *right, res;
5751         BcNum *l = NULL, *r = NULL;
5752         unsigned long val, max;
5753         bool assign = inst == BC_INST_ASSIGN, ib, sc;
5754
5755         s = bc_program_binOpPrep(&left, &l, &right, &r, assign);
5756         if (s) return s;
5757
5758         ib = left->t == BC_RESULT_IBASE;
5759         sc = left->t == BC_RESULT_SCALE;
5760
5761 #if ENABLE_DC
5762
5763         if (right->t == BC_RESULT_STR) {
5764
5765                 BcVec *v;
5766
5767                 if (left->t != BC_RESULT_VAR)
5768                         return bc_error_variable_is_wrong_type();
5769                 v = bc_program_search(left->d.id.name, true);
5770
5771                 return bc_program_assignStr(right, v, false);
5772         }
5773 #endif
5774
5775         if (left->t == BC_RESULT_CONSTANT || left->t == BC_RESULT_TEMP)
5776                 return bc_error("bad assignment:"
5777                                 " left side must be scale,"
5778                                 " ibase, obase, last, var,"
5779                                 " or array element"
5780                 );
5781
5782 #if ENABLE_BC
5783         if (inst == BC_INST_ASSIGN_DIVIDE && !bc_num_cmp(r, &G.prog.zero))
5784                 return bc_error("divide by zero");
5785
5786         if (assign)
5787                 bc_num_copy(l, r);
5788         else
5789                 s = bc_program_ops[inst - BC_INST_ASSIGN_POWER](l, r, l, G.prog.scale);
5790
5791         if (s) return s;
5792 #else
5793         bc_num_copy(l, r);
5794 #endif
5795
5796         if (ib || sc || left->t == BC_RESULT_OBASE) {
5797                 static const char *const msg[] = {
5798                         "bad ibase; must be [2, 16]",           //BC_RESULT_IBASE
5799                         "bad scale; must be [0, BC_SCALE_MAX]", //BC_RESULT_SCALE
5800                         "?1",                                   //BC_RESULT_LAST
5801                         "?2",                                   //BC_RESULT_CONSTANT
5802                         "?3",                                   //BC_RESULT_ONE
5803                         "bad obase; must be [2, BC_BASE_MAX]",  //BC_RESULT_OBASE
5804                 };
5805                 size_t *ptr;
5806
5807                 s = bc_num_ulong(l, &val);
5808                 if (s)
5809                         return s;
5810                 s = left->t - BC_RESULT_IBASE;
5811                 if (sc) {
5812                         max = BC_MAX_SCALE;
5813                         ptr = &G.prog.scale;
5814                 }
5815                 else {
5816                         if (val < BC_NUM_MIN_BASE)
5817                                 return bc_error(msg[s]);
5818                         max = ib ? BC_NUM_MAX_IBASE : BC_MAX_OBASE;
5819                         ptr = ib ? &G.prog.ib_t : &G.prog.ob_t;
5820                 }
5821
5822                 if (val > max)
5823                         return bc_error(msg[s]);
5824                 if (!sc)
5825                         bc_num_copy(ib ? &G.prog.ib : &G.prog.ob, l);
5826
5827                 *ptr = (size_t) val;
5828                 s = BC_STATUS_SUCCESS;
5829         }
5830
5831         bc_num_init(&res.d.n, l->len);
5832         bc_num_copy(&res.d.n, l);
5833         bc_program_binOpRetire(&res);
5834
5835         return s;
5836 }
5837
5838 #if !ENABLE_DC
5839 #define bc_program_pushVar(code, bgn, pop, copy) \
5840         bc_program_pushVar(code, bgn)
5841 // for bc, 'pop' and 'copy' are always false
5842 #endif
5843 static BcStatus bc_program_pushVar(char *code, size_t *bgn,
5844                                    bool pop, bool copy)
5845 {
5846         BcStatus s = BC_STATUS_SUCCESS;
5847         BcResult r;
5848         char *name = bc_program_name(code, bgn);
5849
5850         r.t = BC_RESULT_VAR;
5851         r.d.id.name = name;
5852
5853 #if ENABLE_DC
5854         {
5855                 BcVec *v = bc_program_search(name, true);
5856                 BcNum *num = bc_vec_top(v);
5857
5858                 if (pop || copy) {
5859
5860                         if (!BC_PROG_STACK(v, 2 - copy)) {
5861                                 free(name);
5862                                 return bc_error_stack_has_too_few_elements();
5863                         }
5864
5865                         free(name);
5866                         name = NULL;
5867
5868                         if (!BC_PROG_STR(num)) {
5869
5870                                 r.t = BC_RESULT_TEMP;
5871
5872                                 bc_num_init(&r.d.n, BC_NUM_DEF_SIZE);
5873                                 bc_num_copy(&r.d.n, num);
5874                         }
5875                         else {
5876                                 r.t = BC_RESULT_STR;
5877                                 r.d.id.idx = num->rdx;
5878                         }
5879
5880                         if (!copy) bc_vec_pop(v);
5881                 }
5882         }
5883 #endif // ENABLE_DC
5884
5885         bc_vec_push(&G.prog.results, &r);
5886
5887         return s;
5888 }
5889
5890 static BcStatus bc_program_pushArray(char *code, size_t *bgn,
5891                                      char inst)
5892 {
5893         BcStatus s = BC_STATUS_SUCCESS;
5894         BcResult r;
5895         BcNum *num;
5896
5897         r.d.id.name = bc_program_name(code, bgn);
5898
5899         if (inst == BC_INST_ARRAY) {
5900                 r.t = BC_RESULT_ARRAY;
5901                 bc_vec_push(&G.prog.results, &r);
5902         }
5903         else {
5904
5905                 BcResult *operand;
5906                 unsigned long temp;
5907
5908                 s = bc_program_prep(&operand, &num);
5909                 if (s) goto err;
5910                 s = bc_num_ulong(num, &temp);
5911                 if (s) goto err;
5912
5913                 if (temp > BC_MAX_DIM) {
5914                         s = bc_error("array too long; must be [1, BC_DIM_MAX]");
5915                         goto err;
5916                 }
5917
5918                 r.d.id.idx = (size_t) temp;
5919                 bc_program_retire(&r, BC_RESULT_ARRAY_ELEM);
5920         }
5921
5922 err:
5923         if (s) free(r.d.id.name);
5924         return s;
5925 }
5926
5927 #if ENABLE_BC
5928 static BcStatus bc_program_incdec(char inst)
5929 {
5930         BcStatus s;
5931         BcResult *ptr, res, copy;
5932         BcNum *num = NULL;
5933         char inst2 = inst;
5934
5935         s = bc_program_prep(&ptr, &num);
5936         if (s) return s;
5937
5938         if (inst == BC_INST_INC_POST || inst == BC_INST_DEC_POST) {
5939                 copy.t = BC_RESULT_TEMP;
5940                 bc_num_init(&copy.d.n, num->len);
5941                 bc_num_copy(&copy.d.n, num);
5942         }
5943
5944         res.t = BC_RESULT_ONE;
5945         inst = inst == BC_INST_INC_PRE || inst == BC_INST_INC_POST ?
5946                    BC_INST_ASSIGN_PLUS :
5947                    BC_INST_ASSIGN_MINUS;
5948
5949         bc_vec_push(&G.prog.results, &res);
5950         bc_program_assign(inst);
5951
5952         if (inst2 == BC_INST_INC_POST || inst2 == BC_INST_DEC_POST) {
5953                 bc_vec_pop(&G.prog.results);
5954                 bc_vec_push(&G.prog.results, &copy);
5955         }
5956
5957         return s;
5958 }
5959
5960 static BcStatus bc_program_call(char *code, size_t *idx)
5961 {
5962         BcStatus s = BC_STATUS_SUCCESS;
5963         BcInstPtr ip;
5964         size_t i, nparams = bc_program_index(code, idx);
5965         BcFunc *func;
5966         BcId *a;
5967         BcResultData param;
5968         BcResult *arg;
5969
5970         ip.idx = 0;
5971         ip.func = bc_program_index(code, idx);
5972         func = bc_vec_item(&G.prog.fns, ip.func);
5973
5974         if (func->code.len == 0) {
5975                 return bc_error("undefined function");
5976         }
5977         if (nparams != func->nparams) {
5978                 return bc_error_fmt("function has %u parameters, but called with %u", func->nparams, nparams);
5979         }
5980         ip.len = G.prog.results.len - nparams;
5981
5982         for (i = 0; i < nparams; ++i) {
5983
5984                 a = bc_vec_item(&func->autos, nparams - 1 - i);
5985                 arg = bc_vec_top(&G.prog.results);
5986
5987                 if ((!a->idx) != (arg->t == BC_RESULT_ARRAY) || arg->t == BC_RESULT_STR)
5988                         return bc_error_variable_is_wrong_type();
5989
5990                 s = bc_program_copyToVar(a->name, a->idx);
5991                 if (s) return s;
5992         }
5993
5994         for (; i < func->autos.len; ++i) {
5995                 BcVec *v;
5996
5997                 a = bc_vec_item(&func->autos, i);
5998                 v = bc_program_search(a->name, a->idx);
5999
6000                 if (a->idx) {
6001                         bc_num_init(&param.n, BC_NUM_DEF_SIZE);
6002                         bc_vec_push(v, &param.n);
6003                 }
6004                 else {
6005                         bc_array_init(&param.v, true);
6006                         bc_vec_push(v, &param.v);
6007                 }
6008         }
6009
6010         bc_vec_push(&G.prog.stack, &ip);
6011
6012         return BC_STATUS_SUCCESS;
6013 }
6014
6015 static BcStatus bc_program_return(char inst)
6016 {
6017         BcStatus s;
6018         BcResult res;
6019         BcFunc *f;
6020         size_t i;
6021         BcInstPtr *ip = bc_vec_top(&G.prog.stack);
6022
6023         if (!BC_PROG_STACK(&G.prog.results, ip->len + inst == BC_INST_RET))
6024                 return bc_error_stack_has_too_few_elements();
6025
6026         f = bc_vec_item(&G.prog.fns, ip->func);
6027         res.t = BC_RESULT_TEMP;
6028
6029         if (inst == BC_INST_RET) {
6030
6031                 BcNum *num;
6032                 BcResult *operand = bc_vec_top(&G.prog.results);
6033
6034                 s = bc_program_num(operand, &num, false);
6035                 if (s) return s;
6036                 bc_num_init(&res.d.n, num->len);
6037                 bc_num_copy(&res.d.n, num);
6038         }
6039         else {
6040                 bc_num_init(&res.d.n, BC_NUM_DEF_SIZE);
6041                 bc_num_zero(&res.d.n);
6042         }
6043
6044         // We need to pop arguments as well, so this takes that into account.
6045         for (i = 0; i < f->autos.len; ++i) {
6046
6047                 BcVec *v;
6048                 BcId *a = bc_vec_item(&f->autos, i);
6049
6050                 v = bc_program_search(a->name, a->idx);
6051                 bc_vec_pop(v);
6052         }
6053
6054         bc_vec_npop(&G.prog.results, G.prog.results.len - ip->len);
6055         bc_vec_push(&G.prog.results, &res);
6056         bc_vec_pop(&G.prog.stack);
6057
6058         return BC_STATUS_SUCCESS;
6059 }
6060 #endif // ENABLE_BC
6061
6062 static unsigned long bc_program_scale(BcNum *n)
6063 {
6064         return (unsigned long) n->rdx;
6065 }
6066
6067 static unsigned long bc_program_len(BcNum *n)
6068 {
6069         unsigned long len = n->len;
6070         size_t i;
6071
6072         if (n->rdx != n->len) return len;
6073         for (i = n->len - 1; i < n->len && n->num[i] == 0; --len, --i);
6074
6075         return len;
6076 }
6077
6078 static BcStatus bc_program_builtin(char inst)
6079 {
6080         BcStatus s;
6081         BcResult *opnd;
6082         BcNum *num = NULL;
6083         BcResult res;
6084         bool len = inst == BC_INST_LENGTH;
6085
6086         if (!BC_PROG_STACK(&G.prog.results, 1))
6087                 return bc_error_stack_has_too_few_elements();
6088         opnd = bc_vec_top(&G.prog.results);
6089
6090         s = bc_program_num(opnd, &num, false);
6091         if (s) return s;
6092
6093 #if ENABLE_DC
6094         if (!BC_PROG_NUM(opnd, num) && !len)
6095                 return bc_error_variable_is_wrong_type();
6096 #endif
6097
6098         bc_num_init(&res.d.n, BC_NUM_DEF_SIZE);
6099
6100         if (inst == BC_INST_SQRT) s = bc_num_sqrt(num, &res.d.n, G.prog.scale);
6101 #if ENABLE_BC
6102         else if (len != 0 && opnd->t == BC_RESULT_ARRAY) {
6103                 bc_num_ulong2num(&res.d.n, (unsigned long) ((BcVec *) num)->len);
6104         }
6105 #endif
6106 #if ENABLE_DC
6107         else if (len != 0 && !BC_PROG_NUM(opnd, num)) {
6108
6109                 char **str;
6110                 size_t idx = opnd->t == BC_RESULT_STR ? opnd->d.id.idx : num->rdx;
6111
6112                 str = bc_vec_item(&G.prog.strs, idx);
6113                 bc_num_ulong2num(&res.d.n, strlen(*str));
6114         }
6115 #endif
6116         else {
6117                 BcProgramBuiltIn f = len ? bc_program_len : bc_program_scale;
6118                 bc_num_ulong2num(&res.d.n, f(num));
6119         }
6120
6121         bc_program_retire(&res, BC_RESULT_TEMP);
6122
6123         return s;
6124 }
6125
6126 #if ENABLE_DC
6127 static BcStatus bc_program_divmod(void)
6128 {
6129         BcStatus s;
6130         BcResult *opd1, *opd2, res, res2;
6131         BcNum *n1, *n2 = NULL;
6132
6133         s = bc_program_binOpPrep(&opd1, &n1, &opd2, &n2, false);
6134         if (s) return s;
6135
6136         bc_num_init(&res.d.n, BC_NUM_DEF_SIZE);
6137         bc_num_init(&res2.d.n, n2->len);
6138
6139         s = bc_num_divmod(n1, n2, &res2.d.n, &res.d.n, G.prog.scale);
6140         if (s) goto err;
6141
6142         bc_program_binOpRetire(&res2);
6143         res.t = BC_RESULT_TEMP;
6144         bc_vec_push(&G.prog.results, &res);
6145
6146         return s;
6147
6148 err:
6149         bc_num_free(&res2.d.n);
6150         bc_num_free(&res.d.n);
6151         return s;
6152 }
6153
6154 static BcStatus bc_program_modexp(void)
6155 {
6156         BcStatus s;
6157         BcResult *r1, *r2, *r3, res;
6158         BcNum *n1, *n2, *n3;
6159
6160         if (!BC_PROG_STACK(&G.prog.results, 3))
6161                 return bc_error_stack_has_too_few_elements();
6162         s = bc_program_binOpPrep(&r2, &n2, &r3, &n3, false);
6163         if (s) return s;
6164
6165         r1 = bc_vec_item_rev(&G.prog.results, 2);
6166         s = bc_program_num(r1, &n1, false);
6167         if (s) return s;
6168         if (!BC_PROG_NUM(r1, n1))
6169                 return bc_error_variable_is_wrong_type();
6170
6171         // Make sure that the values have their pointers updated, if necessary.
6172         if (r1->t == BC_RESULT_VAR || r1->t == BC_RESULT_ARRAY_ELEM) {
6173
6174                 if (r1->t == r2->t) {
6175                         s = bc_program_num(r2, &n2, false);
6176                         if (s) return s;
6177                 }
6178
6179                 if (r1->t == r3->t) {
6180                         s = bc_program_num(r3, &n3, false);
6181                         if (s) return s;
6182                 }
6183         }
6184
6185         bc_num_init(&res.d.n, n3->len);
6186         s = bc_num_modexp(n1, n2, n3, &res.d.n);
6187         if (s) goto err;
6188
6189         bc_vec_pop(&G.prog.results);
6190         bc_program_binOpRetire(&res);
6191
6192         return s;
6193
6194 err:
6195         bc_num_free(&res.d.n);
6196         return s;
6197 }
6198
6199 static void bc_program_stackLen(void)
6200 {
6201         BcResult res;
6202         size_t len = G.prog.results.len;
6203
6204         res.t = BC_RESULT_TEMP;
6205
6206         bc_num_init(&res.d.n, BC_NUM_DEF_SIZE);
6207         bc_num_ulong2num(&res.d.n, len);
6208         bc_vec_push(&G.prog.results, &res);
6209 }
6210
6211 static BcStatus bc_program_asciify(void)
6212 {
6213         BcStatus s;
6214         BcResult *r, res;
6215         BcNum *num = NULL, n;
6216         char *str, *str2, c;
6217         size_t len = G.prog.strs.len, idx;
6218         unsigned long val;
6219
6220         if (!BC_PROG_STACK(&G.prog.results, 1))
6221                 return bc_error_stack_has_too_few_elements();
6222         r = bc_vec_top(&G.prog.results);
6223
6224         s = bc_program_num(r, &num, false);
6225         if (s) return s;
6226
6227         if (BC_PROG_NUM(r, num)) {
6228
6229                 bc_num_init(&n, BC_NUM_DEF_SIZE);
6230                 bc_num_copy(&n, num);
6231                 bc_num_truncate(&n, n.rdx);
6232
6233                 s = bc_num_mod(&n, &G.prog.strmb, &n, 0);
6234                 if (s) goto num_err;
6235                 s = bc_num_ulong(&n, &val);
6236                 if (s) goto num_err;
6237
6238                 c = (char) val;
6239
6240                 bc_num_free(&n);
6241         }
6242         else {
6243                 idx = (r->t == BC_RESULT_STR) ? r->d.id.idx : num->rdx;
6244                 str2 = *((char **) bc_vec_item(&G.prog.strs, idx));
6245                 c = str2[0];
6246         }
6247
6248         str = xmalloc(2);
6249         str[0] = c;
6250         str[1] = '\0';
6251
6252         str2 = xstrdup(str);
6253         bc_program_addFunc(str2, &idx);
6254
6255         if (idx != len + BC_PROG_REQ_FUNCS) {
6256
6257                 for (idx = 0; idx < G.prog.strs.len; ++idx) {
6258                         if (!strcmp(*((char **) bc_vec_item(&G.prog.strs, idx)), str)) {
6259                                 len = idx;
6260                                 break;
6261                         }
6262                 }
6263
6264                 free(str);
6265         }
6266         else
6267                 bc_vec_push(&G.prog.strs, &str);
6268
6269         res.t = BC_RESULT_STR;
6270         res.d.id.idx = len;
6271         bc_vec_pop(&G.prog.results);
6272         bc_vec_push(&G.prog.results, &res);
6273
6274         return BC_STATUS_SUCCESS;
6275
6276 num_err:
6277         bc_num_free(&n);
6278         return s;
6279 }
6280
6281 static BcStatus bc_program_printStream(void)
6282 {
6283         BcStatus s;
6284         BcResult *r;
6285         BcNum *n = NULL;
6286         size_t idx;
6287         char *str;
6288
6289         if (!BC_PROG_STACK(&G.prog.results, 1))
6290                 return bc_error_stack_has_too_few_elements();
6291         r = bc_vec_top(&G.prog.results);
6292
6293         s = bc_program_num(r, &n, false);
6294         if (s) return s;
6295
6296         if (BC_PROG_NUM(r, n))
6297                 s = bc_num_stream(n, &G.prog.strmb, &G.prog.nchars, G.prog.len);
6298         else {
6299                 idx = (r->t == BC_RESULT_STR) ? r->d.id.idx : n->rdx;
6300                 str = *((char **) bc_vec_item(&G.prog.strs, idx));
6301                 printf("%s", str);
6302         }
6303
6304         return s;
6305 }
6306
6307 static BcStatus bc_program_nquit(void)
6308 {
6309         BcStatus s;
6310         BcResult *opnd;
6311         BcNum *num = NULL;
6312         unsigned long val;
6313
6314         s = bc_program_prep(&opnd, &num);
6315         if (s) return s;
6316         s = bc_num_ulong(num, &val);
6317         if (s) return s;
6318
6319         bc_vec_pop(&G.prog.results);
6320
6321         if (G.prog.stack.len < val)
6322                 return bc_error_stack_has_too_few_elements();
6323         if (G.prog.stack.len == val)
6324                 quit();
6325
6326         bc_vec_npop(&G.prog.stack, val);
6327
6328         return s;
6329 }
6330
6331 static BcStatus bc_program_execStr(char *code, size_t *bgn,
6332                                    bool cond)
6333 {
6334         BcStatus s = BC_STATUS_SUCCESS;
6335         BcResult *r;
6336         char **str;
6337         BcFunc *f;
6338         BcParse prs;
6339         BcInstPtr ip;
6340         size_t fidx, sidx;
6341         BcNum *n;
6342         bool exec;
6343
6344         if (!BC_PROG_STACK(&G.prog.results, 1))
6345                 return bc_error_stack_has_too_few_elements();
6346
6347         r = bc_vec_top(&G.prog.results);
6348
6349         if (cond) {
6350
6351                 char *name, *then_name = bc_program_name(code, bgn), *else_name = NULL;
6352
6353                 if (code[*bgn] == BC_PARSE_STREND)
6354                         (*bgn) += 1;
6355                 else
6356                         else_name = bc_program_name(code, bgn);
6357
6358                 exec = r->d.n.len != 0;
6359
6360                 if (exec)
6361                         name = then_name;
6362                 else if (else_name != NULL) {
6363                         exec = true;
6364                         name = else_name;
6365                 }
6366
6367                 if (exec) {
6368                         BcVec *v;
6369                         v = bc_program_search(name, true);
6370                         n = bc_vec_top(v);
6371                 }
6372
6373                 free(then_name);
6374                 free(else_name);
6375
6376                 if (!exec) goto exit;
6377                 if (!BC_PROG_STR(n)) {
6378                         s = bc_error_variable_is_wrong_type();
6379                         goto exit;
6380                 }
6381
6382                 sidx = n->rdx;
6383         }
6384         else {
6385
6386                 if (r->t == BC_RESULT_STR)
6387                         sidx = r->d.id.idx;
6388                 else if (r->t == BC_RESULT_VAR) {
6389                         s = bc_program_num(r, &n, false);
6390                         if (s || !BC_PROG_STR(n)) goto exit;
6391                         sidx = n->rdx;
6392                 }
6393                 else
6394                         goto exit;
6395         }
6396
6397         fidx = sidx + BC_PROG_REQ_FUNCS;
6398
6399         str = bc_vec_item(&G.prog.strs, sidx);
6400         f = bc_vec_item(&G.prog.fns, fidx);
6401
6402         if (f->code.len == 0) {
6403                 common_parse_init(&prs, fidx);
6404                 s = bc_parse_text(&prs, *str);
6405                 if (s) goto err;
6406                 s = common_parse_expr(&prs, BC_PARSE_NOCALL);
6407                 if (s) goto err;
6408
6409                 if (prs.l.t.t != BC_LEX_EOF) {
6410                         s = bc_error_bad_expression();
6411                         goto err;
6412                 }
6413
6414                 bc_parse_free(&prs);
6415         }
6416
6417         ip.idx = 0;
6418         ip.len = G.prog.results.len;
6419         ip.func = fidx;
6420
6421         bc_vec_pop(&G.prog.results);
6422         bc_vec_push(&G.prog.stack, &ip);
6423
6424         return BC_STATUS_SUCCESS;
6425
6426 err:
6427         bc_parse_free(&prs);
6428         f = bc_vec_item(&G.prog.fns, fidx);
6429         bc_vec_pop_all(&f->code);
6430 exit:
6431         bc_vec_pop(&G.prog.results);
6432         return s;
6433 }
6434 #endif // ENABLE_DC
6435
6436 static void bc_program_pushGlobal(char inst)
6437 {
6438         BcResult res;
6439         unsigned long val;
6440
6441         res.t = inst - BC_INST_IBASE + BC_RESULT_IBASE;
6442         if (inst == BC_INST_IBASE)
6443                 val = (unsigned long) G.prog.ib_t;
6444         else if (inst == BC_INST_SCALE)
6445                 val = (unsigned long) G.prog.scale;
6446         else
6447                 val = (unsigned long) G.prog.ob_t;
6448
6449         bc_num_init(&res.d.n, BC_NUM_DEF_SIZE);
6450         bc_num_ulong2num(&res.d.n, val);
6451         bc_vec_push(&G.prog.results, &res);
6452 }
6453
6454 static void bc_program_addFunc(char *name, size_t *idx)
6455 {
6456         BcId entry, *entry_ptr;
6457         BcFunc f;
6458         int inserted;
6459
6460         entry.name = name;
6461         entry.idx = G.prog.fns.len;
6462
6463         inserted = bc_map_insert(&G.prog.fn_map, &entry, idx);
6464         if (!inserted) free(name);
6465
6466         entry_ptr = bc_vec_item(&G.prog.fn_map, *idx);
6467         *idx = entry_ptr->idx;
6468
6469         if (!inserted) {
6470
6471                 BcFunc *func = bc_vec_item(&G.prog.fns, entry_ptr->idx);
6472
6473                 // We need to reset these, so the function can be repopulated.
6474                 func->nparams = 0;
6475                 bc_vec_pop_all(&func->autos);
6476                 bc_vec_pop_all(&func->code);
6477                 bc_vec_pop_all(&func->labels);
6478         }
6479         else {
6480                 bc_func_init(&f);
6481                 bc_vec_push(&G.prog.fns, &f);
6482         }
6483 }
6484
6485 // Called when parsing or execution detects a failure,
6486 // resets execution structures.
6487 static void bc_program_reset(void)
6488 {
6489         BcFunc *f;
6490         BcInstPtr *ip;
6491
6492         bc_vec_npop(&G.prog.stack, G.prog.stack.len - 1);
6493         bc_vec_pop_all(&G.prog.results);
6494
6495         f = bc_vec_item(&G.prog.fns, 0);
6496         ip = bc_vec_top(&G.prog.stack);
6497         ip->idx = f->code.len;
6498
6499         // If !tty, no need to check for ^C: we don't have ^C handler,
6500         // we would be killed by a signal and won't reach this place
6501 }
6502
6503 static BcStatus bc_program_exec(void)
6504 {
6505         BcStatus s = BC_STATUS_SUCCESS;
6506         size_t idx;
6507         BcResult r, *ptr;
6508         BcNum *num;
6509         BcInstPtr *ip = bc_vec_top(&G.prog.stack);
6510         BcFunc *func = bc_vec_item(&G.prog.fns, ip->func);
6511         char *code = func->code.v;
6512         bool cond = false;
6513
6514         while (!s && ip->idx < func->code.len) {
6515
6516                 char inst = code[(ip->idx)++];
6517
6518                 switch (inst) {
6519
6520 #if ENABLE_BC
6521                         case BC_INST_JUMP_ZERO:
6522                         {
6523                                 s = bc_program_prep(&ptr, &num);
6524                                 if (s) return s;
6525                                 cond = !bc_num_cmp(num, &G.prog.zero);
6526                                 bc_vec_pop(&G.prog.results);
6527                         }
6528                         // Fallthrough.
6529                         case BC_INST_JUMP:
6530                         {
6531                                 size_t *addr;
6532                                 idx = bc_program_index(code, &ip->idx);
6533                                 addr = bc_vec_item(&func->labels, idx);
6534                                 if (inst == BC_INST_JUMP || cond) ip->idx = *addr;
6535                                 break;
6536                         }
6537
6538                         case BC_INST_CALL:
6539                         {
6540                                 s = bc_program_call(code, &ip->idx);
6541                                 break;
6542                         }
6543
6544                         case BC_INST_INC_PRE:
6545                         case BC_INST_DEC_PRE:
6546                         case BC_INST_INC_POST:
6547                         case BC_INST_DEC_POST:
6548                         {
6549                                 s = bc_program_incdec(inst);
6550                                 break;
6551                         }
6552
6553                         case BC_INST_HALT:
6554                         {
6555                                 quit();
6556                                 break;
6557                         }
6558
6559                         case BC_INST_RET:
6560                         case BC_INST_RET0:
6561                         {
6562                                 s = bc_program_return(inst);
6563                                 break;
6564                         }
6565
6566                         case BC_INST_BOOL_OR:
6567                         case BC_INST_BOOL_AND:
6568 #endif // ENABLE_BC
6569                         case BC_INST_REL_EQ:
6570                         case BC_INST_REL_LE:
6571                         case BC_INST_REL_GE:
6572                         case BC_INST_REL_NE:
6573                         case BC_INST_REL_LT:
6574                         case BC_INST_REL_GT:
6575                         {
6576                                 s = bc_program_logical(inst);
6577                                 break;
6578                         }
6579
6580                         case BC_INST_READ:
6581                         {
6582                                 s = bc_program_read();
6583                                 break;
6584                         }
6585
6586                         case BC_INST_VAR:
6587                         {
6588                                 s = bc_program_pushVar(code, &ip->idx, false, false);
6589                                 break;
6590                         }
6591
6592                         case BC_INST_ARRAY_ELEM:
6593                         case BC_INST_ARRAY:
6594                         {
6595                                 s = bc_program_pushArray(code, &ip->idx, inst);
6596                                 break;
6597                         }
6598
6599                         case BC_INST_LAST:
6600                         {
6601                                 r.t = BC_RESULT_LAST;
6602                                 bc_vec_push(&G.prog.results, &r);
6603                                 break;
6604                         }
6605
6606                         case BC_INST_IBASE:
6607                         case BC_INST_SCALE:
6608                         case BC_INST_OBASE:
6609                         {
6610                                 bc_program_pushGlobal(inst);
6611                                 break;
6612                         }
6613
6614                         case BC_INST_SCALE_FUNC:
6615                         case BC_INST_LENGTH:
6616                         case BC_INST_SQRT:
6617                         {
6618                                 s = bc_program_builtin(inst);
6619                                 break;
6620                         }
6621
6622                         case BC_INST_NUM:
6623                         {
6624                                 r.t = BC_RESULT_CONSTANT;
6625                                 r.d.id.idx = bc_program_index(code, &ip->idx);
6626                                 bc_vec_push(&G.prog.results, &r);
6627                                 break;
6628                         }
6629
6630                         case BC_INST_POP:
6631                         {
6632                                 if (!BC_PROG_STACK(&G.prog.results, 1))
6633                                         s = bc_error_stack_has_too_few_elements();
6634                                 else
6635                                         bc_vec_pop(&G.prog.results);
6636                                 break;
6637                         }
6638
6639                         case BC_INST_POP_EXEC:
6640                         {
6641                                 bc_vec_pop(&G.prog.stack);
6642                                 break;
6643                         }
6644
6645                         case BC_INST_PRINT:
6646                         case BC_INST_PRINT_POP:
6647                         case BC_INST_PRINT_STR:
6648                         {
6649                                 s = bc_program_print(inst, 0);
6650                                 break;
6651                         }
6652
6653                         case BC_INST_STR:
6654                         {
6655                                 r.t = BC_RESULT_STR;
6656                                 r.d.id.idx = bc_program_index(code, &ip->idx);
6657                                 bc_vec_push(&G.prog.results, &r);
6658                                 break;
6659                         }
6660
6661                         case BC_INST_POWER:
6662                         case BC_INST_MULTIPLY:
6663                         case BC_INST_DIVIDE:
6664                         case BC_INST_MODULUS:
6665                         case BC_INST_PLUS:
6666                         case BC_INST_MINUS:
6667                         {
6668                                 s = bc_program_op(inst);
6669                                 break;
6670                         }
6671
6672                         case BC_INST_BOOL_NOT:
6673                         {
6674                                 s = bc_program_prep(&ptr, &num);
6675                                 if (s) return s;
6676
6677                                 bc_num_init(&r.d.n, BC_NUM_DEF_SIZE);
6678                                 (!bc_num_cmp(num, &G.prog.zero) ? bc_num_one : bc_num_zero)(&r.d.n);
6679                                 bc_program_retire(&r, BC_RESULT_TEMP);
6680
6681                                 break;
6682                         }
6683
6684                         case BC_INST_NEG:
6685                         {
6686                                 s = bc_program_negate();
6687                                 break;
6688                         }
6689
6690 #if ENABLE_BC
6691                         case BC_INST_ASSIGN_POWER:
6692                         case BC_INST_ASSIGN_MULTIPLY:
6693                         case BC_INST_ASSIGN_DIVIDE:
6694                         case BC_INST_ASSIGN_MODULUS:
6695                         case BC_INST_ASSIGN_PLUS:
6696                         case BC_INST_ASSIGN_MINUS:
6697 #endif
6698                         case BC_INST_ASSIGN:
6699                         {
6700                                 s = bc_program_assign(inst);
6701                                 break;
6702                         }
6703 #if ENABLE_DC
6704                         case BC_INST_MODEXP:
6705                         {
6706                                 s = bc_program_modexp();
6707                                 break;
6708                         }
6709
6710                         case BC_INST_DIVMOD:
6711                         {
6712                                 s = bc_program_divmod();
6713                                 break;
6714                         }
6715
6716                         case BC_INST_EXECUTE:
6717                         case BC_INST_EXEC_COND:
6718                         {
6719                                 cond = inst == BC_INST_EXEC_COND;
6720                                 s = bc_program_execStr(code, &ip->idx, cond);
6721                                 break;
6722                         }
6723
6724                         case BC_INST_PRINT_STACK:
6725                         {
6726                                 for (idx = 0; !s && idx < G.prog.results.len; ++idx)
6727                                         s = bc_program_print(BC_INST_PRINT, idx);
6728                                 break;
6729                         }
6730
6731                         case BC_INST_CLEAR_STACK:
6732                         {
6733                                 bc_vec_pop_all(&G.prog.results);
6734                                 break;
6735                         }
6736
6737                         case BC_INST_STACK_LEN:
6738                         {
6739                                 bc_program_stackLen();
6740                                 break;
6741                         }
6742
6743                         case BC_INST_DUPLICATE:
6744                         {
6745                                 if (!BC_PROG_STACK(&G.prog.results, 1))
6746                                         return bc_error_stack_has_too_few_elements();
6747                                 ptr = bc_vec_top(&G.prog.results);
6748                                 bc_result_copy(&r, ptr);
6749                                 bc_vec_push(&G.prog.results, &r);
6750                                 break;
6751                         }
6752
6753                         case BC_INST_SWAP:
6754                         {
6755                                 BcResult *ptr2;
6756
6757                                 if (!BC_PROG_STACK(&G.prog.results, 2))
6758                                         return bc_error_stack_has_too_few_elements();
6759
6760                                 ptr = bc_vec_item_rev(&G.prog.results, 0);
6761                                 ptr2 = bc_vec_item_rev(&G.prog.results, 1);
6762                                 memcpy(&r, ptr, sizeof(BcResult));
6763                                 memcpy(ptr, ptr2, sizeof(BcResult));
6764                                 memcpy(ptr2, &r, sizeof(BcResult));
6765
6766                                 break;
6767                         }
6768
6769                         case BC_INST_ASCIIFY:
6770                         {
6771                                 s = bc_program_asciify();
6772                                 break;
6773                         }
6774
6775                         case BC_INST_PRINT_STREAM:
6776                         {
6777                                 s = bc_program_printStream();
6778                                 break;
6779                         }
6780
6781                         case BC_INST_LOAD:
6782                         case BC_INST_PUSH_VAR:
6783                         {
6784                                 bool copy = inst == BC_INST_LOAD;
6785                                 s = bc_program_pushVar(code, &ip->idx, true, copy);
6786                                 break;
6787                         }
6788
6789                         case BC_INST_PUSH_TO_VAR:
6790                         {
6791                                 char *name = bc_program_name(code, &ip->idx);
6792                                 s = bc_program_copyToVar(name, true);
6793                                 free(name);
6794                                 break;
6795                         }
6796
6797                         case BC_INST_QUIT:
6798                         {
6799                                 if (G.prog.stack.len <= 2)
6800                                         quit();
6801                                 bc_vec_npop(&G.prog.stack, 2);
6802                                 break;
6803                         }
6804
6805                         case BC_INST_NQUIT:
6806                         {
6807                                 s = bc_program_nquit();
6808                                 break;
6809                         }
6810 #endif // ENABLE_DC
6811                 }
6812
6813                 if (s || G_interrupt) {
6814                         bc_program_reset();
6815                         break;
6816                 }
6817
6818                 // If the stack has changed, pointers may be invalid.
6819                 ip = bc_vec_top(&G.prog.stack);
6820                 func = bc_vec_item(&G.prog.fns, ip->func);
6821                 code = func->code.v;
6822         }
6823
6824         return s;
6825 }
6826
6827 static void bc_vm_info(void)
6828 {
6829         printf("%s "BB_VER"\n"
6830                 "Copyright (c) 2018 Gavin D. Howard and contributors\n"
6831                 "Report bugs at: https://github.com/gavinhoward/bc\n"
6832                 "This is free software with ABSOLUTELY NO WARRANTY\n"
6833         , applet_name);
6834 }
6835
6836 #if ENABLE_BC
6837 static void bc_vm_envArgs(void)
6838 {
6839         static const char* const bc_args_env_name = "BC_ENV_ARGS";
6840
6841         BcVec v;
6842         char *env_args = getenv(bc_args_env_name), *buf;
6843
6844         if (!env_args) return;
6845
6846         G.env_args = xstrdup(env_args);
6847         buf = G.env_args;
6848
6849         bc_vec_init(&v, sizeof(char *), NULL);
6850         bc_vec_push(&v, &bc_args_env_name);
6851
6852         while (*buf != 0) {
6853                 if (!isspace(*buf)) {
6854                         bc_vec_push(&v, &buf);
6855                         while (*buf != 0 && !isspace(*buf)) ++buf;
6856                         if (*buf != 0) (*(buf++)) = '\0';
6857                 }
6858                 else
6859                         ++buf;
6860         }
6861
6862         bc_args((int) v.len, (char **) v.v);
6863
6864         bc_vec_free(&v);
6865 }
6866 #endif // ENABLE_BC
6867
6868 static size_t bc_vm_envLen(const char *var)
6869 {
6870         char *lenv = getenv(var);
6871         size_t i, len = BC_NUM_PRINT_WIDTH;
6872         int num;
6873
6874         if (!lenv) return len;
6875
6876         len = strlen(lenv);
6877
6878         for (num = 1, i = 0; num && i < len; ++i) num = isdigit(lenv[i]);
6879         if (num) {
6880                 len = (size_t) atoi(lenv) - 1;
6881                 if (len < 2 || len >= INT32_MAX) len = BC_NUM_PRINT_WIDTH;
6882         }
6883         else
6884                 len = BC_NUM_PRINT_WIDTH;
6885
6886         return len;
6887 }
6888
6889 static BcStatus bc_vm_process(const char *text)
6890 {
6891         BcStatus s = bc_parse_text(&G.prs, text);
6892
6893         if (s) return s;
6894
6895         while (G.prs.l.t.t != BC_LEX_EOF) {
6896                 s = G.prs.parse(&G.prs);
6897                 if (s) return s;
6898         }
6899
6900         if (BC_PARSE_CAN_EXEC(&G.prs)) {
6901                 s = bc_program_exec();
6902                 fflush_and_check();
6903                 if (s)
6904                         bc_program_reset();
6905         }
6906
6907         return s;
6908 }
6909
6910 static BcStatus bc_vm_file(const char *file)
6911 {
6912         const char *sv_file;
6913         char *data;
6914         BcStatus s;
6915         BcFunc *main_func;
6916         BcInstPtr *ip;
6917
6918         data = bc_read_file(file);
6919         if (!data) return bc_error_fmt("file '%s' is not text", file);
6920
6921         sv_file = G.prog.file;
6922         G.prog.file = file;
6923         bc_lex_file(&G.prs.l);
6924         s = bc_vm_process(data);
6925         if (s) goto err;
6926
6927         main_func = bc_vec_item(&G.prog.fns, BC_PROG_MAIN);
6928         ip = bc_vec_item(&G.prog.stack, 0);
6929
6930         if (main_func->code.len < ip->idx)
6931                 s = bc_error_fmt("file '%s' is not executable", file);
6932
6933 err:
6934         G.prog.file = sv_file;
6935         free(data);
6936         return s;
6937 }
6938
6939 static BcStatus bc_vm_stdin(void)
6940 {
6941         BcStatus s;
6942         BcVec buf, buffer;
6943         size_t len, i, str = 0;
6944         bool comment = false;
6945
6946         G.prog.file = NULL;
6947         bc_lex_file(&G.prs.l);
6948
6949         bc_char_vec_init(&buffer);
6950         bc_char_vec_init(&buf);
6951         bc_vec_pushZeroByte(&buffer);
6952
6953         // This loop is complex because the vm tries not to send any lines that end
6954         // with a backslash to the parser. The reason for that is because the parser
6955         // treats a backslash+newline combo as whitespace, per the bc spec. In that
6956         // case, and for strings and comments, the parser will expect more stuff.
6957         while (!G.eof && (s = bc_read_line(&buf, ">>> ")) == BC_STATUS_SUCCESS) {
6958
6959                 char *string = buf.v;
6960
6961                 len = buf.len - 1;
6962
6963                 if (len == 1) {
6964                         if (str && buf.v[0] == G.send)
6965                                 str -= 1;
6966                         else if (buf.v[0] == G.sbgn)
6967                                 str += 1;
6968                 }
6969                 else if (len > 1 || comment) {
6970
6971                         for (i = 0; i < len; ++i) {
6972
6973                                 bool notend = len > i + 1;
6974                                 char c = string[i];
6975
6976                                 if (i - 1 > len || string[i - 1] != '\\') {
6977                                         if (G.sbgn == G.send)
6978                                                 str ^= c == G.sbgn;
6979                                         else if (c == G.send)
6980                                                 str -= 1;
6981                                         else if (c == G.sbgn)
6982                                                 str += 1;
6983                                 }
6984
6985                                 if (c == '/' && notend && !comment && string[i + 1] == '*') {
6986                                         comment = true;
6987                                         break;
6988                                 }
6989                                 else if (c == '*' && notend && comment && string[i + 1] == '/')
6990                                         comment = false;
6991                         }
6992
6993                         if (str || comment || string[len - 2] == '\\') {
6994                                 bc_vec_concat(&buffer, buf.v);
6995                                 continue;
6996                         }
6997                 }
6998
6999                 bc_vec_concat(&buffer, buf.v);
7000                 s = bc_vm_process(buffer.v);
7001                 if (s) {
7002                         fflush_and_check();
7003                         fputs("ready for more input\n", stderr);
7004                 }
7005
7006                 bc_vec_pop_all(&buffer);
7007         }
7008
7009         if (str) {
7010                 s = bc_error("string end could not be found");
7011         }
7012         else if (comment) {
7013                 s = bc_error("comment end could not be found");
7014         }
7015
7016         bc_vec_free(&buf);
7017         bc_vec_free(&buffer);
7018         return s;
7019 }
7020
7021 #if ENABLE_BC
7022 static const char bc_lib[] = {
7023         "scale=20"
7024 "\n"    "define e(x){"
7025 "\n"            "auto b,s,n,r,d,i,p,f,v"
7026 "\n"            "b=ibase"
7027 "\n"            "ibase=A"
7028 "\n"            "if(x<0){"
7029 "\n"                    "n=1"
7030 "\n"                    "x=-x"
7031 "\n"            "}"
7032 "\n"            "s=scale"
7033 "\n"            "r=6+s+0.44*x"
7034 "\n"            "scale=scale(x)+1"
7035 "\n"            "while(x>1){"
7036 "\n"                    "d+=1"
7037 "\n"                    "x/=2"
7038 "\n"                    "scale+=1"
7039 "\n"            "}"
7040 "\n"            "scale=r"
7041 "\n"            "r=x+1"
7042 "\n"            "p=x"
7043 "\n"            "f=v=1"
7044 "\n"            "for(i=2;v!=0;++i){"
7045 "\n"                    "p*=x"
7046 "\n"                    "f*=i"
7047 "\n"                    "v=p/f"
7048 "\n"                    "r+=v"
7049 "\n"            "}"
7050 "\n"            "while((d--)!=0)r*=r"
7051 "\n"            "scale=s"
7052 "\n"            "ibase=b"
7053 "\n"            "if(n!=0)return(1/r)"
7054 "\n"            "return(r/1)"
7055 "\n"    "}"
7056 "\n"    "define l(x){"
7057 "\n"            "auto b,s,r,p,a,q,i,v"
7058 "\n"            "b=ibase"
7059 "\n"            "ibase=A"
7060 "\n"            "if(x<=0){"
7061 "\n"                    "r=(1-10^scale)/1"
7062 "\n"                    "ibase=b"
7063 "\n"                    "return(r)"
7064 "\n"            "}"
7065 "\n"            "s=scale"
7066 "\n"            "scale+=6"
7067 "\n"            "p=2"
7068 "\n"            "while(x>=2){"
7069 "\n"                    "p*=2"
7070 "\n"                    "x=sqrt(x)"
7071 "\n"            "}"
7072 "\n"            "while(x<=0.5){"
7073 "\n"                    "p*=2"
7074 "\n"                    "x=sqrt(x)"
7075 "\n"            "}"
7076 "\n"            "r=a=(x-1)/(x+1)"
7077 "\n"            "q=a*a"
7078 "\n"                    "v=1"
7079 "\n"            "for(i=3;v!=0;i+=2){"
7080 "\n"                    "a*=q"
7081 "\n"                    "v=a/i"
7082 "\n"                    "r+=v"
7083 "\n"            "}"
7084 "\n"            "r*=p"
7085 "\n"            "scale=s"
7086 "\n"            "ibase=b"
7087 "\n"            "return(r/1)"
7088 "\n"    "}"
7089 "\n"    "define s(x){"
7090 "\n"            "auto b,s,r,n,a,q,i"
7091 "\n"            "b=ibase"
7092 "\n"            "ibase=A"
7093 "\n"            "s=scale"
7094 "\n"            "scale=1.1*s+2"
7095 "\n"            "a=a(1)"
7096 "\n"            "if(x<0){"
7097 "\n"                    "n=1"
7098 "\n"                    "x=-x"
7099 "\n"            "}"
7100 "\n"            "scale=0"
7101 "\n"            "q=(x/a+2)/4"
7102 "\n"            "x=x-4*q*a"
7103 "\n"            "if(q%2!=0)x=-x"
7104 "\n"            "scale=s+2"
7105 "\n"            "r=a=x"
7106 "\n"            "q=-x*x"
7107 "\n"            "for(i=3;a!=0;i+=2){"
7108 "\n"                    "a*=q/(i*(i-1))"
7109 "\n"                    "r+=a"
7110 "\n"            "}"
7111 "\n"            "scale=s"
7112 "\n"            "ibase=b"
7113 "\n"            "if(n!=0)return(-r/1)"
7114 "\n"            "return(r/1)"
7115 "\n"    "}"
7116 "\n"    "define c(x){"
7117 "\n"            "auto b,s"
7118 "\n"            "b=ibase"
7119 "\n"            "ibase=A"
7120 "\n"            "s=scale"
7121 "\n"            "scale*=1.2"
7122 "\n"            "x=s(2*a(1)+x)"
7123 "\n"            "scale=s"
7124 "\n"            "ibase=b"
7125 "\n"            "return(x/1)"
7126 "\n"    "}"
7127 "\n"    "define a(x){"
7128 "\n"            "auto b,s,r,n,a,m,t,f,i,u"
7129 "\n"            "b=ibase"
7130 "\n"            "ibase=A"
7131 "\n"            "n=1"
7132 "\n"            "if(x<0){"
7133 "\n"                    "n=-1"
7134 "\n"                    "x=-x"
7135 "\n"            "}"
7136 "\n"            "if(x==1){"
7137 "\n"                    "if(scale<65){"
7138 "\n"                            "return(.7853981633974483096156608458198757210492923498437764552437361480/n)"
7139 "\n"                    "}"
7140 "\n"            "}"
7141 "\n"            "if(x==.2){"
7142 "\n"                    "if(scale<65){"
7143 "\n"                            "return(.1973955598498807583700497651947902934475851037878521015176889402/n)"
7144 "\n"                    "}"
7145 "\n"            "}"
7146 "\n"            "s=scale"
7147 "\n"            "if(x>.2){"
7148 "\n"                    "scale+=5"
7149 "\n"                    "a=a(.2)"
7150 "\n"            "}"
7151 "\n"            "scale=s+3"
7152 "\n"            "while(x>.2){"
7153 "\n"                    "m+=1"
7154 "\n"                    "x=(x-.2)/(1+.2*x)"
7155 "\n"            "}"
7156 "\n"            "r=u=x"
7157 "\n"            "f=-x*x"
7158 "\n"            "t=1"
7159 "\n"            "for(i=3;t!=0;i+=2){"
7160 "\n"                    "u*=f"
7161 "\n"                    "t=u/i"
7162 "\n"                    "r+=t"
7163 "\n"            "}"
7164 "\n"            "scale=s"
7165 "\n"            "ibase=b"
7166 "\n"            "return((m*a+r)/n)"
7167 "\n"    "}"
7168 "\n"    "define j(n,x){"
7169 "\n"            "auto b,s,o,a,i,v,f"
7170 "\n"            "b=ibase"
7171 "\n"            "ibase=A"
7172 "\n"            "s=scale"
7173 "\n"            "scale=0"
7174 "\n"            "n/=1"
7175 "\n"            "if(n<0){"
7176 "\n"                    "n=-n"
7177 "\n"                    "if(n%2==1)o=1"
7178 "\n"            "}"
7179 "\n"            "a=1"
7180 "\n"            "for(i=2;i<=n;++i)a*=i"
7181 "\n"            "scale=1.5*s"
7182 "\n"            "a=(x^n)/2^n/a"
7183 "\n"            "r=v=1"
7184 "\n"            "f=-x*x/4"
7185 "\n"            "scale=scale+length(a)-scale(a)"
7186 "\n"            "for(i=1;v!=0;++i){"
7187 "\n"                    "v=v*f/i/(n+i)"
7188 "\n"                    "r+=v"
7189 "\n"            "}"
7190 "\n"            "scale=s"
7191 "\n"            "ibase=b"
7192 "\n"            "if(o!=0)a=-a"
7193 "\n"            "return(a*r/1)"
7194 "\n"    "}"
7195 };
7196 #endif // ENABLE_BC
7197
7198 static BcStatus bc_vm_exec(void)
7199 {
7200         BcStatus s = BC_STATUS_SUCCESS;
7201         size_t i;
7202
7203 #if ENABLE_BC
7204         if (option_mask32 & BC_FLAG_L) {
7205
7206                 // We know that internal library is not buggy,
7207                 // thus error checking is normally disabled.
7208 # define DEBUG_LIB 0
7209                 bc_lex_file(&G.prs.l);
7210                 s = bc_parse_text(&G.prs, bc_lib);
7211                 if (DEBUG_LIB && s) return s;
7212
7213                 while (G.prs.l.t.t != BC_LEX_EOF) {
7214                         s = G.prs.parse(&G.prs);
7215                         if (DEBUG_LIB && s) return s;
7216                 }
7217                 s = bc_program_exec();
7218                 if (DEBUG_LIB && s) return s;
7219         }
7220 #endif
7221
7222         for (i = 0; !s && i < G.files.len; ++i)
7223                 s = bc_vm_file(*((char **) bc_vec_item(&G.files, i)));
7224         if (s) {
7225                 fflush_and_check();
7226                 fputs("ready for more input\n", stderr);
7227         }
7228
7229         if (IS_BC || !G.files.len)
7230                 s = bc_vm_stdin();
7231         if (!s && !BC_PARSE_CAN_EXEC(&G.prs))
7232                 s = bc_vm_process("");
7233
7234         return s;
7235 }
7236
7237 #if ENABLE_FEATURE_CLEAN_UP
7238 static void bc_program_free()
7239 {
7240         bc_num_free(&G.prog.ib);
7241         bc_num_free(&G.prog.ob);
7242         bc_num_free(&G.prog.hexb);
7243 # if ENABLE_DC
7244         bc_num_free(&G.prog.strmb);
7245 # endif
7246         bc_vec_free(&G.prog.fns);
7247         bc_vec_free(&G.prog.fn_map);
7248         bc_vec_free(&G.prog.vars);
7249         bc_vec_free(&G.prog.var_map);
7250         bc_vec_free(&G.prog.arrs);
7251         bc_vec_free(&G.prog.arr_map);
7252         bc_vec_free(&G.prog.strs);
7253         bc_vec_free(&G.prog.consts);
7254         bc_vec_free(&G.prog.results);
7255         bc_vec_free(&G.prog.stack);
7256         bc_num_free(&G.prog.last);
7257         bc_num_free(&G.prog.zero);
7258         bc_num_free(&G.prog.one);
7259 }
7260
7261 static void bc_vm_free(void)
7262 {
7263         bc_vec_free(&G.files);
7264         bc_program_free();
7265         bc_parse_free(&G.prs);
7266         free(G.env_args);
7267 }
7268 #endif
7269
7270 static void bc_program_init(size_t line_len)
7271 {
7272         size_t idx;
7273         BcInstPtr ip;
7274
7275         /* memset(&G.prog, 0, sizeof(G.prog)); - already is */
7276         memset(&ip, 0, sizeof(BcInstPtr));
7277
7278         /* G.prog.nchars = G.prog.scale = 0; - already is */
7279         G.prog.len = line_len;
7280
7281         bc_num_init(&G.prog.ib, BC_NUM_DEF_SIZE);
7282         bc_num_ten(&G.prog.ib);
7283         G.prog.ib_t = 10;
7284
7285         bc_num_init(&G.prog.ob, BC_NUM_DEF_SIZE);
7286         bc_num_ten(&G.prog.ob);
7287         G.prog.ob_t = 10;
7288
7289         bc_num_init(&G.prog.hexb, BC_NUM_DEF_SIZE);
7290         bc_num_ten(&G.prog.hexb);
7291         G.prog.hexb.num[0] = 6;
7292
7293 #if ENABLE_DC
7294         bc_num_init(&G.prog.strmb, BC_NUM_DEF_SIZE);
7295         bc_num_ulong2num(&G.prog.strmb, UCHAR_MAX + 1);
7296 #endif
7297
7298         bc_num_init(&G.prog.last, BC_NUM_DEF_SIZE);
7299         bc_num_zero(&G.prog.last);
7300
7301         bc_num_init(&G.prog.zero, BC_NUM_DEF_SIZE);
7302         bc_num_zero(&G.prog.zero);
7303
7304         bc_num_init(&G.prog.one, BC_NUM_DEF_SIZE);
7305         bc_num_one(&G.prog.one);
7306
7307         bc_vec_init(&G.prog.fns, sizeof(BcFunc), bc_func_free);
7308         bc_vec_init(&G.prog.fn_map, sizeof(BcId), bc_id_free);
7309
7310         bc_program_addFunc(xstrdup("(main)"), &idx);
7311         bc_program_addFunc(xstrdup("(read)"), &idx);
7312
7313         bc_vec_init(&G.prog.vars, sizeof(BcVec), bc_vec_free);
7314         bc_vec_init(&G.prog.var_map, sizeof(BcId), bc_id_free);
7315
7316         bc_vec_init(&G.prog.arrs, sizeof(BcVec), bc_vec_free);
7317         bc_vec_init(&G.prog.arr_map, sizeof(BcId), bc_id_free);
7318
7319         bc_vec_init(&G.prog.strs, sizeof(char *), bc_string_free);
7320         bc_vec_init(&G.prog.consts, sizeof(char *), bc_string_free);
7321         bc_vec_init(&G.prog.results, sizeof(BcResult), bc_result_free);
7322         bc_vec_init(&G.prog.stack, sizeof(BcInstPtr), NULL);
7323         bc_vec_push(&G.prog.stack, &ip);
7324 }
7325
7326 static void bc_vm_init(const char *env_len)
7327 {
7328         size_t len = bc_vm_envLen(env_len);
7329
7330         bc_vec_init(&G.files, sizeof(char *), NULL);
7331
7332         if (IS_BC) {
7333                 bc_vm_envArgs();
7334         }
7335
7336         bc_program_init(len);
7337         if (IS_BC) {
7338                 bc_parse_init(&G.prs, BC_PROG_MAIN);
7339         } else {
7340                 dc_parse_init(&G.prs, BC_PROG_MAIN);
7341         }
7342 }
7343
7344 static BcStatus bc_vm_run(int argc, char *argv[],
7345                           const char *env_len)
7346 {
7347         BcStatus st;
7348
7349         bc_vm_init(env_len);
7350         bc_args(argc, argv);
7351
7352         G.ttyin = isatty(0);
7353
7354         if (G.ttyin) {
7355 #if ENABLE_FEATURE_BC_SIGNALS
7356                 // With SA_RESTART, most system calls will restart
7357                 // (IOW: they won't fail with EINTR).
7358                 // In particular, this means ^C won't cause
7359                 // stdout to get into "error state" if SIGINT hits
7360                 // within write() syscall.
7361                 // The downside is that ^C while line input is taken
7362                 // will only be handled after [Enter] since read()
7363                 // from stdin is not interrupted by ^C either,
7364                 // it restarts, thus fgetc() does not return on ^C.
7365                 signal_SA_RESTART_empty_mask(SIGINT, record_signo);
7366
7367                 // Without SA_RESTART, this exhibits a bug:
7368                 // "while (1) print 1" and try ^C-ing it.
7369                 // Intermittently, instead of returning to input line,
7370                 // you'll get "output error: Interrupted system call"
7371                 // and exit.
7372                 //signal_no_SA_RESTART_empty_mask(SIGINT, record_signo);
7373 #endif
7374                 if (!(option_mask32 & BC_FLAG_Q))
7375                         bc_vm_info();
7376         }
7377         st = bc_vm_exec();
7378
7379 #if ENABLE_FEATURE_CLEAN_UP
7380         bc_vm_free();
7381 #endif
7382         return st;
7383 }
7384
7385 #if ENABLE_BC
7386 int bc_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
7387 int bc_main(int argc, char **argv)
7388 {
7389         INIT_G();
7390         G.sbgn = G.send = '"';
7391
7392         return bc_vm_run(argc, argv, "BC_LINE_LENGTH");
7393 }
7394 #endif
7395
7396 #if ENABLE_DC
7397 int dc_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
7398 int dc_main(int argc, char **argv)
7399 {
7400         INIT_G();
7401         G.sbgn = '[';
7402         G.send = ']';
7403
7404         return bc_vm_run(argc, argv, "DC_LINE_LENGTH");
7405 }
7406 #endif