Mercurial > libavutil.hg
comparison eval.c @ 932:be49bac1a894 libavutil
Move eval.c and eval.h from libavcodec to libavutil, and make the eval
API public.
author | stefano |
---|---|
date | Sat, 05 Jun 2010 12:01:28 +0000 |
parents | |
children | 4059de4c9f90 |
comparison
equal
deleted
inserted
replaced
931:239e2d9c478a | 932:be49bac1a894 |
---|---|
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 "libavutil/avutil.h" | |
30 #include "eval.h" | |
31 | |
32 typedef struct Parser { | |
33 const AVClass *class; | |
34 int stack_index; | |
35 char *s; | |
36 const double *const_values; | |
37 const char * const *const_names; // NULL terminated | |
38 double (* const *funcs1)(void *, double a); // NULL terminated | |
39 const char * const *func1_names; // NULL terminated | |
40 double (* const *funcs2)(void *, double a, double b); // NULL terminated | |
41 const char * const *func2_names; // NULL terminated | |
42 void *opaque; | |
43 int log_offset; | |
44 void *log_ctx; | |
45 #define VARS 10 | |
46 double var[VARS]; | |
47 } Parser; | |
48 | |
49 static const AVClass class = { "Eval", av_default_item_name, NULL, LIBAVUTIL_VERSION_INT, offsetof(Parser,log_offset), offsetof(Parser,log_ctx) }; | |
50 | |
51 static const int8_t si_prefixes['z' - 'E' + 1] = { | |
52 ['y'-'E']= -24, | |
53 ['z'-'E']= -21, | |
54 ['a'-'E']= -18, | |
55 ['f'-'E']= -15, | |
56 ['p'-'E']= -12, | |
57 ['n'-'E']= - 9, | |
58 ['u'-'E']= - 6, | |
59 ['m'-'E']= - 3, | |
60 ['c'-'E']= - 2, | |
61 ['d'-'E']= - 1, | |
62 ['h'-'E']= 2, | |
63 ['k'-'E']= 3, | |
64 ['K'-'E']= 3, | |
65 ['M'-'E']= 6, | |
66 ['G'-'E']= 9, | |
67 ['T'-'E']= 12, | |
68 ['P'-'E']= 15, | |
69 ['E'-'E']= 18, | |
70 ['Z'-'E']= 21, | |
71 ['Y'-'E']= 24, | |
72 }; | |
73 | |
74 double av_strtod(const char *numstr, char **tail) | |
75 { | |
76 double d; | |
77 char *next; | |
78 d = strtod(numstr, &next); | |
79 /* if parsing succeeded, check for and interpret postfixes */ | |
80 if (next!=numstr) { | |
81 if (*next >= 'E' && *next <= 'z') { | |
82 int e= si_prefixes[*next - 'E']; | |
83 if (e) { | |
84 if (next[1] == 'i') { | |
85 d*= pow( 2, e/0.3); | |
86 next+=2; | |
87 } else { | |
88 d*= pow(10, e); | |
89 next++; | |
90 } | |
91 } | |
92 } | |
93 | |
94 if (*next=='B') { | |
95 d*=8; | |
96 next++; | |
97 } | |
98 } | |
99 /* if requested, fill in tail with the position after the last parsed | |
100 character */ | |
101 if (tail) | |
102 *tail = next; | |
103 return d; | |
104 } | |
105 | |
106 static int strmatch(const char *s, const char *prefix) | |
107 { | |
108 int i; | |
109 for (i=0; prefix[i]; i++) { | |
110 if (prefix[i] != s[i]) return 0; | |
111 } | |
112 return 1; | |
113 } | |
114 | |
115 struct AVExpr { | |
116 enum { | |
117 e_value, e_const, e_func0, e_func1, e_func2, | |
118 e_squish, e_gauss, e_ld, | |
119 e_mod, e_max, e_min, e_eq, e_gt, e_gte, | |
120 e_pow, e_mul, e_div, e_add, | |
121 e_last, e_st, e_while, | |
122 } type; | |
123 double value; // is sign in other types | |
124 union { | |
125 int const_index; | |
126 double (*func0)(double); | |
127 double (*func1)(void *, double); | |
128 double (*func2)(void *, double, double); | |
129 } a; | |
130 struct AVExpr *param[2]; | |
131 }; | |
132 | |
133 static double eval_expr(Parser *p, AVExpr *e) | |
134 { | |
135 switch (e->type) { | |
136 case e_value: return e->value; | |
137 case e_const: return e->value * p->const_values[e->a.const_index]; | |
138 case e_func0: return e->value * e->a.func0(eval_expr(p, e->param[0])); | |
139 case e_func1: return e->value * e->a.func1(p->opaque, eval_expr(p, e->param[0])); | |
140 case e_func2: return e->value * e->a.func2(p->opaque, eval_expr(p, e->param[0]), eval_expr(p, e->param[1])); | |
141 case e_squish: return 1/(1+exp(4*eval_expr(p, e->param[0]))); | |
142 case e_gauss: { double d = eval_expr(p, e->param[0]); return exp(-d*d/2)/sqrt(2*M_PI); } | |
143 case e_ld: return e->value * p->var[av_clip(eval_expr(p, e->param[0]), 0, VARS-1)]; | |
144 case e_while: { | |
145 double d = NAN; | |
146 while (eval_expr(p, e->param[0])) | |
147 d=eval_expr(p, e->param[1]); | |
148 return d; | |
149 } | |
150 default: { | |
151 double d = eval_expr(p, e->param[0]); | |
152 double d2 = eval_expr(p, e->param[1]); | |
153 switch (e->type) { | |
154 case e_mod: return e->value * (d - floor(d/d2)*d2); | |
155 case e_max: return e->value * (d > d2 ? d : d2); | |
156 case e_min: return e->value * (d < d2 ? d : d2); | |
157 case e_eq: return e->value * (d == d2 ? 1.0 : 0.0); | |
158 case e_gt: return e->value * (d > d2 ? 1.0 : 0.0); | |
159 case e_gte: return e->value * (d >= d2 ? 1.0 : 0.0); | |
160 case e_pow: return e->value * pow(d, d2); | |
161 case e_mul: return e->value * (d * d2); | |
162 case e_div: return e->value * (d / d2); | |
163 case e_add: return e->value * (d + d2); | |
164 case e_last:return e->value * d2; | |
165 case e_st : return e->value * (p->var[av_clip(d, 0, VARS-1)]= d2); | |
166 } | |
167 } | |
168 } | |
169 return NAN; | |
170 } | |
171 | |
172 static int parse_expr(AVExpr **e, Parser *p); | |
173 | |
174 void av_free_expr(AVExpr *e) | |
175 { | |
176 if (!e) return; | |
177 av_free_expr(e->param[0]); | |
178 av_free_expr(e->param[1]); | |
179 av_freep(&e); | |
180 } | |
181 | |
182 static int parse_primary(AVExpr **e, Parser *p) | |
183 { | |
184 AVExpr *d = av_mallocz(sizeof(AVExpr)); | |
185 char *next= p->s; | |
186 int ret, i; | |
187 | |
188 if (!d) | |
189 return AVERROR(ENOMEM); | |
190 | |
191 /* number */ | |
192 d->value = av_strtod(p->s, &next); | |
193 if (next != p->s) { | |
194 d->type = e_value; | |
195 p->s= next; | |
196 *e = d; | |
197 return 0; | |
198 } | |
199 d->value = 1; | |
200 | |
201 /* named constants */ | |
202 for (i=0; p->const_names && p->const_names[i]; i++) { | |
203 if (strmatch(p->s, p->const_names[i])) { | |
204 p->s+= strlen(p->const_names[i]); | |
205 d->type = e_const; | |
206 d->a.const_index = i; | |
207 *e = d; | |
208 return 0; | |
209 } | |
210 } | |
211 | |
212 p->s= strchr(p->s, '('); | |
213 if (p->s==NULL) { | |
214 av_log(p, AV_LOG_ERROR, "undefined constant or missing (\n"); | |
215 p->s= next; | |
216 av_free_expr(d); | |
217 return AVERROR(EINVAL); | |
218 } | |
219 p->s++; // "(" | |
220 if (*next == '(') { // special case do-nothing | |
221 av_freep(&d); | |
222 if ((ret = parse_expr(&d, p)) < 0) | |
223 return ret; | |
224 if (p->s[0] != ')') { | |
225 av_log(p, AV_LOG_ERROR, "missing )\n"); | |
226 av_free_expr(d); | |
227 return AVERROR(EINVAL); | |
228 } | |
229 p->s++; // ")" | |
230 *e = d; | |
231 return 0; | |
232 } | |
233 if ((ret = parse_expr(&(d->param[0]), p)) < 0) { | |
234 av_free_expr(d); | |
235 return ret; | |
236 } | |
237 if (p->s[0]== ',') { | |
238 p->s++; // "," | |
239 parse_expr(&d->param[1], p); | |
240 } | |
241 if (p->s[0] != ')') { | |
242 av_log(p, AV_LOG_ERROR, "missing )\n"); | |
243 av_free_expr(d); | |
244 return AVERROR(EINVAL); | |
245 } | |
246 p->s++; // ")" | |
247 | |
248 d->type = e_func0; | |
249 if (strmatch(next, "sinh" )) d->a.func0 = sinh; | |
250 else if (strmatch(next, "cosh" )) d->a.func0 = cosh; | |
251 else if (strmatch(next, "tanh" )) d->a.func0 = tanh; | |
252 else if (strmatch(next, "sin" )) d->a.func0 = sin; | |
253 else if (strmatch(next, "cos" )) d->a.func0 = cos; | |
254 else if (strmatch(next, "tan" )) d->a.func0 = tan; | |
255 else if (strmatch(next, "atan" )) d->a.func0 = atan; | |
256 else if (strmatch(next, "asin" )) d->a.func0 = asin; | |
257 else if (strmatch(next, "acos" )) d->a.func0 = acos; | |
258 else if (strmatch(next, "exp" )) d->a.func0 = exp; | |
259 else if (strmatch(next, "log" )) d->a.func0 = log; | |
260 else if (strmatch(next, "abs" )) d->a.func0 = fabs; | |
261 else if (strmatch(next, "squish")) d->type = e_squish; | |
262 else if (strmatch(next, "gauss" )) d->type = e_gauss; | |
263 else if (strmatch(next, "mod" )) d->type = e_mod; | |
264 else if (strmatch(next, "max" )) d->type = e_max; | |
265 else if (strmatch(next, "min" )) d->type = e_min; | |
266 else if (strmatch(next, "eq" )) d->type = e_eq; | |
267 else if (strmatch(next, "gte" )) d->type = e_gte; | |
268 else if (strmatch(next, "gt" )) d->type = e_gt; | |
269 else if (strmatch(next, "lte" )) { AVExpr *tmp = d->param[1]; d->param[1] = d->param[0]; d->param[0] = tmp; d->type = e_gt; } | |
270 else if (strmatch(next, "lt" )) { AVExpr *tmp = d->param[1]; d->param[1] = d->param[0]; d->param[0] = tmp; d->type = e_gte; } | |
271 else if (strmatch(next, "ld" )) d->type = e_ld; | |
272 else if (strmatch(next, "st" )) d->type = e_st; | |
273 else if (strmatch(next, "while" )) d->type = e_while; | |
274 else { | |
275 for (i=0; p->func1_names && p->func1_names[i]; i++) { | |
276 if (strmatch(next, p->func1_names[i])) { | |
277 d->a.func1 = p->funcs1[i]; | |
278 d->type = e_func1; | |
279 *e = d; | |
280 return 0; | |
281 } | |
282 } | |
283 | |
284 for (i=0; p->func2_names && p->func2_names[i]; i++) { | |
285 if (strmatch(next, p->func2_names[i])) { | |
286 d->a.func2 = p->funcs2[i]; | |
287 d->type = e_func2; | |
288 *e = d; | |
289 return 0; | |
290 } | |
291 } | |
292 | |
293 av_log(p, AV_LOG_ERROR, "unknown function\n"); | |
294 av_free_expr(d); | |
295 return AVERROR(EINVAL); | |
296 } | |
297 | |
298 *e = d; | |
299 return 0; | |
300 } | |
301 | |
302 static AVExpr *new_eval_expr(int type, int value, AVExpr *p0, AVExpr *p1) | |
303 { | |
304 AVExpr *e = av_mallocz(sizeof(AVExpr)); | |
305 if (!e) | |
306 return NULL; | |
307 e->type =type ; | |
308 e->value =value ; | |
309 e->param[0] =p0 ; | |
310 e->param[1] =p1 ; | |
311 return e; | |
312 } | |
313 | |
314 static int parse_pow(AVExpr **e, Parser *p, int *sign) | |
315 { | |
316 *sign= (*p->s == '+') - (*p->s == '-'); | |
317 p->s += *sign&1; | |
318 return parse_primary(e, p); | |
319 } | |
320 | |
321 static int parse_factor(AVExpr **e, Parser *p) | |
322 { | |
323 int sign, sign2, ret; | |
324 AVExpr *e0, *e1, *e2; | |
325 if ((ret = parse_pow(&e0, p, &sign)) < 0) | |
326 return ret; | |
327 while(p->s[0]=='^'){ | |
328 e1 = e0; | |
329 p->s++; | |
330 if ((ret = parse_pow(&e2, p, &sign2)) < 0) { | |
331 av_free_expr(e1); | |
332 return ret; | |
333 } | |
334 e0 = new_eval_expr(e_pow, 1, e1, e2); | |
335 if (!e0) { | |
336 av_free_expr(e1); | |
337 av_free_expr(e2); | |
338 return AVERROR(ENOMEM); | |
339 } | |
340 if (e0->param[1]) e0->param[1]->value *= (sign2|1); | |
341 } | |
342 if (e0) e0->value *= (sign|1); | |
343 | |
344 *e = e0; | |
345 return 0; | |
346 } | |
347 | |
348 static int parse_term(AVExpr **e, Parser *p) | |
349 { | |
350 int ret; | |
351 AVExpr *e0, *e1, *e2; | |
352 if ((ret = parse_factor(&e0, p)) < 0) | |
353 return ret; | |
354 while (p->s[0]=='*' || p->s[0]=='/') { | |
355 int c= *p->s++; | |
356 e1 = e0; | |
357 if ((ret = parse_factor(&e2, p)) < 0) { | |
358 av_free_expr(e1); | |
359 return ret; | |
360 } | |
361 e0 = new_eval_expr(c == '*' ? e_mul : e_div, 1, e1, e2); | |
362 if (!e0) { | |
363 av_free_expr(e1); | |
364 av_free_expr(e2); | |
365 return AVERROR(ENOMEM); | |
366 } | |
367 } | |
368 *e = e0; | |
369 return 0; | |
370 } | |
371 | |
372 static int parse_subexpr(AVExpr **e, Parser *p) | |
373 { | |
374 int ret; | |
375 AVExpr *e0, *e1, *e2; | |
376 if ((ret = parse_term(&e0, p)) < 0) | |
377 return ret; | |
378 while (*p->s == '+' || *p->s == '-') { | |
379 e1 = e0; | |
380 if ((ret = parse_term(&e2, p)) < 0) { | |
381 av_free_expr(e1); | |
382 return ret; | |
383 } | |
384 e0 = new_eval_expr(e_add, 1, e1, e2); | |
385 if (!e0) { | |
386 av_free_expr(e1); | |
387 av_free_expr(e2); | |
388 return AVERROR(ENOMEM); | |
389 } | |
390 }; | |
391 | |
392 *e = e0; | |
393 return 0; | |
394 } | |
395 | |
396 static int parse_expr(AVExpr **e, Parser *p) | |
397 { | |
398 int ret; | |
399 AVExpr *e0, *e1, *e2; | |
400 if (p->stack_index <= 0) //protect against stack overflows | |
401 return AVERROR(EINVAL); | |
402 p->stack_index--; | |
403 | |
404 if ((ret = parse_subexpr(&e0, p)) < 0) | |
405 return ret; | |
406 while (*p->s == ';') { | |
407 e1 = e0; | |
408 if ((ret = parse_subexpr(&e2, p)) < 0) { | |
409 av_free_expr(e1); | |
410 return ret; | |
411 } | |
412 p->s++; | |
413 e0 = new_eval_expr(e_last, 1, e1, e2); | |
414 if (!e0) { | |
415 av_free_expr(e1); | |
416 av_free_expr(e2); | |
417 return AVERROR(ENOMEM); | |
418 } | |
419 }; | |
420 | |
421 p->stack_index++; | |
422 *e = e0; | |
423 return 0; | |
424 } | |
425 | |
426 static int verify_expr(AVExpr *e) | |
427 { | |
428 if (!e) return 0; | |
429 switch (e->type) { | |
430 case e_value: | |
431 case e_const: return 1; | |
432 case e_func0: | |
433 case e_func1: | |
434 case e_squish: | |
435 case e_ld: | |
436 case e_gauss: return verify_expr(e->param[0]); | |
437 default: return verify_expr(e->param[0]) && verify_expr(e->param[1]); | |
438 } | |
439 } | |
440 | |
441 int av_parse_expr(AVExpr **expr, const char *s, | |
442 const char * const *const_names, | |
443 const char * const *func1_names, double (* const *funcs1)(void *, double), | |
444 const char * const *func2_names, double (* const *funcs2)(void *, double, double), | |
445 int log_offset, void *log_ctx) | |
446 { | |
447 Parser p; | |
448 AVExpr *e = NULL; | |
449 char *w = av_malloc(strlen(s) + 1); | |
450 char *wp = w; | |
451 int ret = 0; | |
452 | |
453 if (!w) | |
454 return AVERROR(ENOMEM); | |
455 | |
456 while (*s) | |
457 if (!isspace(*s++)) *wp++ = s[-1]; | |
458 *wp++ = 0; | |
459 | |
460 p.class = &class; | |
461 p.stack_index=100; | |
462 p.s= w; | |
463 p.const_names = const_names; | |
464 p.funcs1 = funcs1; | |
465 p.func1_names = func1_names; | |
466 p.funcs2 = funcs2; | |
467 p.func2_names = func2_names; | |
468 p.log_offset = log_offset; | |
469 p.log_ctx = log_ctx; | |
470 | |
471 if ((ret = parse_expr(&e, &p)) < 0) | |
472 goto end; | |
473 if (!verify_expr(e)) { | |
474 av_free_expr(e); | |
475 ret = AVERROR(EINVAL); | |
476 goto end; | |
477 } | |
478 *expr = e; | |
479 end: | |
480 av_free(w); | |
481 return ret; | |
482 } | |
483 | |
484 double av_eval_expr(AVExpr *e, const double *const_values, void *opaque) | |
485 { | |
486 Parser p; | |
487 | |
488 p.const_values = const_values; | |
489 p.opaque = opaque; | |
490 return eval_expr(&p, e); | |
491 } | |
492 | |
493 int av_parse_and_eval_expr(double *d, const char *s, | |
494 const char * const *const_names, const double *const_values, | |
495 const char * const *func1_names, double (* const *funcs1)(void *, double), | |
496 const char * const *func2_names, double (* const *funcs2)(void *, double, double), | |
497 void *opaque, int log_offset, void *log_ctx) | |
498 { | |
499 AVExpr *e = NULL; | |
500 int ret = av_parse_expr(&e, s, const_names, func1_names, funcs1, func2_names, funcs2, log_offset, log_ctx); | |
501 | |
502 if (ret < 0) { | |
503 *d = NAN; | |
504 return ret; | |
505 } | |
506 *d = av_eval_expr(e, const_values, opaque); | |
507 av_free_expr(e); | |
508 return isnan(*d) ? AVERROR(EINVAL) : 0; | |
509 } | |
510 | |
511 #ifdef TEST | |
512 #undef printf | |
513 static double const_values[] = { | |
514 M_PI, | |
515 M_E, | |
516 0 | |
517 }; | |
518 | |
519 static const char *const_names[] = { | |
520 "PI", | |
521 "E", | |
522 0 | |
523 }; | |
524 | |
525 int main(void) | |
526 { | |
527 int i; | |
528 double d; | |
529 av_parse_and_eval_expr(&d, "1+(5-2)^(3-1)+1/2+sin(PI)-max(-2.2,-3.1)", | |
530 const_names, const_values, | |
531 NULL, NULL, NULL, NULL, NULL, 0, NULL); | |
532 printf("%f == 12.7\n", d); | |
533 av_parse_and_eval_expr(&d, "80G/80Gi", | |
534 const_names, const_values, | |
535 NULL, NULL, NULL, NULL, NULL, 0, NULL); | |
536 printf("%f == 0.931322575\n", d); | |
537 | |
538 for (i=0; i<1050; i++) { | |
539 START_TIMER | |
540 av_parse_and_eval_expr(&d, "1+(5-2)^(3-1)+1/2+sin(PI)-max(-2.2,-3.1)", | |
541 const_names, const_values, | |
542 NULL, NULL, NULL, NULL, NULL, 0, NULL); | |
543 STOP_TIMER("av_parse_and_eval_expr") | |
544 } | |
545 return 0; | |
546 } | |
547 #endif |