dtoa.h
Go to the documentation of this file.
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 
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 
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  int 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 = -kappa;
106  GrisuRound(buffer, *len, delta, p2, one.f, wp_w.f * (index < 9 ? kPow10[index] : 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
244 
245 #endif // RAPIDJSON_DTOA_
#define RAPIDJSON_ASSERT(x)
Assertion.
Definition: rapidjson.h:406
#define RAPIDJSON_NAMESPACE_END
provide custom rapidjson namespace (closing expression)
Definition: rapidjson.h:124
char * Prettify(char *buffer, int length, int k, int maxDecimalPlaces)
Definition: dtoa.h:150
const char * GetDigitsLut()
Definition: itoa.h:23
#define RAPIDJSON_NAMESPACE_BEGIN
provide custom rapidjson namespace (opening expression)
Definition: rapidjson.h:121
DiyFp Normalize() const
Definition: diyfp.h:102
bool Sign() const
Definition: ieee754.h:37
auto array(Array const &a)
Returns a manipulator which will print the specified array.
Definition: DumpUtils.h:228
void Grisu2(double value, char *buffer, int *length, int *K)
Definition: dtoa.h:112
unsigned int uint32_t
Definition: stdint.h:126
bool IsZero() const
Definition: ieee754.h:45
void GrisuRound(char *buffer, int len, uint64_t delta, uint64_t rest, uint64_t ten_kappa, uint64_t wp_w)
Definition: dtoa.h:35
std::void_t< T > n
unsigned __int64 uint64_t
Definition: stdint.h:136
string tmp
Definition: languages.py:63
uint64_t f
Definition: diyfp.h:171
void DigitGen(const DiyFp &W, const DiyFp &Mp, uint64_t delta, char *buffer, int *len, int *K)
Definition: dtoa.h:60
BoundingBox bounds(int x, int y, int w, int h)
Definition: main.cpp:37
char * WriteExponent(int K, char *buffer)
Definition: dtoa.h:126
int CountDecimalDigit32(uint32_t n)
Definition: dtoa.h:44
const GenericPointer< typename T::ValueType > T2 value
Definition: pointer.h:1225
void NormalizedBoundaries(DiyFp *minus, DiyFp *plus) const
Definition: diyfp.h:132
DiyFp GetCachedPower(int e, int *K)
Definition: diyfp.h:238
char * dtoa(double value, char *buffer, int maxDecimalPlaces=324)
Definition: dtoa.h:216