← Back to branch summary

~ubuntu-branches/ubuntu/precise/kompozer/precise

« back to all changes in this revision

Viewing changes to mozilla/js/src/jslong.c

  • Committer: Bazaar Package Importer
  • Author(s): Anthony Yarusso
  • Date: 2007-08-27 01:11:03 UTC
  • Revision ID: james.westby@ubuntu.com-20070827011103-2jgf4s6532gqu2ka
Tags: upstream-0.7.10
Import upstream version 0.7.10

Show diffs side-by-side

added added

removed removed

Lines of Context:
mozilla/js/src/jslong.c
 
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
JS_PUBLIC_API(JSInt64) JSLL_Zero(void) { return ll_zero; }
 
56
JS_PUBLIC_API(JSInt64) JSLL_MaxInt(void) { return ll_maxint; }
 
57
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
}
 
281
#endif /* !JS_HAVE_LONG_LONG */