/* vi: set sw=4 ts=4: */
/*
 * Licensed under GPLv2 or later, see file LICENSE in this source tree.
 * Adapted from https://github.com/gavinhoward/bc
 * Original code copyright (c) 2018 Gavin D. Howard and contributors.
 */
//TODO:
// maybe implement a^b for non-integer b?

#define DEBUG_LEXER   0
#define DEBUG_COMPILE 0
#define DEBUG_EXEC    0
// This can be left enabled for production as well:
#define SANITY_CHECKS 1

//config:config BC
//config:       bool "bc (45 kb)"
//config:       default y
//config:       select FEATURE_DC_BIG
//config:       help
//config:       bc is a command-line, arbitrary-precision calculator with a
//config:       Turing-complete language. See the GNU bc manual
//config:       (https://www.gnu.org/software/bc/manual/bc.html) and bc spec
//config:       (http://pubs.opengroup.org/onlinepubs/9699919799/utilities/bc.html).
//config:
//config:       This bc has five differences to the GNU bc:
//config:         1) The period (.) is a shortcut for "last", as in the BSD bc.
//config:         2) Arrays are copied before being passed as arguments to
//config:            functions. This behavior is required by the bc spec.
//config:         3) Arrays can be passed to the builtin "length" function to get
//config:            the number of elements in the array. This prints "1":
//config:               a[0] = 0; length(a[])
//config:         4) The precedence of the boolean "not" operator (!) is equal to
//config:            that of the unary minus (-) negation operator. This still
//config:            allows POSIX-compliant scripts to work while somewhat
//config:            preserving expected behavior (versus C) and making parsing
//config:            easier.
//config:         5) "read()" accepts expressions, not only numeric literals.
//config:
//config:config DC
//config:       bool "dc (36 kb)"
//config:       default y
//config:       help
//config:       dc is a reverse-polish notation command-line calculator which
//config:       supports unlimited precision arithmetic. See the FreeBSD man page
//config:       (https://www.unix.com/man-page/FreeBSD/1/dc/) and GNU dc manual
//config:       (https://www.gnu.org/software/bc/manual/dc-1.05/html_mono/dc.html).
//config:
//config:       This dc has a few differences from the two above:
//config:         1) When printing a byte stream (command "P"), this dc follows what
//config:            the FreeBSD dc does.
//config:         2) Implements the GNU extensions for divmod ("~") and
//config:            modular exponentiation ("|").
//config:         3) Implements all FreeBSD extensions, except for "J" and "M".
//config:         4) Like the FreeBSD dc, this dc supports extended registers.
//config:            However, they are implemented differently. When it encounters
//config:            whitespace where a register should be, it skips the whitespace.
//config:            If the character following is not a lowercase letter, an error
//config:            is issued. Otherwise, the register name is parsed by the
//config:            following regex: [a-z][a-z0-9_]*
//config:            This generally means that register names will be surrounded by
//config:            whitespace. Examples:
//config:               l idx s temp L index S temp2 < do_thing
//config:            Also note that, like the FreeBSD dc, extended registers are not
//config:            allowed unless the "-x" option is given.
//config:
//config:if BC || DC  # for menuconfig indenting
//config:
//config:config FEATURE_DC_BIG
//config:       bool "Use bc code base for dc (larger, more features)"
//config:       default y
//config:
//config:config FEATURE_DC_LIBM
//config:       bool "Enable power and exp functions (requires libm)"
//config:       default y
//config:       depends on DC && !BC && !FEATURE_DC_BIG
//config:       help
//config:       Enable power and exp functions.
//config:       NOTE: This will require libm to be present for linking.
//config:
//config:config FEATURE_BC_INTERACTIVE
//config:       bool "Interactive mode (+4kb)"
//config:       default y
//config:       depends on BC || (DC && FEATURE_DC_BIG)
//config:       help
//config:       Enable interactive mode: when started on a tty,
//config:       ^C interrupts execution and returns to command line,
//config:       errors also return to command line instead of exiting,
//config:       line editing with history is available.
//config:
//config:       With this option off, input can still be taken from tty,
//config:       but all errors are fatal, ^C is fatal,
//config:       tty is treated exactly the same as any other
//config:       standard input (IOW: no line editing).
//config:
//config:config FEATURE_BC_LONG_OPTIONS
//config:       bool "Enable bc/dc long options"
//config:       default y
//config:       depends on BC || (DC && FEATURE_DC_BIG)
//config:
//config:endif

//applet:IF_BC(APPLET(bc, BB_DIR_USR_BIN, BB_SUID_DROP))
//applet:IF_DC(APPLET(dc, BB_DIR_USR_BIN, BB_SUID_DROP))

//kbuild:lib-$(CONFIG_BC) += bc.o
//kbuild:lib-$(CONFIG_DC) += bc.o

//See www.gnu.org/software/bc/manual/bc.html
//usage:#define bc_trivial_usage
//usage:       "[-sqlw] FILE..."
//usage:
//usage:#define bc_full_usage "\n"
//usage:     "\nArbitrary precision calculator"
//usage:     "\n"
///////:     "\n        -i      Interactive" - has no effect for now
//usage:     "\n        -q      Quiet"
//usage:     "\n        -l      Load standard math library"
//usage:     "\n        -s      Be POSIX compatible"
//usage:     "\n        -w      Warn if extensions are used"
///////:     "\n        -v      Version"
//usage:     "\n"
//usage:     "\n$BC_LINE_LENGTH changes output width"
//usage:
//usage:#define bc_example_usage
//usage:       "3 + 4.129\n"
//usage:       "1903 - 2893\n"
//usage:       "-129 * 213.28935\n"
//usage:       "12 / -1932\n"
//usage:       "12 % 12\n"
//usage:       "34 ^ 189\n"
//usage:       "scale = 13\n"
//usage:       "ibase = 2\n"
//usage:       "obase = A\n"
//usage:
//usage:#define dc_trivial_usage
//usage:       IF_FEATURE_DC_BIG("[-x] ")"[-eSCRIPT]... [-fFILE]... [FILE]..."
//usage:
//usage:#define dc_full_usage "\n"
//usage:     "\nTiny RPN calculator. Operations:"
//usage:     "\n+, -, *, /, %, ~, ^," IF_FEATURE_DC_BIG(" |,")
//usage:     "\np - print top of the stack without popping"
//usage:     "\nf - print entire stack"
//usage:     "\nk - pop the value and set the precision"
//usage:     "\ni - pop the value and set input radix"
//usage:     "\no - pop the value and set output radix"
//usage:     "\nExamples: dc -e'2 2 + p' -> 4, dc -e'8 8 * 2 2 + / p' -> 16"
//usage:
//usage:#define dc_example_usage
//usage:       "$ dc -e'2 2 + p'\n"
//usage:       "4\n"
//usage:       "$ dc -e'8 8 \\* 2 2 + / p'\n"
//usage:       "16\n"
//usage:       "$ dc -e'0 1 & p'\n"
//usage:       "0\n"
//usage:       "$ dc -e'0 1 | p'\n"
//usage:       "1\n"
//usage:       "$ echo '72 9 / 8 * p' | dc\n"
//usage:       "64\n"

#include "libbb.h"
#include "common_bufsiz.h"

#if !ENABLE_BC && !ENABLE_FEATURE_DC_BIG
# include "dc.c"
#else

#if DEBUG_LEXER
static uint8_t lex_indent;
#define dbg_lex(...) \
        do { \
                fprintf(stderr, "%*s", lex_indent, ""); \
                bb_error_msg(__VA_ARGS__); \
        } while (0)
#define dbg_lex_enter(...) \
        do { \
                dbg_lex(__VA_ARGS__); \
                lex_indent++; \
        } while (0)
#define dbg_lex_done(...) \
        do { \
                lex_indent--; \
                dbg_lex(__VA_ARGS__); \
        } while (0)
#else
# define dbg_lex(...)       ((void)0)
# define dbg_lex_enter(...) ((void)0)
# define dbg_lex_done(...)  ((void)0)
#endif

#if DEBUG_COMPILE
# define dbg_compile(...) bb_error_msg(__VA_ARGS__)
#else
# define dbg_compile(...) ((void)0)
#endif

#if DEBUG_EXEC
# define dbg_exec(...) bb_error_msg(__VA_ARGS__)
#else
# define dbg_exec(...) ((void)0)
#endif

typedef enum BcStatus {
        BC_STATUS_SUCCESS = 0,
        BC_STATUS_FAILURE = 1,
} BcStatus;

#define BC_VEC_INVALID_IDX  ((size_t) -1)
#define BC_VEC_START_CAP    (1 << 5)

typedef void (*BcVecFree)(void *) FAST_FUNC;

typedef struct BcVec {
        char *v;
        size_t len;
        size_t cap;
        size_t size;
        BcVecFree dtor;
} BcVec;

typedef signed char BcDig;

typedef struct BcNum {
        BcDig *restrict num;
        size_t rdx;
        size_t len;
        size_t cap;
        bool neg;
} BcNum;

#define BC_NUM_MAX_IBASE        36
// larger value might speed up BIGNUM calculations a bit:
#define BC_NUM_DEF_SIZE         16
#define BC_NUM_PRINT_WIDTH      69

#define BC_NUM_KARATSUBA_LEN    32

typedef enum BcInst {
#if ENABLE_BC
        BC_INST_INC_PRE,
        BC_INST_DEC_PRE,
        BC_INST_INC_POST,
        BC_INST_DEC_POST,
#endif
        XC_INST_NEG,            // order

        XC_INST_REL_EQ,         // should
        XC_INST_REL_LE,         // match
        XC_INST_REL_GE,         // LEX
        XC_INST_REL_NE,         // constants
        XC_INST_REL_LT,         // for
        XC_INST_REL_GT,         // these

        XC_INST_POWER,          // operations
        XC_INST_MULTIPLY,       // |
        XC_INST_DIVIDE,         // |
        XC_INST_MODULUS,        // |
        XC_INST_PLUS,           // |
        XC_INST_MINUS,          // |

        XC_INST_BOOL_NOT,       // |
        XC_INST_BOOL_OR,        // |
        XC_INST_BOOL_AND,       // |
#if ENABLE_BC
        BC_INST_ASSIGN_POWER,   // |
        BC_INST_ASSIGN_MULTIPLY,// |
        BC_INST_ASSIGN_DIVIDE,  // |
        BC_INST_ASSIGN_MODULUS, // |
        BC_INST_ASSIGN_PLUS,    // |
        BC_INST_ASSIGN_MINUS,   // |
#endif
        XC_INST_ASSIGN,         // V

        XC_INST_NUM,
        XC_INST_VAR,
        XC_INST_ARRAY_ELEM,
        XC_INST_ARRAY,
        XC_INST_SCALE_FUNC,

        XC_INST_IBASE,       // order of these constans should match other enums
        XC_INST_OBASE,       // order of these constans should match other enums
        XC_INST_SCALE,       // order of these constans should match other enums
        IF_BC(BC_INST_LAST,) // order of these constans should match other enums
        XC_INST_LENGTH,
        XC_INST_READ,
        XC_INST_SQRT,

        XC_INST_PRINT,
        XC_INST_PRINT_POP,
        XC_INST_STR,
        XC_INST_PRINT_STR,

#if ENABLE_BC
        BC_INST_HALT,
        BC_INST_JUMP,
        BC_INST_JUMP_ZERO,

        BC_INST_CALL,
        BC_INST_RET0,
#endif
        XC_INST_RET,

        XC_INST_POP,
#if ENABLE_DC
        DC_INST_POP_EXEC,

        DC_INST_MODEXP,
        DC_INST_DIVMOD,

        DC_INST_EXECUTE,
        DC_INST_EXEC_COND,

        DC_INST_ASCIIFY,
        DC_INST_PRINT_STREAM,

        DC_INST_PRINT_STACK,
        DC_INST_CLEAR_STACK,
        DC_INST_STACK_LEN,
        DC_INST_DUPLICATE,
        DC_INST_SWAP,

        DC_INST_LOAD,
        DC_INST_PUSH_VAR,
        DC_INST_PUSH_TO_VAR,

        DC_INST_QUIT,
        DC_INST_NQUIT,

        DC_INST_INVALID = -1,
#endif
} BcInst;

typedef struct BcId {
        char *name;
        size_t idx;
} BcId;

typedef struct BcFunc {
        BcVec code;
        IF_BC(BcVec labels;)
        IF_BC(BcVec autos;)
        IF_BC(BcVec strs;)
        IF_BC(BcVec consts;)
        IF_BC(size_t nparams;)
        IF_BC(bool voidfunc;)
} BcFunc;

typedef enum BcResultType {
        XC_RESULT_TEMP,
        IF_BC(BC_RESULT_VOID,) // same as TEMP, but INST_PRINT will ignore it

        XC_RESULT_VAR,
        XC_RESULT_ARRAY_ELEM,
        XC_RESULT_ARRAY,

        XC_RESULT_STR,

        //code uses "inst - XC_INST_IBASE + XC_RESULT_IBASE" construct,
        XC_RESULT_IBASE,       // relative order should match for: XC_INST_IBASE
        XC_RESULT_OBASE,       // relative order should match for: XC_INST_OBASE
        XC_RESULT_SCALE,       // relative order should match for: XC_INST_SCALE
        IF_BC(BC_RESULT_LAST,) // relative order should match for: BC_INST_LAST
        XC_RESULT_CONSTANT,
        IF_BC(BC_RESULT_ONE,)
} BcResultType;

typedef union BcResultData {
        BcNum n;
        BcVec v;
        BcId id;
} BcResultData;

typedef struct BcResult {
        BcResultType t;
        BcResultData d;
} BcResult;

typedef struct BcInstPtr {
        size_t func;
        size_t inst_idx;
} BcInstPtr;

typedef enum BcType {
        BC_TYPE_VAR,
        BC_TYPE_ARRAY,
        BC_TYPE_REF,
} BcType;

typedef enum BcLexType {
        XC_LEX_EOF,
        XC_LEX_INVALID,

        XC_LEX_NLINE,
        XC_LEX_WHITESPACE,
        XC_LEX_STR,
        XC_LEX_NAME,
        XC_LEX_NUMBER,

        XC_LEX_1st_op,
        XC_LEX_NEG = XC_LEX_1st_op,     // order

        XC_LEX_OP_REL_EQ,               // should
        XC_LEX_OP_REL_LE,               // match
        XC_LEX_OP_REL_GE,               // INST
        XC_LEX_OP_REL_NE,               // constants
        XC_LEX_OP_REL_LT,               // for
        XC_LEX_OP_REL_GT,               // these

        XC_LEX_OP_POWER,                // operations
        XC_LEX_OP_MULTIPLY,             // |
        XC_LEX_OP_DIVIDE,               // |
        XC_LEX_OP_MODULUS,              // |
        XC_LEX_OP_PLUS,                 // |
        XC_LEX_OP_MINUS,                // |
        XC_LEX_OP_last = XC_LEX_OP_MINUS,
#if ENABLE_BC
        BC_LEX_OP_BOOL_NOT,             // |
        BC_LEX_OP_BOOL_OR,              // |
        BC_LEX_OP_BOOL_AND,             // |

        BC_LEX_OP_ASSIGN_POWER,         // |
        BC_LEX_OP_ASSIGN_MULTIPLY,      // |
        BC_LEX_OP_ASSIGN_DIVIDE,        // |
        BC_LEX_OP_ASSIGN_MODULUS,       // |
        BC_LEX_OP_ASSIGN_PLUS,          // |
        BC_LEX_OP_ASSIGN_MINUS,         // |

        BC_LEX_OP_ASSIGN,               // V

        BC_LEX_OP_INC,
        BC_LEX_OP_DEC,

        BC_LEX_LPAREN, // () are 0x28 and 0x29
        BC_LEX_RPAREN, // must be LPAREN+1: code uses (c - '(' + BC_LEX_LPAREN)

        BC_LEX_LBRACKET, // [] are 0x5B and 0x5D
        BC_LEX_COMMA,
        BC_LEX_RBRACKET, // must be LBRACKET+2: code uses (c - '[' + BC_LEX_LBRACKET)

        BC_LEX_LBRACE, // {} are 0x7B and 0x7D
        BC_LEX_SCOLON,
        BC_LEX_RBRACE, // must be LBRACE+2: code uses (c - '{' + BC_LEX_LBRACE)

        BC_LEX_KEY_1st_keyword,
        BC_LEX_KEY_AUTO = BC_LEX_KEY_1st_keyword,
        BC_LEX_KEY_BREAK,
        BC_LEX_KEY_CONTINUE,
        BC_LEX_KEY_DEFINE,
        BC_LEX_KEY_ELSE,
        BC_LEX_KEY_FOR,
        BC_LEX_KEY_HALT,
        // code uses "type - BC_LEX_KEY_IBASE + XC_INST_IBASE" construct,
        BC_LEX_KEY_IBASE,    // relative order should match for: XC_INST_IBASE
        BC_LEX_KEY_OBASE,    // relative order should match for: XC_INST_OBASE
        BC_LEX_KEY_IF,
        BC_LEX_KEY_LAST,     // relative order should match for: BC_INST_LAST
        BC_LEX_KEY_LENGTH,
        BC_LEX_KEY_LIMITS,
        BC_LEX_KEY_PRINT,
        BC_LEX_KEY_QUIT,
        BC_LEX_KEY_READ,
        BC_LEX_KEY_RETURN,
        BC_LEX_KEY_SCALE,
        BC_LEX_KEY_SQRT,
        BC_LEX_KEY_WHILE,
#endif // ENABLE_BC

#if ENABLE_DC
        DC_LEX_OP_BOOL_NOT = XC_LEX_OP_last + 1,
        DC_LEX_OP_ASSIGN,

        DC_LEX_LPAREN,
        DC_LEX_SCOLON,
        DC_LEX_READ,
        DC_LEX_IBASE,
        DC_LEX_SCALE,
        DC_LEX_OBASE,
        DC_LEX_LENGTH,
        DC_LEX_PRINT,
        DC_LEX_QUIT,
        DC_LEX_SQRT,
        DC_LEX_LBRACE,

        DC_LEX_EQ_NO_REG,
        DC_LEX_OP_MODEXP,
        DC_LEX_OP_DIVMOD,

        DC_LEX_COLON,
        DC_LEX_ELSE,
        DC_LEX_EXECUTE,
        DC_LEX_PRINT_STACK,
        DC_LEX_CLEAR_STACK,
        DC_LEX_STACK_LEVEL,
        DC_LEX_DUPLICATE,
        DC_LEX_SWAP,
        DC_LEX_POP,

        DC_LEX_ASCIIFY,
        DC_LEX_PRINT_STREAM,

        // code uses "t - DC_LEX_STORE_IBASE + XC_INST_IBASE" construct,
        DC_LEX_STORE_IBASE,  // relative order should match for: XC_INST_IBASE
        DC_LEX_STORE_OBASE,  // relative order should match for: XC_INST_OBASE
        DC_LEX_STORE_SCALE,  // relative order should match for: XC_INST_SCALE
        DC_LEX_LOAD,
        DC_LEX_LOAD_POP,
        DC_LEX_STORE_PUSH,
        DC_LEX_PRINT_POP,
        DC_LEX_NQUIT,
        DC_LEX_SCALE_FACTOR,
#endif
} BcLexType;
// must match order of BC_LEX_KEY_foo etc above
#if ENABLE_BC
struct BcLexKeyword {
        char name8[8];
};
#define LEX_KW_ENTRY(a, b) \
        { .name8 = a /*, .posix = b */ }
static const struct BcLexKeyword bc_lex_kws[20] = {
        LEX_KW_ENTRY("auto"    , 1), // 0
        LEX_KW_ENTRY("break"   , 1), // 1
        LEX_KW_ENTRY("continue", 0), // 2 note: this one has no terminating NUL
        LEX_KW_ENTRY("define"  , 1), // 3
        LEX_KW_ENTRY("else"    , 0), // 4
        LEX_KW_ENTRY("for"     , 1), // 5
        LEX_KW_ENTRY("halt"    , 0), // 6
        LEX_KW_ENTRY("ibase"   , 1), // 7
        LEX_KW_ENTRY("obase"   , 1), // 8
        LEX_KW_ENTRY("if"      , 1), // 9
        LEX_KW_ENTRY("last"    , 0), // 10
        LEX_KW_ENTRY("length"  , 1), // 11
        LEX_KW_ENTRY("limits"  , 0), // 12
        LEX_KW_ENTRY("print"   , 0), // 13
        LEX_KW_ENTRY("quit"    , 1), // 14
        LEX_KW_ENTRY("read"    , 0), // 15
        LEX_KW_ENTRY("return"  , 1), // 16
        LEX_KW_ENTRY("scale"   , 1), // 17
        LEX_KW_ENTRY("sqrt"    , 1), // 18
        LEX_KW_ENTRY("while"   , 1), // 19
};
#undef LEX_KW_ENTRY
#define STRING_else  (bc_lex_kws[4].name8)
#define STRING_for   (bc_lex_kws[5].name8)
#define STRING_if    (bc_lex_kws[9].name8)
#define STRING_while (bc_lex_kws[19].name8)
enum {
        POSIX_KWORD_MASK = 0
                | (1 << 0)  // 0
                | (1 << 1)  // 1
                | (0 << 2)  // 2
                | (1 << 3)  // 3
                | (0 << 4)  // 4
                | (1 << 5)  // 5
                | (0 << 6)  // 6
                | (1 << 7)  // 7
                | (1 << 8)  // 8
                | (1 << 9)  // 9
                | (0 << 10) // 10
                | (1 << 11) // 11
                | (0 << 12) // 12
                | (0 << 13) // 13
                | (1 << 14) // 14
                | (0 << 15) // 15
                | (1 << 16) // 16
                | (1 << 17) // 17
                | (1 << 18) // 18
                | (1 << 19) // 19
};
#define keyword_is_POSIX(i) ((1 << (i)) & POSIX_KWORD_MASK)

// This is a bit array that corresponds to token types. An entry is
// true if the token is valid in an expression, false otherwise.
// Used to figure out when expr parsing should stop *without error message*
// - 0 element indicates this condition. 1 means "this token is to be eaten
// as part of the expression", it can then still be determined to be invalid
// by later processing.
enum {
#define EXBITS(a,b,c,d,e,f,g,h) \
        ((uint64_t)((a << 0)+(b << 1)+(c << 2)+(d << 3)+(e << 4)+(f << 5)+(g << 6)+(h << 7)))
        BC_PARSE_EXPRS_BITS = 0              // corresponding BC_LEX_xyz:
        + (EXBITS(0,0,0,0,0,1,1,1) << (0*8)) //  0: EOF    INVAL  NL     WS     STR    NAME   NUM    -
        + (EXBITS(1,1,1,1,1,1,1,1) << (1*8)) //  8: ==     <=     >=     !=     <      >      ^      *
        + (EXBITS(1,1,1,1,1,1,1,1) << (2*8)) // 16: /      %      +      -      !      ||     &&     ^=
        + (EXBITS(1,1,1,1,1,1,1,1) << (3*8)) // 24: *=     /=     %=     +=     -=     =      ++     --
        + (EXBITS(1,1,0,0,0,0,0,0) << (4*8)) // 32: (      )      [      ,      ]      {      ;      }
        + (EXBITS(0,0,0,0,0,0,0,1) << (5*8)) // 40: auto   break  cont   define else   for    halt   ibase
        + (EXBITS(1,0,1,1,0,0,0,1) << (6*8)) // 48: obase  if     last   length limits print  quit   read
        + (EXBITS(0,1,1,0,0,0,0,0) << (7*8)) // 56: return scale  sqrt   while
#undef EXBITS
};
static ALWAYS_INLINE long lex_allowed_in_bc_expr(unsigned i)
{
#if ULONG_MAX > 0xffffffff
        // 64-bit version (will not work correctly for 32-bit longs!)
        return BC_PARSE_EXPRS_BITS & (1UL << i);
#else
        // 32-bit version
        unsigned long m = (uint32_t)BC_PARSE_EXPRS_BITS;
        if (i >= 32) {
                m = (uint32_t)(BC_PARSE_EXPRS_BITS >> 32);
                i &= 31;
        }
        return m & (1UL << i);
#endif
}

// This is an array of data for operators that correspond to
// [XC_LEX_1st_op...] token types.
static const uint8_t bc_ops_prec_and_assoc[] ALIGN1 = {
#define OP(p,l) ((int)(l) * 0x10 + (p))
        OP(1, false), // neg
        OP(6, true ), OP( 6, true  ), OP( 6, true  ), OP( 6, true  ), OP( 6, true  ), OP( 6, true ), // == <= >= != < >
        OP(2, false), // pow
        OP(3, true ), OP( 3, true  ), OP( 3, true  ), // mul div mod
        OP(4, true ), OP( 4, true  ), // + -
        OP(1, false), // not
        OP(7, true ), OP( 7, true  ), // or and
        OP(5, false), OP( 5, false ), OP( 5, false ), OP( 5, false ), OP( 5, false ), // ^= *= /= %= +=
        OP(5, false), OP( 5, false ), // -= =
        OP(0, false), OP( 0, false ), // inc dec
#undef OP
};
#define bc_operation_PREC(i) (bc_ops_prec_and_assoc[i] & 0x0f)
#define bc_operation_LEFT(i) (bc_ops_prec_and_assoc[i] & 0x10)
#endif // ENABLE_BC

#if ENABLE_DC
static const //BcLexType - should be this type
uint8_t
dc_char_to_LEX[] ALIGN1 = {
        // %&'(
        XC_LEX_OP_MODULUS, XC_LEX_INVALID, XC_LEX_INVALID, DC_LEX_LPAREN,
        // )*+,
        XC_LEX_INVALID, XC_LEX_OP_MULTIPLY, XC_LEX_OP_PLUS, XC_LEX_INVALID,
        // -./
        XC_LEX_OP_MINUS, XC_LEX_INVALID, XC_LEX_OP_DIVIDE,
        // 0123456789
        XC_LEX_INVALID, XC_LEX_INVALID, XC_LEX_INVALID, XC_LEX_INVALID,
        XC_LEX_INVALID, XC_LEX_INVALID, XC_LEX_INVALID, XC_LEX_INVALID,
        XC_LEX_INVALID, XC_LEX_INVALID,
        // :;<=>?@
        DC_LEX_COLON, DC_LEX_SCOLON, XC_LEX_OP_REL_GT, XC_LEX_OP_REL_EQ,
        XC_LEX_OP_REL_LT, DC_LEX_READ, XC_LEX_INVALID,
        // ABCDEFGH
        XC_LEX_INVALID, XC_LEX_INVALID, XC_LEX_INVALID, XC_LEX_INVALID,
        XC_LEX_INVALID, XC_LEX_INVALID, DC_LEX_EQ_NO_REG, XC_LEX_INVALID,
        // IJKLMNOP
        DC_LEX_IBASE, XC_LEX_INVALID, DC_LEX_SCALE, DC_LEX_LOAD_POP,
        XC_LEX_INVALID, DC_LEX_OP_BOOL_NOT, DC_LEX_OBASE, DC_LEX_PRINT_STREAM,
        // QRSTUVWX
        DC_LEX_NQUIT, DC_LEX_POP, DC_LEX_STORE_PUSH, XC_LEX_INVALID,
        XC_LEX_INVALID, XC_LEX_INVALID, XC_LEX_INVALID, DC_LEX_SCALE_FACTOR,
        // YZ
        XC_LEX_INVALID, DC_LEX_LENGTH,
        // [\]
        XC_LEX_INVALID, XC_LEX_INVALID, XC_LEX_INVALID,
        // ^_`
        XC_LEX_OP_POWER, XC_LEX_NEG, XC_LEX_INVALID,
        // abcdefgh
        DC_LEX_ASCIIFY, XC_LEX_INVALID, DC_LEX_CLEAR_STACK, DC_LEX_DUPLICATE,
        DC_LEX_ELSE, DC_LEX_PRINT_STACK, XC_LEX_INVALID, XC_LEX_INVALID,
        // ijklmnop
        DC_LEX_STORE_IBASE, XC_LEX_INVALID, DC_LEX_STORE_SCALE, DC_LEX_LOAD,
        XC_LEX_INVALID, DC_LEX_PRINT_POP, DC_LEX_STORE_OBASE, DC_LEX_PRINT,
        // qrstuvwx
        DC_LEX_QUIT, DC_LEX_SWAP, DC_LEX_OP_ASSIGN, XC_LEX_INVALID,
        XC_LEX_INVALID, DC_LEX_SQRT, XC_LEX_INVALID, DC_LEX_EXECUTE,
        // yz
        XC_LEX_INVALID, DC_LEX_STACK_LEVEL,
        // {|}~
        DC_LEX_LBRACE, DC_LEX_OP_MODEXP, XC_LEX_INVALID, DC_LEX_OP_DIVMOD,
};
static const //BcInst - should be this type. Using signed narrow type since DC_INST_INVALID is -1
int8_t
dc_LEX_to_INST[] ALIGN1 = { //starts at XC_LEX_OP_POWER // corresponding XC/DC_LEX_xyz:
        XC_INST_POWER,       XC_INST_MULTIPLY,          // XC_LEX_OP_POWER    XC_LEX_OP_MULTIPLY
        XC_INST_DIVIDE,      XC_INST_MODULUS,           // XC_LEX_OP_DIVIDE   XC_LEX_OP_MODULUS
        XC_INST_PLUS,        XC_INST_MINUS,             // XC_LEX_OP_PLUS     XC_LEX_OP_MINUS
        XC_INST_BOOL_NOT,                               // DC_LEX_OP_BOOL_NOT
        DC_INST_INVALID,                                // DC_LEX_OP_ASSIGN
        XC_INST_REL_GT,                                 // DC_LEX_LPAREN
        DC_INST_INVALID,                                // DC_LEX_SCOLON
        DC_INST_INVALID,                                // DC_LEX_READ
        XC_INST_IBASE,                                  // DC_LEX_IBASE
        XC_INST_SCALE,                                  // DC_LEX_SCALE
        XC_INST_OBASE,                                  // DC_LEX_OBASE
        XC_INST_LENGTH,                                 // DC_LEX_LENGTH
        XC_INST_PRINT,                                  // DC_LEX_PRINT
        DC_INST_QUIT,                                   // DC_LEX_QUIT
        XC_INST_SQRT,                                   // DC_LEX_SQRT
        XC_INST_REL_GE,                                 // DC_LEX_LBRACE
        XC_INST_REL_EQ,                                 // DC_LEX_EQ_NO_REG
        DC_INST_MODEXP,      DC_INST_DIVMOD,            // DC_LEX_OP_MODEXP   DC_LEX_OP_DIVMOD
        DC_INST_INVALID,     DC_INST_INVALID,           // DC_LEX_COLON       DC_LEX_ELSE
        DC_INST_EXECUTE,                                // DC_LEX_EXECUTE
        DC_INST_PRINT_STACK, DC_INST_CLEAR_STACK,       // DC_LEX_PRINT_STACK DC_LEX_CLEAR_STACK
        DC_INST_STACK_LEN,   DC_INST_DUPLICATE,         // DC_LEX_STACK_LEVEL DC_LEX_DUPLICATE
        DC_INST_SWAP,        XC_INST_POP,               // DC_LEX_SWAP        DC_LEX_POP
        DC_INST_ASCIIFY,     DC_INST_PRINT_STREAM,      // DC_LEX_ASCIIFY     DC_LEX_PRINT_STREAM
        DC_INST_INVALID,     DC_INST_INVALID,           // DC_LEX_STORE_IBASE DC_LEX_STORE_OBASE
        DC_INST_INVALID,     DC_INST_INVALID,           // DC_LEX_STORE_SCALE DC_LEX_LOAD
        DC_INST_INVALID,     DC_INST_INVALID,           // DC_LEX_LOAD_POP    DC_LEX_STORE_PUSH
        XC_INST_PRINT,       DC_INST_NQUIT,             // DC_LEX_PRINT_POP   DC_LEX_NQUIT
        XC_INST_SCALE_FUNC,                             // DC_LEX_SCALE_FACTOR
        // DC_INST_INVALID in this table either means that corresponding LEX
        // is not possible for dc, or that it does not compile one-to-one
        // to a single INST.
};
#endif // ENABLE_DC

typedef struct BcParse {
        smallint lex;      // was BcLexType // first member is most used
        smallint lex_last; // was BcLexType
        size_t lex_line;
        const char *lex_inbuf;
        const char *lex_next_at; // last lex_next() was called at this string
        const char *lex_filename;
        FILE *lex_input_fp;
        BcVec  lex_strnumbuf;

        BcFunc *func;
        size_t fidx;
        IF_BC(size_t in_funcdef;)
        IF_BC(BcVec exits;)
        IF_BC(BcVec conds;)
        IF_BC(BcVec ops;)
} BcParse;

typedef struct BcProgram {
        size_t len;
        size_t nchars;

        size_t scale;
        size_t ib_t;
        size_t ob_t;

        BcVec results;
        BcVec exestack;

        BcVec fns;
        IF_BC(BcVec fn_map;)

        BcVec vars;
        BcVec var_map;

        BcVec arrs;
        BcVec arr_map;

        IF_DC(BcVec strs;)
        IF_DC(BcVec consts;)

        BcNum zero;
        IF_BC(BcNum one;)
        IF_BC(BcNum last;)
} BcProgram;

struct globals {
        BcParse prs; // first member is most used

        // For error messages. Can be set to current parsed line,
        // or [TODO] to current executing line (can be before last parsed one)
        size_t err_line;

        BcVec input_buffer;

        IF_FEATURE_BC_INTERACTIVE(smallint ttyin;)
        IF_FEATURE_CLEAN_UP(smallint exiting;)

        BcProgram prog;

        BcVec files;

        char *env_args;

#if ENABLE_FEATURE_EDITING
        line_input_t *line_input_state;
#endif
} FIX_ALIASING;
#define G (*ptr_to_globals)
#define INIT_G() do { \
        SET_PTR_TO_GLOBALS(xzalloc(sizeof(G))); \
} while (0)
#define FREE_G() do { \
        FREE_PTR_TO_GLOBALS(); \
} while (0)
#define G_posix (ENABLE_BC && (option_mask32 & BC_FLAG_S))
#define G_warn  (ENABLE_BC && (option_mask32 & BC_FLAG_W))
#define G_exreg (ENABLE_DC && (option_mask32 & DC_FLAG_X))
#if ENABLE_FEATURE_BC_INTERACTIVE
# define G_interrupt bb_got_signal
# define G_ttyin     G.ttyin
#else
# define G_interrupt 0
# define G_ttyin     0
#endif
#if ENABLE_FEATURE_CLEAN_UP
# define G_exiting G.exiting
#else
# define G_exiting 0
#endif
#define IS_BC (ENABLE_BC && (!ENABLE_DC || applet_name[0] == 'b'))
#define IS_DC (ENABLE_DC && (!ENABLE_BC || applet_name[0] != 'b'))

#if ENABLE_BC
# define BC_PARSE_REL           (1 << 0)
# define BC_PARSE_PRINT         (1 << 1)
# define BC_PARSE_ARRAY         (1 << 2)
# define BC_PARSE_NOCALL        (1 << 3)
#endif

#define BC_PROG_MAIN      0
#define BC_PROG_READ      1
#if ENABLE_DC
#define BC_PROG_REQ_FUNCS 2
#endif

#define BC_FLAG_W (1 << 0)
#define BC_FLAG_V (1 << 1)
#define BC_FLAG_S (1 << 2)
#define BC_FLAG_Q (1 << 3)
#define BC_FLAG_L (1 << 4)
#define BC_FLAG_I ((1 << 5) * ENABLE_DC)
#define DC_FLAG_X ((1 << 6) * ENABLE_DC)

#define BC_MAX_OBASE    ((unsigned) 999)
#define BC_MAX_DIM      ((unsigned) INT_MAX)
#define BC_MAX_SCALE    ((unsigned) UINT_MAX)
#define BC_MAX_STRING   ((unsigned) UINT_MAX - 1)
#define BC_MAX_NUM      BC_MAX_STRING
// Unused apart from "limits" message. Just show a "biggish number" there.
//#define BC_MAX_EXP      ((unsigned long) LONG_MAX)
//#define BC_MAX_VARS     ((unsigned long) SIZE_MAX - 1)
#define BC_MAX_EXP_STR  "999999999"
#define BC_MAX_VARS_STR "999999999"

#define BC_MAX_OBASE_STR "999"

#if INT_MAX == 2147483647
# define BC_MAX_DIM_STR "2147483647"
#elif INT_MAX == 9223372036854775807
# define BC_MAX_DIM_STR "9223372036854775807"
#else
# error Strange INT_MAX
#endif

#if UINT_MAX == 4294967295
# define BC_MAX_SCALE_STR  "4294967295"
# define BC_MAX_STRING_STR "4294967294"
#elif UINT_MAX == 18446744073709551615
# define BC_MAX_SCALE_STR  "18446744073709551615"
# define BC_MAX_STRING_STR "18446744073709551614"
#else
# error Strange UINT_MAX
#endif
#define BC_MAX_NUM_STR BC_MAX_STRING_STR

// In configurations where errors abort instead of propagating error
// return code up the call chain, functions returning BC_STATUS
// actually don't return anything, they always succeed and return "void".
// A macro wrapper is provided, which makes this statement work:
//  s = zbc_func(...)
// and makes it visible to the compiler that s is always zero,
// allowing compiler to optimize dead code after the statement.
//
// To make code more readable, each such function has a "z"
// ("always returning zero") prefix, i.e. zbc_foo or zdc_foo.
//
#if ENABLE_FEATURE_BC_INTERACTIVE || ENABLE_FEATURE_CLEAN_UP
# define ERRORS_ARE_FATAL 0
# define ERRORFUNC        /*nothing*/
# define IF_ERROR_RETURN_POSSIBLE(a)  a
# define BC_STATUS        BcStatus
# define RETURN_STATUS(v) return (v)
# define COMMA_SUCCESS    /*nothing*/
#else
# define ERRORS_ARE_FATAL 1
# define ERRORFUNC        NORETURN
# define IF_ERROR_RETURN_POSSIBLE(a)  /*nothing*/
# define BC_STATUS        void
# define RETURN_STATUS(v) do { ((void)(v)); return; } while (0)
# define COMMA_SUCCESS    ,BC_STATUS_SUCCESS
#endif

//
// Utility routines
//

#define BC_MAX(a, b) ((a) > (b) ? (a) : (b))
#define BC_MIN(a, b) ((a) < (b) ? (a) : (b))

static void fflush_and_check(void)
{
        fflush_all();
        if (ferror(stdout) || ferror(stderr))
                bb_perror_msg_and_die("output error");
}

#if ENABLE_FEATURE_CLEAN_UP
#define QUIT_OR_RETURN_TO_MAIN \
do { \
        IF_FEATURE_BC_INTERACTIVE(G_ttyin = 0;) /* do not loop in main loop anymore */ \
        G_exiting = 1; \
        return BC_STATUS_FAILURE; \
} while (0)
#else
static void quit(void) NORETURN;
static void quit(void)
{
        if (ferror(stdin))
                bb_perror_msg_and_die("input error");
        fflush_and_check();
        dbg_exec("quit(): exiting with exitcode SUCCESS");
        exit(0);
}
#define QUIT_OR_RETURN_TO_MAIN quit()
#endif

static void bc_verror_msg(const char *fmt, va_list p)
{
        const char *sv = sv; // for compiler
        if (G.prs.lex_filename) {
                sv = applet_name;
                applet_name = xasprintf("%s: %s:%lu", applet_name,
                        G.prs.lex_filename, (unsigned long)G.err_line
                );
        }
        bb_verror_msg(fmt, p, NULL);
        if (G.prs.lex_filename) {
                free((char*)applet_name);
                applet_name = sv;
        }
}

static NOINLINE ERRORFUNC int bc_error_fmt(const char *fmt, ...)
{
        va_list p;

        va_start(p, fmt);
        bc_verror_msg(fmt, p);
        va_end(p);

        if (ENABLE_FEATURE_CLEAN_UP || G_ttyin)
                IF_ERROR_RETURN_POSSIBLE(return BC_STATUS_FAILURE);
        exit(1);
}

#if ENABLE_BC
static NOINLINE BC_STATUS zbc_posix_error_fmt(const char *fmt, ...)
{
        va_list p;

        // Are non-POSIX constructs totally ok?
        if (!(option_mask32 & (BC_FLAG_S|BC_FLAG_W)))
                RETURN_STATUS(BC_STATUS_SUCCESS); // yes

        va_start(p, fmt);
        bc_verror_msg(fmt, p);
        va_end(p);

        // Do we treat non-POSIX constructs as errors?
        if (!(option_mask32 & BC_FLAG_S))
                RETURN_STATUS(BC_STATUS_SUCCESS); // no, it's a warning

        if (ENABLE_FEATURE_CLEAN_UP || G_ttyin)
                RETURN_STATUS(BC_STATUS_FAILURE);
        exit(1);
}
#define zbc_posix_error_fmt(...) (zbc_posix_error_fmt(__VA_ARGS__) COMMA_SUCCESS)
#endif

// We use error functions with "return bc_error(FMT[, PARAMS])" idiom.
// This idiom begs for tail-call optimization, but for it to work,
// function must not have caller-cleaned parameters on stack.
// Unfortunately, vararg function API does exactly that on most arches.
// Thus, use these shims for the cases when we have no vararg PARAMS:
static ERRORFUNC int bc_error(const char *msg)
{
        IF_ERROR_RETURN_POSSIBLE(return) bc_error_fmt("%s", msg);
}
static ERRORFUNC int bc_error_at(const char *msg)
{
        const char *err_at = G.prs.lex_next_at;
        if (err_at) {
                IF_ERROR_RETURN_POSSIBLE(return) bc_error_fmt(
                        "%s at '%.*s'",
                        msg,
                        (int)(strchrnul(err_at, '\n') - err_at),
                        err_at
                );
        }
        IF_ERROR_RETURN_POSSIBLE(return) bc_error_fmt("%s", msg);
}
static ERRORFUNC int bc_error_bad_character(char c)
{
        if (!c)
                IF_ERROR_RETURN_POSSIBLE(return) bc_error("NUL character");
        IF_ERROR_RETURN_POSSIBLE(return) bc_error_fmt("bad character '%c'", c);
}
#if ENABLE_BC

static ERRORFUNC int bc_error_bad_function_definition(void)
{
        IF_ERROR_RETURN_POSSIBLE(return) bc_error_at("bad function definition");
}
#endif
static ERRORFUNC int bc_error_bad_expression(void)
{
        IF_ERROR_RETURN_POSSIBLE(return) bc_error_at("bad expression");
}
static ERRORFUNC int bc_error_bad_assignment(void)
{
        IF_ERROR_RETURN_POSSIBLE(return) bc_error_at(
                "bad assignment: left side must be variable or array element"
        );
}
static ERRORFUNC int bc_error_bad_token(void)
{
        IF_ERROR_RETURN_POSSIBLE(return) bc_error_at("bad token");
}
static ERRORFUNC int bc_error_stack_has_too_few_elements(void)
{
        IF_ERROR_RETURN_POSSIBLE(return) bc_error("stack has too few elements");
}
static ERRORFUNC int bc_error_variable_is_wrong_type(void)
{
        IF_ERROR_RETURN_POSSIBLE(return) bc_error("variable is wrong type");
}
#if ENABLE_BC
static BC_STATUS zbc_POSIX_requires(const char *msg)
{
        RETURN_STATUS(zbc_posix_error_fmt("POSIX requires %s", msg));
}
#define zbc_POSIX_requires(...) (zbc_POSIX_requires(__VA_ARGS__) COMMA_SUCCESS)
static BC_STATUS zbc_POSIX_does_not_allow(const char *msg)
{
        RETURN_STATUS(zbc_posix_error_fmt("%s%s", "POSIX does not allow ", msg));
}
#define zbc_POSIX_does_not_allow(...) (zbc_POSIX_does_not_allow(__VA_ARGS__) COMMA_SUCCESS)
static BC_STATUS zbc_POSIX_does_not_allow_bool_ops_this_is_bad(const char *msg)
{
        RETURN_STATUS(zbc_posix_error_fmt("%s%s %s", "POSIX does not allow ", "boolean operators; this is bad:", msg));
}
#define zbc_POSIX_does_not_allow_bool_ops_this_is_bad(...) (zbc_POSIX_does_not_allow_bool_ops_this_is_bad(__VA_ARGS__) COMMA_SUCCESS)
static BC_STATUS zbc_POSIX_does_not_allow_empty_X_expression_in_for(const char *msg)
{
        RETURN_STATUS(zbc_posix_error_fmt("%san empty %s expression in 'for()'", "POSIX does not allow ", msg));
}
#define zbc_POSIX_does_not_allow_empty_X_expression_in_for(...) (zbc_POSIX_does_not_allow_empty_X_expression_in_for(__VA_ARGS__) COMMA_SUCCESS)
#endif

static void bc_vec_grow(BcVec *v, size_t n)
{
        size_t cap = v->cap * 2;
        while (cap < v->len + n) cap *= 2;
        v->v = xrealloc(v->v, v->size * cap);
        v->cap = cap;
}

static void bc_vec_init(BcVec *v, size_t esize, BcVecFree dtor)
{
        v->size = esize;
        v->cap = BC_VEC_START_CAP;
        v->len = 0;
        v->dtor = dtor;
        v->v = xmalloc(esize * BC_VEC_START_CAP);
}

static void bc_char_vec_init(BcVec *v)
{
        bc_vec_init(v, sizeof(char), NULL);
}

static void bc_vec_expand(BcVec *v, size_t req)
{
        if (v->cap < req) {
                v->v = xrealloc(v->v, v->size * req);
                v->cap = req;
        }
}

static void bc_vec_pop(BcVec *v)
{
        v->len--;
        if (v->dtor)
                v->dtor(v->v + (v->size * v->len));
}

static void bc_vec_npop(BcVec *v, size_t n)
{
        if (!v->dtor)
                v->len -= n;
        else {
                size_t len = v->len - n;
                while (v->len > len) v->dtor(v->v + (v->size * --v->len));
        }
}

static void bc_vec_pop_all(BcVec *v)
{
        bc_vec_npop(v, v->len);
}

static size_t bc_vec_npush(BcVec *v, size_t n, const void *data)
{
        size_t len = v->len;
        if (len + n > v->cap) bc_vec_grow(v, n);
        memmove(v->v + (v->size * len), data, v->size * n);
        v->len = len + n;
        return len;
}

static size_t bc_vec_push(BcVec *v, const void *data)
{
        return bc_vec_npush(v, 1, data);
        //size_t len = v->len;
        //if (len >= v->cap) bc_vec_grow(v, 1);
        //memmove(v->v + (v->size * len), data, v->size);
        //v->len = len + 1;
        //return len;
}

// G.prog.results often needs "pop old operand, push result" idiom.
// Can do this without a few extra ops
static size_t bc_result_pop_and_push(const void *data)
{
        BcVec *v = &G.prog.results;
        char *last;
        size_t len = v->len - 1;

        last = v->v + (v->size * len);
        if (v->dtor)
                v->dtor(last);
        memmove(last, data, v->size);
        return len;
}

static size_t bc_vec_pushByte(BcVec *v, char data)
{
        return bc_vec_push(v, &data);
}

static size_t bc_vec_pushZeroByte(BcVec *v)
{
        //return bc_vec_pushByte(v, '\0');
        // better:
        return bc_vec_push(v, &const_int_0);
}

static void bc_vec_pushAt(BcVec *v, const void *data, size_t idx)
{
        if (idx == v->len)
                bc_vec_push(v, data);
        else {
                char *ptr;

                if (v->len == v->cap) bc_vec_grow(v, 1);

                ptr = v->v + v->size * idx;

                memmove(ptr + v->size, ptr, v->size * (v->len++ - idx));
                memmove(ptr, data, v->size);
        }
}

static void bc_vec_string(BcVec *v, size_t len, const char *str)
{
        bc_vec_pop_all(v);
        bc_vec_expand(v, len + 1);
        memcpy(v->v, str, len);
        v->len = len;

        bc_vec_pushZeroByte(v);
}

static void *bc_vec_item(const BcVec *v, size_t idx)
{
        return v->v + v->size * idx;
}

static void *bc_vec_item_rev(const BcVec *v, size_t idx)
{
        return v->v + v->size * (v->len - idx - 1);
}

static void *bc_vec_top(const BcVec *v)
{
        return v->v + v->size * (v->len - 1);
}

static FAST_FUNC void bc_vec_free(void *vec)
{
        BcVec *v = (BcVec *) vec;
        bc_vec_pop_all(v);
        free(v->v);
}

static BcFunc* xc_program_func(size_t idx)
{
        return bc_vec_item(&G.prog.fns, idx);
}
// BC_PROG_MAIN is zeroth element, so:
#define xc_program_func_BC_PROG_MAIN() ((BcFunc*)(G.prog.fns.v))

#if ENABLE_BC
static BcFunc* bc_program_current_func(void)
{
        BcInstPtr *ip = bc_vec_top(&G.prog.exestack);
        BcFunc *func = xc_program_func(ip->func);
        return func;
}
#endif

static char** xc_program_str(size_t idx)
{
#if ENABLE_BC
        if (IS_BC) {
                BcFunc *func = bc_program_current_func();
                return bc_vec_item(&func->strs, idx);
        }
#endif
        IF_DC(return bc_vec_item(&G.prog.strs, idx);)
}

static char** xc_program_const(size_t idx)
{
#if ENABLE_BC
        if (IS_BC) {
                BcFunc *func = bc_program_current_func();
                return bc_vec_item(&func->consts, idx);
        }
#endif
        IF_DC(return bc_vec_item(&G.prog.consts, idx);)
}

static int bc_id_cmp(const void *e1, const void *e2)
{
        return strcmp(((const BcId *) e1)->name, ((const BcId *) e2)->name);
}

static FAST_FUNC void bc_id_free(void *id)
{
        free(((BcId *) id)->name);
}

static size_t bc_map_find_ge(const BcVec *v, const void *ptr)
{
        size_t low = 0, high = v->len;

        while (low < high) {
                size_t mid = (low + high) / 2;
                BcId *id = bc_vec_item(v, mid);
                int result = bc_id_cmp(ptr, id);

                if (result == 0)
                        return mid;
                if (result < 0)
                        high = mid;
                else
                        low = mid + 1;
        }

        return low;
}

static int bc_map_insert(BcVec *v, const void *ptr, size_t *i)
{
        size_t n = *i = bc_map_find_ge(v, ptr);

        if (n == v->len)
                bc_vec_push(v, ptr);
        else if (!bc_id_cmp(ptr, bc_vec_item(v, n)))
                return 0; // "was not inserted"
        else
                bc_vec_pushAt(v, ptr, n);
        return 1; // "was inserted"
}

static size_t bc_map_find_exact(const BcVec *v, const void *ptr)
{
        size_t i = bc_map_find_ge(v, ptr);
        if (i >= v->len) return BC_VEC_INVALID_IDX;
        return bc_id_cmp(ptr, bc_vec_item(v, i)) ? BC_VEC_INVALID_IDX : i;
}

static void bc_num_setToZero(BcNum *n, size_t scale)
{
        n->len = 0;
        n->neg = false;
        n->rdx = scale;
}

static void bc_num_zero(BcNum *n)
{
        bc_num_setToZero(n, 0);
}

static void bc_num_one(BcNum *n)
{
        bc_num_setToZero(n, 0);
        n->len = 1;
        n->num[0] = 1;
}

// Note: this also sets BcNum to zero
static void bc_num_init(BcNum *n, size_t req)
{
        req = req >= BC_NUM_DEF_SIZE ? req : BC_NUM_DEF_SIZE;
        //memset(n, 0, sizeof(BcNum)); - cleared by assignments below
        n->num = xmalloc(req);
        n->cap = req;
        n->rdx = 0;
        n->len = 0;
        n->neg = false;
}

static void bc_num_init_DEF_SIZE(BcNum *n)
{
        bc_num_init(n, BC_NUM_DEF_SIZE);
}

static void bc_num_expand(BcNum *n, size_t req)
{
        req = req >= BC_NUM_DEF_SIZE ? req : BC_NUM_DEF_SIZE;
        if (req > n->cap) {
                n->num = xrealloc(n->num, req);
                n->cap = req;
        }
}

static FAST_FUNC void bc_num_free(void *num)
{
        free(((BcNum *) num)->num);
}

static void bc_num_copy(BcNum *d, BcNum *s)
{
        if (d != s) {
                bc_num_expand(d, s->cap);
                d->len = s->len;
                d->neg = s->neg;
                d->rdx = s->rdx;
                memcpy(d->num, s->num, sizeof(BcDig) * d->len);
        }
}

static BC_STATUS zbc_num_ulong_abs(BcNum *n, unsigned long *result_p)
{
        size_t i;
        unsigned long result;

        result = 0;
        i = n->len;
        while (i > n->rdx) {
                unsigned long prev = result;
                result = result * 10 + n->num[--i];
                // Even overflowed N*10 can still satisfy N*10>=N. For example,
                //    0x1ff00000 * 10 is 0x13f600000,
                // or 0x3f600000 truncated to 32 bits. Which is larger.
                // However, (N*10)/8 < N check is always correct.
                if ((result / 8) < prev)
                        RETURN_STATUS(bc_error("overflow"));
        }
        *result_p = result;

        RETURN_STATUS(BC_STATUS_SUCCESS);
}
#define zbc_num_ulong_abs(...) (zbc_num_ulong_abs(__VA_ARGS__) COMMA_SUCCESS)

static BC_STATUS zbc_num_ulong(BcNum *n, unsigned long *result_p)
{
        if (n->neg) RETURN_STATUS(bc_error("negative number"));

        RETURN_STATUS(zbc_num_ulong_abs(n, result_p));
}
#define zbc_num_ulong(...) (zbc_num_ulong(__VA_ARGS__) COMMA_SUCCESS)

#if ULONG_MAX == 0xffffffffUL // 10 digits: 4294967295
# define ULONG_NUM_BUFSIZE (10 > BC_NUM_DEF_SIZE ? 10 : BC_NUM_DEF_SIZE)
#elif ULONG_MAX == 0xffffffffffffffffULL // 20 digits: 18446744073709551615
# define ULONG_NUM_BUFSIZE (20 > BC_NUM_DEF_SIZE ? 20 : BC_NUM_DEF_SIZE)
#endif
// minimum BC_NUM_DEF_SIZE, so that bc_num_expand() in bc_num_ulong2num()
// would not hit realloc() code path - not good if num[] is not malloced

static void bc_num_ulong2num(BcNum *n, unsigned long val)
{
        BcDig *ptr;

        bc_num_zero(n);

        if (val == 0) return;

        bc_num_expand(n, ULONG_NUM_BUFSIZE);

        ptr = n->num;
        for (;;) {
                n->len++;
                *ptr++ = val % 10;
                val /= 10;
                if (val == 0) break;
        }
}

static void bc_num_subArrays(BcDig *restrict a, BcDig *restrict b, size_t len)
{
        size_t i, j;
        for (i = 0; i < len; ++i) {
                a[i] -= b[i];
                for (j = i; a[j] < 0;) {
                        a[j++] += 10;
                        a[j] -= 1;
                }
        }
}

static ssize_t bc_num_compare(BcDig *restrict a, BcDig *restrict b, size_t len)
{
        size_t i = len;
        for (;;) {
                int c;
                if (i == 0)
                        return 0;
                i--;
                c = a[i] - b[i];
                if (c != 0) {
                        i++;
                        if (c < 0)
                                return -i;
                        return i;
                }
        }
}

#define BC_NUM_NEG(n, neg)      ((((ssize_t)(n)) ^ -((ssize_t)(neg))) + (neg))
#define BC_NUM_ONE(n)           ((n)->len == 1 && (n)->rdx == 0 && (n)->num[0] == 1)
#define BC_NUM_INT(n)           ((n)->len - (n)->rdx)
//#define BC_NUM_AREQ(a, b)       (BC_MAX((a)->rdx, (b)->rdx) + BC_MAX(BC_NUM_INT(a), BC_NUM_INT(b)) + 1)
static /*ALWAYS_INLINE*/ size_t BC_NUM_AREQ(BcNum *a, BcNum *b)
{
        return BC_MAX(a->rdx, b->rdx) + BC_MAX(BC_NUM_INT(a), BC_NUM_INT(b)) + 1;
}
//#define BC_NUM_MREQ(a, b, scale) (BC_NUM_INT(a) + BC_NUM_INT(b) + BC_MAX((scale), (a)->rdx + (b)->rdx) + 1)
static /*ALWAYS_INLINE*/ size_t BC_NUM_MREQ(BcNum *a, BcNum *b, size_t scale)
{
        return BC_NUM_INT(a) + BC_NUM_INT(b) + BC_MAX(scale, a->rdx + b->rdx) + 1;
}

static ssize_t bc_num_cmp(BcNum *a, BcNum *b)
{
        size_t i, min, a_int, b_int, diff;
        BcDig *max_num, *min_num;
        bool a_max, neg;
        ssize_t cmp;

        if (a == b) return 0;
        if (a->len == 0) return BC_NUM_NEG(!!b->len, !b->neg);
        if (b->len == 0) return BC_NUM_NEG(1, a->neg);

        if (a->neg != b->neg) // signs of a and b differ
                // +a,-b = a>b = 1 or -a,+b = a<b = -1
                return (int)b->neg - (int)a->neg;
        neg = a->neg; // 1 if both negative, 0 if both positive

        a_int = BC_NUM_INT(a);
        b_int = BC_NUM_INT(b);
        a_int -= b_int;

        if (a_int != 0) return (ssize_t) a_int;

        a_max = (a->rdx > b->rdx);
        if (a_max) {
                min = b->rdx;
                diff = a->rdx - b->rdx;
                max_num = a->num + diff;
                min_num = b->num;
                // neg = (a_max == neg); - NOP (maps 1->1 and 0->0)
        } else {
                min = a->rdx;
                diff = b->rdx - a->rdx;
                max_num = b->num + diff;
                min_num = a->num;
                neg = !neg; // same as "neg = (a_max == neg)"
        }

        cmp = bc_num_compare(max_num, min_num, b_int + min);
        if (cmp != 0) return BC_NUM_NEG(cmp, neg);

        for (max_num -= diff, i = diff - 1; i < diff; --i) {
                if (max_num[i]) return BC_NUM_NEG(1, neg);
        }

        return 0;
}

static void bc_num_truncate(BcNum *n, size_t places)
{
        if (places == 0) return;

        n->rdx -= places;

        if (n->len != 0) {
                n->len -= places;
                memmove(n->num, n->num + places, n->len * sizeof(BcDig));
        }
}

static void bc_num_extend(BcNum *n, size_t places)
{
        size_t len = n->len + places;

        if (places != 0) {
                if (n->cap < len) bc_num_expand(n, len);

                memmove(n->num + places, n->num, sizeof(BcDig) * n->len);
                memset(n->num, 0, sizeof(BcDig) * places);

                n->len += places;
                n->rdx += places;
        }
}

static void bc_num_clean(BcNum *n)
{
        while (n->len > 0 && n->num[n->len - 1] == 0) --n->len;
        if (n->len == 0)
                n->neg = false;
        else if (n->len < n->rdx)
                n->len = n->rdx;
}

static void bc_num_retireMul(BcNum *n, size_t scale, bool neg1, bool neg2)
{
        if (n->rdx < scale)
                bc_num_extend(n, scale - n->rdx);
        else
                bc_num_truncate(n, n->rdx - scale);

        bc_num_clean(n);
        if (n->len != 0) n->neg = !neg1 != !neg2;
}

static void bc_num_split(BcNum *restrict n, size_t idx, BcNum *restrict a,
                         BcNum *restrict b)
{
        if (idx < n->len) {
                b->len = n->len - idx;
                a->len = idx;
                a->rdx = b->rdx = 0;

                memcpy(b->num, n->num + idx, b->len * sizeof(BcDig));
                memcpy(a->num, n->num, idx * sizeof(BcDig));
        } else {
                bc_num_zero(b);
                bc_num_copy(a, n);
        }

        bc_num_clean(a);
        bc_num_clean(b);
}

static BC_STATUS zbc_num_shift(BcNum *n, size_t places)
{
        if (places == 0 || n->len == 0) RETURN_STATUS(BC_STATUS_SUCCESS);

        // This check makes sense only if size_t is (much) larger than BC_MAX_NUM.
        if (SIZE_MAX > (BC_MAX_NUM | 0xff)) {
                if (places + n->len > BC_MAX_NUM)
                        RETURN_STATUS(bc_error("number too long: must be [1,"BC_MAX_NUM_STR"]"));
        }

        if (n->rdx >= places)
                n->rdx -= places;
        else {
                bc_num_extend(n, places - n->rdx);
                n->rdx = 0;
        }

        bc_num_clean(n);

        RETURN_STATUS(BC_STATUS_SUCCESS);
}
#define zbc_num_shift(...) (zbc_num_shift(__VA_ARGS__) COMMA_SUCCESS)

typedef BC_STATUS (*BcNumBinaryOp)(BcNum *, BcNum *, BcNum *, size_t) FAST_FUNC;

static BC_STATUS zbc_num_binary(BcNum *a, BcNum *b, BcNum *c, size_t scale,
                              BcNumBinaryOp op, size_t req)
{
        BcStatus s;
        BcNum num2, *ptr_a, *ptr_b;
        bool init = false;

        if (c == a) {
                ptr_a = &num2;
                memcpy(ptr_a, c, sizeof(BcNum));
                init = true;
        } else
                ptr_a = a;

        if (c == b) {
                ptr_b = &num2;
                if (c != a) {
                        memcpy(ptr_b, c, sizeof(BcNum));
                        init = true;
                }
        } else
                ptr_b = b;

        if (init)
                bc_num_init(c, req);
        else
                bc_num_expand(c, req);

        s = BC_STATUS_SUCCESS;
        IF_ERROR_RETURN_POSSIBLE(s =) op(ptr_a, ptr_b, c, scale);

        if (init) bc_num_free(&num2);

        RETURN_STATUS(s);
}
#define zbc_num_binary(...) (zbc_num_binary(__VA_ARGS__) COMMA_SUCCESS)

static FAST_FUNC BC_STATUS zbc_num_a(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale);
static FAST_FUNC BC_STATUS zbc_num_s(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale);
static FAST_FUNC BC_STATUS zbc_num_p(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale);
static FAST_FUNC BC_STATUS zbc_num_m(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale);
static FAST_FUNC BC_STATUS zbc_num_d(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale);
static FAST_FUNC BC_STATUS zbc_num_rem(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale);

static FAST_FUNC BC_STATUS zbc_num_add(BcNum *a, BcNum *b, BcNum *c, size_t scale)
{
        BcNumBinaryOp op = (!a->neg == !b->neg) ? zbc_num_a : zbc_num_s;
        (void) scale;
        RETURN_STATUS(zbc_num_binary(a, b, c, false, op, BC_NUM_AREQ(a, b)));
}

static FAST_FUNC BC_STATUS zbc_num_sub(BcNum *a, BcNum *b, BcNum *c, size_t scale)
{
        BcNumBinaryOp op = (!a->neg == !b->neg) ? zbc_num_s : zbc_num_a;
        (void) scale;
        RETURN_STATUS(zbc_num_binary(a, b, c, true, op, BC_NUM_AREQ(a, b)));
}

static FAST_FUNC BC_STATUS zbc_num_mul(BcNum *a, BcNum *b, BcNum *c, size_t scale)
{
        size_t req = BC_NUM_MREQ(a, b, scale);
        RETURN_STATUS(zbc_num_binary(a, b, c, scale, zbc_num_m, req));
}

static FAST_FUNC BC_STATUS zbc_num_div(BcNum *a, BcNum *b, BcNum *c, size_t scale)
{
        size_t req = BC_NUM_MREQ(a, b, scale);
        RETURN_STATUS(zbc_num_binary(a, b, c, scale, zbc_num_d, req));
}

static FAST_FUNC BC_STATUS zbc_num_mod(BcNum *a, BcNum *b, BcNum *c, size_t scale)
{
        size_t req = BC_NUM_MREQ(a, b, scale);
        RETURN_STATUS(zbc_num_binary(a, b, c, scale, zbc_num_rem, req));
}

static FAST_FUNC BC_STATUS zbc_num_pow(BcNum *a, BcNum *b, BcNum *c, size_t scale)
{
        RETURN_STATUS(zbc_num_binary(a, b, c, scale, zbc_num_p, a->len * b->len + 1));
}

static const BcNumBinaryOp zxc_program_ops[] = {
        zbc_num_pow, zbc_num_mul, zbc_num_div, zbc_num_mod, zbc_num_add, zbc_num_sub,
};
#define zbc_num_add(...) (zbc_num_add(__VA_ARGS__) COMMA_SUCCESS)
#define zbc_num_sub(...) (zbc_num_sub(__VA_ARGS__) COMMA_SUCCESS)
#define zbc_num_mul(...) (zbc_num_mul(__VA_ARGS__) COMMA_SUCCESS)
#define zbc_num_div(...) (zbc_num_div(__VA_ARGS__) COMMA_SUCCESS)
#define zbc_num_mod(...) (zbc_num_mod(__VA_ARGS__) COMMA_SUCCESS)
#define zbc_num_pow(...) (zbc_num_pow(__VA_ARGS__) COMMA_SUCCESS)

static BC_STATUS zbc_num_inv(BcNum *a, BcNum *b, size_t scale)
{
        BcNum one;
        BcDig num[2];

        one.cap = 2;
        one.num = num;
        bc_num_one(&one);

        RETURN_STATUS(zbc_num_div(&one, a, b, scale));
}
#define zbc_num_inv(...) (zbc_num_inv(__VA_ARGS__) COMMA_SUCCESS)

static FAST_FUNC BC_STATUS zbc_num_a(BcNum *a, BcNum *b, BcNum *restrict c, size_t sub)
{
        BcDig *ptr, *ptr_a, *ptr_b, *ptr_c;
        size_t i, max, min_rdx, min_int, diff, a_int, b_int;
        unsigned carry;

        // Because this function doesn't need to use scale (per the bc spec),
        // I am hijacking it to say whether it's doing an add or a subtract.

        if (a->len == 0) {
                bc_num_copy(c, b);
                if (sub && c->len) c->neg = !c->neg;
                RETURN_STATUS(BC_STATUS_SUCCESS);
        }
        if (b->len == 0) {
                bc_num_copy(c, a);
                RETURN_STATUS(BC_STATUS_SUCCESS);
        }

        c->neg = a->neg;
        c->rdx = BC_MAX(a->rdx, b->rdx);
        min_rdx = BC_MIN(a->rdx, b->rdx);
        c->len = 0;

        if (a->rdx > b->rdx) {
                diff = a->rdx - b->rdx;
                ptr = a->num;
                ptr_a = a->num + diff;
                ptr_b = b->num;
        } else {
                diff = b->rdx - a->rdx;
                ptr = b->num;
                ptr_a = a->num;
                ptr_b = b->num + diff;
        }

        ptr_c = c->num;
        for (i = 0; i < diff; ++i, ++c->len)
                ptr_c[i] = ptr[i];

        ptr_c += diff;
        a_int = BC_NUM_INT(a);
        b_int = BC_NUM_INT(b);

        if (a_int > b_int) {
                min_int = b_int;
                max = a_int;
                ptr = ptr_a;
        } else {
                min_int = a_int;
                max = b_int;
                ptr = ptr_b;
        }

        carry = 0;
        for (i = 0; i < min_rdx + min_int; ++i) {
                unsigned in = (unsigned)ptr_a[i] + (unsigned)ptr_b[i] + carry;
                carry = in / 10;
                ptr_c[i] = (BcDig)(in % 10);
        }
        for (; i < max + min_rdx; ++i) {
                unsigned in = (unsigned)ptr[i] + carry;
                carry = in / 10;
                ptr_c[i] = (BcDig)(in % 10);
        }
        c->len += i;

        if (carry != 0) c->num[c->len++] = (BcDig) carry;

        RETURN_STATUS(BC_STATUS_SUCCESS); // can't make void, see zbc_num_binary()
}

static FAST_FUNC BC_STATUS zbc_num_s(BcNum *a, BcNum *b, BcNum *restrict c, size_t sub)
{
        ssize_t cmp;
        BcNum *minuend, *subtrahend;
        size_t start;
        bool aneg, bneg, neg;

        // Because this function doesn't need to use scale (per the bc spec),
        // I am hijacking it to say whether it's doing an add or a subtract.

        if (a->len == 0) {
                bc_num_copy(c, b);
                if (sub && c->len) c->neg = !c->neg;
                RETURN_STATUS(BC_STATUS_SUCCESS);
        }
        if (b->len == 0) {
                bc_num_copy(c, a);
                RETURN_STATUS(BC_STATUS_SUCCESS);
        }

        aneg = a->neg;
        bneg = b->neg;
        a->neg = b->neg = false;

        cmp = bc_num_cmp(a, b);

        a->neg = aneg;
        b->neg = bneg;

        if (cmp == 0) {
                bc_num_setToZero(c, BC_MAX(a->rdx, b->rdx));
                RETURN_STATUS(BC_STATUS_SUCCESS);
        }
        if (cmp > 0) {
                neg = a->neg;
                minuend = a;
                subtrahend = b;
        } else {
                neg = b->neg;
                if (sub) neg = !neg;
                minuend = b;
                subtrahend = a;
        }

        bc_num_copy(c, minuend);
        c->neg = neg;

        if (c->rdx < subtrahend->rdx) {
                bc_num_extend(c, subtrahend->rdx - c->rdx);
                start = 0;
        } else
                start = c->rdx - subtrahend->rdx;

        bc_num_subArrays(c->num + start, subtrahend->num, subtrahend->len);

        bc_num_clean(c);

        RETURN_STATUS(BC_STATUS_SUCCESS); // can't make void, see zbc_num_binary()
}

static FAST_FUNC BC_STATUS zbc_num_k(BcNum *restrict a, BcNum *restrict b,
                         BcNum *restrict c)
#define zbc_num_k(...) (zbc_num_k(__VA_ARGS__) COMMA_SUCCESS)
{
        BcStatus s;
        size_t max = BC_MAX(a->len, b->len), max2 = (max + 1) / 2;
        BcNum l1, h1, l2, h2, m2, m1, z0, z1, z2, temp;
        bool aone;

        if (a->len == 0 || b->len == 0) {
                bc_num_zero(c);
                RETURN_STATUS(BC_STATUS_SUCCESS);
        }
        aone = BC_NUM_ONE(a);
        if (aone || BC_NUM_ONE(b)) {
                bc_num_copy(c, aone ? b : a);
                RETURN_STATUS(BC_STATUS_SUCCESS);
        }

        if (a->len + b->len < BC_NUM_KARATSUBA_LEN
         || a->len < BC_NUM_KARATSUBA_LEN
         || b->len < BC_NUM_KARATSUBA_LEN
        ) {
                size_t i, j, len;

                bc_num_expand(c, a->len + b->len + 1);

                memset(c->num, 0, sizeof(BcDig) * c->cap);
                c->len = len = 0;

                for (i = 0; i < b->len; ++i) {
                        unsigned carry = 0;
                        for (j = 0; j < a->len; ++j) {
                                unsigned in = c->num[i + j];
                                in += (unsigned)a->num[j] * (unsigned)b->num[i] + carry;
                                // note: compilers prefer _unsigned_ div/const
                                carry = in / 10;
                                c->num[i + j] = (BcDig)(in % 10);
                        }

                        c->num[i + j] += (BcDig) carry;
                        len = BC_MAX(len, i + j + !!carry);

#if ENABLE_FEATURE_BC_INTERACTIVE
                        // a=2^1000000
                        // a*a <- without check below, this will not be interruptible
                        if (G_interrupt) return BC_STATUS_FAILURE;
#endif
                }

                c->len = len;

                RETURN_STATUS(BC_STATUS_SUCCESS);
        }

        bc_num_init(&l1, max);
        bc_num_init(&h1, max);
        bc_num_init(&l2, max);
        bc_num_init(&h2, max);
        bc_num_init(&m1, max);
        bc_num_init(&m2, max);
        bc_num_init(&z0, max);
        bc_num_init(&z1, max);
        bc_num_init(&z2, max);
        bc_num_init(&temp, max + max);

        bc_num_split(a, max2, &l1, &h1);
        bc_num_split(b, max2, &l2, &h2);

        s = zbc_num_add(&h1, &l1, &m1, 0);
        if (s) goto err;
        s = zbc_num_add(&h2, &l2, &m2, 0);
        if (s) goto err;

        s = zbc_num_k(&h1, &h2, &z0);
        if (s) goto err;
        s = zbc_num_k(&m1, &m2, &z1);
        if (s) goto err;
        s = zbc_num_k(&l1, &l2, &z2);
        if (s) goto err;

        s = zbc_num_sub(&z1, &z0, &temp, 0);
        if (s) goto err;
        s = zbc_num_sub(&temp, &z2, &z1, 0);
        if (s) goto err;

        s = zbc_num_shift(&z0, max2 * 2);
        if (s) goto err;
        s = zbc_num_shift(&z1, max2);
        if (s) goto err;
        s = zbc_num_add(&z0, &z1, &temp, 0);
        if (s) goto err;
        s = zbc_num_add(&temp, &z2, c, 0);
 err:
        bc_num_free(&temp);
        bc_num_free(&z2);
        bc_num_free(&z1);
        bc_num_free(&z0);
        bc_num_free(&m2);
        bc_num_free(&m1);
        bc_num_free(&h2);
        bc_num_free(&l2);
        bc_num_free(&h1);
        bc_num_free(&l1);
        RETURN_STATUS(s);
}

static FAST_FUNC BC_STATUS zbc_num_m(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale)
{
        BcStatus s;
        BcNum cpa, cpb;
        size_t maxrdx = BC_MAX(a->rdx, b->rdx);

        scale = BC_MAX(scale, a->rdx);
        scale = BC_MAX(scale, b->rdx);
        scale = BC_MIN(a->rdx + b->rdx, scale);
        maxrdx = BC_MAX(maxrdx, scale);

        bc_num_init(&cpa, a->len);
        bc_num_init(&cpb, b->len);

        bc_num_copy(&cpa, a);
        bc_num_copy(&cpb, b);
        cpa.neg = cpb.neg = false;

        s = zbc_num_shift(&cpa, maxrdx);
        if (s) goto err;
        s = zbc_num_shift(&cpb, maxrdx);
        if (s) goto err;
        s = zbc_num_k(&cpa, &cpb, c);
        if (s) goto err;

        maxrdx += scale;
        bc_num_expand(c, c->len + maxrdx);

        if (c->len < maxrdx) {
                memset(c->num + c->len, 0, (c->cap - c->len) * sizeof(BcDig));
                c->len += maxrdx;
        }

        c->rdx = maxrdx;
        bc_num_retireMul(c, scale, a->neg, b->neg);
 err:
        bc_num_free(&cpb);
        bc_num_free(&cpa);
        RETURN_STATUS(s);
}
#define zbc_num_m(...) (zbc_num_m(__VA_ARGS__) COMMA_SUCCESS)

static FAST_FUNC BC_STATUS zbc_num_d(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale)
{
        BcStatus s;
        size_t len, end, i;
        BcNum cp;

        if (b->len == 0)
                RETURN_STATUS(bc_error("divide by zero"));
        if (a->len == 0) {
                bc_num_setToZero(c, scale);
                RETURN_STATUS(BC_STATUS_SUCCESS);
        }
        if (BC_NUM_ONE(b)) {
                bc_num_copy(c, a);
                bc_num_retireMul(c, scale, a->neg, b->neg);
                RETURN_STATUS(BC_STATUS_SUCCESS);
        }

        bc_num_init(&cp, BC_NUM_MREQ(a, b, scale));
        bc_num_copy(&cp, a);
        len = b->len;

        if (len > cp.len) {
                bc_num_expand(&cp, len + 2);
                bc_num_extend(&cp, len - cp.len);
        }

        if (b->rdx > cp.rdx) bc_num_extend(&cp, b->rdx - cp.rdx);
        cp.rdx -= b->rdx;
        if (scale > cp.rdx) bc_num_extend(&cp, scale - cp.rdx);

        if (b->rdx == b->len) {
                for (;;) {
                        if (len == 0) break;
                        len--;
                        if (b->num[len] != 0)
                                break;
                }
                len++;
        }

        if (cp.cap == cp.len) bc_num_expand(&cp, cp.len + 1);

        // We want an extra zero in front to make things simpler.
        cp.num[cp.len++] = 0;
        end = cp.len - len;

        bc_num_expand(c, cp.len);

        bc_num_zero(c);
        memset(c->num + end, 0, (c->cap - end) * sizeof(BcDig));
        c->rdx = cp.rdx;
        c->len = cp.len;

        s = BC_STATUS_SUCCESS;
        for (i = end - 1; i < end; --i) {
                BcDig *n, q;
                n = cp.num + i;
                for (q = 0; n[len] != 0 || bc_num_compare(n, b->num, len) >= 0; ++q)
                        bc_num_subArrays(n, b->num, len);
                c->num[i] = q;
#if ENABLE_FEATURE_BC_INTERACTIVE
                // a=2^100000
                // scale=40000
                // 1/a <- without check below, this will not be interruptible
                if (G_interrupt) {
                        s = BC_STATUS_FAILURE;
                        break;
                }
#endif
        }

        bc_num_retireMul(c, scale, a->neg, b->neg);
        bc_num_free(&cp);

        RETURN_STATUS(s);
}
#define zbc_num_d(...) (zbc_num_d(__VA_ARGS__) COMMA_SUCCESS)

static FAST_FUNC BC_STATUS zbc_num_r(BcNum *a, BcNum *b, BcNum *restrict c,
                         BcNum *restrict d, size_t scale, size_t ts)
{
        BcStatus s;
        BcNum temp;
        bool neg;

        if (b->len == 0)
                RETURN_STATUS(bc_error("divide by zero"));

        if (a->len == 0) {
                bc_num_setToZero(d, ts);
                RETURN_STATUS(BC_STATUS_SUCCESS);
        }

        bc_num_init(&temp, d->cap);
        s = zbc_num_d(a, b, c, scale);
        if (s) goto err;

        if (scale != 0) scale = ts;

        s = zbc_num_m(c, b, &temp, scale);
        if (s) goto err;
        s = zbc_num_sub(a, &temp, d, scale);
        if (s) goto err;

        if (ts > d->rdx && d->len) bc_num_extend(d, ts - d->rdx);

        neg = d->neg;
        bc_num_retireMul(d, ts, a->neg, b->neg);
        d->neg = neg;
 err:
        bc_num_free(&temp);
        RETURN_STATUS(s);
}
#define zbc_num_r(...) (zbc_num_r(__VA_ARGS__) COMMA_SUCCESS)

static FAST_FUNC BC_STATUS zbc_num_rem(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale)
{
        BcStatus s;
        BcNum c1;
        size_t ts = BC_MAX(scale + b->rdx, a->rdx), len = BC_NUM_MREQ(a, b, ts);

        bc_num_init(&c1, len);
        s = zbc_num_r(a, b, &c1, c, scale, ts);
        bc_num_free(&c1);

        RETURN_STATUS(s);
}
#define zbc_num_rem(...) (zbc_num_rem(__VA_ARGS__) COMMA_SUCCESS)

static FAST_FUNC BC_STATUS zbc_num_p(BcNum *a, BcNum *b, BcNum *restrict c, size_t scale)
{
        BcStatus s = BC_STATUS_SUCCESS;
        BcNum copy;
        unsigned long pow;
        size_t i, powrdx, resrdx;
        bool neg;

        // GNU bc does not allow 2^2.0 - we do
        for (i = 0; i < b->rdx; i++)
                if (b->num[i] != 0)
                        RETURN_STATUS(bc_error("not an integer"));

        if (b->len == 0) {
                bc_num_one(c);
                RETURN_STATUS(BC_STATUS_SUCCESS);
        }
        if (a->len == 0) {
                bc_num_setToZero(c, scale);
                RETURN_STATUS(BC_STATUS_SUCCESS);
        }
        if (BC_NUM_ONE(b)) {
                if (!b->neg)
                        bc_num_copy(c, a);
                else
                        s = zbc_num_inv(a, c, scale);
                RETURN_STATUS(s);
        }

        neg = b->neg;
        s = zbc_num_ulong_abs(b, &pow);
        if (s) RETURN_STATUS(s);
        // b is not used beyond this point

        bc_num_init(&copy, a->len);
        bc_num_copy(&copy, a);

        if (!neg) {
                if (a->rdx > scale)
                        scale = a->rdx;
                if (a->rdx * pow < scale)
                        scale = a->rdx * pow;
        }


        for (powrdx = a->rdx; !(pow & 1); pow >>= 1) {
                powrdx <<= 1;
                s = zbc_num_mul(&copy, &copy, &copy, powrdx);
                if (s) goto err;
                // Not needed: zbc_num_mul() has a check for ^C:
                //if (G_interrupt) {
                //      s = BC_STATUS_FAILURE;
                //      goto err;
                //}
        }

        bc_num_copy(c, &copy);

        for (resrdx = powrdx, pow >>= 1; pow != 0; pow >>= 1) {
                powrdx <<= 1;
                s = zbc_num_mul(&copy, &copy, &copy, powrdx);
                if (s) goto err;

                if (pow & 1) {
                        resrdx += powrdx;
                        s = zbc_num_mul(c, &copy, c, resrdx);
                        if (s) goto err;
                }
                // Not needed: zbc_num_mul() has a check for ^C:
                //if (G_interrupt) {
                //      s = BC_STATUS_FAILURE;
                //      goto err;
                //}
        }

        if (neg) {
                s = zbc_num_inv(c, c, scale);
                if (s) goto err;
        }

        if (c->rdx > scale) bc_num_truncate(c, c->rdx - scale);

        // We can't use bc_num_clean() here.
        for (i = 0; i < c->len; ++i)
                if (c->num[i] != 0)
                        goto skip;
        bc_num_setToZero(c, scale);
 skip:

 err:
        bc_num_free(&copy);
        RETURN_STATUS(s);
}
#define zbc_num_p(...) (zbc_num_p(__VA_ARGS__) COMMA_SUCCESS)

static BC_STATUS zbc_num_sqrt(BcNum *a, BcNum *restrict b, size_t scale)
{
        BcStatus s;
        BcNum num1, num2, half, f, fprime, *x0, *x1, *temp;
        BcDig half_digs[1];
        size_t pow, len, digs, digs1, resrdx, req, times = 0;
        ssize_t cmp = 1, cmp1 = SSIZE_MAX, cmp2 = SSIZE_MAX;

        req = BC_MAX(scale, a->rdx) + ((BC_NUM_INT(a) + 1) >> 1) + 1;
        bc_num_expand(b, req);

        if (a->len == 0) {
                bc_num_setToZero(b, scale);
                RETURN_STATUS(BC_STATUS_SUCCESS);
        }
        if (a->neg) {
                RETURN_STATUS(bc_error("negative number"));
        }
        if (BC_NUM_ONE(a)) {
                bc_num_one(b);
                bc_num_extend(b, scale);
                RETURN_STATUS(BC_STATUS_SUCCESS);
        }

        scale = BC_MAX(scale, a->rdx) + 1;
        len = a->len + scale;

        bc_num_init(&num1, len);
        bc_num_init(&num2, len);

        half.cap = ARRAY_SIZE(half_digs);
        half.num = half_digs;
        bc_num_one(&half);
        half_digs[0] = 5;
        half.rdx = 1;

        bc_num_init(&f, len);
        bc_num_init(&fprime, len);

        x0 = &num1;
        x1 = &num2;

        bc_num_one(x0);
        pow = BC_NUM_INT(a);

        if (pow) {
                if (pow & 1)
                        x0->num[0] = 2;
                else
                        x0->num[0] = 6;

                pow -= 2 - (pow & 1);

                bc_num_extend(x0, pow);

                // Make sure to move the radix back.
                x0->rdx -= pow;
        }

        x0->rdx = digs = digs1 = 0;
        resrdx = scale + 2;
        len = BC_NUM_INT(x0) + resrdx - 1;

        while (cmp != 0 || digs < len) {
                s = zbc_num_div(a, x0, &f, resrdx);
                if (s) goto err;
                s = zbc_num_add(x0, &f, &fprime, resrdx);
                if (s) goto err;
                s = zbc_num_mul(&fprime, &half, x1, resrdx);
                if (s) goto err;

                cmp = bc_num_cmp(x1, x0);
                digs = x1->len - (unsigned long long) llabs(cmp);

                if (cmp == cmp2 && digs == digs1)
                        times += 1;
                else
                        times = 0;

                resrdx += times > 4;

                cmp2 = cmp1;
                cmp1 = cmp;
                digs1 = digs;

                temp = x0;
                x0 = x1;
                x1 = temp;
        }

        bc_num_copy(b, x0);
        scale -= 1;
        if (b->rdx > scale) bc_num_truncate(b, b->rdx - scale);
 err:
        bc_num_free(&fprime);
        bc_num_free(&f);
        bc_num_free(&num2);
        bc_num_free(&num1);
        RETURN_STATUS(s);
}
#define zbc_num_sqrt(...) (zbc_num_sqrt(__VA_ARGS__) COMMA_SUCCESS)

static BC_STATUS zbc_num_divmod(BcNum *a, BcNum *b, BcNum *c, BcNum *d,
                              size_t scale)
{
        BcStatus s;
        BcNum num2, *ptr_a;
        bool init = false;
        size_t ts = BC_MAX(scale + b->rdx, a->rdx), len = BC_NUM_MREQ(a, b, ts);

        if (c == a) {
                memcpy(&num2, c, sizeof(BcNum));
                ptr_a = &num2;
                bc_num_init(c, len);
                init = true;
        } else {
                ptr_a = a;
                bc_num_expand(c, len);
        }

        s = zbc_num_r(ptr_a, b, c, d, scale, ts);

        if (init) bc_num_free(&num2);

        RETURN_STATUS(s);
}
#define zbc_num_divmod(...) (zbc_num_divmod(__VA_ARGS__) COMMA_SUCCESS)

#if ENABLE_DC
static BC_STATUS zdc_num_modexp(BcNum *a, BcNum *b, BcNum *c, BcNum *restrict d)
{
        BcStatus s;
        BcNum base, exp, two, temp;
        BcDig two_digs[1];

        if (c->len == 0)
                RETURN_STATUS(bc_error("divide by zero"));
        if (a->rdx || b->rdx || c->rdx)
                RETURN_STATUS(bc_error("not an integer"));
        if (b->neg)
                RETURN_STATUS(bc_error("negative number"));

        bc_num_expand(d, c->len);
        bc_num_init(&base, c->len);
        bc_num_init(&exp, b->len);
        bc_num_init(&temp, b->len);

        two.cap = ARRAY_SIZE(two_digs);
        two.num = two_digs;
        bc_num_one(&two);
        two_digs[0] = 2;

        bc_num_one(d);

        s = zbc_num_rem(a, c, &base, 0);
        if (s) goto err;
        bc_num_copy(&exp, b);

        while (exp.len != 0) {
                s = zbc_num_divmod(&exp, &two, &exp, &temp, 0);
                if (s) goto err;

                if (BC_NUM_ONE(&temp)) {
                        s = zbc_num_mul(d, &base, &temp, 0);
                        if (s) goto err;
                        s = zbc_num_rem(&temp, c, d, 0);
                        if (s) goto err;
                }

                s = zbc_num_mul(&base, &base, &temp, 0);
                if (s) goto err;
                s = zbc_num_rem(&temp, c, &base, 0);
                if (s) goto err;
        }
 err:
        bc_num_free(&temp);
        bc_num_free(&exp);
        bc_num_free(&base);
        RETURN_STATUS(s);
}
#define zdc_num_modexp(...) (zdc_num_modexp(__VA_ARGS__) COMMA_SUCCESS)
#endif // ENABLE_DC

static FAST_FUNC void bc_string_free(void *string)
{
        free(*(char**)string);
}

static void bc_func_init(BcFunc *f)
{
        bc_char_vec_init(&f->code);
        IF_BC(bc_vec_init(&f->labels, sizeof(size_t), NULL);)
        IF_BC(bc_vec_init(&f->autos, sizeof(BcId), bc_id_free);)
        IF_BC(bc_vec_init(&f->strs, sizeof(char *), bc_string_free);)
        IF_BC(bc_vec_init(&f->consts, sizeof(char *), bc_string_free);)
        IF_BC(f->nparams = 0;)
}

static FAST_FUNC void bc_func_free(void *func)
{
        BcFunc *f = (BcFunc *) func;
        bc_vec_free(&f->code);
        IF_BC(bc_vec_free(&f->labels);)
        IF_BC(bc_vec_free(&f->autos);)
        IF_BC(bc_vec_free(&f->strs);)
        IF_BC(bc_vec_free(&f->consts);)
}

static void bc_array_expand(BcVec *a, size_t len);

static void bc_array_init(BcVec *a, bool nums)
{
        if (nums)
                bc_vec_init(a, sizeof(BcNum), bc_num_free);
        else
                bc_vec_init(a, sizeof(BcVec), bc_vec_free);
        bc_array_expand(a, 1);
}

static void bc_array_expand(BcVec *a, size_t len)
{
        if (a->dtor == bc_num_free
         // && a->size == sizeof(BcNum) - always true
        ) {
                BcNum n;
                while (len > a->len) {
                        bc_num_init_DEF_SIZE(&n);
                        bc_vec_push(a, &n);
                }
        } else {
                BcVec v;
                while (len > a->len) {
                        bc_array_init(&v, true);
                        bc_vec_push(a, &v);
                }
        }
}

static void bc_array_copy(BcVec *d, const BcVec *s)
{
        BcNum *dnum, *snum;
        size_t i;

        bc_vec_pop_all(d);
        bc_vec_expand(d, s->cap);
        d->len = s->len;

        dnum = (void*)d->v;
        snum = (void*)s->v;
        for (i = 0; i < s->len; i++, dnum++, snum++) {
                bc_num_init(dnum, snum->len);
                bc_num_copy(dnum, snum);
        }
}

#if ENABLE_DC
static void dc_result_copy(BcResult *d, BcResult *src)
{
        d->t = src->t;

        switch (d->t) {
                case XC_RESULT_TEMP:
                case XC_RESULT_IBASE:
                case XC_RESULT_SCALE:
                case XC_RESULT_OBASE:
                        bc_num_init(&d->d.n, src->d.n.len);
                        bc_num_copy(&d->d.n, &src->d.n);
                        break;
                case XC_RESULT_VAR:
                case XC_RESULT_ARRAY:
                case XC_RESULT_ARRAY_ELEM:
                        d->d.id.name = xstrdup(src->d.id.name);
                        break;
                case XC_RESULT_CONSTANT:
                case XC_RESULT_STR:
                        memcpy(&d->d.n, &src->d.n, sizeof(BcNum));
                        break;
                default: // placate compiler
                        // BC_RESULT_VOID, BC_RESULT_LAST, BC_RESULT_ONE - do not happen
                        break;
        }
}
#endif // ENABLE_DC

static FAST_FUNC void bc_result_free(void *result)
{
        BcResult *r = (BcResult *) result;

        switch (r->t) {
                case XC_RESULT_TEMP:
                IF_BC(case BC_RESULT_VOID:)
                case XC_RESULT_IBASE:
                case XC_RESULT_SCALE:
                case XC_RESULT_OBASE:
                        bc_num_free(&r->d.n);
                        break;
                case XC_RESULT_VAR:
                case XC_RESULT_ARRAY:
                case XC_RESULT_ARRAY_ELEM:
                        free(r->d.id.name);
                        break;
                default:
                        // Do nothing.
                        break;
        }
}

static int bad_input_byte(char c)
{
        if ((c < ' ' && c != '\t' && c != '\r' && c != '\n') // also allow '\v' '\f'?
         || c > 0x7e
        ) {
                bc_error_fmt("illegal character 0x%02x", c);
                return 1;
        }
        return 0;
}

static void xc_read_line(BcVec *vec, FILE *fp)
{
 again:
        bc_vec_pop_all(vec);
        fflush_and_check();

#if ENABLE_FEATURE_BC_INTERACTIVE
        if (G_interrupt) { // ^C was pressed
 intr:
                if (fp != stdin) {
                        // ^C while running a script (bc SCRIPT): die.
                        // We do not return to interactive prompt:
                        // user might be running us from a shell,
                        // and SCRIPT might be intended to terminate
                        // (e.g. contain a "halt" stmt).
                        // ^C dropping user into a bc prompt instead of
                        // the shell would be unexpected.
                        xfunc_die();
                }
                // ^C while interactive input
                G_interrupt = 0;
                // GNU bc says "interrupted execution."
                // GNU dc says "Interrupt!"
                fputs("\ninterrupted execution\n", stderr);
        }

# if ENABLE_FEATURE_EDITING
        if (G_ttyin && fp == stdin) {
                int n, i;
#  define line_buf bb_common_bufsiz1
                n = read_line_input(G.line_input_state, "", line_buf, COMMON_BUFSIZE);
                if (n <= 0) { // read errors or EOF, or ^D, or ^C
                        if (n == 0) // ^C
                                goto intr;
                        bc_vec_pushZeroByte(vec); // ^D or EOF (or error)
                        return;
                }
                i = 0;
                for (;;) {
                        char c = line_buf[i++];
                        if (c == '\0') break;
                        if (bad_input_byte(c)) goto again;
                }
                bc_vec_string(vec, n, line_buf);
#  undef line_buf
        } else
# endif
#endif
        {
                int c;
                bool bad_chars = 0;

                do {
 get_char:
#if ENABLE_FEATURE_BC_INTERACTIVE
                        if (G_interrupt) {
                                // ^C was pressed: ignore entire line, get another one
                                goto again;
                        }
#endif
                        c = fgetc(fp);
                        if (c == '\0')
                                goto get_char;
                        if (c == EOF) {
                                if (ferror(fp))
                                        bb_perror_msg_and_die("input error");
                                // Note: EOF does not append '\n'
                                break;
                        }
                        bad_chars |= bad_input_byte(c);
                        bc_vec_pushByte(vec, (char)c);
                } while (c != '\n');

                if (bad_chars) {
                        // Bad chars on this line
                        if (!G.prs.lex_filename) { // stdin
                                // ignore entire line, get another one
                                goto again;
                        }
                        bb_perror_msg_and_die("file '%s' is not text", G.prs.lex_filename);
                }
                bc_vec_pushZeroByte(vec);
        }
}

//
// Parsing routines
//

// "Input numbers may contain the characters 0-9 and A-Z.
// (Note: They must be capitals.  Lower case letters are variable names.)
// Single digit numbers always have the value of the digit regardless of
// the value of ibase. (i.e. A = 10.) For multi-digit numbers, bc changes
// all input digits greater or equal to ibase to the value of ibase-1.
// This makes the number ZZZ always be the largest 3 digit number of the
// input base."
static bool xc_num_strValid(const char *val)
{
        bool radix = false;
        for (;;) {
                BcDig c = *val++;
                if (c == '\0')
                        break;
                if (c == '.') {
                        if (radix) return false;
                        radix = true;
                        continue;
                }
                if ((c < '0' || c > '9') && (c < 'A' || c > 'Z'))
                        return false;
        }
        return true;
}

// Note: n is already "bc_num_zero()"ed,
// leading zeroes in "val" are removed
static void bc_num_parseDecimal(BcNum *n, const char *val)
{
        size_t len, i;
        const char *ptr;

        len = strlen(val);
        if (len == 0)
                return;

        bc_num_expand(n, len + 1); // +1 for e.g. "A" converting into 10

        ptr = strchr(val, '.');

        n->rdx = 0;
        if (ptr != NULL)
                n->rdx = (size_t)((val + len) - (ptr + 1));

        for (i = 0; val[i]; ++i) {
                if (val[i] != '0' && val[i] != '.') {
                        // Not entirely zero value - convert it, and exit
                        if (len == 1) {
                                unsigned c = val[0] - '0';
                                n->len = 1;
                                if (c > 9) { // A-Z => 10-36
                                        n->len = 2;
                                        c -= ('A' - '9' - 1);
                                        n->num[1] = c/10;
                                        c = c%10;
                                }
                                n->num[0] = c;
                                break;
                        }
                        i = len - 1;
                        for (;;) {
                                char c = val[i] - '0';
                                if (c > 9) // A-Z => 9
                                        c = 9;
                                n->num[n->len] = c;
                                n->len++;
 skip_dot:
                                if (i == 0) break;
                                if (val[--i] == '.') goto skip_dot;
                        }
                        break;
                }
        }
        // if for() exits without hitting if(), the value is entirely zero
}

// Note: n is already "bc_num_zero()"ed,
// leading zeroes in "val" are removed
static void bc_num_parseBase(BcNum *n, const char *val, unsigned base_t)
{
        BcStatus s;
        BcNum mult, result;
        BcNum temp;
        BcNum base;
        BcDig temp_digs[ULONG_NUM_BUFSIZE];
        BcDig base_digs[ULONG_NUM_BUFSIZE];
        size_t digits;

        bc_num_init_DEF_SIZE(&mult);

        temp.cap = ARRAY_SIZE(temp_digs);
        temp.num = temp_digs;

        base.cap = ARRAY_SIZE(base_digs);
        base.num = base_digs;
        bc_num_ulong2num(&base, base_t);
        base_t--;

        for (;;) {
                unsigned v;
                char c;

                c = *val++;
                if (c == '\0') goto int_err;
                if (c == '.') break;

                v = (unsigned)(c <= '9' ? c - '0' : c - 'A' + 10);
                if (v > base_t) v = base_t;

                s = zbc_num_mul(n, &base, &mult, 0);
                if (s) goto int_err;
                bc_num_ulong2num(&temp, v);
                s = zbc_num_add(&mult, &temp, n, 0);
                if (s) goto int_err;
        }

        bc_num_init(&result, base.len);
        //bc_num_zero(&result); - already is
        bc_num_one(&mult);

        digits = 0;
        for (;;) {
                unsigned v;
                char c;

                c = *val++;
                if (c == '\0') break;
                digits++;

                v = (unsigned)(c <= '9' ? c - '0' : c - 'A' + 10);
                if (v > base_t) v = base_t;

                s = zbc_num_mul(&result, &base, &result, 0);
                if (s) goto err;
                bc_num_ulong2num(&temp, v);
                s = zbc_num_add(&result, &temp, &result, 0);
                if (s) goto err;
                s = zbc_num_mul(&mult, &base, &mult, 0);
                if (s) goto err;
        }

        s = zbc_num_div(&result, &mult, &result, digits);
        if (s) goto err;
        s = zbc_num_add(n, &result, n, digits);
        if (s) goto err;

        if (n->len != 0) {
                if (n->rdx < digits)
                        bc_num_extend(n, digits - n->rdx);
        } else
                bc_num_zero(n);
 err:
        bc_num_free(&result);
 int_err:
        bc_num_free(&mult);
}

static BC_STATUS zxc_num_parse(BcNum *n, const char *val, unsigned base_t)
{
        size_t i;

        if (!xc_num_strValid(val))
                RETURN_STATUS(bc_error("bad number string"));

        bc_num_zero(n);
        while (*val == '0')
                val++;
        for (i = 0; ; ++i) {
                if (val[i] == '\0')
                        RETURN_STATUS(BC_STATUS_SUCCESS);
                if (val[i] != '.' && val[i] != '0')
                        break;
        }

        if (base_t == 10 || val[1] == '\0')
                // Decimal, or single-digit number
                bc_num_parseDecimal(n, val);
        else
                bc_num_parseBase(n, val, base_t);

        RETURN_STATUS(BC_STATUS_SUCCESS);
}
#define zxc_num_parse(...) (zxc_num_parse(__VA_ARGS__) COMMA_SUCCESS)

// p->lex_inbuf points to the current string to be parsed.
// if p->lex_inbuf points to '\0', it's either EOF or it points after
// last processed line's terminating '\n' (and more reading needs to be done
// to get next character).
//
// If you are in a situation where that is a possibility, call peek_inbuf().
// If necessary, it performs more reading and changes p->lex_inbuf,
// then it returns *p->lex_inbuf (which will be '\0' only if it's EOF).
// After it, just referencing *p->lex_inbuf is valid, and if it wasn't '\0',
// it's ok to do p->lex_inbuf++ once without end-of-buffer checking.
//
// eat_inbuf() is equvalent to "peek_inbuf(); if (c) p->lex_inbuf++":
// it returns current char and advances the pointer (if not EOF).
// After eat_inbuf(), referencing p->lex_inbuf[-1] and *p->lex_inbuf is valid.
//
// In many cases, you can use fast *p->lex_inbuf instead of peek_inbuf():
// unless prev char might have been '\n', *p->lex_inbuf is '\0' ONLY
// on real EOF, not end-of-buffer.
//
// bc cases to test interactively:
// 1 #comment\  - prints "1<newline>" at once (comment is not continued)
// 1 #comment/* - prints "1<newline>" at once
// 1 #comment"  - prints "1<newline>" at once
// 1\#comment   - error at once (\ is not a line continuation)
// 1 + /*"*/2   - prints "3<newline>" at once
// 1 + /*#*/2   - prints "3<newline>" at once
// "str\"       - prints "str\" at once
// "str#"       - prints "str#" at once
// "str/*"      - prints "str/*" at once
// "str#\       - waits for second line
// end"         - ...prints "str#\<newline>end"
static char peek_inbuf(void)
{
        if (*G.prs.lex_inbuf == '\0'
         && G.prs.lex_input_fp
        ) {
                xc_read_line(&G.input_buffer, G.prs.lex_input_fp);
                G.prs.lex_inbuf = G.input_buffer.v;
                if (G.input_buffer.len <= 1) // on EOF, len is 1 (NUL byte)
                        G.prs.lex_input_fp = NULL;
        }
        return *G.prs.lex_inbuf;
}
static char eat_inbuf(void)
{
        char c = peek_inbuf();
        if (c) G.prs.lex_inbuf++;
        return c;
}

static void xc_lex_lineComment(void)
{
        BcParse *p = &G.prs;
        char c;

        // Try: echo -n '#foo' | bc
        p->lex = XC_LEX_WHITESPACE;

        // Not peek_inbuf(): we depend on input being done in whole lines:
        // '\0' which isn't the EOF can only be seen after '\n'.
        while ((c = *p->lex_inbuf) != '\n' && c != '\0')
                p->lex_inbuf++;
}

static void xc_lex_whitespace(void)
{
        BcParse *p = &G.prs;

        p->lex = XC_LEX_WHITESPACE;
        for (;;) {
                // We depend here on input being done in whole lines:
                // '\0' which isn't the EOF can only be seen after '\n'.
                char c = *p->lex_inbuf;
                if (c == '\n') // this is XC_LEX_NLINE, not XC_LEX_WHITESPACE
                        break;
                if (!isspace(c))
                        break;
                p->lex_inbuf++;
        }
}

static BC_STATUS zxc_lex_number(char last)
{
        BcParse *p = &G.prs;
        bool pt;
        char last_valid_ch;

        bc_vec_pop_all(&p->lex_strnumbuf);
        bc_vec_pushByte(&p->lex_strnumbuf, last);

// bc: "Input numbers may contain the characters 0-9 and A-Z.
// (Note: They must be capitals.  Lower case letters are variable names.)
// Single digit numbers always have the value of the digit regardless of
// the value of ibase. (i.e. A = 10.) For multi-digit numbers, bc changes
// all input digits greater or equal to ibase to the value of ibase-1.
// This makes the number ZZZ always be the largest 3 digit number of the
// input base."
// dc only allows A-F, the rules about single-char and multi-char are the same.
        last_valid_ch = (IS_BC ? 'Z' : 'F');
        pt = (last == '.');
        p->lex = XC_LEX_NUMBER;
        for (;;) {
                // We depend here on input being done in whole lines:
                // '\0' which isn't the EOF can only be seen after '\n'.
                char c = *p->lex_inbuf;
 check_c:
                if (c == '\0')
                        break;
                if (c == '\\' && p->lex_inbuf[1] == '\n') {
                        p->lex_inbuf += 2;
                        p->lex_line++;
                        dbg_lex("++p->lex_line=%zd", p->lex_line);
                        c = peek_inbuf(); // force next line to be read
                        goto check_c;
                }
                if (!isdigit(c) && (c < 'A' || c > last_valid_ch)) {
                        if (c != '.') break;
                        // if '.' was already seen, stop on second one:
                        if (pt) break;
                        pt = true;
                }
                // c is one of "0-9A-Z."
                last = c;
                bc_vec_push(&p->lex_strnumbuf, p->lex_inbuf);
                p->lex_inbuf++;
        }
        if (last == '.') // remove trailing '.' if any
                bc_vec_pop(&p->lex_strnumbuf);
        bc_vec_pushZeroByte(&p->lex_strnumbuf);

        G.err_line = G.prs.lex_line;
        RETURN_STATUS(BC_STATUS_SUCCESS);
}
#define zxc_lex_number(...) (zxc_lex_number(__VA_ARGS__) COMMA_SUCCESS)

static void xc_lex_name(void)
{
        BcParse *p = &G.prs;
        size_t i;
        const char *buf;

        p->lex = XC_LEX_NAME;

        // Since names can't cross lines with \<newline>,
        // we depend on the fact that whole line is in the buffer
        i = 0;
        buf = p->lex_inbuf - 1;
        for (;;) {
                char c = buf[i];
                if ((c < 'a' || c > 'z') && !isdigit(c) && c != '_') break;
                i++;
        }

#if 0 // We do not protect against people with gigabyte-long names
        // This check makes sense only if size_t is (much) larger than BC_MAX_STRING.
        if (SIZE_MAX > (BC_MAX_STRING | 0xff)) {
                if (i > BC_MAX_STRING)
                        return bc_error("name too long: must be [1,"BC_MAX_STRING_STR"]");
        }
#endif
        bc_vec_string(&p->lex_strnumbuf, i, buf);

        // Increment the index. We minus 1 because it has already been incremented.
        p->lex_inbuf += i - 1;

        //return BC_STATUS_SUCCESS;
}

IF_BC(static BC_STATUS zbc_lex_token(void);)
IF_DC(static BC_STATUS zdc_lex_token(void);)
#define zbc_lex_token(...) (zbc_lex_token(__VA_ARGS__) COMMA_SUCCESS)
#define zdc_lex_token(...) (zdc_lex_token(__VA_ARGS__) COMMA_SUCCESS)

static BC_STATUS zxc_lex_next(void)
{
        BcParse *p = &G.prs;
        BcStatus s;

        G.err_line = p->lex_line;
        p->lex_last = p->lex;
//why?
//      if (p->lex_last == XC_LEX_EOF)
//              RETURN_STATUS(bc_error("end of file"));

        // Loop until failure or we don't have whitespace. This
        // is so the parser doesn't get inundated with whitespace.
        // Comments are also XC_LEX_WHITESPACE tokens and eaten here.
        s = BC_STATUS_SUCCESS;
        do {
                if (*p->lex_inbuf == '\0') {
                        p->lex = XC_LEX_EOF;
                        if (peek_inbuf() == '\0')
                                RETURN_STATUS(BC_STATUS_SUCCESS);
                }
                p->lex_next_at = p->lex_inbuf;
                dbg_lex("next string to parse:'%.*s'",
                        (int)(strchrnul(p->lex_next_at, '\n') - p->lex_next_at),
                        p->lex_next_at
                );
                if (IS_BC) {
                        IF_BC(s = zbc_lex_token());
                } else {
                        IF_DC(s = zdc_lex_token());
                }
        } while (!s && p->lex == XC_LEX_WHITESPACE);
        dbg_lex("p->lex from string:%d", p->lex);

        RETURN_STATUS(s);
}
#define zxc_lex_next(...) (zxc_lex_next(__VA_ARGS__) COMMA_SUCCESS)

#if ENABLE_BC
static BC_STATUS zbc_lex_skip_if_at_NLINE(void)
{