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
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 for (;;) {
541 unsigned digit = (unsigned)*nptr - '0';
542 if (digit >= 10
543 && digit <= 'z' - '0'
544 ) {
545
546 digit = (unsigned)(*nptr | 0x20) - ('a' - 10);
547 if (base > 36 && *nptr <= '_') {
548
549 if (*nptr == '_')
550 digit = 63;
551 else if (*nptr == '@')
552 digit = 62;
553 else if (digit < 36)
554 digit += 36 - 10;
555 else
556 break;
557 }
558
559
560
561 }
562 if (digit >= base)
563 break;
564
565 n = n * base + digit;
566 nptr++;
567 }
568
569
570
571
572
573
574 *endptr = (char*)nptr;
575 return n;
576}
577#else
578# if ENABLE_FEATURE_SH_MATH_64
579# define strto_arith_t(nptr, endptr) strtoull(nptr, endptr, 0)
580# else
581# define strto_arith_t(nptr, endptr) strtoul(nptr, endptr, 0)
582# endif
583#endif
584
585static arith_t
586evaluate_string(arith_state_t *math_state, const char *expr)
587{
588 operator lasttok;
589 const char *errmsg;
590 const char *start_expr = expr = skip_whitespace(expr);
591 unsigned expr_len = strlen(expr) + 2;
592
593
594
595
596 var_or_num_t *const numstack = alloca((expr_len / 2) * sizeof(numstack[0]));
597 var_or_num_t *numstackptr = numstack;
598
599 operator *const stack = alloca(expr_len * sizeof(stack[0]));
600 operator *stackptr = stack;
601
602
603 *stackptr++ = lasttok = TOK_LPAREN;
604 errmsg = NULL;
605
606 while (1) {
607 const char *p;
608 operator op;
609 operator prec;
610 char arithval;
611
612 expr = skip_whitespace(expr);
613 arithval = *expr;
614 if (arithval == '\0') {
615 if (expr == start_expr) {
616
617 numstack->val = 0;
618 goto ret;
619 }
620
621
622
623
624
625
626 if (expr != ptr_to_rparen + 1) {
627
628
629
630 expr = ptr_to_rparen;
631 continue;
632 }
633
634 if (numstackptr != numstack + 1) {
635
636 goto err;
637 }
638 if (numstack->var) {
639
640 errmsg = arith_lookup_val(math_state, numstack);
641 }
642 goto ret;
643 }
644
645 p = endofname(expr);
646 if (p != expr) {
647
648 size_t var_name_size = (p-expr) + 1;
649 numstackptr->var = alloca(var_name_size);
650 safe_strncpy(numstackptr->var, expr, var_name_size);
651 expr = p;
652 num:
653 numstackptr->second_val_present = 0;
654 numstackptr++;
655 lasttok = TOK_NUM;
656 continue;
657 }
658
659 if (isdigit(arithval)) {
660
661 numstackptr->var = NULL;
662 errno = 0;
663 numstackptr->val = strto_arith_t(expr, (char**) &expr);
664 if (errno)
665 numstackptr->val = 0;
666 goto num;
667 }
668
669
670
671
672
673
674
675
676 if (lasttok == TOK_NUM && !numstackptr[-1].var
677 && (expr[0] == '+' || expr[0] == '-')
678 && (expr[1] == expr[0])
679 ) {
680
681 op = (expr[0] == '+' ? TOK_ADD : TOK_SUB);
682 expr += 1;
683 goto tok_found1;
684 }
685
686 p = op_tokens;
687 while (1) {
688
689 const char *e = expr;
690 while (1) {
691 if (*p == '\0') {
692
693 expr = e;
694 goto tok_found;
695 }
696 if (*p != *e)
697 break;
698 p++;
699 e++;
700 }
701
702 while (*p)
703 p++;
704 p += 2;
705 if (*p == '\0') {
706
707
708 goto err;
709 }
710 }
711 tok_found:
712 op = p[1];
713 tok_found1:
714
715
716
717 if (lasttok == TOK_POST_INC || lasttok == TOK_POST_DEC)
718 lasttok = TOK_NUM;
719
720
721
722
723
724 if (lasttok != TOK_NUM) {
725 switch (op) {
726 case TOK_ADD:
727 op = TOK_UPLUS;
728 break;
729 case TOK_SUB:
730 op = TOK_UMINUS;
731 break;
732 case TOK_POST_INC:
733 op = TOK_PRE_INC;
734 break;
735 case TOK_POST_DEC:
736 op = TOK_PRE_DEC;
737 break;
738 }
739 }
740
741
742
743
744
745
746
747
748
749
750
751 prec = PREC(op);
752 if ((prec > 0 && prec < UNARYPREC) || prec == SPEC_PREC) {
753
754 if (lasttok != TOK_NUM) {
755
756 goto err;
757 }
758 while (stackptr != stack) {
759 operator prev_op = *--stackptr;
760 if (op == TOK_RPAREN) {
761
762
763
764 if (prev_op == TOK_LPAREN) {
765
766
767 lasttok = TOK_NUM;
768 goto next;
769 }
770 } else {
771 operator prev_prec = PREC(prev_op);
772 fix_assignment_prec(prec);
773 fix_assignment_prec(prev_prec);
774 if (prev_prec < prec
775 || (prev_prec == prec && is_right_associative(prec))
776 ) {
777 stackptr++;
778 break;
779 }
780 }
781 errmsg = arith_apply(math_state, prev_op, numstack, &numstackptr);
782 if (errmsg)
783 goto err_with_custom_msg;
784 }
785 if (op == TOK_RPAREN)
786 goto err;
787 }
788
789
790 *stackptr++ = lasttok = op;
791 next: ;
792 }
793
794 err:
795 errmsg = "arithmetic syntax error";
796 err_with_custom_msg:
797 numstack->val = -1;
798 ret:
799 math_state->errmsg = errmsg;
800 return numstack->val;
801}
802
803arith_t FAST_FUNC
804arith(arith_state_t *math_state, const char *expr)
805{
806 math_state->errmsg = NULL;
807 math_state->list_of_recursed_names = NULL;
808 return evaluate_string(math_state, expr);
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
839
840
841
842