big.c

OTP是开放电信平台的简称

	    if (b2 <= a2)
		q0 = 1;
	    else {
		q0 = D_BASE-1;
		nsz++;
		rp--;
	    }
	}

	if ((nnsz = D_mulsub(rp, nsz, q0, y, yl, rp)) == 0) {
	    nnsz = Z_sub(r, rl, r);
	    if (nsz > (rl-nnsz))
		nnsz = nsz - (rl-nnsz);
	    else
		nnsz = 1;
	    r_signed = !r_signed;
	}

	if (nnsz == 1 && *rp == 0)
	    nnsz = 0;

	rp = rp - (yl-nnsz);
	rl -= (nsz-nnsz);
    } while (I_comp(r, rl, y, yl) >= 0);

    if (rl == 0)
	rl = 1;

    while(rl > 1 && r[rl-1] == 0) /* Remove "trailing zeroes" */
      --rl;

    if (r_signed && (rl > 1 || *r != 0))
	rl = I_sub(y, yl, r, rl, r);
    return rl;
}

/*
** Remove trailing digits from bitwise operations
** 32UPDATE
*/
static dsize_t I_btrail(digit_t* r0, digit_t* r, short sign)
{
    /* convert negative numbers to one complement */
    if (sign) {
	dsize_t rl;
	digit_t d;

	/* 1 remove all 0xffff words */
	do {
	    r--;
	} while((d = *r) == D_BASE-1 && r != r0);

	/* 2 complement high digit */
	if (d == D_BASE-1)
	    *r = 0;
	else {
	    digit_t prev_mask = 0;
	    digit_t mask = D_BASE >> 1;

	    while((d & mask) == mask) {
		prev_mask = mask;
		mask = (prev_mask >> 1) | (D_BASE>>1);
	    }
	    *r = ~d & ~prev_mask;
	}
	rl = (r - r0) + 1;
	while(r != r0) {
	    r--;
	    *r = ~*r;
	}
	return D_add(r0, rl, 1, r0);
    }

    do {
	r--;
    } while(*r == 0 && r != r0);
    return (r - r0) + 1;
}

/* 
** Bitwise and
** 32UPDATE
*/
static dsize_t I_band(digit_t* x, dsize_t xl, short xsgn,
		      digit_t* y, dsize_t yl, short ysgn, digit_t* r)
{
    digit_t* r0 = r;
    short sign = xsgn && ysgn;

    ASSERT(xl >= yl);

    xl -= yl;

    if (!xsgn) {
	if (!ysgn) {
	    while(yl--)
		*r++ = *x++ & *y++;
	}
	else {
	    digit_t b;
	    digit_t c;

	    DSUB(*y,1,b,c);
	    *r++ = *x++ & ~c;
	    y++;
	    yl--;
	    while(yl--) {
		DSUBb(*y,0,b,c);
		*r++ = *x++ & ~c;
		y++;
	    }
	    while (xl--) {
		*r++ = *x++;
	    }
	}
    }
    else {
	if (!ysgn) {
	    digit_t b;
	    digit_t c;

	    DSUB(*x,1,b,c);
	    *r = ~c & *y;
	    x++; y++; r++;
	    yl--;
	    while(yl--) {
		DSUBb(*x,0,b,c);
		*r++ = ~c & *y++;
		x++;
	    }
	}
	else {
	    digit_t b1, b2;
	    digit_t c1, c2;

	    DSUB(*x,1,b1,c1);
	    DSUB(*y,1,b2,c2);
	    *r++ = ~c1 & ~c2;
	    x++; y++;
	    yl--;
	    while(yl--) {
		DSUBb(*x,0,b1,c1);
		DSUBb(*y,0,b2,c2);
		*r++ = ~c1 & ~c2;
		x++; y++;
	    }
	    while(xl--)
		*r++ = ~*x++;
	}
    }
    return I_btrail(r0, r, sign);
}

/* 
 * Bitwise 'or'.
 */
static dsize_t
I_bor(digit_t* x, dsize_t xl, short xsgn, digit_t* y,
      dsize_t yl, short ysgn, digit_t* r)
{
    digit_t* r0 = r;
    short sign = xsgn || ysgn;

    ASSERT(xl >= yl);

    xl -= yl;

    if (!xsgn) {
	if (!ysgn) {
	    while(yl--)
		*r++ = *x++ | *y++;
	    while(xl--)
		*r++ = *x++;
	}
	else {
	    digit_t b;
	    digit_t c;

	    DSUB(*y,1,b,c);
	    *r++ = *x++ | ~c;
	    y++;
	    yl--;
	    while(yl--) {
		DSUBb(*y,0,b,c);
		*r++ = *x++ | ~c;
		y++;
	    }
	}
    }
    else {
	if (!ysgn) {
	    digit_t b;
	    digit_t c;

	    DSUB(*x,1,b,c);
	    *r++ = ~c | *y++;
	    x++;
	    yl--;
	    while(yl--) {
		DSUBb(*x,0,b,c);
		*r++ = ~c | *y++;
		x++;
	    }
	    while(xl--) {
		DSUBb(*x,0,b,c);
 		*r++ = ~c;
 		x++;
	    }
	}
	else {
	    digit_t b1, b2;
	    digit_t c1, c2;

	    DSUB(*x,1,b1,c1);
	    DSUB(*y,1,b2,c2);
	    *r++ = ~c1 | ~c2;
	    x++; y++;
	    yl--;
	    while(yl--) {
		DSUBb(*x,0,b1,c1);
		DSUBb(*y,0,b2,c2);
		*r++ = ~c1 | ~c2;
		x++; y++;
	    }
	}
    }
    return I_btrail(r0, r, sign);
}

/* 
** Bitwise xor
*/
static dsize_t I_bxor(digit_t* x, dsize_t xl, short xsgn,
		      digit_t* y, dsize_t yl, short ysgn, digit_t* r)
{
    digit_t* r0 = r;
    short sign = xsgn != ysgn;

    ASSERT(xl >= yl);

    xl -= yl;

    if (!xsgn) {
	if (!ysgn) {
	    while(yl--)
		*r++ = *x++ ^ *y++;
	    while(xl--)
		*r++ = *x++;
	}
	else {
	    digit_t b;
	    digit_t c;

	    DSUB(*y,1,b,c);
	    *r++ = *x++ ^ ~c;
	    y++;
	    yl--;
	    while(yl--) {
		DSUBb(*y,0,b,c);
		*r++ = *x++ ^ ~c;
		y++;
	    }
	    while(xl--)
		*r++ = ~*x++;
	}
    }
    else {
	if (!ysgn) {
	    digit_t b;
	    digit_t c;

	    DSUB(*x,1,b,c);
	    *r++ = ~c ^ *y++;
	    x++;
	    yl--;
	    while(yl--) {
		DSUBb(*x,0,b,c);
		*r++ = ~c ^ *y++;
		x++;
	    }
	    while(xl--)
		*r++ = ~*x++;
	}
	else {
	    digit_t b1, b2;
	    digit_t c1, c2;

	    DSUB(*x,1,b1,c1);
	    DSUB(*y,1,b2,c2);
	    *r++ = ~c1 ^ ~c2;
	    x++; y++;
	    yl--;
	    while(yl--) {
		DSUBb(*x,0,b1,c1);
		DSUBb(*y,0,b2,c2);
		*r++ = ~c1 ^ ~c2;
		x++; y++;
	    }
	    while(xl--) {
		*r++ = *x++;
	    }
	}
    }
    return I_btrail(r0, r, sign);
}

/*
** Bitwise not  simulated as
** bnot -X  == (X - 1)
** bnot +X  == -(X + 1)
** 32OK
*/
static dsize_t I_bnot(digit_t* x, dsize_t xl, short xsgn, digit_t* r)
{
    if (xsgn)
	return D_add(x, xl, 1, r);
    else
	return D_sub(x, xl, 1, r);
}

/*
** Arithmetic left shift or right
** 32UPDATE
*/
static dsize_t I_lshift(digit_t* x, dsize_t xl, Sint y, 
			short sign, digit_t* r)
{
    if (y == 0) {
	MOVE_DIGITS(r, x, xl);
	return xl;
    }
    else if (xl == 1 && *x == 0) {
	*r = 0;
	return 1;
    }
    else {
	long ay = (y < 0) ? -y : y;
	int bw = ay / D_EXP;
	int sw = ay % D_EXP;
	dsize_t rl;
	reg_t a = 0;

	if (y > 0) {		/* shift left */
	    rl = xl + bw + 1;

	    while(bw--)
		*r++ = 0;
	    while(xl--) {
		a = DHIGH(a) | ((reg_t) *x << sw);
		*r++ = DLOW(a);
		x++;
	    }
	    if (DHIGH(a) == 0)
		return rl-1;
	    *r = DHIGH(a);
	    return rl;
	}
	else {			/* shift right */
	    digit_t* r0 = r;
	    int rw = D_EXP - sw;
	    int add_one = 0;

	    if (xl <= bw) {
		if (sign)
		    *r = 1;
		else
		    *r = 0;
		return 1;
	    }

	    if (sign) {
		int zl = bw;
		digit_t* z = x;

		while(zl--) {
		    if (*z != 0) {
			add_one = 1;
			break;
		    }
		    z++;
		}
	    }

	    rl = xl - bw;
	    x += (xl-1);
	    r += (rl-1);
	    xl -= bw;
	    while(xl--) {
		a = DLOW2HIGH(a) | ((reg_t) *x << rw);
		*r-- = DHIGH(a);
		x--;
	    }

	    if (sign && DLOW(a) != 0)
		add_one = 1;

	    if (r[rl] == 0) {
		if (rl == 1) {
		    if (sign)
			r[1] = 1;
		    return 1;
		}
		rl--;
	    }
	    if (add_one)
		return D_add(r0, rl, 1, r0);
	    return rl;
	}
    }
}

/*
** Return log(x)/log(2)
** 32OK
*/
static int I_lg(digit_t* x, dsize_t xl)
{
    dsize_t sz = xl - 1;
    digit_t d = x[sz];

    sz *= D_EXP;
    while(d != 0) {
	d >>= 1;
	sz++;
    }
    return sz - 1;
}

/*
** Create bigint on heap if necessary. Like the previously existing
** make_small_or_big(), except for a HAlloc() instead of an
** ArithAlloc().
** NOTE: Only use erts_make_integer(), when order of heap fragments is
**       guaranteed to be correct.
*/
Eterm
erts_make_integer(Uint x, Process *p)
{
    Eterm* hp;
    if (IS_USMALL(0,x))
	return make_small(x);
    else {
	hp = HAlloc(p, BIG_UINT_HEAP_SIZE);
	return uint_to_big(x,hp);
    }
}

/*
** convert uint32 to bigint
** 32UPDATE (as macro?)
** (must only be used if x is to big to be stored as a small)
*/
Eterm uint_to_big(Uint x, Eterm *y)
{
    *y = make_pos_bignum_header(1);
    BIG_DIGIT(y, 0) = DLOW(x);
    BIG_DIGIT(y, 1) = DHIGH(x);
    return make_big(y);
}


/*
** convert signed int to bigint
** 32UPDATE (as macro?)
*/
Eterm small_to_big(Sint x, Eterm *y)
{
    if (x >= 0) {
	*y = make_pos_bignum_header(1);
    } else {
	x = -x;
	*y = make_neg_bignum_header(1);
    }
    BIG_DIGIT(y, 0) = DLOW(x);
    BIG_DIGIT(y, 1) = DHIGH(x);
    return make_big(y);
}

/*
** Convert a bignum to a double float
** 32OK XXX must check
*/
int
big_to_double(Eterm x, double* resp)
{
    double d = 0.0;
    Eterm* xp = big_val(x);
    dsize_t xl = BIG_SIZE(xp);
    digit_t* s = BIG_V(xp) + xl;
    short xsgn = BIG_SIGN(xp);
    volatile int *fpexnp = erts_get_current_fp_exception();
    __ERTS_SAVE_FP_EXCEPTION(fpexnp);

    __ERTS_FP_CHECK_INIT(fpexnp);
    while (xl--) {
	d = d * D_BASE + *--s;

	__ERTS_FP_ERROR(fpexnp, d, __ERTS_RESTORE_FP_EXCEPTION(fpexnp); return -1);
    }

    *resp = xsgn ? -d : d;
    __ERTS_FP_ERROR(fpexnp,*resp,;);
    __ERTS_RESTORE_FP_EXCEPTION(fpexnp);
    return 0;
}


/*
 ** Estimate the number of decimal digits (include sign)
 */
int big_decimal_estimate(Eterm x)
{
    Eterm* xp = big_val(x);
    int lg = I_lg(BIG_V(xp), BIG_SIZE(xp));
    int lg10 = ((lg+1)*28/93)+1;

    if (BIG_SIGN(xp)) lg10++;	/* add sign */
    return lg10+1;		/* add null */
}

/*
** Convert a bignum into a string of decimal numbers
*/

static void write_big(Eterm x, void (*write_func)(void *, char), void *arg)
{
    Eterm* xp = big_val(x);
    digit_t* dx = BIG_V(xp);
    dsize_t xl = BIG_SIZE(xp);
    short sign = BIG_SIGN(xp);
    digit_t rem;

    if (xl == 1 && *dx < D_DECIMAL_BASE) {
	rem = *dx;
	if (rem == 0)
	    (*write_func)(arg, '0');
	else {
	    while(rem) {
		(*write_func)(arg, (rem % 10) + '0');
		rem /= 10;
	    }
	}
    }
    else {
	digit_t* tmp  = (digit_t*) erts_alloc(ERTS_ALC_T_TMP,
					      sizeof(digit_t)*xl);
	dsize_t tmpl = xl;

	MOVE_DIGITS(tmp, dx, xl);

	while(1) {
	    tmpl = D_div(tmp, tmpl, D_DECIMAL_BASE, tmp, &rem);
	    if (tmpl == 1 && *tmp == 0) {
		while(rem) {
		    (*write_func)(arg, (rem % 10)+'0');
		    rem /= 10;
		}
		break;
	    }
	    else {
		int i = D_DECIMAL_EXP;
		while(i--) {
		    (*write_func)(arg, (rem % 10)+'0');
		    rem /= 10;
		}
	    }
	}
	erts_free(ERTS_ALC_T_TMP, (void *) tmp);
    }

    if (sign)
	(*write_func)(arg, '-');
}

struct big_list__ {
    Eterm *hp;
    Eterm res;
};

static void
write_list(void *arg, char c)
{
    struct big_list__ *blp = (struct big_list__ *) arg;
    blp->res = CONS(blp->hp, make_small(c), blp->res);
    blp->hp += 2;
}

Eterm erts_big_to_list(Eterm x, Eterm **hpp)
{
    struct big_list__ bl;
    bl.hp = *hpp;
    bl.res = NIL;
    write_big(x, write_list, (void *) &bl);
    *hpp = bl.hp;
    return bl.res;
}

static void
write_string(void *arg, char c)
{
    *(--(*((char **) arg))) = c;
}

char *erts_big_to_string(Eterm x, char *buf, Uint buf_sz)
{
    char *big_str = buf + buf_sz - 1;
    *big_str = '\0';
    write_big(x, write_string, (void *) &big_str);
    ASSERT(buf <= big_str && big_str <= buf + buf_sz - 1);
    return big_str;
}

/*