FFmpeg
eval.c
Go to the documentation of this file.
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 "internal.h"
36 #include "log.h"
37 #include "mathematics.h"
38 #include "time.h"
39 #include "avstring.h"
40 #include "timer.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 } Parser;
59 
60 static const AVClass eval_class = {
61  .class_name = "Eval",
62  .item_name = av_default_item_name,
63  .option = NULL,
64  .version = LIBAVUTIL_VERSION_INT,
65  .log_level_offset_offset = offsetof(Parser, log_offset),
66  .parent_log_context_offset = offsetof(Parser, log_ctx),
67 };
68 
69 static const struct {
70  double bin_val;
71  double dec_val;
72  int8_t exp;
73 } si_prefixes['z' - 'E' + 1] = {
74  ['y'-'E']= { 8.271806125530276749e-25, 1e-24, -24 },
75  ['z'-'E']= { 8.4703294725430034e-22, 1e-21, -21 },
76  ['a'-'E']= { 8.6736173798840355e-19, 1e-18, -18 },
77  ['f'-'E']= { 8.8817841970012523e-16, 1e-15, -15 },
78  ['p'-'E']= { 9.0949470177292824e-13, 1e-12, -12 },
79  ['n'-'E']= { 9.3132257461547852e-10, 1e-9, -9 },
80  ['u'-'E']= { 9.5367431640625e-7, 1e-6, -6 },
81  ['m'-'E']= { 9.765625e-4, 1e-3, -3 },
82  ['c'-'E']= { 9.8431332023036951e-3, 1e-2, -2 },
83  ['d'-'E']= { 9.921256574801246e-2, 1e-1, -1 },
84  ['h'-'E']= { 1.0159366732596479e2, 1e2, 2 },
85  ['k'-'E']= { 1.024e3, 1e3, 3 },
86  ['K'-'E']= { 1.024e3, 1e3, 3 },
87  ['M'-'E']= { 1.048576e6, 1e6, 6 },
88  ['G'-'E']= { 1.073741824e9, 1e9, 9 },
89  ['T'-'E']= { 1.099511627776e12, 1e12, 12 },
90  ['P'-'E']= { 1.125899906842624e15, 1e15, 15 },
91  ['E'-'E']= { 1.152921504606847e18, 1e18, 18 },
92  ['Z'-'E']= { 1.1805916207174113e21, 1e21, 21 },
93  ['Y'-'E']= { 1.2089258196146292e24, 1e24, 24 },
94 };
95 
96 static const struct {
97  const char *name;
98  double value;
99 } constants[] = {
100  { "E", M_E },
101  { "PI", M_PI },
102  { "PHI", M_PHI },
103  { "QP2LAMBDA", FF_QP2LAMBDA },
104 };
105 
106 double av_strtod(const char *numstr, char **tail)
107 {
108  double d;
109  char *next;
110  if(numstr[0]=='0' && (numstr[1]|0x20)=='x') {
111  d = strtoul(numstr, &next, 16);
112  } else
113  d = strtod(numstr, &next);
114  /* if parsing succeeded, check for and interpret postfixes */
115  if (next!=numstr) {
116  if (next[0] == 'd' && next[1] == 'B') {
117  /* treat dB as decibels instead of decibytes */
118  d = ff_exp10(d / 20);
119  next += 2;
120  } else if (*next >= 'E' && *next <= 'z') {
121  int e= si_prefixes[*next - 'E'].exp;
122  if (e) {
123  if (next[1] == 'i') {
124  d*= si_prefixes[*next - 'E'].bin_val;
125  next+=2;
126  } else {
127  d*= si_prefixes[*next - 'E'].dec_val;
128  next++;
129  }
130  }
131  }
132 
133  if (*next=='B') {
134  d*=8;
135  next++;
136  }
137  }
138  /* if requested, fill in tail with the position after the last parsed
139  character */
140  if (tail)
141  *tail = next;
142  return d;
143 }
144 
145 #define IS_IDENTIFIER_CHAR(c) ((c) - '0' <= 9U || (c) - 'a' <= 25U || (c) - 'A' <= 25U || (c) == '_')
146 
147 static int strmatch(const char *s, const char *prefix)
148 {
149  int i;
150  for (i=0; prefix[i]; i++) {
151  if (prefix[i] != s[i]) return 0;
152  }
153  /* return 1 only if the s identifier is terminated */
154  return !IS_IDENTIFIER_CHAR(s[i]);
155 }
156 
157 struct AVExpr {
158  enum {
159  e_value, e_const, e_func0, e_func1, e_func2,
160  e_squish, e_gauss, e_ld, e_isnan, e_isinf,
161  e_mod, e_max, e_min, e_eq, e_gt, e_gte, e_lte, e_lt,
162  e_pow, e_mul, e_div, e_add,
163  e_last, e_st, e_while, e_taylor, e_root, e_floor, e_ceil, e_trunc, e_round,
164  e_sqrt, e_not, e_random, e_hypot, e_gcd,
165  e_if, e_ifnot, e_print, e_bitand, e_bitor, e_between, e_clip, e_atan2, e_lerp,
166  e_sgn,
167  } type;
168  double value; // is sign in other types
169  union {
170  int const_index;
171  double (*func0)(double);
172  double (*func1)(void *, double);
173  double (*func2)(void *, double, double);
174  } a;
175  struct AVExpr *param[3];
176  double *var;
177 };
178 
179 static double etime(double v)
180 {
181  return av_gettime() * 0.000001;
182 }
183 
184 static double eval_expr(Parser *p, AVExpr *e)
185 {
186  switch (e->type) {
187  case e_value: return e->value;
188  case e_const: return e->value * p->const_values[e->a.const_index];
189  case e_func0: return e->value * e->a.func0(eval_expr(p, e->param[0]));
190  case e_func1: return e->value * e->a.func1(p->opaque, eval_expr(p, e->param[0]));
191  case e_func2: return e->value * e->a.func2(p->opaque, eval_expr(p, e->param[0]), eval_expr(p, e->param[1]));
192  case e_squish: return 1/(1+exp(4*eval_expr(p, e->param[0])));
193  case e_gauss: { double d = eval_expr(p, e->param[0]); return exp(-d*d/2)/sqrt(2*M_PI); }
194  case e_ld: return e->value * p->var[av_clip(eval_expr(p, e->param[0]), 0, VARS-1)];
195  case e_isnan: return e->value * !!isnan(eval_expr(p, e->param[0]));
196  case e_isinf: return e->value * !!isinf(eval_expr(p, e->param[0]));
197  case e_floor: return e->value * floor(eval_expr(p, e->param[0]));
198  case e_ceil : return e->value * ceil (eval_expr(p, e->param[0]));
199  case e_trunc: return e->value * trunc(eval_expr(p, e->param[0]));
200  case e_round: return e->value * round(eval_expr(p, e->param[0]));
201  case e_sgn: return e->value * FFDIFFSIGN(eval_expr(p, e->param[0]), 0);
202  case e_sqrt: return e->value * sqrt (eval_expr(p, e->param[0]));
203  case e_not: return e->value * (eval_expr(p, e->param[0]) == 0);
204  case e_if: return e->value * (eval_expr(p, e->param[0]) ? eval_expr(p, e->param[1]) :
205  e->param[2] ? eval_expr(p, e->param[2]) : 0);
206  case e_ifnot: 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_clip: {
209  double x = eval_expr(p, e->param[0]);
210  double min = eval_expr(p, e->param[1]), max = eval_expr(p, e->param[2]);
211  if (isnan(min) || isnan(max) || isnan(x) || min > max)
212  return NAN;
213  return e->value * av_clipd(eval_expr(p, e->param[0]), min, max);
214  }
215  case e_between: {
216  double d = eval_expr(p, e->param[0]);
217  return e->value * (d >= eval_expr(p, e->param[1]) &&
218  d <= eval_expr(p, e->param[2]));
219  }
220  case e_lerp: {
221  double v0 = eval_expr(p, e->param[0]);
222  double v1 = eval_expr(p, e->param[1]);
223  double f = eval_expr(p, e->param[2]);
224  return v0 + (v1 - v0) * f;
225  }
226  case e_print: {
227  double x = eval_expr(p, e->param[0]);
228  int level = e->param[1] ? av_clip(eval_expr(p, e->param[1]), INT_MIN, INT_MAX) : AV_LOG_INFO;
229  av_log(p, level, "%f\n", x);
230  return x;
231  }
232  case e_random:{
233  int idx= av_clip(eval_expr(p, e->param[0]), 0, VARS-1);
234  uint64_t r= isnan(p->var[idx]) ? 0 : p->var[idx];
235  r= r*1664525+1013904223;
236  p->var[idx]= r;
237  return e->value * (r * (1.0/UINT64_MAX));
238  }
239  case e_while: {
240  double d = NAN;
241  while (eval_expr(p, e->param[0]))
242  d=eval_expr(p, e->param[1]);
243  return d;
244  }
245  case e_taylor: {
246  double t = 1, d = 0, v;
247  double x = eval_expr(p, e->param[1]);
248  int id = e->param[2] ? av_clip(eval_expr(p, e->param[2]), 0, VARS-1) : 0;
249  int i;
250  double var0 = p->var[id];
251  for(i=0; i<1000; i++) {
252  double ld = d;
253  p->var[id] = i;
254  v = eval_expr(p, e->param[0]);
255  d += t*v;
256  if(ld==d && v)
257  break;
258  t *= x / (i+1);
259  }
260  p->var[id] = var0;
261  return d;
262  }
263  case e_root: {
264  int i, j;
265  double low = -1, high = -1, v, low_v = -DBL_MAX, high_v = DBL_MAX;
266  double var0 = p->var[0];
267  double x_max = eval_expr(p, e->param[1]);
268  for(i=-1; i<1024; i++) {
269  if(i<255) {
270  p->var[0] = ff_reverse[i&255]*x_max/255;
271  } else {
272  p->var[0] = x_max*pow(0.9, i-255);
273  if (i&1) p->var[0] *= -1;
274  if (i&2) p->var[0] += low;
275  else p->var[0] += high;
276  }
277  v = eval_expr(p, e->param[0]);
278  if (v<=0 && v>low_v) {
279  low = p->var[0];
280  low_v = v;
281  }
282  if (v>=0 && v<high_v) {
283  high = p->var[0];
284  high_v = v;
285  }
286  if (low>=0 && high>=0){
287  for (j=0; j<1000; j++) {
288  p->var[0] = (low+high)*0.5;
289  if (low == p->var[0] || high == p->var[0])
290  break;
291  v = eval_expr(p, e->param[0]);
292  if (v<=0) low = p->var[0];
293  if (v>=0) high= p->var[0];
294  if (isnan(v)) {
295  low = high = v;
296  break;
297  }
298  }
299  break;
300  }
301  }
302  p->var[0] = var0;
303  return -low_v<high_v ? low : high;
304  }
305  default: {
306  double d = eval_expr(p, e->param[0]);
307  double d2 = eval_expr(p, e->param[1]);
308  switch (e->type) {
309  case e_mod: return e->value * (d - floor((!CONFIG_FTRAPV || d2) ? d / d2 : d * INFINITY) * d2);
310  case e_gcd: return e->value * av_gcd(d,d2);
311  case e_max: return e->value * (d > d2 ? d : d2);
312  case e_min: return e->value * (d < d2 ? d : d2);
313  case e_eq: return e->value * (d == d2 ? 1.0 : 0.0);
314  case e_gt: return e->value * (d > d2 ? 1.0 : 0.0);
315  case e_gte: return e->value * (d >= d2 ? 1.0 : 0.0);
316  case e_lt: return e->value * (d < d2 ? 1.0 : 0.0);
317  case e_lte: return e->value * (d <= d2 ? 1.0 : 0.0);
318  case e_pow: return e->value * pow(d, d2);
319  case e_mul: return e->value * (d * d2);
320  case e_div: return e->value * ((!CONFIG_FTRAPV || d2 ) ? (d / d2) : d * INFINITY);
321  case e_add: return e->value * (d + d2);
322  case e_last:return e->value * d2;
323  case e_st : return e->value * (p->var[av_clip(d, 0, VARS-1)]= d2);
324  case e_hypot:return e->value * hypot(d, d2);
325  case e_atan2:return e->value * atan2(d, d2);
326  case e_bitand: return isnan(d) || isnan(d2) ? NAN : e->value * ((long int)d & (long int)d2);
327  case e_bitor: return isnan(d) || isnan(d2) ? NAN : e->value * ((long int)d | (long int)d2);
328  }
329  }
330  }
331  return NAN;
332 }
333 
334 static int parse_expr(AVExpr **e, Parser *p);
335 
336 void av_expr_free(AVExpr *e)
337 {
338  if (!e) return;
339  av_expr_free(e->param[0]);
340  av_expr_free(e->param[1]);
341  av_expr_free(e->param[2]);
342  av_freep(&e->var);
343  av_freep(&e);
344 }
345 
346 static int parse_primary(AVExpr **e, Parser *p)
347 {
348  AVExpr *d = av_mallocz(sizeof(AVExpr));
349  char *next = p->s, *s0 = p->s;
350  int ret, i;
351 
352  if (!d)
353  return AVERROR(ENOMEM);
354 
355  /* number */
356  d->value = av_strtod(p->s, &next);
357  if (next != p->s) {
358  d->type = e_value;
359  p->s= next;
360  *e = d;
361  return 0;
362  }
363  d->value = 1;
364 
365  /* named constants */
366  for (i=0; p->const_names && p->const_names[i]; i++) {
367  if (strmatch(p->s, p->const_names[i])) {
368  p->s+= strlen(p->const_names[i]);
369  d->type = e_const;
370  d->a.const_index = i;
371  *e = d;
372  return 0;
373  }
374  }
375  for (i = 0; i < FF_ARRAY_ELEMS(constants); i++) {
376  if (strmatch(p->s, constants[i].name)) {
377  p->s += strlen(constants[i].name);
378  d->type = e_value;
379  d->value = constants[i].value;
380  *e = d;
381  return 0;
382  }
383  }
384 
385  p->s= strchr(p->s, '(');
386  if (!p->s) {
387  av_log(p, AV_LOG_ERROR, "Undefined constant or missing '(' in '%s'\n", s0);
388  p->s= next;
389  av_expr_free(d);
390  return AVERROR(EINVAL);
391  }
392  p->s++; // "("
393  if (*next == '(') { // special case do-nothing
394  av_freep(&d);
395  if ((ret = parse_expr(&d, p)) < 0)
396  return ret;
397  if (p->s[0] != ')') {
398  av_log(p, AV_LOG_ERROR, "Missing ')' in '%s'\n", s0);
399  av_expr_free(d);
400  return AVERROR(EINVAL);
401  }
402  p->s++; // ")"
403  *e = d;
404  return 0;
405  }
406  if ((ret = parse_expr(&(d->param[0]), p)) < 0) {
407  av_expr_free(d);
408  return ret;
409  }
410  if (p->s[0]== ',') {
411  p->s++; // ","
412  parse_expr(&d->param[1], p);
413  }
414  if (p->s[0]== ',') {
415  p->s++; // ","
416  parse_expr(&d->param[2], p);
417  }
418  if (p->s[0] != ')') {
419  av_log(p, AV_LOG_ERROR, "Missing ')' or too many args in '%s'\n", s0);
420  av_expr_free(d);
421  return AVERROR(EINVAL);
422  }
423  p->s++; // ")"
424 
425  d->type = e_func0;
426  if (strmatch(next, "sinh" )) d->a.func0 = sinh;
427  else if (strmatch(next, "cosh" )) d->a.func0 = cosh;
428  else if (strmatch(next, "tanh" )) d->a.func0 = tanh;
429  else if (strmatch(next, "sin" )) d->a.func0 = sin;
430  else if (strmatch(next, "cos" )) d->a.func0 = cos;
431  else if (strmatch(next, "tan" )) d->a.func0 = tan;
432  else if (strmatch(next, "atan" )) d->a.func0 = atan;
433  else if (strmatch(next, "asin" )) d->a.func0 = asin;
434  else if (strmatch(next, "acos" )) d->a.func0 = acos;
435  else if (strmatch(next, "exp" )) d->a.func0 = exp;
436  else if (strmatch(next, "log" )) d->a.func0 = log;
437  else if (strmatch(next, "abs" )) d->a.func0 = fabs;
438  else if (strmatch(next, "time" )) d->a.func0 = etime;
439  else if (strmatch(next, "squish")) d->type = e_squish;
440  else if (strmatch(next, "gauss" )) d->type = e_gauss;
441  else if (strmatch(next, "mod" )) d->type = e_mod;
442  else if (strmatch(next, "max" )) d->type = e_max;
443  else if (strmatch(next, "min" )) d->type = e_min;
444  else if (strmatch(next, "eq" )) d->type = e_eq;
445  else if (strmatch(next, "gte" )) d->type = e_gte;
446  else if (strmatch(next, "gt" )) d->type = e_gt;
447  else if (strmatch(next, "lte" )) d->type = e_lte;
448  else if (strmatch(next, "lt" )) d->type = e_lt;
449  else if (strmatch(next, "ld" )) d->type = e_ld;
450  else if (strmatch(next, "isnan" )) d->type = e_isnan;
451  else if (strmatch(next, "isinf" )) d->type = e_isinf;
452  else if (strmatch(next, "st" )) d->type = e_st;
453  else if (strmatch(next, "while" )) d->type = e_while;
454  else if (strmatch(next, "taylor")) d->type = e_taylor;
455  else if (strmatch(next, "root" )) d->type = e_root;
456  else if (strmatch(next, "floor" )) d->type = e_floor;
457  else if (strmatch(next, "ceil" )) d->type = e_ceil;
458  else if (strmatch(next, "trunc" )) d->type = e_trunc;
459  else if (strmatch(next, "round" )) d->type = e_round;
460  else if (strmatch(next, "sqrt" )) d->type = e_sqrt;
461  else if (strmatch(next, "not" )) d->type = e_not;
462  else if (strmatch(next, "pow" )) d->type = e_pow;
463  else if (strmatch(next, "print" )) d->type = e_print;
464  else if (strmatch(next, "random")) d->type = e_random;
465  else if (strmatch(next, "hypot" )) d->type = e_hypot;
466  else if (strmatch(next, "gcd" )) d->type = e_gcd;
467  else if (strmatch(next, "if" )) d->type = e_if;
468  else if (strmatch(next, "ifnot" )) d->type = e_ifnot;
469  else if (strmatch(next, "bitand")) d->type = e_bitand;
470  else if (strmatch(next, "bitor" )) d->type = e_bitor;
471  else if (strmatch(next, "between"))d->type = e_between;
472  else if (strmatch(next, "clip" )) d->type = e_clip;
473  else if (strmatch(next, "atan2" )) d->type = e_atan2;
474  else if (strmatch(next, "lerp" )) d->type = e_lerp;
475  else if (strmatch(next, "sgn" )) d->type = e_sgn;
476  else {
477  for (i=0; p->func1_names && p->func1_names[i]; i++) {
478  if (strmatch(next, p->func1_names[i])) {
479  d->a.func1 = p->funcs1[i];
480  d->type = e_func1;
481  *e = d;
482  return 0;
483  }
484  }
485 
486  for (i=0; p->func2_names && p->func2_names[i]; i++) {
487  if (strmatch(next, p->func2_names[i])) {
488  d->a.func2 = p->funcs2[i];
489  d->type = e_func2;
490  *e = d;
491  return 0;
492  }
493  }
494 
495  av_log(p, AV_LOG_ERROR, "Unknown function in '%s'\n", s0);
496  av_expr_free(d);
497  return AVERROR(EINVAL);
498  }
499 
500  *e = d;
501  return 0;
502 }
503 
504 static AVExpr *make_eval_expr(int type, int value, AVExpr *p0, AVExpr *p1)
505 {
506  AVExpr *e = av_mallocz(sizeof(AVExpr));
507  if (!e)
508  return NULL;
509  e->type =type ;
510  e->value =value ;
511  e->param[0] =p0 ;
512  e->param[1] =p1 ;
513  return e;
514 }
515 
516 static int parse_pow(AVExpr **e, Parser *p, int *sign)
517 {
518  *sign= (*p->s == '+') - (*p->s == '-');
519  p->s += *sign&1;
520  return parse_primary(e, p);
521 }
522 
523 static int parse_dB(AVExpr **e, Parser *p, int *sign)
524 {
525  /* do not filter out the negative sign when parsing a dB value.
526  for example, -3dB is not the same as -(3dB) */
527  if (*p->s == '-') {
528  char *next;
529  double av_unused ignored = strtod(p->s, &next);
530  if (next != p->s && next[0] == 'd' && next[1] == 'B') {
531  *sign = 0;
532  return parse_primary(e, p);
533  }
534  }
535  return parse_pow(e, p, sign);
536 }
537 
538 static int parse_factor(AVExpr **e, Parser *p)
539 {
540  int sign, sign2, ret;
541  AVExpr *e0, *e1, *e2;
542  if ((ret = parse_dB(&e0, p, &sign)) < 0)
543  return ret;
544  while(p->s[0]=='^'){
545  e1 = e0;
546  p->s++;
547  if ((ret = parse_dB(&e2, p, &sign2)) < 0) {
548  av_expr_free(e1);
549  return ret;
550  }
551  e0 = make_eval_expr(e_pow, 1, e1, e2);
552  if (!e0) {
553  av_expr_free(e1);
554  av_expr_free(e2);
555  return AVERROR(ENOMEM);
556  }
557  if (e0->param[1]) e0->param[1]->value *= (sign2|1);
558  }
559  if (e0) e0->value *= (sign|1);
560 
561  *e = e0;
562  return 0;
563 }
564 
565 static int parse_term(AVExpr **e, Parser *p)
566 {
567  int ret;
568  AVExpr *e0, *e1, *e2;
569  if ((ret = parse_factor(&e0, p)) < 0)
570  return ret;
571  while (p->s[0]=='*' || p->s[0]=='/') {
572  int c= *p->s++;
573  e1 = e0;
574  if ((ret = parse_factor(&e2, p)) < 0) {
575  av_expr_free(e1);
576  return ret;
577  }
578  e0 = make_eval_expr(c == '*' ? e_mul : e_div, 1, e1, e2);
579  if (!e0) {
580  av_expr_free(e1);
581  av_expr_free(e2);
582  return AVERROR(ENOMEM);
583  }
584  }
585  *e = e0;
586  return 0;
587 }
588 
589 static int parse_subexpr(AVExpr **e, Parser *p)
590 {
591  int ret;
592  AVExpr *e0, *e1, *e2;
593  if ((ret = parse_term(&e0, p)) < 0)
594  return ret;
595  while (*p->s == '+' || *p->s == '-') {
596  e1 = e0;
597  if ((ret = parse_term(&e2, p)) < 0) {
598  av_expr_free(e1);
599  return ret;
600  }
601  e0 = make_eval_expr(e_add, 1, e1, e2);
602  if (!e0) {
603  av_expr_free(e1);
604  av_expr_free(e2);
605  return AVERROR(ENOMEM);
606  }
607  };
608 
609  *e = e0;
610  return 0;
611 }
612 
613 static int parse_expr(AVExpr **e, Parser *p)
614 {
615  int ret;
616  AVExpr *e0, *e1, *e2;
617  if (p->stack_index <= 0) //protect against stack overflows
618  return AVERROR(EINVAL);
619  p->stack_index--;
620 
621  if ((ret = parse_subexpr(&e0, p)) < 0)
622  return ret;
623  while (*p->s == ';') {
624  p->s++;
625  e1 = e0;
626  if ((ret = parse_subexpr(&e2, p)) < 0) {
627  av_expr_free(e1);
628  return ret;
629  }
630  e0 = make_eval_expr(e_last, 1, e1, e2);
631  if (!e0) {
632  av_expr_free(e1);
633  av_expr_free(e2);
634  return AVERROR(ENOMEM);
635  }
636  };
637 
638  p->stack_index++;
639  *e = e0;
640  return 0;
641 }
642 
643 static int verify_expr(AVExpr *e)
644 {
645  if (!e) return 0;
646  switch (e->type) {
647  case e_value:
648  case e_const: return 1;
649  case e_func0:
650  case e_func1:
651  case e_squish:
652  case e_ld:
653  case e_gauss:
654  case e_isnan:
655  case e_isinf:
656  case e_floor:
657  case e_ceil:
658  case e_trunc:
659  case e_round:
660  case e_sqrt:
661  case e_not:
662  case e_random:
663  case e_sgn:
664  return verify_expr(e->param[0]) && !e->param[1];
665  case e_print:
666  return verify_expr(e->param[0])
667  && (!e->param[1] || verify_expr(e->param[1]));
668  case e_if:
669  case e_ifnot:
670  case e_taylor:
671  return verify_expr(e->param[0]) && verify_expr(e->param[1])
672  && (!e->param[2] || verify_expr(e->param[2]));
673  case e_between:
674  case e_clip:
675  case e_lerp:
676  return verify_expr(e->param[0]) &&
677  verify_expr(e->param[1]) &&
678  verify_expr(e->param[2]);
679  default: return verify_expr(e->param[0]) && verify_expr(e->param[1]) && !e->param[2];
680  }
681 }
682 
683 int av_expr_parse(AVExpr **expr, const char *s,
684  const char * const *const_names,
685  const char * const *func1_names, double (* const *funcs1)(void *, double),
686  const char * const *func2_names, double (* const *funcs2)(void *, double, double),
687  int log_offset, void *log_ctx)
688 {
689  Parser p = { 0 };
690  AVExpr *e = NULL;
691  char *w = av_malloc(strlen(s) + 1);
692  char *wp = w;
693  const char *s0 = s;
694  int ret = 0;
695 
696  if (!w)
697  return AVERROR(ENOMEM);
698 
699  while (*s)
700  if (!av_isspace(*s++)) *wp++ = s[-1];
701  *wp++ = 0;
702 
703  p.class = &eval_class;
704  p.stack_index=100;
705  p.s= w;
706  p.const_names = const_names;
707  p.funcs1 = funcs1;
708  p.func1_names = func1_names;
709  p.funcs2 = funcs2;
710  p.func2_names = func2_names;
711  p.log_offset = log_offset;
712  p.log_ctx = log_ctx;
713 
714  if ((ret = parse_expr(&e, &p)) < 0)
715  goto end;
716  if (*p.s) {
717  av_log(&p, AV_LOG_ERROR, "Invalid chars '%s' at the end of expression '%s'\n", p.s, s0);
718  ret = AVERROR(EINVAL);
719  goto end;
720  }
721  if (!verify_expr(e)) {
722  ret = AVERROR(EINVAL);
723  goto end;
724  }
725  e->var= av_mallocz(sizeof(double) *VARS);
726  if (!e->var) {
727  ret = AVERROR(ENOMEM);
728  goto end;
729  }
730  *expr = e;
731  e = NULL;
732 end:
733  av_expr_free(e);
734  av_free(w);
735  return ret;
736 }
737 
738 int av_expr_count_vars(AVExpr *e, unsigned *counter, int size)
739 {
740  int i;
741 
742  if (!e || !counter || !size)
743  return AVERROR(EINVAL);
744 
745  for (i = 0; e->type != e_const && i < 3 && e->param[i]; i++)
746  av_expr_count_vars(e->param[i], counter, size);
747 
748  if (e->type == e_const && e->a.const_index < size)
749  counter[e->a.const_index]++;
750 
751  return 0;
752 }
753 
754 double av_expr_eval(AVExpr *e, const double *const_values, void *opaque)
755 {
756  Parser p = { 0 };
757  p.var= e->var;
758 
759  p.const_values = const_values;
760  p.opaque = opaque;
761  return eval_expr(&p, e);
762 }
763 
764 int av_expr_parse_and_eval(double *d, const char *s,
765  const char * const *const_names, const double *const_values,
766  const char * const *func1_names, double (* const *funcs1)(void *, double),
767  const char * const *func2_names, double (* const *funcs2)(void *, double, double),
768  void *opaque, int log_offset, void *log_ctx)
769 {
770  AVExpr *e = NULL;
771  int ret = av_expr_parse(&e, s, const_names, func1_names, funcs1, func2_names, funcs2, log_offset, log_ctx);
772 
773  if (ret < 0) {
774  *d = NAN;
775  return ret;
776  }
777  *d = av_expr_eval(e, const_values, opaque);
778  av_expr_free(e);
779  return isnan(*d) ? AVERROR(EINVAL) : 0;
780 }
VARS
#define VARS
Definition: eval.c:56
verify_expr
static int verify_expr(AVExpr *e)
Definition: eval.c:643
Parser::func1_names
const char *const * func1_names
Definition: eval.c:50
NULL
#define NULL
Definition: coverity.c:32
AVExpr::type
enum AVExpr::@295 type
isinf
#define isinf(x)
Definition: libm.h:317
ret
ret
Definition: filter_design.txt:187
LIBAVUTIL_VERSION_INT
#define LIBAVUTIL_VERSION_INT
Definition: version.h:85
ff_reverse
const uint8_t ff_reverse[256]
Definition: reverse.c:23
av_default_item_name
const char * av_default_item_name(void *ptr)
Return the context name.
Definition: log.c:191
av_isspace
static av_const int av_isspace(int c)
Locale-independent conversion of ASCII isspace.
Definition: avstring.h:222
a
The reader does not expect b to be semantically here and if the code is changed by maybe adding a a division or other the signedness will almost certainly be mistaken To avoid this confusion a new type was SUINT is the C unsigned type but it holds a signed int to use the same example SUINT a
Definition: undefined.txt:36
avutil.h
Convenience header that includes libavutil&#39;s core.
type
GLint GLenum type
Definition: opengl_enc.c:104
av_mallocz
void * av_mallocz(size_t size)
Allocate a memory block with alignment suitable for all memory accesses (including vectors if availab...
Definition: mem.c:236
av_expr_parse
int av_expr_parse(AVExpr **expr, const char *s, const char *const *const_names, const char *const *func1_names, double(*const *funcs1)(void *, double), const char *const *func2_names, double(*const *funcs2)(void *, double, double), int log_offset, void *log_ctx)
Parse an expression.
Definition: eval.c:683
v0
GLfloat v0
Definition: opengl_enc.c:106
Parser::log_ctx
void * log_ctx
Definition: eval.c:55
attributes.h
Macro definitions for various function/variable attributes.
AVClass::class_name
const char * class_name
The name of the class; usually it is the same name as the context structure type to which the AVClass...
Definition: log.h:72
parse_dB
static int parse_dB(AVExpr **e, Parser *p, int *sign)
Definition: eval.c:523
av_malloc
#define av_malloc(s)
Definition: tableprint_vlc.h:31
f
#define f(width, name)
Definition: cbs_vp9.c:255
end
static av_cold int end(AVCodecContext *avctx)
Definition: avrndec.c:90
c
Undefined Behavior In the C some operations are like signed integer dereferencing freed accessing outside allocated Undefined Behavior must not occur in a C it is not safe even if the output of undefined operations is unused The unsafety may seem nit picking but Optimizing compilers have in fact optimized code on the assumption that no undefined Behavior occurs Optimizing code based on wrong assumptions can and has in some cases lead to effects beyond the output of computations The signed integer overflow problem in speed critical code Code which is highly optimized and works with signed integers sometimes has the problem that often the output of the computation does not c
Definition: undefined.txt:32
parse_expr
static int parse_expr(AVExpr **e, Parser *p)
Definition: eval.c:613
Parser
Definition: eval.c:43
value
GLsizei GLboolean const GLfloat * value
Definition: opengl_enc.c:108
AVExpr
Definition: eval.c:157
strtod
double strtod(const char *, char **)
AVExpr::func2
double(* func2)(void *, double, double)
Definition: eval.c:173
Parser::const_names
const char *const * const_names
Definition: eval.c:48
parse_pow
static int parse_pow(AVExpr **e, Parser *p, int *sign)
Definition: eval.c:516
parse_factor
static int parse_factor(AVExpr **e, Parser *p)
Definition: eval.c:538
max
#define max(a, b)
Definition: cuda_runtime.h:33
size
ptrdiff_t size
Definition: opengl_enc.c:100
timer.h
high precision timer, useful to profile code
av_log
#define av_log(a,...)
Definition: tableprint_vlc.h:28
parse_subexpr
static int parse_subexpr(AVExpr **e, Parser *p)
Definition: eval.c:589
av_expr_parse_and_eval
int av_expr_parse_and_eval(double *d, const char *s, const char *const *const_names, const double *const_values, const char *const *func1_names, double(*const *funcs1)(void *, double), const char *const *func2_names, double(*const *funcs2)(void *, double, double), void *opaque, int log_offset, void *log_ctx)
Parse and evaluate an expression.
Definition: eval.c:764
Parser::const_values
const double * const_values
Definition: eval.c:47
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:259
ff_exp10
static av_always_inline double ff_exp10(double x)
Compute 10^x for floating point values.
Definition: ffmath.h:42
AV_LOG_ERROR
#define AV_LOG_ERROR
Something went wrong and cannot losslessly be recovered.
Definition: log.h:176
IS_IDENTIFIER_CHAR
#define IS_IDENTIFIER_CHAR(c)
Definition: eval.c:145
si_prefixes
static const struct @293 si_prefixes['z'- 'E'+1]
func1
static double(*const func1[])(void *, double)
Definition: vf_rotate.c:189
AVExpr::const_index
int const_index
Definition: eval.c:170
M_E
#define M_E
Definition: mathematics.h:37
r
const char * r
Definition: vf_curves.c:114
s0
#define s0
Definition: regdef.h:37
parse_term
static int parse_term(AVExpr **e, Parser *p)
Definition: eval.c:565
av_gcd
int64_t av_gcd(int64_t a, int64_t b)
Compute the greatest common divisor of two integer operands.
Definition: mathematics.c:37
round
static av_always_inline av_const double round(double x)
Definition: libm.h:444
constants
static const struct @294 constants[]
exp
int8_t exp
Definition: eval.c:72
FFDIFFSIGN
#define FFDIFFSIGN(x, y)
Comparator.
Definition: common.h:92
internal.h
common internal API header
hypot
static av_const double hypot(double x, double y)
Definition: libm.h:366
etime
static double etime(double v)
Definition: eval.c:179
b
#define b
Definition: input.c:41
NAN
#define NAN
Definition: mathematics.h:64
w
uint8_t w
Definition: llviddspenc.c:38
trunc
static av_always_inline av_const double trunc(double x)
Definition: libm.h:458
strmatch
static int strmatch(const char *s, const char *prefix)
Definition: eval.c:147
parse_primary
static int parse_primary(AVExpr **e, Parser *p)
Definition: eval.c:346
Parser::funcs1
double(*const funcs1)(void *, double a)
Definition: eval.c:49
bin_val
double bin_val
Definition: eval.c:70
FF_ARRAY_ELEMS
#define FF_ARRAY_ELEMS(a)
Definition: sinewin_tablegen_template.c:38
Parser::opaque
void * opaque
Definition: eval.c:53
av_gettime
int64_t av_gettime(void)
Get the current time in microseconds.
Definition: time.c:39
av_strtod
double av_strtod(const char *numstr, char **tail)
Parse the string in numstr and return its value as a double.
Definition: eval.c:106
Parser::class
const AVClass * class
Definition: eval.c:44
AV_LOG_INFO
#define AV_LOG_INFO
Standard information.
Definition: log.h:187
eval_expr
static double eval_expr(Parser *p, AVExpr *e)
Definition: eval.c:184
av_expr_free
void av_expr_free(AVExpr *e)
Free a parsed expression previously created with av_expr_parse().
Definition: eval.c:336
AVExpr::var
double * var
Definition: eval.c:176
func2
double(* func2[])(void *, double, double)
Definition: af_afftfilt.c:120
Parser::s
char * s
Definition: eval.c:46
value
double value
Definition: eval.c:98
AVClass
Describe the class of an AVClass context structure.
Definition: log.h:67
eval_class
static const AVClass eval_class
Definition: eval.c:60
AVExpr::func1
double(* func1)(void *, double)
Definition: eval.c:172
Parser::var
double * var
Definition: eval.c:57
isnan
#define isnan(x)
Definition: libm.h:340
AVExpr::param
struct AVExpr * param[3]
Definition: eval.c:175
M_PHI
#define M_PHI
Definition: mathematics.h:49
Parser::func2_names
const char *const * func2_names
Definition: eval.c:52
level
uint8_t level
Definition: svq3.c:207
ffmath.h
internal math functions header
int
int
Definition: ffmpeg_filter.c:191
common.h
common internal and external API header
Parser::stack_index
int stack_index
Definition: eval.c:45
av_expr_count_vars
int av_expr_count_vars(AVExpr *e, unsigned *counter, int size)
Track the presence of variables and their number of occurrences in a parsed expression.
Definition: eval.c:738
av_free
#define av_free(p)
Definition: tableprint_vlc.h:34
dec_val
double dec_val
Definition: eval.c:71
av_expr_eval
double av_expr_eval(AVExpr *e, const double *const_values, void *opaque)
Evaluate a previously parsed expression.
Definition: eval.c:754
FF_QP2LAMBDA
#define FF_QP2LAMBDA
factor to convert from H.263 QP to lambda
Definition: avutil.h:227
make_eval_expr
static AVExpr * make_eval_expr(int type, int value, AVExpr *p0, AVExpr *p1)
Definition: eval.c:504
av_freep
#define av_freep(p)
Definition: tableprint_vlc.h:35
M_PI
#define M_PI
Definition: mathematics.h:52
Parser::log_offset
int log_offset
Definition: eval.c:54
Parser::funcs2
double(*const funcs2)(void *, double a, double b)
Definition: eval.c:51
name
const char * name
Definition: eval.c:97
AVERROR
Filter the word “frame” indicates either a video frame or a group of audio as stored in an AVFrame structure Format for each input and each output the list of supported formats For video that means pixel format For audio that means channel sample they are references to shared objects When the negotiation mechanism computes the intersection of the formats supported at each end of a all references to both lists are replaced with a reference to the intersection And when a single format is eventually chosen for a link amongst the remaining all references to the list are updated That means that if a filter requires that its input and output have the same format amongst a supported all it has to do is use a reference to the same list of formats query_formats can leave some formats unset and return AVERROR(EAGAIN) to cause the negotiation mechanism toagain later.That can be used by filters with complex requirements to use the format negotiated on one link to set the formats supported on another.Frame references ownership and permissions
AVExpr::func0
double(* func0)(double)
Definition: eval.c:171
INFINITY
#define INFINITY
Definition: mathematics.h:67
min
float min
Definition: vorbis_enc_data.h:456
id
enum AVCodecID id
Definition: extract_extradata_bsf.c:332
av_unused
#define av_unused
Definition: attributes.h:125
AVExpr::value
double value
Definition: eval.c:168
AVExpr::a
union AVExpr::@296 a
eval.h
simple arithmetic expression evaluator
name
const char * name
Definition: opengl_enc.c:102
Generated on Thu Dec 5 2019 19:21:56 for FFmpeg by   doxygen 1.8.11