1 /***************************************************************************\
2 |* Function Parser for C++ v4.5.2 *|
3 |*-------------------------------------------------------------------------*|
4 |* Copyright: Juha Nieminen, Joel Yliluoma *|
5 |* *|
6 |* This library is distributed under the terms of the *|
7 |* GNU Lesser General Public License version 3. *|
8 |* (See lgpl.txt and gpl.txt for the license text.) *|
9 \***************************************************************************/
10
11 #include "fpconfig.hh"
12 #include "fparser.hh"
13
14 #include <set>
15 #include <cstdlib>
16 #include <cstring>
17 #include <cctype>
18 #include <cmath>
19 #include <cassert>
20 #include <limits>
21
22 #include "extrasrc/fptypes.hh"
23 #include "extrasrc/fpaux.hh"
24 using namespace FUNCTIONPARSERTYPES;
25
26 #ifdef FP_USE_THREAD_SAFE_EVAL_WITH_ALLOCA
27 #ifndef FP_USE_THREAD_SAFE_EVAL
28 #define FP_USE_THREAD_SAFE_EVAL
29 #endif
30 #endif
31
32 #ifdef __GNUC__
33 # define likely(x) __builtin_expect(!!(x), 1)
34 # define unlikely(x) __builtin_expect(!!(x), 0)
35 #else
36 # define likely(x) (x)
37 # define unlikely(x) (x)
38 #endif
39
40 //=========================================================================
41 // Opcode analysis functions
42 //=========================================================================
43 // These functions are used by the Parse() bytecode optimizer (mostly from
44 // code in fp_opcode_add.inc).
45
IsLogicalOpcode(unsigned op)46 bool FUNCTIONPARSERTYPES::IsLogicalOpcode(unsigned op)
47 {
48 switch(op)
49 {
50 case cAnd: case cAbsAnd:
51 case cOr: case cAbsOr:
52 case cNot: case cAbsNot:
53 case cNotNot: case cAbsNotNot:
54 case cEqual: case cNEqual:
55 case cLess: case cLessOrEq:
56 case cGreater: case cGreaterOrEq:
57 return true;
58 default: break;
59 }
60 return false;
61 }
62
IsComparisonOpcode(unsigned op)63 bool FUNCTIONPARSERTYPES::IsComparisonOpcode(unsigned op)
64 {
65 switch(op)
66 {
67 case cEqual: case cNEqual:
68 case cLess: case cLessOrEq:
69 case cGreater: case cGreaterOrEq:
70 return true;
71 default: break;
72 }
73 return false;
74 }
75
OppositeComparisonOpcode(unsigned op)76 unsigned FUNCTIONPARSERTYPES::OppositeComparisonOpcode(unsigned op)
77 {
78 switch(op)
79 {
80 case cLess: return cGreater;
81 case cGreater: return cLess;
82 case cLessOrEq: return cGreaterOrEq;
83 case cGreaterOrEq: return cLessOrEq;
84 }
85 return op;
86 }
87
IsNeverNegativeValueOpcode(unsigned op)88 bool FUNCTIONPARSERTYPES::IsNeverNegativeValueOpcode(unsigned op)
89 {
90 switch(op)
91 {
92 case cAnd: case cAbsAnd:
93 case cOr: case cAbsOr:
94 case cNot: case cAbsNot:
95 case cNotNot: case cAbsNotNot:
96 case cEqual: case cNEqual:
97 case cLess: case cLessOrEq:
98 case cGreater: case cGreaterOrEq:
99 case cSqrt: case cRSqrt: case cSqr:
100 case cHypot:
101 case cAbs:
102 case cAcos: case cCosh:
103 return true;
104 default: break;
105 }
106 return false;
107 }
108
IsAlwaysIntegerOpcode(unsigned op)109 bool FUNCTIONPARSERTYPES::IsAlwaysIntegerOpcode(unsigned op)
110 {
111 switch(op)
112 {
113 case cAnd: case cAbsAnd:
114 case cOr: case cAbsOr:
115 case cNot: case cAbsNot:
116 case cNotNot: case cAbsNotNot:
117 case cEqual: case cNEqual:
118 case cLess: case cLessOrEq:
119 case cGreater: case cGreaterOrEq:
120 case cInt: case cFloor: case cCeil: case cTrunc:
121 return true;
122 default: break;
123 }
124 return false;
125 }
126
IsUnaryOpcode(unsigned op)127 bool FUNCTIONPARSERTYPES::IsUnaryOpcode(unsigned op)
128 {
129 switch(op)
130 {
131 case cInv: case cNeg:
132 case cNot: case cAbsNot:
133 case cNotNot: case cAbsNotNot:
134 case cSqr: case cRSqrt:
135 case cDeg: case cRad:
136 return true;
137 }
138 return (op < FUNC_AMOUNT && Functions[op].params == 1);
139 }
140
IsBinaryOpcode(unsigned op)141 bool FUNCTIONPARSERTYPES::IsBinaryOpcode(unsigned op)
142 {
143 switch(op)
144 {
145 case cAdd: case cSub: case cRSub:
146 case cMul: case cDiv: case cRDiv:
147 case cMod:
148 case cEqual: case cNEqual: case cLess:
149 case cLessOrEq: case cGreater: case cGreaterOrEq:
150 case cAnd: case cAbsAnd:
151 case cOr: case cAbsOr:
152 return true;
153 }
154 return (op < FUNC_AMOUNT && Functions[op].params == 2);
155 }
156
IsVarOpcode(unsigned op)157 bool FUNCTIONPARSERTYPES::IsVarOpcode(unsigned op)
158 {
159 // See comment in declaration of FP_ParamGuardMask
160 return int(op) >= VarBegin;
161 }
162
IsCommutativeOrParamSwappableBinaryOpcode(unsigned op)163 bool FUNCTIONPARSERTYPES::IsCommutativeOrParamSwappableBinaryOpcode(unsigned op)
164 {
165 switch(op)
166 {
167 case cAdd:
168 case cMul:
169 case cEqual: case cNEqual:
170 case cAnd: case cAbsAnd:
171 case cOr: case cAbsOr:
172 case cMin: case cMax: case cHypot:
173 return true;
174 case cDiv: case cSub: case cRDiv: case cRSub:
175 return true;
176 case cLess: case cGreater:
177 case cLessOrEq: case cGreaterOrEq: return true;
178 }
179 return false;
180 }
181
GetParamSwappedBinaryOpcode(unsigned op)182 unsigned FUNCTIONPARSERTYPES::GetParamSwappedBinaryOpcode(unsigned op)
183 {
184 switch(op)
185 {
186 case cAdd:
187 case cMul:
188 case cEqual: case cNEqual:
189 case cAnd: case cAbsAnd:
190 case cOr: case cAbsOr:
191 case cMin: case cMax: case cHypot:
192 return op;
193 case cDiv: return cRDiv;
194 case cSub: return cRSub;
195 case cRDiv: return cDiv;
196 case cRSub: return cSub;
197 case cLess: return cGreater;
198 case cGreater: return cLess;
199 case cLessOrEq: return cGreaterOrEq;
200 case cGreaterOrEq: return cLessOrEq;
201 }
202 return op; // Error
203 }
204
205 template<bool ComplexType>
HasInvalidRangesOpcode(unsigned op)206 bool FUNCTIONPARSERTYPES::HasInvalidRangesOpcode(unsigned op)
207 {
208 // Returns true, if the given opcode has a range of
209 // input values that gives an error.
210 if(ComplexType)
211 {
212 // COMPLEX:
213 switch(op)
214 {
215 case cAtan: // allowed range: x != +-1i
216 case cAtanh: // allowed range: x != +-1
217 //case cCot: // allowed range: tan(x) != 0
218 //case cCsc: // allowed range: sin(x) != 0
219 case cLog: // allowed range: x != 0
220 case cLog2: // allowed range: x != 0
221 case cLog10: // allowed range: x != 0
222 #ifdef FP_SUPPORT_OPTIMIZER
223 case cLog2by:// allowed range: x != 0
224 #endif
225 //case cPow: // allowed when: x != 0 or y != 0
226 //case cSec: // allowed range: cos(x) != 0
227 //case cTan: // allowed range: cos(x) != 0 --> x != +-(pi/2)
228 //case cTanh: // allowed range: log(x) != -1 --> x != +-(pi/2)i
229 case cRSqrt: // allowed range: x != 0
230 //case cDiv: // allowed range: y != 0
231 //case cRDiv: // allowed range: x != 0
232 //case cInv: // allowed range: x != 0
233 return true;
234 }
235 }
236 else
237 {
238 // REAL:
239 switch(op)
240 {
241 case cAcos: // allowed range: |x| <= 1
242 case cAsin: // allowed range: |x| <= 1
243 case cAcosh: // allowed range: x >= 1
244 case cAtanh: // allowed range: |x| < 1
245 //case cCot: // allowed range: tan(x) != 0
246 //case cCsc: // allowed range: sin(x) != 0
247 case cLog: // allowed range: x > 0
248 case cLog2: // allowed range: x > 0
249 case cLog10: // allowed range: x > 0
250 #ifdef FP_SUPPORT_OPTIMIZER
251 case cLog2by:// allowed range: x > 0
252 #endif
253 //case cPow: // allowed when: x > 0 or (x = 0 and y != 0) or (x<0)
254 // Technically, when (x<0 and y is not integer),
255 // it is not allowed, but we allow it anyway
256 // in order to make nontrivial roots work.
257 //case cSec: // allowed range: cos(x) != 0
258 case cSqrt: // allowed range: x >= 0
259 case cRSqrt: // allowed range: x > 0
260 //case cTan: // allowed range: cos(x) != 0 --> x != +-(pi/2)
261 //case cDiv: // allowed range: y != 0
262 //case cRDiv: // allowed range: x != 0
263 //case cInv: // allowed range: x != 0
264 return true;
265 }
266 }
267 return false;
268 }
269
270 template bool FUNCTIONPARSERTYPES::HasInvalidRangesOpcode<false>(unsigned op);
271 template bool FUNCTIONPARSERTYPES::HasInvalidRangesOpcode<true>(unsigned op);
272
273
274 #if(0) // Implementation moved to fpaux.hh due to linker problems
275 //=========================================================================
276 // Mathematical template functions
277 //=========================================================================
278 /* fp_pow() is a wrapper for std::pow()
279 * that produces an identical value for
280 * exp(1) ^ 2.0 (0x4000000000000000)
281 * as exp(2.0) (0x4000000000000000)
282 * - std::pow() on x86_64
283 * produces 2.0 (0x3FFFFFFFFFFFFFFF) instead!
284 * See comments below for other special traits.
285 */
286 namespace
287 {
288 template<typename ValueT>
fp_pow_with_exp_log(const ValueT & x,const ValueT & y)289 inline ValueT fp_pow_with_exp_log(const ValueT& x, const ValueT& y)
290 {
291 // Exponentiation using exp(log(x)*y).
292 // See http://en.wikipedia.org/wiki/Exponentiation#Real_powers
293 // Requirements: x > 0.
294 return fp_exp(fp_log(x) * y);
295 }
296
297 template<typename ValueT>
fp_powi(ValueT x,unsigned long y)298 inline ValueT fp_powi(ValueT x, unsigned long y)
299 {
300 // Fast binary exponentiation algorithm
301 // See http://en.wikipedia.org/wiki/Exponentiation_by_squaring
302 // Requirements: y is non-negative integer.
303 ValueT result(1);
304 while(y != 0)
305 {
306 if(y & 1) { result *= x; y -= 1; }
307 else { x *= x; y /= 2; }
308 }
309 return result;
310 }
311 }
312
313 template<typename ValueT>
fp_pow(const ValueT & x,const ValueT & y)314 ValueT FUNCTIONPARSERTYPES::fp_pow(const ValueT& x, const ValueT& y)
315 {
316 if(x == ValueT(1)) return ValueT(1);
317 // y is now zero or positive
318 if(isLongInteger(y))
319 {
320 // Use fast binary exponentiation algorithm
321 if(y >= ValueT(0))
322 return fp_powi(x, makeLongInteger(y));
323 else
324 return ValueT(1) / fp_powi(x, -makeLongInteger(y));
325 }
326 if(y >= ValueT(0))
327 {
328 // y is now positive. Calculate using exp(log(x)*y).
329 if(x > ValueT(0)) return fp_pow_with_exp_log(x, y);
330 if(x == ValueT(0)) return ValueT(0);
331 // At this point, y > 0.0 and x is known to be < 0.0,
332 // because positive and zero cases are already handled.
333 if(!isInteger(y*ValueT(16)))
334 return -fp_pow_with_exp_log(-x, y);
335 // ^This is not technically correct, but it allows
336 // functions such as cbrt(x^5), that is, x^(5/3),
337 // to be evaluated when x is negative.
338 // It is too complicated (and slow) to test whether y
339 // is a formed from a ratio of an integer to an odd integer.
340 // (And due to floating point inaccuracy, pointless too.)
341 // For example, x^1.30769230769... is
342 // actually x^(17/13), i.e. (x^17) ^ (1/13).
343 // (-5)^(17/13) gives us now -8.204227562330453.
344 // To see whether the result is right, we can test the given
345 // root: (-8.204227562330453)^13 gives us the value of (-5)^17,
346 // which proves that the expression was correct.
347 //
348 // The y*16 check prevents e.g. (-4)^(3/2) from being calculated,
349 // as it would confuse functioninfo when pow() returns no error
350 // but sqrt() does when the formula is converted into sqrt(x)*x.
351 //
352 // The errors in this approach are:
353 // (-2)^sqrt(2) should produce NaN
354 // or actually sqrt(2)I + 2^sqrt(2),
355 // produces -(2^sqrt(2)) instead.
356 // (Impact: Neglible)
357 // Thus, at worst, we're changing a NaN (or complex)
358 // result into a negative real number result.
359 }
360 else
361 {
362 // y is negative. Utilize the x^y = 1/(x^-y) identity.
363 if(x > ValueT(0)) return fp_pow_with_exp_log(ValueT(1) / x, -y);
364 if(x < ValueT(0))
365 {
366 if(!isInteger(y*ValueT(-16)))
367 return -fp_pow_with_exp_log(ValueT(-1) / x, -y);
368 // ^ See comment above.
369 }
370 // Remaining case: 0.0 ^ negative number
371 }
372 // This is reached when:
373 // x=0, and y<0
374 // x<0, and y*16 is either positive or negative integer
375 // It is used for producing error values and as a safe fallback.
376 return fp_pow_base(x, y);
377 }
378 #endif
379
380
381 //=========================================================================
382 // Elementary (atom) parsing functions
383 //=========================================================================
384 namespace
385 {
386 const unsigned FP_ParamGuardMask = 1U << (sizeof(unsigned) * 8u - 1u);
387 // ^ This mask is used to prevent cFetch/other opcode's parameters
388 // from being confused into opcodes or variable indices within the
389 // bytecode optimizer. Because the way it is tested in bytecoderules.dat
390 // for speed reasons, it must also be the sign-bit of the "int" datatype.
391 // Perhaps an "assert(IsVarOpcode(X | FP_ParamGuardMask) == false)"
392 // might be justified to put somewhere in the code, just in case?
393
394
395 /* Reads an UTF8-encoded sequence which forms a valid identifier name from
396 the given input string and returns its length. If bit 31 is set, the
397 return value also contains the internal function opcode (defined in
398 fptypes.hh) that matches the name.
399 */
readIdentifierCommon(const char * input)400 unsigned readIdentifierCommon(const char* input)
401 {
402 /* Assuming unsigned = 32 bits:
403 76543210 76543210 76543210 76543210
404 Return value if built-in function:
405 1PPPPPPP PPPPPPPP LLLLLLLL LLLLLLLL
406 P = function opcode (15 bits)
407 L = function name length (16 bits)
408 Return value if not built-in function:
409 0LLLLLLL LLLLLLLL LLLLLLLL LLLLLLLL
410 L = identifier length (31 bits)
411 If unsigned has more than 32 bits, the other
412 higher order bits are to be assumed zero.
413 */
414 #include "extrasrc/fp_identifier_parser.inc"
415 return 0;
416 }
417
418 template<typename Value_t>
readIdentifier(const char * input)419 inline unsigned readIdentifier(const char* input)
420 {
421 const unsigned value = readIdentifierCommon(input);
422 if( (value & 0x80000000U) != 0) // Function?
423 {
424 // Verify that the function actually exists for this datatype
425 if(IsIntType<Value_t>::result
426 && !Functions[(value >> 16) & 0x7FFF].okForInt())
427 {
428 // If it does not exist, return it as an identifier instead
429 return value & 0xFFFFu;
430 }
431 if(!IsComplexType<Value_t>::result
432 && Functions[(value >> 16) & 0x7FFF].complexOnly())
433 {
434 // If it does not exist, return it as an identifier instead
435 return value & 0xFFFFu;
436 }
437 }
438 return value;
439 }
440
441 // Returns true if the entire string is a valid identifier
442 template<typename Value_t>
containsOnlyValidIdentifierChars(const std::string & name)443 bool containsOnlyValidIdentifierChars(const std::string& name)
444 {
445 if(name.empty()) return false;
446 return readIdentifier<Value_t>(name.c_str()) == (unsigned) name.size();
447 }
448
449
450 // -----------------------------------------------------------------------
451 // Wrappers for strto... functions
452 // -----------------------------------------------------------------------
453 template<typename Value_t>
fp_parseLiteral(const char * str,char ** endptr)454 inline Value_t fp_parseLiteral(const char* str, char** endptr)
455 {
456 return std::strtod(str, endptr);
457 }
458
459 #if defined(FP_USE_STRTOLD) || defined(FP_SUPPORT_CPLUSPLUS11_MATH_FUNCS)
460 template<>
fp_parseLiteral(const char * str,char ** endptr)461 inline long double fp_parseLiteral<long double>(const char* str,
462 char** endptr)
463 {
464 using namespace std; // Just in case strtold() is not inside std::
465 return strtold(str, endptr);
466 }
467 #endif
468
469 #ifdef FP_SUPPORT_LONG_INT_TYPE
470 template<>
fp_parseLiteral(const char * str,char ** endptr)471 inline long fp_parseLiteral<long>(const char* str, char** endptr)
472 {
473 return std::strtol(str, endptr, 10);
474 }
475 #endif
476
477 #ifdef FP_SUPPORT_COMPLEX_NUMBERS
478 template<typename T>
fp_parseComplexLiteral(const char * str,char ** endptr)479 inline std::complex<T> fp_parseComplexLiteral(const char* str,
480 char** endptr)
481 {
482 T result = fp_parseLiteral<T> (str,endptr);
483 const char* end = *endptr;
484 if( (*end == 'i' || *end == 'I')
485 && !std::isalnum(end[1]) )
486 {
487 ++*endptr;
488 return std::complex<T> (T(), result);
489 }
490 return std::complex<T> (result, T());
491 }
492 #endif
493
494 #ifdef FP_SUPPORT_COMPLEX_DOUBLE_TYPE
495 template<>
fp_parseLiteral(const char * str,char ** endptr)496 inline std::complex<double> fp_parseLiteral<std::complex<double> >
497 (const char* str, char** endptr)
498 {
499 return fp_parseComplexLiteral<double> (str,endptr);
500 }
501 #endif
502
503 #ifdef FP_SUPPORT_COMPLEX_FLOAT_TYPE
504 template<>
fp_parseLiteral(const char * str,char ** endptr)505 inline std::complex<float> fp_parseLiteral<std::complex<float> >
506 (const char* str, char** endptr)
507 {
508 return fp_parseComplexLiteral<float> (str,endptr);
509 }
510 #endif
511
512 #ifdef FP_SUPPORT_COMPLEX_LONG_DOUBLE_TYPE
513 template<>
fp_parseLiteral(const char * str,char ** endptr)514 inline std::complex<long double> fp_parseLiteral<std::complex<long double> >
515 (const char* str, char** endptr)
516 {
517 return fp_parseComplexLiteral<long double> (str,endptr);
518 }
519 #endif
520
521 // -----------------------------------------------------------------------
522 // Hexadecimal floating point literal parsing
523 // -----------------------------------------------------------------------
testXdigit(unsigned c)524 inline int testXdigit(unsigned c)
525 {
526 if((c-'0') < 10u) return c&15; // 0..9
527 if(((c|0x20)-'a') < 6u) return 9+(c&15); // A..F or a..f
528 return -1; // Not a hex digit
529 }
530
531 template<typename elem_t, unsigned n_limbs, unsigned limb_bits>
addXdigit(elem_t * buffer,unsigned nibble)532 inline void addXdigit(elem_t* buffer, unsigned nibble)
533 {
534 for(unsigned p=0; p<n_limbs; ++p)
535 {
536 unsigned carry = unsigned( buffer[p] >> (elem_t)(limb_bits-4) );
537 buffer[p] = (buffer[p] << 4) | nibble;
538 nibble = carry;
539 }
540 }
541
542 template<typename Value_t>
parseHexLiteral(const char * str,char ** endptr)543 Value_t parseHexLiteral(const char* str, char** endptr)
544 {
545 const unsigned bits_per_char = 8;
546
547 const int MantissaBits =
548 std::numeric_limits<Value_t>::radix == 2
549 ? std::numeric_limits<Value_t>::digits
550 : (((sizeof(Value_t) * bits_per_char) &~ 3) - 4);
551
552 typedef unsigned long elem_t;
553 const int ExtraMantissaBits = 4 + ((MantissaBits+3)&~3); // Store one digit more for correct rounding
554 const unsigned limb_bits = sizeof(elem_t) * bits_per_char;
555 const unsigned n_limbs = (ExtraMantissaBits + limb_bits-1) / limb_bits;
556 elem_t mantissa_buffer[n_limbs] = { 0 };
557
558 int n_mantissa_bits = 0; // Track the number of bits
559 int exponent = 0; // The exponent that will be used to multiply the mantissa
560 // Read integer portion
561 while(true)
562 {
563 int xdigit = testXdigit(*str);
564 if(xdigit < 0) break;
565 addXdigit<elem_t,n_limbs,limb_bits> (mantissa_buffer, xdigit);
566 ++str;
567
568 n_mantissa_bits += 4;
569 if(n_mantissa_bits >= ExtraMantissaBits)
570 {
571 // Exhausted the precision. Parse the rest (until exponent)
572 // normally but ignore the actual digits.
573 for(; testXdigit(*str) >= 0; ++str)
574 exponent += 4;
575 // Read but ignore decimals
576 if(*str == '.')
577 for(++str; testXdigit(*str) >= 0; ++str)
578 {}
579 goto read_exponent;
580 }
581 }
582 // Read decimals
583 if(*str == '.')
584 for(++str; ; )
585 {
586 int xdigit = testXdigit(*str);
587 if(xdigit < 0) break;
588 addXdigit<elem_t,n_limbs,limb_bits> (mantissa_buffer, xdigit);
589 ++str;
590
591 exponent -= 4;
592 n_mantissa_bits += 4;
593 if(n_mantissa_bits >= ExtraMantissaBits)
594 {
595 // Exhausted the precision. Skip the rest
596 // of the decimals, until the exponent.
597 while(testXdigit(*str) >= 0)
598 ++str;
599 break;
600 }
601 }
602
603 // Read exponent
604 read_exponent:
605 if(*str == 'p' || *str == 'P')
606 {
607 const char* str2 = str+1;
608 long p_exponent = strtol(str2, const_cast<char**> (&str2), 10);
609 if(str2 != str+1 && p_exponent == (long)(int)p_exponent)
610 {
611 exponent += (int)p_exponent;
612 str = str2;
613 }
614 }
615
616 if(endptr) *endptr = const_cast<char*> (str);
617
618 Value_t result = std::ldexp(Value_t(mantissa_buffer[0]), exponent);
619 for(unsigned p=1; p<n_limbs; ++p)
620 {
621 exponent += limb_bits;
622 result += ldexp(Value_t(mantissa_buffer[p]), exponent);
623 }
624 return result;
625 }
626
627 #ifdef FP_SUPPORT_LONG_INT_TYPE
628 template<>
parseHexLiteral(const char * str,char ** endptr)629 long parseHexLiteral<long>(const char* str, char** endptr)
630 {
631 return std::strtol(str, endptr, 16);
632 }
633 #endif
634
635 #ifdef FP_SUPPORT_COMPLEX_DOUBLE_TYPE
636 template<>
637 std::complex<double>
parseHexLiteral(const char * str,char ** endptr)638 parseHexLiteral<std::complex<double> >(const char* str, char** endptr)
639 {
640 return parseHexLiteral<double> (str, endptr);
641 }
642 #endif
643
644 #ifdef FP_SUPPORT_COMPLEX_FLOAT_TYPE
645 template<>
646 std::complex<float>
parseHexLiteral(const char * str,char ** endptr)647 parseHexLiteral<std::complex<float> >(const char* str, char** endptr)
648 {
649 return parseHexLiteral<float> (str, endptr);
650 }
651 #endif
652
653 #ifdef FP_SUPPORT_COMPLEX_LONG_DOUBLE_TYPE
654 template<>
655 std::complex<long double>
parseHexLiteral(const char * str,char ** endptr)656 parseHexLiteral<std::complex<long double> >(const char* str, char** endptr)
657 {
658 return parseHexLiteral<long double> (str, endptr);
659 }
660 #endif
661 }
662
663 //=========================================================================
664 // Utility functions
665 //=========================================================================
666 namespace
667 {
668 // -----------------------------------------------------------------------
669 // Add a new identifier to the specified identifier map
670 // -----------------------------------------------------------------------
671 // Return value will be false if the name already existed
672 template<typename Value_t>
addNewNameData(NamePtrsMap<Value_t> & namePtrs,std::pair<NamePtr,NameData<Value_t>> & newName,bool isVar)673 bool addNewNameData(NamePtrsMap<Value_t>& namePtrs,
674 std::pair<NamePtr, NameData<Value_t> >& newName,
675 bool isVar)
676 {
677 typename NamePtrsMap<Value_t>::iterator nameIter =
678 namePtrs.lower_bound(newName.first);
679
680 if(nameIter != namePtrs.end() && newName.first == nameIter->first)
681 {
682 // redefining a var is not allowed.
683 if(isVar) return false;
684
685 // redefining other tokens is allowed, if the type stays the same.
686 if(nameIter->second.type != newName.second.type)
687 return false;
688
689 // update the data
690 nameIter->second = newName.second;
691 return true;
692 }
693
694 if(!isVar)
695 {
696 // Allocate a copy of the name (pointer stored in the map key)
697 // However, for VARIABLEs, the pointer points to VariableString,
698 // which is managed separately. Thusly, only done when !IsVar.
699 char* namebuf = new char[newName.first.nameLength];
700 memcpy(namebuf, newName.first.name, newName.first.nameLength);
701 newName.first.name = namebuf;
702 }
703
704 namePtrs.insert(nameIter, newName);
705 return true;
706 }
707 }
708
709
710 //=========================================================================
711 // Data struct implementation
712 //=========================================================================
713 template<typename Value_t>
Data()714 FunctionParserBase<Value_t>::Data::Data():
715 mReferenceCounter(1),
716 mDelimiterChar(0),
717 mParseErrorType(NO_FUNCTION_PARSED_YET),
718 mEvalErrorType(0),
719 mUseDegreeConversion(false),
720 mErrorLocation(0),
721 mVariablesAmount(0),
722 mStackSize(0)
723 {}
724
725 template<typename Value_t>
Data(const Data & rhs)726 FunctionParserBase<Value_t>::Data::Data(const Data& rhs):
727 mReferenceCounter(0),
728 mDelimiterChar(rhs.mDelimiterChar),
729 mParseErrorType(rhs.mParseErrorType),
730 mEvalErrorType(rhs.mEvalErrorType),
731 mUseDegreeConversion(rhs.mUseDegreeConversion),
732 mErrorLocation(rhs.mErrorLocation),
733 mVariablesAmount(rhs.mVariablesAmount),
734 mVariablesString(rhs.mVariablesString),
735 mNamePtrs(),
736 mFuncPtrs(rhs.mFuncPtrs),
737 mFuncParsers(rhs.mFuncParsers),
738 mByteCode(rhs.mByteCode),
739 mImmed(rhs.mImmed),
740 #ifndef FP_USE_THREAD_SAFE_EVAL
741 mStack(rhs.mStackSize),
742 #endif
743 mStackSize(rhs.mStackSize)
744 {
745 for(typename NamePtrsMap<Value_t>::const_iterator i = rhs.mNamePtrs.begin();
746 i != rhs.mNamePtrs.end();
747 ++i)
748 {
749 if(i->second.type == NameData<Value_t>::VARIABLE)
750 {
751 const std::size_t variableStringOffset =
752 i->first.name - rhs.mVariablesString.c_str();
753 std::pair<NamePtr, NameData<Value_t> > tmp
754 (NamePtr(&mVariablesString[variableStringOffset],
755 i->first.nameLength),
756 i->second);
757 mNamePtrs.insert(mNamePtrs.end(), tmp);
758 }
759 else
760 {
761 std::pair<NamePtr, NameData<Value_t> > tmp
762 (NamePtr(new char[i->first.nameLength], i->first.nameLength),
763 i->second );
764 memcpy(const_cast<char*>(tmp.first.name), i->first.name,
765 tmp.first.nameLength);
766 mNamePtrs.insert(mNamePtrs.end(), tmp);
767 }
768 }
769 }
770
771 template<typename Value_t>
~Data()772 FunctionParserBase<Value_t>::Data::~Data()
773 {
774 for(typename NamePtrsMap<Value_t>::iterator i = mNamePtrs.begin();
775 i != mNamePtrs.end();
776 ++i)
777 {
778 if(i->second.type != NameData<Value_t>::VARIABLE)
779 delete[] i->first.name;
780 }
781 }
782
783 template<typename Value_t>
incFuncWrapperRefCount(FunctionWrapper * wrapper)784 void FunctionParserBase<Value_t>::incFuncWrapperRefCount
785 (FunctionWrapper* wrapper)
786 {
787 ++wrapper->mReferenceCount;
788 }
789
790 template<typename Value_t>
decFuncWrapperRefCount(FunctionWrapper * wrapper)791 unsigned FunctionParserBase<Value_t>::decFuncWrapperRefCount
792 (FunctionWrapper* wrapper)
793 {
794 return --wrapper->mReferenceCount;
795 }
796
797 template<typename Value_t>
FuncWrapperPtrData()798 FunctionParserBase<Value_t>::Data::FuncWrapperPtrData::FuncWrapperPtrData():
799 mRawFuncPtr(0), mFuncWrapperPtr(0), mParams(0)
800 {}
801
802 template<typename Value_t>
~FuncWrapperPtrData()803 FunctionParserBase<Value_t>::Data::FuncWrapperPtrData::~FuncWrapperPtrData()
804 {
805 if(mFuncWrapperPtr &&
806 FunctionParserBase::decFuncWrapperRefCount(mFuncWrapperPtr) == 0)
807 delete mFuncWrapperPtr;
808 }
809
810 template<typename Value_t>
FuncWrapperPtrData(const FuncWrapperPtrData & rhs)811 FunctionParserBase<Value_t>::Data::FuncWrapperPtrData::FuncWrapperPtrData
812 (const FuncWrapperPtrData& rhs):
813 mRawFuncPtr(rhs.mRawFuncPtr),
814 mFuncWrapperPtr(rhs.mFuncWrapperPtr),
815 mParams(rhs.mParams)
816 {
817 if(mFuncWrapperPtr)
818 FunctionParserBase::incFuncWrapperRefCount(mFuncWrapperPtr);
819 }
820
821 template<typename Value_t>
822 typename FunctionParserBase<Value_t>::Data::FuncWrapperPtrData&
operator =(const FuncWrapperPtrData & rhs)823 FunctionParserBase<Value_t>::Data::FuncWrapperPtrData::operator=
824 (const FuncWrapperPtrData& rhs)
825 {
826 if(&rhs != this)
827 {
828 if(mFuncWrapperPtr &&
829 FunctionParserBase::decFuncWrapperRefCount(mFuncWrapperPtr) == 0)
830 delete mFuncWrapperPtr;
831 mRawFuncPtr = rhs.mRawFuncPtr;
832 mFuncWrapperPtr = rhs.mFuncWrapperPtr;
833 mParams = rhs.mParams;
834 if(mFuncWrapperPtr)
835 FunctionParserBase::incFuncWrapperRefCount(mFuncWrapperPtr);
836 }
837 return *this;
838 }
839
840
841 //=========================================================================
842 // FunctionParser constructors, destructor and assignment
843 //=========================================================================
844 template<typename Value_t>
FunctionParserBase()845 FunctionParserBase<Value_t>::FunctionParserBase():
846 mData(new Data),
847 mStackPtr(0)
848 {
849 }
850
851 template<typename Value_t>
~FunctionParserBase()852 FunctionParserBase<Value_t>::~FunctionParserBase()
853 {
854 if(--(mData->mReferenceCounter) == 0)
855 delete mData;
856 }
857
858 template<typename Value_t>
FunctionParserBase(const FunctionParserBase & cpy)859 FunctionParserBase<Value_t>::FunctionParserBase(const FunctionParserBase& cpy):
860 mData(cpy.mData),
861 mStackPtr(0)
862 {
863 ++(mData->mReferenceCounter);
864 }
865
866 template<typename Value_t>
867 FunctionParserBase<Value_t>&
operator =(const FunctionParserBase & cpy)868 FunctionParserBase<Value_t>::operator=(const FunctionParserBase& cpy)
869 {
870 if(mData != cpy.mData)
871 {
872 if(--(mData->mReferenceCounter) == 0) delete mData;
873
874 mData = cpy.mData;
875 ++(mData->mReferenceCounter);
876 }
877 return *this;
878 }
879
880 template<typename Value_t>
881 typename FunctionParserBase<Value_t>::Data*
getParserData()882 FunctionParserBase<Value_t>::getParserData()
883 {
884 return mData;
885 }
886
887 template<typename Value_t>
setDelimiterChar(char c)888 void FunctionParserBase<Value_t>::setDelimiterChar(char c)
889 {
890 mData->mDelimiterChar = c;
891 }
892
893
894 //---------------------------------------------------------------------------
895 // Copy-on-write method
896 //---------------------------------------------------------------------------
897 template<typename Value_t>
CopyOnWrite()898 void FunctionParserBase<Value_t>::CopyOnWrite()
899 {
900 if(mData->mReferenceCounter > 1)
901 {
902 Data* oldData = mData;
903 mData = new Data(*oldData);
904 --(oldData->mReferenceCounter);
905 mData->mReferenceCounter = 1;
906 }
907 }
908
909 template<typename Value_t>
ForceDeepCopy()910 void FunctionParserBase<Value_t>::ForceDeepCopy()
911 {
912 CopyOnWrite();
913 }
914
915
916 //=========================================================================
917 // Epsilon
918 //=========================================================================
919 template<typename Value_t>
epsilon()920 Value_t FunctionParserBase<Value_t>::epsilon()
921 {
922 return Epsilon<Value_t>::value;
923 }
924
925 template<typename Value_t>
setEpsilon(Value_t value)926 void FunctionParserBase<Value_t>::setEpsilon(Value_t value)
927 {
928 Epsilon<Value_t>::value = value;
929 }
930
931
932 //=========================================================================
933 // User-defined identifier addition functions
934 //=========================================================================
935 template<typename Value_t>
AddConstant(const std::string & name,Value_t value)936 bool FunctionParserBase<Value_t>::AddConstant(const std::string& name,
937 Value_t value)
938 {
939 if(!containsOnlyValidIdentifierChars<Value_t>(name)) return false;
940
941 CopyOnWrite();
942 std::pair<NamePtr, NameData<Value_t> > newName
943 (NamePtr(name.data(), unsigned(name.size())),
944 NameData<Value_t>(NameData<Value_t>::CONSTANT, value));
945
946 return addNewNameData(mData->mNamePtrs, newName, false);
947 }
948
949 template<typename Value_t>
AddUnit(const std::string & name,Value_t value)950 bool FunctionParserBase<Value_t>::AddUnit(const std::string& name,
951 Value_t value)
952 {
953 if(!containsOnlyValidIdentifierChars<Value_t>(name)) return false;
954
955 CopyOnWrite();
956 std::pair<NamePtr, NameData<Value_t> > newName
957 (NamePtr(name.data(), unsigned(name.size())),
958 NameData<Value_t>(NameData<Value_t>::UNIT, value));
959 return addNewNameData(mData->mNamePtrs, newName, false);
960 }
961
962 template<typename Value_t>
AddFunction(const std::string & name,FunctionPtr ptr,unsigned paramsAmount)963 bool FunctionParserBase<Value_t>::AddFunction
964 (const std::string& name, FunctionPtr ptr, unsigned paramsAmount)
965 {
966 if(!containsOnlyValidIdentifierChars<Value_t>(name)) return false;
967
968 CopyOnWrite();
969 std::pair<NamePtr, NameData<Value_t> > newName
970 (NamePtr(name.data(), unsigned(name.size())),
971 NameData<Value_t>(NameData<Value_t>::FUNC_PTR,
972 unsigned(mData->mFuncPtrs.size())));
973
974 const bool success = addNewNameData(mData->mNamePtrs, newName, false);
975 if(success)
976 {
977 mData->mFuncPtrs.push_back(typename Data::FuncWrapperPtrData());
978 mData->mFuncPtrs.back().mRawFuncPtr = ptr;
979 mData->mFuncPtrs.back().mParams = paramsAmount;
980 }
981 return success;
982 }
983
984 template<typename Value_t>
addFunctionWrapperPtr(const std::string & name,FunctionWrapper * wrapper,unsigned paramsAmount)985 bool FunctionParserBase<Value_t>::addFunctionWrapperPtr
986 (const std::string& name, FunctionWrapper* wrapper, unsigned paramsAmount)
987 {
988 if(!AddFunction(name, FunctionPtr(0), paramsAmount)) return false;
989 mData->mFuncPtrs.back().mFuncWrapperPtr = wrapper;
990 return true;
991 }
992
993 template<typename Value_t>
994 typename FunctionParserBase<Value_t>::FunctionWrapper*
GetFunctionWrapper(const std::string & name)995 FunctionParserBase<Value_t>::GetFunctionWrapper(const std::string& name)
996 {
997 CopyOnWrite();
998 NamePtr namePtr(name.data(), unsigned(name.size()));
999
1000 typename NamePtrsMap<Value_t>::iterator nameIter =
1001 mData->mNamePtrs.find(namePtr);
1002
1003 if(nameIter != mData->mNamePtrs.end() &&
1004 nameIter->second.type == NameData<Value_t>::FUNC_PTR)
1005 {
1006 return mData->mFuncPtrs[nameIter->second.index].mFuncWrapperPtr;
1007 }
1008 return 0;
1009 }
1010
1011 template<typename Value_t>
CheckRecursiveLinking(const FunctionParserBase * fp) const1012 bool FunctionParserBase<Value_t>::CheckRecursiveLinking
1013 (const FunctionParserBase* fp) const
1014 {
1015 if(fp == this) return true;
1016 for(unsigned i = 0; i < fp->mData->mFuncParsers.size(); ++i)
1017 if(CheckRecursiveLinking(fp->mData->mFuncParsers[i].mParserPtr))
1018 return true;
1019 return false;
1020 }
1021
1022 template<typename Value_t>
AddFunction(const std::string & name,FunctionParserBase & fp)1023 bool FunctionParserBase<Value_t>::AddFunction(const std::string& name,
1024 FunctionParserBase& fp)
1025 {
1026 if(!containsOnlyValidIdentifierChars<Value_t>(name) ||
1027 CheckRecursiveLinking(&fp))
1028 return false;
1029
1030 CopyOnWrite();
1031 std::pair<NamePtr, NameData<Value_t> > newName
1032 (NamePtr(name.data(), unsigned(name.size())),
1033 NameData<Value_t>(NameData<Value_t>::PARSER_PTR,
1034 unsigned(mData->mFuncParsers.size())));
1035
1036 const bool success = addNewNameData(mData->mNamePtrs, newName, false);
1037 if(success)
1038 {
1039 mData->mFuncParsers.push_back(typename Data::FuncParserPtrData());
1040 mData->mFuncParsers.back().mParserPtr = &fp;
1041 mData->mFuncParsers.back().mParams = fp.mData->mVariablesAmount;
1042 }
1043 return success;
1044 }
1045
1046 template<typename Value_t>
RemoveIdentifier(const std::string & name)1047 bool FunctionParserBase<Value_t>::RemoveIdentifier(const std::string& name)
1048 {
1049 CopyOnWrite();
1050
1051 NamePtr namePtr(name.data(), unsigned(name.size()));
1052
1053 typename NamePtrsMap<Value_t>::iterator nameIter =
1054 mData->mNamePtrs.find(namePtr);
1055
1056 if(nameIter != mData->mNamePtrs.end())
1057 {
1058 if(nameIter->second.type == NameData<Value_t>::VARIABLE)
1059 {
1060 // Illegal attempt to delete variables
1061 return false;
1062 }
1063 delete[] nameIter->first.name;
1064 mData->mNamePtrs.erase(nameIter);
1065 return true;
1066 }
1067 return false;
1068 }
1069
1070
1071 //=========================================================================
1072 // Function parsing
1073 //=========================================================================
1074 namespace
1075 {
1076 // Error messages returned by ErrorMsg():
1077 const char* const ParseErrorMessage[]=
1078 {
1079 "Syntax error", // 0
1080 "Mismatched parenthesis", // 1
1081 "Missing ')'", // 2
1082 "Empty parentheses", // 3
1083 "Syntax error: Operator expected", // 4
1084 "Not enough memory", // 5
1085 "An unexpected error occurred. Please make a full bug report "
1086 "to the author", // 6
1087 "Syntax error in parameter 'Vars' given to "
1088 "FunctionParser::Parse()", // 7
1089 "Illegal number of parameters to function", // 8
1090 "Syntax error: Premature end of string", // 9
1091 "Syntax error: Expecting ( after function", // 10
1092 "Syntax error: Unknown identifier", // 11
1093 "(No function has been parsed yet)",
1094 ""
1095 };
1096
1097 template<typename Value_t>
1098 inline typename FunctionParserBase<Value_t>::ParseErrorType
noCommaError(char c)1099 noCommaError(char c)
1100 {
1101 return c == ')' ?
1102 FunctionParserBase<Value_t>::ILL_PARAMS_AMOUNT :
1103 FunctionParserBase<Value_t>::SYNTAX_ERROR;
1104 }
1105
1106 template<typename Value_t>
1107 inline typename FunctionParserBase<Value_t>::ParseErrorType
noParenthError(char c)1108 noParenthError(char c)
1109 {
1110 return c == ',' ?
1111 FunctionParserBase<Value_t>::ILL_PARAMS_AMOUNT :
1112 FunctionParserBase<Value_t>::MISSING_PARENTH;
1113 }
1114
1115 template<unsigned offset>
1116 struct IntLiteralMask
1117 {
1118 enum { mask =
1119 // ( 1UL << ('-'-offset)) |
1120 (0x3FFUL << ('0'-offset)) }; /* 0x3FF = 10 bits worth "1" */
1121 // Note: If you change fparser to support negative numbers parsing
1122 // (as opposed to parsing them as cNeg followed by literal),
1123 // enable the '-' line above, and change the offset value
1124 // in BeginsLiteral() to '-' instead of '.'.
1125 };
1126
1127 template<typename Value_t, unsigned offset>
1128 struct LiteralMask
1129 {
1130 enum { mask =
1131 ( 1UL << ('.'-offset)) |
1132 IntLiteralMask<offset>::mask };
1133 };
1134 #ifdef FP_SUPPORT_LONG_INT_TYPE
1135 template<unsigned offset>
1136 struct LiteralMask<long, offset>: public IntLiteralMask<offset>
1137 {
1138 };
1139 #endif
1140 #ifdef FP_SUPPORT_GMP_INT_TYPE
1141 template<unsigned offset>
1142 struct LiteralMask<GmpInt, offset>: public IntLiteralMask<offset>
1143 {
1144 };
1145 #endif
1146
1147 template<unsigned offset>
1148 struct SimpleSpaceMask
1149 {
1150 enum { mask =
1151 (1UL << ('\r'-offset)) |
1152 (1UL << ('\n'-offset)) |
1153 (1UL << ('\v'-offset)) |
1154 (1UL << ('\t'-offset)) |
1155 (1UL << (' ' -offset)) };
1156 };
1157
1158 template<typename Value_t>
BeginsLiteral(unsigned byte)1159 inline bool BeginsLiteral(unsigned byte)
1160 {
1161 enum { n = sizeof(unsigned long)>=8 ? 0 : '.' };
1162 byte -= n;
1163 if(byte > (unsigned char)('9'-n)) return false;
1164 unsigned long shifted = 1UL << byte;
1165 const unsigned long mask = LiteralMask<Value_t, n>::mask;
1166 return (mask & shifted) != 0;
1167 }
1168
1169 template<typename CharPtr>
SkipSpace(CharPtr & function)1170 inline void SkipSpace(CharPtr& function)
1171 {
1172 /*
1173 Space characters in unicode:
1174 U+0020 SPACE Depends on font, often adjusted (see below)
1175 U+00A0 NO-BREAK SPACE As a space, but often not adjusted
1176 U+2000 EN QUAD 1 en (= 1/2 em)
1177 U+2001 EM QUAD 1 em (nominally, the height of the font)
1178 U+2002 EN SPACE 1 en (= 1/2 em)
1179 U+2003 EM SPACE 1 em
1180 U+2004 THREE-PER-EM SPACE 1/3 em
1181 U+2005 FOUR-PER-EM SPACE 1/4 em
1182 U+2006 SIX-PER-EM SPACE 1/6 em
1183 U+2007 FIGURE SPACE Tabular width, the width of digits
1184 U+2008 PUNCTUATION SPACE The width of a period .
1185 U+2009 THIN SPACE 1/5 em (or sometimes 1/6 em)
1186 U+200A HAIR SPACE Narrower than THIN SPACE
1187 U+200B ZERO WIDTH SPACE Nominally no width, but may expand
1188 U+202F NARROW NO-BREAK SPACE Narrower than NO-BREAK SPACE (or SPACE)
1189 U+205F MEDIUM MATHEMATICAL SPACE 4/18 em
1190 U+3000 IDEOGRAPHIC SPACE The width of ideographic (CJK) characters.
1191 Also:
1192 U+000A \n
1193 U+000D \r
1194 U+0009 \t
1195 U+000B \v
1196 As UTF-8 sequences:
1197 09
1198 0A
1199 0B
1200 0D
1201 20
1202 C2 A0
1203 E2 80 80-8B
1204 E2 80 AF
1205 E2 81 9F
1206 E3 80 80
1207 */
1208 while(true)
1209 {
1210 enum { n = sizeof(unsigned long)>=8 ? 0 : '\t' };
1211 typedef signed char schar;
1212 unsigned byte = (unsigned char)*function;
1213 byte -= n;
1214 // ^Note: values smaller than n intentionally become
1215 // big values here due to integer wrap. The
1216 // comparison below thus excludes them, making
1217 // the effective range 0x09..0x20 (32-bit)
1218 // or 0x00..0x20 (64-bit) within the if-clause.
1219 if(byte <= (unsigned char)(' '-n))
1220 {
1221 unsigned long shifted = 1UL << byte;
1222 const unsigned long mask = SimpleSpaceMask<n>::mask;
1223 if(mask & shifted)
1224 { ++function; continue; } // \r, \n, \t, \v and space
1225 break;
1226 }
1227 if(likely(byte < 0xC2-n)) break;
1228
1229 if(byte == 0xC2-n && function[1] == char(0xA0))
1230 { function += 2; continue; } // U+00A0
1231 if(byte == 0xE3-n &&
1232 function[1] == char(0x80) && function[2] == char(0x80))
1233 { function += 3; continue; } // U+3000
1234 if(byte == 0xE2-n)
1235 {
1236 if(function[1] == char(0x81))
1237 {
1238 if(function[2] != char(0x9F)) break;
1239 function += 3; // U+205F
1240 continue;
1241 }
1242 if(function[1] == char(0x80))
1243 if(function[2] == char(0xAF) || // U+202F
1244 schar(function[2]) <= schar(0x8B) // U+2000..U+200B
1245 )
1246 {
1247 function += 3;
1248 continue;
1249 }
1250 }
1251 break;
1252 } // while(true)
1253 } // SkipSpace(CharPtr& function)
1254 }
1255
1256 // ---------------------------------------------------------------------------
1257 // Return parse error message
1258 // ---------------------------------------------------------------------------
1259 template<typename Value_t>
ErrorMsg() const1260 const char* FunctionParserBase<Value_t>::ErrorMsg() const
1261 {
1262 return ParseErrorMessage[mData->mParseErrorType];
1263 }
1264
1265 template<typename Value_t>
1266 typename FunctionParserBase<Value_t>::ParseErrorType
GetParseErrorType() const1267 FunctionParserBase<Value_t>::GetParseErrorType() const
1268 {
1269 return mData->mParseErrorType;
1270 }
1271
1272 template<typename Value_t>
EvalError() const1273 int FunctionParserBase<Value_t>::EvalError() const
1274 {
1275 return mData->mEvalErrorType;
1276 }
1277
1278
1279 // ---------------------------------------------------------------------------
1280 // Parse variables
1281 // ---------------------------------------------------------------------------
1282 template<typename Value_t>
ParseVariables(const std::string & inputVarString)1283 bool FunctionParserBase<Value_t>::ParseVariables
1284 (const std::string& inputVarString)
1285 {
1286 if(mData->mVariablesString == inputVarString) return true;
1287
1288 /* Delete existing variables from mNamePtrs */
1289 for(typename NamePtrsMap<Value_t>::iterator i =
1290 mData->mNamePtrs.begin();
1291 i != mData->mNamePtrs.end(); )
1292 {
1293 if(i->second.type == NameData<Value_t>::VARIABLE)
1294 {
1295 typename NamePtrsMap<Value_t>::iterator j (i);
1296 ++i;
1297 mData->mNamePtrs.erase(j);
1298 }
1299 else ++i;
1300 }
1301 mData->mVariablesString = inputVarString;
1302
1303 const std::string& vars = mData->mVariablesString;
1304 const unsigned len = unsigned(vars.size());
1305
1306 unsigned varNumber = VarBegin;
1307
1308 const char* beginPtr = vars.c_str();
1309 const char* finalPtr = beginPtr + len;
1310 while(beginPtr < finalPtr)
1311 {
1312 SkipSpace(beginPtr);
1313 unsigned nameLength = readIdentifier<Value_t>(beginPtr);
1314 if(nameLength == 0 || (nameLength & 0x80000000U)) return false;
1315 const char* endPtr = beginPtr + nameLength;
1316 SkipSpace(endPtr);
1317 if(endPtr != finalPtr && *endPtr != ',') return false;
1318
1319 std::pair<NamePtr, NameData<Value_t> > newName
1320 (NamePtr(beginPtr, nameLength),
1321 NameData<Value_t>(NameData<Value_t>::VARIABLE, varNumber++));
1322
1323 if(!addNewNameData(mData->mNamePtrs, newName, true))
1324 {
1325 return false;
1326 }
1327
1328 beginPtr = endPtr + 1;
1329 }
1330
1331 mData->mVariablesAmount = varNumber - VarBegin;
1332 return true;
1333 }
1334
1335 // ---------------------------------------------------------------------------
1336 // Parse() public interface functions
1337 // ---------------------------------------------------------------------------
1338 template<typename Value_t>
Parse(const char * Function,const std::string & Vars,bool useDegrees)1339 int FunctionParserBase<Value_t>::Parse(const char* Function,
1340 const std::string& Vars,
1341 bool useDegrees)
1342 {
1343 CopyOnWrite();
1344
1345 if(!ParseVariables(Vars))
1346 {
1347 mData->mParseErrorType = INVALID_VARS;
1348 return int(strlen(Function));
1349 }
1350
1351 return ParseFunction(Function, useDegrees);
1352 }
1353
1354 template<typename Value_t>
Parse(const std::string & Function,const std::string & Vars,bool useDegrees)1355 int FunctionParserBase<Value_t>::Parse(const std::string& Function,
1356 const std::string& Vars,
1357 bool useDegrees)
1358 {
1359 CopyOnWrite();
1360
1361 if(!ParseVariables(Vars))
1362 {
1363 mData->mParseErrorType = INVALID_VARS;
1364 return int(Function.size());
1365 }
1366
1367 return ParseFunction(Function.c_str(), useDegrees);
1368 }
1369
1370
1371 // ---------------------------------------------------------------------------
1372 // Main parsing function
1373 // ---------------------------------------------------------------------------
1374 template<typename Value_t>
ParseFunction(const char * function,bool useDegrees)1375 int FunctionParserBase<Value_t>::ParseFunction(const char* function,
1376 bool useDegrees)
1377 {
1378 mData->mUseDegreeConversion = useDegrees;
1379 mData->mParseErrorType = FP_NO_ERROR;
1380
1381 mData->mInlineVarNames.clear();
1382 mData->mByteCode.clear(); mData->mByteCode.reserve(128);
1383 mData->mImmed.clear(); mData->mImmed.reserve(128);
1384 mData->mStackSize = mStackPtr = 0;
1385
1386 mData->mHasByteCodeFlags = false;
1387
1388 const char* ptr = Compile(function);
1389 mData->mInlineVarNames.clear();
1390
1391 if(mData->mHasByteCodeFlags)
1392 {
1393 for(unsigned i = unsigned(mData->mByteCode.size()); i-- > 0; )
1394 mData->mByteCode[i] &= ~FP_ParamGuardMask;
1395 }
1396
1397 if(mData->mParseErrorType != FP_NO_ERROR)
1398 return int(mData->mErrorLocation - function);
1399
1400 assert(ptr); // Should never be null at this point. It's a bug otherwise.
1401 if(*ptr)
1402 {
1403 if(mData->mDelimiterChar == 0 || *ptr != mData->mDelimiterChar)
1404 mData->mParseErrorType = EXPECT_OPERATOR;
1405 return int(ptr - function);
1406 }
1407
1408 #ifndef FP_USE_THREAD_SAFE_EVAL
1409 mData->mStack.resize(mData->mStackSize);
1410 #endif
1411
1412 return -1;
1413 }
1414
1415
1416 //=========================================================================
1417 // Parsing and bytecode compiling functions
1418 //=========================================================================
1419 template<typename Value_t>
SetErrorType(ParseErrorType t,const char * pos)1420 inline const char* FunctionParserBase<Value_t>::SetErrorType(ParseErrorType t,
1421 const char* pos)
1422 {
1423 mData->mParseErrorType = t;
1424 mData->mErrorLocation = pos;
1425 return 0;
1426 }
1427
1428 template<typename Value_t>
incStackPtr()1429 inline void FunctionParserBase<Value_t>::incStackPtr()
1430 {
1431 if(++mStackPtr > mData->mStackSize) ++(mData->mStackSize);
1432 }
1433
1434 namespace
1435 {
1436 const unsigned char powi_factor_table[128] =
1437 {
1438 0,1,0,0,0,0,0,0, 0, 0,0,0,0,0,0,3,/* 0 - 15 */
1439 0,0,0,0,0,0,0,0, 0, 5,0,3,0,0,3,0,/* 16 - 31 */
1440 0,0,0,0,0,0,0,3, 0, 0,0,0,0,5,0,0,/* 32 - 47 */
1441 0,0,5,3,0,0,3,5, 0, 3,0,0,3,0,0,3,/* 48 - 63 */
1442 0,0,0,0,0,0,0,0, 0, 0,0,3,0,0,3,0,/* 64 - 79 */
1443 0,9,0,0,0,5,0,3, 0, 0,5,7,0,0,0,5,/* 80 - 95 */
1444 0,0,0,3,5,0,3,0, 0, 3,0,0,3,0,5,3,/* 96 - 111 */
1445 0,0,3,5,0,9,0,7, 3,11,0,3,0,5,3,0,/* 112 - 127 */
1446 };
1447
get_powi_factor(long abs_int_exponent)1448 inline int get_powi_factor(long abs_int_exponent)
1449 {
1450 if(abs_int_exponent >= int(sizeof(powi_factor_table))) return 0;
1451 return powi_factor_table[abs_int_exponent];
1452 }
1453
1454 #if 0
1455 int EstimatePowiComplexity(int abs_int_exponent)
1456 {
1457 int cost = 0;
1458 while(abs_int_exponent > 1)
1459 {
1460 int factor = get_powi_factor(abs_int_exponent);
1461 if(factor)
1462 {
1463 cost += EstimatePowiComplexity(factor);
1464 abs_int_exponent /= factor;
1465 continue;
1466 }
1467 if(!(abs_int_exponent & 1))
1468 {
1469 abs_int_exponent /= 2;
1470 cost += 3; // sqr
1471 }
1472 else
1473 {
1474 cost += 4; // dup+mul
1475 abs_int_exponent -= 1;
1476 }
1477 }
1478 return cost;
1479 }
1480 #endif
1481
IsEligibleIntPowiExponent(long int_exponent)1482 bool IsEligibleIntPowiExponent(long int_exponent)
1483 {
1484 if(int_exponent == 0) return false;
1485 long abs_int_exponent = int_exponent;
1486 #if 0
1487 int cost = 0;
1488
1489 if(abs_int_exponent < 0)
1490 {
1491 cost += 11;
1492 abs_int_exponent = -abs_int_exponent;
1493 }
1494
1495 cost += EstimatePowiComplexity(abs_int_exponent);
1496
1497 return cost < (10*3 + 4*4);
1498 #else
1499 if(abs_int_exponent < 0) abs_int_exponent = -abs_int_exponent;
1500
1501 return (abs_int_exponent >= 1)
1502 && (abs_int_exponent <= 46 ||
1503 (abs_int_exponent <= 1024 &&
1504 (abs_int_exponent & (abs_int_exponent - 1)) == 0));
1505 #endif
1506 }
1507
1508 /* Needed by fp_opcode_add.inc if tracing is enabled */
1509 template<typename Value_t>
findName(const NamePtrsMap<Value_t> & nameMap,unsigned index,typename NameData<Value_t>::DataType type)1510 std::string findName(const NamePtrsMap<Value_t>& nameMap,
1511 unsigned index,
1512 typename NameData<Value_t>::DataType type)
1513 {
1514 for(typename NamePtrsMap<Value_t>::const_iterator
1515 iter = nameMap.begin();
1516 iter != nameMap.end();
1517 ++iter)
1518 {
1519 if(iter->second.type == type && iter->second.index == index)
1520 return std::string(iter->first.name,
1521 iter->first.name + iter->first.nameLength);
1522 }
1523 return "?";
1524 }
1525 }
1526
1527 template<typename Value_t>
AddImmedOpcode(Value_t value)1528 inline void FunctionParserBase<Value_t>::AddImmedOpcode(Value_t value)
1529 {
1530 mData->mImmed.push_back(value);
1531 mData->mByteCode.push_back(cImmed);
1532 }
1533
1534 template<typename Value_t>
CompilePowi(long abs_int_exponent)1535 inline void FunctionParserBase<Value_t>::CompilePowi(long abs_int_exponent)
1536 {
1537 int num_muls=0;
1538 while(abs_int_exponent > 1)
1539 {
1540 long factor = get_powi_factor(abs_int_exponent);
1541 if(factor)
1542 {
1543 CompilePowi(factor);
1544 abs_int_exponent /= factor;
1545 continue;
1546 }
1547 if(!(abs_int_exponent & 1))
1548 {
1549 abs_int_exponent /= 2;
1550 mData->mByteCode.push_back(cSqr);
1551 // ^ Don't put AddFunctionOpcode here,
1552 // it would slow down a great deal.
1553 }
1554 else
1555 {
1556 mData->mByteCode.push_back(cDup);
1557 incStackPtr();
1558 abs_int_exponent -= 1;
1559 ++num_muls;
1560 }
1561 }
1562 if(num_muls > 0)
1563 {
1564 mData->mByteCode.resize(mData->mByteCode.size()+num_muls, cMul);
1565 mStackPtr -= num_muls;
1566 }
1567 }
1568
1569 template<typename Value_t>
TryCompilePowi(Value_t original_immed)1570 inline bool FunctionParserBase<Value_t>::TryCompilePowi(Value_t original_immed)
1571 {
1572 Value_t changed_immed = original_immed;
1573 for(int sqrt_count=0; /**/; ++sqrt_count)
1574 {
1575 long int_exponent = makeLongInteger(changed_immed);
1576 if(isLongInteger(changed_immed) &&
1577 IsEligibleIntPowiExponent(int_exponent))
1578 {
1579 long abs_int_exponent = int_exponent;
1580 if(abs_int_exponent < 0)
1581 abs_int_exponent = -abs_int_exponent;
1582
1583 mData->mImmed.pop_back(); mData->mByteCode.pop_back();
1584 --mStackPtr;
1585 // ^Though the above is accounted for by the procedure
1586 // that generates cPow, we need it for correct cFetch
1587 // indexes in CompilePowi().
1588
1589 while(sqrt_count > 0)
1590 {
1591 int opcode = cSqrt;
1592 if(sqrt_count == 1 && int_exponent < 0)
1593 {
1594 opcode = cRSqrt;
1595 int_exponent = -int_exponent;
1596 }
1597 mData->mByteCode.push_back(opcode);
1598 --sqrt_count;
1599 }
1600 if((abs_int_exponent & 1) == 0)
1601 {
1602 // This special rule fixes the optimization
1603 // shortcoming of (-x)^2 with minimal overhead.
1604 AddFunctionOpcode(cSqr);
1605 abs_int_exponent >>= 1;
1606 }
1607 CompilePowi(abs_int_exponent);
1608 if(int_exponent < 0) mData->mByteCode.push_back(cInv);
1609 ++mStackPtr; // Needed because cPow adding will assume this.
1610 return true;
1611 }
1612 if(sqrt_count >= 4) break;
1613 changed_immed += changed_immed;
1614 }
1615
1616 // When we don't know whether x >= 0, we still know that
1617 // x^y can be safely converted into exp(y * log(x))
1618 // when y is _not_ integer, because we know that x >= 0.
1619 // Otherwise either expression will give a NaN.
1620 if(/*!isInteger(original_immed) ||*/
1621 IsNeverNegativeValueOpcode(mData->mByteCode[mData->mByteCode.size()-2]))
1622 {
1623 mData->mImmed.pop_back();
1624 mData->mByteCode.pop_back();
1625 //--mStackPtr; - accounted for by the procedure that generates cPow
1626 AddFunctionOpcode(cLog);
1627 AddImmedOpcode(original_immed);
1628 //incStackPtr(); - this and the next are redundant because...
1629 AddFunctionOpcode(cMul);
1630 //--mStackPtr; - ...because the cImmed was popped earlier.
1631 AddFunctionOpcode(cExp);
1632 return true;
1633 }
1634 return false;
1635 }
1636
1637 //#include "fpoptimizer/opcodename.hh"
1638 // ^ needed only if FP_TRACE_BYTECODE_OPTIMIZATION() is used
1639
1640 template<typename Value_t>
AddFunctionOpcode(unsigned opcode)1641 inline void FunctionParserBase<Value_t>::AddFunctionOpcode(unsigned opcode)
1642 {
1643 #define FP_FLOAT_VERSION 1
1644 #define FP_COMPLEX_VERSION 0
1645 #include "extrasrc/fp_opcode_add.inc"
1646 #undef FP_COMPLEX_VERSION
1647 #undef FP_FLOAT_VERSION
1648 }
1649
1650 #ifdef FP_SUPPORT_LONG_INT_TYPE
1651 template<>
AddFunctionOpcode(unsigned opcode)1652 inline void FunctionParserBase<long>::AddFunctionOpcode(unsigned opcode)
1653 {
1654 typedef long Value_t;
1655 #define FP_FLOAT_VERSION 0
1656 #define FP_COMPLEX_VERSION 0
1657 #include "extrasrc/fp_opcode_add.inc"
1658 #undef FP_COMPLEX_VERSION
1659 #undef FP_FLOAT_VERSION
1660 }
1661 #endif
1662
1663 #ifdef FP_SUPPORT_GMP_INT_TYPE
1664 template<>
AddFunctionOpcode(unsigned opcode)1665 inline void FunctionParserBase<GmpInt>::AddFunctionOpcode(unsigned opcode)
1666 {
1667 typedef GmpInt Value_t;
1668 #define FP_FLOAT_VERSION 0
1669 #define FP_COMPLEX_VERSION 0
1670 #include "extrasrc/fp_opcode_add.inc"
1671 #undef FP_COMPLEX_VERSION
1672 #undef FP_FLOAT_VERSION
1673 }
1674 #endif
1675
1676 #ifdef FP_SUPPORT_COMPLEX_DOUBLE_TYPE
1677 template<>
AddFunctionOpcode(unsigned opcode)1678 inline void FunctionParserBase<std::complex<double> >::AddFunctionOpcode(unsigned opcode)
1679 {
1680 typedef std::complex<double> Value_t;
1681 #define FP_FLOAT_VERSION 1
1682 #define FP_COMPLEX_VERSION 1
1683 #include "extrasrc/fp_opcode_add.inc"
1684 #undef FP_COMPLEX_VERSION
1685 #undef FP_FLOAT_VERSION
1686 }
1687 #endif
1688
1689 #ifdef FP_SUPPORT_COMPLEX_FLOAT_TYPE
1690 template<>
AddFunctionOpcode(unsigned opcode)1691 inline void FunctionParserBase<std::complex<float> >::AddFunctionOpcode(unsigned opcode)
1692 {
1693 typedef std::complex<float> Value_t;
1694 #define FP_FLOAT_VERSION 1
1695 #define FP_COMPLEX_VERSION 1
1696 #include "extrasrc/fp_opcode_add.inc"
1697 #undef FP_COMPLEX_VERSION
1698 #undef FP_FLOAT_VERSION
1699 }
1700 #endif
1701
1702 #ifdef FP_SUPPORT_COMPLEX_LONG_DOUBLE_TYPE
1703 template<>
AddFunctionOpcode(unsigned opcode)1704 inline void FunctionParserBase<std::complex<long double> >::AddFunctionOpcode(unsigned opcode)
1705 {
1706 typedef std::complex<long double> Value_t;
1707 #define FP_FLOAT_VERSION 1
1708 #define FP_COMPLEX_VERSION 1
1709 #include "extrasrc/fp_opcode_add.inc"
1710 #undef FP_COMPLEX_VERSION
1711 #undef FP_FLOAT_VERSION
1712 }
1713 #endif
1714
1715 template<typename Value_t>
1716 unsigned
ParseIdentifier(const char * function)1717 FunctionParserBase<Value_t>::ParseIdentifier(const char* function)
1718 {
1719 return readIdentifier<Value_t>(function);
1720 }
1721
1722 template<typename Value_t>
1723 std::pair<const char*, Value_t>
ParseLiteral(const char * function)1724 FunctionParserBase<Value_t>::ParseLiteral(const char* function)
1725 {
1726 char* endptr;
1727 #if 0 /* Profile the hex literal parser */
1728 if(function[0]=='0' && function[1]=='x')
1729 {
1730 // Parse hexadecimal literal if fp_parseLiteral didn't already
1731 Value_t val = parseHexLiteral<Value_t>(function+2, &endptr);
1732 if(endptr == function+2)
1733 return std::pair<const char*,Value_t> (function, Value_t());
1734 return std::pair<const char*, Value_t> (endptr, val);
1735 }
1736 #endif
1737 Value_t val = fp_parseLiteral<Value_t>(function, &endptr);
1738
1739 if(endptr == function+1 && function[0] == '0' && function[1] == 'x')
1740 {
1741 // Parse hexadecimal literal if fp_parseLiteral didn't already
1742 val = parseHexLiteral<Value_t>(function+2, &endptr);
1743 if(endptr == function+2)
1744 return std::pair<const char*,Value_t> (function, Value_t());
1745 }
1746 else if(endptr == function)
1747 return std::pair<const char*,Value_t> (function, Value_t());
1748
1749 return std::pair<const char*,Value_t> (endptr, val);
1750 }
1751
1752 #ifdef FP_SUPPORT_MPFR_FLOAT_TYPE
1753 template<>
1754 std::pair<const char*, MpfrFloat>
ParseLiteral(const char * function)1755 FunctionParserBase<MpfrFloat>::ParseLiteral(const char* function)
1756 {
1757 char* endPtr;
1758 const MpfrFloat val = MpfrFloat::parseString(function, &endPtr);
1759 if(endPtr == function)
1760 return std::pair<const char*,MpfrFloat> (function, MpfrFloat());
1761 return std::pair<const char*,MpfrFloat> (endPtr, val);
1762 }
1763 #endif
1764
1765 #ifdef FP_SUPPORT_GMP_INT_TYPE
1766 template<>
1767 std::pair<const char*, GmpInt>
ParseLiteral(const char * function)1768 FunctionParserBase<GmpInt>::ParseLiteral(const char* function)
1769 {
1770 char* endPtr;
1771 const GmpInt val = GmpInt::parseString(function, &endPtr);
1772 if(endPtr == function)
1773 return std::pair<const char*,GmpInt> (function, GmpInt());
1774 return std::pair<const char*,GmpInt> (endPtr, val);
1775 }
1776 #endif
1777
1778
1779 template<typename Value_t>
1780 inline const char*
CompileLiteral(const char * function)1781 FunctionParserBase<Value_t>::CompileLiteral(const char* function)
1782 {
1783 std::pair<const char*, Value_t> result = ParseLiteral(function);
1784
1785 if(result.first == function)
1786 return SetErrorType(SYNTAX_ERROR, result.first);
1787
1788 AddImmedOpcode(result.second);
1789 incStackPtr();
1790 SkipSpace(result.first);
1791 return result.first;
1792 }
1793
1794 template<typename Value_t>
CompileIf(const char * function)1795 const char* FunctionParserBase<Value_t>::CompileIf(const char* function)
1796 {
1797 if(*function != '(') return SetErrorType(EXPECT_PARENTH_FUNC, function);
1798
1799 function = CompileExpression(function+1);
1800 if(!function) return 0;
1801 if(*function != ',')
1802 return SetErrorType(noCommaError<Value_t>(*function), function);
1803
1804 OPCODE opcode = cIf;
1805 if(mData->mByteCode.back() == cNotNot) mData->mByteCode.pop_back();
1806 if(IsNeverNegativeValueOpcode(mData->mByteCode.back()))
1807 {
1808 // If we know that the condition to be tested is always
1809 // a positive value (such as when produced by "x<y"),
1810 // we can use the faster opcode to evaluate it.
1811 // cIf tests whether fabs(cond) >= 0.5,
1812 // cAbsIf simply tests whether cond >= 0.5.
1813 opcode = cAbsIf;
1814 }
1815
1816 mData->mByteCode.push_back(opcode);
1817 const unsigned curByteCodeSize = unsigned(mData->mByteCode.size());
1818 PushOpcodeParam<false>(0); // Jump index; to be set later
1819 PushOpcodeParam<true> (0); // Immed jump index; to be set later
1820
1821 --mStackPtr;
1822
1823 function = CompileExpression(function + 1);
1824 if(!function) return 0;
1825 if(*function != ',')
1826 return SetErrorType(noCommaError<Value_t>(*function), function);
1827
1828 mData->mByteCode.push_back(cJump);
1829 const unsigned curByteCodeSize2 = unsigned(mData->mByteCode.size());
1830 const unsigned curImmedSize2 = unsigned(mData->mImmed.size());
1831 PushOpcodeParam<false>(0); // Jump index; to be set later
1832 PushOpcodeParam<true> (0); // Immed jump index; to be set later
1833
1834 --mStackPtr;
1835
1836 function = CompileExpression(function + 1);
1837 if(!function) return 0;
1838 if(*function != ')')
1839 return SetErrorType(noParenthError<Value_t>(*function), function);
1840
1841 PutOpcodeParamAt<true> ( mData->mByteCode.back(), unsigned(mData->mByteCode.size()-1) );
1842 // ^Necessary for guarding against if(x,1,2)+1 being changed
1843 // into if(x,1,3) by fp_opcode_add.inc
1844
1845 // Set jump indices
1846 PutOpcodeParamAt<false>( curByteCodeSize2+1, curByteCodeSize );
1847 PutOpcodeParamAt<false>( curImmedSize2, curByteCodeSize+1 );
1848 PutOpcodeParamAt<false>( unsigned(mData->mByteCode.size())-1, curByteCodeSize2);
1849 PutOpcodeParamAt<false>( unsigned(mData->mImmed.size()), curByteCodeSize2+1);
1850
1851 ++function;
1852 SkipSpace(function);
1853 return function;
1854 }
1855
1856 template<typename Value_t>
CompileFunctionParams(const char * function,unsigned requiredParams)1857 const char* FunctionParserBase<Value_t>::CompileFunctionParams
1858 (const char* function, unsigned requiredParams)
1859 {
1860 if(*function != '(') return SetErrorType(EXPECT_PARENTH_FUNC, function);
1861
1862 if(requiredParams > 0)
1863 {
1864 const char* function_end = CompileExpression(function+1);
1865 if(!function_end)
1866 {
1867 // If an error occurred, verify whether it was caused by ()
1868 ++function;
1869 SkipSpace(function);
1870 if(*function == ')')
1871 return SetErrorType(ILL_PARAMS_AMOUNT, function);
1872 // Not caused by (), use the error message given by CompileExpression()
1873 return 0;
1874 }
1875 function = function_end;
1876
1877 for(unsigned i = 1; i < requiredParams; ++i)
1878 {
1879 if(*function != ',')
1880 return SetErrorType(noCommaError<Value_t>(*function), function);
1881
1882 function = CompileExpression(function+1);
1883 if(!function) return 0;
1884 }
1885 // No need for incStackPtr() because each parse parameter calls it
1886 mStackPtr -= requiredParams-1;
1887 }
1888 else
1889 {
1890 incStackPtr(); // return value of function is pushed onto the stack
1891 ++function;
1892 SkipSpace(function);
1893 }
1894
1895 if(*function != ')')
1896 return SetErrorType(noParenthError<Value_t>(*function), function);
1897 ++function;
1898 SkipSpace(function);
1899 return function;
1900 }
1901
1902 template<typename Value_t>
CompileElement(const char * function)1903 const char* FunctionParserBase<Value_t>::CompileElement(const char* function)
1904 {
1905 if(BeginsLiteral<Value_t>( (unsigned char) *function))
1906 return CompileLiteral(function);
1907
1908 unsigned nameLength = readIdentifier<Value_t>(function);
1909 if(nameLength == 0)
1910 {
1911 // No identifier found
1912 if(*function == '(') return CompileParenthesis(function);
1913 if(*function == ')') return SetErrorType(MISM_PARENTH, function);
1914 return SetErrorType(SYNTAX_ERROR, function);
1915 }
1916
1917 // Function, variable or constant
1918 if(nameLength & 0x80000000U) // Function
1919 {
1920 OPCODE func_opcode = OPCODE( (nameLength >> 16) & 0x7FFF );
1921 return CompileFunction(function + (nameLength & 0xFFFF), func_opcode);
1922 }
1923
1924 NamePtr name(function, nameLength);
1925 const char* endPtr = function + nameLength;
1926 SkipSpace(endPtr);
1927
1928 typename NamePtrsMap<Value_t>::iterator nameIter =
1929 mData->mNamePtrs.find(name);
1930 if(nameIter == mData->mNamePtrs.end())
1931 {
1932 // Check if it's an inline variable:
1933 for(typename Data::InlineVarNamesContainer::reverse_iterator iter =
1934 mData->mInlineVarNames.rbegin();
1935 iter != mData->mInlineVarNames.rend();
1936 ++iter)
1937 {
1938 if(name == iter->mName)
1939 {
1940 if( iter->mFetchIndex+1 == mStackPtr)
1941 {
1942 mData->mByteCode.push_back(cDup);
1943 }
1944 else
1945 {
1946 mData->mByteCode.push_back(cFetch);
1947 PushOpcodeParam<true>(iter->mFetchIndex);
1948 }
1949 incStackPtr();
1950 return endPtr;
1951 }
1952 }
1953
1954 return SetErrorType(UNKNOWN_IDENTIFIER, function);
1955 }
1956
1957 const NameData<Value_t>* nameData = &nameIter->second;
1958 switch(nameData->type)
1959 {
1960 case NameData<Value_t>::VARIABLE: // is variable
1961 if(unlikely(!mData->mByteCode.empty() &&
1962 mData->mByteCode.back() == nameData->index))
1963 mData->mByteCode.push_back(cDup);
1964 else
1965 mData->mByteCode.push_back(nameData->index);
1966 incStackPtr();
1967 return endPtr;
1968
1969 case NameData<Value_t>::CONSTANT: // is constant
1970 AddImmedOpcode(nameData->value);
1971 incStackPtr();
1972 return endPtr;
1973
1974 case NameData<Value_t>::UNIT: // is unit (error if appears here)
1975 break;
1976
1977 case NameData<Value_t>::FUNC_PTR: // is C++ function
1978 function = CompileFunctionParams
1979 (endPtr, mData->mFuncPtrs[nameData->index].mParams);
1980 //if(!function) return 0;
1981 mData->mByteCode.push_back(cFCall);
1982 PushOpcodeParam<true>(nameData->index);
1983 return function;
1984
1985 case NameData<Value_t>::PARSER_PTR: // is FunctionParser
1986 function = CompileFunctionParams
1987 (endPtr, mData->mFuncParsers[nameData->index].mParams);
1988 //if(!function) return 0;
1989 mData->mByteCode.push_back(cPCall);
1990 PushOpcodeParam<true>(nameData->index);
1991 return function;
1992 }
1993
1994 // When it's an unit (or unrecognized type):
1995 return SetErrorType(SYNTAX_ERROR, function);
1996 }
1997
1998 template<typename Value_t>
CompileFunction(const char * function,unsigned func_opcode)1999 inline const char* FunctionParserBase<Value_t>::CompileFunction
2000 (const char* function, unsigned func_opcode)
2001 {
2002 SkipSpace(function);
2003 const FuncDefinition& funcDef = Functions[func_opcode];
2004
2005 if(func_opcode == cIf) // "if" is a special case
2006 return CompileIf(function);
2007
2008 unsigned requiredParams = funcDef.params;
2009
2010 function = CompileFunctionParams(function, requiredParams);
2011 if(!function) return 0;
2012
2013 if(mData->mUseDegreeConversion)
2014 {
2015 if(funcDef.flags & FuncDefinition::AngleIn)
2016 AddFunctionOpcode(cRad);
2017
2018 AddFunctionOpcode(func_opcode);
2019
2020 if(funcDef.flags & FuncDefinition::AngleOut)
2021 AddFunctionOpcode(cDeg);
2022 }
2023 else
2024 {
2025 AddFunctionOpcode(func_opcode);
2026 }
2027 return function;
2028 }
2029
2030 template<typename Value_t>
2031 inline const char*
CompileParenthesis(const char * function)2032 FunctionParserBase<Value_t>::CompileParenthesis(const char* function)
2033 {
2034 ++function; // Skip '('
2035
2036 SkipSpace(function);
2037 if(*function == ')') return SetErrorType(EMPTY_PARENTH, function);
2038 function = CompileExpression(function);
2039 if(!function) return 0;
2040
2041 if(*function != ')') return SetErrorType(MISSING_PARENTH, function);
2042 ++function; // Skip ')'
2043
2044 SkipSpace(function);
2045 return function;
2046 }
2047
2048 template<typename Value_t>
2049 const char*
CompilePossibleUnit(const char * function)2050 FunctionParserBase<Value_t>::CompilePossibleUnit(const char* function)
2051 {
2052 unsigned nameLength = readIdentifier<Value_t>(function);
2053 if(nameLength & 0x80000000U) return function; // built-in function name
2054 if(nameLength != 0)
2055 {
2056 NamePtr name(function, nameLength);
2057
2058 typename NamePtrsMap<Value_t>::iterator nameIter =
2059 mData->mNamePtrs.find(name);
2060 if(nameIter != mData->mNamePtrs.end())
2061 {
2062 const NameData<Value_t>* nameData = &nameIter->second;
2063 if(nameData->type == NameData<Value_t>::UNIT)
2064 {
2065 AddImmedOpcode(nameData->value);
2066 incStackPtr();
2067 AddFunctionOpcode(cMul);
2068 --mStackPtr;
2069
2070 const char* endPtr = function + nameLength;
2071 SkipSpace(endPtr);
2072 return endPtr;
2073 }
2074 }
2075 }
2076
2077 return function;
2078 }
2079
2080 template<typename Value_t>
2081 inline const char*
CompilePow(const char * function)2082 FunctionParserBase<Value_t>::CompilePow(const char* function)
2083 {
2084 function = CompileElement(function);
2085 if(!function) return 0;
2086 function = CompilePossibleUnit(function);
2087
2088 if(*function == '^')
2089 {
2090 ++function;
2091 SkipSpace(function);
2092
2093 unsigned op = cPow;
2094 if(mData->mByteCode.back() == cImmed)
2095 {
2096 if(mData->mImmed.back() == fp_const_e<Value_t>())
2097 { op = cExp; mData->mByteCode.pop_back();
2098 mData->mImmed.pop_back(); --mStackPtr; }
2099 else if(mData->mImmed.back() == Value_t(2))
2100 { op = cExp2; mData->mByteCode.pop_back();
2101 mData->mImmed.pop_back(); --mStackPtr; }
2102 }
2103
2104 function = CompileUnaryMinus(function);
2105 if(!function) return 0;
2106
2107 // add opcode
2108 AddFunctionOpcode(op);
2109
2110 if(op == cPow) --mStackPtr;
2111 }
2112 return function;
2113 }
2114
2115 /* Currently the power operator is skipped for integral types because its
2116 usefulness with them is questionable, and in the case of GmpInt, for safety
2117 reasons:
2118 - With long int almost any power, except for very small ones, would
2119 overflow the result, so the usefulness of this is rather questionable.
2120 - With GmpInt the power operator could be easily abused to make the program
2121 run out of memory (think of a function like "10^10^10^10^1000000").
2122 */
2123 #ifdef FP_SUPPORT_LONG_INT_TYPE
2124 template<>
2125 inline const char*
CompilePow(const char * function)2126 FunctionParserBase<long>::CompilePow(const char* function)
2127 {
2128 function = CompileElement(function);
2129 if(!function) return 0;
2130 return CompilePossibleUnit(function);
2131 }
2132 #endif
2133
2134 #ifdef FP_SUPPORT_GMP_INT_TYPE
2135 template<>
2136 inline const char*
CompilePow(const char * function)2137 FunctionParserBase<GmpInt>::CompilePow(const char* function)
2138 {
2139 function = CompileElement(function);
2140 if(!function) return 0;
2141 return CompilePossibleUnit(function);
2142 }
2143 #endif
2144
2145 template<typename Value_t>
2146 inline const char*
CompileUnaryMinus(const char * function)2147 FunctionParserBase<Value_t>::CompileUnaryMinus(const char* function)
2148 {
2149 char op = *function;
2150 switch(op)
2151 {
2152 case '-':
2153 case '!':
2154 ++function;
2155 SkipSpace(function);
2156
2157 function = CompileUnaryMinus(function);
2158 if(!function) return 0;
2159
2160 AddFunctionOpcode(op=='-' ? cNeg : cNot);
2161
2162 return function;
2163 default: break;
2164 }
2165 return CompilePow(function);
2166 }
2167
2168 template<typename Value_t>
2169 inline const char*
CompileMult(const char * function)2170 FunctionParserBase<Value_t>::CompileMult(const char* function)
2171 {
2172 function = CompileUnaryMinus(function);
2173 if(!function) return 0;
2174
2175 Value_t pending_immed(1);
2176 #define FP_FlushImmed(do_reset) \
2177 if(pending_immed != Value_t(1)) \
2178 { \
2179 unsigned op = cMul; \
2180 if(!IsIntType<Value_t>::result && mData->mByteCode.back() == cInv) \
2181 { \
2182 /* (...) cInv 5 cMul -> (...) 5 cRDiv */ \
2183 /* ^ ^ | */ \
2184 mData->mByteCode.pop_back(); \
2185 op = cRDiv; \
2186 } \
2187 AddImmedOpcode(pending_immed); \
2188 incStackPtr(); \
2189 AddFunctionOpcode(op); \
2190 --mStackPtr; \
2191 if(do_reset) pending_immed = Value_t(1); \
2192 }
2193 while(true)
2194 {
2195 char c = *function;
2196 if(c == '%')
2197 {
2198 FP_FlushImmed(true);
2199 ++function;
2200 SkipSpace(function);
2201 function = CompileUnaryMinus(function);
2202 if(!function) return 0;
2203 AddFunctionOpcode(cMod);
2204 --mStackPtr;
2205 continue;
2206 }
2207 if(c != '*' && c != '/') break;
2208
2209 bool safe_cumulation = (c == '*' || !IsIntType<Value_t>::result);
2210 if(!safe_cumulation)
2211 {
2212 FP_FlushImmed(true);
2213 }
2214
2215 ++function;
2216 SkipSpace(function);
2217 if(mData->mByteCode.back() == cImmed
2218 && (safe_cumulation
2219 || mData->mImmed.back() == Value_t(1)))
2220 {
2221 // 5 (...) cMul --> (...) ||| 5 cMul
2222 // 5 (...) cDiv --> (...) cInv ||| 5 cMul
2223 // ^ | ^
2224 pending_immed *= mData->mImmed.back();
2225 mData->mImmed.pop_back();
2226 mData->mByteCode.pop_back();
2227 --mStackPtr;
2228 function = CompileUnaryMinus(function);
2229 if(!function) return 0;
2230 if(c == '/')
2231 AddFunctionOpcode(cInv);
2232 continue;
2233 }
2234 if(safe_cumulation
2235 && mData->mByteCode.back() == cMul
2236 && mData->mByteCode[mData->mByteCode.size()-2] == cImmed)
2237 {
2238 // (:::) 5 cMul (...) cMul -> (:::) (...) cMul ||| 5 cMul
2239 // (:::) 5 cMul (...) cDiv -> (:::) (...) cDiv ||| 5 cMul
2240 // ^ ^
2241 pending_immed *= mData->mImmed.back();
2242 mData->mImmed.pop_back();
2243 mData->mByteCode.pop_back();
2244 mData->mByteCode.pop_back();
2245 }
2246 // cDiv is not tested here because the bytecode
2247 // optimizer will convert this kind of cDivs into cMuls.
2248 bool lhs_inverted = false;
2249 if(!IsIntType<Value_t>::result && c == '*'
2250 && mData->mByteCode.back() == cInv)
2251 {
2252 // (:::) cInv (...) cMul -> (:::) (...) cRDiv
2253 // (:::) cInv (...) cDiv -> (:::) (...) cMul cInv
2254 // ^ ^ |
2255 mData->mByteCode.pop_back();
2256 lhs_inverted = true;
2257 }
2258 function = CompileUnaryMinus(function);
2259 if(!function) return 0;
2260 if(safe_cumulation
2261 && mData->mByteCode.back() == cMul
2262 && mData->mByteCode[mData->mByteCode.size()-2] == cImmed)
2263 {
2264 // (:::) (...) 5 cMul cMul -> (:::) (...) cMul ||| 5 Mul
2265 // (:::) (...) 5 cMul cDiv -> (:::) (...) cDiv ||| /5 Mul
2266 // ^ ^
2267 if(c == '*')
2268 pending_immed *= mData->mImmed.back();
2269 else
2270 pending_immed /= mData->mImmed.back();
2271 mData->mImmed.pop_back();
2272 mData->mByteCode.pop_back();
2273 mData->mByteCode.pop_back();
2274 }
2275 else
2276 if(safe_cumulation
2277 && mData->mByteCode.back() == cRDiv
2278 && mData->mByteCode[mData->mByteCode.size()-2] == cImmed)
2279 {
2280 // (:::) (...) 5 cRDiv cMul -> (:::) (...) cDiv ||| 5 cMul
2281 // (:::) (...) 5 cRDiv cDiv -> (:::) (...) cMul ||| /5 cMul
2282 // ^ ^
2283 if(c == '*')
2284 { c = '/'; pending_immed *= mData->mImmed.back(); }
2285 else
2286 { c = '*'; pending_immed /= mData->mImmed.back(); }
2287 mData->mImmed.pop_back();
2288 mData->mByteCode.pop_back();
2289 mData->mByteCode.pop_back();
2290 }
2291 if(!lhs_inverted) // if (/x/y) was changed to /(x*y), add missing cInv
2292 {
2293 AddFunctionOpcode(c == '*' ? cMul : cDiv);
2294 --mStackPtr;
2295 }
2296 else if(c == '*') // (/x)*y -> rdiv(x,y)
2297 {
2298 AddFunctionOpcode(cRDiv);
2299 --mStackPtr;
2300 }
2301 else // (/x)/y -> /(x*y)
2302 {
2303 AddFunctionOpcode(cMul);
2304 --mStackPtr;
2305 AddFunctionOpcode(cInv);
2306 }
2307 }
2308 FP_FlushImmed(false);
2309 #undef FP_FlushImmed
2310 return function;
2311 }
2312
2313 template<typename Value_t>
2314 inline const char*
CompileAddition(const char * function)2315 FunctionParserBase<Value_t>::CompileAddition(const char* function)
2316 {
2317 function = CompileMult(function);
2318 if(!function) return 0;
2319
2320 Value_t pending_immed(0);
2321 #define FP_FlushImmed(do_reset) \
2322 if(pending_immed != Value_t(0)) \
2323 { \
2324 unsigned op = cAdd; \
2325 if(mData->mByteCode.back() == cNeg) \
2326 { \
2327 /* (...) cNeg 5 cAdd -> (...) 5 cRSub */ \
2328 /* ^ ^ | */ \
2329 mData->mByteCode.pop_back(); \
2330 op = cRSub; \
2331 } \
2332 AddImmedOpcode(pending_immed); \
2333 incStackPtr(); \
2334 AddFunctionOpcode(op); \
2335 --mStackPtr; \
2336 if(do_reset) pending_immed = Value_t(0); \
2337 }
2338 while(true)
2339 {
2340 char c = *function;
2341 if(c != '+' && c != '-') break;
2342 ++function;
2343 SkipSpace(function);
2344 if(mData->mByteCode.back() == cImmed)
2345 {
2346 // 5 (...) cAdd --> (...) ||| 5 cAdd
2347 // 5 (...) cSub --> (...) cNeg ||| 5 cAdd
2348 // ^ | ^
2349 pending_immed += mData->mImmed.back();
2350 mData->mImmed.pop_back();
2351 mData->mByteCode.pop_back();
2352 --mStackPtr;
2353 function = CompileMult(function);
2354 if(!function) return 0;
2355 if(c == '-')
2356 AddFunctionOpcode(cNeg);
2357 continue;
2358 }
2359 if(mData->mByteCode.back() == cAdd
2360 && mData->mByteCode[mData->mByteCode.size()-2] == cImmed)
2361 {
2362 // (:::) 5 cAdd (...) cAdd -> (:::) (...) cAdd ||| 5 cAdd
2363 // (:::) 5 cAdd (...) cSub -> (:::) (...) cSub ||| 5 cAdd
2364 // ^ ^
2365 pending_immed += mData->mImmed.back();
2366 mData->mImmed.pop_back();
2367 mData->mByteCode.pop_back();
2368 mData->mByteCode.pop_back();
2369 }
2370 // cSub is not tested here because the bytecode
2371 // optimizer will convert this kind of cSubs into cAdds.
2372 bool lhs_negated = false;
2373 if(mData->mByteCode.back() == cNeg)
2374 {
2375 // (:::) cNeg (...) cAdd -> (:::) (...) cRSub
2376 // (:::) cNeg (...) cSub -> (:::) (...) cAdd cNeg
2377 // ^ ^ |
2378 mData->mByteCode.pop_back();
2379 lhs_negated = true;
2380 }
2381 function = CompileMult(function);
2382 if(!function) return 0;
2383 if(mData->mByteCode.back() == cAdd
2384 && mData->mByteCode[mData->mByteCode.size()-2] == cImmed)
2385 {
2386 // (:::) (...) 5 cAdd cAdd -> (:::) (...) cAdd ||| 5 Add
2387 // (:::) (...) 5 cAdd cSub -> (:::) (...) cSub ||| -5 Add
2388 // ^ ^
2389 if(c == '+')
2390 pending_immed += mData->mImmed.back();
2391 else
2392 pending_immed -= mData->mImmed.back();
2393 mData->mImmed.pop_back();
2394 mData->mByteCode.pop_back();
2395 mData->mByteCode.pop_back();
2396 }
2397 else
2398 if(mData->mByteCode.back() == cRSub
2399 && mData->mByteCode[mData->mByteCode.size()-2] == cImmed)
2400 {
2401 // (:::) (...) 5 cRSub cAdd -> (:::) (...) cSub ||| 5 cAdd
2402 // (:::) (...) 5 cRSub cSub -> (:::) (...) cAdd ||| -5 cAdd
2403 // ^ ^
2404 if(c == '+')
2405 { c = '-'; pending_immed += mData->mImmed.back(); }
2406 else
2407 { c = '+'; pending_immed -= mData->mImmed.back(); }
2408 mData->mImmed.pop_back();
2409 mData->mByteCode.pop_back();
2410 mData->mByteCode.pop_back();
2411 }
2412 if(!lhs_negated) // if (-x-y) was changed to -(x+y), add missing cNeg
2413 {
2414 AddFunctionOpcode(c == '+' ? cAdd : cSub);
2415 --mStackPtr;
2416 }
2417 else if(c == '+') // (-x)+y -> rsub(x,y)
2418 {
2419 AddFunctionOpcode(cRSub);
2420 --mStackPtr;
2421 }
2422 else // (-x)-y -> -(x+y)
2423 {
2424 AddFunctionOpcode(cAdd);
2425 --mStackPtr;
2426 AddFunctionOpcode(cNeg);
2427 }
2428 }
2429 FP_FlushImmed(false);
2430 #undef FP_FlushImmed
2431 return function;
2432 }
2433
2434 template<typename Value_t>
2435 inline const char*
CompileComparison(const char * function)2436 FunctionParserBase<Value_t>::CompileComparison(const char* function)
2437 {
2438 unsigned op=0;
2439 while(true)
2440 {
2441 function = CompileAddition(function);
2442 if(!function) return 0;
2443
2444 if(op)
2445 {
2446 AddFunctionOpcode(op);
2447 --mStackPtr;
2448 }
2449 switch(*function)
2450 {
2451 case '=':
2452 ++function; op = cEqual; break;
2453 case '!':
2454 if(function[1] == '=')
2455 { function += 2; op = cNEqual; break; }
2456 // If '=' does not follow '!', a syntax error will
2457 // be generated at the outermost parsing level
2458 return function;
2459 case '<':
2460 if(function[1] == '=')
2461 { function += 2; op = cLessOrEq; break; }
2462 ++function; op = cLess; break;
2463 case '>':
2464 if(function[1] == '=')
2465 { function += 2; op = cGreaterOrEq; break; }
2466 ++function; op = cGreater; break;
2467 default: return function;
2468 }
2469 SkipSpace(function);
2470 }
2471 return function;
2472 }
2473
2474 template<typename Value_t>
CompileAnd(const char * function)2475 inline const char* FunctionParserBase<Value_t>::CompileAnd(const char* function)
2476 {
2477 std::size_t param0end=0;
2478 while(true)
2479 {
2480 function = CompileComparison(function);
2481 if(!function) return 0;
2482
2483 if(param0end)
2484 {
2485 if(mData->mByteCode.back() == cNotNot) mData->mByteCode.pop_back();
2486
2487 AddFunctionOpcode(cAnd);
2488 --mStackPtr;
2489 }
2490 if(*function != '&') break;
2491 ++function;
2492 SkipSpace(function);
2493 param0end = mData->mByteCode.size();
2494 }
2495 return function;
2496 }
2497
2498 template<typename Value_t>
CompileExpression(const char * function)2499 const char* FunctionParserBase<Value_t>::CompileExpression(const char* function)
2500 {
2501 std::size_t param0end=0;
2502 while(true)
2503 {
2504 SkipSpace(function);
2505 function = CompileAnd(function);
2506 if(!function) return 0;
2507
2508 if(param0end)
2509 {
2510 if(mData->mByteCode.back() == cNotNot) mData->mByteCode.pop_back();
2511
2512 AddFunctionOpcode(cOr);
2513 --mStackPtr;
2514 }
2515 if(*function != '|') break;
2516 ++function;
2517 param0end = mData->mByteCode.size();
2518 }
2519 return function;
2520 }
2521
2522 template<typename Value_t>
Compile(const char * function)2523 const char* FunctionParserBase<Value_t>::Compile(const char* function)
2524 {
2525 while(true)
2526 {
2527 // Check if an identifier appears as first token:
2528 SkipSpace(function);
2529 unsigned nameLength = readIdentifier<Value_t>(function);
2530 if(nameLength > 0 && !(nameLength & 0x80000000U))
2531 {
2532 typename Data::InlineVariable inlineVar =
2533 { NamePtr(function, nameLength), 0 };
2534
2535 // Check if it's an unknown identifier:
2536 typename NamePtrsMap<Value_t>::iterator nameIter =
2537 mData->mNamePtrs.find(inlineVar.mName);
2538 if(nameIter == mData->mNamePtrs.end())
2539 {
2540 const char* function2 = function + nameLength;
2541 SkipSpace(function2);
2542
2543 // Check if ":=" follows the unknown identifier:
2544 if(function2[0] == ':' && function2[1] == '=')
2545 {
2546 // Parse the expression that follows and create the
2547 // inline variable:
2548 function2 = CompileExpression(function2 + 2);
2549 if(!function2) return 0;
2550 if(*function2 != ';') return function2;
2551
2552 inlineVar.mFetchIndex = mStackPtr - 1;
2553 mData->mInlineVarNames.push_back(inlineVar);
2554
2555 // Continue with the expression after the ';':
2556 function = function2 + 1;
2557 continue;
2558 }
2559 }
2560 }
2561 break;
2562 }
2563
2564 return CompileExpression(function);
2565 }
2566
2567 template<typename Value_t> template<bool PutFlag>
PushOpcodeParam(unsigned value)2568 inline void FunctionParserBase<Value_t>::PushOpcodeParam
2569 (unsigned value)
2570 {
2571 mData->mByteCode.push_back(value | (PutFlag ? FP_ParamGuardMask : 0u));
2572 if(PutFlag) mData->mHasByteCodeFlags = true;
2573 }
2574
2575 template<typename Value_t> template<bool PutFlag>
PutOpcodeParamAt(unsigned value,unsigned offset)2576 inline void FunctionParserBase<Value_t>::PutOpcodeParamAt
2577 (unsigned value, unsigned offset)
2578 {
2579 mData->mByteCode[offset] = value | (PutFlag ? FP_ParamGuardMask : 0u);
2580 if(PutFlag) mData->mHasByteCodeFlags = true;
2581 }
2582
2583 //===========================================================================
2584 // Function evaluation
2585 //===========================================================================
2586 template<typename Value_t>
Eval(const Value_t * Vars)2587 Value_t FunctionParserBase<Value_t>::Eval(const Value_t* Vars)
2588 {
2589 if(mData->mParseErrorType != FP_NO_ERROR) return Value_t(0);
2590
2591 const unsigned* const byteCode = &(mData->mByteCode[0]);
2592 const Value_t* const immed = mData->mImmed.empty() ? 0 : &(mData->mImmed[0]);
2593 const unsigned byteCodeSize = unsigned(mData->mByteCode.size());
2594 unsigned IP, DP=0;
2595 int SP=-1;
2596
2597 #ifdef FP_USE_THREAD_SAFE_EVAL
2598 /* If Eval() may be called by multiple threads simultaneously,
2599 * then Eval() must allocate its own stack.
2600 */
2601 #ifdef FP_USE_THREAD_SAFE_EVAL_WITH_ALLOCA
2602 /* alloca() allocates room from the hardware stack.
2603 * It is automatically freed when the function returns.
2604 */
2605 Value_t* const Stack = (Value_t*)alloca(mData->mStackSize*sizeof(Value_t));
2606 #else
2607 /* Allocate from the heap. Ensure that it is freed
2608 * automatically no matter which exit path is taken.
2609 */
2610 struct AutoDealloc
2611 {
2612 Value_t* ptr;
2613 ~AutoDealloc() { delete[] ptr; }
2614 } AutoDeallocStack = { new Value_t[mData->mStackSize] };
2615 Value_t*& Stack = AutoDeallocStack.ptr;
2616 #endif
2617 #else
2618 /* No thread safety, so use a global stack. */
2619 std::vector<Value_t>& Stack = mData->mStack;
2620 #endif
2621
2622 for(IP=0; IP<byteCodeSize; ++IP)
2623 {
2624 switch(byteCode[IP])
2625 {
2626 // Functions:
2627 case cAbs: Stack[SP] = fp_abs(Stack[SP]); break;
2628
2629 case cAcos:
2630 if(IsComplexType<Value_t>::result == false
2631 && (Stack[SP] < Value_t(-1) || Stack[SP] > Value_t(1)))
2632 { mData->mEvalErrorType=4; return Value_t(0); }
2633 Stack[SP] = fp_acos(Stack[SP]); break;
2634
2635 case cAcosh:
2636 if(IsComplexType<Value_t>::result == false
2637 && Stack[SP] < Value_t(1))
2638 { mData->mEvalErrorType=4; return Value_t(0); }
2639 Stack[SP] = fp_acosh(Stack[SP]); break;
2640
2641 case cAsin:
2642 if(IsComplexType<Value_t>::result == false
2643 && (Stack[SP] < Value_t(-1) || Stack[SP] > Value_t(1)))
2644 { mData->mEvalErrorType=4; return Value_t(0); }
2645 Stack[SP] = fp_asin(Stack[SP]); break;
2646
2647 case cAsinh: Stack[SP] = fp_asinh(Stack[SP]); break;
2648
2649 case cAtan: Stack[SP] = fp_atan(Stack[SP]); break;
2650
2651 case cAtan2: Stack[SP-1] = fp_atan2(Stack[SP-1], Stack[SP]);
2652 --SP; break;
2653
2654 case cAtanh:
2655 if(IsComplexType<Value_t>::result
2656 ? (Stack[SP] == Value_t(-1) || Stack[SP] == Value_t(1))
2657 : (Stack[SP] <= Value_t(-1) || Stack[SP] >= Value_t(1)))
2658 { mData->mEvalErrorType=4; return Value_t(0); }
2659 Stack[SP] = fp_atanh(Stack[SP]); break;
2660
2661 case cCbrt: Stack[SP] = fp_cbrt(Stack[SP]); break;
2662
2663 case cCeil: Stack[SP] = fp_ceil(Stack[SP]); break;
2664
2665 case cCos: Stack[SP] = fp_cos(Stack[SP]); break;
2666
2667 case cCosh: Stack[SP] = fp_cosh(Stack[SP]); break;
2668
2669 case cCot:
2670 {
2671 const Value_t t = fp_tan(Stack[SP]);
2672 if(t == Value_t(0))
2673 { mData->mEvalErrorType=1; return Value_t(0); }
2674 Stack[SP] = Value_t(1)/t; break;
2675 }
2676
2677 case cCsc:
2678 {
2679 const Value_t s = fp_sin(Stack[SP]);
2680 if(s == Value_t(0))
2681 { mData->mEvalErrorType=1; return Value_t(0); }
2682 Stack[SP] = Value_t(1)/s; break;
2683 }
2684
2685
2686 case cExp: Stack[SP] = fp_exp(Stack[SP]); break;
2687
2688 case cExp2: Stack[SP] = fp_exp2(Stack[SP]); break;
2689
2690 case cFloor: Stack[SP] = fp_floor(Stack[SP]); break;
2691
2692 case cHypot:
2693 Stack[SP-1] = fp_hypot(Stack[SP-1], Stack[SP]);
2694 --SP; break;
2695
2696 case cIf:
2697 if(fp_truth(Stack[SP--]))
2698 IP += 2;
2699 else
2700 {
2701 const unsigned* buf = &byteCode[IP+1];
2702 IP = buf[0];
2703 DP = buf[1];
2704 }
2705 break;
2706
2707 case cInt: Stack[SP] = fp_int(Stack[SP]); break;
2708
2709 case cLog:
2710 if(IsComplexType<Value_t>::result
2711 ? Stack[SP] == Value_t(0)
2712 : !(Stack[SP] > Value_t(0)))
2713 { mData->mEvalErrorType=3; return Value_t(0); }
2714 Stack[SP] = fp_log(Stack[SP]); break;
2715
2716 case cLog10:
2717 if(IsComplexType<Value_t>::result
2718 ? Stack[SP] == Value_t(0)
2719 : !(Stack[SP] > Value_t(0)))
2720 { mData->mEvalErrorType=3; return Value_t(0); }
2721 Stack[SP] = fp_log10(Stack[SP]);
2722 break;
2723
2724 case cLog2:
2725 if(IsComplexType<Value_t>::result
2726 ? Stack[SP] == Value_t(0)
2727 : !(Stack[SP] > Value_t(0)))
2728 { mData->mEvalErrorType=3; return Value_t(0); }
2729 Stack[SP] = fp_log2(Stack[SP]);
2730 break;
2731
2732 case cMax: Stack[SP-1] = fp_max(Stack[SP-1], Stack[SP]);
2733 --SP; break;
2734
2735 case cMin: Stack[SP-1] = fp_min(Stack[SP-1], Stack[SP]);
2736 --SP; break;
2737
2738 case cPow:
2739 // x:Negative ^ y:NonInteger is failure,
2740 // except when the reciprocal of y forms an integer
2741 /*if(IsComplexType<Value_t>::result == false
2742 && Stack[SP-1] < Value_t(0) &&
2743 !isInteger(Stack[SP]) &&
2744 !isInteger(1.0 / Stack[SP]))
2745 { mEvalErrorType=3; return Value_t(0); }*/
2746 // x:0 ^ y:negative is failure
2747 if(Stack[SP-1] == Value_t(0) &&
2748 Stack[SP] < Value_t(0))
2749 { mData->mEvalErrorType=3; return Value_t(0); }
2750 Stack[SP-1] = fp_pow(Stack[SP-1], Stack[SP]);
2751 --SP; break;
2752
2753 case cTrunc: Stack[SP] = fp_trunc(Stack[SP]); break;
2754
2755 case cSec:
2756 {
2757 const Value_t c = fp_cos(Stack[SP]);
2758 if(c == Value_t(0))
2759 { mData->mEvalErrorType=1; return Value_t(0); }
2760 Stack[SP] = Value_t(1)/c; break;
2761 }
2762
2763 case cSin: Stack[SP] = fp_sin(Stack[SP]); break;
2764
2765 case cSinh: Stack[SP] = fp_sinh(Stack[SP]); break;
2766
2767 case cSqrt:
2768 if(IsComplexType<Value_t>::result == false &&
2769 Stack[SP] < Value_t(0))
2770 { mData->mEvalErrorType=2; return Value_t(0); }
2771 Stack[SP] = fp_sqrt(Stack[SP]); break;
2772
2773 case cTan: Stack[SP] = fp_tan(Stack[SP]); break;
2774
2775 case cTanh: Stack[SP] = fp_tanh(Stack[SP]); break;
2776
2777
2778 // Misc:
2779 case cImmed: Stack[++SP] = immed[DP++]; break;
2780
2781 case cJump:
2782 {
2783 const unsigned* buf = &byteCode[IP+1];
2784 IP = buf[0];
2785 DP = buf[1];
2786 break;
2787 }
2788
2789 // Operators:
2790 case cNeg: Stack[SP] = -Stack[SP]; break;
2791 case cAdd: Stack[SP-1] += Stack[SP]; --SP; break;
2792 case cSub: Stack[SP-1] -= Stack[SP]; --SP; break;
2793 case cMul: Stack[SP-1] *= Stack[SP]; --SP; break;
2794
2795 case cDiv:
2796 if(Stack[SP] == Value_t(0))
2797 { mData->mEvalErrorType=1; return Value_t(0); }
2798 Stack[SP-1] /= Stack[SP]; --SP; break;
2799
2800 case cMod:
2801 if(Stack[SP] == Value_t(0))
2802 { mData->mEvalErrorType=1; return Value_t(0); }
2803 Stack[SP-1] = fp_mod(Stack[SP-1], Stack[SP]);
2804 --SP; break;
2805
2806 case cEqual:
2807 Stack[SP-1] = fp_equal(Stack[SP-1], Stack[SP]);
2808 --SP; break;
2809
2810 case cNEqual:
2811 Stack[SP-1] = fp_nequal(Stack[SP-1], Stack[SP]);
2812 --SP; break;
2813
2814 case cLess:
2815 Stack[SP-1] = fp_less(Stack[SP-1], Stack[SP]);
2816 --SP; break;
2817
2818 case cLessOrEq:
2819 Stack[SP-1] = fp_lessOrEq(Stack[SP-1], Stack[SP]);
2820 --SP; break;
2821
2822 case cGreater:
2823 Stack[SP-1] = fp_less(Stack[SP], Stack[SP-1]);
2824 --SP; break;
2825
2826 case cGreaterOrEq:
2827 Stack[SP-1] = fp_lessOrEq(Stack[SP], Stack[SP-1]);
2828 --SP; break;
2829
2830 case cNot: Stack[SP] = fp_not(Stack[SP]); break;
2831
2832 case cNotNot: Stack[SP] = fp_notNot(Stack[SP]); break;
2833
2834 case cAnd:
2835 Stack[SP-1] = fp_and(Stack[SP-1], Stack[SP]);
2836 --SP; break;
2837
2838 case cOr:
2839 Stack[SP-1] = fp_or(Stack[SP-1], Stack[SP]);
2840 --SP; break;
2841
2842 // Degrees-radians conversion:
2843 case cDeg: Stack[SP] = RadiansToDegrees(Stack[SP]); break;
2844 case cRad: Stack[SP] = DegreesToRadians(Stack[SP]); break;
2845
2846 // User-defined function calls:
2847 case cFCall:
2848 {
2849 const unsigned index = byteCode[++IP];
2850 const unsigned params = mData->mFuncPtrs[index].mParams;
2851 const Value_t retVal =
2852 mData->mFuncPtrs[index].mRawFuncPtr ?
2853 mData->mFuncPtrs[index].mRawFuncPtr(&Stack[SP-params+1]) :
2854 mData->mFuncPtrs[index].mFuncWrapperPtr->callFunction
2855 (&Stack[SP-params+1]);
2856 SP -= int(params)-1;
2857 Stack[SP] = retVal;
2858 break;
2859 }
2860
2861 case cPCall:
2862 {
2863 unsigned index = byteCode[++IP];
2864 unsigned params = mData->mFuncParsers[index].mParams;
2865 Value_t retVal =
2866 mData->mFuncParsers[index].mParserPtr->Eval
2867 (&Stack[SP-params+1]);
2868 SP -= int(params)-1;
2869 Stack[SP] = retVal;
2870 const int error =
2871 mData->mFuncParsers[index].mParserPtr->EvalError();
2872 if(error)
2873 {
2874 mData->mEvalErrorType = error;
2875 return 0;
2876 }
2877 break;
2878 }
2879
2880
2881 case cFetch:
2882 {
2883 unsigned stackOffs = byteCode[++IP];
2884 Stack[SP+1] = Stack[stackOffs]; ++SP;
2885 break;
2886 }
2887
2888 #ifdef FP_SUPPORT_OPTIMIZER
2889 case cPopNMov:
2890 {
2891 unsigned stackOffs_target = byteCode[++IP];
2892 unsigned stackOffs_source = byteCode[++IP];
2893 Stack[stackOffs_target] = Stack[stackOffs_source];
2894 SP = stackOffs_target;
2895 break;
2896 }
2897
2898 case cLog2by:
2899 if(IsComplexType<Value_t>::result
2900 ? Stack[SP-1] == Value_t(0)
2901 : !(Stack[SP-1] > Value_t(0)))
2902 { mData->mEvalErrorType=3; return Value_t(0); }
2903 Stack[SP-1] = fp_log2(Stack[SP-1]) * Stack[SP];
2904 --SP;
2905 break;
2906
2907 case cNop: break;
2908 #endif // FP_SUPPORT_OPTIMIZER
2909
2910 case cSinCos:
2911 fp_sinCos(Stack[SP], Stack[SP+1], Stack[SP]);
2912 ++SP;
2913 break;
2914 case cSinhCosh:
2915 fp_sinhCosh(Stack[SP], Stack[SP+1], Stack[SP]);
2916 ++SP;
2917 break;
2918
2919 case cAbsNot:
2920 Stack[SP] = fp_absNot(Stack[SP]); break;
2921 case cAbsNotNot:
2922 Stack[SP] = fp_absNotNot(Stack[SP]); break;
2923 case cAbsAnd:
2924 Stack[SP-1] = fp_absAnd(Stack[SP-1], Stack[SP]);
2925 --SP; break;
2926 case cAbsOr:
2927 Stack[SP-1] = fp_absOr(Stack[SP-1], Stack[SP]);
2928 --SP; break;
2929 case cAbsIf:
2930 if(fp_absTruth(Stack[SP--]))
2931 IP += 2;
2932 else
2933 {
2934 const unsigned* buf = &byteCode[IP+1];
2935 IP = buf[0];
2936 DP = buf[1];
2937 }
2938 break;
2939
2940 case cDup: Stack[SP+1] = Stack[SP]; ++SP; break;
2941
2942 case cInv:
2943 if(Stack[SP] == Value_t(0))
2944 { mData->mEvalErrorType=1; return Value_t(0); }
2945 Stack[SP] = Value_t(1)/Stack[SP];
2946 break;
2947
2948 case cSqr:
2949 Stack[SP] = Stack[SP]*Stack[SP];
2950 break;
2951
2952 case cRDiv:
2953 if(Stack[SP-1] == Value_t(0))
2954 { mData->mEvalErrorType=1; return Value_t(0); }
2955 Stack[SP-1] = Stack[SP] / Stack[SP-1]; --SP; break;
2956
2957 case cRSub: Stack[SP-1] = Stack[SP] - Stack[SP-1]; --SP; break;
2958
2959 case cRSqrt:
2960 if(Stack[SP] == Value_t(0))
2961 { mData->mEvalErrorType=1; return Value_t(0); }
2962 Stack[SP] = Value_t(1) / fp_sqrt(Stack[SP]); break;
2963
2964 #ifdef FP_SUPPORT_COMPLEX_NUMBERS
2965 case cReal: Stack[SP] = fp_real(Stack[SP]); break;
2966 case cImag: Stack[SP] = fp_imag(Stack[SP]); break;
2967 case cArg: Stack[SP] = fp_arg(Stack[SP]); break;
2968 case cConj: Stack[SP] = fp_conj(Stack[SP]); break;
2969 case cPolar:
2970 Stack[SP-1] = fp_polar(Stack[SP-1], Stack[SP]);
2971 --SP; break;
2972 #endif
2973
2974
2975 // Variables:
2976 default:
2977 Stack[++SP] = Vars[byteCode[IP]-VarBegin];
2978 }
2979 }
2980
2981 mData->mEvalErrorType=0;
2982 return Stack[SP];
2983 }
2984
2985
2986 //===========================================================================
2987 // Variable deduction
2988 //===========================================================================
2989 namespace
2990 {
2991 template<typename Value_t>
deduceVariables(FunctionParserBase<Value_t> & fParser,const char * funcStr,std::string & destVarString,int * amountOfVariablesFound,std::vector<std::string> * destVarNames,bool useDegrees)2992 int deduceVariables(FunctionParserBase<Value_t>& fParser,
2993 const char* funcStr,
2994 std::string& destVarString,
2995 int* amountOfVariablesFound,
2996 std::vector<std::string>* destVarNames,
2997 bool useDegrees)
2998 {
2999 typedef std::set<std::string> StrSet;
3000 StrSet varNames;
3001
3002 int oldIndex = -1;
3003
3004 while(true)
3005 {
3006 destVarString.clear();
3007 for(StrSet::iterator iter = varNames.begin();
3008 iter != varNames.end();
3009 ++iter)
3010 {
3011 if(iter != varNames.begin()) destVarString += ",";
3012 destVarString += *iter;
3013 }
3014
3015 const int index =
3016 fParser.Parse(funcStr, destVarString, useDegrees);
3017 if(index < 0) break;
3018 if(index == oldIndex) return index;
3019
3020 unsigned nameLength = readIdentifier<Value_t>(funcStr + index);
3021 if(nameLength & 0x80000000U) return index;
3022 if(nameLength == 0) return index;
3023
3024 varNames.insert(std::string(funcStr + index, nameLength));
3025 oldIndex = index;
3026 }
3027
3028 if(amountOfVariablesFound)
3029 *amountOfVariablesFound = int(varNames.size());
3030
3031 if(destVarNames)
3032 destVarNames->assign(varNames.begin(), varNames.end());
3033
3034 return -1;
3035 }
3036 }
3037
3038 template<typename Value_t>
ParseAndDeduceVariables(const std::string & function,int * amountOfVariablesFound,bool useDegrees)3039 int FunctionParserBase<Value_t>::ParseAndDeduceVariables
3040 (const std::string& function,
3041 int* amountOfVariablesFound,
3042 bool useDegrees)
3043 {
3044 std::string varString;
3045 return deduceVariables(*this, function.c_str(), varString,
3046 amountOfVariablesFound, 0, useDegrees);
3047 }
3048
3049 template<typename Value_t>
ParseAndDeduceVariables(const std::string & function,std::string & resultVarString,int * amountOfVariablesFound,bool useDegrees)3050 int FunctionParserBase<Value_t>::ParseAndDeduceVariables
3051 (const std::string& function,
3052 std::string& resultVarString,
3053 int* amountOfVariablesFound,
3054 bool useDegrees)
3055 {
3056 std::string varString;
3057 const int index =
3058 deduceVariables(*this, function.c_str(), varString,
3059 amountOfVariablesFound, 0, useDegrees);
3060 if(index < 0) resultVarString = varString;
3061 return index;
3062 }
3063
3064 template<typename Value_t>
ParseAndDeduceVariables(const std::string & function,std::vector<std::string> & resultVars,bool useDegrees)3065 int FunctionParserBase<Value_t>::ParseAndDeduceVariables
3066 (const std::string& function,
3067 std::vector<std::string>& resultVars,
3068 bool useDegrees)
3069 {
3070 std::string varString;
3071 std::vector<std::string> vars;
3072 const int index =
3073 deduceVariables(*this, function.c_str(), varString,
3074 0, &vars, useDegrees);
3075 if(index < 0) resultVars.swap(vars);
3076 return index;
3077 }
3078
3079
3080 #ifdef FUNCTIONPARSER_SUPPORT_DEBUGGING
3081 //===========================================================================
3082 // Bytecode injection
3083 //===========================================================================
3084 template<typename Value_t>
InjectRawByteCode(const unsigned * bytecode,unsigned bytecodeAmount,const Value_t * immed,unsigned immedAmount,unsigned stackSize)3085 void FunctionParserBase<Value_t>::InjectRawByteCode
3086 (const unsigned* bytecode, unsigned bytecodeAmount,
3087 const Value_t* immed, unsigned immedAmount, unsigned stackSize)
3088 {
3089 CopyOnWrite();
3090
3091 mData->mByteCode.assign(bytecode, bytecode + bytecodeAmount);
3092 mData->mImmed.assign(immed, immed + immedAmount);
3093 mData->mStackSize = stackSize;
3094
3095 #ifndef FP_USE_THREAD_SAFE_EVAL
3096 mData->mStack.resize(stackSize);
3097 #endif
3098 }
3099
3100 //===========================================================================
3101 // Debug output
3102 //===========================================================================
3103 #include <iomanip>
3104 #include <sstream>
3105 namespace
3106 {
printHex(std::ostream & dest,unsigned n)3107 inline void printHex(std::ostream& dest, unsigned n)
3108 {
3109 std::ios::fmtflags flags = dest.flags();
3110 dest.width(4); dest.fill('0'); std::hex(dest); //uppercase(dest);
3111 dest << n;
3112 dest.flags(flags);
3113 }
3114
padLine(std::ostringstream & dest,unsigned destLength)3115 void padLine(std::ostringstream& dest, unsigned destLength)
3116 {
3117 for(std::size_t currentLength = dest.str().length();
3118 currentLength < destLength;
3119 ++currentLength)
3120 {
3121 dest << ' ';
3122 }
3123 }
3124
3125 const struct PowiMuliType
3126 {
3127 unsigned opcode_square;
3128 unsigned opcode_cumulate;
3129 unsigned opcode_invert;
3130 unsigned opcode_half;
3131 unsigned opcode_invhalf;
3132 } iseq_powi = {cSqr,cMul,cInv,cSqrt,cRSqrt},
3133 iseq_muli = {~unsigned(0), cAdd,cNeg, ~unsigned(0),~unsigned(0) };
3134
3135 template<typename Value_t>
ParsePowiMuli(const PowiMuliType & opcodes,const std::vector<unsigned> & ByteCode,unsigned & IP,unsigned limit,std::size_t factor_stack_base,std::vector<Value_t> & stack,bool IgnoreExcess)3136 Value_t ParsePowiMuli(
3137 const PowiMuliType& opcodes,
3138 const std::vector<unsigned>& ByteCode, unsigned& IP,
3139 unsigned limit,
3140 std::size_t factor_stack_base,
3141 std::vector<Value_t>& stack,
3142 bool IgnoreExcess)
3143 {
3144 Value_t result = Value_t(1);
3145 while(IP < limit)
3146 {
3147 if(ByteCode[IP] == opcodes.opcode_square)
3148 {
3149 if(!isInteger(result)) break;
3150 result *= Value_t(2);
3151 ++IP;
3152 continue;
3153 }
3154 if(ByteCode[IP] == opcodes.opcode_invert)
3155 {
3156 if(result < Value_t(0)) break;
3157 result = -result;
3158 ++IP;
3159 continue;
3160 }
3161 if(ByteCode[IP] == opcodes.opcode_half)
3162 {
3163 if(result > Value_t(0) && isEvenInteger(result))
3164 break;
3165 if(isInteger(result * Value_t(0.5))) break;
3166 result *= Value_t(0.5);
3167 ++IP;
3168 continue;
3169 }
3170 if(ByteCode[IP] == opcodes.opcode_invhalf)
3171 {
3172 if(result > Value_t(0) && isEvenInteger(result))
3173 break;
3174 if(isInteger(result * Value_t(-0.5))) break;
3175 result *= Value_t(-0.5);
3176 ++IP;
3177 continue;
3178 }
3179
3180 unsigned dup_fetch_pos = IP;
3181 Value_t lhs = Value_t(1);
3182
3183 if(ByteCode[IP] == cFetch)
3184 {
3185 unsigned index = ByteCode[++IP];
3186 if(index < factor_stack_base
3187 || std::size_t(index-factor_stack_base) >= stack.size())
3188 {
3189 // It wasn't a powi-fetch after all
3190 IP = dup_fetch_pos;
3191 break;
3192 }
3193 lhs = stack[index - factor_stack_base];
3194 // Note: ^This assumes that cFetch of recentmost
3195 // is always converted into cDup.
3196 goto dup_or_fetch;
3197 }
3198
3199 if(ByteCode[IP] == cDup)
3200 {
3201 lhs = result;
3202 goto dup_or_fetch;
3203
3204 dup_or_fetch:
3205 stack.push_back(result);
3206 ++IP;
3207 Value_t subexponent = ParsePowiMuli
3208 (opcodes,
3209 ByteCode, IP, limit,
3210 factor_stack_base, stack,
3211 IgnoreExcess);
3212 if(IP >= limit && IgnoreExcess)
3213 return lhs*subexponent;
3214 if(IP >= limit || ByteCode[IP] != opcodes.opcode_cumulate)
3215 {
3216 // It wasn't a powi-dup after all
3217 IP = dup_fetch_pos;
3218 break;
3219 }
3220 ++IP; // skip opcode_cumulate
3221 stack.pop_back();
3222 result += lhs*subexponent;
3223 continue;
3224 }
3225 break;
3226 }
3227 return result;
3228 }
3229
3230 template<typename Value_t>
ParsePowiSequence(const std::vector<unsigned> & ByteCode,unsigned & IP,unsigned limit,std::size_t factor_stack_base,bool IgnoreExcess=false)3231 Value_t ParsePowiSequence(const std::vector<unsigned>& ByteCode,
3232 unsigned& IP, unsigned limit,
3233 std::size_t factor_stack_base,
3234 bool IgnoreExcess = false)
3235 {
3236 std::vector<Value_t> stack;
3237 stack.push_back(Value_t(1));
3238 return ParsePowiMuli(iseq_powi, ByteCode, IP, limit,
3239 factor_stack_base, stack,
3240 IgnoreExcess);
3241 }
3242
3243 template<typename Value_t>
ParseMuliSequence(const std::vector<unsigned> & ByteCode,unsigned & IP,unsigned limit,std::size_t factor_stack_base,bool IgnoreExcess=false)3244 Value_t ParseMuliSequence(const std::vector<unsigned>& ByteCode,
3245 unsigned& IP, unsigned limit,
3246 std::size_t factor_stack_base,
3247 bool IgnoreExcess = false)
3248 {
3249 std::vector<Value_t> stack;
3250 stack.push_back(Value_t(1));
3251 return ParsePowiMuli(iseq_muli, ByteCode, IP, limit,
3252 factor_stack_base, stack,
3253 IgnoreExcess);
3254 }
3255
3256 struct IfInfo
3257 {
3258 std::pair<int,std::string> condition;
3259 std::pair<int,std::string> thenbranch;
3260 unsigned endif_location;
3261
IfInfo__anon4ecb8ad20c11::IfInfo3262 IfInfo() : condition(), thenbranch(), endif_location() { }
3263 };
3264 }
3265
3266 template<typename Value_t>
PrintByteCode(std::ostream & dest,bool showExpression) const3267 void FunctionParserBase<Value_t>::PrintByteCode(std::ostream& dest,
3268 bool showExpression) const
3269 {
3270 dest << "Size of stack: " << mData->mStackSize << "\n";
3271
3272 std::ostringstream outputBuffer;
3273 std::ostream& output = (showExpression ? outputBuffer : dest);
3274
3275 const std::vector<unsigned>& ByteCode = mData->mByteCode;
3276 const std::vector<Value_t>& Immed = mData->mImmed;
3277
3278 std::vector<std::pair<int,std::string> > stack;
3279 std::vector<IfInfo> if_stack;
3280
3281 for(unsigned IP = 0, DP = 0; IP <= ByteCode.size(); ++IP)
3282 {
3283 after_powi_or_muli:;
3284 std::string n;
3285 bool out_params = false;
3286 unsigned params = 2, produces = 1, opcode = 0;
3287
3288 if(showExpression && !if_stack.empty() &&
3289 ( // Normal If termination rule:
3290 if_stack.back().endif_location == IP
3291 // This rule matches when cJumps are threaded:
3292 || (IP < ByteCode.size() && ByteCode[IP] == cJump
3293 && !if_stack.back().thenbranch.second.empty())
3294 ))
3295 {
3296 printHex(output, IP);
3297 if(if_stack.back().endif_location == IP)
3298 output << ": ----- (phi)";
3299 else
3300 output << ": ----- (phi+)";
3301
3302 stack.resize(stack.size()+2);
3303 std::swap(stack[stack.size()-3], stack[stack.size()-1]);
3304 std::swap(if_stack.back().condition, stack[stack.size()-3]);
3305 std::swap(if_stack.back().thenbranch, stack[stack.size()-2]);
3306 opcode = cIf;
3307 params = 3;
3308 --IP;
3309 if_stack.pop_back();
3310 }
3311 else
3312 {
3313 if(IP >= ByteCode.size()) break;
3314 opcode = ByteCode[IP];
3315
3316 if(showExpression && (
3317 opcode == cSqr || opcode == cDup
3318 || opcode == cInv
3319 || opcode == cSqrt || opcode == cRSqrt
3320 || opcode == cFetch
3321 ))
3322 {
3323 unsigned changed_ip = IP;
3324 Value_t exponent =
3325 ParsePowiSequence<Value_t>
3326 (ByteCode, changed_ip,
3327 if_stack.empty()
3328 ? (unsigned)ByteCode.size()
3329 : if_stack.back().endif_location,
3330 stack.size()-1);
3331 std::string operation_prefix;
3332 std::ostringstream operation_value;
3333 int prio = 0;
3334 if(exponent == Value_t(1.0))
3335 {
3336 if(opcode != cDup) goto not_powi_or_muli;
3337 Value_t factor =
3338 ParseMuliSequence<Value_t>
3339 (ByteCode, changed_ip,
3340 if_stack.empty()
3341 ? (unsigned)ByteCode.size()
3342 : if_stack.back().endif_location,
3343 stack.size()-1);
3344 if(factor == Value_t(1) || factor == Value_t(-1))
3345 goto not_powi_or_muli;
3346 operation_prefix = "*";
3347 operation_value << factor;
3348 prio = 3;
3349 }
3350 else
3351 {
3352 prio = 2;
3353 operation_prefix = "^";
3354 operation_value << exponent;
3355 }
3356
3357 //unsigned explanation_before = changed_ip-2;
3358 unsigned explanation_before = changed_ip-1;
3359
3360 const char* explanation_prefix = "_";
3361 for(const unsigned first_ip = IP; IP < changed_ip; ++IP)
3362 {
3363 printHex(output, IP);
3364 output << ": ";
3365
3366 const char* sep = "|";
3367 if(first_ip+1 == changed_ip)
3368 { sep = "="; explanation_prefix = " "; }
3369 else if(IP == first_ip) sep = "\\";
3370 else if(IP+1 == changed_ip) sep = "/";
3371 else explanation_prefix = "=";
3372
3373 switch(ByteCode[IP])
3374 {
3375 case cInv: output << "inv"; break;
3376 case cNeg: output << "neg"; break;
3377 case cDup: output << "dup"; break;
3378 case cSqr: output << "sqr"; break;
3379 case cMul: output << "mul"; break;
3380 case cAdd: output << "add"; break;
3381 case cCbrt: output << "cbrt"; break;
3382 case cSqrt: output << "sqrt"; break;
3383 case cRSqrt: output << "rsqrt"; break;
3384 case cFetch:
3385 {
3386 unsigned index = ByteCode[++IP];
3387 output << "cFetch(" << index << ")";
3388 break;
3389 }
3390 default: break;
3391 }
3392 padLine(outputBuffer, 20);
3393 output << sep;
3394 if(IP >= explanation_before)
3395 {
3396 explanation_before = (unsigned)ByteCode.size();
3397 output << explanation_prefix
3398 << '[' << (stack.size()-1) << ']';
3399 std::string last = stack.back().second;
3400 if(stack.back().first >= prio)
3401 last = "(" + last + ")";
3402 output << last;
3403 output << operation_prefix;
3404 output << operation_value.str();
3405 }
3406 else
3407 {
3408 unsigned p = first_ip;
3409 Value_t exp = operation_prefix=="^" ?
3410 ParsePowiSequence<Value_t>
3411 (ByteCode, p, IP+1, stack.size()-1, true) :
3412 ParseMuliSequence<Value_t>
3413 (ByteCode, p, IP+1, stack.size()-1, true);
3414 std::string last = stack.back().second;
3415 if(stack.back().first >= prio)
3416 last = "(" + last + ")";
3417 output << " ..." << last;
3418 output << operation_prefix;
3419 output << exp;
3420 }
3421 dest << outputBuffer.str() << std::endl;
3422 outputBuffer.str("");
3423 }
3424
3425 std::string& last = stack.back().second;
3426 if(stack.back().first >= prio)
3427 last = "(" + last + ")";
3428 last += operation_prefix;
3429 last += operation_value.str();
3430 stack.back().first = prio;
3431
3432 goto after_powi_or_muli;
3433 }
3434 not_powi_or_muli:;
3435 printHex(output, IP);
3436 output << ": ";
3437
3438 switch(opcode)
3439 {
3440 case cIf:
3441 {
3442 unsigned label = ByteCode[IP+1]+1;
3443 output << "jz ";
3444 printHex(output, label);
3445 params = 1;
3446 produces = 0;
3447 IP += 2;
3448
3449 if_stack.resize(if_stack.size() + 1);
3450 std::swap( if_stack.back().condition, stack.back() );
3451 if_stack.back().endif_location = (unsigned) ByteCode.size();
3452 stack.pop_back();
3453 break;
3454 }
3455 case cAbsIf:
3456 {
3457 unsigned dp = ByteCode[IP+2];
3458 unsigned label = ByteCode[IP+1]+1;
3459 output << "jz_abs " << dp << ",";
3460 printHex(output, label);
3461 params = 1;
3462 produces = 0;
3463 IP += 2;
3464
3465 if_stack.resize(if_stack.size() + 1);
3466 std::swap( if_stack.back().condition, stack.back() );
3467 if_stack.back().endif_location = (unsigned) ByteCode.size();
3468 stack.pop_back();
3469 break;
3470 }
3471
3472 case cJump:
3473 {
3474 unsigned dp = ByteCode[IP+2];
3475 unsigned label = ByteCode[IP+1]+1;
3476
3477 if(!if_stack.empty() && !stack.empty())
3478 {
3479 std::swap(if_stack.back().thenbranch, stack.back());
3480 if_stack.back().endif_location = label;
3481 stack.pop_back();
3482 }
3483
3484 output << "jump " << dp << ",";
3485 printHex(output, label);
3486 params = 0;
3487 produces = 0;
3488 IP += 2;
3489 break;
3490 }
3491 case cImmed:
3492 {
3493 if(showExpression)
3494 {
3495 std::ostringstream buf;
3496 buf.precision(8);
3497 buf << Immed[DP];
3498 stack.push_back( std::make_pair(0, buf.str()) );
3499 }
3500 output.precision(8);
3501 output << "push " << Immed[DP];
3502 ++DP;
3503 produces = 0;
3504 break;
3505 }
3506
3507 case cFCall:
3508 {
3509 const unsigned index = ByteCode[++IP];
3510 params = mData->mFuncPtrs[index].mParams;
3511 static std::string name;
3512 name = "f:" + findName(mData->mNamePtrs, index,
3513 NameData<Value_t>::FUNC_PTR);
3514 n = name.c_str();
3515 out_params = true;
3516 break;
3517 }
3518
3519 case cPCall:
3520 {
3521 const unsigned index = ByteCode[++IP];
3522 params = mData->mFuncParsers[index].mParams;
3523 static std::string name;
3524 name = "p:" + findName(mData->mNamePtrs, index,
3525 NameData<Value_t>::PARSER_PTR);
3526 n = name.c_str();
3527 out_params = true;
3528 break;
3529 }
3530
3531 default:
3532 if(IsVarOpcode(opcode))
3533 {
3534 if(showExpression)
3535 {
3536 stack.push_back(std::make_pair(0,
3537 (findName(mData->mNamePtrs, opcode,
3538 NameData<Value_t>::VARIABLE))));
3539 }
3540 output << "push Var" << opcode-VarBegin;
3541 produces = 0;
3542 }
3543 else
3544 {
3545 switch(OPCODE(opcode))
3546 {
3547 case cNeg: n = "neg"; params = 1; break;
3548 case cAdd: n = "add"; break;
3549 case cSub: n = "sub"; break;
3550 case cMul: n = "mul"; break;
3551 case cDiv: n = "div"; break;
3552 case cMod: n = "mod"; break;
3553 case cPow: n = "pow"; break;
3554 case cEqual: n = "eq"; break;
3555 case cNEqual: n = "neq"; break;
3556 case cLess: n = "lt"; break;
3557 case cLessOrEq: n = "le"; break;
3558 case cGreater: n = "gt"; break;
3559 case cGreaterOrEq: n = "ge"; break;
3560 case cAnd: n = "and"; break;
3561 case cOr: n = "or"; break;
3562 case cNot: n = "not"; params = 1; break;
3563 case cNotNot: n = "notnot"; params = 1; break;
3564 case cDeg: n = "deg"; params = 1; break;
3565 case cRad: n = "rad"; params = 1; break;
3566
3567 case cFetch:
3568 {
3569 unsigned index = ByteCode[++IP];
3570 if(showExpression && index < stack.size())
3571 stack.push_back(stack[index]);
3572 output << "cFetch(" << index << ")";
3573 produces = 0;
3574 break;
3575 }
3576 #ifdef FP_SUPPORT_OPTIMIZER
3577 case cLog2by: n = "log2by"; params = 2; out_params = 1; break;
3578 case cPopNMov:
3579 {
3580 std::size_t a = ByteCode[++IP];
3581 std::size_t b = ByteCode[++IP];
3582 if(showExpression && b < stack.size())
3583 {
3584 std::pair<int, std::string> stacktop(0, "?");
3585 if(b < stack.size()) stacktop = stack[b];
3586 stack.resize(a);
3587 stack.push_back(stacktop);
3588 }
3589 output << "cPopNMov(" << a << ", " << b << ")";
3590 produces = 0;
3591 break;
3592 }
3593 case cNop:
3594 output << "nop"; params = 0; produces = 0;
3595 break;
3596 #endif
3597 case cSinCos:
3598 {
3599 if(showExpression)
3600 {
3601 std::pair<int, std::string> sin = stack.back();
3602 std::pair<int, std::string> cos(
3603 0, "cos(" + sin.second + ")");
3604 sin.first = 0;
3605 sin.second = "sin(" + sin.second + ")";
3606 stack.back() = sin;
3607 stack.push_back(cos);
3608 }
3609 output << "sincos";
3610 produces = 0;
3611 break;
3612 }
3613 case cSinhCosh:
3614 {
3615 if(showExpression)
3616 {
3617 std::pair<int, std::string> sinh = stack.back();
3618 std::pair<int, std::string> cosh(
3619 0, "cosh(" + sinh.second + ")");
3620 sinh.first = 0;
3621 sinh.second = "sinh(" + sinh.second + ")";
3622 stack.back() = sinh;
3623 stack.push_back(cosh);
3624 }
3625 output << "sinhcosh";
3626 produces = 0;
3627 break;
3628 }
3629 case cAbsAnd: n = "abs_and"; break;
3630 case cAbsOr: n = "abs_or"; break;
3631 case cAbsNot: n = "abs_not"; params = 1; break;
3632 case cAbsNotNot: n = "abs_notnot"; params = 1; break;
3633 case cDup:
3634 {
3635 if(showExpression)
3636 stack.push_back(stack.back());
3637 output << "dup";
3638 produces = 0;
3639 break;
3640 }
3641 case cInv: n = "inv"; params = 1; break;
3642 case cSqr: n = "sqr"; params = 1; break;
3643 case cRDiv: n = "rdiv"; break;
3644 case cRSub: n = "rsub"; break;
3645 case cRSqrt: n = "rsqrt"; params = 1; break;
3646
3647 default:
3648 n = Functions[opcode-cAbs].name;
3649 params = Functions[opcode-cAbs].params;
3650 out_params = params != 1;
3651 }
3652 }
3653 }
3654 }
3655 if(produces) output << n;
3656 if(out_params) output << " (" << params << ")";
3657 if(showExpression)
3658 {
3659 padLine(outputBuffer, 20);
3660
3661 if(produces > 0)
3662 {
3663 std::ostringstream buf;
3664 const char *paramsep = ",", *suff = "";
3665 int prio = 0; bool commutative = false;
3666 switch(opcode)
3667 {
3668 case cIf: buf << "if("; suff = ")";
3669 break;
3670 case cAbsIf: buf << "if("; suff = ")";
3671 break;
3672 case cOr: prio = 6; paramsep = "|"; commutative = true;
3673 break;
3674 case cAnd: prio = 5; paramsep = "&"; commutative = true;
3675 break;
3676 case cAdd: prio = 4; paramsep = "+"; commutative = true;
3677 break;
3678 case cSub: prio = 4; paramsep = "-";
3679 break;
3680 case cMul: prio = 3; paramsep = "*"; commutative = true;
3681 break;
3682 case cDiv: prio = 3; paramsep = "/";
3683 break;
3684 case cPow: prio = 2; paramsep = "^";
3685 break;
3686 case cAbsOr: prio = 6; paramsep = "|"; commutative = true;
3687 break;
3688 case cAbsAnd: prio = 5; paramsep = "&"; commutative = true;
3689 break;
3690 case cSqr: prio = 2; suff = "^2";
3691 break;
3692 case cNeg: buf << "(-("; suff = "))";
3693 break;
3694 case cNot: buf << "(!("; suff = "))";
3695 break;
3696 default: buf << n << '('; suff = ")";
3697 }
3698
3699 const char* sep = "";
3700 for(unsigned a=0; a<params; ++a)
3701 {
3702 buf << sep;
3703 if(stack.size() + a < params)
3704 buf << "?";
3705 else
3706 {
3707 const std::pair<int,std::string>& prev =
3708 stack[stack.size() - params + a];
3709 if(prio > 0 && (prev.first > prio ||
3710 (prev.first==prio && !commutative)))
3711 buf << '(' << prev.second << ')';
3712 else
3713 buf << prev.second;
3714 }
3715 sep = paramsep;
3716 }
3717 if(stack.size() >= params)
3718 stack.resize(stack.size() - params);
3719 else
3720 stack.clear();
3721 buf << suff;
3722 stack.push_back(std::make_pair(prio, buf.str()));
3723 //if(n.size() <= 4 && !out_params) padLine(outputBuffer, 20);
3724 }
3725 //padLine(outputBuffer, 20);
3726 output << "= ";
3727 if(((opcode == cIf || opcode == cAbsIf) && params != 3)
3728 || opcode == cJump
3729 #ifdef FP_SUPPORT_OPTIMIZER
3730 || opcode == cNop
3731 #endif
3732 )
3733 output << "(void)";
3734 else if(stack.empty())
3735 output << "[?] ?";
3736 else
3737 output << '[' << (stack.size()-1) << ']'
3738 << stack.back().second;
3739 }
3740
3741 if(showExpression)
3742 {
3743 dest << outputBuffer.str() << std::endl;
3744 outputBuffer.str("");
3745 }
3746 else
3747 output << std::endl;
3748 }
3749 dest << std::flush;
3750 }
3751 #endif
3752
3753
3754 #ifndef FP_SUPPORT_OPTIMIZER
3755 template<typename Value_t>
Optimize()3756 void FunctionParserBase<Value_t>::Optimize()
3757 {
3758 // Do nothing if no optimizations are supported.
3759 }
3760 #endif
3761
3762
3763 #define FUNCTIONPARSER_INSTANTIATE_CLASS(type) \
3764 template class FunctionParserBase< type >;
3765
3766 #ifndef FP_DISABLE_DOUBLE_TYPE
3767 FUNCTIONPARSER_INSTANTIATE_CLASS(double)
3768 #endif
3769
3770 #ifdef FP_SUPPORT_FLOAT_TYPE
3771 FUNCTIONPARSER_INSTANTIATE_CLASS(float)
3772 #endif
3773
3774 #ifdef FP_SUPPORT_LONG_DOUBLE_TYPE
3775 FUNCTIONPARSER_INSTANTIATE_CLASS(long double)
3776 #endif
3777
3778 #ifdef FP_SUPPORT_LONG_INT_TYPE
3779 FUNCTIONPARSER_INSTANTIATE_CLASS(long)
3780 #endif
3781
3782 #ifdef FP_SUPPORT_MPFR_FLOAT_TYPE
3783 FUNCTIONPARSER_INSTANTIATE_CLASS(MpfrFloat)
3784 #endif
3785
3786 #ifdef FP_SUPPORT_GMP_INT_TYPE
3787 FUNCTIONPARSER_INSTANTIATE_CLASS(GmpInt)
3788 #endif
3789
3790 #ifdef FP_SUPPORT_COMPLEX_DOUBLE_TYPE
3791 FUNCTIONPARSER_INSTANTIATE_CLASS(std::complex<double>)
3792 #endif
3793
3794 #ifdef FP_SUPPORT_COMPLEX_FLOAT_TYPE
3795 FUNCTIONPARSER_INSTANTIATE_CLASS(std::complex<float>)
3796 #endif
3797
3798 #ifdef FP_SUPPORT_COMPLEX_LONG_DOUBLE_TYPE
3799 FUNCTIONPARSER_INSTANTIATE_CLASS(std::complex<long double>)
3800 #endif
3801