~mdw / catacomb-python / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Bug squashing.
[catacomb-python] / mp.c
1 /* -*-c-*-
2 *
3 * $Id$
4 *
5 * Multiprecision arithmetic
6 *
7 * (c) 2004 Straylight/Edgeware
8 */
9
10 /*----- Licensing notice --------------------------------------------------*
11 *
12 * This file is part of the Python interface to Catacomb.
13 *
14 * Catacomb/Python is free software; you can redistribute it and/or modify
15 * it under the terms of the GNU General Public License as published by
16 * the Free Software Foundation; either version 2 of the License, or
17 * (at your option) any later version.
18 *
19 * Catacomb/Python is distributed in the hope that it will be useful,
20 * but WITHOUT ANY WARRANTY; without even the implied warranty of
21 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22 * GNU General Public License for more details.
23 *
24 * You should have received a copy of the GNU General Public License
25 * along with Catacomb/Python; if not, write to the Free Software Foundation,
26 * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
27 */
28
29 /*----- Header files ------------------------------------------------------*/
30
31 #include "catacomb-python.h"
32
33 /*----- General utilities -------------------------------------------------*/
34
35 PyTypeObject *mp_pytype = 0;
36 PyTypeObject *gf_pytype = 0;
37
38 mp *mp_frompylong(PyObject *obj)
39 {
40 unsigned long bits;
41 PyLongObject *l = (PyLongObject *)obj;
42 int sz;
43 size_t w;
44 mpd r = 0;
45 int b = 0;
46 int i;
47 mp *x;
48 mpw *p;
49
50 sz = l->ob_size;
51 if (sz < 0) sz = -sz;
52 assert(MPW_BITS >= SHIFT);
53 bits = (unsigned long)sz * SHIFT;
54 w = (bits + MPW_BITS - 1)/MPW_BITS;
55 x = mp_new(w, l->ob_size < 0 ? MP_NEG : 0);
56 p = x->v;
57 for (i = 0; i < sz; i++) {
58 r |= (mpd)l->ob_digit[i] << b;
59 b += SHIFT;
60 while (b >= MPW_BITS) {
61 *p++ = MPW(r);
62 r >>= MPW_BITS;
63 b -= MPW_BITS;
64 }
65 }
66 while (r) {
67 *p++ = MPW(r);
68 r >>= MPW_BITS;
69 }
70 x->vl = p;
71 MP_SHRINK(x);
72 return (x);
73 }
74
75 PyObject *mp_topylong(mp *x)
76 {
77 unsigned long bits = mp_bits(x);
78 int sz = (bits + SHIFT - 1)/SHIFT;
79 PyLongObject *l = _PyLong_New(sz);
80 mpd r = 0;
81 int b = 0;
82 mpw *p = x->v;
83 int i = 0;
84
85 assert(MPW_BITS >= SHIFT);
86 while (i < sz && p < x->vl) {
87 r |= (mpd)*p++ << b;
88 b += MPW_BITS;
89 while (i < sz && b >= SHIFT) {
90 l->ob_digit[i++] = r & MASK;
91 r >>= SHIFT;
92 b -= SHIFT;
93 }
94 }
95 while (i < sz && r) {
96 l->ob_digit[i++] = r & MASK;
97 r >>= SHIFT;
98 }
99 l->ob_size = (x->f & MP_NEG) ? -sz : sz;
100 return ((PyObject *)l);
101 }
102
103 mp *mp_frompyobject(PyObject *o, int radix)
104 {
105 mp *x;
106
107 if (PyString_Check(o)) {
108 mptext_stringctx sc;
109 mp *x;
110 sc.buf = PyString_AS_STRING(o);
111 sc.lim = sc.buf + PyString_GET_SIZE(o);
112 x = mp_read(MP_NEW, radix, &mptext_stringops, &sc);
113 if (!x) return (0);
114 if (sc.buf < sc.lim) { MP_DROP(x); return (0); }
115 return (x);
116 }
117 if ((x = tomp(o)) != 0)
118 return (x);
119 return (0);
120 }
121
122 PyObject *mp_topystring(mp *x, int radix, const char *xpre,
123 const char *pre, const char *post)
124 {
125 int len = mptext_len(x, radix) + 1;
126 mptext_stringctx sc;
127 PyObject *o;
128 size_t xprelen = xpre ? strlen(xpre) : 0;
129 size_t prelen = pre ? strlen(pre) : 0;
130 size_t postlen = post ? strlen(post) : 0;
131 char *p;
132 MP_COPY(x);
133 o = PyString_FromStringAndSize(0, len + 1 + xprelen + prelen + postlen);
134 p = PyString_AS_STRING(o);
135 sc.buf = p;
136 if (xpre) { memcpy(sc.buf, xpre, xprelen); sc.buf += xprelen; }
137 if (MP_NEGP(x)) { *sc.buf++ = '-'; x = mp_neg(x, x); }
138 if (pre) { memcpy(sc.buf, pre, prelen); sc.buf += prelen; }
139 sc.lim = sc.buf + len;
140 mp_write(x, radix, &mptext_stringops, &sc);
141 if (post) { memcpy(sc.buf, post, postlen); sc.buf += postlen; }
142 MP_DROP(x);
143 _PyString_Resize(&o, sc.buf - p);
144 return (o);
145 }
146
147 static int good_radix_p(int r, int readp)
148 {
149 return ((r >= -255 && r <= -2) ||
150 (readp && r == 0) ||
151 (r >= 2 && r <= 62));
152 }
153
154 PyObject *mp_pywrap(mp *x)
155 {
156 mp_pyobj *z = PyObject_New(mp_pyobj, mp_pytype);
157 z->x = x;
158 return ((PyObject *)z);
159 }
160
161 PyObject *gf_pywrap(mp *x)
162 {
163 mp_pyobj *z = PyObject_New(mp_pyobj, gf_pytype);
164 z->x = x;
165 return ((PyObject *)z);
166 }
167
168 int mp_tolong_checked(mp *x, long *l)
169 {
170 static mp *longmin = 0, *longmax = 0;
171 int rc = -1;
172
173 if (!longmax) {
174 longmin = mp_fromlong(MP_NEW, LONG_MIN);
175 longmax = mp_fromlong(MP_NEW, LONG_MAX);
176 }
177 if (MP_CMP(x, <, longmin) || MP_CMP(x, >, longmax))
178 VALERR("mp out of range for int");
179 *l = mp_tolong(x);
180 rc = 0;
181 end:
182 return (rc);
183 }
184
185 /*----- Python interface --------------------------------------------------*/
186
187 static void mp_pydealloc(PyObject *o)
188 {
189 MP_DROP(MP_X(o));
190 FREEOBJ(o);
191 }
192
193 static PyObject *mp_pyrepr(PyObject *o)
194 { return mp_topystring(MP_X(o), 10, "MP(", 0, "L)"); }
195
196 static PyObject *mp_pystr(PyObject *o)
197 { return mp_topystring(MP_X(o), 10, 0, 0, 0); }
198
199 mp *tomp(PyObject *o)
200 {
201 PyObject *l;
202 mp *x;
203
204 if (!o)
205 return (0);
206 else if (MP_PYCHECK(o) || GF_PYCHECK(o))
207 return (MP_COPY(MP_X(o)));
208 else if (FE_PYCHECK(o))
209 return (F_OUT(FE_F(o), MP_NEW, FE_X(o)));
210 else if (PFILT_PYCHECK(o))
211 return (MP_COPY(PFILT_F(o)->m));
212 else if (ECPT_PYCHECK(o)) {
213 ec p = EC_INIT;
214 getecptout(&p, o);
215 x = MP_COPY(p.x);
216 EC_DESTROY(&p);
217 return (x);
218 } else if (GE_PYCHECK(o)) {
219 if ((x = G_TOINT(GE_G(o), MP_NEW, GE_X(o))) == 0)
220 return (0);
221 return (x);
222 } else if (PyInt_Check(o))
223 return (mp_fromlong(MP_NEW, PyInt_AS_LONG(o)));
224 else if ((l = PyNumber_Long(o)) != 0) {
225 x = mp_frompylong(l);
226 Py_DECREF(l);
227 return (x);
228 } else {
229 PyErr_Clear();
230 return (0);
231 }
232 }
233
234 mp *getmp(PyObject *o)
235 {
236 mp *x = 0;
237 if (!o) return (0);
238 if ((x = tomp(o)) == 0) {
239 PyErr_Format(PyExc_TypeError, "can't convert %.100s to mp",
240 o->ob_type->tp_name);
241 }
242 return (x);
243 }
244
245 int convmp(PyObject *o, void *p)
246 {
247 mp *x;
248 if ((x = getmp(o)) == 0) return (0);
249 *(mp **)p = x;
250 return (1);
251 }
252
253 mp *getgf(PyObject *o)
254 {
255 mp *x = 0;
256 if (!o) return (0);
257 if ((x = tomp(o)) == 0) {
258 PyErr_Format(PyExc_TypeError, "can't convert %.100s to gf",
259 o->ob_type->tp_name);
260 }
261 return (x);
262 }
263
264 int convgf(PyObject *o, void *p)
265 {
266 mp *x;
267 if ((x = getgf(o)) == 0) return (0);
268 *(mp **)p = x;
269 return (1);
270 }
271
272 static int mpbinop(PyObject *x, PyObject *y, mp **xx, mp **yy)
273 {
274 if ((*xx = tomp(x)) == 0)
275 return (-1);
276 if ((*yy = tomp(y)) == 0) {
277 MP_DROP(*xx);
278 return (-1);
279 }
280 return (0);
281 }
282
283 #define gf_and mp_and
284 #define gf_or mp_or
285 #define gf_xor mp_xor
286 #define BINOP(pre, name) \
287 static PyObject *pre##_py##name(PyObject *x, PyObject *y) { \
288 mp *xx, *yy, *zz; \
289 if (mpbinop(x, y, &xx, &yy)) RETURN_NOTIMPL; \
290 zz = pre##_##name(MP_NEW, xx, yy); \
291 MP_DROP(xx); MP_DROP(yy); \
292 return (pre##_pywrap(zz)); \
293 }
294 BINOP(mp, add)
295 BINOP(mp, sub)
296 BINOP(mp, mul)
297 BINOP(mp, and2c)
298 BINOP(mp, or2c)
299 BINOP(mp, xor2c)
300 BINOP(gf, add)
301 BINOP(gf, sub)
302 BINOP(gf, mul)
303 BINOP(gf, and)
304 BINOP(gf, or)
305 BINOP(gf, xor)
306 #undef BINOP
307
308 static mp *mp_abs(mp *d, mp *x)
309 {
310 if (MP_NEGP(x))
311 return (mp_neg(d, x));
312 MP_COPY(x);
313 if (d) MP_DROP(d);
314 return (x);
315 }
316
317 #define UNOP(pre, name) \
318 static PyObject *pre##_py##name(PyObject *x) \
319 { return mp_pywrap(pre##_##name(MP_NEW, MP_X(x))); }
320 UNOP(mp, neg)
321 UNOP(mp, abs)
322 UNOP(mp, not2c)
323 #undef UNOP
324
325 static PyObject *mp_pyid(PyObject *x) { RETURN_OBJ(x); }
326
327 #define gf_lsr mp_lsr
328 #define SHIFTOP(pre, name, rname) \
329 static PyObject *pre##_py##name(PyObject *x, PyObject *y) { \
330 mp *xx, *yy; \
331 PyObject *z = 0; \
332 long n; \
333 if (mpbinop(x, y, &xx, &yy)) RETURN_NOTIMPL; \
334 if (mp_tolong_checked(yy, &n)) goto end; \
335 if (n < 0) \
336 z = pre##_pywrap(mp_##rname(MP_NEW, xx, -n)); \
337 else \
338 z = pre##_pywrap(mp_##name(MP_NEW, xx, n)); \
339 end: \
340 MP_DROP(xx); MP_DROP(yy); \
341 return (z); \
342 }
343 SHIFTOP(mp, lsl2c, lsr2c)
344 SHIFTOP(mp, lsr2c, lsl2c)
345 SHIFTOP(gf, lsl, lsr)
346 SHIFTOP(gf, lsr, lsl)
347 #undef SHIFTOP
348
349 #define DIVOP(pre, name, qq, rr, gather) \
350 static PyObject *pre##_py##name(PyObject *x, PyObject *y) { \
351 mp *xx, *yy; \
352 PyObject *z = 0; \
353 INIT_##qq(q) INIT_##rr(r) \
354 if (mpbinop(x, y, &xx, &yy)) RETURN_NOTIMPL; \
355 if (MP_ZEROP(yy)) \
356 ZDIVERR("division by zero"); \
357 pre##_div(ARG_##qq(q), ARG_##rr(r), xx, yy); \
358 z = gather; \
359 end: \
360 MP_DROP(xx); MP_DROP(yy); \
361 return (z); \
362 }
363 #define INIT_YES(p) mp *p = MP_NEW;
364 #define INIT_NO(p)
365 #define ARG_YES(p) &p
366 #define ARG_NO(p) 0
367 DIVOP(mp, divmod, YES, YES,
368 Py_BuildValue("(NN)", mp_pywrap(q), mp_pywrap(r)))
369 DIVOP(mp, div, YES, NO, mp_pywrap(q))
370 DIVOP(mp, mod, NO, YES, mp_pywrap(r))
371 DIVOP(gf, divmod, YES, YES,
372 Py_BuildValue("(NN)", gf_pywrap(q), gf_pywrap(r)))
373 DIVOP(gf, div, YES, NO, gf_pywrap(q))
374 DIVOP(gf, mod, NO, YES, gf_pywrap(r))
375 #undef INIT_YES
376 #undef INIT_NO
377 #undef ARG_YES
378 #undef ARG_NO
379 #undef DIVOP
380
381 static mp *mp_modinv_checked(mp *d, mp *x, mp *p)
382 {
383 mp *g = MP_NEW;
384 mp_gcd(&g, 0, &d, p, x);
385 if (!MP_EQ(g, MP_ONE)) {
386 MP_DROP(g); MP_DROP(d);
387 PyErr_SetString(PyExc_ZeroDivisionError, "no modular inverse");
388 return (0);
389 }
390 MP_DROP(g); return (d);
391 }
392
393 static PyObject *mp_pyexp(PyObject *x, PyObject *y, PyObject *z)
394 {
395 mp *xx = 0, *yy = 0, *zz = 0;
396 mp *r = 0;
397 PyObject *rc = 0;
398
399 if ((xx = tomp(x)) == 0 || (yy = tomp(y)) == 0 ||
400 (z && z != Py_None && (zz = tomp(z)) == 0)) {
401 mp_drop(xx); mp_drop(yy); mp_drop(zz);
402 RETURN_NOTIMPL;
403 }
404 if (!z || z == Py_None) {
405 if (MP_NEGP(yy)) VALERR("negative exponent");
406 r = mp_exp(MP_NEW, xx, yy);
407 } else {
408 if (!MP_POSP(zz)) VALERR("modulus must be positive");
409 if (MP_NEGP(yy)) {
410 if ((xx = mp_modinv_checked(xx, xx, zz)) == 0) goto end;
411 yy = mp_neg(yy, yy);
412 }
413 if (MP_ODDP(zz)) {
414 mpmont mm;
415 mpmont_create(&mm, zz);
416 r = mpmont_exp(&mm, MP_NEW, xx, yy);
417 mpmont_destroy(&mm);
418 } else {
419 mpbarrett mb;
420 mpbarrett_create(&mb, zz);
421 r = mpbarrett_exp(&mb, MP_NEW, xx, yy);
422 mpbarrett_destroy(&mb);
423 }
424 }
425 rc = mp_pywrap(r);
426 end:
427 mp_drop(xx); mp_drop(yy); mp_drop(zz);
428 return (rc);
429 }
430
431 static mp *gf_modinv_checked(mp *d, mp *x, mp *p)
432 {
433 mp *g = MP_NEW;
434 gf_gcd(&g, 0, &d, p, x);
435 if (!MP_EQ(g, MP_ONE)) {
436 MP_DROP(g); MP_DROP(d);
437 PyErr_SetString(PyExc_ZeroDivisionError, "no modular inverse");
438 return (0);
439 }
440 MP_DROP(g); return (d);
441 }
442
443 #define BASEOP(name, radix, pre) \
444 static PyObject *mp_py##name(PyObject *x) \
445 { return mp_topystring(MP_X(x), radix, 0, pre, 0); }
446 BASEOP(oct, 8, "0");
447 BASEOP(hex, 16, "0x");
448 #undef BASEOP
449
450 static int mp_pynonzerop(PyObject *x) { return !MP_ZEROP(MP_X(x)); }
451
452 static PyObject *mp_pyint(PyObject *x)
453 {
454 long l;
455 if (mp_tolong_checked(MP_X(x), &l)) return (0);
456 return (PyInt_FromLong(l));
457 }
458 static PyObject *mp_pylong(PyObject *x)
459 { return (mp_topylong(MP_X(x))); }
460 static PyObject *mp_pyfloat(PyObject *x)
461 {
462 PyObject *l = mp_topylong(MP_X(x));
463 double f = PyLong_AsDouble(l);
464 Py_DECREF(l);
465 return (PyFloat_FromDouble(f));
466 }
467
468 #define COERCE(pre, PRE) \
469 static int pre##_pycoerce(PyObject **x, PyObject **y) \
470 { \
471 mp *z; \
472 \
473 if (PRE##_PYCHECK(*y)) { \
474 Py_INCREF(*x); Py_INCREF(*y); \
475 return (0); \
476 } \
477 if ((z = tomp(*y)) != 0) { \
478 Py_INCREF(*x); \
479 *y = pre##_pywrap(z); \
480 return (0); \
481 } \
482 return (1); \
483 }
484 COERCE(mp, MP)
485 COERCE(gf, GF)
486 #undef COERCE
487
488 static int mp_pycompare(PyObject *x, PyObject *y)
489 { return mp_cmp(MP_X(x), MP_X(y)); }
490
491 static PyObject *mp_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
492 {
493 PyObject *x;
494 mp *z;
495 mp_pyobj *zz = 0;
496 int radix = 0;
497 char *kwlist[] = { "x", "radix", 0 };
498
499 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O|i:new", kwlist, &x, &radix))
500 goto end;
501 if (MP_PYCHECK(x)) RETURN_OBJ(x);
502 if (!good_radix_p(radix, 1)) VALERR("bad radix");
503 if ((z = mp_frompyobject(x, radix)) == 0) {
504 PyErr_Format(PyExc_TypeError, "can't convert %.100s to mp",
505 x->ob_type->tp_name);
506 goto end;
507 }
508 zz = (mp_pyobj *)ty->tp_alloc(ty, 0);
509 zz->x = z;
510 end:
511 return ((PyObject *)zz);
512 }
513
514 static long mp_pyhash(PyObject *me)
515 {
516 long h;
517 PyObject *l = mp_topylong(MP_X(me)); h = PyObject_Hash(l);
518 Py_DECREF(l); return (h);
519 }
520
521 static PyObject *mpmeth_jacobi(PyObject *me, PyObject *arg)
522 {
523 mp *y = 0;
524 PyObject *z = 0;
525
526 if (!PyArg_ParseTuple(arg, "O&:jacobi", convmp, &y)) goto end;
527 if (MP_NEGP(MP_X(me)) || MP_EVENP(MP_X(me)))
528 VALERR("must be positive and odd");
529 z = PyInt_FromLong(mp_jacobi(y, MP_X(me)));
530 end:
531 if (y) MP_DROP(y);
532 return (z);
533 }
534
535 #define BITOP(pre, name, c) \
536 static PyObject *pre##meth_##name(PyObject *me, PyObject *arg) \
537 { \
538 int i; \
539 if (!PyArg_ParseTuple(arg, "i:" #name, &i)) return (0); \
540 return (pre##_pywrap(mp_##name##c(MP_NEW, MP_X(me), i))); \
541 }
542 BITOP(mp, setbit, 2c);
543 BITOP(mp, clearbit, 2c);
544 BITOP(gf, setbit, );
545 BITOP(gf, clearbit, );
546 #undef BITOP
547
548 static PyObject *mpmeth_testbit(PyObject *me, PyObject *arg)
549 {
550 int i;
551 if (!PyArg_ParseTuple(arg, "i:testbit", &i)) return (0);
552 return (getbool(mp_testbit2c(MP_X(me), i)));
553 }
554
555 static PyObject *gfmeth_testbit(PyObject *me, PyObject *arg)
556 {
557 int i;
558 if (!PyArg_ParseTuple(arg, "i:testbit", &i)) return (0);
559 return (getbool(mp_testbit(MP_X(me), i)));
560 }
561
562 static PyObject *mpmeth_odd(PyObject *me, PyObject *arg)
563 {
564 mp *t;
565 size_t s;
566
567 if (!PyArg_ParseTuple(arg, ":odd")) return (0);
568 t = mp_odd(MP_NEW, MP_X(me), &s);
569 return (Py_BuildValue("(lN)", (long)s, mp_pywrap(t)));
570 }
571
572 static PyObject *mpmeth_sqr(PyObject *me, PyObject *arg)
573 {
574 if (!PyArg_ParseTuple(arg, ":sqr")) return (0);
575 return (mp_pywrap(mp_sqr(MP_NEW, MP_X(me))));
576 }
577
578 static PyObject *mpmeth_sqrt(PyObject *me, PyObject *arg)
579 {
580 if (!PyArg_ParseTuple(arg, ":sqrt")) return (0);
581 if (MP_NEGP(MP_X(me))) VALERR("negative root");
582 return (mp_pywrap(mp_sqrt(MP_NEW, MP_X(me))));
583 end:
584 return (0);
585 }
586
587 static PyObject *mpmeth_gcd(PyObject *me, PyObject *arg)
588 {
589 mp *y = 0, *zz = MP_NEW;
590 PyObject *z = 0;
591
592 if (!PyArg_ParseTuple(arg, "O&:gcd", convmp, &y)) goto end;
593 mp_gcd(&zz, 0, 0, MP_X(me), y);
594 z = mp_pywrap(zz);
595 end:
596 if (y) MP_DROP(y);
597 return (z);
598 }
599
600 static PyObject *mpmeth_gcdx(PyObject *me, PyObject *arg)
601 {
602 PyObject *z = 0;
603 mp *yy = 0, *zz = MP_NEW, *uu = MP_NEW, *vv = MP_NEW;
604
605 if (!PyArg_ParseTuple(arg, "O&:gcdx", convmp, &yy)) goto end;
606 mp_gcd(&zz, &uu, &vv, MP_X(me), yy);
607 z = Py_BuildValue("(NNN)",
608 mp_pywrap(zz), mp_pywrap(uu), mp_pywrap(vv));
609 end:
610 if (yy) MP_DROP(yy);
611 return (z);
612 }
613
614 static PyObject *mpmeth_modinv(PyObject *me, PyObject *arg)
615 {
616 PyObject *z = 0;
617 mp *yy = 0, *zz = MP_NEW;
618
619 if (!PyArg_ParseTuple(arg, "O&:modinv", convmp, &yy) ||
620 (zz = mp_modinv_checked(MP_NEW, yy, MP_X(me))) == 0)
621 goto end;
622 z = mp_pywrap(zz);
623 end:
624 if (yy) MP_DROP(yy);
625 return (z);
626 }
627
628 static PyObject *mpmeth_tostring(PyObject *me, PyObject *arg, PyObject *kw)
629 {
630 int radix = 10;
631 char *kwlist[] = { "radix", 0 };
632 if (!PyArg_ParseTupleAndKeywords(arg, kw, "|i:tostring", kwlist, &radix))
633 goto end;
634 if (!good_radix_p(radix, 0)) VALERR("bad radix");
635 return (mp_topystring(MP_X(me), radix, 0, 0, 0));
636 end:
637 return (0);
638 }
639
640 static PyObject *mpmeth_modsqrt(PyObject *me, PyObject *arg)
641 {
642 PyObject *z = 0;
643 mp *yy = 0, *zz = MP_NEW;
644
645 if (!PyArg_ParseTuple(arg, "O&:modsqrt", convmp, &yy)) goto end;
646 if ((zz = mp_modsqrt(MP_NEW, yy, MP_X(me))) == 0)
647 VALERR("no modular square root");
648 z = mp_pywrap(zz);
649 end:
650 if (yy) MP_DROP(yy);
651 return (z);
652 }
653
654 #define STOREOP(name, c) \
655 static PyObject *mpmeth_##name(PyObject *me, \
656 PyObject *arg, PyObject *kw) \
657 { \
658 long len = -1; \
659 char *kwlist[] = { "len", 0 }; \
660 PyObject *rc = 0; \
661 \
662 if (!PyArg_ParseTupleAndKeywords(arg, kw, "|l:" #name, \
663 kwlist, &len)) \
664 goto end; \
665 if (len < 0) { \
666 len = mp_octets##c(MP_X(me)); \
667 if (!len) len = 1; \
668 } \
669 rc = bytestring_pywrap(0, len); \
670 mp_##name(MP_X(me), PyString_AS_STRING(rc), len); \
671 end: \
672 return (rc); \
673 }
674 STOREOP(storel, )
675 STOREOP(storeb, )
676 STOREOP(storel2c, 2c)
677 STOREOP(storeb2c, 2c)
678 #undef STOREOP
679
680 #define BUFOP(ty, pyty) \
681 static PyObject *meth__##pyty##_frombuf(PyObject *me, PyObject *arg) \
682 { \
683 buf b; \
684 char *p; \
685 int sz; \
686 PyObject *rc = 0; \
687 mp *x; \
688 \
689 if (!PyArg_ParseTuple(arg, "Os#:frombuf", &me, &p, &sz)) goto end; \
690 buf_init(&b, p, sz); \
691 if ((x = buf_getmp(&b)) == 0) VALERR("malformed data"); \
692 rc = Py_BuildValue("(NN)", ty##_pywrap(x), \
693 bytestring_pywrapbuf(&b)); \
694 end: \
695 return (rc); \
696 }
697 BUFOP(mp, MP)
698 BUFOP(gf, GF)
699 #undef BUFOP
700
701 static PyObject *mpmeth_tobuf(PyObject *me, PyObject *arg)
702 {
703 buf b;
704 PyObject *rc;
705 mp *x;
706 size_t n;
707
708 if (!PyArg_ParseTuple(arg, ":tobuf")) return (0);
709 x = MP_X(me);
710 n = mp_octets(x) + 3;
711 rc = bytestring_pywrap(0, n);
712 buf_init(&b, PyString_AS_STRING(rc), n);
713 buf_putmp(&b, x);
714 assert(BOK(&b));
715 _PyString_Resize(&rc, BLEN(&b));
716 return (rc);
717 }
718
719 static PyObject *mpmeth_primep(PyObject *me, PyObject *arg, PyObject *kw)
720 {
721 grand *r = &rand_global;
722 char *kwlist[] = { "rng", 0 };
723 PyObject *rc = 0;
724
725 if (!PyArg_ParseTupleAndKeywords(arg, kw, "|O&", kwlist, convgrand, &r))
726 goto end;
727 rc = getbool(pgen_primep(MP_X(me), r));
728 end:
729 return (rc);
730 }
731
732 static PyObject *mpget_nbits(PyObject *me, void *hunoz)
733 { return (PyInt_FromLong(mp_bits(MP_X(me)))); }
734
735 static PyObject *mpget_noctets(PyObject *me, void *hunoz)
736 { return (PyInt_FromLong(mp_octets(MP_X(me)))); }
737
738 static PyObject *mpget_noctets2c(PyObject *me, void *hunoz)
739 { return (PyInt_FromLong(mp_octets2c(MP_X(me)))); }
740
741 static PyGetSetDef mp_pygetset[] = {
742 #define GETSETNAME(op, func) mp##op##_##func
743 GET (nbits, "X.nbits -> bit length of X")
744 GET (noctets, "X.noctets -> octet length of X")
745 GET (noctets2c, "X.noctets2c -> two's complement octet length of X")
746 #undef GETSETNAME
747 { 0 }
748 };
749
750 static PyMethodDef mp_pymethods[] = {
751 #define METHNAME(func) mpmeth_##func
752 METH (jacobi, "X.jacobi(Y) -> Jacobi symbol (Y/X) (NB inversion!)")
753 METH (setbit, "X.setbit(N) -> X with bit N set")
754 METH (clearbit, "X.clearbit(N) -> X with bit N clear")
755 METH (testbit, "X.testbit(N) -> true/false if bit N set/clear in X")
756 METH (odd, "X.odd() -> S, T where X = 2^S T with T odd")
757 METH (sqr, "X.sqr() -> X^2")
758 METH (sqrt, "X.sqrt() -> largest integer <= sqrt(X)")
759 METH (gcd, "X.gcd(Y) -> gcd(X, Y)")
760 METH (gcdx,
761 "X.gcdx(Y) -> (gcd(X, Y), U, V) with X U + Y V = gcd(X, Y)")
762 METH (modinv, "X.modinv(Y) -> multiplicative inverse of Y mod X")
763 METH (modsqrt, "X.modsqrt(Y) -> square root of Y mod X, if X prime")
764 KWMETH(primep, "X.primep(rng = rand) -> true/false if X is prime")
765 KWMETH(tostring, "X.tostring(radix = 10) -> STR")
766 KWMETH(storel, "X.storel(len = -1) -> little-endian bytes")
767 KWMETH(storeb, "X.storeb(len = -1) -> big-endian bytes")
768 KWMETH(storel2c,
769 "X.storel2c(len = -1) -> little-endian bytes, two's complement")
770 KWMETH(storeb2c,
771 "X.storeb2c(len = -1) -> big-endian bytes, two's complement")
772 METH (tobuf, "X.tobuf() -> buffer format")
773 #undef METHNAME
774 { 0 }
775 };
776
777 static PyNumberMethods mp_pynumber = {
778 mp_pyadd, /* @nb_add@ */
779 mp_pysub, /* @nb_subtract@ */
780 mp_pymul, /* @nb_multiply@ */
781 0, /* @nb_divide@ */
782 mp_pymod, /* @nb_remainder@ */
783 mp_pydivmod, /* @nb_divmod@ */
784 mp_pyexp, /* @nb_power@ */
785 mp_pyneg, /* @nb_negative@ */
786 mp_pyid, /* @nb_positive@ */
787 mp_pyabs, /* @nb_absolute@ */
788 mp_pynonzerop, /* @nb_nonzero@ */
789 mp_pynot2c, /* @nb_invert@ */
790 mp_pylsl2c, /* @nb_lshift@ */
791 mp_pylsr2c, /* @nb_rshift@ */
792 mp_pyand2c, /* @nb_and@ */
793 mp_pyxor2c, /* @nb_xor@ */
794 mp_pyor2c, /* @nb_or@ */
795 mp_pycoerce, /* @nb_coerce@ */
796 mp_pyint, /* @nb_int@ */
797 mp_pylong, /* @nb_long@ */
798 mp_pyfloat, /* @nb_float@ */
799 mp_pyoct, /* @nb_oct@ */
800 mp_pyhex, /* @nb_hex@ */
801
802 0, /* @nb_inplace_add@ */
803 0, /* @nb_inplace_subtract@ */
804 0, /* @nb_inplace_multiply@ */
805 0, /* @nb_inplace_divide@ */
806 0, /* @nb_inplace_remainder@ */
807 0, /* @nb_inplace_power@ */
808 0, /* @nb_inplace_lshift@ */
809 0, /* @nb_inplace_rshift@ */
810 0, /* @nb_inplace_and@ */
811 0, /* @nb_inplace_xor@ */
812 0, /* @nb_inplace_or@ */
813
814 mp_pydiv, /* @nb_floor_divide@ */
815 0, /* @nb_true_divide@ */
816 0, /* @nb_inplace_floor_divide@ */
817 0, /* @nb_inplace_true_divide@ */
818 };
819
820 static PyTypeObject mp_pytype_skel = {
821 PyObject_HEAD_INIT(0) 0, /* Header */
822 "catacomb.MP", /* @tp_name@ */
823 sizeof(mp_pyobj), /* @tp_basicsize@ */
824 0, /* @tp_itemsize@ */
825
826 mp_pydealloc, /* @tp_dealloc@ */
827 0, /* @tp_print@ */
828 0, /* @tp_getattr@ */
829 0, /* @tp_setattr@ */
830 mp_pycompare, /* @tp_compare@ */
831 mp_pyrepr, /* @tp_repr@ */
832 &mp_pynumber, /* @tp_as_number@ */
833 0, /* @tp_as_sequence@ */
834 0, /* @tp_as_mapping@ */
835 mp_pyhash, /* @tp_hash@ */
836 0, /* @tp_call@ */
837 mp_pystr, /* @tp_str@ */
838 0, /* @tp_getattro@ */
839 0, /* @tp_setattro@ */
840 0, /* @tp_as_buffer@ */
841 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
842 Py_TPFLAGS_CHECKTYPES |
843 Py_TPFLAGS_BASETYPE,
844
845 /* @tp_doc@ */
846 "Multiprecision integers, similar to `long' but more efficient and\n\
847 versatile. Support all the standard arithmetic operations.\n\
848 \n\
849 Constructor mp(X, radix = R) attempts to convert X to an `mp'. If\n\
850 X is a string, it's read in radix-R form, or we look for a prefix\n\
851 if R = 0. Other acceptable things are ints and longs.\n\
852 \n\
853 Notes:\n\
854 \n\
855 * Use `//' for division. MPs don't have `/' division.",
856
857 0, /* @tp_traverse@ */
858 0, /* @tp_clear@ */
859 0, /* @tp_richcompare@ */
860 0, /* @tp_weaklistoffset@ */
861 0, /* @tp_iter@ */
862 0, /* @tp_iternext@ */
863 mp_pymethods, /* @tp_methods@ */
864 0, /* @tp_members@ */
865 mp_pygetset, /* @tp_getset@ */
866 0, /* @tp_base@ */
867 0, /* @tp_dict@ */
868 0, /* @tp_descr_get@ */
869 0, /* @tp_descr_set@ */
870 0, /* @tp_dictoffset@ */
871 0, /* @tp_init@ */
872 PyType_GenericAlloc, /* @tp_alloc@ */
873 mp_pynew, /* @tp_new@ */
874 0, /* @tp_free@ */
875 0 /* @tp_is_gc@ */
876 };
877
878 static PyObject *meth__MP_fromstring(PyObject *me,
879 PyObject *arg, PyObject *kw)
880 {
881 int r = 0;
882 char *p;
883 int len;
884 PyObject *z = 0;
885 mp *zz;
886 mptext_stringctx sc;
887 char *kwlist[] = { "class", "x", "radix", 0 };
888
889 if (!PyArg_ParseTupleAndKeywords(arg, kw, "Os#|i:fromstring",
890 kwlist, &me, &p, &len, &r))
891 goto end;
892 if (!good_radix_p(r, 1)) VALERR("bad radix");
893 sc.buf = p; sc.lim = p + len;
894 if ((zz = mp_read(MP_NEW, r, &mptext_stringops, &sc)) == 0)
895 SYNERR("bad integer");
896 z = Py_BuildValue("(Ns#)", mp_pywrap(zz), sc.buf, (int)(sc.lim - sc.buf));
897 end:
898 return (z);
899 }
900
901 static PyObject *meth__MP_product(PyObject *me, PyObject *arg)
902 {
903 mpmul m;
904 PyObject *q, *i;
905 mp *x;
906
907 if (PyTuple_Size(arg) != 2) {
908 i = PyObject_GetIter(arg);
909 PyIter_Next(i);
910 } else {
911 if ((q = PyTuple_GetItem(arg, 1)) == 0) return (0);
912 if ((i = PyObject_GetIter(q)) == 0) {
913 PyErr_Clear(); /* that's ok */
914 i = PyObject_GetIter(arg);
915 }
916 }
917 if (!i) return (0);
918 mpmul_init(&m);
919 while ((q = PyIter_Next(i)) != 0) {
920 x = getmp(q); Py_DECREF(q); if (!x) {
921 MP_DROP(mpmul_done(&m));
922 Py_DECREF(i);
923 return (0);
924 }
925 mpmul_add(&m, x);
926 MP_DROP(x);
927 }
928 x = mpmul_done(&m);
929 Py_DECREF(i);
930 return (mp_pywrap(x));
931 }
932
933 #define LOADOP(pre, py, name) \
934 static PyObject *meth__##py##_##name(PyObject *me, PyObject *arg) \
935 { \
936 char *p; \
937 int len; \
938 if (!PyArg_ParseTuple(arg, "Os#:" #name, &me, &p, &len)) return (0); \
939 return (pre##_pywrap(mp_##name(MP_NEW, p, len))); \
940 }
941 LOADOP(mp, MP, loadl)
942 LOADOP(mp, MP, loadb)
943 LOADOP(mp, MP, loadl2c)
944 LOADOP(mp, MP, loadb2c)
945 LOADOP(gf, GF, loadl)
946 LOADOP(gf, GF, loadb)
947 #undef LOADOP
948
949 /*----- Montgomery reduction ----------------------------------------------*/
950
951 typedef struct mpmont_pyobj {
952 PyObject_HEAD
953 mpmont mm;
954 } mpmont_pyobj;
955
956 #define MPMONT_PY(o) (&((mpmont_pyobj *)(o))->mm)
957
958 static PyObject *mmmeth_int(PyObject *me, PyObject *arg)
959 {
960 PyObject *z = 0;
961 mp *yy = 0;
962 mpmont *mm = MPMONT_PY(me);
963
964 if (!PyArg_ParseTuple(arg, "O&:in", convmp, &yy))
965 goto end;
966 mp_div(0, &yy, yy, mm->m);
967 z = mp_pywrap(mpmont_mul(mm, MP_NEW, yy, mm->r2));
968 end:
969 if (yy) MP_DROP(yy);
970 return (z);
971 }
972
973 static PyObject *mmmeth_mul(PyObject *me, PyObject *arg)
974 {
975 PyObject *rc = 0;
976 mp *yy = 0, *zz = 0;
977
978 if (!PyArg_ParseTuple(arg, "O&O&:mul", convmp, &yy, convmp, &zz))
979 goto end;
980 rc = mp_pywrap(mpmont_mul(MPMONT_PY(me), MP_NEW, yy, zz));
981 end:
982 if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
983 return (rc);
984 }
985
986 static PyObject *mmmeth_exp(PyObject *me, PyObject *arg)
987 {
988 PyObject *rc = 0;
989 mp *yy = 0, *zz = 0;
990
991 if (!PyArg_ParseTuple(arg, "O&O&:exp", convmp, &yy, convmp, &zz))
992 goto end;
993 if (MP_NEGP(zz)) {
994 if ((yy = mp_modinv_checked(yy, yy, MPMONT_PY(me)->m)) == 0) goto end;
995 zz = mp_neg(zz, zz);
996 }
997 rc = mp_pywrap(mpmont_exp(MPMONT_PY(me), MP_NEW, yy, zz));
998 end:
999 if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
1000 return (rc);
1001 }
1002
1003 static PyObject *mmmeth_expr(PyObject *me, PyObject *arg)
1004 {
1005 PyObject *rc = 0;
1006 mp *yy = 0, *zz = 0;
1007
1008 if (!PyArg_ParseTuple(arg, "O&O&:expr", convmp, &yy, convmp, &zz))
1009 goto end;
1010 if (MP_NEGP(zz)) {
1011 yy = mpmont_reduce(MPMONT_PY(me), yy, yy);
1012 if ((yy = mp_modinv_checked(yy, yy, MPMONT_PY(me)->m)) == 0) goto end;
1013 yy = mpmont_mul(MPMONT_PY(me), yy, yy, MPMONT_PY(me)->r2);
1014 zz = mp_neg(zz, zz);
1015 }
1016 rc = mp_pywrap(mpmont_expr(MPMONT_PY(me), MP_NEW, yy, zz));
1017 end:
1018 if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
1019 return (rc);
1020 }
1021
1022 static PyObject *mm_mexpr_id(PyObject *me)
1023 { return mp_pywrap(MP_COPY(MPMONT_PY(me)->r)); }
1024
1025 static int mm_mexpr_fill(void *p, PyObject *me, PyObject *x, PyObject *y)
1026 {
1027 mp *xx = 0, *yy = 0;
1028 mp_expfactor *f = p;
1029 mpmont *mm = MPMONT_PY(me);
1030
1031 if ((xx = getmp(x)) == 0 || (yy = getmp(y)) == 0)
1032 goto fail;
1033 if (MP_NEGP(yy)) {
1034 xx = mpmont_reduce(mm, xx, xx);
1035 if ((xx = mp_modinv_checked(xx, xx, yy)) == 0)
1036 goto fail;
1037 xx = mpmont_mul(mm, xx, xx, mm->r2);
1038 yy = mp_neg(yy, yy);
1039 }
1040 f->base = xx;
1041 f->exp = yy;
1042 return (0);
1043
1044 fail:
1045 mp_drop(xx); mp_drop(yy);
1046 return (-1);
1047 }
1048
1049 static PyObject *mm_mexpr(PyObject *me, void *v, int n)
1050 { return mp_pywrap(mpmont_mexpr(MPMONT_PY(me), MP_NEW, v, n)); }
1051
1052 static void mp_mexp_drop(void *p)
1053 {
1054 mp_expfactor *f = p;
1055 mp_drop(f->base);
1056 mp_drop(f->exp);
1057 }
1058
1059 static PyObject *mmmeth_mexpr(PyObject *me, PyObject *arg)
1060 {
1061 return mexp_common(me, arg, sizeof(mp_expfactor),
1062 mm_mexpr_id, mm_mexpr_fill, mm_mexpr, mp_mexp_drop);
1063 }
1064
1065 static PyObject *mp_mexp_id(PyObject *me)
1066 { return mp_pywrap(MP_ONE); }
1067
1068 static int mp_mexp_fill(void *p, PyObject *me, PyObject *x, PyObject *y)
1069 {
1070 mp *xx = 0, *yy = 0;
1071 mp_expfactor *f = p;
1072
1073 if ((xx = getmp(x)) == 0 || (yy = getmp(y)) == 0)
1074 goto fail;
1075 if (MP_NEGP(yy)) {
1076 if ((xx = mp_modinv_checked(xx, xx, yy)) == 0)
1077 goto fail;
1078 yy = mp_neg(yy, yy);
1079 }
1080 f->base = xx;
1081 f->exp = yy;
1082 return (0);
1083
1084 fail:
1085 mp_drop(xx); mp_drop(yy);
1086 return (-1);
1087 }
1088
1089 static PyObject *mm_mexp(PyObject *me, void *v, int n)
1090 { return mp_pywrap(mpmont_mexp(MPMONT_PY(me), MP_NEW, v, n)); }
1091
1092 static PyObject *mmmeth_mexp(PyObject *me, PyObject *arg)
1093 {
1094 return mexp_common(me, arg, sizeof(mp_expfactor),
1095 mp_mexp_id, mp_mexp_fill, mm_mexp, mp_mexp_drop);
1096 }
1097
1098 #define mmmeth_ext mmmeth_reduce
1099 static PyObject *mmmeth_reduce(PyObject *me, PyObject *arg)
1100 {
1101 PyObject *z = 0;
1102 mp *yy = 0;
1103
1104 if (!PyArg_ParseTuple(arg, "O&", convmp, &yy)) goto end;
1105 z = mp_pywrap(mpmont_reduce(MPMONT_PY(me), MP_NEW, yy));
1106 end:
1107 return (z);
1108 }
1109
1110 static void mpmont_pydealloc(PyObject *me)
1111 {
1112 mpmont_destroy(MPMONT_PY(me));
1113 FREEOBJ(me);
1114 }
1115
1116 static PyObject *mpmont_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
1117 {
1118 mpmont_pyobj *mm = 0;
1119 char *kwlist[] = { "m", 0 };
1120 mp *xx = 0;
1121
1122 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convmp, &xx))
1123 goto end;
1124 if (!MP_POSP(xx) || !MP_ODDP(xx)) VALERR("m must be positive and odd");
1125 mm = (mpmont_pyobj *)ty->tp_alloc(ty, 0);
1126 mpmont_create(&mm->mm, xx);
1127 end:
1128 if (xx) MP_DROP(xx);
1129 return ((PyObject *)mm);
1130 }
1131
1132 static PyObject *mmget_m(PyObject *me, void *hunoz)
1133 { return (mp_pywrap(MP_COPY(MPMONT_PY(me)->m))); }
1134
1135 static PyObject *mmget_r(PyObject *me, void *hunoz)
1136 { return (mp_pywrap(MP_COPY(MPMONT_PY(me)->r))); }
1137
1138 static PyObject *mmget_r2(PyObject *me, void *hunoz)
1139 { return (mp_pywrap(MP_COPY(MPMONT_PY(me)->r2))); }
1140
1141 static PyGetSetDef mpmont_pygetset[] = {
1142 #define GETSETNAME(op, name) mm##op##_##name
1143 GET (m, "M.m -> modulus for reduction")
1144 GET (r, "M.r -> multiplicative identity")
1145 GET (r2, "M.r2 -> M.r^2, Montgomerization factor")
1146 #undef GETSETNAME
1147 { 0 }
1148 };
1149
1150 static PyMethodDef mpmont_pymethods[] = {
1151 #define METHNAME(name) mmmeth_##name
1152 METH (int, "M.out(X) -> XR")
1153 METH (mul, "M.mul(XR, YR) -> ZR where Z = X Y")
1154 METH (expr, "M.expr(XR, N) -> ZR where Z = X^N mod M.m")
1155 METH (mexpr, "\
1156 B.mexp([(XR0, N0), (XR1, N1), ...]) = ZR where Z = X0^N0 X1^N1 mod B.m\n\
1157 \t(the list may be flattened if this more convenient.)")
1158 METH (reduce, "M.reduce(XR) -> X")
1159 METH (ext, "M.ext(XR) -> X")
1160 METH (exp, "M.exp(X, N) -> X^N mod M.m")
1161 METH (mexp, "\
1162 B.mexp([(X0, N0), (X1, N1), ...]) = X0^N0 X1^N1 mod B.m\n\
1163 \t(the list may be flattened if this more convenient.)")
1164 #undef METHNAME
1165 { 0 }
1166 };
1167
1168 static PyTypeObject *mpmont_pytype, mpmont_pytype_skel = {
1169 PyObject_HEAD_INIT(0) 0, /* Header */
1170 "catacomb.MPMont", /* @tp_name@ */
1171 sizeof(mpmont_pyobj), /* @tp_basicsize@ */
1172 0, /* @tp_itemsize@ */
1173
1174 mpmont_pydealloc, /* @tp_dealloc@ */
1175 0, /* @tp_print@ */
1176 0, /* @tp_getattr@ */
1177 0, /* @tp_setattr@ */
1178 0, /* @tp_compare@ */
1179 0, /* @tp_repr@ */
1180 0, /* @tp_as_number@ */
1181 0, /* @tp_as_sequence@ */
1182 0, /* @tp_as_mapping@ */
1183 0, /* @tp_hash@ */
1184 0, /* @tp_call@ */
1185 0, /* @tp_str@ */
1186 0, /* @tp_getattro@ */
1187 0, /* @tp_setattro@ */
1188 0, /* @tp_as_buffer@ */
1189 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
1190 Py_TPFLAGS_BASETYPE,
1191
1192 /* @tp_doc@ */
1193 "A Montgomery reduction context.",
1194
1195 0, /* @tp_traverse@ */
1196 0, /* @tp_clear@ */
1197 0, /* @tp_richcompare@ */
1198 0, /* @tp_weaklistoffset@ */
1199 0, /* @tp_iter@ */
1200 0, /* @tp_iternext@ */
1201 mpmont_pymethods, /* @tp_methods@ */
1202 0, /* @tp_members@ */
1203 mpmont_pygetset, /* @tp_getset@ */
1204 0, /* @tp_base@ */
1205 0, /* @tp_dict@ */
1206 0, /* @tp_descr_get@ */
1207 0, /* @tp_descr_set@ */
1208 0, /* @tp_dictoffset@ */
1209 0, /* @tp_init@ */
1210 PyType_GenericAlloc, /* @tp_alloc@ */
1211 mpmont_pynew, /* @tp_new@ */
1212 0, /* @tp_free@ */
1213 0 /* @tp_is_gc@ */
1214 };
1215
1216 /*----- Barrett reduction -------------------------------------------------*/
1217
1218 typedef struct mpbarrett_pyobj {
1219 PyObject_HEAD
1220 mpbarrett mb;
1221 } mpbarrett_pyobj;
1222
1223 #define MPBARRETT_PY(o) (&((mpbarrett_pyobj *)(o))->mb)
1224
1225 static PyObject *mbmeth_exp(PyObject *me, PyObject *arg)
1226 {
1227 PyObject *rc = 0;
1228 mp *yy = 0, *zz = 0;
1229
1230 if (!PyArg_ParseTuple(arg, "O&O&:exp", convmp, &yy, convmp, &zz))
1231 goto end;
1232 if (MP_NEGP(zz)) {
1233 if ((yy = mp_modinv_checked(yy, yy, MPBARRETT_PY(me)->m)) == 0) goto end;
1234 zz = mp_neg(zz, zz);
1235 }
1236 rc = mp_pywrap(mpbarrett_exp(MPBARRETT_PY(me), MP_NEW, yy, zz));
1237 end:
1238 if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
1239 return (rc);
1240 }
1241
1242 static PyObject *mb_mexp(PyObject *me, void *v, int n)
1243 { return mp_pywrap(mpbarrett_mexp(MPBARRETT_PY(me), MP_NEW, v, n)); }
1244
1245 static PyObject *mbmeth_mexp(PyObject *me, PyObject *arg)
1246 {
1247 return mexp_common(me, arg, sizeof(mp_expfactor),
1248 mp_mexp_id, mp_mexp_fill, mb_mexp, mp_mexp_drop);
1249 }
1250
1251 static PyObject *mbmeth_reduce(PyObject *me, PyObject *arg)
1252 {
1253 PyObject *z = 0;
1254 mp *yy = 0;
1255
1256 if (!PyArg_ParseTuple(arg, "O&:reduce", convmp, &yy))
1257 goto end;
1258 z = mp_pywrap(mpbarrett_reduce(MPBARRETT_PY(me), MP_NEW, yy));
1259 end:
1260 return (z);
1261 }
1262
1263 static void mpbarrett_pydealloc(PyObject *me)
1264 {
1265 mpbarrett_destroy(MPBARRETT_PY(me));
1266 FREEOBJ(me);
1267 }
1268
1269 static PyObject *mpbarrett_pynew(PyTypeObject *ty,
1270 PyObject *arg, PyObject *kw)
1271 {
1272 mpbarrett_pyobj *mb = 0;
1273 char *kwlist[] = { "m", 0 };
1274 mp *xx = 0;
1275
1276 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convmp, &xx))
1277 goto end;
1278 if (!MP_POSP(xx)) VALERR("m must be positive");
1279 mb = (mpbarrett_pyobj *)ty->tp_alloc(ty, 0);
1280 mpbarrett_create(&mb->mb, xx);
1281 end:
1282 if (xx) MP_DROP(xx);
1283 return ((PyObject *)mb);
1284 }
1285
1286 static PyObject *mbget_m(PyObject *me, void *hunoz)
1287 { return (mp_pywrap(MP_COPY(MPBARRETT_PY(me)->m))); }
1288
1289 static PyGetSetDef mpbarrett_pygetset[] = {
1290 #define GETSETNAME(op, name) mb##op##_##name
1291 GET (m, "B.m -> modulus for reduction")
1292 #undef GETSETNAME
1293 { 0 }
1294 };
1295
1296 static PyMethodDef mpbarrett_pymethods[] = {
1297 #define METHNAME(name) mbmeth_##name
1298 METH (reduce, "B.reduce(X) -> X mod B.m")
1299 METH (exp, "B.exp(X, N) -> X^N mod B.m")
1300 METH (mexp, "\
1301 B.mexp([(X0, N0), (X1, N1), ...]) = X0^N0 X1^N1 mod B.m\n\
1302 \t(the list may be flattened if this more convenient.)")
1303 #undef METHNAME
1304 { 0 }
1305 };
1306
1307 static PyTypeObject *mpbarrett_pytype, mpbarrett_pytype_skel = {
1308 PyObject_HEAD_INIT(0) 0, /* Header */
1309 "catacomb.MPBarrett", /* @tp_name@ */
1310 sizeof(mpbarrett_pyobj), /* @tp_basicsize@ */
1311 0, /* @tp_itemsize@ */
1312
1313 mpbarrett_pydealloc, /* @tp_dealloc@ */
1314 0, /* @tp_print@ */
1315 0, /* @tp_getattr@ */
1316 0, /* @tp_setattr@ */
1317 0, /* @tp_compare@ */
1318 0, /* @tp_repr@ */
1319 0, /* @tp_as_number@ */
1320 0, /* @tp_as_sequence@ */
1321 0, /* @tp_as_mapping@ */
1322 0, /* @tp_hash@ */
1323 0, /* @tp_call@ */
1324 0, /* @tp_str@ */
1325 0, /* @tp_getattro@ */
1326 0, /* @tp_setattro@ */
1327 0, /* @tp_as_buffer@ */
1328 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
1329 Py_TPFLAGS_BASETYPE,
1330
1331 /* @tp_doc@ */
1332 "A Barrett reduction context.",
1333
1334 0, /* @tp_traverse@ */
1335 0, /* @tp_clear@ */
1336 0, /* @tp_richcompare@ */
1337 0, /* @tp_weaklistoffset@ */
1338 0, /* @tp_iter@ */
1339 0, /* @tp_iternext@ */
1340 mpbarrett_pymethods, /* @tp_methods@ */
1341 0, /* @tp_members@ */
1342 mpbarrett_pygetset, /* @tp_getset@ */
1343 0, /* @tp_base@ */
1344 0, /* @tp_dict@ */
1345 0, /* @tp_descr_get@ */
1346 0, /* @tp_descr_set@ */
1347 0, /* @tp_dictoffset@ */
1348 0, /* @tp_init@ */
1349 PyType_GenericAlloc, /* @tp_alloc@ */
1350 mpbarrett_pynew, /* @tp_new@ */
1351 0, /* @tp_free@ */
1352 0 /* @tp_is_gc@ */
1353 };
1354
1355 /*----- Nice prime reduction ----------------------------------------------*/
1356
1357 typedef struct mpreduce_pyobj {
1358 PyObject_HEAD
1359 mpreduce mr;
1360 } mpreduce_pyobj;
1361
1362 #define MPREDUCE_PY(o) (&((mpreduce_pyobj *)(o))->mr)
1363
1364 static PyObject *mrmeth_exp(PyObject *me, PyObject *arg)
1365 {
1366 PyObject *rc = 0;
1367 mp *yy = 0, *zz = 0;
1368
1369 if (!PyArg_ParseTuple(arg, "O&O&:exp", convmp, &yy, convmp, &zz))
1370 goto end;
1371 if (MP_NEGP(zz)) {
1372 if ((yy = mp_modinv_checked(yy, yy, MPREDUCE_PY(me)->p)) == 0) goto end;
1373 zz = mp_neg(zz, zz);
1374 }
1375 rc = mp_pywrap(mpreduce_exp(MPREDUCE_PY(me), MP_NEW, yy, zz));
1376 end:
1377 if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
1378 return (rc);
1379 }
1380
1381 static PyObject *mrmeth_reduce(PyObject *me, PyObject *arg)
1382 {
1383 PyObject *z = 0;
1384 mp *yy = 0;
1385
1386 if (!PyArg_ParseTuple(arg, "O&:reduce", convmp, &yy)) goto end;
1387 z = mp_pywrap(mpreduce_do(MPREDUCE_PY(me), MP_NEW, yy));
1388 end:
1389 return (z);
1390 }
1391
1392 static void mpreduce_pydealloc(PyObject *me)
1393 {
1394 mpreduce_destroy(MPREDUCE_PY(me));
1395 FREEOBJ(me);
1396 }
1397
1398 static PyObject *mpreduce_pynew(PyTypeObject *ty,
1399 PyObject *arg, PyObject *kw)
1400 {
1401 mpreduce_pyobj *mr = 0;
1402 mpreduce r;
1403 char *kwlist[] = { "m", 0 };
1404 mp *xx = 0;
1405
1406 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convmp, &xx))
1407 goto end;
1408 if (!MP_POSP(xx)) VALERR("m must be positive");
1409 if (mpreduce_create(&r, xx)) VALERR("bad modulus (must be 2^k - ...)");
1410 mr = (mpreduce_pyobj *)ty->tp_alloc(ty, 0);
1411 mr->mr = r;
1412 end:
1413 if (xx) MP_DROP(xx);
1414 return ((PyObject *)mr);
1415 }
1416
1417 static PyObject *mrget_m(PyObject *me, void *hunoz)
1418 { return (mp_pywrap(MP_COPY(MPREDUCE_PY(me)->p))); }
1419
1420 static PyGetSetDef mpreduce_pygetset[] = {
1421 #define GETSETNAME(op, name) mr##op##_##name
1422 GET (m, "R.m -> modulus for reduction")
1423 #undef GETSETNAME
1424 { 0 }
1425 };
1426
1427 static PyMethodDef mpreduce_pymethods[] = {
1428 #define METHNAME(name) mrmeth_##name
1429 METH (reduce, "R.reduce(X) -> X mod B.m")
1430 METH (exp, "R.exp(X, N) -> X^N mod B.m")
1431 #undef METHNAME
1432 { 0 }
1433 };
1434
1435 static PyTypeObject *mpreduce_pytype, mpreduce_pytype_skel = {
1436 PyObject_HEAD_INIT(0) 0, /* Header */
1437 "catacomb.MPReduce", /* @tp_name@ */
1438 sizeof(mpreduce_pyobj), /* @tp_basicsize@ */
1439 0, /* @tp_itemsize@ */
1440
1441 mpreduce_pydealloc, /* @tp_dealloc@ */
1442 0, /* @tp_print@ */
1443 0, /* @tp_getattr@ */
1444 0, /* @tp_setattr@ */
1445 0, /* @tp_compare@ */
1446 0, /* @tp_repr@ */
1447 0, /* @tp_as_number@ */
1448 0, /* @tp_as_sequence@ */
1449 0, /* @tp_as_mapping@ */
1450 0, /* @tp_hash@ */
1451 0, /* @tp_call@ */
1452 0, /* @tp_str@ */
1453 0, /* @tp_getattro@ */
1454 0, /* @tp_setattro@ */
1455 0, /* @tp_as_buffer@ */
1456 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
1457 Py_TPFLAGS_BASETYPE,
1458
1459 /* @tp_doc@ */
1460 "A reduction context for reduction modulo primes of special form.",
1461
1462 0, /* @tp_traverse@ */
1463 0, /* @tp_clear@ */
1464 0, /* @tp_richcompare@ */
1465 0, /* @tp_weaklistoffset@ */
1466 0, /* @tp_iter@ */
1467 0, /* @tp_iternext@ */
1468 mpreduce_pymethods, /* @tp_methods@ */
1469 0, /* @tp_members@ */
1470 mpreduce_pygetset, /* @tp_getset@ */
1471 0, /* @tp_base@ */
1472 0, /* @tp_dict@ */
1473 0, /* @tp_descr_get@ */
1474 0, /* @tp_descr_set@ */
1475 0, /* @tp_dictoffset@ */
1476 0, /* @tp_init@ */
1477 PyType_GenericAlloc, /* @tp_alloc@ */
1478 mpreduce_pynew, /* @tp_new@ */
1479 0, /* @tp_free@ */
1480 0 /* @tp_is_gc@ */
1481 };
1482
1483 /*----- Chinese Remainder Theorem solution --------------------------------*/
1484
1485 typedef struct mpcrt_pyobj {
1486 PyObject_HEAD
1487 mpcrt c;
1488 } mpcrt_pyobj;
1489
1490 #define MPCRT_PY(o) (&((mpcrt_pyobj *)(o))->c)
1491
1492 static PyObject *mcmeth_solve(PyObject *me, PyObject *arg)
1493 {
1494 mpcrt *c = MPCRT_PY(me);
1495 PyObject *q = 0, *x, *z = 0;
1496 mp *xx;
1497 mp **v = 0;
1498 int i = 0, n = c->k;
1499
1500 Py_INCREF(me);
1501 if (PyTuple_Size(arg) == n)
1502 q = arg;
1503 else if (!PyArg_ParseTuple(arg, "O:solve", &q))
1504 goto end;
1505 Py_INCREF(q);
1506 if (!PySequence_Check(q)) TYERR("want a sequence of residues");
1507 if (PySequence_Size(q) != n) VALERR("residue count mismatch");
1508 v = xmalloc(n * sizeof(*v));
1509 for (i = 0; i < n; i++) {
1510 if ((x = PySequence_GetItem(q, i)) == 0) goto end;
1511 xx = getmp(x); Py_DECREF(x); if (!xx) goto end;
1512 v[i] = xx;
1513 }
1514 z = mp_pywrap(mpcrt_solve(c, MP_NEW, v));
1515 end:
1516 if (v) {
1517 n = i;
1518 for (i = 0; i < n; i++)
1519 MP_DROP(v[i]);
1520 xfree(v);
1521 }
1522 Py_DECREF(me);
1523 Py_XDECREF(q);
1524 return (z);
1525 }
1526
1527 static void mpcrt_pydealloc(PyObject *me)
1528 {
1529 mpcrt *c = MPCRT_PY(me);
1530 mpcrt_destroy(c);
1531 xfree(c->v);
1532 }
1533
1534 static PyObject *mpcrt_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
1535 {
1536 mpcrt_mod *v = 0;
1537 int n, i = 0;
1538 char *kwlist[] = { "mv", 0 };
1539 PyObject *q = 0, *x;
1540 mp *xx;
1541 mpcrt_pyobj *c = 0;
1542
1543 if (PyTuple_Size(arg) > 1)
1544 q = arg;
1545 else if (!PyArg_ParseTupleAndKeywords(arg, kw, "O:new", kwlist, &q))
1546 goto end;
1547 Py_INCREF(q);
1548 if (!PySequence_Check(q)) TYERR("want a sequence of moduli");
1549 n = PySequence_Size(q);
1550 if (PyErr_Occurred()) goto end;
1551 if (!n) VALERR("want at least one modulus");
1552 v = xmalloc(n * sizeof(*v));
1553 for (i = 0; i < n; i++) {
1554 if ((x = PySequence_GetItem(q, i)) == 0) goto end;
1555 xx = getmp(x); Py_DECREF(x); if (!xx) goto end;
1556 v[i].m = xx; v[i].n = 0; v[i].ni = 0; v[i].nni = 0;
1557 }
1558 c = (mpcrt_pyobj *)ty->tp_alloc(ty, 0);
1559 mpcrt_create(&c->c, v, n, 0);
1560 Py_DECREF(q);
1561 return ((PyObject *)c);
1562
1563 end:
1564 if (v) {
1565 n = i;
1566 for (i = 0; i < n; i++)
1567 MP_DROP(v[i].m);
1568 xfree(v);
1569 }
1570 Py_XDECREF(q);
1571 return (0);
1572 }
1573
1574 static PyObject *mcget_product(PyObject *me, void *hunoz)
1575 { return (mp_pywrap(MP_COPY(MPCRT_PY(me)->mb.m))); }
1576
1577 static PyObject *mcget_moduli(PyObject *me, void *hunoz)
1578 {
1579 int i;
1580 PyObject *q;
1581 mpcrt *c = MPCRT_PY(me);
1582
1583 if ((q = PyList_New(c->k)) == 0) return (0);
1584 for (i = 0; i < c->k; i++)
1585 PyList_SetItem(q, i, mp_pywrap(c->v[i].m));
1586 return (q);
1587 }
1588
1589 static PyGetSetDef mpcrt_pygetset[] = {
1590 #define GETSETNAME(op, name) mc##op##_##name
1591 GET (product, "C.product -> product of moduli")
1592 GET (moduli, "C.moduli -> list of individual moduli")
1593 #undef GETSETNAME
1594 { 0 }
1595 };
1596
1597 static PyMethodDef mpcrt_pymethods[] = {
1598 #define METHNAME(name) mcmeth_##name
1599 METH (solve, "C.solve([R0, R1]) -> X mod C.product")
1600 #undef METHNAME
1601 { 0 }
1602 };
1603
1604 static PyTypeObject *mpcrt_pytype, mpcrt_pytype_skel = {
1605 PyObject_HEAD_INIT(0) 0, /* Header */
1606 "catacomb.MPCRT", /* @tp_name@ */
1607 sizeof(mpcrt_pyobj), /* @tp_basicsize@ */
1608 0, /* @tp_itemsize@ */
1609
1610 mpcrt_pydealloc, /* @tp_dealloc@ */
1611 0, /* @tp_print@ */
1612 0, /* @tp_getattr@ */
1613 0, /* @tp_setattr@ */
1614 0, /* @tp_compare@ */
1615 0, /* @tp_repr@ */
1616 0, /* @tp_as_number@ */
1617 0, /* @tp_as_sequence@ */
1618 0, /* @tp_as_mapping@ */
1619 0, /* @tp_hash@ */
1620 0, /* @tp_call@ */
1621 0, /* @tp_str@ */
1622 0, /* @tp_getattro@ */
1623 0, /* @tp_setattro@ */
1624 0, /* @tp_as_buffer@ */
1625 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
1626 Py_TPFLAGS_BASETYPE,
1627
1628 /* @tp_doc@ */
1629 "A context for the solution of Chinese Remainder Theorem problems.",
1630
1631 0, /* @tp_traverse@ */
1632 0, /* @tp_clear@ */
1633 0, /* @tp_richcompare@ */
1634 0, /* @tp_weaklistoffset@ */
1635 0, /* @tp_iter@ */
1636 0, /* @tp_iternext@ */
1637 mpcrt_pymethods, /* @tp_methods@ */
1638 0, /* @tp_members@ */
1639 mpcrt_pygetset, /* @tp_getset@ */
1640 0, /* @tp_base@ */
1641 0, /* @tp_dict@ */
1642 0, /* @tp_descr_get@ */
1643 0, /* @tp_descr_set@ */
1644 0, /* @tp_dictoffset@ */
1645 0, /* @tp_init@ */
1646 PyType_GenericAlloc, /* @tp_alloc@ */
1647 mpcrt_pynew, /* @tp_new@ */
1648 0, /* @tp_free@ */
1649 0 /* @tp_is_gc@ */
1650 };
1651
1652 /*----- Binary polynomials ------------------------------------------------*/
1653
1654 static PyObject *gf_pyrepr(PyObject *o)
1655 { return mp_topystring(MP_X(o), 16, "GF(", "0x", "L)"); }
1656
1657 static PyObject *gf_pyrichcompare(PyObject *x, PyObject *y, int op)
1658 {
1659 mp *xx, *yy;
1660 int xl, yl;
1661 int b;
1662
1663 if (mpbinop(x, y, &xx, &yy)) RETURN_NOTIMPL;
1664 switch (op) {
1665 case Py_EQ: b = MP_EQ(xx, yy); break;
1666 case Py_NE: b = !MP_EQ(xx, yy); break;
1667 default:
1668 xl = mp_bits(xx);
1669 yl = mp_bits(yy);
1670 switch (op) {
1671 case Py_LT: b = xl < yl; break;
1672 case Py_LE: b = xl <= yl; break;
1673 case Py_GT: b = xl > yl; break;
1674 case Py_GE: b = xl >= yl; break;
1675 default: abort();
1676 }
1677 break;
1678 }
1679 MP_DROP(xx); MP_DROP(yy);
1680 return (getbool(b));
1681 }
1682
1683 static PyObject *gf_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
1684 {
1685 PyObject *x;
1686 mp *z;
1687 mp_pyobj *zz = 0;
1688 int radix = 0;
1689 char *kwlist[] = { "x", "radix", 0 };
1690
1691 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O|i:gf", kwlist, &x, &radix))
1692 goto end;
1693 if (GF_PYCHECK(x)) RETURN_OBJ(x);
1694 if (!good_radix_p(radix, 1)) VALERR("radix out of range");
1695 if ((z = mp_frompyobject(x, radix)) == 0) {
1696 PyErr_Format(PyExc_TypeError, "can't convert %.100s to gf",
1697 x->ob_type->tp_name);
1698 goto end;
1699 }
1700 if (MP_NEGP(z)) {
1701 MP_DROP(z);
1702 VALERR("gf cannot be negative");
1703 }
1704 zz = (mp_pyobj *)ty->tp_alloc(ty, 0);
1705 zz->x = z;
1706 end:
1707 return ((PyObject *)zz);
1708 }
1709
1710 static long gf_pyhash(PyObject *me)
1711 {
1712 long i = mp_tolong(MP_X(me));
1713 i ^= 0xc7ecd67c; /* random perturbance */
1714 if (i == -1)
1715 i = -2;
1716 return (i);
1717 }
1718
1719 static PyObject *gf_pyexp(PyObject *x, PyObject *y, PyObject *z)
1720 {
1721 mp *xx = 0, *yy = 0, *zz = 0;
1722 mp *r = 0;
1723 PyObject *rc = 0;
1724
1725 if ((xx = tomp(x)) == 0 || (yy = tomp(y)) == 0 ||
1726 (z && z != Py_None && (zz = tomp(z)) == 0)) {
1727 mp_drop(xx); mp_drop(yy); mp_drop(zz);
1728 RETURN_NOTIMPL;
1729 }
1730 if (!z || z == Py_None) {
1731 if (MP_NEGP(yy)) VALERR("negative exponent");
1732 r = gf_exp(MP_NEW, xx, yy);
1733 } else {
1734 gfreduce gr;
1735 if (MP_ZEROP(zz)) ZDIVERR("zero modulus");
1736 if (MP_NEGP(yy)) {
1737 if ((xx = gf_modinv_checked(xx, xx, zz)) == 0) goto end;
1738 yy = mp_neg(yy, yy);
1739 }
1740 gfreduce_create(&gr, zz);
1741 r = gfreduce_exp(&gr, MP_NEW, xx, yy);
1742 gfreduce_destroy(&gr);
1743 }
1744 rc = gf_pywrap(r);
1745 end:
1746 mp_drop(xx); mp_drop(yy); mp_drop(zz);
1747 return (rc);
1748 }
1749
1750 static PyObject *gfmeth_sqr(PyObject *me, PyObject *arg)
1751 {
1752 if (!PyArg_ParseTuple(arg, ":sqr")) return (0);
1753 return (gf_pywrap(gf_sqr(MP_NEW, MP_X(me))));
1754 }
1755
1756 static PyObject *gfmeth_gcd(PyObject *me, PyObject *arg)
1757 {
1758 PyObject *z = 0;
1759 mp *yy = 0, *zz = MP_NEW;
1760
1761 if (!PyArg_ParseTuple(arg, "O&:gcd", convgf, &yy)) goto end;
1762 gf_gcd(&zz, 0, 0, MP_X(me), yy);
1763 z = gf_pywrap(zz);
1764 end:
1765 if (yy) MP_DROP(yy);
1766 return (z);
1767 }
1768
1769 static PyObject *gfmeth_gcdx(PyObject *me, PyObject *arg)
1770 {
1771 PyObject *z = 0;
1772 mp *yy = 0, *zz = MP_NEW, *uu = MP_NEW, *vv = MP_NEW;
1773
1774 if (!PyArg_ParseTuple(arg, "O&:gcdx", convgf, &yy))
1775 goto end;
1776 gf_gcd(&zz, &uu, &vv, MP_X(me), yy);
1777 z = Py_BuildValue("(NNN)",
1778 gf_pywrap(zz), gf_pywrap(uu), gf_pywrap(vv));
1779 end:
1780 if (yy) MP_DROP(yy);
1781 return (z);
1782 }
1783
1784 static PyObject *gfmeth_modinv(PyObject *me, PyObject *arg)
1785 {
1786 PyObject *z = 0;
1787 mp *yy = 0, *zz = MP_NEW;
1788
1789 if (!PyArg_ParseTuple(arg, "O&:modinv", convgf, &yy) ||
1790 (zz = gf_modinv_checked(MP_NEW, yy, MP_X(me))) == 0)
1791 goto end;
1792 z = gf_pywrap(zz);
1793 end:
1794 if (yy) MP_DROP(yy);
1795 return (z);
1796 }
1797
1798 static PyObject *gfmeth_irreduciblep(PyObject *me, PyObject *arg)
1799 {
1800 if (!PyArg_ParseTuple(arg, ":irreduciblep")) return (0);
1801 return getbool(gf_irreduciblep(MP_X(me)));
1802 }
1803
1804 static PyObject *gfget_degree(PyObject *me, void *hunoz)
1805 { return (PyInt_FromLong(mp_bits(MP_X(me)) - 1)); }
1806
1807 static PyGetSetDef gf_pygetset[] = {
1808 #define GETSETNAME(op, name) gf##op##_##name
1809 GET (degree, "X.degree -> polynomial degree of X")
1810 #undef GETSETNAME
1811 #define GETSETNAME(op, name) mp##op##_##name
1812 GET (nbits, "X.nbits -> bit length of X")
1813 GET (noctets, "X.noctets -> octet length of X")
1814 #undef GETSETNAME
1815 { 0 }
1816 };
1817
1818 static PyMethodDef gf_pymethods[] = {
1819 #define METHNAME(func) gfmeth_##func
1820 METH (setbit, "X.setbit(N) -> X with bit N set")
1821 METH (clearbit, "X.clearbit(N) -> X with bit N clear")
1822 METH (testbit, "X.testbit(N) -> true/false if bit N set/clear in X")
1823 METH (sqr, "X.sqr() -> X^2")
1824 METH (gcd, "X.gcd(Y) -> gcd(X, Y)")
1825 METH (gcdx,
1826 "X.gcdx(Y) -> (gcd(X, Y), U, V) with X U + Y V = gcd(X, Y)")
1827 METH (modinv, "X.modinv(Y) -> multiplicative inverse of Y mod X")
1828 METH (irreduciblep, "X.irreduciblep() -> true/false")
1829 #undef METHNAME
1830 #define METHNAME(func) mpmeth_##func
1831 KWMETH(tostring, "X.tostring(radix = 10) -> STR")
1832 KWMETH(storel, "X.storel(len = -1) -> little-endian bytes")
1833 KWMETH(storeb, "X.storeb(len = -1) -> big-endian bytes")
1834 KWMETH(storel2c,
1835 "X.storel2c(len = -1) -> little-endian bytes, two's complement")
1836 KWMETH(storeb2c,
1837 "X.storeb2c(len = -1) -> big-endian bytes, two's complement")
1838 METH (tobuf, "X.tobuf() -> buffer format")
1839 #undef METHNAME
1840 { 0 }
1841 };
1842
1843 static PyNumberMethods gf_pynumber = {
1844 gf_pyadd, /* @nb_add@ */
1845 gf_pysub, /* @nb_subtract@ */
1846 gf_pymul, /* @nb_multiply@ */
1847 0, /* @nb_divide@ */
1848 gf_pymod, /* @nb_remainder@ */
1849 gf_pydivmod, /* @nb_divmod@ */
1850 gf_pyexp, /* @nb_power@ */
1851 mp_pyid, /* @nb_negative@ */
1852 mp_pyid, /* @nb_positive@ */
1853 mp_pyid, /* @nb_absolute@ */
1854 mp_pynonzerop, /* @nb_nonzero@ */
1855 0 /* doesn't make any sense */, /* @nb_invert@ */
1856 gf_pylsl, /* @nb_lshift@ */
1857 gf_pylsr, /* @nb_rshift@ */
1858 gf_pyand, /* @nb_and@ */
1859 gf_pyxor, /* @nb_xor@ */
1860 gf_pyor, /* @nb_or@ */
1861 gf_pycoerce, /* @nb_coerce@ */
1862 mp_pyint, /* @nb_int@ */
1863 mp_pylong, /* @nb_long@ */
1864 0 /* doesn't make any sense */, /* @nb_float@ */
1865 mp_pyoct, /* @nb_oct@ */
1866 mp_pyhex, /* @nb_hex@ */
1867
1868 0, /* @nb_inplace_add@ */
1869 0, /* @nb_inplace_subtract@ */
1870 0, /* @nb_inplace_multiply@ */
1871 0, /* @nb_inplace_divide@ */
1872 0, /* @nb_inplace_remainder@ */
1873 0, /* @nb_inplace_power@ */
1874 0, /* @nb_inplace_lshift@ */
1875 0, /* @nb_inplace_rshift@ */
1876 0, /* @nb_inplace_and@ */
1877 0, /* @nb_inplace_xor@ */
1878 0, /* @nb_inplace_or@ */
1879
1880 gf_pydiv, /* @nb_floor_divide@ */
1881 0, /* @nb_true_divide@ */
1882 0, /* @nb_inplace_floor_divide@ */
1883 0, /* @nb_inplace_true_divide@ */
1884 };
1885
1886 static PyTypeObject gf_pytype_skel = {
1887 PyObject_HEAD_INIT(0) 0, /* Header */
1888 "catacomb.GF", /* @tp_name@ */
1889 sizeof(mp_pyobj), /* @tp_basicsize@ */
1890 0, /* @tp_itemsize@ */
1891
1892 mp_pydealloc, /* @tp_dealloc@ */
1893 0, /* @tp_print@ */
1894 0, /* @tp_getattr@ */
1895 0, /* @tp_setattr@ */
1896 0, /* @tp_compare@ */
1897 gf_pyrepr, /* @tp_repr@ */
1898 &gf_pynumber, /* @tp_as_number@ */
1899 0, /* @tp_as_sequence@ */
1900 0, /* @tp_as_mapping@ */
1901 gf_pyhash, /* @tp_hash@ */
1902 0, /* @tp_call@ */
1903 mp_pyhex, /* @tp_str@ */
1904 0, /* @tp_getattro@ */
1905 0, /* @tp_setattro@ */
1906 0, /* @tp_as_buffer@ */
1907 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
1908 Py_TPFLAGS_CHECKTYPES |
1909 Py_TPFLAGS_BASETYPE,
1910
1911 /* @tp_doc@ */
1912 "Binary polynomials. Support almost all the standard arithmetic\n\
1913 operations.\n\
1914 \n\
1915 Constructor gf(X, radix = R) attempts to convert X to a `gf'. If\n\
1916 X is a string, it's read in radix-R form, or we look for a prefix\n\
1917 if R = 0. Other acceptable things are ints and longs.\n\
1918 \n\
1919 The name is hopelessly wrong from a technical point of view, but\n\
1920 but it's much easier to type than `p2' or `c2' or whatever.\n\
1921 \n\
1922 Notes:\n\
1923 \n\
1924 * Use `//' for division. GFs don't have `/' division.",
1925
1926 0, /* @tp_traverse@ */
1927 0, /* @tp_clear@ */
1928 gf_pyrichcompare, /* @tp_richcompare@ */
1929 0, /* @tp_weaklistoffset@ */
1930 0, /* @tp_iter@ */
1931 0, /* @tp_iternext@ */
1932 gf_pymethods, /* @tp_methods@ */
1933 0, /* @tp_members@ */
1934 gf_pygetset, /* @tp_getset@ */
1935 0, /* @tp_base@ */
1936 0, /* @tp_dict@ */
1937 0, /* @tp_descr_get@ */
1938 0, /* @tp_descr_set@ */
1939 0, /* @tp_dictoffset@ */
1940 0, /* @tp_init@ */
1941 PyType_GenericAlloc, /* @tp_alloc@ */
1942 gf_pynew, /* @tp_new@ */
1943 0, /* @tp_free@ */
1944 0 /* @tp_is_gc@ */
1945 };
1946
1947 static PyObject *meth__GF_fromstring(PyObject *me,
1948 PyObject *arg, PyObject *kw)
1949 {
1950 int r = 0;
1951 char *p;
1952 int len;
1953 PyObject *z = 0;
1954 mp *zz;
1955 mptext_stringctx sc;
1956 char *kwlist[] = { "class", "x", "radix", 0 };
1957
1958 if (!PyArg_ParseTupleAndKeywords(arg, kw, "Os#|i:fromstring",
1959 kwlist, &me, &p, &len, &r))
1960 goto end;
1961 if (!good_radix_p(r, 1)) VALERR("radix out of range");
1962 sc.buf = p; sc.lim = p + len;
1963 if ((zz = mp_read(MP_NEW, r, &mptext_stringops, &sc)) == 0 || MP_NEGP(zz))
1964 z = Py_BuildValue("(Os#)", Py_None, p, len);
1965 else
1966 z = Py_BuildValue("(Ns#)", gf_pywrap(zz),
1967 sc.buf, (int)(sc.lim - sc.buf));
1968 end:
1969 return (z);
1970 }
1971
1972 /*----- Sparse poly reduction ---------------------------------------------*/
1973
1974 typedef struct gfreduce_pyobj {
1975 PyObject_HEAD
1976 gfreduce mr;
1977 } gfreduce_pyobj;
1978
1979 #define GFREDUCE_PY(o) (&((gfreduce_pyobj *)(o))->mr)
1980
1981 static PyObject *grmeth_exp(PyObject *me, PyObject *arg)
1982 {
1983 PyObject *rc = 0;
1984 mp *yy = 0, *zz = 0;
1985
1986 if (!PyArg_ParseTuple(arg, "O&O&:exp", convgf, &yy, convgf, &zz))
1987 goto end;
1988 if (MP_NEGP(zz)) {
1989 if ((yy = gf_modinv_checked(yy, yy, GFREDUCE_PY(me)->p)) == 0) goto end;
1990 zz = mp_neg(zz, zz);
1991 }
1992 rc = gf_pywrap(gfreduce_exp(GFREDUCE_PY(me), MP_NEW, yy, zz));
1993 end:
1994 if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
1995 return (rc);
1996 }
1997
1998 static PyObject *grmeth_reduce(PyObject *me, PyObject *arg)
1999 {
2000 PyObject *z = 0;
2001 mp *yy = 0;
2002
2003 if (!PyArg_ParseTuple(arg, "O&:reduce", convgf, &yy)) goto end;
2004 z = gf_pywrap(gfreduce_do(GFREDUCE_PY(me), MP_NEW, yy));
2005 end:
2006 return (z);
2007 }
2008
2009 static void gfreduce_pydealloc(PyObject *me)
2010 {
2011 gfreduce_destroy(GFREDUCE_PY(me));
2012 FREEOBJ(me);
2013 }
2014
2015 static PyObject *gfreduce_pynew(PyTypeObject *ty,
2016 PyObject *arg, PyObject *kw)
2017 {
2018 gfreduce_pyobj *mr = 0;
2019 gfreduce r;
2020 char *kwlist[] = { "m", 0 };
2021 mp *xx = 0;
2022
2023 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convgf, &xx))
2024 goto end;
2025 if (MP_ZEROP(xx)) ZDIVERR("modulus is zero!");
2026 gfreduce_create(&r, xx);
2027 mr = (gfreduce_pyobj *)ty->tp_alloc(ty, 0);
2028 mr->mr = r;
2029 end:
2030 if (xx) MP_DROP(xx);
2031 return ((PyObject *)mr);
2032 }
2033
2034 static PyObject *grget_m(PyObject *me, void *hunoz)
2035 { return (gf_pywrap(MP_COPY(GFREDUCE_PY(me)->p))); }
2036
2037 static PyGetSetDef gfreduce_pygetset[] = {
2038 #define GETSETNAME(op, name) gr##op##_##name
2039 GET (m, "R.m -> reduction polynomial")
2040 #undef GETSETNAME
2041 { 0 }
2042 };
2043
2044 static PyMethodDef gfreduce_pymethods[] = {
2045 #define METHNAME(name) grmeth_##name
2046 METH (reduce, "R.reduce(X) -> X mod B.m")
2047 METH (exp, "R.exp(X, N) -> X^N mod B.m")
2048 #undef METHNAME
2049 { 0 }
2050 };
2051
2052 static PyTypeObject *gfreduce_pytype, gfreduce_pytype_skel = {
2053 PyObject_HEAD_INIT(0) 0, /* Header */
2054 "catacomb.GFReduce", /* @tp_name@ */
2055 sizeof(gfreduce_pyobj), /* @tp_basicsize@ */
2056 0, /* @tp_itemsize@ */
2057
2058 gfreduce_pydealloc, /* @tp_dealloc@ */
2059 0, /* @tp_print@ */
2060 0, /* @tp_getattr@ */
2061 0, /* @tp_setattr@ */
2062 0, /* @tp_compare@ */
2063 0, /* @tp_repr@ */
2064 0, /* @tp_as_number@ */
2065 0, /* @tp_as_sequence@ */
2066 0, /* @tp_as_mapping@ */
2067 0, /* @tp_hash@ */
2068 0, /* @tp_call@ */
2069 0, /* @tp_str@ */
2070 0, /* @tp_getattro@ */
2071 0, /* @tp_setattro@ */
2072 0, /* @tp_as_buffer@ */
2073 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
2074 Py_TPFLAGS_BASETYPE,
2075
2076 /* @tp_doc@ */
2077 "A reduction context for reduction modulo sparse irreducible polynomials.",
2078
2079 0, /* @tp_traverse@ */
2080 0, /* @tp_clear@ */
2081 0, /* @tp_richcompare@ */
2082 0, /* @tp_weaklistoffset@ */
2083 0, /* @tp_iter@ */
2084 0, /* @tp_iternext@ */
2085 gfreduce_pymethods, /* @tp_methods@ */
2086 0, /* @tp_members@ */
2087 gfreduce_pygetset, /* @tp_getset@ */
2088 0, /* @tp_base@ */
2089 0, /* @tp_dict@ */
2090 0, /* @tp_descr_get@ */
2091 0, /* @tp_descr_set@ */
2092 0, /* @tp_dictoffset@ */
2093 0, /* @tp_init@ */
2094 PyType_GenericAlloc, /* @tp_alloc@ */
2095 gfreduce_pynew, /* @tp_new@ */
2096 0, /* @tp_free@ */
2097 0 /* @tp_is_gc@ */
2098 };
2099
2100 /*----- Normal/poly transformation ----------------------------------------*/
2101
2102 typedef struct gfn_pyobj {
2103 PyObject_HEAD
2104 mp *p;
2105 gfn ntop, pton;
2106 } gfn_pyobj;
2107
2108 static PyTypeObject *gfn_pytype, gfn_pytype_skel;
2109
2110 #define GFN_P(o) (((gfn_pyobj *)(o))->p)
2111 #define GFN_PTON(o) (&((gfn_pyobj *)(o))->pton)
2112 #define GFN_NTOP(o) (&((gfn_pyobj *)(o))->ntop)
2113
2114 static PyObject *gfn_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
2115 {
2116 mp *p = 0, *beta = 0;
2117 gfn_pyobj *gg = 0;
2118 char *kwlist[] = { "p", "beta", 0 };
2119
2120 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&O&:new", kwlist,
2121 convgf, &p, convgf, &beta))
2122 goto end;
2123 gg = PyObject_New(gfn_pyobj, ty);
2124 if (gfn_create(p, beta, &gg->ntop, &gg->pton)) {
2125 FREEOBJ(gg);
2126 gg = 0;
2127 VALERR("can't invert transformation matrix");
2128 }
2129 gg->p = MP_COPY(p);
2130 end:
2131 mp_drop(p);
2132 mp_drop(beta);
2133 return ((PyObject *)gg);
2134 }
2135
2136 static PyObject *gfnget_p(PyObject *me, void *hunoz)
2137 { return (gf_pywrap(MP_COPY(GFN_P(me)))); }
2138
2139 static PyObject *gfnget_beta(PyObject *me, void *hunoz)
2140 {
2141 gfn *n = GFN_NTOP(me);
2142 mp *x = n->r[n->n - 1];
2143 return (gf_pywrap(MP_COPY(x)));
2144 }
2145
2146 #define XFORMOP(name, NAME) \
2147 static PyObject *gfnmeth_##name(PyObject *me, PyObject *arg) \
2148 { \
2149 mp *xx = 0; \
2150 mp *z = 0; \
2151 \
2152 if (!PyArg_ParseTuple(arg, "O&:" #name, convgf, &xx)) goto end; \
2153 z = gfn_transform(GFN_##NAME(me), MP_NEW, xx); \
2154 end: \
2155 mp_drop(xx); \
2156 if (!z) return (0); \
2157 return (mp_pywrap(z)); \
2158 }
2159 XFORMOP(pton, PTON)
2160 XFORMOP(ntop, NTOP)
2161 #undef XFORMOP
2162
2163 static void gfn_pydealloc(PyObject *me)
2164 {
2165 gfn_destroy(GFN_PTON(me));
2166 gfn_destroy(GFN_NTOP(me));
2167 FREEOBJ(me);
2168 }
2169
2170 static PyGetSetDef gfn_pygetset[] = {
2171 #define GETSETNAME(op, name) gfn##op##_##name
2172 GET (p, "X.p -> polynomial basis, as polynomial")
2173 GET (beta, "X.beta -> normal basis element, in poly form")
2174 #undef GETSETNAME
2175 { 0 }
2176 };
2177
2178 static PyMethodDef gfn_pymethods[] = {
2179 #define METHNAME(name) gfnmeth_##name
2180 METH (pton, "X.pton(A) -> normal-basis representation of A")
2181 METH (ntop, "X.ntop(A) -> polynomial-basis representation of A")
2182 #undef METHNAME
2183 { 0 }
2184 };
2185
2186 static PyTypeObject gfn_pytype_skel = {
2187 PyObject_HEAD_INIT(0) 0, /* Header */
2188 "catacomb.GFN", /* @tp_name@ */
2189 sizeof(gfn_pyobj), /* @tp_basicsize@ */
2190 0, /* @tp_itemsize@ */
2191
2192 gfn_pydealloc, /* @tp_dealloc@ */
2193 0, /* @tp_print@ */
2194 0, /* @tp_getattr@ */
2195 0, /* @tp_setattr@ */
2196 0, /* @tp_compare@ */
2197 0, /* @tp_repr@ */
2198 0, /* @tp_as_number@ */
2199 0, /* @tp_as_sequence@ */
2200 0, /* @tp_as_mapping@ */
2201 0, /* @tp_hash@ */
2202 0, /* @tp_call@ */
2203 0, /* @tp_str@ */
2204 0, /* @tp_getattro@ */
2205 0, /* @tp_setattro@ */
2206 0, /* @tp_as_buffer@ */
2207 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
2208 Py_TPFLAGS_BASETYPE,
2209
2210 /* @tp_doc@ */
2211 "An object for transforming elements of binary fields between polynomial\n\
2212 and normal basis representations.",
2213
2214 0, /* @tp_traverse@ */
2215 0, /* @tp_clear@ */
2216 0, /* @tp_richcompare@ */
2217 0, /* @tp_weaklistoffset@ */
2218 0, /* @tp_iter@ */
2219 0, /* @tp_iternext@ */
2220 gfn_pymethods, /* @tp_methods@ */
2221 0, /* @tp_members@ */
2222 gfn_pygetset, /* @tp_getset@ */
2223 0, /* @tp_base@ */
2224 0, /* @tp_dict@ */
2225 0, /* @tp_descr_get@ */
2226 0, /* @tp_descr_set@ */
2227 0, /* @tp_dictoffset@ */
2228 0, /* @tp_init@ */
2229 PyType_GenericAlloc, /* @tp_alloc@ */
2230 gfn_pynew, /* @tp_new@ */
2231 0, /* @tp_free@ */
2232 0 /* @tp_is_gc@ */
2233 };
2234
2235 /*----- Glue --------------------------------------------------------------*/
2236
2237 static PyMethodDef methods[] = {
2238 #define METHNAME(func) meth_##func
2239 KWMETH(_MP_fromstring, "\
2240 fromstring(STR, radix = 0) -> (X, REST)\n\
2241 \n\
2242 Parse STR as a large integer, according to radix. If radix is zero,\n\
2243 read a prefix from STR to decide radix: allow `0' for octal, `0x' for hex\n\
2244 or `R_' for other radix R.")
2245 KWMETH(_GF_fromstring, "\
2246 fromstring(STR, radix = 0) -> (X, REST)\n\
2247 \n\
2248 Parse STR as a binary polynomial, according to radix. If radix is zero,\n\
2249 read a prefix from STR to decide radix: allow `0' for octal, `0x' for hex\n\
2250 or `R_' for other radix R.")
2251 METH (_MP_loadl, "\
2252 loadl(STR) -> X: read little-endian bytes")
2253 METH (_MP_loadb, "\
2254 loadb(STR) -> X: read big-endian bytes")
2255 METH (_MP_loadl2c, "\
2256 loadl2c(STR) -> X: read little-endian bytes, two's complement")
2257 METH (_MP_loadb2c, "\
2258 loadb2c(STR) -> X: read big-endian bytes, two's complement")
2259 METH (_MP_frombuf, "\
2260 frombuf(STR) -> (X, REST): read buffer format")
2261 METH (_MP_product, "\
2262 product(ITER) -> X: product of things iterated over")
2263 METH (_GF_loadl, "\
2264 loadl(STR) -> X: read little-endian bytes")
2265 METH (_GF_loadb, "\
2266 loadb(STR) -> X: read big-endian bytes")
2267 METH (_GF_frombuf, "\
2268 frombuf(STR) -> (X, REST): read buffer format")
2269 #undef METHNAME
2270 { 0 }
2271 };
2272
2273 void mp_pyinit(void)
2274 {
2275 INITTYPE(mp, root);
2276 INITTYPE(gf, root);
2277 INITTYPE(mpmont, root);
2278 INITTYPE(mpbarrett, root);
2279 INITTYPE(mpreduce, root);
2280 INITTYPE(mpcrt, root);
2281 INITTYPE(gfreduce, root);
2282 INITTYPE(gfn, root);
2283 addmethods(methods);
2284 }
2285
2286 void mp_pyinsert(PyObject *mod)
2287 {
2288 INSERT("MP", mp_pytype);
2289 INSERT("MPMont", mpmont_pytype);
2290 INSERT("MPBarrett", mpbarrett_pytype);
2291 INSERT("MPReduce", mpreduce_pytype);
2292 INSERT("MPCRT", mpcrt_pytype);
2293 INSERT("GF", gf_pytype);
2294 INSERT("GFReduce", gfreduce_pytype);
2295 INSERT("GFN", gfn_pytype);
2296 }
2297
2298 /*----- That's all, folks -------------------------------------------------*/
Catacomb cryptographic library -- Python bindings