Annotation of src/usr.bin/dc/bcode.c, Revision 1.25
1.25 ! otto 1: /* $OpenBSD: bcode.c,v 1.24 2004/10/18 07:49:00 otto 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.25 ! otto 20: static const char rcsid[] = "$OpenBSD: bcode.c,v 1.24 2004/10/18 07:49:00 otto 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);
1.25 ! otto 104: static bool bsqrt_stop(const BIGNUM *, const BIGNUM *, u_int *);
1.1 otto 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
1.25 ! otto 1241: bsqrt_stop(const BIGNUM *x, const BIGNUM *y, u_int *onecount)
1.1 otto 1242: {
1243: BIGNUM *r;
1244: bool ret;
1245:
1246: r = BN_new();
1247: bn_checkp(r);
1248: bn_check(BN_sub(r, x, y));
1.25 ! otto 1249: if (BN_is_one(r))
! 1250: (*onecount)++;
! 1251: ret = BN_is_zero(r);
1.1 otto 1252: BN_free(r);
1.25 ! otto 1253: return ret || *onecount > 1;
1.1 otto 1254: }
1255:
1256: static void
1257: bsqrt(void)
1258: {
1259: struct number *n;
1260: struct number *r;
1261: BIGNUM *x, *y;
1.25 ! otto 1262: u_int scale, onecount;
1.1 otto 1263: BN_CTX *ctx;
1264:
1.25 ! otto 1265: onecount = 0;
1.1 otto 1266: n = pop_number();
1267: if (n == NULL) {
1268: return;
1269: }
1270: if (BN_is_zero(n->number)) {
1271: r = new_number();
1272: push_number(r);
1273: } else if (BN_cmp(n->number, &zero) < 0)
1274: warnx("square root of negative number");
1275: else {
1276: scale = max(bmachine.scale, n->scale);
1277: normalize(n, 2*scale);
1278: x = BN_dup(n->number);
1279: bn_checkp(x);
1280: bn_check(BN_rshift(x, x, BN_num_bits(x)/2));
1281: y = BN_new();
1282: bn_checkp(y);
1283: ctx = BN_CTX_new();
1284: bn_checkp(ctx);
1285: for (;;) {
1286: bn_checkp(BN_copy(y, x));
1287: bn_check(BN_div(x, NULL, n->number, x, ctx));
1288: bn_check(BN_add(x, x, y));
1289: bn_check(BN_rshift1(x, x));
1.25 ! otto 1290: if (bsqrt_stop(x, y, &onecount))
1.1 otto 1291: break;
1292: }
1293: r = bmalloc(sizeof(*r));
1294: r->scale = scale;
1295: r->number = y;
1296: BN_free(x);
1297: BN_CTX_free(ctx);
1298: push_number(r);
1299: }
1300:
1301: free_number(n);
1302: }
1303:
1304: static void
1.16 otto 1305: not(void)
1306: {
1307: struct number *a;
1308:
1309: a = pop_number();
1310: if (a == NULL) {
1311: return;
1312: }
1313: a->scale = 0;
1314: bn_check(BN_set_word(a->number, BN_get_word(a->number) ? 0 : 1));
1315: push_number(a);
1316: }
1317:
1318: static void
1.1 otto 1319: equal(void)
1320: {
1321: compare(BCODE_EQUAL);
1322: }
1323:
1324: static void
1.16 otto 1325: equal_numbers(void)
1326: {
1327: struct number *a, *b, *r;
1328:
1329: a = pop_number();
1330: if (a == NULL) {
1331: return;
1332: }
1333: b = pop_number();
1334: if (b == NULL) {
1335: push_number(a);
1336: return;
1337: }
1338: r = new_number();
1339: bn_check(BN_set_word(r->number,
1340: compare_numbers(BCODE_EQUAL, a, b) ? 1 : 0));
1341: push_number(r);
1342: }
1343:
1344: static void
1345: less_numbers(void)
1346: {
1347: struct number *a, *b, *r;
1348:
1349: a = pop_number();
1350: if (a == NULL) {
1351: return;
1352: }
1353: b = pop_number();
1354: if (b == NULL) {
1355: push_number(a);
1356: return;
1357: }
1358: r = new_number();
1359: bn_check(BN_set_word(r->number,
1360: compare_numbers(BCODE_LESS, a, b) ? 1 : 0));
1361: push_number(r);
1362: }
1363:
1364: static void
1365: lesseq_numbers(void)
1366: {
1367: struct number *a, *b, *r;
1368:
1369: a = pop_number();
1370: if (a == NULL) {
1371: return;
1372: }
1373: b = pop_number();
1374: if (b == NULL) {
1375: push_number(a);
1376: return;
1377: }
1378: r = new_number();
1379: bn_check(BN_set_word(r->number,
1380: compare_numbers(BCODE_NOT_GREATER, a, b) ? 1 : 0));
1381: push_number(r);
1382: }
1383:
1384: static void
1.1 otto 1385: not_equal(void)
1386: {
1387: compare(BCODE_NOT_EQUAL);
1388: }
1389:
1390: static void
1391: less(void)
1392: {
1393: compare(BCODE_LESS);
1394: }
1395:
1396: static void
1397: not_compare(void)
1398: {
1399: switch (readch()) {
1400: case '<':
1401: not_less();
1402: break;
1403: case '>':
1404: not_greater();
1405: break;
1406: case '=':
1407: not_equal();
1408: break;
1.2 deraadt 1409: default:
1.1 otto 1410: unreadch();
1411: bexec(readline());
1412: break;
1413: }
1414: }
1415:
1416: static void
1417: not_less(void)
1418: {
1419: compare(BCODE_NOT_LESS);
1420: }
1421:
1422: static void
1423: greater(void)
1424: {
1425: compare(BCODE_GREATER);
1426: }
1427:
1428: static void
1429: not_greater(void)
1430: {
1431: compare(BCODE_NOT_GREATER);
1432: }
1433:
1.16 otto 1434: static bool
1435: compare_numbers(enum bcode_compare type, struct number *a, struct number *b)
1436: {
1437: u_int scale;
1438: int cmp;
1439:
1440: scale = max(a->scale, b->scale);
1441:
1442: if (scale > a->scale)
1443: normalize(a, scale);
1444: else if (scale > scale)
1445: normalize(b, scale);
1446:
1447: cmp = BN_cmp(a->number, b->number);
1448:
1449: free_number(a);
1450: free_number(b);
1451:
1452: switch (type) {
1453: case BCODE_EQUAL:
1454: return cmp == 0;
1455: case BCODE_NOT_EQUAL:
1456: return cmp != 0;
1457: case BCODE_LESS:
1458: return cmp < 0;
1459: case BCODE_NOT_LESS:
1460: return cmp >= 0;
1461: case BCODE_GREATER:
1462: return cmp > 0;
1463: case BCODE_NOT_GREATER:
1464: return cmp <= 0;
1465: }
1466: return false;
1467: }
1468:
1.1 otto 1469: static void
1470: compare(enum bcode_compare type)
1471: {
1.11 otto 1472: int index, elseindex;
1.1 otto 1473: struct number *a, *b;
1474: bool ok;
1475: struct value *v;
1476:
1.11 otto 1477: elseindex = NO_ELSE;
1.18 otto 1478: index = readreg();
1.11 otto 1479: if (readch() == 'e')
1.18 otto 1480: elseindex = readreg();
1.11 otto 1481: else
1482: unreadch();
1.1 otto 1483:
1484: a = pop_number();
1.11 otto 1485: if (a == NULL)
1.1 otto 1486: return;
1487: b = pop_number();
1488: if (b == NULL) {
1489: push_number(a);
1490: return;
1491: }
1492:
1.16 otto 1493: ok = compare_numbers(type, a, b);
1.1 otto 1494:
1.11 otto 1495: if (!ok && elseindex != NO_ELSE)
1496: index = elseindex;
1497:
1.18 otto 1498: if (index >= 0 && (ok || (!ok && elseindex != NO_ELSE))) {
1.1 otto 1499: v = stack_tos(&bmachine.reg[index]);
1500: if (v == NULL)
1.11 otto 1501: warnx("register '%c' (0%o) is empty", index, index);
1.1 otto 1502: else {
1503: switch(v->type) {
1504: case BCODE_NONE:
1505: warnx("register '%c' (0%o) is empty",
1506: index, index);
1507: break;
1508: case BCODE_NUMBER:
1509: warn("eval called with non-string argument");
1510: break;
1511: case BCODE_STRING:
1512: eval_string(bstrdup(v->u.string));
1513: break;
1514: }
1515: }
1516: }
1517: }
1518:
1519:
1520: static void
1521: nop(void)
1522: {
1523: }
1524:
1.2 deraadt 1525: static void
1.1 otto 1526: quit(void)
1527: {
1.2 deraadt 1528: if (bmachine.readsp < 2)
1.1 otto 1529: exit(0);
1530: src_free();
1531: bmachine.readsp--;
1532: src_free();
1533: bmachine.readsp--;
1534: }
1535:
1536: static void
1537: quitN(void)
1538: {
1539: struct number *n;
1540: u_long i;
1541:
1542: n = pop_number();
1543: if (n == NULL)
1544: return;
1545: i = get_ulong(n);
1546: if (i == BN_MASK2 || i == 0)
1547: warnx("Q command requires a number >= 1");
1548: else if (bmachine.readsp < i)
1549: warnx("Q command argument exceeded string execution depth");
1550: else {
1551: while (i-- > 0) {
1552: src_free();
1553: bmachine.readsp--;
1554: }
1555: }
1556: }
1557:
1558: static void
1.9 otto 1559: skipN(void)
1560: {
1561: struct number *n;
1562: u_long i;
1563:
1564: n = pop_number();
1565: if (n == NULL)
1566: return;
1567: i = get_ulong(n);
1568: if (i == BN_MASK2)
1569: warnx("J command requires a number >= 0");
1570: else if (i > 0 && bmachine.readsp < i)
1571: warnx("J command argument exceeded string execution depth");
1572: else {
1573: while (i-- > 0) {
1574: src_free();
1575: bmachine.readsp--;
1576: }
1577: skip_until_mark();
1578: }
1579: }
1580:
1581: static void
1582: skip_until_mark(void)
1583: {
1584: int ch;
1585:
1586: for (;;) {
1587: ch = readch();
1588: switch (ch) {
1589: case 'M':
1590: return;
1591: case EOF:
1592: errx(1, "mark not found");
1593: return;
1594: case 'l':
1595: case 'L':
1596: case 's':
1597: case 'S':
1598: case ':':
1599: case ';':
1600: case '<':
1601: case '>':
1602: case '=':
1.18 otto 1603: readreg();
1.12 otto 1604: if (readch() == 'e')
1.18 otto 1605: readreg();
1.12 otto 1606: else
1607: unreadch();
1.9 otto 1608: break;
1609: case '[':
1610: free(read_string(&bmachine.readstack[bmachine.readsp]));
1611: break;
1612: case '!':
1613: switch (ch = readch()) {
1614: case '<':
1615: case '>':
1616: case '=':
1.18 otto 1617: readreg();
1.12 otto 1618: if (readch() == 'e')
1.18 otto 1619: readreg();
1.12 otto 1620: else
1621: unreadch();
1.9 otto 1622: break;
1623: default:
1624: free(readline());
1625: break;
1626: }
1627: break;
1628: default:
1629: break;
1630: }
1631: }
1632: }
1633:
1634: static void
1.1 otto 1635: parse_number(void)
1636: {
1637: unreadch();
1638: push_number(readnumber(&bmachine.readstack[bmachine.readsp],
1639: bmachine.ibase));
1640: }
1641:
1642: static void
1643: unknown(void)
1644: {
1645: int ch = bmachine.readstack[bmachine.readsp].lastchar;
1646: warnx("%c (0%o) is unimplemented", ch, ch);
1647: }
1648:
1649: static void
1650: eval_string(char *p)
1651: {
1652: int ch;
1653:
1654: if (bmachine.readsp > 0) {
1655: /* Check for tail call. Do not recurse in that case. */
1656: ch = readch();
1657: if (ch == EOF) {
1658: src_free();
1659: src_setstring(&bmachine.readstack[bmachine.readsp], p);
1660: return;
1661: } else
1662: unreadch();
1663: }
1.19 otto 1664: if (bmachine.readsp == RECURSION_STACK_SIZE-1)
1.1 otto 1665: errx(1, "recursion too deep");
1666: src_setstring(&bmachine.readstack[++bmachine.readsp], p);
1667: }
1668:
1669: static void
1670: eval_line(void)
1671: {
1672: /* Always read from stdin */
1673: struct source in;
1674: char *p;
1675:
1676: src_setstream(&in, stdin);
1677: p = (*in.vtable->readline)(&in);
1678: eval_string(p);
1679: }
1680:
1681: static void
1682: eval_tos(void)
1683: {
1684: char *p;
1685:
1686: p = pop_string();
1687: if (p == NULL)
1688: return;
1689: eval_string(p);
1690: }
1691:
1692: void
1693: eval(void)
1694: {
1695: int ch;
1696:
1697: for (;;) {
1698: ch = readch();
1699: if (ch == EOF) {
1700: if (bmachine.readsp == 0)
1.24 otto 1701: return;
1.1 otto 1702: src_free();
1703: bmachine.readsp--;
1704: continue;
1.20 otto 1705: }
1706: if (bmachine.interrupted) {
1707: if (bmachine.readsp > 0) {
1708: src_free();
1709: bmachine.readsp--;
1710: continue;
1.22 otto 1711: } else
1.20 otto 1712: bmachine.interrupted = false;
1.1 otto 1713: }
1.9 otto 1714: #ifdef DEBUGGING
1715: fprintf(stderr, "# %c\n", ch);
1716: stack_print(stderr, &bmachine.stack, "* ",
1717: bmachine.obase);
1718: fprintf(stderr, "%d =>\n", bmachine.readsp);
1719: #endif
1.1 otto 1720:
1721: if (0 <= ch && ch < UCHAR_MAX)
1722: (*jump_table[ch])();
1723: else
1724: warnx("internal error: opcode %d", ch);
1725:
1.9 otto 1726: #ifdef DEBUGGING
1727: stack_print(stderr, &bmachine.stack, "* ",
1728: bmachine.obase);
1729: fprintf(stderr, "%d ==\n", bmachine.readsp);
1730: #endif
1.1 otto 1731: }
1732: }