jsdtoa.c

java script test programing source code

        xi = *x;
        y = (xi & 0xffff) * m + carry;
        z = (xi >> 16) * m + (y >> 16);
        carry = z >> 16;
        *x++ = (z << 16) + (y & 0xffff);
#endif
    }
    while(++i < wds);
    if (carry) {
        if (wds >= b->maxwds) {
            b1 = Balloc(b->k+1);
            if (!b1) {
                Bfree(b);
                return NULL;
            }
            Bcopy(b1, b);
            Bfree(b);
            b = b1;
        }
        b->x[wds++] = (ULong)carry;
        b->wds = wds;
    }
    return b;
}

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

    x = (nd + 8) / 9;
    for(k = 0, y = 1; x > y; y <<= 1, k++) ;
    b = Balloc(k);
    if (!b)
        return NULL;
    b->x[0] = y9;
    b->wds = 1;

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


/* Return the number (0 through 32) of most significant zero bits in x. */
static int32 hi0bits(register ULong x)
{
    register int32 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;
}


/* Return the number (0 through 32) of least significant zero bits in y.
 * Also shift y to the right past these 0 through 32 zeros so that y's
 * least significant bit will be set unless y was originally zero. */
static int32 lo0bits(ULong *y)
{
    register int32 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;
}

/* Return a new Bigint with the given integer value, which must be nonnegative. */
static Bigint *i2b(int32 i)
{
    Bigint *b;

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

/* Return a newly allocated product of a and b. */
static Bigint *mult(CONST Bigint *a, CONST Bigint *b)
{
    CONST Bigint *t;
    Bigint *c;
    int32 k, wa, wb, wc;
    ULong y;
    ULong *xc, *xc0, *xce;
    CONST ULong *x, *xa, *xae, *xb, *xbe;
#ifdef ULLong
    ULLong carry, z;
#else
    ULong carry, z;
    ULong z2;
#endif

    if (a->wds < b->wds) {
        t = a;
        a = b;
        b = t;
    }
    k = a->k;
    wa = a->wds;
    wb = b->wds;
    wc = wa + wb;
    if (wc > a->maxwds)
        k++;
    c = Balloc(k);
    if (!c)
        return NULL;
    for(xc = c->x, xce = xc + wc; xc < xce; xc++)
        *xc = 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++) != 0) {
            x = xa;
            xc = xc0;
            carry = 0;
            do {
                z = *x++ * (ULLong)y + *xc + carry;
                carry = z >> 32;
                *xc++ = (ULong)(z & 0xffffffffUL);
                }
                while(x < xae);
            *xc = (ULong)carry;
            }
        }
#else
    for(; xb < xbe; xb++, xc0++) {
        if ((y = *xb & 0xffff) != 0) {
            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) != 0) {
            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;
        }
    }
#endif
    for(xc0 = c->x, xc = xc0 + wc; wc > 0 && !*--xc; --wc) ;
    c->wds = wc;
    return c;
}

/*
 * 'p5s' points to a linked list of Bigints that are powers of 5.
 * This list grows on demand, and it can only grow: it won't change
 * in any other way.  So if we read 'p5s' or the 'next' field of
 * some Bigint on the list, and it is not NULL, we know it won't
 * change to NULL or some other value.  Only when the value of
 * 'p5s' or 'next' is NULL do we need to acquire the lock and add
 * a new Bigint to the list.
 */

static Bigint *p5s;

#ifdef JS_THREADSAFE
static PRLock *p5s_lock;
#endif

/* Return b * 5^k.  Deallocate the old b.  k must be nonnegative. */
/* NOTE: old b is deallocated on memory failure. */
static Bigint *pow5mult(Bigint *b, int32 k)
{
    Bigint *b1, *p5, *p51;
    int32 i;
    static CONST int32 p05[3] = { 5, 25, 125 };

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

    if (!(k >>= 2))
        return b;
    if (!(p5 = p5s)) {
#ifdef JS_THREADSAFE
        /*
         * We take great care to not call i2b() and Bfree()
         * while holding the lock.
         */
        Bigint *wasted_effort = NULL;
        p5 = i2b(625);
        if (!p5) {
            Bfree(b);
            return NULL;
        }
        /* lock and check again */
        PR_Lock(p5s_lock);
        if (!p5s) {
            /* first time */
            p5s = p5;
            p5->next = 0;
        } else {
            /* some other thread just beat us */
            wasted_effort = p5;
            p5 = p5s;
        }
        PR_Unlock(p5s_lock);
        if (wasted_effort) {
            Bfree(wasted_effort);
        }
#else
        /* first time */
        p5 = p5s = i2b(625);
        if (!p5) {
            Bfree(b);
            return NULL;
        }
        p5->next = 0;
#endif
    }
    for(;;) {
        if (k & 1) {
            b1 = mult(b, p5);
            Bfree(b);
            if (!b1)
                return NULL;
            b = b1;
        }
        if (!(k >>= 1))
            break;
        if (!(p51 = p5->next)) {
#ifdef JS_THREADSAFE
            Bigint *wasted_effort = NULL;
            p51 = mult(p5, p5);
            if (!p51) {
                Bfree(b);
                return NULL;
            }
            PR_Lock(p5s_lock);
            if (!p5->next) {
                p5->next = p51;
                p51->next = 0;
            } else {
                wasted_effort = p51;
                p51 = p5->next;
            }
            PR_Unlock(p5s_lock);
            if (wasted_effort) {
                Bfree(wasted_effort);
            }
#else
            p51 = mult(p5,p5);
            if (!p51) {
                Bfree(b);
                return NULL;
            }
            p51->next = 0;
            p5->next = p51;
#endif
        }
        p5 = p51;
    }
    return b;
}

/* Return b * 2^k.  Deallocate the old b.  k must be nonnegative.
 * NOTE: on memory failure, old b is deallocated. */
static Bigint *lshift(Bigint *b, int32 k)
{
    int32 i, k1, n, n1;
    Bigint *b1;
    ULong *x, *x1, *xe, z;

    n = k >> 5;
    k1 = b->k;
    n1 = n + b->wds + 1;
    for(i = b->maxwds; n1 > i; i <<= 1)
        k1++;
    b1 = Balloc(k1);
    if (!b1)
        goto done;
    x1 = b1->x;
    for(i = 0; i < n; i++)
        *x1++ = 0;
    x = b->x;
    xe = x + b->wds;
    if (k &= 0x1f) {
        k1 = 32 - k;
        z = 0;
        do {
            *x1++ = *x << k | z;
            z = *x++ >> k1;
        }
        while(x < xe);
        if ((*x1 = z) != 0)
            ++n1;
    }
    else do
        *x1++ = *x++;
         while(x < xe);
    b1->wds = n1 - 1;
done:
    Bfree(b);
    return b1;
}

/* Return -1, 0, or 1 depending on whether a<b, a==b, or a>b, respectively. */
static int32 cmp(Bigint *a, Bigint *b)
{
    ULong *xa, *xa0, *xb, *xb0;
    int32 i, j;

    i = a->wds;
    j = b->wds;
#ifdef DEBUG
    if (i > 1 && !a->x[i-1])
        Bug("cmp called with a->x[a->wds-1] == 0");
    if (j > 1 && !b->x[j-1])
        Bug("cmp called with b->x[b->wds-1] == 0");
#endif
    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;
    int32 i, wa, wb;
    ULong *xa, *xae, *xb, *xbe, *xc;
#ifdef ULLong
    ULLong borrow, y;
#else
    ULong borrow, y;
    ULong z;
#endif

    i = cmp(a,b);
    if (!i) {
        c = Balloc(0);
        if (!c)
            return NULL;
        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);
    if (!c)
        return NULL;
    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 & 1UL;
        *xc++ = (ULong)(y & 0xffffffffUL);
        }
        while(xb < xbe);
    while(xa < xae) {
        y = *xa++ - borrow;
        borrow = y >> 32 & 1UL;
        *xc++ = (ULong)(y & 0xffffffffUL);
        }
#else
    do {
        y = (*xa & 0xffff) - (*xb & 0xffff) - borrow;
        borrow = (y & 0x10000) >> 16;