Line data Source code
1 : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 : /* This Source Code Form is subject to the terms of the Mozilla Public
3 : * License, v. 2.0. If a copy of the MPL was not distributed with this
4 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5 :
6 : #include "prlong.h"
7 :
8 : static PRInt64 ll_zero = PR_INT64(0x0000000000000000);
9 : static PRInt64 ll_maxint = PR_INT64(0x7fffffffffffffff);
10 : static PRInt64 ll_minint = PR_INT64(0x8000000000000000);
11 : static PRUint64 ll_maxuint = PR_UINT64(0xffffffffffffffff);
12 :
13 0 : PR_IMPLEMENT(PRInt64) LL_Zero(void) { return ll_zero; }
14 0 : PR_IMPLEMENT(PRInt64) LL_MaxInt(void) { return ll_maxint; }
15 0 : PR_IMPLEMENT(PRInt64) LL_MinInt(void) { return ll_minint; }
16 0 : PR_IMPLEMENT(PRUint64) LL_MaxUint(void) { return ll_maxuint; }
17 :
18 : #ifndef HAVE_LONG_LONG
19 : /*
20 : ** Divide 64-bit a by 32-bit b, which must be normalized so its high bit is 1.
21 : */
22 : static void norm_udivmod32(PRUint32 *qp, PRUint32 *rp, PRUint64 a, PRUint32 b)
23 : {
24 : PRUint32 d1, d0, q1, q0;
25 : PRUint32 r1, r0, m;
26 :
27 : d1 = _hi16(b);
28 : d0 = _lo16(b);
29 : r1 = a.hi % d1;
30 : q1 = a.hi / d1;
31 : m = q1 * d0;
32 : r1 = (r1 << 16) | _hi16(a.lo);
33 : if (r1 < m) {
34 : q1--, r1 += b;
35 : if (r1 >= b /* i.e., we didn't get a carry when adding to r1 */
36 : && r1 < m) {
37 : q1--, r1 += b;
38 : }
39 : }
40 : r1 -= m;
41 : r0 = r1 % d1;
42 : q0 = r1 / d1;
43 : m = q0 * d0;
44 : r0 = (r0 << 16) | _lo16(a.lo);
45 : if (r0 < m) {
46 : q0--, r0 += b;
47 : if (r0 >= b
48 : && r0 < m) {
49 : q0--, r0 += b;
50 : }
51 : }
52 : *qp = (q1 << 16) | q0;
53 : *rp = r0 - m;
54 : }
55 :
56 : static PRUint32 CountLeadingZeros(PRUint32 a)
57 : {
58 : PRUint32 t;
59 : PRUint32 r = 32;
60 :
61 : if ((t = a >> 16) != 0)
62 : r -= 16, a = t;
63 : if ((t = a >> 8) != 0)
64 : r -= 8, a = t;
65 : if ((t = a >> 4) != 0)
66 : r -= 4, a = t;
67 : if ((t = a >> 2) != 0)
68 : r -= 2, a = t;
69 : if ((t = a >> 1) != 0)
70 : r -= 1, a = t;
71 : if (a & 1)
72 : r--;
73 : return r;
74 : }
75 :
76 : PR_IMPLEMENT(void) ll_udivmod(PRUint64 *qp, PRUint64 *rp, PRUint64 a, PRUint64 b)
77 : {
78 : PRUint32 n0, n1, n2;
79 : PRUint32 q0, q1;
80 : PRUint32 rsh, lsh;
81 :
82 : n0 = a.lo;
83 : n1 = a.hi;
84 :
85 : if (b.hi == 0) {
86 : if (b.lo > n1) {
87 : /* (0 q0) = (n1 n0) / (0 D0) */
88 :
89 : lsh = CountLeadingZeros(b.lo);
90 :
91 : if (lsh) {
92 : /*
93 : * Normalize, i.e. make the most significant bit of the
94 : * denominator be set.
95 : */
96 : b.lo = b.lo << lsh;
97 : n1 = (n1 << lsh) | (n0 >> (32 - lsh));
98 : n0 = n0 << lsh;
99 : }
100 :
101 : a.lo = n0, a.hi = n1;
102 : norm_udivmod32(&q0, &n0, a, b.lo);
103 : q1 = 0;
104 :
105 : /* remainder is in n0 >> lsh */
106 : } else {
107 : /* (q1 q0) = (n1 n0) / (0 d0) */
108 :
109 : if (b.lo == 0) /* user wants to divide by zero! */
110 : b.lo = 1 / b.lo; /* so go ahead and crash */
111 :
112 : lsh = CountLeadingZeros(b.lo);
113 :
114 : if (lsh == 0) {
115 : /*
116 : * From (n1 >= b.lo)
117 : * && (the most significant bit of b.lo is set),
118 : * conclude that
119 : * (the most significant bit of n1 is set)
120 : * && (the leading quotient digit q1 = 1).
121 : *
122 : * This special case is necessary, not an optimization
123 : * (Shifts counts of 32 are undefined).
124 : */
125 : n1 -= b.lo;
126 : q1 = 1;
127 : } else {
128 : /*
129 : * Normalize.
130 : */
131 : rsh = 32 - lsh;
132 :
133 : b.lo = b.lo << lsh;
134 : n2 = n1 >> rsh;
135 : n1 = (n1 << lsh) | (n0 >> rsh);
136 : n0 = n0 << lsh;
137 :
138 : a.lo = n1, a.hi = n2;
139 : norm_udivmod32(&q1, &n1, a, b.lo);
140 : }
141 :
142 : /* n1 != b.lo... */
143 :
144 : a.lo = n0, a.hi = n1;
145 : norm_udivmod32(&q0, &n0, a, b.lo);
146 :
147 : /* remainder in n0 >> lsh */
148 : }
149 :
150 : if (rp) {
151 : rp->lo = n0 >> lsh;
152 : rp->hi = 0;
153 : }
154 : } else {
155 : if (b.hi > n1) {
156 : /* (0 0) = (n1 n0) / (D1 d0) */
157 :
158 : q0 = 0;
159 : q1 = 0;
160 :
161 : /* remainder in (n1 n0) */
162 : if (rp) {
163 : rp->lo = n0;
164 : rp->hi = n1;
165 : }
166 : } else {
167 : /* (0 q0) = (n1 n0) / (d1 d0) */
168 :
169 : lsh = CountLeadingZeros(b.hi);
170 : if (lsh == 0) {
171 : /*
172 : * From (n1 >= b.hi)
173 : * && (the most significant bit of b.hi is set),
174 : * conclude that
175 : * (the most significant bit of n1 is set)
176 : * && (the quotient digit q0 = 0 or 1).
177 : *
178 : * This special case is necessary, not an optimization.
179 : */
180 :
181 : /*
182 : * The condition on the next line takes advantage of that
183 : * n1 >= b.hi (true due to control flow).
184 : */
185 : if (n1 > b.hi || n0 >= b.lo) {
186 : q0 = 1;
187 : a.lo = n0, a.hi = n1;
188 : LL_SUB(a, a, b);
189 : } else {
190 : q0 = 0;
191 : }
192 : q1 = 0;
193 :
194 : if (rp) {
195 : rp->lo = n0;
196 : rp->hi = n1;
197 : }
198 : } else {
199 : PRInt64 m;
200 :
201 : /*
202 : * Normalize.
203 : */
204 : rsh = 32 - lsh;
205 :
206 : b.hi = (b.hi << lsh) | (b.lo >> rsh);
207 : b.lo = b.lo << lsh;
208 : n2 = n1 >> rsh;
209 : n1 = (n1 << lsh) | (n0 >> rsh);
210 : n0 = n0 << lsh;
211 :
212 : a.lo = n1, a.hi = n2;
213 : norm_udivmod32(&q0, &n1, a, b.hi);
214 : LL_MUL32(m, q0, b.lo);
215 :
216 : if ((m.hi > n1) || ((m.hi == n1) && (m.lo > n0))) {
217 : q0--;
218 : LL_SUB(m, m, b);
219 : }
220 :
221 : q1 = 0;
222 :
223 : /* Remainder is ((n1 n0) - (m1 m0)) >> lsh */
224 : if (rp) {
225 : a.lo = n0, a.hi = n1;
226 : LL_SUB(a, a, m);
227 : rp->lo = (a.hi << rsh) | (a.lo >> lsh);
228 : rp->hi = a.hi >> lsh;
229 : }
230 : }
231 : }
232 : }
233 :
234 : if (qp) {
235 : qp->lo = q0;
236 : qp->hi = q1;
237 : }
238 : }
239 : #endif /* !HAVE_LONG_LONG */
|
