/*      $NetBSD: bcode.c,v 1.4 2023/06/26 17:47:04 martin Exp $ */
/*      $OpenBSD: bcode.c,v 1.51 2017/02/26 11:29:55 otto Exp $ */

/*
* Copyright (c) 2003, Otto Moerbeek <[email protected]>
*
* Permission to use, copy, modify, and distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
* copyright notice and this permission notice appear in all copies.
*
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*/
#include <sys/cdefs.h>
__RCSID("$NetBSD: bcode.c,v 1.4 2023/06/26 17:47:04 martin Exp $");

#include <err.h>
#include <limits.h>
#include <signal.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "extern.h"

/* #define      DEBUGGING */

#define MAX_ARRAY_INDEX         2048
#define READSTACK_SIZE          8
#define NO_NUMBER               (~0UL)

#define NO_ELSE                 -2      /* -1 is EOF */
#define REG_ARRAY_SIZE_SMALL    (UCHAR_MAX + 1)
#define REG_ARRAY_SIZE_BIG      (UCHAR_MAX + 1 + USHRT_MAX + 1)

struct bmachine {
       struct stack            stack;
       u_int                   scale;
       u_int                   obase;
       u_int                   ibase;
       size_t                  readsp;
       bool                    extended_regs;
       size_t                  reg_array_size;
       struct stack            *reg;
       volatile sig_atomic_t   interrupted;
       struct source           *readstack;
       size_t                  readstack_sz;
};

static struct bmachine  bmachine;
static void sighandler(int);

static __inline int     readch(void);
static __inline void    unreadch(void);
static __inline char    *readline(void);
static __inline void    src_free(void);

static __inline u_int   max(u_int, u_int);
static u_long           get_ulong(struct number *);

static __inline void    push_number(struct number *);
static __inline void    push_string(char *);
static __inline void    push(struct value *);
static __inline struct value *tos(void);
static __inline struct number   *pop_number(void);
static __inline char    *pop_string(void);
static __inline void    clear_stack(void);
static __inline void    print_tos(void);
static void             print_err(void);
static void             pop_print(void);
static void             pop_printn(void);
static __inline void    print_stack(void);
static __inline void    dup(void);
static void             swap(void);
static void             drop(void);

static void             get_scale(void);
static void             set_scale(void);
static void             get_obase(void);
static void             set_obase(void);
static void             get_ibase(void);
static void             set_ibase(void);
static void             stackdepth(void);
static void             push_scale(void);
static u_int            count_digits(const struct number *);
static void             num_digits(void);
static void             to_ascii(void);
static void             push_line(void);
static void             comment(void);
static void             badd(void);
static void             bsub(void);
static void             bmul(void);
static void             bdiv(void);
static void             bmod(void);
static void             bdivmod(void);
static void             bexp(void);
static bool             bsqrt_stop(const BIGNUM *, const BIGNUM *, u_int *);
static void             bsqrt(void);
static void             not(void);
static void             equal_numbers(void);
static void             less_numbers(void);
static void             lesseq_numbers(void);
static void             equal(void);
static void             not_equal(void);
static void             less(void);
static void             not_less(void);
static void             greater(void);
static void             not_greater(void);
static void             not_compare(void);
static bool             compare_numbers(enum bcode_compare, struct number *,
                           struct number *);
static void             compare(enum bcode_compare);
static int              readreg(void);
static void             load(void);
static void             store(void);
static void             load_stack(void);
static void             store_stack(void);
static void             load_array(void);
static void             store_array(void);
static void             nop(void);
static void             quit(void);
static void             quitN(void);
static void             skipN(void);
static void             skip_until_mark(void);
static void             parse_number(void);
static void             unknown(void);
static void             eval_string(char *);
static void             eval_line(void);
static void             eval_tos(void);


typedef void            (*opcode_function)(void);

struct jump_entry {
       u_char          ch;
       opcode_function f;
};

static opcode_function jump_table[UCHAR_MAX];

static const struct jump_entry jump_table_data[] = {
       { ' ',  nop             },
       { '!',  not_compare     },
       { '#',  comment         },
       { '%',  bmod            },
       { '(',  less_numbers    },
       { '*',  bmul            },
       { '+',  badd            },
       { '-',  bsub            },
       { '.',  parse_number    },
       { '/',  bdiv            },
       { '0',  parse_number    },
       { '1',  parse_number    },
       { '2',  parse_number    },
       { '3',  parse_number    },
       { '4',  parse_number    },
       { '5',  parse_number    },
       { '6',  parse_number    },
       { '7',  parse_number    },
       { '8',  parse_number    },
       { '9',  parse_number    },
       { ':',  store_array     },
       { ';',  load_array      },
       { '<',  less            },
       { '=',  equal           },
       { '>',  greater         },
       { '?',  eval_line       },
       { 'A',  parse_number    },
       { 'B',  parse_number    },
       { 'C',  parse_number    },
       { 'D',  parse_number    },
       { 'E',  parse_number    },
       { 'F',  parse_number    },
       { 'G',  equal_numbers   },
       { 'I',  get_ibase       },
       { 'J',  skipN           },
       { 'K',  get_scale       },
       { 'L',  load_stack      },
       { 'M',  nop             },
       { 'N',  not             },
       { 'O',  get_obase       },
       { 'P',  pop_print       },
       { 'Q',  quitN           },
       { 'R',  drop            },
       { 'S',  store_stack     },
       { 'X',  push_scale      },
       { 'Z',  num_digits      },
       { '[',  push_line       },
       { '\f', nop             },
       { '\n', nop             },
       { '\r', nop             },
       { '\t', nop             },
       { '^',  bexp            },
       { '_',  parse_number    },
       { 'a',  to_ascii        },
       { 'c',  clear_stack     },
       { 'd',  dup             },
       { 'e',  print_err       },
       { 'f',  print_stack     },
       { 'i',  set_ibase       },
       { 'k',  set_scale       },
       { 'l',  load            },
       { 'n',  pop_printn      },
       { 'o',  set_obase       },
       { 'p',  print_tos       },
       { 'q',  quit            },
       { 'r',  swap            },
       { 's',  store           },
       { 'v',  bsqrt           },
       { 'x',  eval_tos        },
       { 'z',  stackdepth      },
       { '{',  lesseq_numbers  },
       { '~',  bdivmod         }
};

#define JUMP_TABLE_DATA_SIZE \
       (sizeof(jump_table_data)/sizeof(jump_table_data[0]))

/* ARGSUSED */
static void
sighandler(int ignored)
{
       bmachine.interrupted = true;
}

void
init_bmachine(bool extended_registers)
{
       size_t i;

       bmachine.extended_regs = extended_registers;
       bmachine.reg_array_size = bmachine.extended_regs ?
           REG_ARRAY_SIZE_BIG : REG_ARRAY_SIZE_SMALL;

       bmachine.reg = calloc(bmachine.reg_array_size,
           sizeof(bmachine.reg[0]));
       if (bmachine.reg == NULL)
               err(1, NULL);

       for (i = 0; i < UCHAR_MAX; i++)
               jump_table[i] = unknown;
       for (i = 0; i < JUMP_TABLE_DATA_SIZE; i++)
               jump_table[jump_table_data[i].ch] = jump_table_data[i].f;

       stack_init(&bmachine.stack);

       for (i = 0; i < bmachine.reg_array_size; i++)
               stack_init(&bmachine.reg[i]);

       bmachine.readstack_sz = READSTACK_SIZE;
       bmachine.readstack = calloc(sizeof(struct source),
           bmachine.readstack_sz);
       if (bmachine.readstack == NULL)
               err(1, NULL);
       bmachine.obase = bmachine.ibase = 10;
       (void)signal(SIGINT, sighandler);
}

u_int
bmachine_scale(void)
{
       return bmachine.scale;
}

/* Reset the things needed before processing a (new) file */
void
reset_bmachine(struct source *src)
{
       bmachine.readsp = 0;
       bmachine.readstack[0] = *src;
}

static __inline int
readch(void)
{
       struct source *src = &bmachine.readstack[bmachine.readsp];

       return src->vtable->readchar(src);
}

static __inline void
unreadch(void)
{
       struct source *src = &bmachine.readstack[bmachine.readsp];

       src->vtable->unreadchar(src);
}

static __inline char *
readline(void)
{
       struct source *src = &bmachine.readstack[bmachine.readsp];

       return src->vtable->readline(src);
}

static __inline void
src_free(void)
{
       struct source *src = &bmachine.readstack[bmachine.readsp];

       src->vtable->free(src);
}

#ifdef DEBUGGING
void
pn(const char *str, const struct number *n)
{
       char *p = BN_bn2dec(n->number);
       if (p == NULL)
               err(1, "BN_bn2dec failed");
       (void)fputs(str, stderr);
       (void)fprintf(stderr, " %s (%u)\n" , p, n->scale);
       OPENSSL_free(p);
}

void
pbn(const char *str, const BIGNUM *n)
{
       char *p = BN_bn2dec(n);
       if (p == NULL)
               err(1, "BN_bn2dec failed");
       (void)fputs(str, stderr);
       (void)fprintf(stderr, " %s\n", p);
       OPENSSL_free(p);
}

#endif

static __inline u_int
max(u_int a, u_int b)
{
       return a > b ? a : b;
}

static BN_ULONG factors[] = {
       0, 10, 100, 1000, 10000, 100000, 1000000, 10000000,
       100000000, 1000000000
};

void
scale_number(BIGNUM *n, int s)
{
       size_t abs_scale;

       if (s == 0)
               return;

       abs_scale = (size_t)(s > 0 ? s : -s);

       if (abs_scale < sizeof(factors)/sizeof(factors[0])) {
               if (s > 0)
                       bn_check(BN_mul_word(n, factors[abs_scale]));
               else
                       (void)BN_div_word(n, factors[abs_scale]);
       } else {
               BIGNUM *a, *p;
               BN_CTX *ctx;

               a = BN_new();
               bn_checkp(a);
               p = BN_new();
               bn_checkp(p);
               ctx = BN_CTX_new();
               bn_checkp(ctx);

               bn_check(BN_set_word(a, 10));
               bn_check(BN_set_word(p, (BN_ULONG)abs_scale));
               bn_check(BN_exp(a, a, p, ctx));
               if (s > 0)
                       bn_check(BN_mul(n, n, a, ctx));
               else
                       bn_check(BN_div(n, NULL, n, a, ctx));
               BN_CTX_free(ctx);
               BN_free(a);
               BN_free(p);
       }
}

void
split_number(const struct number *n, BIGNUM *i, BIGNUM *f)
{
       u_long rem;

       bn_checkp(BN_copy(i, n->number));

       if (n->scale == 0 && f != NULL)
               bn_check(BN_set_word(f, 0));
       else if (n->scale < sizeof(factors)/sizeof(factors[0])) {
               rem = BN_div_word(i, factors[n->scale]);
               if (f != NULL)
                       bn_check(BN_set_word(f, (BN_ULONG)rem));
       } else {
               BIGNUM *a, *p;
               BN_CTX *ctx;

               a = BN_new();
               bn_checkp(a);
               p = BN_new();
               bn_checkp(p);
               ctx = BN_CTX_new();
               bn_checkp(ctx);

               bn_check(BN_set_word(a, 10));
               bn_check(BN_set_word(p, n->scale));
               bn_check(BN_exp(a, a, p, ctx));
               bn_check(BN_div(i, f, n->number, a, ctx));
               BN_CTX_free(ctx);
               BN_free(a);
               BN_free(p);
       }
}

void
normalize(struct number *n, u_int s)
{
       scale_number(n->number, (int)(s - n->scale));
       n->scale = s;
}

static u_long
get_ulong(struct number *n)
{
       normalize(n, 0);
       return BN_get_word(n->number);
}

void
negate(struct number *n)
{
       BN_set_negative(n->number, !BN_is_negative(n->number));
}

static __inline void
push_number(struct number *n)
{
       stack_pushnumber(&bmachine.stack, n);
}

static __inline void
push_string(char *string)
{
       stack_pushstring(&bmachine.stack, string);
}

static __inline void
push(struct value *v)
{
       stack_push(&bmachine.stack, v);
}

static __inline struct value *
tos(void)
{
       return stack_tos(&bmachine.stack);
}

static __inline struct value *
pop(void)
{
       return stack_pop(&bmachine.stack);
}

static __inline struct number *
pop_number(void)
{
       return stack_popnumber(&bmachine.stack);
}

static __inline char *
pop_string(void)
{
       return stack_popstring(&bmachine.stack);
}

static __inline void
clear_stack(void)
{
       stack_clear(&bmachine.stack);
}

static __inline void
print_stack(void)
{
       stack_print(stdout, &bmachine.stack, "", bmachine.obase);
}

static __inline void
print_tos(void)
{
       struct value *value = tos();
       if (value != NULL) {
               print_value(stdout, value, "", bmachine.obase);
               (void)putchar('\n');
       }
       else
               warnx("stack empty");
}

static void
print_err(void)
{
       struct value *value = tos();
       if (value != NULL) {
               print_value(stderr, value, "", bmachine.obase);
               (void)putc('\n', stderr);
       }
       else
               warnx("stack empty");
}

static void
pop_print(void)
{
       struct value *value = pop();

       if (value != NULL) {
               switch (value->type) {
               case BCODE_NONE:
                       break;
               case BCODE_NUMBER:
                       normalize(value->u.num, 0);
                       print_ascii(stdout, value->u.num);
                       (void)fflush(stdout);
                       break;
               case BCODE_STRING:
                       (void)fputs(value->u.string, stdout);
                       (void)fflush(stdout);
                       break;
               }
               stack_free_value(value);
       }
}

static void
pop_printn(void)
{
       struct value *value = pop();

       if (value != NULL) {
               print_value(stdout, value, "", bmachine.obase);
               (void)fflush(stdout);
               stack_free_value(value);
       }
}

static __inline void
dup(void)
{
       stack_dup(&bmachine.stack);
}

static void
swap(void)
{
       stack_swap(&bmachine.stack);
}

static void
drop(void)
{
       struct value *v = pop();
       if (v != NULL)
               stack_free_value(v);
}

static void
get_scale(void)
{
       struct number   *n;

       n = new_number();
       bn_check(BN_set_word(n->number, bmachine.scale));
       push_number(n);
}

static void
set_scale(void)
{
       struct number   *n;
       u_long          scale;

       n = pop_number();
       if (n != NULL) {
               if (BN_is_negative(n->number))
                       warnx("scale must be a nonnegative number");
               else {
                       scale = get_ulong(n);
                       if (scale != NO_NUMBER && scale <= UINT_MAX)
                               bmachine.scale = (u_int)scale;
                       else
                               warnx("scale too large");
                       }
               free_number(n);
       }
}

static void
get_obase(void)
{
       struct number   *n;

       n = new_number();
       bn_check(BN_set_word(n->number, bmachine.obase));
       push_number(n);
}

static void
set_obase(void)
{
       struct number   *n;
       u_long          base;

       n = pop_number();
       if (n != NULL) {
               base = get_ulong(n);
               if (base != NO_NUMBER && base > 1 && base <= UINT_MAX)
                       bmachine.obase = (u_int)base;
               else
                       warnx("output base must be a number greater than 1");
               free_number(n);
       }
}

static void
get_ibase(void)
{
       struct number *n;

       n = new_number();
       bn_check(BN_set_word(n->number, bmachine.ibase));
       push_number(n);
}

static void
set_ibase(void)
{
       struct number   *n;
       u_long          base;

       n = pop_number();
       if (n != NULL) {
               base = get_ulong(n);
               if (base != NO_NUMBER && 2 <= base && base <= 16)
                       bmachine.ibase = (u_int)base;
               else
                       warnx("input base must be a number between 2 and 16 "
                           "(inclusive)");
               free_number(n);
       }
}

static void
stackdepth(void)
{
       size_t i;
       struct number *n;

       i = stack_size(&bmachine.stack);
       n = new_number();
       bn_check(BN_set_word(n->number, (BN_ULONG)i));
       push_number(n);
}

static void
push_scale(void)
{
       struct value    *value;
       u_int           scale = 0;
       struct number   *n;


       value = pop();
       if (value != NULL) {
               switch (value->type) {
               case BCODE_NONE:
                       return;
               case BCODE_NUMBER:
                       scale = value->u.num->scale;
                       break;
               case BCODE_STRING:
                       break;
               }
               stack_free_value(value);
               n = new_number();
               bn_check(BN_set_word(n->number, scale));
               push_number(n);
       }
}

static u_int
count_digits(const struct number *n)
{
       struct number   *int_part, *fract_part;
       u_int           i;

       if (BN_is_zero(n->number))
               return n->scale ? n->scale : 1;

       int_part = new_number();
       fract_part = new_number();
       fract_part->scale = n->scale;
       split_number(n, int_part->number, fract_part->number);

       i = 0;
       while (!BN_is_zero(int_part->number)) {
               (void)BN_div_word(int_part->number, 10);
               i++;
       }
       free_number(int_part);
       free_number(fract_part);
       return i + n->scale;
}

static void
num_digits(void)
{
       struct value    *value;
       size_t          digits;
       struct number   *n = NULL;

       value = pop();
       if (value != NULL) {
               switch (value->type) {
               case BCODE_NONE:
                       return;
               case BCODE_NUMBER:
                       digits = count_digits(value->u.num);
                       n = new_number();
                       bn_check(BN_set_word(n->number, (BN_ULONG)digits));
                       break;
               case BCODE_STRING:
                       digits = strlen(value->u.string);
                       n = new_number();
                       bn_check(BN_set_word(n->number, (BN_ULONG)digits));
                       break;
               }
               stack_free_value(value);
               push_number(n);
       }
}

static void
to_ascii(void)
{
       char            str[2];
       struct value    *value;
       struct number   *n;

       value = pop();
       if (value != NULL) {
               str[1] = '\0';
               switch (value->type) {
               case BCODE_NONE:
                       return;
               case BCODE_NUMBER:
                       n = value->u.num;
                       normalize(n, 0);
                       if (BN_num_bits(n->number) > 8)
                               bn_check(BN_mask_bits(n->number, 8));
                       str[0] = (char)BN_get_word(n->number);
                       break;
               case BCODE_STRING:
                       str[0] = value->u.string[0];
                       break;
               }
               stack_free_value(value);
               push_string(bstrdup(str));
       }
}

static int
readreg(void)
{
       int idx, ch1, ch2;

       idx = readch();
       if (idx == 0xff && bmachine.extended_regs) {
               ch1 = readch();
               ch2 = readch();
               if (ch1 == EOF || ch2 == EOF) {
                       warnx("unexpected eof");
                       idx = -1;
               } else
                       idx = (ch1 << 8) + ch2 + UCHAR_MAX + 1;
       }
       if (idx < 0 || (size_t)idx >= bmachine.reg_array_size) {
               warnx("internal error: reg num = %d", idx);
               idx = -1;
       }
       return idx;
}

static void
load(void)
{
       int             idx;
       struct value    *v, copy;
       struct number   *n;

       idx = readreg();
       if (idx >= 0) {
               v = stack_tos(&bmachine.reg[idx]);
               if (v == NULL) {
                       n = new_number();
                       bn_check(BN_set_word(n->number, 0));
                       push_number(n);
               } else
                       push(stack_dup_value(v, &copy));
       }
}

static void
store(void)
{
       int             idx;
       struct value    *val;

       idx = readreg();
       if (idx >= 0) {
               val = pop();
               if (val == NULL) {
                       return;
               }
               stack_set_tos(&bmachine.reg[idx], val);
       }
}

static void
load_stack(void)
{
       int             idx;
       struct stack    *stack;
       struct value    *value;

       idx = readreg();
       if (idx >= 0) {
               stack = &bmachine.reg[idx];
               value = NULL;
               if (stack_size(stack) > 0) {
                       value = stack_pop(stack);
               }
               if (value != NULL)
                       push(value);
               else
                       warnx("stack register '%c' (0%o) is empty",
                           idx, idx);
       }
}

static void
store_stack(void)
{
       int             idx;
       struct value    *value;

       idx = readreg();
       if (idx >= 0) {
               value = pop();
               if (value == NULL)
                       return;
               stack_push(&bmachine.reg[idx], value);
       }
}

static void
load_array(void)
{
       int                     reg;
       struct number           *inumber, *n;
       u_long                  idx;
       struct stack            *stack;
       struct value            *v, copy;

       reg = readreg();
       if (reg >= 0) {
               inumber = pop_number();
               if (inumber == NULL)
                       return;
               idx = get_ulong(inumber);
               if (BN_is_negative(inumber->number))
                       warnx("negative idx");
               else if (idx == NO_NUMBER || idx > MAX_ARRAY_INDEX)
                       warnx("idx too big");
               else {
                       stack = &bmachine.reg[reg];
                       v = frame_retrieve(stack, idx);
                       if (v == NULL || v->type == BCODE_NONE) {
                               n = new_number();
                               bn_check(BN_set_word(n->number, 0));
                               push_number(n);
                       }
                       else
                               push(stack_dup_value(v, &copy));
               }
               free_number(inumber);
       }
}

static void
store_array(void)
{
       int                     reg;
       struct number           *inumber;
       u_long                  idx;
       struct value            *value;
       struct stack            *stack;

       reg = readreg();
       if (reg >= 0) {
               inumber = pop_number();
               if (inumber == NULL)
                       return;
               value = pop();
               if (value == NULL) {
                       free_number(inumber);
                       return;
               }
               idx = get_ulong(inumber);
               if (BN_is_negative(inumber->number)) {
                       warnx("negative idx");
                       stack_free_value(value);
               } else if (idx == NO_NUMBER || idx > MAX_ARRAY_INDEX) {
                       warnx("idx too big");
                       stack_free_value(value);
               } else {
                       stack = &bmachine.reg[reg];
                       frame_assign(stack, idx, value);
               }
               free_number(inumber);
       }
}

static void
push_line(void)
{
       push_string(read_string(&bmachine.readstack[bmachine.readsp]));
}

static void
comment(void)
{
       free(readline());
}

static void
badd(void)
{
       struct number   *a, *b;
       struct number   *r;

       a = pop_number();
       if (a == NULL)
               return;
       b = pop_number();
       if (b == NULL) {
               push_number(a);
               return;
       }

       r = new_number();
       r->scale = max(a->scale, b->scale);
       if (r->scale > a->scale)
               normalize(a, r->scale);
       else if (r->scale > b->scale)
               normalize(b, r->scale);
       bn_check(BN_add(r->number, a->number, b->number));
       push_number(r);
       free_number(a);
       free_number(b);
}

static void
bsub(void)
{
       struct number   *a, *b;
       struct number   *r;

       a = pop_number();
       if (a == NULL)
               return;
       b = pop_number();
       if (b == NULL) {
               push_number(a);
               return;
       }

       r = new_number();

       r->scale = max(a->scale, b->scale);
       if (r->scale > a->scale)
               normalize(a, r->scale);
       else if (r->scale > b->scale)
               normalize(b, r->scale);
       bn_check(BN_sub(r->number, b->number, a->number));
       push_number(r);
       free_number(a);
       free_number(b);
}

void
bmul_number(struct number *r, struct number *a, struct number *b, u_int scale)
{
       BN_CTX          *ctx;

       /* Create copies of the scales, since r might be equal to a or b */
       u_int ascale = a->scale;
       u_int bscale = b->scale;
       u_int rscale = ascale + bscale;

       ctx = BN_CTX_new();
       bn_checkp(ctx);
       bn_check(BN_mul(r->number, a->number, b->number, ctx));
       BN_CTX_free(ctx);

       r->scale = rscale;
       if (rscale > bmachine.scale && rscale > ascale && rscale > bscale)
               normalize(r, max(scale, max(ascale, bscale)));
}

static void
bmul(void)
{
       struct number   *a, *b;
       struct number   *r;

       a = pop_number();
       if (a == NULL)
               return;
       b = pop_number();
       if (b == NULL) {
               push_number(a);
               return;
       }

       r = new_number();
       bmul_number(r, a, b, bmachine.scale);

       push_number(r);
       free_number(a);
       free_number(b);
}

static void
bdiv(void)
{
       struct number   *a, *b;
       struct number   *r;
       u_int           scale;
       BN_CTX          *ctx;

       a = pop_number();
       if (a == NULL)
               return;
       b = pop_number();
       if (b == NULL) {
               push_number(a);
               return;
       }

       r = new_number();
       r->scale = bmachine.scale;
       scale = max(a->scale, b->scale);

       if (BN_is_zero(a->number))
               warnx("divide by zero");
       else {
               normalize(a, scale);
               normalize(b, scale + r->scale);

               ctx = BN_CTX_new();
               bn_checkp(ctx);
               bn_check(BN_div(r->number, NULL, b->number, a->number, ctx));
               BN_CTX_free(ctx);
       }
       push_number(r);
       free_number(a);
       free_number(b);
}

static void
bmod(void)
{
       struct number   *a, *b;
       struct number   *r;
       u_int           scale;
       BN_CTX          *ctx;

       a = pop_number();
       if (a == NULL)
               return;
       b = pop_number();
       if (b == NULL) {
               push_number(a);
               return;
       }

       r = new_number();
       scale = max(a->scale, b->scale);
       r->scale = max(b->scale, a->scale + bmachine.scale);

       if (BN_is_zero(a->number))
               warnx("remainder by zero");
       else {
               normalize(a, scale);
               normalize(b, scale + bmachine.scale);

               ctx = BN_CTX_new();
               bn_checkp(ctx);
               bn_check(BN_mod(r->number, b->number, a->number, ctx));
               BN_CTX_free(ctx);
       }
       push_number(r);
       free_number(a);
       free_number(b);
}

static void
bdivmod(void)
{
       struct number   *a, *b;
       struct number   *rdiv, *rmod;
       u_int           scale;
       BN_CTX          *ctx;

       a = pop_number();
       if (a == NULL)
               return;
       b = pop_number();
       if (b == NULL) {
               push_number(a);
               return;
       }

       rdiv = new_number();
       rmod = new_number();
       rdiv->scale = bmachine.scale;
       rmod->scale = max(b->scale, a->scale + bmachine.scale);
       scale = max(a->scale, b->scale);

       if (BN_is_zero(a->number))
               warnx("divide by zero");
       else {
               normalize(a, scale);
               normalize(b, scale + bmachine.scale);

               ctx = BN_CTX_new();
               bn_checkp(ctx);
               bn_check(BN_div(rdiv->number, rmod->number,
                   b->number, a->number, ctx));
               BN_CTX_free(ctx);
       }
       push_number(rdiv);
       push_number(rmod);
       free_number(a);
       free_number(b);
}

static void
bexp(void)
{
       struct number   *a, *p;
       struct number   *r;
       bool            neg;
       u_int           rscale;

       p = pop_number();
       if (p == NULL)
               return;
       a = pop_number();
       if (a == NULL) {
               push_number(p);
               return;
       }

       if (p->scale != 0) {
               BIGNUM *i, *f;
               i = BN_new();
               bn_checkp(i);
               f = BN_new();
               bn_checkp(f);
               split_number(p, i, f);
               if (!BN_is_zero(f))
                       warnx("Runtime warning: non-zero fractional part in exponent");
               BN_free(i);
               BN_free(f);
       }

       normalize(p, 0);

       neg = false;
       if (BN_is_negative(p->number)) {
               neg = true;
               negate(p);
               rscale = bmachine.scale;
       } else {
               /* Posix bc says min(a.scale * b, max(a.scale, scale) */
               u_long  b;
               u_int   m;

               b = BN_get_word(p->number);
               m = max(a->scale, bmachine.scale);
               rscale = a->scale * (u_int)b;
               if (rscale > m || (a->scale > 0 && (b == NO_NUMBER ||
                   b > UINT_MAX)))
                       rscale = m;
       }

       if (BN_is_zero(p->number)) {
               r = new_number();
               bn_check(BN_one(r->number));
               normalize(r, rscale);
       } else {
               u_int ascale, mscale;

               ascale = a->scale;
               while (!BN_is_bit_set(p->number, 0)) {
                       ascale *= 2;
                       bmul_number(a, a, a, ascale);
                       bn_check(BN_rshift1(p->number, p->number));
               }

               r = dup_number(a);
               bn_check(BN_rshift1(p->number, p->number));

               mscale = ascale;
               while (!BN_is_zero(p->number)) {
                       ascale *= 2;
                       bmul_number(a, a, a, ascale);
                       if (BN_is_bit_set(p->number, 0)) {
                               mscale += ascale;
                               bmul_number(r, r, a, mscale);
                       }
                       bn_check(BN_rshift1(p->number, p->number));
               }

               if (neg) {
                       BN_CTX  *ctx;
                       BIGNUM  *one;

                       one = BN_new();
                       bn_checkp(one);
                       bn_check(BN_one(one));
                       ctx = BN_CTX_new();
                       bn_checkp(ctx);
                       scale_number(one, (int)(r->scale + rscale));

                       if (BN_is_zero(r->number))
                               warnx("divide by zero");
                       else
                               bn_check(BN_div(r->number, NULL, one,
                                   r->number, ctx));
                       BN_free(one);
                       BN_CTX_free(ctx);
                       r->scale = rscale;
               } else
                       normalize(r, rscale);
       }
       push_number(r);
       free_number(a);
       free_number(p);
}

static bool
bsqrt_stop(const BIGNUM *x, const BIGNUM *y, u_int *onecount)
{
       BIGNUM *r;
       bool ret;

       r = BN_new();
       bn_checkp(r);
       bn_check(BN_sub(r, x, y));
       if (BN_is_one(r))
               (*onecount)++;
       ret = BN_is_zero(r);
       BN_free(r);
       return ret || *onecount > 1;
}

static void
bsqrt(void)
{
       struct number   *n;
       struct number   *r;
       BIGNUM          *x, *y;
       u_int           scale, onecount;
       BN_CTX          *ctx;

       onecount = 0;
       n = pop_number();
       if (n == NULL)
               return;
       if (BN_is_zero(n->number)) {
               r = new_number();
               push_number(r);
       } else if (BN_is_negative(n->number))
               warnx("square root of negative number");
       else {
               scale = max(bmachine.scale, n->scale);
               normalize(n, 2*scale);
               x = BN_dup(n->number);
               bn_checkp(x);
               bn_check(BN_rshift(x, x, BN_num_bits(x)/2));
               y = BN_new();
               bn_checkp(y);
               ctx = BN_CTX_new();
               bn_checkp(ctx);
               for (;;) {
                       bn_checkp(BN_copy(y, x));
                       bn_check(BN_div(x, NULL, n->number, x, ctx));
                       bn_check(BN_add(x, x, y));
                       bn_check(BN_rshift1(x, x));
                       if (bsqrt_stop(x, y, &onecount))
                               break;
               }
               r = bmalloc(sizeof(*r));
               r->scale = scale;
               r->number = y;
               BN_free(x);
               BN_CTX_free(ctx);
               push_number(r);
       }

       free_number(n);
}

static void
not(void)
{
       struct number   *a;

       a = pop_number();
       if (a == NULL)
               return;
       a->scale = 0;
       bn_check(BN_set_word(a->number, BN_get_word(a->number) ? 0 : 1));
       push_number(a);
}

static void
equal(void)
{
       compare(BCODE_EQUAL);
}

static void
equal_numbers(void)
{
       struct number *a, *b, *r;

       a = pop_number();
       if (a == NULL)
               return;
       b = pop_number();
       if (b == NULL) {
               push_number(a);
               return;
       }
       r = new_number();
       bn_check(BN_set_word(r->number,
           compare_numbers(BCODE_EQUAL, a, b) ? 1 : 0));
       push_number(r);
}

static void
less_numbers(void)
{
       struct number *a, *b, *r;

       a = pop_number();
       if (a == NULL)
               return;
       b = pop_number();
       if (b == NULL) {
               push_number(a);
               return;
       }
       r = new_number();
       bn_check(BN_set_word(r->number,
           compare_numbers(BCODE_LESS, a, b) ? 1 : 0));
       push_number(r);
}

static void
lesseq_numbers(void)
{
       struct number *a, *b, *r;

       a = pop_number();
       if (a == NULL)
               return;
       b = pop_number();
       if (b == NULL) {
               push_number(a);
               return;
       }
       r = new_number();
       bn_check(BN_set_word(r->number,
           compare_numbers(BCODE_NOT_GREATER, a, b) ? 1 : 0));
       push_number(r);
}

static void
not_equal(void)
{
       compare(BCODE_NOT_EQUAL);
}

static void
less(void)
{
       compare(BCODE_LESS);
}

static void
not_compare(void)
{
       switch (readch()) {
       case '<':
               not_less();
               break;
       case '>':
               not_greater();
               break;
       case '=':
               not_equal();
               break;
       default:
               unreadch();
               (void)fprintf(stderr, "! command is deprecated\n");
               break;
       }
}

static void
not_less(void)
{
       compare(BCODE_NOT_LESS);
}

static void
greater(void)
{
       compare(BCODE_GREATER);
}

static void
not_greater(void)
{
       compare(BCODE_NOT_GREATER);
}

static bool
compare_numbers(enum bcode_compare type, struct number *a, struct number *b)
{
       u_int   scale;
       int     cmp;

       scale = max(a->scale, b->scale);

       if (scale > a->scale)
               normalize(a, scale);
       else if (scale > b->scale)
               normalize(b, scale);

       cmp = BN_cmp(a->number, b->number);

       free_number(a);
       free_number(b);

       switch (type) {
       case BCODE_EQUAL:
               return cmp == 0;
       case BCODE_NOT_EQUAL:
               return cmp != 0;
       case BCODE_LESS:
               return cmp < 0;
       case BCODE_NOT_LESS:
               return cmp >= 0;
       case BCODE_GREATER:
               return cmp > 0;
       case BCODE_NOT_GREATER:
               return cmp <= 0;
       }
       return false;
}

static void
compare(enum bcode_compare type)
{
       int             idx, elseidx;
       struct number   *a, *b;
       bool            ok;
       struct value    *v;

       elseidx = NO_ELSE;
       idx = readreg();
       if (readch() == 'e')
               elseidx = readreg();
       else
               unreadch();

       a = pop_number();
       if (a == NULL)
               return;
       b = pop_number();
       if (b == NULL) {
               push_number(a);
               return;
       }

       ok = compare_numbers(type, a, b);

       if (!ok && elseidx != NO_ELSE)
               idx = elseidx;

       if (idx >= 0 && (ok || (!ok && elseidx != NO_ELSE))) {
               v = stack_tos(&bmachine.reg[idx]);
               if (v == NULL)
                       warnx("register '%c' (0%o) is empty", idx, idx);
               else {
                       switch(v->type) {
                       case BCODE_NONE:
                               warnx("register '%c' (0%o) is empty", idx, idx);
                               break;
                       case BCODE_NUMBER:
                               warn("eval called with non-string argument");
                               break;
                       case BCODE_STRING:
                               eval_string(bstrdup(v->u.string));
                               break;
                       }
               }
       }
}


static void
nop(void)
{
}

static void
quit(void)
{
       if (bmachine.readsp < 2)
               exit(0);
       src_free();
       bmachine.readsp--;
       src_free();
       bmachine.readsp--;
}

static void
quitN(void)
{
       struct number   *n;
       u_long          i;

       n = pop_number();
       if (n == NULL)
               return;
       i = get_ulong(n);
       free_number(n);
       if (i == NO_NUMBER || i == 0)
               warnx("Q command requires a number >= 1");
       else if (bmachine.readsp < i)
               warnx("Q command argument exceeded string execution depth");
       else {
               while (i-- > 0) {
                       src_free();
                       bmachine.readsp--;
               }
       }
}

static void
skipN(void)
{
       struct number   *n;
       u_long          i;

       n = pop_number();
       if (n == NULL)
               return;
       i = get_ulong(n);
       if (i == NO_NUMBER)
               warnx("J command requires a number >= 0");
       else if (i > 0 && bmachine.readsp < i)
               warnx("J command argument exceeded string execution depth");
       else {
               while (i-- > 0) {
                       src_free();
                       bmachine.readsp--;
               }
               skip_until_mark();
       }
}

static void
skip_until_mark(void)
{
       int ch;

       for (;;) {
               ch = readch();
               switch (ch) {
               case 'M':
                       return;
               case EOF:
                       errx(1, "mark not found");
                       return;
               case 'l':
               case 'L':
               case 's':
               case 'S':
               case ':':
               case ';':
               case '<':
               case '>':
               case '=':
                       (void)readreg();
                       if (readch() == 'e')
                               (void)readreg();
                       else
                               unreadch();
                       break;
               case '[':
                       free(read_string(&bmachine.readstack[bmachine.readsp]));
                       break;
               case '!':
                       switch (ch = readch()) {
                               case '<':
                               case '>':
                               case '=':
                                       (void)readreg();
                                       if (readch() == 'e')
                                               (void)readreg();
                                       else
                                               unreadch();
                                       break;
                               default:
                                       free(readline());
                                       break;
                       }
                       break;
               default:
                       break;
               }
       }
}

static void
parse_number(void)
{
       unreadch();
       push_number(readnumber(&bmachine.readstack[bmachine.readsp],
           bmachine.ibase));
}

static void
unknown(void)
{
       int ch = bmachine.readstack[bmachine.readsp].lastchar;
       warnx("%c (0%o) is unimplemented", ch, ch);
}

static void
eval_string(char *p)
{
       int ch;

       if (bmachine.readsp > 0) {
               /* Check for tail call. Do not recurse in that case. */
               ch = readch();
               if (ch == EOF) {
                       src_free();
                       src_setstring(&bmachine.readstack[bmachine.readsp], p);
                       return;
               } else
                       unreadch();
       }
       if (bmachine.readsp == bmachine.readstack_sz - 1) {
               size_t newsz = bmachine.readstack_sz * 2;
               struct source *stack = bmachine.readstack;
               int ret = reallocarr(&stack, newsz, sizeof(struct source));
               if (ret)
                       errc(1, ret, "recursion too deep");
               bmachine.readstack_sz = newsz;
               bmachine.readstack = stack;
       }
       src_setstring(&bmachine.readstack[++bmachine.readsp], p);
}

static void
eval_line(void)
{
       /* Always read from stdin */
       struct source   in;
       char            *p;

       clearerr(stdin);
       src_setstream(&in, stdin);
       p = (*in.vtable->readline)(&in);
       eval_string(p);
}

static void
eval_tos(void)
{
       char *p;

       p = pop_string();
       if (p != NULL)
               eval_string(p);
}

void
eval(void)
{
       int     ch;

       for (;;) {
               ch = readch();
               if (ch == EOF) {
                       if (bmachine.readsp == 0)
                               return;
                       src_free();
                       bmachine.readsp--;
                       continue;
               }
               if (bmachine.interrupted) {
                       if (bmachine.readsp > 0) {
                               src_free();
                               bmachine.readsp--;
                               continue;
                       } else
                               bmachine.interrupted = false;
               }
#ifdef DEBUGGING
               (void)fprintf(stderr, "# %c\n", ch);
               stack_print(stderr, &bmachine.stack, "* ",
                   bmachine.obase);
               (void)fprintf(stderr, "%zd =>\n", bmachine.readsp);
#endif

               if (0 <= ch && ch < UCHAR_MAX)
                       (*jump_table[ch])();
               else
                       warnx("internal error: opcode %d", ch);

#ifdef DEBUGGING
               stack_print(stderr, &bmachine.stack, "* ",
                   bmachine.obase);
               (void)fprintf(stderr, "%zd ==\n", bmachine.readsp);
#endif
       }
}

You are viewing proxied material from ftp.icm.edu.pl. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.