~mdw / catacomb-python / blob
? search:


f31691e7567b6ab15fdfff981808f9ca809e8949
[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 unsigned long i; \
539 if (!PyArg_ParseTuple(arg, "O&:" #name, convulong, &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 unsigned long i;
551 if (!PyArg_ParseTuple(arg, "O&:testbit", convulong, &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 unsigned long i;
558 if (!PyArg_ParseTuple(arg, "O&:testbit", convulong, &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 #define LOADOP(pre, py, name) \
902 static PyObject *meth__##py##_##name(PyObject *me, PyObject *arg) \
903 { \
904 char *p; \
905 int len; \
906 if (!PyArg_ParseTuple(arg, "Os#:" #name, &me, &p, &len)) return (0); \
907 return (pre##_pywrap(mp_##name(MP_NEW, p, len))); \
908 }
909 LOADOP(mp, MP, loadl)
910 LOADOP(mp, MP, loadb)
911 LOADOP(mp, MP, loadl2c)
912 LOADOP(mp, MP, loadb2c)
913 LOADOP(gf, GF, loadl)
914 LOADOP(gf, GF, loadb)
915 #undef LOADOP
916
917 /*----- Products of small integers ----------------------------------------*/
918
919 typedef struct mpmul_pyobj {
920 PyObject_HEAD
921 int livep;
922 mpmul mm;
923 } mpmul_pyobj;
924
925 #define MPMUL_LIVEP(o) (((mpmul_pyobj *)(o))->livep)
926 #define MPMUL_PY(o) (&((mpmul_pyobj *)(o))->mm)
927
928 static void mpmul_pydealloc(PyObject *me)
929 {
930 if (MPMUL_LIVEP(me))
931 mp_drop(mpmul_done(MPMUL_PY(me)));
932 FREEOBJ(me);
933 }
934
935 static PyObject *mmmeth_factor(PyObject *me, PyObject *arg)
936 {
937 PyObject *q, *i;
938 mp *x;
939
940 if (!MPMUL_LIVEP(me)) VALERR("MPMul object invalid");
941 if (PyTuple_Size(arg) != 1)
942 i = PyObject_GetIter(arg);
943 else {
944 if ((q = PyTuple_GetItem(arg, 0)) == 0) goto end;
945 if ((i = PyObject_GetIter(q)) == 0) {
946 PyErr_Clear(); /* that's ok */
947 i = PyObject_GetIter(arg);
948 }
949 }
950 if (!i) goto end;
951 while ((q = PyIter_Next(i)) != 0) {
952 x = getmp(q); Py_DECREF(q); if (!x) {
953 Py_DECREF(i);
954 goto end;
955 }
956 mpmul_add(MPMUL_PY(me), x);
957 MP_DROP(x);
958 }
959 Py_DECREF(i);
960 RETURN_ME;
961 end:
962 return (0);
963 }
964
965 static PyObject *mmmeth_done(PyObject *me, PyObject *arg)
966 {
967 mp *x;
968
969 if (!PyArg_ParseTuple(arg, ":done")) goto end;
970 if (!MPMUL_LIVEP(me)) VALERR("MPMul object invalid");
971 x = mpmul_done(MPMUL_PY(me));
972 MPMUL_LIVEP(me) = 0;
973 return (mp_pywrap(x));
974 end:
975 return (0);
976 }
977
978 static PyObject *mpmul_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
979 {
980 mpmul_pyobj *mm;
981
982 if (kw) TYERR("keyword arguments not allowed here");
983 mm = (mpmul_pyobj *)ty->tp_alloc(ty, 0);
984 mpmul_init(&mm->mm);
985 mm->livep = 1;
986 if (mmmeth_factor((PyObject *)mm, arg) == 0) {
987 Py_DECREF(mm);
988 goto end;
989 }
990 return ((PyObject *)mm);
991 end:
992 return (0);
993 }
994
995 static PyObject *mmget_livep(PyObject *me, void *hunoz)
996 { return (getbool(MPMUL_LIVEP(me))); }
997
998 static PyGetSetDef mpmul_pygetset[] = {
999 #define GETSETNAME(op, name) mm##op##_##name
1000 GET (livep, "MM.livep -> flag: object still valid?")
1001 #undef GETSETNAME
1002 { 0 }
1003 };
1004
1005 static PyMethodDef mpmul_pymethods[] = {
1006 #define METHNAME(name) mmmeth_##name
1007 METH (factor, "MM.factor(ITERABLE) or MM.factor(I, ...)")
1008 METH (done, "MM.done() -> PRODUCT")
1009 #undef METHNAME
1010 { 0 }
1011 };
1012
1013 static PyTypeObject *mpmul_pytype, mpmul_pytype_skel = {
1014 PyObject_HEAD_INIT(0) 0, /* Header */
1015 "catacomb.MPMul", /* @tp_name@ */
1016 sizeof(mpmul_pyobj), /* @tp_basicsize@ */
1017 0, /* @tp_itemsize@ */
1018
1019 mpmul_pydealloc, /* @tp_dealloc@ */
1020 0, /* @tp_print@ */
1021 0, /* @tp_getattr@ */
1022 0, /* @tp_setattr@ */
1023 0, /* @tp_compare@ */
1024 0, /* @tp_repr@ */
1025 0, /* @tp_as_number@ */
1026 0, /* @tp_as_sequence@ */
1027 0, /* @tp_as_mapping@ */
1028 0, /* @tp_hash@ */
1029 0, /* @tp_call@ */
1030 0, /* @tp_str@ */
1031 0, /* @tp_getattro@ */
1032 0, /* @tp_setattro@ */
1033 0, /* @tp_as_buffer@ */
1034 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
1035 Py_TPFLAGS_BASETYPE,
1036
1037 /* @tp_doc@ */
1038 "An object for multiplying many small integers.",
1039
1040 0, /* @tp_traverse@ */
1041 0, /* @tp_clear@ */
1042 0, /* @tp_richcompare@ */
1043 0, /* @tp_weaklistoffset@ */
1044 0, /* @tp_iter@ */
1045 0, /* @tp_iternext@ */
1046 mpmul_pymethods, /* @tp_methods@ */
1047 0, /* @tp_members@ */
1048 mpmul_pygetset, /* @tp_getset@ */
1049 0, /* @tp_base@ */
1050 0, /* @tp_dict@ */
1051 0, /* @tp_descr_get@ */
1052 0, /* @tp_descr_set@ */
1053 0, /* @tp_dictoffset@ */
1054 0, /* @tp_init@ */
1055 PyType_GenericAlloc, /* @tp_alloc@ */
1056 mpmul_pynew, /* @tp_new@ */
1057 0, /* @tp_free@ */
1058 0 /* @tp_is_gc@ */
1059 };
1060
1061 /*----- Montgomery reduction ----------------------------------------------*/
1062
1063 typedef struct mpmont_pyobj {
1064 PyObject_HEAD
1065 mpmont mm;
1066 } mpmont_pyobj;
1067
1068 #define MPMONT_PY(o) (&((mpmont_pyobj *)(o))->mm)
1069
1070 static PyObject *mmmeth_int(PyObject *me, PyObject *arg)
1071 {
1072 PyObject *z = 0;
1073 mp *yy = 0;
1074 mpmont *mm = MPMONT_PY(me);
1075
1076 if (!PyArg_ParseTuple(arg, "O&:in", convmp, &yy))
1077 goto end;
1078 mp_div(0, &yy, yy, mm->m);
1079 z = mp_pywrap(mpmont_mul(mm, MP_NEW, yy, mm->r2));
1080 end:
1081 if (yy) MP_DROP(yy);
1082 return (z);
1083 }
1084
1085 static PyObject *mmmeth_mul(PyObject *me, PyObject *arg)
1086 {
1087 PyObject *rc = 0;
1088 mp *yy = 0, *zz = 0;
1089
1090 if (!PyArg_ParseTuple(arg, "O&O&:mul", convmp, &yy, convmp, &zz))
1091 goto end;
1092 rc = mp_pywrap(mpmont_mul(MPMONT_PY(me), MP_NEW, yy, zz));
1093 end:
1094 if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
1095 return (rc);
1096 }
1097
1098 static PyObject *mmmeth_exp(PyObject *me, PyObject *arg)
1099 {
1100 PyObject *rc = 0;
1101 mp *yy = 0, *zz = 0;
1102
1103 if (!PyArg_ParseTuple(arg, "O&O&:exp", convmp, &yy, convmp, &zz))
1104 goto end;
1105 if (MP_NEGP(zz)) {
1106 if ((yy = mp_modinv_checked(yy, yy, MPMONT_PY(me)->m)) == 0) goto end;
1107 zz = mp_neg(zz, zz);
1108 }
1109 rc = mp_pywrap(mpmont_exp(MPMONT_PY(me), MP_NEW, yy, zz));
1110 end:
1111 if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
1112 return (rc);
1113 }
1114
1115 static PyObject *mmmeth_expr(PyObject *me, PyObject *arg)
1116 {
1117 PyObject *rc = 0;
1118 mp *yy = 0, *zz = 0;
1119
1120 if (!PyArg_ParseTuple(arg, "O&O&:expr", convmp, &yy, convmp, &zz))
1121 goto end;
1122 if (MP_NEGP(zz)) {
1123 yy = mpmont_reduce(MPMONT_PY(me), yy, yy);
1124 if ((yy = mp_modinv_checked(yy, yy, MPMONT_PY(me)->m)) == 0) goto end;
1125 yy = mpmont_mul(MPMONT_PY(me), yy, yy, MPMONT_PY(me)->r2);
1126 zz = mp_neg(zz, zz);
1127 }
1128 rc = mp_pywrap(mpmont_expr(MPMONT_PY(me), MP_NEW, yy, zz));
1129 end:
1130 if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
1131 return (rc);
1132 }
1133
1134 static PyObject *mm_mexpr_id(PyObject *me)
1135 { return mp_pywrap(MP_COPY(MPMONT_PY(me)->r)); }
1136
1137 static int mm_mexpr_fill(void *p, PyObject *me, PyObject *x, PyObject *y)
1138 {
1139 mp *xx = 0, *yy = 0;
1140 mp_expfactor *f = p;
1141 mpmont *mm = MPMONT_PY(me);
1142
1143 if ((xx = getmp(x)) == 0 || (yy = getmp(y)) == 0)
1144 goto fail;
1145 if (MP_NEGP(yy)) {
1146 xx = mpmont_reduce(mm, xx, xx);
1147 if ((xx = mp_modinv_checked(xx, xx, yy)) == 0)
1148 goto fail;
1149 xx = mpmont_mul(mm, xx, xx, mm->r2);
1150 yy = mp_neg(yy, yy);
1151 }
1152 f->base = xx;
1153 f->exp = yy;
1154 return (0);
1155
1156 fail:
1157 mp_drop(xx); mp_drop(yy);
1158 return (-1);
1159 }
1160
1161 static PyObject *mm_mexpr(PyObject *me, void *v, int n)
1162 { return mp_pywrap(mpmont_mexpr(MPMONT_PY(me), MP_NEW, v, n)); }
1163
1164 static void mp_mexp_drop(void *p)
1165 {
1166 mp_expfactor *f = p;
1167 mp_drop(f->base);
1168 mp_drop(f->exp);
1169 }
1170
1171 static PyObject *mmmeth_mexpr(PyObject *me, PyObject *arg)
1172 {
1173 return mexp_common(me, arg, sizeof(mp_expfactor),
1174 mm_mexpr_id, mm_mexpr_fill, mm_mexpr, mp_mexp_drop);
1175 }
1176
1177 static PyObject *mp_mexp_id(PyObject *me)
1178 { return mp_pywrap(MP_ONE); }
1179
1180 static int mp_mexp_fill(void *p, PyObject *me, PyObject *x, PyObject *y)
1181 {
1182 mp *xx = 0, *yy = 0;
1183 mp_expfactor *f = p;
1184
1185 if ((xx = getmp(x)) == 0 || (yy = getmp(y)) == 0)
1186 goto fail;
1187 if (MP_NEGP(yy)) {
1188 if ((xx = mp_modinv_checked(xx, xx, yy)) == 0)
1189 goto fail;
1190 yy = mp_neg(yy, yy);
1191 }
1192 f->base = xx;
1193 f->exp = yy;
1194 return (0);
1195
1196 fail:
1197 mp_drop(xx); mp_drop(yy);
1198 return (-1);
1199 }
1200
1201 static PyObject *mm_mexp(PyObject *me, void *v, int n)
1202 { return mp_pywrap(mpmont_mexp(MPMONT_PY(me), MP_NEW, v, n)); }
1203
1204 static PyObject *mmmeth_mexp(PyObject *me, PyObject *arg)
1205 {
1206 return mexp_common(me, arg, sizeof(mp_expfactor),
1207 mp_mexp_id, mp_mexp_fill, mm_mexp, mp_mexp_drop);
1208 }
1209
1210 #define mmmeth_ext mmmeth_reduce
1211 static PyObject *mmmeth_reduce(PyObject *me, PyObject *arg)
1212 {
1213 PyObject *z = 0;
1214 mp *yy = 0;
1215
1216 if (!PyArg_ParseTuple(arg, "O&", convmp, &yy)) goto end;
1217 z = mp_pywrap(mpmont_reduce(MPMONT_PY(me), MP_NEW, yy));
1218 end:
1219 return (z);
1220 }
1221
1222 static void mpmont_pydealloc(PyObject *me)
1223 {
1224 mpmont_destroy(MPMONT_PY(me));
1225 FREEOBJ(me);
1226 }
1227
1228 static PyObject *mpmont_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
1229 {
1230 mpmont_pyobj *mm = 0;
1231 char *kwlist[] = { "m", 0 };
1232 mp *xx = 0;
1233
1234 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convmp, &xx))
1235 goto end;
1236 if (!MP_POSP(xx) || !MP_ODDP(xx)) VALERR("m must be positive and odd");
1237 mm = (mpmont_pyobj *)ty->tp_alloc(ty, 0);
1238 mpmont_create(&mm->mm, xx);
1239 end:
1240 if (xx) MP_DROP(xx);
1241 return ((PyObject *)mm);
1242 }
1243
1244 static PyObject *mmget_m(PyObject *me, void *hunoz)
1245 { return (mp_pywrap(MP_COPY(MPMONT_PY(me)->m))); }
1246
1247 static PyObject *mmget_r(PyObject *me, void *hunoz)
1248 { return (mp_pywrap(MP_COPY(MPMONT_PY(me)->r))); }
1249
1250 static PyObject *mmget_r2(PyObject *me, void *hunoz)
1251 { return (mp_pywrap(MP_COPY(MPMONT_PY(me)->r2))); }
1252
1253 static PyGetSetDef mpmont_pygetset[] = {
1254 #define GETSETNAME(op, name) mm##op##_##name
1255 GET (m, "M.m -> modulus for reduction")
1256 GET (r, "M.r -> multiplicative identity")
1257 GET (r2, "M.r2 -> M.r^2, Montgomerization factor")
1258 #undef GETSETNAME
1259 { 0 }
1260 };
1261
1262 static PyMethodDef mpmont_pymethods[] = {
1263 #define METHNAME(name) mmmeth_##name
1264 METH (int, "M.out(X) -> XR")
1265 METH (mul, "M.mul(XR, YR) -> ZR where Z = X Y")
1266 METH (expr, "M.expr(XR, N) -> ZR where Z = X^N mod M.m")
1267 METH (mexpr, "\
1268 B.mexp([(XR0, N0), (XR1, N1), ...]) = ZR where Z = X0^N0 X1^N1 mod B.m\n\
1269 \t(the list may be flattened if this more convenient.)")
1270 METH (reduce, "M.reduce(XR) -> X")
1271 METH (ext, "M.ext(XR) -> X")
1272 METH (exp, "M.exp(X, N) -> X^N mod M.m")
1273 METH (mexp, "\
1274 B.mexp([(X0, N0), (X1, N1), ...]) = X0^N0 X1^N1 mod B.m\n\
1275 \t(the list may be flattened if this more convenient.)")
1276 #undef METHNAME
1277 { 0 }
1278 };
1279
1280 static PyTypeObject *mpmont_pytype, mpmont_pytype_skel = {
1281 PyObject_HEAD_INIT(0) 0, /* Header */
1282 "catacomb.MPMont", /* @tp_name@ */
1283 sizeof(mpmont_pyobj), /* @tp_basicsize@ */
1284 0, /* @tp_itemsize@ */
1285
1286 mpmont_pydealloc, /* @tp_dealloc@ */
1287 0, /* @tp_print@ */
1288 0, /* @tp_getattr@ */
1289 0, /* @tp_setattr@ */
1290 0, /* @tp_compare@ */
1291 0, /* @tp_repr@ */
1292 0, /* @tp_as_number@ */
1293 0, /* @tp_as_sequence@ */
1294 0, /* @tp_as_mapping@ */
1295 0, /* @tp_hash@ */
1296 0, /* @tp_call@ */
1297 0, /* @tp_str@ */
1298 0, /* @tp_getattro@ */
1299 0, /* @tp_setattro@ */
1300 0, /* @tp_as_buffer@ */
1301 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
1302 Py_TPFLAGS_BASETYPE,
1303
1304 /* @tp_doc@ */
1305 "A Montgomery reduction context.",
1306
1307 0, /* @tp_traverse@ */
1308 0, /* @tp_clear@ */
1309 0, /* @tp_richcompare@ */
1310 0, /* @tp_weaklistoffset@ */
1311 0, /* @tp_iter@ */
1312 0, /* @tp_iternext@ */
1313 mpmont_pymethods, /* @tp_methods@ */
1314 0, /* @tp_members@ */
1315 mpmont_pygetset, /* @tp_getset@ */
1316 0, /* @tp_base@ */
1317 0, /* @tp_dict@ */
1318 0, /* @tp_descr_get@ */
1319 0, /* @tp_descr_set@ */
1320 0, /* @tp_dictoffset@ */
1321 0, /* @tp_init@ */
1322 PyType_GenericAlloc, /* @tp_alloc@ */
1323 mpmont_pynew, /* @tp_new@ */
1324 0, /* @tp_free@ */
1325 0 /* @tp_is_gc@ */
1326 };
1327
1328 /*----- Barrett reduction -------------------------------------------------*/
1329
1330 typedef struct mpbarrett_pyobj {
1331 PyObject_HEAD
1332 mpbarrett mb;
1333 } mpbarrett_pyobj;
1334
1335 #define MPBARRETT_PY(o) (&((mpbarrett_pyobj *)(o))->mb)
1336
1337 static PyObject *mbmeth_exp(PyObject *me, PyObject *arg)
1338 {
1339 PyObject *rc = 0;
1340 mp *yy = 0, *zz = 0;
1341
1342 if (!PyArg_ParseTuple(arg, "O&O&:exp", convmp, &yy, convmp, &zz))
1343 goto end;
1344 if (MP_NEGP(zz)) {
1345 if ((yy = mp_modinv_checked(yy, yy, MPBARRETT_PY(me)->m)) == 0) goto end;
1346 zz = mp_neg(zz, zz);
1347 }
1348 rc = mp_pywrap(mpbarrett_exp(MPBARRETT_PY(me), MP_NEW, yy, zz));
1349 end:
1350 if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
1351 return (rc);
1352 }
1353
1354 static PyObject *mb_mexp(PyObject *me, void *v, int n)
1355 { return mp_pywrap(mpbarrett_mexp(MPBARRETT_PY(me), MP_NEW, v, n)); }
1356
1357 static PyObject *mbmeth_mexp(PyObject *me, PyObject *arg)
1358 {
1359 return mexp_common(me, arg, sizeof(mp_expfactor),
1360 mp_mexp_id, mp_mexp_fill, mb_mexp, mp_mexp_drop);
1361 }
1362
1363 static PyObject *mbmeth_reduce(PyObject *me, PyObject *arg)
1364 {
1365 PyObject *z = 0;
1366 mp *yy = 0;
1367
1368 if (!PyArg_ParseTuple(arg, "O&:reduce", convmp, &yy))
1369 goto end;
1370 z = mp_pywrap(mpbarrett_reduce(MPBARRETT_PY(me), MP_NEW, yy));
1371 end:
1372 return (z);
1373 }
1374
1375 static void mpbarrett_pydealloc(PyObject *me)
1376 {
1377 mpbarrett_destroy(MPBARRETT_PY(me));
1378 FREEOBJ(me);
1379 }
1380
1381 static PyObject *mpbarrett_pynew(PyTypeObject *ty,
1382 PyObject *arg, PyObject *kw)
1383 {
1384 mpbarrett_pyobj *mb = 0;
1385 char *kwlist[] = { "m", 0 };
1386 mp *xx = 0;
1387
1388 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convmp, &xx))
1389 goto end;
1390 if (!MP_POSP(xx)) VALERR("m must be positive");
1391 mb = (mpbarrett_pyobj *)ty->tp_alloc(ty, 0);
1392 mpbarrett_create(&mb->mb, xx);
1393 end:
1394 if (xx) MP_DROP(xx);
1395 return ((PyObject *)mb);
1396 }
1397
1398 static PyObject *mbget_m(PyObject *me, void *hunoz)
1399 { return (mp_pywrap(MP_COPY(MPBARRETT_PY(me)->m))); }
1400
1401 static PyGetSetDef mpbarrett_pygetset[] = {
1402 #define GETSETNAME(op, name) mb##op##_##name
1403 GET (m, "B.m -> modulus for reduction")
1404 #undef GETSETNAME
1405 { 0 }
1406 };
1407
1408 static PyMethodDef mpbarrett_pymethods[] = {
1409 #define METHNAME(name) mbmeth_##name
1410 METH (reduce, "B.reduce(X) -> X mod B.m")
1411 METH (exp, "B.exp(X, N) -> X^N mod B.m")
1412 METH (mexp, "\
1413 B.mexp([(X0, N0), (X1, N1), ...]) = X0^N0 X1^N1 mod B.m\n\
1414 \t(the list may be flattened if this more convenient.)")
1415 #undef METHNAME
1416 { 0 }
1417 };
1418
1419 static PyTypeObject *mpbarrett_pytype, mpbarrett_pytype_skel = {
1420 PyObject_HEAD_INIT(0) 0, /* Header */
1421 "catacomb.MPBarrett", /* @tp_name@ */
1422 sizeof(mpbarrett_pyobj), /* @tp_basicsize@ */
1423 0, /* @tp_itemsize@ */
1424
1425 mpbarrett_pydealloc, /* @tp_dealloc@ */
1426 0, /* @tp_print@ */
1427 0, /* @tp_getattr@ */
1428 0, /* @tp_setattr@ */
1429 0, /* @tp_compare@ */
1430 0, /* @tp_repr@ */
1431 0, /* @tp_as_number@ */
1432 0, /* @tp_as_sequence@ */
1433 0, /* @tp_as_mapping@ */
1434 0, /* @tp_hash@ */
1435 0, /* @tp_call@ */
1436 0, /* @tp_str@ */
1437 0, /* @tp_getattro@ */
1438 0, /* @tp_setattro@ */
1439 0, /* @tp_as_buffer@ */
1440 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
1441 Py_TPFLAGS_BASETYPE,
1442
1443 /* @tp_doc@ */
1444 "A Barrett reduction context.",
1445
1446 0, /* @tp_traverse@ */
1447 0, /* @tp_clear@ */
1448 0, /* @tp_richcompare@ */
1449 0, /* @tp_weaklistoffset@ */
1450 0, /* @tp_iter@ */
1451 0, /* @tp_iternext@ */
1452 mpbarrett_pymethods, /* @tp_methods@ */
1453 0, /* @tp_members@ */
1454 mpbarrett_pygetset, /* @tp_getset@ */
1455 0, /* @tp_base@ */
1456 0, /* @tp_dict@ */
1457 0, /* @tp_descr_get@ */
1458 0, /* @tp_descr_set@ */
1459 0, /* @tp_dictoffset@ */
1460 0, /* @tp_init@ */
1461 PyType_GenericAlloc, /* @tp_alloc@ */
1462 mpbarrett_pynew, /* @tp_new@ */
1463 0, /* @tp_free@ */
1464 0 /* @tp_is_gc@ */
1465 };
1466
1467 /*----- Nice prime reduction ----------------------------------------------*/
1468
1469 typedef struct mpreduce_pyobj {
1470 PyObject_HEAD
1471 mpreduce mr;
1472 } mpreduce_pyobj;
1473
1474 #define MPREDUCE_PY(o) (&((mpreduce_pyobj *)(o))->mr)
1475
1476 static PyObject *mrmeth_exp(PyObject *me, PyObject *arg)
1477 {
1478 PyObject *rc = 0;
1479 mp *yy = 0, *zz = 0;
1480
1481 if (!PyArg_ParseTuple(arg, "O&O&:exp", convmp, &yy, convmp, &zz))
1482 goto end;
1483 if (MP_NEGP(zz)) {
1484 if ((yy = mp_modinv_checked(yy, yy, MPREDUCE_PY(me)->p)) == 0) goto end;
1485 zz = mp_neg(zz, zz);
1486 }
1487 rc = mp_pywrap(mpreduce_exp(MPREDUCE_PY(me), MP_NEW, yy, zz));
1488 end:
1489 if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
1490 return (rc);
1491 }
1492
1493 static PyObject *mrmeth_reduce(PyObject *me, PyObject *arg)
1494 {
1495 PyObject *z = 0;
1496 mp *yy = 0;
1497
1498 if (!PyArg_ParseTuple(arg, "O&:reduce", convmp, &yy)) goto end;
1499 z = mp_pywrap(mpreduce_do(MPREDUCE_PY(me), MP_NEW, yy));
1500 end:
1501 return (z);
1502 }
1503
1504 static void mpreduce_pydealloc(PyObject *me)
1505 {
1506 mpreduce_destroy(MPREDUCE_PY(me));
1507 FREEOBJ(me);
1508 }
1509
1510 static PyObject *mpreduce_pynew(PyTypeObject *ty,
1511 PyObject *arg, PyObject *kw)
1512 {
1513 mpreduce_pyobj *mr = 0;
1514 mpreduce r;
1515 char *kwlist[] = { "m", 0 };
1516 mp *xx = 0;
1517
1518 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convmp, &xx))
1519 goto end;
1520 if (!MP_POSP(xx)) VALERR("m must be positive");
1521 if (mpreduce_create(&r, xx)) VALERR("bad modulus (must be 2^k - ...)");
1522 mr = (mpreduce_pyobj *)ty->tp_alloc(ty, 0);
1523 mr->mr = r;
1524 end:
1525 if (xx) MP_DROP(xx);
1526 return ((PyObject *)mr);
1527 }
1528
1529 static PyObject *mrget_m(PyObject *me, void *hunoz)
1530 { return (mp_pywrap(MP_COPY(MPREDUCE_PY(me)->p))); }
1531
1532 static PyGetSetDef mpreduce_pygetset[] = {
1533 #define GETSETNAME(op, name) mr##op##_##name
1534 GET (m, "R.m -> modulus for reduction")
1535 #undef GETSETNAME
1536 { 0 }
1537 };
1538
1539 static PyMethodDef mpreduce_pymethods[] = {
1540 #define METHNAME(name) mrmeth_##name
1541 METH (reduce, "R.reduce(X) -> X mod B.m")
1542 METH (exp, "R.exp(X, N) -> X^N mod B.m")
1543 #undef METHNAME
1544 { 0 }
1545 };
1546
1547 static PyTypeObject *mpreduce_pytype, mpreduce_pytype_skel = {
1548 PyObject_HEAD_INIT(0) 0, /* Header */
1549 "catacomb.MPReduce", /* @tp_name@ */
1550 sizeof(mpreduce_pyobj), /* @tp_basicsize@ */
1551 0, /* @tp_itemsize@ */
1552
1553 mpreduce_pydealloc, /* @tp_dealloc@ */
1554 0, /* @tp_print@ */
1555 0, /* @tp_getattr@ */
1556 0, /* @tp_setattr@ */
1557 0, /* @tp_compare@ */
1558 0, /* @tp_repr@ */
1559 0, /* @tp_as_number@ */
1560 0, /* @tp_as_sequence@ */
1561 0, /* @tp_as_mapping@ */
1562 0, /* @tp_hash@ */
1563 0, /* @tp_call@ */
1564 0, /* @tp_str@ */
1565 0, /* @tp_getattro@ */
1566 0, /* @tp_setattro@ */
1567 0, /* @tp_as_buffer@ */
1568 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
1569 Py_TPFLAGS_BASETYPE,
1570
1571 /* @tp_doc@ */
1572 "A reduction context for reduction modulo primes of special form.",
1573
1574 0, /* @tp_traverse@ */
1575 0, /* @tp_clear@ */
1576 0, /* @tp_richcompare@ */
1577 0, /* @tp_weaklistoffset@ */
1578 0, /* @tp_iter@ */
1579 0, /* @tp_iternext@ */
1580 mpreduce_pymethods, /* @tp_methods@ */
1581 0, /* @tp_members@ */
1582 mpreduce_pygetset, /* @tp_getset@ */
1583 0, /* @tp_base@ */
1584 0, /* @tp_dict@ */
1585 0, /* @tp_descr_get@ */
1586 0, /* @tp_descr_set@ */
1587 0, /* @tp_dictoffset@ */
1588 0, /* @tp_init@ */
1589 PyType_GenericAlloc, /* @tp_alloc@ */
1590 mpreduce_pynew, /* @tp_new@ */
1591 0, /* @tp_free@ */
1592 0 /* @tp_is_gc@ */
1593 };
1594
1595 /*----- Chinese Remainder Theorem solution --------------------------------*/
1596
1597 typedef struct mpcrt_pyobj {
1598 PyObject_HEAD
1599 mpcrt c;
1600 } mpcrt_pyobj;
1601
1602 #define MPCRT_PY(o) (&((mpcrt_pyobj *)(o))->c)
1603
1604 static PyObject *mcmeth_solve(PyObject *me, PyObject *arg)
1605 {
1606 mpcrt *c = MPCRT_PY(me);
1607 PyObject *q = 0, *x, *z = 0;
1608 mp *xx;
1609 mp **v = 0;
1610 int i = 0, n = c->k;
1611
1612 Py_INCREF(me);
1613 if (PyTuple_Size(arg) == n)
1614 q = arg;
1615 else if (!PyArg_ParseTuple(arg, "O:solve", &q))
1616 goto end;
1617 Py_INCREF(q);
1618 if (!PySequence_Check(q)) TYERR("want a sequence of residues");
1619 if (PySequence_Size(q) != n) VALERR("residue count mismatch");
1620 v = xmalloc(n * sizeof(*v));
1621 for (i = 0; i < n; i++) {
1622 if ((x = PySequence_GetItem(q, i)) == 0) goto end;
1623 xx = getmp(x); Py_DECREF(x); if (!xx) goto end;
1624 v[i] = xx;
1625 }
1626 z = mp_pywrap(mpcrt_solve(c, MP_NEW, v));
1627 end:
1628 if (v) {
1629 n = i;
1630 for (i = 0; i < n; i++)
1631 MP_DROP(v[i]);
1632 xfree(v);
1633 }
1634 Py_DECREF(me);
1635 Py_XDECREF(q);
1636 return (z);
1637 }
1638
1639 static void mpcrt_pydealloc(PyObject *me)
1640 {
1641 mpcrt *c = MPCRT_PY(me);
1642 mpcrt_destroy(c);
1643 xfree(c->v);
1644 }
1645
1646 static PyObject *mpcrt_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
1647 {
1648 mpcrt_mod *v = 0;
1649 int n, i = 0;
1650 char *kwlist[] = { "mv", 0 };
1651 PyObject *q = 0, *x;
1652 mp *xx;
1653 mpcrt_pyobj *c = 0;
1654
1655 if (PyTuple_Size(arg) > 1)
1656 q = arg;
1657 else if (!PyArg_ParseTupleAndKeywords(arg, kw, "O:new", kwlist, &q))
1658 goto end;
1659 Py_INCREF(q);
1660 if (!PySequence_Check(q)) TYERR("want a sequence of moduli");
1661 n = PySequence_Size(q);
1662 if (PyErr_Occurred()) goto end;
1663 if (!n) VALERR("want at least one modulus");
1664 v = xmalloc(n * sizeof(*v));
1665 for (i = 0; i < n; i++) {
1666 if ((x = PySequence_GetItem(q, i)) == 0) goto end;
1667 xx = getmp(x); Py_DECREF(x); if (!xx) goto end;
1668 v[i].m = xx; v[i].n = 0; v[i].ni = 0; v[i].nni = 0;
1669 }
1670 c = (mpcrt_pyobj *)ty->tp_alloc(ty, 0);
1671 mpcrt_create(&c->c, v, n, 0);
1672 Py_DECREF(q);
1673 return ((PyObject *)c);
1674
1675 end:
1676 if (v) {
1677 n = i;
1678 for (i = 0; i < n; i++)
1679 MP_DROP(v[i].m);
1680 xfree(v);
1681 }
1682 Py_XDECREF(q);
1683 return (0);
1684 }
1685
1686 static PyObject *mcget_product(PyObject *me, void *hunoz)
1687 { return (mp_pywrap(MP_COPY(MPCRT_PY(me)->mb.m))); }
1688
1689 static PyObject *mcget_moduli(PyObject *me, void *hunoz)
1690 {
1691 int i;
1692 PyObject *q;
1693 mpcrt *c = MPCRT_PY(me);
1694
1695 if ((q = PyList_New(c->k)) == 0) return (0);
1696 for (i = 0; i < c->k; i++)
1697 PyList_SetItem(q, i, mp_pywrap(c->v[i].m));
1698 return (q);
1699 }
1700
1701 static PyGetSetDef mpcrt_pygetset[] = {
1702 #define GETSETNAME(op, name) mc##op##_##name
1703 GET (product, "C.product -> product of moduli")
1704 GET (moduli, "C.moduli -> list of individual moduli")
1705 #undef GETSETNAME
1706 { 0 }
1707 };
1708
1709 static PyMethodDef mpcrt_pymethods[] = {
1710 #define METHNAME(name) mcmeth_##name
1711 METH (solve, "C.solve([R0, R1]) -> X mod C.product")
1712 #undef METHNAME
1713 { 0 }
1714 };
1715
1716 static PyTypeObject *mpcrt_pytype, mpcrt_pytype_skel = {
1717 PyObject_HEAD_INIT(0) 0, /* Header */
1718 "catacomb.MPCRT", /* @tp_name@ */
1719 sizeof(mpcrt_pyobj), /* @tp_basicsize@ */
1720 0, /* @tp_itemsize@ */
1721
1722 mpcrt_pydealloc, /* @tp_dealloc@ */
1723 0, /* @tp_print@ */
1724 0, /* @tp_getattr@ */
1725 0, /* @tp_setattr@ */
1726 0, /* @tp_compare@ */
1727 0, /* @tp_repr@ */
1728 0, /* @tp_as_number@ */
1729 0, /* @tp_as_sequence@ */
1730 0, /* @tp_as_mapping@ */
1731 0, /* @tp_hash@ */
1732 0, /* @tp_call@ */
1733 0, /* @tp_str@ */
1734 0, /* @tp_getattro@ */
1735 0, /* @tp_setattro@ */
1736 0, /* @tp_as_buffer@ */
1737 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
1738 Py_TPFLAGS_BASETYPE,
1739
1740 /* @tp_doc@ */
1741 "A context for the solution of Chinese Remainder Theorem problems.",
1742
1743 0, /* @tp_traverse@ */
1744 0, /* @tp_clear@ */
1745 0, /* @tp_richcompare@ */
1746 0, /* @tp_weaklistoffset@ */
1747 0, /* @tp_iter@ */
1748 0, /* @tp_iternext@ */
1749 mpcrt_pymethods, /* @tp_methods@ */
1750 0, /* @tp_members@ */
1751 mpcrt_pygetset, /* @tp_getset@ */
1752 0, /* @tp_base@ */
1753 0, /* @tp_dict@ */
1754 0, /* @tp_descr_get@ */
1755 0, /* @tp_descr_set@ */
1756 0, /* @tp_dictoffset@ */
1757 0, /* @tp_init@ */
1758 PyType_GenericAlloc, /* @tp_alloc@ */
1759 mpcrt_pynew, /* @tp_new@ */
1760 0, /* @tp_free@ */
1761 0 /* @tp_is_gc@ */
1762 };
1763
1764 /*----- Binary polynomials ------------------------------------------------*/
1765
1766 static PyObject *gf_pyrepr(PyObject *o)
1767 { return mp_topystring(MP_X(o), 16, "GF(", "0x", "L)"); }
1768
1769 static PyObject *gf_pyrichcompare(PyObject *x, PyObject *y, int op)
1770 {
1771 mp *xx, *yy;
1772 int xl, yl;
1773 int b;
1774
1775 if (mpbinop(x, y, &xx, &yy)) RETURN_NOTIMPL;
1776 switch (op) {
1777 case Py_EQ: b = MP_EQ(xx, yy); break;
1778 case Py_NE: b = !MP_EQ(xx, yy); break;
1779 default:
1780 xl = mp_bits(xx);
1781 yl = mp_bits(yy);
1782 switch (op) {
1783 case Py_LT: b = xl < yl; break;
1784 case Py_LE: b = xl <= yl; break;
1785 case Py_GT: b = xl > yl; break;
1786 case Py_GE: b = xl >= yl; break;
1787 default: abort();
1788 }
1789 break;
1790 }
1791 MP_DROP(xx); MP_DROP(yy);
1792 return (getbool(b));
1793 }
1794
1795 static PyObject *gf_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
1796 {
1797 PyObject *x;
1798 mp *z;
1799 mp_pyobj *zz = 0;
1800 int radix = 0;
1801 char *kwlist[] = { "x", "radix", 0 };
1802
1803 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O|i:gf", kwlist, &x, &radix))
1804 goto end;
1805 if (GF_PYCHECK(x)) RETURN_OBJ(x);
1806 if (!good_radix_p(radix, 1)) VALERR("radix out of range");
1807 if ((z = mp_frompyobject(x, radix)) == 0) {
1808 PyErr_Format(PyExc_TypeError, "can't convert %.100s to gf",
1809 x->ob_type->tp_name);
1810 goto end;
1811 }
1812 if (MP_NEGP(z)) {
1813 MP_DROP(z);
1814 VALERR("gf cannot be negative");
1815 }
1816 zz = (mp_pyobj *)ty->tp_alloc(ty, 0);
1817 zz->x = z;
1818 end:
1819 return ((PyObject *)zz);
1820 }
1821
1822 static long gf_pyhash(PyObject *me)
1823 {
1824 long i = mp_tolong(MP_X(me));
1825 i ^= 0xc7ecd67c; /* random perturbance */
1826 if (i == -1)
1827 i = -2;
1828 return (i);
1829 }
1830
1831 static PyObject *gf_pyexp(PyObject *x, PyObject *y, PyObject *z)
1832 {
1833 mp *xx = 0, *yy = 0, *zz = 0;
1834 mp *r = 0;
1835 PyObject *rc = 0;
1836
1837 if ((xx = tomp(x)) == 0 || (yy = tomp(y)) == 0 ||
1838 (z && z != Py_None && (zz = tomp(z)) == 0)) {
1839 mp_drop(xx); mp_drop(yy); mp_drop(zz);
1840 RETURN_NOTIMPL;
1841 }
1842 if (!z || z == Py_None) {
1843 if (MP_NEGP(yy)) VALERR("negative exponent");
1844 r = gf_exp(MP_NEW, xx, yy);
1845 } else {
1846 gfreduce gr;
1847 if (MP_ZEROP(zz)) ZDIVERR("zero modulus");
1848 if (MP_NEGP(yy)) {
1849 if ((xx = gf_modinv_checked(xx, xx, zz)) == 0) goto end;
1850 yy = mp_neg(yy, yy);
1851 }
1852 gfreduce_create(&gr, zz);
1853 r = gfreduce_exp(&gr, MP_NEW, xx, yy);
1854 gfreduce_destroy(&gr);
1855 }
1856 rc = gf_pywrap(r);
1857 end:
1858 mp_drop(xx); mp_drop(yy); mp_drop(zz);
1859 return (rc);
1860 }
1861
1862 static PyObject *gfmeth_sqr(PyObject *me, PyObject *arg)
1863 {
1864 if (!PyArg_ParseTuple(arg, ":sqr")) return (0);
1865 return (gf_pywrap(gf_sqr(MP_NEW, MP_X(me))));
1866 }
1867
1868 static PyObject *gfmeth_gcd(PyObject *me, PyObject *arg)
1869 {
1870 PyObject *z = 0;
1871 mp *yy = 0, *zz = MP_NEW;
1872
1873 if (!PyArg_ParseTuple(arg, "O&:gcd", convgf, &yy)) goto end;
1874 gf_gcd(&zz, 0, 0, MP_X(me), yy);
1875 z = gf_pywrap(zz);
1876 end:
1877 if (yy) MP_DROP(yy);
1878 return (z);
1879 }
1880
1881 static PyObject *gfmeth_gcdx(PyObject *me, PyObject *arg)
1882 {
1883 PyObject *z = 0;
1884 mp *yy = 0, *zz = MP_NEW, *uu = MP_NEW, *vv = MP_NEW;
1885
1886 if (!PyArg_ParseTuple(arg, "O&:gcdx", convgf, &yy))
1887 goto end;
1888 gf_gcd(&zz, &uu, &vv, MP_X(me), yy);
1889 z = Py_BuildValue("(NNN)",
1890 gf_pywrap(zz), gf_pywrap(uu), gf_pywrap(vv));
1891 end:
1892 if (yy) MP_DROP(yy);
1893 return (z);
1894 }
1895
1896 static PyObject *gfmeth_modinv(PyObject *me, PyObject *arg)
1897 {
1898 PyObject *z = 0;
1899 mp *yy = 0, *zz = MP_NEW;
1900
1901 if (!PyArg_ParseTuple(arg, "O&:modinv", convgf, &yy) ||
1902 (zz = gf_modinv_checked(MP_NEW, yy, MP_X(me))) == 0)
1903 goto end;
1904 z = gf_pywrap(zz);
1905 end:
1906 if (yy) MP_DROP(yy);
1907 return (z);
1908 }
1909
1910 static PyObject *gfmeth_irreduciblep(PyObject *me, PyObject *arg)
1911 {
1912 if (!PyArg_ParseTuple(arg, ":irreduciblep")) return (0);
1913 return getbool(gf_irreduciblep(MP_X(me)));
1914 }
1915
1916 static PyObject *gfget_degree(PyObject *me, void *hunoz)
1917 { return (PyInt_FromLong(mp_bits(MP_X(me)) - 1)); }
1918
1919 static PyGetSetDef gf_pygetset[] = {
1920 #define GETSETNAME(op, name) gf##op##_##name
1921 GET (degree, "X.degree -> polynomial degree of X")
1922 #undef GETSETNAME
1923 #define GETSETNAME(op, name) mp##op##_##name
1924 GET (nbits, "X.nbits -> bit length of X")
1925 GET (noctets, "X.noctets -> octet length of X")
1926 #undef GETSETNAME
1927 { 0 }
1928 };
1929
1930 static PyMethodDef gf_pymethods[] = {
1931 #define METHNAME(func) gfmeth_##func
1932 METH (setbit, "X.setbit(N) -> X with bit N set")
1933 METH (clearbit, "X.clearbit(N) -> X with bit N clear")
1934 METH (testbit, "X.testbit(N) -> true/false if bit N set/clear in X")
1935 METH (sqr, "X.sqr() -> X^2")
1936 METH (gcd, "X.gcd(Y) -> gcd(X, Y)")
1937 METH (gcdx,
1938 "X.gcdx(Y) -> (gcd(X, Y), U, V) with X U + Y V = gcd(X, Y)")
1939 METH (modinv, "X.modinv(Y) -> multiplicative inverse of Y mod X")
1940 METH (irreduciblep, "X.irreduciblep() -> true/false")
1941 #undef METHNAME
1942 #define METHNAME(func) mpmeth_##func
1943 KWMETH(tostring, "X.tostring(radix = 10) -> STR")
1944 KWMETH(storel, "X.storel(len = -1) -> little-endian bytes")
1945 KWMETH(storeb, "X.storeb(len = -1) -> big-endian bytes")
1946 KWMETH(storel2c,
1947 "X.storel2c(len = -1) -> little-endian bytes, two's complement")
1948 KWMETH(storeb2c,
1949 "X.storeb2c(len = -1) -> big-endian bytes, two's complement")
1950 METH (tobuf, "X.tobuf() -> buffer format")
1951 #undef METHNAME
1952 { 0 }
1953 };
1954
1955 static PyNumberMethods gf_pynumber = {
1956 gf_pyadd, /* @nb_add@ */
1957 gf_pysub, /* @nb_subtract@ */
1958 gf_pymul, /* @nb_multiply@ */
1959 0, /* @nb_divide@ */
1960 gf_pymod, /* @nb_remainder@ */
1961 gf_pydivmod, /* @nb_divmod@ */
1962 gf_pyexp, /* @nb_power@ */
1963 mp_pyid, /* @nb_negative@ */
1964 mp_pyid, /* @nb_positive@ */
1965 mp_pyid, /* @nb_absolute@ */
1966 mp_pynonzerop, /* @nb_nonzero@ */
1967 0 /* doesn't make any sense */, /* @nb_invert@ */
1968 gf_pylsl, /* @nb_lshift@ */
1969 gf_pylsr, /* @nb_rshift@ */
1970 gf_pyand, /* @nb_and@ */
1971 gf_pyxor, /* @nb_xor@ */
1972 gf_pyor, /* @nb_or@ */
1973 gf_pycoerce, /* @nb_coerce@ */
1974 mp_pyint, /* @nb_int@ */
1975 mp_pylong, /* @nb_long@ */
1976 0 /* doesn't make any sense */, /* @nb_float@ */
1977 mp_pyoct, /* @nb_oct@ */
1978 mp_pyhex, /* @nb_hex@ */
1979
1980 0, /* @nb_inplace_add@ */
1981 0, /* @nb_inplace_subtract@ */
1982 0, /* @nb_inplace_multiply@ */
1983 0, /* @nb_inplace_divide@ */
1984 0, /* @nb_inplace_remainder@ */
1985 0, /* @nb_inplace_power@ */
1986 0, /* @nb_inplace_lshift@ */
1987 0, /* @nb_inplace_rshift@ */
1988 0, /* @nb_inplace_and@ */
1989 0, /* @nb_inplace_xor@ */
1990 0, /* @nb_inplace_or@ */
1991
1992 gf_pydiv, /* @nb_floor_divide@ */
1993 0, /* @nb_true_divide@ */
1994 0, /* @nb_inplace_floor_divide@ */
1995 0, /* @nb_inplace_true_divide@ */
1996 };
1997
1998 static PyTypeObject gf_pytype_skel = {
1999 PyObject_HEAD_INIT(0) 0, /* Header */
2000 "catacomb.GF", /* @tp_name@ */
2001 sizeof(mp_pyobj), /* @tp_basicsize@ */
2002 0, /* @tp_itemsize@ */
2003
2004 mp_pydealloc, /* @tp_dealloc@ */
2005 0, /* @tp_print@ */
2006 0, /* @tp_getattr@ */
2007 0, /* @tp_setattr@ */
2008 0, /* @tp_compare@ */
2009 gf_pyrepr, /* @tp_repr@ */
2010 &gf_pynumber, /* @tp_as_number@ */
2011 0, /* @tp_as_sequence@ */
2012 0, /* @tp_as_mapping@ */
2013 gf_pyhash, /* @tp_hash@ */
2014 0, /* @tp_call@ */
2015 mp_pyhex, /* @tp_str@ */
2016 0, /* @tp_getattro@ */
2017 0, /* @tp_setattro@ */
2018 0, /* @tp_as_buffer@ */
2019 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
2020 Py_TPFLAGS_CHECKTYPES |
2021 Py_TPFLAGS_BASETYPE,
2022
2023 /* @tp_doc@ */
2024 "Binary polynomials. Support almost all the standard arithmetic\n\
2025 operations.\n\
2026 \n\
2027 Constructor gf(X, radix = R) attempts to convert X to a `gf'. If\n\
2028 X is a string, it's read in radix-R form, or we look for a prefix\n\
2029 if R = 0. Other acceptable things are ints and longs.\n\
2030 \n\
2031 The name is hopelessly wrong from a technical point of view, but\n\
2032 but it's much easier to type than `p2' or `c2' or whatever.\n\
2033 \n\
2034 Notes:\n\
2035 \n\
2036 * Use `//' for division. GFs don't have `/' division.",
2037
2038 0, /* @tp_traverse@ */
2039 0, /* @tp_clear@ */
2040 gf_pyrichcompare, /* @tp_richcompare@ */
2041 0, /* @tp_weaklistoffset@ */
2042 0, /* @tp_iter@ */
2043 0, /* @tp_iternext@ */
2044 gf_pymethods, /* @tp_methods@ */
2045 0, /* @tp_members@ */
2046 gf_pygetset, /* @tp_getset@ */
2047 0, /* @tp_base@ */
2048 0, /* @tp_dict@ */
2049 0, /* @tp_descr_get@ */
2050 0, /* @tp_descr_set@ */
2051 0, /* @tp_dictoffset@ */
2052 0, /* @tp_init@ */
2053 PyType_GenericAlloc, /* @tp_alloc@ */
2054 gf_pynew, /* @tp_new@ */
2055 0, /* @tp_free@ */
2056 0 /* @tp_is_gc@ */
2057 };
2058
2059 static PyObject *meth__GF_fromstring(PyObject *me,
2060 PyObject *arg, PyObject *kw)
2061 {
2062 int r = 0;
2063 char *p;
2064 int len;
2065 PyObject *z = 0;
2066 mp *zz;
2067 mptext_stringctx sc;
2068 char *kwlist[] = { "class", "x", "radix", 0 };
2069
2070 if (!PyArg_ParseTupleAndKeywords(arg, kw, "Os#|i:fromstring",
2071 kwlist, &me, &p, &len, &r))
2072 goto end;
2073 if (!good_radix_p(r, 1)) VALERR("bad radix");
2074 sc.buf = p; sc.lim = p + len;
2075 if ((zz = mp_read(MP_NEW, r, &mptext_stringops, &sc)) == 0 ||
2076 MP_NEGP(zz)) {
2077 if (zz) MP_DROP(zz);
2078 SYNERR("bad binary polynomial");
2079 }
2080 z = Py_BuildValue("(Ns#)", gf_pywrap(zz), sc.buf, (int)(sc.lim - sc.buf));
2081 end:
2082 return (z);
2083 }
2084
2085 /*----- Sparse poly reduction ---------------------------------------------*/
2086
2087 typedef struct gfreduce_pyobj {
2088 PyObject_HEAD
2089 gfreduce mr;
2090 } gfreduce_pyobj;
2091
2092 #define GFREDUCE_PY(o) (&((gfreduce_pyobj *)(o))->mr)
2093
2094 static PyObject *grmeth_exp(PyObject *me, PyObject *arg)
2095 {
2096 PyObject *rc = 0;
2097 mp *yy = 0, *zz = 0;
2098
2099 if (!PyArg_ParseTuple(arg, "O&O&:exp", convgf, &yy, convgf, &zz))
2100 goto end;
2101 if (MP_NEGP(zz)) {
2102 if ((yy = gf_modinv_checked(yy, yy, GFREDUCE_PY(me)->p)) == 0) goto end;
2103 zz = mp_neg(zz, zz);
2104 }
2105 rc = gf_pywrap(gfreduce_exp(GFREDUCE_PY(me), MP_NEW, yy, zz));
2106 end:
2107 if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
2108 return (rc);
2109 }
2110
2111 static PyObject *grmeth_reduce(PyObject *me, PyObject *arg)
2112 {
2113 PyObject *z = 0;
2114 mp *yy = 0;
2115
2116 if (!PyArg_ParseTuple(arg, "O&:reduce", convgf, &yy)) goto end;
2117 z = gf_pywrap(gfreduce_do(GFREDUCE_PY(me), MP_NEW, yy));
2118 end:
2119 return (z);
2120 }
2121
2122 static void gfreduce_pydealloc(PyObject *me)
2123 {
2124 gfreduce_destroy(GFREDUCE_PY(me));
2125 FREEOBJ(me);
2126 }
2127
2128 static PyObject *gfreduce_pynew(PyTypeObject *ty,
2129 PyObject *arg, PyObject *kw)
2130 {
2131 gfreduce_pyobj *mr = 0;
2132 gfreduce r;
2133 char *kwlist[] = { "m", 0 };
2134 mp *xx = 0;
2135
2136 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convgf, &xx))
2137 goto end;
2138 if (MP_ZEROP(xx)) ZDIVERR("modulus is zero!");
2139 gfreduce_create(&r, xx);
2140 mr = (gfreduce_pyobj *)ty->tp_alloc(ty, 0);
2141 mr->mr = r;
2142 end:
2143 if (xx) MP_DROP(xx);
2144 return ((PyObject *)mr);
2145 }
2146
2147 static PyObject *grget_m(PyObject *me, void *hunoz)
2148 { return (gf_pywrap(MP_COPY(GFREDUCE_PY(me)->p))); }
2149
2150 static PyGetSetDef gfreduce_pygetset[] = {
2151 #define GETSETNAME(op, name) gr##op##_##name
2152 GET (m, "R.m -> reduction polynomial")
2153 #undef GETSETNAME
2154 { 0 }
2155 };
2156
2157 static PyMethodDef gfreduce_pymethods[] = {
2158 #define METHNAME(name) grmeth_##name
2159 METH (reduce, "R.reduce(X) -> X mod B.m")
2160 METH (exp, "R.exp(X, N) -> X^N mod B.m")
2161 #undef METHNAME
2162 { 0 }
2163 };
2164
2165 static PyTypeObject *gfreduce_pytype, gfreduce_pytype_skel = {
2166 PyObject_HEAD_INIT(0) 0, /* Header */
2167 "catacomb.GFReduce", /* @tp_name@ */
2168 sizeof(gfreduce_pyobj), /* @tp_basicsize@ */
2169 0, /* @tp_itemsize@ */
2170
2171 gfreduce_pydealloc, /* @tp_dealloc@ */
2172 0, /* @tp_print@ */
2173 0, /* @tp_getattr@ */
2174 0, /* @tp_setattr@ */
2175 0, /* @tp_compare@ */
2176 0, /* @tp_repr@ */
2177 0, /* @tp_as_number@ */
2178 0, /* @tp_as_sequence@ */
2179 0, /* @tp_as_mapping@ */
2180 0, /* @tp_hash@ */
2181 0, /* @tp_call@ */
2182 0, /* @tp_str@ */
2183 0, /* @tp_getattro@ */
2184 0, /* @tp_setattro@ */
2185 0, /* @tp_as_buffer@ */
2186 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
2187 Py_TPFLAGS_BASETYPE,
2188
2189 /* @tp_doc@ */
2190 "A reduction context for reduction modulo sparse irreducible polynomials.",
2191
2192 0, /* @tp_traverse@ */
2193 0, /* @tp_clear@ */
2194 0, /* @tp_richcompare@ */
2195 0, /* @tp_weaklistoffset@ */
2196 0, /* @tp_iter@ */
2197 0, /* @tp_iternext@ */
2198 gfreduce_pymethods, /* @tp_methods@ */
2199 0, /* @tp_members@ */
2200 gfreduce_pygetset, /* @tp_getset@ */
2201 0, /* @tp_base@ */
2202 0, /* @tp_dict@ */
2203 0, /* @tp_descr_get@ */
2204 0, /* @tp_descr_set@ */
2205 0, /* @tp_dictoffset@ */
2206 0, /* @tp_init@ */
2207 PyType_GenericAlloc, /* @tp_alloc@ */
2208 gfreduce_pynew, /* @tp_new@ */
2209 0, /* @tp_free@ */
2210 0 /* @tp_is_gc@ */
2211 };
2212
2213 /*----- Normal/poly transformation ----------------------------------------*/
2214
2215 typedef struct gfn_pyobj {
2216 PyObject_HEAD
2217 mp *p;
2218 gfn ntop, pton;
2219 } gfn_pyobj;
2220
2221 static PyTypeObject *gfn_pytype, gfn_pytype_skel;
2222
2223 #define GFN_P(o) (((gfn_pyobj *)(o))->p)
2224 #define GFN_PTON(o) (&((gfn_pyobj *)(o))->pton)
2225 #define GFN_NTOP(o) (&((gfn_pyobj *)(o))->ntop)
2226
2227 static PyObject *gfn_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
2228 {
2229 mp *p = 0, *beta = 0;
2230 gfn_pyobj *gg = 0;
2231 char *kwlist[] = { "p", "beta", 0 };
2232
2233 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&O&:new", kwlist,
2234 convgf, &p, convgf, &beta))
2235 goto end;
2236 gg = PyObject_New(gfn_pyobj, ty);
2237 if (gfn_create(p, beta, &gg->ntop, &gg->pton)) {
2238 FREEOBJ(gg);
2239 gg = 0;
2240 VALERR("can't invert transformation matrix");
2241 }
2242 gg->p = MP_COPY(p);
2243 end:
2244 mp_drop(p);
2245 mp_drop(beta);
2246 return ((PyObject *)gg);
2247 }
2248
2249 static PyObject *gfnget_p(PyObject *me, void *hunoz)
2250 { return (gf_pywrap(MP_COPY(GFN_P(me)))); }
2251
2252 static PyObject *gfnget_beta(PyObject *me, void *hunoz)
2253 {
2254 gfn *n = GFN_NTOP(me);
2255 mp *x = n->r[n->n - 1];
2256 return (gf_pywrap(MP_COPY(x)));
2257 }
2258
2259 #define XFORMOP(name, NAME) \
2260 static PyObject *gfnmeth_##name(PyObject *me, PyObject *arg) \
2261 { \
2262 mp *xx = 0; \
2263 mp *z = 0; \
2264 \
2265 if (!PyArg_ParseTuple(arg, "O&:" #name, convgf, &xx)) goto end; \
2266 z = gfn_transform(GFN_##NAME(me), MP_NEW, xx); \
2267 end: \
2268 mp_drop(xx); \
2269 if (!z) return (0); \
2270 return (mp_pywrap(z)); \
2271 }
2272 XFORMOP(pton, PTON)
2273 XFORMOP(ntop, NTOP)
2274 #undef XFORMOP
2275
2276 static void gfn_pydealloc(PyObject *me)
2277 {
2278 gfn_destroy(GFN_PTON(me));
2279 gfn_destroy(GFN_NTOP(me));
2280 FREEOBJ(me);
2281 }
2282
2283 static PyGetSetDef gfn_pygetset[] = {
2284 #define GETSETNAME(op, name) gfn##op##_##name
2285 GET (p, "X.p -> polynomial basis, as polynomial")
2286 GET (beta, "X.beta -> normal basis element, in poly form")
2287 #undef GETSETNAME
2288 { 0 }
2289 };
2290
2291 static PyMethodDef gfn_pymethods[] = {
2292 #define METHNAME(name) gfnmeth_##name
2293 METH (pton, "X.pton(A) -> normal-basis representation of A")
2294 METH (ntop, "X.ntop(A) -> polynomial-basis representation of A")
2295 #undef METHNAME
2296 { 0 }
2297 };
2298
2299 static PyTypeObject gfn_pytype_skel = {
2300 PyObject_HEAD_INIT(0) 0, /* Header */
2301 "catacomb.GFN", /* @tp_name@ */
2302 sizeof(gfn_pyobj), /* @tp_basicsize@ */
2303 0, /* @tp_itemsize@ */
2304
2305 gfn_pydealloc, /* @tp_dealloc@ */
2306 0, /* @tp_print@ */
2307 0, /* @tp_getattr@ */
2308 0, /* @tp_setattr@ */
2309 0, /* @tp_compare@ */
2310 0, /* @tp_repr@ */
2311 0, /* @tp_as_number@ */
2312 0, /* @tp_as_sequence@ */
2313 0, /* @tp_as_mapping@ */
2314 0, /* @tp_hash@ */
2315 0, /* @tp_call@ */
2316 0, /* @tp_str@ */
2317 0, /* @tp_getattro@ */
2318 0, /* @tp_setattro@ */
2319 0, /* @tp_as_buffer@ */
2320 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
2321 Py_TPFLAGS_BASETYPE,
2322
2323 /* @tp_doc@ */
2324 "An object for transforming elements of binary fields between polynomial\n\
2325 and normal basis representations.",
2326
2327 0, /* @tp_traverse@ */
2328 0, /* @tp_clear@ */
2329 0, /* @tp_richcompare@ */
2330 0, /* @tp_weaklistoffset@ */
2331 0, /* @tp_iter@ */
2332 0, /* @tp_iternext@ */
2333 gfn_pymethods, /* @tp_methods@ */
2334 0, /* @tp_members@ */
2335 gfn_pygetset, /* @tp_getset@ */
2336 0, /* @tp_base@ */
2337 0, /* @tp_dict@ */
2338 0, /* @tp_descr_get@ */
2339 0, /* @tp_descr_set@ */
2340 0, /* @tp_dictoffset@ */
2341 0, /* @tp_init@ */
2342 PyType_GenericAlloc, /* @tp_alloc@ */
2343 gfn_pynew, /* @tp_new@ */
2344 0, /* @tp_free@ */
2345 0 /* @tp_is_gc@ */
2346 };
2347
2348 /*----- Glue --------------------------------------------------------------*/
2349
2350 static PyMethodDef methods[] = {
2351 #define METHNAME(func) meth_##func
2352 KWMETH(_MP_fromstring, "\
2353 fromstring(STR, radix = 0) -> (X, REST)\n\
2354 \n\
2355 Parse STR as a large integer, according to radix. If radix is zero,\n\
2356 read a prefix from STR to decide radix: allow `0' for octal, `0x' for hex\n\
2357 or `R_' for other radix R.")
2358 KWMETH(_GF_fromstring, "\
2359 fromstring(STR, radix = 0) -> (X, REST)\n\
2360 \n\
2361 Parse STR as a binary polynomial, according to radix. If radix is zero,\n\
2362 read a prefix from STR to decide radix: allow `0' for octal, `0x' for hex\n\
2363 or `R_' for other radix R.")
2364 METH (_MP_loadl, "\
2365 loadl(STR) -> X: read little-endian bytes")
2366 METH (_MP_loadb, "\
2367 loadb(STR) -> X: read big-endian bytes")
2368 METH (_MP_loadl2c, "\
2369 loadl2c(STR) -> X: read little-endian bytes, two's complement")
2370 METH (_MP_loadb2c, "\
2371 loadb2c(STR) -> X: read big-endian bytes, two's complement")
2372 METH (_MP_frombuf, "\
2373 frombuf(STR) -> (X, REST): read buffer format")
2374 METH (_GF_loadl, "\
2375 loadl(STR) -> X: read little-endian bytes")
2376 METH (_GF_loadb, "\
2377 loadb(STR) -> X: read big-endian bytes")
2378 METH (_GF_frombuf, "\
2379 frombuf(STR) -> (X, REST): read buffer format")
2380 #undef METHNAME
2381 { 0 }
2382 };
2383
2384 void mp_pyinit(void)
2385 {
2386 INITTYPE(mp, root);
2387 INITTYPE(gf, root);
2388 INITTYPE(mpmul, root);
2389 INITTYPE(mpmont, root);
2390 INITTYPE(mpbarrett, root);
2391 INITTYPE(mpreduce, root);
2392 INITTYPE(mpcrt, root);
2393 INITTYPE(gfreduce, root);
2394 INITTYPE(gfn, root);
2395 addmethods(methods);
2396 }
2397
2398 void mp_pyinsert(PyObject *mod)
2399 {
2400 INSERT("MP", mp_pytype);
2401 INSERT("MPMul", mpmul_pytype);
2402 INSERT("MPMont", mpmont_pytype);
2403 INSERT("MPBarrett", mpbarrett_pytype);
2404 INSERT("MPReduce", mpreduce_pytype);
2405 INSERT("MPCRT", mpcrt_pytype);
2406 INSERT("GF", gf_pytype);
2407 INSERT("GFReduce", gfreduce_pytype);
2408 INSERT("GFN", gfn_pytype);
2409 }
2410
2411 /*----- That's all, folks -------------------------------------------------*/
Catacomb cryptographic library -- Python bindings