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