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$");
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 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
56static struct bmachine	 bmachine;
57
58static __inline int	 readch(void);
59static __inline void	 unreadch(void);
60static __inline char	*readline(void);
61static __inline void	 src_free(void);
62
63static __inline u_int	 max(u_int, u_int);
64static u_long		 get_ulong(struct number *);
65
66static __inline void	 push_number(struct number *);
67static __inline void	 push_string(char *);
68static __inline void	 push(struct value *);
69static __inline struct value *tos(void);
70static __inline struct number	*pop_number(void);
71static __inline char	*pop_string(void);
72static __inline void	 clear_stack(void);
73static __inline void	 print_tos(void);
74static void		 pop_print(void);
75static void		 pop_printn(void);
76static __inline void	 print_stack(void);
77static __inline void	 dup(void);
78static void		 swap(void);
79static void		 drop(void);
80
81static void		 get_scale(void);
82static void		 set_scale(void);
83static void		 get_obase(void);
84static void		 set_obase(void);
85static void		 get_ibase(void);
86static void		 set_ibase(void);
87static void		 stackdepth(void);
88static void		 push_scale(void);
89static u_int		 count_digits(const struct number *);
90static void		 num_digits(void);
91static void		 to_ascii(void);
92static void		 push_line(void);
93static void		 comment(void);
94static void		 bexec(char *);
95static void		 badd(void);
96static void		 bsub(void);
97static void		 bmul(void);
98static void		 bdiv(void);
99static void		 bmod(void);
100static void		 bdivmod(void);
101static void		 bexp(void);
102static bool		 bsqrt_stop(const BIGNUM *, const BIGNUM *, u_int *);
103static void		 bsqrt(void);
104static void		 not(void);
105static void		 equal_numbers(void);
106static void		 less_numbers(void);
107static void		 lesseq_numbers(void);
108static void		 equal(void);
109static void		 not_equal(void);
110static void		 less(void);
111static void		 not_less(void);
112static void		 greater(void);
113static void		 not_greater(void);
114static void		 not_compare(void);
115static bool		 compare_numbers(enum bcode_compare, struct number *,
116			     struct number *);
117static void		 compare(enum bcode_compare);
118static int		 readreg(void);
119static void		 load(void);
120static void		 store(void);
121static void		 load_stack(void);
122static void		 store_stack(void);
123static void		 load_array(void);
124static void		 store_array(void);
125static void		 nop(void);
126static void		 quit(void);
127static void		 quitN(void);
128static void		 skipN(void);
129static void		 skip_until_mark(void);
130static void		 parse_number(void);
131static void		 unknown(void);
132static void		 eval_string(char *);
133static void		 eval_line(void);
134static void		 eval_tos(void);
135
136
137typedef void		(*opcode_function)(void);
138
139struct jump_entry {
140	u_char		 ch;
141	opcode_function	 f;
142};
143
144static opcode_function jump_table[UCHAR_MAX];
145
146static 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
223void
224init_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 */
258void
259reset_bmachine(struct source *src)
260{
261
262	bmachine.readsp = 0;
263	bmachine.readstack[0] = *src;
264}
265
266static __inline int
267readch(void)
268{
269	struct source *src = &bmachine.readstack[bmachine.readsp];
270
271	return (src->vtable->readchar(src));
272}
273
274static __inline void
275unreadch(void)
276{
277	struct source *src = &bmachine.readstack[bmachine.readsp];
278
279	src->vtable->unreadchar(src);
280}
281
282static __inline char *
283readline(void)
284{
285	struct source *src = &bmachine.readstack[bmachine.readsp];
286
287	return (src->vtable->readline(src));
288}
289
290static __inline void
291src_free(void)
292{
293	struct source *src = &bmachine.readstack[bmachine.readsp];
294
295	src->vtable->free(src);
296}
297
298#ifdef DEBUGGING
299void
300pn(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
311void
312pbn(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
325static __inline u_int
326max(u_int a, u_int b)
327{
328
329	return (a > b ? a : b);
330}
331
332static unsigned long factors[] = {
333	0, 10, 100, 1000, 10000, 100000, 1000000, 10000000,
334	100000000, 1000000000
335};
336
337void
338scale_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
376void
377split_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
411normalize(struct number *n, u_int s)
412{
413
414	scale_number(n->number, s - n->scale);
415	n->scale = s;
416}
417
418static u_long
419get_ulong(struct number *n)
420{
421
422	normalize(n, 0);
423	return (BN_get_word(n->number));
424}
425
426void
427negate(struct number *n)
428{
429
430	bn_check(BN_sub(n->number, &zero, n->number));
431}
432
433static __inline void
434push_number(struct number *n)
435{
436
437	stack_pushnumber(&bmachine.stack, n);
438}
439
440static __inline void
441push_string(char *string)
442{
443
444	stack_pushstring(&bmachine.stack, string);
445}
446
447static __inline void
448push(struct value *v)
449{
450
451	stack_push(&bmachine.stack, v);
452}
453
454static __inline struct value *
455tos(void)
456{
457
458	return (stack_tos(&bmachine.stack));
459}
460
461static __inline struct value *
462pop(void)
463{
464
465	return (stack_pop(&bmachine.stack));
466}
467
468static __inline struct number *
469pop_number(void)
470{
471
472	return (stack_popnumber(&bmachine.stack));
473}
474
475static __inline char *
476pop_string(void)
477{
478
479	return (stack_popstring(&bmachine.stack));
480}
481
482static __inline void
483clear_stack(void)
484{
485
486	stack_clear(&bmachine.stack);
487}
488
489static __inline void
490print_stack(void)
491{
492
493	stack_print(stdout, &bmachine.stack, "", bmachine.obase);
494}
495
496static __inline void
497print_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
509static void
510pop_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
532static void
533pop_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
544static __inline void
545dup(void)
546{
547
548	stack_dup(&bmachine.stack);
549}
550
551static void
552swap(void)
553{
554
555	stack_swap(&bmachine.stack);
556}
557
558static void
559drop(void)
560{
561	struct value *v = pop();
562	if (v != NULL)
563		stack_free_value(v);
564}
565
566static void
567get_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
576static void
577set_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
597static void
598get_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
607static void
608set_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
624static void
625get_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
634static void
635set_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
652static void
653stackdepth(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
664static void
665push_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
689static u_int
690count_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
713static void
714num_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
741static void
742to_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
770static int
771readreg(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
792static void
793load(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
812static void
813store(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
828static void
829load_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
850static void
851store_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
865static void
866load_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
900static void
901store_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
934static void
935push_line(void)
936{
937
938	push_string(read_string(&bmachine.readstack[bmachine.readsp]));
939}
940
941static void
942comment(void)
943{
944
945	free(readline());
946}
947
948static void
949bexec(char *line)
950{
951
952	system(line);
953	free(line);
954}
955
956static void
957badd(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
983static void
984bsub(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
1011void
1012bmul_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
1033static void
1034bmul(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
1056static void
1057bdiv(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
1093static void
1094bmod(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
1130static void
1131bdivmod(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
1171static void
1172bexp(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
1253static bool
1254bsqrt_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
1269static void
1270bsqrt(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
1316static void
1317not(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
1330static void
1331equal(void)
1332{
1333
1334	compare(BCODE_EQUAL);
1335}
1336
1337static void
1338equal_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
1357static void
1358less_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
1377static void
1378lesseq_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
1397static void
1398not_equal(void)
1399{
1400
1401	compare(BCODE_NOT_EQUAL);
1402}
1403
1404static void
1405less(void)
1406{
1407
1408	compare(BCODE_LESS);
1409}
1410
1411static void
1412not_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
1432static void
1433not_less(void)
1434{
1435
1436	compare(BCODE_NOT_LESS);
1437}
1438
1439static void
1440greater(void)
1441{
1442
1443	compare(BCODE_GREATER);
1444}
1445
1446static void
1447not_greater(void)
1448{
1449
1450	compare(BCODE_NOT_GREATER);
1451}
1452
1453static bool
1454compare_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
1488static void
1489compare(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
1538static void
1539nop(void)
1540{
1541
1542}
1543
1544static void
1545quit(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
1556static void
1557quitN(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
1579static void
1580skipN(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
1602static void
1603skip_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
1653static void
1654parse_number(void)
1655{
1656
1657	unreadch();
1658	push_number(readnumber(&bmachine.readstack[bmachine.readsp],
1659	    bmachine.ibase));
1660}
1661
1662static void
1663unknown(void)
1664{
1665	int ch = bmachine.readstack[bmachine.readsp].lastchar;
1666	warnx("%c (0%o) is unimplemented", ch, ch);
1667}
1668
1669static void
1670eval_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
1697static void
1698eval_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
1710static void
1711eval_tos(void)
1712{
1713	char *p;
1714
1715	p = pop_string();
1716	if (p == NULL)
1717		return;
1718	eval_string(p);
1719}
1720
1721void
1722eval(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