1/****************************************************************
2
3The author of this software is David M. Gay.
4
5Copyright (C) 1998 by Lucent Technologies
6All Rights Reserved
7
8Permission to use, copy, modify, and distribute this software and
9its documentation for any purpose and without fee is hereby
10granted, provided that the above copyright notice appear in all
11copies and that both that the copyright notice and this
12permission notice and warranty disclaimer appear in supporting
13documentation, and that the name of Lucent or any of its entities
14not be used in advertising or publicity pertaining to
15distribution of the software without specific, written prior
16permission.
17
18LUCENT DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
19INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.
20IN NO EVENT SHALL LUCENT OR ANY OF ITS ENTITIES BE LIABLE FOR ANY
21SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
22WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER
23IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
24ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
25THIS 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
40rv_alloc(i) int i;
41#else
42rv_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
69nrv_alloc(s, rve, n) char *s, **rve; int n;
70#else
71nrv_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
94freedtoa(s) char *s;
95#else
96freedtoa(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	}
107DEF_STRONG(freedtoa);
108
109 int
110quorem
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	}
226