Annotation of src/usr.bin/dc/bcode.c, Revision 1.7
1.7 ! otto 1: /* $OpenBSD: bcode.c,v 1.6 2003/09/28 19:15:53 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.7 ! otto 20: static const char rcsid[] = "$OpenBSD: bcode.c,v 1.6 2003/09/28 19:15:53 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);
1.7 ! otto 455: fflush(stdout);
1.1 otto 456: break;
457: case BCODE_STRING:
1.7 ! otto 458: fputs(value->u.string, stdout);
! 459: fflush(stdout);
1.1 otto 460: break;
461: }
462: stack_free_value(value);
463: }
464: }
465:
466: static __inline void
467: dup(void)
468: {
469: stack_dup(&bmachine.stack);
470: }
471:
472: static void
473: get_scale(void)
474: {
475: struct number *n;
476:
477: n = new_number();
478: bn_check(BN_set_word(n->number, bmachine.scale));
479: push_number(n);
480: }
481:
482: static void
483: set_scale(void)
484: {
485: struct number *n;
486: u_long scale;
487:
488: n = pop_number();
489: if (n != NULL) {
490: if (BN_cmp(n->number, &zero) < 0)
491: warnx("scale must be a nonnegative number");
492: else {
493: scale = get_ulong(n);
494: if (scale != BN_MASK2)
495: bmachine.scale = scale;
496: else
497: warnx("scale too large");
498: }
499: free_number(n);
500: }
501: }
502:
503: static void
504: get_obase(void)
505: {
506: struct number *n;
507:
508: n = new_number();
509: bn_check(BN_set_word(n->number, bmachine.obase));
510: push_number(n);
511: }
512:
513: static void
514: set_obase(void)
515: {
516: struct number *n;
517: u_long base;
518:
519: n = pop_number();
520: if (n != NULL) {
521: base = get_ulong(n);
522: if (base != BN_MASK2 && base > 1)
523: bmachine.obase = base;
524: else
525: warnx("output base must be a number greater than 1");
526: free_number(n);
527: }
528: }
529:
530: static void
531: get_ibase(void)
532: {
533: struct number *n;
534:
535: n = new_number();
536: bn_check(BN_set_word(n->number, bmachine.ibase));
537: push_number(n);
538: }
539:
540: static void
541: set_ibase(void)
542: {
543: struct number *n;
544: u_long base;
545:
546: n = pop_number();
547: if (n != NULL) {
548: base = get_ulong(n);
549: if (base != BN_MASK2 && 2 <= base && base <= 16)
550: bmachine.ibase = base;
551: else
552: warnx("input base must be a number between 2 and 16 "
553: "(inclusive)");
554: free_number(n);
555: }
556: }
557:
558: static void
559: stackdepth(void)
560: {
561: u_int i;
562: struct number *n;
563:
564: i = stack_size(&bmachine.stack);
565: n = new_number();
566: bn_check(BN_set_word(n->number, i));
567: push_number(n);
568: }
569:
570: static void
571: push_scale(void)
572: {
573: struct value *value;
574: u_int scale = 0;
575: struct number *n;
576:
577:
578: value = pop();
579: if (value != NULL) {
580: switch (value->type) {
581: case BCODE_NONE:
582: return;
583: case BCODE_NUMBER:
584: scale = value->u.num->scale;
585: break;
586: case BCODE_STRING:
587: break;
588: }
589: stack_free_value(value);
590: n = new_number();
591: bn_check(BN_set_word(n->number, scale));
592: push_number(n);
593: }
594: }
595:
596: static u_int
597: count_digits(const struct number *n)
598: {
599: struct number *int_part, *fract_part;
600: u_int i;
601:
602: if (BN_is_zero(n->number))
603: return 1;
604:
605: int_part = new_number();
606: fract_part = new_number();
607: fract_part->scale = n->scale;
608: split_number(n, int_part->number, fract_part->number);
609:
610: i = 0;
611: while (!BN_is_zero(int_part->number)) {
612: BN_div_word(int_part->number, 10);
613: i++;
614: }
615: free_number(int_part);
616: free_number(fract_part);
617: return i + n->scale;
618: }
619:
620: static void
621: num_digits(void)
622: {
623: struct value *value;
624: u_int digits;
625: struct number *n;
626:
627: value = pop();
628: if (value != NULL) {
629: switch (value->type) {
630: case BCODE_NONE:
631: break;
632: case BCODE_NUMBER:
633: digits = count_digits(value->u.num);
634: n = new_number();
635: bn_check(BN_set_word(n->number, digits));
636: /* free first, then reassign */
637: BN_free(value->u.num->number);
638: push_number(n);
639: break;
640: case BCODE_STRING:
641: digits = strlen(value->u.string);
642: n = new_number();
643: bn_check(BN_set_word(n->number, digits));
644: /* free first, then reassign */
645: free(value->u.string);
646: push_number(n);
647: break;
648: }
649: }
650: }
651:
652: static void
653: load(void)
654: {
655: int index;
656: struct value *v, copy;
1.5 otto 657: struct number *n;
1.1 otto 658:
659: index = readch();
660: if (0 <= index && index < UCHAR_MAX) {
661: v = stack_tos(&bmachine.reg[index]);
1.5 otto 662: if (v == NULL) {
663: n = new_number();
664: bn_check(BN_zero(n->number));
665: push_number(n);
666: } else
1.1 otto 667: push(stack_dup_value(v, ©));
668: } else
669: warnx("internal error: reg num = %d", index);
670: }
671:
672: static void
673: store(void)
674: {
675: int index;
676: struct value *val;
677:
678: index = readch();
679: if (0 <= index && index < UCHAR_MAX) {
680: val = pop();
681: if (val == NULL) {
682: return;
683: }
684: stack_set_tos(&bmachine.reg[index], val);
685: } else
686: warnx("internal error: reg num = %d", index);
687: }
688:
689: static void
690: load_stack(void)
691: {
692: int index;
693: struct stack *stack;
694: struct value *value, copy;
695:
696: index = readch();
697: if (0 <= index && index < UCHAR_MAX) {
698: stack = &bmachine.reg[index];
699: value = NULL;
700: if (stack_size(stack) > 0) {
701: value = stack_pop(stack);
702: }
703: if (value != NULL)
704: push(stack_dup_value(value, ©));
705: else
706: warnx("stack register '%c' (0%o) is empty",
707: index, index);
708: } else
709: warnx("internal error: reg num = %d", index);
710: }
711:
712: static void
713: store_stack(void)
714: {
715: int index;
716: struct value *value;
717:
718: index = readch();
719: if (0 <= index && index < UCHAR_MAX) {
720: value = pop();
721: if (value == NULL)
722: return;
723: stack_push(&bmachine.reg[index], value);
724: } else
725: warnx("internal error: reg num = %d", index);
726: }
727:
728: static void
729: load_array(void)
730: {
731: int reg;
732: struct number *inumber, *n;
733: u_long index;
734: struct stack *stack;
735: struct value *v, copy;
736:
737: reg = readch();
738: if (0 <= reg && reg < UCHAR_MAX) {
739: inumber = pop_number();
740: if (inumber == NULL)
741: return;
742: index = get_ulong(inumber);
743: if (BN_cmp(inumber->number, &zero) < 0)
744: warnx("negative index");
745: else if (index == BN_MASK2 || index > MAX_ARRAY_INDEX)
746: warnx("index too big");
747: else {
748: stack = &bmachine.reg[reg];
749: v = frame_retrieve(stack, index);
750: if (v == NULL) {
751: n = new_number();
752: bn_check(BN_zero(n->number));
753: push_number(n);
754: }
755: else
756: push(stack_dup_value(v, ©));
757: }
758: free_number(inumber);
759: } else
760: warnx("internal error: reg num = %d", reg);
761: }
762:
763: static void
764: store_array(void)
765: {
766: int reg;
767: struct number *inumber;
768: u_long index;
769: struct value *value;
770: struct stack *stack;
771:
772: reg = readch();
773: if (0 <= reg && reg < UCHAR_MAX) {
774: inumber = pop_number();
1.6 otto 775: if (inumber == NULL)
776: return;
1.1 otto 777: value = pop();
1.6 otto 778: if (value == NULL) {
779: free_number(inumber);
1.1 otto 780: return;
781: }
782: index = get_ulong(inumber);
783: if (BN_cmp(inumber->number, &zero) < 0) {
784: warnx("negative index");
785: stack_free_value(value);
786: } else if (index == BN_MASK2 || index > MAX_ARRAY_INDEX) {
787: warnx("index too big");
788: stack_free_value(value);
789: } else {
790: stack = &bmachine.reg[reg];
791: frame_assign(stack, index, value);
792: }
793: free_number(inumber);
794: } else
795: warnx("internal error: reg num = %d", reg);
796: }
797:
798: static void
799: push_line(void)
800: {
801: push_string(read_string(&bmachine.readstack[bmachine.readsp]));
802: }
803:
804: static void
805: bexec(char *line)
806: {
807: system(line);
808: free(line);
809: }
810:
811: static void
812: badd(void)
813: {
814: struct number *a, *b;
815: struct number *r;
816:
817: a = pop_number();
818: if (a == NULL) {
819: return;
820: }
821: b = pop_number();
822: if (b == NULL) {
823: push_number(a);
824: return;
825: }
826:
827: r = new_number();
828: r->scale = max(a->scale, b->scale);
829: if (r->scale > a->scale)
830: normalize(a, r->scale);
831: else if (r->scale > b->scale)
832: normalize(b, r->scale);
833: bn_check(BN_add(r->number, a->number, b->number));
834: push_number(r);
835: free_number(a);
836: free_number(b);
837: }
838:
839: static void
840: bsub(void)
841: {
842: struct number *a, *b;
843: struct number *r;
844:
845: a = pop_number();
846: if (a == NULL) {
847: return;
848: }
849: b = pop_number();
850: if (b == NULL) {
851: push_number(a);
852: return;
853: }
854:
855: r = new_number();
856:
857: r->scale = max(a->scale, b->scale);
858: if (r->scale > a->scale)
859: normalize(a, r->scale);
860: else if (r->scale > b->scale)
861: normalize(b, r->scale);
862: bn_check(BN_sub(r->number, b->number, a->number));
863: push_number(r);
864: free_number(a);
865: free_number(b);
866: }
867:
868: void
869: bmul_number(struct number *r, struct number *a, struct number *b)
870: {
871: BN_CTX *ctx;
872:
873: /* Create copies of the scales, since r might be equal to a or b */
874: u_int ascale = a->scale;
875: u_int bscale = b->scale;
876: u_int rscale = ascale + bscale;
877:
878: ctx = BN_CTX_new();
879: bn_checkp(ctx);
880: bn_check(BN_mul(r->number, a->number, b->number, ctx));
881: BN_CTX_free(ctx);
882:
883: if (rscale > bmachine.scale && rscale > ascale && rscale > bscale) {
884: r->scale = rscale;
885: normalize(r, max(bmachine.scale, max(ascale, bscale)));
886: } else
887: r->scale = rscale;
888: }
889:
890: static void
891: bmul(void)
892: {
893: struct number *a, *b;
894: struct number *r;
895:
896: a = pop_number();
897: if (a == NULL) {
898: return;
899: }
900: b = pop_number();
901: if (b == NULL) {
902: push_number(a);
903: return;
904: }
905:
906: r = new_number();
907: bmul_number(r, a, b);
908:
909: push_number(r);
910: free_number(a);
911: free_number(b);
912: }
913:
914: static void
915: bdiv(void)
916: {
917: struct number *a, *b;
918: struct number *r;
919: u_int scale;
920: BN_CTX *ctx;
921:
922: a = pop_number();
923: if (a == NULL) {
924: return;
925: }
926: b = pop_number();
927: if (b == NULL) {
928: push_number(a);
929: return;
930: }
931:
932: r = new_number();
933: r->scale = bmachine.scale;
934: scale = max(a->scale, b->scale);
935:
936: if (BN_is_zero(a->number))
937: warnx("divide by zero");
938: else {
939: normalize(a, scale);
940: normalize(b, scale + r->scale);
941:
942: ctx = BN_CTX_new();
943: bn_checkp(ctx);
944: bn_check(BN_div(r->number, NULL, b->number, a->number, ctx));
945: BN_CTX_free(ctx);
946: }
947: push_number(r);
948: free_number(a);
949: free_number(b);
950: }
951:
952: static void
953: bmod(void)
954: {
955: struct number *a, *b;
956: struct number *r;
957: u_int scale;
958: BN_CTX *ctx;
959:
960: a = pop_number();
961: if (a == NULL) {
962: return;
963: }
964: b = pop_number();
965: if (b == NULL) {
966: push_number(a);
967: return;
968: }
969:
970: r = new_number();
971: scale = max(a->scale, b->scale);
972: r->scale = max(b->scale, a->scale + bmachine.scale);
973:
974: if (BN_is_zero(a->number))
975: warnx("remainder by zero");
976: else {
977: normalize(a, scale);
978: normalize(b, scale + bmachine.scale);
979:
980: ctx = BN_CTX_new();
981: bn_checkp(ctx);
982: bn_check(BN_mod(r->number, b->number, a->number, ctx));
983: BN_CTX_free(ctx);
984: }
985: push_number(r);
986: free_number(a);
987: free_number(b);
988: }
989:
990: static void
991: bexp(void)
992: {
993: struct number *a, *p;
994: struct number *r;
995: bool neg;
996: u_int scale;
997:
998: p = pop_number();
999: if (p == NULL) {
1000: return;
1001: }
1002: a = pop_number();
1003: if (a == NULL) {
1004: push_number(p);
1005: return;
1006: }
1007:
1008: if (p->scale != 0)
1009: warnx("Runtime warning: non-zero scale in exponent");
1010: normalize(p, 0);
1011:
1012: neg = false;
1013: if (BN_cmp(p->number, &zero) < 0) {
1014: neg = true;
1015: negate(p);
1016: scale = bmachine.scale;
1017: } else {
1018: /* Posix bc says min(a.scale * b, max(a.scale, scale) */
1019: u_long b;
1020: u_int m;
1021:
1022: b = BN_get_word(p->number);
1023: m = max(a->scale, bmachine.scale);
1024: scale = a->scale * b;
1025: if (scale > m || b == BN_MASK2)
1026: scale = m;
1027: }
1.2 deraadt 1028:
1.1 otto 1029: if (BN_is_zero(p->number)) {
1030: r = new_number();
1031: bn_check(BN_one(r->number));
1032: normalize(r, scale);
1033: } else {
1034: while (!BN_is_bit_set(p->number, 0)) {
1035: bmul_number(a, a, a);
1036: bn_check(BN_rshift1(p->number, p->number));
1037: }
1038:
1039: r = dup_number(a);
1040: normalize(r, scale);
1041: bn_check(BN_rshift1(p->number, p->number));
1042:
1043: while (!BN_is_zero(p->number)) {
1044: bmul_number(a, a, a);
1045: if (BN_is_bit_set(p->number, 0))
1046: bmul_number(r, r, a);
1047: bn_check(BN_rshift1(p->number, p->number));
1048: }
1049:
1050: if (neg) {
1051: BN_CTX *ctx;
1052: BIGNUM *one;
1053:
1054: one = BN_new();
1055: bn_checkp(one);
1056: BN_one(one);
1057: ctx = BN_CTX_new();
1058: bn_checkp(ctx);
1059: r->scale = scale;
1060: scale_number(one, r->scale);
1061: bn_check(BN_div(r->number, NULL, one, r->number, ctx));
1062: BN_free(one);
1063: BN_CTX_free(ctx);
1064: }
1065: }
1066: push_number(r);
1067: free_number(a);
1068: free_number(p);
1069: }
1070:
1071: static bool
1072: bsqrt_stop(const BIGNUM *x, const BIGNUM *y)
1073: {
1074: BIGNUM *r;
1075: bool ret;
1076:
1077: r = BN_new();
1078: bn_checkp(r);
1079: bn_check(BN_sub(r, x, y));
1080: ret = BN_is_one(r) || BN_is_zero(r);
1081: BN_free(r);
1082: return ret;
1083: }
1084:
1085: static void
1086: bsqrt(void)
1087: {
1088: struct number *n;
1089: struct number *r;
1090: BIGNUM *x, *y;
1091: u_int scale;
1092: BN_CTX *ctx;
1093:
1094: n = pop_number();
1095: if (n == NULL) {
1096: return;
1097: }
1098: if (BN_is_zero(n->number)) {
1099: r = new_number();
1100: push_number(r);
1101: } else if (BN_cmp(n->number, &zero) < 0)
1102: warnx("square root of negative number");
1103: else {
1104: scale = max(bmachine.scale, n->scale);
1105: normalize(n, 2*scale);
1106: x = BN_dup(n->number);
1107: bn_checkp(x);
1108: bn_check(BN_rshift(x, x, BN_num_bits(x)/2));
1109: y = BN_new();
1110: bn_checkp(y);
1111: ctx = BN_CTX_new();
1112: bn_checkp(ctx);
1113: for (;;) {
1114: bn_checkp(BN_copy(y, x));
1115: bn_check(BN_div(x, NULL, n->number, x, ctx));
1116: bn_check(BN_add(x, x, y));
1117: bn_check(BN_rshift1(x, x));
1118: if (bsqrt_stop(x, y))
1119: break;
1120: }
1121: r = bmalloc(sizeof(*r));
1122: r->scale = scale;
1123: r->number = y;
1124: BN_free(x);
1125: BN_CTX_free(ctx);
1126: push_number(r);
1127: }
1128:
1129: free_number(n);
1130: }
1131:
1132: static void
1133: equal(void)
1134: {
1135: compare(BCODE_EQUAL);
1136: }
1137:
1138: static void
1139: not_equal(void)
1140: {
1141: compare(BCODE_NOT_EQUAL);
1142: }
1143:
1144: static void
1145: less(void)
1146: {
1147: compare(BCODE_LESS);
1148: }
1149:
1150: static void
1151: not_compare(void)
1152: {
1153: switch (readch()) {
1154: case '<':
1155: not_less();
1156: break;
1157: case '>':
1158: not_greater();
1159: break;
1160: case '=':
1161: not_equal();
1162: break;
1.2 deraadt 1163: default:
1.1 otto 1164: unreadch();
1165: bexec(readline());
1166: break;
1167: }
1168: }
1169:
1170: static void
1171: not_less(void)
1172: {
1173: compare(BCODE_NOT_LESS);
1174: }
1175:
1176: static void
1177: greater(void)
1178: {
1179: compare(BCODE_GREATER);
1180: }
1181:
1182: static void
1183: not_greater(void)
1184: {
1185: compare(BCODE_NOT_GREATER);
1186: }
1187:
1188: static void
1189: compare(enum bcode_compare type)
1190: {
1191: int index;
1192: struct number *a, *b;
1193: u_int scale;
1194: int cmp;
1195: bool ok;
1196: struct value *v;
1197:
1198: index = readch();
1199:
1200: a = pop_number();
1201: if (a == NULL) {
1202: return;
1203: }
1204: b = pop_number();
1205: if (b == NULL) {
1206: push_number(a);
1207: return;
1208: }
1209:
1210: scale = max(a->scale, b->scale);
1211: if (scale > a->scale)
1212: normalize(a, scale);
1213: else if (scale > scale)
1214: normalize(b, scale);
1215:
1216: cmp = BN_cmp(a->number, b->number);
1217:
1218: free_number(a);
1219: free_number(b);
1220:
1221: ok = false;
1222: switch (type) {
1.2 deraadt 1223: case BCODE_EQUAL:
1.1 otto 1224: ok = cmp == 0;
1225: break;
1.2 deraadt 1226: case BCODE_NOT_EQUAL:
1.1 otto 1227: ok = cmp != 0;
1228: break;
1.2 deraadt 1229: case BCODE_LESS:
1.1 otto 1230: ok = cmp < 0;
1231: break;
1.2 deraadt 1232: case BCODE_NOT_LESS:
1.1 otto 1233: ok = cmp >= 0;
1234: break;
1.2 deraadt 1235: case BCODE_GREATER:
1.1 otto 1236: ok = cmp > 0;
1237: break;
1238: case BCODE_NOT_GREATER:
1239: ok = cmp <= 0;
1240: break;
1241: }
1242:
1243: if (ok) {
1244: v = stack_tos(&bmachine.reg[index]);
1245: if (v == NULL)
1246: warn("stack empty");
1247: else {
1248: switch(v->type) {
1249: case BCODE_NONE:
1250: warnx("register '%c' (0%o) is empty",
1251: index, index);
1252: break;
1253: case BCODE_NUMBER:
1254: warn("eval called with non-string argument");
1255: break;
1256: case BCODE_STRING:
1257: eval_string(bstrdup(v->u.string));
1258: break;
1259: }
1260: }
1261: }
1262: }
1263:
1264:
1265: static void
1266: nop(void)
1267: {
1268: }
1269:
1.2 deraadt 1270: static void
1.1 otto 1271: quit(void)
1272: {
1.2 deraadt 1273: if (bmachine.readsp < 2)
1.1 otto 1274: exit(0);
1275: src_free();
1276: bmachine.readsp--;
1277: src_free();
1278: bmachine.readsp--;
1279: }
1280:
1281: static void
1282: quitN(void)
1283: {
1284: struct number *n;
1285: u_long i;
1286:
1287: n = pop_number();
1288: if (n == NULL)
1289: return;
1290: i = get_ulong(n);
1291: if (i == BN_MASK2 || i == 0)
1292: warnx("Q command requires a number >= 1");
1293: else if (bmachine.readsp < i)
1294: warnx("Q command argument exceeded string execution depth");
1295: else {
1296: while (i-- > 0) {
1297: src_free();
1298: bmachine.readsp--;
1299: }
1300: }
1301: }
1302:
1303: static void
1304: parse_number(void)
1305: {
1306: unreadch();
1307: push_number(readnumber(&bmachine.readstack[bmachine.readsp],
1308: bmachine.ibase));
1309: }
1310:
1311: static void
1312: unknown(void)
1313: {
1314: int ch = bmachine.readstack[bmachine.readsp].lastchar;
1315: warnx("%c (0%o) is unimplemented", ch, ch);
1316: }
1317:
1318: static void
1319: eval_string(char *p)
1320: {
1321: int ch;
1322:
1323: if (bmachine.readsp > 0) {
1324: /* Check for tail call. Do not recurse in that case. */
1325: ch = readch();
1326: if (ch == EOF) {
1327: src_free();
1328: src_setstring(&bmachine.readstack[bmachine.readsp], p);
1329: return;
1330: } else
1331: unreadch();
1332: }
1333: if (bmachine.readsp == MAX_RECURSION)
1334: errx(1, "recursion too deep");
1335: src_setstring(&bmachine.readstack[++bmachine.readsp], p);
1336: }
1337:
1338: static void
1339: eval_line(void)
1340: {
1341: /* Always read from stdin */
1342: struct source in;
1343: char *p;
1344:
1345: src_setstream(&in, stdin);
1346: p = (*in.vtable->readline)(&in);
1347: eval_string(p);
1348: }
1349:
1350: static void
1351: eval_tos(void)
1352: {
1353: char *p;
1354:
1355: p = pop_string();
1356: if (p == NULL)
1357: return;
1358: eval_string(p);
1359: }
1360:
1361: void
1362: eval(void)
1363: {
1364: int ch;
1365:
1366: for (;;) {
1367: ch = readch();
1368: if (ch == EOF) {
1369: if (bmachine.readsp == 0)
1370: exit(0);
1371: src_free();
1372: bmachine.readsp--;
1373: continue;
1374: }
1375: if (trace) {
1376: fprintf(stderr, "# %c\n", ch);
1377: stack_print(stderr, &bmachine.stack, "* ",
1378: bmachine.obase);
1379: fprintf(stderr, "%d =>\n", bmachine.readsp);
1380: }
1381:
1382: if (0 <= ch && ch < UCHAR_MAX)
1383: (*jump_table[ch])();
1384: else
1385: warnx("internal error: opcode %d", ch);
1386:
1387: if (trace) {
1388: stack_print(stderr, &bmachine.stack, "* ",
1389: bmachine.obase);
1390: fprintf(stderr, "%d ==\n", bmachine.readsp);
1391: }
1392: }
1393: }