fatbase

portable OpenBSD tools
git clone git://git.2f30.org/fatbase.git
Log | Files | Refs

commit 31791265cbd54d6158aa81ba37a67b740531ee79
parent 2befc4e623a69bdfcdc118e58769c2bc3c9c7788
Author: Hiltjo Posthuma <hiltjo@codemadness.org>
Date:   Fri Nov 21 22:19:40 +0100

add dc

Diffstat:
dc/Makefile | 10++++++++++
dc/bcode.c | 1768+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
dc/bcode.h | 97+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
dc/dc.1 | 537+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
dc/dc.c | 111+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
dc/extern.h | 62++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
dc/inout.c | 412+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
dc/mem.c | 104+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
dc/stack.c | 360+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
9 files changed, 3461 insertions(+), 0 deletions(-)
diff --git a/dc/Makefile b/dc/Makefile @@ -0,0 +1,10 @@ +OBJ = dc.o bcode.o inout.o mem.o stack.o +TARG = dc +LDLIBS = + +all: $(TARG) + +include ../std.mk + +clean: + rm -f $(TARG) $(OBJ) diff --git a/dc/bcode.c b/dc/bcode.c @@ -0,0 +1,1768 @@ +/* $OpenBSD: bcode.c,v 1.46 2014/10/08 03:59:56 doug Exp $ */ + +/* + * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net> + * + * 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 <ssl/ssl.h> +#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_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 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 bexec(char *); +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 }, + { '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) +{ + int 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 unsigned long factors[] = { + 0, 10, 100, 1000, 10000, 100000, 1000000, 10000000, + 100000000, 1000000000 +}; + +void +scale_number(BIGNUM *n, int s) +{ + int abs_scale; + + if (s == 0) + return; + + abs_scale = 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, 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_zero(f)); + 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, 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, 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 +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 != BN_MASK2 && 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 != BN_MASK2 && 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 != BN_MASK2 && 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, 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, digits)); + break; + case BCODE_STRING: + digits = strlen(value->u.string); + n = new_number(); + bn_check(BN_set_word(n->number, 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 || 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_zero(n->number)); + 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 == BN_MASK2 || 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_zero(n->number)); + 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 == BN_MASK2 || 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 +bexec(char *line) +{ + (void)system(line); + free(line); +} + +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 == BN_MASK2 || + 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, 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(); + bexec(readline()); + 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 == BN_MASK2 || 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 == BN_MASK2) + 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; + stack = reallocarray(bmachine.readstack, newsz, + sizeof(struct source)); + if (stack == NULL) + err(1, "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) + return; + 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 + } +} diff --git a/dc/bcode.h b/dc/bcode.h @@ -0,0 +1,97 @@ +/* $OpenBSD: bcode.h,v 1.7 2012/11/07 11:06:14 otto Exp $ */ + +/* + * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net> + * + * 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/types.h> +#include <ssl/bn.h> + + +struct number { + BIGNUM *number; + u_int scale; +}; + +enum stacktype { + BCODE_NONE, + BCODE_NUMBER, + BCODE_STRING +}; + +enum bcode_compare { + BCODE_EQUAL, + BCODE_NOT_EQUAL, + BCODE_LESS, + BCODE_NOT_LESS, + BCODE_GREATER, + BCODE_NOT_GREATER +}; + +struct array; + +struct value { + union { + struct number *num; + char *string; + } u; + struct array *array; + enum stacktype type; +}; + +struct array { + struct value *data; + size_t size; +}; + +struct stack { + struct value *stack; + ssize_t sp; + size_t size; +}; + +struct source; + +struct vtable { + int (*readchar)(struct source *); + void (*unreadchar)(struct source *); + char *(*readline)(struct source *); + void (*free)(struct source *); +}; + +struct source { + struct vtable *vtable; + union { + FILE *stream; + struct { + u_char *buf; + size_t pos; + } string; + } u; + int lastchar; +}; + +void init_bmachine(bool); +void reset_bmachine(struct source *); +u_int bmachine_scale(void); +void scale_number(BIGNUM *, int); +void normalize(struct number *, u_int); +void eval(void); +void pn(const char *, const struct number *); +void pbn(const char *, const BIGNUM *); +void negate(struct number *); +void split_number(const struct number *, BIGNUM *, BIGNUM *); +void bmul_number(struct number *, struct number *, + struct number *, u_int scale); diff --git a/dc/dc.1 b/dc/dc.1 @@ -0,0 +1,537 @@ +.\" $OpenBSD: dc.1,v 1.27 2012/08/19 12:07:21 jmc Exp $ +.\" +.\" Copyright (C) Caldera International Inc. 2001-2002. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code and documentation must retain the above +.\" copyright notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. All advertising materials mentioning features or use of this software +.\" must display the following acknowledgement: +.\" This product includes software developed or owned by Caldera +.\" International, Inc. +.\" 4. Neither the name of Caldera International, Inc. nor the names of other +.\" contributors may be used to endorse or promote products derived from +.\" this software without specific prior written permission. +.\" +.\" USE OF THE SOFTWARE PROVIDED FOR UNDER THIS LICENSE BY CALDERA +.\" INTERNATIONAL, INC. AND CONTRIBUTORS ``AS IS'' AND ANY EXPRESS OR +.\" IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES +.\" OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. +.\" IN NO EVENT SHALL CALDERA INTERNATIONAL, INC. BE LIABLE FOR ANY DIRECT, +.\" INDIRECT INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES +.\" (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR +.\" SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, +.\" STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING +.\" IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +.\" POSSIBILITY OF SUCH DAMAGE. +.\" +.\" @(#)dc.1 8.1 (Berkeley) 6/6/93 +.\" +.Dd $Mdocdate: August 19 2012 $ +.Dt DC 1 +.Os +.Sh NAME +.Nm dc +.Nd desk calculator +.Sh SYNOPSIS +.Nm +.Op Fl x +.Op Fl e Ar expression +.Op Ar file +.Sh DESCRIPTION +.Nm +is an arbitrary precision arithmetic package. +The overall structure of +.Nm +is +a stacking (reverse Polish) calculator i.e.\& +numbers are stored on a stack. +Adding a number pushes it onto the stack. +Arithmetic operations pop arguments off the stack +and push the results. +See also the +.Xr bc 1 +utility, which is a preprocessor for +.Nm +providing infix notation and a C-like syntax +which implements functions and reasonable control +structures for programs. +The options are as follows: +.Bl -tag -width Ds +.It Fl e Ar expression +Evaluate +.Ar expression . +If multiple +.Fl e +options are specified, they will be processed in the order given. +.It Fl x +Enable extended register mode. +This mode is used by +.Xr bc 1 +to allow more than 256 registers. +See +.Sx Registers +for a more detailed description. +.El +.Pp +If neither +.Ar expression +nor +.Ar file +are specified on the command line, +.Nm +reads from the standard input. +Otherwise +.Ar expression +and +.Ar file +are processed and +.Nm +exits. +.Pp +Ordinarily, +.Nm +operates on decimal integers, +but one may specify an input base, output base, +and a number of fractional digits (scale) to be maintained. +Whitespace is ignored, except where it signals the end of a number, +end of a line or when a register name is expected. +The following constructions are recognized: +.Bl -tag -width "number" +.It Va number +The value of the number is pushed on the stack. +A number is an unbroken string of the digits 0\-9 and letters A\-F. +It may be preceded by an underscore +.Pq Sq _ +to input a negative number. +A number may contain a single decimal point. +A number may also contain the characters A\-F, with the values 10\-15. +.It Cm "+ - / * % ~ ^" +The +top two values on the stack are added +(+), +subtracted +(\-), +multiplied (*), +divided (/), +remaindered (%), +divided and remaindered (~), +or exponentiated (^). +The two entries are popped off the stack; +the result is pushed on the stack in their place. +Any fractional part of an exponent is ignored. +.Pp +For addition and subtraction, the scale of the result is the maximum +of scales of the operands. +For division the scale of the result is defined +by the scale set by the +.Ic k +operation. +For multiplication, the scale is defined by the expression +.Sy min(a+b,max(a,b,scale)) , +where +.Sy a +and +.Sy b +are the scales of the operands, and +.Sy scale +is the scale defined by the +.Ic k +operation. +For exponentiation with a non-negative exponent, the scale of the result is +.Sy min(a*b,max(scale,a)) , +where +.Sy a +is the scale of the base, and +.Sy b +is the +.Em value +of the exponent. +If the exponent is negative, the scale of the result is the scale +defined by the +.Ic k +operation. +.Pp +In the case of the division and modulus operator (~), +the resultant quotient is pushed first followed by the remainder. +This is a shorthand for the sequence: +.Bd -literal -offset indent -compact +x y / x y % +.Ed +The division and modulus operator is a non-portable extension. +.It Ic a +Pop the top value from the stack. +If that value is a number, compute the integer part of the number modulo 256. +If the result is zero, push an empty string. +Otherwise push a one character string by interpreting the computed value +as an +.Tn ASCII +character. +.Pp +If the top value is a string, push a string containing the first character +of the original string. +If the original string is empty, an empty string is pushed back. +The +.Ic a +operator is a non-portable extension. +.It Ic c +All values on the stack are popped. +.It Ic d +The top value on the stack is duplicated. +.It Ic f +All values on the stack are printed, separated by newlines. +.It Ic G +The top two numbers are popped from the stack and compared. +A one is pushed if the top of the stack is equal to the second number +on the stack. +A zero is pushed otherwise. +This is a non-portable extension. +.It Ic I +Pushes the input base on the top of the stack. +.It Ic i +The top value on the stack is popped and used as the +base for further input. +The initial input base is 10. +.It Ic J +Pop the top value from the stack. +The recursion level is popped by that value and, following that, +the input is skipped until the first occurrence of the +.Ic M +operator. +The +.Ic J +operator is a non-portable extension, used by the +.Xr bc 1 +command. +.It Ic K +The current scale factor is pushed onto the stack. +.It Ic k +The top of the stack is popped, and that value is used as +a non-negative scale factor: +the appropriate number of places +are printed on output, +and maintained during multiplication, division, and exponentiation. +The interaction of scale factor, +input base, and output base will be reasonable if all are changed +together. +.It Ic L Ns Ar x +Register +.Ar x +is treated as a stack and its top value is popped onto the main stack. +.It Ic l Ns Ar x +The +value in register +.Ar x +is pushed on the stack. +The register +.Ar x +is not altered. +Initially, all registers contain the value zero. +.It Ic M +Mark used by the +.Ic J +operator. +The +.Ic M +operator is a non-portable extensions, used by the +.Xr bc 1 +command. +.It Ic N +The top of the stack is replaced by one if the top of the stack +is equal to zero. +If the top of the stack is unequal to zero, it is replaced by zero. +This is a non-portable extension. +.It Ic n +The top value on the stack is popped and printed without a newline. +This is a non-portable extension. +.It Ic O +Pushes the output base on the top of the stack. +.It Ic o +The top value on the stack is popped and used as the +base for further output. +The initial output base is 10. +.It Ic P +The top of the stack is popped. +If the top of the stack is a string, it is printed without a trailing newline. +If the top of the stack is a number, it is interpreted as a +base 256 number, and each digit of this base 256 number is printed as +an +.Tn ASCII +character, without a trailing newline. +.It Ic p +The top value on the stack is printed with a trailing newline. +The top value remains unchanged. +.It Ic Q +The top value on the stack is popped and the string execution level is popped +by that value. +.It Ic q +Exits the program. +If executing a string, the recursion level is +popped by two. +.It Ic R +The top of the stack is removed (popped). +This is a non-portable extension. +.It Ic r +The top two values on the stack are reversed (swapped). +This is a non-portable extension. +.It Ic S Ns Ar x +Register +.Ar x +is treated as a stack. +The top value of the main stack is popped and pushed on it. +.It Ic s Ns Ar x +The +top of the stack is popped and stored into +a register named +.Ar x . +.It Ic v +Replaces the top element on the stack by its square root. +The scale of the result is the maximum of the scale of the argument +and the current value of scale. +.It Ic X +Replaces the number on the top of the stack with its scale factor. +If the top of the stack is a string, replace it with the integer 0. +.It Ic x +Treats the top element of the stack as a character string +and executes it as a string of +.Nm +commands. +.It Ic Z +Replaces the number on the top of the stack with its length. +The length of a string is its number of characters. +The length of a number is its number of digits, not counting the minus sign +and decimal point. +.It Ic z +The stack level is pushed onto the stack. +.It Cm \&[ Ns ... Ns Cm \&] +Puts the bracketed +.Tn ASCII +string onto the top of the stack. +If the string includes brackets, these must be properly balanced. +The backslash character +.Pq Sq \e +may be used as an escape character, making it +possible to include unbalanced brackets in strings. +To include a backslash in a string, use a double backslash. +.It Xo +.Cm < Ns Va x +.Cm > Ns Va x +.Cm = Ns Va x +.Cm !< Ns Va x +.Cm !> Ns Va x +.Cm != Ns Va x +.Xc +The top two elements of the stack are popped and compared. +Register +.Ar x +is executed if they obey the stated +relation. +.It Xo +.Cm < Ns Va x Ns e Ns Va y +.Cm > Ns Va x Ns e Ns Va y +.Cm = Ns Va x Ns e Ns Va y +.Cm !< Ns Va x Ns e Ns Va y +.Cm !> Ns Va x Ns e Ns Va y +.Cm != Ns Va x Ns e Ns Va y +.Xc +These operations are variants of the comparison operations above. +The first register name is followed by the letter +.Sq e +and another register name. +Register +.Ar x +will be executed if the relation is true, and register +.Ar y +will be executed if the relation is false. +This is a non-portable extension. +.It Ic \&( +The top two numbers are popped from the stack and compared. +A one is pushed if the top of the stack is less than the second number +on the stack. +A zero is pushed otherwise. +This is a non-portable extension. +.It Ic { +The top two numbers are popped from the stack and compared. +A one is pushed if the top of stack is less than or equal to the +second number on the stack. +A zero is pushed otherwise. +This is a non-portable extension. +.It Ic \&! +Interprets the rest of the line as a +.Ux +command. +.It Ic \&? +A line of input is taken from the input source (usually the terminal) +and executed. +.It Ic \&: Ns Ar r +Pop two values from the stack. +The second value on the stack is stored into the array +.Ar r +indexed by the top of stack. +.It Ic \&; Ns Ar r +Pop a value from the stack. +The value is used as an index into register +.Ar r . +The value in this register is pushed onto the stack. +.Pp +Array elements initially have the value zero. +Each level of a stacked register has its own array associated with +it. +The command sequence +.Bd -literal -offset indent +[first] 0:a [dummy] Sa [second] 0:a 0;a p La 0;a p +.Ed +.Pp +will print +.Bd -literal -offset indent +second +first +.Ed +.Pp +since the string +.Ql second +is written in an array that is later popped, to reveal the array that +stored +.Ql first . +.It Ic # +Skip the rest of the line. +This is a non-portable extension. +.El +.Ss Registers +Registers have a single character name +.Ar x , +where +.Ar x +may be any character, including space, tab or any other special character. +If extended register mode is enabled using the +.Fl x +option and the register identifier +.Ar x +has the value 255, the next two characters are interpreted as a +two-byte register index. +The set of standard single character registers and the set of extended +registers do not overlap. +Extended register mode is a non-portable extension. +.Sh EXAMPLES +An example which prints the first ten values of +.Ic n! : +.Bd -literal -offset indent +[la1+dsa*pla10>y]sy +0sa1 +lyx +.Ed +.Pp +Independent of the current input base, the command +.Bd -literal -offset indent +Ai +.Ed +.Pp +will reset the input base to decimal 10. +.Sh DIAGNOSTICS +.Bl -diag +.It %c (0%o) is unimplemented +an undefined operation was called. +.It stack empty +for not enough elements on the stack to do what was asked. +.It stack register '%c' (0%o) is empty +for an +.Ar L +operation from a stack register that is empty. +.It Runtime warning: non-zero scale in exponent +for a fractional part of an exponent that is being ignored. +.It divide by zero +for trying to divide by zero. +.It remainder by zero +for trying to take a remainder by zero. +.It square root of negative number +for trying to take the square root of a negative number. +.It index too big +for an array index that is larger than 2048. +.It negative index +for a negative array index. +.It "input base must be a number between 2 and 16" +for trying to set an illegal input base. +.It output base must be a number greater than 1 +for trying to set an illegal output base. +.It scale must be a nonnegative number +for trying to set a negative or zero scale. +.It scale too large +for trying to set a scale that is too large. +A scale must be representable as a 32-bit unsigned number. +.It Q command argument exceeded string execution depth +for trying to pop the recursion level more than the current +recursion level. +.It Q command requires a number >= 1 +for trying to pop an illegal number of recursion levels. +.It recursion too deep +for too many levels of nested execution. +.Pp +The recursion level is increased by one if the +.Ar x +or +.Ar ?\& +operation or one of the compare operations resulting in the execution +of register is executed. +As an exception, the recursion level is not increased if the operation +is executed as the last command of a string. +For example, the commands +.Bd -literal -offset indent +[lax]sa +1 lax +.Ed +.Pp +will execute an endless loop, while the commands +.Bd -literal -offset indent +[laxp]sa +1 lax +.Ed +.Pp +will terminate because of a too deep recursion level. +.It J command argument exceeded string execution depth +for trying to pop the recursion level more than the current +recursion level. +.It mark not found +for a failed scan for an occurrence of the +.Ic M +operator. +.El +.Sh SEE ALSO +.Xr bc 1 +.Sh STANDARDS +The arithmetic operations of the +.Nm +utility are expected to conform to the definition listed in the +.Xr bc 1 +section of the +.St -p1003.2 +specification. +.Sh HISTORY +The +.Nm +command first appeared in +.At v6 . +A complete rewrite of the +.Nm +command using the +.Xr bn 3 +big number routines first appeared in +.Ox 3.5 . +.Sh AUTHORS +.An -nosplit +The original version of the +.Nm +command was written by +.An Robert Morris +and +.An Lorinda Cherry . +The current version of the +.Nm +utility was written by +.An Otto Moerbeek . diff --git a/dc/dc.c b/dc/dc.c @@ -0,0 +1,111 @@ +/* $OpenBSD: dc.c,v 1.12 2014/05/20 01:25:23 guenther Exp $ */ + +/* + * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net> + * + * 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/stat.h> +#include <err.h> +#include <errno.h> +#include <stdlib.h> +#include <string.h> +#include <unistd.h> + +#include "extern.h" + +static __dead void usage(void); + +extern char *__progname; + +static __dead void +usage(void) +{ + (void)fprintf(stderr, "usage: %s [-x] [-e expression] [file]\n", + __progname); + exit(1); +} + +int +main(int argc, char *argv[]) +{ + int ch; + bool extended_regs = false; + FILE *file; + struct source src; + char *buf, *p; + struct stat st; + + + if ((buf = strdup("")) == NULL) + err(1, NULL); + /* accept and ignore a single dash to be 4.4BSD dc(1) compatible */ + while ((ch = getopt(argc, argv, "e:x-")) != -1) { + switch (ch) { + case 'e': + p = buf; + if (asprintf(&buf, "%s %s", buf, optarg) == -1) + err(1, NULL); + free(p); + break; + case 'x': + extended_regs = true; + break; + case '-': + break; + default: + usage(); + } + } + argc -= optind; + argv += optind; + + init_bmachine(extended_regs); + (void)setlinebuf(stdout); + (void)setlinebuf(stderr); + + if (argc > 1) + usage(); + if (buf[0] != '\0') { + src_setstring(&src, buf); + reset_bmachine(&src); + eval(); + free(buf); + if (argc == 0) + return (0); + } + if (argc == 1) { + file = fopen(argv[0], "r"); + if (file == NULL) + err(1, "cannot open file %s", argv[0]); + if (fstat(fileno(file), &st) == -1) + err(1, "%s", argv[0]); + if (S_ISDIR(st.st_mode)) + errc(1, EISDIR, "%s", argv[0]); + src_setstream(&src, file); + reset_bmachine(&src); + eval(); + (void)fclose(file); + /* + * BSD and Solaris dc(1) continue with stdin after processing + * the file given as the argument. We follow GNU dc(1). + */ + return (0); + } + src_setstream(&src, stdin); + reset_bmachine(&src); + eval(); + + return (0); +} diff --git a/dc/extern.h b/dc/extern.h @@ -0,0 +1,62 @@ +/* $OpenBSD: extern.h,v 1.3 2006/01/16 08:09:25 otto Exp $ */ + +/* + * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net> + * + * 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 <stdbool.h> +#include "bcode.h" + + +/* inout.c */ +void src_setstream(struct source *, FILE *); +void src_setstring(struct source *, char *); +struct number *readnumber(struct source *, u_int); +void printnumber(FILE *, const struct number *, u_int); +char *read_string(struct source *); +void print_value(FILE *, const struct value *, const char *, u_int); +void print_ascii(FILE *, const struct number *); + +/* mem.c */ +struct number *new_number(void); +void free_number(struct number *); +struct number *dup_number(const struct number *); +void *bmalloc(size_t); +void *brealloc(void *, size_t); +char *bstrdup(const char *p); +void bn_check(int); +void bn_checkp(const void *); + +/* stack.c */ +void stack_init(struct stack *); +void stack_free_value(struct value *); +struct value *stack_dup_value(const struct value *, struct value *); +void stack_swap(struct stack *); +size_t stack_size(const struct stack *); +void stack_dup(struct stack *); +void stack_pushnumber(struct stack *, struct number *); +void stack_pushstring(struct stack *stack, char *); +void stack_push(struct stack *, struct value *); +void stack_set_tos(struct stack *, struct value *); +struct value *stack_tos(const struct stack *); +struct value *stack_pop(struct stack *); +struct number *stack_popnumber(struct stack *); +char * stack_popstring(struct stack *); +void stack_clear(struct stack *); +void stack_print(FILE *, const struct stack *, const char *, + u_int base); +void frame_assign(struct stack *, size_t, const struct value *); +struct value * frame_retrieve(const struct stack *, size_t); +/* void frame_free(struct stack *); */ diff --git a/dc/inout.c b/dc/inout.c @@ -0,0 +1,412 @@ +/* $OpenBSD: inout.c,v 1.17 2012/11/07 11:06:14 otto Exp $ */ + +/* + * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net> + * + * 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 <ssl/ssl.h> +#include <ctype.h> +#include <err.h> +#include <string.h> + +#include "extern.h" + +#define MAX_CHARS_PER_LINE 68 + +static int lastchar; +static int charcount; + +static int src_getcharstream(struct source *); +static void src_ungetcharstream(struct source *); +static char *src_getlinestream(struct source *); +static void src_freestream(struct source *); +static int src_getcharstring(struct source *); +static void src_ungetcharstring(struct source *); +static char *src_getlinestring(struct source *); +static void src_freestring(struct source *); +static void flushwrap(FILE *); +static void putcharwrap(FILE *, int); +static void printwrap(FILE *, const char *); +static char *get_digit(u_long, int, u_int); + +static struct vtable stream_vtable = { + src_getcharstream, + src_ungetcharstream, + src_getlinestream, + src_freestream +}; + +static struct vtable string_vtable = { + src_getcharstring, + src_ungetcharstring, + src_getlinestring, + src_freestring +}; + +void +src_setstream(struct source *src, FILE *stream) +{ + src->u.stream = stream; + src->vtable = &stream_vtable; +} + +void +src_setstring(struct source *src, char *p) +{ + src->u.string.buf = (u_char *)p; + src->u.string.pos = 0; + src->vtable = &string_vtable; +} + +static int +src_getcharstream(struct source *src) +{ + return src->lastchar = getc(src->u.stream); +} + +static void +src_ungetcharstream(struct source *src) +{ + (void)ungetc(src->lastchar, src->u.stream); +} + +/* ARGSUSED */ +static void +src_freestream(struct source *src) +{ +} + +static char * +src_getlinestream(struct source *src) +{ + char buf[BUFSIZ]; + + if (fgets(buf, BUFSIZ, src->u.stream) == NULL) + return bstrdup(""); + return bstrdup(buf); +} + +static int +src_getcharstring(struct source *src) +{ + src->lastchar = src->u.string.buf[src->u.string.pos]; + if (src->lastchar == '\0') + return EOF; + else { + src->u.string.pos++; + return src->lastchar; + } +} + +static void +src_ungetcharstring(struct source *src) +{ + if (src->u.string.pos > 0) { + if (src->lastchar != '\0') + --src->u.string.pos; + } +} + +static char * +src_getlinestring(struct source *src) +{ + char buf[BUFSIZ]; + int ch, i; + + i = 0; + while (i < BUFSIZ-1) { + ch = src_getcharstring(src); + if (ch == EOF) + break; + buf[i++] = ch; + if (ch == '\n') + break; + } + buf[i] = '\0'; + return bstrdup(buf); +} + +static void +src_freestring(struct source *src) +{ + free(src->u.string.buf); +} + +static void +flushwrap(FILE *f) +{ + if (lastchar != -1) + (void)putc(lastchar, f); +} + +static void +putcharwrap(FILE *f, int ch) +{ + if (charcount >= MAX_CHARS_PER_LINE) { + charcount = 0; + (void)fputs("\\\n", f); + } + if (lastchar != -1) { + charcount++; + (void)putc(lastchar, f); + } + lastchar = ch; +} + +static void +printwrap(FILE *f, const char *p) +{ + char buf[12]; + char *q = buf; + + (void)strlcpy(buf, p, sizeof(buf)); + while (*q) + putcharwrap(f, *q++); +} + +struct number * +readnumber(struct source *src, u_int base) +{ + struct number *n; + int ch; + bool sign = false; + bool dot = false; + BN_ULONG v; + u_int i; + + n = new_number(); + bn_check(BN_zero(n->number)); + + while ((ch = (*src->vtable->readchar)(src)) != EOF) { + + if ('0' <= ch && ch <= '9') + v = ch - '0'; + else if ('A' <= ch && ch <= 'F') + v = ch - 'A' + 10; + else if (ch == '_') { + sign = true; + continue; + } else if (ch == '.') { + if (dot) + break; + dot = true; + continue; + } else { + (*src->vtable->unreadchar)(src); + break; + } + if (dot) + n->scale++; + + bn_check(BN_mul_word(n->number, base)); + +#if 0 + /* work around a bug in BN_add_word: 0 += 0 is buggy.... */ + if (v > 0) +#endif + bn_check(BN_add_word(n->number, v)); + } + if (base != 10) { + scale_number(n->number, n->scale); + for (i = 0; i < n->scale; i++) + (void)BN_div_word(n->number, base); + } + if (sign) + negate(n); + return n; +} + +char * +read_string(struct source *src) +{ + int count, i, sz, new_sz, ch; + char *p; + bool escape; + + escape = false; + count = 1; + i = 0; + sz = 15; + p = bmalloc(sz + 1); + + while ((ch = (*src->vtable->readchar)(src)) != EOF) { + if (!escape) { + if (ch == '[') + count++; + else if (ch == ']') + count--; + if (count == 0) + break; + } + if (ch == '\\' && !escape) + escape = true; + else { + escape = false; + if (i == sz) { + new_sz = sz * 2; + p = brealloc(p, new_sz + 1); + sz = new_sz; + } + p[i++] = ch; + } + } + p[i] = '\0'; + return p; +} + +static char * +get_digit(u_long num, int digits, u_int base) +{ + char *p; + + if (base <= 16) { + p = bmalloc(2); + p[0] = num >= 10 ? num + 'A' - 10 : num + '0'; + p[1] = '\0'; + } else { + if (asprintf(&p, "%0*lu", digits, num) == -1) + err(1, NULL); + } + return p; +} + +void +printnumber(FILE *f, const struct number *b, u_int base) +{ + struct number *int_part, *fract_part; + int digits; + char buf[11]; + size_t sz; + int i; + struct stack stack; + char *p; + + charcount = 0; + lastchar = -1; + if (BN_is_zero(b->number)) + putcharwrap(f, '0'); + + int_part = new_number(); + fract_part = new_number(); + fract_part->scale = b->scale; + + if (base <= 16) + digits = 1; + else { + digits = snprintf(buf, sizeof(buf), "%u", base-1); + } + split_number(b, int_part->number, fract_part->number); + + i = 0; + stack_init(&stack); + while (!BN_is_zero(int_part->number)) { + BN_ULONG rem = BN_div_word(int_part->number, base); + stack_pushstring(&stack, get_digit(rem, digits, base)); + i++; + } + sz = i; + if (BN_is_negative(b->number)) + putcharwrap(f, '-'); + for (i = 0; i < sz; i++) { + p = stack_popstring(&stack); + if (base > 16) + putcharwrap(f, ' '); + printwrap(f, p); + free(p); + } + stack_clear(&stack); + if (b->scale > 0) { + struct number *num_base; + BIGNUM mult, stop; + + putcharwrap(f, '.'); + num_base = new_number(); + bn_check(BN_set_word(num_base->number, base)); + BN_init(&mult); + bn_check(BN_one(&mult)); + BN_init(&stop); + bn_check(BN_one(&stop)); + scale_number(&stop, b->scale); + + i = 0; + while (BN_cmp(&mult, &stop) < 0) { + u_long rem; + + if (i && base > 16) + putcharwrap(f, ' '); + i = 1; + + bmul_number(fract_part, fract_part, num_base, + bmachine_scale()); + split_number(fract_part, int_part->number, NULL); + rem = BN_get_word(int_part->number); + p = get_digit(rem, digits, base); + int_part->scale = 0; + normalize(int_part, fract_part->scale); + bn_check(BN_sub(fract_part->number, fract_part->number, + int_part->number)); + printwrap(f, p); + free(p); + bn_check(BN_mul_word(&mult, base)); + } + free_number(num_base); + BN_free(&mult); + BN_free(&stop); + } + flushwrap(f); + free_number(int_part); + free_number(fract_part); +} + +void +print_value(FILE *f, const struct value *value, const char *prefix, u_int base) +{ + (void)fputs(prefix, f); + switch (value->type) { + case BCODE_NONE: + if (value->array != NULL) + (void)fputs("<array>", f); + break; + case BCODE_NUMBER: + printnumber(f, value->u.num, base); + break; + case BCODE_STRING: + (void)fputs(value->u.string, f); + break; + } +} + +void +print_ascii(FILE *f, const struct number *n) +{ + BIGNUM *v; + int numbits, i, ch; + + v = BN_dup(n->number); + bn_checkp(v); + + if (BN_is_negative(v)) + BN_set_negative(v, 0); + + numbits = BN_num_bytes(v) * 8; + while (numbits > 0) { + ch = 0; + for (i = 0; i < 8; i++) + ch |= BN_is_bit_set(v, numbits-i-1) << (7 - i); + (void)putc(ch, f); + numbits -= 8; + } + BN_free(v); +} diff --git a/dc/mem.c b/dc/mem.c @@ -0,0 +1,104 @@ +/* $OpenBSD: mem.c,v 1.5 2009/10/27 23:59:37 deraadt Exp $ */ + +/* + * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net> + * + * 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 <ssl/err.h> + +#include <err.h> +#include <stdlib.h> +#include <string.h> + +#include "extern.h" + +struct number * +new_number(void) +{ + struct number *n; + + n = bmalloc(sizeof(*n)); + n->scale = 0; + n->number = BN_new(); + if (n->number == NULL) + err(1, NULL); + return n; +} + +void +free_number(struct number *n) +{ + BN_free(n->number); + free(n); +} + +struct number * +dup_number(const struct number *a) +{ + struct number *n; + + n = bmalloc(sizeof(*n)); + n->scale = a->scale; + n->number = BN_dup(a->number); + bn_checkp(n->number); + return n; +} + +void * +bmalloc(size_t sz) +{ + void *p; + + p = malloc(sz); + if (p == NULL) + err(1, NULL); + return p; +} + +void * +brealloc(void *p, size_t sz) +{ + void *q; + + q = realloc(p, sz); + if (q == NULL) + err(1, NULL); + return q; +} + +char * +bstrdup(const char *p) +{ + char *q; + + q = strdup(p); + if (q == NULL) + err(1, NULL); + return q; +} + +void +bn_check(int x) \ +{ + if (x == 0) + err(1, "big number failure %lx", ERR_get_error()); +} + +void +bn_checkp(const void *p) \ +{ + if (p == NULL) + err(1, "allocation failure %lx", ERR_get_error()); +} diff --git a/dc/stack.c b/dc/stack.c @@ -0,0 +1,360 @@ +/* $OpenBSD: stack.c,v 1.11 2009/10/27 23:59:37 deraadt Exp $ */ + +/* + * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net> + * + * 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 <err.h> +#include <stdlib.h> +#include <string.h> + +#include "extern.h" + +static __inline bool stack_empty(const struct stack *); +static void stack_grow(struct stack *); +static struct array *array_new(void); +static __inline void array_free(struct array *); +static struct array * array_dup(const struct array *); +static __inline void array_grow(struct array *, size_t); +static __inline void array_assign(struct array *, size_t, const struct value *); +static __inline struct value *array_retrieve(const struct array *, size_t); + +void +stack_init(struct stack *stack) +{ + stack->size = 0; + stack->sp = -1; + stack->stack = NULL; +} + +static __inline bool +stack_empty(const struct stack *stack) +{ + bool empty = stack->sp == -1; + if (empty) + warnx("stack empty"); + return empty; +} + +/* Clear number or string, but leave value itself */ +void +stack_free_value(struct value *v) +{ + switch (v->type) { + case BCODE_NONE: + break; + case BCODE_NUMBER: + free_number(v->u.num); + break; + case BCODE_STRING: + free(v->u.string); + break; + } + if (v->array != NULL) { + array_free(v->array); + v->array = NULL; + } +} + +/* Copy number or string content into already allocated target */ +struct value * +stack_dup_value(const struct value *a, struct value *copy) +{ + copy->type = a->type; + + switch (a->type) { + case BCODE_NONE: + break; + case BCODE_NUMBER: + copy->u.num = dup_number(a->u.num); + break; + case BCODE_STRING: + copy->u.string = strdup(a->u.string); + if (copy->u.string == NULL) + err(1, NULL); + break; + } + + copy->array = a->array == NULL ? NULL : array_dup(a->array); + + return copy; +} + +size_t +stack_size(const struct stack *stack) +{ + return stack->sp + 1; +} + +void +stack_dup(struct stack *stack) +{ + struct value *value; + struct value copy; + + value = stack_tos(stack); + if (value == NULL) { + warnx("stack empty"); + return; + } + stack_push(stack, stack_dup_value(value, &copy)); +} + +void +stack_swap(struct stack *stack) +{ + struct value copy; + + if (stack->sp < 1) { + warnx("stack empty"); + return; + } + copy = stack->stack[stack->sp]; + stack->stack[stack->sp] = stack->stack[stack->sp-1]; + stack->stack[stack->sp-1] = copy; +} + +static void +stack_grow(struct stack *stack) +{ + size_t new_size, i; + + if (++stack->sp == stack->size) { + new_size = stack->size * 2 + 1; + stack->stack = brealloc(stack->stack, + new_size * sizeof(*stack->stack)); + for (i = stack->size; i < new_size; i++) + stack->stack[i].array = NULL; + stack->size = new_size; + } +} + +void +stack_pushnumber(struct stack *stack, struct number *b) +{ + stack_grow(stack); + stack->stack[stack->sp].type = BCODE_NUMBER; + stack->stack[stack->sp].u.num = b; +} + +void +stack_pushstring(struct stack *stack, char *string) +{ + stack_grow(stack); + stack->stack[stack->sp].type = BCODE_STRING; + stack->stack[stack->sp].u.string = string; +} + +void +stack_push(struct stack *stack, struct value *v) +{ + switch (v->type) { + case BCODE_NONE: + stack_grow(stack); + stack->stack[stack->sp].type = BCODE_NONE; + break; + case BCODE_NUMBER: + stack_pushnumber(stack, v->u.num); + break; + case BCODE_STRING: + stack_pushstring(stack, v->u.string); + break; + } + stack->stack[stack->sp].array = v->array == NULL ? + NULL : array_dup(v->array); +} + +struct value * +stack_tos(const struct stack *stack) +{ + if (stack->sp == -1) + return NULL; + return &stack->stack[stack->sp]; +} + +void +stack_set_tos(struct stack *stack, struct value *v) +{ + if (stack->sp == -1) + stack_push(stack, v); + else { + stack_free_value(&stack->stack[stack->sp]); + stack->stack[stack->sp] = *v; + stack->stack[stack->sp].array = v->array == NULL ? + NULL : array_dup(v->array); + } +} + +struct value * +stack_pop(struct stack *stack) +{ + if (stack_empty(stack)) + return NULL; + return &stack->stack[stack->sp--]; +} + +struct number * +stack_popnumber(struct stack *stack) +{ + if (stack_empty(stack)) + return NULL; + if (stack->stack[stack->sp].array != NULL) { + array_free(stack->stack[stack->sp].array); + stack->stack[stack->sp].array = NULL; + } + if (stack->stack[stack->sp].type != BCODE_NUMBER) { + warnx("not a number"); /* XXX remove */ + return NULL; + } + return stack->stack[stack->sp--].u.num; +} + +char * +stack_popstring(struct stack *stack) +{ + if (stack_empty(stack)) + return NULL; + if (stack->stack[stack->sp].array != NULL) { + array_free(stack->stack[stack->sp].array); + stack->stack[stack->sp].array = NULL; + } + if (stack->stack[stack->sp].type != BCODE_STRING) { + warnx("not a string"); /* XXX remove */ + return NULL; + } + return stack->stack[stack->sp--].u.string; +} + +void +stack_clear(struct stack *stack) +{ + while (stack->sp >= 0) { + stack_free_value(&stack->stack[stack->sp--]); + } + free(stack->stack); + stack_init(stack); +} + +void +stack_print(FILE *f, const struct stack *stack, const char *prefix, u_int base) +{ + ssize_t i; + + for (i = stack->sp; i >= 0; i--) { + print_value(f, &stack->stack[i], prefix, base); + (void)putc('\n', f); + } +} + + +static struct array * +array_new(void) +{ + struct array *a; + + a = bmalloc(sizeof(*a)); + a->data = NULL; + a->size = 0; + return a; +} + +static __inline void +array_free(struct array *a) +{ + size_t i; + + if (a == NULL) + return; + for (i = 0; i < a->size; i++) + stack_free_value(&a->data[i]); + free(a->data); + free(a); +} + +static struct array * +array_dup(const struct array *a) +{ + struct array *n; + size_t i; + + if (a == NULL) + return NULL; + n = array_new(); + array_grow(n, a->size); + for (i = 0; i < a->size; i++) + (void)stack_dup_value(&a->data[i], &n->data[i]); + return n; +} + +static __inline void +array_grow(struct array *array, size_t newsize) +{ + size_t i; + + array->data = brealloc(array->data, newsize * sizeof(*array->data)); + for (i = array->size; i < newsize; i++) { + array->data[i].type = BCODE_NONE; + array->data[i].array = NULL; + } + array->size = newsize; +} + +static __inline void +array_assign(struct array *array, size_t index, const struct value *v) +{ + if (index >= array->size) + array_grow(array, index+1); + stack_free_value(&array->data[index]); + array->data[index] = *v; +} + +static __inline struct value * +array_retrieve(const struct array *array, size_t index) +{ + if (index >= array->size) + return NULL; + return &array->data[index]; +} + +void +frame_assign(struct stack *stack, size_t index, const struct value *v) +{ + struct array *a; + struct value n; + + if (stack->sp == -1) { + n.type = BCODE_NONE; + n.array = NULL; + stack_push(stack, &n); + } + + a = stack->stack[stack->sp].array; + if (a == NULL) + a = stack->stack[stack->sp].array = array_new(); + array_assign(a, index, v); +} + +struct value * +frame_retrieve(const struct stack *stack, size_t index) +{ + struct array *a; + + if (stack->sp == -1) + return NULL; + a = stack->stack[stack->sp].array; + if (a == NULL) + a = stack->stack[stack->sp].array = array_new(); + return array_retrieve(a, index); +}