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