include/boost/json /detail /charconv /detail /emulated128.hpp
0.00% Lines (0/3) 0.00% Functions (0/1)
[ ] prev/next file n p prev/next uncovered line
TLA Baseline Branch
Line Hits Code Line Hits Code
1   // Copyright 2020-2023 Daniel Lemire 1   // Copyright 2020-2023 Daniel Lemire
2   // Copyright 2023 Matt Borland 2   // Copyright 2023 Matt Borland
3   // Distributed under the Boost Software License, Version 1.0. 3   // Distributed under the Boost Software License, Version 1.0.
4   // https://www.boost.org/LICENSE_1_0.txt 4   // https://www.boost.org/LICENSE_1_0.txt
5   5  
6   // If the architecture (e.g. ARM) does not have __int128 we need to emulate it 6   // If the architecture (e.g. ARM) does not have __int128 we need to emulate it
7   7  
8   #ifndef BOOST_JSON_DETAIL_CHARCONV_DETAIL_EMULATED128_HPP 8   #ifndef BOOST_JSON_DETAIL_CHARCONV_DETAIL_EMULATED128_HPP
9   #define BOOST_JSON_DETAIL_CHARCONV_DETAIL_EMULATED128_HPP 9   #define BOOST_JSON_DETAIL_CHARCONV_DETAIL_EMULATED128_HPP
10   10  
11   #include <boost/json/detail/charconv/detail/config.hpp> 11   #include <boost/json/detail/charconv/detail/config.hpp>
12   #include <cstdint> 12   #include <cstdint>
13   #include <cassert> 13   #include <cassert>
14   14  
15   namespace boost { namespace json { namespace detail { namespace charconv { namespace detail { 15   namespace boost { namespace json { namespace detail { namespace charconv { namespace detail {
16   16  
17   // Compilers might support built-in 128-bit integer types. However, it seems that 17   // Compilers might support built-in 128-bit integer types. However, it seems that
18   // emulating them with a pair of 64-bit integers actually produces a better code, 18   // emulating them with a pair of 64-bit integers actually produces a better code,
19   // so we avoid using those built-ins. That said, they are still useful for 19   // so we avoid using those built-ins. That said, they are still useful for
20   // implementing 64-bit x 64-bit -> 128-bit multiplication. 20   // implementing 64-bit x 64-bit -> 128-bit multiplication.
21   21  
22   struct uint128 22   struct uint128
23   { 23   {
24   std::uint64_t high; 24   std::uint64_t high;
25   std::uint64_t low; 25   std::uint64_t low;
26   26  
27   uint128& operator+=(std::uint64_t n) & noexcept 27   uint128& operator+=(std::uint64_t n) & noexcept
28   { 28   {
29   #if BOOST_JSON_HAS_BUILTIN(__builtin_addcll) 29   #if BOOST_JSON_HAS_BUILTIN(__builtin_addcll)
30   30  
31   unsigned long long carry; 31   unsigned long long carry;
32   low = __builtin_addcll(low, n, 0, &carry); 32   low = __builtin_addcll(low, n, 0, &carry);
33   high = __builtin_addcll(high, 0, carry, &carry); 33   high = __builtin_addcll(high, 0, carry, &carry);
34   34  
35   #elif BOOST_JSON_HAS_BUILTIN(__builtin_ia32_addcarryx_u64) 35   #elif BOOST_JSON_HAS_BUILTIN(__builtin_ia32_addcarryx_u64)
36   36  
37   unsigned long long result; 37   unsigned long long result;
38   auto carry = __builtin_ia32_addcarryx_u64(0, low, n, &result); 38   auto carry = __builtin_ia32_addcarryx_u64(0, low, n, &result);
39   low = result; 39   low = result;
40   __builtin_ia32_addcarryx_u64(carry, high, 0, &result); 40   __builtin_ia32_addcarryx_u64(carry, high, 0, &result);
41   high = result; 41   high = result;
42   42  
43   #elif defined(BOOST_MSVC) && defined(_M_X64) 43   #elif defined(BOOST_MSVC) && defined(_M_X64)
44   44  
45   auto carry = _addcarry_u64(0, low, n, &low); 45   auto carry = _addcarry_u64(0, low, n, &low);
46   _addcarry_u64(carry, high, 0, &high); 46   _addcarry_u64(carry, high, 0, &high);
47   47  
48   #else 48   #else
49   49  
50   auto sum = low + n; 50   auto sum = low + n;
51   high += (sum < low ? 1 : 0); 51   high += (sum < low ? 1 : 0);
52   low = sum; 52   low = sum;
53   53  
54   #endif 54   #endif
55   return *this; 55   return *this;
56   } 56   }
57   }; 57   };
58   58  
59   static inline std::uint64_t umul64(std::uint32_t x, std::uint32_t y) noexcept 59   static inline std::uint64_t umul64(std::uint32_t x, std::uint32_t y) noexcept
60   { 60   {
61   #if defined(BOOST_JSON_HAS_MSVC_32BIT_INTRINSICS) && !defined(_M_ARM) 61   #if defined(BOOST_JSON_HAS_MSVC_32BIT_INTRINSICS) && !defined(_M_ARM)
62   62  
63   return __emulu(x, y); 63   return __emulu(x, y);
64   64  
65   #else 65   #else
66   66  
67   return x * static_cast<std::uint64_t>(y); 67   return x * static_cast<std::uint64_t>(y);
68   68  
69   #endif 69   #endif
70   } 70   }
71   71  
72   // Get 128-bit result of multiplication of two 64-bit unsigned integers. 72   // Get 128-bit result of multiplication of two 64-bit unsigned integers.
MISUBC 73   ✗ BOOST_JSON_SAFEBUFFERS inline uint128 umul128(std::uint64_t x, std::uint64_t y) noexcept 73   ✗ BOOST_JSON_SAFEBUFFERS inline uint128 umul128(std::uint64_t x, std::uint64_t y) noexcept
74   { 74   {
75   #if defined(BOOST_HAS_INT128) 75   #if defined(BOOST_HAS_INT128)
76   76  
MISUBC 77   ✗ auto result = static_cast<boost::uint128_type>(x) * static_cast<boost::uint128_type>(y); 77   ✗ auto result = static_cast<boost::uint128_type>(x) * static_cast<boost::uint128_type>(y);
MISUBC 78   ✗ return {static_cast<std::uint64_t>(result >> 64), static_cast<std::uint64_t>(result)}; 78   ✗ return {static_cast<std::uint64_t>(result >> 64), static_cast<std::uint64_t>(result)};
79   79  
80   #elif defined(BOOST_JSON_HAS_MSVC_64BIT_INTRINSICS) && !defined(_M_ARM64) 80   #elif defined(BOOST_JSON_HAS_MSVC_64BIT_INTRINSICS) && !defined(_M_ARM64)
81   81  
82   std::uint64_t high; 82   std::uint64_t high;
83   std::uint64_t low = _umul128(x, y, &high); 83   std::uint64_t low = _umul128(x, y, &high);
84   return {high, low}; 84   return {high, low};
85   85  
86   // https://developer.arm.com/documentation/dui0802/a/A64-General-Instructions/UMULH 86   // https://developer.arm.com/documentation/dui0802/a/A64-General-Instructions/UMULH
87   #elif defined(_M_ARM64) && !defined(__MINGW32__) 87   #elif defined(_M_ARM64) && !defined(__MINGW32__)
88   88  
89   std::uint64_t high = __umulh(x, y); 89   std::uint64_t high = __umulh(x, y);
90   std::uint64_t low = x * y; 90   std::uint64_t low = x * y;
91   return {high, low}; 91   return {high, low};
92   92  
93   #else 93   #else
94   94  
95   auto a = static_cast<std::uint32_t>(x >> 32); 95   auto a = static_cast<std::uint32_t>(x >> 32);
96   auto b = static_cast<std::uint32_t>(x); 96   auto b = static_cast<std::uint32_t>(x);
97   auto c = static_cast<std::uint32_t>(y >> 32); 97   auto c = static_cast<std::uint32_t>(y >> 32);
98   auto d = static_cast<std::uint32_t>(y); 98   auto d = static_cast<std::uint32_t>(y);
99   99  
100   auto ac = umul64(a, c); 100   auto ac = umul64(a, c);
101   auto bc = umul64(b, c); 101   auto bc = umul64(b, c);
102   auto ad = umul64(a, d); 102   auto ad = umul64(a, d);
103   auto bd = umul64(b, d); 103   auto bd = umul64(b, d);
104   104  
105   auto intermediate = (bd >> 32) + static_cast<std::uint32_t>(ad) + static_cast<std::uint32_t>(bc); 105   auto intermediate = (bd >> 32) + static_cast<std::uint32_t>(ad) + static_cast<std::uint32_t>(bc);
106   106  
107   return {ac + (intermediate >> 32) + (ad >> 32) + (bc >> 32), 107   return {ac + (intermediate >> 32) + (ad >> 32) + (bc >> 32),
108   (intermediate << 32) + static_cast<std::uint32_t>(bd)}; 108   (intermediate << 32) + static_cast<std::uint32_t>(bd)};
109   109  
110   #endif 110   #endif
111   } 111   }
112   112  
113   BOOST_JSON_SAFEBUFFERS inline std::uint64_t umul128_upper64(std::uint64_t x, std::uint64_t y) noexcept 113   BOOST_JSON_SAFEBUFFERS inline std::uint64_t umul128_upper64(std::uint64_t x, std::uint64_t y) noexcept
114   { 114   {
115   #if defined(BOOST_HAS_INT128) 115   #if defined(BOOST_HAS_INT128)
116   116  
117   auto result = static_cast<boost::uint128_type>(x) * static_cast<boost::uint128_type>(y); 117   auto result = static_cast<boost::uint128_type>(x) * static_cast<boost::uint128_type>(y);
118   return static_cast<std::uint64_t>(result >> 64); 118   return static_cast<std::uint64_t>(result >> 64);
119   119  
120   #elif defined(BOOST_JSON_HAS_MSVC_64BIT_INTRINSICS) 120   #elif defined(BOOST_JSON_HAS_MSVC_64BIT_INTRINSICS)
121   121  
122   return __umulh(x, y); 122   return __umulh(x, y);
123   123  
124   #else 124   #else
125   125  
126   auto a = static_cast<std::uint32_t>(x >> 32); 126   auto a = static_cast<std::uint32_t>(x >> 32);
127   auto b = static_cast<std::uint32_t>(x); 127   auto b = static_cast<std::uint32_t>(x);
128   auto c = static_cast<std::uint32_t>(y >> 32); 128   auto c = static_cast<std::uint32_t>(y >> 32);
129   auto d = static_cast<std::uint32_t>(y); 129   auto d = static_cast<std::uint32_t>(y);
130   130  
131   auto ac = umul64(a, c); 131   auto ac = umul64(a, c);
132   auto bc = umul64(b, c); 132   auto bc = umul64(b, c);
133   auto ad = umul64(a, d); 133   auto ad = umul64(a, d);
134   auto bd = umul64(b, d); 134   auto bd = umul64(b, d);
135   135  
136   auto intermediate = (bd >> 32) + static_cast<std::uint32_t>(ad) + static_cast<std::uint32_t>(bc); 136   auto intermediate = (bd >> 32) + static_cast<std::uint32_t>(ad) + static_cast<std::uint32_t>(bc);
137   137  
138   return ac + (intermediate >> 32) + (ad >> 32) + (bc >> 32); 138   return ac + (intermediate >> 32) + (ad >> 32) + (bc >> 32);
139   139  
140   #endif 140   #endif
141   } 141   }
142   142  
143   // Get upper 128-bits of multiplication of a 64-bit unsigned integer and a 128-bit 143   // Get upper 128-bits of multiplication of a 64-bit unsigned integer and a 128-bit
144   // unsigned integer. 144   // unsigned integer.
145   BOOST_JSON_SAFEBUFFERS inline uint128 umul192_upper128(std::uint64_t x, uint128 y) noexcept 145   BOOST_JSON_SAFEBUFFERS inline uint128 umul192_upper128(std::uint64_t x, uint128 y) noexcept
146   { 146   {
147   auto r = umul128(x, y.high); 147   auto r = umul128(x, y.high);
148   r += umul128_upper64(x, y.low); 148   r += umul128_upper64(x, y.low);
149   return r; 149   return r;
150   } 150   }
151   151  
152   // Get upper 64-bits of multiplication of a 32-bit unsigned integer and a 64-bit 152   // Get upper 64-bits of multiplication of a 32-bit unsigned integer and a 64-bit
153   // unsigned integer. 153   // unsigned integer.
154   inline std::uint64_t umul96_upper64(std::uint32_t x, std::uint64_t y) noexcept 154   inline std::uint64_t umul96_upper64(std::uint32_t x, std::uint64_t y) noexcept
155   { 155   {
156   #if defined(BOOST_HAS_INT128) || defined(BOOST_JSON_HAS_MSVC_64BIT_INTRINSICS) 156   #if defined(BOOST_HAS_INT128) || defined(BOOST_JSON_HAS_MSVC_64BIT_INTRINSICS)
157   157  
158   return umul128_upper64(static_cast<std::uint64_t>(x) << 32, y); 158   return umul128_upper64(static_cast<std::uint64_t>(x) << 32, y);
159   159  
160   #else 160   #else
161   161  
162   auto yh = static_cast<std::uint32_t>(y >> 32); 162   auto yh = static_cast<std::uint32_t>(y >> 32);
163   auto yl = static_cast<std::uint32_t>(y); 163   auto yl = static_cast<std::uint32_t>(y);
164   164  
165   auto xyh = umul64(x, yh); 165   auto xyh = umul64(x, yh);
166   auto xyl = umul64(x, yl); 166   auto xyl = umul64(x, yl);
167   167  
168   return xyh + (xyl >> 32); 168   return xyh + (xyl >> 32);
169   169  
170   #endif 170   #endif
171   } 171   }
172   172  
173   // Get lower 128-bits of multiplication of a 64-bit unsigned integer and a 128-bit 173   // Get lower 128-bits of multiplication of a 64-bit unsigned integer and a 128-bit
174   // unsigned integer. 174   // unsigned integer.
175   BOOST_JSON_SAFEBUFFERS inline uint128 umul192_lower128(std::uint64_t x, uint128 y) noexcept 175   BOOST_JSON_SAFEBUFFERS inline uint128 umul192_lower128(std::uint64_t x, uint128 y) noexcept
176   { 176   {
177   auto high = x * y.high; 177   auto high = x * y.high;
178   auto highlow = umul128(x, y.low); 178   auto highlow = umul128(x, y.low);
179   return {high + highlow.high, highlow.low}; 179   return {high + highlow.high, highlow.low};
180   } 180   }
181   181  
182   // Get lower 64-bits of multiplication of a 32-bit unsigned integer and a 64-bit 182   // Get lower 64-bits of multiplication of a 32-bit unsigned integer and a 64-bit
183   // unsigned integer. 183   // unsigned integer.
184   inline std::uint64_t umul96_lower64(std::uint32_t x, std::uint64_t y) noexcept 184   inline std::uint64_t umul96_lower64(std::uint32_t x, std::uint64_t y) noexcept
185   { 185   {
186   return x * y; 186   return x * y;
187   } 187   }
188   188  
189   }}}}} // Namespaces 189   }}}}} // Namespaces
190   190  
191   #endif // BOOST_JSON_DETAIL_CHARCONV_DETAIL_EMULATED128_HPP 191   #endif // BOOST_JSON_DETAIL_CHARCONV_DETAIL_EMULATED128_HPP