home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / gnu / djgpp / src / libgplus.5 / libio / floatcon.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-10-12  |  70.9 KB  |  2,332 lines
  1. /* 
  2. Copyright (C) 1993 Free Software Foundation
  3.  
  4. This file is part of the GNU IO Library.  This library is free
  5. software; you can redistribute it and/or modify it under the
  6. terms of the GNU General Public License as published by the
  7. Free Software Foundation; either version 2, or (at your option)
  8. any later version.
  9.  
  10. This library is distributed in the hope that it will be useful,
  11. but WITHOUT ANY WARRANTY; without even the implied warranty of
  12. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13. GNU General Public License for more details.
  14.  
  15. You should have received a copy of the GNU General Public License
  16. along with GNU CC; see the file COPYING.  If not, write to
  17. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
  18.  
  19. As a special exception, if you link this library with files
  20. compiled with a GNU compiler to produce an executable, this does not cause
  21. the resulting executable to be covered by the GNU General Public License.
  22. This exception does not however invalidate any other reasons why
  23. the executable file might be covered by the GNU General Public License. */
  24.  
  25. #include <libioP.h>
  26. #ifdef USE_DTOA
  27. /****************************************************************
  28.  *
  29.  * The author of this software is David M. Gay.
  30.  *
  31.  * Copyright (c) 1991 by AT&T.
  32.  *
  33.  * Permission to use, copy, modify, and distribute this software for any
  34.  * purpose without fee is hereby granted, provided that this entire notice
  35.  * is included in all copies of any software which is or includes a copy
  36.  * or modification of this software and in all copies of the supporting
  37.  * documentation for such software.
  38.  *
  39.  * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
  40.  * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHOR NOR AT&T MAKES ANY
  41.  * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
  42.  * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
  43.  *
  44.  ***************************************************************/
  45.  
  46. /* Some cleaning up by Per Bothner, bothner@cygnus.com, 1992, 1993.
  47.    Re-written to not need static variables
  48.    (except result, result_k, HIWORD, LOWORD). */
  49.  
  50. /* Please send bug reports to
  51.         David M. Gay
  52.         AT&T Bell Laboratories, Room 2C-463
  53.         600 Mountain Avenue
  54.         Murray Hill, NJ 07974-2070
  55.         U.S.A.
  56.         dmg@research.att.com or research!dmg
  57.  */
  58.  
  59. /* strtod for IEEE-, VAX-, and IBM-arithmetic machines.
  60.  *
  61.  * This strtod returns a nearest machine number to the input decimal
  62.  * string (or sets errno to ERANGE).  With IEEE arithmetic, ties are
  63.  * broken by the IEEE round-even rule.  Otherwise ties are broken by
  64.  * biased rounding (add half and chop).
  65.  *
  66.  * Inspired loosely by William D. Clinger's paper "How to Read Floating
  67.  * Point Numbers Accurately" [Proc. ACM SIGPLAN '90, pp. 92-101].
  68.  *
  69.  * Modifications:
  70.  *
  71.  *      1. We only require IEEE, IBM, or VAX double-precision
  72.  *              arithmetic (not IEEE double-extended).
  73.  *      2. We get by with floating-point arithmetic in a case that
  74.  *              Clinger missed -- when we're computing d * 10^n
  75.  *              for a small integer d and the integer n is not too
  76.  *              much larger than 22 (the maximum integer k for which
  77.  *              we can represent 10^k exactly), we may be able to
  78.  *              compute (d*10^k) * 10^(e-k) with just one roundoff.
  79.  *      3. Rather than a bit-at-a-time adjustment of the binary
  80.  *              result in the hard case, we use floating-point
  81.  *              arithmetic to determine the adjustment to within
  82.  *              one bit; only in really hard cases do we need to
  83.  *              compute a second residual.
  84.  *      4. Because of 3., we don't need a large table of powers of 10
  85.  *              for ten-to-e (just some small tables, e.g. of 10^k
  86.  *              for 0 <= k <= 22).
  87.  */
  88.  
  89. /*
  90.  * #define IEEE_8087 for IEEE-arithmetic machines where the least
  91.  *      significant byte has the lowest address.
  92.  * #define IEEE_MC68k for IEEE-arithmetic machines where the most
  93.  *      significant byte has the lowest address.
  94.  * #define Sudden_Underflow for IEEE-format machines without gradual
  95.  *      underflow (i.e., that flush to zero on underflow).
  96.  * #define IBM for IBM mainframe-style floating-point arithmetic.
  97.  * #define VAX for VAX-style floating-point arithmetic.
  98.  * #define Unsigned_Shifts if >> does treats its left operand as unsigned.
  99.  * #define No_leftright to omit left-right logic in fast floating-point
  100.  *      computation of dtoa.
  101.  * #define Check_FLT_ROUNDS if FLT_ROUNDS can assume the values 2 or 3.
  102.  * #define RND_PRODQUOT to use rnd_prod and rnd_quot (assembly routines
  103.  *      that use extended-precision instructions to compute rounded
  104.  *      products and quotients) with IBM.
  105.  * #define ROUND_BIASED for IEEE-format with biased rounding.
  106.  * #define Inaccurate_Divide for IEEE-format with correctly rounded
  107.  *      products but inaccurate quotients, e.g., for Intel i860.
  108.  * #define KR_headers for old-style C function headers.
  109.  */
  110.  
  111. #ifdef DEBUG
  112. #include <stdio.h>
  113. #define Bug(x) {fprintf(stderr, "%s\n", x); exit(1);}
  114. #endif
  115.  
  116. #ifdef __STDC__
  117. #include <stdlib.h>
  118. #include <string.h>
  119. #include <float.h>
  120. #define CONST const
  121. #else
  122. #define CONST
  123. #define KR_headers
  124.  
  125. /* In this case, we assume IEEE floats. */
  126. #define FLT_ROUNDS 1
  127. #define FLT_RADIX 2
  128. #define DBL_DIG 15
  129. #define DBL_MAX_10_EXP (-307)
  130. #define DBL_MAX_EXP 1024
  131. #endif
  132.  
  133. #include <errno.h>
  134. #ifndef __MATH_H__
  135. #include <math.h>
  136. #endif
  137.  
  138. #ifdef Unsigned_Shifts
  139. #define Sign_Extend(a,b) if (b < 0) a |= 0xffff0000;
  140. #else
  141. #define Sign_Extend(a,b) /*no-op*/
  142. #endif
  143.  
  144. #if defined(__i386__) || defined(clipper) || defined(MIPSEL)
  145. #define IEEE_8087
  146. #endif
  147.  
  148. #if defined(__sparc__) || defined(sparc) || defined(MIPSEB)
  149. #define IEEE_MC68k
  150. #endif
  151.  
  152. #if defined(IEEE_8087) + defined(IEEE_MC68k) + defined(VAX) + defined(IBM) != 1
  153.  
  154. #if FLT_RADIX==16
  155. #define IBM
  156. #elif DBL_MANT_DIG==56
  157. #define VAX
  158. #elif DBL_MANT_DIG==53 && DBL_MAX_10_EXP==308
  159. #define IEEE_Unknown
  160. #else
  161. Exactly one of IEEE_8087, IEEE_MC68k, VAX, or IBM should be defined.
  162. #endif
  163. #endif
  164.  
  165. #ifdef IEEE_8087
  166. #define HIWORD 1
  167. #define LOWORD 0
  168. #define TEST_ENDIANNESS  /* nothing */
  169. #elif defined(IEEE_MC68k)
  170. #define HIWORD 0
  171. #define LOWORD 1
  172. #define TEST_ENDIANNESS  /* nothing */
  173. #else
  174. static int HIWORD = -1, LOWORD;
  175. static void test_endianness()
  176. {
  177.     union doubleword {
  178.     double d;
  179.     unsigned long u[2];
  180.     } dw;
  181.     dw.d = 10;
  182.     if (dw.u[0] != 0) /* big-endian */
  183.     HIWORD=0, LOWORD=1;
  184.     else
  185.     HIWORD=1, LOWORD=0;
  186. }
  187. #define TEST_ENDIANNESS  if (HIWORD<0) test_endianness();
  188. #endif
  189. #if 0
  190. union {
  191.   double d;
  192.   unsigned long x[2];
  193. } _temp;
  194. #endif
  195. #define word0(x) ((unsigned long *)&x)[HIWORD]
  196. #if 0
  197. #define word0(X) (_temp.d = X, _temp.x[HIWORD])
  198. #define setword0(D,X) (_temp.d = D, _temp.x[HIWORD] = X, D = _temp.d)
  199. #endif
  200. #define word1(x) ((unsigned long *)&x)[LOWORD]
  201.  
  202. /* The following definition of Storeinc is appropriate for MIPS processors. */
  203. #if defined(IEEE_8087) + defined(VAX)
  204. #define Storeinc(a,b,c) (((unsigned short *)a)[1] = (unsigned short)b, \
  205. ((unsigned short *)a)[0] = (unsigned short)c, a++)
  206. #elif defined(IEEE_MC68k)
  207. #define Storeinc(a,b,c) (((unsigned short *)a)[0] = (unsigned short)b, \
  208. ((unsigned short *)a)[1] = (unsigned short)c, a++)
  209. #else
  210. #define Storeinc(a,b,c) (*a++ = b << 16 | c & 0xffff)
  211. #endif
  212.  
  213. /* #define P DBL_MANT_DIG */
  214. /* Ten_pmax = floor(P*log(2)/log(5)) */
  215. /* Bletch = (highest power of 2 < DBL_MAX_10_EXP) / 16 */
  216. /* Quick_max = floor((P-1)*log(FLT_RADIX)/log(10) - 1) */
  217. /* Int_max = floor(P*log(FLT_RADIX)/log(10) - 1) */
  218.  
  219. #if defined(IEEE_8087) + defined(IEEE_MC68k) + defined(IEEE_Unknown)
  220. #define Exp_shift  20
  221. #define Exp_shift1 20
  222. #define Exp_msk1    0x100000
  223. #define Exp_msk11   0x100000
  224. #define Exp_mask  0x7ff00000
  225. #define P 53
  226. #define Bias 1023
  227. #define IEEE_Arith
  228. #define Emin (-1022)
  229. #define Exp_1  0x3ff00000
  230. #define Exp_11 0x3ff00000
  231. #define Ebits 11
  232. #define Frac_mask  0xfffff
  233. #define Frac_mask1 0xfffff
  234. #define Ten_pmax 22
  235. #define Bletch 0x10
  236. #define Bndry_mask  0xfffff
  237. #define Bndry_mask1 0xfffff
  238. #define LSB 1
  239. #define Sign_bit 0x80000000
  240. #define Log2P 1
  241. #define Tiny0 0
  242. #define Tiny1 1
  243. #define Quick_max 14
  244. #define Int_max 14
  245. #define Infinite(x) (word0(x) == 0x7ff00000) /* sufficient test for here */
  246. #else
  247. #undef  Sudden_Underflow
  248. #define Sudden_Underflow
  249. #ifdef IBM
  250. #define Exp_shift  24
  251. #define Exp_shift1 24
  252. #define Exp_msk1   0x1000000
  253. #define Exp_msk11  0x1000000
  254. #define Exp_mask  0x7f000000
  255. #define P 14
  256. #define Bias 65
  257. #define Exp_1  0x41000000
  258. #define Exp_11 0x41000000
  259. #define Ebits 8 /* exponent has 7 bits, but 8 is the right value in b2d */
  260. #define Frac_mask  0xffffff
  261. #define Frac_mask1 0xffffff
  262. #define Bletch 4
  263. #define Ten_pmax 22
  264. #define Bndry_mask  0xefffff
  265. #define Bndry_mask1 0xffffff
  266. #define LSB 1
  267. #define Sign_bit 0x80000000
  268. #define Log2P 4
  269. #define Tiny0 0x100000
  270. #define Tiny1 0
  271. #define Quick_max 14
  272. #define Int_max 15
  273. #else /* VAX */
  274. #define Exp_shift  23
  275. #define Exp_shift1 7
  276. #define Exp_msk1    0x80
  277. #define Exp_msk11   0x800000
  278. #define Exp_mask  0x7f80
  279. #define P 56
  280. #define Bias 129
  281. #define Exp_1  0x40800000
  282. #define Exp_11 0x4080
  283. #define Ebits 8
  284. #define Frac_mask  0x7fffff
  285. #define Frac_mask1 0xffff007f
  286. #define Ten_pmax 24
  287. #define Bletch 2
  288. #define Bndry_mask  0xffff007f
  289. #define Bndry_mask1 0xffff007f
  290. #define LSB 0x10000
  291. #define Sign_bit 0x8000
  292. #define Log2P 1
  293. #define Tiny0 0x80
  294. #define Tiny1 0
  295. #define Quick_max 15
  296. #define Int_max 15
  297. #endif
  298. #endif
  299.  
  300. #ifndef IEEE_Arith
  301. #define ROUND_BIASED
  302. #endif
  303.  
  304. #ifdef RND_PRODQUOT
  305. #define rounded_product(a,b) a = rnd_prod(a, b)
  306. #define rounded_quotient(a,b) a = rnd_quot(a, b)
  307. extern double rnd_prod(double, double), rnd_quot(double, double);
  308. #else
  309. #define rounded_product(a,b) a *= b
  310. #define rounded_quotient(a,b) a /= b
  311. #endif
  312.  
  313. #define Big0 (Frac_mask1 | Exp_msk1*(DBL_MAX_EXP+Bias-1))
  314. #define Big1 0xffffffff
  315.  
  316. #define Kmax 15
  317.  
  318. /* (1<<BIGINT_MINIMUM_K) is the minimum number of words to allocate
  319.    in a Bigint.  dtoa usually manages with 1<<2, and has not been
  320.    known to need more than 1<<3.  */
  321.  
  322. #define BIGINT_MINIMUM_K 3
  323.  
  324. struct Bigint {
  325.   struct Bigint *next;
  326.   int k;        /* Parameter given to Balloc(k) */
  327.   int maxwds;        /* Allocated space: equals 1<<k. */
  328.   short on_stack;    /* 1 if stack-allocated. */
  329.   short sign;        /* 0 if value is positive or zero; 1 if negative. */
  330.   int wds;        /* Current length. */
  331.   unsigned long x[1<<BIGINT_MINIMUM_K]; /* Actually: x[maxwds] */
  332. };
  333.  
  334. #define BIGINT_HEADER_SIZE \
  335.   (sizeof(Bigint) - (1<<BIGINT_MINIMUM_K) * sizeof(unsigned long))
  336.  
  337. typedef struct Bigint Bigint;
  338.  
  339. /* Initialize a stack-allocated Bigint. */
  340.  
  341. Bigint *
  342. Binit
  343. #ifdef KR_headers
  344.         (v) Bigint *v;
  345. #else
  346.         (Bigint *v)
  347. #endif
  348. {
  349.   v->on_stack = 1;
  350.   v->k = BIGINT_MINIMUM_K;
  351.   v->maxwds = 1 << BIGINT_MINIMUM_K;
  352.   v->sign = v->wds = 0;
  353.   return v;
  354. }
  355.  
  356. /* Allocate a Bigint with '1<<k' big digits. */
  357.  
  358. static Bigint *
  359. Balloc
  360. #ifdef KR_headers
  361.         (k) int k;
  362. #else
  363.         (int k)
  364. #endif
  365. {
  366.   int x;
  367.   Bigint *rv;
  368.  
  369.   if (k < BIGINT_MINIMUM_K)
  370.     k = BIGINT_MINIMUM_K;
  371.  
  372.   x = 1 << k;
  373.   rv = (Bigint *)
  374.     malloc(BIGINT_HEADER_SIZE + x * sizeof(unsigned long));
  375.   rv->k = k;
  376.   rv->maxwds = x;
  377.   rv->sign = rv->wds = 0;
  378.   rv->on_stack = 0;
  379.   return rv;
  380. }
  381.  
  382. static void
  383. Bfree
  384. #ifdef KR_headers
  385.         (v) Bigint *v;
  386. #else
  387.         (Bigint *v)
  388. #endif
  389. {
  390.   if (v && !v->on_stack)
  391.     free (v);
  392. }
  393.  
  394. static void
  395. Bcopy
  396. #ifdef KR_headers
  397.         (x, y) Bigint *x, *y;
  398. #else
  399.         (Bigint *x, Bigint *y)
  400. #endif
  401. {
  402.   register unsigned long *xp, *yp;
  403.   register int i = y->wds;
  404.   x->sign = y->sign;
  405.   x->wds = i;
  406.   for (xp = x->x, yp = y->x; --i >= 0; )
  407.     *xp++ = *yp++;
  408. }
  409.  
  410. /* Make sure b has room for at least 1<<k big digits. */
  411.  
  412. static Bigint *
  413. Brealloc
  414. #ifdef KR_headers
  415.         (b, k) Bigint *b; int k;
  416. #else
  417.         (Bigint * b, int k)
  418. #endif
  419. {
  420.   if (b == NULL)
  421.     return Balloc(k);
  422.   if (b->k >= k)
  423.     return b;
  424.   else
  425.     {
  426.       Bigint *rv = Balloc (k);
  427.       Bcopy(rv, b);
  428.       Bfree(b);
  429.       return rv;
  430.     }
  431. }
  432.  
  433. /* Return b*m+a.  b is modified.
  434.    Assumption:  0xFFFF*m+a fits in 32 bits. */
  435.  
  436. static Bigint *
  437. multadd
  438. #ifdef KR_headers
  439.         (b, m, a) Bigint *b; int m, a;
  440. #else
  441.         (Bigint *b, int m, int a)
  442. #endif
  443. {
  444.         int i, wds;
  445.         unsigned long *x, y;
  446.         unsigned long xi, z;
  447.  
  448.         wds = b->wds;
  449.         x = b->x;
  450.         i = 0;
  451.         do {
  452.                 xi = *x;
  453.                 y = (xi & 0xffff) * m + a;
  454.                 z = (xi >> 16) * m + (y >> 16);
  455.                 a = (int)(z >> 16);
  456.                 *x++ = (z << 16) + (y & 0xffff);
  457.                 }
  458.                 while(++i < wds);
  459.         if (a) {
  460.                 if (wds >= b->maxwds)
  461.                         b = Brealloc(b, b->k+1);
  462.                 b->x[wds++] = a;
  463.                 b->wds = wds;
  464.                 }
  465.         return b;
  466.         }
  467.  
  468. static Bigint *
  469. s2b
  470. #ifdef KR_headers
  471.         (result, s, nd0, nd, y9)
  472.     Bigint *result; CONST char *s; int nd0, nd; unsigned long y9;
  473. #else
  474.         (Bigint *result, CONST char *s, int nd0, int nd, unsigned long y9)
  475. #endif
  476. {
  477.   int i, k;
  478.   long x, y;
  479.  
  480.   x = (nd + 8) / 9;
  481.   for(k = 0, y = 1; x > y; y <<= 1, k++) ;
  482.   result = Brealloc(result, k);
  483.   result->x[0] = y9;
  484.   result->wds = 1;
  485.  
  486.   i = 9;
  487.   if (9 < nd0)
  488.     {
  489.       s += 9;
  490.       do
  491.     result = multadd(result, 10, *s++ - '0');
  492.       while (++i < nd0);
  493.       s++;
  494.     }
  495.   else
  496.     s += 10;
  497.   for(; i < nd; i++)
  498.     result = multadd(result, 10, *s++ - '0');
  499.   return result;
  500. }
  501.  
  502. static int
  503. hi0bits
  504. #ifdef KR_headers
  505.         (x) register unsigned long x;
  506. #else
  507.         (register unsigned long x)
  508. #endif
  509. {
  510.         register int k = 0;
  511.  
  512.         if (!(x & 0xffff0000)) {
  513.                 k = 16;
  514.                 x <<= 16;
  515.                 }
  516.         if (!(x & 0xff000000)) {
  517.                 k += 8;
  518.                 x <<= 8;
  519.                 }
  520.         if (!(x & 0xf0000000)) {
  521.                 k += 4;
  522.                 x <<= 4;
  523.                 }
  524.         if (!(x & 0xc0000000)) {
  525.                 k += 2;
  526.                 x <<= 2;
  527.                 }
  528.         if (!(x & 0x80000000)) {
  529.                 k++;
  530.                 if (!(x & 0x40000000))
  531.                         return 32;
  532.                 }
  533.         return k;
  534.         }
  535.  
  536. static int
  537. lo0bits
  538. #ifdef KR_headers
  539.         (y) unsigned long *y;
  540. #else
  541.         (unsigned long *y)
  542. #endif
  543. {
  544.         register int k;
  545.         register unsigned long x = *y;
  546.  
  547.         if (x & 7) {
  548.                 if (x & 1)
  549.                         return 0;
  550.                 if (x & 2) {
  551.                         *y = x >> 1;
  552.                         return 1;
  553.                         }
  554.                 *y = x >> 2;
  555.                 return 2;
  556.                 }
  557.         k = 0;
  558.         if (!(x & 0xffff)) {
  559.                 k = 16;
  560.                 x >>= 16;
  561.                 }
  562.         if (!(x & 0xff)) {
  563.                 k += 8;
  564.                 x >>= 8;
  565.                 }
  566.         if (!(x & 0xf)) {
  567.                 k += 4;
  568.                 x >>= 4;
  569.                 }
  570.         if (!(x & 0x3)) {
  571.                 k += 2;
  572.                 x >>= 2;
  573.                 }
  574.         if (!(x & 1)) {
  575.                 k++;
  576.                 x >>= 1;
  577.                 if (!x & 1)
  578.                         return 32;
  579.                 }
  580.         *y = x;
  581.         return k;
  582.         }
  583.  
  584. static Bigint *
  585. i2b
  586. #ifdef KR_headers
  587.         (result, i) Bigint *result; int i;
  588. #else
  589.         (Bigint* result, int i)
  590. #endif
  591. {
  592.   result = Brealloc(result, 1);
  593.   result->x[0] = i;
  594.   result->wds = 1;
  595.   return result;
  596. }
  597.  
  598. /* Do: c = a * b. */
  599.  
  600. static Bigint *
  601. mult
  602. #ifdef KR_headers
  603.         (c, a, b) Bigint *a, *b, *c;
  604. #else
  605.         (Bigint *c, Bigint *a, Bigint *b)
  606. #endif
  607. {
  608.         int k, wa, wb, wc;
  609.         unsigned long carry, y, z;
  610.         unsigned long *x, *xa, *xae, *xb, *xbe, *xc, *xc0;
  611.         unsigned long z2;
  612.         if (a->wds < b->wds) {
  613.                 Bigint *tmp = a;
  614.                 a = b;
  615.                 b = tmp;
  616.                 }
  617.         k = a->k;
  618.         wa = a->wds;
  619.         wb = b->wds;
  620.         wc = wa + wb;
  621.         if (wc > a->maxwds)
  622.                 k++;
  623.     c = Brealloc(c, k);
  624.         for(x = c->x, xa = x + wc; x < xa; x++)
  625.                 *x = 0;
  626.         xa = a->x;
  627.         xae = xa + wa;
  628.         xb = b->x;
  629.         xbe = xb + wb;
  630.         xc0 = c->x;
  631.         for(; xb < xbe; xb++, xc0++) {
  632.                 if (y = *xb & 0xffff) {
  633.                         x = xa;
  634.                         xc = xc0;
  635.                         carry = 0;
  636.                         do {
  637.                                 z = (*x & 0xffff) * y + (*xc & 0xffff) + carry;
  638.                                 carry = z >> 16;
  639.                                 z2 = (*x++ >> 16) * y + (*xc >> 16) + carry;
  640.                                 carry = z2 >> 16;
  641.                                 Storeinc(xc, z2, z);
  642.                                 }
  643.                                 while(x < xae);
  644.                         *xc = carry;
  645.                         }
  646.                 if (y = *xb >> 16) {
  647.                         x = xa;
  648.                         xc = xc0;
  649.                         carry = 0;
  650.                         z2 = *xc;
  651.                         do {
  652.                                 z = (*x & 0xffff) * y + (*xc >> 16) + carry;
  653.                                 carry = z >> 16;
  654.                                 Storeinc(xc, z, z2);
  655.                                 z2 = (*x++ >> 16) * y + (*xc & 0xffff) + carry;
  656.                                 carry = z2 >> 16;
  657.                                 }
  658.                                 while(x < xae);
  659.                         *xc = z2;
  660.                         }
  661.                 }
  662.         for(xc0 = c->x, xc = xc0 + wc; wc > 0 && !*--xc; --wc) ;
  663.         c->wds = wc;
  664.         return c;
  665.         }
  666.  
  667. /* Returns b*(5**k).  b is modified. */
  668. /* Re-written by Per Bothner to not need a static list. */
  669.  
  670. static Bigint *
  671. pow5mult
  672. #ifdef KR_headers
  673.         (b, k) Bigint *b; int k;
  674. #else
  675.         (Bigint *b, int k)
  676. #endif
  677. {
  678.   static int p05[6] = { 5, 25, 125, 625, 3125, 15625 };
  679.  
  680.   for (; k > 6; k -= 6)
  681.     b = multadd(b, 15625, 0); /* b *= 5**6 */
  682.   if (k == 0)
  683.     return b;
  684.   else
  685.     return multadd(b, p05[k-1], 0);
  686. }
  687.  
  688. /* Re-written by Per Bothner so shift can be in place. */
  689.  
  690. static Bigint *
  691. lshift
  692. #ifdef KR_headers
  693.     (b, k) Bigint *b; int k;
  694. #else
  695.         (Bigint *b, int k)
  696. #endif
  697. {
  698.   int i;
  699.   unsigned long *x, *x1, *xe;
  700.   int old_wds = b->wds;
  701.   int n = k >> 5;
  702.   int k1 = b->k;
  703.   int n1 = n + old_wds + 1;
  704.  
  705.   if (k == 0)
  706.     return b;
  707.  
  708.   for(i = b->maxwds; n1 > i; i <<= 1)
  709.     k1++;
  710.   b = Brealloc(b, k1);
  711.  
  712.   xe = b->x; /* Source limit */
  713.   x = xe + old_wds; /* Source pointer */
  714.   x1 = x + n; /* Destination pointer */
  715.   if (k &= 0x1f) {
  716.     int k1 = 32 - k;
  717.     unsigned long z = *--x;
  718.     if ((*x1 = (z >> k1)) != 0) {
  719.       ++n1;
  720.     }
  721.     while (x > xe) {
  722.       unsigned long w = *--x;
  723.       *--x1 = (z << k) | (w >> k1);
  724.       z = w;
  725.     }
  726.     *--x1 = z << k;
  727.   }
  728.   else
  729.     do {
  730.       *--x1 = *--x;
  731.     } while(x > xe);
  732.   while (x1 > xe)
  733.     *--x1 = 0;
  734.   b->wds = n1 - 1;
  735.   return b;
  736. }
  737.  
  738. static int
  739. cmp
  740. #ifdef KR_headers
  741.         (a, b) Bigint *a, *b;
  742. #else
  743.         (Bigint *a, Bigint *b)
  744. #endif
  745. {
  746.         unsigned long *xa, *xa0, *xb, *xb0;
  747.         int i, j;
  748.  
  749.         i = a->wds;
  750.         j = b->wds;
  751. #ifdef DEBUG
  752.         if (i > 1 && !a->x[i-1])
  753.                 Bug("cmp called with a->x[a->wds-1] == 0");
  754.         if (j > 1 && !b->x[j-1])
  755.                 Bug("cmp called with b->x[b->wds-1] == 0");
  756. #endif
  757.         if (i -= j)
  758.                 return i;
  759.         xa0 = a->x;
  760.         xa = xa0 + j;
  761.         xb0 = b->x;
  762.         xb = xb0 + j;
  763.         for(;;) {
  764.                 if (*--xa != *--xb)
  765.                         return *xa < *xb ? -1 : 1;
  766.                 if (xa <= xa0)
  767.                         break;
  768.                 }
  769.         return 0;
  770.         }
  771.  
  772. /* Do: c = a-b. */
  773.  
  774. static Bigint *
  775. diff
  776. #ifdef KR_headers
  777.         (c, a, b) Bigint *c, *a, *b;
  778. #else
  779.         (Bigint *c, Bigint *a, Bigint *b)
  780. #endif
  781. {
  782.         int i, wa, wb;
  783.         long borrow, y; /* We need signed shifts here. */
  784.         unsigned long *xa, *xae, *xb, *xbe, *xc;
  785.         long z;
  786.  
  787.         i = cmp(a,b);
  788.         if (!i) {
  789.                 c = Brealloc(c, 0);
  790.                 c->wds = 1;
  791.                 c->x[0] = 0;
  792.                 return c;
  793.                 }
  794.         if (i < 0) {
  795.                 Bigint *tmp = a;
  796.                 a = b;
  797.                 b = tmp;
  798.                 i = 1;
  799.                 }
  800.         else
  801.                 i = 0;
  802.         c = Brealloc(c, a->k);
  803.         c->sign = i;
  804.         wa = a->wds;
  805.         xa = a->x;
  806.         xae = xa + wa;
  807.         wb = b->wds;
  808.         xb = b->x;
  809.         xbe = xb + wb;
  810.         xc = c->x;
  811.         borrow = 0;
  812.         do {
  813.                 y = (*xa & 0xffff) - (*xb & 0xffff) + borrow;
  814.                 borrow = y >> 16;
  815.                 Sign_Extend(borrow, y);
  816.                 z = (*xa++ >> 16) - (*xb++ >> 16) + borrow;
  817.                 borrow = z >> 16;
  818.                 Sign_Extend(borrow, z);
  819.                 Storeinc(xc, z, y);
  820.                 }
  821.                 while(xb < xbe);
  822.         while(xa < xae) {
  823.                 y = (*xa & 0xffff) + borrow;
  824.                 borrow = y >> 16;
  825.                 Sign_Extend(borrow, y);
  826.                 z = (*xa++ >> 16) + borrow;
  827.                 borrow = z >> 16;
  828.                 Sign_Extend(borrow, z);
  829.                 Storeinc(xc, z, y);
  830.                 }
  831.         while(!*--xc)
  832.                 wa--;
  833.         c->wds = wa;
  834.         return c;
  835.         }
  836.  
  837. static double
  838. ulp
  839. #ifdef KR_headers
  840.         (x) double x;
  841. #else
  842.         (double x)
  843. #endif
  844. {
  845.         register long L;
  846.         double a;
  847.  
  848.         L = (word0(x) & Exp_mask) - (P-1)*Exp_msk1;
  849. #ifndef Sudden_Underflow
  850.         if (L > 0) {
  851. #endif
  852. #ifdef IBM
  853.                 L |= Exp_msk1 >> 4;
  854. #endif
  855.                 word0(a) = L;
  856.                 word1(a) = 0;
  857. #ifndef Sudden_Underflow
  858.                 }
  859.         else {
  860.                 L = -L >> Exp_shift;
  861.                 if (L < Exp_shift) {
  862.                         word0(a) = 0x80000 >> L;
  863.                         word1(a) = 0;
  864.                         }
  865.                 else {
  866.                         word0(a) = 0;
  867.                         L -= Exp_shift;
  868.                         word1(a) = L >= 31 ? 1 : 1 << 31 - L;
  869.                         }
  870.                 }
  871. #endif
  872.         return a;
  873.         }
  874.  
  875. static double
  876. b2d
  877. #ifdef KR_headers
  878.         (a, e) Bigint *a; int *e;
  879. #else
  880.         (Bigint *a, int *e)
  881. #endif
  882. {
  883.         unsigned long *xa, *xa0, w, y, z;
  884.         int k;
  885.         double d;
  886. #ifdef VAX
  887.         unsigned long d0, d1;
  888. #else
  889. #define d0 word0(d)
  890. #define d1 word1(d)
  891. #endif
  892.  
  893.         xa0 = a->x;
  894.         xa = xa0 + a->wds;
  895.         y = *--xa;
  896. #ifdef DEBUG
  897.         if (!y) Bug("zero y in b2d");
  898. #endif
  899.         k = hi0bits(y);
  900.         *e = 32 - k;
  901.         if (k < Ebits) {
  902.                 d0 = Exp_1 | y >> Ebits - k;
  903.                 w = xa > xa0 ? *--xa : 0;
  904.                 d1 = y << (32-Ebits) + k | w >> Ebits - k;
  905.                 goto ret_d;
  906.                 }
  907.         z = xa > xa0 ? *--xa : 0;
  908.         if (k -= Ebits) {
  909.                 d0 = Exp_1 | y << k | z >> 32 - k;
  910.                 y = xa > xa0 ? *--xa : 0;
  911.                 d1 = z << k | y >> 32 - k;
  912.                 }
  913.         else {
  914.                 d0 = Exp_1 | y;
  915.                 d1 = z;
  916.                 }
  917.  ret_d:
  918. #ifdef VAX
  919.         word0(d) = d0 >> 16 | d0 << 16;
  920.         word1(d) = d1 >> 16 | d1 << 16;
  921. #else
  922. #undef d0
  923. #undef d1
  924. #endif
  925.         return d;
  926.         }
  927.  
  928. static Bigint *
  929. d2b
  930. #ifdef KR_headers
  931.         (result, d, e, bits) Bigint *result; double d; int *e, *bits;
  932. #else
  933.         (Bigint *result, double d, int *e, int *bits)
  934. #endif
  935. {
  936.         int de, i, k;
  937.         unsigned long *x, y, z;
  938. #ifdef VAX
  939.         unsigned long d0, d1;
  940.         d0 = word0(d) >> 16 | word0(d) << 16;
  941.         d1 = word1(d) >> 16 | word1(d) << 16;
  942. #else
  943. #define d0 word0(d)
  944. #define d1 word1(d)
  945. #endif
  946.  
  947.         result = Brealloc(result, 1);
  948.         x = result->x;
  949.  
  950.         z = d0 & Frac_mask;
  951.         d0 &= 0x7fffffff;       /* clear sign bit, which we ignore */
  952.  
  953.         de = (int)(d0 >> Exp_shift);  /* The exponent part of d. */
  954.  
  955.     /* Put back the suppressed high-order bit, if normalized. */
  956. #ifndef IBM
  957. #ifndef Sudden_Underflow
  958.         if (de)
  959. #endif
  960.       z |= Exp_msk11;
  961. #endif
  962.  
  963.         if (y = d1) {
  964.                 if (k = lo0bits(&y)) {
  965.                         x[0] = y | z << 32 - k;
  966.                         z >>= k;
  967.                         }
  968.                 else
  969.                         x[0] = y;
  970.                 i = result->wds = (x[1] = z) ? 2 : 1;
  971.                 }
  972.         else {
  973. #ifdef DEBUG
  974.                 if (!z)
  975.                         Bug("Zero passed to d2b");
  976. #endif
  977.                 k = lo0bits(&z);
  978.                 x[0] = z;
  979.                 i = result->wds = 1;
  980.                 k += 32;
  981.                 }
  982. #ifndef Sudden_Underflow
  983.         if (de) {
  984. #endif
  985. #ifdef IBM
  986.                 *e = (de - Bias - (P-1) << 2) + k;
  987.                 *bits = 4*P + 8 - k - hi0bits(word0(d) & Frac_mask);
  988. #else
  989.                 *e = de - Bias - (P-1) + k;
  990.                 *bits = P - k;
  991. #endif
  992. #ifndef Sudden_Underflow
  993.                 }
  994.         else {
  995.                 *e = de - Bias - (P-1) + 1 + k;
  996.                 *bits = 32*i - hi0bits(x[i-1]);
  997.                 }
  998. #endif
  999.         return result;
  1000.         }
  1001. #undef d0
  1002. #undef d1
  1003.  
  1004. static double
  1005. ratio
  1006. #ifdef KR_headers
  1007.         (a, b) Bigint *a, *b;
  1008. #else
  1009.         (Bigint *a, Bigint *b)
  1010. #endif
  1011. {
  1012.         double da, db;
  1013.         int k, ka, kb;
  1014.  
  1015.         da = b2d(a, &ka);
  1016.         db = b2d(b, &kb);
  1017.         k = ka - kb + 32*(a->wds - b->wds);
  1018. #ifdef IBM
  1019.         if (k > 0) {
  1020.                 word0(da) += (k >> 2)*Exp_msk1;
  1021.                 if (k &= 3)
  1022.                         da *= 1 << k;
  1023.                 }
  1024.         else {
  1025.                 k = -k;
  1026.                 word0(db) += (k >> 2)*Exp_msk1;
  1027.                 if (k &= 3)
  1028.                         db *= 1 << k;
  1029.                 }
  1030. #else
  1031.         if (k > 0)
  1032.                 word0(da) += k*Exp_msk1;
  1033.         else {
  1034.                 k = -k;
  1035.                 word0(db) += k*Exp_msk1;
  1036.                 }
  1037. #endif
  1038.         return da / db;
  1039.         }
  1040.  
  1041. static double
  1042. tens[] = {
  1043.                 1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9,
  1044.                 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19,
  1045.                 1e20, 1e21, 1e22
  1046. #ifdef VAX
  1047.                 , 1e23, 1e24
  1048. #endif
  1049.                 };
  1050.  
  1051. static double
  1052. #ifdef IEEE_Arith
  1053. bigtens[] = { 1e16, 1e32, 1e64, 1e128, 1e256 };
  1054. static double tinytens[] = { 1e-16, 1e-32, 1e-64, 1e-128, 1e-256 };
  1055. #define n_bigtens 5
  1056. #else
  1057. #ifdef IBM
  1058. bigtens[] = { 1e16, 1e32, 1e64 };
  1059. static double tinytens[] = { 1e-16, 1e-32, 1e-64 };
  1060. #define n_bigtens 3
  1061. #else
  1062. bigtens[] = { 1e16, 1e32 };
  1063. static double tinytens[] = { 1e-16, 1e-32 };
  1064. #define n_bigtens 2
  1065. #endif
  1066. #endif
  1067.  
  1068.  double
  1069. _IO_strtod
  1070. #ifdef KR_headers
  1071.         (s00, se) CONST char *s00; char **se;
  1072. #else
  1073.         (CONST char *s00, char **se)
  1074. #endif
  1075. {
  1076.         int bb2, bb5, bbe, bd2, bd5, bbbits, bs2, c, dsign,
  1077.                  e, e1, esign, i, j, k, nd, nd0, nf, nz, nz0, sign;
  1078.         CONST char *s, *s0, *s1;
  1079.         double aadj, aadj1, adj, rv, rv0;
  1080.         long L;
  1081.         unsigned long y, z;
  1082.     Bigint _bb, _b_avail, _bd, _bd0, _bs, _delta;
  1083.     Bigint *bb = Binit(&_bb);
  1084.     Bigint *bd = Binit(&_bd);
  1085.     Bigint *bd0 = Binit(&_bd0);
  1086.     Bigint *bs = Binit(&_bs);
  1087.     Bigint *b_avail = Binit(&_b_avail);
  1088.     Bigint *delta = Binit(&_delta);
  1089.  
  1090.     TEST_ENDIANNESS;
  1091.         sign = nz0 = nz = 0;
  1092.         rv = 0.;
  1093.         for(s = s00;;s++) switch(*s) {
  1094.                 case '-':
  1095.                         sign = 1;
  1096.                         /* no break */
  1097.                 case '+':
  1098.                         if (*++s)
  1099.                                 goto break2;
  1100.                         /* no break */
  1101.                 case 0:
  1102.                         goto ret;
  1103.                 case '\t':
  1104.                 case '\n':
  1105.                 case '\v':
  1106.                 case '\f':
  1107.                 case '\r':
  1108.                 case ' ':
  1109.                         continue;
  1110.                 default:
  1111.                         goto break2;
  1112.                 }
  1113.  break2:
  1114.         if (*s == '0') {
  1115.                 nz0 = 1;
  1116.                 while(*++s == '0') ;
  1117.                 if (!*s)
  1118.                         goto ret;
  1119.                 }
  1120.         s0 = s;
  1121.         y = z = 0;
  1122.         for(nd = nf = 0; (c = *s) >= '0' && c <= '9'; nd++, s++)
  1123.                 if (nd < 9)
  1124.                         y = 10*y + c - '0';
  1125.                 else if (nd < 16)
  1126.                         z = 10*z + c - '0';
  1127.         nd0 = nd;
  1128.         if (c == '.') {
  1129.                 c = *++s;
  1130.                 if (!nd) {
  1131.                         for(; c == '0'; c = *++s)
  1132.                                 nz++;
  1133.                         if (c > '0' && c <= '9') {
  1134.                                 s0 = s;
  1135.                                 nf += nz;
  1136.                                 nz = 0;
  1137.                                 goto have_dig;
  1138.                                 }
  1139.                         goto dig_done;
  1140.                         }
  1141.                 for(; c >= '0' && c <= '9'; c = *++s) {
  1142.  have_dig:
  1143.                         nz++;
  1144.                         if (c -= '0') {
  1145.                                 nf += nz;
  1146.                                 for(i = 1; i < nz; i++)
  1147.                                         if (nd++ < 9)
  1148.                                                 y *= 10;
  1149.                                         else if (nd <= DBL_DIG + 1)
  1150.                                                 z *= 10;
  1151.                                 if (nd++ < 9)
  1152.                                         y = 10*y + c;
  1153.                                 else if (nd <= DBL_DIG + 1)
  1154.                                         z = 10*z + c;
  1155.                                 nz = 0;
  1156.                                 }
  1157.                         }
  1158.                 }
  1159.  dig_done:
  1160.         e = 0;
  1161.         if (c == 'e' || c == 'E') {
  1162.                 if (!nd && !nz && !nz0) {
  1163.                         s = s00;
  1164.                         goto ret;
  1165.                         }
  1166.                 s00 = s;
  1167.                 esign = 0;
  1168.                 switch(c = *++s) {
  1169.                         case '-':
  1170.                                 esign = 1;
  1171.                         case '+':
  1172.                                 c = *++s;
  1173.                         }
  1174.                 if (c >= '0' && c <= '9') {
  1175.                         while(c == '0')
  1176.                                 c = *++s;
  1177.                         if (c > '0' && c <= '9') {
  1178.                                 e = c - '0';
  1179.                                 s1 = s;
  1180.                                 while((c = *++s) >= '0' && c <= '9')
  1181.                                         e = 10*e + c - '0';
  1182.                                 if (s - s1 > 8)
  1183.                                         /* Avoid confusion from exponents
  1184.                                          * so large that e might overflow.
  1185.                                          */
  1186.                                         e = 9999999;
  1187.                                 if (esign)
  1188.                                         e = -e;
  1189.                                 }
  1190.                         else
  1191.                                 e = 0;
  1192.                         }
  1193.                 else
  1194.                         s = s00;
  1195.                 }
  1196.         if (!nd) {
  1197.                 if (!nz && !nz0)
  1198.                         s = s00;
  1199.                 goto ret;
  1200.                 }
  1201.         e1 = e -= nf;
  1202.  
  1203.         /* Now we have nd0 digits, starting at s0, followed by a
  1204.          * decimal point, followed by nd-nd0 digits.  The number we're
  1205.          * after is the integer represented by those digits times
  1206.          * 10**e */
  1207.  
  1208.         if (!nd0)
  1209.                 nd0 = nd;
  1210.         k = nd < DBL_DIG + 1 ? nd : DBL_DIG + 1;
  1211.         rv = y;
  1212.         if (k > 9)
  1213.                 rv = tens[k - 9] * rv + z;
  1214.         if (nd <= DBL_DIG
  1215. #ifndef RND_PRODQUOT
  1216.                 && FLT_ROUNDS == 1
  1217. #endif
  1218.                         ) {
  1219.                 if (!e)
  1220.                         goto ret;
  1221.                 if (e > 0) {
  1222.                         if (e <= Ten_pmax) {
  1223. #ifdef VAX
  1224.                                 goto vax_ovfl_check;
  1225. #else
  1226.                                 /* rv = */ rounded_product(rv, tens[e]);
  1227.                                 goto ret;
  1228. #endif
  1229.                                 }
  1230.                         i = DBL_DIG - nd;
  1231.                         if (e <= Ten_pmax + i) {
  1232.                                 /* A fancier test would sometimes let us do
  1233.                                  * this for larger i values.
  1234.                                  */
  1235.                                 e -= i;
  1236.                                 rv *= tens[i];
  1237. #ifdef VAX
  1238.                                 /* VAX exponent range is so narrow we must
  1239.                                  * worry about overflow here...
  1240.                                  */
  1241.  vax_ovfl_check:
  1242.                                 word0(rv) -= P*Exp_msk1;
  1243.                                 /* rv = */ rounded_product(rv, tens[e]);
  1244.                                 if ((word0(rv) & Exp_mask)
  1245.                                  > Exp_msk1*(DBL_MAX_EXP+Bias-1-P))
  1246.                                         goto ovfl;
  1247.                                 word0(rv) += P*Exp_msk1;
  1248. #else
  1249.                                 /* rv = */ rounded_product(rv, tens[e]);
  1250. #endif
  1251.                                 goto ret;
  1252.                                 }
  1253.                         }
  1254. #ifndef Inaccurate_Divide
  1255.                 else if (e >= -Ten_pmax) {
  1256.                         /* rv = */ rounded_quotient(rv, tens[-e]);
  1257.                         goto ret;
  1258.                         }
  1259. #endif
  1260.                 }
  1261.         e1 += nd - k;
  1262.  
  1263.         /* Get starting approximation = rv * 10**e1 */
  1264.  
  1265.         if (e1 > 0) {
  1266.                 if (i = e1 & 15)
  1267.                         rv *= tens[i];
  1268.                 if (e1 &= ~15) {
  1269.                         if (e1 > DBL_MAX_10_EXP) {
  1270.  ovfl:
  1271.                                 errno = ERANGE;
  1272. #if defined(sun) && !defined(__svr4__)
  1273. /* SunOS defines HUGE_VAL as __infinity(), which is in libm. */
  1274. #undef HUGE_VAL
  1275. #endif
  1276. #ifndef HUGE_VAL
  1277. #define HUGE_VAL        1.7976931348623157E+308
  1278. #endif
  1279.                                 rv = HUGE_VAL;
  1280.                                 goto ret;
  1281.                                 }
  1282.                         if (e1 >>= 4) {
  1283.                                 for(j = 0; e1 > 1; j++, e1 >>= 1)
  1284.                                         if (e1 & 1)
  1285.                                                 rv *= bigtens[j];
  1286.                         /* The last multiplication could overflow. */
  1287.                                 word0(rv) -= P*Exp_msk1;
  1288.                                 rv *= bigtens[j];
  1289.                                 if ((z = word0(rv) & Exp_mask)
  1290.                                  > Exp_msk1*(DBL_MAX_EXP+Bias-P))
  1291.                                         goto ovfl;
  1292.                                 if (z > Exp_msk1*(DBL_MAX_EXP+Bias-1-P)) {
  1293.                                         /* set to largest number */
  1294.                                         /* (Can't trust DBL_MAX) */
  1295.                                         word0(rv) = Big0;
  1296.                                         word1(rv) = Big1;
  1297.                                         }
  1298.                                 else
  1299.                                         word0(rv) += P*Exp_msk1;
  1300.                                 }
  1301.  
  1302.                         }
  1303.                 }
  1304.         else if (e1 < 0) {
  1305.                 e1 = -e1;
  1306.                 if (i = e1 & 15)
  1307.                         rv /= tens[i];
  1308.                 if (e1 &= ~15) {
  1309.                         e1 >>= 4;
  1310.                         for(j = 0; e1 > 1; j++, e1 >>= 1)
  1311.                                 if (e1 & 1)
  1312.                                         rv *= tinytens[j];
  1313.                         /* The last multiplication could underflow. */
  1314.                         rv0 = rv;
  1315.                         rv *= tinytens[j];
  1316.                         if (!rv) {
  1317.                                 rv = 2.*rv0;
  1318.                                 rv *= tinytens[j];
  1319.                                 if (!rv) {
  1320.  undfl:
  1321.                                         rv = 0.;
  1322.                                         errno = ERANGE;
  1323.                                         goto ret;
  1324.                                         }
  1325.                                 word0(rv) = Tiny0;
  1326.                                 word1(rv) = Tiny1;
  1327.                                 /* The refinement below will clean
  1328.                                  * this approximation up.
  1329.                                  */
  1330.                                 }
  1331.                         }
  1332.                 }
  1333.  
  1334.         /* Now the hard part -- adjusting rv to the correct value.*/
  1335.  
  1336.         /* Put digits into bd: true value = bd * 10^e */
  1337.  
  1338.         bd0 = s2b(bd0, s0, nd0, nd, y);
  1339.     bd = Brealloc(bd, bd0->k);
  1340.  
  1341.         for(;;) {
  1342.                 Bcopy(bd, bd0);
  1343.                 bb = d2b(bb, rv, &bbe, &bbbits);    /* rv = bb * 2^bbe */
  1344.                 bs = i2b(bs, 1);
  1345.  
  1346.                 if (e >= 0) {
  1347.                         bb2 = bb5 = 0;
  1348.                         bd2 = bd5 = e;
  1349.                         }
  1350.                 else {
  1351.                         bb2 = bb5 = -e;
  1352.                         bd2 = bd5 = 0;
  1353.                         }
  1354.                 if (bbe >= 0)
  1355.                         bb2 += bbe;
  1356.                 else
  1357.                         bd2 -= bbe;
  1358.                 bs2 = bb2;
  1359. #ifdef Sudden_Underflow
  1360. #ifdef IBM
  1361.                 j = 1 + 4*P - 3 - bbbits + ((bbe + bbbits - 1) & 3);
  1362. #else
  1363.                 j = P + 1 - bbbits;
  1364. #endif
  1365. #else
  1366.                 i = bbe + bbbits - 1;   /* logb(rv) */
  1367.                 if (i < Emin)   /* denormal */
  1368.                         j = bbe + (P-Emin);
  1369.                 else
  1370.                         j = P + 1 - bbbits;
  1371. #endif
  1372.                 bb2 += j;
  1373.                 bd2 += j;
  1374.                 i = bb2 < bd2 ? bb2 : bd2;
  1375.                 if (i > bs2)
  1376.                         i = bs2;
  1377.                 if (i > 0) {
  1378.                         bb2 -= i;
  1379.                         bd2 -= i;
  1380.                         bs2 -= i;
  1381.                         }
  1382.                 if (bb5 > 0) {
  1383.             Bigint *b_tmp;
  1384.                         bs = pow5mult(bs, bb5);
  1385.                         b_tmp = mult(b_avail, bs, bb);
  1386.                         b_avail = bb;
  1387.                         bb = b_tmp;
  1388.                         }
  1389.                 if (bb2 > 0)
  1390.                         bb = lshift(bb, bb2);
  1391.                 if (bd5 > 0)
  1392.                         bd = pow5mult(bd, bd5);
  1393.                 if (bd2 > 0)
  1394.                         bd = lshift(bd, bd2);
  1395.                 if (bs2 > 0)
  1396.                         bs = lshift(bs, bs2);
  1397.                 delta = diff(delta, bb, bd);
  1398.                 dsign = delta->sign;
  1399.                 delta->sign = 0;
  1400.                 i = cmp(delta, bs);
  1401.                 if (i < 0) {
  1402.                         /* Error is less than half an ulp -- check for
  1403.                          * special case of mantissa a power of two.
  1404.                          */
  1405.                         if (dsign || word1(rv) || word0(rv) & Bndry_mask)
  1406.                                 break;
  1407.                         delta = lshift(delta,Log2P);
  1408.                         if (cmp(delta, bs) > 0)
  1409.                                 goto drop_down;
  1410.                         break;
  1411.                         }
  1412.                 if (i == 0) {
  1413.                         /* exactly half-way between */
  1414.                         if (dsign) {
  1415.                                 if ((word0(rv) & Bndry_mask1) == Bndry_mask1
  1416.                                  &&  word1(rv) == 0xffffffff) {
  1417.                                         /*boundary case -- increment exponent*/
  1418.                                         word0(rv) = (word0(rv) & Exp_mask)
  1419.                                                 + Exp_msk1
  1420. #ifdef IBM
  1421.                                                 | Exp_msk1 >> 4
  1422. #endif
  1423.                                                 ;
  1424.                                         word1(rv) = 0;
  1425.                                         break;
  1426.                                         }
  1427.                                 }
  1428.                         else if (!(word0(rv) & Bndry_mask) && !word1(rv)) {
  1429.  drop_down:
  1430.                                 /* boundary case -- decrement exponent */
  1431. #ifdef Sudden_Underflow
  1432.                                 L = word0(rv) & Exp_mask;
  1433. #ifdef IBM
  1434.                                 if (L <  Exp_msk1)
  1435. #else
  1436.                                 if (L <= Exp_msk1)
  1437. #endif
  1438.                                         goto undfl;
  1439.                                 L -= Exp_msk1;
  1440. #else
  1441.                                 L = (word0(rv) & Exp_mask) - Exp_msk1;
  1442. #endif
  1443.                                 word0(rv) = L | Bndry_mask1;
  1444.                                 word1(rv) = 0xffffffff;
  1445. #ifdef IBM
  1446.                                 continue;
  1447. #else
  1448.                                 break;
  1449. #endif
  1450.                                 }
  1451. #ifndef ROUND_BIASED
  1452.                         if (!(word1(rv) & LSB))
  1453.                                 break;
  1454. #endif
  1455.                         if (dsign)
  1456.                                 rv += ulp(rv);
  1457. #ifndef ROUND_BIASED
  1458.                         else {
  1459.                                 rv -= ulp(rv);
  1460. #ifndef Sudden_Underflow
  1461.                                 if (!rv)
  1462.                                         goto undfl;
  1463. #endif
  1464.                                 }
  1465. #endif
  1466.                         break;
  1467.                         }
  1468.                 if ((aadj = ratio(delta, bs)) <= 2.) {
  1469.                         if (dsign)
  1470.                                 aadj = aadj1 = 1.;
  1471.                         else if (word1(rv) || word0(rv) & Bndry_mask) {
  1472. #ifndef Sudden_Underflow
  1473.                                 if (word1(rv) == Tiny1 && !word0(rv))
  1474.                                         goto undfl;
  1475. #endif
  1476.                                 aadj = 1.;
  1477.                                 aadj1 = -1.;
  1478.                                 }
  1479.                         else {
  1480.                                 /* special case -- power of FLT_RADIX to be */
  1481.                                 /* rounded down... */
  1482.  
  1483.                                 if (aadj < 2./FLT_RADIX)
  1484.                                         aadj = 1./FLT_RADIX;
  1485.                                 else
  1486.                                         aadj *= 0.5;
  1487.                                 aadj1 = -aadj;
  1488.                                 }
  1489.                         }
  1490.                 else {
  1491.                         aadj *= 0.5;
  1492.                         aadj1 = dsign ? aadj : -aadj;
  1493. #ifdef Check_FLT_ROUNDS
  1494.                         switch(FLT_ROUNDS) {
  1495.                                 case 2: /* towards +infinity */
  1496.                                         aadj1 -= 0.5;
  1497.                                         break;
  1498.                                 case 0: /* towards 0 */
  1499.                                 case 3: /* towards -infinity */
  1500.                                         aadj1 += 0.5;
  1501.                                 }
  1502. #else
  1503.                         if (FLT_ROUNDS == 0)
  1504.                                 aadj1 += 0.5;
  1505. #endif
  1506.                         }
  1507.                 y = word0(rv) & Exp_mask;
  1508.  
  1509.                 /* Check for overflow */
  1510.  
  1511.                 if (y == Exp_msk1*(DBL_MAX_EXP+Bias-1)) {
  1512.                         rv0 = rv;
  1513.                         word0(rv) -= P*Exp_msk1;
  1514.                         adj = aadj1 * ulp(rv);
  1515.                         rv += adj;
  1516.                         if ((word0(rv) & Exp_mask) >=
  1517.                                         Exp_msk1*(DBL_MAX_EXP+Bias-P)) {
  1518.                                 if (word0(rv0) == Big0 && word1(rv0) == Big1)
  1519.                                         goto ovfl;
  1520.                                 word0(rv) = Big0;
  1521.                                 word1(rv) = Big1;
  1522.                                 continue;
  1523.                                 }
  1524.                         else
  1525.                                 word0(rv) += P*Exp_msk1;
  1526.                         }
  1527.                 else {
  1528. #ifdef Sudden_Underflow
  1529.                         if ((word0(rv) & Exp_mask) <= P*Exp_msk1) {
  1530.                                 rv0 = rv;
  1531.                                 word0(rv) += P*Exp_msk1;
  1532.                                 adj = aadj1 * ulp(rv);
  1533.                                 rv += adj;
  1534. #ifdef IBM
  1535.                                 if ((word0(rv) & Exp_mask) <  P*Exp_msk1)
  1536. #else
  1537.                                 if ((word0(rv) & Exp_mask) <= P*Exp_msk1)
  1538. #endif
  1539.                                         {
  1540.                                         if (word0(rv0) == Tiny0
  1541.                                          && word1(rv0) == Tiny1)
  1542.                                                 goto undfl;
  1543.                                         word0(rv) = Tiny0;
  1544.                                         word1(rv) = Tiny1;
  1545.                                         continue;
  1546.                                         }
  1547.                                 else
  1548.                                         word0(rv) -= P*Exp_msk1;
  1549.                                 }
  1550.                         else {
  1551.                                 adj = aadj1 * ulp(rv);
  1552.                                 rv += adj;
  1553.                                 }
  1554. #else
  1555.                         /* Compute adj so that the IEEE rounding rules will
  1556.                          * correctly round rv + adj in some half-way cases.
  1557.                          * If rv * ulp(rv) is denormalized (i.e.,
  1558.                          * y <= (P-1)*Exp_msk1), we must adjust aadj to avoid
  1559.                          * trouble from bits lost to denormalization;
  1560.                          * example: 1.2e-307 .
  1561.                          */
  1562.                         if (y <= (P-1)*Exp_msk1 && aadj >= 1.) {
  1563.                                 aadj1 = (double)(int)(aadj + 0.5);
  1564.                                 if (!dsign)
  1565.                                         aadj1 = -aadj1;
  1566.                                 }
  1567.                         adj = aadj1 * ulp(rv);
  1568.                         rv += adj;
  1569. #endif
  1570.                         }
  1571.                 z = word0(rv) & Exp_mask;
  1572.                 if (y == z) {
  1573.                         /* Can we stop now? */
  1574.                         L = (long)aadj;
  1575.                         aadj -= L;
  1576.                         /* The tolerances below are conservative. */
  1577.                         if (dsign || word1(rv) || word0(rv) & Bndry_mask) {
  1578.                                 if (aadj < .4999999 || aadj > .5000001)
  1579.                                         break;
  1580.                                 }
  1581.                         else if (aadj < .4999999/FLT_RADIX)
  1582.                                 break;
  1583.                         }
  1584.                 }
  1585.         Bfree(bb);
  1586.         Bfree(bd);
  1587.         Bfree(bs);
  1588.         Bfree(bd0);
  1589.         Bfree(delta);
  1590.     Bfree(b_avail);
  1591.  ret:
  1592.         if (se)
  1593.                 *se = (char *)s;
  1594.         return sign ? -rv : rv;
  1595.         }
  1596.  
  1597. static int
  1598. quorem
  1599. #ifdef KR_headers
  1600.         (b, S) Bigint *b, *S;
  1601. #else
  1602.         (Bigint *b, Bigint *S)
  1603. #endif
  1604. {
  1605.         int n;
  1606.         long borrow, y;
  1607.         unsigned long carry, q, ys;
  1608.         unsigned long *bx, *bxe, *sx, *sxe;
  1609.         long z;
  1610.         unsigned long si, zs;
  1611.  
  1612.         n = S->wds;
  1613. #ifdef DEBUG
  1614.         /*debug*/ if (b->wds > n)
  1615.         /*debug*/       Bug("oversize b in quorem");
  1616. #endif
  1617.         if (b->wds < n)
  1618.                 return 0;
  1619.         sx = S->x;
  1620.         sxe = sx + --n;
  1621.         bx = b->x;
  1622.         bxe = bx + n;
  1623.         q = *bxe / (*sxe + 1);  /* ensure q <= true quotient */
  1624. #ifdef DEBUG
  1625.         /*debug*/ if (q > 9)
  1626.         /*debug*/       Bug("oversized quotient in quorem");
  1627. #endif
  1628.         if (q) {
  1629.                 borrow = 0;
  1630.                 carry = 0;
  1631.                 do {
  1632.                         si = *sx++;
  1633.                         ys = (si & 0xffff) * q + carry;
  1634.                         zs = (si >> 16) * q + (ys >> 16);
  1635.                         carry = zs >> 16;
  1636.                         y = (*bx & 0xffff) - (ys & 0xffff) + borrow;
  1637.                         borrow = y >> 16;
  1638.                         Sign_Extend(borrow, y);
  1639.                         z = (*bx >> 16) - (zs & 0xffff) + borrow;
  1640.                         borrow = z >> 16;
  1641.                         Sign_Extend(borrow, z);
  1642.                         Storeinc(bx, z, y);
  1643.                         }
  1644.                         while(sx <= sxe);
  1645.                 if (!*bxe) {
  1646.                         bx = b->x;
  1647.                         while(--bxe > bx && !*bxe)
  1648.                                 --n;
  1649.                         b->wds = n;
  1650.                         }
  1651.                 }
  1652.         if (cmp(b, S) >= 0) {
  1653.                 q++;
  1654.                 borrow = 0;
  1655.                 carry = 0;
  1656.                 bx = b->x;
  1657.                 sx = S->x;
  1658.                 do {
  1659.                         si = *sx++;
  1660.                         ys = (si & 0xffff) + carry;
  1661.                         zs = (si >> 16) + (ys >> 16);
  1662.                         carry = zs >> 16;
  1663.                         y = (*bx & 0xffff) - (ys & 0xffff) + borrow;
  1664.                         borrow = y >> 16;
  1665.                         Sign_Extend(borrow, y);
  1666.                         z = (*bx >> 16) - (zs & 0xffff) + borrow;
  1667.                         borrow = z >> 16;
  1668.                         Sign_Extend(borrow, z);
  1669.                         Storeinc(bx, z, y);
  1670.                         }
  1671.                         while(sx <= sxe);
  1672.                 bx = b->x;
  1673.                 bxe = bx + n;
  1674.                 if (!*bxe) {
  1675.                         while(--bxe > bx && !*bxe)
  1676.                                 --n;
  1677.                         b->wds = n;
  1678.                         }
  1679.                 }
  1680.         return q;
  1681.         }
  1682.  
  1683. /* dtoa for IEEE arithmetic (dmg): convert double to ASCII string.
  1684.  *
  1685.  * Inspired by "How to Print Floating-Point Numbers Accurately" by
  1686.  * Guy L. Steele, Jr. and Jon L. White [Proc. ACM SIGPLAN '90, pp. 92-101].
  1687.  *
  1688.  * Modifications:
  1689.  *      1. Rather than iterating, we use a simple numeric overestimate
  1690.  *         to determine k = floor(log10(d)).  We scale relevant
  1691.  *         quantities using O(log2(k)) rather than O(k) multiplications.
  1692.  *      2. For some modes > 2 (corresponding to ecvt and fcvt), we don't
  1693.  *         try to generate digits strictly left to right.  Instead, we
  1694.  *         compute with fewer bits and propagate the carry if necessary
  1695.  *         when rounding the final digit up.  This is often faster.
  1696.  *      3. Under the assumption that input will be rounded nearest,
  1697.  *         mode 0 renders 1e23 as 1e23 rather than 9.999999999999999e22.
  1698.  *         That is, we allow equality in stopping tests when the
  1699.  *         round-nearest rule will give the same floating-point value
  1700.  *         as would satisfaction of the stopping test with strict
  1701.  *         inequality.
  1702.  *      4. We remove common factors of powers of 2 from relevant
  1703.  *         quantities.
  1704.  *      5. When converting floating-point integers less than 1e16,
  1705.  *         we use floating-point arithmetic rather than resorting
  1706.  *         to multiple-precision integers.
  1707.  *      6. When asked to produce fewer than 15 digits, we first try
  1708.  *         to get by with floating-point arithmetic; we resort to
  1709.  *         multiple-precision integer arithmetic only if we cannot
  1710.  *         guarantee that the floating-point calculation has given
  1711.  *         the correctly rounded result.  For k requested digits and
  1712.  *         "uniformly" distributed input, the probability is
  1713.  *         something like 10^(k-15) that we must resort to the long
  1714.  *         calculation.
  1715.  */
  1716.  
  1717.  char *
  1718. _IO_dtoa
  1719. #ifdef KR_headers
  1720.         (d, mode, ndigits, decpt, sign, rve)
  1721.         double d; int mode, ndigits, *decpt, *sign; char **rve;
  1722. #else
  1723.         (double d, int mode, int ndigits, int *decpt, int *sign, char **rve)
  1724. #endif
  1725. {
  1726.  /*     Arguments ndigits, decpt, sign are similar to those
  1727.         of ecvt and fcvt; trailing zeros are suppressed from
  1728.         the returned string.  If not null, *rve is set to point
  1729.         to the end of the return value.  If d is +-Infinity or NaN,
  1730.         then *decpt is set to 9999.
  1731.  
  1732.         mode:
  1733.                 0 ==> shortest string that yields d when read in
  1734.                         and rounded to nearest.
  1735.                 1 ==> like 0, but with Steele & White stopping rule;
  1736.                         e.g. with IEEE P754 arithmetic , mode 0 gives
  1737.                         1e23 whereas mode 1 gives 9.999999999999999e22.
  1738.                 2 ==> max(1,ndigits) significant digits.  This gives a
  1739.                         return value similar to that of ecvt, except
  1740.                         that trailing zeros are suppressed.
  1741.                 3 ==> through ndigits past the decimal point.  This
  1742.                         gives a return value similar to that from fcvt,
  1743.                         except that trailing zeros are suppressed, and
  1744.                         ndigits can be negative.
  1745.                 4-9 should give the same return values as 2-3, i.e.,
  1746.                         4 <= mode <= 9 ==> same return as mode
  1747.                         2 + (mode & 1).  These modes are mainly for
  1748.                         debugging; often they run slower but sometimes
  1749.                         faster than modes 2-3.
  1750.                 4,5,8,9 ==> left-to-right digit generation.
  1751.                 6-9 ==> don't try fast floating-point estimate
  1752.                         (if applicable).
  1753.  
  1754.                 Values of mode other than 0-9 are treated as mode 0.
  1755.  
  1756.                 Sufficient space is allocated to the return value
  1757.                 to hold the suppressed trailing zeros.
  1758.         */
  1759.  
  1760.         int bbits, b2, b5, be, dig, i, ieps, ilim, ilim0, ilim1,
  1761.                 j, j1, k, k0, k_check, leftright, m2, m5, s2, s5,
  1762.                 spec_case, try_quick;
  1763.         long L;
  1764. #ifndef Sudden_Underflow
  1765.         int denorm;
  1766. #endif
  1767.     Bigint _b_avail, _b, _mhi, _mlo, _S;
  1768.     Bigint *b_avail = Binit(&_b_avail);
  1769.     Bigint *b = Binit(&_b);
  1770.     Bigint *S = Binit(&_S);
  1771.     /* mhi and mlo are only set and used if leftright. */
  1772.         Bigint *mhi = NULL, *mlo = NULL;
  1773.         double d2, ds, eps;
  1774.         char *s, *s0;
  1775.         static Bigint *result = NULL;
  1776.         static int result_k;
  1777.  
  1778.     TEST_ENDIANNESS;
  1779.         if (result) {
  1780.                 result->k = result_k;
  1781.                 result->maxwds = 1 << result_k;
  1782.                 }
  1783.  
  1784.         if (word0(d) & Sign_bit) {
  1785.                 /* set sign for everything, including 0's and NaNs */
  1786.                 *sign = 1;
  1787.                 word0(d) &= ~Sign_bit;  /* clear sign bit */
  1788.                 }
  1789.         else
  1790.                 *sign = 0;
  1791.  
  1792. #if defined(IEEE_Arith) + defined(VAX)
  1793. #ifdef IEEE_Arith
  1794.         if ((word0(d) & Exp_mask) == Exp_mask)
  1795. #else
  1796.         if (word0(d)  == 0x8000)
  1797. #endif
  1798.                 {
  1799.                 /* Infinity or NaN */
  1800.                 *decpt = 9999;
  1801. #ifdef IEEE_Arith
  1802.         if (!word1(d) && !(word0(d) & 0xfffff))
  1803.           {
  1804.             s = "Infinity";
  1805.             if (rve)
  1806.               *rve = s + 8;
  1807.           }
  1808.         else
  1809. #endif
  1810.           {
  1811.             s = "NaN";
  1812.             if (rve)
  1813.               *rve = s +3;
  1814.           }
  1815.                 return s;
  1816.                 }
  1817. #endif
  1818. #ifdef IBM
  1819.         d += 0; /* normalize */
  1820. #endif
  1821.         if (!d) {
  1822.                 *decpt = 1;
  1823.                 s = "0";
  1824.                 if (rve)
  1825.                         *rve = s + 1;
  1826.                 return s;
  1827.                 }
  1828.  
  1829.         b = d2b(b, d, &be, &bbits);
  1830.         i = (int)(word0(d) >> Exp_shift1 & (Exp_mask>>Exp_shift1));
  1831. #ifndef Sudden_Underflow
  1832.         if (i) {
  1833. #endif
  1834.                 d2 = d;
  1835.                 word0(d2) &= Frac_mask1;
  1836.                 word0(d2) |= Exp_11;
  1837. #ifdef IBM
  1838.                 if (j = 11 - hi0bits(word0(d2) & Frac_mask))
  1839.                         d2 /= 1 << j;
  1840. #endif
  1841.  
  1842.                 i -= Bias;
  1843. #ifdef IBM
  1844.                 i <<= 2;
  1845.                 i += j;
  1846. #endif
  1847. #ifndef Sudden_Underflow
  1848.                 denorm = 0;
  1849.                 }
  1850.         else {
  1851.                 /* d is denormalized */
  1852.         unsigned long x;
  1853.  
  1854.                 i = bbits + be + (Bias + (P-1) - 1);
  1855.                 x = i > 32  ? word0(d) << 64 - i | word1(d) >> i - 32
  1856.                             : word1(d) << 32 - i;
  1857.                 d2 = x;
  1858.                 word0(d2) -= 31*Exp_msk1; /* adjust exponent */
  1859.                 i -= (Bias + (P-1) - 1) + 1;
  1860.                 denorm = 1;
  1861.                 }
  1862. #endif
  1863.  
  1864.     /* Now i is the unbiased base-2 exponent. */
  1865.  
  1866.         /* log(x)       ~=~ log(1.5) + (x-1.5)/1.5
  1867.          * log10(x)      =  log(x) / log(10)
  1868.          *              ~=~ log(1.5)/log(10) + (x-1.5)/(1.5*log(10))
  1869.          * log10(d) = i*log(2)/log(10) + log10(d2)
  1870.          *
  1871.          * This suggests computing an approximation k to log10(d) by
  1872.          *
  1873.          * k = i*0.301029995663981
  1874.          *      + ( (d2-1.5)*0.289529654602168 + 0.176091259055681 );
  1875.          *
  1876.          * We want k to be too large rather than too small.
  1877.          * The error in the first-order Taylor series approximation
  1878.          * is in our favor, so we just round up the constant enough
  1879.          * to compensate for any error in the multiplication of
  1880.          * (i) by 0.301029995663981; since |i| <= 1077,
  1881.          * and 1077 * 0.30103 * 2^-52 ~=~ 7.2e-14,
  1882.          * adding 1e-13 to the constant term more than suffices.
  1883.          * Hence we adjust the constant term to 0.1760912590558.
  1884.          * (We could get a more accurate k by invoking log10,
  1885.          *  but this is probably not worthwhile.)
  1886.          */
  1887.  
  1888.         ds = (d2-1.5)*0.289529654602168 + 0.1760912590558 + i*0.301029995663981;
  1889.         k = (int)ds;
  1890.         if (ds < 0. && ds != k)
  1891.                 k--;    /* want k = floor(ds) */
  1892.         k_check = 1;
  1893.         if (k >= 0 && k <= Ten_pmax) {
  1894.                 if (d < tens[k])
  1895.                         k--;
  1896.                 k_check = 0;
  1897.                 }
  1898.         j = bbits - i - 1;
  1899.         if (j >= 0) {
  1900.                 b2 = 0;
  1901.                 s2 = j;
  1902.                 }
  1903.         else {
  1904.                 b2 = -j;
  1905.                 s2 = 0;
  1906.                 }
  1907.         if (k >= 0) {
  1908.                 b5 = 0;
  1909.                 s5 = k;
  1910.                 s2 += k;
  1911.                 }
  1912.         else {
  1913.                 b2 -= k;
  1914.                 b5 = -k;
  1915.                 s5 = 0;
  1916.                 }
  1917.         if (mode < 0 || mode > 9)
  1918.                 mode = 0;
  1919.         try_quick = 1;
  1920.         if (mode > 5) {
  1921.                 mode -= 4;
  1922.                 try_quick = 0;
  1923.                 }
  1924.         leftright = 1;
  1925.         switch(mode) {
  1926.                 case 0:
  1927.                 case 1:
  1928.                         ilim = ilim1 = -1;
  1929.                         i = 18;
  1930.                         ndigits = 0;
  1931.                         break;
  1932.                 case 2:
  1933.                         leftright = 0;
  1934.                         /* no break */
  1935.                 case 4:
  1936.                         if (ndigits <= 0)
  1937.                                 ndigits = 1;
  1938.                         ilim = ilim1 = i = ndigits;
  1939.                         break;
  1940.                 case 3:
  1941.                         leftright = 0;
  1942.                         /* no break */
  1943.                 case 5:
  1944.                         i = ndigits + k + 1;
  1945.                         ilim = i;
  1946.                         ilim1 = i - 1;
  1947.                         if (i <= 0)
  1948.                                 i = 1;
  1949.                 }
  1950.     /* i is now an upper bound of the number of digits to generate. */
  1951.         j = sizeof(unsigned long) * (1<<BIGINT_MINIMUM_K);
  1952.     /* The test is <= so as to allow room for the final '\0'. */
  1953.         for(result_k = BIGINT_MINIMUM_K; BIGINT_HEADER_SIZE + j <= i;
  1954.                 j <<= 1) result_k++;
  1955.         result = Brealloc(result, result_k);
  1956.         s = s0 = (char *)result;
  1957.  
  1958.         if (ilim >= 0 && ilim <= Quick_max && try_quick) {
  1959.  
  1960.                 /* Try to get by with floating-point arithmetic. */
  1961.  
  1962.                 i = 0;
  1963.                 d2 = d;
  1964.                 k0 = k;
  1965.                 ilim0 = ilim;
  1966.                 ieps = 2; /* conservative */
  1967.                 if (k > 0) {
  1968.                         ds = tens[k&0xf];
  1969.                         j = k >> 4;
  1970.                         if (j & Bletch) {
  1971.                                 /* prevent overflows */
  1972.                                 j &= Bletch - 1;
  1973.                                 d /= bigtens[n_bigtens-1];
  1974.                                 ieps++;
  1975.                                 }
  1976.                         for(; j; j >>= 1, i++)
  1977.                                 if (j & 1) {
  1978.                                         ieps++;
  1979.                                         ds *= bigtens[i];
  1980.                                         }
  1981.                         d /= ds;
  1982.                         }
  1983.                 else if (j1 = -k) {
  1984.                         d *= tens[j1 & 0xf];
  1985.                         for(j = j1 >> 4; j; j >>= 1, i++)
  1986.                                 if (j & 1) {
  1987.                                         ieps++;
  1988.                                         d *= bigtens[i];
  1989.                                         }
  1990.                         }
  1991.                 if (k_check && d < 1. && ilim > 0) {
  1992.                         if (ilim1 <= 0)
  1993.                                 goto fast_failed;
  1994.                         ilim = ilim1;
  1995.                         k--;
  1996.                         d *= 10.;
  1997.                         ieps++;
  1998.                         }
  1999.                 eps = ieps*d + 7.;
  2000.                 word0(eps) -= (P-1)*Exp_msk1;
  2001.                 if (ilim == 0) {
  2002.                         d -= 5.;
  2003.                         if (d > eps)
  2004.                                 goto one_digit;
  2005.                         if (d < -eps)
  2006.                                 goto no_digits;
  2007.                         goto fast_failed;
  2008.                         }
  2009. #ifndef No_leftright
  2010.                 if (leftright) {
  2011.                         /* Use Steele & White method of only
  2012.                          * generating digits needed.
  2013.                          */
  2014.                         eps = 0.5/tens[ilim-1] - eps;
  2015.                         for(i = 0;;) {
  2016.                                 L = (long)d;
  2017.                                 d -= L;
  2018.                                 *s++ = '0' + (int)L;
  2019.                                 if (d < eps)
  2020.                                         goto ret1;
  2021.                                 if (1. - d < eps)
  2022.                                         goto bump_up;
  2023.                                 if (++i >= ilim)
  2024.                                         break;
  2025.                                 eps *= 10.;
  2026.                                 d *= 10.;
  2027.                                 }
  2028.                         }
  2029.                 else {
  2030. #endif
  2031.                         /* Generate ilim digits, then fix them up. */
  2032.                         eps *= tens[ilim-1];
  2033.                         for(i = 1;; i++, d *= 10.) {
  2034.                                 L = (long)d;
  2035.                                 d -= L;
  2036.                                 *s++ = '0' + (int)L;
  2037.                                 if (i == ilim) {
  2038.                                         if (d > 0.5 + eps)
  2039.                                                 goto bump_up;
  2040.                                         else if (d < 0.5 - eps) {
  2041.                                                 while(*--s == '0');
  2042.                                                 s++;
  2043.                                                 goto ret1;
  2044.                                                 }
  2045.                                         break;
  2046.                                         }
  2047.                                 }
  2048. #ifndef No_leftright
  2049.                         }
  2050. #endif
  2051.  fast_failed:
  2052.                 s = s0;
  2053.                 d = d2;
  2054.                 k = k0;
  2055.                 ilim = ilim0;
  2056.                 }
  2057.  
  2058.         /* Do we have a "small" integer? */
  2059.  
  2060.         if (be >= 0 && k <= Int_max) {
  2061.                 /* Yes. */
  2062.                 ds = tens[k];
  2063.                 if (ndigits < 0 && ilim <= 0) {
  2064.                         if (ilim < 0 || d <= 5*ds)
  2065.                                 goto no_digits;
  2066.                         goto one_digit;
  2067.                         }
  2068.                 for(i = 1;; i++) {
  2069.                         L = (long)(d / ds);
  2070.                         d -= L*ds;
  2071. #ifdef Check_FLT_ROUNDS
  2072.                         /* If FLT_ROUNDS == 2, L will usually be high by 1 */
  2073.                         if (d < 0) {
  2074.                                 L--;
  2075.                                 d += ds;
  2076.                                 }
  2077. #endif
  2078.                         *s++ = '0' + (int)L;
  2079.                         if (i == ilim) {
  2080.                                 d += d;
  2081.                                 if (d > ds || d == ds && L & 1) {
  2082.  bump_up:
  2083.                                         while(*--s == '9')
  2084.                                                 if (s == s0) {
  2085.                                                         k++;
  2086.                                                         *s = '0';
  2087.                                                         break;
  2088.                                                         }
  2089.                                         ++*s++;
  2090.                                         }
  2091.                                 break;
  2092.                                 }
  2093.                         if (!(d *= 10.))
  2094.                                 break;
  2095.                         }
  2096.                 goto ret1;
  2097.                 }
  2098.  
  2099.         m2 = b2;
  2100.         m5 = b5;
  2101.         if (leftright) {
  2102.                 if (mode < 2) {
  2103.                         i =
  2104. #ifndef Sudden_Underflow
  2105.                                 denorm ? be + (Bias + (P-1) - 1 + 1) :
  2106. #endif
  2107. #ifdef IBM
  2108.                                 1 + 4*P - 3 - bbits + ((bbits + be - 1) & 3);
  2109. #else
  2110.                                 1 + P - bbits;
  2111. #endif
  2112.                         }
  2113.                 else {
  2114.                         j = ilim - 1;
  2115.                         if (m5 >= j)
  2116.                                 m5 -= j;
  2117.                         else {
  2118.                                 s5 += j -= m5;
  2119.                                 b5 += j;
  2120.                                 m5 = 0;
  2121.                                 }
  2122.                         if ((i = ilim) < 0) {
  2123.                                 m2 -= i;
  2124.                                 i = 0;
  2125.                                 }
  2126.                         }
  2127.                 b2 += i;
  2128.                 s2 += i;
  2129.                 mhi = i2b(Binit(&_mhi), 1);
  2130.                 }
  2131.         if (m2 > 0 && s2 > 0) {
  2132.                 i = m2 < s2 ? m2 : s2;
  2133.                 b2 -= i;
  2134.                 m2 -= i;
  2135.                 s2 -= i;
  2136.                 }
  2137.         if (b5 > 0) {
  2138.                 if (leftright) {
  2139.                         if (m5 > 0) {
  2140.                 Bigint *b_tmp;
  2141.                                 mhi = pow5mult(mhi, m5);
  2142.                                 b_tmp = mult(b_avail, mhi, b);
  2143.                                 b_avail = b;
  2144.                                 b = b_tmp;
  2145.                                 }
  2146.                         if (j = b5 - m5)
  2147.                                 b = pow5mult(b, j);
  2148.                         }
  2149.                 else
  2150.                         b = pow5mult(b, b5);
  2151.                 }
  2152.         S = i2b(S, 1);
  2153.         if (s5 > 0)
  2154.                 S = pow5mult(S, s5);
  2155.  
  2156.         /* Check for special case that d is a normalized power of 2. */
  2157.  
  2158.         if (mode < 2) {
  2159.                 if (!word1(d) && !(word0(d) & Bndry_mask)
  2160. #ifndef Sudden_Underflow
  2161.                  && word0(d) & Exp_mask
  2162. #endif
  2163.                                 ) {
  2164.                         /* The special case */
  2165.                         b2 += Log2P;
  2166.                         s2 += Log2P;
  2167.                         spec_case = 1;
  2168.                         }
  2169.                 else
  2170.                         spec_case = 0;
  2171.                 }
  2172.  
  2173.         /* Arrange for convenient computation of quotients:
  2174.          * shift left if necessary so divisor has 4 leading 0 bits.
  2175.          *
  2176.          * Perhaps we should just compute leading 28 bits of S once
  2177.          * and for all and pass them and a shift to quorem, so it
  2178.          * can do shifts and ors to compute the numerator for q.
  2179.          */
  2180.         if (i = ((s5 ? 32 - hi0bits(S->x[S->wds-1]) : 1) + s2) & 0x1f)
  2181.                 i = 32 - i;
  2182.         if (i > 4) {
  2183.                 i -= 4;
  2184.                 b2 += i;
  2185.                 m2 += i;
  2186.                 s2 += i;
  2187.                 }
  2188.         else if (i < 4) {
  2189.                 i += 28;
  2190.                 b2 += i;
  2191.                 m2 += i;
  2192.                 s2 += i;
  2193.                 }
  2194.         if (b2 > 0)
  2195.                 b = lshift(b, b2);
  2196.         if (s2 > 0)
  2197.                 S = lshift(S, s2);
  2198.         if (k_check) {
  2199.                 if (cmp(b,S) < 0) {
  2200.                         k--;
  2201.                         b = multadd(b, 10, 0);  /* we botched the k estimate */
  2202.                         if (leftright)
  2203.                                 mhi = multadd(mhi, 10, 0);
  2204.                         ilim = ilim1;
  2205.                         }
  2206.                 }
  2207.         if (ilim <= 0 && mode > 2) {
  2208.                 if (ilim < 0 || cmp(b,S = multadd(S,5,0)) <= 0) {
  2209.                         /* no digits, fcvt style */
  2210.  no_digits:
  2211.                         k = -1 - ndigits;
  2212.                         goto ret;
  2213.                         }
  2214.  one_digit:
  2215.                 *s++ = '1';
  2216.                 k++;
  2217.                 goto ret;
  2218.                 }
  2219.         if (leftright) {
  2220.                 if (m2 > 0)
  2221.                         mhi = lshift(mhi, m2);
  2222.  
  2223.                 /* Compute mlo -- check for special case
  2224.                  * that d is a normalized power of 2.
  2225.                  */
  2226.  
  2227.                 if (spec_case) {
  2228.             mlo = Brealloc(Binit(&_mlo), mhi->k);
  2229.                         Bcopy(mlo, mhi);
  2230.                         mhi = lshift(mhi, Log2P);
  2231.                         }
  2232.         else
  2233.             mlo = mhi;
  2234.  
  2235.                 for(i = 1;;i++) {
  2236.                         dig = quorem(b,S) + '0';
  2237.                         /* Do we yet have the shortest decimal string
  2238.                          * that will round to d?
  2239.                          */
  2240.                         j = cmp(b, mlo);
  2241.                         b_avail = diff(b_avail, S, mhi); /* b_avail = S - mi */
  2242.                         j1 = b_avail->sign ? 1 : cmp(b, b_avail);
  2243. #ifndef ROUND_BIASED
  2244.                         if (j1 == 0 && !mode && !(word1(d) & 1)) {
  2245.                                 if (dig == '9')
  2246.                                         goto round_9_up;
  2247.                                 if (j > 0)
  2248.                                         dig++;
  2249.                                 *s++ = dig;
  2250.                                 goto ret;
  2251.                                 }
  2252. #endif
  2253.                         if (j < 0 || j == 0 && !mode
  2254. #ifndef ROUND_BIASED
  2255.                                                         && !(word1(d) & 1)
  2256. #endif
  2257.                                         ) {
  2258.                                 if (j1 > 0) {
  2259.                                         b = lshift(b, 1);
  2260.                                         j1 = cmp(b, S);
  2261.                                         if ((j1 > 0 || j1 == 0 && dig & 1)
  2262.                                         && dig++ == '9')
  2263.                                                 goto round_9_up;
  2264.                                         }
  2265.                                 *s++ = dig;
  2266.                                 goto ret;
  2267.                                 }
  2268.                         if (j1 > 0) {
  2269.                                 if (dig == '9') { /* possible if i == 1 */
  2270.  round_9_up:
  2271.                                         *s++ = '9';
  2272.                                         goto roundoff;
  2273.                                         }
  2274.                                 *s++ = dig + 1;
  2275.                                 goto ret;
  2276.                                 }
  2277.                         *s++ = dig;
  2278.                         if (i == ilim)
  2279.                                 break;
  2280.                         b = multadd(b, 10, 0);
  2281.                         if (mlo == mhi)
  2282.                                 mlo = mhi = multadd(mhi, 10, 0);
  2283.                         else {
  2284.                                 mlo = multadd(mlo, 10, 0);
  2285.                                 mhi = multadd(mhi, 10, 0);
  2286.                                 }
  2287.                         }
  2288.                 }
  2289.         else
  2290.                 for(i = 1;; i++) {
  2291.                         *s++ = dig = quorem(b,S) + '0';
  2292.                         if (i >= ilim)
  2293.                                 break;
  2294.                         b = multadd(b, 10, 0);
  2295.                         }
  2296.  
  2297.         /* Round off last digit */
  2298.  
  2299.         b = lshift(b, 1);
  2300.         j = cmp(b, S);
  2301.         if (j > 0 || j == 0 && dig & 1) {
  2302.  roundoff:
  2303.                 while(*--s == '9')
  2304.                         if (s == s0) {
  2305.                                 k++;
  2306.                                 *s++ = '1';
  2307.                                 goto ret;
  2308.                                 }
  2309.                 ++*s++;
  2310.                 }
  2311.         else {
  2312.                 while(*--s == '0');
  2313.                 s++;
  2314.                 }
  2315.  ret:
  2316.     Bfree(b_avail);
  2317.         Bfree(S);
  2318.         if (mhi) {
  2319.                 if (mlo && mlo != mhi)
  2320.                         Bfree(mlo);
  2321.                 Bfree(mhi);
  2322.                 }
  2323.  ret1:
  2324.         Bfree(b);
  2325.         *s = 0;
  2326.         *decpt = k + 1;
  2327.         if (rve)
  2328.                 *rve = s;
  2329.         return s0;
  2330.         }
  2331. #endif /* USE_DTOA */
  2332.