blob: c7246ea1a1610195e78de07d9e09b4e38535fcdd [file] [log] [blame]
/* 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