1 // SPDX-License-Identifier: GPL-2.0+
2 /*
3 * Copyright (C) 1989-2013 Free Software Foundation, Inc.
4 */
5
6 #include "libgcc2.h"
7
8 DWtype
__ashldi3(DWtype u,shift_count_type b)9 __ashldi3(DWtype u, shift_count_type b)
10 {
11 if (b == 0)
12 return u;
13
14 const DWunion uu = {.ll = u};
15 const shift_count_type bm = W_TYPE_SIZE - b;
16 DWunion w;
17
18 if (bm <= 0) {
19 w.s.low = 0;
20 w.s.high = (UWtype)uu.s.low << -bm;
21 } else {
22 const UWtype carries = (UWtype) uu.s.low >> bm;
23
24 w.s.low = (UWtype)uu.s.low << b;
25 w.s.high = ((UWtype)uu.s.high << b) | carries;
26 }
27
28 return w.ll;
29 }
30
31 DWtype
__ashrdi3(DWtype u,shift_count_type b)32 __ashrdi3(DWtype u, shift_count_type b)
33 {
34 if (b == 0)
35 return u;
36
37 const DWunion uu = {.ll = u};
38 const shift_count_type bm = W_TYPE_SIZE - b;
39 DWunion w;
40
41 if (bm <= 0) {
42 /* w.s.high = 1..1 or 0..0 */
43 w.s.high = uu.s.high >> (W_TYPE_SIZE - 1);
44 w.s.low = uu.s.high >> -bm;
45 } else {
46 const UWtype carries = (UWtype) uu.s.high << bm;
47
48 w.s.high = uu.s.high >> b;
49 w.s.low = ((UWtype)uu.s.low >> b) | carries;
50 }
51
52 return w.ll;
53 }
54
55 DWtype
__lshrdi3(DWtype u,shift_count_type b)56 __lshrdi3(DWtype u, shift_count_type b)
57 {
58 if (b == 0)
59 return u;
60
61 const DWunion uu = {.ll = u};
62 const shift_count_type bm = W_TYPE_SIZE - b;
63 DWunion w;
64
65 if (bm <= 0) {
66 w.s.high = 0;
67 w.s.low = (UWtype)uu.s.high >> -bm;
68 } else {
69 const UWtype carries = (UWtype)uu.s.high << bm;
70
71 w.s.high = (UWtype)uu.s.high >> b;
72 w.s.low = ((UWtype)uu.s.low >> b) | carries;
73 }
74
75 return w.ll;
76 }
77
78 unsigned long
udivmodsi4(unsigned long num,unsigned long den,int modwanted)79 udivmodsi4(unsigned long num, unsigned long den, int modwanted)
80 {
81 unsigned long bit = 1;
82 unsigned long res = 0;
83
84 while (den < num && bit && !(den & (1L<<31))) {
85 den <<= 1;
86 bit <<= 1;
87 }
88
89 while (bit) {
90 if (num >= den) {
91 num -= den;
92 res |= bit;
93 }
94 bit >>= 1;
95 den >>= 1;
96 }
97
98 if (modwanted)
99 return num;
100
101 return res;
102 }
103
104 long
__divsi3(long a,long b)105 __divsi3(long a, long b)
106 {
107 int neg = 0;
108 long res;
109
110 if (a < 0) {
111 a = -a;
112 neg = !neg;
113 }
114
115 if (b < 0) {
116 b = -b;
117 neg = !neg;
118 }
119
120 res = udivmodsi4(a, b, 0);
121
122 if (neg)
123 res = -res;
124
125 return res;
126 }
127
128 long
__modsi3(long a,long b)129 __modsi3(long a, long b)
130 {
131 int neg = 0;
132 long res;
133
134 if (a < 0) {
135 a = -a;
136 neg = 1;
137 }
138
139 if (b < 0)
140 b = -b;
141
142 res = udivmodsi4(a, b, 1);
143
144 if (neg)
145 res = -res;
146
147 return res;
148 }
149
150 long
__udivsi3(long a,long b)151 __udivsi3(long a, long b)
152 {
153 return udivmodsi4(a, b, 0);
154 }
155
156 long
__umodsi3(long a,long b)157 __umodsi3(long a, long b)
158 {
159 return udivmodsi4(a, b, 1);
160 }
161
162 UDWtype
__udivmoddi4(UDWtype n,UDWtype d,UDWtype * rp)163 __udivmoddi4(UDWtype n, UDWtype d, UDWtype *rp)
164 {
165 UDWtype q = 0, r = n, y = d;
166 UWtype lz1, lz2, i, k;
167
168 /*
169 * Implements align divisor shift dividend method. This algorithm
170 * aligns the divisor under the dividend and then perform number of
171 * test-subtract iterations which shift the dividend left. Number of
172 * iterations is k + 1 where k is the number of bit positions the
173 * divisor must be shifted left to align it under the dividend.
174 * quotient bits can be saved in the rightmost positions of the
175 * dividend as it shifts left on each test-subtract iteration.
176 */
177
178 if (y <= r) {
179 lz1 = __builtin_clzll(d);
180 lz2 = __builtin_clzll(n);
181
182 k = lz1 - lz2;
183 y = (y << k);
184
185 /*
186 * Dividend can exceed 2 ^ (width - 1) - 1 but still be less
187 * than the aligned divisor. Normal iteration can drops the
188 * high order bit of the dividend. Therefore, first
189 * test-subtract iteration is a special case, saving its
190 * quotient bit in a separate location and not shifting
191 * the dividend.
192 */
193
194 if (r >= y) {
195 r = r - y;
196 q = (1ULL << k);
197 }
198
199 if (k > 0) {
200 y = y >> 1;
201
202 /*
203 * k additional iterations where k regular test
204 * subtract shift dividend iterations are done.
205 */
206 i = k;
207 do {
208 if (r >= y)
209 r = ((r - y) << 1) + 1;
210 else
211 r = (r << 1);
212 i = i - 1;
213 } while (i != 0);
214
215 /*
216 * First quotient bit is combined with the quotient
217 * bits resulting from the k regular iterations.
218 */
219 q = q + r;
220 r = r >> k;
221 q = q - (r << k);
222 }
223 }
224
225 if (rp)
226 *rp = r;
227
228 return q;
229 }
230
231 UDWtype
__udivdi3(UDWtype n,UDWtype d)232 __udivdi3(UDWtype n, UDWtype d)
233 {
234 return __udivmoddi4(n, d, (UDWtype *)0);
235 }
236