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