usr.bin/dc/bcode.c

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