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