chiark / gitweb /
~mdw / catacomb-python / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Various other little bits.
[catacomb-python] / pgen.c
CommitLineData
d7ab1bab 1/* -*-c-*-
2 *
3 * $Id$
4 *
5 * Prime number generation
6 *
7 * (c) 2005 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/*----- Filters -----------------------------------------------------------*/
34
35PyTypeObject *pfilt_pytype;
36
37static PyObject *pfilt_pywrap(pfilt *f)
38{
39 pfilt_pyobj *o = 0;
40 o = PyObject_New(pfilt_pyobj, pfilt_pytype);
41 o->f = *f;
42 o->st = pfilt_step(f, 0);
43 return ((PyObject *)o);
44}
45
46static PyObject *pfilt_pymake(PyTypeObject *ty, PyObject *xobj)
47{
48 mp *x = 0;
49 pfilt_pyobj *o = 0;
50
51 if (PFILT_PYCHECK(xobj)) RETURN_OBJ(xobj);
52 if ((x = getmp(xobj)) == 0) goto end;
53 o = (pfilt_pyobj *)ty->tp_alloc(ty, 0);
54 o->st = pfilt_create(&o->f, x);
55end:
56 mp_drop(x);
57 return ((PyObject *)o);
58}
59
60static PyObject *pfilt_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
61{
62 char *kwlist[] = { "x", 0 };
63 PyObject *xobj;
64
65 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O:new", kwlist, &xobj))
66 return (0);
67 return (pfilt_pymake(ty, xobj));
68}
69
70static void pfilt_pydealloc(PyObject *me)
3aa33042 71 { pfilt_destroy(PFILT_F(me)); FREEOBJ(me); }
d7ab1bab 72
73static PyObject *pfmeth_step(PyObject *me, PyObject *arg)
74{
75 mpw x;
76
77 if (!PyArg_ParseTuple(arg, "O&:step", convmpw, &x)) return (0);
78 PFILT_ST(me) = pfilt_step(PFILT_F(me), x);
79 RETURN_ME;
80}
81
82static PyObject *pfmeth_muladd(PyObject *me, PyObject *arg)
83{
84 mpw m, a;
85 pfilt_pyobj *o = 0;
86
87 if (!PyArg_ParseTuple(arg, "O&O&:muladd", convmpw, &m, convmpw, &a))
88 return (0);
89 o = PyObject_New(pfilt_pyobj, pfilt_pytype);
90 o->st = pfilt_muladd(&o->f, PFILT_F(me), m, a);
91 return ((PyObject *)o);
92}
93
94static CONVFUNC(pfilt, pfilt *, PFILT_F)
95
96static PyObject *pfmeth_jump(PyObject *me, PyObject *arg)
97{
98 pfilt *f;
99
100 if (!PyArg_ParseTuple(arg, "O&:jump", convpfilt, &f)) return (0);
101 PFILT_ST(me) = pfilt_jump(PFILT_F(me), f);
102 RETURN_ME;
103}
104
105static PyObject *meth__PrimeFilter_smallfactor(PyObject *me, PyObject *arg)
106{
107 mp *x = 0;
108 PyObject *rc = 0;
109
110 if (!PyArg_ParseTuple(arg, "OO&:smallfactor", &me, convmp, &x)) goto end;
111 rc = PyInt_FromLong(pfilt_smallfactor(x));
112end:
113 mp_drop(x);
114 return (rc);
115}
116
117static int pfilt_pynonzerop(PyObject *me)
118 { return (PFILT_ST(me) != PGEN_FAIL); }
119
120static PyObject *pfilt_pyint(PyObject *me)
121{
122 long l;
123 PyObject *rc = 0;
124
125 if (mp_tolong_checked(PFILT_F(me)->m, &l)) goto end;
126 rc = PyInt_FromLong(l);
127end:
128 return (rc);
129}
130
131static PyObject *pfilt_pylong(PyObject *me)
132 { return ((PyObject *)mp_topylong(PFILT_F(me)->m)); }
133
134static PyObject *pfget_x(PyObject *me, void *hunoz)
135 { return (mp_pywrap(MP_COPY(PFILT_F(me)->m))); }
136
137static PyObject *pfget_status(PyObject *me, void *hunoz)
138 { return (PyInt_FromLong(PFILT_ST(me))); }
139
140static PyGetSetDef pfilt_pygetset[] = {
141#define GETSETNAME(op, name) pf##op##_##name
142 GET (x, "F.x -> current position of filter")
143 GET (status, "F.status -> primality status of filter")
144#undef GETSETNAME
145 { 0 }
146};
147
148static PyMethodDef pfilt_pymethods[] = {
149#define METHNAME(name) pfmeth_##name
150 METH (step, "F.step(N)")
151 METH (muladd, "F.muladd(M, A)")
152 METH (jump, "F.jump(FF)")
153#undef METHNAME
154 { 0 }
155};
156
157static PyNumberMethods pfilt_pynumber = {
158 0, /* @nb_add@ */
159 0, /* @nb_subtract@ */
160 0, /* @nb_multiply@ */
161 0, /* @nb_divide@ */
162 0, /* @nb_remainder@ */
163 0, /* @nb_divmod@ */
164 0, /* @nb_power@ */
165 0, /* @nb_negative@ */
166 0, /* @nb_positive@ */
167 0, /* @nb_absolute@ */
168 pfilt_pynonzerop, /* @nb_nonzero@ */
169 0, /* @nb_invert@ */
170 0, /* @nb_lshift@ */
171 0, /* @nb_rshift@ */
172 0, /* @nb_and@ */
173 0, /* @nb_xor@ */
174 0, /* @nb_or@ */
175 0, /* @nb_coerce@ */
176 pfilt_pyint, /* @nb_int@ */
177 pfilt_pylong, /* @nb_long@ */
178 0, /* @nb_float@ */
179 0, /* @nb_oct@ */
180 0, /* @nb_hex@ */
181
182 0, /* @nb_inplace_add@ */
183 0, /* @nb_inplace_subtract@ */
184 0, /* @nb_inplace_multiply@ */
185 0, /* @nb_inplace_divide@ */
186 0, /* @nb_inplace_remainder@ */
187 0, /* @nb_inplace_power@ */
188 0, /* @nb_inplace_lshift@ */
189 0, /* @nb_inplace_rshift@ */
190 0, /* @nb_inplace_and@ */
191 0, /* @nb_inplace_xor@ */
192 0, /* @nb_inplace_or@ */
193
194 0, /* @nb_floor_divide@ */
195 0, /* @nb_true_divide@ */
196 0, /* @nb_inplace_floor_divide@ */
197 0, /* @nb_inplace_true_divide@ */
198};
199
200static PyTypeObject pfilt_pytype_skel = {
201 PyObject_HEAD_INIT(&PyType_Type) 0, /* Header */
202 "catacomb.PrimeFilter", /* @tp_name@ */
203 sizeof(pfilt_pyobj), /* @tp_basicsize@ */
204 0, /* @tp_itemsize@ */
205
206 pfilt_pydealloc, /* @tp_dealloc@ */
207 0, /* @tp_print@ */
208 0, /* @tp_getattr@ */
209 0, /* @tp_setattr@ */
210 0, /* @tp_compare@ */
211 0, /* @tp_repr@ */
212 &pfilt_pynumber, /* @tp_as_number@ */
213 0, /* @tp_as_sequence@ */
214 0, /* @tp_as_mapping@ */
215 0, /* @tp_hash@ */
216 0, /* @tp_call@ */
217 0, /* @tp_str@ */
218 0, /* @tp_getattro@ */
219 0, /* @tp_setattro@ */
220 0, /* @tp_as_buffer@ */
221 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
222 Py_TPFLAGS_BASETYPE,
223
224 /* @tp_doc@ */
225"Small-primes filter.",
226
227 0, /* @tp_traverse@ */
228 0, /* @tp_clear@ */
229 0, /* @tp_richcompare@ */
230 0, /* @tp_weaklistoffset@ */
231 0, /* @tp_iter@ */
232 0, /* @tp_iternexr@ */
233 pfilt_pymethods, /* @tp_methods@ */
234 0, /* @tp_members@ */
235 pfilt_pygetset, /* @tp_getset@ */
236 0, /* @tp_base@ */
237 0, /* @tp_dict@ */
238 0, /* @tp_descr_get@ */
239 0, /* @tp_descr_set@ */
240 0, /* @tp_dictoffset@ */
241 0, /* @tp_init@ */
242 PyType_GenericAlloc, /* @tp_alloc@ */
243 pfilt_pynew, /* @tp_new@ */
3aa33042 244 0, /* @tp_free@ */
d7ab1bab 245 0 /* @tp_is_gc@ */
246};
247
248/*----- Rabin-Miller testing ----------------------------------------------*/
249
250typedef struct rabin_pyobj {
251 PyObject_HEAD
252 rabin r;
253} rabin_pyobj;
254
255static PyTypeObject *rabin_pytype;
256#define RABIN_R(o) (&((rabin_pyobj *)(o))->r)
257
258static PyObject *rabin_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
259{
260 mp *x = 0;
261 rabin_pyobj *o = 0;
262 char *kwlist[] = { "x", 0 };
263
264 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convmp, &x))
265 goto end;
266 if (!MP_POSP(x) || MP_EVENP(x)) VALERR("must be positive and odd");
267 o = (rabin_pyobj *)ty->tp_alloc(ty, 0);
268 rabin_create(&o->r, x);
269end:
270 return ((PyObject *)o);
271}
272
273static void rabin_pydealloc(PyObject *me)
274{
275 rabin_destroy(RABIN_R(me));
3aa33042 276 FREEOBJ(me);
d7ab1bab 277}
278
279static PyObject *rmeth_test(PyObject *me, PyObject *arg)
280{
281 mp *w = 0;
282 PyObject *rc = 0;
283
284 if (!PyArg_ParseTuple(arg, "O&:test", convmp, &w)) goto end;
285 rc = PyInt_FromLong(rabin_test(RABIN_R(me), w));
286end:
287 mp_drop(w);
288 return (rc);
289}
290
291static PyObject *rmeth_rtest(PyObject *me, PyObject *arg)
292{
293 mp *w = 0;
294 PyObject *rc = 0;
295
296 if (!PyArg_ParseTuple(arg, "O&:rtest", convmp, &w)) goto end;
297 rc = PyInt_FromLong(rabin_rtest(RABIN_R(me), w));
298end:
299 mp_drop(w);
300 return (rc);
301}
302
303static PyObject *rget_niters(PyObject *me, void *hunoz)
304 { return (PyInt_FromLong(rabin_iters(mp_bits(RABIN_R(me)->mm.m)))); }
305
306static PyObject *rget_x(PyObject *me, void *hunoz)
307 { return (mp_pywrap(MP_COPY(RABIN_R(me)->mm.m))); }
308
309static PyObject *meth__RabinMiller_iters(PyObject *me, PyObject *arg)
310{
311 unsigned n;
312
313 if (!PyArg_ParseTuple(arg, "OO&:iters", &me, convuint, &n)) return (0);
314 return (PyInt_FromLong(rabin_iters(n)));
315}
316
317static PyGetSetDef rabin_pygetset[] = {
318#define GETSETNAME(op, name) r##op##_##name
319 GET (x, "R.x -> number under test")
320 GET (niters, "R.niters -> suggested number of tests")
321#undef GETSETNAME
322 { 0 }
323};
324
325static PyMethodDef rabin_pymethods[] = {
326#define METHNAME(name) rmeth_##name
327 METH (test, "R.test(W) -> PGST")
328 METH (rtest, "R.rtest(W) -> PGST")
329#undef METHNAME
330 { 0 }
331};
332
333static PyTypeObject rabin_pytype_skel = {
334 PyObject_HEAD_INIT(&PyType_Type) 0, /* Header */
335 "catacomb.RabinMiller", /* @tp_name@ */
336 sizeof(rabin_pyobj), /* @tp_basicsize@ */
337 0, /* @tp_itemsize@ */
338
339 rabin_pydealloc, /* @tp_dealloc@ */
340 0, /* @tp_print@ */
341 0, /* @tp_getattr@ */
342 0, /* @tp_setattr@ */
343 0, /* @tp_compare@ */
344 0, /* @tp_repr@ */
345 0, /* @tp_as_number@ */
346 0, /* @tp_as_sequence@ */
347 0, /* @tp_as_mapping@ */
348 0, /* @tp_hash@ */
349 0, /* @tp_call@ */
350 0, /* @tp_str@ */
351 0, /* @tp_getattro@ */
352 0, /* @tp_setattro@ */
353 0, /* @tp_as_buffer@ */
354 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
355 Py_TPFLAGS_BASETYPE,
356
357 /* @tp_doc@ */
358"Rabin-Miller strong primality test.",
359
360 0, /* @tp_traverse@ */
361 0, /* @tp_clear@ */
362 0, /* @tp_richcompare@ */
363 0, /* @tp_weaklistoffset@ */
364 0, /* @tp_iter@ */
365 0, /* @tp_iternexr@ */
366 rabin_pymethods, /* @tp_methods@ */
367 0, /* @tp_members@ */
368 rabin_pygetset, /* @tp_getset@ */
369 0, /* @tp_base@ */
370 0, /* @tp_dict@ */
371 0, /* @tp_descr_get@ */
372 0, /* @tp_descr_set@ */
373 0, /* @tp_dictoffset@ */
374 0, /* @tp_init@ */
375 PyType_GenericAlloc, /* @tp_alloc@ */
376 rabin_pynew, /* @tp_new@ */
3aa33042 377 0, /* @tp_free@ */
d7ab1bab 378 0 /* @tp_is_gc@ */
379};
380
381/*----- Events ------------------------------------------------------------*/
382
383typedef struct pgevent_pyobj {
384 PyObject_HEAD
385 pgen_event *ev;
386} pgevent_pyobj;
387
388static PyTypeObject *pgevent_pytype;
389#define PGEVENT_EV(o) (((pgevent_pyobj *)(o))->ev)
390
391static PyObject *pgevent_pywrap(pgen_event *ev)
392{
393 pgevent_pyobj *o = PyObject_New(pgevent_pyobj, pgevent_pytype);
394 o->ev = ev;
395 return ((PyObject *)o);
396}
397
398static CONVFUNC(pgevent, pgen_event *, PGEVENT_EV)
399
400static void pgevent_kill(PyObject *me) { PGEVENT_EV(me) = 0; }
3aa33042 401static void pgevent_pydealloc(PyObject *me) { FREEOBJ(me); }
d7ab1bab 402
403#define PGEVENT_CHECK(me) do { \
404 if (!PGEVENT_EV(me)) { \
405 PyErr_SetString(PyExc_ValueError, "event object is dead"); \
406 return (0); \
407 } \
408} while (0)
409
410static PyObject *peget_name(PyObject *me, void *hunoz)
411 { PGEVENT_CHECK(me); return (PyString_FromString(PGEVENT_EV(me)->name)); }
412
413static PyObject *peget_x(PyObject *me, void *hunoz)
414 { PGEVENT_CHECK(me); return (mp_pywrap(MP_COPY(PGEVENT_EV(me)->m))); }
415
416static PyObject *peget_steps(PyObject *me, void *hunoz)
417 { PGEVENT_CHECK(me); return (PyInt_FromLong(PGEVENT_EV(me)->steps)); }
418
419static PyObject *peget_tests(PyObject *me, void *hunoz)
420 { PGEVENT_CHECK(me); return (PyInt_FromLong(PGEVENT_EV(me)->tests)); }
421
422static PyObject *peget_rng(PyObject *me, void *hunoz)
423 { PGEVENT_CHECK(me); return (grand_pywrap(PGEVENT_EV(me)->r, 0)); }
424
425static int peset_x(PyObject *me, PyObject *xobj, void *hunoz)
426{
427 mp *x = 0;
428 pgen_event *ev = PGEVENT_EV(me);
429 int rc = -1;
430 PGEVENT_CHECK(me);
431 if ((x = getmp(xobj)) == 0) goto end;
432 mp_drop(ev->m);
433 ev->m = MP_COPY(x);
434 rc = 0;
435end:
436 mp_drop(x);
437 return (rc);
438}
439
440static PyGetSetDef pgevent_pygetset[] = {
441#define GETSETNAME(op, name) pe##op##_##name
442 GET (name, "EV.name -> value being generated")
443 GETSET(x, "EV.x -> value under test")
444 GET (steps, "EV.steps -> number of steps left")
445 GET (tests, "EV.tests -> tests before passing")
446 GET (rng, "EV.rng -> (noncrypto) random number generator")
447#undef GETSETNAME
448 { 0 }
449};
450
451static PyTypeObject pgevent_pytype_skel = {
452 PyObject_HEAD_INIT(&PyType_Type) 0, /* Header */
453 "catacomb.PrimeGenEvent", /* @tp_name@ */
454 sizeof(pgevent_pyobj), /* @tp_basicsize@ */
455 0, /* @tp_itemsize@ */
456
457 pgevent_pydealloc, /* @tp_dealloc@ */
458 0, /* @tp_print@ */
459 0, /* @tp_getattr@ */
460 0, /* @tp_setattr@ */
461 0, /* @tp_compare@ */
462 0, /* @tp_repr@ */
463 0, /* @tp_as_number@ */
464 0, /* @tp_as_sequence@ */
465 0, /* @tp_as_mapping@ */
466 0, /* @tp_hash@ */
467 0, /* @tp_call@ */
468 0, /* @tp_str@ */
469 0, /* @tp_getattro@ */
470 0, /* @tp_setattro@ */
471 0, /* @tp_as_buffer@ */
472 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
473 Py_TPFLAGS_BASETYPE,
474
475 /* @tp_doc@ */
476"Prime-generation event.",
477
478 0, /* @tp_traverse@ */
479 0, /* @tp_clear@ */
480 0, /* @tp_richcompare@ */
481 0, /* @tp_weaklistoffset@ */
482 0, /* @tp_iter@ */
483 0, /* @tp_iternexr@ */
484 0, /* @tp_methods@ */
485 0, /* @tp_members@ */
486 pgevent_pygetset, /* @tp_getset@ */
487 0, /* @tp_base@ */
488 0, /* @tp_dict@ */
489 0, /* @tp_descr_get@ */
490 0, /* @tp_descr_set@ */
491 0, /* @tp_dictoffset@ */
492 0, /* @tp_init@ */
493 PyType_GenericAlloc, /* @tp_alloc@ */
494 abstract_pynew, /* @tp_new@ */
3aa33042 495 0, /* @tp_free@ */
d7ab1bab 496 0 /* @tp_is_gc@ */
497};
498
499/*----- Event handlers ----------------------------------------------------*/
500
501PyTypeObject *pgev_pytype;
502
503typedef struct pgstep_pyobj {
504 PGEV_HEAD
505 pgen_filterctx f;
506} pgstep_pyobj;
507
508static PyTypeObject *pgstep_pytype;
509#define PGSTEP_STEP(o) (((pgstep_pyobj *)(o))->f.step)
510
511typedef struct pgjump_pyobj {
512 PGEV_HEAD
513 PyObject *fobj;
514 pgen_jumpctx j;
515} pgjump_pyobj;
516
517static PyTypeObject *pgjump_pytype;
518#define PGJUMP_FOBJ(o) (((pgjump_pyobj *)(o))->fobj)
519#define PGJUMP_J(o) (&((pgjump_pyobj *)(o))->j)
520
521typedef struct pgtest_pyobj {
522 PGEV_HEAD
523 rabin r;
524} pgtest_pyobj;
525
526static PyTypeObject *pgtest_pytype;
527
528static int pgev_python(int rq, pgen_event *ev, void *p)
529{
530 PyObject *py = p;
531 PyObject *pyev = 0;
532 PyObject *rc = 0;
533 int st = PGEN_ABORT;
534 long l;
535 char *meth[] = {
536 "pg_abort", "pg_done", "pg_begin", "pg_try", "pg_fail", "pg_pass"
537 };
538
539 Py_INCREF(py);
540 rq++;
541 if (rq > N(meth)) SYSERR("event code out of range");
542 pyev = pgevent_pywrap(ev);
543 if ((rc = PyObject_CallMethod(py, meth[rq], "(O)", pyev)) == 0)
544 goto end;
545 if (rc == Py_None)
546 st = PGEN_TRY;
547 else if ((l = PyInt_AsLong(rc)) == -1 && PyErr_Occurred())
548 goto end;
549 else if (l < PGEN_ABORT || l > PGEN_PASS)
550 VALERR("return code out of range");
551 else
552 st = l;
553end:
554 if (pyev) {
555 pgevent_kill(pyev);
556 Py_DECREF(pyev);
557 }
558 Py_XDECREF(rc);
559 Py_DECREF(py);
560 return (st);
561}
562
563static PyObject *pgev_pywrap(const pgev *pg)
564{
565 pgev_pyobj *o;
566
567 o = PyObject_New(pgev_pyobj, pgev_pytype);
568 o->pg = *pg;
569 return ((PyObject *)o);
570}
571
572int convpgev(PyObject *o, void *p)
573{
574 pgev *pg = p;
575
576 if (PGEV_PYCHECK(o))
577 *pg = *PGEV_PG(o);
578 else {
579 pg->proc = pgev_python;
580 pg->ctx = o;
581 Py_INCREF(o);
582 }
583 return (1);
584}
585
586void droppgev(pgev *p)
587{
588 if (p->proc == pgev_python) {
589 PyObject *py = p->ctx;
590 Py_DECREF(py);
591 }
592}
593
594static PyObject *pgmeth_common(PyObject *me, PyObject *arg, int rq)
595{
596 pgen_event *ev;
597 pgev *pg = PGEV_PG(me);
598 PyObject *rc = 0;
599
600 if (!PyArg_ParseTuple(arg, "O&", convpgevent, &ev)) goto end;
601 rc = PyInt_FromLong(!pg->proc ? rq : pg->proc(rq, ev, pg->ctx));
602end:
603 return (rc);
604}
605
606#define PGMETH(lc, uc) \
607 static PyObject *pgmeth_pg_##lc(PyObject *me, PyObject *arg) \
608 { return pgmeth_common(me, arg, PGEN_##uc); }
609PGMETH(abort, ABORT)
610PGMETH(done, DONE)
611PGMETH(begin, BEGIN)
612PGMETH(try, TRY)
613PGMETH(pass, PASS)
614PGMETH(fail, FAIL)
615#undef PGMETH
616
617static PyObject *pgev_stdev(pgen_proc *proc)
618 { pgev pg; pg.proc = proc; pg.ctx = 0; return (pgev_pywrap(&pg)); }
619
620static PyMethodDef pgev_pymethods[] = {
621#define METHNAME(name) pgmeth_##name
622 METH (pg_abort, "E.pg_abort() -> PGRC -- prime generation aborted")
623 METH (pg_done, "E.pg_done() -> PGRC -- prime generation finished")
624 METH (pg_begin, "E.pg_begin() -> PGRC -- commence stepping/testing")
625 METH (pg_try, "E.pg_try() -> PGRC -- found new candidate")
626 METH (pg_pass, "E.pg_pass() -> PGRC -- passed primality test")
627 METH (pg_fail, "E.pg_fail() -> PGRC -- failed primality test")
628#undef METHNAME
629 { 0 }
630};
631
632static PyTypeObject pgev_pytype_skel = {
633 PyObject_HEAD_INIT(&PyType_Type) 0, /* Header */
634 "catacomb.PrimeGenBuiltinHandler", /* @tp_name@ */
635 sizeof(pgev_pyobj), /* @tp_basicsize@ */
636 0, /* @tp_itemsize@ */
637
3aa33042 638 0, /* @tp_dealloc@ */
d7ab1bab 639 0, /* @tp_print@ */
640 0, /* @tp_getattr@ */
641 0, /* @tp_setattr@ */
642 0, /* @tp_compare@ */
643 0, /* @tp_repr@ */
644 0, /* @tp_as_number@ */
645 0, /* @tp_as_sequence@ */
646 0, /* @tp_as_mapping@ */
647 0, /* @tp_hash@ */
648 0, /* @tp_call@ */
649 0, /* @tp_str@ */
650 0, /* @tp_getattro@ */
651 0, /* @tp_setattro@ */
652 0, /* @tp_as_buffer@ */
653 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
654 Py_TPFLAGS_BASETYPE,
655
656 /* @tp_doc@ */
657"Built-in prime-generation event handler, base class.",
658
659 0, /* @tp_traverse@ */
660 0, /* @tp_clear@ */
661 0, /* @tp_richcompare@ */
662 0, /* @tp_weaklistoffset@ */
663 0, /* @tp_iter@ */
664 0, /* @tp_iternexr@ */
665 pgev_pymethods, /* @tp_methods@ */
666 0, /* @tp_members@ */
667 0, /* @tp_getset@ */
668 0, /* @tp_base@ */
669 0, /* @tp_dict@ */
670 0, /* @tp_descr_get@ */
671 0, /* @tp_descr_set@ */
672 0, /* @tp_dictoffset@ */
673 0, /* @tp_init@ */
674 PyType_GenericAlloc, /* @tp_alloc@ */
675 abstract_pynew, /* @tp_new@ */
3aa33042 676 0, /* @tp_free@ */
d7ab1bab 677 0 /* @tp_is_gc@ */
678};
679
680static PyObject *pgstep_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
681{
682 mpw s;
683 pgstep_pyobj *rc = 0;
684 char *kwlist[] = { "step", 0 };
685
686 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&:new", kwlist, convmpw, &s))
687 goto end;
688 rc = (pgstep_pyobj *)ty->tp_alloc(ty, 0);
689 rc->f.step = s;
690 rc->pg.proc = pgen_filter;
691 rc->pg.ctx = &rc->f;
692end:
693 return ((PyObject *)rc);
694}
695
696static PyObject *psget_step(PyObject *me, void *hunoz)
697 { return (PyInt_FromLong(PGSTEP_STEP(me))); }
698
699static PyGetSetDef pgstep_pygetset[] = {
700#define GETSETNAME(op, name) ps##op##_##name
701 GET (step, "S.step -> step size for the stepper")
702#undef GETSETNAME
703 { 0 }
704};
705
706static PyTypeObject pgstep_pytype_skel = {
707 PyObject_HEAD_INIT(&PyType_Type) 0, /* Header */
708 "catacomb.PrimeGenStepper", /* @tp_name@ */
709 sizeof(pgstep_pyobj), /* @tp_basicsize@ */
710 0, /* @tp_itemsize@ */
711
712 0, /* @tp_dealloc@ */
713 0, /* @tp_print@ */
714 0, /* @tp_getattr@ */
715 0, /* @tp_setattr@ */
716 0, /* @tp_compare@ */
717 0, /* @tp_repr@ */
718 0, /* @tp_as_number@ */
719 0, /* @tp_as_sequence@ */
720 0, /* @tp_as_mapping@ */
721 0, /* @tp_hash@ */
722 0, /* @tp_call@ */
723 0, /* @tp_str@ */
724 0, /* @tp_getattro@ */
725 0, /* @tp_setattro@ */
726 0, /* @tp_as_buffer@ */
727 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
728 Py_TPFLAGS_BASETYPE,
729
730 /* @tp_doc@ */
731 "Simple prime-number stepper with small-factors filter.",
732
733 0, /* @tp_traverse@ */
734 0, /* @tp_clear@ */
735 0, /* @tp_richcompare@ */
736 0, /* @tp_weaklistoffset@ */
737 0, /* @tp_iter@ */
738 0, /* @tp_iternexr@ */
739 0, /* @tp_methods@ */
740 0, /* @tp_members@ */
741 pgstep_pygetset, /* @tp_getset@ */
742 0, /* @tp_base@ */
743 0, /* @tp_dict@ */
744 0, /* @tp_descr_get@ */
745 0, /* @tp_descr_set@ */
746 0, /* @tp_dictoffset@ */
747 0, /* @tp_init@ */
748 PyType_GenericAlloc, /* @tp_alloc@ */
749 pgstep_pynew, /* @tp_new@ */
3aa33042 750 0, /* @tp_free@ */
d7ab1bab 751 0 /* @tp_is_gc@ */
752};
753
754static PyObject *pgjump_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
755{
756 PyObject *o, *fobj;
757 pgjump_pyobj *rc = 0;
758 char *kwlist[] = { "jump", 0 };
759
760 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O:new", kwlist, &o) ||
761 (fobj = pfilt_pymake(pfilt_pytype, o)) == 0)
762 goto end;
763 rc = (pgjump_pyobj *)ty->tp_alloc(ty, 0);
764 rc->fobj = fobj;
765 rc->j.j = PFILT_F(fobj);
766 rc->pg.proc = pgen_jump;
767 rc->pg.ctx = &rc->j;
768end:
769 return ((PyObject *)rc);
770}
771
772static void pgjump_pydealloc(PyObject *me)
773{
774 Py_DECREF(PGJUMP_FOBJ(me));
3aa33042 775 FREEOBJ(me);
d7ab1bab 776}
777
778static PyObject *pjget_jump(PyObject *me, void *hunoz)
779 { RETURN_OBJ(PGJUMP_FOBJ(me)); }
780
781static PyGetSetDef pgjump_pygetset[] = {
782#define GETSETNAME(op, name) pj##op##_##name
783 GET (jump, "S.jump -> jump size for the stepper")
784#undef GETSETNAME
785 { 0 }
786};
787
788static PyTypeObject pgjump_pytype_skel = {
789 PyObject_HEAD_INIT(&PyType_Type) 0, /* Header */
790 "catacomb.PrimeGenJumper", /* @tp_name@ */
791 sizeof(pgjump_pyobj), /* @tp_basicsize@ */
792 0, /* @tp_itemsize@ */
793
794 pgjump_pydealloc, /* @tp_dealloc@ */
795 0, /* @tp_print@ */
796 0, /* @tp_getattr@ */
797 0, /* @tp_setattr@ */
798 0, /* @tp_compare@ */
799 0, /* @tp_repr@ */
800 0, /* @tp_as_number@ */
801 0, /* @tp_as_sequence@ */
802 0, /* @tp_as_mapping@ */
803 0, /* @tp_hash@ */
804 0, /* @tp_call@ */
805 0, /* @tp_str@ */
806 0, /* @tp_getattro@ */
807 0, /* @tp_setattro@ */
808 0, /* @tp_as_buffer@ */
809 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
810 Py_TPFLAGS_BASETYPE,
811
812 /* @tp_doc@ */
813"Stepper for larger steps, with small-factors filter.",
814
815 0, /* @tp_traverse@ */
816 0, /* @tp_clear@ */
817 0, /* @tp_richcompare@ */
818 0, /* @tp_weaklistoffset@ */
819 0, /* @tp_iter@ */
820 0, /* @tp_iternexr@ */
821 0, /* @tp_methods@ */
822 0, /* @tp_members@ */
823 pgjump_pygetset, /* @tp_getset@ */
824 0, /* @tp_base@ */
825 0, /* @tp_dict@ */
826 0, /* @tp_descr_get@ */
827 0, /* @tp_descr_set@ */
828 0, /* @tp_dictoffset@ */
829 0, /* @tp_init@ */
830 PyType_GenericAlloc, /* @tp_alloc@ */
831 pgjump_pynew, /* @tp_new@ */
3aa33042 832 0, /* @tp_free@ */
d7ab1bab 833 0 /* @tp_is_gc@ */
834};
835
836static PyObject *pgtest_pynew(PyTypeObject *ty, PyObject *arg, PyObject *kw)
837{
838 pgtest_pyobj *rc = 0;
839 char *kwlist[] = { 0 };
840
841 if (!PyArg_ParseTupleAndKeywords(arg, kw, ":new", kwlist)) goto end;
842 rc = (pgtest_pyobj *)ty->tp_alloc(ty, 0);
843 rc->pg.proc = pgen_test;
844 rc->pg.ctx = &rc->r;
845end:
846 return ((PyObject *)rc);
847}
848
849static PyTypeObject pgtest_pytype_skel = {
850 PyObject_HEAD_INIT(&PyType_Type) 0, /* Header */
851 "catacomb.PrimeGenTester", /* @tp_name@ */
852 sizeof(pgtest_pyobj), /* @tp_basicsize@ */
853 0, /* @tp_itemsize@ */
854
855 0, /* @tp_dealloc@ */
856 0, /* @tp_print@ */
857 0, /* @tp_getattr@ */
858 0, /* @tp_setattr@ */
859 0, /* @tp_compare@ */
860 0, /* @tp_repr@ */
861 0, /* @tp_as_number@ */
862 0, /* @tp_as_sequence@ */
863 0, /* @tp_as_mapping@ */
864 0, /* @tp_hash@ */
865 0, /* @tp_call@ */
866 0, /* @tp_str@ */
867 0, /* @tp_getattro@ */
868 0, /* @tp_setattro@ */
869 0, /* @tp_as_buffer@ */
870 Py_TPFLAGS_DEFAULT | /* @tp_flags@ */
871 Py_TPFLAGS_BASETYPE,
872
873 /* @tp_doc@ */
874"Rabin-Miller tester.",
875
876 0, /* @tp_traverse@ */
877 0, /* @tp_clear@ */
878 0, /* @tp_richcompare@ */
879 0, /* @tp_weaklistoffset@ */
880 0, /* @tp_iter@ */
881 0, /* @tp_iternexr@ */
882 0, /* @tp_methods@ */
883 0, /* @tp_members@ */
884 0, /* @tp_getset@ */
885 0, /* @tp_base@ */
886 0, /* @tp_dict@ */
887 0, /* @tp_descr_get@ */
888 0, /* @tp_descr_set@ */
889 0, /* @tp_dictoffset@ */
890 0, /* @tp_init@ */
891 PyType_GenericAlloc, /* @tp_alloc@ */
892 pgtest_pynew, /* @tp_new@ */
3aa33042 893 0, /* @tp_free@ */
d7ab1bab 894 0 /* @tp_is_gc@ */
895};
896
897/*----- Prime generation functions ----------------------------------------*/
898
899void pgenerr(void)
900{
901 if (!PyErr_Occurred())
902 PyErr_SetString(PyExc_ValueError, "prime generation failed");
903}
904
905static PyObject *meth_pgen(PyObject *me, PyObject *arg, PyObject *kw)
906{
907 mp *x = 0;
908 mp *r = 0;
909 PyObject *rc = 0;
910 char *p = "p";
911 pgen_filterctx fc = { 2 };
912 rabin tc;
913 pgev step = { 0 }, test = { 0 }, evt = { 0 };
914 unsigned nsteps = 0, ntests = 0;
915 char *kwlist[] = { "start", "name", "stepper", "tester", "event",
916 "nsteps", "ntests", 0 };
917
918 step.proc = pgen_filter; step.ctx = &fc;
919 test.proc = pgen_test; test.ctx = &tc;
920 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&|sO&O&O&O&O&:pgen", kwlist,
921 convmp, &x, &p, convpgev, &step,
922 convpgev, &test, convpgev, &evt,
923 convuint, &nsteps, convuint, &ntests))
924 goto end;
925 if (!ntests) ntests = rabin_iters(mp_bits(x));
926 if ((r = pgen(p, MP_NEW, x, evt.proc, evt.ctx,
927 nsteps, step.proc, step.ctx,
928 ntests, test.proc, test.ctx)) == 0)
929 PGENERR;
930 if (PyErr_Occurred()) goto end;
931 rc = mp_pywrap(r);
932 r = 0;
933end:
934 mp_drop(r); mp_drop(x);
935 droppgev(&step); droppgev(&test); droppgev(&evt);
936 return (rc);
937}
938
939static PyObject *meth_strongprime_setup(PyObject *me,
940 PyObject *arg, PyObject *kw)
941{
942 mp *x = 0;
943 pfilt f;
944 grand *r = &rand_global;
945 unsigned nbits;
946 char *name = "p";
947 unsigned n = 0;
948 pgev evt = { 0 };
949 PyObject *rc = 0;
950 char *kwlist[] = { "nbits", "name", "event", "rng", "nsteps", 0 };
951
952 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&|sO&O&O&", kwlist,
953 convuint, &nbits, &name,
954 convpgev, &evt, convgrand, &r,
955 convuint, &n))
956 goto end;
957 if ((x = strongprime_setup(name, MP_NEW, &f, nbits,
958 r, n, evt.proc, evt.ctx)) == 0)
959 PGENERR;
960 rc = Py_BuildValue("(NN)", mp_pywrap(x), pfilt_pywrap(&f));
961 x = 0;
962end:
963 mp_drop(x);
964 droppgev(&evt);
965 return (rc);
966}
967
968static PyObject *meth_strongprime(PyObject *me, PyObject *arg, PyObject *kw)
969{
970 mp *x = 0;
971 grand *r = &rand_global;
972 unsigned nbits;
973 char *name = "p";
974 unsigned n = 0;
975 pgev evt = { 0 };
976 PyObject *rc = 0;
977 char *kwlist[] = { "nbits", "name", "event", "rng", "nsteps", 0 };
978
979 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&|sO&O&O&", kwlist,
980 convuint, &nbits, &name,
981 convpgev, &evt, convgrand, &r,
982 convuint, &n))
983 goto end;
984 if ((x = strongprime(name, MP_NEW, nbits,
985 r, n, evt.proc, evt.ctx)) == 0)
986 PGENERR;
987 rc = mp_pywrap(x);
988 x = 0;
989end:
990 mp_drop(x);
991 droppgev(&evt);
992 return (rc);
993}
994
995static PyObject *meth_limlee(PyObject *me, PyObject *arg, PyObject *kw)
996{
997 char *p = "p";
998 pgev ie = { 0 }, oe = { 0 };
999 unsigned ql, pl;
1000 grand *r = &rand_global;
1001 unsigned on = 0;
1002 size_t i, nf = 0;
1003 PyObject *rc = 0, *vec;
1004 char *kwlist[] = { "pbits", "qbits", "name", "event", "ievent",
1005 "rng", "nsteps", 0 };
1006 mp *x = 0, **v = 0;
1007
1008 if (!PyArg_ParseTupleAndKeywords(arg, kw, "O&O&|sO&O&O&O&:limlee", kwlist,
1009 convuint, &pl, convuint, &ql,
1010 &p, convpgev, &oe, convpgev, &ie,
1011 convgrand, &r, convuint, &on))
1012 goto end;
1013 if ((x = limlee(p, MP_NEW, MP_NEW, ql, pl, r, on,
1014 oe.proc, oe.ctx, ie.proc, ie.ctx, &nf, &v)) == 0)
1015 PGENERR;
1016 vec = PyList_New(nf);
1017 for (i = 0; i < nf; i++)
1018 PyList_SetItem(vec, i, mp_pywrap(v[i]));
1019 xfree(v);
1020 rc = Py_BuildValue("(NN)", mp_pywrap(x), vec);
1021end:
1022 droppgev(&oe); droppgev(&ie);
1023 return (rc);
1024}
1025
1026/*----- Global stuff ------------------------------------------------------*/
1027
1028static PyMethodDef methods[] = {
1029#define METHNAME(name) meth_##name
1030 METH (_PrimeFilter_smallfactor, "smallfactor(X) -> PGRC")
1031 METH (_RabinMiller_iters, "iters(NBITS) -> NITERS")
1032 KWMETH(pgen, "\
1033pgen(START, [name = 'p', stepper = PrimeGenStepper(2),\n\
1034 tester = PrimeGenTester(), event = pgen_nullev,\n\
1035 nsteps = 0, ntests = RabinMiller.iters(START.nbits)]) -> P")
1036 KWMETH(strongprime_setup, "\
1037strongprime_setup(NBITS, [name = 'p', event = pgen_nullev,\n\
1038 rng = rand, nsteps = 0]) -> (START, JUMP)")
1039 KWMETH(strongprime, "\
1040strongprime_setup(NBITS, [name = 'p', event = pgen_nullev,\n\
1041 rng = rand, nsteps = 0]) -> P")
1042 KWMETH(limlee, "\
1043limlee(PBITS, QBITS, [name = 'p', event = pgen_nullev,\n\
1044 ievent = pgen_nullev, rng = rand, nsteps = 0]) -> (P, [Q, ...])")
1045#undef METHNAME
1046 { 0 }
1047};
1048
1049void pgen_pyinit(void)
1050{
1051 INITTYPE(pfilt, root);
1052 INITTYPE(rabin, root);
1053 INITTYPE(pgevent, root);
1054 INITTYPE(pgev, root);
1055 INITTYPE(pgstep, pgev);
1056 INITTYPE(pgjump, pgev);
1057 INITTYPE(pgtest, pgev);
1058 addmethods(methods);
1059}
1060
1061static PyObject *obj;
1062
1063void pgen_pyinsert(PyObject *mod)
1064{
1065 INSERT("PrimeFilter", pfilt_pytype);
1066 INSERT("RabinMiller", rabin_pytype);
1067 INSERT("PrimeGenEvent", pgevent_pytype);
1068 INSERT("PrimeGenBuiltinHandler", pgev_pytype);
1069 INSERT("PrimeGenStepper", pgstep_pytype);
1070 INSERT("PrimeGenJumper", pgjump_pytype);
1071 INSERT("PrimeGenTester", pgtest_pytype);
1072 INSERT("pgen_nullev", obj = pgev_stdev(0));
1073 INSERT("pgen_stdev", pgev_stdev(pgen_ev));
1074 INSERT("pgen_spinev", pgev_stdev(pgen_evspin));
1075 INSERT("pgen_subev", pgev_stdev(pgen_subev));
1076}
1077
1078/*----- That's all, folks -------------------------------------------------*/
Catacomb cryptographic library -- Python bindings