1 |
/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ |
2 |
/* ***** BEGIN LICENSE BLOCK ***** |
3 |
* Version: MPL 1.1/GPL 2.0/LGPL 2.1 |
4 |
* |
5 |
* The contents of this file are subject to the Mozilla Public License Version |
6 |
* 1.1 (the "License"); you may not use this file except in compliance with |
7 |
* the License. You may obtain a copy of the License at |
8 |
* http://www.mozilla.org/MPL/ |
9 |
* |
10 |
* Software distributed under the License is distributed on an "AS IS" basis, |
11 |
* WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License |
12 |
* for the specific language governing rights and limitations under the |
13 |
* License. |
14 |
* |
15 |
* The Original Code is Mozilla Communicator client code, released |
16 |
* March 31, 1998. |
17 |
* |
18 |
* The Initial Developer of the Original Code is |
19 |
* Netscape Communications Corporation. |
20 |
* Portions created by the Initial Developer are Copyright (C) 1998 |
21 |
* the Initial Developer. All Rights Reserved. |
22 |
* |
23 |
* Contributor(s): |
24 |
* |
25 |
* Alternatively, the contents of this file may be used under the terms of |
26 |
* either of the GNU General Public License Version 2 or later (the "GPL"), |
27 |
* or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"), |
28 |
* in which case the provisions of the GPL or the LGPL are applicable instead |
29 |
* of those above. If you wish to allow use of your version of this file only |
30 |
* under the terms of either the GPL or the LGPL, and not to allow others to |
31 |
* use your version of this file under the terms of the MPL, indicate your |
32 |
* decision by deleting the provisions above and replace them with the notice |
33 |
* and other provisions required by the GPL or the LGPL. If you do not delete |
34 |
* the provisions above, a recipient may use your version of this file under |
35 |
* the terms of any one of the MPL, the GPL or the LGPL. |
36 |
* |
37 |
* ***** END LICENSE BLOCK ***** */ |
38 |
|
39 |
#include "jsstddef.h" |
40 |
#include "jstypes.h" |
41 |
#include "jslong.h" |
42 |
|
43 |
#ifndef JS_HAVE_LONG_LONG |
44 |
/* |
45 |
** Divide 64-bit a by 32-bit b, which must be normalized so its high bit is 1. |
46 |
*/ |
47 |
static void norm_udivmod32(JSUint32 *qp, JSUint32 *rp, JSUint64 a, JSUint32 b) |
48 |
{ |
49 |
JSUint32 d1, d0, q1, q0; |
50 |
JSUint32 r1, r0, m; |
51 |
|
52 |
d1 = jshi16(b); |
53 |
d0 = jslo16(b); |
54 |
r1 = a.hi % d1; |
55 |
q1 = a.hi / d1; |
56 |
m = q1 * d0; |
57 |
r1 = (r1 << 16) | jshi16(a.lo); |
58 |
if (r1 < m) { |
59 |
q1--, r1 += b; |
60 |
if (r1 >= b /* i.e., we didn't get a carry when adding to r1 */ |
61 |
&& r1 < m) { |
62 |
q1--, r1 += b; |
63 |
} |
64 |
} |
65 |
r1 -= m; |
66 |
r0 = r1 % d1; |
67 |
q0 = r1 / d1; |
68 |
m = q0 * d0; |
69 |
r0 = (r0 << 16) | jslo16(a.lo); |
70 |
if (r0 < m) { |
71 |
q0--, r0 += b; |
72 |
if (r0 >= b |
73 |
&& r0 < m) { |
74 |
q0--, r0 += b; |
75 |
} |
76 |
} |
77 |
*qp = (q1 << 16) | q0; |
78 |
*rp = r0 - m; |
79 |
} |
80 |
|
81 |
static JSUint32 CountLeadingZeros(JSUint32 a) |
82 |
{ |
83 |
JSUint32 t; |
84 |
JSUint32 r = 32; |
85 |
|
86 |
if ((t = a >> 16) != 0) |
87 |
r -= 16, a = t; |
88 |
if ((t = a >> 8) != 0) |
89 |
r -= 8, a = t; |
90 |
if ((t = a >> 4) != 0) |
91 |
r -= 4, a = t; |
92 |
if ((t = a >> 2) != 0) |
93 |
r -= 2, a = t; |
94 |
if ((t = a >> 1) != 0) |
95 |
r -= 1, a = t; |
96 |
if (a & 1) |
97 |
r--; |
98 |
return r; |
99 |
} |
100 |
|
101 |
JS_PUBLIC_API(void) jsll_udivmod(JSUint64 *qp, JSUint64 *rp, JSUint64 a, JSUint64 b) |
102 |
{ |
103 |
JSUint32 n0, n1, n2; |
104 |
JSUint32 q0, q1; |
105 |
JSUint32 rsh, lsh; |
106 |
|
107 |
n0 = a.lo; |
108 |
n1 = a.hi; |
109 |
|
110 |
if (b.hi == 0) { |
111 |
if (b.lo > n1) { |
112 |
/* (0 q0) = (n1 n0) / (0 D0) */ |
113 |
|
114 |
lsh = CountLeadingZeros(b.lo); |
115 |
|
116 |
if (lsh) { |
117 |
/* |
118 |
* Normalize, i.e. make the most significant bit of the |
119 |
* denominator be set. |
120 |
*/ |
121 |
b.lo = b.lo << lsh; |
122 |
n1 = (n1 << lsh) | (n0 >> (32 - lsh)); |
123 |
n0 = n0 << lsh; |
124 |
} |
125 |
|
126 |
a.lo = n0, a.hi = n1; |
127 |
norm_udivmod32(&q0, &n0, a, b.lo); |
128 |
q1 = 0; |
129 |
|
130 |
/* remainder is in n0 >> lsh */ |
131 |
} else { |
132 |
/* (q1 q0) = (n1 n0) / (0 d0) */ |
133 |
|
134 |
if (b.lo == 0) /* user wants to divide by zero! */ |
135 |
b.lo = 1 / b.lo; /* so go ahead and crash */ |
136 |
|
137 |
lsh = CountLeadingZeros(b.lo); |
138 |
|
139 |
if (lsh == 0) { |
140 |
/* |
141 |
* From (n1 >= b.lo) |
142 |
* && (the most significant bit of b.lo is set), |
143 |
* conclude that |
144 |
* (the most significant bit of n1 is set) |
145 |
* && (the leading quotient digit q1 = 1). |
146 |
* |
147 |
* This special case is necessary, not an optimization |
148 |
* (Shifts counts of 32 are undefined). |
149 |
*/ |
150 |
n1 -= b.lo; |
151 |
q1 = 1; |
152 |
} else { |
153 |
/* |
154 |
* Normalize. |
155 |
*/ |
156 |
rsh = 32 - lsh; |
157 |
|
158 |
b.lo = b.lo << lsh; |
159 |
n2 = n1 >> rsh; |
160 |
n1 = (n1 << lsh) | (n0 >> rsh); |
161 |
n0 = n0 << lsh; |
162 |
|
163 |
a.lo = n1, a.hi = n2; |
164 |
norm_udivmod32(&q1, &n1, a, b.lo); |
165 |
} |
166 |
|
167 |
/* n1 != b.lo... */ |
168 |
|
169 |
a.lo = n0, a.hi = n1; |
170 |
norm_udivmod32(&q0, &n0, a, b.lo); |
171 |
|
172 |
/* remainder in n0 >> lsh */ |
173 |
} |
174 |
|
175 |
if (rp) { |
176 |
rp->lo = n0 >> lsh; |
177 |
rp->hi = 0; |
178 |
} |
179 |
} else { |
180 |
if (b.hi > n1) { |
181 |
/* (0 0) = (n1 n0) / (D1 d0) */ |
182 |
|
183 |
q0 = 0; |
184 |
q1 = 0; |
185 |
|
186 |
/* remainder in (n1 n0) */ |
187 |
if (rp) { |
188 |
rp->lo = n0; |
189 |
rp->hi = n1; |
190 |
} |
191 |
} else { |
192 |
/* (0 q0) = (n1 n0) / (d1 d0) */ |
193 |
|
194 |
lsh = CountLeadingZeros(b.hi); |
195 |
if (lsh == 0) { |
196 |
/* |
197 |
* From (n1 >= b.hi) |
198 |
* && (the most significant bit of b.hi is set), |
199 |
* conclude that |
200 |
* (the most significant bit of n1 is set) |
201 |
* && (the quotient digit q0 = 0 or 1). |
202 |
* |
203 |
* This special case is necessary, not an optimization. |
204 |
*/ |
205 |
|
206 |
/* |
207 |
* The condition on the next line takes advantage of that |
208 |
* n1 >= b.hi (true due to control flow). |
209 |
*/ |
210 |
if (n1 > b.hi || n0 >= b.lo) { |
211 |
q0 = 1; |
212 |
a.lo = n0, a.hi = n1; |
213 |
JSLL_SUB(a, a, b); |
214 |
} else { |
215 |
q0 = 0; |
216 |
} |
217 |
q1 = 0; |
218 |
|
219 |
if (rp) { |
220 |
rp->lo = n0; |
221 |
rp->hi = n1; |
222 |
} |
223 |
} else { |
224 |
JSInt64 m; |
225 |
|
226 |
/* |
227 |
* Normalize. |
228 |
*/ |
229 |
rsh = 32 - lsh; |
230 |
|
231 |
b.hi = (b.hi << lsh) | (b.lo >> rsh); |
232 |
b.lo = b.lo << lsh; |
233 |
n2 = n1 >> rsh; |
234 |
n1 = (n1 << lsh) | (n0 >> rsh); |
235 |
n0 = n0 << lsh; |
236 |
|
237 |
a.lo = n1, a.hi = n2; |
238 |
norm_udivmod32(&q0, &n1, a, b.hi); |
239 |
JSLL_MUL32(m, q0, b.lo); |
240 |
|
241 |
if ((m.hi > n1) || ((m.hi == n1) && (m.lo > n0))) { |
242 |
q0--; |
243 |
JSLL_SUB(m, m, b); |
244 |
} |
245 |
|
246 |
q1 = 0; |
247 |
|
248 |
/* Remainder is ((n1 n0) - (m1 m0)) >> lsh */ |
249 |
if (rp) { |
250 |
a.lo = n0, a.hi = n1; |
251 |
JSLL_SUB(a, a, m); |
252 |
rp->lo = (a.hi << rsh) | (a.lo >> lsh); |
253 |
rp->hi = a.hi >> lsh; |
254 |
} |
255 |
} |
256 |
} |
257 |
} |
258 |
|
259 |
if (qp) { |
260 |
qp->lo = q0; |
261 |
qp->hi = q1; |
262 |
} |
263 |
} |
264 |
#endif /* !JS_HAVE_LONG_LONG */ |