Merge pull request #12 from Kijewski/pr-faster-floating-point-encoding
Faster double encoding
diff --git a/.github/workflows/compile_test.yml b/.github/workflows/compile_test.yml
index 9928efc..140aece 100644
--- a/.github/workflows/compile_test.yml
+++ b/.github/workflows/compile_test.yml
@@ -12,8 +12,8 @@
- macos-latest
- windows-latest
python: [
- '3.5',
- # '3.6', '3.7', '3.8', # it takes too much GitHub action time to run tests on all versions in between
+ '3.6',
+ # '3.5', '3.7', '3.8', # it takes too much GitHub action time to run tests on all versions in between
'3.9',
]
include:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 1a97231..8149835 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,3 +1,8 @@
+### 1.5.0
+
+* Faster floating-point number encoding using [Junekey Jeon's Dragonbox algorithm](https://github.com/abolz/Drachennest/blob/77f4889a4cd9d7f0b9da82a379f14beabcfba13e/src/dragonbox.cc) implemented by Alexander Bolz
+* Removed a lot of configuration options from pyjson5.Options()
+
### 1.4.9
* Faster floating-point number decoding using [fast_double_parser](https://github.com/lemire/fast_double_parser) by Daniel Lemire
diff --git a/Makefile b/Makefile
index 4b878d7..ec84964 100644
--- a/Makefile
+++ b/Makefile
@@ -10,7 +10,8 @@
INCLUDES := \
src/VERSION src/DESCRIPTION \
src/_decoder_recursive_select.hpp src/_unicode_cat_of.hpp \
- src/_escape_dct.hpp src/_stack_heap_string.hpp src/native.hpp
+ src/_escape_dct.hpp src/_stack_heap_string.hpp src/native.hpp \
+ src/dragonbox.cc
FILES := Makefile MANIFEST.in pyjson5.pyx README.rst setup.py ${INCLUDES}
diff --git a/docs/performance.rst b/docs/performance.rst
index 5756899..9563649 100644
--- a/docs/performance.rst
+++ b/docs/performance.rst
@@ -25,9 +25,71 @@
The output is always ASCII regardless if you call :func:`pyjson5.encode` or :func:`pyjson5.encode_bytes`.
* Dataset: https://github.com/zemirco/sf-city-lots-json
-* Version: 3.9.1 (default, Dec 8 2020, 07:51:42)
+* Python 3.9.1+ (default, Feb 5 2021, 13:46:56)
* CPU: AMD Ryzen 7 2700 @ 3.7GHz
-* :func:`pyjson5.encode`: **3.21** s ± 25.1 per loop *(lower is better)*
-* :func:`json.dumps`: **3.82** s ± 20.4 ms per loop
-* :func:`json.dumps` + :func:`xml.sax.saxutils.escape`: **3.95** s ± 18.3 ms per loop
-* The encoder works correcty: ``obj == json.loads(pyjson5.encode(obj, floatformat='%.16e'))``
+* :func:`pyjson5.encode`: **1.37** s ± 19.2 per loop *(lower is better)*
+* :func:`json.dumps`: **3.66** s ± 72.6 ms per loop
+* :func:`json.dumps` + :func:`xml.sax.saxutils.escape`: **4.01** s ± 21.3 ms per loop
+* The encoder works correcty: ``obj == json.loads(pyjson5.encode(obj))``
+
+
+Benchmark
+---------
+
+Using `Ultrajson's benchmark <https://github.com/ultrajson/ultrajson/blob/197a7fd4d8bbf0a8355852017c8b25aab26b6777/tests/benchmark.py>`_
+you can tell for which kind of data PyJSON5 is fast, and for which data it is slow in comparison *(higher is better)*:
+
++-----------------------------------------------------------+-------------+------------+------------+------------+
+| | json | pyjson5 | ujson | orjson |
++===========================================================+=============+============+============+============+
+| **Array with 256 doubles** | | | | |
++-----------------------------------------------------------+-------------+------------+------------+------------+
+| encode | 6,425 | 81,202 | 28,966 | 83,836 |
++-----------------------------------------------------------+-------------+------------+------------+------------+
+| decode | 16,759 | 34,801 | 34,794 | 80,655 |
++-----------------------------------------------------------+-------------+------------+------------+------------+
+| **Array with 256 strings** | | | | |
++-----------------------------------------------------------+-------------+------------+------------+------------+
+| encode | 36,969 | 73,165 | 35,574 | 113,082 |
++-----------------------------------------------------------+-------------+------------+------------+------------+
+| decode | 42,730 | 38,542 | 38,386 | 60,732 |
++-----------------------------------------------------------+-------------+------------+------------+------------+
+| **Array with 256 UTF-8 strings** | | | | |
++-----------------------------------------------------------+-------------+------------+------------+------------+
+| encode | 3,458 | 3,134 | 4,024 | 31,677 |
++-----------------------------------------------------------+-------------+------------+------------+------------+
+| decode | 2,428 | 2,498 | 2,491 | 1,750 |
++-----------------------------------------------------------+-------------+------------+------------+------------+
+| **Array with 256 True values** | | | | |
++-----------------------------------------------------------+-------------+------------+------------+------------+
+| encode | 130,441 | 282,703 | 131,279 | 423,371 |
++-----------------------------------------------------------+-------------+------------+------------+------------+
+| decode | 220,657 | 262,690 | 264,485 | 262,283 |
++-----------------------------------------------------------+-------------+------------+------------+------------+
+| **Array with 256 dict{string, int} pairs** | | | | |
++-----------------------------------------------------------+-------------+------------+------------+------------+
+| encode | 11,621 | 10,014 | 18,148 | 73,905 |
++-----------------------------------------------------------+-------------+------------+------------+------------+
+| decode | 17,802 | 19,406 | 19,391 | 23,478 |
++-----------------------------------------------------------+-------------+------------+------------+------------+
+| **Dict with 256 arrays with 256 dict{string, int} pairs** | | | | |
++-----------------------------------------------------------+-------------+------------+------------+------------+
+| encode | 40 | 38 | 68 | 213 |
++-----------------------------------------------------------+-------------+------------+------------+------------+
+| decode | 43 | 49 | 48 | 51 |
++-----------------------------------------------------------+-------------+------------+------------+------------+
+| **Medium complex object** | | | | |
++-----------------------------------------------------------+-------------+------------+------------+------------+
+| encode | 8,704 | 11,922 | 15,319 | 49,677 |
++-----------------------------------------------------------+-------------+------------+------------+------------+
+| decode | 12,567 | 14,042 | 13,985 | 19,481 |
++-----------------------------------------------------------+-------------+------------+------------+------------+
+| **Complex object** | | | | |
++-----------------------------------------------------------+-------------+------------+------------+------------+
+| encode | 672 | 909 | 731 | |
++-----------------------------------------------------------+-------------+------------+------------+------------+
+| decode | 462 | 700 | 700 | |
++-----------------------------------------------------------+-------------+------------+------------+------------+
+
+* `ujson <https://github.com/ultrajson/ultrajson>`_ == 4.0.3.dev9
+* `orjson <https://github.com/ijl/orjson>`_ == 3.5.1
diff --git a/requirements.txt b/requirements.txt
index 9000539..9c1dc39 100644
--- a/requirements.txt
+++ b/requirements.txt
@@ -3,6 +3,6 @@
cython == 0.*, >= 0.29.14
more_itertools == 8.*, >= 8.0.2
sphinx == 2.*, >= 2.2.2
-sphinx_autodoc_typehints == 1.*, >= 1.10.3
+sphinx_autodoc_typehints == 1.*, >= 1.10.3, < 1.11
sphinx_rtd_theme == 0.*, >= 0.4.3
wheel == 0.*, >= 0.33.6
diff --git a/src/VERSION b/src/VERSION
index 340028b..c5c7371 100644
--- a/src/VERSION
+++ b/src/VERSION
@@ -1 +1 @@
-"1.4.9.post1"
+"1.5.0"
diff --git a/src/_encoder.pyx b/src/_encoder.pyx
index 675034d..80dd2c4 100644
--- a/src/_encoder.pyx
+++ b/src/_encoder.pyx
@@ -286,49 +286,46 @@
return True
-cdef int _encode_format_string(WriterRef writer, object data, object formatter_string) except -1:
+cdef int _encode_format_string(WriterRef writer, object data, object fmt) except -1:
+ cdef object formatted
cdef const char *string
cdef Py_ssize_t length = 0 # silence warning
- if expect(formatter_string is None, False):
- _raise_unstringifiable(data)
-
- formatter_string = PyUnicode_Format(formatter_string, data)
- string = PyUnicode_AsUTF8AndSize(formatter_string, &length)
+ formatted = PyUnicode_Format(fmt, data)
+ string = PyUnicode_AsUTF8AndSize(formatted, &length)
writer.append_s(writer, string, length)
return True
cdef int _encode_float(WriterRef writer, object data) except -1:
- cdef object formatter_string
cdef double value = PyFloat_AsDouble(data)
cdef int classification = fpclassify(value)
+ cdef char buf[64]
+ cdef char *end
+ cdef char *string
+ cdef Py_ssize_t length
if classification == FP_NORMAL:
- return _encode_format_string(writer, data, (<Options> writer.options).floatformat)
-
- if classification in (FP_SUBNORMAL, FP_ZERO):
- writer.append_c(writer, b'0')
- return True
-
- if classification == FP_NAN:
- formatter_string = (<Options> writer.options).nan
+ end = Dtoa(buf, PyFloat_AsDouble(data))
+ length = end - buf
+ string = buf
+ elif classification in (FP_SUBNORMAL, FP_ZERO):
+ string = b'0.0'
+ length = 3
+ elif classification == FP_NAN:
+ string = b'NaN'
+ length = 3
else:
# classification == FP_INFINITE
if value > 0.0:
- formatter_string = (<Options> writer.options).posinfinity
+ string = b'Infinity'
+ length = 8
else:
- formatter_string = (<Options> writer.options).neginfinity
+ string = b'-Infinity'
+ length = 9
- if expect(formatter_string is None, False):
- _raise_unstringifiable(data)
-
- writer.append_s(
- writer,
- <const char*> PyUnicode_1BYTE_DATA(formatter_string),
- PyUnicode_GET_LENGTH(formatter_string),
- )
+ writer.append_s(writer, string, length)
return True
@@ -339,7 +336,7 @@
else:
writer.append_s(writer, 'false', 5)
else:
- _encode_format_string(writer, data, (<Options> writer.options).intformat)
+ _encode_format_string(writer, data, DEFAULT_INTFORMAT)
return True
@@ -347,7 +344,7 @@
if not isinstance(data, Decimal):
return False
- _encode_format_string(writer, data, (<Options> writer.options).decimalformat)
+ _encode_format_string(writer, data, DEFAULT_DECIMALFORMAT)
return True
diff --git a/src/_encoder_options.pyx b/src/_encoder_options.pyx
index 7454c3e..16d5bee 100644
--- a/src/_encoder_options.pyx
+++ b/src/_encoder_options.pyx
@@ -1,9 +1,5 @@
cdef object DEFAULT_TOJSON = False
-cdef object DEFAULT_POSINFINITY = 'Infinity'
-cdef object DEFAULT_NEGINFINITY = '-Infinity'
-cdef object DEFAULT_NAN = 'NaN'
cdef object DEFAULT_INTFORMAT = '%d'
-cdef object DEFAULT_FLOATFORMAT = '%.6e'
cdef object DEFAULT_DECIMALFORMAT = '%s'
cdef object DEFAULT_MAPPINGTYPES = (Mapping,)
cdef object DEFAULT_QUOTATIONMARK = '"'
@@ -45,12 +41,6 @@
return ', '.join(filter(bool, (
_option_from_ascii('quotationmark', self.quotationmark, DEFAULT_QUOTATIONMARK),
_option_from_ascii('tojson', self.tojson, None),
- _option_from_ascii('posinfinity', self.posinfinity, DEFAULT_POSINFINITY),
- _option_from_ascii('neginfinity', self.neginfinity, DEFAULT_NEGINFINITY),
- _option_from_ascii('intformat', self.intformat, DEFAULT_INTFORMAT),
- _option_from_ascii('floatformat', self.floatformat, DEFAULT_FLOATFORMAT),
- _option_from_ascii('decimalformat', self.decimalformat, DEFAULT_DECIMALFORMAT),
- _option_from_ascii('nan', self.nan, DEFAULT_NAN),
)))
@@ -73,30 +63,6 @@
* **str:** A special method to call on objects to return a custom JSON encoded string. Must return ASCII data!
* **False:** No such member exists. (Default.)
* **None:** Use default.
- posinfinity : str|False|None
- * **str:** String to represent positive infinity. Must be ASCII.
- * **False:** Throw an exception if ``float('+inf')`` is encountered.
- * **None:** Use default: ``"Infinity"``.
- neginfinity : str|False|None
- * **str:** String to represent negative infinity. Must be ASCII.
- * **False:** Throw an exception if ``float('-inf')`` is encountered.
- * **None:** Use default: ``"-Infinity"``.
- nan : str|False|None
- * **str:** String to represent not-a-number. Must be ASCII.
- * **False:** Throw an exception if ``float('NaN')`` is encountered.
- * **None:** Use default: ``"NaN"``.
- intformat : str|False|None
- * **str:** Format string to use with ``int``.
- * **False:** Throw an exception if an ``int`` is encountered.
- * **None:** Use default: ``"%d"``.
- floatformat : str|False|None
- * **str:** Format string to use with ``float``.
- * **False:** Throw an exception if a ``float`` is encountered.
- * **None:** Use default: ``"%.6e"``.
- decimalformat : str|False|None
- * **str:** Format string to use with ``Decimal``.
- * **False:** Throw an exception if a ``Decimal`` is encountered.
- * **None:** Use default: ``"%s"``.
mappingtypes : Iterable[type]|False|None
* **Iterable[type]:** Classes that should be encoded to objects. Must be iterable over their keys, and implement ``__getitem__``.
* **False:** There are no objects. Any object will be encoded as list of keys as in list(obj).
@@ -109,30 +75,6 @@
'''The creation argument ``tojson``.
``None`` if ``False`` was specified.
'''
- cdef readonly unicode posinfinity
- '''The creation argument ``posinfinity``.
- ``None`` if ``False`` was specified.
- '''
- cdef readonly unicode neginfinity
- '''The creation argument ``neginfinity``.
- ``None`` if ``False`` was specified.
- '''
- cdef readonly unicode nan
- '''The creation argument ``nan``.
- ``None`` if ``False`` was specified.
- '''
- cdef readonly unicode intformat
- '''The creation argument ``intformat``.
- ``None`` if ``False`` was specified.
- '''
- cdef readonly unicode floatformat
- '''The creation argument ``floatformat``.
- ``None`` if ``False`` was specified.
- '''
- cdef readonly unicode decimalformat
- '''The creation argument ``decimalformat``.
- ``None`` if ``False`` was specified.
- '''
cdef readonly tuple mappingtypes
'''The creation argument ``mappingtypes``.
``()`` if ``False`` was specified.
@@ -142,12 +84,7 @@
cdef object args = tuple(filter(bool, (
_options_reduce_arg('quotationmark', self.quotationmark, DEFAULT_QUOTATIONMARK),
_options_reduce_arg('tojson', self.tojson, None),
- _options_reduce_arg('posinfinity', self.posinfinity, DEFAULT_POSINFINITY),
- _options_reduce_arg('neginfinity', self.neginfinity, DEFAULT_NEGINFINITY),
- _options_reduce_arg('intformat', self.intformat, DEFAULT_INTFORMAT),
- _options_reduce_arg('floatformat', self.floatformat, DEFAULT_FLOATFORMAT),
- _options_reduce_arg('decimalformat', self.decimalformat, DEFAULT_DECIMALFORMAT),
- _options_reduce_arg('nan', self.nan, DEFAULT_NAN),
+ _options_reduce_arg('mappingtypes', self.mappingtypes, DEFAULT_MAPPINGTYPES),
)))
return (_UnpickleOptions if args else Options), args
@@ -170,7 +107,7 @@
def __cinit__(self, *,
quotationmark=None,
tojson=None, posinfinity=None, neginfinity=None, nan=None,
- decimalformat=None, intformat=None, floatformat=None,
+ decimalformat=None, intformat=None,
mappingtypes=None):
cdef object cls
cdef object ex
@@ -179,51 +116,15 @@
quotationmark = DEFAULT_QUOTATIONMARK
if tojson is None:
tojson = DEFAULT_TOJSON
- if posinfinity is None:
- posinfinity = DEFAULT_POSINFINITY
- if neginfinity is None:
- neginfinity = DEFAULT_NEGINFINITY
- if nan is None:
- nan = DEFAULT_NAN
- if intformat is None:
- intformat = DEFAULT_INTFORMAT
- if floatformat is None:
- floatformat = DEFAULT_FLOATFORMAT
- if decimalformat is None:
- decimalformat = DEFAULT_DECIMALFORMAT
if mappingtypes is None:
mappingtypes = DEFAULT_MAPPINGTYPES
self.quotationmark = _options_ascii(quotationmark)
self.tojson = _options_ascii(tojson, False)
- self.posinfinity = _options_ascii(posinfinity)
- self.neginfinity = _options_ascii(neginfinity)
- self.intformat = _options_ascii(intformat)
- self.floatformat = _options_ascii(floatformat)
- self.decimalformat = _options_ascii(decimalformat)
- self.nan = _options_ascii(nan)
if self.quotationmark is None or PyUnicode_GET_LENGTH(self.quotationmark) != 1:
raise TypeError('quotationmark must be one ASCII character.')
- if intformat is not None:
- try:
- PyUnicode_Format(intformat, TEST_INT)
- except Exception as ex:
- raise ValueError('intformat is not a valid format string') from ex
-
- if floatformat is not None:
- try:
- PyUnicode_Format(floatformat, TEST_FLOAT)
- except Exception as ex:
- raise ValueError('floatformat is not a valid format string') from ex
-
- if decimalformat is not None:
- try:
- PyUnicode_Format(decimalformat, TEST_DECIMAL)
- except Exception as ex:
- raise ValueError('decimalformat is not a valid format string') from ex
-
if mappingtypes is False:
self.mappingtypes = ()
else:
@@ -264,12 +165,6 @@
PyDict_SetDefault(kw, 'quotationmark', (<Options> arg).quotationmark)
PyDict_SetDefault(kw, 'tojson', (<Options> arg).tojson)
- PyDict_SetDefault(kw, 'posinfinity', (<Options> arg).posinfinity)
- PyDict_SetDefault(kw, 'neginfinity', (<Options> arg).neginfinity)
- PyDict_SetDefault(kw, 'nan', (<Options> arg).nan)
- PyDict_SetDefault(kw, 'intformat', (<Options> arg).intformat)
- PyDict_SetDefault(kw, 'floatformat', (<Options> arg).floatformat)
- PyDict_SetDefault(kw, 'decimalformat', (<Options> arg).decimalformat)
PyDict_SetDefault(kw, 'mappingtypes', (<Options> arg).mappingtypes)
return Options(**kw)
diff --git a/src/_imports.pyx b/src/_imports.pyx
index 75d9926..7af9493 100644
--- a/src/_imports.pyx
+++ b/src/_imports.pyx
@@ -130,6 +130,10 @@
const char *parse_number(const char *p, double *outDouble)
+cdef extern from 'src/dragonbox.cc' namespace 'dragonbox' nogil:
+ char *Dtoa(char* buffer, double value)
+
+
cdef extern from 'Python.h':
enum:
PyUnicode_WCHAR_KIND
diff --git a/src/dragonbox.cc b/src/dragonbox.cc
new file mode 100644
index 0000000..1855316
--- /dev/null
+++ b/src/dragonbox.cc
@@ -0,0 +1,1527 @@
+// Copyright 2020 Junekey Jeon
+// Copyright 2020 Alexander Bolz
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at https://www.boost.org/LICENSE_1_0.txt)
+
+//--------------------------------------------------------------------------------------------------
+// This file contains an implementation of Junekey Jeon's Dragonbox algorithm.
+//
+// It is a simplified version of the reference implementation found here:
+// https://github.com/jk-jeon/dragonbox
+//
+// The reference implementation also works with single-precision floating-point numbers and
+// has options to configure the rounding mode.
+//--------------------------------------------------------------------------------------------------
+
+#include <cstdint>
+#include <cstring>
+#include <limits>
+#if defined(_MSC_VER)
+#include <intrin.h>
+#endif
+
+#ifndef DRAGONBOX_ASSERT
+#define DRAGONBOX_ASSERT(X)
+#endif
+
+namespace dragonbox {
+namespace {
+
+//==================================================================================================
+//
+//==================================================================================================
+
+template <typename Dest, typename Source>
+static inline Dest ReinterpretBits(Source source)
+{
+ static_assert(sizeof(Dest) == sizeof(Source), "size mismatch");
+
+ Dest dest;
+ std::memcpy(&dest, &source, sizeof(Source));
+ return dest;
+}
+
+struct Double
+{
+ static_assert(std::numeric_limits<double>::is_iec559
+ && std::numeric_limits<double>::digits == 53
+ && std::numeric_limits<double>::max_exponent == 1024,
+ "IEEE-754 double-precision implementation required");
+
+ using value_type = double;
+ using bits_type = uint64_t;
+
+// static constexpr int32_t MaxDigits10 = std::numeric_limits<value_type>::max_digits10;
+ static constexpr int32_t SignificandSize = std::numeric_limits<value_type>::digits; // = p (includes the hidden bit)
+ static constexpr int32_t ExponentBias = std::numeric_limits<value_type>::max_exponent - 1 + (SignificandSize - 1);
+// static constexpr int32_t MaxExponent = std::numeric_limits<value_type>::max_exponent - 1 - (SignificandSize - 1);
+// static constexpr int32_t MinExponent = std::numeric_limits<value_type>::min_exponent - 1 - (SignificandSize - 1);
+ static constexpr bits_type MaxIeeeExponent = bits_type{2 * std::numeric_limits<value_type>::max_exponent - 1};
+ static constexpr bits_type HiddenBit = bits_type{1} << (SignificandSize - 1); // = 2^(p-1)
+ static constexpr bits_type SignificandMask = HiddenBit - 1; // = 2^(p-1) - 1
+ static constexpr bits_type ExponentMask = MaxIeeeExponent << (SignificandSize - 1);
+ static constexpr bits_type SignMask = ~(~bits_type{0} >> 1);
+
+ bits_type bits;
+
+ explicit Double(bits_type bits_) : bits(bits_) {}
+ explicit Double(value_type value) : bits(ReinterpretBits<bits_type>(value)) {}
+
+ bits_type PhysicalSignificand() const {
+ return bits & SignificandMask;
+ }
+
+ bits_type PhysicalExponent() const {
+ return (bits & ExponentMask) >> (SignificandSize - 1);
+ }
+
+ bool IsFinite() const {
+ return (bits & ExponentMask) != ExponentMask;
+ }
+
+ bool IsInf() const {
+ return (bits & ExponentMask) == ExponentMask && (bits & SignificandMask) == 0;
+ }
+
+ bool IsNaN() const {
+ return (bits & ExponentMask) == ExponentMask && (bits & SignificandMask) != 0;
+ }
+
+ bool IsZero() const {
+ return (bits & ~SignMask) == 0;
+ }
+
+ bool SignBit() const {
+ return (bits & SignMask) != 0;
+ }
+};
+
+//==================================================================================================
+//
+//==================================================================================================
+
+// Returns floor(x / 2^n).
+//
+// Technically, right-shift of negative integers is implementation defined...
+// Should easily be optimized into SAR (or equivalent) instruction.
+static inline int32_t FloorDivPow2(int32_t x, int32_t n)
+{
+#if 0
+ return x < 0 ? ~(~x >> n) : (x >> n);
+#else
+ return x >> n;
+#endif
+}
+
+static inline int32_t FloorLog2Pow10(int32_t e)
+{
+ DRAGONBOX_ASSERT(e >= -1233);
+ DRAGONBOX_ASSERT(e <= 1233);
+ return FloorDivPow2(e * 1741647, 19);
+}
+
+static inline int32_t FloorLog10Pow2(int32_t e)
+{
+ DRAGONBOX_ASSERT(e >= -1500);
+ DRAGONBOX_ASSERT(e <= 1500);
+ return FloorDivPow2(e * 1262611, 22);
+}
+
+static inline int32_t FloorLog10ThreeQuartersPow2(int32_t e)
+{
+ DRAGONBOX_ASSERT(e >= -1500);
+ DRAGONBOX_ASSERT(e <= 1500);
+ return FloorDivPow2(e * 1262611 - 524031, 22);
+}
+
+//==================================================================================================
+//
+//==================================================================================================
+
+namespace {
+struct uint64x2 {
+ uint64_t hi;
+ uint64_t lo;
+};
+}
+
+static inline uint64x2 ComputePow10(int32_t k)
+{
+ static constexpr int32_t kMin = -292;
+ static constexpr int32_t kMax = 326;
+ static constexpr uint64x2 Pow10[kMax - kMin + 1] = {
+ {0xFF77B1FCBEBCDC4F, 0x25E8E89C13BB0F7B},
+ {0x9FAACF3DF73609B1, 0x77B191618C54E9AD},
+ {0xC795830D75038C1D, 0xD59DF5B9EF6A2418},
+ {0xF97AE3D0D2446F25, 0x4B0573286B44AD1E},
+ {0x9BECCE62836AC577, 0x4EE367F9430AEC33},
+ {0xC2E801FB244576D5, 0x229C41F793CDA740},
+ {0xF3A20279ED56D48A, 0x6B43527578C11110},
+ {0x9845418C345644D6, 0x830A13896B78AAAA},
+ {0xBE5691EF416BD60C, 0x23CC986BC656D554},
+ {0xEDEC366B11C6CB8F, 0x2CBFBE86B7EC8AA9},
+ {0x94B3A202EB1C3F39, 0x7BF7D71432F3D6AA},
+ {0xB9E08A83A5E34F07, 0xDAF5CCD93FB0CC54},
+ {0xE858AD248F5C22C9, 0xD1B3400F8F9CFF69},
+ {0x91376C36D99995BE, 0x23100809B9C21FA2},
+ {0xB58547448FFFFB2D, 0xABD40A0C2832A78B},
+ {0xE2E69915B3FFF9F9, 0x16C90C8F323F516D},
+ {0x8DD01FAD907FFC3B, 0xAE3DA7D97F6792E4},
+ {0xB1442798F49FFB4A, 0x99CD11CFDF41779D},
+ {0xDD95317F31C7FA1D, 0x40405643D711D584},
+ {0x8A7D3EEF7F1CFC52, 0x482835EA666B2573},
+ {0xAD1C8EAB5EE43B66, 0xDA3243650005EED0},
+ {0xD863B256369D4A40, 0x90BED43E40076A83},
+ {0x873E4F75E2224E68, 0x5A7744A6E804A292},
+ {0xA90DE3535AAAE202, 0x711515D0A205CB37},
+ {0xD3515C2831559A83, 0x0D5A5B44CA873E04},
+ {0x8412D9991ED58091, 0xE858790AFE9486C3},
+ {0xA5178FFF668AE0B6, 0x626E974DBE39A873},
+ {0xCE5D73FF402D98E3, 0xFB0A3D212DC81290},
+ {0x80FA687F881C7F8E, 0x7CE66634BC9D0B9A},
+ {0xA139029F6A239F72, 0x1C1FFFC1EBC44E81},
+ {0xC987434744AC874E, 0xA327FFB266B56221},
+ {0xFBE9141915D7A922, 0x4BF1FF9F0062BAA9},
+ {0x9D71AC8FADA6C9B5, 0x6F773FC3603DB4AA},
+ {0xC4CE17B399107C22, 0xCB550FB4384D21D4},
+ {0xF6019DA07F549B2B, 0x7E2A53A146606A49},
+ {0x99C102844F94E0FB, 0x2EDA7444CBFC426E},
+ {0xC0314325637A1939, 0xFA911155FEFB5309},
+ {0xF03D93EEBC589F88, 0x793555AB7EBA27CB},
+ {0x96267C7535B763B5, 0x4BC1558B2F3458DF},
+ {0xBBB01B9283253CA2, 0x9EB1AAEDFB016F17},
+ {0xEA9C227723EE8BCB, 0x465E15A979C1CADD},
+ {0x92A1958A7675175F, 0x0BFACD89EC191ECA},
+ {0xB749FAED14125D36, 0xCEF980EC671F667C},
+ {0xE51C79A85916F484, 0x82B7E12780E7401B},
+ {0x8F31CC0937AE58D2, 0xD1B2ECB8B0908811},
+ {0xB2FE3F0B8599EF07, 0x861FA7E6DCB4AA16},
+ {0xDFBDCECE67006AC9, 0x67A791E093E1D49B},
+ {0x8BD6A141006042BD, 0xE0C8BB2C5C6D24E1},
+ {0xAECC49914078536D, 0x58FAE9F773886E19},
+ {0xDA7F5BF590966848, 0xAF39A475506A899F},
+ {0x888F99797A5E012D, 0x6D8406C952429604},
+ {0xAAB37FD7D8F58178, 0xC8E5087BA6D33B84},
+ {0xD5605FCDCF32E1D6, 0xFB1E4A9A90880A65},
+ {0x855C3BE0A17FCD26, 0x5CF2EEA09A550680},
+ {0xA6B34AD8C9DFC06F, 0xF42FAA48C0EA481F},
+ {0xD0601D8EFC57B08B, 0xF13B94DAF124DA27},
+ {0x823C12795DB6CE57, 0x76C53D08D6B70859},
+ {0xA2CB1717B52481ED, 0x54768C4B0C64CA6F},
+ {0xCB7DDCDDA26DA268, 0xA9942F5DCF7DFD0A},
+ {0xFE5D54150B090B02, 0xD3F93B35435D7C4D},
+ {0x9EFA548D26E5A6E1, 0xC47BC5014A1A6DB0},
+ {0xC6B8E9B0709F109A, 0x359AB6419CA1091C},
+ {0xF867241C8CC6D4C0, 0xC30163D203C94B63},
+ {0x9B407691D7FC44F8, 0x79E0DE63425DCF1E},
+ {0xC21094364DFB5636, 0x985915FC12F542E5},
+ {0xF294B943E17A2BC4, 0x3E6F5B7B17B2939E},
+ {0x979CF3CA6CEC5B5A, 0xA705992CEECF9C43},
+ {0xBD8430BD08277231, 0x50C6FF782A838354},
+ {0xECE53CEC4A314EBD, 0xA4F8BF5635246429},
+ {0x940F4613AE5ED136, 0x871B7795E136BE9A},
+ {0xB913179899F68584, 0x28E2557B59846E40},
+ {0xE757DD7EC07426E5, 0x331AEADA2FE589D0},
+ {0x9096EA6F3848984F, 0x3FF0D2C85DEF7622},
+ {0xB4BCA50B065ABE63, 0x0FED077A756B53AA},
+ {0xE1EBCE4DC7F16DFB, 0xD3E8495912C62895},
+ {0x8D3360F09CF6E4BD, 0x64712DD7ABBBD95D},
+ {0xB080392CC4349DEC, 0xBD8D794D96AACFB4},
+ {0xDCA04777F541C567, 0xECF0D7A0FC5583A1},
+ {0x89E42CAAF9491B60, 0xF41686C49DB57245},
+ {0xAC5D37D5B79B6239, 0x311C2875C522CED6},
+ {0xD77485CB25823AC7, 0x7D633293366B828C},
+ {0x86A8D39EF77164BC, 0xAE5DFF9C02033198},
+ {0xA8530886B54DBDEB, 0xD9F57F830283FDFD},
+ {0xD267CAA862A12D66, 0xD072DF63C324FD7C},
+ {0x8380DEA93DA4BC60, 0x4247CB9E59F71E6E},
+ {0xA46116538D0DEB78, 0x52D9BE85F074E609},
+ {0xCD795BE870516656, 0x67902E276C921F8C},
+ {0x806BD9714632DFF6, 0x00BA1CD8A3DB53B7},
+ {0xA086CFCD97BF97F3, 0x80E8A40ECCD228A5},
+ {0xC8A883C0FDAF7DF0, 0x6122CD128006B2CE},
+ {0xFAD2A4B13D1B5D6C, 0x796B805720085F82},
+ {0x9CC3A6EEC6311A63, 0xCBE3303674053BB1},
+ {0xC3F490AA77BD60FC, 0xBEDBFC4411068A9D},
+ {0xF4F1B4D515ACB93B, 0xEE92FB5515482D45},
+ {0x991711052D8BF3C5, 0x751BDD152D4D1C4B},
+ {0xBF5CD54678EEF0B6, 0xD262D45A78A0635E},
+ {0xEF340A98172AACE4, 0x86FB897116C87C35},
+ {0x9580869F0E7AAC0E, 0xD45D35E6AE3D4DA1},
+ {0xBAE0A846D2195712, 0x8974836059CCA10A},
+ {0xE998D258869FACD7, 0x2BD1A438703FC94C},
+ {0x91FF83775423CC06, 0x7B6306A34627DDD0},
+ {0xB67F6455292CBF08, 0x1A3BC84C17B1D543},
+ {0xE41F3D6A7377EECA, 0x20CABA5F1D9E4A94},
+ {0x8E938662882AF53E, 0x547EB47B7282EE9D},
+ {0xB23867FB2A35B28D, 0xE99E619A4F23AA44},
+ {0xDEC681F9F4C31F31, 0x6405FA00E2EC94D5},
+ {0x8B3C113C38F9F37E, 0xDE83BC408DD3DD05},
+ {0xAE0B158B4738705E, 0x9624AB50B148D446},
+ {0xD98DDAEE19068C76, 0x3BADD624DD9B0958},
+ {0x87F8A8D4CFA417C9, 0xE54CA5D70A80E5D7},
+ {0xA9F6D30A038D1DBC, 0x5E9FCF4CCD211F4D},
+ {0xD47487CC8470652B, 0x7647C32000696720},
+ {0x84C8D4DFD2C63F3B, 0x29ECD9F40041E074},
+ {0xA5FB0A17C777CF09, 0xF468107100525891},
+ {0xCF79CC9DB955C2CC, 0x7182148D4066EEB5},
+ {0x81AC1FE293D599BF, 0xC6F14CD848405531},
+ {0xA21727DB38CB002F, 0xB8ADA00E5A506A7D},
+ {0xCA9CF1D206FDC03B, 0xA6D90811F0E4851D},
+ {0xFD442E4688BD304A, 0x908F4A166D1DA664},
+ {0x9E4A9CEC15763E2E, 0x9A598E4E043287FF},
+ {0xC5DD44271AD3CDBA, 0x40EFF1E1853F29FE},
+ {0xF7549530E188C128, 0xD12BEE59E68EF47D},
+ {0x9A94DD3E8CF578B9, 0x82BB74F8301958CF},
+ {0xC13A148E3032D6E7, 0xE36A52363C1FAF02},
+ {0xF18899B1BC3F8CA1, 0xDC44E6C3CB279AC2},
+ {0x96F5600F15A7B7E5, 0x29AB103A5EF8C0BA},
+ {0xBCB2B812DB11A5DE, 0x7415D448F6B6F0E8},
+ {0xEBDF661791D60F56, 0x111B495B3464AD22},
+ {0x936B9FCEBB25C995, 0xCAB10DD900BEEC35},
+ {0xB84687C269EF3BFB, 0x3D5D514F40EEA743},
+ {0xE65829B3046B0AFA, 0x0CB4A5A3112A5113},
+ {0x8FF71A0FE2C2E6DC, 0x47F0E785EABA72AC},
+ {0xB3F4E093DB73A093, 0x59ED216765690F57},
+ {0xE0F218B8D25088B8, 0x306869C13EC3532D},
+ {0x8C974F7383725573, 0x1E414218C73A13FC},
+ {0xAFBD2350644EEACF, 0xE5D1929EF90898FB},
+ {0xDBAC6C247D62A583, 0xDF45F746B74ABF3A},
+ {0x894BC396CE5DA772, 0x6B8BBA8C328EB784},
+ {0xAB9EB47C81F5114F, 0x066EA92F3F326565},
+ {0xD686619BA27255A2, 0xC80A537B0EFEFEBE},
+ {0x8613FD0145877585, 0xBD06742CE95F5F37},
+ {0xA798FC4196E952E7, 0x2C48113823B73705},
+ {0xD17F3B51FCA3A7A0, 0xF75A15862CA504C6},
+ {0x82EF85133DE648C4, 0x9A984D73DBE722FC},
+ {0xA3AB66580D5FDAF5, 0xC13E60D0D2E0EBBB},
+ {0xCC963FEE10B7D1B3, 0x318DF905079926A9},
+ {0xFFBBCFE994E5C61F, 0xFDF17746497F7053},
+ {0x9FD561F1FD0F9BD3, 0xFEB6EA8BEDEFA634},
+ {0xC7CABA6E7C5382C8, 0xFE64A52EE96B8FC1},
+ {0xF9BD690A1B68637B, 0x3DFDCE7AA3C673B1},
+ {0x9C1661A651213E2D, 0x06BEA10CA65C084F},
+ {0xC31BFA0FE5698DB8, 0x486E494FCFF30A63},
+ {0xF3E2F893DEC3F126, 0x5A89DBA3C3EFCCFB},
+ {0x986DDB5C6B3A76B7, 0xF89629465A75E01D},
+ {0xBE89523386091465, 0xF6BBB397F1135824},
+ {0xEE2BA6C0678B597F, 0x746AA07DED582E2D},
+ {0x94DB483840B717EF, 0xA8C2A44EB4571CDD},
+ {0xBA121A4650E4DDEB, 0x92F34D62616CE414},
+ {0xE896A0D7E51E1566, 0x77B020BAF9C81D18},
+ {0x915E2486EF32CD60, 0x0ACE1474DC1D122F},
+ {0xB5B5ADA8AAFF80B8, 0x0D819992132456BB},
+ {0xE3231912D5BF60E6, 0x10E1FFF697ED6C6A},
+ {0x8DF5EFABC5979C8F, 0xCA8D3FFA1EF463C2},
+ {0xB1736B96B6FD83B3, 0xBD308FF8A6B17CB3},
+ {0xDDD0467C64BCE4A0, 0xAC7CB3F6D05DDBDF},
+ {0x8AA22C0DBEF60EE4, 0x6BCDF07A423AA96C},
+ {0xAD4AB7112EB3929D, 0x86C16C98D2C953C7},
+ {0xD89D64D57A607744, 0xE871C7BF077BA8B8},
+ {0x87625F056C7C4A8B, 0x11471CD764AD4973},
+ {0xA93AF6C6C79B5D2D, 0xD598E40D3DD89BD0},
+ {0xD389B47879823479, 0x4AFF1D108D4EC2C4},
+ {0x843610CB4BF160CB, 0xCEDF722A585139BB},
+ {0xA54394FE1EEDB8FE, 0xC2974EB4EE658829},
+ {0xCE947A3DA6A9273E, 0x733D226229FEEA33},
+ {0x811CCC668829B887, 0x0806357D5A3F5260},
+ {0xA163FF802A3426A8, 0xCA07C2DCB0CF26F8},
+ {0xC9BCFF6034C13052, 0xFC89B393DD02F0B6},
+ {0xFC2C3F3841F17C67, 0xBBAC2078D443ACE3},
+ {0x9D9BA7832936EDC0, 0xD54B944B84AA4C0E},
+ {0xC5029163F384A931, 0x0A9E795E65D4DF12},
+ {0xF64335BCF065D37D, 0x4D4617B5FF4A16D6},
+ {0x99EA0196163FA42E, 0x504BCED1BF8E4E46},
+ {0xC06481FB9BCF8D39, 0xE45EC2862F71E1D7},
+ {0xF07DA27A82C37088, 0x5D767327BB4E5A4D},
+ {0x964E858C91BA2655, 0x3A6A07F8D510F870},
+ {0xBBE226EFB628AFEA, 0x890489F70A55368C},
+ {0xEADAB0ABA3B2DBE5, 0x2B45AC74CCEA842F},
+ {0x92C8AE6B464FC96F, 0x3B0B8BC90012929E},
+ {0xB77ADA0617E3BBCB, 0x09CE6EBB40173745},
+ {0xE55990879DDCAABD, 0xCC420A6A101D0516},
+ {0x8F57FA54C2A9EAB6, 0x9FA946824A12232E},
+ {0xB32DF8E9F3546564, 0x47939822DC96ABFA},
+ {0xDFF9772470297EBD, 0x59787E2B93BC56F8},
+ {0x8BFBEA76C619EF36, 0x57EB4EDB3C55B65B},
+ {0xAEFAE51477A06B03, 0xEDE622920B6B23F2},
+ {0xDAB99E59958885C4, 0xE95FAB368E45ECEE},
+ {0x88B402F7FD75539B, 0x11DBCB0218EBB415},
+ {0xAAE103B5FCD2A881, 0xD652BDC29F26A11A},
+ {0xD59944A37C0752A2, 0x4BE76D3346F04960},
+ {0x857FCAE62D8493A5, 0x6F70A4400C562DDC},
+ {0xA6DFBD9FB8E5B88E, 0xCB4CCD500F6BB953},
+ {0xD097AD07A71F26B2, 0x7E2000A41346A7A8},
+ {0x825ECC24C873782F, 0x8ED400668C0C28C9},
+ {0xA2F67F2DFA90563B, 0x728900802F0F32FB},
+ {0xCBB41EF979346BCA, 0x4F2B40A03AD2FFBA},
+ {0xFEA126B7D78186BC, 0xE2F610C84987BFA9},
+ {0x9F24B832E6B0F436, 0x0DD9CA7D2DF4D7CA},
+ {0xC6EDE63FA05D3143, 0x91503D1C79720DBC},
+ {0xF8A95FCF88747D94, 0x75A44C6397CE912B},
+ {0x9B69DBE1B548CE7C, 0xC986AFBE3EE11ABB},
+ {0xC24452DA229B021B, 0xFBE85BADCE996169},
+ {0xF2D56790AB41C2A2, 0xFAE27299423FB9C4},
+ {0x97C560BA6B0919A5, 0xDCCD879FC967D41B},
+ {0xBDB6B8E905CB600F, 0x5400E987BBC1C921},
+ {0xED246723473E3813, 0x290123E9AAB23B69},
+ {0x9436C0760C86E30B, 0xF9A0B6720AAF6522},
+ {0xB94470938FA89BCE, 0xF808E40E8D5B3E6A},
+ {0xE7958CB87392C2C2, 0xB60B1D1230B20E05},
+ {0x90BD77F3483BB9B9, 0xB1C6F22B5E6F48C3},
+ {0xB4ECD5F01A4AA828, 0x1E38AEB6360B1AF4},
+ {0xE2280B6C20DD5232, 0x25C6DA63C38DE1B1},
+ {0x8D590723948A535F, 0x579C487E5A38AD0F},
+ {0xB0AF48EC79ACE837, 0x2D835A9DF0C6D852},
+ {0xDCDB1B2798182244, 0xF8E431456CF88E66},
+ {0x8A08F0F8BF0F156B, 0x1B8E9ECB641B5900},
+ {0xAC8B2D36EED2DAC5, 0xE272467E3D222F40},
+ {0xD7ADF884AA879177, 0x5B0ED81DCC6ABB10},
+ {0x86CCBB52EA94BAEA, 0x98E947129FC2B4EA},
+ {0xA87FEA27A539E9A5, 0x3F2398D747B36225},
+ {0xD29FE4B18E88640E, 0x8EEC7F0D19A03AAE},
+ {0x83A3EEEEF9153E89, 0x1953CF68300424AD},
+ {0xA48CEAAAB75A8E2B, 0x5FA8C3423C052DD8},
+ {0xCDB02555653131B6, 0x3792F412CB06794E},
+ {0x808E17555F3EBF11, 0xE2BBD88BBEE40BD1},
+ {0xA0B19D2AB70E6ED6, 0x5B6ACEAEAE9D0EC5},
+ {0xC8DE047564D20A8B, 0xF245825A5A445276},
+ {0xFB158592BE068D2E, 0xEED6E2F0F0D56713},
+ {0x9CED737BB6C4183D, 0x55464DD69685606C},
+ {0xC428D05AA4751E4C, 0xAA97E14C3C26B887},
+ {0xF53304714D9265DF, 0xD53DD99F4B3066A9},
+ {0x993FE2C6D07B7FAB, 0xE546A8038EFE402A},
+ {0xBF8FDB78849A5F96, 0xDE98520472BDD034},
+ {0xEF73D256A5C0F77C, 0x963E66858F6D4441},
+ {0x95A8637627989AAD, 0xDDE7001379A44AA9},
+ {0xBB127C53B17EC159, 0x5560C018580D5D53},
+ {0xE9D71B689DDE71AF, 0xAAB8F01E6E10B4A7},
+ {0x9226712162AB070D, 0xCAB3961304CA70E9},
+ {0xB6B00D69BB55C8D1, 0x3D607B97C5FD0D23},
+ {0xE45C10C42A2B3B05, 0x8CB89A7DB77C506B},
+ {0x8EB98A7A9A5B04E3, 0x77F3608E92ADB243},
+ {0xB267ED1940F1C61C, 0x55F038B237591ED4},
+ {0xDF01E85F912E37A3, 0x6B6C46DEC52F6689},
+ {0x8B61313BBABCE2C6, 0x2323AC4B3B3DA016},
+ {0xAE397D8AA96C1B77, 0xABEC975E0A0D081B},
+ {0xD9C7DCED53C72255, 0x96E7BD358C904A22},
+ {0x881CEA14545C7575, 0x7E50D64177DA2E55},
+ {0xAA242499697392D2, 0xDDE50BD1D5D0B9EA},
+ {0xD4AD2DBFC3D07787, 0x955E4EC64B44E865},
+ {0x84EC3C97DA624AB4, 0xBD5AF13BEF0B113F},
+ {0xA6274BBDD0FADD61, 0xECB1AD8AEACDD58F},
+ {0xCFB11EAD453994BA, 0x67DE18EDA5814AF3},
+ {0x81CEB32C4B43FCF4, 0x80EACF948770CED8},
+ {0xA2425FF75E14FC31, 0xA1258379A94D028E},
+ {0xCAD2F7F5359A3B3E, 0x096EE45813A04331},
+ {0xFD87B5F28300CA0D, 0x8BCA9D6E188853FD},
+ {0x9E74D1B791E07E48, 0x775EA264CF55347E},
+ {0xC612062576589DDA, 0x95364AFE032A819E},
+ {0xF79687AED3EEC551, 0x3A83DDBD83F52205},
+ {0x9ABE14CD44753B52, 0xC4926A9672793543},
+ {0xC16D9A0095928A27, 0x75B7053C0F178294},
+ {0xF1C90080BAF72CB1, 0x5324C68B12DD6339},
+ {0x971DA05074DA7BEE, 0xD3F6FC16EBCA5E04},
+ {0xBCE5086492111AEA, 0x88F4BB1CA6BCF585},
+ {0xEC1E4A7DB69561A5, 0x2B31E9E3D06C32E6},
+ {0x9392EE8E921D5D07, 0x3AFF322E62439FD0},
+ {0xB877AA3236A4B449, 0x09BEFEB9FAD487C3},
+ {0xE69594BEC44DE15B, 0x4C2EBE687989A9B4},
+ {0x901D7CF73AB0ACD9, 0x0F9D37014BF60A11},
+ {0xB424DC35095CD80F, 0x538484C19EF38C95},
+ {0xE12E13424BB40E13, 0x2865A5F206B06FBA},
+ {0x8CBCCC096F5088CB, 0xF93F87B7442E45D4},
+ {0xAFEBFF0BCB24AAFE, 0xF78F69A51539D749},
+ {0xDBE6FECEBDEDD5BE, 0xB573440E5A884D1C},
+ {0x89705F4136B4A597, 0x31680A88F8953031},
+ {0xABCC77118461CEFC, 0xFDC20D2B36BA7C3E},
+ {0xD6BF94D5E57A42BC, 0x3D32907604691B4D},
+ {0x8637BD05AF6C69B5, 0xA63F9A49C2C1B110},
+ {0xA7C5AC471B478423, 0x0FCF80DC33721D54},
+ {0xD1B71758E219652B, 0xD3C36113404EA4A9},
+ {0x83126E978D4FDF3B, 0x645A1CAC083126EA},
+ {0xA3D70A3D70A3D70A, 0x3D70A3D70A3D70A4},
+ {0xCCCCCCCCCCCCCCCC, 0xCCCCCCCCCCCCCCCD},
+ {0x8000000000000000, 0x0000000000000000},
+ {0xA000000000000000, 0x0000000000000000},
+ {0xC800000000000000, 0x0000000000000000},
+ {0xFA00000000000000, 0x0000000000000000},
+ {0x9C40000000000000, 0x0000000000000000},
+ {0xC350000000000000, 0x0000000000000000},
+ {0xF424000000000000, 0x0000000000000000},
+ {0x9896800000000000, 0x0000000000000000},
+ {0xBEBC200000000000, 0x0000000000000000},
+ {0xEE6B280000000000, 0x0000000000000000},
+ {0x9502F90000000000, 0x0000000000000000},
+ {0xBA43B74000000000, 0x0000000000000000},
+ {0xE8D4A51000000000, 0x0000000000000000},
+ {0x9184E72A00000000, 0x0000000000000000},
+ {0xB5E620F480000000, 0x0000000000000000},
+ {0xE35FA931A0000000, 0x0000000000000000},
+ {0x8E1BC9BF04000000, 0x0000000000000000},
+ {0xB1A2BC2EC5000000, 0x0000000000000000},
+ {0xDE0B6B3A76400000, 0x0000000000000000},
+ {0x8AC7230489E80000, 0x0000000000000000},
+ {0xAD78EBC5AC620000, 0x0000000000000000},
+ {0xD8D726B7177A8000, 0x0000000000000000},
+ {0x878678326EAC9000, 0x0000000000000000},
+ {0xA968163F0A57B400, 0x0000000000000000},
+ {0xD3C21BCECCEDA100, 0x0000000000000000},
+ {0x84595161401484A0, 0x0000000000000000},
+ {0xA56FA5B99019A5C8, 0x0000000000000000},
+ {0xCECB8F27F4200F3A, 0x0000000000000000},
+ {0x813F3978F8940984, 0x4000000000000000},
+ {0xA18F07D736B90BE5, 0x5000000000000000},
+ {0xC9F2C9CD04674EDE, 0xA400000000000000},
+ {0xFC6F7C4045812296, 0x4D00000000000000},
+ {0x9DC5ADA82B70B59D, 0xF020000000000000},
+ {0xC5371912364CE305, 0x6C28000000000000},
+ {0xF684DF56C3E01BC6, 0xC732000000000000},
+ {0x9A130B963A6C115C, 0x3C7F400000000000},
+ {0xC097CE7BC90715B3, 0x4B9F100000000000},
+ {0xF0BDC21ABB48DB20, 0x1E86D40000000000},
+ {0x96769950B50D88F4, 0x1314448000000000},
+ {0xBC143FA4E250EB31, 0x17D955A000000000},
+ {0xEB194F8E1AE525FD, 0x5DCFAB0800000000},
+ {0x92EFD1B8D0CF37BE, 0x5AA1CAE500000000},
+ {0xB7ABC627050305AD, 0xF14A3D9E40000000},
+ {0xE596B7B0C643C719, 0x6D9CCD05D0000000},
+ {0x8F7E32CE7BEA5C6F, 0xE4820023A2000000},
+ {0xB35DBF821AE4F38B, 0xDDA2802C8A800000},
+ {0xE0352F62A19E306E, 0xD50B2037AD200000},
+ {0x8C213D9DA502DE45, 0x4526F422CC340000},
+ {0xAF298D050E4395D6, 0x9670B12B7F410000},
+ {0xDAF3F04651D47B4C, 0x3C0CDD765F114000},
+ {0x88D8762BF324CD0F, 0xA5880A69FB6AC800},
+ {0xAB0E93B6EFEE0053, 0x8EEA0D047A457A00},
+ {0xD5D238A4ABE98068, 0x72A4904598D6D880},
+ {0x85A36366EB71F041, 0x47A6DA2B7F864750},
+ {0xA70C3C40A64E6C51, 0x999090B65F67D924},
+ {0xD0CF4B50CFE20765, 0xFFF4B4E3F741CF6D},
+ {0x82818F1281ED449F, 0xBFF8F10E7A8921A4},
+ {0xA321F2D7226895C7, 0xAFF72D52192B6A0D},
+ {0xCBEA6F8CEB02BB39, 0x9BF4F8A69F764490},
+ {0xFEE50B7025C36A08, 0x02F236D04753D5B4},
+ {0x9F4F2726179A2245, 0x01D762422C946590},
+ {0xC722F0EF9D80AAD6, 0x424D3AD2B7B97EF5},
+ {0xF8EBAD2B84E0D58B, 0xD2E0898765A7DEB2},
+ {0x9B934C3B330C8577, 0x63CC55F49F88EB2F},
+ {0xC2781F49FFCFA6D5, 0x3CBF6B71C76B25FB},
+ {0xF316271C7FC3908A, 0x8BEF464E3945EF7A},
+ {0x97EDD871CFDA3A56, 0x97758BF0E3CBB5AC},
+ {0xBDE94E8E43D0C8EC, 0x3D52EEED1CBEA317},
+ {0xED63A231D4C4FB27, 0x4CA7AAA863EE4BDD},
+ {0x945E455F24FB1CF8, 0x8FE8CAA93E74EF6A},
+ {0xB975D6B6EE39E436, 0xB3E2FD538E122B44},
+ {0xE7D34C64A9C85D44, 0x60DBBCA87196B616},
+ {0x90E40FBEEA1D3A4A, 0xBC8955E946FE31CD},
+ {0xB51D13AEA4A488DD, 0x6BABAB6398BDBE41},
+ {0xE264589A4DCDAB14, 0xC696963C7EED2DD1},
+ {0x8D7EB76070A08AEC, 0xFC1E1DE5CF543CA2},
+ {0xB0DE65388CC8ADA8, 0x3B25A55F43294BCB},
+ {0xDD15FE86AFFAD912, 0x49EF0EB713F39EBE},
+ {0x8A2DBF142DFCC7AB, 0x6E3569326C784337},
+ {0xACB92ED9397BF996, 0x49C2C37F07965404},
+ {0xD7E77A8F87DAF7FB, 0xDC33745EC97BE906},
+ {0x86F0AC99B4E8DAFD, 0x69A028BB3DED71A3},
+ {0xA8ACD7C0222311BC, 0xC40832EA0D68CE0C},
+ {0xD2D80DB02AABD62B, 0xF50A3FA490C30190},
+ {0x83C7088E1AAB65DB, 0x792667C6DA79E0FA},
+ {0xA4B8CAB1A1563F52, 0x577001B891185938},
+ {0xCDE6FD5E09ABCF26, 0xED4C0226B55E6F86},
+ {0x80B05E5AC60B6178, 0x544F8158315B05B4},
+ {0xA0DC75F1778E39D6, 0x696361AE3DB1C721},
+ {0xC913936DD571C84C, 0x03BC3A19CD1E38E9},
+ {0xFB5878494ACE3A5F, 0x04AB48A04065C723},
+ {0x9D174B2DCEC0E47B, 0x62EB0D64283F9C76},
+ {0xC45D1DF942711D9A, 0x3BA5D0BD324F8394},
+ {0xF5746577930D6500, 0xCA8F44EC7EE36479},
+ {0x9968BF6ABBE85F20, 0x7E998B13CF4E1ECB},
+ {0xBFC2EF456AE276E8, 0x9E3FEDD8C321A67E},
+ {0xEFB3AB16C59B14A2, 0xC5CFE94EF3EA101E},
+ {0x95D04AEE3B80ECE5, 0xBBA1F1D158724A12},
+ {0xBB445DA9CA61281F, 0x2A8A6E45AE8EDC97},
+ {0xEA1575143CF97226, 0xF52D09D71A3293BD},
+ {0x924D692CA61BE758, 0x593C2626705F9C56},
+ {0xB6E0C377CFA2E12E, 0x6F8B2FB00C77836C},
+ {0xE498F455C38B997A, 0x0B6DFB9C0F956447},
+ {0x8EDF98B59A373FEC, 0x4724BD4189BD5EAC},
+ {0xB2977EE300C50FE7, 0x58EDEC91EC2CB657},
+ {0xDF3D5E9BC0F653E1, 0x2F2967B66737E3ED},
+ {0x8B865B215899F46C, 0xBD79E0D20082EE74},
+ {0xAE67F1E9AEC07187, 0xECD8590680A3AA11},
+ {0xDA01EE641A708DE9, 0xE80E6F4820CC9495},
+ {0x884134FE908658B2, 0x3109058D147FDCDD},
+ {0xAA51823E34A7EEDE, 0xBD4B46F0599FD415},
+ {0xD4E5E2CDC1D1EA96, 0x6C9E18AC7007C91A},
+ {0x850FADC09923329E, 0x03E2CF6BC604DDB0},
+ {0xA6539930BF6BFF45, 0x84DB8346B786151C},
+ {0xCFE87F7CEF46FF16, 0xE612641865679A63},
+ {0x81F14FAE158C5F6E, 0x4FCB7E8F3F60C07E},
+ {0xA26DA3999AEF7749, 0xE3BE5E330F38F09D},
+ {0xCB090C8001AB551C, 0x5CADF5BFD3072CC5},
+ {0xFDCB4FA002162A63, 0x73D9732FC7C8F7F6},
+ {0x9E9F11C4014DDA7E, 0x2867E7FDDCDD9AFA},
+ {0xC646D63501A1511D, 0xB281E1FD541501B8},
+ {0xF7D88BC24209A565, 0x1F225A7CA91A4226},
+ {0x9AE757596946075F, 0x3375788DE9B06958},
+ {0xC1A12D2FC3978937, 0x0052D6B1641C83AE},
+ {0xF209787BB47D6B84, 0xC0678C5DBD23A49A},
+ {0x9745EB4D50CE6332, 0xF840B7BA963646E0},
+ {0xBD176620A501FBFF, 0xB650E5A93BC3D898},
+ {0xEC5D3FA8CE427AFF, 0xA3E51F138AB4CEBE},
+ {0x93BA47C980E98CDF, 0xC66F336C36B10137},
+ {0xB8A8D9BBE123F017, 0xB80B0047445D4184},
+ {0xE6D3102AD96CEC1D, 0xA60DC059157491E5},
+ {0x9043EA1AC7E41392, 0x87C89837AD68DB2F},
+ {0xB454E4A179DD1877, 0x29BABE4598C311FB},
+ {0xE16A1DC9D8545E94, 0xF4296DD6FEF3D67A},
+ {0x8CE2529E2734BB1D, 0x1899E4A65F58660C},
+ {0xB01AE745B101E9E4, 0x5EC05DCFF72E7F8F},
+ {0xDC21A1171D42645D, 0x76707543F4FA1F73},
+ {0x899504AE72497EBA, 0x6A06494A791C53A8},
+ {0xABFA45DA0EDBDE69, 0x0487DB9D17636892},
+ {0xD6F8D7509292D603, 0x45A9D2845D3C42B6},
+ {0x865B86925B9BC5C2, 0x0B8A2392BA45A9B2},
+ {0xA7F26836F282B732, 0x8E6CAC7768D7141E},
+ {0xD1EF0244AF2364FF, 0x3207D795430CD926},
+ {0x8335616AED761F1F, 0x7F44E6BD49E807B8},
+ {0xA402B9C5A8D3A6E7, 0x5F16206C9C6209A6},
+ {0xCD036837130890A1, 0x36DBA887C37A8C0F},
+ {0x802221226BE55A64, 0xC2494954DA2C9789},
+ {0xA02AA96B06DEB0FD, 0xF2DB9BAA10B7BD6C},
+ {0xC83553C5C8965D3D, 0x6F92829494E5ACC7},
+ {0xFA42A8B73ABBF48C, 0xCB772339BA1F17F9},
+ {0x9C69A97284B578D7, 0xFF2A760414536EFB},
+ {0xC38413CF25E2D70D, 0xFEF5138519684ABA},
+ {0xF46518C2EF5B8CD1, 0x7EB258665FC25D69},
+ {0x98BF2F79D5993802, 0xEF2F773FFBD97A61},
+ {0xBEEEFB584AFF8603, 0xAAFB550FFACFD8FA},
+ {0xEEAABA2E5DBF6784, 0x95BA2A53F983CF38},
+ {0x952AB45CFA97A0B2, 0xDD945A747BF26183},
+ {0xBA756174393D88DF, 0x94F971119AEEF9E4},
+ {0xE912B9D1478CEB17, 0x7A37CD5601AAB85D},
+ {0x91ABB422CCB812EE, 0xAC62E055C10AB33A},
+ {0xB616A12B7FE617AA, 0x577B986B314D6009},
+ {0xE39C49765FDF9D94, 0xED5A7E85FDA0B80B},
+ {0x8E41ADE9FBEBC27D, 0x14588F13BE847307},
+ {0xB1D219647AE6B31C, 0x596EB2D8AE258FC8},
+ {0xDE469FBD99A05FE3, 0x6FCA5F8ED9AEF3BB},
+ {0x8AEC23D680043BEE, 0x25DE7BB9480D5854},
+ {0xADA72CCC20054AE9, 0xAF561AA79A10AE6A},
+ {0xD910F7FF28069DA4, 0x1B2BA1518094DA04},
+ {0x87AA9AFF79042286, 0x90FB44D2F05D0842},
+ {0xA99541BF57452B28, 0x353A1607AC744A53},
+ {0xD3FA922F2D1675F2, 0x42889B8997915CE8},
+ {0x847C9B5D7C2E09B7, 0x69956135FEBADA11},
+ {0xA59BC234DB398C25, 0x43FAB9837E699095},
+ {0xCF02B2C21207EF2E, 0x94F967E45E03F4BB},
+ {0x8161AFB94B44F57D, 0x1D1BE0EEBAC278F5},
+ {0xA1BA1BA79E1632DC, 0x6462D92A69731732},
+ {0xCA28A291859BBF93, 0x7D7B8F7503CFDCFE},
+ {0xFCB2CB35E702AF78, 0x5CDA735244C3D43E},
+ {0x9DEFBF01B061ADAB, 0x3A0888136AFA64A7},
+ {0xC56BAEC21C7A1916, 0x088AAA1845B8FDD0},
+ {0xF6C69A72A3989F5B, 0x8AAD549E57273D45},
+ {0x9A3C2087A63F6399, 0x36AC54E2F678864B},
+ {0xC0CB28A98FCF3C7F, 0x84576A1BB416A7DD},
+ {0xF0FDF2D3F3C30B9F, 0x656D44A2A11C51D5},
+ {0x969EB7C47859E743, 0x9F644AE5A4B1B325},
+ {0xBC4665B596706114, 0x873D5D9F0DDE1FEE},
+ {0xEB57FF22FC0C7959, 0xA90CB506D155A7EA},
+ {0x9316FF75DD87CBD8, 0x09A7F12442D588F2},
+ {0xB7DCBF5354E9BECE, 0x0C11ED6D538AEB2F},
+ {0xE5D3EF282A242E81, 0x8F1668C8A86DA5FA},
+ {0x8FA475791A569D10, 0xF96E017D694487BC},
+ {0xB38D92D760EC4455, 0x37C981DCC395A9AC},
+ {0xE070F78D3927556A, 0x85BBE253F47B1417},
+ {0x8C469AB843B89562, 0x93956D7478CCEC8E},
+ {0xAF58416654A6BABB, 0x387AC8D1970027B2},
+ {0xDB2E51BFE9D0696A, 0x06997B05FCC0319E},
+ {0x88FCF317F22241E2, 0x441FECE3BDF81F03},
+ {0xAB3C2FDDEEAAD25A, 0xD527E81CAD7626C3},
+ {0xD60B3BD56A5586F1, 0x8A71E223D8D3B074},
+ {0x85C7056562757456, 0xF6872D5667844E49},
+ {0xA738C6BEBB12D16C, 0xB428F8AC016561DB},
+ {0xD106F86E69D785C7, 0xE13336D701BEBA52},
+ {0x82A45B450226B39C, 0xECC0024661173473},
+ {0xA34D721642B06084, 0x27F002D7F95D0190},
+ {0xCC20CE9BD35C78A5, 0x31EC038DF7B441F4},
+ {0xFF290242C83396CE, 0x7E67047175A15271},
+ {0x9F79A169BD203E41, 0x0F0062C6E984D386},
+ {0xC75809C42C684DD1, 0x52C07B78A3E60868},
+ {0xF92E0C3537826145, 0xA7709A56CCDF8A82},
+ {0x9BBCC7A142B17CCB, 0x88A66076400BB691},
+ {0xC2ABF989935DDBFE, 0x6ACFF893D00EA435},
+ {0xF356F7EBF83552FE, 0x0583F6B8C4124D43},
+ {0x98165AF37B2153DE, 0xC3727A337A8B704A},
+ {0xBE1BF1B059E9A8D6, 0x744F18C0592E4C5C},
+ {0xEDA2EE1C7064130C, 0x1162DEF06F79DF73},
+ {0x9485D4D1C63E8BE7, 0x8ADDCB5645AC2BA8},
+ {0xB9A74A0637CE2EE1, 0x6D953E2BD7173692},
+ {0xE8111C87C5C1BA99, 0xC8FA8DB6CCDD0437},
+ {0x910AB1D4DB9914A0, 0x1D9C9892400A22A2},
+ {0xB54D5E4A127F59C8, 0x2503BEB6D00CAB4B},
+ {0xE2A0B5DC971F303A, 0x2E44AE64840FD61D},
+ {0x8DA471A9DE737E24, 0x5CEAECFED289E5D2},
+ {0xB10D8E1456105DAD, 0x7425A83E872C5F47},
+ {0xDD50F1996B947518, 0xD12F124E28F77719},
+ {0x8A5296FFE33CC92F, 0x82BD6B70D99AAA6F},
+ {0xACE73CBFDC0BFB7B, 0x636CC64D1001550B},
+ {0xD8210BEFD30EFA5A, 0x3C47F7E05401AA4E},
+ {0x8714A775E3E95C78, 0x65ACFAEC34810A71},
+ {0xA8D9D1535CE3B396, 0x7F1839A741A14D0D},
+ {0xD31045A8341CA07C, 0x1EDE48111209A050},
+ {0x83EA2B892091E44D, 0x934AED0AAB460432},
+ {0xA4E4B66B68B65D60, 0xF81DA84D5617853F},
+ {0xCE1DE40642E3F4B9, 0x36251260AB9D668E},
+ {0x80D2AE83E9CE78F3, 0xC1D72B7C6B426019},
+ {0xA1075A24E4421730, 0xB24CF65B8612F81F},
+ {0xC94930AE1D529CFC, 0xDEE033F26797B627},
+ {0xFB9B7CD9A4A7443C, 0x169840EF017DA3B1},
+ {0x9D412E0806E88AA5, 0x8E1F289560EE864E},
+ {0xC491798A08A2AD4E, 0xF1A6F2BAB92A27E2},
+ {0xF5B5D7EC8ACB58A2, 0xAE10AF696774B1DB},
+ {0x9991A6F3D6BF1765, 0xACCA6DA1E0A8EF29},
+ {0xBFF610B0CC6EDD3F, 0x17FD090A58D32AF3},
+ {0xEFF394DCFF8A948E, 0xDDFC4B4CEF07F5B0},
+ {0x95F83D0A1FB69CD9, 0x4ABDAF101564F98E},
+ {0xBB764C4CA7A4440F, 0x9D6D1AD41ABE37F1},
+ {0xEA53DF5FD18D5513, 0x84C86189216DC5ED},
+ {0x92746B9BE2F8552C, 0x32FD3CF5B4E49BB4},
+ {0xB7118682DBB66A77, 0x3FBC8C33221DC2A1},
+ {0xE4D5E82392A40515, 0x0FABAF3FEAA5334A},
+ {0x8F05B1163BA6832D, 0x29CB4D87F2A7400E},
+ {0xB2C71D5BCA9023F8, 0x743E20E9EF511012},
+ {0xDF78E4B2BD342CF6, 0x914DA9246B255416},
+ {0x8BAB8EEFB6409C1A, 0x1AD089B6C2F7548E},
+ {0xAE9672ABA3D0C320, 0xA184AC2473B529B1},
+ {0xDA3C0F568CC4F3E8, 0xC9E5D72D90A2741E},
+ {0x8865899617FB1871, 0x7E2FA67C7A658892},
+ {0xAA7EEBFB9DF9DE8D, 0xDDBB901B98FEEAB7},
+ {0xD51EA6FA85785631, 0x552A74227F3EA565},
+ {0x8533285C936B35DE, 0xD53A88958F87275F},
+ {0xA67FF273B8460356, 0x8A892ABAF368F137},
+ {0xD01FEF10A657842C, 0x2D2B7569B0432D85},
+ {0x8213F56A67F6B29B, 0x9C3B29620E29FC73},
+ {0xA298F2C501F45F42, 0x8349F3BA91B47B8F},
+ {0xCB3F2F7642717713, 0x241C70A936219A73},
+ {0xFE0EFB53D30DD4D7, 0xED238CD383AA0110},
+ {0x9EC95D1463E8A506, 0xF4363804324A40AA},
+ {0xC67BB4597CE2CE48, 0xB143C6053EDCD0D5},
+ {0xF81AA16FDC1B81DA, 0xDD94B7868E94050A},
+ {0x9B10A4E5E9913128, 0xCA7CF2B4191C8326},
+ {0xC1D4CE1F63F57D72, 0xFD1C2F611F63A3F0},
+ {0xF24A01A73CF2DCCF, 0xBC633B39673C8CEC},
+ {0x976E41088617CA01, 0xD5BE0503E085D813},
+ {0xBD49D14AA79DBC82, 0x4B2D8644D8A74E18},
+ {0xEC9C459D51852BA2, 0xDDF8E7D60ED1219E},
+ {0x93E1AB8252F33B45, 0xCABB90E5C942B503},
+ {0xB8DA1662E7B00A17, 0x3D6A751F3B936243},
+ {0xE7109BFBA19C0C9D, 0x0CC512670A783AD4},
+ {0x906A617D450187E2, 0x27FB2B80668B24C5},
+ {0xB484F9DC9641E9DA, 0xB1F9F660802DEDF6},
+ {0xE1A63853BBD26451, 0x5E7873F8A0396973},
+ {0x8D07E33455637EB2, 0xDB0B487B6423E1E8},
+ {0xB049DC016ABC5E5F, 0x91CE1A9A3D2CDA62},
+ {0xDC5C5301C56B75F7, 0x7641A140CC7810FB},
+ {0x89B9B3E11B6329BA, 0xA9E904C87FCB0A9D},
+ {0xAC2820D9623BF429, 0x546345FA9FBDCD44},
+ {0xD732290FBACAF133, 0xA97C177947AD4095},
+ {0x867F59A9D4BED6C0, 0x49ED8EABCCCC485D},
+ {0xA81F301449EE8C70, 0x5C68F256BFFF5A74},
+ {0xD226FC195C6A2F8C, 0x73832EEC6FFF3111},
+ {0x83585D8FD9C25DB7, 0xC831FD53C5FF7EAB},
+ {0xA42E74F3D032F525, 0xBA3E7CA8B77F5E55},
+ {0xCD3A1230C43FB26F, 0x28CE1BD2E55F35EB},
+ {0x80444B5E7AA7CF85, 0x7980D163CF5B81B3},
+ {0xA0555E361951C366, 0xD7E105BCC332621F},
+ {0xC86AB5C39FA63440, 0x8DD9472BF3FEFAA7},
+ {0xFA856334878FC150, 0xB14F98F6F0FEB951},
+ {0x9C935E00D4B9D8D2, 0x6ED1BF9A569F33D3},
+ {0xC3B8358109E84F07, 0x0A862F80EC4700C8},
+ {0xF4A642E14C6262C8, 0xCD27BB612758C0FA},
+ {0x98E7E9CCCFBD7DBD, 0x8038D51CB897789C},
+ {0xBF21E44003ACDD2C, 0xE0470A63E6BD56C3},
+ {0xEEEA5D5004981478, 0x1858CCFCE06CAC74},
+ {0x95527A5202DF0CCB, 0x0F37801E0C43EBC8},
+ {0xBAA718E68396CFFD, 0xD30560258F54E6BA},
+ {0xE950DF20247C83FD, 0x47C6B82EF32A2069},
+ {0x91D28B7416CDD27E, 0x4CDC331D57FA5441},
+ {0xB6472E511C81471D, 0xE0133FE4ADF8E952},
+ {0xE3D8F9E563A198E5, 0x58180FDDD97723A6},
+ {0x8E679C2F5E44FF8F, 0x570F09EAA7EA7648},
+ {0xB201833B35D63F73, 0x2CD2CC6551E513DA},
+ {0xDE81E40A034BCF4F, 0xF8077F7EA65E58D1},
+ {0x8B112E86420F6191, 0xFB04AFAF27FAF782},
+ {0xADD57A27D29339F6, 0x79C5DB9AF1F9B563},
+ {0xD94AD8B1C7380874, 0x18375281AE7822BC},
+ {0x87CEC76F1C830548, 0x8F2293910D0B15B5},
+ {0xA9C2794AE3A3C69A, 0xB2EB3875504DDB22},
+ {0xD433179D9C8CB841, 0x5FA60692A46151EB},
+ {0x849FEEC281D7F328, 0xDBC7C41BA6BCD333},
+ {0xA5C7EA73224DEFF3, 0x12B9B522906C0800},
+ {0xCF39E50FEAE16BEF, 0xD768226B34870A00},
+ {0x81842F29F2CCE375, 0xE6A1158300D46640},
+ {0xA1E53AF46F801C53, 0x60495AE3C1097FD0},
+ {0xCA5E89B18B602368, 0x385BB19CB14BDFC4},
+ {0xFCF62C1DEE382C42, 0x46729E03DD9ED7B5},
+ {0x9E19DB92B4E31BA9, 0x6C07A2C26A8346D1},
+ {0xC5A05277621BE293, 0xC7098B7305241885},
+ {0xF70867153AA2DB38, 0xB8CBEE4FC66D1EA7},
+ };
+
+ DRAGONBOX_ASSERT(k >= kMin);
+ DRAGONBOX_ASSERT(k <= kMax);
+ return Pow10[static_cast<uint32_t>(k - kMin)];
+}
+
+// Returns whether value is divisible by 2^e2
+static inline bool MultipleOfPow2(uint64_t value, int32_t e2)
+{
+ DRAGONBOX_ASSERT(e2 >= 0);
+ return e2 < 64 && (value & ((uint64_t{1} << e2) - 1)) == 0;
+}
+
+// Returns whether value is divisible by 5^e5
+static inline bool MultipleOfPow5(uint64_t value, int32_t e5)
+{
+ struct MulCmp {
+ uint64_t mul;
+ uint64_t cmp;
+ };
+
+ static constexpr MulCmp Mod5[] = {
+ {0x0000000000000001u, 0xFFFFFFFFFFFFFFFFu}, // 5^0
+ {0xCCCCCCCCCCCCCCCDu, 0x3333333333333333u}, // 5^1
+ {0x8F5C28F5C28F5C29u, 0x0A3D70A3D70A3D70u}, // 5^2
+ {0x1CAC083126E978D5u, 0x020C49BA5E353F7Cu}, // 5^3
+ {0xD288CE703AFB7E91u, 0x0068DB8BAC710CB2u}, // 5^4
+ {0x5D4E8FB00BCBE61Du, 0x0014F8B588E368F0u}, // 5^5
+ {0x790FB65668C26139u, 0x000431BDE82D7B63u}, // 5^6
+ {0xE5032477AE8D46A5u, 0x0000D6BF94D5E57Au}, // 5^7
+ {0xC767074B22E90E21u, 0x00002AF31DC46118u}, // 5^8
+ {0x8E47CE423A2E9C6Du, 0x0000089705F4136Bu}, // 5^9
+ {0x4FA7F60D3ED61F49u, 0x000001B7CDFD9D7Bu}, // 5^10
+ {0x0FEE64690C913975u, 0x00000057F5FF85E5u}, // 5^11
+ {0x3662E0E1CF503EB1u, 0x000000119799812Du}, // 5^12
+ {0xA47A2CF9F6433FBDu, 0x0000000384B84D09u}, // 5^13
+ {0x54186F653140A659u, 0x00000000B424DC35u}, // 5^14
+ {0x7738164770402145u, 0x0000000024075F3Du}, // 5^15
+ {0xE4A4D1417CD9A041u, 0x000000000734ACA5u}, // 5^16
+ {0xC75429D9E5C5200Du, 0x000000000170EF54u}, // 5^17
+ {0xC1773B91FAC10669u, 0x000000000049C977u}, // 5^18
+ {0x26B172506559CE15u, 0x00000000000EC1E4u}, // 5^19
+ {0xD489E3A9ADDEC2D1u, 0x000000000002F394u}, // 5^20
+ {0x90E860BB892C8D5Du, 0x000000000000971Du}, // 5^21char* buffer, double value
+ {0x502E79BF1B6F4F79u, 0x0000000000001E39u}, // 5^22
+ {0xDCD618596BE30FE5u, 0x000000000000060Bu}, // 5^23
+ {0x2C2AD1AB7BFA3661u, 0x0000000000000135u}, // 5^24
+ };
+
+ DRAGONBOX_ASSERT(e5 >= 0);
+ DRAGONBOX_ASSERT(e5 <= 24);
+ const MulCmp m5 = Mod5[static_cast<unsigned>(e5)];
+
+ return value * m5.mul <= m5.cmp;
+}
+
+namespace {
+struct FloatingDecimal64 {
+ uint64_t significand;
+ int32_t exponent;
+};
+}
+
+static inline FloatingDecimal64 ToDecimal64_asymmetric_interval(int32_t e2)
+{
+ // NB:
+ // accept_lower_endpoint = true
+ // accept_upper_endpoint = true
+
+ static constexpr int32_t P = Double::SignificandSize;
+
+ // Compute k and beta
+ const int32_t minus_k = FloorLog10ThreeQuartersPow2(e2);
+ const int32_t beta_minus_1 = e2 + FloorLog2Pow10(-minus_k);
+
+ // Compute xi and zi
+ const uint64x2 pow10 = ComputePow10(-minus_k);
+
+ const uint64_t lower_endpoint = (pow10.hi - (pow10.hi >> (P + 1))) >> (64 - P - beta_minus_1);
+ const uint64_t upper_endpoint = (pow10.hi + (pow10.hi >> (P + 0))) >> (64 - P - beta_minus_1);
+
+ // If we don't accept the left endpoint (but we do!) or
+ // if the left endpoint is not an integer, increase it
+ const bool lower_endpoint_is_integer = (2 <= e2 && e2 <= 3);
+
+ const uint64_t xi = lower_endpoint + !lower_endpoint_is_integer;
+ const uint64_t zi = upper_endpoint;
+
+ // Try bigger divisor
+ uint64_t q = zi / 10;
+ if (q * 10 >= xi)
+ {
+ return {q, minus_k + 1};
+ }
+
+ // Otherwise, compute the round-up of y
+ q = ((pow10.hi >> (64 - (P + 1) - beta_minus_1)) + 1) / 2;
+
+ // When tie occurs, choose one of them according to the rule
+ if (e2 == -77)
+ {
+ q -= (q % 2 != 0); // Round to even.
+ }
+ else
+ {
+ q += (q < xi);
+ }
+
+ return {q, minus_k};
+}
+
+static inline uint32_t ComputeDelta(uint64x2 pow10, int32_t beta_minus_1)
+{
+ DRAGONBOX_ASSERT(beta_minus_1 >= 0);
+ DRAGONBOX_ASSERT(beta_minus_1 <= 63);
+ return static_cast<uint32_t>(pow10.hi >> (64 - 1 - beta_minus_1));
+}
+
+#if defined(__SIZEOF_INT128__)
+static inline uint64x2 Mul128(uint64_t x, uint64_t y) // 1 mulx
+{
+ __extension__ using uint128_t = unsigned __int128;
+
+ const uint128_t p = uint128_t{x} * y;
+
+ const uint64_t hi = static_cast<uint64_t>(p >> 64);
+ const uint64_t lo = static_cast<uint64_t>(p);
+ return {hi, lo};
+}
+#elif defined(_MSC_VER) && defined(_M_X64)
+static inline uint64x2 Mul128(uint64_t x, uint64_t y)
+{
+ uint64_t hi = 0;
+ uint64_t lo = _umul128(x, y, &hi);
+ return {hi, lo};
+}
+#else
+static inline uint32_t Lo32(uint64_t x)
+{
+ return static_cast<uint32_t>(x);
+}
+
+static inline uint32_t Hi32(uint64_t x)
+{
+ return static_cast<uint32_t>(x >> 32);
+}
+
+static inline uint64x2 Mul128(uint64_t a, uint64_t b)
+{
+ const uint64_t b00 = uint64_t{Lo32(a)} * Lo32(b);
+ const uint64_t b01 = uint64_t{Lo32(a)} * Hi32(b);
+ const uint64_t b10 = uint64_t{Hi32(a)} * Lo32(b);
+ const uint64_t b11 = uint64_t{Hi32(a)} * Hi32(b);
+
+ const uint64_t mid1 = b10 + Hi32(b00);
+ const uint64_t mid2 = b01 + Lo32(mid1);
+
+ const uint64_t hi = b11 + Hi32(mid1) + Hi32(mid2);
+ const uint64_t lo = Lo32(b00) | uint64_t{Lo32(mid2)} << 32;
+ return {hi, lo};
+}
+#endif
+
+// Returns (x * y) / 2^128
+static inline uint64_t MulShift(uint64_t x, uint64x2 y) // 2 mulx
+{
+ uint64x2 p1 = Mul128(x, y.hi);
+ uint64x2 p0 = Mul128(x, y.lo);
+ p1.lo += p0.hi;
+ p1.hi += p1.lo < p0.hi;
+ return p1.hi;
+}
+
+static inline bool MulParity(uint64_t two_f, uint64x2 pow10, int32_t beta_minus_1) // 1 mulx, 1 mul
+{
+ DRAGONBOX_ASSERT(beta_minus_1 >= 1);
+ DRAGONBOX_ASSERT(beta_minus_1 <= 63);
+
+ const uint64_t p01 = two_f * pow10.hi;
+ const uint64_t p10 = Mul128(two_f, pow10.lo).hi;
+ const uint64_t mid = p01 + p10;
+
+ return (mid & (uint64_t{1} << (64 - beta_minus_1))) != 0;
+}
+
+static inline bool IsIntegralEndpoint(uint64_t two_f, int32_t e2, int32_t minus_k)
+{
+ if (e2 < -2)
+ return false;
+ if (e2 <= 9)
+ return true;
+ if (e2 <= 86)
+ return MultipleOfPow5(two_f, minus_k);
+
+ return false;
+}
+
+static inline bool IsIntegralMidpoint(uint64_t two_f, int32_t e2, int32_t minus_k)
+{
+ if (e2 < -4)
+ return MultipleOfPow2(two_f, minus_k - e2 + 1);
+ if (e2 <= 9)
+ return true;
+ if (e2 <= 86)
+ return MultipleOfPow5(two_f, minus_k);
+
+ return false;
+}
+
+static inline FloatingDecimal64 ToDecimal64(const uint64_t ieee_significand, const uint64_t ieee_exponent)
+{
+ static constexpr int32_t Kappa = 2;
+ static constexpr uint32_t BigDivisor = 1000; // 10^(kappa + 1)
+ static constexpr uint32_t SmallDivisor = 100; // 10^(kappa)
+
+ //
+ // Step 1:
+ // integer promotion & Schubfach multiplier calculation.
+ //
+
+ uint64_t m2;
+ int32_t e2;
+ if (ieee_exponent != 0)
+ {
+ m2 = Double::HiddenBit | ieee_significand;
+ e2 = static_cast<int32_t>(ieee_exponent) - Double::ExponentBias;
+
+ if /*unlikely*/ (0 <= -e2 && -e2 < Double::SignificandSize && MultipleOfPow2(m2, -e2))
+ {
+ // Small integer.
+ return {m2 >> -e2, 0};
+ }
+
+ if /*unlikely*/ (ieee_significand == 0 && ieee_exponent > 1)
+ {
+ // Shorter interval case; proceed like Schubfach.
+ return ToDecimal64_asymmetric_interval(e2);
+ }
+ }
+ else
+ {
+ // Subnormal case; interval is always regular.
+ m2 = ieee_significand;
+ e2 = 1 - Double::ExponentBias;
+ }
+
+ const bool is_even = (m2 % 2 == 0);
+ const bool accept_lower = is_even;
+ const bool accept_upper = is_even;
+
+ // Compute k and beta.
+ const int32_t minus_k = FloorLog10Pow2(e2) - Kappa;
+ const int32_t beta_minus_1 = e2 + FloorLog2Pow10(-minus_k);
+ DRAGONBOX_ASSERT(beta_minus_1 >= 6);
+ DRAGONBOX_ASSERT(beta_minus_1 <= 9);
+
+ const uint64x2 pow10 = ComputePow10(-minus_k);
+
+ // Compute delta
+ // 10^kappa <= delta < 10^(kappa + 1)
+ // 100 <= delta < 1000
+ const uint32_t delta = ComputeDelta(pow10, beta_minus_1);
+ DRAGONBOX_ASSERT(delta >= SmallDivisor);
+ DRAGONBOX_ASSERT(delta < BigDivisor );
+
+ const uint64_t two_fl = 2 * m2 - 1;
+ const uint64_t two_fc = 2 * m2;
+ const uint64_t two_fr = 2 * m2 + 1; // (54 bits)
+
+ // Compute zi
+ // (54 + 9 = 63 bits)
+ const uint64_t zi = MulShift(two_fr << beta_minus_1, pow10); // 2 mulx
+
+ //
+ // Step 2:
+ // Try larger divisor.
+ //
+
+ uint64_t q = zi / BigDivisor;
+// uint64_t q = Mul128(zi, 0x83126E978D4FDF3Cu).hi >> 9; // 1 mulx
+ uint32_t r = static_cast<uint32_t>(zi) - BigDivisor * static_cast<uint32_t>(q); // r = zi % BigDivisor
+ // 0 <= r < 1000
+
+ if /*likely ~50% ?!*/ (r < delta)
+ {
+ // Exclude the right endpoint if necessary
+ if /*likely*/ (r != 0 || accept_upper || !IsIntegralEndpoint(two_fr, e2, minus_k))
+ {
+ return {q, minus_k + Kappa + 1};
+ }
+
+ DRAGONBOX_ASSERT(q != 0);
+ --q;
+ r = BigDivisor;
+ }
+ else if /*unlikely*/ (r == delta)
+ {
+ // Compare fractional parts.
+ // Check conditions in the order different from the paper
+ // to take advantage of short-circuiting
+ if ((accept_lower && IsIntegralEndpoint(two_fl, e2, minus_k)) || MulParity(two_fl, pow10, beta_minus_1)) // 1 mulx, 1 mul
+ {
+ return {q, minus_k + Kappa + 1};
+ }
+ }
+ else /*likely ~50% ?!*/ // (r > deltai)
+ {
+ }
+
+ //
+ // Step 3:
+ // Find the significand with the smaller divisor
+ //
+
+ q *= 10; // 1 hmul
+
+ // 0 <= r <= 1000
+
+ const uint32_t dist = r - (delta / 2) + (SmallDivisor / 2);
+
+ const uint32_t dist_q = dist / 100; // 1 mul
+// const uint32_t dist_r = dist % 100;
+ q += dist_q;
+
+// if /*likely*/ (dist_r == 0)
+ if /*likely*/ (dist == dist_q * 100) // 1 mul32
+ {
+// const bool approx_y_parity = ((dist ^ (SmallDivisor / 2)) & 1) != 0;
+ const bool approx_y_parity = (dist & 1) != 0;
+
+ // Check z^(f) >= epsilon^(f)
+ // We have either yi == zi - epsiloni or yi == (zi - epsiloni) - 1,
+ // where yi == zi - epsiloni if and only if z^(f) >= epsilon^(f)
+ // Since there are only 2 possibilities, we only need to care about the
+ // parity. Also, zi and r should have the same parity since the divisor
+ // is an even number
+ if /*likely*/ (MulParity(two_fc, pow10, beta_minus_1) != approx_y_parity) // 1 mulx, 1 mul
+ {
+ --q;
+ }
+ // If z^(f) >= epsilon^(f), we might have a tie
+ // when z^(f) == epsilon^(f), or equivalently, when y is an integer
+ else if (q % 2 != 0 && IsIntegralMidpoint(two_fc, e2, minus_k))
+ {
+ --q;
+ }
+ }
+
+ return {q, minus_k + Kappa};
+}
+
+//==================================================================================================
+// ToChars
+//==================================================================================================
+
+static inline void Utoa_2Digits(char* buf, uint32_t digits)
+{
+ static constexpr char Digits100[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',
+ };
+
+ DRAGONBOX_ASSERT(digits <= 99);
+ std::memcpy(buf, &Digits100[2 * digits], 2 * sizeof(char));
+}
+
+static inline int32_t TrailingZeros_2Digits(uint32_t digits)
+{
+ static constexpr int8_t TrailingZeros100[100] = {
+ 2, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ };
+
+ DRAGONBOX_ASSERT(digits <= 99);
+ return TrailingZeros100[digits];
+}
+
+static inline int32_t Utoa_8Digits_skip_trailing_zeros(char* buf, uint32_t digits)
+{
+ DRAGONBOX_ASSERT(digits >= 1);
+ DRAGONBOX_ASSERT(digits <= 99999999);
+
+ const uint32_t q = digits / 10000;
+ const uint32_t r = digits % 10000;
+
+ const uint32_t qH = q / 100;
+ const uint32_t qL = q % 100;
+ Utoa_2Digits(buf + 0, qH);
+ Utoa_2Digits(buf + 2, qL);
+
+ if (r == 0)
+ {
+ return TrailingZeros_2Digits(qL == 0 ? qH : qL) + (qL == 0 ? 6 : 4);
+ }
+ else
+ {
+ const uint32_t rH = r / 100;
+ const uint32_t rL = r % 100;
+ Utoa_2Digits(buf + 4, rH);
+ Utoa_2Digits(buf + 6, rL);
+
+ return TrailingZeros_2Digits(rL == 0 ? rH : rL) + (rL == 0 ? 2 : 0);
+ }
+}
+
+static inline int32_t PrintDecimalDigitsBackwards(char* buf, uint64_t output64)
+{
+ int32_t tz = 0; // number of trailing zeros removed.
+ int32_t nd = 0; // number of decimal digits processed.
+
+ // At most 17 digits remaining
+
+ if (output64 >= 100000000)
+ {
+ const uint64_t q = output64 / 100000000;
+ const uint32_t r = static_cast<uint32_t>(output64 % 100000000);
+ output64 = q;
+ buf -= 8;
+ if (r != 0)
+ {
+ tz = Utoa_8Digits_skip_trailing_zeros(buf, r);
+ DRAGONBOX_ASSERT(tz >= 0);
+ DRAGONBOX_ASSERT(tz <= 7);
+ }
+ else
+ {
+ tz = 8;
+ }
+ nd = 8;
+ }
+
+ // At most 9 digits remaining.
+ DRAGONBOX_ASSERT(output64 <= UINT32_MAX);
+ uint32_t output = static_cast<uint32_t>(output64);
+
+ if (output >= 10000)
+ {
+ const uint32_t q = output / 10000;
+ const uint32_t r = output % 10000;
+ output = q;
+ buf -= 4;
+ if (r != 0)
+ {
+ const uint32_t rH = r / 100;
+ const uint32_t rL = r % 100;
+ Utoa_2Digits(buf + 0, rH);
+ Utoa_2Digits(buf + 2, rL);
+ if (tz == nd)
+ {
+ tz += TrailingZeros_2Digits(rL == 0 ? rH : rL) + (rL == 0 ? 2 : 0);
+ }
+ }
+ else
+ {
+ if (tz == nd)
+ tz += 4;
+ else
+ std::memset(buf, '0', 4); // (actually not required...)
+ }
+ nd += 4;
+ }
+
+ // At most 5 digits remaining.
+
+ if (output >= 100)
+ {
+ const uint32_t q = output / 100;
+ const uint32_t r = output % 100;
+ output = q;
+ buf -= 2;
+ Utoa_2Digits(buf, r);
+ if (tz == nd)
+ {
+ tz += TrailingZeros_2Digits(r);
+ }
+ nd += 2;
+
+ if (output >= 100)
+ {
+ const uint32_t q = output / 100;
+ const uint32_t r = output % 100;
+ output = q;
+ buf -= 2;
+ Utoa_2Digits(buf, r);
+ if (tz == nd)
+ {
+ tz += TrailingZeros_2Digits(r);
+ }
+ nd += 2;
+ }
+ }
+
+ // At most 2 digits remaining.
+
+ DRAGONBOX_ASSERT(output >= 1);
+ DRAGONBOX_ASSERT(output <= 99);
+
+ if (output >= 10)
+ {
+ const uint32_t q = output;
+ buf -= 2;
+ Utoa_2Digits(buf, q);
+ if (tz == nd)
+ {
+ tz += TrailingZeros_2Digits(q);
+ }
+// nd += 2;
+ }
+ else
+ {
+ const uint32_t q = output;
+ DRAGONBOX_ASSERT(q >= 1);
+ DRAGONBOX_ASSERT(q <= 9);
+ *--buf = static_cast<char>('0' + q);
+ }
+
+ return tz;
+}
+
+static inline int32_t DecimalLength(uint64_t v)
+{
+ DRAGONBOX_ASSERT(v >= 1);
+ DRAGONBOX_ASSERT(v <= 99999999999999999ull);
+
+ if (static_cast<uint32_t>(v >> 32) != 0)
+ {
+ if (v >= 10000000000000000ull) { return 17; }
+ if (v >= 1000000000000000ull) { return 16; }
+ if (v >= 100000000000000ull) { return 15; }
+ if (v >= 10000000000000ull) { return 14; }
+ if (v >= 1000000000000ull) { return 13; }
+ if (v >= 100000000000ull) { return 12; }
+ if (v >= 10000000000ull) { return 11; }
+ return 10;
+ }
+
+ const uint32_t v32 = static_cast<uint32_t>(v);
+ if (v32 >= 1000000000u) { return 10; }
+ if (v32 >= 100000000u) { return 9; }
+ if (v32 >= 10000000u) { return 8; }
+ if (v32 >= 1000000u) { return 7; }
+ if (v32 >= 100000u) { return 6; }
+ if (v32 >= 10000u) { return 5; }
+ if (v32 >= 1000u) { return 4; }
+ if (v32 >= 100u) { return 3; }
+ if (v32 >= 10u) { return 2; }
+ return 1;
+}
+
+static inline char* FormatDigits(char* buffer, uint64_t digits, int32_t decimal_exponent, bool force_trailing_dot_zero = false)
+{
+ static constexpr int32_t MinFixedDecimalPoint = -6;
+ static constexpr int32_t MaxFixedDecimalPoint = 17;
+ static_assert(MinFixedDecimalPoint <= -1, "internal error");
+ static_assert(MaxFixedDecimalPoint >= 17, "internal error");
+
+ DRAGONBOX_ASSERT(digits >= 1);
+ DRAGONBOX_ASSERT(digits <= 99999999999999999ull);
+ DRAGONBOX_ASSERT(decimal_exponent >= -999);
+ DRAGONBOX_ASSERT(decimal_exponent <= 999);
+
+ int32_t num_digits = DecimalLength(digits);
+ const int32_t decimal_point = num_digits + decimal_exponent;
+
+ const bool use_fixed = MinFixedDecimalPoint <= decimal_point && decimal_point <= MaxFixedDecimalPoint;
+
+ // Prepare the buffer.
+ // Avoid calling memset/memcpy with variable arguments below...
+
+ std::memset(buffer + 0, '0', 16);
+ std::memset(buffer + 16, '0', 16);
+ static_assert(MinFixedDecimalPoint >= -30, "internal error");
+ static_assert(MaxFixedDecimalPoint <= 32, "internal error");
+
+ int32_t decimal_digits_position;
+ if (use_fixed)
+ {
+ if (decimal_point <= 0)
+ {
+ // 0.[000]digits
+ decimal_digits_position = 2 - decimal_point;
+ }
+ else
+ {
+ // dig.its
+ // digits[000]
+ decimal_digits_position = 0;
+ }
+ }
+ else
+ {
+ // dE+123 or d.igitsE+123
+ decimal_digits_position = 1;
+ }
+
+ char* digits_end = buffer + decimal_digits_position + num_digits;
+
+ const int32_t tz = PrintDecimalDigitsBackwards(digits_end, digits);
+ digits_end -= tz;
+ num_digits -= tz;
+// decimal_exponent += tz; // => decimal_point unchanged.
+
+ if (use_fixed)
+ {
+ if (decimal_point <= 0)
+ {
+ // 0.[000]digits
+ buffer[1] = '.';
+ buffer = digits_end;
+ }
+ else if (decimal_point < num_digits)
+ {
+ // dig.its
+#if defined(_MSC_VER) && !defined(__clang__)
+ // VC does not inline the memmove call below. (Even if compiled with /arch:AVX2.)
+ // However, memcpy will be inlined.
+ uint8_t tmp[16];
+ char* const src = buffer + decimal_point;
+ char* const dst = src + 1;
+ std::memcpy(tmp, src, 16);
+ std::memcpy(dst, tmp, 16);
+#else
+ std::memmove(buffer + decimal_point + 1, buffer + decimal_point, 16);
+#endif
+ buffer[decimal_point] = '.';
+ buffer = digits_end + 1;
+ }
+ else
+ {
+ // digits[000]
+ buffer += decimal_point;
+ if (force_trailing_dot_zero)
+ {
+ std::memcpy(buffer, ".0", 2);
+ buffer += 2;
+ }
+ }
+ }
+ else
+ {
+ // Copy the first digit one place to the left.
+ buffer[0] = buffer[1];
+ if (num_digits == 1)
+ {
+ // dE+123
+ ++buffer;
+ }
+ else
+ {
+ // d.igitsE+123
+ buffer[1] = '.';
+ buffer = digits_end;
+ }
+
+ const int32_t scientific_exponent = decimal_point - 1;
+// SF_ASSERT(scientific_exponent != 0);
+
+ std::memcpy(buffer, scientific_exponent < 0 ? "e-" : "e+", 2);
+ buffer += 2;
+
+ const uint32_t k = static_cast<uint32_t>(scientific_exponent < 0 ? -scientific_exponent : scientific_exponent);
+ if (k < 10)
+ {
+ *buffer++ = static_cast<char>('0' + k);
+ }
+ else if (k < 100)
+ {
+ Utoa_2Digits(buffer, k);
+ buffer += 2;
+ }
+ else
+ {
+ const uint32_t q = k / 100;
+ const uint32_t r = k % 100;
+ *buffer++ = static_cast<char>('0' + q);
+ Utoa_2Digits(buffer, r);
+ buffer += 2;
+ }
+ }
+
+ return buffer;
+}
+
+static inline char* ToChars(char* buffer, double value, bool force_trailing_dot_zero = false)
+{
+ const Double v(value);
+
+ const uint64_t significand = v.PhysicalSignificand();
+ const uint64_t exponent = v.PhysicalExponent();
+
+// if (exponent != Double::MaxIeeeExponent) // [[likely]]
+// {
+// // Finite
+
+ buffer[0] = '-';
+ buffer += v.SignBit();
+
+// if (exponent != 0 || significand != 0) // [[likely]]
+// {
+// // != 0
+//
+ const auto dec = ToDecimal64(significand, exponent);
+ return FormatDigits(buffer, dec.significand, dec.exponent, force_trailing_dot_zero);
+// }
+// else
+// {
+// std::memcpy(buffer, "0.0 ", 4);
+// buffer += force_trailing_dot_zero ? 3 : 1;
+// return buffer;
+// }
+// }
+//
+// if (significand == 0)
+// {
+// buffer[0] = '-';
+// buffer += v.SignBit();
+//
+// std::memcpy(buffer, "inf ", 4);
+// return buffer + 3;
+// }
+// else
+// {
+// std::memcpy(buffer, "nan ", 4);
+// return buffer + 3;
+// }
+}
+
+//==================================================================================================
+//
+//==================================================================================================
+
+char* Dtoa(char* buffer, double value)
+{
+ return ToChars(buffer, value, true);
+}
+
+} // namespace
+} // dragonbox
