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