2 * $OpenBSD: bcode.c,v 1.45 2012/11/07 11:06:14 otto Exp $
3 * $DragonFly: src/usr.bin/dc/bcode.c,v 1.3 2008/09/14 21:08:29 swildner Exp $
7 * Copyright (c) 2003, Otto Moerbeek <otto@drijf.net>
9 * Permission to use, copy, modify, and distribute this software for any
10 * purpose with or without fee is hereby granted, provided that the above
11 * copyright notice and this permission notice appear in all copies.
13 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
14 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
15 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
16 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
17 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
18 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
19 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
22 #include <openssl/ssl.h>
32 /* #define DEBUGGING */
34 #define MAX_ARRAY_INDEX 2048
35 #define READSTACK_SIZE 8
37 #define NO_ELSE -2 /* -1 is EOF */
38 #define REG_ARRAY_SIZE_SMALL (UCHAR_MAX + 1)
39 #define REG_ARRAY_SIZE_BIG (UCHAR_MAX + 1 + USHRT_MAX + 1)
48 size_t reg_array_size;
50 volatile sig_atomic_t interrupted;
51 struct source *readstack;
55 static struct bmachine bmachine;
56 static void sighandler(int);
58 static __inline int readch(void);
59 static __inline void unreadch(void);
60 static __inline char *readline(void);
61 static __inline void src_free(void);
63 static __inline u_int max(u_int, u_int);
64 static u_long get_ulong(struct number *);
66 static __inline void push_number(struct number *);
67 static __inline void push_string(char *);
68 static __inline void push(struct value *);
69 static __inline struct value *tos(void);
70 static __inline struct number *pop_number(void);
71 static __inline char *pop_string(void);
72 static __inline void clear_stack(void);
73 static __inline void print_tos(void);
74 static void pop_print(void);
75 static void pop_printn(void);
76 static __inline void print_stack(void);
77 static __inline void dup(void);
78 static void swap(void);
79 static void drop(void);
81 static void get_scale(void);
82 static void set_scale(void);
83 static void get_obase(void);
84 static void set_obase(void);
85 static void get_ibase(void);
86 static void set_ibase(void);
87 static void stackdepth(void);
88 static void push_scale(void);
89 static u_int count_digits(const struct number *);
90 static void num_digits(void);
91 static void to_ascii(void);
92 static void push_line(void);
93 static void comment(void);
94 static void bexec(char *);
95 static void badd(void);
96 static void bsub(void);
97 static void bmul(void);
98 static void bdiv(void);
99 static void bmod(void);
100 static void bdivmod(void);
101 static void bexp(void);
102 static bool bsqrt_stop(const BIGNUM *, const BIGNUM *, u_int *);
103 static void bsqrt(void);
104 static void not(void);
105 static void equal_numbers(void);
106 static void less_numbers(void);
107 static void lesseq_numbers(void);
108 static void equal(void);
109 static void not_equal(void);
110 static void less(void);
111 static void not_less(void);
112 static void greater(void);
113 static void not_greater(void);
114 static void not_compare(void);
115 static bool compare_numbers(enum bcode_compare, struct number *,
117 static void compare(enum bcode_compare);
118 static int readreg(void);
119 static void load(void);
120 static void store(void);
121 static void load_stack(void);
122 static void store_stack(void);
123 static void load_array(void);
124 static void store_array(void);
125 static void nop(void);
126 static void quit(void);
127 static void quitN(void);
128 static void skipN(void);
129 static void skip_until_mark(void);
130 static void parse_number(void);
131 static void unknown(void);
132 static void eval_string(char *);
133 static void eval_line(void);
134 static void eval_tos(void);
137 typedef void (*opcode_function)(void);
144 static opcode_function jump_table[UCHAR_MAX];
146 static const struct jump_entry jump_table_data[] = {
148 { '!', not_compare },
151 { '(', less_numbers },
155 { '.', parse_number },
157 { '0', parse_number },
158 { '1', parse_number },
159 { '2', parse_number },
160 { '3', parse_number },
161 { '4', parse_number },
162 { '5', parse_number },
163 { '6', parse_number },
164 { '7', parse_number },
165 { '8', parse_number },
166 { '9', parse_number },
167 { ':', store_array },
173 { 'A', parse_number },
174 { 'B', parse_number },
175 { 'C', parse_number },
176 { 'D', parse_number },
177 { 'E', parse_number },
178 { 'F', parse_number },
179 { 'G', equal_numbers },
190 { 'S', store_stack },
199 { '_', parse_number },
201 { 'c', clear_stack },
203 { 'f', print_stack },
216 { '{', lesseq_numbers },
220 #define JUMP_TABLE_DATA_SIZE \
221 (sizeof(jump_table_data)/sizeof(jump_table_data[0]))
224 sighandler(int ignored __unused)
226 bmachine.interrupted = true;
230 init_bmachine(bool extended_registers)
234 bmachine.extended_regs = extended_registers;
235 bmachine.reg_array_size = bmachine.extended_regs ?
236 REG_ARRAY_SIZE_BIG : REG_ARRAY_SIZE_SMALL;
238 bmachine.reg = calloc(bmachine.reg_array_size,
239 sizeof(bmachine.reg[0]));
240 if (bmachine.reg == NULL)
243 for (i = 0; i < UCHAR_MAX; i++)
244 jump_table[i] = unknown;
245 for (i = 0; i < JUMP_TABLE_DATA_SIZE; i++)
246 jump_table[jump_table_data[i].ch] = jump_table_data[i].f;
248 stack_init(&bmachine.stack);
250 for (i = 0; i < bmachine.reg_array_size; i++)
251 stack_init(&bmachine.reg[i]);
253 bmachine.readstack_sz = READSTACK_SIZE;
254 bmachine.readstack = calloc(sizeof(struct source),
255 bmachine.readstack_sz);
256 if (bmachine.readstack == NULL)
258 bmachine.obase = bmachine.ibase = 10;
259 signal(SIGINT, sighandler);
265 return bmachine.scale;
268 /* Reset the things needed before processing a (new) file */
270 reset_bmachine(struct source *src)
273 bmachine.readstack[0] = *src;
279 struct source *src = &bmachine.readstack[bmachine.readsp];
281 return src->vtable->readchar(src);
287 struct source *src = &bmachine.readstack[bmachine.readsp];
289 src->vtable->unreadchar(src);
292 static __inline char *
295 struct source *src = &bmachine.readstack[bmachine.readsp];
297 return src->vtable->readline(src);
303 struct source *src = &bmachine.readstack[bmachine.readsp];
305 src->vtable->free(src);
310 pn(const char *str, const struct number *n)
312 char *p = BN_bn2dec(n->number);
314 err(1, "BN_bn2dec failed");
316 fprintf(stderr, " %s (%u)\n" , p, n->scale);
321 pbn(const char *str, const BIGNUM *n)
323 char *p = BN_bn2dec(n);
325 err(1, "BN_bn2dec failed");
327 fprintf(stderr, " %s\n", p);
333 static __inline u_int
334 max(u_int a, u_int b)
336 return a > b ? a : b;
339 static unsigned long factors[] = {
340 0, 10, 100, 1000, 10000, 100000, 1000000, 10000000,
341 100000000, 1000000000
345 scale_number(BIGNUM *n, int s)
352 abs_scale = s > 0 ? s : -s;
354 if (abs_scale < sizeof(factors)/sizeof(factors[0])) {
356 bn_check(BN_mul_word(n, factors[abs_scale]));
358 BN_div_word(n, factors[abs_scale]);
370 bn_check(BN_set_word(a, 10));
371 bn_check(BN_set_word(p, abs_scale));
372 bn_check(BN_exp(a, a, p, ctx));
374 bn_check(BN_mul(n, n, a, ctx));
376 bn_check(BN_div(n, NULL, n, a, ctx));
384 split_number(const struct number *n, BIGNUM *i, BIGNUM *f)
388 bn_checkp(BN_copy(i, n->number));
390 if (n->scale == 0 && f != NULL)
391 bn_check(BN_zero(f));
392 else if (n->scale < sizeof(factors)/sizeof(factors[0])) {
393 rem = BN_div_word(i, factors[n->scale]);
395 bn_check(BN_set_word(f, rem));
407 bn_check(BN_set_word(a, 10));
408 bn_check(BN_set_word(p, n->scale));
409 bn_check(BN_exp(a, a, p, ctx));
410 bn_check(BN_div(i, f, n->number, a, ctx));
418 normalize(struct number *n, u_int s)
420 scale_number(n->number, s - n->scale);
425 get_ulong(struct number *n)
428 return BN_get_word(n->number);
432 negate(struct number *n)
434 BN_set_negative(n->number, !BN_is_negative(n->number));
438 push_number(struct number *n)
440 stack_pushnumber(&bmachine.stack, n);
444 push_string(char *string)
446 stack_pushstring(&bmachine.stack, string);
450 push(struct value *v)
452 stack_push(&bmachine.stack, v);
455 static __inline struct value *
458 return stack_tos(&bmachine.stack);
461 static __inline struct value *
464 return stack_pop(&bmachine.stack);
467 static __inline struct number *
470 return stack_popnumber(&bmachine.stack);
473 static __inline char *
476 return stack_popstring(&bmachine.stack);
482 stack_clear(&bmachine.stack);
488 stack_print(stdout, &bmachine.stack, "", bmachine.obase);
494 struct value *value = tos();
496 print_value(stdout, value, "", bmachine.obase);
500 warnx("stack empty");
506 struct value *value = pop();
509 switch (value->type) {
513 normalize(value->u.num, 0);
514 print_ascii(stdout, value->u.num);
518 fputs(value->u.string, stdout);
522 stack_free_value(value);
529 struct value *value = pop();
532 print_value(stdout, value, "", bmachine.obase);
534 stack_free_value(value);
541 stack_dup(&bmachine.stack);
547 stack_swap(&bmachine.stack);
553 struct value *v = pop();
564 bn_check(BN_set_word(n->number, bmachine.scale));
576 if (BN_is_negative(n->number))
577 warnx("scale must be a nonnegative number");
579 scale = get_ulong(n);
580 if (scale != BN_MASK2 && scale <= UINT_MAX)
581 bmachine.scale = (u_int)scale;
583 warnx("scale too large");
595 bn_check(BN_set_word(n->number, bmachine.obase));
608 if (base != BN_MASK2 && base > 1 && base <= UINT_MAX)
609 bmachine.obase = (u_int)base;
611 warnx("output base must be a number greater than 1");
622 bn_check(BN_set_word(n->number, bmachine.ibase));
635 if (base != BN_MASK2 && 2 <= base && base <= 16)
636 bmachine.ibase = (u_int)base;
638 warnx("input base must be a number between 2 and 16 "
650 i = stack_size(&bmachine.stack);
652 bn_check(BN_set_word(n->number, i));
666 switch (value->type) {
670 scale = value->u.num->scale;
675 stack_free_value(value);
677 bn_check(BN_set_word(n->number, scale));
683 count_digits(const struct number *n)
685 struct number *int_part, *fract_part;
688 if (BN_is_zero(n->number))
689 return n->scale ? n->scale : 1;
691 int_part = new_number();
692 fract_part = new_number();
693 fract_part->scale = n->scale;
694 split_number(n, int_part->number, fract_part->number);
697 while (!BN_is_zero(int_part->number)) {
698 BN_div_word(int_part->number, 10);
701 free_number(int_part);
702 free_number(fract_part);
711 struct number *n = NULL;
715 switch (value->type) {
719 digits = count_digits(value->u.num);
721 bn_check(BN_set_word(n->number, digits));
724 digits = strlen(value->u.string);
726 bn_check(BN_set_word(n->number, digits));
729 stack_free_value(value);
744 switch (value->type) {
750 if (BN_num_bits(n->number) > 8)
751 bn_check(BN_mask_bits(n->number, 8));
752 str[0] = BN_get_word(n->number);
755 str[0] = value->u.string[0];
758 stack_free_value(value);
759 push_string(bstrdup(str));
769 if (index == 0xff && bmachine.extended_regs) {
772 if (ch1 == EOF || ch2 == EOF) {
773 warnx("unexpected eof");
776 index = (ch1 << 8) + ch2 + UCHAR_MAX + 1;
778 if (index < 0 || index >= bmachine.reg_array_size) {
779 warnx("internal error: reg num = %d", index);
789 struct value *v, copy;
794 v = stack_tos(&bmachine.reg[index]);
797 bn_check(BN_zero(n->number));
800 push(stack_dup_value(v, ©));
816 stack_set_tos(&bmachine.reg[index], val);
829 stack = &bmachine.reg[index];
831 if (stack_size(stack) > 0) {
832 value = stack_pop(stack);
837 warnx("stack register '%c' (0%o) is empty",
853 stack_push(&bmachine.reg[index], value);
861 struct number *inumber, *n;
864 struct value *v, copy;
868 inumber = pop_number();
871 index = get_ulong(inumber);
872 if (BN_is_negative(inumber->number))
873 warnx("negative index");
874 else if (index == BN_MASK2 || index > MAX_ARRAY_INDEX)
875 warnx("index too big");
877 stack = &bmachine.reg[reg];
878 v = frame_retrieve(stack, index);
879 if (v == NULL || v->type == BCODE_NONE ) {
881 bn_check(BN_zero(n->number));
885 push(stack_dup_value(v, ©));
887 free_number(inumber);
895 struct number *inumber;
902 inumber = pop_number();
907 free_number(inumber);
910 index = get_ulong(inumber);
911 if (BN_is_negative(inumber->number)) {
912 warnx("negative index");
913 stack_free_value(value);
914 } else if (index == BN_MASK2 || index > MAX_ARRAY_INDEX) {
915 warnx("index too big");
916 stack_free_value(value);
918 stack = &bmachine.reg[reg];
919 frame_assign(stack, index, value);
921 free_number(inumber);
928 push_string(read_string(&bmachine.readstack[bmachine.readsp]));
947 struct number *a, *b;
961 r->scale = max(a->scale, b->scale);
962 if (r->scale > a->scale)
963 normalize(a, r->scale);
964 else if (r->scale > b->scale)
965 normalize(b, r->scale);
966 bn_check(BN_add(r->number, a->number, b->number));
975 struct number *a, *b;
990 r->scale = max(a->scale, b->scale);
991 if (r->scale > a->scale)
992 normalize(a, r->scale);
993 else if (r->scale > b->scale)
994 normalize(b, r->scale);
995 bn_check(BN_sub(r->number, b->number, a->number));
1002 bmul_number(struct number *r, struct number *a, struct number *b, u_int scale)
1006 /* Create copies of the scales, since r might be equal to a or b */
1007 u_int ascale = a->scale;
1008 u_int bscale = b->scale;
1009 u_int rscale = ascale + bscale;
1013 bn_check(BN_mul(r->number, a->number, b->number, ctx));
1017 if (rscale > bmachine.scale && rscale > ascale && rscale > bscale)
1018 normalize(r, max(scale, max(ascale, bscale)));
1024 struct number *a, *b;
1038 bmul_number(r, a, b, bmachine.scale);
1048 struct number *a, *b;
1064 r->scale = bmachine.scale;
1065 scale = max(a->scale, b->scale);
1067 if (BN_is_zero(a->number))
1068 warnx("divide by zero");
1070 normalize(a, scale);
1071 normalize(b, scale + r->scale);
1075 bn_check(BN_div(r->number, NULL, b->number, a->number, ctx));
1086 struct number *a, *b;
1102 scale = max(a->scale, b->scale);
1103 r->scale = max(b->scale, a->scale + bmachine.scale);
1105 if (BN_is_zero(a->number))
1106 warnx("remainder by zero");
1108 normalize(a, scale);
1109 normalize(b, scale + bmachine.scale);
1113 bn_check(BN_mod(r->number, b->number, a->number, ctx));
1124 struct number *a, *b;
1125 struct number *rdiv, *rmod;
1139 rdiv = new_number();
1140 rmod = new_number();
1141 rdiv->scale = bmachine.scale;
1142 rmod->scale = max(b->scale, a->scale + bmachine.scale);
1143 scale = max(a->scale, b->scale);
1145 if (BN_is_zero(a->number))
1146 warnx("divide by zero");
1148 normalize(a, scale);
1149 normalize(b, scale + bmachine.scale);
1153 bn_check(BN_div(rdiv->number, rmod->number,
1154 b->number, a->number, ctx));
1166 struct number *a, *p;
1181 if (p->scale != 0) {
1187 split_number(p, i, f);
1189 warnx("Runtime warning: non-zero fractional part in exponent");
1196 if (BN_is_negative(p->number)) {
1199 rscale = bmachine.scale;
1201 /* Posix bc says min(a.scale * b, max(a.scale, scale) */
1205 b = BN_get_word(p->number);
1206 m = max(a->scale, bmachine.scale);
1207 rscale = a->scale * (u_int)b;
1208 if (rscale > m || (a->scale > 0 && (b == BN_MASK2 ||
1213 if (BN_is_zero(p->number)) {
1215 bn_check(BN_one(r->number));
1216 normalize(r, rscale);
1218 u_int ascale, mscale;
1221 while (!BN_is_bit_set(p->number, 0)) {
1223 bmul_number(a, a, a, ascale);
1224 bn_check(BN_rshift1(p->number, p->number));
1228 bn_check(BN_rshift1(p->number, p->number));
1231 while (!BN_is_zero(p->number)) {
1233 bmul_number(a, a, a, ascale);
1234 if (BN_is_bit_set(p->number, 0)) {
1236 bmul_number(r, r, a, mscale);
1238 bn_check(BN_rshift1(p->number, p->number));
1247 bn_check(BN_one(one));
1250 scale_number(one, r->scale + rscale);
1252 if (BN_is_zero(r->number))
1253 warnx("divide by zero");
1255 bn_check(BN_div(r->number, NULL, one,
1261 normalize(r, rscale);
1269 bsqrt_stop(const BIGNUM *x, const BIGNUM *y, u_int *onecount)
1276 bn_check(BN_sub(r, x, y));
1279 ret = BN_is_zero(r);
1281 return ret || *onecount > 1;
1290 u_int scale, onecount;
1298 if (BN_is_zero(n->number)) {
1301 } else if (BN_is_negative(n->number))
1302 warnx("square root of negative number");
1304 scale = max(bmachine.scale, n->scale);
1305 normalize(n, 2*scale);
1306 x = BN_dup(n->number);
1308 bn_check(BN_rshift(x, x, BN_num_bits(x)/2));
1314 bn_checkp(BN_copy(y, x));
1315 bn_check(BN_div(x, NULL, n->number, x, ctx));
1316 bn_check(BN_add(x, x, y));
1317 bn_check(BN_rshift1(x, x));
1318 if (bsqrt_stop(x, y, &onecount))
1321 r = bmalloc(sizeof(*r));
1342 bn_check(BN_set_word(a->number, BN_get_word(a->number) ? 0 : 1));
1349 compare(BCODE_EQUAL);
1355 struct number *a, *b, *r;
1367 bn_check(BN_set_word(r->number,
1368 compare_numbers(BCODE_EQUAL, a, b) ? 1 : 0));
1375 struct number *a, *b, *r;
1387 bn_check(BN_set_word(r->number,
1388 compare_numbers(BCODE_LESS, a, b) ? 1 : 0));
1393 lesseq_numbers(void)
1395 struct number *a, *b, *r;
1407 bn_check(BN_set_word(r->number,
1408 compare_numbers(BCODE_NOT_GREATER, a, b) ? 1 : 0));
1415 compare(BCODE_NOT_EQUAL);
1421 compare(BCODE_LESS);
1447 compare(BCODE_NOT_LESS);
1453 compare(BCODE_GREATER);
1459 compare(BCODE_NOT_GREATER);
1463 compare_numbers(enum bcode_compare type, struct number *a, struct number *b)
1468 scale = max(a->scale, b->scale);
1470 if (scale > a->scale)
1471 normalize(a, scale);
1472 else if (scale > b->scale)
1473 normalize(b, scale);
1475 cmp = BN_cmp(a->number, b->number);
1483 case BCODE_NOT_EQUAL:
1487 case BCODE_NOT_LESS:
1491 case BCODE_NOT_GREATER:
1498 compare(enum bcode_compare type)
1500 int index, elseindex;
1501 struct number *a, *b;
1505 elseindex = NO_ELSE;
1507 if (readch() == 'e')
1508 elseindex = readreg();
1521 ok = compare_numbers(type, a, b);
1523 if (!ok && elseindex != NO_ELSE)
1526 if (index >= 0 && (ok || (!ok && elseindex != NO_ELSE))) {
1527 v = stack_tos(&bmachine.reg[index]);
1529 warnx("register '%c' (0%o) is empty", index, index);
1533 warnx("register '%c' (0%o) is empty",
1537 warn("eval called with non-string argument");
1540 eval_string(bstrdup(v->u.string));
1556 if (bmachine.readsp < 2)
1575 if (i == BN_MASK2 || i == 0)
1576 warnx("Q command requires a number >= 1");
1577 else if (bmachine.readsp < i)
1578 warnx("Q command argument exceeded string execution depth");
1598 warnx("J command requires a number >= 0");
1599 else if (i > 0 && bmachine.readsp < i)
1600 warnx("J command argument exceeded string execution depth");
1611 skip_until_mark(void)
1621 errx(1, "mark not found");
1633 if (readch() == 'e')
1639 free(read_string(&bmachine.readstack[bmachine.readsp]));
1642 switch (ch = readch()) {
1647 if (readch() == 'e')
1667 push_number(readnumber(&bmachine.readstack[bmachine.readsp],
1674 int ch = bmachine.readstack[bmachine.readsp].lastchar;
1675 warnx("%c (0%o) is unimplemented", ch, ch);
1679 eval_string(char *p)
1683 if (bmachine.readsp > 0) {
1684 /* Check for tail call. Do not recurse in that case. */
1688 src_setstring(&bmachine.readstack[bmachine.readsp], p);
1693 if (bmachine.readsp == bmachine.readstack_sz - 1) {
1694 size_t newsz = bmachine.readstack_sz * 2;
1695 struct source *stack;
1696 stack = realloc(bmachine.readstack, newsz *
1697 sizeof(struct source));
1699 err(1, "recursion too deep");
1700 bmachine.readstack_sz = newsz;
1701 bmachine.readstack = stack;
1703 src_setstring(&bmachine.readstack[++bmachine.readsp], p);
1709 /* Always read from stdin */
1714 src_setstream(&in, stdin);
1715 p = (*in.vtable->readline)(&in);
1738 if (bmachine.readsp == 0)
1744 if (bmachine.interrupted) {
1745 if (bmachine.readsp > 0) {
1750 bmachine.interrupted = false;
1753 fprintf(stderr, "# %c\n", ch);
1754 stack_print(stderr, &bmachine.stack, "* ",
1756 fprintf(stderr, "%zd =>\n", bmachine.readsp);
1759 if (0 <= ch && ch < UCHAR_MAX)
1760 (*jump_table[ch])();
1762 warnx("internal error: opcode %d", ch);
1765 stack_print(stderr, &bmachine.stack, "* ",
1767 fprintf(stderr, "%zd ==\n", bmachine.readsp);