--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/dmeval.c	Fri Sep 28 01:54:23 2012 +0300
@@ -0,0 +1,862 @@
+#include "dmeval.h"
+#include <stdio.h>
+#include <math.h>
+
+#define DM_MAX_ID_LEN  16
+#define DM_MAX_BUF     512
+#define DM_STACK_SIZE  512
+
+static DMValue int_clip(DMValue v)
+{
+    return (v < -1.0f) ? -1.0f : ((v > 1.0f) ? 1.0f : v);
+}
+
+
+/* Some basic functions
+ */
+static const DMEvalId dm_eval_basic[] =
+{
+    { "sin",  ID_FUNC, sin, NULL },
+    { "cos",  ID_FUNC, cos, NULL },
+    { "clip", ID_FUNC, int_clip, NULL },
+};
+
+static const int ndm_eval_basic = sizeof(dm_eval_basic) / sizeof(dm_eval_basic[0]);
+
+
+void dm_eval_err_v(DMEvalContext *ev, const char *fmt, va_list ap)
+{
+#if 1
+    char *tmp = dm_strdup_vprintf(fmt, ap);
+    
+    ev->err = TRUE;
+
+    if (ev->errStr != NULL)
+    {
+        ev->errStr = dm_strdup_printf("%s%s", ev->errStr, tmp);
+        dmFree(tmp);
+    }
+    else
+        ev->errStr = tmp;
+#else
+    vfprintf(stdout, fmt, ap);
+#endif
+}
+
+
+void dm_eval_err(DMEvalContext *ev, const char *fmt, ...)
+{
+    va_list ap;
+    va_start(ap, fmt);
+    dm_eval_err_v(ev, fmt, ap);
+    va_end(ap);
+}
+
+
+DMEvalId *dm_eval_find_id(DMEvalContext *ev, const char *name)
+{
+    int i;
+    if (ev->ids == NULL)
+        return NULL;
+
+    for (i = 0; i < ev->nids; i++)
+        if (strcmp(ev->ids[i].name, name) == 0)
+            return &(ev->ids[i]);
+    
+    return NULL;
+}
+
+
+static DMEvalId *dm_eval_add_id(DMEvalContext *ev, const char *name, const int type)
+{
+    DMEvalId *id = dm_eval_find_id(ev, name);
+    if (id != NULL)
+        return NULL;
+
+    ev->ids = dmRealloc(ev->ids, sizeof(DMEvalId) * (ev->nids + 1));
+    if (ev->ids == NULL)
+    {
+        dm_eval_err(ev, "Could not reallocate eval ids array (#%d). Fatal error.\n", ev->nids + 1);
+        return NULL;
+    }
+    
+    id = &(ev->ids[ev->nids]);
+    ev->nids++;
+
+    id->name = dm_strdup(name);
+    id->type = type;
+    id->func = NULL;
+    id->var = NULL;
+    
+    return id;
+}
+
+
+DMEvalId *dm_eval_add_var(DMEvalContext *ev, const char *name, DMValue *var)
+{
+    DMEvalId *id = dm_eval_add_id(ev, name, ID_VAR);
+    if (id == NULL)
+        return NULL;
+    
+    id->var = var;
+    return id;
+}
+
+
+DMEvalId *dm_eval_add_func(DMEvalContext *ev, const char *name, DMValue (*func)(DMValue))
+{
+    DMEvalId *id = dm_eval_add_id(ev, name, ID_VAR);
+    if (id == NULL)
+        return NULL;
+    
+    id->func = func;
+    return id;
+}
+
+
+
+DMEvalContext *dm_eval_new(void)
+{
+    int i;
+    DMEvalContext *ev = dmCalloc(1, sizeof(DMEvalContext));
+
+    if (ev == NULL)
+        return NULL;
+
+    for (i = 0; i < ndm_eval_basic; i++)
+    {
+        const DMEvalId *id = &dm_eval_basic[i];
+        DMEvalId *nid = dm_eval_add_id(ev, id->name, id->type);
+        nid->func = id->func;
+    }
+
+    return ev;
+}
+
+void dm_eval_free(DMEvalNode *node)
+{
+    while (node != NULL)
+    {
+        DMEvalNode *next = node->next;
+
+        if (node->subexpr != NULL)
+            dm_eval_free(node->subexpr);
+
+        dmFree(node);
+        node = next;
+    }
+}
+
+
+void dm_eval_clear_err(DMEvalContext *ev)
+{
+    if (ev == NULL)
+        return;
+    
+    dmFree(ev->errStr);
+    ev->err = FALSE;
+    ev->errStr = NULL;
+}
+
+
+void dm_eval_close(DMEvalContext *ev)
+{
+    int i;
+
+    if (ev == NULL)
+        return;
+
+    for (i = 0; i < ev->nids; i++)
+        dmFree(ev->ids[i].name);
+
+    dmFree(ev->ids);
+    dm_eval_clear_err(ev);
+    dmFree(ev);
+}
+
+
+static DMEvalNode *dm_eval_pop_node(DMEvalNode **list)
+{
+    DMEvalNode *node;
+
+    if (*list == NULL)
+        return NULL;
+
+    node = (*list)->prev;
+
+    if (*list != node)
+    {
+        node->prev->next = NULL;
+        (*list)->prev = node->prev;
+    }
+    else
+        *list = NULL;
+
+    return node;
+}
+
+
+static DMEvalNode *dm_eval_insert_node(DMEvalNode **list, DMEvalNode *node)
+{
+    if (*list != NULL)
+    {
+        node->prev = (*list)->prev;
+        (*list)->prev->next = node;
+        (*list)->prev = node;
+    }
+    else
+    {
+        *list = node;
+        node->prev = *list;
+    }
+
+    node->next = NULL;
+    return node;
+}
+
+
+static DMEvalNode *dm_eval_push_node(DMEvalNode **list, DMEvalNode *src)
+{
+    DMEvalNode *node = dmCalloc(1, sizeof(DMEvalNode));
+    if (node == NULL)
+        return NULL;
+
+    node->op = src->op;
+    node->val = src->val;
+    node->id = src->id;
+    node->subexpr = src->subexpr;
+
+    return dm_eval_insert_node(list, node);
+}
+
+
+static DMEvalNode *dm_eval_add_node(DMEvalNode **list, const int op)
+{
+    DMEvalNode *node = dmCalloc(1, sizeof(DMEvalNode));
+    if (node == NULL)
+        return NULL;
+
+    node->op = op;
+
+    return dm_eval_insert_node(list, node);
+}
+
+
+enum
+{
+    PARSE_NONE    = 0x0000,
+    PARSE_START   = 0x1000,
+    PARSE_END     = 0x2000,
+    PARSE_ERROR   = 0x8000,
+
+    PARSE_IDENT   = 0x0001,
+    PARSE_WS      = 0x0002,
+    PARSE_CONST   = 0x0004,
+    PARSE_OPER    = 0x0008,
+    PARSE_SUBEXPR = 0x0010,
+};
+
+#define DM_CHECK(x) { if (mode & PARSE_ ## x ) { if (str[0]) strcat(str, " or "); strcat(str, # x ); } }
+
+static char *dm_get_mode(int mode)
+{
+    char str[128] = "";
+    
+
+    DM_CHECK(START);
+    DM_CHECK(END);
+    DM_CHECK(IDENT);
+    DM_CHECK(WS);
+    DM_CHECK(CONST);
+    DM_CHECK(OPER);
+    DM_CHECK(SUBEXPR);
+            
+    return dm_strdup(str);
+}
+
+
+static void dm_set_mode(DMEvalContext *ev, const int mode)
+{
+    if (mode != PARSE_ERROR && mode != PARSE_START &&
+        ev->expect != PARSE_NONE &&
+        (mode & ev->expect) == 0)
+    {
+        char *tmp1 = dm_get_mode(ev->expect),
+             *tmp2 = dm_get_mode(mode);
+
+        dm_eval_err(ev, "Expected [%s], got %s.\n", tmp1, tmp2);
+        dmFree(tmp1);
+        dmFree(tmp2);
+    }
+
+    ev->prev = ev->mode;
+    ev->mode = mode;
+}
+
+
+static int dm_eval_parse_expr_do(DMEvalContext *ev, DMEvalNode **list, char **str, int depth)
+{
+    char *c = *str;
+    char tmpStr[DM_MAX_BUF + 2];
+    int tmpStrLen = 0;
+    DMEvalNode *node = NULL, *func = NULL;
+    BOOL first = FALSE, decimal = FALSE;
+
+    ev->expect = PARSE_CONST | PARSE_IDENT | PARSE_SUBEXPR;
+    ev->mode = PARSE_START;
+    
+    while (ev->mode != PARSE_ERROR && ev->mode != PARSE_END)
+    {
+    switch (ev->mode)
+    {
+        case PARSE_WS:
+            // Skip whitespace
+            if (isspace(*c))
+                c++;
+            else
+                dm_set_mode(ev, PARSE_START);
+            break;
+
+        case PARSE_SUBEXPR:
+            {
+                char *tmp = c + 1;
+
+                ev->expect = PARSE_SUBEXPR | PARSE_IDENT | PARSE_CONST;
+
+                if (func != NULL)
+                {
+                    if (dm_eval_parse_expr_do(ev, &(func->subexpr), &tmp, depth + 1) != 0)
+                    {
+                        dm_eval_err(ev, "Function argument subexpression starting at '%s' contained errors.\n", c);
+                        dm_set_mode(ev, PARSE_ERROR);
+                    }
+
+                    func = NULL;
+                }
+                else
+                {
+                    if ((node = dm_eval_add_node(list, OP_SUBEXPR)) == NULL)
+                        dm_set_mode(ev, PARSE_ERROR);
+                    else
+                    if (dm_eval_parse_expr_do(ev, &(node->subexpr), &tmp, depth + 1) != 0)
+                    {
+                        dm_eval_err(ev, "Subexpression starting at '%s' contained errors.\n", c);
+                        dm_set_mode(ev, PARSE_ERROR);
+                    }
+                }
+                if (ev->mode != PARSE_ERROR)
+                {
+                    dm_set_mode(ev, PARSE_START);
+                    ev->expect = PARSE_OPER | PARSE_END;
+                    c = tmp;
+                }
+            }
+            break;
+            
+        case PARSE_START:
+            // Start
+            if (*c == 0)
+                dm_set_mode(ev, PARSE_END);
+
+            else if (isspace(*c))
+            {
+                ev->mode = PARSE_WS;
+            }
+
+            else if (*c == ')')
+            {
+                if (depth > 0)
+                    dm_set_mode(ev, PARSE_END);
+                else
+                {
+                    dm_eval_err(ev, "Invalid nesting near '%s' (depth %d).\n", c, depth);
+                    dm_set_mode(ev, PARSE_ERROR);
+                }
+                c++;
+            }
+
+            else if (*c == '(')
+                dm_set_mode(ev, PARSE_SUBEXPR);
+
+            else if (strchr("+-*/<>%&|!^", *c))
+                dm_set_mode(ev, PARSE_OPER);
+
+            else if (isdigit(*c) || *c == '.')
+                dm_set_mode(ev, PARSE_CONST);
+
+            else if (isalpha(*c) || *c == '_')
+                dm_set_mode(ev, PARSE_IDENT);
+            
+            else
+            {
+                dm_eval_err(ev, "Syntax error near '%s' (depth %d).\n", c, depth);
+                dm_set_mode(ev, PARSE_ERROR);
+            }
+
+            first = TRUE;
+            break;
+        
+        case PARSE_CONST:
+            if (first)
+            {
+                first = FALSE;
+                decimal = FALSE;
+                tmpStrLen = 0;
+                
+                if (isdigit(*c) || *c == '-' || *c == '+' || *c == '.')
+                {
+                    if (*c == '.')
+                        decimal = TRUE;
+                    tmpStr[tmpStrLen++] = *c++;
+                }
+                else
+                {
+                    dm_eval_err(ev, "Invalid constant expression near '%s'.\n", c);
+                    dm_set_mode(ev, PARSE_ERROR);
+                }
+            }
+            else
+            {
+                if (isdigit(*c) || (*c == '.' && !decimal))
+                {
+                    if (*c == '.')
+                        decimal = TRUE;
+                    tmpStr[tmpStrLen++] = *c++;
+                }
+                else
+                {
+                    tmpStr[tmpStrLen] = 0;
+
+                    if ((node = dm_eval_add_node(list, OP_CONST)) == NULL)
+                    {
+                        dm_set_mode(ev, PARSE_ERROR);
+                        break;
+                    }
+                    
+                    node->val = atof(tmpStr);
+                    dm_set_mode(ev, PARSE_START);
+                    ev->expect = PARSE_OPER | PARSE_END;
+                }
+            }
+            break;
+
+        case PARSE_OPER:
+            {
+                int op = OP_NONE;
+
+                switch (*c)
+                {
+                    case '+': op = OP_ADD; c++; break;
+                    case '-': op = OP_SUB; c++; break;
+                    case '*': op = OP_MUL; c++; break;
+                    case '/': op = OP_DIV; c++; break;
+                    case '%': op = OP_MOD; c++; break;
+                    case '&': op = OP_AND; c++; break;
+                    case '|': op = OP_OR; c++; break;
+                    case '>':
+                        if (c[1] == '>')
+                        {
+                            c += 2;
+                            op = OP_RSHIFT;
+                        }
+                        else
+                        {
+                            dm_eval_err(ev, "Syntax error near '%s'.\n", c);
+                            dm_set_mode(ev, PARSE_ERROR);
+                        }
+                        break;
+                        
+                    case '<':
+                        if (c[1] == '<')
+                        {
+                            c += 2;
+                            op = OP_LSHIFT;
+                        }
+                        else
+                        {
+                            dm_eval_err(ev, "Syntax error near '%s'.\n", c);
+                            dm_set_mode(ev, PARSE_ERROR);
+                        }
+                        break;
+
+                    default:
+                        dm_eval_err(ev, "Unknown operator '%c'.\n", *c);
+                        dm_set_mode(ev, PARSE_ERROR);
+                }
+
+                if (op != OP_NONE)
+                {
+                    if ((node = dm_eval_add_node(list, op)) != NULL)
+                    {
+                        ev->expect = PARSE_IDENT | PARSE_CONST | PARSE_SUBEXPR;
+                        dm_set_mode(ev, PARSE_START);
+                    }
+                    else
+                        dm_set_mode(ev, PARSE_ERROR);
+                }
+            }
+            break;
+
+        case PARSE_IDENT:
+            if (isalnum(*c) || *c == '_')
+            {
+                if (first)
+                {
+                    tmpStrLen = 0;
+                    first = FALSE;
+                }
+
+                if (tmpStrLen < DM_MAX_ID_LEN)
+                    tmpStr[tmpStrLen++] = *c++;
+                else
+                {
+                    tmpStr[tmpStrLen] = 0;
+                    dm_eval_err(ev, "Identifier too long! ('%s')\n", tmpStr);
+                }
+            }
+            else
+            {
+                tmpStr[tmpStrLen] = 0;
+                DMEvalId *id = dm_eval_find_id(ev, tmpStr);
+                if (id != NULL)
+                {
+                    if ((node = dm_eval_add_node(list, id->type == ID_FUNC ? OP_FUNC : OP_VAR)) != NULL)
+                    {
+                        node->id = id;
+                        if (id->type == ID_FUNC)
+                        {
+                            func = node;
+                            ev->expect = PARSE_SUBEXPR;
+                        }
+                        else
+                            ev->expect = PARSE_END | PARSE_OPER;
+
+                        dm_set_mode(ev, PARSE_START);
+                    }
+                    else
+                        dm_set_mode(ev, PARSE_ERROR);
+                }
+                else
+                {
+                    dm_eval_err(ev, "No such identifier '%s'.\n", tmpStr);
+                    dm_set_mode(ev, PARSE_ERROR);
+                }
+            }
+            break;
+    }
+    }
+
+    *str = c;
+
+    return (ev->mode == PARSE_ERROR) ? -1 : 0;
+}
+
+
+int dm_eval_parse_expr(DMEvalContext *ev, char *expr, DMEvalNode **result)
+{
+    int ret;
+
+    if (ev == NULL || result == NULL)
+        return -1;
+
+    ret = dm_eval_parse_expr_do(ev, result, &expr, 0);
+    
+    return ret;
+}
+
+
+static const char *dm_oper_names[OP_NOPERS] =
+{
+    "NONE",
+    "+",
+    "-",
+    "*",
+    "/",
+    "%",
+    
+    "<<",
+    ">>",
+    
+    "&",
+    "|",
+    "^",
+    
+    "FUNC",
+    "VAR",
+    "SUBEXPR",
+    "CONST"
+};
+
+
+static void dm_print_optree_do(DMEvalContext *ev, DMEvalNode *node, const int level)
+{
+    while (node != NULL)
+    {
+        switch (node->op)
+        {
+            case OP_FUNC:
+                printf("%s(", node->id != NULL ? node->id->name : "?ERROR");
+                dm_print_optree_do(ev, node->subexpr, level + 1);
+                printf(")");
+                break;
+
+            case OP_VAR:
+                printf("%s", node->id != NULL ? node->id->name : "?ERROR");
+                break;
+
+            case OP_CONST:
+                printf("%.1f", node->val);
+                break;
+
+            case OP_SUBEXPR:
+                printf("(");
+                if (node->subexpr != NULL)
+                    dm_print_optree_do(ev, node->subexpr, level + 1);
+                else
+                    printf("?ERROR");
+                printf(")");
+                break;
+
+            default:
+                if (node->op > 0 && node->op < OP_NOPERS)
+                    printf("%s", dm_oper_names[node->op]);
+                else
+                    printf("ERROR!");
+                break;
+        }
+        node = node->next;
+    }
+}
+
+
+void dm_print_optree(DMEvalContext *ev, DMEvalNode *node)
+{
+    dm_print_optree_do(ev, node, 0);
+    printf("\n");
+}
+
+
+/*
+    operator precedence:
+      HIGHEST
+      "()"
+      
+      "*"
+      "/"
+      "%"
+      
+      "+"
+      "-"
+      
+      "<<"
+      ">>"
+      
+      "&"
+      "^"
+      "|"
+      LOWEST
+*/
+
+int dm_eval_reorder(DMEvalContext *ev, DMEvalNode *node, DMEvalNode **result)
+{
+    DMEvalNode *list = NULL;
+
+    while (node != NULL)
+    {
+        DMEvalNode *tmp;
+
+        switch (node->op)
+        {
+            case OP_SUBEXPR:
+            case OP_FUNC:
+                if ((tmp = dm_eval_push_node(&list, node)) == NULL)
+                    return -1;
+
+                if (dm_eval_reorder(ev, node->subexpr, &(tmp->subexpr)) != 0)
+                    return -2;
+                break;
+
+            case OP_MUL:
+            case OP_DIV:
+            case OP_MOD:
+                if ((tmp = dm_eval_pop_node(&list)) != NULL)
+                {
+                    DMEvalNode *sub;
+
+                    if ((sub = dm_eval_add_node(&list, OP_SUBEXPR)) == NULL)
+                        return -3;
+
+                    dm_eval_push_node(&(sub->subexpr), tmp);
+                    dm_eval_add_node(&(sub->subexpr), node->op);
+                    node = node->next;
+                    if (node != NULL)
+                    {
+                        if (node->op == OP_FUNC || node->op == OP_SUBEXPR)
+                        {
+                            if ((tmp = dm_eval_push_node(&(sub->subexpr), node)) == NULL)
+                                return -178;
+                            
+                            if (dm_eval_reorder(ev, node->subexpr, &(tmp->subexpr)) != 0)
+                                return -66;
+                        }
+                        else
+                            dm_eval_push_node(&(sub->subexpr), node);
+                    }
+                    else
+                        return -72;
+                }
+                else
+                    return -24;
+                break;
+            
+            case OP_LSHIFT:
+            case OP_RSHIFT:
+
+            case OP_ADD:
+            case OP_SUB:
+            
+            case OP_AND:
+            case OP_XOR:
+            case OP_OR:
+
+            case OP_VAR:
+            case OP_CONST:
+                if (dm_eval_push_node(&list, node) == NULL)
+                    return -32;
+                break;
+
+            default:
+                dm_eval_err(ev, "Invalid opcode %d in node %p.\n", node->op, node);
+                return -4;
+        }
+        
+        node = node->next;
+    }
+
+    *result = list;
+    return 0;
+}
+
+
+static int dm_eval_get(DMEvalContext *ev, DMEvalNode *node, DMValue *result)
+{
+    DMValue tmp;
+    
+    if (node == NULL)
+        return -32;
+    
+    switch (node->op)
+    {
+        case OP_VAR:
+            *result = *(node->id->var);
+            break;
+
+        case OP_CONST:
+            *result = node->val;
+            break;
+
+        case OP_SUBEXPR:
+            if (dm_eval_exec(ev, node->subexpr, result) != 0)
+                return -1;
+            break;
+        
+        case OP_FUNC:
+            if (dm_eval_exec(ev, node->subexpr, &tmp) != 0)
+                return -1;
+            
+            *result = node->id->func(tmp);
+            break;
+
+        default:
+            return -16;
+    }
+
+    return 0;
+}
+
+
+int dm_eval_exec(DMEvalContext *ev, DMEvalNode *tree, DMValue *presult)
+{
+    DMValue result;
+    DMEvalNode *node = tree;
+
+    while (node != NULL)
+    {
+        DMValue tmp;
+
+        switch (node->op)
+        {
+            case OP_LSHIFT:
+            case OP_RSHIFT:
+            
+            case OP_AND:
+            case OP_XOR:
+            case OP_OR:
+
+            case OP_MUL:
+            case OP_DIV:
+            case OP_MOD:
+                if (dm_eval_get(ev, node->next, &tmp) != 0)
+                    return -6;
+                
+                switch (node->op)
+                {
+                    case OP_DIV:
+                        if (tmp == 0)
+                        {
+                            dm_eval_err(ev, "Division by zero.\n");
+                            return -1;
+                        }
+                        result /= tmp;
+                        break;
+
+                    case OP_MUL:     result  *= tmp; break;
+
+                    case OP_MOD:
+                        if (tmp == 0)
+                        {
+                            dm_eval_err(ev, "Division by zero.\n");
+                            return -1;
+                        }
+                        result = DMCONVTYPE result % DMCONVTYPE tmp;
+                        break;
+
+                    case OP_LSHIFT:  result = DMCONVTYPE result << DMCONVTYPE tmp; break;
+                    case OP_RSHIFT:  result = DMCONVTYPE result >> DMCONVTYPE tmp; break;
+
+                    case OP_AND:     result = DMCONVTYPE result & DMCONVTYPE tmp; break;
+                    case OP_OR:      result = DMCONVTYPE result | DMCONVTYPE tmp; break;
+                    case OP_XOR:     result = DMCONVTYPE result ^ DMCONVTYPE tmp; break;
+                }
+                
+                node = node->next;
+                break;
+            
+            case OP_ADD:
+            case OP_SUB:
+                if (dm_eval_get(ev, node->next, &tmp) != 0)
+                    return -6;
+                
+                switch (node->op)
+                {
+                    case OP_ADD: result += tmp; break;
+                    case OP_SUB: result -= tmp; break;
+                }
+
+                node = node->next;
+                break;
+
+            default:
+                if (dm_eval_get(ev, node, &result) != 0)
+                {
+                    dm_eval_err(ev, "Invalid opcode %d in node %p.\n", node->op, node);
+                    return -4;
+                }
+        }
+        
+        node = node->next;
+    }
+
+    *presult = result;
+    return 0;
+}