Contents of /trunk/mkinitrd-magellan/busybox/shell/math.c
Parent Directory | Revision Log
Revision 984 -
(show annotations)
(download)
Sun May 30 11:32:42 2010 UTC (14 years, 4 months ago) by niro
File MIME type: text/plain
File size: 21625 byte(s)
Sun May 30 11:32:42 2010 UTC (14 years, 4 months ago) by niro
File MIME type: text/plain
File size: 21625 byte(s)
-updated to busybox-1.16.1 and enabled blkid/uuid support in default config
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 the GPL v2 or later, see the file LICENSE in this tarball. |
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 | |
50 | /* This is my infix parser/evaluator. It is optimized for size, intended |
51 | * as a replacement for yacc-based parsers. However, it may well be faster |
52 | * than a comparable parser written in yacc. The supported operators are |
53 | * listed in #defines below. Parens, order of operations, and error handling |
54 | * are supported. This code is thread safe. The exact expression format should |
55 | * be that which POSIX specifies for shells. */ |
56 | |
57 | /* The code uses a simple two-stack algorithm. See |
58 | * http://www.onthenet.com.au/~grahamis/int2008/week02/lect02.html |
59 | * for a detailed explanation of the infix-to-postfix algorithm on which |
60 | * this is based (this code differs in that it applies operators immediately |
61 | * to the stack instead of adding them to a queue to end up with an |
62 | * expression). */ |
63 | |
64 | /* To use the routine, call it with an expression string and error return |
65 | * pointer */ |
66 | |
67 | /* |
68 | * Aug 24, 2001 Manuel Novoa III |
69 | * |
70 | * Reduced the generated code size by about 30% (i386) and fixed several bugs. |
71 | * |
72 | * 1) In arith_apply(): |
73 | * a) Cached values of *numptr and &(numptr[-1]). |
74 | * b) Removed redundant test for zero denominator. |
75 | * |
76 | * 2) In arith(): |
77 | * a) Eliminated redundant code for processing operator tokens by moving |
78 | * to a table-based implementation. Also folded handling of parens |
79 | * into the table. |
80 | * b) Combined all 3 loops which called arith_apply to reduce generated |
81 | * code size at the cost of speed. |
82 | * |
83 | * 3) The following expressions were treated as valid by the original code: |
84 | * 1() , 0! , 1 ( *3 ) . |
85 | * These bugs have been fixed by internally enclosing the expression in |
86 | * parens and then checking that all binary ops and right parens are |
87 | * preceded by a valid expression (NUM_TOKEN). |
88 | * |
89 | * Note: It may be desirable to replace Aaron's test for whitespace with |
90 | * ctype's isspace() if it is used by another busybox applet or if additional |
91 | * whitespace chars should be considered. Look below the "#include"s for a |
92 | * precompiler test. |
93 | */ |
94 | /* |
95 | * Aug 26, 2001 Manuel Novoa III |
96 | * |
97 | * Return 0 for null expressions. Pointed out by Vladimir Oleynik. |
98 | * |
99 | * Merge in Aaron's comments previously posted to the busybox list, |
100 | * modified slightly to take account of my changes to the code. |
101 | * |
102 | */ |
103 | /* |
104 | * (C) 2003 Vladimir Oleynik <dzo@simtreas.ru> |
105 | * |
106 | * - allow access to variable, |
107 | * used recursive find value indirection (c=2*2; a="c"; $((a+=2)) produce 6) |
108 | * - realize assign syntax (VAR=expr, +=, *= etc) |
109 | * - realize exponentiation (** operator) |
110 | * - realize comma separated - expr, expr |
111 | * - realise ++expr --expr expr++ expr-- |
112 | * - realise expr ? expr : expr (but, second expr calculate always) |
113 | * - allow hexadecimal and octal numbers |
114 | * - was restored loses XOR operator |
115 | * - remove one goto label, added three ;-) |
116 | * - protect $((num num)) as true zero expr (Manuel`s error) |
117 | * - always use special isspace(), see comment from bash ;-) |
118 | */ |
119 | #include "libbb.h" |
120 | #include "math.h" |
121 | |
122 | #define a_e_h_t arith_eval_hooks_t |
123 | #define lookupvar (math_hooks->lookupvar) |
124 | #define setvar (math_hooks->setvar ) |
125 | #define endofname (math_hooks->endofname) |
126 | |
127 | #define arith_isspace(arithval) \ |
128 | (arithval == ' ' || arithval == '\n' || arithval == '\t') |
129 | |
130 | typedef unsigned char operator; |
131 | |
132 | /* An operator's token id is a bit of a bitfield. The lower 5 bits are the |
133 | * precedence, and 3 high bits are an ID unique across operators of that |
134 | * precedence. The ID portion is so that multiple operators can have the |
135 | * same precedence, ensuring that the leftmost one is evaluated first. |
136 | * Consider * and /. */ |
137 | |
138 | #define tok_decl(prec,id) (((id)<<5)|(prec)) |
139 | #define PREC(op) ((op) & 0x1F) |
140 | |
141 | #define TOK_LPAREN tok_decl(0,0) |
142 | |
143 | #define TOK_COMMA tok_decl(1,0) |
144 | |
145 | #define TOK_ASSIGN tok_decl(2,0) |
146 | #define TOK_AND_ASSIGN tok_decl(2,1) |
147 | #define TOK_OR_ASSIGN tok_decl(2,2) |
148 | #define TOK_XOR_ASSIGN tok_decl(2,3) |
149 | #define TOK_PLUS_ASSIGN tok_decl(2,4) |
150 | #define TOK_MINUS_ASSIGN tok_decl(2,5) |
151 | #define TOK_LSHIFT_ASSIGN tok_decl(2,6) |
152 | #define TOK_RSHIFT_ASSIGN tok_decl(2,7) |
153 | |
154 | #define TOK_MUL_ASSIGN tok_decl(3,0) |
155 | #define TOK_DIV_ASSIGN tok_decl(3,1) |
156 | #define TOK_REM_ASSIGN tok_decl(3,2) |
157 | |
158 | /* all assign is right associativity and precedence eq, but (7+3)<<5 > 256 */ |
159 | #define convert_prec_is_assing(prec) do { if (prec == 3) prec = 2; } while (0) |
160 | |
161 | /* conditional is right associativity too */ |
162 | #define TOK_CONDITIONAL tok_decl(4,0) |
163 | #define TOK_CONDITIONAL_SEP tok_decl(4,1) |
164 | |
165 | #define TOK_OR tok_decl(5,0) |
166 | |
167 | #define TOK_AND tok_decl(6,0) |
168 | |
169 | #define TOK_BOR tok_decl(7,0) |
170 | |
171 | #define TOK_BXOR tok_decl(8,0) |
172 | |
173 | #define TOK_BAND tok_decl(9,0) |
174 | |
175 | #define TOK_EQ tok_decl(10,0) |
176 | #define TOK_NE tok_decl(10,1) |
177 | |
178 | #define TOK_LT tok_decl(11,0) |
179 | #define TOK_GT tok_decl(11,1) |
180 | #define TOK_GE tok_decl(11,2) |
181 | #define TOK_LE tok_decl(11,3) |
182 | |
183 | #define TOK_LSHIFT tok_decl(12,0) |
184 | #define TOK_RSHIFT tok_decl(12,1) |
185 | |
186 | #define TOK_ADD tok_decl(13,0) |
187 | #define TOK_SUB tok_decl(13,1) |
188 | |
189 | #define TOK_MUL tok_decl(14,0) |
190 | #define TOK_DIV tok_decl(14,1) |
191 | #define TOK_REM tok_decl(14,2) |
192 | |
193 | /* exponent is right associativity */ |
194 | #define TOK_EXPONENT tok_decl(15,1) |
195 | |
196 | /* For now unary operators. */ |
197 | #define UNARYPREC 16 |
198 | #define TOK_BNOT tok_decl(UNARYPREC,0) |
199 | #define TOK_NOT tok_decl(UNARYPREC,1) |
200 | |
201 | #define TOK_UMINUS tok_decl(UNARYPREC+1,0) |
202 | #define TOK_UPLUS tok_decl(UNARYPREC+1,1) |
203 | |
204 | #define PREC_PRE (UNARYPREC+2) |
205 | |
206 | #define TOK_PRE_INC tok_decl(PREC_PRE, 0) |
207 | #define TOK_PRE_DEC tok_decl(PREC_PRE, 1) |
208 | |
209 | #define PREC_POST (UNARYPREC+3) |
210 | |
211 | #define TOK_POST_INC tok_decl(PREC_POST, 0) |
212 | #define TOK_POST_DEC tok_decl(PREC_POST, 1) |
213 | |
214 | #define SPEC_PREC (UNARYPREC+4) |
215 | |
216 | #define TOK_NUM tok_decl(SPEC_PREC, 0) |
217 | #define TOK_RPAREN tok_decl(SPEC_PREC, 1) |
218 | |
219 | #define NUMPTR (*numstackptr) |
220 | |
221 | static int |
222 | tok_have_assign(operator op) |
223 | { |
224 | operator prec = PREC(op); |
225 | |
226 | convert_prec_is_assing(prec); |
227 | return (prec == PREC(TOK_ASSIGN) || |
228 | prec == PREC_PRE || prec == PREC_POST); |
229 | } |
230 | |
231 | static int |
232 | is_right_associativity(operator prec) |
233 | { |
234 | return (prec == PREC(TOK_ASSIGN) || prec == PREC(TOK_EXPONENT) |
235 | || prec == PREC(TOK_CONDITIONAL)); |
236 | } |
237 | |
238 | typedef struct { |
239 | arith_t val; |
240 | arith_t contidional_second_val; |
241 | char contidional_second_val_initialized; |
242 | char *var; /* if NULL then is regular number, |
243 | else is variable name */ |
244 | } v_n_t; |
245 | |
246 | typedef struct chk_var_recursive_looped_t { |
247 | const char *var; |
248 | struct chk_var_recursive_looped_t *next; |
249 | } chk_var_recursive_looped_t; |
250 | |
251 | static chk_var_recursive_looped_t *prev_chk_var_recursive; |
252 | |
253 | static int |
254 | arith_lookup_val(v_n_t *t, a_e_h_t *math_hooks) |
255 | { |
256 | if (t->var) { |
257 | const char *p = lookupvar(t->var); |
258 | |
259 | if (p) { |
260 | int errcode; |
261 | |
262 | /* recursive try as expression */ |
263 | chk_var_recursive_looped_t *cur; |
264 | chk_var_recursive_looped_t cur_save; |
265 | |
266 | for (cur = prev_chk_var_recursive; cur; cur = cur->next) { |
267 | if (strcmp(cur->var, t->var) == 0) { |
268 | /* expression recursion loop detected */ |
269 | return -5; |
270 | } |
271 | } |
272 | /* save current lookuped var name */ |
273 | cur = prev_chk_var_recursive; |
274 | cur_save.var = t->var; |
275 | cur_save.next = cur; |
276 | prev_chk_var_recursive = &cur_save; |
277 | |
278 | t->val = arith (p, &errcode, math_hooks); |
279 | /* restore previous ptr after recursiving */ |
280 | prev_chk_var_recursive = cur; |
281 | return errcode; |
282 | } |
283 | /* allow undefined var as 0 */ |
284 | t->val = 0; |
285 | } |
286 | return 0; |
287 | } |
288 | |
289 | /* "applying" a token means performing it on the top elements on the integer |
290 | * stack. For a unary operator it will only change the top element, but a |
291 | * binary operator will pop two arguments and push a result */ |
292 | static NOINLINE int |
293 | arith_apply(operator op, v_n_t *numstack, v_n_t **numstackptr, a_e_h_t *math_hooks) |
294 | { |
295 | v_n_t *numptr_m1; |
296 | arith_t numptr_val, rez; |
297 | int ret_arith_lookup_val; |
298 | |
299 | /* There is no operator that can work without arguments */ |
300 | if (NUMPTR == numstack) goto err; |
301 | numptr_m1 = NUMPTR - 1; |
302 | |
303 | /* check operand is var with noninteger value */ |
304 | ret_arith_lookup_val = arith_lookup_val(numptr_m1, math_hooks); |
305 | if (ret_arith_lookup_val) |
306 | return ret_arith_lookup_val; |
307 | |
308 | rez = numptr_m1->val; |
309 | if (op == TOK_UMINUS) |
310 | rez *= -1; |
311 | else if (op == TOK_NOT) |
312 | rez = !rez; |
313 | else if (op == TOK_BNOT) |
314 | rez = ~rez; |
315 | else if (op == TOK_POST_INC || op == TOK_PRE_INC) |
316 | rez++; |
317 | else if (op == TOK_POST_DEC || op == TOK_PRE_DEC) |
318 | rez--; |
319 | else if (op != TOK_UPLUS) { |
320 | /* Binary operators */ |
321 | |
322 | /* check and binary operators need two arguments */ |
323 | if (numptr_m1 == numstack) goto err; |
324 | |
325 | /* ... and they pop one */ |
326 | --NUMPTR; |
327 | numptr_val = rez; |
328 | if (op == TOK_CONDITIONAL) { |
329 | if (!numptr_m1->contidional_second_val_initialized) { |
330 | /* protect $((expr1 ? expr2)) without ": expr" */ |
331 | goto err; |
332 | } |
333 | rez = numptr_m1->contidional_second_val; |
334 | } else if (numptr_m1->contidional_second_val_initialized) { |
335 | /* protect $((expr1 : expr2)) without "expr ? " */ |
336 | goto err; |
337 | } |
338 | numptr_m1 = NUMPTR - 1; |
339 | if (op != TOK_ASSIGN) { |
340 | /* check operand is var with noninteger value for not '=' */ |
341 | ret_arith_lookup_val = arith_lookup_val(numptr_m1, math_hooks); |
342 | if (ret_arith_lookup_val) |
343 | return ret_arith_lookup_val; |
344 | } |
345 | if (op == TOK_CONDITIONAL) { |
346 | numptr_m1->contidional_second_val = rez; |
347 | } |
348 | rez = numptr_m1->val; |
349 | if (op == TOK_BOR || op == TOK_OR_ASSIGN) |
350 | rez |= numptr_val; |
351 | else if (op == TOK_OR) |
352 | rez = numptr_val || rez; |
353 | else if (op == TOK_BAND || op == TOK_AND_ASSIGN) |
354 | rez &= numptr_val; |
355 | else if (op == TOK_BXOR || op == TOK_XOR_ASSIGN) |
356 | rez ^= numptr_val; |
357 | else if (op == TOK_AND) |
358 | rez = rez && numptr_val; |
359 | else if (op == TOK_EQ) |
360 | rez = (rez == numptr_val); |
361 | else if (op == TOK_NE) |
362 | rez = (rez != numptr_val); |
363 | else if (op == TOK_GE) |
364 | rez = (rez >= numptr_val); |
365 | else if (op == TOK_RSHIFT || op == TOK_RSHIFT_ASSIGN) |
366 | rez >>= numptr_val; |
367 | else if (op == TOK_LSHIFT || op == TOK_LSHIFT_ASSIGN) |
368 | rez <<= numptr_val; |
369 | else if (op == TOK_GT) |
370 | rez = (rez > numptr_val); |
371 | else if (op == TOK_LT) |
372 | rez = (rez < numptr_val); |
373 | else if (op == TOK_LE) |
374 | rez = (rez <= numptr_val); |
375 | else if (op == TOK_MUL || op == TOK_MUL_ASSIGN) |
376 | rez *= numptr_val; |
377 | else if (op == TOK_ADD || op == TOK_PLUS_ASSIGN) |
378 | rez += numptr_val; |
379 | else if (op == TOK_SUB || op == TOK_MINUS_ASSIGN) |
380 | rez -= numptr_val; |
381 | else if (op == TOK_ASSIGN || op == TOK_COMMA) |
382 | rez = numptr_val; |
383 | else if (op == TOK_CONDITIONAL_SEP) { |
384 | if (numptr_m1 == numstack) { |
385 | /* protect $((expr : expr)) without "expr ? " */ |
386 | goto err; |
387 | } |
388 | numptr_m1->contidional_second_val_initialized = op; |
389 | numptr_m1->contidional_second_val = numptr_val; |
390 | } else if (op == TOK_CONDITIONAL) { |
391 | rez = rez ? |
392 | numptr_val : numptr_m1->contidional_second_val; |
393 | } else if (op == TOK_EXPONENT) { |
394 | if (numptr_val < 0) |
395 | return -3; /* exponent less than 0 */ |
396 | else { |
397 | arith_t c = 1; |
398 | |
399 | if (numptr_val) |
400 | while (numptr_val--) |
401 | c *= rez; |
402 | rez = c; |
403 | } |
404 | } else if (numptr_val==0) /* zero divisor check */ |
405 | return -2; |
406 | else if (op == TOK_DIV || op == TOK_DIV_ASSIGN) |
407 | rez /= numptr_val; |
408 | else if (op == TOK_REM || op == TOK_REM_ASSIGN) |
409 | rez %= numptr_val; |
410 | } |
411 | if (tok_have_assign(op)) { |
412 | char buf[sizeof(arith_t)*3 + 2]; |
413 | |
414 | if (numptr_m1->var == NULL) { |
415 | /* Hmm, 1=2 ? */ |
416 | goto err; |
417 | } |
418 | /* save to shell variable */ |
419 | sprintf(buf, arith_t_fmt, rez); |
420 | setvar(numptr_m1->var, buf); |
421 | /* after saving, make previous value for v++ or v-- */ |
422 | if (op == TOK_POST_INC) |
423 | rez--; |
424 | else if (op == TOK_POST_DEC) |
425 | rez++; |
426 | } |
427 | numptr_m1->val = rez; |
428 | /* protect geting var value, is number now */ |
429 | numptr_m1->var = NULL; |
430 | return 0; |
431 | err: |
432 | return -1; |
433 | } |
434 | |
435 | /* longest must be first */ |
436 | static const char op_tokens[] ALIGN1 = { |
437 | '<','<','=',0, TOK_LSHIFT_ASSIGN, |
438 | '>','>','=',0, TOK_RSHIFT_ASSIGN, |
439 | '<','<', 0, TOK_LSHIFT, |
440 | '>','>', 0, TOK_RSHIFT, |
441 | '|','|', 0, TOK_OR, |
442 | '&','&', 0, TOK_AND, |
443 | '!','=', 0, TOK_NE, |
444 | '<','=', 0, TOK_LE, |
445 | '>','=', 0, TOK_GE, |
446 | '=','=', 0, TOK_EQ, |
447 | '|','=', 0, TOK_OR_ASSIGN, |
448 | '&','=', 0, TOK_AND_ASSIGN, |
449 | '*','=', 0, TOK_MUL_ASSIGN, |
450 | '/','=', 0, TOK_DIV_ASSIGN, |
451 | '%','=', 0, TOK_REM_ASSIGN, |
452 | '+','=', 0, TOK_PLUS_ASSIGN, |
453 | '-','=', 0, TOK_MINUS_ASSIGN, |
454 | '-','-', 0, TOK_POST_DEC, |
455 | '^','=', 0, TOK_XOR_ASSIGN, |
456 | '+','+', 0, TOK_POST_INC, |
457 | '*','*', 0, TOK_EXPONENT, |
458 | '!', 0, TOK_NOT, |
459 | '<', 0, TOK_LT, |
460 | '>', 0, TOK_GT, |
461 | '=', 0, TOK_ASSIGN, |
462 | '|', 0, TOK_BOR, |
463 | '&', 0, TOK_BAND, |
464 | '*', 0, TOK_MUL, |
465 | '/', 0, TOK_DIV, |
466 | '%', 0, TOK_REM, |
467 | '+', 0, TOK_ADD, |
468 | '-', 0, TOK_SUB, |
469 | '^', 0, TOK_BXOR, |
470 | /* uniq */ |
471 | '~', 0, TOK_BNOT, |
472 | ',', 0, TOK_COMMA, |
473 | '?', 0, TOK_CONDITIONAL, |
474 | ':', 0, TOK_CONDITIONAL_SEP, |
475 | ')', 0, TOK_RPAREN, |
476 | '(', 0, TOK_LPAREN, |
477 | 0 |
478 | }; |
479 | /* ptr to ")" */ |
480 | #define endexpression (&op_tokens[sizeof(op_tokens)-7]) |
481 | |
482 | arith_t |
483 | arith(const char *expr, int *perrcode, a_e_h_t *math_hooks) |
484 | { |
485 | char arithval; /* Current character under analysis */ |
486 | operator lasttok, op; |
487 | operator prec; |
488 | operator *stack, *stackptr; |
489 | const char *p = endexpression; |
490 | int errcode; |
491 | v_n_t *numstack, *numstackptr; |
492 | unsigned datasizes = strlen(expr) + 2; |
493 | |
494 | /* Stack of integers */ |
495 | /* The proof that there can be no more than strlen(startbuf)/2+1 integers |
496 | * in any given correct or incorrect expression is left as an exercise to |
497 | * the reader. */ |
498 | numstackptr = numstack = alloca((datasizes / 2) * sizeof(numstack[0])); |
499 | /* Stack of operator tokens */ |
500 | stackptr = stack = alloca(datasizes * sizeof(stack[0])); |
501 | |
502 | *stackptr++ = lasttok = TOK_LPAREN; /* start off with a left paren */ |
503 | *perrcode = errcode = 0; |
504 | |
505 | while (1) { |
506 | arithval = *expr; |
507 | if (arithval == 0) { |
508 | if (p == endexpression) { |
509 | /* Null expression. */ |
510 | return 0; |
511 | } |
512 | |
513 | /* This is only reached after all tokens have been extracted from the |
514 | * input stream. If there are still tokens on the operator stack, they |
515 | * are to be applied in order. At the end, there should be a final |
516 | * result on the integer stack */ |
517 | |
518 | if (expr != endexpression + 1) { |
519 | /* If we haven't done so already, */ |
520 | /* append a closing right paren */ |
521 | expr = endexpression; |
522 | /* and let the loop process it. */ |
523 | continue; |
524 | } |
525 | /* At this point, we're done with the expression. */ |
526 | if (numstackptr != numstack+1) { |
527 | /* ... but if there isn't, it's bad */ |
528 | err: |
529 | *perrcode = -1; |
530 | return *perrcode; |
531 | } |
532 | if (numstack->var) { |
533 | /* expression is $((var)) only, lookup now */ |
534 | errcode = arith_lookup_val(numstack, math_hooks); |
535 | } |
536 | ret: |
537 | *perrcode = errcode; |
538 | return numstack->val; |
539 | } |
540 | |
541 | /* Continue processing the expression. */ |
542 | if (arith_isspace(arithval)) { |
543 | /* Skip whitespace */ |
544 | goto prologue; |
545 | } |
546 | p = endofname(expr); |
547 | if (p != expr) { |
548 | size_t var_name_size = (p-expr) + 1; /* trailing zero */ |
549 | |
550 | numstackptr->var = alloca(var_name_size); |
551 | safe_strncpy(numstackptr->var, expr, var_name_size); |
552 | expr = p; |
553 | num: |
554 | numstackptr->contidional_second_val_initialized = 0; |
555 | numstackptr++; |
556 | lasttok = TOK_NUM; |
557 | continue; |
558 | } |
559 | if (isdigit(arithval)) { |
560 | numstackptr->var = NULL; |
561 | errno = 0; |
562 | /* call strtoul[l]: */ |
563 | numstackptr->val = strto_arith_t(expr, (char **) &expr, 0); |
564 | if (errno) |
565 | numstackptr->val = 0; /* bash compat */ |
566 | goto num; |
567 | } |
568 | for (p = op_tokens; ; p++) { |
569 | const char *o; |
570 | |
571 | if (*p == 0) { |
572 | /* strange operator not found */ |
573 | goto err; |
574 | } |
575 | for (o = expr; *p && *o == *p; p++) |
576 | o++; |
577 | if (!*p) { |
578 | /* found */ |
579 | expr = o - 1; |
580 | break; |
581 | } |
582 | /* skip tail uncompared token */ |
583 | while (*p) |
584 | p++; |
585 | /* skip zero delim */ |
586 | p++; |
587 | } |
588 | op = p[1]; |
589 | |
590 | /* post grammar: a++ reduce to num */ |
591 | if (lasttok == TOK_POST_INC || lasttok == TOK_POST_DEC) |
592 | lasttok = TOK_NUM; |
593 | |
594 | /* Plus and minus are binary (not unary) _only_ if the last |
595 | * token was a number, or a right paren (which pretends to be |
596 | * a number, since it evaluates to one). Think about it. |
597 | * It makes sense. */ |
598 | if (lasttok != TOK_NUM) { |
599 | switch (op) { |
600 | case TOK_ADD: |
601 | op = TOK_UPLUS; |
602 | break; |
603 | case TOK_SUB: |
604 | op = TOK_UMINUS; |
605 | break; |
606 | case TOK_POST_INC: |
607 | op = TOK_PRE_INC; |
608 | break; |
609 | case TOK_POST_DEC: |
610 | op = TOK_PRE_DEC; |
611 | break; |
612 | } |
613 | } |
614 | /* We don't want an unary operator to cause recursive descent on the |
615 | * stack, because there can be many in a row and it could cause an |
616 | * operator to be evaluated before its argument is pushed onto the |
617 | * integer stack. */ |
618 | /* But for binary operators, "apply" everything on the operator |
619 | * stack until we find an operator with a lesser priority than the |
620 | * one we have just extracted. */ |
621 | /* Left paren is given the lowest priority so it will never be |
622 | * "applied" in this way. |
623 | * if associativity is right and priority eq, applied also skip |
624 | */ |
625 | prec = PREC(op); |
626 | if ((prec > 0 && prec < UNARYPREC) || prec == SPEC_PREC) { |
627 | /* not left paren or unary */ |
628 | if (lasttok != TOK_NUM) { |
629 | /* binary op must be preceded by a num */ |
630 | goto err; |
631 | } |
632 | while (stackptr != stack) { |
633 | if (op == TOK_RPAREN) { |
634 | /* The algorithm employed here is simple: while we don't |
635 | * hit an open paren nor the bottom of the stack, pop |
636 | * tokens and apply them */ |
637 | if (stackptr[-1] == TOK_LPAREN) { |
638 | --stackptr; |
639 | /* Any operator directly after a */ |
640 | lasttok = TOK_NUM; |
641 | /* close paren should consider itself binary */ |
642 | goto prologue; |
643 | } |
644 | } else { |
645 | operator prev_prec = PREC(stackptr[-1]); |
646 | |
647 | convert_prec_is_assing(prec); |
648 | convert_prec_is_assing(prev_prec); |
649 | if (prev_prec < prec) |
650 | break; |
651 | /* check right assoc */ |
652 | if (prev_prec == prec && is_right_associativity(prec)) |
653 | break; |
654 | } |
655 | errcode = arith_apply(*--stackptr, numstack, &numstackptr, math_hooks); |
656 | if (errcode) goto ret; |
657 | } |
658 | if (op == TOK_RPAREN) { |
659 | goto err; |
660 | } |
661 | } |
662 | |
663 | /* Push this operator to the stack and remember it. */ |
664 | *stackptr++ = lasttok = op; |
665 | prologue: |
666 | ++expr; |
667 | } /* while */ |
668 | } |
669 | |
670 | /* |
671 | * Copyright (c) 1989, 1991, 1993, 1994 |
672 | * The Regents of the University of California. All rights reserved. |
673 | * |
674 | * This code is derived from software contributed to Berkeley by |
675 | * Kenneth Almquist. |
676 | * |
677 | * Redistribution and use in source and binary forms, with or without |
678 | * modification, are permitted provided that the following conditions |
679 | * are met: |
680 | * 1. Redistributions of source code must retain the above copyright |
681 | * notice, this list of conditions and the following disclaimer. |
682 | * 2. Redistributions in binary form must reproduce the above copyright |
683 | * notice, this list of conditions and the following disclaimer in the |
684 | * documentation and/or other materials provided with the distribution. |
685 | * 3. Neither the name of the University nor the names of its contributors |
686 | * may be used to endorse or promote products derived from this software |
687 | * without specific prior written permission. |
688 | * |
689 | * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND |
690 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
691 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
692 | * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE |
693 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL |
694 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS |
695 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) |
696 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT |
697 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY |
698 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF |
699 | * SUCH DAMAGE. |
700 | */ |