96 lines · plain
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-exception6//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 Guide16static __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 < d22 return 0;23 if (sr == N - 1) // d == 124 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 < d51 return n;52 if (sr == N - 1) // d == 153 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_UDIV73static __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 : 076 fixint_t s_b = b >> N; // s_b = b < 0 ? -1 : 077 fixuint_t a_u = (fixuint_t)(a ^ s_a) + (-s_a); // negate if s_a == -178 fixuint_t b_u = (fixuint_t)(b ^ s_b) + (-s_b); // negate if s_b == -179 s_a ^= s_b; // sign of quotient80 return (COMPUTE_UDIV(a_u, b_u) ^ s_a) + (-s_a); // negate if s_a == -181}82#endif // COMPUTE_UDIV83 84#ifdef ASSIGN_UMOD85static __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 : 088 fixuint_t b_u = (fixuint_t)(b ^ s) + (-s); // negate if s == -189 s = a >> N; // s = a < 0 ? -1 : 090 fixuint_t a_u = (fixuint_t)(a ^ s) + (-s); // negate if s == -191 fixuint_t res;92 ASSIGN_UMOD(res, a_u, b_u);93 return (res ^ s) + (-s); // negate if s == -194}95#endif // ASSIGN_UMOD96