xref: /openbsd-src/usr.bin/dc/bcode.c (revision b725ae7711052a2233e31a66fefb8a752c388d7a) 
1 /*	$OpenBSD: bcode.c,v 1.22 2004/02/11 20:44:31 otto Exp $	*/
2 
3 /*
4  * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net>
5  *
6  * Permission to use, copy, modify, and distribute this software for any
7  * purpose with or without fee is hereby granted, provided that the above
8  * copyright notice and this permission notice appear in all copies.
9  *
10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17  */
18 
19 #ifndef lint
20 static const char rcsid[] = "$OpenBSD: bcode.c,v 1.22 2004/02/11 20:44:31 otto Exp $";
21 #endif /* not lint */
22 
23 #include <ssl/ssl.h>
24 #include <err.h>
25 #include <limits.h>
26 #include <signal.h>
27 #include <stdio.h>
28 #include <stdlib.h>
29 #include <string.h>
30 
31 #include "extern.h"
32 
33 BIGNUM		zero;
34 
35 /* #define	DEBUGGING */
36 
37 #define MAX_ARRAY_INDEX		2048
38 #define RECURSION_STACK_SIZE	100
39 
40 #define NO_ELSE			-2	/* -1 is EOF */
41 #define REG_ARRAY_SIZE_SMALL	(UCHAR_MAX + 1)
42 #define REG_ARRAY_SIZE_BIG	(UCHAR_MAX + 1 + USHRT_MAX + 1)
43 
44 struct bmachine {
45 	struct stack		stack;
46 	u_int			scale;
47 	u_int			obase;
48 	u_int			ibase;
49 	int			readsp;
50 	bool			extended_regs;
51 	size_t			reg_array_size;
52 	struct stack		*reg;
53 	volatile bool		interrupted;
54 	struct source		readstack[RECURSION_STACK_SIZE];
55 };
56 
57 static struct bmachine	bmachine;
58 static void sighandler(int);
59 
60 static __inline int	readch(void);
61 static __inline int	unreadch(void);
62 static __inline char	*readline(void);
63 static __inline void	src_free(void);
64 
65 static __inline u_int	max(u_int, u_int);
66 static u_long		get_ulong(struct number *);
67 
68 static __inline void	push_number(struct number *);
69 static __inline void	push_string(char *);
70 static __inline void	push(struct value *);
71 static __inline struct value *tos(void);
72 static __inline struct number	*pop_number(void);
73 static __inline char	*pop_string(void);
74 static __inline void	clear_stack(void);
75 static __inline void	print_tos(void);
76 static void		pop_print(void);
77 static void		pop_printn(void);
78 static __inline void	print_stack(void);
79 static __inline void	dup(void);
80 static void		swap(void);
81 static void		drop(void);
82 
83 static void		get_scale(void);
84 static void		set_scale(void);
85 static void		get_obase(void);
86 static void		set_obase(void);
87 static void		get_ibase(void);
88 static void		set_ibase(void);
89 static void		stackdepth(void);
90 static void		push_scale(void);
91 static u_int		count_digits(const struct number *);
92 static void		num_digits(void);
93 static void		to_ascii(void);
94 static void		push_line(void);
95 static void		comment(void);
96 static void		bexec(char *);
97 static void		badd(void);
98 static void		bsub(void);
99 static void		bmul(void);
100 static void		bdiv(void);
101 static void		bmod(void);
102 static void		bdivmod(void);
103 static void		bexp(void);
104 static bool		bsqrt_stop(const BIGNUM *, const BIGNUM *);
105 static void		bsqrt(void);
106 static void		not(void);
107 static void		equal_numbers(void);
108 static void		less_numbers(void);
109 static void		lesseq_numbers(void);
110 static void		equal(void);
111 static void		not_equal(void);
112 static void		less(void);
113 static void		not_less(void);
114 static void		greater(void);
115 static void		not_greater(void);
116 static void		not_compare(void);
117 static bool		compare_numbers(enum bcode_compare, struct number *,
118 			    struct number *);
119 static void		compare(enum bcode_compare);
120 static int		readreg(void);
121 static void		load(void);
122 static void		store(void);
123 static void		load_stack(void);
124 static void		store_stack(void);
125 static void		load_array(void);
126 static void		store_array(void);
127 static void		nop(void);
128 static void		quit(void);
129 static void		quitN(void);
130 static void		skipN(void);
131 static void		skip_until_mark(void);
132 static void		parse_number(void);
133 static void		unknown(void);
134 static void		eval_string(char *);
135 static void		eval_line(void);
136 static void		eval_tos(void);
137 
138 
139 typedef void		(*opcode_function)(void);
140 
141 struct jump_entry {
142 	u_char		ch;
143 	opcode_function	f;
144 };
145 
146 static opcode_function jump_table[UCHAR_MAX];
147 
148 static const struct jump_entry jump_table_data[] = {
149 	{ ' ',	nop		},
150 	{ '!',	not_compare	},
151 	{ '#',	comment		},
152 	{ '%',	bmod		},
153 	{ '(',	less_numbers	},
154 	{ '*',	bmul		},
155 	{ '+',	badd		},
156 	{ '-',	bsub		},
157 	{ '.',	parse_number	},
158 	{ '/',	bdiv		},
159 	{ '0',	parse_number	},
160 	{ '1',	parse_number	},
161 	{ '2',	parse_number	},
162 	{ '3',	parse_number	},
163 	{ '4',	parse_number	},
164 	{ '5',	parse_number	},
165 	{ '6',	parse_number	},
166 	{ '7',	parse_number	},
167 	{ '8',	parse_number	},
168 	{ '9',	parse_number	},
169 	{ ':',	store_array	},
170 	{ ';',	load_array	},
171 	{ '<',	less		},
172 	{ '=',	equal		},
173 	{ '>',	greater		},
174 	{ '?',	eval_line	},
175 	{ 'A',	parse_number	},
176 	{ 'B',	parse_number	},
177 	{ 'C',	parse_number	},
178 	{ 'D',	parse_number	},
179 	{ 'E',	parse_number	},
180 	{ 'F',	parse_number	},
181 	{ 'G',	equal_numbers	},
182 	{ 'I',	get_ibase	},
183 	{ 'J',	skipN		},
184 	{ 'K',	get_scale	},
185 	{ 'L',	load_stack	},
186 	{ 'M',	nop		},
187 	{ 'N',	not		},
188 	{ 'O',	get_obase	},
189 	{ 'P',	pop_print	},
190 	{ 'Q',	quitN		},
191 	{ 'R',	drop		},
192 	{ 'S',	store_stack	},
193 	{ 'X',	push_scale	},
194 	{ 'Z',	num_digits	},
195 	{ '[',	push_line	},
196 	{ '\f',	nop		},
197 	{ '\n',	nop		},
198 	{ '\r',	nop		},
199 	{ '\t',	nop		},
200 	{ '^',	bexp		},
201 	{ '_',	parse_number	},
202 	{ 'a',	to_ascii	},
203 	{ 'c',	clear_stack	},
204 	{ 'd',	dup		},
205 	{ 'f',	print_stack	},
206 	{ 'i',	set_ibase	},
207 	{ 'k',	set_scale	},
208 	{ 'l',	load		},
209 	{ 'n',	pop_printn	},
210 	{ 'o',	set_obase	},
211 	{ 'p',	print_tos	},
212 	{ 'q',	quit		},
213 	{ 'r',	swap		},
214 	{ 's',	store		},
215 	{ 'v',	bsqrt		},
216 	{ 'x',	eval_tos	},
217 	{ 'z',	stackdepth	},
218 	{ '{',	lesseq_numbers	},
219 	{ '~',	bdivmod		}
220 };
221 
222 #define JUMP_TABLE_DATA_SIZE \
223 	(sizeof(jump_table_data)/sizeof(jump_table_data[0]))
224 
225 static void
226 sighandler(int ignored)
227 {
228 	bmachine.interrupted = true;
229 }
230 
231 void
232 init_bmachine(bool extended_registers)
233 {
234 	int i;
235 
236 	bmachine.extended_regs = extended_registers;
237 	bmachine.reg_array_size = bmachine.extended_regs ?
238 	    REG_ARRAY_SIZE_BIG : REG_ARRAY_SIZE_SMALL;
239 
240 	bmachine.reg = malloc(bmachine.reg_array_size *
241 	    sizeof(bmachine.reg[0]));
242 	if (bmachine.reg == NULL)
243 		err(1, NULL);
244 
245 	for (i = 0; i < UCHAR_MAX; i++)
246 		jump_table[i] = unknown;
247 	for (i = 0; i < JUMP_TABLE_DATA_SIZE; i++)
248 		jump_table[jump_table_data[i].ch] = jump_table_data[i].f;
249 
250 	stack_init(&bmachine.stack);
251 
252 	for (i = 0; i < bmachine.reg_array_size; i++)
253 		stack_init(&bmachine.reg[i]);
254 
255 	bmachine.obase = bmachine.ibase = 10;
256 	BN_init(&zero);
257 	bn_check(BN_zero(&zero));
258 	signal(SIGINT, sighandler);
259 }
260 
261 /* Reset the things needed before processing a (new) file */
262 void
263 reset_bmachine(struct source *src)
264 {
265 	bmachine.readsp = 0;
266 	bmachine.readstack[0] = *src;
267 }
268 
269 static __inline int
270 readch(void)
271 {
272 	struct source *src = &bmachine.readstack[bmachine.readsp];
273 
274 	return src->vtable->readchar(src);
275 }
276 
277 static __inline int
278 unreadch(void)
279 {
280 	struct source *src = &bmachine.readstack[bmachine.readsp];
281 
282 	return src->vtable->unreadchar(src);
283 }
284 
285 static __inline char *
286 readline(void)
287 {
288 	struct source *src = &bmachine.readstack[bmachine.readsp];
289 
290 	return src->vtable->readline(src);
291 }
292 
293 static __inline void
294 src_free(void)
295 {
296 	struct source *src = &bmachine.readstack[bmachine.readsp];
297 
298 	src->vtable->free(src);
299 }
300 
301 #ifdef DEBUGGING
302 void
303 pn(const char * str, const struct number *n)
304 {
305 	char *p = BN_bn2dec(n->number);
306 	if (p == NULL)
307 		err(1, "BN_bn2dec failed");
308 	fputs(str, stderr);
309 	fprintf(stderr, " %s (%u)\n" , p, n->scale);
310 	OPENSSL_free(p);
311 }
312 
313 void
314 pbn(const char * str, const BIGNUM *n)
315 {
316 	char *p = BN_bn2dec(n);
317 	if (p == NULL)
318 		err(1, "BN_bn2dec failed");
319 	fputs(str, stderr);
320 	fprintf(stderr, " %s\n", p);
321 	OPENSSL_free(p);
322 }
323 
324 #endif
325 
326 static __inline u_int
327 max(u_int a, u_int b)
328 {
329 	return a > b ? a : b;
330 }
331 
332 static unsigned long factors[] = {
333 	0, 10, 100, 1000, 10000, 100000, 1000000, 10000000,
334 	100000000, 1000000000
335 };
336 
337 void
338 scale_number(BIGNUM *n, int s)
339 {
340 	int abs_scale;
341 
342 	if (s == 0)
343 		return;
344 
345 	abs_scale = s > 0 ? s : -s;
346 
347 	if (abs_scale < sizeof(factors)/sizeof(factors[0])) {
348 		if (s > 0)
349 			bn_check(BN_mul_word(n, factors[abs_scale]));
350 		else
351 			BN_div_word(n, factors[abs_scale]);
352 	} else {
353 		BIGNUM *a, *p;
354 		BN_CTX *ctx;
355 
356 		a = BN_new();
357 		bn_checkp(a);
358 		p = BN_new();
359 		bn_checkp(p);
360 		ctx = BN_CTX_new();
361 		bn_checkp(ctx);
362 
363 		bn_check(BN_set_word(a, 10));
364 		bn_check(BN_set_word(p, abs_scale));
365 		bn_check(BN_exp(a, a, p, ctx));
366 		if (s > 0)
367 			bn_check(BN_mul(n, n, a, ctx));
368 		else
369 			bn_check(BN_div(n, NULL, n, a, ctx));
370 		BN_CTX_free(ctx);
371 		BN_free(a);
372 		BN_free(p);
373 	}
374 }
375 
376 void
377 split_number(const struct number *n, BIGNUM *i, BIGNUM *f)
378 {
379 	u_long rem;
380 
381 	bn_checkp(BN_copy(i, n->number));
382 
383 	if (n->scale == 0 && f != NULL)
384 		BN_zero(f);
385 	else if (n->scale < sizeof(factors)/sizeof(factors[0])) {
386 		rem = BN_div_word(i, factors[n->scale]);
387 		if (f != NULL)
388 			BN_set_word(f, rem);
389 	} else {
390 		BIGNUM *a, *p;
391 		BN_CTX *ctx;
392 
393 		a = BN_new();
394 		bn_checkp(a);
395 		p = BN_new();
396 		bn_checkp(p);
397 		ctx = BN_CTX_new();
398 		bn_checkp(ctx);
399 
400 		bn_check(BN_set_word(a, 10));
401 		bn_check(BN_set_word(p, n->scale));
402 		bn_check(BN_exp(a, a, p, ctx));
403 		bn_check(BN_div(i, f, n->number, a, ctx));
404 		BN_CTX_free(ctx);
405 		BN_free(a);
406 		BN_free(p);
407 	}
408 }
409 
410 __inline void
411 normalize(struct number *n, u_int s)
412 {
413 	scale_number(n->number, s - n->scale);
414 	n->scale = s;
415 }
416 
417 static u_long
418 get_ulong(struct number *n)
419 {
420 	normalize(n, 0);
421 	return BN_get_word(n->number);
422 }
423 
424 void
425 negate(struct number *n)
426 {
427 	bn_check(BN_sub(n->number, &zero, n->number));
428 }
429 
430 static __inline void
431 push_number(struct number *n)
432 {
433 	stack_pushnumber(&bmachine.stack, n);
434 }
435 
436 static __inline void
437 push_string(char *string)
438 {
439 	stack_pushstring(&bmachine.stack, string);
440 }
441 
442 static __inline void
443 push(struct value *v)
444 {
445 	stack_push(&bmachine.stack, v);
446 }
447 
448 static __inline struct value *
449 tos(void)
450 {
451 	return stack_tos(&bmachine.stack);
452 }
453 
454 static __inline struct value *
455 pop(void)
456 {
457 	return stack_pop(&bmachine.stack);
458 }
459 
460 static __inline struct number *
461 pop_number(void)
462 {
463 	return stack_popnumber(&bmachine.stack);
464 }
465 
466 static __inline char *
467 pop_string(void)
468 {
469 	return stack_popstring(&bmachine.stack);
470 }
471 
472 static __inline void
473 clear_stack(void)
474 {
475 	stack_clear(&bmachine.stack);
476 }
477 
478 static __inline void
479 print_stack(void)
480 {
481 	stack_print(stdout, &bmachine.stack, "", bmachine.obase);
482 }
483 
484 static __inline void
485 print_tos(void)
486 {
487 	struct value *value = tos();
488 	if (value != NULL) {
489 		print_value(stdout, value, "", bmachine.obase);
490 		putchar('\n');
491 	}
492 	else
493 		warnx("stack empty");
494 }
495 
496 static void
497 pop_print(void)
498 {
499 	struct value *value = pop();
500 
501 	if (value != NULL) {
502 		switch (value->type) {
503 		case BCODE_NONE:
504 			break;
505 		case BCODE_NUMBER:
506 			normalize(value->u.num, 0);
507 			print_ascii(stdout, value->u.num);
508 			fflush(stdout);
509 			break;
510 		case BCODE_STRING:
511 			fputs(value->u.string, stdout);
512 			fflush(stdout);
513 			break;
514 		}
515 		stack_free_value(value);
516 	}
517 }
518 
519 static void
520 pop_printn(void)
521 {
522 	struct value *value = pop();
523 
524 	if (value != NULL) {
525 		print_value(stdout, value, "", bmachine.obase);
526 		fflush(stdout);
527 		stack_free_value(value);
528 	}
529 }
530 
531 static __inline void
532 dup(void)
533 {
534 	stack_dup(&bmachine.stack);
535 }
536 
537 static void
538 swap(void)
539 {
540 	stack_swap(&bmachine.stack);
541 }
542 
543 static void
544 drop(void)
545 {
546 	struct value *v = pop();
547 	if (v != NULL)
548 		stack_free_value(v);
549 }
550 
551 static void
552 get_scale(void)
553 {
554 	struct number	*n;
555 
556 	n = new_number();
557 	bn_check(BN_set_word(n->number, bmachine.scale));
558 	push_number(n);
559 }
560 
561 static void
562 set_scale(void)
563 {
564 	struct number	*n;
565 	u_long		scale;
566 
567 	n = pop_number();
568 	if (n != NULL) {
569 		if (BN_cmp(n->number, &zero) < 0)
570 			warnx("scale must be a nonnegative number");
571 		else {
572 			scale = get_ulong(n);
573 			if (scale != BN_MASK2)
574 				bmachine.scale = scale;
575 			else
576 				warnx("scale too large");
577 			}
578 		free_number(n);
579 	}
580 }
581 
582 static void
583 get_obase(void)
584 {
585 	struct number	*n;
586 
587 	n = new_number();
588 	bn_check(BN_set_word(n->number, bmachine.obase));
589 	push_number(n);
590 }
591 
592 static void
593 set_obase(void)
594 {
595 	struct number	*n;
596 	u_long		base;
597 
598 	n = pop_number();
599 	if (n != NULL) {
600 		base = get_ulong(n);
601 		if (base != BN_MASK2 && base > 1)
602 			bmachine.obase = base;
603 		else
604 			warnx("output base must be a number greater than 1");
605 		free_number(n);
606 	}
607 }
608 
609 static void
610 get_ibase(void)
611 {
612 	struct number *n;
613 
614 	n = new_number();
615 	bn_check(BN_set_word(n->number, bmachine.ibase));
616 	push_number(n);
617 }
618 
619 static void
620 set_ibase(void)
621 {
622 	struct number	*n;
623 	u_long		base;
624 
625 	n = pop_number();
626 	if (n != NULL) {
627 		base = get_ulong(n);
628 		if (base != BN_MASK2 && 2 <= base && base <= 16)
629 			bmachine.ibase = base;
630 		else
631 			warnx("input base must be a number between 2 and 16 "
632 			    "(inclusive)");
633 		free_number(n);
634 	}
635 }
636 
637 static void
638 stackdepth(void)
639 {
640 	u_int i;
641 	struct number *n;
642 
643 	i = stack_size(&bmachine.stack);
644 	n = new_number();
645 	bn_check(BN_set_word(n->number, i));
646 	push_number(n);
647 }
648 
649 static void
650 push_scale(void)
651 {
652 	struct value	*value;
653 	u_int		scale = 0;
654 	struct number	*n;
655 
656 
657 	value = pop();
658 	if (value != NULL) {
659 		switch (value->type) {
660 		case BCODE_NONE:
661 			return;
662 		case BCODE_NUMBER:
663 			scale = value->u.num->scale;
664 			break;
665 		case BCODE_STRING:
666 			break;
667 		}
668 		stack_free_value(value);
669 		n = new_number();
670 		bn_check(BN_set_word(n->number, scale));
671 		push_number(n);
672 	}
673 }
674 
675 static u_int
676 count_digits(const struct number *n)
677 {
678 	struct number	*int_part, *fract_part;
679 	u_int		i;
680 
681 	if (BN_is_zero(n->number))
682 		return 1;
683 
684 	int_part = new_number();
685 	fract_part = new_number();
686 	fract_part->scale = n->scale;
687 	split_number(n, int_part->number, fract_part->number);
688 
689 	i = 0;
690 	while (!BN_is_zero(int_part->number)) {
691 		BN_div_word(int_part->number, 10);
692 		i++;
693 	}
694 	free_number(int_part);
695 	free_number(fract_part);
696 	return i + n->scale;
697 }
698 
699 static void
700 num_digits(void)
701 {
702 	struct value	*value;
703 	u_int		digits;
704 	struct number	*n = NULL;
705 
706 	value = pop();
707 	if (value != NULL) {
708 		switch (value->type) {
709 		case BCODE_NONE:
710 			return;
711 		case BCODE_NUMBER:
712 			digits = count_digits(value->u.num);
713 			n = new_number();
714 			bn_check(BN_set_word(n->number, digits));
715 			break;
716 		case BCODE_STRING:
717 			digits = strlen(value->u.string);
718 			n = new_number();
719 			bn_check(BN_set_word(n->number, digits));
720 			break;
721 		}
722 		stack_free_value(value);
723 		push_number(n);
724 	}
725 }
726 
727 static void
728 to_ascii(void)
729 {
730 	char		str[2];
731 	struct value	*value;
732 	struct number	*n;
733 
734 	value = pop();
735 	if (value != NULL) {
736 		str[1] = '\0';
737 		switch (value->type) {
738 		case BCODE_NONE:
739 			return;
740 		case BCODE_NUMBER:
741 			n = value->u.num;
742 			normalize(n, 0);
743 			if (BN_num_bits(n->number) > 8)
744 				bn_check(BN_mask_bits(n->number, 8));
745 			str[0] = BN_get_word(n->number);
746 			break;
747 		case BCODE_STRING:
748 			str[0] = value->u.string[0];
749 			break;
750 		}
751 		stack_free_value(value);
752 		push_string(bstrdup(str));
753 	}
754 }
755 
756 static int
757 readreg(void)
758 {
759 	int index, ch1, ch2;
760 
761 	index = readch();
762 	if (index == 0xff && bmachine.extended_regs) {
763 		ch1 = readch();
764 		ch2 = readch();
765 		if (ch1 == EOF || ch2 == EOF) {
766 			warnx("unexpected eof");
767 			index = -1;
768 		} else
769 			index = (ch1 << 8) + ch2 + UCHAR_MAX + 1;
770 	}
771 	if (index < 0 || index >= bmachine.reg_array_size) {
772 		warnx("internal error: reg num = %d", index);
773 		index = -1;
774 	}
775 	return index;
776 }
777 
778 static void
779 load(void)
780 {
781 	int		index;
782 	struct value	*v, copy;
783 	struct number	*n;
784 
785 	index = readreg();
786 	if (index >= 0) {
787 		v = stack_tos(&bmachine.reg[index]);
788 		if (v == NULL) {
789 			n = new_number();
790 			bn_check(BN_zero(n->number));
791 			push_number(n);
792 		} else
793 			push(stack_dup_value(v, &copy));
794 	}
795 }
796 
797 static void
798 store(void)
799 {
800 	int		index;
801 	struct value	*val;
802 
803 	index = readreg();
804 	if (index >= 0) {
805 		val = pop();
806 		if (val == NULL) {
807 			return;
808 		}
809 		stack_set_tos(&bmachine.reg[index], val);
810 	}
811 }
812 
813 static void
814 load_stack(void)
815 {
816 	int		index;
817 	struct stack	*stack;
818 	struct value	*value, copy;
819 
820 	index = readreg();
821 	if (index >= 0) {
822 		stack = &bmachine.reg[index];
823 		value = NULL;
824 		if (stack_size(stack) > 0) {
825 			value = stack_pop(stack);
826 		}
827 		if (value != NULL)
828 			push(stack_dup_value(value, &copy));
829 		else
830 			warnx("stack register '%c' (0%o) is empty",
831 			    index, index);
832 	}
833 }
834 
835 static void
836 store_stack(void)
837 {
838 	int		index;
839 	struct value	*value;
840 
841 	index = readreg();
842 	if (index >= 0) {
843 		value = pop();
844 		if (value == NULL)
845 			return;
846 		stack_push(&bmachine.reg[index], value);
847 	}
848 }
849 
850 static void
851 load_array(void)
852 {
853 	int			reg;
854 	struct number		*inumber, *n;
855 	u_long			index;
856 	struct stack		*stack;
857 	struct value		*v, copy;
858 
859 	reg = readreg();
860 	if (reg >= 0) {
861 		inumber = pop_number();
862 		if (inumber == NULL)
863 			return;
864 		index = get_ulong(inumber);
865 		if (BN_cmp(inumber->number, &zero) < 0)
866 			warnx("negative index");
867 		else if (index == BN_MASK2 || index > MAX_ARRAY_INDEX)
868 			warnx("index too big");
869 		else {
870 			stack = &bmachine.reg[reg];
871 			v = frame_retrieve(stack, index);
872 			if (v == NULL) {
873 				n = new_number();
874 				bn_check(BN_zero(n->number));
875 				push_number(n);
876 			}
877 			else
878 				push(stack_dup_value(v, &copy));
879 		}
880 		free_number(inumber);
881 	}
882 }
883 
884 static void
885 store_array(void)
886 {
887 	int			reg;
888 	struct number		*inumber;
889 	u_long			index;
890 	struct value		*value;
891 	struct stack		*stack;
892 
893 	reg = readreg();
894 	if (reg >= 0) {
895 		inumber = pop_number();
896 		if (inumber == NULL)
897 			return;
898 		value = pop();
899 		if (value == NULL) {
900 			free_number(inumber);
901 			return;
902 		}
903 		index = get_ulong(inumber);
904 		if (BN_cmp(inumber->number, &zero) < 0) {
905 			warnx("negative index");
906 			stack_free_value(value);
907 		} else if (index == BN_MASK2 || index > MAX_ARRAY_INDEX) {
908 			warnx("index too big");
909 			stack_free_value(value);
910 		} else {
911 			stack = &bmachine.reg[reg];
912 			frame_assign(stack, index, value);
913 		}
914 		free_number(inumber);
915 	}
916 }
917 
918 static void
919 push_line(void)
920 {
921 	push_string(read_string(&bmachine.readstack[bmachine.readsp]));
922 }
923 
924 static void
925 comment(void)
926 {
927 	free(readline());
928 }
929 
930 static void
931 bexec(char *line)
932 {
933 	system(line);
934 	free(line);
935 }
936 
937 static void
938 badd(void)
939 {
940 	struct number	*a, *b;
941 	struct number	*r;
942 
943 	a = pop_number();
944 	if (a == NULL) {
945 		return;
946 	}
947 	b = pop_number();
948 	if (b == NULL) {
949 		push_number(a);
950 		return;
951 	}
952 
953 	r = new_number();
954 	r->scale = max(a->scale, b->scale);
955 	if (r->scale > a->scale)
956 		normalize(a, r->scale);
957 	else if (r->scale > b->scale)
958 		normalize(b, r->scale);
959 	bn_check(BN_add(r->number, a->number, b->number));
960 	push_number(r);
961 	free_number(a);
962 	free_number(b);
963 }
964 
965 static void
966 bsub(void)
967 {
968 	struct number	*a, *b;
969 	struct number	*r;
970 
971 	a = pop_number();
972 	if (a == NULL) {
973 		return;
974 	}
975 	b = pop_number();
976 	if (b == NULL) {
977 		push_number(a);
978 		return;
979 	}
980 
981 	r = new_number();
982 
983 	r->scale = max(a->scale, b->scale);
984 	if (r->scale > a->scale)
985 		normalize(a, r->scale);
986 	else if (r->scale > b->scale)
987 		normalize(b, r->scale);
988 	bn_check(BN_sub(r->number, b->number, a->number));
989 	push_number(r);
990 	free_number(a);
991 	free_number(b);
992 }
993 
994 void
995 bmul_number(struct number *r, struct number *a, struct number *b)
996 {
997 	BN_CTX		*ctx;
998 
999 	/* Create copies of the scales, since r might be equal to a or b */
1000 	u_int ascale = a->scale;
1001 	u_int bscale = b->scale;
1002 	u_int rscale = ascale + bscale;
1003 
1004 	ctx = BN_CTX_new();
1005 	bn_checkp(ctx);
1006 	bn_check(BN_mul(r->number, a->number, b->number, ctx));
1007 	BN_CTX_free(ctx);
1008 
1009 	if (rscale > bmachine.scale && rscale > ascale && rscale > bscale) {
1010 		r->scale = rscale;
1011 		normalize(r, max(bmachine.scale, max(ascale, bscale)));
1012 	} else
1013 		r->scale = rscale;
1014 }
1015 
1016 static void
1017 bmul(void)
1018 {
1019 	struct number	*a, *b;
1020 	struct number	*r;
1021 
1022 	a = pop_number();
1023 	if (a == NULL) {
1024 		return;
1025 	}
1026 	b = pop_number();
1027 	if (b == NULL) {
1028 		push_number(a);
1029 		return;
1030 	}
1031 
1032 	r = new_number();
1033 	bmul_number(r, a, b);
1034 
1035 	push_number(r);
1036 	free_number(a);
1037 	free_number(b);
1038 }
1039 
1040 static void
1041 bdiv(void)
1042 {
1043 	struct number	*a, *b;
1044 	struct number	*r;
1045 	u_int		scale;
1046 	BN_CTX		*ctx;
1047 
1048 	a = pop_number();
1049 	if (a == NULL) {
1050 		return;
1051 	}
1052 	b = pop_number();
1053 	if (b == NULL) {
1054 		push_number(a);
1055 		return;
1056 	}
1057 
1058 	r = new_number();
1059 	r->scale = bmachine.scale;
1060 	scale = max(a->scale, b->scale);
1061 
1062 	if (BN_is_zero(a->number))
1063 		warnx("divide by zero");
1064 	else {
1065 		normalize(a, scale);
1066 		normalize(b, scale + r->scale);
1067 
1068 		ctx = BN_CTX_new();
1069 		bn_checkp(ctx);
1070 		bn_check(BN_div(r->number, NULL, b->number, a->number, ctx));
1071 		BN_CTX_free(ctx);
1072 	}
1073 	push_number(r);
1074 	free_number(a);
1075 	free_number(b);
1076 }
1077 
1078 static void
1079 bmod(void)
1080 {
1081 	struct number	*a, *b;
1082 	struct number	*r;
1083 	u_int		scale;
1084 	BN_CTX		*ctx;
1085 
1086 	a = pop_number();
1087 	if (a == NULL) {
1088 		return;
1089 	}
1090 	b = pop_number();
1091 	if (b == NULL) {
1092 		push_number(a);
1093 		return;
1094 	}
1095 
1096 	r = new_number();
1097 	scale = max(a->scale, b->scale);
1098 	r->scale = max(b->scale, a->scale + bmachine.scale);
1099 
1100 	if (BN_is_zero(a->number))
1101 		warnx("remainder by zero");
1102 	else {
1103 		normalize(a, scale);
1104 		normalize(b, scale + bmachine.scale);
1105 
1106 		ctx = BN_CTX_new();
1107 		bn_checkp(ctx);
1108 		bn_check(BN_mod(r->number, b->number, a->number, ctx));
1109 		BN_CTX_free(ctx);
1110 	}
1111 	push_number(r);
1112 	free_number(a);
1113 	free_number(b);
1114 }
1115 
1116 static void
1117 bdivmod(void)
1118 {
1119 	struct number	*a, *b;
1120 	struct number	*rdiv, *rmod;
1121 	u_int		scale;
1122 	BN_CTX		*ctx;
1123 
1124 	a = pop_number();
1125 	if (a == NULL) {
1126 		return;
1127 	}
1128 	b = pop_number();
1129 	if (b == NULL) {
1130 		push_number(a);
1131 		return;
1132 	}
1133 
1134 	rdiv = new_number();
1135 	rmod = new_number();
1136 	rdiv->scale = bmachine.scale;
1137 	rmod->scale = max(b->scale, a->scale + bmachine.scale);
1138 	scale = max(a->scale, b->scale);
1139 
1140 	if (BN_is_zero(a->number))
1141 		warnx("divide by zero");
1142 	else {
1143 		normalize(a, scale);
1144 		normalize(b, scale + bmachine.scale);
1145 
1146 		ctx = BN_CTX_new();
1147 		bn_checkp(ctx);
1148 		bn_check(BN_div(rdiv->number, rmod->number,
1149 		    b->number, a->number, ctx));
1150 		BN_CTX_free(ctx);
1151 	}
1152 	push_number(rdiv);
1153 	push_number(rmod);
1154 	free_number(a);
1155 	free_number(b);
1156 }
1157 
1158 static void
1159 bexp(void)
1160 {
1161 	struct number	*a, *p;
1162 	struct number	*r;
1163 	bool		neg;
1164 	u_int		scale;
1165 
1166 	p = pop_number();
1167 	if (p == NULL) {
1168 		return;
1169 	}
1170 	a = pop_number();
1171 	if (a == NULL) {
1172 		push_number(p);
1173 		return;
1174 	}
1175 
1176 	if (p->scale != 0)
1177 		warnx("Runtime warning: non-zero scale in exponent");
1178 	normalize(p, 0);
1179 
1180 	neg = false;
1181 	if (BN_cmp(p->number, &zero) < 0) {
1182 		neg = true;
1183 		negate(p);
1184 		scale = bmachine.scale;
1185 	} else {
1186 		/* Posix bc says min(a.scale * b, max(a.scale, scale) */
1187 		u_long	b;
1188 		u_int	m;
1189 
1190 		b = BN_get_word(p->number);
1191 		m = max(a->scale, bmachine.scale);
1192 		scale = a->scale * b;
1193 		if (scale > m || b == BN_MASK2)
1194 			scale = m;
1195 	}
1196 
1197 	if (BN_is_zero(p->number)) {
1198 		r = new_number();
1199 		bn_check(BN_one(r->number));
1200 		normalize(r, scale);
1201 	} else {
1202 		while (!BN_is_bit_set(p->number, 0)) {
1203 			bmul_number(a, a, a);
1204 			bn_check(BN_rshift1(p->number, p->number));
1205 		}
1206 
1207 		r = dup_number(a);
1208 		normalize(r, scale);
1209 		bn_check(BN_rshift1(p->number, p->number));
1210 
1211 		while (!BN_is_zero(p->number)) {
1212 			bmul_number(a, a, a);
1213 			if (BN_is_bit_set(p->number, 0))
1214 				bmul_number(r, r, a);
1215 			bn_check(BN_rshift1(p->number, p->number));
1216 		}
1217 
1218 		if (neg) {
1219 			BN_CTX	*ctx;
1220 			BIGNUM	*one;
1221 
1222 			one = BN_new();
1223 			bn_checkp(one);
1224 			BN_one(one);
1225 			ctx = BN_CTX_new();
1226 			bn_checkp(ctx);
1227 			r->scale = scale;
1228 			scale_number(one, r->scale);
1229 			bn_check(BN_div(r->number, NULL, one, r->number, ctx));
1230 			BN_free(one);
1231 			BN_CTX_free(ctx);
1232 		}
1233 	}
1234 	push_number(r);
1235 	free_number(a);
1236 	free_number(p);
1237 }
1238 
1239 static bool
1240 bsqrt_stop(const BIGNUM *x, const BIGNUM *y)
1241 {
1242 	BIGNUM *r;
1243 	bool ret;
1244 
1245 	r = BN_new();
1246 	bn_checkp(r);
1247 	bn_check(BN_sub(r, x, y));
1248 	ret = BN_is_one(r) || BN_is_zero(r);
1249 	BN_free(r);
1250 	return ret;
1251 }
1252 
1253 static void
1254 bsqrt(void)
1255 {
1256 	struct number	*n;
1257 	struct number	*r;
1258 	BIGNUM		*x, *y;
1259 	u_int		scale;
1260 	BN_CTX		*ctx;
1261 
1262 	n = pop_number();
1263 	if (n == NULL) {
1264 		return;
1265 	}
1266 	if (BN_is_zero(n->number)) {
1267 		r = new_number();
1268 		push_number(r);
1269 	} else if (BN_cmp(n->number, &zero) < 0)
1270 		warnx("square root of negative number");
1271 	else {
1272 		scale = max(bmachine.scale, n->scale);
1273 		normalize(n, 2*scale);
1274 		x = BN_dup(n->number);
1275 		bn_checkp(x);
1276 		bn_check(BN_rshift(x, x, BN_num_bits(x)/2));
1277 		y = BN_new();
1278 		bn_checkp(y);
1279 		ctx = BN_CTX_new();
1280 		bn_checkp(ctx);
1281 		for (;;) {
1282 			bn_checkp(BN_copy(y, x));
1283 			bn_check(BN_div(x, NULL, n->number, x, ctx));
1284 			bn_check(BN_add(x, x, y));
1285 			bn_check(BN_rshift1(x, x));
1286 			if (bsqrt_stop(x, y))
1287 				break;
1288 		}
1289 		r = bmalloc(sizeof(*r));
1290 		r->scale = scale;
1291 		r->number = y;
1292 		BN_free(x);
1293 		BN_CTX_free(ctx);
1294 		push_number(r);
1295 	}
1296 
1297 	free_number(n);
1298 }
1299 
1300 static void
1301 not(void)
1302 {
1303 	struct number	*a;
1304 
1305 	a = pop_number();
1306 	if (a == NULL) {
1307 		return;
1308 	}
1309 	a->scale = 0;
1310 	bn_check(BN_set_word(a->number, BN_get_word(a->number) ? 0 : 1));
1311 	push_number(a);
1312 }
1313 
1314 static void
1315 equal(void)
1316 {
1317 	compare(BCODE_EQUAL);
1318 }
1319 
1320 static void
1321 equal_numbers(void)
1322 {
1323 	struct number *a, *b, *r;
1324 
1325 	a = pop_number();
1326 	if (a == NULL) {
1327 		return;
1328 	}
1329 	b = pop_number();
1330 	if (b == NULL) {
1331 		push_number(a);
1332 		return;
1333 	}
1334 	r = new_number();
1335 	bn_check(BN_set_word(r->number,
1336 	    compare_numbers(BCODE_EQUAL, a, b) ? 1 : 0));
1337 	push_number(r);
1338 }
1339 
1340 static void
1341 less_numbers(void)
1342 {
1343 	struct number *a, *b, *r;
1344 
1345 	a = pop_number();
1346 	if (a == NULL) {
1347 		return;
1348 	}
1349 	b = pop_number();
1350 	if (b == NULL) {
1351 		push_number(a);
1352 		return;
1353 	}
1354 	r = new_number();
1355 	bn_check(BN_set_word(r->number,
1356 	    compare_numbers(BCODE_LESS, a, b) ? 1 : 0));
1357 	push_number(r);
1358 }
1359 
1360 static void
1361 lesseq_numbers(void)
1362 {
1363 	struct number *a, *b, *r;
1364 
1365 	a = pop_number();
1366 	if (a == NULL) {
1367 		return;
1368 	}
1369 	b = pop_number();
1370 	if (b == NULL) {
1371 		push_number(a);
1372 		return;
1373 	}
1374 	r = new_number();
1375 	bn_check(BN_set_word(r->number,
1376 	    compare_numbers(BCODE_NOT_GREATER, a, b) ? 1 : 0));
1377 	push_number(r);
1378 }
1379 
1380 static void
1381 not_equal(void)
1382 {
1383 	compare(BCODE_NOT_EQUAL);
1384 }
1385 
1386 static void
1387 less(void)
1388 {
1389 	compare(BCODE_LESS);
1390 }
1391 
1392 static void
1393 not_compare(void)
1394 {
1395 	switch (readch()) {
1396 	case '<':
1397 		not_less();
1398 		break;
1399 	case '>':
1400 		not_greater();
1401 		break;
1402 	case '=':
1403 		not_equal();
1404 		break;
1405 	default:
1406 		unreadch();
1407 		bexec(readline());
1408 		break;
1409 	}
1410 }
1411 
1412 static void
1413 not_less(void)
1414 {
1415 	compare(BCODE_NOT_LESS);
1416 }
1417 
1418 static void
1419 greater(void)
1420 {
1421 	compare(BCODE_GREATER);
1422 }
1423 
1424 static void
1425 not_greater(void)
1426 {
1427 	compare(BCODE_NOT_GREATER);
1428 }
1429 
1430 static bool
1431 compare_numbers(enum bcode_compare type, struct number *a, struct number *b)
1432 {
1433 	u_int	scale;
1434 	int	cmp;
1435 
1436 	scale = max(a->scale, b->scale);
1437 
1438 	if (scale > a->scale)
1439 		normalize(a, scale);
1440 	else if (scale > scale)
1441 		normalize(b, scale);
1442 
1443 	cmp = BN_cmp(a->number, b->number);
1444 
1445 	free_number(a);
1446 	free_number(b);
1447 
1448 	switch (type) {
1449 	case BCODE_EQUAL:
1450 		return cmp == 0;
1451 	case BCODE_NOT_EQUAL:
1452 		return cmp != 0;
1453 	case BCODE_LESS:
1454 		return cmp < 0;
1455 	case BCODE_NOT_LESS:
1456 		return cmp >= 0;
1457 	case BCODE_GREATER:
1458 		return cmp > 0;
1459 	case BCODE_NOT_GREATER:
1460 		return cmp <= 0;
1461 	}
1462 	return false;
1463 }
1464 
1465 static void
1466 compare(enum bcode_compare type)
1467 {
1468 	int		index, elseindex;
1469 	struct number	*a, *b;
1470 	bool		ok;
1471 	struct value	*v;
1472 
1473 	elseindex = NO_ELSE;
1474 	index = readreg();
1475 	if (readch() == 'e')
1476 		elseindex = readreg();
1477 	else
1478 		unreadch();
1479 
1480 	a = pop_number();
1481 	if (a == NULL)
1482 		return;
1483 	b = pop_number();
1484 	if (b == NULL) {
1485 		push_number(a);
1486 		return;
1487 	}
1488 
1489 	ok = compare_numbers(type, a, b);
1490 
1491 	if (!ok && elseindex != NO_ELSE)
1492 		index = elseindex;
1493 
1494 	if (index >= 0 && (ok || (!ok && elseindex != NO_ELSE))) {
1495 		v = stack_tos(&bmachine.reg[index]);
1496 		if (v == NULL)
1497 			warnx("register '%c' (0%o) is empty", index, index);
1498 		else {
1499 			switch(v->type) {
1500 			case BCODE_NONE:
1501 				warnx("register '%c' (0%o) is empty",
1502 				    index, index);
1503 				break;
1504 			case BCODE_NUMBER:
1505 				warn("eval called with non-string argument");
1506 				break;
1507 			case BCODE_STRING:
1508 				eval_string(bstrdup(v->u.string));
1509 				break;
1510 			}
1511 		}
1512 	}
1513 }
1514 
1515 
1516 static void
1517 nop(void)
1518 {
1519 }
1520 
1521 static void
1522 quit(void)
1523 {
1524 	if (bmachine.readsp < 2)
1525 		exit(0);
1526 	src_free();
1527 	bmachine.readsp--;
1528 	src_free();
1529 	bmachine.readsp--;
1530 }
1531 
1532 static void
1533 quitN(void)
1534 {
1535 	struct number	*n;
1536 	u_long		i;
1537 
1538 	n = pop_number();
1539 	if (n == NULL)
1540 		return;
1541 	i = get_ulong(n);
1542 	if (i == BN_MASK2 || i == 0)
1543 		warnx("Q command requires a number >= 1");
1544 	else if (bmachine.readsp < i)
1545 		warnx("Q command argument exceeded string execution depth");
1546 	else {
1547 		while (i-- > 0) {
1548 			src_free();
1549 			bmachine.readsp--;
1550 		}
1551 	}
1552 }
1553 
1554 static void
1555 skipN(void)
1556 {
1557 	struct number	*n;
1558 	u_long		i;
1559 
1560 	n = pop_number();
1561 	if (n == NULL)
1562 		return;
1563 	i = get_ulong(n);
1564 	if (i == BN_MASK2)
1565 		warnx("J command requires a number >= 0");
1566 	else if (i > 0 && bmachine.readsp < i)
1567 		warnx("J command argument exceeded string execution depth");
1568 	else {
1569 		while (i-- > 0) {
1570 			src_free();
1571 			bmachine.readsp--;
1572 		}
1573 		skip_until_mark();
1574 	}
1575 }
1576 
1577 static void
1578 skip_until_mark(void)
1579 {
1580 	int ch;
1581 
1582 	for (;;) {
1583 		ch = readch();
1584 		switch (ch) {
1585 		case 'M':
1586 			return;
1587 		case EOF:
1588 			errx(1, "mark not found");
1589 			return;
1590 		case 'l':
1591 		case 'L':
1592 		case 's':
1593 		case 'S':
1594 		case ':':
1595 		case ';':
1596 		case '<':
1597 		case '>':
1598 		case '=':
1599 			readreg();
1600 			if (readch() == 'e')
1601 				readreg();
1602 			else
1603 				unreadch();
1604 			break;
1605 		case '[':
1606 			free(read_string(&bmachine.readstack[bmachine.readsp]));
1607 			break;
1608 		case '!':
1609 			switch (ch = readch()) {
1610 				case '<':
1611 				case '>':
1612 				case '=':
1613 					readreg();
1614 					if (readch() == 'e')
1615 						readreg();
1616 					else
1617 						unreadch();
1618 					break;
1619 				default:
1620 					free(readline());
1621 					break;
1622 			}
1623 			break;
1624 		default:
1625 			break;
1626 		}
1627 	}
1628 }
1629 
1630 static void
1631 parse_number(void)
1632 {
1633 	unreadch();
1634 	push_number(readnumber(&bmachine.readstack[bmachine.readsp],
1635 	    bmachine.ibase));
1636 }
1637 
1638 static void
1639 unknown(void)
1640 {
1641 	int ch = bmachine.readstack[bmachine.readsp].lastchar;
1642 	warnx("%c (0%o) is unimplemented", ch, ch);
1643 }
1644 
1645 static void
1646 eval_string(char *p)
1647 {
1648 	int ch;
1649 
1650 	if (bmachine.readsp > 0) {
1651 		/* Check for tail call. Do not recurse in that case. */
1652 		ch = readch();
1653 		if (ch == EOF) {
1654 			src_free();
1655 			src_setstring(&bmachine.readstack[bmachine.readsp], p);
1656 			return;
1657 		} else
1658 			unreadch();
1659 	}
1660 	if (bmachine.readsp == RECURSION_STACK_SIZE-1)
1661 		errx(1, "recursion too deep");
1662 	src_setstring(&bmachine.readstack[++bmachine.readsp], p);
1663 }
1664 
1665 static void
1666 eval_line(void)
1667 {
1668 	/* Always read from stdin */
1669 	struct source	in;
1670 	char		*p;
1671 
1672 	src_setstream(&in, stdin);
1673 	p = (*in.vtable->readline)(&in);
1674 	eval_string(p);
1675 }
1676 
1677 static void
1678 eval_tos(void)
1679 {
1680 	char *p;
1681 
1682 	p = pop_string();
1683 	if (p == NULL)
1684 		return;
1685 	eval_string(p);
1686 }
1687 
1688 void
1689 eval(void)
1690 {
1691 	int	ch;
1692 
1693 	for (;;) {
1694 		ch = readch();
1695 		if (ch == EOF) {
1696 			if (bmachine.readsp == 0)
1697 				exit(0);
1698 			src_free();
1699 			bmachine.readsp--;
1700 			continue;
1701 		}
1702 		if (bmachine.interrupted) {
1703 			if (bmachine.readsp > 0) {
1704 				src_free();
1705 				bmachine.readsp--;
1706 				continue;
1707 			} else
1708 				bmachine.interrupted = false;
1709 		}
1710 #ifdef DEBUGGING
1711 		fprintf(stderr, "# %c\n", ch);
1712 		stack_print(stderr, &bmachine.stack, "* ",
1713 		    bmachine.obase);
1714 		fprintf(stderr, "%d =>\n", bmachine.readsp);
1715 #endif
1716 
1717 		if (0 <= ch && ch < UCHAR_MAX)
1718 			(*jump_table[ch])();
1719 		else
1720 			warnx("internal error: opcode %d", ch);
1721 
1722 #ifdef DEBUGGING
1723 		stack_print(stderr, &bmachine.stack, "* ",
1724 		    bmachine.obase);
1725 		fprintf(stderr, "%d ==\n", bmachine.readsp);
1726 #endif
1727 	}
1728 }
1729