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         size_t max = BC_MAX(a->len, b->len), max2 = (max + 1) / 2;
1643         BcNum l1, h1, l2, h2, m2, m1, z0, z1, z2, temp;
1644         bool aone;
1645
1646         if (a->len == 0 || b->len == 0) {
1647                 bc_num_zero(c);
1648                 return BC_STATUS_SUCCESS;
1649         }
1650         aone = BC_NUM_ONE(a);
1651         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                 size_t i, j, len;
1660                 unsigned carry;
1661
1662                 bc_num_expand(c, a->len + b->len + 1);
1663
1664                 memset(c->num, 0, sizeof(BcDig) * c->cap);
1665                 c->len = len = 0;
1666
1667                 for (i = 0; i < b->len; ++i) {
1668
1669                         carry = 0;
1670                         for (j = 0; j < a->len; ++j) {
1671                                 unsigned in = c->num[i + j];
1672                                 in += ((unsigned) a->num[j]) * ((unsigned) b->num[i]) + carry;
1673                                 // note: compilers prefer _unsigned_ div/const
1674                                 carry = in / 10;
1675                                 c->num[i + j] = (BcDig)(in % 10);
1676                         }
1677
1678                         c->num[i + j] += (BcDig) carry;
1679                         len = BC_MAX(len, i + j + !!carry);
1680
1681                         // a=2^1000000
1682                         // a*a <- without check below, this will not be interruptible
1683                         if (G_interrupt) return BC_STATUS_FAILURE;
1684                 }
1685
1686                 c->len = len;
1687
1688                 return BC_STATUS_SUCCESS;
1689         }
1690
1691         bc_num_init(&l1, max);
1692         bc_num_init(&h1, max);
1693         bc_num_init(&l2, max);
1694         bc_num_init(&h2, max);
1695         bc_num_init(&m1, max);
1696         bc_num_init(&m2, max);
1697         bc_num_init(&z0, max);
1698         bc_num_init(&z1, max);
1699         bc_num_init(&z2, max);
1700         bc_num_init(&temp, max + max);
1701
1702         bc_num_split(a, max2, &l1, &h1);
1703         bc_num_split(b, max2, &l2, &h2);
1704
1705         s = bc_num_add(&h1, &l1, &m1, 0);
1706         if (s) goto err;
1707         s = bc_num_add(&h2, &l2, &m2, 0);
1708         if (s) goto err;
1709
1710         s = bc_num_k(&h1, &h2, &z0);
1711         if (s) goto err;
1712         s = bc_num_k(&m1, &m2, &z1);
1713         if (s) goto err;
1714         s = bc_num_k(&l1, &l2, &z2);
1715         if (s) goto err;
1716
1717         s = bc_num_sub(&z1, &z0, &temp, 0);
1718         if (s) goto err;
1719         s = bc_num_sub(&temp, &z2, &z1, 0);
1720         if (s) goto err;
1721
1722         s = bc_num_shift(&z0, max2 * 2);
1723         if (s) goto err;
1724         s = bc_num_shift(&z1, max2);
1725         if (s) goto err;
1726         s = bc_num_add(&z0, &z1, &temp, 0);
1727         if (s) goto err;
1728         s = bc_num_add(&temp, &z2, c, 0);
1729
1730 err:
1731         bc_num_free(&temp);
1732         bc_num_free(&z2);
1733         bc_num_free(&z1);
1734         bc_num_free(&z0);
1735         bc_num_free(&m2);
1736         bc_num_free(&m1);
1737         bc_num_free(&h2);
1738         bc_num_free(&l2);
1739         bc_num_free(&h1);
1740         bc_num_free(&l1);
1741         return s;
1742 }
1743
1744 static BcStatus bc_num_m(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale)
1745 {
1746         BcStatus s;
1747         BcNum cpa, cpb;
1748         size_t maxrdx = BC_MAX(a->rdx, b->rdx);
1749
1750         scale = BC_MAX(scale, a->rdx);
1751         scale = BC_MAX(scale, b->rdx);
1752         scale = BC_MIN(a->rdx + b->rdx, scale);
1753         maxrdx = BC_MAX(maxrdx, scale);
1754
1755         bc_num_init(&cpa, a->len);
1756         bc_num_init(&cpb, b->len);
1757
1758         bc_num_copy(&cpa, a);
1759         bc_num_copy(&cpb, b);
1760         cpa.neg = cpb.neg = false;
1761
1762         s = bc_num_shift(&cpa, maxrdx);
1763         if (s) goto err;
1764         s = bc_num_shift(&cpb, maxrdx);
1765         if (s) goto err;
1766         s = bc_num_k(&cpa, &cpb, c);
1767         if (s) goto err;
1768
1769         maxrdx += scale;
1770         bc_num_expand(c, c->len + maxrdx);
1771
1772         if (c->len < maxrdx) {
1773                 memset(c->num + c->len, 0, (c->cap - c->len) * sizeof(BcDig));
1774                 c->len += maxrdx;
1775         }
1776
1777         c->rdx = maxrdx;
1778         bc_num_retireMul(c, scale, a->neg, b->neg);
1779
1780 err:
1781         bc_num_free(&cpb);
1782         bc_num_free(&cpa);
1783         return s;
1784 }
1785
1786 static BcStatus bc_num_d(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale)
1787 {
1788         BcStatus s = BC_STATUS_SUCCESS;
1789         BcDig *n, *p, q;
1790         size_t len, end, i;
1791         BcNum cp;
1792         bool zero = true;
1793
1794         if (b->len == 0)
1795                 return bc_error("divide by zero");
1796         else if (a->len == 0) {
1797                 bc_num_setToZero(c, scale);
1798                 return BC_STATUS_SUCCESS;
1799         }
1800         else if (BC_NUM_ONE(b)) {
1801                 bc_num_copy(c, a);
1802                 bc_num_retireMul(c, scale, a->neg, b->neg);
1803                 return BC_STATUS_SUCCESS;
1804         }
1805
1806         bc_num_init(&cp, BC_NUM_MREQ(a, b, scale));
1807         bc_num_copy(&cp, a);
1808         len = b->len;
1809
1810         if (len > cp.len) {
1811                 bc_num_expand(&cp, len + 2);
1812                 bc_num_extend(&cp, len - cp.len);
1813         }
1814
1815         if (b->rdx > cp.rdx) bc_num_extend(&cp, b->rdx - cp.rdx);
1816         cp.rdx -= b->rdx;
1817         if (scale > cp.rdx) bc_num_extend(&cp, scale - cp.rdx);
1818
1819         if (b->rdx == b->len) {
1820                 for (i = 0; zero && i < len; ++i) zero = !b->num[len - i - 1];
1821                 len -= i - 1;
1822         }
1823
1824         if (cp.cap == cp.len) bc_num_expand(&cp, cp.len + 1);
1825
1826         // We want an extra zero in front to make things simpler.
1827         cp.num[cp.len++] = 0;
1828         end = cp.len - len;
1829
1830         bc_num_expand(c, cp.len);
1831
1832         bc_num_zero(c);
1833         memset(c->num + end, 0, (c->cap - end) * sizeof(BcDig));
1834         c->rdx = cp.rdx;
1835         c->len = cp.len;
1836         p = b->num;
1837
1838         for (i = end - 1; !s && i < end; --i) {
1839                 n = cp.num + i;
1840                 for (q = 0; (!s && n[len] != 0) || bc_num_compare(n, p, len) >= 0; ++q)
1841                         bc_num_subArrays(n, p, len);
1842                 c->num[i] = q;
1843                 // a=2^100000
1844                 // scale=40000
1845                 // 1/a <- without check below, this will not be interruptible
1846                 if (G_interrupt) {
1847                         s = BC_STATUS_FAILURE;
1848                         break;
1849                 }
1850         }
1851
1852         bc_num_retireMul(c, scale, a->neg, b->neg);
1853         bc_num_free(&cp);
1854
1855         return s;
1856 }
1857
1858 static BcStatus bc_num_r(BcNum *a, BcNum *b, BcNum *restrict c,
1859                          BcNum *restrict d, size_t scale, size_t ts)
1860 {
1861         BcStatus s;
1862         BcNum temp;
1863         bool neg;
1864
1865         if (b->len == 0)
1866                 return bc_error("divide by zero");
1867
1868         if (a->len == 0) {
1869                 bc_num_setToZero(d, ts);
1870                 return BC_STATUS_SUCCESS;
1871         }
1872
1873         bc_num_init(&temp, d->cap);
1874         s = bc_num_d(a, b, c, scale);
1875         if (s) goto err;
1876
1877         if (scale != 0) scale = ts;
1878
1879         s = bc_num_m(c, b, &temp, scale);
1880         if (s) goto err;
1881         s = bc_num_sub(a, &temp, d, scale);
1882         if (s) goto err;
1883
1884         if (ts > d->rdx && d->len) bc_num_extend(d, ts - d->rdx);
1885
1886         neg = d->neg;
1887         bc_num_retireMul(d, ts, a->neg, b->neg);
1888         d->neg = neg;
1889
1890 err:
1891         bc_num_free(&temp);
1892         return s;
1893 }
1894
1895 static BcStatus bc_num_rem(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale)
1896 {
1897         BcStatus s;
1898         BcNum c1;
1899         size_t ts = BC_MAX(scale + b->rdx, a->rdx), len = BC_NUM_MREQ(a, b, ts);
1900
1901         bc_num_init(&c1, len);
1902         s = bc_num_r(a, b, &c1, c, scale, ts);
1903         bc_num_free(&c1);
1904
1905         return s;
1906 }
1907
1908 static BcStatus bc_num_p(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale)
1909 {
1910         BcStatus s = BC_STATUS_SUCCESS;
1911         BcNum copy;
1912         unsigned long pow;
1913         size_t i, powrdx, resrdx;
1914         bool neg, zero;
1915
1916         if (b->rdx) return bc_error("non integer number");
1917
1918         if (b->len == 0) {
1919                 bc_num_one(c);
1920                 return BC_STATUS_SUCCESS;
1921         }
1922         else if (a->len == 0) {
1923                 bc_num_setToZero(c, scale);
1924                 return BC_STATUS_SUCCESS;
1925         }
1926         else if (BC_NUM_ONE(b)) {
1927                 if (!b->neg)
1928                         bc_num_copy(c, a);
1929                 else
1930                         s = bc_num_inv(a, c, scale);
1931                 return s;
1932         }
1933
1934         neg = b->neg;
1935         b->neg = false;
1936
1937         s = bc_num_ulong(b, &pow);
1938         if (s) return s;
1939
1940         bc_num_init(&copy, a->len);
1941         bc_num_copy(&copy, a);
1942
1943         if (!neg) scale = BC_MIN(a->rdx * pow, BC_MAX(scale, a->rdx));
1944
1945         b->neg = neg;
1946
1947         for (powrdx = a->rdx; !(pow & 1); pow >>= 1) {
1948                 powrdx <<= 1;
1949                 s = bc_num_mul(&copy, &copy, &copy, powrdx);
1950                 if (s) goto err;
1951                 // Not needed: bc_num_mul() has a check for ^C:
1952                 //if (G_interrupt) {
1953                 //      s = BC_STATUS_FAILURE;
1954                 //      goto err;
1955                 //}
1956         }
1957
1958         bc_num_copy(c, &copy);
1959
1960         for (resrdx = powrdx, pow >>= 1; pow != 0; pow >>= 1) {
1961
1962                 powrdx <<= 1;
1963                 s = bc_num_mul(&copy, &copy, &copy, powrdx);
1964                 if (s) goto err;
1965
1966                 if (pow & 1) {
1967                         resrdx += powrdx;
1968                         s = bc_num_mul(c, &copy, c, resrdx);
1969                         if (s) goto err;
1970                 }
1971                 // Not needed: bc_num_mul() has a check for ^C:
1972                 //if (G_interrupt) {
1973                 //      s = BC_STATUS_FAILURE;
1974                 //      goto err;
1975                 //}
1976         }
1977
1978         if (neg) {
1979                 s = bc_num_inv(c, c, scale);
1980                 if (s) goto err;
1981         }
1982
1983         if (c->rdx > scale) bc_num_truncate(c, c->rdx - scale);
1984
1985         // We can't use bc_num_clean() here.
1986         for (zero = true, i = 0; zero && i < c->len; ++i) zero = !c->num[i];
1987         if (zero) bc_num_setToZero(c, scale);
1988
1989 err:
1990         bc_num_free(&copy);
1991         return s;
1992 }
1993
1994 static BcStatus bc_num_binary(BcNum *a, BcNum *b, BcNum *c, size_t scale,
1995                               BcNumBinaryOp op, size_t req)
1996 {
1997         BcStatus s;
1998         BcNum num2, *ptr_a, *ptr_b;
1999         bool init = false;
2000
2001         if (c == a) {
2002                 ptr_a = &num2;
2003                 memcpy(ptr_a, c, sizeof(BcNum));
2004                 init = true;
2005         }
2006         else
2007                 ptr_a = a;
2008
2009         if (c == b) {
2010                 ptr_b = &num2;
2011                 if (c != a) {
2012                         memcpy(ptr_b, c, sizeof(BcNum));
2013                         init = true;
2014                 }
2015         }
2016         else
2017                 ptr_b = b;
2018
2019         if (init)
2020                 bc_num_init(c, req);
2021         else
2022                 bc_num_expand(c, req);
2023
2024         s = op(ptr_a, ptr_b, c, scale);
2025
2026         if (init) bc_num_free(&num2);
2027
2028         return s;
2029 }
2030
2031 static bool bc_num_strValid(const char *val, size_t base)
2032 {
2033         BcDig b;
2034         bool small, radix = false;
2035         size_t i, len = strlen(val);
2036
2037         if (!len) return true;
2038
2039         small = base <= 10;
2040         b = (BcDig)(small ? base + '0' : base - 10 + 'A');
2041
2042         for (i = 0; i < len; ++i) {
2043
2044                 BcDig c = val[i];
2045
2046                 if (c == '.') {
2047
2048                         if (radix) return false;
2049
2050                         radix = true;
2051                         continue;
2052                 }
2053
2054                 if (c < '0' || (small && c >= b) || (c > '9' && (c < 'A' || c >= b)))
2055                         return false;
2056         }
2057
2058         return true;
2059 }
2060
2061 static void bc_num_parseDecimal(BcNum *n, const char *val)
2062 {
2063         size_t len, i;
2064         const char *ptr;
2065         bool zero = true;
2066
2067         for (i = 0; val[i] == '0'; ++i);
2068
2069         val += i;
2070         len = strlen(val);
2071         bc_num_zero(n);
2072
2073         if (len != 0) {
2074                 for (i = 0; zero && i < len; ++i) zero = val[i] == '0' || val[i] == '.';
2075                 bc_num_expand(n, len);
2076         }
2077
2078         ptr = strchr(val, '.');
2079
2080         n->rdx = 0;
2081         if (ptr != NULL)
2082                 n->rdx = (size_t)((val + len) - (ptr + 1));
2083
2084         if (!zero) {
2085                 for (i = len - 1; i < len; ++n->len, i -= 1 + (i && val[i - 1] == '.'))
2086                         n->num[n->len] = val[i] - '0';
2087         }
2088 }
2089
2090 static void bc_num_parseBase(BcNum *n, const char *val, BcNum *base)
2091 {
2092         BcStatus s;
2093         BcNum temp, mult, result;
2094         BcDig c = '\0';
2095         bool zero = true;
2096         unsigned long v;
2097         size_t i, digits, len = strlen(val);
2098
2099         bc_num_zero(n);
2100
2101         for (i = 0; zero && i < len; ++i) zero = (val[i] == '.' || val[i] == '0');
2102         if (zero) return;
2103
2104         bc_num_init(&temp, BC_NUM_DEF_SIZE);
2105         bc_num_init(&mult, BC_NUM_DEF_SIZE);
2106
2107         for (i = 0; i < len; ++i) {
2108
2109                 c = val[i];
2110                 if (c == '.') break;
2111
2112                 v = (unsigned long) (c <= '9' ? c - '0' : c - 'A' + 10);
2113
2114                 s = bc_num_mul(n, base, &mult, 0);
2115                 if (s) goto int_err;
2116                 bc_num_ulong2num(&temp, v);
2117                 s = bc_num_add(&mult, &temp, n, 0);
2118                 if (s) goto int_err;
2119         }
2120
2121         if (i == len) {
2122                 c = val[i];
2123                 if (c == 0) goto int_err;
2124         }
2125
2126         bc_num_init(&result, base->len);
2127         bc_num_zero(&result);
2128         bc_num_one(&mult);
2129
2130         for (i += 1, digits = 0; i < len; ++i, ++digits) {
2131
2132                 c = val[i];
2133                 if (c == 0) break;
2134
2135                 v = (unsigned long) (c <= '9' ? c - '0' : c - 'A' + 10);
2136
2137                 s = bc_num_mul(&result, base, &result, 0);
2138                 if (s) goto err;
2139                 bc_num_ulong2num(&temp, v);
2140                 s = bc_num_add(&result, &temp, &result, 0);
2141                 if (s) goto err;
2142                 s = bc_num_mul(&mult, base, &mult, 0);
2143                 if (s) goto err;
2144         }
2145
2146         s = bc_num_div(&result, &mult, &result, digits);
2147         if (s) goto err;
2148         s = bc_num_add(n, &result, n, digits);
2149         if (s) goto err;
2150
2151         if (n->len != 0) {
2152                 if (n->rdx < digits) bc_num_extend(n, digits - n->rdx);
2153         }
2154         else
2155                 bc_num_zero(n);
2156
2157 err:
2158         bc_num_free(&result);
2159 int_err:
2160         bc_num_free(&mult);
2161         bc_num_free(&temp);
2162 }
2163
2164 static void bc_num_printNewline(size_t *nchars, size_t line_len)
2165 {
2166         if (*nchars == line_len - 1) {
2167                 bb_putchar('\\');
2168                 bb_putchar('\n');
2169                 *nchars = 0;
2170         }
2171 }
2172
2173 #if ENABLE_DC
2174 static void bc_num_printChar(size_t num, size_t width, bool radix,
2175                              size_t *nchars, size_t line_len)
2176 {
2177         (void) radix, (void) line_len;
2178         bb_putchar((char) num);
2179         *nchars = *nchars + width;
2180 }
2181 #endif
2182
2183 static void bc_num_printDigits(size_t num, size_t width, bool radix,
2184                                size_t *nchars, size_t line_len)
2185 {
2186         size_t exp, pow;
2187
2188         bc_num_printNewline(nchars, line_len);
2189         bb_putchar(radix ? '.' : ' ');
2190         ++(*nchars);
2191
2192         bc_num_printNewline(nchars, line_len);
2193         for (exp = 0, pow = 1; exp < width - 1; ++exp, pow *= 10)
2194                 continue;
2195
2196         for (exp = 0; exp < width; pow /= 10, ++(*nchars), ++exp) {
2197                 size_t dig;
2198                 bc_num_printNewline(nchars, line_len);
2199                 dig = num / pow;
2200                 num -= dig * pow;
2201                 bb_putchar(((char) dig) + '0');
2202         }
2203 }
2204
2205 static void bc_num_printHex(size_t num, size_t width, bool radix,
2206                             size_t *nchars, size_t line_len)
2207 {
2208         if (radix) {
2209                 bc_num_printNewline(nchars, line_len);
2210                 bb_putchar('.');
2211                 *nchars += 1;
2212         }
2213
2214         bc_num_printNewline(nchars, line_len);
2215         bb_putchar(bb_hexdigits_upcase[num]);
2216         *nchars = *nchars + width;
2217 }
2218
2219 static void bc_num_printDecimal(BcNum *n, size_t *nchars, size_t len)
2220 {
2221         size_t i, rdx = n->rdx - 1;
2222
2223         if (n->neg) bb_putchar('-');
2224         (*nchars) += n->neg;
2225
2226         for (i = n->len - 1; i < n->len; --i)
2227                 bc_num_printHex((size_t) n->num[i], 1, i == rdx, nchars, len);
2228 }
2229
2230 static BcStatus bc_num_printNum(BcNum *n, BcNum *base, size_t width,
2231                                 size_t *nchars, size_t len, BcNumDigitOp print)
2232 {
2233         BcStatus s;
2234         BcVec stack;
2235         BcNum intp, fracp, digit, frac_len;
2236         unsigned long dig, *ptr;
2237         size_t i;
2238         bool radix;
2239
2240         if (n->len == 0) {
2241                 print(0, width, false, nchars, len);
2242                 return BC_STATUS_SUCCESS;
2243         }
2244
2245         bc_vec_init(&stack, sizeof(long), NULL);
2246         bc_num_init(&intp, n->len);
2247         bc_num_init(&fracp, n->rdx);
2248         bc_num_init(&digit, width);
2249         bc_num_init(&frac_len, BC_NUM_INT(n));
2250         bc_num_copy(&intp, n);
2251         bc_num_one(&frac_len);
2252
2253         bc_num_truncate(&intp, intp.rdx);
2254         s = bc_num_sub(n, &intp, &fracp, 0);
2255         if (s) goto err;
2256
2257         while (intp.len != 0) {
2258                 s = bc_num_divmod(&intp, base, &intp, &digit, 0);
2259                 if (s) goto err;
2260                 s = bc_num_ulong(&digit, &dig);
2261                 if (s) goto err;
2262                 bc_vec_push(&stack, &dig);
2263         }
2264
2265         for (i = 0; i < stack.len; ++i) {
2266                 ptr = bc_vec_item_rev(&stack, i);
2267                 print(*ptr, width, false, nchars, len);
2268         }
2269
2270         if (!n->rdx) goto err;
2271
2272         for (radix = true; frac_len.len <= n->rdx; radix = false) {
2273                 s = bc_num_mul(&fracp, base, &fracp, n->rdx);
2274                 if (s) goto err;
2275                 s = bc_num_ulong(&fracp, &dig);
2276                 if (s) goto err;
2277                 bc_num_ulong2num(&intp, dig);
2278                 s = bc_num_sub(&fracp, &intp, &fracp, 0);
2279                 if (s) goto err;
2280                 print(dig, width, radix, nchars, len);
2281                 s = bc_num_mul(&frac_len, base, &frac_len, 0);
2282                 if (s) goto err;
2283         }
2284
2285 err:
2286         bc_num_free(&frac_len);
2287         bc_num_free(&digit);
2288         bc_num_free(&fracp);
2289         bc_num_free(&intp);
2290         bc_vec_free(&stack);
2291         return s;
2292 }
2293
2294 static BcStatus bc_num_printBase(BcNum *n, BcNum *base, size_t base_t,
2295                                  size_t *nchars, size_t line_len)
2296 {
2297         BcStatus s;
2298         size_t width, i;
2299         BcNumDigitOp print;
2300         bool neg = n->neg;
2301
2302         if (neg) bb_putchar('-');
2303         (*nchars) += neg;
2304
2305         n->neg = false;
2306
2307         if (base_t <= BC_NUM_MAX_IBASE) {
2308                 width = 1;
2309                 print = bc_num_printHex;
2310         }
2311         else {
2312                 for (i = base_t - 1, width = 0; i != 0; i /= 10, ++width);
2313                 print = bc_num_printDigits;
2314         }
2315
2316         s = bc_num_printNum(n, base, width, nchars, line_len, print);
2317         n->neg = neg;
2318
2319         return s;
2320 }
2321
2322 #if ENABLE_DC
2323 static BcStatus bc_num_stream(BcNum *n, BcNum *base, size_t *nchars, size_t len)
2324 {
2325         return bc_num_printNum(n, base, 1, nchars, len, bc_num_printChar);
2326 }
2327 #endif
2328
2329 static void bc_num_init(BcNum *n, size_t req)
2330 {
2331         req = req >= BC_NUM_DEF_SIZE ? req : BC_NUM_DEF_SIZE;
2332         memset(n, 0, sizeof(BcNum));
2333         n->num = xmalloc(req);
2334         n->cap = req;
2335 }
2336
2337 static void bc_num_expand(BcNum *n, size_t req)
2338 {
2339         req = req >= BC_NUM_DEF_SIZE ? req : BC_NUM_DEF_SIZE;
2340         if (req > n->cap) {
2341                 n->num = xrealloc(n->num, req);
2342                 n->cap = req;
2343         }
2344 }
2345
2346 static void bc_num_free(void *num)
2347 {
2348         free(((BcNum *) num)->num);
2349 }
2350
2351 static void bc_num_copy(BcNum *d, BcNum *s)
2352 {
2353         if (d != s) {
2354                 bc_num_expand(d, s->cap);
2355                 d->len = s->len;
2356                 d->neg = s->neg;
2357                 d->rdx = s->rdx;
2358                 memcpy(d->num, s->num, sizeof(BcDig) * d->len);
2359         }
2360 }
2361
2362 static BcStatus bc_num_parse(BcNum *n, const char *val, BcNum *base,
2363                              size_t base_t)
2364 {
2365         if (!bc_num_strValid(val, base_t))
2366                 return bc_error("bad number string");
2367
2368         if (base_t == 10)
2369                 bc_num_parseDecimal(n, val);
2370         else
2371                 bc_num_parseBase(n, val, base);
2372
2373         return BC_STATUS_SUCCESS;
2374 }
2375
2376 static BcStatus bc_num_print(BcNum *n, BcNum *base, size_t base_t, bool newline,
2377                              size_t *nchars, size_t line_len)
2378 {
2379         BcStatus s = BC_STATUS_SUCCESS;
2380
2381         bc_num_printNewline(nchars, line_len);
2382
2383         if (n->len == 0) {
2384                 bb_putchar('0');
2385                 ++(*nchars);
2386         }
2387         else if (base_t == 10)
2388                 bc_num_printDecimal(n, nchars, line_len);
2389         else
2390                 s = bc_num_printBase(n, base, base_t, nchars, line_len);
2391
2392         if (newline) {
2393                 bb_putchar('\n');
2394                 *nchars = 0;
2395         }
2396
2397         return s;
2398 }
2399
2400 static BcStatus bc_num_ulong(BcNum *n, unsigned long *result)
2401 {
2402         size_t i;
2403         unsigned long pow;
2404
2405         if (n->neg) return bc_error("negative number");
2406
2407         for (*result = 0, pow = 1, i = n->rdx; i < n->len; ++i) {
2408
2409                 unsigned long prev = *result, powprev = pow;
2410
2411                 *result += ((unsigned long) n->num[i]) * pow;
2412                 pow *= 10;
2413
2414                 if (*result < prev || pow < powprev)
2415                         return bc_error("overflow");
2416         }
2417
2418         return BC_STATUS_SUCCESS;
2419 }
2420
2421 static void bc_num_ulong2num(BcNum *n, unsigned long val)
2422 {
2423         size_t len;
2424         BcDig *ptr;
2425         unsigned long i;
2426
2427         bc_num_zero(n);
2428
2429         if (val == 0) return;
2430
2431         for (len = 1, i = ULONG_MAX; i != 0; i /= 10, ++len) bc_num_expand(n, len);
2432         for (ptr = n->num, i = 0; val; ++i, ++n->len, val /= 10) ptr[i] = val % 10;
2433 }
2434
2435 static BcStatus bc_num_add(BcNum *a, BcNum *b, BcNum *c, size_t scale)
2436 {
2437         BcNumBinaryOp op = (!a->neg == !b->neg) ? bc_num_a : bc_num_s;
2438         (void) scale;
2439         return bc_num_binary(a, b, c, false, op, BC_NUM_AREQ(a, b));
2440 }
2441
2442 static BcStatus bc_num_sub(BcNum *a, BcNum *b, BcNum *c, size_t scale)
2443 {
2444         BcNumBinaryOp op = (!a->neg == !b->neg) ? bc_num_s : bc_num_a;
2445         (void) scale;
2446         return bc_num_binary(a, b, c, true, op, BC_NUM_AREQ(a, b));
2447 }
2448
2449 static BcStatus bc_num_mul(BcNum *a, BcNum *b, BcNum *c, size_t scale)
2450 {
2451         size_t req = BC_NUM_MREQ(a, b, scale);
2452         return bc_num_binary(a, b, c, scale, bc_num_m, req);
2453 }
2454
2455 static BcStatus bc_num_div(BcNum *a, BcNum *b, BcNum *c, size_t scale)
2456 {
2457         size_t req = BC_NUM_MREQ(a, b, scale);
2458         return bc_num_binary(a, b, c, scale, bc_num_d, req);
2459 }
2460
2461 static BcStatus bc_num_mod(BcNum *a, BcNum *b, BcNum *c, size_t scale)
2462 {
2463         size_t req = BC_NUM_MREQ(a, b, scale);
2464         return bc_num_binary(a, b, c, scale, bc_num_rem, req);
2465 }
2466
2467 static BcStatus bc_num_pow(BcNum *a, BcNum *b, BcNum *c, size_t scale)
2468 {
2469         return bc_num_binary(a, b, c, scale, bc_num_p, a->len * b->len + 1);
2470 }
2471
2472 static BcStatus bc_num_sqrt(BcNum *a, BcNum *restrict b, size_t scale)
2473 {
2474         BcStatus s;
2475         BcNum num1, num2, half, f, fprime, *x0, *x1, *temp;
2476         size_t pow, len, digs, digs1, resrdx, req, times = 0;
2477         ssize_t cmp = 1, cmp1 = SSIZE_MAX, cmp2 = SSIZE_MAX;
2478
2479         req = BC_MAX(scale, a->rdx) + ((BC_NUM_INT(a) + 1) >> 1) + 1;
2480         bc_num_expand(b, req);
2481
2482         if (a->len == 0) {
2483                 bc_num_setToZero(b, scale);
2484                 return BC_STATUS_SUCCESS;
2485         }
2486         else if (a->neg)
2487                 return bc_error("negative number");
2488         else if (BC_NUM_ONE(a)) {
2489                 bc_num_one(b);
2490                 bc_num_extend(b, scale);
2491                 return BC_STATUS_SUCCESS;
2492         }
2493
2494         scale = BC_MAX(scale, a->rdx) + 1;
2495         len = a->len + scale;
2496
2497         bc_num_init(&num1, len);
2498         bc_num_init(&num2, len);
2499         bc_num_init(&half, BC_NUM_DEF_SIZE);
2500
2501         bc_num_one(&half);
2502         half.num[0] = 5;
2503         half.rdx = 1;
2504
2505         bc_num_init(&f, len);
2506         bc_num_init(&fprime, len);
2507
2508         x0 = &num1;
2509         x1 = &num2;
2510
2511         bc_num_one(x0);
2512         pow = BC_NUM_INT(a);
2513
2514         if (pow) {
2515
2516                 if (pow & 1)
2517                         x0->num[0] = 2;
2518                 else
2519                         x0->num[0] = 6;
2520
2521                 pow -= 2 - (pow & 1);
2522
2523                 bc_num_extend(x0, pow);
2524
2525                 // Make sure to move the radix back.
2526                 x0->rdx -= pow;
2527         }
2528
2529         x0->rdx = digs = digs1 = 0;
2530         resrdx = scale + 2;
2531         len = BC_NUM_INT(x0) + resrdx - 1;
2532
2533         while (cmp != 0 || digs < len) {
2534
2535                 s = bc_num_div(a, x0, &f, resrdx);
2536                 if (s) goto err;
2537                 s = bc_num_add(x0, &f, &fprime, resrdx);
2538                 if (s) goto err;
2539                 s = bc_num_mul(&fprime, &half, x1, resrdx);
2540                 if (s) goto err;
2541
2542                 cmp = bc_num_cmp(x1, x0);
2543                 digs = x1->len - (unsigned long long) llabs(cmp);
2544
2545                 if (cmp == cmp2 && digs == digs1)
2546                         times += 1;
2547                 else
2548                         times = 0;
2549
2550                 resrdx += times > 4;
2551
2552                 cmp2 = cmp1;
2553                 cmp1 = cmp;
2554                 digs1 = digs;
2555
2556                 temp = x0;
2557                 x0 = x1;
2558                 x1 = temp;
2559         }
2560
2561         bc_num_copy(b, x0);
2562         scale -= 1;
2563         if (b->rdx > scale) bc_num_truncate(b, b->rdx - scale);
2564
2565 err:
2566         bc_num_free(&fprime);
2567         bc_num_free(&f);
2568         bc_num_free(&half);
2569         bc_num_free(&num2);
2570         bc_num_free(&num1);
2571         return s;
2572 }
2573
2574 static BcStatus bc_num_divmod(BcNum *a, BcNum *b, BcNum *c, BcNum *d,
2575                               size_t scale)
2576 {
2577         BcStatus s;
2578         BcNum num2, *ptr_a;
2579         bool init = false;
2580         size_t ts = BC_MAX(scale + b->rdx, a->rdx), len = BC_NUM_MREQ(a, b, ts);
2581
2582         if (c == a) {
2583                 memcpy(&num2, c, sizeof(BcNum));
2584                 ptr_a = &num2;
2585                 bc_num_init(c, len);
2586                 init = true;
2587         }
2588         else {
2589                 ptr_a = a;
2590                 bc_num_expand(c, len);
2591         }
2592
2593         s = bc_num_r(ptr_a, b, c, d, scale, ts);
2594
2595         if (init) bc_num_free(&num2);
2596
2597         return s;
2598 }
2599
2600 #if ENABLE_DC
2601 static BcStatus bc_num_modexp(BcNum *a, BcNum *b, BcNum *c, BcNum *restrict d)
2602 {
2603         BcStatus s;
2604         BcNum base, exp, two, temp;
2605
2606         if (c->len == 0)
2607                 return bc_error("divide by zero");
2608         if (a->rdx || b->rdx || c->rdx)
2609                 return bc_error("non integer number");
2610         if (b->neg)
2611                 return bc_error("negative number");
2612
2613         bc_num_expand(d, c->len);
2614         bc_num_init(&base, c->len);
2615         bc_num_init(&exp, b->len);
2616         bc_num_init(&two, BC_NUM_DEF_SIZE);
2617         bc_num_init(&temp, b->len);
2618
2619         bc_num_one(&two);
2620         two.num[0] = 2;
2621         bc_num_one(d);
2622
2623         s = bc_num_rem(a, c, &base, 0);
2624         if (s) goto err;
2625         bc_num_copy(&exp, b);
2626
2627         while (exp.len != 0) {
2628
2629                 s = bc_num_divmod(&exp, &two, &exp, &temp, 0);
2630                 if (s) goto err;
2631
2632                 if (BC_NUM_ONE(&temp)) {
2633                         s = bc_num_mul(d, &base, &temp, 0);
2634                         if (s) goto err;
2635                         s = bc_num_rem(&temp, c, d, 0);
2636                         if (s) goto err;
2637                 }
2638
2639                 s = bc_num_mul(&base, &base, &temp, 0);
2640                 if (s) goto err;
2641                 s = bc_num_rem(&temp, c, &base, 0);
2642                 if (s) goto err;
2643         }
2644
2645 err:
2646         bc_num_free(&temp);
2647         bc_num_free(&two);
2648         bc_num_free(&exp);
2649         bc_num_free(&base);
2650         return s;
2651 }
2652 #endif // ENABLE_DC
2653
2654 static int bc_id_cmp(const void *e1, const void *e2)
2655 {
2656         return strcmp(((const BcId *) e1)->name, ((const BcId *) e2)->name);
2657 }
2658
2659 static void bc_id_free(void *id)
2660 {
2661         free(((BcId *) id)->name);
2662 }
2663
2664 static BcStatus bc_func_insert(BcFunc *f, char *name, bool var)
2665 {
2666         BcId a;
2667         size_t i;
2668
2669         for (i = 0; i < f->autos.len; ++i) {
2670                 if (strcmp(name, ((BcId *) bc_vec_item(&f->autos, i))->name) == 0)
2671                         return bc_error("function parameter or auto var has the same name as another");
2672         }
2673
2674         a.idx = var;
2675         a.name = name;
2676
2677         bc_vec_push(&f->autos, &a);
2678
2679         return BC_STATUS_SUCCESS;
2680 }
2681
2682 static void bc_func_init(BcFunc *f)
2683 {
2684         bc_char_vec_init(&f->code);
2685         bc_vec_init(&f->autos, sizeof(BcId), bc_id_free);
2686         bc_vec_init(&f->labels, sizeof(size_t), NULL);
2687         f->nparams = 0;
2688 }
2689
2690 static void bc_func_free(void *func)
2691 {
2692         BcFunc *f = (BcFunc *) func;
2693         bc_vec_free(&f->code);
2694         bc_vec_free(&f->autos);
2695         bc_vec_free(&f->labels);
2696 }
2697
2698 static void bc_array_init(BcVec *a, bool nums)
2699 {
2700         if (nums)
2701                 bc_vec_init(a, sizeof(BcNum), bc_num_free);
2702         else
2703                 bc_vec_init(a, sizeof(BcVec), bc_vec_free);
2704         bc_array_expand(a, 1);
2705 }
2706
2707 static void bc_array_copy(BcVec *d, const BcVec *s)
2708 {
2709         size_t i;
2710
2711         bc_vec_pop_all(d);
2712         bc_vec_expand(d, s->cap);
2713         d->len = s->len;
2714
2715         for (i = 0; i < s->len; ++i) {
2716                 BcNum *dnum = bc_vec_item(d, i), *snum = bc_vec_item(s, i);
2717                 bc_num_init(dnum, snum->len);
2718                 bc_num_copy(dnum, snum);
2719         }
2720 }
2721
2722 static void bc_array_expand(BcVec *a, size_t len)
2723 {
2724         BcResultData data;
2725
2726         if (a->size == sizeof(BcNum) && a->dtor == bc_num_free) {
2727                 while (len > a->len) {
2728                         bc_num_init(&data.n, BC_NUM_DEF_SIZE);
2729                         bc_vec_push(a, &data.n);
2730                 }
2731         }
2732         else {
2733                 while (len > a->len) {
2734                         bc_array_init(&data.v, true);
2735                         bc_vec_push(a, &data.v);
2736                 }
2737         }
2738 }
2739
2740 static void bc_string_free(void *string)
2741 {
2742         free(*((char **) string));
2743 }
2744
2745 #if ENABLE_DC
2746 static void bc_result_copy(BcResult *d, BcResult *src)
2747 {
2748         d->t = src->t;
2749
2750         switch (d->t) {
2751
2752                 case BC_RESULT_TEMP:
2753                 case BC_RESULT_IBASE:
2754                 case BC_RESULT_SCALE:
2755                 case BC_RESULT_OBASE:
2756                 {
2757                         bc_num_init(&d->d.n, src->d.n.len);
2758                         bc_num_copy(&d->d.n, &src->d.n);
2759                         break;
2760                 }
2761
2762                 case BC_RESULT_VAR:
2763                 case BC_RESULT_ARRAY:
2764                 case BC_RESULT_ARRAY_ELEM:
2765                 {
2766                         d->d.id.name = xstrdup(src->d.id.name);
2767                         break;
2768                 }
2769
2770                 case BC_RESULT_CONSTANT:
2771                 case BC_RESULT_LAST:
2772                 case BC_RESULT_ONE:
2773                 case BC_RESULT_STR:
2774                 {
2775                         memcpy(&d->d.n, &src->d.n, sizeof(BcNum));
2776                         break;
2777                 }
2778         }
2779 }
2780 #endif // ENABLE_DC
2781
2782 static void bc_result_free(void *result)
2783 {
2784         BcResult *r = (BcResult *) result;
2785
2786         switch (r->t) {
2787
2788                 case BC_RESULT_TEMP:
2789                 case BC_RESULT_IBASE:
2790                 case BC_RESULT_SCALE:
2791                 case BC_RESULT_OBASE:
2792                 {
2793                         bc_num_free(&r->d.n);
2794                         break;
2795                 }
2796
2797                 case BC_RESULT_VAR:
2798                 case BC_RESULT_ARRAY:
2799                 case BC_RESULT_ARRAY_ELEM:
2800                 {
2801                         free(r->d.id.name);
2802                         break;
2803                 }
2804
2805                 default:
2806                 {
2807                         // Do nothing.
2808                         break;
2809                 }
2810         }
2811 }
2812
2813 static void bc_lex_lineComment(BcLex *l)
2814 {
2815         l->t.t = BC_LEX_WHITESPACE;
2816         while (l->i < l->len && l->buf[l->i++] != '\n');
2817         --l->i;
2818 }
2819
2820 static void bc_lex_whitespace(BcLex *l)
2821 {
2822         char c;
2823         l->t.t = BC_LEX_WHITESPACE;
2824         for (c = l->buf[l->i]; c != '\n' && isspace(c); c = l->buf[++l->i]);
2825 }
2826
2827 static BcStatus bc_lex_number(BcLex *l, char start)
2828 {
2829         const char *buf = l->buf + l->i;
2830         size_t len, hits = 0, bslashes = 0, i = 0, j;
2831         char c = buf[i];
2832         bool last_pt, pt = start == '.';
2833
2834         last_pt = pt;
2835         l->t.t = BC_LEX_NUMBER;
2836
2837         while (c != 0 && (isdigit(c) || (c >= 'A' && c <= 'F') ||
2838                           (c == '.' && !pt) || (c == '\\' && buf[i + 1] == '\n')))
2839         {
2840                 if (c != '\\') {
2841                         last_pt = c == '.';
2842                         pt = pt || last_pt;
2843                 }
2844                 else {
2845                         ++i;
2846                         bslashes += 1;
2847                 }
2848
2849                 c = buf[++i];
2850         }
2851
2852         len = i + !last_pt - bslashes * 2;
2853         if (len > BC_MAX_NUM)
2854                 return bc_error("number too long: must be [1, BC_NUM_MAX]");
2855
2856         bc_vec_pop_all(&l->t.v);
2857         bc_vec_expand(&l->t.v, len + 1);
2858         bc_vec_push(&l->t.v, &start);
2859
2860         for (buf -= 1, j = 1; j < len + hits * 2; ++j) {
2861
2862                 c = buf[j];
2863
2864                 // If we have hit a backslash, skip it. We don't have
2865                 // to check for a newline because it's guaranteed.
2866                 if (hits < bslashes && c == '\\') {
2867                         ++hits;
2868                         ++j;
2869                         continue;
2870                 }
2871
2872                 bc_vec_push(&l->t.v, &c);
2873         }
2874
2875         bc_vec_pushZeroByte(&l->t.v);
2876         l->i += i;
2877
2878         return BC_STATUS_SUCCESS;
2879 }
2880
2881 static BcStatus bc_lex_name(BcLex *l)
2882 {
2883         size_t i = 0;
2884         const char *buf = l->buf + l->i - 1;
2885         char c = buf[i];
2886
2887         l->t.t = BC_LEX_NAME;
2888
2889         while ((c >= 'a' && c <= 'z') || isdigit(c) || c == '_') c = buf[++i];
2890
2891         if (i > BC_MAX_STRING)
2892                 return bc_error("name too long: must be [1, BC_NAME_MAX]");
2893         bc_vec_string(&l->t.v, i, buf);
2894
2895         // Increment the index. We minus 1 because it has already been incremented.
2896         l->i += i - 1;
2897
2898         return BC_STATUS_SUCCESS;
2899 }
2900
2901 static void bc_lex_init(BcLex *l, BcLexNext next)
2902 {
2903         l->next = next;
2904         bc_char_vec_init(&l->t.v);
2905 }
2906
2907 static void bc_lex_free(BcLex *l)
2908 {
2909         bc_vec_free(&l->t.v);
2910 }
2911
2912 static void bc_lex_file(BcLex *l)
2913 {
2914         G.err_line = l->line = 1;
2915         l->newline = false;
2916 }
2917
2918 static BcStatus bc_lex_next(BcLex *l)
2919 {
2920         BcStatus s;
2921
2922         l->t.last = l->t.t;
2923         if (l->t.last == BC_LEX_EOF) return bc_error("end of file");
2924
2925         l->line += l->newline;
2926         G.err_line = l->line;
2927         l->t.t = BC_LEX_EOF;
2928
2929         l->newline = (l->i == l->len);
2930         if (l->newline) return BC_STATUS_SUCCESS;
2931
2932         // Loop until failure or we don't have whitespace. This
2933         // is so the parser doesn't get inundated with whitespace.
2934         do {
2935                 s = l->next(l);
2936         } while (!s && l->t.t == BC_LEX_WHITESPACE);
2937
2938         return s;
2939 }
2940
2941 static BcStatus bc_lex_text(BcLex *l, const char *text)
2942 {
2943         l->buf = text;
2944         l->i = 0;
2945         l->len = strlen(text);
2946         l->t.t = l->t.last = BC_LEX_INVALID;
2947         return bc_lex_next(l);
2948 }
2949
2950 #if ENABLE_BC
2951 static BcStatus bc_lex_identifier(BcLex *l)
2952 {
2953         BcStatus s;
2954         unsigned i;
2955         const char *buf = l->buf + l->i - 1;
2956
2957         for (i = 0; i < ARRAY_SIZE(bc_lex_kws); ++i) {
2958                 const char *keyword8 = bc_lex_kws[i].name8;
2959                 unsigned j = 0;
2960                 while (buf[j] != '\0' && buf[j] == keyword8[j]) {
2961                         j++;
2962                         if (j == 8) goto match;
2963                 }
2964                 if (keyword8[j] != '\0')
2965                         continue;
2966  match:
2967                 // buf starts with keyword bc_lex_kws[i]
2968                 l->t.t = BC_LEX_KEY_1st_keyword + i;
2969                 if (!((1 << i) & POSIX_KWORD_MASK)) {
2970                         s = bc_posix_error_fmt("%sthe '%.8s' keyword", "POSIX does not allow ", bc_lex_kws[i].name8);
2971                         if (s) return s;
2972                 }
2973
2974                 // We minus 1 because the index has already been incremented.
2975                 l->i += j - 1;
2976                 return BC_STATUS_SUCCESS;
2977         }
2978
2979         s = bc_lex_name(l);
2980         if (s) return s;
2981
2982         if (l->t.v.len > 2) {
2983                 // Prevent this:
2984                 // >>> qwe=1
2985                 // bc: POSIX only allows one character names; the following is bad: 'qwe=1
2986                 // '
2987                 unsigned len = strchrnul(buf, '\n') - buf;
2988                 s = bc_posix_error_fmt("POSIX only allows one character names; the following is bad: '%.*s'", len, buf);
2989         }
2990
2991         return s;
2992 }
2993
2994 static BcStatus bc_lex_string(BcLex *l)
2995 {
2996         size_t len, nls = 0, i = l->i;
2997         char c;
2998
2999         l->t.t = BC_LEX_STR;
3000
3001         for (c = l->buf[i]; c != 0 && c != '"'; c = l->buf[++i]) nls += (c == '\n');
3002
3003         if (c == '\0') {
3004                 l->i = i;
3005                 return bc_error("string end could not be found");
3006         }
3007
3008         len = i - l->i;
3009         if (len > BC_MAX_STRING)
3010                 return bc_error("string too long: must be [1, BC_STRING_MAX]");
3011         bc_vec_string(&l->t.v, len, l->buf + l->i);
3012
3013         l->i = i + 1;
3014         l->line += nls;
3015         G.err_line = l->line;
3016
3017         return BC_STATUS_SUCCESS;
3018 }
3019
3020 static void bc_lex_assign(BcLex *l, BcLexType with, BcLexType without)
3021 {
3022         if (l->buf[l->i] == '=') {
3023                 ++l->i;
3024                 l->t.t = with;
3025         }
3026         else
3027                 l->t.t = without;
3028 }
3029
3030 static BcStatus bc_lex_comment(BcLex *l)
3031 {
3032         size_t i, nls = 0;
3033         const char *buf = l->buf;
3034
3035         l->t.t = BC_LEX_WHITESPACE;
3036         i = ++l->i;
3037         for (;;) {
3038                 char c = buf[i];
3039  check_star:
3040                 if (c == '*') {
3041                         c = buf[++i];
3042                         if (c == '/')
3043                                 break;
3044                         goto check_star;
3045                 }
3046                 if (c == '\0') {
3047                         l->i = i;
3048                         return bc_error("comment end could not be found");
3049                 }
3050                 nls += (c == '\n');
3051                 i++;
3052         }
3053
3054         l->i = i + 1;
3055         l->line += nls;
3056         G.err_line = l->line;
3057
3058         return BC_STATUS_SUCCESS;
3059 }
3060
3061 static BcStatus bc_lex_token(BcLex *l)
3062 {
3063         BcStatus s = BC_STATUS_SUCCESS;
3064         char c = l->buf[l->i++], c2;
3065
3066         // This is the workhorse of the lexer.
3067         switch (c) {
3068
3069                 case '\0':
3070                 case '\n':
3071                 {
3072                         l->newline = true;
3073                         l->t.t = !c ? BC_LEX_EOF : BC_LEX_NLINE;
3074                         break;
3075                 }
3076
3077                 case '\t':
3078                 case '\v':
3079                 case '\f':
3080                 case '\r':
3081                 case ' ':
3082                 {
3083                         bc_lex_whitespace(l);
3084                         break;
3085                 }
3086
3087                 case '!':
3088                 {
3089                         bc_lex_assign(l, BC_LEX_OP_REL_NE, BC_LEX_OP_BOOL_NOT);
3090
3091                         if (l->t.t == BC_LEX_OP_BOOL_NOT) {
3092                                 s = bc_POSIX_does_not_allow_bool_ops_this_is_bad("!");
3093                                 if (s) return s;
3094                         }
3095
3096                         break;
3097                 }
3098
3099                 case '"':
3100                 {
3101                         s = bc_lex_string(l);
3102                         break;
3103                 }
3104
3105                 case '#':
3106                 {
3107                         s = bc_POSIX_does_not_allow("'#' script comments");
3108                         if (s) return s;
3109
3110                         bc_lex_lineComment(l);
3111
3112                         break;
3113                 }
3114
3115                 case '%':
3116                 {
3117                         bc_lex_assign(l, BC_LEX_OP_ASSIGN_MODULUS, BC_LEX_OP_MODULUS);
3118                         break;
3119                 }
3120
3121                 case '&':
3122                 {
3123                         c2 = l->buf[l->i];
3124                         if (c2 == '&') {
3125
3126                                 s = bc_POSIX_does_not_allow_bool_ops_this_is_bad("&&");
3127                                 if (s) return s;
3128
3129                                 ++l->i;
3130                                 l->t.t = BC_LEX_OP_BOOL_AND;
3131                         }
3132                         else {
3133                                 l->t.t = BC_LEX_INVALID;
3134                                 s = bc_error_bad_character('&');
3135                         }
3136
3137                         break;
3138                 }
3139
3140                 case '(':
3141                 case ')':
3142                 {
3143                         l->t.t = (BcLexType)(c - '(' + BC_LEX_LPAREN);
3144                         break;
3145                 }
3146
3147                 case '*':
3148                 {
3149                         bc_lex_assign(l, BC_LEX_OP_ASSIGN_MULTIPLY, BC_LEX_OP_MULTIPLY);
3150                         break;
3151                 }
3152
3153                 case '+':
3154                 {
3155                         c2 = l->buf[l->i];
3156                         if (c2 == '+') {
3157                                 ++l->i;
3158                                 l->t.t = BC_LEX_OP_INC;
3159                         }
3160                         else
3161                                 bc_lex_assign(l, BC_LEX_OP_ASSIGN_PLUS, BC_LEX_OP_PLUS);
3162                         break;
3163                 }
3164
3165                 case ',':
3166                 {
3167                         l->t.t = BC_LEX_COMMA;
3168                         break;
3169                 }
3170
3171                 case '-':
3172                 {
3173                         c2 = l->buf[l->i];
3174                         if (c2 == '-') {
3175                                 ++l->i;
3176                                 l->t.t = BC_LEX_OP_DEC;
3177                         }
3178                         else
3179                                 bc_lex_assign(l, BC_LEX_OP_ASSIGN_MINUS, BC_LEX_OP_MINUS);
3180                         break;
3181                 }
3182
3183                 case '.':
3184                 {
3185                         if (isdigit(l->buf[l->i]))
3186                                 s = bc_lex_number(l, c);
3187                         else {
3188                                 l->t.t = BC_LEX_KEY_LAST;
3189                                 s = bc_POSIX_does_not_allow("a period ('.') as a shortcut for the last result");
3190                         }
3191                         break;
3192                 }
3193
3194                 case '/':
3195                 {
3196                         c2 = l->buf[l->i];
3197                         if (c2 == '*')
3198                                 s = bc_lex_comment(l);
3199                         else
3200                                 bc_lex_assign(l, BC_LEX_OP_ASSIGN_DIVIDE, BC_LEX_OP_DIVIDE);
3201                         break;
3202                 }
3203
3204                 case '0':
3205                 case '1':
3206                 case '2':
3207                 case '3':
3208                 case '4':
3209                 case '5':
3210                 case '6':
3211                 case '7':
3212                 case '8':
3213                 case '9':
3214                 case 'A':
3215                 case 'B':
3216                 case 'C':
3217                 case 'D':
3218                 case 'E':
3219                 case 'F':
3220                 {
3221                         s = bc_lex_number(l, c);
3222                         break;
3223                 }
3224
3225                 case ';':
3226                 {
3227                         l->t.t = BC_LEX_SCOLON;
3228                         break;
3229                 }
3230
3231                 case '<':
3232                 {
3233                         bc_lex_assign(l, BC_LEX_OP_REL_LE, BC_LEX_OP_REL_LT);
3234                         break;
3235                 }
3236
3237                 case '=':
3238                 {
3239                         bc_lex_assign(l, BC_LEX_OP_REL_EQ, BC_LEX_OP_ASSIGN);
3240                         break;
3241                 }
3242
3243                 case '>':
3244                 {
3245                         bc_lex_assign(l, BC_LEX_OP_REL_GE, BC_LEX_OP_REL_GT);
3246                         break;
3247                 }
3248
3249                 case '[':
3250                 case ']':
3251                 {
3252                         l->t.t = (BcLexType)(c - '[' + BC_LEX_LBRACKET);
3253                         break;
3254                 }
3255
3256                 case '\\':
3257                 {
3258                         if (l->buf[l->i] == '\n') {
3259                                 l->t.t = BC_LEX_WHITESPACE;
3260                                 ++l->i;
3261                         }
3262                         else
3263                                 s = bc_error_bad_character(c);
3264                         break;
3265                 }
3266
3267                 case '^':
3268                 {
3269                         bc_lex_assign(l, BC_LEX_OP_ASSIGN_POWER, BC_LEX_OP_POWER);
3270                         break;
3271                 }
3272
3273                 case 'a':
3274                 case 'b':
3275                 case 'c':
3276                 case 'd':
3277                 case 'e':
3278                 case 'f':
3279                 case 'g':
3280                 case 'h':
3281                 case 'i':
3282                 case 'j':
3283                 case 'k':
3284                 case 'l':
3285                 case 'm':
3286                 case 'n':
3287                 case 'o':
3288                 case 'p':
3289                 case 'q':
3290                 case 'r':
3291                 case 's':
3292                 case 't':
3293                 case 'u':
3294                 case 'v':
3295                 case 'w':
3296                 case 'x':
3297                 case 'y':
3298                 case 'z':
3299                 {
3300                         s = bc_lex_identifier(l);
3301                         break;
3302                 }
3303
3304                 case '{':
3305                 case '}':
3306                 {
3307                         l->t.t = (BcLexType)(c - '{' + BC_LEX_LBRACE);
3308                         break;
3309                 }
3310
3311                 case '|':
3312                 {
3313                         c2 = l->buf[l->i];
3314
3315                         if (c2 == '|') {
3316                                 s = bc_POSIX_does_not_allow_bool_ops_this_is_bad("||");
3317                                 if (s) return s;
3318
3319                                 ++l->i;
3320                                 l->t.t = BC_LEX_OP_BOOL_OR;
3321                         }
3322                         else {
3323                                 l->t.t = BC_LEX_INVALID;
3324                                 s = bc_error_bad_character(c);
3325                         }
3326
3327                         break;
3328                 }
3329
3330                 default:
3331                 {
3332                         l->t.t = BC_LEX_INVALID;
3333                         s = bc_error_bad_character(c);
3334                         break;
3335                 }
3336         }
3337
3338         return s;
3339 }
3340 #endif // ENABLE_BC
3341
3342 #if ENABLE_DC
3343 static BcStatus dc_lex_register(BcLex *l)
3344 {
3345         BcStatus s = BC_STATUS_SUCCESS;
3346
3347         if (isspace(l->buf[l->i - 1])) {
3348                 bc_lex_whitespace(l);
3349                 ++l->i;
3350                 if (!G_exreg)
3351                         s = bc_error("extended register");
3352                 else
3353                         s = bc_lex_name(l);
3354         }
3355         else {
3356                 bc_vec_pop_all(&l->t.v);
3357                 bc_vec_pushByte(&l->t.v, l->buf[l->i - 1]);
3358                 bc_vec_pushZeroByte(&l->t.v);
3359                 l->t.t = BC_LEX_NAME;
3360         }
3361
3362         return s;
3363 }
3364
3365 static BcStatus dc_lex_string(BcLex *l)
3366 {
3367         size_t depth = 1, nls = 0, i = l->i;
3368         char c;
3369
3370         l->t.t = BC_LEX_STR;
3371         bc_vec_pop_all(&l->t.v);
3372
3373         for (c = l->buf[i]; c != 0 && depth; c = l->buf[++i]) {
3374
3375                 depth += (c == '[' && (i == l->i || l->buf[i - 1] != '\\'));
3376                 depth -= (c == ']' && (i == l->i || l->buf[i - 1] != '\\'));
3377                 nls += (c == '\n');
3378
3379                 if (depth) bc_vec_push(&l->t.v, &c);
3380         }
3381
3382         if (c == '\0') {
3383                 l->i = i;
3384                 return bc_error("string end could not be found");
3385         }
3386
3387         bc_vec_pushZeroByte(&l->t.v);
3388         if (i - l->i > BC_MAX_STRING)
3389                 return bc_error("string too long: must be [1, BC_STRING_MAX]");
3390
3391         l->i = i;
3392         l->line += nls;
3393         G.err_line = l->line;
3394
3395         return BC_STATUS_SUCCESS;
3396 }
3397
3398 static BcStatus dc_lex_token(BcLex *l)
3399 {
3400         BcStatus s = BC_STATUS_SUCCESS;
3401         char c = l->buf[l->i++], c2;
3402         size_t i;
3403
3404         for (i = 0; i < ARRAY_SIZE(dc_lex_regs); ++i) {
3405                 if (l->t.last == dc_lex_regs[i])
3406                         return dc_lex_register(l);
3407         }
3408
3409         if (c >= '%' && c <= '~' &&
3410             (l->t.t = dc_lex_tokens[(c - '%')]) != BC_LEX_INVALID)
3411         {
3412                 return s;
3413         }
3414
3415         // This is the workhorse of the lexer.
3416         switch (c) {
3417
3418                 case '\0':
3419                 {
3420                         l->t.t = BC_LEX_EOF;
3421                         break;
3422                 }
3423
3424                 case '\n':
3425                 case '\t':
3426                 case '\v':
3427                 case '\f':
3428                 case '\r':
3429                 case ' ':
3430                 {
3431                         l->newline = (c == '\n');
3432                         bc_lex_whitespace(l);
3433                         break;
3434                 }
3435
3436                 case '!':
3437                 {
3438                         c2 = l->buf[l->i];
3439
3440                         if (c2 == '=')
3441                                 l->t.t = BC_LEX_OP_REL_NE;
3442                         else if (c2 == '<')
3443                                 l->t.t = BC_LEX_OP_REL_LE;
3444                         else if (c2 == '>')
3445                                 l->t.t = BC_LEX_OP_REL_GE;
3446                         else
3447                                 return bc_error_bad_character(c);
3448
3449                         ++l->i;
3450                         break;
3451                 }
3452
3453                 case '#':
3454                 {
3455                         bc_lex_lineComment(l);
3456                         break;
3457                 }
3458
3459                 case '.':
3460                 {
3461                         if (isdigit(l->buf[l->i]))
3462                                 s = bc_lex_number(l, c);
3463                         else
3464                                 s = bc_error_bad_character(c);
3465                         break;
3466                 }
3467
3468                 case '0':
3469                 case '1':
3470                 case '2':
3471                 case '3':
3472                 case '4':
3473                 case '5':
3474                 case '6':
3475                 case '7':
3476                 case '8':
3477                 case '9':
3478                 case 'A':
3479                 case 'B':
3480                 case 'C':
3481                 case 'D':
3482                 case 'E':
3483                 case 'F':
3484                 {
3485                         s = bc_lex_number(l, c);
3486                         break;
3487                 }
3488
3489                 case '[':
3490                 {
3491                         s = dc_lex_string(l);
3492                         break;
3493                 }
3494
3495                 default:
3496                 {
3497                         l->t.t = BC_LEX_INVALID;
3498                         s = bc_error_bad_character(c);
3499                         break;
3500                 }
3501         }
3502
3503         return s;
3504 }
3505 #endif // ENABLE_DC
3506
3507 static void bc_parse_addFunc(BcParse *p, char *name, size_t *idx)
3508 {
3509         bc_program_addFunc(name, idx);
3510         p->func = bc_vec_item(&G.prog.fns, p->fidx);
3511 }
3512
3513 static void bc_parse_pushName(BcParse *p, char *name)
3514 {
3515         size_t i = 0, len = strlen(name);
3516
3517         for (; i < len; ++i) bc_parse_push(p, name[i]);
3518         bc_parse_push(p, BC_PARSE_STREND);
3519
3520         free(name);
3521 }
3522
3523 static void bc_parse_pushIndex(BcParse *p, size_t idx)
3524 {
3525         unsigned char amt, i, nums[sizeof(size_t)];
3526
3527         for (amt = 0; idx; ++amt) {
3528                 nums[amt] = (char) idx;
3529                 idx = (idx & ((unsigned long) ~(UCHAR_MAX))) >> sizeof(char) * CHAR_BIT;
3530         }
3531
3532         bc_parse_push(p, amt);
3533         for (i = 0; i < amt; ++i) bc_parse_push(p, nums[i]);
3534 }
3535
3536 static void bc_parse_number(BcParse *p, BcInst *prev, size_t *nexs)
3537 {
3538         char *num = xstrdup(p->l.t.v.v);
3539         size_t idx = G.prog.consts.len;
3540
3541         bc_vec_push(&G.prog.consts, &num);
3542
3543         bc_parse_push(p, BC_INST_NUM);
3544         bc_parse_pushIndex(p, idx);
3545
3546         ++(*nexs);
3547         (*prev) = BC_INST_NUM;
3548 }
3549
3550 static BcStatus bc_parse_text(BcParse *p, const char *text)
3551 {
3552         BcStatus s;
3553
3554         p->func = bc_vec_item(&G.prog.fns, p->fidx);
3555
3556         if (!text[0] && !BC_PARSE_CAN_EXEC(p)) {
3557                 p->l.t.t = BC_LEX_INVALID;
3558                 s = p->parse(p);
3559                 if (s) return s;
3560                 if (!BC_PARSE_CAN_EXEC(p))
3561                         return bc_error("file is not executable");
3562         }
3563
3564         return bc_lex_text(&p->l, text);
3565 }
3566
3567 // Called when bc/dc_parse_parse() detects a failure,
3568 // resets parsing structures.
3569 static void bc_parse_reset(BcParse *p)
3570 {
3571         if (p->fidx != BC_PROG_MAIN) {
3572                 p->func->nparams = 0;
3573                 bc_vec_pop_all(&p->func->code);
3574                 bc_vec_pop_all(&p->func->autos);
3575                 bc_vec_pop_all(&p->func->labels);
3576
3577                 bc_parse_updateFunc(p, BC_PROG_MAIN);
3578         }
3579
3580         p->l.i = p->l.len;
3581         p->l.t.t = BC_LEX_EOF;
3582         p->auto_part = (p->nbraces = 0);
3583
3584         bc_vec_npop(&p->flags, p->flags.len - 1);
3585         bc_vec_pop_all(&p->exits);
3586         bc_vec_pop_all(&p->conds);
3587         bc_vec_pop_all(&p->ops);
3588
3589         bc_program_reset();
3590 }
3591
3592 static void bc_parse_free(BcParse *p)
3593 {
3594         bc_vec_free(&p->flags);
3595         bc_vec_free(&p->exits);
3596         bc_vec_free(&p->conds);
3597         bc_vec_free(&p->ops);
3598         bc_lex_free(&p->l);
3599 }
3600
3601 static void bc_parse_create(BcParse *p, size_t func,
3602                             BcParseParse parse, BcLexNext next)
3603 {
3604         memset(p, 0, sizeof(BcParse));
3605
3606         bc_lex_init(&p->l, next);
3607         bc_vec_init(&p->flags, sizeof(uint8_t), NULL);
3608         bc_vec_init(&p->exits, sizeof(BcInstPtr), NULL);
3609         bc_vec_init(&p->conds, sizeof(size_t), NULL);
3610         bc_vec_pushZeroByte(&p->flags);
3611         bc_vec_init(&p->ops, sizeof(BcLexType), NULL);
3612
3613         p->parse = parse;
3614         // p->auto_part = p->nbraces = 0; - already is
3615         bc_parse_updateFunc(p, func);
3616 }
3617
3618 #if ENABLE_BC
3619 static BcStatus bc_parse_else(BcParse *p);
3620 static BcStatus bc_parse_stmt(BcParse *p);
3621
3622 static BcStatus bc_parse_operator(BcParse *p, BcLexType type, size_t start,
3623                                   size_t *nexprs, bool next)
3624 {
3625         BcStatus s = BC_STATUS_SUCCESS;
3626         BcLexType t;
3627         char l, r = bc_parse_ops[type - BC_LEX_OP_INC].prec;
3628         bool left = bc_parse_ops[type - BC_LEX_OP_INC].left;
3629
3630         while (p->ops.len > start) {
3631
3632                 t = BC_PARSE_TOP_OP(p);
3633                 if (t == BC_LEX_LPAREN) break;
3634
3635                 l = bc_parse_ops[t - BC_LEX_OP_INC].prec;
3636                 if (l >= r && (l != r || !left)) break;
3637
3638                 bc_parse_push(p, BC_PARSE_TOKEN_INST(t));
3639                 bc_vec_pop(&p->ops);
3640                 *nexprs -= t != BC_LEX_OP_BOOL_NOT && t != BC_LEX_NEG;
3641         }
3642
3643         bc_vec_push(&p->ops, &type);
3644         if (next) s = bc_lex_next(&p->l);
3645
3646         return s;
3647 }
3648
3649 static BcStatus bc_parse_rightParen(BcParse *p, size_t ops_bgn, size_t *nexs)
3650 {
3651         BcLexType top;
3652
3653         if (p->ops.len <= ops_bgn)
3654                 return bc_error_bad_expression();
3655         top = BC_PARSE_TOP_OP(p);
3656
3657         while (top != BC_LEX_LPAREN) {
3658
3659                 bc_parse_push(p, BC_PARSE_TOKEN_INST(top));
3660
3661                 bc_vec_pop(&p->ops);
3662                 *nexs -= top != BC_LEX_OP_BOOL_NOT && top != BC_LEX_NEG;
3663
3664                 if (p->ops.len <= ops_bgn)
3665                         return bc_error_bad_expression();
3666                 top = BC_PARSE_TOP_OP(p);
3667         }
3668
3669         bc_vec_pop(&p->ops);
3670
3671         return bc_lex_next(&p->l);
3672 }
3673
3674 static BcStatus bc_parse_params(BcParse *p, uint8_t flags)
3675 {
3676         BcStatus s;
3677         bool comma = false;
3678         size_t nparams;
3679
3680         s = bc_lex_next(&p->l);
3681         if (s) return s;
3682
3683         for (nparams = 0; p->l.t.t != BC_LEX_RPAREN; ++nparams) {
3684
3685                 flags = (flags & ~(BC_PARSE_PRINT | BC_PARSE_REL)) | BC_PARSE_ARRAY;
3686                 s = bc_parse_expr(p, flags, bc_parse_next_param);
3687                 if (s) return s;
3688
3689                 comma = p->l.t.t == BC_LEX_COMMA;
3690                 if (comma) {
3691                         s = bc_lex_next(&p->l);
3692                         if (s) return s;
3693                 }
3694         }
3695
3696         if (comma) return bc_error_bad_token();
3697         bc_parse_push(p, BC_INST_CALL);
3698         bc_parse_pushIndex(p, nparams);
3699
3700         return BC_STATUS_SUCCESS;
3701 }
3702
3703 static BcStatus bc_parse_call(BcParse *p, char *name, uint8_t flags)
3704 {
3705         BcStatus s;
3706         BcId entry, *entry_ptr;
3707         size_t idx;
3708
3709         entry.name = name;
3710
3711         s = bc_parse_params(p, flags);
3712         if (s) goto err;
3713
3714         if (p->l.t.t != BC_LEX_RPAREN) {
3715                 s = bc_error_bad_token();
3716                 goto err;
3717         }
3718
3719         idx = bc_map_index(&G.prog.fn_map, &entry);
3720
3721         if (idx == BC_VEC_INVALID_IDX) {
3722                 name = xstrdup(entry.name);
3723                 bc_parse_addFunc(p, name, &idx);
3724                 idx = bc_map_index(&G.prog.fn_map, &entry);
3725                 free(entry.name);
3726         }
3727         else
3728                 free(name);
3729
3730         entry_ptr = bc_vec_item(&G.prog.fn_map, idx);
3731         bc_parse_pushIndex(p, entry_ptr->idx);
3732
3733         return bc_lex_next(&p->l);
3734
3735 err:
3736         free(name);
3737         return s;
3738 }
3739
3740 static BcStatus bc_parse_name(BcParse *p, BcInst *type, uint8_t flags)
3741 {
3742         BcStatus s;
3743         char *name;
3744
3745         name = xstrdup(p->l.t.v.v);
3746         s = bc_lex_next(&p->l);
3747         if (s) goto err;
3748
3749         if (p->l.t.t == BC_LEX_LBRACKET) {
3750
3751                 s = bc_lex_next(&p->l);
3752                 if (s) goto err;
3753
3754                 if (p->l.t.t == BC_LEX_RBRACKET) {
3755
3756                         if (!(flags & BC_PARSE_ARRAY)) {
3757                                 s = bc_error_bad_expression();
3758                                 goto err;
3759                         }
3760
3761                         *type = BC_INST_ARRAY;
3762                 }
3763                 else {
3764
3765                         *type = BC_INST_ARRAY_ELEM;
3766
3767                         flags &= ~(BC_PARSE_PRINT | BC_PARSE_REL);
3768                         s = bc_parse_expr(p, flags, bc_parse_next_elem);
3769                         if (s) goto err;
3770                 }
3771
3772                 s = bc_lex_next(&p->l);
3773                 if (s) goto err;
3774                 bc_parse_push(p, *type);
3775                 bc_parse_pushName(p, name);
3776         }
3777         else if (p->l.t.t == BC_LEX_LPAREN) {
3778
3779                 if (flags & BC_PARSE_NOCALL) {
3780                         s = bc_error_bad_token();
3781                         goto err;
3782                 }
3783
3784                 *type = BC_INST_CALL;
3785                 s = bc_parse_call(p, name, flags);
3786         }
3787         else {
3788                 *type = BC_INST_VAR;
3789                 bc_parse_push(p, BC_INST_VAR);
3790                 bc_parse_pushName(p, name);
3791         }
3792
3793         return s;
3794
3795 err:
3796         free(name);
3797         return s;
3798 }
3799
3800 static BcStatus bc_parse_read(BcParse *p)
3801 {
3802         BcStatus s;
3803
3804         s = bc_lex_next(&p->l);
3805         if (s) return s;
3806         if (p->l.t.t != BC_LEX_LPAREN) return bc_error_bad_token();
3807
3808         s = bc_lex_next(&p->l);
3809         if (s) return s;
3810         if (p->l.t.t != BC_LEX_RPAREN) return bc_error_bad_token();
3811
3812         bc_parse_push(p, BC_INST_READ);
3813
3814         return bc_lex_next(&p->l);
3815 }
3816
3817 static BcStatus bc_parse_builtin(BcParse *p, BcLexType type, uint8_t flags,
3818                                  BcInst *prev)
3819 {
3820         BcStatus s;
3821
3822         s = bc_lex_next(&p->l);
3823         if (s) return s;
3824         if (p->l.t.t != BC_LEX_LPAREN) return bc_error_bad_token();
3825
3826         flags = (flags & ~(BC_PARSE_PRINT | BC_PARSE_REL)) | BC_PARSE_ARRAY;
3827
3828         s = bc_lex_next(&p->l);
3829         if (s) return s;
3830
3831         s = bc_parse_expr(p, flags, bc_parse_next_rel);
3832         if (s) return s;
3833
3834         if (p->l.t.t != BC_LEX_RPAREN) return bc_error_bad_token();
3835
3836         *prev = (type == BC_LEX_KEY_LENGTH) ? BC_INST_LENGTH : BC_INST_SQRT;
3837         bc_parse_push(p, *prev);
3838
3839         return bc_lex_next(&p->l);
3840 }
3841
3842 static BcStatus bc_parse_scale(BcParse *p, BcInst *type, uint8_t flags)
3843 {
3844         BcStatus s;
3845
3846         s = bc_lex_next(&p->l);
3847         if (s) return s;
3848
3849         if (p->l.t.t != BC_LEX_LPAREN) {
3850                 *type = BC_INST_SCALE;
3851                 bc_parse_push(p, BC_INST_SCALE);
3852                 return BC_STATUS_SUCCESS;
3853         }
3854
3855         *type = BC_INST_SCALE_FUNC;
3856         flags &= ~(BC_PARSE_PRINT | BC_PARSE_REL);
3857
3858         s = bc_lex_next(&p->l);
3859         if (s) return s;
3860
3861         s = bc_parse_expr(p, flags, bc_parse_next_rel);
3862         if (s) return s;
3863         if (p->l.t.t != BC_LEX_RPAREN) return bc_error_bad_token();
3864         bc_parse_push(p, BC_INST_SCALE_FUNC);
3865
3866         return bc_lex_next(&p->l);
3867 }
3868
3869 static BcStatus bc_parse_incdec(BcParse *p, BcInst *prev, bool *paren_expr,
3870                                 size_t *nexprs, uint8_t flags)
3871 {
3872         BcStatus s;
3873         BcLexType type;
3874         char inst;
3875         BcInst etype = *prev;
3876
3877         if (etype == BC_INST_VAR || etype == BC_INST_ARRAY_ELEM ||
3878             etype == BC_INST_SCALE || etype == BC_INST_LAST ||
3879             etype == BC_INST_IBASE || etype == BC_INST_OBASE)
3880         {
3881                 *prev = inst = BC_INST_INC_POST + (p->l.t.t != BC_LEX_OP_INC);
3882                 bc_parse_push(p, inst);
3883                 s = bc_lex_next(&p->l);
3884         }
3885         else {
3886
3887                 *prev = inst = BC_INST_INC_PRE + (p->l.t.t != BC_LEX_OP_INC);
3888                 *paren_expr = true;
3889
3890                 s = bc_lex_next(&p->l);
3891                 if (s) return s;
3892                 type = p->l.t.t;
3893
3894                 // Because we parse the next part of the expression
3895                 // right here, we need to increment this.
3896                 *nexprs = *nexprs + 1;
3897
3898                 switch (type) {
3899
3900                         case BC_LEX_NAME:
3901                         {
3902                                 s = bc_parse_name(p, prev, flags | BC_PARSE_NOCALL);
3903                                 break;
3904                         }
3905
3906                         case BC_LEX_KEY_IBASE:
3907                         case BC_LEX_KEY_LAST:
3908                         case BC_LEX_KEY_OBASE:
3909                         {
3910                                 bc_parse_push(p, type - BC_LEX_KEY_IBASE + BC_INST_IBASE);
3911                                 s = bc_lex_next(&p->l);
3912                                 break;
3913                         }
3914
3915                         case BC_LEX_KEY_SCALE:
3916                         {
3917                                 s = bc_lex_next(&p->l);
3918                                 if (s) return s;
3919                                 if (p->l.t.t == BC_LEX_LPAREN)
3920                                         s = bc_error_bad_token();
3921                                 else
3922                                         bc_parse_push(p, BC_INST_SCALE);
3923                                 break;
3924                         }
3925
3926                         default:
3927                         {
3928                                 s = bc_error_bad_token();
3929                                 break;
3930                         }
3931                 }
3932
3933                 if (!s) bc_parse_push(p, inst);
3934         }
3935
3936         return s;
3937 }
3938
3939 static BcStatus bc_parse_minus(BcParse *p, BcInst *prev, size_t ops_bgn,
3940                                bool rparen, size_t *nexprs)
3941 {
3942         BcStatus s;
3943         BcLexType type;
3944         BcInst etype = *prev;
3945
3946         s = bc_lex_next(&p->l);
3947         if (s) return s;
3948
3949         type = rparen || etype == BC_INST_INC_POST || etype == BC_INST_DEC_POST ||
3950                        (etype >= BC_INST_NUM && etype <= BC_INST_SQRT) ?
3951                    BC_LEX_OP_MINUS :
3952                    BC_LEX_NEG;
3953         *prev = BC_PARSE_TOKEN_INST(type);
3954
3955         // We can just push onto the op stack because this is the largest
3956         // precedence operator that gets pushed. Inc/dec does not.
3957         if (type != BC_LEX_OP_MINUS)
3958                 bc_vec_push(&p->ops, &type);
3959         else
3960                 s = bc_parse_operator(p, type, ops_bgn, nexprs, false);
3961
3962         return s;
3963 }
3964
3965 static BcStatus bc_parse_string(BcParse *p, char inst)
3966 {
3967         char *str = xstrdup(p->l.t.v.v);
3968
3969         bc_parse_push(p, BC_INST_STR);
3970         bc_parse_pushIndex(p, G.prog.strs.len);
3971         bc_vec_push(&G.prog.strs, &str);
3972         bc_parse_push(p, inst);
3973
3974         return bc_lex_next(&p->l);
3975 }
3976
3977 static BcStatus bc_parse_print(BcParse *p)
3978 {
3979         BcStatus s;
3980         BcLexType type;
3981         bool comma = false;
3982
3983         s = bc_lex_next(&p->l);
3984         if (s) return s;
3985
3986         type = p->l.t.t;
3987
3988         if (type == BC_LEX_SCOLON || type == BC_LEX_NLINE)
3989                 return bc_error("bad print statement");
3990
3991         while (!s && type != BC_LEX_SCOLON && type != BC_LEX_NLINE) {
3992
3993                 if (type == BC_LEX_STR)
3994                         s = bc_parse_string(p, BC_INST_PRINT_POP);
3995                 else {
3996                         s = bc_parse_expr(p, 0, bc_parse_next_print);
3997                         if (s) return s;
3998                         bc_parse_push(p, BC_INST_PRINT_POP);
3999                 }
4000
4001                 if (s) return s;
4002
4003                 comma = p->l.t.t == BC_LEX_COMMA;
4004                 if (comma) s = bc_lex_next(&p->l);
4005                 type = p->l.t.t;
4006         }
4007
4008         if (s) return s;
4009         if (comma) return bc_error_bad_token();
4010
4011         return bc_lex_next(&p->l);
4012 }
4013
4014 static BcStatus bc_parse_return(BcParse *p)
4015 {
4016         BcStatus s;
4017         BcLexType t;
4018         bool paren;
4019
4020         if (!BC_PARSE_FUNC(p)) return bc_error_bad_token();
4021
4022         s = bc_lex_next(&p->l);
4023         if (s) return s;
4024
4025         t = p->l.t.t;
4026         paren = t == BC_LEX_LPAREN;
4027
4028         if (t == BC_LEX_NLINE || t == BC_LEX_SCOLON)
4029                 bc_parse_push(p, BC_INST_RET0);
4030         else {
4031
4032                 s = bc_parse_expr(p, 0, bc_parse_next_expr);
4033                 if (s && s != BC_STATUS_PARSE_EMPTY_EXP)
4034                         return s;
4035
4036                 if (s == BC_STATUS_PARSE_EMPTY_EXP) {
4037                         bc_parse_push(p, BC_INST_RET0);
4038                         s = bc_lex_next(&p->l);
4039                         if (s) return s;
4040                 }
4041
4042                 if (!paren || p->l.t.last != BC_LEX_RPAREN) {
4043                         s = bc_posix_error("POSIX requires parentheses around return expressions");
4044                         if (s) return s;
4045                 }
4046
4047                 bc_parse_push(p, BC_INST_RET);
4048         }
4049
4050         return s;
4051 }
4052
4053 static BcStatus bc_parse_endBody(BcParse *p, bool brace)
4054 {
4055         BcStatus s = BC_STATUS_SUCCESS;
4056
4057         if (p->flags.len <= 1 || (brace && p->nbraces == 0))
4058                 return bc_error_bad_token();
4059
4060         if (brace) {
4061
4062                 if (p->l.t.t == BC_LEX_RBRACE) {
4063                         if (!p->nbraces) return bc_error_bad_token();
4064                         --p->nbraces;
4065                         s = bc_lex_next(&p->l);
4066                         if (s) return s;
4067                 }
4068                 else
4069                         return bc_error_bad_token();
4070         }
4071
4072         if (BC_PARSE_IF(p)) {
4073
4074                 uint8_t *flag_ptr;
4075
4076                 while (p->l.t.t == BC_LEX_NLINE) {
4077                         s = bc_lex_next(&p->l);
4078                         if (s) return s;
4079                 }
4080
4081                 bc_vec_pop(&p->flags);
4082
4083                 flag_ptr = BC_PARSE_TOP_FLAG_PTR(p);
4084                 *flag_ptr = (*flag_ptr | BC_PARSE_FLAG_IF_END);
4085
4086                 if (p->l.t.t == BC_LEX_KEY_ELSE) s = bc_parse_else(p);
4087         }
4088         else if (BC_PARSE_ELSE(p)) {
4089
4090                 BcInstPtr *ip;
4091                 size_t *label;
4092
4093                 bc_vec_pop(&p->flags);
4094
4095                 ip = bc_vec_top(&p->exits);
4096                 label = bc_vec_item(&p->func->labels, ip->idx);
4097                 *label = p->func->code.len;
4098
4099                 bc_vec_pop(&p->exits);
4100         }
4101         else if (BC_PARSE_FUNC_INNER(p)) {
4102                 bc_parse_push(p, BC_INST_RET0);
4103                 bc_parse_updateFunc(p, BC_PROG_MAIN);
4104                 bc_vec_pop(&p->flags);
4105         }
4106         else {
4107
4108                 BcInstPtr *ip = bc_vec_top(&p->exits);
4109                 size_t *label = bc_vec_top(&p->conds);
4110
4111                 bc_parse_push(p, BC_INST_JUMP);
4112                 bc_parse_pushIndex(p, *label);
4113
4114                 label = bc_vec_item(&p->func->labels, ip->idx);
4115                 *label = p->func->code.len;
4116
4117                 bc_vec_pop(&p->flags);
4118                 bc_vec_pop(&p->exits);
4119                 bc_vec_pop(&p->conds);
4120         }
4121
4122         return s;
4123 }
4124
4125 static void bc_parse_startBody(BcParse *p, uint8_t flags)
4126 {
4127         uint8_t *flag_ptr = BC_PARSE_TOP_FLAG_PTR(p);
4128         flags |= (*flag_ptr & (BC_PARSE_FLAG_FUNC | BC_PARSE_FLAG_LOOP));
4129         flags |= BC_PARSE_FLAG_BODY;
4130         bc_vec_push(&p->flags, &flags);
4131 }
4132
4133 static void bc_parse_noElse(BcParse *p)
4134 {
4135         BcInstPtr *ip;
4136         size_t *label;
4137         uint8_t *flag_ptr = BC_PARSE_TOP_FLAG_PTR(p);
4138
4139         *flag_ptr = (*flag_ptr & ~(BC_PARSE_FLAG_IF_END));
4140
4141         ip = bc_vec_top(&p->exits);
4142         label = bc_vec_item(&p->func->labels, ip->idx);
4143         *label = p->func->code.len;
4144
4145         bc_vec_pop(&p->exits);
4146 }
4147
4148 static BcStatus bc_parse_if(BcParse *p)
4149 {
4150         BcStatus s;
4151         BcInstPtr ip;
4152
4153         s = bc_lex_next(&p->l);
4154         if (s) return s;
4155         if (p->l.t.t != BC_LEX_LPAREN) return bc_error_bad_token();
4156
4157         s = bc_lex_next(&p->l);
4158         if (s) return s;
4159         s = bc_parse_expr(p, BC_PARSE_REL, bc_parse_next_rel);
4160         if (s) return s;
4161         if (p->l.t.t != BC_LEX_RPAREN) return bc_error_bad_token();
4162
4163         s = bc_lex_next(&p->l);
4164         if (s) return s;
4165         bc_parse_push(p, BC_INST_JUMP_ZERO);
4166
4167         ip.idx = p->func->labels.len;
4168         ip.func = ip.len = 0;
4169
4170         bc_parse_pushIndex(p, ip.idx);
4171         bc_vec_push(&p->exits, &ip);
4172         bc_vec_push(&p->func->labels, &ip.idx);
4173         bc_parse_startBody(p, BC_PARSE_FLAG_IF);
4174
4175         return BC_STATUS_SUCCESS;
4176 }
4177
4178 static BcStatus bc_parse_else(BcParse *p)
4179 {
4180         BcInstPtr ip;
4181
4182         if (!BC_PARSE_IF_END(p)) return bc_error_bad_token();
4183
4184         ip.idx = p->func->labels.len;
4185         ip.func = ip.len = 0;
4186
4187         bc_parse_push(p, BC_INST_JUMP);
4188         bc_parse_pushIndex(p, ip.idx);
4189
4190         bc_parse_noElse(p);
4191
4192         bc_vec_push(&p->exits, &ip);
4193         bc_vec_push(&p->func->labels, &ip.idx);
4194         bc_parse_startBody(p, BC_PARSE_FLAG_ELSE);
4195
4196         return bc_lex_next(&p->l);
4197 }
4198
4199 static BcStatus bc_parse_while(BcParse *p)
4200 {
4201         BcStatus s;
4202         BcInstPtr ip;
4203
4204         s = bc_lex_next(&p->l);
4205         if (s) return s;
4206         if (p->l.t.t != BC_LEX_LPAREN) return bc_error_bad_token();
4207         s = bc_lex_next(&p->l);
4208         if (s) return s;
4209
4210         ip.idx = p->func->labels.len;
4211
4212         bc_vec_push(&p->func->labels, &p->func->code.len);
4213         bc_vec_push(&p->conds, &ip.idx);
4214
4215         ip.idx = p->func->labels.len;
4216         ip.func = 1;
4217         ip.len = 0;
4218
4219         bc_vec_push(&p->exits, &ip);
4220         bc_vec_push(&p->func->labels, &ip.idx);
4221
4222         s = bc_parse_expr(p, BC_PARSE_REL, bc_parse_next_rel);
4223         if (s) return s;
4224         if (p->l.t.t != BC_LEX_RPAREN) return bc_error_bad_token();
4225         s = bc_lex_next(&p->l);
4226         if (s) return s;
4227
4228         bc_parse_push(p, BC_INST_JUMP_ZERO);
4229         bc_parse_pushIndex(p, ip.idx);
4230         bc_parse_startBody(p, BC_PARSE_FLAG_LOOP | BC_PARSE_FLAG_LOOP_INNER);
4231
4232         return BC_STATUS_SUCCESS;
4233 }
4234
4235 static BcStatus bc_parse_for(BcParse *p)
4236 {
4237         BcStatus s;
4238         BcInstPtr ip;
4239         size_t cond_idx, exit_idx, body_idx, update_idx;
4240
4241         s = bc_lex_next(&p->l);
4242         if (s) return s;
4243         if (p->l.t.t != BC_LEX_LPAREN) return bc_error_bad_token();
4244         s = bc_lex_next(&p->l);
4245         if (s) return s;
4246
4247         if (p->l.t.t != BC_LEX_SCOLON)
4248                 s = bc_parse_expr(p, 0, bc_parse_next_for);
4249         else
4250                 s = bc_POSIX_does_not_allow_empty_X_expression_in_for("init");
4251
4252         if (s) return s;
4253         if (p->l.t.t != BC_LEX_SCOLON) return bc_error_bad_token();
4254         s = bc_lex_next(&p->l);
4255         if (s) return s;
4256
4257         cond_idx = p->func->labels.len;
4258         update_idx = cond_idx + 1;
4259         body_idx = update_idx + 1;
4260         exit_idx = body_idx + 1;
4261
4262         bc_vec_push(&p->func->labels, &p->func->code.len);
4263
4264         if (p->l.t.t != BC_LEX_SCOLON)
4265                 s = bc_parse_expr(p, BC_PARSE_REL, bc_parse_next_for);
4266         else
4267                 s = bc_POSIX_does_not_allow_empty_X_expression_in_for("condition");
4268
4269         if (s) return s;
4270         if (p->l.t.t != BC_LEX_SCOLON) return bc_error_bad_token();
4271
4272         s = bc_lex_next(&p->l);
4273         if (s) return s;
4274
4275         bc_parse_push(p, BC_INST_JUMP_ZERO);
4276         bc_parse_pushIndex(p, exit_idx);
4277         bc_parse_push(p, BC_INST_JUMP);
4278         bc_parse_pushIndex(p, body_idx);
4279
4280         ip.idx = p->func->labels.len;
4281
4282         bc_vec_push(&p->conds, &update_idx);
4283         bc_vec_push(&p->func->labels, &p->func->code.len);
4284
4285         if (p->l.t.t != BC_LEX_RPAREN)
4286                 s = bc_parse_expr(p, 0, bc_parse_next_rel);
4287         else
4288                 s = bc_POSIX_does_not_allow_empty_X_expression_in_for("update");
4289
4290         if (s) return s;
4291
4292         if (p->l.t.t != BC_LEX_RPAREN) return bc_error_bad_token();
4293         bc_parse_push(p, BC_INST_JUMP);
4294         bc_parse_pushIndex(p, cond_idx);
4295         bc_vec_push(&p->func->labels, &p->func->code.len);
4296
4297         ip.idx = exit_idx;
4298         ip.func = 1;
4299         ip.len = 0;
4300
4301         bc_vec_push(&p->exits, &ip);
4302         bc_vec_push(&p->func->labels, &ip.idx);
4303         bc_lex_next(&p->l);
4304         bc_parse_startBody(p, BC_PARSE_FLAG_LOOP | BC_PARSE_FLAG_LOOP_INNER);
4305
4306         return BC_STATUS_SUCCESS;
4307 }
4308
4309 static BcStatus bc_parse_loopExit(BcParse *p, BcLexType type)
4310 {
4311         BcStatus s;
4312         size_t i;
4313         BcInstPtr *ip;
4314
4315         if (!BC_PARSE_LOOP(p)) return bc_error_bad_token();
4316
4317         if (type == BC_LEX_KEY_BREAK) {
4318
4319                 if (p->exits.len == 0) return bc_error_bad_token();
4320
4321                 i = p->exits.len - 1;
4322                 ip = bc_vec_item(&p->exits, i);
4323
4324                 while (!ip->func && i < p->exits.len) ip = bc_vec_item(&p->exits, i--);
4325                 if (i >= p->exits.len && !ip->func) return bc_error_bad_token();
4326
4327                 i = ip->idx;
4328         }
4329         else
4330                 i = *((size_t *) bc_vec_top(&p->conds));
4331
4332         bc_parse_push(p, BC_INST_JUMP);
4333         bc_parse_pushIndex(p, i);
4334
4335         s = bc_lex_next(&p->l);
4336         if (s) return s;
4337
4338         if (p->l.t.t != BC_LEX_SCOLON && p->l.t.t != BC_LEX_NLINE)
4339                 return bc_error_bad_token();
4340
4341         return bc_lex_next(&p->l);
4342 }
4343
4344 static BcStatus bc_parse_func(BcParse *p)
4345 {
4346         BcStatus s;
4347         bool var, comma = false;
4348         uint8_t flags;
4349         char *name;
4350
4351         s = bc_lex_next(&p->l);
4352         if (s) return s;
4353         if (p->l.t.t != BC_LEX_NAME)
4354                 return bc_error("bad function definition");
4355
4356         name = xstrdup(p->l.t.v.v);
4357         bc_parse_addFunc(p, name, &p->fidx);
4358
4359         s = bc_lex_next(&p->l);
4360         if (s) return s;
4361         if (p->l.t.t != BC_LEX_LPAREN)
4362                 return bc_error("bad function definition");
4363         s = bc_lex_next(&p->l);
4364         if (s) return s;
4365
4366         while (p->l.t.t != BC_LEX_RPAREN) {
4367
4368                 if (p->l.t.t != BC_LEX_NAME)
4369                         return bc_error("bad function definition");
4370
4371                 ++p->func->nparams;
4372
4373                 name = xstrdup(p->l.t.v.v);
4374                 s = bc_lex_next(&p->l);
4375                 if (s) goto err;
4376
4377                 var = p->l.t.t != BC_LEX_LBRACKET;
4378
4379                 if (!var) {
4380
4381                         s = bc_lex_next(&p->l);
4382                         if (s) goto err;
4383
4384                         if (p->l.t.t != BC_LEX_RBRACKET) {
4385                                 s = bc_error("bad function definition");
4386                                 goto err;
4387                         }
4388
4389                         s = bc_lex_next(&p->l);
4390                         if (s) goto err;
4391                 }
4392
4393                 comma = p->l.t.t == BC_LEX_COMMA;
4394                 if (comma) {
4395                         s = bc_lex_next(&p->l);
4396                         if (s) goto err;
4397                 }
4398
4399                 s = bc_func_insert(p->func, name, var);
4400                 if (s) goto err;
4401         }
4402
4403         if (comma) return bc_error("bad function definition");
4404
4405         flags = BC_PARSE_FLAG_FUNC | BC_PARSE_FLAG_FUNC_INNER | BC_PARSE_FLAG_BODY;
4406         bc_parse_startBody(p, flags);
4407
4408         s = bc_lex_next(&p->l);
4409         if (s) return s;
4410
4411         if (p->l.t.t != BC_LEX_LBRACE)
4412                 s = bc_posix_error("POSIX requires the left brace be on the same line as the function header");
4413
4414         return s;
4415
4416 err:
4417         free(name);
4418         return s;
4419 }
4420
4421 static BcStatus bc_parse_auto(BcParse *p)
4422 {
4423         BcStatus s;
4424         bool comma, var, one;
4425         char *name;
4426
4427         if (!p->auto_part) return bc_error_bad_token();
4428         s = bc_lex_next(&p->l);
4429         if (s) return s;
4430
4431         p->auto_part = comma = false;
4432         one = p->l.t.t == BC_LEX_NAME;
4433
4434         while (p->l.t.t == BC_LEX_NAME) {
4435
4436                 name = xstrdup(p->l.t.v.v);
4437                 s = bc_lex_next(&p->l);
4438                 if (s) goto err;
4439
4440                 var = p->l.t.t != BC_LEX_LBRACKET;
4441                 if (!var) {
4442
4443                         s = bc_lex_next(&p->l);
4444                         if (s) goto err;
4445
4446                         if (p->l.t.t != BC_LEX_RBRACKET) {
4447                                 s = bc_error("bad function definition");
4448                                 goto err;
4449                         }
4450
4451                         s = bc_lex_next(&p->l);
4452                         if (s) goto err;
4453                 }
4454
4455                 comma = p->l.t.t == BC_LEX_COMMA;
4456                 if (comma) {
4457                         s = bc_lex_next(&p->l);
4458                         if (s) goto err;
4459                 }
4460
4461                 s = bc_func_insert(p->func, name, var);
4462                 if (s) goto err;
4463         }
4464
4465         if (comma) return bc_error("bad function definition");
4466         if (!one) return bc_error("no auto variable found");
4467
4468         if (p->l.t.t != BC_LEX_NLINE && p->l.t.t != BC_LEX_SCOLON)
4469                 return bc_error_bad_token();
4470
4471         return bc_lex_next(&p->l);
4472
4473 err:
4474         free(name);
4475         return s;
4476 }
4477
4478 static BcStatus bc_parse_body(BcParse *p, bool brace)
4479 {
4480         BcStatus s = BC_STATUS_SUCCESS;
4481         uint8_t *flag_ptr = bc_vec_top(&p->flags);
4482
4483         *flag_ptr &= ~(BC_PARSE_FLAG_BODY);
4484
4485         if (*flag_ptr & BC_PARSE_FLAG_FUNC_INNER) {
4486
4487                 if (!brace) return bc_error_bad_token();
4488                 p->auto_part = p->l.t.t != BC_LEX_KEY_AUTO;
4489
4490                 if (!p->auto_part) {
4491                         s = bc_parse_auto(p);
4492                         if (s) return s;
4493                 }
4494
4495                 if (p->l.t.t == BC_LEX_NLINE) s = bc_lex_next(&p->l);
4496         }
4497         else {
4498                 s = bc_parse_stmt(p);
4499                 if (!s && !brace) s = bc_parse_endBody(p, false);
4500         }
4501
4502         return s;
4503 }
4504
4505 static BcStatus bc_parse_stmt(BcParse *p)
4506 {
4507         BcStatus s = BC_STATUS_SUCCESS;
4508
4509         switch (p->l.t.t) {
4510
4511                 case BC_LEX_NLINE:
4512                 {
4513                         return bc_lex_next(&p->l);
4514                 }
4515
4516                 case BC_LEX_KEY_ELSE:
4517                 {
4518                         p->auto_part = false;
4519                         break;
4520                 }
4521
4522                 case BC_LEX_LBRACE:
4523                 {
4524                         if (!BC_PARSE_BODY(p)) return bc_error_bad_token();
4525
4526                         ++p->nbraces;
4527                         s = bc_lex_next(&p->l);
4528                         if (s) return s;
4529
4530                         return bc_parse_body(p, true);
4531                 }
4532
4533                 case BC_LEX_KEY_AUTO:
4534                 {
4535                         return bc_parse_auto(p);
4536                 }
4537
4538                 default:
4539                 {
4540                         p->auto_part = false;
4541
4542                         if (BC_PARSE_IF_END(p)) {
4543                                 bc_parse_noElse(p);
4544                                 return BC_STATUS_SUCCESS;
4545                         }
4546                         else if (BC_PARSE_BODY(p))
4547                                 return bc_parse_body(p, false);
4548
4549                         break;
4550                 }
4551         }
4552
4553         switch (p->l.t.t) {
4554
4555                 case BC_LEX_OP_INC:
4556                 case BC_LEX_OP_DEC:
4557                 case BC_LEX_OP_MINUS:
4558                 case BC_LEX_OP_BOOL_NOT:
4559                 case BC_LEX_LPAREN:
4560                 case BC_LEX_NAME:
4561                 case BC_LEX_NUMBER:
4562                 case BC_LEX_KEY_IBASE:
4563                 case BC_LEX_KEY_LAST:
4564                 case BC_LEX_KEY_LENGTH:
4565                 case BC_LEX_KEY_OBASE:
4566                 case BC_LEX_KEY_READ:
4567                 case BC_LEX_KEY_SCALE:
4568                 case BC_LEX_KEY_SQRT:
4569                 {
4570                         s = bc_parse_expr(p, BC_PARSE_PRINT, bc_parse_next_expr);
4571                         break;
4572                 }
4573
4574                 case BC_LEX_KEY_ELSE:
4575                 {
4576                         s = bc_parse_else(p);
4577                         break;
4578                 }
4579
4580                 case BC_LEX_SCOLON:
4581                 {
4582                         while (!s && p->l.t.t == BC_LEX_SCOLON) s = bc_lex_next(&p->l);
4583                         break;
4584                 }
4585
4586                 case BC_LEX_RBRACE:
4587                 {
4588                         s = bc_parse_endBody(p, true);
4589                         break;
4590                 }
4591
4592                 case BC_LEX_STR:
4593                 {
4594                         s = bc_parse_string(p, BC_INST_PRINT_STR);
4595                         break;
4596                 }
4597
4598                 case BC_LEX_KEY_BREAK:
4599                 case BC_LEX_KEY_CONTINUE:
4600                 {
4601                         s = bc_parse_loopExit(p, p->l.t.t);
4602                         break;
4603                 }
4604
4605                 case BC_LEX_KEY_FOR:
4606                 {
4607                         s = bc_parse_for(p);
4608                         break;
4609                 }
4610
4611                 case BC_LEX_KEY_HALT:
4612                 {
4613                         bc_parse_push(p, BC_INST_HALT);
4614                         s = bc_lex_next(&p->l);
4615                         break;
4616                 }
4617
4618                 case BC_LEX_KEY_IF:
4619                 {
4620                         s = bc_parse_if(p);
4621                         break;
4622                 }
4623
4624                 case BC_LEX_KEY_LIMITS:
4625                 {
4626                         // "limits" is a compile-time command,
4627                         // the output is produced at _parse time_.
4628                         s = bc_lex_next(&p->l);
4629                         if (s) return s;
4630                         printf("BC_BASE_MAX     = %u\n", BC_MAX_OBASE);
4631                         printf("BC_DIM_MAX      = %u\n", BC_MAX_DIM);
4632                         printf("BC_SCALE_MAX    = %u\n", BC_MAX_SCALE);
4633                         printf("BC_STRING_MAX   = %u\n", BC_MAX_STRING);
4634                         printf("BC_NAME_MAX     = %u\n", BC_MAX_NAME);
4635                         printf("BC_NUM_MAX      = %u\n", BC_MAX_NUM);
4636                         printf("MAX Exponent    = %lu\n", BC_MAX_EXP);
4637                         printf("Number of vars  = %lu\n", BC_MAX_VARS);
4638                         break;
4639                 }
4640
4641                 case BC_LEX_KEY_PRINT:
4642                 {
4643                         s = bc_parse_print(p);
4644                         break;
4645                 }
4646
4647                 case BC_LEX_KEY_QUIT:
4648                 {
4649                         // "quit" is a compile-time command. For example,
4650                         // "if (0 == 1) quit" terminates when parsing the statement,
4651                         // not when it is executed
4652                         quit();
4653                 }
4654
4655                 case BC_LEX_KEY_RETURN:
4656                 {
4657                         s = bc_parse_return(p);
4658                         break;
4659                 }
4660
4661                 case BC_LEX_KEY_WHILE:
4662                 {
4663                         s = bc_parse_while(p);
4664                         break;
4665                 }
4666
4667                 default:
4668                 {
4669                         s = bc_error_bad_token();
4670                         break;
4671                 }
4672         }
4673
4674         return s;
4675 }
4676
4677 static BcStatus bc_parse_parse(BcParse *p)
4678 {
4679         BcStatus s;
4680
4681         if (p->l.t.t == BC_LEX_EOF)
4682                 s = p->flags.len > 0 ? bc_error("block end could not be found") : bc_error("end of file");
4683         else if (p->l.t.t == BC_LEX_KEY_DEFINE) {
4684                 if (!BC_PARSE_CAN_EXEC(p)) return bc_error_bad_token();
4685                 s = bc_parse_func(p);
4686         }
4687         else
4688                 s = bc_parse_stmt(p);
4689
4690         if (s || G_interrupt) {
4691                 bc_parse_reset(p);
4692                 s = BC_STATUS_FAILURE;
4693         }
4694
4695         return s;
4696 }
4697
4698 static BcStatus bc_parse_expr(BcParse *p, uint8_t flags, BcParseNext next)
4699 {
4700         BcStatus s = BC_STATUS_SUCCESS;
4701         BcInst prev = BC_INST_PRINT;
4702         BcLexType top, t = p->l.t.t;
4703         size_t nexprs = 0, ops_bgn = p->ops.len;
4704         uint32_t i, nparens, nrelops;
4705         bool paren_first, paren_expr, rprn, done, get_token, assign, bin_last;
4706
4707         paren_first = p->l.t.t == BC_LEX_LPAREN;
4708         nparens = nrelops = 0;
4709         paren_expr = rprn = done = get_token = assign = false;
4710         bin_last = true;
4711
4712         for (; !G_interrupt && !s && !done && bc_parse_exprs[t]; t = p->l.t.t) {
4713                 switch (t) {
4714
4715                         case BC_LEX_OP_INC:
4716                         case BC_LEX_OP_DEC:
4717                         {
4718                                 s = bc_parse_incdec(p, &prev, &paren_expr, &nexprs, flags);
4719                                 rprn = get_token = bin_last = false;
4720                                 break;
4721                         }
4722
4723                         case BC_LEX_OP_MINUS:
4724                         {
4725                                 s = bc_parse_minus(p, &prev, ops_bgn, rprn, &nexprs);
4726                                 rprn = get_token = false;
4727                                 bin_last = prev == BC_INST_MINUS;
4728                                 break;
4729                         }
4730
4731                         case BC_LEX_OP_ASSIGN_POWER:
4732                         case BC_LEX_OP_ASSIGN_MULTIPLY:
4733                         case BC_LEX_OP_ASSIGN_DIVIDE:
4734                         case BC_LEX_OP_ASSIGN_MODULUS:
4735                         case BC_LEX_OP_ASSIGN_PLUS:
4736                         case BC_LEX_OP_ASSIGN_MINUS:
4737                         case BC_LEX_OP_ASSIGN:
4738                         {
4739                                 if (prev != BC_INST_VAR && prev != BC_INST_ARRAY_ELEM &&
4740                                     prev != BC_INST_SCALE && prev != BC_INST_IBASE &&
4741                                     prev != BC_INST_OBASE && prev != BC_INST_LAST)
4742                                 {
4743                                         s = bc_error("bad assignment:"
4744                                                 " left side must be scale,"
4745                                                 " ibase, obase, last, var,"
4746                                                 " or array element"
4747                                         );
4748                                         break;
4749                                 }
4750                         }
4751                         // Fallthrough.
4752                         case BC_LEX_OP_POWER:
4753                         case BC_LEX_OP_MULTIPLY:
4754                         case BC_LEX_OP_DIVIDE:
4755                         case BC_LEX_OP_MODULUS:
4756                         case BC_LEX_OP_PLUS:
4757                         case BC_LEX_OP_REL_EQ:
4758                         case BC_LEX_OP_REL_LE:
4759                         case BC_LEX_OP_REL_GE:
4760                         case BC_LEX_OP_REL_NE:
4761                         case BC_LEX_OP_REL_LT:
4762                         case BC_LEX_OP_REL_GT:
4763                         case BC_LEX_OP_BOOL_NOT:
4764                         case BC_LEX_OP_BOOL_OR:
4765                         case BC_LEX_OP_BOOL_AND:
4766                         {
4767                                 if (((t == BC_LEX_OP_BOOL_NOT) != bin_last)
4768                                  || (t != BC_LEX_OP_BOOL_NOT && prev == BC_INST_BOOL_NOT)
4769                                 ) {
4770                                         return bc_error_bad_expression();
4771                                 }
4772
4773                                 nrelops += t >= BC_LEX_OP_REL_EQ && t <= BC_LEX_OP_REL_GT;
4774                                 prev = BC_PARSE_TOKEN_INST(t);
4775                                 s = bc_parse_operator(p, t, ops_bgn, &nexprs, true);
4776                                 rprn = get_token = false;
4777                                 bin_last = t != BC_LEX_OP_BOOL_NOT;
4778
4779                                 break;
4780                         }
4781
4782                         case BC_LEX_LPAREN:
4783                         {
4784                                 if (BC_PARSE_LEAF(prev, rprn))
4785                                         return bc_error_bad_expression();
4786                                 ++nparens;
4787                                 paren_expr = rprn = bin_last = false;
4788                                 get_token = true;
4789                                 bc_vec_push(&p->ops, &t);
4790
4791                                 break;
4792                         }
4793
4794                         case BC_LEX_RPAREN:
4795                         {
4796                                 if (bin_last || prev == BC_INST_BOOL_NOT)
4797                                         return bc_error_bad_expression();
4798
4799                                 if (nparens == 0) {
4800                                         s = BC_STATUS_SUCCESS;
4801                                         done = true;
4802                                         get_token = false;
4803                                         break;
4804                                 }
4805                                 else if (!paren_expr)
4806                                         return BC_STATUS_PARSE_EMPTY_EXP;
4807
4808                                 --nparens;
4809                                 paren_expr = rprn = true;
4810                                 get_token = bin_last = false;
4811
4812                                 s = bc_parse_rightParen(p, ops_bgn, &nexprs);
4813
4814                                 break;
4815                         }
4816
4817                         case BC_LEX_NAME:
4818                         {
4819                                 if (BC_PARSE_LEAF(prev, rprn))
4820                                         return bc_error_bad_expression();
4821                                 paren_expr = true;
4822                                 rprn = get_token = bin_last = false;
4823                                 s = bc_parse_name(p, &prev, flags & ~BC_PARSE_NOCALL);
4824                                 ++nexprs;
4825
4826                                 break;
4827                         }
4828
4829                         case BC_LEX_NUMBER:
4830                         {
4831                                 if (BC_PARSE_LEAF(prev, rprn))
4832                                         return bc_error_bad_expression();
4833                                 bc_parse_number(p, &prev, &nexprs);
4834                                 paren_expr = get_token = true;
4835                                 rprn = bin_last = false;
4836
4837                                 break;
4838                         }
4839
4840                         case BC_LEX_KEY_IBASE:
4841                         case BC_LEX_KEY_LAST:
4842                         case BC_LEX_KEY_OBASE:
4843                         {
4844                                 if (BC_PARSE_LEAF(prev, rprn))
4845                                         return bc_error_bad_expression();
4846                                 prev = (char) (t - BC_LEX_KEY_IBASE + BC_INST_IBASE);
4847                                 bc_parse_push(p, (char) prev);
4848
4849                                 paren_expr = get_token = true;
4850                                 rprn = bin_last = false;
4851                                 ++nexprs;
4852
4853                                 break;
4854                         }
4855
4856                         case BC_LEX_KEY_LENGTH:
4857                         case BC_LEX_KEY_SQRT:
4858                         {
4859                                 if (BC_PARSE_LEAF(prev, rprn))
4860                                         return bc_error_bad_expression();
4861                                 s = bc_parse_builtin(p, t, flags, &prev);
4862                                 paren_expr = true;
4863                                 rprn = get_token = bin_last = false;
4864                                 ++nexprs;
4865
4866                                 break;
4867                         }
4868
4869                         case BC_LEX_KEY_READ:
4870                         {
4871                                 if (BC_PARSE_LEAF(prev, rprn))
4872                                         return bc_error_bad_expression();
4873                                 else if (flags & BC_PARSE_NOREAD)
4874                                         s = bc_error_nested_read_call();
4875                                 else
4876                                         s = bc_parse_read(p);
4877
4878                                 paren_expr = true;
4879                                 rprn = get_token = bin_last = false;
4880                                 ++nexprs;
4881                                 prev = BC_INST_READ;
4882
4883                                 break;
4884                         }
4885
4886                         case BC_LEX_KEY_SCALE:
4887                         {
4888                                 if (BC_PARSE_LEAF(prev, rprn))
4889                                         return bc_error_bad_expression();
4890                                 s = bc_parse_scale(p, &prev, flags);
4891                                 paren_expr = true;
4892                                 rprn = get_token = bin_last = false;
4893                                 ++nexprs;
4894                                 prev = BC_INST_SCALE;
4895
4896                                 break;
4897                         }
4898
4899                         default:
4900                         {
4901                                 s = bc_error_bad_token();
4902                                 break;
4903                         }
4904                 }
4905
4906                 if (!s && get_token) s = bc_lex_next(&p->l);
4907         }
4908
4909         if (s) return s;
4910         if (G_interrupt) return BC_STATUS_FAILURE; // ^C: stop parsing
4911
4912         while (p->ops.len > ops_bgn) {
4913
4914                 top = BC_PARSE_TOP_OP(p);
4915                 assign = top >= BC_LEX_OP_ASSIGN_POWER && top <= BC_LEX_OP_ASSIGN;
4916
4917                 if (top == BC_LEX_LPAREN || top == BC_LEX_RPAREN)
4918                         return bc_error_bad_expression();
4919
4920                 bc_parse_push(p, BC_PARSE_TOKEN_INST(top));
4921
4922                 nexprs -= top != BC_LEX_OP_BOOL_NOT && top != BC_LEX_NEG;
4923                 bc_vec_pop(&p->ops);
4924         }
4925
4926         if (prev == BC_INST_BOOL_NOT || nexprs != 1)
4927                 return bc_error_bad_expression();
4928
4929         for (i = 0; i < next.len; ++i)
4930                 if (t == next.tokens[i])
4931                         goto ok;
4932         return bc_error_bad_expression();
4933  ok:
4934
4935         if (!(flags & BC_PARSE_REL) && nrelops) {
4936                 s = bc_POSIX_does_not_allow("comparison operators outside if or loops");
4937                 if (s) return s;
4938         }
4939         else if ((flags & BC_PARSE_REL) && nrelops > 1) {
4940                 s = bc_posix_error("POSIX requires exactly one comparison operator per condition");
4941                 if (s) return s;
4942         }
4943
4944         if (flags & BC_PARSE_PRINT) {
4945                 if (paren_first || !assign) bc_parse_push(p, BC_INST_PRINT);
4946                 bc_parse_push(p, BC_INST_POP);
4947         }
4948
4949         return s;
4950 }
4951
4952 static void bc_parse_init(BcParse *p, size_t func)
4953 {
4954         bc_parse_create(p, func, bc_parse_parse, bc_lex_token);
4955 }
4956
4957 static BcStatus bc_parse_expression(BcParse *p, uint8_t flags)
4958 {
4959         return bc_parse_expr(p, flags, bc_parse_next_read);
4960 }
4961 #endif // ENABLE_BC
4962
4963 #if ENABLE_DC
4964 static BcStatus dc_parse_register(BcParse *p)
4965 {
4966         BcStatus s;
4967         char *name;
4968
4969         s = bc_lex_next(&p->l);
4970         if (s) return s;
4971         if (p->l.t.t != BC_LEX_NAME) return bc_error_bad_token();
4972
4973         name = xstrdup(p->l.t.v.v);
4974         bc_parse_pushName(p, name);
4975
4976         return s;
4977 }
4978
4979 static BcStatus dc_parse_string(BcParse *p)
4980 {
4981         char *str, *name, b[DC_PARSE_BUF_LEN + 1];
4982         size_t idx, len = G.prog.strs.len;
4983
4984         sprintf(b, "%0*zu", DC_PARSE_BUF_LEN, len);
4985         name = xstrdup(b);
4986
4987         str = xstrdup(p->l.t.v.v);
4988         bc_parse_push(p, BC_INST_STR);
4989         bc_parse_pushIndex(p, len);
4990         bc_vec_push(&G.prog.strs, &str);
4991         bc_parse_addFunc(p, name, &idx);
4992
4993         return bc_lex_next(&p->l);
4994 }
4995
4996 static BcStatus dc_parse_mem(BcParse *p, uint8_t inst, bool name, bool store)
4997 {
4998         BcStatus s;
4999
5000         bc_parse_push(p, inst);
5001         if (name) {
5002                 s = dc_parse_register(p);
5003                 if (s) return s;
5004         }
5005
5006         if (store) {
5007                 bc_parse_push(p, BC_INST_SWAP);
5008                 bc_parse_push(p, BC_INST_ASSIGN);
5009                 bc_parse_push(p, BC_INST_POP);
5010         }
5011
5012         return bc_lex_next(&p->l);
5013 }
5014
5015 static BcStatus dc_parse_cond(BcParse *p, uint8_t inst)
5016 {
5017         BcStatus s;
5018
5019         bc_parse_push(p, inst);
5020         bc_parse_push(p, BC_INST_EXEC_COND);
5021
5022         s = dc_parse_register(p);
5023         if (s) return s;
5024
5025         s = bc_lex_next(&p->l);
5026         if (s) return s;
5027
5028         if (p->l.t.t == BC_LEX_ELSE) {
5029                 s = dc_parse_register(p);
5030                 if (s) return s;
5031                 s = bc_lex_next(&p->l);
5032         }
5033         else
5034                 bc_parse_push(p, BC_PARSE_STREND);
5035
5036         return s;
5037 }
5038
5039 static BcStatus dc_parse_token(BcParse *p, BcLexType t, uint8_t flags)
5040 {
5041         BcStatus s = BC_STATUS_SUCCESS;
5042         BcInst prev;
5043         uint8_t inst;
5044         bool assign, get_token = false;
5045
5046         switch (t) {
5047
5048                 case BC_LEX_OP_REL_EQ:
5049                 case BC_LEX_OP_REL_LE:
5050                 case BC_LEX_OP_REL_GE:
5051                 case BC_LEX_OP_REL_NE:
5052                 case BC_LEX_OP_REL_LT:
5053                 case BC_LEX_OP_REL_GT:
5054                 {
5055                         s = dc_parse_cond(p, t - BC_LEX_OP_REL_EQ + BC_INST_REL_EQ);
5056                         break;
5057                 }
5058
5059                 case BC_LEX_SCOLON:
5060                 case BC_LEX_COLON:
5061                 {
5062                         s = dc_parse_mem(p, BC_INST_ARRAY_ELEM, true, t == BC_LEX_COLON);
5063                         break;
5064                 }
5065
5066                 case BC_LEX_STR:
5067                 {
5068                         s = dc_parse_string(p);
5069                         break;
5070                 }
5071
5072                 case BC_LEX_NEG:
5073                 case BC_LEX_NUMBER:
5074                 {
5075                         if (t == BC_LEX_NEG) {
5076                                 s = bc_lex_next(&p->l);
5077                                 if (s) return s;
5078                                 if (p->l.t.t != BC_LEX_NUMBER)
5079                                         return bc_error_bad_token();
5080                         }
5081
5082                         bc_parse_number(p, &prev, &p->nbraces);
5083
5084                         if (t == BC_LEX_NEG) bc_parse_push(p, BC_INST_NEG);
5085                         get_token = true;
5086
5087                         break;
5088                 }
5089
5090                 case BC_LEX_KEY_READ:
5091                 {
5092                         if (flags & BC_PARSE_NOREAD)
5093                                 s = bc_error_nested_read_call();
5094                         else
5095                                 bc_parse_push(p, BC_INST_READ);
5096                         get_token = true;
5097                         break;
5098                 }
5099
5100                 case BC_LEX_OP_ASSIGN:
5101                 case BC_LEX_STORE_PUSH:
5102                 {
5103                         assign = t == BC_LEX_OP_ASSIGN;
5104                         inst = assign ? BC_INST_VAR : BC_INST_PUSH_TO_VAR;
5105                         s = dc_parse_mem(p, inst, true, assign);
5106                         break;
5107                 }
5108
5109                 case BC_LEX_LOAD:
5110                 case BC_LEX_LOAD_POP:
5111                 {
5112                         inst = t == BC_LEX_LOAD_POP ? BC_INST_PUSH_VAR : BC_INST_LOAD;
5113                         s = dc_parse_mem(p, inst, true, false);
5114                         break;
5115                 }
5116
5117                 case BC_LEX_STORE_IBASE:
5118                 case BC_LEX_STORE_SCALE:
5119                 case BC_LEX_STORE_OBASE:
5120                 {
5121                         inst = t - BC_LEX_STORE_IBASE + BC_INST_IBASE;
5122                         s = dc_parse_mem(p, inst, false, true);
5123                         break;
5124                 }
5125
5126                 default:
5127                 {
5128                         s = bc_error_bad_token();
5129                         get_token = true;
5130                         break;
5131                 }
5132         }
5133
5134         if (!s && get_token) s = bc_lex_next(&p->l);
5135
5136         return s;
5137 }
5138
5139 static BcStatus dc_parse_expr(BcParse *p, uint8_t flags)
5140 {
5141         BcStatus s = BC_STATUS_SUCCESS;
5142         BcInst inst;
5143         BcLexType t;
5144
5145         if (flags & BC_PARSE_NOCALL) p->nbraces = G.prog.results.len;
5146
5147         for (t = p->l.t.t; !s && t != BC_LEX_EOF; t = p->l.t.t) {
5148
5149                 inst = dc_parse_insts[t];
5150
5151                 if (inst != BC_INST_INVALID) {
5152                         bc_parse_push(p, inst);
5153                         s = bc_lex_next(&p->l);
5154                 }
5155                 else
5156                         s = dc_parse_token(p, t, flags);
5157         }
5158
5159         if (!s && p->l.t.t == BC_LEX_EOF && (flags & BC_PARSE_NOCALL))
5160                 bc_parse_push(p, BC_INST_POP_EXEC);
5161
5162         return s;
5163 }
5164
5165 static BcStatus dc_parse_parse(BcParse *p)
5166 {
5167         BcStatus s;
5168
5169         if (p->l.t.t == BC_LEX_EOF)
5170                 s = bc_error("end of file");
5171         else
5172                 s = dc_parse_expr(p, 0);
5173
5174         if (s || G_interrupt) {
5175                 bc_parse_reset(p);
5176                 s = BC_STATUS_FAILURE;
5177         }
5178
5179         return s;
5180 }
5181
5182 static void dc_parse_init(BcParse *p, size_t func)
5183 {
5184         bc_parse_create(p, func, dc_parse_parse, dc_lex_token);
5185 }
5186 #endif // ENABLE_DC
5187
5188 static void common_parse_init(BcParse *p, size_t func)
5189 {
5190         if (IS_BC) {
5191                 bc_parse_init(p, func);
5192         } else {
5193                 dc_parse_init(p, func);
5194         }
5195 }
5196
5197 static BcStatus common_parse_expr(BcParse *p, uint8_t flags)
5198 {
5199         if (IS_BC) {
5200                 return bc_parse_expression(p, flags);
5201         } else {
5202                 return dc_parse_expr(p, flags);
5203         }
5204 }
5205
5206 static BcVec* bc_program_search(char *id, bool var)
5207 {
5208         BcId e, *ptr;
5209         BcVec *v, *map;
5210         size_t i;
5211         BcResultData data;
5212         int new;
5213
5214         v = var ? &G.prog.vars : &G.prog.arrs;
5215         map = var ? &G.prog.var_map : &G.prog.arr_map;
5216
5217         e.name = id;
5218         e.idx = v->len;
5219         new = bc_map_insert(map, &e, &i); // 1 if insertion was successful
5220
5221         if (new) {
5222                 bc_array_init(&data.v, var);
5223                 bc_vec_push(v, &data.v);
5224         }
5225
5226         ptr = bc_vec_item(map, i);
5227         if (new) ptr->name = xstrdup(e.name);
5228         return bc_vec_item(v, ptr->idx);
5229 }
5230
5231 static BcStatus bc_program_num(BcResult *r, BcNum **num, bool hex)
5232 {
5233         BcStatus s = BC_STATUS_SUCCESS;
5234
5235         switch (r->t) {
5236
5237                 case BC_RESULT_STR:
5238                 case BC_RESULT_TEMP:
5239                 case BC_RESULT_IBASE:
5240                 case BC_RESULT_SCALE:
5241                 case BC_RESULT_OBASE:
5242                 {
5243                         *num = &r->d.n;
5244                         break;
5245                 }
5246
5247                 case BC_RESULT_CONSTANT:
5248                 {
5249                         char **str = bc_vec_item(&G.prog.consts, r->d.id.idx);
5250                         size_t base_t, len = strlen(*str);
5251                         BcNum *base;
5252
5253                         bc_num_init(&r->d.n, len);
5254
5255                         hex = hex && len == 1;
5256                         base = hex ? &G.prog.hexb : &G.prog.ib;
5257                         base_t = hex ? BC_NUM_MAX_IBASE : G.prog.ib_t;
5258                         s = bc_num_parse(&r->d.n, *str, base, base_t);
5259
5260                         if (s) {
5261                                 bc_num_free(&r->d.n);
5262                                 return s;
5263                         }
5264
5265                         *num = &r->d.n;
5266                         r->t = BC_RESULT_TEMP;
5267
5268                         break;
5269                 }
5270
5271                 case BC_RESULT_VAR:
5272                 case BC_RESULT_ARRAY:
5273                 case BC_RESULT_ARRAY_ELEM:
5274                 {
5275                         BcVec *v;
5276
5277                         v = bc_program_search(r->d.id.name, r->t == BC_RESULT_VAR);
5278
5279                         if (r->t == BC_RESULT_ARRAY_ELEM) {
5280                                 v = bc_vec_top(v);
5281                                 if (v->len <= r->d.id.idx) bc_array_expand(v, r->d.id.idx + 1);
5282                                 *num = bc_vec_item(v, r->d.id.idx);
5283                         }
5284                         else
5285                                 *num = bc_vec_top(v);
5286
5287                         break;
5288                 }
5289
5290                 case BC_RESULT_LAST:
5291                 {
5292                         *num = &G.prog.last;
5293                         break;
5294                 }
5295
5296                 case BC_RESULT_ONE:
5297                 {
5298                         *num = &G.prog.one;
5299                         break;
5300                 }
5301         }
5302
5303         return s;
5304 }
5305
5306 static BcStatus bc_program_binOpPrep(BcResult **l, BcNum **ln,
5307                                      BcResult **r, BcNum **rn, bool assign)
5308 {
5309         BcStatus s;
5310         bool hex;
5311         BcResultType lt, rt;
5312
5313         if (!BC_PROG_STACK(&G.prog.results, 2))
5314                 return bc_error_stack_has_too_few_elements();
5315
5316         *r = bc_vec_item_rev(&G.prog.results, 0);
5317         *l = bc_vec_item_rev(&G.prog.results, 1);
5318
5319         lt = (*l)->t;
5320         rt = (*r)->t;
5321         hex = assign && (lt == BC_RESULT_IBASE || lt == BC_RESULT_OBASE);
5322
5323         s = bc_program_num(*l, ln, false);
5324         if (s) return s;
5325         s = bc_program_num(*r, rn, hex);
5326         if (s) return s;
5327
5328         // We run this again under these conditions in case any vector has been
5329         // reallocated out from under the BcNums or arrays we had.
5330         if (lt == rt && (lt == BC_RESULT_VAR || lt == BC_RESULT_ARRAY_ELEM)) {
5331                 s = bc_program_num(*l, ln, false);
5332                 if (s) return s;
5333         }
5334
5335         if (!BC_PROG_NUM((*l), (*ln)) && (!assign || (*l)->t != BC_RESULT_VAR))
5336                 return bc_error_variable_is_wrong_type();
5337         if (!assign && !BC_PROG_NUM((*r), (*ln)))
5338                 return bc_error_variable_is_wrong_type();
5339
5340         return s;
5341 }
5342
5343 static void bc_program_binOpRetire(BcResult *r)
5344 {
5345         r->t = BC_RESULT_TEMP;
5346         bc_vec_pop(&G.prog.results);
5347         bc_vec_pop(&G.prog.results);
5348         bc_vec_push(&G.prog.results, r);
5349 }
5350
5351 static BcStatus bc_program_prep(BcResult **r, BcNum **n)
5352 {
5353         BcStatus s;
5354
5355         if (!BC_PROG_STACK(&G.prog.results, 1))
5356                 return bc_error_stack_has_too_few_elements();
5357         *r = bc_vec_top(&G.prog.results);
5358
5359         s = bc_program_num(*r, n, false);
5360         if (s) return s;
5361
5362         if (!BC_PROG_NUM((*r), (*n)))
5363                 return bc_error_variable_is_wrong_type();
5364
5365         return s;
5366 }
5367
5368 static void bc_program_retire(BcResult *r, BcResultType t)
5369 {
5370         r->t = t;
5371         bc_vec_pop(&G.prog.results);
5372         bc_vec_push(&G.prog.results, r);
5373 }
5374
5375 static BcStatus bc_program_op(char inst)
5376 {
5377         BcStatus s;
5378         BcResult *opd1, *opd2, res;
5379         BcNum *n1, *n2 = NULL;
5380
5381         s = bc_program_binOpPrep(&opd1, &n1, &opd2, &n2, false);
5382         if (s) return s;
5383         bc_num_init(&res.d.n, BC_NUM_DEF_SIZE);
5384
5385         s = bc_program_ops[inst - BC_INST_POWER](n1, n2, &res.d.n, G.prog.scale);
5386         if (s) goto err;
5387         bc_program_binOpRetire(&res);
5388
5389         return s;
5390
5391 err:
5392         bc_num_free(&res.d.n);
5393         return s;
5394 }
5395
5396 static BcStatus bc_program_read(void)
5397 {
5398         const char *sv_file;
5399         BcStatus s;
5400         BcParse parse;
5401         BcVec buf;
5402         BcInstPtr ip;
5403         size_t i;
5404         BcFunc *f = bc_vec_item(&G.prog.fns, BC_PROG_READ);
5405
5406         for (i = 0; i < G.prog.stack.len; ++i) {
5407                 BcInstPtr *ip_ptr = bc_vec_item(&G.prog.stack, i);
5408                 if (ip_ptr->func == BC_PROG_READ)
5409                         return bc_error_nested_read_call();
5410         }
5411
5412         bc_vec_pop_all(&f->code);
5413         bc_char_vec_init(&buf);
5414
5415         sv_file = G.prog.file;
5416         G.prog.file = NULL;
5417
5418         s = bc_read_line(&buf, "read> ");
5419         if (s) goto io_err;
5420
5421         common_parse_init(&parse, BC_PROG_READ);
5422         bc_lex_file(&parse.l);
5423
5424         s = bc_parse_text(&parse, buf.v);
5425         if (s) goto exec_err;
5426         s = common_parse_expr(&parse, BC_PARSE_NOREAD);
5427         if (s) goto exec_err;
5428
5429         if (parse.l.t.t != BC_LEX_NLINE && parse.l.t.t != BC_LEX_EOF) {
5430                 s = bc_error("bad read() expression");
5431                 goto exec_err;
5432         }
5433
5434         ip.func = BC_PROG_READ;
5435         ip.idx = 0;
5436         ip.len = G.prog.results.len;
5437
5438         // Update this pointer, just in case.
5439         f = bc_vec_item(&G.prog.fns, BC_PROG_READ);
5440
5441         bc_vec_pushByte(&f->code, BC_INST_POP_EXEC);
5442         bc_vec_push(&G.prog.stack, &ip);
5443
5444 exec_err:
5445         G.prog.file = sv_file;
5446         bc_parse_free(&parse);
5447 io_err:
5448         bc_vec_free(&buf);
5449         return s;
5450 }
5451
5452 static size_t bc_program_index(char *code, size_t *bgn)
5453 {
5454         char amt = code[(*bgn)++], i = 0;
5455         size_t res = 0;
5456
5457         for (; i < amt; ++i, ++(*bgn))
5458                 res |= (((size_t)((int) code[*bgn]) & UCHAR_MAX) << (i * CHAR_BIT));
5459
5460         return res;
5461 }
5462
5463 static char *bc_program_name(char *code, size_t *bgn)
5464 {
5465         size_t i;
5466         char c, *s, *str = code + *bgn, *ptr = strchr(str, BC_PARSE_STREND);
5467
5468         s = xmalloc(ptr - str + 1);
5469         c = code[(*bgn)++];
5470
5471         for (i = 0; c != 0 && c != BC_PARSE_STREND; c = code[(*bgn)++], ++i)
5472                 s[i] = c;
5473
5474         s[i] = '\0';
5475
5476         return s;
5477 }
5478
5479 static void bc_program_printString(const char *str, size_t *nchars)
5480 {
5481         size_t i, len = strlen(str);
5482
5483 #if ENABLE_DC
5484         if (len == 0) {
5485                 bb_putchar('\0');
5486                 return;
5487         }
5488 #endif
5489
5490         for (i = 0; i < len; ++i, ++(*nchars)) {
5491
5492                 int c = str[i];
5493
5494                 if (c != '\\' || i == len - 1)
5495                         bb_putchar(c);
5496                 else {
5497
5498                         c = str[++i];
5499
5500                         switch (c) {
5501
5502                                 case 'a':
5503                                 {
5504                                         bb_putchar('\a');
5505                                         break;
5506                                 }
5507
5508                                 case 'b':
5509                                 {
5510                                         bb_putchar('\b');
5511                                         break;
5512                                 }
5513
5514                                 case '\\':
5515                                 case 'e':
5516                                 {
5517                                         bb_putchar('\\');
5518                                         break;
5519                                 }
5520
5521                                 case 'f':
5522                                 {
5523                                         bb_putchar('\f');
5524                                         break;
5525                                 }
5526
5527                                 case 'n':
5528                                 {
5529                                         bb_putchar('\n');
5530                                         *nchars = SIZE_MAX;
5531                                         break;
5532                                 }
5533
5534                                 case 'r':
5535                                 {
5536                                         bb_putchar('\r');
5537                                         break;
5538                                 }
5539
5540                                 case 'q':
5541                                 {
5542                                         bb_putchar('"');
5543                                         break;
5544                                 }
5545
5546                                 case 't':
5547                                 {
5548                                         bb_putchar('\t');
5549                                         break;
5550                                 }
5551
5552                                 default:
5553                                 {
5554                                         // Just print the backslash and following character.
5555                                         bb_putchar('\\');
5556                                         ++(*nchars);
5557                                         bb_putchar(c);
5558                                         break;
5559                                 }
5560                         }
5561                 }
5562         }
5563 }
5564
5565 static BcStatus bc_program_print(char inst, size_t idx)
5566 {
5567         BcStatus s = BC_STATUS_SUCCESS;
5568         BcResult *r;
5569         size_t len, i;
5570         char *str;
5571         BcNum *num = NULL;
5572         bool pop = inst != BC_INST_PRINT;
5573
5574         if (!BC_PROG_STACK(&G.prog.results, idx + 1))
5575                 return bc_error_stack_has_too_few_elements();
5576
5577         r = bc_vec_item_rev(&G.prog.results, idx);
5578         s = bc_program_num(r, &num, false);
5579         if (s) return s;
5580
5581         if (BC_PROG_NUM(r, num)) {
5582                 s = bc_num_print(num, &G.prog.ob, G.prog.ob_t, !pop, &G.prog.nchars, G.prog.len);
5583                 if (!s) bc_num_copy(&G.prog.last, num);
5584         }
5585         else {
5586
5587                 idx = (r->t == BC_RESULT_STR) ? r->d.id.idx : num->rdx;
5588                 str = *((char **) bc_vec_item(&G.prog.strs, idx));
5589
5590                 if (inst == BC_INST_PRINT_STR) {
5591                         for (i = 0, len = strlen(str); i < len; ++i) {
5592                                 char c = str[i];
5593                                 bb_putchar(c);
5594                                 if (c == '\n') G.prog.nchars = SIZE_MAX;
5595                                 ++G.prog.nchars;
5596                         }
5597                 }
5598                 else {
5599                         bc_program_printString(str, &G.prog.nchars);
5600                         if (inst == BC_INST_PRINT) bb_putchar('\n');
5601                 }
5602         }
5603
5604         if (!s && pop) bc_vec_pop(&G.prog.results);
5605
5606         return s;
5607 }
5608
5609 static BcStatus bc_program_negate(void)
5610 {
5611         BcStatus s;
5612         BcResult res, *ptr;
5613         BcNum *num = NULL;
5614
5615         s = bc_program_prep(&ptr, &num);
5616         if (s) return s;
5617
5618         bc_num_init(&res.d.n, num->len);
5619         bc_num_copy(&res.d.n, num);
5620         if (res.d.n.len) res.d.n.neg = !res.d.n.neg;
5621
5622         bc_program_retire(&res, BC_RESULT_TEMP);
5623
5624         return s;
5625 }
5626
5627 static BcStatus bc_program_logical(char inst)
5628 {
5629         BcStatus s;
5630         BcResult *opd1, *opd2, res;
5631         BcNum *n1, *n2;
5632         bool cond = 0;
5633         ssize_t cmp;
5634
5635         s = bc_program_binOpPrep(&opd1, &n1, &opd2, &n2, false);
5636         if (s) return s;
5637         bc_num_init(&res.d.n, BC_NUM_DEF_SIZE);
5638
5639         if (inst == BC_INST_BOOL_AND)
5640                 cond = bc_num_cmp(n1, &G.prog.zero) && bc_num_cmp(n2, &G.prog.zero);
5641         else if (inst == BC_INST_BOOL_OR)
5642                 cond = bc_num_cmp(n1, &G.prog.zero) || bc_num_cmp(n2, &G.prog.zero);
5643         else {
5644
5645                 cmp = bc_num_cmp(n1, n2);
5646
5647                 switch (inst) {
5648
5649                         case BC_INST_REL_EQ:
5650                         {
5651                                 cond = cmp == 0;
5652                                 break;
5653                         }
5654
5655                         case BC_INST_REL_LE:
5656                         {
5657                                 cond = cmp <= 0;
5658                                 break;
5659                         }
5660
5661                         case BC_INST_REL_GE:
5662                         {
5663                                 cond = cmp >= 0;
5664                                 break;
5665                         }
5666
5667                         case BC_INST_REL_NE:
5668                         {
5669                                 cond = cmp != 0;
5670                                 break;
5671                         }
5672
5673                         case BC_INST_REL_LT:
5674                         {
5675                                 cond = cmp < 0;
5676                                 break;
5677                         }
5678
5679                         case BC_INST_REL_GT:
5680                         {
5681                                 cond = cmp > 0;
5682                                 break;
5683                         }
5684                 }
5685         }
5686
5687         (cond ? bc_num_one : bc_num_zero)(&res.d.n);
5688
5689         bc_program_binOpRetire(&res);
5690
5691         return s;
5692 }
5693
5694 #if ENABLE_DC
5695 static BcStatus bc_program_assignStr(BcResult *r, BcVec *v,
5696                                      bool push)
5697 {
5698         BcNum n2;
5699         BcResult res;
5700
5701         memset(&n2, 0, sizeof(BcNum));
5702         n2.rdx = res.d.id.idx = r->d.id.idx;
5703         res.t = BC_RESULT_STR;
5704
5705         if (!push) {
5706                 if (!BC_PROG_STACK(&G.prog.results, 2))
5707                         return bc_error_stack_has_too_few_elements();
5708                 bc_vec_pop(v);
5709                 bc_vec_pop(&G.prog.results);
5710         }
5711
5712         bc_vec_pop(&G.prog.results);
5713
5714         bc_vec_push(&G.prog.results, &res);
5715         bc_vec_push(v, &n2);
5716
5717         return BC_STATUS_SUCCESS;
5718 }
5719 #endif // ENABLE_DC
5720
5721 static BcStatus bc_program_copyToVar(char *name, bool var)
5722 {
5723         BcStatus s;
5724         BcResult *ptr, r;
5725         BcVec *v;
5726         BcNum *n;
5727
5728         if (!BC_PROG_STACK(&G.prog.results, 1))
5729                 return bc_error_stack_has_too_few_elements();
5730
5731         ptr = bc_vec_top(&G.prog.results);
5732         if ((ptr->t == BC_RESULT_ARRAY) != !var)
5733                 return bc_error_variable_is_wrong_type();
5734         v = bc_program_search(name, var);
5735
5736 #if ENABLE_DC
5737         if (ptr->t == BC_RESULT_STR && !var)
5738                 return bc_error_variable_is_wrong_type();
5739         if (ptr->t == BC_RESULT_STR) return bc_program_assignStr(ptr, v, true);
5740 #endif
5741
5742         s = bc_program_num(ptr, &n, false);
5743         if (s) return s;
5744
5745         // Do this once more to make sure that pointers were not invalidated.
5746         v = bc_program_search(name, var);
5747
5748         if (var) {
5749                 bc_num_init(&r.d.n, BC_NUM_DEF_SIZE);
5750                 bc_num_copy(&r.d.n, n);
5751         }
5752         else {
5753                 bc_array_init(&r.d.v, true);
5754                 bc_array_copy(&r.d.v, (BcVec *) n);
5755         }
5756
5757         bc_vec_push(v, &r.d);
5758         bc_vec_pop(&G.prog.results);
5759
5760         return s;
5761 }
5762
5763 static BcStatus bc_program_assign(char inst)
5764 {
5765         BcStatus s;
5766         BcResult *left, *right, res;
5767         BcNum *l = NULL, *r = NULL;
5768         unsigned long val, max;
5769         bool assign = inst == BC_INST_ASSIGN, ib, sc;
5770
5771         s = bc_program_binOpPrep(&left, &l, &right, &r, assign);
5772         if (s) return s;
5773
5774         ib = left->t == BC_RESULT_IBASE;
5775         sc = left->t == BC_RESULT_SCALE;
5776
5777 #if ENABLE_DC
5778
5779         if (right->t == BC_RESULT_STR) {
5780
5781                 BcVec *v;
5782
5783                 if (left->t != BC_RESULT_VAR)
5784                         return bc_error_variable_is_wrong_type();
5785                 v = bc_program_search(left->d.id.name, true);
5786
5787                 return bc_program_assignStr(right, v, false);
5788         }
5789 #endif
5790
5791         if (left->t == BC_RESULT_CONSTANT || left->t == BC_RESULT_TEMP)
5792                 return bc_error("bad assignment:"
5793                                 " left side must be scale,"
5794                                 " ibase, obase, last, var,"
5795                                 " or array element"
5796                 );
5797
5798 #if ENABLE_BC
5799         if (inst == BC_INST_ASSIGN_DIVIDE && !bc_num_cmp(r, &G.prog.zero))
5800                 return bc_error("divide by zero");
5801
5802         if (assign)
5803                 bc_num_copy(l, r);
5804         else
5805                 s = bc_program_ops[inst - BC_INST_ASSIGN_POWER](l, r, l, G.prog.scale);
5806
5807         if (s) return s;
5808 #else
5809         bc_num_copy(l, r);
5810 #endif
5811
5812         if (ib || sc || left->t == BC_RESULT_OBASE) {
5813                 static const char *const msg[] = {
5814                         "bad ibase; must be [2, 16]",           //BC_RESULT_IBASE
5815                         "bad scale; must be [0, BC_SCALE_MAX]", //BC_RESULT_SCALE
5816                         "?1",                                   //BC_RESULT_LAST
5817                         "?2",                                   //BC_RESULT_CONSTANT
5818                         "?3",                                   //BC_RESULT_ONE
5819                         "bad obase; must be [2, BC_BASE_MAX]",  //BC_RESULT_OBASE
5820                 };
5821                 size_t *ptr;
5822
5823                 s = bc_num_ulong(l, &val);
5824                 if (s)
5825                         return s;
5826                 s = left->t - BC_RESULT_IBASE;
5827                 if (sc) {
5828                         max = BC_MAX_SCALE;
5829                         ptr = &G.prog.scale;
5830                 }
5831                 else {
5832                         if (val < BC_NUM_MIN_BASE)
5833                                 return bc_error(msg[s]);
5834                         max = ib ? BC_NUM_MAX_IBASE : BC_MAX_OBASE;
5835                         ptr = ib ? &G.prog.ib_t : &G.prog.ob_t;
5836                 }
5837
5838                 if (val > max)
5839                         return bc_error(msg[s]);
5840                 if (!sc)
5841                         bc_num_copy(ib ? &G.prog.ib : &G.prog.ob, l);
5842
5843                 *ptr = (size_t) val;
5844                 s = BC_STATUS_SUCCESS;
5845         }
5846
5847         bc_num_init(&res.d.n, l->len);
5848         bc_num_copy(&res.d.n, l);
5849         bc_program_binOpRetire(&res);
5850
5851         return s;
5852 }
5853
5854 #if !ENABLE_DC
5855 #define bc_program_pushVar(code, bgn, pop, copy) \
5856         bc_program_pushVar(code, bgn)
5857 // for bc, 'pop' and 'copy' are always false
5858 #endif
5859 static BcStatus bc_program_pushVar(char *code, size_t *bgn,
5860                                    bool pop, bool copy)
5861 {
5862         BcStatus s = BC_STATUS_SUCCESS;
5863         BcResult r;
5864         char *name = bc_program_name(code, bgn);
5865
5866         r.t = BC_RESULT_VAR;
5867         r.d.id.name = name;
5868
5869 #if ENABLE_DC
5870         {
5871                 BcVec *v = bc_program_search(name, true);
5872                 BcNum *num = bc_vec_top(v);
5873
5874                 if (pop || copy) {
5875
5876                         if (!BC_PROG_STACK(v, 2 - copy)) {
5877                                 free(name);
5878                                 return bc_error_stack_has_too_few_elements();
5879                         }
5880
5881                         free(name);
5882                         name = NULL;
5883
5884                         if (!BC_PROG_STR(num)) {
5885
5886                                 r.t = BC_RESULT_TEMP;
5887
5888                                 bc_num_init(&r.d.n, BC_NUM_DEF_SIZE);
5889                                 bc_num_copy(&r.d.n, num);
5890                         }
5891                         else {
5892                                 r.t = BC_RESULT_STR;
5893                                 r.d.id.idx = num->rdx;
5894                         }
5895
5896                         if (!copy) bc_vec_pop(v);
5897                 }
5898         }
5899 #endif // ENABLE_DC
5900
5901         bc_vec_push(&G.prog.results, &r);
5902
5903         return s;
5904 }
5905
5906 static BcStatus bc_program_pushArray(char *code, size_t *bgn,
5907                                      char inst)
5908 {
5909         BcStatus s = BC_STATUS_SUCCESS;
5910         BcResult r;
5911         BcNum *num;
5912
5913         r.d.id.name = bc_program_name(code, bgn);
5914
5915         if (inst == BC_INST_ARRAY) {
5916                 r.t = BC_RESULT_ARRAY;
5917                 bc_vec_push(&G.prog.results, &r);
5918         }
5919         else {
5920
5921                 BcResult *operand;
5922                 unsigned long temp;
5923
5924                 s = bc_program_prep(&operand, &num);
5925                 if (s) goto err;
5926                 s = bc_num_ulong(num, &temp);
5927                 if (s) goto err;
5928
5929                 if (temp > BC_MAX_DIM) {
5930                         s = bc_error("array too long; must be [1, BC_DIM_MAX]");
5931                         goto err;
5932                 }
5933
5934                 r.d.id.idx = (size_t) temp;
5935                 bc_program_retire(&r, BC_RESULT_ARRAY_ELEM);
5936         }
5937
5938 err:
5939         if (s) free(r.d.id.name);
5940         return s;
5941 }
5942
5943 #if ENABLE_BC
5944 static BcStatus bc_program_incdec(char inst)
5945 {
5946         BcStatus s;
5947         BcResult *ptr, res, copy;
5948         BcNum *num = NULL;
5949         char inst2 = inst;
5950
5951         s = bc_program_prep(&ptr, &num);
5952         if (s) return s;
5953
5954         if (inst == BC_INST_INC_POST || inst == BC_INST_DEC_POST) {
5955                 copy.t = BC_RESULT_TEMP;
5956                 bc_num_init(&copy.d.n, num->len);
5957                 bc_num_copy(&copy.d.n, num);
5958         }
5959
5960         res.t = BC_RESULT_ONE;
5961         inst = inst == BC_INST_INC_PRE || inst == BC_INST_INC_POST ?
5962                    BC_INST_ASSIGN_PLUS :
5963                    BC_INST_ASSIGN_MINUS;
5964
5965         bc_vec_push(&G.prog.results, &res);
5966         bc_program_assign(inst);
5967
5968         if (inst2 == BC_INST_INC_POST || inst2 == BC_INST_DEC_POST) {
5969                 bc_vec_pop(&G.prog.results);
5970                 bc_vec_push(&G.prog.results, &copy);
5971         }
5972
5973         return s;
5974 }
5975
5976 static BcStatus bc_program_call(char *code, size_t *idx)
5977 {
5978         BcStatus s = BC_STATUS_SUCCESS;
5979         BcInstPtr ip;
5980         size_t i, nparams = bc_program_index(code, idx);
5981         BcFunc *func;
5982         BcId *a;
5983         BcResultData param;
5984         BcResult *arg;
5985
5986         ip.idx = 0;
5987         ip.func = bc_program_index(code, idx);
5988         func = bc_vec_item(&G.prog.fns, ip.func);
5989
5990         if (func->code.len == 0) {
5991                 return bc_error("undefined function");
5992         }
5993         if (nparams != func->nparams) {
5994                 return bc_error_fmt("function has %u parameters, but called with %u", func->nparams, nparams);
5995         }
5996         ip.len = G.prog.results.len - nparams;
5997
5998         for (i = 0; i < nparams; ++i) {
5999
6000                 a = bc_vec_item(&func->autos, nparams - 1 - i);
6001                 arg = bc_vec_top(&G.prog.results);
6002
6003                 if ((!a->idx) != (arg->t == BC_RESULT_ARRAY) || arg->t == BC_RESULT_STR)
6004                         return bc_error_variable_is_wrong_type();
6005
6006                 s = bc_program_copyToVar(a->name, a->idx);
6007                 if (s) return s;
6008         }
6009
6010         for (; i < func->autos.len; ++i) {
6011                 BcVec *v;
6012
6013                 a = bc_vec_item(&func->autos, i);
6014                 v = bc_program_search(a->name, a->idx);
6015
6016                 if (a->idx) {
6017                         bc_num_init(&param.n, BC_NUM_DEF_SIZE);
6018                         bc_vec_push(v, &param.n);
6019                 }
6020                 else {
6021                         bc_array_init(&param.v, true);
6022                         bc_vec_push(v, &param.v);
6023                 }
6024         }
6025
6026         bc_vec_push(&G.prog.stack, &ip);
6027
6028         return BC_STATUS_SUCCESS;
6029 }
6030
6031 static BcStatus bc_program_return(char inst)
6032 {
6033         BcStatus s;
6034         BcResult res;
6035         BcFunc *f;
6036         size_t i;
6037         BcInstPtr *ip = bc_vec_top(&G.prog.stack);
6038
6039         if (!BC_PROG_STACK(&G.prog.results, ip->len + inst == BC_INST_RET))
6040                 return bc_error_stack_has_too_few_elements();
6041
6042         f = bc_vec_item(&G.prog.fns, ip->func);
6043         res.t = BC_RESULT_TEMP;
6044
6045         if (inst == BC_INST_RET) {
6046
6047                 BcNum *num;
6048                 BcResult *operand = bc_vec_top(&G.prog.results);
6049
6050                 s = bc_program_num(operand, &num, false);
6051                 if (s) return s;
6052                 bc_num_init(&res.d.n, num->len);
6053                 bc_num_copy(&res.d.n, num);
6054         }
6055         else {
6056                 bc_num_init(&res.d.n, BC_NUM_DEF_SIZE);
6057                 bc_num_zero(&res.d.n);
6058         }
6059
6060         // We need to pop arguments as well, so this takes that into account.
6061         for (i = 0; i < f->autos.len; ++i) {
6062
6063                 BcVec *v;
6064                 BcId *a = bc_vec_item(&f->autos, i);
6065
6066                 v = bc_program_search(a->name, a->idx);
6067                 bc_vec_pop(v);
6068         }
6069
6070         bc_vec_npop(&G.prog.results, G.prog.results.len - ip->len);
6071         bc_vec_push(&G.prog.results, &res);
6072         bc_vec_pop(&G.prog.stack);
6073
6074         return BC_STATUS_SUCCESS;
6075 }
6076 #endif // ENABLE_BC
6077
6078 static unsigned long bc_program_scale(BcNum *n)
6079 {
6080         return (unsigned long) n->rdx;
6081 }
6082
6083 static unsigned long bc_program_len(BcNum *n)
6084 {
6085         unsigned long len = n->len;
6086         size_t i;
6087
6088         if (n->rdx != n->len) return len;
6089         for (i = n->len - 1; i < n->len && n->num[i] == 0; --len, --i);
6090
6091         return len;
6092 }
6093
6094 static BcStatus bc_program_builtin(char inst)
6095 {
6096         BcStatus s;
6097         BcResult *opnd;
6098         BcNum *num = NULL;
6099         BcResult res;
6100         bool len = inst == BC_INST_LENGTH;
6101
6102         if (!BC_PROG_STACK(&G.prog.results, 1))
6103                 return bc_error_stack_has_too_few_elements();
6104         opnd = bc_vec_top(&G.prog.results);
6105
6106         s = bc_program_num(opnd, &num, false);
6107         if (s) return s;
6108
6109 #if ENABLE_DC
6110         if (!BC_PROG_NUM(opnd, num) && !len)
6111                 return bc_error_variable_is_wrong_type();
6112 #endif
6113
6114         bc_num_init(&res.d.n, BC_NUM_DEF_SIZE);
6115
6116         if (inst == BC_INST_SQRT) s = bc_num_sqrt(num, &res.d.n, G.prog.scale);
6117 #if ENABLE_BC
6118         else if (len != 0 && opnd->t == BC_RESULT_ARRAY) {
6119                 bc_num_ulong2num(&res.d.n, (unsigned long) ((BcVec *) num)->len);
6120         }
6121 #endif
6122 #if ENABLE_DC
6123         else if (len != 0 && !BC_PROG_NUM(opnd, num)) {
6124
6125                 char **str;
6126                 size_t idx = opnd->t == BC_RESULT_STR ? opnd->d.id.idx : num->rdx;
6127
6128                 str = bc_vec_item(&G.prog.strs, idx);
6129                 bc_num_ulong2num(&res.d.n, strlen(*str));
6130         }
6131 #endif
6132         else {
6133                 BcProgramBuiltIn f = len ? bc_program_len : bc_program_scale;
6134                 bc_num_ulong2num(&res.d.n, f(num));
6135         }
6136
6137         bc_program_retire(&res, BC_RESULT_TEMP);
6138
6139         return s;
6140 }
6141
6142 #if ENABLE_DC
6143 static BcStatus bc_program_divmod(void)
6144 {
6145         BcStatus s;
6146         BcResult *opd1, *opd2, res, res2;
6147         BcNum *n1, *n2 = NULL;
6148
6149         s = bc_program_binOpPrep(&opd1, &n1, &opd2, &n2, false);
6150         if (s) return s;
6151
6152         bc_num_init(&res.d.n, BC_NUM_DEF_SIZE);
6153         bc_num_init(&res2.d.n, n2->len);
6154
6155         s = bc_num_divmod(n1, n2, &res2.d.n, &res.d.n, G.prog.scale);
6156         if (s) goto err;
6157
6158         bc_program_binOpRetire(&res2);
6159         res.t = BC_RESULT_TEMP;
6160         bc_vec_push(&G.prog.results, &res);
6161
6162         return s;
6163
6164 err:
6165         bc_num_free(&res2.d.n);
6166         bc_num_free(&res.d.n);
6167         return s;
6168 }
6169
6170 static BcStatus bc_program_modexp(void)
6171 {
6172         BcStatus s;
6173         BcResult *r1, *r2, *r3, res;
6174         BcNum *n1, *n2, *n3;
6175
6176         if (!BC_PROG_STACK(&G.prog.results, 3))
6177                 return bc_error_stack_has_too_few_elements();
6178         s = bc_program_binOpPrep(&r2, &n2, &r3, &n3, false);
6179         if (s) return s;
6180
6181         r1 = bc_vec_item_rev(&G.prog.results, 2);
6182         s = bc_program_num(r1, &n1, false);
6183         if (s) return s;
6184         if (!BC_PROG_NUM(r1, n1))
6185                 return bc_error_variable_is_wrong_type();
6186
6187         // Make sure that the values have their pointers updated, if necessary.
6188         if (r1->t == BC_RESULT_VAR || r1->t == BC_RESULT_ARRAY_ELEM) {
6189
6190                 if (r1->t == r2->t) {
6191                         s = bc_program_num(r2, &n2, false);
6192                         if (s) return s;
6193                 }
6194
6195                 if (r1->t == r3->t) {
6196                         s = bc_program_num(r3, &n3, false);
6197                         if (s) return s;
6198                 }
6199         }
6200
6201         bc_num_init(&res.d.n, n3->len);
6202         s = bc_num_modexp(n1, n2, n3, &res.d.n);
6203         if (s) goto err;
6204
6205         bc_vec_pop(&G.prog.results);
6206         bc_program_binOpRetire(&res);
6207
6208         return s;
6209
6210 err:
6211         bc_num_free(&res.d.n);
6212         return s;
6213 }
6214
6215 static void bc_program_stackLen(void)
6216 {
6217         BcResult res;
6218         size_t len = G.prog.results.len;
6219
6220         res.t = BC_RESULT_TEMP;
6221
6222         bc_num_init(&res.d.n, BC_NUM_DEF_SIZE);
6223         bc_num_ulong2num(&res.d.n, len);
6224         bc_vec_push(&G.prog.results, &res);
6225 }
6226
6227 static BcStatus bc_program_asciify(void)
6228 {
6229         BcStatus s;
6230         BcResult *r, res;
6231         BcNum *num = NULL, n;
6232         char *str, *str2, c;
6233         size_t len = G.prog.strs.len, idx;
6234         unsigned long val;
6235
6236         if (!BC_PROG_STACK(&G.prog.results, 1))
6237                 return bc_error_stack_has_too_few_elements();
6238         r = bc_vec_top(&G.prog.results);
6239
6240         s = bc_program_num(r, &num, false);
6241         if (s) return s;
6242
6243         if (BC_PROG_NUM(r, num)) {
6244
6245                 bc_num_init(&n, BC_NUM_DEF_SIZE);
6246                 bc_num_copy(&n, num);
6247                 bc_num_truncate(&n, n.rdx);
6248
6249                 s = bc_num_mod(&n, &G.prog.strmb, &n, 0);
6250                 if (s) goto num_err;
6251                 s = bc_num_ulong(&n, &val);
6252                 if (s) goto num_err;
6253
6254                 c = (char) val;
6255
6256                 bc_num_free(&n);
6257         }
6258         else {
6259                 idx = (r->t == BC_RESULT_STR) ? r->d.id.idx : num->rdx;
6260                 str2 = *((char **) bc_vec_item(&G.prog.strs, idx));
6261                 c = str2[0];
6262         }
6263
6264         str = xmalloc(2);
6265         str[0] = c;
6266         str[1] = '\0';
6267
6268         str2 = xstrdup(str);
6269         bc_program_addFunc(str2, &idx);
6270
6271         if (idx != len + BC_PROG_REQ_FUNCS) {
6272
6273                 for (idx = 0; idx < G.prog.strs.len; ++idx) {
6274                         if (!strcmp(*((char **) bc_vec_item(&G.prog.strs, idx)), str)) {
6275                                 len = idx;
6276                                 break;
6277                         }
6278                 }
6279
6280                 free(str);
6281         }
6282         else
6283                 bc_vec_push(&G.prog.strs, &str);
6284
6285         res.t = BC_RESULT_STR;
6286         res.d.id.idx = len;
6287         bc_vec_pop(&G.prog.results);
6288         bc_vec_push(&G.prog.results, &res);
6289
6290         return BC_STATUS_SUCCESS;
6291
6292 num_err:
6293         bc_num_free(&n);
6294         return s;
6295 }
6296
6297 static BcStatus bc_program_printStream(void)
6298 {
6299         BcStatus s;
6300         BcResult *r;
6301         BcNum *n = NULL;
6302         size_t idx;
6303         char *str;
6304
6305         if (!BC_PROG_STACK(&G.prog.results, 1))
6306                 return bc_error_stack_has_too_few_elements();
6307         r = bc_vec_top(&G.prog.results);
6308
6309         s = bc_program_num(r, &n, false);
6310         if (s) return s;
6311
6312         if (BC_PROG_NUM(r, n))
6313                 s = bc_num_stream(n, &G.prog.strmb, &G.prog.nchars, G.prog.len);
6314         else {
6315                 idx = (r->t == BC_RESULT_STR) ? r->d.id.idx : n->rdx;
6316                 str = *((char **) bc_vec_item(&G.prog.strs, idx));
6317                 printf("%s", str);
6318         }
6319
6320         return s;
6321 }
6322
6323 static BcStatus bc_program_nquit(void)
6324 {
6325         BcStatus s;
6326         BcResult *opnd;
6327         BcNum *num = NULL;
6328         unsigned long val;
6329
6330         s = bc_program_prep(&opnd, &num);
6331         if (s) return s;
6332         s = bc_num_ulong(num, &val);
6333         if (s) return s;
6334
6335         bc_vec_pop(&G.prog.results);
6336
6337         if (G.prog.stack.len < val)
6338                 return bc_error_stack_has_too_few_elements();
6339         if (G.prog.stack.len == val)
6340                 quit();
6341
6342         bc_vec_npop(&G.prog.stack, val);
6343
6344         return s;
6345 }
6346
6347 static BcStatus bc_program_execStr(char *code, size_t *bgn,
6348                                    bool cond)
6349 {
6350         BcStatus s = BC_STATUS_SUCCESS;
6351         BcResult *r;
6352         char **str;
6353         BcFunc *f;
6354         BcParse prs;
6355         BcInstPtr ip;
6356         size_t fidx, sidx;
6357         BcNum *n;
6358         bool exec;
6359
6360         if (!BC_PROG_STACK(&G.prog.results, 1))
6361                 return bc_error_stack_has_too_few_elements();
6362
6363         r = bc_vec_top(&G.prog.results);
6364
6365         if (cond) {
6366
6367                 char *name, *then_name = bc_program_name(code, bgn), *else_name = NULL;
6368
6369                 if (code[*bgn] == BC_PARSE_STREND)
6370                         (*bgn) += 1;
6371                 else
6372                         else_name = bc_program_name(code, bgn);
6373
6374                 exec = r->d.n.len != 0;
6375
6376                 if (exec)
6377                         name = then_name;
6378                 else if (else_name != NULL) {
6379                         exec = true;
6380                         name = else_name;
6381                 }
6382
6383                 if (exec) {
6384                         BcVec *v;
6385                         v = bc_program_search(name, true);
6386                         n = bc_vec_top(v);
6387                 }
6388
6389                 free(then_name);
6390                 free(else_name);
6391
6392                 if (!exec) goto exit;
6393                 if (!BC_PROG_STR(n)) {
6394                         s = bc_error_variable_is_wrong_type();
6395                         goto exit;
6396                 }
6397
6398                 sidx = n->rdx;
6399         }
6400         else {
6401
6402                 if (r->t == BC_RESULT_STR)
6403                         sidx = r->d.id.idx;
6404                 else if (r->t == BC_RESULT_VAR) {
6405                         s = bc_program_num(r, &n, false);
6406                         if (s || !BC_PROG_STR(n)) goto exit;
6407                         sidx = n->rdx;
6408                 }
6409                 else
6410                         goto exit;
6411         }
6412
6413         fidx = sidx + BC_PROG_REQ_FUNCS;
6414
6415         str = bc_vec_item(&G.prog.strs, sidx);
6416         f = bc_vec_item(&G.prog.fns, fidx);
6417
6418         if (f->code.len == 0) {
6419                 common_parse_init(&prs, fidx);
6420                 s = bc_parse_text(&prs, *str);
6421                 if (s) goto err;
6422                 s = common_parse_expr(&prs, BC_PARSE_NOCALL);
6423                 if (s) goto err;
6424
6425                 if (prs.l.t.t != BC_LEX_EOF) {
6426                         s = bc_error_bad_expression();
6427                         goto err;
6428                 }
6429
6430                 bc_parse_free(&prs);
6431         }
6432
6433         ip.idx = 0;
6434         ip.len = G.prog.results.len;
6435         ip.func = fidx;
6436
6437         bc_vec_pop(&G.prog.results);
6438         bc_vec_push(&G.prog.stack, &ip);
6439
6440         return BC_STATUS_SUCCESS;
6441
6442 err:
6443         bc_parse_free(&prs);
6444         f = bc_vec_item(&G.prog.fns, fidx);
6445         bc_vec_pop_all(&f->code);
6446 exit:
6447         bc_vec_pop(&G.prog.results);
6448         return s;
6449 }
6450 #endif // ENABLE_DC
6451
6452 static void bc_program_pushGlobal(char inst)
6453 {
6454         BcResult res;
6455         unsigned long val;
6456
6457         res.t = inst - BC_INST_IBASE + BC_RESULT_IBASE;
6458         if (inst == BC_INST_IBASE)
6459                 val = (unsigned long) G.prog.ib_t;
6460         else if (inst == BC_INST_SCALE)
6461                 val = (unsigned long) G.prog.scale;
6462         else
6463                 val = (unsigned long) G.prog.ob_t;
6464
6465         bc_num_init(&res.d.n, BC_NUM_DEF_SIZE);
6466         bc_num_ulong2num(&res.d.n, val);
6467         bc_vec_push(&G.prog.results, &res);
6468 }
6469
6470 static void bc_program_addFunc(char *name, size_t *idx)
6471 {
6472         BcId entry, *entry_ptr;
6473         BcFunc f;
6474         int inserted;
6475
6476         entry.name = name;
6477         entry.idx = G.prog.fns.len;
6478
6479         inserted = bc_map_insert(&G.prog.fn_map, &entry, idx);
6480         if (!inserted) free(name);
6481
6482         entry_ptr = bc_vec_item(&G.prog.fn_map, *idx);
6483         *idx = entry_ptr->idx;
6484
6485         if (!inserted) {
6486
6487                 BcFunc *func = bc_vec_item(&G.prog.fns, entry_ptr->idx);
6488
6489                 // We need to reset these, so the function can be repopulated.
6490                 func->nparams = 0;
6491                 bc_vec_pop_all(&func->autos);
6492                 bc_vec_pop_all(&func->code);
6493                 bc_vec_pop_all(&func->labels);
6494         }
6495         else {
6496                 bc_func_init(&f);
6497                 bc_vec_push(&G.prog.fns, &f);
6498         }
6499 }
6500
6501 // Called when parsing or execution detects a failure,
6502 // resets execution structures.
6503 static void bc_program_reset(void)
6504 {
6505         BcFunc *f;
6506         BcInstPtr *ip;
6507
6508         bc_vec_npop(&G.prog.stack, G.prog.stack.len - 1);
6509         bc_vec_pop_all(&G.prog.results);
6510
6511         f = bc_vec_item(&G.prog.fns, 0);
6512         ip = bc_vec_top(&G.prog.stack);
6513         ip->idx = f->code.len;
6514
6515         // If !tty, no need to check for ^C: we don't have ^C handler,
6516         // we would be killed by a signal and won't reach this place
6517 }
6518
6519 static BcStatus bc_program_exec(void)
6520 {
6521         BcStatus s = BC_STATUS_SUCCESS;
6522         size_t idx;
6523         BcResult r, *ptr;
6524         BcNum *num;
6525         BcInstPtr *ip = bc_vec_top(&G.prog.stack);
6526         BcFunc *func = bc_vec_item(&G.prog.fns, ip->func);
6527         char *code = func->code.v;
6528         bool cond = false;
6529
6530         while (!s && ip->idx < func->code.len) {
6531
6532                 char inst = code[(ip->idx)++];
6533
6534                 switch (inst) {
6535
6536 #if ENABLE_BC
6537                         case BC_INST_JUMP_ZERO:
6538                         {
6539                                 s = bc_program_prep(&ptr, &num);
6540                                 if (s) return s;
6541                                 cond = !bc_num_cmp(num, &G.prog.zero);
6542                                 bc_vec_pop(&G.prog.results);
6543                         }
6544                         // Fallthrough.
6545                         case BC_INST_JUMP:
6546                         {
6547                                 size_t *addr;
6548                                 idx = bc_program_index(code, &ip->idx);
6549                                 addr = bc_vec_item(&func->labels, idx);
6550                                 if (inst == BC_INST_JUMP || cond) ip->idx = *addr;
6551                                 break;
6552                         }
6553
6554                         case BC_INST_CALL:
6555                         {
6556                                 s = bc_program_call(code, &ip->idx);
6557                                 break;
6558                         }
6559
6560                         case BC_INST_INC_PRE:
6561                         case BC_INST_DEC_PRE:
6562                         case BC_INST_INC_POST:
6563                         case BC_INST_DEC_POST:
6564                         {
6565                                 s = bc_program_incdec(inst);
6566                                 break;
6567                         }
6568
6569                         case BC_INST_HALT:
6570                         {
6571                                 quit();
6572                                 break;
6573                         }
6574
6575                         case BC_INST_RET:
6576                         case BC_INST_RET0:
6577                         {
6578                                 s = bc_program_return(inst);
6579                                 break;
6580                         }
6581
6582                         case BC_INST_BOOL_OR:
6583                         case BC_INST_BOOL_AND:
6584 #endif // ENABLE_BC
6585                         case BC_INST_REL_EQ:
6586                         case BC_INST_REL_LE:
6587                         case BC_INST_REL_GE:
6588                         case BC_INST_REL_NE:
6589                         case BC_INST_REL_LT:
6590                         case BC_INST_REL_GT:
6591                         {
6592                                 s = bc_program_logical(inst);
6593                                 break;
6594                         }
6595
6596                         case BC_INST_READ:
6597                         {
6598                                 s = bc_program_read();
6599                                 break;
6600                         }
6601
6602                         case BC_INST_VAR:
6603                         {
6604                                 s = bc_program_pushVar(code, &ip->idx, false, false);
6605                                 break;
6606                         }
6607
6608                         case BC_INST_ARRAY_ELEM:
6609                         case BC_INST_ARRAY:
6610                         {
6611                                 s = bc_program_pushArray(code, &ip->idx, inst);
6612                                 break;
6613                         }
6614
6615                         case BC_INST_LAST:
6616                         {
6617                                 r.t = BC_RESULT_LAST;
6618                                 bc_vec_push(&G.prog.results, &r);
6619                                 break;
6620                         }
6621
6622                         case BC_INST_IBASE:
6623                         case BC_INST_SCALE:
6624                         case BC_INST_OBASE:
6625                         {
6626                                 bc_program_pushGlobal(inst);
6627                                 break;
6628                         }
6629
6630                         case BC_INST_SCALE_FUNC:
6631                         case BC_INST_LENGTH:
6632                         case BC_INST_SQRT:
6633                         {
6634                                 s = bc_program_builtin(inst);
6635                                 break;
6636                         }
6637
6638                         case BC_INST_NUM:
6639                         {
6640                                 r.t = BC_RESULT_CONSTANT;
6641                                 r.d.id.idx = bc_program_index(code, &ip->idx);
6642                                 bc_vec_push(&G.prog.results, &r);
6643                                 break;
6644                         }
6645
6646                         case BC_INST_POP:
6647                         {
6648                                 if (!BC_PROG_STACK(&G.prog.results, 1))
6649                                         s = bc_error_stack_has_too_few_elements();
6650                                 else
6651                                         bc_vec_pop(&G.prog.results);
6652                                 break;
6653                         }
6654
6655                         case BC_INST_POP_EXEC:
6656                         {
6657                                 bc_vec_pop(&G.prog.stack);
6658                                 break;
6659                         }
6660
6661                         case BC_INST_PRINT:
6662                         case BC_INST_PRINT_POP:
6663                         case BC_INST_PRINT_STR:
6664                         {
6665                                 s = bc_program_print(inst, 0);
6666                                 break;
6667                         }
6668
6669                         case BC_INST_STR:
6670                         {
6671                                 r.t = BC_RESULT_STR;
6672                                 r.d.id.idx = bc_program_index(code, &ip->idx);
6673                                 bc_vec_push(&G.prog.results, &r);
6674                                 break;
6675                         }
6676
6677                         case BC_INST_POWER:
6678                         case BC_INST_MULTIPLY:
6679                         case BC_INST_DIVIDE:
6680                         case BC_INST_MODULUS:
6681                         case BC_INST_PLUS:
6682                         case BC_INST_MINUS:
6683                         {
6684                                 s = bc_program_op(inst);
6685                                 break;
6686                         }
6687
6688                         case BC_INST_BOOL_NOT:
6689                         {
6690                                 s = bc_program_prep(&ptr, &num);
6691                                 if (s) return s;
6692
6693                                 bc_num_init(&r.d.n, BC_NUM_DEF_SIZE);
6694                                 (!bc_num_cmp(num, &G.prog.zero) ? bc_num_one : bc_num_zero)(&r.d.n);
6695                                 bc_program_retire(&r, BC_RESULT_TEMP);
6696
6697                                 break;
6698                         }
6699
6700                         case BC_INST_NEG:
6701                         {
6702                                 s = bc_program_negate();
6703                                 break;
6704                         }
6705
6706 #if ENABLE_BC
6707                         case BC_INST_ASSIGN_POWER:
6708                         case BC_INST_ASSIGN_MULTIPLY:
6709                         case BC_INST_ASSIGN_DIVIDE:
6710                         case BC_INST_ASSIGN_MODULUS:
6711                         case BC_INST_ASSIGN_PLUS:
6712                         case BC_INST_ASSIGN_MINUS:
6713 #endif
6714                         case BC_INST_ASSIGN:
6715                         {
6716                                 s = bc_program_assign(inst);
6717                                 break;
6718                         }
6719 #if ENABLE_DC
6720                         case BC_INST_MODEXP:
6721                         {
6722                                 s = bc_program_modexp();
6723                                 break;
6724                         }
6725
6726                         case BC_INST_DIVMOD:
6727                         {
6728                                 s = bc_program_divmod();
6729                                 break;
6730                         }
6731
6732                         case BC_INST_EXECUTE:
6733                         case BC_INST_EXEC_COND:
6734                         {
6735                                 cond = inst == BC_INST_EXEC_COND;
6736                                 s = bc_program_execStr(code, &ip->idx, cond);
6737                                 break;
6738                         }
6739
6740                         case BC_INST_PRINT_STACK:
6741                         {
6742                                 for (idx = 0; !s && idx < G.prog.results.len; ++idx)
6743                                         s = bc_program_print(BC_INST_PRINT, idx);
6744                                 break;
6745                         }
6746
6747                         case BC_INST_CLEAR_STACK:
6748                         {
6749                                 bc_vec_pop_all(&G.prog.results);
6750                                 break;
6751                         }
6752
6753                         case BC_INST_STACK_LEN:
6754                         {
6755                                 bc_program_stackLen();
6756                                 break;
6757                         }
6758
6759                         case BC_INST_DUPLICATE:
6760                         {
6761                                 if (!BC_PROG_STACK(&G.prog.results, 1))
6762                                         return bc_error_stack_has_too_few_elements();
6763                                 ptr = bc_vec_top(&G.prog.results);
6764                                 bc_result_copy(&r, ptr);
6765                                 bc_vec_push(&G.prog.results, &r);
6766                                 break;
6767                         }
6768
6769                         case BC_INST_SWAP:
6770                         {
6771                                 BcResult *ptr2;
6772
6773                                 if (!BC_PROG_STACK(&G.prog.results, 2))
6774                                         return bc_error_stack_has_too_few_elements();
6775
6776                                 ptr = bc_vec_item_rev(&G.prog.results, 0);
6777                                 ptr2 = bc_vec_item_rev(&G.prog.results, 1);
6778                                 memcpy(&r, ptr, sizeof(BcResult));
6779                                 memcpy(ptr, ptr2, sizeof(BcResult));
6780                                 memcpy(ptr2, &r, sizeof(BcResult));
6781
6782                                 break;
6783                         }
6784
6785                         case BC_INST_ASCIIFY:
6786                         {
6787                                 s = bc_program_asciify();
6788                                 break;
6789                         }
6790
6791                         case BC_INST_PRINT_STREAM:
6792                         {
6793                                 s = bc_program_printStream();
6794                                 break;
6795                         }
6796
6797                         case BC_INST_LOAD:
6798                         case BC_INST_PUSH_VAR:
6799                         {
6800                                 bool copy = inst == BC_INST_LOAD;
6801                                 s = bc_program_pushVar(code, &ip->idx, true, copy);
6802                                 break;
6803                         }
6804
6805                         case BC_INST_PUSH_TO_VAR:
6806                         {
6807                                 char *name = bc_program_name(code, &ip->idx);
6808                                 s = bc_program_copyToVar(name, true);
6809                                 free(name);
6810                                 break;
6811                         }
6812
6813                         case BC_INST_QUIT:
6814                         {
6815                                 if (G.prog.stack.len <= 2)
6816                                         quit();
6817                                 bc_vec_npop(&G.prog.stack, 2);
6818                                 break;
6819                         }
6820
6821                         case BC_INST_NQUIT:
6822                         {
6823                                 s = bc_program_nquit();
6824                                 break;
6825                         }
6826 #endif // ENABLE_DC
6827                 }
6828
6829                 if (s || G_interrupt) {
6830                         bc_program_reset();
6831                         break;
6832                 }
6833
6834                 // If the stack has changed, pointers may be invalid.
6835                 ip = bc_vec_top(&G.prog.stack);
6836                 func = bc_vec_item(&G.prog.fns, ip->func);
6837                 code = func->code.v;
6838         }
6839
6840         return s;
6841 }
6842
6843 static void bc_vm_info(void)
6844 {
6845         printf("%s "BB_VER"\n"
6846                 "Copyright (c) 2018 Gavin D. Howard and contributors\n"
6847                 "Report bugs at: https://github.com/gavinhoward/bc\n"
6848                 "This is free software with ABSOLUTELY NO WARRANTY\n"
6849         , applet_name);
6850 }
6851
6852 #if ENABLE_BC
6853 static void bc_vm_envArgs(void)
6854 {
6855         static const char* const bc_args_env_name = "BC_ENV_ARGS";
6856
6857         BcVec v;
6858         char *env_args = getenv(bc_args_env_name), *buf;
6859
6860         if (!env_args) return;
6861
6862         G.env_args = xstrdup(env_args);
6863         buf = G.env_args;
6864
6865         bc_vec_init(&v, sizeof(char *), NULL);
6866         bc_vec_push(&v, &bc_args_env_name);
6867
6868         while (*buf != 0) {
6869                 if (!isspace(*buf)) {
6870                         bc_vec_push(&v, &buf);
6871                         while (*buf != 0 && !isspace(*buf)) ++buf;
6872                         if (*buf != 0) (*(buf++)) = '\0';
6873                 }
6874                 else
6875                         ++buf;
6876         }
6877
6878         bc_args((int) v.len, (char **) v.v);
6879
6880         bc_vec_free(&v);
6881 }
6882 #endif // ENABLE_BC
6883
6884 static size_t bc_vm_envLen(const char *var)
6885 {
6886         char *lenv = getenv(var);
6887         size_t i, len = BC_NUM_PRINT_WIDTH;
6888         int num;
6889
6890         if (!lenv) return len;
6891
6892         len = strlen(lenv);
6893
6894         for (num = 1, i = 0; num && i < len; ++i) num = isdigit(lenv[i]);
6895         if (num) {
6896                 len = (size_t) atoi(lenv) - 1;
6897                 if (len < 2 || len >= INT32_MAX) len = BC_NUM_PRINT_WIDTH;
6898         }
6899         else
6900                 len = BC_NUM_PRINT_WIDTH;
6901
6902         return len;
6903 }
6904
6905 static BcStatus bc_vm_process(const char *text)
6906 {
6907         BcStatus s = bc_parse_text(&G.prs, text);
6908
6909         if (s) return s;
6910
6911         while (G.prs.l.t.t != BC_LEX_EOF) {
6912                 s = G.prs.parse(&G.prs);
6913                 if (s) return s;
6914         }
6915
6916         if (BC_PARSE_CAN_EXEC(&G.prs)) {
6917                 s = bc_program_exec();
6918                 fflush_and_check();
6919                 if (s)
6920                         bc_program_reset();
6921         }
6922
6923         return s;
6924 }
6925
6926 static BcStatus bc_vm_file(const char *file)
6927 {
6928         const char *sv_file;
6929         char *data;
6930         BcStatus s;
6931         BcFunc *main_func;
6932         BcInstPtr *ip;
6933
6934         data = bc_read_file(file);
6935         if (!data) return bc_error_fmt("file '%s' is not text", file);
6936
6937         sv_file = G.prog.file;
6938         G.prog.file = file;
6939         bc_lex_file(&G.prs.l);
6940         s = bc_vm_process(data);
6941         if (s) goto err;
6942
6943         main_func = bc_vec_item(&G.prog.fns, BC_PROG_MAIN);
6944         ip = bc_vec_item(&G.prog.stack, 0);
6945
6946         if (main_func->code.len < ip->idx)
6947                 s = bc_error_fmt("file '%s' is not executable", file);
6948
6949 err:
6950         G.prog.file = sv_file;
6951         free(data);
6952         return s;
6953 }
6954
6955 static BcStatus bc_vm_stdin(void)
6956 {
6957         BcStatus s;
6958         BcVec buf, buffer;
6959         size_t len, i, str = 0;
6960         bool comment = false;
6961
6962         G.prog.file = NULL;
6963         bc_lex_file(&G.prs.l);
6964
6965         bc_char_vec_init(&buffer);
6966         bc_char_vec_init(&buf);
6967         bc_vec_pushZeroByte(&buffer);
6968
6969         // This loop is complex because the vm tries not to send any lines that end
6970         // with a backslash to the parser. The reason for that is because the parser
6971         // treats a backslash+newline combo as whitespace, per the bc spec. In that
6972         // case, and for strings and comments, the parser will expect more stuff.
6973         while (!G.eof && (s = bc_read_line(&buf, ">>> ")) == BC_STATUS_SUCCESS) {
6974
6975                 char *string = buf.v;
6976
6977                 len = buf.len - 1;
6978
6979                 if (len == 1) {
6980                         if (str && buf.v[0] == G.send)
6981                                 str -= 1;
6982                         else if (buf.v[0] == G.sbgn)
6983                                 str += 1;
6984                 }
6985                 else if (len > 1 || comment) {
6986
6987                         for (i = 0; i < len; ++i) {
6988
6989                                 bool notend = len > i + 1;
6990                                 char c = string[i];
6991
6992                                 if (i - 1 > len || string[i - 1] != '\\') {
6993                                         if (G.sbgn == G.send)
6994                                                 str ^= c == G.sbgn;
6995                                         else if (c == G.send)
6996                                                 str -= 1;
6997                                         else if (c == G.sbgn)
6998                                                 str += 1;
6999                                 }
7000
7001                                 if (c == '/' && notend && !comment && string[i + 1] == '*') {
7002                                         comment = true;
7003                                         break;
7004                                 }
7005                                 else if (c == '*' && notend && comment && string[i + 1] == '/')
7006                                         comment = false;
7007                         }
7008
7009                         if (str || comment || string[len - 2] == '\\') {
7010                                 bc_vec_concat(&buffer, buf.v);
7011                                 continue;
7012                         }
7013                 }
7014
7015                 bc_vec_concat(&buffer, buf.v);
7016                 s = bc_vm_process(buffer.v);
7017                 if (s) {
7018                         fflush_and_check();
7019                         fputs("ready for more input\n", stderr);
7020                 }
7021
7022                 bc_vec_pop_all(&buffer);
7023         }
7024
7025         if (str) {
7026                 s = bc_error("string end could not be found");
7027         }
7028         else if (comment) {
7029                 s = bc_error("comment end could not be found");
7030         }
7031
7032         bc_vec_free(&buf);
7033         bc_vec_free(&buffer);
7034         return s;
7035 }
7036
7037 #if ENABLE_BC
7038 static const char bc_lib[] = {
7039         "scale=20"
7040 "\n"    "define e(x){"
7041 "\n"            "auto b,s,n,r,d,i,p,f,v"
7042 "\n"            "b=ibase"
7043 "\n"            "ibase=A"
7044 "\n"            "if(x<0){"
7045 "\n"                    "n=1"
7046 "\n"                    "x=-x"
7047 "\n"            "}"
7048 "\n"            "s=scale"
7049 "\n"            "r=6+s+0.44*x"
7050 "\n"            "scale=scale(x)+1"
7051 "\n"            "while(x>1){"
7052 "\n"                    "d+=1"
7053 "\n"                    "x/=2"
7054 "\n"                    "scale+=1"
7055 "\n"            "}"
7056 "\n"            "scale=r"
7057 "\n"            "r=x+1"
7058 "\n"            "p=x"
7059 "\n"            "f=v=1"
7060 "\n"            "for(i=2;v!=0;++i){"
7061 "\n"                    "p*=x"
7062 "\n"                    "f*=i"
7063 "\n"                    "v=p/f"
7064 "\n"                    "r+=v"
7065 "\n"            "}"
7066 "\n"            "while((d--)!=0)r*=r"
7067 "\n"            "scale=s"
7068 "\n"            "ibase=b"
7069 "\n"            "if(n!=0)return(1/r)"
7070 "\n"            "return(r/1)"
7071 "\n"    "}"
7072 "\n"    "define l(x){"
7073 "\n"            "auto b,s,r,p,a,q,i,v"
7074 "\n"            "b=ibase"
7075 "\n"            "ibase=A"
7076 "\n"            "if(x<=0){"
7077 "\n"                    "r=(1-10^scale)/1"
7078 "\n"                    "ibase=b"
7079 "\n"                    "return(r)"
7080 "\n"            "}"
7081 "\n"            "s=scale"
7082 "\n"            "scale+=6"
7083 "\n"            "p=2"
7084 "\n"            "while(x>=2){"
7085 "\n"                    "p*=2"
7086 "\n"                    "x=sqrt(x)"
7087 "\n"            "}"
7088 "\n"            "while(x<=0.5){"
7089 "\n"                    "p*=2"
7090 "\n"                    "x=sqrt(x)"
7091 "\n"            "}"
7092 "\n"            "r=a=(x-1)/(x+1)"
7093 "\n"            "q=a*a"
7094 "\n"                    "v=1"
7095 "\n"            "for(i=3;v!=0;i+=2){"
7096 "\n"                    "a*=q"
7097 "\n"                    "v=a/i"
7098 "\n"                    "r+=v"
7099 "\n"            "}"
7100 "\n"            "r*=p"
7101 "\n"            "scale=s"
7102 "\n"            "ibase=b"
7103 "\n"            "return(r/1)"
7104 "\n"    "}"
7105 "\n"    "define s(x){"
7106 "\n"            "auto b,s,r,n,a,q,i"
7107 "\n"            "b=ibase"
7108 "\n"            "ibase=A"
7109 "\n"            "s=scale"
7110 "\n"            "scale=1.1*s+2"
7111 "\n"            "a=a(1)"
7112 "\n"            "if(x<0){"
7113 "\n"                    "n=1"
7114 "\n"                    "x=-x"
7115 "\n"            "}"
7116 "\n"            "scale=0"
7117 "\n"            "q=(x/a+2)/4"
7118 "\n"            "x=x-4*q*a"
7119 "\n"            "if(q%2!=0)x=-x"
7120 "\n"            "scale=s+2"
7121 "\n"            "r=a=x"
7122 "\n"            "q=-x*x"
7123 "\n"            "for(i=3;a!=0;i+=2){"
7124 "\n"                    "a*=q/(i*(i-1))"
7125 "\n"                    "r+=a"
7126 "\n"            "}"
7127 "\n"            "scale=s"
7128 "\n"            "ibase=b"
7129 "\n"            "if(n!=0)return(-r/1)"
7130 "\n"            "return(r/1)"
7131 "\n"    "}"
7132 "\n"    "define c(x){"
7133 "\n"            "auto b,s"
7134 "\n"            "b=ibase"
7135 "\n"            "ibase=A"
7136 "\n"            "s=scale"
7137 "\n"            "scale*=1.2"
7138 "\n"            "x=s(2*a(1)+x)"
7139 "\n"            "scale=s"
7140 "\n"            "ibase=b"
7141 "\n"            "return(x/1)"
7142 "\n"    "}"
7143 "\n"    "define a(x){"
7144 "\n"            "auto b,s,r,n,a,m,t,f,i,u"
7145 "\n"            "b=ibase"
7146 "\n"            "ibase=A"
7147 "\n"            "n=1"
7148 "\n"            "if(x<0){"
7149 "\n"                    "n=-1"
7150 "\n"                    "x=-x"
7151 "\n"            "}"
7152 "\n"            "if(x==1){"
7153 "\n"                    "if(scale<65){"
7154 "\n"                            "return(.7853981633974483096156608458198757210492923498437764552437361480/n)"
7155 "\n"                    "}"
7156 "\n"            "}"
7157 "\n"            "if(x==.2){"
7158 "\n"                    "if(scale<65){"
7159 "\n"                            "return(.1973955598498807583700497651947902934475851037878521015176889402/n)"
7160 "\n"                    "}"
7161 "\n"            "}"
7162 "\n"            "s=scale"
7163 "\n"            "if(x>.2){"
7164 "\n"                    "scale+=5"
7165 "\n"                    "a=a(.2)"
7166 "\n"            "}"
7167 "\n"            "scale=s+3"
7168 "\n"            "while(x>.2){"
7169 "\n"                    "m+=1"
7170 "\n"                    "x=(x-.2)/(1+.2*x)"
7171 "\n"            "}"
7172 "\n"            "r=u=x"
7173 "\n"            "f=-x*x"
7174 "\n"            "t=1"
7175 "\n"            "for(i=3;t!=0;i+=2){"
7176 "\n"                    "u*=f"
7177 "\n"                    "t=u/i"
7178 "\n"                    "r+=t"
7179 "\n"            "}"
7180 "\n"            "scale=s"
7181 "\n"            "ibase=b"
7182 "\n"            "return((m*a+r)/n)"
7183 "\n"    "}"
7184 "\n"    "define j(n,x){"
7185 "\n"            "auto b,s,o,a,i,v,f"
7186 "\n"            "b=ibase"
7187 "\n"            "ibase=A"
7188 "\n"            "s=scale"
7189 "\n"            "scale=0"
7190 "\n"            "n/=1"
7191 "\n"            "if(n<0){"
7192 "\n"                    "n=-n"
7193 "\n"                    "if(n%2==1)o=1"
7194 "\n"            "}"
7195 "\n"            "a=1"
7196 "\n"            "for(i=2;i<=n;++i)a*=i"
7197 "\n"            "scale=1.5*s"
7198 "\n"            "a=(x^n)/2^n/a"
7199 "\n"            "r=v=1"
7200 "\n"            "f=-x*x/4"
7201 "\n"            "scale=scale+length(a)-scale(a)"
7202 "\n"            "for(i=1;v!=0;++i){"
7203 "\n"                    "v=v*f/i/(n+i)"
7204 "\n"                    "r+=v"
7205 "\n"            "}"
7206 "\n"            "scale=s"
7207 "\n"            "ibase=b"
7208 "\n"            "if(o!=0)a=-a"
7209 "\n"            "return(a*r/1)"
7210 "\n"    "}"
7211 };
7212 #endif // ENABLE_BC
7213
7214 static BcStatus bc_vm_exec(void)
7215 {
7216         BcStatus s = BC_STATUS_SUCCESS;
7217         size_t i;
7218
7219 #if ENABLE_BC
7220         if (option_mask32 & BC_FLAG_L) {
7221
7222                 // We know that internal library is not buggy,
7223                 // thus error checking is normally disabled.
7224 # define DEBUG_LIB 0
7225                 bc_lex_file(&G.prs.l);
7226                 s = bc_parse_text(&G.prs, bc_lib);
7227                 if (DEBUG_LIB && s) return s;
7228
7229                 while (G.prs.l.t.t != BC_LEX_EOF) {
7230                         s = G.prs.parse(&G.prs);
7231                         if (DEBUG_LIB && s) return s;
7232                 }
7233                 s = bc_program_exec();
7234                 if (DEBUG_LIB && s) return s;
7235         }
7236 #endif
7237
7238         for (i = 0; !s && i < G.files.len; ++i)
7239                 s = bc_vm_file(*((char **) bc_vec_item(&G.files, i)));
7240         if (s) {
7241                 fflush_and_check();
7242                 fputs("ready for more input\n", stderr);
7243         }
7244
7245         if (IS_BC || !G.files.len)
7246                 s = bc_vm_stdin();
7247         if (!s && !BC_PARSE_CAN_EXEC(&G.prs))
7248                 s = bc_vm_process("");
7249
7250         return s;
7251 }
7252
7253 #if ENABLE_FEATURE_CLEAN_UP
7254 static void bc_program_free()
7255 {
7256         bc_num_free(&G.prog.ib);
7257         bc_num_free(&G.prog.ob);
7258         bc_num_free(&G.prog.hexb);
7259 # if ENABLE_DC
7260         bc_num_free(&G.prog.strmb);
7261 # endif
7262         bc_vec_free(&G.prog.fns);
7263         bc_vec_free(&G.prog.fn_map);
7264         bc_vec_free(&G.prog.vars);
7265         bc_vec_free(&G.prog.var_map);
7266         bc_vec_free(&G.prog.arrs);
7267         bc_vec_free(&G.prog.arr_map);
7268         bc_vec_free(&G.prog.strs);
7269         bc_vec_free(&G.prog.consts);
7270         bc_vec_free(&G.prog.results);
7271         bc_vec_free(&G.prog.stack);
7272         bc_num_free(&G.prog.last);
7273         bc_num_free(&G.prog.zero);
7274         bc_num_free(&G.prog.one);
7275 }
7276
7277 static void bc_vm_free(void)
7278 {
7279         bc_vec_free(&G.files);
7280         bc_program_free();
7281         bc_parse_free(&G.prs);
7282         free(G.env_args);
7283 }
7284 #endif
7285
7286 static void bc_program_init(size_t line_len)
7287 {
7288         size_t idx;
7289         BcInstPtr ip;
7290
7291         /* memset(&G.prog, 0, sizeof(G.prog)); - already is */
7292         memset(&ip, 0, sizeof(BcInstPtr));
7293
7294         /* G.prog.nchars = G.prog.scale = 0; - already is */
7295         G.prog.len = line_len;
7296
7297         bc_num_init(&G.prog.ib, BC_NUM_DEF_SIZE);
7298         bc_num_ten(&G.prog.ib);
7299         G.prog.ib_t = 10;
7300
7301         bc_num_init(&G.prog.ob, BC_NUM_DEF_SIZE);
7302         bc_num_ten(&G.prog.ob);
7303         G.prog.ob_t = 10;
7304
7305         bc_num_init(&G.prog.hexb, BC_NUM_DEF_SIZE);
7306         bc_num_ten(&G.prog.hexb);
7307         G.prog.hexb.num[0] = 6;
7308
7309 #if ENABLE_DC
7310         bc_num_init(&G.prog.strmb, BC_NUM_DEF_SIZE);
7311         bc_num_ulong2num(&G.prog.strmb, UCHAR_MAX + 1);
7312 #endif
7313
7314         bc_num_init(&G.prog.last, BC_NUM_DEF_SIZE);
7315         bc_num_zero(&G.prog.last);
7316
7317         bc_num_init(&G.prog.zero, BC_NUM_DEF_SIZE);
7318         bc_num_zero(&G.prog.zero);
7319
7320         bc_num_init(&G.prog.one, BC_NUM_DEF_SIZE);
7321         bc_num_one(&G.prog.one);
7322
7323         bc_vec_init(&G.prog.fns, sizeof(BcFunc), bc_func_free);
7324         bc_vec_init(&G.prog.fn_map, sizeof(BcId), bc_id_free);
7325
7326         bc_program_addFunc(xstrdup("(main)"), &idx);
7327         bc_program_addFunc(xstrdup("(read)"), &idx);
7328
7329         bc_vec_init(&G.prog.vars, sizeof(BcVec), bc_vec_free);
7330         bc_vec_init(&G.prog.var_map, sizeof(BcId), bc_id_free);
7331
7332         bc_vec_init(&G.prog.arrs, sizeof(BcVec), bc_vec_free);
7333         bc_vec_init(&G.prog.arr_map, sizeof(BcId), bc_id_free);
7334
7335         bc_vec_init(&G.prog.strs, sizeof(char *), bc_string_free);
7336         bc_vec_init(&G.prog.consts, sizeof(char *), bc_string_free);
7337         bc_vec_init(&G.prog.results, sizeof(BcResult), bc_result_free);
7338         bc_vec_init(&G.prog.stack, sizeof(BcInstPtr), NULL);
7339         bc_vec_push(&G.prog.stack, &ip);
7340 }
7341
7342 static void bc_vm_init(const char *env_len)
7343 {
7344         size_t len = bc_vm_envLen(env_len);
7345
7346         bc_vec_init(&G.files, sizeof(char *), NULL);
7347
7348         if (IS_BC) {
7349                 bc_vm_envArgs();
7350         }
7351
7352         bc_program_init(len);
7353         if (IS_BC) {
7354                 bc_parse_init(&G.prs, BC_PROG_MAIN);
7355         } else {
7356                 dc_parse_init(&G.prs, BC_PROG_MAIN);
7357         }
7358 }
7359
7360 static BcStatus bc_vm_run(int argc, char *argv[],
7361                           const char *env_len)
7362 {
7363         BcStatus st;
7364
7365         bc_vm_init(env_len);
7366         bc_args(argc, argv);
7367
7368         G.ttyin = isatty(0);
7369
7370         if (G.ttyin) {
7371 #if ENABLE_FEATURE_BC_SIGNALS
7372                 // With SA_RESTART, most system calls will restart
7373                 // (IOW: they won't fail with EINTR).
7374                 // In particular, this means ^C won't cause
7375                 // stdout to get into "error state" if SIGINT hits
7376                 // within write() syscall.
7377                 // The downside is that ^C while line input is taken
7378                 // will only be handled after [Enter] since read()
7379                 // from stdin is not interrupted by ^C either,
7380                 // it restarts, thus fgetc() does not return on ^C.
7381                 signal_SA_RESTART_empty_mask(SIGINT, record_signo);
7382
7383                 // Without SA_RESTART, this exhibits a bug:
7384                 // "while (1) print 1" and try ^C-ing it.
7385                 // Intermittently, instead of returning to input line,
7386                 // you'll get "output error: Interrupted system call"
7387                 // and exit.
7388                 //signal_no_SA_RESTART_empty_mask(SIGINT, record_signo);
7389 #endif
7390                 if (!(option_mask32 & BC_FLAG_Q))
7391                         bc_vm_info();
7392         }
7393         st = bc_vm_exec();
7394
7395 #if ENABLE_FEATURE_CLEAN_UP
7396         bc_vm_free();
7397 #endif
7398         return st;
7399 }
7400
7401 #if ENABLE_BC
7402 int bc_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
7403 int bc_main(int argc, char **argv)
7404 {
7405         INIT_G();
7406         G.sbgn = G.send = '"';
7407
7408         return bc_vm_run(argc, argv, "BC_LINE_LENGTH");
7409 }
7410 #endif
7411
7412 #if ENABLE_DC
7413 int dc_main(int argc, char **argv) MAIN_EXTERNALLY_VISIBLE;
7414 int dc_main(int argc, char **argv)
7415 {
7416         INIT_G();
7417         G.sbgn = '[';
7418         G.send = ']';
7419
7420         return bc_vm_run(argc, argv, "DC_LINE_LENGTH");
7421 }
7422 #endif