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