1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116#include "libbb.h"
117#include "math.h"
118
119#define lookupvar (math_state->lookupvar)
120#define setvar (math_state->setvar )
121
122
123typedef unsigned char operator;
124
125
126
127
128
129
130
131#define tok_decl(prec,id) (((id)<<5) | (prec))
132#define PREC(op) ((op) & 0x1F)
133
134#define TOK_LPAREN tok_decl(0,0)
135
136#define TOK_COMMA tok_decl(1,0)
137
138
139
140
141
142#define TOK_ASSIGN tok_decl(2,0)
143#define TOK_AND_ASSIGN tok_decl(2,1)
144#define TOK_OR_ASSIGN tok_decl(2,2)
145#define TOK_XOR_ASSIGN tok_decl(2,3)
146#define TOK_PLUS_ASSIGN tok_decl(2,4)
147#define TOK_MINUS_ASSIGN tok_decl(2,5)
148#define TOK_LSHIFT_ASSIGN tok_decl(2,6)
149#define TOK_RSHIFT_ASSIGN tok_decl(2,7)
150
151#define TOK_MUL_ASSIGN tok_decl(3,0)
152#define TOK_DIV_ASSIGN tok_decl(3,1)
153#define TOK_REM_ASSIGN tok_decl(3,2)
154
155#define fix_assignment_prec(prec) do { if (prec == 3) prec = 2; } while (0)
156
157
158#define TOK_CONDITIONAL tok_decl(4,0)
159#define TOK_CONDITIONAL_SEP tok_decl(4,1)
160
161#define TOK_OR tok_decl(5,0)
162
163#define TOK_AND tok_decl(6,0)
164
165#define TOK_BOR tok_decl(7,0)
166
167#define TOK_BXOR tok_decl(8,0)
168
169#define TOK_BAND tok_decl(9,0)
170
171#define TOK_EQ tok_decl(10,0)
172#define TOK_NE tok_decl(10,1)
173
174#define TOK_LT tok_decl(11,0)
175#define TOK_GT tok_decl(11,1)
176#define TOK_GE tok_decl(11,2)
177#define TOK_LE tok_decl(11,3)
178
179#define TOK_LSHIFT tok_decl(12,0)
180#define TOK_RSHIFT tok_decl(12,1)
181
182#define TOK_ADD tok_decl(13,0)
183#define TOK_SUB tok_decl(13,1)
184
185#define TOK_MUL tok_decl(14,0)
186#define TOK_DIV tok_decl(14,1)
187#define TOK_REM tok_decl(14,2)
188
189
190#define TOK_EXPONENT tok_decl(15,1)
191
192
193#define UNARYPREC 16
194#define TOK_BNOT tok_decl(UNARYPREC,0)
195#define TOK_NOT tok_decl(UNARYPREC,1)
196
197#define TOK_UMINUS tok_decl(UNARYPREC+1,0)
198#define TOK_UPLUS tok_decl(UNARYPREC+1,1)
199
200#define PREC_PRE (UNARYPREC+2)
201
202#define TOK_PRE_INC tok_decl(PREC_PRE, 0)
203#define TOK_PRE_DEC tok_decl(PREC_PRE, 1)
204
205#define PREC_POST (UNARYPREC+3)
206
207#define TOK_POST_INC tok_decl(PREC_POST, 0)
208#define TOK_POST_DEC tok_decl(PREC_POST, 1)
209
210#define SPEC_PREC (UNARYPREC+4)
211
212#define TOK_NUM tok_decl(SPEC_PREC, 0)
213#define TOK_RPAREN tok_decl(SPEC_PREC, 1)
214
215static int
216is_assign_op(operator op)
217{
218 operator prec = PREC(op);
219 fix_assignment_prec(prec);
220 return prec == PREC(TOK_ASSIGN)
221 || prec == PREC_PRE
222 || prec == PREC_POST;
223}
224
225static int
226is_right_associative(operator prec)
227{
228 return prec == PREC(TOK_ASSIGN)
229 || prec == PREC(TOK_EXPONENT)
230 || prec == PREC(TOK_CONDITIONAL);
231}
232
233
234typedef struct {
235 arith_t val;
236
237
238
239
240
241
242 arith_t second_val;
243 char second_val_present;
244
245 char *var;
246} var_or_num_t;
247
248typedef struct remembered_name {
249 struct remembered_name *next;
250 const char *var;
251} remembered_name;
252
253
254static arith_t FAST_FUNC
255evaluate_string(arith_state_t *math_state, const char *expr);
256
257static const char*
258arith_lookup_val(arith_state_t *math_state, var_or_num_t *t)
259{
260 if (t->var) {
261 const char *p = lookupvar(t->var);
262 if (p) {
263 remembered_name *cur;
264 remembered_name cur_save;
265
266
267
268
269 for (cur = math_state->list_of_recursed_names; cur; cur = cur->next) {
270 if (strcmp(cur->var, t->var) == 0) {
271
272 return "expression recursion loop detected";
273 }
274 }
275
276
277 cur = math_state->list_of_recursed_names;
278 cur_save.var = t->var;
279 cur_save.next = cur;
280 math_state->list_of_recursed_names = &cur_save;
281
282
283 t->val = evaluate_string(math_state, p);
284
285
286 math_state->list_of_recursed_names = cur;
287
288 return math_state->errmsg;
289 }
290
291 t->val = 0;
292 }
293 return 0;
294}
295
296
297
298
299static NOINLINE const char*
300arith_apply(arith_state_t *math_state, operator op, var_or_num_t *numstack, var_or_num_t **numstackptr)
301{
302#define NUMPTR (*numstackptr)
303
304 var_or_num_t *top_of_stack;
305 arith_t rez;
306 const char *err;
307
308
309 if (NUMPTR == numstack)
310 goto err;
311
312 top_of_stack = NUMPTR - 1;
313
314
315 err = arith_lookup_val(math_state, top_of_stack);
316 if (err)
317 return err;
318
319 rez = top_of_stack->val;
320 if (op == TOK_UMINUS)
321 rez = -rez;
322 else if (op == TOK_NOT)
323 rez = !rez;
324 else if (op == TOK_BNOT)
325 rez = ~rez;
326 else if (op == TOK_POST_INC || op == TOK_PRE_INC)
327 rez++;
328 else if (op == TOK_POST_DEC || op == TOK_PRE_DEC)
329 rez--;
330 else if (op != TOK_UPLUS) {
331
332 arith_t right_side_val;
333 char bad_second_val;
334
335
336 if (top_of_stack == numstack)
337 goto err;
338
339 NUMPTR = top_of_stack;
340
341 bad_second_val = top_of_stack->second_val_present;
342 if (op == TOK_CONDITIONAL) {
343
344
345 bad_second_val = !bad_second_val;
346 }
347 if (bad_second_val) {
348
349 return "malformed ?: operator";
350 }
351
352 top_of_stack--;
353
354 if (op != TOK_ASSIGN) {
355
356 err = arith_lookup_val(math_state, top_of_stack);
357 if (err)
358 return err;
359 }
360
361 right_side_val = rez;
362 rez = top_of_stack->val;
363 if (op == TOK_CONDITIONAL)
364 rez = (rez ? right_side_val : top_of_stack[1].second_val);
365 else if (op == TOK_CONDITIONAL_SEP) {
366 if (top_of_stack == numstack) {
367
368 return "malformed ?: operator";
369 }
370 top_of_stack->second_val_present = op;
371 top_of_stack->second_val = right_side_val;
372 }
373 else if (op == TOK_BOR || op == TOK_OR_ASSIGN)
374 rez |= right_side_val;
375 else if (op == TOK_OR)
376 rez = right_side_val || rez;
377 else if (op == TOK_BAND || op == TOK_AND_ASSIGN)
378 rez &= right_side_val;
379 else if (op == TOK_BXOR || op == TOK_XOR_ASSIGN)
380 rez ^= right_side_val;
381 else if (op == TOK_AND)
382 rez = rez && right_side_val;
383 else if (op == TOK_EQ)
384 rez = (rez == right_side_val);
385 else if (op == TOK_NE)
386 rez = (rez != right_side_val);
387 else if (op == TOK_GE)
388 rez = (rez >= right_side_val);
389 else if (op == TOK_RSHIFT || op == TOK_RSHIFT_ASSIGN)
390 rez >>= right_side_val;
391 else if (op == TOK_LSHIFT || op == TOK_LSHIFT_ASSIGN)
392 rez <<= right_side_val;
393 else if (op == TOK_GT)
394 rez = (rez > right_side_val);
395 else if (op == TOK_LT)
396 rez = (rez < right_side_val);
397 else if (op == TOK_LE)
398 rez = (rez <= right_side_val);
399 else if (op == TOK_MUL || op == TOK_MUL_ASSIGN)
400 rez *= right_side_val;
401 else if (op == TOK_ADD || op == TOK_PLUS_ASSIGN)
402 rez += right_side_val;
403 else if (op == TOK_SUB || op == TOK_MINUS_ASSIGN)
404 rez -= right_side_val;
405 else if (op == TOK_ASSIGN || op == TOK_COMMA)
406 rez = right_side_val;
407 else if (op == TOK_EXPONENT) {
408 arith_t c;
409 if (right_side_val < 0)
410 return "exponent less than 0";
411 c = 1;
412 while (--right_side_val >= 0)
413 c *= rez;
414 rez = c;
415 }
416 else if (right_side_val == 0)
417 return "divide by zero";
418 else if (op == TOK_DIV || op == TOK_DIV_ASSIGN
419 || op == TOK_REM || op == TOK_REM_ASSIGN) {
420
421
422
423
424
425
426
427
428
429
430 if (right_side_val == -1
431 && rez << 1 == 0
432 ) {
433 right_side_val = 1;
434 }
435 if (op == TOK_DIV || op == TOK_DIV_ASSIGN)
436 rez /= right_side_val;
437 else {
438 rez %= right_side_val;
439 }
440 }
441 }
442
443 if (is_assign_op(op)) {
444 char buf[sizeof(arith_t)*3 + 2];
445
446 if (top_of_stack->var == NULL) {
447
448
449 goto err;
450 }
451
452 sprintf(buf, ARITH_FMT, rez);
453 setvar(top_of_stack->var, buf);
454
455 if (op == TOK_POST_INC)
456 rez--;
457 else if (op == TOK_POST_DEC)
458 rez++;
459 }
460
461 top_of_stack->val = rez;
462
463 top_of_stack->var = NULL;
464 return NULL;
465 err:
466 return "arithmetic syntax error";
467#undef NUMPTR
468}
469
470
471static const char op_tokens[] ALIGN1 = {
472 '<','<','=',0, TOK_LSHIFT_ASSIGN,
473 '>','>','=',0, TOK_RSHIFT_ASSIGN,
474 '<','<', 0, TOK_LSHIFT,
475 '>','>', 0, TOK_RSHIFT,
476 '|','|', 0, TOK_OR,
477 '&','&', 0, TOK_AND,
478 '!','=', 0, TOK_NE,
479 '<','=', 0, TOK_LE,
480 '>','=', 0, TOK_GE,
481 '=','=', 0, TOK_EQ,
482 '|','=', 0, TOK_OR_ASSIGN,
483 '&','=', 0, TOK_AND_ASSIGN,
484 '*','=', 0, TOK_MUL_ASSIGN,
485 '/','=', 0, TOK_DIV_ASSIGN,
486 '%','=', 0, TOK_REM_ASSIGN,
487 '+','=', 0, TOK_PLUS_ASSIGN,
488 '-','=', 0, TOK_MINUS_ASSIGN,
489 '-','-', 0, TOK_POST_DEC,
490 '^','=', 0, TOK_XOR_ASSIGN,
491 '+','+', 0, TOK_POST_INC,
492 '*','*', 0, TOK_EXPONENT,
493 '!', 0, TOK_NOT,
494 '<', 0, TOK_LT,
495 '>', 0, TOK_GT,
496 '=', 0, TOK_ASSIGN,
497 '|', 0, TOK_BOR,
498 '&', 0, TOK_BAND,
499 '*', 0, TOK_MUL,
500 '/', 0, TOK_DIV,
501 '%', 0, TOK_REM,
502 '+', 0, TOK_ADD,
503 '-', 0, TOK_SUB,
504 '^', 0, TOK_BXOR,
505
506 '~', 0, TOK_BNOT,
507 ',', 0, TOK_COMMA,
508 '?', 0, TOK_CONDITIONAL,
509 ':', 0, TOK_CONDITIONAL_SEP,
510 ')', 0, TOK_RPAREN,
511 '(', 0, TOK_LPAREN,
512 0
513};
514#define ptr_to_rparen (&op_tokens[sizeof(op_tokens)-7])
515
516#if ENABLE_FEATURE_SH_MATH_BASE
517static arith_t strto_arith_t(const char *nptr, char **endptr)
518{
519 unsigned base;
520 arith_t n;
521
522# if ENABLE_FEATURE_SH_MATH_64
523 n = strtoull(nptr, endptr, 0);
524# else
525 n = strtoul(nptr, endptr, 0);
526# endif
527 if (**endptr != '#'
528 || (*nptr < '1' || *nptr > '9')
529 || (n < 2 || n > 64)
530 ) {
531 return n;
532 }
533
534
535
536
537 base = (unsigned)n;
538 n = 0;
539 nptr = *endptr + 1;
540
541 for (;;) {
542 unsigned digit = (unsigned)*nptr - '0';
543 if (digit >= 10) {
544
545 if (*nptr > 'z')
546 break;
547
548 digit = (unsigned)(*nptr | 0x20) - ('a' - 10);
549 if (base > 36 && *nptr <= '_') {
550
551 if (*nptr == '@')
552 digit = 62;
553 else if (*nptr == '_')
554 digit = 63;
555 else if (digit < 36)
556 digit += 36 - 10;
557 else
558 break;
559 }
560
561
562
563 }
564 if (digit >= base)
565 break;
566
567 n = n * base + digit;
568 nptr++;
569 }
570 *endptr = (char*)nptr;
571 return n;
572}
573#else
574# if ENABLE_FEATURE_SH_MATH_64
575# define strto_arith_t(nptr, endptr) strtoull(nptr, endptr, 0)
576# else
577# define strto_arith_t(nptr, endptr) strtoul(nptr, endptr, 0)
578# endif
579#endif
580
581static arith_t FAST_FUNC
582evaluate_string(arith_state_t *math_state, const char *expr)
583{
584 operator lasttok;
585 const char *errmsg;
586 const char *start_expr = expr = skip_whitespace(expr);
587 unsigned expr_len = strlen(expr) + 2;
588
589
590
591
592 var_or_num_t *const numstack = alloca((expr_len / 2) * sizeof(numstack[0]));
593 var_or_num_t *numstackptr = numstack;
594
595 operator *const stack = alloca(expr_len * sizeof(stack[0]));
596 operator *stackptr = stack;
597
598
599 *stackptr++ = lasttok = TOK_LPAREN;
600 errmsg = NULL;
601
602 while (1) {
603 const char *p;
604 operator op;
605 operator prec;
606 char arithval;
607
608 expr = skip_whitespace(expr);
609 arithval = *expr;
610 if (arithval == '\0') {
611 if (expr == start_expr) {
612
613 numstack->val = 0;
614 goto ret;
615 }
616
617
618
619
620
621
622 if (expr != ptr_to_rparen + 1) {
623
624
625
626 expr = ptr_to_rparen;
627 continue;
628 }
629
630 if (numstackptr != numstack + 1) {
631
632 goto err;
633 }
634 if (numstack->var) {
635
636 errmsg = arith_lookup_val(math_state, numstack);
637 }
638 goto ret;
639 }
640
641 p = endofname(expr);
642 if (p != expr) {
643
644 size_t var_name_size = (p-expr) + 1;
645 numstackptr->var = alloca(var_name_size);
646 safe_strncpy(numstackptr->var, expr, var_name_size);
647 expr = p;
648 num:
649 numstackptr->second_val_present = 0;
650 numstackptr++;
651 lasttok = TOK_NUM;
652 continue;
653 }
654
655 if (isdigit(arithval)) {
656
657 numstackptr->var = NULL;
658 errno = 0;
659 numstackptr->val = strto_arith_t(expr, (char**) &expr);
660 if (errno)
661 numstackptr->val = 0;
662 goto num;
663 }
664
665
666
667
668
669
670
671
672 if (lasttok == TOK_NUM && !numstackptr[-1].var
673 && (expr[0] == '+' || expr[0] == '-')
674 && (expr[1] == expr[0])
675 ) {
676
677 op = (expr[0] == '+' ? TOK_ADD : TOK_SUB);
678 expr += 1;
679 goto tok_found1;
680 }
681
682 p = op_tokens;
683 while (1) {
684
685 const char *e = expr;
686 while (1) {
687 if (*p == '\0') {
688
689 expr = e;
690 goto tok_found;
691 }
692 if (*p != *e)
693 break;
694 p++;
695 e++;
696 }
697
698 while (*p)
699 p++;
700 p += 2;
701 if (*p == '\0') {
702
703
704 goto err;
705 }
706 }
707 tok_found:
708 op = p[1];
709 tok_found1:
710
711
712
713 if (lasttok == TOK_POST_INC || lasttok == TOK_POST_DEC)
714 lasttok = TOK_NUM;
715
716
717
718
719
720 if (lasttok != TOK_NUM) {
721 switch (op) {
722 case TOK_ADD:
723 op = TOK_UPLUS;
724 break;
725 case TOK_SUB:
726 op = TOK_UMINUS;
727 break;
728 case TOK_POST_INC:
729 op = TOK_PRE_INC;
730 break;
731 case TOK_POST_DEC:
732 op = TOK_PRE_DEC;
733 break;
734 }
735 }
736
737
738
739
740
741
742
743
744
745
746
747 prec = PREC(op);
748 if ((prec > 0 && prec < UNARYPREC) || prec == SPEC_PREC) {
749
750 if (lasttok != TOK_NUM) {
751
752 goto err;
753 }
754 while (stackptr != stack) {
755 operator prev_op = *--stackptr;
756 if (op == TOK_RPAREN) {
757
758
759
760 if (prev_op == TOK_LPAREN) {
761
762
763 lasttok = TOK_NUM;
764 goto next;
765 }
766 } else {
767 operator prev_prec = PREC(prev_op);
768 fix_assignment_prec(prec);
769 fix_assignment_prec(prev_prec);
770 if (prev_prec < prec
771 || (prev_prec == prec && is_right_associative(prec))
772 ) {
773 stackptr++;
774 break;
775 }
776 }
777 errmsg = arith_apply(math_state, prev_op, numstack, &numstackptr);
778 if (errmsg)
779 goto err_with_custom_msg;
780 }
781 if (op == TOK_RPAREN)
782 goto err;
783 }
784
785
786 *stackptr++ = lasttok = op;
787 next: ;
788 }
789
790 err:
791 errmsg = "arithmetic syntax error";
792 err_with_custom_msg:
793 numstack->val = -1;
794 ret:
795 math_state->errmsg = errmsg;
796 return numstack->val;
797}
798
799arith_t FAST_FUNC
800arith(arith_state_t *math_state, const char *expr)
801{
802 math_state->errmsg = NULL;
803 math_state->list_of_recursed_names = NULL;
804 return evaluate_string(math_state, expr);
805}
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838