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  int const_index;
170  union {
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->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(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 * (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->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  d->const_index = i;
482  *e = d;
483  return 0;
484  }
485  }
486 
487  for (i=0; p->func2_names && p->func2_names[i]; i++) {
488  if (strmatch(next, p->func2_names[i])) {
489  d->a.func2 = p->funcs2[i];
490  d->type = e_func2;
491  d->const_index = i;
492  *e = d;
493  return 0;
494  }
495  }
496 
497  av_log(p, AV_LOG_ERROR, "Unknown function in '%s'\n", s0);
498  av_expr_free(d);
499  return AVERROR(EINVAL);
500  }
501 
502  *e = d;
503  return 0;
504 }
505 
506 static AVExpr *make_eval_expr(int type, int value, AVExpr *p0, AVExpr *p1)
507 {
508  AVExpr *e = av_mallocz(sizeof(AVExpr));
509  if (!e)
510  return NULL;
511  e->type =type ;
512  e->value =value ;
513  e->param[0] =p0 ;
514  e->param[1] =p1 ;
515  return e;
516 }
517 
518 static int parse_pow(AVExpr **e, Parser *p, int *sign)
519 {
520  *sign= (*p->s == '+') - (*p->s == '-');
521  p->s += *sign&1;
522  return parse_primary(e, p);
523 }
524 
525 static int parse_dB(AVExpr **e, Parser *p, int *sign)
526 {
527  /* do not filter out the negative sign when parsing a dB value.
528  for example, -3dB is not the same as -(3dB) */
529  if (*p->s == '-') {
530  char *next;
531  double av_unused ignored = strtod(p->s, &next);
532  if (next != p->s && next[0] == 'd' && next[1] == 'B') {
533  *sign = 0;
534  return parse_primary(e, p);
535  }
536  }
537  return parse_pow(e, p, sign);
538 }
539 
540 static int parse_factor(AVExpr **e, Parser *p)
541 {
542  int sign, sign2, ret;
543  AVExpr *e0, *e1, *e2;
544  if ((ret = parse_dB(&e0, p, &sign)) < 0)
545  return ret;
546  while(p->s[0]=='^'){
547  e1 = e0;
548  p->s++;
549  if ((ret = parse_dB(&e2, p, &sign2)) < 0) {
550  av_expr_free(e1);
551  return ret;
552  }
553  e0 = make_eval_expr(e_pow, 1, e1, e2);
554  if (!e0) {
555  av_expr_free(e1);
556  av_expr_free(e2);
557  return AVERROR(ENOMEM);
558  }
559  if (e0->param[1]) e0->param[1]->value *= (sign2|1);
560  }
561  if (e0) e0->value *= (sign|1);
562 
563  *e = e0;
564  return 0;
565 }
566 
567 static int parse_term(AVExpr **e, Parser *p)
568 {
569  int ret;
570  AVExpr *e0, *e1, *e2;
571  if ((ret = parse_factor(&e0, p)) < 0)
572  return ret;
573  while (p->s[0]=='*' || p->s[0]=='/') {
574  int c= *p->s++;
575  e1 = e0;
576  if ((ret = parse_factor(&e2, p)) < 0) {
577  av_expr_free(e1);
578  return ret;
579  }
580  e0 = make_eval_expr(c == '*' ? e_mul : e_div, 1, e1, e2);
581  if (!e0) {
582  av_expr_free(e1);
583  av_expr_free(e2);
584  return AVERROR(ENOMEM);
585  }
586  }
587  *e = e0;
588  return 0;
589 }
590 
591 static int parse_subexpr(AVExpr **e, Parser *p)
592 {
593  int ret;
594  AVExpr *e0, *e1, *e2;
595  if ((ret = parse_term(&e0, p)) < 0)
596  return ret;
597  while (*p->s == '+' || *p->s == '-') {
598  e1 = e0;
599  if ((ret = parse_term(&e2, p)) < 0) {
600  av_expr_free(e1);
601  return ret;
602  }
603  e0 = make_eval_expr(e_add, 1, e1, e2);
604  if (!e0) {
605  av_expr_free(e1);
606  av_expr_free(e2);
607  return AVERROR(ENOMEM);
608  }
609  };
610 
611  *e = e0;
612  return 0;
613 }
614 
615 static int parse_expr(AVExpr **e, Parser *p)
616 {
617  int ret;
618  AVExpr *e0, *e1, *e2;
619  if (p->stack_index <= 0) //protect against stack overflows
620  return AVERROR(EINVAL);
621  p->stack_index--;
622 
623  if ((ret = parse_subexpr(&e0, p)) < 0)
624  return ret;
625  while (*p->s == ';') {
626  p->s++;
627  e1 = e0;
628  if ((ret = parse_subexpr(&e2, p)) < 0) {
629  av_expr_free(e1);
630  return ret;
631  }
632  e0 = make_eval_expr(e_last, 1, e1, e2);
633  if (!e0) {
634  av_expr_free(e1);
635  av_expr_free(e2);
636  return AVERROR(ENOMEM);
637  }
638  };
639 
640  p->stack_index++;
641  *e = e0;
642  return 0;
643 }
644 
645 static int verify_expr(AVExpr *e)
646 {
647  if (!e) return 0;
648  switch (e->type) {
649  case e_value:
650  case e_const: return 1;
651  case e_func0:
652  case e_func1:
653  case e_squish:
654  case e_ld:
655  case e_gauss:
656  case e_isnan:
657  case e_isinf:
658  case e_floor:
659  case e_ceil:
660  case e_trunc:
661  case e_round:
662  case e_sqrt:
663  case e_not:
664  case e_random:
665  case e_sgn:
666  return verify_expr(e->param[0]) && !e->param[1];
667  case e_print:
668  return verify_expr(e->param[0])
669  && (!e->param[1] || verify_expr(e->param[1]));
670  case e_if:
671  case e_ifnot:
672  case e_taylor:
673  return verify_expr(e->param[0]) && verify_expr(e->param[1])
674  && (!e->param[2] || verify_expr(e->param[2]));
675  case e_between:
676  case e_clip:
677  case e_lerp:
678  return verify_expr(e->param[0]) &&
679  verify_expr(e->param[1]) &&
680  verify_expr(e->param[2]);
681  default: return verify_expr(e->param[0]) && verify_expr(e->param[1]) && !e->param[2];
682  }
683 }
684 
685 int av_expr_parse(AVExpr **expr, const char *s,
686  const char * const *const_names,
687  const char * const *func1_names, double (* const *funcs1)(void *, double),
688  const char * const *func2_names, double (* const *funcs2)(void *, double, double),
689  int log_offset, void *log_ctx)
690 {
691  Parser p = { 0 };
692  AVExpr *e = NULL;
693  char *w = av_malloc(strlen(s) + 1);
694  char *wp = w;
695  const char *s0 = s;
696  int ret = 0;
697 
698  if (!w)
699  return AVERROR(ENOMEM);
700 
701  while (*s)
702  if (!av_isspace(*s++)) *wp++ = s[-1];
703  *wp++ = 0;
704 
705  p.class = &eval_class;
706  p.stack_index=100;
707  p.s= w;
708  p.const_names = const_names;
709  p.funcs1 = funcs1;
710  p.func1_names = func1_names;
711  p.funcs2 = funcs2;
712  p.func2_names = func2_names;
713  p.log_offset = log_offset;
714  p.log_ctx = log_ctx;
715 
716  if ((ret = parse_expr(&e, &p)) < 0)
717  goto end;
718  if (*p.s) {
719  av_log(&p, AV_LOG_ERROR, "Invalid chars '%s' at the end of expression '%s'\n", p.s, s0);
720  ret = AVERROR(EINVAL);
721  goto end;
722  }
723  if (!verify_expr(e)) {
724  ret = AVERROR(EINVAL);
725  goto end;
726  }
727  e->var= av_mallocz(sizeof(double) *VARS);
728  if (!e->var) {
729  ret = AVERROR(ENOMEM);
730  goto end;
731  }
732  *expr = e;
733  e = NULL;
734 end:
735  av_expr_free(e);
736  av_free(w);
737  return ret;
738 }
739 
740 static int expr_count(AVExpr *e, unsigned *counter, int size, int type)
741 {
742  int i;
743 
744  if (!e || !counter || !size)
745  return AVERROR(EINVAL);
746 
747  for (i = 0; e->type != type && i < 3 && e->param[i]; i++)
748  expr_count(e->param[i], counter, size, type);
749 
750  if (e->type == type && e->const_index < size)
751  counter[e->const_index]++;
752 
753  return 0;
754 }
755 
756 int av_expr_count_vars(AVExpr *e, unsigned *counter, int size)
757 {
758  return expr_count(e, counter, size, e_const);
759 }
760 
761 int av_expr_count_func(AVExpr *e, unsigned *counter, int size, int arg)
762 {
763  return expr_count(e, counter, size, ((int[]){e_const, e_func1, e_func2})[arg]);
764 }
765 
766 double av_expr_eval(AVExpr *e, const double *const_values, void *opaque)
767 {
768  Parser p = { 0 };
769  p.var= e->var;
770 
771  p.const_values = const_values;
772  p.opaque = opaque;
773  return eval_expr(&p, e);
774 }
775 
776 int av_expr_parse_and_eval(double *d, const char *s,
777  const char * const *const_names, const double *const_values,
778  const char * const *func1_names, double (* const *funcs1)(void *, double),
779  const char * const *func2_names, double (* const *funcs2)(void *, double, double),
780  void *opaque, int log_offset, void *log_ctx)
781 {
782  AVExpr *e = NULL;
783  int ret = av_expr_parse(&e, s, const_names, func1_names, funcs1, func2_names, funcs2, log_offset, log_ctx);
784 
785  if (ret < 0) {
786  *d = NAN;
787  return ret;
788  }
789  *d = av_expr_eval(e, const_values, opaque);
790  av_expr_free(e);
791  return isnan(*d) ? AVERROR(EINVAL) : 0;
792 }
VARS
#define VARS
Definition: eval.c:56
verify_expr
static int verify_expr(AVExpr *e)
Definition: eval.c:645
Parser::func1_names
const char *const * func1_names
Definition: eval.c:50
NULL
#define NULL
Definition: coverity.c:32
isinf
#define isinf(x)
Definition: libm.h:317
func2
static double(*const func2[])(void *, double, double)
Definition: af_afftfilt.c:121
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_expr_count_func
int av_expr_count_func(AVExpr *e, unsigned *counter, int size, int arg)
Track the presence of user provided functions and their number of occurrences in a parsed expression...
Definition: eval.c:761
trunc
static __device__ float trunc(float a)
Definition: cuda_runtime.h:179
av_default_item_name
const char * av_default_item_name(void *ptr)
Return the context name.
Definition: log.c:235
av_isspace
static av_const int av_isspace(int c)
Locale-independent conversion of ASCII isspace.
Definition: avstring.h:227
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
AVExpr::a
union AVExpr::@293 a
FF_ARRAY_ELEMS
#define FF_ARRAY_ELEMS(a)
Definition: sinewin_tablegen.c:29
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:237
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:685
v0
GLfloat v0
Definition: opengl_enc.c:106
ceil
static __device__ float ceil(float a)
Definition: cuda_runtime.h:176
Parser::log_ctx
void * log_ctx
Definition: eval.c:55
attributes.h
Macro definitions for various function/variable attributes.
floor
static __device__ float floor(float a)
Definition: cuda_runtime.h:173
si_prefixes
static const struct @290 si_prefixes['z'- 'E'+1]
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:525
av_malloc
#define av_malloc(s)
Definition: tableprint_vlc.h:31
f
#define f(width, name)
Definition: cbs_vp9.c:255
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:615
Parser
Definition: eval.c:43
value
GLsizei GLboolean const GLfloat * value
Definition: opengl_enc.c:108
AVExpr::type
enum AVExpr::@292 type
AVExpr
Definition: eval.c:157
strtod
double strtod(const char *, char **)
AVExpr::func2
double(* func2)(void *, double, double)
Definition: eval.c:173
av_clip
#define av_clip
Definition: common.h:122
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:518
parse_factor
static int parse_factor(AVExpr **e, Parser *p)
Definition: eval.c:540
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:591
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:776
Parser::const_values
const double * const_values
Definition: eval.c:47
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:194
IS_IDENTIFIER_CHAR
#define IS_IDENTIFIER_CHAR(c)
Definition: eval.c:145
expr_count
static int expr_count(AVExpr *e, unsigned *counter, int size, int type)
Definition: eval.c:740
func1
static double(*const func1[])(void *, double)
Definition: vf_rotate.c:190
fabs
static __device__ float fabs(float a)
Definition: cuda_runtime.h:182
AVExpr::const_index
int const_index
Definition: eval.c:169
M_E
#define M_E
Definition: mathematics.h:37
r
const char * r
Definition: vf_curves.c:116
s0
#define s0
Definition: regdef.h:37
arg
const char * arg
Definition: jacosubdec.c:66
parse_term
static int parse_term(AVExpr **e, Parser *p)
Definition: eval.c:567
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
exp
int8_t exp
Definition: eval.c:72
FFDIFFSIGN
#define FFDIFFSIGN(x, y)
Comparator.
Definition: common.h:101
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
constants
static const struct @291 constants[]
NAN
#define NAN
Definition: mathematics.h:64
w
uint8_t w
Definition: llviddspenc.c:39
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
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:205
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
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:206
ffmath.h
internal math functions header
int
int
Definition: ffmpeg_filter.c:170
common.h
common internal and external API header
av_clipd
#define av_clipd
Definition: common.h:173
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:756
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:766
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:506
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:325
i
int i
Definition: input.c:407
av_unused
#define av_unused
Definition: attributes.h:131
AVExpr::value
double value
Definition: eval.c:168
eval.h
simple arithmetic expression evaluator
name
const char * name
Definition: opengl_enc.c:102
Generated on Sat Feb 27 2021 19:22:35 for FFmpeg by   doxygen 1.8.11