This is a mostly cleaned-up version of the test patch I posted
previously for floating-point output using the Ryu algorithm.
Upstream source: github.com/ulfjack/ryu/ryu at commit 795c8b57a
>From the upstream, I've taken only specific files which are
Boost-licensed, removed code not of interest to us, removed C99-isms,
applied project style for things like type names and use of INT64CONST,
removed some ad-hoc configuration #ifs in favour of using values
established by pg_config.h, and ran the whole thing through pgindent and
fixed up the resulting wreckage.
On top of that I made these functional changes:
1. Added an alternative fixed-point output format so that values with
exponents not less than -4 and less than the default precision for the
type are formatted in fixed-point, as sprintf does.
2. Exponents now always have a sign and at least two digits, also as per
sprintf formatting rules.
The fixed-point output hasn't been micro-optimized to the same extent as
the rest of the code, and there is a measurable performance effect - but
it's not that significant compared to the speedup over the existing code.
As for the extent of that speedup: in my tests, float8 output is now as
fast or marginally faster than bigint output, and roughly one order of
magnitude faster than the existing float8 output.
This version of the patch continues to use extra_float_digits to select
whether Ryu output is used - but I've also changed the default, so that
Ryu is used unless you explicitly set extra_float_digits to 0 or less.
This does mean that at the moment, about 13 regression tests fail on
this patch due to the higher precision of float output. I have
intentionally not yet adjusted those results, pending discussion.
--
Andrew (irc:RhodiumToad)
diff --git a/src/backend/utils/adt/float.c b/src/backend/utils/adt/float.c
index cf9327f885..24d41c2e89 100644
--- a/src/backend/utils/adt/float.c
+++ b/src/backend/utils/adt/float.c
@@ -21,6 +21,7 @@
#include "catalog/pg_type.h"
#include "common/int.h"
+#include "common/ryu.h"
#include "libpq/pqformat.h"
#include "utils/array.h"
#include "utils/float.h"
@@ -29,7 +30,7 @@
/* Configurable GUC parameter */
-int extra_float_digits = 0; /* Added to DBL_DIG or FLT_DIG */
+int extra_float_digits = 1; /* Added to DBL_DIG or FLT_DIG */
/* Cached constants for degree-based trig functions */
static bool degree_consts_set = false;
@@ -246,6 +247,12 @@ float4out(PG_FUNCTION_ARGS)
char *ascii = (char *) palloc(32);
int ndig = FLT_DIG + extra_float_digits;
+ if (extra_float_digits > 0)
+ {
+ ryu_f2s_buffered(num, ascii);
+ PG_RETURN_CSTRING(ascii);
+ }
+
(void) pg_strfromd(ascii, 32, ndig, num);
PG_RETURN_CSTRING(ascii);
}
@@ -462,6 +469,12 @@ float8out_internal(double num)
char *ascii = (char *) palloc(32);
int ndig = DBL_DIG + extra_float_digits;
+ if (extra_float_digits > 0)
+ {
+ ryu_d2s_buffered(num, ascii);
+ return ascii;
+ }
+
(void) pg_strfromd(ascii, 32, ndig, num);
return ascii;
}
diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c
index 6fe1939881..6e223335bc 100644
--- a/src/backend/utils/misc/guc.c
+++ b/src/backend/utils/misc/guc.c
@@ -2631,11 +2631,12 @@ static struct config_int ConfigureNamesInt[] =
{"extra_float_digits", PGC_USERSET, CLIENT_CONN_LOCALE,
gettext_noop("Sets the number of digits displayed for floating-point values."),
gettext_noop("This affects real, double precision, and geometric data types. "
- "The parameter value is added to the standard number of digits "
- "(FLT_DIG or DBL_DIG as appropriate).")
+ "A zero or negative parameter value is added to the standard "
+ "number of digits (FLT_DIG or DBL_DIG as appropriate). "
+ "Any value greater than zero selects round-trip-safe output.")
},
&extra_float_digits,
- 0, -15, 3,
+ 1, -15, 3,
NULL, NULL, NULL
},
diff --git a/src/common/Makefile b/src/common/Makefile
index ec8139f014..ae89dd8c5e 100644
--- a/src/common/Makefile
+++ b/src/common/Makefile
@@ -44,8 +44,8 @@ override CPPFLAGS += -DVAL_LIBS="\"$(LIBS)\""
override CPPFLAGS := -DFRONTEND $(CPPFLAGS)
LIBS += $(PTHREAD_LIBS)
-OBJS_COMMON = base64.o config_info.o controldata_utils.o exec.o file_perm.o \
- ip.o keywords.o link-canary.o md5.o pg_lzcompress.o \
+OBJS_COMMON = base64.o config_info.o controldata_utils.o d2s.o exec.o f2s.o \
+ file_perm.o ip.o keywords.o link-canary.o md5.o pg_lzcompress.o \
pgfnames.o psprintf.o relpath.o \
rmtree.o saslprep.o scram-common.o string.o unicode_norm.o \
username.o wait_error.o
diff --git a/src/common/d2s.c b/src/common/d2s.c
new file mode 100644
index 0000000000..e7d7f2a14c
--- /dev/null
+++ b/src/common/d2s.c
@@ -0,0 +1,974 @@
+/*---------------------------------------------------------------------------
+ *
+ * Ryu floating-point output for double precision.
+ *
+ * Portions Copyright (c) 2018, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ * src/common/d2s.c
+ *
+ * This is a modification of code taken from github.com/ulfjack/ryu under the
+ * terms of the Boost license (not the Apache license). The original copyright
+ * notice follows:
+ *
+ * Copyright 2018 Ulf Adams
+ *
+ * The contents of this file may be used under the terms of the Apache
+ * License, Version 2.0.
+ *
+ * (See accompanying file LICENSE-Apache or copy at
+ * http://www.apache.org/licenses/LICENSE-2.0)
+ *
+ * Alternatively, the contents of this file may be used under the terms of the
+ * Boost Software License, Version 1.0.
+ *
+ * (See accompanying file LICENSE-Boost or copy at
+ * https://www.boost.org/LICENSE_1_0.txt)
+ *
+ * Unless required by applicable law or agreed to in writing, this software is
+ * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.
+ *
+ *---------------------------------------------------------------------------
+ */
+
+/*
+ * Runtime compiler options:
+ *
+ * -DRYU_ONLY_64_BIT_OPS Avoid using uint128 or 64-bit intrinsics. Slower,
+ * depending on your compiler.
+ */
+
+#ifndef FRONTEND
+#include "postgres.h"
+#else
+#include "postgres_fe.h"
+#endif
+
+#include "common/ryu.h"
+
+/*
+ * For consistency, we use 128-bit types if and only if the rest of PG also
+ * does, even though we could use them here without worrying about the
+ * alignment concerns that apply elsewhere.
+ */
+#if !defined(HAVE_INT128) && defined(_MSC_VER) \
+ && !defined(RYU_ONLY_64_BIT_OPS) && defined(_M_X64)
+#define HAS_64_BIT_INTRINSICS
+#endif
+
+#include "ryu_common.h"
+#include "digit_table.h"
+#include "d2s_full_table.h"
+#include "d2s_intrinsics.h"
+
+#define DOUBLE_MANTISSA_BITS 52
+#define DOUBLE_EXPONENT_BITS 11
+#define DOUBLE_BIAS 1023
+
+#define DOUBLE_POW5_INV_BITCOUNT 122
+#define DOUBLE_POW5_BITCOUNT 121
+
+
+static inline uint32
+pow5Factor(uint64 value)
+{
+ uint32 count = 0;
+
+ for (;;)
+ {
+ uint64 q;
+ uint32 r;
+
+ Assert(value != 0);
+
+ q = div5(value);
+ r = (uint32) (value - 5 * q);
+
+ if (r != 0)
+ break;
+
+ value = q;
+ ++count;
+ }
+ return count;
+}
+
+/* Returns true if value is divisible by 5^p. */
+static inline bool
+multipleOfPowerOf5(const uint64 value, const uint32 p)
+{
+ /*
+ * I tried a case distinction on p, but there was no performance
+ * difference.
+ */
+ return pow5Factor(value) >= p;
+}
+
+/* Returns true if value is divisible by 2^p. */
+static inline bool
+multipleOfPowerOf2(const uint64 value, const uint32 p)
+{
+ /* return __builtin_ctzll(value) >= p; */
+ return (value & ((1ull << p) - 1)) == 0;
+}
+
+/*
+ * We need a 64x128-bit multiplication and a subsequent 128-bit shift.
+ *
+ * Multiplication:
+ *
+ * The 64-bit factor is variable and passed in, the 128-bit factor comes
+ * from a lookup table. We know that the 64-bit factor only has 55
+ * significant bits (i.e., the 9 topmost bits are zeros). The 128-bit
+ * factor only has 124 significant bits (i.e., the 4 topmost bits are
+ * zeros).
+ *
+ * Shift:
+ *
+ * In principle, the multiplication result requires 55 + 124 = 179 bits to
+ * represent. However, we then shift this value to the right by j, which is
+ * at least j >= 115, so the result is guaranteed to fit into 179 - 115 =
+ * 64 bits. This means that we only need the topmost 64 significant bits of
+ * the 64x128-bit multiplication.
+ *
+ * There are several ways to do this:
+ *
+ * 1. Best case: the compiler exposes a 128-bit type.
+ * We perform two 64x64-bit multiplications, add the higher 64 bits of the
+ * lower result to the higher result, and shift by j - 64 bits.
+ *
+ * We explicitly cast from 64-bit to 128-bit, so the compiler can tell
+ * that these are only 64-bit inputs, and can map these to the best
+ * possible sequence of assembly instructions. x86-64 machines happen to
+ * have matching assembly instructions for 64x64-bit multiplications and
+ * 128-bit shifts.
+ *
+ * 2. Second best case: the compiler exposes intrinsics for the x86-64
+ * assembly instructions mentioned in 1.
+ *
+ * 3. We only have 64x64 bit instructions that return the lower 64 bits of
+ * the result, i.e., we have to use plain C.
+ *
+ * Our inputs are less than the full width, so we have three options:
+ * a. Ignore this fact and just implement the intrinsics manually.
+ * b. Split both into 31-bit pieces, which guarantees no internal
+ * overflow, but requires extra work upfront (unless we change the
+ * lookup table).
+ * c. Split only the first factor into 31-bit pieces, which also
+ * guarantees no internal overflow, but requires extra work since the
+ * intermediate results are not perfectly aligned.
+ */
+#if defined(HAVE_UINT128)
+
+/* Best case: use 128-bit type. */
+static inline uint64
+mulShift(const uint64 m, const uint64 *const mul, const int32 j)
+{
+ const uint128 b0 = ((uint128) m) * mul[0];
+ const uint128 b2 = ((uint128) m) * mul[1];
+
+ return (uint64) (((b0 >> 64) + b2) >> (j - 64));
+}
+
+static inline uint64
+mulShiftAll(const uint64 m, const uint64 *const mul, const int32 j,
+ uint64 *const vp, uint64 *const vm, const uint32 mmShift)
+{
+/* m <<= 2; */
+/* uint128 b0 = ((uint128) m) * mul[0]; // 0 */
+/* uint128 b2 = ((uint128) m) * mul[1]; // 64 */
+/* */
+/* uint128 hi = (b0 >> 64) + b2; */
+/* uint128 lo = b0 & 0xffffffffffffffffull; */
+/* uint128 factor = (((uint128) mul[1]) << 64) + mul[0]; */
+/* uint128 vpLo = lo + (factor << 1); */
+/* *vp = (uint64) ((hi + (vpLo >> 64)) >> (j - 64)); */
+/* uint128 vmLo = lo - (factor << mmShift); */
+/* *vm = (uint64) ((hi + (vmLo >> 64) - (((uint128) 1ull) << 64)) >> (j - 64)); */
+/* return (uint64) (hi >> (j - 64)); */
+ *vp = mulShift(4 * m + 2, mul, j);
+ *vm = mulShift(4 * m - 1 - mmShift, mul, j);
+ return mulShift(4 * m, mul, j);
+}
+
+#elif defined(HAS_64_BIT_INTRINSICS)
+
+static inline uint64
+mulShift(const uint64 m, const uint64 *const mul, const int32 j)
+{
+ /* m is maximum 55 bits */
+ uint64 high1;
+
+ /* 128 */
+ const uint64 low1 = umul128(m, mul[1], &high1);
+
+ /* 64 */
+ uint64 high0;
+ const uint64 sum;
+
+ /* 64 */
+ umul128(m, mul[0], &high0);
+ /* 0 */
+ sum = high0 + low1;
+
+ if (sum < high0)
+ {
+ ++high1;
+ /* overflow into high1 */
+ }
+ return shiftright128(sum, high1, j - 64);
+}
+
+static inline uint64
+mulShiftAll(const uint64 m, const uint64 *const mul, const int32 j,
+ uint64 *const vp, uint64 *const vm, const uint32 mmShift)
+{
+ *vp = mulShift(4 * m + 2, mul, j);
+ *vm = mulShift(4 * m - 1 - mmShift, mul, j);
+ return mulShift(4 * m, mul, j);
+}
+
+#else /* // !defined(HAVE_UINT128) &&
+ * !defined(HAS_64_BIT_INTRINSICS) */
+
+static inline uint64
+mulShiftAll(uint64 m, const uint64 *const mul, const int32 j,
+ uint64 *const vp, uint64 *const vm, const uint32 mmShift)
+{
+ m <<= 1;
+ {
+ /* m is maximum 55 bits */
+ uint64 tmp;
+ const uint64 lo = umul128(m, mul[0], &tmp);
+ uint64 hi;
+ const uint64 mid = tmp + umul128(m, mul[1], &hi);
+
+ hi += mid < tmp;
+ /* overflow into hi */
+
+ {
+ const uint64 lo2 = lo + mul[0];
+ const uint64 mid2 = mid + mul[1] + (lo2 < lo);
+ const uint64 hi2 = hi + (mid2 < mid);
+
+ *vp = shiftright128(mid2, hi2, j - 64 - 1);
+
+ if (mmShift == 1)
+ {
+ const uint64 lo3 = lo - mul[0];
+ const uint64 mid3 = mid - mul[1] - (lo3 > lo);
+ const uint64 hi3 = hi - (mid3 > mid);
+
+ *vm = shiftright128(mid3, hi3, j - 64 - 1);
+ }
+ else
+ {
+ const uint64 lo3 = lo + lo;
+ const uint64 mid3 = mid + mid + (lo3 < lo);
+ const uint64 hi3 = hi + hi + (mid3 < mid);
+ const uint64 lo4 = lo3 - mul[0];
+ const uint64 mid4 = mid3 - mul[1] - (lo4 > lo3);
+ const uint64 hi4 = hi3 - (mid4 > mid3);
+
+ *vm = shiftright128(mid4, hi4, j - 64);
+ }
+
+ return shiftright128(mid, hi, j - 64 - 1);
+ }
+ }
+}
+
+#endif /* // HAS_64_BIT_INTRINSICS */
+
+static inline uint32
+decimalLength(const uint64 v)
+{
+ /* This is slightly faster than a loop. */
+ /* The average output length is 16.38 digits, so we check high-to-low. */
+ /* Function precondition: v is not an 18, 19, or 20-digit number. */
+ /* (17 digits are sufficient for round-tripping.) */
+ Assert(v < 100000000000000000L);
+ if (v >= 10000000000000000L)
+ {
+ return 17;
+ }
+ if (v >= 1000000000000000L)
+ {
+ return 16;
+ }
+ if (v >= 100000000000000L)
+ {
+ return 15;
+ }
+ if (v >= 10000000000000L)
+ {
+ return 14;
+ }
+ if (v >= 1000000000000L)
+ {
+ return 13;
+ }
+ if (v >= 100000000000L)
+ {
+ return 12;
+ }
+ if (v >= 10000000000L)
+ {
+ return 11;
+ }
+ if (v >= 1000000000L)
+ {
+ return 10;
+ }
+ if (v >= 100000000L)
+ {
+ return 9;
+ }
+ if (v >= 10000000L)
+ {
+ return 8;
+ }
+ if (v >= 1000000L)
+ {
+ return 7;
+ }
+ if (v >= 100000L)
+ {
+ return 6;
+ }
+ if (v >= 10000L)
+ {
+ return 5;
+ }
+ if (v >= 1000L)
+ {
+ return 4;
+ }
+ if (v >= 100L)
+ {
+ return 3;
+ }
+ if (v >= 10L)
+ {
+ return 2;
+ }
+ return 1;
+}
+
+/* A floating decimal representing m * 10^e. */
+typedef struct floating_decimal_64
+{
+ uint64 mantissa;
+ int32 exponent;
+} floating_decimal_64;
+
+static inline floating_decimal_64
+d2d(const uint64 ieeeMantissa, const uint32 ieeeExponent)
+{
+ int32 e2;
+ uint64 m2;
+
+ if (ieeeExponent == 0)
+ {
+ /* We subtract 2 so that the bounds computation has 2 additional bits. */
+ e2 = 1 - DOUBLE_BIAS - DOUBLE_MANTISSA_BITS - 2;
+ m2 = ieeeMantissa;
+ }
+ else
+ {
+ e2 = ieeeExponent - DOUBLE_BIAS - DOUBLE_MANTISSA_BITS - 2;
+ m2 = (1ull << DOUBLE_MANTISSA_BITS) | ieeeMantissa;
+ }
+
+ {
+ const bool even = (m2 & 1) == 0;
+ const bool acceptBounds = even;
+
+ /* Step 2: Determine the interval of legal decimal representations. */
+ const uint64 mv = 4 * m2;
+
+ /* Implicit bool -> int conversion. True is 1, false is 0. */
+ const uint32 mmShift = ieeeMantissa != 0 || ieeeExponent <= 1;
+
+ /* We would compute mp and mm like this: */
+ /* uint64 mp = 4 * m2 + 2; */
+ /* uint64 mm = mv - 1 - mmShift; */
+
+ /* Step 3: Convert to a decimal power base using 128-bit arithmetic. */
+ uint64 vr,
+ vp,
+ vm;
+ int32 e10;
+ bool vmIsTrailingZeros = false;
+ bool vrIsTrailingZeros = false;
+
+ if (e2 >= 0)
+ {
+ /*
+ * I tried special-casing q == 0, but there was no effect on
+ * performance.
+ *
+ * This expr is slightly faster than max(0, log10Pow2(e2) - 1).
+ */
+ const uint32 q = log10Pow2(e2) - (e2 > 3);
+ const int32 k = DOUBLE_POW5_INV_BITCOUNT + pow5bits(q) - 1;
+ const int32 i = -e2 + q + k;
+
+ e10 = q;
+
+ vr = mulShiftAll(m2, DOUBLE_POW5_INV_SPLIT[q], i, &vp, &vm, mmShift);
+
+ if (q <= 21)
+ {
+ /*
+ * This should use q <= 22, but I think 21 is also safe.
+ * Smaller values may still be safe, but it's more difficult
+ * to reason about them.
+ *
+ * Only one of mp, mv, and mm can be a multiple of 5, if any.
+ */
+ const uint32 mvMod5 = (uint32) (mv - 5 * div5(mv));
+
+ if (mvMod5 == 0)
+ {
+ vrIsTrailingZeros = multipleOfPowerOf5(mv, q);
+ }
+ else if (acceptBounds)
+ {
+ /*----
+ * Same as min(e2 + (~mm & 1), pow5Factor(mm)) >= q
+ * <=> e2 + (~mm & 1) >= q && pow5Factor(mm) >= q
+ * <=> true && pow5Factor(mm) >= q, since e2 >= q.
+ *----
+ */
+ vmIsTrailingZeros = multipleOfPowerOf5(mv - 1 - mmShift, q);
+ }
+ else
+ {
+ /* Same as min(e2 + 1, pow5Factor(mp)) >= q. */
+ vp -= multipleOfPowerOf5(mv + 2, q);
+ }
+ }
+ }
+ else
+ {
+ /*
+ * This expression is slightly faster than max(0, log10Pow5(-e2) -
+ * 1).
+ */
+ const uint32 q = log10Pow5(-e2) - (-e2 > 1);
+ const int32 i = -e2 - q;
+ const int32 k = pow5bits(i) - DOUBLE_POW5_BITCOUNT;
+ const int32 j = q - k;
+
+ e10 = q + e2;
+
+ vr = mulShiftAll(m2, DOUBLE_POW5_SPLIT[i], j, &vp, &vm, mmShift);
+
+ if (q <= 1)
+ {
+ /*
+ * {vr,vp,vm} is trailing zeros if {mv,mp,mm} has at least q
+ * trailing 0 bits.
+ */
+ /* mv = 4 * m2, so it always has at least two trailing 0 bits. */
+ vrIsTrailingZeros = true;
+ if (acceptBounds)
+ {
+ /*
+ * mm = mv - 1 - mmShift, so it has 1 trailing 0 bit iff
+ * mmShift == 1.
+ */
+ vmIsTrailingZeros = mmShift == 1;
+ }
+ else
+ {
+ /*
+ * mp = mv + 2, so it always has at least one trailing 0
+ * bit.
+ */
+ --vp;
+ }
+ }
+ else if (q < 63)
+ {
+ /* TODO(ulfjack):Use a tighter bound here. */
+ /*
+ * We need to compute min(ntz(mv), pow5Factor(mv) - e2) >= q -
+ * 1
+ */
+ /* <=> ntz(mv) >= q - 1 && pow5Factor(mv) - e2 >= q - 1 */
+ /* <=> ntz(mv) >= q - 1 (e2 is negative and -e2 >= q) */
+ /* <=> (mv & ((1 << (q - 1)) - 1)) == 0 */
+
+ /*
+ * We also need to make sure that the left shift does not
+ * overflow.
+ */
+ vrIsTrailingZeros = multipleOfPowerOf2(mv, q - 1);
+ }
+ }
+
+ {
+ /*
+ * Step 4: Find the shortest decimal representation in the
+ * interval of legal representations.
+ */
+ uint32 removed = 0;
+ uint8_t lastRemovedDigit = 0;
+ uint64 output;
+
+ /* On average, we remove ~2 digits. */
+ if (vmIsTrailingZeros || vrIsTrailingZeros)
+ {
+ /* General case, which happens rarely (~0.7%). */
+ for (;;)
+ {
+ const uint64 vpDiv10 = div10(vp);
+ const uint64 vmDiv10 = div10(vm);
+ uint32 vmMod10;
+ uint64 vrDiv10;
+ uint32 vrMod10;
+
+ if (vpDiv10 <= vmDiv10)
+ break;
+
+ vmMod10 = (uint32) (vm - 10 * vmDiv10);
+ vrDiv10 = div10(vr);
+ vrMod10 = (uint32) (vr - 10 * vrDiv10);
+
+ vmIsTrailingZeros &= vmMod10 == 0;
+ vrIsTrailingZeros &= lastRemovedDigit == 0;
+ lastRemovedDigit = (uint8_t) vrMod10;
+ vr = vrDiv10;
+ vp = vpDiv10;
+ vm = vmDiv10;
+ ++removed;
+ }
+
+ if (vmIsTrailingZeros)
+ {
+ for (;;)
+ {
+ const uint64 vmDiv10 = div10(vm);
+ const uint32 vmMod10 = (uint32) (vm - 10 * vmDiv10);
+ uint64 vpDiv10;
+ uint64 vrDiv10;
+ uint32 vrMod10;
+
+ if (vmMod10 != 0)
+ break;
+
+ vpDiv10 = div10(vp);
+ vrDiv10 = div10(vr);
+ vrMod10 = (uint32) (vr - 10 * vrDiv10);
+
+ vrIsTrailingZeros &= lastRemovedDigit == 0;
+ lastRemovedDigit = (uint8_t) vrMod10;
+ vr = vrDiv10;
+ vp = vpDiv10;
+ vm = vmDiv10;
+ ++removed;
+ }
+ }
+
+ if (vrIsTrailingZeros && lastRemovedDigit == 5 && vr % 2 == 0)
+ {
+ /* Round even if the exact number is .....50..0. */
+ lastRemovedDigit = 4;
+ }
+
+ /*
+ * We need to take vr + 1 if vr is outside bounds or we need
+ * to round up.
+ */
+ output = vr + ((vr == vm && (!acceptBounds || !vmIsTrailingZeros)) || lastRemovedDigit >= 5);
+ }
+ else
+ {
+ /*
+ * Specialized for the common case (~99.3%). Percentages below
+ * are relative to this.
+ */
+ bool roundUp = false;
+ const uint64 vpDiv100 = div100(vp);
+ const uint64 vmDiv100 = div100(vm);
+
+ if (vpDiv100 > vmDiv100)
+ {
+ /* Optimization:remove two digits at a time(~86.2 %). */
+ const uint64 vrDiv100 = div100(vr);
+ const uint32 vrMod100 = (uint32) (vr - 100 * vrDiv100);
+
+ roundUp = vrMod100 >= 50;
+ vr = vrDiv100;
+ vp = vpDiv100;
+ vm = vmDiv100;
+ removed += 2;
+ }
+
+ /*----
+ * Loop iterations below (approximately), without optimization
+ * above:
+ *
+ * 0: 0.03%, 1: 13.8%, 2: 70.6%, 3: 14.0%, 4: 1.40%, 5: 0.14%,
+ * 6+: 0.02%
+ *
+ * Loop iterations below (approximately), with optimization
+ * above:
+ *
+ * 0: 70.6%, 1: 27.8%, 2: 1.40%, 3: 0.14%, 4+: 0.02%
+ *----
+ */
+ for (;;)
+ {
+ const uint64 vpDiv10 = div10(vp);
+ const uint64 vmDiv10 = div10(vm);
+ uint64 vrDiv10;
+ uint32 vrMod10;
+
+ if (vpDiv10 <= vmDiv10)
+ break;
+
+ vrDiv10 = div10(vr);
+ vrMod10 = (uint32) (vr - 10 * vrDiv10);
+
+ roundUp = vrMod10 >= 5;
+ vr = vrDiv10;
+ vp = vpDiv10;
+ vm = vmDiv10;
+ ++removed;
+ }
+
+ /*
+ * We need to take vr + 1 if vr is outside bounds or we need
+ * to round up.
+ */
+ output = vr + (vr == vm || roundUp);
+ }
+
+ {
+ const int32 exp = e10 + removed;
+
+ floating_decimal_64 fd;
+
+ fd.exponent = exp;
+ fd.mantissa = output;
+ return fd;
+ }
+ }
+ }
+}
+
+static inline int
+to_chars_df(const floating_decimal_64 v, const uint32 olength, char *const result)
+{
+ /* Step 5: Print the decimal representation. */
+ int index = 0;
+
+ uint64 output = v.mantissa;
+ int32 exp = v.exponent;
+
+ /*----
+ *
+ * On entry, mantissa * 10^exp is the result to be output.
+ * Caller has already done the - sign if needed.
+ *
+ * We want to insert the point somewhere else, which might mean
+ * adding zeros:
+ *
+ * exp | format
+ * 1+ | ddddddddd000000
+ * 0 | ddddddddd
+ * -1 .. -len+1 | dddddddd.d to d.ddddddddd
+ * -len ... | 0.ddddddddd to 0.0000dddddd
+ */
+ uint32 i = 0;
+ int32 nexp = exp + olength;
+
+ if (nexp <= 0)
+ {
+ /* 0.0000ddddd */
+ index = 2 - nexp;
+ memset(result, '0', index);
+ result[1] = '.';
+ }
+ else if (exp < 0)
+ {
+ /*
+ * dddd.dddd; leave space at the start and move the '.' in after
+ */
+ index = 1;
+ }
+
+ /*
+ * We prefer 32-bit operations, even on 64-bit platforms. We have at most
+ * 17 digits, and uint32 can store 9 digits. If output doesn't fit into
+ * uint32, we cut off 8 digits, so the rest will fit into uint32.
+ */
+ if ((output >> 32) != 0)
+ {
+ /* Expensive 64-bit division. */
+ const uint64 q = div1e8(output);
+ uint32 output2 = (uint32) (output - 100000000 * q);
+ const uint32 c = output2 % 10000;
+
+ output = q;
+ output2 /= 10000;
+
+ {
+ const uint32 d = output2 % 10000;
+ const uint32 c0 = (c % 100) << 1;
+ const uint32 c1 = (c / 100) << 1;
+ const uint32 d0 = (d % 100) << 1;
+ const uint32 d1 = (d / 100) << 1;
+
+ memcpy(result + index + olength - i - 2, DIGIT_TABLE + c0, 2);
+ memcpy(result + index + olength - i - 4, DIGIT_TABLE + c1, 2);
+ memcpy(result + index + olength - i - 6, DIGIT_TABLE + d0, 2);
+ memcpy(result + index + olength - i - 8, DIGIT_TABLE + d1, 2);
+ i += 8;
+ }
+ }
+
+ {
+ uint32 output2 = (uint32) output;
+
+ while (output2 >= 10000)
+ {
+ const uint32 c = output2 - 10000 * (output2 / 10000);
+ const uint32 c0 = (c % 100) << 1;
+ const uint32 c1 = (c / 100) << 1;
+
+ output2 /= 10000;
+ memcpy(result + index + olength - i - 2, DIGIT_TABLE + c0, 2);
+ memcpy(result + index + olength - i - 4, DIGIT_TABLE + c1, 2);
+ i += 4;
+ }
+ if (output2 >= 100)
+ {
+ const uint32 c = (output2 % 100) << 1;
+
+ output2 /= 100;
+ memcpy(result + index + olength - i - 2, DIGIT_TABLE + c, 2);
+ i += 2;
+ }
+ if (output2 >= 10)
+ {
+ const uint32 c = output2 << 1;
+
+ memcpy(result + index + olength - i - 2, DIGIT_TABLE + c, 2);
+ }
+ else
+ {
+ result[index] = (char) ('0' + output2);
+ }
+ }
+
+ if (index == 1)
+ {
+ memmove(result, result+1, nexp);
+ result[nexp] = '.';
+ index = olength + 1;
+ }
+ else if (exp >= 0)
+ {
+ if (exp > 0)
+ memset(result + olength, '0', exp);
+ index = olength + exp;
+ }
+ else
+ {
+ index = olength + (2 - nexp);
+ }
+
+ return index;
+}
+
+static inline int
+to_chars(const floating_decimal_64 v, const bool sign, char *const result)
+{
+ /* Step 5: Print the decimal representation. */
+ int index = 0;
+
+ uint64 output = v.mantissa;
+ const uint32 olength = decimalLength(output);
+ int32 exp = v.exponent + olength - 1;
+
+ if (sign)
+ {
+ result[index++] = '-';
+ }
+
+ if (exp >= -4 && exp < 15)
+ return to_chars_df(v, olength, result+index) + sign;
+
+ /*----
+ * Print the decimal digits.
+ *
+ * The following code is equivalent to:
+ *
+ * for (uint32 i = 0; i < olength - 1; ++i) {
+ * const uint32 c = output % 10; output /= 10;
+ * result[index + olength - i] = (char) ('0' + c);
+ * }
+ * result[index] = '0' + output % 10;
+ *----
+ */
+
+ uint32 i = 0;
+
+ /*
+ * We prefer 32-bit operations, even on 64-bit platforms. We have at most
+ * 17 digits, and uint32 can store 9 digits. If output doesn't fit into
+ * uint32, we cut off 8 digits, so the rest will fit into uint32.
+ */
+ if ((output >> 32) != 0)
+ {
+ /* Expensive 64-bit division. */
+ const uint64 q = div1e8(output);
+ uint32 output2 = (uint32) (output - 100000000 * q);
+ const uint32 c = output2 % 10000;
+
+ output = q;
+ output2 /= 10000;
+
+ {
+ const uint32 d = output2 % 10000;
+ const uint32 c0 = (c % 100) << 1;
+ const uint32 c1 = (c / 100) << 1;
+ const uint32 d0 = (d % 100) << 1;
+ const uint32 d1 = (d / 100) << 1;
+
+ memcpy(result + index + olength - i - 1, DIGIT_TABLE + c0, 2);
+ memcpy(result + index + olength - i - 3, DIGIT_TABLE + c1, 2);
+ memcpy(result + index + olength - i - 5, DIGIT_TABLE + d0, 2);
+ memcpy(result + index + olength - i - 7, DIGIT_TABLE + d1, 2);
+ i += 8;
+ }
+ }
+
+ {
+ uint32 output2 = (uint32) output;
+
+ while (output2 >= 10000)
+ {
+ const uint32 c = output2 - 10000 * (output2 / 10000);
+ const uint32 c0 = (c % 100) << 1;
+ const uint32 c1 = (c / 100) << 1;
+
+ output2 /= 10000;
+ memcpy(result + index + olength - i - 1, DIGIT_TABLE + c0, 2);
+ memcpy(result + index + olength - i - 3, DIGIT_TABLE + c1, 2);
+ i += 4;
+ }
+ if (output2 >= 100)
+ {
+ const uint32 c = (output2 % 100) << 1;
+
+ output2 /= 100;
+ memcpy(result + index + olength - i - 1, DIGIT_TABLE + c, 2);
+ i += 2;
+ }
+ if (output2 >= 10)
+ {
+ const uint32 c = output2 << 1;
+
+ /*
+ * We can't use memcpy here: the decimal dot goes between these
+ * two digits.
+ */
+ result[index + olength - i] = DIGIT_TABLE[c + 1];
+ result[index] = DIGIT_TABLE[c];
+ }
+ else
+ {
+ result[index] = (char) ('0' + output2);
+ }
+ }
+
+ /* Print decimal point if needed. */
+ if (olength > 1)
+ {
+ result[index + 1] = '.';
+ index += olength + 1;
+ }
+ else
+ {
+ ++index;
+ }
+
+ /* Print the exponent. */
+ result[index++] = 'e';
+ {
+ if (exp < 0)
+ {
+ result[index++] = '-';
+ exp = -exp;
+ }
+ else
+ result[index++] = '+';
+
+ if (exp >= 100)
+ {
+ const int32 c = exp % 10;
+
+ memcpy(result + index, DIGIT_TABLE + 2 * (exp / 10), 2);
+ result[index + 2] = (char) ('0' + c);
+ index += 3;
+ }
+ else
+ {
+ memcpy(result + index, DIGIT_TABLE + 2 * exp, 2);
+ index += 2;
+ }
+ }
+
+ return index;
+}
+
+int
+ryu_d2s_buffered_n(double f, char *result)
+{
+ /*
+ * Step 1: Decode the floating-point number, and unify normalized and
+ * subnormal cases.
+ */
+ const uint64 bits = double_to_bits(f);
+
+ /* Decode bits into sign, mantissa, and exponent. */
+ const bool ieeeSign = ((bits >> (DOUBLE_MANTISSA_BITS + DOUBLE_EXPONENT_BITS)) & 1) != 0;
+ const uint64 ieeeMantissa = bits & ((1ull << DOUBLE_MANTISSA_BITS) - 1);
+ const uint32 ieeeExponent = (uint32) ((bits >> DOUBLE_MANTISSA_BITS) & ((1u << DOUBLE_EXPONENT_BITS) - 1));
+
+ /* Case distinction; exit early for the easy cases. */
+ if (ieeeExponent == ((1u << DOUBLE_EXPONENT_BITS) - 1u) || (ieeeExponent == 0 && ieeeMantissa == 0))
+ {
+ return copy_special_str(result, ieeeSign, ieeeExponent, ieeeMantissa);
+ }
+
+ {
+ const floating_decimal_64 v = d2d(ieeeMantissa, ieeeExponent);
+
+ return to_chars(v, ieeeSign, result);
+ }
+}
+
+void
+ryu_d2s_buffered(double f, char *result)
+{
+ const int index = ryu_d2s_buffered_n(f, result);
+
+ /* Terminate the string. */
+ result[index] = '\0';
+}
+
+char *
+ryu_d2s(double f)
+{
+ char *const result = (char *) malloc(25);
+
+ ryu_d2s_buffered(f, result);
+ return result;
+}
diff --git a/src/common/d2s_full_table.h b/src/common/d2s_full_table.h
new file mode 100644
index 0000000000..7934db3b14
--- /dev/null
+++ b/src/common/d2s_full_table.h
@@ -0,0 +1,354 @@
+/*---------------------------------------------------------------------------
+ *
+ * Ryu floating-point output for double precision.
+ *
+ * Portions Copyright (c) 2018, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ * src/common/d2s_full_table.h
+ *
+ * This is a modification of code taken from github.com/ulfjack/ryu under the
+ * terms of the Boost license (not the Apache license). The original copyright
+ * notice follows:
+ *
+ * Copyright 2018 Ulf Adams
+ *
+ * The contents of this file may be used under the terms of the Apache
+ * License, Version 2.0.
+ *
+ * (See accompanying file LICENSE-Apache or copy at
+ * http://www.apache.org/licenses/LICENSE-2.0)
+ *
+ * Alternatively, the contents of this file may be used under the terms of the
+ * Boost Software License, Version 1.0.
+ *
+ * (See accompanying file LICENSE-Boost or copy at
+ * https://www.boost.org/LICENSE_1_0.txt)
+ *
+ * Unless required by applicable law or agreed to in writing, this software is
+ * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.
+ *
+ *---------------------------------------------------------------------------
+ */
+
+#ifndef RYU_D2S_FULL_TABLE_H
+#define RYU_D2S_FULL_TABLE_H
+
+/* These tables are generated by PrintDoubleLookupTable. */
+static const uint64 DOUBLE_POW5_INV_SPLIT[292][2] = {
+ {UINT64CONST(1), UINT64CONST(288230376151711744)}, {UINT64CONST(3689348814741910324), UINT64CONST(230584300921369395)},
+ {UINT64CONST(2951479051793528259), UINT64CONST(184467440737095516)}, {UINT64CONST(17118578500402463900), UINT64CONST(147573952589676412)},
+ {UINT64CONST(12632330341676300947), UINT64CONST(236118324143482260)}, {UINT64CONST(10105864273341040758), UINT64CONST(188894659314785808)},
+ {UINT64CONST(15463389048156653253), UINT64CONST(151115727451828646)}, {UINT64CONST(17362724847566824558), UINT64CONST(241785163922925834)},
+ {UINT64CONST(17579528692795369969), UINT64CONST(193428131138340667)}, {UINT64CONST(6684925324752475329), UINT64CONST(154742504910672534)},
+ {UINT64CONST(18074578149087781173), UINT64CONST(247588007857076054)}, {UINT64CONST(18149011334012135262), UINT64CONST(198070406285660843)},
+ {UINT64CONST(3451162622983977240), UINT64CONST(158456325028528675)}, {UINT64CONST(5521860196774363583), UINT64CONST(253530120045645880)},
+ {UINT64CONST(4417488157419490867), UINT64CONST(202824096036516704)}, {UINT64CONST(7223339340677503017), UINT64CONST(162259276829213363)},
+ {UINT64CONST(7867994130342094503), UINT64CONST(259614842926741381)}, {UINT64CONST(2605046489531765280), UINT64CONST(207691874341393105)},
+ {UINT64CONST(2084037191625412224), UINT64CONST(166153499473114484)}, {UINT64CONST(10713157136084480204), UINT64CONST(265845599156983174)},
+ {UINT64CONST(12259874523609494487), UINT64CONST(212676479325586539)}, {UINT64CONST(13497248433629505913), UINT64CONST(170141183460469231)},
+ {UINT64CONST(14216899864323388813), UINT64CONST(272225893536750770)}, {UINT64CONST(11373519891458711051), UINT64CONST(217780714829400616)},
+ {UINT64CONST(5409467098425058518), UINT64CONST(174224571863520493)}, {UINT64CONST(4965798542738183305), UINT64CONST(278759314981632789)},
+ {UINT64CONST(7661987648932456967), UINT64CONST(223007451985306231)}, {UINT64CONST(2440241304404055250), UINT64CONST(178405961588244985)},
+ {UINT64CONST(3904386087046488400), UINT64CONST(285449538541191976)}, {UINT64CONST(17880904128604832013), UINT64CONST(228359630832953580)},
+ {UINT64CONST(14304723302883865611), UINT64CONST(182687704666362864)}, {UINT64CONST(15133127457049002812), UINT64CONST(146150163733090291)},
+ {UINT64CONST(16834306301794583852), UINT64CONST(233840261972944466)}, {UINT64CONST(9778096226693756759), UINT64CONST(187072209578355573)},
+ {UINT64CONST(15201174610838826053), UINT64CONST(149657767662684458)}, {UINT64CONST(2185786488890659746), UINT64CONST(239452428260295134)},
+ {UINT64CONST(5437978005854438120), UINT64CONST(191561942608236107)}, {UINT64CONST(15418428848909281466), UINT64CONST(153249554086588885)},
+ {UINT64CONST(6222742084545298729), UINT64CONST(245199286538542217)}, {UINT64CONST(16046240111861969953), UINT64CONST(196159429230833773)},
+ {UINT64CONST(1768945645263844993), UINT64CONST(156927543384667019)}, {UINT64CONST(10209010661905972635), UINT64CONST(251084069415467230)},
+ {UINT64CONST(8167208529524778108), UINT64CONST(200867255532373784)}, {UINT64CONST(10223115638361732810), UINT64CONST(160693804425899027)},
+ {UINT64CONST(1599589762411131202), UINT64CONST(257110087081438444)}, {UINT64CONST(4969020624670815285), UINT64CONST(205688069665150755)},
+ {UINT64CONST(3975216499736652228), UINT64CONST(164550455732120604)}, {UINT64CONST(13739044029062464211), UINT64CONST(263280729171392966)},
+ {UINT64CONST(7301886408508061046), UINT64CONST(210624583337114373)}, {UINT64CONST(13220206756290269483), UINT64CONST(168499666669691498)},
+ {UINT64CONST(17462981995322520850), UINT64CONST(269599466671506397)}, {UINT64CONST(6591687966774196033), UINT64CONST(215679573337205118)},
+ {UINT64CONST(12652048002903177473), UINT64CONST(172543658669764094)}, {UINT64CONST(9175230360419352987), UINT64CONST(276069853871622551)},
+ {UINT64CONST(3650835473593572067), UINT64CONST(220855883097298041)}, {UINT64CONST(17678063637842498946), UINT64CONST(176684706477838432)},
+ {UINT64CONST(13527506561580357021), UINT64CONST(282695530364541492)}, {UINT64CONST(3443307619780464970), UINT64CONST(226156424291633194)},
+ {UINT64CONST(6443994910566282300), UINT64CONST(180925139433306555)}, {UINT64CONST(5155195928453025840), UINT64CONST(144740111546645244)},
+ {UINT64CONST(15627011115008661990), UINT64CONST(231584178474632390)}, {UINT64CONST(12501608892006929592), UINT64CONST(185267342779705912)},
+ {UINT64CONST(2622589484121723027), UINT64CONST(148213874223764730)}, {UINT64CONST(4196143174594756843), UINT64CONST(237142198758023568)},
+ {UINT64CONST(10735612169159626121), UINT64CONST(189713759006418854)}, {UINT64CONST(12277838550069611220), UINT64CONST(151771007205135083)},
+ {UINT64CONST(15955192865369467629), UINT64CONST(242833611528216133)}, {UINT64CONST(1696107848069843133), UINT64CONST(194266889222572907)},
+ {UINT64CONST(12424932722681605476), UINT64CONST(155413511378058325)}, {UINT64CONST(1433148282581017146), UINT64CONST(248661618204893321)},
+ {UINT64CONST(15903913885032455010), UINT64CONST(198929294563914656)}, {UINT64CONST(9033782293284053685), UINT64CONST(159143435651131725)},
+ {UINT64CONST(14454051669254485895), UINT64CONST(254629497041810760)}, {UINT64CONST(11563241335403588716), UINT64CONST(203703597633448608)},
+ {UINT64CONST(16629290697806691620), UINT64CONST(162962878106758886)}, {UINT64CONST(781423413297334329), UINT64CONST(260740604970814219)},
+ {UINT64CONST(4314487545379777786), UINT64CONST(208592483976651375)}, {UINT64CONST(3451590036303822229), UINT64CONST(166873987181321100)},
+ {UINT64CONST(5522544058086115566), UINT64CONST(266998379490113760)}, {UINT64CONST(4418035246468892453), UINT64CONST(213598703592091008)},
+ {UINT64CONST(10913125826658934609), UINT64CONST(170878962873672806)}, {UINT64CONST(10082303693170474728), UINT64CONST(273406340597876490)},
+ {UINT64CONST(8065842954536379782), UINT64CONST(218725072478301192)}, {UINT64CONST(17520720807854834795), UINT64CONST(174980057982640953)},
+ {UINT64CONST(5897060404116273733), UINT64CONST(279968092772225526)}, {UINT64CONST(1028299508551108663), UINT64CONST(223974474217780421)},
+ {UINT64CONST(15580034865808528224), UINT64CONST(179179579374224336)}, {UINT64CONST(17549358155809824511), UINT64CONST(286687326998758938)},
+ {UINT64CONST(2971440080422128639), UINT64CONST(229349861599007151)}, {UINT64CONST(17134547323305344204), UINT64CONST(183479889279205720)},
+ {UINT64CONST(13707637858644275364), UINT64CONST(146783911423364576)}, {UINT64CONST(14553522944347019935), UINT64CONST(234854258277383322)},
+ {UINT64CONST(4264120725993795302), UINT64CONST(187883406621906658)}, {UINT64CONST(10789994210278856888), UINT64CONST(150306725297525326)},
+ {UINT64CONST(9885293106962350374), UINT64CONST(240490760476040522)}, {UINT64CONST(529536856086059653), UINT64CONST(192392608380832418)},
+ {UINT64CONST(7802327114352668369), UINT64CONST(153914086704665934)}, {UINT64CONST(1415676938738538420), UINT64CONST(246262538727465495)},
+ {UINT64CONST(1132541550990830736), UINT64CONST(197010030981972396)}, {UINT64CONST(15663428499760305882), UINT64CONST(157608024785577916)},
+ {UINT64CONST(17682787970132668764), UINT64CONST(252172839656924666)}, {UINT64CONST(10456881561364224688), UINT64CONST(201738271725539733)},
+ {UINT64CONST(15744202878575200397), UINT64CONST(161390617380431786)}, {UINT64CONST(17812026976236499989), UINT64CONST(258224987808690858)},
+ {UINT64CONST(3181575136763469022), UINT64CONST(206579990246952687)}, {UINT64CONST(13613306553636506187), UINT64CONST(165263992197562149)},
+ {UINT64CONST(10713244041592678929), UINT64CONST(264422387516099439)}, {UINT64CONST(12259944048016053467), UINT64CONST(211537910012879551)},
+ {UINT64CONST(6118606423670932450), UINT64CONST(169230328010303641)}, {UINT64CONST(2411072648389671274), UINT64CONST(270768524816485826)},
+ {UINT64CONST(16686253377679378312), UINT64CONST(216614819853188660)}, {UINT64CONST(13349002702143502650), UINT64CONST(173291855882550928)},
+ {UINT64CONST(17669055508687693916), UINT64CONST(277266969412081485)}, {UINT64CONST(14135244406950155133), UINT64CONST(221813575529665188)},
+ {UINT64CONST(240149081334393137), UINT64CONST(177450860423732151)}, {UINT64CONST(11452284974360759988), UINT64CONST(283921376677971441)},
+ {UINT64CONST(5472479164746697667), UINT64CONST(227137101342377153)}, {UINT64CONST(11756680961281178780), UINT64CONST(181709681073901722)},
+ {UINT64CONST(2026647139541122378), UINT64CONST(145367744859121378)}, {UINT64CONST(18000030682233437097), UINT64CONST(232588391774594204)},
+ {UINT64CONST(18089373360528660001), UINT64CONST(186070713419675363)}, {UINT64CONST(3403452244197197031), UINT64CONST(148856570735740291)},
+ {UINT64CONST(16513570034941246220), UINT64CONST(238170513177184465)}, {UINT64CONST(13210856027952996976), UINT64CONST(190536410541747572)},
+ {UINT64CONST(3189987192878576934), UINT64CONST(152429128433398058)}, {UINT64CONST(1414630693863812771), UINT64CONST(243886605493436893)},
+ {UINT64CONST(8510402184574870864), UINT64CONST(195109284394749514)}, {UINT64CONST(10497670562401807014), UINT64CONST(156087427515799611)},
+ {UINT64CONST(9417575270359070576), UINT64CONST(249739884025279378)}, {UINT64CONST(14912757845771077107), UINT64CONST(199791907220223502)},
+ {UINT64CONST(4551508647133041040), UINT64CONST(159833525776178802)}, {UINT64CONST(10971762650154775986), UINT64CONST(255733641241886083)},
+ {UINT64CONST(16156107749607641435), UINT64CONST(204586912993508866)}, {UINT64CONST(9235537384944202825), UINT64CONST(163669530394807093)},
+ {UINT64CONST(11087511001168814197), UINT64CONST(261871248631691349)}, {UINT64CONST(12559357615676961681), UINT64CONST(209496998905353079)},
+ {UINT64CONST(13736834907283479668), UINT64CONST(167597599124282463)}, {UINT64CONST(18289587036911657145), UINT64CONST(268156158598851941)},
+ {UINT64CONST(10942320814787415393), UINT64CONST(214524926879081553)}, {UINT64CONST(16132554281313752961), UINT64CONST(171619941503265242)},
+ {UINT64CONST(11054691591134363444), UINT64CONST(274591906405224388)}, {UINT64CONST(16222450902391311402), UINT64CONST(219673525124179510)},
+ {UINT64CONST(12977960721913049122), UINT64CONST(175738820099343608)}, {UINT64CONST(17075388340318968271), UINT64CONST(281182112158949773)},
+ {UINT64CONST(2592264228029443648), UINT64CONST(224945689727159819)}, {UINT64CONST(5763160197165465241), UINT64CONST(179956551781727855)},
+ {UINT64CONST(9221056315464744386), UINT64CONST(287930482850764568)}, {UINT64CONST(14755542681855616155), UINT64CONST(230344386280611654)},
+ {UINT64CONST(15493782960226403247), UINT64CONST(184275509024489323)}, {UINT64CONST(1326979923955391628), UINT64CONST(147420407219591459)},
+ {UINT64CONST(9501865507812447252), UINT64CONST(235872651551346334)}, {UINT64CONST(11290841220991868125), UINT64CONST(188698121241077067)},
+ {UINT64CONST(1653975347309673853), UINT64CONST(150958496992861654)}, {UINT64CONST(10025058185179298811), UINT64CONST(241533595188578646)},
+ {UINT64CONST(4330697733401528726), UINT64CONST(193226876150862917)}, {UINT64CONST(14532604630946953951), UINT64CONST(154581500920690333)},
+ {UINT64CONST(1116074521063664381), UINT64CONST(247330401473104534)}, {UINT64CONST(4582208431592841828), UINT64CONST(197864321178483627)},
+ {UINT64CONST(14733813189500004432), UINT64CONST(158291456942786901)}, {UINT64CONST(16195403473716186445), UINT64CONST(253266331108459042)},
+ {UINT64CONST(5577625149489128510), UINT64CONST(202613064886767234)}, {UINT64CONST(8151448934333213131), UINT64CONST(162090451909413787)},
+ {UINT64CONST(16731667109675051333), UINT64CONST(259344723055062059)}, {UINT64CONST(17074682502481951390), UINT64CONST(207475778444049647)},
+ {UINT64CONST(6281048372501740465), UINT64CONST(165980622755239718)}, {UINT64CONST(6360328581260874421), UINT64CONST(265568996408383549)},
+ {UINT64CONST(8777611679750609860), UINT64CONST(212455197126706839)}, {UINT64CONST(10711438158542398211), UINT64CONST(169964157701365471)},
+ {UINT64CONST(9759603424184016492), UINT64CONST(271942652322184754)}, {UINT64CONST(11497031554089123517), UINT64CONST(217554121857747803)},
+ {UINT64CONST(16576322872755119460), UINT64CONST(174043297486198242)}, {UINT64CONST(11764721337440549842), UINT64CONST(278469275977917188)},
+ {UINT64CONST(16790474699436260520), UINT64CONST(222775420782333750)}, {UINT64CONST(13432379759549008416), UINT64CONST(178220336625867000)},
+ {UINT64CONST(3045063541568861850), UINT64CONST(285152538601387201)}, {UINT64CONST(17193446092222730773), UINT64CONST(228122030881109760)},
+ {UINT64CONST(13754756873778184618), UINT64CONST(182497624704887808)}, {UINT64CONST(18382503128506368341), UINT64CONST(145998099763910246)},
+ {UINT64CONST(3586563302416817083), UINT64CONST(233596959622256395)}, {UINT64CONST(2869250641933453667), UINT64CONST(186877567697805116)},
+ {UINT64CONST(17052795772514404226), UINT64CONST(149502054158244092)}, {UINT64CONST(12527077977055405469), UINT64CONST(239203286653190548)},
+ {UINT64CONST(17400360011128145022), UINT64CONST(191362629322552438)}, {UINT64CONST(2852241564676785048), UINT64CONST(153090103458041951)},
+ {UINT64CONST(15631632947708587046), UINT64CONST(244944165532867121)}, {UINT64CONST(8815957543424959314), UINT64CONST(195955332426293697)},
+ {UINT64CONST(18120812478965698421), UINT64CONST(156764265941034957)}, {UINT64CONST(14235904707377476180), UINT64CONST(250822825505655932)},
+ {UINT64CONST(4010026136418160298), UINT64CONST(200658260404524746)}, {UINT64CONST(17965416168102169531), UINT64CONST(160526608323619796)},
+ {UINT64CONST(2919224165770098987), UINT64CONST(256842573317791675)}, {UINT64CONST(2335379332616079190), UINT64CONST(205474058654233340)},
+ {UINT64CONST(1868303466092863352), UINT64CONST(164379246923386672)}, {UINT64CONST(6678634360490491686), UINT64CONST(263006795077418675)},
+ {UINT64CONST(5342907488392393349), UINT64CONST(210405436061934940)}, {UINT64CONST(4274325990713914679), UINT64CONST(168324348849547952)},
+ {UINT64CONST(10528270399884173809), UINT64CONST(269318958159276723)}, {UINT64CONST(15801313949391159694), UINT64CONST(215455166527421378)},
+ {UINT64CONST(1573004715287196786), UINT64CONST(172364133221937103)}, {UINT64CONST(17274202803427156150), UINT64CONST(275782613155099364)},
+ {UINT64CONST(17508711057483635243), UINT64CONST(220626090524079491)}, {UINT64CONST(10317620031244997871), UINT64CONST(176500872419263593)},
+ {UINT64CONST(12818843235250086271), UINT64CONST(282401395870821749)}, {UINT64CONST(13944423402941979340), UINT64CONST(225921116696657399)},
+ {UINT64CONST(14844887537095493795), UINT64CONST(180736893357325919)}, {UINT64CONST(15565258844418305359), UINT64CONST(144589514685860735)},
+ {UINT64CONST(6457670077359736959), UINT64CONST(231343223497377177)}, {UINT64CONST(16234182506113520537), UINT64CONST(185074578797901741)},
+ {UINT64CONST(9297997190148906106), UINT64CONST(148059663038321393)}, {UINT64CONST(11187446689496339446), UINT64CONST(236895460861314229)},
+ {UINT64CONST(12639306166338981880), UINT64CONST(189516368689051383)}, {UINT64CONST(17490142562555006151), UINT64CONST(151613094951241106)},
+ {UINT64CONST(2158786396894637579), UINT64CONST(242580951921985771)}, {UINT64CONST(16484424376483351356), UINT64CONST(194064761537588616)},
+ {UINT64CONST(9498190686444770762), UINT64CONST(155251809230070893)}, {UINT64CONST(11507756283569722895), UINT64CONST(248402894768113429)},
+ {UINT64CONST(12895553841597688639), UINT64CONST(198722315814490743)}, {UINT64CONST(17695140702761971558), UINT64CONST(158977852651592594)},
+ {UINT64CONST(17244178680193423523), UINT64CONST(254364564242548151)}, {UINT64CONST(10105994129412828495), UINT64CONST(203491651394038521)},
+ {UINT64CONST(4395446488788352473), UINT64CONST(162793321115230817)}, {UINT64CONST(10722063196803274280), UINT64CONST(260469313784369307)},
+ {UINT64CONST(1198952927958798777), UINT64CONST(208375451027495446)}, {UINT64CONST(15716557601334680315), UINT64CONST(166700360821996356)},
+ {UINT64CONST(17767794532651667857), UINT64CONST(266720577315194170)}, {UINT64CONST(14214235626121334286), UINT64CONST(213376461852155336)},
+ {UINT64CONST(7682039686155157106), UINT64CONST(170701169481724269)}, {UINT64CONST(1223217053622520399), UINT64CONST(273121871170758831)},
+ {UINT64CONST(15735968901865657612), UINT64CONST(218497496936607064)}, {UINT64CONST(16278123936234436413), UINT64CONST(174797997549285651)},
+ {UINT64CONST(219556594781725998), UINT64CONST(279676796078857043)}, {UINT64CONST(7554342905309201445), UINT64CONST(223741436863085634)},
+ {UINT64CONST(9732823138989271479), UINT64CONST(178993149490468507)}, {UINT64CONST(815121763415193074), UINT64CONST(286389039184749612)},
+ {UINT64CONST(11720143854957885429), UINT64CONST(229111231347799689)}, {UINT64CONST(13065463898708218666), UINT64CONST(183288985078239751)},
+ {UINT64CONST(6763022304224664610), UINT64CONST(146631188062591801)}, {UINT64CONST(3442138057275642729), UINT64CONST(234609900900146882)},
+ {UINT64CONST(13821756890046245153), UINT64CONST(187687920720117505)}, {UINT64CONST(11057405512036996122), UINT64CONST(150150336576094004)},
+ {UINT64CONST(6623802375033462826), UINT64CONST(240240538521750407)}, {UINT64CONST(16367088344252501231), UINT64CONST(192192430817400325)},
+ {UINT64CONST(13093670675402000985), UINT64CONST(153753944653920260)}, {UINT64CONST(2503129006933649959), UINT64CONST(246006311446272417)},
+ {UINT64CONST(13070549649772650937), UINT64CONST(196805049157017933)}, {UINT64CONST(17835137349301941396), UINT64CONST(157444039325614346)},
+ {UINT64CONST(2710778055689733971), UINT64CONST(251910462920982955)}, {UINT64CONST(2168622444551787177), UINT64CONST(201528370336786364)},
+ {UINT64CONST(5424246770383340065), UINT64CONST(161222696269429091)}, {UINT64CONST(1300097203129523457), UINT64CONST(257956314031086546)},
+ {UINT64CONST(15797473021471260058), UINT64CONST(206365051224869236)}, {UINT64CONST(8948629602435097724), UINT64CONST(165092040979895389)},
+ {UINT64CONST(3249760919670425388), UINT64CONST(264147265567832623)}, {UINT64CONST(9978506365220160957), UINT64CONST(211317812454266098)},
+ {UINT64CONST(15361502721659949412), UINT64CONST(169054249963412878)}, {UINT64CONST(2442311466204457120), UINT64CONST(270486799941460606)},
+ {UINT64CONST(16711244431931206989), UINT64CONST(216389439953168484)}, {UINT64CONST(17058344360286875914), UINT64CONST(173111551962534787)},
+ {UINT64CONST(12535955717491360170), UINT64CONST(276978483140055660)}, {UINT64CONST(10028764573993088136), UINT64CONST(221582786512044528)},
+ {UINT64CONST(15401709288678291155), UINT64CONST(177266229209635622)}, {UINT64CONST(9885339602917624555), UINT64CONST(283625966735416996)},
+ {UINT64CONST(4218922867592189321), UINT64CONST(226900773388333597)}, {UINT64CONST(14443184738299482427), UINT64CONST(181520618710666877)},
+ {UINT64CONST(4175850161155765295), UINT64CONST(145216494968533502)}, {UINT64CONST(10370709072591134795), UINT64CONST(232346391949653603)},
+ {UINT64CONST(15675264887556728482), UINT64CONST(185877113559722882)}, {UINT64CONST(5161514280561562140), UINT64CONST(148701690847778306)},
+ {UINT64CONST(879725219414678777), UINT64CONST(237922705356445290)}, {UINT64CONST(703780175531743021), UINT64CONST(190338164285156232)},
+ {UINT64CONST(11631070584651125387), UINT64CONST(152270531428124985)}, {UINT64CONST(162968861732249003), UINT64CONST(243632850284999977)},
+ {UINT64CONST(11198421533611530172), UINT64CONST(194906280227999981)}, {UINT64CONST(5269388412147313814), UINT64CONST(155925024182399985)},
+ {UINT64CONST(8431021459435702103), UINT64CONST(249480038691839976)}, {UINT64CONST(3055468352806651359), UINT64CONST(199584030953471981)},
+ {UINT64CONST(17201769941212962380), UINT64CONST(159667224762777584)}, {UINT64CONST(16454785461715008838), UINT64CONST(255467559620444135)},
+ {UINT64CONST(13163828369372007071), UINT64CONST(204374047696355308)}, {UINT64CONST(17909760324981426303), UINT64CONST(163499238157084246)},
+ {UINT64CONST(2830174816776909822), UINT64CONST(261598781051334795)}, {UINT64CONST(2264139853421527858), UINT64CONST(209279024841067836)},
+ {UINT64CONST(16568707141704863579), UINT64CONST(167423219872854268)}, {UINT64CONST(4373838538276319787), UINT64CONST(267877151796566830)},
+ {UINT64CONST(3499070830621055830), UINT64CONST(214301721437253464)}, {UINT64CONST(6488605479238754987), UINT64CONST(171441377149802771)},
+ {UINT64CONST(3003071137298187333), UINT64CONST(274306203439684434)}, {UINT64CONST(6091805724580460189), UINT64CONST(219444962751747547)},
+ {UINT64CONST(15941491023890099121), UINT64CONST(175555970201398037)}, {UINT64CONST(10748990379256517301), UINT64CONST(280889552322236860)},
+ {UINT64CONST(8599192303405213841), UINT64CONST(224711641857789488)}, {UINT64CONST(14258051472207991719), UINT64CONST(179769313486231590)}
+};
+
+static const uint64 DOUBLE_POW5_SPLIT[326][2] = {
+ {UINT64CONST(0), UINT64CONST(72057594037927936)}, {UINT64CONST(0), UINT64CONST(90071992547409920)},
+ {UINT64CONST(0), UINT64CONST(112589990684262400)}, {UINT64CONST(0), UINT64CONST(140737488355328000)},
+ {UINT64CONST(0), UINT64CONST(87960930222080000)}, {UINT64CONST(0), UINT64CONST(109951162777600000)},
+ {UINT64CONST(0), UINT64CONST(137438953472000000)}, {UINT64CONST(0), UINT64CONST(85899345920000000)},
+ {UINT64CONST(0), UINT64CONST(107374182400000000)}, {UINT64CONST(0), UINT64CONST(134217728000000000)},
+ {UINT64CONST(0), UINT64CONST(83886080000000000)}, {UINT64CONST(0), UINT64CONST(104857600000000000)},
+ {UINT64CONST(0), UINT64CONST(131072000000000000)}, {UINT64CONST(0), UINT64CONST(81920000000000000)},
+ {UINT64CONST(0), UINT64CONST(102400000000000000)}, {UINT64CONST(0), UINT64CONST(128000000000000000)},
+ {UINT64CONST(0), UINT64CONST(80000000000000000)}, {UINT64CONST(0), UINT64CONST(100000000000000000)},
+ {UINT64CONST(0), UINT64CONST(125000000000000000)}, {UINT64CONST(0), UINT64CONST(78125000000000000)},
+ {UINT64CONST(0), UINT64CONST(97656250000000000)}, {UINT64CONST(0), UINT64CONST(122070312500000000)},
+ {UINT64CONST(0), UINT64CONST(76293945312500000)}, {UINT64CONST(0), UINT64CONST(95367431640625000)},
+ {UINT64CONST(0), UINT64CONST(119209289550781250)}, {UINT64CONST(4611686018427387904), UINT64CONST(74505805969238281)},
+ {UINT64CONST(10376293541461622784), UINT64CONST(93132257461547851)}, {UINT64CONST(8358680908399640576), UINT64CONST(116415321826934814)},
+ {UINT64CONST(612489549322387456), UINT64CONST(72759576141834259)}, {UINT64CONST(14600669991935148032), UINT64CONST(90949470177292823)},
+ {UINT64CONST(13639151471491547136), UINT64CONST(113686837721616029)}, {UINT64CONST(3213881284082270208), UINT64CONST(142108547152020037)},
+ {UINT64CONST(4314518811765112832), UINT64CONST(88817841970012523)}, {UINT64CONST(781462496279003136), UINT64CONST(111022302462515654)},
+ {UINT64CONST(10200200157203529728), UINT64CONST(138777878078144567)}, {UINT64CONST(13292654125893287936), UINT64CONST(86736173798840354)},
+ {UINT64CONST(7392445620511834112), UINT64CONST(108420217248550443)}, {UINT64CONST(4628871007212404736), UINT64CONST(135525271560688054)},
+ {UINT64CONST(16728102434789916672), UINT64CONST(84703294725430033)}, {UINT64CONST(7075069988205232128), UINT64CONST(105879118406787542)},
+ {UINT64CONST(18067209522111315968), UINT64CONST(132348898008484427)}, {UINT64CONST(8986162942105878528), UINT64CONST(82718061255302767)},
+ {UINT64CONST(6621017659204960256), UINT64CONST(103397576569128459)}, {UINT64CONST(3664586055578812416), UINT64CONST(129246970711410574)},
+ {UINT64CONST(16125424340018921472), UINT64CONST(80779356694631608)}, {UINT64CONST(1710036351314100224), UINT64CONST(100974195868289511)},
+ {UINT64CONST(15972603494424788992), UINT64CONST(126217744835361888)}, {UINT64CONST(9982877184015493120), UINT64CONST(78886090522101180)},
+ {UINT64CONST(12478596480019366400), UINT64CONST(98607613152626475)}, {UINT64CONST(10986559581596820096), UINT64CONST(123259516440783094)},
+ {UINT64CONST(2254913720070624656), UINT64CONST(77037197775489434)}, {UINT64CONST(12042014186943056628), UINT64CONST(96296497219361792)},
+ {UINT64CONST(15052517733678820785), UINT64CONST(120370621524202240)}, {UINT64CONST(9407823583549262990), UINT64CONST(75231638452626400)},
+ {UINT64CONST(11759779479436578738), UINT64CONST(94039548065783000)}, {UINT64CONST(14699724349295723422), UINT64CONST(117549435082228750)},
+ {UINT64CONST(4575641699882439235), UINT64CONST(73468396926392969)}, {UINT64CONST(10331238143280436948), UINT64CONST(91835496157991211)},
+ {UINT64CONST(8302361660673158281), UINT64CONST(114794370197489014)}, {UINT64CONST(1154580038986672043), UINT64CONST(143492962746861268)},
+ {UINT64CONST(9944984561221445835), UINT64CONST(89683101716788292)}, {UINT64CONST(12431230701526807293), UINT64CONST(112103877145985365)},
+ {UINT64CONST(1703980321626345405), UINT64CONST(140129846432481707)}, {UINT64CONST(17205888765512323542), UINT64CONST(87581154020301066)},
+ {UINT64CONST(12283988920035628619), UINT64CONST(109476442525376333)}, {UINT64CONST(1519928094762372062), UINT64CONST(136845553156720417)},
+ {UINT64CONST(12479170105294952299), UINT64CONST(85528470722950260)}, {UINT64CONST(15598962631618690374), UINT64CONST(106910588403687825)},
+ {UINT64CONST(5663645234241199255), UINT64CONST(133638235504609782)}, {UINT64CONST(17374836326682913246), UINT64CONST(83523897190381113)},
+ {UINT64CONST(7883487353071477846), UINT64CONST(104404871487976392)}, {UINT64CONST(9854359191339347308), UINT64CONST(130506089359970490)},
+ {UINT64CONST(10770660513014479971), UINT64CONST(81566305849981556)}, {UINT64CONST(13463325641268099964), UINT64CONST(101957882312476945)},
+ {UINT64CONST(2994098996302961243), UINT64CONST(127447352890596182)}, {UINT64CONST(15706369927971514489), UINT64CONST(79654595556622613)},
+ {UINT64CONST(5797904354682229399), UINT64CONST(99568244445778267)}, {UINT64CONST(2635694424925398845), UINT64CONST(124460305557222834)},
+ {UINT64CONST(6258995034005762182), UINT64CONST(77787690973264271)}, {UINT64CONST(3212057774079814824), UINT64CONST(97234613716580339)},
+ {UINT64CONST(17850130272881932242), UINT64CONST(121543267145725423)}, {UINT64CONST(18073860448192289507), UINT64CONST(75964541966078389)},
+ {UINT64CONST(8757267504958198172), UINT64CONST(94955677457597987)}, {UINT64CONST(6334898362770359811), UINT64CONST(118694596821997484)},
+ {UINT64CONST(13182683513586250689), UINT64CONST(74184123013748427)}, {UINT64CONST(11866668373555425458), UINT64CONST(92730153767185534)},
+ {UINT64CONST(5609963430089506015), UINT64CONST(115912692208981918)}, {UINT64CONST(17341285199088104971), UINT64CONST(72445432630613698)},
+ {UINT64CONST(12453234462005355406), UINT64CONST(90556790788267123)}, {UINT64CONST(10954857059079306353), UINT64CONST(113195988485333904)},
+ {UINT64CONST(13693571323849132942), UINT64CONST(141494985606667380)}, {UINT64CONST(17781854114260483896), UINT64CONST(88434366004167112)},
+ {UINT64CONST(3780573569116053255), UINT64CONST(110542957505208891)}, {UINT64CONST(114030942967678664), UINT64CONST(138178696881511114)},
+ {UINT64CONST(4682955357782187069), UINT64CONST(86361685550944446)}, {UINT64CONST(15077066234082509644), UINT64CONST(107952106938680557)},
+ {UINT64CONST(5011274737320973344), UINT64CONST(134940133673350697)}, {UINT64CONST(14661261756894078100), UINT64CONST(84337583545844185)},
+ {UINT64CONST(4491519140835433913), UINT64CONST(105421979432305232)}, {UINT64CONST(5614398926044292391), UINT64CONST(131777474290381540)},
+ {UINT64CONST(12732371365632458552), UINT64CONST(82360921431488462)}, {UINT64CONST(6692092170185797382), UINT64CONST(102951151789360578)},
+ {UINT64CONST(17588487249587022536), UINT64CONST(128688939736700722)}, {UINT64CONST(15604490549419276989), UINT64CONST(80430587335437951)},
+ {UINT64CONST(14893927168346708332), UINT64CONST(100538234169297439)}, {UINT64CONST(14005722942005997511), UINT64CONST(125672792711621799)},
+ {UINT64CONST(15671105866394830300), UINT64CONST(78545495444763624)}, {UINT64CONST(1142138259283986260), UINT64CONST(98181869305954531)},
+ {UINT64CONST(15262730879387146537), UINT64CONST(122727336632443163)}, {UINT64CONST(7233363790403272633), UINT64CONST(76704585395276977)},
+ {UINT64CONST(13653390756431478696), UINT64CONST(95880731744096221)}, {UINT64CONST(3231680390257184658), UINT64CONST(119850914680120277)},
+ {UINT64CONST(4325643253124434363), UINT64CONST(74906821675075173)}, {UINT64CONST(10018740084832930858), UINT64CONST(93633527093843966)},
+ {UINT64CONST(3300053069186387764), UINT64CONST(117041908867304958)}, {UINT64CONST(15897591223523656064), UINT64CONST(73151193042065598)},
+ {UINT64CONST(10648616992549794273), UINT64CONST(91438991302581998)}, {UINT64CONST(4087399203832467033), UINT64CONST(114298739128227498)},
+ {UINT64CONST(14332621041645359599), UINT64CONST(142873423910284372)}, {UINT64CONST(18181260187883125557), UINT64CONST(89295889943927732)},
+ {UINT64CONST(4279831161144355331), UINT64CONST(111619862429909666)}, {UINT64CONST(14573160988285219972), UINT64CONST(139524828037387082)},
+ {UINT64CONST(13719911636105650386), UINT64CONST(87203017523366926)}, {UINT64CONST(7926517508277287175), UINT64CONST(109003771904208658)},
+ {UINT64CONST(684774848491833161), UINT64CONST(136254714880260823)}, {UINT64CONST(7345513307948477581), UINT64CONST(85159196800163014)},
+ {UINT64CONST(18405263671790372785), UINT64CONST(106448996000203767)}, {UINT64CONST(18394893571310578077), UINT64CONST(133061245000254709)},
+ {UINT64CONST(13802651491282805250), UINT64CONST(83163278125159193)}, {UINT64CONST(3418256308821342851), UINT64CONST(103954097656448992)},
+ {UINT64CONST(4272820386026678563), UINT64CONST(129942622070561240)}, {UINT64CONST(2670512741266674102), UINT64CONST(81214138794100775)},
+ {UINT64CONST(17173198981865506339), UINT64CONST(101517673492625968)}, {UINT64CONST(3019754653622331308), UINT64CONST(126897091865782461)},
+ {UINT64CONST(4193189667727651020), UINT64CONST(79310682416114038)}, {UINT64CONST(14464859121514339583), UINT64CONST(99138353020142547)},
+ {UINT64CONST(13469387883465536574), UINT64CONST(123922941275178184)}, {UINT64CONST(8418367427165960359), UINT64CONST(77451838296986365)},
+ {UINT64CONST(15134645302384838353), UINT64CONST(96814797871232956)}, {UINT64CONST(471562554271496325), UINT64CONST(121018497339041196)},
+ {UINT64CONST(9518098633274461011), UINT64CONST(75636560836900747)}, {UINT64CONST(7285937273165688360), UINT64CONST(94545701046125934)},
+ {UINT64CONST(18330793628311886258), UINT64CONST(118182126307657417)}, {UINT64CONST(4539216990053847055), UINT64CONST(73863828942285886)},
+ {UINT64CONST(14897393274422084627), UINT64CONST(92329786177857357)}, {UINT64CONST(4786683537745442072), UINT64CONST(115412232722321697)},
+ {UINT64CONST(14520892257159371055), UINT64CONST(72132645451451060)}, {UINT64CONST(18151115321449213818), UINT64CONST(90165806814313825)},
+ {UINT64CONST(8853836096529353561), UINT64CONST(112707258517892282)}, {UINT64CONST(1843923083806916143), UINT64CONST(140884073147365353)},
+ {UINT64CONST(12681666973447792349), UINT64CONST(88052545717103345)}, {UINT64CONST(2017025661527576725), UINT64CONST(110065682146379182)},
+ {UINT64CONST(11744654113764246714), UINT64CONST(137582102682973977)}, {UINT64CONST(422879793461572340), UINT64CONST(85988814176858736)},
+ {UINT64CONST(528599741826965425), UINT64CONST(107486017721073420)}, {UINT64CONST(660749677283706782), UINT64CONST(134357522151341775)},
+ {UINT64CONST(7330497575943398595), UINT64CONST(83973451344588609)}, {UINT64CONST(13774807988356636147), UINT64CONST(104966814180735761)},
+ {UINT64CONST(3383451930163631472), UINT64CONST(131208517725919702)}, {UINT64CONST(15949715511634433382), UINT64CONST(82005323578699813)},
+ {UINT64CONST(6102086334260878016), UINT64CONST(102506654473374767)}, {UINT64CONST(3015921899398709616), UINT64CONST(128133318091718459)},
+ {UINT64CONST(18025852251620051174), UINT64CONST(80083323807324036)}, {UINT64CONST(4085571240815512351), UINT64CONST(100104154759155046)},
+ {UINT64CONST(14330336087874166247), UINT64CONST(125130193448943807)}, {UINT64CONST(15873989082562435760), UINT64CONST(78206370905589879)},
+ {UINT64CONST(15230800334775656796), UINT64CONST(97757963631987349)}, {UINT64CONST(5203442363187407284), UINT64CONST(122197454539984187)},
+ {UINT64CONST(946308467778435600), UINT64CONST(76373409087490117)}, {UINT64CONST(5794571603150432404), UINT64CONST(95466761359362646)},
+ {UINT64CONST(16466586540792816313), UINT64CONST(119333451699203307)}, {UINT64CONST(7985773578781816244), UINT64CONST(74583407312002067)},
+ {UINT64CONST(5370530955049882401), UINT64CONST(93229259140002584)}, {UINT64CONST(6713163693812353001), UINT64CONST(116536573925003230)},
+ {UINT64CONST(18030785363914884337), UINT64CONST(72835358703127018)}, {UINT64CONST(13315109668038829614), UINT64CONST(91044198378908773)},
+ {UINT64CONST(2808829029766373305), UINT64CONST(113805247973635967)}, {UINT64CONST(17346094342490130344), UINT64CONST(142256559967044958)},
+ {UINT64CONST(6229622945628943561), UINT64CONST(88910349979403099)}, {UINT64CONST(3175342663608791547), UINT64CONST(111137937474253874)},
+ {UINT64CONST(13192550366365765242), UINT64CONST(138922421842817342)}, {UINT64CONST(3633657960551215372), UINT64CONST(86826513651760839)},
+ {UINT64CONST(18377130505971182927), UINT64CONST(108533142064701048)}, {UINT64CONST(4524669058754427043), UINT64CONST(135666427580876311)},
+ {UINT64CONST(9745447189362598758), UINT64CONST(84791517238047694)}, {UINT64CONST(2958436949848472639), UINT64CONST(105989396547559618)},
+ {UINT64CONST(12921418224165366607), UINT64CONST(132486745684449522)}, {UINT64CONST(12687572408530742033), UINT64CONST(82804216052780951)},
+ {UINT64CONST(11247779492236039638), UINT64CONST(103505270065976189)}, {UINT64CONST(224666310012885835), UINT64CONST(129381587582470237)},
+ {UINT64CONST(2446259452971747599), UINT64CONST(80863492239043898)}, {UINT64CONST(12281196353069460307), UINT64CONST(101079365298804872)},
+ {UINT64CONST(15351495441336825384), UINT64CONST(126349206623506090)}, {UINT64CONST(14206370669262903769), UINT64CONST(78968254139691306)},
+ {UINT64CONST(8534591299723853903), UINT64CONST(98710317674614133)}, {UINT64CONST(15279925143082205283), UINT64CONST(123387897093267666)},
+ {UINT64CONST(14161639232853766206), UINT64CONST(77117435683292291)}, {UINT64CONST(13090363022639819853), UINT64CONST(96396794604115364)},
+ {UINT64CONST(16362953778299774816), UINT64CONST(120495993255144205)}, {UINT64CONST(12532689120651053212), UINT64CONST(75309995784465128)},
+ {UINT64CONST(15665861400813816515), UINT64CONST(94137494730581410)}, {UINT64CONST(10358954714162494836), UINT64CONST(117671868413226763)},
+ {UINT64CONST(4168503687137865320), UINT64CONST(73544917758266727)}, {UINT64CONST(598943590494943747), UINT64CONST(91931147197833409)},
+ {UINT64CONST(5360365506546067587), UINT64CONST(114913933997291761)}, {UINT64CONST(11312142901609972388), UINT64CONST(143642417496614701)},
+ {UINT64CONST(9375932322719926695), UINT64CONST(89776510935384188)}, {UINT64CONST(11719915403399908368), UINT64CONST(112220638669230235)},
+ {UINT64CONST(10038208235822497557), UINT64CONST(140275798336537794)}, {UINT64CONST(10885566165816448877), UINT64CONST(87672373960336121)},
+ {UINT64CONST(18218643725697949000), UINT64CONST(109590467450420151)}, {UINT64CONST(18161618638695048346), UINT64CONST(136988084313025189)},
+ {UINT64CONST(13656854658398099168), UINT64CONST(85617552695640743)}, {UINT64CONST(12459382304570236056), UINT64CONST(107021940869550929)},
+ {UINT64CONST(1739169825430631358), UINT64CONST(133777426086938662)}, {UINT64CONST(14922039196176308311), UINT64CONST(83610891304336663)},
+ {UINT64CONST(14040862976792997485), UINT64CONST(104513614130420829)}, {UINT64CONST(3716020665709083144), UINT64CONST(130642017663026037)},
+ {UINT64CONST(4628355925281870917), UINT64CONST(81651261039391273)}, {UINT64CONST(10397130925029726550), UINT64CONST(102064076299239091)},
+ {UINT64CONST(8384727637859770284), UINT64CONST(127580095374048864)}, {UINT64CONST(5240454773662356427), UINT64CONST(79737559608780540)},
+ {UINT64CONST(6550568467077945534), UINT64CONST(99671949510975675)}, {UINT64CONST(3576524565420044014), UINT64CONST(124589936888719594)},
+ {UINT64CONST(6847013871814915412), UINT64CONST(77868710555449746)}, {UINT64CONST(17782139376623420074), UINT64CONST(97335888194312182)},
+ {UINT64CONST(13004302183924499284), UINT64CONST(121669860242890228)}, {UINT64CONST(17351060901807587860), UINT64CONST(76043662651806392)},
+ {UINT64CONST(3242082053549933210), UINT64CONST(95054578314757991)}, {UINT64CONST(17887660622219580224), UINT64CONST(118818222893447488)},
+ {UINT64CONST(11179787888887237640), UINT64CONST(74261389308404680)}, {UINT64CONST(13974734861109047050), UINT64CONST(92826736635505850)},
+ {UINT64CONST(8245046539531533005), UINT64CONST(116033420794382313)}, {UINT64CONST(16682369133275677888), UINT64CONST(72520887996488945)},
+ {UINT64CONST(7017903361312433648), UINT64CONST(90651109995611182)}, {UINT64CONST(17995751238495317868), UINT64CONST(113313887494513977)},
+ {UINT64CONST(8659630992836983623), UINT64CONST(141642359368142472)}, {UINT64CONST(5412269370523114764), UINT64CONST(88526474605089045)},
+ {UINT64CONST(11377022731581281359), UINT64CONST(110658093256361306)}, {UINT64CONST(4997906377621825891), UINT64CONST(138322616570451633)},
+ {UINT64CONST(14652906532082110942), UINT64CONST(86451635356532270)}, {UINT64CONST(9092761128247862869), UINT64CONST(108064544195665338)},
+ {UINT64CONST(2142579373455052779), UINT64CONST(135080680244581673)}, {UINT64CONST(12868327154477877747), UINT64CONST(84425425152863545)},
+ {UINT64CONST(2250350887815183471), UINT64CONST(105531781441079432)}, {UINT64CONST(2812938609768979339), UINT64CONST(131914726801349290)},
+ {UINT64CONST(6369772649532999991), UINT64CONST(82446704250843306)}, {UINT64CONST(17185587848771025797), UINT64CONST(103058380313554132)},
+ {UINT64CONST(3035240737254230630), UINT64CONST(128822975391942666)}, {UINT64CONST(6508711479211282048), UINT64CONST(80514359619964166)},
+ {UINT64CONST(17359261385868878368), UINT64CONST(100642949524955207)}, {UINT64CONST(17087390713908710056), UINT64CONST(125803686906194009)},
+ {UINT64CONST(3762090168551861929), UINT64CONST(78627304316371256)}, {UINT64CONST(4702612710689827411), UINT64CONST(98284130395464070)},
+ {UINT64CONST(15101637925217060072), UINT64CONST(122855162994330087)}, {UINT64CONST(16356052730901744401), UINT64CONST(76784476871456304)},
+ {UINT64CONST(1998321839917628885), UINT64CONST(95980596089320381)}, {UINT64CONST(7109588318324424010), UINT64CONST(119975745111650476)},
+ {UINT64CONST(13666864735807540814), UINT64CONST(74984840694781547)}, {UINT64CONST(12471894901332038114), UINT64CONST(93731050868476934)},
+ {UINT64CONST(6366496589810271835), UINT64CONST(117163813585596168)}, {UINT64CONST(3979060368631419896), UINT64CONST(73227383490997605)},
+ {UINT64CONST(9585511479216662775), UINT64CONST(91534229363747006)}, {UINT64CONST(2758517312166052660), UINT64CONST(114417786704683758)},
+ {UINT64CONST(12671518677062341634), UINT64CONST(143022233380854697)}, {UINT64CONST(1002170145522881665), UINT64CONST(89388895863034186)},
+ {UINT64CONST(10476084718758377889), UINT64CONST(111736119828792732)}, {UINT64CONST(13095105898447972362), UINT64CONST(139670149785990915)},
+ {UINT64CONST(5878598177316288774), UINT64CONST(87293843616244322)}, {UINT64CONST(16571619758500136775), UINT64CONST(109117304520305402)},
+ {UINT64CONST(11491152661270395161), UINT64CONST(136396630650381753)}, {UINT64CONST(264441385652915120), UINT64CONST(85247894156488596)},
+ {UINT64CONST(330551732066143900), UINT64CONST(106559867695610745)}, {UINT64CONST(5024875683510067779), UINT64CONST(133199834619513431)},
+ {UINT64CONST(10058076329834874218), UINT64CONST(83249896637195894)}, {UINT64CONST(3349223375438816964), UINT64CONST(104062370796494868)},
+ {UINT64CONST(4186529219298521205), UINT64CONST(130077963495618585)}, {UINT64CONST(14145795808130045513), UINT64CONST(81298727184761615)},
+ {UINT64CONST(13070558741735168987), UINT64CONST(101623408980952019)}, {UINT64CONST(11726512408741573330), UINT64CONST(127029261226190024)},
+ {UINT64CONST(7329070255463483331), UINT64CONST(79393288266368765)}, {UINT64CONST(13773023837756742068), UINT64CONST(99241610332960956)},
+ {UINT64CONST(17216279797195927585), UINT64CONST(124052012916201195)}, {UINT64CONST(8454331864033760789), UINT64CONST(77532508072625747)},
+ {UINT64CONST(5956228811614813082), UINT64CONST(96915635090782184)}, {UINT64CONST(7445286014518516353), UINT64CONST(121144543863477730)},
+ {UINT64CONST(9264989777501460624), UINT64CONST(75715339914673581)}, {UINT64CONST(16192923240304213684), UINT64CONST(94644174893341976)},
+ {UINT64CONST(1794409976670715490), UINT64CONST(118305218616677471)}, {UINT64CONST(8039035263060279037), UINT64CONST(73940761635423419)},
+ {UINT64CONST(5437108060397960892), UINT64CONST(92425952044279274)}, {UINT64CONST(16019757112352226923), UINT64CONST(115532440055349092)},
+ {UINT64CONST(788976158365366019), UINT64CONST(72207775034593183)}, {UINT64CONST(14821278253238871236), UINT64CONST(90259718793241478)},
+ {UINT64CONST(9303225779693813237), UINT64CONST(112824648491551848)}, {UINT64CONST(11629032224617266546), UINT64CONST(141030810614439810)},
+ {UINT64CONST(11879831158813179495), UINT64CONST(88144256634024881)}, {UINT64CONST(1014730893234310657), UINT64CONST(110180320792531102)},
+ {UINT64CONST(10491785653397664129), UINT64CONST(137725400990663877)}, {UINT64CONST(8863209042587234033), UINT64CONST(86078375619164923)},
+ {UINT64CONST(6467325284806654637), UINT64CONST(107597969523956154)}, {UINT64CONST(17307528642863094104), UINT64CONST(134497461904945192)},
+ {UINT64CONST(10817205401789433815), UINT64CONST(84060913690590745)}, {UINT64CONST(18133192770664180173), UINT64CONST(105076142113238431)},
+ {UINT64CONST(18054804944902837312), UINT64CONST(131345177641548039)}, {UINT64CONST(18201782118205355176), UINT64CONST(82090736025967524)},
+ {UINT64CONST(4305483574047142354), UINT64CONST(102613420032459406)}, {UINT64CONST(14605226504413703751), UINT64CONST(128266775040574257)},
+ {UINT64CONST(2210737537617482988), UINT64CONST(80166734400358911)}, {UINT64CONST(16598479977304017447), UINT64CONST(100208418000448638)},
+ {UINT64CONST(11524727934775246001), UINT64CONST(125260522500560798)}, {UINT64CONST(2591268940807140847), UINT64CONST(78287826562850499)},
+ {UINT64CONST(17074144231291089770), UINT64CONST(97859783203563123)}, {UINT64CONST(16730994270686474309), UINT64CONST(122324729004453904)},
+ {UINT64CONST(10456871419179046443), UINT64CONST(76452955627783690)}, {UINT64CONST(3847717237119032246), UINT64CONST(95566194534729613)},
+ {UINT64CONST(9421332564826178211), UINT64CONST(119457743168412016)}, {UINT64CONST(5888332853016361382), UINT64CONST(74661089480257510)},
+ {UINT64CONST(16583788103125227536), UINT64CONST(93326361850321887)}, {UINT64CONST(16118049110479146516), UINT64CONST(116657952312902359)},
+ {UINT64CONST(16991309721690548428), UINT64CONST(72911220195563974)}, {UINT64CONST(12015765115258409727), UINT64CONST(91139025244454968)},
+ {UINT64CONST(15019706394073012159), UINT64CONST(113923781555568710)}, {UINT64CONST(9551260955736489391), UINT64CONST(142404726944460888)},
+ {UINT64CONST(5969538097335305869), UINT64CONST(89002954340288055)}, {UINT64CONST(2850236603241744433), UINT64CONST(111253692925360069)}
+};
+
+#endif /* RYU_D2S_FULL_TABLE_H */
diff --git a/src/common/d2s_intrinsics.h b/src/common/d2s_intrinsics.h
new file mode 100644
index 0000000000..db70395f82
--- /dev/null
+++ b/src/common/d2s_intrinsics.h
@@ -0,0 +1,202 @@
+/*---------------------------------------------------------------------------
+ *
+ * Ryu floating-point output for double precision.
+ *
+ * Portions Copyright (c) 2018, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ * src/common/d2s_intrinsics.h
+ *
+ * This is a modification of code taken from github.com/ulfjack/ryu under the
+ * terms of the Boost license (not the Apache license). The original copyright
+ * notice follows:
+ *
+ * Copyright 2018 Ulf Adams
+ *
+ * The contents of this file may be used under the terms of the Apache
+ * License, Version 2.0.
+ *
+ * (See accompanying file LICENSE-Apache or copy at
+ * http://www.apache.org/licenses/LICENSE-2.0)
+ *
+ * Alternatively, the contents of this file may be used under the terms of the
+ * Boost Software License, Version 1.0.
+ *
+ * (See accompanying file LICENSE-Boost or copy at
+ * https://www.boost.org/LICENSE_1_0.txt)
+ *
+ * Unless required by applicable law or agreed to in writing, this software is
+ * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.
+ *
+ *---------------------------------------------------------------------------
+ */
+#ifndef RYU_D2S_INTRINSICS_H
+#define RYU_D2S_INTRINSICS_H
+
+#if defined(HAS_64_BIT_INTRINSICS)
+
+#include <intrin.h>
+
+static inline uint64
+umul128(const uint64 a, const uint64 b, uint64 *const productHi)
+{
+ return _umul128(a, b, productHi);
+}
+
+static inline uint64
+shiftright128(const uint64 lo, const uint64 hi, const uint32 dist)
+{
+ /*
+ * For the __shiftright128 intrinsic, the shift value is always modulo 64.
+ * In the current implementation of the double-precision version of Ryu,
+ * the shift value is always < 64. (In the case RYU_OPTIMIZE_SIZE == 0,
+ * the shift value is in the range [49, 58]. Otherwise in the range [2,
+ * 59].) Check this here in case a future change requires larger shift
+ * values. In this case this function needs to be adjusted.
+ */
+ Assert(dist < 64);
+ return __shiftright128(lo, hi, (unsigned char) dist);
+}
+
+#else /* defined(HAS_64_BIT_INTRINSICS) */
+
+static inline uint64
+umul128(const uint64 a, const uint64 b, uint64 *const productHi)
+{
+ /*
+ * The casts here help MSVC to avoid calls to the __allmul library
+ * function.
+ */
+ const uint32 aLo = (uint32) a;
+ const uint32 aHi = (uint32) (a >> 32);
+ const uint32 bLo = (uint32) b;
+ const uint32 bHi = (uint32) (b >> 32);
+
+ const uint64 b00 = (uint64) aLo * bLo;
+ const uint64 b01 = (uint64) aLo * bHi;
+ const uint64 b10 = (uint64) aHi * bLo;
+ const uint64 b11 = (uint64) aHi * bHi;
+
+ const uint32 b00Lo = (uint32) b00;
+ const uint32 b00Hi = (uint32) (b00 >> 32);
+
+ const uint64 mid1 = b10 + b00Hi;
+ const uint32 mid1Lo = (uint32) (mid1);
+ const uint32 mid1Hi = (uint32) (mid1 >> 32);
+
+ const uint64 mid2 = b01 + mid1Lo;
+ const uint32 mid2Lo = (uint32) (mid2);
+ const uint32 mid2Hi = (uint32) (mid2 >> 32);
+
+ const uint64 pHi = b11 + mid1Hi + mid2Hi;
+ const uint64 pLo = ((uint64) mid2Lo << 32) + b00Lo;
+
+ *productHi = pHi;
+ return pLo;
+}
+
+static inline uint64
+shiftright128(const uint64 lo, const uint64 hi, const uint32 dist)
+{
+ /* We don't need to handle the case dist >= 64 here (see above). */
+ Assert(dist < 64);
+#if defined(RYU_OPTIMIZE_SIZE) || !defined(RYU_32_BIT_PLATFORM)
+ Assert(dist > 0);
+ return (hi << (64 - dist)) | (lo >> dist);
+#else
+ /* Avoid a 64-bit shift by taking advantage of the range of shift values. */
+ Assert(dist >= 32);
+ return (hi << (64 - dist)) | ((uint32) (lo >> 32) >> (dist - 32));
+#endif
+}
+
+#endif /* // defined(HAS_64_BIT_INTRINSICS) */
+
+#ifdef RYU_32_BIT_PLATFORM
+
+/* Returns the high 64 bits of the 128-bit product of a and b. */
+static inline uint64
+umulh(const uint64 a, const uint64 b)
+{
+ /*
+ * Reuse the umul128 implementation. Optimizers will likely eliminate the
+ * instructions used to compute the low part of the product.
+ */
+ uint64 hi;
+
+ umul128(a, b, &hi);
+ return hi;
+}
+
+/*----
+ * On 32-bit platforms, compilers typically generate calls to library
+ * functions for 64-bit divisions, even if the divisor is a constant.
+ *
+ * E.g.:
+ * https://bugs.llvm.org/show_bug.cgi?id=37932
+ * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=17958
+ * https://gcc.gnu.org/bugzilla/show_bug.cgi?id=37443
+ *
+ * The functions here perform division-by-constant using multiplications
+ * in the same way as 64-bit compilers would do.
+ *
+ * NB:
+ * The multipliers and shift values are the ones generated by clang x64
+ * for expressions like x/5, x/10, etc.
+ *----
+ */
+
+static inline uint64
+div5(const uint64 x)
+{
+ return umulh(x, 0xCCCCCCCCCCCCCCCDu) >> 2;
+}
+
+static inline uint64
+div10(const uint64 x)
+{
+ return umulh(x, 0xCCCCCCCCCCCCCCCDu) >> 3;
+}
+
+static inline uint64
+div100(const uint64 x)
+{
+ return umulh(x >> 2, 0x28F5C28F5C28F5C3u) >> 2;
+}
+
+static inline uint64
+div1e8(const uint64 x)
+{
+ return umulh(x, 0xABCC77118461CEFDu) >> 26;
+}
+
+#else /* RYU_32_BIT_PLATFORM */
+
+static inline uint64
+div5(const uint64 x)
+{
+ return x / 5;
+}
+
+static inline uint64
+div10(const uint64 x)
+{
+ return x / 10;
+}
+
+static inline uint64
+div100(const uint64 x)
+{
+ return x / 100;
+}
+
+static inline uint64
+div1e8(const uint64 x)
+{
+ return x / 100000000;
+}
+
+#endif /* RYU_32_BIT_PLATFORM */
+
+#endif /* RYU_D2S_INTRINSICS_H */
diff --git a/src/common/digit_table.h b/src/common/digit_table.h
new file mode 100644
index 0000000000..483aa17142
--- /dev/null
+++ b/src/common/digit_table.h
@@ -0,0 +1,21 @@
+#ifndef RYU_DIGIT_TABLE_H
+#define RYU_DIGIT_TABLE_H
+
+/*
+ * A table of all two-digit numbers. This is used to speed up decimal digit
+ * generation by copying pairs of digits into the final output.
+ */
+static const char DIGIT_TABLE[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'
+};
+
+#endif /* RYU_DIGIT_TABLE_H */
diff --git a/src/common/f2s.c b/src/common/f2s.c
new file mode 100644
index 0000000000..b509402dc5
--- /dev/null
+++ b/src/common/f2s.c
@@ -0,0 +1,668 @@
+/*---------------------------------------------------------------------------
+ *
+ * Ryu floating-point output for single precision.
+ *
+ * Portions Copyright (c) 2018, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ * src/common/f2s.c
+ *
+ * This is a modification of code taken from github.com/ulfjack/ryu under the
+ * terms of the Boost license (not the Apache license). The original copyright
+ * notice follows:
+ *
+ * Copyright 2018 Ulf Adams
+ *
+ * The contents of this file may be used under the terms of the Apache
+ * License, Version 2.0.
+ *
+ * (See accompanying file LICENSE-Apache or copy at
+ * http://www.apache.org/licenses/LICENSE-2.0)
+ *
+ * Alternatively, the contents of this file may be used under the terms of the
+ * Boost Software License, Version 1.0.
+ *
+ * (See accompanying file LICENSE-Boost or copy at
+ * https://www.boost.org/LICENSE_1_0.txt)
+ *
+ * Unless required by applicable law or agreed to in writing, this software is
+ * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.
+ *
+ *---------------------------------------------------------------------------
+ */
+
+#ifndef FRONTEND
+#include "postgres.h"
+#else
+#include "postgres_fe.h"
+#endif
+
+#include "common/ryu.h"
+
+#include "ryu_common.h"
+#include "digit_table.h"
+
+#define FLOAT_MANTISSA_BITS 23
+#define FLOAT_EXPONENT_BITS 8
+#define FLOAT_BIAS 127
+
+/* This table is generated by PrintFloatLookupTable. */
+#define FLOAT_POW5_INV_BITCOUNT 59
+static const uint64 FLOAT_POW5_INV_SPLIT[31] = {
+ UINT64CONST(576460752303423489), UINT64CONST(461168601842738791), UINT64CONST(368934881474191033), UINT64CONST(295147905179352826),
+ UINT64CONST(472236648286964522), UINT64CONST(377789318629571618), UINT64CONST(302231454903657294), UINT64CONST(483570327845851670),
+ UINT64CONST(386856262276681336), UINT64CONST(309485009821345069), UINT64CONST(495176015714152110), UINT64CONST(396140812571321688),
+ UINT64CONST(316912650057057351), UINT64CONST(507060240091291761), UINT64CONST(405648192073033409), UINT64CONST(324518553658426727),
+ UINT64CONST(519229685853482763), UINT64CONST(415383748682786211), UINT64CONST(332306998946228969), UINT64CONST(531691198313966350),
+ UINT64CONST(425352958651173080), UINT64CONST(340282366920938464), UINT64CONST(544451787073501542), UINT64CONST(435561429658801234),
+ UINT64CONST(348449143727040987), UINT64CONST(557518629963265579), UINT64CONST(446014903970612463), UINT64CONST(356811923176489971),
+ UINT64CONST(570899077082383953), UINT64CONST(456719261665907162), UINT64CONST(365375409332725730)
+};
+#define FLOAT_POW5_BITCOUNT 61
+static const uint64 FLOAT_POW5_SPLIT[47] = {
+ UINT64CONST(1152921504606846976), UINT64CONST(1441151880758558720), UINT64CONST(1801439850948198400), UINT64CONST(2251799813685248000),
+ UINT64CONST(1407374883553280000), UINT64CONST(1759218604441600000), UINT64CONST(2199023255552000000), UINT64CONST(1374389534720000000),
+ UINT64CONST(1717986918400000000), UINT64CONST(2147483648000000000), UINT64CONST(1342177280000000000), UINT64CONST(1677721600000000000),
+ UINT64CONST(2097152000000000000), UINT64CONST(1310720000000000000), UINT64CONST(1638400000000000000), UINT64CONST(2048000000000000000),
+ UINT64CONST(1280000000000000000), UINT64CONST(1600000000000000000), UINT64CONST(2000000000000000000), UINT64CONST(1250000000000000000),
+ UINT64CONST(1562500000000000000), UINT64CONST(1953125000000000000), UINT64CONST(1220703125000000000), UINT64CONST(1525878906250000000),
+ UINT64CONST(1907348632812500000), UINT64CONST(1192092895507812500), UINT64CONST(1490116119384765625), UINT64CONST(1862645149230957031),
+ UINT64CONST(1164153218269348144), UINT64CONST(1455191522836685180), UINT64CONST(1818989403545856475), UINT64CONST(2273736754432320594),
+ UINT64CONST(1421085471520200371), UINT64CONST(1776356839400250464), UINT64CONST(2220446049250313080), UINT64CONST(1387778780781445675),
+ UINT64CONST(1734723475976807094), UINT64CONST(2168404344971008868), UINT64CONST(1355252715606880542), UINT64CONST(1694065894508600678),
+ UINT64CONST(2117582368135750847), UINT64CONST(1323488980084844279), UINT64CONST(1654361225106055349), UINT64CONST(2067951531382569187),
+ UINT64CONST(1292469707114105741), UINT64CONST(1615587133892632177), UINT64CONST(2019483917365790221)
+};
+
+static inline uint32
+pow5Factor(uint32 value)
+{
+ uint32 count = 0;
+
+ for (;;)
+ {
+ uint32 q;
+ uint32 r;
+
+ Assert(value != 0);
+ q = value / 5;
+ r = value % 5;
+
+ if (r != 0)
+ break;
+
+ value = q;
+ ++count;
+ }
+ return count;
+}
+
+/* Returns true if value is divisible by 5^p. */
+static inline bool
+multipleOfPowerOf5(const uint32 value, const uint32 p)
+{
+ return pow5Factor(value) >= p;
+}
+
+/* Returns true if value is divisible by 2^p. */
+static inline bool
+multipleOfPowerOf2(const uint32 value, const uint32 p)
+{
+ /* return __builtin_ctz(value) >= p; */
+ return (value & ((1u << p) - 1)) == 0;
+}
+
+/*
+ * It seems to be slightly faster to avoid uint128_t here, although the
+ * generated code for uint128_t looks slightly nicer.
+ */
+static inline uint32
+mulShift(const uint32 m, const uint64 factor, const int32 shift)
+{
+ /*
+ * The casts here help MSVC to avoid calls to the __allmul library
+ * function.
+ */
+ const uint32 factorLo = (uint32) (factor);
+ const uint32 factorHi = (uint32) (factor >> 32);
+ const uint64 bits0 = (uint64) m * factorLo;
+ const uint64 bits1 = (uint64) m * factorHi;
+
+ Assert(shift > 32);
+
+#ifdef RYU_32_BIT_PLATFORM
+ {
+ /*
+ * On 32-bit platforms we can avoid a 64-bit shift-right since we only
+ * need the upper 32 bits of the result and the shift value is > 32.
+ */
+ const uint32 bits0Hi = (uint32) (bits0 >> 32);
+ uint32 bits1Lo = (uint32) (bits1);
+ uint32 bits1Hi = (uint32) (bits1 >> 32);
+ int32 s;
+
+ bits1Lo += bits0Hi;
+ bits1Hi += (bits1Lo < bits0Hi);
+
+ s = shift - 32;
+ return (bits1Hi << (32 - s)) | (bits1Lo >> s);
+ }
+#else /* RYU_32_BIT_PLATFORM */
+ {
+ const uint64 sum = (bits0 >> 32) + bits1;
+ const uint64 shiftedSum = sum >> (shift - 32);
+
+ Assert(shiftedSum <= UINT32_MAX);
+ return (uint32) shiftedSum;
+ }
+#endif /* RYU_32_BIT_PLATFORM */
+}
+
+static inline uint32
+mulPow5InvDivPow2(const uint32 m, const uint32 q, const int32 j)
+{
+ return mulShift(m, FLOAT_POW5_INV_SPLIT[q], j);
+}
+
+static inline uint32
+mulPow5divPow2(const uint32 m, const uint32 i, const int32 j)
+{
+ return mulShift(m, FLOAT_POW5_SPLIT[i], j);
+}
+
+static inline uint32
+decimalLength(const uint32 v)
+{
+ /* Function precondition: v is not a 10-digit number. */
+ /* (9 digits are sufficient for round-tripping.) */
+ Assert(v < 1000000000);
+ if (v >= 100000000)
+ {
+ return 9;
+ }
+ if (v >= 10000000)
+ {
+ return 8;
+ }
+ if (v >= 1000000)
+ {
+ return 7;
+ }
+ if (v >= 100000)
+ {
+ return 6;
+ }
+ if (v >= 10000)
+ {
+ return 5;
+ }
+ if (v >= 1000)
+ {
+ return 4;
+ }
+ if (v >= 100)
+ {
+ return 3;
+ }
+ if (v >= 10)
+ {
+ return 2;
+ }
+ return 1;
+}
+
+/* A floating decimal representing m * 10^e. */
+typedef struct floating_decimal_32
+{
+ uint32 mantissa;
+ int32 exponent;
+} floating_decimal_32;
+
+static inline floating_decimal_32
+f2d(const uint32 ieeeMantissa, const uint32 ieeeExponent)
+{
+ int32 e2;
+ uint32 m2;
+
+ if (ieeeExponent == 0)
+ {
+ /* We subtract 2 so that the bounds computation has 2 additional bits. */
+ e2 = 1 - FLOAT_BIAS - FLOAT_MANTISSA_BITS - 2;
+ m2 = ieeeMantissa;
+ }
+ else
+ {
+ e2 = ieeeExponent - FLOAT_BIAS - FLOAT_MANTISSA_BITS - 2;
+ m2 = (1u << FLOAT_MANTISSA_BITS) | ieeeMantissa;
+ }
+
+ {
+ const bool even = (m2 & 1) == 0;
+ const bool acceptBounds = even;
+
+ /* Step 2: Determine the interval of legal decimal representations. */
+ const uint32 mv = 4 * m2;
+ const uint32 mp = 4 * m2 + 2;
+
+ /* Implicit bool -> int conversion. True is 1, false is 0. */
+ const uint32 mmShift = ieeeMantissa != 0 || ieeeExponent <= 1;
+ const uint32 mm = 4 * m2 - 1 - mmShift;
+
+ /* Step 3: Convert to a decimal power base using 64-bit arithmetic. */
+ uint32 vr,
+ vp,
+ vm;
+ int32 e10;
+ bool vmIsTrailingZeros = false;
+ bool vrIsTrailingZeros = false;
+ uint8_t lastRemovedDigit = 0;
+
+ if (e2 >= 0)
+ {
+ const uint32 q = log10Pow2(e2);
+ const int32 k = FLOAT_POW5_INV_BITCOUNT + pow5bits(q) - 1;
+ const int32 i = -e2 + q + k;
+
+ e10 = q;
+ vr = mulPow5InvDivPow2(mv, q, i);
+ vp = mulPow5InvDivPow2(mp, q, i);
+ vm = mulPow5InvDivPow2(mm, q, i);
+
+ if (q != 0 && (vp - 1) / 10 <= vm / 10)
+ {
+ /*
+ * We need to know one removed digit even if we are not going
+ * to loop below. We could use q = X - 1 above, except that
+ * would require 33 bits for the result, and we've found that
+ * 32-bit arithmetic is faster even on 64-bit machines.
+ */
+ const int32 l = FLOAT_POW5_INV_BITCOUNT + pow5bits(q - 1) - 1;
+
+ lastRemovedDigit = (uint8_t) (mulPow5InvDivPow2(mv, q - 1, -e2 + q - 1 + l) % 10);
+ }
+ if (q <= 9)
+ {
+ /*
+ * The largest power of 5 that fits in 24 bits is 5^10, but q
+ * <= 9 seems to be safe as well.
+ *
+ * Only one of mp, mv, and mm can be a multiple of 5, if any.
+ */
+ if (mv % 5 == 0)
+ {
+ vrIsTrailingZeros = multipleOfPowerOf5(mv, q);
+ }
+ else if (acceptBounds)
+ {
+ vmIsTrailingZeros = multipleOfPowerOf5(mm, q);
+ }
+ else
+ {
+ vp -= multipleOfPowerOf5(mp, q);
+ }
+ }
+ }
+ else
+ {
+ const uint32 q = log10Pow5(-e2);
+ const int32 i = -e2 - q;
+ const int32 k = pow5bits(i) - FLOAT_POW5_BITCOUNT;
+ int32 j = q - k;
+
+ e10 = q + e2;
+
+ vr = mulPow5divPow2(mv, i, j);
+ vp = mulPow5divPow2(mp, i, j);
+ vm = mulPow5divPow2(mm, i, j);
+
+ if (q != 0 && (vp - 1) / 10 <= vm / 10)
+ {
+ j = q - 1 - (pow5bits(i + 1) - FLOAT_POW5_BITCOUNT);
+ lastRemovedDigit = (uint8_t) (mulPow5divPow2(mv, i + 1, j) % 10);
+ }
+ if (q <= 1)
+ {
+ /*
+ * {vr,vp,vm} is trailing zeros if {mv,mp,mm} has at least q
+ * trailing 0 bits.
+ */
+ /* mv = 4 * m2, so it always has at least two trailing 0 bits. */
+ vrIsTrailingZeros = true;
+ if (acceptBounds)
+ {
+ /*
+ * mm = mv - 1 - mmShift, so it has 1 trailing 0 bit iff
+ * mmShift == 1.
+ */
+ vmIsTrailingZeros = mmShift == 1;
+ }
+ else
+ {
+ /*
+ * mp = mv + 2, so it always has at least one trailing 0
+ * bit.
+ */
+ --vp;
+ }
+ }
+ else if (q < 31)
+ {
+ /* TODO(ulfjack):Use a tighter bound here. */
+ vrIsTrailingZeros = multipleOfPowerOf2(mv, q - 1);
+ }
+ }
+
+ /*
+ * Step 4: Find the shortest decimal representation in the interval of
+ * legal representations.
+ */
+ {
+ uint32 removed = 0;
+ uint32 output;
+
+ if (vmIsTrailingZeros || vrIsTrailingZeros)
+ {
+ /* General case, which happens rarely (~4.0%). */
+ while (vp / 10 > vm / 10)
+ {
+ vmIsTrailingZeros &= vm - (vm / 10) * 10 == 0;
+ vrIsTrailingZeros &= lastRemovedDigit == 0;
+ lastRemovedDigit = (uint8_t) (vr % 10);
+ vr /= 10;
+ vp /= 10;
+ vm /= 10;
+ ++removed;
+ }
+ if (vmIsTrailingZeros)
+ {
+ while (vm % 10 == 0)
+ {
+ vrIsTrailingZeros &= lastRemovedDigit == 0;
+ lastRemovedDigit = (uint8_t) (vr % 10);
+ vr /= 10;
+ vp /= 10;
+ vm /= 10;
+ ++removed;
+ }
+ }
+
+ if (vrIsTrailingZeros && lastRemovedDigit == 5 && vr % 2 == 0)
+ {
+ /* Round even if the exact number is .....50..0. */
+ lastRemovedDigit = 4;
+ }
+
+ /*
+ * We need to take vr + 1 if vr is outside bounds or we need
+ * to round up.
+ */
+ output = vr + ((vr == vm && (!acceptBounds || !vmIsTrailingZeros)) || lastRemovedDigit >= 5);
+ }
+ else
+ {
+ /*
+ * Specialized for the common case (~96.0%). Percentages below
+ * are relative to this.
+ *
+ * Loop iterations below (approximately): 0: 13.6%, 1: 70.7%,
+ * 2: 14.1%, 3: 1.39%, 4: 0.14%, 5+: 0.01%
+ */
+ while (vp / 10 > vm / 10)
+ {
+ lastRemovedDigit = (uint8_t) (vr % 10);
+ vr /= 10;
+ vp /= 10;
+ vm /= 10;
+ ++removed;
+ }
+
+ /*
+ * We need to take vr + 1 if vr is outside bounds or we need
+ * to round up.
+ */
+ output = vr + (vr == vm || lastRemovedDigit >= 5);
+ }
+
+ {
+ const int32 exp = e10 + removed;
+
+ floating_decimal_32 fd;
+
+ fd.exponent = exp;
+ fd.mantissa = output;
+ return fd;
+ }
+ }
+ }
+}
+
+static inline int
+to_chars_f(const floating_decimal_32 v, const uint32 olength, char *const result)
+{
+ /* Step 5: Print the decimal representation. */
+ int index = 0;
+
+ uint32 output = v.mantissa;
+ int32 exp = v.exponent;
+
+ /*----
+ *
+ * On entry, mantissa * 10^exp is the result to be output.
+ * Caller has already done the - sign if needed.
+ *
+ * We want to insert the point somewhere else, which might mean
+ * adding zeros:
+ *
+ * exp | format
+ * 1+ | ddddddddd000000
+ * 0 | ddddddddd
+ * -1 .. -len+1 | dddddddd.d to d.ddddddddd
+ * -len ... | 0.ddddddddd to 0.0000dddddd
+ */
+ uint32 i = 0;
+ int32 nexp = exp + olength;
+
+ if (nexp <= 0)
+ {
+ /* 0.0000ddddd */
+ index = 2 - nexp;
+ memset(result, '0', index);
+ result[1] = '.';
+ }
+ else if (exp < 0)
+ {
+ /*
+ * dddd.dddd; leave space at the start and move the '.' in after
+ */
+ index = 1;
+ }
+
+ while (output >= 10000)
+ {
+ const uint32 c = output - 10000 * (output / 10000);
+ const uint32 c0 = (c % 100) << 1;
+ const uint32 c1 = (c / 100) << 1;
+
+ output /= 10000;
+
+ memcpy(result + index + olength - i - 2, DIGIT_TABLE + c0, 2);
+ memcpy(result + index + olength - i - 4, DIGIT_TABLE + c1, 2);
+ i += 4;
+ }
+ if (output >= 100)
+ {
+ const uint32 c = (output % 100) << 1;
+
+ output /= 100;
+ memcpy(result + index + olength - i - 2, DIGIT_TABLE + c, 2);
+ i += 2;
+ }
+ if (output >= 10)
+ {
+ const uint32 c = output << 1;
+ memcpy(result + index + olength - i - 2, DIGIT_TABLE + c, 2);
+ }
+ else
+ {
+ result[index] = (char) ('0' + output);
+ }
+
+ if (index == 1)
+ {
+ memmove(result, result+1, nexp);
+ result[nexp] = '.';
+ index = olength + 1;
+ }
+ else if (exp >= 0)
+ {
+ if (exp > 0)
+ memset(result + olength, '0', exp);
+ index = olength + exp;
+ }
+ else
+ {
+ index = olength + (2 - nexp);
+ }
+
+ return index;
+}
+
+static inline int
+to_chars(const floating_decimal_32 v, const bool sign, char *const result)
+{
+ /* Step 5: Print the decimal representation. */
+ int index = 0;
+
+ uint32 output = v.mantissa;
+ const uint32 olength = decimalLength(output);
+ int32 exp = v.exponent + olength - 1;
+ uint32 i = 0;
+
+ if (sign)
+ result[index++] = '-';
+
+ if (exp >= -4 && exp < 6)
+ return to_chars_f(v, olength, result+index) + sign;
+
+ /*----
+ * Print the decimal digits.
+ * The following code is equivalent to:
+ *
+ * for (uint32 i = 0; i < olength - 1; ++i) {
+ * const uint32 c = output % 10; output /= 10;
+ * result[index + olength - i] = (char) ('0' + c);
+ * }
+ * result[index] = '0' + output % 10;
+ */
+
+
+ while (output >= 10000)
+ {
+ const uint32 c = output - 10000 * (output / 10000);
+ const uint32 c0 = (c % 100) << 1;
+ const uint32 c1 = (c / 100) << 1;
+
+ output /= 10000;
+
+ memcpy(result + index + olength - i - 1, DIGIT_TABLE + c0, 2);
+ memcpy(result + index + olength - i - 3, DIGIT_TABLE + c1, 2);
+ i += 4;
+ }
+ if (output >= 100)
+ {
+ const uint32 c = (output % 100) << 1;
+
+ output /= 100;
+ memcpy(result + index + olength - i - 1, DIGIT_TABLE + c, 2);
+ i += 2;
+ }
+ if (output >= 10)
+ {
+ const uint32 c = output << 1;
+
+ /*
+ * We can't use memcpy here: the decimal dot goes between these two
+ * digits.
+ */
+ result[index + olength - i] = DIGIT_TABLE[c + 1];
+ result[index] = DIGIT_TABLE[c];
+ }
+ else
+ {
+ result[index] = (char) ('0' + output);
+ }
+
+ /* Print decimal point if needed. */
+ if (olength > 1)
+ {
+ result[index + 1] = '.';
+ index += olength + 1;
+ }
+ else
+ {
+ ++index;
+ }
+
+ /* Print the exponent. */
+ result[index++] = 'e';
+ {
+ if (exp < 0)
+ {
+ result[index++] = '-';
+ exp = -exp;
+ }
+ else
+ result[index++] = '+';
+
+ memcpy(result + index, DIGIT_TABLE + 2 * exp, 2);
+ index += 2;
+ }
+
+ return index;
+}
+
+int
+ryu_f2s_buffered_n(float f, char *result)
+{
+ /*
+ * Step 1: Decode the floating-point number, and unify normalized and
+ * subnormal cases.
+ */
+ const uint32 bits = float_to_bits(f);
+
+ /* Decode bits into sign, mantissa, and exponent. */
+ const bool ieeeSign = ((bits >> (FLOAT_MANTISSA_BITS + FLOAT_EXPONENT_BITS)) & 1) != 0;
+ const uint32 ieeeMantissa = bits & ((1u << FLOAT_MANTISSA_BITS) - 1);
+ const uint32 ieeeExponent = (bits >> FLOAT_MANTISSA_BITS) & ((1u << FLOAT_EXPONENT_BITS) - 1);
+
+ /* Case distinction; exit early for the easy cases. */
+ if (ieeeExponent == ((1u << FLOAT_EXPONENT_BITS) - 1u) || (ieeeExponent == 0 && ieeeMantissa == 0))
+ {
+ return copy_special_str(result, ieeeSign, ieeeExponent, ieeeMantissa);
+ }
+
+ {
+ const floating_decimal_32 v = f2d(ieeeMantissa, ieeeExponent);
+
+ return to_chars(v, ieeeSign, result);
+ }
+}
+
+void
+ryu_f2s_buffered(float f, char *result)
+{
+ const int index = ryu_f2s_buffered_n(f, result);
+
+ /* Terminate the string. */
+ result[index] = '\0';
+}
+
+char *
+ryu_f2s(float f)
+{
+ char *const result = (char *) malloc(16);
+
+ ryu_f2s_buffered(f, result);
+ return result;
+}
diff --git a/src/common/ryu_common.h b/src/common/ryu_common.h
new file mode 100644
index 0000000000..c601c747a7
--- /dev/null
+++ b/src/common/ryu_common.h
@@ -0,0 +1,122 @@
+/*---------------------------------------------------------------------------
+ *
+ * Common routines for Ryu floating-point output.
+ *
+ * Portions Copyright (c) 2018, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ * src/common/ryu_common.h
+ *
+ * This is a modification of code taken from github.com/ulfjack/ryu under the
+ * terms of the Boost license (not the Apache license). The original copyright
+ * notice follows:
+ *
+ * Copyright 2018 Ulf Adams
+ *
+ * The contents of this file may be used under the terms of the Apache
+ * License, Version 2.0.
+ *
+ * (See accompanying file LICENSE-Apache or copy at
+ * http://www.apache.org/licenses/LICENSE-2.0)
+ *
+ * Alternatively, the contents of this file may be used under the terms of the
+ * Boost Software License, Version 1.0.
+ *
+ * (See accompanying file LICENSE-Boost or copy at
+ * https://www.boost.org/LICENSE_1_0.txt)
+ *
+ * Unless required by applicable law or agreed to in writing, this software is
+ * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.
+ *
+ *---------------------------------------------------------------------------
+ */
+#ifndef RYU_COMMON_H
+#define RYU_COMMON_H
+
+#if SIZEOF_LONG < 8
+#define RYU_32_BIT_PLATFORM
+#endif
+
+/* Returns e == 0 ? 1 : ceil(log_2(5^e)). */
+static inline uint32
+pow5bits(const int32 e)
+{
+ /*
+ * This approximation works up to the point that the multiplication
+ * overflows at e = 3529.
+ *
+ * If the multiplication were done in 64 bits, it would fail at 5^4004
+ * which is just greater than 2^9297.
+ */
+ Assert(e >= 0);
+ Assert(e <= 3528);
+ return ((((uint32) e) * 1217359) >> 19) + 1;
+}
+
+/* Returns floor(log_10(2^e)). */
+static inline int32
+log10Pow2(const int32 e)
+{
+ /*
+ * The first value this approximation fails for is 2^1651 which is just
+ * greater than 10^297.
+ */
+ Assert(e >= 0);
+ Assert(e <= 1650);
+ return (int32) ((((uint32) e) * 78913) >> 18);
+}
+
+/* Returns floor(log_10(5^e)). */
+static inline int32
+log10Pow5(const int32 e)
+{
+ /*
+ * The first value this approximation fails for is 5^2621 which is just
+ * greater than 10^1832.
+ */
+ Assert(e >= 0);
+ Assert(e <= 2620);
+ return (int32) ((((uint32) e) * 732923) >> 20);
+}
+
+static inline int
+copy_special_str(char *const result, const bool sign, const bool exponent, const bool mantissa)
+{
+ if (mantissa)
+ {
+ memcpy(result, "NaN", 3);
+ return 3;
+ }
+ if (sign)
+ {
+ result[0] = '-';
+ }
+ if (exponent)
+ {
+ memcpy(result + sign, "Infinity", 8);
+ return sign + 8;
+ }
+ result[sign] = '0';
+ return sign + 1;
+}
+
+static inline uint32
+float_to_bits(const float f)
+{
+ uint32 bits = 0;
+
+ memcpy(&bits, &f, sizeof(float));
+ return bits;
+}
+
+static inline uint64
+double_to_bits(const double d)
+{
+ uint64 bits = 0;
+
+ memcpy(&bits, &d, sizeof(double));
+ return bits;
+}
+
+#endif /* RYU_COMMON_H */
diff --git a/src/include/common/ryu.h b/src/include/common/ryu.h
new file mode 100644
index 0000000000..bd8e823c01
--- /dev/null
+++ b/src/include/common/ryu.h
@@ -0,0 +1,45 @@
+/*---------------------------------------------------------------------------
+ *
+ * Ryu floating-point output.
+ *
+ * Portions Copyright (c) 2018, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ * src/include/common/ryu.h
+ *
+ * This is a modification of code taken from github.com/ulfjack/ryu under the
+ * terms of the Boost license (not the Apache license). The original copyright
+ * notice follows:
+ *
+ * Copyright 2018 Ulf Adams
+ *
+ * The contents of this file may be used under the terms of the Apache
+ * License, Version 2.0.
+ *
+ * (See accompanying file LICENSE-Apache or copy at
+ * http://www.apache.org/licenses/LICENSE-2.0)
+ *
+ * Alternatively, the contents of this file may be used under the terms of the
+ * Boost Software License, Version 1.0.
+ *
+ * (See accompanying file LICENSE-Boost or copy at
+ * https://www.boost.org/LICENSE_1_0.txt)
+ *
+ * Unless required by applicable law or agreed to in writing, this software is
+ * distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.
+ *
+ *---------------------------------------------------------------------------
+ */
+#ifndef RYU_H
+#define RYU_H
+
+int ryu_d2s_buffered_n(double f, char *result);
+void ryu_d2s_buffered(double f, char *result);
+char *ryu_d2s(double f);
+
+int ryu_f2s_buffered_n(float f, char *result);
+void ryu_f2s_buffered(float f, char *result);
+char *ryu_f2s(float f);
+
+#endif /* RYU_H */
