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