big.c

OTP是开放电信平台的简称

** Normalize a bignum given thing pointer length in digits and a sign
** patch zero if odd length
** 32UPDATE  in 32 bit version no patch is needed
*/
static Eterm big_norm(Eterm *x, dsize_t xl, short sign)
{
    Uint arity;

    if (xl == 1) {
	Uint y = BIG_DIGIT(x, 0);

	if (D_EXP < SMALL_BITS || IS_USMALL(sign, y)) {
	    if (sign)
		return make_small(-((Sint)y));
	    else
		return make_small(y);
	}
    }
    else if (xl == 2) {
	Uint y = BIG_DIGIT(x,0) + BIG_DIGIT(x,1)*D_BASE;

	if (IS_USMALL(sign, y)) {
	    if (sign)
		return make_small(-((Sint)y));
	    else
		return make_small(y);
	}
    }

    /* __alpha__: This was fixed */
    if ((arity = BIG_NEED_SIZE(xl)-1) > BIG_ARITY_MAX)
      return NIL;  /* signal error (too big) */

    if (sign) {
      *x = make_neg_bignum_header(arity);
    }
    else {
      *x = make_pos_bignum_header(arity);
    }

    /* Its VERY important to patch a zero if odd number of digits! */
    switch(xl & 1) {
    case 0:
      break;
    case 1:
      BIG_DIGIT(x, xl) = 0;
      break;
    }

    return make_big(x);
}

/*
** Compare bignums
** 32OK
*/
int big_comp(Eterm x, Eterm y)
{
    Eterm* xp = big_val(x);
    Eterm* yp = big_val(y);

    if (BIG_SIGN(xp) == BIG_SIGN(yp)) {
	int c = I_comp(BIG_V(xp), BIG_SIZE(xp), BIG_V(yp), BIG_SIZE(yp));
	if (BIG_SIGN(xp))
	    return -c;
	else
	    return c;
    }
    else
	return BIG_SIGN(xp) ? -1 : 1;
}

/*
** Unsigned compare
** 32OK
*/
int big_ucomp(Eterm x, Eterm y)
{
    Eterm* xp = big_val(x);
    Eterm* yp = big_val(y);

    return I_comp(BIG_V(xp), BIG_SIZE(xp), BIG_V(yp), BIG_SIZE(yp));
}

/*
** Check if bytes in xp corresponds to a bignum y
** 32UPDATE
*/
#if 0	/* XXX: unused */
int bytes_eq_big(byte *xp, dsize_t xsz, int xsgn, Eterm y)
{
    if (is_big(y)) {
	Eterm* yp = big_val(y);

	dsize_t ysz = big_bytes(y); /* ysz in bytes */
	short sgny = BIG_SIGN(yp);
	digit_t* ywp = BIG_V(yp);
	digit_t d;

	if (sgny != xsgn) return 0;
	if (xsz != ysz) return 0;
	while (xsz >= 2) {
	    d = xp[0] | (xp[1] << 8);
	    if (d != *ywp)
		return 0;
	    ywp++;
	    xp += 2;
	    xsz -= 2;
	}
	if (xsz == 1)
	{
	    d = *xp;
	    if (d != *ywp) return 0;
	}
	return 1;
    }
    else if (is_small(y)) {
	Sint yv = signed_val(y);
	Uint xv;

	if (xsz > 4) return 0;
	if ((yv < 0) != xsgn) return 0;

	switch(xsz) {
	case 1:
	    xv = *xp;
	    break;
	case 2:
	    xv = xp[0] | (xp[1] << 8);
	    break;
	case 3:
	    xv = xp[0] | (xp[1] << 8) | (xp[2] << 16);
	    break;
	case 4:
	    xv = xp[0] | (xp[1] << 8) | (xp[2] << 16) | (xp[3] << 24);
	    break;
	default:		/* Silence compiler warning. */
	    xv = 0;
	    break;
	}
	if (!IS_USMALL(xsgn, xv)) return 0;
	if (yv < 0)
	    return (-yv == xv);
	else
	    return (yv == xv);
    }
    return 0;
}
#endif	/* 0 */

/*
** Return number of bytes in the bignum
** 32UPDATE
*/
dsize_t big_bytes(Eterm x)
{
    Eterm* xp = big_val(x);

    dsize_t sz = BIG_SIZE(xp);
    digit_t d = BIG_DIGIT(xp, sz-1);

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

/*
** Load a bignum from bytes
** xsz is the number of bytes in xp
** 32UPDATE
*/
Eterm bytes_to_big(byte *xp, dsize_t xsz, int xsgn, Eterm *r)
{
    digit_t* rwp = BIG_V(r);
    dsize_t rsz = 0;
    digit_t d;
    int i;

    while(xsz >= sizeof(digit_t)) {
	d = 0;
	for(i = sizeof(digit_t); --i >= 0;)
	    d = (d << 8) | xp[i];
	*rwp = d;
	rwp++;
	xsz -= sizeof(digit_t);
	xp += sizeof(digit_t);
	rsz++;
    }

    if (xsz > 0) {
	d = 0;
	for(i = xsz; --i >= 0;)
	    d = (d << 8) | xp[i];
	*rwp = d;
	rwp++;
	rsz++;
    }
    return big_norm(r, rsz, (short) xsgn);
}

/*
** Store digits in the array of bytes pointed to by p
** 32UPDATE
*/
byte* big_to_bytes(Eterm x, byte *p)
{
    digit_t* xr = big_v(x);
    dsize_t  xl = big_size(x);
    digit_t d;
    int i;

    while(xl > 1) {
	d = *xr;
	xr++;
	for(i = 0; i < sizeof(digit_t); ++i) {
	    p[i] = d & 0xff;
	    d >>= 8;
	}
	p += sizeof(digit_t);
	xl--;
    }
    d = *xr;
    do {
	*p++ = d & 0xff;
	d >>= 8;
    } while (d != 0);
    return p;
}

/*
 * Converts a positive term (small or bignum) to an Uint.
 *
 * Fails returning 0 if the term is neither a small nor a bignum,
 * if it's negative, or the big number does not fit in an Uint.
 * Otherwise returns a non-zero value.
 */

int
term_to_Uint(Eterm term, Uint *up)
{
    if (is_small(term)) {
	Sint i = signed_val(term);
	if (i < 0) {
	    return 0;
	}
	*up = (Uint) i;
	return 1;
    } else if (is_big(term)) {
	digit_t* xr = big_v(term);
	dsize_t  xl = big_size(term);
	Uint uval = 0;
	int n = 0;
	
	if (big_sign(term) || xl*D_EXP > sizeof(Uint)*CHAR_BIT) {
	    return 0;
	}
	while (xl-- > 0) {
	    uval |= ((Uint)(*xr++)) << n;
	    n += D_EXP;
	}
	*up = uval;
	return 1;
    } else {
	return 0;
    }
}

int term_to_Sint(Eterm term, Sint *sp)
{
    if (is_small(term)) {
	*sp = signed_val(term);
	return 1;
    } else if (is_big(term)) {
	digit_t* xr = big_v(term);
	dsize_t xl = big_size(term);
	int sign = big_sign(term);
	Uint uval = 0;
	int n = 0;

	if (xl*D_EXP > sizeof(Uint)*CHAR_BIT) {
	    return 0;
	}
	while (xl-- > 0) {
	    uval |= ((Uint)(*xr++)) << n;
	    n += D_EXP;
	}
	if (sign) {
	    uval = -uval;
	    if ((Sint)uval > 0)
		return 0;
	} else {
	    if ((Sint)uval < 0)
		return 0;
	}
	*sp = uval;
	return 1;
    } else {
	return 0;
    }
}

/*
** Add and subtract
** 32OK
*/
static Eterm B_plus_minus(digit_t *x, dsize_t xl, short xsgn, 
			  digit_t *y, dsize_t yl, short ysgn, Eterm *r)
{
    if (xsgn == ysgn) {
	if (xl > yl)
	    return big_norm(r, I_add(x,xl,y,yl,BIG_V(r)), xsgn);
	else
	    return big_norm(r, I_add(y,yl,x,xl,BIG_V(r)), xsgn);
    }
    else {
	int comp = I_comp(x, xl, y, yl);
	if (comp == 0)
	    return make_small(0);
	else if (comp > 0)
	    return big_norm(r, I_sub(x,xl,y,yl,BIG_V(r)), xsgn);
	else
	    return big_norm(r, I_sub(y,yl,x,xl,BIG_V(r)), ysgn);
    }
}

/*
** Add bignums
** 32OK
*/
Eterm big_plus(Eterm x, Eterm y, Eterm *r)
{
    Eterm* xp = big_val(x);
    Eterm* yp = big_val(y);

    return B_plus_minus(BIG_V(xp),BIG_SIZE(xp),(short) BIG_SIGN(xp),
			BIG_V(yp),BIG_SIZE(yp),(short) BIG_SIGN(yp), r);
}

/*
** Subtract bignums
** 32OK
*/

Eterm big_minus(Eterm x, Eterm y, Eterm *r)
{
    Eterm* xp = big_val(x);
    Eterm* yp = big_val(y);

    return B_plus_minus(BIG_V(xp),BIG_SIZE(xp),(short) BIG_SIGN(xp),
			BIG_V(yp),BIG_SIZE(yp),(short) !BIG_SIGN(yp), r);
}

/*
** Subtract a digit from big number
*/
Eterm big_minus_small(Eterm x, Eterm y, Eterm *r)
{
    Eterm* xp = big_val(x);

    if (BIG_SIGN(xp))
	return big_norm(r, D_add(BIG_V(xp),BIG_SIZE(xp), (digit_t) y, BIG_V(r)), 
			(short) BIG_SIGN(xp));
    else
	return big_norm(r, D_sub(BIG_V(xp),BIG_SIZE(xp), (digit_t) y, BIG_V(r)), 
			(short) BIG_SIGN(xp));
}

/*
** Multiply bignums
** 32OK
*/

Eterm big_times(Eterm x, Eterm y, Eterm *r)
{
    Eterm* xp = big_val(x);
    Eterm* yp = big_val(y);

    short sign = BIG_SIGN(xp) != BIG_SIGN(yp);
    dsize_t xsz = BIG_SIZE(xp);
    dsize_t ysz = BIG_SIZE(yp);
    dsize_t rsz;

    if (ysz == 1)
	rsz = D_mul(BIG_V(xp), xsz, BIG_DIGIT(yp, 0), BIG_V(r));
    else if (xsz == 1)
	rsz = D_mul(BIG_V(yp), ysz, BIG_DIGIT(xp, 0), BIG_V(r));
    else if (xp == yp) {
	ZERO_DIGITS(BIG_V(r), xsz+1);
	rsz = I_sqr(BIG_V(xp), xsz, BIG_V(r));
    }
    else if (xsz >= ysz) {
	ZERO_DIGITS(BIG_V(r), xsz);
	rsz = I_mul(BIG_V(xp), xsz, BIG_V(yp), ysz, BIG_V(r));
    }
    else {
	ZERO_DIGITS(BIG_V(r), ysz);
	rsz = I_mul(BIG_V(yp), ysz, BIG_V(xp), xsz, BIG_V(r));
    }
    return big_norm(r, rsz, sign);
}


/* 
** Divide bignums
** 32UPDATE?
*/

Eterm big_div(Eterm x, Eterm y, Eterm *q)
{
    Eterm* xp = big_val(x);
    Eterm* yp = big_val(y);

    short sign = BIG_SIGN(xp) != BIG_SIGN(yp);
    dsize_t xsz = BIG_SIZE(xp);
    dsize_t ysz = BIG_SIZE(yp);
    dsize_t qsz;

    if (ysz == 1) {
	digit_t rem;
	qsz = D_div(BIG_V(xp), xsz, BIG_DIGIT(yp,0), BIG_V(q), &rem);
    }
    else {
	Eterm* remp;
	dsize_t rem_sz;

	qsz = xsz - ysz + 1;
	remp = q + BIG_NEED_SIZE(qsz);
	qsz = I_div(BIG_V(xp), xsz, BIG_V(yp), ysz, BIG_V(q), BIG_V(remp),
		    &rem_sz);
    }
    return big_norm(q, qsz, sign);
}

/*
** Remainder
** 32UPDATE?
*/
Eterm big_rem(Eterm x, Eterm y, Eterm *r)
{
    Eterm* xp = big_val(x);
    Eterm* yp = big_val(y);
    short sign = BIG_SIGN(xp);
    dsize_t xsz = BIG_SIZE(xp);
    dsize_t ysz = BIG_SIZE(yp);

    if (ysz == 1) {
	digit_t rem;
	rem = D_rem(BIG_V(xp), xsz, BIG_DIGIT(yp,0));
	if (sign)
	    return make_small(-(Sint)rem);
	else
	    return make_small(rem);
    }
    else {
	dsize_t rsz = I_rem(BIG_V(xp), xsz, BIG_V(yp), ysz, BIG_V(r));
	return big_norm(r, rsz, sign);
    }
}

Eterm big_neg(Eterm x, Eterm *r)
{
    Eterm* xp = big_val(x);
    dsize_t xsz = BIG_SIZE(xp);
    short xsgn = BIG_SIGN(xp);
    
    MOVE_DIGITS(BIG_V(r), BIG_V(xp), xsz);
    return big_norm(r, xsz, (short) !xsgn);
}

Eterm big_band(Eterm x, Eterm y, Eterm *r)
{
    Eterm* xp = big_val(x);
    Eterm* yp = big_val(y);

    short xsgn = BIG_SIGN(xp);
    short ysgn = BIG_SIGN(yp);
    short sign = xsgn && ysgn;
    dsize_t xsz = BIG_SIZE(xp);
    dsize_t ysz = BIG_SIZE(yp);

    if (xsz >= ysz)
	return big_norm(r,I_band(BIG_V(xp),xsz,xsgn,
				 BIG_V(yp),ysz,ysgn,
				 BIG_V(r)),sign);
    else
	return big_norm(r,I_band(BIG_V(yp),ysz,ysgn,
				 BIG_V(xp),xsz,xsgn,
				 BIG_V(r)),sign);
}


Eterm big_bor(Eterm x, Eterm y, Eterm *r)
{
    Eterm* xp = big_val(x);
    Eterm* yp = big_val(y);
    short xsgn = BIG_SIGN(xp);
    short ysgn = BIG_SIGN(yp);
    short sign = (xsgn || ysgn);
    dsize_t xsz = BIG_SIZE(xp);
    dsize_t ysz = BIG_SIZE(yp);

    if (xsz >= ysz)
	return big_norm(r,I_bor(BIG_V(xp),xsz,xsgn,
				BIG_V(yp),ysz,ysgn,
				BIG_V(r)),sign);
    else
	return big_norm(r,I_bor(BIG_V(yp),ysz,ysgn,
				BIG_V(xp),xsz,xsgn,
				BIG_V(r)),sign);
}


Eterm big_bxor(Eterm x, Eterm y, Eterm *r)
{
    Eterm* xp = big_val(x);
    Eterm* yp = big_val(y);
    short xsgn = BIG_SIGN(xp);
    short ysgn = BIG_SIGN(yp);
    short sign = (xsgn != ysgn);
    dsize_t xsz = BIG_SIZE(xp);
    dsize_t ysz = BIG_SIZE(yp);

    if (xsz >= ysz)
	return big_norm(r,I_bxor(BIG_V(xp),xsz,xsgn,
				 BIG_V(yp),ysz,ysgn,
				 BIG_V(r)),sign);
    else
	return big_norm(r,I_bxor(BIG_V(yp),ysz,ysgn,
				 BIG_V(xp),xsz,xsgn,
				 BIG_V(r)),sign);
}

Eterm big_bnot(Eterm x,  Eterm *r)
{
    Eterm* xp = big_val(x);
    short sign = !BIG_SIGN(xp);
    dsize_t xsz = BIG_SIZE(xp);

    return big_norm(r, I_bnot(BIG_V(xp), xsz, sign, BIG_V(r)), sign);
}

Eterm big_lshift(Eterm x, Sint y, Eterm *r)
{
    Eterm* xp = big_val(x);
    short sign = BIG_SIGN(xp);
    dsize_t xsz = BIG_SIZE(xp);

    return big_norm(r, I_lshift(BIG_V(xp), xsz, y, sign, BIG_V(r)), sign);
}


/* add unsigned small int y to x */

Eterm big_plus_small(Eterm x, Uint y, Eterm *r)
{
    Eterm* xp = big_val(x);

    if (BIG_SIGN(xp))
	return big_norm(r, D_sub(BIG_V(xp),BIG_SIZE(xp), (digit_t) y, 
				 BIG_V(r)), (short) BIG_SIGN(xp));
    else
	return big_norm(r, D_add(BIG_V(xp),BIG_SIZE(xp), (digit_t) y, 
				 BIG_V(r)), (short) BIG_SIGN(xp));
}

Eterm big_times_small(Eterm x, Uint y, Eterm *r)
{
    Eterm* xp = big_val(x);

    return big_norm(r, D_mul(BIG_V(xp),BIG_SIZE(xp), (digit_t) y, 
			     BIG_V(r)), (short) BIG_SIGN(xp));
}

/*
** Expects the big to fit.
*/
Uint32 big_to_uint32(Eterm b)
{
    Uint u;
    if (!term_to_Uint(b, &u)) {
	ASSERT(0);
        return 0;
    }
    return u;
}

/*
 * Check if a fixnum or bignum equals 2^32.
 */
int term_equals_2pow32(Eterm x)
{
    if (sizeof(Uint) > 4) {
	Uint u;
	if (!term_to_Uint(x, &u))
	    return 0;
	return (u & 0xFFFFFFFF) == 0 && ((u >> 16) >> 16) == 1;
    } else {
	Eterm *bp;
	if (!is_big(x))
	    return 0;
	bp = big_val(x);
	if (BIG_SIZE(bp) == 3 && !BIG_DIGIT(bp,0) && !BIG_DIGIT(bp,1) &&
	    BIG_DIGIT(bp,2) == 1)
	    return 1;
	return 0;
    }
}