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