eval.c (27444B)
1 /* 2 * Copyright (c) 2002-2006 Michael Niedermayer <michaelni@gmx.at> 3 * Copyright (c) 2006 Oded Shimon <ods15@ods15.dyndns.org> 4 * 5 * This file is part of FFmpeg. 6 * 7 * FFmpeg is free software; you can redistribute it and/or 8 * modify it under the terms of the GNU Lesser General Public 9 * License as published by the Free Software Foundation; either 10 * version 2.1 of the License, or (at your option) any later version. 11 * 12 * FFmpeg is distributed in the hope that it will be useful, 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 15 * Lesser General Public License for more details. 16 * 17 * You should have received a copy of the GNU Lesser General Public 18 * License along with FFmpeg; if not, write to the Free Software 19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 20 */ 21 22 /** 23 * @file 24 * simple arithmetic expression evaluator. 25 * 26 * see http://joe.hotchkiss.com/programming/eval/eval.html 27 */ 28 29 #include <float.h> 30 #include "attributes.h" 31 #include "avutil.h" 32 #include "common.h" 33 #include "eval.h" 34 #include "ffmath.h" 35 #include "log.h" 36 #include "mathematics.h" 37 #include "mem.h" 38 #include "sfc64.h" 39 #include "fftime.h" 40 #include "avstring.h" 41 #include "reverse.h" 42 43 typedef struct Parser { 44 const AVClass *class; 45 int stack_index; 46 char *s; 47 const double *const_values; 48 const char * const *const_names; // NULL terminated 49 double (* const *funcs1)(void *, double a); // NULL terminated 50 const char * const *func1_names; // NULL terminated 51 double (* const *funcs2)(void *, double a, double b); // NULL terminated 52 const char * const *func2_names; // NULL terminated 53 void *opaque; 54 int log_offset; 55 void *log_ctx; 56 #define VARS 10 57 double *var; 58 FFSFC64 *prng_state; 59 } Parser; 60 61 static const AVClass eval_class = { 62 .class_name = "Eval", 63 .item_name = av_default_item_name, 64 .option = NULL, 65 .version = LIBAVUTIL_VERSION_INT, 66 .log_level_offset_offset = offsetof(Parser, log_offset), 67 .parent_log_context_offset = offsetof(Parser, log_ctx), 68 }; 69 70 static const struct { 71 double bin_val; 72 double dec_val; 73 int8_t exp; 74 } si_prefixes['z' - 'E' + 1] = { 75 ['y'-'E']= { 8.271806125530276749e-25, 1e-24, -24 }, 76 ['z'-'E']= { 8.4703294725430034e-22, 1e-21, -21 }, 77 ['a'-'E']= { 8.6736173798840355e-19, 1e-18, -18 }, 78 ['f'-'E']= { 8.8817841970012523e-16, 1e-15, -15 }, 79 ['p'-'E']= { 9.0949470177292824e-13, 1e-12, -12 }, 80 ['n'-'E']= { 9.3132257461547852e-10, 1e-9, -9 }, 81 ['u'-'E']= { 9.5367431640625e-7, 1e-6, -6 }, 82 ['m'-'E']= { 9.765625e-4, 1e-3, -3 }, 83 ['c'-'E']= { 9.8431332023036951e-3, 1e-2, -2 }, 84 ['d'-'E']= { 9.921256574801246e-2, 1e-1, -1 }, 85 ['h'-'E']= { 1.0159366732596479e2, 1e2, 2 }, 86 ['k'-'E']= { 1.024e3, 1e3, 3 }, 87 ['K'-'E']= { 1.024e3, 1e3, 3 }, 88 ['M'-'E']= { 1.048576e6, 1e6, 6 }, 89 ['G'-'E']= { 1.073741824e9, 1e9, 9 }, 90 ['T'-'E']= { 1.099511627776e12, 1e12, 12 }, 91 ['P'-'E']= { 1.125899906842624e15, 1e15, 15 }, 92 ['E'-'E']= { 1.152921504606847e18, 1e18, 18 }, 93 ['Z'-'E']= { 1.1805916207174113e21, 1e21, 21 }, 94 ['Y'-'E']= { 1.2089258196146292e24, 1e24, 24 }, 95 }; 96 97 static const struct { 98 const char *name; 99 double value; 100 } constants[] = { 101 { "E", M_E }, 102 { "PI", M_PI }, 103 { "PHI", M_PHI }, 104 { "QP2LAMBDA", FF_QP2LAMBDA }, 105 }; 106 107 double av_strtod(const char *numstr, char **tail) 108 { 109 double d; 110 char *next; 111 if(numstr[0]=='0' && (numstr[1]|0x20)=='x') { 112 d = strtoul(numstr, &next, 16); 113 } else 114 d = strtod(numstr, &next); 115 /* if parsing succeeded, check for and interpret postfixes */ 116 if (next!=numstr) { 117 if (next[0] == 'd' && next[1] == 'B') { 118 /* treat dB as decibels instead of decibytes */ 119 d = ff_exp10(d / 20); 120 next += 2; 121 } else if (*next >= 'E' && *next <= 'z') { 122 int e= si_prefixes[*next - 'E'].exp; 123 if (e) { 124 if (next[1] == 'i') { 125 d*= si_prefixes[*next - 'E'].bin_val; 126 next+=2; 127 } else { 128 d*= si_prefixes[*next - 'E'].dec_val; 129 next++; 130 } 131 } 132 } 133 134 if (*next=='B') { 135 d*=8; 136 next++; 137 } 138 } 139 /* if requested, fill in tail with the position after the last parsed 140 character */ 141 if (tail) 142 *tail = next; 143 return d; 144 } 145 146 #define IS_IDENTIFIER_CHAR(c) ((c) - '0' <= 9U || (c) - 'a' <= 25U || (c) - 'A' <= 25U || (c) == '_') 147 148 static int strmatch(const char *s, const char *prefix) 149 { 150 int i; 151 for (i=0; prefix[i]; i++) { 152 if (prefix[i] != s[i]) return 0; 153 } 154 /* return 1 only if the s identifier is terminated */ 155 return !IS_IDENTIFIER_CHAR(s[i]); 156 } 157 158 struct AVExpr { 159 enum { 160 e_value, e_const, e_func0, e_func1, e_func2, 161 e_squish, e_gauss, e_ld, e_isnan, e_isinf, 162 e_mod, e_max, e_min, e_eq, e_gt, e_gte, e_lte, e_lt, 163 e_pow, e_mul, e_div, e_add, 164 e_last, e_st, e_while, e_taylor, e_root, e_floor, e_ceil, e_trunc, e_round, 165 e_sqrt, e_not, e_random, e_hypot, e_gcd, 166 e_if, e_ifnot, e_print, e_bitand, e_bitor, e_between, e_clip, e_atan2, e_lerp, 167 e_sgn, e_randomi 168 } type; 169 double value; // is sign in other types 170 int const_index; 171 union { 172 double (*func0)(double); 173 double (*func1)(void *, double); 174 double (*func2)(void *, double, double); 175 } a; 176 struct AVExpr *param[3]; 177 double *var; 178 FFSFC64 *prng_state; 179 }; 180 181 static double etime(double v) 182 { 183 return av_gettime() * 0.000001; 184 } 185 186 static double eval_expr(Parser *p, AVExpr *e) 187 { 188 switch (e->type) { 189 case e_value: return e->value; 190 case e_const: return e->value * p->const_values[e->const_index]; 191 case e_func0: return e->value * e->a.func0(eval_expr(p, e->param[0])); 192 case e_func1: return e->value * e->a.func1(p->opaque, eval_expr(p, e->param[0])); 193 case e_func2: return e->value * e->a.func2(p->opaque, eval_expr(p, e->param[0]), eval_expr(p, e->param[1])); 194 case e_squish: return 1/(1+exp(4*eval_expr(p, e->param[0]))); 195 case e_gauss: { double d = eval_expr(p, e->param[0]); return exp(-d*d/2)/sqrt(2*M_PI); } 196 case e_ld: return e->value * p->var[av_clip(eval_expr(p, e->param[0]), 0, VARS-1)]; 197 case e_isnan: return e->value * !!isnan(eval_expr(p, e->param[0])); 198 case e_isinf: return e->value * !!isinf(eval_expr(p, e->param[0])); 199 case e_floor: return e->value * floor(eval_expr(p, e->param[0])); 200 case e_ceil : return e->value * ceil (eval_expr(p, e->param[0])); 201 case e_trunc: return e->value * trunc(eval_expr(p, e->param[0])); 202 case e_round: return e->value * round(eval_expr(p, e->param[0])); 203 case e_sgn: return e->value * FFDIFFSIGN(eval_expr(p, e->param[0]), 0); 204 case e_sqrt: return e->value * sqrt (eval_expr(p, e->param[0])); 205 case e_not: return e->value * (eval_expr(p, e->param[0]) == 0); 206 case e_if: return e->value * (eval_expr(p, e->param[0]) ? eval_expr(p, e->param[1]) : 207 e->param[2] ? eval_expr(p, e->param[2]) : 0); 208 case e_ifnot: return e->value * (!eval_expr(p, e->param[0]) ? eval_expr(p, e->param[1]) : 209 e->param[2] ? eval_expr(p, e->param[2]) : 0); 210 case e_clip: { 211 double x = eval_expr(p, e->param[0]); 212 double min = eval_expr(p, e->param[1]), max = eval_expr(p, e->param[2]); 213 if (isnan(min) || isnan(max) || isnan(x) || min > max) 214 return NAN; 215 return e->value * av_clipd(eval_expr(p, e->param[0]), min, max); 216 } 217 case e_between: { 218 double d = eval_expr(p, e->param[0]); 219 return e->value * (d >= eval_expr(p, e->param[1]) && 220 d <= eval_expr(p, e->param[2])); 221 } 222 case e_lerp: { 223 double v0 = eval_expr(p, e->param[0]); 224 double v1 = eval_expr(p, e->param[1]); 225 double f = eval_expr(p, e->param[2]); 226 return v0 + (v1 - v0) * f; 227 } 228 case e_print: { 229 double x = eval_expr(p, e->param[0]); 230 int level = e->param[1] ? av_clip(eval_expr(p, e->param[1]), INT_MIN, INT_MAX) : AV_LOG_INFO; 231 av_log(p, level, "%f\n", x); 232 return x; 233 } 234 235 #define COMPUTE_NEXT_RANDOM() \ 236 int idx = av_clip(eval_expr(p, e->param[0]), 0, VARS-1); \ 237 FFSFC64 *s = p->prng_state + idx; \ 238 uint64_t r; \ 239 \ 240 if (!s->counter) { \ 241 r = isnan(p->var[idx]) ? 0 : p->var[idx]; \ 242 ff_sfc64_init(s, r, r, r, 12); \ 243 } \ 244 r = ff_sfc64_get(s); \ 245 p->var[idx] = r; \ 246 247 case e_random: { 248 COMPUTE_NEXT_RANDOM(); 249 return r * (1.0/UINT64_MAX); 250 } 251 case e_randomi: { 252 double min = eval_expr(p, e->param[1]); 253 double max = eval_expr(p, e->param[2]); 254 COMPUTE_NEXT_RANDOM(); 255 return min + (max - min) * r / UINT64_MAX; 256 } 257 case e_while: { 258 double d = NAN; 259 while (eval_expr(p, e->param[0])) 260 d=eval_expr(p, e->param[1]); 261 return d; 262 } 263 case e_taylor: { 264 double t = 1, d = 0, v; 265 double x = eval_expr(p, e->param[1]); 266 int id = e->param[2] ? av_clip(eval_expr(p, e->param[2]), 0, VARS-1) : 0; 267 int i; 268 double var0 = p->var[id]; 269 for(i=0; i<1000; i++) { 270 double ld = d; 271 p->var[id] = i; 272 v = eval_expr(p, e->param[0]); 273 d += t*v; 274 if(ld==d && v) 275 break; 276 t *= x / (i+1); 277 } 278 p->var[id] = var0; 279 return d; 280 } 281 case e_root: { 282 int i, j; 283 double low = -1, high = -1, v, low_v = -DBL_MAX, high_v = DBL_MAX; 284 double var0 = p->var[0]; 285 double x_max = eval_expr(p, e->param[1]); 286 for(i=-1; i<1024; i++) { 287 if(i<255) { 288 p->var[0] = ff_reverse[i&255]*x_max/255; 289 } else { 290 p->var[0] = x_max*pow(0.9, i-255); 291 if (i&1) p->var[0] *= -1; 292 if (i&2) p->var[0] += low; 293 else p->var[0] += high; 294 } 295 v = eval_expr(p, e->param[0]); 296 if (v<=0 && v>low_v) { 297 low = p->var[0]; 298 low_v = v; 299 } 300 if (v>=0 && v<high_v) { 301 high = p->var[0]; 302 high_v = v; 303 } 304 if (low>=0 && high>=0){ 305 for (j=0; j<1000; j++) { 306 p->var[0] = (low+high)*0.5; 307 if (low == p->var[0] || high == p->var[0]) 308 break; 309 v = eval_expr(p, e->param[0]); 310 if (v<=0) low = p->var[0]; 311 if (v>=0) high= p->var[0]; 312 if (isnan(v)) { 313 low = high = v; 314 break; 315 } 316 } 317 break; 318 } 319 } 320 p->var[0] = var0; 321 return -low_v<high_v ? low : high; 322 } 323 default: { 324 double d = eval_expr(p, e->param[0]); 325 double d2 = eval_expr(p, e->param[1]); 326 switch (e->type) { 327 case e_mod: return e->value * (d - floor(d2 ? d / d2 : d * INFINITY) * d2); 328 case e_gcd: return e->value * av_gcd(d,d2); 329 case e_max: return e->value * (d > d2 ? d : d2); 330 case e_min: return e->value * (d < d2 ? d : d2); 331 case e_eq: return e->value * (d == d2 ? 1.0 : 0.0); 332 case e_gt: return e->value * (d > d2 ? 1.0 : 0.0); 333 case e_gte: return e->value * (d >= d2 ? 1.0 : 0.0); 334 case e_lt: return e->value * (d < d2 ? 1.0 : 0.0); 335 case e_lte: return e->value * (d <= d2 ? 1.0 : 0.0); 336 case e_pow: return e->value * pow(d, d2); 337 case e_mul: return e->value * (d * d2); 338 case e_div: return e->value * (d2 ? (d / d2) : d * INFINITY); 339 case e_add: return e->value * (d + d2); 340 case e_last:return e->value * d2; 341 case e_st : { 342 int index = av_clip(d, 0, VARS-1); 343 p->prng_state[index].counter = 0; 344 return e->value * (p->var[index]= d2); 345 } 346 case e_hypot:return e->value * hypot(d, d2); 347 case e_atan2:return e->value * atan2(d, d2); 348 case e_bitand: return isnan(d) || isnan(d2) ? NAN : e->value * ((long int)d & (long int)d2); 349 case e_bitor: return isnan(d) || isnan(d2) ? NAN : e->value * ((long int)d | (long int)d2); 350 } 351 } 352 } 353 return NAN; 354 } 355 356 static int parse_expr(AVExpr **e, Parser *p); 357 358 void av_expr_free(AVExpr *e) 359 { 360 if (!e) return; 361 av_expr_free(e->param[0]); 362 av_expr_free(e->param[1]); 363 av_expr_free(e->param[2]); 364 av_freep(&e->var); 365 av_freep(&e->prng_state); 366 av_freep(&e); 367 } 368 369 static int parse_primary(AVExpr **e, Parser *p) 370 { 371 AVExpr *d = av_mallocz(sizeof(AVExpr)); 372 char *next = p->s, *s0 = p->s; 373 int ret, i; 374 375 if (!d) 376 return AVERROR(ENOMEM); 377 378 /* number */ 379 d->value = av_strtod(p->s, &next); 380 if (next != p->s) { 381 d->type = e_value; 382 p->s= next; 383 *e = d; 384 return 0; 385 } 386 d->value = 1; 387 388 /* named constants */ 389 for (i=0; p->const_names && p->const_names[i]; i++) { 390 if (strmatch(p->s, p->const_names[i])) { 391 p->s+= strlen(p->const_names[i]); 392 d->type = e_const; 393 d->const_index = i; 394 *e = d; 395 return 0; 396 } 397 } 398 for (i = 0; i < FF_ARRAY_ELEMS(constants); i++) { 399 if (strmatch(p->s, constants[i].name)) { 400 p->s += strlen(constants[i].name); 401 d->type = e_value; 402 d->value = constants[i].value; 403 *e = d; 404 return 0; 405 } 406 } 407 408 p->s= strchr(p->s, '('); 409 if (!p->s) { 410 av_log(p, AV_LOG_ERROR, "Undefined constant or missing '(' in '%s'\n", s0); 411 p->s= next; 412 av_expr_free(d); 413 return AVERROR(EINVAL); 414 } 415 p->s++; // "(" 416 if (*next == '(') { // special case do-nothing 417 av_freep(&d); 418 if ((ret = parse_expr(&d, p)) < 0) 419 return ret; 420 if (p->s[0] != ')') { 421 av_log(p, AV_LOG_ERROR, "Missing ')' in '%s'\n", s0); 422 av_expr_free(d); 423 return AVERROR(EINVAL); 424 } 425 p->s++; // ")" 426 *e = d; 427 return 0; 428 } 429 if ((ret = parse_expr(&(d->param[0]), p)) < 0) { 430 av_expr_free(d); 431 return ret; 432 } 433 if (p->s[0]== ',') { 434 p->s++; // "," 435 parse_expr(&d->param[1], p); 436 } 437 if (p->s[0]== ',') { 438 p->s++; // "," 439 parse_expr(&d->param[2], p); 440 } 441 if (p->s[0] != ')') { 442 av_log(p, AV_LOG_ERROR, "Missing ')' or too many args in '%s'\n", s0); 443 av_expr_free(d); 444 return AVERROR(EINVAL); 445 } 446 p->s++; // ")" 447 448 d->type = e_func0; 449 if (strmatch(next, "sinh" )) d->a.func0 = sinh; 450 else if (strmatch(next, "cosh" )) d->a.func0 = cosh; 451 else if (strmatch(next, "tanh" )) d->a.func0 = tanh; 452 else if (strmatch(next, "sin" )) d->a.func0 = sin; 453 else if (strmatch(next, "cos" )) d->a.func0 = cos; 454 else if (strmatch(next, "tan" )) d->a.func0 = tan; 455 else if (strmatch(next, "atan" )) d->a.func0 = atan; 456 else if (strmatch(next, "asin" )) d->a.func0 = asin; 457 else if (strmatch(next, "acos" )) d->a.func0 = acos; 458 else if (strmatch(next, "exp" )) d->a.func0 = exp; 459 else if (strmatch(next, "log" )) d->a.func0 = log; 460 else if (strmatch(next, "abs" )) d->a.func0 = fabs; 461 else if (strmatch(next, "time" )) d->a.func0 = etime; 462 else if (strmatch(next, "squish")) d->type = e_squish; 463 else if (strmatch(next, "gauss" )) d->type = e_gauss; 464 else if (strmatch(next, "mod" )) d->type = e_mod; 465 else if (strmatch(next, "max" )) d->type = e_max; 466 else if (strmatch(next, "min" )) d->type = e_min; 467 else if (strmatch(next, "eq" )) d->type = e_eq; 468 else if (strmatch(next, "gte" )) d->type = e_gte; 469 else if (strmatch(next, "gt" )) d->type = e_gt; 470 else if (strmatch(next, "lte" )) d->type = e_lte; 471 else if (strmatch(next, "lt" )) d->type = e_lt; 472 else if (strmatch(next, "ld" )) d->type = e_ld; 473 else if (strmatch(next, "isnan" )) d->type = e_isnan; 474 else if (strmatch(next, "isinf" )) d->type = e_isinf; 475 else if (strmatch(next, "st" )) d->type = e_st; 476 else if (strmatch(next, "while" )) d->type = e_while; 477 else if (strmatch(next, "taylor")) d->type = e_taylor; 478 else if (strmatch(next, "root" )) d->type = e_root; 479 else if (strmatch(next, "floor" )) d->type = e_floor; 480 else if (strmatch(next, "ceil" )) d->type = e_ceil; 481 else if (strmatch(next, "trunc" )) d->type = e_trunc; 482 else if (strmatch(next, "round" )) d->type = e_round; 483 else if (strmatch(next, "sqrt" )) d->type = e_sqrt; 484 else if (strmatch(next, "not" )) d->type = e_not; 485 else if (strmatch(next, "pow" )) d->type = e_pow; 486 else if (strmatch(next, "print" )) d->type = e_print; 487 else if (strmatch(next, "random")) d->type = e_random; 488 else if (strmatch(next, "randomi")) d->type = e_randomi; 489 else if (strmatch(next, "hypot" )) d->type = e_hypot; 490 else if (strmatch(next, "gcd" )) d->type = e_gcd; 491 else if (strmatch(next, "if" )) d->type = e_if; 492 else if (strmatch(next, "ifnot" )) d->type = e_ifnot; 493 else if (strmatch(next, "bitand")) d->type = e_bitand; 494 else if (strmatch(next, "bitor" )) d->type = e_bitor; 495 else if (strmatch(next, "between"))d->type = e_between; 496 else if (strmatch(next, "clip" )) d->type = e_clip; 497 else if (strmatch(next, "atan2" )) d->type = e_atan2; 498 else if (strmatch(next, "lerp" )) d->type = e_lerp; 499 else if (strmatch(next, "sgn" )) d->type = e_sgn; 500 else { 501 for (i=0; p->func1_names && p->func1_names[i]; i++) { 502 if (strmatch(next, p->func1_names[i])) { 503 d->a.func1 = p->funcs1[i]; 504 d->type = e_func1; 505 d->const_index = i; 506 *e = d; 507 return 0; 508 } 509 } 510 511 for (i=0; p->func2_names && p->func2_names[i]; i++) { 512 if (strmatch(next, p->func2_names[i])) { 513 d->a.func2 = p->funcs2[i]; 514 d->type = e_func2; 515 d->const_index = i; 516 *e = d; 517 return 0; 518 } 519 } 520 521 av_log(p, AV_LOG_ERROR, "Unknown function in '%s'\n", s0); 522 av_expr_free(d); 523 return AVERROR(EINVAL); 524 } 525 526 *e = d; 527 return 0; 528 } 529 530 static AVExpr *make_eval_expr(int type, int value, AVExpr *p0, AVExpr *p1) 531 { 532 AVExpr *e = av_mallocz(sizeof(AVExpr)); 533 if (!e) 534 return NULL; 535 e->type =type ; 536 e->value =value ; 537 e->param[0] =p0 ; 538 e->param[1] =p1 ; 539 return e; 540 } 541 542 static int parse_pow(AVExpr **e, Parser *p, int *sign) 543 { 544 *sign= (*p->s == '+') - (*p->s == '-'); 545 p->s += *sign&1; 546 return parse_primary(e, p); 547 } 548 549 static int parse_dB(AVExpr **e, Parser *p, int *sign) 550 { 551 /* do not filter out the negative sign when parsing a dB value. 552 for example, -3dB is not the same as -(3dB) */ 553 if (*p->s == '-') { 554 char *next; 555 double av_unused ignored = strtod(p->s, &next); 556 if (next != p->s && next[0] == 'd' && next[1] == 'B') { 557 *sign = 0; 558 return parse_primary(e, p); 559 } 560 } 561 return parse_pow(e, p, sign); 562 } 563 564 static int parse_factor(AVExpr **e, Parser *p) 565 { 566 int sign, sign2, ret; 567 AVExpr *e0, *e1, *e2; 568 if ((ret = parse_dB(&e0, p, &sign)) < 0) 569 return ret; 570 while(p->s[0]=='^'){ 571 e1 = e0; 572 p->s++; 573 if ((ret = parse_dB(&e2, p, &sign2)) < 0) { 574 av_expr_free(e1); 575 return ret; 576 } 577 e0 = make_eval_expr(e_pow, 1, e1, e2); 578 if (!e0) { 579 av_expr_free(e1); 580 av_expr_free(e2); 581 return AVERROR(ENOMEM); 582 } 583 if (e0->param[1]) e0->param[1]->value *= (sign2|1); 584 } 585 if (e0) e0->value *= (sign|1); 586 587 *e = e0; 588 return 0; 589 } 590 591 static int parse_term(AVExpr **e, Parser *p) 592 { 593 int ret; 594 AVExpr *e0, *e1, *e2; 595 if ((ret = parse_factor(&e0, p)) < 0) 596 return ret; 597 while (p->s[0]=='*' || p->s[0]=='/') { 598 int c= *p->s++; 599 e1 = e0; 600 if ((ret = parse_factor(&e2, p)) < 0) { 601 av_expr_free(e1); 602 return ret; 603 } 604 e0 = make_eval_expr(c == '*' ? e_mul : e_div, 1, e1, e2); 605 if (!e0) { 606 av_expr_free(e1); 607 av_expr_free(e2); 608 return AVERROR(ENOMEM); 609 } 610 } 611 *e = e0; 612 return 0; 613 } 614 615 static int parse_subexpr(AVExpr **e, Parser *p) 616 { 617 int ret; 618 AVExpr *e0, *e1, *e2; 619 if ((ret = parse_term(&e0, p)) < 0) 620 return ret; 621 while (*p->s == '+' || *p->s == '-') { 622 e1 = e0; 623 if ((ret = parse_term(&e2, p)) < 0) { 624 av_expr_free(e1); 625 return ret; 626 } 627 e0 = make_eval_expr(e_add, 1, e1, e2); 628 if (!e0) { 629 av_expr_free(e1); 630 av_expr_free(e2); 631 return AVERROR(ENOMEM); 632 } 633 }; 634 635 *e = e0; 636 return 0; 637 } 638 639 static int parse_expr(AVExpr **e, Parser *p) 640 { 641 int ret; 642 AVExpr *e0, *e1, *e2; 643 if (p->stack_index <= 0) //protect against stack overflows 644 return AVERROR(EINVAL); 645 p->stack_index--; 646 647 if ((ret = parse_subexpr(&e0, p)) < 0) 648 return ret; 649 while (*p->s == ';') { 650 p->s++; 651 e1 = e0; 652 if ((ret = parse_subexpr(&e2, p)) < 0) { 653 av_expr_free(e1); 654 return ret; 655 } 656 e0 = make_eval_expr(e_last, 1, e1, e2); 657 if (!e0) { 658 av_expr_free(e1); 659 av_expr_free(e2); 660 return AVERROR(ENOMEM); 661 } 662 }; 663 664 p->stack_index++; 665 *e = e0; 666 return 0; 667 } 668 669 static int verify_expr(AVExpr *e) 670 { 671 if (!e) return 0; 672 switch (e->type) { 673 case e_value: 674 case e_const: return 1; 675 case e_func0: 676 case e_func1: 677 case e_squish: 678 case e_ld: 679 case e_gauss: 680 case e_isnan: 681 case e_isinf: 682 case e_floor: 683 case e_ceil: 684 case e_trunc: 685 case e_round: 686 case e_sqrt: 687 case e_not: 688 case e_random: 689 case e_sgn: 690 return verify_expr(e->param[0]) && !e->param[1]; 691 case e_print: 692 return verify_expr(e->param[0]) 693 && (!e->param[1] || verify_expr(e->param[1])); 694 case e_if: 695 case e_ifnot: 696 case e_taylor: 697 return verify_expr(e->param[0]) && verify_expr(e->param[1]) 698 && (!e->param[2] || verify_expr(e->param[2])); 699 case e_between: 700 case e_clip: 701 case e_lerp: 702 case e_randomi: 703 return verify_expr(e->param[0]) && 704 verify_expr(e->param[1]) && 705 verify_expr(e->param[2]); 706 default: return verify_expr(e->param[0]) && verify_expr(e->param[1]) && !e->param[2]; 707 } 708 } 709 710 int av_expr_parse(AVExpr **expr, const char *s, 711 const char * const *const_names, 712 const char * const *func1_names, double (* const *funcs1)(void *, double), 713 const char * const *func2_names, double (* const *funcs2)(void *, double, double), 714 int log_offset, void *log_ctx) 715 { 716 Parser p = { 0 }; 717 AVExpr *e = NULL; 718 char *w = av_malloc(strlen(s) + 1); 719 char *wp = w; 720 const char *s0 = s; 721 int ret = 0; 722 723 if (!w) 724 return AVERROR(ENOMEM); 725 726 while (*s) 727 if (!av_isspace(*s++)) *wp++ = s[-1]; 728 *wp++ = 0; 729 730 p.class = &eval_class; 731 p.stack_index=100; 732 p.s= w; 733 p.const_names = const_names; 734 p.funcs1 = funcs1; 735 p.func1_names = func1_names; 736 p.funcs2 = funcs2; 737 p.func2_names = func2_names; 738 p.log_offset = log_offset; 739 p.log_ctx = log_ctx; 740 741 if ((ret = parse_expr(&e, &p)) < 0) 742 goto end; 743 if (*p.s) { 744 av_log(&p, AV_LOG_ERROR, "Invalid chars '%s' at the end of expression '%s'\n", p.s, s0); 745 ret = AVERROR(EINVAL); 746 goto end; 747 } 748 if (!verify_expr(e)) { 749 ret = AVERROR(EINVAL); 750 goto end; 751 } 752 e->var= av_mallocz(sizeof(double) *VARS); 753 e->prng_state = av_mallocz(sizeof(*e->prng_state) *VARS); 754 if (!e->var || !e->prng_state) { 755 ret = AVERROR(ENOMEM); 756 goto end; 757 } 758 *expr = e; 759 e = NULL; 760 end: 761 av_expr_free(e); 762 av_free(w); 763 return ret; 764 } 765 766 static int expr_count(AVExpr *e, unsigned *counter, int size, int type) 767 { 768 int i; 769 770 if (!e || !counter || !size) 771 return AVERROR(EINVAL); 772 773 for (i = 0; e->type != type && i < 3 && e->param[i]; i++) 774 expr_count(e->param[i], counter, size, type); 775 776 if (e->type == type && e->const_index < size) 777 counter[e->const_index]++; 778 779 return 0; 780 } 781 782 int av_expr_count_vars(AVExpr *e, unsigned *counter, int size) 783 { 784 return expr_count(e, counter, size, e_const); 785 } 786 787 int av_expr_count_func(AVExpr *e, unsigned *counter, int size, int arg) 788 { 789 return expr_count(e, counter, size, ((int[]){e_const, e_func1, e_func2})[arg]); 790 } 791 792 double av_expr_eval(AVExpr *e, const double *const_values, void *opaque) 793 { 794 Parser p = { 0 }; 795 p.var= e->var; 796 p.prng_state= e->prng_state; 797 798 p.const_values = const_values; 799 p.opaque = opaque; 800 return eval_expr(&p, e); 801 } 802 803 int av_expr_parse_and_eval(double *d, const char *s, 804 const char * const *const_names, const double *const_values, 805 const char * const *func1_names, double (* const *funcs1)(void *, double), 806 const char * const *func2_names, double (* const *funcs2)(void *, double, double), 807 void *opaque, int log_offset, void *log_ctx) 808 { 809 AVExpr *e = NULL; 810 int ret = av_expr_parse(&e, s, const_names, func1_names, funcs1, func2_names, funcs2, log_offset, log_ctx); 811 812 if (ret < 0) { 813 *d = NAN; 814 return ret; 815 } 816 *d = av_expr_eval(e, const_values, opaque); 817 av_expr_free(e); 818 return isnan(*d) ? AVERROR(EINVAL) : 0; 819 }