1 /*
2 * Copyright (C) Alexander Borisov
3 *
4 * Based on nxt_dtoa.c from NGINX NJS project
5 *
6 * Copyright (C) Dmitry Volyntsev
7 * Copyright (C) NGINX, Inc.
8 *
9 * Grisu2 algorithm implementation for printing floating-point numbers based
10 * upon the work of Milo Yip and Doug Currie.
11 *
12 * For algorithm information, see Loitsch, Florian. "Printing
13 * floating-point numbers quickly and accurately with integers." ACM Sigplan
14 * Notices 45.6 (2010): 233-243.
15 *
16 * Copyright (C) 2015 Doug Currie
17 * based on dtoa_milo.h
18 * Copyright (C) 2014 Milo Yip
19 *
20 * Permission is hereby granted, free of charge, to any person obtaining a copy
21 * of this software and associated documentation files (the "Software"), to deal
22 * in the Software without restriction, including without limitation the rights
23 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
24 * copies of the Software, and to permit persons to whom the Software is
25 * furnished to do so, subject to the following conditions:
26 *
27 * The above copyright notice and this permission notice shall be included in
28 * all copies or substantial portions of the Software.
29 *
30 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
31 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
32 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
33 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
34 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
35 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
36 * THE SOFTWARE.
37 */
38
39 #include "lexbor/core/str.h"
40 #include "lexbor/core/diyfp.h"
41 #include "lexbor/core/dtoa.h"
42
43 #include <math.h>
44 #include <string.h>
45
46
47 lxb_inline void
lexbor_grisu2_round(lxb_char_t * start,size_t len,uint64_t delta,uint64_t rest,uint64_t ten_kappa,uint64_t wp_w)48 lexbor_grisu2_round(lxb_char_t *start, size_t len, uint64_t delta, uint64_t rest,
49 uint64_t ten_kappa, uint64_t wp_w)
50 {
51 while (rest < wp_w && delta - rest >= ten_kappa
52 && (rest + ten_kappa < wp_w || /* closer */
53 wp_w - rest > rest + ten_kappa - wp_w))
54 {
55 start[len - 1]--;
56 rest += ten_kappa;
57 }
58 }
59
60 lxb_inline int
lexbor_dec_count(uint32_t n)61 lexbor_dec_count(uint32_t n)
62 {
63 if (n < 10) return 1;
64 if (n < 100) return 2;
65 if (n < 1000) return 3;
66 if (n < 10000) return 4;
67 if (n < 100000) return 5;
68 if (n < 1000000) return 6;
69 if (n < 10000000) return 7;
70 if (n < 100000000) return 8;
71 if (n < 1000000000) return 9;
72
73 return 10;
74 }
75
76 lxb_inline size_t
lexbor_grisu2_gen(lexbor_diyfp_t W,lexbor_diyfp_t Mp,uint64_t delta,lxb_char_t * begin,lxb_char_t * end,int * dec_exp)77 lexbor_grisu2_gen(lexbor_diyfp_t W, lexbor_diyfp_t Mp, uint64_t delta,
78 lxb_char_t *begin, lxb_char_t *end, int *dec_exp)
79 {
80 int kappa;
81 lxb_char_t c, *p;
82 uint32_t p1, d;
83 uint64_t p2, tmp;
84 lexbor_diyfp_t one, wp_w;
85
86 static const uint64_t pow10[] = {
87 1,
88 10,
89 100,
90 1000,
91 10000,
92 100000,
93 1000000,
94 10000000,
95 100000000,
96 1000000000
97 };
98
99 wp_w = lexbor_diyfp_sub(Mp, W);
100
101 one = lexbor_diyfp((uint64_t) 1 << -Mp.exp, Mp.exp);
102 p1 = (uint32_t) (Mp.significand >> -one.exp);
103 p2 = Mp.significand & (one.significand - 1);
104
105 p = begin;
106
107 /* GCC 4.2 complains about uninitialized d. */
108 d = 0;
109
110 kappa = lexbor_dec_count(p1);
111
112 while (kappa > 0) {
113 switch (kappa) {
114 case 10: d = p1 / 1000000000; p1 %= 1000000000; break;
115 case 9: d = p1 / 100000000; p1 %= 100000000; break;
116 case 8: d = p1 / 10000000; p1 %= 10000000; break;
117 case 7: d = p1 / 1000000; p1 %= 1000000; break;
118 case 6: d = p1 / 100000; p1 %= 100000; break;
119 case 5: d = p1 / 10000; p1 %= 10000; break;
120 case 4: d = p1 / 1000; p1 %= 1000; break;
121 case 3: d = p1 / 100; p1 %= 100; break;
122 case 2: d = p1 / 10; p1 %= 10; break;
123 case 1: d = p1; p1 = 0; break;
124 default:
125 /* Never go here. */
126 return 0;
127 }
128
129 if (d != 0 || p != begin) {
130 *p = '0' + d;
131
132 p += 1;
133 if (p == end) {
134 return p - begin;
135 }
136 }
137
138 kappa--;
139
140 tmp = ((uint64_t) p1 << -one.exp) + p2;
141
142 if (tmp <= delta) {
143 *dec_exp += kappa;
144 lexbor_grisu2_round(begin, p - begin, delta, tmp,
145 pow10[kappa] << -one.exp, wp_w.significand);
146 return p - begin;
147 }
148 }
149
150 /* kappa = 0. */
151
152 for ( ;; ) {
153 p2 *= 10;
154 delta *= 10;
155 c = (char) (p2 >> -one.exp);
156
157 if (c != 0 || p != begin) {
158 *p = '0' + c;
159
160 p += 1;
161 if (p == end) {
162 return p - begin;
163 }
164 }
165
166 p2 &= one.significand - 1;
167 kappa--;
168
169 if (p2 < delta) {
170 *dec_exp += kappa;
171 tmp = (-kappa < 10) ? pow10[-kappa] : 0;
172 lexbor_grisu2_round(begin, p - begin, delta, p2, one.significand,
173 wp_w.significand * tmp);
174 break;
175 }
176 }
177
178 return p - begin;
179 }
180
181 lxb_inline lexbor_diyfp_t
lexbor_diyfp_normalize_boundary(lexbor_diyfp_t v)182 lexbor_diyfp_normalize_boundary(lexbor_diyfp_t v)
183 {
184 while ((v.significand & (LEXBOR_DBL_HIDDEN_BIT << 1)) == 0) {
185 v.significand <<= 1;
186 v.exp--;
187 }
188
189 return lexbor_diyfp_shift_left(v, LEXBOR_SIGNIFICAND_SHIFT - 2);
190 }
191
192 lxb_inline void
lexbor_diyfp_normalize_boundaries(lexbor_diyfp_t v,lexbor_diyfp_t * minus,lexbor_diyfp_t * plus)193 lexbor_diyfp_normalize_boundaries(lexbor_diyfp_t v, lexbor_diyfp_t* minus,
194 lexbor_diyfp_t* plus)
195 {
196 lexbor_diyfp_t pl, mi;
197
198 pl = lexbor_diyfp_normalize_boundary(lexbor_diyfp((v.significand << 1) + 1,
199 v.exp - 1));
200
201 if (v.significand == LEXBOR_DBL_HIDDEN_BIT) {
202 mi = lexbor_diyfp((v.significand << 2) - 1, v.exp - 2);
203
204 } else {
205 mi = lexbor_diyfp((v.significand << 1) - 1, v.exp - 1);
206 }
207
208 mi.significand <<= mi.exp - pl.exp;
209 mi.exp = pl.exp;
210
211 *plus = pl;
212 *minus = mi;
213 }
214
215 lxb_inline size_t
lexbor_grisu2(double value,lxb_char_t * begin,lxb_char_t * end,int * dec_exp)216 lexbor_grisu2(double value, lxb_char_t *begin, lxb_char_t *end, int *dec_exp)
217 {
218 lexbor_diyfp_t v, w_m, w_p, c_mk, W, Wp, Wm;
219
220 v = lexbor_diyfp_from_d2(value);
221
222 lexbor_diyfp_normalize_boundaries(v, &w_m, &w_p);
223
224 c_mk = lexbor_cached_power_bin(w_p.exp, dec_exp);
225 W = lexbor_diyfp_mul(lexbor_diyfp_normalize(v), c_mk);
226
227 Wp = lexbor_diyfp_mul(w_p, c_mk);
228 Wm = lexbor_diyfp_mul(w_m, c_mk);
229
230 Wm.significand++;
231 Wp.significand--;
232
233 return lexbor_grisu2_gen(W, Wp, Wp.significand - Wm.significand, begin, end,
234 dec_exp);
235 }
236
237 lxb_inline size_t
lexbor_write_exponent(int exp,lxb_char_t * begin,lxb_char_t * end)238 lexbor_write_exponent(int exp, lxb_char_t *begin, lxb_char_t *end)
239 {
240 char *p;
241 size_t len;
242 uint32_t u32;
243 char buf[4];
244
245 /* -324 <= exp <= 308. */
246
247 if ((begin + (sizeof(buf) - 1) + 1) >= end) {
248 return 0;
249 }
250
251 if (exp < 0) {
252 *begin = '-';
253 begin += 1;
254
255 exp = -exp;
256 }
257 else {
258 *begin++ = '+';
259 }
260
261 u32 = exp;
262 p = buf + (sizeof(buf) - 1);
263
264 do {
265 *--p = u32 % 10 + '0';
266 u32 /= 10;
267 }
268 while (u32 != 0);
269
270 len = buf + (sizeof(buf) - 1) - p;
271
272 memcpy(begin, p, len);
273
274 return len + 1;
275 }
276
277 lxb_inline size_t
lexbor_prettify(lxb_char_t * begin,lxb_char_t * end,size_t len,int dec_exp)278 lexbor_prettify(lxb_char_t *begin, lxb_char_t *end, size_t len, int dec_exp)
279 {
280 int kk, offset, length;
281 size_t size;
282
283 /* 10^(kk-1) <= v < 10^kk */
284
285 length = (int) len;
286 kk = length + dec_exp;
287
288 if (length <= kk && kk <= 21) {
289 /* 1234e7 -> 12340000000 */
290
291 if (kk - length > 0) {
292 if ((&begin[length] + (kk - length)) < end) {
293 memset(&begin[length], '0', kk - length);
294 }
295 else {
296 memset(&begin[length], '0', (end - &begin[length]));
297 }
298 }
299
300 return kk;
301 }
302 else if (0 < kk && kk <= 21) {
303 /* 1234e-2 -> 12.34 */
304
305 if ((&begin[kk + 1] + (length - kk)) >= end) {
306 return length;
307 }
308
309 memmove(&begin[kk + 1], &begin[kk], length - kk);
310 begin[kk] = '.';
311
312 return (length + 1);
313 }
314 else if (-6 < kk && kk <= 0) {
315 /* 1234e-6 -> 0.001234 */
316
317 offset = 2 - kk;
318 if ((&begin[offset] + length) >= end
319 || (begin + 2) >= end)
320 {
321 return length;
322 }
323
324 memmove(&begin[offset], begin, length);
325 begin[0] = '0';
326 begin[1] = '.';
327
328 if (offset - 2 > 0) {
329 if ((&begin[2] + (offset - 2)) >= end) {
330 return length;
331 }
332
333 memset(&begin[2], '0', offset - 2);
334 }
335
336 return (length + offset);
337 }
338 else if (length == 1) {
339 /* 1e30 */
340
341 if ((begin + 1) >= end) {
342 return length;
343 }
344
345 begin[1] = 'e';
346
347 size = lexbor_write_exponent(kk - 1, &begin[2], end);
348
349 return (size + 2);
350 }
351
352 /* 1234e30 -> 1.234e33 */
353
354 if ((&begin[2] + (length - 1)) >= end) {
355 return length;
356 }
357
358 memmove(&begin[2], &begin[1], length - 1);
359 begin[1] = '.';
360 begin[length + 1] = 'e';
361
362 size = lexbor_write_exponent(kk - 1, &begin[length + 2], end);
363
364 return (size + length + 2);
365 }
366
367 size_t
lexbor_dtoa(double value,lxb_char_t * begin,size_t len)368 lexbor_dtoa(double value, lxb_char_t *begin, size_t len)
369 {
370 int dec_exp, minus;
371 size_t length;
372 lxb_char_t *end = begin + len;
373
374 if (len == 0) {
375 return 0;
376 }
377
378 /* Not handling NaN and inf. */
379
380 minus = 0;
381
382 if (value == 0) {
383 *begin = '0';
384
385 return 1;
386 }
387
388 if (signbit(value)) {
389 *begin = '-';
390
391 begin += 1;
392 if (begin == end) {
393 return 1;
394 }
395
396 value = -value;
397 minus = 1;
398 }
399
400 length = lexbor_grisu2(value, begin, end, &dec_exp);
401 length = lexbor_prettify(begin, end, length, dec_exp);
402
403 return (minus + length);
404 }
405
