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