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