Coverage Report

Created: 2025-10-13 07:13

next uncovered line (L), next uncovered region (R), next uncovered branch (B)
/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
}