Merge mozilla-central and tracemonkey. (a=blockers)

[mozilla-central.git] / js / src / jsdtoa.cpp

/* -*- 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 "jstypes.h"
#include "jsstdint.h"
#include "jsdtoa.h"
#include "jsprf.h"
#include "jsapi.h"
#include "jsprvtd.h"
#include "jsnum.h"
#include "jsbit.h"
#include "jslibmath.h"
#include "jscntxt.h"

#include "jsobjinlines.h"

#ifdef IS_LITTLE_ENDIAN
#define IEEE_8087
#else
#define IEEE_MC68k
#endif

#ifndef Long
#define Long int32
#endif

#ifndef ULong
#define ULong uint32
#endif

/*
#ifndef Llong
#define Llong JSInt64
#endif

#ifndef ULlong
#define ULlong JSUint64
#endif
*/

#define NO_GLOBAL_STATE
#define MALLOC js_malloc
#define FREE js_free
#include "dtoa.c"

/* Mapping of JSDToStrMode -> js_dtoa mode */
static const uint8 dtoaModes[] = {
    0,   /* DTOSTR_STANDARD */
    0,   /* DTOSTR_STANDARD_EXPONENTIAL, */
    3,   /* DTOSTR_FIXED, */
    2,   /* DTOSTR_EXPONENTIAL, */
    2};  /* DTOSTR_PRECISION */

double
js_strtod_harder(DtoaState *state, const char *s00, char **se, int *err)
{
    double retval;
    if (err)
        *err = 0;
    retval = _strtod(state, s00, se);
    return retval;
}

char *
js_dtostr(DtoaState *state, char *buffer, size_t bufferSize, JSDToStrMode mode, int precision,
          double dinput)
{
    U d;
    int decPt;        /* Offset of decimal point from first digit */
    int sign;         /* Nonzero if the sign bit was set in d */
    int nDigits;      /* Number of significand digits returned by js_dtoa */
    char *numBegin;   /* Pointer to the digits returned by js_dtoa */
    char *numEnd = 0; /* Pointer past the digits returned by js_dtoa */

    JS_ASSERT(bufferSize >= (size_t)(mode <= DTOSTR_STANDARD_EXPONENTIAL
                                    ? DTOSTR_STANDARD_BUFFER_SIZE
                                    : DTOSTR_VARIABLE_BUFFER_SIZE(precision)));

    /*
     * Change mode here rather than below because the buffer may not be large
     * enough to hold a large integer.
     */
    if (mode == DTOSTR_FIXED && (dinput >= 1e21 || dinput <= -1e21))
        mode = DTOSTR_STANDARD;

    dval(d) = dinput;
    numBegin = dtoa(PASS_STATE d, dtoaModes[mode], precision, &decPt, &sign, &numEnd);
    if (!numBegin) {
        return NULL;
    }

    nDigits = numEnd - numBegin;
    JS_ASSERT((size_t) nDigits <= bufferSize - 2);
    if ((size_t) nDigits > bufferSize - 2) {
        return NULL;
    }

    memcpy(buffer + 2, numBegin, nDigits);
    freedtoa(PASS_STATE numBegin);
    numBegin = buffer + 2; /* +2 leaves space for sign and/or decimal point */
    numEnd = numBegin + nDigits;
    *numEnd = '\0';

    /* If Infinity, -Infinity, or NaN, return the string regardless of mode. */
    if (decPt != 9999) {
        JSBool exponentialNotation = JS_FALSE;
        int minNDigits = 0;  /* Min number of significant digits required */
        char *p;
        char *q;

        switch (mode) {
            case DTOSTR_STANDARD:
                if (decPt < -5 || decPt > 21)
                    exponentialNotation = JS_TRUE;
                else
                    minNDigits = decPt;
                break;

            case DTOSTR_FIXED:
                if (precision >= 0)
                    minNDigits = decPt + precision;
                else
                    minNDigits = decPt;
                break;

            case DTOSTR_EXPONENTIAL:
                JS_ASSERT(precision > 0);
                minNDigits = precision;
                /* Fall through */
            case DTOSTR_STANDARD_EXPONENTIAL:
                exponentialNotation = JS_TRUE;
                break;

            case DTOSTR_PRECISION:
                JS_ASSERT(precision > 0);
                minNDigits = precision;
                if (decPt < -5 || decPt > precision)
                    exponentialNotation = JS_TRUE;
                break;
        }

        /* If the number has fewer than minNDigits, end-pad it with zeros. */
        if (nDigits < minNDigits) {
            p = numBegin + minNDigits;
            nDigits = minNDigits;
            do {
                *numEnd++ = '0';
            } while (numEnd != p);
            *numEnd = '\0';
        }

        if (exponentialNotation) {
            /* Insert a decimal point if more than one significand digit */
            if (nDigits != 1) {
                numBegin--;
                numBegin[0] = numBegin[1];
                numBegin[1] = '.';
            }
            JS_snprintf(numEnd, bufferSize - (numEnd - buffer), "e%+d", decPt-1);
        } else if (decPt != nDigits) {
            /* Some kind of a fraction in fixed notation */
            JS_ASSERT(decPt <= nDigits);
            if (decPt > 0) {
                /* dd...dd . dd...dd */
                p = --numBegin;
                do {
                    *p = p[1];
                    p++;
                } while (--decPt);
                *p = '.';
            } else {
                /* 0 . 00...00dd...dd */
                p = numEnd;
                numEnd += 1 - decPt;
                q = numEnd;
                JS_ASSERT(numEnd < buffer + bufferSize);
                *numEnd = '\0';
                while (p != numBegin)
                    *--q = *--p;
                for (p = numBegin + 1; p != q; p++)
                    *p = '0';
                *numBegin = '.';
                *--numBegin = '0';
            }
        }
    }

    /* If negative and neither -0.0 nor NaN, output a leading '-'. */
    if (sign &&
            !(word0(d) == Sign_bit && word1(d) == 0) &&
            !((word0(d) & Exp_mask) == Exp_mask &&
              (word1(d) || (word0(d) & Frac_mask)))) {
        *--numBegin = '-';
    }
    return numBegin;
}


/* Let b = floor(b / divisor), and return the remainder.  b must be nonnegative.
 * divisor must be between 1 and 65536.
 * This function cannot run out of memory. */
static uint32
divrem(Bigint *b, uint32 divisor)
{
    int32 n = b->wds;
    uint32 remainder = 0;
    ULong *bx;
    ULong *bp;

    JS_ASSERT(divisor > 0 && divisor <= 65536);

    if (!n)
        return 0; /* b is zero */
    bx = b->x;
    bp = bx + n;
    do {
        ULong a = *--bp;
        ULong dividend = remainder << 16 | a >> 16;
        ULong quotientHi = dividend / divisor;
        ULong quotientLo;

        remainder = dividend - quotientHi*divisor;
        JS_ASSERT(quotientHi <= 0xFFFF && remainder < divisor);
        dividend = remainder << 16 | (a & 0xFFFF);
        quotientLo = dividend / divisor;
        remainder = dividend - quotientLo*divisor;
        JS_ASSERT(quotientLo <= 0xFFFF && remainder < divisor);
        *bp = quotientHi << 16 | quotientLo;
    } while (bp != bx);
    /* Decrease the size of the number if its most significant word is now zero. */
    if (bx[n-1] == 0)
        b->wds--;
    return remainder;
}

/* Return floor(b/2^k) and set b to be the remainder.  The returned quotient must be less than 2^32. */
static uint32 quorem2(Bigint *b, int32 k)
{
    ULong mask;
    ULong result;
    ULong *bx, *bxe;
    int32 w;
    int32 n = k >> 5;
    k &= 0x1F;
    mask = (1<<k) - 1;

    w = b->wds - n;
    if (w <= 0)
        return 0;
    JS_ASSERT(w <= 2);
    bx = b->x;
    bxe = bx + n;
    result = *bxe >> k;
    *bxe &= mask;
    if (w == 2) {
        JS_ASSERT(!(bxe[1] & ~mask));
        if (k)
            result |= bxe[1] << (32 - k);
    }
    n++;
    while (!*bxe && bxe != bx) {
        n--;
        bxe--;
    }
    b->wds = n;
    return result;
}


/* "-0.0000...(1073 zeros after decimal point)...0001\0" is the longest string that we could produce,
 * which occurs when printing -5e-324 in binary.  We could compute a better estimate of the size of
 * the output string and malloc fewer bytes depending on d and base, but why bother? */
#define DTOBASESTR_BUFFER_SIZE 1078
#define BASEDIGIT(digit) ((char)(((digit) >= 10) ? 'a' - 10 + (digit) : '0' + (digit)))

char *
js_dtobasestr(DtoaState *state, int base, double dinput)
{
    U d;
    char *buffer;        /* The output string */
    char *p;             /* Pointer to current position in the buffer */
    char *pInt;          /* Pointer to the beginning of the integer part of the string */
    char *q;
    uint32 digit;
    U di;                /* d truncated to an integer */
    U df;                /* The fractional part of d */

    JS_ASSERT(base >= 2 && base <= 36);

    dval(d) = dinput;
    buffer = (char*) js_malloc(DTOBASESTR_BUFFER_SIZE);
    if (!buffer)
        return NULL;
    p = buffer;

    if (dval(d) < 0.0
#if defined(XP_WIN) || defined(XP_OS2)
        && !((word0(d) & Exp_mask) == Exp_mask && ((word0(d) & Frac_mask) || word1(d))) /* Visual C++ doesn't know how to compare against NaN */
#endif
       ) {
        *p++ = '-';
        dval(d) = -dval(d);
    }

    /* Check for Infinity and NaN */
    if ((word0(d) & Exp_mask) == Exp_mask) {
        strcpy(p, !word1(d) && !(word0(d) & Frac_mask) ? "Infinity" : "NaN");
        return buffer;
    }

    /* Output the integer part of d with the digits in reverse order. */
    pInt = p;
    dval(di) = floor(dval(d));
    if (dval(di) <= 4294967295.0) {
        uint32 n = (uint32)dval(di);
        if (n)
            do {
                uint32 m = n / base;
                digit = n - m*base;
                n = m;
                JS_ASSERT(digit < (uint32)base);
                *p++ = BASEDIGIT(digit);
            } while (n);
        else *p++ = '0';
    } else {
        int e;
        int bits;  /* Number of significant bits in di; not used. */
        Bigint *b = d2b(PASS_STATE di, &e, &bits);
        if (!b)
            goto nomem1;
        b = lshift(PASS_STATE b, e);
        if (!b) {
          nomem1:
            Bfree(PASS_STATE b);
            js_free(buffer);
            return NULL;
        }
        do {
            digit = divrem(b, base);
            JS_ASSERT(digit < (uint32)base);
            *p++ = BASEDIGIT(digit);
        } while (b->wds);
        Bfree(PASS_STATE b);
    }
    /* Reverse the digits of the integer part of d. */
    q = p-1;
    while (q > pInt) {
        char ch = *pInt;
        *pInt++ = *q;
        *q-- = ch;
    }

    dval(df) = dval(d) - dval(di);
    if (dval(df) != 0.0) {
        /* We have a fraction. */
        int e, bbits;
        int32 s2, done;
        Bigint *b, *s, *mlo, *mhi;

        b = s = mlo = mhi = NULL;

        *p++ = '.';
        b = d2b(PASS_STATE df, &e, &bbits);
        if (!b) {
          nomem2:
            Bfree(PASS_STATE b);
            Bfree(PASS_STATE s);
            if (mlo != mhi)
                Bfree(PASS_STATE mlo);
            Bfree(PASS_STATE mhi);
            js_free(buffer);
            return NULL;
        }
        JS_ASSERT(e < 0);
        /* At this point df = b * 2^e.  e must be less than zero because 0 < df < 1. */

        s2 = -(int32)(word0(d) >> Exp_shift1 & Exp_mask>>Exp_shift1);
#ifndef Sudden_Underflow
        if (!s2)
            s2 = -1;
#endif
        s2 += Bias + P;
        /* 1/2^s2 = (nextDouble(d) - d)/2 */
        JS_ASSERT(-s2 < e);
        mlo = i2b(PASS_STATE 1);
        if (!mlo)
            goto nomem2;
        mhi = mlo;
        if (!word1(d) && !(word0(d) & Bndry_mask)
#ifndef Sudden_Underflow
            && word0(d) & (Exp_mask & Exp_mask << 1)
#endif
            ) {
            /* The special case.  Here we want to be within a quarter of the last input
               significant digit instead of one half of it when the output string's value is less than d.  */
            s2 += Log2P;
            mhi = i2b(PASS_STATE 1<<Log2P);
            if (!mhi)
                goto nomem2;
        }
        b = lshift(PASS_STATE b, e + s2);
        if (!b)
            goto nomem2;
        s = i2b(PASS_STATE 1);
        if (!s)
            goto nomem2;
        s = lshift(PASS_STATE s, s2);
        if (!s)
            goto nomem2;
        /* At this point we have the following:
         *   s = 2^s2;
         *   1 > df = b/2^s2 > 0;
         *   (d - prevDouble(d))/2 = mlo/2^s2;
         *   (nextDouble(d) - d)/2 = mhi/2^s2. */

        done = JS_FALSE;
        do {
            int32 j, j1;
            Bigint *delta;

            b = multadd(PASS_STATE b, base, 0);
            if (!b)
                goto nomem2;
            digit = quorem2(b, s2);
            if (mlo == mhi) {
                mlo = mhi = multadd(PASS_STATE mlo, base, 0);
                if (!mhi)
                    goto nomem2;
            }
            else {
                mlo = multadd(PASS_STATE mlo, base, 0);
                if (!mlo)
                    goto nomem2;
                mhi = multadd(PASS_STATE mhi, base, 0);
                if (!mhi)
                    goto nomem2;
            }

            /* Do we yet have the shortest string that will round to d? */
            j = cmp(b, mlo);
            /* j is b/2^s2 compared with mlo/2^s2. */
            delta = diff(PASS_STATE s, mhi);
            if (!delta)
                goto nomem2;
            j1 = delta->sign ? 1 : cmp(b, delta);
            Bfree(PASS_STATE delta);
            /* j1 is b/2^s2 compared with 1 - mhi/2^s2. */

#ifndef ROUND_BIASED
            if (j1 == 0 && !(word1(d) & 1)) {
                if (j > 0)
                    digit++;
                done = JS_TRUE;
            } else
#endif
            if (j < 0 || (j == 0
#ifndef ROUND_BIASED
                && !(word1(d) & 1)
#endif
                )) {
                if (j1 > 0) {
                    /* Either dig or dig+1 would work here as the least significant digit.
                       Use whichever would produce an output value closer to d. */
                    b = lshift(PASS_STATE b, 1);
                    if (!b)
                        goto nomem2;
                    j1 = cmp(b, s);
                    if (j1 > 0) /* The even test (|| (j1 == 0 && (digit & 1))) is not here because it messes up odd base output
                                 * such as 3.5 in base 3.  */
                        digit++;
                }
                done = JS_TRUE;
            } else if (j1 > 0) {
                digit++;
                done = JS_TRUE;
            }
            JS_ASSERT(digit < (uint32)base);
            *p++ = BASEDIGIT(digit);
        } while (!done);
        Bfree(PASS_STATE b);
        Bfree(PASS_STATE s);
        if (mlo != mhi)
            Bfree(PASS_STATE mlo);
        Bfree(PASS_STATE mhi);
    }
    JS_ASSERT(p < buffer + DTOBASESTR_BUFFER_SIZE);
    *p = '\0';
    return buffer;
}

DtoaState *
js_NewDtoaState()
{
    return newdtoa();
}

void
js_DestroyDtoaState(DtoaState *state)
{
    destroydtoa(state);
}