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