Mercurial > libavcodec.hg
comparison eval.c @ 4081:cedb63307f3d libavcodec
new optimized eval method, by seperating parsing and runtime
author | ods15 |
---|---|
date | Fri, 27 Oct 2006 16:42:16 +0000 |
parents | 0f2bb0baf6f0 |
children | 16b88d6b3546 |
comparison
equal
deleted
inserted
replaced
4080:f426c81afc9e | 4081:cedb63307f3d |
---|---|
28 * see http://joe.hotchkiss.com/programming/eval/eval.html | 28 * see http://joe.hotchkiss.com/programming/eval/eval.html |
29 */ | 29 */ |
30 | 30 |
31 #include "avcodec.h" | 31 #include "avcodec.h" |
32 #include "mpegvideo.h" | 32 #include "mpegvideo.h" |
33 #include "eval.h" | |
33 | 34 |
34 #include <stdio.h> | 35 #include <stdio.h> |
35 #include <stdlib.h> | 36 #include <stdlib.h> |
36 #include <string.h> | 37 #include <string.h> |
37 #include <math.h> | 38 #include <math.h> |
54 double (**func2)(void *, double a, double b); // NULL terminated | 55 double (**func2)(void *, double a, double b); // NULL terminated |
55 char **func2_name; // NULL terminated | 56 char **func2_name; // NULL terminated |
56 void *opaque; | 57 void *opaque; |
57 char **error; | 58 char **error; |
58 } Parser; | 59 } Parser; |
59 | |
60 static double evalExpression(Parser *p); | |
61 | 60 |
62 static int8_t si_prefixes['z' - 'E' + 1]={ | 61 static int8_t si_prefixes['z' - 'E' + 1]={ |
63 ['y'-'E']= -24, | 62 ['y'-'E']= -24, |
64 ['z'-'E']= -21, | 63 ['z'-'E']= -21, |
65 ['a'-'E']= -18, | 64 ['a'-'E']= -18, |
124 if(prefix[i] != s[i]) return 0; | 123 if(prefix[i] != s[i]) return 0; |
125 } | 124 } |
126 return 1; | 125 return 1; |
127 } | 126 } |
128 | 127 |
129 static double evalPrimary(Parser *p){ | 128 struct ff_expr_s { |
130 double d, d2=NAN; | 129 enum { |
130 e_value, e_const, e_func0, e_func1, e_func2, | |
131 e_squish, e_gauss, | |
132 e_mod, e_max, e_min, e_eq, e_gt, e_gte, | |
133 e_pow, e_mul, e_div, e_add, | |
134 } type; | |
135 double value; // is sign in other types | |
136 union { | |
137 int const_index; | |
138 double (*func0)(double); | |
139 double (*func1)(void *, double); | |
140 double (*func2)(void *, double, double); | |
141 } a; | |
142 AVEvalExpr * param[2]; | |
143 }; | |
144 | |
145 static double eval_expr(Parser * p, AVEvalExpr * e) { | |
146 switch (e->type) { | |
147 case e_value: return e->value; | |
148 case e_const: return e->value * p->const_value[e->a.const_index]; | |
149 case e_func0: return e->value * e->a.func0(eval_expr(p, e->param[0])); | |
150 case e_func1: return e->value * e->a.func1(p->opaque, eval_expr(p, e->param[0])); | |
151 case e_func2: return e->value * e->a.func2(p->opaque, eval_expr(p, e->param[0]), eval_expr(p, e->param[1])); | |
152 case e_squish: return 1/(1+exp(4*eval_expr(p, e->param[0]))); | |
153 case e_gauss: { double d = eval_expr(p, e->param[0]); return exp(-d*d/2)/sqrt(2*M_PI); } | |
154 default: { | |
155 double d = eval_expr(p, e->param[0]); | |
156 double d2 = eval_expr(p, e->param[1]); | |
157 switch (e->type) { | |
158 case e_mod: return e->value * (d - floor(d/d2)*d2); | |
159 case e_max: return e->value * (d > d2 ? d : d2); | |
160 case e_min: return e->value * (d < d2 ? d : d2); | |
161 case e_eq: return e->value * (d == d2 ? 1.0 : 0.0); | |
162 case e_gt: return e->value * (d > d2 ? 1.0 : 0.0); | |
163 case e_gte: return e->value * (d >= d2 ? 1.0 : 0.0); | |
164 case e_pow: return e->value * pow(d, d2); | |
165 case e_mul: return e->value * (d * d2); | |
166 case e_div: return e->value * (d / d2); | |
167 case e_add: return e->value * (d + d2); | |
168 } | |
169 } | |
170 } | |
171 return NAN; | |
172 } | |
173 | |
174 static AVEvalExpr * parse_expr(Parser *p); | |
175 | |
176 void ff_eval_free(AVEvalExpr * e) { | |
177 if (!e) return; | |
178 ff_eval_free(e->param[0]); | |
179 ff_eval_free(e->param[1]); | |
180 av_freep(&e); | |
181 } | |
182 | |
183 static AVEvalExpr * parse_primary(Parser *p) { | |
184 AVEvalExpr * d = av_mallocz(sizeof(AVEvalExpr)); | |
131 char *next= p->s; | 185 char *next= p->s; |
132 int i; | 186 int i; |
133 | 187 |
134 /* number */ | 188 /* number */ |
135 d= av_strtod(p->s, &next); | 189 d->value = av_strtod(p->s, &next); |
136 if(next != p->s){ | 190 if(next != p->s){ |
191 d->type = e_value; | |
137 p->s= next; | 192 p->s= next; |
138 return d; | 193 return d; |
139 } | 194 } |
195 d->value = 1; | |
140 | 196 |
141 /* named constants */ | 197 /* named constants */ |
142 for(i=0; p->const_name && p->const_name[i]; i++){ | 198 for(i=0; p->const_name && p->const_name[i]; i++){ |
143 if(strmatch(p->s, p->const_name[i])){ | 199 if(strmatch(p->s, p->const_name[i])){ |
144 p->s+= strlen(p->const_name[i]); | 200 p->s+= strlen(p->const_name[i]); |
145 return p->const_value[i]; | 201 d->type = e_const; |
202 d->a.const_index = i; | |
203 return d; | |
146 } | 204 } |
147 } | 205 } |
148 | 206 |
149 p->s= strchr(p->s, '('); | 207 p->s= strchr(p->s, '('); |
150 if(p->s==NULL){ | 208 if(p->s==NULL){ |
151 *p->error = "missing ("; | 209 *p->error = "missing ("; |
152 p->s= next; | 210 p->s= next; |
153 return NAN; | 211 ff_eval_free(d); |
212 return NULL; | |
154 } | 213 } |
155 p->s++; // "(" | 214 p->s++; // "(" |
156 d= evalExpression(p); | 215 if (*next == '(') { // special case do-nothing |
216 av_freep(&d); | |
217 d = parse_expr(p); | |
218 if(p->s[0] != ')'){ | |
219 *p->error = "missing )"; | |
220 ff_eval_free(d); | |
221 return NULL; | |
222 } | |
223 p->s++; // ")" | |
224 return d; | |
225 } | |
226 d->param[0] = parse_expr(p); | |
157 if(p->s[0]== ','){ | 227 if(p->s[0]== ','){ |
158 p->s++; // "," | 228 p->s++; // "," |
159 d2= evalExpression(p); | 229 d->param[1] = parse_expr(p); |
160 } | 230 } |
161 if(p->s[0] != ')'){ | 231 if(p->s[0] != ')'){ |
162 *p->error = "missing )"; | 232 *p->error = "missing )"; |
163 return NAN; | 233 ff_eval_free(d); |
234 return NULL; | |
164 } | 235 } |
165 p->s++; // ")" | 236 p->s++; // ")" |
166 | 237 |
167 if( strmatch(next, "sinh" ) ) d= sinh(d); | 238 d->type = e_func0; |
168 else if( strmatch(next, "cosh" ) ) d= cosh(d); | 239 if( strmatch(next, "sinh" ) ) d->a.func0 = sinh; |
169 else if( strmatch(next, "tanh" ) ) d= tanh(d); | 240 else if( strmatch(next, "cosh" ) ) d->a.func0 = cosh; |
170 else if( strmatch(next, "sin" ) ) d= sin(d); | 241 else if( strmatch(next, "tanh" ) ) d->a.func0 = tanh; |
171 else if( strmatch(next, "cos" ) ) d= cos(d); | 242 else if( strmatch(next, "sin" ) ) d->a.func0 = sin; |
172 else if( strmatch(next, "tan" ) ) d= tan(d); | 243 else if( strmatch(next, "cos" ) ) d->a.func0 = cos; |
173 else if( strmatch(next, "atan" ) ) d= atan(d); | 244 else if( strmatch(next, "tan" ) ) d->a.func0 = tan; |
174 else if( strmatch(next, "asin" ) ) d= asin(d); | 245 else if( strmatch(next, "atan" ) ) d->a.func0 = atan; |
175 else if( strmatch(next, "acos" ) ) d= acos(d); | 246 else if( strmatch(next, "asin" ) ) d->a.func0 = asin; |
176 else if( strmatch(next, "exp" ) ) d= exp(d); | 247 else if( strmatch(next, "acos" ) ) d->a.func0 = acos; |
177 else if( strmatch(next, "log" ) ) d= log(d); | 248 else if( strmatch(next, "exp" ) ) d->a.func0 = exp; |
178 else if( strmatch(next, "squish") ) d= 1/(1+exp(4*d)); | 249 else if( strmatch(next, "log" ) ) d->a.func0 = log; |
179 else if( strmatch(next, "gauss" ) ) d= exp(-d*d/2)/sqrt(2*M_PI); | 250 else if( strmatch(next, "abs" ) ) d->a.func0 = fabs; |
180 else if( strmatch(next, "abs" ) ) d= fabs(d); | 251 else if( strmatch(next, "squish") ) d->type = e_squish; |
181 else if( strmatch(next, "mod" ) ) d-= floor(d/d2)*d2; | 252 else if( strmatch(next, "gauss" ) ) d->type = e_gauss; |
182 else if( strmatch(next, "max" ) ) d= d > d2 ? d : d2; | 253 else if( strmatch(next, "mod" ) ) d->type = e_mod; |
183 else if( strmatch(next, "min" ) ) d= d < d2 ? d : d2; | 254 else if( strmatch(next, "max" ) ) d->type = e_max; |
184 else if( strmatch(next, "gt" ) ) d= d > d2 ? 1.0 : 0.0; | 255 else if( strmatch(next, "min" ) ) d->type = e_min; |
185 else if( strmatch(next, "gte" ) ) d= d >= d2 ? 1.0 : 0.0; | 256 else if( strmatch(next, "eq" ) ) d->type = e_eq; |
186 else if( strmatch(next, "lt" ) ) d= d > d2 ? 0.0 : 1.0; | 257 else if( strmatch(next, "gt" ) ) d->type = e_gt; |
187 else if( strmatch(next, "lte" ) ) d= d >= d2 ? 0.0 : 1.0; | 258 else if( strmatch(next, "gte" ) ) d->type = e_gte; |
188 else if( strmatch(next, "eq" ) ) d= d == d2 ? 1.0 : 0.0; | 259 else if( strmatch(next, "lt" ) ) { AVEvalExpr * tmp = d->param[1]; d->param[1] = d->param[0]; d->param[0] = tmp; d->type = e_gte; } |
189 else if( strmatch(next, "(" ) ) d= d; | 260 else if( strmatch(next, "lte" ) ) { AVEvalExpr * tmp = d->param[1]; d->param[1] = d->param[0]; d->param[0] = tmp; d->type = e_gt; } |
190 // else if( strmatch(next, "l1" ) ) d= 1 + d2*(d - 1); | 261 else { |
191 // else if( strmatch(next, "sq01" ) ) d= (d >= 0.0 && d <=1.0) ? 1.0 : 0.0; | |
192 else{ | |
193 for(i=0; p->func1_name && p->func1_name[i]; i++){ | 262 for(i=0; p->func1_name && p->func1_name[i]; i++){ |
194 if(strmatch(next, p->func1_name[i])){ | 263 if(strmatch(next, p->func1_name[i])){ |
195 return p->func1[i](p->opaque, d); | 264 d->a.func1 = p->func1[i]; |
265 d->type = e_func1; | |
266 return d; | |
196 } | 267 } |
197 } | 268 } |
198 | 269 |
199 for(i=0; p->func2_name && p->func2_name[i]; i++){ | 270 for(i=0; p->func2_name && p->func2_name[i]; i++){ |
200 if(strmatch(next, p->func2_name[i])){ | 271 if(strmatch(next, p->func2_name[i])){ |
201 return p->func2[i](p->opaque, d, d2); | 272 d->a.func2 = p->func2[i]; |
273 d->type = e_func2; | |
274 return d; | |
202 } | 275 } |
203 } | 276 } |
204 | 277 |
205 *p->error = "unknown function"; | 278 *p->error = "unknown function"; |
206 return NAN; | 279 ff_eval_free(d); |
280 return NULL; | |
207 } | 281 } |
208 | 282 |
209 return d; | 283 return d; |
210 } | 284 } |
211 | 285 |
212 static double evalPow(Parser *p, int *sign){ | 286 static AVEvalExpr * parse_pow(Parser *p, int *sign){ |
213 *sign= (*p->s == '+') - (*p->s == '-'); | 287 *sign= (*p->s == '+') - (*p->s == '-'); |
214 p->s += *sign&1; | 288 p->s += *sign&1; |
215 return evalPrimary(p); | 289 return parse_primary(p); |
216 } | 290 } |
217 | 291 |
218 static double evalFactor(Parser *p){ | 292 static AVEvalExpr * parse_factor(Parser *p){ |
219 int sign, sign2; | 293 int sign, sign2; |
220 double ret, e; | 294 AVEvalExpr * e = parse_pow(p, &sign); |
221 ret= evalPow(p, &sign); | |
222 while(p->s[0]=='^'){ | 295 while(p->s[0]=='^'){ |
296 AVEvalExpr * tmp = av_mallocz(sizeof(AVEvalExpr)); | |
297 | |
223 p->s++; | 298 p->s++; |
224 e= evalPow(p, &sign2); | 299 |
225 ret= pow(ret, (sign2|1) * e); | 300 tmp->type = e_pow; |
226 } | 301 tmp->value = 1.; |
227 return (sign|1) * ret; | 302 tmp->param[0] = e; |
228 } | 303 tmp->param[1] = parse_pow(p, &sign2); |
229 | 304 if (tmp->param[1]) tmp->param[1]->value *= (sign2|1); |
230 static double evalTerm(Parser *p){ | 305 e = tmp; |
231 double ret= evalFactor(p); | 306 } |
307 if (e) e->value *= (sign|1); | |
308 return e; | |
309 } | |
310 | |
311 static AVEvalExpr * parse_term(Parser *p){ | |
312 AVEvalExpr * e = parse_factor(p); | |
232 while(p->s[0]=='*' || p->s[0]=='/'){ | 313 while(p->s[0]=='*' || p->s[0]=='/'){ |
233 if(*p->s++ == '*') ret*= evalFactor(p); | 314 AVEvalExpr * tmp = av_mallocz(sizeof(AVEvalExpr)); |
234 else ret/= evalFactor(p); | 315 if(*p->s++ == '*') tmp->type = e_mul; |
235 } | 316 else tmp->type = e_div; |
236 return ret; | 317 tmp->value = 1.; |
237 } | 318 tmp->param[0] = e; |
238 | 319 tmp->param[1] = parse_factor(p); |
239 static double evalExpression(Parser *p){ | 320 e = tmp; |
240 double ret= 0; | 321 } |
322 return e; | |
323 } | |
324 | |
325 static AVEvalExpr * parse_expr(Parser *p) { | |
326 AVEvalExpr * e; | |
241 | 327 |
242 if(p->stack_index <= 0) //protect against stack overflows | 328 if(p->stack_index <= 0) //protect against stack overflows |
243 return NAN; | 329 return NULL; |
244 p->stack_index--; | 330 p->stack_index--; |
245 | 331 |
246 do{ | 332 e = parse_term(p); |
247 ret += evalTerm(p); | 333 |
248 }while(*p->s == '+' || *p->s == '-'); | 334 while(*p->s == '+' || *p->s == '-') { |
335 AVEvalExpr * tmp = av_mallocz(sizeof(AVEvalExpr)); | |
336 tmp->type = e_add; | |
337 tmp->value = 1.; | |
338 tmp->param[0] = e; | |
339 tmp->param[1] = parse_term(p); | |
340 e = tmp; | |
341 }; | |
249 | 342 |
250 p->stack_index++; | 343 p->stack_index++; |
251 | 344 |
252 return ret; | 345 return e; |
253 } | 346 } |
254 | 347 |
255 double ff_eval2(char *s, double *const_value, const char **const_name, | 348 static int verify_expr(AVEvalExpr * e) { |
349 if (!e) return 0; | |
350 switch (e->type) { | |
351 case e_value: | |
352 case e_const: return 1; | |
353 case e_func0: | |
354 case e_func1: | |
355 case e_squish: | |
356 case e_gauss: return verify_expr(e->param[0]); | |
357 default: return verify_expr(e->param[0]) && verify_expr(e->param[1]); | |
358 } | |
359 } | |
360 | |
361 AVEvalExpr * ff_parse(char *s, const char **const_name, | |
256 double (**func1)(void *, double), const char **func1_name, | 362 double (**func1)(void *, double), const char **func1_name, |
257 double (**func2)(void *, double, double), char **func2_name, | 363 double (**func2)(void *, double, double), char **func2_name, |
258 void *opaque, char **error){ | 364 char **error){ |
259 Parser p; | 365 Parser p; |
366 AVEvalExpr * e; | |
260 | 367 |
261 p.stack_index=100; | 368 p.stack_index=100; |
262 p.s= s; | 369 p.s= s; |
263 p.const_value= const_value; | |
264 p.const_name = const_name; | 370 p.const_name = const_name; |
265 p.func1 = func1; | 371 p.func1 = func1; |
266 p.func1_name = func1_name; | 372 p.func1_name = func1_name; |
267 p.func2 = func2; | 373 p.func2 = func2; |
268 p.func2_name = func2_name; | 374 p.func2_name = func2_name; |
375 p.error= error; | |
376 | |
377 e = parse_expr(&p); | |
378 if (!verify_expr(e)) { | |
379 ff_eval_free(e); | |
380 return NULL; | |
381 } | |
382 return e; | |
383 } | |
384 | |
385 double ff_parse_eval(AVEvalExpr * e, double *const_value, void *opaque) { | |
386 Parser p; | |
387 | |
388 p.const_value= const_value; | |
269 p.opaque = opaque; | 389 p.opaque = opaque; |
270 p.error= error; | 390 return eval_expr(&p, e); |
271 | 391 } |
272 return evalExpression(&p); | 392 |
393 double ff_eval2(char *s, double *const_value, const char **const_name, | |
394 double (**func1)(void *, double), const char **func1_name, | |
395 double (**func2)(void *, double, double), char **func2_name, | |
396 void *opaque, char **error){ | |
397 AVEvalExpr * e = ff_parse(s, const_name, func1, func1_name, func2, func2_name, error); | |
398 double d; | |
399 if (!e) return NAN; | |
400 d = ff_parse_eval(e, const_value, opaque); | |
401 ff_eval_free(e); | |
402 return d; | |
273 } | 403 } |
274 | 404 |
275 #if LIBAVCODEC_VERSION_INT < ((52<<16)+(0<<8)+0) | 405 #if LIBAVCODEC_VERSION_INT < ((52<<16)+(0<<8)+0) |
276 attribute_deprecated double ff_eval(char *s, double *const_value, const char **const_name, | 406 attribute_deprecated double ff_eval(char *s, double *const_value, const char **const_name, |
277 double (**func1)(void *, double), const char **func1_name, | 407 double (**func1)(void *, double), const char **func1_name, |