]>
Commit | Line | Data |
---|---|---|
31f18b77 FG |
1 | // Tencent is pleased to support the open source community by making RapidJSON available. |
2 | // | |
3 | // Copyright (C) 2015 THL A29 Limited, a Tencent company, and Milo Yip. All rights reserved. | |
4 | // | |
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 | |
7 | // | |
8 | // http://opensource.org/licenses/MIT | |
9 | // | |
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. | |
14 | ||
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. | |
18 | ||
19 | #ifndef RAPIDJSON_DTOA_ | |
20 | #define RAPIDJSON_DTOA_ | |
21 | ||
22 | #include "itoa.h" // GetDigitsLut() | |
23 | #include "diyfp.h" | |
24 | #include "ieee754.h" | |
25 | ||
26 | RAPIDJSON_NAMESPACE_BEGIN | |
27 | namespace internal { | |
28 | ||
29 | #ifdef __GNUC__ | |
30 | RAPIDJSON_DIAG_PUSH | |
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 | |
33 | #endif | |
34 | ||
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)) { | |
39 | buffer[len - 1]--; | |
40 | rest += ten_kappa; | |
41 | } | |
42 | } | |
43 | ||
44 | inline unsigned CountDecimalDigit32(uint32_t n) { | |
45 | // Simple pure C++ implementation was faster than __builtin_clz version in this situation. | |
46 | if (n < 10) return 1; | |
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; | |
56 | //return 10; | |
57 | return 9; | |
58 | } | |
59 | ||
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] | |
67 | *len = 0; | |
68 | ||
69 | while (kappa > 0) { | |
70 | uint32_t d = 0; | |
71 | switch (kappa) { | |
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; | |
81 | default:; | |
82 | } | |
83 | if (d || *len) | |
84 | buffer[(*len)++] = static_cast<char>('0' + static_cast<char>(d)); | |
85 | kappa--; | |
86 | uint64_t tmp = (static_cast<uint64_t>(p1) << -one.e) + p2; | |
87 | if (tmp <= delta) { | |
88 | *K += kappa; | |
89 | GrisuRound(buffer, *len, delta, tmp, static_cast<uint64_t>(kPow10[kappa]) << -one.e, wp_w.f); | |
90 | return; | |
91 | } | |
92 | } | |
93 | ||
94 | // kappa = 0 | |
95 | for (;;) { | |
96 | p2 *= 10; | |
97 | delta *= 10; | |
98 | char d = static_cast<char>(p2 >> -one.e); | |
99 | if (d || *len) | |
100 | buffer[(*len)++] = static_cast<char>('0' + d); | |
101 | p2 &= one.f - 1; | |
102 | kappa--; | |
103 | if (p2 < delta) { | |
104 | *K += kappa; | |
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)); | |
107 | return; | |
108 | } | |
109 | } | |
110 | } | |
111 | ||
112 | inline void Grisu2(double value, char* buffer, int* length, int* K) { | |
113 | const DiyFp v(value); | |
114 | DiyFp w_m, w_p; | |
115 | v.NormalizedBoundaries(&w_m, &w_p); | |
116 | ||
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; | |
121 | Wm.f++; | |
122 | Wp.f--; | |
123 | DigitGen(W, Wp, Wp.f - Wm.f, buffer, length, K); | |
124 | } | |
125 | ||
126 | inline char* WriteExponent(int K, char* buffer) { | |
127 | if (K < 0) { | |
128 | *buffer++ = '-'; | |
129 | K = -K; | |
130 | } | |
131 | ||
132 | if (K >= 100) { | |
133 | *buffer++ = static_cast<char>('0' + static_cast<char>(K / 100)); | |
134 | K %= 100; | |
135 | const char* d = GetDigitsLut() + K * 2; | |
136 | *buffer++ = d[0]; | |
137 | *buffer++ = d[1]; | |
138 | } | |
139 | else if (K >= 10) { | |
140 | const char* d = GetDigitsLut() + K * 2; | |
141 | *buffer++ = d[0]; | |
142 | *buffer++ = d[1]; | |
143 | } | |
144 | else | |
145 | *buffer++ = static_cast<char>('0' + static_cast<char>(K)); | |
146 | ||
147 | return buffer; | |
148 | } | |
149 | ||
150 | inline char* Prettify(char* buffer, int length, int k, int maxDecimalPlaces) { | |
151 | const int kk = length + k; // 10^(kk-1) <= v < 10^kk | |
152 | ||
153 | if (0 <= k && kk <= 21) { | |
154 | // 1234e7 -> 12340000000 | |
155 | for (int i = length; i < kk; i++) | |
156 | buffer[i] = '0'; | |
157 | buffer[kk] = '.'; | |
158 | buffer[kk + 1] = '0'; | |
159 | return &buffer[kk + 2]; | |
160 | } | |
161 | else if (0 < kk && kk <= 21) { | |
162 | // 1234e-2 -> 12.34 | |
163 | std::memmove(&buffer[kk + 1], &buffer[kk], static_cast<size_t>(length - kk)); | |
164 | buffer[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 | |
172 | } | |
173 | else | |
174 | return &buffer[length + 1]; | |
175 | } | |
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)); | |
180 | buffer[0] = '0'; | |
181 | buffer[1] = '.'; | |
182 | for (int i = 2; i < offset; i++) | |
183 | buffer[i] = '0'; | |
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 | |
191 | } | |
192 | else | |
193 | return &buffer[length + offset]; | |
194 | } | |
195 | else if (kk < -maxDecimalPlaces) { | |
196 | // Truncate to zero | |
197 | buffer[0] = '0'; | |
198 | buffer[1] = '.'; | |
199 | buffer[2] = '0'; | |
200 | return &buffer[3]; | |
201 | } | |
202 | else if (length == 1) { | |
203 | // 1e30 | |
204 | buffer[1] = 'e'; | |
205 | return WriteExponent(kk - 1, &buffer[2]); | |
206 | } | |
207 | else { | |
208 | // 1234e30 -> 1.234e33 | |
209 | std::memmove(&buffer[2], &buffer[1], static_cast<size_t>(length - 1)); | |
210 | buffer[1] = '.'; | |
211 | buffer[length + 1] = 'e'; | |
212 | return WriteExponent(kk - 1, &buffer[0 + length + 2]); | |
213 | } | |
214 | } | |
215 | ||
216 | inline char* dtoa(double value, char* buffer, int maxDecimalPlaces = 324) { | |
217 | RAPIDJSON_ASSERT(maxDecimalPlaces >= 1); | |
218 | Double d(value); | |
219 | if (d.IsZero()) { | |
220 | if (d.Sign()) | |
221 | *buffer++ = '-'; // -0.0, Issue #289 | |
222 | buffer[0] = '0'; | |
223 | buffer[1] = '.'; | |
224 | buffer[2] = '0'; | |
225 | return &buffer[3]; | |
226 | } | |
227 | else { | |
228 | if (value < 0) { | |
229 | *buffer++ = '-'; | |
230 | value = -value; | |
231 | } | |
232 | int length, K; | |
233 | Grisu2(value, buffer, &length, &K); | |
234 | return Prettify(buffer, length, K, maxDecimalPlaces); | |
235 | } | |
236 | } | |
237 | ||
238 | #ifdef __GNUC__ | |
239 | RAPIDJSON_DIAG_POP | |
240 | #endif | |
241 | ||
242 | } // namespace internal | |
243 | RAPIDJSON_NAMESPACE_END | |
244 | ||
245 | #endif // RAPIDJSON_DTOA_ |