trunk/js/jslong.cpp

/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* ***** BEGIN LICENSE BLOCK *****
 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
 *
 * The contents of this file are subject to the Mozilla Public License Version
 * 1.1 (the "License"); you may not use this file except in compliance with
 * the License. You may obtain a copy of the License at
 * http://www.mozilla.org/MPL/
 *
 * Software distributed under the License is distributed on an "AS IS" basis,
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 * for the specific language governing rights and limitations under the
 * License.
 *
 * The Original Code is Mozilla Communicator client code, released
 * March 31, 1998.
 *
 * The Initial Developer of the Original Code is
 * Netscape Communications Corporation.
 * Portions created by the Initial Developer are Copyright (C) 1998
 * the Initial Developer. All Rights Reserved.
 *
 * Contributor(s):
 *
 * Alternatively, the contents of this file may be used under the terms of
 * either of the GNU General Public License Version 2 or later (the "GPL"),
 * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
 * in which case the provisions of the GPL or the LGPL are applicable instead
 * of those above. If you wish to allow use of your version of this file only
 * under the terms of either the GPL or the LGPL, and not to allow others to
 * use your version of this file under the terms of the MPL, indicate your
 * decision by deleting the provisions above and replace them with the notice
 * and other provisions required by the GPL or the LGPL. If you do not delete
 * the provisions above, a recipient may use your version of this file under
 * the terms of any one of the MPL, the GPL or the LGPL.
 *
 * ***** END LICENSE BLOCK ***** */

#include "jsstddef.h"
#include "jstypes.h"
#include "jslong.h"

#ifndef JS_HAVE_LONG_LONG
/*
** Divide 64-bit a by 32-bit b, which must be normalized so its high bit is 1.
*/
static void norm_udivmod32(JSUint32 *qp, JSUint32 *rp, JSUint64 a, JSUint32 b)
{
    JSUint32 d1, d0, q1, q0;
    JSUint32 r1, r0, m;

    d1 = jshi16(b);
    d0 = jslo16(b);
    r1 = a.hi % d1;
    q1 = a.hi / d1;
    m = q1 * d0;
    r1 = (r1 << 16) | jshi16(a.lo);
    if (r1 < m) {
        q1--, r1 += b;
        if (r1 >= b     /* i.e., we didn't get a carry when adding to r1 */
            && r1 < m) {
            q1--, r1 += b;
        }
    }
    r1 -= m;
    r0 = r1 % d1;
    q0 = r1 / d1;
    m = q0 * d0;
    r0 = (r0 << 16) | jslo16(a.lo);
    if (r0 < m) {
        q0--, r0 += b;
        if (r0 >= b
            && r0 < m) {
            q0--, r0 += b;
        }
    }
    *qp = (q1 << 16) | q0;
    *rp = r0 - m;
}

static JSUint32 CountLeadingZeros(JSUint32 a)
{
    JSUint32 t;
    JSUint32 r = 32;

    if ((t = a >> 16) != 0)
        r -= 16, a = t;
    if ((t = a >> 8) != 0)
        r -= 8, a = t;
    if ((t = a >> 4) != 0)
        r -= 4, a = t;
    if ((t = a >> 2) != 0)
        r -= 2, a = t;
    if ((t = a >> 1) != 0)
        r -= 1, a = t;
    if (a & 1)
        r--;
    return r;
}

JS_PUBLIC_API(void) jsll_udivmod(JSUint64 *qp, JSUint64 *rp, JSUint64 a, JSUint64 b)
{
    JSUint32 n0, n1, n2;
    JSUint32 q0, q1;
    JSUint32 rsh, lsh;

    n0 = a.lo;
    n1 = a.hi;

    if (b.hi == 0) {
        if (b.lo > n1) {
            /* (0 q0) = (n1 n0) / (0 D0) */

            lsh = CountLeadingZeros(b.lo);

            if (lsh) {
                /*
                 * Normalize, i.e. make the most significant bit of the
                 * denominator be set.
                 */
                b.lo = b.lo << lsh;
                n1 = (n1 << lsh) | (n0 >> (32 - lsh));
                n0 = n0 << lsh;
            }

            a.lo = n0, a.hi = n1;
            norm_udivmod32(&q0, &n0, a, b.lo);
            q1 = 0;

            /* remainder is in n0 >> lsh */
        } else {
            /* (q1 q0) = (n1 n0) / (0 d0) */

            if (b.lo == 0)              /* user wants to divide by zero! */
                b.lo = 1 / b.lo;        /* so go ahead and crash */

            lsh = CountLeadingZeros(b.lo);

            if (lsh == 0) {
                /*
                 * From (n1 >= b.lo)
                 *   && (the most significant bit of b.lo is set),
                 * conclude that
                 *      (the most significant bit of n1 is set)
                 *   && (the leading quotient digit q1 = 1).
                 *
                 * This special case is necessary, not an optimization
                 * (Shifts counts of 32 are undefined).
                 */
                n1 -= b.lo;
                q1 = 1;
            } else {
                /*
                 * Normalize.
                 */
                rsh = 32 - lsh;

                b.lo = b.lo << lsh;
                n2 = n1 >> rsh;
                n1 = (n1 << lsh) | (n0 >> rsh);
                n0 = n0 << lsh;

                a.lo = n1, a.hi = n2;
                norm_udivmod32(&q1, &n1, a, b.lo);
            }

            /* n1 != b.lo... */

            a.lo = n0, a.hi = n1;
            norm_udivmod32(&q0, &n0, a, b.lo);

            /* remainder in n0 >> lsh */
        }

        if (rp) {
            rp->lo = n0 >> lsh;
            rp->hi = 0;
        }
    } else {
        if (b.hi > n1) {
            /* (0 0) = (n1 n0) / (D1 d0) */

            q0 = 0;
            q1 = 0;

            /* remainder in (n1 n0) */
            if (rp) {
                rp->lo = n0;
                rp->hi = n1;
            }
        } else {
            /* (0 q0) = (n1 n0) / (d1 d0) */

            lsh = CountLeadingZeros(b.hi);
            if (lsh == 0) {
                /*
                 * From (n1 >= b.hi)
                 *   && (the most significant bit of b.hi is set),
                 * conclude that
                 *      (the most significant bit of n1 is set)
                 *   && (the quotient digit q0 = 0 or 1).
                 *
                 * This special case is necessary, not an optimization.
                 */

                /*
                 * The condition on the next line takes advantage of that
                 * n1 >= b.hi (true due to control flow).
                 */
                if (n1 > b.hi || n0 >= b.lo) {
                    q0 = 1;
                    a.lo = n0, a.hi = n1;
                    JSLL_SUB(a, a, b);
                } else {
                    q0 = 0;
                }
                q1 = 0;

                if (rp) {
                    rp->lo = n0;
                    rp->hi = n1;
                }
            } else {
                JSInt64 m;

                /*
                 * Normalize.
                 */
                rsh = 32 - lsh;

                b.hi = (b.hi << lsh) | (b.lo >> rsh);
                b.lo = b.lo << lsh;
                n2 = n1 >> rsh;
                n1 = (n1 << lsh) | (n0 >> rsh);
                n0 = n0 << lsh;

                a.lo = n1, a.hi = n2;
                norm_udivmod32(&q0, &n1, a, b.hi);
                JSLL_MUL32(m, q0, b.lo);

                if ((m.hi > n1) || ((m.hi == n1) && (m.lo > n0))) {
                    q0--;
                    JSLL_SUB(m, m, b);
                }

                q1 = 0;

                /* Remainder is ((n1 n0) - (m1 m0)) >> lsh */
                if (rp) {
                    a.lo = n0, a.hi = n1;
                    JSLL_SUB(a, a, m);
                    rp->lo = (a.hi << rsh) | (a.lo >> lsh);
                    rp->hi = a.hi >> lsh;
                }
            }
        }
    }

    if (qp) {
        qp->lo = q0;
        qp->hi = q1;
    }
}
#endif /* !JS_HAVE_LONG_LONG */
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 */