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		static JSInt64 ll_zero = JSLL_INIT( 0x00000000,0x00000000 );
44		static JSInt64 ll_maxint = JSLL_INIT( 0x7fffffff, 0xffffffff );
45		static JSInt64 ll_minint = JSLL_INIT( 0x80000000, 0x00000000 );
46
47		#ifdef HAVE_WATCOM_BUG_2
48		JSInt64 __pascal __loadds __export
49		JSLL_Zero(void) { return ll_zero; }
50		JSInt64 __pascal __loadds __export
51		JSLL_MaxInt(void) { return ll_maxint; }
52		JSInt64 __pascal __loadds __export
53		JSLL_MinInt(void) { return ll_minint; }
54		#else
55	0	JS_PUBLIC_API(JSInt64) JSLL_Zero(void) { return ll_zero; }
56	0	JS_PUBLIC_API(JSInt64) JSLL_MaxInt(void) { return ll_maxint; }
57	0	JS_PUBLIC_API(JSInt64) JSLL_MinInt(void) { return ll_minint; }
58		#endif
59
60		#ifndef JS_HAVE_LONG_LONG
61		/*
62		** Divide 64-bit a by 32-bit b, which must be normalized so its high bit is 1.
63		*/
64		static void norm_udivmod32(JSUint32 *qp, JSUint32 *rp, JSUint64 a, JSUint32 b)
65		{
66		JSUint32 d1, d0, q1, q0;
67		JSUint32 r1, r0, m;
68
69		d1 = jshi16(b);
70		d0 = jslo16(b);
71		r1 = a.hi % d1;
72		q1 = a.hi / d1;
73		m = q1 * d0;
74		r1 = (r1 << 16) | jshi16(a.lo);
75		if (r1 < m) {
76		q1--, r1 += b;
77		if (r1 >= b /* i.e., we didn't get a carry when adding to r1 */
78		&& r1 < m) {
79		q1--, r1 += b;
80		}
81		}
82		r1 -= m;
83		r0 = r1 % d1;
84		q0 = r1 / d1;
85		m = q0 * d0;
86		r0 = (r0 << 16) | jslo16(a.lo);
87		if (r0 < m) {
88		q0--, r0 += b;
89		if (r0 >= b
90		&& r0 < m) {
91		q0--, r0 += b;
92		}
93		}
94		*qp = (q1 << 16) | q0;
95		*rp = r0 - m;
96		}
97
98		static JSUint32 CountLeadingZeros(JSUint32 a)
99		{
100		JSUint32 t;
101		JSUint32 r = 32;
102
103		if ((t = a >> 16) != 0)
104		r -= 16, a = t;
105		if ((t = a >> 8) != 0)
106		r -= 8, a = t;
107		if ((t = a >> 4) != 0)
108		r -= 4, a = t;
109		if ((t = a >> 2) != 0)
110		r -= 2, a = t;
111		if ((t = a >> 1) != 0)
112		r -= 1, a = t;
113		if (a & 1)
114		r--;
115		return r;
116		}
117
118		JS_PUBLIC_API(void) jsll_udivmod(JSUint64 *qp, JSUint64 *rp, JSUint64 a, JSUint64 b)
119		{
120		JSUint32 n0, n1, n2;
121		JSUint32 q0, q1;
122		JSUint32 rsh, lsh;
123
124		n0 = a.lo;
125		n1 = a.hi;
126
127		if (b.hi == 0) {
128		if (b.lo > n1) {
129		/* (0 q0) = (n1 n0) / (0 D0) */
130
131		lsh = CountLeadingZeros(b.lo);
132
133		if (lsh) {
134		/*
135		* Normalize, i.e. make the most significant bit of the
136		* denominator be set.
137		*/
138		b.lo = b.lo << lsh;
139		n1 = (n1 << lsh) | (n0 >> (32 - lsh));
140		n0 = n0 << lsh;
141		}
142
143		a.lo = n0, a.hi = n1;
144		norm_udivmod32(&q0, &n0, a, b.lo);
145		q1 = 0;
146
147		/* remainder is in n0 >> lsh */
148		} else {
149		/* (q1 q0) = (n1 n0) / (0 d0) */
150
151		if (b.lo == 0) /* user wants to divide by zero! */
152		b.lo = 1 / b.lo; /* so go ahead and crash */
153
154		lsh = CountLeadingZeros(b.lo);
155
156		if (lsh == 0) {
157		/*
158		* From (n1 >= b.lo)
159		*   && (the most significant bit of b.lo is set),
160		* conclude that
161		* (the most significant bit of n1 is set)
162		*   && (the leading quotient digit q1 = 1).
163		*
164		* This special case is necessary, not an optimization
165		* (Shifts counts of 32 are undefined).
166		*/
167		n1 -= b.lo;
168		q1 = 1;
169		} else {
170		/*
171		* Normalize.
172		*/
173		rsh = 32 - lsh;
174
175		b.lo = b.lo << lsh;
176		n2 = n1 >> rsh;
177		n1 = (n1 << lsh) | (n0 >> rsh);
178		n0 = n0 << lsh;
179
180		a.lo = n1, a.hi = n2;
181		norm_udivmod32(&q1, &n1, a, b.lo);
182		}
183
184		/* n1 != b.lo... */
185
186		a.lo = n0, a.hi = n1;
187		norm_udivmod32(&q0, &n0, a, b.lo);
188
189		/* remainder in n0 >> lsh */
190		}
191
192		if (rp) {
193		rp->lo = n0 >> lsh;
194		rp->hi = 0;
195		}
196		} else {
197		if (b.hi > n1) {
198		/* (0 0) = (n1 n0) / (D1 d0) */
199
200		q0 = 0;
201		q1 = 0;
202
203		/* remainder in (n1 n0) */
204		if (rp) {
205		rp->lo = n0;
206		rp->hi = n1;
207		}
208		} else {
209		/* (0 q0) = (n1 n0) / (d1 d0) */
210
211		lsh = CountLeadingZeros(b.hi);
212		if (lsh == 0) {
213		/*
214		* From (n1 >= b.hi)
215		*   && (the most significant bit of b.hi is set),
216		* conclude that
217		*      (the most significant bit of n1 is set)
218		*   && (the quotient digit q0 = 0 or 1).
219		*
220		* This special case is necessary, not an optimization.
221		*/
222
223		/*
224		* The condition on the next line takes advantage of that
225		* n1 >= b.hi (true due to control flow).
226		*/
227		if (n1 > b.hi || n0 >= b.lo) {
228		q0 = 1;
229		a.lo = n0, a.hi = n1;
230		JSLL_SUB(a, a, b);
231		} else {
232		q0 = 0;
233		}
234		q1 = 0;
235
236		if (rp) {
237		rp->lo = n0;
238		rp->hi = n1;
239		}
240		} else {
241		JSInt64 m;
242
243		/*
244		* Normalize.
245		*/
246		rsh = 32 - lsh;
247
248		b.hi = (b.hi << lsh) | (b.lo >> rsh);
249		b.lo = b.lo << lsh;
250		n2 = n1 >> rsh;
251		n1 = (n1 << lsh) | (n0 >> rsh);
252		n0 = n0 << lsh;
253
254		a.lo = n1, a.hi = n2;
255		norm_udivmod32(&q0, &n1, a, b.hi);
256		JSLL_MUL32(m, q0, b.lo);
257
258		if ((m.hi > n1) || ((m.hi == n1) && (m.lo > n0))) {
259		q0--;
260		JSLL_SUB(m, m, b);
261		}
262
263		q1 = 0;
264
265		/* Remainder is ((n1 n0) - (m1 m0)) >> lsh */
266		if (rp) {
267		a.lo = n0, a.hi = n1;
268		JSLL_SUB(a, a, m);
269		rp->lo = (a.hi << rsh) | (a.lo >> lsh);
270		rp->hi = a.hi >> lsh;
271		}
272		}
273		}
274		}
275
276		if (qp) {
277		qp->lo = q0;
278		qp->hi = q1;
279		}
280		}