int_div_impl.inc
3.17 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
//===-- int_div_impl.inc - Integer division ---------------------*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// Helpers used by __udivsi3, __umodsi3, __udivdi3, and __umodsi3.
//
//===----------------------------------------------------------------------===//
#define clz(a) (sizeof(a) == sizeof(unsigned long long) ? __builtin_clzll(a) : clzsi(a))
// Adapted from Figure 3-40 of The PowerPC Compiler Writer's Guide
static __inline fixuint_t __udivXi3(fixuint_t n, fixuint_t d) {
const unsigned N = sizeof(fixuint_t) * CHAR_BIT;
// d == 0 cases are unspecified.
unsigned sr = (d ? clz(d) : N) - (n ? clz(n) : N);
// 0 <= sr <= N - 1 or sr is very large.
if (sr > N - 1) // n < d
return 0;
if (sr == N - 1) // d == 1
return n;
++sr;
// 1 <= sr <= N - 1. Shifts do not trigger UB.
fixuint_t r = n >> sr;
n <<= N - sr;
fixuint_t carry = 0;
for (; sr > 0; --sr) {
r = (r << 1) | (n >> (N - 1));
n = (n << 1) | carry;
// Branch-less version of:
// carry = 0;
// if (r >= d) r -= d, carry = 1;
const fixint_t s = (fixint_t)(d - r - 1) >> (N - 1);
carry = s & 1;
r -= d & s;
}
n = (n << 1) | carry;
return n;
}
// Mostly identical to __udivXi3 but the return values are different.
static __inline fixuint_t __umodXi3(fixuint_t n, fixuint_t d) {
const unsigned N = sizeof(fixuint_t) * CHAR_BIT;
// d == 0 cases are unspecified.
unsigned sr = (d ? clz(d) : N) - (n ? clz(n) : N);
// 0 <= sr <= N - 1 or sr is very large.
if (sr > N - 1) // n < d
return n;
if (sr == N - 1) // d == 1
return 0;
++sr;
// 1 <= sr <= N - 1. Shifts do not trigger UB.
fixuint_t r = n >> sr;
n <<= N - sr;
fixuint_t carry = 0;
for (; sr > 0; --sr) {
r = (r << 1) | (n >> (N - 1));
n = (n << 1) | carry;
// Branch-less version of:
// carry = 0;
// if (r >= d) r -= d, carry = 1;
const fixint_t s = (fixint_t)(d - r - 1) >> (N - 1);
carry = s & 1;
r -= d & s;
}
return r;
}
#ifdef COMPUTE_UDIV
static __inline fixint_t __divXi3(fixint_t a, fixint_t b) {
const int N = (int)(sizeof(fixint_t) * CHAR_BIT) - 1;
fixint_t s_a = a >> N; // s_a = a < 0 ? -1 : 0
fixint_t s_b = b >> N; // s_b = b < 0 ? -1 : 0
a = (a ^ s_a) - s_a; // negate if s_a == -1
b = (b ^ s_b) - s_b; // negate if s_b == -1
s_a ^= s_b; // sign of quotient
return (COMPUTE_UDIV(a, b) ^ s_a) - s_a; // negate if s_a == -1
}
#endif // COMPUTE_UDIV
#ifdef ASSIGN_UMOD
static __inline fixint_t __modXi3(fixint_t a, fixint_t b) {
const int N = (int)(sizeof(fixint_t) * CHAR_BIT) - 1;
fixint_t s = b >> N; // s = b < 0 ? -1 : 0
b = (b ^ s) - s; // negate if s == -1
s = a >> N; // s = a < 0 ? -1 : 0
a = (a ^ s) - s; // negate if s == -1
fixuint_t res;
ASSIGN_UMOD(res, a, b);
return (res ^ s) - s; // negate if s == -1
}
#endif // ASSIGN_UMOD