/src/njs/src/njs_strtod.c
Line | Count | Source |
1 | | /* |
2 | | * An internal strtod() implementation based upon V8 src/strtod.cc |
3 | | * without bignum support. |
4 | | * |
5 | | * Copyright 2012 the V8 project authors. All rights reserved. |
6 | | * Use of this source code is governed by a BSD-style license |
7 | | * that can be found in the LICENSE file. |
8 | | */ |
9 | | |
10 | | #include <njs_main.h> |
11 | | #include <njs_diyfp.h> |
12 | | |
13 | | /* |
14 | | * Max double: 1.7976931348623157 x 10^308 |
15 | | * Min non-zero double: 4.9406564584124654 x 10^-324 |
16 | | * Any x >= 10^309 is interpreted as +infinity. |
17 | | * Any x <= 10^-324 is interpreted as 0. |
18 | | * Note that 2.5e-324 (despite being smaller than the min double) |
19 | | * will be read as non-zero (equal to the min non-zero double). |
20 | | */ |
21 | | |
22 | 3.24M | #define NJS_DECIMAL_POWER_MAX 309 |
23 | 3.24M | #define NJS_DECIMAL_POWER_MIN (-324) |
24 | | |
25 | 7.47M | #define NJS_UINT64_MAX njs_uint64(0xFFFFFFFF, 0xFFFFFFFF) |
26 | 3.24M | #define NJS_UINT64_DECIMAL_DIGITS_MAX 19 |
27 | | |
28 | | |
29 | | /* |
30 | | * Reads digits from the buffer and converts them to a uint64. |
31 | | * Reads in as many digits as fit into a uint64. |
32 | | * When the string starts with "1844674407370955161" no further digit is read. |
33 | | * Since 2^64 = 18446744073709551616 it would still be possible read another |
34 | | * digit if it was less or equal than 6, but this would complicate the code. |
35 | | */ |
36 | | njs_inline uint64_t |
37 | | njs_read_uint64(const u_char *start, size_t length, size_t *ndigits) |
38 | 3.24M | { |
39 | 3.24M | u_char d; |
40 | 3.24M | uint64_t value; |
41 | 3.24M | const u_char *p, *e; |
42 | | |
43 | 3.24M | value = 0; |
44 | | |
45 | 3.24M | p = start; |
46 | 3.24M | e = p + length; |
47 | | |
48 | 10.7M | while (p < e && value <= (NJS_UINT64_MAX / 10 - 1)) { |
49 | 7.47M | d = *p++ - '0'; |
50 | 7.47M | value = 10 * value + d; |
51 | 7.47M | } |
52 | | |
53 | 3.24M | *ndigits = p - start; |
54 | | |
55 | 3.24M | return value; |
56 | 3.24M | } |
57 | | |
58 | | |
59 | | /* |
60 | | * Reads a njs_diyfp_t from the buffer. |
61 | | * The returned njs_diyfp_t is not necessarily normalized. |
62 | | * If remaining is zero then the returned njs_diyfp_t is accurate. |
63 | | * Otherwise it has been rounded and has error of at most 1/2 ulp. |
64 | | */ |
65 | | static njs_diyfp_t |
66 | | njs_diyfp_read(const u_char *start, size_t length, int *remaining) |
67 | 3.24M | { |
68 | 3.24M | size_t read; |
69 | 3.24M | uint64_t significand; |
70 | | |
71 | 3.24M | significand = njs_read_uint64(start, length, &read); |
72 | | |
73 | | /* Round the significand. */ |
74 | | |
75 | 3.24M | if (length != read) { |
76 | 1.43k | if (start[read] >= '5') { |
77 | 908 | significand++; |
78 | 908 | } |
79 | 1.43k | } |
80 | | |
81 | 3.24M | *remaining = length - read; |
82 | | |
83 | 3.24M | return njs_diyfp(significand, 0); |
84 | 3.24M | } |
85 | | |
86 | | |
87 | | /* |
88 | | * Returns 10^exp as an exact njs_diyfp_t. |
89 | | * The given exp must be in the range [1; NJS_DECIMAL_EXPONENT_DIST[. |
90 | | */ |
91 | | njs_inline njs_diyfp_t |
92 | | njs_adjust_pow10(int exp) |
93 | 3.24M | { |
94 | 3.24M | switch (exp) { |
95 | 1.39k | case 1: |
96 | 1.39k | return njs_diyfp(njs_uint64(0xa0000000, 00000000), -60); |
97 | 3.65k | case 2: |
98 | 3.65k | return njs_diyfp(njs_uint64(0xc8000000, 00000000), -57); |
99 | 1.55k | case 3: |
100 | 1.55k | return njs_diyfp(njs_uint64(0xfa000000, 00000000), -54); |
101 | 3.00M | case 4: |
102 | 3.00M | return njs_diyfp(njs_uint64(0x9c400000, 00000000), -50); |
103 | 214k | case 5: |
104 | 214k | return njs_diyfp(njs_uint64(0xc3500000, 00000000), -47); |
105 | 18.0k | case 6: |
106 | 18.0k | return njs_diyfp(njs_uint64(0xf4240000, 00000000), -44); |
107 | 985 | case 7: |
108 | 985 | return njs_diyfp(njs_uint64(0x98968000, 00000000), -40); |
109 | 0 | default: |
110 | 0 | njs_unreachable(); |
111 | 0 | return njs_diyfp(0, 0); |
112 | 3.24M | } |
113 | 3.24M | } |
114 | | |
115 | | |
116 | | /* |
117 | | * Returns the significand size for a given order of magnitude. |
118 | | * If v = f*2^e with 2^p-1 <= f <= 2^p then p+e is v's order of magnitude. |
119 | | * This function returns the number of significant binary digits v will have |
120 | | * once its encoded into a double. In almost all cases this is equal to |
121 | | * NJS_SIGNIFICAND_SIZE. The only exception are denormals. They start with |
122 | | * leading zeroes and their effective significand-size is hence smaller. |
123 | | */ |
124 | | njs_inline int |
125 | | njs_diyfp_sgnd_size(int order) |
126 | 3.24M | { |
127 | 3.24M | if (order >= (NJS_DBL_EXPONENT_DENORMAL + NJS_SIGNIFICAND_SIZE)) { |
128 | 3.24M | return NJS_SIGNIFICAND_SIZE; |
129 | 3.24M | } |
130 | | |
131 | 1 | if (order <= NJS_DBL_EXPONENT_DENORMAL) { |
132 | 1 | return 0; |
133 | 1 | } |
134 | | |
135 | 0 | return order - NJS_DBL_EXPONENT_DENORMAL; |
136 | 1 | } |
137 | | |
138 | | |
139 | 13.0M | #define NJS_DENOM_LOG 3 |
140 | 9.75M | #define NJS_DENOM (1 << NJS_DENOM_LOG) |
141 | | |
142 | | /* |
143 | | * Returns either the correct double or the double that is just below |
144 | | * the correct double. |
145 | | */ |
146 | | static double |
147 | | njs_diyfp_strtod(const u_char *start, size_t length, int exp) |
148 | 3.24M | { |
149 | 3.24M | int magnitude, prec_digits; |
150 | 3.24M | int remaining, dec_exp, adj_exp, orig_e, shift; |
151 | 3.24M | int64_t error; |
152 | 3.24M | uint64_t prec_bits, half_way; |
153 | 3.24M | njs_diyfp_t value, pow, adj_pow, rounded; |
154 | | |
155 | 3.24M | value = njs_diyfp_read(start, length, &remaining); |
156 | | |
157 | 3.24M | exp += remaining; |
158 | | |
159 | | /* |
160 | | * Since some digits may have been dropped the value is not accurate. |
161 | | * If remaining is different than 0 than the error is at most .5 ulp |
162 | | * (unit in the last place). |
163 | | * Using a common denominator to avoid dealing with fractions. |
164 | | */ |
165 | | |
166 | 3.24M | error = (remaining == 0 ? 0 : NJS_DENOM / 2); |
167 | | |
168 | 3.24M | orig_e = value.exp; |
169 | 3.24M | value = njs_diyfp_normalize(value); |
170 | 3.24M | error <<= orig_e - value.exp; |
171 | | |
172 | 3.24M | if (exp < NJS_DECIMAL_EXPONENT_MIN) { |
173 | 0 | return 0.0; |
174 | 0 | } |
175 | | |
176 | 3.24M | pow = njs_cached_power_dec(exp, &dec_exp); |
177 | | |
178 | 3.24M | if (dec_exp != exp) { |
179 | | |
180 | 3.24M | adj_exp = exp - dec_exp; |
181 | 3.24M | adj_pow = njs_adjust_pow10(exp - dec_exp); |
182 | 3.24M | value = njs_diyfp_mul(value, adj_pow); |
183 | | |
184 | 3.24M | if (NJS_UINT64_DECIMAL_DIGITS_MAX - (int) length < adj_exp) { |
185 | | /* |
186 | | * The adjustment power is exact. There is hence only |
187 | | * an error of 0.5. |
188 | | */ |
189 | 11.2k | error += NJS_DENOM / 2; |
190 | 11.2k | } |
191 | 3.24M | } |
192 | | |
193 | 3.24M | value = njs_diyfp_mul(value, pow); |
194 | | |
195 | | /* |
196 | | * The error introduced by a multiplication of a * b equals |
197 | | * error_a + error_b + error_a * error_b / 2^64 + 0.5 |
198 | | * Substituting a with 'value' and b with 'pow': |
199 | | * error_b = 0.5 (all cached powers have an error of less than 0.5 ulp), |
200 | | * error_ab = 0 or 1 / NJS_DENOM > error_a * error_b / 2^64. |
201 | | */ |
202 | | |
203 | 3.24M | error += NJS_DENOM + (error != 0 ? 1 : 0); |
204 | | |
205 | 3.24M | orig_e = value.exp; |
206 | 3.24M | value = njs_diyfp_normalize(value); |
207 | 3.24M | error <<= orig_e - value.exp; |
208 | | |
209 | | /* |
210 | | * Check whether the double's significand changes when the error is added |
211 | | * or substracted. |
212 | | */ |
213 | | |
214 | 3.24M | magnitude = NJS_DIYFP_SIGNIFICAND_SIZE + value.exp; |
215 | 3.24M | prec_digits = NJS_DIYFP_SIGNIFICAND_SIZE - njs_diyfp_sgnd_size(magnitude); |
216 | | |
217 | 3.24M | if (prec_digits + NJS_DENOM_LOG >= NJS_DIYFP_SIGNIFICAND_SIZE) { |
218 | | /* |
219 | | * This can only happen for very small denormals. In this case the |
220 | | * half-way multiplied by the denominator exceeds the range of uint64. |
221 | | * Simply shift everything to the right. |
222 | | */ |
223 | 1 | shift = prec_digits + NJS_DENOM_LOG - NJS_DIYFP_SIGNIFICAND_SIZE + 1; |
224 | | |
225 | 1 | value = njs_diyfp_shift_right(value, shift); |
226 | | |
227 | | /* |
228 | | * Add 1 for the lost precision of error, and NJS_DENOM |
229 | | * for the lost precision of value.significand. |
230 | | */ |
231 | 1 | error = (error >> shift) + 1 + NJS_DENOM; |
232 | 1 | prec_digits -= shift; |
233 | 1 | } |
234 | | |
235 | 3.24M | prec_bits = value.significand & (((uint64_t) 1 << prec_digits) - 1); |
236 | 3.24M | prec_bits *= NJS_DENOM; |
237 | | |
238 | 3.24M | half_way = (uint64_t) 1 << (prec_digits - 1); |
239 | 3.24M | half_way *= NJS_DENOM; |
240 | | |
241 | 3.24M | rounded = njs_diyfp_shift_right(value, prec_digits); |
242 | | |
243 | 3.24M | if (prec_bits >= half_way + error) { |
244 | 8.44k | rounded.significand++; |
245 | 8.44k | } |
246 | | |
247 | 3.24M | return njs_diyfp2d(rounded); |
248 | 3.24M | } |
249 | | |
250 | | |
251 | | static double |
252 | | njs_strtod_internal(const u_char *start, size_t length, int exp) |
253 | 3.40M | { |
254 | 3.40M | int shift; |
255 | 3.40M | size_t left, right; |
256 | 3.40M | const u_char *p, *e, *b; |
257 | | |
258 | | /* Trim leading zeroes. */ |
259 | | |
260 | 3.40M | p = start; |
261 | 3.40M | e = p + length; |
262 | | |
263 | 3.58M | while (p < e) { |
264 | 3.43M | if (*p != '0') { |
265 | 3.24M | start = p; |
266 | 3.24M | break; |
267 | 3.24M | } |
268 | | |
269 | 182k | p++; |
270 | 182k | } |
271 | | |
272 | 3.40M | left = e - p; |
273 | | |
274 | | /* Trim trailing zeroes. */ |
275 | | |
276 | 3.40M | b = start; |
277 | 3.40M | p = b + left - 1; |
278 | | |
279 | 3.65M | while (p > b) { |
280 | 1.90M | if (*p != '0') { |
281 | 1.65M | break; |
282 | 1.65M | } |
283 | | |
284 | 251k | p--; |
285 | 251k | } |
286 | | |
287 | 3.40M | right = p - b + 1; |
288 | | |
289 | 3.40M | length = right; |
290 | | |
291 | 3.40M | if (length == 0) { |
292 | 151k | return 0.0; |
293 | 151k | } |
294 | | |
295 | 3.24M | shift = (int) (left - right); |
296 | | |
297 | 3.24M | if (exp >= NJS_DECIMAL_POWER_MAX - shift - (int) length + 1) { |
298 | 5 | return INFINITY; |
299 | 5 | } |
300 | | |
301 | 3.24M | if (exp <= NJS_DECIMAL_POWER_MIN - shift - (int) length) { |
302 | 0 | return 0.0; |
303 | 0 | } |
304 | | |
305 | 3.24M | return njs_diyfp_strtod(start, length, exp + shift); |
306 | 3.24M | } |
307 | | |
308 | | |
309 | | double |
310 | | njs_strtod(const u_char **start, const u_char *end, njs_bool_t literal) |
311 | 4.25M | { |
312 | 4.25M | int exponent, exp, insignf; |
313 | 4.25M | u_char c, *pos; |
314 | 4.25M | njs_bool_t minus; |
315 | 4.25M | const u_char *e, *p, *last, *_; |
316 | 4.25M | u_char data[128]; |
317 | | |
318 | 4.25M | exponent = 0; |
319 | 4.25M | insignf = 0; |
320 | | |
321 | 4.25M | pos = data; |
322 | 4.25M | last = data + sizeof(data); |
323 | | |
324 | 4.25M | p = *start; |
325 | 4.25M | _ = p - 2; |
326 | | |
327 | 12.0M | for (; p < end; p++) { |
328 | | /* Values less than '0' become >= 208. */ |
329 | 9.96M | c = *p - '0'; |
330 | | |
331 | 9.96M | if (njs_slow_path(c > 9)) { |
332 | 2.18M | if (literal) { |
333 | 1.67M | if ((p - _) == 1) { |
334 | 0 | goto done; |
335 | 0 | } |
336 | | |
337 | 1.67M | if (*p == '_') { |
338 | 0 | _ = p; |
339 | 0 | continue; |
340 | 0 | } |
341 | 1.67M | } |
342 | | |
343 | 2.18M | break; |
344 | 2.18M | } |
345 | | |
346 | 7.77M | if (pos < last) { |
347 | 7.77M | *pos++ = *p; |
348 | | |
349 | 7.77M | } else { |
350 | 1.11k | insignf++; |
351 | 1.11k | } |
352 | 7.77M | } |
353 | | |
354 | | /* Do not emit a '.', but adjust the exponent instead. */ |
355 | 4.25M | if (p < end && *p == '.') { |
356 | 16.8k | _ = p; |
357 | | |
358 | 162k | for (p++; p < end; p++) { |
359 | | /* Values less than '0' become >= 208. */ |
360 | 155k | c = *p - '0'; |
361 | | |
362 | 155k | if (njs_slow_path(c > 9)) { |
363 | 9.50k | if (literal && *p == '_' && (p - _) > 1) { |
364 | 0 | _ = p; |
365 | 0 | continue; |
366 | 0 | } |
367 | | |
368 | 9.50k | break; |
369 | 9.50k | } |
370 | | |
371 | 145k | if (pos < last) { |
372 | 145k | *pos++ = *p; |
373 | 145k | exponent--; |
374 | | |
375 | 145k | } else { |
376 | | /* Ignore insignificant digits in the fractional part. */ |
377 | 0 | } |
378 | 145k | } |
379 | 16.8k | } |
380 | | |
381 | 4.25M | if (pos == data) { |
382 | 854k | return NAN; |
383 | 854k | } |
384 | | |
385 | 3.40M | e = p + 1; |
386 | | |
387 | 3.40M | if (e < end && (*p == 'e' || *p == 'E')) { |
388 | 4.47k | minus = 0; |
389 | | |
390 | 4.47k | if (e + 1 < end) { |
391 | 4.47k | if (*e == '-') { |
392 | 1.06k | e++; |
393 | 1.06k | minus = 1; |
394 | | |
395 | 3.41k | } else if (*e == '+') { |
396 | 1.82k | e++; |
397 | 1.82k | } |
398 | 4.47k | } |
399 | | |
400 | | /* Values less than '0' become >= 208. */ |
401 | 4.47k | c = *e - '0'; |
402 | | |
403 | 4.47k | if (njs_fast_path(c <= 9)) { |
404 | 4.47k | exp = c; |
405 | | |
406 | 7.86k | for (p = e + 1; p < end; p++) { |
407 | | /* Values less than '0' become >= 208. */ |
408 | 4.54k | c = *p - '0'; |
409 | | |
410 | 4.54k | if (njs_slow_path(c > 9)) { |
411 | 1.14k | if (literal && *p == '_' && (p - _) > 1) { |
412 | 0 | _ = p; |
413 | 0 | continue; |
414 | 0 | } |
415 | | |
416 | 1.14k | break; |
417 | 1.14k | } |
418 | | |
419 | 3.39k | if (exp < (INT_MAX - 9) / 10) { |
420 | 3.39k | exp = exp * 10 + c; |
421 | 3.39k | } |
422 | 3.39k | } |
423 | | |
424 | 4.47k | exponent += minus ? -exp : exp; |
425 | | |
426 | 4.47k | } else if (literal && *e == '_') { |
427 | 0 | p = e; |
428 | 0 | } |
429 | 4.47k | } |
430 | | |
431 | 3.40M | done: |
432 | | |
433 | 3.40M | *start = p; |
434 | | |
435 | 3.40M | exponent += insignf; |
436 | | |
437 | 3.40M | return njs_strtod_internal(data, pos - data, exponent); |
438 | 3.40M | } |