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 16static __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. 45static __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 73static __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 85static __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 96