| 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 |