include/boost/json /detail /ryu /detail /d2s.hpp
0.00% Lines (0/0) 0.00% Functions (0/0)
[ ] prev/next file n p prev/next uncovered line
TLA Baseline Branch
Line Hits Code Line Hits 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  
DCB 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 - };  
DCB 64 - 1186 return arr;  
65 - }  
66 -  
67 - inline  
68 - std::uint64_t const  
DCB 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 }};  
DCB 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  
DCB 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};  
DCB 98 - 626 return arr;  
99 - }  
100 -  
101 - inline  
102 - std::uint64_t const  
DCB 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 }};  
DCB 119 - 584 return arr;  
120 - }  
121 -  
122 - inline  
123 - std::uint32_t const  
DCB 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};  
DCB 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  
DCB 139 - 652 double_computePow5(  
140 - const std::uint32_t i,  
141 - std::uint64_t* const result)  
142 - {  
DCB 143 - 652 const std::uint32_t base = i / POW5_TABLE_SIZE;  
DCB 144 - 652 const std::uint32_t base2 = base * POW5_TABLE_SIZE;  
DCB 145 - 652 const std::uint32_t offset = i - base2;  
DCB 146 - 652 const std::uint64_t* const mul = DOUBLE_POW5_SPLIT2()[base];  
DCB 147 - 652 if (offset == 0)  
148 - {  
DCB 149 - 26 result[0] = mul[0];  
DCB 150 - 26 result[1] = mul[1];  
DCB 151 - 26 return;  
152 - }  
DCB 153 - 626 const std::uint64_t m = DOUBLE_POW5_TABLE()[offset];  
DCB 154 - 626 const uint128_t b0 = ((uint128_t)m) * mul[0];  
DCB 155 - 626 const uint128_t b2 = ((uint128_t)m) * mul[1];  
DCB 156 - 626 const std::uint32_t delta = pow5bits(i) - pow5bits(base2);  
DCB 157 - 626 const uint128_t shiftedSum = (b0 >> delta) + (b2 << (64 - delta)) + ((POW5_OFFSETS()[base] >> offset) & 1);  
DCB 158 - 626 result[0] = (std::uint64_t)shiftedSum;  
DCB 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  
DCB 165 - 584 double_computeInvPow5(  
166 - const std::uint32_t i,  
167 - std::uint64_t* const result)  
168 - {  
DCB 169 - 584 const std::uint32_t base = (i + POW5_TABLE_SIZE - 1) / POW5_TABLE_SIZE;  
DCB 170 - 584 const std::uint32_t base2 = base * POW5_TABLE_SIZE;  
DCB 171 - 584 const std::uint32_t offset = base2 - i;  
DCB 172 - 584 const std::uint64_t* const mul = DOUBLE_POW5_INV_SPLIT2()[base]; // 1/5^base2  
DCB 173 - 584 if (offset == 0)  
174 - {  
DCB 175 - 24 result[0] = mul[0];  
DCB 176 - 24 result[1] = mul[1];  
DCB 177 - 24 return;  
178 - }  
DCB 179 - 560 const std::uint64_t m = DOUBLE_POW5_TABLE()[offset]; // 5^offset  
DCB 180 - 560 const uint128_t b0 = ((uint128_t)m) * (mul[0] - 1);  
DCB 181 - 560 const uint128_t b2 = ((uint128_t)m) * mul[1]; // 1/5^base2 * 5^offset = 1/5^(base2-offset) = 1/5^i  
DCB 182 - 560 const std::uint32_t delta = pow5bits(base2) - pow5bits(i);  
183 - const uint128_t shiftedSum =  
DCB 184 - 560 ((b0 >> delta) + (b2 << (64 - delta))) + 1 + ((POW5_INV_OFFSETS()[i / 16] >> ((i % 16) << 1)) & 3);  
DCB 185 - 560 result[0] = (std::uint64_t)shiftedSum;  
DCB 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