1/* $NetBSD: arithmetic.c,v 1.5 2018/04/21 23:01:29 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.5 2018/04/21 23:01:29 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#include "syntax.h" 63 64#if ARITH_BOR + ARITH_ASS_GAP != ARITH_BORASS || \ 65 ARITH_ASS + ARITH_ASS_GAP != ARITH_EQ 66#error Arithmetic tokens are out of order. 67#endif 68 69static const char *arith_startbuf; 70 71const char *arith_buf; 72union a_token_val a_t_val; 73 74static int last_token; 75 76int arith_lno, arith_var_lno; 77 78#define ARITH_PRECEDENCE(op, prec) [op - ARITH_BINOP_MIN] = prec 79 80static const char prec[ARITH_BINOP_MAX - ARITH_BINOP_MIN] = { 81 ARITH_PRECEDENCE(ARITH_MUL, 0), 82 ARITH_PRECEDENCE(ARITH_DIV, 0), 83 ARITH_PRECEDENCE(ARITH_REM, 0), 84 ARITH_PRECEDENCE(ARITH_ADD, 1), 85 ARITH_PRECEDENCE(ARITH_SUB, 1), 86 ARITH_PRECEDENCE(ARITH_LSHIFT, 2), 87 ARITH_PRECEDENCE(ARITH_RSHIFT, 2), 88 ARITH_PRECEDENCE(ARITH_LT, 3), 89 ARITH_PRECEDENCE(ARITH_LE, 3), 90 ARITH_PRECEDENCE(ARITH_GT, 3), 91 ARITH_PRECEDENCE(ARITH_GE, 3), 92 ARITH_PRECEDENCE(ARITH_EQ, 4), 93 ARITH_PRECEDENCE(ARITH_NE, 4), 94 ARITH_PRECEDENCE(ARITH_BAND, 5), 95 ARITH_PRECEDENCE(ARITH_BXOR, 6), 96 ARITH_PRECEDENCE(ARITH_BOR, 7), 97}; 98 99#define ARITH_MAX_PREC 8 100 101int expcmd(int, char **); 102 103static void __dead 104arith_err(const char *s) 105{ 106 error("arithmetic expression: %s: \"%s\"", s, arith_startbuf); 107 /* NOTREACHED */ 108} 109 110static intmax_t 111arith_lookupvarint(char *varname) 112{ 113 const char *str; 114 char *p; 115 intmax_t result; 116 const int oln = line_number; 117 118 VTRACE(DBG_ARITH, ("Arith var lookup(\"%s\") with lno=%d\n", varname, 119 arith_var_lno)); 120 121 line_number = arith_var_lno; 122 str = lookupvar(varname); 123 line_number = oln; 124 125 if (uflag && str == NULL) 126 arith_err("variable not set"); 127 if (str == NULL || *str == '\0') 128 str = "0"; 129 errno = 0; 130 result = strtoimax(str, &p, 0); 131 if (errno != 0 || *p != '\0') { 132 if (errno == 0) { 133 while (*p != '\0' && is_space(*p)) 134 p++; 135 if (*p == '\0') 136 return result; 137 } 138 arith_err("variable contains non-numeric value"); 139 } 140 return result; 141} 142 143static inline int 144arith_prec(int op) 145{ 146 147 return prec[op - ARITH_BINOP_MIN]; 148} 149 150static inline int 151higher_prec(int op1, int op2) 152{ 153 154 return arith_prec(op1) < arith_prec(op2); 155} 156 157static intmax_t 158do_binop(int op, intmax_t a, intmax_t b) 159{ 160 161 VTRACE(DBG_ARITH, ("Arith do binop %d (%jd, %jd)\n", op, a, b)); 162 switch (op) { 163 default: 164 arith_err("token error"); 165 case ARITH_REM: 166 case ARITH_DIV: 167 if (b == 0) 168 arith_err("division by zero"); 169 if (a == INTMAX_MIN && b == -1) 170 arith_err("divide error"); 171 return op == ARITH_REM ? a % b : a / b; 172 case ARITH_MUL: 173 return (uintmax_t)a * (uintmax_t)b; 174 case ARITH_ADD: 175 return (uintmax_t)a + (uintmax_t)b; 176 case ARITH_SUB: 177 return (uintmax_t)a - (uintmax_t)b; 178 case ARITH_LSHIFT: 179 return (uintmax_t)a << (b & (sizeof(uintmax_t) * CHAR_BIT - 1)); 180 case ARITH_RSHIFT: 181 return a >> (b & (sizeof(uintmax_t) * CHAR_BIT - 1)); 182 case ARITH_LT: 183 return a < b; 184 case ARITH_LE: 185 return a <= b; 186 case ARITH_GT: 187 return a > b; 188 case ARITH_GE: 189 return a >= b; 190 case ARITH_EQ: 191 return a == b; 192 case ARITH_NE: 193 return a != b; 194 case ARITH_BAND: 195 return a & b; 196 case ARITH_BXOR: 197 return a ^ b; 198 case ARITH_BOR: 199 return a | b; 200 } 201} 202 203static intmax_t assignment(int, int); 204static intmax_t comma_list(int, int); 205 206static intmax_t 207primary(int token, union a_token_val *val, int op, int noeval) 208{ 209 intmax_t result; 210 char sresult[DIGITS(result) + 1]; 211 212 VTRACE(DBG_ARITH, ("Arith primary: token %d op %d%s\n", 213 token, op, noeval ? " noeval" : "")); 214 215 switch (token) { 216 case ARITH_LPAREN: 217 result = comma_list(op, noeval); 218 if (last_token != ARITH_RPAREN) 219 arith_err("expecting ')'"); 220 last_token = arith_token(); 221 return result; 222 case ARITH_NUM: 223 last_token = op; 224 return val->val; 225 case ARITH_VAR: 226 result = noeval ? val->val : arith_lookupvarint(val->name); 227 if (op == ARITH_INCR || op == ARITH_DECR) { 228 last_token = arith_token(); 229 if (noeval) 230 return val->val; 231 232 snprintf(sresult, sizeof(sresult), ARITH_FORMAT_STR, 233 result + (op == ARITH_INCR ? 1 : -1)); 234 setvar(val->name, sresult, 0); 235 } else 236 last_token = op; 237 return result; 238 case ARITH_ADD: 239 *val = a_t_val; 240 return primary(op, val, arith_token(), noeval); 241 case ARITH_SUB: 242 *val = a_t_val; 243 return -primary(op, val, arith_token(), noeval); 244 case ARITH_NOT: 245 *val = a_t_val; 246 return !primary(op, val, arith_token(), noeval); 247 case ARITH_BNOT: 248 *val = a_t_val; 249 return ~primary(op, val, arith_token(), noeval); 250 case ARITH_INCR: 251 case ARITH_DECR: 252 if (op != ARITH_VAR) 253 arith_err("incr/decr require var name"); 254 last_token = arith_token(); 255 if (noeval) 256 return val->val; 257 result = arith_lookupvarint(a_t_val.name); 258 snprintf(sresult, sizeof(sresult), ARITH_FORMAT_STR, 259 result += (token == ARITH_INCR ? 1 : -1)); 260 setvar(a_t_val.name, sresult, 0); 261 return result; 262 default: 263 arith_err("expecting primary"); 264 } 265 return 0; /* never reached */ 266} 267 268static intmax_t 269binop2(intmax_t a, int op, int precedence, int noeval) 270{ 271 union a_token_val val; 272 intmax_t b; 273 int op2; 274 int token; 275 276 VTRACE(DBG_ARITH, ("Arith: binop2 %jd op %d (P:%d)%s\n", 277 a, op, precedence, noeval ? " noeval" : "")); 278 279 for (;;) { 280 token = arith_token(); 281 val = a_t_val; 282 283 b = primary(token, &val, arith_token(), noeval); 284 285 op2 = last_token; 286 if (op2 >= ARITH_BINOP_MIN && op2 < ARITH_BINOP_MAX && 287 higher_prec(op2, op)) { 288 b = binop2(b, op2, arith_prec(op), noeval); 289 op2 = last_token; 290 } 291 292 a = noeval ? b : do_binop(op, a, b); 293 294 if (op2 < ARITH_BINOP_MIN || op2 >= ARITH_BINOP_MAX || 295 arith_prec(op2) >= precedence) 296 return a; 297 298 op = op2; 299 } 300} 301 302static intmax_t 303binop(int token, union a_token_val *val, int op, int noeval) 304{ 305 intmax_t a = primary(token, val, op, noeval); 306 307 op = last_token; 308 if (op < ARITH_BINOP_MIN || op >= ARITH_BINOP_MAX) 309 return a; 310 311 return binop2(a, op, ARITH_MAX_PREC, noeval); 312} 313 314static intmax_t 315and(int token, union a_token_val *val, int op, int noeval) 316{ 317 intmax_t a = binop(token, val, op, noeval); 318 intmax_t b; 319 320 op = last_token; 321 if (op != ARITH_AND) 322 return a; 323 324 VTRACE(DBG_ARITH, ("Arith: AND %jd%s\n", a, noeval ? " noeval" : "")); 325 326 token = arith_token(); 327 *val = a_t_val; 328 329 b = and(token, val, arith_token(), noeval | !a); 330 331 return a && b; 332} 333 334static intmax_t 335or(int token, union a_token_val *val, int op, int noeval) 336{ 337 intmax_t a = and(token, val, op, noeval); 338 intmax_t b; 339 340 op = last_token; 341 if (op != ARITH_OR) 342 return a; 343 344 VTRACE(DBG_ARITH, ("Arith: OR %jd%s\n", a, noeval ? " noeval" : "")); 345 346 token = arith_token(); 347 *val = a_t_val; 348 349 b = or(token, val, arith_token(), noeval | !!a); 350 351 return a || b; 352} 353 354static intmax_t 355cond(int token, union a_token_val *val, int op, int noeval) 356{ 357 intmax_t a = or(token, val, op, noeval); 358 intmax_t b; 359 intmax_t c; 360 361 if (last_token != ARITH_QMARK) 362 return a; 363 364 VTRACE(DBG_ARITH, ("Arith: ?: %jd%s\n", a, noeval ? " noeval" : "")); 365 366 b = assignment(arith_token(), noeval | !a); 367 368 if (last_token != ARITH_COLON) 369 arith_err("expecting ':'"); 370 371 token = arith_token(); 372 *val = a_t_val; 373 374 c = cond(token, val, arith_token(), noeval | !!a); 375 376 return a ? b : c; 377} 378 379static intmax_t 380assignment(int var, int noeval) 381{ 382 union a_token_val val = a_t_val; 383 int op = arith_token(); 384 intmax_t result; 385 char sresult[DIGITS(result) + 1]; 386 387 388 if (var != ARITH_VAR) 389 return cond(var, &val, op, noeval); 390 391 if (op != ARITH_ASS && (op < ARITH_ASS_MIN || op >= ARITH_ASS_MAX)) 392 return cond(var, &val, op, noeval); 393 394 VTRACE(DBG_ARITH, ("Arith: %s ASSIGN %d%s\n", val.name, op, 395 noeval ? " noeval" : "")); 396 397 result = assignment(arith_token(), noeval); 398 if (noeval) 399 return result; 400 401 if (op != ARITH_ASS) 402 result = do_binop(op - ARITH_ASS_GAP, 403 arith_lookupvarint(val.name), result); 404 snprintf(sresult, sizeof(sresult), ARITH_FORMAT_STR, result); 405 setvar(val.name, sresult, 0); 406 return result; 407} 408 409static intmax_t 410comma_list(int token, int noeval) 411{ 412 intmax_t result = assignment(token, noeval); 413 414 while (last_token == ARITH_COMMA) { 415 VTRACE(DBG_ARITH, ("Arith: comma discarding %jd%s\n", result, 416 noeval ? " noeval" : "")); 417 result = assignment(arith_token(), noeval); 418 } 419 420 return result; 421} 422 423intmax_t 424arith(const char *s, int lno) 425{ 426 struct stackmark smark; 427 intmax_t result; 428 const char *p; 429 int nls = 0; 430 431 setstackmark(&smark); 432 433 arith_lno = lno; 434 435 CTRACE(DBG_ARITH, ("Arith(\"%s\", %d) @%d\n", s, lno, arith_lno)); 436 437 /* check if it is possible we might reference LINENO */ 438 p = s; 439 while ((p = strchr(p, 'L')) != NULL) { 440 if (p[1] == 'I' && p[2] == 'N') { 441 /* if it is possible, we need to correct airth_lno */ 442 p = s; 443 while ((p = strchr(p, '\n')) != NULL) 444 nls++, p++; 445 VTRACE(DBG_ARITH, ("Arith found %d newlines\n", nls)); 446 arith_lno -= nls; 447 break; 448 } 449 p++; 450 } 451 452 arith_buf = arith_startbuf = s; 453 454 result = comma_list(arith_token(), 0); 455 456 if (last_token) 457 arith_err("expecting end of expression"); 458 459 popstackmark(&smark); 460 461 CTRACE(DBG_ARITH, ("Arith result=%jd\n", result)); 462 463 return result; 464} 465 466/* 467 * The let(1)/exp(1) builtin. 468 */ 469int 470expcmd(int argc, char **argv) 471{ 472 const char *p; 473 char *concat; 474 char **ap; 475 intmax_t i; 476 477 if (argc > 1) { 478 p = argv[1]; 479 if (argc > 2) { 480 /* 481 * Concatenate arguments. 482 */ 483 STARTSTACKSTR(concat); 484 ap = argv + 2; 485 for (;;) { 486 while (*p) 487 STPUTC(*p++, concat); 488 if ((p = *ap++) == NULL) 489 break; 490 STPUTC(' ', concat); 491 } 492 STPUTC('\0', concat); 493 p = grabstackstr(concat); 494 } 495 } else 496 p = ""; 497 498 i = arith(p, line_number); 499 500 out1fmt(ARITH_FORMAT_STR "\n", i); 501 return !i; 502} 503