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