1112158Sdas/**************************************************************** 2112158Sdas 3112158SdasThe author of this software is David M. Gay. 4112158Sdas 5112158SdasCopyright (C) 1998 by Lucent Technologies 6112158SdasAll Rights Reserved 7112158Sdas 8112158SdasPermission to use, copy, modify, and distribute this software and 9112158Sdasits documentation for any purpose and without fee is hereby 10112158Sdasgranted, provided that the above copyright notice appear in all 11112158Sdascopies and that both that the copyright notice and this 12112158Sdaspermission notice and warranty disclaimer appear in supporting 13112158Sdasdocumentation, and that the name of Lucent or any of its entities 14112158Sdasnot be used in advertising or publicity pertaining to 15112158Sdasdistribution of the software without specific, written prior 16112158Sdaspermission. 17112158Sdas 18112158SdasLUCENT DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, 19112158SdasINCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. 20112158SdasIN NO EVENT SHALL LUCENT OR ANY OF ITS ENTITIES BE LIABLE FOR ANY 21112158SdasSPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 22112158SdasWHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER 23112158SdasIN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, 24112158SdasARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF 25112158SdasTHIS SOFTWARE. 26112158Sdas 27112158Sdas****************************************************************/ 28112158Sdas 29165743Sdas/* Please send bug reports to David M. Gay (dmg at acm dot org, 30165743Sdas * with " at " changed at "@" and " dot " changed to "."). */ 31112158Sdas 32112158Sdas#include "gdtoaimp.h" 33112158Sdas 34112158Sdas#ifndef MULTIPLE_THREADS 35112158Sdas char *dtoa_result; 36112158Sdas#endif 37112158Sdas 38112158Sdas char * 39112158Sdas#ifdef KR_headers 40112158Sdasrv_alloc(i) int i; 41112158Sdas#else 42112158Sdasrv_alloc(int i) 43112158Sdas#endif 44112158Sdas{ 45112158Sdas int j, k, *r; 46112158Sdas 47112158Sdas j = sizeof(ULong); 48112158Sdas for(k = 0; 49112158Sdas sizeof(Bigint) - sizeof(ULong) - sizeof(int) + j <= i; 50112158Sdas j <<= 1) 51112158Sdas k++; 52112158Sdas r = (int*)Balloc(k); 53112158Sdas *r = k; 54112158Sdas return 55112158Sdas#ifndef MULTIPLE_THREADS 56112158Sdas dtoa_result = 57112158Sdas#endif 58112158Sdas (char *)(r+1); 59112158Sdas } 60112158Sdas 61112158Sdas char * 62112158Sdas#ifdef KR_headers 63112158Sdasnrv_alloc(s, rve, n) char *s, **rve; int n; 64112158Sdas#else 65112158Sdasnrv_alloc(char *s, char **rve, int n) 66112158Sdas#endif 67112158Sdas{ 68112158Sdas char *rv, *t; 69112158Sdas 70112158Sdas t = rv = rv_alloc(n); 71112158Sdas while((*t = *s++) !=0) 72112158Sdas t++; 73112158Sdas if (rve) 74112158Sdas *rve = t; 75112158Sdas return rv; 76112158Sdas } 77112158Sdas 78112158Sdas/* freedtoa(s) must be used to free values s returned by dtoa 79112158Sdas * when MULTIPLE_THREADS is #defined. It should be used in all cases, 80112158Sdas * but for consistency with earlier versions of dtoa, it is optional 81112158Sdas * when MULTIPLE_THREADS is not defined. 82112158Sdas */ 83112158Sdas 84112158Sdas void 85112158Sdas#ifdef KR_headers 86112158Sdasfreedtoa(s) char *s; 87112158Sdas#else 88112158Sdasfreedtoa(char *s) 89112158Sdas#endif 90112158Sdas{ 91112158Sdas Bigint *b = (Bigint *)((int *)s - 1); 92112158Sdas b->maxwds = 1 << (b->k = *(int*)b); 93112158Sdas Bfree(b); 94112158Sdas#ifndef MULTIPLE_THREADS 95112158Sdas if (s == dtoa_result) 96112158Sdas dtoa_result = 0; 97112158Sdas#endif 98112158Sdas } 99112158Sdas 100112158Sdas int 101112158Sdasquorem 102112158Sdas#ifdef KR_headers 103112158Sdas (b, S) Bigint *b, *S; 104112158Sdas#else 105112158Sdas (Bigint *b, Bigint *S) 106112158Sdas#endif 107112158Sdas{ 108112158Sdas int n; 109112158Sdas ULong *bx, *bxe, q, *sx, *sxe; 110112158Sdas#ifdef ULLong 111112158Sdas ULLong borrow, carry, y, ys; 112112158Sdas#else 113112158Sdas ULong borrow, carry, y, ys; 114112158Sdas#ifdef Pack_32 115112158Sdas ULong si, z, zs; 116112158Sdas#endif 117112158Sdas#endif 118112158Sdas 119112158Sdas n = S->wds; 120112158Sdas#ifdef DEBUG 121112158Sdas /*debug*/ if (b->wds > n) 122112158Sdas /*debug*/ Bug("oversize b in quorem"); 123112158Sdas#endif 124112158Sdas if (b->wds < n) 125112158Sdas return 0; 126112158Sdas sx = S->x; 127112158Sdas sxe = sx + --n; 128112158Sdas bx = b->x; 129112158Sdas bxe = bx + n; 130112158Sdas q = *bxe / (*sxe + 1); /* ensure q <= true quotient */ 131112158Sdas#ifdef DEBUG 132112158Sdas /*debug*/ if (q > 9) 133112158Sdas /*debug*/ Bug("oversized quotient in quorem"); 134112158Sdas#endif 135112158Sdas if (q) { 136112158Sdas borrow = 0; 137112158Sdas carry = 0; 138112158Sdas do { 139112158Sdas#ifdef ULLong 140112158Sdas ys = *sx++ * (ULLong)q + carry; 141112158Sdas carry = ys >> 32; 142112158Sdas y = *bx - (ys & 0xffffffffUL) - borrow; 143112158Sdas borrow = y >> 32 & 1UL; 144112158Sdas *bx++ = y & 0xffffffffUL; 145112158Sdas#else 146112158Sdas#ifdef Pack_32 147112158Sdas si = *sx++; 148112158Sdas ys = (si & 0xffff) * q + carry; 149112158Sdas zs = (si >> 16) * q + (ys >> 16); 150112158Sdas carry = zs >> 16; 151112158Sdas y = (*bx & 0xffff) - (ys & 0xffff) - borrow; 152112158Sdas borrow = (y & 0x10000) >> 16; 153112158Sdas z = (*bx >> 16) - (zs & 0xffff) - borrow; 154112158Sdas borrow = (z & 0x10000) >> 16; 155112158Sdas Storeinc(bx, z, y); 156112158Sdas#else 157112158Sdas ys = *sx++ * q + carry; 158112158Sdas carry = ys >> 16; 159112158Sdas y = *bx - (ys & 0xffff) - borrow; 160112158Sdas borrow = (y & 0x10000) >> 16; 161112158Sdas *bx++ = y & 0xffff; 162112158Sdas#endif 163112158Sdas#endif 164112158Sdas } 165112158Sdas while(sx <= sxe); 166112158Sdas if (!*bxe) { 167112158Sdas bx = b->x; 168112158Sdas while(--bxe > bx && !*bxe) 169112158Sdas --n; 170112158Sdas b->wds = n; 171112158Sdas } 172112158Sdas } 173112158Sdas if (cmp(b, S) >= 0) { 174112158Sdas q++; 175112158Sdas borrow = 0; 176112158Sdas carry = 0; 177112158Sdas bx = b->x; 178112158Sdas sx = S->x; 179112158Sdas do { 180112158Sdas#ifdef ULLong 181112158Sdas ys = *sx++ + carry; 182112158Sdas carry = ys >> 32; 183112158Sdas y = *bx - (ys & 0xffffffffUL) - borrow; 184112158Sdas borrow = y >> 32 & 1UL; 185112158Sdas *bx++ = y & 0xffffffffUL; 186112158Sdas#else 187112158Sdas#ifdef Pack_32 188112158Sdas si = *sx++; 189112158Sdas ys = (si & 0xffff) + carry; 190112158Sdas zs = (si >> 16) + (ys >> 16); 191112158Sdas carry = zs >> 16; 192112158Sdas y = (*bx & 0xffff) - (ys & 0xffff) - borrow; 193112158Sdas borrow = (y & 0x10000) >> 16; 194112158Sdas z = (*bx >> 16) - (zs & 0xffff) - borrow; 195112158Sdas borrow = (z & 0x10000) >> 16; 196112158Sdas Storeinc(bx, z, y); 197112158Sdas#else 198112158Sdas ys = *sx++ + carry; 199112158Sdas carry = ys >> 16; 200112158Sdas y = *bx - (ys & 0xffff) - borrow; 201112158Sdas borrow = (y & 0x10000) >> 16; 202112158Sdas *bx++ = y & 0xffff; 203112158Sdas#endif 204112158Sdas#endif 205112158Sdas } 206112158Sdas while(sx <= sxe); 207112158Sdas bx = b->x; 208112158Sdas bxe = bx + n; 209112158Sdas if (!*bxe) { 210112158Sdas while(--bxe > bx && !*bxe) 211112158Sdas --n; 212112158Sdas b->wds = n; 213112158Sdas } 214112158Sdas } 215112158Sdas return q; 216112158Sdas } 217