dtoa.cc File Reference

#include "my_config.h"
#include <assert.h>
#include <algorithm>
#include <limits>
#include "decimal.h"
#include "my_inttypes.h"
#include "my_pointer_arithmetic.h"
#include <errno.h>
#include <float.h>
#include <stdlib.h>
#include <string.h>
#include "m_string.h"

Classes
union	U
struct	Bigint
struct	Stack_alloc

Macros
#define	EOVERFLOW   84
#define	DTOA_BUFF_SIZE   (460 * sizeof(void *))
	Appears to suffice to not call malloc() in most cases. More...
#define	DTOA_OVERFLOW   9999
#define	word0(x)   (x)->L[1]
#define	word1(x)   (x)->L[0]
#define	dval(x)   (x)->d
#define	Exp_shift   20
#define	Exp_shift1   20
#define	Exp_msk1   0x100000
#define	Exp_mask   0x7ff00000
#define	P   53
#define	Bias   1023
#define	Emin   (-1022)
#define	Exp_1   0x3ff00000
#define	Exp_11   0x3ff00000
#define	Ebits   11
#define	Frac_mask   0xfffff
#define	Frac_mask1   0xfffff
#define	Ten_pmax   22
#define	Bletch   0x10
#define	Bndry_mask   0xfffff
#define	Bndry_mask1   0xfffff
#define	LSB   1
#define	Sign_bit   0x80000000
#define	Log2P   1
#define	Tiny1   1
#define	Quick_max   14
#define	Int_max   14
#define	Flt_Rounds   1
#define	rounded_product(a, b)   a *= b
#define	rounded_quotient(a, b)   a /= b
#define	Big0   (Frac_mask1 | Exp_msk1 * (DBL_MAX_EXP + Bias - 1))
#define	Big1   0xffffffff
#define	FFFFFFFF   0xffffffffUL
#define	Kmax   15
#define	Bcopy(x, y)
#define	P5A_MAX   (sizeof(p5_a) / sizeof(*p5_a) - 1)
#define	d0   word0(&d)
#define	d1   word1(&d)
#define	d0   word0(d)
#define	d1   word1(d)
#define	Scale_Bit   0x10
#define	n_bigtens   5

Typedefs
typedef int32	Long
typedef uint32	ULong
typedef int64	LLong
typedef uint64	ULLong
typedef struct Bigint	Bigint
typedef struct Stack_alloc	Stack_alloc

Functions
static double	my_strtod_int (const char *, const char **, int *, char *, size_t)
static char *	dtoa (double, int, int, int *, int *, char **, char *, size_t)
static void	dtoa_free (char *, char *, size_t)
static size_t	my_fcvt_internal (double x, int precision, bool shorten, char *to, bool *error)
	Converts a given floating point number to a zero-terminated string representation using the 'f' format. More...
size_t	my_fcvt (double x, int precision, char *to, bool *error)
	Converts a given floating point number to a zero-terminated string representation using the 'f' format. More...
size_t	my_fcvt_compact (double x, char *to, bool *error)
	Converts a given floating point number to a zero-terminated string representation using the 'f' format. More...
size_t	my_gcvt (double x, my_gcvt_arg_type type, int width, char *to, bool *error)
	Converts a given floating point number to a zero-terminated string representation with a given field width using the 'e' format (aka scientific notation) or the 'f' one. More...
double	my_strtod (const char *str, const char **end, int *error)
	Converts string to double (string does not have to be zero-terminated) More...
static Bigint *	Balloc (int k, Stack_alloc *alloc)
static void	Bfree (Bigint *v, Stack_alloc *alloc)
static char *	dtoa_alloc (int i, Stack_alloc *alloc)
static Bigint *	multadd (Bigint *b, int m, int a, Stack_alloc *alloc)
static Bigint *	s2b (const char *s, int nd0, int nd, ULong y9, Stack_alloc *alloc)
	Converts a string to Bigint. More...
static int	hi0bits (ULong x)
static int	lo0bits (ULong *y)
static Bigint *	i2b (int i, Stack_alloc *alloc)
static Bigint *	mult (Bigint *a, Bigint *b, Stack_alloc *alloc)
static Bigint *	pow5mult (Bigint *b, int k, Stack_alloc *alloc)
static Bigint *	lshift (Bigint *b, int k, Stack_alloc *alloc)
static int	cmp (Bigint *a, Bigint *b)
static Bigint *	diff (Bigint *a, Bigint *b, Stack_alloc *alloc)
static double	ulp (U *x)
static double	b2d (Bigint *a, int *e)
static Bigint *	d2b (U *d, int *e, int *bits, Stack_alloc *alloc)
static double	ratio (Bigint *a, Bigint *b)
static int	quorem (Bigint *b, Bigint *S)

Variables
static ULong	powers5 []
static Bigint	p5_a []
static const double	tens []
static const double	bigtens [] = {1e16, 1e32, 1e64, 1e128, 1e256}
static const double	tinytens []

Macro Definition Documentation

Bcopy

#define Bcopy	(		x,
			y
	)

Value:

  memcpy((char *)&x->sign, (char *)&y->sign, \
         2 * sizeof(int) + y->wds * sizeof(ULong))

Bias

#define Bias   1023

Big0

#define Big0   (Frac_mask1 | Exp_msk1 * (DBL_MAX_EXP + Bias - 1))

Big1

#define Big1   0xffffffff

Bletch

#define Bletch   0x10

Bndry_mask

#define Bndry_mask   0xfffff

Bndry_mask1

#define Bndry_mask1   0xfffff

d0 [1/2]

#define d0   word0(&d)

d0 [2/2]

#define d0   word0(d)

d1 [1/2]

#define d1   word1(&d)

d1 [2/2]

#define d1   word1(d)

DTOA_BUFF_SIZE

#define DTOA_BUFF_SIZE   (460 * sizeof(void *))

Appears to suffice to not call malloc() in most cases.

DTOA_OVERFLOW

#define DTOA_OVERFLOW   9999

dval

#define dval

(

x

)

(x)->d

Ebits

#define Ebits   11

Emin

#define Emin   (-1022)

EOVERFLOW

#define EOVERFLOW   84

Exp_1

#define Exp_1   0x3ff00000

Exp_11

#define Exp_11   0x3ff00000

Exp_mask

#define Exp_mask   0x7ff00000

Exp_msk1

#define Exp_msk1   0x100000

Exp_shift

#define Exp_shift   20

Exp_shift1

#define Exp_shift1   20

FFFFFFFF

#define FFFFFFFF   0xffffffffUL

Flt_Rounds

#define Flt_Rounds   1

Frac_mask

#define Frac_mask   0xfffff

Frac_mask1

#define Frac_mask1   0xfffff

Int_max

#define Int_max   14

Kmax

#define Kmax   15

Log2P

#define Log2P   1

LSB

#define LSB   1

n_bigtens

#define n_bigtens   5

P

#define P   53

P5A_MAX

#define P5A_MAX   (sizeof(p5_a) / sizeof(*p5_a) - 1)

Quick_max

#define Quick_max   14

rounded_product

#define rounded_product	(		a,
			b
	)		a *= b

rounded_quotient

#define rounded_quotient	(		a,
			b
	)		a /= b

Scale_Bit

#define Scale_Bit   0x10

Sign_bit

#define Sign_bit   0x80000000

Ten_pmax

#define Ten_pmax   22

Tiny1

#define Tiny1   1

word0

#define word0

(

x

)

(x)->L[1]

word1

#define word1

(

x

)

(x)->L[0]

Typedef Documentation

Bigint

typedef struct Bigint Bigint

LLong

typedef int64 LLong

Long

typedef int32 Long

Stack_alloc

typedef struct Stack_alloc Stack_alloc

ULLong

typedef uint64 ULLong

ULong

typedef uint32 ULong

Function Documentation

b2d()

static double b2d ( Bigint *  a, int *  e  )

static

Balloc()

static Bigint * Balloc ( int  k, Stack_alloc *  alloc  )

static

Bfree()

static void Bfree ( Bigint *  v, Stack_alloc *  alloc  )

static

cmp()

static int cmp ( Bigint *  a, Bigint *  b  )

static

d2b()

static Bigint * d2b ( U *  d, int *  e, int *  bits, Stack_alloc *  alloc  )

static

diff()

static Bigint * diff ( Bigint *  a, Bigint *  b, Stack_alloc *  alloc  )

static

dtoa()

static char * dtoa ( double  dd, int  mode, int  ndigits, int *  decpt, int *  sign, char **  rve, char *  buf, size_t  buf_size  )

static

dtoa_alloc()

static char * dtoa_alloc ( int  i, Stack_alloc *  alloc  )

static

dtoa_free()

static void dtoa_free ( char *  gptr, char *  buf, size_t  buf_size  )

static

hi0bits()

static int hi0bits ( ULong  x )

static

i2b()

static Bigint * i2b ( int  i, Stack_alloc *  alloc  )

static

lo0bits()

static int lo0bits ( ULong *  y )

static

lshift()

static Bigint * lshift ( Bigint *  b, int  k, Stack_alloc *  alloc  )

static

mult()

static Bigint * mult ( Bigint *  a, Bigint *  b, Stack_alloc *  alloc  )

static

multadd()

static Bigint * multadd ( Bigint *  b, int  m, int  a, Stack_alloc *  alloc  )

static

my_fcvt()

size_t my_fcvt	(	double	x,
		int	precision,
		char *	to,
		bool *	error
	)

Converts a given floating point number to a zero-terminated string representation using the 'f' format.

This function is a wrapper around dtoa() to do the same as sprintf(to, "%-.*f", precision, x), though the conversion is usually more precise. The only difference is in handling [-,+]infinity and nan values, in which case we print '0\0' to the output string and indicate an overflow.

Parameters

x	the input floating point number.
precision	the number of digits after the decimal point. All properties of sprintf() apply: if the number of significant digits after the decimal point is less than precision, the resulting string is right-padded with zeros if the precision is 0, no decimal point appears if a decimal point appears, at least one digit appears before it
to	pointer to the output buffer. The longest string which my_fcvt() can return is FLOATING_POINT_BUFFER bytes (including the terminating '\0').
error	if not NULL, points to a location where the status of conversion is stored upon return. false successful conversion true the input number is [-,+]infinity or nan. The output string in this case is always '0'.

Returns

number of written characters (excluding terminating '\0')

my_fcvt_compact()

size_t my_fcvt_compact	(	double	x,
		char *	to,
		bool *	error
	)

Converts a given floating point number to a zero-terminated string representation using the 'f' format.

This function is a wrapper around dtoa() to do almost the same as sprintf(to, "%-.*f", precision, x), though the conversion is usually more precise. The only difference is in handling [-,+]infinity and nan values, in which case we print '0\0' to the output string and indicate an overflow.

The string always contains the minimum number of digits necessary to reproduce the same binary double value if the string is parsed back to a double value.

Parameters

x	the input floating point number.
to	pointer to the output buffer. The longest string which my_fcvt() can return is FLOATING_POINT_BUFFER bytes (including the terminating '\0').
error	if not NULL, points to a location where the status of conversion is stored upon return. false successful conversion true the input number is [-,+]infinity or nan. The output string in this case is always '0'.

Returns

number of written characters (excluding terminating '\0')

my_fcvt_internal()

static size_t my_fcvt_internal ( double  x, int  precision, bool  shorten, char *  to, bool *  error  )

static

Converts a given floating point number to a zero-terminated string representation using the 'f' format.

This function is a wrapper around dtoa() to do the same as sprintf(to, "%-.*f", precision, x), though the conversion is usually more precise. The only difference is in handling [-,+]infinity and nan values, in which case we print '0\0' to the output string and indicate an overflow.

Parameters

x	the input floating point number.
precision	the number of digits after the decimal point. All properties of sprintf() apply: if the number of significant digits after the decimal point is less than precision, the resulting string is right-padded with zeros if the precision is 0, no decimal point appears if a decimal point appears, at least one digit appears before it
to	pointer to the output buffer. The longest string which my_fcvt() can return is FLOATING_POINT_BUFFER bytes (including the terminating '\0').
error	if not NULL, points to a location where the status of conversion is stored upon return. false successful conversion true the input number is [-,+]infinity or nan. The output string in this case is always '0'.
shorten	Whether to minimize the number of significant digits. If true, write only the minimum number of digits necessary to reproduce the double value when parsing the string. If false, zeros are added to the end to reach the precision limit.

Returns

number of written characters (excluding terminating '\0')

my_gcvt()

size_t my_gcvt	(	double	x,
		my_gcvt_arg_type	type,
		int	width,
		char *	to,
		bool *	error
	)

Converts a given floating point number to a zero-terminated string representation with a given field width using the 'e' format (aka scientific notation) or the 'f' one.

The format is chosen automatically to provide the most number of significant digits (and thus, precision) with a given field width. In many cases, the result is similar to that of sprintf(to, "%g", x) with a few notable differences:

• the conversion is usually more precise than C library functions.
• there is no 'precision' argument. instead, we specify the number of characters available for conversion (i.e. a field width).
• the result never exceeds the specified field width. If the field is too short to contain even a rounded decimal representation, my_gcvt() indicates overflow and truncates the output string to the specified width.
• float-type arguments are handled differently than double ones. For a float input number (i.e. when the 'type' argument is MY_GCVT_ARG_FLOAT) we deliberately limit the precision of conversion by FLT_DIG digits to avoid garbage past the significant digits.
• unlike sprintf(), in cases where the 'e' format is preferred, we don't zero-pad the exponent to save space for significant digits. The '+' sign for a positive exponent does not appear for the same reason.

Parameters

x	the input floating point number.
type	is either MY_GCVT_ARG_FLOAT or MY_GCVT_ARG_DOUBLE. Specifies the type of the input number (see notes above).
width	field width in characters. The minimal field width to hold any number representation (albeit rounded) is 7 characters ("-Ne-NNN").
to	pointer to the output buffer. The result is always zero-terminated, and the longest returned string is thus 'width + 1' bytes.
error	if not NULL, points to a location where the status of conversion is stored upon return. false successful conversion true the input number is [-,+]infinity or nan. The output string in this case is always '0'.

Returns

number of written characters (excluding terminating '\0')

my_gcvt(-9e-3, ..., 4, ...); my_gcvt(-9e-3, ..., 2, ...); my_gcvt(1.87e-3, ..., 4, ...); my_gcvt(55, ..., 1, ...);

We do our best to minimize such cases by:

• passing to dtoa() the field width as the number of significant digits
• removing the sign of the number early (and decreasing the width before passing it to dtoa())
• choosing the proper format to preserve the most number of significant digits.

my_strtod()

double my_strtod	(	const char *	str,
		const char **	end,
		int *	error
	)

Converts string to double (string does not have to be zero-terminated)

This is a wrapper around dtoa's version of strtod().

Parameters

str	input string
end	address of a pointer to the first character after the input string. Upon return the pointer is set to point to the first rejected character.
error	Upon return is set to EOVERFLOW in case of underflow or overflow.

Returns

The resulting double value. In case of underflow, 0.0 is returned. In case overflow, signed DBL_MAX is returned.

my_strtod_int()

static double my_strtod_int ( const char *  s00, const char **  se, int *  error, char *  buf, size_t  buf_size  )

static

pow5mult()

static Bigint * pow5mult ( Bigint *  b, int  k, Stack_alloc *  alloc  )

static

quorem()

static int quorem ( Bigint *  b, Bigint *  S  )

static

ratio()

static double ratio ( Bigint *  a, Bigint *  b  )

static

s2b()

static Bigint * s2b ( const char *  s, int  nd0, int  nd, ULong  y9, Stack_alloc *  alloc  )

static

Converts a string to Bigint.

Now we have nd0 digits, starting at s, followed by a decimal point, followed by nd-nd0 digits. Unless nd0 == nd, in which case we have a number of the form: ".xxxxxx" or "xxxxxx."

Parameters

s	Input string, already partially parsed by my_strtod_int().
nd0	Number of digits before decimal point.
nd	Total number of digits.
y9	Pre-computed value of the first nine digits.
alloc	Stack allocator for Bigints.

ulp()

static double ulp ( U *  x )

static

Variable Documentation

bigtens

const double bigtens[] = {1e16, 1e32, 1e64, 1e128, 1e256}

static

p5_a

Bigint p5_a[]

static

Initial value:

= {
    
    {{powers5}, 1, 1, 0, 1},       {{powers5 + 1}, 1, 1, 0, 1},
    {{powers5 + 2}, 1, 2, 0, 2},   {{powers5 + 4}, 2, 3, 0, 3},
    {{powers5 + 7}, 3, 5, 0, 5},   {{powers5 + 12}, 4, 10, 0, 10},
    {{powers5 + 22}, 5, 19, 0, 19}}

powers5

ULong powers5[]

static

Initial value:

= {
    625UL,
 
    390625UL,
 
    2264035265UL, 35UL,
 
    2242703233UL, 762134875UL,  1262UL,
 
    3211403009UL, 1849224548UL, 3668416493UL, 3913284084UL, 1593091UL,
 
    781532673UL,  64985353UL,   253049085UL,  594863151UL,  3553621484UL,
    3288652808UL, 3167596762UL, 2788392729UL, 3911132675UL, 590UL,
 
    2553183233UL, 3201533787UL, 3638140786UL, 303378311UL,  1809731782UL,
    3477761648UL, 3583367183UL, 649228654UL,  2915460784UL, 487929380UL,
    1011012442UL, 1677677582UL, 3428152256UL, 1710878487UL, 1438394610UL,
    2161952759UL, 4100910556UL, 1608314830UL, 349175UL}

tens

const double tens[]

static

Initial value:

= {1e0,  1e1,  1e2,  1e3,  1e4,  1e5,  1e6,  1e7,
                              1e8,  1e9,  1e10, 1e11, 1e12, 1e13, 1e14, 1e15,
                              1e16, 1e17, 1e18, 1e19, 1e20, 1e21, 1e22}

tinytens

const double tinytens[]

static

Initial value:

= {
    1e-16, 1e-32, 1e-64, 1e-128,
    9007199254740992. * 9007199254740992.e-256 
}