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 // This is a C++ header-only implementation of Grisu2 algorithm from the publication:
16 // Loitsch, Florian. "Printing floating-point numbers quickly and accurately with
17 // integers." ACM Sigplan Notices 45.6 (2010): 233-243.
19 #ifndef RAPIDJSON_DTOA_
20 #define RAPIDJSON_DTOA_
22 #include "itoa.h" // GetDigitsLut()
26 RAPIDJSON_NAMESPACE_BEGIN
31 RAPIDJSON_DIAG_OFF(effc
++)
32 RAPIDJSON_DIAG_OFF(array
-bounds
) // some gcc versions generate wrong warnings https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59124
35 inline void GrisuRound(char* buffer
, int len
, uint64_t delta
, uint64_t rest
, uint64_t ten_kappa
, uint64_t wp_w
) {
36 while (rest
< wp_w
&& delta
- rest
>= ten_kappa
&&
37 (rest
+ ten_kappa
< wp_w
|| /// closer
38 wp_w
- rest
> rest
+ ten_kappa
- wp_w
)) {
44 inline unsigned CountDecimalDigit32(uint32_t n
) {
45 // Simple pure C++ implementation was faster than __builtin_clz version in this situation.
47 if (n
< 100) return 2;
48 if (n
< 1000) return 3;
49 if (n
< 10000) return 4;
50 if (n
< 100000) return 5;
51 if (n
< 1000000) return 6;
52 if (n
< 10000000) return 7;
53 if (n
< 100000000) return 8;
54 // Will not reach 10 digits in DigitGen()
55 //if (n < 1000000000) return 9;
60 inline void DigitGen(const DiyFp
& W
, const DiyFp
& Mp
, uint64_t delta
, char* buffer
, int* len
, int* K
) {
61 static const uint32_t kPow10
[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };
62 const DiyFp
one(uint64_t(1) << -Mp
.e
, Mp
.e
);
63 const DiyFp wp_w
= Mp
- W
;
64 uint32_t p1
= static_cast<uint32_t>(Mp
.f
>> -one
.e
);
65 uint64_t p2
= Mp
.f
& (one
.f
- 1);
66 unsigned kappa
= CountDecimalDigit32(p1
); // kappa in [0, 9]
72 case 9: d
= p1
/ 100000000; p1
%= 100000000; break;
73 case 8: d
= p1
/ 10000000; p1
%= 10000000; break;
74 case 7: d
= p1
/ 1000000; p1
%= 1000000; break;
75 case 6: d
= p1
/ 100000; p1
%= 100000; break;
76 case 5: d
= p1
/ 10000; p1
%= 10000; break;
77 case 4: d
= p1
/ 1000; p1
%= 1000; break;
78 case 3: d
= p1
/ 100; p1
%= 100; break;
79 case 2: d
= p1
/ 10; p1
%= 10; break;
80 case 1: d
= p1
; p1
= 0; break;
84 buffer
[(*len
)++] = static_cast<char>('0' + static_cast<char>(d
));
86 uint64_t tmp
= (static_cast<uint64_t>(p1
) << -one
.e
) + p2
;
89 GrisuRound(buffer
, *len
, delta
, tmp
, static_cast<uint64_t>(kPow10
[kappa
]) << -one
.e
, wp_w
.f
);
98 char d
= static_cast<char>(p2
>> -one
.e
);
100 buffer
[(*len
)++] = static_cast<char>('0' + d
);
105 int index
= -static_cast<int>(kappa
);
106 GrisuRound(buffer
, *len
, delta
, p2
, one
.f
, wp_w
.f
* (index
< 9 ? kPow10
[-static_cast<int>(kappa
)] : 0));
112 inline void Grisu2(double value
, char* buffer
, int* length
, int* K
) {
113 const DiyFp
v(value
);
115 v
.NormalizedBoundaries(&w_m
, &w_p
);
117 const DiyFp c_mk
= GetCachedPower(w_p
.e
, K
);
118 const DiyFp W
= v
.Normalize() * c_mk
;
119 DiyFp Wp
= w_p
* c_mk
;
120 DiyFp Wm
= w_m
* c_mk
;
123 DigitGen(W
, Wp
, Wp
.f
- Wm
.f
, buffer
, length
, K
);
126 inline char* WriteExponent(int K
, char* buffer
) {
133 *buffer
++ = static_cast<char>('0' + static_cast<char>(K
/ 100));
135 const char* d
= GetDigitsLut() + K
* 2;
140 const char* d
= GetDigitsLut() + K
* 2;
145 *buffer
++ = static_cast<char>('0' + static_cast<char>(K
));
150 inline char* Prettify(char* buffer
, int length
, int k
, int maxDecimalPlaces
) {
151 const int kk
= length
+ k
; // 10^(kk-1) <= v < 10^kk
153 if (0 <= k
&& kk
<= 21) {
154 // 1234e7 -> 12340000000
155 for (int i
= length
; i
< kk
; i
++)
158 buffer
[kk
+ 1] = '0';
159 return &buffer
[kk
+ 2];
161 else if (0 < kk
&& kk
<= 21) {
163 std::memmove(&buffer
[kk
+ 1], &buffer
[kk
], static_cast<size_t>(length
- kk
));
165 if (0 > k
+ maxDecimalPlaces
) {
166 // When maxDecimalPlaces = 2, 1.2345 -> 1.23, 1.102 -> 1.1
167 // Remove extra trailing zeros (at least one) after truncation.
168 for (int i
= kk
+ maxDecimalPlaces
; i
> kk
+ 1; i
--)
169 if (buffer
[i
] != '0')
170 return &buffer
[i
+ 1];
171 return &buffer
[kk
+ 2]; // Reserve one zero
174 return &buffer
[length
+ 1];
176 else if (-6 < kk
&& kk
<= 0) {
177 // 1234e-6 -> 0.001234
178 const int offset
= 2 - kk
;
179 std::memmove(&buffer
[offset
], &buffer
[0], static_cast<size_t>(length
));
182 for (int i
= 2; i
< offset
; i
++)
184 if (length
- kk
> maxDecimalPlaces
) {
185 // When maxDecimalPlaces = 2, 0.123 -> 0.12, 0.102 -> 0.1
186 // Remove extra trailing zeros (at least one) after truncation.
187 for (int i
= maxDecimalPlaces
+ 1; i
> 2; i
--)
188 if (buffer
[i
] != '0')
189 return &buffer
[i
+ 1];
190 return &buffer
[3]; // Reserve one zero
193 return &buffer
[length
+ offset
];
195 else if (kk
< -maxDecimalPlaces
) {
202 else if (length
== 1) {
205 return WriteExponent(kk
- 1, &buffer
[2]);
208 // 1234e30 -> 1.234e33
209 std::memmove(&buffer
[2], &buffer
[1], static_cast<size_t>(length
- 1));
211 buffer
[length
+ 1] = 'e';
212 return WriteExponent(kk
- 1, &buffer
[0 + length
+ 2]);
216 inline char* dtoa(double value
, char* buffer
, int maxDecimalPlaces
= 324) {
217 RAPIDJSON_ASSERT(maxDecimalPlaces
>= 1);
221 *buffer
++ = '-'; // -0.0, Issue #289
233 Grisu2(value
, buffer
, &length
, &K
);
234 return Prettify(buffer
, length
, K
, maxDecimalPlaces
);
242 } // namespace internal
243 RAPIDJSON_NAMESPACE_END
245 #endif // RAPIDJSON_DTOA_