mux/src/strtod.cpp

Go to the documentation of this file.

/****************************************************************
 *
 * The author of this software is David M. Gay.
 *
 * Copyright (c) 1991, 2000, 2001 by Lucent Technologies.
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose without fee is hereby granted, provided that this entire notice
 * is included in all copies of any software which is or includes a copy
 * or modification of this software and in all copies of the supporting
 * documentation for such software.
 *
 * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTY.  IN PARTICULAR, NEITHER THE AUTHOR NOR LUCENT MAKES ANY
 * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
 * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
 *
 ***************************************************************/

/* Please send bug reports to
    David M. Gay
    Bell Laboratories, Room 2C-463
    600 Mountain Avenue
    Murray Hill, NJ 07974-0636
    U.S.A.
    dmg@bell-labs.com
 */

/* On a machine with IEEE extended-precision registers, it is
 * necessary to specify double-precision (53-bit) rounding precision
 * before invoking strtod or dtoa.  If the machine uses (the equivalent
 * of) Intel 80x87 arithmetic, the call
 *  _control87(PC_53, MCW_PC);
 * does this with many compilers.  Whether this or another call is
 * appropriate depends on the compiler; for this to work, it may be
 * necessary to #include "float.h" or another system-dependent header
 * file.
 */

/* strtod for IEEE-, VAX-, and IBM-arithmetic machines.
 *
 * This strtod returns a nearest machine number to the input decimal
 * string (or sets errno to ERANGE).  With IEEE arithmetic, ties are
 * broken by the IEEE round-even rule.  Otherwise ties are broken by
 * biased rounding (add half and chop).
 *
 * Inspired loosely by William D. Clinger's paper "How to Read Floating
 * Point Numbers Accurately" [Proc. ACM SIGPLAN '90, pp. 92-101].
 *
 * Modifications:
 *
 *  1. We only require IEEE, IBM, or VAX double-precision
 *      arithmetic (not IEEE double-extended).
 *  2. We get by with floating-point arithmetic in a case that
 *      Clinger missed -- when we're computing d * 10^n
 *      for a small integer d and the integer n is not too
 *      much larger than 22 (the maximum integer k for which
 *      we can represent 10^k exactly), we may be able to
 *      compute (d*10^k) * 10^(e-k) with just one roundoff.
 *  3. Rather than a bit-at-a-time adjustment of the binary
 *      result in the hard case, we use floating-point
 *      arithmetic to determine the adjustment to within
 *      one bit; only in really hard cases do we need to
 *      compute a second residual.
 *  4. Because of 3., we don't need a large table of powers of 10
 *      for ten-to-e (just some small tables, e.g. of 10^k
 *      for 0 <= k <= 22).
 */

/*
 * #define IEEE_8087 for IEEE-arithmetic machines where the least
 *  significant byte has the lowest address.
 * #define IEEE_MC68k for IEEE-arithmetic machines where the most
 *  significant byte has the lowest address.
 * #define Long int on machines with 32-bit ints and 64-bit longs.
 * #define IBM for IBM mainframe-style floating-point arithmetic.
 * #define VAX for VAX-style floating-point arithmetic (D_floating).
 * #define No_leftright to omit left-right logic in fast floating-point
 *  computation of dtoa.
 * #define Honor_FLT_ROUNDS if FLT_ROUNDS can assume the values 2 or 3
 *  and strtod and dtoa should round accordingly.
 * #define Check_FLT_ROUNDS if FLT_ROUNDS can assume the values 2 or 3
 *  and Honor_FLT_ROUNDS is not #defined.
 * #define RND_PRODQUOT to use rnd_prod and rnd_quot (assembly routines
 *  that use extended-precision instructions to compute rounded
 *  products and quotients) with IBM.
 * #define ROUND_BIASED for IEEE-format with biased rounding.
 * #define Inaccurate_Divide for IEEE-format with correctly rounded
 *  products but inaccurate quotients, e.g., for Intel i860.
 * #define Bad_float_h if your system lacks a float.h or if it does not
 *  define some or all of DBL_DIG, DBL_MAX_10_EXP, DBL_MAX_EXP,
 *  FLT_RADIX, FLT_ROUNDS, and DBL_MAX.
 * #define Omit_Private_Memory to omit logic (added Jan. 1998) for making
 *  memory allocations from a private pool of memory when possible.
 *  When used, the private pool is PRIVATE_MEM bytes long:  2304 bytes,
 *  unless #defined to be a different length.  This default length
 *  suffices to get rid of MALLOC calls except for unusual cases,
 *  such as decimal-to-binary conversion of a very long string of
 *  digits.  The longest string dtoa can return is about 751 bytes
 *  long.  For conversions by strtod of strings of 800 digits and
 *  all dtoa conversions in single-threaded executions with 8-byte
 *  pointers, PRIVATE_MEM >= 7400 appears to suffice; with 4-byte
 *  pointers, PRIVATE_MEM >= 7112 appears adequate.
 * #define NO_IEEE_Scale to disable new (Feb. 1997) logic in strtod that
 *  avoids underflows on inputs whose result does not underflow.
 *  If you #define NO_IEEE_Scale on a machine that uses IEEE-format
 *  floating-point numbers and flushes underflows to zero rather
 *  than implementing gradual underflow, then you must also #define
 *  Sudden_Underflow.
 * #define YES_ALIAS to permit aliasing certain double values with
 *  arrays of ULongs.  This leads to slightly better code with
 *  some compilers and was always used prior to 19990916, but it
 *  is not strictly legal and can cause trouble with aggressively
 *  optimizing compilers (e.g., gcc 2.95.1 under -O2).
 * #define SET_INEXACT if IEEE arithmetic is being used and extra
 *  computation should be done to set the inexact flag when the
 *  result is inexact and avoid setting inexact when the result
 *  is exact.  In this case, dtoa.c must be compiled in
 *  an environment, perhaps provided by #include "dtoa.c" in a
 *  suitable wrapper, that defines two functions,
 *      int get_inexact(void);
 *      void clear_inexact(void);
 *  such that get_inexact() returns a nonzero value if the
 *  inexact bit is already set, and clear_inexact() sets the
 *  inexact bit to 0.  When SET_INEXACT is #defined, strtod
 *  also does extra computations to set the underflow and overflow
 *  flags when appropriate (i.e., when the result is tiny and
 *  inexact or when it is a numeric value rounded to +-infinity).
 */

#include "autoconf.h"
#include "config.h"
#include "externs.h"
#include "stringutil.h"

#if   defined(HAVE_FPU_CONTROL_H)
#include <fpu_control.h>
#elif defined(IEEEFP_H_USEABLE)
#include <ieeefp.h>
#elif defined(HAVE_FENV_H)
#include <fenv.h>
#endif

#if defined(WORDS_BIGENDIAN)
#define IEEE_MC68k
#elif defined(WORDS_LITTLEENDIAN)
#define IEEE_8087
#else
#error Must be either Big or Little Endian.
#endif

#define Long INT32
typedef UINT32 ULong;

#ifndef Omit_Private_Memory
#ifndef PRIVATE_MEM
#define PRIVATE_MEM 2304
#endif
#define PRIVATE_mem ((PRIVATE_MEM+sizeof(double)-1)/sizeof(double))
static double private_mem[PRIVATE_mem], *pmem_next = private_mem;
#endif

#undef IEEE_Arith
#undef Avoid_Underflow
#ifdef IEEE_MC68k
#define IEEE_Arith
#endif
#ifdef IEEE_8087
#define IEEE_Arith
#endif

#ifdef Bad_float_h

#ifdef IEEE_Arith
#define DBL_DIG 15
#define DBL_MAX_10_EXP 308
#define DBL_MAX_EXP 1024
#define FLT_RADIX 2
#endif /*IEEE_Arith*/

#ifdef IBM
#define DBL_DIG 16
#define DBL_MAX_10_EXP 75
#define DBL_MAX_EXP 63
#define FLT_RADIX 16
#define DBL_MAX 7.2370055773322621e+75
#endif

#ifdef VAX
#define DBL_DIG 16
#define DBL_MAX_10_EXP 38
#define DBL_MAX_EXP 127
#define FLT_RADIX 2
#define DBL_MAX 1.7014118346046923e+38
#endif

#ifndef LONG_MAX
#define LONG_MAX 2147483647
#endif

#else /* ifndef Bad_float_h */
#include "float.h"
#endif /* Bad_float_h */

#ifndef __MATH_H__
#include "math.h"
#endif

#ifndef CONST
#define CONST const
#endif

#if defined(IEEE_8087) + defined(IEEE_MC68k) + defined(VAX) + defined(IBM) != 1
Exactly one of IEEE_8087, IEEE_MC68k, VAX, or IBM should be defined.
#endif

typedef union
{
    double d;
    ULong L[2];
} U;

#ifdef YES_ALIAS
#define dval(x) x
#ifdef IEEE_8087
#define word0(x) ((ULong *)&x)[1]
#define word1(x) ((ULong *)&x)[0]
#else
#define word0(x) ((ULong *)&x)[0]
#define word1(x) ((ULong *)&x)[1]
#endif
#else
#ifdef IEEE_8087
#define word0(x) ((U*)&x)->L[1]
#define word1(x) ((U*)&x)->L[0]
#else
#define word0(x) ((U*)&x)->L[0]
#define word1(x) ((U*)&x)->L[1]
#endif
#define dval(x) ((U*)&x)->d
#endif

/* The following definition of Storeinc is appropriate for MIPS processors.
 * An alternative that might be better on some machines is
 * #define Storeinc(a,b,c) (*a++ = b << 16 | c & 0xffff)
 */
#if defined(IEEE_8087) + defined(VAX)
#define Storeinc(a,b,c) (((unsigned short *)a)[1] = (unsigned short)b, \
((unsigned short *)a)[0] = (unsigned short)c, a++)
#else
#define Storeinc(a,b,c) (((unsigned short *)a)[0] = (unsigned short)b, \
((unsigned short *)a)[1] = (unsigned short)c, a++)
#endif

/* #define P DBL_MANT_DIG */
/* Ten_pmax = floor(P*log(2)/log(5)) */
/* Bletch = (highest power of 2 < DBL_MAX_10_EXP) / 16 */
/* Quick_max = floor((P-1)*log(FLT_RADIX)/log(10) - 1) */
/* Int_max = floor(P*log(FLT_RADIX)/log(10) - 1) */

#ifdef IEEE_Arith
#define Exp_shift  20
#define Exp_shift1 20
#define Exp_msk1    0x100000
#define Exp_msk11   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 Tiny0 0
#define Tiny1 1
#define Quick_max 14
#define Int_max 14
#ifndef NO_IEEE_Scale
#define Avoid_Underflow
#ifdef Flush_Denorm /* debugging option */
#undef Sudden_Underflow
#endif
#endif

#ifndef Flt_Rounds
#ifdef FLT_ROUNDS
#define Flt_Rounds FLT_ROUNDS
#else
#define Flt_Rounds 1
#endif
#endif /*Flt_Rounds*/

#ifdef Honor_FLT_ROUNDS
#define Rounding rounding
#undef Check_FLT_ROUNDS
#define Check_FLT_ROUNDS
#else
#define Rounding Flt_Rounds
#endif

#else /* ifndef IEEE_Arith */
#undef Check_FLT_ROUNDS
#undef Honor_FLT_ROUNDS
#undef SET_INEXACT
#undef  Sudden_Underflow
#define Sudden_Underflow
#ifdef IBM
#undef Flt_Rounds
#define Flt_Rounds 0
#define Exp_shift  24
#define Exp_shift1 24
#define Exp_msk1   0x1000000
#define Exp_msk11  0x1000000
#define Exp_mask  0x7f000000
#define P 14
#define Bias 65
#define Exp_1  0x41000000
#define Exp_11 0x41000000
#define Ebits 8 /* exponent has 7 bits, but 8 is the right value in b2d */
#define Frac_mask  0xffffff
#define Frac_mask1 0xffffff
#define Bletch 4
#define Ten_pmax 22
#define Bndry_mask  0xefffff
#define Bndry_mask1 0xffffff
#define LSB 1
#define Sign_bit 0x80000000
#define Log2P 4
#define Tiny0 0x100000
#define Tiny1 0
#define Quick_max 14
#define Int_max 15
#else /* VAX */
#undef Flt_Rounds
#define Flt_Rounds 1
#define Exp_shift  23
#define Exp_shift1 7
#define Exp_msk1    0x80
#define Exp_msk11   0x800000
#define Exp_mask  0x7f80
#define P 56
#define Bias 129
#define Exp_1  0x40800000
#define Exp_11 0x4080
#define Ebits 8
#define Frac_mask  0x7fffff
#define Frac_mask1 0xffff007f
#define Ten_pmax 24
#define Bletch 2
#define Bndry_mask  0xffff007f
#define Bndry_mask1 0xffff007f
#define LSB 0x10000
#define Sign_bit 0x8000
#define Log2P 1
#define Tiny0 0x80
#define Tiny1 0
#define Quick_max 15
#define Int_max 15
#endif /* IBM, VAX */
#endif /* IEEE_Arith */

#ifndef IEEE_Arith
#define ROUND_BIASED
#endif

#ifdef RND_PRODQUOT
#define rounded_product(a,b) a = rnd_prod(a, b)
#define rounded_quotient(a,b) a = rnd_quot(a, b)
extern double rnd_prod(double, double), rnd_quot(double, double);
#else
#define rounded_product(a,b) a *= b
#define rounded_quotient(a,b) a /= b
#endif

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

#ifndef Pack_32
#define Pack_32
#endif

#define FFFFFFFF 0xffffffffUL

#ifndef Llong
#define Llong INT64
#endif
#ifndef ULLong
#define ULLong UINT64
#endif

#define Kmax 15

struct Bigint
{
    struct Bigint *next;
    int k, maxwds, sign, wds;
    ULong x[1];
};

typedef struct Bigint Bigint;

static Bigint *freelist[Kmax+1];

static Bigint *Balloc(int k)
{
    int x;
    Bigint *rv;
#ifndef Omit_Private_Memory
    unsigned int len;
#endif

    if ((rv = freelist[k]))
    {
        freelist[k] = rv->next;
    }
    else
    {
        x = 1 << k;
#ifdef Omit_Private_Memory
        rv = (Bigint *)MEMALLOC(sizeof(Bigint) + (x-1)*sizeof(ULong));
        ISOUTOFMEMORY(rv);
#else
        len = (sizeof(Bigint) + (x-1)*sizeof(ULong) + sizeof(double) - 1)
            /sizeof(double);
        if (pmem_next - private_mem + len <= PRIVATE_mem)
        {
            rv = (Bigint*)pmem_next;
            pmem_next += len;
        }
        else
        {
            rv = (Bigint*)MEMALLOC(len*sizeof(double));
            ISOUTOFMEMORY(rv);
        }
#endif
        rv->k = k;
        rv->maxwds = x;
    }
    rv->sign = rv->wds = 0;
    return rv;
}

static void Bfree(Bigint *v)
{
    if (v)
    {
        v->next = freelist[v->k];
        freelist[v->k] = v;
    }
}

#define Bcopy(x,y) memcpy((char *)&x->sign, (char *)&y->sign, \
y->wds*sizeof(Long) + 2*sizeof(int))

// multiply by m and add a.
//
static Bigint *multadd(Bigint *b, int m, int a)
{
    int i, wds;
#ifdef ULLong
    ULong *x;
    ULLong carry, y;
#else
    ULong carry, *x, y;
#ifdef Pack_32
    ULong xi, z;
#endif
#endif
    Bigint *b1;

    wds = b->wds;
    x = b->x;
    i = 0;
    carry = a;
    do
    {
#ifdef ULLong
        y = *x * (ULLong)m + carry;
        carry = y >> 32;
        *x++ = (unsigned int)(y & 0xFFFFFFFF);
#else
#ifdef Pack_32
        xi = *x;
        y = (xi & 0xffff) * m + carry;
        z = (xi >> 16) * m + (y >> 16);
        carry = z >> 16;
        *x++ = (z << 16) + (y & 0xffff);
#else
        y = *x * m + carry;
        carry = y >> 16;
        *x++ = y & 0xffff;
#endif
#endif
    } while (++i < wds);
    if (carry)
    {
        if (wds >= b->maxwds)
        {
            b1 = Balloc(b->k+1);
            Bcopy(b1, b);
            Bfree(b);
            b = b1;
        }
        b->x[wds++] = (unsigned int)carry;
        b->wds = wds;
    }
    return b;
}

static Bigint *s2b(CONST char *s, int nd0, int nd, ULong y9)
{
    Bigint *b;
    int i, k;
    Long x, y;

    x = (nd + 8) / 9;
    for (k = 0, y = 1; x > y; y <<= 1, k++)
    {
        ; // Nothing.
    }
#ifdef Pack_32
    b = Balloc(k);
    b->x[0] = y9;
    b->wds = 1;
#else
    b = Balloc(k+1);
    b->x[0] = y9 & 0xffff;
    b->wds = (b->x[1] = y9 >> 16) ? 2 : 1;
#endif

    i = 9;
    if (9 < nd0)
    {
        s += 9;
        do
        {
            b = multadd(b, 10, *s++ - '0');
        } while (++i < nd0);
        s++;
    }
    else
    {
        s += 10;
    }
    for (; i < nd; i++)
    {
        b = multadd(b, 10, *s++ - '0');
    }
    return b;
}

static int hi0bits(register ULong x)
{
    register int k = 0;

    if (!(x & 0xffff0000))
    {
        k = 16;
        x <<= 16;
    }
    if (!(x & 0xff000000))
    {
        k += 8;
        x <<= 8;
    }
    if (!(x & 0xf0000000))
    {
        k += 4;
        x <<= 4;
    }
    if (!(x & 0xc0000000))
    {
        k += 2;
        x <<= 2;
    }
    if (!(x & 0x80000000))
    {
        k++;
        if (!(x & 0x40000000))
        {
            return 32;
        }
    }
    return k;
}

static int lo0bits(ULong *y)
{
    register int k;
    register ULong x = *y;

    if (x & 7)
    {
        if (x & 1)
        {
            return 0;
        }
        if (x & 2)
        {
            *y = x >> 1;
            return 1;
        }
        *y = x >> 2;
        return 2;
    }
    k = 0;
    if (!(x & 0xffff))
    {
        k = 16;
        x >>= 16;
    }
    if (!(x & 0xff))
    {
        k += 8;
        x >>= 8;
    }
    if (!(x & 0xf))
    {
        k += 4;
        x >>= 4;
    }
    if (!(x & 0x3))
    {
        k += 2;
        x >>= 2;
    }
    if (!(x & 1))
    {
        k++;
        x >>= 1;
        if (!(x & 1))
        {
            return 32;
        }
    }
    *y = x;
    return k;
}

static Bigint *i2b(int i)
{
    Bigint *b;

    b = Balloc(1);
    b->x[0] = i;
    b->wds = 1;
    return b;
}

static Bigint *mult(Bigint *a, Bigint *b)
{
    Bigint *c;
    int k, wa, wb, wc;
    ULong *x, *xa, *xae, *xb, *xbe, *xc, *xc0;
    ULong y;
#ifdef ULLong
    ULLong carry, z;
#else
    ULong carry, z;
#ifdef Pack_32
    ULong z2;
#endif
#endif

    if (a->wds < b->wds)
    {
        c = a;
        a = b;
        b = c;
    }
    k = a->k;
    wa = a->wds;
    wb = b->wds;
    wc = wa + wb;
    if (wc > a->maxwds)
    {
        k++;
    }
    c = Balloc(k);
    for (x = c->x, xa = x + wc; x < xa; x++)
    {
        *x = 0;
    }
    xa = a->x;
    xae = xa + wa;
    xb = b->x;
    xbe = xb + wb;
    xc0 = c->x;
#ifdef ULLong
    for (; xb < xbe; xc0++)
    {
        if ((y = *xb++))
        {
            x = xa;
            xc = xc0;
            carry = 0;
            do
            {
                z = *x++ * (ULLong)y + *xc + carry;
                carry = z >> 32;
                *xc++ = (unsigned int)(z & 0xFFFFFFFF);
            } while (x < xae);
            *xc = (unsigned int)carry;
        }
    }
#else
#ifdef Pack_32
    for (; xb < xbe; xb++, xc0++)
    {
        if (y = *xb & 0xffff)
        {
            x = xa;
            xc = xc0;
            carry = 0;
            do
            {
                z = (*x & 0xffff) * y + (*xc & 0xffff) + carry;
                carry = z >> 16;
                z2 = (*x++ >> 16) * y + (*xc >> 16) + carry;
                carry = z2 >> 16;
                Storeinc(xc, z2, z);
            } while (x < xae);
            *xc = carry;
        }
        if (y = *xb >> 16)
        {
            x = xa;
            xc = xc0;
            carry = 0;
            z2 = *xc;
            do
            {
                z = (*x & 0xffff) * y + (*xc >> 16) + carry;
                carry = z >> 16;
                Storeinc(xc, z, z2);
                z2 = (*x++ >> 16) * y + (*xc & 0xffff) + carry;
                carry = z2 >> 16;
            } while (x < xae);
            *xc = z2;
        }
    }
#else
    for (; xb < xbe; xc0++)
    {
        if (y = *xb++)
        {
            x = xa;
            xc = xc0;
            carry = 0;
            do
            {
                z = *x++ * y + *xc + carry;
                carry = z >> 16;
                *xc++ = z & 0xffff;
            } while (x < xae);
            *xc = carry;
        }
    }
#endif
#endif
    for (xc0 = c->x, xc = xc0 + wc; wc > 0 && !*--xc; --wc)
    {
        ; // Nothing.
    }
    c->wds = wc;
    return c;
}

static Bigint *p5s;

static Bigint *pow5mult(Bigint *b, int k)
{
    Bigint *b1, *p5, *p51;
    int i;
    static int p05[3] = { 5, 25, 125 };

    if ((i = k & 3))
    {
        b = multadd(b, p05[i-1], 0);
    }

    if (!(k >>= 2))
    {
        return b;
    }
    if (!(p5 = p5s))
    {
        /* first time */
        p5 = p5s = i2b(625);
        p5->next = 0;
    }
    for (;;)
    {
        if (k & 1)
        {
            b1 = mult(b, p5);
            Bfree(b);
            b = b1;
        }
        if (!(k >>= 1))
        {
            break;
        }
        if (!(p51 = p5->next))
        {
            p51 = p5->next = mult(p5,p5);
            p51->next = 0;
        }
        p5 = p51;
    }
    return b;
}

static Bigint *lshift(Bigint *b, int k)
{
    int i, k1, n, n1;
    Bigint *b1;
    ULong *x, *x1, *xe, z;

#ifdef Pack_32
    n = k >> 5;
#else
    n = k >> 4;
#endif
    k1 = b->k;
    n1 = n + b->wds + 1;
    for (i = b->maxwds; n1 > i; i <<= 1)
    {
        k1++;
    }
    b1 = Balloc(k1);
    x1 = b1->x;
    for (i = 0; i < n; i++)
    {
        *x1++ = 0;
    }
    x = b->x;
    xe = x + b->wds;
#ifdef Pack_32
    if (k &= 0x1f)
    {
        k1 = 32 - k;
        z = 0;
        do
        {
            *x1++ = *x << k | z;
            z = *x++ >> k1;
        } while (x < xe);
        if ((*x1 = z))
        {
            ++n1;
        }
    }
#else
    if (k &= 0xf)
    {
        k1 = 16 - k;
        z = 0;
        do
        {
            *x1++ = *x << k  & 0xffff | z;
            z = *x++ >> k1;
        } while (x < xe);
        if (*x1 = z)
        {
            ++n1;
        }
    }
#endif
    else
    {
        do
        {
            *x1++ = *x++;
        } while (x < xe);
    }
    b1->wds = n1 - 1;
    Bfree(b);
    return b1;
}

static int cmp(Bigint *a, Bigint *b)
{
    ULong *xa, *xa0, *xb, *xb0;
    int i, j;

    i = a->wds;
    j = b->wds;
    if (i -= j)
    {
        return i;
    }
    xa0 = a->x;
    xa = xa0 + j;
    xb0 = b->x;
    xb = xb0 + j;
    for (;;)
    {
        if (*--xa != *--xb)
        {
            return *xa < *xb ? -1 : 1;
        }
        if (xa <= xa0)
        {
            break;
        }
    }
    return 0;
}

static Bigint *diff(Bigint *a, Bigint *b)
{
    Bigint *c;
    int i, wa, wb;
    ULong *xa, *xae, *xb, *xbe, *xc;
#ifdef ULLong
    ULLong borrow, y;
#else
    ULong borrow, y;
#ifdef Pack_32
    ULong z;
#endif
#endif

    i = cmp(a,b);
    if (!i)
    {
        c = Balloc(0);
        c->wds = 1;
        c->x[0] = 0;
        return c;
    }
    if (i < 0)
    {
        c = a;
        a = b;
        b = c;
        i = 1;
    }
    else
    {
        i = 0;
    }
    c = Balloc(a->k);
    c->sign = i;
    wa = a->wds;
    xa = a->x;
    xae = xa + wa;
    wb = b->wds;
    xb = b->x;
    xbe = xb + wb;
    xc = c->x;
    borrow = 0;
#ifdef ULLong
    do
    {
        y = (ULLong)*xa++ - *xb++ - borrow;
        borrow = y >> 32 & (ULong)1;
        *xc++ = (unsigned int)(y & 0xFFFFFFFF);
    } while (xb < xbe);
    while (xa < xae)
    {
        y = *xa++ - borrow;
        borrow = y >> 32 & (ULong)1;
        *xc++ = (unsigned int)(y & 0xFFFFFFFF);
    }
#else
#ifdef Pack_32
    do
    {
        y = (*xa & 0xffff) - (*xb & 0xffff) - borrow;
        borrow = (y & 0x10000) >> 16;
        z = (*xa++ >> 16) - (*xb++ >> 16) - borrow;
        borrow = (z & 0x10000) >> 16;
        Storeinc(xc, z, y);
    } while (xb < xbe);
    while (xa < xae)
    {
        y = (*xa & 0xffff) - borrow;
        borrow = (y & 0x10000) >> 16;
        z = (*xa++ >> 16) - borrow;
        borrow = (z & 0x10000) >> 16;
        Storeinc(xc, z, y);
    }
#else
    do
    {
        y = *xa++ - *xb++ - borrow;
        borrow = (y & 0x10000) >> 16;
        *xc++ = y & 0xffff;
    } while (xb < xbe);
    while (xa < xae)
    {
        y = *xa++ - borrow;
        borrow = (y & 0x10000) >> 16;
        *xc++ = y & 0xffff;
    }
#endif
#endif
    while (!*--xc)
    {
        wa--;
    }
    c->wds = wa;
    return c;
}

double ulp(double x)
{
    register Long L;
    double a;

    L = (word0(x) & Exp_mask) - (P-1)*Exp_msk1;
#ifndef Avoid_Underflow
#ifndef Sudden_Underflow
    if (L > 0)
    {
#endif
#endif
#ifdef IBM
        L |= Exp_msk1 >> 4;
#endif
        word0(a) = L;
        word1(a) = 0;
#ifndef Avoid_Underflow
#ifndef Sudden_Underflow
    }
    else
    {
        L = -L >> Exp_shift;
        if (L < Exp_shift)
        {
            word0(a) = 0x80000 >> L;
            word1(a) = 0;
        }
        else
        {
            word0(a) = 0;
            L -= Exp_shift;
            word1(a) = L >= 31 ? 1 : 1 << 31 - L;
        }
    }
#endif
#endif
    return dval(a);
}

static double b2d(Bigint *a, int *e)
{
    ULong *xa, *xa0, w, y, z;
    int k;
    double d;
#ifdef VAX
    ULong d0, d1;
#else
#define d0 word0(d)
#define d1 word1(d)
#endif

    xa0 = a->x;
    xa = xa0 + a->wds;
    y = *--xa;
    k = hi0bits(y);
    *e = 32 - k;
#ifdef Pack_32
    if (k < Ebits)
    {
        d0 = Exp_1 | y >> (Ebits - k);
        w = xa > xa0 ? *--xa : 0;
        d1 = y << ((32-Ebits) + k) | w >> (Ebits - k);
        goto ret_d;
    }
    z = xa > xa0 ? *--xa : 0;
    if (k -= Ebits)
    {
        d0 = Exp_1 | y << k | z >> (32 - k);
        y = xa > xa0 ? *--xa : 0;
        d1 = z << k | y >> (32 - k);
    }
    else
    {
        d0 = Exp_1 | y;
        d1 = z;
    }
#else
    if (k < Ebits + 16)
    {
        z = xa > xa0 ? *--xa : 0;
        d0 = Exp_1 | y << k - Ebits | z >> Ebits + 16 - k;
        w = xa > xa0 ? *--xa : 0;
        y = xa > xa0 ? *--xa : 0;
        d1 = z << k + 16 - Ebits | w << k - Ebits | y >> 16 + Ebits - k;
        goto ret_d;
    }
    z = xa > xa0 ? *--xa : 0;
    w = xa > xa0 ? *--xa : 0;
    k -= Ebits + 16;
    d0 = Exp_1 | y << k + 16 | z << k | w >> 16 - k;
    y = xa > xa0 ? *--xa : 0;
    d1 = w << k + 16 | y << k;
#endif
ret_d:
#ifdef VAX
    word0(d) = d0 >> 16 | d0 << 16;
    word1(d) = d1 >> 16 | d1 << 16;
#else
#undef d0
#undef d1
#endif
    return dval(d);
}

static Bigint *d2b(double d, int *e, int *bits)
{
    Bigint *b;
    int de, k;
    ULong *x, y, z;
#ifndef Sudden_Underflow
    int i;
#endif
#ifdef VAX
    ULong d0, d1;
    d0 = word0(d) >> 16 | word0(d) << 16;
    d1 = word1(d) >> 16 | word1(d) << 16;
#else
#define d0 word0(d)
#define d1 word1(d)
#endif

#ifdef Pack_32
    b = Balloc(1);
#else
    b = Balloc(2);
#endif
    x = b->x;

    z = d0 & Frac_mask;
    d0 &= 0x7fffffff;   /* clear sign bit, which we ignore */
#ifdef Sudden_Underflow
    de = (int)(d0 >> Exp_shift);
#ifndef IBM
    z |= Exp_msk11;
#endif
#else
    if ((de = (int)(d0 >> Exp_shift)))
    {
        z |= Exp_msk1;
    }
#endif
#ifdef Pack_32
    if ((y = d1))
    {
        if ((k = lo0bits(&y)))
        {
            x[0] = y | z << (32 - k);
            z >>= k;
        }
        else
        {
            x[0] = y;
        }
#ifndef Sudden_Underflow
        i =
#endif
            b->wds = (x[1] = z) ? 2 : 1;
    }
    else
    {
        k = lo0bits(&z);
        x[0] = z;
#ifndef Sudden_Underflow
        i =
#endif
            b->wds = 1;
        k += 32;
    }
#else
    if (y = d1)
    {
        if (k = lo0bits(&y))
        {
            if (k >= 16)
            {
                x[0] = y | z << 32 - k & 0xffff;
                x[1] = z >> k - 16 & 0xffff;
                x[2] = z >> k;
                i = 2;
            }
            else
            {
                x[0] = y & 0xffff;
                x[1] = y >> 16 | z << 16 - k & 0xffff;
                x[2] = z >> k & 0xffff;
                x[3] = z >> k+16;
                i = 3;
            }
        }
        else
        {
            x[0] = y & 0xffff;
            x[1] = y >> 16;
            x[2] = z & 0xffff;
            x[3] = z >> 16;
            i = 3;
        }
    }
    else
    {
        k = lo0bits(&z);
        if (k >= 16)
        {
            x[0] = z;
            i = 0;
        }
        else
        {
            x[0] = z & 0xffff;
            x[1] = z >> 16;
            i = 1;
        }
        k += 32;
    }
    while (!x[i])
    {
        --i;
    }
    b->wds = i + 1;
#endif
#ifndef Sudden_Underflow
    if (de)
    {
#endif
#ifdef IBM
        *e = (de - Bias - (P-1) << 2) + k;
        *bits = 4*P + 8 - k - hi0bits(word0(d) & Frac_mask);
#else
        *e = de - Bias - (P-1) + k;
        *bits = P - k;
#endif
#ifndef Sudden_Underflow
    }
    else
    {
        *e = de - Bias - (P-1) + 1 + k;
#ifdef Pack_32
        *bits = 32*i - hi0bits(x[i-1]);
#else
        *bits = (i+2)*16 - hi0bits(x[i]);
#endif
    }
#endif
    return b;
}
#undef d0
#undef d1

static double ratio(Bigint *a, Bigint *b)
{
    double da, db;
    int k, ka, kb;

    dval(da) = b2d(a, &ka);
    dval(db) = b2d(b, &kb);
#ifdef Pack_32
    k = ka - kb + 32*(a->wds - b->wds);
#else
    k = ka - kb + 16*(a->wds - b->wds);
#endif
#ifdef IBM
    if (k > 0)
    {
        word0(da) += (k >> 2)*Exp_msk1;
        if (k &= 3)
        {
            dval(da) *= 1 << k;
        }
    }
    else
    {
        k = -k;
        word0(db) += (k >> 2)*Exp_msk1;
        if (k &= 3)
        {
            dval(db) *= 1 << k;
        }
    }
#else
    if (k > 0)
    {
        word0(da) += k*Exp_msk1;
    }
    else
    {
        k = -k;
        word0(db) += k*Exp_msk1;
    }
#endif
    return dval(da) / dval(db);
}

static CONST double tens[] =
{
    1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9,
    1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19,
    1e20, 1e21, 1e22
#ifdef VAX
    , 1e23, 1e24
#endif
};

 static