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  } type;
167  double value; // is sign in other types
168  union {
169  int const_index;
170  double (*func0)(double);
171  double (*func1)(void *, double);
172  double (*func2)(void *, double, double);
173  } a;
174  struct AVExpr *param[3];
175  double *var;
176 };
177 
178 static double etime(double v)
179 {
180  return av_gettime() * 0.000001;
181 }
182 
183 static double eval_expr(Parser *p, AVExpr *e)
184 {
185  switch (e->type) {
186  case e_value: return e->value;
187  case e_const: return e->value * p->const_values[e->a.const_index];
188  case e_func0: return e->value * e->a.func0(eval_expr(p, e->param[0]));
189  case e_func1: return e->value * e->a.func1(p->opaque, eval_expr(p, e->param[0]));
190  case e_func2: return e->value * e->a.func2(p->opaque, eval_expr(p, e->param[0]), eval_expr(p, e->param[1]));
191  case e_squish: return 1/(1+exp(4*eval_expr(p, e->param[0])));
192  case e_gauss: { double d = eval_expr(p, e->param[0]); return exp(-d*d/2)/sqrt(2*M_PI); }
193  case e_ld: return e->value * p->var[av_clip(eval_expr(p, e->param[0]), 0, VARS-1)];
194  case e_isnan: return e->value * !!isnan(eval_expr(p, e->param[0]));
195  case e_isinf: return e->value * !!isinf(eval_expr(p, e->param[0]));
196  case e_floor: return e->value * floor(eval_expr(p, e->param[0]));
197  case e_ceil : return e->value * ceil (eval_expr(p, e->param[0]));
198  case e_trunc: return e->value * trunc(eval_expr(p, e->param[0]));
199  case e_round: return e->value * round(eval_expr(p, e->param[0]));
200  case e_sqrt: return e->value * sqrt (eval_expr(p, e->param[0]));
201  case e_not: return e->value * (eval_expr(p, e->param[0]) == 0);
202  case e_if: return e->value * (eval_expr(p, e->param[0]) ? eval_expr(p, e->param[1]) :
203  e->param[2] ? eval_expr(p, e->param[2]) : 0);
204  case e_ifnot: 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_clip: {
207  double x = eval_expr(p, e->param[0]);
208  double min = eval_expr(p, e->param[1]), max = eval_expr(p, e->param[2]);
209  if (isnan(min) || isnan(max) || isnan(x) || min > max)
210  return NAN;
211  return e->value * av_clipd(eval_expr(p, e->param[0]), min, max);
212  }
213  case e_between: {
214  double d = eval_expr(p, e->param[0]);
215  return e->value * (d >= eval_expr(p, e->param[1]) &&
216  d <= eval_expr(p, e->param[2]));
217  }
218  case e_lerp: {
219  double v0 = eval_expr(p, e->param[0]);
220  double v1 = eval_expr(p, e->param[1]);
221  double f = eval_expr(p, e->param[2]);
222  return v0 + (v1 - v0) * f;
223  }
224  case e_print: {
225  double x = eval_expr(p, e->param[0]);
226  int level = e->param[1] ? av_clip(eval_expr(p, e->param[1]), INT_MIN, INT_MAX) : AV_LOG_INFO;
227  av_log(p, level, "%f\n", x);
228  return x;
229  }
230  case e_random:{
231  int idx= av_clip(eval_expr(p, e->param[0]), 0, VARS-1);
232  uint64_t r= isnan(p->var[idx]) ? 0 : p->var[idx];
233  r= r*1664525+1013904223;
234  p->var[idx]= r;
235  return e->value * (r * (1.0/UINT64_MAX));
236  }
237  case e_while: {
238  double d = NAN;
239  while (eval_expr(p, e->param[0]))
240  d=eval_expr(p, e->param[1]);
241  return d;
242  }
243  case e_taylor: {
244  double t = 1, d = 0, v;
245  double x = eval_expr(p, e->param[1]);
246  int id = e->param[2] ? av_clip(eval_expr(p, e->param[2]), 0, VARS-1) : 0;
247  int i;
248  double var0 = p->var[id];
249  for(i=0; i<1000; i++) {
250  double ld = d;
251  p->var[id] = i;
252  v = eval_expr(p, e->param[0]);
253  d += t*v;
254  if(ld==d && v)
255  break;
256  t *= x / (i+1);
257  }
258  p->var[id] = var0;
259  return d;
260  }
261  case e_root: {
262  int i, j;
263  double low = -1, high = -1, v, low_v = -DBL_MAX, high_v = DBL_MAX;
264  double var0 = p->var[0];
265  double x_max = eval_expr(p, e->param[1]);
266  for(i=-1; i<1024; i++) {
267  if(i<255) {
268  p->var[0] = ff_reverse[i&255]*x_max/255;
269  } else {
270  p->var[0] = x_max*pow(0.9, i-255);
271  if (i&1) p->var[0] *= -1;
272  if (i&2) p->var[0] += low;
273  else p->var[0] += high;
274  }
275  v = eval_expr(p, e->param[0]);
276  if (v<=0 && v>low_v) {
277  low = p->var[0];
278  low_v = v;
279  }
280  if (v>=0 && v<high_v) {
281  high = p->var[0];
282  high_v = v;
283  }
284  if (low>=0 && high>=0){
285  for (j=0; j<1000; j++) {
286  p->var[0] = (low+high)*0.5;
287  if (low == p->var[0] || high == p->var[0])
288  break;
289  v = eval_expr(p, e->param[0]);
290  if (v<=0) low = p->var[0];
291  if (v>=0) high= p->var[0];
292  if (isnan(v)) {
293  low = high = v;
294  break;
295  }
296  }
297  break;
298  }
299  }
300  p->var[0] = var0;
301  return -low_v<high_v ? low : high;
302  }
303  default: {
304  double d = eval_expr(p, e->param[0]);
305  double d2 = eval_expr(p, e->param[1]);
306  switch (e->type) {
307  case e_mod: return e->value * (d - floor(d2 ? d / d2 : d * INFINITY) * d2);
308  case e_gcd: return e->value * av_gcd(d,d2);
309  case e_max: return e->value * (d > d2 ? d : d2);
310  case e_min: return e->value * (d < d2 ? d : d2);
311  case e_eq: return e->value * (d == d2 ? 1.0 : 0.0);
312  case e_gt: return e->value * (d > d2 ? 1.0 : 0.0);
313  case e_gte: return e->value * (d >= d2 ? 1.0 : 0.0);
314  case e_lt: return e->value * (d < d2 ? 1.0 : 0.0);
315  case e_lte: return e->value * (d <= d2 ? 1.0 : 0.0);
316  case e_pow: return e->value * pow(d, d2);
317  case e_mul: return e->value * (d * d2);
318  case e_div: return e->value * ((!CONFIG_FTRAPV || d2 ) ? (d / d2) : d * INFINITY);
319  case e_add: return e->value * (d + d2);
320  case e_last:return e->value * d2;
321  case e_st : return e->value * (p->var[av_clip(d, 0, VARS-1)]= d2);
322  case e_hypot:return e->value * hypot(d, d2);
323  case e_atan2:return e->value * atan2(d, d2);
324  case e_bitand: return isnan(d) || isnan(d2) ? NAN : e->value * ((long int)d & (long int)d2);
325  case e_bitor: return isnan(d) || isnan(d2) ? NAN : e->value * ((long int)d | (long int)d2);
326  }
327  }
328  }
329  return NAN;
330 }
331 
332 static int parse_expr(AVExpr **e, Parser *p);
333 
334 void av_expr_free(AVExpr *e)
335 {
336  if (!e) return;
337  av_expr_free(e->param[0]);
338  av_expr_free(e->param[1]);
339  av_expr_free(e->param[2]);
340  av_freep(&e->var);
341  av_freep(&e);
342 }
343 
344 static int parse_primary(AVExpr **e, Parser *p)
345 {
346  AVExpr *d = av_mallocz(sizeof(AVExpr));
347  char *next = p->s, *s0 = p->s;
348  int ret, i;
349 
350  if (!d)
351  return AVERROR(ENOMEM);
352 
353  /* number */
354  d->value = av_strtod(p->s, &next);
355  if (next != p->s) {
356  d->type = e_value;
357  p->s= next;
358  *e = d;
359  return 0;
360  }
361  d->value = 1;
362 
363  /* named constants */
364  for (i=0; p->const_names && p->const_names[i]; i++) {
365  if (strmatch(p->s, p->const_names[i])) {
366  p->s+= strlen(p->const_names[i]);
367  d->type = e_const;
368  d->a.const_index = i;
369  *e = d;
370  return 0;
371  }
372  }
373  for (i = 0; i < FF_ARRAY_ELEMS(constants); i++) {
374  if (strmatch(p->s, constants[i].name)) {
375  p->s += strlen(constants[i].name);
376  d->type = e_value;
377  d->value = constants[i].value;
378  *e = d;
379  return 0;
380  }
381  }
382 
383  p->s= strchr(p->s, '(');
384  if (!p->s) {
385  av_log(p, AV_LOG_ERROR, "Undefined constant or missing '(' in '%s'\n", s0);
386  p->s= next;
387  av_expr_free(d);
388  return AVERROR(EINVAL);
389  }
390  p->s++; // "("
391  if (*next == '(') { // special case do-nothing
392  av_freep(&d);
393  if ((ret = parse_expr(&d, p)) < 0)
394  return ret;
395  if (p->s[0] != ')') {
396  av_log(p, AV_LOG_ERROR, "Missing ')' in '%s'\n", s0);
397  av_expr_free(d);
398  return AVERROR(EINVAL);
399  }
400  p->s++; // ")"
401  *e = d;
402  return 0;
403  }
404  if ((ret = parse_expr(&(d->param[0]), p)) < 0) {
405  av_expr_free(d);
406  return ret;
407  }
408  if (p->s[0]== ',') {
409  p->s++; // ","
410  parse_expr(&d->param[1], p);
411  }
412  if (p->s[0]== ',') {
413  p->s++; // ","
414  parse_expr(&d->param[2], p);
415  }
416  if (p->s[0] != ')') {
417  av_log(p, AV_LOG_ERROR, "Missing ')' or too many args in '%s'\n", s0);
418  av_expr_free(d);
419  return AVERROR(EINVAL);
420  }
421  p->s++; // ")"
422 
423  d->type = e_func0;
424  if (strmatch(next, "sinh" )) d->a.func0 = sinh;
425  else if (strmatch(next, "cosh" )) d->a.func0 = cosh;
426  else if (strmatch(next, "tanh" )) d->a.func0 = tanh;
427  else if (strmatch(next, "sin" )) d->a.func0 = sin;
428  else if (strmatch(next, "cos" )) d->a.func0 = cos;
429  else if (strmatch(next, "tan" )) d->a.func0 = tan;
430  else if (strmatch(next, "atan" )) d->a.func0 = atan;
431  else if (strmatch(next, "asin" )) d->a.func0 = asin;
432  else if (strmatch(next, "acos" )) d->a.func0 = acos;
433  else if (strmatch(next, "exp" )) d->a.func0 = exp;
434  else if (strmatch(next, "log" )) d->a.func0 = log;
435  else if (strmatch(next, "abs" )) d->a.func0 = fabs;
436  else if (strmatch(next, "time" )) d->a.func0 = etime;
437  else if (strmatch(next, "squish")) d->type = e_squish;
438  else if (strmatch(next, "gauss" )) d->type = e_gauss;
439  else if (strmatch(next, "mod" )) d->type = e_mod;
440  else if (strmatch(next, "max" )) d->type = e_max;
441  else if (strmatch(next, "min" )) d->type = e_min;
442  else if (strmatch(next, "eq" )) d->type = e_eq;
443  else if (strmatch(next, "gte" )) d->type = e_gte;
444  else if (strmatch(next, "gt" )) d->type = e_gt;
445  else if (strmatch(next, "lte" )) d->type = e_lte;
446  else if (strmatch(next, "lt" )) d->type = e_lt;
447  else if (strmatch(next, "ld" )) d->type = e_ld;
448  else if (strmatch(next, "isnan" )) d->type = e_isnan;
449  else if (strmatch(next, "isinf" )) d->type = e_isinf;
450  else if (strmatch(next, "st" )) d->type = e_st;
451  else if (strmatch(next, "while" )) d->type = e_while;
452  else if (strmatch(next, "taylor")) d->type = e_taylor;
453  else if (strmatch(next, "root" )) d->type = e_root;
454  else if (strmatch(next, "floor" )) d->type = e_floor;
455  else if (strmatch(next, "ceil" )) d->type = e_ceil;
456  else if (strmatch(next, "trunc" )) d->type = e_trunc;
457  else if (strmatch(next, "round" )) d->type = e_round;
458  else if (strmatch(next, "sqrt" )) d->type = e_sqrt;
459  else if (strmatch(next, "not" )) d->type = e_not;
460  else if (strmatch(next, "pow" )) d->type = e_pow;
461  else if (strmatch(next, "print" )) d->type = e_print;
462  else if (strmatch(next, "random")) d->type = e_random;
463  else if (strmatch(next, "hypot" )) d->type = e_hypot;
464  else if (strmatch(next, "gcd" )) d->type = e_gcd;
465  else if (strmatch(next, "if" )) d->type = e_if;
466  else if (strmatch(next, "ifnot" )) d->type = e_ifnot;
467  else if (strmatch(next, "bitand")) d->type = e_bitand;
468  else if (strmatch(next, "bitor" )) d->type = e_bitor;
469  else if (strmatch(next, "between"))d->type = e_between;
470  else if (strmatch(next, "clip" )) d->type = e_clip;
471  else if (strmatch(next, "atan2" )) d->type = e_atan2;
472  else if (strmatch(next, "lerp" )) d->type = e_lerp;
473  else {
474  for (i=0; p->func1_names && p->func1_names[i]; i++) {
475  if (strmatch(next, p->func1_names[i])) {
476  d->a.func1 = p->funcs1[i];
477  d->type = e_func1;
478  *e = d;
479  return 0;
480  }
481  }
482 
483  for (i=0; p->func2_names && p->func2_names[i]; i++) {
484  if (strmatch(next, p->func2_names[i])) {
485  d->a.func2 = p->funcs2[i];
486  d->type = e_func2;
487  *e = d;
488  return 0;
489  }
490  }
491 
492  av_log(p, AV_LOG_ERROR, "Unknown function in '%s'\n", s0);
493  av_expr_free(d);
494  return AVERROR(EINVAL);
495  }
496 
497  *e = d;
498  return 0;
499 }
500 
501 static AVExpr *make_eval_expr(int type, int value, AVExpr *p0, AVExpr *p1)
502 {
503  AVExpr *e = av_mallocz(sizeof(AVExpr));
504  if (!e)
505  return NULL;
506  e->type =type ;
507  e->value =value ;
508  e->param[0] =p0 ;
509  e->param[1] =p1 ;
510  return e;
511 }
512 
513 static int parse_pow(AVExpr **e, Parser *p, int *sign)
514 {
515  *sign= (*p->s == '+') - (*p->s == '-');
516  p->s += *sign&1;
517  return parse_primary(e, p);
518 }
519 
520 static int parse_dB(AVExpr **e, Parser *p, int *sign)
521 {
522  /* do not filter out the negative sign when parsing a dB value.
523  for example, -3dB is not the same as -(3dB) */
524  if (*p->s == '-') {
525  char *next;
526  double av_unused ignored = strtod(p->s, &next);
527  if (next != p->s && next[0] == 'd' && next[1] == 'B') {
528  *sign = 0;
529  return parse_primary(e, p);
530  }
531  }
532  return parse_pow(e, p, sign);
533 }
534 
535 static int parse_factor(AVExpr **e, Parser *p)
536 {
537  int sign, sign2, ret;
538  AVExpr *e0, *e1, *e2;
539  if ((ret = parse_dB(&e0, p, &sign)) < 0)
540  return ret;
541  while(p->s[0]=='^'){
542  e1 = e0;
543  p->s++;
544  if ((ret = parse_dB(&e2, p, &sign2)) < 0) {
545  av_expr_free(e1);
546  return ret;
547  }
548  e0 = make_eval_expr(e_pow, 1, e1, e2);
549  if (!e0) {
550  av_expr_free(e1);
551  av_expr_free(e2);
552  return AVERROR(ENOMEM);
553  }
554  if (e0->param[1]) e0->param[1]->value *= (sign2|1);
555  }
556  if (e0) e0->value *= (sign|1);
557 
558  *e = e0;
559  return 0;
560 }
561 
562 static int parse_term(AVExpr **e, Parser *p)
563 {
564  int ret;
565  AVExpr *e0, *e1, *e2;
566  if ((ret = parse_factor(&e0, p)) < 0)
567  return ret;
568  while (p->s[0]=='*' || p->s[0]=='/') {
569  int c= *p->s++;
570  e1 = e0;
571  if ((ret = parse_factor(&e2, p)) < 0) {
572  av_expr_free(e1);
573  return ret;
574  }
575  e0 = make_eval_expr(c == '*' ? e_mul : e_div, 1, e1, e2);
576  if (!e0) {
577  av_expr_free(e1);
578  av_expr_free(e2);
579  return AVERROR(ENOMEM);
580  }
581  }
582  *e = e0;
583  return 0;
584 }
585 
586 static int parse_subexpr(AVExpr **e, Parser *p)
587 {
588  int ret;
589  AVExpr *e0, *e1, *e2;
590  if ((ret = parse_term(&e0, p)) < 0)
591  return ret;
592  while (*p->s == '+' || *p->s == '-') {
593  e1 = e0;
594  if ((ret = parse_term(&e2, p)) < 0) {
595  av_expr_free(e1);
596  return ret;
597  }
598  e0 = make_eval_expr(e_add, 1, e1, e2);
599  if (!e0) {
600  av_expr_free(e1);
601  av_expr_free(e2);
602  return AVERROR(ENOMEM);
603  }
604  };
605 
606  *e = e0;
607  return 0;
608 }
609 
610 static int parse_expr(AVExpr **e, Parser *p)
611 {
612  int ret;
613  AVExpr *e0, *e1, *e2;
614  if (p->stack_index <= 0) //protect against stack overflows
615  return AVERROR(EINVAL);
616  p->stack_index--;
617 
618  if ((ret = parse_subexpr(&e0, p)) < 0)
619  return ret;
620  while (*p->s == ';') {
621  p->s++;
622  e1 = e0;
623  if ((ret = parse_subexpr(&e2, p)) < 0) {
624  av_expr_free(e1);
625  return ret;
626  }
627  e0 = make_eval_expr(e_last, 1, e1, e2);
628  if (!e0) {
629  av_expr_free(e1);
630  av_expr_free(e2);
631  return AVERROR(ENOMEM);
632  }
633  };
634 
635  p->stack_index++;
636  *e = e0;
637  return 0;
638 }
639 
640 static int verify_expr(AVExpr *e)
641 {
642  if (!e) return 0;
643  switch (e->type) {
644  case e_value:
645  case e_const: return 1;
646  case e_func0:
647  case e_func1:
648  case e_squish:
649  case e_ld:
650  case e_gauss:
651  case e_isnan:
652  case e_isinf:
653  case e_floor:
654  case e_ceil:
655  case e_trunc:
656  case e_round:
657  case e_sqrt:
658  case e_not:
659  case e_random:
660  return verify_expr(e->param[0]) && !e->param[1];
661  case e_print:
662  return verify_expr(e->param[0])
663  && (!e->param[1] || verify_expr(e->param[1]));
664  case e_if:
665  case e_ifnot:
666  case e_taylor:
667  return verify_expr(e->param[0]) && verify_expr(e->param[1])
668  && (!e->param[2] || verify_expr(e->param[2]));
669  case e_between:
670  case e_clip:
671  case e_lerp:
672  return verify_expr(e->param[0]) &&
673  verify_expr(e->param[1]) &&
674  verify_expr(e->param[2]);
675  default: return verify_expr(e->param[0]) && verify_expr(e->param[1]) && !e->param[2];
676  }
677 }
678 
679 int av_expr_parse(AVExpr **expr, const char *s,
680  const char * const *const_names,
681  const char * const *func1_names, double (* const *funcs1)(void *, double),
682  const char * const *func2_names, double (* const *funcs2)(void *, double, double),
683  int log_offset, void *log_ctx)
684 {
685  Parser p = { 0 };
686  AVExpr *e = NULL;
687  char *w = av_malloc(strlen(s) + 1);
688  char *wp = w;
689  const char *s0 = s;
690  int ret = 0;
691 
692  if (!w)
693  return AVERROR(ENOMEM);
694 
695  while (*s)
696  if (!av_isspace(*s++)) *wp++ = s[-1];
697  *wp++ = 0;
698 
699  p.class = &eval_class;
700  p.stack_index=100;
701  p.s= w;
702  p.const_names = const_names;
703  p.funcs1 = funcs1;
704  p.func1_names = func1_names;
705  p.funcs2 = funcs2;
706  p.func2_names = func2_names;
707  p.log_offset = log_offset;
708  p.log_ctx = log_ctx;
709 
710  if ((ret = parse_expr(&e, &p)) < 0)
711  goto end;
712  if (*p.s) {
713  av_log(&p, AV_LOG_ERROR, "Invalid chars '%s' at the end of expression '%s'\n", p.s, s0);
714  ret = AVERROR(EINVAL);
715  goto end;
716  }
717  if (!verify_expr(e)) {
718  ret = AVERROR(EINVAL);
719  goto end;
720  }
721  e->var= av_mallocz(sizeof(double) *VARS);
722  if (!e->var) {
723  ret = AVERROR(ENOMEM);
724  goto end;
725  }
726  *expr = e;
727  e = NULL;
728 end:
729  av_expr_free(e);
730  av_free(w);
731  return ret;
732 }
733 
734 double av_expr_eval(AVExpr *e, const double *const_values, void *opaque)
735 {
736  Parser p = { 0 };
737  p.var= e->var;
738 
739  p.const_values = const_values;
740  p.opaque = opaque;
741  return eval_expr(&p, e);
742 }
743 
744 int av_expr_parse_and_eval(double *d, const char *s,
745  const char * const *const_names, const double *const_values,
746  const char * const *func1_names, double (* const *funcs1)(void *, double),
747  const char * const *func2_names, double (* const *funcs2)(void *, double, double),
748  void *opaque, int log_offset, void *log_ctx)
749 {
750  AVExpr *e = NULL;
751  int ret = av_expr_parse(&e, s, const_names, func1_names, funcs1, func2_names, funcs2, log_offset, log_ctx);
752 
753  if (ret < 0) {
754  *d = NAN;
755  return ret;
756  }
757  *d = av_expr_eval(e, const_values, opaque);
758  av_expr_free(e);
759  return isnan(*d) ? AVERROR(EINVAL) : 0;
760 }
AVExpr::e_root
@ e_root
Definition: eval.c:163
AVExpr::e_lt
@ e_lt
Definition: eval.c:161
ff_exp10
static av_always_inline double ff_exp10(double x)
Compute 10^x for floating point values.
Definition: ffmath.h:42
level
uint8_t level
Definition: svq3.c:207
INFINITY
#define INFINITY
Definition: mathematics.h:67
r
const char * r
Definition: vf_curves.c:114
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
M_PHI
#define M_PHI
Definition: mathematics.h:49
parse_primary
static int parse_primary(AVExpr **e, Parser *p)
Definition: eval.c:344
AVExpr::e_eq
@ e_eq
Definition: eval.c:161
strtod
double strtod(const char *, char **)
AVExpr::e_isinf
@ e_isinf
Definition: eval.c:160
AVExpr::e_gt
@ e_gt
Definition: eval.c:161
AVExpr::e_round
@ e_round
Definition: eval.c:163
av_unused
#define av_unused
Definition: attributes.h:125
av_isspace
static av_const int av_isspace(int c)
Locale-independent conversion of ASCII isspace.
Definition: avstring.h:222
end
static av_cold int end(AVCodecContext *avctx)
Definition: avrndec.c:90
AVExpr::e_pow
@ e_pow
Definition: eval.c:162
w
uint8_t w
Definition: llviddspenc.c:38
dec_val
double dec_val
Definition: eval.c:71
b
#define b
Definition: input.c:41
ff_reverse
const uint8_t ff_reverse[256]
Definition: reverse.c:23
float.h
reverse.h
max
#define max(a, b)
Definition: cuda_runtime.h:33
mathematics.h
AVExpr::e_ceil
@ e_ceil
Definition: eval.c:163
Parser::const_names
const char *const * const_names
Definition: eval.c:48
IS_IDENTIFIER_CHAR
#define IS_IDENTIFIER_CHAR(c)
Definition: eval.c:145
AVExpr::e_trunc
@ e_trunc
Definition: eval.c:163
Parser::funcs2
double(*const funcs2)(void *, double a, double b)
Definition: eval.c:51
AVExpr::e_lte
@ e_lte
Definition: eval.c:161
AVExpr::e_bitor
@ e_bitor
Definition: eval.c:165
func2_names
static const char *const func2_names[]
Definition: af_afftfilt.c:119
const_values
static const double const_values[]
Definition: eval.c:28
value
double value
Definition: eval.c:98
av_malloc
#define av_malloc(s)
Definition: tableprint_vlc.h:31
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
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:679
v0
#define v0
Definition: regdef.h:26
Parser::func1_names
const char *const * func1_names
Definition: eval.c:50
AVExpr::e_value
@ e_value
Definition: eval.c:159
AVExpr::func0
double(* func0)(double)
Definition: eval.c:170
type
it s the only field you need to keep assuming you have a context There is some magic you don t need to care about around this just let it vf type
Definition: writing_filters.txt:86
func1_names
static const char *const func1_names[]
Definition: vf_rotate.c:195
av_expr_free
void av_expr_free(AVExpr *e)
Free a parsed expression previously created with av_expr_parse().
Definition: eval.c:334
AVExpr::e_ld
@ e_ld
Definition: eval.c:160
Parser::funcs1
double(*const funcs1)(void *, double a)
Definition: eval.c:49
AVExpr::e_div
@ e_div
Definition: eval.c:162
AV_LOG_ERROR
#define AV_LOG_ERROR
Something went wrong and cannot losslessly be recovered.
Definition: log.h:176
funcs1
static double(*const funcs1[])(void *, double)
Definition: vf_lut.c:200
AVExpr::e_bitand
@ e_bitand
Definition: eval.c:165
Parser::log_ctx
void * log_ctx
Definition: eval.c:55
s
#define s(width, name)
Definition: cbs_vp9.c:257
AVExpr::e_random
@ e_random
Definition: eval.c:164
AVExpr::e_if
@ e_if
Definition: eval.c:165
M_E
#define M_E
Definition: mathematics.h:37
AVExpr::e_lerp
@ e_lerp
Definition: eval.c:165
AVExpr::func1
double(* func1)(void *, double)
Definition: eval.c:171
av_expr_eval
double av_expr_eval(AVExpr *e, const double *const_values, void *opaque)
Evaluate a previously parsed expression.
Definition: eval.c:734
AVExpr
Definition: eval.c:157
eval_class
static const AVClass eval_class
Definition: eval.c:60
NAN
#define NAN
Definition: mathematics.h:64
f
#define f(width, name)
Definition: cbs_vp9.c:255
Parser::log_offset
int log_offset
Definition: eval.c:54
name
const char * name
Definition: eval.c:97
LIBAVUTIL_VERSION_INT
#define LIBAVUTIL_VERSION_INT
Definition: version.h:85
AVClass
Describe the class of an AVClass context structure.
Definition: log.h:67
NULL
#define NULL
Definition: coverity.c:32
AVExpr::e_func2
@ e_func2
Definition: eval.c:159
isnan
#define isnan(x)
Definition: libm.h:340
parse_pow
static int parse_pow(AVExpr **e, Parser *p, int *sign)
Definition: eval.c:513
AVExpr::e_max
@ e_max
Definition: eval.c:161
av_default_item_name
const char * av_default_item_name(void *ptr)
Return the context name.
Definition: log.c:191
AVExpr::e_st
@ e_st
Definition: eval.c:163
timer.h
AVExpr::e_isnan
@ e_isnan
Definition: eval.c:160
isinf
#define isinf(x)
Definition: libm.h:317
time.h
AVExpr::const_index
int const_index
Definition: eval.c:169
exp
int8_t exp
Definition: eval.c:72
parse_dB
static int parse_dB(AVExpr **e, Parser *p, int *sign)
Definition: eval.c:520
AVExpr::e_atan2
@ e_atan2
Definition: eval.c:165
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
trunc
static av_always_inline av_const double trunc(double x)
Definition: libm.h:458
AVExpr::e_gauss
@ e_gauss
Definition: eval.c:160
AVExpr::e_mod
@ e_mod
Definition: eval.c:161
AVExpr::var
double * var
Definition: eval.c:175
eval.h
Parser::stack_index
int stack_index
Definition: eval.c:45
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:744
id
enum AVCodecID id
Definition: extract_extradata_bsf.c:329
eval_expr
static double eval_expr(Parser *p, AVExpr *e)
Definition: eval.c:183
hypot
static av_const double hypot(double x, double y)
Definition: libm.h:366
AVExpr::param
struct AVExpr * param[3]
Definition: eval.c:174
AVExpr::e_mul
@ e_mul
Definition: eval.c:162
AVExpr::e_while
@ e_while
Definition: eval.c:163
verify_expr
static int verify_expr(AVExpr *e)
Definition: eval.c:640
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:41
Parser
Definition: eval.c:43
attributes.h
AVExpr::e_print
@ e_print
Definition: eval.c:165
parse_subexpr
static int parse_subexpr(AVExpr **e, Parser *p)
Definition: eval.c:586
M_PI
#define M_PI
Definition: mathematics.h:52
make_eval_expr
static AVExpr * make_eval_expr(int type, int value, AVExpr *p0, AVExpr *p1)
Definition: eval.c:501
AV_LOG_INFO
#define AV_LOG_INFO
Standard information.
Definition: log.h:187
AVExpr::a
union AVExpr::@288 a
AVExpr::e_floor
@ e_floor
Definition: eval.c:163
AVExpr::e_last
@ e_last
Definition: eval.c:163
Parser::s
char * s
Definition: eval.c:46
log.h
i
#define i(width, name, range_min, range_max)
Definition: cbs_h2645.c:259
etime
static double etime(double v)
Definition: eval.c:178
round
static av_always_inline av_const double round(double x)
Definition: libm.h:444
AVExpr::value
double value
Definition: eval.c:167
internal.h
common.h
parse_factor
static int parse_factor(AVExpr **e, Parser *p)
Definition: eval.c:535
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
AVExpr::e_squish
@ e_squish
Definition: eval.c:160
VARS
#define VARS
Definition: eval.c:56
ret
ret
Definition: filter_design.txt:187
AVExpr::e_add
@ e_add
Definition: eval.c:162
AVExpr::e_func0
@ e_func0
Definition: eval.c:159
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
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
AVExpr::e_not
@ e_not
Definition: eval.c:164
const_names
static const char *const const_names[]
Definition: eval.c:34
bin_val
double bin_val
Definition: eval.c:70
AVExpr::type
enum AVExpr::@287 type
FF_ARRAY_ELEMS
#define FF_ARRAY_ELEMS(a)
Definition: sinewin_tablegen_template.c:38
AVExpr::e_min
@ e_min
Definition: eval.c:161
Parser::opaque
void * opaque
Definition: eval.c:53
AVExpr::e_gcd
@ e_gcd
Definition: eval.c:164
Parser::func2_names
const char *const * func2_names
Definition: eval.c:52
si_prefixes
static const struct @285 si_prefixes[ 'z' - 'E'+1]
Parser::class
const AVClass * class
Definition: eval.c:44
ffmath.h
av_gettime
int64_t av_gettime(void)
Get the current time in microseconds.
Definition: time.c:39
avutil.h
Parser::var
double * var
Definition: eval.c:57
s0
#define s0
Definition: regdef.h:37
constants
static const struct @286 constants[]
av_free
#define av_free(p)
Definition: tableprint_vlc.h:34
AVExpr::e_hypot
@ e_hypot
Definition: eval.c:164
av_freep
#define av_freep(p)
Definition: tableprint_vlc.h:35
AVExpr::e_taylor
@ e_taylor
Definition: eval.c:163
av_log
#define av_log(a,...)
Definition: tableprint_vlc.h:28
strmatch
static int strmatch(const char *s, const char *prefix)
Definition: eval.c:147
parse_term
static int parse_term(AVExpr **e, Parser *p)
Definition: eval.c:562
AVExpr::e_const
@ e_const
Definition: eval.c:159
AVExpr::e_ifnot
@ e_ifnot
Definition: eval.c:165
AVExpr::e_gte
@ e_gte
Definition: eval.c:161
avstring.h
FF_QP2LAMBDA
#define FF_QP2LAMBDA
factor to convert from H.263 QP to lambda
Definition: avutil.h:227
AVExpr::e_func1
@ e_func1
Definition: eval.c:159
int
int
Definition: ffmpeg_filter.c:191
parse_expr
static int parse_expr(AVExpr **e, Parser *p)
Definition: eval.c:610
AVExpr::e_sqrt
@ e_sqrt
Definition: eval.c:164
AVExpr::e_between
@ e_between
Definition: eval.c:165
Parser::const_values
const double * const_values
Definition: eval.c:47
AVExpr::e_clip
@ e_clip
Definition: eval.c:165
min
float min
Definition: vorbis_enc_data.h:456
AVExpr::func2
double(* func2)(void *, double, double)
Definition: eval.c:172
Generated on Wed Aug 24 2022 21:27:27 for FFmpeg by   doxygen 1.8.17