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