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