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