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