StdLib/LibC/gdtoa/dmisc.c

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