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