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