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