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 } 226