1/* $NetBSD: dmisc.c,v 1.3 2007/02/03 16:44:02 christos Exp $ */ 2 3/**************************************************************** 4 5The author of this software is David M. Gay. 6 7Copyright (C) 1998 by Lucent Technologies 8All Rights Reserved 9 10Permission to use, copy, modify, and distribute this software and 11its documentation for any purpose and without fee is hereby 12granted, provided that the above copyright notice appear in all 13copies and that both that the copyright notice and this 14permission notice and warranty disclaimer appear in supporting 15documentation, and that the name of Lucent or any of its entities 16not be used in advertising or publicity pertaining to 17distribution of the software without specific, written prior 18permission. 19 20LUCENT DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, 21INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. 22IN NO EVENT SHALL LUCENT OR ANY OF ITS ENTITIES BE LIABLE FOR ANY 23SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 24WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER 25IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, 26ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF 27THIS 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 42rv_alloc(i) size_t i; 43#else 44rv_alloc(size_t i) 45#endif 46{ 47 size_t j; 48 int k, *r; 49 50 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