1 /* $NetBSD: dmisc.c,v 1.2 2006/01/25 15:27:42 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*)(void*)Balloc(k); 55 *r = k; 56 return 57 #ifndef MULTIPLE_THREADS 58 dtoa_result = 59 #endif 60 (char *)(void *)(r+1); 61 } 62 63 char * 64 #ifdef KR_headers 65 nrv_alloc(s, rve, n) CONST char *s; char **rve; int n; 66 #else 67 nrv_alloc(CONST 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 *)(void *)((int *)(void *)s - 1); 94 b->maxwds = 1 << (b->k = *(int*)(void*)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 /* LINTED conversion */ 145 y = *bx - (ys & 0xffffffffUL) - borrow; 146 borrow = y >> 32 & 1UL; 147 /* LINTED conversion */ 148 *bx++ = y & 0xffffffffUL; 149 #else 150 #ifdef Pack_32 151 si = *sx++; 152 ys = (si & 0xffff) * q + carry; 153 zs = (si >> 16) * q + (ys >> 16); 154 carry = zs >> 16; 155 y = (*bx & 0xffff) - (ys & 0xffff) - borrow; 156 borrow = (y & 0x10000) >> 16; 157 z = (*bx >> 16) - (zs & 0xffff) - borrow; 158 borrow = (z & 0x10000) >> 16; 159 Storeinc(bx, z, y); 160 #else 161 ys = *sx++ * q + carry; 162 carry = ys >> 16; 163 y = *bx - (ys & 0xffff) - borrow; 164 borrow = (y & 0x10000) >> 16; 165 *bx++ = y & 0xffff; 166 #endif 167 #endif 168 } 169 while(sx <= sxe); 170 if (!*bxe) { 171 bx = b->x; 172 while(--bxe > bx && !*bxe) 173 --n; 174 b->wds = n; 175 } 176 } 177 if (cmp(b, S) >= 0) { 178 q++; 179 borrow = 0; 180 carry = 0; 181 bx = b->x; 182 sx = S->x; 183 do { 184 #ifdef ULLong 185 ys = *sx++ + carry; 186 carry = ys >> 32; 187 /* LINTED conversion */ 188 y = *bx - (ys & 0xffffffffUL) - borrow; 189 borrow = y >> 32 & 1UL; 190 /* LINTED conversion */ 191 *bx++ = y & 0xffffffffUL; 192 #else 193 #ifdef Pack_32 194 si = *sx++; 195 ys = (si & 0xffff) + carry; 196 zs = (si >> 16) + (ys >> 16); 197 carry = zs >> 16; 198 y = (*bx & 0xffff) - (ys & 0xffff) - borrow; 199 borrow = (y & 0x10000) >> 16; 200 z = (*bx >> 16) - (zs & 0xffff) - borrow; 201 borrow = (z & 0x10000) >> 16; 202 Storeinc(bx, z, y); 203 #else 204 ys = *sx++ + carry; 205 carry = ys >> 16; 206 y = *bx - (ys & 0xffff) - borrow; 207 borrow = (y & 0x10000) >> 16; 208 *bx++ = y & 0xffff; 209 #endif 210 #endif 211 } 212 while(sx <= sxe); 213 bx = b->x; 214 bxe = bx + n; 215 if (!*bxe) { 216 while(--bxe > bx && !*bxe) 217 --n; 218 b->wds = n; 219 } 220 } 221 return q; 222 } 223