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