mp.c

纯C数据结构

	if (sx) {
		XP_neg(nbytes, tmp[0], x, 1);
		x = tmp[0];
		x[nbytes-1] &= msb;
	}
	if (sy) {
		XP_neg(nbytes, tmp[1], y, 1);
		y = tmp[1];
		y[nbytes-1] &= msb;
	} else {
				    	memcpy(tmp[1], y, nbytes);
				    	y = tmp[1];
				    }
	if (!XP_div(nbytes, tmp[2], x, nbytes, y, z, tmp[3]))
		RAISE(MP_Dividebyzero);
	if (sx != sy) {
		if (!iszero(z))
			XP_sub(nbytes, z, y, z, 0);
	} else if (sx && sign(tmp[2]))
		RAISE(MP_Overflow);
	return z;
}
T MP_addui(T z, T x, unsigned long y) {
	assert(x); assert(z);
	if (y < BASE) {
		int carry = XP_sum(nbytes, z, x, y);
		carry |= z[nbytes-1]&~msb;
		z[nbytes-1] &= msb;
		if (carry)
			RAISE(MP_Overflow);
	} else if (applyu(MP_addu, z, x, y))
		RAISE(MP_Overflow);
	return z;
}
T MP_subui(T z, T x, unsigned long y) {
	assert(x); assert(z);
	if (y < BASE) {
		int borrow = XP_diff(nbytes, z, x, y);
		borrow |= z[nbytes-1]&~msb;
		z[nbytes-1] &= msb;
		if (borrow)
			RAISE(MP_Overflow);
	} else if (applyu(MP_subu, z, x, y))
		RAISE(MP_Overflow);
	return z;
}
T MP_mului(T z, T x, unsigned long y) {
	assert(x); assert(z);
	if (y < BASE) {
		int carry = XP_product(nbytes, z, x, y);
		carry |= z[nbytes-1]&~msb;
		z[nbytes-1] &= msb;
		if (carry)
			RAISE(MP_Overflow);
		if (nbits < 8 && y >= (1U<<nbits))
			RAISE(MP_Overflow);
	} else if (applyu(MP_mulu, z, x, y))
		RAISE(MP_Overflow);
	return z;
}
T MP_divui(T z, T x, unsigned long y) {
	assert(x); assert(z);
	if (y == 0)
		RAISE(MP_Dividebyzero);
	else if (y < BASE) {
		XP_quotient(nbytes, z, x, y);
		if (nbits < 8 && y >= (1U<<nbits))
			RAISE(MP_Overflow);
	} else if (applyu(MP_divu, z, x, y))
		RAISE(MP_Overflow);
	return z;
}
unsigned long MP_modui(T x, unsigned long y) {
	assert(x);
	if (y == 0)
		RAISE(MP_Dividebyzero);
	else if (y < BASE) {
		int r = XP_quotient(nbytes, tmp[2], x, y);
		if (nbits < 8 && y >= (1U<<nbits))
			RAISE(MP_Overflow);
		return r;
	} else if (applyu(MP_modu, tmp[2], x, y))
		RAISE(MP_Overflow);
	return XP_toint(nbytes, tmp[2]);
}
T MP_addi(T z, T x, long y) {
	assert(x); assert(z);
	if (-BASE < y && y < BASE) {
		int sx = sign(x), sy = y < 0;
		if (sy)
			XP_diff(nbytes, z, x, -y);
		else
			XP_sum (nbytes, z, x,  y);
		z[nbytes-1] &= msb;
		if (sx == sy && sy != sign(z))
			RAISE(MP_Overflow);
		if (nbits < 8
		&& (y < -(1<<(nbits-1)) || y >= (1<<(nbits-1))))
			RAISE(MP_Overflow);
	} else if (apply(MP_add, z, x, y))
		RAISE(MP_Overflow);
	return z;
}
T MP_subi(T z, T x, long y) {
	assert(x); assert(z);
	if (-BASE < y && y < BASE) {
		int sx = sign(x), sy = y < 0;
		if (sy)
			XP_sum (nbytes, z, x, -y);
		else
			XP_diff(nbytes, z, x,  y);
		z[nbytes-1] &= msb;
		if (sx != sy && sy == sign(z))
			RAISE(MP_Overflow);
		if (nbits < 8
		&& (y < -(1<<(nbits-1)) || y >= (1<<(nbits-1))))
			RAISE(MP_Overflow);
	} else if (apply(MP_sub, z, x, y))
		RAISE(MP_Overflow);
	return z;
}
T MP_muli(T z, T x, long y) {
	assert(x); assert(z);
	if (-BASE < y && y < BASE) {
		int sx = sign(x), sy = y < 0;
		if (sx) {
			XP_neg(nbytes, tmp[0], x, 1);
			x = tmp[0];
			x[nbytes-1] &= msb;
		}
		XP_product(nbytes, z, x, sy ? -y : y);
		if (sx != sy)
			XP_neg(nbytes, z, x, 1);
		z[nbytes-1] &= msb;
		if (sx == sy && sign(z))
			RAISE(MP_Overflow);
		if (nbits < 8
		&& (y < -(1<<(nbits-1)) || y >= (1<<(nbits-1))))
			RAISE(MP_Overflow);
	} else if (apply(MP_mul, z, x, y))
		RAISE(MP_Overflow);
	return z;
}
T MP_divi(T z, T x, long y) {
	assert(x); assert(z);
	if (y == 0)
		RAISE(MP_Dividebyzero);
	else if (-BASE < y && y < BASE) {
		int r;
		int sx = sign(x), sy = y < 0;
if (sx) {
	XP_neg(nbytes, tmp[0], x, 1);
	x = tmp[0];
	x[nbytes-1] &= msb;
}
		r = XP_quotient(nbytes, z, x, sy ? -y : y);
		if (sx != sy) {
			XP_neg(nbytes, z, z, 1);
			if (r != 0) {
				XP_diff(nbytes, z, z, 1);
				r = y - r;
			}
			z[nbytes-1] &= msb;
		} else if (sx && sign(z))
			RAISE(MP_Overflow);
		if (nbits < 8
		&& (y < -(1<<(nbits-1)) || y >= (1<<(nbits-1))))
			RAISE(MP_Overflow);
	} else if (apply(MP_div, z, x, y))
		RAISE(MP_Overflow);
	return z;
}
long MP_modi(T x, long y) {
	assert(x);
	if (y == 0)
		RAISE(MP_Dividebyzero);
	else if (-BASE < y && y < BASE) {
		T z = tmp[2];
		int r;
		int sx = sign(x), sy = y < 0;
if (sx) {
	XP_neg(nbytes, tmp[0], x, 1);
	x = tmp[0];
	x[nbytes-1] &= msb;
}
		r = XP_quotient(nbytes, z, x, sy ? -y : y);
		if (sx != sy) {
			XP_neg(nbytes, z, z, 1);
			if (r != 0) {
				XP_diff(nbytes, z, z, 1);
				r = y - r;
			}
			z[nbytes-1] &= msb;
		} else if (sx && sign(z))
			RAISE(MP_Overflow);
		if (nbits < 8
		&& (y < -(1<<(nbits-1)) || y >= (1<<(nbits-1))))
			RAISE(MP_Overflow);
		return r;
	} else if (apply(MP_mod, tmp[2], x, y))
		RAISE(MP_Overflow);
	return MP_toint(tmp[2]);
}
int MP_cmpu(T x, T y) {
	assert(x);
	assert(y);
	return XP_cmp(nbytes, x, y);
}
int MP_cmp(T x, T y) {
	int sx, sy;
	assert(x);
	assert(y);
	sx = sign(x);
	sy = sign(y);
	if (sx != sy)
		return sy - sx;
	else
		return XP_cmp(nbytes, x, y);
}
int MP_cmpui(T x, unsigned long y) {
	assert(x);
	if ((int)sizeof y >= nbytes) {
		unsigned long v = XP_toint(nbytes, x);
		if (v < y)
			return -1;
		else if (v > y)
			return 1;
		else
			return 0;
	} else {
		XP_fromint(nbytes, tmp[2], y);
		return XP_cmp(nbytes, x, tmp[2]);
	}
}
int MP_cmpi(T x, long y) {
	int sx, sy = y < 0;
	assert(x);
	sx = sign(x);
	if (sx != sy)
		return sy - sx;
	else if ((int)sizeof y >= nbytes) {
		long v = MP_toint(x);
		if (v < y)
			return -1;
		else if (v > y)
			return 1;
		else
			return 0;
	} else {
		MP_fromint(tmp[2], y);
		return XP_cmp(nbytes, x, tmp[2]);
	}
}
T MP_and(T z, T x, T y) { bitop(&); }
T MP_or (T z, T x, T y) { bitop(|); }
T MP_xor(T z, T x, T y) { bitop(^); }
T MP_not(T z, T x) {
	int i;
	assert(x); assert(z);
	for (i = 0; i < nbytes; i++)
		z[i] = ~x[i];
	z[nbytes-1] &= msb;
	return z;
}
T MP_andi(T z, T x, unsigned long y) { bitopi(MP_and); }
T MP_ori (T z, T x, unsigned long y) { bitopi(MP_or);  }
T MP_xori(T z, T x, unsigned long y) { bitopi(MP_xor); }
T MP_lshift(T z, T x, int s) { shft(0, XP_lshift); }
T MP_rshift(T z, T x, int s) { shft(0, XP_rshift); }
T MP_ashift(T z, T x, int s) { shft(sign(x),XP_rshift); }
T MP_fromstr(T z, const char *str, int base, char **end){
	int carry;
	assert(z);
	memset(z, '\0', nbytes);
	carry = XP_fromstr(nbytes, z, str, base, end);
	carry |= z[nbytes-1]&~msb;
	z[nbytes-1] &= msb;
	if (carry)
		RAISE(MP_Overflow);
	return z;
}
char *MP_tostr(char *str, int size, int base, T x) {
	assert(x);
	assert(base >= 2 && base <= 36);
	assert(str == NULL || size > 1);
	if (str == NULL) {
		{
			int k;
			for (k = 5; (1<<k) > base; k--)
				;
			size = nbits/k + 1 + 1;
		}
		str = ALLOC(size);
	}
	memcpy(tmp[1], x, nbytes);
	XP_tostr(str, size, base, nbytes, tmp[1]);
	return str;
}
void MP_fmtu(int code, va_list *app,
	int put(int c, void *cl), void *cl,
	unsigned char flags[], int width, int precision) {
	T x;
	char *buf;
	assert(app && *app && flags);
	x = va_arg(*app, T);
	assert(x);
	buf = MP_tostr(NULL, 0, va_arg(*app, int), x);
	Fmt_putd(buf, strlen(buf), put, cl, flags,
		width, precision);
	FREE(&buf);
}
void MP_fmt(int code, va_list *app,
	int put(int c, void *cl), void *cl,
	unsigned char flags[], int width, int precision) {
	T x;
	int base, size, sx;
	char *buf;
	assert(app && *app && flags);
	x = va_arg(*app, T);
	assert(x);
	base = va_arg(*app, int);
	sx = sign(x);
	if (sx) {
		XP_neg(nbytes, tmp[0], x, 1);
		x = tmp[0];
		x[nbytes-1] &= msb;
	}
	{
		int k;
		for (k = 5; (1<<k) > base; k--)
			;
		size = nbits/k + 1 + 1;
	}
	buf = ALLOC(size+1);
	if (sx) {
		buf[0] = '-';
		MP_tostr(buf + 1, size, base, x);
	} else
		MP_tostr(buf, size + 1, base, x);
	Fmt_putd(buf, strlen(buf), put, cl, flags,
		width, precision);
	FREE(&buf);
}
static char rcsid[] = "$RCSfile: RCS/mp.doc,v $ $Revision: 1.8 $";