math.c 24 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772
  1. /*
  2. * Arithmetic code ripped out of ash shell for code sharing.
  3. *
  4. * This code is derived from software contributed to Berkeley by
  5. * Kenneth Almquist.
  6. *
  7. * Original BSD copyright notice is retained at the end of this file.
  8. *
  9. * Copyright (c) 1989, 1991, 1993, 1994
  10. * The Regents of the University of California. All rights reserved.
  11. *
  12. * Copyright (c) 1997-2005 Herbert Xu <herbert@gondor.apana.org.au>
  13. * was re-ported from NetBSD and debianized.
  14. *
  15. * rewrite arith.y to micro stack based cryptic algorithm by
  16. * Copyright (c) 2001 Aaron Lehmann <aaronl@vitelus.com>
  17. *
  18. * Modified by Paul Mundt <lethal@linux-sh.org> (c) 2004 to support
  19. * dynamic variables.
  20. *
  21. * Modified by Vladimir Oleynik <dzo@simtreas.ru> (c) 2001-2005 to be
  22. * used in busybox and size optimizations,
  23. * rewrote arith (see notes to this), added locale support,
  24. * rewrote dynamic variables.
  25. *
  26. * Licensed under GPLv2 or later, see file LICENSE in this source tree.
  27. */
  28. /* Copyright (c) 2001 Aaron Lehmann <aaronl@vitelus.com>
  29. *
  30. * Permission is hereby granted, free of charge, to any person obtaining
  31. * a copy of this software and associated documentation files (the
  32. * "Software"), to deal in the Software without restriction, including
  33. * without limitation the rights to use, copy, modify, merge, publish,
  34. * distribute, sublicense, and/or sell copies of the Software, and to
  35. * permit persons to whom the Software is furnished to do so, subject to
  36. * the following conditions:
  37. *
  38. * The above copyright notice and this permission notice shall be
  39. * included in all copies or substantial portions of the Software.
  40. *
  41. * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  42. * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  43. * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  44. * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  45. * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
  46. * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
  47. * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  48. */
  49. /* This is my infix parser/evaluator. It is optimized for size, intended
  50. * as a replacement for yacc-based parsers. However, it may well be faster
  51. * than a comparable parser written in yacc. The supported operators are
  52. * listed in #defines below. Parens, order of operations, and error handling
  53. * are supported. This code is thread safe. The exact expression format should
  54. * be that which POSIX specifies for shells.
  55. *
  56. * The code uses a simple two-stack algorithm. See
  57. * http://www.onthenet.com.au/~grahamis/int2008/week02/lect02.html
  58. * for a detailed explanation of the infix-to-postfix algorithm on which
  59. * this is based (this code differs in that it applies operators immediately
  60. * to the stack instead of adding them to a queue to end up with an
  61. * expression).
  62. */
  63. /*
  64. * Aug 24, 2001 Manuel Novoa III
  65. *
  66. * Reduced the generated code size by about 30% (i386) and fixed several bugs.
  67. *
  68. * 1) In arith_apply():
  69. * a) Cached values of *numptr and &(numptr[-1]).
  70. * b) Removed redundant test for zero denominator.
  71. *
  72. * 2) In arith():
  73. * a) Eliminated redundant code for processing operator tokens by moving
  74. * to a table-based implementation. Also folded handling of parens
  75. * into the table.
  76. * b) Combined all 3 loops which called arith_apply to reduce generated
  77. * code size at the cost of speed.
  78. *
  79. * 3) The following expressions were treated as valid by the original code:
  80. * 1() , 0! , 1 ( *3 ) .
  81. * These bugs have been fixed by internally enclosing the expression in
  82. * parens and then checking that all binary ops and right parens are
  83. * preceded by a valid expression (NUM_TOKEN).
  84. *
  85. * Note: It may be desirable to replace Aaron's test for whitespace with
  86. * ctype's isspace() if it is used by another busybox applet or if additional
  87. * whitespace chars should be considered. Look below the "#include"s for a
  88. * precompiler test.
  89. */
  90. /*
  91. * Aug 26, 2001 Manuel Novoa III
  92. *
  93. * Return 0 for null expressions. Pointed out by Vladimir Oleynik.
  94. *
  95. * Merge in Aaron's comments previously posted to the busybox list,
  96. * modified slightly to take account of my changes to the code.
  97. *
  98. */
  99. /*
  100. * (C) 2003 Vladimir Oleynik <dzo@simtreas.ru>
  101. *
  102. * - allow access to variable,
  103. * use recursive value indirection: c="2*2"; a="c"; echo $((a+=2)) produce 6
  104. * - implement assign syntax (VAR=expr, +=, *= etc)
  105. * - implement exponentiation (** operator)
  106. * - implement comma separated - expr, expr
  107. * - implement ++expr --expr expr++ expr--
  108. * - implement expr ? expr : expr (but second expr is always calculated)
  109. * - allow hexadecimal and octal numbers
  110. * - restore lost XOR operator
  111. * - protect $((num num)) as true zero expr (Manuel's error)
  112. * - always use special isspace(), see comment from bash ;-)
  113. */
  114. #include "libbb.h"
  115. #include "math.h"
  116. #define lookupvar (math_state->lookupvar)
  117. #define setvar (math_state->setvar )
  118. //#define endofname (math_state->endofname)
  119. typedef unsigned char operator;
  120. /* An operator's token id is a bit of a bitfield. The lower 5 bits are the
  121. * precedence, and 3 high bits are an ID unique across operators of that
  122. * precedence. The ID portion is so that multiple operators can have the
  123. * same precedence, ensuring that the leftmost one is evaluated first.
  124. * Consider * and /
  125. */
  126. #define tok_decl(prec,id) (((id)<<5) | (prec))
  127. #define PREC(op) ((op) & 0x1F)
  128. #define TOK_LPAREN tok_decl(0,0)
  129. #define TOK_COMMA tok_decl(1,0)
  130. /* All assignments are right associative and have the same precedence,
  131. * but there are 11 of them, which doesn't fit into 3 bits for unique id.
  132. * Abusing another precedence level:
  133. */
  134. #define TOK_ASSIGN tok_decl(2,0)
  135. #define TOK_AND_ASSIGN tok_decl(2,1)
  136. #define TOK_OR_ASSIGN tok_decl(2,2)
  137. #define TOK_XOR_ASSIGN tok_decl(2,3)
  138. #define TOK_PLUS_ASSIGN tok_decl(2,4)
  139. #define TOK_MINUS_ASSIGN tok_decl(2,5)
  140. #define TOK_LSHIFT_ASSIGN tok_decl(2,6)
  141. #define TOK_RSHIFT_ASSIGN tok_decl(2,7)
  142. #define TOK_MUL_ASSIGN tok_decl(3,0)
  143. #define TOK_DIV_ASSIGN tok_decl(3,1)
  144. #define TOK_REM_ASSIGN tok_decl(3,2)
  145. #define fix_assignment_prec(prec) do { if (prec == 3) prec = 2; } while (0)
  146. /* Ternary conditional operator is right associative too */
  147. #define TOK_CONDITIONAL tok_decl(4,0)
  148. #define TOK_CONDITIONAL_SEP tok_decl(4,1)
  149. #define TOK_OR tok_decl(5,0)
  150. #define TOK_AND tok_decl(6,0)
  151. #define TOK_BOR tok_decl(7,0)
  152. #define TOK_BXOR tok_decl(8,0)
  153. #define TOK_BAND tok_decl(9,0)
  154. #define TOK_EQ tok_decl(10,0)
  155. #define TOK_NE tok_decl(10,1)
  156. #define TOK_LT tok_decl(11,0)
  157. #define TOK_GT tok_decl(11,1)
  158. #define TOK_GE tok_decl(11,2)
  159. #define TOK_LE tok_decl(11,3)
  160. #define TOK_LSHIFT tok_decl(12,0)
  161. #define TOK_RSHIFT tok_decl(12,1)
  162. #define TOK_ADD tok_decl(13,0)
  163. #define TOK_SUB tok_decl(13,1)
  164. #define TOK_MUL tok_decl(14,0)
  165. #define TOK_DIV tok_decl(14,1)
  166. #define TOK_REM tok_decl(14,2)
  167. /* Exponent is right associative */
  168. #define TOK_EXPONENT tok_decl(15,1)
  169. /* Unary operators */
  170. #define UNARYPREC 16
  171. #define TOK_BNOT tok_decl(UNARYPREC,0)
  172. #define TOK_NOT tok_decl(UNARYPREC,1)
  173. #define TOK_UMINUS tok_decl(UNARYPREC+1,0)
  174. #define TOK_UPLUS tok_decl(UNARYPREC+1,1)
  175. #define PREC_PRE (UNARYPREC+2)
  176. #define TOK_PRE_INC tok_decl(PREC_PRE, 0)
  177. #define TOK_PRE_DEC tok_decl(PREC_PRE, 1)
  178. #define PREC_POST (UNARYPREC+3)
  179. #define TOK_POST_INC tok_decl(PREC_POST, 0)
  180. #define TOK_POST_DEC tok_decl(PREC_POST, 1)
  181. #define SPEC_PREC (UNARYPREC+4)
  182. #define TOK_NUM tok_decl(SPEC_PREC, 0)
  183. #define TOK_RPAREN tok_decl(SPEC_PREC, 1)
  184. static int
  185. is_assign_op(operator op)
  186. {
  187. operator prec = PREC(op);
  188. fix_assignment_prec(prec);
  189. return prec == PREC(TOK_ASSIGN)
  190. || prec == PREC_PRE
  191. || prec == PREC_POST;
  192. }
  193. static int
  194. is_right_associative(operator prec)
  195. {
  196. return prec == PREC(TOK_ASSIGN)
  197. || prec == PREC(TOK_EXPONENT)
  198. || prec == PREC(TOK_CONDITIONAL);
  199. }
  200. typedef struct {
  201. arith_t val;
  202. /* We acquire second_val only when "expr1 : expr2" part
  203. * of ternary ?: op is evaluated.
  204. * We treat ?: as two binary ops: (expr ? (expr1 : expr2)).
  205. * ':' produces a new value which has two parts, val and second_val;
  206. * then '?' selects one of them based on its left side.
  207. */
  208. arith_t second_val;
  209. char second_val_present;
  210. /* If NULL then it's just a number, else it's a named variable */
  211. char *var;
  212. } var_or_num_t;
  213. typedef struct remembered_name {
  214. struct remembered_name *next;
  215. const char *var;
  216. } remembered_name;
  217. static arith_t FAST_FUNC
  218. evaluate_string(arith_state_t *math_state, const char *expr);
  219. static const char*
  220. arith_lookup_val(arith_state_t *math_state, var_or_num_t *t)
  221. {
  222. if (t->var) {
  223. const char *p = lookupvar(t->var);
  224. if (p) {
  225. remembered_name *cur;
  226. remembered_name cur_save;
  227. /* did we already see this name?
  228. * testcase: a=b; b=a; echo $((a))
  229. */
  230. for (cur = math_state->list_of_recursed_names; cur; cur = cur->next) {
  231. if (strcmp(cur->var, t->var) == 0) {
  232. /* Yes */
  233. return "expression recursion loop detected";
  234. }
  235. }
  236. /* push current var name */
  237. cur = math_state->list_of_recursed_names;
  238. cur_save.var = t->var;
  239. cur_save.next = cur;
  240. math_state->list_of_recursed_names = &cur_save;
  241. /* recursively evaluate p as expression */
  242. t->val = evaluate_string(math_state, p);
  243. /* pop current var name */
  244. math_state->list_of_recursed_names = cur;
  245. return math_state->errmsg;
  246. }
  247. /* treat undefined var as 0 */
  248. t->val = 0;
  249. }
  250. return 0;
  251. }
  252. /* "Applying" a token means performing it on the top elements on the integer
  253. * stack. For an unary operator it will only change the top element, but a
  254. * binary operator will pop two arguments and push the result */
  255. static NOINLINE const char*
  256. arith_apply(arith_state_t *math_state, operator op, var_or_num_t *numstack, var_or_num_t **numstackptr)
  257. {
  258. #define NUMPTR (*numstackptr)
  259. var_or_num_t *top_of_stack;
  260. arith_t rez;
  261. const char *err;
  262. /* There is no operator that can work without arguments */
  263. if (NUMPTR == numstack)
  264. goto err;
  265. top_of_stack = NUMPTR - 1;
  266. /* Resolve name to value, if needed */
  267. err = arith_lookup_val(math_state, top_of_stack);
  268. if (err)
  269. return err;
  270. rez = top_of_stack->val;
  271. if (op == TOK_UMINUS)
  272. rez = -rez;
  273. else if (op == TOK_NOT)
  274. rez = !rez;
  275. else if (op == TOK_BNOT)
  276. rez = ~rez;
  277. else if (op == TOK_POST_INC || op == TOK_PRE_INC)
  278. rez++;
  279. else if (op == TOK_POST_DEC || op == TOK_PRE_DEC)
  280. rez--;
  281. else if (op != TOK_UPLUS) {
  282. /* Binary operators */
  283. arith_t right_side_val;
  284. char bad_second_val;
  285. /* Binary operators need two arguments */
  286. if (top_of_stack == numstack)
  287. goto err;
  288. /* ...and they pop one */
  289. NUMPTR = top_of_stack; /* this decrements NUMPTR */
  290. bad_second_val = top_of_stack->second_val_present;
  291. if (op == TOK_CONDITIONAL) { /* ? operation */
  292. /* Make next if (...) protect against
  293. * $((expr1 ? expr2)) - that is, missing ": expr" */
  294. bad_second_val = !bad_second_val;
  295. }
  296. if (bad_second_val) {
  297. /* Protect against $((expr <not_?_op> expr1 : expr2)) */
  298. return "malformed ?: operator";
  299. }
  300. top_of_stack--; /* now points to left side */
  301. if (op != TOK_ASSIGN) {
  302. /* Resolve left side value (unless the op is '=') */
  303. err = arith_lookup_val(math_state, top_of_stack);
  304. if (err)
  305. return err;
  306. }
  307. right_side_val = rez;
  308. rez = top_of_stack->val;
  309. if (op == TOK_CONDITIONAL) /* ? operation */
  310. rez = (rez ? right_side_val : top_of_stack[1].second_val);
  311. else if (op == TOK_CONDITIONAL_SEP) { /* : operation */
  312. if (top_of_stack == numstack) {
  313. /* Protect against $((expr : expr)) */
  314. return "malformed ?: operator";
  315. }
  316. top_of_stack->second_val_present = op;
  317. top_of_stack->second_val = right_side_val;
  318. }
  319. else if (op == TOK_BOR || op == TOK_OR_ASSIGN)
  320. rez |= right_side_val;
  321. else if (op == TOK_OR)
  322. rez = right_side_val || rez;
  323. else if (op == TOK_BAND || op == TOK_AND_ASSIGN)
  324. rez &= right_side_val;
  325. else if (op == TOK_BXOR || op == TOK_XOR_ASSIGN)
  326. rez ^= right_side_val;
  327. else if (op == TOK_AND)
  328. rez = rez && right_side_val;
  329. else if (op == TOK_EQ)
  330. rez = (rez == right_side_val);
  331. else if (op == TOK_NE)
  332. rez = (rez != right_side_val);
  333. else if (op == TOK_GE)
  334. rez = (rez >= right_side_val);
  335. else if (op == TOK_RSHIFT || op == TOK_RSHIFT_ASSIGN)
  336. rez >>= right_side_val;
  337. else if (op == TOK_LSHIFT || op == TOK_LSHIFT_ASSIGN)
  338. rez <<= right_side_val;
  339. else if (op == TOK_GT)
  340. rez = (rez > right_side_val);
  341. else if (op == TOK_LT)
  342. rez = (rez < right_side_val);
  343. else if (op == TOK_LE)
  344. rez = (rez <= right_side_val);
  345. else if (op == TOK_MUL || op == TOK_MUL_ASSIGN)
  346. rez *= right_side_val;
  347. else if (op == TOK_ADD || op == TOK_PLUS_ASSIGN)
  348. rez += right_side_val;
  349. else if (op == TOK_SUB || op == TOK_MINUS_ASSIGN)
  350. rez -= right_side_val;
  351. else if (op == TOK_ASSIGN || op == TOK_COMMA)
  352. rez = right_side_val;
  353. else if (op == TOK_EXPONENT) {
  354. arith_t c;
  355. if (right_side_val < 0)
  356. return "exponent less than 0";
  357. c = 1;
  358. while (--right_side_val >= 0)
  359. c *= rez;
  360. rez = c;
  361. }
  362. else if (right_side_val == 0)
  363. return "divide by zero";
  364. else if (op == TOK_DIV || op == TOK_DIV_ASSIGN
  365. || op == TOK_REM || op == TOK_REM_ASSIGN) {
  366. /*
  367. * bash 4.2.45 x86 64bit: SEGV on 'echo $((2**63 / -1))'
  368. *
  369. * MAX_NEGATIVE_INT / -1 = MAX_POSITIVE_INT+1
  370. * and thus is not representable.
  371. * Some CPUs segfault trying such op.
  372. * Others overflow MAX_POSITIVE_INT+1 to
  373. * MAX_NEGATIVE_INT (0x7fff+1 = 0x8000).
  374. * Make sure to at least not SEGV here:
  375. */
  376. if (right_side_val == -1
  377. && rez << 1 == 0 /* MAX_NEGATIVE_INT or 0 */
  378. ) {
  379. right_side_val = 1;
  380. }
  381. if (op == TOK_DIV || op == TOK_DIV_ASSIGN)
  382. rez /= right_side_val;
  383. else {
  384. rez %= right_side_val;
  385. }
  386. }
  387. }
  388. if (is_assign_op(op)) {
  389. char buf[sizeof(arith_t)*3 + 2];
  390. if (top_of_stack->var == NULL) {
  391. /* Hmm, 1=2 ? */
  392. //TODO: actually, bash allows ++7 but for some reason it evals to 7, not 8
  393. goto err;
  394. }
  395. /* Save to shell variable */
  396. sprintf(buf, ARITH_FMT, rez);
  397. setvar(top_of_stack->var, buf);
  398. /* After saving, make previous value for v++ or v-- */
  399. if (op == TOK_POST_INC)
  400. rez--;
  401. else if (op == TOK_POST_DEC)
  402. rez++;
  403. }
  404. top_of_stack->val = rez;
  405. /* Erase var name, it is just a number now */
  406. top_of_stack->var = NULL;
  407. return NULL;
  408. err:
  409. return "arithmetic syntax error";
  410. #undef NUMPTR
  411. }
  412. /* longest must be first */
  413. static const char op_tokens[] ALIGN1 = {
  414. '<','<','=',0, TOK_LSHIFT_ASSIGN,
  415. '>','>','=',0, TOK_RSHIFT_ASSIGN,
  416. '<','<', 0, TOK_LSHIFT,
  417. '>','>', 0, TOK_RSHIFT,
  418. '|','|', 0, TOK_OR,
  419. '&','&', 0, TOK_AND,
  420. '!','=', 0, TOK_NE,
  421. '<','=', 0, TOK_LE,
  422. '>','=', 0, TOK_GE,
  423. '=','=', 0, TOK_EQ,
  424. '|','=', 0, TOK_OR_ASSIGN,
  425. '&','=', 0, TOK_AND_ASSIGN,
  426. '*','=', 0, TOK_MUL_ASSIGN,
  427. '/','=', 0, TOK_DIV_ASSIGN,
  428. '%','=', 0, TOK_REM_ASSIGN,
  429. '+','=', 0, TOK_PLUS_ASSIGN,
  430. '-','=', 0, TOK_MINUS_ASSIGN,
  431. '-','-', 0, TOK_POST_DEC,
  432. '^','=', 0, TOK_XOR_ASSIGN,
  433. '+','+', 0, TOK_POST_INC,
  434. '*','*', 0, TOK_EXPONENT,
  435. '!', 0, TOK_NOT,
  436. '<', 0, TOK_LT,
  437. '>', 0, TOK_GT,
  438. '=', 0, TOK_ASSIGN,
  439. '|', 0, TOK_BOR,
  440. '&', 0, TOK_BAND,
  441. '*', 0, TOK_MUL,
  442. '/', 0, TOK_DIV,
  443. '%', 0, TOK_REM,
  444. '+', 0, TOK_ADD,
  445. '-', 0, TOK_SUB,
  446. '^', 0, TOK_BXOR,
  447. /* uniq */
  448. '~', 0, TOK_BNOT,
  449. ',', 0, TOK_COMMA,
  450. '?', 0, TOK_CONDITIONAL,
  451. ':', 0, TOK_CONDITIONAL_SEP,
  452. ')', 0, TOK_RPAREN,
  453. '(', 0, TOK_LPAREN,
  454. 0
  455. };
  456. #define ptr_to_rparen (&op_tokens[sizeof(op_tokens)-7])
  457. static arith_t FAST_FUNC
  458. evaluate_string(arith_state_t *math_state, const char *expr)
  459. {
  460. operator lasttok;
  461. const char *errmsg;
  462. const char *start_expr = expr = skip_whitespace(expr);
  463. unsigned expr_len = strlen(expr) + 2;
  464. /* Stack of integers */
  465. /* The proof that there can be no more than strlen(startbuf)/2+1
  466. * integers in any given correct or incorrect expression
  467. * is left as an exercise to the reader. */
  468. var_or_num_t *const numstack = alloca((expr_len / 2) * sizeof(numstack[0]));
  469. var_or_num_t *numstackptr = numstack;
  470. /* Stack of operator tokens */
  471. operator *const stack = alloca(expr_len * sizeof(stack[0]));
  472. operator *stackptr = stack;
  473. /* Start with a left paren */
  474. *stackptr++ = lasttok = TOK_LPAREN;
  475. errmsg = NULL;
  476. while (1) {
  477. const char *p;
  478. operator op;
  479. operator prec;
  480. char arithval;
  481. expr = skip_whitespace(expr);
  482. arithval = *expr;
  483. if (arithval == '\0') {
  484. if (expr == start_expr) {
  485. /* Null expression */
  486. numstack->val = 0;
  487. goto ret;
  488. }
  489. /* This is only reached after all tokens have been extracted from the
  490. * input stream. If there are still tokens on the operator stack, they
  491. * are to be applied in order. At the end, there should be a final
  492. * result on the integer stack */
  493. if (expr != ptr_to_rparen + 1) {
  494. /* If we haven't done so already,
  495. * append a closing right paren
  496. * and let the loop process it */
  497. expr = ptr_to_rparen;
  498. continue;
  499. }
  500. /* At this point, we're done with the expression */
  501. if (numstackptr != numstack + 1) {
  502. /* ...but if there isn't, it's bad */
  503. goto err;
  504. }
  505. if (numstack->var) {
  506. /* expression is $((var)) only, lookup now */
  507. errmsg = arith_lookup_val(math_state, numstack);
  508. }
  509. goto ret;
  510. }
  511. p = endofname(expr);
  512. if (p != expr) {
  513. /* Name */
  514. size_t var_name_size = (p-expr) + 1; /* +1 for NUL */
  515. numstackptr->var = alloca(var_name_size);
  516. safe_strncpy(numstackptr->var, expr, var_name_size);
  517. expr = p;
  518. num:
  519. numstackptr->second_val_present = 0;
  520. numstackptr++;
  521. lasttok = TOK_NUM;
  522. continue;
  523. }
  524. if (isdigit(arithval)) {
  525. /* Number */
  526. numstackptr->var = NULL;
  527. errno = 0;
  528. numstackptr->val = strto_arith_t(expr, (char**) &expr, 0);
  529. if (errno)
  530. numstackptr->val = 0; /* bash compat */
  531. goto num;
  532. }
  533. /* Should be an operator */
  534. /* Special case: NUM-- and NUM++ are not recognized if NUM
  535. * is a literal number, not a variable. IOW:
  536. * "a+++v" is a++ + v.
  537. * "7+++v" is 7 + ++v, not 7++ + v.
  538. */
  539. if (lasttok == TOK_NUM && !numstackptr[-1].var /* number literal */
  540. && (expr[0] == '+' || expr[0] == '-')
  541. && (expr[1] == expr[0])
  542. ) {
  543. //bb_error_msg("special %c%c", expr[0], expr[0]);
  544. op = (expr[0] == '+' ? TOK_ADD : TOK_SUB);
  545. expr += 1;
  546. goto tok_found1;
  547. }
  548. p = op_tokens;
  549. while (1) {
  550. /* Compare expr to current op_tokens[] element */
  551. const char *e = expr;
  552. while (1) {
  553. if (*p == '\0') {
  554. /* Match: operator is found */
  555. expr = e;
  556. goto tok_found;
  557. }
  558. if (*p != *e)
  559. break;
  560. p++;
  561. e++;
  562. }
  563. /* No match, go to next element of op_tokens[] */
  564. while (*p)
  565. p++;
  566. p += 2; /* skip NUL and TOK_foo bytes */
  567. if (*p == '\0') {
  568. /* No next element, operator not found */
  569. //math_state->syntax_error_at = expr;
  570. goto err;
  571. }
  572. }
  573. tok_found:
  574. op = p[1]; /* fetch TOK_foo value */
  575. tok_found1:
  576. /* NB: expr now points past the operator */
  577. /* post grammar: a++ reduce to num */
  578. if (lasttok == TOK_POST_INC || lasttok == TOK_POST_DEC)
  579. lasttok = TOK_NUM;
  580. /* Plus and minus are binary (not unary) _only_ if the last
  581. * token was a number, or a right paren (which pretends to be
  582. * a number, since it evaluates to one). Think about it.
  583. * It makes sense. */
  584. if (lasttok != TOK_NUM) {
  585. switch (op) {
  586. case TOK_ADD:
  587. op = TOK_UPLUS;
  588. break;
  589. case TOK_SUB:
  590. op = TOK_UMINUS;
  591. break;
  592. case TOK_POST_INC:
  593. op = TOK_PRE_INC;
  594. break;
  595. case TOK_POST_DEC:
  596. op = TOK_PRE_DEC;
  597. break;
  598. }
  599. }
  600. /* We don't want an unary operator to cause recursive descent on the
  601. * stack, because there can be many in a row and it could cause an
  602. * operator to be evaluated before its argument is pushed onto the
  603. * integer stack.
  604. * But for binary operators, "apply" everything on the operator
  605. * stack until we find an operator with a lesser priority than the
  606. * one we have just extracted. If op is right-associative,
  607. * then stop "applying" on the equal priority too.
  608. * Left paren is given the lowest priority so it will never be
  609. * "applied" in this way.
  610. */
  611. prec = PREC(op);
  612. if ((prec > 0 && prec < UNARYPREC) || prec == SPEC_PREC) {
  613. /* not left paren or unary */
  614. if (lasttok != TOK_NUM) {
  615. /* binary op must be preceded by a num */
  616. goto err;
  617. }
  618. while (stackptr != stack) {
  619. operator prev_op = *--stackptr;
  620. if (op == TOK_RPAREN) {
  621. /* The algorithm employed here is simple: while we don't
  622. * hit an open paren nor the bottom of the stack, pop
  623. * tokens and apply them */
  624. if (prev_op == TOK_LPAREN) {
  625. /* Any operator directly after a
  626. * close paren should consider itself binary */
  627. lasttok = TOK_NUM;
  628. goto next;
  629. }
  630. } else {
  631. operator prev_prec = PREC(prev_op);
  632. fix_assignment_prec(prec);
  633. fix_assignment_prec(prev_prec);
  634. if (prev_prec < prec
  635. || (prev_prec == prec && is_right_associative(prec))
  636. ) {
  637. stackptr++;
  638. break;
  639. }
  640. }
  641. errmsg = arith_apply(math_state, prev_op, numstack, &numstackptr);
  642. if (errmsg)
  643. goto err_with_custom_msg;
  644. }
  645. if (op == TOK_RPAREN)
  646. goto err;
  647. }
  648. /* Push this operator to the stack and remember it */
  649. *stackptr++ = lasttok = op;
  650. next: ;
  651. } /* while (1) */
  652. err:
  653. errmsg = "arithmetic syntax error";
  654. err_with_custom_msg:
  655. numstack->val = -1;
  656. ret:
  657. math_state->errmsg = errmsg;
  658. return numstack->val;
  659. }
  660. arith_t FAST_FUNC
  661. arith(arith_state_t *math_state, const char *expr)
  662. {
  663. math_state->errmsg = NULL;
  664. math_state->list_of_recursed_names = NULL;
  665. return evaluate_string(math_state, expr);
  666. }
  667. /*
  668. * Copyright (c) 1989, 1991, 1993, 1994
  669. * The Regents of the University of California. All rights reserved.
  670. *
  671. * This code is derived from software contributed to Berkeley by
  672. * Kenneth Almquist.
  673. *
  674. * Redistribution and use in source and binary forms, with or without
  675. * modification, are permitted provided that the following conditions
  676. * are met:
  677. * 1. Redistributions of source code must retain the above copyright
  678. * notice, this list of conditions and the following disclaimer.
  679. * 2. Redistributions in binary form must reproduce the above copyright
  680. * notice, this list of conditions and the following disclaimer in the
  681. * documentation and/or other materials provided with the distribution.
  682. * 3. Neither the name of the University nor the names of its contributors
  683. * may be used to endorse or promote products derived from this software
  684. * without specific prior written permission.
  685. *
  686. * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ''AS IS'' AND
  687. * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  688. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  689. * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  690. * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  691. * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  692. * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  693. * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  694. * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  695. * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  696. * SUCH DAMAGE.
  697. */