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