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