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 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 { 'f', print_stack },
202 { 'i', set_ibase },
203 { 'k', set_scale },
204 { 'l', load },
205 { 'n', pop_printn },
206 { 'o', set_obase },
207 { 'p', print_tos },
208 { 'q', quit },
209 { 'r', swap },
210 { 's', store },
211 { 'v', bsqrt },
212 { 'x', eval_tos },
213 { 'z', stackdepth },
214 { '{', lesseq_numbers },
215 { '~', bdivmod }
216 };
217
218 #define JUMP_TABLE_DATA_SIZE \
219 (sizeof(jump_table_data)/sizeof(jump_table_data[0]))
220
221 void
init_bmachine(bool extended_registers)222 init_bmachine(bool extended_registers)
223 {
224 unsigned int i;
225
226 bmachine.extended_regs = extended_registers;
227 bmachine.reg_array_size = bmachine.extended_regs ?
228 REG_ARRAY_SIZE_BIG : REG_ARRAY_SIZE_SMALL;
229
230 bmachine.reg = calloc(bmachine.reg_array_size,
231 sizeof(bmachine.reg[0]));
232 if (bmachine.reg == NULL)
233 err(1, NULL);
234
235 for (i = 0; i < UCHAR_MAX; i++)
236 jump_table[i] = unknown;
237 for (i = 0; i < JUMP_TABLE_DATA_SIZE; i++)
238 jump_table[jump_table_data[i].ch] = jump_table_data[i].f;
239
240 stack_init(&bmachine.stack);
241
242 for (i = 0; i < bmachine.reg_array_size; i++)
243 stack_init(&bmachine.reg[i]);
244
245 bmachine.readstack_sz = READSTACK_SIZE;
246 bmachine.readstack = calloc(sizeof(struct source),
247 bmachine.readstack_sz);
248 if (bmachine.readstack == NULL)
249 err(1, NULL);
250 bmachine.obase = bmachine.ibase = 10;
251 }
252
253 u_int
bmachine_scale(void)254 bmachine_scale(void)
255 {
256 return bmachine.scale;
257 }
258
259 /* Reset the things needed before processing a (new) file */
260 void
reset_bmachine(struct source * src)261 reset_bmachine(struct source *src)
262 {
263
264 bmachine.readsp = 0;
265 bmachine.readstack[0] = *src;
266 }
267
268 static __inline int
readch(void)269 readch(void)
270 {
271 struct source *src = &bmachine.readstack[bmachine.readsp];
272
273 return (src->vtable->readchar(src));
274 }
275
276 static __inline void
unreadch(void)277 unreadch(void)
278 {
279 struct source *src = &bmachine.readstack[bmachine.readsp];
280
281 src->vtable->unreadchar(src);
282 }
283
284 static __inline char *
readline(void)285 readline(void)
286 {
287 struct source *src = &bmachine.readstack[bmachine.readsp];
288
289 return (src->vtable->readline(src));
290 }
291
292 static __inline void
src_free(void)293 src_free(void)
294 {
295 struct source *src = &bmachine.readstack[bmachine.readsp];
296
297 src->vtable->free(src);
298 }
299
300 #ifdef DEBUGGING
301 void
pn(const char * str,const struct number * n)302 pn(const char *str, const struct number *n)
303 {
304 char *p = BN_bn2dec(n->number);
305
306 if (p == NULL)
307 err(1, "BN_bn2dec failed");
308 fputs(str, stderr);
309 fprintf(stderr, " %s (%u)\n" , p, n->scale);
310 OPENSSL_free(p);
311 }
312
313 void
pbn(const char * str,const BIGNUM * n)314 pbn(const char *str, const BIGNUM *n)
315 {
316 char *p = BN_bn2dec(n);
317
318 if (p == NULL)
319 err(1, "BN_bn2dec failed");
320 fputs(str, stderr);
321 fprintf(stderr, " %s\n", p);
322 OPENSSL_free(p);
323 }
324
325 #endif
326
327 static __inline u_int
max(u_int a,u_int b)328 max(u_int a, u_int b)
329 {
330
331 return (a > b ? a : b);
332 }
333
334 static unsigned long factors[] = {
335 0, 10, 100, 1000, 10000, 100000, 1000000, 10000000,
336 100000000, 1000000000
337 };
338
339 void
scale_number(BIGNUM * n,int s)340 scale_number(BIGNUM *n, int s)
341 {
342 unsigned int abs_scale;
343
344 if (s == 0)
345 return;
346
347 abs_scale = s > 0 ? s : -s;
348
349 if (abs_scale < sizeof(factors)/sizeof(factors[0])) {
350 if (s > 0)
351 bn_check(BN_mul_word(n, factors[abs_scale]));
352 else
353 BN_div_word(n, factors[abs_scale]);
354 } else {
355 BIGNUM *a, *p;
356 BN_CTX *ctx;
357
358 a = BN_new();
359 bn_checkp(a);
360 p = BN_new();
361 bn_checkp(p);
362 ctx = BN_CTX_new();
363 bn_checkp(ctx);
364
365 bn_check(BN_set_word(a, 10));
366 bn_check(BN_set_word(p, abs_scale));
367 bn_check(BN_exp(a, a, p, ctx));
368 if (s > 0)
369 bn_check(BN_mul(n, n, a, ctx));
370 else
371 bn_check(BN_div(n, NULL, n, a, ctx));
372 BN_CTX_free(ctx);
373 BN_free(a);
374 BN_free(p);
375 }
376 }
377
378 void
split_number(const struct number * n,BIGNUM * i,BIGNUM * f)379 split_number(const struct number *n, BIGNUM *i, BIGNUM *f)
380 {
381 u_long rem;
382
383 bn_checkp(BN_copy(i, n->number));
384
385 if (n->scale == 0 && f != NULL)
386 bn_check(BN_zero(f));
387 else if (n->scale < sizeof(factors)/sizeof(factors[0])) {
388 rem = BN_div_word(i, factors[n->scale]);
389 if (f != NULL)
390 bn_check(BN_set_word(f, rem));
391 } else {
392 BIGNUM *a, *p;
393 BN_CTX *ctx;
394
395 a = BN_new();
396 bn_checkp(a);
397 p = BN_new();
398 bn_checkp(p);
399 ctx = BN_CTX_new();
400 bn_checkp(ctx);
401
402 bn_check(BN_set_word(a, 10));
403 bn_check(BN_set_word(p, n->scale));
404 bn_check(BN_exp(a, a, p, ctx));
405 bn_check(BN_div(i, f, n->number, a, ctx));
406 BN_CTX_free(ctx);
407 BN_free(a);
408 BN_free(p);
409 }
410 }
411
412 void
normalize(struct number * n,u_int s)413 normalize(struct number *n, u_int s)
414 {
415
416 scale_number(n->number, s - n->scale);
417 n->scale = s;
418 }
419
420 static u_long
get_ulong(struct number * n)421 get_ulong(struct number *n)
422 {
423
424 normalize(n, 0);
425 return (BN_get_word(n->number));
426 }
427
428 void
negate(struct number * n)429 negate(struct number *n)
430 {
431 BN_set_negative(n->number, !BN_is_negative(n->number));
432 }
433
434 static __inline void
push_number(struct number * n)435 push_number(struct number *n)
436 {
437
438 stack_pushnumber(&bmachine.stack, n);
439 }
440
441 static __inline void
push_string(char * string)442 push_string(char *string)
443 {
444
445 stack_pushstring(&bmachine.stack, string);
446 }
447
448 static __inline void
push(struct value * v)449 push(struct value *v)
450 {
451
452 stack_push(&bmachine.stack, v);
453 }
454
455 static __inline struct value *
tos(void)456 tos(void)
457 {
458
459 return (stack_tos(&bmachine.stack));
460 }
461
462 static __inline struct value *
pop(void)463 pop(void)
464 {
465
466 return (stack_pop(&bmachine.stack));
467 }
468
469 static __inline struct number *
pop_number(void)470 pop_number(void)
471 {
472
473 return (stack_popnumber(&bmachine.stack));
474 }
475
476 static __inline char *
pop_string(void)477 pop_string(void)
478 {
479
480 return (stack_popstring(&bmachine.stack));
481 }
482
483 static __inline void
clear_stack(void)484 clear_stack(void)
485 {
486
487 stack_clear(&bmachine.stack);
488 }
489
490 static __inline void
print_stack(void)491 print_stack(void)
492 {
493
494 stack_print(stdout, &bmachine.stack, "", bmachine.obase);
495 }
496
497 static __inline void
print_tos(void)498 print_tos(void)
499 {
500 struct value *value = tos();
501
502 if (value != NULL) {
503 print_value(stdout, value, "", bmachine.obase);
504 putchar('\n');
505 }
506 else
507 warnx("stack empty");
508 }
509
510 static void
pop_print(void)511 pop_print(void)
512 {
513 struct value *value = pop();
514
515 if (value != NULL) {
516 switch (value->type) {
517 case BCODE_NONE:
518 break;
519 case BCODE_NUMBER:
520 normalize(value->u.num, 0);
521 print_ascii(stdout, value->u.num);
522 fflush(stdout);
523 break;
524 case BCODE_STRING:
525 fputs(value->u.string, stdout);
526 fflush(stdout);
527 break;
528 }
529 stack_free_value(value);
530 }
531 }
532
533 static void
pop_printn(void)534 pop_printn(void)
535 {
536 struct value *value = pop();
537
538 if (value != NULL) {
539 print_value(stdout, value, "", bmachine.obase);
540 fflush(stdout);
541 stack_free_value(value);
542 }
543 }
544
545 static __inline void
dup(void)546 dup(void)
547 {
548
549 stack_dup(&bmachine.stack);
550 }
551
552 static void
swap(void)553 swap(void)
554 {
555
556 stack_swap(&bmachine.stack);
557 }
558
559 static void
drop(void)560 drop(void)
561 {
562 struct value *v = pop();
563 if (v != NULL)
564 stack_free_value(v);
565 }
566
567 static void
get_scale(void)568 get_scale(void)
569 {
570 struct number *n;
571
572 n = new_number();
573 bn_check(BN_set_word(n->number, bmachine.scale));
574 push_number(n);
575 }
576
577 static void
set_scale(void)578 set_scale(void)
579 {
580 struct number *n;
581 u_long scale;
582
583 n = pop_number();
584 if (n != NULL) {
585 if (BN_is_negative(n->number))
586 warnx("scale must be a nonnegative number");
587 else {
588 scale = get_ulong(n);
589 if (scale != BN_MASK2 && scale <= UINT_MAX)
590 bmachine.scale = (u_int)scale;
591 else
592 warnx("scale too large");
593 }
594 free_number(n);
595 }
596 }
597
598 static void
get_obase(void)599 get_obase(void)
600 {
601 struct number *n;
602
603 n = new_number();
604 bn_check(BN_set_word(n->number, bmachine.obase));
605 push_number(n);
606 }
607
608 static void
set_obase(void)609 set_obase(void)
610 {
611 struct number *n;
612 u_long base;
613
614 n = pop_number();
615 if (n != NULL) {
616 base = get_ulong(n);
617 if (base != BN_MASK2 && base > 1 && base <= UINT_MAX)
618 bmachine.obase = (u_int)base;
619 else
620 warnx("output base must be a number greater than 1");
621 free_number(n);
622 }
623 }
624
625 static void
get_ibase(void)626 get_ibase(void)
627 {
628 struct number *n;
629
630 n = new_number();
631 bn_check(BN_set_word(n->number, bmachine.ibase));
632 push_number(n);
633 }
634
635 static void
set_ibase(void)636 set_ibase(void)
637 {
638 struct number *n;
639 u_long base;
640
641 n = pop_number();
642 if (n != NULL) {
643 base = get_ulong(n);
644 if (base != BN_MASK2 && 2 <= base && base <= 16)
645 bmachine.ibase = (u_int)base;
646 else
647 warnx("input base must be a number between 2 and 16 "
648 "(inclusive)");
649 free_number(n);
650 }
651 }
652
653 static void
stackdepth(void)654 stackdepth(void)
655 {
656 struct number *n;
657 size_t i;
658
659 i = stack_size(&bmachine.stack);
660 n = new_number();
661 bn_check(BN_set_word(n->number, i));
662 push_number(n);
663 }
664
665 static void
push_scale(void)666 push_scale(void)
667 {
668 struct number *n;
669 struct value *value;
670 u_int scale = 0;
671
672 value = pop();
673 if (value != NULL) {
674 switch (value->type) {
675 case BCODE_NONE:
676 return;
677 case BCODE_NUMBER:
678 scale = value->u.num->scale;
679 break;
680 case BCODE_STRING:
681 break;
682 }
683 stack_free_value(value);
684 n = new_number();
685 bn_check(BN_set_word(n->number, scale));
686 push_number(n);
687 }
688 }
689
690 static u_int
count_digits(const struct number * n)691 count_digits(const struct number *n)
692 {
693 struct number *int_part, *fract_part;
694 u_int i;
695
696 if (BN_is_zero(n->number))
697 return n->scale ? n->scale : 1;
698
699 int_part = new_number();
700 fract_part = new_number();
701 fract_part->scale = n->scale;
702 split_number(n, int_part->number, fract_part->number);
703
704 i = 0;
705 while (!BN_is_zero(int_part->number)) {
706 BN_div_word(int_part->number, 10);
707 i++;
708 }
709 free_number(int_part);
710 free_number(fract_part);
711 return (i + n->scale);
712 }
713
714 static void
num_digits(void)715 num_digits(void)
716 {
717 struct number *n = NULL;
718 struct value *value;
719 size_t digits;
720
721 value = pop();
722 if (value != NULL) {
723 switch (value->type) {
724 case BCODE_NONE:
725 return;
726 case BCODE_NUMBER:
727 digits = count_digits(value->u.num);
728 n = new_number();
729 bn_check(BN_set_word(n->number, digits));
730 break;
731 case BCODE_STRING:
732 digits = strlen(value->u.string);
733 n = new_number();
734 bn_check(BN_set_word(n->number, digits));
735 break;
736 }
737 stack_free_value(value);
738 push_number(n);
739 }
740 }
741
742 static void
to_ascii(void)743 to_ascii(void)
744 {
745 struct number *n;
746 struct value *value;
747 char str[2];
748
749 value = pop();
750 if (value != NULL) {
751 str[1] = '\0';
752 switch (value->type) {
753 case BCODE_NONE:
754 return;
755 case BCODE_NUMBER:
756 n = value->u.num;
757 normalize(n, 0);
758 if (BN_num_bits(n->number) > 8)
759 bn_check(BN_mask_bits(n->number, 8));
760 str[0] = (char)BN_get_word(n->number);
761 break;
762 case BCODE_STRING:
763 str[0] = value->u.string[0];
764 break;
765 }
766 stack_free_value(value);
767 push_string(bstrdup(str));
768 }
769 }
770
771 static int
readreg(void)772 readreg(void)
773 {
774 int ch1, ch2, idx;
775
776 idx = readch();
777 if (idx == 0xff && bmachine.extended_regs) {
778 ch1 = readch();
779 ch2 = readch();
780 if (ch1 == EOF || ch2 == EOF) {
781 warnx("unexpected eof");
782 idx = -1;
783 } else
784 idx = (ch1 << 8) + ch2 + UCHAR_MAX + 1;
785 }
786 if (idx < 0 || (unsigned)idx >= bmachine.reg_array_size) {
787 warnx("internal error: reg num = %d", idx);
788 idx = -1;
789 }
790 return (idx);
791 }
792
793 static void
load(void)794 load(void)
795 {
796 struct number *n;
797 struct value *v;
798 struct value copy;
799 int idx;
800
801 idx = readreg();
802 if (idx >= 0) {
803 v = stack_tos(&bmachine.reg[idx]);
804 if (v == NULL) {
805 n = new_number();
806 bn_check(BN_zero(n->number));
807 push_number(n);
808 } else
809 push(stack_dup_value(v, ©));
810 }
811 }
812
813 static void
store(void)814 store(void)
815 {
816 struct value *val;
817 int idx;
818
819 idx = readreg();
820 if (idx >= 0) {
821 val = pop();
822 if (val == NULL) {
823 return;
824 }
825 stack_set_tos(&bmachine.reg[idx], val);
826 }
827 }
828
829 static void
load_stack(void)830 load_stack(void)
831 {
832 struct stack *stack;
833 struct value *value;
834 int idx;
835
836 idx = readreg();
837 if (idx >= 0) {
838 stack = &bmachine.reg[idx];
839 value = NULL;
840 if (stack_size(stack) > 0) {
841 value = stack_pop(stack);
842 }
843 if (value != NULL)
844 push(value);
845 else
846 warnx("stack register '%c' (0%o) is empty",
847 idx, idx);
848 }
849 }
850
851 static void
store_stack(void)852 store_stack(void)
853 {
854 struct value *value;
855 int idx;
856
857 idx = readreg();
858 if (idx >= 0) {
859 value = pop();
860 if (value == NULL)
861 return;
862 stack_push(&bmachine.reg[idx], value);
863 }
864 }
865
866 static void
load_array(void)867 load_array(void)
868 {
869 struct number *inumber, *n;
870 struct stack *stack;
871 struct value *v;
872 struct value copy;
873 u_long idx;
874 int reg;
875
876 reg = readreg();
877 if (reg >= 0) {
878 inumber = pop_number();
879 if (inumber == NULL)
880 return;
881 idx = get_ulong(inumber);
882 if (BN_is_negative(inumber->number))
883 warnx("negative idx");
884 else if (idx == BN_MASK2 || idx > MAX_ARRAY_INDEX)
885 warnx("idx too big");
886 else {
887 stack = &bmachine.reg[reg];
888 v = frame_retrieve(stack, idx);
889 if (v == NULL || v->type == BCODE_NONE) {
890 n = new_number();
891 bn_check(BN_zero(n->number));
892 push_number(n);
893 }
894 else
895 push(stack_dup_value(v, ©));
896 }
897 free_number(inumber);
898 }
899 }
900
901 static void
store_array(void)902 store_array(void)
903 {
904 struct number *inumber;
905 struct value *value;
906 struct stack *stack;
907 u_long idx;
908 int reg;
909
910 reg = readreg();
911 if (reg >= 0) {
912 inumber = pop_number();
913 if (inumber == NULL)
914 return;
915 value = pop();
916 if (value == NULL) {
917 free_number(inumber);
918 return;
919 }
920 idx = get_ulong(inumber);
921 if (BN_is_negative(inumber->number)) {
922 warnx("negative idx");
923 stack_free_value(value);
924 } else if (idx == BN_MASK2 || idx > MAX_ARRAY_INDEX) {
925 warnx("idx too big");
926 stack_free_value(value);
927 } else {
928 stack = &bmachine.reg[reg];
929 frame_assign(stack, idx, value);
930 }
931 free_number(inumber);
932 }
933 }
934
935 static void
push_line(void)936 push_line(void)
937 {
938
939 push_string(read_string(&bmachine.readstack[bmachine.readsp]));
940 }
941
942 static void
comment(void)943 comment(void)
944 {
945
946 free(readline());
947 }
948
949 static void
bexec(char * line)950 bexec(char *line)
951 {
952
953 system(line);
954 free(line);
955 }
956
957 static void
badd(void)958 badd(void)
959 {
960 struct number *a, *b, *r;
961
962 a = pop_number();
963 if (a == NULL) {
964 return;
965 }
966 b = pop_number();
967 if (b == NULL) {
968 push_number(a);
969 return;
970 }
971
972 r = new_number();
973 r->scale = max(a->scale, b->scale);
974 if (r->scale > a->scale)
975 normalize(a, r->scale);
976 else if (r->scale > b->scale)
977 normalize(b, r->scale);
978 bn_check(BN_add(r->number, a->number, b->number));
979 push_number(r);
980 free_number(a);
981 free_number(b);
982 }
983
984 static void
bsub(void)985 bsub(void)
986 {
987 struct number *a, *b, *r;
988
989 a = pop_number();
990 if (a == NULL) {
991 return;
992 }
993 b = pop_number();
994 if (b == NULL) {
995 push_number(a);
996 return;
997 }
998
999 r = new_number();
1000
1001 r->scale = max(a->scale, b->scale);
1002 if (r->scale > a->scale)
1003 normalize(a, r->scale);
1004 else if (r->scale > b->scale)
1005 normalize(b, r->scale);
1006 bn_check(BN_sub(r->number, b->number, a->number));
1007 push_number(r);
1008 free_number(a);
1009 free_number(b);
1010 }
1011
1012 void
bmul_number(struct number * r,struct number * a,struct number * b,u_int scale)1013 bmul_number(struct number *r, struct number *a, struct number *b, u_int scale)
1014 {
1015 BN_CTX *ctx;
1016
1017 /* Create copies of the scales, since r might be equal to a or b */
1018 u_int ascale = a->scale;
1019 u_int bscale = b->scale;
1020 u_int rscale = ascale + bscale;
1021
1022 ctx = BN_CTX_new();
1023 bn_checkp(ctx);
1024 bn_check(BN_mul(r->number, a->number, b->number, ctx));
1025 BN_CTX_free(ctx);
1026
1027 r->scale = rscale;
1028 if (rscale > bmachine.scale && rscale > ascale && rscale > bscale)
1029 normalize(r, max(scale, max(ascale, bscale)));
1030 }
1031
1032 static void
bmul(void)1033 bmul(void)
1034 {
1035 struct number *a, *b, *r;
1036
1037 a = pop_number();
1038 if (a == NULL) {
1039 return;
1040 }
1041 b = pop_number();
1042 if (b == NULL) {
1043 push_number(a);
1044 return;
1045 }
1046
1047 r = new_number();
1048 bmul_number(r, a, b, bmachine.scale);
1049
1050 push_number(r);
1051 free_number(a);
1052 free_number(b);
1053 }
1054
1055 static void
bdiv(void)1056 bdiv(void)
1057 {
1058 struct number *a, *b, *r;
1059 BN_CTX *ctx;
1060 u_int scale;
1061
1062 a = pop_number();
1063 if (a == NULL) {
1064 return;
1065 }
1066 b = pop_number();
1067 if (b == NULL) {
1068 push_number(a);
1069 return;
1070 }
1071
1072 r = new_number();
1073 r->scale = bmachine.scale;
1074 scale = max(a->scale, b->scale);
1075
1076 if (BN_is_zero(a->number))
1077 warnx("divide by zero");
1078 else {
1079 normalize(a, scale);
1080 normalize(b, scale + r->scale);
1081
1082 ctx = BN_CTX_new();
1083 bn_checkp(ctx);
1084 bn_check(BN_div(r->number, NULL, b->number, a->number, ctx));
1085 BN_CTX_free(ctx);
1086 }
1087 push_number(r);
1088 free_number(a);
1089 free_number(b);
1090 }
1091
1092 static void
bmod(void)1093 bmod(void)
1094 {
1095 struct number *a, *b, *r;
1096 BN_CTX *ctx;
1097 u_int scale;
1098
1099 a = pop_number();
1100 if (a == NULL) {
1101 return;
1102 }
1103 b = pop_number();
1104 if (b == NULL) {
1105 push_number(a);
1106 return;
1107 }
1108
1109 r = new_number();
1110 scale = max(a->scale, b->scale);
1111 r->scale = max(b->scale, a->scale + bmachine.scale);
1112
1113 if (BN_is_zero(a->number))
1114 warnx("remainder by zero");
1115 else {
1116 normalize(a, scale);
1117 normalize(b, scale + bmachine.scale);
1118
1119 ctx = BN_CTX_new();
1120 bn_checkp(ctx);
1121 bn_check(BN_mod(r->number, b->number, a->number, ctx));
1122 BN_CTX_free(ctx);
1123 }
1124 push_number(r);
1125 free_number(a);
1126 free_number(b);
1127 }
1128
1129 static void
bdivmod(void)1130 bdivmod(void)
1131 {
1132 struct number *a, *b, *rdiv, *rmod;
1133 BN_CTX *ctx;
1134 u_int scale;
1135
1136 a = pop_number();
1137 if (a == NULL) {
1138 return;
1139 }
1140 b = pop_number();
1141 if (b == NULL) {
1142 push_number(a);
1143 return;
1144 }
1145
1146 rdiv = new_number();
1147 rmod = new_number();
1148 rdiv->scale = bmachine.scale;
1149 rmod->scale = max(b->scale, a->scale + bmachine.scale);
1150 scale = max(a->scale, b->scale);
1151
1152 if (BN_is_zero(a->number))
1153 warnx("divide by zero");
1154 else {
1155 normalize(a, scale);
1156 normalize(b, scale + bmachine.scale);
1157
1158 ctx = BN_CTX_new();
1159 bn_checkp(ctx);
1160 bn_check(BN_div(rdiv->number, rmod->number,
1161 b->number, a->number, ctx));
1162 BN_CTX_free(ctx);
1163 }
1164 push_number(rdiv);
1165 push_number(rmod);
1166 free_number(a);
1167 free_number(b);
1168 }
1169
1170 static void
bexp(void)1171 bexp(void)
1172 {
1173 struct number *a, *p;
1174 struct number *r;
1175 bool neg;
1176 u_int rscale;
1177
1178 p = pop_number();
1179 if (p == NULL) {
1180 return;
1181 }
1182 a = pop_number();
1183 if (a == NULL) {
1184 push_number(p);
1185 return;
1186 }
1187
1188 if (p->scale != 0) {
1189 BIGNUM *i, *f;
1190 i = BN_new();
1191 bn_checkp(i);
1192 f = BN_new();
1193 bn_checkp(f);
1194 split_number(p, i, f);
1195 if (!BN_is_zero(f))
1196 warnx("Runtime warning: non-zero fractional part in exponent");
1197 BN_free(i);
1198 BN_free(f);
1199 }
1200
1201 normalize(p, 0);
1202
1203 neg = false;
1204 if (BN_is_negative(p->number)) {
1205 neg = true;
1206 negate(p);
1207 rscale = bmachine.scale;
1208 } else {
1209 /* Posix bc says min(a.scale * b, max(a.scale, scale) */
1210 u_long b;
1211 u_int m;
1212
1213 b = BN_get_word(p->number);
1214 m = max(a->scale, bmachine.scale);
1215 rscale = a->scale * (u_int)b;
1216 if (rscale > m || (a->scale > 0 && (b == BN_MASK2 ||
1217 b > UINT_MAX)))
1218 rscale = m;
1219 }
1220
1221 if (BN_is_zero(p->number)) {
1222 r = new_number();
1223 bn_check(BN_one(r->number));
1224 normalize(r, rscale);
1225 } else {
1226 u_int ascale, mscale;
1227
1228 ascale = a->scale;
1229 while (!BN_is_bit_set(p->number, 0)) {
1230 ascale *= 2;
1231 bmul_number(a, a, a, ascale);
1232 bn_check(BN_rshift1(p->number, p->number));
1233 }
1234
1235 r = dup_number(a);
1236 bn_check(BN_rshift1(p->number, p->number));
1237
1238 mscale = ascale;
1239 while (!BN_is_zero(p->number)) {
1240 ascale *= 2;
1241 bmul_number(a, a, a, ascale);
1242 if (BN_is_bit_set(p->number, 0)) {
1243 mscale += ascale;
1244 bmul_number(r, r, a, mscale);
1245 }
1246 bn_check(BN_rshift1(p->number, p->number));
1247 }
1248
1249 if (neg) {
1250 BN_CTX *ctx;
1251 BIGNUM *one;
1252
1253 one = BN_new();
1254 bn_checkp(one);
1255 bn_check(BN_one(one));
1256 ctx = BN_CTX_new();
1257 bn_checkp(ctx);
1258 scale_number(one, r->scale + rscale);
1259
1260 if (BN_is_zero(r->number))
1261 warnx("divide by zero");
1262 else
1263 bn_check(BN_div(r->number, NULL, one,
1264 r->number, ctx));
1265 BN_free(one);
1266 BN_CTX_free(ctx);
1267 r->scale = rscale;
1268 } else
1269 normalize(r, rscale);
1270 }
1271 push_number(r);
1272 free_number(a);
1273 free_number(p);
1274 }
1275
1276 static bool
bsqrt_stop(const BIGNUM * x,const BIGNUM * y,u_int * onecount)1277 bsqrt_stop(const BIGNUM *x, const BIGNUM *y, u_int *onecount)
1278 {
1279 BIGNUM *r;
1280 bool ret;
1281
1282 r = BN_new();
1283 bn_checkp(r);
1284 bn_check(BN_sub(r, x, y));
1285 if (BN_is_one(r))
1286 (*onecount)++;
1287 ret = BN_is_zero(r);
1288 BN_free(r);
1289 return (ret || *onecount > 1);
1290 }
1291
1292 static void
bsqrt(void)1293 bsqrt(void)
1294 {
1295 struct number *n, *r;
1296 BIGNUM *x, *y;
1297 BN_CTX *ctx;
1298 u_int onecount, scale;
1299
1300 onecount = 0;
1301 n = pop_number();
1302 if (n == NULL) {
1303 return;
1304 }
1305 if (BN_is_zero(n->number)) {
1306 r = new_number();
1307 push_number(r);
1308 } else if (BN_is_negative(n->number))
1309 warnx("square root of negative number");
1310 else {
1311 scale = max(bmachine.scale, n->scale);
1312 normalize(n, 2*scale);
1313 x = BN_dup(n->number);
1314 bn_checkp(x);
1315 bn_check(BN_rshift(x, x, BN_num_bits(x)/2));
1316 y = BN_new();
1317 bn_checkp(y);
1318 ctx = BN_CTX_new();
1319 bn_checkp(ctx);
1320 for (;;) {
1321 bn_checkp(BN_copy(y, x));
1322 bn_check(BN_div(x, NULL, n->number, x, ctx));
1323 bn_check(BN_add(x, x, y));
1324 bn_check(BN_rshift1(x, x));
1325 if (bsqrt_stop(x, y, &onecount))
1326 break;
1327 }
1328 r = bmalloc(sizeof(*r));
1329 r->scale = scale;
1330 r->number = y;
1331 BN_free(x);
1332 BN_CTX_free(ctx);
1333 push_number(r);
1334 }
1335
1336 free_number(n);
1337 }
1338
1339 static void
not(void)1340 not(void)
1341 {
1342 struct number *a;
1343
1344 a = pop_number();
1345 if (a == NULL) {
1346 return;
1347 }
1348 a->scale = 0;
1349 bn_check(BN_set_word(a->number, BN_get_word(a->number) ? 0 : 1));
1350 push_number(a);
1351 }
1352
1353 static void
equal(void)1354 equal(void)
1355 {
1356
1357 compare(BCODE_EQUAL);
1358 }
1359
1360 static void
equal_numbers(void)1361 equal_numbers(void)
1362 {
1363 struct number *a, *b, *r;
1364
1365 a = pop_number();
1366 if (a == NULL) {
1367 return;
1368 }
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 }
1389 b = pop_number();
1390 if (b == NULL) {
1391 push_number(a);
1392 return;
1393 }
1394 r = new_number();
1395 bn_check(BN_set_word(r->number,
1396 compare_numbers(BCODE_LESS, a, b) ? 1 : 0));
1397 push_number(r);
1398 }
1399
1400 static void
lesseq_numbers(void)1401 lesseq_numbers(void)
1402 {
1403 struct number *a, *b, *r;
1404
1405 a = pop_number();
1406 if (a == NULL) {
1407 return;
1408 }
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 == BN_MASK2 || 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 == BN_MASK2)
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));
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 = realloc(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 return;
1741 eval_string(p);
1742 }
1743
1744 void
eval(void)1745 eval(void)
1746 {
1747 int ch;
1748
1749 for (;;) {
1750 ch = readch();
1751 if (ch == EOF) {
1752 if (bmachine.readsp == 0)
1753 return;
1754 src_free();
1755 bmachine.readsp--;
1756 continue;
1757 }
1758 #ifdef DEBUGGING
1759 fprintf(stderr, "# %c\n", ch);
1760 stack_print(stderr, &bmachine.stack, "* ",
1761 bmachine.obase);
1762 fprintf(stderr, "%zd =>\n", bmachine.readsp);
1763 #endif
1764
1765 if (0 <= ch && ch < (signed)UCHAR_MAX)
1766 (*jump_table[ch])();
1767 else
1768 warnx("internal error: opcode %d", ch);
1769
1770 #ifdef DEBUGGING
1771 stack_print(stderr, &bmachine.stack, "* ",
1772 bmachine.obase);
1773 fprintf(stderr, "%zd ==\n", bmachine.readsp);
1774 #endif
1775 }
1776 }
1777