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
27COMPILER_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
201

source code of compiler-rt/lib/builtins/udivmoddi4.c