TLA Line data Source code
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 HIT 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 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 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
|
