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