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