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