1 /* pMARS -- a portable Memory Array Redcode Simulator
2  * Copyright (C) 1993-1996 Albert Ma, Na'ndor Sieben, Stefan Strack and Mintardjo Wangsawidjaja
3  * Copyright (C) 2000 Ilmari Karonen
4  *
5  * This program is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License as published by
7  * the Free Software Foundation; either version 2 of the License, or
8  * (at your option) any later version.
9  *
10  * This program is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13  * GNU General Public License for more details.
14  *
15  * You should have received a copy of the GNU General Public License
16  * along with this program; if not, write to the Free Software
17  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
18  */
19 
20 /*
21  * eval.c: expression evaluator used by assembler and debugger
22  * $Id: eval.c,v 1.3 2000/12/25 00:49:08 iltzu Exp $
23  */
24 
25 #include <ctype.h>
26 
27 #include "global.h"
28 
29 /*
30  * eval_expr - arithmetic expression evaluator
31  * by Stefan Strack, version 3 (pMARS v0.4.0+)
32  *
33  * usage:
34  *
35  * int eval_expr(char *expr, long *result); returns 0 if expression is ok, -1 if
36  * bad, -2 if attempted division by zero expr must be null-terminated and can
37  * contain whitespace characters (\t \n)
38  *
39  * -recursion-based -supports arbitrary levels of precedence and parentheses
40  * -supports nested unary minus and plus: 3--2 = 3-(-2) = 5
41  * -arithmetic operators: +,-,*,/,%,=
42  * -26 registers named "a" thru "z", assignment operator =
43  * -C-like comparison and logic operators: ==,!=,<,>,<=,>=,&&,||
44  *
45  */
46 
47 #define STANDALONE 0
48 #define BIGNUM 20                /* largest number taken */
49 
50 /* two-char operators */
51 enum {
52   EQUAL, NEQU, GTE, LTE, AND, OR, IDENT
53 };
54 
55 #ifdef DEBUG
56 #define X(c) (c==IDENT ? '#' :\
57               (c==EQUAL ? '=' :\
58                (c==AND ? '&' :\
59                 (c==OR ? '|' :\
60                  (c)))))
61 #endif
62 
63 #define TERMINAL(c) (((c)==')' || !(c)) ? 1 : 0)
64 /* order of precedence (high to low):
65    * / %
66    + -
67    > < == != >= <=
68    &&
69    ||
70    =
71  */
72 #define PRECEDENCE(op) (op=='*' || op=='/' || op=='%' ? 5 :\
73                         (op=='+' || op=='-' ? 4 :\
74                          (op=='>' || op=='<' || op==EQUAL || op==NEQU\
75                                   || op==GTE || op==LTE ? 3 :\
76                           (op==AND ? 2 : (op==OR ? 1 : 0)))))
77 #define SKIP_SPACE(e) while(isspace(*(e))) ++(e)
78 
79 /* function prototypes */
80 #ifdef NEW_STYLE
81 char   *eval(int prevPrec, long val, char operator, char *expr, long *result);
82 char   *getreg(char *expr, int regId, long *val);
83 char   *getval(char *expr, long *val);
84 char   *getop(char *expr, char *op);
85 long    calc(long x, long y, int op);
86 #else
87 char   *eval();
88 char   *getreg();
89 char   *getval();
90 char   *getop();
91 long    calc();
92 #endif
93 
94 /* global error flag */
95 int     evalerr;
96 
97 /* registers */
98 
99 static long regAr[26];
100 
101 /* kludge to implement several precedence levels */
102 
103 char    saveOper = 0;
104 
105 /*--------------------*/
106 long
calc(x,y,op)107 calc(x, y, op)
108   long    x;
109   long    y;
110   int     op;
111 {
112   long    z;
113 
114   switch (op) {
115   case '+':
116     if (evalerr == OK_EXPR && (x > 0 ?
117                                y > 0 && x > LONG_MAX - y :
118                                y < 0 && x < LONG_MIN - y ))
119       evalerr = OVERFLOW;
120     z = x + y;
121     break;
122   case '-':
123     if (evalerr == OK_EXPR && (x > 0 ?
124                                y < 0 && x > LONG_MAX + y :
125                                y > 0 && x < LONG_MIN + y ))
126       evalerr = OVERFLOW;
127     z = x - y;
128     break;
129   case '/':
130     if (y == 0) {
131       evalerr = DIV_ZERO;
132       z = 0;
133     } else
134       z = x / y;
135     break;
136   case '*':
137     if (evalerr == OK_EXPR && x != 0 && y != 0 &&
138         x != -1 && y != -1 &&    /* LONG_MIN/(-1) causes FP error! */
139         ((x > 0) == (y > 0) ?
140          LONG_MAX / y / x == 0 :
141          LONG_MIN / y / x == 0 ))
142       evalerr = OVERFLOW;
143     z = x * y;
144     break;
145   case '%':
146     if (y == 0) {
147       evalerr = DIV_ZERO;
148       z = 0;
149     } else
150       z = x % y;
151     break;
152   case AND:
153     z = x && y;
154     break;
155   case OR:
156     z = x || y;
157     break;
158   case EQUAL:
159     z = x == y;
160     break;
161   case NEQU:
162     z = x != y;
163     break;
164   case '<':
165     z = x < y;
166     break;
167   case '>':
168     z = x > y;
169     break;
170   case LTE:
171     z = x <= y;
172     break;
173   case GTE:
174     z = x >= y;
175     break;
176   case IDENT:                        /* the right-identity operator, used for
177                                  * initial call to eval() */
178     z = y;
179     break;
180   default:
181     z = 0;
182     evalerr = BAD_EXPR;
183   }
184   return z;
185 }
186 
187 /*--------------------*/
188 char   *
getop(expr,oper)189 getop(expr, oper)
190   char   *expr;
191   char   *oper;
192 {
193   char    ch;
194   switch (ch = *(expr++)) {
195   case '&':
196     if (*(expr++) == '&')
197       *oper = AND;
198     break;
199   case '|':
200     if (*(expr++) == '|')
201       *oper = OR;
202     break;
203   case '=':
204     if (*(expr++) == '=')
205       *oper = EQUAL;
206     break;
207   case '!':
208     if (*(expr++) == '=')
209       *oper = NEQU;
210     break;
211   case '<':
212     if (*expr == '=') {
213       ++expr;
214       *oper = LTE;
215     } else
216       *oper = '<';
217     break;
218   case '>':
219     if (*expr == '=') {
220       ++expr;
221       *oper = GTE;
222     } else
223       *oper = '>';
224     break;
225   default:
226     *oper = ch;
227     break;
228   }
229   return expr;
230 }
231 /*--------------------*/
232 char   *
getreg(expr,regId,val)233 getreg(expr, regId, val)
234   char   *expr;
235   int     regId;
236   long   *val;
237 {
238   SKIP_SPACE(expr);
239   if (*expr == '=' && *(expr + 1) != '=') {        /* assignment, not equality */
240     expr = eval(-1, 0L, IDENT, expr + 1, val);
241     regAr[regId] = *val;
242   } else
243     *val = regAr[regId];
244   return expr;
245 }
246 
247 /*--------------------*/
248 char   *
getval(expr,val)249 getval(expr, val)
250   char   *expr;
251   long   *val;
252 {
253   char    buffer[BIGNUM];
254   int     regId;
255   int     bufptr = 0;
256   long    accum;
257 
258   SKIP_SPACE(expr);
259   if (*expr == '(') {                /* parenthetical expression */
260     expr = eval(-1, 0L, IDENT, expr + 1, val);
261     if (*expr != ')')
262       evalerr = BAD_EXPR;
263     return expr + 1;
264   }
265   if (*expr == '-') {                /* unary minus */
266     expr = getval(expr + 1, &accum);
267     *val = accum * -1;
268     return expr;
269   } else if (*expr == '!') {        /* logical NOT */
270     expr = getval(expr + 1, &accum);
271     *val = (accum ? 0 : 1);
272     return expr;
273   } else if (*expr == '+')        /* unary plus */
274     return getval(expr + 1, val);
275   else if (((regId = (int) toupper(*expr)) >= 'A') && (regId <= 'Z'))
276     return getreg(expr + 1, regId - 'A', val);
277   else
278     while (isdigit(*expr))
279       buffer[bufptr++] = *expr++;
280   if (bufptr == 0)
281     evalerr = BAD_EXPR;                /* no digits */
282   buffer[bufptr] = 0;
283   sscanf(buffer, "%ld", val);
284   return expr;
285 }
286 
287 /*--------------------*/
288 #ifdef NEW_STYLE
289 char   *
eval(int prevPrec,long val1,char oper1,char * expr,long * result)290 eval(int prevPrec, long val1, char oper1, char *expr, long *result)
291 #else
292 char   *
293 eval(prevPrec, val1, oper1, expr, result)
294   int     prevPrec;
295   char    oper1, *expr;
296   long    val1, *result;
297 #endif
298 {
299   long    result2, val2;
300   char    oper2;
301   int     prec1, prec2;
302 
303 
304   expr = getval(expr, &val2);
305   SKIP_SPACE(expr);
306   if (TERMINAL(*expr)) {        /* trivial: expr is number or () */
307     *result = calc(val1, val2, oper1);
308     return expr;
309   }
310   expr = getop(expr, &oper2);
311   saveOper = 0;
312 
313   if ((prec1 = PRECEDENCE(oper1)) >= (prec2 = PRECEDENCE(oper2))) {
314     if (prec2 >= prevPrec || prec1 <= prevPrec) {
315       expr = eval(prec1, calc(val1, val2, oper1), oper2, expr, result);
316 #if 0
317       if (saveOper && PRECEDENCE(saveOper) >= prevPrec) {
318         expr = eval(prec2, *result, saveOper, expr, result);
319         saveOper = 0;
320         printf("Umpff!\n");
321       }
322 #endif
323 #ifdef DEBUG
324       fprintf(stderr, "%ld = ((%ld %c %ld) %c ..)\n", *result, val1, X(oper1), val2, X(oper2));
325 #endif
326     } else {
327       *result = calc(val1, val2, oper1);
328       saveOper = oper2;
329 #ifdef DEBUG
330       fprintf(stderr, "%ld = (%ld %c %ld)\n", *result, val1, X(oper1), val2);
331 #endif
332     }
333   } else {
334     expr = eval(prec1, val2, oper2, expr, &result2);
335     *result = calc(val1, result2, oper1);
336 
337     if (saveOper && PRECEDENCE(saveOper) >= prevPrec) {
338       expr = eval(prec2, *result, saveOper, expr, result);
339       saveOper = 0;
340 #ifdef DEBUG
341       fprintf(stderr, "%ld = .. ? (%ld %c (%ld %c ..))\n", *result,
342               val1, X(oper1), val2, X(oper2));
343 #endif
344     }
345 #ifdef DEBUG
346     else
347       fprintf(stderr, "%ld = (%ld %c (%ld %c ..))\n", *result, val1, X(oper1), val2, X(oper2));
348 #endif
349   }
350 
351   return expr;
352 }
353 
354 /*--------------------*/
355 void
reset_regs()356 reset_regs()
357 {
358   register int idx;
359 
360   for (idx = 0; idx < 26; ++idx)
361     regAr[idx] = 0L;
362 }
363 
364 /*--------------------*/
365 
366 void
set_reg(regChr,val)367 set_reg(regChr, val)
368   char    regChr;
369   long    val;
370 {
371   regAr[regChr - 'A'] = val;
372 }
373 
374 /*--------------------*/
375 int
eval_expr(expr,result)376 eval_expr(expr, result)                /* wrapper for eval() */
377   char   *expr;
378   long   *result;
379 {
380   evalerr = OK_EXPR;
381   if (*eval(-1, 0L, IDENT, expr, result) != 0)
382     evalerr = BAD_EXPR;                /* still chars left */
383   return (evalerr);
384 }
385 
386 #if STANDALONE
387 /*--------------------*/
388 void
main()389 main()
390 {                                /* test evaluator */
391   char    expr[80];
392   long    result;
393   int     err;
394 
395   printf("Enter infix expression: ");
396   gets(expr);
397 
398   if ((err = eval_expr(expr, &result)) >= OK_EXPR)
399     printf("Evaluation result:      %ld\n", result);
400   else if (err == DIV_ZERO)
401     printf("Division by zero in %s\n", expr);
402   else if (err == BAD_EXPR)
403     printf("Bad expression %s\n", expr);
404 }
405 #endif
406