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