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
201