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