1240116Smarcel/* $NetBSD: dmisc.c,v 1.3 2007/02/03 16:44:02 christos Exp $ */ 2240116Smarcel 3240116Smarcel/**************************************************************** 4240116Smarcel 5240116SmarcelThe author of this software is David M. Gay. 6240116Smarcel 7240116SmarcelCopyright (C) 1998 by Lucent Technologies 8240116SmarcelAll Rights Reserved 9240116Smarcel 10240116SmarcelPermission to use, copy, modify, and distribute this software and 11240116Smarcelits documentation for any purpose and without fee is hereby 12240116Smarcelgranted, provided that the above copyright notice appear in all 13240116Smarcelcopies and that both that the copyright notice and this 14240116Smarcelpermission notice and warranty disclaimer appear in supporting 15240116Smarceldocumentation, and that the name of Lucent or any of its entities 16240116Smarcelnot be used in advertising or publicity pertaining to 17240116Smarceldistribution of the software without specific, written prior 18240116Smarcelpermission. 19240116Smarcel 20240116SmarcelLUCENT DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, 21240116SmarcelINCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. 22240116SmarcelIN NO EVENT SHALL LUCENT OR ANY OF ITS ENTITIES BE LIABLE FOR ANY 23240116SmarcelSPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 24240116SmarcelWHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER 25240116SmarcelIN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, 26240116SmarcelARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF 27240116SmarcelTHIS SOFTWARE. 28240116Smarcel 29240116Smarcel****************************************************************/ 30240116Smarcel 31240116Smarcel/* Please send bug reports to David M. Gay (dmg at acm dot org, 32240116Smarcel * with " at " changed at "@" and " dot " changed to "."). */ 33240116Smarcel 34240116Smarcel#include "gdtoaimp.h" 35240116Smarcel 36240116Smarcel#ifndef MULTIPLE_THREADS 37240116Smarcel char *dtoa_result; 38240116Smarcel#endif 39240116Smarcel 40240116Smarcel char * 41240116Smarcel#ifdef KR_headers 42240116Smarcelrv_alloc(i) size_t i; 43240116Smarcel#else 44240116Smarcelrv_alloc(size_t i) 45240116Smarcel#endif 46240116Smarcel{ 47240116Smarcel size_t j; 48240116Smarcel int k, *r; 49240116Smarcel 50240116Smarcel j = sizeof(ULong); 51 for(k = 0; 52 sizeof(Bigint) - sizeof(ULong) - sizeof(int) + j <= i; 53 j <<= 1) 54 k++; 55 r = (int*)(void*)Balloc(k); 56 if (r == NULL) 57 return NULL; 58 *r = k; 59 return 60#ifndef MULTIPLE_THREADS 61 dtoa_result = 62#endif 63 (char *)(void *)(r+1); 64 } 65 66 char * 67#ifdef KR_headers 68nrv_alloc(s, rve, n) CONST char *s; char **rve; size_t n; 69#else 70nrv_alloc(CONST char *s, char **rve, size_t n) 71#endif 72{ 73 char *rv, *t; 74 75 t = rv = rv_alloc(n); 76 if (t == NULL) 77 return NULL; 78 while((*t = *s++) !=0) 79 t++; 80 if (rve) 81 *rve = t; 82 return rv; 83 } 84 85/* freedtoa(s) must be used to free values s returned by dtoa 86 * when MULTIPLE_THREADS is #defined. It should be used in all cases, 87 * but for consistency with earlier versions of dtoa, it is optional 88 * when MULTIPLE_THREADS is not defined. 89 */ 90 91 void 92#ifdef KR_headers 93freedtoa(s) char *s; 94#else 95freedtoa(char *s) 96#endif 97{ 98 Bigint *b = (Bigint *)(void *)((int *)(void *)s - 1); 99 b->maxwds = 1 << (b->k = *(int*)(void*)b); 100 Bfree(b); 101#ifndef MULTIPLE_THREADS 102 if (s == dtoa_result) 103 dtoa_result = 0; 104#endif 105 } 106 107 int 108quorem 109#ifdef KR_headers 110 (b, S) Bigint *b, *S; 111#else 112 (Bigint *b, Bigint *S) 113#endif 114{ 115 int n; 116 ULong *bx, *bxe, q, *sx, *sxe; 117#ifdef ULLong 118 ULLong borrow, carry, y, ys; 119#else 120 ULong borrow, carry, y, ys; 121#ifdef Pack_32 122 ULong si, z, zs; 123#endif 124#endif 125 126 n = S->wds; 127#ifdef DEBUG 128 /*debug*/ if (b->wds > n) 129 /*debug*/ Bug("oversize b in quorem"); 130#endif 131 if (b->wds < n) 132 return 0; 133 sx = S->x; 134 sxe = sx + --n; 135 bx = b->x; 136 bxe = bx + n; 137 q = *bxe / (*sxe + 1); /* ensure q <= true quotient */ 138#ifdef DEBUG 139 /*debug*/ if (q > 9) 140 /*debug*/ Bug("oversized quotient in quorem"); 141#endif 142 if (q) { 143 borrow = 0; 144 carry = 0; 145 do { 146#ifdef ULLong 147 ys = *sx++ * (ULLong)q + carry; 148 carry = ys >> 32; 149 /* LINTED conversion */ 150 y = *bx - (ys & 0xffffffffUL) - borrow; 151 borrow = y >> 32 & 1UL; 152 /* LINTED conversion */ 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 /* LINTED conversion */ 193 y = *bx - (ys & 0xffffffffUL) - borrow; 194 borrow = y >> 32 & 1UL; 195 /* LINTED conversion */ 196 *bx++ = y & 0xffffffffUL; 197#else 198#ifdef Pack_32 199 si = *sx++; 200 ys = (si & 0xffff) + carry; 201 zs = (si >> 16) + (ys >> 16); 202 carry = zs >> 16; 203 y = (*bx & 0xffff) - (ys & 0xffff) - borrow; 204 borrow = (y & 0x10000) >> 16; 205 z = (*bx >> 16) - (zs & 0xffff) - borrow; 206 borrow = (z & 0x10000) >> 16; 207 Storeinc(bx, z, y); 208#else 209 ys = *sx++ + carry; 210 carry = ys >> 16; 211 y = *bx - (ys & 0xffff) - borrow; 212 borrow = (y & 0x10000) >> 16; 213 *bx++ = y & 0xffff; 214#endif 215#endif 216 } 217 while(sx <= sxe); 218 bx = b->x; 219 bxe = bx + n; 220 if (!*bxe) { 221 while(--bxe > bx && !*bxe) 222 --n; 223 b->wds = n; 224 } 225 } 226 return q; 227 } 228