Annotation of src/usr.bin/dc/bcode.c, Revision 1.6
1.6 ! otto 1: /* $OpenBSD: bcode.c,v 1.5 2003/09/22 14:49:16 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.6 ! otto 20: static const char rcsid[] = "$OpenBSD: bcode.c,v 1.5 2003/09/22 14:49:16 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;
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;
1.5 otto 655: struct number *n;
1.1 otto 656:
657: index = readch();
658: if (0 <= index && index < UCHAR_MAX) {
659: v = stack_tos(&bmachine.reg[index]);
1.5 otto 660: if (v == NULL) {
661: n = new_number();
662: bn_check(BN_zero(n->number));
663: push_number(n);
664: } else
1.1 otto 665: push(stack_dup_value(v, ©));
666: } else
667: warnx("internal error: reg num = %d", index);
668: }
669:
670: static void
671: store(void)
672: {
673: int index;
674: struct value *val;
675:
676: index = readch();
677: if (0 <= index && index < UCHAR_MAX) {
678: val = pop();
679: if (val == NULL) {
680: return;
681: }
682: stack_set_tos(&bmachine.reg[index], val);
683: } else
684: warnx("internal error: reg num = %d", index);
685: }
686:
687: static void
688: load_stack(void)
689: {
690: int index;
691: struct stack *stack;
692: struct value *value, copy;
693:
694: index = readch();
695: if (0 <= index && index < UCHAR_MAX) {
696: stack = &bmachine.reg[index];
697: value = NULL;
698: if (stack_size(stack) > 0) {
699: value = stack_pop(stack);
700: }
701: if (value != NULL)
702: push(stack_dup_value(value, ©));
703: else
704: warnx("stack register '%c' (0%o) is empty",
705: index, index);
706: } else
707: warnx("internal error: reg num = %d", index);
708: }
709:
710: static void
711: store_stack(void)
712: {
713: int index;
714: struct value *value;
715:
716: index = readch();
717: if (0 <= index && index < UCHAR_MAX) {
718: value = pop();
719: if (value == NULL)
720: return;
721: stack_push(&bmachine.reg[index], value);
722: } else
723: warnx("internal error: reg num = %d", index);
724: }
725:
726: static void
727: load_array(void)
728: {
729: int reg;
730: struct number *inumber, *n;
731: u_long index;
732: struct stack *stack;
733: struct value *v, copy;
734:
735: reg = readch();
736: if (0 <= reg && reg < UCHAR_MAX) {
737: inumber = pop_number();
738: if (inumber == NULL)
739: return;
740: index = get_ulong(inumber);
741: if (BN_cmp(inumber->number, &zero) < 0)
742: warnx("negative index");
743: else if (index == BN_MASK2 || index > MAX_ARRAY_INDEX)
744: warnx("index too big");
745: else {
746: stack = &bmachine.reg[reg];
747: v = frame_retrieve(stack, index);
748: if (v == NULL) {
749: n = new_number();
750: bn_check(BN_zero(n->number));
751: push_number(n);
752: }
753: else
754: push(stack_dup_value(v, ©));
755: }
756: free_number(inumber);
757: } else
758: warnx("internal error: reg num = %d", reg);
759: }
760:
761: static void
762: store_array(void)
763: {
764: int reg;
765: struct number *inumber;
766: u_long index;
767: struct value *value;
768: struct stack *stack;
769:
770: reg = readch();
771: if (0 <= reg && reg < UCHAR_MAX) {
772: inumber = pop_number();
1.6 ! otto 773: if (inumber == NULL)
! 774: return;
1.1 otto 775: value = pop();
1.6 ! otto 776: if (value == NULL) {
! 777: free_number(inumber);
1.1 otto 778: return;
779: }
780: index = get_ulong(inumber);
781: if (BN_cmp(inumber->number, &zero) < 0) {
782: warnx("negative index");
783: stack_free_value(value);
784: } else if (index == BN_MASK2 || index > MAX_ARRAY_INDEX) {
785: warnx("index too big");
786: stack_free_value(value);
787: } else {
788: stack = &bmachine.reg[reg];
789: frame_assign(stack, index, value);
790: }
791: free_number(inumber);
792: } else
793: warnx("internal error: reg num = %d", reg);
794: }
795:
796: static void
797: push_line(void)
798: {
799: push_string(read_string(&bmachine.readstack[bmachine.readsp]));
800: }
801:
802: static void
803: bexec(char *line)
804: {
805: system(line);
806: free(line);
807: }
808:
809: static void
810: badd(void)
811: {
812: struct number *a, *b;
813: struct number *r;
814:
815: a = pop_number();
816: if (a == NULL) {
817: return;
818: }
819: b = pop_number();
820: if (b == NULL) {
821: push_number(a);
822: return;
823: }
824:
825: r = new_number();
826: r->scale = max(a->scale, b->scale);
827: if (r->scale > a->scale)
828: normalize(a, r->scale);
829: else if (r->scale > b->scale)
830: normalize(b, r->scale);
831: bn_check(BN_add(r->number, a->number, b->number));
832: push_number(r);
833: free_number(a);
834: free_number(b);
835: }
836:
837: static void
838: bsub(void)
839: {
840: struct number *a, *b;
841: struct number *r;
842:
843: a = pop_number();
844: if (a == NULL) {
845: return;
846: }
847: b = pop_number();
848: if (b == NULL) {
849: push_number(a);
850: return;
851: }
852:
853: r = new_number();
854:
855: r->scale = max(a->scale, b->scale);
856: if (r->scale > a->scale)
857: normalize(a, r->scale);
858: else if (r->scale > b->scale)
859: normalize(b, r->scale);
860: bn_check(BN_sub(r->number, b->number, a->number));
861: push_number(r);
862: free_number(a);
863: free_number(b);
864: }
865:
866: void
867: bmul_number(struct number *r, struct number *a, struct number *b)
868: {
869: BN_CTX *ctx;
870:
871: /* Create copies of the scales, since r might be equal to a or b */
872: u_int ascale = a->scale;
873: u_int bscale = b->scale;
874: u_int rscale = ascale + bscale;
875:
876: ctx = BN_CTX_new();
877: bn_checkp(ctx);
878: bn_check(BN_mul(r->number, a->number, b->number, ctx));
879: BN_CTX_free(ctx);
880:
881: if (rscale > bmachine.scale && rscale > ascale && rscale > bscale) {
882: r->scale = rscale;
883: normalize(r, max(bmachine.scale, max(ascale, bscale)));
884: } else
885: r->scale = rscale;
886: }
887:
888: static void
889: bmul(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: bmul_number(r, a, b);
906:
907: push_number(r);
908: free_number(a);
909: free_number(b);
910: }
911:
912: static void
913: bdiv(void)
914: {
915: struct number *a, *b;
916: struct number *r;
917: u_int scale;
918: BN_CTX *ctx;
919:
920: a = pop_number();
921: if (a == NULL) {
922: return;
923: }
924: b = pop_number();
925: if (b == NULL) {
926: push_number(a);
927: return;
928: }
929:
930: r = new_number();
931: r->scale = bmachine.scale;
932: scale = max(a->scale, b->scale);
933:
934: if (BN_is_zero(a->number))
935: warnx("divide by zero");
936: else {
937: normalize(a, scale);
938: normalize(b, scale + r->scale);
939:
940: ctx = BN_CTX_new();
941: bn_checkp(ctx);
942: bn_check(BN_div(r->number, NULL, b->number, a->number, ctx));
943: BN_CTX_free(ctx);
944: }
945: push_number(r);
946: free_number(a);
947: free_number(b);
948: }
949:
950: static void
951: bmod(void)
952: {
953: struct number *a, *b;
954: struct number *r;
955: u_int scale;
956: BN_CTX *ctx;
957:
958: a = pop_number();
959: if (a == NULL) {
960: return;
961: }
962: b = pop_number();
963: if (b == NULL) {
964: push_number(a);
965: return;
966: }
967:
968: r = new_number();
969: scale = max(a->scale, b->scale);
970: r->scale = max(b->scale, a->scale + bmachine.scale);
971:
972: if (BN_is_zero(a->number))
973: warnx("remainder by zero");
974: else {
975: normalize(a, scale);
976: normalize(b, scale + bmachine.scale);
977:
978: ctx = BN_CTX_new();
979: bn_checkp(ctx);
980: bn_check(BN_mod(r->number, b->number, a->number, ctx));
981: BN_CTX_free(ctx);
982: }
983: push_number(r);
984: free_number(a);
985: free_number(b);
986: }
987:
988: static void
989: bexp(void)
990: {
991: struct number *a, *p;
992: struct number *r;
993: bool neg;
994: u_int scale;
995:
996: p = pop_number();
997: if (p == NULL) {
998: return;
999: }
1000: a = pop_number();
1001: if (a == NULL) {
1002: push_number(p);
1003: return;
1004: }
1005:
1006: if (p->scale != 0)
1007: warnx("Runtime warning: non-zero scale in exponent");
1008: normalize(p, 0);
1009:
1010: neg = false;
1011: if (BN_cmp(p->number, &zero) < 0) {
1012: neg = true;
1013: negate(p);
1014: scale = bmachine.scale;
1015: } else {
1016: /* Posix bc says min(a.scale * b, max(a.scale, scale) */
1017: u_long b;
1018: u_int m;
1019:
1020: b = BN_get_word(p->number);
1021: m = max(a->scale, bmachine.scale);
1022: scale = a->scale * b;
1023: if (scale > m || b == BN_MASK2)
1024: scale = m;
1025: }
1.2 deraadt 1026:
1.1 otto 1027: if (BN_is_zero(p->number)) {
1028: r = new_number();
1029: bn_check(BN_one(r->number));
1030: normalize(r, scale);
1031: } else {
1032: while (!BN_is_bit_set(p->number, 0)) {
1033: bmul_number(a, a, a);
1034: bn_check(BN_rshift1(p->number, p->number));
1035: }
1036:
1037: r = dup_number(a);
1038: normalize(r, scale);
1039: bn_check(BN_rshift1(p->number, p->number));
1040:
1041: while (!BN_is_zero(p->number)) {
1042: bmul_number(a, a, a);
1043: if (BN_is_bit_set(p->number, 0))
1044: bmul_number(r, r, a);
1045: bn_check(BN_rshift1(p->number, p->number));
1046: }
1047:
1048: if (neg) {
1049: BN_CTX *ctx;
1050: BIGNUM *one;
1051:
1052: one = BN_new();
1053: bn_checkp(one);
1054: BN_one(one);
1055: ctx = BN_CTX_new();
1056: bn_checkp(ctx);
1057: r->scale = scale;
1058: scale_number(one, r->scale);
1059: bn_check(BN_div(r->number, NULL, one, r->number, ctx));
1060: BN_free(one);
1061: BN_CTX_free(ctx);
1062: }
1063: }
1064: push_number(r);
1065: free_number(a);
1066: free_number(p);
1067: }
1068:
1069: static bool
1070: bsqrt_stop(const BIGNUM *x, const BIGNUM *y)
1071: {
1072: BIGNUM *r;
1073: bool ret;
1074:
1075: r = BN_new();
1076: bn_checkp(r);
1077: bn_check(BN_sub(r, x, y));
1078: ret = BN_is_one(r) || BN_is_zero(r);
1079: BN_free(r);
1080: return ret;
1081: }
1082:
1083: static void
1084: bsqrt(void)
1085: {
1086: struct number *n;
1087: struct number *r;
1088: BIGNUM *x, *y;
1089: u_int scale;
1090: BN_CTX *ctx;
1091:
1092: n = pop_number();
1093: if (n == NULL) {
1094: return;
1095: }
1096: if (BN_is_zero(n->number)) {
1097: r = new_number();
1098: push_number(r);
1099: } else if (BN_cmp(n->number, &zero) < 0)
1100: warnx("square root of negative number");
1101: else {
1102: scale = max(bmachine.scale, n->scale);
1103: normalize(n, 2*scale);
1104: x = BN_dup(n->number);
1105: bn_checkp(x);
1106: bn_check(BN_rshift(x, x, BN_num_bits(x)/2));
1107: y = BN_new();
1108: bn_checkp(y);
1109: ctx = BN_CTX_new();
1110: bn_checkp(ctx);
1111: for (;;) {
1112: bn_checkp(BN_copy(y, x));
1113: bn_check(BN_div(x, NULL, n->number, x, ctx));
1114: bn_check(BN_add(x, x, y));
1115: bn_check(BN_rshift1(x, x));
1116: if (bsqrt_stop(x, y))
1117: break;
1118: }
1119: r = bmalloc(sizeof(*r));
1120: r->scale = scale;
1121: r->number = y;
1122: BN_free(x);
1123: BN_CTX_free(ctx);
1124: push_number(r);
1125: }
1126:
1127: free_number(n);
1128: }
1129:
1130: static void
1131: equal(void)
1132: {
1133: compare(BCODE_EQUAL);
1134: }
1135:
1136: static void
1137: not_equal(void)
1138: {
1139: compare(BCODE_NOT_EQUAL);
1140: }
1141:
1142: static void
1143: less(void)
1144: {
1145: compare(BCODE_LESS);
1146: }
1147:
1148: static void
1149: not_compare(void)
1150: {
1151: switch (readch()) {
1152: case '<':
1153: not_less();
1154: break;
1155: case '>':
1156: not_greater();
1157: break;
1158: case '=':
1159: not_equal();
1160: break;
1.2 deraadt 1161: default:
1.1 otto 1162: unreadch();
1163: bexec(readline());
1164: break;
1165: }
1166: }
1167:
1168: static void
1169: not_less(void)
1170: {
1171: compare(BCODE_NOT_LESS);
1172: }
1173:
1174: static void
1175: greater(void)
1176: {
1177: compare(BCODE_GREATER);
1178: }
1179:
1180: static void
1181: not_greater(void)
1182: {
1183: compare(BCODE_NOT_GREATER);
1184: }
1185:
1186: static void
1187: compare(enum bcode_compare type)
1188: {
1189: int index;
1190: struct number *a, *b;
1191: u_int scale;
1192: int cmp;
1193: bool ok;
1194: struct value *v;
1195:
1196: index = readch();
1197:
1198: a = pop_number();
1199: if (a == NULL) {
1200: return;
1201: }
1202: b = pop_number();
1203: if (b == NULL) {
1204: push_number(a);
1205: return;
1206: }
1207:
1208: scale = max(a->scale, b->scale);
1209: if (scale > a->scale)
1210: normalize(a, scale);
1211: else if (scale > scale)
1212: normalize(b, scale);
1213:
1214: cmp = BN_cmp(a->number, b->number);
1215:
1216: free_number(a);
1217: free_number(b);
1218:
1219: ok = false;
1220: switch (type) {
1.2 deraadt 1221: case BCODE_EQUAL:
1.1 otto 1222: ok = cmp == 0;
1223: break;
1.2 deraadt 1224: case BCODE_NOT_EQUAL:
1.1 otto 1225: ok = cmp != 0;
1226: break;
1.2 deraadt 1227: case BCODE_LESS:
1.1 otto 1228: ok = cmp < 0;
1229: break;
1.2 deraadt 1230: case BCODE_NOT_LESS:
1.1 otto 1231: ok = cmp >= 0;
1232: break;
1.2 deraadt 1233: case BCODE_GREATER:
1.1 otto 1234: ok = cmp > 0;
1235: break;
1236: case BCODE_NOT_GREATER:
1237: ok = cmp <= 0;
1238: break;
1239: }
1240:
1241: if (ok) {
1242: v = stack_tos(&bmachine.reg[index]);
1243: if (v == NULL)
1244: warn("stack empty");
1245: else {
1246: switch(v->type) {
1247: case BCODE_NONE:
1248: warnx("register '%c' (0%o) is empty",
1249: index, index);
1250: break;
1251: case BCODE_NUMBER:
1252: warn("eval called with non-string argument");
1253: break;
1254: case BCODE_STRING:
1255: eval_string(bstrdup(v->u.string));
1256: break;
1257: }
1258: }
1259: }
1260: }
1261:
1262:
1263: static void
1264: nop(void)
1265: {
1266: }
1267:
1.2 deraadt 1268: static void
1.1 otto 1269: quit(void)
1270: {
1.2 deraadt 1271: if (bmachine.readsp < 2)
1.1 otto 1272: exit(0);
1273: src_free();
1274: bmachine.readsp--;
1275: src_free();
1276: bmachine.readsp--;
1277: }
1278:
1279: static void
1280: quitN(void)
1281: {
1282: struct number *n;
1283: u_long i;
1284:
1285: n = pop_number();
1286: if (n == NULL)
1287: return;
1288: i = get_ulong(n);
1289: if (i == BN_MASK2 || i == 0)
1290: warnx("Q command requires a number >= 1");
1291: else if (bmachine.readsp < i)
1292: warnx("Q command argument exceeded string execution depth");
1293: else {
1294: while (i-- > 0) {
1295: src_free();
1296: bmachine.readsp--;
1297: }
1298: }
1299: }
1300:
1301: static void
1302: parse_number(void)
1303: {
1304: unreadch();
1305: push_number(readnumber(&bmachine.readstack[bmachine.readsp],
1306: bmachine.ibase));
1307: }
1308:
1309: static void
1310: unknown(void)
1311: {
1312: int ch = bmachine.readstack[bmachine.readsp].lastchar;
1313: warnx("%c (0%o) is unimplemented", ch, ch);
1314: }
1315:
1316: static void
1317: eval_string(char *p)
1318: {
1319: int ch;
1320:
1321: if (bmachine.readsp > 0) {
1322: /* Check for tail call. Do not recurse in that case. */
1323: ch = readch();
1324: if (ch == EOF) {
1325: src_free();
1326: src_setstring(&bmachine.readstack[bmachine.readsp], p);
1327: return;
1328: } else
1329: unreadch();
1330: }
1331: if (bmachine.readsp == MAX_RECURSION)
1332: errx(1, "recursion too deep");
1333: src_setstring(&bmachine.readstack[++bmachine.readsp], p);
1334: }
1335:
1336: static void
1337: eval_line(void)
1338: {
1339: /* Always read from stdin */
1340: struct source in;
1341: char *p;
1342:
1343: src_setstream(&in, stdin);
1344: p = (*in.vtable->readline)(&in);
1345: eval_string(p);
1346: }
1347:
1348: static void
1349: eval_tos(void)
1350: {
1351: char *p;
1352:
1353: p = pop_string();
1354: if (p == NULL)
1355: return;
1356: eval_string(p);
1357: }
1358:
1359: void
1360: eval(void)
1361: {
1362: int ch;
1363:
1364: for (;;) {
1365: ch = readch();
1366: if (ch == EOF) {
1367: if (bmachine.readsp == 0)
1368: exit(0);
1369: src_free();
1370: bmachine.readsp--;
1371: continue;
1372: }
1373: if (trace) {
1374: fprintf(stderr, "# %c\n", ch);
1375: stack_print(stderr, &bmachine.stack, "* ",
1376: bmachine.obase);
1377: fprintf(stderr, "%d =>\n", bmachine.readsp);
1378: }
1379:
1380: if (0 <= ch && ch < UCHAR_MAX)
1381: (*jump_table[ch])();
1382: else
1383: warnx("internal error: opcode %d", ch);
1384:
1385: if (trace) {
1386: stack_print(stderr, &bmachine.stack, "* ",
1387: bmachine.obase);
1388: fprintf(stderr, "%d ==\n", bmachine.readsp);
1389: }
1390: }
1391: }