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