Libav
|
00001 /* 00002 * Copyright (c) 2002-2006 Michael Niedermayer <michaelni@gmx.at> 00003 * Copyright (c) 2006 Oded Shimon <ods15@ods15.dyndns.org> 00004 * 00005 * This file is part of FFmpeg. 00006 * 00007 * FFmpeg is free software; you can redistribute it and/or 00008 * modify it under the terms of the GNU Lesser General Public 00009 * License as published by the Free Software Foundation; either 00010 * version 2.1 of the License, or (at your option) any later version. 00011 * 00012 * FFmpeg is distributed in the hope that it will be useful, 00013 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00015 * Lesser General Public License for more details. 00016 * 00017 * You should have received a copy of the GNU Lesser General Public 00018 * License along with FFmpeg; if not, write to the Free Software 00019 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 00020 */ 00021 00029 #include "libavutil/avutil.h" 00030 #include "eval.h" 00031 00032 typedef struct Parser{ 00033 int stack_index; 00034 char *s; 00035 const double *const_value; 00036 const char * const *const_name; // NULL terminated 00037 double (* const *func1)(void *, double a); // NULL terminated 00038 const char * const *func1_name; // NULL terminated 00039 double (* const *func2)(void *, double a, double b); // NULL terminated 00040 const char * const *func2_name; // NULL terminated 00041 void *opaque; 00042 const char **error; 00043 #define VARS 10 00044 double var[VARS]; 00045 } Parser; 00046 00047 static const int8_t si_prefixes['z' - 'E' + 1]={ 00048 ['y'-'E']= -24, 00049 ['z'-'E']= -21, 00050 ['a'-'E']= -18, 00051 ['f'-'E']= -15, 00052 ['p'-'E']= -12, 00053 ['n'-'E']= - 9, 00054 ['u'-'E']= - 6, 00055 ['m'-'E']= - 3, 00056 ['c'-'E']= - 2, 00057 ['d'-'E']= - 1, 00058 ['h'-'E']= 2, 00059 ['k'-'E']= 3, 00060 ['K'-'E']= 3, 00061 ['M'-'E']= 6, 00062 ['G'-'E']= 9, 00063 ['T'-'E']= 12, 00064 ['P'-'E']= 15, 00065 ['E'-'E']= 18, 00066 ['Z'-'E']= 21, 00067 ['Y'-'E']= 24, 00068 }; 00069 00070 double av_strtod(const char *numstr, char **tail) { 00071 double d; 00072 char *next; 00073 d = strtod(numstr, &next); 00074 /* if parsing succeeded, check for and interpret postfixes */ 00075 if (next!=numstr) { 00076 00077 if(*next >= 'E' && *next <= 'z'){ 00078 int e= si_prefixes[*next - 'E']; 00079 if(e){ 00080 if(next[1] == 'i'){ 00081 d*= pow( 2, e/0.3); 00082 next+=2; 00083 }else{ 00084 d*= pow(10, e); 00085 next++; 00086 } 00087 } 00088 } 00089 00090 if(*next=='B') { 00091 d*=8; 00092 next++; 00093 } 00094 } 00095 /* if requested, fill in tail with the position after the last parsed 00096 character */ 00097 if (tail) 00098 *tail = next; 00099 return d; 00100 } 00101 00102 static int strmatch(const char *s, const char *prefix){ 00103 int i; 00104 for(i=0; prefix[i]; i++){ 00105 if(prefix[i] != s[i]) return 0; 00106 } 00107 return 1; 00108 } 00109 00110 struct AVExpr { 00111 enum { 00112 e_value, e_const, e_func0, e_func1, e_func2, 00113 e_squish, e_gauss, e_ld, 00114 e_mod, e_max, e_min, e_eq, e_gt, e_gte, 00115 e_pow, e_mul, e_div, e_add, 00116 e_last, e_st, e_while, 00117 } type; 00118 double value; // is sign in other types 00119 union { 00120 int const_index; 00121 double (*func0)(double); 00122 double (*func1)(void *, double); 00123 double (*func2)(void *, double, double); 00124 } a; 00125 struct AVExpr *param[2]; 00126 }; 00127 00128 static double eval_expr(Parser * p, AVExpr * e) { 00129 switch (e->type) { 00130 case e_value: return e->value; 00131 case e_const: return e->value * p->const_value[e->a.const_index]; 00132 case e_func0: return e->value * e->a.func0(eval_expr(p, e->param[0])); 00133 case e_func1: return e->value * e->a.func1(p->opaque, eval_expr(p, e->param[0])); 00134 case e_func2: return e->value * e->a.func2(p->opaque, eval_expr(p, e->param[0]), eval_expr(p, e->param[1])); 00135 case e_squish: return 1/(1+exp(4*eval_expr(p, e->param[0]))); 00136 case e_gauss: { double d = eval_expr(p, e->param[0]); return exp(-d*d/2)/sqrt(2*M_PI); } 00137 case e_ld: return e->value * p->var[av_clip(eval_expr(p, e->param[0]), 0, VARS-1)]; 00138 case e_while: { 00139 double d = NAN; 00140 while(eval_expr(p, e->param[0])) 00141 d=eval_expr(p, e->param[1]); 00142 return d; 00143 } 00144 default: { 00145 double d = eval_expr(p, e->param[0]); 00146 double d2 = eval_expr(p, e->param[1]); 00147 switch (e->type) { 00148 case e_mod: return e->value * (d - floor(d/d2)*d2); 00149 case e_max: return e->value * (d > d2 ? d : d2); 00150 case e_min: return e->value * (d < d2 ? d : d2); 00151 case e_eq: return e->value * (d == d2 ? 1.0 : 0.0); 00152 case e_gt: return e->value * (d > d2 ? 1.0 : 0.0); 00153 case e_gte: return e->value * (d >= d2 ? 1.0 : 0.0); 00154 case e_pow: return e->value * pow(d, d2); 00155 case e_mul: return e->value * (d * d2); 00156 case e_div: return e->value * (d / d2); 00157 case e_add: return e->value * (d + d2); 00158 case e_last:return e->value * d2; 00159 case e_st : return e->value * (p->var[av_clip(d, 0, VARS-1)]= d2); 00160 } 00161 } 00162 } 00163 return NAN; 00164 } 00165 00166 static AVExpr * parse_expr(Parser *p); 00167 00168 void ff_free_expr(AVExpr * e) { 00169 if (!e) return; 00170 ff_free_expr(e->param[0]); 00171 ff_free_expr(e->param[1]); 00172 av_freep(&e); 00173 } 00174 00175 static AVExpr * parse_primary(Parser *p) { 00176 AVExpr * d = av_mallocz(sizeof(AVExpr)); 00177 char *next= p->s; 00178 int i; 00179 00180 if (!d) 00181 return NULL; 00182 00183 /* number */ 00184 d->value = av_strtod(p->s, &next); 00185 if(next != p->s){ 00186 d->type = e_value; 00187 p->s= next; 00188 return d; 00189 } 00190 d->value = 1; 00191 00192 /* named constants */ 00193 for(i=0; p->const_name && p->const_name[i]; i++){ 00194 if(strmatch(p->s, p->const_name[i])){ 00195 p->s+= strlen(p->const_name[i]); 00196 d->type = e_const; 00197 d->a.const_index = i; 00198 return d; 00199 } 00200 } 00201 00202 p->s= strchr(p->s, '('); 00203 if(p->s==NULL){ 00204 *p->error = "undefined constant or missing ("; 00205 p->s= next; 00206 ff_free_expr(d); 00207 return NULL; 00208 } 00209 p->s++; // "(" 00210 if (*next == '(') { // special case do-nothing 00211 av_freep(&d); 00212 d = parse_expr(p); 00213 if(p->s[0] != ')'){ 00214 *p->error = "missing )"; 00215 ff_free_expr(d); 00216 return NULL; 00217 } 00218 p->s++; // ")" 00219 return d; 00220 } 00221 d->param[0] = parse_expr(p); 00222 if(p->s[0]== ','){ 00223 p->s++; // "," 00224 d->param[1] = parse_expr(p); 00225 } 00226 if(p->s[0] != ')'){ 00227 *p->error = "missing )"; 00228 ff_free_expr(d); 00229 return NULL; 00230 } 00231 p->s++; // ")" 00232 00233 d->type = e_func0; 00234 if( strmatch(next, "sinh" ) ) d->a.func0 = sinh; 00235 else if( strmatch(next, "cosh" ) ) d->a.func0 = cosh; 00236 else if( strmatch(next, "tanh" ) ) d->a.func0 = tanh; 00237 else if( strmatch(next, "sin" ) ) d->a.func0 = sin; 00238 else if( strmatch(next, "cos" ) ) d->a.func0 = cos; 00239 else if( strmatch(next, "tan" ) ) d->a.func0 = tan; 00240 else if( strmatch(next, "atan" ) ) d->a.func0 = atan; 00241 else if( strmatch(next, "asin" ) ) d->a.func0 = asin; 00242 else if( strmatch(next, "acos" ) ) d->a.func0 = acos; 00243 else if( strmatch(next, "exp" ) ) d->a.func0 = exp; 00244 else if( strmatch(next, "log" ) ) d->a.func0 = log; 00245 else if( strmatch(next, "abs" ) ) d->a.func0 = fabs; 00246 else if( strmatch(next, "squish") ) d->type = e_squish; 00247 else if( strmatch(next, "gauss" ) ) d->type = e_gauss; 00248 else if( strmatch(next, "mod" ) ) d->type = e_mod; 00249 else if( strmatch(next, "max" ) ) d->type = e_max; 00250 else if( strmatch(next, "min" ) ) d->type = e_min; 00251 else if( strmatch(next, "eq" ) ) d->type = e_eq; 00252 else if( strmatch(next, "gte" ) ) d->type = e_gte; 00253 else if( strmatch(next, "gt" ) ) d->type = e_gt; 00254 else if( strmatch(next, "lte" ) ) { AVExpr * tmp = d->param[1]; d->param[1] = d->param[0]; d->param[0] = tmp; d->type = e_gt; } 00255 else if( strmatch(next, "lt" ) ) { AVExpr * tmp = d->param[1]; d->param[1] = d->param[0]; d->param[0] = tmp; d->type = e_gte; } 00256 else if( strmatch(next, "ld" ) ) d->type = e_ld; 00257 else if( strmatch(next, "st" ) ) d->type = e_st; 00258 else if( strmatch(next, "while" ) ) d->type = e_while; 00259 else { 00260 for(i=0; p->func1_name && p->func1_name[i]; i++){ 00261 if(strmatch(next, p->func1_name[i])){ 00262 d->a.func1 = p->func1[i]; 00263 d->type = e_func1; 00264 return d; 00265 } 00266 } 00267 00268 for(i=0; p->func2_name && p->func2_name[i]; i++){ 00269 if(strmatch(next, p->func2_name[i])){ 00270 d->a.func2 = p->func2[i]; 00271 d->type = e_func2; 00272 return d; 00273 } 00274 } 00275 00276 *p->error = "unknown function"; 00277 ff_free_expr(d); 00278 return NULL; 00279 } 00280 00281 return d; 00282 } 00283 00284 static AVExpr * new_eval_expr(int type, int value, AVExpr *p0, AVExpr *p1){ 00285 AVExpr * e = av_mallocz(sizeof(AVExpr)); 00286 if (!e) 00287 return NULL; 00288 e->type =type ; 00289 e->value =value ; 00290 e->param[0] =p0 ; 00291 e->param[1] =p1 ; 00292 return e; 00293 } 00294 00295 static AVExpr * parse_pow(Parser *p, int *sign){ 00296 *sign= (*p->s == '+') - (*p->s == '-'); 00297 p->s += *sign&1; 00298 return parse_primary(p); 00299 } 00300 00301 static AVExpr * parse_factor(Parser *p){ 00302 int sign, sign2; 00303 AVExpr * e = parse_pow(p, &sign); 00304 while(p->s[0]=='^'){ 00305 p->s++; 00306 e= new_eval_expr(e_pow, 1, e, parse_pow(p, &sign2)); 00307 if (!e) 00308 return NULL; 00309 if (e->param[1]) e->param[1]->value *= (sign2|1); 00310 } 00311 if (e) e->value *= (sign|1); 00312 return e; 00313 } 00314 00315 static AVExpr * parse_term(Parser *p){ 00316 AVExpr * e = parse_factor(p); 00317 while(p->s[0]=='*' || p->s[0]=='/'){ 00318 int c= *p->s++; 00319 e= new_eval_expr(c == '*' ? e_mul : e_div, 1, e, parse_factor(p)); 00320 if (!e) 00321 return NULL; 00322 } 00323 return e; 00324 } 00325 00326 static AVExpr * parse_subexpr(Parser *p) { 00327 AVExpr * e = parse_term(p); 00328 while(*p->s == '+' || *p->s == '-') { 00329 e= new_eval_expr(e_add, 1, e, parse_term(p)); 00330 if (!e) 00331 return NULL; 00332 }; 00333 00334 return e; 00335 } 00336 00337 static AVExpr * parse_expr(Parser *p) { 00338 AVExpr * e; 00339 00340 if(p->stack_index <= 0) //protect against stack overflows 00341 return NULL; 00342 p->stack_index--; 00343 00344 e = parse_subexpr(p); 00345 00346 while(*p->s == ';') { 00347 p->s++; 00348 e= new_eval_expr(e_last, 1, e, parse_subexpr(p)); 00349 if (!e) 00350 return NULL; 00351 }; 00352 00353 p->stack_index++; 00354 00355 return e; 00356 } 00357 00358 static int verify_expr(AVExpr * e) { 00359 if (!e) return 0; 00360 switch (e->type) { 00361 case e_value: 00362 case e_const: return 1; 00363 case e_func0: 00364 case e_func1: 00365 case e_squish: 00366 case e_ld: 00367 case e_gauss: return verify_expr(e->param[0]); 00368 default: return verify_expr(e->param[0]) && verify_expr(e->param[1]); 00369 } 00370 } 00371 00372 AVExpr *ff_parse_expr(const char *s, const char * const *const_name, 00373 double (* const *func1)(void *, double), const char * const *func1_name, 00374 double (* const *func2)(void *, double, double), const char * const *func2_name, 00375 const char **error){ 00376 Parser p; 00377 AVExpr *e = NULL; 00378 char *w = av_malloc(strlen(s) + 1); 00379 char *wp = w; 00380 00381 if (!w) 00382 goto end; 00383 00384 while (*s) 00385 if (!isspace(*s++)) *wp++ = s[-1]; 00386 *wp++ = 0; 00387 00388 p.stack_index=100; 00389 p.s= w; 00390 p.const_name = const_name; 00391 p.func1 = func1; 00392 p.func1_name = func1_name; 00393 p.func2 = func2; 00394 p.func2_name = func2_name; 00395 p.error= error; 00396 00397 e = parse_expr(&p); 00398 if (!verify_expr(e)) { 00399 ff_free_expr(e); 00400 e = NULL; 00401 } 00402 end: 00403 av_free(w); 00404 return e; 00405 } 00406 00407 double ff_eval_expr(AVExpr * e, const double *const_value, void *opaque) { 00408 Parser p; 00409 00410 p.const_value= const_value; 00411 p.opaque = opaque; 00412 return eval_expr(&p, e); 00413 } 00414 00415 double ff_parse_and_eval_expr(const char *s, const double *const_value, const char * const *const_name, 00416 double (* const *func1)(void *, double), const char * const *func1_name, 00417 double (* const *func2)(void *, double, double), const char * const *func2_name, 00418 void *opaque, const char **error){ 00419 AVExpr * e = ff_parse_expr(s, const_name, func1, func1_name, func2, func2_name, error); 00420 double d; 00421 if (!e) return NAN; 00422 d = ff_eval_expr(e, const_value, opaque); 00423 ff_free_expr(e); 00424 return d; 00425 } 00426 00427 #ifdef TEST 00428 #undef printf 00429 static double const_values[]={ 00430 M_PI, 00431 M_E, 00432 0 00433 }; 00434 static const char *const_names[]={ 00435 "PI", 00436 "E", 00437 0 00438 }; 00439 int main(void){ 00440 int i; 00441 printf("%f == 12.7\n", ff_parse_and_eval_expr("1+(5-2)^(3-1)+1/2+sin(PI)-max(-2.2,-3.1)", const_values, const_names, NULL, NULL, NULL, NULL, NULL, NULL)); 00442 printf("%f == 0.931322575\n", ff_parse_and_eval_expr("80G/80Gi", const_values, const_names, NULL, NULL, NULL, NULL, NULL, NULL)); 00443 00444 for(i=0; i<1050; i++){ 00445 START_TIMER 00446 ff_parse_and_eval_expr("1+(5-2)^(3-1)+1/2+sin(PI)-max(-2.2,-3.1)", const_values, const_names, NULL, NULL, NULL, NULL, NULL, NULL); 00447 STOP_TIMER("ff_parse_and_eval_expr") 00448 } 00449 return 0; 00450 } 00451 #endif