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