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