1 | //===-- llvm/Support/MathExtras.h - Useful math functions -------*- C++ -*-===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | // This file contains some functions that are useful for math stuff. |
10 | // |
11 | //===----------------------------------------------------------------------===// |
12 | |
13 | #ifndef LLVM_SUPPORT_MATHEXTRAS_H |
14 | #define |
15 | |
16 | #include "llvm/ADT/bit.h" |
17 | #include "llvm/Support/Compiler.h" |
18 | #include <cassert> |
19 | #include <climits> |
20 | #include <cstdint> |
21 | #include <cstring> |
22 | #include <limits> |
23 | #include <type_traits> |
24 | |
25 | namespace llvm { |
26 | |
27 | /// Mathematical constants. |
28 | namespace numbers { |
29 | // TODO: Track C++20 std::numbers. |
30 | // TODO: Favor using the hexadecimal FP constants (requires C++17). |
31 | constexpr double e = 2.7182818284590452354, // (0x1.5bf0a8b145749P+1) https://oeis.org/A001113 |
32 | egamma = .57721566490153286061, // (0x1.2788cfc6fb619P-1) https://oeis.org/A001620 |
33 | ln2 = .69314718055994530942, // (0x1.62e42fefa39efP-1) https://oeis.org/A002162 |
34 | ln10 = 2.3025850929940456840, // (0x1.24bb1bbb55516P+1) https://oeis.org/A002392 |
35 | log2e = 1.4426950408889634074, // (0x1.71547652b82feP+0) |
36 | log10e = .43429448190325182765, // (0x1.bcb7b1526e50eP-2) |
37 | pi = 3.1415926535897932385, // (0x1.921fb54442d18P+1) https://oeis.org/A000796 |
38 | inv_pi = .31830988618379067154, // (0x1.45f306bc9c883P-2) https://oeis.org/A049541 |
39 | sqrtpi = 1.7724538509055160273, // (0x1.c5bf891b4ef6bP+0) https://oeis.org/A002161 |
40 | inv_sqrtpi = .56418958354775628695, // (0x1.20dd750429b6dP-1) https://oeis.org/A087197 |
41 | sqrt2 = 1.4142135623730950488, // (0x1.6a09e667f3bcdP+0) https://oeis.org/A00219 |
42 | inv_sqrt2 = .70710678118654752440, // (0x1.6a09e667f3bcdP-1) |
43 | sqrt3 = 1.7320508075688772935, // (0x1.bb67ae8584caaP+0) https://oeis.org/A002194 |
44 | inv_sqrt3 = .57735026918962576451, // (0x1.279a74590331cP-1) |
45 | phi = 1.6180339887498948482; // (0x1.9e3779b97f4a8P+0) https://oeis.org/A001622 |
46 | constexpr float ef = 2.71828183F, // (0x1.5bf0a8P+1) https://oeis.org/A001113 |
47 | egammaf = .577215665F, // (0x1.2788d0P-1) https://oeis.org/A001620 |
48 | ln2f = .693147181F, // (0x1.62e430P-1) https://oeis.org/A002162 |
49 | ln10f = 2.30258509F, // (0x1.26bb1cP+1) https://oeis.org/A002392 |
50 | log2ef = 1.44269504F, // (0x1.715476P+0) |
51 | log10ef = .434294482F, // (0x1.bcb7b2P-2) |
52 | pif = 3.14159265F, // (0x1.921fb6P+1) https://oeis.org/A000796 |
53 | inv_pif = .318309886F, // (0x1.45f306P-2) https://oeis.org/A049541 |
54 | sqrtpif = 1.77245385F, // (0x1.c5bf8aP+0) https://oeis.org/A002161 |
55 | inv_sqrtpif = .564189584F, // (0x1.20dd76P-1) https://oeis.org/A087197 |
56 | sqrt2f = 1.41421356F, // (0x1.6a09e6P+0) https://oeis.org/A002193 |
57 | inv_sqrt2f = .707106781F, // (0x1.6a09e6P-1) |
58 | sqrt3f = 1.73205081F, // (0x1.bb67aeP+0) https://oeis.org/A002194 |
59 | inv_sqrt3f = .577350269F, // (0x1.279a74P-1) |
60 | phif = 1.61803399F; // (0x1.9e377aP+0) https://oeis.org/A001622 |
61 | } // namespace numbers |
62 | |
63 | /// Create a bitmask with the N right-most bits set to 1, and all other |
64 | /// bits set to 0. Only unsigned types are allowed. |
65 | template <typename T> T maskTrailingOnes(unsigned N) { |
66 | static_assert(std::is_unsigned_v<T>, "Invalid type!" ); |
67 | const unsigned Bits = CHAR_BIT * sizeof(T); |
68 | assert(N <= Bits && "Invalid bit index" ); |
69 | if (N == 0) |
70 | return 0; |
71 | return T(-1) >> (Bits - N); |
72 | } |
73 | |
74 | /// Create a bitmask with the N left-most bits set to 1, and all other |
75 | /// bits set to 0. Only unsigned types are allowed. |
76 | template <typename T> T maskLeadingOnes(unsigned N) { |
77 | return ~maskTrailingOnes<T>(CHAR_BIT * sizeof(T) - N); |
78 | } |
79 | |
80 | /// Create a bitmask with the N right-most bits set to 0, and all other |
81 | /// bits set to 1. Only unsigned types are allowed. |
82 | template <typename T> T maskTrailingZeros(unsigned N) { |
83 | return maskLeadingOnes<T>(CHAR_BIT * sizeof(T) - N); |
84 | } |
85 | |
86 | /// Create a bitmask with the N left-most bits set to 0, and all other |
87 | /// bits set to 1. Only unsigned types are allowed. |
88 | template <typename T> T maskLeadingZeros(unsigned N) { |
89 | return maskTrailingOnes<T>(CHAR_BIT * sizeof(T) - N); |
90 | } |
91 | |
92 | /// Macro compressed bit reversal table for 256 bits. |
93 | /// |
94 | /// http://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable |
95 | static const unsigned char BitReverseTable256[256] = { |
96 | #define R2(n) n, n + 2 * 64, n + 1 * 64, n + 3 * 64 |
97 | #define R4(n) R2(n), R2(n + 2 * 16), R2(n + 1 * 16), R2(n + 3 * 16) |
98 | #define R6(n) R4(n), R4(n + 2 * 4), R4(n + 1 * 4), R4(n + 3 * 4) |
99 | R6(0), R6(2), R6(1), R6(3) |
100 | #undef R2 |
101 | #undef R4 |
102 | #undef R6 |
103 | }; |
104 | |
105 | /// Reverse the bits in \p Val. |
106 | template <typename T> T reverseBits(T Val) { |
107 | #if __has_builtin(__builtin_bitreverse8) |
108 | if constexpr (std::is_same_v<T, uint8_t>) |
109 | return __builtin_bitreverse8(Val); |
110 | #endif |
111 | #if __has_builtin(__builtin_bitreverse16) |
112 | if constexpr (std::is_same_v<T, uint16_t>) |
113 | return __builtin_bitreverse16(Val); |
114 | #endif |
115 | #if __has_builtin(__builtin_bitreverse32) |
116 | if constexpr (std::is_same_v<T, uint32_t>) |
117 | return __builtin_bitreverse32(Val); |
118 | #endif |
119 | #if __has_builtin(__builtin_bitreverse64) |
120 | if constexpr (std::is_same_v<T, uint64_t>) |
121 | return __builtin_bitreverse64(Val); |
122 | #endif |
123 | |
124 | unsigned char in[sizeof(Val)]; |
125 | unsigned char out[sizeof(Val)]; |
126 | std::memcpy(dest: in, src: &Val, n: sizeof(Val)); |
127 | for (unsigned i = 0; i < sizeof(Val); ++i) |
128 | out[(sizeof(Val) - i) - 1] = BitReverseTable256[in[i]]; |
129 | std::memcpy(dest: &Val, src: out, n: sizeof(Val)); |
130 | return Val; |
131 | } |
132 | |
133 | // NOTE: The following support functions use the _32/_64 extensions instead of |
134 | // type overloading so that signed and unsigned integers can be used without |
135 | // ambiguity. |
136 | |
137 | /// Return the high 32 bits of a 64 bit value. |
138 | constexpr inline uint32_t Hi_32(uint64_t Value) { |
139 | return static_cast<uint32_t>(Value >> 32); |
140 | } |
141 | |
142 | /// Return the low 32 bits of a 64 bit value. |
143 | constexpr inline uint32_t Lo_32(uint64_t Value) { |
144 | return static_cast<uint32_t>(Value); |
145 | } |
146 | |
147 | /// Make a 64-bit integer from a high / low pair of 32-bit integers. |
148 | constexpr inline uint64_t Make_64(uint32_t High, uint32_t Low) { |
149 | return ((uint64_t)High << 32) | (uint64_t)Low; |
150 | } |
151 | |
152 | /// Checks if an integer fits into the given bit width. |
153 | template <unsigned N> constexpr inline bool isInt(int64_t x) { |
154 | if constexpr (N == 0) |
155 | return 0 == x; |
156 | if constexpr (N == 8) |
157 | return static_cast<int8_t>(x) == x; |
158 | if constexpr (N == 16) |
159 | return static_cast<int16_t>(x) == x; |
160 | if constexpr (N == 32) |
161 | return static_cast<int32_t>(x) == x; |
162 | if constexpr (N < 64) |
163 | return -(INT64_C(1) << (N - 1)) <= x && x < (INT64_C(1) << (N - 1)); |
164 | (void)x; // MSVC v19.25 warns that x is unused. |
165 | return true; |
166 | } |
167 | |
168 | /// Checks if a signed integer is an N bit number shifted left by S. |
169 | template <unsigned N, unsigned S> |
170 | constexpr inline bool isShiftedInt(int64_t x) { |
171 | static_assert(S < 64, "isShiftedInt<N, S> with S >= 64 is too much." ); |
172 | static_assert(N + S <= 64, "isShiftedInt<N, S> with N + S > 64 is too wide." ); |
173 | return isInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0); |
174 | } |
175 | |
176 | /// Checks if an unsigned integer fits into the given bit width. |
177 | template <unsigned N> constexpr inline bool isUInt(uint64_t x) { |
178 | if constexpr (N == 0) |
179 | return 0 == x; |
180 | if constexpr (N == 8) |
181 | return static_cast<uint8_t>(x) == x; |
182 | if constexpr (N == 16) |
183 | return static_cast<uint16_t>(x) == x; |
184 | if constexpr (N == 32) |
185 | return static_cast<uint32_t>(x) == x; |
186 | if constexpr (N < 64) |
187 | return x < (UINT64_C(1) << (N)); |
188 | (void)x; // MSVC v19.25 warns that x is unused. |
189 | return true; |
190 | } |
191 | |
192 | /// Checks if a unsigned integer is an N bit number shifted left by S. |
193 | template <unsigned N, unsigned S> |
194 | constexpr inline bool isShiftedUInt(uint64_t x) { |
195 | static_assert(S < 64, "isShiftedUInt<N, S> with S >= 64 is too much." ); |
196 | static_assert(N + S <= 64, |
197 | "isShiftedUInt<N, S> with N + S > 64 is too wide." ); |
198 | // S must be strictly less than 64. So 1 << S is not undefined behavior. |
199 | return isUInt<N + S>(x) && (x % (UINT64_C(1) << S) == 0); |
200 | } |
201 | |
202 | /// Gets the maximum value for a N-bit unsigned integer. |
203 | inline uint64_t maxUIntN(uint64_t N) { |
204 | assert(N <= 64 && "integer width out of range" ); |
205 | |
206 | // uint64_t(1) << 64 is undefined behavior, so we can't do |
207 | // (uint64_t(1) << N) - 1 |
208 | // without checking first that N != 64. But this works and doesn't have a |
209 | // branch for N != 0. |
210 | // Unfortunately, shifting a uint64_t right by 64 bit is undefined |
211 | // behavior, so the condition on N == 0 is necessary. Fortunately, most |
212 | // optimizers do not emit branches for this check. |
213 | if (N == 0) |
214 | return 0; |
215 | return UINT64_MAX >> (64 - N); |
216 | } |
217 | |
218 | /// Gets the minimum value for a N-bit signed integer. |
219 | inline int64_t minIntN(int64_t N) { |
220 | assert(N <= 64 && "integer width out of range" ); |
221 | |
222 | if (N == 0) |
223 | return 0; |
224 | return UINT64_C(1) + ~(UINT64_C(1) << (N - 1)); |
225 | } |
226 | |
227 | /// Gets the maximum value for a N-bit signed integer. |
228 | inline int64_t maxIntN(int64_t N) { |
229 | assert(N <= 64 && "integer width out of range" ); |
230 | |
231 | // This relies on two's complement wraparound when N == 64, so we convert to |
232 | // int64_t only at the very end to avoid UB. |
233 | if (N == 0) |
234 | return 0; |
235 | return (UINT64_C(1) << (N - 1)) - 1; |
236 | } |
237 | |
238 | /// Checks if an unsigned integer fits into the given (dynamic) bit width. |
239 | inline bool isUIntN(unsigned N, uint64_t x) { |
240 | return N >= 64 || x <= maxUIntN(N); |
241 | } |
242 | |
243 | /// Checks if an signed integer fits into the given (dynamic) bit width. |
244 | inline bool isIntN(unsigned N, int64_t x) { |
245 | return N >= 64 || (minIntN(N) <= x && x <= maxIntN(N)); |
246 | } |
247 | |
248 | /// Return true if the argument is a non-empty sequence of ones starting at the |
249 | /// least significant bit with the remainder zero (32 bit version). |
250 | /// Ex. isMask_32(0x0000FFFFU) == true. |
251 | constexpr inline bool isMask_32(uint32_t Value) { |
252 | return Value && ((Value + 1) & Value) == 0; |
253 | } |
254 | |
255 | /// Return true if the argument is a non-empty sequence of ones starting at the |
256 | /// least significant bit with the remainder zero (64 bit version). |
257 | constexpr inline bool isMask_64(uint64_t Value) { |
258 | return Value && ((Value + 1) & Value) == 0; |
259 | } |
260 | |
261 | /// Return true if the argument contains a non-empty sequence of ones with the |
262 | /// remainder zero (32 bit version.) Ex. isShiftedMask_32(0x0000FF00U) == true. |
263 | constexpr inline bool isShiftedMask_32(uint32_t Value) { |
264 | return Value && isMask_32(Value: (Value - 1) | Value); |
265 | } |
266 | |
267 | /// Return true if the argument contains a non-empty sequence of ones with the |
268 | /// remainder zero (64 bit version.) |
269 | constexpr inline bool isShiftedMask_64(uint64_t Value) { |
270 | return Value && isMask_64(Value: (Value - 1) | Value); |
271 | } |
272 | |
273 | /// Return true if the argument is a power of two > 0. |
274 | /// Ex. isPowerOf2_32(0x00100000U) == true (32 bit edition.) |
275 | constexpr inline bool isPowerOf2_32(uint32_t Value) { |
276 | return llvm::has_single_bit(Value); |
277 | } |
278 | |
279 | /// Return true if the argument is a power of two > 0 (64 bit edition.) |
280 | constexpr inline bool isPowerOf2_64(uint64_t Value) { |
281 | return llvm::has_single_bit(Value); |
282 | } |
283 | |
284 | /// Return true if the argument contains a non-empty sequence of ones with the |
285 | /// remainder zero (32 bit version.) Ex. isShiftedMask_32(0x0000FF00U) == true. |
286 | /// If true, \p MaskIdx will specify the index of the lowest set bit and \p |
287 | /// MaskLen is updated to specify the length of the mask, else neither are |
288 | /// updated. |
289 | inline bool isShiftedMask_32(uint32_t Value, unsigned &MaskIdx, |
290 | unsigned &MaskLen) { |
291 | if (!isShiftedMask_32(Value)) |
292 | return false; |
293 | MaskIdx = llvm::countr_zero(Val: Value); |
294 | MaskLen = llvm::popcount(Value); |
295 | return true; |
296 | } |
297 | |
298 | /// Return true if the argument contains a non-empty sequence of ones with the |
299 | /// remainder zero (64 bit version.) If true, \p MaskIdx will specify the index |
300 | /// of the lowest set bit and \p MaskLen is updated to specify the length of the |
301 | /// mask, else neither are updated. |
302 | inline bool isShiftedMask_64(uint64_t Value, unsigned &MaskIdx, |
303 | unsigned &MaskLen) { |
304 | if (!isShiftedMask_64(Value)) |
305 | return false; |
306 | MaskIdx = llvm::countr_zero(Val: Value); |
307 | MaskLen = llvm::popcount(Value); |
308 | return true; |
309 | } |
310 | |
311 | /// Compile time Log2. |
312 | /// Valid only for positive powers of two. |
313 | template <size_t kValue> constexpr inline size_t CTLog2() { |
314 | static_assert(kValue > 0 && llvm::isPowerOf2_64(Value: kValue), |
315 | "Value is not a valid power of 2" ); |
316 | return 1 + CTLog2<kValue / 2>(); |
317 | } |
318 | |
319 | template <> constexpr inline size_t CTLog2<1>() { return 0; } |
320 | |
321 | /// Return the floor log base 2 of the specified value, -1 if the value is zero. |
322 | /// (32 bit edition.) |
323 | /// Ex. Log2_32(32) == 5, Log2_32(1) == 0, Log2_32(0) == -1, Log2_32(6) == 2 |
324 | inline unsigned Log2_32(uint32_t Value) { |
325 | return 31 - llvm::countl_zero(Val: Value); |
326 | } |
327 | |
328 | /// Return the floor log base 2 of the specified value, -1 if the value is zero. |
329 | /// (64 bit edition.) |
330 | inline unsigned Log2_64(uint64_t Value) { |
331 | return 63 - llvm::countl_zero(Val: Value); |
332 | } |
333 | |
334 | /// Return the ceil log base 2 of the specified value, 32 if the value is zero. |
335 | /// (32 bit edition). |
336 | /// Ex. Log2_32_Ceil(32) == 5, Log2_32_Ceil(1) == 0, Log2_32_Ceil(6) == 3 |
337 | inline unsigned Log2_32_Ceil(uint32_t Value) { |
338 | return 32 - llvm::countl_zero(Val: Value - 1); |
339 | } |
340 | |
341 | /// Return the ceil log base 2 of the specified value, 64 if the value is zero. |
342 | /// (64 bit edition.) |
343 | inline unsigned Log2_64_Ceil(uint64_t Value) { |
344 | return 64 - llvm::countl_zero(Val: Value - 1); |
345 | } |
346 | |
347 | /// A and B are either alignments or offsets. Return the minimum alignment that |
348 | /// may be assumed after adding the two together. |
349 | constexpr inline uint64_t MinAlign(uint64_t A, uint64_t B) { |
350 | // The largest power of 2 that divides both A and B. |
351 | // |
352 | // Replace "-Value" by "1+~Value" in the following commented code to avoid |
353 | // MSVC warning C4146 |
354 | // return (A | B) & -(A | B); |
355 | return (A | B) & (1 + ~(A | B)); |
356 | } |
357 | |
358 | /// Returns the next power of two (in 64-bits) that is strictly greater than A. |
359 | /// Returns zero on overflow. |
360 | constexpr inline uint64_t NextPowerOf2(uint64_t A) { |
361 | A |= (A >> 1); |
362 | A |= (A >> 2); |
363 | A |= (A >> 4); |
364 | A |= (A >> 8); |
365 | A |= (A >> 16); |
366 | A |= (A >> 32); |
367 | return A + 1; |
368 | } |
369 | |
370 | /// Returns the power of two which is greater than or equal to the given value. |
371 | /// Essentially, it is a ceil operation across the domain of powers of two. |
372 | inline uint64_t PowerOf2Ceil(uint64_t A) { |
373 | if (!A || A > UINT64_MAX / 2) |
374 | return 0; |
375 | return UINT64_C(1) << Log2_64_Ceil(Value: A); |
376 | } |
377 | |
378 | /// Returns the next integer (mod 2**64) that is greater than or equal to |
379 | /// \p Value and is a multiple of \p Align. \p Align must be non-zero. |
380 | /// |
381 | /// Examples: |
382 | /// \code |
383 | /// alignTo(5, 8) = 8 |
384 | /// alignTo(17, 8) = 24 |
385 | /// alignTo(~0LL, 8) = 0 |
386 | /// alignTo(321, 255) = 510 |
387 | /// \endcode |
388 | inline uint64_t alignTo(uint64_t Value, uint64_t Align) { |
389 | assert(Align != 0u && "Align can't be 0." ); |
390 | return (Value + Align - 1) / Align * Align; |
391 | } |
392 | |
393 | inline uint64_t alignToPowerOf2(uint64_t Value, uint64_t Align) { |
394 | assert(Align != 0 && (Align & (Align - 1)) == 0 && |
395 | "Align must be a power of 2" ); |
396 | // Replace unary minus to avoid compilation error on Windows: |
397 | // "unary minus operator applied to unsigned type, result still unsigned" |
398 | uint64_t negAlign = (~Align) + 1; |
399 | return (Value + Align - 1) & negAlign; |
400 | } |
401 | |
402 | /// If non-zero \p Skew is specified, the return value will be a minimal integer |
403 | /// that is greater than or equal to \p Size and equal to \p A * N + \p Skew for |
404 | /// some integer N. If \p Skew is larger than \p A, its value is adjusted to '\p |
405 | /// Skew mod \p A'. \p Align must be non-zero. |
406 | /// |
407 | /// Examples: |
408 | /// \code |
409 | /// alignTo(5, 8, 7) = 7 |
410 | /// alignTo(17, 8, 1) = 17 |
411 | /// alignTo(~0LL, 8, 3) = 3 |
412 | /// alignTo(321, 255, 42) = 552 |
413 | /// \endcode |
414 | inline uint64_t alignTo(uint64_t Value, uint64_t Align, uint64_t Skew) { |
415 | assert(Align != 0u && "Align can't be 0." ); |
416 | Skew %= Align; |
417 | return alignTo(Value: Value - Skew, Align) + Skew; |
418 | } |
419 | |
420 | /// Returns the next integer (mod 2**64) that is greater than or equal to |
421 | /// \p Value and is a multiple of \c Align. \c Align must be non-zero. |
422 | template <uint64_t Align> constexpr inline uint64_t alignTo(uint64_t Value) { |
423 | static_assert(Align != 0u, "Align must be non-zero" ); |
424 | return (Value + Align - 1) / Align * Align; |
425 | } |
426 | |
427 | /// Returns the integer ceil(Numerator / Denominator). |
428 | inline uint64_t divideCeil(uint64_t Numerator, uint64_t Denominator) { |
429 | return alignTo(Value: Numerator, Align: Denominator) / Denominator; |
430 | } |
431 | |
432 | /// Returns the integer nearest(Numerator / Denominator). |
433 | inline uint64_t divideNearest(uint64_t Numerator, uint64_t Denominator) { |
434 | return (Numerator + (Denominator / 2)) / Denominator; |
435 | } |
436 | |
437 | /// Returns the largest uint64_t less than or equal to \p Value and is |
438 | /// \p Skew mod \p Align. \p Align must be non-zero |
439 | inline uint64_t alignDown(uint64_t Value, uint64_t Align, uint64_t Skew = 0) { |
440 | assert(Align != 0u && "Align can't be 0." ); |
441 | Skew %= Align; |
442 | return (Value - Skew) / Align * Align + Skew; |
443 | } |
444 | |
445 | /// Sign-extend the number in the bottom B bits of X to a 32-bit integer. |
446 | /// Requires B <= 32. |
447 | template <unsigned B> constexpr inline int32_t SignExtend32(uint32_t X) { |
448 | static_assert(B <= 32, "Bit width out of range." ); |
449 | if constexpr (B == 0) |
450 | return 0; |
451 | return int32_t(X << (32 - B)) >> (32 - B); |
452 | } |
453 | |
454 | /// Sign-extend the number in the bottom B bits of X to a 32-bit integer. |
455 | /// Requires B <= 32. |
456 | inline int32_t SignExtend32(uint32_t X, unsigned B) { |
457 | assert(B <= 32 && "Bit width out of range." ); |
458 | if (B == 0) |
459 | return 0; |
460 | return int32_t(X << (32 - B)) >> (32 - B); |
461 | } |
462 | |
463 | /// Sign-extend the number in the bottom B bits of X to a 64-bit integer. |
464 | /// Requires B <= 64. |
465 | template <unsigned B> constexpr inline int64_t SignExtend64(uint64_t x) { |
466 | static_assert(B <= 64, "Bit width out of range." ); |
467 | if constexpr (B == 0) |
468 | return 0; |
469 | return int64_t(x << (64 - B)) >> (64 - B); |
470 | } |
471 | |
472 | /// Sign-extend the number in the bottom B bits of X to a 64-bit integer. |
473 | /// Requires B <= 64. |
474 | inline int64_t SignExtend64(uint64_t X, unsigned B) { |
475 | assert(B <= 64 && "Bit width out of range." ); |
476 | if (B == 0) |
477 | return 0; |
478 | return int64_t(X << (64 - B)) >> (64 - B); |
479 | } |
480 | |
481 | /// Subtract two unsigned integers, X and Y, of type T and return the absolute |
482 | /// value of the result. |
483 | template <typename T> |
484 | std::enable_if_t<std::is_unsigned_v<T>, T> AbsoluteDifference(T X, T Y) { |
485 | return X > Y ? (X - Y) : (Y - X); |
486 | } |
487 | |
488 | /// Add two unsigned integers, X and Y, of type T. Clamp the result to the |
489 | /// maximum representable value of T on overflow. ResultOverflowed indicates if |
490 | /// the result is larger than the maximum representable value of type T. |
491 | template <typename T> |
492 | std::enable_if_t<std::is_unsigned_v<T>, T> |
493 | SaturatingAdd(T X, T Y, bool *ResultOverflowed = nullptr) { |
494 | bool Dummy; |
495 | bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy; |
496 | // Hacker's Delight, p. 29 |
497 | T Z = X + Y; |
498 | Overflowed = (Z < X || Z < Y); |
499 | if (Overflowed) |
500 | return std::numeric_limits<T>::max(); |
501 | else |
502 | return Z; |
503 | } |
504 | |
505 | /// Add multiple unsigned integers of type T. Clamp the result to the |
506 | /// maximum representable value of T on overflow. |
507 | template <class T, class... Ts> |
508 | std::enable_if_t<std::is_unsigned_v<T>, T> SaturatingAdd(T X, T Y, T Z, |
509 | Ts... Args) { |
510 | bool Overflowed = false; |
511 | T XY = SaturatingAdd(X, Y, &Overflowed); |
512 | if (Overflowed) |
513 | return SaturatingAdd(std::numeric_limits<T>::max(), T(1), Args...); |
514 | return SaturatingAdd(XY, Z, Args...); |
515 | } |
516 | |
517 | /// Multiply two unsigned integers, X and Y, of type T. Clamp the result to the |
518 | /// maximum representable value of T on overflow. ResultOverflowed indicates if |
519 | /// the result is larger than the maximum representable value of type T. |
520 | template <typename T> |
521 | std::enable_if_t<std::is_unsigned_v<T>, T> |
522 | SaturatingMultiply(T X, T Y, bool *ResultOverflowed = nullptr) { |
523 | bool Dummy; |
524 | bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy; |
525 | |
526 | // Hacker's Delight, p. 30 has a different algorithm, but we don't use that |
527 | // because it fails for uint16_t (where multiplication can have undefined |
528 | // behavior due to promotion to int), and requires a division in addition |
529 | // to the multiplication. |
530 | |
531 | Overflowed = false; |
532 | |
533 | // Log2(Z) would be either Log2Z or Log2Z + 1. |
534 | // Special case: if X or Y is 0, Log2_64 gives -1, and Log2Z |
535 | // will necessarily be less than Log2Max as desired. |
536 | int Log2Z = Log2_64(X) + Log2_64(Y); |
537 | const T Max = std::numeric_limits<T>::max(); |
538 | int Log2Max = Log2_64(Max); |
539 | if (Log2Z < Log2Max) { |
540 | return X * Y; |
541 | } |
542 | if (Log2Z > Log2Max) { |
543 | Overflowed = true; |
544 | return Max; |
545 | } |
546 | |
547 | // We're going to use the top bit, and maybe overflow one |
548 | // bit past it. Multiply all but the bottom bit then add |
549 | // that on at the end. |
550 | T Z = (X >> 1) * Y; |
551 | if (Z & ~(Max >> 1)) { |
552 | Overflowed = true; |
553 | return Max; |
554 | } |
555 | Z <<= 1; |
556 | if (X & 1) |
557 | return SaturatingAdd(Z, Y, ResultOverflowed); |
558 | |
559 | return Z; |
560 | } |
561 | |
562 | /// Multiply two unsigned integers, X and Y, and add the unsigned integer, A to |
563 | /// the product. Clamp the result to the maximum representable value of T on |
564 | /// overflow. ResultOverflowed indicates if the result is larger than the |
565 | /// maximum representable value of type T. |
566 | template <typename T> |
567 | std::enable_if_t<std::is_unsigned_v<T>, T> |
568 | SaturatingMultiplyAdd(T X, T Y, T A, bool *ResultOverflowed = nullptr) { |
569 | bool Dummy; |
570 | bool &Overflowed = ResultOverflowed ? *ResultOverflowed : Dummy; |
571 | |
572 | T Product = SaturatingMultiply(X, Y, &Overflowed); |
573 | if (Overflowed) |
574 | return Product; |
575 | |
576 | return SaturatingAdd(A, Product, &Overflowed); |
577 | } |
578 | |
579 | /// Use this rather than HUGE_VALF; the latter causes warnings on MSVC. |
580 | extern const float huge_valf; |
581 | |
582 | /// Add two signed integers, computing the two's complement truncated result, |
583 | /// returning true if overflow occurred. |
584 | template <typename T> |
585 | std::enable_if_t<std::is_signed_v<T>, T> AddOverflow(T X, T Y, T &Result) { |
586 | #if __has_builtin(__builtin_add_overflow) |
587 | return __builtin_add_overflow(X, Y, &Result); |
588 | #else |
589 | // Perform the unsigned addition. |
590 | using U = std::make_unsigned_t<T>; |
591 | const U UX = static_cast<U>(X); |
592 | const U UY = static_cast<U>(Y); |
593 | const U UResult = UX + UY; |
594 | |
595 | // Convert to signed. |
596 | Result = static_cast<T>(UResult); |
597 | |
598 | // Adding two positive numbers should result in a positive number. |
599 | if (X > 0 && Y > 0) |
600 | return Result <= 0; |
601 | // Adding two negatives should result in a negative number. |
602 | if (X < 0 && Y < 0) |
603 | return Result >= 0; |
604 | return false; |
605 | #endif |
606 | } |
607 | |
608 | /// Subtract two signed integers, computing the two's complement truncated |
609 | /// result, returning true if an overflow ocurred. |
610 | template <typename T> |
611 | std::enable_if_t<std::is_signed_v<T>, T> SubOverflow(T X, T Y, T &Result) { |
612 | #if __has_builtin(__builtin_sub_overflow) |
613 | return __builtin_sub_overflow(X, Y, &Result); |
614 | #else |
615 | // Perform the unsigned addition. |
616 | using U = std::make_unsigned_t<T>; |
617 | const U UX = static_cast<U>(X); |
618 | const U UY = static_cast<U>(Y); |
619 | const U UResult = UX - UY; |
620 | |
621 | // Convert to signed. |
622 | Result = static_cast<T>(UResult); |
623 | |
624 | // Subtracting a positive number from a negative results in a negative number. |
625 | if (X <= 0 && Y > 0) |
626 | return Result >= 0; |
627 | // Subtracting a negative number from a positive results in a positive number. |
628 | if (X >= 0 && Y < 0) |
629 | return Result <= 0; |
630 | return false; |
631 | #endif |
632 | } |
633 | |
634 | /// Multiply two signed integers, computing the two's complement truncated |
635 | /// result, returning true if an overflow ocurred. |
636 | template <typename T> |
637 | std::enable_if_t<std::is_signed_v<T>, T> MulOverflow(T X, T Y, T &Result) { |
638 | // Perform the unsigned multiplication on absolute values. |
639 | using U = std::make_unsigned_t<T>; |
640 | const U UX = X < 0 ? (0 - static_cast<U>(X)) : static_cast<U>(X); |
641 | const U UY = Y < 0 ? (0 - static_cast<U>(Y)) : static_cast<U>(Y); |
642 | const U UResult = UX * UY; |
643 | |
644 | // Convert to signed. |
645 | const bool IsNegative = (X < 0) ^ (Y < 0); |
646 | Result = IsNegative ? (0 - UResult) : UResult; |
647 | |
648 | // If any of the args was 0, result is 0 and no overflow occurs. |
649 | if (UX == 0 || UY == 0) |
650 | return false; |
651 | |
652 | // UX and UY are in [1, 2^n], where n is the number of digits. |
653 | // Check how the max allowed absolute value (2^n for negative, 2^(n-1) for |
654 | // positive) divided by an argument compares to the other. |
655 | if (IsNegative) |
656 | return UX > (static_cast<U>(std::numeric_limits<T>::max()) + U(1)) / UY; |
657 | else |
658 | return UX > (static_cast<U>(std::numeric_limits<T>::max())) / UY; |
659 | } |
660 | |
661 | } // namespace llvm |
662 | |
663 | #endif |
664 | |