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