/*	$OpenBSD: bcode.c,v 1.40 2009/10/27 23:59:37 deraadt Exp $	*/

/*
 * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#include <ssl/ssl.h>
#include <err.h>
#include <limits.h>
#include <signal.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "extern.h"

BIGNUM		zero;

/* #define	DEBUGGING */

#define MAX_ARRAY_INDEX		2048
#define READSTACK_SIZE		8

#define NO_ELSE			-2	/* -1 is EOF */
#define REG_ARRAY_SIZE_SMALL	(UCHAR_MAX + 1)
#define REG_ARRAY_SIZE_BIG	(UCHAR_MAX + 1 + USHRT_MAX + 1)

struct bmachine {
	struct stack		stack;
	u_int			scale;
	u_int			obase;
	u_int			ibase;
	size_t			readsp;
	bool			extended_regs;
	size_t			reg_array_size;
	struct stack		*reg;
	volatile sig_atomic_t	interrupted;
	struct source		*readstack;
	size_t			readstack_sz;
};

static struct bmachine	bmachine;
static void sighandler(int);

static __inline int	readch(void);
static __inline void	unreadch(void);
static __inline char	*readline(void);
static __inline void	src_free(void);

static __inline u_int	max(u_int, u_int);
static u_long		get_ulong(struct number *);

static __inline void	push_number(struct number *);
static __inline void	push_string(char *);
static __inline void	push(struct value *);
static __inline struct value *tos(void);
static __inline struct number	*pop_number(void);
static __inline char	*pop_string(void);
static __inline void	clear_stack(void);
static __inline void	print_tos(void);
static void		pop_print(void);
static void		pop_printn(void);
static __inline void	print_stack(void);
static __inline void	dup(void);
static void		swap(void);
static void		drop(void);

static void		get_scale(void);
static void		set_scale(void);
static void		get_obase(void);
static void		set_obase(void);
static void		get_ibase(void);
static void		set_ibase(void);
static void		stackdepth(void);
static void		push_scale(void);
static u_int		count_digits(const struct number *);
static void		num_digits(void);
static void		to_ascii(void);
static void		push_line(void);
static void		comment(void);
static void		bexec(char *);
static void		badd(void);
static void		bsub(void);
static void		bmul(void);
static void		bdiv(void);
static void		bmod(void);
static void		bdivmod(void);
static void		bexp(void);
static bool		bsqrt_stop(const BIGNUM *, const BIGNUM *, u_int *);
static void		bsqrt(void);
static void		not(void);
static void		equal_numbers(void);
static void		less_numbers(void);
static void		lesseq_numbers(void);
static void		equal(void);
static void		not_equal(void);
static void		less(void);
static void		not_less(void);
static void		greater(void);
static void		not_greater(void);
static void		not_compare(void);
static bool		compare_numbers(enum bcode_compare, struct number *,
			    struct number *);
static void		compare(enum bcode_compare);
static int		readreg(void);
static void		load(void);
static void		store(void);
static void		load_stack(void);
static void		store_stack(void);
static void		load_array(void);
static void		store_array(void);
static void		nop(void);
static void		quit(void);
static void		quitN(void);
static void		skipN(void);
static void		skip_until_mark(void);
static void		parse_number(void);
static void		unknown(void);
static void		eval_string(char *);
static void		eval_line(void);
static void		eval_tos(void);


typedef void		(*opcode_function)(void);

struct jump_entry {
	u_char		ch;
	opcode_function	f;
};

static opcode_function jump_table[UCHAR_MAX];

static const struct jump_entry jump_table_data[] = {
	{ ' ',	nop		},
	{ '!',	not_compare	},
	{ '#',	comment		},
	{ '%',	bmod		},
	{ '(',	less_numbers	},
	{ '*',	bmul		},
	{ '+',	badd		},
	{ '-',	bsub		},
	{ '.',	parse_number	},
	{ '/',	bdiv		},
	{ '0',	parse_number	},
	{ '1',	parse_number	},
	{ '2',	parse_number	},
	{ '3',	parse_number	},
	{ '4',	parse_number	},
	{ '5',	parse_number	},
	{ '6',	parse_number	},
	{ '7',	parse_number	},
	{ '8',	parse_number	},
	{ '9',	parse_number	},
	{ ':',	store_array	},
	{ ';',	load_array	},
	{ '<',	less		},
	{ '=',	equal		},
	{ '>',	greater		},
	{ '?',	eval_line	},
	{ 'A',	parse_number	},
	{ 'B',	parse_number	},
	{ 'C',	parse_number	},
	{ 'D',	parse_number	},
	{ 'E',	parse_number	},
	{ 'F',	parse_number	},
	{ 'G',	equal_numbers	},
	{ 'I',	get_ibase	},
	{ 'J',	skipN		},
	{ 'K',	get_scale	},
	{ 'L',	load_stack	},
	{ 'M',	nop		},
	{ 'N',	not		},
	{ 'O',	get_obase	},
	{ 'P',	pop_print	},
	{ 'Q',	quitN		},
	{ 'R',	drop		},
	{ 'S',	store_stack	},
	{ 'X',	push_scale	},
	{ 'Z',	num_digits	},
	{ '[',	push_line	},
	{ '\f',	nop		},
	{ '\n',	nop		},
	{ '\r',	nop		},
	{ '\t',	nop		},
	{ '^',	bexp		},
	{ '_',	parse_number	},
	{ 'a',	to_ascii	},
	{ 'c',	clear_stack	},
	{ 'd',	dup		},
	{ 'f',	print_stack	},
	{ 'i',	set_ibase	},
	{ 'k',	set_scale	},
	{ 'l',	load		},
	{ 'n',	pop_printn	},
	{ 'o',	set_obase	},
	{ 'p',	print_tos	},
	{ 'q',	quit		},
	{ 'r',	swap		},
	{ 's',	store		},
	{ 'v',	bsqrt		},
	{ 'x',	eval_tos	},
	{ 'z',	stackdepth	},
	{ '{',	lesseq_numbers	},
	{ '~',	bdivmod		}
};

#define JUMP_TABLE_DATA_SIZE \
	(sizeof(jump_table_data)/sizeof(jump_table_data[0]))

/* ARGSUSED */
static void
sighandler(int ignored)
{
	bmachine.interrupted = true;
}

void
init_bmachine(bool extended_registers)
{
	int i;

	bmachine.extended_regs = extended_registers;
	bmachine.reg_array_size = bmachine.extended_regs ?
	    REG_ARRAY_SIZE_BIG : REG_ARRAY_SIZE_SMALL;

	bmachine.reg = calloc(bmachine.reg_array_size,
	    sizeof(bmachine.reg[0]));
	if (bmachine.reg == NULL)
		err(1, NULL);

	for (i = 0; i < UCHAR_MAX; i++)
		jump_table[i] = unknown;
	for (i = 0; i < JUMP_TABLE_DATA_SIZE; i++)
		jump_table[jump_table_data[i].ch] = jump_table_data[i].f;

	stack_init(&bmachine.stack);

	for (i = 0; i < bmachine.reg_array_size; i++)
		stack_init(&bmachine.reg[i]);

	bmachine.readstack_sz = READSTACK_SIZE;
	bmachine.readstack = calloc(sizeof(struct source),
	    bmachine.readstack_sz);
	if (bmachine.readstack == NULL)
		err(1, NULL);
	bmachine.obase = bmachine.ibase = 10;
	BN_init(&zero);
	bn_check(BN_zero(&zero));
	(void)signal(SIGINT, sighandler);
}

/* Reset the things needed before processing a (new) file */
void
reset_bmachine(struct source *src)
{
	bmachine.readsp = 0;
	bmachine.readstack[0] = *src;
}

static __inline int
readch(void)
{
	struct source *src = &bmachine.readstack[bmachine.readsp];

	return src->vtable->readchar(src);
}

static __inline void
unreadch(void)
{
	struct source *src = &bmachine.readstack[bmachine.readsp];

	src->vtable->unreadchar(src);
}

static __inline char *
readline(void)
{
	struct source *src = &bmachine.readstack[bmachine.readsp];

	return src->vtable->readline(src);
}

static __inline void
src_free(void)
{
	struct source *src = &bmachine.readstack[bmachine.readsp];

	src->vtable->free(src);
}

#ifdef DEBUGGING
void
pn(const char *str, const struct number *n)
{
	char *p = BN_bn2dec(n->number);
	if (p == NULL)
		err(1, "BN_bn2dec failed");
	(void)fputs(str, stderr);
	(void)fprintf(stderr, " %s (%u)\n" , p, n->scale);
	OPENSSL_free(p);
}

void
pbn(const char *str, const BIGNUM *n)
{
	char *p = BN_bn2dec(n);
	if (p == NULL)
		err(1, "BN_bn2dec failed");
	(void)fputs(str, stderr);
	(void)fprintf(stderr, " %s\n", p);
	OPENSSL_free(p);
}

#endif

static __inline u_int
max(u_int a, u_int b)
{
	return a > b ? a : b;
}

static unsigned long factors[] = {
	0, 10, 100, 1000, 10000, 100000, 1000000, 10000000,
	100000000, 1000000000
};

void
scale_number(BIGNUM *n, int s)
{
	int abs_scale;

	if (s == 0)
		return;

	abs_scale = s > 0 ? s : -s;

	if (abs_scale < sizeof(factors)/sizeof(factors[0])) {
		if (s > 0)
			bn_check(BN_mul_word(n, factors[abs_scale]));
		else
			(void)BN_div_word(n, factors[abs_scale]);
	} else {
		BIGNUM *a, *p;
		BN_CTX *ctx;

		a = BN_new();
		bn_checkp(a);
		p = BN_new();
		bn_checkp(p);
		ctx = BN_CTX_new();
		bn_checkp(ctx);

		bn_check(BN_set_word(a, 10));
		bn_check(BN_set_word(p, abs_scale));
		bn_check(BN_exp(a, a, p, ctx));
		if (s > 0)
			bn_check(BN_mul(n, n, a, ctx));
		else
			bn_check(BN_div(n, NULL, n, a, ctx));
		BN_CTX_free(ctx);
		BN_free(a);
		BN_free(p);
	}
}

void
split_number(const struct number *n, BIGNUM *i, BIGNUM *f)
{
	u_long rem;

	bn_checkp(BN_copy(i, n->number));

	if (n->scale == 0 && f != NULL)
		bn_check(BN_zero(f));
	else if (n->scale < sizeof(factors)/sizeof(factors[0])) {
		rem = BN_div_word(i, factors[n->scale]);
		if (f != NULL)
			bn_check(BN_set_word(f, rem));
	} else {
		BIGNUM *a, *p;
		BN_CTX *ctx;

		a = BN_new();
		bn_checkp(a);
		p = BN_new();
		bn_checkp(p);
		ctx = BN_CTX_new();
		bn_checkp(ctx);

		bn_check(BN_set_word(a, 10));
		bn_check(BN_set_word(p, n->scale));
		bn_check(BN_exp(a, a, p, ctx));
		bn_check(BN_div(i, f, n->number, a, ctx));
		BN_CTX_free(ctx);
		BN_free(a);
		BN_free(p);
	}
}

__inline void
normalize(struct number *n, u_int s)
{
	scale_number(n->number, s - n->scale);
	n->scale = s;
}

static u_long
get_ulong(struct number *n)
{
	normalize(n, 0);
	return BN_get_word(n->number);
}

void
negate(struct number *n)
{
	bn_check(BN_sub(n->number, &zero, n->number));
}

static __inline void
push_number(struct number *n)
{
	stack_pushnumber(&bmachine.stack, n);
}

static __inline void
push_string(char *string)
{
	stack_pushstring(&bmachine.stack, string);
}

static __inline void
push(struct value *v)
{
	stack_push(&bmachine.stack, v);
}

static __inline struct value *
tos(void)
{
	return stack_tos(&bmachine.stack);
}

static __inline struct value *
pop(void)
{
	return stack_pop(&bmachine.stack);
}

static __inline struct number *
pop_number(void)
{
	return stack_popnumber(&bmachine.stack);
}

static __inline char *
pop_string(void)
{
	return stack_popstring(&bmachine.stack);
}

static __inline void
clear_stack(void)
{
	stack_clear(&bmachine.stack);
}

static __inline void
print_stack(void)
{
	stack_print(stdout, &bmachine.stack, "", bmachine.obase);
}

static __inline void
print_tos(void)
{
	struct value *value = tos();
	if (value != NULL) {
		print_value(stdout, value, "", bmachine.obase);
		(void)putchar('\n');
	}
	else
		warnx("stack empty");
}

static void
pop_print(void)
{
	struct value *value = pop();

	if (value != NULL) {
		switch (value->type) {
		case BCODE_NONE:
			break;
		case BCODE_NUMBER:
			normalize(value->u.num, 0);
			print_ascii(stdout, value->u.num);
			(void)fflush(stdout);
			break;
		case BCODE_STRING:
			(void)fputs(value->u.string, stdout);
			(void)fflush(stdout);
			break;
		}
		stack_free_value(value);
	}
}

static void
pop_printn(void)
{
	struct value *value = pop();

	if (value != NULL) {
		print_value(stdout, value, "", bmachine.obase);
		(void)fflush(stdout);
		stack_free_value(value);
	}
}

static __inline void
dup(void)
{
	stack_dup(&bmachine.stack);
}

static void
swap(void)
{
	stack_swap(&bmachine.stack);
}

static void
drop(void)
{
	struct value *v = pop();
	if (v != NULL)
		stack_free_value(v);
}

static void
get_scale(void)
{
	struct number	*n;

	n = new_number();
	bn_check(BN_set_word(n->number, bmachine.scale));
	push_number(n);
}

static void
set_scale(void)
{
	struct number	*n;
	u_long		scale;

	n = pop_number();
	if (n != NULL) {
		if (BN_cmp(n->number, &zero) < 0)
			warnx("scale must be a nonnegative number");
		else {
			scale = get_ulong(n);
			if (scale != BN_MASK2 && scale <= UINT_MAX)
				bmachine.scale = (u_int)scale;
			else
				warnx("scale too large");
			}
		free_number(n);
	}
}

static void
get_obase(void)
{
	struct number	*n;

	n = new_number();
	bn_check(BN_set_word(n->number, bmachine.obase));
	push_number(n);
}

static void
set_obase(void)
{
	struct number	*n;
	u_long		base;

	n = pop_number();
	if (n != NULL) {
		base = get_ulong(n);
		if (base != BN_MASK2 && base > 1 && base <= UINT_MAX)
			bmachine.obase = (u_int)base;
		else
			warnx("output base must be a number greater than 1");
		free_number(n);
	}
}

static void
get_ibase(void)
{
	struct number *n;

	n = new_number();
	bn_check(BN_set_word(n->number, bmachine.ibase));
	push_number(n);
}

static void
set_ibase(void)
{
	struct number	*n;
	u_long		base;

	n = pop_number();
	if (n != NULL) {
		base = get_ulong(n);
		if (base != BN_MASK2 && 2 <= base && base <= 16)
			bmachine.ibase = (u_int)base;
		else
			warnx("input base must be a number between 2 and 16 "
			    "(inclusive)");
		free_number(n);
	}
}

static void
stackdepth(void)
{
	size_t i;
	struct number *n;

	i = stack_size(&bmachine.stack);
	n = new_number();
	bn_check(BN_set_word(n->number, i));
	push_number(n);
}

static void
push_scale(void)
{
	struct value	*value;
	u_int		scale = 0;
	struct number	*n;


	value = pop();
	if (value != NULL) {
		switch (value->type) {
		case BCODE_NONE:
			return;
		case BCODE_NUMBER:
			scale = value->u.num->scale;
			break;
		case BCODE_STRING:
			break;
		}
		stack_free_value(value);
		n = new_number();
		bn_check(BN_set_word(n->number, scale));
		push_number(n);
	}
}

static u_int
count_digits(const struct number *n)
{
	struct number	*int_part, *fract_part;
	u_int		i;

	if (BN_is_zero(n->number))
		return 1;

	int_part = new_number();
	fract_part = new_number();
	fract_part->scale = n->scale;
	split_number(n, int_part->number, fract_part->number);

	i = 0;
	while (!BN_is_zero(int_part->number)) {
		(void)BN_div_word(int_part->number, 10);
		i++;
	}
	free_number(int_part);
	free_number(fract_part);
	return i + n->scale;
}

static void
num_digits(void)
{
	struct value	*value;
	size_t		digits;
	struct number	*n = NULL;

	value = pop();
	if (value != NULL) {
		switch (value->type) {
		case BCODE_NONE:
			return;
		case BCODE_NUMBER:
			digits = count_digits(value->u.num);
			n = new_number();
			bn_check(BN_set_word(n->number, digits));
			break;
		case BCODE_STRING:
			digits = strlen(value->u.string);
			n = new_number();
			bn_check(BN_set_word(n->number, digits));
			break;
		}
		stack_free_value(value);
		push_number(n);
	}
}

static void
to_ascii(void)
{
	char		str[2];
	struct value	*value;
	struct number	*n;

	value = pop();
	if (value != NULL) {
		str[1] = '\0';
		switch (value->type) {
		case BCODE_NONE:
			return;
		case BCODE_NUMBER:
			n = value->u.num;
			normalize(n, 0);
			if (BN_num_bits(n->number) > 8)
				bn_check(BN_mask_bits(n->number, 8));
			str[0] = (char)BN_get_word(n->number);
			break;
		case BCODE_STRING:
			str[0] = value->u.string[0];
			break;
		}
		stack_free_value(value);
		push_string(bstrdup(str));
	}
}

static int
readreg(void)
{
	int idx, ch1, ch2;

	idx = readch();
	if (idx == 0xff && bmachine.extended_regs) {
		ch1 = readch();
		ch2 = readch();
		if (ch1 == EOF || ch2 == EOF) {
			warnx("unexpected eof");
			idx = -1;
		} else
			idx = (ch1 << 8) + ch2 + UCHAR_MAX + 1;
	}
	if (idx < 0 || idx >= bmachine.reg_array_size) {
		warnx("internal error: reg num = %d", idx);
		idx = -1;
	}
	return idx;
}

static void
load(void)
{
	int		idx;
	struct value	*v, copy;
	struct number	*n;

	idx = readreg();
	if (idx >= 0) {
		v = stack_tos(&bmachine.reg[idx]);
		if (v == NULL) {
			n = new_number();
			bn_check(BN_zero(n->number));
			push_number(n);
		} else
			push(stack_dup_value(v, &copy));
	}
}

static void
store(void)
{
	int		idx;
	struct value	*val;

	idx = readreg();
	if (idx >= 0) {
		val = pop();
		if (val == NULL) {
			return;
		}
		stack_set_tos(&bmachine.reg[idx], val);
	}
}

static void
load_stack(void)
{
	int		idx;
	struct stack	*stack;
	struct value	*value;

	idx = readreg();
	if (idx >= 0) {
		stack = &bmachine.reg[idx];
		value = NULL;
		if (stack_size(stack) > 0) {
			value = stack_pop(stack);
		}
		if (value != NULL)
			push(value);
		else
			warnx("stack register '%c' (0%o) is empty",
			    idx, idx);
	}
}

static void
store_stack(void)
{
	int		idx;
	struct value	*value;

	idx = readreg();
	if (idx >= 0) {
		value = pop();
		if (value == NULL)
			return;
		stack_push(&bmachine.reg[idx], value);
	}
}

static void
load_array(void)
{
	int			reg;
	struct number		*inumber, *n;
	u_long			idx;
	struct stack		*stack;
	struct value		*v, copy;

	reg = readreg();
	if (reg >= 0) {
		inumber = pop_number();
		if (inumber == NULL)
			return;
		idx = get_ulong(inumber);
		if (BN_cmp(inumber->number, &zero) < 0)
			warnx("negative idx");
		else if (idx == BN_MASK2 || idx > MAX_ARRAY_INDEX)
			warnx("idx too big");
		else {
			stack = &bmachine.reg[reg];
			v = frame_retrieve(stack, idx);
			if (v == NULL || v->type == BCODE_NONE) {
				n = new_number();
				bn_check(BN_zero(n->number));
				push_number(n);
			}
			else
				push(stack_dup_value(v, &copy));
		}
		free_number(inumber);
	}
}

static void
store_array(void)
{
	int			reg;
	struct number		*inumber;
	u_long			idx;
	struct value		*value;
	struct stack		*stack;

	reg = readreg();
	if (reg >= 0) {
		inumber = pop_number();
		if (inumber == NULL)
			return;
		value = pop();
		if (value == NULL) {
			free_number(inumber);
			return;
		}
		idx = get_ulong(inumber);
		if (BN_cmp(inumber->number, &zero) < 0) {
			warnx("negative idx");
			stack_free_value(value);
		} else if (idx == BN_MASK2 || idx > MAX_ARRAY_INDEX) {
			warnx("idx too big");
			stack_free_value(value);
		} else {
			stack = &bmachine.reg[reg];
			frame_assign(stack, idx, value);
		}
		free_number(inumber);
	}
}

static void
push_line(void)
{
	push_string(read_string(&bmachine.readstack[bmachine.readsp]));
}

static void
comment(void)
{
	free(readline());
}

static void
bexec(char *line)
{
	(void)system(line);
	free(line);
}

static void
badd(void)
{
	struct number	*a, *b;
	struct number	*r;

	a = pop_number();
	if (a == NULL) {
		return;
	}
	b = pop_number();
	if (b == NULL) {
		push_number(a);
		return;
	}

	r = new_number();
	r->scale = max(a->scale, b->scale);
	if (r->scale > a->scale)
		normalize(a, r->scale);
	else if (r->scale > b->scale)
		normalize(b, r->scale);
	bn_check(BN_add(r->number, a->number, b->number));
	push_number(r);
	free_number(a);
	free_number(b);
}

static void
bsub(void)
{
	struct number	*a, *b;
	struct number	*r;

	a = pop_number();
	if (a == NULL) {
		return;
	}
	b = pop_number();
	if (b == NULL) {
		push_number(a);
		return;
	}

	r = new_number();

	r->scale = max(a->scale, b->scale);
	if (r->scale > a->scale)
		normalize(a, r->scale);
	else if (r->scale > b->scale)
		normalize(b, r->scale);
	bn_check(BN_sub(r->number, b->number, a->number));
	push_number(r);
	free_number(a);
	free_number(b);
}

void
bmul_number(struct number *r, struct number *a, struct number *b)
{
	BN_CTX		*ctx;

	/* Create copies of the scales, since r might be equal to a or b */
	u_int ascale = a->scale;
	u_int bscale = b->scale;
	u_int rscale = ascale + bscale;

	ctx = BN_CTX_new();
	bn_checkp(ctx);
	bn_check(BN_mul(r->number, a->number, b->number, ctx));
	BN_CTX_free(ctx);

	if (rscale > bmachine.scale && rscale > ascale && rscale > bscale) {
		r->scale = rscale;
		normalize(r, max(bmachine.scale, max(ascale, bscale)));
	} else
		r->scale = rscale;
}

static void
bmul(void)
{
	struct number	*a, *b;
	struct number	*r;

	a = pop_number();
	if (a == NULL) {
		return;
	}
	b = pop_number();
	if (b == NULL) {
		push_number(a);
		return;
	}

	r = new_number();
	bmul_number(r, a, b);

	push_number(r);
	free_number(a);
	free_number(b);
}

static void
bdiv(void)
{
	struct number	*a, *b;
	struct number	*r;
	u_int		scale;
	BN_CTX		*ctx;

	a = pop_number();
	if (a == NULL) {
		return;
	}
	b = pop_number();
	if (b == NULL) {
		push_number(a);
		return;
	}

	r = new_number();
	r->scale = bmachine.scale;
	scale = max(a->scale, b->scale);

	if (BN_is_zero(a->number))
		warnx("divide by zero");
	else {
		normalize(a, scale);
		normalize(b, scale + r->scale);

		ctx = BN_CTX_new();
		bn_checkp(ctx);
		bn_check(BN_div(r->number, NULL, b->number, a->number, ctx));
		BN_CTX_free(ctx);
	}
	push_number(r);
	free_number(a);
	free_number(b);
}

static void
bmod(void)
{
	struct number	*a, *b;
	struct number	*r;
	u_int		scale;
	BN_CTX		*ctx;

	a = pop_number();
	if (a == NULL) {
		return;
	}
	b = pop_number();
	if (b == NULL) {
		push_number(a);
		return;
	}

	r = new_number();
	scale = max(a->scale, b->scale);
	r->scale = max(b->scale, a->scale + bmachine.scale);

	if (BN_is_zero(a->number))
		warnx("remainder by zero");
	else {
		normalize(a, scale);
		normalize(b, scale + bmachine.scale);

		ctx = BN_CTX_new();
		bn_checkp(ctx);
		bn_check(BN_mod(r->number, b->number, a->number, ctx));
		BN_CTX_free(ctx);
	}
	push_number(r);
	free_number(a);
	free_number(b);
}

static void
bdivmod(void)
{
	struct number	*a, *b;
	struct number	*rdiv, *rmod;
	u_int		scale;
	BN_CTX		*ctx;

	a = pop_number();
	if (a == NULL) {
		return;
	}
	b = pop_number();
	if (b == NULL) {
		push_number(a);
		return;
	}

	rdiv = new_number();
	rmod = new_number();
	rdiv->scale = bmachine.scale;
	rmod->scale = max(b->scale, a->scale + bmachine.scale);
	scale = max(a->scale, b->scale);

	if (BN_is_zero(a->number))
		warnx("divide by zero");
	else {
		normalize(a, scale);
		normalize(b, scale + bmachine.scale);

		ctx = BN_CTX_new();
		bn_checkp(ctx);
		bn_check(BN_div(rdiv->number, rmod->number,
		    b->number, a->number, ctx));
		BN_CTX_free(ctx);
	}
	push_number(rdiv);
	push_number(rmod);
	free_number(a);
	free_number(b);
}

static void
bexp(void)
{
	struct number	*a, *p;
	struct number	*r;
	bool		neg;
	u_int		scale;

	p = pop_number();
	if (p == NULL) {
		return;
	}
	a = pop_number();
	if (a == NULL) {
		push_number(p);
		return;
	}

	if (p->scale != 0)
		warnx("Runtime warning: non-zero scale in exponent");
	normalize(p, 0);

	neg = false;
	if (BN_cmp(p->number, &zero) < 0) {
		neg = true;
		negate(p);
		scale = bmachine.scale;
	} else {
		/* Posix bc says min(a.scale * b, max(a.scale, scale) */
		u_long	b;
		u_int	m;

		b = BN_get_word(p->number);
		m = max(a->scale, bmachine.scale);
		scale = a->scale * (u_int)b;
		if (scale > m || (a->scale > 0 && (b == BN_MASK2 ||
		    b > UINT_MAX)))
			scale = m;
	}

	if (BN_is_zero(p->number)) {
		r = new_number();
		bn_check(BN_one(r->number));
		normalize(r, scale);
	} else {
		while (!BN_is_bit_set(p->number, 0)) {
			bmul_number(a, a, a);
			bn_check(BN_rshift1(p->number, p->number));
		}

		r = dup_number(a);
		normalize(r, scale);
		bn_check(BN_rshift1(p->number, p->number));

		while (!BN_is_zero(p->number)) {
			bmul_number(a, a, a);
			if (BN_is_bit_set(p->number, 0))
				bmul_number(r, r, a);
			bn_check(BN_rshift1(p->number, p->number));
		}

		if (neg) {
			BN_CTX	*ctx;
			BIGNUM	*one;

			one = BN_new();
			bn_checkp(one);
			bn_check(BN_one(one));
			ctx = BN_CTX_new();
			bn_checkp(ctx);
			scale_number(one, r->scale + scale);
			normalize(r, scale);
			bn_check(BN_div(r->number, NULL, one, r->number, ctx));
			BN_free(one);
			BN_CTX_free(ctx);
		} else
			normalize(r, scale);
	}
	push_number(r);
	free_number(a);
	free_number(p);
}

static bool
bsqrt_stop(const BIGNUM *x, const BIGNUM *y, u_int *onecount)
{
	BIGNUM *r;
	bool ret;

	r = BN_new();
	bn_checkp(r);
	bn_check(BN_sub(r, x, y));
	if (BN_is_one(r))
		(*onecount)++;
	ret = BN_is_zero(r);
	BN_free(r);
	return ret || *onecount > 1;
}

static void
bsqrt(void)
{
	struct number	*n;
	struct number	*r;
	BIGNUM		*x, *y;
	u_int		scale, onecount;
	BN_CTX		*ctx;

	onecount = 0;
	n = pop_number();
	if (n == NULL) {
		return;
	}
	if (BN_is_zero(n->number)) {
		r = new_number();
		push_number(r);
	} else if (BN_cmp(n->number, &zero) < 0)
		warnx("square root of negative number");
	else {
		scale = max(bmachine.scale, n->scale);
		normalize(n, 2*scale);
		x = BN_dup(n->number);
		bn_checkp(x);
		bn_check(BN_rshift(x, x, BN_num_bits(x)/2));
		y = BN_new();
		bn_checkp(y);
		ctx = BN_CTX_new();
		bn_checkp(ctx);
		for (;;) {
			bn_checkp(BN_copy(y, x));
			bn_check(BN_div(x, NULL, n->number, x, ctx));
			bn_check(BN_add(x, x, y));
			bn_check(BN_rshift1(x, x));
			if (bsqrt_stop(x, y, &onecount))
				break;
		}
		r = bmalloc(sizeof(*r));
		r->scale = scale;
		r->number = y;
		BN_free(x);
		BN_CTX_free(ctx);
		push_number(r);
	}

	free_number(n);
}

static void
not(void)
{
	struct number	*a;

	a = pop_number();
	if (a == NULL) {
		return;
	}
	a->scale = 0;
	bn_check(BN_set_word(a->number, BN_get_word(a->number) ? 0 : 1));
	push_number(a);
}

static void
equal(void)
{
	compare(BCODE_EQUAL);
}

static void
equal_numbers(void)
{
	struct number *a, *b, *r;

	a = pop_number();
	if (a == NULL) {
		return;
	}
	b = pop_number();
	if (b == NULL) {
		push_number(a);
		return;
	}
	r = new_number();
	bn_check(BN_set_word(r->number,
	    compare_numbers(BCODE_EQUAL, a, b) ? 1 : 0));
	push_number(r);
}

static void
less_numbers(void)
{
	struct number *a, *b, *r;

	a = pop_number();
	if (a == NULL) {
		return;
	}
	b = pop_number();
	if (b == NULL) {
		push_number(a);
		return;
	}
	r = new_number();
	bn_check(BN_set_word(r->number,
	    compare_numbers(BCODE_LESS, a, b) ? 1 : 0));
	push_number(r);
}

static void
lesseq_numbers(void)
{
	struct number *a, *b, *r;

	a = pop_number();
	if (a == NULL) {
		return;
	}
	b = pop_number();
	if (b == NULL) {
		push_number(a);
		return;
	}
	r = new_number();
	bn_check(BN_set_word(r->number,
	    compare_numbers(BCODE_NOT_GREATER, a, b) ? 1 : 0));
	push_number(r);
}

static void
not_equal(void)
{
	compare(BCODE_NOT_EQUAL);
}

static void
less(void)
{
	compare(BCODE_LESS);
}

static void
not_compare(void)
{
	switch (readch()) {
	case '<':
		not_less();
		break;
	case '>':
		not_greater();
		break;
	case '=':
		not_equal();
		break;
	default:
		unreadch();
		bexec(readline());
		break;
	}
}

static void
not_less(void)
{
	compare(BCODE_NOT_LESS);
}

static void
greater(void)
{
	compare(BCODE_GREATER);
}

static void
not_greater(void)
{
	compare(BCODE_NOT_GREATER);
}

static bool
compare_numbers(enum bcode_compare type, struct number *a, struct number *b)
{
	u_int	scale;
	int	cmp;

	scale = max(a->scale, b->scale);

	if (scale > a->scale)
		normalize(a, scale);
	else if (scale > b->scale)
		normalize(b, scale);

	cmp = BN_cmp(a->number, b->number);

	free_number(a);
	free_number(b);

	switch (type) {
	case BCODE_EQUAL:
		return cmp == 0;
	case BCODE_NOT_EQUAL:
		return cmp != 0;
	case BCODE_LESS:
		return cmp < 0;
	case BCODE_NOT_LESS:
		return cmp >= 0;
	case BCODE_GREATER:
		return cmp > 0;
	case BCODE_NOT_GREATER:
		return cmp <= 0;
	}
	return false;
}

static void
compare(enum bcode_compare type)
{
	int		idx, elseidx;
	struct number	*a, *b;
	bool		ok;
	struct value	*v;

	elseidx = NO_ELSE;
	idx = readreg();
	if (readch() == 'e')
		elseidx = readreg();
	else
		unreadch();

	a = pop_number();
	if (a == NULL)
		return;
	b = pop_number();
	if (b == NULL) {
		push_number(a);
		return;
	}

	ok = compare_numbers(type, a, b);

	if (!ok && elseidx != NO_ELSE)
		idx = elseidx;

	if (idx >= 0 && (ok || (!ok && elseidx != NO_ELSE))) {
		v = stack_tos(&bmachine.reg[idx]);
		if (v == NULL)
			warnx("register '%c' (0%o) is empty", idx, idx);
		else {
			switch(v->type) {
			case BCODE_NONE:
				warnx("register '%c' (0%o) is empty", idx, idx);
				break;
			case BCODE_NUMBER:
				warn("eval called with non-string argument");
				break;
			case BCODE_STRING:
				eval_string(bstrdup(v->u.string));
				break;
			}
		}
	}
}


static void
nop(void)
{
}

static void
quit(void)
{
	if (bmachine.readsp < 2)
		exit(0);
	src_free();
	bmachine.readsp--;
	src_free();
	bmachine.readsp--;
}

static void
quitN(void)
{
	struct number	*n;
	u_long		i;

	n = pop_number();
	if (n == NULL)
		return;
	i = get_ulong(n);
	free_number(n);
	if (i == BN_MASK2 || i == 0)
		warnx("Q command requires a number >= 1");
	else if (bmachine.readsp < i)
		warnx("Q command argument exceeded string execution depth");
	else {
		while (i-- > 0) {
			src_free();
			bmachine.readsp--;
		}
	}
}

static void
skipN(void)
{
	struct number	*n;
	u_long		i;

	n = pop_number();
	if (n == NULL)
		return;
	i = get_ulong(n);
	if (i == BN_MASK2)
		warnx("J command requires a number >= 0");
	else if (i > 0 && bmachine.readsp < i)
		warnx("J command argument exceeded string execution depth");
	else {
		while (i-- > 0) {
			src_free();
			bmachine.readsp--;
		}
		skip_until_mark();
	}
}

static void
skip_until_mark(void)
{
	int ch;

	for (;;) {
		ch = readch();
		switch (ch) {
		case 'M':
			return;
		case EOF:
			errx(1, "mark not found");
			return;
		case 'l':
		case 'L':
		case 's':
		case 'S':
		case ':':
		case ';':
		case '<':
		case '>':
		case '=':
			(void)readreg();
			if (readch() == 'e')
				(void)readreg();
			else
				unreadch();
			break;
		case '[':
			free(read_string(&bmachine.readstack[bmachine.readsp]));
			break;
		case '!':
			switch (ch = readch()) {
				case '<':
				case '>':
				case '=':
					(void)readreg();
					if (readch() == 'e')
						(void)readreg();
					else
						unreadch();
					break;
				default:
					free(readline());
					break;
			}
			break;
		default:
			break;
		}
	}
}

static void
parse_number(void)
{
	unreadch();
	push_number(readnumber(&bmachine.readstack[bmachine.readsp],
	    bmachine.ibase));
}

static void
unknown(void)
{
	int ch = bmachine.readstack[bmachine.readsp].lastchar;
	warnx("%c (0%o) is unimplemented", ch, ch);
}

static void
eval_string(char *p)
{
	int ch;

	if (bmachine.readsp > 0) {
		/* Check for tail call. Do not recurse in that case. */
		ch = readch();
		if (ch == EOF) {
			src_free();
			src_setstring(&bmachine.readstack[bmachine.readsp], p);
			return;
		} else
			unreadch();
	}
	if (bmachine.readsp == bmachine.readstack_sz - 1) {
		size_t newsz = bmachine.readstack_sz * 2;
		struct source *stack;
		stack = realloc(bmachine.readstack, newsz *
		    sizeof(struct source));
		if (stack == NULL)
			err(1, "recursion too deep");
		bmachine.readstack_sz = newsz;
		bmachine.readstack = stack;
	}
	src_setstring(&bmachine.readstack[++bmachine.readsp], p);
}

static void
eval_line(void)
{
	/* Always read from stdin */
	struct source	in;
	char		*p;

	clearerr(stdin);
	src_setstream(&in, stdin);
	p = (*in.vtable->readline)(&in);
	eval_string(p);
}

static void
eval_tos(void)
{
	char *p;

	p = pop_string();
	if (p == NULL)
		return;
	eval_string(p);
}

void
eval(void)
{
	int	ch;

	for (;;) {
		ch = readch();
		if (ch == EOF) {
			if (bmachine.readsp == 0)
				return;
			src_free();
			bmachine.readsp--;
			continue;
		}
		if (bmachine.interrupted) {
			if (bmachine.readsp > 0) {
				src_free();
				bmachine.readsp--;
				continue;
			} else
				bmachine.interrupted = false;
		}
#ifdef DEBUGGING
		(void)fprintf(stderr, "# %c\n", ch);
		stack_print(stderr, &bmachine.stack, "* ",
		    bmachine.obase);
		(void)fprintf(stderr, "%zd =>\n", bmachine.readsp);
#endif

		if (0 <= ch && ch < UCHAR_MAX)
			(*jump_table[ch])();
		else
			warnx("internal error: opcode %d", ch);

#ifdef DEBUGGING
		stack_print(stderr, &bmachine.stack, "* ",
		    bmachine.obase);
		(void)fprintf(stderr, "%zd ==\n", bmachine.readsp);
#endif
	}
}