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