mpzmodule.c

python s60 1.4.5版本的源代码

/* MPZ module */

/* This module provides an interface to an alternate Multi-Precision
   library, GNU MP in this case */

/* XXX note: everywhere where mpz_size is called,
   sizeof (limb) == sizeof (long)  has been assumed. */
   

/* MPZ objects */

#include "Python.h"

#include <sys/types.h>		/* For size_t */

/*
**	These are the cpp-flags used in this file...
**
**
** MPZ_MDIV_BUG		works around the mpz_m{div,mod,...} routines.
** 			This bug has been fixed in a later release of
** 			GMP.
** 
** MPZ_GET_STR_BUG	mpz_get_str corrupts memory, seems to be fixed
** 			in a later release
** 
** MPZ_DEBUG		generates a bunch of diagnostic messages
** 
** MPZ_SPARE_MALLOC	if set, results in extra code that tries to
** 			minimize the creation of extra objects.
** 
** MPZ_TEST_DIV		extra diagnostic output on stderr, when division
** 			routines are involved
** 
** MPZ_LIB_DOES_CHECKING	if set, assumes that mpz library doesn't call
** 			alloca with arg < 0 (when casted to a signed
** 			integral type).
** 
** MPZ_CONVERSIONS_AS_METHODS	if set, presents the conversions as
** 			methods. e.g., `mpz(5).long() == 5L'
** 			Later, Guido provided an interface to the
** 			standard functions. So this flag has no been
** 			cleared, and `long(mpz(5)) == 5L'
** 
** MP_TEST_ALLOC	If set, you would discover why MPZ_GET_STR_BUG
**			is needed
** 
** MAKEDUMMYINT		Must be set if dynamic linking will be used
*/


/*
** IMHO, mpz_m{div,mod,divmod}() do the wrong things when the denominator < 0
** This has been fixed with gmp release 2.0
*/
/*#define MPZ_MDIV_BUG fixed the (for me) nexessary parts in libgmp.a */
/*
** IMO, mpz_get_str() assumes a bit too large target space, if he doesn't
** allocate it himself
*/

#include "gmp.h"

#if __GNU_MP__ + 0 >= 2
#define GMP2
#define BITS_PER_MP_LIMB mp_bits_per_limb
#else
#define MPZ_GET_STR_BUG
#include "gmp-mparam.h"
#endif

typedef struct {
	PyObject_HEAD
        MP_INT	mpz;		/* the actual number */
} mpzobject;

staticforward PyTypeObject MPZtype;

#define is_mpzobject(v)		((v)->ob_type == &MPZtype)

static const char initialiser_name[] = "mpz";

/* #define MPZ_DEBUG */

static mpzobject *
newmpzobject(void)
{
	mpzobject *mpzp;


#ifdef MPZ_DEBUG
	fputs( "mpz_object() called...\n", stderr );
#endif /* def MPZ_DEBUG */
	mpzp = PyObject_New(mpzobject, &MPZtype);
	if (mpzp == NULL)
		return NULL;

	mpz_init(&mpzp->mpz);	/* actual initialisation */
	return mpzp;
} /* newmpzobject() */

#ifdef MPZ_GET_STR_BUG
#include "longlong.h"
#endif /* def MPZ_GET_STR_BUG */

static PyObject *
mpz_format(PyObject *objp, int base, unsigned char withname)
{
	mpzobject *mpzp = (mpzobject *)objp;
	PyStringObject *strobjp;
	size_t i;
	int cmpres;
	int taglong;
	char *cp;
	char prefix[5], *tcp;


	tcp = &prefix[0];

	if (mpzp == NULL || !is_mpzobject(mpzp)) {
		PyErr_BadInternalCall();
		return NULL;
	}

	assert(base >= 2 && base <= 36);

	if (withname)
		i = strlen(initialiser_name) + 2; /* e.g. 'mpz(' + ')' */
	else
		i = 0;

	if ((cmpres = mpz_cmp_si(&mpzp->mpz, 0L)) == 0)
		base = 10;	/* '0' in every base, right */
	else if (cmpres < 0) {
		*tcp++ = '-';
		i += 1;		/* space to hold '-' */
	}

#ifdef MPZ_DEBUG
	fprintf(stderr, "mpz_format: mpz_sizeinbase %d\n",
		(int)mpz_sizeinbase(&mpzp->mpz, base));
#endif /* def MPZ_DEBUG */
#ifdef MPZ_GET_STR_BUG
#ifdef GMP2
	i += ((size_t) abs(mpzp->mpz._mp_size) * BITS_PER_MP_LIMB
	      * __mp_bases[base].chars_per_bit_exactly) + 1;
#else
	i += ((size_t) abs(mpzp->mpz.size) * BITS_PER_MP_LIMB
	      * __mp_bases[base].chars_per_bit_exactly) + 1;
#endif
#else /* def MPZ_GET_STR_BUG */
	i += (int)mpz_sizeinbase(&mpzp->mpz, base);
#endif /* def MPZ_GET_STR_BUG else */

	if (base == 16) {
		*tcp++ = '0';
		*tcp++ = 'x';
		i += 2;		/* space to hold '0x' */
	}
	else if (base == 8) {
		*tcp++ = '0';
		i += 1;		/* space to hold the extra '0' */
	}
	else if (base > 10) {
		*tcp++ = '0' + base / 10;
		*tcp++ = '0' + base % 10;
		*tcp++ = '#';
		i += 3;		/* space to hold e.g. '12#' */
	}
	else if (base < 10) {
		*tcp++ = '0' + base;
		*tcp++ = '#';
		i += 2;		/* space to hold e.g. '6#' */
	}

	/*
	** the following code looks if we need a 'L' attached to the number
	** it will also attach an 'L' to the value -0x80000000
	*/
	taglong = 0;
	if (mpz_size(&mpzp->mpz) > 1
	    || (long)mpz_get_ui(&mpzp->mpz) < 0L) {
		taglong = 1;
		i += 1;		/* space to hold 'L' */
	}

#ifdef MPZ_DEBUG
	fprintf(stderr, "mpz_format: requesting string size %d\n", i);
#endif /* def MPZ_DEBUG */	
	if ((strobjp =
	     (PyStringObject *)PyString_FromStringAndSize((char *)0, i))
	    == NULL)
		return NULL;

	/* get the beginning of the string memory and start copying things */
	cp = PyString_AS_STRING(strobjp);
	if (withname) {
		strcpy(cp, initialiser_name);
		cp += strlen(initialiser_name);
		*cp++ = '('; /*')'*/
	}

	/* copy the already prepared prefix; e.g. sign and base indicator */
	*tcp = '\0';
	strcpy(cp, prefix);
	cp += tcp - prefix;

	/* since' we have the sign already, let the lib think it's a positive
	   number */
	if (cmpres < 0)
		mpz_neg(&mpzp->mpz,&mpzp->mpz);	/* hack Hack HAck HACk HACK */
	(void)mpz_get_str(cp, base, &mpzp->mpz);
	if (cmpres < 0)
		mpz_neg(&mpzp->mpz,&mpzp->mpz);	/* hack Hack HAck HACk HACK */
#ifdef MPZ_DEBUG
	fprintf(stderr, "mpz_format: base (ultim) %d, mpz_get_str: %s\n",
		base, cp);
#endif /* def MPZ_DEBUG */
	cp += strlen(cp);

	if (taglong)
		*cp++ = 'L';
	if (withname)
		*cp++ = /*'('*/ ')';

	*cp = '\0';

#ifdef MPZ_DEBUG
	fprintf(stderr,
		"mpz_format: cp (str end) %p, begin %p, diff %d, i %d\n",
		cp, PyString_AS_STRING(strobjp),
		cp - PyString_AS_STRING(strobjp), i);
#endif /* def MPZ_DEBUG */	
	assert(cp - PyString_AS_STRING(strobjp) <= i);

	if (cp - PyString_AS_STRING(strobjp) != i) {
		strobjp->ob_size -= i - (cp - PyString_AS_STRING(strobjp));
	}

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

/* MPZ methods */

static void
mpz_dealloc(mpzobject *mpzp)
{
#ifdef MPZ_DEBUG
	fputs( "mpz_dealloc() called...\n", stderr );
#endif /* def MPZ_DEBUG */
	mpz_clear(&mpzp->mpz);
	PyObject_Del(mpzp);
} /* mpz_dealloc() */


/* pointers to frequently used values 0, 1 and -1 */
static mpzobject *mpz_value_zero, *mpz_value_one, *mpz_value_mone;

static int
mpz_compare(mpzobject *a, mpzobject *b)
{
	int cmpres;


	/* guido sez it's better to return -1, 0 or 1 */
	return (cmpres = mpz_cmp( &a->mpz, &b->mpz )) == 0 ? 0
		: cmpres > 0 ? 1 : -1;
} /* mpz_compare() */

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

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

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

	if ((z = newmpzobject()) == NULL)
		return NULL;
	
	mpz_add(&z->mpz, &a->mpz, &b->mpz);
	return (PyObject *)z;
} /* mpz_addition() */

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

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

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

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

static PyObject *
mpz_multiply(mpzobject *a, mpzobject *b)
{
#ifdef MPZ_SPARE_MALLOC
	int cmpres;
#endif /* def MPZ_SPARE_MALLOC */
	mpzobject *z;


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

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

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

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

static PyObject *
mpz_divide(mpzobject *a, mpzobject *b)
{
#ifdef MPZ_SPARE_MALLOC
	int cmpres;
#endif /* def MPZ_SPARE_MALLOC */
	mpzobject *z;


	if ((
#ifdef MPZ_SPARE_MALLOC
	     cmpres =
#endif /* def MPZ_SPARE_MALLOC */
	     mpz_cmp_ui(&b->mpz, (unsigned long int)0)) == 0) {
		PyErr_SetString(PyExc_ZeroDivisionError, "mpz./ by zero");
		return NULL;
	}
#ifdef MPZ_SPARE_MALLOC
	if (cmpres > 0 && mpz_cmp_ui(&b->mpz(unsigned long int)1) == 0) {
		Py_INCREF(a);
		return (PyObject *)a;
	}
#endif /* def MPZ_SPARE_MALLOC */

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

#ifdef MPZ_TEST_DIV
	fputs("mpz_divide:  div result", stderr);
	mpz_div(&z->mpz, &a->mpz, &b->mpz);
	mpz_out_str(stderr, 10, &z->mpz);
	putc('\n', stderr);
#endif /* def MPZ_TEST_DIV */
#ifdef MPZ_MDIV_BUG
	if ((mpz_cmp_ui(&a->mpz, (unsigned long int)0) < 0)
	    != (mpz_cmp_ui(&b->mpz, (unsigned long int)0) < 0)) {
		/*
		** numerator has other sign than denominator: we have
		** to look at the remainder for a correction, since mpz_mdiv
		** also calls mpz_divmod, I can as well do it myself
		*/
		MP_INT tmpmpz;


		mpz_init(&tmpmpz);
		mpz_divmod(&z->mpz, &tmpmpz, &a->mpz, &b->mpz);

		if (mpz_cmp_ui(&tmpmpz, (unsigned long int)0) != 0)
			mpz_sub_ui(&z->mpz, &z->mpz, (unsigned long int)1);

		mpz_clear(&tmpmpz);
	}
	else
		mpz_div(&z->mpz, &a->mpz, &b->mpz);
		/* the ``naive'' implementation does it right for operands
		   having the same sign */

#else /* def MPZ_MDIV_BUG */
	mpz_mdiv(&z->mpz, &a->mpz, &b->mpz);
#endif /* def MPZ_MDIV_BUG else */
#ifdef MPZ_TEST_DIV
	fputs("mpz_divide: mdiv result", stderr);
	mpz_out_str(stderr, 10, &z->mpz);
	putc('\n', stderr);
#endif /* def MPZ_TEST_DIV */
	return (PyObject *)z;

} /* mpz_divide() */

static PyObject *
mpz_remainder(mpzobject *a, mpzobject *b)
{
#ifdef MPZ_SPARE_MALLOC
	int cmpres;
#endif /* def MPZ_SPARE_MALLOC */	
	mpzobject *z;


	if ((
#ifdef MPZ_SPARE_MALLOC	     
	     cmpres =
#endif /* def MPZ_SPARE_MALLOC */	
	     mpz_cmp_ui(&b->mpz, (unsigned long int)0)) == 0) {
		PyErr_SetString(PyExc_ZeroDivisionError, "mpz.% by zero");
		return NULL;
	}
#ifdef MPZ_SPARE_MALLOC
	if (cmpres > 0) {
		if ((cmpres = mpz_cmp_ui(&b->mpz, (unsigned long int)2)) == 0)
		{
			Py_INCREF(mpz_value_one);
			return (PyObject *)mpz_value_one;
		}
		if (cmpres < 0) {
			/* b must be 1 now */
			Py_INCREF(mpz_value_zero);
			return (PyObject *)mpz_value_zero;
		}
	}
#endif /* def MPZ_SPARE_MALLOC */	

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

#ifdef MPZ_TEST_DIV
	fputs("mpz_remain:  mod result", stderr);
	mpz_mod(&z->mpz, &a->mpz, &b->mpz);
	mpz_out_str(stderr, 10, &z->mpz);
	putc('\n', stderr);
#endif /* def MPZ_TEST_DIV */
#ifdef MPZ_MDIV_BUG

	/* the ``naive'' implementation does it right for operands
	   having the same sign */
	mpz_mod(&z->mpz, &a->mpz, &b->mpz);

	/* assumption: z, a and b all point to different locations */
	if ((mpz_cmp_ui(&a->mpz, (unsigned long int)0) < 0)
	    != (mpz_cmp_ui(&b->mpz, (unsigned long int)0) < 0)
	    && mpz_cmp_ui(&z->mpz, (unsigned long int)0) != 0)
		mpz_add(&z->mpz, &z->mpz, &b->mpz);
		/*
		** numerator has other sign than denominator: we have
		** to look at the remainder for a correction, since mpz_mdiv
		** also calls mpz_divmod, I can as well do it myself
		*/
#else /* def MPZ_MDIV_BUG */
	mpz_mmod(&z->mpz, &a->mpz, &b->mpz);
#endif /* def MPZ_MDIV_BUG else */
#ifdef MPZ_TEST_DIV
	fputs("mpz_remain: mmod result", stderr);
	mpz_out_str(stderr, 10, &z->mpz);
	putc('\n', stderr);
#endif /* def MPZ_TEST_DIV */
	return (PyObject *)z;

} /* mpz_remainder() */

static PyObject *
mpz_div_and_mod(mpzobject *a, mpzobject *b)
{
	PyObject *z = NULL;
	mpzobject *x = NULL, *y = NULL;


	if (mpz_cmp_ui(&b->mpz, (unsigned long int)0) == 0) {
		PyErr_SetString(PyExc_ZeroDivisionError, "mpz.divmod by zero");
		return NULL;
	}

	if ((z = PyTuple_New(2)) == NULL
	    || (x = newmpzobject()) == NULL
	    || (y = newmpzobject()) == NULL) {
		Py_XDECREF(z);
		Py_XDECREF(x);
		Py_XDECREF(y);
		return NULL;
	}

#ifdef MPZ_TEST_DIV
	fputs("mpz_divmod:  dm  result", stderr);
	mpz_divmod(&x->mpz, &y->mpz, &a->mpz, &b->mpz);
	mpz_out_str(stderr, 10, &x->mpz);
	putc('\n', stderr);
	mpz_out_str(stderr, 10, &y->mpz);
	putc('\n', stderr);
#endif /* def MPZ_TEST_DIV */
#ifdef MPZ_MDIV_BUG
	mpz_divmod(&x->mpz, &y->mpz, &a->mpz, &b->mpz);
	if ((mpz_cmp_ui(&a->mpz, (unsigned long int)0) < 0)
	    != (mpz_cmp_ui(&b->mpz, (unsigned long int)0) < 0)
	    && mpz_cmp_ui(&y->mpz, (unsigned long int)0) != 0) {
		/*
		** numerator has other sign than denominator: we have
		** to look at the remainder for a correction.
		*/
		mpz_add(&y->mpz, &y->mpz, &b->mpz);
		mpz_sub_ui(&x->mpz, &x->mpz, (unsigned long int)1);
	}
#else /* def MPZ_MDIV_BUG */
	mpz_mdivmod( &x->mpz, &y->mpz, &a->mpz, &b->mpz );
#endif /* def MPZ_MDIV_BUG else */
#ifdef MPZ_TEST_DIV
	fputs("mpz_divmod: mdm  result", stderr);
	mpz_out_str(stderr, 10, &x->mpz);
	putc('\n', stderr);
	mpz_out_str(stderr, 10, &y->mpz);
	putc('\n', stderr);
#endif /* def MPZ_TEST_DIV */

	(void)PyTuple_SetItem(z, 0, (PyObject *)x);
	(void)PyTuple_SetItem(z, 1, (PyObject *)y);

	return z;
} /* mpz_div_and_mod() */

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

 	if ((PyObject *)m != Py_None) {
		mpzobject *z2;
		Py_INCREF(Py_None);
		z=(mpzobject *)mpz_power(a, b, (mpzobject *)Py_None);
		Py_DECREF(Py_None);
		if (z==NULL) return((PyObject *)z);
		z2=(mpzobject *)mpz_remainder(z, m);
		Py_DECREF(z);
		return((PyObject *)z2);
	}	    

	if ((cmpres = mpz_cmp_ui(&b->mpz, (unsigned long int)0)) == 0) {
		/* the gnu-mp lib sets pow(0,0) to 0, we to 1 */

		Py_INCREF(mpz_value_one);
		return (PyObject *)mpz_value_one;
	}

	if (cmpres < 0) {
		PyErr_SetString(PyExc_ValueError,
				"mpz.pow to negative exponent");
		return NULL;
	}

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

		Py_INCREF(mpz_value_zero);
		return (PyObject *)mpz_value_zero;
	}