00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00029 #include "avutil.h"
00030 #include "eval.h"
00031 #include "log.h"
00032
00033 typedef struct Parser {
00034 const AVClass *class;
00035 int stack_index;
00036 char *s;
00037 const double *const_values;
00038 const char * const *const_names;
00039 double (* const *funcs1)(void *, double a);
00040 const char * const *func1_names;
00041 double (* const *funcs2)(void *, double a, double b);
00042 const char * const *func2_names;
00043 void *opaque;
00044 int log_offset;
00045 void *log_ctx;
00046 #define VARS 10
00047 double var[VARS];
00048 } Parser;
00049
00050 static const AVClass class = { "Eval", av_default_item_name, NULL, LIBAVUTIL_VERSION_INT, offsetof(Parser,log_offset), offsetof(Parser,log_ctx) };
00051
00052 static const int8_t si_prefixes['z' - 'E' + 1] = {
00053 ['y'-'E']= -24,
00054 ['z'-'E']= -21,
00055 ['a'-'E']= -18,
00056 ['f'-'E']= -15,
00057 ['p'-'E']= -12,
00058 ['n'-'E']= - 9,
00059 ['u'-'E']= - 6,
00060 ['m'-'E']= - 3,
00061 ['c'-'E']= - 2,
00062 ['d'-'E']= - 1,
00063 ['h'-'E']= 2,
00064 ['k'-'E']= 3,
00065 ['K'-'E']= 3,
00066 ['M'-'E']= 6,
00067 ['G'-'E']= 9,
00068 ['T'-'E']= 12,
00069 ['P'-'E']= 15,
00070 ['E'-'E']= 18,
00071 ['Z'-'E']= 21,
00072 ['Y'-'E']= 24,
00073 };
00074
00075 double av_strtod(const char *numstr, char **tail)
00076 {
00077 double d;
00078 char *next;
00079 d = strtod(numstr, &next);
00080
00081 if (next!=numstr) {
00082 if (*next >= 'E' && *next <= 'z') {
00083 int e= si_prefixes[*next - 'E'];
00084 if (e) {
00085 if (next[1] == 'i') {
00086 d*= pow( 2, e/0.3);
00087 next+=2;
00088 } else {
00089 d*= pow(10, e);
00090 next++;
00091 }
00092 }
00093 }
00094
00095 if (*next=='B') {
00096 d*=8;
00097 next++;
00098 }
00099 }
00100
00101
00102 if (tail)
00103 *tail = next;
00104 return d;
00105 }
00106
00107 #define IS_IDENTIFIER_CHAR(c) ((c) - '0' <= 9U || (c) - 'a' <= 25U || (c) - 'A' <= 25U || (c) == '_')
00108
00109 static int strmatch(const char *s, const char *prefix)
00110 {
00111 int i;
00112 for (i=0; prefix[i]; i++) {
00113 if (prefix[i] != s[i]) return 0;
00114 }
00115
00116 return !IS_IDENTIFIER_CHAR(s[i]);
00117 }
00118
00119 struct AVExpr {
00120 enum {
00121 e_value, e_const, e_func0, e_func1, e_func2,
00122 e_squish, e_gauss, e_ld, e_isnan,
00123 e_mod, e_max, e_min, e_eq, e_gt, e_gte,
00124 e_pow, e_mul, e_div, e_add,
00125 e_last, e_st, e_while, e_floor, e_ceil, e_trunc,
00126 e_sqrt, e_not,
00127 } type;
00128 double value;
00129 union {
00130 int const_index;
00131 double (*func0)(double);
00132 double (*func1)(void *, double);
00133 double (*func2)(void *, double, double);
00134 } a;
00135 struct AVExpr *param[2];
00136 };
00137
00138 static double eval_expr(Parser *p, AVExpr *e)
00139 {
00140 switch (e->type) {
00141 case e_value: return e->value;
00142 case e_const: return e->value * p->const_values[e->a.const_index];
00143 case e_func0: return e->value * e->a.func0(eval_expr(p, e->param[0]));
00144 case e_func1: return e->value * e->a.func1(p->opaque, eval_expr(p, e->param[0]));
00145 case e_func2: return e->value * e->a.func2(p->opaque, eval_expr(p, e->param[0]), eval_expr(p, e->param[1]));
00146 case e_squish: return 1/(1+exp(4*eval_expr(p, e->param[0])));
00147 case e_gauss: { double d = eval_expr(p, e->param[0]); return exp(-d*d/2)/sqrt(2*M_PI); }
00148 case e_ld: return e->value * p->var[av_clip(eval_expr(p, e->param[0]), 0, VARS-1)];
00149 case e_isnan: return e->value * !!isnan(eval_expr(p, e->param[0]));
00150 case e_floor: return e->value * floor(eval_expr(p, e->param[0]));
00151 case e_ceil : return e->value * ceil (eval_expr(p, e->param[0]));
00152 case e_trunc: return e->value * trunc(eval_expr(p, e->param[0]));
00153 case e_sqrt: return e->value * sqrt (eval_expr(p, e->param[0]));
00154 case e_not: return e->value * eval_expr(p, e->param[0]) == 0;
00155 case e_while: {
00156 double d = NAN;
00157 while (eval_expr(p, e->param[0]))
00158 d=eval_expr(p, e->param[1]);
00159 return d;
00160 }
00161 default: {
00162 double d = eval_expr(p, e->param[0]);
00163 double d2 = eval_expr(p, e->param[1]);
00164 switch (e->type) {
00165 case e_mod: return e->value * (d - floor(d/d2)*d2);
00166 case e_max: return e->value * (d > d2 ? d : d2);
00167 case e_min: return e->value * (d < d2 ? d : d2);
00168 case e_eq: return e->value * (d == d2 ? 1.0 : 0.0);
00169 case e_gt: return e->value * (d > d2 ? 1.0 : 0.0);
00170 case e_gte: return e->value * (d >= d2 ? 1.0 : 0.0);
00171 case e_pow: return e->value * pow(d, d2);
00172 case e_mul: return e->value * (d * d2);
00173 case e_div: return e->value * (d / d2);
00174 case e_add: return e->value * (d + d2);
00175 case e_last:return e->value * d2;
00176 case e_st : return e->value * (p->var[av_clip(d, 0, VARS-1)]= d2);
00177 }
00178 }
00179 }
00180 return NAN;
00181 }
00182
00183 static int parse_expr(AVExpr **e, Parser *p);
00184
00185 void av_expr_free(AVExpr *e)
00186 {
00187 if (!e) return;
00188 av_expr_free(e->param[0]);
00189 av_expr_free(e->param[1]);
00190 av_freep(&e);
00191 }
00192
00193 static int parse_primary(AVExpr **e, Parser *p)
00194 {
00195 AVExpr *d = av_mallocz(sizeof(AVExpr));
00196 char *next = p->s, *s0 = p->s;
00197 int ret, i;
00198
00199 if (!d)
00200 return AVERROR(ENOMEM);
00201
00202
00203 d->value = av_strtod(p->s, &next);
00204 if (next != p->s) {
00205 d->type = e_value;
00206 p->s= next;
00207 *e = d;
00208 return 0;
00209 }
00210 d->value = 1;
00211
00212
00213 for (i=0; p->const_names && p->const_names[i]; i++) {
00214 if (strmatch(p->s, p->const_names[i])) {
00215 p->s+= strlen(p->const_names[i]);
00216 d->type = e_const;
00217 d->a.const_index = i;
00218 *e = d;
00219 return 0;
00220 }
00221 }
00222
00223 p->s= strchr(p->s, '(');
00224 if (p->s==NULL) {
00225 av_log(p, AV_LOG_ERROR, "Undefined constant or missing '(' in '%s'\n", s0);
00226 p->s= next;
00227 av_expr_free(d);
00228 return AVERROR(EINVAL);
00229 }
00230 p->s++;
00231 if (*next == '(') {
00232 av_freep(&d);
00233 if ((ret = parse_expr(&d, p)) < 0)
00234 return ret;
00235 if (p->s[0] != ')') {
00236 av_log(p, AV_LOG_ERROR, "Missing ')' in '%s'\n", s0);
00237 av_expr_free(d);
00238 return AVERROR(EINVAL);
00239 }
00240 p->s++;
00241 *e = d;
00242 return 0;
00243 }
00244 if ((ret = parse_expr(&(d->param[0]), p)) < 0) {
00245 av_expr_free(d);
00246 return ret;
00247 }
00248 if (p->s[0]== ',') {
00249 p->s++;
00250 parse_expr(&d->param[1], p);
00251 }
00252 if (p->s[0] != ')') {
00253 av_log(p, AV_LOG_ERROR, "Missing ')' or too many args in '%s'\n", s0);
00254 av_expr_free(d);
00255 return AVERROR(EINVAL);
00256 }
00257 p->s++;
00258
00259 d->type = e_func0;
00260 if (strmatch(next, "sinh" )) d->a.func0 = sinh;
00261 else if (strmatch(next, "cosh" )) d->a.func0 = cosh;
00262 else if (strmatch(next, "tanh" )) d->a.func0 = tanh;
00263 else if (strmatch(next, "sin" )) d->a.func0 = sin;
00264 else if (strmatch(next, "cos" )) d->a.func0 = cos;
00265 else if (strmatch(next, "tan" )) d->a.func0 = tan;
00266 else if (strmatch(next, "atan" )) d->a.func0 = atan;
00267 else if (strmatch(next, "asin" )) d->a.func0 = asin;
00268 else if (strmatch(next, "acos" )) d->a.func0 = acos;
00269 else if (strmatch(next, "exp" )) d->a.func0 = exp;
00270 else if (strmatch(next, "log" )) d->a.func0 = log;
00271 else if (strmatch(next, "abs" )) d->a.func0 = fabs;
00272 else if (strmatch(next, "squish")) d->type = e_squish;
00273 else if (strmatch(next, "gauss" )) d->type = e_gauss;
00274 else if (strmatch(next, "mod" )) d->type = e_mod;
00275 else if (strmatch(next, "max" )) d->type = e_max;
00276 else if (strmatch(next, "min" )) d->type = e_min;
00277 else if (strmatch(next, "eq" )) d->type = e_eq;
00278 else if (strmatch(next, "gte" )) d->type = e_gte;
00279 else if (strmatch(next, "gt" )) d->type = e_gt;
00280 else if (strmatch(next, "lte" )) { AVExpr *tmp = d->param[1]; d->param[1] = d->param[0]; d->param[0] = tmp; d->type = e_gte; }
00281 else if (strmatch(next, "lt" )) { AVExpr *tmp = d->param[1]; d->param[1] = d->param[0]; d->param[0] = tmp; d->type = e_gt; }
00282 else if (strmatch(next, "ld" )) d->type = e_ld;
00283 else if (strmatch(next, "isnan" )) d->type = e_isnan;
00284 else if (strmatch(next, "st" )) d->type = e_st;
00285 else if (strmatch(next, "while" )) d->type = e_while;
00286 else if (strmatch(next, "floor" )) d->type = e_floor;
00287 else if (strmatch(next, "ceil" )) d->type = e_ceil;
00288 else if (strmatch(next, "trunc" )) d->type = e_trunc;
00289 else if (strmatch(next, "sqrt" )) d->type = e_sqrt;
00290 else if (strmatch(next, "not" )) d->type = e_not;
00291 else {
00292 for (i=0; p->func1_names && p->func1_names[i]; i++) {
00293 if (strmatch(next, p->func1_names[i])) {
00294 d->a.func1 = p->funcs1[i];
00295 d->type = e_func1;
00296 *e = d;
00297 return 0;
00298 }
00299 }
00300
00301 for (i=0; p->func2_names && p->func2_names[i]; i++) {
00302 if (strmatch(next, p->func2_names[i])) {
00303 d->a.func2 = p->funcs2[i];
00304 d->type = e_func2;
00305 *e = d;
00306 return 0;
00307 }
00308 }
00309
00310 av_log(p, AV_LOG_ERROR, "Unknown function in '%s'\n", s0);
00311 av_expr_free(d);
00312 return AVERROR(EINVAL);
00313 }
00314
00315 *e = d;
00316 return 0;
00317 }
00318
00319 static AVExpr *new_eval_expr(int type, int value, AVExpr *p0, AVExpr *p1)
00320 {
00321 AVExpr *e = av_mallocz(sizeof(AVExpr));
00322 if (!e)
00323 return NULL;
00324 e->type =type ;
00325 e->value =value ;
00326 e->param[0] =p0 ;
00327 e->param[1] =p1 ;
00328 return e;
00329 }
00330
00331 static int parse_pow(AVExpr **e, Parser *p, int *sign)
00332 {
00333 *sign= (*p->s == '+') - (*p->s == '-');
00334 p->s += *sign&1;
00335 return parse_primary(e, p);
00336 }
00337
00338 static int parse_factor(AVExpr **e, Parser *p)
00339 {
00340 int sign, sign2, ret;
00341 AVExpr *e0, *e1, *e2;
00342 if ((ret = parse_pow(&e0, p, &sign)) < 0)
00343 return ret;
00344 while(p->s[0]=='^'){
00345 e1 = e0;
00346 p->s++;
00347 if ((ret = parse_pow(&e2, p, &sign2)) < 0) {
00348 av_expr_free(e1);
00349 return ret;
00350 }
00351 e0 = new_eval_expr(e_pow, 1, e1, e2);
00352 if (!e0) {
00353 av_expr_free(e1);
00354 av_expr_free(e2);
00355 return AVERROR(ENOMEM);
00356 }
00357 if (e0->param[1]) e0->param[1]->value *= (sign2|1);
00358 }
00359 if (e0) e0->value *= (sign|1);
00360
00361 *e = e0;
00362 return 0;
00363 }
00364
00365 static int parse_term(AVExpr **e, Parser *p)
00366 {
00367 int ret;
00368 AVExpr *e0, *e1, *e2;
00369 if ((ret = parse_factor(&e0, p)) < 0)
00370 return ret;
00371 while (p->s[0]=='*' || p->s[0]=='/') {
00372 int c= *p->s++;
00373 e1 = e0;
00374 if ((ret = parse_factor(&e2, p)) < 0) {
00375 av_expr_free(e1);
00376 return ret;
00377 }
00378 e0 = new_eval_expr(c == '*' ? e_mul : e_div, 1, e1, e2);
00379 if (!e0) {
00380 av_expr_free(e1);
00381 av_expr_free(e2);
00382 return AVERROR(ENOMEM);
00383 }
00384 }
00385 *e = e0;
00386 return 0;
00387 }
00388
00389 static int parse_subexpr(AVExpr **e, Parser *p)
00390 {
00391 int ret;
00392 AVExpr *e0, *e1, *e2;
00393 if ((ret = parse_term(&e0, p)) < 0)
00394 return ret;
00395 while (*p->s == '+' || *p->s == '-') {
00396 e1 = e0;
00397 if ((ret = parse_term(&e2, p)) < 0) {
00398 av_expr_free(e1);
00399 return ret;
00400 }
00401 e0 = new_eval_expr(e_add, 1, e1, e2);
00402 if (!e0) {
00403 av_expr_free(e1);
00404 av_expr_free(e2);
00405 return AVERROR(ENOMEM);
00406 }
00407 };
00408
00409 *e = e0;
00410 return 0;
00411 }
00412
00413 static int parse_expr(AVExpr **e, Parser *p)
00414 {
00415 int ret;
00416 AVExpr *e0, *e1, *e2;
00417 if (p->stack_index <= 0)
00418 return AVERROR(EINVAL);
00419 p->stack_index--;
00420
00421 if ((ret = parse_subexpr(&e0, p)) < 0)
00422 return ret;
00423 while (*p->s == ';') {
00424 p->s++;
00425 e1 = e0;
00426 if ((ret = parse_subexpr(&e2, p)) < 0) {
00427 av_expr_free(e1);
00428 return ret;
00429 }
00430 e0 = new_eval_expr(e_last, 1, e1, e2);
00431 if (!e0) {
00432 av_expr_free(e1);
00433 av_expr_free(e2);
00434 return AVERROR(ENOMEM);
00435 }
00436 };
00437
00438 p->stack_index++;
00439 *e = e0;
00440 return 0;
00441 }
00442
00443 static int verify_expr(AVExpr *e)
00444 {
00445 if (!e) return 0;
00446 switch (e->type) {
00447 case e_value:
00448 case e_const: return 1;
00449 case e_func0:
00450 case e_func1:
00451 case e_squish:
00452 case e_ld:
00453 case e_gauss:
00454 case e_isnan:
00455 case e_floor:
00456 case e_ceil:
00457 case e_trunc:
00458 case e_sqrt:
00459 case e_not:
00460 return verify_expr(e->param[0]);
00461 default: return verify_expr(e->param[0]) && verify_expr(e->param[1]);
00462 }
00463 }
00464
00465 int av_expr_parse(AVExpr **expr, const char *s,
00466 const char * const *const_names,
00467 const char * const *func1_names, double (* const *funcs1)(void *, double),
00468 const char * const *func2_names, double (* const *funcs2)(void *, double, double),
00469 int log_offset, void *log_ctx)
00470 {
00471 Parser p = { 0 };
00472 AVExpr *e = NULL;
00473 char *w = av_malloc(strlen(s) + 1);
00474 char *wp = w;
00475 const char *s0 = s;
00476 int ret = 0;
00477
00478 if (!w)
00479 return AVERROR(ENOMEM);
00480
00481 while (*s)
00482 if (!isspace(*s++)) *wp++ = s[-1];
00483 *wp++ = 0;
00484
00485 p.class = &class;
00486 p.stack_index=100;
00487 p.s= w;
00488 p.const_names = const_names;
00489 p.funcs1 = funcs1;
00490 p.func1_names = func1_names;
00491 p.funcs2 = funcs2;
00492 p.func2_names = func2_names;
00493 p.log_offset = log_offset;
00494 p.log_ctx = log_ctx;
00495
00496 if ((ret = parse_expr(&e, &p)) < 0)
00497 goto end;
00498 if (*p.s) {
00499 av_expr_free(e);
00500 av_log(&p, AV_LOG_ERROR, "Invalid chars '%s' at the end of expression '%s'\n", p.s, s0);
00501 ret = AVERROR(EINVAL);
00502 goto end;
00503 }
00504 if (!verify_expr(e)) {
00505 av_expr_free(e);
00506 ret = AVERROR(EINVAL);
00507 goto end;
00508 }
00509 *expr = e;
00510 end:
00511 av_free(w);
00512 return ret;
00513 }
00514
00515 double av_expr_eval(AVExpr *e, const double *const_values, void *opaque)
00516 {
00517 Parser p = { 0 };
00518
00519 p.const_values = const_values;
00520 p.opaque = opaque;
00521 return eval_expr(&p, e);
00522 }
00523
00524 int av_expr_parse_and_eval(double *d, const char *s,
00525 const char * const *const_names, const double *const_values,
00526 const char * const *func1_names, double (* const *funcs1)(void *, double),
00527 const char * const *func2_names, double (* const *funcs2)(void *, double, double),
00528 void *opaque, int log_offset, void *log_ctx)
00529 {
00530 AVExpr *e = NULL;
00531 int ret = av_expr_parse(&e, s, const_names, func1_names, funcs1, func2_names, funcs2, log_offset, log_ctx);
00532
00533 if (ret < 0) {
00534 *d = NAN;
00535 return ret;
00536 }
00537 *d = av_expr_eval(e, const_values, opaque);
00538 av_expr_free(e);
00539 return isnan(*d) ? AVERROR(EINVAL) : 0;
00540 }
00541
00542 #ifdef TEST
00543 #undef printf
00544 #include <string.h>
00545
00546 static double const_values[] = {
00547 M_PI,
00548 M_E,
00549 0
00550 };
00551
00552 static const char *const_names[] = {
00553 "PI",
00554 "E",
00555 0
00556 };
00557
00558 int main(int argc, char **argv)
00559 {
00560 int i;
00561 double d;
00562 const char **expr, *exprs[] = {
00563 "",
00564 "1;2",
00565 "-20",
00566 "-PI",
00567 "+PI",
00568 "1+(5-2)^(3-1)+1/2+sin(PI)-max(-2.2,-3.1)",
00569 "80G/80Gi",
00570 "1k",
00571 "1Gi",
00572 "1gi",
00573 "1GiFoo",
00574 "1k+1k",
00575 "1Gi*3foo",
00576 "foo",
00577 "foo(",
00578 "foo()",
00579 "foo)",
00580 "sin",
00581 "sin(",
00582 "sin()",
00583 "sin)",
00584 "sin 10",
00585 "sin(1,2,3)",
00586 "sin(1 )",
00587 "1",
00588 "1foo",
00589 "bar + PI + E + 100f*2 + foo",
00590 "13k + 12f - foo(1, 2)",
00591 "1gi",
00592 "1Gi",
00593 "st(0, 123)",
00594 "st(1, 123); ld(1)",
00595
00596 "st(0, 1); while(lte(ld(0), 100), st(1, ld(1)+ld(0));st(0, ld(0)+1)); ld(1)",
00597
00598 "st(1, 1); st(2, 2); st(0, 1); while(lte(ld(0),10), st(3, ld(1)+ld(2)); st(1, ld(2)); st(2, ld(3)); st(0, ld(0)+1)); ld(3)",
00599 "while(0, 10)",
00600 "st(0, 1); while(lte(ld(0),100), st(1, ld(1)+ld(0)); st(0, ld(0)+1))",
00601 "isnan(1)",
00602 "isnan(NAN)",
00603 "floor(NAN)",
00604 "floor(123.123)",
00605 "floor(-123.123)",
00606 "trunc(123.123)",
00607 "trunc(-123.123)",
00608 "ceil(123.123)",
00609 "ceil(-123.123)",
00610 "sqrt(1764)",
00611 "isnan(sqrt(-1))",
00612 "not(1)",
00613 "not(NAN)",
00614 "not(0)",
00615 NULL
00616 };
00617
00618 for (expr = exprs; *expr; expr++) {
00619 printf("Evaluating '%s'\n", *expr);
00620 av_expr_parse_and_eval(&d, *expr,
00621 const_names, const_values,
00622 NULL, NULL, NULL, NULL, NULL, 0, NULL);
00623 printf("'%s' -> %f\n\n", *expr, d);
00624 }
00625
00626 av_expr_parse_and_eval(&d, "1+(5-2)^(3-1)+1/2+sin(PI)-max(-2.2,-3.1)",
00627 const_names, const_values,
00628 NULL, NULL, NULL, NULL, NULL, 0, NULL);
00629 printf("%f == 12.7\n", d);
00630 av_expr_parse_and_eval(&d, "80G/80Gi",
00631 const_names, const_values,
00632 NULL, NULL, NULL, NULL, NULL, 0, NULL);
00633 printf("%f == 0.931322575\n", d);
00634
00635 if (argc > 1 && !strcmp(argv[1], "-t")) {
00636 for (i = 0; i < 1050; i++) {
00637 START_TIMER;
00638 av_expr_parse_and_eval(&d, "1+(5-2)^(3-1)+1/2+sin(PI)-max(-2.2,-3.1)",
00639 const_names, const_values,
00640 NULL, NULL, NULL, NULL, NULL, 0, NULL);
00641 STOP_TIMER("av_expr_parse_and_eval");
00642 }
00643 }
00644
00645 return 0;
00646 }
00647 #endif