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