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