1 |
|
|
/**************************************************************** |
2 |
|
|
|
3 |
|
|
The author of this software is David M. Gay. |
4 |
|
|
|
5 |
|
|
Copyright (C) 1998 by Lucent Technologies |
6 |
|
|
All Rights Reserved |
7 |
|
|
|
8 |
|
|
Permission to use, copy, modify, and distribute this software and |
9 |
|
|
its documentation for any purpose and without fee is hereby |
10 |
|
|
granted, provided that the above copyright notice appear in all |
11 |
|
|
copies and that both that the copyright notice and this |
12 |
|
|
permission notice and warranty disclaimer appear in supporting |
13 |
|
|
documentation, and that the name of Lucent or any of its entities |
14 |
|
|
not be used in advertising or publicity pertaining to |
15 |
|
|
distribution of the software without specific, written prior |
16 |
|
|
permission. |
17 |
|
|
|
18 |
|
|
LUCENT DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, |
19 |
|
|
INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. |
20 |
|
|
IN NO EVENT SHALL LUCENT OR ANY OF ITS ENTITIES BE LIABLE FOR ANY |
21 |
|
|
SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES |
22 |
|
|
WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER |
23 |
|
|
IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, |
24 |
|
|
ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF |
25 |
|
|
THIS SOFTWARE. |
26 |
|
|
|
27 |
|
|
****************************************************************/ |
28 |
|
|
|
29 |
|
|
/* Please send bug reports to David M. Gay (dmg at acm dot org, |
30 |
|
|
* with " at " changed at "@" and " dot " changed to "."). */ |
31 |
|
|
|
32 |
|
|
#include "gdtoaimp.h" |
33 |
|
|
|
34 |
|
|
#ifndef MULTIPLE_THREADS |
35 |
|
|
char *dtoa_result; |
36 |
|
|
#endif |
37 |
|
|
|
38 |
|
|
char * |
39 |
|
|
#ifdef KR_headers |
40 |
|
|
rv_alloc(i) int i; |
41 |
|
|
#else |
42 |
|
|
rv_alloc(int i) |
43 |
|
|
#endif |
44 |
|
|
{ |
45 |
|
|
int j, k, *r; |
46 |
|
|
|
47 |
|
|
j = sizeof(ULong); |
48 |
|
|
for(k = 0; |
49 |
|
|
sizeof(Bigint) - sizeof(ULong) - sizeof(int) + j <= i; |
50 |
|
|
j <<= 1) |
51 |
|
|
k++; |
52 |
|
|
r = (int*)Balloc(k); |
53 |
|
|
if (r == NULL) |
54 |
|
|
return ( |
55 |
|
|
#ifndef MULTIPLE_THREADS |
56 |
|
|
dtoa_result = |
57 |
|
|
#endif |
58 |
|
|
NULL); |
59 |
|
|
*r = k; |
60 |
|
|
return |
61 |
|
|
#ifndef MULTIPLE_THREADS |
62 |
|
|
dtoa_result = |
63 |
|
|
#endif |
64 |
|
|
(char *)(r+1); |
65 |
|
|
} |
66 |
|
|
|
67 |
|
|
char * |
68 |
|
|
#ifdef KR_headers |
69 |
|
|
nrv_alloc(s, rve, n) char *s, **rve; int n; |
70 |
|
|
#else |
71 |
|
|
nrv_alloc(char *s, char **rve, int n) |
72 |
|
|
#endif |
73 |
|
|
{ |
74 |
|
|
char *rv, *t; |
75 |
|
|
|
76 |
|
|
t = rv = rv_alloc(n); |
77 |
|
|
if (t == NULL) |
78 |
|
|
return (NULL); |
79 |
|
|
while((*t = *s++) !=0) |
80 |
|
|
t++; |
81 |
|
|
if (rve) |
82 |
|
|
*rve = t; |
83 |
|
|
return rv; |
84 |
|
|
} |
85 |
|
|
|
86 |
|
|
/* freedtoa(s) must be used to free values s returned by dtoa |
87 |
|
|
* when MULTIPLE_THREADS is #defined. It should be used in all cases, |
88 |
|
|
* but for consistency with earlier versions of dtoa, it is optional |
89 |
|
|
* when MULTIPLE_THREADS is not defined. |
90 |
|
|
*/ |
91 |
|
|
|
92 |
|
|
void |
93 |
|
|
#ifdef KR_headers |
94 |
|
|
freedtoa(s) char *s; |
95 |
|
|
#else |
96 |
|
|
freedtoa(char *s) |
97 |
|
|
#endif |
98 |
|
|
{ |
99 |
|
|
Bigint *b = (Bigint *)((int *)s - 1); |
100 |
|
|
b->maxwds = 1 << (b->k = *(int*)b); |
101 |
|
|
Bfree(b); |
102 |
|
|
#ifndef MULTIPLE_THREADS |
103 |
|
|
if (s == dtoa_result) |
104 |
|
|
dtoa_result = 0; |
105 |
|
|
#endif |
106 |
|
|
} |
107 |
|
|
DEF_STRONG(freedtoa); |
108 |
|
|
|
109 |
|
|
int |
110 |
|
|
quorem |
111 |
|
|
#ifdef KR_headers |
112 |
|
|
(b, S) Bigint *b, *S; |
113 |
|
|
#else |
114 |
|
|
(Bigint *b, Bigint *S) |
115 |
|
|
#endif |
116 |
|
|
{ |
117 |
|
|
int n; |
118 |
|
|
ULong *bx, *bxe, q, *sx, *sxe; |
119 |
|
|
#ifdef ULLong |
120 |
|
|
ULLong borrow, carry, y, ys; |
121 |
|
|
#else |
122 |
|
|
ULong borrow, carry, y, ys; |
123 |
|
|
#ifdef Pack_32 |
124 |
|
|
ULong si, z, zs; |
125 |
|
|
#endif |
126 |
|
|
#endif |
127 |
|
|
|
128 |
|
|
n = S->wds; |
129 |
|
|
#ifdef DEBUG |
130 |
|
|
/*debug*/ if (b->wds > n) |
131 |
|
|
/*debug*/ Bug("oversize b in quorem"); |
132 |
|
|
#endif |
133 |
|
|
if (b->wds < n) |
134 |
|
|
return 0; |
135 |
|
|
sx = S->x; |
136 |
|
|
sxe = sx + --n; |
137 |
|
|
bx = b->x; |
138 |
|
|
bxe = bx + n; |
139 |
|
|
q = *bxe / (*sxe + 1); /* ensure q <= true quotient */ |
140 |
|
|
#ifdef DEBUG |
141 |
|
|
/*debug*/ if (q > 9) |
142 |
|
|
/*debug*/ Bug("oversized quotient in quorem"); |
143 |
|
|
#endif |
144 |
|
|
if (q) { |
145 |
|
|
borrow = 0; |
146 |
|
|
carry = 0; |
147 |
|
|
do { |
148 |
|
|
#ifdef ULLong |
149 |
|
|
ys = *sx++ * (ULLong)q + carry; |
150 |
|
|
carry = ys >> 32; |
151 |
|
|
y = *bx - (ys & 0xffffffffUL) - borrow; |
152 |
|
|
borrow = y >> 32 & 1UL; |
153 |
|
|
*bx++ = y & 0xffffffffUL; |
154 |
|
|
#else |
155 |
|
|
#ifdef Pack_32 |
156 |
|
|
si = *sx++; |
157 |
|
|
ys = (si & 0xffff) * q + carry; |
158 |
|
|
zs = (si >> 16) * q + (ys >> 16); |
159 |
|
|
carry = zs >> 16; |
160 |
|
|
y = (*bx & 0xffff) - (ys & 0xffff) - borrow; |
161 |
|
|
borrow = (y & 0x10000) >> 16; |
162 |
|
|
z = (*bx >> 16) - (zs & 0xffff) - borrow; |
163 |
|
|
borrow = (z & 0x10000) >> 16; |
164 |
|
|
Storeinc(bx, z, y); |
165 |
|
|
#else |
166 |
|
|
ys = *sx++ * q + carry; |
167 |
|
|
carry = ys >> 16; |
168 |
|
|
y = *bx - (ys & 0xffff) - borrow; |
169 |
|
|
borrow = (y & 0x10000) >> 16; |
170 |
|
|
*bx++ = y & 0xffff; |
171 |
|
|
#endif |
172 |
|
|
#endif |
173 |
|
|
} |
174 |
|
|
while(sx <= sxe); |
175 |
|
|
if (!*bxe) { |
176 |
|
|
bx = b->x; |
177 |
|
|
while(--bxe > bx && !*bxe) |
178 |
|
|
--n; |
179 |
|
|
b->wds = n; |
180 |
|
|
} |
181 |
|
|
} |
182 |
|
|
if (cmp(b, S) >= 0) { |
183 |
|
|
q++; |
184 |
|
|
borrow = 0; |
185 |
|
|
carry = 0; |
186 |
|
|
bx = b->x; |
187 |
|
|
sx = S->x; |
188 |
|
|
do { |
189 |
|
|
#ifdef ULLong |
190 |
|
|
ys = *sx++ + carry; |
191 |
|
|
carry = ys >> 32; |
192 |
|
|
y = *bx - (ys & 0xffffffffUL) - borrow; |
193 |
|
|
borrow = y >> 32 & 1UL; |
194 |
|
|
*bx++ = y & 0xffffffffUL; |
195 |
|
|
#else |
196 |
|
|
#ifdef Pack_32 |
197 |
|
|
si = *sx++; |
198 |
|
|
ys = (si & 0xffff) + carry; |
199 |
|
|
zs = (si >> 16) + (ys >> 16); |
200 |
|
|
carry = zs >> 16; |
201 |
|
|
y = (*bx & 0xffff) - (ys & 0xffff) - borrow; |
202 |
|
|
borrow = (y & 0x10000) >> 16; |
203 |
|
|
z = (*bx >> 16) - (zs & 0xffff) - borrow; |
204 |
|
|
borrow = (z & 0x10000) >> 16; |
205 |
|
|
Storeinc(bx, z, y); |
206 |
|
|
#else |
207 |
|
|
ys = *sx++ + carry; |
208 |
|
|
carry = ys >> 16; |
209 |
|
|
y = *bx - (ys & 0xffff) - borrow; |
210 |
|
|
borrow = (y & 0x10000) >> 16; |
211 |
|
|
*bx++ = y & 0xffff; |
212 |
|
|
#endif |
213 |
|
|
#endif |
214 |
|
|
} |
215 |
|
|
while(sx <= sxe); |
216 |
|
|
bx = b->x; |
217 |
|
|
bxe = bx + n; |
218 |
|
|
if (!*bxe) { |
219 |
|
|
while(--bxe > bx && !*bxe) |
220 |
|
|
--n; |
221 |
|
|
b->wds = n; |
222 |
|
|
} |
223 |
|
|
} |
224 |
|
|
return q; |
225 |
|
|
} |