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 } 1177