aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorGlenn L McGrath <bug1@ihug.co.nz>2002-08-23 12:04:23 +0000
committerGlenn L McGrath <bug1@ihug.co.nz>2002-08-23 12:04:23 +0000
commitde9e803149a6e3e2d8c7db03620dd94b48a55843 (patch)
treeb483d973fbbd9768428cd053bd4ca35e3d29f52a
parente599b6d96ea61ef4cda5f5a72b588aa474eba73f (diff)
downloadbusybox-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.c203
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
160static short arith_apply(operator op, long *numstack, long **numstackptr) 161 */
162static 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;
220err: return(-1); 234 err:
235 return (-1);
221} 236}
222 237
223static const char endexpression[] = ")"; 238static const char endexpression[] = ")";
@@ -227,7 +242,7 @@ static const char op_char[] = "!<>=|&*/%~()+-";
227static const char op_token[] = { 242static 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
241extern long arith (const char *expr, int *errcode) 256extern 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 }