| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | // Copyright 2018 Ulf Adams | ||
| 2 | // | ||
| 3 | // The contents of this file may be used under the terms of the Apache License, | ||
| 4 | // Version 2.0. | ||
| 5 | // | ||
| 6 | // (See accompanying file LICENSE-Apache or copy at | ||
| 7 | // http://www.apache.org/licenses/LICENSE-2.0) | ||
| 8 | // | ||
| 9 | // Alternatively, the contents of this file may be used under the terms of | ||
| 10 | // the Boost Software License, Version 1.0. | ||
| 11 | // (See accompanying file LICENSE-Boost or copy at | ||
| 12 | // https://www.boost.org/LICENSE_1_0.txt) | ||
| 13 | // | ||
| 14 | // Unless required by applicable law or agreed to in writing, this software | ||
| 15 | // is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY | ||
| 16 | // KIND, either express or implied. | ||
| 17 | |||
| 18 | /* | ||
| 19 | This is a derivative work | ||
| 20 | */ | ||
| 21 | |||
| 22 | #ifndef BOOST_JSON_DETAIL_RYU_DETAIL_D2S_HPP | ||
| 23 | #define BOOST_JSON_DETAIL_RYU_DETAIL_D2S_HPP | ||
| 24 | |||
| 25 | #include <boost/json/detail/config.hpp> | ||
| 26 | #include <boost/json/detail/ryu/detail/common.hpp> | ||
| 27 | |||
| 28 | // Only include the full table if we're not optimizing for size. | ||
| 29 | #if !defined(BOOST_JSON_RYU_OPTIMIZE_SIZE) | ||
| 30 | #include <boost/json/detail/ryu/detail/d2s_full_table.hpp> | ||
| 31 | #endif | ||
| 32 | #if defined(BOOST_JSON_RYU_HAS_UINT128) | ||
| 33 | typedef __uint128_t uint128_t; | ||
| 34 | #else | ||
| 35 | #include <boost/json/detail/ryu/detail/d2s_intrinsics.hpp> | ||
| 36 | #endif | ||
| 37 | |||
| 38 | namespace boost { | ||
| 39 | namespace json { | ||
| 40 | namespace detail { | ||
| 41 | |||
| 42 | namespace ryu { | ||
| 43 | namespace detail { | ||
| 44 | |||
| 45 | constexpr int DOUBLE_POW5_INV_BITCOUNT = 122; | ||
| 46 | constexpr int DOUBLE_POW5_BITCOUNT = 121; | ||
| 47 | |||
| 48 | #if defined(BOOST_JSON_RYU_OPTIMIZE_SIZE) | ||
| 49 | |||
| 50 | constexpr int POW5_TABLE_SIZE = 26; | ||
| 51 | |||
| 52 | inline | ||
| 53 | std::uint64_t const | ||
| 54 | 1186 | (&DOUBLE_POW5_TABLE() noexcept)[POW5_TABLE_SIZE] | |
| 55 | { | ||
| 56 | static constexpr std::uint64_t arr[26] = { | ||
| 57 | 1ull, 5ull, 25ull, 125ull, 625ull, 3125ull, 15625ull, 78125ull, 390625ull, | ||
| 58 | 1953125ull, 9765625ull, 48828125ull, 244140625ull, 1220703125ull, 6103515625ull, | ||
| 59 | 30517578125ull, 152587890625ull, 762939453125ull, 3814697265625ull, | ||
| 60 | 19073486328125ull, 95367431640625ull, 476837158203125ull, | ||
| 61 | 2384185791015625ull, 11920928955078125ull, 59604644775390625ull, | ||
| 62 | 298023223876953125ull //, 1490116119384765625ull | ||
| 63 | }; | ||
| 64 | 1186 | return arr; | |
| 65 | } | ||
| 66 | |||
| 67 | inline | ||
| 68 | std::uint64_t const | ||
| 69 | 652 | (&DOUBLE_POW5_SPLIT2() noexcept)[13][2] | |
| 70 | { | ||
| 71 | static constexpr std::uint64_t arr[13][2] = { | ||
| 72 | { 0u, 72057594037927936u }, | ||
| 73 | { 10376293541461622784u, 93132257461547851u }, | ||
| 74 | { 15052517733678820785u, 120370621524202240u }, | ||
| 75 | { 6258995034005762182u, 77787690973264271u }, | ||
| 76 | { 14893927168346708332u, 100538234169297439u }, | ||
| 77 | { 4272820386026678563u, 129942622070561240u }, | ||
| 78 | { 7330497575943398595u, 83973451344588609u }, | ||
| 79 | { 18377130505971182927u, 108533142064701048u }, | ||
| 80 | { 10038208235822497557u, 140275798336537794u }, | ||
| 81 | { 7017903361312433648u, 90651109995611182u }, | ||
| 82 | { 6366496589810271835u, 117163813585596168u }, | ||
| 83 | { 9264989777501460624u, 75715339914673581u }, | ||
| 84 | { 17074144231291089770u, 97859783203563123u }}; | ||
| 85 | 652 | return arr; | |
| 86 | } | ||
| 87 | |||
| 88 | // Unfortunately, the results are sometimes off by one. We use an additional | ||
| 89 | // lookup table to store those cases and adjust the result. | ||
| 90 | inline | ||
| 91 | std::uint32_t const | ||
| 92 | 626 | (&POW5_OFFSETS() noexcept)[13] | |
| 93 | { | ||
| 94 | static constexpr std::uint32_t arr[13] = { | ||
| 95 | 0x00000000, 0x00000000, 0x00000000, 0x033c55be, 0x03db77d8, 0x0265ffb2, | ||
| 96 | 0x00000800, 0x01a8ff56, 0x00000000, 0x0037a200, 0x00004000, 0x03fffffc, | ||
| 97 | 0x00003ffe}; | ||
| 98 | 626 | return arr; | |
| 99 | } | ||
| 100 | |||
| 101 | inline | ||
| 102 | std::uint64_t const | ||
| 103 | 584 | (&DOUBLE_POW5_INV_SPLIT2() noexcept)[13][2] | |
| 104 | { | ||
| 105 | static constexpr std::uint64_t arr[13][2] = { | ||
| 106 | { 1u, 288230376151711744u }, | ||
| 107 | { 7661987648932456967u, 223007451985306231u }, | ||
| 108 | { 12652048002903177473u, 172543658669764094u }, | ||
| 109 | { 5522544058086115566u, 266998379490113760u }, | ||
| 110 | { 3181575136763469022u, 206579990246952687u }, | ||
| 111 | { 4551508647133041040u, 159833525776178802u }, | ||
| 112 | { 1116074521063664381u, 247330401473104534u }, | ||
| 113 | { 17400360011128145022u, 191362629322552438u }, | ||
| 114 | { 9297997190148906106u, 148059663038321393u }, | ||
| 115 | { 11720143854957885429u, 229111231347799689u }, | ||
| 116 | { 15401709288678291155u, 177266229209635622u }, | ||
| 117 | { 3003071137298187333u, 274306203439684434u }, | ||
| 118 | { 17516772882021341108u, 212234145163966538u }}; | ||
| 119 | 584 | return arr; | |
| 120 | } | ||
| 121 | |||
| 122 | inline | ||
| 123 | std::uint32_t const | ||
| 124 | 560 | (&POW5_INV_OFFSETS() noexcept)[20] | |
| 125 | { | ||
| 126 | static constexpr std::uint32_t arr[20] = { | ||
| 127 | 0x51505404, 0x55054514, 0x45555545, 0x05511411, 0x00505010, 0x00000004, | ||
| 128 | 0x00000000, 0x00000000, 0x55555040, 0x00505051, 0x00050040, 0x55554000, | ||
| 129 | 0x51659559, 0x00001000, 0x15000010, 0x55455555, 0x41404051, 0x00001010, | ||
| 130 | 0x00000014, 0x00000000}; | ||
| 131 | 560 | return arr; | |
| 132 | } | ||
| 133 | |||
| 134 | #if defined(BOOST_JSON_RYU_HAS_UINT128) | ||
| 135 | |||
| 136 | // Computes 5^i in the form required by Ryu, and stores it in the given pointer. | ||
| 137 | inline | ||
| 138 | void | ||
| 139 | 652 | double_computePow5( | |
| 140 | const std::uint32_t i, | ||
| 141 | std::uint64_t* const result) | ||
| 142 | { | ||
| 143 | 652 | const std::uint32_t base = i / POW5_TABLE_SIZE; | |
| 144 | 652 | const std::uint32_t base2 = base * POW5_TABLE_SIZE; | |
| 145 | 652 | const std::uint32_t offset = i - base2; | |
| 146 | 652 | const std::uint64_t* const mul = DOUBLE_POW5_SPLIT2()[base]; | |
| 147 |
2/2✓ Branch 0 taken 26 times.
✓ Branch 1 taken 626 times.
|
652 | if (offset == 0) |
| 148 | { | ||
| 149 | 26 | result[0] = mul[0]; | |
| 150 | 26 | result[1] = mul[1]; | |
| 151 | 26 | return; | |
| 152 | } | ||
| 153 | 626 | const std::uint64_t m = DOUBLE_POW5_TABLE()[offset]; | |
| 154 | 626 | const uint128_t b0 = ((uint128_t)m) * mul[0]; | |
| 155 | 626 | const uint128_t b2 = ((uint128_t)m) * mul[1]; | |
| 156 | 626 | const std::uint32_t delta = pow5bits(i) - pow5bits(base2); | |
| 157 | 626 | const uint128_t shiftedSum = (b0 >> delta) + (b2 << (64 - delta)) + ((POW5_OFFSETS()[base] >> offset) & 1); | |
| 158 | 626 | result[0] = (std::uint64_t)shiftedSum; | |
| 159 | 626 | result[1] = (std::uint64_t)(shiftedSum >> 64); | |
| 160 | } | ||
| 161 | |||
| 162 | // Computes 5^-i in the form required by Ryu, and stores it in the given pointer. | ||
| 163 | inline | ||
| 164 | void | ||
| 165 | 584 | double_computeInvPow5( | |
| 166 | const std::uint32_t i, | ||
| 167 | std::uint64_t* const result) | ||
| 168 | { | ||
| 169 | 584 | const std::uint32_t base = (i + POW5_TABLE_SIZE - 1) / POW5_TABLE_SIZE; | |
| 170 | 584 | const std::uint32_t base2 = base * POW5_TABLE_SIZE; | |
| 171 | 584 | const std::uint32_t offset = base2 - i; | |
| 172 | 584 | const std::uint64_t* const mul = DOUBLE_POW5_INV_SPLIT2()[base]; // 1/5^base2 | |
| 173 |
2/2✓ Branch 0 taken 24 times.
✓ Branch 1 taken 560 times.
|
584 | if (offset == 0) |
| 174 | { | ||
| 175 | 24 | result[0] = mul[0]; | |
| 176 | 24 | result[1] = mul[1]; | |
| 177 | 24 | return; | |
| 178 | } | ||
| 179 | 560 | const std::uint64_t m = DOUBLE_POW5_TABLE()[offset]; // 5^offset | |
| 180 | 560 | const uint128_t b0 = ((uint128_t)m) * (mul[0] - 1); | |
| 181 | 560 | const uint128_t b2 = ((uint128_t)m) * mul[1]; // 1/5^base2 * 5^offset = 1/5^(base2-offset) = 1/5^i | |
| 182 | 560 | const std::uint32_t delta = pow5bits(base2) - pow5bits(i); | |
| 183 | const uint128_t shiftedSum = | ||
| 184 | 560 | ((b0 >> delta) + (b2 << (64 - delta))) + 1 + ((POW5_INV_OFFSETS()[i / 16] >> ((i % 16) << 1)) & 3); | |
| 185 | 560 | result[0] = (std::uint64_t)shiftedSum; | |
| 186 | 560 | result[1] = (std::uint64_t)(shiftedSum >> 64); | |
| 187 | } | ||
| 188 | |||
| 189 | #else // defined(BOOST_JSON_RYU_HAS_UINT128) | ||
| 190 | |||
| 191 | // Computes 5^i in the form required by Ryu, and stores it in the given pointer. | ||
| 192 | inline | ||
| 193 | void | ||
| 194 | double_computePow5( | ||
| 195 | const std::uint32_t i, | ||
| 196 | std::uint64_t* const result) | ||
| 197 | { | ||
| 198 | const std::uint32_t base = i / POW5_TABLE_SIZE; | ||
| 199 | const std::uint32_t base2 = base * POW5_TABLE_SIZE; | ||
| 200 | const std::uint32_t offset = i - base2; | ||
| 201 | const std::uint64_t* const mul = DOUBLE_POW5_SPLIT2()[base]; | ||
| 202 | if (offset == 0) | ||
| 203 | { | ||
| 204 | result[0] = mul[0]; | ||
| 205 | result[1] = mul[1]; | ||
| 206 | return; | ||
| 207 | } | ||
| 208 | std::uint64_t const m = DOUBLE_POW5_TABLE()[offset]; | ||
| 209 | std::uint64_t high1; | ||
| 210 | std::uint64_t const low1 = umul128(m, mul[1], &high1); | ||
| 211 | std::uint64_t high0; | ||
| 212 | std::uint64_t const low0 = umul128(m, mul[0], &high0); | ||
| 213 | std::uint64_t const sum = high0 + low1; | ||
| 214 | if (sum < high0) | ||
| 215 | ++high1; // overflow into high1 | ||
| 216 | // high1 | sum | low0 | ||
| 217 | std::uint32_t const delta = pow5bits(i) - pow5bits(base2); | ||
| 218 | result[0] = shiftright128(low0, sum, delta) + ((POW5_OFFSETS()[base] >> offset) & 1); | ||
| 219 | result[1] = shiftright128(sum, high1, delta); | ||
| 220 | } | ||
| 221 | |||
| 222 | // Computes 5^-i in the form required by Ryu, and stores it in the given pointer. | ||
| 223 | inline | ||
| 224 | void | ||
| 225 | double_computeInvPow5( | ||
| 226 | const std::uint32_t i, | ||
| 227 | std::uint64_t* const result) | ||
| 228 | { | ||
| 229 | const std::uint32_t base = (i + POW5_TABLE_SIZE - 1) / POW5_TABLE_SIZE; | ||
| 230 | const std::uint32_t base2 = base * POW5_TABLE_SIZE; | ||
| 231 | const std::uint32_t offset = base2 - i; | ||
| 232 | const std::uint64_t* const mul = DOUBLE_POW5_INV_SPLIT2()[base]; // 1/5^base2 | ||
| 233 | if (offset == 0) | ||
| 234 | { | ||
| 235 | result[0] = mul[0]; | ||
| 236 | result[1] = mul[1]; | ||
| 237 | return; | ||
| 238 | } | ||
| 239 | std::uint64_t const m = DOUBLE_POW5_TABLE()[offset]; | ||
| 240 | std::uint64_t high1; | ||
| 241 | std::uint64_t const low1 = umul128(m, mul[1], &high1); | ||
| 242 | std::uint64_t high0; | ||
| 243 | std::uint64_t const low0 = umul128(m, mul[0] - 1, &high0); | ||
| 244 | std::uint64_t const sum = high0 + low1; | ||
| 245 | if (sum < high0) | ||
| 246 | ++high1; // overflow into high1 | ||
| 247 | // high1 | sum | low0 | ||
| 248 | std::uint32_t const delta = pow5bits(base2) - pow5bits(i); | ||
| 249 | result[0] = shiftright128(low0, sum, delta) + 1 + ((POW5_INV_OFFSETS()[i / 16] >> ((i % 16) << 1)) & 3); | ||
| 250 | result[1] = shiftright128(sum, high1, delta); | ||
| 251 | } | ||
| 252 | |||
| 253 | #endif // defined(BOOST_JSON_RYU_HAS_UINT128) | ||
| 254 | |||
| 255 | #endif // defined(BOOST_JSON_RYU_OPTIMIZE_SIZE) | ||
| 256 | |||
| 257 | } // detail | ||
| 258 | } // ryu | ||
| 259 | |||
| 260 | } // detail | ||
| 261 | } // namespace json | ||
| 262 | } // namespace boost | ||
| 263 | |||
| 264 | #endif | ||
| 265 |