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