1 /* $NetBSD: arithmetic.c,v 1.4 2017/07/24 13:21:14 kre Exp $ */ 2 3 /*- 4 * Copyright (c) 1993 5 * The Regents of the University of California. All rights reserved. 6 * Copyright (c) 2007 7 * Herbert Xu <herbert@gondor.apana.org.au>. All rights reserved. 8 * 9 * This code is derived from software contributed to Berkeley by 10 * Kenneth Almquist. 11 * 12 * Redistribution and use in source and binary forms, with or without 13 * modification, are permitted provided that the following conditions 14 * are met: 15 * 1. Redistributions of source code must retain the above copyright 16 * notice, this list of conditions and the following disclaimer. 17 * 2. Redistributions in binary form must reproduce the above copyright 18 * notice, this list of conditions and the following disclaimer in the 19 * documentation and/or other materials provided with the distribution. 20 * 3. Neither the name of the University nor the names of its contributors 21 * may be used to endorse or promote products derived from this software 22 * without specific prior written permission. 23 * 24 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 25 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 26 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 27 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 28 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 29 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 30 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 31 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 32 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 33 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 34 * SUCH DAMAGE. 35 * 36 * From FreeBSD, who obtained it from dash, modified both times... 37 */ 38 39 #include <sys/cdefs.h> 40 41 #ifndef lint 42 __RCSID("$NetBSD: arithmetic.c,v 1.4 2017/07/24 13:21:14 kre Exp $"); 43 #endif /* not lint */ 44 45 #include <limits.h> 46 #include <errno.h> 47 #include <inttypes.h> 48 #include <stdlib.h> 49 #include <stdio.h> 50 #include <string.h> 51 52 #include "shell.h" 53 #include "arithmetic.h" 54 #include "arith_tokens.h" 55 #include "expand.h" 56 #include "error.h" 57 #include "memalloc.h" 58 #include "output.h" 59 #include "options.h" 60 #include "var.h" 61 #include "show.h" 62 63 #if ARITH_BOR + ARITH_ASS_GAP != ARITH_BORASS || \ 64 ARITH_ASS + ARITH_ASS_GAP != ARITH_EQ 65 #error Arithmetic tokens are out of order. 66 #endif 67 68 static const char *arith_startbuf; 69 70 const char *arith_buf; 71 union a_token_val a_t_val; 72 73 static int last_token; 74 75 int arith_lno, arith_var_lno; 76 77 #define ARITH_PRECEDENCE(op, prec) [op - ARITH_BINOP_MIN] = prec 78 79 static const char prec[ARITH_BINOP_MAX - ARITH_BINOP_MIN] = { 80 ARITH_PRECEDENCE(ARITH_MUL, 0), 81 ARITH_PRECEDENCE(ARITH_DIV, 0), 82 ARITH_PRECEDENCE(ARITH_REM, 0), 83 ARITH_PRECEDENCE(ARITH_ADD, 1), 84 ARITH_PRECEDENCE(ARITH_SUB, 1), 85 ARITH_PRECEDENCE(ARITH_LSHIFT, 2), 86 ARITH_PRECEDENCE(ARITH_RSHIFT, 2), 87 ARITH_PRECEDENCE(ARITH_LT, 3), 88 ARITH_PRECEDENCE(ARITH_LE, 3), 89 ARITH_PRECEDENCE(ARITH_GT, 3), 90 ARITH_PRECEDENCE(ARITH_GE, 3), 91 ARITH_PRECEDENCE(ARITH_EQ, 4), 92 ARITH_PRECEDENCE(ARITH_NE, 4), 93 ARITH_PRECEDENCE(ARITH_BAND, 5), 94 ARITH_PRECEDENCE(ARITH_BXOR, 6), 95 ARITH_PRECEDENCE(ARITH_BOR, 7), 96 }; 97 98 #define ARITH_MAX_PREC 8 99 100 int expcmd(int, char **); 101 102 static void __dead 103 arith_err(const char *s) 104 { 105 error("arithmetic expression: %s: \"%s\"", s, arith_startbuf); 106 /* NOTREACHED */ 107 } 108 109 static intmax_t 110 arith_lookupvarint(char *varname) 111 { 112 const char *str; 113 char *p; 114 intmax_t result; 115 const int oln = line_number; 116 117 VTRACE(DBG_ARITH, ("Arith var lookup(\"%s\") with lno=%d\n", varname, 118 arith_var_lno)); 119 120 line_number = arith_var_lno; 121 str = lookupvar(varname); 122 line_number = oln; 123 124 if (uflag && str == NULL) 125 arith_err("variable not set"); 126 if (str == NULL || *str == '\0') 127 str = "0"; 128 errno = 0; 129 result = strtoimax(str, &p, 0); 130 if (errno != 0 || *p != '\0') 131 arith_err("variable contains non-numeric value"); 132 return result; 133 } 134 135 static inline int 136 arith_prec(int op) 137 { 138 139 return prec[op - ARITH_BINOP_MIN]; 140 } 141 142 static inline int 143 higher_prec(int op1, int op2) 144 { 145 146 return arith_prec(op1) < arith_prec(op2); 147 } 148 149 static intmax_t 150 do_binop(int op, intmax_t a, intmax_t b) 151 { 152 153 VTRACE(DBG_ARITH, ("Arith do binop %d (%jd, %jd)\n", op, a, b)); 154 switch (op) { 155 default: 156 arith_err("token error"); 157 case ARITH_REM: 158 case ARITH_DIV: 159 if (b == 0) 160 arith_err("division by zero"); 161 if (a == INTMAX_MIN && b == -1) 162 arith_err("divide error"); 163 return op == ARITH_REM ? a % b : a / b; 164 case ARITH_MUL: 165 return (uintmax_t)a * (uintmax_t)b; 166 case ARITH_ADD: 167 return (uintmax_t)a + (uintmax_t)b; 168 case ARITH_SUB: 169 return (uintmax_t)a - (uintmax_t)b; 170 case ARITH_LSHIFT: 171 return (uintmax_t)a << (b & (sizeof(uintmax_t) * CHAR_BIT - 1)); 172 case ARITH_RSHIFT: 173 return a >> (b & (sizeof(uintmax_t) * CHAR_BIT - 1)); 174 case ARITH_LT: 175 return a < b; 176 case ARITH_LE: 177 return a <= b; 178 case ARITH_GT: 179 return a > b; 180 case ARITH_GE: 181 return a >= b; 182 case ARITH_EQ: 183 return a == b; 184 case ARITH_NE: 185 return a != b; 186 case ARITH_BAND: 187 return a & b; 188 case ARITH_BXOR: 189 return a ^ b; 190 case ARITH_BOR: 191 return a | b; 192 } 193 } 194 195 static intmax_t assignment(int, int); 196 static intmax_t comma_list(int, int); 197 198 static intmax_t 199 primary(int token, union a_token_val *val, int op, int noeval) 200 { 201 intmax_t result; 202 char sresult[DIGITS(result) + 1]; 203 204 VTRACE(DBG_ARITH, ("Arith primary: token %d op %d%s\n", 205 token, op, noeval ? " noeval" : "")); 206 207 switch (token) { 208 case ARITH_LPAREN: 209 result = comma_list(op, noeval); 210 if (last_token != ARITH_RPAREN) 211 arith_err("expecting ')'"); 212 last_token = arith_token(); 213 return result; 214 case ARITH_NUM: 215 last_token = op; 216 return val->val; 217 case ARITH_VAR: 218 result = noeval ? val->val : arith_lookupvarint(val->name); 219 if (op == ARITH_INCR || op == ARITH_DECR) { 220 last_token = arith_token(); 221 if (noeval) 222 return val->val; 223 224 snprintf(sresult, sizeof(sresult), ARITH_FORMAT_STR, 225 result + (op == ARITH_INCR ? 1 : -1)); 226 setvar(val->name, sresult, 0); 227 } else 228 last_token = op; 229 return result; 230 case ARITH_ADD: 231 *val = a_t_val; 232 return primary(op, val, arith_token(), noeval); 233 case ARITH_SUB: 234 *val = a_t_val; 235 return -primary(op, val, arith_token(), noeval); 236 case ARITH_NOT: 237 *val = a_t_val; 238 return !primary(op, val, arith_token(), noeval); 239 case ARITH_BNOT: 240 *val = a_t_val; 241 return ~primary(op, val, arith_token(), noeval); 242 case ARITH_INCR: 243 case ARITH_DECR: 244 if (op != ARITH_VAR) 245 arith_err("incr/decr require var name"); 246 last_token = arith_token(); 247 if (noeval) 248 return val->val; 249 result = arith_lookupvarint(a_t_val.name); 250 snprintf(sresult, sizeof(sresult), ARITH_FORMAT_STR, 251 result += (token == ARITH_INCR ? 1 : -1)); 252 setvar(a_t_val.name, sresult, 0); 253 return result; 254 default: 255 arith_err("expecting primary"); 256 } 257 return 0; /* never reached */ 258 } 259 260 static intmax_t 261 binop2(intmax_t a, int op, int precedence, int noeval) 262 { 263 union a_token_val val; 264 intmax_t b; 265 int op2; 266 int token; 267 268 VTRACE(DBG_ARITH, ("Arith: binop2 %jd op %d (P:%d)%s\n", 269 a, op, precedence, noeval ? " noeval" : "")); 270 271 for (;;) { 272 token = arith_token(); 273 val = a_t_val; 274 275 b = primary(token, &val, arith_token(), noeval); 276 277 op2 = last_token; 278 if (op2 >= ARITH_BINOP_MIN && op2 < ARITH_BINOP_MAX && 279 higher_prec(op2, op)) { 280 b = binop2(b, op2, arith_prec(op), noeval); 281 op2 = last_token; 282 } 283 284 a = noeval ? b : do_binop(op, a, b); 285 286 if (op2 < ARITH_BINOP_MIN || op2 >= ARITH_BINOP_MAX || 287 arith_prec(op2) >= precedence) 288 return a; 289 290 op = op2; 291 } 292 } 293 294 static intmax_t 295 binop(int token, union a_token_val *val, int op, int noeval) 296 { 297 intmax_t a = primary(token, val, op, noeval); 298 299 op = last_token; 300 if (op < ARITH_BINOP_MIN || op >= ARITH_BINOP_MAX) 301 return a; 302 303 return binop2(a, op, ARITH_MAX_PREC, noeval); 304 } 305 306 static intmax_t 307 and(int token, union a_token_val *val, int op, int noeval) 308 { 309 intmax_t a = binop(token, val, op, noeval); 310 intmax_t b; 311 312 op = last_token; 313 if (op != ARITH_AND) 314 return a; 315 316 VTRACE(DBG_ARITH, ("Arith: AND %jd%s\n", a, noeval ? " noeval" : "")); 317 318 token = arith_token(); 319 *val = a_t_val; 320 321 b = and(token, val, arith_token(), noeval | !a); 322 323 return a && b; 324 } 325 326 static intmax_t 327 or(int token, union a_token_val *val, int op, int noeval) 328 { 329 intmax_t a = and(token, val, op, noeval); 330 intmax_t b; 331 332 op = last_token; 333 if (op != ARITH_OR) 334 return a; 335 336 VTRACE(DBG_ARITH, ("Arith: OR %jd%s\n", a, noeval ? " noeval" : "")); 337 338 token = arith_token(); 339 *val = a_t_val; 340 341 b = or(token, val, arith_token(), noeval | !!a); 342 343 return a || b; 344 } 345 346 static intmax_t 347 cond(int token, union a_token_val *val, int op, int noeval) 348 { 349 intmax_t a = or(token, val, op, noeval); 350 intmax_t b; 351 intmax_t c; 352 353 if (last_token != ARITH_QMARK) 354 return a; 355 356 VTRACE(DBG_ARITH, ("Arith: ?: %jd%s\n", a, noeval ? " noeval" : "")); 357 358 b = assignment(arith_token(), noeval | !a); 359 360 if (last_token != ARITH_COLON) 361 arith_err("expecting ':'"); 362 363 token = arith_token(); 364 *val = a_t_val; 365 366 c = cond(token, val, arith_token(), noeval | !!a); 367 368 return a ? b : c; 369 } 370 371 static intmax_t 372 assignment(int var, int noeval) 373 { 374 union a_token_val val = a_t_val; 375 int op = arith_token(); 376 intmax_t result; 377 char sresult[DIGITS(result) + 1]; 378 379 380 if (var != ARITH_VAR) 381 return cond(var, &val, op, noeval); 382 383 if (op != ARITH_ASS && (op < ARITH_ASS_MIN || op >= ARITH_ASS_MAX)) 384 return cond(var, &val, op, noeval); 385 386 VTRACE(DBG_ARITH, ("Arith: %s ASSIGN %d%s\n", val.name, op, 387 noeval ? " noeval" : "")); 388 389 result = assignment(arith_token(), noeval); 390 if (noeval) 391 return result; 392 393 if (op != ARITH_ASS) 394 result = do_binop(op - ARITH_ASS_GAP, 395 arith_lookupvarint(val.name), result); 396 snprintf(sresult, sizeof(sresult), ARITH_FORMAT_STR, result); 397 setvar(val.name, sresult, 0); 398 return result; 399 } 400 401 static intmax_t 402 comma_list(int token, int noeval) 403 { 404 intmax_t result = assignment(token, noeval); 405 406 while (last_token == ARITH_COMMA) { 407 VTRACE(DBG_ARITH, ("Arith: comma discarding %jd%s\n", result, 408 noeval ? " noeval" : "")); 409 result = assignment(arith_token(), noeval); 410 } 411 412 return result; 413 } 414 415 intmax_t 416 arith(const char *s, int lno) 417 { 418 struct stackmark smark; 419 intmax_t result; 420 const char *p; 421 int nls = 0; 422 423 setstackmark(&smark); 424 425 arith_lno = lno; 426 427 CTRACE(DBG_ARITH, ("Arith(\"%s\", %d) @%d\n", s, lno, arith_lno)); 428 429 /* check if it is possible we might reference LINENO */ 430 p = s; 431 while ((p = strchr(p, 'L')) != NULL) { 432 if (p[1] == 'I' && p[2] == 'N') { 433 /* if it is possible, we need to correct airth_lno */ 434 p = s; 435 while ((p = strchr(p, '\n')) != NULL) 436 nls++, p++; 437 VTRACE(DBG_ARITH, ("Arith found %d newlines\n", nls)); 438 arith_lno -= nls; 439 break; 440 } 441 p++; 442 } 443 444 arith_buf = arith_startbuf = s; 445 446 result = comma_list(arith_token(), 0); 447 448 if (last_token) 449 arith_err("expecting end of expression"); 450 451 popstackmark(&smark); 452 453 CTRACE(DBG_ARITH, ("Arith result=%jd\n", result)); 454 455 return result; 456 } 457 458 /* 459 * The let(1)/exp(1) builtin. 460 */ 461 int 462 expcmd(int argc, char **argv) 463 { 464 const char *p; 465 char *concat; 466 char **ap; 467 intmax_t i; 468 469 if (argc > 1) { 470 p = argv[1]; 471 if (argc > 2) { 472 /* 473 * Concatenate arguments. 474 */ 475 STARTSTACKSTR(concat); 476 ap = argv + 2; 477 for (;;) { 478 while (*p) 479 STPUTC(*p++, concat); 480 if ((p = *ap++) == NULL) 481 break; 482 STPUTC(' ', concat); 483 } 484 STPUTC('\0', concat); 485 p = grabstackstr(concat); 486 } 487 } else 488 p = ""; 489 490 i = arith(p, line_number); 491 492 out1fmt(ARITH_FORMAT_STR "\n", i); 493 return !i; 494 } 495