blob: 2d9275516d3c67f1d970e7b45a11ddbbfed9bc68 [file] [log] [blame]
/* bc.c - An implementation of POSIX bc.
*
* Copyright 2018 Gavin D. Howard <yzena.tech@gmail.com>
*
* See http://pubs.opengroup.org/onlinepubs/9699919799/utilities/bc.html
USE_BC(NEWTOY(bc, "i(interactive)l(mathlib)q(quiet)s(standard)w(warn)", TOYFLAG_USR|TOYFLAG_BIN|TOYFLAG_LOCALE))
config BC
bool "bc"
default n
help
usage: bc [-ilqsw] [file ...]
bc is a command-line calculator with a Turing-complete language.
options:
-i --interactive force interactive mode
-l --mathlib use predefined math routines:
s(expr) = sine of expr in radians
c(expr) = cosine of expr in radians
a(expr) = arctangent of expr, returning radians
l(expr) = natural log of expr
e(expr) = raises e to the power of expr
j(n, x) = Bessel function of integer order n of x
-q --quiet don't print version and copyright
-s --standard error if any non-POSIX extensions are used
-w --warn warn if any non-POSIX extensions are used
*/
#define FOR_bc
#include "toys.h"
GLOBALS(
// This actually needs to be a BcVm*, but the toybox build
// system complains if I make it so. Instead, we'll just cast.
char *vm;
size_t nchars;
char *file, sig, max_ibase;
uint16_t line_len;
)
#define BC_VM ((BcVm*) TT.vm)
typedef enum BcStatus {
BC_STATUS_SUCCESS = 0,
BC_STATUS_ERROR,
BC_STATUS_EOF,
BC_STATUS_EMPTY_EXPR,
BC_STATUS_SIGNAL,
BC_STATUS_QUIT,
} BcStatus;
typedef enum BcError {
BC_ERROR_VM_ALLOC_ERR,
BC_ERROR_VM_IO_ERR,
BC_ERROR_VM_BIN_FILE,
BC_ERROR_VM_PATH_DIR,
BC_ERROR_PARSE_EOF,
BC_ERROR_PARSE_CHAR,
BC_ERROR_PARSE_STRING,
BC_ERROR_PARSE_COMMENT,
BC_ERROR_PARSE_TOKEN,
BC_ERROR_EXEC_NUM_LEN,
BC_ERROR_EXEC_NAME_LEN,
BC_ERROR_EXEC_STRING_LEN,
BC_ERROR_PARSE_EXPR,
BC_ERROR_PARSE_EMPTY_EXPR,
BC_ERROR_PARSE_PRINT,
BC_ERROR_PARSE_FUNC,
BC_ERROR_PARSE_ASSIGN,
BC_ERROR_PARSE_NO_AUTO,
BC_ERROR_PARSE_DUP_LOCAL,
BC_ERROR_PARSE_BLOCK,
BC_ERROR_PARSE_RET_VOID,
BC_ERROR_MATH_NEGATIVE,
BC_ERROR_MATH_NON_INTEGER,
BC_ERROR_MATH_OVERFLOW,
BC_ERROR_MATH_DIVIDE_BY_ZERO,
BC_ERROR_EXEC_FILE_ERR,
BC_ERROR_EXEC_ARRAY_LEN,
BC_ERROR_EXEC_IBASE,
BC_ERROR_EXEC_OBASE,
BC_ERROR_EXEC_SCALE,
BC_ERROR_EXEC_READ_EXPR,
BC_ERROR_EXEC_REC_READ,
BC_ERROR_EXEC_TYPE,
BC_ERROR_EXEC_PARAMS,
BC_ERROR_EXEC_UNDEF_FUNC,
BC_ERROR_EXEC_VOID_VAL,
BC_ERROR_POSIX_START,
BC_ERROR_POSIX_NAME_LEN = BC_ERROR_POSIX_START,
BC_ERROR_POSIX_COMMENT,
BC_ERROR_POSIX_KW,
BC_ERROR_POSIX_DOT,
BC_ERROR_POSIX_RET,
BC_ERROR_POSIX_BOOL,
BC_ERROR_POSIX_REL_POS,
BC_ERROR_POSIX_MULTIREL,
BC_ERROR_POSIX_FOR1,
BC_ERROR_POSIX_FOR2,
BC_ERROR_POSIX_FOR3,
BC_ERROR_POSIX_BRACE,
BC_ERROR_POSIX_REF,
} BcError;
#define BC_ERR_IDX_VM (0)
#define BC_ERR_IDX_PARSE (1)
#define BC_ERR_IDX_MATH (2)
#define BC_ERR_IDX_EXEC (3)
#define BC_ERR_IDX_POSIX (4)
#define BC_VEC_START_CAP (1<<5)
typedef unsigned char uchar;
typedef void (*BcVecFree)(void*);
typedef struct BcVec {
char *v;
size_t len, cap, size;
BcVecFree dtor;
} BcVec;
#define bc_vec_pop(v) (bc_vec_npop((v), 1))
#define bc_vec_top(v) (bc_vec_item_rev((v), 0))
typedef signed char BcDig;
typedef struct BcNum {
signed char *num;
unsigned long rdx, len, cap;
int neg;
} BcNum;
#define BC_NUM_DEF_SIZE (16)
// A crude, but always big enough, calculation of
// the size required for ibase and obase BcNum's.
#define BC_NUM_LONG_LOG10 ((CHAR_BIT * sizeof(unsigned long) + 1) / 2 + 1)
#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_CMP_ZERO(a) (BC_NUM_NEG((a)->len != 0, (a)->neg))
typedef BcStatus (*BcNumBinaryOp)(BcNum*, BcNum*, BcNum*, size_t);
typedef size_t (*BcNumBinaryOpReq)(BcNum*, BcNum*, size_t);
typedef void (*BcNumDigitOp)(size_t, size_t, int);
void bc_num_init(BcNum *n, size_t req);
void bc_num_expand(BcNum *n, size_t req);
void bc_num_copy(BcNum *d, BcNum *s);
void bc_num_createCopy(BcNum *d, BcNum *s);
void bc_num_createFromUlong(BcNum *n, unsigned long val);
void bc_num_free(void *num);
BcStatus bc_num_ulong(BcNum *n, unsigned long *result);
void bc_num_ulong2num(BcNum *n, unsigned long val);
BcStatus bc_num_add(BcNum *a, BcNum *b, BcNum *c, size_t scale);
BcStatus bc_num_sub(BcNum *a, BcNum *b, BcNum *c, size_t scale);
BcStatus bc_num_mul(BcNum *a, BcNum *b, BcNum *c, size_t scale);
BcStatus bc_num_div(BcNum *a, BcNum *b, BcNum *c, size_t scale);
BcStatus bc_num_mod(BcNum *a, BcNum *b, BcNum *c, size_t scale);
BcStatus bc_num_pow(BcNum *a, BcNum *b, BcNum *c, size_t scale);
BcStatus bc_num_sqrt(BcNum *a, BcNum *b, size_t scale);
BcStatus bc_num_divmod(BcNum *a, BcNum *b, BcNum *c, BcNum *d, size_t scale);
size_t bc_num_addReq(BcNum *a, BcNum *b, size_t scale);
size_t bc_num_mulReq(BcNum *a, BcNum *b, size_t scale);
size_t bc_num_powReq(BcNum *a, BcNum *b, size_t scale);
typedef enum BcInst {
BC_INST_INC_POST = 0,
BC_INST_DEC_POST,
BC_INST_INC_PRE,
BC_INST_DEC_PRE,
BC_INST_NEG,
BC_INST_BOOL_NOT,
BC_INST_POWER,
BC_INST_MULTIPLY,
BC_INST_DIVIDE,
BC_INST_MODULUS,
BC_INST_PLUS,
BC_INST_MINUS,
BC_INST_REL_EQ,
BC_INST_REL_LE,
BC_INST_REL_GE,
BC_INST_REL_NE,
BC_INST_REL_LT,
BC_INST_REL_GT,
BC_INST_BOOL_OR,
BC_INST_BOOL_AND,
BC_INST_ASSIGN_POWER,
BC_INST_ASSIGN_MULTIPLY,
BC_INST_ASSIGN_DIVIDE,
BC_INST_ASSIGN_MODULUS,
BC_INST_ASSIGN_PLUS,
BC_INST_ASSIGN_MINUS,
BC_INST_ASSIGN,
BC_INST_NUM,
BC_INST_VAR,
BC_INST_ARRAY_ELEM,
BC_INST_ARRAY,
BC_INST_LAST,
BC_INST_IBASE,
BC_INST_OBASE,
BC_INST_SCALE,
BC_INST_LENGTH,
BC_INST_SCALE_FUNC,
BC_INST_SQRT,
BC_INST_ABS,
BC_INST_READ,
BC_INST_PRINT,
BC_INST_PRINT_POP,
BC_INST_STR,
BC_INST_PRINT_STR,
BC_INST_JUMP,
BC_INST_JUMP_ZERO,
BC_INST_CALL,
BC_INST_RET,
BC_INST_RET0,
BC_INST_RET_VOID,
BC_INST_HALT,
BC_INST_POP,
BC_INST_POP_EXEC,
} BcInst;
typedef struct BcFunc {
BcVec code;
BcVec labels;
BcVec autos;
size_t nparams;
BcVec strs;
BcVec consts;
char *name;
int voidfn;
} BcFunc;
typedef enum BcResultType {
BC_RESULT_VAR,
BC_RESULT_ARRAY_ELEM,
BC_RESULT_ARRAY,
BC_RESULT_STR,
BC_RESULT_CONSTANT,
BC_RESULT_TEMP,
BC_RESULT_VOID,
BC_RESULT_ONE,
BC_RESULT_LAST,
BC_RESULT_IBASE,
BC_RESULT_OBASE,
BC_RESULT_SCALE,
} BcResultType;
typedef union BcResultData {
BcNum n;
BcVec v;
struct str_len id;
} BcResultData;
typedef struct BcResult {
BcResultType t;
BcResultData d;
} BcResult;
typedef struct BcInstPtr {
size_t func;
size_t idx;
size_t len;
} BcInstPtr;
typedef enum BcType {
BC_TYPE_VAR,
BC_TYPE_ARRAY,
} BcType;
void bc_array_expand(BcVec *a, size_t len);
int bc_id_cmp(struct str_len *e1, struct str_len *e2);
#define bc_lex_err(l, e) (bc_vm_error((e), (l)->line))
#define bc_lex_verr(l, e, ...) (bc_vm_error((e), (l)->line, __VA_ARGS__))
#define BC_LEX_NUM_CHAR(c, l, pt) \
(isdigit(c) || ((c) >= 'A' && (c) <= (l)) || ((c) == '.' && !(pt)))
// BC_LEX_NEG is not used in lexing; it is only for parsing.
typedef enum BcLexType {
BC_LEX_EOF,
BC_LEX_INVALID,
BC_LEX_OP_INC,
BC_LEX_OP_DEC,
BC_LEX_NEG,
BC_LEX_OP_BOOL_NOT,
BC_LEX_OP_POWER,
BC_LEX_OP_MULTIPLY,
BC_LEX_OP_DIVIDE,
BC_LEX_OP_MODULUS,
BC_LEX_OP_PLUS,
BC_LEX_OP_MINUS,
BC_LEX_OP_REL_EQ,
BC_LEX_OP_REL_LE,
BC_LEX_OP_REL_GE,
BC_LEX_OP_REL_NE,
BC_LEX_OP_REL_LT,
BC_LEX_OP_REL_GT,
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,
BC_LEX_NLINE,
BC_LEX_WHITESPACE,
BC_LEX_LPAREN,
BC_LEX_RPAREN,
BC_LEX_LBRACKET,
BC_LEX_COMMA,
BC_LEX_RBRACKET,
BC_LEX_LBRACE,
BC_LEX_SCOLON,
BC_LEX_RBRACE,
BC_LEX_STR,
BC_LEX_NAME,
BC_LEX_NUMBER,
BC_LEX_KEY_AUTO,
BC_LEX_KEY_BREAK,
BC_LEX_KEY_CONTINUE,
BC_LEX_KEY_DEFINE,
BC_LEX_KEY_FOR,
BC_LEX_KEY_IF,
BC_LEX_KEY_LIMITS,
BC_LEX_KEY_RETURN,
BC_LEX_KEY_WHILE,
BC_LEX_KEY_HALT,
BC_LEX_KEY_LAST,
BC_LEX_KEY_IBASE,
BC_LEX_KEY_OBASE,
BC_LEX_KEY_SCALE,
BC_LEX_KEY_LENGTH,
BC_LEX_KEY_PRINT,
BC_LEX_KEY_SQRT,
BC_LEX_KEY_ABS,
BC_LEX_KEY_QUIT,
BC_LEX_KEY_READ,
BC_LEX_KEY_ELSE,
} BcLexType;
typedef struct BcLex {
char *buf;
size_t i;
size_t line;
size_t len;
BcLexType t;
BcLexType last;
BcVec str;
} BcLex;
#define BC_PARSE_REL (1<<0)
#define BC_PARSE_PRINT (1<<1)
#define BC_PARSE_NOCALL (1<<2)
#define BC_PARSE_NOREAD (1<<3)
#define BC_PARSE_ARRAY (1<<4)
#define bc_parse_push(p, i) (bc_vec_pushByte(&(p)->func->code, i))
#define bc_parse_number(p)(bc_parse_addId((p), BC_INST_NUM))
#define bc_parse_string(p)(bc_parse_addId((p), BC_INST_STR))
#define bc_parse_err(p, e) (bc_vm_error((e), (p)->l.line))
#define bc_parse_verr(p, e, ...) (bc_vm_error((e), (p)->l.line, __VA_ARGS__))
typedef struct BcParseNext {
char len, tokens[4];
} BcParseNext;
#define BC_PARSE_NEXT_TOKENS(...) .tokens = { __VA_ARGS__ }
#define BC_PARSE_NEXT(a, ...) { .len = a, BC_PARSE_NEXT_TOKENS(__VA_ARGS__) }
struct BcProgram;
typedef struct BcParse {
BcLex l;
BcVec flags;
BcVec exits;
BcVec conds;
BcVec ops;
struct BcProgram *prog;
BcFunc *func;
size_t fidx;
int auto_part;
} BcParse;
typedef struct BcLexKeyword {
char data, name[9];
} BcLexKeyword;
#define BC_LEX_CHAR_MSB(bit) ((bit) << (CHAR_BIT - 1))
#define BC_LEX_KW_POSIX(kw) ((kw)->data & (BC_LEX_CHAR_MSB(1)))
#define BC_LEX_KW_LEN(kw) ((size_t) ((kw)->data & ~(BC_LEX_CHAR_MSB(1))))
#define BC_LEX_KW_ENTRY(a, b, c) \
{ .data = ((b) & ~(BC_LEX_CHAR_MSB(1))) | BC_LEX_CHAR_MSB(c),.name = a }
#define bc_lex_posixErr(l, e) (bc_vm_posixError((e), (l)->line))
#define bc_lex_vposixErr(l, e, ...) \
(bc_vm_posixError((e), (l)->line, __VA_ARGS__))
BcStatus bc_lex_token(BcLex *l);
#define BC_PARSE_TOP_FLAG_PTR(p) ((uint16_t*) bc_vec_top(&(p)->flags))
#define BC_PARSE_TOP_FLAG(p) (*(BC_PARSE_TOP_FLAG_PTR(p)))
#define BC_PARSE_FLAG_BRACE (1<<0)
#define BC_PARSE_BRACE(p) (BC_PARSE_TOP_FLAG(p) & BC_PARSE_FLAG_BRACE)
#define BC_PARSE_FLAG_FUNC_INNER (1<<1)
#define BC_PARSE_FUNC_INNER(p) (BC_PARSE_TOP_FLAG(p) & BC_PARSE_FLAG_FUNC_INNER)
#define BC_PARSE_FLAG_FUNC (1<<2)
#define BC_PARSE_FUNC(p) (BC_PARSE_TOP_FLAG(p) & BC_PARSE_FLAG_FUNC)
#define BC_PARSE_FLAG_BODY (1<<3)
#define BC_PARSE_BODY(p) (BC_PARSE_TOP_FLAG(p) & BC_PARSE_FLAG_BODY)
#define BC_PARSE_FLAG_LOOP (1<<4)
#define BC_PARSE_LOOP(p) (BC_PARSE_TOP_FLAG(p) & BC_PARSE_FLAG_LOOP)
#define BC_PARSE_FLAG_LOOP_INNER (1<<5)
#define BC_PARSE_LOOP_INNER(p) (BC_PARSE_TOP_FLAG(p) & BC_PARSE_FLAG_LOOP_INNER)
#define BC_PARSE_FLAG_IF (1<<6)
#define BC_PARSE_IF(p) (BC_PARSE_TOP_FLAG(p) & BC_PARSE_FLAG_IF)
#define BC_PARSE_FLAG_ELSE (1<<7)
#define BC_PARSE_ELSE(p) (BC_PARSE_TOP_FLAG(p) & BC_PARSE_FLAG_ELSE)
#define BC_PARSE_FLAG_IF_END (1<<8)
#define BC_PARSE_IF_END(p) (BC_PARSE_TOP_FLAG(p) & BC_PARSE_FLAG_IF_END)
#define BC_PARSE_NO_EXEC(p) ((p)->flags.len != 1 || BC_PARSE_TOP_FLAG(p) != 0)
#define BC_PARSE_DELIMITER(t) \
((t) == BC_LEX_SCOLON || (t) == BC_LEX_NLINE || (t) == BC_LEX_EOF)
#define BC_PARSE_BLOCK_STMT(f) \
((f) & (BC_PARSE_FLAG_ELSE | BC_PARSE_FLAG_LOOP_INNER))
#define BC_PARSE_OP(p, l) (((p) & ~(BC_LEX_CHAR_MSB(1))) | (BC_LEX_CHAR_MSB(l)))
#define BC_PARSE_OP_DATA(t) bc_parse_ops[((t) - BC_LEX_OP_INC)]
#define BC_PARSE_OP_LEFT(op) (BC_PARSE_OP_DATA(op) & BC_LEX_CHAR_MSB(1))
#define BC_PARSE_OP_PREC(op) (BC_PARSE_OP_DATA(op) & ~(BC_LEX_CHAR_MSB(1)))
#define BC_PARSE_TOP_OP(p) (*((BcLexType*) bc_vec_top(&(p)->ops)))
#define BC_PARSE_LEAF(prev, bin_last, rparen) \
(!(bin_last) && ((rparen) || bc_parse_inst_isLeaf(prev)))
#define BC_PARSE_INST_VAR(t) \
((t) >= BC_INST_VAR && (t) <= BC_INST_SCALE && (t) != BC_INST_ARRAY)
#define BC_PARSE_PREV_PREFIX(p) \
((p) >= BC_INST_INC_PRE && (p) <= BC_INST_BOOL_NOT)
#define BC_PARSE_OP_PREFIX(t) ((t) == BC_LEX_OP_BOOL_NOT || (t) == BC_LEX_NEG)
// We can calculate the conversion between tokens and exprs by subtracting the
// position of the first operator in the lex enum and adding the position of
// the first in the expr enum. Note: This only works for binary operators.
#define BC_PARSE_TOKEN_INST(t) ((uchar) ((t) - BC_LEX_NEG + BC_INST_NEG))
#define bc_parse_posixErr(p, e) (bc_vm_posixError((e), (p)->l.line))
BcStatus bc_parse_parse(BcParse *p);
BcStatus bc_parse_expr_status(BcParse *p, uint8_t flags, BcParseNext next);
void bc_parse_noElse(BcParse *p);
#define BC_PROG_ONE_CAP (1)
typedef struct BcProgram {
size_t scale;
BcNum ib;
size_t ib_t;
BcNum ob;
size_t ob_t;
BcVec results;
BcVec stack;
BcVec fns;
BcVec fn_map;
BcVec vars;
BcVec var_map;
BcVec arrs;
BcVec arr_map;
BcNum one;
BcNum last;
signed char ib_num[BC_NUM_LONG_LOG10], ob_num[BC_NUM_LONG_LOG10],
one_num[BC_PROG_ONE_CAP];
} BcProgram;
#define BC_PROG_STACK(s, n) ((s)->len >= ((size_t) (n)))
#define BC_PROG_MAIN (0)
#define BC_PROG_READ (1)
#define BC_PROG_STR(n) (!(n)->num && !(n)->cap)
#define BC_PROG_NUM(r, n) \
((r)->t != BC_RESULT_ARRAY && (r)->t != BC_RESULT_STR && !BC_PROG_STR(n))
typedef void (*BcProgramUnary)(BcResult*, BcNum*);
void bc_program_addFunc(BcProgram *p, BcFunc *f, char *name);
size_t bc_program_insertFunc(BcProgram *p, char *name);
BcStatus bc_program_reset(BcProgram *p, BcStatus s);
BcStatus bc_program_exec(BcProgram *p);
unsigned long bc_program_scale(BcNum *n);
unsigned long bc_program_len(BcNum *n);
void bc_program_negate(BcResult *r, BcNum *n);
void bc_program_not(BcResult *r, BcNum *n);
#define BC_FLAG_TTYIN (1<<7)
#define BC_TTYIN (toys.optflags & BC_FLAG_TTYIN)
#define BC_MAX_OBASE ((unsigned long) INT_MAX)
#define BC_MAX_DIM ((unsigned long) INT_MAX)
#define BC_MAX_SCALE ((unsigned long) UINT_MAX)
#define BC_MAX_STRING ((unsigned long) UINT_MAX - 1)
#define BC_MAX_NAME BC_MAX_STRING
#define BC_MAX_NUM BC_MAX_STRING
#define BC_MAX_EXP ((unsigned long) ULONG_MAX)
#define BC_MAX_VARS ((unsigned long) SIZE_MAX - 1)
#define bc_vm_err(e) (bc_vm_error((e), 0))
#define bc_vm_verr(e, ...) (bc_vm_error((e), 0, __VA_ARGS__))
typedef struct BcVm {
BcParse prs;
BcProgram prog;
} BcVm;
BcStatus bc_vm_posixError(BcError e, size_t line, ...);
BcStatus bc_vm_error(BcError e, size_t line, ...);
char bc_sig_msg[] = "\ninterrupt (type \"quit\" to exit)\n";
char bc_copyright[] =
"Copyright (c) 2018 Gavin D. Howard and contributors\n"
"Report bugs at: https://github.com/gavinhoward/bc\n\n"
"This is free software with ABSOLUTELY NO WARRANTY.\n";
char *bc_err_fmt = "\n%s error: ";
char *bc_warn_fmt = "\n%s warning: ";
char *bc_err_line = ":%zu";
char *bc_errs[] = {
"VM",
"Parse",
"Math",
"Runtime",
"POSIX",
};
char bc_err_ids[] = {
BC_ERR_IDX_VM, BC_ERR_IDX_VM, BC_ERR_IDX_VM, BC_ERR_IDX_VM,
BC_ERR_IDX_PARSE, BC_ERR_IDX_PARSE, BC_ERR_IDX_PARSE, BC_ERR_IDX_PARSE,
BC_ERR_IDX_PARSE, BC_ERR_IDX_PARSE, BC_ERR_IDX_PARSE, BC_ERR_IDX_PARSE,
BC_ERR_IDX_PARSE, BC_ERR_IDX_PARSE, BC_ERR_IDX_PARSE, BC_ERR_IDX_PARSE,
BC_ERR_IDX_PARSE, BC_ERR_IDX_PARSE, BC_ERR_IDX_PARSE, BC_ERR_IDX_PARSE,
BC_ERR_IDX_PARSE,
BC_ERR_IDX_MATH, BC_ERR_IDX_MATH, BC_ERR_IDX_MATH, BC_ERR_IDX_MATH,
BC_ERR_IDX_EXEC, BC_ERR_IDX_EXEC, BC_ERR_IDX_EXEC, BC_ERR_IDX_EXEC,
BC_ERR_IDX_EXEC, BC_ERR_IDX_EXEC, BC_ERR_IDX_EXEC, BC_ERR_IDX_EXEC,
BC_ERR_IDX_EXEC, BC_ERR_IDX_EXEC, BC_ERR_IDX_EXEC,
BC_ERR_IDX_POSIX, BC_ERR_IDX_POSIX, BC_ERR_IDX_POSIX, BC_ERR_IDX_POSIX,
BC_ERR_IDX_POSIX, BC_ERR_IDX_POSIX, BC_ERR_IDX_POSIX, BC_ERR_IDX_POSIX,
BC_ERR_IDX_POSIX, BC_ERR_IDX_POSIX, BC_ERR_IDX_POSIX, BC_ERR_IDX_POSIX,
BC_ERR_IDX_POSIX,
};
char *bc_err_msgs[] = {
"memory allocation error",
"I/O error",
"file is not ASCII: %s",
"path is a directory: %s",
"end of file",
"bad character (%c)",
"string end could not be found",
"comment end could not be found",
"bad token",
"name too long: must be [1, %lu]",
"string too long: must be [1, %lu]",
"array too long; must be [1, %lu]",
"bad expression",
"empty expression",
"bad print statement",
"bad function definition",
"bad assignment: left side must be scale, ibase, "
"obase, last, var, or array element",
"no auto variable found",
"function parameter or auto \"%s\" already exists",
"block end could not be found",
"cannot return a value from void function: %s()",
"negative number",
"non integer number",
"overflow",
"divide by zero",
"could not open file: %s",
"number too long: must be [1, %lu]",
"bad ibase; must be [%lu, %lu]",
"bad obase; must be [%lu, %lu]",
"bad scale; must be [%lu, %lu]",
"bad read() expression",
"read() call inside of a read() call",
"variable is wrong type",
"mismatched parameters; need %zu, have %zu",
"undefined function: %s()",
"cannot use a void value in an expression",
"POSIX does not allow names longer than 1 character, like \"%s\"",
"POSIX does not allow '#' script comments",
"POSIX does not allow \"%s\" as a keyword",
"POSIX does not allow a period ('.') as a shortcut for the last result",
"POSIX requires parentheses around return expressions",
"POSIX does not allow the \"%s\" operators",
"POSIX does not allow comparison operators outside if or loops",
"POSIX requires zero or one comparison operator per condition",
"POSIX does not allow an empty init expression in a for loop",
"POSIX does not allow an empty condition expression in a for loop",
"POSIX does not allow an empty update expression in a for loop",
"POSIX requires the left brace be on the same line as the function header",
"POSIX does not allow array references as function parameters",
};
char bc_func_main[] = "(main)";
char bc_func_read[] = "(read)";
BcLexKeyword bc_lex_kws[] = {
BC_LEX_KW_ENTRY("auto", 4, 1),
BC_LEX_KW_ENTRY("break", 5, 1),
BC_LEX_KW_ENTRY("continue", 8, 0),
BC_LEX_KW_ENTRY("define", 6, 1),
BC_LEX_KW_ENTRY("for", 3, 1),
BC_LEX_KW_ENTRY("if", 2, 1),
BC_LEX_KW_ENTRY("limits", 6, 0),
BC_LEX_KW_ENTRY("return", 6, 1),
BC_LEX_KW_ENTRY("while", 5, 1),
BC_LEX_KW_ENTRY("halt", 4, 0),
BC_LEX_KW_ENTRY("last", 4, 0),
BC_LEX_KW_ENTRY("ibase", 5, 1),
BC_LEX_KW_ENTRY("obase", 5, 1),
BC_LEX_KW_ENTRY("scale", 5, 1),
BC_LEX_KW_ENTRY("length", 6, 1),
BC_LEX_KW_ENTRY("print", 5, 0),
BC_LEX_KW_ENTRY("sqrt", 4, 1),
BC_LEX_KW_ENTRY("abs", 3, 0),
BC_LEX_KW_ENTRY("quit", 4, 1),
BC_LEX_KW_ENTRY("read", 4, 0),
BC_LEX_KW_ENTRY("else", 4, 0),
};
size_t bc_lex_kws_len = sizeof(bc_lex_kws) / sizeof(BcLexKeyword);
char *bc_parse_const1 = "1";
// This is an array of data for operators that correspond to token types.
uchar bc_parse_ops[] = {
BC_PARSE_OP(0, 0), BC_PARSE_OP(0, 0),
BC_PARSE_OP(1, 0), BC_PARSE_OP(1, 0),
BC_PARSE_OP(4, 0),
BC_PARSE_OP(5, 1), BC_PARSE_OP(5, 1), BC_PARSE_OP(5, 1),
BC_PARSE_OP(6, 1), BC_PARSE_OP(6, 1),
BC_PARSE_OP(9, 1), BC_PARSE_OP(9, 1), BC_PARSE_OP(9, 1),
BC_PARSE_OP(9, 1), BC_PARSE_OP(9, 1), BC_PARSE_OP(9, 1),
BC_PARSE_OP(11, 1), BC_PARSE_OP(10, 1),
BC_PARSE_OP(8, 0), BC_PARSE_OP(8, 0), BC_PARSE_OP(8, 0),
BC_PARSE_OP(8, 0), BC_PARSE_OP(8, 0), BC_PARSE_OP(8, 0),
BC_PARSE_OP(8, 0),
};
// These identify what tokens can come after expressions in certain cases.
BcParseNext bc_parse_next_expr =
BC_PARSE_NEXT(4, BC_LEX_NLINE, BC_LEX_SCOLON, BC_LEX_RBRACE, BC_LEX_EOF);
BcParseNext bc_parse_next_param =
BC_PARSE_NEXT(2, BC_LEX_RPAREN, BC_LEX_COMMA);
BcParseNext bc_parse_next_print =
BC_PARSE_NEXT(4, BC_LEX_COMMA, BC_LEX_NLINE, BC_LEX_SCOLON, BC_LEX_EOF);
BcParseNext bc_parse_next_rel = BC_PARSE_NEXT(1, BC_LEX_RPAREN);
BcParseNext bc_parse_next_elem = BC_PARSE_NEXT(1, BC_LEX_RBRACKET);
BcParseNext bc_parse_next_for = BC_PARSE_NEXT(1, BC_LEX_SCOLON);
BcParseNext bc_parse_next_read =
BC_PARSE_NEXT(2, BC_LEX_NLINE, BC_LEX_EOF);
char bc_num_hex_digits[] = "0123456789ABCDEF";
BcNumBinaryOp bc_program_ops[] = {
bc_num_pow, bc_num_mul, bc_num_div, bc_num_mod, bc_num_add, bc_num_sub,
};
BcNumBinaryOpReq bc_program_opReqs[] = {
bc_num_powReq, bc_num_mulReq, bc_num_mulReq, bc_num_mulReq,
bc_num_addReq, bc_num_addReq,
};
BcProgramUnary bc_program_unarys[] = {
bc_program_negate, bc_program_not,
};
char bc_program_stdin_name[] = "<stdin>";
char bc_program_ready_msg[] = "ready for more input\n";
char *bc_lib_name = "gen/lib.bc";
char bc_lib[] = {
115,99,97,108,101,61,50,48,10,100,101,102,105,110,101,32,101,40,120,41,123,
10,97,117,116,111,32,98,44,115,44,110,44,114,44,100,44,105,44,112,44,102,44,
118,10,98,61,105,98,97,115,101,10,105,98,97,115,101,61,65,10,105,102,40,120,
60,48,41,123,10,110,61,49,10,120,61,45,120,10,125,10,115,61,115,99,97,108,101,
10,114,61,54,43,115,43,46,52,52,42,120,10,115,99,97,108,101,61,115,99,97,108,
101,40,120,41,43,49,10,119,104,105,108,101,40,120,62,49,41,123,10,100,43,61,
49,10,120,47,61,50,10,115,99,97,108,101,43,61,49,10,125,10,115,99,97,108,101,
61,114,10,114,61,120,43,49,10,112,61,120,10,102,61,118,61,49,10,102,111,114,
40,105,61,50,59,118,59,43,43,105,41,123,10,112,42,61,120,10,102,42,61,105,10,
118,61,112,47,102,10,114,43,61,118,10,125,10,119,104,105,108,101,40,100,45,
45,41,114,42,61,114,10,115,99,97,108,101,61,115,10,105,98,97,115,101,61,98,
10,105,102,40,110,41,114,101,116,117,114,110,40,49,47,114,41,10,114,101,116,
117,114,110,40,114,47,49,41,10,125,10,100,101,102,105,110,101,32,108,40,120,
41,123,10,97,117,116,111,32,98,44,115,44,114,44,112,44,97,44,113,44,105,44,
118,10,98,61,105,98,97,115,101,10,105,98,97,115,101,61,65,10,105,102,40,120,
60,61,48,41,123,10,114,61,40,49,45,49,48,94,115,99,97,108,101,41,47,49,10,105,
98,97,115,101,61,98,10,114,101,116,117,114,110,40,114,41,10,125,10,115,61,115,
99,97,108,101,10,115,99,97,108,101,43,61,54,10,112,61,50,10,119,104,105,108,
101,40,120,62,61,50,41,123,10,112,42,61,50,10,120,61,115,113,114,116,40,120,
41,10,125,10,119,104,105,108,101,40,120,60,61,46,53,41,123,10,112,42,61,50,
10,120,61,115,113,114,116,40,120,41,10,125,10,114,61,97,61,40,120,45,49,41,
47,40,120,43,49,41,10,113,61,97,42,97,10,118,61,49,10,102,111,114,40,105,61,
51,59,118,59,105,43,61,50,41,123,10,97,42,61,113,10,118,61,97,47,105,10,114,
43,61,118,10,125,10,114,42,61,112,10,115,99,97,108,101,61,115,10,105,98,97,
115,101,61,98,10,114,101,116,117,114,110,40,114,47,49,41,10,125,10,100,101,
102,105,110,101,32,115,40,120,41,123,10,97,117,116,111,32,98,44,115,44,114,
44,97,44,113,44,105,10,105,102,40,120,60,48,41,114,101,116,117,114,110,40,45,
115,40,45,120,41,41,10,98,61,105,98,97,115,101,10,105,98,97,115,101,61,65,10,
115,61,115,99,97,108,101,10,115,99,97,108,101,61,49,46,49,42,115,43,50,10,97,
61,97,40,49,41,10,115,99,97,108,101,61,48,10,113,61,40,120,47,97,43,50,41,47,
52,10,120,45,61,52,42,113,42,97,10,105,102,40,113,37,50,41,120,61,45,120,10,
115,99,97,108,101,61,115,43,50,10,114,61,97,61,120,10,113,61,45,120,42,120,
10,102,111,114,40,105,61,51,59,97,59,105,43,61,50,41,123,10,97,42,61,113,47,
40,105,42,40,105,45,49,41,41,10,114,43,61,97,10,125,10,115,99,97,108,101,61,
115,10,105,98,97,115,101,61,98,10,114,101,116,117,114,110,40,114,47,49,41,10,
125,10,100,101,102,105,110,101,32,99,40,120,41,123,10,97,117,116,111,32,98,
44,115,10,98,61,105,98,97,115,101,10,105,98,97,115,101,61,65,10,115,61,115,
99,97,108,101,10,115,99,97,108,101,42,61,49,46,50,10,120,61,115,40,50,42,97,
40,49,41,43,120,41,10,115,99,97,108,101,61,115,10,105,98,97,115,101,61,98,10,
114,101,116,117,114,110,40,120,47,49,41,10,125,10,100,101,102,105,110,101,32,
97,40,120,41,123,10,97,117,116,111,32,98,44,115,44,114,44,110,44,97,44,109,
44,116,44,102,44,105,44,117,10,98,61,105,98,97,115,101,10,105,98,97,115,101,
61,65,10,110,61,49,10,105,102,40,120,60,48,41,123,10,110,61,45,49,10,120,61,
45,120,10,125,10,105,102,40,115,99,97,108,101,60,54,53,41,123,10,105,102,40,
120,61,61,49,41,123,10,114,61,46,55,56,53,51,57,56,49,54,51,51,57,55,52,52,
56,51,48,57,54,49,53,54,54,48,56,52,53,56,49,57,56,55,53,55,50,49,48,52,57,
50,57,50,51,52,57,56,52,51,55,55,54,52,53,53,50,52,51,55,51,54,49,52,56,48,
47,110,10,105,98,97,115,101,61,98,10,114,101,116,117,114,110,40,114,41,10,125,
10,105,102,40,120,61,61,46,50,41,123,10,114,61,46,49,57,55,51,57,53,53,53,57,
56,52,57,56,56,48,55,53,56,51,55,48,48,52,57,55,54,53,49,57,52,55,57,48,50,
57,51,52,52,55,53,56,53,49,48,51,55,56,55,56,53,50,49,48,49,53,49,55,54,56,
56,57,52,48,50,47,110,10,105,98,97,115,101,61,98,10,114,101,116,117,114,110,
40,114,41,10,125,10,125,10,115,61,115,99,97,108,101,10,105,102,40,120,62,46,
50,41,123,10,115,99,97,108,101,43,61,53,10,97,61,97,40,46,50,41,10,125,10,115,
99,97,108,101,61,115,43,51,10,119,104,105,108,101,40,120,62,46,50,41,123,10,
109,43,61,49,10,120,61,40,120,45,46,50,41,47,40,49,43,46,50,42,120,41,10,125,
10,114,61,117,61,120,10,102,61,45,120,42,120,10,116,61,49,10,102,111,114,40,
105,61,51,59,116,59,105,43,61,50,41,123,10,117,42,61,102,10,116,61,117,47,105,
10,114,43,61,116,10,125,10,115,99,97,108,101,61,115,10,105,98,97,115,101,61,
98,10,114,101,116,117,114,110,40,40,109,42,97,43,114,41,47,110,41,10,125,10,
100,101,102,105,110,101,32,106,40,110,44,120,41,123,10,97,117,116,111,32,98,
44,115,44,111,44,97,44,105,44,118,44,102,10,98,61,105,98,97,115,101,10,105,
98,97,115,101,61,65,10,115,61,115,99,97,108,101,10,115,99,97,108,101,61,48,
10,110,47,61,49,10,105,102,40,110,60,48,41,123,10,110,61,45,110,10,111,61,110,
37,50,10,125,10,97,61,49,10,102,111,114,40,105,61,50,59,105,60,61,110,59,43,
43,105,41,97,42,61,105,10,115,99,97,108,101,61,49,46,53,42,115,10,97,61,40,
120,94,110,41,47,50,94,110,47,97,10,114,61,118,61,49,10,102,61,45,120,42,120,
47,52,10,115,99,97,108,101,43,61,108,101,110,103,116,104,40,97,41,45,115,99,
97,108,101,40,97,41,10,102,111,114,40,105,61,49,59,118,59,43,43,105,41,123,
10,118,61,118,42,102,47,105,47,40,110,43,105,41,10,114,43,61,118,10,125,10,
115,99,97,108,101,61,115,10,105,98,97,115,101,61,98,10,105,102,40,111,41,97,
61,45,97,10,114,101,116,117,114,110,40,97,42,114,47,49,41,10,125,10,0
};
static void bc_vec_grow(BcVec *v, unsigned long n) {
unsigned long old = v->cap;
while (v->cap < v->len + n) v->cap *= 2;
if (old != v->cap) v->v = xrealloc(v->v, v->size * v->cap);
}
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);
}
void bc_vec_expand(BcVec *v, size_t req) {
if (v->cap < req) {
v->v = xrealloc(v->v, v->size * req);
v->cap = req;
}
}
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));
}
}
void bc_vec_npush(BcVec *v, size_t n, void *data) {
bc_vec_grow(v, n);
memcpy(v->v + (v->size * v->len), data, v->size * n);
v->len += n;
}
void bc_vec_push(BcVec *v, void *data) {
bc_vec_npush(v, 1, data);
}
void bc_vec_pushByte(BcVec *v, uchar data) {
bc_vec_push(v, &data);
}
void bc_vec_pushIndex(BcVec *v, size_t idx) {
uchar amt, nums[sizeof(size_t)];
for (amt = 0; idx; ++amt) {
nums[amt] = (uchar) idx;
idx &= ((size_t) ~(UCHAR_MAX));
idx >>= sizeof(uchar) * CHAR_BIT;
}
bc_vec_push(v, &amt);
bc_vec_npush(v, amt, nums);
}
static void bc_vec_pushAt(BcVec *v, void *data, size_t idx) {
if (idx == v->len) bc_vec_push(v, data);
else {
char *ptr;
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);
}
}
void bc_vec_string(BcVec *v, size_t len, char *str) {
bc_vec_npop(v, v->len);
bc_vec_expand(v, len + 1);
memcpy(v->v, str, len);
v->len = len;
bc_vec_pushByte(v, '\0');
}
void bc_vec_concat(BcVec *v, char *str) {
unsigned long len;
if (!v->len) bc_vec_pushByte(v, '\0');
len = strlen(str);
bc_vec_grow(v, len);
strcpy(v->v+v->len-1, str);
v->len += len;
}
void bc_vec_empty(BcVec *v) {
bc_vec_npop(v, v->len);
bc_vec_pushByte(v, '\0');
}
void* bc_vec_item(BcVec *v, size_t idx) {
return v->v + v->size * idx;
}
void* bc_vec_item_rev(BcVec *v, size_t idx) {
return v->v + v->size * (v->len - idx - 1);
}
void bc_vec_free(void *vec) {
BcVec *v = (BcVec*) vec;
bc_vec_npop(v, v->len);
free(v->v);
}
static size_t bc_map_find(BcVec *v, struct str_len *ptr) {
size_t low = 0, high = v->len;
while (low < high) {
size_t mid = (low + high) / 2;
struct str_len *id = bc_vec_item(v, mid);
int result = bc_id_cmp(ptr, id);
if (!result) return mid;
else if (result < 0) high = mid;
else low = mid + 1;
}
return low;
}
int bc_map_insert(BcVec *v, struct str_len *ptr, size_t *i) {
*i = bc_map_find(v, ptr);
if (*i == v->len) bc_vec_push(v, ptr);
else if (!bc_id_cmp(ptr, bc_vec_item(v, *i))) return 0;
else bc_vec_pushAt(v, ptr, *i);
return 1;
}
size_t bc_map_index(BcVec *v, struct str_len *ptr) {
size_t i = bc_map_find(v, ptr);
if (i >= v->len) return SIZE_MAX;
return bc_id_cmp(ptr, bc_vec_item(v, i)) ? SIZE_MAX : i;
}
static int bc_read_binary(char *buf, size_t size) {
size_t i;
for (i = 0; i < size; ++i)
if ((buf[i]<' ' && !isspace(buf[i])) || buf[i]>'~') return 1;
return 0;
}
BcStatus bc_read_chars(BcVec *vec, char *prompt) {
int i;
signed char c = 0;
bc_vec_npop(vec, vec->len);
if (BC_TTYIN && !FLAG(s)) {
fputs(prompt, stderr);
fflush(stderr);
}
while (!TT.sig && c != '\n') {
i = fgetc(stdin);
if (i == EOF) {
if (errno == EINTR) {
if (TT.sig == SIGTERM || TT.sig == SIGQUIT) return BC_STATUS_SIGNAL;
TT.sig = 0;
if (BC_TTYIN) {
fputs(bc_program_ready_msg, stderr);
if (!FLAG(s)) fputs(prompt, stderr);
fflush(stderr);
}
else return BC_STATUS_SIGNAL;
continue;
}
bc_vec_pushByte(vec, '\0');
return BC_STATUS_EOF;
}
c = (signed char) i;
bc_vec_push(vec, &c);
}
bc_vec_pushByte(vec, '\0');
return TT.sig ? BC_STATUS_SIGNAL : BC_STATUS_SUCCESS;
}
BcStatus bc_read_line(BcVec *vec, char *prompt) {
BcStatus s;
// We are about to output to stderr, so flush stdout to
// make sure that we don't get the outputs mixed up.
fflush(stdout);
s = bc_read_chars(vec, prompt);
if (s && s != BC_STATUS_EOF) return s;
if (bc_read_binary(vec->v, vec->len - 1))
return bc_vm_verr(BC_ERROR_VM_BIN_FILE, bc_program_stdin_name);
return BC_STATUS_SUCCESS;
}
BcStatus bc_read_file(char *path, char **buf) {
BcError e = BC_ERROR_VM_IO_ERR;
FILE *f;
size_t size, read;
long res;
struct stat pstat;
f = fopen(path, "r");
if (!f) return bc_vm_verr(BC_ERROR_EXEC_FILE_ERR, path);
if (fstat(fileno(f), &pstat) == -1) goto malloc_err;
if (S_ISDIR(pstat.st_mode)) {
e = BC_ERROR_VM_PATH_DIR;
goto malloc_err;
}
if (fseek(f, 0, SEEK_END) == -1) goto malloc_err;
res = ftell(f);
if (res < 0) goto malloc_err;
if (fseek(f, 0, SEEK_SET) == -1) goto malloc_err;
size = (size_t) res;
*buf = xmalloc(size + 1);
read = fread(*buf, 1, size, f);
if (read != size) goto read_err;
(*buf)[size] = '\0';
if (bc_read_binary(*buf, size)) {
e = BC_ERROR_VM_BIN_FILE;
goto read_err;
}
fclose(f);
return BC_STATUS_SUCCESS;
read_err:
free(*buf);
malloc_err:
fclose(f);
return bc_vm_verr(e, path);
}
static void bc_num_setToZero(BcNum *n, size_t scale) {
n->len = 0;
n->neg = 0;
n->rdx = scale;
}
void bc_num_one(BcNum *n) {
bc_num_setToZero(n, 0);
n->len = 1;
n->num[0] = 1;
}
void bc_num_ten(BcNum *n) {
bc_num_setToZero(n, 0);
n->len = 2;
n->num[0] = 0;
n->num[1] = 1;
}
static size_t bc_num_log10(size_t i) {
size_t len;
for (len = 1; i; i /= 10, ++len);
return len;
}
static BcStatus bc_num_subArrays(signed char *a, signed char *b, size_t len)
{
size_t i, j;
for (i = 0; !TT.sig && i < len; ++i) {
for (a[i] -= b[i], j = 0; !TT.sig && a[i + j] < 0;) {
a[i + j++] += 10;
a[i + j] -= 1;
}
}
return TT.sig ? BC_STATUS_SIGNAL : BC_STATUS_SUCCESS;
}
static ssize_t bc_num_compare(signed char *a, signed char *b, size_t len)
{
size_t i;
int c = 0;
for (i = len - 1; !TT.sig && i < len && !(c = a[i] - b[i]); --i);
return BC_NUM_NEG(i + 1, c < 0);
}
ssize_t bc_num_cmp(BcNum *a, BcNum *b) {
size_t i, min, a_int, b_int, diff;
signed char *max_num, *min_num;
int a_max, neg = 0;
ssize_t cmp;
if (a == b) return 0;
if (!a->len) return BC_NUM_NEG(b->len != 0, !b->neg);
if (!b->len) return BC_NUM_CMP_ZERO(a);
if (a->neg) {
if (b->neg) neg = 1;
else return -1;
} else if (b->neg) return 1;
a_int = BC_NUM_INT(a);
b_int = BC_NUM_INT(b);
a_int -= b_int;
a_max = (a->rdx > b->rdx);
if (a_int) return neg ? -((ssize_t) a_int) : (ssize_t) a_int;
if (a_max) {
min = b->rdx;
diff = a->rdx - b->rdx;
max_num = a->num + diff;
min_num = b->num;
} else {
min = a->rdx;
diff = b->rdx - a->rdx;
max_num = b->num + diff;
min_num = a->num;
}
cmp = bc_num_compare(max_num, min_num, b_int + min);
if (cmp) return BC_NUM_NEG(cmp, (!a_max) != neg);
for (max_num -= diff, i = diff - 1; !TT.sig && i < diff; --i) {
if (max_num[i]) return BC_NUM_NEG(1, (!a_max) != neg);
}
return 0;
}
static void bc_num_clean(BcNum *n) {
while (n->len && !n->num[n->len - 1]) --n->len;
if (!n->len) n->neg = 0;
else if (n->len < n->rdx) n->len = n->rdx;
}
void bc_num_truncate(BcNum *n, size_t places) {
if (!places) return;
n->rdx -= places;
if (n->len) {
n->len -= places;
memmove(n->num, n->num + places, n->len);
bc_num_clean(n);
}
}
static void bc_num_extend(BcNum *n, size_t places) {
size_t len = n->len + places;
if (!places) return;
if (n->cap < len) bc_num_expand(n, len);
memmove(n->num + places, n->num, n->len);
memset(n->num, 0, places);
if (n->len) n->len += places;
n->rdx += places;
}
static void bc_num_retireMul(BcNum *n, size_t scale, int neg1, int 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) n->neg = (!neg1 != !neg2);
}
static void bc_num_split(BcNum *n, size_t idx, BcNum *a, BcNum *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);
memcpy(a->num, n->num, idx);
bc_num_clean(b);
}
else bc_num_copy(a, n);
bc_num_clean(a);
}
static BcStatus bc_num_shift(BcNum *n, size_t places) {
if (!places || !n->len) return BC_STATUS_SUCCESS;
if (places + n->len > BC_MAX_NUM)
return bc_vm_verr(BC_ERROR_MATH_OVERFLOW, "shifted left too far");
if (n->rdx >= places) n->rdx -= places;
else {
bc_num_extend(n, places - n->rdx);
n->rdx = 0;
}
bc_num_clean(n);
return BC_STATUS_SUCCESS;
}
static BcStatus bc_num_inv(BcNum *a, BcNum *b, size_t scale) {
BcNum one;
signed char num[2];
one.cap = 2;
one.num = num;
bc_num_one(&one);
return bc_num_div(&one, a, b, scale);
}
static unsigned int bc_num_addDigit(signed char *num, unsigned int d, unsigned int c)
{
d += c;
*num = d % 10;
return d / 10;
}
static BcStatus bc_num_a(BcNum *a, BcNum *b, BcNum *c, size_t sub) {
signed char *ptr, *ptr_a, *ptr_b, *ptr_c;
size_t i, max, min_rdx, min_int, diff, a_int, b_int;
unsigned int 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) {
bc_num_copy(c, b);
if (sub && c->len) c->neg = !c->neg;
return BC_STATUS_SUCCESS;
}
if (!b->len) {
bc_num_copy(c, a);
return BC_STATUS_SUCCESS;
}
c->neg = a->neg;
c->rdx = maxof(a->rdx, b->rdx);
min_rdx = minof(a->rdx, b->rdx);
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;
}
for (ptr_c = c->num, i = 0; i < diff; ++i) ptr_c[i] = ptr[i];
c->len = diff;
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;
}
for (carry = 0, i = 0; !TT.sig && i < min_rdx + min_int; ++i) {
unsigned int in = (unsigned int) (ptr_a[i] + ptr_b[i]);
carry = bc_num_addDigit(ptr_c + i, in, carry);
}
for (; !TT.sig && i < max + min_rdx; ++i)
carry = bc_num_addDigit(ptr_c + i, (unsigned int) ptr[i], carry);
c->len += i;
if (carry) c->num[c->len++] = carry;
return TT.sig ? BC_STATUS_SIGNAL : BC_STATUS_SUCCESS;
}
static BcStatus bc_num_s(BcNum *a, BcNum *b, BcNum *c, size_t sub) {
BcStatus s;
ssize_t cmp;
BcNum *minuend, *subtrahend;
size_t start;
int 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) {
bc_num_copy(c, b);
if (sub && c->len) c->neg = !c->neg;
return BC_STATUS_SUCCESS;
}
if (!b->len) {
bc_num_copy(c, a);
return BC_STATUS_SUCCESS;
}
aneg = a->neg;
bneg = b->neg;
a->neg = b->neg = 0;
cmp = bc_num_cmp(a, b);
a->neg = aneg;
b->neg = bneg;
if (!cmp) {
bc_num_setToZero(c, maxof(a->rdx, b->rdx));
return 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;
s = bc_num_subArrays(c->num + start, subtrahend->num, subtrahend->len);
bc_num_clean(c);
return s;
}
static BcStatus bc_num_k(BcNum *a, BcNum *b, BcNum *c) {
BcStatus s;
size_t max = maxof(a->len, b->len), max2 = (max + 1) / 2;
BcNum l1, h1, l2, h2, m2, m1, z0, z1, z2, temp;
int aone = BC_NUM_ONE(a);
// This is here because the function is recursive.
if (TT.sig) return BC_STATUS_SIGNAL;
if (!a->len || !b->len) {
bc_num_setToZero(c, 0);
return BC_STATUS_SUCCESS;
}
if (aone || BC_NUM_ONE(b)) {
bc_num_copy(c, aone ? b : a);
return BC_STATUS_SUCCESS;
}
// check karatsuba length
if (a->len + b->len < 32 || a->len < 32 || b->len < 32)
{
size_t i, j, len;
unsigned int carry;
signed char *ptr_c;
bc_num_expand(c, a->len + b->len + 1);
ptr_c = c->num;
memset(ptr_c, 0, c->cap);
c->len = len = 0;
for (i = 0; !TT.sig && i < b->len; ++i) {
signed char *ptr = ptr_c + i;
carry = 0;
for (j = 0; !TT.sig && j < a->len; ++j) {
unsigned int in = (uchar) ptr[j];
in += ((unsigned int) a->num[j]) * ((unsigned int) b->num[i]);
carry = bc_num_addDigit(ptr + j, in, carry);
}
// todo: is this typecast useless?
ptr[j] += (signed) carry;
len = maxof(len, i + j + (carry != 0));
}
c->len = len;
return TT.sig ? BC_STATUS_SIGNAL : 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 = bc_num_add(&h1, &l1, &m1, 0);
if (s) goto err;
s = bc_num_add(&h2, &l2, &m2, 0);
if (s) goto err;
s = bc_num_k(&h1, &h2, &z0);
if (s) goto err;
s = bc_num_k(&m1, &m2, &z1);
if (s) goto err;
s = bc_num_k(&l1, &l2, &z2);
if (s) goto err;
s = bc_num_sub(&z1, &z0, &temp, 0);
if (s) goto err;
s = bc_num_sub(&temp, &z2, &z1, 0);
if (s) goto err;
s = bc_num_shift(&z0, max2 * 2);
if (s) goto err;
s = bc_num_shift(&z1, max2);
if (s) goto err;
s = bc_num_add(&z0, &z1, &temp, 0);
if (s) goto err;
s = bc_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 s;
}
static BcStatus bc_num_m(BcNum *a, BcNum *b, BcNum *c, size_t scale) {
BcStatus s;
BcNum cpa, cpb;
size_t maxrdx = maxof(a->rdx, b->rdx);
scale = maxof(scale, a->rdx);
scale = maxof(scale, b->rdx);
scale = minof(a->rdx + b->rdx, scale);
maxrdx = maxof(maxrdx, scale);
bc_num_createCopy(&cpa, a);
bc_num_createCopy(&cpb, b);
cpa.neg = cpb.neg = 0;
s = bc_num_shift(&cpa, maxrdx);
if (s) goto err;
s = bc_num_shift(&cpb, maxrdx);
if (s) goto err;
s = bc_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);
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 s;
}
static BcStatus bc_num_d(BcNum *a, BcNum *b, BcNum *c, size_t scale) {
BcStatus s = BC_STATUS_SUCCESS;
signed char *n, *p, q;
size_t len, end, i;
BcNum cp;
int zero = 1;
if (!b->len) return bc_vm_err(BC_ERROR_MATH_DIVIDE_BY_ZERO);
if (!a->len) {
bc_num_setToZero(c, scale);
return BC_STATUS_SUCCESS;
}
if (BC_NUM_ONE(b)) {
bc_num_copy(c, a);
bc_num_retireMul(c, scale, a->neg, b->neg);
return BC_STATUS_SUCCESS;
}
bc_num_init(&cp, bc_num_mulReq(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 (i = 0; zero && i < len; ++i) zero = !b->num[len - i - 1];
len -= i - 1;
}
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);
memset(c->num + end, 0, c->cap - end);
c->rdx = cp.rdx;
c->len = cp.len;
p = b->num;
for (i = end - 1; !TT.sig && !s && i < end; --i) {
n = cp.num + i;
for (q = 0; !s && (n[len] || bc_num_compare(n, p, len) >= 0); ++q)
s = bc_num_subArrays(n, p, len);
c->num[i] = q;
}
if (!s) bc_num_retireMul(c, scale, a->neg, b->neg);
bc_num_free(&cp);
return s;
}
static BcStatus bc_num_r(BcNum *a, BcNum *b, BcNum *c, BcNum *d, size_t scale,
size_t ts)
{
BcStatus s;
BcNum temp;
int neg;
if (!b->len) return bc_vm_err(BC_ERROR_MATH_DIVIDE_BY_ZERO);
if (!a->len) {
bc_num_setToZero(c, ts);
bc_num_setToZero(d, ts);
return BC_STATUS_SUCCESS;
}
bc_num_init(&temp, d->cap);
bc_num_d(a, b, c, scale);
if (scale) scale = ts;
s = bc_num_m(c, b, &temp, scale);
if (s) goto err;
s = bc_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 s;
}
static BcStatus bc_num_rem(BcNum *a, BcNum *b, BcNum *c, size_t scale) {
BcStatus s;
BcNum c1;
size_t ts = maxof(scale + b->rdx, a->rdx), len = bc_num_mulReq(a, b, ts);
bc_num_init(&c1, len);
s = bc_num_r(a, b, &c1, c, scale, ts);
bc_num_free(&c1);
return s;
}
static BcStatus bc_num_p(BcNum *a, BcNum *b, BcNum *c, size_t scale) {
BcStatus s = BC_STATUS_SUCCESS;
BcNum copy;
unsigned long pow = 0;
size_t i, powrdx, resrdx;
int neg, zero;
if (b->rdx) return bc_vm_err(BC_ERROR_MATH_NON_INTEGER);
if (!b->len) {
bc_num_one(c);
return BC_STATUS_SUCCESS;
}
if (!a->len) {
if (b->neg) return bc_vm_err(BC_ERROR_MATH_DIVIDE_BY_ZERO);
bc_num_setToZero(c, scale);
return BC_STATUS_SUCCESS;
}
if (BC_NUM_ONE(b)) {
if (!b->neg) bc_num_copy(c, a);
else s = bc_num_inv(a, c, scale);
return s;
}
neg = b->neg;
b->neg = 0;
s = bc_num_ulong(b, &pow);
b->neg = neg;
if (s) return s;
bc_num_createCopy(&copy, a);
if (!neg) scale = minof(a->rdx * pow, maxof(scale, a->rdx));
for (powrdx = a->rdx; !TT.sig && !(pow & 1); pow >>= 1) {
powrdx <<= 1;
s = bc_num_mul(&copy, &copy, &copy, powrdx);
if (s) goto err;
}
if (TT.sig) {
s = BC_STATUS_SIGNAL;
goto err;
}
bc_num_copy(c, &copy);
resrdx = powrdx;
while (!TT.sig && (pow >>= 1)) {
powrdx <<= 1;
s = bc_num_mul(&copy, &copy, &copy, powrdx);
if (s) goto err;
if (pow & 1) {
resrdx += powrdx;
s = bc_num_mul(c, &copy, c, resrdx);
if (s) goto err;
}
}
if (neg) {
s = bc_num_inv(c, c, scale);
if (s) goto err;
}
if (TT.sig) {
s = BC_STATUS_SIGNAL;
goto err;
}
if (c->rdx > scale) bc_num_truncate(c, c->rdx - scale);
// We can't use bc_num_clean() here.
for (zero = 1, i = 0; zero && i < c->len; ++i) zero = !c->num[i];
if (zero) bc_num_setToZero(c, scale);
err:
bc_num_free(&copy);
return s;
}
static BcStatus bc_num_binary(BcNum *a, BcNum *b, BcNum *c, size_t scale,
BcNumBinaryOp op, size_t req)
{
BcStatus s;
BcNum num2, *ptr_a, *ptr_b;
int init = 0;
if (c == a) {
ptr_a = &num2;
memcpy(ptr_a, c, sizeof(BcNum));
init = 1;
}
else ptr_a = a;
if (c == b) {
ptr_b = &num2;
if (c != a) {
memcpy(ptr_b, c, sizeof(BcNum));
init = 1;
}
}
else ptr_b = b;
if (init) bc_num_init(c, req);
else bc_num_expand(c, req);
s = op(ptr_a, ptr_b, c, scale);
if (init) bc_num_free(&num2);
return s;
}
static unsigned long bc_num_parseChar(char c, size_t base_t) {
if (isupper(c)) {
c += 10 - 'A';
if (c >= base_t) c = base_t - 1;
} else c -= '0';
return c;
}
static BcStatus bc_num_parseBase(BcNum *n, char *val,
BcNum *base, size_t base_t)
{
BcStatus s = BC_STATUS_SUCCESS;
BcNum temp, mult, result;
signed char c = 0;
int zero = 1;
unsigned long v;
size_t i, digits, len = strlen(val);
for (i = 0; zero && i < len; ++i) zero = (val[i] == '.' || val[i] == '0');
if (zero) return BC_STATUS_SUCCESS;
bc_num_init(&temp, BC_NUM_LONG_LOG10);
bc_num_init(&mult, BC_NUM_LONG_LOG10);
for (i = 0; i < len && (c = val[i]) && c != '.'; ++i) {
v = bc_num_parseChar(c, base_t);
s = bc_num_mul(n, base, &mult, 0);
if (s) goto int_err;
bc_num_ulong2num(&temp, v);
s = bc_num_add(&mult, &temp, n, 0);
if (s) goto int_err;
}
if (i == len && !(c = val[i])) goto int_err;
bc_num_init(&result, base->len);
bc_num_one(&mult);
for (i += 1, digits = 0; i < len && (c = val[i]); ++i, ++digits) {
v = bc_num_parseChar(c, base_t);
s = bc_num_mul(&result, base, &result, 0);
if (s) goto err;
bc_num_ulong2num(&temp, v);
s = bc_num_add(&result, &temp, &result, 0);
if (s) goto err;
s = bc_num_mul(&mult, base, &mult, 0);
if (s) goto err;
}
s = bc_num_div(&result, &mult, &result, digits);
if (s) goto err;
s = bc_num_add(n, &result, n, digits);
if (s) goto err;
if (n->len) {
if (n->rdx < digits) bc_num_extend(n, digits - n->rdx);
}
else bc_num_setToZero(n, 0);
err:
bc_num_free(&result);
int_err:
bc_num_free(&mult);
bc_num_free(&temp);
return s;
}
static void bc_num_printNewline() {
if (TT.nchars >= TT.line_len - 1) {
putchar('\\');
putchar('\n');
TT.nchars = 0;
}
}
static void bc_num_printDigits(size_t n, size_t len, int rdx) {
size_t exp, pow;
bc_num_printNewline();
putchar(rdx ? '.' : ' ');
++TT.nchars;
bc_num_printNewline();
for (exp = 0, pow = 1; exp < len - 1; ++exp, pow *= 10);
for (exp = 0; exp < len; pow /= 10, ++TT.nchars, ++exp) {
size_t dig;
bc_num_printNewline();
dig = n / pow;
n -= dig * pow;
putchar(((uchar) dig) + '0');
}
}
static void bc_num_printHex(size_t n, size_t len, int rdx) {
if (rdx) {
bc_num_printNewline();
putchar('.');
TT.nchars += 1;
}
bc_num_printNewline();
putchar(bc_num_hex_digits[n]);
TT.nchars += len;
}
static void bc_num_printDecimal(BcNum *n) {
size_t i, rdx = n->rdx - 1;
if (n->neg) putchar('-');
TT.nchars += n->neg;
for (i = n->len - 1; i < n->len; --i)
bc_num_printHex((size_t) n->num[i], 1, i == rdx);
}
static BcStatus bc_num_printNum(BcNum *n, BcNum *base,
size_t len, BcNumDigitOp print)
{
BcStatus s;
BcVec stack;
BcNum intp, fracp, digit, frac_len;
unsigned long dig, *ptr;
size_t i;
int radix;
if (!n->len) {
print(0, len, 0);
return BC_STATUS_SUCCESS;
}
bc_vec_init(&stack, sizeof(unsigned long), NULL);
bc_num_init(&fracp, n->rdx);
bc_num_init(&digit, len);
bc_num_init(&frac_len, BC_NUM_INT(n));
bc_num_one(&frac_len);
bc_num_createCopy(&intp, n);
bc_num_truncate(&intp, intp.rdx);
s = bc_num_sub(n, &intp, &fracp, 0);
if (s) goto err;
while (intp.len) {
s = bc_num_divmod(&intp, base, &intp, &digit, 0);
if (s) goto err;
s = bc_num_ulong(&digit, &dig);
if (s) goto err;
bc_vec_push(&stack, &dig);
}
for (i = 0; i < stack.len; ++i) {
ptr = bc_vec_item_rev(&stack, i);
print(*ptr, len, 0);
}
if (!n->rdx) goto err;
for (radix = 1; frac_len.len <= n->rdx; radix = 0) {
s = bc_num_mul(&fracp, base, &fracp, n->rdx);
if (s) goto err;
s = bc_num_ulong(&fracp, &dig);
if (s) goto err;
bc_num_ulong2num(&intp, dig);
s = bc_num_sub(&fracp, &intp, &fracp, 0);
if (s) goto err;
print(dig, len, radix);
s = bc_num_mul(&frac_len, base, &frac_len, 0);
if (s) goto err;
}
err:
bc_num_free(&frac_len);
bc_num_free(&digit);
bc_num_free(&fracp);
bc_num_free(&intp);
bc_vec_free(&stack);
return s;
}
static BcStatus bc_num_printBase(BcNum *n, BcNum *base, size_t base_t) {
BcStatus s;
size_t width;
BcNumDigitOp print;
int neg = n->neg;
if (neg) putchar('-');
TT.nchars += neg;
n->neg = 0;
if (base_t <= 16) {
width = 1;
print = bc_num_printHex;
} else {
width = bc_num_log10(base_t - 1) - 1;
print = bc_num_printDigits;
}
s = bc_num_printNum(n, base, width, print);
n->neg = neg;
return s;
}
void bc_num_setup(BcNum *n, signed char *num, size_t cap) {
n->num = num;
n->cap = cap;
n->rdx = n->len = 0;
n->neg = 0;
}
void bc_num_init(BcNum *n, size_t req) {
req = req >= BC_NUM_DEF_SIZE ? req : BC_NUM_DEF_SIZE;
bc_num_setup(n, xmalloc(req), req);
}
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;
}
}
void bc_num_free(void *num) {
free(((BcNum*) num)->num);
}
void bc_num_copy(BcNum *d, BcNum *s) {
if (d == s) return;
bc_num_expand(d, s->len);
d->len = s->len;
d->neg = s->neg;
d->rdx = s->rdx;
memcpy(d->num, s->num, d->len);
}
void bc_num_createCopy(BcNum *d, BcNum *s) {
bc_num_init(d, s->len);
bc_num_copy(d, s);
}
void bc_num_createFromUlong(BcNum *n, unsigned long val) {
bc_num_init(n, BC_NUM_LONG_LOG10);
bc_num_ulong2num(n, val);
}
BcStatus bc_num_parse(BcNum *n, char *val,
BcNum *base, size_t base_t, int letter)
{
BcStatus s = BC_STATUS_SUCCESS;
if (letter) bc_num_ulong2num(n, bc_num_parseChar(val[0], 'Z'+11));
else if (base_t == 10) {
size_t len, i;
char *ptr;
int zero = 1;
while (*val == '0') val++;
len = strlen(val);
if (len) {
for (i = 0; zero && i < len; ++i) zero = (val[i] == '0') || val[i] == '.';
bc_num_expand(n, len);
}
ptr = strchr(val, '.');
n->rdx = ptr ? (val + len) - (ptr + 1) : 0;
if (!zero) {
for (i = len - 1; i < len; ++n->len, --i) {
char c = val[i];
if (c == '.') n->len -= 1;
else {
if (isupper(c)) c = '9';
n->num[n->len] = c - '0';
}
}
}
} else s = bc_num_parseBase(n, val, base, base_t);
return s;
}
BcStatus bc_num_ulong(BcNum *n, unsigned long *result) {
size_t i;
unsigned long r;
*result = 0;
if (n->neg) return bc_vm_err(BC_ERROR_MATH_NEGATIVE);
for (r = 0, i = n->len; i > n->rdx;) {
unsigned long prev = r * 10;
if (prev == SIZE_MAX || prev / 10 != r)
return bc_vm_err(BC_ERROR_MATH_OVERFLOW);
r = prev + ((uchar) n->num[--i]);
if (r == SIZE_MAX || r < prev) return bc_vm_err(BC_ERROR_MATH_OVERFLOW);
}
*result = r;
return BC_STATUS_SUCCESS;
}
void bc_num_ulong2num(BcNum *n, unsigned long val) {
size_t len;
signed char *ptr;
unsigned long i;
bc_num_setToZero(n, 0);
if (!val) return;
len = bc_num_log10(ULONG_MAX);
bc_num_expand(n, len);
for (ptr = n->num, i = 0; val; ++i, ++n->len, val /= 10) ptr[i] = val % 10;
}
size_t bc_num_addReq(BcNum *a, BcNum *b, size_t scale) {
return maxof(a->rdx, b->rdx) + maxof(BC_NUM_INT(a), BC_NUM_INT(b)) + 1;
}
size_t bc_num_mulReq(BcNum *a, BcNum *b, size_t scale) {
return BC_NUM_INT(a) + BC_NUM_INT(b) + maxof(scale, a->rdx + b->rdx) + 1;
}
size_t bc_num_powReq(BcNum *a, BcNum *b, size_t scale) {
return a->len + b->len + 1;
}
BcStatus bc_num_add(BcNum *a, BcNum *b, BcNum *c, size_t scale) {
BcNumBinaryOp op = (!a->neg == !b->neg) ? bc_num_a : bc_num_s;
return bc_num_binary(a, b, c, 0, op, bc_num_addReq(a, b, scale));
}
BcStatus bc_num_sub(BcNum *a, BcNum *b, BcNum *c, size_t scale) {
BcNumBinaryOp op = (!a->neg == !b->neg) ? bc_num_s : bc_num_a;
return bc_num_binary(a, b, c, 1, op, bc_num_addReq(a, b, scale));
}
BcStatus bc_num_mul(BcNum *a, BcNum *b, BcNum *c, size_t scale) {
return bc_num_binary(a, b, c, scale, bc_num_m, bc_num_mulReq(a, b, scale));
}
BcStatus bc_num_div(BcNum *a, BcNum *b, BcNum *c, size_t scale) {
return bc_num_binary(a, b, c, scale, bc_num_d, bc_num_mulReq(a, b, scale));
}
BcStatus bc_num_mod(BcNum *a, BcNum *b, BcNum *c, size_t scale) {
return bc_num_binary(a, b, c, scale, bc_num_rem, bc_num_mulReq(a, b, scale));
}
BcStatus bc_num_pow(BcNum *a, BcNum *b, BcNum *c, size_t scale) {
return bc_num_binary(a, b, c, scale, bc_num_p, a->len + b->len + 1);
}
BcStatus bc_num_sqrt(BcNum *a, BcNum *b, size_t scale) {
BcStatus s = BC_STATUS_SUCCESS;
BcNum num1, num2, half, f, fprime, *x0, *x1, *temp;
size_t pow, len, digs, digs1, resrdx, times = 0;
ssize_t cmp = 1, cmp1 = SSIZE_MAX, cmp2 = SSIZE_MAX;
signed char half_digs[2];
bc_num_init(b, maxof(scale, a->rdx) + ((BC_NUM_INT(a) + 1) >> 1) + 1);
if (!a->len) {
bc_num_setToZero(b, scale);
return BC_STATUS_SUCCESS;
}
if (a->neg) return bc_vm_err(BC_ERROR_MATH_NEGATIVE);
if (BC_NUM_ONE(a)) {
bc_num_one(b);
bc_num_extend(b, scale);
return BC_STATUS_SUCCESS;
}
scale = maxof(scale, a->rdx) + 1;
len = a->len + scale;
bc_num_init(&num1, len);
bc_num_init(&num2, len);
bc_num_setup(&half, half_digs, sizeof(half_digs));
bc_num_one(&half);
half.num[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 (!TT.sig && (cmp || digs < len)) {
s = bc_num_div(a, x0, &f, resrdx);
if (s) goto err;
s = bc_num_add(x0, &f, &fprime, resrdx);
if (s) goto err;
s = bc_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;
}
if (TT.sig) {
s = BC_STATUS_SIGNAL;
goto err;
}
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 s;
}
BcStatus bc_num_divmod(BcNum *a, BcNum *b, BcNum *c, BcNum *d, size_t scale) {
BcStatus s;
BcNum num2, *ptr_a;
int init = 0;
size_t ts = maxof(scale + b->rdx, a->rdx), len = bc_num_mulReq(a, b, ts);
if (c == a) {
memcpy(&num2, c, sizeof(BcNum));
ptr_a = &num2;
bc_num_init(c, len);
init = 1;
}
else {
ptr_a = a;
bc_num_expand(c, len);
}
s = bc_num_r(ptr_a, b, c, d, scale, ts);
if (init) bc_num_free(&num2);
return s;
}
int bc_id_cmp(struct str_len *e1, struct str_len *e2) {
return strcmp(e1->str, e2->str);
}
void bc_id_free(void *id) {
free(((struct str_len *)id)->str);
}
void bc_string_free(void *string) {
free(*((char**) string));
}
BcStatus bc_func_insert(BcFunc *f, char *name, BcType type, size_t line) {
struct str_len a;
size_t i;
for (i = 0; i < f->autos.len; ++i) {
struct str_len *id = bc_vec_item(&f->autos, i);
if (!strcmp(name, id->str) && type == (BcType) id->len)
return bc_vm_error(BC_ERROR_PARSE_DUP_LOCAL, line, name);
}
a.len = type;
a.str = name;
bc_vec_push(&f->autos, &a);
return BC_STATUS_SUCCESS;
}
void bc_func_init(BcFunc *f, char *name) {
bc_vec_init(&f->code, sizeof(uchar), NULL);
bc_vec_init(&f->strs, sizeof(char*), bc_string_free);
bc_vec_init(&f->consts, sizeof(char*), bc_string_free);
bc_vec_init(&f->autos, sizeof(struct str_len), bc_id_free);
bc_vec_init(&f->labels, sizeof(size_t), NULL);
f->nparams = 0;
f->voidfn = 0;
f->name = name;
}
void bc_func_reset(BcFunc *f) {
bc_vec_npop(&f->code, f->code.len);
bc_vec_npop(&f->strs, f->strs.len);
bc_vec_npop(&f->consts, f->consts.len);
bc_vec_npop(&f->autos, f->autos.len);
bc_vec_npop(&f->labels, f->labels.len);
f->nparams = 0;
f->voidfn = 0;
}
void bc_func_free(void *func) {
BcFunc *f = (BcFunc*) func;