?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Remove building with NOCRYPTO option
[minix.git] / minix / lib / libmagicrt / magic_eval_lib.c
blob6af7c9013423f68078a5844a3c256552e9688239
1 /* evaluate.c (C) 2000-2002 Kyzer/CSG. */
2 /* Released under the terms of the GNU General Public Licence version 2. */
3
4 #include "magic_eval_lib.h"
5 #include <ctype.h>
6 #include <limits.h>
7 #include <string.h>
8 #include <stdio.h>
9 #include <assert.h>
10
11 #if USE_MATH_LIB
12 #include <math.h>
13 #endif
14
15 #ifdef __MINIX
16 /* FIXME: due to the current linker command line ordering, parts of lib(min)c
17 * that are used exclusively by libmagicrt end up not being instrumented, which
18 * then causes problems transferring pointers such as _ctype_tab_ and
19 * _tolower_tab_. As a temporary workaround, we redefine the macros that use
20 * those pointers. This code is currently never triggered so it is not
21 * performance critical; obviously there are a million better ways to do this.
22 */
23 #undef isalpha
24 #define isalpha(c) ((unsigned)(((c) & ~0x20) - 'A') <= ('Z' - 'A'))
25 #undef isupper
26 #define isupper(c) ((unsigned)((c) - 'A') <= ('Z' - 'A'))
27 #undef islower
28 #define islower(c) ((unsigned)((c) - 'a') <= ('z' - 'a'))
29 #undef isdigit
30 #define isdigit(c) ((unsigned)((c) - '0') <= ('9' - '0'))
31 static inline int __isxdigit(c) {
32 return isdigit(c) || (c >= 'A' && c <= 'F') || (c >= 'a' && c <= 'f');
33 }
34 #undef isxdigit
35 #define isxdigit(c) (__isxdigit(c))
36 static inline int __isspace(c) {
37 switch (c) {
38 case ' ': case '\t': case '\n': case '\v': case '\f': case '\r': return 1;
39 default: return 0;
40 }
41 }
42 #undef isspace
43 #define isspace(c) (__isspace(c))
44 static inline int __tolower(c) {
45 return isupper(c) ? (c | 0x20) : c;
46 }
47 #undef tolower
48 #define tolower(c) (__tolower(c))
49 #endif /* __MINIX */
50
51 /* a token structure */
52 struct tok {
53 struct tok *next;
54 struct var *var;
55 char token;
56 struct val val;
57 char funcid, *name, *name_end;
58 };
59 #define REG_TOK_SIZE() offsetof(struct tok, val)
60 #define VAL_TOK_SIZE() offsetof(struct tok, funcid)
61 #define VAR_TOK_SIZE() sizeof(struct tok)
62
63 /* private memory header for tracked memory allocation */
64 struct memh {
65 struct memh *next;
66 void *ptr;
67 };
68
69 /* creates a new memory header for allocating memory */
70 static struct memh *create_mem();
71
72 /* allocates memory using a particular header */
73 static void *mem_alloc(struct memh *mh, size_t len);
74
75 /* frees all memory for a particular header */
76 static void free_mem(struct memh *mh);
77
78 /* token types */
79 enum {
80 /* parentheses */
81 TK_OPEN, TK_CLOSE,
82
83 /* variables and values */
84 TK_VAR, TK_VARQUOTE, TK_VAL,
85
86 /* binary operators */
87 TK_ADD, TK_SUB, TK_MUL, TK_MULI, TK_DIV,
88 TK_MOD, TK_POW, TK_AND, TK_OR, TK_BAND,
89 TK_BOR, TK_BXOR, TK_EQ, TK_NE, TK_LT, TK_GT,
90 TK_LE, TK_GE, TK_SHL, TK_SHR,
91
92 /* unary operators */
93 TK_ASSN, TK_NEG, TK_FUNC, TK_NOT, TK_BNOT,
94
95 /* special scan codes */
96 TK_BREAK, /* finish scanning, bring remainder of string forward */
97 TK_ERROR, /* abort scanning */
98 TK_SKIP /* ignore the character */
99 };
100
101 /* lookup table to do conversion [char -> token type] */
102 char scantable[UCHAR_MAX+1];
103 int scantable_ok = 0;
104
105 /* table of function names */
106 const char *functable[] = {
107 "acos", "asin", "atan", "cos", "cosh", "exp", "ln", "log",
108 "sin", "sinh", "sqr", "sqrt", "tan", "tanh", NULL
109 };
110
111 /* function ids (index to functable) */
112 enum {
113 F_ACOS, F_ASIN, F_ATAN, F_COS, F_COSH, F_EXP, F_LN, F_LOG,
114 F_SIN, F_SINH, F_SQR, F_SQRT, F_TAN, F_TANH
115 };
116
117 /* callbacks */
118 static get_var_cb_t get_var_cb = NULL;
119 static get_func_result_cb_t get_func_result_cb = NULL;
120 void eval_set_cb_get_var(get_var_cb_t cb) {
121 get_var_cb = cb;
122 }
123 void eval_set_cb_get_func_result(get_func_result_cb_t cb) {
124 get_func_result_cb = cb;
125 }
126
127 int same_str(const char *a, const char *b);
128 int same_str_len(const char *a, const char *b, int len);
129
130 void init_scantable(void);
131 int tokenize(struct memh *mh, char **string, struct tok **listptr);
132 int scan_number(char **stringptr, struct val *valptr);
133 int precedence(struct tok *t);
134 int eval(struct memh *mh, struct tok *list, struct vartable *vt,
135 struct val *result);
136 void prt_lst(struct tok *t);
137 void prt_tok(struct tok *t);
138
139 /*** FRONT-END ***/
140
141 int evaluate(char *expr, struct val *result, struct vartable *vartable) {
142 struct memh *mh = NULL;
143 int error = RESULT_OK, madevar = 0;
144 struct tok *list;
145 char *str;
146
147 /* ensure we have a variable table */
148 if (!vartable) madevar = 1, vartable = create_vartable();
149 if (!vartable) return ERROR_NOMEM;
150
151 init_scantable();
152 result->type = T_INT;
153 result->ival = 0;
154
155 if ((mh = create_mem())) {
156 if (expr && (str = (char *) mem_alloc(mh, strlen(expr)+1))) {
157 strcpy(str, expr);
158 while (*str) {
159 if ((error = tokenize(mh, &str, &list)) != RESULT_OK) break;
160 if ((error = eval(mh, list, vartable, result)) != RESULT_OK) break;
161 }
162 } else error = ERROR_NOMEM;
163 } else error = ERROR_NOMEM;
164
165 if(mh) free_mem(mh);
166 if (madevar) free_vartable(vartable);
167 return error;
168 }
169
170
171
172
173 /**** TOKENIZATION ***/
174
175 void init_scantable(void) {
176 int i;
177
178 if (scantable_ok) return;
179
180 for (i = 0; i <= UCHAR_MAX; i++)
181 scantable[i] =
182 (isalpha(i) || i == '_') ? TK_VAR :
183 (isdigit(i) ? TK_VAL :
184 (isspace(i) ? TK_SKIP :
185 TK_ERROR));
186
187 scantable['+'] = TK_ADD;
188 scantable['-'] = TK_SUB;
189 scantable['*'] = TK_MUL; /* also '**' = TK_POW */
190 scantable['/'] = TK_DIV;
191 scantable['%'] = TK_MOD;
192 scantable['$'] = TK_VAL; /* '$' starts a hexadecimal value */
193 scantable['.'] = TK_VAL; /* '.' starts a fractional value */
194 scantable['('] = TK_OPEN;
195 scantable[')'] = TK_CLOSE;
196 scantable[';'] = TK_BREAK;
197 scantable['='] = TK_ASSN; /* also '==' = TK_EQ */
198 scantable['~'] = TK_BNOT;
199 scantable['^'] = TK_BXOR;
200 scantable['&'] = TK_BAND; /* also '&&' = TK_AND */
201 scantable['|'] = TK_BOR; /* also '||' = TK_OR */
202 scantable['!'] = TK_NOT; /* also '!=' = TK_NE */
203 scantable['<'] = TK_LT; /* also '<<' = TK_SHL, '<=' = TK_LE */
204 scantable['>'] = TK_GT; /* also '>>' = TK_SHR, '>=' = TK_GE */
205 scantable['\''] = TK_VARQUOTE;
206
207 scantable_ok = 1;
208 }
209
210 #if !MEM_LOW_FOOTPRINT
211
212 int tokenize(struct memh *mh, char **string, struct tok **listptr) {
213 struct tok *list;
214 int idx = 0, i, len;
215 char *s, *name, c, c2, nt;
216
217 /* allocate a block of memory to hold the maximum amount of tokens */
218 i = strlen(*string) + 1;
219 list = (struct tok *) mem_alloc(mh, i * sizeof(struct tok));
220 if (!list) return ERROR_NOMEM;
221
222 for (s = *string; *s; s++) {
223 /* get token type of character and store into list */
224 c = list[idx].token = scantable[* (unsigned char *) s];
225
226 #if TOKEN_DEBUG
227 printf("tokenize: token %p code %d string %s\n", &list[idx], list[idx].token, s);
228 #endif
229
230 /* break out of the for loop on TK_BREAK */
231 if (c == TK_BREAK) { s++; break; }
232
233 switch (c) {
234 case TK_ERROR:
235 return ERROR_SYNTAX;
236
237 case TK_SKIP:
238 break;
239
240 /* most symbol-tokens fall under this one - nothing much to do */
241 case TK_OPEN: case TK_CLOSE: case TK_ADD: case TK_SUB:
242 case TK_MUL: case TK_DIV: case TK_MOD: case TK_BAND: case TK_BOR:
243 case TK_BXOR: case TK_BNOT: case TK_NOT: case TK_LT: case TK_GT:
244
245 /* check for 'double character' tokens */
246 c2 = s[1];
247 nt = 0;
248 if (c == TK_MUL && c2 == '*') nt = TK_POW;
249 if (c == TK_BAND && c2 == '&') nt = TK_AND;
250 if (c == TK_BOR && c2 == '|') nt = TK_OR;
251 if (c == TK_NOT && c2 == '=') nt = TK_NE;
252 if (c == TK_LT && c2 == '=') nt = TK_LE;
253 if (c == TK_LT && c2 == '<') nt = TK_SHL;
254 if (c == TK_GT && c2 == '=') nt = TK_GE;
255 if (c == TK_GT && c2 == '>') nt = TK_SHR;
256 if (nt) { list[idx].token = nt; s++; }
257
258 idx++;
259 break;
260
261 case TK_ASSN:
262 /* '=' = TK_ASSN, '==' = TK_EQ */
263 if (s[1] == '=') { list[idx++].token = TK_EQ; s++; break; }
264
265 /* if the last token was a variable, change it to an assignment */
266 if (idx <= 0 || list[idx-1].token != TK_VAR) return ERROR_SYNTAX;
267 list[idx-1].token = TK_ASSN;
268 break;
269
270 case TK_VAL:
271 if (!scan_number(&s, &list[idx++].val)) return ERROR_SYNTAX;
272 s--; /* wind back one for the loop's iterator */
273 break;
274
275 case TK_VAR:
276 case TK_VARQUOTE:
277 if(c == TK_VAR) {
278 list[idx].name = name = s;
279 c2 = scantable[(int)s[1]];
280 while (c2 == TK_VAR || c2 == TK_VAL) {
281 s++; /* skip to end of string */
282 c2 = scantable[(int)s[1]];
283 }
284 }
285 else {
286 if(!s[1] || scantable[(int)s[1]] == TK_VARQUOTE) {
287 return ERROR_SYNTAX;
288 }
289 list[idx].token = TK_VAR;
290 list[idx].name = name = ++s;
291 while (s[1] && scantable[(int)s[1]] != TK_VARQUOTE) s++; /* skip to end of string */
292 if(!s[1]) {
293 return ERROR_SYNTAX;
294 }
295 }
296 list[idx].name_end = s+1;
297 len = s+1 - name;
298 if(c == TK_VARQUOTE) {
299 s++;
300 }
301
302 if(scantable[(int)s[1]] == TK_OPEN) {
303 list[idx].token = TK_FUNC;
304 list[idx].funcid = 0;
305 /* look for matching function */
306 for (i = 0; functable[i]; i++) {
307 char *fname = functable[i];
308 if (same_str_len(name, fname, len) && strlen(fname) == len) {
309 list[idx].funcid = i+1;
310 break;
311 }
312 }
313 }
314 idx++;
315 break;
316 }
317 }
318
319 /* write back the final position of the tokenizer - either pointing at
320 * a null character, or the next expression to go */
321 *string = s;
322
323 /* lace up the tokens and null-terminate the strings */
324 if (idx > 0) {
325 for (i = 0; i < idx; i++) {
326 list[i].next = &list[i+1];
327 #if TOKEN_DEBUG
328 printf("tokenize: processed token %p code %d\n", &list[i], list[i].token);
329 #endif
330 if (list[i].token == TK_VAR || list[i].token == TK_ASSN || list[i].token == TK_FUNC)
331 *(list[i].name_end) = '\0';
332 }
333 list[idx-1].next = NULL;
334 *listptr = list;
335 }
336 else {
337 *listptr = NULL;
338 }
339
340 return RESULT_OK;
341 }
342
343 #else
344
345 int tokenize(struct memh *mh, char **string, struct tok **listptr) {
346 struct tok *tok = NULL, *last_tok = NULL;
347 int idx = 0, i, len;
348 char *s, *name, c, c2, nt;
349 int skip_alloc = 0;
350
351 for (s = *string; *s; s++) {
352 /* get token type of character and store into list */
353 c = scantable[* (unsigned char *) s];
354
355 /* break out of the for loop on TK_BREAK */
356 if(c == TK_BREAK) { s++; break; }
357 if(c == TK_ERROR) return ERROR_SYNTAX;
358
359 if(c == TK_SKIP) continue;
360
361 if(!skip_alloc) {
362 size_t tok_size;
363 last_tok = tok;
364 switch(c) {
365 case TK_VAL:
366 tok_size = VAL_TOK_SIZE();
367 break;
368 case TK_VAR:
369 case TK_VARQUOTE:
370 case TK_ASSN:
371 tok_size = VAR_TOK_SIZE();
372 break;
373 default:
374 tok_size = REG_TOK_SIZE();
375 break;
376 }
377 tok = (struct tok *) mem_alloc(mh, tok_size);
378 if(!tok) return ERROR_NOMEM;
379 tok->next = NULL;
380 if(last_tok) {
381 last_tok->next = tok;
382 }
383 else {
384 *listptr = tok;
385 }
386 }
387 else {
388 skip_alloc = 0;
389 }
390 tok->token = c;
391
392 #if TOKEN_DEBUG
393 printf("tokenize: token %p code %d string %s\n", tok, tok->token, s);
394 #endif
395
396 switch (c) {
397
398 /* most symbol-tokens fall under this one - nothing much to do */
399 case TK_OPEN: case TK_CLOSE: case TK_ADD: case TK_SUB:
400 case TK_MUL: case TK_DIV: case TK_MOD: case TK_BAND: case TK_BOR:
401 case TK_BXOR: case TK_BNOT: case TK_NOT: case TK_LT: case TK_GT:
402
403 /* check for 'double character' tokens */
404 c2 = s[1];
405 nt = 0;
406 if (c == TK_MUL && c2 == '*') nt = TK_POW;
407 if (c == TK_BAND && c2 == '&') nt = TK_AND;
408 if (c == TK_BOR && c2 == '|') nt = TK_OR;
409 if (c == TK_NOT && c2 == '=') nt = TK_NE;
410 if (c == TK_LT && c2 == '=') nt = TK_LE;
411 if (c == TK_LT && c2 == '<') nt = TK_SHL;
412 if (c == TK_GT && c2 == '=') nt = TK_GE;
413 if (c == TK_GT && c2 == '>') nt = TK_SHR;
414 if (nt) { tok->token = nt; s++; }
415
416 idx++;
417 break;
418
419 case TK_ASSN:
420 /* '=' = TK_ASSN, '==' = TK_EQ */
421 if (s[1] == '=') { tok->token = TK_EQ; idx++; s++; break; }
422
423 /* if the last token was a variable, change it to an assignment */
424 if (idx <= 0 || last_tok->token != TK_VAR) return ERROR_SYNTAX;
425 last_tok->token = TK_ASSN;
426 skip_alloc = 1;
427 break;
428
429 case TK_VAL:
430 if (!scan_number(&s, &tok->val)) return ERROR_SYNTAX;
431 idx++;
432 s--; /* wind back one for the loop's iterator */
433 break;
434
435 case TK_VAR:
436 case TK_VARQUOTE:
437 if(c == TK_VAR) {
438 tok->name = name = s;
439 c2 = scantable[(int)s[1]];
440 while (c2 == TK_VAR || c2 == TK_VAL) {
441 s++; /* skip to end of string */
442 c2 = scantable[(int)s[1]];
443 }
444 }
445 else {
446 if(!s[1] || scantable[(int)s[1]] == TK_VARQUOTE) {
447 return ERROR_SYNTAX;
448 }
449 tok->token = TK_VAR;
450 tok->name = name = ++s;
451 while (s[1] && scantable[(int)s[1]] != TK_VARQUOTE) s++; /* skip to end of string */
452 if(!s[1]) {
453 return ERROR_SYNTAX;
454 }
455 }
456 tok->name_end = s+1;
457 len = s+1 - name;
458 if(c == TK_VARQUOTE) {
459 s++;
460 }
461
462 if(scantable[(int)s[1]] == TK_OPEN) {
463 tok->token = TK_FUNC;
464 tok->funcid = 0;
465 /* look for matching function */
466 for (i = 0; functable[i]; i++) {
467 const char *fname = functable[i];
468 if (same_str_len(name, fname, len) && strlen(fname) == (size_t)len) {
469 tok->funcid = i+1;
470 break;
471 }
472 }
473 }
474 idx++;
475 break;
476 }
477 }
478
479 /* write back the final position of the tokenizer - either pointing at
480 * a null character, or the next expression to go */
481 *string = s;
482
483 /* lace up the tokens and null-terminate the strings */
484 if (idx > 0) {
485 tok = *listptr;
486 do {
487 #if TOKEN_DEBUG
488 printf("tokenize: processed token %p code %d\n", tok, tok->token);
489 #endif
490 if (tok->token == TK_VAR || tok->token == TK_ASSN || tok->token == TK_FUNC)
491 *(tok->name_end) = '\0';
492 tok = tok->next;
493 } while(tok);
494 }
495 else {
496 *listptr = NULL;
497 }
498
499 return RESULT_OK;
500 }
501
502 #endif
503
504 /* scans some text into a value */
505 int scan_number(char **stringptr, struct val *valptr) {
506 struct val v = { T_INT, 0, 0.0 };
507 char *s = *stringptr;
508 int c;
509 double dp;
510
511 /* test to see if it's a hex number */
512 if (s[0] == '$' || (s[0] == '0' && s[1] == 'x')) {
513 s += (s[1] == 'x') ? 2 : 1;
514 *stringptr = s;
515
516 for (; isxdigit(c = (int) *s); s++)
517 v.ival = (v.ival << 4)
518 + (isdigit(c) ? c-'0' : 0)
519 + (isupper(c) ? c-'A' + 10 : 0)
520 + (islower(c) ? c-'a' + 10 : 0);
521 }
522
523 /* must be a decimal integer or real */
524 else {
525 for (; isdigit(c = (int) *s); s++) v.ival = (v.ival * 10) + c-'0';
526 if (*s == '.') {
527 *stringptr = ++s;
528 v.type = T_REAL;
529 v.rval = (double) v.ival;
530 for (dp = 0.1; isdigit(c = (int) *s); s++, dp /= 10.0)
531 v.rval += dp * (double) (c-'0');
532 }
533 }
534
535 /* if no numeric chars have been read, it's a dud - return FAIL */
536 if (s == *stringptr) return 0;
537
538 /* otherwise, update position and return SUCCESS */
539 *stringptr = s;
540 *valptr = v;
541 return 1;
542 }
543
544
545 /*** EVALUATION ***/
546
547 /* returns the precedence of a token */
548 int precedence(struct tok *t) {
549 switch (t->token) {
550 case TK_FUNC: return 15;
551 case TK_MULI: return 14;
552 case TK_NEG: case TK_NOT: case TK_BNOT: return 13;
553 case TK_POW: return 12;
554 case TK_MUL: case TK_DIV: case TK_MOD: return 11;
555 case TK_ADD: case TK_SUB: return 10;
556 case TK_SHL: case TK_SHR: return 9;
557 case TK_LT: case TK_GT: case TK_LE: case TK_GE: return 8;
558 case TK_EQ: case TK_NE: return 7;
559 case TK_BAND: return 6;
560 case TK_BOR: case TK_BXOR: return 5;
561 case TK_AND: case TK_OR: return 4;
562 case TK_ASSN: return 3;
563 case TK_CLOSE: return 2;
564 case TK_OPEN: return 1;
565 }
566 return 0;
567 }
568
569
570 int eval(struct memh *mh, struct tok *list, struct vartable *vt,
571 struct val *result) {
572
573 static struct val newval = { T_INT, 0, 0.0 };
574
575 struct val tmp_val, *valstk, *x, *y;
576 struct tok open, close, *l, *r, *t, **opstk;
577 char lt, rt, token;
578 int vstk, ostk, vcnt = 0, ocnt = 0;
579 double xr, yr, rr = 0;
580 long xi, yi, ri = 0;
581 #if VAR_FROM_ENV
582 char *envtxt;
583 #endif
584
585 /* clear result before we do anything - and no tokens is no result */
586 *result = newval;
587 if (!list) return RESULT_OK;
588
589
590 /* CONVERSION OF RAW TOKENS INTO COMPLETE INFIX EXPRESSION */
591
592 /* wrap the token list in a pair of parentheses */
593 for (t = list; t->next; t = t->next)
594 ;
595 t->next = &close;
596 close.next = NULL; open.next = list; list = &open;
597 close.token = TK_CLOSE; open.token = TK_OPEN;
598
599 /* insert and change tokens as neccessary */
600 for (l=list, r=l->next; r->next; l=r, r=r->next) {
601 lt = l->token;
602 rt = r->token;
603
604 /* convert TK_SUBs that should be unary into TK_NEGs */
605 if (rt == TK_SUB && lt != TK_CLOSE && lt != TK_VAR && lt != TK_VAL)
606 r->token = TK_NEG;
607
608 /* insert implicit multiplication tokens */
609 if ((lt == TK_VAR || lt == TK_VAL || lt == TK_CLOSE)
610 && (rt == TK_VAR || rt == TK_VAL || rt == TK_OPEN || rt == TK_FUNC)) {
611 if (lt == rt) return ERROR_SYNTAX;
612 t = (struct tok *) mem_alloc(mh, sizeof(struct tok));
613 if (!t) return ERROR_NOMEM;
614 t->token = TK_MULI; l->next = t; t->next = r;
615 }
616 }
617
618 /* VARIABLE CHECKING */
619
620 vcnt = ocnt = 0;
621 for (t = list; t; t = t->next) {
622 lt = t->token;
623
624 /* count the number of values and operators */
625 if (lt == TK_VAR || lt == TK_VAL) vcnt++; else ocnt++;
626
627 /* if assigned variables don't exist, create a new blank one */
628 if (lt == TK_ASSN) {
629 if (!(t->var = get_var(vt, t->name)))
630 if (!(t->var = put_var(vt, t->name, &newval)))
631 return ERROR_NOMEM;
632 }
633
634 /* try to get vars from vartable - if not, try the environment */
635 else if (lt == TK_VAR) {
636 int var_found = 0;
637 if ((t->var = get_var(vt, t->name))) {
638 var_found = 1;
639 }
640 #if VAR_FROM_ENV
641 if(!var_found && (envtxt = getenv(t->name))) {
642 if (!scan_number(&envtxt, &tmp_val)) return ERROR_SYNTAX;
643 if (!(t->var = put_var(vt, t->name, &tmp_val))) return ERROR_NOMEM;
644 var_found = 1;
645 }
646 #endif
647 if(!var_found && get_var_cb && (get_var_cb(t->name, &tmp_val))) {
648 if (!(t->var = put_var(vt, t->name, &tmp_val))) return ERROR_NOMEM;
649 var_found = 1;
650 }
651 if(!var_found) {
652 return ERROR_VARNOTFOUND;
653 }
654 }
655 }
656
657 /* ALLOCATE STACKS */
658
659 /* allocate the operator stack and the value stack */
660 valstk = (struct val *) mem_alloc(mh, vcnt * sizeof(struct val));
661 opstk = (struct tok **) mem_alloc(mh, ocnt * sizeof(struct tok *));
662 if (!valstk || !opstk) return ERROR_NOMEM;
663
664 /* set the stack pointers to '0 items on stack' */
665 /* (the stack pointers are always set at the topmost stack item) */
666 ostk = vstk = -1;
667
668 /* MAIN EVALUATION LOOP */
669 prt_lst(list);
670 for (t = list; t; t=t->next) {
671 switch (t->token) {
672
673 /* unary operators always wait until after what follows is evaluated */
674 /* also, open parentheses are pushed to match where close ones stop */
675 case TK_OPEN:
676 case TK_ASSN: case TK_NEG: case TK_FUNC: case TK_NOT: case TK_BNOT:
677 opstk[++ostk] = t; break;
678
679 /* values go straight on the value stack */
680 case TK_VAL:
681 valstk[++vstk] = t->val;
682 break;
683
684 /* variables go straight on the value stack */
685 case TK_VAR:
686 valstk[++vstk] = t->var->val;
687 break;
688
689 /* this is where the action happens - all operations of a higher or same
690 * precedence are now executed. then, after that, we push the operator
691 * to the stack, or if it's a close paren, pull and expect an open paren
692 *
693 * it's assumed that all tokens in the token stream that aren't one of
694 * the previous cases must be the close bracket or a binary operator -
695 * that's why 'default' is used rather than all the names
696 */
697 default:
698 while (precedence(opstk[ostk]) >= precedence(t)) {
699 struct tok *op = opstk[ostk--];
700 #if EVAL_DEBUG
701 printf("eval: "); prt_tok(op); printf("\n");
702 #endif
703
704 /* there should always be at least a close bracket left here */
705 if (ostk < 0) return ERROR_SYNTAX;
706
707 /* we assume that all operators require at least one value */
708 /* on the stack, and check here */
709 if (vstk < 0) return ERROR_SYNTAX;
710
711 /* now we actually perform evaluations */
712 switch (token = op->token) {
713
714 /* binary (int/real) -> (int/real) */
715 case TK_ADD: case TK_SUB: case TK_MUL: case TK_MULI:
716
717 /* pull two values from the stack, y then x, and push 'x op y' */
718 if (vstk < 1) return ERROR_SYNTAX;
719 y = &valstk[vstk--]; x = &valstk[vstk];
720
721 /* if both values are integer, do integer operations only */
722 if (x->type == T_INT && y->type == T_INT) {
723 xi = x->ival;
724 yi = y->ival;
725 switch (token) {
726 case TK_MULI:
727 case TK_MUL: ri = (xi * yi); break;
728 case TK_ADD: ri = (xi + yi); break;
729 case TK_SUB: ri = (xi - yi); break;
730 }
731 /* push int-value result to value stack */
732 x->type = T_INT;
733 x->ival = ri;
734 }
735 else {
736 /* get real values - convert if neccessary */
737 xr = (x->type == T_REAL) ? x->rval : (double) x->ival;
738 yr = (y->type == T_REAL) ? y->rval : (double) y->ival;
739
740 switch (token) {
741 case TK_MULI:
742 case TK_MUL: rr = (xr * yr); break;
743 case TK_ADD: rr = (xr + yr); break;
744 case TK_SUB: rr = (xr - yr); break;
745 }
746 /* push real-value result to value stack */
747 x->type = T_REAL;
748 x->rval = rr;
749 }
750 break;
751
752
753
754 /* binary (int/real) -> int */
755 case TK_EQ: case TK_NE: case TK_LT:
756 case TK_GT: case TK_LE: case TK_GE:
757
758 if (vstk < 1) return ERROR_SYNTAX;
759 y = &valstk[vstk--]; x = &valstk[vstk];
760
761 if (x->type == T_INT && y->type == T_INT) {
762 xi = x->ival;
763 yi = y->ival;
764 switch (token) {
765 case TK_EQ: ri = (xi == yi); break;
766 case TK_NE: ri = (xi != yi); break;
767 case TK_LT: ri = (xi < yi); break;
768 case TK_GT: ri = (xi > yi); break;
769 case TK_LE: ri = (xi <= yi); break;
770 case TK_GE: ri = (xi >= yi); break;
771 }
772 }
773 else {
774 xr = (x->type == T_REAL) ? x->rval : (double) x->ival;
775 yr = (y->type == T_REAL) ? y->rval : (double) y->ival;
776 switch (token) {
777 case TK_EQ: ri = (xr == yr); break;
778 case TK_NE: ri = (xr != yr); break;
779 case TK_LT: ri = (xr < yr); break;
780 case TK_GT: ri = (xr > yr); break;
781 case TK_LE: ri = (xr <= yr); break;
782 case TK_GE: ri = (xr >= yr); break;
783 }
784 }
785 x->type = T_INT;
786 x->ival = ri;
787 break;
788
789
790 /* binary real -> real */
791 case TK_DIV: case TK_POW:
792
793 if (vstk < 1) return ERROR_SYNTAX;
794 y = &valstk[vstk--]; x = &valstk[vstk];
795 xr = (x->type == T_REAL) ? x->rval : (double) x->ival;
796 yr = (y->type == T_REAL) ? y->rval : (double) y->ival;
797
798 if (token == TK_DIV) {
799 if (yr == 0) return ERROR_DIV0;
800 x->rval = xr / yr;
801 }
802 else {
803 #if USE_MATH_LIB
804 x->rval = pow(xr, yr);
805 #else
806 x->rval = 0;
807 #endif
808 }
809 x->type = T_REAL;
810 break;
811
812
813 /* binary int -> int */
814 case TK_MOD: case TK_AND: case TK_OR:
815 case TK_BAND: case TK_BOR: case TK_BXOR:
816 case TK_SHL: case TK_SHR:
817
818 if (vstk < 1) return ERROR_SYNTAX;
819 y = &valstk[vstk--]; x = &valstk[vstk];
820 xi = (x->type == T_INT) ? x->ival : (long) x->rval;
821 yi = (y->type == T_INT) ? y->ival : (long) y->rval;
822
823 switch (token) {
824 case TK_MOD: if (yi == 0) return ERROR_DIV0;
825 ri = (xi % yi); break;
826 case TK_AND: ri = (xi && yi); break;
827 case TK_OR: ri = (xi || yi); break;
828 case TK_BAND: ri = (xi & yi); break;
829 case TK_BOR: ri = (xi | yi); break;
830 case TK_BXOR: ri = (xi ^ yi); break;
831 case TK_SHL: ri = (xi << yi); break;
832 case TK_SHR: ri = (xi >> yi); break;
833 }
834
835 x->type = T_INT;
836 x->ival = ri;
837 break;
838
839
840
841 /* unary real -> real */
842 case TK_FUNC:
843 x = &valstk[vstk];
844 if(op->funcid) {
845 #if USE_MATH_LIB
846 xr = (x->type == T_REAL) ? x->rval : (double) x->ival;
847 switch (op->funcid-1) {
848 case F_ACOS: xr = acos(xr); break;
849 case F_ASIN: xr = asin(xr); break;
850 case F_ATAN: xr = atan(xr); break;
851 case F_COS: xr = cos(xr); break;
852 case F_COSH: xr = cosh(xr); break;
853 case F_EXP: xr = exp(xr); break;
854 case F_LN: xr = log(xr); break;
855 case F_LOG: xr = log10(xr); break;
856 case F_SIN: xr = sin(xr); break;
857 case F_SINH: xr = sinh(xr); break;
858 case F_SQR: xr = xr * xr; break;
859 case F_SQRT: xr = sqrt(xr); break;
860 case F_TAN: xr = tan(xr); break;
861 case F_TANH: xr = tanh(xr); break;
862 default: xr = 0; break;
863 }
864 #else
865 xr = 0;
866 #endif
867 x->rval = xr;
868 x->type = T_REAL;
869 }
870 else {
871 if(!get_func_result_cb || !get_func_result_cb(op->name, x, x)) {
872 return ERROR_FUNCNOTFOUND;
873 }
874 }
875 break;
876
877
878 /* unary int -> int */
879 case TK_BNOT: case TK_NOT:
880
881 x = &valstk[vstk];
882 xi = (x->type == T_INT) ? x->ival : (long) x->rval;
883 if (token == TK_BNOT) {
884 x->ival = ~ xi;
885 }
886 else {
887 x->ival = ! xi;
888 }
889 x->type = T_INT;
890 break;
891
892
893 /* unary (int/real) -> (int/real) */
894 case TK_ASSN:
895 op->var->val = valstk[vstk];
896 break;
897
898
899 /* unary (int/real) -> (int/real) */
900 case TK_NEG:
901 x = &valstk[vstk];
902 if (x->type == T_INT)
903 x->ival = - x->ival;
904 else
905 x->rval = - x->rval;
906 break;
907
908 } /* end select (execution switch) */
909 } /* end while (precedence loop) */
910
911 /* back to the postfixified */
912
913 /* if we had a close paren, pull the matching open paren (error if
914 * we pull something else. otherwise push our new operator
915 */
916 if (t->token == TK_CLOSE) {
917 if (opstk[ostk--]->token != TK_OPEN) return ERROR_SYNTAX;
918 }
919 else {
920 opstk[++ostk] = t;
921 }
922 }
923 }
924
925 /* there should be exactly one value and no operators left on the stacks */
926 if (vstk != 0 || ostk != -1) return ERROR_SYNTAX;
927
928 /* return that value */
929 *result = valstk[0];
930 return RESULT_OK;
931 }
932
933
934
935
936
937 /** debugging things **/
938 #if EVAL_DEBUG
939 /* expression printer */
940 void prt_tok(struct tok *t) {
941 switch(t->token) {
942 case TK_OPEN: printf("( "); break;
943 case TK_CLOSE: printf(") "); break;
944
945 case TK_ADD: printf("+ "); break;
946 case TK_SUB: printf("- "); break;
947 case TK_MUL: printf("* "); break;
948 case TK_MULI: printf("*i "); break;
949 case TK_POW: printf("** "); break;
950 case TK_DIV: printf("/ "); break;
951 case TK_MOD: printf("%% "); break;
952
953 case TK_EQ: printf("== "); break;
954 case TK_NE: printf("!= "); break;
955 case TK_LT: printf("< "); break;
956 case TK_GT: printf("> "); break;
957 case TK_LE: printf("<= "); break;
958 case TK_GE: printf(">= "); break;
959
960 case TK_AND: printf("&& "); break;
961 case TK_BAND: printf("& "); break;
962 case TK_BNOT: printf("~ "); break;
963 case TK_BOR: printf("| "); break;
964 case TK_BXOR: printf("^ "); break;
965 case TK_NEG: printf("_ "); break;
966 case TK_NOT: printf("! "); break;
967 case TK_OR: printf("|| "); break;
968 case TK_SHL: printf("<< "); break;
969 case TK_SHR: printf(">> "); break;
970
971 case TK_ASSN: printf("%s = ", t->name); break;
972 case TK_FUNC: printf("%s() ", t->funcid ? functable[(int)t->funcid-1] : t->name); break;
973 case TK_VAL: if (t->val.type == T_INT)
974 printf("%ld ", t->val.ival);
975 else
976 printf("%g ", t->val.rval);
977 break;
978
979 case TK_VAR: printf("%s ", t->name); break;
980 default: printf("?? (%d)", t->token); break;
981 }
982 }
983
984 void prt_lst(struct tok *t) {
985 for (; t; t=t->next) prt_tok(t);
986 printf("\n");
987 }
988
989 #else
990 void prt_tok(struct tok *t) {}
991 void prt_lst(struct tok *t) {}
992 #endif
993
994
995
996 /*** UTILITY FUNCTIONS ***/
997
998 /* case-insensitive string comparison, TRUE or FALSE result */
999 int same_str(const char *a, const char *b) {
1000 if (!a || !b) return 0; /* false even if a == b == null */
1001 if (a == b) return 1;
1002
1003 #ifdef HAVE_STRCASECMP
1004 return (strcasecmp(a, b) == 0);
1005 #elif HAVE_STRCMPI
1006 return (strcmpi(a, b) == 0);
1007 #else
1008 while ((tolower((int)*a) == tolower((int)*b))) {
1009 if (!*a) return 1; /* if end of both strings, return true */
1010 a++; b++;
1011 }
1012 return 0; /* mismatch before end of string - return false */
1013 #endif
1014 }
1015
1016 /* case-insensitive string comparison with maximum length */
1017 int same_str_len(const char *a, const char *b, int len) {
1018 if (!a || !b) return 0; /* false even if a == b == null */
1019 if (len == 0) return 0;
1020 if (a == b) return 1;
1021
1022 #ifdef HAVE_STRNCASECMP
1023 return (strncasecmp(a, b, len) == 0);
1024 #elif HAVE_STRNCMPI
1025 return (strncmpi(a, b) == 0);
1026 #else
1027 while (--len && (tolower((int)*a) == tolower((int)*b))) {
1028 if (!*a) return 1; /* true if both strings equal & end before len */
1029 a++; b++;
1030 }
1031 /* result based on last char of allowed length */
1032 return (tolower((int)*a) == tolower((int)*b)) ? 1 : 0;
1033 #endif
1034 }
1035
1036 #if EVAL_MALLOC
1037 /* tracked memory allocation - create header */
1038 struct memh *create_mem() {
1039 struct memh *mh = (struct memh *) malloc(sizeof(struct memh));
1040 mh->next = NULL;
1041 mh->ptr = NULL;
1042 return mh;
1043 }
1044
1045 /* tracked memory allocation - allocate memory using header */
1046 void *mem_alloc(struct memh *mh, size_t len) {
1047 struct memh *mem = (struct memh *) malloc(len + sizeof(struct memh));
1048 if (!mem) return NULL;
1049 mem->next = mh->next;
1050 mh->next = mem;
1051 return mem->ptr = (void *) &mem[1];
1052 }
1053
1054 /* tracked memory allocation - free all memory in header */
1055 void free_mem(struct memh *mh) {
1056 struct memh *next;
1057 for (; mh; mh = next) {
1058 next = mh->next;
1059 free(mh);
1060 }
1061 }
1062
1063 #else
1064 #define MEM_BUFFER_LEN 4096
1065 #define MAX_NUM_BUFFERS 2
1066 char mem_buffer[MAX_NUM_BUFFERS][MEM_BUFFER_LEN];
1067 struct memh mem_headers[MAX_NUM_BUFFERS];
1068 int mem_idx[MAX_NUM_BUFFERS] = {0};
1069
1070 #define MEM_HEADER_TO_N(H) ((H)-mem_headers)
1071
1072 struct memh *create_mem() {
1073 int n;
1074 struct memh *mh;
1075 for(n=0;n<MAX_NUM_BUFFERS;n++) {
1076 if(mem_idx[n] == 0) {
1077 mem_idx[n] = 1;
1078 break;
1079 }
1080 }
1081
1082 if(n == MAX_NUM_BUFFERS) {
1083 #if MEM_DEBUG
1084 printf("create_mem: out of buffers\n", n);
1085 #endif
1086 return NULL;
1087 }
1088 #if MEM_DEBUG
1089 printf("create_mem: n is %d\n", n);
1090 #endif
1091 mh = &mem_headers[n];
1092 memset(mh, 0, sizeof(struct memh));
1093 return mh;
1094 }
1095
1096 void *mem_alloc(struct memh *mh, size_t len) {
1097 int n = MEM_HEADER_TO_N(mh);
1098 int mem_idx_n;
1099 struct memh *mem = NULL;
1100 len += sizeof(struct memh);
1101 mem_idx_n = mem_idx[n]-1;
1102 #if MEM_DEBUG
1103 printf("mem_alloc: len is %d, buffer num is %d, buffer idx is %d, buffer len is %d\n", len, n, mem_idx_n, MEM_BUFFER_LEN);
1104 #endif
1105 if(mem_idx_n + len > MEM_BUFFER_LEN) {
1106 #if MEM_DEBUG
1107 printf("mem_alloc: out of mem\n");
1108 #endif
1109 return NULL;
1110 }
1111 mem = (struct memh *) &mem_buffer[n][mem_idx_n];
1112 mem_idx[n] += len;
1113 mem->next = mh->next;
1114 mh->next = mem;
1115 return mem->ptr = (void *) &mem[1];
1116 }
1117
1118 void free_mem(struct memh *mh) {
1119 int n = MEM_HEADER_TO_N(mh);
1120 mem_idx[n] = 0;
1121 #if MEM_DEBUG
1122 printf("free_mem: n is %d\n", n);
1123 #endif
1124 }
1125
1126 #endif
1127
1128 /* creates an empty variable table */
1129 struct vartable *create_vartable() {
1130 struct memh *mh = create_mem();
1131 struct vartable *vt;
1132 if(!mh) {
1133 return NULL;
1134 }
1135 vt = (struct vartable *) mem_alloc(mh, sizeof(struct vartable));
1136 if (mh && vt) vt->mh = mh, vt->first = NULL; else free_mem(mh);
1137 return vt;
1138 }
1139
1140 /* frees a variable table */
1141 void free_vartable(struct vartable *vt) {
1142 free_mem(vt->mh);
1143 }
1144
1145 /* gets a variable out of a variable table */
1146 struct var *get_var(struct vartable *vt, char *name) {
1147 struct var *v;
1148 if (!vt || !name) return NULL;
1149 for (v = vt->first; v; v = v->next) if (same_str(v->name, name)) return v;
1150 return NULL;
1151 }
1152
1153 /* creates a new variable in a variable table */
1154 struct var *put_var(struct vartable *vt, char *name, struct val *value) {
1155 struct var *v;
1156 char *n;
1157
1158 if (!vt || !name || !value) return NULL;
1159
1160 if ((v = get_var(vt, name))) {
1161 v->val = *value;
1162 return v;
1163 }
1164
1165 v = (struct var *) mem_alloc(vt->mh, sizeof(struct var));
1166 n = (char *) mem_alloc(vt->mh, strlen(name)+1);
1167 if (v && n) {
1168 strcpy(n, name);
1169 v->name = n;
1170 v->val = *value;
1171 v->next = vt->first;
1172 vt->first = v;
1173 return v;
1174 }
1175 return NULL;
1176 }
MINIX 3 (repo.or.cz mirror)