drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
dtoa.cc
1/* Copyright (C) 2007 MySQL AB
2 This program is free software; you can redistribute it and/or modify
3 it under the terms of the GNU General Public License as published by
4 the Free Software Foundation; either version 2 of the License, or
5 (at your option) any later version.
6
7 This program is distributed in the hope that it will be useful,
8 but WITHOUT ANY WARRANTY; without even the implied warranty of
9 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 GNU General Public License for more details.
11
12 You should have received a copy of the GNU General Public License
13 along with this program; if not, write to the Free Software
14 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
15
16/****************************************************************
17
18 This file incorporates work covered by the following copyright and
19 permission notice:
20
21 The author of this software is David M. Gay.
22
23 Copyright (C) 1991, 2000, 2001 by Lucent Technologies.
24
25 Permission to use, copy, modify, and distribute this software for any
26 purpose without fee is hereby granted, provided that this entire notice
27 is included in all copies of any software which is or includes a copy
28 or modification of this software and in all copies of the supporting
29 documentation for such software.
30
31 THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
32 WARRANTY. IN PARTICULAR, NEITHER THE AUTHOR NOR LUCENT MAKES ANY
33 REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
34 OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
35
36 ***************************************************************/
37
38#include <config.h>
39
40#include <drizzled/internal/m_string.h> /* for memcpy and NOT_FIXED_DEC */
41
42#include <cfloat>
43
44#include <cstdlib>
45#include <cerrno>
46#include <algorithm>
47
48#include "drizzled/compare_double.h"
49
50using namespace std;
51
52namespace drizzled
53{
54namespace internal
55{
56
57/* Magic value returned by dtoa() to indicate overflow */
58#define DTOA_OVERFLOW 9999
59
60static double my_strtod_int(const char *, char **, int *);
61static char *dtoa(double, int, int, int *, int *, char **);
62
93
94size_t my_fcvt(double x, int precision, char *to, bool *error)
95{
96 int decpt, sign, len, i;
97 char *res, *src, *end, *dst= to;
98 assert(precision >= 0 && precision < NOT_FIXED_DEC && to != NULL);
99
100 res= dtoa(x, 5, precision, &decpt, &sign, &end);
101
102 if (decpt == DTOA_OVERFLOW)
103 {
104 free(res);
105 *to++= '0';
106 *to= '\0';
107 if (error != NULL)
108 *error= true;
109 return 1;
110 }
111
112 src= res;
113 len= end - src;
114
115 if (sign)
116 *dst++= '-';
117
118 if (decpt <= 0)
119 {
120 *dst++= '0';
121 *dst++= '.';
122 for (i= decpt; i < 0; i++)
123 *dst++= '0';
124 }
125
126 for (i= 1; i <= len; i++)
127 {
128 *dst++= *src++;
129 if (i == decpt && i < len)
130 *dst++= '.';
131 }
132 while (i++ <= decpt)
133 *dst++= '0';
134
135 if (precision > 0)
136 {
137 if (len <= decpt)
138 *dst++= '.';
139
140 for (i= precision - max(0, (len - decpt)); i > 0; i--)
141 *dst++= '0';
142 }
143
144 *dst= '\0';
145 if (error != NULL)
146 *error= false;
147
148 free(res);
149
150 return dst - to;
151}
152
215
216size_t my_gcvt(double x, my_gcvt_arg_type type, int width, char *to,
217 bool *error)
218{
219 int decpt, sign, len, exp_len;
220 char *res, *src, *end, *dst= to, *dend= dst + width;
221 bool have_space, force_e_format;
222 assert(width > 0 && to != NULL);
223
224 /* We want to remove '-' from equations early */
225 if (x < 0.)
226 width--;
227
228 res= dtoa(x, 4, type == MY_GCVT_ARG_DOUBLE ? min(width, DBL_DIG) :
229 min(width, FLT_DIG), &decpt, &sign, &end);
230
231 if (decpt == DTOA_OVERFLOW)
232 {
233 free(res);
234 *to++= '0';
235 *to= '\0';
236 if (error != NULL)
237 *error= true;
238 return 1;
239 }
240
241 if (error != NULL)
242 *error= false;
243
244 src= res;
245 len= end - res;
246
247 /*
248 Number of digits in the exponent from the 'e' conversion.
249 The sign of the exponent is taken into account separetely, we don't need
250 to count it here.
251 */
252 exp_len= 1 + (decpt >= 101 || decpt <= -99) + (decpt >= 11 || decpt <= -9);
253
254 /*
255 Do we have enough space for all digits in the 'f' format?
256 Let 'len' be the number of significant digits returned by dtoa,
257 and F be the length of the resulting decimal representation.
258 Consider the following cases:
259 1. decpt <= 0, i.e. we have "0.NNN" => F = len - decpt + 2
260 2. 0 < decpt < len, i.e. we have "NNN.NNN" => F = len + 1
261 3. len <= decpt, i.e. we have "NNN00" => F = decpt
262 */
263 have_space= (decpt <= 0 ? len - decpt + 2 :
264 decpt > 0 && decpt < len ? len + 1 :
265 decpt) <= width;
266 /*
267 The following is true when no significant digits can be placed with the
268 specified field width using the 'f' format, and the 'e' format
269 will not be truncated.
270 */
271 force_e_format= (decpt <= 0 && width <= 2 - decpt && width >= 3 + exp_len);
272 /*
273 Assume that we don't have enough space to place all significant digits in
274 the 'f' format. We have to choose between the 'e' format and the 'f' one
275 to keep as many significant digits as possible.
276 Let E and F be the lengths of decimal representaion in the 'e' and 'f'
277 formats, respectively. We want to use the 'f' format if, and only if F <= E.
278 Consider the following cases:
279 1. decpt <= 0.
280 F = len - decpt + 2 (see above)
281 E = len + (len > 1) + 1 + 1 (decpt <= -99) + (decpt <= -9) + 1
282 ("N.NNe-MMM")
283 (F <= E) <=> (len == 1 && decpt >= -1) || (len > 1 && decpt >= -2)
284 We also need to ensure that if the 'f' format is chosen,
285 the field width allows us to place at least one significant digit
286 (i.e. width > 2 - decpt). If not, we prefer the 'e' format.
287 2. 0 < decpt < len
288 F = len + 1 (see above)
289 E = len + 1 + 1 + ... ("N.NNeMMM")
290 F is always less than E.
291 3. len <= decpt <= width
292 In this case we have enough space to represent the number in the 'f'
293 format, so we prefer it with some exceptions.
294 4. width < decpt
295 The number cannot be represented in the 'f' format at all, always use
296 the 'e' 'one.
297 */
298 if ((have_space ||
299 /*
300 Not enough space, let's see if the 'f' format provides the most number
301 of significant digits.
302 */
303 ((decpt <= width && (decpt >= -1 || (decpt == -2 &&
304 (len > 1 || !force_e_format)))) &&
305 !force_e_format)) &&
306
307 /*
308 Use the 'e' format in some cases even if we have enough space for the
309 'f' one. See comment for MAX_DECPT_FOR_F_FORMAT.
310 */
311 (!have_space || (decpt >= -MAX_DECPT_FOR_F_FORMAT + 1 &&
312 (decpt <= MAX_DECPT_FOR_F_FORMAT || len > decpt))))
313 {
314 /* 'f' format */
315 int i;
316
317 width-= (decpt < len) + (decpt <= 0 ? 1 - decpt : 0);
318
319 /* Do we have to truncate any digits? */
320 if (width < len)
321 {
322 if (width < decpt)
323 {
324 if (error != NULL)
325 *error= true;
326 width= decpt;
327 }
328
329 /*
330 We want to truncate (len - width) least significant digits after the
331 decimal point. For this we are calling dtoa with mode=5, passing the
332 number of significant digits = (len-decpt) - (len-width) = width-decpt
333 */
334 free(res);
335 res= dtoa(x, 5, width - decpt, &decpt, &sign, &end);
336 src= res;
337 len= end - res;
338 }
339
340 if (len == 0)
341 {
342 /* Underflow. Just print '0' and exit */
343 *dst++= '0';
344 goto end;
345 }
346
347 /*
348 At this point we are sure we have enough space to put all digits
349 returned by dtoa
350 */
351 if (sign && dst < dend)
352 *dst++= '-';
353 if (decpt <= 0)
354 {
355 if (dst < dend)
356 *dst++= '0';
357 if (len > 0 && dst < dend)
358 *dst++= '.';
359 for (; decpt < 0 && dst < dend; decpt++)
360 *dst++= '0';
361 }
362
363 for (i= 1; i <= len && dst < dend; i++)
364 {
365 *dst++= *src++;
366 if (i == decpt && i < len && dst < dend)
367 *dst++= '.';
368 }
369 while (i++ <= decpt && dst < dend)
370 *dst++= '0';
371 }
372 else
373 {
374 /* 'e' format */
375 int decpt_sign= 0;
376
377 if (--decpt < 0)
378 {
379 decpt= -decpt;
380 width--;
381 decpt_sign= 1;
382 }
383 width-= 1 + exp_len; /* eNNN */
384
385 if (len > 1)
386 width--;
387
388 if (width <= 0)
389 {
390 /* Overflow */
391 if (error != NULL)
392 *error= true;
393 width= 0;
394 }
395
396 /* Do we have to truncate any digits? */
397 if (width < len)
398 {
399 /* Yes, re-convert with a smaller width */
400 free(res);
401 res= dtoa(x, 4, width, &decpt, &sign, &end);
402 src= res;
403 len= end - res;
404 if (--decpt < 0)
405 decpt= -decpt;
406 }
407 /*
408 At this point we are sure we have enough space to put all digits
409 returned by dtoa
410 */
411 if (sign && dst < dend)
412 *dst++= '-';
413 if (dst < dend)
414 *dst++= *src++;
415 if (len > 1 && dst < dend)
416 {
417 *dst++= '.';
418 while (src < end && dst < dend)
419 *dst++= *src++;
420 }
421 if (dst < dend)
422 *dst++= 'e';
423 if (decpt_sign && dst < dend)
424 *dst++= '-';
425
426 if (decpt >= 100 && dst < dend)
427 {
428 *dst++= decpt / 100 + '0';
429 decpt%= 100;
430 if (dst < dend)
431 *dst++= decpt / 10 + '0';
432 }
433 else if (decpt >= 10 && dst < dend)
434 *dst++= decpt / 10 + '0';
435 if (dst < dend)
436 *dst++= decpt % 10 + '0';
437
438 }
439
440end:
441 free(res);
442 *dst= '\0';
443
444 return dst - to;
445}
446
464
465double my_strtod(const char *str, char **end, int *error)
466{
467 double res;
468 assert(str != NULL && end != NULL && *end != NULL && error != NULL);
469
470 res= my_strtod_int(str, end, error);
471 return (*error == 0) ? res : (res < 0 ? -DBL_MAX : DBL_MAX);
472}
473
474
475double my_atof(const char *nptr)
476{
477 int error;
478 const char *end= nptr+65535; /* Should be enough */
479 return (my_strtod(nptr, (char**) &end, &error));
480}
481
482
483/****************************************************************
484 *
485 * The author of this software is David M. Gay.
486 *
487 * Copyright (C) 1991, 2000, 2001 by Lucent Technologies.
488 *
489 * Permission to use, copy, modify, and distribute this software for any
490 * purpose without fee is hereby granted, provided that this entire notice
491 * is included in all copies of any software which is or includes a copy
492 * or modification of this software and in all copies of the supporting
493 * documentation for such software.
494 *
495 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
496 * WARRANTY. IN PARTICULAR, NEITHER THE AUTHOR NOR LUCENT MAKES ANY
497 * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
498 * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
499 *
500 ***************************************************************/
501/* Please send bug reports to David M. Gay (dmg at acm dot org,
502 * with " at " changed at "@" and " dot " changed to "."). */
503
504/*
505 Original copy of the software is located at http://www.netlib.org/fp/dtoa.c
506 It was adjusted to serve MySQL server needs:
507 * strtod() was modified to not expect a zero-terminated string.
508 It now honors 'se' (end of string) argument as the input parameter,
509 not just as the output one.
510 * in dtoa(), in case of overflow/underflow/NaN result string now contains "0";
511 decpt is set to DTOA_OVERFLOW to indicate overflow.
512 * support for VAX, IBM mainframe and 16-bit hardware removed
513 * we always assume that 64-bit integer type is available
514 * support for Kernigan-Ritchie style headers (pre-ANSI compilers)
515 removed
516 * all gcc warnings ironed out
517 * we always assume multithreaded environment, so we had to change
518 memory allocation procedures to use stack in most cases;
519 malloc is used as the last resort.
520 * pow5mult rewritten to use pre-calculated pow5 list instead of
521 the one generated on the fly.
522*/
523
524
525/*
526 On a machine with IEEE extended-precision registers, it is
527 necessary to specify double-precision (53-bit) rounding precision
528 before invoking strtod or dtoa. If the machine uses (the equivalent
529 of) Intel 80x87 arithmetic, the call
530 _control87(PC_53, MCW_PC);
531 does this with many compilers. Whether this or another call is
532 appropriate depends on the compiler; for this to work, it may be
533 necessary to #include "float.h" or another system-dependent header
534 file.
535*/
536
537typedef int32_t Long;
538typedef uint32_t ULong;
539typedef int64_t LLong;
540typedef uint64_t ULLong;
541
542typedef union { double d; ULong L[2]; } U;
543
544#if defined(WORDS_BIGENDIAN) || (defined(__FLOAT_WORD_ORDER) && \
545 (__FLOAT_WORD_ORDER == __BIG_ENDIAN))
546#define word0(x) ((U*)&x)->L[0]
547#define word1(x) ((U*)&x)->L[1]
548#else
549#define word0(x) ((U*)&x)->L[1]
550#define word1(x) ((U*)&x)->L[0]
551#endif
552
553#define dval(x) ((U*)&x)->d
554
555/* #define P DBL_MANT_DIG */
556/* Ten_pmax= floor(P*log(2)/log(5)) */
557/* Bletch= (highest power of 2 < DBL_MAX_10_EXP) / 16 */
558/* Quick_max= floor((P-1)*log(FLT_RADIX)/log(10) - 1) */
559/* Int_max= floor(P*log(FLT_RADIX)/log(10) - 1) */
560
561#define Exp_shift 20
562#define Exp_shift1 20
563#define Exp_msk1 0x100000
564#define Exp_mask 0x7ff00000
565#define P 53
566#define Bias 1023
567#define Emin (-1022)
568#define Exp_1 0x3ff00000
569#define Exp_11 0x3ff00000
570#define Ebits 11
571#define Frac_mask 0xfffff
572#define Frac_mask1 0xfffff
573#define Ten_pmax 22
574#define Bletch 0x10
575#define Bndry_mask 0xfffff
576#define Bndry_mask1 0xfffff
577#define LSB 1
578#define Sign_bit 0x80000000
579#define Log2P 1
580#define Tiny1 1
581#define Quick_max 14
582#define Int_max 14
583
584#ifndef Flt_Rounds
585#ifdef FLT_ROUNDS
586#define Flt_Rounds FLT_ROUNDS
587#else
588#define Flt_Rounds 1
589#endif
590#endif /*Flt_Rounds*/
591
592#define rounded_product(a,b) a*= b
593#define rounded_quotient(a,b) a/= b
594
595#define Big0 (Frac_mask1 | Exp_msk1*(DBL_MAX_EXP+Bias-1))
596#define Big1 0xffffffff
597#define FFFFFFFF 0xffffffffUL
598
599/* Arbitrary-length integer */
600
601typedef struct Bigint
602{
603 union {
604 ULong *x; /* points right after this Bigint object */
605 } p;
606 int k; /* 2^k = maxwds */
607 int maxwds; /* maximum length in 32-bit words */
608 int sign; /* not zero if number is negative */
609 int wds; /* current length in 32-bit words */
610} Bigint;
611
612static Bigint *Bcopy(Bigint* dst, Bigint* src)
613{
614 dst->sign= src->sign;
615 dst->wds= src->wds;
616
617 assert(dst->maxwds >= src->wds);
618
619 memcpy(dst->p.x, src->p.x, src->wds*sizeof(ULong));
620
621 return dst;
622}
623
624static Bigint *Balloc(int k)
625{
626 int x= 1 << k;
627 Bigint* rv= (Bigint*) malloc(sizeof(Bigint));
628
629 rv->p.x= (ULong*)malloc(x * sizeof(ULong));
630
631 rv->k= k;
632 rv->maxwds= x;
633
634 rv->sign= rv->wds= 0;
635
636 return rv;
637}
638
639
640/*
641 If object was allocated on stack, try putting it to the free
642 list. Otherwise call free().
643*/
644
645static void Bfree(Bigint *v)
646{
647 if(!v)
648 return;
649 free(v->p.x);
650 free(v);
651}
652
653/* Bigint arithmetic functions */
654
655/* Multiply by m and add a */
656
657static Bigint *multadd(Bigint *b, int m, int a)
658{
659 int i, wds;
660 ULong *x;
661 ULLong carry, y;
662 Bigint *b1;
663
664 wds= b->wds;
665 x= b->p.x;
666 i= 0;
667 carry= a;
668 do
669 {
670 y= *x * (ULLong)m + carry;
671 carry= y >> 32;
672 *x++= (ULong)(y & FFFFFFFF);
673 }
674 while (++i < wds);
675 if (carry)
676 {
677 if (wds >= b->maxwds)
678 {
679 b1= Balloc(b->k+1);
680 Bcopy(b1, b);
681 Bfree(b);
682 b= b1;
683 }
684 b->p.x[wds++]= (ULong) carry;
685 b->wds= wds;
686 }
687 return b;
688}
689
690
691static Bigint *s2b(const char *s, int nd0, int nd, ULong y9)
692{
693 Bigint *b;
694 int i, k;
695 Long x, y;
696
697 x= (nd + 8) / 9;
698 for (k= 0, y= 1; x > y; y <<= 1, k++) ;
699 b= Balloc(k);
700 b->p.x[0]= y9;
701 b->wds= 1;
702
703 i= 9;
704 if (9 < nd0)
705 {
706 s+= 9;
707 do
708 b= multadd(b, 10, *s++ - '0');
709 while (++i < nd0);
710 s++;
711 }
712 else
713 s+= 10;
714 for(; i < nd; i++)
715 b= multadd(b, 10, *s++ - '0');
716 return b;
717}
718
719
720static int hi0bits(ULong x)
721{
722 int k= 0;
723
724 if (!(x & 0xffff0000))
725 {
726 k= 16;
727 x<<= 16;
728 }
729 if (!(x & 0xff000000))
730 {
731 k+= 8;
732 x<<= 8;
733 }
734 if (!(x & 0xf0000000))
735 {
736 k+= 4;
737 x<<= 4;
738 }
739 if (!(x & 0xc0000000))
740 {
741 k+= 2;
742 x<<= 2;
743 }
744 if (!(x & 0x80000000))
745 {
746 k++;
747 if (!(x & 0x40000000))
748 return 32;
749 }
750 return k;
751}
752
753
754static int lo0bits(ULong *y)
755{
756 int k;
757 ULong x= *y;
758
759 if (x & 7)
760 {
761 if (x & 1)
762 return 0;
763 if (x & 2)
764 {
765 *y= x >> 1;
766 return 1;
767 }
768 *y= x >> 2;
769 return 2;
770 }
771 k= 0;
772 if (!(x & 0xffff))
773 {
774 k= 16;
775 x>>= 16;
776 }
777 if (!(x & 0xff))
778 {
779 k+= 8;
780 x>>= 8;
781 }
782 if (!(x & 0xf))
783 {
784 k+= 4;
785 x>>= 4;
786 }
787 if (!(x & 0x3))
788 {
789 k+= 2;
790 x>>= 2;
791 }
792 if (!(x & 1))
793 {
794 k++;
795 x>>= 1;
796 if (!x)
797 return 32;
798 }
799 *y= x;
800 return k;
801}
802
803
804/* Convert integer to Bigint number */
805
806static Bigint *i2b(int i)
807{
808 Bigint *b;
809
810 b= Balloc(1);
811 b->p.x[0]= i;
812 b->wds= 1;
813 return b;
814}
815
816
817/* Multiply two Bigint numbers */
818
819static Bigint *mult(Bigint *a, Bigint *b)
820{
821 Bigint *c;
822 int k, wa, wb, wc;
823 ULong *x, *xa, *xae, *xb, *xbe, *xc, *xc0;
824 ULong y;
825 ULLong carry, z;
826
827 if (a->wds < b->wds)
828 {
829 c= a;
830 a= b;
831 b= c;
832 }
833 k= a->k;
834 wa= a->wds;
835 wb= b->wds;
836 wc= wa + wb;
837 if (wc > a->maxwds)
838 k++;
839 c= Balloc(k);
840 for (x= c->p.x, xa= x + wc; x < xa; x++)
841 *x= 0;
842 xa= a->p.x;
843 xae= xa + wa;
844 xb= b->p.x;
845 xbe= xb + wb;
846 xc0= c->p.x;
847 for (; xb < xbe; xc0++)
848 {
849 if ((y= *xb++))
850 {
851 x= xa;
852 xc= xc0;
853 carry= 0;
854 do
855 {
856 z= *x++ * (ULLong)y + *xc + carry;
857 carry= z >> 32;
858 *xc++= (ULong) (z & FFFFFFFF);
859 }
860 while (x < xae);
861 *xc= (ULong) carry;
862 }
863 }
864 for (xc0= c->p.x, xc= xc0 + wc; wc > 0 && !*--xc; --wc) ;
865 c->wds= wc;
866 return c;
867}
868
869
870/*
871 Precalculated array of powers of 5: tested to be enough for
872 vasting majority of dtoa_r cases.
873*/
874
875static ULong powers5[]=
876{
877 625UL,
878
879 390625UL,
880
881 2264035265UL, 35UL,
882
883 2242703233UL, 762134875UL, 1262UL,
884
885 3211403009UL, 1849224548UL, 3668416493UL, 3913284084UL, 1593091UL,
886
887 781532673UL, 64985353UL, 253049085UL, 594863151UL, 3553621484UL,
888 3288652808UL, 3167596762UL, 2788392729UL, 3911132675UL, 590UL,
889
890 2553183233UL, 3201533787UL, 3638140786UL, 303378311UL, 1809731782UL,
891 3477761648UL, 3583367183UL, 649228654UL, 2915460784UL, 487929380UL,
892 1011012442UL, 1677677582UL, 3428152256UL, 1710878487UL, 1438394610UL,
893 2161952759UL, 4100910556UL, 1608314830UL, 349175UL
894};
895
896
897static Bigint p5_a[]=
898{
899 /* { x } - k - maxwds - sign - wds */
900 { { powers5 }, 1, 1, 0, 1 },
901 { { powers5 + 1 }, 1, 1, 0, 1 },
902 { { powers5 + 2 }, 1, 2, 0, 2 },
903 { { powers5 + 4 }, 2, 3, 0, 3 },
904 { { powers5 + 7 }, 3, 5, 0, 5 },
905 { { powers5 + 12 }, 4, 10, 0, 10 },
906 { { powers5 + 22 }, 5, 19, 0, 19 }
907};
908
909#define P5A_MAX (sizeof(p5_a)/sizeof(*p5_a) - 1)
910
911static Bigint *pow5mult(Bigint *b, int k)
912{
913 Bigint *b1, *p5, *p51;
914 int i;
915 static int p05[3]= { 5, 25, 125 };
916
917 if ((i= k & 3))
918 b= multadd(b, p05[i-1], 0);
919
920 if (!(k>>= 2))
921 return b;
922 p5= p5_a;
923 for (;;)
924 {
925 if (k & 1)
926 {
927 b1= mult(b, p5);
928 Bfree(b);
929 b= b1;
930 }
931 if (!(k>>= 1))
932 break;
933 /* Calculate next power of 5 */
934 if (p5 < p5_a + P5A_MAX)
935 ++p5;
936 else if (p5 == p5_a + P5A_MAX)
937 p5= mult(p5, p5);
938 else
939 {
940 p51= mult(p5, p5);
941 Bfree(p5);
942 p5= p51;
943 }
944 }
945 return b;
946}
947
948
949static Bigint *lshift(Bigint *b, int k)
950{
951 int i, k1, n, n1;
952 Bigint *b1;
953 ULong *x, *x1, *xe, z;
954
955 n= k >> 5;
956 k1= b->k;
957 n1= n + b->wds + 1;
958 for (i= b->maxwds; n1 > i; i<<= 1)
959 k1++;
960 b1= Balloc(k1);
961 x1= b1->p.x;
962 for (i= 0; i < n; i++)
963 *x1++= 0;
964 x= b->p.x;
965 xe= x + b->wds;
966 if (k&= 0x1f)
967 {
968 k1= 32 - k;
969 z= 0;
970 do
971 {
972 *x1++= *x << k | z;
973 z= *x++ >> k1;
974 }
975 while (x < xe);
976 if ((*x1= z))
977 ++n1;
978 }
979 else
980 do
981 *x1++= *x++;
982 while (x < xe);
983 b1->wds= n1 - 1;
984 Bfree(b);
985 return b1;
986}
987
988
989static int cmp(Bigint *a, Bigint *b)
990{
991 ULong *xa, *xa0, *xb, *xb0;
992 int i, j;
993
994 i= a->wds;
995 j= b->wds;
996 if (i-= j)
997 return i;
998 xa0= a->p.x;
999 xa= xa0 + j;
1000 xb0= b->p.x;
1001 xb= xb0 + j;
1002 for (;;)
1003 {
1004 if (*--xa != *--xb)
1005 return *xa < *xb ? -1 : 1;
1006 if (xa <= xa0)
1007 break;
1008 }
1009 return 0;
1010}
1011
1012
1013static Bigint *diff(Bigint *a, Bigint *b)
1014{
1015 Bigint *c;
1016 int i, wa, wb;
1017 ULong *xa, *xae, *xb, *xbe, *xc;
1018 ULLong borrow, y;
1019
1020 i= cmp(a,b);
1021 if (!i)
1022 {
1023 c= Balloc(0);
1024 c->wds= 1;
1025 c->p.x[0]= 0;
1026 return c;
1027 }
1028 if (i < 0)
1029 {
1030 c= a;
1031 a= b;
1032 b= c;
1033 i= 1;
1034 }
1035 else
1036 i= 0;
1037 c= Balloc(a->k);
1038 c->sign= i;
1039 wa= a->wds;
1040 xa= a->p.x;
1041 xae= xa + wa;
1042 wb= b->wds;
1043 xb= b->p.x;
1044 xbe= xb + wb;
1045 xc= c->p.x;
1046 borrow= 0;
1047 do
1048 {
1049 y= (ULLong)*xa++ - *xb++ - borrow;
1050 borrow= y >> 32 & (ULong)1;
1051 *xc++= (ULong) (y & FFFFFFFF);
1052 }
1053 while (xb < xbe);
1054 while (xa < xae)
1055 {
1056 y= *xa++ - borrow;
1057 borrow= y >> 32 & (ULong)1;
1058 *xc++= (ULong) (y & FFFFFFFF);
1059 }
1060 while (!*--xc)
1061 wa--;
1062 c->wds= wa;
1063 return c;
1064}
1065
1066
1067static double ulp(double x)
1068{
1069 Long L;
1070 double a;
1071
1072 L= (word0(x) & Exp_mask) - (P - 1)*Exp_msk1;
1073 word0(a) = L;
1074 word1(a) = 0;
1075 return dval(a);
1076}
1077
1078
1079static double b2d(Bigint *a, int *e)
1080{
1081 ULong *xa, *xa0, w, y, z;
1082 int k;
1083 double d;
1084#define d0 word0(d)
1085#define d1 word1(d)
1086
1087 xa0= a->p.x;
1088 xa= xa0 + a->wds;
1089 y= *--xa;
1090 k= hi0bits(y);
1091 *e= 32 - k;
1092 if (k < Ebits)
1093 {
1094 d0= Exp_1 | y >> (Ebits - k);
1095 w= xa > xa0 ? *--xa : 0;
1096 d1= y << ((32-Ebits) + k) | w >> (Ebits - k);
1097 goto ret_d;
1098 }
1099 z= xa > xa0 ? *--xa : 0;
1100 if (k-= Ebits)
1101 {
1102 d0= Exp_1 | y << k | z >> (32 - k);
1103 y= xa > xa0 ? *--xa : 0;
1104 d1= z << k | y >> (32 - k);
1105 }
1106 else
1107 {
1108 d0= Exp_1 | y;
1109 d1= z;
1110 }
1111 ret_d:
1112#undef d0
1113#undef d1
1114 return dval(d);
1115}
1116
1117
1118static Bigint *d2b(double d, int *e, int *bits)
1119{
1120 Bigint *b;
1121 int de, k;
1122 ULong *x, y, z;
1123 int i;
1124#define d0 word0(d)
1125#define d1 word1(d)
1126
1127 b= Balloc(1);
1128 x= b->p.x;
1129
1130 z= d0 & Frac_mask;
1131 d0 &= 0x7fffffff; /* clear sign bit, which we ignore */
1132 if ((de= (int)(d0 >> Exp_shift)))
1133 z|= Exp_msk1;
1134 if ((y= d1))
1135 {
1136 if ((k= lo0bits(&y)))
1137 {
1138 x[0]= y | z << (32 - k);
1139 z>>= k;
1140 }
1141 else
1142 x[0]= y;
1143 i= b->wds= (x[1]= z) ? 2 : 1;
1144 }
1145 else
1146 {
1147 k= lo0bits(&z);
1148 x[0]= z;
1149 i= b->wds= 1;
1150 k+= 32;
1151 }
1152 if (de)
1153 {
1154 *e= de - Bias - (P-1) + k;
1155 *bits= P - k;
1156 }
1157 else
1158 {
1159 *e= de - Bias - (P-1) + 1 + k;
1160 *bits= 32*i - hi0bits(x[i-1]);
1161 }
1162 return b;
1163#undef d0
1164#undef d1
1165}
1166
1167
1168static double ratio(Bigint *a, Bigint *b)
1169{
1170 double da, db;
1171 int k, ka, kb;
1172
1173 dval(da)= b2d(a, &ka);
1174 dval(db)= b2d(b, &kb);
1175 k= ka - kb + 32*(a->wds - b->wds);
1176 if (k > 0)
1177 word0(da)+= k*Exp_msk1;
1178 else
1179 {
1180 k= -k;
1181 word0(db)+= k*Exp_msk1;
1182 }
1183 return dval(da) / dval(db);
1184}
1185
1186static const double tens[] =
1187{
1188 1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9,
1189 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19,
1190 1e20, 1e21, 1e22
1191};
1192
1193static const double bigtens[]= { 1e16, 1e32, 1e64, 1e128, 1e256 };
1194static const double tinytens[]=
1195{ 1e-16, 1e-32, 1e-64, 1e-128,
1196 9007199254740992.*9007199254740992.e-256 /* = 2^106 * 1e-53 */
1197};
1198/*
1199 The factor of 2^53 in tinytens[4] helps us avoid setting the underflow
1200 flag unnecessarily. It leads to a song and dance at the end of strtod.
1201*/
1202#define Scale_Bit 0x10
1203#define n_bigtens 5
1204
1205/*
1206 strtod for IEEE--arithmetic machines.
1207
1208 This strtod returns a nearest machine number to the input decimal
1209 string (or sets errno to EOVERFLOW). Ties are broken by the IEEE round-even
1210 rule.
1211
1212 Inspired loosely by William D. Clinger's paper "How to Read Floating
1213 Point Numbers Accurately" [Proc. ACM SIGPLAN '90, pp. 92-101].
1214
1215 Modifications:
1216
1217 1. We only require IEEE (not IEEE double-extended).
1218 2. We get by with floating-point arithmetic in a case that
1219 Clinger missed -- when we're computing d * 10^n
1220 for a small integer d and the integer n is not too
1221 much larger than 22 (the maximum integer k for which
1222 we can represent 10^k exactly), we may be able to
1223 compute (d*10^k) * 10^(e-k) with just one roundoff.
1224 3. Rather than a bit-at-a-time adjustment of the binary
1225 result in the hard case, we use floating-point
1226 arithmetic to determine the adjustment to within
1227 one bit; only in really hard cases do we need to
1228 compute a second residual.
1229 4. Because of 3., we don't need a large table of powers of 10
1230 for ten-to-e (just some small tables, e.g. of 10^k
1231 for 0 <= k <= 22).
1232*/
1233
1234static double my_strtod_int(const char *s00, char **se, int *error)
1235{
1236 int scale;
1237 int bb2, bb5, bbe, bd2, bd5, bbbits, bs2, c, dsign,
1238 e, e1, esign, i, j, k, nd, nd0, nf, nz, nz0, sign;
1239 const char *s, *s0, *s1, *end = *se;
1240 double aadj, aadj1, adj, rv, rv0;
1241 Long L;
1242 ULong y, z;
1243 Bigint *bb= NULL, *bb1= NULL, *bd= NULL, *bd0= NULL, *bs= NULL, *delta= NULL;
1244#ifdef SET_INEXACT
1245 int inexact, oldinexact;
1246#endif
1247
1248 c= 0;
1249 *error= 0;
1250
1251 sign= nz0= nz= 0;
1252 dval(rv)= 0.;
1253 for (s= s00; s < end; s++)
1254 switch (*s) {
1255 case '-':
1256 sign= 1;
1257 /* fallthrough */
1258 case '+':
1259 s++;
1260 goto break2;
1261 case '\t':
1262 case '\n':
1263 case '\v':
1264 case '\f':
1265 case '\r':
1266 case ' ':
1267 continue;
1268 default:
1269 goto break2;
1270 }
1271 break2:
1272 if (s >= end)
1273 goto ret0;
1274
1275 if (*s == '0')
1276 {
1277 nz0= 1;
1278 while (++s < end && *s == '0') ;
1279 if (s >= end)
1280 goto ret;
1281 }
1282 s0= s;
1283 y= z= 0;
1284 for (nd= nf= 0; s < end && (c= *s) >= '0' && c <= '9'; nd++, s++)
1285 if (nd < 9)
1286 y= 10*y + c - '0';
1287 else if (nd < 16)
1288 z= 10*z + c - '0';
1289 nd0= nd;
1290 if (s < end - 1 && c == '.')
1291 {
1292 c= *++s;
1293 if (!nd)
1294 {
1295 for (; s < end && c == '0'; c= *++s)
1296 nz++;
1297 if (s < end && c > '0' && c <= '9')
1298 {
1299 s0= s;
1300 nf+= nz;
1301 nz= 0;
1302 goto have_dig;
1303 }
1304 goto dig_done;
1305 }
1306 for (; s < end && c >= '0' && c <= '9'; c = *++s)
1307 {
1308 have_dig:
1309 nz++;
1310 if (c-= '0')
1311 {
1312 nf+= nz;
1313 for (i= 1; i < nz; i++)
1314 if (nd++ < 9)
1315 y*= 10;
1316 else if (nd <= DBL_DIG + 1)
1317 z*= 10;
1318 if (nd++ < 9)
1319 y= 10*y + c;
1320 else if (nd <= DBL_DIG + 1)
1321 z= 10*z + c;
1322 nz= 0;
1323 }
1324 }
1325 }
1326 dig_done:
1327 e= 0;
1328 if (s < end && (c == 'e' || c == 'E'))
1329 {
1330 if (!nd && !nz && !nz0)
1331 goto ret0;
1332 s00= s;
1333 esign= 0;
1334 if (++s < end)
1335 switch (c= *s) {
1336 case '-':
1337 esign= 1;
1338 /* fallthrough */
1339 case '+':
1340 c= *++s;
1341 }
1342 if (s < end && c >= '0' && c <= '9')
1343 {
1344 while (s < end && c == '0')
1345 c= *++s;
1346 if (s < end && c > '0' && c <= '9') {
1347 L= c - '0';
1348 s1= s;
1349 while (++s < end && (c= *s) >= '0' && c <= '9')
1350 L= 10*L + c - '0';
1351 if (s - s1 > 8 || L > 19999)
1352 /* Avoid confusion from exponents
1353 * so large that e might overflow.
1354 */
1355 e= 19999; /* safe for 16 bit ints */
1356 else
1357 e= (int)L;
1358 if (esign)
1359 e= -e;
1360 }
1361 else
1362 e= 0;
1363 }
1364 else
1365 s= s00;
1366 }
1367 if (!nd)
1368 {
1369 if (!nz && !nz0)
1370 {
1371 ret0:
1372 s= s00;
1373 sign= 0;
1374 }
1375 goto ret;
1376 }
1377 e1= e -= nf;
1378
1379 /*
1380 Now we have nd0 digits, starting at s0, followed by a
1381 decimal point, followed by nd-nd0 digits. The number we're
1382 after is the integer represented by those digits times
1383 10**e
1384 */
1385
1386 if (!nd0)
1387 nd0= nd;
1388 k= nd < DBL_DIG + 1 ? nd : DBL_DIG + 1;
1389 dval(rv)= y;
1390 if (k > 9)
1391 {
1392#ifdef SET_INEXACT
1393 if (k > DBL_DIG)
1394 oldinexact = get_inexact();
1395#endif
1396 dval(rv)= tens[k - 9] * dval(rv) + z;
1397 }
1398 bd0= 0;
1399 if (nd <= DBL_DIG
1400 )
1401 {
1402 if (!e)
1403 goto ret;
1404 if (e > 0)
1405 {
1406 if (e <= Ten_pmax)
1407 {
1408 /* rv = */ rounded_product(dval(rv), tens[e]);
1409 goto ret;
1410 }
1411 i= DBL_DIG - nd;
1412 if (e <= Ten_pmax + i)
1413 {
1414 /*
1415 A fancier test would sometimes let us do
1416 this for larger i values.
1417 */
1418 e-= i;
1419 dval(rv)*= tens[i];
1420 /* rv = */ rounded_product(dval(rv), tens[e]);
1421 goto ret;
1422 }
1423 }
1424#ifndef Inaccurate_Divide
1425 else if (e >= -Ten_pmax)
1426 {
1427 /* rv = */ rounded_quotient(dval(rv), tens[-e]);
1428 goto ret;
1429 }
1430#endif
1431 }
1432 e1+= nd - k;
1433
1434#ifdef SET_INEXACT
1435 inexact= 1;
1436 if (k <= DBL_DIG)
1437 oldinexact= get_inexact();
1438#endif
1439 scale= 0;
1440
1441 /* Get starting approximation = rv * 10**e1 */
1442
1443 if (e1 > 0)
1444 {
1445 if ((i= e1 & 15))
1446 dval(rv)*= tens[i];
1447 if (e1&= ~15)
1448 {
1449 if (e1 > DBL_MAX_10_EXP)
1450 {
1451 ovfl:
1452 *error= EOVERFLOW;
1453 /* Can't trust HUGE_VAL */
1454 word0(rv)= Exp_mask;
1455 word1(rv)= 0;
1456#ifdef SET_INEXACT
1457 /* set overflow bit */
1458 dval(rv0)= 1e300;
1459 dval(rv0)*= dval(rv0);
1460#endif
1461 if (bd0)
1462 goto retfree;
1463 goto ret;
1464 }
1465 e1>>= 4;
1466 for(j= 0; e1 > 1; j++, e1>>= 1)
1467 if (e1 & 1)
1468 dval(rv)*= bigtens[j];
1469 /* The last multiplication could overflow. */
1470 word0(rv)-= P*Exp_msk1;
1471 dval(rv)*= bigtens[j];
1472 if ((z= word0(rv) & Exp_mask) > Exp_msk1 * (DBL_MAX_EXP + Bias - P))
1473 goto ovfl;
1474 if (z > Exp_msk1 * (DBL_MAX_EXP + Bias - 1 - P))
1475 {
1476 /* set to largest number (Can't trust DBL_MAX) */
1477 word0(rv)= Big0;
1478 word1(rv)= Big1;
1479 }
1480 else
1481 word0(rv)+= P*Exp_msk1;
1482 }
1483 }
1484 else if (e1 < 0)
1485 {
1486 e1= -e1;
1487 if ((i= e1 & 15))
1488 dval(rv)/= tens[i];
1489 if ((e1>>= 4))
1490 {
1491 if (e1 >= 1 << n_bigtens)
1492 goto undfl;
1493 if (e1 & Scale_Bit)
1494 scale= 2 * P;
1495 for(j= 0; e1 > 0; j++, e1>>= 1)
1496 if (e1 & 1)
1497 dval(rv)*= tinytens[j];
1498 if (scale && (j = 2 * P + 1 - ((word0(rv) & Exp_mask) >> Exp_shift)) > 0)
1499 {
1500 /* scaled rv is denormal; zap j low bits */
1501 if (j >= 32)
1502 {
1503 word1(rv)= 0;
1504 if (j >= 53)
1505 word0(rv)= (P + 2) * Exp_msk1;
1506 else
1507 word0(rv)&= 0xffffffff << (j - 32);
1508 }
1509 else
1510 word1(rv)&= 0xffffffff << j;
1511 }
1512 if (compare_double(dval(rv), 0))
1513 {
1514 undfl:
1515 dval(rv)= 0.;
1516 if (bd0)
1517 goto retfree;
1518 goto ret;
1519 }
1520 }
1521 }
1522
1523 /* Now the hard part -- adjusting rv to the correct value.*/
1524
1525 /* Put digits into bd: true value = bd * 10^e */
1526
1527 bd0= s2b(s0, nd0, nd, y);
1528
1529 for(;;)
1530 {
1531 bd= Balloc(bd0->k);
1532 Bcopy(bd, bd0);
1533 bb= d2b(dval(rv), &bbe, &bbbits); /* rv = bb * 2^bbe */
1534 bs= i2b(1);
1535
1536 if (e >= 0)
1537 {
1538 bb2= bb5= 0;
1539 bd2= bd5= e;
1540 }
1541 else
1542 {
1543 bb2= bb5= -e;
1544 bd2= bd5= 0;
1545 }
1546 if (bbe >= 0)
1547 bb2+= bbe;
1548 else
1549 bd2-= bbe;
1550 bs2= bb2;
1551 j= bbe - scale;
1552 i= j + bbbits - 1; /* logb(rv) */
1553 if (i < Emin) /* denormal */
1554 j+= P - Emin;
1555 else
1556 j= P + 1 - bbbits;
1557 bb2+= j;
1558 bd2+= j;
1559 bd2+= scale;
1560 i= bb2 < bd2 ? bb2 : bd2;
1561 if (i > bs2)
1562 i= bs2;
1563 if (i > 0)
1564 {
1565 bb2-= i;
1566 bd2-= i;
1567 bs2-= i;
1568 }
1569 if (bb5 > 0)
1570 {
1571 bs= pow5mult(bs, bb5);
1572 bb1= mult(bs, bb);
1573 Bfree(bb);
1574 bb= bb1;
1575 }
1576 if (bb2 > 0)
1577 bb= lshift(bb, bb2);
1578 if (bd5 > 0)
1579 bd= pow5mult(bd, bd5);
1580 if (bd2 > 0)
1581 bd= lshift(bd, bd2);
1582 if (bs2 > 0)
1583 bs= lshift(bs, bs2);
1584 delta= diff(bb, bd);
1585 dsign= delta->sign;
1586 delta->sign= 0;
1587 i= cmp(delta, bs);
1588
1589 if (i < 0)
1590 {
1591 /*
1592 Error is less than half an ulp -- check for special case of mantissa
1593 a power of two.
1594 */
1595 if (dsign || word1(rv) || word0(rv) & Bndry_mask ||
1596 (word0(rv) & Exp_mask) <= (2 * P + 1) * Exp_msk1)
1597 {
1598#ifdef SET_INEXACT
1599 if (!delta->x[0] && delta->wds <= 1)
1600 inexact= 0;
1601#endif
1602 break;
1603 }
1604 if (!delta->p.x[0] && delta->wds <= 1)
1605 {
1606 /* exact result */
1607#ifdef SET_INEXACT
1608 inexact= 0;
1609#endif
1610 break;
1611 }
1612 delta= lshift(delta, Log2P);
1613 if (cmp(delta, bs) > 0)
1614 goto drop_down;
1615 break;
1616 }
1617 if (i == 0)
1618 {
1619 /* exactly half-way between */
1620 if (dsign)
1621 {
1622 if ((word0(rv) & Bndry_mask1) == Bndry_mask1 &&
1623 word1(rv) ==
1624 ((scale && (y = word0(rv) & Exp_mask) <= 2 * P * Exp_msk1) ?
1625 (0xffffffff & (0xffffffff << (2*P+1-(y>>Exp_shift)))) :
1626 0xffffffff))
1627 {
1628 /*boundary case -- increment exponent*/
1629 word0(rv)= (word0(rv) & Exp_mask) + Exp_msk1;
1630 word1(rv) = 0;
1631 dsign = 0;
1632 break;
1633 }
1634 }
1635 else if (!(word0(rv) & Bndry_mask) && !word1(rv))
1636 {
1637 drop_down:
1638 /* boundary case -- decrement exponent */
1639 if (scale)
1640 {
1641 L= word0(rv) & Exp_mask;
1642 if (L <= (2 *P + 1) * Exp_msk1)
1643 {
1644 if (L > (P + 2) * Exp_msk1)
1645 /* round even ==> accept rv */
1646 break;
1647 /* rv = smallest denormal */
1648 goto undfl;
1649 }
1650 }
1651 L= (word0(rv) & Exp_mask) - Exp_msk1;
1652 word0(rv)= L | Bndry_mask1;
1653 word1(rv)= 0xffffffff;
1654 break;
1655 }
1656 if (!(word1(rv) & LSB))
1657 break;
1658 if (dsign)
1659 dval(rv)+= ulp(dval(rv));
1660 else
1661 {
1662 dval(rv)-= ulp(dval(rv));
1663 if (!dval(rv))
1664 goto undfl;
1665 }
1666 dsign= 1 - dsign;
1667 break;
1668 }
1669 if ((aadj= ratio(delta, bs)) <= 2.)
1670 {
1671 if (dsign)
1672 aadj= aadj1= 1.;
1673 else if (word1(rv) || word0(rv) & Bndry_mask)
1674 {
1675 if (word1(rv) == Tiny1 && !word0(rv))
1676 goto undfl;
1677 aadj= 1.;
1678 aadj1= -1.;
1679 }
1680 else
1681 {
1682 /* special case -- power of FLT_RADIX to be rounded down... */
1683 if (aadj < 2. / FLT_RADIX)
1684 aadj= 1. / FLT_RADIX;
1685 else
1686 aadj*= 0.5;
1687 aadj1= -aadj;
1688 }
1689 }
1690 else
1691 {
1692 aadj*= 0.5;
1693 aadj1= dsign ? aadj : -aadj;
1694 if (Flt_Rounds == 0)
1695 aadj1+= 0.5;
1696 }
1697 y= word0(rv) & Exp_mask;
1698
1699 /* Check for overflow */
1700
1701 if (y == Exp_msk1 * (DBL_MAX_EXP + Bias - 1))
1702 {
1703 dval(rv0)= dval(rv);
1704 word0(rv)-= P * Exp_msk1;
1705 adj= aadj1 * ulp(dval(rv));
1706 dval(rv)+= adj;
1707 if ((word0(rv) & Exp_mask) >= Exp_msk1 * (DBL_MAX_EXP + Bias - P))
1708 {
1709 if (word0(rv0) == Big0 && word1(rv0) == Big1)
1710 goto ovfl;
1711 word0(rv)= Big0;
1712 word1(rv)= Big1;
1713 goto cont;
1714 }
1715 else
1716 word0(rv)+= P * Exp_msk1;
1717 }
1718 else
1719 {
1720 if (scale && y <= 2 * P * Exp_msk1)
1721 {
1722 if (aadj <= 0x7fffffff)
1723 {
1724 if ((z= (ULong) aadj) <= 0)
1725 z= 1;
1726 aadj= z;
1727 aadj1= dsign ? aadj : -aadj;
1728 }
1729 word0(aadj1)+= (2 * P + 1) * Exp_msk1 - y;
1730 }
1731 adj = aadj1 * ulp(dval(rv));
1732 dval(rv) += adj;
1733 }
1734 z= word0(rv) & Exp_mask;
1735#ifndef SET_INEXACT
1736 if (!scale)
1737 if (y == z)
1738 {
1739 /* Can we stop now? */
1740 L= (Long)aadj;
1741 aadj-= L;
1742 /* The tolerances below are conservative. */
1743 if (dsign || word1(rv) || word0(rv) & Bndry_mask)
1744 {
1745 if (aadj < .4999999 || aadj > .5000001)
1746 break;
1747 }
1748 else if (aadj < .4999999 / FLT_RADIX)
1749 break;
1750 }
1751#endif
1752 cont:
1753 Bfree(bb);
1754 Bfree(bd);
1755 Bfree(bs);
1756 Bfree(delta);
1757 }
1758#ifdef SET_INEXACT
1759 if (inexact)
1760 {
1761 if (!oldinexact)
1762 {
1763 word0(rv0)= Exp_1 + (70 << Exp_shift);
1764 word1(rv0)= 0;
1765 dval(rv0)+= 1.;
1766 }
1767 }
1768 else if (!oldinexact)
1769 clear_inexact();
1770#endif
1771 if (scale)
1772 {
1773 word0(rv0)= Exp_1 - 2 * P * Exp_msk1;
1774 word1(rv0)= 0;
1775 dval(rv)*= dval(rv0);
1776 }
1777#ifdef SET_INEXACT
1778 if (inexact && !(word0(rv) & Exp_mask))
1779 {
1780 /* set underflow bit */
1781 dval(rv0)= 1e-300;
1782 dval(rv0)*= dval(rv0);
1783 }
1784#endif
1785 retfree:
1786 Bfree(bb);
1787 Bfree(bd);
1788 Bfree(bs);
1789 Bfree(bd0);
1790 Bfree(delta);
1791 ret:
1792 *se= (char *)s;
1793 return sign ? -dval(rv) : dval(rv);
1794}
1795
1796
1797static int quorem(Bigint *b, Bigint *S)
1798{
1799 int n;
1800 ULong *bx, *bxe, q, *sx, *sxe;
1801 ULLong borrow, carry, y, ys;
1802
1803 n= S->wds;
1804 if (b->wds < n)
1805 return 0;
1806 sx= S->p.x;
1807 sxe= sx + --n;
1808 bx= b->p.x;
1809 bxe= bx + n;
1810 q= *bxe / (*sxe + 1); /* ensure q <= true quotient */
1811 if (q)
1812 {
1813 borrow= 0;
1814 carry= 0;
1815 do
1816 {
1817 ys= *sx++ * (ULLong)q + carry;
1818 carry= ys >> 32;
1819 y= *bx - (ys & FFFFFFFF) - borrow;
1820 borrow= y >> 32 & (ULong)1;
1821 *bx++= (ULong) (y & FFFFFFFF);
1822 }
1823 while (sx <= sxe);
1824 if (!*bxe)
1825 {
1826 bx= b->p.x;
1827 while (--bxe > bx && !*bxe)
1828 --n;
1829 b->wds= n;
1830 }
1831 }
1832 if (cmp(b, S) >= 0)
1833 {
1834 q++;
1835 borrow= 0;
1836 carry= 0;
1837 bx= b->p.x;
1838 sx= S->p.x;
1839 do
1840 {
1841 ys= *sx++ + carry;
1842 carry= ys >> 32;
1843 y= *bx - (ys & FFFFFFFF) - borrow;
1844 borrow= y >> 32 & (ULong)1;
1845 *bx++= (ULong) (y & FFFFFFFF);
1846 }
1847 while (sx <= sxe);
1848 bx= b->p.x;
1849 bxe= bx + n;
1850 if (!*bxe)
1851 {
1852 while (--bxe > bx && !*bxe)
1853 --n;
1854 b->wds= n;
1855 }
1856 }
1857 return q;
1858}
1859
1860
1861/*
1862 dtoa for IEEE arithmetic (dmg): convert double to ASCII string.
1863
1864 Inspired by "How to Print Floating-Point Numbers Accurately" by
1865 Guy L. Steele, Jr. and Jon L. White [Proc. ACM SIGPLAN '90, pp. 112-126].
1866
1867 Modifications:
1868 1. Rather than iterating, we use a simple numeric overestimate
1869 to determine k= floor(log10(d)). We scale relevant
1870 quantities using O(log2(k)) rather than O(k) multiplications.
1871 2. For some modes > 2 (corresponding to ecvt and fcvt), we don't
1872 try to generate digits strictly left to right. Instead, we
1873 compute with fewer bits and propagate the carry if necessary
1874 when rounding the final digit up. This is often faster.
1875 3. Under the assumption that input will be rounded nearest,
1876 mode 0 renders 1e23 as 1e23 rather than 9.999999999999999e22.
1877 That is, we allow equality in stopping tests when the
1878 round-nearest rule will give the same floating-point value
1879 as would satisfaction of the stopping test with strict
1880 inequality.
1881 4. We remove common factors of powers of 2 from relevant
1882 quantities.
1883 5. When converting floating-point integers less than 1e16,
1884 we use floating-point arithmetic rather than resorting
1885 to multiple-precision integers.
1886 6. When asked to produce fewer than 15 digits, we first try
1887 to get by with floating-point arithmetic; we resort to
1888 multiple-precision integer arithmetic only if we cannot
1889 guarantee that the floating-point calculation has given
1890 the correctly rounded result. For k requested digits and
1891 "uniformly" distributed input, the probability is
1892 something like 10^(k-15) that we must resort to the Long
1893 calculation.
1894 */
1895
1896static char *dtoa(double d, int mode, int ndigits, int *decpt, int *sign,
1897 char **rve)
1898{
1899 /*
1900 Arguments ndigits, decpt, sign are similar to those
1901 of ecvt and fcvt; trailing zeros are suppressed from
1902 the returned string. If not null, *rve is set to point
1903 to the end of the return value. If d is +-Infinity or NaN,
1904 then *decpt is set to DTOA_OVERFLOW.
1905
1906 mode:
1907 0 ==> shortest string that yields d when read in
1908 and rounded to nearest.
1909
1910 1 ==> like 0, but with Steele & White stopping rule;
1911 e.g. with IEEE P754 arithmetic , mode 0 gives
1912 1e23 whereas mode 1 gives 9.999999999999999e22.
1913 2 ==> cmax(1,ndigits) significant digits. This gives a
1914 return value similar to that of ecvt, except
1915 that trailing zeros are suppressed.
1916 3 ==> through ndigits past the decimal point. This
1917 gives a return value similar to that from fcvt,
1918 except that trailing zeros are suppressed, and
1919 ndigits can be negative.
1920 4,5 ==> similar to 2 and 3, respectively, but (in
1921 round-nearest mode) with the tests of mode 0 to
1922 possibly return a shorter string that rounds to d.
1923 6-9 ==> Debugging modes similar to mode - 4: don't try
1924 fast floating-point estimate (if applicable).
1925
1926 Values of mode other than 0-9 are treated as mode 0.
1927
1928 Sufficient space is allocated to the return value
1929 to hold the suppressed trailing zeros.
1930 */
1931
1932 int bbits, b2, b5, be, dig, i, ieps, ilim=0, ilim0, ilim1= 0,
1933 j, j1, k, k0, k_check, leftright, m2, m5, s2, s5,
1934 spec_case, try_quick;
1935 Long L;
1936 int denorm;
1937 ULong x;
1938 Bigint *b, *b1, *delta, *mlo = NULL, *mhi, *S;
1939 double d2, ds, eps;
1940 char *s, *s0;
1941
1942 if (word0(d) & Sign_bit)
1943 {
1944 /* set sign for everything, including 0's and NaNs */
1945 *sign= 1;
1946 word0(d) &= ~Sign_bit; /* clear sign bit */
1947 }
1948 else
1949 *sign= 0;
1950
1951 /* If infinity, set decpt to DTOA_OVERFLOW, if 0 set it to 1 */
1952 if ((((word0(d) & Exp_mask) == Exp_mask) && ((*decpt= DTOA_OVERFLOW) != 0)) ||
1953 (!dval(d) && ((*decpt= 1) != 0)))
1954 {
1955 /* Infinity, NaN, 0 */
1956 char *res= (char*) malloc(2);
1957 res[0]= '0';
1958 res[1]= '\0';
1959 if (rve)
1960 *rve= res + 1;
1961 return res;
1962 }
1963
1964
1965 b= d2b(dval(d), &be, &bbits);
1966 if ((i= (int)(word0(d) >> Exp_shift1 & (Exp_mask>>Exp_shift1))))
1967 {
1968 dval(d2)= dval(d);
1969 word0(d2) &= Frac_mask1;
1970 word0(d2) |= Exp_11;
1971
1972 /*
1973 log(x) ~=~ log(1.5) + (x-1.5)/1.5
1974 log10(x) = log(x) / log(10)
1975 ~=~ log(1.5)/log(10) + (x-1.5)/(1.5*log(10))
1976 log10(d)= (i-Bias)*log(2)/log(10) + log10(d2)
1977
1978 This suggests computing an approximation k to log10(d) by
1979
1980 k= (i - Bias)*0.301029995663981
1981 + ( (d2-1.5)*0.289529654602168 + 0.176091259055681 );
1982
1983 We want k to be too large rather than too small.
1984 The error in the first-order Taylor series approximation
1985 is in our favor, so we just round up the constant enough
1986 to compensate for any error in the multiplication of
1987 (i - Bias) by 0.301029995663981; since |i - Bias| <= 1077,
1988 and 1077 * 0.30103 * 2^-52 ~=~ 7.2e-14,
1989 adding 1e-13 to the constant term more than suffices.
1990 Hence we adjust the constant term to 0.1760912590558.
1991 (We could get a more accurate k by invoking log10,
1992 but this is probably not worthwhile.)
1993 */
1994
1995 i-= Bias;
1996 denorm= 0;
1997 }
1998 else
1999 {
2000 /* d is denormalized */
2001
2002 i= bbits + be + (Bias + (P-1) - 1);
2003 x= i > 32 ? word0(d) << (64 - i) | word1(d) >> (i - 32)
2004 : word1(d) << (32 - i);
2005 dval(d2)= x;
2006 word0(d2)-= 31*Exp_msk1; /* adjust exponent */
2007 i-= (Bias + (P-1) - 1) + 1;
2008 denorm= 1;
2009 }
2010 ds= (dval(d2)-1.5)*0.289529654602168 + 0.1760912590558 + i*0.301029995663981;
2011 k= (int)ds;
2012 if (ds < 0. && ds != k)
2013 k--; /* want k= floor(ds) */
2014 k_check= 1;
2015 if (k >= 0 && k <= Ten_pmax)
2016 {
2017 if (dval(d) < tens[k])
2018 k--;
2019 k_check= 0;
2020 }
2021 j= bbits - i - 1;
2022 if (j >= 0)
2023 {
2024 b2= 0;
2025 s2= j;
2026 }
2027 else
2028 {
2029 b2= -j;
2030 s2= 0;
2031 }
2032 if (k >= 0)
2033 {
2034 b5= 0;
2035 s5= k;
2036 s2+= k;
2037 }
2038 else
2039 {
2040 b2-= k;
2041 b5= -k;
2042 s5= 0;
2043 }
2044 if (mode < 0 || mode > 9)
2045 mode= 0;
2046
2047 try_quick= 1;
2048
2049 if (mode > 5)
2050 {
2051 mode-= 4;
2052 try_quick= 0;
2053 }
2054 leftright= 1;
2055 switch (mode) {
2056 case 0:
2057 case 1:
2058 ilim= ilim1= -1;
2059 i= 18;
2060 ndigits= 0;
2061 break;
2062 case 2:
2063 leftright= 0;
2064 /* fallthrough */
2065 case 4:
2066 if (ndigits <= 0)
2067 ndigits= 1;
2068 ilim= ilim1= i= ndigits;
2069 break;
2070 case 3:
2071 leftright= 0;
2072 /* fallthrough */
2073 case 5:
2074 i= ndigits + k + 1;
2075 ilim= i;
2076 ilim1= i - 1;
2077 if (i <= 0)
2078 i= 1;
2079 }
2080 s= s0= (char*)malloc(i+1); /* +1 for trailing '\0' appended
2081 at end of function */
2082
2083 if (ilim >= 0 && ilim <= Quick_max && try_quick)
2084 {
2085 /* Try to get by with floating-point arithmetic. */
2086 i= 0;
2087 dval(d2)= dval(d);
2088 k0= k;
2089 ilim0= ilim;
2090 ieps= 2; /* conservative */
2091 if (k > 0)
2092 {
2093 ds= tens[k&0xf];
2094 j= k >> 4;
2095 if (j & Bletch)
2096 {
2097 /* prevent overflows */
2098 j&= Bletch - 1;
2099 dval(d)/= bigtens[n_bigtens-1];
2100 ieps++;
2101 }
2102 for (; j; j>>= 1, i++)
2103 {
2104 if (j & 1)
2105 {
2106 ieps++;
2107 ds*= bigtens[i];
2108 }
2109 }
2110 dval(d)/= ds;
2111 }
2112 else if ((j1= -k))
2113 {
2114 dval(d)*= tens[j1 & 0xf];
2115 for (j= j1 >> 4; j; j>>= 1, i++)
2116 {
2117 if (j & 1)
2118 {
2119 ieps++;
2120 dval(d)*= bigtens[i];
2121 }
2122 }
2123 }
2124 if (k_check && dval(d) < 1. && ilim > 0)
2125 {
2126 if (ilim1 <= 0)
2127 goto fast_failed;
2128 ilim= ilim1;
2129 k--;
2130 dval(d)*= 10.;
2131 ieps++;
2132 }
2133 dval(eps)= ieps*dval(d) + 7.;
2134 word0(eps)-= (P-1)*Exp_msk1;
2135 if (ilim == 0)
2136 {
2137 S= mhi= 0;
2138 dval(d)-= 5.;
2139 if (dval(d) > dval(eps))
2140 goto one_digit;
2141 if (dval(d) < -dval(eps))
2142 goto no_digits;
2143 goto fast_failed;
2144 }
2145 if (leftright)
2146 {
2147 /* Use Steele & White method of only generating digits needed. */
2148 dval(eps)= 0.5/tens[ilim-1] - dval(eps);
2149 for (i= 0;;)
2150 {
2151 L= (Long) dval(d);
2152 dval(d)-= L;
2153 *s++= '0' + (int)L;
2154 if (dval(d) < dval(eps))
2155 goto ret1;
2156 if (1. - dval(d) < dval(eps))
2157 goto bump_up;
2158 if (++i >= ilim)
2159 break;
2160 dval(eps)*= 10.;
2161 dval(d)*= 10.;
2162 }
2163 }
2164 else
2165 {
2166 /* Generate ilim digits, then fix them up. */
2167 dval(eps)*= tens[ilim-1];
2168 for (i= 1;; i++, dval(d)*= 10.)
2169 {
2170 L= (Long)(dval(d));
2171 if (!(dval(d)-= L))
2172 ilim= i;
2173 *s++= '0' + (int)L;
2174 if (i == ilim)
2175 {
2176 if (dval(d) > 0.5 + dval(eps))
2177 goto bump_up;
2178 else if (dval(d) < 0.5 - dval(eps))
2179 {
2180 while (*--s == '0') {}
2181 s++;
2182 goto ret1;
2183 }
2184 break;
2185 }
2186 }
2187 }
2188 fast_failed:
2189 s= s0;
2190 dval(d)= dval(d2);
2191 k= k0;
2192 ilim= ilim0;
2193 }
2194
2195 /* Do we have a "small" integer? */
2196
2197 if (be >= 0 && k <= Int_max)
2198 {
2199 /* Yes. */
2200 ds= tens[k];
2201 if (ndigits < 0 && ilim <= 0)
2202 {
2203 S= mhi= 0;
2204 if (ilim < 0 || dval(d) <= 5*ds)
2205 goto no_digits;
2206 goto one_digit;
2207 }
2208 for (i= 1;; i++, dval(d)*= 10.)
2209 {
2210 L= (Long)(dval(d) / ds);
2211 dval(d)-= L*ds;
2212 *s++= '0' + (int)L;
2213 if (!dval(d))
2214 {
2215 break;
2216 }
2217 if (i == ilim)
2218 {
2219 dval(d)+= dval(d);
2220 if (dval(d) > ds || (dval(d) == ds && L & 1))
2221 {
2222bump_up:
2223 while (*--s == '9')
2224 if (s == s0)
2225 {
2226 k++;
2227 *s= '0';
2228 break;
2229 }
2230 ++*s++;
2231 }
2232 break;
2233 }
2234 }
2235 goto ret1;
2236 }
2237
2238 m2= b2;
2239 m5= b5;
2240 mhi= mlo= 0;
2241 if (leftright)
2242 {
2243 i = denorm ? be + (Bias + (P-1) - 1 + 1) : 1 + P - bbits;
2244 b2+= i;
2245 s2+= i;
2246 mhi= i2b(1);
2247 }
2248 if (m2 > 0 && s2 > 0)
2249 {
2250 i= m2 < s2 ? m2 : s2;
2251 b2-= i;
2252 m2-= i;
2253 s2-= i;
2254 }
2255 if (b5 > 0)
2256 {
2257 if (leftright)
2258 {
2259 if (m5 > 0)
2260 {
2261 mhi= pow5mult(mhi, m5);
2262 b1= mult(mhi, b);
2263 Bfree(b);
2264 b= b1;
2265 }
2266 if ((j= b5 - m5))
2267 b= pow5mult(b, j);
2268 }
2269 else
2270 b= pow5mult(b, b5);
2271 }
2272 S= i2b(1);
2273 if (s5 > 0)
2274 S= pow5mult(S, s5);
2275
2276 /* Check for special case that d is a normalized power of 2. */
2277
2278 spec_case= 0;
2279 if ((mode < 2 || leftright)
2280 )
2281 {
2282 if (!word1(d) && !(word0(d) & Bndry_mask) &&
2283 word0(d) & (Exp_mask & ~Exp_msk1)
2284 )
2285 {
2286 /* The special case */
2287 b2+= Log2P;
2288 s2+= Log2P;
2289 spec_case= 1;
2290 }
2291 }
2292
2293 /*
2294 Arrange for convenient computation of quotients:
2295 shift left if necessary so divisor has 4 leading 0 bits.
2296
2297 Perhaps we should just compute leading 28 bits of S once
2298 a nd for all and pass them and a shift to quorem, so it
2299 can do shifts and ors to compute the numerator for q.
2300 */
2301 if ((i= ((s5 ? 32 - hi0bits(S->p.x[S->wds-1]) : 1) + s2) & 0x1f))
2302 i= 32 - i;
2303 if (i > 4)
2304 {
2305 i-= 4;
2306 b2+= i;
2307 m2+= i;
2308 s2+= i;
2309 }
2310 else if (i < 4)
2311 {
2312 i+= 28;
2313 b2+= i;
2314 m2+= i;
2315 s2+= i;
2316 }
2317 if (b2 > 0)
2318 b= lshift(b, b2);
2319 if (s2 > 0)
2320 S= lshift(S, s2);
2321 if (k_check)
2322 {
2323 if (cmp(b,S) < 0)
2324 {
2325 k--;
2326 /* we botched the k estimate */
2327 b= multadd(b, 10, 0);
2328 if (leftright)
2329 mhi= multadd(mhi, 10, 0);
2330 ilim= ilim1;
2331 }
2332 }
2333 if (ilim <= 0 && (mode == 3 || mode == 5))
2334 {
2335 if (ilim < 0 || cmp(b,S= multadd(S,5,0)) <= 0)
2336 {
2337 /* no digits, fcvt style */
2338no_digits:
2339 k= -1 - ndigits;
2340 goto ret;
2341 }
2342one_digit:
2343 *s++= '1';
2344 k++;
2345 goto ret;
2346 }
2347 if (leftright)
2348 {
2349 if (m2 > 0)
2350 mhi= lshift(mhi, m2);
2351
2352 /*
2353 Compute mlo -- check for special case that d is a normalized power of 2.
2354 */
2355
2356 mlo= mhi;
2357 if (spec_case)
2358 {
2359 mhi= Balloc(mhi->k);
2360 Bcopy(mhi, mlo);
2361 mhi= lshift(mhi, Log2P);
2362 }
2363
2364 for (i= 1;;i++)
2365 {
2366 dig= quorem(b,S) + '0';
2367 /* Do we yet have the shortest decimal string that will round to d? */
2368 j= cmp(b, mlo);
2369 delta= diff(S, mhi);
2370 j1= delta->sign ? 1 : cmp(b, delta);
2371 Bfree(delta);
2372 if (j1 == 0 && mode != 1 && !(word1(d) & 1)
2373 )
2374 {
2375 if (dig == '9')
2376 goto round_9_up;
2377 if (j > 0)
2378 dig++;
2379 *s++= dig;
2380 goto ret;
2381 }
2382 if (j < 0 || (j == 0 && mode != 1 && !(word1(d) & 1)))
2383 {
2384 if (!b->p.x[0] && b->wds <= 1)
2385 {
2386 goto accept_dig;
2387 }
2388 if (j1 > 0)
2389 {
2390 b= lshift(b, 1);
2391 j1= cmp(b, S);
2392 if ((j1 > 0 || (j1 == 0 && dig & 1))
2393 && dig++ == '9')
2394 goto round_9_up;
2395 }
2396accept_dig:
2397 *s++= dig;
2398 goto ret;
2399 }
2400 if (j1 > 0)
2401 {
2402 if (dig == '9')
2403 { /* possible if i == 1 */
2404round_9_up:
2405 *s++= '9';
2406 goto roundoff;
2407 }
2408 *s++= dig + 1;
2409 goto ret;
2410 }
2411 *s++= dig;
2412 if (i == ilim)
2413 break;
2414 b= multadd(b, 10, 0);
2415 if (mlo == mhi)
2416 mlo= mhi= multadd(mhi, 10, 0);
2417 else
2418 {
2419 mlo= multadd(mlo, 10, 0);
2420 mhi= multadd(mhi, 10, 0);
2421 }
2422 }
2423 }
2424 else
2425 for (i= 1;; i++)
2426 {
2427 *s++= dig= quorem(b,S) + '0';
2428 if (!b->p.x[0] && b->wds <= 1)
2429 {
2430 goto ret;
2431 }
2432 if (i >= ilim)
2433 break;
2434 b= multadd(b, 10, 0);
2435 }
2436
2437 /* Round off last digit */
2438
2439 b= lshift(b, 1);
2440 j= cmp(b, S);
2441 if (j > 0 || (j == 0 && dig & 1))
2442 {
2443roundoff:
2444 while (*--s == '9')
2445 if (s == s0)
2446 {
2447 k++;
2448 *s++= '1';
2449 goto ret;
2450 }
2451 ++*s++;
2452 }
2453 else
2454 {
2455 while (*--s == '0') {}
2456 s++;
2457 }
2458ret:
2459 Bfree(S);
2460 if (mhi)
2461 {
2462 if (mlo && mlo != mhi)
2463 Bfree(mlo);
2464 Bfree(mhi);
2465 }
2466ret1:
2467 Bfree(b);
2468 *s= 0;
2469 *decpt= k + 1;
2470 if (rve)
2471 *rve= s;
2472 return s0;
2473}
2474
2475} /* namespace internal */
2476} /* namespace drizzled */
TODO: Rename this file - func.h is stupid.
STL namespace.