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
69 static const char *arith_startbuf;
70
71 const char *arith_buf;
72 union a_token_val a_t_val;
73
74 static int last_token;
75
76 int arith_lno, arith_var_lno;
77
78 #define ARITH_PRECEDENCE(op, prec) [op - ARITH_BINOP_MIN] = prec
79
80 static 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
101 int expcmd(int, char **);
102
103 static void __dead
arith_err(const char * s)104 arith_err(const char *s)
105 {
106 error("arithmetic expression: %s: \"%s\"", s, arith_startbuf);
107 /* NOTREACHED */
108 }
109
110 static intmax_t
arith_lookupvarint(char * varname)111 arith_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
143 static inline int
arith_prec(int op)144 arith_prec(int op)
145 {
146
147 return prec[op - ARITH_BINOP_MIN];
148 }
149
150 static inline int
higher_prec(int op1,int op2)151 higher_prec(int op1, int op2)
152 {
153
154 return arith_prec(op1) < arith_prec(op2);
155 }
156
157 static intmax_t
do_binop(int op,intmax_t a,intmax_t b)158 do_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
203 static intmax_t assignment(int, int);
204 static intmax_t comma_list(int, int);
205
206 static intmax_t
primary(int token,union a_token_val * val,int op,int noeval)207 primary(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
268 static intmax_t
binop2(intmax_t a,int op,int precedence,int noeval)269 binop2(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
302 static intmax_t
binop(int token,union a_token_val * val,int op,int noeval)303 binop(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
314 static intmax_t
and(int token,union a_token_val * val,int op,int noeval)315 and(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
334 static intmax_t
or(int token,union a_token_val * val,int op,int noeval)335 or(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
354 static intmax_t
cond(int token,union a_token_val * val,int op,int noeval)355 cond(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
379 static intmax_t
assignment(int var,int noeval)380 assignment(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
409 static intmax_t
comma_list(int token,int noeval)410 comma_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
423 intmax_t
arith(const char * s,int lno)424 arith(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 */
469 int
expcmd(int argc,char ** argv)470 expcmd(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