1 // Tencent is pleased to support the open source community by making RapidJSON available.
3 // Copyright (C) 2015 THL A29 Limited, a Tencent company, and Milo Yip. All rights reserved.
5 // Licensed under the MIT License (the "License"); you may not use this file except
6 // in compliance with the License. You may obtain a copy of the License at
8 // http://opensource.org/licenses/MIT
10 // Unless required by applicable law or agreed to in writing, software distributed
11 // under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR
12 // CONDITIONS OF ANY KIND, either express or implied. See the License for the
13 // specific language governing permissions and limitations under the License.
15 #ifndef RAPIDJSON_STRTOD_
16 #define RAPIDJSON_STRTOD_
19 #include "biginteger.h"
23 RAPIDJSON_NAMESPACE_BEGIN
26 inline double FastPath(double significand
, int exp
) {
30 return significand
* internal::Pow10(exp
);
32 return significand
/ internal::Pow10(-exp
);
35 inline double StrtodNormalPrecision(double d
, int p
) {
37 // Prevent expSum < -308, making Pow10(p) = 0
38 d
= FastPath(d
, -308);
39 d
= FastPath(d
, p
+ 308);
47 inline T
Min3(T a
, T b
, T c
) {
54 inline int CheckWithinHalfULP(double b
, const BigInteger
& d
, int dExp
) {
56 const uint64_t bInt
= db
.IntegerSignificand();
57 const int bExp
= db
.IntegerExponent();
58 const int hExp
= bExp
- 1;
60 int dS_Exp2
= 0, dS_Exp5
= 0, bS_Exp2
= 0, bS_Exp5
= 0, hS_Exp2
= 0, hS_Exp5
= 0;
62 // Adjust for decimal exponent
74 // Adjust for binary exponent
82 // Adjust for half ulp exponent
90 // Remove common power of two factor from all three scaled values
91 int common_Exp2
= Min3(dS_Exp2
, bS_Exp2
, hS_Exp2
);
92 dS_Exp2
-= common_Exp2
;
93 bS_Exp2
-= common_Exp2
;
94 hS_Exp2
-= common_Exp2
;
97 dS
.MultiplyPow5(static_cast<unsigned>(dS_Exp5
)) <<= static_cast<unsigned>(dS_Exp2
);
100 bS
.MultiplyPow5(static_cast<unsigned>(bS_Exp5
)) <<= static_cast<unsigned>(bS_Exp2
);
103 hS
.MultiplyPow5(static_cast<unsigned>(hS_Exp5
)) <<= static_cast<unsigned>(hS_Exp2
);
106 dS
.Difference(bS
, &delta
);
108 return delta
.Compare(hS
);
111 inline bool StrtodFast(double d
, int p
, double* result
) {
112 // Use fast path for string-to-double conversion if possible
113 // see http://www.exploringbinary.com/fast-path-decimal-to-floating-point-conversion/
114 if (p
> 22 && p
< 22 + 16) {
115 // Fast Path Cases In Disguise
116 d
*= internal::Pow10(p
- 22);
120 if (p
>= -22 && p
<= 22 && d
<= 9007199254740991.0) { // 2^53 - 1
121 *result
= FastPath(d
, p
);
128 // Compute an approximation and see if it is within 1/2 ULP
129 inline bool StrtodDiyFp(const char* decimals
, size_t length
, size_t decimalPosition
, int exp
, double* result
) {
130 uint64_t significand
= 0;
131 size_t i
= 0; // 2^64 - 1 = 18446744073709551615, 1844674407370955161 = 0x1999999999999999
132 for (; i
< length
; i
++) {
133 if (significand
> RAPIDJSON_UINT64_C2(0x19999999, 0x99999999) ||
134 (significand
== RAPIDJSON_UINT64_C2(0x19999999, 0x99999999) && decimals
[i
] > '5'))
136 significand
= significand
* 10u + static_cast<unsigned>(decimals
[i
] - '0');
139 if (i
< length
&& decimals
[i
] >= '5') // Rounding
142 size_t remaining
= length
- i
;
143 const unsigned kUlpShift
= 3;
144 const unsigned kUlp
= 1 << kUlpShift
;
145 int64_t error
= (remaining
== 0) ? 0 : kUlp
/ 2;
147 DiyFp
v(significand
, 0);
151 const int dExp
= static_cast<int>(decimalPosition
) - static_cast<int>(i
) + exp
;
154 DiyFp cachedPower
= GetCachedPower10(dExp
, &actualExp
);
155 if (actualExp
!= dExp
) {
156 static const DiyFp kPow10
[] = {
157 DiyFp(RAPIDJSON_UINT64_C2(0xa0000000, 00000000), -60), // 10^1
158 DiyFp(RAPIDJSON_UINT64_C2(0xc8000000, 00000000), -57), // 10^2
159 DiyFp(RAPIDJSON_UINT64_C2(0xfa000000, 00000000), -54), // 10^3
160 DiyFp(RAPIDJSON_UINT64_C2(0x9c400000, 00000000), -50), // 10^4
161 DiyFp(RAPIDJSON_UINT64_C2(0xc3500000, 00000000), -47), // 10^5
162 DiyFp(RAPIDJSON_UINT64_C2(0xf4240000, 00000000), -44), // 10^6
163 DiyFp(RAPIDJSON_UINT64_C2(0x98968000, 00000000), -40) // 10^7
165 int adjustment
= dExp
- actualExp
- 1;
166 RAPIDJSON_ASSERT(adjustment
>= 0 && adjustment
< 7);
167 v
= v
* kPow10
[adjustment
];
168 if (length
+ static_cast<unsigned>(adjustment
)> 19u) // has more digits than decimal digits in 64-bit
174 error
+= kUlp
+ (error
== 0 ? 0 : 1);
176 const int oldExp
= v
.e
;
178 error
<<= oldExp
- v
.e
;
180 const unsigned effectiveSignificandSize
= Double::EffectiveSignificandSize(64 + v
.e
);
181 unsigned precisionSize
= 64 - effectiveSignificandSize
;
182 if (precisionSize
+ kUlpShift
>= 64) {
183 unsigned scaleExp
= (precisionSize
+ kUlpShift
) - 63;
186 error
= (error
>> scaleExp
) + 1 + static_cast<int>(kUlp
);
187 precisionSize
-= scaleExp
;
190 DiyFp
rounded(v
.f
>> precisionSize
, v
.e
+ static_cast<int>(precisionSize
));
191 const uint64_t precisionBits
= (v
.f
& ((uint64_t(1) << precisionSize
) - 1)) * kUlp
;
192 const uint64_t halfWay
= (uint64_t(1) << (precisionSize
- 1)) * kUlp
;
193 if (precisionBits
>= halfWay
+ static_cast<unsigned>(error
)) {
195 if (rounded
.f
& (DiyFp::kDpHiddenBit
<< 1)) { // rounding overflows mantissa (issue #340)
201 *result
= rounded
.ToDouble();
203 return halfWay
- static_cast<unsigned>(error
) >= precisionBits
|| precisionBits
>= halfWay
+ static_cast<unsigned>(error
);
206 inline double StrtodBigInteger(double approx
, const char* decimals
, size_t length
, size_t decimalPosition
, int exp
) {
207 const BigInteger
dInt(decimals
, length
);
208 const int dExp
= static_cast<int>(decimalPosition
) - static_cast<int>(length
) + exp
;
210 int cmp
= CheckWithinHalfULP(a
.Value(), dInt
, dExp
);
212 return a
.Value(); // within half ULP
214 // Round towards even
215 if (a
.Significand() & 1)
216 return a
.NextPositiveDouble();
221 return a
.NextPositiveDouble();
224 inline double StrtodFullPrecision(double d
, int p
, const char* decimals
, size_t length
, size_t decimalPosition
, int exp
) {
225 RAPIDJSON_ASSERT(d
>= 0.0);
226 RAPIDJSON_ASSERT(length
>= 1);
229 if (StrtodFast(d
, p
, &result
))
232 // Trim leading zeros
233 while (*decimals
== '0' && length
> 1) {
239 // Trim trailing zeros
240 while (decimals
[length
- 1] == '0' && length
> 1) {
246 // Trim right-most digits
247 const int kMaxDecimalDigit
= 780;
248 if (static_cast<int>(length
) > kMaxDecimalDigit
) {
249 int delta
= (static_cast<int>(length
) - kMaxDecimalDigit
);
251 decimalPosition
-= static_cast<unsigned>(delta
);
252 length
= kMaxDecimalDigit
;
255 // If too small, underflow to zero
256 if (int(length
) + exp
< -324)
259 if (StrtodDiyFp(decimals
, length
, decimalPosition
, exp
, &result
))
262 // Use approximation from StrtodDiyFp and make adjustment with BigInteger comparison
263 return StrtodBigInteger(result
, decimals
, length
, decimalPosition
, exp
);
266 } // namespace internal
267 RAPIDJSON_NAMESPACE_END
269 #endif // RAPIDJSON_STRTOD_