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