| 1 |
//===-- udivmoddi4.c - Implement __udivmoddi4 -----------------------------===// |
| 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 |
// This file implements __udivmoddi4 for the compiler_rt library. |
| 10 |
// |
| 11 |
//===----------------------------------------------------------------------===// |
| 12 |
|
| 13 |
#include "int_lib.h" |
| 14 |
|
| 15 |
// Effects: if rem != 0, *rem = a % b |
| 16 |
// Returns: a / b |
| 17 |
|
| 18 |
// Translated from Figure 3-40 of The PowerPC Compiler Writer's Guide |
| 19 |
|
| 20 |
#if defined(_MSC_VER) && !defined(__clang__) |
| 21 |
// MSVC throws a warning about mod 0 here, disable it for builds that |
| 22 |
// warn-as-error |
| 23 |
#pragma warning(push) |
| 24 |
#pragma warning(disable : 4723 4724) |
| 25 |
#endif |
| 26 |
|
| 27 |
COMPILER_RT_ABI du_int __udivmoddi4(du_int a, du_int b, du_int *rem) { |
| 28 |
const unsigned n_uword_bits = sizeof(su_int) * CHAR_BIT; |
| 29 |
const unsigned n_udword_bits = sizeof(du_int) * CHAR_BIT; |
| 30 |
udwords n; |
| 31 |
n.all = a; |
| 32 |
udwords d; |
| 33 |
d.all = b; |
| 34 |
udwords q; |
| 35 |
udwords r; |
| 36 |
unsigned sr; |
| 37 |
// special cases, X is unknown, K != 0 |
| 38 |
if (n.s.high == 0) { |
| 39 |
if (d.s.high == 0) { |
| 40 |
// 0 X |
| 41 |
// --- |
| 42 |
// 0 X |
| 43 |
if (rem) |
| 44 |
*rem = n.s.low % d.s.low; |
| 45 |
return n.s.low / d.s.low; |
| 46 |
} |
| 47 |
// 0 X |
| 48 |
// --- |
| 49 |
// K X |
| 50 |
if (rem) |
| 51 |
*rem = n.s.low; |
| 52 |
return 0; |
| 53 |
} |
| 54 |
// n.s.high != 0 |
| 55 |
if (d.s.low == 0) { |
| 56 |
if (d.s.high == 0) { |
| 57 |
// K X |
| 58 |
// --- |
| 59 |
// 0 0 |
| 60 |
if (rem) |
| 61 |
*rem = n.s.high % d.s.low; |
| 62 |
return n.s.high / d.s.low; |
| 63 |
} |
| 64 |
// d.s.high != 0 |
| 65 |
if (n.s.low == 0) { |
| 66 |
// K 0 |
| 67 |
// --- |
| 68 |
// K 0 |
| 69 |
if (rem) { |
| 70 |
r.s.high = n.s.high % d.s.high; |
| 71 |
r.s.low = 0; |
| 72 |
*rem = r.all; |
| 73 |
} |
| 74 |
return n.s.high / d.s.high; |
| 75 |
} |
| 76 |
// K K |
| 77 |
// --- |
| 78 |
// K 0 |
| 79 |
if ((d.s.high & (d.s.high - 1)) == 0) /* if d is a power of 2 */ { |
| 80 |
if (rem) { |
| 81 |
r.s.low = n.s.low; |
| 82 |
r.s.high = n.s.high & (d.s.high - 1); |
| 83 |
*rem = r.all; |
| 84 |
} |
| 85 |
return n.s.high >> ctzsi(d.s.high); |
| 86 |
} |
| 87 |
// K K |
| 88 |
// --- |
| 89 |
// K 0 |
| 90 |
sr = clzsi(d.s.high) - clzsi(n.s.high); |
| 91 |
// 0 <= sr <= n_uword_bits - 2 or sr large |
| 92 |
if (sr > n_uword_bits - 2) { |
| 93 |
if (rem) |
| 94 |
*rem = n.all; |
| 95 |
return 0; |
| 96 |
} |
| 97 |
++sr; |
| 98 |
// 1 <= sr <= n_uword_bits - 1 |
| 99 |
// q.all = n.all << (n_udword_bits - sr); |
| 100 |
q.s.low = 0; |
| 101 |
q.s.high = n.s.low << (n_uword_bits - sr); |
| 102 |
// r.all = n.all >> sr; |
| 103 |
r.s.high = n.s.high >> sr; |
| 104 |
r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr); |
| 105 |
} else /* d.s.low != 0 */ { |
| 106 |
if (d.s.high == 0) { |
| 107 |
// K X |
| 108 |
// --- |
| 109 |
// 0 K |
| 110 |
if ((d.s.low & (d.s.low - 1)) == 0) /* if d is a power of 2 */ { |
| 111 |
if (rem) |
| 112 |
*rem = n.s.low & (d.s.low - 1); |
| 113 |
if (d.s.low == 1) |
| 114 |
return n.all; |
| 115 |
sr = ctzsi(d.s.low); |
| 116 |
q.s.high = n.s.high >> sr; |
| 117 |
q.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr); |
| 118 |
return q.all; |
| 119 |
} |
| 120 |
// K X |
| 121 |
// --- |
| 122 |
// 0 K |
| 123 |
sr = 1 + n_uword_bits + clzsi(d.s.low) - clzsi(n.s.high); |
| 124 |
// 2 <= sr <= n_udword_bits - 1 |
| 125 |
// q.all = n.all << (n_udword_bits - sr); |
| 126 |
// r.all = n.all >> sr; |
| 127 |
if (sr == n_uword_bits) { |
| 128 |
q.s.low = 0; |
| 129 |
q.s.high = n.s.low; |
| 130 |
r.s.high = 0; |
| 131 |
r.s.low = n.s.high; |
| 132 |
} else if (sr < n_uword_bits) /* 2 <= sr <= n_uword_bits - 1 */ { |
| 133 |
q.s.low = 0; |
| 134 |
q.s.high = n.s.low << (n_uword_bits - sr); |
| 135 |
r.s.high = n.s.high >> sr; |
| 136 |
r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr); |
| 137 |
} else /* n_uword_bits + 1 <= sr <= n_udword_bits - 1 */ { |
| 138 |
q.s.low = n.s.low << (n_udword_bits - sr); |
| 139 |
q.s.high = (n.s.high << (n_udword_bits - sr)) | |
| 140 |
(n.s.low >> (sr - n_uword_bits)); |
| 141 |
r.s.high = 0; |
| 142 |
r.s.low = n.s.high >> (sr - n_uword_bits); |
| 143 |
} |
| 144 |
} else { |
| 145 |
// K X |
| 146 |
// --- |
| 147 |
// K K |
| 148 |
sr = clzsi(d.s.high) - clzsi(n.s.high); |
| 149 |
// 0 <= sr <= n_uword_bits - 1 or sr large |
| 150 |
if (sr > n_uword_bits - 1) { |
| 151 |
if (rem) |
| 152 |
*rem = n.all; |
| 153 |
return 0; |
| 154 |
} |
| 155 |
++sr; |
| 156 |
// 1 <= sr <= n_uword_bits |
| 157 |
// q.all = n.all << (n_udword_bits - sr); |
| 158 |
q.s.low = 0; |
| 159 |
if (sr == n_uword_bits) { |
| 160 |
q.s.high = n.s.low; |
| 161 |
r.s.high = 0; |
| 162 |
r.s.low = n.s.high; |
| 163 |
} else { |
| 164 |
q.s.high = n.s.low << (n_uword_bits - sr); |
| 165 |
r.s.high = n.s.high >> sr; |
| 166 |
r.s.low = (n.s.high << (n_uword_bits - sr)) | (n.s.low >> sr); |
| 167 |
} |
| 168 |
} |
| 169 |
} |
| 170 |
// Not a special case |
| 171 |
// q and r are initialized with: |
| 172 |
// q.all = n.all << (n_udword_bits - sr); |
| 173 |
// r.all = n.all >> sr; |
| 174 |
// 1 <= sr <= n_udword_bits - 1 |
| 175 |
su_int carry = 0; |
| 176 |
for (; sr > 0; --sr) { |
| 177 |
// r:q = ((r:q) << 1) | carry |
| 178 |
r.s.high = (r.s.high << 1) | (r.s.low >> (n_uword_bits - 1)); |
| 179 |
r.s.low = (r.s.low << 1) | (q.s.high >> (n_uword_bits - 1)); |
| 180 |
q.s.high = (q.s.high << 1) | (q.s.low >> (n_uword_bits - 1)); |
| 181 |
q.s.low = (q.s.low << 1) | carry; |
| 182 |
// carry = 0; |
| 183 |
// if (r.all >= d.all) |
| 184 |
// { |
| 185 |
// r.all -= d.all; |
| 186 |
// carry = 1; |
| 187 |
// } |
| 188 |
const di_int s = (di_int)(d.all - r.all - 1) >> (n_udword_bits - 1); |
| 189 |
carry = s & 1; |
| 190 |
r.all -= d.all & s; |
| 191 |
} |
| 192 |
q.all = (q.all << 1) | carry; |
| 193 |
if (rem) |
| 194 |
*rem = r.all; |
| 195 |
return q.all; |
| 196 |
} |
| 197 |
|
| 198 |
#if defined(_MSC_VER) && !defined(__clang__) |
| 199 |
#pragma warning(pop) |
| 200 |
#endif |