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