1 #include "expression_parser.h"
2 #include <ctype.h>
3 #include <cstring>
4 #include <cstdio>
5 #include <cstdlib>
6
7 typedef enum {
8 EXOP_BRACKETL, EXOP_BRACKETR, EXOP_MEML, EXOP_MEMR, EXOP_MEMSIZE, EXOP_SIGNPLUS, EXOP_SIGNMINUS,
9 EXOP_BITNOT, EXOP_LOGNOT, EXOP_MUL, EXOP_DIV, EXOP_MOD, EXOP_ADD, EXOP_SUB,
10 EXOP_SHL, EXOP_SHR, EXOP_GREATEREQUAL, EXOP_GREATER, EXOP_LOWEREQUAL, EXOP_LOWER,
11 EXOP_EQUAL, EXOP_NOTEQUAL, EXOP_BITAND, EXOP_XOR, EXOP_BITOR, EXOP_LOGAND,
12 EXOP_LOGOR, EXOP_TERTIF, EXOP_TERTELSE, EXOP_NUMBER, EXOP_MEM, EXOP_NONE, EXOP_COUNT
13 } ExpressionOpcodeType;
14
15 typedef enum { EXCOMM_CONST, EXCOMM_CONST_FLOAT, EXCOMM_REF, EXCOMM_OP } ExpressionCommand;
16
17 static char expressionError[256];
18
19 typedef struct {
20 char Name[4];
21 unsigned char Priority;
22 unsigned char len;
23 unsigned char args;
24 bool sign;
25 } ExpressionOpcode;
26
27 const ExpressionOpcode ExpressionOpcodes[] = {
28 { "(", 25, 1, 0, false }, // EXOP_BRACKETL
29 { ")", 25, 1, 0, false }, // EXOP_BRACKETR
30 { "[", 4, 1, 0, false }, // EXOP_MEML
31 { "]", 4, 1, 0, false }, // EXOP_MEMR
32 { ",", 5, 1, 2, false }, // EXOP_MEMSIZE
33 { "+", 22, 1, 1, true }, // EXOP_SIGNPLUS
34 { "-", 22, 1, 1, true }, // EXOP_SIGNMINUS
35 { "~", 22, 1, 1, false }, // EXOP_BITNOT
36 { "!", 22, 1, 1, false }, // EXOP_LOGNOT
37 { "*", 21, 1, 2, false }, // EXOP_MUL
38 { "/", 21, 1, 2, false }, // EXOP_DIV
39 { "%", 21, 1, 2, false }, // EXOP_MOD
40 { "+", 20, 1, 2, false }, // EXOP_ADD
41 { "-", 20, 1, 2, false }, // EXOP_SUB
42 { "<<", 19, 2, 2, false }, // EXOP_SHL
43 { ">>", 19, 2, 2, false }, // EXOP_SHR
44 { ">=", 18, 2, 2, false }, // EXOP_GREATEREQUAL
45 { ">", 18, 1, 2, false }, // EXOP_GREATER
46 { "<=", 18, 2, 2, false }, // EXOP_LOWEREQUAL
47 { "<", 18, 1, 2, false }, // EXOP_LOWER
48 { "==", 17, 2, 2, false }, // EXOP_EQUAL
49 { "!=", 17, 2, 2, false }, // EXOP_NOTEQUAL
50 { "&", 16, 1, 2, false }, // EXOP_BITAND
51 { "^", 15, 1, 2, false }, // EXOP_XOR
52 { "|", 14, 1, 2, false }, // EXOP_BITOR
53 { "&&", 13, 2, 2, false }, // EXOP_LOGAND
54 { "||", 12, 2, 2, false }, // EXOP_LOGOR
55 { "?", 10, 1, 0, false }, // EXOP_TERTIF
56 { ":", 11, 1, 3, false }, // EXOP_TERTELSE
57 { "", 0, 0, 0, false }, // EXOP_NUMBER
58 { "[]", 0, 0, 1, false }, // EXOP_MEM
59 { "", 0, 0, 0, false } // EXOP_NONE
60 };
61
parseNumber(char * str,int defaultrad,int len,uint32_t & result)62 bool parseNumber(char* str, int defaultrad, int len, uint32_t& result)
63 {
64 int val = 0;
65 int r = 0;
66 if (len == 0) len = (int) strlen(str);
67
68 if (str[0] == '0' && tolower(str[1]) == 'x')
69 {
70 r = 16;
71 str+=2;
72 len-=2;
73 } else if (str[0] == '$')
74 {
75 r = 16;
76 str++;
77 len--;
78 } else if (str[0] == '0' && tolower(str[1]) == 'o')
79 {
80 r = 8;
81 str+=2;
82 len-=2;
83 } else {
84 if (!(str[0] >= '0' && str[0] <= '9')) return false;
85
86 if (tolower(str[len-1]) == 'b' && defaultrad != 16)
87 {
88 r = 2;
89 len--;
90 } else if (tolower(str[len-1]) == 'o')
91 {
92 r = 8;
93 len--;
94 } else if (tolower(str[len-1]) == 'h')
95 {
96 r = 16;
97 len--;
98 } else {
99 r = defaultrad;
100 }
101 }
102
103 switch (r)
104 {
105 case 2: // bin
106 while (len--)
107 {
108 if (*str != '0' && *str != '1') return false;
109 val = val << 1;
110 if (*str++ == '1')
111 {
112 val++;
113 }
114 }
115 break;
116 case 8: // oct
117 while (len--)
118 {
119 if (*str < '0' || *str > '7') return false;
120 val = val << 3;
121 val+=(*str++-'0');
122 }
123 break;
124 case 10: // dec
125 while (len--)
126 {
127 if (*str < '0' || *str > '9') return false;
128 val = val * 10;
129 val += (*str++ - '0');
130 }
131 break;
132 case 16: // hex
133 while (len--)
134 {
135 char c = tolower(*str++);
136 if ((c < '0' || c > '9') && (c < 'a' || c > 'f')) return false;
137 val = val << 4;
138
139 if (c >= 'a') val += c-'a'+10;
140 else val += c-'0';
141 }
142 break;
143 default:
144 return false;
145 }
146
147 result = val;
148 return true;
149 }
150
151 // Parse only a float, and return as float bits.
parseFloat(const char * str,int len,uint32_t & result)152 static bool parseFloat(const char *str, int len, uint32_t &result)
153 {
154 bool foundDecimal = false;
155 for (int i = 0; i < len; ++i)
156 {
157 if (str[i] == '.')
158 {
159 if (foundDecimal)
160 return false;
161 foundDecimal = true;
162 continue;
163 }
164 if (str[i] < '0' || str[i] > '9')
165 return false;
166 }
167
168 float f = (float)atof(str);
169 memcpy(&result, &f, sizeof(result));
170 return foundDecimal;
171 }
172
getExpressionOpcode(const char * str,int & ReturnLen,ExpressionOpcodeType LastOpcode)173 ExpressionOpcodeType getExpressionOpcode(const char* str, int& ReturnLen, ExpressionOpcodeType LastOpcode)
174 {
175 int longestlen = 0;
176 ExpressionOpcodeType result = EXOP_NONE;
177
178 for (int i = 0; i < EXOP_NUMBER; i++)
179 {
180 if (ExpressionOpcodes[i].sign == true &&
181 (LastOpcode == EXOP_NUMBER || LastOpcode == EXOP_BRACKETR)) continue;
182
183 int len = ExpressionOpcodes[i].len;
184 if (len > longestlen)
185 {
186 if (strncmp(ExpressionOpcodes[i].Name,str,len) == 0)
187 {
188 result = (ExpressionOpcodeType) i;
189 longestlen = len;
190 }
191 }
192 }
193
194 ReturnLen = longestlen;
195 return result;
196 }
197
isAlphaNum(char c)198 bool isAlphaNum(char c)
199 {
200 if ((c >= '0' && c <= '9') ||
201 (c >= 'A' && c <= 'Z') ||
202 (c >= 'a' && c <= 'z') ||
203 c == '@' || c == '_' || c == '$' || c == '.')
204 {
205 return true;
206 } else {
207 return false;
208 }
209 }
210
initPostfixExpression(const char * infix,IExpressionFunctions * funcs,PostfixExpression & dest)211 bool initPostfixExpression(const char* infix, IExpressionFunctions* funcs, PostfixExpression& dest)
212 {
213 expressionError[0] = 0;
214
215 int infixPos = 0;
216 int infixLen = (int)strlen(infix);
217 ExpressionOpcodeType lastOpcode = EXOP_NONE;
218 std::vector<ExpressionOpcodeType> opcodeStack;
219 dest.clear();
220
221 while (infixPos < infixLen)
222 {
223 char first = tolower(infix[infixPos]);
224 char subStr[256];
225 int subPos = 0;
226
227 if (first == ' ' || first == '\t')
228 {
229 infixPos++;
230 continue;
231 }
232
233 if (first >= '0' && first <= '9')
234 {
235 while (isAlphaNum(infix[infixPos]))
236 {
237 subStr[subPos++] = infix[infixPos++];
238 }
239 subStr[subPos] = 0;
240
241 uint32_t value;
242 bool isFloat = false;
243 if (parseFloat(subStr,subPos,value) == true)
244 isFloat = true;
245 else if (parseNumber(subStr,16,subPos,value) == false)
246 {
247 snprintf(expressionError, sizeof(expressionError), "Invalid number \"%s\"",subStr);
248 return false;
249 }
250
251 dest.push_back(ExpressionPair(isFloat?EXCOMM_CONST_FLOAT:EXCOMM_CONST,value));
252 lastOpcode = EXOP_NUMBER;
253 } else if ((first >= 'a' && first <= 'z') || first == '@')
254 {
255 while (isAlphaNum(infix[infixPos]))
256 {
257 subStr[subPos++] = infix[infixPos++];
258 }
259 subStr[subPos] = 0;
260
261 uint32_t value;
262 if (funcs->parseReference(subStr,value) == true)
263 {
264 dest.push_back(ExpressionPair(EXCOMM_REF,value));
265 lastOpcode = EXOP_NUMBER;
266 continue;
267 }
268
269 if (funcs->parseSymbol(subStr,value) == true)
270 {
271 dest.push_back(ExpressionPair(EXCOMM_CONST,value));
272 lastOpcode = EXOP_NUMBER;
273 continue;
274 }
275
276 snprintf(expressionError, sizeof(expressionError), "Invalid symbol \"%s\"",subStr);
277 return false;
278 } else {
279 int len;
280 ExpressionOpcodeType type = getExpressionOpcode(&infix[infixPos],len,lastOpcode);
281 if (type == EXOP_NONE)
282 {
283 snprintf(expressionError, sizeof(expressionError), "Invalid operator at \"%s\"",&infix[infixPos]);
284 return false;
285 }
286
287 switch (type)
288 {
289 case EXOP_BRACKETL:
290 case EXOP_MEML:
291 opcodeStack.push_back(type);
292 break;
293 case EXOP_BRACKETR:
294 while (true)
295 {
296 if (opcodeStack.empty())
297 {
298 snprintf(expressionError, sizeof(expressionError), "Closing parenthesis without opening one");
299 return false;
300 }
301 ExpressionOpcodeType t = opcodeStack[opcodeStack.size()-1];
302 opcodeStack.pop_back();
303 if (t == EXOP_BRACKETL) break;
304 dest.push_back(ExpressionPair(EXCOMM_OP,t));
305 }
306 break;
307 case EXOP_MEMR:
308 while (true)
309 {
310 if (opcodeStack.empty())
311 {
312 snprintf(expressionError, sizeof(expressionError), "Closing bracket without opening one");
313 return false;
314 }
315 ExpressionOpcodeType t = opcodeStack[opcodeStack.size()-1];
316 opcodeStack.pop_back();
317 if (t == EXOP_MEML)
318 {
319 dest.push_back(ExpressionPair(EXCOMM_OP,EXOP_MEM));
320 break;
321 }
322 dest.push_back(ExpressionPair(EXCOMM_OP,t));
323 }
324 type = EXOP_NUMBER;
325 break;
326 default:
327 if (opcodeStack.empty() == false)
328 {
329 int CurrentPriority = ExpressionOpcodes[type].Priority;
330 while (!opcodeStack.empty())
331 {
332 ExpressionOpcodeType t = opcodeStack[opcodeStack.size()-1];
333 opcodeStack.pop_back();
334
335 if (t == EXOP_BRACKETL || t == EXOP_MEML)
336 {
337 opcodeStack.push_back(t);
338 break;
339 }
340
341 if (ExpressionOpcodes[t].Priority >= CurrentPriority)
342 {
343 dest.push_back(ExpressionPair(EXCOMM_OP,t));
344 } else {
345 opcodeStack.push_back(t);
346 break;
347 }
348 }
349 }
350 opcodeStack.push_back(type);
351 break;
352 }
353 infixPos += len;
354 lastOpcode = type;
355 }
356 }
357
358 while (!opcodeStack.empty())
359 {
360 ExpressionOpcodeType t = opcodeStack[opcodeStack.size()-1];
361 opcodeStack.pop_back();
362
363 if (t == EXOP_BRACKETL) // opening bracket without closing one
364 {
365 snprintf(expressionError, sizeof(expressionError), "Parenthesis not closed");
366 return false;
367 }
368 dest.push_back(ExpressionPair(EXCOMM_OP,t));
369 }
370
371 #if 0 // only for testing
372 char test[1024];
373 int testPos = 0;
374 for (int i = 0; i < dest.size(); i++)
375 {
376 switch (dest[i].first)
377 {
378 case EXCOMM_CONST:
379 case EXCOMM_CONST_FLOAT:
380 testPos += sprintf(&test[testPos],"0x%04X ",dest[i].second);
381 break;
382 case EXCOMM_REF:
383 testPos += sprintf(&test[testPos],"r%d ",dest[i].second);
384 break;
385 case EXCOMM_OP:
386 testPos += sprintf(&test[testPos],"%s ",ExpressionOpcodes[dest[i].second].Name);
387 break;
388 };
389 }
390 #endif
391
392 return true;
393 }
394
parsePostfixExpression(PostfixExpression & exp,IExpressionFunctions * funcs,uint32_t & dest)395 bool parsePostfixExpression(PostfixExpression& exp, IExpressionFunctions* funcs, uint32_t& dest)
396 {
397 size_t num = 0;
398 uint32_t opcode;
399 std::vector<uint32_t> valueStack;
400 unsigned int arg[5];
401 float fArg[5];
402 bool useFloat = false;
403
404 while (num < exp.size())
405 {
406 switch (exp[num].first)
407 {
408 case EXCOMM_CONST: // konstante zahl
409 valueStack.push_back(exp[num++].second);
410 break;
411 case EXCOMM_CONST_FLOAT:
412 useFloat = true;
413 valueStack.push_back(exp[num++].second);
414 break;
415 case EXCOMM_REF:
416 useFloat = useFloat || funcs->getReferenceType(exp[num].second) == EXPR_TYPE_FLOAT;
417 opcode = funcs->getReferenceValue(exp[num++].second);
418 valueStack.push_back(opcode);
419 break;
420 case EXCOMM_OP: // opcode
421 opcode = exp[num++].second;
422 if (valueStack.size() < ExpressionOpcodes[opcode].args)
423 {
424 snprintf(expressionError, sizeof(expressionError), "Not enough arguments");
425 return false;
426 }
427 for (int l = 0; l < ExpressionOpcodes[opcode].args; l++)
428 {
429 arg[l] = valueStack[valueStack.size()-1];
430 valueStack.pop_back();
431 }
432 // In case of float representation.
433 memcpy(fArg, arg, sizeof(fArg));
434
435 switch (opcode)
436 {
437 case EXOP_MEMSIZE: // must be followed by EXOP_MEM
438 if (exp[num++].second != EXOP_MEM)
439 {
440 snprintf(expressionError, sizeof(expressionError), "Invalid memsize operator");
441 return false;
442 }
443
444 uint32_t val;
445 if(funcs->getMemoryValue(arg[1],arg[0],val,expressionError) == false)
446 {
447 return false;
448 }
449 valueStack.push_back(val);
450 break;
451 case EXOP_MEM:
452 {
453 uint32_t val;
454 if (funcs->getMemoryValue(arg[0],4,val,expressionError) == false)
455 {
456 return false;
457 }
458 valueStack.push_back(val);
459 }
460 break;
461 case EXOP_SIGNPLUS: // keine aktion nötig
462 break;
463 case EXOP_SIGNMINUS: // -0
464 if (useFloat)
465 valueStack.push_back((uint32_t)(0.0f - fArg[0]));
466 else
467 valueStack.push_back(0-arg[0]);
468 break;
469 case EXOP_BITNOT: // ~b
470 valueStack.push_back(~arg[0]);
471 break;
472 case EXOP_LOGNOT: // !b
473 valueStack.push_back(!arg[0]);
474 break;
475 case EXOP_MUL: // a*b
476 if (useFloat)
477 valueStack.push_back((uint32_t)(fArg[1] * fArg[0]));
478 else
479 valueStack.push_back(arg[1]*arg[0]);
480 break;
481 case EXOP_DIV: // a/b
482 if (arg[0] == 0)
483 {
484 snprintf(expressionError, sizeof(expressionError), "Division by zero");
485 return false;
486 }
487 if (useFloat)
488 valueStack.push_back((uint32_t)(fArg[1] / fArg[0]));
489 else
490 valueStack.push_back(arg[1]/arg[0]);
491 break;
492 case EXOP_MOD: // a%b
493 if (arg[0] == 0)
494 {
495 snprintf(expressionError, sizeof(expressionError), "Modulo by zero");
496 return false;
497 }
498 valueStack.push_back(arg[1]%arg[0]);
499 break;
500 case EXOP_ADD: // a+b
501 if (useFloat)
502 valueStack.push_back((uint32_t)(fArg[1] + fArg[0]));
503 else
504 valueStack.push_back(arg[1]+arg[0]);
505 break;
506 case EXOP_SUB: // a-b
507 if (useFloat)
508 valueStack.push_back((uint32_t)(fArg[1] - fArg[0]));
509 else
510 valueStack.push_back(arg[1]-arg[0]);
511 break;
512 case EXOP_SHL: // a<<b
513 valueStack.push_back(arg[1]<<arg[0]);
514 break;
515 case EXOP_SHR: // a>>b
516 valueStack.push_back(arg[1]>>arg[0]);
517 break;
518 case EXOP_GREATEREQUAL: // a >= b
519 if (useFloat)
520 valueStack.push_back(fArg[1]>=fArg[0]);
521 else
522 valueStack.push_back(arg[1]>=arg[0]);
523 break;
524 case EXOP_GREATER: // a > b
525 if (useFloat)
526 valueStack.push_back(fArg[1]>fArg[0]);
527 else
528 valueStack.push_back(arg[1]>arg[0]);
529 break;
530 case EXOP_LOWEREQUAL: // a <= b
531 if (useFloat)
532 valueStack.push_back(fArg[1]<=fArg[0]);
533 else
534 valueStack.push_back(arg[1]<=arg[0]);
535 break;
536 case EXOP_LOWER: // a < b
537 if (useFloat)
538 valueStack.push_back(fArg[1]<fArg[0]);
539 else
540 valueStack.push_back(arg[1]<arg[0]);
541 break;
542 case EXOP_EQUAL: // a == b
543 valueStack.push_back(arg[1]==arg[0]);
544 break;
545 case EXOP_NOTEQUAL: // a != b
546 valueStack.push_back(arg[1]!=arg[0]);
547 break;
548 case EXOP_BITAND: // a&b
549 valueStack.push_back(arg[1]&arg[0]);
550 break;
551 case EXOP_XOR: // a^b
552 valueStack.push_back(arg[1]^arg[0]);
553 break;
554 case EXOP_BITOR: // a|b
555 valueStack.push_back(arg[1]|arg[0]);
556 break;
557 case EXOP_LOGAND: // a && b
558 valueStack.push_back(arg[1]&&arg[0]);
559 break;
560 case EXOP_LOGOR: // a || b
561 valueStack.push_back(arg[1]||arg[0]);
562 break;
563 case EXOP_TERTIF: // darf so nicht vorkommen
564 return false;
565 case EXOP_TERTELSE: // exp ? exp : exp, else muss zuerst kommen!
566 if (exp[num++].second != EXOP_TERTIF)
567 {
568 snprintf(expressionError, sizeof(expressionError), "Invalid tertiary operator");
569 return false;
570 }
571 valueStack.push_back(arg[2]?arg[1]:arg[0]);
572 break;
573 }
574 break;
575 }
576 }
577
578 if (valueStack.size() != 1) return false;
579 dest = valueStack[0];
580 return true;
581 }
582
parseExpression(char * exp,IExpressionFunctions * funcs,uint32_t & dest)583 bool parseExpression(char* exp, IExpressionFunctions* funcs, uint32_t& dest)
584 {
585 PostfixExpression postfix;
586 if (initPostfixExpression(exp,funcs,postfix) == false) return false;
587 return parsePostfixExpression(postfix,funcs,dest);
588 }
589
getExpressionError()590 const char* getExpressionError()
591 {
592 if (expressionError[0] == 0) snprintf(expressionError, sizeof(expressionError), "Invalid expression");
593 return expressionError;
594 }
595