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