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