Daniel Boulby | 318e7a5 | 2022-10-21 20:20:52 +0100 | [diff] [blame] | 1 | //===-- int_div_impl.inc - Integer division ---------------------*- 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 | // Helpers used by __udivsi3, __umodsi3, __udivdi3, and __umodsi3. |
| 10 | // |
| 11 | //===----------------------------------------------------------------------===// |
| 12 | |
| 13 | #define clz(a) (sizeof(a) == sizeof(unsigned long long) ? __builtin_clzll(a) : clzsi(a)) |
| 14 | |
| 15 | // Adapted from Figure 3-40 of The PowerPC Compiler Writer's Guide |
| 16 | static __inline fixuint_t __udivXi3(fixuint_t n, fixuint_t d) { |
| 17 | const unsigned N = sizeof(fixuint_t) * CHAR_BIT; |
| 18 | // d == 0 cases are unspecified. |
| 19 | unsigned sr = (d ? clz(d) : N) - (n ? clz(n) : N); |
| 20 | // 0 <= sr <= N - 1 or sr is very large. |
| 21 | if (sr > N - 1) // n < d |
| 22 | return 0; |
| 23 | if (sr == N - 1) // d == 1 |
| 24 | return n; |
| 25 | ++sr; |
| 26 | // 1 <= sr <= N - 1. Shifts do not trigger UB. |
| 27 | fixuint_t r = n >> sr; |
| 28 | n <<= N - sr; |
| 29 | fixuint_t carry = 0; |
| 30 | for (; sr > 0; --sr) { |
| 31 | r = (r << 1) | (n >> (N - 1)); |
| 32 | n = (n << 1) | carry; |
| 33 | // Branch-less version of: |
| 34 | // carry = 0; |
| 35 | // if (r >= d) r -= d, carry = 1; |
| 36 | const fixint_t s = (fixint_t)(d - r - 1) >> (N - 1); |
| 37 | carry = s & 1; |
| 38 | r -= d & s; |
| 39 | } |
| 40 | n = (n << 1) | carry; |
| 41 | return n; |
| 42 | } |
| 43 | |
| 44 | // Mostly identical to __udivXi3 but the return values are different. |
| 45 | static __inline fixuint_t __umodXi3(fixuint_t n, fixuint_t d) { |
| 46 | const unsigned N = sizeof(fixuint_t) * CHAR_BIT; |
| 47 | // d == 0 cases are unspecified. |
| 48 | unsigned sr = (d ? clz(d) : N) - (n ? clz(n) : N); |
| 49 | // 0 <= sr <= N - 1 or sr is very large. |
| 50 | if (sr > N - 1) // n < d |
| 51 | return n; |
| 52 | if (sr == N - 1) // d == 1 |
| 53 | return 0; |
| 54 | ++sr; |
| 55 | // 1 <= sr <= N - 1. Shifts do not trigger UB. |
| 56 | fixuint_t r = n >> sr; |
| 57 | n <<= N - sr; |
| 58 | fixuint_t carry = 0; |
| 59 | for (; sr > 0; --sr) { |
| 60 | r = (r << 1) | (n >> (N - 1)); |
| 61 | n = (n << 1) | carry; |
| 62 | // Branch-less version of: |
| 63 | // carry = 0; |
| 64 | // if (r >= d) r -= d, carry = 1; |
| 65 | const fixint_t s = (fixint_t)(d - r - 1) >> (N - 1); |
| 66 | carry = s & 1; |
| 67 | r -= d & s; |
| 68 | } |
| 69 | return r; |
| 70 | } |
| 71 | |
| 72 | #ifdef COMPUTE_UDIV |
| 73 | static __inline fixint_t __divXi3(fixint_t a, fixint_t b) { |
| 74 | const int N = (int)(sizeof(fixint_t) * CHAR_BIT) - 1; |
| 75 | fixint_t s_a = a >> N; // s_a = a < 0 ? -1 : 0 |
| 76 | fixint_t s_b = b >> N; // s_b = b < 0 ? -1 : 0 |
| 77 | fixuint_t a_u = (fixuint_t)(a ^ s_a) + (-s_a); // negate if s_a == -1 |
| 78 | fixuint_t b_u = (fixuint_t)(b ^ s_b) + (-s_b); // negate if s_b == -1 |
| 79 | s_a ^= s_b; // sign of quotient |
| 80 | return (COMPUTE_UDIV(a_u, b_u) ^ s_a) + (-s_a); // negate if s_a == -1 |
| 81 | } |
| 82 | #endif // COMPUTE_UDIV |
| 83 | |
| 84 | #ifdef ASSIGN_UMOD |
| 85 | static __inline fixint_t __modXi3(fixint_t a, fixint_t b) { |
| 86 | const int N = (int)(sizeof(fixint_t) * CHAR_BIT) - 1; |
| 87 | fixint_t s = b >> N; // s = b < 0 ? -1 : 0 |
| 88 | fixuint_t b_u = (fixuint_t)(b ^ s) + (-s); // negate if s == -1 |
| 89 | s = a >> N; // s = a < 0 ? -1 : 0 |
| 90 | fixuint_t a_u = (fixuint_t)(a ^ s) + (-s); // negate if s == -1 |
| 91 | fixuint_t res; |
| 92 | ASSIGN_UMOD(res, a_u, b_u); |
| 93 | return (res ^ s) + (-s); // negate if s == -1 |
| 94 | } |
| 95 | #endif // ASSIGN_UMOD |