bcode.c (31689B)
1 /* $OpenBSD: bcode.c,v 1.46 2014/10/08 03:59:56 doug Exp $ */ 2 3 /* 4 * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net> 5 * 6 * Permission to use, copy, modify, and distribute this software for any 7 * purpose with or without fee is hereby granted, provided that the above 8 * copyright notice and this permission notice appear in all copies. 9 * 10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 17 */ 18 19 #include <openssl/ssl.h> 20 #include <err.h> 21 #include <limits.h> 22 #include <signal.h> 23 #include <stdio.h> 24 #include <stdlib.h> 25 #include <string.h> 26 27 #include "extern.h" 28 29 /* #define DEBUGGING */ 30 31 #define MAX_ARRAY_INDEX 2048 32 #define READSTACK_SIZE 8 33 34 #define NO_ELSE -2 /* -1 is EOF */ 35 #define REG_ARRAY_SIZE_SMALL (UCHAR_MAX + 1) 36 #define REG_ARRAY_SIZE_BIG (UCHAR_MAX + 1 + USHRT_MAX + 1) 37 38 struct bmachine { 39 struct stack stack; 40 u_int scale; 41 u_int obase; 42 u_int ibase; 43 size_t readsp; 44 bool extended_regs; 45 size_t reg_array_size; 46 struct stack *reg; 47 volatile sig_atomic_t interrupted; 48 struct source *readstack; 49 size_t readstack_sz; 50 }; 51 52 static struct bmachine bmachine; 53 static void sighandler(int); 54 55 static __inline int readch(void); 56 static __inline void unreadch(void); 57 static __inline char *readline(void); 58 static __inline void src_free(void); 59 60 static __inline u_int max(u_int, u_int); 61 static u_long get_ulong(struct number *); 62 63 static __inline void push_number(struct number *); 64 static __inline void push_string(char *); 65 static __inline void push(struct value *); 66 static __inline struct value *tos(void); 67 static __inline struct number *pop_number(void); 68 static __inline char *pop_string(void); 69 static __inline void clear_stack(void); 70 static __inline void print_tos(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 bexec(char *); 92 static void badd(void); 93 static void bsub(void); 94 static void bmul(void); 95 static void bdiv(void); 96 static void bmod(void); 97 static void bdivmod(void); 98 static void bexp(void); 99 static bool bsqrt_stop(const BIGNUM *, const BIGNUM *, u_int *); 100 static void bsqrt(void); 101 static void not(void); 102 static void equal_numbers(void); 103 static void less_numbers(void); 104 static void lesseq_numbers(void); 105 static void equal(void); 106 static void not_equal(void); 107 static void less(void); 108 static void not_less(void); 109 static void greater(void); 110 static void not_greater(void); 111 static void not_compare(void); 112 static bool compare_numbers(enum bcode_compare, struct number *, 113 struct number *); 114 static void compare(enum bcode_compare); 115 static int readreg(void); 116 static void load(void); 117 static void store(void); 118 static void load_stack(void); 119 static void store_stack(void); 120 static void load_array(void); 121 static void store_array(void); 122 static void nop(void); 123 static void quit(void); 124 static void quitN(void); 125 static void skipN(void); 126 static void skip_until_mark(void); 127 static void parse_number(void); 128 static void unknown(void); 129 static void eval_string(char *); 130 static void eval_line(void); 131 static void eval_tos(void); 132 133 134 typedef void (*opcode_function)(void); 135 136 struct jump_entry { 137 u_char ch; 138 opcode_function f; 139 }; 140 141 static opcode_function jump_table[UCHAR_MAX]; 142 143 static const struct jump_entry jump_table_data[] = { 144 { ' ', nop }, 145 { '!', not_compare }, 146 { '#', comment }, 147 { '%', bmod }, 148 { '(', less_numbers }, 149 { '*', bmul }, 150 { '+', badd }, 151 { '-', bsub }, 152 { '.', parse_number }, 153 { '/', bdiv }, 154 { '0', parse_number }, 155 { '1', parse_number }, 156 { '2', parse_number }, 157 { '3', parse_number }, 158 { '4', parse_number }, 159 { '5', parse_number }, 160 { '6', parse_number }, 161 { '7', parse_number }, 162 { '8', parse_number }, 163 { '9', parse_number }, 164 { ':', store_array }, 165 { ';', load_array }, 166 { '<', less }, 167 { '=', equal }, 168 { '>', greater }, 169 { '?', eval_line }, 170 { 'A', parse_number }, 171 { 'B', parse_number }, 172 { 'C', parse_number }, 173 { 'D', parse_number }, 174 { 'E', parse_number }, 175 { 'F', parse_number }, 176 { 'G', equal_numbers }, 177 { 'I', get_ibase }, 178 { 'J', skipN }, 179 { 'K', get_scale }, 180 { 'L', load_stack }, 181 { 'M', nop }, 182 { 'N', not }, 183 { 'O', get_obase }, 184 { 'P', pop_print }, 185 { 'Q', quitN }, 186 { 'R', drop }, 187 { 'S', store_stack }, 188 { 'X', push_scale }, 189 { 'Z', num_digits }, 190 { '[', push_line }, 191 { '\f', nop }, 192 { '\n', nop }, 193 { '\r', nop }, 194 { '\t', nop }, 195 { '^', bexp }, 196 { '_', parse_number }, 197 { 'a', to_ascii }, 198 { 'c', clear_stack }, 199 { 'd', dup }, 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_zero(f)); 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 pop_print(void) 503 { 504 struct value *value = pop(); 505 506 if (value != NULL) { 507 switch (value->type) { 508 case BCODE_NONE: 509 break; 510 case BCODE_NUMBER: 511 normalize(value->u.num, 0); 512 print_ascii(stdout, value->u.num); 513 (void)fflush(stdout); 514 break; 515 case BCODE_STRING: 516 (void)fputs(value->u.string, stdout); 517 (void)fflush(stdout); 518 break; 519 } 520 stack_free_value(value); 521 } 522 } 523 524 static void 525 pop_printn(void) 526 { 527 struct value *value = pop(); 528 529 if (value != NULL) { 530 print_value(stdout, value, "", bmachine.obase); 531 (void)fflush(stdout); 532 stack_free_value(value); 533 } 534 } 535 536 static __inline void 537 dup(void) 538 { 539 stack_dup(&bmachine.stack); 540 } 541 542 static void 543 swap(void) 544 { 545 stack_swap(&bmachine.stack); 546 } 547 548 static void 549 drop(void) 550 { 551 struct value *v = pop(); 552 if (v != NULL) 553 stack_free_value(v); 554 } 555 556 static void 557 get_scale(void) 558 { 559 struct number *n; 560 561 n = new_number(); 562 bn_check(BN_set_word(n->number, bmachine.scale)); 563 push_number(n); 564 } 565 566 static void 567 set_scale(void) 568 { 569 struct number *n; 570 u_long scale; 571 572 n = pop_number(); 573 if (n != NULL) { 574 if (BN_is_negative(n->number)) 575 warnx("scale must be a nonnegative number"); 576 else { 577 scale = get_ulong(n); 578 if (scale != BN_MASK2 && scale <= UINT_MAX) 579 bmachine.scale = (u_int)scale; 580 else 581 warnx("scale too large"); 582 } 583 free_number(n); 584 } 585 } 586 587 static void 588 get_obase(void) 589 { 590 struct number *n; 591 592 n = new_number(); 593 bn_check(BN_set_word(n->number, bmachine.obase)); 594 push_number(n); 595 } 596 597 static void 598 set_obase(void) 599 { 600 struct number *n; 601 u_long base; 602 603 n = pop_number(); 604 if (n != NULL) { 605 base = get_ulong(n); 606 if (base != BN_MASK2 && base > 1 && base <= UINT_MAX) 607 bmachine.obase = (u_int)base; 608 else 609 warnx("output base must be a number greater than 1"); 610 free_number(n); 611 } 612 } 613 614 static void 615 get_ibase(void) 616 { 617 struct number *n; 618 619 n = new_number(); 620 bn_check(BN_set_word(n->number, bmachine.ibase)); 621 push_number(n); 622 } 623 624 static void 625 set_ibase(void) 626 { 627 struct number *n; 628 u_long base; 629 630 n = pop_number(); 631 if (n != NULL) { 632 base = get_ulong(n); 633 if (base != BN_MASK2 && 2 <= base && base <= 16) 634 bmachine.ibase = (u_int)base; 635 else 636 warnx("input base must be a number between 2 and 16 " 637 "(inclusive)"); 638 free_number(n); 639 } 640 } 641 642 static void 643 stackdepth(void) 644 { 645 size_t i; 646 struct number *n; 647 648 i = stack_size(&bmachine.stack); 649 n = new_number(); 650 bn_check(BN_set_word(n->number, i)); 651 push_number(n); 652 } 653 654 static void 655 push_scale(void) 656 { 657 struct value *value; 658 u_int scale = 0; 659 struct number *n; 660 661 662 value = pop(); 663 if (value != NULL) { 664 switch (value->type) { 665 case BCODE_NONE: 666 return; 667 case BCODE_NUMBER: 668 scale = value->u.num->scale; 669 break; 670 case BCODE_STRING: 671 break; 672 } 673 stack_free_value(value); 674 n = new_number(); 675 bn_check(BN_set_word(n->number, scale)); 676 push_number(n); 677 } 678 } 679 680 static u_int 681 count_digits(const struct number *n) 682 { 683 struct number *int_part, *fract_part; 684 u_int i; 685 686 if (BN_is_zero(n->number)) 687 return n->scale ? n->scale : 1; 688 689 int_part = new_number(); 690 fract_part = new_number(); 691 fract_part->scale = n->scale; 692 split_number(n, int_part->number, fract_part->number); 693 694 i = 0; 695 while (!BN_is_zero(int_part->number)) { 696 (void)BN_div_word(int_part->number, 10); 697 i++; 698 } 699 free_number(int_part); 700 free_number(fract_part); 701 return i + n->scale; 702 } 703 704 static void 705 num_digits(void) 706 { 707 struct value *value; 708 size_t digits; 709 struct number *n = NULL; 710 711 value = pop(); 712 if (value != NULL) { 713 switch (value->type) { 714 case BCODE_NONE: 715 return; 716 case BCODE_NUMBER: 717 digits = count_digits(value->u.num); 718 n = new_number(); 719 bn_check(BN_set_word(n->number, digits)); 720 break; 721 case BCODE_STRING: 722 digits = strlen(value->u.string); 723 n = new_number(); 724 bn_check(BN_set_word(n->number, digits)); 725 break; 726 } 727 stack_free_value(value); 728 push_number(n); 729 } 730 } 731 732 static void 733 to_ascii(void) 734 { 735 char str[2]; 736 struct value *value; 737 struct number *n; 738 739 value = pop(); 740 if (value != NULL) { 741 str[1] = '\0'; 742 switch (value->type) { 743 case BCODE_NONE: 744 return; 745 case BCODE_NUMBER: 746 n = value->u.num; 747 normalize(n, 0); 748 if (BN_num_bits(n->number) > 8) 749 bn_check(BN_mask_bits(n->number, 8)); 750 str[0] = (char)BN_get_word(n->number); 751 break; 752 case BCODE_STRING: 753 str[0] = value->u.string[0]; 754 break; 755 } 756 stack_free_value(value); 757 push_string(bstrdup(str)); 758 } 759 } 760 761 static int 762 readreg(void) 763 { 764 int idx, ch1, ch2; 765 766 idx = readch(); 767 if (idx == 0xff && bmachine.extended_regs) { 768 ch1 = readch(); 769 ch2 = readch(); 770 if (ch1 == EOF || ch2 == EOF) { 771 warnx("unexpected eof"); 772 idx = -1; 773 } else 774 idx = (ch1 << 8) + ch2 + UCHAR_MAX + 1; 775 } 776 if (idx < 0 || idx >= bmachine.reg_array_size) { 777 warnx("internal error: reg num = %d", idx); 778 idx = -1; 779 } 780 return idx; 781 } 782 783 static void 784 load(void) 785 { 786 int idx; 787 struct value *v, copy; 788 struct number *n; 789 790 idx = readreg(); 791 if (idx >= 0) { 792 v = stack_tos(&bmachine.reg[idx]); 793 if (v == NULL) { 794 n = new_number(); 795 bn_check(BN_zero(n->number)); 796 push_number(n); 797 } else 798 push(stack_dup_value(v, ©)); 799 } 800 } 801 802 static void 803 store(void) 804 { 805 int idx; 806 struct value *val; 807 808 idx = readreg(); 809 if (idx >= 0) { 810 val = pop(); 811 if (val == NULL) { 812 return; 813 } 814 stack_set_tos(&bmachine.reg[idx], val); 815 } 816 } 817 818 static void 819 load_stack(void) 820 { 821 int idx; 822 struct stack *stack; 823 struct value *value; 824 825 idx = readreg(); 826 if (idx >= 0) { 827 stack = &bmachine.reg[idx]; 828 value = NULL; 829 if (stack_size(stack) > 0) { 830 value = stack_pop(stack); 831 } 832 if (value != NULL) 833 push(value); 834 else 835 warnx("stack register '%c' (0%o) is empty", 836 idx, idx); 837 } 838 } 839 840 static void 841 store_stack(void) 842 { 843 int idx; 844 struct value *value; 845 846 idx = readreg(); 847 if (idx >= 0) { 848 value = pop(); 849 if (value == NULL) 850 return; 851 stack_push(&bmachine.reg[idx], value); 852 } 853 } 854 855 static void 856 load_array(void) 857 { 858 int reg; 859 struct number *inumber, *n; 860 u_long idx; 861 struct stack *stack; 862 struct value *v, copy; 863 864 reg = readreg(); 865 if (reg >= 0) { 866 inumber = pop_number(); 867 if (inumber == NULL) 868 return; 869 idx = get_ulong(inumber); 870 if (BN_is_negative(inumber->number)) 871 warnx("negative idx"); 872 else if (idx == BN_MASK2 || idx > MAX_ARRAY_INDEX) 873 warnx("idx too big"); 874 else { 875 stack = &bmachine.reg[reg]; 876 v = frame_retrieve(stack, idx); 877 if (v == NULL || v->type == BCODE_NONE) { 878 n = new_number(); 879 bn_check(BN_zero(n->number)); 880 push_number(n); 881 } 882 else 883 push(stack_dup_value(v, ©)); 884 } 885 free_number(inumber); 886 } 887 } 888 889 static void 890 store_array(void) 891 { 892 int reg; 893 struct number *inumber; 894 u_long idx; 895 struct value *value; 896 struct stack *stack; 897 898 reg = readreg(); 899 if (reg >= 0) { 900 inumber = pop_number(); 901 if (inumber == NULL) 902 return; 903 value = pop(); 904 if (value == NULL) { 905 free_number(inumber); 906 return; 907 } 908 idx = get_ulong(inumber); 909 if (BN_is_negative(inumber->number)) { 910 warnx("negative idx"); 911 stack_free_value(value); 912 } else if (idx == BN_MASK2 || idx > MAX_ARRAY_INDEX) { 913 warnx("idx too big"); 914 stack_free_value(value); 915 } else { 916 stack = &bmachine.reg[reg]; 917 frame_assign(stack, idx, value); 918 } 919 free_number(inumber); 920 } 921 } 922 923 static void 924 push_line(void) 925 { 926 push_string(read_string(&bmachine.readstack[bmachine.readsp])); 927 } 928 929 static void 930 comment(void) 931 { 932 free(readline()); 933 } 934 935 static void 936 bexec(char *line) 937 { 938 (void)system(line); 939 free(line); 940 } 941 942 static void 943 badd(void) 944 { 945 struct number *a, *b; 946 struct number *r; 947 948 a = pop_number(); 949 if (a == NULL) { 950 return; 951 } 952 b = pop_number(); 953 if (b == NULL) { 954 push_number(a); 955 return; 956 } 957 958 r = new_number(); 959 r->scale = max(a->scale, b->scale); 960 if (r->scale > a->scale) 961 normalize(a, r->scale); 962 else if (r->scale > b->scale) 963 normalize(b, r->scale); 964 bn_check(BN_add(r->number, a->number, b->number)); 965 push_number(r); 966 free_number(a); 967 free_number(b); 968 } 969 970 static void 971 bsub(void) 972 { 973 struct number *a, *b; 974 struct number *r; 975 976 a = pop_number(); 977 if (a == NULL) { 978 return; 979 } 980 b = pop_number(); 981 if (b == NULL) { 982 push_number(a); 983 return; 984 } 985 986 r = new_number(); 987 988 r->scale = max(a->scale, b->scale); 989 if (r->scale > a->scale) 990 normalize(a, r->scale); 991 else if (r->scale > b->scale) 992 normalize(b, r->scale); 993 bn_check(BN_sub(r->number, b->number, a->number)); 994 push_number(r); 995 free_number(a); 996 free_number(b); 997 } 998 999 void 1000 bmul_number(struct number *r, struct number *a, struct number *b, u_int scale) 1001 { 1002 BN_CTX *ctx; 1003 1004 /* Create copies of the scales, since r might be equal to a or b */ 1005 u_int ascale = a->scale; 1006 u_int bscale = b->scale; 1007 u_int rscale = ascale + bscale; 1008 1009 ctx = BN_CTX_new(); 1010 bn_checkp(ctx); 1011 bn_check(BN_mul(r->number, a->number, b->number, ctx)); 1012 BN_CTX_free(ctx); 1013 1014 r->scale = rscale; 1015 if (rscale > bmachine.scale && rscale > ascale && rscale > bscale) 1016 normalize(r, max(scale, max(ascale, bscale))); 1017 } 1018 1019 static void 1020 bmul(void) 1021 { 1022 struct number *a, *b; 1023 struct number *r; 1024 1025 a = pop_number(); 1026 if (a == NULL) { 1027 return; 1028 } 1029 b = pop_number(); 1030 if (b == NULL) { 1031 push_number(a); 1032 return; 1033 } 1034 1035 r = new_number(); 1036 bmul_number(r, a, b, bmachine.scale); 1037 1038 push_number(r); 1039 free_number(a); 1040 free_number(b); 1041 } 1042 1043 static void 1044 bdiv(void) 1045 { 1046 struct number *a, *b; 1047 struct number *r; 1048 u_int scale; 1049 BN_CTX *ctx; 1050 1051 a = pop_number(); 1052 if (a == NULL) { 1053 return; 1054 } 1055 b = pop_number(); 1056 if (b == NULL) { 1057 push_number(a); 1058 return; 1059 } 1060 1061 r = new_number(); 1062 r->scale = bmachine.scale; 1063 scale = max(a->scale, b->scale); 1064 1065 if (BN_is_zero(a->number)) 1066 warnx("divide by zero"); 1067 else { 1068 normalize(a, scale); 1069 normalize(b, scale + r->scale); 1070 1071 ctx = BN_CTX_new(); 1072 bn_checkp(ctx); 1073 bn_check(BN_div(r->number, NULL, b->number, a->number, ctx)); 1074 BN_CTX_free(ctx); 1075 } 1076 push_number(r); 1077 free_number(a); 1078 free_number(b); 1079 } 1080 1081 static void 1082 bmod(void) 1083 { 1084 struct number *a, *b; 1085 struct number *r; 1086 u_int scale; 1087 BN_CTX *ctx; 1088 1089 a = pop_number(); 1090 if (a == NULL) { 1091 return; 1092 } 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 } 1131 b = pop_number(); 1132 if (b == NULL) { 1133 push_number(a); 1134 return; 1135 } 1136 1137 rdiv = new_number(); 1138 rmod = new_number(); 1139 rdiv->scale = bmachine.scale; 1140 rmod->scale = max(b->scale, a->scale + bmachine.scale); 1141 scale = max(a->scale, b->scale); 1142 1143 if (BN_is_zero(a->number)) 1144 warnx("divide by zero"); 1145 else { 1146 normalize(a, scale); 1147 normalize(b, scale + bmachine.scale); 1148 1149 ctx = BN_CTX_new(); 1150 bn_checkp(ctx); 1151 bn_check(BN_div(rdiv->number, rmod->number, 1152 b->number, a->number, ctx)); 1153 BN_CTX_free(ctx); 1154 } 1155 push_number(rdiv); 1156 push_number(rmod); 1157 free_number(a); 1158 free_number(b); 1159 } 1160 1161 static void 1162 bexp(void) 1163 { 1164 struct number *a, *p; 1165 struct number *r; 1166 bool neg; 1167 u_int rscale; 1168 1169 p = pop_number(); 1170 if (p == NULL) { 1171 return; 1172 } 1173 a = pop_number(); 1174 if (a == NULL) { 1175 push_number(p); 1176 return; 1177 } 1178 1179 if (p->scale != 0) { 1180 BIGNUM *i, *f; 1181 i = BN_new(); 1182 bn_checkp(i); 1183 f = BN_new(); 1184 bn_checkp(f); 1185 split_number(p, i, f); 1186 if (!BN_is_zero(f)) 1187 warnx("Runtime warning: non-zero fractional part in exponent"); 1188 BN_free(i); 1189 BN_free(f); 1190 } 1191 1192 normalize(p, 0); 1193 1194 neg = false; 1195 if (BN_is_negative(p->number)) { 1196 neg = true; 1197 negate(p); 1198 rscale = bmachine.scale; 1199 } else { 1200 /* Posix bc says min(a.scale * b, max(a.scale, scale) */ 1201 u_long b; 1202 u_int m; 1203 1204 b = BN_get_word(p->number); 1205 m = max(a->scale, bmachine.scale); 1206 rscale = a->scale * (u_int)b; 1207 if (rscale > m || (a->scale > 0 && (b == BN_MASK2 || 1208 b > UINT_MAX))) 1209 rscale = m; 1210 } 1211 1212 if (BN_is_zero(p->number)) { 1213 r = new_number(); 1214 bn_check(BN_one(r->number)); 1215 normalize(r, rscale); 1216 } else { 1217 u_int ascale, mscale; 1218 1219 ascale = a->scale; 1220 while (!BN_is_bit_set(p->number, 0)) { 1221 ascale *= 2; 1222 bmul_number(a, a, a, ascale); 1223 bn_check(BN_rshift1(p->number, p->number)); 1224 } 1225 1226 r = dup_number(a); 1227 bn_check(BN_rshift1(p->number, p->number)); 1228 1229 mscale = ascale; 1230 while (!BN_is_zero(p->number)) { 1231 ascale *= 2; 1232 bmul_number(a, a, a, ascale); 1233 if (BN_is_bit_set(p->number, 0)) { 1234 mscale += ascale; 1235 bmul_number(r, r, a, mscale); 1236 } 1237 bn_check(BN_rshift1(p->number, p->number)); 1238 } 1239 1240 if (neg) { 1241 BN_CTX *ctx; 1242 BIGNUM *one; 1243 1244 one = BN_new(); 1245 bn_checkp(one); 1246 bn_check(BN_one(one)); 1247 ctx = BN_CTX_new(); 1248 bn_checkp(ctx); 1249 scale_number(one, r->scale + rscale); 1250 1251 if (BN_is_zero(r->number)) 1252 warnx("divide by zero"); 1253 else 1254 bn_check(BN_div(r->number, NULL, one, 1255 r->number, ctx)); 1256 BN_free(one); 1257 BN_CTX_free(ctx); 1258 r->scale = rscale; 1259 } else 1260 normalize(r, rscale); 1261 } 1262 push_number(r); 1263 free_number(a); 1264 free_number(p); 1265 } 1266 1267 static bool 1268 bsqrt_stop(const BIGNUM *x, const BIGNUM *y, u_int *onecount) 1269 { 1270 BIGNUM *r; 1271 bool ret; 1272 1273 r = BN_new(); 1274 bn_checkp(r); 1275 bn_check(BN_sub(r, x, y)); 1276 if (BN_is_one(r)) 1277 (*onecount)++; 1278 ret = BN_is_zero(r); 1279 BN_free(r); 1280 return ret || *onecount > 1; 1281 } 1282 1283 static void 1284 bsqrt(void) 1285 { 1286 struct number *n; 1287 struct number *r; 1288 BIGNUM *x, *y; 1289 u_int scale, onecount; 1290 BN_CTX *ctx; 1291 1292 onecount = 0; 1293 n = pop_number(); 1294 if (n == NULL) { 1295 return; 1296 } 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 } 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 } 1360 b = pop_number(); 1361 if (b == NULL) { 1362 push_number(a); 1363 return; 1364 } 1365 r = new_number(); 1366 bn_check(BN_set_word(r->number, 1367 compare_numbers(BCODE_EQUAL, a, b) ? 1 : 0)); 1368 push_number(r); 1369 } 1370 1371 static void 1372 less_numbers(void) 1373 { 1374 struct number *a, *b, *r; 1375 1376 a = pop_number(); 1377 if (a == NULL) { 1378 return; 1379 } 1380 b = pop_number(); 1381 if (b == NULL) { 1382 push_number(a); 1383 return; 1384 } 1385 r = new_number(); 1386 bn_check(BN_set_word(r->number, 1387 compare_numbers(BCODE_LESS, a, b) ? 1 : 0)); 1388 push_number(r); 1389 } 1390 1391 static void 1392 lesseq_numbers(void) 1393 { 1394 struct number *a, *b, *r; 1395 1396 a = pop_number(); 1397 if (a == NULL) { 1398 return; 1399 } 1400 b = pop_number(); 1401 if (b == NULL) { 1402 push_number(a); 1403 return; 1404 } 1405 r = new_number(); 1406 bn_check(BN_set_word(r->number, 1407 compare_numbers(BCODE_NOT_GREATER, a, b) ? 1 : 0)); 1408 push_number(r); 1409 } 1410 1411 static void 1412 not_equal(void) 1413 { 1414 compare(BCODE_NOT_EQUAL); 1415 } 1416 1417 static void 1418 less(void) 1419 { 1420 compare(BCODE_LESS); 1421 } 1422 1423 static void 1424 not_compare(void) 1425 { 1426 switch (readch()) { 1427 case '<': 1428 not_less(); 1429 break; 1430 case '>': 1431 not_greater(); 1432 break; 1433 case '=': 1434 not_equal(); 1435 break; 1436 default: 1437 unreadch(); 1438 bexec(readline()); 1439 break; 1440 } 1441 } 1442 1443 static void 1444 not_less(void) 1445 { 1446 compare(BCODE_NOT_LESS); 1447 } 1448 1449 static void 1450 greater(void) 1451 { 1452 compare(BCODE_GREATER); 1453 } 1454 1455 static void 1456 not_greater(void) 1457 { 1458 compare(BCODE_NOT_GREATER); 1459 } 1460 1461 static bool 1462 compare_numbers(enum bcode_compare type, struct number *a, struct number *b) 1463 { 1464 u_int scale; 1465 int cmp; 1466 1467 scale = max(a->scale, b->scale); 1468 1469 if (scale > a->scale) 1470 normalize(a, scale); 1471 else if (scale > b->scale) 1472 normalize(b, scale); 1473 1474 cmp = BN_cmp(a->number, b->number); 1475 1476 free_number(a); 1477 free_number(b); 1478 1479 switch (type) { 1480 case BCODE_EQUAL: 1481 return cmp == 0; 1482 case BCODE_NOT_EQUAL: 1483 return cmp != 0; 1484 case BCODE_LESS: 1485 return cmp < 0; 1486 case BCODE_NOT_LESS: 1487 return cmp >= 0; 1488 case BCODE_GREATER: 1489 return cmp > 0; 1490 case BCODE_NOT_GREATER: 1491 return cmp <= 0; 1492 } 1493 return false; 1494 } 1495 1496 static void 1497 compare(enum bcode_compare type) 1498 { 1499 int idx, elseidx; 1500 struct number *a, *b; 1501 bool ok; 1502 struct value *v; 1503 1504 elseidx = NO_ELSE; 1505 idx = readreg(); 1506 if (readch() == 'e') 1507 elseidx = readreg(); 1508 else 1509 unreadch(); 1510 1511 a = pop_number(); 1512 if (a == NULL) 1513 return; 1514 b = pop_number(); 1515 if (b == NULL) { 1516 push_number(a); 1517 return; 1518 } 1519 1520 ok = compare_numbers(type, a, b); 1521 1522 if (!ok && elseidx != NO_ELSE) 1523 idx = elseidx; 1524 1525 if (idx >= 0 && (ok || (!ok && elseidx != NO_ELSE))) { 1526 v = stack_tos(&bmachine.reg[idx]); 1527 if (v == NULL) 1528 warnx("register '%c' (0%o) is empty", idx, idx); 1529 else { 1530 switch(v->type) { 1531 case BCODE_NONE: 1532 warnx("register '%c' (0%o) is empty", idx, idx); 1533 break; 1534 case BCODE_NUMBER: 1535 warn("eval called with non-string argument"); 1536 break; 1537 case BCODE_STRING: 1538 eval_string(bstrdup(v->u.string)); 1539 break; 1540 } 1541 } 1542 } 1543 } 1544 1545 1546 static void 1547 nop(void) 1548 { 1549 } 1550 1551 static void 1552 quit(void) 1553 { 1554 if (bmachine.readsp < 2) 1555 exit(0); 1556 src_free(); 1557 bmachine.readsp--; 1558 src_free(); 1559 bmachine.readsp--; 1560 } 1561 1562 static void 1563 quitN(void) 1564 { 1565 struct number *n; 1566 u_long i; 1567 1568 n = pop_number(); 1569 if (n == NULL) 1570 return; 1571 i = get_ulong(n); 1572 free_number(n); 1573 if (i == BN_MASK2 || i == 0) 1574 warnx("Q command requires a number >= 1"); 1575 else if (bmachine.readsp < i) 1576 warnx("Q command argument exceeded string execution depth"); 1577 else { 1578 while (i-- > 0) { 1579 src_free(); 1580 bmachine.readsp--; 1581 } 1582 } 1583 } 1584 1585 static void 1586 skipN(void) 1587 { 1588 struct number *n; 1589 u_long i; 1590 1591 n = pop_number(); 1592 if (n == NULL) 1593 return; 1594 i = get_ulong(n); 1595 if (i == BN_MASK2) 1596 warnx("J command requires a number >= 0"); 1597 else if (i > 0 && bmachine.readsp < i) 1598 warnx("J command argument exceeded string execution depth"); 1599 else { 1600 while (i-- > 0) { 1601 src_free(); 1602 bmachine.readsp--; 1603 } 1604 skip_until_mark(); 1605 } 1606 } 1607 1608 static void 1609 skip_until_mark(void) 1610 { 1611 int ch; 1612 1613 for (;;) { 1614 ch = readch(); 1615 switch (ch) { 1616 case 'M': 1617 return; 1618 case EOF: 1619 errx(1, "mark not found"); 1620 return; 1621 case 'l': 1622 case 'L': 1623 case 's': 1624 case 'S': 1625 case ':': 1626 case ';': 1627 case '<': 1628 case '>': 1629 case '=': 1630 (void)readreg(); 1631 if (readch() == 'e') 1632 (void)readreg(); 1633 else 1634 unreadch(); 1635 break; 1636 case '[': 1637 free(read_string(&bmachine.readstack[bmachine.readsp])); 1638 break; 1639 case '!': 1640 switch (ch = readch()) { 1641 case '<': 1642 case '>': 1643 case '=': 1644 (void)readreg(); 1645 if (readch() == 'e') 1646 (void)readreg(); 1647 else 1648 unreadch(); 1649 break; 1650 default: 1651 free(readline()); 1652 break; 1653 } 1654 break; 1655 default: 1656 break; 1657 } 1658 } 1659 } 1660 1661 static void 1662 parse_number(void) 1663 { 1664 unreadch(); 1665 push_number(readnumber(&bmachine.readstack[bmachine.readsp], 1666 bmachine.ibase)); 1667 } 1668 1669 static void 1670 unknown(void) 1671 { 1672 int ch = bmachine.readstack[bmachine.readsp].lastchar; 1673 warnx("%c (0%o) is unimplemented", ch, ch); 1674 } 1675 1676 static void 1677 eval_string(char *p) 1678 { 1679 int ch; 1680 1681 if (bmachine.readsp > 0) { 1682 /* Check for tail call. Do not recurse in that case. */ 1683 ch = readch(); 1684 if (ch == EOF) { 1685 src_free(); 1686 src_setstring(&bmachine.readstack[bmachine.readsp], p); 1687 return; 1688 } else 1689 unreadch(); 1690 } 1691 if (bmachine.readsp == bmachine.readstack_sz - 1) { 1692 size_t newsz = bmachine.readstack_sz * 2; 1693 struct source *stack; 1694 stack = reallocarray(bmachine.readstack, newsz, 1695 sizeof(struct source)); 1696 if (stack == NULL) 1697 err(1, "recursion too deep"); 1698 bmachine.readstack_sz = newsz; 1699 bmachine.readstack = stack; 1700 } 1701 src_setstring(&bmachine.readstack[++bmachine.readsp], p); 1702 } 1703 1704 static void 1705 eval_line(void) 1706 { 1707 /* Always read from stdin */ 1708 struct source in; 1709 char *p; 1710 1711 clearerr(stdin); 1712 src_setstream(&in, stdin); 1713 p = (*in.vtable->readline)(&in); 1714 eval_string(p); 1715 } 1716 1717 static void 1718 eval_tos(void) 1719 { 1720 char *p; 1721 1722 p = pop_string(); 1723 if (p == NULL) 1724 return; 1725 eval_string(p); 1726 } 1727 1728 void 1729 eval(void) 1730 { 1731 int ch; 1732 1733 for (;;) { 1734 ch = readch(); 1735 if (ch == EOF) { 1736 if (bmachine.readsp == 0) 1737 return; 1738 src_free(); 1739 bmachine.readsp--; 1740 continue; 1741 } 1742 if (bmachine.interrupted) { 1743 if (bmachine.readsp > 0) { 1744 src_free(); 1745 bmachine.readsp--; 1746 continue; 1747 } else 1748 bmachine.interrupted = false; 1749 } 1750 #ifdef DEBUGGING 1751 (void)fprintf(stderr, "# %c\n", ch); 1752 stack_print(stderr, &bmachine.stack, "* ", 1753 bmachine.obase); 1754 (void)fprintf(stderr, "%zd =>\n", bmachine.readsp); 1755 #endif 1756 1757 if (0 <= ch && ch < UCHAR_MAX) 1758 (*jump_table[ch])(); 1759 else 1760 warnx("internal error: opcode %d", ch); 1761 1762 #ifdef DEBUGGING 1763 stack_print(stderr, &bmachine.stack, "* ", 1764 bmachine.obase); 1765 (void)fprintf(stderr, "%zd ==\n", bmachine.readsp); 1766 #endif 1767 } 1768 }