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