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