Root/detail / charconv / detail / emulated128.hpp
Prev Index Next

detail/charconv/detail/emulated128.hpp

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