mpzmodule.c

python s60 1.4.5版本的源代码

		mpz_set(&s1, &x);
	}

#ifdef GMP2
	if (d0._mp_size != 1 || d0._mp_d[0] != 1)
		res->_mp_size = 0; /* trouble: the gcd != 1; set s to zero */
#else
	if (d0.size != 1 || d0.d[0] != 1)
		res->size = 0;	/* trouble: the gcd != 1; set s to zero */
#endif
	else {
#ifdef MPZ_MDIV_BUG
		/* watch out here! first check the signs, and then perform
		   the mpz_mod() since mod could point to res */
		if ((s0.size < 0) != (mod->size < 0)) {
			mpz_mod(res, &s0, mod);

			if (res->size)
				mpz_add(res, res, mod);
		}
		else
			mpz_mod(res, &s0, mod);

#else /* def MPZ_MDIV_BUG */
		mpz_mmod(res, &s0, mod);
#endif /* def MPZ_MDIV_BUG else */
	}

	mpz_clear(&s0);
	mpz_clear(&s1);
	mpz_clear(&q);
	mpz_clear(&r);
	mpz_clear(&x);
	mpz_clear(&d0);
	mpz_clear(&d1);
} /* mpz_divm() */


static PyObject *
MPZ_divm(PyObject *self, PyObject *args)
{
	PyObject *num, *den, *mod;
	mpzobject *mpznum, *mpzden = NULL, *mpzmod = NULL;
	mpzobject *z = NULL;


	if (!PyArg_Parse(args, "(OOO)", &num, &den, &mod))
		return NULL;

	if ((mpznum = mpz_mpzcoerce(num)) == NULL
	    || (mpzden = mpz_mpzcoerce(den)) == NULL
	    || (mpzmod = mpz_mpzcoerce(mod)) == NULL
	    || (z = newmpzobject()) == NULL ) {
		Py_XDECREF(mpznum);
		Py_XDECREF(mpzden);
		Py_XDECREF(mpzmod);
		return NULL;
	}

	mpz_divm(&z->mpz, &mpznum->mpz, &mpzden->mpz, &mpzmod->mpz);

	Py_DECREF(mpznum);
	Py_DECREF(mpzden);
	Py_DECREF(mpzmod);

	if (mpz_cmp_ui(&z->mpz, (unsigned long int)0) == 0) {
		Py_DECREF(z);
		PyErr_SetString(PyExc_ValueError,
				"gcd(den, mod) != 1 or num == 0");
		return NULL;
	}

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


/* MPZ methods-as-attributes */
#ifdef MPZ_CONVERSIONS_AS_METHODS
static PyObject *
mpz_int(mpzobject *self, PyObject *args)
#else /* def MPZ_CONVERSIONS_AS_METHODS */
static PyObject *
mpz_int(mpzobject *self)
#endif /* def MPZ_CONVERSIONS_AS_METHODS else */
{
	long sli;


#ifdef MPZ_CONVERSIONS_AS_METHODS
	if (!PyArg_NoArgs(args))
		return NULL;
#endif /* def MPZ_CONVERSIONS_AS_METHODS */

	if (mpz_size(&self->mpz) > 1
	    || (sli = (long)mpz_get_ui(&self->mpz)) < (long)0 ) {
		PyErr_SetString(PyExc_ValueError,
				"mpz.int() arg too long to convert");
		return NULL;
	}

	if (mpz_cmp_ui(&self->mpz, (unsigned long)0) < 0)
		sli = -sli;

	return PyInt_FromLong(sli);
} /* mpz_int() */
	
static PyObject *
#ifdef MPZ_CONVERSIONS_AS_METHODS
mpz_long(mpzobject *self, PyObject *args)
#else /* def MPZ_CONVERSIONS_AS_METHODS */
mpz_long(mpzobject *self)
#endif /* def MPZ_CONVERSIONS_AS_METHODS else */
{
	int i, isnegative;
	unsigned long int uli;
	PyLongObject *longobjp;
	int ldcount;
	int bitpointer, newbitpointer;
	MP_INT mpzscratch;


#ifdef MPZ_CONVERSIONS_AS_METHODS
	if (!PyArg_NoArgs(args))
		return NULL;
#endif /* def MPZ_CONVERSIONS_AS_METHODS */

	/* determine length of python-long to be allocated */
	if ((longobjp = _PyLong_New(i = (int)
			    ((mpz_size(&self->mpz) * BITS_PER_MP_LIMB
			      + SHIFT - 1) /
			     SHIFT))) == NULL)
		return NULL;

	/* determine sign, and copy self to scratch var */
	mpz_init_set(&mpzscratch, &self->mpz);
	if ((isnegative = (mpz_cmp_ui(&self->mpz, (unsigned long int)0) < 0)))
		mpz_neg(&mpzscratch, &mpzscratch);

	/* let those bits come, let those bits go,
	   e.g. dismantle mpzscratch, build PyLongObject */

	bitpointer = 0;		/* the number of valid bits in stock */
	newbitpointer = 0;
	ldcount = 0;		/* the python-long limb counter */
	uli = (unsigned long int)0;
	while (i--) {
		longobjp->ob_digit[ldcount] = uli & MASK;

		/* check if we've had enough bits for this digit */
		if (bitpointer < SHIFT) {
			uli = mpz_get_ui(&mpzscratch);
			longobjp->ob_digit[ldcount] |=
				(uli << bitpointer) & MASK;
			uli >>= SHIFT-bitpointer;
			bitpointer += BITS_PER_MP_LIMB;
			mpz_div_2exp(&mpzscratch, &mpzscratch,
				     BITS_PER_MP_LIMB);
		}
		else
			uli >>= SHIFT;
		bitpointer -= SHIFT;
		ldcount++;
	}

	assert(mpz_cmp_ui(&mpzscratch, (unsigned long int)0) == 0);
	mpz_clear(&mpzscratch);
	assert(ldcount <= longobjp->ob_size);

	/* long_normalize() is file-static */
	/* longobjp = long_normalize(longobjp); */
	while (ldcount > 0 && longobjp->ob_digit[ldcount-1] == 0)
		ldcount--;
	longobjp->ob_size = ldcount;


	if (isnegative)
		longobjp->ob_size = -longobjp->ob_size;

	return (PyObject *)longobjp;

} /* mpz_long() */


/* I would have avoided pow() anyways, so ... */
static const double multiplier = 256.0 * 256.0 * 256.0 * 256.0;

#ifdef MPZ_CONVERSIONS_AS_METHODS
static PyObject *
mpz_float(mpzobject *self, PyObject *args)
#else /* def MPZ_CONVERSIONS_AS_METHODS */
static PyObject *
mpz_float(mpzobject *self)
#endif /* def MPZ_CONVERSIONS_AS_METHODS else */
{
	int i, isnegative;
	double x;
	double mulstate;
	MP_INT mpzscratch;


#ifdef MPZ_CONVERSIONS_AS_METHODS
	if (!PyArg_NoArgs(args))
		return NULL;
#endif /* def MPZ_CONVERSIONS_AS_METHODS */

	i = (int)mpz_size(&self->mpz);

	/* determine sign, and copy abs(self) to scratch var */
	if ((isnegative = (mpz_cmp_ui(&self->mpz, (unsigned long int)0) < 0)))
	{
		mpz_init(&mpzscratch);
		mpz_neg(&mpzscratch, &self->mpz);
	}
	else
		mpz_init_set(&mpzscratch, &self->mpz);

	/* let those bits come, let those bits go,
	   e.g. dismantle mpzscratch, build PyFloatObject */

	/* Can this overflow?  Dunno, protect against that possibility. */
	PyFPE_START_PROTECT("mpz_float", return 0)
	x = 0.0;
	mulstate = 1.0;
	while (i--) {
		x += mulstate * mpz_get_ui(&mpzscratch);
		mulstate *= multiplier;
		mpz_div_2exp(&mpzscratch, &mpzscratch, BITS_PER_MP_LIMB);
	}
	PyFPE_END_PROTECT(mulstate)

	assert(mpz_cmp_ui(&mpzscratch, (unsigned long int)0) == 0);
	mpz_clear(&mpzscratch);

	if (isnegative)
		x = -x;

	return PyFloat_FromDouble(x);

} /* mpz_float() */

#ifdef MPZ_CONVERSIONS_AS_METHODS
static PyObject *
mpz_hex(mpzobject *self, PyObject *args)
#else /* def MPZ_CONVERSIONS_AS_METHODS */
static PyObject *
mpz_hex(mpzobject *self)
#endif /* def MPZ_CONVERSIONS_AS_METHODS else */
{
#ifdef MPZ_CONVERSIONS_AS_METHODS
	if (!PyArg_NoArgs(args))
		return NULL;
#endif /* def MPZ_CONVERSIONS_AS_METHODS */

	return mpz_format((PyObject *)self, 16, (unsigned char)1);
} /* mpz_hex() */

#ifdef MPZ_CONVERSIONS_AS_METHODS
static PyObject *
mpz_oct(mpzobject *self, PyObject *args)
#else /* def MPZ_CONVERSIONS_AS_METHODS */
static PyObject *
mpz_oct(mpzobject *self)
#endif /* def MPZ_CONVERSIONS_AS_METHODS else */
{
#ifdef MPZ_CONVERSIONS_AS_METHODS
	if (!PyArg_NoArgs(args))
		return NULL;
#endif /* def MPZ_CONVERSIONS_AS_METHODS */
	
	return mpz_format((PyObject *)self, 8, (unsigned char)1);
} /* mpz_oct() */

static PyObject *
mpz_binary(mpzobject *self, PyObject *args)
{
	int size;
	PyStringObject *strobjp;
	char *cp;
	MP_INT mp;
	unsigned long ldigit;

	if (!PyArg_NoArgs(args))
		return NULL;

	if (mpz_cmp_ui(&self->mpz, (unsigned long int)0) < 0) {
		PyErr_SetString(PyExc_ValueError,
				"mpz.binary() arg must be >= 0");
		return NULL;
	}

	mpz_init_set(&mp, &self->mpz);
	size = (int)mpz_size(&mp);

	if ((strobjp = (PyStringObject *)
	     PyString_FromStringAndSize(
		     (char *)0, size * sizeof (unsigned long int))) == NULL)
		return NULL;

	/* get the beginning of the string memory and start copying things */
	cp = PyString_AS_STRING(strobjp);

	/* this has been programmed using a (fairly) decent lib-i/f it could
	   be must faster if we looked into the GMP lib */
	while (size--) {
		ldigit = mpz_get_ui(&mp);
		mpz_div_2exp(&mp, &mp, BITS_PER_MP_LIMB);
		*cp++ = (unsigned char)(ldigit & 0xFF);
		*cp++ = (unsigned char)((ldigit >>= 8) & 0xFF);
		*cp++ = (unsigned char)((ldigit >>= 8) & 0xFF);
		*cp++ = (unsigned char)((ldigit >>= 8) & 0xFF);
		if (sizeof(ldigit) == 8 && BITS_PER_MP_LIMB == 64) {
			*cp++ = (unsigned char)((ldigit >>= 8) & 0xFF);
			*cp++ = (unsigned char)((ldigit >>= 8) & 0xFF);
			*cp++ = (unsigned char)((ldigit >>= 8) & 0xFF);
			*cp++ = (unsigned char)((ldigit >>= 8) & 0xFF);
		}
	}

	while (strobjp->ob_size && !*--cp)
		strobjp->ob_size--;

	return (PyObject *)strobjp;
} /* mpz_binary() */


static PyMethodDef mpz_methods[] = {
#ifdef MPZ_CONVERSIONS_AS_METHODS
	{"int",			mpz_int},
	{"long",		mpz_long},
	{"float",		mpz_float},
	{"hex",			mpz_hex},
	{"oct",			mpz_oct},
#endif /* def MPZ_CONVERSIONS_AS_METHODS */
	{"binary",		(PyCFunction)mpz_binary},
	{NULL,			NULL}		/* sentinel */
};

static PyObject *
mpz_getattr(mpzobject *self, char *name)
{
	return Py_FindMethod(mpz_methods, (PyObject *)self, name);
} /* mpz_getattr() */


static int
mpz_coerce(PyObject **pv, PyObject **pw)
{
	PyObject *z;

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

	assert(is_mpzobject(*pv));

	/* always convert other arg to mpz value, except for floats */
	if (!PyFloat_Check(*pw)) {
		if ((z = (PyObject *)mpz_mpzcoerce(*pw)) == NULL)
			return -1;	/* -1: an error always has been set */
		
		Py_INCREF(*pv);
		*pw = z;
	}
	else {
#ifdef MPZ_CONVERSIONS_AS_METHODS
		if ((z = mpz_float((mpzobject *)(*pv), NULL)) == NULL)
			return -1;
#else /* def MPZ_CONVERSIONS_AS_METHODS */
		if ((z = mpz_float((mpzobject *)(*pv))) == NULL)
			return -1;
#endif /* def MPZ_CONVERSIONS_AS_METHODS else */

		Py_INCREF(*pw);
		*pv = z;
	}
	return 0;		/* coercion succeeded */

} /* mpz_coerce() */


static PyObject *
mpz_repr(PyObject *v)
{
	return mpz_format(v, 10, (unsigned char)1);
} /* mpz_repr() */



#define UF (unaryfunc)
#define BF (binaryfunc)
#define TF (ternaryfunc)
#define IF (inquiry)
#define CF (coercion)

static PyNumberMethods mpz_as_number = {
	BF mpz_addition,	/*nb_add*/
	BF mpz_substract,	/*nb_subtract*/
	BF mpz_multiply,	/*nb_multiply*/
	BF mpz_divide,		/*nb_divide*/
	BF mpz_remainder,	/*nb_remainder*/
	BF mpz_div_and_mod,	/*nb_divmod*/
	TF mpz_power,		/*nb_power*/
	UF mpz_negative,	/*nb_negative*/
	UF mpz_positive,	/*tp_positive*/
	UF mpz_absolute,	/*tp_absolute*/
	IF mpz_nonzero,		/*tp_nonzero*/
	UF py_mpz_invert,	/*nb_invert*/
	BF mpz_lshift,		/*nb_lshift*/
	BF mpz_rshift,		/*nb_rshift*/
	BF mpz_andfunc,		/*nb_and*/
	BF mpz_xorfunc,		/*nb_xor*/
	BF mpz_orfunc,		/*nb_or*/
	CF mpz_coerce,		/*nb_coerce*/
#ifndef MPZ_CONVERSIONS_AS_METHODS
	UF mpz_int,		/*nb_int*/
	UF mpz_long,		/*nb_long*/
	UF mpz_float,		/*nb_float*/
	UF mpz_oct,		/*nb_oct*/
	UF mpz_hex,		/*nb_hex*/
#endif /* ndef MPZ_CONVERSIONS_AS_METHODS */
};

static PyTypeObject MPZtype = {
	PyObject_HEAD_INIT(NULL)
	0,			/*ob_size*/
	"mpz.mpz",		/*tp_name*/
	sizeof(mpzobject),	/*tp_size*/
	0,			/*tp_itemsize*/
	/* methods */
	(destructor)mpz_dealloc, /*tp_dealloc*/
	0,			/*tp_print*/
	(getattrfunc)mpz_getattr, /*tp_getattr*/
	0,			/*tp_setattr*/
	(cmpfunc)mpz_compare,	/*tp_compare*/
	(reprfunc)mpz_repr,	/*tp_repr*/
        &mpz_as_number, 	/*tp_as_number*/
};

/* List of functions exported by this module */

static PyMethodDef mpz_functions[] = {
#if 0
	{initialiser_name,	MPZ_mpz},
#else /* 0 */
	/* until guido ``fixes'' struct PyMethodDef */
	{(char *)initialiser_name,	MPZ_mpz},
#endif /* 0 else */	
	{"powm",		MPZ_powm},
	{"gcd",			MPZ_gcd},
	{"gcdext",		MPZ_gcdext},
	{"sqrt",		MPZ_sqrt},
	{"sqrtrem",		MPZ_sqrtrem},
	{"divm",		MPZ_divm},
	{NULL,			NULL}		 /* Sentinel */
};


/* #define MP_TEST_ALLOC */

#ifdef MP_TEST_ALLOC
#define MP_TEST_SIZE		4
static const char mp_test_magic[MP_TEST_SIZE] = {'\xAA','\xAA','\xAA','\xAA'};
static mp_test_error(int *location)
{
	/* assumptions: *alloc returns address divisible by 4,
	mpz_* routines allocate in chunks divisible by four */
	fprintf(stderr, "MP_TEST_ERROR: location holds 0x%08d\n", *location );
	Py_FatalError("MP_TEST_ERROR");
} /* static mp_test_error() */
#define MP_EXTRA_ALLOC(size)	((size) + MP_TEST_SIZE)
#define MP_SET_TEST(basep,size)	(void)memcpy( ((char *)(basep))+(size), mp_test_magic, MP_TEST_SIZE)
#define MP_DO_TEST(basep,size)	if ( !memcmp( ((char *)(basep))+(size), mp_test_magic, MP_TEST_SIZE ) ) \
					; \
				else \
					mp_test_error((int *)((char *)(basep) + size))
#else /* def MP_TEST_ALLOC */
#define MP_EXTRA_ALLOC(size)	(size)
#define MP_SET_TEST(basep,size)
#define MP_DO_TEST(basep,size)
#endif /* def MP_TEST_ALLOC else */

void *mp_allocate(size_t alloc_size)
{
	void *res;

#ifdef MPZ_DEBUG
	fprintf(stderr, "mp_allocate  :                             size %ld\n",
		alloc_size);
#endif /* def MPZ_DEBUG */	

	if ( (res = malloc(MP_EXTRA_ALLOC(alloc_size))) == NULL )
		Py_FatalError("mp_allocate failure");

#ifdef MPZ_DEBUG
	fprintf(stderr, "mp_allocate  :     address %08p\n", res);
#endif /* def MPZ_DEBUG */	

	MP_SET_TEST(res,alloc_size);
	
	return res;
} /* mp_allocate() */


void *mp_reallocate(void *ptr, size_t old_size, size_t new_size)
{
	void *res;

#ifdef MPZ_DEBUG
	fprintf(stderr, "mp_reallocate: old address %08p, old size %ld\n",
		ptr, old_size);
#endif /* def MPZ_DEBUG */	

	MP_DO_TEST(ptr, old_size);
	
	if ( (res = realloc(ptr, MP_EXTRA_ALLOC(new_size))) == NULL )
		Py_FatalError("mp_reallocate failure");

#ifdef MPZ_DEBUG
	fprintf(stderr, "mp_reallocate: new address %08p, new size %ld\n",
		res, new_size);
#endif /* def MPZ_DEBUG */	

	MP_SET_TEST(res, new_size);

	return res;
} /* mp_reallocate() */


void mp_free(void *ptr, size_t size)
{

#ifdef MPZ_DEBUG
	fprintf(stderr, "mp_free      : old address %08p, old size %ld\n",
		ptr, size);
#endif /* def MPZ_DEBUG */	

	MP_DO_TEST(ptr, size);
	free(ptr);
} /* mp_free() */



/* Initialize this module. */

DL_EXPORT(void)
initmpz(void)
{
	PyObject *module;
	PyObject *dict;

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

	mp_set_memory_functions( mp_allocate, mp_reallocate, mp_free );
        MPZtype.ob_type = &PyType_Type;
	module = Py_InitModule("mpz", mpz_functions);

	/* create some frequently used constants */
	if ((mpz_value_zero = newmpzobject()) == NULL)
		goto finally;
	mpz_set_ui(&mpz_value_zero->mpz, (unsigned long int)0);

	if ((mpz_value_one = newmpzobject()) == NULL)
		goto finally;
	mpz_set_ui(&mpz_value_one->mpz, (unsigned long int)1);

	if ((mpz_value_mone = newmpzobject()) == NULL)
		goto finally;
	mpz_set_si(&mpz_value_mone->mpz, (long)-1);

	dict = PyModule_GetDict(module);
	if (dict != NULL) {
		PyDict_SetItemString(dict, "MPZType", (PyObject*)&MPZtype);
	}
  finally:
	return;
} /* initmpz() */

#ifdef MAKEDUMMYINT
int _mpz_dummy_int;	/* XXX otherwise, we're .bss-less (DYNLOAD->Jack?) */
#endif /* def MAKEDUMMYINT */