miscutils/bc.c

/* 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 == 4294967295U
# define BC_MAX_SCALE_STR  "4294967295"
# define BC_MAX_STRING_STR "4294967294"
#elif UINT_MAX == 18446744073709551615U
# 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_simple_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_simple_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) {
		if (neg) return - (ssize_t) a_int;
		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_simple_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;