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