strtod.h
Engine/source/persistence/rapidjson/internal/strtod.h
Namespaces:
namespace
Detailed Description
1 2// Tencent is pleased to support the open source community by making RapidJSON available. 3// 4// Copyright (C) 2015 THL A29 Limited, a Tencent company, and Milo Yip. All rights reserved. 5// 6// Licensed under the MIT License (the "License"); you may not use this file except 7// in compliance with the License. You may obtain a copy of the License at 8// 9// http://opensource.org/licenses/MIT 10// 11// Unless required by applicable law or agreed to in writing, software distributed 12// under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR 13// CONDITIONS OF ANY KIND, either express or implied. See the License for the 14// specific language governing permissions and limitations under the License. 15 16#ifndef RAPIDJSON_STRTOD_ 17#define RAPIDJSON_STRTOD_ 18 19#include "ieee754.h" 20#include "biginteger.h" 21#include "diyfp.h" 22#include "pow10.h" 23#include <climits> 24#include <limits> 25 26RAPIDJSON_NAMESPACE_BEGIN 27namespace internal { 28 29inline double FastPath(double significand, int exp) { 30 if (exp < -308) 31 return 0.0; 32 else if (exp >= 0) 33 return significand * internal::Pow10(exp); 34 else 35 return significand / internal::Pow10(-exp); 36} 37 38inline double StrtodNormalPrecision(double d, int p) { 39 if (p < -308) { 40 // Prevent expSum < -308, making Pow10(p) = 0 41 d = FastPath(d, -308); 42 d = FastPath(d, p + 308); 43 } 44 else 45 d = FastPath(d, p); 46 return d; 47} 48 49template <typename T> 50inline T Min3(T a, T b, T c) { 51 T m = a; 52 if (m > b) m = b; 53 if (m > c) m = c; 54 return m; 55} 56 57inline int CheckWithinHalfULP(double b, const BigInteger& d, int dExp) { 58 const Double db(b); 59 const uint64_t bInt = db.IntegerSignificand(); 60 const int bExp = db.IntegerExponent(); 61 const int hExp = bExp - 1; 62 63 int dS_Exp2 = 0, dS_Exp5 = 0, bS_Exp2 = 0, bS_Exp5 = 0, hS_Exp2 = 0, hS_Exp5 = 0; 64 65 // Adjust for decimal exponent 66 if (dExp >= 0) { 67 dS_Exp2 += dExp; 68 dS_Exp5 += dExp; 69 } 70 else { 71 bS_Exp2 -= dExp; 72 bS_Exp5 -= dExp; 73 hS_Exp2 -= dExp; 74 hS_Exp5 -= dExp; 75 } 76 77 // Adjust for binary exponent 78 if (bExp >= 0) 79 bS_Exp2 += bExp; 80 else { 81 dS_Exp2 -= bExp; 82 hS_Exp2 -= bExp; 83 } 84 85 // Adjust for half ulp exponent 86 if (hExp >= 0) 87 hS_Exp2 += hExp; 88 else { 89 dS_Exp2 -= hExp; 90 bS_Exp2 -= hExp; 91 } 92 93 // Remove common power of two factor from all three scaled values 94 int common_Exp2 = Min3(dS_Exp2, bS_Exp2, hS_Exp2); 95 dS_Exp2 -= common_Exp2; 96 bS_Exp2 -= common_Exp2; 97 hS_Exp2 -= common_Exp2; 98 99 BigInteger dS = d; 100 dS.MultiplyPow5(static_cast<unsigned>(dS_Exp5)) <<= static_cast<unsigned>(dS_Exp2); 101 102 BigInteger bS(bInt); 103 bS.MultiplyPow5(static_cast<unsigned>(bS_Exp5)) <<= static_cast<unsigned>(bS_Exp2); 104 105 BigInteger hS(1); 106 hS.MultiplyPow5(static_cast<unsigned>(hS_Exp5)) <<= static_cast<unsigned>(hS_Exp2); 107 108 BigInteger delta(0); 109 dS.Difference(bS, &delta); 110 111 return delta.Compare(hS); 112} 113 114inline bool StrtodFast(double d, int p, double* result) { 115 // Use fast path for string-to-double conversion if possible 116 // see http://www.exploringbinary.com/fast-path-decimal-to-floating-point-conversion/ 117 if (p > 22 && p < 22 + 16) { 118 // Fast Path Cases In Disguise 119 d *= internal::Pow10(p - 22); 120 p = 22; 121 } 122 123 if (p >= -22 && p <= 22 && d <= 9007199254740991.0) { // 2^53 - 1 124 *result = FastPath(d, p); 125 return true; 126 } 127 else 128 return false; 129} 130 131// Compute an approximation and see if it is within 1/2 ULP 132inline bool StrtodDiyFp(const char* decimals, int dLen, int dExp, double* result) { 133 uint64_t significand = 0; 134 int i = 0; // 2^64 - 1 = 18446744073709551615, 1844674407370955161 = 0x1999999999999999 135 for (; i < dLen; i++) { 136 if (significand > RAPIDJSON_UINT64_C2(0x19999999, 0x99999999) || 137 (significand == RAPIDJSON_UINT64_C2(0x19999999, 0x99999999) && decimals[i] > '5')) 138 break; 139 significand = significand * 10u + static_cast<unsigned>(decimals[i] - '0'); 140 } 141 142 if (i < dLen && decimals[i] >= '5') // Rounding 143 significand++; 144 145 int remaining = dLen - i; 146 const int kUlpShift = 3; 147 const int kUlp = 1 << kUlpShift; 148 int64_t error = (remaining == 0) ? 0 : kUlp / 2; 149 150 DiyFp v(significand, 0); 151 v = v.Normalize(); 152 error <<= -v.e; 153 154 dExp += remaining; 155 156 int actualExp; 157 DiyFp cachedPower = GetCachedPower10(dExp, &actualExp); 158 if (actualExp != dExp) { 159 static const DiyFp kPow10[] = { 160 DiyFp(RAPIDJSON_UINT64_C2(0xa0000000, 0x00000000), -60), // 10^1 161 DiyFp(RAPIDJSON_UINT64_C2(0xc8000000, 0x00000000), -57), // 10^2 162 DiyFp(RAPIDJSON_UINT64_C2(0xfa000000, 0x00000000), -54), // 10^3 163 DiyFp(RAPIDJSON_UINT64_C2(0x9c400000, 0x00000000), -50), // 10^4 164 DiyFp(RAPIDJSON_UINT64_C2(0xc3500000, 0x00000000), -47), // 10^5 165 DiyFp(RAPIDJSON_UINT64_C2(0xf4240000, 0x00000000), -44), // 10^6 166 DiyFp(RAPIDJSON_UINT64_C2(0x98968000, 0x00000000), -40) // 10^7 167 }; 168 int adjustment = dExp - actualExp; 169 RAPIDJSON_ASSERT(adjustment >= 1 && adjustment < 8); 170 v = v * kPow10[adjustment - 1]; 171 if (dLen + adjustment > 19) // has more digits than decimal digits in 64-bit 172 error += kUlp / 2; 173 } 174 175 v = v * cachedPower; 176 177 error += kUlp + (error == 0 ? 0 : 1); 178 179 const int oldExp = v.e; 180 v = v.Normalize(); 181 error <<= oldExp - v.e; 182 183 const int effectiveSignificandSize = Double::EffectiveSignificandSize(64 + v.e); 184 int precisionSize = 64 - effectiveSignificandSize; 185 if (precisionSize + kUlpShift >= 64) { 186 int scaleExp = (precisionSize + kUlpShift) - 63; 187 v.f >>= scaleExp; 188 v.e += scaleExp; 189 error = (error >> scaleExp) + 1 + kUlp; 190 precisionSize -= scaleExp; 191 } 192 193 DiyFp rounded(v.f >> precisionSize, v.e + precisionSize); 194 const uint64_t precisionBits = (v.f & ((uint64_t(1) << precisionSize) - 1)) * kUlp; 195 const uint64_t halfWay = (uint64_t(1) << (precisionSize - 1)) * kUlp; 196 if (precisionBits >= halfWay + static_cast<unsigned>(error)) { 197 rounded.f++; 198 if (rounded.f & (DiyFp::kDpHiddenBit << 1)) { // rounding overflows mantissa (issue #340) 199 rounded.f >>= 1; 200 rounded.e++; 201 } 202 } 203 204 *result = rounded.ToDouble(); 205 206 return halfWay - static_cast<unsigned>(error) >= precisionBits || precisionBits >= halfWay + static_cast<unsigned>(error); 207} 208 209inline double StrtodBigInteger(double approx, const char* decimals, int dLen, int dExp) { 210 RAPIDJSON_ASSERT(dLen >= 0); 211 const BigInteger dInt(decimals, static_cast<unsigned>(dLen)); 212 Double a(approx); 213 int cmp = CheckWithinHalfULP(a.Value(), dInt, dExp); 214 if (cmp < 0) 215 return a.Value(); // within half ULP 216 else if (cmp == 0) { 217 // Round towards even 218 if (a.Significand() & 1) 219 return a.NextPositiveDouble(); 220 else 221 return a.Value(); 222 } 223 else // adjustment 224 return a.NextPositiveDouble(); 225} 226 227inline double StrtodFullPrecision(double d, int p, const char* decimals, size_t length, size_t decimalPosition, int exp) { 228 RAPIDJSON_ASSERT(d >= 0.0); 229 RAPIDJSON_ASSERT(length >= 1); 230 231 double result = 0.0; 232 if (StrtodFast(d, p, &result)) 233 return result; 234 235 RAPIDJSON_ASSERT(length <= INT_MAX); 236 int dLen = static_cast<int>(length); 237 238 RAPIDJSON_ASSERT(length >= decimalPosition); 239 RAPIDJSON_ASSERT(length - decimalPosition <= INT_MAX); 240 int dExpAdjust = static_cast<int>(length - decimalPosition); 241 242 RAPIDJSON_ASSERT(exp >= INT_MIN + dExpAdjust); 243 int dExp = exp - dExpAdjust; 244 245 // Make sure length+dExp does not overflow 246 RAPIDJSON_ASSERT(dExp <= INT_MAX - dLen); 247 248 // Trim leading zeros 249 while (dLen > 0 && *decimals == '0') { 250 dLen--; 251 decimals++; 252 } 253 254 // Trim trailing zeros 255 while (dLen > 0 && decimals[dLen - 1] == '0') { 256 dLen--; 257 dExp++; 258 } 259 260 if (dLen == 0) { // Buffer only contains zeros. 261 return 0.0; 262 } 263 264 // Trim right-most digits 265 const int kMaxDecimalDigit = 767 + 1; 266 if (dLen > kMaxDecimalDigit) { 267 dExp += dLen - kMaxDecimalDigit; 268 dLen = kMaxDecimalDigit; 269 } 270 271 // If too small, underflow to zero. 272 // Any x <= 10^-324 is interpreted as zero. 273 if (dLen + dExp <= -324) 274 return 0.0; 275 276 // If too large, overflow to infinity. 277 // Any x >= 10^309 is interpreted as +infinity. 278 if (dLen + dExp > 309) 279 return std::numeric_limits<double>::infinity(); 280 281 if (StrtodDiyFp(decimals, dLen, dExp, &result)) 282 return result; 283 284 // Use approximation from StrtodDiyFp and make adjustment with BigInteger comparison 285 return StrtodBigInteger(result, decimals, dLen, dExp); 286} 287 288} // namespace internal 289RAPIDJSON_NAMESPACE_END 290 291#endif // RAPIDJSON_STRTOD_ 292