internals: add correctly implemented dtoa routine #28
Assignees
Labels
Comments
This was referenced Jul 2, 2018
drsm
changed the title
|
this one looks very nice |
|
Code is based upon https://github.com/miloyip/dtoa-benchmark/tree/master/src/emyg and https://github.com/v8/v8/blob/master/src/strtod.cc. Please, note that the realization is not 100% accurate in comparison to V8 (Bignumbers are omited). It works well for typical values, but can differ a bit in the most pathological numbers. I think it is OK, because NJS is not for complex mathematical computations. Here is the draft version of the patch: # HG changeset patch
# User Dmitry Volyntsev <xeioex@nginx.com>
# Date 1530815219 -10800
# Thu Jul 05 21:26:59 2018 +0300
# Node ID 30fa4787ef1b375607a9c40e2aeb7cb89b074bb0
# Parent c1f9fe4022bc2e33b9491d528346090dfd1f481f
Fixed Number.toString().
The patch adds correct dtoa() and strtod() realization.
This fixes #28 issue on GitHub.
diff --git a/Makefile b/Makefile
--- a/Makefile
+++ b/Makefile
@@ -34,6 +34,9 @@ NXT_BUILDDIR = build
$(NXT_BUILDDIR)/njs_parser_expression.o \
$(NXT_BUILDDIR)/njs_generator.o \
$(NXT_BUILDDIR)/njs_disassembler.o \
+ $(NXT_BUILDDIR)/nxt_diyfp.o \
+ $(NXT_BUILDDIR)/nxt_dtoa.o \
+ $(NXT_BUILDDIR)/nxt_strtod.o \
$(NXT_BUILDDIR)/nxt_djb_hash.o \
$(NXT_BUILDDIR)/nxt_utf8.o \
$(NXT_BUILDDIR)/nxt_array.o \
@@ -76,6 +79,9 @@ NXT_BUILDDIR = build
$(NXT_BUILDDIR)/njs_parser_expression.o \
$(NXT_BUILDDIR)/njs_generator.o \
$(NXT_BUILDDIR)/njs_disassembler.o \
+ $(NXT_BUILDDIR)/nxt_diyfp.o \
+ $(NXT_BUILDDIR)/nxt_dtoa.o \
+ $(NXT_BUILDDIR)/nxt_strtod.o \
$(NXT_BUILDDIR)/nxt_djb_hash.o \
$(NXT_BUILDDIR)/nxt_utf8.o \
$(NXT_BUILDDIR)/nxt_array.o \
diff --git a/njs/njs_core.h b/njs/njs_core.h
--- a/njs/njs_core.h
+++ b/njs/njs_core.h
@@ -15,6 +15,8 @@
#include <nxt_string.h>
#include <nxt_stub.h>
#include <nxt_utf8.h>
+#include <nxt_dtoa.h>
+#include <nxt_strtod.h>
#include <nxt_djb_hash.h>
#include <nxt_trace.h>
#include <nxt_array.h>
diff --git a/njs/njs_json.c b/njs/njs_json.c
--- a/njs/njs_json.c
+++ b/njs/njs_json.c
@@ -1844,7 +1844,7 @@ njs_json_append_number(njs_json_stringif
return NXT_ERROR;
}
- size = njs_num_to_buf(num, p, 64);
+ size = nxt_dtoa(num, (char *) p);
njs_json_buf_written(stringify, size);
}
diff --git a/njs/njs_number.c b/njs/njs_number.c
--- a/njs/njs_number.c
+++ b/njs/njs_number.c
@@ -66,91 +66,7 @@ njs_value_to_index(const njs_value_t *va
double
njs_number_dec_parse(const u_char **start, const u_char *end)
{
- u_char c;
- double num, frac, scale, exponent;
- nxt_bool_t minus;
- const u_char *e, *p;
-
- p = *start;
-
- num = 0;
-
- while (p < end) {
- /* Values less than '0' become >= 208. */
- c = *p - '0';
-
- if (nxt_slow_path(c > 9)) {
- break;
- }
-
- num = num * 10 + c;
- p++;
- }
-
- if (p < end && *p == '.') {
-
- frac = 0;
- scale = 1;
-
- for (p++; p < end; p++) {
- /* Values less than '0' become >= 208. */
- c = *p - '0';
-
- if (nxt_slow_path(c > 9)) {
- break;
- }
-
- frac = frac * 10 + c;
- scale *= 10;
- }
-
- num += frac / scale;
- }
-
- e = p + 1;
-
- if (e < end && (*p == 'e' || *p == 'E')) {
- minus = 0;
-
- if (e + 1 < end) {
- if (*e == '-') {
- e++;
- minus = 1;
-
- } else if (*e == '+') {
- e++;
- }
- }
-
- /* Values less than '0' become >= 208. */
- c = *e - '0';
-
- if (nxt_fast_path(c <= 9)) {
- exponent = c;
- p = e + 1;
-
- while (p < end) {
- /* Values less than '0' become >= 208. */
- c = *p - '0';
-
- if (nxt_slow_path(c > 9)) {
- break;
- }
-
- exponent = exponent * 10 + c;
- p++;
- }
-
- if (num != 0) {
- exponent = minus ? -exponent : exponent;
- num = num * pow(10.0, exponent);
- }
- }
- }
-
- *start = p;
-
- return num;
+ return nxt_strtod(start, end);
}
@@ -303,10 +219,10 @@ njs_ret_t
njs_number_to_string(njs_vm_t *vm, njs_value_t *string,
const njs_value_t *number)
{
+ u_char buf[128];
double num;
size_t size;
const njs_value_t *value;
- u_char buf[128];
num = number->data.u.number;
@@ -323,7 +239,7 @@ njs_number_to_string(njs_vm_t *vm, njs_v
}
} else {
- size = njs_num_to_buf(num, buf, sizeof(buf));
+ size = nxt_dtoa(num, (char *) buf);
return njs_string_new(vm, string, buf, size, size);
}
diff --git a/njs/test/njs_unit_test.c b/njs/test/njs_unit_test.c
--- a/njs/test/njs_unit_test.c
+++ b/njs/test/njs_unit_test.c
@@ -96,16 +96,14 @@ static njs_unit_test_t njs_test[] =
{ nxt_string("999999999999999999999"),
nxt_string("1e+21") },
-#if 0
{ nxt_string("9223372036854775808"),
- nxt_string("9223372036854775808") },
+ nxt_string("9223372036854776000") },
{ nxt_string("18446744073709551616"),
- nxt_string("18446744073709552000") },
+ nxt_string("18446744073709553000") },
{ nxt_string("1.7976931348623157E+308"),
nxt_string("1.7976931348623157e+308") },
-#endif
{ nxt_string("+1"),
nxt_string("1") },
@@ -223,16 +221,16 @@ static njs_unit_test_t njs_test[] =
nxt_string("57") },
{ nxt_string("5.7e-1"),
- nxt_string("0.570000") },
+ nxt_string("0.57") },
{ nxt_string("-5.7e-1"),
- nxt_string("-0.570000") },
+ nxt_string("-0.57") },
{ nxt_string("1.1e-01"),
- nxt_string("0.110000") },
+ nxt_string("0.11") },
{ nxt_string("5.7e-2"),
- nxt_string("0.057000") },
+ nxt_string("0.057") },
{ nxt_string("1.1e+01"),
nxt_string("11") },
@@ -629,7 +627,7 @@ static njs_unit_test_t njs_test[] =
nxt_string("NaN") },
{ nxt_string("var a = 0.1; a **= -2"),
- nxt_string("100") },
+ nxt_string("99.99999999999999") },
{ nxt_string("var a = 1; a **= NaN"),
nxt_string("NaN") },
@@ -7467,7 +7465,7 @@ static njs_unit_test_t njs_test[] =
/* Math. */
{ nxt_string("Math.PI"),
- nxt_string("3.14159") },
+ nxt_string("3.141592653589793") },
{ nxt_string("Math.abs()"),
nxt_string("NaN") },
@@ -7726,7 +7724,7 @@ static njs_unit_test_t njs_test[] =
nxt_string("-Infinity") },
{ nxt_string("Math.cbrt('27')"),
- nxt_string("3") },
+ nxt_string("3.0000000000000006") },
{ nxt_string("Math.cbrt(-1)"),
nxt_string("-1") },
@@ -8507,10 +8505,10 @@ static njs_unit_test_t njs_test[] =
nxt_string("57") },
{ nxt_string("parseFloat('-5.7e-1')"),
- nxt_string("-0.570000") },
+ nxt_string("-0.57") },
{ nxt_string("parseFloat('-5.e-1')"),
- nxt_string("-0.500000") },
+ nxt_string("-0.5") },
{ nxt_string("parseFloat('5.7e+01')"),
nxt_string("57") },
@@ -8519,7 +8517,7 @@ static njs_unit_test_t njs_test[] =
nxt_string("57") },
{ nxt_string("parseFloat('-5.7e-1abc')"),
- nxt_string("-0.570000") },
+ nxt_string("-0.57") },
{ nxt_string("parseFloat('-5.7e')"),
nxt_string("-5.7") },
diff --git a/nxt/Makefile b/nxt/Makefile
--- a/nxt/Makefile
+++ b/nxt/Makefile
@@ -4,6 +4,9 @@ NXT_LIB = nxt
$(NXT_BUILDDIR)/libnxt.a: \
$(NXT_LIB)/nxt_auto_config.h \
+ $(NXT_BUILDDIR)/nxt_diyfp.o \
+ $(NXT_BUILDDIR)/nxt_dtoa.o \
+ $(NXT_BUILDDIR)/nxt_strtod.o \
$(NXT_BUILDDIR)/nxt_djb_hash.o \
$(NXT_BUILDDIR)/nxt_utf8.o \
$(NXT_BUILDDIR)/nxt_array.o \
@@ -20,6 +23,9 @@ NXT_LIB = nxt
$(NXT_BUILDDIR)/nxt_mem_cache_pool.o \
ar -r -c $(NXT_BUILDDIR)/libnxt.a \
+ $(NXT_BUILDDIR)/nxt_diyfp.o \
+ $(NXT_BUILDDIR)/nxt_dtoa.o \
+ $(NXT_BUILDDIR)/nxt_strtod.o \
$(NXT_BUILDDIR)/nxt_djb_hash.o \
$(NXT_BUILDDIR)/nxt_utf8.o \
$(NXT_BUILDDIR)/nxt_array.o \
@@ -34,6 +40,36 @@ NXT_LIB = nxt
$(NXT_BUILDDIR)/nxt_trace.o \
$(NXT_BUILDDIR)/nxt_mem_cache_pool.o \
+$(NXT_BUILDDIR)/nxt_diyfp.o: \
+ $(NXT_LIB)/nxt_types.h \
+ $(NXT_LIB)/nxt_clang.h \
+ $(NXT_LIB)/nxt_diyfp.h \
+ $(NXT_LIB)/nxt_diyfp.c \
+
+ $(NXT_CC) -c -o $(NXT_BUILDDIR)/nxt_diyfp.o $(NXT_CFLAGS) \
+ -I$(NXT_LIB) \
+ $(NXT_LIB)/nxt_diyfp.c
+
+$(NXT_BUILDDIR)/nxt_dtoa.o: \
+ $(NXT_LIB)/nxt_types.h \
+ $(NXT_LIB)/nxt_clang.h \
+ $(NXT_LIB)/nxt_dtoa.h \
+ $(NXT_LIB)/nxt_dtoa.c \
+
+ $(NXT_CC) -c -o $(NXT_BUILDDIR)/nxt_dtoa.o $(NXT_CFLAGS) \
+ -I$(NXT_LIB) \
+ $(NXT_LIB)/nxt_dtoa.c
+
+$(NXT_BUILDDIR)/nxt_strtod.o: \
+ $(NXT_LIB)/nxt_types.h \
+ $(NXT_LIB)/nxt_clang.h \
+ $(NXT_LIB)/nxt_strtod.h \
+ $(NXT_LIB)/nxt_strtod.c \
+
+ $(NXT_CC) -c -o $(NXT_BUILDDIR)/nxt_strtod.o $(NXT_CFLAGS) \
+ -I$(NXT_LIB) \
+ $(NXT_LIB)/nxt_strtod.c
+
$(NXT_BUILDDIR)/nxt_murmur_hash.o: \
$(NXT_LIB)/nxt_types.h \
$(NXT_LIB)/nxt_clang.h \
diff --git a/nxt/auto/clang b/nxt/auto/clang
--- a/nxt/auto/clang
+++ b/nxt/auto/clang
@@ -217,6 +217,20 @@ nxt_feature_test="int main(void) {
. ${NXT_AUTO}feature
+nxt_feature="GCC __builtin_clzll()"
+nxt_feature_name=NXT_HAVE_BUILTIN_CLZLL
+nxt_feature_run=no
+nxt_feature_incs=
+nxt_feature_libs=
+nxt_feature_test="int main(void) {
+ if (__builtin_clzll(1ULL) != 63) {
+ return 1;
+ }
+ return 0;
+ }"
+. ${NXT_AUTO}feature
+
+
nxt_feature="GCC __attribute__ visibility"
nxt_feature_name=NXT_HAVE_GCC_ATTRIBUTE_VISIBILITY
nxt_feature_run=no
diff --git a/nxt/nxt_diyfp.c b/nxt/nxt_diyfp.c
new file mode 100644
--- /dev/null
+++ b/nxt/nxt_diyfp.c
@@ -0,0 +1,153 @@
+
+/*
+ * An internal nxt_diyfp_t implementation based on V8 src/cached-powers.cc.
+ *
+ * Copyright 2011 the V8 project authors. All rights reserved.
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include <nxt_auto_config.h>
+#include <nxt_types.h>
+#include <nxt_clang.h>
+#include <nxt_diyfp.h>
+
+#include <assert.h>
+
+
+typedef struct nxt_cpe_s {
+ uint64_t significand;
+ int16_t bin_exp;
+ int16_t dec_exp;
+} nxt_cpe_t;
+
+
+static const nxt_cpe_t nxt_cached_powers[] = {
+ {UINT64_C2(0xfa8fd5a0, 0x081c0288), -1220, -348},
+ {UINT64_C2(0xbaaee17f, 0xa23ebf76), -1193, -340},
+ {UINT64_C2(0x8b16fb20, 0x3055ac76), -1166, -332},
+ {UINT64_C2(0xcf42894a, 0x5dce35ea), -1140, -324},
+ {UINT64_C2(0x9a6bb0aa, 0x55653b2d), -1113, -316},
+ {UINT64_C2(0xe61acf03, 0x3d1a45df), -1087, -308},
+ {UINT64_C2(0xab70fe17, 0xc79ac6ca), -1060, -300},
+ {UINT64_C2(0xff77b1fc, 0xbebcdc4f), -1034, -292},
+ {UINT64_C2(0xbe5691ef, 0x416bd60c), -1007, -284},
+ {UINT64_C2(0x8dd01fad, 0x907ffc3c), -980, -276},
+ {UINT64_C2(0xd3515c28, 0x31559a83), -954, -268},
+ {UINT64_C2(0x9d71ac8f, 0xada6c9b5), -927, -260},
+ {UINT64_C2(0xea9c2277, 0x23ee8bcb), -901, -252},
+ {UINT64_C2(0xaecc4991, 0x4078536d), -874, -244},
+ {UINT64_C2(0x823c1279, 0x5db6ce57), -847, -236},
+ {UINT64_C2(0xc2109436, 0x4dfb5637), -821, -228},
+ {UINT64_C2(0x9096ea6f, 0x3848984f), -794, -220},
+ {UINT64_C2(0xd77485cb, 0x25823ac7), -768, -212},
+ {UINT64_C2(0xa086cfcd, 0x97bf97f4), -741, -204},
+ {UINT64_C2(0xef340a98, 0x172aace5), -715, -196},
+ {UINT64_C2(0xb23867fb, 0x2a35b28e), -688, -188},
+ {UINT64_C2(0x84c8d4df, 0xd2c63f3b), -661, -180},
+ {UINT64_C2(0xc5dd4427, 0x1ad3cdba), -635, -172},
+ {UINT64_C2(0x936b9fce, 0xbb25c996), -608, -164},
+ {UINT64_C2(0xdbac6c24, 0x7d62a584), -582, -156},
+ {UINT64_C2(0xa3ab6658, 0x0d5fdaf6), -555, -148},
+ {UINT64_C2(0xf3e2f893, 0xdec3f126), -529, -140},
+ {UINT64_C2(0xb5b5ada8, 0xaaff80b8), -502, -132},
+ {UINT64_C2(0x87625f05, 0x6c7c4a8b), -475, -124},
+ {UINT64_C2(0xc9bcff60, 0x34c13053), -449, -116},
+ {UINT64_C2(0x964e858c, 0x91ba2655), -422, -108},
+ {UINT64_C2(0xdff97724, 0x70297ebd), -396, -100},
+ {UINT64_C2(0xa6dfbd9f, 0xb8e5b88f), -369, -92},
+ {UINT64_C2(0xf8a95fcf, 0x88747d94), -343, -84},
+ {UINT64_C2(0xb9447093, 0x8fa89bcf), -316, -76},
+ {UINT64_C2(0x8a08f0f8, 0xbf0f156b), -289, -68},
+ {UINT64_C2(0xcdb02555, 0x653131b6), -263, -60},
+ {UINT64_C2(0x993fe2c6, 0xd07b7fac), -236, -52},
+ {UINT64_C2(0xe45c10c4, 0x2a2b3b06), -210, -44},
+ {UINT64_C2(0xaa242499, 0x697392d3), -183, -36},
+ {UINT64_C2(0xfd87b5f2, 0x8300ca0e), -157, -28},
+ {UINT64_C2(0xbce50864, 0x92111aeb), -130, -20},
+ {UINT64_C2(0x8cbccc09, 0x6f5088cc), -103, -12},
+ {UINT64_C2(0xd1b71758, 0xe219652c), -77, -4},
+ {UINT64_C2(0x9c400000, 0x00000000), -50, 4},
+ {UINT64_C2(0xe8d4a510, 0x00000000), -24, 12},
+ {UINT64_C2(0xad78ebc5, 0xac620000), 3, 20},
+ {UINT64_C2(0x813f3978, 0xf8940984), 30, 28},
+ {UINT64_C2(0xc097ce7b, 0xc90715b3), 56, 36},
+ {UINT64_C2(0x8f7e32ce, 0x7bea5c70), 83, 44},
+ {UINT64_C2(0xd5d238a4, 0xabe98068), 109, 52},
+ {UINT64_C2(0x9f4f2726, 0x179a2245), 136, 60},
+ {UINT64_C2(0xed63a231, 0xd4c4fb27), 162, 68},
+ {UINT64_C2(0xb0de6538, 0x8cc8ada8), 189, 76},
+ {UINT64_C2(0x83c7088e, 0x1aab65db), 216, 84},
+ {UINT64_C2(0xc45d1df9, 0x42711d9a), 242, 92},
+ {UINT64_C2(0x924d692c, 0xa61be758), 269, 100},
+ {UINT64_C2(0xda01ee64, 0x1a708dea), 295, 108},
+ {UINT64_C2(0xa26da399, 0x9aef774a), 322, 116},
+ {UINT64_C2(0xf209787b, 0xb47d6b85), 348, 124},
+ {UINT64_C2(0xb454e4a1, 0x79dd1877), 375, 132},
+ {UINT64_C2(0x865b8692, 0x5b9bc5c2), 402, 140},
+ {UINT64_C2(0xc83553c5, 0xc8965d3d), 428, 148},
+ {UINT64_C2(0x952ab45c, 0xfa97a0b3), 455, 156},
+ {UINT64_C2(0xde469fbd, 0x99a05fe3), 481, 164},
+ {UINT64_C2(0xa59bc234, 0xdb398c25), 508, 172},
+ {UINT64_C2(0xf6c69a72, 0xa3989f5c), 534, 180},
+ {UINT64_C2(0xb7dcbf53, 0x54e9bece), 561, 188},
+ {UINT64_C2(0x88fcf317, 0xf22241e2), 588, 196},
+ {UINT64_C2(0xcc20ce9b, 0xd35c78a5), 614, 204},
+ {UINT64_C2(0x98165af3, 0x7b2153df), 641, 212},
+ {UINT64_C2(0xe2a0b5dc, 0x971f303a), 667, 220},
+ {UINT64_C2(0xa8d9d153, 0x5ce3b396), 694, 228},
+ {UINT64_C2(0xfb9b7cd9, 0xa4a7443c), 720, 236},
+ {UINT64_C2(0xbb764c4c, 0xa7a44410), 747, 244},
+ {UINT64_C2(0x8bab8eef, 0xb6409c1a), 774, 252},
+ {UINT64_C2(0xd01fef10, 0xa657842c), 800, 260},
+ {UINT64_C2(0x9b10a4e5, 0xe9913129), 827, 268},
+ {UINT64_C2(0xe7109bfb, 0xa19c0c9d), 853, 276},
+ {UINT64_C2(0xac2820d9, 0x623bf429), 880, 284},
+ {UINT64_C2(0x80444b5e, 0x7aa7cf85), 907, 292},
+ {UINT64_C2(0xbf21e440, 0x03acdd2d), 933, 300},
+ {UINT64_C2(0x8e679c2f, 0x5e44ff8f), 960, 308},
+ {UINT64_C2(0xd433179d, 0x9c8cb841), 986, 316},
+ {UINT64_C2(0x9e19db92, 0xb4e31ba9), 1013, 324},
+ {UINT64_C2(0xeb96bf6e, 0xbadf77d9), 1039, 332},
+ {UINT64_C2(0xaf87023b, 0x9bf0ee6b), 1066, 340},
+};
+
+
+nxt_diyfp_t
+nxt_cached_power_dec(int exp, int* K)
+{
+ assert(NXT_DECIMAL_EXPONENT_MIN <= exp);
+ assert(exp < NXT_DECIMAL_EXPONENT_MAX + NXT_DECIMAL_EXPONENT_DIST);
+
+ int index = (exp + NXT_DECIMAL_EXPONENT_OFF) / NXT_DECIMAL_EXPONENT_DIST;
+ nxt_cpe_t cp = nxt_cached_powers[index];
+
+ *K = cp.dec_exp;
+
+ assert(*K <= exp);
+ assert(exp < *K + NXT_DECIMAL_EXPONENT_DIST);
+
+ return nxt_diyfp(cp.significand, cp.bin_exp);
+}
+
+
+nxt_diyfp_t
+nxt_cached_power_bin(int exp, int* K)
+{
+ //int k = (int )(ceil((-61 - e) * 0.30102999566398114)) + 374;
+ //dk must be positive, so can do ceiling in positive
+ double dk = (-61 - exp) * 0.30102999566398114 + 347;
+ int k = (int) dk;
+ if (k != dk)
+ k++;
+
+ unsigned index = (unsigned )((k >> 3) + 1);
+
+ assert(index < sizeof(nxt_cached_powers) / sizeof(nxt_cached_powers[0]));
+
+ nxt_cpe_t cp = nxt_cached_powers[index];
+
+ *K = -(NXT_DECIMAL_EXPONENT_MIN + (int) (index << 3));
+
+ return nxt_diyfp(cp.significand, cp.bin_exp);
+}
diff --git a/nxt/nxt_diyfp.h b/nxt/nxt_diyfp.h
new file mode 100644
--- /dev/null
+++ b/nxt/nxt_diyfp.h
@@ -0,0 +1,246 @@
+
+/*
+ * Copyright (C) Dmitry Volyntsev
+ * Copyright (C) Nginx, Inc.
+ */
+
+#ifndef _NXT_DIYFP_H_INCLUDED_
+#define _NXT_DIYFP_H_INCLUDED_
+
+#include <nxt_types.h>
+#include <math.h>
+
+typedef struct {
+ uint64_t f;
+ int e;
+} nxt_diyfp_t;
+
+
+#define UINT64_C2(h, l) (((uint64_t) (h) << 32) | (uint64_t) (l))
+
+#define nxt_diyfp(_f, _e) (nxt_diyfp_t) {.f = (_f), .e = (_e)}
+
+#define NXT_DIYFP_SIGNIFICAND_SIZE 64
+#define NXT_DBL_SIGNIFICAND_SIZE 52
+#define NXT_DBL_EXPONENT_BIAS (0x3FF + NXT_DBL_SIGNIFICAND_SIZE)
+#define NXT_DBL_EXPONENT_MIN (-NXT_DBL_EXPONENT_BIAS)
+#define NXT_DBL_EXPONENT_MAX (0x7FF - NXT_DBL_EXPONENT_BIAS)
+
+#define NXT_DBL_SIGNIFICAND_MASK UINT64_C2(0x000FFFFF, 0xFFFFFFFF)
+
+#define kDpExponentMask UINT64_C2(0x7FF00000, 0x00000000)
+#define kDpSignificandMask UINT64_C2(0x000FFFFF, 0xFFFFFFFF)
+#define kDpHiddenBit UINT64_C2(0x00100000, 0x00000000)
+
+#define kSignificandSize 53
+#define kDenormalExponent (-NXT_DBL_EXPONENT_BIAS + 1)
+
+
+#define NXT_DECIMAL_EXPONENT_OFF 348
+#define NXT_DECIMAL_EXPONENT_MIN (-348)
+#define NXT_DECIMAL_EXPONENT_MAX 340
+#define NXT_DECIMAL_EXPONENT_DIST 8
+
+
+nxt_diyfp_t nxt_cached_power_dec(int exponent, int* K);
+nxt_diyfp_t nxt_cached_power_bin(int e, int* K);
+
+
+nxt_inline nxt_diyfp_t
+nxt_d2diyfp(double d)
+{
+ int biased_e;
+ uint64_t significand;
+ nxt_diyfp_t r;
+
+ union {
+ double d;
+ uint64_t u64;
+ } u = { d };
+
+ biased_e = (u.u64 & kDpExponentMask) >> NXT_DBL_SIGNIFICAND_SIZE;
+ significand = u.u64 & NXT_DBL_SIGNIFICAND_MASK;
+
+ if (biased_e != 0) {
+ r.f = significand + kDpHiddenBit;
+ r.e = biased_e - NXT_DBL_EXPONENT_BIAS;
+
+ } else {
+ r.f = significand;
+ r.e = NXT_DBL_EXPONENT_MIN + 1;
+ }
+
+ return r;
+}
+
+
+nxt_inline double
+nxt_diyfp2d(nxt_diyfp_t v)
+{
+ int exp;
+ uint64_t significand, biased_exp;
+
+ union {
+ double d;
+ uint64_t u64;
+ } u;
+
+ exp = v.e;
+ significand = v.f;
+
+ while (significand > kDpHiddenBit + NXT_DBL_SIGNIFICAND_MASK) {
+ significand >>= 1;
+ exp++;
+ }
+
+ if (exp >= NXT_DBL_EXPONENT_MAX) {
+ return INFINITY;
+ }
+
+ if (exp < kDenormalExponent) {
+ return 0.0;
+ }
+
+ while (exp > kDenormalExponent && (significand & kDpHiddenBit) == 0) {
+ significand <<= 1;
+ exp--;
+ }
+
+ if (exp == kDenormalExponent && (significand & kDpHiddenBit) == 0) {
+ biased_exp = 0;
+
+ } else {
+ biased_exp = (uint64_t) (exp + NXT_DBL_EXPONENT_BIAS);
+ }
+
+ u.u64 = (significand & NXT_DBL_SIGNIFICAND_MASK)
+ | (biased_exp << NXT_DBL_SIGNIFICAND_SIZE);
+
+ return u.d;
+}
+
+
+nxt_inline nxt_diyfp_t
+nxt_diyfp_subtract(nxt_diyfp_t lhs, nxt_diyfp_t rhs)
+{
+ return nxt_diyfp(lhs.f - rhs.f, lhs.e);
+}
+
+
+nxt_inline nxt_diyfp_t
+nxt_diyfp_multiply(nxt_diyfp_t lhs, nxt_diyfp_t rhs)
+{
+#if ((__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 6) \
+ || __clang_major__ >= 9) && defined(__x86_64__))
+
+ unsigned __int128 p = (unsigned __int128) (lhs.f)
+ * (unsigned __int128) (rhs.f);
+ uint64_t h = p >> 64;
+ uint64_t l = (uint64_t) p;
+
+ if (l & ((uint64_t) 1u << 63)) /* rounding */
+ h++;
+
+ return nxt_diyfp(h, lhs.e + rhs.e + 64);
+
+#else
+
+ const uint64_t M32 = 0xFFFFFFFF;
+ const uint64_t a = lhs.f >> 32;
+ const uint64_t b = lhs.f & M32;
+ const uint64_t c = rhs.f >> 32;
+ const uint64_t d = rhs.f & M32;
+ const uint64_t ac = a * c;
+ const uint64_t bc = b * c;
+ const uint64_t ad = a * d;
+ const uint64_t bd = b * d;
+
+ uint64_t tmp = (bd >> 32) + (ad & M32) + (bc & M32);
+
+ tmp += 1U << 31; /* mult_round */
+
+ return nxt_diyfp(ac + (ad >> 32) + (bc >> 32) + (tmp >> 32),
+ lhs.e + rhs.e + 64);
+
+#endif
+}
+
+
+nxt_inline nxt_diyfp_t
+nxt_diyfp_normalize(nxt_diyfp_t lhs)
+{
+#if defined(NXT_HAVE_BUILTIN_CLZLL)
+
+ int s = __builtin_clzll(lhs.f);
+ return nxt_diyfp(lhs.f << s, lhs.e - s);
+
+#else
+
+ nxt_diyfp_t res = lhs;
+ while (!(res.f & kDpHiddenBit)) {
+ res.f <<= 1;
+ res.e--;
+ }
+
+ res.f <<= (NXT_DIYFP_SIGNIFICAND_SIZE - NXT_DBL_SIGNIFICAND_SIZE - 1);
+ res.e = res.e - (NXT_DIYFP_SIGNIFICAND_SIZE - NXT_DBL_SIGNIFICAND_SIZE - 1);
+
+ return res;
+
+#endif
+}
+
+
+nxt_inline nxt_diyfp_t
+nxt_diyfp_normalize_boundary(nxt_diyfp_t lhs)
+{
+ nxt_diyfp_t res = lhs;
+ while (!(res.f & (kDpHiddenBit << 1))) {
+ res.f <<= 1;
+ res.e--;
+ }
+
+ res.f <<= (NXT_DIYFP_SIGNIFICAND_SIZE - NXT_DBL_SIGNIFICAND_SIZE - 2);
+ res.e = res.e - (NXT_DIYFP_SIGNIFICAND_SIZE - NXT_DBL_SIGNIFICAND_SIZE - 2);
+
+ return res;
+}
+
+
+nxt_inline void
+nxt_diyfp_normalize_boundaries(nxt_diyfp_t lhs, nxt_diyfp_t* minus,
+ nxt_diyfp_t* plus)
+{
+ nxt_diyfp_t pl = nxt_diyfp_normalize_boundary(nxt_diyfp((lhs.f << 1) + 1,
+ lhs.e - 1));
+ nxt_diyfp_t mi = (lhs.f == kDpHiddenBit)
+ ? nxt_diyfp((lhs.f << 2) - 1, lhs.e - 2)
+ : nxt_diyfp((lhs.f << 1) - 1, lhs.e - 1);
+
+ mi.f <<= mi.e - pl.e;
+ mi.e = pl.e;
+
+ *plus = pl;
+ *minus = mi;
+}
+
+// Returns the significand size for a given order of magnitude.
+// If v = f*2^e with 2^p-1 <= f <= 2^p then p+e is v's order of magnitude.
+// This function returns the number of significant binary digits v will have
+// once its encoded into a double. In almost all cases this is equal to
+// kSignificandSize. The only exception are denormals. They start with leading
+// zeroes and their effective significand-size is hence smaller.
+static inline int
+SignificandSizeForOrderOfMagnitude(int order) {
+ if (order >= (kDenormalExponent + kSignificandSize)) {
+ return kSignificandSize;
+ }
+
+ if (order <= kDenormalExponent) {
+ return 0;
+ }
+
+ return order - kDenormalExponent;
+}
+
+#endif /* _NXT_DIYFP_H_INCLUDED_ */
diff --git a/nxt/nxt_dtoa.c b/nxt/nxt_dtoa.c
new file mode 100644
--- /dev/null
+++ b/nxt/nxt_dtoa.c
@@ -0,0 +1,308 @@
+
+/*
+ * An internal dtoa() implementation based on the work of Milo Yip and Doug
+ * Currie.
+ *
+ * This code is a mostly mechanical translation of Milo Yip's C++ version of
+ * Grisu2 to C. For algorithm information, see Loitsch, Florian. "Printing
+ * floating-point numbers quickly and accurately with integers." ACM Sigplan
+ * Notices 45.6 (2010): 233-243.
+ *
+ * emyg_dtoa.c
+ * Copyright (C) 2015 Doug Currie
+ * based on dtoa_milo.h
+ * Copyright (C) 2014 Milo Yip
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ * THE SOFTWARE.
+ */
+
+#include <nxt_auto_config.h>
+#include <nxt_types.h>
+#include <nxt_clang.h>
+#include <nxt_diyfp.h>
+#include <nxt_dtoa.h>
+
+#include <math.h>
+#include <string.h>
+#include <stdio.h>
+#include <assert.h>
+#include <stdint.h>
+
+
+static inline void
+GrisuRound(char* buffer, int len, uint64_t delta, uint64_t rest,
+ uint64_t ten_kappa, uint64_t wp_w)
+{
+ while (rest < wp_w && delta - rest >= ten_kappa &&
+ (rest + ten_kappa < wp_w || /* closer */
+ wp_w - rest > rest + ten_kappa - wp_w))
+ {
+ buffer[len - 1]--;
+ rest += ten_kappa;
+ }
+}
+
+
+static inline unsigned
+CountDecimalDigit32(uint32_t n)
+{
+ if (n < 10) return 1;
+ if (n < 100) return 2;
+ if (n < 1000) return 3;
+ if (n < 10000) return 4;
+ if (n < 100000) return 5;
+ if (n < 1000000) return 6;
+ if (n < 10000000) return 7;
+ if (n < 100000000) return 8;
+ if (n < 1000000000) return 9;
+
+ return 10;
+}
+
+
+static inline void
+DigitGen(const nxt_diyfp_t W, const nxt_diyfp_t Mp, uint64_t delta, char* buffer, int* len,
+ int* K)
+{
+ const nxt_diyfp_t one = nxt_diyfp((uint64_t) (1) << -Mp.e, Mp.e);
+ const nxt_diyfp_t wp_w = nxt_diyfp_subtract(Mp, W);
+ uint32_t p1 = (uint32_t) (Mp.f >> -one.e);
+ uint64_t p2 = Mp.f & (one.f - 1);
+ int kappa = (int) (CountDecimalDigit32(p1));
+
+ static const uint32_t kPow10[] = { 1, 10, 100, 1000, 10000, 100000, 1000000,
+ 10000000, 100000000, 1000000000 };
+ *len = 0;
+
+ while (kappa > 0) {
+ uint32_t d;
+ switch (kappa) {
+ case 10: d = p1 / 1000000000; p1 %= 1000000000; break;
+ case 9: d = p1 / 100000000; p1 %= 100000000; break;
+ case 8: d = p1 / 10000000; p1 %= 10000000; break;
+ case 7: d = p1 / 1000000; p1 %= 1000000; break;
+ case 6: d = p1 / 100000; p1 %= 100000; break;
+ case 5: d = p1 / 10000; p1 %= 10000; break;
+ case 4: d = p1 / 1000; p1 %= 1000; break;
+ case 3: d = p1 / 100; p1 %= 100; break;
+ case 2: d = p1 / 10; p1 %= 10; break;
+ case 1: d = p1; p1 = 0; break;
+ default:
+ nxt_unreachable();
+ }
+
+ if (d || *len)
+ buffer[(*len)++] = '0' + (char) (d);
+
+ kappa--;
+
+ uint64_t tmp = ((uint64_t) (p1) << -one.e) + p2;
+
+ if (tmp <= delta) {
+ *K += kappa;
+ GrisuRound(buffer, *len, delta, tmp,
+ (uint64_t) (kPow10[kappa]) << -one.e, wp_w.f);
+ return;
+ }
+ }
+
+ /* kappa = 0 */
+ for (;;) {
+ p2 *= 10;
+ delta *= 10;
+ char d = (char) (p2 >> -one.e);
+
+ if (d || *len)
+ buffer[(*len)++] = '0' + d;
+
+ p2 &= one.f - 1;
+ kappa--;
+
+ if (p2 < delta) {
+ *K += kappa;
+ uint32_t kpow = (-kappa < 9) ? kPow10[-kappa] : 0;
+ GrisuRound(buffer, *len, delta, p2, one.f, wp_w.f * kpow);
+ return;
+ }
+ }
+}
+
+
+static inline void
+Grisu2(double value, char* buffer, int* length, int* K)
+{
+ const nxt_diyfp_t v = nxt_d2diyfp(value);
+ nxt_diyfp_t w_m, w_p;
+
+ nxt_diyfp_normalize_boundaries(v, &w_m, &w_p);
+
+ const nxt_diyfp_t c_mk = nxt_cached_power_bin(w_p.e, K);
+ const nxt_diyfp_t W = nxt_diyfp_multiply(nxt_diyfp_normalize(v), c_mk);
+ nxt_diyfp_t Wp = nxt_diyfp_multiply(w_p, c_mk);
+ nxt_diyfp_t Wm = nxt_diyfp_multiply(w_m, c_mk);
+ Wm.f++;
+ Wp.f--;
+
+ DigitGen(W, Wp, Wp.f - Wm.f, buffer, length, K);
+}
+
+
+static const char cDigitsLut[200] = {
+ '0', '0', '0', '1', '0', '2', '0', '3', '0', '4',
+ '0', '5', '0', '6', '0', '7', '0', '8', '0', '9',
+ '1', '0', '1', '1', '1', '2', '1', '3', '1', '4',
+ '1', '5', '1', '6', '1', '7', '1', '8', '1', '9',
+ '2', '0', '2', '1', '2', '2', '2', '3', '2', '4',
+ '2', '5', '2', '6', '2', '7', '2', '8', '2', '9',
+ '3', '0', '3', '1', '3', '2', '3', '3', '3', '4',
+ '3', '5', '3', '6', '3', '7', '3', '8', '3', '9',
+ '4', '0', '4', '1', '4', '2', '4', '3', '4', '4',
+ '4', '5', '4', '6', '4', '7', '4', '8', '4', '9',
+ '5', '0', '5', '1', '5', '2', '5', '3', '5', '4',
+ '5', '5', '5', '6', '5', '7', '5', '8', '5', '9',
+ '6', '0', '6', '1', '6', '2', '6', '3', '6', '4',
+ '6', '5', '6', '6', '6', '7', '6', '8', '6', '9',
+ '7', '0', '7', '1', '7', '2', '7', '3', '7', '4',
+ '7', '5', '7', '6', '7', '7', '7', '8', '7', '9',
+ '8', '0', '8', '1', '8', '2', '8', '3', '8', '4',
+ '8', '5', '8', '6', '8', '7', '8', '8', '8', '9',
+ '9', '0', '9', '1', '9', '2', '9', '3', '9', '4',
+ '9', '5', '9', '6', '9', '7', '9', '8', '9', '9'
+};
+
+
+static inline void
+WriteExponent(int K, char* buffer)
+{
+ if (K < 0) {
+ *buffer++ = '-';
+ K = -K;
+ } else {
+ *buffer++ = '+';
+ }
+
+ if (K >= 100) {
+ *buffer++ = '0' + (char)(K / 100);
+ K %= 100;
+
+ const char* d = &cDigitsLut[K * 2];
+ *buffer++ = d[0];
+ *buffer++ = d[1];
+
+ } else if (K >= 10) {
+ const char* d = &cDigitsLut[K * 2];
+ *buffer++ = d[0];
+ *buffer++ = d[1];
+
+ } else {
+ *buffer++ = '0' + (char) (K);
+ }
+
+ *buffer = '\0';
+}
+
+
+static inline void
+Prettify(char* buffer, int length, int k)
+{
+ /* 10^(kk-1) <= v < 10^kk */
+ const int kk = length + k;
+
+ if (length <= kk && kk <= 21) {
+
+ /* 1234e7 -> 12340000000 */
+
+ for (int i = length; i < kk; i++)
+ buffer[i] = '0';
+
+ buffer[kk] = '\0';
+
+ } else if (0 < kk && kk <= 21) {
+
+ /* 1234e-2 -> 12.34 */
+
+ memmove(&buffer[kk + 1], &buffer[kk], length - kk);
+ buffer[kk] = '.';
+ buffer[length + 1] = '\0';
+
+ } else if (-6 < kk && kk <= 0) {
+
+ /* 1234e-6 -> 0.001234 */
+
+ const int offset = 2 - kk;
+ memmove(&buffer[offset], &buffer[0], length);
+
+ buffer[0] = '0';
+ buffer[1] = '.';
+
+ for (int i = 2; i < offset; i++)
+ buffer[i] = '0';
+
+ buffer[length + offset] = '\0';
+
+ } else if (length == 1) {
+
+ /* 1e30 */
+
+ buffer[1] = 'e';
+ WriteExponent(kk - 1, &buffer[2]);
+
+ } else {
+
+ /* 1234e30 -> 1.234e33 */
+
+ memmove(&buffer[2], &buffer[1], length - 1);
+ buffer[1] = '.';
+ buffer[length + 1] = 'e';
+ WriteExponent(kk - 1, &buffer[0 + length + 2]);
+ }
+}
+
+
+size_t
+nxt_dtoa(double value, char* buf)
+{
+ int length, K;
+ char *p;
+
+ /* Not handling NaN and inf */
+
+ assert(!isnan(value));
+ assert(!isinf(value));
+
+ p = buf;
+
+ if (signbit(value)) {
+ *p++ = '-';
+ value = -value;
+ }
+
+ if (value == 0) {
+ *p++ = '0';
+
+ return p - buf;
+
+ } else {
+
+ Grisu2(value, p, &length, &K);
+ Prettify(p, length, K);
+
+ return strlen(buf);
+ }
+}
diff --git a/nxt/nxt_dtoa.h b/nxt/nxt_dtoa.h
new file mode 100644
--- /dev/null
+++ b/nxt/nxt_dtoa.h
@@ -0,0 +1,12 @@
+
+/*
+ * Copyright (C) Dmitry Volyntsev
+ * Copyright (C) Nginx, Inc.
+ */
+
+#ifndef _NXT_DTOA_H_INCLUDED_
+#define _NXT_DTOA_H_INCLUDED_
+
+NXT_EXPORT size_t nxt_dtoa(double value, char* buffer);
+
+#endif /* _NXT_DTOA_H_INCLUDED_ */
diff --git a/nxt/nxt_strtod.c b/nxt/nxt_strtod.c
new file mode 100644
--- /dev/null
+++ b/nxt/nxt_strtod.c
@@ -0,0 +1,382 @@
+/*
+ * An internal strtod() implementation based on V8 src/strtod.cc code without
+ * bignum support.
+ *
+ * Copyright 2012 the V8 project authors. All rights reserved.
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include <nxt_auto_config.h>
+#include <nxt_types.h>
+#include <nxt_clang.h>
+#include <nxt_diyfp.h>
+#include <nxt_strtod.h>
+#include <nxt_string.h>
+
+#include <assert.h>
+#include <math.h>
+
+/*
+ * Max double: 1.7976931348623157 x 10^308
+ * Min non-zero double: 4.9406564584124654 x 10^-324
+ * Any x >= 10^309 is interpreted as +infinity.
+ * Any x <= 10^-324 is interpreted as 0.
+ * Note that 2.5e-324 (despite being smaller than the min double) will be read
+ * as non-zero (equal to the min non-zero double).
+ */
+
+#define NXT_DECIMAL_POWER_MAX 309
+#define NXT_DECIMAL_POWER_MIN (-324)
+
+#define NXT_UINT64_MAX 0xFFFFFFFFFFFFFFFF
+#define NXT_UINT64_DECIMAL_DIGITS_MAX 19
+
+
+/*
+ * Reads digits from the buffer and converts them to a uint64.
+ * Reads in as many digits as fit into a uint64.
+ * When the string starts with "1844674407370955161" no further digit is read.
+ * Since 2^64 = 18446744073709551616 it would still be possible read another
+ * digit if it was less or equal than 6, but this would complicate the code.
+ */
+nxt_inline uint64_t
+nxt_read_uint64(const nxt_str_t *str, size_t *ndigits)
+{
+ u_char *p, *e, d;
+ uint64_t value;
+
+ value = 0;
+
+ p = str->start;
+ e = p + str->length;
+
+ while (p < e && value <= (NXT_UINT64_MAX / 10 - 1)) {
+ d = *p++ - '0';
+ value = 10 * value + d;
+ }
+
+ *ndigits = p - str->start;
+
+ return value;
+}
+
+
+/*
+ * Reads a nxt_diyfp_t from the buffer.
+ * The returned nxt_diyfp_t is not necessarily normalized.
+ * If remaining is zero then the returned nxt_diyfp_t is accurate.
+ * Otherwise it has been rounded and has error of at most 1/2 ulp.
+ */
+static nxt_diyfp_t
+nxt_diyfp_read(const nxt_str_t *str, int *remaining)
+{
+ size_t read;
+ uint64_t significand;
+
+ significand = nxt_read_uint64(str, &read);
+
+ /* Round the significand. */
+
+ if (str->length != read) {
+ if (str->start[read] >= '5') {
+ significand++;
+ }
+ }
+
+ *remaining = str->length - read;
+
+ return nxt_diyfp(significand, 0);
+}
+
+
+/*
+ * Returns 10^exp as an exact nxt_diyfp_t.
+ * The given exp must be in the range [1; NXT_DECIMAL_EXPONENT_DIST[.
+ */
+static nxt_diyfp_t
+nxt_adjust_pow10(int exp)
+{
+ assert(0 < exp);
+
+ switch (exp) {
+ case 1: return nxt_diyfp(UINT64_C2(0xa0000000, 00000000), -60);
+ case 2: return nxt_diyfp(UINT64_C2(0xc8000000, 00000000), -57);
+ case 3: return nxt_diyfp(UINT64_C2(0xfa000000, 00000000), -54);
+ case 4: return nxt_diyfp(UINT64_C2(0x9c400000, 00000000), -50);
+ case 5: return nxt_diyfp(UINT64_C2(0xc3500000, 00000000), -47);
+ case 6: return nxt_diyfp(UINT64_C2(0xf4240000, 00000000), -44);
+ case 7: return nxt_diyfp(UINT64_C2(0x98968000, 00000000), -40);
+ default:
+ nxt_unreachable();
+ }
+}
+
+
+/*
+ * If the function returns true then the result is the correct double.
+ * Otherwise it is either the correct double or the double that is just below
+ * the correct double.
+ */
+static double
+nxt_diyfp_strtod(nxt_str_t *str, int exp)
+{
+ int remaining, dec_exp, adj_exp;
+ nxt_diyfp_t value, pow, adj_pow, rounded;
+
+ value = nxt_diyfp_read(str, &remaining);
+
+ // Since we may have dropped some digits the value is not accurate.
+ // If remaining is different than 0 than the error is at most
+ // .5 ulp (unit in the last place).
+ // We don't want to deal with fractions and therefore keep a common
+ // denominator.
+ const int kDenominatorLog = 3;
+ const int kDenominator = 1 << kDenominatorLog;
+ // Move the remaining decimals into the exp.
+ exp += remaining;
+ int64_t error = (remaining == 0 ? 0 : kDenominator / 2);
+
+ int old_e = value.e;
+ value = nxt_diyfp_normalize(value);
+ error <<= old_e - value.e;
+
+ assert(exp <= NXT_DECIMAL_EXPONENT_MAX);
+
+ if (exp < NXT_DECIMAL_EXPONENT_MIN) {
+ return 0.0;
+ }
+
+ pow = nxt_cached_power_dec(exp, &dec_exp);
+
+ if (dec_exp != exp) {
+ adj_exp = exp - dec_exp;
+ adj_pow = nxt_adjust_pow10(exp - dec_exp);
+
+ value = nxt_diyfp_multiply(value, adj_pow);
+ if (NXT_UINT64_DECIMAL_DIGITS_MAX - (int) str->length < adj_exp) {
+ // The adjustment power is exact. There is hence only
+ // an error of 0.5.
+ error += kDenominator / 2;
+ }
+ }
+
+ value = nxt_diyfp_multiply(value, pow);
+
+ // The error introduced by a multiplication of a*b equals
+ // error_a + error_b + error_a*error_b/2^64 + 0.5
+ // Substituting a with 'value' and b with 'pow' we have
+ // error_b = 0.5 (all cached powers have an error of less than 0.5 ulp),
+ // error_ab = 0 or 1 / kDenominator > error_a * error_b / 2^64
+ int error_b = kDenominator / 2;
+ int error_ab = (error == 0 ? 0 : 1); // We round up to 1.
+ int fixed_error = kDenominator / 2;
+ error += error_b + error_ab + fixed_error;
+
+ old_e = value.e;
+ value = nxt_diyfp_normalize(value);
+ error <<= old_e - value.e;
+
+ // See if the double's significand changes if we add/subtract the error.
+ int order_of_magnitude = NXT_DIYFP_SIGNIFICAND_SIZE + value.e;
+
+ int effective_significand_size =
+ SignificandSizeForOrderOfMagnitude(order_of_magnitude);
+
+ int precision_digits_count =
+ NXT_DIYFP_SIGNIFICAND_SIZE - effective_significand_size;
+
+ if (precision_digits_count + kDenominatorLog >= NXT_DIYFP_SIGNIFICAND_SIZE) {
+ // This can only happen for very small denormals. In this case the
+ // half-way multiplied by the denominator exceeds the range of an uint64.
+ // Simply shift everything to the right.
+ int shift_amount = (precision_digits_count + kDenominatorLog)
+ - NXT_DIYFP_SIGNIFICAND_SIZE + 1;
+
+ value = nxt_diyfp(value.f >> shift_amount, value.e + shift_amount);
+ // We add 1 for the lost precision of error, and kDenominator for
+ // the lost precision of value.f.
+ error = (error >> shift_amount) + 1 + kDenominator;
+ precision_digits_count -= shift_amount;
+ }
+
+ // We use uint64_ts now. This only works if the nxt_diyfp_t uses uint64_ts too.
+ assert(precision_digits_count < 64);
+
+ uint64_t one64 = 1;
+ uint64_t precision_bits_mask = (one64 << precision_digits_count) - 1;
+ uint64_t precision_bits = value.f & precision_bits_mask;
+ uint64_t half_way = one64 << (precision_digits_count - 1);
+ precision_bits *= kDenominator;
+ half_way *= kDenominator;
+
+ rounded = nxt_diyfp(value.f >> precision_digits_count,
+ value.e + precision_digits_count);
+
+ if (precision_bits >= half_way + error) {
+ rounded.f++;
+ }
+
+ return nxt_diyfp2d(rounded);
+}
+
+
+nxt_inline size_t
+nxt_trim_leading_zeros(nxt_str_t *str)
+{
+ u_char *p, *e;
+
+ p = str->start;
+ e = p + str->length;
+
+ while (p < e) {
+ if (*p != '0') {
+ str->start = p;
+ break;
+ }
+
+ p++;
+ }
+
+ str->length = e - p;
+
+ return str->length;
+}
+
+
+nxt_inline size_t
+nxt_trim_trailing_zeros(nxt_str_t *str)
+{
+ u_char *b, *p;
+
+ b = str->start;
+ p = b + str->length;
+
+ while (p >= b) {
+ if (*p != '0') {
+ break;
+ }
+
+ p++;
+ }
+
+ str->length = p - b;
+
+ return str->length;
+}
+
+
+static double
+nxt_strtod_internal(nxt_str_t *str, int exp)
+{
+ size_t left, right;
+
+ left = nxt_trim_leading_zeros(str);
+ right = nxt_trim_trailing_zeros(str);
+
+ exp += (int) (left - right);
+
+ if (str->length == 0) {
+ return 0.0;
+ }
+
+ if (exp + (int) str->length - 1 >= NXT_DECIMAL_POWER_MAX) {
+ return INFINITY;
+ }
+
+ if (exp + (int) str->length <= NXT_DECIMAL_POWER_MIN) {
+ return 0.0;
+ }
+
+ return nxt_diyfp_strtod(str, exp);
+}
+
+
+double
+nxt_strtod(const u_char **start, const u_char *end)
+{
+ int exponent, exp;
+ u_char c;
+ nxt_str_t buf;
+ nxt_bool_t minus;
+ const u_char *e, *p;
+ u_char data[128];
+
+ exponent = 0;
+
+ buf.start = data;
+ buf.length = 0;
+
+ p = *start;
+
+ for (; p < end && buf.length < sizeof(data); p++) {
+ /* Values less than '0' become >= 208. */
+ c = *p - '0';
+
+ if (nxt_slow_path(c > 9)) {
+ break;
+ }
+
+ buf.start[buf.length++] = *p;
+ }
+
+ /* We don't emit a '.', but adjust the exponent instead. */
+ if (p < end && *p == '.') {
+
+ p++;
+
+ for (; p < end && buf.length < sizeof(data); p++) {
+ /* Values less than '0' become >= 208. */
+ c = *p - '0';
+
+ if (nxt_slow_path(c > 9)) {
+ break;
+ }
+
+ buf.start[buf.length++] = *p;
+ exponent--;
+ }
+ }
+
+ e = p + 1;
+
+ if (e < end && (*p == 'e' || *p == 'E')) {
+ minus = 0;
+
+ if (e + 1 < end) {
+ if (*e == '-') {
+ e++;
+ minus = 1;
+
+ } else if (*e == '+') {
+ e++;
+ }
+ }
+
+ /* Values less than '0' become >= 208. */
+ c = *e - '0';
+
+ if (nxt_fast_path(c <= 9)) {
+ exp = c;
+ p = e + 1;
+
+ while (p < end) {
+ /* Values less than '0' become >= 208. */
+ c = *p - '0';
+
+ if (nxt_slow_path(c > 9)) {
+ break;
+ }
+
+ exp = exp * 10 + c;
+ p++;
+ }
+
+ exponent += minus ? -exp : exp;
+ }
+ }
+
+ *start = p;
+
+ return nxt_strtod_internal(&buf, exponent);
+}
diff --git a/nxt/nxt_strtod.h b/nxt/nxt_strtod.h
new file mode 100644
--- /dev/null
+++ b/nxt/nxt_strtod.h
@@ -0,0 +1,12 @@
+
+/*
+ * Copyright (C) Dmitry Volyntsev
+ * Copyright (C) Nginx, Inc.
+ */
+
+#ifndef _NXT_STRTOD_H_INCLUDED_
+#define _NXT_STRTOD_H_INCLUDED_
+
+NXT_EXPORT double nxt_strtod(const u_char **start, const u_char *end);
+
+#endif /* _NXT_STRTOD_H_INCLUDED_ */ |
|
Hi @xeioex ! nxt/nxt_strtod.c
nxt/nxt_strtod.c: In function ‘TrimTrailingZeros’:
nxt/nxt_strtod.c:62:39: error: comparison of unsigned expression >= 0 is always true [-Werror=type-limits]
for (i = buffer.length - 1; i >= 0; --i) {so i change the test to >> 0.00000123
0.00000123
>> 0.000001234
0.000001234
>> 0.0000012345
0.0000012345
>> 0.00000123456
0.00000123456
>> 0.000001234567
0.000001234567
>> 0.00000001
0
>> 0.0000001
0
>> 0.000001
0
>> 0.00001
0
>> 0.0001
0
>> 0.001
0
>> 0.01
0
>> 0.1
0
>> |
|
@drsm Please, try the updated patch from my first message. That part was rewritten. Your tests work the same way as in V8. |
|
@xeioex thank you for the patch, works fine for me. |
Merged
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
https://www.ecma-international.org/ecma-262/6.0/#sec-tostring-applied-to-the-number-type
some reference implementations may be found here https://github.com/miloyip/dtoa-benchmark
The text was updated successfully, but these errors were encountered: