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$"); 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 } 966 b = pop_number(); 967 if (b == NULL) { 968 push_number(a); 969 return; 970 } 971 972 r = new_number(); 973 r->scale = max(a->scale, b->scale); 974 if (r->scale > a->scale) 975 normalize(a, r->scale); 976 else if (r->scale > b->scale) 977 normalize(b, r->scale); 978 bn_check(BN_add(r->number, a->number, b->number)); 979 push_number(r); 980 free_number(a); 981 free_number(b); 982} 983 984static void 985bsub(void) 986{ 987 struct number *a, *b, *r; 988 989 a = pop_number(); 990 if (a == NULL) { 991 return; 992 } 993 b = pop_number(); 994 if (b == NULL) { 995 push_number(a); 996 return; 997 } 998 999 r = new_number(); 1000 1001 r->scale = max(a->scale, b->scale); 1002 if (r->scale > a->scale) 1003 normalize(a, r->scale); 1004 else if (r->scale > b->scale) 1005 normalize(b, r->scale); 1006 bn_check(BN_sub(r->number, b->number, a->number)); 1007 push_number(r); 1008 free_number(a); 1009 free_number(b); 1010} 1011 1012void 1013bmul_number(struct number *r, struct number *a, struct number *b, u_int scale) 1014{ 1015 BN_CTX *ctx; 1016 1017 /* Create copies of the scales, since r might be equal to a or b */ 1018 u_int ascale = a->scale; 1019 u_int bscale = b->scale; 1020 u_int rscale = ascale + bscale; 1021 1022 ctx = BN_CTX_new(); 1023 bn_checkp(ctx); 1024 bn_check(BN_mul(r->number, a->number, b->number, ctx)); 1025 BN_CTX_free(ctx); 1026 1027 r->scale = rscale; 1028 if (rscale > bmachine.scale && rscale > ascale && rscale > bscale) 1029 normalize(r, max(scale, max(ascale, bscale))); 1030} 1031 1032static void 1033bmul(void) 1034{ 1035 struct number *a, *b, *r; 1036 1037 a = pop_number(); 1038 if (a == NULL) { 1039 return; 1040 } 1041 b = pop_number(); 1042 if (b == NULL) { 1043 push_number(a); 1044 return; 1045 } 1046 1047 r = new_number(); 1048 bmul_number(r, a, b, bmachine.scale); 1049 1050 push_number(r); 1051 free_number(a); 1052 free_number(b); 1053} 1054 1055static void 1056bdiv(void) 1057{ 1058 struct number *a, *b, *r; 1059 BN_CTX *ctx; 1060 u_int scale; 1061 1062 a = pop_number(); 1063 if (a == NULL) { 1064 return; 1065 } 1066 b = pop_number(); 1067 if (b == NULL) { 1068 push_number(a); 1069 return; 1070 } 1071 1072 r = new_number(); 1073 r->scale = bmachine.scale; 1074 scale = max(a->scale, b->scale); 1075 1076 if (BN_is_zero(a->number)) 1077 warnx("divide by zero"); 1078 else { 1079 normalize(a, scale); 1080 normalize(b, scale + r->scale); 1081 1082 ctx = BN_CTX_new(); 1083 bn_checkp(ctx); 1084 bn_check(BN_div(r->number, NULL, b->number, a->number, ctx)); 1085 BN_CTX_free(ctx); 1086 } 1087 push_number(r); 1088 free_number(a); 1089 free_number(b); 1090} 1091 1092static void 1093bmod(void) 1094{ 1095 struct number *a, *b, *r; 1096 BN_CTX *ctx; 1097 u_int scale; 1098 1099 a = pop_number(); 1100 if (a == NULL) { 1101 return; 1102 } 1103 b = pop_number(); 1104 if (b == NULL) { 1105 push_number(a); 1106 return; 1107 } 1108 1109 r = new_number(); 1110 scale = max(a->scale, b->scale); 1111 r->scale = max(b->scale, a->scale + bmachine.scale); 1112 1113 if (BN_is_zero(a->number)) 1114 warnx("remainder by zero"); 1115 else { 1116 normalize(a, scale); 1117 normalize(b, scale + bmachine.scale); 1118 1119 ctx = BN_CTX_new(); 1120 bn_checkp(ctx); 1121 bn_check(BN_mod(r->number, b->number, a->number, ctx)); 1122 BN_CTX_free(ctx); 1123 } 1124 push_number(r); 1125 free_number(a); 1126 free_number(b); 1127} 1128 1129static void 1130bdivmod(void) 1131{ 1132 struct number *a, *b, *rdiv, *rmod; 1133 BN_CTX *ctx; 1134 u_int scale; 1135 1136 a = pop_number(); 1137 if (a == NULL) { 1138 return; 1139 } 1140 b = pop_number(); 1141 if (b == NULL) { 1142 push_number(a); 1143 return; 1144 } 1145 1146 rdiv = new_number(); 1147 rmod = new_number(); 1148 rdiv->scale = bmachine.scale; 1149 rmod->scale = max(b->scale, a->scale + bmachine.scale); 1150 scale = max(a->scale, b->scale); 1151 1152 if (BN_is_zero(a->number)) 1153 warnx("divide by zero"); 1154 else { 1155 normalize(a, scale); 1156 normalize(b, scale + bmachine.scale); 1157 1158 ctx = BN_CTX_new(); 1159 bn_checkp(ctx); 1160 bn_check(BN_div(rdiv->number, rmod->number, 1161 b->number, a->number, ctx)); 1162 BN_CTX_free(ctx); 1163 } 1164 push_number(rdiv); 1165 push_number(rmod); 1166 free_number(a); 1167 free_number(b); 1168} 1169 1170static void 1171bexp(void) 1172{ 1173 struct number *a, *p; 1174 struct number *r; 1175 bool neg; 1176 u_int rscale; 1177 1178 p = pop_number(); 1179 if (p == NULL) { 1180 return; 1181 } 1182 a = pop_number(); 1183 if (a == NULL) { 1184 push_number(p); 1185 return; 1186 } 1187 1188 if (p->scale != 0) { 1189 BIGNUM *i, *f; 1190 i = BN_new(); 1191 bn_checkp(i); 1192 f = BN_new(); 1193 bn_checkp(f); 1194 split_number(p, i, f); 1195 if (!BN_is_zero(f)) 1196 warnx("Runtime warning: non-zero fractional part in exponent"); 1197 BN_free(i); 1198 BN_free(f); 1199 } 1200 1201 normalize(p, 0); 1202 1203 neg = false; 1204 if (BN_is_negative(p->number)) { 1205 neg = true; 1206 negate(p); 1207 rscale = bmachine.scale; 1208 } else { 1209 /* Posix bc says min(a.scale * b, max(a.scale, scale) */ 1210 u_long b; 1211 u_int m; 1212 1213 b = BN_get_word(p->number); 1214 m = max(a->scale, bmachine.scale); 1215 rscale = a->scale * (u_int)b; 1216 if (rscale > m || (a->scale > 0 && (b == BN_MASK2 || 1217 b > UINT_MAX))) 1218 rscale = m; 1219 } 1220 1221 if (BN_is_zero(p->number)) { 1222 r = new_number(); 1223 bn_check(BN_one(r->number)); 1224 normalize(r, rscale); 1225 } else { 1226 u_int ascale, mscale; 1227 1228 ascale = a->scale; 1229 while (!BN_is_bit_set(p->number, 0)) { 1230 ascale *= 2; 1231 bmul_number(a, a, a, ascale); 1232 bn_check(BN_rshift1(p->number, p->number)); 1233 } 1234 1235 r = dup_number(a); 1236 bn_check(BN_rshift1(p->number, p->number)); 1237 1238 mscale = ascale; 1239 while (!BN_is_zero(p->number)) { 1240 ascale *= 2; 1241 bmul_number(a, a, a, ascale); 1242 if (BN_is_bit_set(p->number, 0)) { 1243 mscale += ascale; 1244 bmul_number(r, r, a, mscale); 1245 } 1246 bn_check(BN_rshift1(p->number, p->number)); 1247 } 1248 1249 if (neg) { 1250 BN_CTX *ctx; 1251 BIGNUM *one; 1252 1253 one = BN_new(); 1254 bn_checkp(one); 1255 bn_check(BN_one(one)); 1256 ctx = BN_CTX_new(); 1257 bn_checkp(ctx); 1258 scale_number(one, r->scale + rscale); 1259 1260 if (BN_is_zero(r->number)) 1261 warnx("divide by zero"); 1262 else 1263 bn_check(BN_div(r->number, NULL, one, 1264 r->number, ctx)); 1265 BN_free(one); 1266 BN_CTX_free(ctx); 1267 r->scale = rscale; 1268 } else 1269 normalize(r, rscale); 1270 } 1271 push_number(r); 1272 free_number(a); 1273 free_number(p); 1274} 1275 1276static bool 1277bsqrt_stop(const BIGNUM *x, const BIGNUM *y, u_int *onecount) 1278{ 1279 BIGNUM *r; 1280 bool ret; 1281 1282 r = BN_new(); 1283 bn_checkp(r); 1284 bn_check(BN_sub(r, x, y)); 1285 if (BN_is_one(r)) 1286 (*onecount)++; 1287 ret = BN_is_zero(r); 1288 BN_free(r); 1289 return (ret || *onecount > 1); 1290} 1291 1292static void 1293bsqrt(void) 1294{ 1295 struct number *n, *r; 1296 BIGNUM *x, *y; 1297 BN_CTX *ctx; 1298 u_int onecount, scale; 1299 1300 onecount = 0; 1301 n = pop_number(); 1302 if (n == NULL) { 1303 return; 1304 } 1305 if (BN_is_zero(n->number)) { 1306 r = new_number(); 1307 push_number(r); 1308 } else if (BN_is_negative(n->number)) 1309 warnx("square root of negative number"); 1310 else { 1311 scale = max(bmachine.scale, n->scale); 1312 normalize(n, 2*scale); 1313 x = BN_dup(n->number); 1314 bn_checkp(x); 1315 bn_check(BN_rshift(x, x, BN_num_bits(x)/2)); 1316 y = BN_new(); 1317 bn_checkp(y); 1318 ctx = BN_CTX_new(); 1319 bn_checkp(ctx); 1320 for (;;) { 1321 bn_checkp(BN_copy(y, x)); 1322 bn_check(BN_div(x, NULL, n->number, x, ctx)); 1323 bn_check(BN_add(x, x, y)); 1324 bn_check(BN_rshift1(x, x)); 1325 if (bsqrt_stop(x, y, &onecount)) 1326 break; 1327 } 1328 r = bmalloc(sizeof(*r)); 1329 r->scale = scale; 1330 r->number = y; 1331 BN_free(x); 1332 BN_CTX_free(ctx); 1333 push_number(r); 1334 } 1335 1336 free_number(n); 1337} 1338 1339static void 1340not(void) 1341{ 1342 struct number *a; 1343 1344 a = pop_number(); 1345 if (a == NULL) { 1346 return; 1347 } 1348 a->scale = 0; 1349 bn_check(BN_set_word(a->number, BN_get_word(a->number) ? 0 : 1)); 1350 push_number(a); 1351} 1352 1353static void 1354equal(void) 1355{ 1356 1357 compare(BCODE_EQUAL); 1358} 1359 1360static void 1361equal_numbers(void) 1362{ 1363 struct number *a, *b, *r; 1364 1365 a = pop_number(); 1366 if (a == NULL) { 1367 return; 1368 } 1369 b = pop_number(); 1370 if (b == NULL) { 1371 push_number(a); 1372 return; 1373 } 1374 r = new_number(); 1375 bn_check(BN_set_word(r->number, 1376 compare_numbers(BCODE_EQUAL, a, b) ? 1 : 0)); 1377 push_number(r); 1378} 1379 1380static void 1381less_numbers(void) 1382{ 1383 struct number *a, *b, *r; 1384 1385 a = pop_number(); 1386 if (a == NULL) { 1387 return; 1388 } 1389 b = pop_number(); 1390 if (b == NULL) { 1391 push_number(a); 1392 return; 1393 } 1394 r = new_number(); 1395 bn_check(BN_set_word(r->number, 1396 compare_numbers(BCODE_LESS, a, b) ? 1 : 0)); 1397 push_number(r); 1398} 1399 1400static void 1401lesseq_numbers(void) 1402{ 1403 struct number *a, *b, *r; 1404 1405 a = pop_number(); 1406 if (a == NULL) { 1407 return; 1408 } 1409 b = pop_number(); 1410 if (b == NULL) { 1411 push_number(a); 1412 return; 1413 } 1414 r = new_number(); 1415 bn_check(BN_set_word(r->number, 1416 compare_numbers(BCODE_NOT_GREATER, a, b) ? 1 : 0)); 1417 push_number(r); 1418} 1419 1420static void 1421not_equal(void) 1422{ 1423 1424 compare(BCODE_NOT_EQUAL); 1425} 1426 1427static void 1428less(void) 1429{ 1430 1431 compare(BCODE_LESS); 1432} 1433 1434static void 1435not_compare(void) 1436{ 1437 1438 switch (readch()) { 1439 case '<': 1440 not_less(); 1441 break; 1442 case '>': 1443 not_greater(); 1444 break; 1445 case '=': 1446 not_equal(); 1447 break; 1448 default: 1449 unreadch(); 1450 bexec(readline()); 1451 break; 1452 } 1453} 1454 1455static void 1456not_less(void) 1457{ 1458 1459 compare(BCODE_NOT_LESS); 1460} 1461 1462static void 1463greater(void) 1464{ 1465 1466 compare(BCODE_GREATER); 1467} 1468 1469static void 1470not_greater(void) 1471{ 1472 1473 compare(BCODE_NOT_GREATER); 1474} 1475 1476static bool 1477compare_numbers(enum bcode_compare type, struct number *a, struct number *b) 1478{ 1479 u_int scale; 1480 int cmp; 1481 1482 scale = max(a->scale, b->scale); 1483 1484 if (scale > a->scale) 1485 normalize(a, scale); 1486 else if (scale > b->scale) 1487 normalize(b, scale); 1488 1489 cmp = BN_cmp(a->number, b->number); 1490 1491 free_number(a); 1492 free_number(b); 1493 1494 switch (type) { 1495 case BCODE_EQUAL: 1496 return (cmp == 0); 1497 case BCODE_NOT_EQUAL: 1498 return (cmp != 0); 1499 case BCODE_LESS: 1500 return (cmp < 0); 1501 case BCODE_NOT_LESS: 1502 return (cmp >= 0); 1503 case BCODE_GREATER: 1504 return (cmp > 0); 1505 case BCODE_NOT_GREATER: 1506 return (cmp <= 0); 1507 } 1508 return (false); 1509} 1510 1511static void 1512compare(enum bcode_compare type) 1513{ 1514 struct number *a, *b; 1515 struct value *v; 1516 int idx, elseidx; 1517 bool ok; 1518 1519 elseidx = NO_ELSE; 1520 idx = readreg(); 1521 if (readch() == 'e') 1522 elseidx = readreg(); 1523 else 1524 unreadch(); 1525 1526 a = pop_number(); 1527 if (a == NULL) 1528 return; 1529 b = pop_number(); 1530 if (b == NULL) { 1531 push_number(a); 1532 return; 1533 } 1534 1535 ok = compare_numbers(type, a, b); 1536 1537 if (!ok && elseidx != NO_ELSE) 1538 idx = elseidx; 1539 1540 if (idx >= 0 && (ok || (!ok && elseidx != NO_ELSE))) { 1541 v = stack_tos(&bmachine.reg[idx]); 1542 if (v == NULL) 1543 warnx("register '%c' (0%o) is empty", idx, idx); 1544 else { 1545 switch(v->type) { 1546 case BCODE_NONE: 1547 warnx("register '%c' (0%o) is empty", idx, idx); 1548 break; 1549 case BCODE_NUMBER: 1550 warn("eval called with non-string argument"); 1551 break; 1552 case BCODE_STRING: 1553 eval_string(bstrdup(v->u.string)); 1554 break; 1555 } 1556 } 1557 } 1558} 1559 1560 1561static void 1562nop(void) 1563{ 1564 1565} 1566 1567static void 1568quit(void) 1569{ 1570 1571 if (bmachine.readsp < 2) 1572 exit(0); 1573 src_free(); 1574 bmachine.readsp--; 1575 src_free(); 1576 bmachine.readsp--; 1577} 1578 1579static void 1580quitN(void) 1581{ 1582 struct number *n; 1583 u_long i; 1584 1585 n = pop_number(); 1586 if (n == NULL) 1587 return; 1588 i = get_ulong(n); 1589 free_number(n); 1590 if (i == BN_MASK2 || i == 0) 1591 warnx("Q command requires a number >= 1"); 1592 else if (bmachine.readsp < i) 1593 warnx("Q command argument exceeded string execution depth"); 1594 else { 1595 while (i-- > 0) { 1596 src_free(); 1597 bmachine.readsp--; 1598 } 1599 } 1600} 1601 1602static void 1603skipN(void) 1604{ 1605 struct number *n; 1606 u_long i; 1607 1608 n = pop_number(); 1609 if (n == NULL) 1610 return; 1611 i = get_ulong(n); 1612 if (i == BN_MASK2) 1613 warnx("J command requires a number >= 0"); 1614 else if (i > 0 && bmachine.readsp < i) 1615 warnx("J command argument exceeded string execution depth"); 1616 else { 1617 while (i-- > 0) { 1618 src_free(); 1619 bmachine.readsp--; 1620 } 1621 skip_until_mark(); 1622 } 1623} 1624 1625static void 1626skip_until_mark(void) 1627{ 1628 1629 for (;;) { 1630 switch (readch()) { 1631 case 'M': 1632 return; 1633 case EOF: 1634 errx(1, "mark not found"); 1635 return; 1636 case 'l': 1637 case 'L': 1638 case 's': 1639 case 'S': 1640 case ':': 1641 case ';': 1642 case '<': 1643 case '>': 1644 case '=': 1645 readreg(); 1646 if (readch() == 'e') 1647 readreg(); 1648 else 1649 unreadch(); 1650 break; 1651 case '[': 1652 free(read_string(&bmachine.readstack[bmachine.readsp])); 1653 break; 1654 case '!': 1655 switch (readch()) { 1656 case '<': 1657 case '>': 1658 case '=': 1659 readreg(); 1660 if (readch() == 'e') 1661 readreg(); 1662 else 1663 unreadch(); 1664 break; 1665 default: 1666 free(readline()); 1667 break; 1668 } 1669 break; 1670 default: 1671 break; 1672 } 1673 } 1674} 1675 1676static void 1677parse_number(void) 1678{ 1679 1680 unreadch(); 1681 push_number(readnumber(&bmachine.readstack[bmachine.readsp], 1682 bmachine.ibase)); 1683} 1684 1685static void 1686unknown(void) 1687{ 1688 int ch = bmachine.readstack[bmachine.readsp].lastchar; 1689 warnx("%c (0%o) is unimplemented", ch, ch); 1690} 1691 1692static void 1693eval_string(char *p) 1694{ 1695 int ch; 1696 1697 if (bmachine.readsp > 0) { 1698 /* Check for tail call. Do not recurse in that case. */ 1699 ch = readch(); 1700 if (ch == EOF) { 1701 src_free(); 1702 src_setstring(&bmachine.readstack[bmachine.readsp], p); 1703 return; 1704 } else 1705 unreadch(); 1706 } 1707 if (bmachine.readsp == bmachine.readstack_sz - 1) { 1708 size_t newsz = bmachine.readstack_sz * 2; 1709 struct source *stack; 1710 stack = realloc(bmachine.readstack, newsz * 1711 sizeof(struct source)); 1712 if (stack == NULL) 1713 err(1, "recursion too deep"); 1714 bmachine.readstack_sz = newsz; 1715 bmachine.readstack = stack; 1716 } 1717 src_setstring(&bmachine.readstack[++bmachine.readsp], p); 1718} 1719 1720static void 1721eval_line(void) 1722{ 1723 /* Always read from stdin */ 1724 struct source in; 1725 char *p; 1726 1727 clearerr(stdin); 1728 src_setstream(&in, stdin); 1729 p = (*in.vtable->readline)(&in); 1730 eval_string(p); 1731} 1732 1733static void 1734eval_tos(void) 1735{ 1736 char *p; 1737 1738 p = pop_string(); 1739 if (p == NULL) 1740 return; 1741 eval_string(p); 1742} 1743 1744void 1745eval(void) 1746{ 1747 int ch; 1748 1749 for (;;) { 1750 ch = readch(); 1751 if (ch == EOF) { 1752 if (bmachine.readsp == 0) 1753 return; 1754 src_free(); 1755 bmachine.readsp--; 1756 continue; 1757 } 1758#ifdef DEBUGGING 1759 fprintf(stderr, "# %c\n", ch); 1760 stack_print(stderr, &bmachine.stack, "* ", 1761 bmachine.obase); 1762 fprintf(stderr, "%zd =>\n", bmachine.readsp); 1763#endif 1764 1765 if (0 <= ch && ch < (signed)UCHAR_MAX) 1766 (*jump_table[ch])(); 1767 else 1768 warnx("internal error: opcode %d", ch); 1769 1770#ifdef DEBUGGING 1771 stack_print(stderr, &bmachine.stack, "* ", 1772 bmachine.obase); 1773 fprintf(stderr, "%zd ==\n", bmachine.readsp); 1774#endif 1775 } 1776} 1777