jsdtoa.c

来自「一个基于alice开发的机器人」· C语言 代码 · 共 2,314 行 · 第 1/5 页

/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 *
 * ***** BEGIN LICENSE BLOCK *****
 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
 *
 * The contents of this file are subject to the Mozilla Public License Version
 * 1.1 (the "License"); you may not use this file except in compliance with
 * the License. You may obtain a copy of the License at
 * http://www.mozilla.org/MPL/
 *
 * Software distributed under the License is distributed on an "AS IS" basis,
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 * for the specific language governing rights and limitations under the
 * License.
 *
 * The Original Code is Mozilla Communicator client code, released
 * March 31, 1998.
 *
 * The Initial Developer of the Original Code is
 * Netscape Communications Corporation.
 * Portions created by the Initial Developer are Copyright (C) 1998
 * the Initial Developer. All Rights Reserved.
 *
 * Contributor(s):
 *
 * Alternatively, the contents of this file may be used under the terms of
 * either of the GNU General Public License Version 2 or later (the "GPL"),
 * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
 * in which case the provisions of the GPL or the LGPL are applicable instead
 * of those above. If you wish to allow use of your version of this file only
 * under the terms of either the GPL or the LGPL, and not to allow others to
 * use your version of this file under the terms of the MPL, indicate your
 * decision by deleting the provisions above and replace them with the notice
 * and other provisions required by the GPL or the LGPL. If you do not delete
 * the provisions above, a recipient may use your version of this file under
 * the terms of any one of the MPL, the GPL or the LGPL.
 *
 * ***** END LICENSE BLOCK ***** */

/*
 * Portable double to alphanumeric string and back converters.
 */
#include "jsstddef.h"
#include "jslibmath.h"
#include "jstypes.h"
#include "jsdtoa.h"
#include "jsprf.h"
#include "jsutil.h" /* Added by JSIFY */
#include "jspubtd.h"
#include "jsnum.h"

#ifdef JS_THREADSAFE
#include "prlock.h"
#endif

/****************************************************************
 *
 * The author of this software is David M. Gay.
 *
 * Copyright (c) 1991 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.
    [e-mail]
 */

/* 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-arithmetic machines.
 *
 * This strtod returns a nearest machine number to the input decimal
 * string (or sets err to JS_DTOA_ERANGE or JS_DTOA_ENOMEM).  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 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 Sudden_Underflow for IEEE-format machines without gradual
 *  underflow (i.e., that flush to zero on underflow).
 * #define No_leftright to omit left-right logic in fast floating-point
 *  computation of js_dtoa.
 * #define Check_FLT_ROUNDS if FLT_ROUNDS can assume the values 2 or 3.
 * #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 JS_HAVE_LONG_LONG on machines that have a "long long"
 *  integer type (of >= 64 bits).  If long long is available and the name is
 *  something other than "long long", #define Llong to be the name,
 *  and if "unsigned Llong" does not work as an unsigned version of
 *  Llong, #define #ULLong to be the corresponding unsigned type.
 * #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 MALLOC your_malloc, where your_malloc(n) acts like malloc(n)
 *  if memory is available and otherwise does something you deem
 *  appropriate.  If MALLOC is undefined, malloc will be invoked
 *  directly -- and assumed always to succeed.
 * #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: 2000 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.
 * #define INFNAN_CHECK on IEEE systems to cause strtod to check for
 *  Infinity and NaN (case insensitively).  On some systems (e.g.,
 *  some HP systems), it may be necessary to #define NAN_WORD0
 *  appropriately -- to the most significant word of a quiet NaN.
 *  (On HP Series 700/800 machines, -DNAN_WORD0=0x7ff40000 works.)
 * #define MULTIPLE_THREADS if the system offers preemptively scheduled
 *  multiple threads.  In this case, you must provide (or suitably
 *  #define) two locks, acquired by ACQUIRE_DTOA_LOCK() and released
 *  by RELEASE_DTOA_LOCK().  (The second lock, accessed
 *  in pow5mult, ensures lazy evaluation of only one copy of high
 *  powers of 5; omitting this lock would introduce a small
 *  probability of wasting memory, but would otherwise be harmless.)
 *  You must also invoke freedtoa(s) to free the value s returned by
 *  dtoa.  You may do so whether or not MULTIPLE_THREADS is #defined.
 * #define NO_IEEE_Scale to disable new (Feb. 1997) logic in strtod that
 *  avoids underflows on inputs whose result does not underflow.
 */
#ifdef IS_LITTLE_ENDIAN
#define IEEE_8087
#else
#define IEEE_MC68k
#endif

#ifndef Long
#define Long int32
#endif

#ifndef ULong
#define ULong uint32
#endif

#define Bug(errorMessageString) JS_ASSERT(!errorMessageString)

#include "stdlib.h"
#include "string.h"

#ifdef MALLOC
extern void *MALLOC(size_t);
#else
#define MALLOC malloc
#endif

#define Omit_Private_Memory
/* Private memory currently doesn't work with JS_THREADSAFE */
#ifndef Omit_Private_Memory
#ifndef PRIVATE_MEM
#define PRIVATE_MEM 2000
#endif
#define PRIVATE_mem ((PRIVATE_MEM+sizeof(double)-1)/sizeof(double))
static double private_mem[PRIVATE_mem], *pmem_next = private_mem;
#endif

#ifdef Bad_float_h
#undef __STDC__

#define DBL_DIG 15
#define DBL_MAX_10_EXP 308
#define DBL_MAX_EXP 1024
#define FLT_RADIX 2
#define FLT_ROUNDS 1
#define DBL_MAX 1.7976931348623157e+308



#ifndef LONG_MAX
#define LONG_MAX 2147483647
#endif

#else /* ifndef Bad_float_h */
#include "float.h"
/*
 * MacOS 10.2 defines the macro FLT_ROUNDS to an internal function
 * which does not exist on 10.1.  We can safely #define it to 1 here
 * to allow 10.2 builds to run on 10.1, since we can't use fesetround()
 * (which does not exist on 10.1 either).
 */
#if defined(MACOS_DEPLOYMENT_TARGET) && (MACOS_DEPLOYMENT_TARGET < 100200)
#undef FLT_ROUNDS   
#define FLT_ROUNDS 1
#endif
#endif /* Bad_float_h */

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

#ifndef CONST
#define CONST const
#endif

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

#define word0(x)        JSDOUBLE_HI32(x)
#define set_word0(x, y) JSDOUBLE_SET_HI32(x, y)
#define word1(x)        JSDOUBLE_LO32(x)
#define set_word1(x, y) JSDOUBLE_SET_LO32(x, y)

#define Storeinc(a,b,c) (*(a)++ = (b) << 16 | (c) & 0xffff)

/* #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) */

#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
#define Infinite(x) (word0(x) == 0x7ff00000) /* sufficient test for here */
#ifndef NO_IEEE_Scale
#define Avoid_Underflow
#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 JS_HAVE_LONG_LONG
#undef ULLong
#else   /* long long available */
#ifndef Llong
#define Llong JSInt64
#endif
#ifndef ULLong
#define ULLong JSUint64
#endif
#endif /* JS_HAVE_LONG_LONG */

#ifdef JS_THREADSAFE
#define MULTIPLE_THREADS
static PRLock *freelist_lock;
#define ACQUIRE_DTOA_LOCK()                                                   \
    JS_BEGIN_MACRO                                                            \
        if (!initialized)                                                     \
            InitDtoa();                                                       \
        PR_Lock(freelist_lock);                                               \
    JS_END_MACRO
#define RELEASE_DTOA_LOCK() PR_Unlock(freelist_lock)
#else
#undef MULTIPLE_THREADS
#define ACQUIRE_DTOA_LOCK()   /*nothing*/
#define RELEASE_DTOA_LOCK()   /*nothing*/
#endif

#define Kmax 15

struct Bigint {
    struct Bigint *next;  /* Free list link */
    int32 k;              /* lg2(maxwds) */
    int32 maxwds;         /* Number of words allocated for x */
    int32 sign;           /* Zero if positive, 1 if negative.  Ignored by most Bigint routines! */
    int32 wds;            /* Actual number of words.  If value is nonzero, the most significant word must be nonzero. */
    ULong x[1];           /* wds words of number in little endian order */
};

#ifdef ENABLE_OOM_TESTING
/* Out-of-memory testing.  Use a good testcase (over and over) and then use
 * these routines to cause a memory failure on every possible Balloc allocation,
 * to make sure that all out-of-memory paths can be followed.  See bug 14044.
 */

static int allocationNum;               /* which allocation is next? */
static int desiredFailure;              /* which allocation should fail? */

/**
 * js_BigintTestingReset
 *
 * Call at the beginning of a test run to set the allocation failure position.
 * (Set to 0 to just have the engine count allocations without failing.)
 */
JS_PUBLIC_API(void)
js_BigintTestingReset(int newFailure)
{
    allocationNum = 0;
    desiredFailure = newFailure;
}

/**
 * js_BigintTestingWhere
 *
 * Report the current allocation position.  This is really only useful when you
 * want to learn how many allocations a test run has.
 */
JS_PUBLIC_API(int)
js_BigintTestingWhere()
{
    return allocationNum;
}


/*
 * So here's what you do: Set up a fantastic test case that exercises the
 * elements of the code you wish.  Set the failure point at 0 and run the test,
 * then get the allocation position.  This number is the number of allocations
 * your test makes.  Now loop from 1 to that number, setting the failure point
 * at each loop count, and run the test over and over, causing failures at each
 * step.  Any memory failure *should* cause a Out-Of-Memory exception; if it
 * doesn't, then there's still an error here.
 */
#endif

typedef struct Bigint Bigint;

static Bigint *freelist[Kmax+1];

/*
 * Allocate a Bigint with 2^k words.
 * This is not threadsafe. The caller must use thread locks
 */
static Bigint *Balloc(int32 k)
{
    int32 x;
    Bigint *rv;
#ifndef Omit_Private_Memory
    uint32 len;
#endif

#ifdef ENABLE_OOM_TESTING
    if (++allocationNum == desiredFailure) {
        printf("Forced Failing Allocation number %d\n", allocationNum);
        return NULL;
    }
#endif

    if ((rv = freelist[k]) != NULL)
        freelist[k] = rv->next;
    if (rv == NULL) {
        x = 1 << k;
#ifdef Omit_Private_Memory
        rv = (Bigint *)MALLOC(sizeof(Bigint) + (x-1)*sizeof(ULong));
#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*)MALLOC(len*sizeof(double));
#endif
        if (!rv)
            return NULL;
        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(int32))

/* Return b*m + a.  Deallocate the old b.  Both a and m must be between 0 and
 * 65535 inclusive.  NOTE: old b is deallocated on memory failure.
 */
static Bigint *multadd(Bigint *b, int32 m, int32 a)
{
    int32 i, wds;
#ifdef ULLong
    ULong *x;
    ULLong carry, y;
#else