1 /* $NetBSD: dmisc.c,v 1.2.4.1.4.1 2008/04/08 21:10:55 jdc 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 #include <LibConfig.h>
34
35 #include "gdtoaimp.h"
36
37 #ifndef MULTIPLE_THREADS
38 char *dtoa_result;
39 #endif
40
41 char *
42 #ifdef KR_headers
rv_alloc(i)43 rv_alloc(i) size_t i;
44 #else
45 rv_alloc(size_t i)
46 #endif
47 {
48 size_t j;
49 int k, *r;
50
51 j = sizeof(ULong);
52 for(k = 0;
53 sizeof(Bigint) - sizeof(ULong) - sizeof(int) + j <= i;
54 j <<= 1)
55 k++;
56 r = (int*)(void*)Balloc(k);
57 if (r == NULL)
58 return NULL;
59 *r = k;
60 return
61 #ifndef MULTIPLE_THREADS
62 dtoa_result =
63 #endif
64 (char *)(void *)(r+1);
65 }
66
67 char *
68 #ifdef KR_headers
nrv_alloc(s,rve,n)69 nrv_alloc(s, rve, n) CONST char *s; char **rve; size_t n;
70 #else
71 nrv_alloc(CONST char *s, char **rve, size_t 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
freedtoa(s)94 freedtoa(s) char *s;
95 #else
96 freedtoa(char *s)
97 #endif
98 {
99 Bigint *b = (Bigint *)(void *)((int *)(void *)s - 1);
100 b->maxwds = 1 << (b->k = *(int*)(void*)b);
101 Bfree(b);
102 #ifndef MULTIPLE_THREADS
103 if (s == dtoa_result)
104 dtoa_result = 0;
105 #endif
106 }
107
108 int
quorem(b,S)109 quorem
110 #ifdef KR_headers
111 (b, S) Bigint *b, *S;
112 #else
113 (Bigint *b, Bigint *S)
114 #endif
115 {
116 int n;
117 ULong *bx, *bxe, q, *sx, *sxe;
118 #ifdef ULLong
119 ULLong borrow, carry, y, ys;
120 #else
121 ULong borrow, carry, y, ys;
122 #ifdef Pack_32
123 ULong si, z, zs;
124 #endif
125 #endif
126
127 n = S->wds;
128 #ifdef DEBUG
129 /*debug*/ if (b->wds > n)
130 /*debug*/ Bug("oversize b in quorem");
131 #endif
132 if (b->wds < n)
133 return 0;
134 sx = S->x;
135 sxe = sx + --n;
136 bx = b->x;
137 bxe = bx + n;
138 q = *bxe / (*sxe + 1); /* ensure q <= true quotient */
139 #ifdef DEBUG
140 /*debug*/ if (q > 9)
141 /*debug*/ Bug("oversized quotient in quorem");
142 #endif
143 if (q) {
144 borrow = 0;
145 carry = 0;
146 do {
147 #ifdef ULLong
148 ys = *sx++ * (ULLong)q + carry;
149 carry = ys >> 32;
150 /* LINTED conversion */
151 y = *bx - (ys & 0xffffffffUL) - borrow;
152 borrow = y >> 32 & 1UL;
153 /* LINTED conversion */
154 *bx++ = (UINT32)(y & 0xffffffffUL);
155 #else
156 #ifdef Pack_32
157 si = *sx++;
158 ys = (si & 0xffff) * q + carry;
159 zs = (si >> 16) * q + (ys >> 16);
160 carry = zs >> 16;
161 y = (*bx & 0xffff) - (ys & 0xffff) - borrow;
162 borrow = (y & 0x10000) >> 16;
163 z = (*bx >> 16) - (zs & 0xffff) - borrow;
164 borrow = (z & 0x10000) >> 16;
165 Storeinc(bx, z, y);
166 #else
167 ys = *sx++ * q + carry;
168 carry = ys >> 16;
169 y = *bx - (ys & 0xffff) - borrow;
170 borrow = (y & 0x10000) >> 16;
171 *bx++ = y & 0xffff;
172 #endif
173 #endif
174 }
175 while(sx <= sxe);
176 if (!*bxe) {
177 bx = b->x;
178 while(--bxe > bx && !*bxe)
179 --n;
180 b->wds = n;
181 }
182 }
183 if (cmp(b, S) >= 0) {
184 q++;
185 borrow = 0;
186 carry = 0;
187 bx = b->x;
188 sx = S->x;
189 do {
190 #ifdef ULLong
191 ys = *sx++ + carry;
192 carry = ys >> 32;
193 /* LINTED conversion */
194 y = *bx - (ys & 0xffffffffUL) - borrow;
195 borrow = y >> 32 & 1UL;
196 /* LINTED conversion */
197 *bx++ = (UINT32)(y & 0xffffffffUL);
198 #else
199 #ifdef Pack_32
200 si = *sx++;
201 ys = (si & 0xffff) + carry;
202 zs = (si >> 16) + (ys >> 16);
203 carry = zs >> 16;
204 y = (*bx & 0xffff) - (ys & 0xffff) - borrow;
205 borrow = (y & 0x10000) >> 16;
206 z = (*bx >> 16) - (zs & 0xffff) - borrow;
207 borrow = (z & 0x10000) >> 16;
208 Storeinc(bx, z, y);
209 #else
210 ys = *sx++ + carry;
211 carry = ys >> 16;
212 y = *bx - (ys & 0xffff) - borrow;
213 borrow = (y & 0x10000) >> 16;
214 *bx++ = y & 0xffff;
215 #endif
216 #endif
217 }
218 while(sx <= sxe);
219 bx = b->x;
220 bxe = bx + n;
221 if (!*bxe) {
222 while(--bxe > bx && !*bxe)
223 --n;
224 b->wds = n;
225 }
226 }
227 return (int)q;
228 }
229