?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
This commit was manufactured by cvs2svn to create tag 'r221c2'.
[python/dscho.git] / Modules / mpzmodule.c
blob5c4d5cc8a6959a362cb9f0d56be77afd77379c8b
1
2 /* MPZ module */
3
4 /* This module provides an interface to an alternate Multi-Precision
5 library, GNU MP in this case */
6
7 /* XXX note: everywhere where mpz_size is called,
8 sizeof (limb) == sizeof (long) has been assumed. */
9
10
11 /* MPZ objects */
12
13 #include "Python.h"
14
15 #include <sys/types.h> /* For size_t */
16
17 /*
18 ** These are the cpp-flags used in this file...
19 **
20 **
21 ** MPZ_MDIV_BUG works around the mpz_m{div,mod,...} routines.
22 ** This bug has been fixed in a later release of
23 ** GMP.
24 **
25 ** MPZ_GET_STR_BUG mpz_get_str corrupts memory, seems to be fixed
26 ** in a later release
27 **
28 ** MPZ_DEBUG generates a bunch of diagnostic messages
29 **
30 ** MPZ_SPARE_MALLOC if set, results in extra code that tries to
31 ** minimize the creation of extra objects.
32 **
33 ** MPZ_TEST_DIV extra diagnostic output on stderr, when division
34 ** routines are involved
35 **
36 ** MPZ_LIB_DOES_CHECKING if set, assumes that mpz library doesn't call
37 ** alloca with arg < 0 (when casted to a signed
38 ** integral type).
39 **
40 ** MPZ_CONVERSIONS_AS_METHODS if set, presents the conversions as
41 ** methods. e.g., `mpz(5).long() == 5L'
42 ** Later, Guido provided an interface to the
43 ** standard functions. So this flag has no been
44 ** cleared, and `long(mpz(5)) == 5L'
45 **
46 ** MP_TEST_ALLOC If set, you would discover why MPZ_GET_STR_BUG
47 ** is needed
48 **
49 ** MAKEDUMMYINT Must be set if dynamic linking will be used
50 */
51
52
53 /*
54 ** IMHO, mpz_m{div,mod,divmod}() do the wrong things when the denominator < 0
55 ** This has been fixed with gmp release 2.0
56 */
57 /*#define MPZ_MDIV_BUG fixed the (for me) nexessary parts in libgmp.a */
58 /*
59 ** IMO, mpz_get_str() assumes a bit too large target space, if he doesn't
60 ** allocate it himself
61 */
62
63 #include "gmp.h"
64
65 #if __GNU_MP__ + 0 >= 2
66 #define GMP2
67 #define BITS_PER_MP_LIMB mp_bits_per_limb
68 #else
69 #define MPZ_GET_STR_BUG
70 #include "gmp-mparam.h"
71 #endif
72
73 typedef struct {
74 PyObject_HEAD
75 MP_INT mpz; /* the actual number */
76 } mpzobject;
77
78 staticforward PyTypeObject MPZtype;
79
80 #define is_mpzobject(v) ((v)->ob_type == &MPZtype)
81
82 static const char initialiser_name[] = "mpz";
83
84 /* #define MPZ_DEBUG */
85
86 static mpzobject *
87 newmpzobject(void)
88 {
89 mpzobject *mpzp;
90
91
92 #ifdef MPZ_DEBUG
93 fputs( "mpz_object() called...\n", stderr );
94 #endif /* def MPZ_DEBUG */
95 mpzp = PyObject_New(mpzobject, &MPZtype);
96 if (mpzp == NULL)
97 return NULL;
98
99 mpz_init(&mpzp->mpz); /* actual initialisation */
100 return mpzp;
101 } /* newmpzobject() */
102
103 #ifdef MPZ_GET_STR_BUG
104 #include "longlong.h"
105 #endif /* def MPZ_GET_STR_BUG */
106
107 static PyObject *
108 mpz_format(PyObject *objp, int base, unsigned char withname)
109 {
110 mpzobject *mpzp = (mpzobject *)objp;
111 PyStringObject *strobjp;
112 size_t i;
113 int cmpres;
114 int taglong;
115 char *cp;
116 char prefix[5], *tcp;
117
118
119 tcp = &prefix[0];
120
121 if (mpzp == NULL || !is_mpzobject(mpzp)) {
122 PyErr_BadInternalCall();
123 return NULL;
124 }
125
126 assert(base >= 2 && base <= 36);
127
128 if (withname)
129 i = strlen(initialiser_name) + 2; /* e.g. 'mpz(' + ')' */
130 else
131 i = 0;
132
133 if ((cmpres = mpz_cmp_si(&mpzp->mpz, 0L)) == 0)
134 base = 10; /* '0' in every base, right */
135 else if (cmpres < 0) {
136 *tcp++ = '-';
137 i += 1; /* space to hold '-' */
138 }
139
140 #ifdef MPZ_DEBUG
141 fprintf(stderr, "mpz_format: mpz_sizeinbase %d\n",
142 (int)mpz_sizeinbase(&mpzp->mpz, base));
143 #endif /* def MPZ_DEBUG */
144 #ifdef MPZ_GET_STR_BUG
145 #ifdef GMP2
146 i += ((size_t) abs(mpzp->mpz._mp_size) * BITS_PER_MP_LIMB
147 * __mp_bases[base].chars_per_bit_exactly) + 1;
148 #else
149 i += ((size_t) abs(mpzp->mpz.size) * BITS_PER_MP_LIMB
150 * __mp_bases[base].chars_per_bit_exactly) + 1;
151 #endif
152 #else /* def MPZ_GET_STR_BUG */
153 i += (int)mpz_sizeinbase(&mpzp->mpz, base);
154 #endif /* def MPZ_GET_STR_BUG else */
155
156 if (base == 16) {
157 *tcp++ = '0';
158 *tcp++ = 'x';
159 i += 2; /* space to hold '0x' */
160 }
161 else if (base == 8) {
162 *tcp++ = '0';
163 i += 1; /* space to hold the extra '0' */
164 }
165 else if (base > 10) {
166 *tcp++ = '0' + base / 10;
167 *tcp++ = '0' + base % 10;
168 *tcp++ = '#';
169 i += 3; /* space to hold e.g. '12#' */
170 }
171 else if (base < 10) {
172 *tcp++ = '0' + base;
173 *tcp++ = '#';
174 i += 2; /* space to hold e.g. '6#' */
175 }
176
177 /*
178 ** the following code looks if we need a 'L' attached to the number
179 ** it will also attach an 'L' to the value -0x80000000
180 */
181 taglong = 0;
182 if (mpz_size(&mpzp->mpz) > 1
183 || (long)mpz_get_ui(&mpzp->mpz) < 0L) {
184 taglong = 1;
185 i += 1; /* space to hold 'L' */
186 }
187
188 #ifdef MPZ_DEBUG
189 fprintf(stderr, "mpz_format: requesting string size %d\n", i);
190 #endif /* def MPZ_DEBUG */
191 if ((strobjp =
192 (PyStringObject *)PyString_FromStringAndSize((char *)0, i))
193 == NULL)
194 return NULL;
195
196 /* get the beginning of the string memory and start copying things */
197 cp = PyString_AS_STRING(strobjp);
198 if (withname) {
199 strcpy(cp, initialiser_name);
200 cp += strlen(initialiser_name);
201 *cp++ = '('; /*')'*/
202 }
203
204 /* copy the already prepared prefix; e.g. sign and base indicator */
205 *tcp = '\0';
206 strcpy(cp, prefix);
207 cp += tcp - prefix;
208
209 /* since' we have the sign already, let the lib think it's a positive
210 number */
211 if (cmpres < 0)
212 mpz_neg(&mpzp->mpz,&mpzp->mpz); /* hack Hack HAck HACk HACK */
213 (void)mpz_get_str(cp, base, &mpzp->mpz);
214 if (cmpres < 0)
215 mpz_neg(&mpzp->mpz,&mpzp->mpz); /* hack Hack HAck HACk HACK */
216 #ifdef MPZ_DEBUG
217 fprintf(stderr, "mpz_format: base (ultim) %d, mpz_get_str: %s\n",
218 base, cp);
219 #endif /* def MPZ_DEBUG */
220 cp += strlen(cp);
221
222 if (taglong)
223 *cp++ = 'L';
224 if (withname)
225 *cp++ = /*'('*/ ')';
226
227 *cp = '\0';
228
229 #ifdef MPZ_DEBUG
230 fprintf(stderr,
231 "mpz_format: cp (str end) %p, begin %p, diff %d, i %d\n",
232 cp, PyString_AS_STRING(strobjp),
233 cp - PyString_AS_STRING(strobjp), i);
234 #endif /* def MPZ_DEBUG */
235 assert(cp - PyString_AS_STRING(strobjp) <= i);
236
237 if (cp - PyString_AS_STRING(strobjp) != i) {
238 strobjp->ob_size -= i - (cp - PyString_AS_STRING(strobjp));
239 }
240
241 return (PyObject *)strobjp;
242 } /* mpz_format() */
243
244 /* MPZ methods */
245
246 static void
247 mpz_dealloc(mpzobject *mpzp)
248 {
249 #ifdef MPZ_DEBUG
250 fputs( "mpz_dealloc() called...\n", stderr );
251 #endif /* def MPZ_DEBUG */
252 mpz_clear(&mpzp->mpz);
253 PyObject_Del(mpzp);
254 } /* mpz_dealloc() */
255
256
257 /* pointers to frequently used values 0, 1 and -1 */
258 static mpzobject *mpz_value_zero, *mpz_value_one, *mpz_value_mone;
259
260 static int
261 mpz_compare(mpzobject *a, mpzobject *b)
262 {
263 int cmpres;
264
265
266 /* guido sez it's better to return -1, 0 or 1 */
267 return (cmpres = mpz_cmp( &a->mpz, &b->mpz )) == 0 ? 0
268 : cmpres > 0 ? 1 : -1;
269 } /* mpz_compare() */
270
271 static PyObject *
272 mpz_addition(mpzobject *a, mpzobject *b)
273 {
274 mpzobject *z;
275
276
277 #ifdef MPZ_SPARE_MALLOC
278 if (mpz_cmp_ui(&a->mpz, (unsigned long int)0) == 0) {
279 Py_INCREF(b);
280 return (PyObject *)b;
281 }
282
283 if (mpz_cmp_ui(&b->mpz, (unsigned long int)0) == 0) {
284 Py_INCREF(a);
285 return (PyObject *)a;
286 }
287 #endif /* def MPZ_SPARE_MALLOC */
288
289 if ((z = newmpzobject()) == NULL)
290 return NULL;
291
292 mpz_add(&z->mpz, &a->mpz, &b->mpz);
293 return (PyObject *)z;
294 } /* mpz_addition() */
295
296 static PyObject *
297 mpz_substract(mpzobject *a, mpzobject *b)
298 {
299 mpzobject *z;
300
301
302 #ifdef MPZ_SPARE_MALLOC
303 if (mpz_cmp_ui(&b->mpz, (unsigned long int)0) == 0) {
304 Py_INCREF(a);
305 return (PyObject *)a;
306 }
307 #endif /* MPZ_SPARE_MALLOC */
308
309 if ((z = newmpzobject()) == NULL)
310 return NULL;
311
312 mpz_sub(&z->mpz, &a->mpz, &b->mpz);
313 return (PyObject *)z;
314 } /* mpz_substract() */
315
316 static PyObject *
317 mpz_multiply(mpzobject *a, mpzobject *b)
318 {
319 #ifdef MPZ_SPARE_MALLOC
320 int cmpres;
321 #endif /* def MPZ_SPARE_MALLOC */
322 mpzobject *z;
323
324
325 #ifdef MPZ_SPARE_MALLOC
326 if ((cmpres = mpz_cmp_ui(&a->mpz, (unsigned long int)0)) == 0) {
327 Py_INCREF(mpz_value_zero);
328 return (PyObject *)mpz_value_zero;
329 }
330 if (cmpres > 0 && mpz_cmp_ui(&a->mpz, (unsigned long int)1) == 0) {
331 Py_INCREF(b);
332 return (PyObject *)b;
333 }
334
335 if ((cmpres = mpz_cmp_ui(&b->mpz, (unsigned long_int)0)) == 0) {
336 Py_INCREF(mpz_value_zero);
337 return (PyObject *)mpz_value_zero;
338 }
339 if (cmpres > 0 && mpz_cmp_ui(&b->mpz, (unsigned long int)1) == 0) {
340 Py_INCREF(a);
341 return (PyObject *)a;
342 }
343 #endif /* MPZ_SPARE_MALLOC */
344
345 if ((z = newmpzobject()) == NULL)
346 return NULL;
347
348 mpz_mul( &z->mpz, &a->mpz, &b->mpz );
349 return (PyObject *)z;
350
351 } /* mpz_multiply() */
352
353 static PyObject *
354 mpz_divide(mpzobject *a, mpzobject *b)
355 {
356 #ifdef MPZ_SPARE_MALLOC
357 int cmpres;
358 #endif /* def MPZ_SPARE_MALLOC */
359 mpzobject *z;
360
361
362 if ((
363 #ifdef MPZ_SPARE_MALLOC
364 cmpres =
365 #endif /* def MPZ_SPARE_MALLOC */
366 mpz_cmp_ui(&b->mpz, (unsigned long int)0)) == 0) {
367 PyErr_SetString(PyExc_ZeroDivisionError, "mpz./ by zero");
368 return NULL;
369 }
370 #ifdef MPZ_SPARE_MALLOC
371 if (cmpres > 0 && mpz_cmp_ui(&b->mpz(unsigned long int)1) == 0) {
372 Py_INCREF(a);
373 return (PyObject *)a;
374 }
375 #endif /* def MPZ_SPARE_MALLOC */
376
377 if ((z = newmpzobject()) == NULL)
378 return NULL;
379
380 #ifdef MPZ_TEST_DIV
381 fputs("mpz_divide: div result", stderr);
382 mpz_div(&z->mpz, &a->mpz, &b->mpz);
383 mpz_out_str(stderr, 10, &z->mpz);
384 putc('\n', stderr);
385 #endif /* def MPZ_TEST_DIV */
386 #ifdef MPZ_MDIV_BUG
387 if ((mpz_cmp_ui(&a->mpz, (unsigned long int)0) < 0)
388 != (mpz_cmp_ui(&b->mpz, (unsigned long int)0) < 0)) {
389 /*
390 ** numerator has other sign than denominator: we have
391 ** to look at the remainder for a correction, since mpz_mdiv
392 ** also calls mpz_divmod, I can as well do it myself
393 */
394 MP_INT tmpmpz;
395
396
397 mpz_init(&tmpmpz);
398 mpz_divmod(&z->mpz, &tmpmpz, &a->mpz, &b->mpz);
399
400 if (mpz_cmp_ui(&tmpmpz, (unsigned long int)0) != 0)
401 mpz_sub_ui(&z->mpz, &z->mpz, (unsigned long int)1);
402
403 mpz_clear(&tmpmpz);
404 }
405 else
406 mpz_div(&z->mpz, &a->mpz, &b->mpz);
407 /* the ``naive'' implementation does it right for operands
408 having the same sign */
409
410 #else /* def MPZ_MDIV_BUG */
411 mpz_mdiv(&z->mpz, &a->mpz, &b->mpz);
412 #endif /* def MPZ_MDIV_BUG else */
413 #ifdef MPZ_TEST_DIV
414 fputs("mpz_divide: mdiv result", stderr);
415 mpz_out_str(stderr, 10, &z->mpz);
416 putc('\n', stderr);
417 #endif /* def MPZ_TEST_DIV */
418 return (PyObject *)z;
419
420 } /* mpz_divide() */
421
422 static PyObject *
423 mpz_remainder(mpzobject *a, mpzobject *b)
424 {
425 #ifdef MPZ_SPARE_MALLOC
426 int cmpres;
427 #endif /* def MPZ_SPARE_MALLOC */
428 mpzobject *z;
429
430
431 if ((
432 #ifdef MPZ_SPARE_MALLOC
433 cmpres =
434 #endif /* def MPZ_SPARE_MALLOC */
435 mpz_cmp_ui(&b->mpz, (unsigned long int)0)) == 0) {
436 PyErr_SetString(PyExc_ZeroDivisionError, "mpz.% by zero");
437 return NULL;
438 }
439 #ifdef MPZ_SPARE_MALLOC
440 if (cmpres > 0) {
441 if ((cmpres = mpz_cmp_ui(&b->mpz, (unsigned long int)2)) == 0)
442 {
443 Py_INCREF(mpz_value_one);
444 return (PyObject *)mpz_value_one;
445 }
446 if (cmpres < 0) {
447 /* b must be 1 now */
448 Py_INCREF(mpz_value_zero);
449 return (PyObject *)mpz_value_zero;
450 }
451 }
452 #endif /* def MPZ_SPARE_MALLOC */
453
454 if ((z = newmpzobject()) == NULL)
455 return NULL;
456
457 #ifdef MPZ_TEST_DIV
458 fputs("mpz_remain: mod result", stderr);
459 mpz_mod(&z->mpz, &a->mpz, &b->mpz);
460 mpz_out_str(stderr, 10, &z->mpz);
461 putc('\n', stderr);
462 #endif /* def MPZ_TEST_DIV */
463 #ifdef MPZ_MDIV_BUG
464
465 /* the ``naive'' implementation does it right for operands
466 having the same sign */
467 mpz_mod(&z->mpz, &a->mpz, &b->mpz);
468
469 /* assumption: z, a and b all point to different locations */
470 if ((mpz_cmp_ui(&a->mpz, (unsigned long int)0) < 0)
471 != (mpz_cmp_ui(&b->mpz, (unsigned long int)0) < 0)
472 && mpz_cmp_ui(&z->mpz, (unsigned long int)0) != 0)
473 mpz_add(&z->mpz, &z->mpz, &b->mpz);
474 /*
475 ** numerator has other sign than denominator: we have
476 ** to look at the remainder for a correction, since mpz_mdiv
477 ** also calls mpz_divmod, I can as well do it myself
478 */
479 #else /* def MPZ_MDIV_BUG */
480 mpz_mmod(&z->mpz, &a->mpz, &b->mpz);
481 #endif /* def MPZ_MDIV_BUG else */
482 #ifdef MPZ_TEST_DIV
483 fputs("mpz_remain: mmod result", stderr);
484 mpz_out_str(stderr, 10, &z->mpz);
485 putc('\n', stderr);
486 #endif /* def MPZ_TEST_DIV */
487 return (PyObject *)z;
488
489 } /* mpz_remainder() */
490
491 static PyObject *
492 mpz_div_and_mod(mpzobject *a, mpzobject *b)
493 {
494 PyObject *z = NULL;
495 mpzobject *x = NULL, *y = NULL;
496
497
498 if (mpz_cmp_ui(&b->mpz, (unsigned long int)0) == 0) {
499 PyErr_SetString(PyExc_ZeroDivisionError, "mpz.divmod by zero");
500 return NULL;
501 }
502
503 if ((z = PyTuple_New(2)) == NULL
504 || (x = newmpzobject()) == NULL
505 || (y = newmpzobject()) == NULL) {
506 Py_XDECREF(z);
507 Py_XDECREF(x);
508 Py_XDECREF(y);
509 return NULL;
510 }
511
512 #ifdef MPZ_TEST_DIV
513 fputs("mpz_divmod: dm result", stderr);
514 mpz_divmod(&x->mpz, &y->mpz, &a->mpz, &b->mpz);
515 mpz_out_str(stderr, 10, &x->mpz);
516 putc('\n', stderr);
517 mpz_out_str(stderr, 10, &y->mpz);
518 putc('\n', stderr);
519 #endif /* def MPZ_TEST_DIV */
520 #ifdef MPZ_MDIV_BUG
521 mpz_divmod(&x->mpz, &y->mpz, &a->mpz, &b->mpz);
522 if ((mpz_cmp_ui(&a->mpz, (unsigned long int)0) < 0)
523 != (mpz_cmp_ui(&b->mpz, (unsigned long int)0) < 0)
524 && mpz_cmp_ui(&y->mpz, (unsigned long int)0) != 0) {
525 /*
526 ** numerator has other sign than denominator: we have
527 ** to look at the remainder for a correction.
528 */
529 mpz_add(&y->mpz, &y->mpz, &b->mpz);
530 mpz_sub_ui(&x->mpz, &x->mpz, (unsigned long int)1);
531 }
532 #else /* def MPZ_MDIV_BUG */
533 mpz_mdivmod( &x->mpz, &y->mpz, &a->mpz, &b->mpz );
534 #endif /* def MPZ_MDIV_BUG else */
535 #ifdef MPZ_TEST_DIV
536 fputs("mpz_divmod: mdm result", stderr);
537 mpz_out_str(stderr, 10, &x->mpz);
538 putc('\n', stderr);
539 mpz_out_str(stderr, 10, &y->mpz);
540 putc('\n', stderr);
541 #endif /* def MPZ_TEST_DIV */
542
543 (void)PyTuple_SetItem(z, 0, (PyObject *)x);
544 (void)PyTuple_SetItem(z, 1, (PyObject *)y);
545
546 return z;
547 } /* mpz_div_and_mod() */
548
549 static PyObject *
550 mpz_power(mpzobject *a, mpzobject *b, mpzobject *m)
551 {
552 mpzobject *z;
553 int cmpres;
554
555 if ((PyObject *)m != Py_None) {
556 mpzobject *z2;
557 Py_INCREF(Py_None);
558 z=(mpzobject *)mpz_power(a, b, (mpzobject *)Py_None);
559 Py_DECREF(Py_None);
560 if (z==NULL) return((PyObject *)z);
561 z2=(mpzobject *)mpz_remainder(z, m);
562 Py_DECREF(z);
563 return((PyObject *)z2);
564 }
565
566 if ((cmpres = mpz_cmp_ui(&b->mpz, (unsigned long int)0)) == 0) {
567 /* the gnu-mp lib sets pow(0,0) to 0, we to 1 */
568
569 Py_INCREF(mpz_value_one);
570 return (PyObject *)mpz_value_one;
571 }
572
573 if (cmpres < 0) {
574 PyErr_SetString(PyExc_ValueError,
575 "mpz.pow to negative exponent");
576 return NULL;
577 }
578
579 if ((cmpres = mpz_cmp_ui(&a->mpz, (unsigned long int)0)) == 0) {
580 /* the base is 0 */
581
582 Py_INCREF(mpz_value_zero);
583 return (PyObject *)mpz_value_zero;
584 }
585 else if (cmpres > 0
586 && mpz_cmp_ui(&a->mpz, (unsigned long int)1) == 0) {
587 /* the base is 1 */
588
589 Py_INCREF(mpz_value_one);
590 return (PyObject *)mpz_value_one;
591 }
592 else if (cmpres < 0
593 && mpz_cmp_si(&a->mpz, (long int)-1) == 0) {
594
595 MP_INT tmpmpz;
596 /* the base is -1: pow(-1, any) == 1,-1 for even,uneven b */
597 /* XXX this code needs to be optimized: what's better?
598 mpz_mmod_ui or mpz_mod_2exp, I choose for the latter
599 for *un*obvious reasons */
600
601 /* is the exponent even? */
602 mpz_init(&tmpmpz);
603
604 /* look to the remainder after a division by (1 << 1) */
605 mpz_mod_2exp(&tmpmpz, &b->mpz, (unsigned long int)1);
606
607 if (mpz_cmp_ui(&tmpmpz, (unsigned int)0) == 0) {
608 mpz_clear(&tmpmpz);
609 Py_INCREF(mpz_value_one);
610 return (PyObject *)mpz_value_one;
611 }
612 mpz_clear(&tmpmpz);
613 Py_INCREF(mpz_value_mone);
614 return (PyObject *)mpz_value_mone;
615 }
616
617 #ifdef MPZ_LIB_DOES_CHECKING
618 /* check if it's doable: sizeof(exp) > sizeof(long) &&
619 abs(base) > 1 ?? --> No Way */
620 if (mpz_size(&b->mpz) > 1)
621 return (PyObject *)PyErr_NoMemory();
622 #else /* def MPZ_LIB_DOES_CHECKING */
623 /* wet finger method */
624 if (mpz_cmp_ui(&b->mpz, (unsigned long int)0x10000) >= 0) {
625 PyErr_SetString(PyExc_ValueError,
626 "mpz.pow outrageous exponent");
627 return NULL;
628 }
629 #endif /* def MPZ_LIB_DOES_CHECKING else */
630
631 if ((z = newmpzobject()) == NULL)
632 return NULL;
633
634 mpz_pow_ui(&z->mpz, &a->mpz, mpz_get_ui(&b->mpz));
635
636 return (PyObject *)z;
637 } /* mpz_power() */
638
639
640 static PyObject *
641 mpz_negative(mpzobject *v)
642 {
643 mpzobject *z;
644
645
646 #ifdef MPZ_SPARE_MALLOC
647 if (mpz_cmp_ui(&v->mpz, (unsigned long int)0) == 0) {
648 /* -0 == 0 */
649 Py_INCREF(v);
650 return (PyObject *)v;
651 }
652 #endif /* def MPZ_SPARE_MALLOC */
653
654 if ((z = newmpzobject()) == NULL)
655 return NULL;
656
657 mpz_neg(&z->mpz, &v->mpz);
658 return (PyObject *)z;
659 } /* mpz_negative() */
660
661
662 static PyObject *
663 mpz_positive(mpzobject *v)
664 {
665 Py_INCREF(v);
666 return (PyObject *)v;
667 } /* mpz_positive() */
668
669
670 static PyObject *
671 mpz_absolute(mpzobject *v)
672 {
673 mpzobject *z;
674
675
676 if (mpz_cmp_ui(&v->mpz, (unsigned long int)0) >= 0) {
677 Py_INCREF(v);
678 return (PyObject *)v;
679 }
680
681 if ((z = newmpzobject()) == NULL)
682 return NULL;
683
684 mpz_neg(&z->mpz, &v->mpz);
685 return (PyObject *)z;
686 } /* mpz_absolute() */
687
688 static int
689 mpz_nonzero(mpzobject *v)
690 {
691 return mpz_cmp_ui(&v->mpz, (unsigned long int)0) != 0;
692 } /* mpz_nonzero() */
693
694 static PyObject *
695 py_mpz_invert(mpzobject *v)
696 {
697 mpzobject *z;
698
699
700 /* I think mpz_com does exactly what needed */
701 if ((z = newmpzobject()) == NULL)
702 return NULL;
703
704 mpz_com(&z->mpz, &v->mpz);
705 return (PyObject *)z;
706 } /* py_mpz_invert() */
707
708 static PyObject *
709 mpz_lshift(mpzobject *a, mpzobject *b)
710 {
711 int cmpres;
712 mpzobject *z;
713
714
715 if ((cmpres = mpz_cmp_ui(&b->mpz, (unsigned long int)0)) == 0) {
716 /* a << 0 == a */
717 Py_INCREF(a);
718 return (PyObject *)a;
719 }
720
721 if (cmpres < 0) {
722 PyErr_SetString(PyExc_ValueError,
723 "mpz.<< negative shift count");
724 return NULL;
725 }
726
727 #ifdef MPZ_LIB_DOES_CHECKING
728 if (mpz_size(&b->mpz) > 1)
729 return (PyObject *)PyErr_NoMemory();
730 #else /* def MPZ_LIB_DOES_CHECKING */
731 /* wet finger method */
732 if (mpz_cmp_ui(&b->mpz, (unsigned long int)0x10000) >= 0) {
733 PyErr_SetString(PyExc_ValueError,
734 "mpz.<< outrageous shift count");
735 return NULL;
736 }
737 #endif /* def MPZ_LIB_DOES_CHECKING else */
738
739 if ((z = newmpzobject()) == NULL)
740 return NULL;
741
742 mpz_mul_2exp(&z->mpz, &a->mpz, mpz_get_ui(&b->mpz));
743 return (PyObject *)z;
744 } /* mpz_lshift() */
745
746 static PyObject *
747 mpz_rshift(mpzobject *a, mpzobject *b)
748 {
749 int cmpres;
750 mpzobject *z;
751
752
753 if ((cmpres = mpz_cmp_ui(&b->mpz, (unsigned long int)0)) == 0) {
754 /* a >> 0 == a */
755 Py_INCREF(a);
756 return (PyObject *)a;
757 }
758
759 if (cmpres < 0) {
760 PyErr_SetString(PyExc_ValueError,
761 "mpz.>> negative shift count");
762 return NULL;
763 }
764
765 if (mpz_size(&b->mpz) > 1)
766 return (PyObject *)PyErr_NoMemory();
767
768 if ((z = newmpzobject()) == NULL)
769 return NULL;
770
771 mpz_div_2exp(&z->mpz, &a->mpz, mpz_get_ui(&b->mpz));
772 return (PyObject *)z;
773 } /* mpz_rshift() */
774
775 static PyObject *
776 mpz_andfunc(mpzobject *a, mpzobject *b)
777 {
778 mpzobject *z;
779
780
781 if ((z = newmpzobject()) == NULL)
782 return NULL;
783
784 mpz_and(&z->mpz, &a->mpz, &b->mpz);
785 return (PyObject *)z;
786 } /* mpz_andfunc() */
787
788 /* hack Hack HAck HACk HACK, XXX this code is dead slow */
789 void
790 mpz_xor(MP_INT *res, const MP_INT *op1, const MP_INT *op2)
791 {
792 MP_INT tmpmpz;
793
794 mpz_init(&tmpmpz);
795
796 mpz_and(res, op1, op2);
797 mpz_com(&tmpmpz, res);
798 mpz_ior(res, op1, op2);
799 mpz_and(res, res, &tmpmpz);
800
801 mpz_clear(&tmpmpz);
802 } /* mpz_xor() HACK */
803
804 static PyObject *
805 mpz_xorfunc(mpzobject *a, mpzobject *b)
806 {
807 mpzobject *z;
808
809
810 if ((z = newmpzobject()) == NULL)
811 return NULL;
812
813 mpz_xor(&z->mpz, &a->mpz, &b->mpz);
814 return (PyObject *)z;
815 } /* mpz_xorfunc() */
816
817 static PyObject *
818 mpz_orfunc(mpzobject *a, mpzobject *b)
819 {
820 mpzobject *z;
821
822
823 if ((z = newmpzobject()) == NULL)
824 return NULL;
825
826 mpz_ior(&z->mpz, &a->mpz, &b->mpz);
827 return (PyObject *)z;
828 } /* mpz_orfunc() */
829
830 /* MPZ initialisation */
831
832 #include "longintrepr.h"
833
834 static PyObject *
835 MPZ_mpz(PyObject *self, PyObject *args)
836 {
837 mpzobject *mpzp;
838 PyObject *objp;
839
840
841 #ifdef MPZ_DEBUG
842 fputs("MPZ_mpz() called...\n", stderr);
843 #endif /* def MPZ_DEBUG */
844
845 if (!PyArg_Parse(args, "O", &objp))
846 return NULL;
847
848 /* at least we know it's some object */
849 /* note DON't Py_DECREF args NEITHER objp */
850
851 if (PyInt_Check(objp)) {
852 long lval;
853
854 if (!PyArg_Parse(objp, "l", &lval))
855 return NULL;
856
857 if (lval == (long)0) {
858 Py_INCREF(mpz_value_zero);
859 mpzp = mpz_value_zero;
860 }
861 else if (lval == (long)1) {
862 Py_INCREF(mpz_value_one);
863 mpzp = mpz_value_one;
864 }
865 else if ((mpzp = newmpzobject()) == NULL)
866 return NULL;
867 else mpz_set_si(&mpzp->mpz, lval);
868 }
869 else if (PyLong_Check(objp)) {
870 MP_INT mplongdigit;
871 int i;
872 unsigned char isnegative;
873
874
875 if ((mpzp = newmpzobject()) == NULL)
876 return NULL;
877
878 mpz_set_si(&mpzp->mpz, 0L);
879 mpz_init(&mplongdigit);
880
881 /* how we're gonna handle this? */
882 if ((isnegative =
883 ((i = ((PyLongObject *)objp)->ob_size) < 0) ))
884 i = -i;
885
886 while (i--) {
887 mpz_set_ui(&mplongdigit,
888 (unsigned long)
889 ((PyLongObject *)objp)->ob_digit[i]);
890 mpz_mul_2exp(&mplongdigit,&mplongdigit,
891 (unsigned long int)i * SHIFT);
892 mpz_ior(&mpzp->mpz, &mpzp->mpz, &mplongdigit);
893 }
894
895 if (isnegative)
896 mpz_neg(&mpzp->mpz, &mpzp->mpz);
897
898 /* get rid of allocation for tmp variable */
899 mpz_clear(&mplongdigit);
900 }
901 else if (PyString_Check(objp)) {
902 unsigned char *cp = (unsigned char *)PyString_AS_STRING(objp);
903 int len = PyString_GET_SIZE(objp);
904 MP_INT mplongdigit;
905
906 if ((mpzp = newmpzobject()) == NULL)
907 return NULL;
908
909 mpz_set_si(&mpzp->mpz, 0L);
910 mpz_init(&mplongdigit);
911
912 /* let's do it the same way as with the long conversion:
913 without thinking how it can be faster (-: :-) */
914
915 cp += len;
916 while (len--) {
917 mpz_set_ui(&mplongdigit, (unsigned long)*--cp );
918 mpz_mul_2exp(&mplongdigit,&mplongdigit,
919 (unsigned long int)len * 8);
920 mpz_ior(&mpzp->mpz, &mpzp->mpz, &mplongdigit);
921 }
922
923 /* get rid of allocation for tmp variable */
924 mpz_clear(&mplongdigit);
925 }
926 else if (is_mpzobject(objp)) {
927 Py_INCREF(objp);
928 mpzp = (mpzobject *)objp;
929 }
930 else {
931 PyErr_SetString(PyExc_TypeError,
932 "mpz.mpz() expects integer, long, string or mpz object argument");
933 return NULL;
934 }
935
936
937 #ifdef MPZ_DEBUG
938 fputs("MPZ_mpz: created mpz=", stderr);
939 mpz_out_str(stderr, 10, &mpzp->mpz);
940 putc('\n', stderr);
941 #endif /* def MPZ_DEBUG */
942 return (PyObject *)mpzp;
943 } /* MPZ_mpz() */
944
945 static mpzobject *
946 mpz_mpzcoerce(PyObject *z)
947 {
948 /* shortcut: 9 out of 10 times the type is already ok */
949 if (is_mpzobject(z)) {
950 Py_INCREF(z);
951 return (mpzobject *)z; /* coercion succeeded */
952 }
953
954 /* what types do we accept?: intobjects and longobjects */
955 if (PyInt_Check(z) || PyLong_Check(z))
956 return (mpzobject *)MPZ_mpz((PyObject *)NULL, z);
957
958 PyErr_SetString(PyExc_TypeError,
959 "number coercion (to mpzobject) failed");
960 return NULL;
961 } /* mpz_mpzcoerce() */
962
963 /* Forward */
964 static void mpz_divm(MP_INT *res, const MP_INT *num,
965 const MP_INT *den, const MP_INT *mod);
966
967 static PyObject *
968 MPZ_powm(PyObject *self, PyObject *args)
969 {
970 PyObject *base, *exp, *mod;
971 mpzobject *mpzbase = NULL, *mpzexp = NULL, *mpzmod = NULL;
972 mpzobject *z;
973 int tstres;
974
975
976 if (!PyArg_Parse(args, "(OOO)", &base, &exp, &mod))
977 return NULL;
978
979 if ((mpzbase = mpz_mpzcoerce(base)) == NULL
980 || (mpzexp = mpz_mpzcoerce(exp)) == NULL
981 || (mpzmod = mpz_mpzcoerce(mod)) == NULL
982 || (z = newmpzobject()) == NULL) {
983 Py_XDECREF(mpzbase);
984 Py_XDECREF(mpzexp);
985 Py_XDECREF(mpzmod);
986 return NULL;
987 }
988
989 if ((tstres=mpz_cmp_ui(&mpzexp->mpz, (unsigned long int)0)) == 0) {
990 Py_INCREF(mpz_value_one);
991 return (PyObject *)mpz_value_one;
992 }
993
994 if (tstres < 0) {
995 MP_INT absexp;
996 /* negative exp */
997
998 mpz_init_set(&absexp, &mpzexp->mpz);
999 mpz_abs(&absexp, &absexp);
1000 mpz_powm(&z->mpz, &mpzbase->mpz, &absexp, &mpzmod->mpz);
1001
1002 mpz_divm(&z->mpz, &mpz_value_one->mpz, &z->mpz, &mpzmod->mpz);
1003
1004 mpz_clear(&absexp);
1005 }
1006 else {
1007 mpz_powm(&z->mpz, &mpzbase->mpz, &mpzexp->mpz, &mpzmod->mpz);
1008 }
1009
1010 Py_DECREF(mpzbase);
1011 Py_DECREF(mpzexp);
1012 Py_DECREF(mpzmod);
1013
1014 return (PyObject *)z;
1015 } /* MPZ_powm() */
1016
1017
1018 static PyObject *
1019 MPZ_gcd(PyObject *self, PyObject *args)
1020 {
1021 PyObject *op1, *op2;
1022 mpzobject *mpzop1 = NULL, *mpzop2 = NULL;
1023 mpzobject *z;
1024
1025
1026 if (!PyArg_Parse(args, "(OO)", &op1, &op2))
1027 return NULL;
1028
1029 if ((mpzop1 = mpz_mpzcoerce(op1)) == NULL
1030 || (mpzop2 = mpz_mpzcoerce(op2)) == NULL
1031 || (z = newmpzobject()) == NULL) {
1032 Py_XDECREF(mpzop1);
1033 Py_XDECREF(mpzop2);
1034 return NULL;
1035 }
1036
1037 /* ok, we have three mpzobjects, and an initialised result holder */
1038 mpz_gcd(&z->mpz, &mpzop1->mpz, &mpzop2->mpz);
1039
1040 Py_DECREF(mpzop1);
1041 Py_DECREF(mpzop2);
1042
1043 return (PyObject *)z;
1044 } /* MPZ_gcd() */
1045
1046
1047 static PyObject *
1048 MPZ_gcdext(PyObject *self, PyObject *args)
1049 {
1050 PyObject *op1, *op2, *z = NULL;
1051 mpzobject *mpzop1 = NULL, *mpzop2 = NULL;
1052 mpzobject *g = NULL, *s = NULL, *t = NULL;
1053
1054
1055 if (!PyArg_Parse(args, "(OO)", &op1, &op2))
1056 return NULL;
1057
1058 if ((mpzop1 = mpz_mpzcoerce(op1)) == NULL
1059 || (mpzop2 = mpz_mpzcoerce(op2)) == NULL
1060 || (z = PyTuple_New(3)) == NULL
1061 || (g = newmpzobject()) == NULL
1062 || (s = newmpzobject()) == NULL
1063 || (t = newmpzobject()) == NULL) {
1064 Py_XDECREF(mpzop1);
1065 Py_XDECREF(mpzop2);
1066 Py_XDECREF(z);
1067 Py_XDECREF(g);
1068 Py_XDECREF(s);
1069 /*Py_XDECREF(t);*/
1070 return NULL;
1071 }
1072
1073 mpz_gcdext(&g->mpz, &s->mpz, &t->mpz, &mpzop1->mpz, &mpzop2->mpz);
1074
1075 Py_DECREF(mpzop1);
1076 Py_DECREF(mpzop2);
1077
1078 (void)PyTuple_SetItem(z, 0, (PyObject *)g);
1079 (void)PyTuple_SetItem(z, 1, (PyObject *)s);
1080 (void)PyTuple_SetItem(z, 2, (PyObject *)t);
1081
1082 return (PyObject *)z;
1083 } /* MPZ_gcdext() */
1084
1085
1086 static PyObject *
1087 MPZ_sqrt(PyObject *self, PyObject *args)
1088 {
1089 PyObject *op;
1090 mpzobject *mpzop = NULL;
1091 mpzobject *z;
1092
1093
1094 if (!PyArg_Parse(args, "O", &op))
1095 return NULL;
1096
1097 if ((mpzop = mpz_mpzcoerce(op)) == NULL
1098 || (z = newmpzobject()) == NULL) {
1099 Py_XDECREF(mpzop);
1100 return NULL;
1101 }
1102
1103 mpz_sqrt(&z->mpz, &mpzop->mpz);
1104
1105 Py_DECREF(mpzop);
1106
1107 return (PyObject *)z;
1108 } /* MPZ_sqrt() */
1109
1110
1111 static PyObject *
1112 MPZ_sqrtrem(PyObject *self, PyObject *args)
1113 {
1114 PyObject *op, *z = NULL;
1115 mpzobject *mpzop = NULL;
1116 mpzobject *root = NULL, *rem = NULL;
1117
1118
1119 if (!PyArg_Parse(args, "O", &op))
1120 return NULL;
1121
1122 if ((mpzop = mpz_mpzcoerce(op)) == NULL
1123 || (z = PyTuple_New(2)) == NULL
1124 || (root = newmpzobject()) == NULL
1125 || (rem = newmpzobject()) == NULL) {
1126 Py_XDECREF(mpzop);
1127 Py_XDECREF(z);
1128 Py_XDECREF(root);
1129 /*Py_XDECREF(rem);*/
1130 return NULL;
1131 }
1132
1133 mpz_sqrtrem(&root->mpz, &rem->mpz, &mpzop->mpz);
1134
1135 Py_DECREF(mpzop);
1136
1137 (void)PyTuple_SetItem(z, 0, (PyObject *)root);
1138 (void)PyTuple_SetItem(z, 1, (PyObject *)rem);
1139
1140 return (PyObject *)z;
1141 } /* MPZ_sqrtrem() */
1142
1143
1144 static void
1145 mpz_divm(MP_INT *res, const MP_INT *num, const MP_INT *den, const MP_INT *mod)
1146 {
1147 MP_INT s0, s1, q, r, x, d0, d1;
1148
1149 mpz_init_set(&s0, num);
1150 mpz_init_set_ui(&s1, 0);
1151 mpz_init(&q);
1152 mpz_init(&r);
1153 mpz_init(&x);
1154 mpz_init_set(&d0, den);
1155 mpz_init_set(&d1, mod);
1156
1157 #ifdef GMP2
1158 while (d1._mp_size != 0) {
1159 #else
1160 while (d1.size != 0) {
1161 #endif
1162 mpz_divmod(&q, &r, &d0, &d1);
1163 mpz_set(&d0, &d1);
1164 mpz_set(&d1, &r);
1165
1166 mpz_mul(&x, &s1, &q);
1167 mpz_sub(&x, &s0, &x);
1168 mpz_set(&s0, &s1);
1169 mpz_set(&s1, &x);
1170 }
1171
1172 #ifdef GMP2
1173 if (d0._mp_size != 1 || d0._mp_d[0] != 1)
1174 res->_mp_size = 0; /* trouble: the gcd != 1; set s to zero */
1175 #else
1176 if (d0.size != 1 || d0.d[0] != 1)
1177 res->size = 0; /* trouble: the gcd != 1; set s to zero */
1178 #endif
1179 else {
1180 #ifdef MPZ_MDIV_BUG
1181 /* watch out here! first check the signs, and then perform
1182 the mpz_mod() since mod could point to res */
1183 if ((s0.size < 0) != (mod->size < 0)) {
1184 mpz_mod(res, &s0, mod);
1185
1186 if (res->size)
1187 mpz_add(res, res, mod);
1188 }
1189 else
1190 mpz_mod(res, &s0, mod);
1191
1192 #else /* def MPZ_MDIV_BUG */
1193 mpz_mmod(res, &s0, mod);
1194 #endif /* def MPZ_MDIV_BUG else */
1195 }
1196
1197 mpz_clear(&s0);
1198 mpz_clear(&s1);
1199 mpz_clear(&q);
1200 mpz_clear(&r);
1201 mpz_clear(&x);
1202 mpz_clear(&d0);
1203 mpz_clear(&d1);
1204 } /* mpz_divm() */
1205
1206
1207 static PyObject *
1208 MPZ_divm(PyObject *self, PyObject *args)
1209 {
1210 PyObject *num, *den, *mod;
1211 mpzobject *mpznum, *mpzden = NULL, *mpzmod = NULL;
1212 mpzobject *z = NULL;
1213
1214
1215 if (!PyArg_Parse(args, "(OOO)", &num, &den, &mod))
1216 return NULL;
1217
1218 if ((mpznum = mpz_mpzcoerce(num)) == NULL
1219 || (mpzden = mpz_mpzcoerce(den)) == NULL
1220 || (mpzmod = mpz_mpzcoerce(mod)) == NULL
1221 || (z = newmpzobject()) == NULL ) {
1222 Py_XDECREF(mpznum);
1223 Py_XDECREF(mpzden);
1224 Py_XDECREF(mpzmod);
1225 return NULL;
1226 }
1227
1228 mpz_divm(&z->mpz, &mpznum->mpz, &mpzden->mpz, &mpzmod->mpz);
1229
1230 Py_DECREF(mpznum);
1231 Py_DECREF(mpzden);
1232 Py_DECREF(mpzmod);
1233
1234 if (mpz_cmp_ui(&z->mpz, (unsigned long int)0) == 0) {
1235 Py_DECREF(z);
1236 PyErr_SetString(PyExc_ValueError,
1237 "gcd(den, mod) != 1 or num == 0");
1238 return NULL;
1239 }
1240
1241 return (PyObject *)z;
1242 } /* MPZ_divm() */
1243
1244
1245 /* MPZ methods-as-attributes */
1246 #ifdef MPZ_CONVERSIONS_AS_METHODS
1247 static PyObject *
1248 mpz_int(mpzobject *self, PyObject *args)
1249 #else /* def MPZ_CONVERSIONS_AS_METHODS */
1250 static PyObject *
1251 mpz_int(mpzobject *self)
1252 #endif /* def MPZ_CONVERSIONS_AS_METHODS else */
1253 {
1254 long sli;
1255
1256
1257 #ifdef MPZ_CONVERSIONS_AS_METHODS
1258 if (!PyArg_NoArgs(args))
1259 return NULL;
1260 #endif /* def MPZ_CONVERSIONS_AS_METHODS */
1261
1262 if (mpz_size(&self->mpz) > 1
1263 || (sli = (long)mpz_get_ui(&self->mpz)) < (long)0 ) {
1264 PyErr_SetString(PyExc_ValueError,
1265 "mpz.int() arg too long to convert");
1266 return NULL;
1267 }
1268
1269 if (mpz_cmp_ui(&self->mpz, (unsigned long)0) < 0)
1270 sli = -sli;
1271
1272 return PyInt_FromLong(sli);
1273 } /* mpz_int() */
1274
1275 static PyObject *
1276 #ifdef MPZ_CONVERSIONS_AS_METHODS
1277 mpz_long(mpzobject *self, PyObject *args)
1278 #else /* def MPZ_CONVERSIONS_AS_METHODS */
1279 mpz_long(mpzobject *self)
1280 #endif /* def MPZ_CONVERSIONS_AS_METHODS else */
1281 {
1282 int i, isnegative;
1283 unsigned long int uli;
1284 PyLongObject *longobjp;
1285 int ldcount;
1286 int bitpointer, newbitpointer;
1287 MP_INT mpzscratch;
1288
1289
1290 #ifdef MPZ_CONVERSIONS_AS_METHODS
1291 if (!PyArg_NoArgs(args))
1292 return NULL;
1293 #endif /* def MPZ_CONVERSIONS_AS_METHODS */
1294
1295 /* determine length of python-long to be allocated */
1296 if ((longobjp = _PyLong_New(i = (int)
1297 ((mpz_size(&self->mpz) * BITS_PER_MP_LIMB
1298 + SHIFT - 1) /
1299 SHIFT))) == NULL)
1300 return NULL;
1301
1302 /* determine sign, and copy self to scratch var */
1303 mpz_init_set(&mpzscratch, &self->mpz);
1304 if ((isnegative = (mpz_cmp_ui(&self->mpz, (unsigned long int)0) < 0)))
1305 mpz_neg(&mpzscratch, &mpzscratch);
1306
1307 /* let those bits come, let those bits go,
1308 e.g. dismantle mpzscratch, build PyLongObject */
1309
1310 bitpointer = 0; /* the number of valid bits in stock */
1311 newbitpointer = 0;
1312 ldcount = 0; /* the python-long limb counter */
1313 uli = (unsigned long int)0;
1314 while (i--) {
1315 longobjp->ob_digit[ldcount] = uli & MASK;
1316
1317 /* check if we've had enough bits for this digit */
1318 if (bitpointer < SHIFT) {
1319 uli = mpz_get_ui(&mpzscratch);
1320 longobjp->ob_digit[ldcount] |=
1321 (uli << bitpointer) & MASK;
1322 uli >>= SHIFT-bitpointer;
1323 bitpointer += BITS_PER_MP_LIMB;
1324 mpz_div_2exp(&mpzscratch, &mpzscratch,
1325 BITS_PER_MP_LIMB);
1326 }
1327 else
1328 uli >>= SHIFT;
1329 bitpointer -= SHIFT;
1330 ldcount++;
1331 }
1332
1333 assert(mpz_cmp_ui(&mpzscratch, (unsigned long int)0) == 0);
1334 mpz_clear(&mpzscratch);
1335 assert(ldcount <= longobjp->ob_size);
1336
1337 /* long_normalize() is file-static */
1338 /* longobjp = long_normalize(longobjp); */
1339 while (ldcount > 0 && longobjp->ob_digit[ldcount-1] == 0)
1340 ldcount--;
1341 longobjp->ob_size = ldcount;
1342
1343
1344 if (isnegative)
1345 longobjp->ob_size = -longobjp->ob_size;
1346
1347 return (PyObject *)longobjp;
1348
1349 } /* mpz_long() */
1350
1351
1352 /* I would have avoided pow() anyways, so ... */
1353 static const double multiplier = 256.0 * 256.0 * 256.0 * 256.0;
1354
1355 #ifdef MPZ_CONVERSIONS_AS_METHODS
1356 static PyObject *
1357 mpz_float(mpzobject *self, PyObject *args)
1358 #else /* def MPZ_CONVERSIONS_AS_METHODS */
1359 static PyObject *
1360 mpz_float(mpzobject *self)
1361 #endif /* def MPZ_CONVERSIONS_AS_METHODS else */
1362 {
1363 int i, isnegative;
1364 double x;
1365 double mulstate;
1366 MP_INT mpzscratch;
1367
1368
1369 #ifdef MPZ_CONVERSIONS_AS_METHODS
1370 if (!PyArg_NoArgs(args))
1371 return NULL;
1372 #endif /* def MPZ_CONVERSIONS_AS_METHODS */
1373
1374 i = (int)mpz_size(&self->mpz);
1375
1376 /* determine sign, and copy abs(self) to scratch var */
1377 if ((isnegative = (mpz_cmp_ui(&self->mpz, (unsigned long int)0) < 0)))
1378 {
1379 mpz_init(&mpzscratch);
1380 mpz_neg(&mpzscratch, &self->mpz);
1381 }
1382 else
1383 mpz_init_set(&mpzscratch, &self->mpz);
1384
1385 /* let those bits come, let those bits go,
1386 e.g. dismantle mpzscratch, build PyFloatObject */
1387
1388 /* Can this overflow? Dunno, protect against that possibility. */
1389 PyFPE_START_PROTECT("mpz_float", return 0)
1390 x = 0.0;
1391 mulstate = 1.0;
1392 while (i--) {
1393 x += mulstate * mpz_get_ui(&mpzscratch);
1394 mulstate *= multiplier;
1395 mpz_div_2exp(&mpzscratch, &mpzscratch, BITS_PER_MP_LIMB);
1396 }
1397 PyFPE_END_PROTECT(mulstate)
1398
1399 assert(mpz_cmp_ui(&mpzscratch, (unsigned long int)0) == 0);
1400 mpz_clear(&mpzscratch);
1401
1402 if (isnegative)
1403 x = -x;
1404
1405 return PyFloat_FromDouble(x);
1406
1407 } /* mpz_float() */
1408
1409 #ifdef MPZ_CONVERSIONS_AS_METHODS
1410 static PyObject *
1411 mpz_hex(mpzobject *self, PyObject *args)
1412 #else /* def MPZ_CONVERSIONS_AS_METHODS */
1413 static PyObject *
1414 mpz_hex(mpzobject *self)
1415 #endif /* def MPZ_CONVERSIONS_AS_METHODS else */
1416 {
1417 #ifdef MPZ_CONVERSIONS_AS_METHODS
1418 if (!PyArg_NoArgs(args))
1419 return NULL;
1420 #endif /* def MPZ_CONVERSIONS_AS_METHODS */
1421
1422 return mpz_format((PyObject *)self, 16, (unsigned char)1);
1423 } /* mpz_hex() */
1424
1425 #ifdef MPZ_CONVERSIONS_AS_METHODS
1426 static PyObject *
1427 mpz_oct(mpzobject *self, PyObject *args)
1428 #else /* def MPZ_CONVERSIONS_AS_METHODS */
1429 static PyObject *
1430 mpz_oct(mpzobject *self)
1431 #endif /* def MPZ_CONVERSIONS_AS_METHODS else */
1432 {
1433 #ifdef MPZ_CONVERSIONS_AS_METHODS
1434 if (!PyArg_NoArgs(args))
1435 return NULL;
1436 #endif /* def MPZ_CONVERSIONS_AS_METHODS */
1437
1438 return mpz_format((PyObject *)self, 8, (unsigned char)1);
1439 } /* mpz_oct() */
1440
1441 static PyObject *
1442 mpz_binary(mpzobject *self, PyObject *args)
1443 {
1444 int size;
1445 PyStringObject *strobjp;
1446 char *cp;
1447 MP_INT mp;
1448 unsigned long ldigit;
1449
1450 if (!PyArg_NoArgs(args))
1451 return NULL;
1452
1453 if (mpz_cmp_ui(&self->mpz, (unsigned long int)0) < 0) {
1454 PyErr_SetString(PyExc_ValueError,
1455 "mpz.binary() arg must be >= 0");
1456 return NULL;
1457 }
1458
1459 mpz_init_set(&mp, &self->mpz);
1460 size = (int)mpz_size(&mp);
1461
1462 if ((strobjp = (PyStringObject *)
1463 PyString_FromStringAndSize(
1464 (char *)0, size * sizeof (unsigned long int))) == NULL)
1465 return NULL;
1466
1467 /* get the beginning of the string memory and start copying things */
1468 cp = PyString_AS_STRING(strobjp);
1469
1470 /* this has been programmed using a (fairly) decent lib-i/f it could
1471 be must faster if we looked into the GMP lib */
1472 while (size--) {
1473 ldigit = mpz_get_ui(&mp);
1474 mpz_div_2exp(&mp, &mp, BITS_PER_MP_LIMB);
1475 *cp++ = (unsigned char)(ldigit & 0xFF);
1476 *cp++ = (unsigned char)((ldigit >>= 8) & 0xFF);
1477 *cp++ = (unsigned char)((ldigit >>= 8) & 0xFF);
1478 *cp++ = (unsigned char)((ldigit >>= 8) & 0xFF);
1479 if (sizeof(ldigit) == 8 && BITS_PER_MP_LIMB == 64) {
1480 *cp++ = (unsigned char)((ldigit >>= 8) & 0xFF);
1481 *cp++ = (unsigned char)((ldigit >>= 8) & 0xFF);
1482 *cp++ = (unsigned char)((ldigit >>= 8) & 0xFF);
1483 *cp++ = (unsigned char)((ldigit >>= 8) & 0xFF);
1484 }
1485 }
1486
1487 while (strobjp->ob_size && !*--cp)
1488 strobjp->ob_size--;
1489
1490 return (PyObject *)strobjp;
1491 } /* mpz_binary() */
1492
1493
1494 static PyMethodDef mpz_methods[] = {
1495 #ifdef MPZ_CONVERSIONS_AS_METHODS
1496 {"int", mpz_int},
1497 {"long", mpz_long},
1498 {"float", mpz_float},
1499 {"hex", mpz_hex},
1500 {"oct", mpz_oct},
1501 #endif /* def MPZ_CONVERSIONS_AS_METHODS */
1502 {"binary", (PyCFunction)mpz_binary},
1503 {NULL, NULL} /* sentinel */
1504 };
1505
1506 static PyObject *
1507 mpz_getattr(mpzobject *self, char *name)
1508 {
1509 return Py_FindMethod(mpz_methods, (PyObject *)self, name);
1510 } /* mpz_getattr() */
1511
1512
1513 static int
1514 mpz_coerce(PyObject **pv, PyObject **pw)
1515 {
1516 PyObject *z;
1517
1518 #ifdef MPZ_DEBUG
1519 fputs("mpz_coerce() called...\n", stderr);
1520 #endif /* def MPZ_DEBUG */
1521
1522 assert(is_mpzobject(*pv));
1523
1524 /* always convert other arg to mpz value, except for floats */
1525 if (!PyFloat_Check(*pw)) {
1526 if ((z = (PyObject *)mpz_mpzcoerce(*pw)) == NULL)
1527 return -1; /* -1: an error always has been set */
1528
1529 Py_INCREF(*pv);
1530 *pw = z;
1531 }
1532 else {
1533 #ifdef MPZ_CONVERSIONS_AS_METHODS
1534 if ((z = mpz_float((mpzobject *)(*pv), NULL)) == NULL)
1535 return -1;
1536 #else /* def MPZ_CONVERSIONS_AS_METHODS */
1537 if ((z = mpz_float((mpzobject *)(*pv))) == NULL)
1538 return -1;
1539 #endif /* def MPZ_CONVERSIONS_AS_METHODS else */
1540
1541 Py_INCREF(*pw);
1542 *pv = z;
1543 }
1544 return 0; /* coercion succeeded */
1545
1546 } /* mpz_coerce() */
1547
1548
1549 static PyObject *
1550 mpz_repr(PyObject *v)
1551 {
1552 return mpz_format(v, 10, (unsigned char)1);
1553 } /* mpz_repr() */
1554
1555
1556
1557 #define UF (unaryfunc)
1558 #define BF (binaryfunc)
1559 #define TF (ternaryfunc)
1560 #define IF (inquiry)
1561 #define CF (coercion)
1562
1563 static PyNumberMethods mpz_as_number = {
1564 BF mpz_addition, /*nb_add*/
1565 BF mpz_substract, /*nb_subtract*/
1566 BF mpz_multiply, /*nb_multiply*/
1567 BF mpz_divide, /*nb_divide*/
1568 BF mpz_remainder, /*nb_remainder*/
1569 BF mpz_div_and_mod, /*nb_divmod*/
1570 TF mpz_power, /*nb_power*/
1571 UF mpz_negative, /*nb_negative*/
1572 UF mpz_positive, /*tp_positive*/
1573 UF mpz_absolute, /*tp_absolute*/
1574 IF mpz_nonzero, /*tp_nonzero*/
1575 UF py_mpz_invert, /*nb_invert*/
1576 BF mpz_lshift, /*nb_lshift*/
1577 BF mpz_rshift, /*nb_rshift*/
1578 BF mpz_andfunc, /*nb_and*/
1579 BF mpz_xorfunc, /*nb_xor*/
1580 BF mpz_orfunc, /*nb_or*/
1581 CF mpz_coerce, /*nb_coerce*/
1582 #ifndef MPZ_CONVERSIONS_AS_METHODS
1583 UF mpz_int, /*nb_int*/
1584 UF mpz_long, /*nb_long*/
1585 UF mpz_float, /*nb_float*/
1586 UF mpz_oct, /*nb_oct*/
1587 UF mpz_hex, /*nb_hex*/
1588 #endif /* ndef MPZ_CONVERSIONS_AS_METHODS */
1589 };
1590
1591 static PyTypeObject MPZtype = {
1592 PyObject_HEAD_INIT(NULL)
1593 0, /*ob_size*/
1594 "mpz.mpz", /*tp_name*/
1595 sizeof(mpzobject), /*tp_size*/
1596 0, /*tp_itemsize*/
1597 /* methods */
1598 (destructor)mpz_dealloc, /*tp_dealloc*/
1599 0, /*tp_print*/
1600 (getattrfunc)mpz_getattr, /*tp_getattr*/
1601 0, /*tp_setattr*/
1602 (cmpfunc)mpz_compare, /*tp_compare*/
1603 (reprfunc)mpz_repr, /*tp_repr*/
1604 &mpz_as_number, /*tp_as_number*/
1605 };
1606
1607 /* List of functions exported by this module */
1608
1609 static PyMethodDef mpz_functions[] = {
1610 #if 0
1611 {initialiser_name, MPZ_mpz},
1612 #else /* 0 */
1613 /* until guido ``fixes'' struct PyMethodDef */
1614 {(char *)initialiser_name, MPZ_mpz},
1615 #endif /* 0 else */
1616 {"powm", MPZ_powm},
1617 {"gcd", MPZ_gcd},
1618 {"gcdext", MPZ_gcdext},
1619 {"sqrt", MPZ_sqrt},
1620 {"sqrtrem", MPZ_sqrtrem},
1621 {"divm", MPZ_divm},
1622 {NULL, NULL} /* Sentinel */
1623 };
1624
1625
1626 /* #define MP_TEST_ALLOC */
1627
1628 #ifdef MP_TEST_ALLOC
1629 #define MP_TEST_SIZE 4
1630 static const char mp_test_magic[MP_TEST_SIZE] = {'\xAA','\xAA','\xAA','\xAA'};
1631 static mp_test_error(int *location)
1632 {
1633 /* assumptions: *alloc returns address divisible by 4,
1634 mpz_* routines allocate in chunks divisible by four */
1635 fprintf(stderr, "MP_TEST_ERROR: location holds 0x%08d\n", *location );
1636 Py_FatalError("MP_TEST_ERROR");
1637 } /* static mp_test_error() */
1638 #define MP_EXTRA_ALLOC(size) ((size) + MP_TEST_SIZE)
1639 #define MP_SET_TEST(basep,size) (void)memcpy( ((char *)(basep))+(size), mp_test_magic, MP_TEST_SIZE)
1640 #define MP_DO_TEST(basep,size) if ( !memcmp( ((char *)(basep))+(size), mp_test_magic, MP_TEST_SIZE ) ) \
1641 ; \
1642 else \
1643 mp_test_error((int *)((char *)(basep) + size))
1644 #else /* def MP_TEST_ALLOC */
1645 #define MP_EXTRA_ALLOC(size) (size)
1646 #define MP_SET_TEST(basep,size)
1647 #define MP_DO_TEST(basep,size)
1648 #endif /* def MP_TEST_ALLOC else */
1649
1650 void *mp_allocate(size_t alloc_size)
1651 {
1652 void *res;
1653
1654 #ifdef MPZ_DEBUG
1655 fprintf(stderr, "mp_allocate : size %ld\n",
1656 alloc_size);
1657 #endif /* def MPZ_DEBUG */
1658
1659 if ( (res = malloc(MP_EXTRA_ALLOC(alloc_size))) == NULL )
1660 Py_FatalError("mp_allocate failure");
1661
1662 #ifdef MPZ_DEBUG
1663 fprintf(stderr, "mp_allocate : address %08p\n", res);
1664 #endif /* def MPZ_DEBUG */
1665
1666 MP_SET_TEST(res,alloc_size);
1667
1668 return res;
1669 } /* mp_allocate() */
1670
1671
1672 void *mp_reallocate(void *ptr, size_t old_size, size_t new_size)
1673 {
1674 void *res;
1675
1676 #ifdef MPZ_DEBUG
1677 fprintf(stderr, "mp_reallocate: old address %08p, old size %ld\n",
1678 ptr, old_size);
1679 #endif /* def MPZ_DEBUG */
1680
1681 MP_DO_TEST(ptr, old_size);
1682
1683 if ( (res = realloc(ptr, MP_EXTRA_ALLOC(new_size))) == NULL )
1684 Py_FatalError("mp_reallocate failure");
1685
1686 #ifdef MPZ_DEBUG
1687 fprintf(stderr, "mp_reallocate: new address %08p, new size %ld\n",
1688 res, new_size);
1689 #endif /* def MPZ_DEBUG */
1690
1691 MP_SET_TEST(res, new_size);
1692
1693 return res;
1694 } /* mp_reallocate() */
1695
1696
1697 void mp_free(void *ptr, size_t size)
1698 {
1699
1700 #ifdef MPZ_DEBUG
1701 fprintf(stderr, "mp_free : old address %08p, old size %ld\n",
1702 ptr, size);
1703 #endif /* def MPZ_DEBUG */
1704
1705 MP_DO_TEST(ptr, size);
1706 free(ptr);
1707 } /* mp_free() */
1708
1709
1710
1711 /* Initialize this module. */
1712
1713 DL_EXPORT(void)
1714 initmpz(void)
1715 {
1716 PyObject *module;
1717 PyObject *dict;
1718
1719 #ifdef MPZ_DEBUG
1720 fputs( "initmpz() called...\n", stderr );
1721 #endif /* def MPZ_DEBUG */
1722
1723 mp_set_memory_functions( mp_allocate, mp_reallocate, mp_free );
1724 MPZtype.ob_type = &PyType_Type;
1725 module = Py_InitModule("mpz", mpz_functions);
1726
1727 /* create some frequently used constants */
1728 if ((mpz_value_zero = newmpzobject()) == NULL)
1729 goto finally;
1730 mpz_set_ui(&mpz_value_zero->mpz, (unsigned long int)0);
1731
1732 if ((mpz_value_one = newmpzobject()) == NULL)
1733 goto finally;
1734 mpz_set_ui(&mpz_value_one->mpz, (unsigned long int)1);
1735
1736 if ((mpz_value_mone = newmpzobject()) == NULL)
1737 goto finally;
1738 mpz_set_si(&mpz_value_mone->mpz, (long)-1);
1739
1740 dict = PyModule_GetDict(module);
1741 if (dict != NULL) {
1742 PyDict_SetItemString(dict, "MPZType", (PyObject*)&MPZtype);
1743 }
1744 finally:
1745 return;
1746 } /* initmpz() */
1747
1748 #ifdef MAKEDUMMYINT
1749 int _mpz_dummy_int; /* XXX otherwise, we're .bss-less (DYNLOAD->Jack?) */
1750 #endif /* def MAKEDUMMYINT */