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