bcode.c revision 203443 
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 203443 2010-02-03 21:06:13Z 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 source		*readstack;
45	struct stack		*reg;
46	struct stack		 stack;
47	volatile sig_atomic_t	 interrupted;
48	u_int			 scale;
49	u_int			 obase;
50	u_int			 ibase;
51	size_t			 readsp;
52	size_t			 reg_array_size;
53	size_t			 readstack_sz;
54	bool			 extended_regs;
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	struct number *n;
670	size_t i;
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 number *n;
682	struct value *value;
683	u_int scale = 0;
684
685	value = pop();
686	if (value != NULL) {
687		switch (value->type) {
688		case BCODE_NONE:
689			return;
690		case BCODE_NUMBER:
691			scale = value->u.num->scale;
692			break;
693		case BCODE_STRING:
694			break;
695		}
696		stack_free_value(value);
697		n = new_number();
698		bn_check(BN_set_word(n->number, scale));
699		push_number(n);
700	}
701}
702
703static u_int
704count_digits(const struct number *n)
705{
706	struct number *int_part, *fract_part;
707	u_int i;
708
709	if (BN_is_zero(n->number))
710		return (1);
711
712	int_part = new_number();
713	fract_part = new_number();
714	fract_part->scale = n->scale;
715	split_number(n, int_part->number, fract_part->number);
716
717	i = 0;
718	while (!BN_is_zero(int_part->number)) {
719		BN_div_word(int_part->number, 10);
720		i++;
721	}
722	free_number(int_part);
723	free_number(fract_part);
724	return (i + n->scale);
725}
726
727static void
728num_digits(void)
729{
730	struct number *n = NULL;
731	struct value *value;
732	size_t digits;
733
734	value = pop();
735	if (value != NULL) {
736		switch (value->type) {
737		case BCODE_NONE:
738			return;
739		case BCODE_NUMBER:
740			digits = count_digits(value->u.num);
741			n = new_number();
742			bn_check(BN_set_word(n->number, digits));
743			break;
744		case BCODE_STRING:
745			digits = strlen(value->u.string);
746			n = new_number();
747			bn_check(BN_set_word(n->number, digits));
748			break;
749		}
750		stack_free_value(value);
751		push_number(n);
752	}
753}
754
755static void
756to_ascii(void)
757{
758	struct number *n;
759	struct value *value;
760	char str[2];
761
762	value = pop();
763	if (value != NULL) {
764		str[1] = '\0';
765		switch (value->type) {
766		case BCODE_NONE:
767			return;
768		case BCODE_NUMBER:
769			n = value->u.num;
770			normalize(n, 0);
771			if (BN_num_bits(n->number) > 8)
772				bn_check(BN_mask_bits(n->number, 8));
773			str[0] = (char)BN_get_word(n->number);
774			break;
775		case BCODE_STRING:
776			str[0] = value->u.string[0];
777			break;
778		}
779		stack_free_value(value);
780		push_string(bstrdup(str));
781	}
782}
783
784static int
785readreg(void)
786{
787	int ch1, ch2, idx;
788
789	idx = readch();
790	if (idx == 0xff && bmachine.extended_regs) {
791		ch1 = readch();
792		ch2 = readch();
793		if (ch1 == EOF || ch2 == EOF) {
794			warnx("unexpected eof");
795			idx = -1;
796		} else
797			idx = (ch1 << 8) + ch2 + UCHAR_MAX + 1;
798	}
799	if (idx < 0 || (unsigned)idx >= bmachine.reg_array_size) {
800		warnx("internal error: reg num = %d", idx);
801		idx = -1;
802	}
803	return (idx);
804}
805
806static void
807load(void)
808{
809	struct number *n;
810	struct value *v;
811	struct value copy;
812	int idx;
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	struct value *val;
830	int idx;
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	struct stack *stack;
846	struct value *value;
847	int idx;
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	struct value *value;
868	int idx;
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	struct number *inumber, *n;
883	struct stack *stack;
884	struct value *v;
885	struct value copy;
886	u_long idx;
887	int reg;
888
889	reg = readreg();
890	if (reg >= 0) {
891		inumber = pop_number();
892		if (inumber == NULL)
893			return;
894		idx = get_ulong(inumber);
895		if (BN_cmp(inumber->number, &zero) < 0)
896			warnx("negative idx");
897		else if (idx == BN_MASK2 || idx > MAX_ARRAY_INDEX)
898			warnx("idx too big");
899		else {
900			stack = &bmachine.reg[reg];
901			v = frame_retrieve(stack, idx);
902			if (v == NULL || v->type == BCODE_NONE) {
903				n = new_number();
904				bn_check(BN_zero(n->number));
905				push_number(n);
906			}
907			else
908				push(stack_dup_value(v, &copy));
909		}
910		free_number(inumber);
911	}
912}
913
914static void
915store_array(void)
916{
917	struct number *inumber;
918	struct value *value;
919	struct stack *stack;
920	u_long idx;
921	int reg;
922
923	reg = readreg();
924	if (reg >= 0) {
925		inumber = pop_number();
926		if (inumber == NULL)
927			return;
928		value = pop();
929		if (value == NULL) {
930			free_number(inumber);
931			return;
932		}
933		idx = get_ulong(inumber);
934		if (BN_cmp(inumber->number, &zero) < 0) {
935			warnx("negative idx");
936			stack_free_value(value);
937		} else if (idx == BN_MASK2 || idx > MAX_ARRAY_INDEX) {
938			warnx("idx too big");
939			stack_free_value(value);
940		} else {
941			stack = &bmachine.reg[reg];
942			frame_assign(stack, idx, value);
943		}
944		free_number(inumber);
945	}
946}
947
948static void
949push_line(void)
950{
951
952	push_string(read_string(&bmachine.readstack[bmachine.readsp]));
953}
954
955static void
956comment(void)
957{
958
959	free(readline());
960}
961
962static void
963bexec(char *line)
964{
965
966	system(line);
967	free(line);
968}
969
970static void
971badd(void)
972{
973	struct number	*a, *b, *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, *r;
1001
1002	a = pop_number();
1003	if (a == NULL) {
1004		return;
1005	}
1006	b = pop_number();
1007	if (b == NULL) {
1008		push_number(a);
1009		return;
1010	}
1011
1012	r = new_number();
1013
1014	r->scale = max(a->scale, b->scale);
1015	if (r->scale > a->scale)
1016		normalize(a, r->scale);
1017	else if (r->scale > b->scale)
1018		normalize(b, r->scale);
1019	bn_check(BN_sub(r->number, b->number, a->number));
1020	push_number(r);
1021	free_number(a);
1022	free_number(b);
1023}
1024
1025void
1026bmul_number(struct number *r, struct number *a, struct number *b)
1027{
1028	BN_CTX *ctx;
1029
1030	/* Create copies of the scales, since r might be equal to a or b */
1031	u_int ascale = a->scale;
1032	u_int bscale = b->scale;
1033	u_int rscale = ascale + bscale;
1034
1035	ctx = BN_CTX_new();
1036	bn_checkp(ctx);
1037	bn_check(BN_mul(r->number, a->number, b->number, ctx));
1038	BN_CTX_free(ctx);
1039
1040	if (rscale > bmachine.scale && rscale > ascale && rscale > bscale) {
1041		r->scale = rscale;
1042		normalize(r, max(bmachine.scale, max(ascale, bscale)));
1043	} else
1044		r->scale = rscale;
1045}
1046
1047static void
1048bmul(void)
1049{
1050	struct number *a, *b, *r;
1051
1052	a = pop_number();
1053	if (a == NULL) {
1054		return;
1055	}
1056	b = pop_number();
1057	if (b == NULL) {
1058		push_number(a);
1059		return;
1060	}
1061
1062	r = new_number();
1063	bmul_number(r, a, b);
1064
1065	push_number(r);
1066	free_number(a);
1067	free_number(b);
1068}
1069
1070static void
1071bdiv(void)
1072{
1073	struct number *a, *b, *r;
1074	BN_CTX *ctx;
1075	u_int scale;
1076
1077	a = pop_number();
1078	if (a == NULL) {
1079		return;
1080	}
1081	b = pop_number();
1082	if (b == NULL) {
1083		push_number(a);
1084		return;
1085	}
1086
1087	r = new_number();
1088	r->scale = bmachine.scale;
1089	scale = max(a->scale, b->scale);
1090
1091	if (BN_is_zero(a->number))
1092		warnx("divide by zero");
1093	else {
1094		normalize(a, scale);
1095		normalize(b, scale + r->scale);
1096
1097		ctx = BN_CTX_new();
1098		bn_checkp(ctx);
1099		bn_check(BN_div(r->number, NULL, b->number, a->number, ctx));
1100		BN_CTX_free(ctx);
1101	}
1102	push_number(r);
1103	free_number(a);
1104	free_number(b);
1105}
1106
1107static void
1108bmod(void)
1109{
1110	struct number *a, *b, *r;
1111	BN_CTX *ctx;
1112	u_int scale;
1113
1114	a = pop_number();
1115	if (a == NULL) {
1116		return;
1117	}
1118	b = pop_number();
1119	if (b == NULL) {
1120		push_number(a);
1121		return;
1122	}
1123
1124	r = new_number();
1125	scale = max(a->scale, b->scale);
1126	r->scale = max(b->scale, a->scale + bmachine.scale);
1127
1128	if (BN_is_zero(a->number))
1129		warnx("remainder by zero");
1130	else {
1131		normalize(a, scale);
1132		normalize(b, scale + bmachine.scale);
1133
1134		ctx = BN_CTX_new();
1135		bn_checkp(ctx);
1136		bn_check(BN_mod(r->number, b->number, a->number, ctx));
1137		BN_CTX_free(ctx);
1138	}
1139	push_number(r);
1140	free_number(a);
1141	free_number(b);
1142}
1143
1144static void
1145bdivmod(void)
1146{
1147	struct number *a, *b, *rdiv, *rmod;
1148	BN_CTX *ctx;
1149	u_int scale;
1150
1151	a = pop_number();
1152	if (a == NULL) {
1153		return;
1154	}
1155	b = pop_number();
1156	if (b == NULL) {
1157		push_number(a);
1158		return;
1159	}
1160
1161	rdiv = new_number();
1162	rmod = new_number();
1163	rdiv->scale = bmachine.scale;
1164	rmod->scale = max(b->scale, a->scale + bmachine.scale);
1165	scale = max(a->scale, b->scale);
1166
1167	if (BN_is_zero(a->number))
1168		warnx("divide by zero");
1169	else {
1170		normalize(a, scale);
1171		normalize(b, scale + bmachine.scale);
1172
1173		ctx = BN_CTX_new();
1174		bn_checkp(ctx);
1175		bn_check(BN_div(rdiv->number, rmod->number,
1176		    b->number, a->number, ctx));
1177		BN_CTX_free(ctx);
1178	}
1179	push_number(rdiv);
1180	push_number(rmod);
1181	free_number(a);
1182	free_number(b);
1183}
1184
1185static void
1186bexp(void)
1187{
1188	struct number *a, *p, *r;
1189	u_int scale;
1190	bool neg;
1191
1192	p = pop_number();
1193	if (p == NULL) {
1194		return;
1195	}
1196	a = pop_number();
1197	if (a == NULL) {
1198		push_number(p);
1199		return;
1200	}
1201
1202	if (p->scale != 0)
1203		warnx("Runtime warning: non-zero scale in exponent");
1204	normalize(p, 0);
1205
1206	neg = false;
1207	if (BN_cmp(p->number, &zero) < 0) {
1208		neg = true;
1209		negate(p);
1210		scale = bmachine.scale;
1211	} else {
1212		/* Posix bc says min(a.scale * b, max(a.scale, scale) */
1213		u_long b;
1214		u_int m;
1215
1216		b = BN_get_word(p->number);
1217		m = max(a->scale, bmachine.scale);
1218		scale = a->scale * (u_int)b;
1219		if (scale > m || (a->scale > 0 && (b == BN_MASK2 ||
1220		    b > UINT_MAX)))
1221			scale = m;
1222	}
1223
1224	if (BN_is_zero(p->number)) {
1225		r = new_number();
1226		bn_check(BN_one(r->number));
1227		normalize(r, scale);
1228	} else {
1229		while (!BN_is_bit_set(p->number, 0)) {
1230			bmul_number(a, a, a);
1231			bn_check(BN_rshift1(p->number, p->number));
1232		}
1233
1234		r = dup_number(a);
1235		normalize(r, scale);
1236		bn_check(BN_rshift1(p->number, p->number));
1237
1238		while (!BN_is_zero(p->number)) {
1239			bmul_number(a, a, a);
1240			if (BN_is_bit_set(p->number, 0))
1241				bmul_number(r, r, a);
1242			bn_check(BN_rshift1(p->number, p->number));
1243		}
1244
1245		if (neg) {
1246			BN_CTX *ctx;
1247			BIGNUM *one;
1248
1249			one = BN_new();
1250			bn_checkp(one);
1251			bn_check(BN_one(one));
1252			ctx = BN_CTX_new();
1253			bn_checkp(ctx);
1254			scale_number(one, r->scale + scale);
1255			normalize(r, scale);
1256			bn_check(BN_div(r->number, NULL, one, r->number, ctx));
1257			BN_free(one);
1258			BN_CTX_free(ctx);
1259		} else
1260			normalize(r, scale);
1261	}
1262	push_number(r);
1263	free_number(a);
1264	free_number(p);
1265}
1266
1267static bool
1268bsqrt_stop(const BIGNUM *x, const BIGNUM *y, u_int *onecount)
1269{
1270	BIGNUM *r;
1271	bool ret;
1272
1273	r = BN_new();
1274	bn_checkp(r);
1275	bn_check(BN_sub(r, x, y));
1276	if (BN_is_one(r))
1277		(*onecount)++;
1278	ret = BN_is_zero(r);
1279	BN_free(r);
1280	return (ret || *onecount > 1);
1281}
1282
1283static void
1284bsqrt(void)
1285{
1286	struct number *n, *r;
1287	BIGNUM *x, *y;
1288	BN_CTX *ctx;
1289	u_int onecount, scale;
1290
1291	onecount = 0;
1292	n = pop_number();
1293	if (n == NULL) {
1294		return;
1295	}
1296	if (BN_is_zero(n->number)) {
1297		r = new_number();
1298		push_number(r);
1299	} else if (BN_cmp(n->number, &zero) < 0)
1300		warnx("square root of negative number");
1301	else {
1302		scale = max(bmachine.scale, n->scale);
1303		normalize(n, 2*scale);
1304		x = BN_dup(n->number);
1305		bn_checkp(x);
1306		bn_check(BN_rshift(x, x, BN_num_bits(x)/2));
1307		y = BN_new();
1308		bn_checkp(y);
1309		ctx = BN_CTX_new();
1310		bn_checkp(ctx);
1311		for (;;) {
1312			bn_checkp(BN_copy(y, x));
1313			bn_check(BN_div(x, NULL, n->number, x, ctx));
1314			bn_check(BN_add(x, x, y));
1315			bn_check(BN_rshift1(x, x));
1316			if (bsqrt_stop(x, y, &onecount))
1317				break;
1318		}
1319		r = bmalloc(sizeof(*r));
1320		r->scale = scale;
1321		r->number = y;
1322		BN_free(x);
1323		BN_CTX_free(ctx);
1324		push_number(r);
1325	}
1326
1327	free_number(n);
1328}
1329
1330static void
1331not(void)
1332{
1333	struct number *a;
1334
1335	a = pop_number();
1336	if (a == NULL) {
1337		return;
1338	}
1339	a->scale = 0;
1340	bn_check(BN_set_word(a->number, BN_get_word(a->number) ? 0 : 1));
1341	push_number(a);
1342}
1343
1344static void
1345equal(void)
1346{
1347
1348	compare(BCODE_EQUAL);
1349}
1350
1351static void
1352equal_numbers(void)
1353{
1354	struct number *a, *b, *r;
1355
1356	a = pop_number();
1357	if (a == NULL) {
1358		return;
1359	}
1360	b = pop_number();
1361	if (b == NULL) {
1362		push_number(a);
1363		return;
1364	}
1365	r = new_number();
1366	bn_check(BN_set_word(r->number,
1367	    compare_numbers(BCODE_EQUAL, a, b) ? 1 : 0));
1368	push_number(r);
1369}
1370
1371static void
1372less_numbers(void)
1373{
1374	struct number *a, *b, *r;
1375
1376	a = pop_number();
1377	if (a == NULL) {
1378		return;
1379	}
1380	b = pop_number();
1381	if (b == NULL) {
1382		push_number(a);
1383		return;
1384	}
1385	r = new_number();
1386	bn_check(BN_set_word(r->number,
1387	    compare_numbers(BCODE_LESS, a, b) ? 1 : 0));
1388	push_number(r);
1389}
1390
1391static void
1392lesseq_numbers(void)
1393{
1394	struct number *a, *b, *r;
1395
1396	a = pop_number();
1397	if (a == NULL) {
1398		return;
1399	}
1400	b = pop_number();
1401	if (b == NULL) {
1402		push_number(a);
1403		return;
1404	}
1405	r = new_number();
1406	bn_check(BN_set_word(r->number,
1407	    compare_numbers(BCODE_NOT_GREATER, a, b) ? 1 : 0));
1408	push_number(r);
1409}
1410
1411static void
1412not_equal(void)
1413{
1414
1415	compare(BCODE_NOT_EQUAL);
1416}
1417
1418static void
1419less(void)
1420{
1421
1422	compare(BCODE_LESS);
1423}
1424
1425static void
1426not_compare(void)
1427{
1428
1429	switch (readch()) {
1430	case '<':
1431		not_less();
1432		break;
1433	case '>':
1434		not_greater();
1435		break;
1436	case '=':
1437		not_equal();
1438		break;
1439	default:
1440		unreadch();
1441		bexec(readline());
1442		break;
1443	}
1444}
1445
1446static void
1447not_less(void)
1448{
1449
1450	compare(BCODE_NOT_LESS);
1451}
1452
1453static void
1454greater(void)
1455{
1456
1457	compare(BCODE_GREATER);
1458}
1459
1460static void
1461not_greater(void)
1462{
1463
1464	compare(BCODE_NOT_GREATER);
1465}
1466
1467static bool
1468compare_numbers(enum bcode_compare type, struct number *a, struct number *b)
1469{
1470	u_int scale;
1471	int cmp;
1472
1473	scale = max(a->scale, b->scale);
1474
1475	if (scale > a->scale)
1476		normalize(a, scale);
1477	else if (scale > b->scale)
1478		normalize(b, scale);
1479
1480	cmp = BN_cmp(a->number, b->number);
1481
1482	free_number(a);
1483	free_number(b);
1484
1485	switch (type) {
1486	case BCODE_EQUAL:
1487		return (cmp == 0);
1488	case BCODE_NOT_EQUAL:
1489		return (cmp != 0);
1490	case BCODE_LESS:
1491		return (cmp < 0);
1492	case BCODE_NOT_LESS:
1493		return (cmp >= 0);
1494	case BCODE_GREATER:
1495		return (cmp > 0);
1496	case BCODE_NOT_GREATER:
1497		return (cmp <= 0);
1498	}
1499	return (false);
1500}
1501
1502static void
1503compare(enum bcode_compare type)
1504{
1505	struct number *a, *b;
1506	struct value *v;
1507	int idx, elseidx;
1508	bool ok;
1509
1510	elseidx = NO_ELSE;
1511	idx = readreg();
1512	if (readch() == 'e')
1513		elseidx = readreg();
1514	else
1515		unreadch();
1516
1517	a = pop_number();
1518	if (a == NULL)
1519		return;
1520	b = pop_number();
1521	if (b == NULL) {
1522		push_number(a);
1523		return;
1524	}
1525
1526	ok = compare_numbers(type, a, b);
1527
1528	if (!ok && elseidx != NO_ELSE)
1529		idx = elseidx;
1530
1531	if (idx >= 0 && (ok || (!ok && elseidx != NO_ELSE))) {
1532		v = stack_tos(&bmachine.reg[idx]);
1533		if (v == NULL)
1534			warnx("register '%c' (0%o) is empty", idx, idx);
1535		else {
1536			switch(v->type) {
1537			case BCODE_NONE:
1538				warnx("register '%c' (0%o) is empty", idx, idx);
1539				break;
1540			case BCODE_NUMBER:
1541				warn("eval called with non-string argument");
1542				break;
1543			case BCODE_STRING:
1544				eval_string(bstrdup(v->u.string));
1545				break;
1546			}
1547		}
1548	}
1549}
1550
1551
1552static void
1553nop(void)
1554{
1555
1556}
1557
1558static void
1559quit(void)
1560{
1561
1562	if (bmachine.readsp < 2)
1563		exit(0);
1564	src_free();
1565	bmachine.readsp--;
1566	src_free();
1567	bmachine.readsp--;
1568}
1569
1570static void
1571quitN(void)
1572{
1573	struct number *n;
1574	u_long i;
1575
1576	n = pop_number();
1577	if (n == NULL)
1578		return;
1579	i = get_ulong(n);
1580	free_number(n);
1581	if (i == BN_MASK2 || i == 0)
1582		warnx("Q command requires a number >= 1");
1583	else if (bmachine.readsp < i)
1584		warnx("Q command argument exceeded string execution depth");
1585	else {
1586		while (i-- > 0) {
1587			src_free();
1588			bmachine.readsp--;
1589		}
1590	}
1591}
1592
1593static void
1594skipN(void)
1595{
1596	struct number *n;
1597	u_long i;
1598
1599	n = pop_number();
1600	if (n == NULL)
1601		return;
1602	i = get_ulong(n);
1603	if (i == BN_MASK2)
1604		warnx("J command requires a number >= 0");
1605	else if (i > 0 && bmachine.readsp < i)
1606		warnx("J command argument exceeded string execution depth");
1607	else {
1608		while (i-- > 0) {
1609			src_free();
1610			bmachine.readsp--;
1611		}
1612		skip_until_mark();
1613	}
1614}
1615
1616static void
1617skip_until_mark(void)
1618{
1619
1620	for (;;) {
1621		switch (readch()) {
1622		case 'M':
1623			return;
1624		case EOF:
1625			errx(1, "mark not found");
1626			return;
1627		case 'l':
1628		case 'L':
1629		case 's':
1630		case 'S':
1631		case ':':
1632		case ';':
1633		case '<':
1634		case '>':
1635		case '=':
1636			readreg();
1637			if (readch() == 'e')
1638				readreg();
1639			else
1640				unreadch();
1641			break;
1642		case '[':
1643			free(read_string(&bmachine.readstack[bmachine.readsp]));
1644			break;
1645		case '!':
1646			switch (readch()) {
1647				case '<':
1648				case '>':
1649				case '=':
1650					readreg();
1651					if (readch() == 'e')
1652						readreg();
1653					else
1654						unreadch();
1655					break;
1656				default:
1657					free(readline());
1658					break;
1659			}
1660			break;
1661		default:
1662			break;
1663		}
1664	}
1665}
1666
1667static void
1668parse_number(void)
1669{
1670
1671	unreadch();
1672	push_number(readnumber(&bmachine.readstack[bmachine.readsp],
1673	    bmachine.ibase));
1674}
1675
1676static void
1677unknown(void)
1678{
1679	int ch = bmachine.readstack[bmachine.readsp].lastchar;
1680	warnx("%c (0%o) is unimplemented", ch, ch);
1681}
1682
1683static void
1684eval_string(char *p)
1685{
1686	int ch;
1687
1688	if (bmachine.readsp > 0) {
1689		/* Check for tail call. Do not recurse in that case. */
1690		ch = readch();
1691		if (ch == EOF) {
1692			src_free();
1693			src_setstring(&bmachine.readstack[bmachine.readsp], p);
1694			return;
1695		} else
1696			unreadch();
1697	}
1698	if (bmachine.readsp == bmachine.readstack_sz - 1) {
1699		size_t newsz = bmachine.readstack_sz * 2;
1700		struct source *stack;
1701		stack = realloc(bmachine.readstack, newsz *
1702		    sizeof(struct source));
1703		if (stack == NULL)
1704			err(1, "recursion too deep");
1705		bmachine.readstack_sz = newsz;
1706		bmachine.readstack = stack;
1707	}
1708	src_setstring(&bmachine.readstack[++bmachine.readsp], p);
1709}
1710
1711static void
1712eval_line(void)
1713{
1714	/* Always read from stdin */
1715	struct source in;
1716	char *p;
1717
1718	clearerr(stdin);
1719	src_setstream(&in, stdin);
1720	p = (*in.vtable->readline)(&in);
1721	eval_string(p);
1722}
1723
1724static void
1725eval_tos(void)
1726{
1727	char *p;
1728
1729	p = pop_string();
1730	if (p == NULL)
1731		return;
1732	eval_string(p);
1733}
1734
1735void
1736eval(void)
1737{
1738	int ch;
1739
1740	for (;;) {
1741		ch = readch();
1742		if (ch == EOF) {
1743			if (bmachine.readsp == 0)
1744				return;
1745			src_free();
1746			bmachine.readsp--;
1747			continue;
1748		}
1749		if (bmachine.interrupted) {
1750			if (bmachine.readsp > 0) {
1751				src_free();
1752				bmachine.readsp--;
1753				continue;
1754			} else
1755				bmachine.interrupted = false;
1756		}
1757#ifdef DEBUGGING
1758		fprintf(stderr, "# %c\n", ch);
1759		stack_print(stderr, &bmachine.stack, "* ",
1760		    bmachine.obase);
1761		fprintf(stderr, "%zd =>\n", bmachine.readsp);
1762#endif
1763
1764		if (0 <= ch && ch < (signed)UCHAR_MAX)
1765			(*jump_table[ch])();
1766		else
1767			warnx("internal error: opcode %d", ch);
1768
1769#ifdef DEBUGGING
1770		stack_print(stderr, &bmachine.stack, "* ",
1771		    bmachine.obase);
1772		fprintf(stderr, "%zd ==\n", bmachine.readsp);
1773#endif
1774	}
1775}
1776