Linux-2.6.12-rc2
[linux-2.6.git] / arch / arm26 / lib / udivdi3.c
1 /* More subroutines needed by GCC output code on some machines.  */
2 /* Compile this one with gcc.  */
3 /* Copyright (C) 1989, 92-98, 1999 Free Software Foundation, Inc.
4
5 This file is part of GNU CC.
6
7 GNU CC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
10 any later version.
11
12 GNU CC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING.  If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA.  */
21
22 /* As a special exception, if you link this library with other files,
23    some of which are compiled with GCC, to produce an executable,
24    this library does not by itself cause the resulting executable
25    to be covered by the GNU General Public License.
26    This exception does not however invalidate any other reasons why
27    the executable file might be covered by the GNU General Public License.
28  */
29 /* support functions required by the kernel. based on code from gcc-2.95.3 */
30 /* I Molton     29/07/01 */
31
32 #include "gcclib.h"
33 #include "longlong.h"
34
35 static const UQItype __clz_tab[] =
36 {
37   0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
38   6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
39   7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
40   7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
41   8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
42   8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
43   8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
44   8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
45 };
46
47 UDItype
48 __udivmoddi4 (UDItype n, UDItype d, UDItype *rp)
49 {
50   DIunion ww;
51   DIunion nn, dd;
52   DIunion rr;
53   USItype d0, d1, n0, n1, n2;
54   USItype q0, q1;
55   USItype b, bm;
56
57   nn.ll = n;
58   dd.ll = d;
59
60   d0 = dd.s.low;
61   d1 = dd.s.high;
62   n0 = nn.s.low;
63   n1 = nn.s.high;
64
65   if (d1 == 0)
66     {
67       if (d0 > n1)
68         {
69           /* 0q = nn / 0D */
70
71           count_leading_zeros (bm, d0);
72
73           if (bm != 0)
74             {
75               /* Normalize, i.e. make the most significant bit of the
76                  denominator set.  */
77
78               d0 = d0 << bm;
79               n1 = (n1 << bm) | (n0 >> (SI_TYPE_SIZE - bm));
80               n0 = n0 << bm;
81             }
82
83           udiv_qrnnd (q0, n0, n1, n0, d0);
84           q1 = 0;
85
86           /* Remainder in n0 >> bm.  */
87         }
88       else
89         {
90           /* qq = NN / 0d */
91
92           if (d0 == 0)
93             d0 = 1 / d0;        /* Divide intentionally by zero.  */
94
95           count_leading_zeros (bm, d0);
96
97           if (bm == 0)
98             {
99               /* From (n1 >= d0) /\ (the most significant bit of d0 is set),
100                  conclude (the most significant bit of n1 is set) /\ (the
101                  leading quotient digit q1 = 1).
102
103                  This special case is necessary, not an optimization.
104                  (Shifts counts of SI_TYPE_SIZE are undefined.)  */
105
106               n1 -= d0;
107               q1 = 1;
108             }
109           else
110             {
111               /* Normalize.  */
112
113               b = SI_TYPE_SIZE - bm;
114
115               d0 = d0 << bm;
116               n2 = n1 >> b;
117               n1 = (n1 << bm) | (n0 >> b);
118               n0 = n0 << bm;
119
120               udiv_qrnnd (q1, n1, n2, n1, d0);
121             }
122
123           /* n1 != d0...  */
124
125           udiv_qrnnd (q0, n0, n1, n0, d0);
126
127           /* Remainder in n0 >> bm.  */
128         }
129
130       if (rp != 0)
131         {
132           rr.s.low = n0 >> bm;
133           rr.s.high = 0;
134           *rp = rr.ll;
135         }
136     }
137   else
138     {
139       if (d1 > n1)
140         {
141           /* 00 = nn / DD */
142
143           q0 = 0;
144           q1 = 0;
145
146           /* Remainder in n1n0.  */
147           if (rp != 0)
148             {
149               rr.s.low = n0;
150               rr.s.high = n1;
151               *rp = rr.ll;
152             }
153         }
154       else
155         {
156           /* 0q = NN / dd */
157
158           count_leading_zeros (bm, d1);
159           if (bm == 0)
160             {
161               /* From (n1 >= d1) /\ (the most significant bit of d1 is set),
162                  conclude (the most significant bit of n1 is set) /\ (the
163                  quotient digit q0 = 0 or 1).
164
165                  This special case is necessary, not an optimization.  */
166
167               /* The condition on the next line takes advantage of that
168                  n1 >= d1 (true due to program flow).  */
169               if (n1 > d1 || n0 >= d0)
170                 {
171                   q0 = 1;
172                   sub_ddmmss (n1, n0, n1, n0, d1, d0);
173                 }
174               else
175                 q0 = 0;
176
177               q1 = 0;
178
179               if (rp != 0)
180                 {
181                   rr.s.low = n0;
182                   rr.s.high = n1;
183                   *rp = rr.ll;
184                 }
185             }
186           else
187             {
188               USItype m1, m0;
189               /* Normalize.  */
190
191               b = SI_TYPE_SIZE - bm;
192
193               d1 = (d1 << bm) | (d0 >> b);
194               d0 = d0 << bm;
195               n2 = n1 >> b;
196               n1 = (n1 << bm) | (n0 >> b);
197               n0 = n0 << bm;
198
199               udiv_qrnnd (q0, n1, n2, n1, d1);
200               umul_ppmm (m1, m0, q0, d0);
201
202               if (m1 > n1 || (m1 == n1 && m0 > n0))
203                 {
204                   q0--;
205                   sub_ddmmss (m1, m0, m1, m0, d1, d0);
206                 }
207
208               q1 = 0;
209
210               /* Remainder in (n1n0 - m1m0) >> bm.  */
211               if (rp != 0)
212                 {
213                   sub_ddmmss (n1, n0, n1, n0, m1, m0);
214                   rr.s.low = (n1 << b) | (n0 >> bm);
215                   rr.s.high = n1 >> bm;
216                   *rp = rr.ll;
217                 }
218             }
219         }
220     }
221
222   ww.s.low = q0;
223   ww.s.high = q1;
224   return ww.ll;
225 }
226
227 UDItype
228 __udivdi3 (UDItype n, UDItype d)
229 {
230   return __udivmoddi4 (n, d, (UDItype *) 0);
231 }
232
233 UDItype
234 __umoddi3 (UDItype u, UDItype v)
235 {
236   UDItype w;
237
238   (void) __udivmoddi4 (u ,v, &w);
239
240   return w;
241 }
242