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

source code of compiler-rt/lib/builtins/int_div_impl.inc