Ruby  1.9.3p547(2014-05-14revision45962)
util.c
Go to the documentation of this file.
1 /**********************************************************************
2 
3  util.c -
4 
5  $Author: usa $
6  created at: Fri Mar 10 17:22:34 JST 1995
7 
8  Copyright (C) 1993-2008 Yukihiro Matsumoto
9 
10 **********************************************************************/
11 
12 #include "ruby/ruby.h"
13 #include "internal.h"
14 
15 #include <ctype.h>
16 #include <stdio.h>
17 #include <errno.h>
18 #include <math.h>
19 #include <float.h>
20 
21 #ifdef _WIN32
22 #include "missing/file.h"
23 #endif
24 
25 #include "ruby/util.h"
26 
27 unsigned long
28 ruby_scan_oct(const char *start, size_t len, size_t *retlen)
29 {
30  register const char *s = start;
31  register unsigned long retval = 0;
32 
33  while (len-- && *s >= '0' && *s <= '7') {
34  retval <<= 3;
35  retval |= *s++ - '0';
36  }
37  *retlen = (int)(s - start); /* less than len */
38  return retval;
39 }
40 
41 unsigned long
42 ruby_scan_hex(const char *start, size_t len, size_t *retlen)
43 {
44  static const char hexdigit[] = "0123456789abcdef0123456789ABCDEF";
45  register const char *s = start;
46  register unsigned long retval = 0;
47  const char *tmp;
48 
49  while (len-- && *s && (tmp = strchr(hexdigit, *s))) {
50  retval <<= 4;
51  retval |= (tmp - hexdigit) & 15;
52  s++;
53  }
54  *retlen = (int)(s - start); /* less than len */
55  return retval;
56 }
57 
58 static unsigned long
59 scan_digits(const char *str, int base, size_t *retlen, int *overflow)
60 {
61  static signed char table[] = {
62  /* 0 1 2 3 4 5 6 7 8 9 a b c d e f */
63  /*0*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
64  /*1*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
65  /*2*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
66  /*3*/ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,-1,-1,-1,-1,-1,-1,
67  /*4*/ -1,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,
68  /*5*/ 25,26,27,28,29,30,31,32,33,34,35,-1,-1,-1,-1,-1,
69  /*6*/ -1,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,
70  /*7*/ 25,26,27,28,29,30,31,32,33,34,35,-1,-1,-1,-1,-1,
71  /*8*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
72  /*9*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
73  /*a*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
74  /*b*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
75  /*c*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
76  /*d*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
77  /*e*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
78  /*f*/ -1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
79  };
80 
81  const char *start = str;
82  unsigned long ret = 0, x;
83  unsigned long mul_overflow = (~(unsigned long)0) / base;
84  int c;
85  *overflow = 0;
86 
87  while ((c = (unsigned char)*str++) != '\0') {
88  int d = table[c];
89  if (d == -1 || base <= d) {
90  *retlen = (str-1) - start;
91  return ret;
92  }
93  if (mul_overflow < ret)
94  *overflow = 1;
95  ret *= base;
96  x = ret;
97  ret += d;
98  if (ret < x)
99  *overflow = 1;
100  }
101  *retlen = (str-1) - start;
102  return ret;
103 }
104 
105 unsigned long
106 ruby_strtoul(const char *str, char **endptr, int base)
107 {
108  int c, b, overflow;
109  int sign = 0;
110  size_t len;
111  unsigned long ret;
112  const char *subject_found = str;
113 
114  if (base == 1 || 36 < base) {
115  errno = EINVAL;
116  return 0;
117  }
118 
119  while ((c = *str) && ISSPACE(c))
120  str++;
121 
122  if (c == '+') {
123  sign = 1;
124  str++;
125  }
126  else if (c == '-') {
127  sign = -1;
128  str++;
129  }
130 
131  if (str[0] == '0') {
132  subject_found = str+1;
133  if (base == 0 || base == 16) {
134  if (str[1] == 'x' || str[1] == 'X') {
135  b = 16;
136  str += 2;
137  }
138  else {
139  b = base == 0 ? 8 : 16;
140  str++;
141  }
142  }
143  else {
144  b = base;
145  str++;
146  }
147  }
148  else {
149  b = base == 0 ? 10 : base;
150  }
151 
152  ret = scan_digits(str, b, &len, &overflow);
153 
154  if (0 < len)
155  subject_found = str+len;
156 
157  if (endptr)
158  *endptr = (char*)subject_found;
159 
160  if (overflow) {
161  errno = ERANGE;
162  return ULONG_MAX;
163  }
164 
165  if (sign < 0) {
166  ret = (unsigned long)(-(long)ret);
167  return ret;
168  }
169  else {
170  return ret;
171  }
172 }
173 
174 #include <sys/types.h>
175 #include <sys/stat.h>
176 #ifdef HAVE_UNISTD_H
177 #include <unistd.h>
178 #endif
179 #if defined(HAVE_FCNTL_H)
180 #include <fcntl.h>
181 #endif
182 
183 #ifndef S_ISDIR
184 # define S_ISDIR(m) (((m) & S_IFMT) == S_IFDIR)
185 #endif
186 
187 
188 /* mm.c */
189 
190 #define A ((int*)a)
191 #define B ((int*)b)
192 #define C ((int*)c)
193 #define D ((int*)d)
194 
195 #define mmprepare(base, size) do {\
196  if (((VALUE)(base) & (0x3)) == 0)\
197  if ((size) >= 16) mmkind = 1;\
198  else mmkind = 0;\
199  else mmkind = -1;\
200  high = ((size) & (~0xf));\
201  low = ((size) & 0x0c);\
202 } while (0)\
203 
204 #define mmarg mmkind, size, high, low
205 
206 static void mmswap_(register char *a, register char *b, int mmkind, size_t size, size_t high, size_t low)
207 {
208  register int s;
209  if (a == b) return;
210  if (mmkind >= 0) {
211  if (mmkind > 0) {
212  register char *t = a + high;
213  do {
214  s = A[0]; A[0] = B[0]; B[0] = s;
215  s = A[1]; A[1] = B[1]; B[1] = s;
216  s = A[2]; A[2] = B[2]; B[2] = s;
217  s = A[3]; A[3] = B[3]; B[3] = s; a += 16; b += 16;
218  } while (a < t);
219  }
220  if (low != 0) { s = A[0]; A[0] = B[0]; B[0] = s;
221  if (low >= 8) { s = A[1]; A[1] = B[1]; B[1] = s;
222  if (low == 12) {s = A[2]; A[2] = B[2]; B[2] = s;}}}
223  }
224  else {
225  register char *t = a + size;
226  do {s = *a; *a++ = *b; *b++ = s;} while (a < t);
227  }
228 }
229 #define mmswap(a,b) mmswap_((a),(b),mmarg)
230 
231 static void mmrot3_(register char *a, register char *b, register char *c, int mmkind, size_t size, size_t high, size_t low)
232 {
233  register int s;
234  if (mmkind >= 0) {
235  if (mmkind > 0) {
236  register char *t = a + high;
237  do {
238  s = A[0]; A[0] = B[0]; B[0] = C[0]; C[0] = s;
239  s = A[1]; A[1] = B[1]; B[1] = C[1]; C[1] = s;
240  s = A[2]; A[2] = B[2]; B[2] = C[2]; C[2] = s;
241  s = A[3]; A[3] = B[3]; B[3] = C[3]; C[3] = s; a += 16; b += 16; c += 16;
242  } while (a < t);
243  }
244  if (low != 0) { s = A[0]; A[0] = B[0]; B[0] = C[0]; C[0] = s;
245  if (low >= 8) { s = A[1]; A[1] = B[1]; B[1] = C[1]; C[1] = s;
246  if (low == 12) {s = A[2]; A[2] = B[2]; B[2] = C[2]; C[2] = s;}}}
247  }
248  else {
249  register char *t = a + size;
250  do {s = *a; *a++ = *b; *b++ = *c; *c++ = s;} while (a < t);
251  }
252 }
253 #define mmrot3(a,b,c) mmrot3_((a),(b),(c),mmarg)
254 
255 /* qs6.c */
256 /*****************************************************/
257 /* */
258 /* qs6 (Quick sort function) */
259 /* */
260 /* by Tomoyuki Kawamura 1995.4.21 */
261 /* kawamura@tokuyama.ac.jp */
262 /*****************************************************/
263 
264 typedef struct { char *LL, *RR; } stack_node; /* Stack structure for L,l,R,r */
265 #define PUSH(ll,rr) do { top->LL = (ll); top->RR = (rr); ++top; } while (0) /* Push L,l,R,r */
266 #define POP(ll,rr) do { --top; (ll) = top->LL; (rr) = top->RR; } while (0) /* Pop L,l,R,r */
267 
268 #define med3(a,b,c) ((*cmp)((a),(b),d)<0 ? \
269  ((*cmp)((b),(c),d)<0 ? (b) : ((*cmp)((a),(c),d)<0 ? (c) : (a))) : \
270  ((*cmp)((b),(c),d)>0 ? (b) : ((*cmp)((a),(c),d)<0 ? (a) : (c))))
271 
272 void
273 ruby_qsort(void* base, const size_t nel, const size_t size,
274  int (*cmp)(const void*, const void*, void*), void *d)
275 {
276  register char *l, *r, *m; /* l,r:left,right group m:median point */
277  register int t, eq_l, eq_r; /* eq_l: all items in left group are equal to S */
278  char *L = base; /* left end of current region */
279  char *R = (char*)base + size*(nel-1); /* right end of current region */
280  size_t chklim = 63; /* threshold of ordering element check */
281  enum {size_bits = sizeof(size) * CHAR_BIT};
282  stack_node stack[size_bits]; /* enough for size_t size */
283  stack_node *top = stack;
284  int mmkind;
285  size_t high, low, n;
286 
287  if (nel <= 1) return; /* need not to sort */
288  mmprepare(base, size);
289  goto start;
290 
291  nxt:
292  if (stack == top) return; /* return if stack is empty */
293  POP(L,R);
294 
295  for (;;) {
296  start:
297  if (L + size == R) { /* 2 elements */
298  if ((*cmp)(L,R,d) > 0) mmswap(L,R); goto nxt;
299  }
300 
301  l = L; r = R;
302  n = (r - l + size) / size; /* number of elements */
303  m = l + size * (n >> 1); /* calculate median value */
304 
305  if (n >= 60) {
306  register char *m1;
307  register char *m3;
308  if (n >= 200) {
309  n = size*(n>>3); /* number of bytes in splitting 8 */
310  {
311  register char *p1 = l + n;
312  register char *p2 = p1 + n;
313  register char *p3 = p2 + n;
314  m1 = med3(p1, p2, p3);
315  p1 = m + n;
316  p2 = p1 + n;
317  p3 = p2 + n;
318  m3 = med3(p1, p2, p3);
319  }
320  }
321  else {
322  n = size*(n>>2); /* number of bytes in splitting 4 */
323  m1 = l + n;
324  m3 = m + n;
325  }
326  m = med3(m1, m, m3);
327  }
328 
329  if ((t = (*cmp)(l,m,d)) < 0) { /*3-5-?*/
330  if ((t = (*cmp)(m,r,d)) < 0) { /*3-5-7*/
331  if (chklim && nel >= chklim) { /* check if already ascending order */
332  char *p;
333  chklim = 0;
334  for (p=l; p<r; p+=size) if ((*cmp)(p,p+size,d) > 0) goto fail;
335  goto nxt;
336  }
337  fail: goto loopA; /*3-5-7*/
338  }
339  if (t > 0) {
340  if ((*cmp)(l,r,d) <= 0) {mmswap(m,r); goto loopA;} /*3-5-4*/
341  mmrot3(r,m,l); goto loopA; /*3-5-2*/
342  }
343  goto loopB; /*3-5-5*/
344  }
345 
346  if (t > 0) { /*7-5-?*/
347  if ((t = (*cmp)(m,r,d)) > 0) { /*7-5-3*/
348  if (chklim && nel >= chklim) { /* check if already ascending order */
349  char *p;
350  chklim = 0;
351  for (p=l; p<r; p+=size) if ((*cmp)(p,p+size,d) < 0) goto fail2;
352  while (l<r) {mmswap(l,r); l+=size; r-=size;} /* reverse region */
353  goto nxt;
354  }
355  fail2: mmswap(l,r); goto loopA; /*7-5-3*/
356  }
357  if (t < 0) {
358  if ((*cmp)(l,r,d) <= 0) {mmswap(l,m); goto loopB;} /*7-5-8*/
359  mmrot3(l,m,r); goto loopA; /*7-5-6*/
360  }
361  mmswap(l,r); goto loopA; /*7-5-5*/
362  }
363 
364  if ((t = (*cmp)(m,r,d)) < 0) {goto loopA;} /*5-5-7*/
365  if (t > 0) {mmswap(l,r); goto loopB;} /*5-5-3*/
366 
367  /* determining splitting type in case 5-5-5 */ /*5-5-5*/
368  for (;;) {
369  if ((l += size) == r) goto nxt; /*5-5-5*/
370  if (l == m) continue;
371  if ((t = (*cmp)(l,m,d)) > 0) {mmswap(l,r); l = L; goto loopA;}/*575-5*/
372  if (t < 0) {mmswap(L,l); l = L; goto loopB;} /*535-5*/
373  }
374 
375  loopA: eq_l = 1; eq_r = 1; /* splitting type A */ /* left <= median < right */
376  for (;;) {
377  for (;;) {
378  if ((l += size) == r)
379  {l -= size; if (l != m) mmswap(m,l); l -= size; goto fin;}
380  if (l == m) continue;
381  if ((t = (*cmp)(l,m,d)) > 0) {eq_r = 0; break;}
382  if (t < 0) eq_l = 0;
383  }
384  for (;;) {
385  if (l == (r -= size))
386  {l -= size; if (l != m) mmswap(m,l); l -= size; goto fin;}
387  if (r == m) {m = l; break;}
388  if ((t = (*cmp)(r,m,d)) < 0) {eq_l = 0; break;}
389  if (t == 0) break;
390  }
391  mmswap(l,r); /* swap left and right */
392  }
393 
394  loopB: eq_l = 1; eq_r = 1; /* splitting type B */ /* left < median <= right */
395  for (;;) {
396  for (;;) {
397  if (l == (r -= size))
398  {r += size; if (r != m) mmswap(r,m); r += size; goto fin;}
399  if (r == m) continue;
400  if ((t = (*cmp)(r,m,d)) < 0) {eq_l = 0; break;}
401  if (t > 0) eq_r = 0;
402  }
403  for (;;) {
404  if ((l += size) == r)
405  {r += size; if (r != m) mmswap(r,m); r += size; goto fin;}
406  if (l == m) {m = r; break;}
407  if ((t = (*cmp)(l,m,d)) > 0) {eq_r = 0; break;}
408  if (t == 0) break;
409  }
410  mmswap(l,r); /* swap left and right */
411  }
412 
413  fin:
414  if (eq_l == 0) /* need to sort left side */
415  if (eq_r == 0) /* need to sort right side */
416  if (l-L < R-r) {PUSH(r,R); R = l;} /* sort left side first */
417  else {PUSH(L,l); L = r;} /* sort right side first */
418  else R = l; /* need to sort left side only */
419  else if (eq_r == 0) L = r; /* need to sort right side only */
420  else goto nxt; /* need not to sort both sides */
421  }
422 }
423 
424 char *
425 ruby_strdup(const char *str)
426 {
427  char *tmp;
428  size_t len = strlen(str) + 1;
429 
430  tmp = xmalloc(len);
431  memcpy(tmp, str, len);
432 
433  return tmp;
434 }
435 
436 char *
438 {
439 #ifdef HAVE_GETCWD
440  int size = 200;
441  char *buf = xmalloc(size);
442 
443  while (!getcwd(buf, size)) {
444  if (errno != ERANGE) {
445  xfree(buf);
446  rb_sys_fail("getcwd");
447  }
448  size *= 2;
449  buf = xrealloc(buf, size);
450  }
451 #else
452 # ifndef PATH_MAX
453 # define PATH_MAX 8192
454 # endif
455  char *buf = xmalloc(PATH_MAX+1);
456 
457  if (!getwd(buf)) {
458  xfree(buf);
459  rb_sys_fail("getwd");
460  }
461 #endif
462  return buf;
463 }
464 
465 /****************************************************************
466  *
467  * The author of this software is David M. Gay.
468  *
469  * Copyright (c) 1991, 2000, 2001 by Lucent Technologies.
470  *
471  * Permission to use, copy, modify, and distribute this software for any
472  * purpose without fee is hereby granted, provided that this entire notice
473  * is included in all copies of any software which is or includes a copy
474  * or modification of this software and in all copies of the supporting
475  * documentation for such software.
476  *
477  * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
478  * WARRANTY. IN PARTICULAR, NEITHER THE AUTHOR NOR LUCENT MAKES ANY
479  * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
480  * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
481  *
482  ***************************************************************/
483 
484 /* Please send bug reports to David M. Gay (dmg at acm dot org,
485  * with " at " changed at "@" and " dot " changed to "."). */
486 
487 /* On a machine with IEEE extended-precision registers, it is
488  * necessary to specify double-precision (53-bit) rounding precision
489  * before invoking strtod or dtoa. If the machine uses (the equivalent
490  * of) Intel 80x87 arithmetic, the call
491  * _control87(PC_53, MCW_PC);
492  * does this with many compilers. Whether this or another call is
493  * appropriate depends on the compiler; for this to work, it may be
494  * necessary to #include "float.h" or another system-dependent header
495  * file.
496  */
497 
498 /* strtod for IEEE-, VAX-, and IBM-arithmetic machines.
499  *
500  * This strtod returns a nearest machine number to the input decimal
501  * string (or sets errno to ERANGE). With IEEE arithmetic, ties are
502  * broken by the IEEE round-even rule. Otherwise ties are broken by
503  * biased rounding (add half and chop).
504  *
505  * Inspired loosely by William D. Clinger's paper "How to Read Floating
506  * Point Numbers Accurately" [Proc. ACM SIGPLAN '90, pp. 92-101].
507  *
508  * Modifications:
509  *
510  * 1. We only require IEEE, IBM, or VAX double-precision
511  * arithmetic (not IEEE double-extended).
512  * 2. We get by with floating-point arithmetic in a case that
513  * Clinger missed -- when we're computing d * 10^n
514  * for a small integer d and the integer n is not too
515  * much larger than 22 (the maximum integer k for which
516  * we can represent 10^k exactly), we may be able to
517  * compute (d*10^k) * 10^(e-k) with just one roundoff.
518  * 3. Rather than a bit-at-a-time adjustment of the binary
519  * result in the hard case, we use floating-point
520  * arithmetic to determine the adjustment to within
521  * one bit; only in really hard cases do we need to
522  * compute a second residual.
523  * 4. Because of 3., we don't need a large table of powers of 10
524  * for ten-to-e (just some small tables, e.g. of 10^k
525  * for 0 <= k <= 22).
526  */
527 
528 /*
529  * #define IEEE_LITTLE_ENDIAN for IEEE-arithmetic machines where the least
530  * significant byte has the lowest address.
531  * #define IEEE_BIG_ENDIAN for IEEE-arithmetic machines where the most
532  * significant byte has the lowest address.
533  * #define Long int on machines with 32-bit ints and 64-bit longs.
534  * #define IBM for IBM mainframe-style floating-point arithmetic.
535  * #define VAX for VAX-style floating-point arithmetic (D_floating).
536  * #define No_leftright to omit left-right logic in fast floating-point
537  * computation of dtoa.
538  * #define Honor_FLT_ROUNDS if FLT_ROUNDS can assume the values 2 or 3
539  * and strtod and dtoa should round accordingly.
540  * #define Check_FLT_ROUNDS if FLT_ROUNDS can assume the values 2 or 3
541  * and Honor_FLT_ROUNDS is not #defined.
542  * #define RND_PRODQUOT to use rnd_prod and rnd_quot (assembly routines
543  * that use extended-precision instructions to compute rounded
544  * products and quotients) with IBM.
545  * #define ROUND_BIASED for IEEE-format with biased rounding.
546  * #define Inaccurate_Divide for IEEE-format with correctly rounded
547  * products but inaccurate quotients, e.g., for Intel i860.
548  * #define NO_LONG_LONG on machines that do not have a "long long"
549  * integer type (of >= 64 bits). On such machines, you can
550  * #define Just_16 to store 16 bits per 32-bit Long when doing
551  * high-precision integer arithmetic. Whether this speeds things
552  * up or slows things down depends on the machine and the number
553  * being converted. If long long is available and the name is
554  * something other than "long long", #define Llong to be the name,
555  * and if "unsigned Llong" does not work as an unsigned version of
556  * Llong, #define #ULLong to be the corresponding unsigned type.
557  * #define KR_headers for old-style C function headers.
558  * #define Bad_float_h if your system lacks a float.h or if it does not
559  * define some or all of DBL_DIG, DBL_MAX_10_EXP, DBL_MAX_EXP,
560  * FLT_RADIX, FLT_ROUNDS, and DBL_MAX.
561  * #define MALLOC your_malloc, where your_malloc(n) acts like malloc(n)
562  * if memory is available and otherwise does something you deem
563  * appropriate. If MALLOC is undefined, malloc will be invoked
564  * directly -- and assumed always to succeed.
565  * #define Omit_Private_Memory to omit logic (added Jan. 1998) for making
566  * memory allocations from a private pool of memory when possible.
567  * When used, the private pool is PRIVATE_MEM bytes long: 2304 bytes,
568  * unless #defined to be a different length. This default length
569  * suffices to get rid of MALLOC calls except for unusual cases,
570  * such as decimal-to-binary conversion of a very long string of
571  * digits. The longest string dtoa can return is about 751 bytes
572  * long. For conversions by strtod of strings of 800 digits and
573  * all dtoa conversions in single-threaded executions with 8-byte
574  * pointers, PRIVATE_MEM >= 7400 appears to suffice; with 4-byte
575  * pointers, PRIVATE_MEM >= 7112 appears adequate.
576  * #define INFNAN_CHECK on IEEE systems to cause strtod to check for
577  * Infinity and NaN (case insensitively). On some systems (e.g.,
578  * some HP systems), it may be necessary to #define NAN_WORD0
579  * appropriately -- to the most significant word of a quiet NaN.
580  * (On HP Series 700/800 machines, -DNAN_WORD0=0x7ff40000 works.)
581  * When INFNAN_CHECK is #defined and No_Hex_NaN is not #defined,
582  * strtod also accepts (case insensitively) strings of the form
583  * NaN(x), where x is a string of hexadecimal digits and spaces;
584  * if there is only one string of hexadecimal digits, it is taken
585  * for the 52 fraction bits of the resulting NaN; if there are two
586  * or more strings of hex digits, the first is for the high 20 bits,
587  * the second and subsequent for the low 32 bits, with intervening
588  * white space ignored; but if this results in none of the 52
589  * fraction bits being on (an IEEE Infinity symbol), then NAN_WORD0
590  * and NAN_WORD1 are used instead.
591  * #define MULTIPLE_THREADS if the system offers preemptively scheduled
592  * multiple threads. In this case, you must provide (or suitably
593  * #define) two locks, acquired by ACQUIRE_DTOA_LOCK(n) and freed
594  * by FREE_DTOA_LOCK(n) for n = 0 or 1. (The second lock, accessed
595  * in pow5mult, ensures lazy evaluation of only one copy of high
596  * powers of 5; omitting this lock would introduce a small
597  * probability of wasting memory, but would otherwise be harmless.)
598  * You must also invoke freedtoa(s) to free the value s returned by
599  * dtoa. You may do so whether or not MULTIPLE_THREADS is #defined.
600  * #define NO_IEEE_Scale to disable new (Feb. 1997) logic in strtod that
601  * avoids underflows on inputs whose result does not underflow.
602  * If you #define NO_IEEE_Scale on a machine that uses IEEE-format
603  * floating-point numbers and flushes underflows to zero rather
604  * than implementing gradual underflow, then you must also #define
605  * Sudden_Underflow.
606  * #define YES_ALIAS to permit aliasing certain double values with
607  * arrays of ULongs. This leads to slightly better code with
608  * some compilers and was always used prior to 19990916, but it
609  * is not strictly legal and can cause trouble with aggressively
610  * optimizing compilers (e.g., gcc 2.95.1 under -O2).
611  * #define USE_LOCALE to use the current locale's decimal_point value.
612  * #define SET_INEXACT if IEEE arithmetic is being used and extra
613  * computation should be done to set the inexact flag when the
614  * result is inexact and avoid setting inexact when the result
615  * is exact. In this case, dtoa.c must be compiled in
616  * an environment, perhaps provided by #include "dtoa.c" in a
617  * suitable wrapper, that defines two functions,
618  * int get_inexact(void);
619  * void clear_inexact(void);
620  * such that get_inexact() returns a nonzero value if the
621  * inexact bit is already set, and clear_inexact() sets the
622  * inexact bit to 0. When SET_INEXACT is #defined, strtod
623  * also does extra computations to set the underflow and overflow
624  * flags when appropriate (i.e., when the result is tiny and
625  * inexact or when it is a numeric value rounded to +-infinity).
626  * #define NO_ERRNO if strtod should not assign errno = ERANGE when
627  * the result overflows to +-Infinity or underflows to 0.
628  */
629 
630 #ifdef WORDS_BIGENDIAN
631 #define IEEE_BIG_ENDIAN
632 #else
633 #define IEEE_LITTLE_ENDIAN
634 #endif
635 
636 #ifdef __vax__
637 #define VAX
638 #undef IEEE_BIG_ENDIAN
639 #undef IEEE_LITTLE_ENDIAN
640 #endif
641 
642 #if defined(__arm__) && !defined(__VFP_FP__)
643 #define IEEE_BIG_ENDIAN
644 #undef IEEE_LITTLE_ENDIAN
645 #endif
646 
647 #undef Long
648 #undef ULong
649 
650 #if SIZEOF_INT == 4
651 #define Long int
652 #define ULong unsigned int
653 #elif SIZEOF_LONG == 4
654 #define Long long int
655 #define ULong unsigned long int
656 #endif
657 
658 #if HAVE_LONG_LONG
659 #define Llong LONG_LONG
660 #endif
661 
662 #ifdef DEBUG
663 #include "stdio.h"
664 #define Bug(x) {fprintf(stderr, "%s\n", (x)); exit(EXIT_FAILURE);}
665 #endif
666 
667 #include "stdlib.h"
668 #include "string.h"
669 
670 #ifdef USE_LOCALE
671 #include "locale.h"
672 #endif
673 
674 #ifdef MALLOC
675 extern void *MALLOC(size_t);
676 #else
677 #define MALLOC malloc
678 #endif
679 #ifdef FREE
680 extern void FREE(void*);
681 #else
682 #define FREE free
683 #endif
684 
685 #ifndef Omit_Private_Memory
686 #ifndef PRIVATE_MEM
687 #define PRIVATE_MEM 2304
688 #endif
689 #define PRIVATE_mem ((PRIVATE_MEM+sizeof(double)-1)/sizeof(double))
691 #endif
692 
693 #undef IEEE_Arith
694 #undef Avoid_Underflow
695 #ifdef IEEE_BIG_ENDIAN
696 #define IEEE_Arith
697 #endif
698 #ifdef IEEE_LITTLE_ENDIAN
699 #define IEEE_Arith
700 #endif
701 
702 #ifdef Bad_float_h
703 
704 #ifdef IEEE_Arith
705 #define DBL_DIG 15
706 #define DBL_MAX_10_EXP 308
707 #define DBL_MAX_EXP 1024
708 #define FLT_RADIX 2
709 #endif /*IEEE_Arith*/
710 
711 #ifdef IBM
712 #define DBL_DIG 16
713 #define DBL_MAX_10_EXP 75
714 #define DBL_MAX_EXP 63
715 #define FLT_RADIX 16
716 #define DBL_MAX 7.2370055773322621e+75
717 #endif
718 
719 #ifdef VAX
720 #define DBL_DIG 16
721 #define DBL_MAX_10_EXP 38
722 #define DBL_MAX_EXP 127
723 #define FLT_RADIX 2
724 #define DBL_MAX 1.7014118346046923e+38
725 #endif
726 
727 #ifndef LONG_MAX
728 #define LONG_MAX 2147483647
729 #endif
730 
731 #else /* ifndef Bad_float_h */
732 #include "float.h"
733 #endif /* Bad_float_h */
734 
735 #ifndef __MATH_H__
736 #include "math.h"
737 #endif
738 
739 #ifdef __cplusplus
740 extern "C" {
741 #if 0
742 }
743 #endif
744 #endif
745 
746 #if defined(IEEE_LITTLE_ENDIAN) + defined(IEEE_BIG_ENDIAN) + defined(VAX) + defined(IBM) != 1
747 Exactly one of IEEE_LITTLE_ENDIAN, IEEE_BIG_ENDIAN, VAX, or IBM should be defined.
748 #endif
749 
750 typedef union { double d; ULong L[2]; } U;
751 
752 #ifdef YES_ALIAS
753 typedef double double_u;
754 # define dval(x) (x)
755 # ifdef IEEE_LITTLE_ENDIAN
756 # define word0(x) (((ULong *)&(x))[1])
757 # define word1(x) (((ULong *)&(x))[0])
758 # else
759 # define word0(x) (((ULong *)&(x))[0])
760 # define word1(x) (((ULong *)&(x))[1])
761 # endif
762 #else
763 typedef U double_u;
764 # ifdef IEEE_LITTLE_ENDIAN
765 # define word0(x) ((x).L[1])
766 # define word1(x) ((x).L[0])
767 # else
768 # define word0(x) ((x).L[0])
769 # define word1(x) ((x).L[1])
770 # endif
771 # define dval(x) ((x).d)
772 #endif
773 
774 /* The following definition of Storeinc is appropriate for MIPS processors.
775  * An alternative that might be better on some machines is
776  * #define Storeinc(a,b,c) (*a++ = b << 16 | c & 0xffff)
777  */
778 #if defined(IEEE_LITTLE_ENDIAN) + defined(VAX) + defined(__arm__)
779 #define Storeinc(a,b,c) (((unsigned short *)(a))[1] = (unsigned short)(b), \
780 ((unsigned short *)(a))[0] = (unsigned short)(c), (a)++)
781 #else
782 #define Storeinc(a,b,c) (((unsigned short *)(a))[0] = (unsigned short)(b), \
783 ((unsigned short *)(a))[1] = (unsigned short)(c), (a)++)
784 #endif
785 
786 /* #define P DBL_MANT_DIG */
787 /* Ten_pmax = floor(P*log(2)/log(5)) */
788 /* Bletch = (highest power of 2 < DBL_MAX_10_EXP) / 16 */
789 /* Quick_max = floor((P-1)*log(FLT_RADIX)/log(10) - 1) */
790 /* Int_max = floor(P*log(FLT_RADIX)/log(10) - 1) */
791 
792 #ifdef IEEE_Arith
793 #define Exp_shift 20
794 #define Exp_shift1 20
795 #define Exp_msk1 0x100000
796 #define Exp_msk11 0x100000
797 #define Exp_mask 0x7ff00000
798 #define P 53
799 #define Bias 1023
800 #define Emin (-1022)
801 #define Exp_1 0x3ff00000
802 #define Exp_11 0x3ff00000
803 #define Ebits 11
804 #define Frac_mask 0xfffff
805 #define Frac_mask1 0xfffff
806 #define Ten_pmax 22
807 #define Bletch 0x10
808 #define Bndry_mask 0xfffff
809 #define Bndry_mask1 0xfffff
810 #define LSB 1
811 #define Sign_bit 0x80000000
812 #define Log2P 1
813 #define Tiny0 0
814 #define Tiny1 1
815 #define Quick_max 14
816 #define Int_max 14
817 #ifndef NO_IEEE_Scale
818 #define Avoid_Underflow
819 #ifdef Flush_Denorm /* debugging option */
820 #undef Sudden_Underflow
821 #endif
822 #endif
823 
824 #ifndef Flt_Rounds
825 #ifdef FLT_ROUNDS
826 #define Flt_Rounds FLT_ROUNDS
827 #else
828 #define Flt_Rounds 1
829 #endif
830 #endif /*Flt_Rounds*/
831 
832 #ifdef Honor_FLT_ROUNDS
833 #define Rounding rounding
834 #undef Check_FLT_ROUNDS
835 #define Check_FLT_ROUNDS
836 #else
837 #define Rounding Flt_Rounds
838 #endif
839 
840 #else /* ifndef IEEE_Arith */
841 #undef Check_FLT_ROUNDS
842 #undef Honor_FLT_ROUNDS
843 #undef SET_INEXACT
844 #undef Sudden_Underflow
845 #define Sudden_Underflow
846 #ifdef IBM
847 #undef Flt_Rounds
848 #define Flt_Rounds 0
849 #define Exp_shift 24
850 #define Exp_shift1 24
851 #define Exp_msk1 0x1000000
852 #define Exp_msk11 0x1000000
853 #define Exp_mask 0x7f000000
854 #define P 14
855 #define Bias 65
856 #define Exp_1 0x41000000
857 #define Exp_11 0x41000000
858 #define Ebits 8 /* exponent has 7 bits, but 8 is the right value in b2d */
859 #define Frac_mask 0xffffff
860 #define Frac_mask1 0xffffff
861 #define Bletch 4
862 #define Ten_pmax 22
863 #define Bndry_mask 0xefffff
864 #define Bndry_mask1 0xffffff
865 #define LSB 1
866 #define Sign_bit 0x80000000
867 #define Log2P 4
868 #define Tiny0 0x100000
869 #define Tiny1 0
870 #define Quick_max 14
871 #define Int_max 15
872 #else /* VAX */
873 #undef Flt_Rounds
874 #define Flt_Rounds 1
875 #define Exp_shift 23
876 #define Exp_shift1 7
877 #define Exp_msk1 0x80
878 #define Exp_msk11 0x800000
879 #define Exp_mask 0x7f80
880 #define P 56
881 #define Bias 129
882 #define Exp_1 0x40800000
883 #define Exp_11 0x4080
884 #define Ebits 8
885 #define Frac_mask 0x7fffff
886 #define Frac_mask1 0xffff007f
887 #define Ten_pmax 24
888 #define Bletch 2
889 #define Bndry_mask 0xffff007f
890 #define Bndry_mask1 0xffff007f
891 #define LSB 0x10000
892 #define Sign_bit 0x8000
893 #define Log2P 1
894 #define Tiny0 0x80
895 #define Tiny1 0
896 #define Quick_max 15
897 #define Int_max 15
898 #endif /* IBM, VAX */
899 #endif /* IEEE_Arith */
900 
901 #ifndef IEEE_Arith
902 #define ROUND_BIASED
903 #endif
904 
905 #ifdef RND_PRODQUOT
906 #define rounded_product(a,b) ((a) = rnd_prod((a), (b)))
907 #define rounded_quotient(a,b) ((a) = rnd_quot((a), (b)))
908 extern double rnd_prod(double, double), rnd_quot(double, double);
909 #else
910 #define rounded_product(a,b) ((a) *= (b))
911 #define rounded_quotient(a,b) ((a) /= (b))
912 #endif
913 
914 #define Big0 (Frac_mask1 | Exp_msk1*(DBL_MAX_EXP+Bias-1))
915 #define Big1 0xffffffff
916 
917 #ifndef Pack_32
918 #define Pack_32
919 #endif
920 
921 #define FFFFFFFF 0xffffffffUL
922 
923 #ifdef NO_LONG_LONG
924 #undef ULLong
925 #ifdef Just_16
926 #undef Pack_32
927 /* When Pack_32 is not defined, we store 16 bits per 32-bit Long.
928  * This makes some inner loops simpler and sometimes saves work
929  * during multiplications, but it often seems to make things slightly
930  * slower. Hence the default is now to store 32 bits per Long.
931  */
932 #endif
933 #else /* long long available */
934 #ifndef Llong
935 #define Llong long long
936 #endif
937 #ifndef ULLong
938 #define ULLong unsigned Llong
939 #endif
940 #endif /* NO_LONG_LONG */
941 
942 #define MULTIPLE_THREADS 1
943 
944 #ifndef MULTIPLE_THREADS
945 #define ACQUIRE_DTOA_LOCK(n) /*nothing*/
946 #define FREE_DTOA_LOCK(n) /*nothing*/
947 #else
948 #define ACQUIRE_DTOA_LOCK(n) /*unused right now*/
949 #define FREE_DTOA_LOCK(n) /*unused right now*/
950 #endif
951 
952 #define Kmax 15
953 
954 struct Bigint {
955  struct Bigint *next;
956  int k, maxwds, sign, wds;
957  ULong x[1];
958 };
959 
960 typedef struct Bigint Bigint;
961 
962 static Bigint *freelist[Kmax+1];
963 
964 static Bigint *
965 Balloc(int k)
966 {
967  int x;
968  Bigint *rv;
969 #ifndef Omit_Private_Memory
970  size_t len;
971 #endif
972 
974  if (k <= Kmax && (rv = freelist[k]) != 0) {
975  freelist[k] = rv->next;
976  }
977  else {
978  x = 1 << k;
979 #ifdef Omit_Private_Memory
980  rv = (Bigint *)MALLOC(sizeof(Bigint) + (x-1)*sizeof(ULong));
981 #else
982  len = (sizeof(Bigint) + (x-1)*sizeof(ULong) + sizeof(double) - 1)
983  /sizeof(double);
984  if (k <= Kmax && pmem_next - private_mem + len <= PRIVATE_mem) {
985  rv = (Bigint*)pmem_next;
986  pmem_next += len;
987  }
988  else
989  rv = (Bigint*)MALLOC(len*sizeof(double));
990 #endif
991  rv->k = k;
992  rv->maxwds = x;
993  }
994  FREE_DTOA_LOCK(0);
995  rv->sign = rv->wds = 0;
996  return rv;
997 }
998 
999 static void
1001 {
1002  if (v) {
1003  if (v->k > Kmax) {
1004  FREE(v);
1005  return;
1006  }
1007  ACQUIRE_DTOA_LOCK(0);
1008  v->next = freelist[v->k];
1009  freelist[v->k] = v;
1010  FREE_DTOA_LOCK(0);
1011  }
1012 }
1013 
1014 #define Bcopy(x,y) memcpy((char *)&(x)->sign, (char *)&(y)->sign, \
1015 (y)->wds*sizeof(Long) + 2*sizeof(int))
1016 
1017 static Bigint *
1018 multadd(Bigint *b, int m, int a) /* multiply by m and add a */
1019 {
1020  int i, wds;
1021  ULong *x;
1022 #ifdef ULLong
1023  ULLong carry, y;
1024 #else
1025  ULong carry, y;
1026 #ifdef Pack_32
1027  ULong xi, z;
1028 #endif
1029 #endif
1030  Bigint *b1;
1031 
1032  wds = b->wds;
1033  x = b->x;
1034  i = 0;
1035  carry = a;
1036  do {
1037 #ifdef ULLong
1038  y = *x * (ULLong)m + carry;
1039  carry = y >> 32;
1040  *x++ = (ULong)(y & FFFFFFFF);
1041 #else
1042 #ifdef Pack_32
1043  xi = *x;
1044  y = (xi & 0xffff) * m + carry;
1045  z = (xi >> 16) * m + (y >> 16);
1046  carry = z >> 16;
1047  *x++ = (z << 16) + (y & 0xffff);
1048 #else
1049  y = *x * m + carry;
1050  carry = y >> 16;
1051  *x++ = y & 0xffff;
1052 #endif
1053 #endif
1054  } while (++i < wds);
1055  if (carry) {
1056  if (wds >= b->maxwds) {
1057  b1 = Balloc(b->k+1);
1058  Bcopy(b1, b);
1059  Bfree(b);
1060  b = b1;
1061  }
1062  b->x[wds++] = (ULong)carry;
1063  b->wds = wds;
1064  }
1065  return b;
1066 }
1067 
1068 static Bigint *
1069 s2b(const char *s, int nd0, int nd, ULong y9)
1070 {
1071  Bigint *b;
1072  int i, k;
1073  Long x, y;
1074 
1075  x = (nd + 8) / 9;
1076  for (k = 0, y = 1; x > y; y <<= 1, k++) ;
1077 #ifdef Pack_32
1078  b = Balloc(k);
1079  b->x[0] = y9;
1080  b->wds = 1;
1081 #else
1082  b = Balloc(k+1);
1083  b->x[0] = y9 & 0xffff;
1084  b->wds = (b->x[1] = y9 >> 16) ? 2 : 1;
1085 #endif
1086 
1087  i = 9;
1088  if (9 < nd0) {
1089  s += 9;
1090  do {
1091  b = multadd(b, 10, *s++ - '0');
1092  } while (++i < nd0);
1093  s++;
1094  }
1095  else
1096  s += 10;
1097  for (; i < nd; i++)
1098  b = multadd(b, 10, *s++ - '0');
1099  return b;
1100 }
1101 
1102 static int
1103 hi0bits(register ULong x)
1104 {
1105  register int k = 0;
1106 
1107  if (!(x & 0xffff0000)) {
1108  k = 16;
1109  x <<= 16;
1110  }
1111  if (!(x & 0xff000000)) {
1112  k += 8;
1113  x <<= 8;
1114  }
1115  if (!(x & 0xf0000000)) {
1116  k += 4;
1117  x <<= 4;
1118  }
1119  if (!(x & 0xc0000000)) {
1120  k += 2;
1121  x <<= 2;
1122  }
1123  if (!(x & 0x80000000)) {
1124  k++;
1125  if (!(x & 0x40000000))
1126  return 32;
1127  }
1128  return k;
1129 }
1130 
1131 static int
1132 lo0bits(ULong *y)
1133 {
1134  register int k;
1135  register ULong x = *y;
1136 
1137  if (x & 7) {
1138  if (x & 1)
1139  return 0;
1140  if (x & 2) {
1141  *y = x >> 1;
1142  return 1;
1143  }
1144  *y = x >> 2;
1145  return 2;
1146  }
1147  k = 0;
1148  if (!(x & 0xffff)) {
1149  k = 16;
1150  x >>= 16;
1151  }
1152  if (!(x & 0xff)) {
1153  k += 8;
1154  x >>= 8;
1155  }
1156  if (!(x & 0xf)) {
1157  k += 4;
1158  x >>= 4;
1159  }
1160  if (!(x & 0x3)) {
1161  k += 2;
1162  x >>= 2;
1163  }
1164  if (!(x & 1)) {
1165  k++;
1166  x >>= 1;
1167  if (!x)
1168  return 32;
1169  }
1170  *y = x;
1171  return k;
1172 }
1173 
1174 static Bigint *
1175 i2b(int i)
1176 {
1177  Bigint *b;
1178 
1179  b = Balloc(1);
1180  b->x[0] = i;
1181  b->wds = 1;
1182  return b;
1183 }
1184 
1185 static Bigint *
1187 {
1188  Bigint *c;
1189  int k, wa, wb, wc;
1190  ULong *x, *xa, *xae, *xb, *xbe, *xc, *xc0;
1191  ULong y;
1192 #ifdef ULLong
1193  ULLong carry, z;
1194 #else
1195  ULong carry, z;
1196 #ifdef Pack_32
1197  ULong z2;
1198 #endif
1199 #endif
1200 
1201  if (a->wds < b->wds) {
1202  c = a;
1203  a = b;
1204  b = c;
1205  }
1206  k = a->k;
1207  wa = a->wds;
1208  wb = b->wds;
1209  wc = wa + wb;
1210  if (wc > a->maxwds)
1211  k++;
1212  c = Balloc(k);
1213  for (x = c->x, xa = x + wc; x < xa; x++)
1214  *x = 0;
1215  xa = a->x;
1216  xae = xa + wa;
1217  xb = b->x;
1218  xbe = xb + wb;
1219  xc0 = c->x;
1220 #ifdef ULLong
1221  for (; xb < xbe; xc0++) {
1222  if ((y = *xb++) != 0) {
1223  x = xa;
1224  xc = xc0;
1225  carry = 0;
1226  do {
1227  z = *x++ * (ULLong)y + *xc + carry;
1228  carry = z >> 32;
1229  *xc++ = (ULong)(z & FFFFFFFF);
1230  } while (x < xae);
1231  *xc = (ULong)carry;
1232  }
1233  }
1234 #else
1235 #ifdef Pack_32
1236  for (; xb < xbe; xb++, xc0++) {
1237  if (y = *xb & 0xffff) {
1238  x = xa;
1239  xc = xc0;
1240  carry = 0;
1241  do {
1242  z = (*x & 0xffff) * y + (*xc & 0xffff) + carry;
1243  carry = z >> 16;
1244  z2 = (*x++ >> 16) * y + (*xc >> 16) + carry;
1245  carry = z2 >> 16;
1246  Storeinc(xc, z2, z);
1247  } while (x < xae);
1248  *xc = (ULong)carry;
1249  }
1250  if (y = *xb >> 16) {
1251  x = xa;
1252  xc = xc0;
1253  carry = 0;
1254  z2 = *xc;
1255  do {
1256  z = (*x & 0xffff) * y + (*xc >> 16) + carry;
1257  carry = z >> 16;
1258  Storeinc(xc, z, z2);
1259  z2 = (*x++ >> 16) * y + (*xc & 0xffff) + carry;
1260  carry = z2 >> 16;
1261  } while (x < xae);
1262  *xc = z2;
1263  }
1264  }
1265 #else
1266  for (; xb < xbe; xc0++) {
1267  if (y = *xb++) {
1268  x = xa;
1269  xc = xc0;
1270  carry = 0;
1271  do {
1272  z = *x++ * y + *xc + carry;
1273  carry = z >> 16;
1274  *xc++ = z & 0xffff;
1275  } while (x < xae);
1276  *xc = (ULong)carry;
1277  }
1278  }
1279 #endif
1280 #endif
1281  for (xc0 = c->x, xc = xc0 + wc; wc > 0 && !*--xc; --wc) ;
1282  c->wds = wc;
1283  return c;
1284 }
1285 
1286 static Bigint *p5s;
1287 
1288 static Bigint *
1290 {
1291  Bigint *b1, *p5, *p51;
1292  int i;
1293  static int p05[3] = { 5, 25, 125 };
1294 
1295  if ((i = k & 3) != 0)
1296  b = multadd(b, p05[i-1], 0);
1297 
1298  if (!(k >>= 2))
1299  return b;
1300  if (!(p5 = p5s)) {
1301  /* first time */
1302 #ifdef MULTIPLE_THREADS
1303  ACQUIRE_DTOA_LOCK(1);
1304  if (!(p5 = p5s)) {
1305  p5 = p5s = i2b(625);
1306  p5->next = 0;
1307  }
1308  FREE_DTOA_LOCK(1);
1309 #else
1310  p5 = p5s = i2b(625);
1311  p5->next = 0;
1312 #endif
1313  }
1314  for (;;) {
1315  if (k & 1) {
1316  b1 = mult(b, p5);
1317  Bfree(b);
1318  b = b1;
1319  }
1320  if (!(k >>= 1))
1321  break;
1322  if (!(p51 = p5->next)) {
1323 #ifdef MULTIPLE_THREADS
1324  ACQUIRE_DTOA_LOCK(1);
1325  if (!(p51 = p5->next)) {
1326  p51 = p5->next = mult(p5,p5);
1327  p51->next = 0;
1328  }
1329  FREE_DTOA_LOCK(1);
1330 #else
1331  p51 = p5->next = mult(p5,p5);
1332  p51->next = 0;
1333 #endif
1334  }
1335  p5 = p51;
1336  }
1337  return b;
1338 }
1339 
1340 static Bigint *
1341 lshift(Bigint *b, int k)
1342 {
1343  int i, k1, n, n1;
1344  Bigint *b1;
1345  ULong *x, *x1, *xe, z;
1346 
1347 #ifdef Pack_32
1348  n = k >> 5;
1349 #else
1350  n = k >> 4;
1351 #endif
1352  k1 = b->k;
1353  n1 = n + b->wds + 1;
1354  for (i = b->maxwds; n1 > i; i <<= 1)
1355  k1++;
1356  b1 = Balloc(k1);
1357  x1 = b1->x;
1358  for (i = 0; i < n; i++)
1359  *x1++ = 0;
1360  x = b->x;
1361  xe = x + b->wds;
1362 #ifdef Pack_32
1363  if (k &= 0x1f) {
1364  k1 = 32 - k;
1365  z = 0;
1366  do {
1367  *x1++ = *x << k | z;
1368  z = *x++ >> k1;
1369  } while (x < xe);
1370  if ((*x1 = z) != 0)
1371  ++n1;
1372  }
1373 #else
1374  if (k &= 0xf) {
1375  k1 = 16 - k;
1376  z = 0;
1377  do {
1378  *x1++ = *x << k & 0xffff | z;
1379  z = *x++ >> k1;
1380  } while (x < xe);
1381  if (*x1 = z)
1382  ++n1;
1383  }
1384 #endif
1385  else
1386  do {
1387  *x1++ = *x++;
1388  } while (x < xe);
1389  b1->wds = n1 - 1;
1390  Bfree(b);
1391  return b1;
1392 }
1393 
1394 static int
1396 {
1397  ULong *xa, *xa0, *xb, *xb0;
1398  int i, j;
1399 
1400  i = a->wds;
1401  j = b->wds;
1402 #ifdef DEBUG
1403  if (i > 1 && !a->x[i-1])
1404  Bug("cmp called with a->x[a->wds-1] == 0");
1405  if (j > 1 && !b->x[j-1])
1406  Bug("cmp called with b->x[b->wds-1] == 0");
1407 #endif
1408  if (i -= j)
1409  return i;
1410  xa0 = a->x;
1411  xa = xa0 + j;
1412  xb0 = b->x;
1413  xb = xb0 + j;
1414  for (;;) {
1415  if (*--xa != *--xb)
1416  return *xa < *xb ? -1 : 1;
1417  if (xa <= xa0)
1418  break;
1419  }
1420  return 0;
1421 }
1422 
1423 static Bigint *
1425 {
1426  Bigint *c;
1427  int i, wa, wb;
1428  ULong *xa, *xae, *xb, *xbe, *xc;
1429 #ifdef ULLong
1430  ULLong borrow, y;
1431 #else
1432  ULong borrow, y;
1433 #ifdef Pack_32
1434  ULong z;
1435 #endif
1436 #endif
1437 
1438  i = cmp(a,b);
1439  if (!i) {
1440  c = Balloc(0);
1441  c->wds = 1;
1442  c->x[0] = 0;
1443  return c;
1444  }
1445  if (i < 0) {
1446  c = a;
1447  a = b;
1448  b = c;
1449  i = 1;
1450  }
1451  else
1452  i = 0;
1453  c = Balloc(a->k);
1454  c->sign = i;
1455  wa = a->wds;
1456  xa = a->x;
1457  xae = xa + wa;
1458  wb = b->wds;
1459  xb = b->x;
1460  xbe = xb + wb;
1461  xc = c->x;
1462  borrow = 0;
1463 #ifdef ULLong
1464  do {
1465  y = (ULLong)*xa++ - *xb++ - borrow;
1466  borrow = y >> 32 & (ULong)1;
1467  *xc++ = (ULong)(y & FFFFFFFF);
1468  } while (xb < xbe);
1469  while (xa < xae) {
1470  y = *xa++ - borrow;
1471  borrow = y >> 32 & (ULong)1;
1472  *xc++ = (ULong)(y & FFFFFFFF);
1473  }
1474 #else
1475 #ifdef Pack_32
1476  do {
1477  y = (*xa & 0xffff) - (*xb & 0xffff) - borrow;
1478  borrow = (y & 0x10000) >> 16;
1479  z = (*xa++ >> 16) - (*xb++ >> 16) - borrow;
1480  borrow = (z & 0x10000) >> 16;
1481  Storeinc(xc, z, y);
1482  } while (xb < xbe);
1483  while (xa < xae) {
1484  y = (*xa & 0xffff) - borrow;
1485  borrow = (y & 0x10000) >> 16;
1486  z = (*xa++ >> 16) - borrow;
1487  borrow = (z & 0x10000) >> 16;
1488  Storeinc(xc, z, y);
1489  }
1490 #else
1491  do {
1492  y = *xa++ - *xb++ - borrow;
1493  borrow = (y & 0x10000) >> 16;
1494  *xc++ = y & 0xffff;
1495  } while (xb < xbe);
1496  while (xa < xae) {
1497  y = *xa++ - borrow;
1498  borrow = (y & 0x10000) >> 16;
1499  *xc++ = y & 0xffff;
1500  }
1501 #endif
1502 #endif
1503  while (!*--xc)
1504  wa--;
1505  c->wds = wa;
1506  return c;
1507 }
1508 
1509 static double
1510 ulp(double x_)
1511 {
1512  register Long L;
1513  double_u x, a;
1514  dval(x) = x_;
1515 
1516  L = (word0(x) & Exp_mask) - (P-1)*Exp_msk1;
1517 #ifndef Avoid_Underflow
1518 #ifndef Sudden_Underflow
1519  if (L > 0) {
1520 #endif
1521 #endif
1522 #ifdef IBM
1523  L |= Exp_msk1 >> 4;
1524 #endif
1525  word0(a) = L;
1526  word1(a) = 0;
1527 #ifndef Avoid_Underflow
1528 #ifndef Sudden_Underflow
1529  }
1530  else {
1531  L = -L >> Exp_shift;
1532  if (L < Exp_shift) {
1533  word0(a) = 0x80000 >> L;
1534  word1(a) = 0;
1535  }
1536  else {
1537  word0(a) = 0;
1538  L -= Exp_shift;
1539  word1(a) = L >= 31 ? 1 : 1 << 31 - L;
1540  }
1541  }
1542 #endif
1543 #endif
1544  return dval(a);
1545 }
1546 
1547 static double
1548 b2d(Bigint *a, int *e)
1549 {
1550  ULong *xa, *xa0, w, y, z;
1551  int k;
1552  double_u d;
1553 #ifdef VAX
1554  ULong d0, d1;
1555 #else
1556 #define d0 word0(d)
1557 #define d1 word1(d)
1558 #endif
1559 
1560  xa0 = a->x;
1561  xa = xa0 + a->wds;
1562  y = *--xa;
1563 #ifdef DEBUG
1564  if (!y) Bug("zero y in b2d");
1565 #endif
1566  k = hi0bits(y);
1567  *e = 32 - k;
1568 #ifdef Pack_32
1569  if (k < Ebits) {
1570  d0 = Exp_1 | y >> (Ebits - k);
1571  w = xa > xa0 ? *--xa : 0;
1572  d1 = y << ((32-Ebits) + k) | w >> (Ebits - k);
1573  goto ret_d;
1574  }
1575  z = xa > xa0 ? *--xa : 0;
1576  if (k -= Ebits) {
1577  d0 = Exp_1 | y << k | z >> (32 - k);
1578  y = xa > xa0 ? *--xa : 0;
1579  d1 = z << k | y >> (32 - k);
1580  }
1581  else {
1582  d0 = Exp_1 | y;
1583  d1 = z;
1584  }
1585 #else
1586  if (k < Ebits + 16) {
1587  z = xa > xa0 ? *--xa : 0;
1588  d0 = Exp_1 | y << k - Ebits | z >> Ebits + 16 - k;
1589  w = xa > xa0 ? *--xa : 0;
1590  y = xa > xa0 ? *--xa : 0;
1591  d1 = z << k + 16 - Ebits | w << k - Ebits | y >> 16 + Ebits - k;
1592  goto ret_d;
1593  }
1594  z = xa > xa0 ? *--xa : 0;
1595  w = xa > xa0 ? *--xa : 0;
1596  k -= Ebits + 16;
1597  d0 = Exp_1 | y << k + 16 | z << k | w >> 16 - k;
1598  y = xa > xa0 ? *--xa : 0;
1599  d1 = w << k + 16 | y << k;
1600 #endif
1601 ret_d:
1602 #ifdef VAX
1603  word0(d) = d0 >> 16 | d0 << 16;
1604  word1(d) = d1 >> 16 | d1 << 16;
1605 #else
1606 #undef d0
1607 #undef d1
1608 #endif
1609  return dval(d);
1610 }
1611 
1612 static Bigint *
1613 d2b(double d_, int *e, int *bits)
1614 {
1615  double_u d;
1616  Bigint *b;
1617  int de, k;
1618  ULong *x, y, z;
1619 #ifndef Sudden_Underflow
1620  int i;
1621 #endif
1622 #ifdef VAX
1623  ULong d0, d1;
1624 #endif
1625  dval(d) = d_;
1626 #ifdef VAX
1627  d0 = word0(d) >> 16 | word0(d) << 16;
1628  d1 = word1(d) >> 16 | word1(d) << 16;
1629 #else
1630 #define d0 word0(d)
1631 #define d1 word1(d)
1632 #endif
1633 
1634 #ifdef Pack_32
1635  b = Balloc(1);
1636 #else
1637  b = Balloc(2);
1638 #endif
1639  x = b->x;
1640 
1641  z = d0 & Frac_mask;
1642  d0 &= 0x7fffffff; /* clear sign bit, which we ignore */
1643 #ifdef Sudden_Underflow
1644  de = (int)(d0 >> Exp_shift);
1645 #ifndef IBM
1646  z |= Exp_msk11;
1647 #endif
1648 #else
1649  if ((de = (int)(d0 >> Exp_shift)) != 0)
1650  z |= Exp_msk1;
1651 #endif
1652 #ifdef Pack_32
1653  if ((y = d1) != 0) {
1654  if ((k = lo0bits(&y)) != 0) {
1655  x[0] = y | z << (32 - k);
1656  z >>= k;
1657  }
1658  else
1659  x[0] = y;
1660 #ifndef Sudden_Underflow
1661  i =
1662 #endif
1663  b->wds = (x[1] = z) ? 2 : 1;
1664  }
1665  else {
1666 #ifdef DEBUG
1667  if (!z)
1668  Bug("Zero passed to d2b");
1669 #endif
1670  k = lo0bits(&z);
1671  x[0] = z;
1672 #ifndef Sudden_Underflow
1673  i =
1674 #endif
1675  b->wds = 1;
1676  k += 32;
1677  }
1678 #else
1679  if (y = d1) {
1680  if (k = lo0bits(&y))
1681  if (k >= 16) {
1682  x[0] = y | z << 32 - k & 0xffff;
1683  x[1] = z >> k - 16 & 0xffff;
1684  x[2] = z >> k;
1685  i = 2;
1686  }
1687  else {
1688  x[0] = y & 0xffff;
1689  x[1] = y >> 16 | z << 16 - k & 0xffff;
1690  x[2] = z >> k & 0xffff;
1691  x[3] = z >> k+16;
1692  i = 3;
1693  }
1694  else {
1695  x[0] = y & 0xffff;
1696  x[1] = y >> 16;
1697  x[2] = z & 0xffff;
1698  x[3] = z >> 16;
1699  i = 3;
1700  }
1701  }
1702  else {
1703 #ifdef DEBUG
1704  if (!z)
1705  Bug("Zero passed to d2b");
1706 #endif
1707  k = lo0bits(&z);
1708  if (k >= 16) {
1709  x[0] = z;
1710  i = 0;
1711  }
1712  else {
1713  x[0] = z & 0xffff;
1714  x[1] = z >> 16;
1715  i = 1;
1716  }
1717  k += 32;
1718  }
1719  while (!x[i])
1720  --i;
1721  b->wds = i + 1;
1722 #endif
1723 #ifndef Sudden_Underflow
1724  if (de) {
1725 #endif
1726 #ifdef IBM
1727  *e = (de - Bias - (P-1) << 2) + k;
1728  *bits = 4*P + 8 - k - hi0bits(word0(d) & Frac_mask);
1729 #else
1730  *e = de - Bias - (P-1) + k;
1731  *bits = P - k;
1732 #endif
1733 #ifndef Sudden_Underflow
1734  }
1735  else {
1736  *e = de - Bias - (P-1) + 1 + k;
1737 #ifdef Pack_32
1738  *bits = 32*i - hi0bits(x[i-1]);
1739 #else
1740  *bits = (i+2)*16 - hi0bits(x[i]);
1741 #endif
1742  }
1743 #endif
1744  return b;
1745 }
1746 #undef d0
1747 #undef d1
1748 
1749 static double
1751 {
1752  double_u da, db;
1753  int k, ka, kb;
1754 
1755  dval(da) = b2d(a, &ka);
1756  dval(db) = b2d(b, &kb);
1757 #ifdef Pack_32
1758  k = ka - kb + 32*(a->wds - b->wds);
1759 #else
1760  k = ka - kb + 16*(a->wds - b->wds);
1761 #endif
1762 #ifdef IBM
1763  if (k > 0) {
1764  word0(da) += (k >> 2)*Exp_msk1;
1765  if (k &= 3)
1766  dval(da) *= 1 << k;
1767  }
1768  else {
1769  k = -k;
1770  word0(db) += (k >> 2)*Exp_msk1;
1771  if (k &= 3)
1772  dval(db) *= 1 << k;
1773  }
1774 #else
1775  if (k > 0)
1776  word0(da) += k*Exp_msk1;
1777  else {
1778  k = -k;
1779  word0(db) += k*Exp_msk1;
1780  }
1781 #endif
1782  return dval(da) / dval(db);
1783 }
1784 
1785 static const double
1786 tens[] = {
1787  1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9,
1788  1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19,
1789  1e20, 1e21, 1e22
1790 #ifdef VAX
1791  , 1e23, 1e24
1792 #endif
1793 };
1794 
1795 static const double
1796 #ifdef IEEE_Arith
1797 bigtens[] = { 1e16, 1e32, 1e64, 1e128, 1e256 };
1798 static const double tinytens[] = { 1e-16, 1e-32, 1e-64, 1e-128,
1799 #ifdef Avoid_Underflow
1800  9007199254740992.*9007199254740992.e-256
1801  /* = 2^106 * 1e-53 */
1802 #else
1803  1e-256
1804 #endif
1805 };
1806 /* The factor of 2^53 in tinytens[4] helps us avoid setting the underflow */
1807 /* flag unnecessarily. It leads to a song and dance at the end of strtod. */
1808 #define Scale_Bit 0x10
1809 #define n_bigtens 5
1810 #else
1811 #ifdef IBM
1812 bigtens[] = { 1e16, 1e32, 1e64 };
1813 static const double tinytens[] = { 1e-16, 1e-32, 1e-64 };
1814 #define n_bigtens 3
1815 #else
1816 bigtens[] = { 1e16, 1e32 };
1817 static const double tinytens[] = { 1e-16, 1e-32 };
1818 #define n_bigtens 2
1819 #endif
1820 #endif
1821 
1822 #ifndef IEEE_Arith
1823 #undef INFNAN_CHECK
1824 #endif
1825 
1826 #ifdef INFNAN_CHECK
1827 
1828 #ifndef NAN_WORD0
1829 #define NAN_WORD0 0x7ff80000
1830 #endif
1831 
1832 #ifndef NAN_WORD1
1833 #define NAN_WORD1 0
1834 #endif
1835 
1836 static int
1837 match(const char **sp, char *t)
1838 {
1839  int c, d;
1840  const char *s = *sp;
1841 
1842  while (d = *t++) {
1843  if ((c = *++s) >= 'A' && c <= 'Z')
1844  c += 'a' - 'A';
1845  if (c != d)
1846  return 0;
1847  }
1848  *sp = s + 1;
1849  return 1;
1850 }
1851 
1852 #ifndef No_Hex_NaN
1853 static void
1854 hexnan(double *rvp, const char **sp)
1855 {
1856  ULong c, x[2];
1857  const char *s;
1858  int havedig, udx0, xshift;
1859 
1860  x[0] = x[1] = 0;
1861  havedig = xshift = 0;
1862  udx0 = 1;
1863  s = *sp;
1864  while (c = *(const unsigned char*)++s) {
1865  if (c >= '0' && c <= '9')
1866  c -= '0';
1867  else if (c >= 'a' && c <= 'f')
1868  c += 10 - 'a';
1869  else if (c >= 'A' && c <= 'F')
1870  c += 10 - 'A';
1871  else if (c <= ' ') {
1872  if (udx0 && havedig) {
1873  udx0 = 0;
1874  xshift = 1;
1875  }
1876  continue;
1877  }
1878  else if (/*(*/ c == ')' && havedig) {
1879  *sp = s + 1;
1880  break;
1881  }
1882  else
1883  return; /* invalid form: don't change *sp */
1884  havedig = 1;
1885  if (xshift) {
1886  xshift = 0;
1887  x[0] = x[1];
1888  x[1] = 0;
1889  }
1890  if (udx0)
1891  x[0] = (x[0] << 4) | (x[1] >> 28);
1892  x[1] = (x[1] << 4) | c;
1893  }
1894  if ((x[0] &= 0xfffff) || x[1]) {
1895  word0(*rvp) = Exp_mask | x[0];
1896  word1(*rvp) = x[1];
1897  }
1898 }
1899 #endif /*No_Hex_NaN*/
1900 #endif /* INFNAN_CHECK */
1901 
1902 double
1903 ruby_strtod(const char *s00, char **se)
1904 {
1905 #ifdef Avoid_Underflow
1906  int scale;
1907 #endif
1908  int bb2, bb5, bbe, bd2, bd5, bbbits, bs2, c, dsign,
1909  e, e1, esign, i, j, k, nd, nd0, nf, nz, nz0, sign;
1910  const char *s, *s0, *s1;
1911  double aadj, adj;
1912  double_u aadj1, rv, rv0;
1913  Long L;
1914  ULong y, z;
1915  Bigint *bb, *bb1, *bd, *bd0, *bs, *delta;
1916 #ifdef SET_INEXACT
1917  int inexact, oldinexact;
1918 #endif
1919 #ifdef Honor_FLT_ROUNDS
1920  int rounding;
1921 #endif
1922 #ifdef USE_LOCALE
1923  const char *s2;
1924 #endif
1925 
1926  errno = 0;
1927  sign = nz0 = nz = 0;
1928  dval(rv) = 0.;
1929  for (s = s00;;s++)
1930  switch (*s) {
1931  case '-':
1932  sign = 1;
1933  /* no break */
1934  case '+':
1935  if (*++s)
1936  goto break2;
1937  /* no break */
1938  case 0:
1939  goto ret0;
1940  case '\t':
1941  case '\n':
1942  case '\v':
1943  case '\f':
1944  case '\r':
1945  case ' ':
1946  continue;
1947  default:
1948  goto break2;
1949  }
1950 break2:
1951  if (*s == '0') {
1952  if (s[1] == 'x' || s[1] == 'X') {
1953  static const char hexdigit[] = "0123456789abcdef0123456789ABCDEF";
1954  s0 = ++s;
1955  adj = 0;
1956  aadj = 1.0;
1957  nd0 = -4;
1958 
1959  if (!*++s || !(s1 = strchr(hexdigit, *s))) goto ret0;
1960  while (*s == '0') s++;
1961  if ((s1 = strchr(hexdigit, *s)) != NULL) {
1962  do {
1963  adj += aadj * ((s1 - hexdigit) & 15);
1964  nd0 += 4;
1965  aadj /= 16;
1966  } while (*++s && (s1 = strchr(hexdigit, *s)));
1967  }
1968 
1969  if (*s == '.') {
1970  dsign = 1;
1971  if (!*++s || !(s1 = strchr(hexdigit, *s))) goto ret0;
1972  if (nd0 < 0) {
1973  while (*s == '0') {
1974  s++;
1975  nd0 -= 4;
1976  }
1977  }
1978  for (; *s && (s1 = strchr(hexdigit, *s)); ++s) {
1979  adj += aadj * ((s1 - hexdigit) & 15);
1980  if ((aadj /= 16) == 0.0) {
1981  while (strchr(hexdigit, *++s));
1982  break;
1983  }
1984  }
1985  }
1986  else {
1987  dsign = 0;
1988  }
1989 
1990  if (*s == 'P' || *s == 'p') {
1991  dsign = 0x2C - *++s; /* +: 2B, -: 2D */
1992  if (abs(dsign) == 1) s++;
1993  else dsign = 1;
1994 
1995  nd = 0;
1996  c = *s;
1997  if (c < '0' || '9' < c) goto ret0;
1998  do {
1999  nd *= 10;
2000  nd += c;
2001  nd -= '0';
2002  c = *++s;
2003  /* Float("0x0."+("0"*267)+"1fp2095") */
2004  if (nd + dsign * nd0 > 2095) {
2005  while ('0' <= c && c <= '9') c = *++s;
2006  break;
2007  }
2008  } while ('0' <= c && c <= '9');
2009  nd0 += nd * dsign;
2010  }
2011  else {
2012  if (dsign) goto ret0;
2013  }
2014  dval(rv) = ldexp(adj, nd0);
2015  goto ret;
2016  }
2017  nz0 = 1;
2018  while (*++s == '0') ;
2019  if (!*s)
2020  goto ret;
2021  }
2022  s0 = s;
2023  y = z = 0;
2024  for (nd = nf = 0; (c = *s) >= '0' && c <= '9'; nd++, s++)
2025  if (nd < 9)
2026  y = 10*y + c - '0';
2027  else if (nd < 16)
2028  z = 10*z + c - '0';
2029  nd0 = nd;
2030 #ifdef USE_LOCALE
2031  s1 = localeconv()->decimal_point;
2032  if (c == *s1) {
2033  c = '.';
2034  if (*++s1) {
2035  s2 = s;
2036  for (;;) {
2037  if (*++s2 != *s1) {
2038  c = 0;
2039  break;
2040  }
2041  if (!*++s1) {
2042  s = s2;
2043  break;
2044  }
2045  }
2046  }
2047  }
2048 #endif
2049  if (c == '.') {
2050  if (!ISDIGIT(s[1]))
2051  goto dig_done;
2052  c = *++s;
2053  if (!nd) {
2054  for (; c == '0'; c = *++s)
2055  nz++;
2056  if (c > '0' && c <= '9') {
2057  s0 = s;
2058  nf += nz;
2059  nz = 0;
2060  goto have_dig;
2061  }
2062  goto dig_done;
2063  }
2064  for (; c >= '0' && c <= '9'; c = *++s) {
2065 have_dig:
2066  nz++;
2067  if (nf > DBL_DIG * 4) continue;
2068  if (c -= '0') {
2069  nf += nz;
2070  for (i = 1; i < nz; i++)
2071  if (nd++ < 9)
2072  y *= 10;
2073  else if (nd <= DBL_DIG + 1)
2074  z *= 10;
2075  if (nd++ < 9)
2076  y = 10*y + c;
2077  else if (nd <= DBL_DIG + 1)
2078  z = 10*z + c;
2079  nz = 0;
2080  }
2081  }
2082  }
2083 dig_done:
2084  e = 0;
2085  if (c == 'e' || c == 'E') {
2086  if (!nd && !nz && !nz0) {
2087  goto ret0;
2088  }
2089  s00 = s;
2090  esign = 0;
2091  switch (c = *++s) {
2092  case '-':
2093  esign = 1;
2094  case '+':
2095  c = *++s;
2096  }
2097  if (c >= '0' && c <= '9') {
2098  while (c == '0')
2099  c = *++s;
2100  if (c > '0' && c <= '9') {
2101  L = c - '0';
2102  s1 = s;
2103  while ((c = *++s) >= '0' && c <= '9')
2104  L = 10*L + c - '0';
2105  if (s - s1 > 8 || L > 19999)
2106  /* Avoid confusion from exponents
2107  * so large that e might overflow.
2108  */
2109  e = 19999; /* safe for 16 bit ints */
2110  else
2111  e = (int)L;
2112  if (esign)
2113  e = -e;
2114  }
2115  else
2116  e = 0;
2117  }
2118  else
2119  s = s00;
2120  }
2121  if (!nd) {
2122  if (!nz && !nz0) {
2123 #ifdef INFNAN_CHECK
2124  /* Check for Nan and Infinity */
2125  switch (c) {
2126  case 'i':
2127  case 'I':
2128  if (match(&s,"nf")) {
2129  --s;
2130  if (!match(&s,"inity"))
2131  ++s;
2132  word0(rv) = 0x7ff00000;
2133  word1(rv) = 0;
2134  goto ret;
2135  }
2136  break;
2137  case 'n':
2138  case 'N':
2139  if (match(&s, "an")) {
2140  word0(rv) = NAN_WORD0;
2141  word1(rv) = NAN_WORD1;
2142 #ifndef No_Hex_NaN
2143  if (*s == '(') /*)*/
2144  hexnan(&rv, &s);
2145 #endif
2146  goto ret;
2147  }
2148  }
2149 #endif /* INFNAN_CHECK */
2150 ret0:
2151  s = s00;
2152  sign = 0;
2153  }
2154  goto ret;
2155  }
2156  e1 = e -= nf;
2157 
2158  /* Now we have nd0 digits, starting at s0, followed by a
2159  * decimal point, followed by nd-nd0 digits. The number we're
2160  * after is the integer represented by those digits times
2161  * 10**e */
2162 
2163  if (!nd0)
2164  nd0 = nd;
2165  k = nd < DBL_DIG + 1 ? nd : DBL_DIG + 1;
2166  dval(rv) = y;
2167  if (k > 9) {
2168 #ifdef SET_INEXACT
2169  if (k > DBL_DIG)
2170  oldinexact = get_inexact();
2171 #endif
2172  dval(rv) = tens[k - 9] * dval(rv) + z;
2173  }
2174  bd0 = bb = bd = bs = delta = 0;
2175  if (nd <= DBL_DIG
2176 #ifndef RND_PRODQUOT
2177 #ifndef Honor_FLT_ROUNDS
2178  && Flt_Rounds == 1
2179 #endif
2180 #endif
2181  ) {
2182  if (!e)
2183  goto ret;
2184  if (e > 0) {
2185  if (e <= Ten_pmax) {
2186 #ifdef VAX
2187  goto vax_ovfl_check;
2188 #else
2189 #ifdef Honor_FLT_ROUNDS
2190  /* round correctly FLT_ROUNDS = 2 or 3 */
2191  if (sign) {
2192  dval(rv) = -dval(rv);
2193  sign = 0;
2194  }
2195 #endif
2196  /* rv = */ rounded_product(dval(rv), tens[e]);
2197  goto ret;
2198 #endif
2199  }
2200  i = DBL_DIG - nd;
2201  if (e <= Ten_pmax + i) {
2202  /* A fancier test would sometimes let us do
2203  * this for larger i values.
2204  */
2205 #ifdef Honor_FLT_ROUNDS
2206  /* round correctly FLT_ROUNDS = 2 or 3 */
2207  if (sign) {
2208  dval(rv) = -dval(rv);
2209  sign = 0;
2210  }
2211 #endif
2212  e -= i;
2213  dval(rv) *= tens[i];
2214 #ifdef VAX
2215  /* VAX exponent range is so narrow we must
2216  * worry about overflow here...
2217  */
2218 vax_ovfl_check:
2219  word0(rv) -= P*Exp_msk1;
2220  /* rv = */ rounded_product(dval(rv), tens[e]);
2221  if ((word0(rv) & Exp_mask)
2222  > Exp_msk1*(DBL_MAX_EXP+Bias-1-P))
2223  goto ovfl;
2224  word0(rv) += P*Exp_msk1;
2225 #else
2226  /* rv = */ rounded_product(dval(rv), tens[e]);
2227 #endif
2228  goto ret;
2229  }
2230  }
2231 #ifndef Inaccurate_Divide
2232  else if (e >= -Ten_pmax) {
2233 #ifdef Honor_FLT_ROUNDS
2234  /* round correctly FLT_ROUNDS = 2 or 3 */
2235  if (sign) {
2236  dval(rv) = -dval(rv);
2237  sign = 0;
2238  }
2239 #endif
2240  /* rv = */ rounded_quotient(dval(rv), tens[-e]);
2241  goto ret;
2242  }
2243 #endif
2244  }
2245  e1 += nd - k;
2246 
2247 #ifdef IEEE_Arith
2248 #ifdef SET_INEXACT
2249  inexact = 1;
2250  if (k <= DBL_DIG)
2251  oldinexact = get_inexact();
2252 #endif
2253 #ifdef Avoid_Underflow
2254  scale = 0;
2255 #endif
2256 #ifdef Honor_FLT_ROUNDS
2257  if ((rounding = Flt_Rounds) >= 2) {
2258  if (sign)
2259  rounding = rounding == 2 ? 0 : 2;
2260  else
2261  if (rounding != 2)
2262  rounding = 0;
2263  }
2264 #endif
2265 #endif /*IEEE_Arith*/
2266 
2267  /* Get starting approximation = rv * 10**e1 */
2268 
2269  if (e1 > 0) {
2270  if ((i = e1 & 15) != 0)
2271  dval(rv) *= tens[i];
2272  if (e1 &= ~15) {
2273  if (e1 > DBL_MAX_10_EXP) {
2274 ovfl:
2275 #ifndef NO_ERRNO
2276  errno = ERANGE;
2277 #endif
2278  /* Can't trust HUGE_VAL */
2279 #ifdef IEEE_Arith
2280 #ifdef Honor_FLT_ROUNDS
2281  switch (rounding) {
2282  case 0: /* toward 0 */
2283  case 3: /* toward -infinity */
2284  word0(rv) = Big0;
2285  word1(rv) = Big1;
2286  break;
2287  default:
2288  word0(rv) = Exp_mask;
2289  word1(rv) = 0;
2290  }
2291 #else /*Honor_FLT_ROUNDS*/
2292  word0(rv) = Exp_mask;
2293  word1(rv) = 0;
2294 #endif /*Honor_FLT_ROUNDS*/
2295 #ifdef SET_INEXACT
2296  /* set overflow bit */
2297  dval(rv0) = 1e300;
2298  dval(rv0) *= dval(rv0);
2299 #endif
2300 #else /*IEEE_Arith*/
2301  word0(rv) = Big0;
2302  word1(rv) = Big1;
2303 #endif /*IEEE_Arith*/
2304  if (bd0)
2305  goto retfree;
2306  goto ret;
2307  }
2308  e1 >>= 4;
2309  for (j = 0; e1 > 1; j++, e1 >>= 1)
2310  if (e1 & 1)
2311  dval(rv) *= bigtens[j];
2312  /* The last multiplication could overflow. */
2313  word0(rv) -= P*Exp_msk1;
2314  dval(rv) *= bigtens[j];
2315  if ((z = word0(rv) & Exp_mask)
2316  > Exp_msk1*(DBL_MAX_EXP+Bias-P))
2317  goto ovfl;
2318  if (z > Exp_msk1*(DBL_MAX_EXP+Bias-1-P)) {
2319  /* set to largest number */
2320  /* (Can't trust DBL_MAX) */
2321  word0(rv) = Big0;
2322  word1(rv) = Big1;
2323  }
2324  else
2325  word0(rv) += P*Exp_msk1;
2326  }
2327  }
2328  else if (e1 < 0) {
2329  e1 = -e1;
2330  if ((i = e1 & 15) != 0)
2331  dval(rv) /= tens[i];
2332  if (e1 >>= 4) {
2333  if (e1 >= 1 << n_bigtens)
2334  goto undfl;
2335 #ifdef Avoid_Underflow
2336  if (e1 & Scale_Bit)
2337  scale = 2*P;
2338  for (j = 0; e1 > 0; j++, e1 >>= 1)
2339  if (e1 & 1)
2340  dval(rv) *= tinytens[j];
2341  if (scale && (j = 2*P + 1 - ((word0(rv) & Exp_mask)
2342  >> Exp_shift)) > 0) {
2343  /* scaled rv is denormal; zap j low bits */
2344  if (j >= 32) {
2345  word1(rv) = 0;
2346  if (j >= 53)
2347  word0(rv) = (P+2)*Exp_msk1;
2348  else
2349  word0(rv) &= 0xffffffff << (j-32);
2350  }
2351  else
2352  word1(rv) &= 0xffffffff << j;
2353  }
2354 #else
2355  for (j = 0; e1 > 1; j++, e1 >>= 1)
2356  if (e1 & 1)
2357  dval(rv) *= tinytens[j];
2358  /* The last multiplication could underflow. */
2359  dval(rv0) = dval(rv);
2360  dval(rv) *= tinytens[j];
2361  if (!dval(rv)) {
2362  dval(rv) = 2.*dval(rv0);
2363  dval(rv) *= tinytens[j];
2364 #endif
2365  if (!dval(rv)) {
2366 undfl:
2367  dval(rv) = 0.;
2368 #ifndef NO_ERRNO
2369  errno = ERANGE;
2370 #endif
2371  if (bd0)
2372  goto retfree;
2373  goto ret;
2374  }
2375 #ifndef Avoid_Underflow
2376  word0(rv) = Tiny0;
2377  word1(rv) = Tiny1;
2378  /* The refinement below will clean
2379  * this approximation up.
2380  */
2381  }
2382 #endif
2383  }
2384  }
2385 
2386  /* Now the hard part -- adjusting rv to the correct value.*/
2387 
2388  /* Put digits into bd: true value = bd * 10^e */
2389 
2390  bd0 = s2b(s0, nd0, nd, y);
2391 
2392  for (;;) {
2393  bd = Balloc(bd0->k);
2394  Bcopy(bd, bd0);
2395  bb = d2b(dval(rv), &bbe, &bbbits); /* rv = bb * 2^bbe */
2396  bs = i2b(1);
2397 
2398  if (e >= 0) {
2399  bb2 = bb5 = 0;
2400  bd2 = bd5 = e;
2401  }
2402  else {
2403  bb2 = bb5 = -e;
2404  bd2 = bd5 = 0;
2405  }
2406  if (bbe >= 0)
2407  bb2 += bbe;
2408  else
2409  bd2 -= bbe;
2410  bs2 = bb2;
2411 #ifdef Honor_FLT_ROUNDS
2412  if (rounding != 1)
2413  bs2++;
2414 #endif
2415 #ifdef Avoid_Underflow
2416  j = bbe - scale;
2417  i = j + bbbits - 1; /* logb(rv) */
2418  if (i < Emin) /* denormal */
2419  j += P - Emin;
2420  else
2421  j = P + 1 - bbbits;
2422 #else /*Avoid_Underflow*/
2423 #ifdef Sudden_Underflow
2424 #ifdef IBM
2425  j = 1 + 4*P - 3 - bbbits + ((bbe + bbbits - 1) & 3);
2426 #else
2427  j = P + 1 - bbbits;
2428 #endif
2429 #else /*Sudden_Underflow*/
2430  j = bbe;
2431  i = j + bbbits - 1; /* logb(rv) */
2432  if (i < Emin) /* denormal */
2433  j += P - Emin;
2434  else
2435  j = P + 1 - bbbits;
2436 #endif /*Sudden_Underflow*/
2437 #endif /*Avoid_Underflow*/
2438  bb2 += j;
2439  bd2 += j;
2440 #ifdef Avoid_Underflow
2441  bd2 += scale;
2442 #endif
2443  i = bb2 < bd2 ? bb2 : bd2;
2444  if (i > bs2)
2445  i = bs2;
2446  if (i > 0) {
2447  bb2 -= i;
2448  bd2 -= i;
2449  bs2 -= i;
2450  }
2451  if (bb5 > 0) {
2452  bs = pow5mult(bs, bb5);
2453  bb1 = mult(bs, bb);
2454  Bfree(bb);
2455  bb = bb1;
2456  }
2457  if (bb2 > 0)
2458  bb = lshift(bb, bb2);
2459  if (bd5 > 0)
2460  bd = pow5mult(bd, bd5);
2461  if (bd2 > 0)
2462  bd = lshift(bd, bd2);
2463  if (bs2 > 0)
2464  bs = lshift(bs, bs2);
2465  delta = diff(bb, bd);
2466  dsign = delta->sign;
2467  delta->sign = 0;
2468  i = cmp(delta, bs);
2469 #ifdef Honor_FLT_ROUNDS
2470  if (rounding != 1) {
2471  if (i < 0) {
2472  /* Error is less than an ulp */
2473  if (!delta->x[0] && delta->wds <= 1) {
2474  /* exact */
2475 #ifdef SET_INEXACT
2476  inexact = 0;
2477 #endif
2478  break;
2479  }
2480  if (rounding) {
2481  if (dsign) {
2482  adj = 1.;
2483  goto apply_adj;
2484  }
2485  }
2486  else if (!dsign) {
2487  adj = -1.;
2488  if (!word1(rv)
2489  && !(word0(rv) & Frac_mask)) {
2490  y = word0(rv) & Exp_mask;
2491 #ifdef Avoid_Underflow
2492  if (!scale || y > 2*P*Exp_msk1)
2493 #else
2494  if (y)
2495 #endif
2496  {
2497  delta = lshift(delta,Log2P);
2498  if (cmp(delta, bs) <= 0)
2499  adj = -0.5;
2500  }
2501  }
2502 apply_adj:
2503 #ifdef Avoid_Underflow
2504  if (scale && (y = word0(rv) & Exp_mask)
2505  <= 2*P*Exp_msk1)
2506  word0(adj) += (2*P+1)*Exp_msk1 - y;
2507 #else
2508 #ifdef Sudden_Underflow
2509  if ((word0(rv) & Exp_mask) <=
2510  P*Exp_msk1) {
2511  word0(rv) += P*Exp_msk1;
2512  dval(rv) += adj*ulp(dval(rv));
2513  word0(rv) -= P*Exp_msk1;
2514  }
2515  else
2516 #endif /*Sudden_Underflow*/
2517 #endif /*Avoid_Underflow*/
2518  dval(rv) += adj*ulp(dval(rv));
2519  }
2520  break;
2521  }
2522  adj = ratio(delta, bs);
2523  if (adj < 1.)
2524  adj = 1.;
2525  if (adj <= 0x7ffffffe) {
2526  /* adj = rounding ? ceil(adj) : floor(adj); */
2527  y = adj;
2528  if (y != adj) {
2529  if (!((rounding>>1) ^ dsign))
2530  y++;
2531  adj = y;
2532  }
2533  }
2534 #ifdef Avoid_Underflow
2535  if (scale && (y = word0(rv) & Exp_mask) <= 2*P*Exp_msk1)
2536  word0(adj) += (2*P+1)*Exp_msk1 - y;
2537 #else
2538 #ifdef Sudden_Underflow
2539  if ((word0(rv) & Exp_mask) <= P*Exp_msk1) {
2540  word0(rv) += P*Exp_msk1;
2541  adj *= ulp(dval(rv));
2542  if (dsign)
2543  dval(rv) += adj;
2544  else
2545  dval(rv) -= adj;
2546  word0(rv) -= P*Exp_msk1;
2547  goto cont;
2548  }
2549 #endif /*Sudden_Underflow*/
2550 #endif /*Avoid_Underflow*/
2551  adj *= ulp(dval(rv));
2552  if (dsign)
2553  dval(rv) += adj;
2554  else
2555  dval(rv) -= adj;
2556  goto cont;
2557  }
2558 #endif /*Honor_FLT_ROUNDS*/
2559 
2560  if (i < 0) {
2561  /* Error is less than half an ulp -- check for
2562  * special case of mantissa a power of two.
2563  */
2564  if (dsign || word1(rv) || word0(rv) & Bndry_mask
2565 #ifdef IEEE_Arith
2566 #ifdef Avoid_Underflow
2567  || (word0(rv) & Exp_mask) <= (2*P+1)*Exp_msk1
2568 #else
2569  || (word0(rv) & Exp_mask) <= Exp_msk1
2570 #endif
2571 #endif
2572  ) {
2573 #ifdef SET_INEXACT
2574  if (!delta->x[0] && delta->wds <= 1)
2575  inexact = 0;
2576 #endif
2577  break;
2578  }
2579  if (!delta->x[0] && delta->wds <= 1) {
2580  /* exact result */
2581 #ifdef SET_INEXACT
2582  inexact = 0;
2583 #endif
2584  break;
2585  }
2586  delta = lshift(delta,Log2P);
2587  if (cmp(delta, bs) > 0)
2588  goto drop_down;
2589  break;
2590  }
2591  if (i == 0) {
2592  /* exactly half-way between */
2593  if (dsign) {
2594  if ((word0(rv) & Bndry_mask1) == Bndry_mask1
2595  && word1(rv) == (
2596 #ifdef Avoid_Underflow
2597  (scale && (y = word0(rv) & Exp_mask) <= 2*P*Exp_msk1)
2598  ? (0xffffffff & (0xffffffff << (2*P+1-(y>>Exp_shift)))) :
2599 #endif
2600  0xffffffff)) {
2601  /*boundary case -- increment exponent*/
2602  word0(rv) = (word0(rv) & Exp_mask)
2603  + Exp_msk1
2604 #ifdef IBM
2605  | Exp_msk1 >> 4
2606 #endif
2607  ;
2608  word1(rv) = 0;
2609 #ifdef Avoid_Underflow
2610  dsign = 0;
2611 #endif
2612  break;
2613  }
2614  }
2615  else if (!(word0(rv) & Bndry_mask) && !word1(rv)) {
2616 drop_down:
2617  /* boundary case -- decrement exponent */
2618 #ifdef Sudden_Underflow /*{{*/
2619  L = word0(rv) & Exp_mask;
2620 #ifdef IBM
2621  if (L < Exp_msk1)
2622 #else
2623 #ifdef Avoid_Underflow
2624  if (L <= (scale ? (2*P+1)*Exp_msk1 : Exp_msk1))
2625 #else
2626  if (L <= Exp_msk1)
2627 #endif /*Avoid_Underflow*/
2628 #endif /*IBM*/
2629  goto undfl;
2630  L -= Exp_msk1;
2631 #else /*Sudden_Underflow}{*/
2632 #ifdef Avoid_Underflow
2633  if (scale) {
2634  L = word0(rv) & Exp_mask;
2635  if (L <= (2*P+1)*Exp_msk1) {
2636  if (L > (P+2)*Exp_msk1)
2637  /* round even ==> */
2638  /* accept rv */
2639  break;
2640  /* rv = smallest denormal */
2641  goto undfl;
2642  }
2643  }
2644 #endif /*Avoid_Underflow*/
2645  L = (word0(rv) & Exp_mask) - Exp_msk1;
2646 #endif /*Sudden_Underflow}}*/
2647  word0(rv) = L | Bndry_mask1;
2648  word1(rv) = 0xffffffff;
2649 #ifdef IBM
2650  goto cont;
2651 #else
2652  break;
2653 #endif
2654  }
2655 #ifndef ROUND_BIASED
2656  if (!(word1(rv) & LSB))
2657  break;
2658 #endif
2659  if (dsign)
2660  dval(rv) += ulp(dval(rv));
2661 #ifndef ROUND_BIASED
2662  else {
2663  dval(rv) -= ulp(dval(rv));
2664 #ifndef Sudden_Underflow
2665  if (!dval(rv))
2666  goto undfl;
2667 #endif
2668  }
2669 #ifdef Avoid_Underflow
2670  dsign = 1 - dsign;
2671 #endif
2672 #endif
2673  break;
2674  }
2675  if ((aadj = ratio(delta, bs)) <= 2.) {
2676  if (dsign)
2677  aadj = dval(aadj1) = 1.;
2678  else if (word1(rv) || word0(rv) & Bndry_mask) {
2679 #ifndef Sudden_Underflow
2680  if (word1(rv) == Tiny1 && !word0(rv))
2681  goto undfl;
2682 #endif
2683  aadj = 1.;
2684  dval(aadj1) = -1.;
2685  }
2686  else {
2687  /* special case -- power of FLT_RADIX to be */
2688  /* rounded down... */
2689 
2690  if (aadj < 2./FLT_RADIX)
2691  aadj = 1./FLT_RADIX;
2692  else
2693  aadj *= 0.5;
2694  dval(aadj1) = -aadj;
2695  }
2696  }
2697  else {
2698  aadj *= 0.5;
2699  dval(aadj1) = dsign ? aadj : -aadj;
2700 #ifdef Check_FLT_ROUNDS
2701  switch (Rounding) {
2702  case 2: /* towards +infinity */
2703  dval(aadj1) -= 0.5;
2704  break;
2705  case 0: /* towards 0 */
2706  case 3: /* towards -infinity */
2707  dval(aadj1) += 0.5;
2708  }
2709 #else
2710  if (Flt_Rounds == 0)
2711  dval(aadj1) += 0.5;
2712 #endif /*Check_FLT_ROUNDS*/
2713  }
2714  y = word0(rv) & Exp_mask;
2715 
2716  /* Check for overflow */
2717 
2718  if (y == Exp_msk1*(DBL_MAX_EXP+Bias-1)) {
2719  dval(rv0) = dval(rv);
2720  word0(rv) -= P*Exp_msk1;
2721  adj = dval(aadj1) * ulp(dval(rv));
2722  dval(rv) += adj;
2723  if ((word0(rv) & Exp_mask) >=
2724  Exp_msk1*(DBL_MAX_EXP+Bias-P)) {
2725  if (word0(rv0) == Big0 && word1(rv0) == Big1)
2726  goto ovfl;
2727  word0(rv) = Big0;
2728  word1(rv) = Big1;
2729  goto cont;
2730  }
2731  else
2732  word0(rv) += P*Exp_msk1;
2733  }
2734  else {
2735 #ifdef Avoid_Underflow
2736  if (scale && y <= 2*P*Exp_msk1) {
2737  if (aadj <= 0x7fffffff) {
2738  if ((z = (int)aadj) <= 0)
2739  z = 1;
2740  aadj = z;
2741  dval(aadj1) = dsign ? aadj : -aadj;
2742  }
2743  word0(aadj1) += (2*P+1)*Exp_msk1 - y;
2744  }
2745  adj = dval(aadj1) * ulp(dval(rv));
2746  dval(rv) += adj;
2747 #else
2748 #ifdef Sudden_Underflow
2749  if ((word0(rv) & Exp_mask) <= P*Exp_msk1) {
2750  dval(rv0) = dval(rv);
2751  word0(rv) += P*Exp_msk1;
2752  adj = dval(aadj1) * ulp(dval(rv));
2753  dval(rv) += adj;
2754 #ifdef IBM
2755  if ((word0(rv) & Exp_mask) < P*Exp_msk1)
2756 #else
2757  if ((word0(rv) & Exp_mask) <= P*Exp_msk1)
2758 #endif
2759  {
2760  if (word0(rv0) == Tiny0 && word1(rv0) == Tiny1)
2761  goto undfl;
2762  word0(rv) = Tiny0;
2763  word1(rv) = Tiny1;
2764  goto cont;
2765  }
2766  else
2767  word0(rv) -= P*Exp_msk1;
2768  }
2769  else {
2770  adj = dval(aadj1) * ulp(dval(rv));
2771  dval(rv) += adj;
2772  }
2773 #else /*Sudden_Underflow*/
2774  /* Compute adj so that the IEEE rounding rules will
2775  * correctly round rv + adj in some half-way cases.
2776  * If rv * ulp(rv) is denormalized (i.e.,
2777  * y <= (P-1)*Exp_msk1), we must adjust aadj to avoid
2778  * trouble from bits lost to denormalization;
2779  * example: 1.2e-307 .
2780  */
2781  if (y <= (P-1)*Exp_msk1 && aadj > 1.) {
2782  dval(aadj1) = (double)(int)(aadj + 0.5);
2783  if (!dsign)
2784  dval(aadj1) = -dval(aadj1);
2785  }
2786  adj = dval(aadj1) * ulp(dval(rv));
2787  dval(rv) += adj;
2788 #endif /*Sudden_Underflow*/
2789 #endif /*Avoid_Underflow*/
2790  }
2791  z = word0(rv) & Exp_mask;
2792 #ifndef SET_INEXACT
2793 #ifdef Avoid_Underflow
2794  if (!scale)
2795 #endif
2796  if (y == z) {
2797  /* Can we stop now? */
2798  L = (Long)aadj;
2799  aadj -= L;
2800  /* The tolerances below are conservative. */
2801  if (dsign || word1(rv) || word0(rv) & Bndry_mask) {
2802  if (aadj < .4999999 || aadj > .5000001)
2803  break;
2804  }
2805  else if (aadj < .4999999/FLT_RADIX)
2806  break;
2807  }
2808 #endif
2809 cont:
2810  Bfree(bb);
2811  Bfree(bd);
2812  Bfree(bs);
2813  Bfree(delta);
2814  }
2815 #ifdef SET_INEXACT
2816  if (inexact) {
2817  if (!oldinexact) {
2818  word0(rv0) = Exp_1 + (70 << Exp_shift);
2819  word1(rv0) = 0;
2820  dval(rv0) += 1.;
2821  }
2822  }
2823  else if (!oldinexact)
2824  clear_inexact();
2825 #endif
2826 #ifdef Avoid_Underflow
2827  if (scale) {
2828  word0(rv0) = Exp_1 - 2*P*Exp_msk1;
2829  word1(rv0) = 0;
2830  dval(rv) *= dval(rv0);
2831 #ifndef NO_ERRNO
2832  /* try to avoid the bug of testing an 8087 register value */
2833  if (word0(rv) == 0 && word1(rv) == 0)
2834  errno = ERANGE;
2835 #endif
2836  }
2837 #endif /* Avoid_Underflow */
2838 #ifdef SET_INEXACT
2839  if (inexact && !(word0(rv) & Exp_mask)) {
2840  /* set underflow bit */
2841  dval(rv0) = 1e-300;
2842  dval(rv0) *= dval(rv0);
2843  }
2844 #endif
2845 retfree:
2846  Bfree(bb);
2847  Bfree(bd);
2848  Bfree(bs);
2849  Bfree(bd0);
2850  Bfree(delta);
2851 ret:
2852  if (se)
2853  *se = (char *)s;
2854  return sign ? -dval(rv) : dval(rv);
2855 }
2856 
2857 static int
2859 {
2860  int n;
2861  ULong *bx, *bxe, q, *sx, *sxe;
2862 #ifdef ULLong
2863  ULLong borrow, carry, y, ys;
2864 #else
2865  ULong borrow, carry, y, ys;
2866 #ifdef Pack_32
2867  ULong si, z, zs;
2868 #endif
2869 #endif
2870 
2871  n = S->wds;
2872 #ifdef DEBUG
2873  /*debug*/ if (b->wds > n)
2874  /*debug*/ Bug("oversize b in quorem");
2875 #endif
2876  if (b->wds < n)
2877  return 0;
2878  sx = S->x;
2879  sxe = sx + --n;
2880  bx = b->x;
2881  bxe = bx + n;
2882  q = *bxe / (*sxe + 1); /* ensure q <= true quotient */
2883 #ifdef DEBUG
2884  /*debug*/ if (q > 9)
2885  /*debug*/ Bug("oversized quotient in quorem");
2886 #endif
2887  if (q) {
2888  borrow = 0;
2889  carry = 0;
2890  do {
2891 #ifdef ULLong
2892  ys = *sx++ * (ULLong)q + carry;
2893  carry = ys >> 32;
2894  y = *bx - (ys & FFFFFFFF) - borrow;
2895  borrow = y >> 32 & (ULong)1;
2896  *bx++ = (ULong)(y & FFFFFFFF);
2897 #else
2898 #ifdef Pack_32
2899  si = *sx++;
2900  ys = (si & 0xffff) * q + carry;
2901  zs = (si >> 16) * q + (ys >> 16);
2902  carry = zs >> 16;
2903  y = (*bx & 0xffff) - (ys & 0xffff) - borrow;
2904  borrow = (y & 0x10000) >> 16;
2905  z = (*bx >> 16) - (zs & 0xffff) - borrow;
2906  borrow = (z & 0x10000) >> 16;
2907  Storeinc(bx, z, y);
2908 #else
2909  ys = *sx++ * q + carry;
2910  carry = ys >> 16;
2911  y = *bx - (ys & 0xffff) - borrow;
2912  borrow = (y & 0x10000) >> 16;
2913  *bx++ = y & 0xffff;
2914 #endif
2915 #endif
2916  } while (sx <= sxe);
2917  if (!*bxe) {
2918  bx = b->x;
2919  while (--bxe > bx && !*bxe)
2920  --n;
2921  b->wds = n;
2922  }
2923  }
2924  if (cmp(b, S) >= 0) {
2925  q++;
2926  borrow = 0;
2927  carry = 0;
2928  bx = b->x;
2929  sx = S->x;
2930  do {
2931 #ifdef ULLong
2932  ys = *sx++ + carry;
2933  carry = ys >> 32;
2934  y = *bx - (ys & FFFFFFFF) - borrow;
2935  borrow = y >> 32 & (ULong)1;
2936  *bx++ = (ULong)(y & FFFFFFFF);
2937 #else
2938 #ifdef Pack_32
2939  si = *sx++;
2940  ys = (si & 0xffff) + carry;
2941  zs = (si >> 16) + (ys >> 16);
2942  carry = zs >> 16;
2943  y = (*bx & 0xffff) - (ys & 0xffff) - borrow;
2944  borrow = (y & 0x10000) >> 16;
2945  z = (*bx >> 16) - (zs & 0xffff) - borrow;
2946  borrow = (z & 0x10000) >> 16;
2947  Storeinc(bx, z, y);
2948 #else
2949  ys = *sx++ + carry;
2950  carry = ys >> 16;
2951  y = *bx - (ys & 0xffff) - borrow;
2952  borrow = (y & 0x10000) >> 16;
2953  *bx++ = y & 0xffff;
2954 #endif
2955 #endif
2956  } while (sx <= sxe);
2957  bx = b->x;
2958  bxe = bx + n;
2959  if (!*bxe) {
2960  while (--bxe > bx && !*bxe)
2961  --n;
2962  b->wds = n;
2963  }
2964  }
2965  return q;
2966 }
2967 
2968 #ifndef MULTIPLE_THREADS
2969 static char *dtoa_result;
2970 #endif
2971 
2972 #ifndef MULTIPLE_THREADS
2973 static char *
2974 rv_alloc(int i)
2975 {
2976  return dtoa_result = xmalloc(i);
2977 }
2978 #else
2979 #define rv_alloc(i) xmalloc(i)
2980 #endif
2981 
2982 static char *
2983 nrv_alloc(const char *s, char **rve, size_t n)
2984 {
2985  char *rv, *t;
2986 
2987  t = rv = rv_alloc(n);
2988  while ((*t = *s++) != 0) t++;
2989  if (rve)
2990  *rve = t;
2991  return rv;
2992 }
2993 
2994 #define rv_strdup(s, rve) nrv_alloc((s), (rve), strlen(s)+1)
2995 
2996 #ifndef MULTIPLE_THREADS
2997 /* freedtoa(s) must be used to free values s returned by dtoa
2998  * when MULTIPLE_THREADS is #defined. It should be used in all cases,
2999  * but for consistency with earlier versions of dtoa, it is optional
3000  * when MULTIPLE_THREADS is not defined.
3001  */
3002 
3003 static void
3004 freedtoa(char *s)
3005 {
3006  xfree(s);
3007 }
3008 #endif
3009 
3010 static const char INFSTR[] = "Infinity";
3011 static const char NANSTR[] = "NaN";
3012 static const char ZEROSTR[] = "0";
3013 
3014 /* dtoa for IEEE arithmetic (dmg): convert double to ASCII string.
3015  *
3016  * Inspired by "How to Print Floating-Point Numbers Accurately" by
3017  * Guy L. Steele, Jr. and Jon L. White [Proc. ACM SIGPLAN '90, pp. 112-126].
3018  *
3019  * Modifications:
3020  * 1. Rather than iterating, we use a simple numeric overestimate
3021  * to determine k = floor(log10(d)). We scale relevant
3022  * quantities using O(log2(k)) rather than O(k) multiplications.
3023  * 2. For some modes > 2 (corresponding to ecvt and fcvt), we don't
3024  * try to generate digits strictly left to right. Instead, we
3025  * compute with fewer bits and propagate the carry if necessary
3026  * when rounding the final digit up. This is often faster.
3027  * 3. Under the assumption that input will be rounded nearest,
3028  * mode 0 renders 1e23 as 1e23 rather than 9.999999999999999e22.
3029  * That is, we allow equality in stopping tests when the
3030  * round-nearest rule will give the same floating-point value
3031  * as would satisfaction of the stopping test with strict
3032  * inequality.
3033  * 4. We remove common factors of powers of 2 from relevant
3034  * quantities.
3035  * 5. When converting floating-point integers less than 1e16,
3036  * we use floating-point arithmetic rather than resorting
3037  * to multiple-precision integers.
3038  * 6. When asked to produce fewer than 15 digits, we first try
3039  * to get by with floating-point arithmetic; we resort to
3040  * multiple-precision integer arithmetic only if we cannot
3041  * guarantee that the floating-point calculation has given
3042  * the correctly rounded result. For k requested digits and
3043  * "uniformly" distributed input, the probability is
3044  * something like 10^(k-15) that we must resort to the Long
3045  * calculation.
3046  */
3047 
3048 char *
3049 ruby_dtoa(double d_, int mode, int ndigits, int *decpt, int *sign, char **rve)
3050 {
3051  /* Arguments ndigits, decpt, sign are similar to those
3052  of ecvt and fcvt; trailing zeros are suppressed from
3053  the returned string. If not null, *rve is set to point
3054  to the end of the return value. If d is +-Infinity or NaN,
3055  then *decpt is set to 9999.
3056 
3057  mode:
3058  0 ==> shortest string that yields d when read in
3059  and rounded to nearest.
3060  1 ==> like 0, but with Steele & White stopping rule;
3061  e.g. with IEEE P754 arithmetic , mode 0 gives
3062  1e23 whereas mode 1 gives 9.999999999999999e22.
3063  2 ==> max(1,ndigits) significant digits. This gives a
3064  return value similar to that of ecvt, except
3065  that trailing zeros are suppressed.
3066  3 ==> through ndigits past the decimal point. This
3067  gives a return value similar to that from fcvt,
3068  except that trailing zeros are suppressed, and
3069  ndigits can be negative.
3070  4,5 ==> similar to 2 and 3, respectively, but (in
3071  round-nearest mode) with the tests of mode 0 to
3072  possibly return a shorter string that rounds to d.
3073  With IEEE arithmetic and compilation with
3074  -DHonor_FLT_ROUNDS, modes 4 and 5 behave the same
3075  as modes 2 and 3 when FLT_ROUNDS != 1.
3076  6-9 ==> Debugging modes similar to mode - 4: don't try
3077  fast floating-point estimate (if applicable).
3078 
3079  Values of mode other than 0-9 are treated as mode 0.
3080 
3081  Sufficient space is allocated to the return value
3082  to hold the suppressed trailing zeros.
3083  */
3084 
3085  int bbits, b2, b5, be, dig, i, ieps, ilim, ilim0, ilim1,
3086  j, j1, k, k0, k_check, leftright, m2, m5, s2, s5,
3087  spec_case, try_quick;
3088  Long L;
3089 #ifndef Sudden_Underflow
3090  int denorm;
3091  ULong x;
3092 #endif
3093  Bigint *b, *b1, *delta, *mlo = 0, *mhi = 0, *S;
3094  double ds;
3095  double_u d, d2, eps;
3096  char *s, *s0;
3097 #ifdef Honor_FLT_ROUNDS
3098  int rounding;
3099 #endif
3100 #ifdef SET_INEXACT
3101  int inexact, oldinexact;
3102 #endif
3103 
3104  dval(d) = d_;
3105 
3106 #ifndef MULTIPLE_THREADS
3107  if (dtoa_result) {
3108  freedtoa(dtoa_result);
3109  dtoa_result = 0;
3110  }
3111 #endif
3112 
3113  if (word0(d) & Sign_bit) {
3114  /* set sign for everything, including 0's and NaNs */
3115  *sign = 1;
3116  word0(d) &= ~Sign_bit; /* clear sign bit */
3117  }
3118  else
3119  *sign = 0;
3120 
3121 #if defined(IEEE_Arith) + defined(VAX)
3122 #ifdef IEEE_Arith
3123  if ((word0(d) & Exp_mask) == Exp_mask)
3124 #else
3125  if (word0(d) == 0x8000)
3126 #endif
3127  {
3128  /* Infinity or NaN */
3129  *decpt = 9999;
3130 #ifdef IEEE_Arith
3131  if (!word1(d) && !(word0(d) & 0xfffff))
3132  return rv_strdup(INFSTR, rve);
3133 #endif
3134  return rv_strdup(NANSTR, rve);
3135  }
3136 #endif
3137 #ifdef IBM
3138  dval(d) += 0; /* normalize */
3139 #endif
3140  if (!dval(d)) {
3141  *decpt = 1;
3142  return rv_strdup(ZEROSTR, rve);
3143  }
3144 
3145 #ifdef SET_INEXACT
3146  try_quick = oldinexact = get_inexact();
3147  inexact = 1;
3148 #endif
3149 #ifdef Honor_FLT_ROUNDS
3150  if ((rounding = Flt_Rounds) >= 2) {
3151  if (*sign)
3152  rounding = rounding == 2 ? 0 : 2;
3153  else
3154  if (rounding != 2)
3155  rounding = 0;
3156  }
3157 #endif
3158 
3159  b = d2b(dval(d), &be, &bbits);
3160 #ifdef Sudden_Underflow
3161  i = (int)(word0(d) >> Exp_shift1 & (Exp_mask>>Exp_shift1));
3162 #else
3163  if ((i = (int)(word0(d) >> Exp_shift1 & (Exp_mask>>Exp_shift1))) != 0) {
3164 #endif
3165  dval(d2) = dval(d);
3166  word0(d2) &= Frac_mask1;
3167  word0(d2) |= Exp_11;
3168 #ifdef IBM
3169  if (j = 11 - hi0bits(word0(d2) & Frac_mask))
3170  dval(d2) /= 1 << j;
3171 #endif
3172 
3173  /* log(x) ~=~ log(1.5) + (x-1.5)/1.5
3174  * log10(x) = log(x) / log(10)
3175  * ~=~ log(1.5)/log(10) + (x-1.5)/(1.5*log(10))
3176  * log10(d) = (i-Bias)*log(2)/log(10) + log10(d2)
3177  *
3178  * This suggests computing an approximation k to log10(d) by
3179  *
3180  * k = (i - Bias)*0.301029995663981
3181  * + ( (d2-1.5)*0.289529654602168 + 0.176091259055681 );
3182  *
3183  * We want k to be too large rather than too small.
3184  * The error in the first-order Taylor series approximation
3185  * is in our favor, so we just round up the constant enough
3186  * to compensate for any error in the multiplication of
3187  * (i - Bias) by 0.301029995663981; since |i - Bias| <= 1077,
3188  * and 1077 * 0.30103 * 2^-52 ~=~ 7.2e-14,
3189  * adding 1e-13 to the constant term more than suffices.
3190  * Hence we adjust the constant term to 0.1760912590558.
3191  * (We could get a more accurate k by invoking log10,
3192  * but this is probably not worthwhile.)
3193  */
3194 
3195  i -= Bias;
3196 #ifdef IBM
3197  i <<= 2;
3198  i += j;
3199 #endif
3200 #ifndef Sudden_Underflow
3201  denorm = 0;
3202  }
3203  else {
3204  /* d is denormalized */
3205 
3206  i = bbits + be + (Bias + (P-1) - 1);
3207  x = i > 32 ? word0(d) << (64 - i) | word1(d) >> (i - 32)
3208  : word1(d) << (32 - i);
3209  dval(d2) = x;
3210  word0(d2) -= 31*Exp_msk1; /* adjust exponent */
3211  i -= (Bias + (P-1) - 1) + 1;
3212  denorm = 1;
3213  }
3214 #endif
3215  ds = (dval(d2)-1.5)*0.289529654602168 + 0.1760912590558 + i*0.301029995663981;
3216  k = (int)ds;
3217  if (ds < 0. && ds != k)
3218  k--; /* want k = floor(ds) */
3219  k_check = 1;
3220  if (k >= 0 && k <= Ten_pmax) {
3221  if (dval(d) < tens[k])
3222  k--;
3223  k_check = 0;
3224  }
3225  j = bbits - i - 1;
3226  if (j >= 0) {
3227  b2 = 0;
3228  s2 = j;
3229  }
3230  else {
3231  b2 = -j;
3232  s2 = 0;
3233  }
3234  if (k >= 0) {
3235  b5 = 0;
3236  s5 = k;
3237  s2 += k;
3238  }
3239  else {
3240  b2 -= k;
3241  b5 = -k;
3242  s5 = 0;
3243  }
3244  if (mode < 0 || mode > 9)
3245  mode = 0;
3246 
3247 #ifndef SET_INEXACT
3248 #ifdef Check_FLT_ROUNDS
3249  try_quick = Rounding == 1;
3250 #else
3251  try_quick = 1;
3252 #endif
3253 #endif /*SET_INEXACT*/
3254 
3255  if (mode > 5) {
3256  mode -= 4;
3257  try_quick = 0;
3258  }
3259  leftright = 1;
3260  ilim = ilim1 = -1;
3261  switch (mode) {
3262  case 0:
3263  case 1:
3264  i = 18;
3265  ndigits = 0;
3266  break;
3267  case 2:
3268  leftright = 0;
3269  /* no break */
3270  case 4:
3271  if (ndigits <= 0)
3272  ndigits = 1;
3273  ilim = ilim1 = i = ndigits;
3274  break;
3275  case 3:
3276  leftright = 0;
3277  /* no break */
3278  case 5:
3279  i = ndigits + k + 1;
3280  ilim = i;
3281  ilim1 = i - 1;
3282  if (i <= 0)
3283  i = 1;
3284  }
3285  s = s0 = rv_alloc(i+1);
3286 
3287 #ifdef Honor_FLT_ROUNDS
3288  if (mode > 1 && rounding != 1)
3289  leftright = 0;
3290 #endif
3291 
3292  if (ilim >= 0 && ilim <= Quick_max && try_quick) {
3293 
3294  /* Try to get by with floating-point arithmetic. */
3295 
3296  i = 0;
3297  dval(d2) = dval(d);
3298  k0 = k;
3299  ilim0 = ilim;
3300  ieps = 2; /* conservative */
3301  if (k > 0) {
3302  ds = tens[k&0xf];
3303  j = k >> 4;
3304  if (j & Bletch) {
3305  /* prevent overflows */
3306  j &= Bletch - 1;
3307  dval(d) /= bigtens[n_bigtens-1];
3308  ieps++;
3309  }
3310  for (; j; j >>= 1, i++)
3311  if (j & 1) {
3312  ieps++;
3313  ds *= bigtens[i];
3314  }
3315  dval(d) /= ds;
3316  }
3317  else if ((j1 = -k) != 0) {
3318  dval(d) *= tens[j1 & 0xf];
3319  for (j = j1 >> 4; j; j >>= 1, i++)
3320  if (j & 1) {
3321  ieps++;
3322  dval(d) *= bigtens[i];
3323  }
3324  }
3325  if (k_check && dval(d) < 1. && ilim > 0) {
3326  if (ilim1 <= 0)
3327  goto fast_failed;
3328  ilim = ilim1;
3329  k--;
3330  dval(d) *= 10.;
3331  ieps++;
3332  }
3333  dval(eps) = ieps*dval(d) + 7.;
3334  word0(eps) -= (P-1)*Exp_msk1;
3335  if (ilim == 0) {
3336  S = mhi = 0;
3337  dval(d) -= 5.;
3338  if (dval(d) > dval(eps))
3339  goto one_digit;
3340  if (dval(d) < -dval(eps))
3341  goto no_digits;
3342  goto fast_failed;
3343  }
3344 #ifndef No_leftright
3345  if (leftright) {
3346  /* Use Steele & White method of only
3347  * generating digits needed.
3348  */
3349  dval(eps) = 0.5/tens[ilim-1] - dval(eps);
3350  for (i = 0;;) {
3351  L = (int)dval(d);
3352  dval(d) -= L;
3353  *s++ = '0' + (int)L;
3354  if (dval(d) < dval(eps))
3355  goto ret1;
3356  if (1. - dval(d) < dval(eps))
3357  goto bump_up;
3358  if (++i >= ilim)
3359  break;
3360  dval(eps) *= 10.;
3361  dval(d) *= 10.;
3362  }
3363  }
3364  else {
3365 #endif
3366  /* Generate ilim digits, then fix them up. */
3367  dval(eps) *= tens[ilim-1];
3368  for (i = 1;; i++, dval(d) *= 10.) {
3369  L = (Long)(dval(d));
3370  if (!(dval(d) -= L))
3371  ilim = i;
3372  *s++ = '0' + (int)L;
3373  if (i == ilim) {
3374  if (dval(d) > 0.5 + dval(eps))
3375  goto bump_up;
3376  else if (dval(d) < 0.5 - dval(eps)) {
3377  while (*--s == '0') ;
3378  s++;
3379  goto ret1;
3380  }
3381  break;
3382  }
3383  }
3384 #ifndef No_leftright
3385  }
3386 #endif
3387 fast_failed:
3388  s = s0;
3389  dval(d) = dval(d2);
3390  k = k0;
3391  ilim = ilim0;
3392  }
3393 
3394  /* Do we have a "small" integer? */
3395 
3396  if (be >= 0 && k <= Int_max) {
3397  /* Yes. */
3398  ds = tens[k];
3399  if (ndigits < 0 && ilim <= 0) {
3400  S = mhi = 0;
3401  if (ilim < 0 || dval(d) <= 5*ds)
3402  goto no_digits;
3403  goto one_digit;
3404  }
3405  for (i = 1;; i++, dval(d) *= 10.) {
3406  L = (Long)(dval(d) / ds);
3407  dval(d) -= L*ds;
3408 #ifdef Check_FLT_ROUNDS
3409  /* If FLT_ROUNDS == 2, L will usually be high by 1 */
3410  if (dval(d) < 0) {
3411  L--;
3412  dval(d) += ds;
3413  }
3414 #endif
3415  *s++ = '0' + (int)L;
3416  if (!dval(d)) {
3417 #ifdef SET_INEXACT
3418  inexact = 0;
3419 #endif
3420  break;
3421  }
3422  if (i == ilim) {
3423 #ifdef Honor_FLT_ROUNDS
3424  if (mode > 1)
3425  switch (rounding) {
3426  case 0: goto ret1;
3427  case 2: goto bump_up;
3428  }
3429 #endif
3430  dval(d) += dval(d);
3431  if (dval(d) > ds || (dval(d) == ds && (L & 1))) {
3432 bump_up:
3433  while (*--s == '9')
3434  if (s == s0) {
3435  k++;
3436  *s = '0';
3437  break;
3438  }
3439  ++*s++;
3440  }
3441  break;
3442  }
3443  }
3444  goto ret1;
3445  }
3446 
3447  m2 = b2;
3448  m5 = b5;
3449  if (leftright) {
3450  i =
3451 #ifndef Sudden_Underflow
3452  denorm ? be + (Bias + (P-1) - 1 + 1) :
3453 #endif
3454 #ifdef IBM
3455  1 + 4*P - 3 - bbits + ((bbits + be - 1) & 3);
3456 #else
3457  1 + P - bbits;
3458 #endif
3459  b2 += i;
3460  s2 += i;
3461  mhi = i2b(1);
3462  }
3463  if (m2 > 0 && s2 > 0) {
3464  i = m2 < s2 ? m2 : s2;
3465  b2 -= i;
3466  m2 -= i;
3467  s2 -= i;
3468  }
3469  if (b5 > 0) {
3470  if (leftright) {
3471  if (m5 > 0) {
3472  mhi = pow5mult(mhi, m5);
3473  b1 = mult(mhi, b);
3474  Bfree(b);
3475  b = b1;
3476  }
3477  if ((j = b5 - m5) != 0)
3478  b = pow5mult(b, j);
3479  }
3480  else
3481  b = pow5mult(b, b5);
3482  }
3483  S = i2b(1);
3484  if (s5 > 0)
3485  S = pow5mult(S, s5);
3486 
3487  /* Check for special case that d is a normalized power of 2. */
3488 
3489  spec_case = 0;
3490  if ((mode < 2 || leftright)
3491 #ifdef Honor_FLT_ROUNDS
3492  && rounding == 1
3493 #endif
3494  ) {
3495  if (!word1(d) && !(word0(d) & Bndry_mask)
3496 #ifndef Sudden_Underflow
3497  && word0(d) & (Exp_mask & ~Exp_msk1)
3498 #endif
3499  ) {
3500  /* The special case */
3501  b2 += Log2P;
3502  s2 += Log2P;
3503  spec_case = 1;
3504  }
3505  }
3506 
3507  /* Arrange for convenient computation of quotients:
3508  * shift left if necessary so divisor has 4 leading 0 bits.
3509  *
3510  * Perhaps we should just compute leading 28 bits of S once
3511  * and for all and pass them and a shift to quorem, so it
3512  * can do shifts and ors to compute the numerator for q.
3513  */
3514 #ifdef Pack_32
3515  if ((i = ((s5 ? 32 - hi0bits(S->x[S->wds-1]) : 1) + s2) & 0x1f) != 0)
3516  i = 32 - i;
3517 #else
3518  if ((i = ((s5 ? 32 - hi0bits(S->x[S->wds-1]) : 1) + s2) & 0xf) != 0)
3519  i = 16 - i;
3520 #endif
3521  if (i > 4) {
3522  i -= 4;
3523  b2 += i;
3524  m2 += i;
3525  s2 += i;
3526  }
3527  else if (i < 4) {
3528  i += 28;
3529  b2 += i;
3530  m2 += i;
3531  s2 += i;
3532  }
3533  if (b2 > 0)
3534  b = lshift(b, b2);
3535  if (s2 > 0)
3536  S = lshift(S, s2);
3537  if (k_check) {
3538  if (cmp(b,S) < 0) {
3539  k--;
3540  b = multadd(b, 10, 0); /* we botched the k estimate */
3541  if (leftright)
3542  mhi = multadd(mhi, 10, 0);
3543  ilim = ilim1;
3544  }
3545  }
3546  if (ilim <= 0 && (mode == 3 || mode == 5)) {
3547  if (ilim < 0 || cmp(b,S = multadd(S,5,0)) <= 0) {
3548  /* no digits, fcvt style */
3549 no_digits:
3550  k = -1 - ndigits;
3551  goto ret;
3552  }
3553 one_digit:
3554  *s++ = '1';
3555  k++;
3556  goto ret;
3557  }
3558  if (leftright) {
3559  if (m2 > 0)
3560  mhi = lshift(mhi, m2);
3561 
3562  /* Compute mlo -- check for special case
3563  * that d is a normalized power of 2.
3564  */
3565 
3566  mlo = mhi;
3567  if (spec_case) {
3568  mhi = Balloc(mhi->k);
3569  Bcopy(mhi, mlo);
3570  mhi = lshift(mhi, Log2P);
3571  }
3572 
3573  for (i = 1;;i++) {
3574  dig = quorem(b,S) + '0';
3575  /* Do we yet have the shortest decimal string
3576  * that will round to d?
3577  */
3578  j = cmp(b, mlo);
3579  delta = diff(S, mhi);
3580  j1 = delta->sign ? 1 : cmp(b, delta);
3581  Bfree(delta);
3582 #ifndef ROUND_BIASED
3583  if (j1 == 0 && mode != 1 && !(word1(d) & 1)
3584 #ifdef Honor_FLT_ROUNDS
3585  && rounding >= 1
3586 #endif
3587  ) {
3588  if (dig == '9')
3589  goto round_9_up;
3590  if (j > 0)
3591  dig++;
3592 #ifdef SET_INEXACT
3593  else if (!b->x[0] && b->wds <= 1)
3594  inexact = 0;
3595 #endif
3596  *s++ = dig;
3597  goto ret;
3598  }
3599 #endif
3600  if (j < 0 || (j == 0 && mode != 1
3601 #ifndef ROUND_BIASED
3602  && !(word1(d) & 1)
3603 #endif
3604  )) {
3605  if (!b->x[0] && b->wds <= 1) {
3606 #ifdef SET_INEXACT
3607  inexact = 0;
3608 #endif
3609  goto accept_dig;
3610  }
3611 #ifdef Honor_FLT_ROUNDS
3612  if (mode > 1)
3613  switch (rounding) {
3614  case 0: goto accept_dig;
3615  case 2: goto keep_dig;
3616  }
3617 #endif /*Honor_FLT_ROUNDS*/
3618  if (j1 > 0) {
3619  b = lshift(b, 1);
3620  j1 = cmp(b, S);
3621  if ((j1 > 0 || (j1 == 0 && (dig & 1))) && dig++ == '9')
3622  goto round_9_up;
3623  }
3624 accept_dig:
3625  *s++ = dig;
3626  goto ret;
3627  }
3628  if (j1 > 0) {
3629 #ifdef Honor_FLT_ROUNDS
3630  if (!rounding)
3631  goto accept_dig;
3632 #endif
3633  if (dig == '9') { /* possible if i == 1 */
3634 round_9_up:
3635  *s++ = '9';
3636  goto roundoff;
3637  }
3638  *s++ = dig + 1;
3639  goto ret;
3640  }
3641 #ifdef Honor_FLT_ROUNDS
3642 keep_dig:
3643 #endif
3644  *s++ = dig;
3645  if (i == ilim)
3646  break;
3647  b = multadd(b, 10, 0);
3648  if (mlo == mhi)
3649  mlo = mhi = multadd(mhi, 10, 0);
3650  else {
3651  mlo = multadd(mlo, 10, 0);
3652  mhi = multadd(mhi, 10, 0);
3653  }
3654  }
3655  }
3656  else
3657  for (i = 1;; i++) {
3658  *s++ = dig = quorem(b,S) + '0';
3659  if (!b->x[0] && b->wds <= 1) {
3660 #ifdef SET_INEXACT
3661  inexact = 0;
3662 #endif
3663  goto ret;
3664  }
3665  if (i >= ilim)
3666  break;
3667  b = multadd(b, 10, 0);
3668  }
3669 
3670  /* Round off last digit */
3671 
3672 #ifdef Honor_FLT_ROUNDS
3673  switch (rounding) {
3674  case 0: goto trimzeros;
3675  case 2: goto roundoff;
3676  }
3677 #endif
3678  b = lshift(b, 1);
3679  j = cmp(b, S);
3680  if (j > 0 || (j == 0 && (dig & 1))) {
3681  roundoff:
3682  while (*--s == '9')
3683  if (s == s0) {
3684  k++;
3685  *s++ = '1';
3686  goto ret;
3687  }
3688  ++*s++;
3689  }
3690  else {
3691  while (*--s == '0') ;
3692  s++;
3693  }
3694 ret:
3695  Bfree(S);
3696  if (mhi) {
3697  if (mlo && mlo != mhi)
3698  Bfree(mlo);
3699  Bfree(mhi);
3700  }
3701 ret1:
3702 #ifdef SET_INEXACT
3703  if (inexact) {
3704  if (!oldinexact) {
3705  word0(d) = Exp_1 + (70 << Exp_shift);
3706  word1(d) = 0;
3707  dval(d) += 1.;
3708  }
3709  }
3710  else if (!oldinexact)
3711  clear_inexact();
3712 #endif
3713  Bfree(b);
3714  *s = 0;
3715  *decpt = k + 1;
3716  if (rve)
3717  *rve = s;
3718  return s0;
3719 }
3720 
3721 void
3722 ruby_each_words(const char *str, void (*func)(const char*, int, void*), void *arg)
3723 {
3724  const char *end;
3725  int len;
3726 
3727  if (!str) return;
3728  for (; *str; str = end) {
3729  while (ISSPACE(*str) || *str == ',') str++;
3730  if (!*str) break;
3731  end = str;
3732  while (*end && !ISSPACE(*end) && *end != ',') end++;
3733  len = (int)(end - str); /* assume no string exceeds INT_MAX */
3734  (*func)(str, len, arg);
3735  }
3736 }
3737 
3738 /*-
3739  * Copyright (c) 2004-2008 David Schultz <das@FreeBSD.ORG>
3740  * All rights reserved.
3741  *
3742  * Redistribution and use in source and binary forms, with or without
3743  * modification, are permitted provided that the following conditions
3744  * are met:
3745  * 1. Redistributions of source code must retain the above copyright
3746  * notice, this list of conditions and the following disclaimer.
3747  * 2. Redistributions in binary form must reproduce the above copyright
3748  * notice, this list of conditions and the following disclaimer in the
3749  * documentation and/or other materials provided with the distribution.
3750  *
3751  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
3752  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
3753  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
3754  * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
3755  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
3756  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
3757  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
3758  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
3759  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
3760  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
3761  * SUCH DAMAGE.
3762  */
3763 
3764 #define DBL_MANH_SIZE 20
3765 #define DBL_MANL_SIZE 32
3766 #define DBL_ADJ (DBL_MAX_EXP - 2)
3767 #define SIGFIGS ((DBL_MANT_DIG + 3) / 4 + 1)
3768 #define dexp_get(u) ((int)(word0(u) >> Exp_shift) & ~Exp_msk1)
3769 #define dexp_set(u,v) (word0(u) = (((int)(word0(u)) & ~Exp_mask) | ((v) << Exp_shift)))
3770 #define dmanh_get(u) ((uint32_t)(word0(u) & Frac_mask))
3771 #define dmanl_get(u) ((uint32_t)word1(u))
3772 
3773 
3774 /*
3775  * This procedure converts a double-precision number in IEEE format
3776  * into a string of hexadecimal digits and an exponent of 2. Its
3777  * behavior is bug-for-bug compatible with dtoa() in mode 2, with the
3778  * following exceptions:
3779  *
3780  * - An ndigits < 0 causes it to use as many digits as necessary to
3781  * represent the number exactly.
3782  * - The additional xdigs argument should point to either the string
3783  * "0123456789ABCDEF" or the string "0123456789abcdef", depending on
3784  * which case is desired.
3785  * - This routine does not repeat dtoa's mistake of setting decpt
3786  * to 9999 in the case of an infinity or NaN. INT_MAX is used
3787  * for this purpose instead.
3788  *
3789  * Note that the C99 standard does not specify what the leading digit
3790  * should be for non-zero numbers. For instance, 0x1.3p3 is the same
3791  * as 0x2.6p2 is the same as 0x4.cp3. This implementation always makes
3792  * the leading digit a 1. This ensures that the exponent printed is the
3793  * actual base-2 exponent, i.e., ilogb(d).
3794  *
3795  * Inputs: d, xdigs, ndigits
3796  * Outputs: decpt, sign, rve
3797  */
3798 char *
3799 ruby_hdtoa(double d, const char *xdigs, int ndigits, int *decpt, int *sign,
3800  char **rve)
3801 {
3802  U u;
3803  char *s, *s0;
3804  int bufsize;
3805  uint32_t manh, manl;
3806 
3807  u.d = d;
3808  if (word0(u) & Sign_bit) {
3809  /* set sign for everything, including 0's and NaNs */
3810  *sign = 1;
3811  word0(u) &= ~Sign_bit; /* clear sign bit */
3812  }
3813  else
3814  *sign = 0;
3815 
3816  if (isinf(d)) { /* FP_INFINITE */
3817  *decpt = INT_MAX;
3818  return rv_strdup(INFSTR, rve);
3819  }
3820  else if (isnan(d)) { /* FP_NAN */
3821  *decpt = INT_MAX;
3822  return rv_strdup(NANSTR, rve);
3823  }
3824  else if (d == 0.0) { /* FP_ZERO */
3825  *decpt = 1;
3826  return rv_strdup(ZEROSTR, rve);
3827  }
3828  else if (dexp_get(u)) { /* FP_NORMAL */
3829  *decpt = dexp_get(u) - DBL_ADJ;
3830  }
3831  else { /* FP_SUBNORMAL */
3832  u.d *= 5.363123171977039e+154 /* 0x1p514 */;
3833  *decpt = dexp_get(u) - (514 + DBL_ADJ);
3834  }
3835 
3836  if (ndigits == 0) /* dtoa() compatibility */
3837  ndigits = 1;
3838 
3839  /*
3840  * If ndigits < 0, we are expected to auto-size, so we allocate
3841  * enough space for all the digits.
3842  */
3843  bufsize = (ndigits > 0) ? ndigits : SIGFIGS;
3844  s0 = rv_alloc(bufsize+1);
3845 
3846  /* Round to the desired number of digits. */
3847  if (SIGFIGS > ndigits && ndigits > 0) {
3848  float redux = 1.0f;
3849  volatile double d;
3850  int offset = 4 * ndigits + DBL_MAX_EXP - 4 - DBL_MANT_DIG;
3851  dexp_set(u, offset);
3852  d = u.d;
3853  d += redux;
3854  d -= redux;
3855  u.d = d;
3856  *decpt += dexp_get(u) - offset;
3857  }
3858 
3859  manh = dmanh_get(u);
3860  manl = dmanl_get(u);
3861  *s0 = '1';
3862  for (s = s0 + 1; s < s0 + bufsize; s++) {
3863  *s = xdigs[(manh >> (DBL_MANH_SIZE - 4)) & 0xf];
3864  manh = (manh << 4) | (manl >> (DBL_MANL_SIZE - 4));
3865  manl <<= 4;
3866  }
3867 
3868  /* If ndigits < 0, we are expected to auto-size the precision. */
3869  if (ndigits < 0) {
3870  for (ndigits = SIGFIGS; s0[ndigits - 1] == '0'; ndigits--)
3871  ;
3872  }
3873 
3874  s = s0 + ndigits;
3875  *s = '\0';
3876  if (rve != NULL)
3877  *rve = s;
3878  return (s0);
3879 }
3880 
3881 #ifdef __cplusplus
3882 #if 0
3883 {
3884 #endif
3885 }
3886 #endif
#define d0
#define Sign_bit
Definition: util.c:811
#define dexp_set(u, v)
Definition: util.c:3769
static int lo0bits(ULong *y)
Definition: util.c:1132
#define FLT_RADIX
Definition: numeric.c:34
#define Big1
Definition: util.c:915
#define R(b, x)
Definition: sha2.c:203
size_t strlen(const char *)
int i
Definition: win32ole.c:776
static unsigned char S[8][64]
Definition: crypt.c:382
#define ACQUIRE_DTOA_LOCK(n)
Definition: util.c:948
#define rv_alloc(i)
Definition: util.c:2979
#define d1
#define P
Definition: util.c:798
static Bigint * Balloc(int k)
Definition: util.c:965
#define rv_strdup(s, rve)
Definition: util.c:2994
#define DBL_DIG
Definition: numeric.c:58
#define dmanh_get(u)
Definition: util.c:3770
#define PATH_MAX
static Bigint * pow5mult(Bigint *b, int k)
Definition: util.c:1289
#define med3(a, b, c)
Definition: util.c:268
#define Exp_1
Definition: util.c:801
unsigned long ruby_scan_hex(const char *start, size_t len, size_t *retlen)
Definition: util.c:42
static const char ZEROSTR[]
Definition: util.c:3012
#define dmanl_get(u)
Definition: util.c:3771
#define Kmax
Definition: util.c:952
char * RR
Definition: util.c:264
#define Quick_max
Definition: util.c:815
#define DBL_MANL_SIZE
Definition: util.c:3765
#define Tiny0
Definition: util.c:813
int sign
Definition: util.c:956
#define Bletch
Definition: util.c:807
static void mmswap_(register char *a, register char *b, int mmkind, size_t size, size_t high, size_t low)
Definition: util.c:206
#define C
Definition: util.c:192
static double ulp(double x_)
Definition: util.c:1510
#define Storeinc(a, b, c)
Definition: util.c:779
struct Bigint Bigint
Definition: util.c:960
#define Int_max
Definition: util.c:816
#define Ebits
Definition: util.c:803
#define PRIVATE_mem
Definition: util.c:689
#define ISDIGIT(c)
#define A
Definition: util.c:190
static int hi0bits(register ULong x)
Definition: util.c:1103
static Bigint * lshift(Bigint *b, int k)
Definition: util.c:1341
Definition: util.c:954
static const char NANSTR[]
Definition: util.c:3011
static double private_mem[PRIVATE_mem]
Definition: util.c:690
#define DBL_MAX_10_EXP
Definition: numeric.c:55
#define LSB
Definition: util.c:810
Win32OLEIDispatch * p
Definition: win32ole.c:778
ULong x[1]
Definition: util.c:957
#define Emin
Definition: util.c:800
static char * nrv_alloc(const char *s, char **rve, size_t n)
Definition: util.c:2983
#define fail()
#define dexp_get(u)
Definition: util.c:3768
static unsigned long scan_digits(const char *str, int base, size_t *retlen, int *overflow)
Definition: util.c:59
#define B
Definition: util.c:191
#define Exp_mask
Definition: util.c:797
#define Rounding
Definition: util.c:837
static int quorem(Bigint *b, Bigint *S)
Definition: util.c:2858
#define DBL_MANH_SIZE
Definition: util.c:3764
static double one(void)
Definition: isinf.c:52
#define n_bigtens
Definition: util.c:1809
#define SIGFIGS
Definition: util.c:3767
#define POP(ll, rr)
Definition: util.c:266
#define Bndry_mask1
Definition: util.c:809
void ruby_qsort(void *base, const size_t nel, const size_t size, int(*cmp)(const void *, const void *, void *), void *d)
Definition: util.c:273
RUBY_EXTERN int isinf(double)
Definition: isinf.c:56
int maxwds
Definition: util.c:956
double d
Definition: util.c:750
static Bigint * s2b(const char *s, int nd0, int nd, ULong y9)
Definition: util.c:1069
arg
Definition: ripper.y:1287
static double * pmem_next
Definition: util.c:690
Definition: util.c:750
double ruby_strtod(const char *s00, char **se)
Definition: util.c:1903
#define Scale_Bit
Definition: util.c:1808
#define IEEE_Arith
Definition: util.c:699
SSL_METHOD *(* func)(void)
Definition: ossl_ssl.c:104
int errno
static const double tens[]
Definition: util.c:1786
#define rounded_product(a, b)
Definition: util.c:910
int wds
Definition: util.c:956
static const char INFSTR[]
Definition: util.c:3010
#define Avoid_Underflow
Definition: util.c:818
unsigned char buf[MIME_BUF_SIZE]
Definition: nkf.c:3913
#define no_digits()
static const double bigtens[]
Definition: util.c:1797
static int cmp(Bigint *a, Bigint *b)
Definition: util.c:1395
#define Log2P
Definition: util.c:812
#define rounded_quotient(a, b)
Definition: util.c:911
static Bigint * multadd(Bigint *b, int m, int a)
Definition: util.c:1018
char * strchr(char *, char)
static double b2d(Bigint *a, int *e)
Definition: util.c:1548
#define Ten_pmax
Definition: util.c:806
register unsigned int len
Definition: name2ctype.h:22210
#define mmswap(a, b)
Definition: util.c:229
#define isnan(x)
Definition: win32.h:334
void rb_sys_fail(const char *mesg)
Definition: error.c:1671
#define MALLOC
Definition: util.c:677
#define DBL_MANT_DIG
Definition: acosh.c:19
#define Tiny1
Definition: util.c:814
#define ULLong
Definition: util.c:938
#define word1(x)
Definition: util.c:766
#define CHAR_BIT
Definition: ruby.h:192
#define DBL_MAX_EXP
Definition: numeric.c:49
void xfree(void *)
unsigned long ruby_scan_oct(const char *start, size_t len, size_t *retlen)
Definition: util.c:28
static Bigint * p5s
Definition: util.c:1286
unsigned int uint32_t
Definition: sha2.h:101
#define Bndry_mask
Definition: util.c:808
unsigned int top
Definition: nkf.c:3914
#define IEEE_LITTLE_ENDIAN
Definition: util.c:633
#define Exp_shift1
Definition: util.c:794
int size
Definition: encoding.c:51
#define DBL_ADJ
Definition: util.c:3766
static Bigint * d2b(double d_, int *e, int *bits)
Definition: util.c:1613
#define xmalloc
Definition: defines.h:64
#define PUSH(ll, rr)
Definition: util.c:265
char * ruby_hdtoa(double d, const char *xdigs, int ndigits, int *decpt, int *sign, char **rve)
Definition: util.c:3799
#define Exp_msk11
Definition: util.c:796
U double_u
Definition: util.c:763
#define Frac_mask1
Definition: util.c:805
#define FREE_DTOA_LOCK(n)
Definition: util.c:949
#define mmprepare(base, size)
Definition: util.c:195
#define mmrot3(a, b, c)
Definition: util.c:253
static Bigint * diff(Bigint *a, Bigint *b)
Definition: util.c:1424
#define Big0
Definition: util.c:914
struct Bigint * next
Definition: util.c:955
v
Definition: win32ole.c:790
#define Exp_msk1
Definition: util.c:795
static double ratio(Bigint *a, Bigint *b)
Definition: util.c:1750
int k
Definition: util.c:956
#define xrealloc
Definition: defines.h:67
static void Bfree(Bigint *v)
Definition: util.c:1000
#define FFFFFFFF
Definition: util.c:921
unsigned long ruby_strtoul(const char *str, char **endptr, int base)
Definition: util.c:106
#define Flt_Rounds
Definition: util.c:828
char * ruby_getcwd(void)
Definition: util.c:437
void ruby_each_words(const char *str, void(*func)(const char *, int, void *), void *arg)
Definition: util.c:3722
static void mmrot3_(register char *a, register char *b, register char *c, int mmkind, size_t size, size_t high, size_t low)
Definition: util.c:231
#define long
Definition: name2ctype.h:37
static const double tinytens[]
Definition: util.c:1798
#define Bcopy(x, y)
Definition: util.c:1014
#define word0(x)
Definition: util.c:765
#define NULL
Definition: _sdbm.c:107
static Bigint * freelist[Kmax+1]
Definition: util.c:962
static int match(VALUE str, VALUE pat, VALUE hash, int(*cb)(VALUE, VALUE))
Definition: date_parse.c:245
#define Exp_11
Definition: util.c:802
#define dval(x)
Definition: util.c:771
char * ruby_strdup(const char *str)
Definition: util.c:425
static Bigint * i2b(int i)
Definition: util.c:1175
static Bigint * mult(Bigint *a, Bigint *b)
Definition: util.c:1186
#define Bias
Definition: util.c:799
#define ISSPACE(c)
Definition: ruby.h:1453
#define Frac_mask
Definition: util.c:804
#define Exp_shift
Definition: util.c:793
char * ruby_dtoa(double d_, int mode, int ndigits, int *decpt, int *sign, char **rve)
Definition: util.c:3049
#define FREE
Definition: util.c:682