robot/include/boost/json/detail/ryu/detail/d2s.hpp

// 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.

/*
    This is a derivative work
*/

#ifndef BOOST_JSON_DETAIL_RYU_DETAIL_D2S_HPP
#define BOOST_JSON_DETAIL_RYU_DETAIL_D2S_HPP

#include <boost/json/detail/config.hpp>
#include <boost/json/detail/ryu/detail/common.hpp>

// Only include the full table if we're not optimizing for size.
#if !defined(BOOST_JSON_RYU_OPTIMIZE_SIZE)
#include <boost/json/detail/ryu/detail/d2s_full_table.hpp>
#endif
#if defined(BOOST_JSON_RYU_HAS_UINT128)
typedef __uint128_t uint128_t;
#else
#include <boost/json/detail/ryu/detail/d2s_intrinsics.hpp>
#endif

namespace boost {
namespace json {
namespace detail {

namespace ryu {
namespace detail {

constexpr int DOUBLE_POW5_INV_BITCOUNT = 122;
constexpr int DOUBLE_POW5_BITCOUNT = 121;

#if defined(BOOST_JSON_RYU_OPTIMIZE_SIZE)

constexpr int POW5_TABLE_SIZE = 26;

inline
std::uint64_t const
(&DOUBLE_POW5_TABLE() noexcept)[POW5_TABLE_SIZE]
{
    static constexpr std::uint64_t arr[26] = {
    1ull, 5ull, 25ull, 125ull, 625ull, 3125ull, 15625ull, 78125ull, 390625ull,
    1953125ull, 9765625ull, 48828125ull, 244140625ull, 1220703125ull, 6103515625ull,
    30517578125ull, 152587890625ull, 762939453125ull, 3814697265625ull,
    19073486328125ull, 95367431640625ull, 476837158203125ull,
    2384185791015625ull, 11920928955078125ull, 59604644775390625ull,
    298023223876953125ull //, 1490116119384765625ull
    };
    return arr;
}

inline
std::uint64_t const
(&DOUBLE_POW5_SPLIT2() noexcept)[13][2]
{
    static constexpr std::uint64_t arr[13][2] = {
    {                    0u,  72057594037927936u },
    { 10376293541461622784u,  93132257461547851u },
    { 15052517733678820785u, 120370621524202240u },
    {  6258995034005762182u,  77787690973264271u },
    { 14893927168346708332u, 100538234169297439u },
    {  4272820386026678563u, 129942622070561240u },
    {  7330497575943398595u,  83973451344588609u },
    { 18377130505971182927u, 108533142064701048u },
    { 10038208235822497557u, 140275798336537794u },
    {  7017903361312433648u,  90651109995611182u },
    {  6366496589810271835u, 117163813585596168u },
    {  9264989777501460624u,  75715339914673581u },
    { 17074144231291089770u,  97859783203563123u }};
    return arr;
}

// Unfortunately, the results are sometimes off by one. We use an additional
// lookup table to store those cases and adjust the result.
inline
std::uint32_t const
(&POW5_OFFSETS() noexcept)[13]
{
    static constexpr std::uint32_t arr[13] = {
        0x00000000, 0x00000000, 0x00000000, 0x033c55be, 0x03db77d8, 0x0265ffb2,
        0x00000800, 0x01a8ff56, 0x00000000, 0x0037a200, 0x00004000, 0x03fffffc,
        0x00003ffe};
    return arr;
}

inline
std::uint64_t const
(&DOUBLE_POW5_INV_SPLIT2() noexcept)[13][2]
{
    static constexpr std::uint64_t arr[13][2] = {
    {                    1u, 288230376151711744u },
    {  7661987648932456967u, 223007451985306231u },
    { 12652048002903177473u, 172543658669764094u },
    {  5522544058086115566u, 266998379490113760u },
    {  3181575136763469022u, 206579990246952687u },
    {  4551508647133041040u, 159833525776178802u },
    {  1116074521063664381u, 247330401473104534u },
    { 17400360011128145022u, 191362629322552438u },
    {  9297997190148906106u, 148059663038321393u },
    { 11720143854957885429u, 229111231347799689u },
    { 15401709288678291155u, 177266229209635622u },
    {  3003071137298187333u, 274306203439684434u },
    { 17516772882021341108u, 212234145163966538u }};
    return arr;
}

inline
std::uint32_t const
(&POW5_INV_OFFSETS() noexcept)[20]
{
    static constexpr std::uint32_t arr[20] = {
    0x51505404, 0x55054514, 0x45555545, 0x05511411, 0x00505010, 0x00000004,
    0x00000000, 0x00000000, 0x55555040, 0x00505051, 0x00050040, 0x55554000,
    0x51659559, 0x00001000, 0x15000010, 0x55455555, 0x41404051, 0x00001010,
    0x00000014, 0x00000000};
    return arr;
}

#if defined(BOOST_JSON_RYU_HAS_UINT128)

// Computes 5^i in the form required by Ryu, and stores it in the given pointer.
inline
void
double_computePow5(
    const std::uint32_t i,
    std::uint64_t* const result)
{
    const std::uint32_t base = i / POW5_TABLE_SIZE;
    const std::uint32_t base2 = base * POW5_TABLE_SIZE;
    const std::uint32_t offset = i - base2;
    const std::uint64_t* const mul = DOUBLE_POW5_SPLIT2()[base];
    if (offset == 0)
    {
        result[0] = mul[0];
        result[1] = mul[1];
        return;
    }
    const std::uint64_t m = DOUBLE_POW5_TABLE()[offset];
    const uint128_t b0 = ((uint128_t)m) * mul[0];
    const uint128_t b2 = ((uint128_t)m) * mul[1];
    const std::uint32_t delta = pow5bits(i) - pow5bits(base2);
    const uint128_t shiftedSum = (b0 >> delta) + (b2 << (64 - delta)) + ((POW5_OFFSETS()[base] >> offset) & 1);
    result[0] = (std::uint64_t)shiftedSum;
    result[1] = (std::uint64_t)(shiftedSum >> 64);
}

// Computes 5^-i in the form required by Ryu, and stores it in the given pointer.
inline
void
double_computeInvPow5(
    const std::uint32_t i,
    std::uint64_t* const result)
{
    const std::uint32_t base = (i + POW5_TABLE_SIZE - 1) / POW5_TABLE_SIZE;
    const std::uint32_t base2 = base * POW5_TABLE_SIZE;
    const std::uint32_t offset = base2 - i;
    const std::uint64_t* const mul = DOUBLE_POW5_INV_SPLIT2()[base]; // 1/5^base2
    if (offset == 0)
    {
        result[0] = mul[0];
        result[1] = mul[1];
        return;
    }
    const std::uint64_t m = DOUBLE_POW5_TABLE()[offset]; // 5^offset
    const uint128_t b0 = ((uint128_t)m) * (mul[0] - 1);
    const uint128_t b2 = ((uint128_t)m) * mul[1]; // 1/5^base2 * 5^offset = 1/5^(base2-offset) = 1/5^i
    const std::uint32_t delta = pow5bits(base2) - pow5bits(i);
    const uint128_t shiftedSum =
        ((b0 >> delta) + (b2 << (64 - delta))) + 1 + ((POW5_INV_OFFSETS()[i / 16] >> ((i % 16) << 1)) & 3);
    result[0] = (std::uint64_t)shiftedSum;
    result[1] = (std::uint64_t)(shiftedSum >> 64);
}

#else // defined(BOOST_JSON_RYU_HAS_UINT128)

// Computes 5^i in the form required by Ryu, and stores it in the given pointer.
inline
void
double_computePow5(
    const std::uint32_t i,
    std::uint64_t* const result)
{
    const std::uint32_t base = i / POW5_TABLE_SIZE;
    const std::uint32_t base2 = base * POW5_TABLE_SIZE;
    const std::uint32_t offset = i - base2;
    const std::uint64_t* const mul = DOUBLE_POW5_SPLIT2()[base];
    if (offset == 0)
    {
        result[0] = mul[0];
        result[1] = mul[1];
        return;
    }
    std::uint64_t const m = DOUBLE_POW5_TABLE()[offset];
    std::uint64_t high1;
    std::uint64_t const low1 = umul128(m, mul[1], &high1);
    std::uint64_t high0;
    std::uint64_t const low0 = umul128(m, mul[0], &high0);
    std::uint64_t const sum = high0 + low1;
    if (sum < high0)
        ++high1; // overflow into high1
    // high1 | sum | low0
    std::uint32_t const delta = pow5bits(i) - pow5bits(base2);
    result[0] = shiftright128(low0, sum, delta) + ((POW5_OFFSETS()[base] >> offset) & 1);
    result[1] = shiftright128(sum, high1, delta);
}

// Computes 5^-i in the form required by Ryu, and stores it in the given pointer.
inline
void
double_computeInvPow5(
    const std::uint32_t i,
    std::uint64_t* const result)
{
    const std::uint32_t base = (i + POW5_TABLE_SIZE - 1) / POW5_TABLE_SIZE;
    const std::uint32_t base2 = base * POW5_TABLE_SIZE;
    const std::uint32_t offset = base2 - i;
    const std::uint64_t* const mul = DOUBLE_POW5_INV_SPLIT2()[base]; // 1/5^base2
    if (offset == 0)
    {
        result[0] = mul[0];
        result[1] = mul[1];
        return;
    }
    std::uint64_t const m = DOUBLE_POW5_TABLE()[offset];
    std::uint64_t high1;
    std::uint64_t const low1 = umul128(m, mul[1], &high1);
    std::uint64_t high0;
    std::uint64_t const low0 = umul128(m, mul[0] - 1, &high0);
    std::uint64_t const sum = high0 + low1;
    if (sum < high0)
        ++high1; // overflow into high1
    // high1 | sum | low0
    std::uint32_t const delta = pow5bits(base2) - pow5bits(i);
    result[0] = shiftright128(low0, sum, delta) + 1 + ((POW5_INV_OFFSETS()[i / 16] >> ((i % 16) << 1)) & 3);
    result[1] = shiftright128(sum, high1, delta);
}

#endif // defined(BOOST_JSON_RYU_HAS_UINT128)

#endif // defined(BOOST_JSON_RYU_OPTIMIZE_SIZE)

} // detail
} // ryu

} // detail
} // namespace json
} // namespace boost

#endif