mpzmodule.c

python s60 1.4.5版本的源代码

	else if (cmpres > 0
		 && mpz_cmp_ui(&a->mpz, (unsigned long int)1) == 0) {
		/* the base is 1 */

		Py_INCREF(mpz_value_one);
		return (PyObject *)mpz_value_one;
	}
	else if (cmpres < 0
		 && mpz_cmp_si(&a->mpz, (long int)-1) == 0) {

		MP_INT tmpmpz;
		/* the base is -1: pow(-1, any) == 1,-1 for even,uneven b */
		/* XXX this code needs to be optimized: what's better?
		   mpz_mmod_ui or mpz_mod_2exp, I choose for the latter
		   for *un*obvious reasons */

		/* is the exponent even? */
		mpz_init(&tmpmpz);

		/* look to the remainder after a division by (1 << 1) */
		mpz_mod_2exp(&tmpmpz, &b->mpz, (unsigned long int)1);

		if (mpz_cmp_ui(&tmpmpz, (unsigned int)0) == 0) {
			mpz_clear(&tmpmpz);
			Py_INCREF(mpz_value_one);
			return (PyObject *)mpz_value_one;
		}
		mpz_clear(&tmpmpz);
		Py_INCREF(mpz_value_mone);
		return (PyObject *)mpz_value_mone;
	}

#ifdef MPZ_LIB_DOES_CHECKING
	/* check if it's doable: sizeof(exp) > sizeof(long) &&
	   abs(base) > 1 ?? --> No Way */
	if (mpz_size(&b->mpz) > 1)
		return (PyObject *)PyErr_NoMemory();
#else /* def MPZ_LIB_DOES_CHECKING */
	/* wet finger method */
	if (mpz_cmp_ui(&b->mpz, (unsigned long int)0x10000) >= 0) {
		PyErr_SetString(PyExc_ValueError,
				"mpz.pow outrageous exponent");
		return NULL;
	}
#endif /* def MPZ_LIB_DOES_CHECKING else */

	if ((z = newmpzobject()) == NULL)
		return NULL;

	mpz_pow_ui(&z->mpz, &a->mpz, mpz_get_ui(&b->mpz));

	return (PyObject *)z;
} /* mpz_power() */


static PyObject *
mpz_negative(mpzobject *v)
{
	mpzobject *z;


#ifdef MPZ_SPARE_MALLOC
	if (mpz_cmp_ui(&v->mpz, (unsigned long int)0) == 0) {
		/* -0 == 0 */
		Py_INCREF(v);
		return (PyObject *)v;
	}
#endif /* def MPZ_SPARE_MALLOC */

	if ((z = newmpzobject()) == NULL)
		return NULL;

	mpz_neg(&z->mpz, &v->mpz);
	return (PyObject *)z;
} /* mpz_negative() */


static PyObject *
mpz_positive(mpzobject *v)
{
	Py_INCREF(v);
	return (PyObject *)v;
} /* mpz_positive() */


static PyObject *
mpz_absolute(mpzobject *v)
{
	mpzobject *z;


	if (mpz_cmp_ui(&v->mpz, (unsigned long int)0) >= 0) {
		Py_INCREF(v);
		return (PyObject *)v;
	}

	if ((z = newmpzobject()) == NULL)
		return NULL;

	mpz_neg(&z->mpz, &v->mpz);
	return (PyObject *)z;
} /* mpz_absolute() */

static int
mpz_nonzero(mpzobject *v)
{
	return mpz_cmp_ui(&v->mpz, (unsigned long int)0) != 0;
} /* mpz_nonzero() */
		
static PyObject *
py_mpz_invert(mpzobject *v)
{
	mpzobject *z;


	/* I think mpz_com does exactly what needed */
	if ((z = newmpzobject()) == NULL)
		return NULL;

	mpz_com(&z->mpz, &v->mpz);
	return (PyObject *)z;
} /* py_mpz_invert() */

static PyObject *
mpz_lshift(mpzobject *a, mpzobject *b)
{
	int cmpres;
	mpzobject *z;


	if ((cmpres = mpz_cmp_ui(&b->mpz, (unsigned long int)0)) == 0) {
		/* a << 0 == a */
		Py_INCREF(a);
		return (PyObject *)a;
	}

	if (cmpres < 0) {
		PyErr_SetString(PyExc_ValueError,
				"mpz.<< negative shift count");
		return NULL;
	}

#ifdef MPZ_LIB_DOES_CHECKING
	if (mpz_size(&b->mpz) > 1)
		return (PyObject *)PyErr_NoMemory();
#else /* def MPZ_LIB_DOES_CHECKING */
	/* wet finger method */
	if (mpz_cmp_ui(&b->mpz, (unsigned long int)0x10000) >= 0) {
		PyErr_SetString(PyExc_ValueError,
				"mpz.<< outrageous shift count");
		return NULL;
	}
#endif /* def MPZ_LIB_DOES_CHECKING else */

	if ((z = newmpzobject()) == NULL)
		return NULL;

	mpz_mul_2exp(&z->mpz, &a->mpz, mpz_get_ui(&b->mpz));
	return (PyObject *)z;
} /* mpz_lshift() */

static PyObject *
mpz_rshift(mpzobject *a, mpzobject *b)
{
	int cmpres;
	mpzobject *z;


	if ((cmpres = mpz_cmp_ui(&b->mpz, (unsigned long int)0)) == 0) {
		/* a >> 0 == a */
		Py_INCREF(a);
		return (PyObject *)a;
	}

	if (cmpres < 0) {
		PyErr_SetString(PyExc_ValueError,
				"mpz.>> negative shift count");
		return NULL;
	}

	if (mpz_size(&b->mpz) > 1)
		return (PyObject *)PyErr_NoMemory();

	if ((z = newmpzobject()) == NULL)
		return NULL;

	mpz_div_2exp(&z->mpz, &a->mpz, mpz_get_ui(&b->mpz));
	return (PyObject *)z;
} /* mpz_rshift() */

static PyObject *
mpz_andfunc(mpzobject *a, mpzobject *b)
{
	mpzobject *z;


	if ((z = newmpzobject()) == NULL)
		return NULL;

	mpz_and(&z->mpz, &a->mpz, &b->mpz);
	return (PyObject *)z;
} /* mpz_andfunc() */

/* hack Hack HAck HACk HACK, XXX this code is dead slow */
void
mpz_xor(MP_INT *res, const MP_INT *op1, const MP_INT *op2)
{
	MP_INT tmpmpz;

	mpz_init(&tmpmpz);

	mpz_and(res, op1, op2);
	mpz_com(&tmpmpz, res);
	mpz_ior(res, op1, op2);
	mpz_and(res, res, &tmpmpz);

	mpz_clear(&tmpmpz);
} /* mpz_xor() HACK */

static PyObject *
mpz_xorfunc(mpzobject *a, mpzobject *b)
{
	mpzobject *z;


	if ((z = newmpzobject()) == NULL)
		return NULL;

	mpz_xor(&z->mpz, &a->mpz, &b->mpz);
	return (PyObject *)z;
} /* mpz_xorfunc() */

static PyObject *
mpz_orfunc(mpzobject *a, mpzobject *b)
{
	mpzobject *z;


	if ((z = newmpzobject()) == NULL)
		return NULL;

	mpz_ior(&z->mpz, &a->mpz, &b->mpz);
	return (PyObject *)z;
} /* mpz_orfunc() */

/* MPZ initialisation */

#include "longintrepr.h"

static PyObject *
MPZ_mpz(PyObject *self, PyObject *args)
{
	mpzobject *mpzp;
	PyObject *objp;


#ifdef MPZ_DEBUG
	fputs("MPZ_mpz() called...\n", stderr);
#endif /* def MPZ_DEBUG */

	if (!PyArg_Parse(args, "O", &objp))
		return NULL;

	/* at least we know it's some object */
	/* note DON't Py_DECREF args NEITHER objp */

	if (PyInt_Check(objp)) {
		long lval;

		if (!PyArg_Parse(objp, "l", &lval))
			return NULL;

		if (lval == (long)0) {
			Py_INCREF(mpz_value_zero);
			mpzp = mpz_value_zero;
		}
		else if (lval == (long)1) {
			Py_INCREF(mpz_value_one);
			mpzp = mpz_value_one;
		}			
		else if ((mpzp = newmpzobject()) == NULL)
			return NULL;
		else mpz_set_si(&mpzp->mpz, lval);
	}
	else if (PyLong_Check(objp)) {
		MP_INT mplongdigit;
		int i;
		unsigned char isnegative;


		if ((mpzp = newmpzobject()) == NULL)
			return NULL;

		mpz_set_si(&mpzp->mpz, 0L);
		mpz_init(&mplongdigit);

		/* how we're gonna handle this? */
		if ((isnegative =
		     ((i = ((PyLongObject *)objp)->ob_size) < 0) ))
			i = -i;

		while (i--) {
			mpz_set_ui(&mplongdigit,
				   (unsigned long)
				   ((PyLongObject *)objp)->ob_digit[i]);
			mpz_mul_2exp(&mplongdigit,&mplongdigit,
				     (unsigned long int)i * SHIFT);
			mpz_ior(&mpzp->mpz, &mpzp->mpz, &mplongdigit);
		}

		if (isnegative)
			mpz_neg(&mpzp->mpz, &mpzp->mpz);

		/* get rid of allocation for tmp variable */
		mpz_clear(&mplongdigit);
	}
	else if (PyString_Check(objp)) {
		unsigned char *cp = (unsigned char *)PyString_AS_STRING(objp);
		int len = PyString_GET_SIZE(objp);
		MP_INT mplongdigit;

		if ((mpzp = newmpzobject()) == NULL)
			return NULL;

		mpz_set_si(&mpzp->mpz, 0L);
		mpz_init(&mplongdigit);

		/* let's do it the same way as with the long conversion:
		   without thinking how it can be faster (-: :-) */

		cp += len;
		while (len--) {
			mpz_set_ui(&mplongdigit, (unsigned long)*--cp );
			mpz_mul_2exp(&mplongdigit,&mplongdigit,
				     (unsigned long int)len * 8);
			mpz_ior(&mpzp->mpz, &mpzp->mpz, &mplongdigit);
		}

		/* get rid of allocation for tmp variable */
		mpz_clear(&mplongdigit);
	}
	else if (is_mpzobject(objp)) {
		Py_INCREF(objp);
		mpzp = (mpzobject *)objp;
	}
	else {
		PyErr_SetString(PyExc_TypeError,
"mpz.mpz() expects integer, long, string or mpz object argument");
		return NULL;
	}


#ifdef MPZ_DEBUG
	fputs("MPZ_mpz: created mpz=", stderr);
	mpz_out_str(stderr, 10, &mpzp->mpz);
	putc('\n', stderr);
#endif /* def MPZ_DEBUG */
	return (PyObject *)mpzp;
} /* MPZ_mpz() */

static mpzobject *
mpz_mpzcoerce(PyObject *z)
{
	/* shortcut: 9 out of 10 times the type is already ok */
	if (is_mpzobject(z)) {
		Py_INCREF(z);
		return (mpzobject *)z;	/* coercion succeeded */
	}

	/* what types do we accept?: intobjects and longobjects */
	if (PyInt_Check(z) || PyLong_Check(z))
		return (mpzobject *)MPZ_mpz((PyObject *)NULL, z);

	PyErr_SetString(PyExc_TypeError,
			"number coercion (to mpzobject) failed");
	return NULL;
} /* mpz_mpzcoerce() */
	
/* Forward */
static void mpz_divm(MP_INT *res, const MP_INT *num,
	             const MP_INT *den, const MP_INT *mod);

static PyObject *
MPZ_powm(PyObject *self, PyObject *args)
{
	PyObject *base, *exp, *mod;
	mpzobject *mpzbase = NULL, *mpzexp = NULL, *mpzmod = NULL;
	mpzobject *z;
	int tstres;


	if (!PyArg_Parse(args, "(OOO)", &base, &exp, &mod))
		return NULL;

	if ((mpzbase = mpz_mpzcoerce(base)) == NULL
	    || (mpzexp = mpz_mpzcoerce(exp)) == NULL
	    || (mpzmod = mpz_mpzcoerce(mod)) == NULL
	    || (z = newmpzobject()) == NULL) {
		Py_XDECREF(mpzbase);
		Py_XDECREF(mpzexp);
		Py_XDECREF(mpzmod);
		return NULL;
	}

	if ((tstres=mpz_cmp_ui(&mpzexp->mpz, (unsigned long int)0)) == 0) {
		Py_INCREF(mpz_value_one);
		return (PyObject *)mpz_value_one;
	}

	if (tstres < 0) {
		MP_INT absexp;
		/* negative exp */

		mpz_init_set(&absexp, &mpzexp->mpz);
		mpz_abs(&absexp, &absexp);
		mpz_powm(&z->mpz, &mpzbase->mpz, &absexp, &mpzmod->mpz);

		mpz_divm(&z->mpz, &mpz_value_one->mpz, &z->mpz, &mpzmod->mpz);
		
		mpz_clear(&absexp);
	}
	else {
		mpz_powm(&z->mpz, &mpzbase->mpz, &mpzexp->mpz, &mpzmod->mpz);
	}
	
	Py_DECREF(mpzbase);
	Py_DECREF(mpzexp);
	Py_DECREF(mpzmod);

	return (PyObject *)z;
} /* MPZ_powm() */


static PyObject *
MPZ_gcd(PyObject *self, PyObject *args)
{
	PyObject *op1, *op2;
	mpzobject *mpzop1 = NULL, *mpzop2 = NULL;
	mpzobject *z;


	if (!PyArg_Parse(args, "(OO)", &op1, &op2))
		return NULL;

	if ((mpzop1 = mpz_mpzcoerce(op1)) == NULL
	    || (mpzop2 = mpz_mpzcoerce(op2)) == NULL
	    || (z = newmpzobject()) == NULL) {
		Py_XDECREF(mpzop1);
		Py_XDECREF(mpzop2);
		return NULL;
	}

	/* ok, we have three mpzobjects, and an initialised result holder */
	mpz_gcd(&z->mpz, &mpzop1->mpz, &mpzop2->mpz);

	Py_DECREF(mpzop1);
	Py_DECREF(mpzop2);

	return (PyObject *)z;
} /* MPZ_gcd() */


static PyObject *
MPZ_gcdext(PyObject *self, PyObject *args)
{
	PyObject *op1, *op2, *z = NULL;
	mpzobject *mpzop1 = NULL, *mpzop2 = NULL;
	mpzobject *g = NULL, *s = NULL, *t = NULL;


	if (!PyArg_Parse(args, "(OO)", &op1, &op2))
		return NULL;

	if ((mpzop1 = mpz_mpzcoerce(op1)) == NULL
	    || (mpzop2 = mpz_mpzcoerce(op2)) == NULL
	    || (z = PyTuple_New(3)) == NULL
	    || (g = newmpzobject()) == NULL
	    || (s = newmpzobject()) == NULL
	    || (t = newmpzobject()) == NULL) {
		Py_XDECREF(mpzop1);
		Py_XDECREF(mpzop2);
		Py_XDECREF(z);
		Py_XDECREF(g);
		Py_XDECREF(s);
		/*Py_XDECREF(t);*/
		return NULL;
	}

	mpz_gcdext(&g->mpz, &s->mpz, &t->mpz, &mpzop1->mpz, &mpzop2->mpz);

	Py_DECREF(mpzop1);
	Py_DECREF(mpzop2);

	(void)PyTuple_SetItem(z, 0, (PyObject *)g);
	(void)PyTuple_SetItem(z, 1, (PyObject *)s);
	(void)PyTuple_SetItem(z, 2, (PyObject *)t);

	return (PyObject *)z;
} /* MPZ_gcdext() */


static PyObject *
MPZ_sqrt(PyObject *self, PyObject *args)
{
	PyObject *op;
	mpzobject *mpzop = NULL;
	mpzobject *z;


	if (!PyArg_Parse(args, "O", &op))
		return NULL;

	if ((mpzop = mpz_mpzcoerce(op)) == NULL
	    || (z = newmpzobject()) == NULL) {
		Py_XDECREF(mpzop);
		return NULL;
	}

	mpz_sqrt(&z->mpz, &mpzop->mpz);

	Py_DECREF(mpzop);

	return (PyObject *)z;
} /* MPZ_sqrt() */


static PyObject *
MPZ_sqrtrem(PyObject *self, PyObject *args)
{
	PyObject *op, *z = NULL;
	mpzobject *mpzop = NULL;
	mpzobject *root = NULL, *rem = NULL;


	if (!PyArg_Parse(args, "O", &op))
		return NULL;

	if ((mpzop = mpz_mpzcoerce(op)) == NULL
	    || (z = PyTuple_New(2)) == NULL
	    || (root = newmpzobject()) == NULL
	    || (rem = newmpzobject()) == NULL) {
		Py_XDECREF(mpzop);
		Py_XDECREF(z);
		Py_XDECREF(root);
		/*Py_XDECREF(rem);*/
		return NULL;
	}

	mpz_sqrtrem(&root->mpz, &rem->mpz, &mpzop->mpz);

	Py_DECREF(mpzop);

	(void)PyTuple_SetItem(z, 0, (PyObject *)root);
	(void)PyTuple_SetItem(z, 1, (PyObject *)rem);

	return (PyObject *)z;
} /* MPZ_sqrtrem() */


static void
mpz_divm(MP_INT *res, const MP_INT *num, const MP_INT *den, const MP_INT *mod)
{
	MP_INT s0, s1, q, r, x, d0, d1;

	mpz_init_set(&s0, num);
	mpz_init_set_ui(&s1, 0);
	mpz_init(&q);
	mpz_init(&r);
	mpz_init(&x);
	mpz_init_set(&d0, den);
	mpz_init_set(&d1, mod);

#ifdef GMP2
	while (d1._mp_size != 0) {
#else
	while (d1.size != 0) {
#endif
		mpz_divmod(&q, &r, &d0, &d1);
		mpz_set(&d0, &d1);
		mpz_set(&d1, &r);

		mpz_mul(&x, &s1, &q);
		mpz_sub(&x, &s0, &x);
		mpz_set(&s0, &s1);