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