eval.c 27 KB

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