dmisc.c revision 1.1
1 /* $NetBSD: dmisc.c,v 1.1 2006/01/25 15:18:40 kleink 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 42 rv_alloc(i) int i; 43 #else 44 rv_alloc(int i) 45 #endif 46 { 47 int j, k, *r; 48 49 j = sizeof(ULong); 50 for(k = 0; 51 sizeof(Bigint) - sizeof(ULong) - sizeof(int) + j <= i; 52 j <<= 1) 53 k++; 54 r = (int*)Balloc(k); 55 *r = k; 56 return 57 #ifndef MULTIPLE_THREADS 58 dtoa_result = 59 #endif 60 (char *)(r+1); 61 } 62 63 char * 64 #ifdef KR_headers 65 nrv_alloc(s, rve, n) char *s, **rve; int n; 66 #else 67 nrv_alloc(char *s, char **rve, int n) 68 #endif 69 { 70 char *rv, *t; 71 72 t = rv = rv_alloc(n); 73 while((*t = *s++) !=0) 74 t++; 75 if (rve) 76 *rve = t; 77 return rv; 78 } 79 80 /* freedtoa(s) must be used to free values s returned by dtoa 81 * when MULTIPLE_THREADS is #defined. It should be used in all cases, 82 * but for consistency with earlier versions of dtoa, it is optional 83 * when MULTIPLE_THREADS is not defined. 84 */ 85 86 void 87 #ifdef KR_headers 88 freedtoa(s) char *s; 89 #else 90 freedtoa(char *s) 91 #endif 92 { 93 Bigint *b = (Bigint *)((int *)s - 1); 94 b->maxwds = 1 << (b->k = *(int*)b); 95 Bfree(b); 96 #ifndef MULTIPLE_THREADS 97 if (s == dtoa_result) 98 dtoa_result = 0; 99 #endif 100 } 101 102 int 103 quorem 104 #ifdef KR_headers 105 (b, S) Bigint *b, *S; 106 #else 107 (Bigint *b, Bigint *S) 108 #endif 109 { 110 int n; 111 ULong *bx, *bxe, q, *sx, *sxe; 112 #ifdef ULLong 113 ULLong borrow, carry, y, ys; 114 #else 115 ULong borrow, carry, y, ys; 116 #ifdef Pack_32 117 ULong si, z, zs; 118 #endif 119 #endif 120 121 n = S->wds; 122 #ifdef DEBUG 123 /*debug*/ if (b->wds > n) 124 /*debug*/ Bug("oversize b in quorem"); 125 #endif 126 if (b->wds < n) 127 return 0; 128 sx = S->x; 129 sxe = sx + --n; 130 bx = b->x; 131 bxe = bx + n; 132 q = *bxe / (*sxe + 1); /* ensure q <= true quotient */ 133 #ifdef DEBUG 134 /*debug*/ if (q > 9) 135 /*debug*/ Bug("oversized quotient in quorem"); 136 #endif 137 if (q) { 138 borrow = 0; 139 carry = 0; 140 do { 141 #ifdef ULLong 142 ys = *sx++ * (ULLong)q + carry; 143 carry = ys >> 32; 144 y = *bx - (ys & 0xffffffffUL) - borrow; 145 borrow = y >> 32 & 1UL; 146 *bx++ = y & 0xffffffffUL; 147 #else 148 #ifdef Pack_32 149 si = *sx++; 150 ys = (si & 0xffff) * q + carry; 151 zs = (si >> 16) * q + (ys >> 16); 152 carry = zs >> 16; 153 y = (*bx & 0xffff) - (ys & 0xffff) - borrow; 154 borrow = (y & 0x10000) >> 16; 155 z = (*bx >> 16) - (zs & 0xffff) - borrow; 156 borrow = (z & 0x10000) >> 16; 157 Storeinc(bx, z, y); 158 #else 159 ys = *sx++ * q + carry; 160 carry = ys >> 16; 161 y = *bx - (ys & 0xffff) - borrow; 162 borrow = (y & 0x10000) >> 16; 163 *bx++ = y & 0xffff; 164 #endif 165 #endif 166 } 167 while(sx <= sxe); 168 if (!*bxe) { 169 bx = b->x; 170 while(--bxe > bx && !*bxe) 171 --n; 172 b->wds = n; 173 } 174 } 175 if (cmp(b, S) >= 0) { 176 q++; 177 borrow = 0; 178 carry = 0; 179 bx = b->x; 180 sx = S->x; 181 do { 182 #ifdef ULLong 183 ys = *sx++ + carry; 184 carry = ys >> 32; 185 y = *bx - (ys & 0xffffffffUL) - borrow; 186 borrow = y >> 32 & 1UL; 187 *bx++ = y & 0xffffffffUL; 188 #else 189 #ifdef Pack_32 190 si = *sx++; 191 ys = (si & 0xffff) + carry; 192 zs = (si >> 16) + (ys >> 16); 193 carry = zs >> 16; 194 y = (*bx & 0xffff) - (ys & 0xffff) - borrow; 195 borrow = (y & 0x10000) >> 16; 196 z = (*bx >> 16) - (zs & 0xffff) - borrow; 197 borrow = (z & 0x10000) >> 16; 198 Storeinc(bx, z, y); 199 #else 200 ys = *sx++ + carry; 201 carry = ys >> 16; 202 y = *bx - (ys & 0xffff) - borrow; 203 borrow = (y & 0x10000) >> 16; 204 *bx++ = y & 0xffff; 205 #endif 206 #endif 207 } 208 while(sx <= sxe); 209 bx = b->x; 210 bxe = bx + n; 211 if (!*bxe) { 212 while(--bxe > bx && !*bxe) 213 --n; 214 b->wds = n; 215 } 216 } 217 return q; 218 } 219
Indexes created Tue Sep 23 14:10:03 GMT 2025