diff options
author | Thales Lima Oliveira <thaleslima.ufu@gmail.com> | 2017-12-31 18:00:25 -0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2017-12-31 18:00:25 -0200 |
commit | 0c0280cfcf540f943fd2dbfdf7ac0304ea96a465 (patch) | |
tree | 51c89fc8155dcc447743dc89a1ab5ce36acc72cf /Project/fparser/fparser.cc | |
parent | c8193665975686fb8a344bee3dc94914a3d3558a (diff) | |
parent | dbe0b112622f8e91fa3e44a6b6e1aa7e230d3ded (diff) | |
download | PSP.git-0c0280cfcf540f943fd2dbfdf7ac0304ea96a465.tar.gz PSP.git-0c0280cfcf540f943fd2dbfdf7ac0304ea96a465.tar.xz PSP.git-0c0280cfcf540f943fd2dbfdf7ac0304ea96a465.zip |
Merge pull request #43 from Thales1330/wip/math-expr-control-block
Wip math expr control block
Diffstat (limited to 'Project/fparser/fparser.cc')
-rw-r--r-- | Project/fparser/fparser.cc | 3800 |
1 files changed, 3800 insertions, 0 deletions
diff --git a/Project/fparser/fparser.cc b/Project/fparser/fparser.cc new file mode 100644 index 0000000..5e77ba5 --- /dev/null +++ b/Project/fparser/fparser.cc @@ -0,0 +1,3800 @@ +/***************************************************************************\ +|* Function Parser for C++ v4.5.2 *| +|*-------------------------------------------------------------------------*| +|* Copyright: Juha Nieminen, Joel Yliluoma *| +|* *| +|* This library is distributed under the terms of the *| +|* GNU Lesser General Public License version 3. *| +|* (See lgpl.txt and gpl.txt for the license text.) *| +\***************************************************************************/ + +#include "fpconfig.hh" +#include "fparser.hh" + +#include <set> +#include <cstdlib> +#include <cstring> +#include <cctype> +#include <cmath> +#include <cassert> +#include <limits> + +#include "extrasrc/fptypes.hh" +#include "extrasrc/fpaux.hh" +using namespace FUNCTIONPARSERTYPES; + +#ifdef FP_USE_THREAD_SAFE_EVAL_WITH_ALLOCA +#ifndef FP_USE_THREAD_SAFE_EVAL +#define FP_USE_THREAD_SAFE_EVAL +#endif +#endif + +#ifdef __GNUC__ +# define likely(x) __builtin_expect(!!(x), 1) +# define unlikely(x) __builtin_expect(!!(x), 0) +#else +# define likely(x) (x) +# define unlikely(x) (x) +#endif + +//========================================================================= +// Opcode analysis functions +//========================================================================= +// These functions are used by the Parse() bytecode optimizer (mostly from +// code in fp_opcode_add.inc). + +bool FUNCTIONPARSERTYPES::IsLogicalOpcode(unsigned op) +{ + switch(op) + { + case cAnd: case cAbsAnd: + case cOr: case cAbsOr: + case cNot: case cAbsNot: + case cNotNot: case cAbsNotNot: + case cEqual: case cNEqual: + case cLess: case cLessOrEq: + case cGreater: case cGreaterOrEq: + return true; + default: break; + } + return false; +} + +bool FUNCTIONPARSERTYPES::IsComparisonOpcode(unsigned op) +{ + switch(op) + { + case cEqual: case cNEqual: + case cLess: case cLessOrEq: + case cGreater: case cGreaterOrEq: + return true; + default: break; + } + return false; +} + +unsigned FUNCTIONPARSERTYPES::OppositeComparisonOpcode(unsigned op) +{ + switch(op) + { + case cLess: return cGreater; + case cGreater: return cLess; + case cLessOrEq: return cGreaterOrEq; + case cGreaterOrEq: return cLessOrEq; + } + return op; +} + +bool FUNCTIONPARSERTYPES::IsNeverNegativeValueOpcode(unsigned op) +{ + switch(op) + { + case cAnd: case cAbsAnd: + case cOr: case cAbsOr: + case cNot: case cAbsNot: + case cNotNot: case cAbsNotNot: + case cEqual: case cNEqual: + case cLess: case cLessOrEq: + case cGreater: case cGreaterOrEq: + case cSqrt: case cRSqrt: case cSqr: + case cHypot: + case cAbs: + case cAcos: case cCosh: + return true; + default: break; + } + return false; +} + +bool FUNCTIONPARSERTYPES::IsAlwaysIntegerOpcode(unsigned op) +{ + switch(op) + { + case cAnd: case cAbsAnd: + case cOr: case cAbsOr: + case cNot: case cAbsNot: + case cNotNot: case cAbsNotNot: + case cEqual: case cNEqual: + case cLess: case cLessOrEq: + case cGreater: case cGreaterOrEq: + case cInt: case cFloor: case cCeil: case cTrunc: + return true; + default: break; + } + return false; +} + +bool FUNCTIONPARSERTYPES::IsUnaryOpcode(unsigned op) +{ + switch(op) + { + case cInv: case cNeg: + case cNot: case cAbsNot: + case cNotNot: case cAbsNotNot: + case cSqr: case cRSqrt: + case cDeg: case cRad: + return true; + } + return (op < FUNC_AMOUNT && Functions[op].params == 1); +} + +bool FUNCTIONPARSERTYPES::IsBinaryOpcode(unsigned op) +{ + switch(op) + { + case cAdd: case cSub: case cRSub: + case cMul: case cDiv: case cRDiv: + case cMod: + case cEqual: case cNEqual: case cLess: + case cLessOrEq: case cGreater: case cGreaterOrEq: + case cAnd: case cAbsAnd: + case cOr: case cAbsOr: + return true; + } + return (op < FUNC_AMOUNT && Functions[op].params == 2); +} + +bool FUNCTIONPARSERTYPES::IsVarOpcode(unsigned op) +{ + // See comment in declaration of FP_ParamGuardMask + return int(op) >= VarBegin; +} + +bool FUNCTIONPARSERTYPES::IsCommutativeOrParamSwappableBinaryOpcode(unsigned op) +{ + switch(op) + { + case cAdd: + case cMul: + case cEqual: case cNEqual: + case cAnd: case cAbsAnd: + case cOr: case cAbsOr: + case cMin: case cMax: case cHypot: + return true; + case cDiv: case cSub: case cRDiv: case cRSub: + return true; + case cLess: case cGreater: + case cLessOrEq: case cGreaterOrEq: return true; + } + return false; +} + +unsigned FUNCTIONPARSERTYPES::GetParamSwappedBinaryOpcode(unsigned op) +{ + switch(op) + { + case cAdd: + case cMul: + case cEqual: case cNEqual: + case cAnd: case cAbsAnd: + case cOr: case cAbsOr: + case cMin: case cMax: case cHypot: + return op; + case cDiv: return cRDiv; + case cSub: return cRSub; + case cRDiv: return cDiv; + case cRSub: return cSub; + case cLess: return cGreater; + case cGreater: return cLess; + case cLessOrEq: return cGreaterOrEq; + case cGreaterOrEq: return cLessOrEq; + } + return op; // Error +} + +template<bool ComplexType> +bool FUNCTIONPARSERTYPES::HasInvalidRangesOpcode(unsigned op) +{ + // Returns true, if the given opcode has a range of + // input values that gives an error. + if(ComplexType) + { + // COMPLEX: + switch(op) + { + case cAtan: // allowed range: x != +-1i + case cAtanh: // allowed range: x != +-1 + //case cCot: // allowed range: tan(x) != 0 + //case cCsc: // allowed range: sin(x) != 0 + case cLog: // allowed range: x != 0 + case cLog2: // allowed range: x != 0 + case cLog10: // allowed range: x != 0 + #ifdef FP_SUPPORT_OPTIMIZER + case cLog2by:// allowed range: x != 0 + #endif + //case cPow: // allowed when: x != 0 or y != 0 + //case cSec: // allowed range: cos(x) != 0 + //case cTan: // allowed range: cos(x) != 0 --> x != +-(pi/2) + //case cTanh: // allowed range: log(x) != -1 --> x != +-(pi/2)i + case cRSqrt: // allowed range: x != 0 + //case cDiv: // allowed range: y != 0 + //case cRDiv: // allowed range: x != 0 + //case cInv: // allowed range: x != 0 + return true; + } + } + else + { + // REAL: + switch(op) + { + case cAcos: // allowed range: |x| <= 1 + case cAsin: // allowed range: |x| <= 1 + case cAcosh: // allowed range: x >= 1 + case cAtanh: // allowed range: |x| < 1 + //case cCot: // allowed range: tan(x) != 0 + //case cCsc: // allowed range: sin(x) != 0 + case cLog: // allowed range: x > 0 + case cLog2: // allowed range: x > 0 + case cLog10: // allowed range: x > 0 + #ifdef FP_SUPPORT_OPTIMIZER + case cLog2by:// allowed range: x > 0 + #endif + //case cPow: // allowed when: x > 0 or (x = 0 and y != 0) or (x<0) + // Technically, when (x<0 and y is not integer), + // it is not allowed, but we allow it anyway + // in order to make nontrivial roots work. + //case cSec: // allowed range: cos(x) != 0 + case cSqrt: // allowed range: x >= 0 + case cRSqrt: // allowed range: x > 0 + //case cTan: // allowed range: cos(x) != 0 --> x != +-(pi/2) + //case cDiv: // allowed range: y != 0 + //case cRDiv: // allowed range: x != 0 + //case cInv: // allowed range: x != 0 + return true; + } + } + return false; +} + +template bool FUNCTIONPARSERTYPES::HasInvalidRangesOpcode<false>(unsigned op); +template bool FUNCTIONPARSERTYPES::HasInvalidRangesOpcode<true>(unsigned op); + + +#if(0) // Implementation moved to fpaux.hh due to linker problems +//========================================================================= +// Mathematical template functions +//========================================================================= +/* fp_pow() is a wrapper for std::pow() + * that produces an identical value for + * exp(1) ^ 2.0 (0x4000000000000000) + * as exp(2.0) (0x4000000000000000) + * - std::pow() on x86_64 + * produces 2.0 (0x3FFFFFFFFFFFFFFF) instead! + * See comments below for other special traits. + */ +namespace +{ + template<typename ValueT> + inline ValueT fp_pow_with_exp_log(const ValueT& x, const ValueT& y) + { + // Exponentiation using exp(log(x)*y). + // See http://en.wikipedia.org/wiki/Exponentiation#Real_powers + // Requirements: x > 0. + return fp_exp(fp_log(x) * y); + } + + template<typename ValueT> + inline ValueT fp_powi(ValueT x, unsigned long y) + { + // Fast binary exponentiation algorithm + // See http://en.wikipedia.org/wiki/Exponentiation_by_squaring + // Requirements: y is non-negative integer. + ValueT result(1); + while(y != 0) + { + if(y & 1) { result *= x; y -= 1; } + else { x *= x; y /= 2; } + } + return result; + } +} + +template<typename ValueT> +ValueT FUNCTIONPARSERTYPES::fp_pow(const ValueT& x, const ValueT& y) +{ + if(x == ValueT(1)) return ValueT(1); + // y is now zero or positive + if(isLongInteger(y)) + { + // Use fast binary exponentiation algorithm + if(y >= ValueT(0)) + return fp_powi(x, makeLongInteger(y)); + else + return ValueT(1) / fp_powi(x, -makeLongInteger(y)); + } + if(y >= ValueT(0)) + { + // y is now positive. Calculate using exp(log(x)*y). + if(x > ValueT(0)) return fp_pow_with_exp_log(x, y); + if(x == ValueT(0)) return ValueT(0); + // At this point, y > 0.0 and x is known to be < 0.0, + // because positive and zero cases are already handled. + if(!isInteger(y*ValueT(16))) + return -fp_pow_with_exp_log(-x, y); + // ^This is not technically correct, but it allows + // functions such as cbrt(x^5), that is, x^(5/3), + // to be evaluated when x is negative. + // It is too complicated (and slow) to test whether y + // is a formed from a ratio of an integer to an odd integer. + // (And due to floating point inaccuracy, pointless too.) + // For example, x^1.30769230769... is + // actually x^(17/13), i.e. (x^17) ^ (1/13). + // (-5)^(17/13) gives us now -8.204227562330453. + // To see whether the result is right, we can test the given + // root: (-8.204227562330453)^13 gives us the value of (-5)^17, + // which proves that the expression was correct. + // + // The y*16 check prevents e.g. (-4)^(3/2) from being calculated, + // as it would confuse functioninfo when pow() returns no error + // but sqrt() does when the formula is converted into sqrt(x)*x. + // + // The errors in this approach are: + // (-2)^sqrt(2) should produce NaN + // or actually sqrt(2)I + 2^sqrt(2), + // produces -(2^sqrt(2)) instead. + // (Impact: Neglible) + // Thus, at worst, we're changing a NaN (or complex) + // result into a negative real number result. + } + else + { + // y is negative. Utilize the x^y = 1/(x^-y) identity. + if(x > ValueT(0)) return fp_pow_with_exp_log(ValueT(1) / x, -y); + if(x < ValueT(0)) + { + if(!isInteger(y*ValueT(-16))) + return -fp_pow_with_exp_log(ValueT(-1) / x, -y); + // ^ See comment above. + } + // Remaining case: 0.0 ^ negative number + } + // This is reached when: + // x=0, and y<0 + // x<0, and y*16 is either positive or negative integer + // It is used for producing error values and as a safe fallback. + return fp_pow_base(x, y); +} +#endif + + +//========================================================================= +// Elementary (atom) parsing functions +//========================================================================= +namespace +{ + const unsigned FP_ParamGuardMask = 1U << (sizeof(unsigned) * 8u - 1u); + // ^ This mask is used to prevent cFetch/other opcode's parameters + // from being confused into opcodes or variable indices within the + // bytecode optimizer. Because the way it is tested in bytecoderules.dat + // for speed reasons, it must also be the sign-bit of the "int" datatype. + // Perhaps an "assert(IsVarOpcode(X | FP_ParamGuardMask) == false)" + // might be justified to put somewhere in the code, just in case? + + + /* Reads an UTF8-encoded sequence which forms a valid identifier name from + the given input string and returns its length. If bit 31 is set, the + return value also contains the internal function opcode (defined in + fptypes.hh) that matches the name. + */ + unsigned readIdentifierCommon(const char* input) + { + /* Assuming unsigned = 32 bits: + 76543210 76543210 76543210 76543210 + Return value if built-in function: + 1PPPPPPP PPPPPPPP LLLLLLLL LLLLLLLL + P = function opcode (15 bits) + L = function name length (16 bits) + Return value if not built-in function: + 0LLLLLLL LLLLLLLL LLLLLLLL LLLLLLLL + L = identifier length (31 bits) + If unsigned has more than 32 bits, the other + higher order bits are to be assumed zero. + */ +#include "extrasrc/fp_identifier_parser.inc" + return 0; + } + + template<typename Value_t> + inline unsigned readIdentifier(const char* input) + { + const unsigned value = readIdentifierCommon(input); + if( (value & 0x80000000U) != 0) // Function? + { + // Verify that the function actually exists for this datatype + if(IsIntType<Value_t>::result + && !Functions[(value >> 16) & 0x7FFF].okForInt()) + { + // If it does not exist, return it as an identifier instead + return value & 0xFFFFu; + } + if(!IsComplexType<Value_t>::result + && Functions[(value >> 16) & 0x7FFF].complexOnly()) + { + // If it does not exist, return it as an identifier instead + return value & 0xFFFFu; + } + } + return value; + } + + // Returns true if the entire string is a valid identifier + template<typename Value_t> + bool containsOnlyValidIdentifierChars(const std::string& name) + { + if(name.empty()) return false; + return readIdentifier<Value_t>(name.c_str()) == (unsigned) name.size(); + } + + + // ----------------------------------------------------------------------- + // Wrappers for strto... functions + // ----------------------------------------------------------------------- + template<typename Value_t> + inline Value_t fp_parseLiteral(const char* str, char** endptr) + { + return std::strtod(str, endptr); + } + +#if defined(FP_USE_STRTOLD) || defined(FP_SUPPORT_CPLUSPLUS11_MATH_FUNCS) + template<> + inline long double fp_parseLiteral<long double>(const char* str, + char** endptr) + { + using namespace std; // Just in case strtold() is not inside std:: + return strtold(str, endptr); + } +#endif + +#ifdef FP_SUPPORT_LONG_INT_TYPE + template<> + inline long fp_parseLiteral<long>(const char* str, char** endptr) + { + return std::strtol(str, endptr, 10); + } +#endif + +#ifdef FP_SUPPORT_COMPLEX_NUMBERS + template<typename T> + inline std::complex<T> fp_parseComplexLiteral(const char* str, + char** endptr) + { + T result = fp_parseLiteral<T> (str,endptr); + const char* end = *endptr; + if( (*end == 'i' || *end == 'I') + && !std::isalnum(end[1]) ) + { + ++*endptr; + return std::complex<T> (T(), result); + } + return std::complex<T> (result, T()); + } +#endif + +#ifdef FP_SUPPORT_COMPLEX_DOUBLE_TYPE + template<> + inline std::complex<double> fp_parseLiteral<std::complex<double> > + (const char* str, char** endptr) + { + return fp_parseComplexLiteral<double> (str,endptr); + } +#endif + +#ifdef FP_SUPPORT_COMPLEX_FLOAT_TYPE + template<> + inline std::complex<float> fp_parseLiteral<std::complex<float> > + (const char* str, char** endptr) + { + return fp_parseComplexLiteral<float> (str,endptr); + } +#endif + +#ifdef FP_SUPPORT_COMPLEX_LONG_DOUBLE_TYPE + template<> + inline std::complex<long double> fp_parseLiteral<std::complex<long double> > + (const char* str, char** endptr) + { + return fp_parseComplexLiteral<long double> (str,endptr); + } +#endif + + // ----------------------------------------------------------------------- + // Hexadecimal floating point literal parsing + // ----------------------------------------------------------------------- + inline int testXdigit(unsigned c) + { + if((c-'0') < 10u) return c&15; // 0..9 + if(((c|0x20)-'a') < 6u) return 9+(c&15); // A..F or a..f + return -1; // Not a hex digit + } + + template<typename elem_t, unsigned n_limbs, unsigned limb_bits> + inline void addXdigit(elem_t* buffer, unsigned nibble) + { + for(unsigned p=0; p<n_limbs; ++p) + { + unsigned carry = unsigned( buffer[p] >> (elem_t)(limb_bits-4) ); + buffer[p] = (buffer[p] << 4) | nibble; + nibble = carry; + } + } + + template<typename Value_t> + Value_t parseHexLiteral(const char* str, char** endptr) + { + const unsigned bits_per_char = 8; + + const int MantissaBits = + std::numeric_limits<Value_t>::radix == 2 + ? std::numeric_limits<Value_t>::digits + : (((sizeof(Value_t) * bits_per_char) &~ 3) - 4); + + typedef unsigned long elem_t; + const int ExtraMantissaBits = 4 + ((MantissaBits+3)&~3); // Store one digit more for correct rounding + const unsigned limb_bits = sizeof(elem_t) * bits_per_char; + const unsigned n_limbs = (ExtraMantissaBits + limb_bits-1) / limb_bits; + elem_t mantissa_buffer[n_limbs] = { 0 }; + + int n_mantissa_bits = 0; // Track the number of bits + int exponent = 0; // The exponent that will be used to multiply the mantissa + // Read integer portion + while(true) + { + int xdigit = testXdigit(*str); + if(xdigit < 0) break; + addXdigit<elem_t,n_limbs,limb_bits> (mantissa_buffer, xdigit); + ++str; + + n_mantissa_bits += 4; + if(n_mantissa_bits >= ExtraMantissaBits) + { + // Exhausted the precision. Parse the rest (until exponent) + // normally but ignore the actual digits. + for(; testXdigit(*str) >= 0; ++str) + exponent += 4; + // Read but ignore decimals + if(*str == '.') + for(++str; testXdigit(*str) >= 0; ++str) + {} + goto read_exponent; + } + } + // Read decimals + if(*str == '.') + for(++str; ; ) + { + int xdigit = testXdigit(*str); + if(xdigit < 0) break; + addXdigit<elem_t,n_limbs,limb_bits> (mantissa_buffer, xdigit); + ++str; + + exponent -= 4; + n_mantissa_bits += 4; + if(n_mantissa_bits >= ExtraMantissaBits) + { + // Exhausted the precision. Skip the rest + // of the decimals, until the exponent. + while(testXdigit(*str) >= 0) + ++str; + break; + } + } + + // Read exponent + read_exponent: + if(*str == 'p' || *str == 'P') + { + const char* str2 = str+1; + long p_exponent = strtol(str2, const_cast<char**> (&str2), 10); + if(str2 != str+1 && p_exponent == (long)(int)p_exponent) + { + exponent += (int)p_exponent; + str = str2; + } + } + + if(endptr) *endptr = const_cast<char*> (str); + + Value_t result = std::ldexp(Value_t(mantissa_buffer[0]), exponent); + for(unsigned p=1; p<n_limbs; ++p) + { + exponent += limb_bits; + result += ldexp(Value_t(mantissa_buffer[p]), exponent); + } + return result; + } + +#ifdef FP_SUPPORT_LONG_INT_TYPE + template<> + long parseHexLiteral<long>(const char* str, char** endptr) + { + return std::strtol(str, endptr, 16); + } +#endif + +#ifdef FP_SUPPORT_COMPLEX_DOUBLE_TYPE + template<> + std::complex<double> + parseHexLiteral<std::complex<double> >(const char* str, char** endptr) + { + return parseHexLiteral<double> (str, endptr); + } +#endif + +#ifdef FP_SUPPORT_COMPLEX_FLOAT_TYPE + template<> + std::complex<float> + parseHexLiteral<std::complex<float> >(const char* str, char** endptr) + { + return parseHexLiteral<float> (str, endptr); + } +#endif + +#ifdef FP_SUPPORT_COMPLEX_LONG_DOUBLE_TYPE + template<> + std::complex<long double> + parseHexLiteral<std::complex<long double> >(const char* str, char** endptr) + { + return parseHexLiteral<long double> (str, endptr); + } +#endif +} + +//========================================================================= +// Utility functions +//========================================================================= +namespace +{ + // ----------------------------------------------------------------------- + // Add a new identifier to the specified identifier map + // ----------------------------------------------------------------------- + // Return value will be false if the name already existed + template<typename Value_t> + bool addNewNameData(NamePtrsMap<Value_t>& namePtrs, + std::pair<NamePtr, NameData<Value_t> >& newName, + bool isVar) + { + typename NamePtrsMap<Value_t>::iterator nameIter = + namePtrs.lower_bound(newName.first); + + if(nameIter != namePtrs.end() && newName.first == nameIter->first) + { + // redefining a var is not allowed. + if(isVar) return false; + + // redefining other tokens is allowed, if the type stays the same. + if(nameIter->second.type != newName.second.type) + return false; + + // update the data + nameIter->second = newName.second; + return true; + } + + if(!isVar) + { + // Allocate a copy of the name (pointer stored in the map key) + // However, for VARIABLEs, the pointer points to VariableString, + // which is managed separately. Thusly, only done when !IsVar. + char* namebuf = new char[newName.first.nameLength]; + memcpy(namebuf, newName.first.name, newName.first.nameLength); + newName.first.name = namebuf; + } + + namePtrs.insert(nameIter, newName); + return true; + } +} + + +//========================================================================= +// Data struct implementation +//========================================================================= +template<typename Value_t> +FunctionParserBase<Value_t>::Data::Data(): + mReferenceCounter(1), + mDelimiterChar(0), + mParseErrorType(NO_FUNCTION_PARSED_YET), + mEvalErrorType(0), + mUseDegreeConversion(false), + mErrorLocation(0), + mVariablesAmount(0), + mStackSize(0) +{} + +template<typename Value_t> +FunctionParserBase<Value_t>::Data::Data(const Data& rhs): + mReferenceCounter(0), + mDelimiterChar(rhs.mDelimiterChar), + mParseErrorType(rhs.mParseErrorType), + mEvalErrorType(rhs.mEvalErrorType), + mUseDegreeConversion(rhs.mUseDegreeConversion), + mErrorLocation(rhs.mErrorLocation), + mVariablesAmount(rhs.mVariablesAmount), + mVariablesString(rhs.mVariablesString), + mNamePtrs(), + mFuncPtrs(rhs.mFuncPtrs), + mFuncParsers(rhs.mFuncParsers), + mByteCode(rhs.mByteCode), + mImmed(rhs.mImmed), +#ifndef FP_USE_THREAD_SAFE_EVAL + mStack(rhs.mStackSize), +#endif + mStackSize(rhs.mStackSize) +{ + for(typename NamePtrsMap<Value_t>::const_iterator i = rhs.mNamePtrs.begin(); + i != rhs.mNamePtrs.end(); + ++i) + { + if(i->second.type == NameData<Value_t>::VARIABLE) + { + const std::size_t variableStringOffset = + i->first.name - rhs.mVariablesString.c_str(); + std::pair<NamePtr, NameData<Value_t> > tmp + (NamePtr(&mVariablesString[variableStringOffset], + i->first.nameLength), + i->second); + mNamePtrs.insert(mNamePtrs.end(), tmp); + } + else + { + std::pair<NamePtr, NameData<Value_t> > tmp + (NamePtr(new char[i->first.nameLength], i->first.nameLength), + i->second ); + memcpy(const_cast<char*>(tmp.first.name), i->first.name, + tmp.first.nameLength); + mNamePtrs.insert(mNamePtrs.end(), tmp); + } + } +} + +template<typename Value_t> +FunctionParserBase<Value_t>::Data::~Data() +{ + for(typename NamePtrsMap<Value_t>::iterator i = mNamePtrs.begin(); + i != mNamePtrs.end(); + ++i) + { + if(i->second.type != NameData<Value_t>::VARIABLE) + delete[] i->first.name; + } +} + +template<typename Value_t> +void FunctionParserBase<Value_t>::incFuncWrapperRefCount +(FunctionWrapper* wrapper) +{ + ++wrapper->mReferenceCount; +} + +template<typename Value_t> +unsigned FunctionParserBase<Value_t>::decFuncWrapperRefCount +(FunctionWrapper* wrapper) +{ + return --wrapper->mReferenceCount; +} + +template<typename Value_t> +FunctionParserBase<Value_t>::Data::FuncWrapperPtrData::FuncWrapperPtrData(): + mRawFuncPtr(0), mFuncWrapperPtr(0), mParams(0) +{} + +template<typename Value_t> +FunctionParserBase<Value_t>::Data::FuncWrapperPtrData::~FuncWrapperPtrData() +{ + if(mFuncWrapperPtr && + FunctionParserBase::decFuncWrapperRefCount(mFuncWrapperPtr) == 0) + delete mFuncWrapperPtr; +} + +template<typename Value_t> +FunctionParserBase<Value_t>::Data::FuncWrapperPtrData::FuncWrapperPtrData +(const FuncWrapperPtrData& rhs): + mRawFuncPtr(rhs.mRawFuncPtr), + mFuncWrapperPtr(rhs.mFuncWrapperPtr), + mParams(rhs.mParams) +{ + if(mFuncWrapperPtr) + FunctionParserBase::incFuncWrapperRefCount(mFuncWrapperPtr); +} + +template<typename Value_t> +typename FunctionParserBase<Value_t>::Data::FuncWrapperPtrData& +FunctionParserBase<Value_t>::Data::FuncWrapperPtrData::operator= +(const FuncWrapperPtrData& rhs) +{ + if(&rhs != this) + { + if(mFuncWrapperPtr && + FunctionParserBase::decFuncWrapperRefCount(mFuncWrapperPtr) == 0) + delete mFuncWrapperPtr; + mRawFuncPtr = rhs.mRawFuncPtr; + mFuncWrapperPtr = rhs.mFuncWrapperPtr; + mParams = rhs.mParams; + if(mFuncWrapperPtr) + FunctionParserBase::incFuncWrapperRefCount(mFuncWrapperPtr); + } + return *this; +} + + +//========================================================================= +// FunctionParser constructors, destructor and assignment +//========================================================================= +template<typename Value_t> +FunctionParserBase<Value_t>::FunctionParserBase(): + mData(new Data), + mStackPtr(0) +{ +} + +template<typename Value_t> +FunctionParserBase<Value_t>::~FunctionParserBase() +{ + if(--(mData->mReferenceCounter) == 0) + delete mData; +} + +template<typename Value_t> +FunctionParserBase<Value_t>::FunctionParserBase(const FunctionParserBase& cpy): + mData(cpy.mData), + mStackPtr(0) +{ + ++(mData->mReferenceCounter); +} + +template<typename Value_t> +FunctionParserBase<Value_t>& +FunctionParserBase<Value_t>::operator=(const FunctionParserBase& cpy) +{ + if(mData != cpy.mData) + { + if(--(mData->mReferenceCounter) == 0) delete mData; + + mData = cpy.mData; + ++(mData->mReferenceCounter); + } + return *this; +} + +template<typename Value_t> +typename FunctionParserBase<Value_t>::Data* +FunctionParserBase<Value_t>::getParserData() +{ + return mData; +} + +template<typename Value_t> +void FunctionParserBase<Value_t>::setDelimiterChar(char c) +{ + mData->mDelimiterChar = c; +} + + +//--------------------------------------------------------------------------- +// Copy-on-write method +//--------------------------------------------------------------------------- +template<typename Value_t> +void FunctionParserBase<Value_t>::CopyOnWrite() +{ + if(mData->mReferenceCounter > 1) + { + Data* oldData = mData; + mData = new Data(*oldData); + --(oldData->mReferenceCounter); + mData->mReferenceCounter = 1; + } +} + +template<typename Value_t> +void FunctionParserBase<Value_t>::ForceDeepCopy() +{ + CopyOnWrite(); +} + + +//========================================================================= +// Epsilon +//========================================================================= +template<typename Value_t> +Value_t FunctionParserBase<Value_t>::epsilon() +{ + return Epsilon<Value_t>::value; +} + +template<typename Value_t> +void FunctionParserBase<Value_t>::setEpsilon(Value_t value) +{ + Epsilon<Value_t>::value = value; +} + + +//========================================================================= +// User-defined identifier addition functions +//========================================================================= +template<typename Value_t> +bool FunctionParserBase<Value_t>::AddConstant(const std::string& name, + Value_t value) +{ + if(!containsOnlyValidIdentifierChars<Value_t>(name)) return false; + + CopyOnWrite(); + std::pair<NamePtr, NameData<Value_t> > newName + (NamePtr(name.data(), unsigned(name.size())), + NameData<Value_t>(NameData<Value_t>::CONSTANT, value)); + + return addNewNameData(mData->mNamePtrs, newName, false); +} + +template<typename Value_t> +bool FunctionParserBase<Value_t>::AddUnit(const std::string& name, + Value_t value) +{ + if(!containsOnlyValidIdentifierChars<Value_t>(name)) return false; + + CopyOnWrite(); + std::pair<NamePtr, NameData<Value_t> > newName + (NamePtr(name.data(), unsigned(name.size())), + NameData<Value_t>(NameData<Value_t>::UNIT, value)); + return addNewNameData(mData->mNamePtrs, newName, false); +} + +template<typename Value_t> +bool FunctionParserBase<Value_t>::AddFunction +(const std::string& name, FunctionPtr ptr, unsigned paramsAmount) +{ + if(!containsOnlyValidIdentifierChars<Value_t>(name)) return false; + + CopyOnWrite(); + std::pair<NamePtr, NameData<Value_t> > newName + (NamePtr(name.data(), unsigned(name.size())), + NameData<Value_t>(NameData<Value_t>::FUNC_PTR, + unsigned(mData->mFuncPtrs.size()))); + + const bool success = addNewNameData(mData->mNamePtrs, newName, false); + if(success) + { + mData->mFuncPtrs.push_back(typename Data::FuncWrapperPtrData()); + mData->mFuncPtrs.back().mRawFuncPtr = ptr; + mData->mFuncPtrs.back().mParams = paramsAmount; + } + return success; +} + +template<typename Value_t> +bool FunctionParserBase<Value_t>::addFunctionWrapperPtr +(const std::string& name, FunctionWrapper* wrapper, unsigned paramsAmount) +{ + if(!AddFunction(name, FunctionPtr(0), paramsAmount)) return false; + mData->mFuncPtrs.back().mFuncWrapperPtr = wrapper; + return true; +} + +template<typename Value_t> +typename FunctionParserBase<Value_t>::FunctionWrapper* +FunctionParserBase<Value_t>::GetFunctionWrapper(const std::string& name) +{ + CopyOnWrite(); + NamePtr namePtr(name.data(), unsigned(name.size())); + + typename NamePtrsMap<Value_t>::iterator nameIter = + mData->mNamePtrs.find(namePtr); + + if(nameIter != mData->mNamePtrs.end() && + nameIter->second.type == NameData<Value_t>::FUNC_PTR) + { + return mData->mFuncPtrs[nameIter->second.index].mFuncWrapperPtr; + } + return 0; +} + +template<typename Value_t> +bool FunctionParserBase<Value_t>::CheckRecursiveLinking +(const FunctionParserBase* fp) const +{ + if(fp == this) return true; + for(unsigned i = 0; i < fp->mData->mFuncParsers.size(); ++i) + if(CheckRecursiveLinking(fp->mData->mFuncParsers[i].mParserPtr)) + return true; + return false; +} + +template<typename Value_t> +bool FunctionParserBase<Value_t>::AddFunction(const std::string& name, + FunctionParserBase& fp) +{ + if(!containsOnlyValidIdentifierChars<Value_t>(name) || + CheckRecursiveLinking(&fp)) + return false; + + CopyOnWrite(); + std::pair<NamePtr, NameData<Value_t> > newName + (NamePtr(name.data(), unsigned(name.size())), + NameData<Value_t>(NameData<Value_t>::PARSER_PTR, + unsigned(mData->mFuncParsers.size()))); + + const bool success = addNewNameData(mData->mNamePtrs, newName, false); + if(success) + { + mData->mFuncParsers.push_back(typename Data::FuncParserPtrData()); + mData->mFuncParsers.back().mParserPtr = &fp; + mData->mFuncParsers.back().mParams = fp.mData->mVariablesAmount; + } + return success; +} + +template<typename Value_t> +bool FunctionParserBase<Value_t>::RemoveIdentifier(const std::string& name) +{ + CopyOnWrite(); + + NamePtr namePtr(name.data(), unsigned(name.size())); + + typename NamePtrsMap<Value_t>::iterator nameIter = + mData->mNamePtrs.find(namePtr); + + if(nameIter != mData->mNamePtrs.end()) + { + if(nameIter->second.type == NameData<Value_t>::VARIABLE) + { + // Illegal attempt to delete variables + return false; + } + delete[] nameIter->first.name; + mData->mNamePtrs.erase(nameIter); + return true; + } + return false; +} + + +//========================================================================= +// Function parsing +//========================================================================= +namespace +{ + // Error messages returned by ErrorMsg(): + const char* const ParseErrorMessage[]= + { + "Syntax error", // 0 + "Mismatched parenthesis", // 1 + "Missing ')'", // 2 + "Empty parentheses", // 3 + "Syntax error: Operator expected", // 4 + "Not enough memory", // 5 + "An unexpected error occurred. Please make a full bug report " + "to the author", // 6 + "Syntax error in parameter 'Vars' given to " + "FunctionParser::Parse()", // 7 + "Illegal number of parameters to function", // 8 + "Syntax error: Premature end of string", // 9 + "Syntax error: Expecting ( after function", // 10 + "Syntax error: Unknown identifier", // 11 + "(No function has been parsed yet)", + "" + }; + + template<typename Value_t> + inline typename FunctionParserBase<Value_t>::ParseErrorType + noCommaError(char c) + { + return c == ')' ? + FunctionParserBase<Value_t>::ILL_PARAMS_AMOUNT : + FunctionParserBase<Value_t>::SYNTAX_ERROR; + } + + template<typename Value_t> + inline typename FunctionParserBase<Value_t>::ParseErrorType + noParenthError(char c) + { + return c == ',' ? + FunctionParserBase<Value_t>::ILL_PARAMS_AMOUNT : + FunctionParserBase<Value_t>::MISSING_PARENTH; + } + + template<unsigned offset> + struct IntLiteralMask + { + enum { mask = + // ( 1UL << ('-'-offset)) | + (0x3FFUL << ('0'-offset)) }; /* 0x3FF = 10 bits worth "1" */ + // Note: If you change fparser to support negative numbers parsing + // (as opposed to parsing them as cNeg followed by literal), + // enable the '-' line above, and change the offset value + // in BeginsLiteral() to '-' instead of '.'. + }; + + template<typename Value_t, unsigned offset> + struct LiteralMask + { + enum { mask = + ( 1UL << ('.'-offset)) | + IntLiteralMask<offset>::mask }; + }; +#ifdef FP_SUPPORT_LONG_INT_TYPE + template<unsigned offset> + struct LiteralMask<long, offset>: public IntLiteralMask<offset> + { + }; +#endif +#ifdef FP_SUPPORT_GMP_INT_TYPE + template<unsigned offset> + struct LiteralMask<GmpInt, offset>: public IntLiteralMask<offset> + { + }; +#endif + + template<unsigned offset> + struct SimpleSpaceMask + { + enum { mask = + (1UL << ('\r'-offset)) | + (1UL << ('\n'-offset)) | + (1UL << ('\v'-offset)) | + (1UL << ('\t'-offset)) | + (1UL << (' ' -offset)) }; + }; + + template<typename Value_t> + inline bool BeginsLiteral(unsigned byte) + { + enum { n = sizeof(unsigned long)>=8 ? 0 : '.' }; + byte -= n; + if(byte > (unsigned char)('9'-n)) return false; + unsigned long shifted = 1UL << byte; + const unsigned long mask = LiteralMask<Value_t, n>::mask; + return (mask & shifted) != 0; + } + + template<typename CharPtr> + inline void SkipSpace(CharPtr& function) + { +/* + Space characters in unicode: +U+0020 SPACE Depends on font, often adjusted (see below) +U+00A0 NO-BREAK SPACE As a space, but often not adjusted +U+2000 EN QUAD 1 en (= 1/2 em) +U+2001 EM QUAD 1 em (nominally, the height of the font) +U+2002 EN SPACE 1 en (= 1/2 em) +U+2003 EM SPACE 1 em +U+2004 THREE-PER-EM SPACE 1/3 em +U+2005 FOUR-PER-EM SPACE 1/4 em +U+2006 SIX-PER-EM SPACE 1/6 em +U+2007 FIGURE SPACE Tabular width, the width of digits +U+2008 PUNCTUATION SPACE The width of a period . +U+2009 THIN SPACE 1/5 em (or sometimes 1/6 em) +U+200A HAIR SPACE Narrower than THIN SPACE +U+200B ZERO WIDTH SPACE Nominally no width, but may expand +U+202F NARROW NO-BREAK SPACE Narrower than NO-BREAK SPACE (or SPACE) +U+205F MEDIUM MATHEMATICAL SPACE 4/18 em +U+3000 IDEOGRAPHIC SPACE The width of ideographic (CJK) characters. + Also: +U+000A \n +U+000D \r +U+0009 \t +U+000B \v + As UTF-8 sequences: + 09 + 0A + 0B + 0D + 20 + C2 A0 + E2 80 80-8B + E2 80 AF + E2 81 9F + E3 80 80 +*/ + while(true) + { + enum { n = sizeof(unsigned long)>=8 ? 0 : '\t' }; + typedef signed char schar; + unsigned byte = (unsigned char)*function; + byte -= n; + // ^Note: values smaller than n intentionally become + // big values here due to integer wrap. The + // comparison below thus excludes them, making + // the effective range 0x09..0x20 (32-bit) + // or 0x00..0x20 (64-bit) within the if-clause. + if(byte <= (unsigned char)(' '-n)) + { + unsigned long shifted = 1UL << byte; + const unsigned long mask = SimpleSpaceMask<n>::mask; + if(mask & shifted) + { ++function; continue; } // \r, \n, \t, \v and space + break; + } + if(likely(byte < 0xC2-n)) break; + + if(byte == 0xC2-n && function[1] == char(0xA0)) + { function += 2; continue; } // U+00A0 + if(byte == 0xE3-n && + function[1] == char(0x80) && function[2] == char(0x80)) + { function += 3; continue; } // U+3000 + if(byte == 0xE2-n) + { + if(function[1] == char(0x81)) + { + if(function[2] != char(0x9F)) break; + function += 3; // U+205F + continue; + } + if(function[1] == char(0x80)) + if(function[2] == char(0xAF) || // U+202F + schar(function[2]) <= schar(0x8B) // U+2000..U+200B + ) + { + function += 3; + continue; + } + } + break; + } // while(true) + } // SkipSpace(CharPtr& function) +} + +// --------------------------------------------------------------------------- +// Return parse error message +// --------------------------------------------------------------------------- +template<typename Value_t> +const char* FunctionParserBase<Value_t>::ErrorMsg() const +{ + return ParseErrorMessage[mData->mParseErrorType]; +} + +template<typename Value_t> +typename FunctionParserBase<Value_t>::ParseErrorType +FunctionParserBase<Value_t>::GetParseErrorType() const +{ + return mData->mParseErrorType; +} + +template<typename Value_t> +int FunctionParserBase<Value_t>::EvalError() const +{ + return mData->mEvalErrorType; +} + + +// --------------------------------------------------------------------------- +// Parse variables +// --------------------------------------------------------------------------- +template<typename Value_t> +bool FunctionParserBase<Value_t>::ParseVariables +(const std::string& inputVarString) +{ + if(mData->mVariablesString == inputVarString) return true; + + /* Delete existing variables from mNamePtrs */ + for(typename NamePtrsMap<Value_t>::iterator i = + mData->mNamePtrs.begin(); + i != mData->mNamePtrs.end(); ) + { + if(i->second.type == NameData<Value_t>::VARIABLE) + { + typename NamePtrsMap<Value_t>::iterator j (i); + ++i; + mData->mNamePtrs.erase(j); + } + else ++i; + } + mData->mVariablesString = inputVarString; + + const std::string& vars = mData->mVariablesString; + const unsigned len = unsigned(vars.size()); + + unsigned varNumber = VarBegin; + + const char* beginPtr = vars.c_str(); + const char* finalPtr = beginPtr + len; + while(beginPtr < finalPtr) + { + SkipSpace(beginPtr); + unsigned nameLength = readIdentifier<Value_t>(beginPtr); + if(nameLength == 0 || (nameLength & 0x80000000U)) return false; + const char* endPtr = beginPtr + nameLength; + SkipSpace(endPtr); + if(endPtr != finalPtr && *endPtr != ',') return false; + + std::pair<NamePtr, NameData<Value_t> > newName + (NamePtr(beginPtr, nameLength), + NameData<Value_t>(NameData<Value_t>::VARIABLE, varNumber++)); + + if(!addNewNameData(mData->mNamePtrs, newName, true)) + { + return false; + } + + beginPtr = endPtr + 1; + } + + mData->mVariablesAmount = varNumber - VarBegin; + return true; +} + +// --------------------------------------------------------------------------- +// Parse() public interface functions +// --------------------------------------------------------------------------- +template<typename Value_t> +int FunctionParserBase<Value_t>::Parse(const char* Function, + const std::string& Vars, + bool useDegrees) +{ + CopyOnWrite(); + + if(!ParseVariables(Vars)) + { + mData->mParseErrorType = INVALID_VARS; + return int(strlen(Function)); + } + + return ParseFunction(Function, useDegrees); +} + +template<typename Value_t> +int FunctionParserBase<Value_t>::Parse(const std::string& Function, + const std::string& Vars, + bool useDegrees) +{ + CopyOnWrite(); + + if(!ParseVariables(Vars)) + { + mData->mParseErrorType = INVALID_VARS; + return int(Function.size()); + } + + return ParseFunction(Function.c_str(), useDegrees); +} + + +// --------------------------------------------------------------------------- +// Main parsing function +// --------------------------------------------------------------------------- +template<typename Value_t> +int FunctionParserBase<Value_t>::ParseFunction(const char* function, + bool useDegrees) +{ + mData->mUseDegreeConversion = useDegrees; + mData->mParseErrorType = FP_NO_ERROR; + + mData->mInlineVarNames.clear(); + mData->mByteCode.clear(); mData->mByteCode.reserve(128); + mData->mImmed.clear(); mData->mImmed.reserve(128); + mData->mStackSize = mStackPtr = 0; + + mData->mHasByteCodeFlags = false; + + const char* ptr = Compile(function); + mData->mInlineVarNames.clear(); + + if(mData->mHasByteCodeFlags) + { + for(unsigned i = unsigned(mData->mByteCode.size()); i-- > 0; ) + mData->mByteCode[i] &= ~FP_ParamGuardMask; + } + + if(mData->mParseErrorType != FP_NO_ERROR) + return int(mData->mErrorLocation - function); + + assert(ptr); // Should never be null at this point. It's a bug otherwise. + if(*ptr) + { + if(mData->mDelimiterChar == 0 || *ptr != mData->mDelimiterChar) + mData->mParseErrorType = EXPECT_OPERATOR; + return int(ptr - function); + } + +#ifndef FP_USE_THREAD_SAFE_EVAL + mData->mStack.resize(mData->mStackSize); +#endif + + return -1; +} + + +//========================================================================= +// Parsing and bytecode compiling functions +//========================================================================= +template<typename Value_t> +inline const char* FunctionParserBase<Value_t>::SetErrorType(ParseErrorType t, + const char* pos) +{ + mData->mParseErrorType = t; + mData->mErrorLocation = pos; + return 0; +} + +template<typename Value_t> +inline void FunctionParserBase<Value_t>::incStackPtr() +{ + if(++mStackPtr > mData->mStackSize) ++(mData->mStackSize); +} + +namespace +{ + const unsigned char powi_factor_table[128] = + { + 0,1,0,0,0,0,0,0, 0, 0,0,0,0,0,0,3,/* 0 - 15 */ + 0,0,0,0,0,0,0,0, 0, 5,0,3,0,0,3,0,/* 16 - 31 */ + 0,0,0,0,0,0,0,3, 0, 0,0,0,0,5,0,0,/* 32 - 47 */ + 0,0,5,3,0,0,3,5, 0, 3,0,0,3,0,0,3,/* 48 - 63 */ + 0,0,0,0,0,0,0,0, 0, 0,0,3,0,0,3,0,/* 64 - 79 */ + 0,9,0,0,0,5,0,3, 0, 0,5,7,0,0,0,5,/* 80 - 95 */ + 0,0,0,3,5,0,3,0, 0, 3,0,0,3,0,5,3,/* 96 - 111 */ + 0,0,3,5,0,9,0,7, 3,11,0,3,0,5,3,0,/* 112 - 127 */ + }; + + inline int get_powi_factor(long abs_int_exponent) + { + if(abs_int_exponent >= int(sizeof(powi_factor_table))) return 0; + return powi_factor_table[abs_int_exponent]; + } + +#if 0 + int EstimatePowiComplexity(int abs_int_exponent) + { + int cost = 0; + while(abs_int_exponent > 1) + { + int factor = get_powi_factor(abs_int_exponent); + if(factor) + { + cost += EstimatePowiComplexity(factor); + abs_int_exponent /= factor; + continue; + } + if(!(abs_int_exponent & 1)) + { + abs_int_exponent /= 2; + cost += 3; // sqr + } + else + { + cost += 4; // dup+mul + abs_int_exponent -= 1; + } + } + return cost; + } +#endif + + bool IsEligibleIntPowiExponent(long int_exponent) + { + if(int_exponent == 0) return false; + long abs_int_exponent = int_exponent; + #if 0 + int cost = 0; + + if(abs_int_exponent < 0) + { + cost += 11; + abs_int_exponent = -abs_int_exponent; + } + + cost += EstimatePowiComplexity(abs_int_exponent); + + return cost < (10*3 + 4*4); + #else + if(abs_int_exponent < 0) abs_int_exponent = -abs_int_exponent; + + return (abs_int_exponent >= 1) + && (abs_int_exponent <= 46 || + (abs_int_exponent <= 1024 && + (abs_int_exponent & (abs_int_exponent - 1)) == 0)); + #endif + } + + /* Needed by fp_opcode_add.inc if tracing is enabled */ + template<typename Value_t> + std::string findName(const NamePtrsMap<Value_t>& nameMap, + unsigned index, + typename NameData<Value_t>::DataType type) + { + for(typename NamePtrsMap<Value_t>::const_iterator + iter = nameMap.begin(); + iter != nameMap.end(); + ++iter) + { + if(iter->second.type == type && iter->second.index == index) + return std::string(iter->first.name, + iter->first.name + iter->first.nameLength); + } + return "?"; + } +} + +template<typename Value_t> +inline void FunctionParserBase<Value_t>::AddImmedOpcode(Value_t value) +{ + mData->mImmed.push_back(value); + mData->mByteCode.push_back(cImmed); +} + +template<typename Value_t> +inline void FunctionParserBase<Value_t>::CompilePowi(long abs_int_exponent) +{ + int num_muls=0; + while(abs_int_exponent > 1) + { + long factor = get_powi_factor(abs_int_exponent); + if(factor) + { + CompilePowi(factor); + abs_int_exponent /= factor; + continue; + } + if(!(abs_int_exponent & 1)) + { + abs_int_exponent /= 2; + mData->mByteCode.push_back(cSqr); + // ^ Don't put AddFunctionOpcode here, + // it would slow down a great deal. + } + else + { + mData->mByteCode.push_back(cDup); + incStackPtr(); + abs_int_exponent -= 1; + ++num_muls; + } + } + if(num_muls > 0) + { + mData->mByteCode.resize(mData->mByteCode.size()+num_muls, cMul); + mStackPtr -= num_muls; + } +} + +template<typename Value_t> +inline bool FunctionParserBase<Value_t>::TryCompilePowi(Value_t original_immed) +{ + Value_t changed_immed = original_immed; + for(int sqrt_count=0; /**/; ++sqrt_count) + { + long int_exponent = makeLongInteger(changed_immed); + if(isLongInteger(changed_immed) && + IsEligibleIntPowiExponent(int_exponent)) + { + long abs_int_exponent = int_exponent; + if(abs_int_exponent < 0) + abs_int_exponent = -abs_int_exponent; + + mData->mImmed.pop_back(); mData->mByteCode.pop_back(); + --mStackPtr; + // ^Though the above is accounted for by the procedure + // that generates cPow, we need it for correct cFetch + // indexes in CompilePowi(). + + while(sqrt_count > 0) + { + int opcode = cSqrt; + if(sqrt_count == 1 && int_exponent < 0) + { + opcode = cRSqrt; + int_exponent = -int_exponent; + } + mData->mByteCode.push_back(opcode); + --sqrt_count; + } + if((abs_int_exponent & 1) == 0) + { + // This special rule fixes the optimization + // shortcoming of (-x)^2 with minimal overhead. + AddFunctionOpcode(cSqr); + abs_int_exponent >>= 1; + } + CompilePowi(abs_int_exponent); + if(int_exponent < 0) mData->mByteCode.push_back(cInv); + ++mStackPtr; // Needed because cPow adding will assume this. + return true; + } + if(sqrt_count >= 4) break; + changed_immed += changed_immed; + } + + // When we don't know whether x >= 0, we still know that + // x^y can be safely converted into exp(y * log(x)) + // when y is _not_ integer, because we know that x >= 0. + // Otherwise either expression will give a NaN. + if(/*!isInteger(original_immed) ||*/ + IsNeverNegativeValueOpcode(mData->mByteCode[mData->mByteCode.size()-2])) + { + mData->mImmed.pop_back(); + mData->mByteCode.pop_back(); + //--mStackPtr; - accounted for by the procedure that generates cPow + AddFunctionOpcode(cLog); + AddImmedOpcode(original_immed); + //incStackPtr(); - this and the next are redundant because... + AddFunctionOpcode(cMul); + //--mStackPtr; - ...because the cImmed was popped earlier. + AddFunctionOpcode(cExp); + return true; + } + return false; +} + +//#include "fpoptimizer/opcodename.hh" +// ^ needed only if FP_TRACE_BYTECODE_OPTIMIZATION() is used + +template<typename Value_t> +inline void FunctionParserBase<Value_t>::AddFunctionOpcode(unsigned opcode) +{ +#define FP_FLOAT_VERSION 1 +#define FP_COMPLEX_VERSION 0 +#include "extrasrc/fp_opcode_add.inc" +#undef FP_COMPLEX_VERSION +#undef FP_FLOAT_VERSION +} + +#ifdef FP_SUPPORT_LONG_INT_TYPE +template<> +inline void FunctionParserBase<long>::AddFunctionOpcode(unsigned opcode) +{ + typedef long Value_t; +#define FP_FLOAT_VERSION 0 +#define FP_COMPLEX_VERSION 0 +#include "extrasrc/fp_opcode_add.inc" +#undef FP_COMPLEX_VERSION +#undef FP_FLOAT_VERSION +} +#endif + +#ifdef FP_SUPPORT_GMP_INT_TYPE +template<> +inline void FunctionParserBase<GmpInt>::AddFunctionOpcode(unsigned opcode) +{ + typedef GmpInt Value_t; +#define FP_FLOAT_VERSION 0 +#define FP_COMPLEX_VERSION 0 +#include "extrasrc/fp_opcode_add.inc" +#undef FP_COMPLEX_VERSION +#undef FP_FLOAT_VERSION +} +#endif + +#ifdef FP_SUPPORT_COMPLEX_DOUBLE_TYPE +template<> +inline void FunctionParserBase<std::complex<double> >::AddFunctionOpcode(unsigned opcode) +{ + typedef std::complex<double> Value_t; +#define FP_FLOAT_VERSION 1 +#define FP_COMPLEX_VERSION 1 +#include "extrasrc/fp_opcode_add.inc" +#undef FP_COMPLEX_VERSION +#undef FP_FLOAT_VERSION +} +#endif + +#ifdef FP_SUPPORT_COMPLEX_FLOAT_TYPE +template<> +inline void FunctionParserBase<std::complex<float> >::AddFunctionOpcode(unsigned opcode) +{ + typedef std::complex<float> Value_t; +#define FP_FLOAT_VERSION 1 +#define FP_COMPLEX_VERSION 1 +#include "extrasrc/fp_opcode_add.inc" +#undef FP_COMPLEX_VERSION +#undef FP_FLOAT_VERSION +} +#endif + +#ifdef FP_SUPPORT_COMPLEX_LONG_DOUBLE_TYPE +template<> +inline void FunctionParserBase<std::complex<long double> >::AddFunctionOpcode(unsigned opcode) +{ + typedef std::complex<long double> Value_t; +#define FP_FLOAT_VERSION 1 +#define FP_COMPLEX_VERSION 1 +#include "extrasrc/fp_opcode_add.inc" +#undef FP_COMPLEX_VERSION +#undef FP_FLOAT_VERSION +} +#endif + +template<typename Value_t> +unsigned +FunctionParserBase<Value_t>::ParseIdentifier(const char* function) +{ + return readIdentifier<Value_t>(function); +} + +template<typename Value_t> +std::pair<const char*, Value_t> +FunctionParserBase<Value_t>::ParseLiteral(const char* function) +{ + char* endptr; +#if 0 /* Profile the hex literal parser */ + if(function[0]=='0' && function[1]=='x') + { + // Parse hexadecimal literal if fp_parseLiteral didn't already + Value_t val = parseHexLiteral<Value_t>(function+2, &endptr); + if(endptr == function+2) + return std::pair<const char*,Value_t> (function, Value_t()); + return std::pair<const char*, Value_t> (endptr, val); + } +#endif + Value_t val = fp_parseLiteral<Value_t>(function, &endptr); + + if(endptr == function+1 && function[0] == '0' && function[1] == 'x') + { + // Parse hexadecimal literal if fp_parseLiteral didn't already + val = parseHexLiteral<Value_t>(function+2, &endptr); + if(endptr == function+2) + return std::pair<const char*,Value_t> (function, Value_t()); + } + else if(endptr == function) + return std::pair<const char*,Value_t> (function, Value_t()); + + return std::pair<const char*,Value_t> (endptr, val); +} + +#ifdef FP_SUPPORT_MPFR_FLOAT_TYPE +template<> +std::pair<const char*, MpfrFloat> +FunctionParserBase<MpfrFloat>::ParseLiteral(const char* function) +{ + char* endPtr; + const MpfrFloat val = MpfrFloat::parseString(function, &endPtr); + if(endPtr == function) + return std::pair<const char*,MpfrFloat> (function, MpfrFloat()); + return std::pair<const char*,MpfrFloat> (endPtr, val); +} +#endif + +#ifdef FP_SUPPORT_GMP_INT_TYPE +template<> +std::pair<const char*, GmpInt> +FunctionParserBase<GmpInt>::ParseLiteral(const char* function) +{ + char* endPtr; + const GmpInt val = GmpInt::parseString(function, &endPtr); + if(endPtr == function) + return std::pair<const char*,GmpInt> (function, GmpInt()); + return std::pair<const char*,GmpInt> (endPtr, val); +} +#endif + + +template<typename Value_t> +inline const char* +FunctionParserBase<Value_t>::CompileLiteral(const char* function) +{ + std::pair<const char*, Value_t> result = ParseLiteral(function); + + if(result.first == function) + return SetErrorType(SYNTAX_ERROR, result.first); + + AddImmedOpcode(result.second); + incStackPtr(); + SkipSpace(result.first); + return result.first; +} + +template<typename Value_t> +const char* FunctionParserBase<Value_t>::CompileIf(const char* function) +{ + if(*function != '(') return SetErrorType(EXPECT_PARENTH_FUNC, function); + + function = CompileExpression(function+1); + if(!function) return 0; + if(*function != ',') + return SetErrorType(noCommaError<Value_t>(*function), function); + + OPCODE opcode = cIf; + if(mData->mByteCode.back() == cNotNot) mData->mByteCode.pop_back(); + if(IsNeverNegativeValueOpcode(mData->mByteCode.back())) + { + // If we know that the condition to be tested is always + // a positive value (such as when produced by "x<y"), + // we can use the faster opcode to evaluate it. + // cIf tests whether fabs(cond) >= 0.5, + // cAbsIf simply tests whether cond >= 0.5. + opcode = cAbsIf; + } + + mData->mByteCode.push_back(opcode); + const unsigned curByteCodeSize = unsigned(mData->mByteCode.size()); + PushOpcodeParam<false>(0); // Jump index; to be set later + PushOpcodeParam<true> (0); // Immed jump index; to be set later + + --mStackPtr; + + function = CompileExpression(function + 1); + if(!function) return 0; + if(*function != ',') + return SetErrorType(noCommaError<Value_t>(*function), function); + + mData->mByteCode.push_back(cJump); + const unsigned curByteCodeSize2 = unsigned(mData->mByteCode.size()); + const unsigned curImmedSize2 = unsigned(mData->mImmed.size()); + PushOpcodeParam<false>(0); // Jump index; to be set later + PushOpcodeParam<true> (0); // Immed jump index; to be set later + + --mStackPtr; + + function = CompileExpression(function + 1); + if(!function) return 0; + if(*function != ')') + return SetErrorType(noParenthError<Value_t>(*function), function); + + PutOpcodeParamAt<true> ( mData->mByteCode.back(), unsigned(mData->mByteCode.size()-1) ); + // ^Necessary for guarding against if(x,1,2)+1 being changed + // into if(x,1,3) by fp_opcode_add.inc + + // Set jump indices + PutOpcodeParamAt<false>( curByteCodeSize2+1, curByteCodeSize ); + PutOpcodeParamAt<false>( curImmedSize2, curByteCodeSize+1 ); + PutOpcodeParamAt<false>( unsigned(mData->mByteCode.size())-1, curByteCodeSize2); + PutOpcodeParamAt<false>( unsigned(mData->mImmed.size()), curByteCodeSize2+1); + + ++function; + SkipSpace(function); + return function; +} + +template<typename Value_t> +const char* FunctionParserBase<Value_t>::CompileFunctionParams +(const char* function, unsigned requiredParams) +{ + if(*function != '(') return SetErrorType(EXPECT_PARENTH_FUNC, function); + + if(requiredParams > 0) + { + const char* function_end = CompileExpression(function+1); + if(!function_end) + { + // If an error occurred, verify whether it was caused by () + ++function; + SkipSpace(function); + if(*function == ')') + return SetErrorType(ILL_PARAMS_AMOUNT, function); + // Not caused by (), use the error message given by CompileExpression() + return 0; + } + function = function_end; + + for(unsigned i = 1; i < requiredParams; ++i) + { + if(*function != ',') + return SetErrorType(noCommaError<Value_t>(*function), function); + + function = CompileExpression(function+1); + if(!function) return 0; + } + // No need for incStackPtr() because each parse parameter calls it + mStackPtr -= requiredParams-1; + } + else + { + incStackPtr(); // return value of function is pushed onto the stack + ++function; + SkipSpace(function); + } + + if(*function != ')') + return SetErrorType(noParenthError<Value_t>(*function), function); + ++function; + SkipSpace(function); + return function; +} + +template<typename Value_t> +const char* FunctionParserBase<Value_t>::CompileElement(const char* function) +{ + if(BeginsLiteral<Value_t>( (unsigned char) *function)) + return CompileLiteral(function); + + unsigned nameLength = readIdentifier<Value_t>(function); + if(nameLength == 0) + { + // No identifier found + if(*function == '(') return CompileParenthesis(function); + if(*function == ')') return SetErrorType(MISM_PARENTH, function); + return SetErrorType(SYNTAX_ERROR, function); + } + + // Function, variable or constant + if(nameLength & 0x80000000U) // Function + { + OPCODE func_opcode = OPCODE( (nameLength >> 16) & 0x7FFF ); + return CompileFunction(function + (nameLength & 0xFFFF), func_opcode); + } + + NamePtr name(function, nameLength); + const char* endPtr = function + nameLength; + SkipSpace(endPtr); + + typename NamePtrsMap<Value_t>::iterator nameIter = + mData->mNamePtrs.find(name); + if(nameIter == mData->mNamePtrs.end()) + { + // Check if it's an inline variable: + for(typename Data::InlineVarNamesContainer::reverse_iterator iter = + mData->mInlineVarNames.rbegin(); + iter != mData->mInlineVarNames.rend(); + ++iter) + { + if(name == iter->mName) + { + if( iter->mFetchIndex+1 == mStackPtr) + { + mData->mByteCode.push_back(cDup); + } + else + { + mData->mByteCode.push_back(cFetch); + PushOpcodeParam<true>(iter->mFetchIndex); + } + incStackPtr(); + return endPtr; + } + } + + return SetErrorType(UNKNOWN_IDENTIFIER, function); + } + + const NameData<Value_t>* nameData = &nameIter->second; + switch(nameData->type) + { + case NameData<Value_t>::VARIABLE: // is variable + if(unlikely(!mData->mByteCode.empty() && + mData->mByteCode.back() == nameData->index)) + mData->mByteCode.push_back(cDup); + else + mData->mByteCode.push_back(nameData->index); + incStackPtr(); + return endPtr; + + case NameData<Value_t>::CONSTANT: // is constant + AddImmedOpcode(nameData->value); + incStackPtr(); + return endPtr; + + case NameData<Value_t>::UNIT: // is unit (error if appears here) + break; + + case NameData<Value_t>::FUNC_PTR: // is C++ function + function = CompileFunctionParams + (endPtr, mData->mFuncPtrs[nameData->index].mParams); + //if(!function) return 0; + mData->mByteCode.push_back(cFCall); + PushOpcodeParam<true>(nameData->index); + return function; + + case NameData<Value_t>::PARSER_PTR: // is FunctionParser + function = CompileFunctionParams + (endPtr, mData->mFuncParsers[nameData->index].mParams); + //if(!function) return 0; + mData->mByteCode.push_back(cPCall); + PushOpcodeParam<true>(nameData->index); + return function; + } + + // When it's an unit (or unrecognized type): + return SetErrorType(SYNTAX_ERROR, function); +} + +template<typename Value_t> +inline const char* FunctionParserBase<Value_t>::CompileFunction +(const char* function, unsigned func_opcode) +{ + SkipSpace(function); + const FuncDefinition& funcDef = Functions[func_opcode]; + + if(func_opcode == cIf) // "if" is a special case + return CompileIf(function); + + unsigned requiredParams = funcDef.params; + + function = CompileFunctionParams(function, requiredParams); + if(!function) return 0; + + if(mData->mUseDegreeConversion) + { + if(funcDef.flags & FuncDefinition::AngleIn) + AddFunctionOpcode(cRad); + + AddFunctionOpcode(func_opcode); + + if(funcDef.flags & FuncDefinition::AngleOut) + AddFunctionOpcode(cDeg); + } + else + { + AddFunctionOpcode(func_opcode); + } + return function; +} + +template<typename Value_t> +inline const char* +FunctionParserBase<Value_t>::CompileParenthesis(const char* function) +{ + ++function; // Skip '(' + + SkipSpace(function); + if(*function == ')') return SetErrorType(EMPTY_PARENTH, function); + function = CompileExpression(function); + if(!function) return 0; + + if(*function != ')') return SetErrorType(MISSING_PARENTH, function); + ++function; // Skip ')' + + SkipSpace(function); + return function; +} + +template<typename Value_t> +const char* +FunctionParserBase<Value_t>::CompilePossibleUnit(const char* function) +{ + unsigned nameLength = readIdentifier<Value_t>(function); + if(nameLength & 0x80000000U) return function; // built-in function name + if(nameLength != 0) + { + NamePtr name(function, nameLength); + + typename NamePtrsMap<Value_t>::iterator nameIter = + mData->mNamePtrs.find(name); + if(nameIter != mData->mNamePtrs.end()) + { + const NameData<Value_t>* nameData = &nameIter->second; + if(nameData->type == NameData<Value_t>::UNIT) + { + AddImmedOpcode(nameData->value); + incStackPtr(); + AddFunctionOpcode(cMul); + --mStackPtr; + + const char* endPtr = function + nameLength; + SkipSpace(endPtr); + return endPtr; + } + } + } + + return function; +} + +template<typename Value_t> +inline const char* +FunctionParserBase<Value_t>::CompilePow(const char* function) +{ + function = CompileElement(function); + if(!function) return 0; + function = CompilePossibleUnit(function); + + if(*function == '^') + { + ++function; + SkipSpace(function); + + unsigned op = cPow; + if(mData->mByteCode.back() == cImmed) + { + if(mData->mImmed.back() == fp_const_e<Value_t>()) + { op = cExp; mData->mByteCode.pop_back(); + mData->mImmed.pop_back(); --mStackPtr; } + else if(mData->mImmed.back() == Value_t(2)) + { op = cExp2; mData->mByteCode.pop_back(); + mData->mImmed.pop_back(); --mStackPtr; } + } + + function = CompileUnaryMinus(function); + if(!function) return 0; + + // add opcode + AddFunctionOpcode(op); + + if(op == cPow) --mStackPtr; + } + return function; +} + +/* Currently the power operator is skipped for integral types because its + usefulness with them is questionable, and in the case of GmpInt, for safety + reasons: + - With long int almost any power, except for very small ones, would + overflow the result, so the usefulness of this is rather questionable. + - With GmpInt the power operator could be easily abused to make the program + run out of memory (think of a function like "10^10^10^10^1000000"). +*/ +#ifdef FP_SUPPORT_LONG_INT_TYPE +template<> +inline const char* +FunctionParserBase<long>::CompilePow(const char* function) +{ + function = CompileElement(function); + if(!function) return 0; + return CompilePossibleUnit(function); +} +#endif + +#ifdef FP_SUPPORT_GMP_INT_TYPE +template<> +inline const char* +FunctionParserBase<GmpInt>::CompilePow(const char* function) +{ + function = CompileElement(function); + if(!function) return 0; + return CompilePossibleUnit(function); +} +#endif + +template<typename Value_t> +inline const char* +FunctionParserBase<Value_t>::CompileUnaryMinus(const char* function) +{ + char op = *function; + switch(op) + { + case '-': + case '!': + ++function; + SkipSpace(function); + + function = CompileUnaryMinus(function); + if(!function) return 0; + + AddFunctionOpcode(op=='-' ? cNeg : cNot); + + return function; + default: break; + } + return CompilePow(function); +} + +template<typename Value_t> +inline const char* +FunctionParserBase<Value_t>::CompileMult(const char* function) +{ + function = CompileUnaryMinus(function); + if(!function) return 0; + + Value_t pending_immed(1); + #define FP_FlushImmed(do_reset) \ + if(pending_immed != Value_t(1)) \ + { \ + unsigned op = cMul; \ + if(!IsIntType<Value_t>::result && mData->mByteCode.back() == cInv) \ + { \ + /* (...) cInv 5 cMul -> (...) 5 cRDiv */ \ + /* ^ ^ | */ \ + mData->mByteCode.pop_back(); \ + op = cRDiv; \ + } \ + AddImmedOpcode(pending_immed); \ + incStackPtr(); \ + AddFunctionOpcode(op); \ + --mStackPtr; \ + if(do_reset) pending_immed = Value_t(1); \ + } + while(true) + { + char c = *function; + if(c == '%') + { + FP_FlushImmed(true); + ++function; + SkipSpace(function); + function = CompileUnaryMinus(function); + if(!function) return 0; + AddFunctionOpcode(cMod); + --mStackPtr; + continue; + } + if(c != '*' && c != '/') break; + + bool safe_cumulation = (c == '*' || !IsIntType<Value_t>::result); + if(!safe_cumulation) + { + FP_FlushImmed(true); + } + + ++function; + SkipSpace(function); + if(mData->mByteCode.back() == cImmed + && (safe_cumulation + || mData->mImmed.back() == Value_t(1))) + { + // 5 (...) cMul --> (...) ||| 5 cMul + // 5 (...) cDiv --> (...) cInv ||| 5 cMul + // ^ | ^ + pending_immed *= mData->mImmed.back(); + mData->mImmed.pop_back(); + mData->mByteCode.pop_back(); + --mStackPtr; + function = CompileUnaryMinus(function); + if(!function) return 0; + if(c == '/') + AddFunctionOpcode(cInv); + continue; + } + if(safe_cumulation + && mData->mByteCode.back() == cMul + && mData->mByteCode[mData->mByteCode.size()-2] == cImmed) + { + // (:::) 5 cMul (...) cMul -> (:::) (...) cMul ||| 5 cMul + // (:::) 5 cMul (...) cDiv -> (:::) (...) cDiv ||| 5 cMul + // ^ ^ + pending_immed *= mData->mImmed.back(); + mData->mImmed.pop_back(); + mData->mByteCode.pop_back(); + mData->mByteCode.pop_back(); + } + // cDiv is not tested here because the bytecode + // optimizer will convert this kind of cDivs into cMuls. + bool lhs_inverted = false; + if(!IsIntType<Value_t>::result && c == '*' + && mData->mByteCode.back() == cInv) + { + // (:::) cInv (...) cMul -> (:::) (...) cRDiv + // (:::) cInv (...) cDiv -> (:::) (...) cMul cInv + // ^ ^ | + mData->mByteCode.pop_back(); + lhs_inverted = true; + } + function = CompileUnaryMinus(function); + if(!function) return 0; + if(safe_cumulation + && mData->mByteCode.back() == cMul + && mData->mByteCode[mData->mByteCode.size()-2] == cImmed) + { + // (:::) (...) 5 cMul cMul -> (:::) (...) cMul ||| 5 Mul + // (:::) (...) 5 cMul cDiv -> (:::) (...) cDiv ||| /5 Mul + // ^ ^ + if(c == '*') + pending_immed *= mData->mImmed.back(); + else + pending_immed /= mData->mImmed.back(); + mData->mImmed.pop_back(); + mData->mByteCode.pop_back(); + mData->mByteCode.pop_back(); + } + else + if(safe_cumulation + && mData->mByteCode.back() == cRDiv + && mData->mByteCode[mData->mByteCode.size()-2] == cImmed) + { + // (:::) (...) 5 cRDiv cMul -> (:::) (...) cDiv ||| 5 cMul + // (:::) (...) 5 cRDiv cDiv -> (:::) (...) cMul ||| /5 cMul + // ^ ^ + if(c == '*') + { c = '/'; pending_immed *= mData->mImmed.back(); } + else + { c = '*'; pending_immed /= mData->mImmed.back(); } + mData->mImmed.pop_back(); + mData->mByteCode.pop_back(); + mData->mByteCode.pop_back(); + } + if(!lhs_inverted) // if (/x/y) was changed to /(x*y), add missing cInv + { + AddFunctionOpcode(c == '*' ? cMul : cDiv); + --mStackPtr; + } + else if(c == '*') // (/x)*y -> rdiv(x,y) + { + AddFunctionOpcode(cRDiv); + --mStackPtr; + } + else // (/x)/y -> /(x*y) + { + AddFunctionOpcode(cMul); + --mStackPtr; + AddFunctionOpcode(cInv); + } + } + FP_FlushImmed(false); + #undef FP_FlushImmed + return function; +} + +template<typename Value_t> +inline const char* +FunctionParserBase<Value_t>::CompileAddition(const char* function) +{ + function = CompileMult(function); + if(!function) return 0; + + Value_t pending_immed(0); + #define FP_FlushImmed(do_reset) \ + if(pending_immed != Value_t(0)) \ + { \ + unsigned op = cAdd; \ + if(mData->mByteCode.back() == cNeg) \ + { \ + /* (...) cNeg 5 cAdd -> (...) 5 cRSub */ \ + /* ^ ^ | */ \ + mData->mByteCode.pop_back(); \ + op = cRSub; \ + } \ + AddImmedOpcode(pending_immed); \ + incStackPtr(); \ + AddFunctionOpcode(op); \ + --mStackPtr; \ + if(do_reset) pending_immed = Value_t(0); \ + } + while(true) + { + char c = *function; + if(c != '+' && c != '-') break; + ++function; + SkipSpace(function); + if(mData->mByteCode.back() == cImmed) + { + // 5 (...) cAdd --> (...) ||| 5 cAdd + // 5 (...) cSub --> (...) cNeg ||| 5 cAdd + // ^ | ^ + pending_immed += mData->mImmed.back(); + mData->mImmed.pop_back(); + mData->mByteCode.pop_back(); + --mStackPtr; + function = CompileMult(function); + if(!function) return 0; + if(c == '-') + AddFunctionOpcode(cNeg); + continue; + } + if(mData->mByteCode.back() == cAdd + && mData->mByteCode[mData->mByteCode.size()-2] == cImmed) + { + // (:::) 5 cAdd (...) cAdd -> (:::) (...) cAdd ||| 5 cAdd + // (:::) 5 cAdd (...) cSub -> (:::) (...) cSub ||| 5 cAdd + // ^ ^ + pending_immed += mData->mImmed.back(); + mData->mImmed.pop_back(); + mData->mByteCode.pop_back(); + mData->mByteCode.pop_back(); + } + // cSub is not tested here because the bytecode + // optimizer will convert this kind of cSubs into cAdds. + bool lhs_negated = false; + if(mData->mByteCode.back() == cNeg) + { + // (:::) cNeg (...) cAdd -> (:::) (...) cRSub + // (:::) cNeg (...) cSub -> (:::) (...) cAdd cNeg + // ^ ^ | + mData->mByteCode.pop_back(); + lhs_negated = true; + } + function = CompileMult(function); + if(!function) return 0; + if(mData->mByteCode.back() == cAdd + && mData->mByteCode[mData->mByteCode.size()-2] == cImmed) + { + // (:::) (...) 5 cAdd cAdd -> (:::) (...) cAdd ||| 5 Add + // (:::) (...) 5 cAdd cSub -> (:::) (...) cSub ||| -5 Add + // ^ ^ + if(c == '+') + pending_immed += mData->mImmed.back(); + else + pending_immed -= mData->mImmed.back(); + mData->mImmed.pop_back(); + mData->mByteCode.pop_back(); + mData->mByteCode.pop_back(); + } + else + if(mData->mByteCode.back() == cRSub + && mData->mByteCode[mData->mByteCode.size()-2] == cImmed) + { + // (:::) (...) 5 cRSub cAdd -> (:::) (...) cSub ||| 5 cAdd + // (:::) (...) 5 cRSub cSub -> (:::) (...) cAdd ||| -5 cAdd + // ^ ^ + if(c == '+') + { c = '-'; pending_immed += mData->mImmed.back(); } + else + { c = '+'; pending_immed -= mData->mImmed.back(); } + mData->mImmed.pop_back(); + mData->mByteCode.pop_back(); + mData->mByteCode.pop_back(); + } + if(!lhs_negated) // if (-x-y) was changed to -(x+y), add missing cNeg + { + AddFunctionOpcode(c == '+' ? cAdd : cSub); + --mStackPtr; + } + else if(c == '+') // (-x)+y -> rsub(x,y) + { + AddFunctionOpcode(cRSub); + --mStackPtr; + } + else // (-x)-y -> -(x+y) + { + AddFunctionOpcode(cAdd); + --mStackPtr; + AddFunctionOpcode(cNeg); + } + } + FP_FlushImmed(false); + #undef FP_FlushImmed + return function; +} + +template<typename Value_t> +inline const char* +FunctionParserBase<Value_t>::CompileComparison(const char* function) +{ + unsigned op=0; + while(true) + { + function = CompileAddition(function); + if(!function) return 0; + + if(op) + { + AddFunctionOpcode(op); + --mStackPtr; + } + switch(*function) + { + case '=': + ++function; op = cEqual; break; + case '!': + if(function[1] == '=') + { function += 2; op = cNEqual; break; } + // If '=' does not follow '!', a syntax error will + // be generated at the outermost parsing level + return function; + case '<': + if(function[1] == '=') + { function += 2; op = cLessOrEq; break; } + ++function; op = cLess; break; + case '>': + if(function[1] == '=') + { function += 2; op = cGreaterOrEq; break; } + ++function; op = cGreater; break; + default: return function; + } + SkipSpace(function); + } + return function; +} + +template<typename Value_t> +inline const char* FunctionParserBase<Value_t>::CompileAnd(const char* function) +{ + std::size_t param0end=0; + while(true) + { + function = CompileComparison(function); + if(!function) return 0; + + if(param0end) + { + if(mData->mByteCode.back() == cNotNot) mData->mByteCode.pop_back(); + + AddFunctionOpcode(cAnd); + --mStackPtr; + } + if(*function != '&') break; + ++function; + SkipSpace(function); + param0end = mData->mByteCode.size(); + } + return function; +} + +template<typename Value_t> +const char* FunctionParserBase<Value_t>::CompileExpression(const char* function) +{ + std::size_t param0end=0; + while(true) + { + SkipSpace(function); + function = CompileAnd(function); + if(!function) return 0; + + if(param0end) + { + if(mData->mByteCode.back() == cNotNot) mData->mByteCode.pop_back(); + + AddFunctionOpcode(cOr); + --mStackPtr; + } + if(*function != '|') break; + ++function; + param0end = mData->mByteCode.size(); + } + return function; +} + +template<typename Value_t> +const char* FunctionParserBase<Value_t>::Compile(const char* function) +{ + while(true) + { + // Check if an identifier appears as first token: + SkipSpace(function); + unsigned nameLength = readIdentifier<Value_t>(function); + if(nameLength > 0 && !(nameLength & 0x80000000U)) + { + typename Data::InlineVariable inlineVar = + { NamePtr(function, nameLength), 0 }; + + // Check if it's an unknown identifier: + typename NamePtrsMap<Value_t>::iterator nameIter = + mData->mNamePtrs.find(inlineVar.mName); + if(nameIter == mData->mNamePtrs.end()) + { + const char* function2 = function + nameLength; + SkipSpace(function2); + + // Check if ":=" follows the unknown identifier: + if(function2[0] == ':' && function2[1] == '=') + { + // Parse the expression that follows and create the + // inline variable: + function2 = CompileExpression(function2 + 2); + if(!function2) return 0; + if(*function2 != ';') return function2; + + inlineVar.mFetchIndex = mStackPtr - 1; + mData->mInlineVarNames.push_back(inlineVar); + + // Continue with the expression after the ';': + function = function2 + 1; + continue; + } + } + } + break; + } + + return CompileExpression(function); +} + +template<typename Value_t> template<bool PutFlag> +inline void FunctionParserBase<Value_t>::PushOpcodeParam + (unsigned value) +{ + mData->mByteCode.push_back(value | (PutFlag ? FP_ParamGuardMask : 0u)); + if(PutFlag) mData->mHasByteCodeFlags = true; +} + +template<typename Value_t> template<bool PutFlag> +inline void FunctionParserBase<Value_t>::PutOpcodeParamAt + (unsigned value, unsigned offset) +{ + mData->mByteCode[offset] = value | (PutFlag ? FP_ParamGuardMask : 0u); + if(PutFlag) mData->mHasByteCodeFlags = true; +} + +//=========================================================================== +// Function evaluation +//=========================================================================== +template<typename Value_t> +Value_t FunctionParserBase<Value_t>::Eval(const Value_t* Vars) +{ + if(mData->mParseErrorType != FP_NO_ERROR) return Value_t(0); + + const unsigned* const byteCode = &(mData->mByteCode[0]); + const Value_t* const immed = mData->mImmed.empty() ? 0 : &(mData->mImmed[0]); + const unsigned byteCodeSize = unsigned(mData->mByteCode.size()); + unsigned IP, DP=0; + int SP=-1; + +#ifdef FP_USE_THREAD_SAFE_EVAL + /* If Eval() may be called by multiple threads simultaneously, + * then Eval() must allocate its own stack. + */ +#ifdef FP_USE_THREAD_SAFE_EVAL_WITH_ALLOCA + /* alloca() allocates room from the hardware stack. + * It is automatically freed when the function returns. + */ + Value_t* const Stack = (Value_t*)alloca(mData->mStackSize*sizeof(Value_t)); +#else + /* Allocate from the heap. Ensure that it is freed + * automatically no matter which exit path is taken. + */ + struct AutoDealloc + { + Value_t* ptr; + ~AutoDealloc() { delete[] ptr; } + } AutoDeallocStack = { new Value_t[mData->mStackSize] }; + Value_t*& Stack = AutoDeallocStack.ptr; +#endif +#else + /* No thread safety, so use a global stack. */ + std::vector<Value_t>& Stack = mData->mStack; +#endif + + for(IP=0; IP<byteCodeSize; ++IP) + { + switch(byteCode[IP]) + { +// Functions: + case cAbs: Stack[SP] = fp_abs(Stack[SP]); break; + + case cAcos: + if(IsComplexType<Value_t>::result == false + && (Stack[SP] < Value_t(-1) || Stack[SP] > Value_t(1))) + { mData->mEvalErrorType=4; return Value_t(0); } + Stack[SP] = fp_acos(Stack[SP]); break; + + case cAcosh: + if(IsComplexType<Value_t>::result == false + && Stack[SP] < Value_t(1)) + { mData->mEvalErrorType=4; return Value_t(0); } + Stack[SP] = fp_acosh(Stack[SP]); break; + + case cAsin: + if(IsComplexType<Value_t>::result == false + && (Stack[SP] < Value_t(-1) || Stack[SP] > Value_t(1))) + { mData->mEvalErrorType=4; return Value_t(0); } + Stack[SP] = fp_asin(Stack[SP]); break; + + case cAsinh: Stack[SP] = fp_asinh(Stack[SP]); break; + + case cAtan: Stack[SP] = fp_atan(Stack[SP]); break; + + case cAtan2: Stack[SP-1] = fp_atan2(Stack[SP-1], Stack[SP]); + --SP; break; + + case cAtanh: + if(IsComplexType<Value_t>::result + ? (Stack[SP] == Value_t(-1) || Stack[SP] == Value_t(1)) + : (Stack[SP] <= Value_t(-1) || Stack[SP] >= Value_t(1))) + { mData->mEvalErrorType=4; return Value_t(0); } + Stack[SP] = fp_atanh(Stack[SP]); break; + + case cCbrt: Stack[SP] = fp_cbrt(Stack[SP]); break; + + case cCeil: Stack[SP] = fp_ceil(Stack[SP]); break; + + case cCos: Stack[SP] = fp_cos(Stack[SP]); break; + + case cCosh: Stack[SP] = fp_cosh(Stack[SP]); break; + + case cCot: + { + const Value_t t = fp_tan(Stack[SP]); + if(t == Value_t(0)) + { mData->mEvalErrorType=1; return Value_t(0); } + Stack[SP] = Value_t(1)/t; break; + } + + case cCsc: + { + const Value_t s = fp_sin(Stack[SP]); + if(s == Value_t(0)) + { mData->mEvalErrorType=1; return Value_t(0); } + Stack[SP] = Value_t(1)/s; break; + } + + + case cExp: Stack[SP] = fp_exp(Stack[SP]); break; + + case cExp2: Stack[SP] = fp_exp2(Stack[SP]); break; + + case cFloor: Stack[SP] = fp_floor(Stack[SP]); break; + + case cHypot: + Stack[SP-1] = fp_hypot(Stack[SP-1], Stack[SP]); + --SP; break; + + case cIf: + if(fp_truth(Stack[SP--])) + IP += 2; + else + { + const unsigned* buf = &byteCode[IP+1]; + IP = buf[0]; + DP = buf[1]; + } + break; + + case cInt: Stack[SP] = fp_int(Stack[SP]); break; + + case cLog: + if(IsComplexType<Value_t>::result + ? Stack[SP] == Value_t(0) + : !(Stack[SP] > Value_t(0))) + { mData->mEvalErrorType=3; return Value_t(0); } + Stack[SP] = fp_log(Stack[SP]); break; + + case cLog10: + if(IsComplexType<Value_t>::result + ? Stack[SP] == Value_t(0) + : !(Stack[SP] > Value_t(0))) + { mData->mEvalErrorType=3; return Value_t(0); } + Stack[SP] = fp_log10(Stack[SP]); + break; + + case cLog2: + if(IsComplexType<Value_t>::result + ? Stack[SP] == Value_t(0) + : !(Stack[SP] > Value_t(0))) + { mData->mEvalErrorType=3; return Value_t(0); } + Stack[SP] = fp_log2(Stack[SP]); + break; + + case cMax: Stack[SP-1] = fp_max(Stack[SP-1], Stack[SP]); + --SP; break; + + case cMin: Stack[SP-1] = fp_min(Stack[SP-1], Stack[SP]); + --SP; break; + + case cPow: + // x:Negative ^ y:NonInteger is failure, + // except when the reciprocal of y forms an integer + /*if(IsComplexType<Value_t>::result == false + && Stack[SP-1] < Value_t(0) && + !isInteger(Stack[SP]) && + !isInteger(1.0 / Stack[SP])) + { mEvalErrorType=3; return Value_t(0); }*/ + // x:0 ^ y:negative is failure + if(Stack[SP-1] == Value_t(0) && + Stack[SP] < Value_t(0)) + { mData->mEvalErrorType=3; return Value_t(0); } + Stack[SP-1] = fp_pow(Stack[SP-1], Stack[SP]); + --SP; break; + + case cTrunc: Stack[SP] = fp_trunc(Stack[SP]); break; + + case cSec: + { + const Value_t c = fp_cos(Stack[SP]); + if(c == Value_t(0)) + { mData->mEvalErrorType=1; return Value_t(0); } + Stack[SP] = Value_t(1)/c; break; + } + + case cSin: Stack[SP] = fp_sin(Stack[SP]); break; + + case cSinh: Stack[SP] = fp_sinh(Stack[SP]); break; + + case cSqrt: + if(IsComplexType<Value_t>::result == false && + Stack[SP] < Value_t(0)) + { mData->mEvalErrorType=2; return Value_t(0); } + Stack[SP] = fp_sqrt(Stack[SP]); break; + + case cTan: Stack[SP] = fp_tan(Stack[SP]); break; + + case cTanh: Stack[SP] = fp_tanh(Stack[SP]); break; + + +// Misc: + case cImmed: Stack[++SP] = immed[DP++]; break; + + case cJump: + { + const unsigned* buf = &byteCode[IP+1]; + IP = buf[0]; + DP = buf[1]; + break; + } + +// Operators: + case cNeg: Stack[SP] = -Stack[SP]; break; + case cAdd: Stack[SP-1] += Stack[SP]; --SP; break; + case cSub: Stack[SP-1] -= Stack[SP]; --SP; break; + case cMul: Stack[SP-1] *= Stack[SP]; --SP; break; + + case cDiv: + if(Stack[SP] == Value_t(0)) + { mData->mEvalErrorType=1; return Value_t(0); } + Stack[SP-1] /= Stack[SP]; --SP; break; + + case cMod: + if(Stack[SP] == Value_t(0)) + { mData->mEvalErrorType=1; return Value_t(0); } + Stack[SP-1] = fp_mod(Stack[SP-1], Stack[SP]); + --SP; break; + + case cEqual: + Stack[SP-1] = fp_equal(Stack[SP-1], Stack[SP]); + --SP; break; + + case cNEqual: + Stack[SP-1] = fp_nequal(Stack[SP-1], Stack[SP]); + --SP; break; + + case cLess: + Stack[SP-1] = fp_less(Stack[SP-1], Stack[SP]); + --SP; break; + + case cLessOrEq: + Stack[SP-1] = fp_lessOrEq(Stack[SP-1], Stack[SP]); + --SP; break; + + case cGreater: + Stack[SP-1] = fp_less(Stack[SP], Stack[SP-1]); + --SP; break; + + case cGreaterOrEq: + Stack[SP-1] = fp_lessOrEq(Stack[SP], Stack[SP-1]); + --SP; break; + + case cNot: Stack[SP] = fp_not(Stack[SP]); break; + + case cNotNot: Stack[SP] = fp_notNot(Stack[SP]); break; + + case cAnd: + Stack[SP-1] = fp_and(Stack[SP-1], Stack[SP]); + --SP; break; + + case cOr: + Stack[SP-1] = fp_or(Stack[SP-1], Stack[SP]); + --SP; break; + +// Degrees-radians conversion: + case cDeg: Stack[SP] = RadiansToDegrees(Stack[SP]); break; + case cRad: Stack[SP] = DegreesToRadians(Stack[SP]); break; + +// User-defined function calls: + case cFCall: + { + const unsigned index = byteCode[++IP]; + const unsigned params = mData->mFuncPtrs[index].mParams; + const Value_t retVal = + mData->mFuncPtrs[index].mRawFuncPtr ? + mData->mFuncPtrs[index].mRawFuncPtr(&Stack[SP-params+1]) : + mData->mFuncPtrs[index].mFuncWrapperPtr->callFunction + (&Stack[SP-params+1]); + SP -= int(params)-1; + Stack[SP] = retVal; + break; + } + + case cPCall: + { + unsigned index = byteCode[++IP]; + unsigned params = mData->mFuncParsers[index].mParams; + Value_t retVal = + mData->mFuncParsers[index].mParserPtr->Eval + (&Stack[SP-params+1]); + SP -= int(params)-1; + Stack[SP] = retVal; + const int error = + mData->mFuncParsers[index].mParserPtr->EvalError(); + if(error) + { + mData->mEvalErrorType = error; + return 0; + } + break; + } + + + case cFetch: + { + unsigned stackOffs = byteCode[++IP]; + Stack[SP+1] = Stack[stackOffs]; ++SP; + break; + } + +#ifdef FP_SUPPORT_OPTIMIZER + case cPopNMov: + { + unsigned stackOffs_target = byteCode[++IP]; + unsigned stackOffs_source = byteCode[++IP]; + Stack[stackOffs_target] = Stack[stackOffs_source]; + SP = stackOffs_target; + break; + } + + case cLog2by: + if(IsComplexType<Value_t>::result + ? Stack[SP-1] == Value_t(0) + : !(Stack[SP-1] > Value_t(0))) + { mData->mEvalErrorType=3; return Value_t(0); } + Stack[SP-1] = fp_log2(Stack[SP-1]) * Stack[SP]; + --SP; + break; + + case cNop: break; +#endif // FP_SUPPORT_OPTIMIZER + + case cSinCos: + fp_sinCos(Stack[SP], Stack[SP+1], Stack[SP]); + ++SP; + break; + case cSinhCosh: + fp_sinhCosh(Stack[SP], Stack[SP+1], Stack[SP]); + ++SP; + break; + + case cAbsNot: + Stack[SP] = fp_absNot(Stack[SP]); break; + case cAbsNotNot: + Stack[SP] = fp_absNotNot(Stack[SP]); break; + case cAbsAnd: + Stack[SP-1] = fp_absAnd(Stack[SP-1], Stack[SP]); + --SP; break; + case cAbsOr: + Stack[SP-1] = fp_absOr(Stack[SP-1], Stack[SP]); + --SP; break; + case cAbsIf: + if(fp_absTruth(Stack[SP--])) + IP += 2; + else + { + const unsigned* buf = &byteCode[IP+1]; + IP = buf[0]; + DP = buf[1]; + } + break; + + case cDup: Stack[SP+1] = Stack[SP]; ++SP; break; + + case cInv: + if(Stack[SP] == Value_t(0)) + { mData->mEvalErrorType=1; return Value_t(0); } + Stack[SP] = Value_t(1)/Stack[SP]; + break; + + case cSqr: + Stack[SP] = Stack[SP]*Stack[SP]; + break; + + case cRDiv: + if(Stack[SP-1] == Value_t(0)) + { mData->mEvalErrorType=1; return Value_t(0); } + Stack[SP-1] = Stack[SP] / Stack[SP-1]; --SP; break; + + case cRSub: Stack[SP-1] = Stack[SP] - Stack[SP-1]; --SP; break; + + case cRSqrt: + if(Stack[SP] == Value_t(0)) + { mData->mEvalErrorType=1; return Value_t(0); } + Stack[SP] = Value_t(1) / fp_sqrt(Stack[SP]); break; + +#ifdef FP_SUPPORT_COMPLEX_NUMBERS + case cReal: Stack[SP] = fp_real(Stack[SP]); break; + case cImag: Stack[SP] = fp_imag(Stack[SP]); break; + case cArg: Stack[SP] = fp_arg(Stack[SP]); break; + case cConj: Stack[SP] = fp_conj(Stack[SP]); break; + case cPolar: + Stack[SP-1] = fp_polar(Stack[SP-1], Stack[SP]); + --SP; break; +#endif + + +// Variables: + default: + Stack[++SP] = Vars[byteCode[IP]-VarBegin]; + } + } + + mData->mEvalErrorType=0; + return Stack[SP]; +} + + +//=========================================================================== +// Variable deduction +//=========================================================================== +namespace +{ + template<typename Value_t> + int deduceVariables(FunctionParserBase<Value_t>& fParser, + const char* funcStr, + std::string& destVarString, + int* amountOfVariablesFound, + std::vector<std::string>* destVarNames, + bool useDegrees) + { + typedef std::set<std::string> StrSet; + StrSet varNames; + + int oldIndex = -1; + + while(true) + { + destVarString.clear(); + for(StrSet::iterator iter = varNames.begin(); + iter != varNames.end(); + ++iter) + { + if(iter != varNames.begin()) destVarString += ","; + destVarString += *iter; + } + + const int index = + fParser.Parse(funcStr, destVarString, useDegrees); + if(index < 0) break; + if(index == oldIndex) return index; + + unsigned nameLength = readIdentifier<Value_t>(funcStr + index); + if(nameLength & 0x80000000U) return index; + if(nameLength == 0) return index; + + varNames.insert(std::string(funcStr + index, nameLength)); + oldIndex = index; + } + + if(amountOfVariablesFound) + *amountOfVariablesFound = int(varNames.size()); + + if(destVarNames) + destVarNames->assign(varNames.begin(), varNames.end()); + + return -1; + } +} + +template<typename Value_t> +int FunctionParserBase<Value_t>::ParseAndDeduceVariables +(const std::string& function, + int* amountOfVariablesFound, + bool useDegrees) +{ + std::string varString; + return deduceVariables(*this, function.c_str(), varString, + amountOfVariablesFound, 0, useDegrees); +} + +template<typename Value_t> +int FunctionParserBase<Value_t>::ParseAndDeduceVariables +(const std::string& function, + std::string& resultVarString, + int* amountOfVariablesFound, + bool useDegrees) +{ + std::string varString; + const int index = + deduceVariables(*this, function.c_str(), varString, + amountOfVariablesFound, 0, useDegrees); + if(index < 0) resultVarString = varString; + return index; +} + +template<typename Value_t> +int FunctionParserBase<Value_t>::ParseAndDeduceVariables +(const std::string& function, + std::vector<std::string>& resultVars, + bool useDegrees) +{ + std::string varString; + std::vector<std::string> vars; + const int index = + deduceVariables(*this, function.c_str(), varString, + 0, &vars, useDegrees); + if(index < 0) resultVars.swap(vars); + return index; +} + + +#ifdef FUNCTIONPARSER_SUPPORT_DEBUGGING +//=========================================================================== +// Bytecode injection +//=========================================================================== +template<typename Value_t> +void FunctionParserBase<Value_t>::InjectRawByteCode +(const unsigned* bytecode, unsigned bytecodeAmount, + const Value_t* immed, unsigned immedAmount, unsigned stackSize) +{ + CopyOnWrite(); + + mData->mByteCode.assign(bytecode, bytecode + bytecodeAmount); + mData->mImmed.assign(immed, immed + immedAmount); + mData->mStackSize = stackSize; + +#ifndef FP_USE_THREAD_SAFE_EVAL + mData->mStack.resize(stackSize); +#endif +} + +//=========================================================================== +// Debug output +//=========================================================================== +#include <iomanip> +#include <sstream> +namespace +{ + inline void printHex(std::ostream& dest, unsigned n) + { + std::ios::fmtflags flags = dest.flags(); + dest.width(4); dest.fill('0'); std::hex(dest); //uppercase(dest); + dest << n; + dest.flags(flags); + } + + void padLine(std::ostringstream& dest, unsigned destLength) + { + for(std::size_t currentLength = dest.str().length(); + currentLength < destLength; + ++currentLength) + { + dest << ' '; + } + } + + const struct PowiMuliType + { + unsigned opcode_square; + unsigned opcode_cumulate; + unsigned opcode_invert; + unsigned opcode_half; + unsigned opcode_invhalf; + } iseq_powi = {cSqr,cMul,cInv,cSqrt,cRSqrt}, + iseq_muli = {~unsigned(0), cAdd,cNeg, ~unsigned(0),~unsigned(0) }; + + template<typename Value_t> + 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) + { + Value_t result = Value_t(1); + while(IP < limit) + { + if(ByteCode[IP] == opcodes.opcode_square) + { + if(!isInteger(result)) break; + result *= Value_t(2); + ++IP; + continue; + } + if(ByteCode[IP] == opcodes.opcode_invert) + { + if(result < Value_t(0)) break; + result = -result; + ++IP; + continue; + } + if(ByteCode[IP] == opcodes.opcode_half) + { + if(result > Value_t(0) && isEvenInteger(result)) + break; + if(isInteger(result * Value_t(0.5))) break; + result *= Value_t(0.5); + ++IP; + continue; + } + if(ByteCode[IP] == opcodes.opcode_invhalf) + { + if(result > Value_t(0) && isEvenInteger(result)) + break; + if(isInteger(result * Value_t(-0.5))) break; + result *= Value_t(-0.5); + ++IP; + continue; + } + + unsigned dup_fetch_pos = IP; + Value_t lhs = Value_t(1); + + if(ByteCode[IP] == cFetch) + { + unsigned index = ByteCode[++IP]; + if(index < factor_stack_base + || std::size_t(index-factor_stack_base) >= stack.size()) + { + // It wasn't a powi-fetch after all + IP = dup_fetch_pos; + break; + } + lhs = stack[index - factor_stack_base]; + // Note: ^This assumes that cFetch of recentmost + // is always converted into cDup. + goto dup_or_fetch; + } + + if(ByteCode[IP] == cDup) + { + lhs = result; + goto dup_or_fetch; + + dup_or_fetch: + stack.push_back(result); + ++IP; + Value_t subexponent = ParsePowiMuli + (opcodes, + ByteCode, IP, limit, + factor_stack_base, stack, + IgnoreExcess); + if(IP >= limit && IgnoreExcess) + return lhs*subexponent; + if(IP >= limit || ByteCode[IP] != opcodes.opcode_cumulate) + { + // It wasn't a powi-dup after all + IP = dup_fetch_pos; + break; + } + ++IP; // skip opcode_cumulate + stack.pop_back(); + result += lhs*subexponent; + continue; + } + break; + } + return result; + } + + template<typename Value_t> + Value_t ParsePowiSequence(const std::vector<unsigned>& ByteCode, + unsigned& IP, unsigned limit, + std::size_t factor_stack_base, + bool IgnoreExcess = false) + { + std::vector<Value_t> stack; + stack.push_back(Value_t(1)); + return ParsePowiMuli(iseq_powi, ByteCode, IP, limit, + factor_stack_base, stack, + IgnoreExcess); + } + + template<typename Value_t> + Value_t ParseMuliSequence(const std::vector<unsigned>& ByteCode, + unsigned& IP, unsigned limit, + std::size_t factor_stack_base, + bool IgnoreExcess = false) + { + std::vector<Value_t> stack; + stack.push_back(Value_t(1)); + return ParsePowiMuli(iseq_muli, ByteCode, IP, limit, + factor_stack_base, stack, + IgnoreExcess); + } + + struct IfInfo + { + std::pair<int,std::string> condition; + std::pair<int,std::string> thenbranch; + unsigned endif_location; + + IfInfo() : condition(), thenbranch(), endif_location() { } + }; +} + +template<typename Value_t> +void FunctionParserBase<Value_t>::PrintByteCode(std::ostream& dest, + bool showExpression) const +{ + dest << "Size of stack: " << mData->mStackSize << "\n"; + + std::ostringstream outputBuffer; + std::ostream& output = (showExpression ? outputBuffer : dest); + + const std::vector<unsigned>& ByteCode = mData->mByteCode; + const std::vector<Value_t>& Immed = mData->mImmed; + + std::vector<std::pair<int,std::string> > stack; + std::vector<IfInfo> if_stack; + + for(unsigned IP = 0, DP = 0; IP <= ByteCode.size(); ++IP) + { + after_powi_or_muli:; + std::string n; + bool out_params = false; + unsigned params = 2, produces = 1, opcode = 0; + + if(showExpression && !if_stack.empty() && + ( // Normal If termination rule: + if_stack.back().endif_location == IP + // This rule matches when cJumps are threaded: + || (IP < ByteCode.size() && ByteCode[IP] == cJump + && !if_stack.back().thenbranch.second.empty()) + )) + { + printHex(output, IP); + if(if_stack.back().endif_location == IP) + output << ": ----- (phi)"; + else + output << ": ----- (phi+)"; + + stack.resize(stack.size()+2); + std::swap(stack[stack.size()-3], stack[stack.size()-1]); + std::swap(if_stack.back().condition, stack[stack.size()-3]); + std::swap(if_stack.back().thenbranch, stack[stack.size()-2]); + opcode = cIf; + params = 3; + --IP; + if_stack.pop_back(); + } + else + { + if(IP >= ByteCode.size()) break; + opcode = ByteCode[IP]; + + if(showExpression && ( + opcode == cSqr || opcode == cDup + || opcode == cInv + || opcode == cSqrt || opcode == cRSqrt + || opcode == cFetch + )) + { + unsigned changed_ip = IP; + Value_t exponent = + ParsePowiSequence<Value_t> + (ByteCode, changed_ip, + if_stack.empty() + ? (unsigned)ByteCode.size() + : if_stack.back().endif_location, + stack.size()-1); + std::string operation_prefix; + std::ostringstream operation_value; + int prio = 0; + if(exponent == Value_t(1.0)) + { + if(opcode != cDup) goto not_powi_or_muli; + Value_t factor = + ParseMuliSequence<Value_t> + (ByteCode, changed_ip, + if_stack.empty() + ? (unsigned)ByteCode.size() + : if_stack.back().endif_location, + stack.size()-1); + if(factor == Value_t(1) || factor == Value_t(-1)) + goto not_powi_or_muli; + operation_prefix = "*"; + operation_value << factor; + prio = 3; + } + else + { + prio = 2; + operation_prefix = "^"; + operation_value << exponent; + } + + //unsigned explanation_before = changed_ip-2; + unsigned explanation_before = changed_ip-1; + + const char* explanation_prefix = "_"; + for(const unsigned first_ip = IP; IP < changed_ip; ++IP) + { + printHex(output, IP); + output << ": "; + + const char* sep = "|"; + if(first_ip+1 == changed_ip) + { sep = "="; explanation_prefix = " "; } + else if(IP == first_ip) sep = "\\"; + else if(IP+1 == changed_ip) sep = "/"; + else explanation_prefix = "="; + + switch(ByteCode[IP]) + { + case cInv: output << "inv"; break; + case cNeg: output << "neg"; break; + case cDup: output << "dup"; break; + case cSqr: output << "sqr"; break; + case cMul: output << "mul"; break; + case cAdd: output << "add"; break; + case cCbrt: output << "cbrt"; break; + case cSqrt: output << "sqrt"; break; + case cRSqrt: output << "rsqrt"; break; + case cFetch: + { + unsigned index = ByteCode[++IP]; + output << "cFetch(" << index << ")"; + break; + } + default: break; + } + padLine(outputBuffer, 20); + output << sep; + if(IP >= explanation_before) + { + explanation_before = (unsigned)ByteCode.size(); + output << explanation_prefix + << '[' << (stack.size()-1) << ']'; + std::string last = stack.back().second; + if(stack.back().first >= prio) + last = "(" + last + ")"; + output << last; + output << operation_prefix; + output << operation_value.str(); + } + else + { + unsigned p = first_ip; + Value_t exp = operation_prefix=="^" ? + ParsePowiSequence<Value_t> + (ByteCode, p, IP+1, stack.size()-1, true) : + ParseMuliSequence<Value_t> + (ByteCode, p, IP+1, stack.size()-1, true); + std::string last = stack.back().second; + if(stack.back().first >= prio) + last = "(" + last + ")"; + output << " ..." << last; + output << operation_prefix; + output << exp; + } + dest << outputBuffer.str() << std::endl; + outputBuffer.str(""); + } + + std::string& last = stack.back().second; + if(stack.back().first >= prio) + last = "(" + last + ")"; + last += operation_prefix; + last += operation_value.str(); + stack.back().first = prio; + + goto after_powi_or_muli; + } + not_powi_or_muli:; + printHex(output, IP); + output << ": "; + + switch(opcode) + { + case cIf: + { + unsigned label = ByteCode[IP+1]+1; + output << "jz "; + printHex(output, label); + params = 1; + produces = 0; + IP += 2; + + if_stack.resize(if_stack.size() + 1); + std::swap( if_stack.back().condition, stack.back() ); + if_stack.back().endif_location = (unsigned) ByteCode.size(); + stack.pop_back(); + break; + } + case cAbsIf: + { + unsigned dp = ByteCode[IP+2]; + unsigned label = ByteCode[IP+1]+1; + output << "jz_abs " << dp << ","; + printHex(output, label); + params = 1; + produces = 0; + IP += 2; + + if_stack.resize(if_stack.size() + 1); + std::swap( if_stack.back().condition, stack.back() ); + if_stack.back().endif_location = (unsigned) ByteCode.size(); + stack.pop_back(); + break; + } + + case cJump: + { + unsigned dp = ByteCode[IP+2]; + unsigned label = ByteCode[IP+1]+1; + + if(!if_stack.empty() && !stack.empty()) + { + std::swap(if_stack.back().thenbranch, stack.back()); + if_stack.back().endif_location = label; + stack.pop_back(); + } + + output << "jump " << dp << ","; + printHex(output, label); + params = 0; + produces = 0; + IP += 2; + break; + } + case cImmed: + { + if(showExpression) + { + std::ostringstream buf; + buf.precision(8); + buf << Immed[DP]; + stack.push_back( std::make_pair(0, buf.str()) ); + } + output.precision(8); + output << "push " << Immed[DP]; + ++DP; + produces = 0; + break; + } + + case cFCall: + { + const unsigned index = ByteCode[++IP]; + params = mData->mFuncPtrs[index].mParams; + static std::string name; + name = "f:" + findName(mData->mNamePtrs, index, + NameData<Value_t>::FUNC_PTR); + n = name.c_str(); + out_params = true; + break; + } + + case cPCall: + { + const unsigned index = ByteCode[++IP]; + params = mData->mFuncParsers[index].mParams; + static std::string name; + name = "p:" + findName(mData->mNamePtrs, index, + NameData<Value_t>::PARSER_PTR); + n = name.c_str(); + out_params = true; + break; + } + + default: + if(IsVarOpcode(opcode)) + { + if(showExpression) + { + stack.push_back(std::make_pair(0, + (findName(mData->mNamePtrs, opcode, + NameData<Value_t>::VARIABLE)))); + } + output << "push Var" << opcode-VarBegin; + produces = 0; + } + else + { + switch(OPCODE(opcode)) + { + case cNeg: n = "neg"; params = 1; break; + case cAdd: n = "add"; break; + case cSub: n = "sub"; break; + case cMul: n = "mul"; break; + case cDiv: n = "div"; break; + case cMod: n = "mod"; break; + case cPow: n = "pow"; break; + case cEqual: n = "eq"; break; + case cNEqual: n = "neq"; break; + case cLess: n = "lt"; break; + case cLessOrEq: n = "le"; break; + case cGreater: n = "gt"; break; + case cGreaterOrEq: n = "ge"; break; + case cAnd: n = "and"; break; + case cOr: n = "or"; break; + case cNot: n = "not"; params = 1; break; + case cNotNot: n = "notnot"; params = 1; break; + case cDeg: n = "deg"; params = 1; break; + case cRad: n = "rad"; params = 1; break; + + case cFetch: + { + unsigned index = ByteCode[++IP]; + if(showExpression && index < stack.size()) + stack.push_back(stack[index]); + output << "cFetch(" << index << ")"; + produces = 0; + break; + } + #ifdef FP_SUPPORT_OPTIMIZER + case cLog2by: n = "log2by"; params = 2; out_params = 1; break; + case cPopNMov: + { + std::size_t a = ByteCode[++IP]; + std::size_t b = ByteCode[++IP]; + if(showExpression && b < stack.size()) + { + std::pair<int, std::string> stacktop(0, "?"); + if(b < stack.size()) stacktop = stack[b]; + stack.resize(a); + stack.push_back(stacktop); + } + output << "cPopNMov(" << a << ", " << b << ")"; + produces = 0; + break; + } + case cNop: + output << "nop"; params = 0; produces = 0; + break; + #endif + case cSinCos: + { + if(showExpression) + { + std::pair<int, std::string> sin = stack.back(); + std::pair<int, std::string> cos( + 0, "cos(" + sin.second + ")"); + sin.first = 0; + sin.second = "sin(" + sin.second + ")"; + stack.back() = sin; + stack.push_back(cos); + } + output << "sincos"; + produces = 0; + break; + } + case cSinhCosh: + { + if(showExpression) + { + std::pair<int, std::string> sinh = stack.back(); + std::pair<int, std::string> cosh( + 0, "cosh(" + sinh.second + ")"); + sinh.first = 0; + sinh.second = "sinh(" + sinh.second + ")"; + stack.back() = sinh; + stack.push_back(cosh); + } + output << "sinhcosh"; + produces = 0; + break; + } + case cAbsAnd: n = "abs_and"; break; + case cAbsOr: n = "abs_or"; break; + case cAbsNot: n = "abs_not"; params = 1; break; + case cAbsNotNot: n = "abs_notnot"; params = 1; break; + case cDup: + { + if(showExpression) + stack.push_back(stack.back()); + output << "dup"; + produces = 0; + break; + } + case cInv: n = "inv"; params = 1; break; + case cSqr: n = "sqr"; params = 1; break; + case cRDiv: n = "rdiv"; break; + case cRSub: n = "rsub"; break; + case cRSqrt: n = "rsqrt"; params = 1; break; + + default: + n = Functions[opcode-cAbs].name; + params = Functions[opcode-cAbs].params; + out_params = params != 1; + } + } + } + } + if(produces) output << n; + if(out_params) output << " (" << params << ")"; + if(showExpression) + { + padLine(outputBuffer, 20); + + if(produces > 0) + { + std::ostringstream buf; + const char *paramsep = ",", *suff = ""; + int prio = 0; bool commutative = false; + switch(opcode) + { + case cIf: buf << "if("; suff = ")"; + break; + case cAbsIf: buf << "if("; suff = ")"; + break; + case cOr: prio = 6; paramsep = "|"; commutative = true; + break; + case cAnd: prio = 5; paramsep = "&"; commutative = true; + break; + case cAdd: prio = 4; paramsep = "+"; commutative = true; + break; + case cSub: prio = 4; paramsep = "-"; + break; + case cMul: prio = 3; paramsep = "*"; commutative = true; + break; + case cDiv: prio = 3; paramsep = "/"; + break; + case cPow: prio = 2; paramsep = "^"; + break; + case cAbsOr: prio = 6; paramsep = "|"; commutative = true; + break; + case cAbsAnd: prio = 5; paramsep = "&"; commutative = true; + break; + case cSqr: prio = 2; suff = "^2"; + break; + case cNeg: buf << "(-("; suff = "))"; + break; + case cNot: buf << "(!("; suff = "))"; + break; + default: buf << n << '('; suff = ")"; + } + + const char* sep = ""; + for(unsigned a=0; a<params; ++a) + { + buf << sep; + if(stack.size() + a < params) + buf << "?"; + else + { + const std::pair<int,std::string>& prev = + stack[stack.size() - params + a]; + if(prio > 0 && (prev.first > prio || + (prev.first==prio && !commutative))) + buf << '(' << prev.second << ')'; + else + buf << prev.second; + } + sep = paramsep; + } + if(stack.size() >= params) + stack.resize(stack.size() - params); + else + stack.clear(); + buf << suff; + stack.push_back(std::make_pair(prio, buf.str())); + //if(n.size() <= 4 && !out_params) padLine(outputBuffer, 20); + } + //padLine(outputBuffer, 20); + output << "= "; + if(((opcode == cIf || opcode == cAbsIf) && params != 3) + || opcode == cJump + #ifdef FP_SUPPORT_OPTIMIZER + || opcode == cNop + #endif + ) + output << "(void)"; + else if(stack.empty()) + output << "[?] ?"; + else + output << '[' << (stack.size()-1) << ']' + << stack.back().second; + } + + if(showExpression) + { + dest << outputBuffer.str() << std::endl; + outputBuffer.str(""); + } + else + output << std::endl; + } + dest << std::flush; +} +#endif + + +#ifndef FP_SUPPORT_OPTIMIZER +template<typename Value_t> +void FunctionParserBase<Value_t>::Optimize() +{ + // Do nothing if no optimizations are supported. +} +#endif + + +#define FUNCTIONPARSER_INSTANTIATE_CLASS(type) \ + template class FunctionParserBase< type >; + +#ifndef FP_DISABLE_DOUBLE_TYPE +FUNCTIONPARSER_INSTANTIATE_CLASS(double) +#endif + +#ifdef FP_SUPPORT_FLOAT_TYPE +FUNCTIONPARSER_INSTANTIATE_CLASS(float) +#endif + +#ifdef FP_SUPPORT_LONG_DOUBLE_TYPE +FUNCTIONPARSER_INSTANTIATE_CLASS(long double) +#endif + +#ifdef FP_SUPPORT_LONG_INT_TYPE +FUNCTIONPARSER_INSTANTIATE_CLASS(long) +#endif + +#ifdef FP_SUPPORT_MPFR_FLOAT_TYPE +FUNCTIONPARSER_INSTANTIATE_CLASS(MpfrFloat) +#endif + +#ifdef FP_SUPPORT_GMP_INT_TYPE +FUNCTIONPARSER_INSTANTIATE_CLASS(GmpInt) +#endif + +#ifdef FP_SUPPORT_COMPLEX_DOUBLE_TYPE +FUNCTIONPARSER_INSTANTIATE_CLASS(std::complex<double>) +#endif + +#ifdef FP_SUPPORT_COMPLEX_FLOAT_TYPE +FUNCTIONPARSER_INSTANTIATE_CLASS(std::complex<float>) +#endif + +#ifdef FP_SUPPORT_COMPLEX_LONG_DOUBLE_TYPE +FUNCTIONPARSER_INSTANTIATE_CLASS(std::complex<long double>) +#endif |