?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Update for release.
[python/dscho.git] / Modules / mpzmodule.c
blob4641298991115101cb1b3a3151f150d8fe463fe8
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 static 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
839
840 #ifdef MPZ_DEBUG
841 fputs("MPZ_mpz() called...\n", stderr);
842 #endif /* def MPZ_DEBUG */
843
844 /* at least we know it's some object */
845 /* note DON't Py_DECREF args */
846
847 if (PyInt_Check(args)) {
848 long lval = PyInt_AS_LONG(args);
849 if (lval == (long)0) {
850 Py_INCREF(mpz_value_zero);
851 mpzp = mpz_value_zero;
852 }
853 else if (lval == (long)1) {
854 Py_INCREF(mpz_value_one);
855 mpzp = mpz_value_one;
856 }
857 else if ((mpzp = newmpzobject()) == NULL)
858 return NULL;
859 else mpz_set_si(&mpzp->mpz, lval);
860 }
861 else if (PyLong_Check(args)) {
862 MP_INT mplongdigit;
863 int i;
864 unsigned char isnegative;
865
866
867 if ((mpzp = newmpzobject()) == NULL)
868 return NULL;
869
870 mpz_set_si(&mpzp->mpz, 0L);
871 mpz_init(&mplongdigit);
872
873 /* how we're gonna handle this? */
874 if ((isnegative =
875 ((i = ((PyLongObject *)args)->ob_size) < 0) ))
876 i = -i;
877
878 while (i--) {
879 mpz_set_ui(&mplongdigit,
880 (unsigned long)
881 ((PyLongObject *)args)->ob_digit[i]);
882 mpz_mul_2exp(&mplongdigit,&mplongdigit,
883 (unsigned long int)i * SHIFT);
884 mpz_ior(&mpzp->mpz, &mpzp->mpz, &mplongdigit);
885 }
886
887 if (isnegative)
888 mpz_neg(&mpzp->mpz, &mpzp->mpz);
889
890 /* get rid of allocation for tmp variable */
891 mpz_clear(&mplongdigit);
892 }
893 else if (PyString_Check(args)) {
894 unsigned char *cp = (unsigned char *)PyString_AS_STRING(args);
895 int len = PyString_GET_SIZE(args);
896 MP_INT mplongdigit;
897
898 if ((mpzp = newmpzobject()) == NULL)
899 return NULL;
900
901 mpz_set_si(&mpzp->mpz, 0L);
902 mpz_init(&mplongdigit);
903
904 /* let's do it the same way as with the long conversion:
905 without thinking how it can be faster (-: :-) */
906
907 cp += len;
908 while (len--) {
909 mpz_set_ui(&mplongdigit, (unsigned long)*--cp );
910 mpz_mul_2exp(&mplongdigit,&mplongdigit,
911 (unsigned long int)len * 8);
912 mpz_ior(&mpzp->mpz, &mpzp->mpz, &mplongdigit);
913 }
914
915 /* get rid of allocation for tmp variable */
916 mpz_clear(&mplongdigit);
917 }
918 else if (is_mpzobject(args)) {
919 Py_INCREF(args);
920 mpzp = (mpzobject *)args;
921 }
922 else {
923 PyErr_SetString(PyExc_TypeError,
924 "mpz.mpz() expects integer, long, string or mpz object argument");
925 return NULL;
926 }
927
928
929 #ifdef MPZ_DEBUG
930 fputs("MPZ_mpz: created mpz=", stderr);
931 mpz_out_str(stderr, 10, &mpzp->mpz);
932 putc('\n', stderr);
933 #endif /* def MPZ_DEBUG */
934 return (PyObject *)mpzp;
935 } /* MPZ_mpz() */
936
937 static mpzobject *
938 mpz_mpzcoerce(PyObject *z)
939 {
940 /* shortcut: 9 out of 10 times the type is already ok */
941 if (is_mpzobject(z)) {
942 Py_INCREF(z);
943 return (mpzobject *)z; /* coercion succeeded */
944 }
945
946 /* what types do we accept?: intobjects and longobjects */
947 if (PyInt_Check(z) || PyLong_Check(z))
948 return (mpzobject *)MPZ_mpz((PyObject *)NULL, z);
949
950 PyErr_SetString(PyExc_TypeError,
951 "number coercion (to mpzobject) failed");
952 return NULL;
953 } /* mpz_mpzcoerce() */
954
955 /* Forward */
956 static void mpz_divm(MP_INT *res, const MP_INT *num,
957 const MP_INT *den, const MP_INT *mod);
958
959 static PyObject *
960 MPZ_powm(PyObject *self, PyObject *args)
961 {
962 PyObject *base, *exp, *mod;
963 mpzobject *mpzbase = NULL, *mpzexp = NULL, *mpzmod = NULL;
964 mpzobject *z = NULL;
965 int tstres;
966
967
968 if (!PyArg_ParseTuple(args, "OOO", &base, &exp, &mod))
969 return NULL;
970
971 if ((mpzbase = mpz_mpzcoerce(base)) == NULL
972 || (mpzexp = mpz_mpzcoerce(exp)) == NULL
973 || (mpzmod = mpz_mpzcoerce(mod)) == NULL
974 || (z = newmpzobject()) == NULL) {
975 Py_XDECREF(mpzbase);
976 Py_XDECREF(mpzexp);
977 Py_XDECREF(mpzmod);
978 Py_XDECREF(z);
979 return NULL;
980 }
981
982 if ((tstres=mpz_cmp_ui(&mpzexp->mpz, (unsigned long int)0)) == 0) {
983 Py_DECREF(mpzbase);
984 Py_DECREF(mpzexp);
985 Py_DECREF(mpzmod);
986 Py_DECREF(z);
987 Py_INCREF(mpz_value_one);
988 return (PyObject *)mpz_value_one;
989 }
990
991 if (mpz_cmp_ui(&mpzmod->mpz, 0) == 0) {
992 Py_DECREF(mpzbase);
993 Py_DECREF(mpzexp);
994 Py_DECREF(mpzmod);
995 Py_DECREF(z);
996 PyErr_SetString(PyExc_ValueError, "modulus cannot be 0");
997 return NULL;
998 }
999
1000 if (tstres < 0) {
1001 MP_INT absexp;
1002 /* negative exp */
1003
1004 mpz_init_set(&absexp, &mpzexp->mpz);
1005 mpz_abs(&absexp, &absexp);
1006 mpz_powm(&z->mpz, &mpzbase->mpz, &absexp, &mpzmod->mpz);
1007
1008 mpz_divm(&z->mpz, &mpz_value_one->mpz, &z->mpz, &mpzmod->mpz);
1009
1010 mpz_clear(&absexp);
1011 }
1012 else {
1013 mpz_powm(&z->mpz, &mpzbase->mpz, &mpzexp->mpz, &mpzmod->mpz);
1014 }
1015
1016 Py_DECREF(mpzbase);
1017 Py_DECREF(mpzexp);
1018 Py_DECREF(mpzmod);
1019
1020 return (PyObject *)z;
1021 } /* MPZ_powm() */
1022
1023
1024 static PyObject *
1025 MPZ_gcd(PyObject *self, PyObject *args)
1026 {
1027 PyObject *op1, *op2;
1028 mpzobject *mpzop1 = NULL, *mpzop2 = NULL;
1029 mpzobject *z;
1030
1031
1032 if (!PyArg_ParseTuple(args, "OO", &op1, &op2))
1033 return NULL;
1034
1035 if ((mpzop1 = mpz_mpzcoerce(op1)) == NULL
1036 || (mpzop2 = mpz_mpzcoerce(op2)) == NULL
1037 || (z = newmpzobject()) == NULL) {
1038 Py_XDECREF(mpzop1);
1039 Py_XDECREF(mpzop2);
1040 return NULL;
1041 }
1042
1043 /* ok, we have three mpzobjects, and an initialised result holder */
1044 mpz_gcd(&z->mpz, &mpzop1->mpz, &mpzop2->mpz);
1045
1046 Py_DECREF(mpzop1);
1047 Py_DECREF(mpzop2);
1048
1049 return (PyObject *)z;
1050 } /* MPZ_gcd() */
1051
1052
1053 static PyObject *
1054 MPZ_gcdext(PyObject *self, PyObject *args)
1055 {
1056 PyObject *op1, *op2, *z = NULL;
1057 mpzobject *mpzop1 = NULL, *mpzop2 = NULL;
1058 mpzobject *g = NULL, *s = NULL, *t = NULL;
1059
1060
1061 if (!PyArg_ParseTuple(args, "OO", &op1, &op2))
1062 return NULL;
1063
1064 if ((mpzop1 = mpz_mpzcoerce(op1)) == NULL
1065 || (mpzop2 = mpz_mpzcoerce(op2)) == NULL
1066 || (z = PyTuple_New(3)) == NULL
1067 || (g = newmpzobject()) == NULL
1068 || (s = newmpzobject()) == NULL
1069 || (t = newmpzobject()) == NULL) {
1070 Py_XDECREF(mpzop1);
1071 Py_XDECREF(mpzop2);
1072 Py_XDECREF(z);
1073 Py_XDECREF(g);
1074 Py_XDECREF(s);
1075 /*Py_XDECREF(t);*/
1076 return NULL;
1077 }
1078
1079 mpz_gcdext(&g->mpz, &s->mpz, &t->mpz, &mpzop1->mpz, &mpzop2->mpz);
1080
1081 Py_DECREF(mpzop1);
1082 Py_DECREF(mpzop2);
1083
1084 (void)PyTuple_SetItem(z, 0, (PyObject *)g);
1085 (void)PyTuple_SetItem(z, 1, (PyObject *)s);
1086 (void)PyTuple_SetItem(z, 2, (PyObject *)t);
1087
1088 return (PyObject *)z;
1089 } /* MPZ_gcdext() */
1090
1091
1092 static PyObject *
1093 MPZ_sqrt(PyObject *self, PyObject *args)
1094 {
1095 mpzobject *mpzop = NULL;
1096 mpzobject *z;
1097
1098
1099 if ((mpzop = mpz_mpzcoerce(args)) == NULL
1100 || (z = newmpzobject()) == NULL) {
1101 Py_XDECREF(mpzop);
1102 return NULL;
1103 }
1104
1105 mpz_sqrt(&z->mpz, &mpzop->mpz);
1106
1107 Py_DECREF(mpzop);
1108
1109 return (PyObject *)z;
1110 } /* MPZ_sqrt() */
1111
1112
1113 static PyObject *
1114 MPZ_sqrtrem(PyObject *self, PyObject *args)
1115 {
1116 PyObject *z = NULL;
1117 mpzobject *mpzop = NULL;
1118 mpzobject *root = NULL, *rem = NULL;
1119
1120 if ((mpzop = mpz_mpzcoerce(args)) == NULL
1121 || (z = PyTuple_New(2)) == NULL
1122 || (root = newmpzobject()) == NULL
1123 || (rem = newmpzobject()) == NULL) {
1124 Py_XDECREF(mpzop);
1125 Py_XDECREF(z);
1126 Py_XDECREF(root);
1127 /*Py_XDECREF(rem);*/
1128 return NULL;
1129 }
1130
1131 mpz_sqrtrem(&root->mpz, &rem->mpz, &mpzop->mpz);
1132
1133 Py_DECREF(mpzop);
1134
1135 (void)PyTuple_SetItem(z, 0, (PyObject *)root);
1136 (void)PyTuple_SetItem(z, 1, (PyObject *)rem);
1137
1138 return (PyObject *)z;
1139 } /* MPZ_sqrtrem() */
1140
1141
1142 static void
1143 mpz_divm(MP_INT *res, const MP_INT *num, const MP_INT *den, const MP_INT *mod)
1144 {
1145 MP_INT s0, s1, q, r, x, d0, d1;
1146
1147 mpz_init_set(&s0, num);
1148 mpz_init_set_ui(&s1, 0);
1149 mpz_init(&q);
1150 mpz_init(&r);
1151 mpz_init(&x);
1152 mpz_init_set(&d0, den);
1153 mpz_init_set(&d1, mod);
1154
1155 #ifdef GMP2
1156 while (d1._mp_size != 0) {
1157 #else
1158 while (d1.size != 0) {
1159 #endif
1160 mpz_divmod(&q, &r, &d0, &d1);
1161 mpz_set(&d0, &d1);
1162 mpz_set(&d1, &r);
1163
1164 mpz_mul(&x, &s1, &q);
1165 mpz_sub(&x, &s0, &x);
1166 mpz_set(&s0, &s1);
1167 mpz_set(&s1, &x);
1168 }
1169
1170 #ifdef GMP2
1171 if (d0._mp_size != 1 || d0._mp_d[0] != 1)
1172 res->_mp_size = 0; /* trouble: the gcd != 1; set s to zero */
1173 #else
1174 if (d0.size != 1 || d0.d[0] != 1)
1175 res->size = 0; /* trouble: the gcd != 1; set s to zero */
1176 #endif
1177 else {
1178 #ifdef MPZ_MDIV_BUG
1179 /* watch out here! first check the signs, and then perform
1180 the mpz_mod() since mod could point to res */
1181 if ((s0.size < 0) != (mod->size < 0)) {
1182 mpz_mod(res, &s0, mod);
1183
1184 if (res->size)
1185 mpz_add(res, res, mod);
1186 }
1187 else
1188 mpz_mod(res, &s0, mod);
1189
1190 #else /* def MPZ_MDIV_BUG */
1191 mpz_mmod(res, &s0, mod);
1192 #endif /* def MPZ_MDIV_BUG else */
1193 }
1194
1195 mpz_clear(&s0);
1196 mpz_clear(&s1);
1197 mpz_clear(&q);
1198 mpz_clear(&r);
1199 mpz_clear(&x);
1200 mpz_clear(&d0);
1201 mpz_clear(&d1);
1202 } /* mpz_divm() */
1203
1204
1205 static PyObject *
1206 MPZ_divm(PyObject *self, PyObject *args)
1207 {
1208 PyObject *num, *den, *mod;
1209 mpzobject *mpznum, *mpzden = NULL, *mpzmod = NULL;
1210 mpzobject *z = NULL;
1211
1212
1213 if (!PyArg_ParseTuple(args, "OOO", &num, &den, &mod))
1214 return NULL;
1215
1216 if ((mpznum = mpz_mpzcoerce(num)) == NULL
1217 || (mpzden = mpz_mpzcoerce(den)) == NULL
1218 || (mpzmod = mpz_mpzcoerce(mod)) == NULL
1219 || (z = newmpzobject()) == NULL ) {
1220 Py_XDECREF(mpznum);
1221 Py_XDECREF(mpzden);
1222 Py_XDECREF(mpzmod);
1223 return NULL;
1224 }
1225
1226 mpz_divm(&z->mpz, &mpznum->mpz, &mpzden->mpz, &mpzmod->mpz);
1227
1228 Py_DECREF(mpznum);
1229 Py_DECREF(mpzden);
1230 Py_DECREF(mpzmod);
1231
1232 if (mpz_cmp_ui(&z->mpz, (unsigned long int)0) == 0) {
1233 Py_DECREF(z);
1234 PyErr_SetString(PyExc_ValueError,
1235 "gcd(den, mod) != 1 or num == 0");
1236 return NULL;
1237 }
1238
1239 return (PyObject *)z;
1240 } /* MPZ_divm() */
1241
1242
1243 static PyObject *
1244 mpz_int(mpzobject *self)
1245 {
1246 long sli;
1247
1248
1249 if (mpz_size(&self->mpz) > 1
1250 || (sli = (long)mpz_get_ui(&self->mpz)) < (long)0 ) {
1251 PyErr_SetString(PyExc_ValueError,
1252 "mpz.int() arg too long to convert");
1253 return NULL;
1254 }
1255
1256 if (mpz_cmp_ui(&self->mpz, (unsigned long)0) < 0)
1257 sli = -sli;
1258
1259 return PyInt_FromLong(sli);
1260 } /* mpz_int() */
1261
1262 static PyObject *
1263 mpz_long(mpzobject *self)
1264 {
1265 int i, isnegative;
1266 unsigned long int uli;
1267 PyLongObject *longobjp;
1268 int ldcount;
1269 int bitpointer, newbitpointer;
1270 MP_INT mpzscratch;
1271
1272
1273 /* determine length of python-long to be allocated */
1274 if ((longobjp = _PyLong_New(i = (int)
1275 ((mpz_size(&self->mpz) * BITS_PER_MP_LIMB
1276 + SHIFT - 1) /
1277 SHIFT))) == NULL)
1278 return NULL;
1279
1280 /* determine sign, and copy self to scratch var */
1281 mpz_init_set(&mpzscratch, &self->mpz);
1282 if ((isnegative = (mpz_cmp_ui(&self->mpz, (unsigned long int)0) < 0)))
1283 mpz_neg(&mpzscratch, &mpzscratch);
1284
1285 /* let those bits come, let those bits go,
1286 e.g. dismantle mpzscratch, build PyLongObject */
1287
1288 bitpointer = 0; /* the number of valid bits in stock */
1289 newbitpointer = 0;
1290 ldcount = 0; /* the python-long limb counter */
1291 uli = (unsigned long int)0;
1292 while (i--) {
1293 longobjp->ob_digit[ldcount] = uli & MASK;
1294
1295 /* check if we've had enough bits for this digit */
1296 if (bitpointer < SHIFT) {
1297 uli = mpz_get_ui(&mpzscratch);
1298 longobjp->ob_digit[ldcount] |=
1299 (uli << bitpointer) & MASK;
1300 uli >>= SHIFT-bitpointer;
1301 bitpointer += BITS_PER_MP_LIMB;
1302 mpz_div_2exp(&mpzscratch, &mpzscratch,
1303 BITS_PER_MP_LIMB);
1304 }
1305 else
1306 uli >>= SHIFT;
1307 bitpointer -= SHIFT;
1308 ldcount++;
1309 }
1310
1311 assert(mpz_cmp_ui(&mpzscratch, (unsigned long int)0) == 0);
1312 mpz_clear(&mpzscratch);
1313 assert(ldcount <= longobjp->ob_size);
1314
1315 /* long_normalize() is file-static */
1316 /* longobjp = long_normalize(longobjp); */
1317 while (ldcount > 0 && longobjp->ob_digit[ldcount-1] == 0)
1318 ldcount--;
1319 longobjp->ob_size = ldcount;
1320
1321
1322 if (isnegative)
1323 longobjp->ob_size = -longobjp->ob_size;
1324
1325 return (PyObject *)longobjp;
1326
1327 } /* mpz_long() */
1328
1329
1330 /* I would have avoided pow() anyways, so ... */
1331 static const double multiplier = 256.0 * 256.0 * 256.0 * 256.0;
1332
1333 static PyObject *
1334 mpz_float(mpzobject *self)
1335 {
1336 int i, isnegative;
1337 double x;
1338 double mulstate;
1339 MP_INT mpzscratch;
1340
1341
1342 i = (int)mpz_size(&self->mpz);
1343
1344 /* determine sign, and copy abs(self) to scratch var */
1345 if ((isnegative = (mpz_cmp_ui(&self->mpz, (unsigned long int)0) < 0)))
1346 {
1347 mpz_init(&mpzscratch);
1348 mpz_neg(&mpzscratch, &self->mpz);
1349 }
1350 else
1351 mpz_init_set(&mpzscratch, &self->mpz);
1352
1353 /* let those bits come, let those bits go,
1354 e.g. dismantle mpzscratch, build PyFloatObject */
1355
1356 /* Can this overflow? Dunno, protect against that possibility. */
1357 PyFPE_START_PROTECT("mpz_float", return 0)
1358 x = 0.0;
1359 mulstate = 1.0;
1360 while (i--) {
1361 x += mulstate * mpz_get_ui(&mpzscratch);
1362 mulstate *= multiplier;
1363 mpz_div_2exp(&mpzscratch, &mpzscratch, BITS_PER_MP_LIMB);
1364 }
1365 PyFPE_END_PROTECT(mulstate)
1366
1367 assert(mpz_cmp_ui(&mpzscratch, (unsigned long int)0) == 0);
1368 mpz_clear(&mpzscratch);
1369
1370 if (isnegative)
1371 x = -x;
1372
1373 return PyFloat_FromDouble(x);
1374
1375 } /* mpz_float() */
1376
1377 static PyObject *
1378 mpz_hex(mpzobject *self)
1379 {
1380 return mpz_format((PyObject *)self, 16, (unsigned char)1);
1381 } /* mpz_hex() */
1382
1383 static PyObject *
1384 mpz_oct(mpzobject *self)
1385 {
1386 return mpz_format((PyObject *)self, 8, (unsigned char)1);
1387 } /* mpz_oct() */
1388
1389 static PyObject *
1390 mpz_binary(mpzobject *self)
1391 {
1392 int size;
1393 PyStringObject *strobjp;
1394 char *cp;
1395 MP_INT mp;
1396 unsigned long ldigit;
1397
1398 if (mpz_cmp_ui(&self->mpz, (unsigned long int)0) < 0) {
1399 PyErr_SetString(PyExc_ValueError,
1400 "mpz.binary() arg must be >= 0");
1401 return NULL;
1402 }
1403
1404 mpz_init_set(&mp, &self->mpz);
1405 size = (int)mpz_size(&mp);
1406
1407 if ((strobjp = (PyStringObject *)
1408 PyString_FromStringAndSize(
1409 (char *)0, size * sizeof (unsigned long int))) == NULL)
1410 return NULL;
1411
1412 /* get the beginning of the string memory and start copying things */
1413 cp = PyString_AS_STRING(strobjp);
1414
1415 /* this has been programmed using a (fairly) decent lib-i/f it could
1416 be must faster if we looked into the GMP lib */
1417 while (size--) {
1418 ldigit = mpz_get_ui(&mp);
1419 mpz_div_2exp(&mp, &mp, BITS_PER_MP_LIMB);
1420 *cp++ = (unsigned char)(ldigit & 0xFF);
1421 *cp++ = (unsigned char)((ldigit >>= 8) & 0xFF);
1422 *cp++ = (unsigned char)((ldigit >>= 8) & 0xFF);
1423 *cp++ = (unsigned char)((ldigit >>= 8) & 0xFF);
1424 if (sizeof(ldigit) == 8 && BITS_PER_MP_LIMB == 64) {
1425 *cp++ = (unsigned char)((ldigit >>= 8) & 0xFF);
1426 *cp++ = (unsigned char)((ldigit >>= 8) & 0xFF);
1427 *cp++ = (unsigned char)((ldigit >>= 8) & 0xFF);
1428 *cp++ = (unsigned char)((ldigit >>= 8) & 0xFF);
1429 }
1430 }
1431
1432 while (strobjp->ob_size && !*--cp)
1433 strobjp->ob_size--;
1434
1435 return (PyObject *)strobjp;
1436 } /* mpz_binary() */
1437
1438
1439 static PyMethodDef mpz_methods[] = {
1440 #ifdef MPZ_CONVERSIONS_AS_METHODS
1441 {"int", mpz_int, METH_NOARGS},
1442 {"long", mpz_long, METH_NOARGS},
1443 {"float", mpz_float, METH_NOARGS},
1444 {"hex", mpz_hex, METH_NOARGS},
1445 {"oct", mpz_oct, METH_NOARGS},
1446 #endif /* def MPZ_CONVERSIONS_AS_METHODS */
1447 {"binary", (PyCFunction)mpz_binary, METH_NOARGS},
1448 {NULL, NULL} /* sentinel */
1449 };
1450
1451 static PyObject *
1452 mpz_getattr(mpzobject *self, char *name)
1453 {
1454 return Py_FindMethod(mpz_methods, (PyObject *)self, name);
1455 } /* mpz_getattr() */
1456
1457
1458 static int
1459 mpz_coerce(PyObject **pv, PyObject **pw)
1460 {
1461 PyObject *z;
1462
1463 #ifdef MPZ_DEBUG
1464 fputs("mpz_coerce() called...\n", stderr);
1465 #endif /* def MPZ_DEBUG */
1466
1467 assert(is_mpzobject(*pv));
1468
1469 /* always convert other arg to mpz value, except for floats */
1470 if (!PyFloat_Check(*pw)) {
1471 if ((z = (PyObject *)mpz_mpzcoerce(*pw)) == NULL)
1472 return -1; /* -1: an error always has been set */
1473
1474 Py_INCREF(*pv);
1475 *pw = z;
1476 }
1477 else {
1478 if ((z = mpz_float((mpzobject *)(*pv))) == NULL)
1479 return -1;
1480
1481 Py_INCREF(*pw);
1482 *pv = z;
1483 }
1484 return 0; /* coercion succeeded */
1485
1486 } /* mpz_coerce() */
1487
1488
1489 static PyObject *
1490 mpz_repr(PyObject *v)
1491 {
1492 return mpz_format(v, 10, (unsigned char)1);
1493 } /* mpz_repr() */
1494
1495
1496
1497 #define UF (unaryfunc)
1498 #define BF (binaryfunc)
1499 #define TF (ternaryfunc)
1500 #define IF (inquiry)
1501 #define CF (coercion)
1502
1503 static PyNumberMethods mpz_as_number = {
1504 BF mpz_addition, /*nb_add*/
1505 BF mpz_substract, /*nb_subtract*/
1506 BF mpz_multiply, /*nb_multiply*/
1507 BF mpz_divide, /*nb_divide*/
1508 BF mpz_remainder, /*nb_remainder*/
1509 BF mpz_div_and_mod, /*nb_divmod*/
1510 TF mpz_power, /*nb_power*/
1511 UF mpz_negative, /*nb_negative*/
1512 UF mpz_positive, /*tp_positive*/
1513 UF mpz_absolute, /*tp_absolute*/
1514 IF mpz_nonzero, /*tp_nonzero*/
1515 UF py_mpz_invert, /*nb_invert*/
1516 BF mpz_lshift, /*nb_lshift*/
1517 BF mpz_rshift, /*nb_rshift*/
1518 BF mpz_andfunc, /*nb_and*/
1519 BF mpz_xorfunc, /*nb_xor*/
1520 BF mpz_orfunc, /*nb_or*/
1521 CF mpz_coerce, /*nb_coerce*/
1522 #ifndef MPZ_CONVERSIONS_AS_METHODS
1523 UF mpz_int, /*nb_int*/
1524 UF mpz_long, /*nb_long*/
1525 UF mpz_float, /*nb_float*/
1526 UF mpz_oct, /*nb_oct*/
1527 UF mpz_hex, /*nb_hex*/
1528 #endif /* ndef MPZ_CONVERSIONS_AS_METHODS */
1529 };
1530
1531 static PyTypeObject MPZtype = {
1532 PyObject_HEAD_INIT(NULL)
1533 0, /*ob_size*/
1534 "mpz.mpz", /*tp_name*/
1535 sizeof(mpzobject), /*tp_size*/
1536 0, /*tp_itemsize*/
1537 /* methods */
1538 (destructor)mpz_dealloc, /*tp_dealloc*/
1539 0, /*tp_print*/
1540 (getattrfunc)mpz_getattr, /*tp_getattr*/
1541 0, /*tp_setattr*/
1542 (cmpfunc)mpz_compare, /*tp_compare*/
1543 (reprfunc)mpz_repr, /*tp_repr*/
1544 &mpz_as_number, /*tp_as_number*/
1545 };
1546
1547 /* List of functions exported by this module */
1548
1549 static PyMethodDef mpz_functions[] = {
1550 #if 0
1551 {initialiser_name, MPZ_mpz, METH_O},
1552 #else /* 0 */
1553 /* until guido ``fixes'' struct PyMethodDef */
1554 {(char *)initialiser_name, MPZ_mpz, METH_O},
1555 #endif /* 0 else */
1556 {"powm", MPZ_powm, METH_VARARGS},
1557 {"gcd", MPZ_gcd, METH_VARARGS},
1558 {"gcdext", MPZ_gcdext, METH_VARARGS},
1559 {"sqrt", MPZ_sqrt, METH_O},
1560 {"sqrtrem", MPZ_sqrtrem, METH_O},
1561 {"divm", MPZ_divm, METH_VARARGS},
1562 {NULL, NULL} /* Sentinel */
1563 };
1564
1565
1566 /* #define MP_TEST_ALLOC */
1567
1568 #ifdef MP_TEST_ALLOC
1569 #define MP_TEST_SIZE 4
1570 static const char mp_test_magic[MP_TEST_SIZE] = {'\xAA','\xAA','\xAA','\xAA'};
1571 static mp_test_error(int *location)
1572 {
1573 /* assumptions: *alloc returns address divisible by 4,
1574 mpz_* routines allocate in chunks divisible by four */
1575 fprintf(stderr, "MP_TEST_ERROR: location holds 0x%08d\n", *location );
1576 Py_FatalError("MP_TEST_ERROR");
1577 } /* static mp_test_error() */
1578 #define MP_EXTRA_ALLOC(size) ((size) + MP_TEST_SIZE)
1579 #define MP_SET_TEST(basep,size) (void)memcpy( ((char *)(basep))+(size), mp_test_magic, MP_TEST_SIZE)
1580 #define MP_DO_TEST(basep,size) if ( !memcmp( ((char *)(basep))+(size), mp_test_magic, MP_TEST_SIZE ) ) \
1581 ; \
1582 else \
1583 mp_test_error((int *)((char *)(basep) + size))
1584 #else /* def MP_TEST_ALLOC */
1585 #define MP_EXTRA_ALLOC(size) (size)
1586 #define MP_SET_TEST(basep,size)
1587 #define MP_DO_TEST(basep,size)
1588 #endif /* def MP_TEST_ALLOC else */
1589
1590 void *mp_allocate(size_t alloc_size)
1591 {
1592 void *res;
1593
1594 #ifdef MPZ_DEBUG
1595 fprintf(stderr, "mp_allocate : size %ld\n",
1596 alloc_size);
1597 #endif /* def MPZ_DEBUG */
1598
1599 if ( (res = malloc(MP_EXTRA_ALLOC(alloc_size))) == NULL )
1600 Py_FatalError("mp_allocate failure");
1601
1602 #ifdef MPZ_DEBUG
1603 fprintf(stderr, "mp_allocate : address %08p\n", res);
1604 #endif /* def MPZ_DEBUG */
1605
1606 MP_SET_TEST(res,alloc_size);
1607
1608 return res;
1609 } /* mp_allocate() */
1610
1611
1612 void *mp_reallocate(void *ptr, size_t old_size, size_t new_size)
1613 {
1614 void *res;
1615
1616 #ifdef MPZ_DEBUG
1617 fprintf(stderr, "mp_reallocate: old address %08p, old size %ld\n",
1618 ptr, old_size);
1619 #endif /* def MPZ_DEBUG */
1620
1621 MP_DO_TEST(ptr, old_size);
1622
1623 if ( (res = realloc(ptr, MP_EXTRA_ALLOC(new_size))) == NULL )
1624 Py_FatalError("mp_reallocate failure");
1625
1626 #ifdef MPZ_DEBUG
1627 fprintf(stderr, "mp_reallocate: new address %08p, new size %ld\n",
1628 res, new_size);
1629 #endif /* def MPZ_DEBUG */
1630
1631 MP_SET_TEST(res, new_size);
1632
1633 return res;
1634 } /* mp_reallocate() */
1635
1636
1637 void mp_free(void *ptr, size_t size)
1638 {
1639
1640 #ifdef MPZ_DEBUG
1641 fprintf(stderr, "mp_free : old address %08p, old size %ld\n",
1642 ptr, size);
1643 #endif /* def MPZ_DEBUG */
1644
1645 MP_DO_TEST(ptr, size);
1646 free(ptr);
1647 } /* mp_free() */
1648
1649
1650
1651 /* Initialize this module. */
1652
1653 PyMODINIT_FUNC
1654 initmpz(void)
1655 {
1656 PyObject *module;
1657 PyObject *dict;
1658
1659 #ifdef MPZ_DEBUG
1660 fputs( "initmpz() called...\n", stderr );
1661 #endif /* def MPZ_DEBUG */
1662
1663 mp_set_memory_functions( mp_allocate, mp_reallocate, mp_free );
1664 MPZtype.ob_type = &PyType_Type;
1665 module = Py_InitModule("mpz", mpz_functions);
1666
1667 /* create some frequently used constants */
1668 if ((mpz_value_zero = newmpzobject()) == NULL)
1669 goto finally;
1670 mpz_set_ui(&mpz_value_zero->mpz, (unsigned long int)0);
1671
1672 if ((mpz_value_one = newmpzobject()) == NULL)
1673 goto finally;
1674 mpz_set_ui(&mpz_value_one->mpz, (unsigned long int)1);
1675
1676 if ((mpz_value_mone = newmpzobject()) == NULL)
1677 goto finally;
1678 mpz_set_si(&mpz_value_mone->mpz, (long)-1);
1679
1680 dict = PyModule_GetDict(module);
1681 if (dict != NULL) {
1682 PyDict_SetItemString(dict, "MPZType", (PyObject*)&MPZtype);
1683 }
1684 finally:
1685 return;
1686 } /* initmpz() */
1687
1688 #ifdef MAKEDUMMYINT
1689 int _mpz_dummy_int; /* XXX otherwise, we're .bss-less (DYNLOAD->Jack?) */
1690 #endif /* def MAKEDUMMYINT */