Mercurial > hg > dmlib
diff dmeval.c @ 0:32250b436bca
Initial re-import.
author | Matti Hamalainen <ccr@tnsp.org> |
---|---|
date | Fri, 28 Sep 2012 01:54:23 +0300 |
parents | |
children | 05eb24a608f0 |
line wrap: on
line diff
--- /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; +}