Mercurial > hg > dmlib

comparison dmeval.c @ 0:32250b436bca

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Initial re-import.
author Matti Hamalainen <ccr@tnsp.org>
date Fri, 28 Sep 2012 01:54:23 +0300
parents
children 05eb24a608f0
comparison
equal deleted inserted replaced
-1:000000000000 0:32250b436bca
1 #include "dmeval.h"
2 #include <stdio.h>
3 #include <math.h>
4
5 #define DM_MAX_ID_LEN 16
6 #define DM_MAX_BUF 512
7 #define DM_STACK_SIZE 512
8
9 static DMValue int_clip(DMValue v)
10 {
11 return (v < -1.0f) ? -1.0f : ((v > 1.0f) ? 1.0f : v);
12 }
13
14
15 /* Some basic functions
16 */
17 static const DMEvalId dm_eval_basic[] =
18 {
19 { "sin", ID_FUNC, sin, NULL },
20 { "cos", ID_FUNC, cos, NULL },
21 { "clip", ID_FUNC, int_clip, NULL },
22 };
23
24 static const int ndm_eval_basic = sizeof(dm_eval_basic) / sizeof(dm_eval_basic[0]);
25
26
27 void dm_eval_err_v(DMEvalContext *ev, const char *fmt, va_list ap)
28 {
29 #if 1
30 char *tmp = dm_strdup_vprintf(fmt, ap);
31
32 ev->err = TRUE;
33
34 if (ev->errStr != NULL)
35 {
36 ev->errStr = dm_strdup_printf("%s%s", ev->errStr, tmp);
37 dmFree(tmp);
38 }
39 else
40 ev->errStr = tmp;
41 #else
42 vfprintf(stdout, fmt, ap);
43 #endif
44 }
45
46
47 void dm_eval_err(DMEvalContext *ev, const char *fmt, ...)
48 {
49 va_list ap;
50 va_start(ap, fmt);
51 dm_eval_err_v(ev, fmt, ap);
52 va_end(ap);
53 }
54
55
56 DMEvalId *dm_eval_find_id(DMEvalContext *ev, const char *name)
57 {
58 int i;
59 if (ev->ids == NULL)
60 return NULL;
61
62 for (i = 0; i < ev->nids; i++)
63 if (strcmp(ev->ids[i].name, name) == 0)
64 return &(ev->ids[i]);
65
66 return NULL;
67 }
68
69
70 static DMEvalId *dm_eval_add_id(DMEvalContext *ev, const char *name, const int type)
71 {
72 DMEvalId *id = dm_eval_find_id(ev, name);
73 if (id != NULL)
74 return NULL;
75
76 ev->ids = dmRealloc(ev->ids, sizeof(DMEvalId) * (ev->nids + 1));
77 if (ev->ids == NULL)
78 {
79 dm_eval_err(ev, "Could not reallocate eval ids array (#%d). Fatal error.\n", ev->nids + 1);
80 return NULL;
81 }
82
83 id = &(ev->ids[ev->nids]);
84 ev->nids++;
85
86 id->name = dm_strdup(name);
87 id->type = type;
88 id->func = NULL;
89 id->var = NULL;
90
91 return id;
92 }
93
94
95 DMEvalId *dm_eval_add_var(DMEvalContext *ev, const char *name, DMValue *var)
96 {
97 DMEvalId *id = dm_eval_add_id(ev, name, ID_VAR);
98 if (id == NULL)
99 return NULL;
100
101 id->var = var;
102 return id;
103 }
104
105
106 DMEvalId *dm_eval_add_func(DMEvalContext *ev, const char *name, DMValue (*func)(DMValue))
107 {
108 DMEvalId *id = dm_eval_add_id(ev, name, ID_VAR);
109 if (id == NULL)
110 return NULL;
111
112 id->func = func;
113 return id;
114 }
115
116
117
118 DMEvalContext *dm_eval_new(void)
119 {
120 int i;
121 DMEvalContext *ev = dmCalloc(1, sizeof(DMEvalContext));
122
123 if (ev == NULL)
124 return NULL;
125
126 for (i = 0; i < ndm_eval_basic; i++)
127 {
128 const DMEvalId *id = &dm_eval_basic[i];
129 DMEvalId *nid = dm_eval_add_id(ev, id->name, id->type);
130 nid->func = id->func;
131 }
132
133 return ev;
134 }
135
136 void dm_eval_free(DMEvalNode *node)
137 {
138 while (node != NULL)
139 {
140 DMEvalNode *next = node->next;
141
142 if (node->subexpr != NULL)
143 dm_eval_free(node->subexpr);
144
145 dmFree(node);
146 node = next;
147 }
148 }
149
150
151 void dm_eval_clear_err(DMEvalContext *ev)
152 {
153 if (ev == NULL)
154 return;
155
156 dmFree(ev->errStr);
157 ev->err = FALSE;
158 ev->errStr = NULL;
159 }
160
161
162 void dm_eval_close(DMEvalContext *ev)
163 {
164 int i;
165
166 if (ev == NULL)
167 return;
168
169 for (i = 0; i < ev->nids; i++)
170 dmFree(ev->ids[i].name);
171
172 dmFree(ev->ids);
173 dm_eval_clear_err(ev);
174 dmFree(ev);
175 }
176
177
178 static DMEvalNode *dm_eval_pop_node(DMEvalNode **list)
179 {
180 DMEvalNode *node;
181
182 if (*list == NULL)
183 return NULL;
184
185 node = (*list)->prev;
186
187 if (*list != node)
188 {
189 node->prev->next = NULL;
190 (*list)->prev = node->prev;
191 }
192 else
193 *list = NULL;
194
195 return node;
196 }
197
198
199 static DMEvalNode *dm_eval_insert_node(DMEvalNode **list, DMEvalNode *node)
200 {
201 if (*list != NULL)
202 {
203 node->prev = (*list)->prev;
204 (*list)->prev->next = node;
205 (*list)->prev = node;
206 }
207 else
208 {
209 *list = node;
210 node->prev = *list;
211 }
212
213 node->next = NULL;
214 return node;
215 }
216
217
218 static DMEvalNode *dm_eval_push_node(DMEvalNode **list, DMEvalNode *src)
219 {
220 DMEvalNode *node = dmCalloc(1, sizeof(DMEvalNode));
221 if (node == NULL)
222 return NULL;
223
224 node->op = src->op;
225 node->val = src->val;
226 node->id = src->id;
227 node->subexpr = src->subexpr;
228
229 return dm_eval_insert_node(list, node);
230 }
231
232
233 static DMEvalNode *dm_eval_add_node(DMEvalNode **list, const int op)
234 {
235 DMEvalNode *node = dmCalloc(1, sizeof(DMEvalNode));
236 if (node == NULL)
237 return NULL;
238
239 node->op = op;
240
241 return dm_eval_insert_node(list, node);
242 }
243
244
245 enum
246 {
247 PARSE_NONE = 0x0000,
248 PARSE_START = 0x1000,
249 PARSE_END = 0x2000,
250 PARSE_ERROR = 0x8000,
251
252 PARSE_IDENT = 0x0001,
253 PARSE_WS = 0x0002,
254 PARSE_CONST = 0x0004,
255 PARSE_OPER = 0x0008,
256 PARSE_SUBEXPR = 0x0010,
257 };
258
259 #define DM_CHECK(x) { if (mode & PARSE_ ## x ) { if (str[0]) strcat(str, " or "); strcat(str, # x ); } }
260
261 static char *dm_get_mode(int mode)
262 {
263 char str[128] = "";
264
265
266 DM_CHECK(START);
267 DM_CHECK(END);
268 DM_CHECK(IDENT);
269 DM_CHECK(WS);
270 DM_CHECK(CONST);
271 DM_CHECK(OPER);
272 DM_CHECK(SUBEXPR);
273
274 return dm_strdup(str);
275 }
276
277
278 static void dm_set_mode(DMEvalContext *ev, const int mode)
279 {
280 if (mode != PARSE_ERROR && mode != PARSE_START &&
281 ev->expect != PARSE_NONE &&
282 (mode & ev->expect) == 0)
283 {
284 char *tmp1 = dm_get_mode(ev->expect),
285 *tmp2 = dm_get_mode(mode);
286
287 dm_eval_err(ev, "Expected [%s], got %s.\n", tmp1, tmp2);
288 dmFree(tmp1);
289 dmFree(tmp2);
290 }
291
292 ev->prev = ev->mode;
293 ev->mode = mode;
294 }
295
296
297 static int dm_eval_parse_expr_do(DMEvalContext *ev, DMEvalNode **list, char **str, int depth)
298 {
299 char *c = *str;
300 char tmpStr[DM_MAX_BUF + 2];
301 int tmpStrLen = 0;
302 DMEvalNode *node = NULL, *func = NULL;
303 BOOL first = FALSE, decimal = FALSE;
304
305 ev->expect = PARSE_CONST | PARSE_IDENT | PARSE_SUBEXPR;
306 ev->mode = PARSE_START;
307
308 while (ev->mode != PARSE_ERROR && ev->mode != PARSE_END)
309 {
310 switch (ev->mode)
311 {
312 case PARSE_WS:
313 // Skip whitespace
314 if (isspace(*c))
315 c++;
316 else
317 dm_set_mode(ev, PARSE_START);
318 break;
319
320 case PARSE_SUBEXPR:
321 {
322 char *tmp = c + 1;
323
324 ev->expect = PARSE_SUBEXPR | PARSE_IDENT | PARSE_CONST;
325
326 if (func != NULL)
327 {
328 if (dm_eval_parse_expr_do(ev, &(func->subexpr), &tmp, depth + 1) != 0)
329 {
330 dm_eval_err(ev, "Function argument subexpression starting at '%s' contained errors.\n", c);
331 dm_set_mode(ev, PARSE_ERROR);
332 }
333
334 func = NULL;
335 }
336 else
337 {
338 if ((node = dm_eval_add_node(list, OP_SUBEXPR)) == NULL)
339 dm_set_mode(ev, PARSE_ERROR);
340 else
341 if (dm_eval_parse_expr_do(ev, &(node->subexpr), &tmp, depth + 1) != 0)
342 {
343 dm_eval_err(ev, "Subexpression starting at '%s' contained errors.\n", c);
344 dm_set_mode(ev, PARSE_ERROR);
345 }
346 }
347 if (ev->mode != PARSE_ERROR)
348 {
349 dm_set_mode(ev, PARSE_START);
350 ev->expect = PARSE_OPER | PARSE_END;
351 c = tmp;
352 }
353 }
354 break;
355
356 case PARSE_START:
357 // Start
358 if (*c == 0)
359 dm_set_mode(ev, PARSE_END);
360
361 else if (isspace(*c))
362 {
363 ev->mode = PARSE_WS;
364 }
365
366 else if (*c == ')')
367 {
368 if (depth > 0)
369 dm_set_mode(ev, PARSE_END);
370 else
371 {
372 dm_eval_err(ev, "Invalid nesting near '%s' (depth %d).\n", c, depth);
373 dm_set_mode(ev, PARSE_ERROR);
374 }
375 c++;
376 }
377
378 else if (*c == '(')
379 dm_set_mode(ev, PARSE_SUBEXPR);
380
381 else if (strchr("+-*/<>%&|!^", *c))
382 dm_set_mode(ev, PARSE_OPER);
383
384 else if (isdigit(*c) || *c == '.')
385 dm_set_mode(ev, PARSE_CONST);
386
387 else if (isalpha(*c) || *c == '_')
388 dm_set_mode(ev, PARSE_IDENT);
389
390 else
391 {
392 dm_eval_err(ev, "Syntax error near '%s' (depth %d).\n", c, depth);
393 dm_set_mode(ev, PARSE_ERROR);
394 }
395
396 first = TRUE;
397 break;
398
399 case PARSE_CONST:
400 if (first)
401 {
402 first = FALSE;
403 decimal = FALSE;
404 tmpStrLen = 0;
405
406 if (isdigit(*c) || *c == '-' || *c == '+' || *c == '.')
407 {
408 if (*c == '.')
409 decimal = TRUE;
410 tmpStr[tmpStrLen++] = *c++;
411 }
412 else
413 {
414 dm_eval_err(ev, "Invalid constant expression near '%s'.\n", c);
415 dm_set_mode(ev, PARSE_ERROR);
416 }
417 }
418 else
419 {
420 if (isdigit(*c) || (*c == '.' && !decimal))
421 {
422 if (*c == '.')
423 decimal = TRUE;
424 tmpStr[tmpStrLen++] = *c++;
425 }
426 else
427 {
428 tmpStr[tmpStrLen] = 0;
429
430 if ((node = dm_eval_add_node(list, OP_CONST)) == NULL)
431 {
432 dm_set_mode(ev, PARSE_ERROR);
433 break;
434 }
435
436 node->val = atof(tmpStr);
437 dm_set_mode(ev, PARSE_START);
438 ev->expect = PARSE_OPER | PARSE_END;
439 }
440 }
441 break;
442
443 case PARSE_OPER:
444 {
445 int op = OP_NONE;
446
447 switch (*c)
448 {
449 case '+': op = OP_ADD; c++; break;
450 case '-': op = OP_SUB; c++; break;
451 case '*': op = OP_MUL; c++; break;
452 case '/': op = OP_DIV; c++; break;
453 case '%': op = OP_MOD; c++; break;
454 case '&': op = OP_AND; c++; break;
455 case '|': op = OP_OR; c++; break;
456 case '>':
457 if (c[1] == '>')
458 {
459 c += 2;
460 op = OP_RSHIFT;
461 }
462 else
463 {
464 dm_eval_err(ev, "Syntax error near '%s'.\n", c);
465 dm_set_mode(ev, PARSE_ERROR);
466 }
467 break;
468
469 case '<':
470 if (c[1] == '<')
471 {
472 c += 2;
473 op = OP_LSHIFT;
474 }
475 else
476 {
477 dm_eval_err(ev, "Syntax error near '%s'.\n", c);
478 dm_set_mode(ev, PARSE_ERROR);
479 }
480 break;
481
482 default:
483 dm_eval_err(ev, "Unknown operator '%c'.\n", *c);
484 dm_set_mode(ev, PARSE_ERROR);
485 }
486
487 if (op != OP_NONE)
488 {
489 if ((node = dm_eval_add_node(list, op)) != NULL)
490 {
491 ev->expect = PARSE_IDENT | PARSE_CONST | PARSE_SUBEXPR;
492 dm_set_mode(ev, PARSE_START);
493 }
494 else
495 dm_set_mode(ev, PARSE_ERROR);
496 }
497 }
498 break;
499
500 case PARSE_IDENT:
501 if (isalnum(*c) || *c == '_')
502 {
503 if (first)
504 {
505 tmpStrLen = 0;
506 first = FALSE;
507 }
508
509 if (tmpStrLen < DM_MAX_ID_LEN)
510 tmpStr[tmpStrLen++] = *c++;
511 else
512 {
513 tmpStr[tmpStrLen] = 0;
514 dm_eval_err(ev, "Identifier too long! ('%s')\n", tmpStr);
515 }
516 }
517 else
518 {
519 tmpStr[tmpStrLen] = 0;
520 DMEvalId *id = dm_eval_find_id(ev, tmpStr);
521 if (id != NULL)
522 {
523 if ((node = dm_eval_add_node(list, id->type == ID_FUNC ? OP_FUNC : OP_VAR)) != NULL)
524 {
525 node->id = id;
526 if (id->type == ID_FUNC)
527 {
528 func = node;
529 ev->expect = PARSE_SUBEXPR;
530 }
531 else
532 ev->expect = PARSE_END | PARSE_OPER;
533
534 dm_set_mode(ev, PARSE_START);
535 }
536 else
537 dm_set_mode(ev, PARSE_ERROR);
538 }
539 else
540 {
541 dm_eval_err(ev, "No such identifier '%s'.\n", tmpStr);
542 dm_set_mode(ev, PARSE_ERROR);
543 }
544 }
545 break;
546 }
547 }
548
549 *str = c;
550
551 return (ev->mode == PARSE_ERROR) ? -1 : 0;
552 }
553
554
555 int dm_eval_parse_expr(DMEvalContext *ev, char *expr, DMEvalNode **result)
556 {
557 int ret;
558
559 if (ev == NULL || result == NULL)
560 return -1;
561
562 ret = dm_eval_parse_expr_do(ev, result, &expr, 0);
563
564 return ret;
565 }
566
567
568 static const char *dm_oper_names[OP_NOPERS] =
569 {
570 "NONE",
571 "+",
572 "-",
573 "*",
574 "/",
575 "%",
576
577 "<<",
578 ">>",
579
580 "&",
581 "|",
582 "^",
583
584 "FUNC",
585 "VAR",
586 "SUBEXPR",
587 "CONST"
588 };
589
590
591 static void dm_print_optree_do(DMEvalContext *ev, DMEvalNode *node, const int level)
592 {
593 while (node != NULL)
594 {
595 switch (node->op)
596 {
597 case OP_FUNC:
598 printf("%s(", node->id != NULL ? node->id->name : "?ERROR");
599 dm_print_optree_do(ev, node->subexpr, level + 1);
600 printf(")");
601 break;
602
603 case OP_VAR:
604 printf("%s", node->id != NULL ? node->id->name : "?ERROR");
605 break;
606
607 case OP_CONST:
608 printf("%.1f", node->val);
609 break;
610
611 case OP_SUBEXPR:
612 printf("(");
613 if (node->subexpr != NULL)
614 dm_print_optree_do(ev, node->subexpr, level + 1);
615 else
616 printf("?ERROR");
617 printf(")");
618 break;
619
620 default:
621 if (node->op > 0 && node->op < OP_NOPERS)
622 printf("%s", dm_oper_names[node->op]);
623 else
624 printf("ERROR!");
625 break;
626 }
627 node = node->next;
628 }
629 }
630
631
632 void dm_print_optree(DMEvalContext *ev, DMEvalNode *node)
633 {
634 dm_print_optree_do(ev, node, 0);
635 printf("\n");
636 }
637
638
639 /*
640 operator precedence:
641 HIGHEST
642 "()"
643
644 "*"
645 "/"
646 "%"
647
648 "+"
649 "-"
650
651 "<<"
652 ">>"
653
654 "&"
655 "^"
656 "|"
657 LOWEST
658 */
659
660 int dm_eval_reorder(DMEvalContext *ev, DMEvalNode *node, DMEvalNode **result)
661 {
662 DMEvalNode *list = NULL;
663
664 while (node != NULL)
665 {
666 DMEvalNode *tmp;
667
668 switch (node->op)
669 {
670 case OP_SUBEXPR:
671 case OP_FUNC:
672 if ((tmp = dm_eval_push_node(&list, node)) == NULL)
673 return -1;
674
675 if (dm_eval_reorder(ev, node->subexpr, &(tmp->subexpr)) != 0)
676 return -2;
677 break;
678
679 case OP_MUL:
680 case OP_DIV:
681 case OP_MOD:
682 if ((tmp = dm_eval_pop_node(&list)) != NULL)
683 {
684 DMEvalNode *sub;
685
686 if ((sub = dm_eval_add_node(&list, OP_SUBEXPR)) == NULL)
687 return -3;
688
689 dm_eval_push_node(&(sub->subexpr), tmp);
690 dm_eval_add_node(&(sub->subexpr), node->op);
691 node = node->next;
692 if (node != NULL)
693 {
694 if (node->op == OP_FUNC || node->op == OP_SUBEXPR)
695 {
696 if ((tmp = dm_eval_push_node(&(sub->subexpr), node)) == NULL)
697 return -178;
698
699 if (dm_eval_reorder(ev, node->subexpr, &(tmp->subexpr)) != 0)
700 return -66;
701 }
702 else
703 dm_eval_push_node(&(sub->subexpr), node);
704 }
705 else
706 return -72;
707 }
708 else
709 return -24;
710 break;
711
712 case OP_LSHIFT:
713 case OP_RSHIFT:
714
715 case OP_ADD:
716 case OP_SUB:
717
718 case OP_AND:
719 case OP_XOR:
720 case OP_OR:
721
722 case OP_VAR:
723 case OP_CONST:
724 if (dm_eval_push_node(&list, node) == NULL)
725 return -32;
726 break;
727
728 default:
729 dm_eval_err(ev, "Invalid opcode %d in node %p.\n", node->op, node);
730 return -4;
731 }
732
733 node = node->next;
734 }
735
736 *result = list;
737 return 0;
738 }
739
740
741 static int dm_eval_get(DMEvalContext *ev, DMEvalNode *node, DMValue *result)
742 {
743 DMValue tmp;
744
745 if (node == NULL)
746 return -32;
747
748 switch (node->op)
749 {
750 case OP_VAR:
751 *result = *(node->id->var);
752 break;
753
754 case OP_CONST:
755 *result = node->val;
756 break;
757
758 case OP_SUBEXPR:
759 if (dm_eval_exec(ev, node->subexpr, result) != 0)
760 return -1;
761 break;
762
763 case OP_FUNC:
764 if (dm_eval_exec(ev, node->subexpr, &tmp) != 0)
765 return -1;
766
767 *result = node->id->func(tmp);
768 break;
769
770 default:
771 return -16;
772 }
773
774 return 0;
775 }
776
777
778 int dm_eval_exec(DMEvalContext *ev, DMEvalNode *tree, DMValue *presult)
779 {
780 DMValue result;
781 DMEvalNode *node = tree;
782
783 while (node != NULL)
784 {
785 DMValue tmp;
786
787 switch (node->op)
788 {
789 case OP_LSHIFT:
790 case OP_RSHIFT:
791
792 case OP_AND:
793 case OP_XOR:
794 case OP_OR:
795
796 case OP_MUL:
797 case OP_DIV:
798 case OP_MOD:
799 if (dm_eval_get(ev, node->next, &tmp) != 0)
800 return -6;
801
802 switch (node->op)
803 {
804 case OP_DIV:
805 if (tmp == 0)
806 {
807 dm_eval_err(ev, "Division by zero.\n");
808 return -1;
809 }
810 result /= tmp;
811 break;
812
813 case OP_MUL: result *= tmp; break;
814
815 case OP_MOD:
816 if (tmp == 0)
817 {
818 dm_eval_err(ev, "Division by zero.\n");
819 return -1;
820 }
821 result = DMCONVTYPE result % DMCONVTYPE tmp;
822 break;
823
824 case OP_LSHIFT: result = DMCONVTYPE result << DMCONVTYPE tmp; break;
825 case OP_RSHIFT: result = DMCONVTYPE result >> DMCONVTYPE tmp; break;
826
827 case OP_AND: result = DMCONVTYPE result & DMCONVTYPE tmp; break;
828 case OP_OR: result = DMCONVTYPE result | DMCONVTYPE tmp; break;
829 case OP_XOR: result = DMCONVTYPE result ^ DMCONVTYPE tmp; break;
830 }
831
832 node = node->next;
833 break;
834
835 case OP_ADD:
836 case OP_SUB:
837 if (dm_eval_get(ev, node->next, &tmp) != 0)
838 return -6;
839
840 switch (node->op)
841 {
842 case OP_ADD: result += tmp; break;
843 case OP_SUB: result -= tmp; break;
844 }
845
846 node = node->next;
847 break;
848
849 default:
850 if (dm_eval_get(ev, node, &result) != 0)
851 {
852 dm_eval_err(ev, "Invalid opcode %d in node %p.\n", node->op, node);
853 return -4;
854 }
855 }
856
857 node = node->next;
858 }
859
860 *presult = result;
861 return 0;
862 }