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