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