~mdw / catacomb-python / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
mp: Replace MP.product() by an MPMul class. Much more useful.
[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 #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("radix out of range");
2074 sc.buf = p; sc.lim = p + len;
2075 if ((zz = mp_read(MP_NEW, r, &mptext_stringops, &sc)) == 0 || MP_NEGP(zz))
2076 z = Py_BuildValue("(Os#)", Py_None, p, len);
2077 else
2078 z = Py_BuildValue("(Ns#)", gf_pywrap(zz),
2079 sc.buf, (int)(sc.lim - sc.buf));
2080 end:
2081 return (z);
2082 }
2083
2084 /*----- Sparse poly reduction ---------------------------------------------*/
2085
2086 typedef struct gfreduce_pyobj {
2087 PyObject_HEAD
2088 gfreduce mr;
2089 } gfreduce_pyobj;
2090
2091 #define GFREDUCE_PY(o) (&((gfreduce_pyobj *)(o))->mr)
2092
2093 static PyObject *grmeth_exp(PyObject *me, PyObject *arg)
2094 {
2095 PyObject *rc = 0;
2096 mp *yy = 0, *zz = 0;
2097
2098 if (!PyArg_ParseTuple(arg, "O&O&:exp", convgf, &yy, convgf, &zz))
2099 goto end;
2100 if (MP_NEGP(zz)) {
2101 if ((yy = gf_modinv_checked(yy, yy, GFREDUCE_PY(me)->p)) == 0) goto end;
2102 zz = mp_neg(zz, zz);
2103 }
2104 rc = gf_pywrap(gfreduce_exp(GFREDUCE_PY(me), MP_NEW, yy, zz));
2105 end:
2106 if (yy) MP_DROP(yy); if (zz) MP_DROP(zz);
2107 return (rc);
2108 }
2109
2110 static PyObject *grmeth_reduce(PyObject *me, PyObject *arg)
2111 {
2112 PyObject *z = 0;
2113 mp *yy = 0;
2114
2115 if (!PyArg_ParseTuple(arg, "O&:reduce", convgf, &yy)) goto end;
2116 z = gf_pywrap(gfreduce_do(GFREDUCE_PY(me), MP_NEW, yy));
2117 end:
2118 return (z);
2119 }
2120
2121 static void gfreduce_pydealloc(PyObject *me)
2122 {
2123 gfreduce_destroy(GFREDUCE_PY(me));
2124 FREEOBJ(me);
2125 }
2126
2127 static PyObject *gfreduce_pynew(PyTypeObject *ty,
2128 PyObject *arg, PyObject *kw)
2129 {
2130 gfreduce_pyobj *mr = 0;
2131 gfreduce r;
2132 char *kwlist[] = { "m", 0 };
2133 mp *xx = 0;
2134
2135 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convgf, &xx))
2136 goto end;
2137 if (MP_ZEROP(xx)) ZDIVERR("modulus is zero!");
2138 gfreduce_create(&r, xx);
2139 mr = (gfreduce_pyobj *)ty->tp_alloc(ty, 0);
2140 mr->mr = r;
2141 end:
2142 if (xx) MP_DROP(xx);
2143 return ((PyObject *)mr);
2144 }
2145
2146 static PyObject *grget_m(PyObject *me, void *hunoz)
2147 { return (gf_pywrap(MP_COPY(GFREDUCE_PY(me)->p))); }
2148
2149 static PyGetSetDef gfreduce_pygetset[] = {
2150 #define GETSETNAME(op, name) gr##op##_##name
2151 GET (m, "R.m -> reduction polynomial")
2152 #undef GETSETNAME
2153 { 0 }
2154 };
2155
2156 static PyMethodDef gfreduce_pymethods[] = {
2157 #define METHNAME(name) grmeth_##name
2158 METH (reduce, "R.reduce(X) -> X mod B.m")
2159 METH (exp, "R.exp(X, N) -> X^N mod B.m")
2160 #undef METHNAME
2161 { 0 }
2162 };
2163
2164 static PyTypeObject *gfreduce_pytype, gfreduce_pytype_skel = {
2165 PyObject_HEAD_INIT(0) 0, /* Header */
2166 "catacomb.GFReduce", /* @tp_name@ */
2167 sizeof(gfreduce_pyobj), /* @tp_basicsize@ */
2168 0, /* @tp_itemsize@ */
2169
2170 gfreduce_pydealloc, /* @tp_dealloc@ */
2171 0, /* @tp_print@ */
2172 0, /* @tp_getattr@ */
2173 0, /* @tp_setattr@ */
2174 0, /* @tp_compare@ */
2175 0, /* @tp_repr@ */
2176 0, /* @tp_as_number@ */
2177 0, /* @tp_as_sequence@ */
2178 0, /* @tp_as_mapping@ */
2179 0, /* @tp_hash@ */
2180 0, /* @tp_call@ */
2181 0, /* @tp_str@ */
2182 0, /* @tp_getattro@ */
2183 0, /* @tp_setattro@ */
2184 0, /* @tp_as_buffer@ */
2185 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
2186 Py_TPFLAGS_BASETYPE,
2187
2188 /* @tp_doc@ */
2189 "A reduction context for reduction modulo sparse irreducible polynomials.",
2190
2191 0, /* @tp_traverse@ */
2192 0, /* @tp_clear@ */
2193 0, /* @tp_richcompare@ */
2194 0, /* @tp_weaklistoffset@ */
2195 0, /* @tp_iter@ */
2196 0, /* @tp_iternext@ */
2197 gfreduce_pymethods, /* @tp_methods@ */
2198 0, /* @tp_members@ */
2199 gfreduce_pygetset, /* @tp_getset@ */
2200 0, /* @tp_base@ */
2201 0, /* @tp_dict@ */
2202 0, /* @tp_descr_get@ */
2203 0, /* @tp_descr_set@ */
2204 0, /* @tp_dictoffset@ */
2205 0, /* @tp_init@ */
2206 PyType_GenericAlloc, /* @tp_alloc@ */
2207 gfreduce_pynew, /* @tp_new@ */
2208 0, /* @tp_free@ */
2209 0 /* @tp_is_gc@ */
2210 };
2211
2212 /*----- Normal/poly transformation ----------------------------------------*/
2213
2214 typedef struct gfn_pyobj {
2215 PyObject_HEAD
2216 mp *p;
2217 gfn ntop, pton;
2218 } gfn_pyobj;
2219
2220 static PyTypeObject *gfn_pytype, gfn_pytype_skel;
2221
2222 #define GFN_P(o) (((gfn_pyobj *)(o))->p)
2223 #define GFN_PTON(o) (&((gfn_pyobj *)(o))->pton)
2224 #define GFN_NTOP(o) (&((gfn_pyobj *)(o))->ntop)
2225
2226 static PyObject *gfn_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
2227 {
2228 mp *p = 0, *beta = 0;
2229 gfn_pyobj *gg = 0;
2230 char *kwlist[] = { "p", "beta", 0 };
2231
2232 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&O&:new", kwlist,
2233 convgf, &p, convgf, &beta))
2234 goto end;
2235 gg = PyObject_New(gfn_pyobj, ty);
2236 if (gfn_create(p, beta, &gg->ntop, &gg->pton)) {
2237 FREEOBJ(gg);
2238 gg = 0;
2239 VALERR("can't invert transformation matrix");
2240 }
2241 gg->p = MP_COPY(p);
2242 end:
2243 mp_drop(p);
2244 mp_drop(beta);
2245 return ((PyObject *)gg);
2246 }
2247
2248 static PyObject *gfnget_p(PyObject *me, void *hunoz)
2249 { return (gf_pywrap(MP_COPY(GFN_P(me)))); }
2250
2251 static PyObject *gfnget_beta(PyObject *me, void *hunoz)
2252 {
2253 gfn *n = GFN_NTOP(me);
2254 mp *x = n->r[n->n - 1];
2255 return (gf_pywrap(MP_COPY(x)));
2256 }
2257
2258 #define XFORMOP(name, NAME) \
2259 static PyObject *gfnmeth_##name(PyObject *me, PyObject *arg) \
2260 { \
2261 mp *xx = 0; \
2262 mp *z = 0; \
2263 \
2264 if (!PyArg_ParseTuple(arg, "O&:" #name, convgf, &xx)) goto end; \
2265 z = gfn_transform(GFN_##NAME(me), MP_NEW, xx); \
2266 end: \
2267 mp_drop(xx); \
2268 if (!z) return (0); \
2269 return (mp_pywrap(z)); \
2270 }
2271 XFORMOP(pton, PTON)
2272 XFORMOP(ntop, NTOP)
2273 #undef XFORMOP
2274
2275 static void gfn_pydealloc(PyObject *me)
2276 {
2277 gfn_destroy(GFN_PTON(me));
2278 gfn_destroy(GFN_NTOP(me));
2279 FREEOBJ(me);
2280 }
2281
2282 static PyGetSetDef gfn_pygetset[] = {
2283 #define GETSETNAME(op, name) gfn##op##_##name
2284 GET (p, "X.p -> polynomial basis, as polynomial")
2285 GET (beta, "X.beta -> normal basis element, in poly form")
2286 #undef GETSETNAME
2287 { 0 }
2288 };
2289
2290 static PyMethodDef gfn_pymethods[] = {
2291 #define METHNAME(name) gfnmeth_##name
2292 METH (pton, "X.pton(A) -> normal-basis representation of A")
2293 METH (ntop, "X.ntop(A) -> polynomial-basis representation of A")
2294 #undef METHNAME
2295 { 0 }
2296 };
2297
2298 static PyTypeObject gfn_pytype_skel = {
2299 PyObject_HEAD_INIT(0) 0, /* Header */
2300 "catacomb.GFN", /* @tp_name@ */
2301 sizeof(gfn_pyobj), /* @tp_basicsize@ */
2302 0, /* @tp_itemsize@ */
2303
2304 gfn_pydealloc, /* @tp_dealloc@ */
2305 0, /* @tp_print@ */
2306 0, /* @tp_getattr@ */
2307 0, /* @tp_setattr@ */
2308 0, /* @tp_compare@ */
2309 0, /* @tp_repr@ */
2310 0, /* @tp_as_number@ */
2311 0, /* @tp_as_sequence@ */
2312 0, /* @tp_as_mapping@ */
2313 0, /* @tp_hash@ */
2314 0, /* @tp_call@ */
2315 0, /* @tp_str@ */
2316 0, /* @tp_getattro@ */
2317 0, /* @tp_setattro@ */
2318 0, /* @tp_as_buffer@ */
2319 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
2320 Py_TPFLAGS_BASETYPE,
2321
2322 /* @tp_doc@ */
2323 "An object for transforming elements of binary fields between polynomial\n\
2324 and normal basis representations.",
2325
2326 0, /* @tp_traverse@ */
2327 0, /* @tp_clear@ */
2328 0, /* @tp_richcompare@ */
2329 0, /* @tp_weaklistoffset@ */
2330 0, /* @tp_iter@ */
2331 0, /* @tp_iternext@ */
2332 gfn_pymethods, /* @tp_methods@ */
2333 0, /* @tp_members@ */
2334 gfn_pygetset, /* @tp_getset@ */
2335 0, /* @tp_base@ */
2336 0, /* @tp_dict@ */
2337 0, /* @tp_descr_get@ */
2338 0, /* @tp_descr_set@ */
2339 0, /* @tp_dictoffset@ */
2340 0, /* @tp_init@ */
2341 PyType_GenericAlloc, /* @tp_alloc@ */
2342 gfn_pynew, /* @tp_new@ */
2343 0, /* @tp_free@ */
2344 0 /* @tp_is_gc@ */
2345 };
2346
2347 /*----- Glue --------------------------------------------------------------*/
2348
2349 static PyMethodDef methods[] = {
2350 #define METHNAME(func) meth_##func
2351 KWMETH(_MP_fromstring, "\
2352 fromstring(STR, radix = 0) -> (X, REST)\n\
2353 \n\
2354 Parse STR as a large integer, according to radix. If radix is zero,\n\
2355 read a prefix from STR to decide radix: allow `0' for octal, `0x' for hex\n\
2356 or `R_' for other radix R.")
2357 KWMETH(_GF_fromstring, "\
2358 fromstring(STR, radix = 0) -> (X, REST)\n\
2359 \n\
2360 Parse STR as a binary polynomial, according to radix. If radix is zero,\n\
2361 read a prefix from STR to decide radix: allow `0' for octal, `0x' for hex\n\
2362 or `R_' for other radix R.")
2363 METH (_MP_loadl, "\
2364 loadl(STR) -> X: read little-endian bytes")
2365 METH (_MP_loadb, "\
2366 loadb(STR) -> X: read big-endian bytes")
2367 METH (_MP_loadl2c, "\
2368 loadl2c(STR) -> X: read little-endian bytes, two's complement")
2369 METH (_MP_loadb2c, "\
2370 loadb2c(STR) -> X: read big-endian bytes, two's complement")
2371 METH (_MP_frombuf, "\
2372 frombuf(STR) -> (X, REST): read buffer format")
2373 METH (_GF_loadl, "\
2374 loadl(STR) -> X: read little-endian bytes")
2375 METH (_GF_loadb, "\
2376 loadb(STR) -> X: read big-endian bytes")
2377 METH (_GF_frombuf, "\
2378 frombuf(STR) -> (X, REST): read buffer format")
2379 #undef METHNAME
2380 { 0 }
2381 };
2382
2383 void mp_pyinit(void)
2384 {
2385 INITTYPE(mp, root);
2386 INITTYPE(gf, root);
2387 INITTYPE(mpmul, root);
2388 INITTYPE(mpmont, root);
2389 INITTYPE(mpbarrett, root);
2390 INITTYPE(mpreduce, root);
2391 INITTYPE(mpcrt, root);
2392 INITTYPE(gfreduce, root);
2393 INITTYPE(gfn, root);
2394 addmethods(methods);
2395 }
2396
2397 void mp_pyinsert(PyObject *mod)
2398 {
2399 INSERT("MP", mp_pytype);
2400 INSERT("MPMul", mpmul_pytype);
2401 INSERT("MPMont", mpmont_pytype);
2402 INSERT("MPBarrett", mpbarrett_pytype);
2403 INSERT("MPReduce", mpreduce_pytype);
2404 INSERT("MPCRT", mpcrt_pytype);
2405 INSERT("GF", gf_pytype);
2406 INSERT("GFReduce", gfreduce_pytype);
2407 INSERT("GFN", gfn_pytype);
2408 }
2409
2410 /*----- That's all, folks -------------------------------------------------*/
Catacomb cryptographic library -- Python bindings