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