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