diff options
author | Glenn L McGrath <bug1@ihug.co.nz> | 2002-08-23 12:04:23 +0000 |
---|---|---|
committer | Glenn L McGrath <bug1@ihug.co.nz> | 2002-08-23 12:04:23 +0000 |
commit | de9e803149a6e3e2d8c7db03620dd94b48a55843 (patch) | |
tree | b483d973fbbd9768428cd053bd4ca35e3d29f52a | |
parent | e599b6d96ea61ef4cda5f5a72b588aa474eba73f (diff) | |
download | busybox-w32-de9e803149a6e3e2d8c7db03620dd94b48a55843.tar.gz busybox-w32-de9e803149a6e3e2d8c7db03620dd94b48a55843.tar.bz2 busybox-w32-de9e803149a6e3e2d8c7db03620dd94b48a55843.zip |
Apply vodz last_patch51_2 and run through indent
-rw-r--r-- | libbb/arith.c | 203 |
1 files changed, 116 insertions, 87 deletions
diff --git a/libbb/arith.c b/libbb/arith.c index 362f7bb2b..d79501cc4 100644 --- a/libbb/arith.c +++ b/libbb/arith.c | |||
@@ -26,14 +26,14 @@ | |||
26 | * listed in #defines below. Parens, order of operations, and error handling | 26 | * listed in #defines below. Parens, order of operations, and error handling |
27 | * are supported. This code is threadsafe. The exact expression format should | 27 | * are supported. This code is threadsafe. The exact expression format should |
28 | * be that which POSIX specifies for shells. */ | 28 | * be that which POSIX specifies for shells. */ |
29 | 29 | ||
30 | /* The code uses a simple two-stack algorithm. See | 30 | /* The code uses a simple two-stack algorithm. See |
31 | * http://www.onthenet.com.au/~grahamis/int2008/week02/lect02.html | 31 | * http://www.onthenet.com.au/~grahamis/int2008/week02/lect02.html |
32 | * for a detailed explaination of the infix-to-postfix algorithm on which | 32 | * for a detailed explaination of the infix-to-postfix algorithm on which |
33 | * this is based (this code differs in that it applies operators immediately | 33 | * this is based (this code differs in that it applies operators immediately |
34 | * to the stack instead of adding them to a queue to end up with an | 34 | * to the stack instead of adding them to a queue to end up with an |
35 | * expression). */ | 35 | * expression). */ |
36 | 36 | ||
37 | /* To use the routine, call it with an expression string and error return | 37 | /* To use the routine, call it with an expression string and error return |
38 | * pointer */ | 38 | * pointer */ |
39 | 39 | ||
@@ -140,7 +140,8 @@ typedef char operator; | |||
140 | #define TOK_REM tok_decl(10,2) | 140 | #define TOK_REM tok_decl(10,2) |
141 | 141 | ||
142 | /* For now all unary operators have the same precedence, and that's used to | 142 | /* For now all unary operators have the same precedence, and that's used to |
143 | * identify them as unary operators */ | 143 | * identify them as unary operators |
144 | */ | ||
144 | #define UNARYPREC 14 | 145 | #define UNARYPREC 14 |
145 | #define TOK_BNOT tok_decl(UNARYPREC,0) | 146 | #define TOK_BNOT tok_decl(UNARYPREC,0) |
146 | #define TOK_NOT tok_decl(UNARYPREC,1) | 147 | #define TOK_NOT tok_decl(UNARYPREC,1) |
@@ -149,75 +150,89 @@ typedef char operator; | |||
149 | 150 | ||
150 | #define TOK_NUM tok_decl(15,0) | 151 | #define TOK_NUM tok_decl(15,0) |
151 | #define TOK_RPAREN tok_decl(15,1) | 152 | #define TOK_RPAREN tok_decl(15,1) |
152 | #define TOK_ERROR tok_decl(15,2) /* just a place-holder really */ | 153 | #define TOK_ERROR tok_decl(15,2) /* just a place-holder really */ |
153 | 154 | ||
154 | #define ARITH_APPLY(op) arith_apply(op, numstack, &numstackptr) | 155 | #define ARITH_APPLY(op) arith_apply(op, numstack, &numstackptr) |
155 | #define NUMPTR (*numstackptr) | 156 | #define NUMPTR (*numstackptr) |
156 | 157 | ||
157 | /* "applying" a token means performing it on the top elements on the integer | 158 | /* "applying" a token means performing it on the top elements on the integer |
158 | * stack. For a unary operator it will only change the top element, but a | 159 | * stack. For a unary operator it will only change the top element, but a |
159 | * binary operator will pop two arguments and push a result */ | 160 | * binary operator will pop two arguments and push a result |
160 | static short arith_apply(operator op, long *numstack, long **numstackptr) | 161 | */ |
162 | static short arith_apply(operator op, long *numstack, long **numstackptr) | ||
161 | { | 163 | { |
162 | long numptr_val; | 164 | long numptr_val; |
163 | long *NUMPTR_M1; | 165 | long *NUMPTR_M1; |
164 | 166 | ||
165 | if (NUMPTR == numstack) goto err; /* There is no operator that can work | 167 | /* There is no operator that can work without arguments */ |
166 | without arguments */ | 168 | if (NUMPTR == numstack) { |
169 | goto err; | ||
170 | } | ||
171 | |||
167 | NUMPTR_M1 = NUMPTR - 1; | 172 | NUMPTR_M1 = NUMPTR - 1; |
168 | if (op == TOK_UMINUS) | 173 | if (op == TOK_UMINUS) { |
169 | *NUMPTR_M1 *= -1; | 174 | *NUMPTR_M1 *= -1; |
170 | else if (op == TOK_NOT) | 175 | } else if (op == TOK_NOT) { |
171 | *NUMPTR_M1 = !(*NUMPTR_M1); | 176 | *NUMPTR_M1 = !(*NUMPTR_M1); |
172 | else if (op == TOK_BNOT) | 177 | } else if (op == TOK_BNOT) { |
173 | *NUMPTR_M1 = ~(*NUMPTR_M1); | 178 | *NUMPTR_M1 = ~(*NUMPTR_M1); |
174 | else if (op != TOK_UPLUS) { | 179 | } else if (op != TOK_UPLUS) { |
175 | /* Binary operators */ | 180 | /* Binary operators */ |
176 | if (NUMPTR_M1 == numstack) goto err; /* ... and binary operators need two | 181 | |
177 | arguments */ | 182 | /* ... and binary operators need two arguments */ |
178 | numptr_val = *--NUMPTR; /* ... and they pop one */ | 183 | if (NUMPTR_M1 == numstack) { |
179 | NUMPTR_M1 = NUMPTR - 1; | 184 | goto err; |
180 | if (op == TOK_BOR) | 185 | } |
181 | *NUMPTR_M1 |= numptr_val; | 186 | /* ... and they pop one */ |
182 | else if (op == TOK_OR) | 187 | numptr_val = *--NUMPTR; |
183 | *NUMPTR_M1 = numptr_val || *NUMPTR_M1; | 188 | |
184 | else if (op == TOK_BAND) | 189 | NUMPTR_M1 = NUMPTR - 1; |
185 | *NUMPTR_M1 &= numptr_val; | 190 | |
186 | else if (op == TOK_AND) | 191 | if (op == TOK_BOR) { |
187 | *NUMPTR_M1 = *NUMPTR_M1 && numptr_val; | 192 | *NUMPTR_M1 |= numptr_val; |
188 | else if (op == TOK_EQ) | 193 | } else if (op == TOK_OR) { |
189 | *NUMPTR_M1 = (*NUMPTR_M1 == numptr_val); | 194 | *NUMPTR_M1 = numptr_val || *NUMPTR_M1; |
190 | else if (op == TOK_NE) | 195 | } else if (op == TOK_BAND) { |
191 | *NUMPTR_M1 = (*NUMPTR_M1 != numptr_val); | 196 | *NUMPTR_M1 &= numptr_val; |
192 | else if (op == TOK_GE) | 197 | } else if (op == TOK_AND) { |
193 | *NUMPTR_M1 = (*NUMPTR_M1 >= numptr_val); | 198 | *NUMPTR_M1 = *NUMPTR_M1 && numptr_val; |
194 | else if (op == TOK_RSHIFT) | 199 | } else if (op == TOK_EQ) { |
195 | *NUMPTR_M1 >>= numptr_val; | 200 | *NUMPTR_M1 = (*NUMPTR_M1 == numptr_val); |
196 | else if (op == TOK_LSHIFT) | 201 | } else if (op == TOK_NE) { |
197 | *NUMPTR_M1 <<= numptr_val; | 202 | *NUMPTR_M1 = (*NUMPTR_M1 != numptr_val); |
198 | else if (op == TOK_GT) | 203 | } else if (op == TOK_GE) { |
199 | *NUMPTR_M1 = (*NUMPTR_M1 > numptr_val); | 204 | *NUMPTR_M1 = (*NUMPTR_M1 >= numptr_val); |
200 | else if (op == TOK_LT) | 205 | } else if (op == TOK_RSHIFT) { |
201 | *NUMPTR_M1 = (*NUMPTR_M1 < numptr_val); | 206 | *NUMPTR_M1 >>= numptr_val; |
202 | else if (op == TOK_LE) | 207 | } else if (op == TOK_LSHIFT) { |
203 | *NUMPTR_M1 = (*NUMPTR_M1 <= numptr_val); | 208 | *NUMPTR_M1 <<= numptr_val; |
204 | else if (op == TOK_MUL) | 209 | } else if (op == TOK_GT) { |
205 | *NUMPTR_M1 *= numptr_val; | 210 | *NUMPTR_M1 = (*NUMPTR_M1 > numptr_val); |
206 | else if (op == TOK_ADD) | 211 | } else if (op == TOK_LT) { |
207 | *NUMPTR_M1 += numptr_val; | 212 | *NUMPTR_M1 = (*NUMPTR_M1 < numptr_val); |
208 | else if (op == TOK_SUB) | 213 | } else if (op == TOK_LE) { |
209 | *NUMPTR_M1 -= numptr_val; | 214 | *NUMPTR_M1 = (*NUMPTR_M1 <= numptr_val); |
210 | else if(numptr_val==0) /* zero divisor check */ | 215 | } else if (op == TOK_MUL) { |
211 | return -2; | 216 | *NUMPTR_M1 *= numptr_val; |
212 | else if (op == TOK_DIV) | 217 | } else if (op == TOK_ADD) { |
213 | *NUMPTR_M1 /= numptr_val; | 218 | *NUMPTR_M1 += numptr_val; |
214 | else if (op == TOK_REM) | 219 | } else if (op == TOK_SUB) { |
215 | *NUMPTR_M1 %= numptr_val; | 220 | *NUMPTR_M1 -= numptr_val; |
216 | /* WARNING!!! WARNING!!! WARNING!!! */ | 221 | } |
217 | /* Any new operators should be added BEFORE the zero divisor check! */ | 222 | /* zero divisor check */ |
223 | else if (numptr_val == 0) { | ||
224 | return -2; | ||
225 | } else if (op == TOK_DIV) { | ||
226 | *NUMPTR_M1 /= numptr_val; | ||
227 | } else if (op == TOK_REM) { | ||
228 | *NUMPTR_M1 %= numptr_val; | ||
229 | } | ||
230 | /* WARNING!!! WARNING!!! WARNING!!! */ | ||
231 | /* Any new operators should be added BEFORE the zero divisor check! */ | ||
218 | } | 232 | } |
219 | return 0; | 233 | return 0; |
220 | err: return(-1); | 234 | err: |
235 | return (-1); | ||
221 | } | 236 | } |
222 | 237 | ||
223 | static const char endexpression[] = ")"; | 238 | static const char endexpression[] = ")"; |
@@ -227,7 +242,7 @@ static const char op_char[] = "!<>=|&*/%~()+-"; | |||
227 | static const char op_token[] = { | 242 | static const char op_token[] = { |
228 | /* paired with equal */ | 243 | /* paired with equal */ |
229 | TOK_NE, TOK_LE, TOK_GE, | 244 | TOK_NE, TOK_LE, TOK_GE, |
230 | /* paired with self -- note: ! is special-cased below*/ | 245 | /* paired with self -- note: ! is special-cased below */ |
231 | TOK_ERROR, TOK_LSHIFT, TOK_RSHIFT, TOK_EQ, TOK_OR, TOK_AND, | 246 | TOK_ERROR, TOK_LSHIFT, TOK_RSHIFT, TOK_EQ, TOK_OR, TOK_AND, |
232 | /* singles */ | 247 | /* singles */ |
233 | TOK_NOT, TOK_LT, TOK_GT, TOK_ERROR, TOK_BOR, TOK_BAND, | 248 | TOK_NOT, TOK_LT, TOK_GT, TOK_ERROR, TOK_BOR, TOK_BAND, |
@@ -238,31 +253,32 @@ static const char op_token[] = { | |||
238 | #define NUM_PAIR_EQUAL 3 | 253 | #define NUM_PAIR_EQUAL 3 |
239 | #define NUM_PAIR_SAME 6 | 254 | #define NUM_PAIR_SAME 6 |
240 | 255 | ||
241 | extern long arith (const char *expr, int *errcode) | 256 | extern long arith(const char *expr, int *errcode) |
242 | { | 257 | { |
243 | register char arithval; /* Current character under analysis */ | 258 | register char arithval; /* Current character under analysis */ |
244 | operator lasttok, op; | 259 | operator lasttok, op; |
245 | unsigned char prec; | 260 | unsigned char prec; |
246 | |||
247 | const char *p = endexpression; | 261 | const char *p = endexpression; |
248 | |||
249 | size_t datasizes = strlen(expr); | 262 | size_t datasizes = strlen(expr); |
250 | 263 | ||
251 | /* Stack of integers */ | 264 | /* Stack of integers */ |
252 | /* The proof that there can be no more than strlen(startbuf)/2+1 integers | 265 | /* The proof that there can be no more than strlen(startbuf)/2+1 integers |
253 | * in any given correct or incorrect expression is left as an excersize to | 266 | * in any given correct or incorrect expression is left as an excersize to |
254 | * the reader. */ | 267 | * the reader. */ |
255 | long *numstack = alloca((datasizes/2)*sizeof(long)), | 268 | long *numstack = alloca(((datasizes + 1) / 2) * sizeof(long)); |
256 | *numstackptr = numstack; | 269 | long *numstackptr = numstack; |
270 | |||
257 | /* Stack of operator tokens */ | 271 | /* Stack of operator tokens */ |
258 | operator *stack = alloca((datasizes+1) * sizeof(operator)), | 272 | operator * stack = alloca((datasizes + 1) * sizeof(operator)); |
259 | *stackptr = stack; | 273 | operator * stackptr = stack; |
260 | 274 | ||
261 | *stackptr++ = lasttok = TOK_LPAREN; /* start off with a left paren */ | 275 | /* start off with a left paren */ |
276 | *stackptr++ = lasttok = TOK_LPAREN; | ||
262 | 277 | ||
263 | loop: | 278 | loop: |
264 | if ((arithval = *expr) == 0) { | 279 | if ((arithval = *expr) == 0) { |
265 | if (p == endexpression) { /* Null expression. */ | 280 | /* Null expression. */ |
281 | if (p == endexpression) { | ||
266 | return (*errcode = 0); | 282 | return (*errcode = 0); |
267 | } | 283 | } |
268 | 284 | ||
@@ -271,23 +287,25 @@ extern long arith (const char *expr, int *errcode) | |||
271 | * are to be applied in order. At the end, there should be a final | 287 | * are to be applied in order. At the end, there should be a final |
272 | * result on the integer stack */ | 288 | * result on the integer stack */ |
273 | 289 | ||
274 | if (expr != endexpression + 1) { /* If we haven't done so already, */ | 290 | if (expr != endexpression + 1) { /* If we haven't done so already, */ |
275 | expr = endexpression; /* append a closing right paren */ | 291 | expr = endexpression; /* append a closing right paren */ |
276 | goto loop; /* and let the loop process it. */ | 292 | goto loop; /* and let the loop process it. */ |
277 | } | 293 | } |
278 | /* At this point, we're done with the expression. */ | 294 | /* At this point, we're done with the expression. */ |
279 | if (numstackptr != numstack+1) {/* ... but if there isn't, it's bad */ | 295 | if (numstackptr != numstack + 1) { /* ... but if there isn't, it's bad */ |
280 | err: | 296 | err: |
281 | return (*errcode = -1); | 297 | return (*errcode = -1); |
282 | /* NOTREACHED */ | 298 | /* NOTREACHED */ |
283 | } | 299 | } |
284 | return *numstack; | 300 | return *numstack; |
285 | } else { | 301 | } else { |
286 | /* Continue processing the expression. */ | 302 | /* Continue processing the expression. */ |
303 | /* Skip whitespace */ | ||
287 | if (isspace(arithval)) { | 304 | if (isspace(arithval)) { |
288 | goto prologue; /* Skip whitespace */ | 305 | goto prologue; |
289 | } | 306 | } |
290 | if ((unsigned)arithval-'0' <= 9) /* isdigit */ { | 307 | /* isdigit ? */ |
308 | if ((unsigned) arithval - '0' <= 9) { | ||
291 | *numstackptr++ = strtol(expr, (char **) &expr, 10); | 309 | *numstackptr++ = strtol(expr, (char **) &expr, 10); |
292 | lasttok = TOK_NUM; | 310 | lasttok = TOK_NUM; |
293 | goto loop; | 311 | goto loop; |
@@ -297,20 +315,21 @@ extern long arith (const char *expr, int *errcode) | |||
297 | goto err; | 315 | goto err; |
298 | } | 316 | } |
299 | #else | 317 | #else |
300 | for ( p=op_char ; *p != arithval ; p++ ) { | 318 | for (p = op_char; *p != arithval; p++) { |
301 | if (!*p) { | 319 | if (!*p) { |
302 | goto err; | 320 | goto err; |
303 | } | 321 | } |
304 | } | 322 | } |
305 | #endif | 323 | #endif |
306 | p = op_token + (int)(p - op_char); | 324 | p = op_token + (int) (p - op_char); |
307 | ++expr; | 325 | ++expr; |
308 | if ((p >= op_token + NUM_PAIR_EQUAL) || (*expr != '=')) { | 326 | if ((p >= op_token + NUM_PAIR_EQUAL) || (*expr != '=')) { |
309 | p += NUM_PAIR_EQUAL; | 327 | p += NUM_PAIR_EQUAL; |
310 | if ((p >= op_token + NUM_PAIR_SAME + NUM_PAIR_EQUAL) | 328 | if ((p >= op_token + NUM_PAIR_SAME + NUM_PAIR_EQUAL) |
311 | || (*expr != arithval) || (arithval == '!')) { | 329 | || (*expr != arithval) || (arithval == '!')) { |
312 | --expr; | 330 | --expr; |
313 | if (arithval == '=') { /* single = */ | 331 | /* single = */ |
332 | if (arithval == '=') { | ||
314 | goto err; | 333 | goto err; |
315 | } | 334 | } |
316 | p += NUM_PAIR_SAME; | 335 | p += NUM_PAIR_SAME; |
@@ -319,9 +338,11 @@ extern long arith (const char *expr, int *errcode) | |||
319 | * a number, since it evaluates to one). Think about it. | 338 | * a number, since it evaluates to one). Think about it. |
320 | * It makes sense. */ | 339 | * It makes sense. */ |
321 | if ((lasttok != TOK_NUM) | 340 | if ((lasttok != TOK_NUM) |
322 | && (p >= op_token + NUM_PAIR_SAME + NUM_PAIR_EQUAL | 341 | && (p >= |
323 | + sizeof(op_char) - 2)) { | 342 | (op_token + NUM_PAIR_SAME + NUM_PAIR_EQUAL + |
324 | p += 2; /* Unary plus or minus */ | 343 | sizeof(op_char) - 2))) { |
344 | /* Unary plus or minus */ | ||
345 | p += 2; | ||
325 | } | 346 | } |
326 | } | 347 | } |
327 | } | 348 | } |
@@ -337,8 +358,11 @@ extern long arith (const char *expr, int *errcode) | |||
337 | /* Left paren is given the lowest priority so it will never be | 358 | /* Left paren is given the lowest priority so it will never be |
338 | * "applied" in this way */ | 359 | * "applied" in this way */ |
339 | prec = PREC(op); | 360 | prec = PREC(op); |
340 | if ((prec > 0) && (prec != UNARYPREC)) { /* not left paren or unary */ | 361 | |
341 | if (lasttok != TOK_NUM) { /* binary op must be preceded by a num */ | 362 | /* not left paren or unary */ |
363 | if ((prec > 0) && (prec != UNARYPREC)) { | ||
364 | /* binary op must be preceded by a num */ | ||
365 | if (lasttok != TOK_NUM) { | ||
342 | goto err; | 366 | goto err; |
343 | } | 367 | } |
344 | while (stackptr != stack) { | 368 | while (stackptr != stack) { |
@@ -348,15 +372,20 @@ extern long arith (const char *expr, int *errcode) | |||
348 | * tokens and apply them */ | 372 | * tokens and apply them */ |
349 | if (stackptr[-1] == TOK_LPAREN) { | 373 | if (stackptr[-1] == TOK_LPAREN) { |
350 | --stackptr; | 374 | --stackptr; |
351 | lasttok = TOK_NUM; /* Any operator directly after a */ | 375 | |
352 | /* close paren should consider itself binary */ | 376 | /* Any operator directly after a */ |
377 | lasttok = TOK_NUM; | ||
378 | |||
379 | /* close paren should consider itself binary */ | ||
353 | goto prologue; | 380 | goto prologue; |
354 | } | 381 | } |
355 | } else if (PREC(stackptr[-1]) < prec) { | 382 | } else if (PREC(stackptr[-1]) < prec) { |
356 | break; | 383 | break; |
357 | } | 384 | } |
358 | *errcode = ARITH_APPLY(*--stackptr); | 385 | *errcode = ARITH_APPLY(*--stackptr); |
359 | if(*errcode) return *errcode; | 386 | if (*errcode) { |
387 | return *errcode; | ||
388 | } | ||
360 | } | 389 | } |
361 | if (op == TOK_RPAREN) { | 390 | if (op == TOK_RPAREN) { |
362 | goto err; | 391 | goto err; |
@@ -366,7 +395,7 @@ extern long arith (const char *expr, int *errcode) | |||
366 | /* Push this operator to the stack and remember it. */ | 395 | /* Push this operator to the stack and remember it. */ |
367 | *stackptr++ = lasttok = op; | 396 | *stackptr++ = lasttok = op; |
368 | 397 | ||
369 | prologue: | 398 | prologue: |
370 | ++expr; | 399 | ++expr; |
371 | goto loop; | 400 | goto loop; |
372 | } | 401 | } |