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