1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
|
/*
* |-----------------------------------------------------------|
* | Copyright (c) 1991 MIPS Computer Systems, Inc. |
* | All Rights Reserved |
* |-----------------------------------------------------------|
* | Restricted Rights Legend |
* | Use, duplication, or disclosure by the Government is |
* | subject to restrictions as set forth in |
* | subparagraph (c)(1)(ii) of the Rights in Technical |
* | Data and Computer Software Clause of DFARS 52.227-7013. |
* | MIPS Computer Systems, Inc. |
* | 950 DeGuigne Drive |
* | Sunnyvale, CA 94086 |
* |-----------------------------------------------------------|
*/
/* $Header: lldiv.c,v 3010.7 92/01/29 16:02:33 murphy Exp $ */
#include "lldefs.h"
/*
Make sure that the intrinsic bit shift routines are not used!
They are guaranteed to work only for shifts of 0-31 bits.
*/
#pragma function(__ll_lshift)
#pragma function(__ll_rshift)
#pragma function(__ull_rshift)
extern void __ull_divrem_6416 (ulonglong_t *q, ulonglong_t *r, ulonglong_t n, ulonglong_t d);
extern void __ull_divrem_5353 (ulonglong_t *q, ulonglong_t *r, ulonglong_t n, ulonglong_t d);
static void __ull_divrem_6464 (llvalue *aquo, llvalue *arem, llvalue num, llvalue denom);
#define pow2_16 65536 /* 2^16 */
#define pow2_21 2097152 /* 2^(53-32) */
/* Given an unsigned64 number, return the number of left-shifts required
to normalize it (causing high-order digit to be 1) */
static
unsigned
ll_firstbit(llvalue number)
{
unsigned bias = 0;
if (MSW(number) == 0)
{
if (LSW(number) != 0)
{
bias = 32;
while ((LSW(number) & 0x80000000) == 0)
{
bias++;
LSW(number) <<= 1;
}
}
}
else
{
while ((MSW(number) & 0x80000000) == 0)
{
bias++;
MSW(number) <<= 1;
}
}
return bias;
}
/*
* General (i.e., difficult) case of 64-bit unsigned division.
* Use this to handle cases where values are greater than can be
* represented with 53-bits of double floats.
* Modified from pl1 library.
*/
static
void
__ull_divrem_6464 (llvalue *aquo, llvalue *arem, llvalue num, llvalue denom)
{
llvalue quo;
int n_bias, d_bias;
/* Shift denom left so its first bit lines up with that of numerator */
n_bias = ll_firstbit(num);
d_bias = ll_firstbit(denom);
if ((d_bias -= n_bias) > 0) {
denom.ll = __ll_lshift(denom.ll, d_bias);
}
/*
"Long division" just like you did in elementary school, except that
by virtue of doing it in binary, we can guess the next digit simply
by comparing numerator and divisor.
quo = 0;
repeat (1 + amount_we_shifted_denom_left)
{
quo <<= 1;
if (!(num < denom))
{
num -= denom;
quo |= 1;
}
denom >>= 1;
}
*/
MSW(quo) = LSW(quo) = 0;
while (d_bias-- >= 0)
{
quo.ll = __ll_lshift(quo.ll, 1);
if (ULL_GE(num, denom))
{
LL_SUB(num, num, denom); /* num -= denom */
LSW(quo) |= 1;
}
denom.ll = __ull_rshift(denom.ll, 1);
}
*aquo = quo;
*arem = num;
}
extern longlong_t
__ll_div (longlong_t left, longlong_t right)
{
llvalue a,b,q,r;
llvalue ll_2_16, ll_2_53;
int negate = 0;
a.ll = left;
b.ll = right;
SET_LL(ll_2_16, pow2_16);
MSW(ll_2_53) = pow2_21; LSW(ll_2_53) = 0;
if (LL_ISNEG(a)) {
/* make positive, but later negate the quotient */
negate = !negate;
LL_NEG(a,a);
}
if (LL_ISNEG(b)) {
/* make positive, but later negate the quotient */
negate = !negate;
LL_NEG(b,b);
}
/* dividend is positive */
if (ULL_LT(b,ll_2_16)) {
/* divide 64 bits by 16 bits */
__ull_divrem_6416(&q.ull,&r.ull,a.ull,b.ull);
} else if (ULL_LE(a,ll_2_53) && ULL_LE(b,ll_2_53)) {
/* do fp double divide */
__ull_divrem_5353(&q.ull,&r.ull,a.ull,b.ull);
} else {
/* do full 64-bit divide */
__ull_divrem_6464(&q,&r, a, b);
}
if (negate) {
LL_NEG(q,q);
}
return q.ll;
}
extern ulonglong_t
__ull_div (ulonglong_t left, ulonglong_t right)
{
llvalue a,b,q,r;
llvalue ll_2_16, ll_2_53;
a.ull = left;
b.ull = right;
SET_LL(ll_2_16, pow2_16);
MSW(ll_2_53) = pow2_21; LSW(ll_2_53) = 0;
if (ULL_LT(b,ll_2_16)) {
__ull_divrem_6416(&q.ull,&r.ull,left,right);
} else if (ULL_LE(a,ll_2_53) && ULL_LE(b,ll_2_53)) {
__ull_divrem_5353(&q.ull,&r.ull,left,right);
} else {
__ull_divrem_6464(&q,&r,a,b);
}
return q.ull;
}
extern longlong_t
__ll_rem (longlong_t left, longlong_t right)
{
llvalue a,b,q,r;
llvalue ll_2_16, ll_2_53;
int negate = 0;
a.ll = left;
b.ll = right;
SET_LL(ll_2_16, pow2_16);
MSW(ll_2_53) = pow2_21; LSW(ll_2_53) = 0;
if (LL_ISNEG(a)) {
/* make positive, but later negate the remainder */
negate = !negate;
LL_NEG(a,a);
}
if (LL_ISNEG(b)) {
/* make positive, remainder only depends on sign of num */
LL_NEG(b,b);
}
/* dividend is positive */
if (ULL_LT(b,ll_2_16)) {
/* divide 64 bits by 16 bits */
__ull_divrem_6416(&q.ull,&r.ull,a.ull,b.ull);
} else if (ULL_LE(a,ll_2_53) && ULL_LE(b,ll_2_53)) {
/* do fp double divide */
__ull_divrem_5353(&q.ull,&r.ull,a.ull,b.ull);
} else {
/* do full 64-bit divide */
__ull_divrem_6464(&q,&r, a, b);
}
if (negate) {
LL_NEG(r,r);
}
return r.ll;
}
extern ulonglong_t
__ull_rem (ulonglong_t left, ulonglong_t right)
{
llvalue a,b,q,r;
llvalue ll_2_16, ll_2_53;
a.ll = left;
b.ll = right;
SET_LL(ll_2_16, pow2_16);
MSW(ll_2_53) = pow2_21; LSW(ll_2_53) = 0;
if (ULL_LT(b,ll_2_16)) {
__ull_divrem_6416(&q.ull,&r.ull,left,right);
} else if (ULL_LE(a,ll_2_53) && ULL_LE(b,ll_2_53)) {
__ull_divrem_5353(&q.ull,&r.ull,left,right);
} else {
__ull_divrem_6464(&q,&r,a,b);
}
return r.ull;
}
extern
longlong_t
__ll_mod (longlong_t left, longlong_t right)
{
/* mod is similar to rem except that:
* 11 rem 5 == 1 == 11 mod 5
* 11 rem -5 == 1, 11 mod -5 == -4
* -11 rem 5 == -1, -11 mod 5 == 4
* -11 rem -5 == -1 == -11 mod -5
*/
llvalue b,r;
b.ll = right;
r.ll = __ll_rem(left,right);
if (LL_ISNEG(r) != LL_ISNEG(b)) {
LL_ADD(r,r,b);
}
return r.ll;
}
|
